1 files changed, 272 insertions, 0 deletions
diff --git a/js/src/jit/LICM.cpp b/js/src/jit/LICM.cpp
new file mode 100644
index 000000000..d661a1c7d
--- /dev/null
+++ b/js/src/jit/LICM.cpp
@@ -0,0 +1,272 @@
+/* -*- 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 "jit/IonAnalysis.h"
+#include "jit/JitSpewer.h"
+#include "jit/MIRGenerator.h"
+#include "jit/MIRGraph.h"
+
+using namespace js;
+using namespace js::jit;
+
+// Test whether any instruction in the loop possiblyCalls().
+static bool
+LoopContainsPossibleCall(MIRGraph& graph, MBasicBlock* header, MBasicBlock* backedge)
+{
+    for (auto i(graph.rpoBegin(header)); ; ++i) {
+        MOZ_ASSERT(i != graph.rpoEnd(), "Reached end of graph searching for blocks in loop");
+        MBasicBlock* block = *i;
+        if (!block->isMarked())
+            continue;
+
+        for (auto insIter(block->begin()), insEnd(block->end()); insIter != insEnd; ++insIter) {
+            MInstruction* ins = *insIter;
+            if (ins->possiblyCalls()) {
+#ifdef JS_JITSPEW
+                JitSpew(JitSpew_LICM, "    Possile call found at %s%u", ins->opName(), ins->id());
+#endif
+                return true;
+            }
+        }
+
+        if (block == backedge)
+            break;
+    }
+    return false;
+}
+
+// When a nested loop has no exits back into what would be its parent loop,
+// MarkLoopBlocks on the parent loop doesn't mark the blocks of the nested
+// loop, since they technically aren't part of the loop. However, AliasAnalysis
+// currently does consider such nested loops to be part of their parent
+// loops. Consequently, we can't use IsInLoop on dependency() values; we must
+// test whether a dependency() is *before* the loop, even if it is not
+// technically in the loop.
+static bool
+IsBeforeLoop(MDefinition* ins, MBasicBlock* header)
+{
+    return ins->block()->id() < header->id();
+}
+
+// Test whether the given instruction is inside the loop (and thus not
+// loop-invariant).
+static bool
+IsInLoop(MDefinition* ins)
+{
+    return ins->block()->isMarked();
+}
+
+// Test whether the given instruction is cheap and not worth hoisting unless
+// one of its users will be hoisted as well.
+static bool
+RequiresHoistedUse(const MDefinition* ins, bool hasCalls)
+{
+    if (ins->isConstantElements())
+        return true;
+
+    if (ins->isBox()) {
+        MOZ_ASSERT(!ins->toBox()->input()->isBox(),
+                "Box of a box could lead to unbounded recursion");
+        return true;
+    }
+
+    // Integer constants are usually cheap 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()) || hasCalls))
+        return true;
+
+    return false;
+}
+
+// Test whether the given instruction has any operands defined within the loop.
+static bool
+HasOperandInLoop(MInstruction* ins, bool hasCalls)
+{
+    // 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) {
+        MDefinition* op = ins->getOperand(i);
+
+        if (!IsInLoop(op))
+            continue;
+
+        if (RequiresHoistedUse(op, hasCalls)) {
+            // Recursively test for loop invariance. Note that the recursion is
+            // bounded because we require RequiresHoistedUse to be set at each
+            // level.
+            if (!HasOperandInLoop(op->toInstruction(), hasCalls))
+                continue;
+        }
+
+        return true;
+    }
+    return false;
+}
+
+// Test whether the given instruction is hoistable, ignoring memory
+// dependencies.
+static bool
+IsHoistableIgnoringDependency(MInstruction* ins, bool hasCalls)
+{
+    return ins->isMovable() && !ins->isEffectful() && !ins->neverHoist() &&
+           !HasOperandInLoop(ins, hasCalls);
+}
+
+// Test whether the given instruction has a memory dependency inside the loop.
+static bool
+HasDependencyInLoop(MInstruction* ins, MBasicBlock* header)
+{
+    // Don't hoist if this instruction depends on a store inside the loop.
+    if (MDefinition* dep = ins->dependency())
+        return !IsBeforeLoop(dep, header);
+    return false;
+}
+
+// Test whether the given instruction is hoistable.
+static bool
+IsHoistable(MInstruction* ins, MBasicBlock* header, bool hasCalls)
+{
+    return IsHoistableIgnoringDependency(ins, hasCalls) && !HasDependencyInLoop(ins, header);
+}
+
+// In preparation for hoisting an instruction, hoist any of its operands which
+// were too cheap to hoist on their own.
+static void
+MoveDeferredOperands(MInstruction* ins, MInstruction* hoistPoint, bool hasCalls)
+{
+    // If any of our operands were waiting for a user to be hoisted, make a note
+    // to hoist them.
+    for (size_t i = 0, e = ins->numOperands(); i != e; ++i) {
+        MDefinition* op = ins->getOperand(i);
+        if (!IsInLoop(op))
+            continue;
+        MOZ_ASSERT(RequiresHoistedUse(op, hasCalls),
+                   "Deferred loop-invariant operand is not cheap");
+        MInstruction* opIns = op->toInstruction();
+
+        // Recursively move the operands. Note that the recursion is bounded
+        // because we require RequiresHoistedUse to be set at each level.
+        MoveDeferredOperands(opIns, hoistPoint, hasCalls);
+
+#ifdef JS_JITSPEW
+        JitSpew(JitSpew_LICM, "    Hoisting %s%u (now that a user will be hoisted)",
+                opIns->opName(), opIns->id());
+#endif
+
+        opIns->block()->moveBefore(hoistPoint, opIns);
+    }
+}
+
+static void
+VisitLoopBlock(MBasicBlock* block, MBasicBlock* header, MInstruction* hoistPoint, bool hasCalls)
+{
+    for (auto insIter(block->begin()), insEnd(block->end()); insIter != insEnd; ) {
+        MInstruction* ins = *insIter++;
+
+        if (!IsHoistable(ins, header, hasCalls)) {
+#ifdef JS_JITSPEW
+            if (IsHoistableIgnoringDependency(ins, hasCalls)) {
+                JitSpew(JitSpew_LICM, "    %s%u isn't hoistable due to dependency on %s%u",
+                        ins->opName(), ins->id(),
+                        ins->dependency()->opName(), ins->dependency()->id());
+            }
+#endif
+            continue;
+        }
+
+        // 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 minimize register pressure.
+        if (RequiresHoistedUse(ins, hasCalls)) {
+#ifdef JS_JITSPEW
+            JitSpew(JitSpew_LICM, "    %s%u will be hoisted only if its users are",
+                    ins->opName(), ins->id());
+#endif
+            continue;
+        }
+
+        // Hoist operands which were too cheap to hoist on their own.
+        MoveDeferredOperands(ins, hoistPoint, hasCalls);
+
+#ifdef JS_JITSPEW
+        JitSpew(JitSpew_LICM, "    Hoisting %s%u", ins->opName(), ins->id());
+#endif
+
+        // Move the instruction to the hoistPoint.
+        block->moveBefore(hoistPoint, ins);
+    }
+}
+
+static void
+VisitLoop(MIRGraph& graph, MBasicBlock* header)
+{
+    MInstruction* hoistPoint = header->loopPredecessor()->lastIns();
+
+#ifdef JS_JITSPEW
+    JitSpew(JitSpew_LICM, "  Visiting loop with header block%u, hoisting to %s%u",
+            header->id(), hoistPoint->opName(), hoistPoint->id());
+#endif
+
+    MBasicBlock* backedge = header->backedge();
+
+    // 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 hasCalls = LoopContainsPossibleCall(graph, header, backedge);
+
+    for (auto i(graph.rpoBegin(header)); ; ++i) {
+        MOZ_ASSERT(i != graph.rpoEnd(), "Reached end of graph searching for blocks in loop");
+        MBasicBlock* block = *i;
+        if (!block->isMarked())
+            continue;
+
+        VisitLoopBlock(block, header, hoistPoint, hasCalls);
+
+        if (block == backedge)
+            break;
+    }
+}
+
+bool
+jit::LICM(MIRGenerator* mir, MIRGraph& graph)
+{
+    JitSpew(JitSpew_LICM, "Beginning LICM pass");
+
+    // Iterate in RPO to visit outer loops before inner loops. We'd hoist the
+    // same things either way, but outer first means we do a little less work.
+    for (auto i(graph.rpoBegin()), e(graph.rpoEnd()); i != e; ++i) {
+        MBasicBlock* header = *i;
+        if (!header->isLoopHeader())
+            continue;
+
+        bool canOsr;
+        size_t numBlocks = MarkLoopBlocks(graph, header, &canOsr);
+
+        if (numBlocks == 0) {
+            JitSpew(JitSpew_LICM, "  Loop with header block%u isn't actually a loop", header->id());
+            continue;
+        }
+
+        // Hoisting out of a loop that has an entry from the OSR block in
+        // addition to its normal entry is tricky. In theory we could clone
+        // the instruction and insert phis.
+        if (!canOsr)
+            VisitLoop(graph, header);
+        else
+            JitSpew(JitSpew_LICM, "  Skipping loop with header block%u due to OSR", header->id());
+
+        UnmarkLoopBlocks(graph, header);
+
+        if (mir->shouldCancel("LICM (main loop)"))
+            return false;
+    }
+
+    return true;
+}