| /* -*- 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 |
