Bug 1867190 - Add prefs for PHC probablities r=glandium
[gecko.git] / js / src / jit / Sink.cpp
blob36977fb93df79426385db5cc286c37447f792d9f
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 * vim: set ts=8 sts=2 et sw=2 tw=80:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 #include "jit/Sink.h"
9 #include "jit/IonOptimizationLevels.h"
10 #include "jit/JitSpewer.h"
11 #include "jit/MIR.h"
12 #include "jit/MIRGenerator.h"
13 #include "jit/MIRGraph.h"
15 namespace js {
16 namespace jit {
18 // Given the last found common dominator and a new definition to dominate, the
19 // CommonDominator function returns the basic block which dominate the last
20 // common dominator and the definition. If no such block exists, then this
21 // functions return null.
22 static MBasicBlock* CommonDominator(MBasicBlock* commonDominator,
23 MBasicBlock* defBlock) {
24 // This is the first instruction visited, record its basic block as being
25 // the only interesting one.
26 if (!commonDominator) {
27 return defBlock;
30 // Iterate on immediate dominators of the known common dominator to find a
31 // block which dominates all previous uses as well as this instruction.
32 while (!commonDominator->dominates(defBlock)) {
33 MBasicBlock* nextBlock = commonDominator->immediateDominator();
34 // All uses are dominated, so, this cannot happen unless the graph
35 // coherency is not respected.
36 MOZ_ASSERT(commonDominator != nextBlock);
37 commonDominator = nextBlock;
40 return commonDominator;
43 bool Sink(MIRGenerator* mir, MIRGraph& graph) {
44 JitSpew(JitSpew_Sink, "Begin");
45 TempAllocator& alloc = graph.alloc();
46 bool sinkEnabled = mir->optimizationInfo().sinkEnabled();
48 for (PostorderIterator block = graph.poBegin(); block != graph.poEnd();
49 block++) {
50 if (mir->shouldCancel("Sink")) {
51 return false;
54 for (MInstructionReverseIterator iter = block->rbegin();
55 iter != block->rend();) {
56 MInstruction* ins = *iter++;
58 // Only instructions which can be recovered on bailout can be moved
59 // into the bailout paths.
60 if (ins->isGuard() || ins->isGuardRangeBailouts() ||
61 ins->isRecoveredOnBailout() || !ins->canRecoverOnBailout()) {
62 continue;
65 // Compute a common dominator for all uses of the current
66 // instruction.
67 bool hasLiveUses = false;
68 bool hasUses = false;
69 MBasicBlock* usesDominator = nullptr;
70 for (MUseIterator i(ins->usesBegin()), e(ins->usesEnd()); i != e; i++) {
71 hasUses = true;
72 MNode* consumerNode = (*i)->consumer();
73 if (consumerNode->isResumePoint()) {
74 if (!consumerNode->toResumePoint()->isRecoverableOperand(*i)) {
75 hasLiveUses = true;
77 continue;
80 MDefinition* consumer = consumerNode->toDefinition();
81 if (consumer->isRecoveredOnBailout()) {
82 continue;
85 hasLiveUses = true;
87 // If the instruction is a Phi, then we should dominate the
88 // predecessor from which the value is coming from.
89 MBasicBlock* consumerBlock = consumer->block();
90 if (consumer->isPhi()) {
91 consumerBlock = consumerBlock->getPredecessor(consumer->indexOf(*i));
94 usesDominator = CommonDominator(usesDominator, consumerBlock);
95 if (usesDominator == *block) {
96 break;
100 // Leave this instruction for DCE.
101 if (!hasUses) {
102 continue;
105 // We have no uses, so sink this instruction in all the bailout
106 // paths.
107 if (!hasLiveUses) {
108 MOZ_ASSERT(!usesDominator);
109 ins->setRecoveredOnBailout();
110 JitSpewDef(JitSpew_Sink,
111 " No live uses, recover the instruction on bailout\n", ins);
112 continue;
115 // This guard is temporarly moved here as the above code deals with
116 // Dead Code elimination, which got moved into this Sink phase, as
117 // the Dead Code elimination used to move instructions with no-live
118 // uses to the bailout path.
119 if (!sinkEnabled) {
120 continue;
123 // To move an effectful instruction, we would have to verify that the
124 // side-effect is not observed. In the mean time, we just inhibit
125 // this optimization on effectful instructions.
126 if (ins->isEffectful()) {
127 continue;
130 // If all the uses are under a loop, we might not want to work
131 // against LICM by moving everything back into the loop, but if the
132 // loop is it-self inside an if, then we still want to move the
133 // computation under this if statement.
134 while (block->loopDepth() < usesDominator->loopDepth()) {
135 MOZ_ASSERT(usesDominator != usesDominator->immediateDominator());
136 usesDominator = usesDominator->immediateDominator();
139 // Only move instructions if there is a branch between the dominator
140 // of the uses and the original instruction. This prevent moving the
141 // computation of the arguments into an inline function if there is
142 // no major win.
143 MBasicBlock* lastJoin = usesDominator;
144 while (*block != lastJoin && lastJoin->numPredecessors() == 1) {
145 MOZ_ASSERT(lastJoin != lastJoin->immediateDominator());
146 MBasicBlock* next = lastJoin->immediateDominator();
147 if (next->numSuccessors() > 1) {
148 break;
150 lastJoin = next;
152 if (*block == lastJoin) {
153 continue;
156 // Skip to the next instruction if we cannot find a common dominator
157 // for all the uses of this instruction, or if the common dominator
158 // correspond to the block of the current instruction.
159 if (!usesDominator || usesDominator == *block) {
160 continue;
163 // Only instruction which can be recovered on bailout and which are
164 // sinkable can be moved into blocks which are below while filling
165 // the resume points with a clone which is recovered on bailout.
167 // If the instruction has live uses and if it is clonable, then we
168 // can clone the instruction for all non-dominated uses and move the
169 // instruction into the block which is dominating all live uses.
170 if (!ins->canClone()) {
171 continue;
174 // If the block is a split-edge block, which is created for folding
175 // test conditions, then the block has no resume point and has
176 // multiple predecessors. In such case, we cannot safely move
177 // bailing instruction to these blocks as we have no way to bailout.
178 if (!usesDominator->entryResumePoint() &&
179 usesDominator->numPredecessors() != 1) {
180 continue;
183 JitSpewDef(JitSpew_Sink, " Can Clone & Recover, sink instruction\n",
184 ins);
185 JitSpew(JitSpew_Sink, " into Block %u", usesDominator->id());
187 // Copy the arguments and clone the instruction.
188 MDefinitionVector operands(alloc);
189 for (size_t i = 0, end = ins->numOperands(); i < end; i++) {
190 if (!operands.append(ins->getOperand(i))) {
191 return false;
195 MInstruction* clone = ins->clone(alloc, operands);
196 if (!clone) {
197 return false;
199 ins->block()->insertBefore(ins, clone);
200 clone->setRecoveredOnBailout();
202 // We should not update the producer of the entry resume point, as
203 // it cannot refer to any instruction within the basic block excepts
204 // for Phi nodes.
205 MResumePoint* entry = usesDominator->entryResumePoint();
207 // Replace the instruction by its clone in all the resume points /
208 // recovered-on-bailout instructions which are not in blocks which
209 // are dominated by the usesDominator block.
210 for (MUseIterator i(ins->usesBegin()), e(ins->usesEnd()); i != e;) {
211 MUse* use = *i++;
212 MNode* consumer = use->consumer();
214 // If the consumer is a Phi, then we look for the index of the
215 // use to find the corresponding predecessor block, which is
216 // then used as the consumer block.
217 MBasicBlock* consumerBlock = consumer->block();
218 if (consumer->isDefinition() && consumer->toDefinition()->isPhi()) {
219 consumerBlock = consumerBlock->getPredecessor(
220 consumer->toDefinition()->toPhi()->indexOf(use));
223 // Keep the current instruction for all dominated uses, except
224 // for the entry resume point of the block in which the
225 // instruction would be moved into.
226 if (usesDominator->dominates(consumerBlock) &&
227 (!consumer->isResumePoint() ||
228 consumer->toResumePoint() != entry)) {
229 continue;
232 use->replaceProducer(clone);
235 // As we move this instruction in a different block, we should
236 // verify that we do not carry over a resume point which would refer
237 // to an outdated state of the control flow.
238 if (ins->resumePoint()) {
239 ins->clearResumePoint();
242 // Now, that all uses which are not dominated by usesDominator are
243 // using the cloned instruction, we can safely move the instruction
244 // into the usesDominator block.
245 MInstruction* at =
246 usesDominator->safeInsertTop(nullptr, MBasicBlock::IgnoreRecover);
247 block->moveBefore(at, ins);
251 return true;
254 } // namespace jit
255 } // namespace js