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/. */
9 #include "jit/IonOptimizationLevels.h"
10 #include "jit/JitSpewer.h"
12 #include "jit/MIRGenerator.h"
13 #include "jit/MIRGraph.h"
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
) {
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();
50 if (mir
->shouldCancel("Sink")) {
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()) {
65 // Compute a common dominator for all uses of the current
67 bool hasLiveUses
= false;
69 MBasicBlock
* usesDominator
= nullptr;
70 for (MUseIterator
i(ins
->usesBegin()), e(ins
->usesEnd()); i
!= e
; i
++) {
72 MNode
* consumerNode
= (*i
)->consumer();
73 if (consumerNode
->isResumePoint()) {
74 if (!consumerNode
->toResumePoint()->isRecoverableOperand(*i
)) {
80 MDefinition
* consumer
= consumerNode
->toDefinition();
81 if (consumer
->isRecoveredOnBailout()) {
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
) {
100 // Leave this instruction for DCE.
105 // We have no uses, so sink this instruction in all the bailout
108 MOZ_ASSERT(!usesDominator
);
109 ins
->setRecoveredOnBailout();
110 JitSpewDef(JitSpew_Sink
,
111 " No live uses, recover the instruction on bailout\n", ins
);
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.
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()) {
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
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) {
152 if (*block
== lastJoin
) {
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
) {
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()) {
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) {
183 JitSpewDef(JitSpew_Sink
, " Can Clone & Recover, sink instruction\n",
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
))) {
195 MInstruction
* clone
= ins
->clone(alloc
, operands
);
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
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
;) {
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
)) {
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.
246 usesDominator
->safeInsertTop(nullptr, MBasicBlock::IgnoreRecover
);
247 block
->moveBefore(at
, ins
);