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/LICM.h"
8 :
9 : #include "jit/IonAnalysis.h"
10 : #include "jit/JitSpewer.h"
11 : #include "jit/MIRGenerator.h"
12 : #include "jit/MIRGraph.h"
13 :
14 : using namespace js;
15 : using namespace js::jit;
16 :
17 : // Test whether any instruction in the loop possiblyCalls().
18 : static bool
19 5 : LoopContainsPossibleCall(MIRGraph& graph, MBasicBlock* header, MBasicBlock* backedge)
20 : {
21 85 : for (auto i(graph.rpoBegin(header)); ; ++i) {
22 85 : MOZ_ASSERT(i != graph.rpoEnd(), "Reached end of graph searching for blocks in loop");
23 85 : MBasicBlock* block = *i;
24 85 : if (!block->isMarked())
25 6 : continue;
26 :
27 289 : for (auto insIter(block->begin()), insEnd(block->end()); insIter != insEnd; ++insIter) {
28 215 : MInstruction* ins = *insIter;
29 215 : if (ins->possiblyCalls()) {
30 : #ifdef JS_JITSPEW
31 5 : JitSpew(JitSpew_LICM, " Possile call found at %s%u", ins->opName(), ins->id());
32 : #endif
33 5 : return true;
34 : }
35 : }
36 :
37 74 : if (block == backedge)
38 0 : break;
39 80 : }
40 0 : return false;
41 : }
42 :
43 : // When a nested loop has no exits back into what would be its parent loop,
44 : // MarkLoopBlocks on the parent loop doesn't mark the blocks of the nested
45 : // loop, since they technically aren't part of the loop. However, AliasAnalysis
46 : // currently does consider such nested loops to be part of their parent
47 : // loops. Consequently, we can't use IsInLoop on dependency() values; we must
48 : // test whether a dependency() is *before* the loop, even if it is not
49 : // technically in the loop.
50 : static bool
51 32 : IsBeforeLoop(MDefinition* ins, MBasicBlock* header)
52 : {
53 32 : return ins->block()->id() < header->id();
54 : }
55 :
56 : // Test whether the given instruction is inside the loop (and thus not
57 : // loop-invariant).
58 : static bool
59 510 : IsInLoop(MDefinition* ins)
60 : {
61 510 : return ins->block()->isMarked();
62 : }
63 :
64 : // Test whether the given instruction is cheap and not worth hoisting unless
65 : // one of its users will be hoisted as well.
66 : static bool
67 548 : RequiresHoistedUse(const MDefinition* ins, bool hasCalls)
68 : {
69 548 : if (ins->isConstantElements())
70 0 : return true;
71 :
72 548 : if (ins->isBox()) {
73 20 : MOZ_ASSERT(!ins->toBox()->input()->isBox(),
74 : "Box of a box could lead to unbounded recursion");
75 20 : return true;
76 : }
77 :
78 : // Integer constants are usually cheap and aren't worth hoisting on their
79 : // own, in general. Floating-point constants typically are worth hoisting,
80 : // unless they'll end up being spilled (eg. due to a call).
81 528 : if (ins->isConstant() && (!IsFloatingPointType(ins->type()) || hasCalls))
82 112 : return true;
83 :
84 416 : return false;
85 : }
86 :
87 : // Test whether the given instruction has any operands defined within the loop.
88 : static bool
89 612 : HasOperandInLoop(MInstruction* ins, bool hasCalls)
90 : {
91 : // An instruction is only loop invariant if it and all of its operands can
92 : // be safely hoisted into the loop preheader.
93 706 : for (size_t i = 0, e = ins->numOperands(); i != e; ++i) {
94 506 : MDefinition* op = ins->getOperand(i);
95 :
96 506 : if (!IsInLoop(op))
97 74 : continue;
98 :
99 432 : if (RequiresHoistedUse(op, hasCalls)) {
100 : // Recursively test for loop invariance. Note that the recursion is
101 : // bounded because we require RequiresHoistedUse to be set at each
102 : // level.
103 20 : if (!HasOperandInLoop(op->toInstruction(), hasCalls))
104 20 : continue;
105 : }
106 :
107 412 : return true;
108 : }
109 200 : return false;
110 : }
111 :
112 : // Test whether the given instruction is hoistable, ignoring memory
113 : // dependencies.
114 : static bool
115 1536 : IsHoistableIgnoringDependency(MInstruction* ins, bool hasCalls)
116 : {
117 2128 : return ins->isMovable() && !ins->isEffectful() && !ins->neverHoist() &&
118 2128 : !HasOperandInLoop(ins, hasCalls);
119 : }
120 :
121 : // Test whether the given instruction has a memory dependency inside the loop.
122 : static bool
123 148 : HasDependencyInLoop(MInstruction* ins, MBasicBlock* header)
124 : {
125 : // Don't hoist if this instruction depends on a store inside the loop.
126 148 : if (MDefinition* dep = ins->dependency())
127 32 : return !IsBeforeLoop(dep, header);
128 116 : return false;
129 : }
130 :
131 : // Test whether the given instruction is hoistable.
132 : static bool
133 826 : IsHoistable(MInstruction* ins, MBasicBlock* header, bool hasCalls)
134 : {
135 826 : return IsHoistableIgnoringDependency(ins, hasCalls) && !HasDependencyInLoop(ins, header);
136 : }
137 :
138 : // In preparation for hoisting an instruction, hoist any of its operands which
139 : // were too cheap to hoist on their own.
140 : static void
141 4 : MoveDeferredOperands(MInstruction* ins, MInstruction* hoistPoint, bool hasCalls)
142 : {
143 : // If any of our operands were waiting for a user to be hoisted, make a note
144 : // to hoist them.
145 8 : for (size_t i = 0, e = ins->numOperands(); i != e; ++i) {
146 4 : MDefinition* op = ins->getOperand(i);
147 4 : if (!IsInLoop(op))
148 4 : continue;
149 0 : MOZ_ASSERT(RequiresHoistedUse(op, hasCalls),
150 : "Deferred loop-invariant operand is not cheap");
151 0 : MInstruction* opIns = op->toInstruction();
152 :
153 : // Recursively move the operands. Note that the recursion is bounded
154 : // because we require RequiresHoistedUse to be set at each level.
155 0 : MoveDeferredOperands(opIns, hoistPoint, hasCalls);
156 :
157 : #ifdef JS_JITSPEW
158 0 : JitSpew(JitSpew_LICM, " Hoisting %s%u (now that a user will be hoisted)",
159 0 : opIns->opName(), opIns->id());
160 : #endif
161 :
162 0 : opIns->block()->moveBefore(hoistPoint, opIns);
163 : }
164 4 : }
165 :
166 : static void
167 293 : VisitLoopBlock(MBasicBlock* block, MBasicBlock* header, MInstruction* hoistPoint, bool hasCalls)
168 : {
169 1119 : for (auto insIter(block->begin()), insEnd(block->end()); insIter != insEnd; ) {
170 826 : MInstruction* ins = *insIter++;
171 :
172 826 : if (!IsHoistable(ins, header, hasCalls)) {
173 : #ifdef JS_JITSPEW
174 710 : if (IsHoistableIgnoringDependency(ins, hasCalls)) {
175 96 : JitSpew(JitSpew_LICM, " %s%u isn't hoistable due to dependency on %s%u",
176 32 : ins->opName(), ins->id(),
177 64 : ins->dependency()->opName(), ins->dependency()->id());
178 : }
179 : #endif
180 710 : continue;
181 : }
182 :
183 : // Don't hoist a cheap constant if it doesn't enable us to hoist one of
184 : // its uses. We want those instructions as close as possible to their
185 : // use, to minimize register pressure.
186 116 : if (RequiresHoistedUse(ins, hasCalls)) {
187 : #ifdef JS_JITSPEW
188 224 : JitSpew(JitSpew_LICM, " %s%u will be hoisted only if its users are",
189 224 : ins->opName(), ins->id());
190 : #endif
191 112 : continue;
192 : }
193 :
194 : // Hoist operands which were too cheap to hoist on their own.
195 4 : MoveDeferredOperands(ins, hoistPoint, hasCalls);
196 :
197 : #ifdef JS_JITSPEW
198 4 : JitSpew(JitSpew_LICM, " Hoisting %s%u", ins->opName(), ins->id());
199 : #endif
200 :
201 : // Move the instruction to the hoistPoint.
202 4 : block->moveBefore(hoistPoint, ins);
203 : }
204 293 : }
205 :
206 : static void
207 5 : VisitLoop(MIRGraph& graph, MBasicBlock* header)
208 : {
209 5 : MInstruction* hoistPoint = header->loopPredecessor()->lastIns();
210 :
211 : #ifdef JS_JITSPEW
212 10 : JitSpew(JitSpew_LICM, " Visiting loop with header block%u, hoisting to %s%u",
213 10 : header->id(), hoistPoint->opName(), hoistPoint->id());
214 : #endif
215 :
216 5 : MBasicBlock* backedge = header->backedge();
217 :
218 : // This indicates whether the loop contains calls or other things which
219 : // clobber most or all floating-point registers. In such loops,
220 : // floating-point constants should not be hoisted unless it enables further
221 : // hoisting.
222 5 : bool hasCalls = LoopContainsPossibleCall(graph, header, backedge);
223 :
224 318 : for (auto i(graph.rpoBegin(header)); ; ++i) {
225 318 : MOZ_ASSERT(i != graph.rpoEnd(), "Reached end of graph searching for blocks in loop");
226 318 : MBasicBlock* block = *i;
227 318 : if (!block->isMarked())
228 25 : continue;
229 :
230 293 : VisitLoopBlock(block, header, hoistPoint, hasCalls);
231 :
232 293 : if (block == backedge)
233 5 : break;
234 313 : }
235 5 : }
236 :
237 : bool
238 8 : jit::LICM(MIRGenerator* mir, MIRGraph& graph)
239 : {
240 8 : JitSpew(JitSpew_LICM, "Beginning LICM pass");
241 :
242 : // Iterate in RPO to visit outer loops before inner loops. We'd hoist the
243 : // same things either way, but outer first means we do a little less work.
244 411 : for (auto i(graph.rpoBegin()), e(graph.rpoEnd()); i != e; ++i) {
245 403 : MBasicBlock* header = *i;
246 403 : if (!header->isLoopHeader())
247 796 : continue;
248 :
249 : bool canOsr;
250 5 : size_t numBlocks = MarkLoopBlocks(graph, header, &canOsr);
251 :
252 5 : if (numBlocks == 0) {
253 0 : JitSpew(JitSpew_LICM, " Loop with header block%u isn't actually a loop", header->id());
254 0 : continue;
255 : }
256 :
257 : // Hoisting out of a loop that has an entry from the OSR block in
258 : // addition to its normal entry is tricky. In theory we could clone
259 : // the instruction and insert phis.
260 5 : if (!canOsr)
261 5 : VisitLoop(graph, header);
262 : else
263 0 : JitSpew(JitSpew_LICM, " Skipping loop with header block%u due to OSR", header->id());
264 :
265 5 : UnmarkLoopBlocks(graph, header);
266 :
267 5 : if (mir->shouldCancel("LICM (main loop)"))
268 0 : return false;
269 : }
270 :
271 8 : return true;
272 : }
|
