summaryrefslogtreecommitdiffstats
path: root/js/src/jit/LoopUnroller.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'js/src/jit/LoopUnroller.cpp')
-rw-r--r--js/src/jit/LoopUnroller.cpp408
1 files changed, 408 insertions, 0 deletions
diff --git a/js/src/jit/LoopUnroller.cpp b/js/src/jit/LoopUnroller.cpp
new file mode 100644
index 000000000..5481d6978
--- /dev/null
+++ b/js/src/jit/LoopUnroller.cpp
@@ -0,0 +1,408 @@
+/* -*- 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/LoopUnroller.h"
+
+#include "jit/MIRGraph.h"
+
+using namespace js;
+using namespace js::jit;
+
+using mozilla::ArrayLength;
+
+namespace {
+
+struct LoopUnroller
+{
+ typedef HashMap<MDefinition*, MDefinition*,
+ PointerHasher<MDefinition*, 2>, SystemAllocPolicy> DefinitionMap;
+
+ explicit LoopUnroller(MIRGraph& graph)
+ : graph(graph), alloc(graph.alloc()),
+ header(nullptr), backedge(nullptr),
+ unrolledHeader(nullptr), unrolledBackedge(nullptr),
+ oldPreheader(nullptr), newPreheader(nullptr)
+ {}
+
+ MIRGraph& graph;
+ TempAllocator& alloc;
+
+ // Header and body of the original loop.
+ MBasicBlock* header;
+ MBasicBlock* backedge;
+
+ // Header and body of the unrolled loop.
+ MBasicBlock* unrolledHeader;
+ MBasicBlock* unrolledBackedge;
+
+ // Old and new preheaders. The old preheader starts out associated with the
+ // original loop, but becomes the preheader of the new loop. The new
+ // preheader will be given to the original loop.
+ MBasicBlock* oldPreheader;
+ MBasicBlock* newPreheader;
+
+ // Map terms in the original loop to terms in the current unrolled iteration.
+ DefinitionMap unrolledDefinitions;
+
+ MDefinition* getReplacementDefinition(MDefinition* def);
+ MResumePoint* makeReplacementResumePoint(MBasicBlock* block, MResumePoint* rp);
+ bool makeReplacementInstruction(MInstruction* ins);
+
+ void go(LoopIterationBound* bound);
+};
+
+} // namespace
+
+MDefinition*
+LoopUnroller::getReplacementDefinition(MDefinition* def)
+{
+ if (def->block()->id() < header->id()) {
+ // The definition is loop invariant.
+ return def;
+ }
+
+ DefinitionMap::Ptr p = unrolledDefinitions.lookup(def);
+ if (!p) {
+ // After phi analysis (TypeAnalyzer::replaceRedundantPhi) the resume
+ // point at the start of a block can contain definitions from within
+ // the block itself.
+ MOZ_ASSERT(def->isConstant());
+
+ MConstant* constant = MConstant::Copy(alloc, def->toConstant());
+ oldPreheader->insertBefore(*oldPreheader->begin(), constant);
+ return constant;
+ }
+
+ return p->value();
+}
+
+bool
+LoopUnroller::makeReplacementInstruction(MInstruction* ins)
+{
+ MDefinitionVector inputs(alloc);
+ for (size_t i = 0; i < ins->numOperands(); i++) {
+ MDefinition* old = ins->getOperand(i);
+ MDefinition* replacement = getReplacementDefinition(old);
+ if (!inputs.append(replacement))
+ return false;
+ }
+
+ MInstruction* clone = ins->clone(alloc, inputs);
+
+ unrolledBackedge->add(clone);
+
+ if (!unrolledDefinitions.putNew(ins, clone))
+ return false;
+
+ if (MResumePoint* old = ins->resumePoint()) {
+ MResumePoint* rp = makeReplacementResumePoint(unrolledBackedge, old);
+ clone->setResumePoint(rp);
+ }
+
+ return true;
+}
+
+MResumePoint*
+LoopUnroller::makeReplacementResumePoint(MBasicBlock* block, MResumePoint* rp)
+{
+ MDefinitionVector inputs(alloc);
+ for (size_t i = 0; i < rp->numOperands(); i++) {
+ MDefinition* old = rp->getOperand(i);
+ MDefinition* replacement = old->isUnused() ? old : getReplacementDefinition(old);
+ if (!inputs.append(replacement))
+ return nullptr;
+ }
+
+ MResumePoint* clone = MResumePoint::New(alloc, block, rp, inputs);
+ if (!clone)
+ return nullptr;
+
+ return clone;
+}
+
+void
+LoopUnroller::go(LoopIterationBound* bound)
+{
+ // For now we always unroll loops the same number of times.
+ static const size_t UnrollCount = 10;
+
+ JitSpew(JitSpew_Unrolling, "Attempting to unroll loop");
+
+ header = bound->header;
+
+ // UCE might have determined this isn't actually a loop.
+ if (!header->isLoopHeader())
+ return;
+
+ backedge = header->backedge();
+ oldPreheader = header->loopPredecessor();
+
+ MOZ_ASSERT(oldPreheader->numSuccessors() == 1);
+
+ // Only unroll loops with two blocks: an initial one ending with the
+ // bound's test, and the body ending with the backedge.
+ MTest* test = bound->test;
+ if (header->lastIns() != test)
+ return;
+ if (test->ifTrue() == backedge) {
+ if (test->ifFalse()->id() <= backedge->id())
+ return;
+ } else if (test->ifFalse() == backedge) {
+ if (test->ifTrue()->id() <= backedge->id())
+ return;
+ } else {
+ return;
+ }
+ if (backedge->numPredecessors() != 1 || backedge->numSuccessors() != 1)
+ return;
+ MOZ_ASSERT(backedge->phisEmpty());
+
+ MBasicBlock* bodyBlocks[] = { header, backedge };
+
+ // All instructions in the header and body must be clonable.
+ for (size_t i = 0; i < ArrayLength(bodyBlocks); i++) {
+ MBasicBlock* block = bodyBlocks[i];
+ for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++) {
+ MInstruction* ins = *iter;
+ if (ins->canClone())
+ continue;
+ if (ins->isTest() || ins->isGoto() || ins->isInterruptCheck())
+ continue;
+#ifdef JS_JITSPEW
+ JitSpew(JitSpew_Unrolling, "Aborting: can't clone instruction %s", ins->opName());
+#endif
+ return;
+ }
+ }
+
+ // Compute the linear inequality we will use for exiting the unrolled loop:
+ //
+ // iterationBound - iterationCount - UnrollCount >= 0
+ //
+ LinearSum remainingIterationsInequality(bound->boundSum);
+ if (!remainingIterationsInequality.add(bound->currentSum, -1))
+ return;
+ if (!remainingIterationsInequality.add(-int32_t(UnrollCount)))
+ return;
+
+ // Terms in the inequality need to be either loop invariant or phis from
+ // the original header.
+ for (size_t i = 0; i < remainingIterationsInequality.numTerms(); i++) {
+ MDefinition* def = remainingIterationsInequality.term(i).term;
+ if (def->isDiscarded())
+ return;
+ if (def->block()->id() < header->id())
+ continue;
+ if (def->block() == header && def->isPhi())
+ continue;
+ return;
+ }
+
+ // OK, we've checked everything, now unroll the loop.
+
+ JitSpew(JitSpew_Unrolling, "Unrolling loop");
+
+ // The old preheader will go before the unrolled loop, and the old loop
+ // will need a new empty preheader.
+ const CompileInfo& info = oldPreheader->info();
+ if (header->trackedPc()) {
+ unrolledHeader =
+ MBasicBlock::New(graph, nullptr, info,
+ oldPreheader, header->trackedSite(), MBasicBlock::LOOP_HEADER);
+ unrolledBackedge =
+ MBasicBlock::New(graph, nullptr, info,
+ unrolledHeader, backedge->trackedSite(), MBasicBlock::NORMAL);
+ newPreheader =
+ MBasicBlock::New(graph, nullptr, info,
+ unrolledHeader, oldPreheader->trackedSite(), MBasicBlock::NORMAL);
+ } else {
+ unrolledHeader = MBasicBlock::New(graph, info, oldPreheader, MBasicBlock::LOOP_HEADER);
+ unrolledBackedge = MBasicBlock::New(graph, info, unrolledHeader, MBasicBlock::NORMAL);
+ newPreheader = MBasicBlock::New(graph, info, unrolledHeader, MBasicBlock::NORMAL);
+ }
+
+ unrolledHeader->discardAllResumePoints();
+ unrolledBackedge->discardAllResumePoints();
+ newPreheader->discardAllResumePoints();
+
+ // Insert new blocks at their RPO position, and update block ids.
+ graph.insertBlockAfter(oldPreheader, unrolledHeader);
+ graph.insertBlockAfter(unrolledHeader, unrolledBackedge);
+ graph.insertBlockAfter(unrolledBackedge, newPreheader);
+ graph.renumberBlocksAfter(oldPreheader);
+
+ // We don't tolerate allocation failure after this point.
+ // TODO: This is a bit drastic, is it possible to improve this?
+ AutoEnterOOMUnsafeRegion oomUnsafe;
+
+ if (!unrolledDefinitions.init())
+ oomUnsafe.crash("LoopUnroller::go");
+
+ // Add phis to the unrolled loop header which correspond to the phis in the
+ // original loop header.
+ MOZ_ASSERT(header->getPredecessor(0) == oldPreheader);
+ for (MPhiIterator iter(header->phisBegin()); iter != header->phisEnd(); iter++) {
+ MPhi* old = *iter;
+ MOZ_ASSERT(old->numOperands() == 2);
+ MPhi* phi = MPhi::New(alloc);
+ phi->setResultType(old->type());
+ phi->setResultTypeSet(old->resultTypeSet());
+ phi->setRange(old->range());
+
+ unrolledHeader->addPhi(phi);
+
+ if (!phi->reserveLength(2))
+ oomUnsafe.crash("LoopUnroller::go");
+
+ // Set the first input for the phi for now. We'll set the second after
+ // finishing the unroll.
+ phi->addInput(old->getOperand(0));
+
+ // The old phi will now take the value produced by the unrolled loop.
+ old->replaceOperand(0, phi);
+
+ if (!unrolledDefinitions.putNew(old, phi))
+ oomUnsafe.crash("LoopUnroller::go");
+ }
+
+ // The loop condition can bail out on e.g. integer overflow, so make a
+ // resume point based on the initial resume point of the original header.
+ MResumePoint* headerResumePoint = header->entryResumePoint();
+ if (headerResumePoint) {
+ MResumePoint* rp = makeReplacementResumePoint(unrolledHeader, headerResumePoint);
+ if (!rp)
+ oomUnsafe.crash("LoopUnroller::makeReplacementResumePoint");
+ unrolledHeader->setEntryResumePoint(rp);
+
+ // Perform an interrupt check at the start of the unrolled loop.
+ unrolledHeader->add(MInterruptCheck::New(alloc));
+ }
+
+ // Generate code for the test in the unrolled loop.
+ for (size_t i = 0; i < remainingIterationsInequality.numTerms(); i++) {
+ MDefinition* def = remainingIterationsInequality.term(i).term;
+ MDefinition* replacement = getReplacementDefinition(def);
+ remainingIterationsInequality.replaceTerm(i, replacement);
+ }
+ MCompare* compare = ConvertLinearInequality(alloc, unrolledHeader, remainingIterationsInequality);
+ MTest* unrolledTest = MTest::New(alloc, compare, unrolledBackedge, newPreheader);
+ unrolledHeader->end(unrolledTest);
+
+ // Make an entry resume point for the unrolled body. The unrolled header
+ // does not have side effects on stack values, even if the original loop
+ // header does, so use the same resume point as for the unrolled header.
+ if (headerResumePoint) {
+ MResumePoint* rp = makeReplacementResumePoint(unrolledBackedge, headerResumePoint);
+ if (!rp)
+ oomUnsafe.crash("LoopUnroller::makeReplacementResumePoint");
+ unrolledBackedge->setEntryResumePoint(rp);
+ }
+
+ // Make an entry resume point for the new preheader. There are no
+ // instructions which use this but some other stuff wants one to be here.
+ if (headerResumePoint) {
+ MResumePoint* rp = makeReplacementResumePoint(newPreheader, headerResumePoint);
+ if (!rp)
+ oomUnsafe.crash("LoopUnroller::makeReplacementResumePoint");
+ newPreheader->setEntryResumePoint(rp);
+ }
+
+ // Generate the unrolled code.
+ MOZ_ASSERT(UnrollCount > 1);
+ size_t unrollIndex = 0;
+ while (true) {
+ // Clone the contents of the original loop into the unrolled loop body.
+ for (size_t i = 0; i < ArrayLength(bodyBlocks); i++) {
+ MBasicBlock* block = bodyBlocks[i];
+ for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++) {
+ MInstruction* ins = *iter;
+ if (ins->canClone()) {
+ if (!makeReplacementInstruction(*iter))
+ oomUnsafe.crash("LoopUnroller::makeReplacementDefinition");
+ } else {
+ // Control instructions are handled separately.
+ MOZ_ASSERT(ins->isTest() || ins->isGoto() || ins->isInterruptCheck());
+ }
+ }
+ }
+
+ // Compute the value of each loop header phi after the execution of
+ // this unrolled iteration.
+ MDefinitionVector phiValues(alloc);
+ MOZ_ASSERT(header->getPredecessor(1) == backedge);
+ for (MPhiIterator iter(header->phisBegin()); iter != header->phisEnd(); iter++) {
+ MPhi* old = *iter;
+ MDefinition* oldInput = old->getOperand(1);
+ if (!phiValues.append(getReplacementDefinition(oldInput)))
+ oomUnsafe.crash("LoopUnroller::go");
+ }
+
+ unrolledDefinitions.clear();
+
+ if (unrollIndex == UnrollCount - 1) {
+ // We're at the end of the last unrolled iteration, set the
+ // backedge input for the unrolled loop phis.
+ size_t phiIndex = 0;
+ for (MPhiIterator iter(unrolledHeader->phisBegin()); iter != unrolledHeader->phisEnd(); iter++) {
+ MPhi* phi = *iter;
+ phi->addInput(phiValues[phiIndex++]);
+ }
+ MOZ_ASSERT(phiIndex == phiValues.length());
+ break;
+ }
+
+ // Update the map for the phis in the next iteration.
+ size_t phiIndex = 0;
+ for (MPhiIterator iter(header->phisBegin()); iter != header->phisEnd(); iter++) {
+ MPhi* old = *iter;
+ if (!unrolledDefinitions.putNew(old, phiValues[phiIndex++]))
+ oomUnsafe.crash("LoopUnroller::go");
+ }
+ MOZ_ASSERT(phiIndex == phiValues.length());
+
+ unrollIndex++;
+ }
+
+ MGoto* backedgeJump = MGoto::New(alloc, unrolledHeader);
+ unrolledBackedge->end(backedgeJump);
+
+ // Place the old preheader before the unrolled loop.
+ MOZ_ASSERT(oldPreheader->lastIns()->isGoto());
+ oldPreheader->discardLastIns();
+ oldPreheader->end(MGoto::New(alloc, unrolledHeader));
+
+ // Place the new preheader before the original loop.
+ newPreheader->end(MGoto::New(alloc, header));
+
+ // Cleanup the MIR graph.
+ if (!unrolledHeader->addPredecessorWithoutPhis(unrolledBackedge))
+ oomUnsafe.crash("LoopUnroller::go");
+ header->replacePredecessor(oldPreheader, newPreheader);
+ oldPreheader->setSuccessorWithPhis(unrolledHeader, 0);
+ newPreheader->setSuccessorWithPhis(header, 0);
+ unrolledBackedge->setSuccessorWithPhis(unrolledHeader, 1);
+}
+
+bool
+jit::UnrollLoops(MIRGraph& graph, const LoopIterationBoundVector& bounds)
+{
+ if (bounds.empty())
+ return true;
+
+ for (size_t i = 0; i < bounds.length(); i++) {
+ LoopUnroller unroller(graph);
+ unroller.go(bounds[i]);
+ }
+
+ // The MIR graph is valid, but now has several new blocks. Update or
+ // recompute previous analysis information for the remaining optimization
+ // passes.
+ ClearDominatorTree(graph);
+ if (!BuildDominatorTree(graph))
+ return false;
+
+ return true;
+}