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