From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- js/src/jit/Sink.cpp | 255 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 255 insertions(+) create mode 100644 js/src/jit/Sink.cpp (limited to 'js/src/jit/Sink.cpp') diff --git a/js/src/jit/Sink.cpp b/js/src/jit/Sink.cpp new file mode 100644 index 0000000000..36977fb93d --- /dev/null +++ b/js/src/jit/Sink.cpp @@ -0,0 +1,255 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- + * vim: set ts=8 sts=2 et sw=2 tw=80: + * 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 "jit/IonOptimizationLevels.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) { + JitSpew(JitSpew_Sink, "Begin"); + 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()) { + if (!consumerNode->toResumePoint()->isRecoverableOperand(*i)) { + hasLiveUses = true; + } + 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); + if (!clone) { + return false; + } + 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 -- cgit v1.2.3