1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
/* -*- 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 "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