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