michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "jit/LICM.h"
michael@0: 
michael@0: #include <stdio.h>
michael@0: 
michael@0: #include "jit/IonSpewer.h"
michael@0: #include "jit/MIR.h"
michael@0: #include "jit/MIRGenerator.h"
michael@0: #include "jit/MIRGraph.h"
michael@0: 
michael@0: using namespace js;
michael@0: using namespace js::jit;
michael@0: 
michael@0: namespace {
michael@0: 
michael@0: typedef Vector<MInstruction*, 1, IonAllocPolicy> InstructionQueue;
michael@0: 
michael@0: class Loop
michael@0: {
michael@0:     MIRGenerator *mir;
michael@0: 
michael@0:   public:
michael@0:     // Loop code may return three values:
michael@0:     enum LoopReturn {
michael@0:         LoopReturn_Success,
michael@0:         LoopReturn_Error, // Compilation failure.
michael@0:         LoopReturn_Skip   // The loop is not suitable for LICM, but there is no error.
michael@0:     };
michael@0: 
michael@0:   public:
michael@0:     // A loop is constructed on a backedge found in the control flow graph.
michael@0:     Loop(MIRGenerator *mir, MBasicBlock *footer);
michael@0: 
michael@0:     // Initializes the loop, finds all blocks and instructions contained in the loop.
michael@0:     LoopReturn init();
michael@0: 
michael@0:     // Identifies hoistable loop invariant instructions and moves them out of the loop.
michael@0:     bool optimize();
michael@0: 
michael@0:   private:
michael@0:     // These blocks define the loop.  header_ points to the loop header
michael@0:     MBasicBlock *header_;
michael@0: 
michael@0:     // The pre-loop block is the first predecessor of the loop header.  It is where
michael@0:     // the loop is first entered and where hoisted instructions will be placed.
michael@0:     MBasicBlock* preLoop_;
michael@0: 
michael@0:     // This indicates whether the loop contains calls or other things which
michael@0:     // clobber most or all floating-point registers. In such loops,
michael@0:     // floating-point constants should not be hoisted unless it enables further
michael@0:     // hoisting.
michael@0:     bool containsPossibleCall_;
michael@0: 
michael@0:     TempAllocator &alloc() const {
michael@0:         return mir->alloc();
michael@0:     }
michael@0: 
michael@0:     bool hoistInstructions(InstructionQueue &toHoist);
michael@0: 
michael@0:     // Utility methods for invariance testing and instruction hoisting.
michael@0:     bool isInLoop(MDefinition *ins);
michael@0:     bool isBeforeLoop(MDefinition *ins);
michael@0:     bool isLoopInvariant(MInstruction *ins);
michael@0: 
michael@0:     // This method determines if this block hot within a loop.  That is, if it's
michael@0:     // always or usually run when the loop executes
michael@0:     bool checkHotness(MBasicBlock *block);
michael@0: 
michael@0:     // Worklist and worklist usage methods
michael@0:     InstructionQueue worklist_;
michael@0:     bool insertInWorklist(MInstruction *ins);
michael@0:     MInstruction* popFromWorklist();
michael@0: 
michael@0:     inline bool isHoistable(const MDefinition *ins) const {
michael@0:         return ins->isMovable() && !ins->isEffectful() && !ins->neverHoist();
michael@0:     }
michael@0: 
michael@0:     bool requiresHoistedUse(const MDefinition *ins) const;
michael@0: };
michael@0: 
michael@0: } /* namespace anonymous */
michael@0: 
michael@0: LICM::LICM(MIRGenerator *mir, MIRGraph &graph)
michael@0:   : mir(mir), graph(graph)
michael@0: {
michael@0: }
michael@0: 
michael@0: bool
michael@0: LICM::analyze()
michael@0: {
michael@0:     IonSpew(IonSpew_LICM, "Beginning LICM pass.");
michael@0: 
michael@0:     // Iterate in RPO to visit outer loops before inner loops.
michael@0:     for (ReversePostorderIterator i(graph.rpoBegin()); i != graph.rpoEnd(); i++) {
michael@0:         MBasicBlock *header = *i;
michael@0: 
michael@0:         // Skip non-headers and self-loops.
michael@0:         if (!header->isLoopHeader() || header->numPredecessors() < 2)
michael@0:             continue;
michael@0: 
michael@0:         // Attempt to optimize loop.
michael@0:         Loop loop(mir, header);
michael@0: 
michael@0:         Loop::LoopReturn lr = loop.init();
michael@0:         if (lr == Loop::LoopReturn_Error)
michael@0:             return false;
michael@0:         if (lr == Loop::LoopReturn_Skip) {
michael@0:             graph.unmarkBlocks();
michael@0:             continue;
michael@0:         }
michael@0: 
michael@0:         if (!loop.optimize())
michael@0:             return false;
michael@0: 
michael@0:         graph.unmarkBlocks();
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: Loop::Loop(MIRGenerator *mir, MBasicBlock *header)
michael@0:   : mir(mir),
michael@0:     header_(header),
michael@0:     containsPossibleCall_(false),
michael@0:     worklist_(mir->alloc())
michael@0: {
michael@0:     preLoop_ = header_->getPredecessor(0);
michael@0: }
michael@0: 
michael@0: Loop::LoopReturn
michael@0: Loop::init()
michael@0: {
michael@0:     IonSpew(IonSpew_LICM, "Loop identified, headed by block %d", header_->id());
michael@0:     IonSpew(IonSpew_LICM, "footer is block %d", header_->backedge()->id());
michael@0: 
michael@0:     // The first predecessor of the loop header must dominate the header.
michael@0:     JS_ASSERT(header_->id() > header_->getPredecessor(0)->id());
michael@0: 
michael@0:     // Loops from backedge to header and marks all visited blocks
michael@0:     // as part of the loop. At the same time add all hoistable instructions
michael@0:     // (in RPO order) to the instruction worklist.
michael@0:     Vector<MBasicBlock *, 1, IonAllocPolicy> inlooplist(alloc());
michael@0:     if (!inlooplist.append(header_->backedge()))
michael@0:         return LoopReturn_Error;
michael@0:     header_->backedge()->mark();
michael@0: 
michael@0:     while (!inlooplist.empty()) {
michael@0:         MBasicBlock *block = inlooplist.back();
michael@0: 
michael@0:         // Hoisting requires more finesse if the loop contains a block that
michael@0:         // self-dominates: there exists control flow that may enter the loop
michael@0:         // without passing through the loop preheader.
michael@0:         //
michael@0:         // Rather than perform a complicated analysis of the dominance graph,
michael@0:         // just return a soft error to ignore this loop.
michael@0:         if (block->immediateDominator() == block) {
michael@0:             while (!worklist_.empty())
michael@0:                 popFromWorklist();
michael@0:             return LoopReturn_Skip;
michael@0:         }
michael@0: 
michael@0:         // Add not yet visited predecessors to the inlooplist.
michael@0:         if (block != header_) {
michael@0:             for (size_t i = 0; i < block->numPredecessors(); i++) {
michael@0:                 MBasicBlock *pred = block->getPredecessor(i);
michael@0:                 if (pred->isMarked())
michael@0:                     continue;
michael@0: 
michael@0:                 if (!inlooplist.append(pred))
michael@0:                     return LoopReturn_Error;
michael@0:                 pred->mark();
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         // If any block was added, process them first.
michael@0:         if (block != inlooplist.back())
michael@0:             continue;
michael@0: 
michael@0:         // Add all instructions in this block (but the control instruction) to the worklist
michael@0:         for (MInstructionIterator i = block->begin(); i != block->end(); i++) {
michael@0:             MInstruction *ins = *i;
michael@0: 
michael@0:             // Remember whether this loop contains anything which clobbers most
michael@0:             // or all floating-point registers. This is just a rough heuristic.
michael@0:             if (ins->possiblyCalls())
michael@0:                 containsPossibleCall_ = true;
michael@0: 
michael@0:             if (isHoistable(ins)) {
michael@0:                 if (!insertInWorklist(ins))
michael@0:                     return LoopReturn_Error;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         // All successors of this block are visited.
michael@0:         inlooplist.popBack();
michael@0:     }
michael@0: 
michael@0:     return LoopReturn_Success;
michael@0: }
michael@0: 
michael@0: bool
michael@0: Loop::optimize()
michael@0: {
michael@0:     InstructionQueue invariantInstructions(alloc());
michael@0: 
michael@0:     IonSpew(IonSpew_LICM, "These instructions are in the loop: ");
michael@0: 
michael@0:     while (!worklist_.empty()) {
michael@0:         if (mir->shouldCancel("LICM (worklist)"))
michael@0:             return false;
michael@0: 
michael@0:         MInstruction *ins = popFromWorklist();
michael@0: 
michael@0:         IonSpewHeader(IonSpew_LICM);
michael@0: 
michael@0:         if (IonSpewEnabled(IonSpew_LICM)) {
michael@0:             ins->printName(IonSpewFile);
michael@0:             fprintf(IonSpewFile, " <- ");
michael@0:             ins->printOpcode(IonSpewFile);
michael@0:             fprintf(IonSpewFile, ":  ");
michael@0:         }
michael@0: 
michael@0:         if (isLoopInvariant(ins)) {
michael@0:             // Flag this instruction as loop invariant.
michael@0:             ins->setLoopInvariant();
michael@0:             if (!invariantInstructions.append(ins))
michael@0:                 return false;
michael@0: 
michael@0:             if (IonSpewEnabled(IonSpew_LICM))
michael@0:                 fprintf(IonSpewFile, " Loop Invariant!\n");
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (!hoistInstructions(invariantInstructions))
michael@0:         return false;
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool
michael@0: Loop::requiresHoistedUse(const MDefinition *ins) const
michael@0: {
michael@0:     if (ins->isConstantElements() || ins->isBox())
michael@0:         return true;
michael@0: 
michael@0:     // Integer constants can often be folded as immediates and aren't worth
michael@0:     // hoisting on their own, in general. Floating-point constants typically
michael@0:     // are worth hoisting, unless they'll end up being spilled (eg. due to a
michael@0:     // call).
michael@0:     if (ins->isConstant() && (IsFloatingPointType(ins->type()) || containsPossibleCall_))
michael@0:         return true;
michael@0: 
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: bool
michael@0: Loop::hoistInstructions(InstructionQueue &toHoist)
michael@0: {
michael@0:     // Iterate in post-order (uses before definitions)
michael@0:     for (int32_t i = toHoist.length() - 1; i >= 0; i--) {
michael@0:         MInstruction *ins = toHoist[i];
michael@0: 
michael@0:         // Don't hoist a cheap constant if it doesn't enable us to hoist one of
michael@0:         // its uses. We want those instructions as close as possible to their
michael@0:         // use, to facilitate folding and minimize register pressure.
michael@0:         if (requiresHoistedUse(ins)) {
michael@0:             bool loopInvariantUse = false;
michael@0:             for (MUseDefIterator use(ins); use; use++) {
michael@0:                 if (use.def()->isLoopInvariant()) {
michael@0:                     loopInvariantUse = true;
michael@0:                     break;
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             if (!loopInvariantUse)
michael@0:                 ins->setNotLoopInvariant();
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Move all instructions to the preLoop_ block just before the control instruction.
michael@0:     for (size_t i = 0; i < toHoist.length(); i++) {
michael@0:         MInstruction *ins = toHoist[i];
michael@0: 
michael@0:         // Loads may have an implicit dependency on either stores (effectful instructions) or
michael@0:         // control instructions so we should never move these.
michael@0:         JS_ASSERT(!ins->isControlInstruction());
michael@0:         JS_ASSERT(!ins->isEffectful());
michael@0:         JS_ASSERT(ins->isMovable());
michael@0: 
michael@0:         if (!ins->isLoopInvariant())
michael@0:             continue;
michael@0: 
michael@0:         if (checkHotness(ins->block())) {
michael@0:             ins->block()->moveBefore(preLoop_->lastIns(), ins);
michael@0:             ins->setNotLoopInvariant();
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool
michael@0: Loop::isInLoop(MDefinition *ins)
michael@0: {
michael@0:     return ins->block()->isMarked();
michael@0: }
michael@0: 
michael@0: bool
michael@0: Loop::isBeforeLoop(MDefinition *ins)
michael@0: {
michael@0:     return ins->block()->id() < header_->id();
michael@0: }
michael@0: 
michael@0: bool
michael@0: Loop::isLoopInvariant(MInstruction *ins)
michael@0: {
michael@0:     if (!isHoistable(ins)) {
michael@0:         if (IonSpewEnabled(IonSpew_LICM))
michael@0:             fprintf(IonSpewFile, "not hoistable\n");
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     // Don't hoist if this instruction depends on a store inside or after the loop.
michael@0:     // Note: "after the loop" can sound strange, but Alias Analysis doesn't look
michael@0:     // at the control flow. Therefore it doesn't match the definition here, that a block
michael@0:     // is in the loop when there is a (directed) path from the block to the loop header.
michael@0:     if (ins->dependency() && !isBeforeLoop(ins->dependency())) {
michael@0:         if (IonSpewEnabled(IonSpew_LICM)) {
michael@0:             fprintf(IonSpewFile, "depends on store inside or after loop: ");
michael@0:             ins->dependency()->printName(IonSpewFile);
michael@0:             fprintf(IonSpewFile, "\n");
michael@0:         }
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     // An instruction is only loop invariant if it and all of its operands can
michael@0:     // be safely hoisted into the loop preheader.
michael@0:     for (size_t i = 0, e = ins->numOperands(); i < e; i++) {
michael@0:         if (isInLoop(ins->getOperand(i)) &&
michael@0:             !ins->getOperand(i)->isLoopInvariant()) {
michael@0: 
michael@0:             if (IonSpewEnabled(IonSpew_LICM)) {
michael@0:                 ins->getOperand(i)->printName(IonSpewFile);
michael@0:                 fprintf(IonSpewFile, " is in the loop.\n");
michael@0:             }
michael@0: 
michael@0:             return false;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool
michael@0: Loop::checkHotness(MBasicBlock *block)
michael@0: {
michael@0:     // TODO: determine if instructions within this block are worth hoisting.
michael@0:     // They might not be if the block is cold enough within the loop.
michael@0:     // BUG 669517
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool
michael@0: Loop::insertInWorklist(MInstruction *ins)
michael@0: {
michael@0:     if (!worklist_.insert(worklist_.begin(), ins))
michael@0:         return false;
michael@0:     ins->setInWorklist();
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: MInstruction*
michael@0: Loop::popFromWorklist()
michael@0: {
michael@0:     MInstruction* toReturn = worklist_.popCopy();
michael@0:     toReturn->setNotInWorklist();
michael@0:     return toReturn;
michael@0: }