diff options
Diffstat (limited to 'js/src/jit/LoopUnroller.cpp')
| -rw-r--r-- | js/src/jit/LoopUnroller.cpp | 408 |
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; +} |