diff options
Diffstat (limited to 'js/src/jit/Sink.cpp')
| -rw-r--r-- | js/src/jit/Sink.cpp | 232 |
1 files changed, 232 insertions, 0 deletions
diff --git a/js/src/jit/Sink.cpp b/js/src/jit/Sink.cpp new file mode 100644 index 000000000..b2c36fae5 --- /dev/null +++ b/js/src/jit/Sink.cpp @@ -0,0 +1,232 @@ +/* -*- 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/Sink.h" + +#include "mozilla/Vector.h" + +#include "jit/IonAnalysis.h" +#include "jit/JitSpewer.h" +#include "jit/MIR.h" +#include "jit/MIRGenerator.h" +#include "jit/MIRGraph.h" + +namespace js { +namespace jit { + +// Given the last found common dominator and a new definition to dominate, the +// CommonDominator function returns the basic block which dominate the last +// common dominator and the definition. If no such block exists, then this +// functions return null. +static MBasicBlock* +CommonDominator(MBasicBlock* commonDominator, MBasicBlock* defBlock) +{ + // This is the first instruction visited, record its basic block as being + // the only interesting one. + if (!commonDominator) + return defBlock; + + // Iterate on immediate dominators of the known common dominator to find a + // block which dominates all previous uses as well as this instruction. + while (!commonDominator->dominates(defBlock)) { + MBasicBlock* nextBlock = commonDominator->immediateDominator(); + // All uses are dominated, so, this cannot happen unless the graph + // coherency is not respected. + MOZ_ASSERT(commonDominator != nextBlock); + commonDominator = nextBlock; + } + + return commonDominator; +} + +bool +Sink(MIRGenerator* mir, MIRGraph& graph) +{ + TempAllocator& alloc = graph.alloc(); + bool sinkEnabled = mir->optimizationInfo().sinkEnabled(); + + for (PostorderIterator block = graph.poBegin(); block != graph.poEnd(); block++) { + if (mir->shouldCancel("Sink")) + return false; + + for (MInstructionReverseIterator iter = block->rbegin(); iter != block->rend(); ) { + MInstruction* ins = *iter++; + + // Only instructions which can be recovered on bailout can be moved + // into the bailout paths. + if (ins->isGuard() || ins->isGuardRangeBailouts() || + ins->isRecoveredOnBailout() || !ins->canRecoverOnBailout()) + { + continue; + } + + // Compute a common dominator for all uses of the current + // instruction. + bool hasLiveUses = false; + bool hasUses = false; + MBasicBlock* usesDominator = nullptr; + for (MUseIterator i(ins->usesBegin()), e(ins->usesEnd()); i != e; i++) { + hasUses = true; + MNode* consumerNode = (*i)->consumer(); + if (consumerNode->isResumePoint()) + continue; + + MDefinition* consumer = consumerNode->toDefinition(); + if (consumer->isRecoveredOnBailout()) + continue; + + hasLiveUses = true; + + // If the instruction is a Phi, then we should dominate the + // predecessor from which the value is coming from. + MBasicBlock* consumerBlock = consumer->block(); + if (consumer->isPhi()) + consumerBlock = consumerBlock->getPredecessor(consumer->indexOf(*i)); + + usesDominator = CommonDominator(usesDominator, consumerBlock); + if (usesDominator == *block) + break; + } + + // Leave this instruction for DCE. + if (!hasUses) + continue; + + // We have no uses, so sink this instruction in all the bailout + // paths. + if (!hasLiveUses) { + MOZ_ASSERT(!usesDominator); + ins->setRecoveredOnBailout(); + JitSpewDef(JitSpew_Sink, " No live uses, recover the instruction on bailout\n", ins); + continue; + } + + // This guard is temporarly moved here as the above code deals with + // Dead Code elimination, which got moved into this Sink phase, as + // the Dead Code elimination used to move instructions with no-live + // uses to the bailout path. + if (!sinkEnabled) + continue; + + // To move an effectful instruction, we would have to verify that the + // side-effect is not observed. In the mean time, we just inhibit + // this optimization on effectful instructions. + if (ins->isEffectful()) + continue; + + // If all the uses are under a loop, we might not want to work + // against LICM by moving everything back into the loop, but if the + // loop is it-self inside an if, then we still want to move the + // computation under this if statement. + while (block->loopDepth() < usesDominator->loopDepth()) { + MOZ_ASSERT(usesDominator != usesDominator->immediateDominator()); + usesDominator = usesDominator->immediateDominator(); + } + + // Only move instructions if there is a branch between the dominator + // of the uses and the original instruction. This prevent moving the + // computation of the arguments into an inline function if there is + // no major win. + MBasicBlock* lastJoin = usesDominator; + while (*block != lastJoin && lastJoin->numPredecessors() == 1) { + MOZ_ASSERT(lastJoin != lastJoin->immediateDominator()); + MBasicBlock* next = lastJoin->immediateDominator(); + if (next->numSuccessors() > 1) + break; + lastJoin = next; + } + if (*block == lastJoin) + continue; + + // Skip to the next instruction if we cannot find a common dominator + // for all the uses of this instruction, or if the common dominator + // correspond to the block of the current instruction. + if (!usesDominator || usesDominator == *block) + continue; + + // Only instruction which can be recovered on bailout and which are + // sinkable can be moved into blocks which are below while filling + // the resume points with a clone which is recovered on bailout. + + // If the instruction has live uses and if it is clonable, then we + // can clone the instruction for all non-dominated uses and move the + // instruction into the block which is dominating all live uses. + if (!ins->canClone()) + continue; + + // If the block is a split-edge block, which is created for folding + // test conditions, then the block has no resume point and has + // multiple predecessors. In such case, we cannot safely move + // bailing instruction to these blocks as we have no way to bailout. + if (!usesDominator->entryResumePoint() && usesDominator->numPredecessors() != 1) + continue; + + JitSpewDef(JitSpew_Sink, " Can Clone & Recover, sink instruction\n", ins); + JitSpew(JitSpew_Sink, " into Block %u", usesDominator->id()); + + // Copy the arguments and clone the instruction. + MDefinitionVector operands(alloc); + for (size_t i = 0, end = ins->numOperands(); i < end; i++) { + if (!operands.append(ins->getOperand(i))) + return false; + } + + MInstruction* clone = ins->clone(alloc, operands); + ins->block()->insertBefore(ins, clone); + clone->setRecoveredOnBailout(); + + // We should not update the producer of the entry resume point, as + // it cannot refer to any instruction within the basic block excepts + // for Phi nodes. + MResumePoint* entry = usesDominator->entryResumePoint(); + + // Replace the instruction by its clone in all the resume points / + // recovered-on-bailout instructions which are not in blocks which + // are dominated by the usesDominator block. + for (MUseIterator i(ins->usesBegin()), e(ins->usesEnd()); i != e; ) { + MUse* use = *i++; + MNode* consumer = use->consumer(); + + // If the consumer is a Phi, then we look for the index of the + // use to find the corresponding predecessor block, which is + // then used as the consumer block. + MBasicBlock* consumerBlock = consumer->block(); + if (consumer->isDefinition() && consumer->toDefinition()->isPhi()) { + consumerBlock = consumerBlock->getPredecessor( + consumer->toDefinition()->toPhi()->indexOf(use)); + } + + // Keep the current instruction for all dominated uses, except + // for the entry resume point of the block in which the + // instruction would be moved into. + if (usesDominator->dominates(consumerBlock) && + (!consumer->isResumePoint() || consumer->toResumePoint() != entry)) + { + continue; + } + + use->replaceProducer(clone); + } + + // As we move this instruction in a different block, we should + // verify that we do not carry over a resume point which would refer + // to an outdated state of the control flow. + if (ins->resumePoint()) + ins->clearResumePoint(); + + // Now, that all uses which are not dominated by usesDominator are + // using the cloned instruction, we can safely move the instruction + // into the usesDominator block. + MInstruction* at = usesDominator->safeInsertTop(nullptr, MBasicBlock::IgnoreRecover); + block->moveBefore(at, ins); + } + } + + return true; +} + +} // namespace jit +} // namespace js |