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/IonAnalysis.h"
10 #include "jit/JitSpewer.h"
11 #include "jit/MIRGenerator.h"
12 #include "jit/MIRGraph.h"
15 using namespace js::jit
;
17 // There are two constants which control whether a loop is LICM'd or is left
18 // unchanged. For rationale see comment in jit::LICM() below.
20 // A bit of quick profiling with the wasm Embenchen suite on x64 shows that
21 // the threshold pair (100,25) has either no effect or gives a small net
22 // reduction in memory traffic, compared to unconstrained LICMing. Halving
23 // them to (50,12) gives a small overall increase in memory traffic,
24 // suggesting it excludes too many loops from LICM. Doubling them to (200,50)
25 // gives a win that is even smaller than (100,25), hence (100,25) seems the
28 // If a loop has more than this number of basic blocks in its body, it won't
30 static constexpr size_t LargestAllowedLoop
= 100;
32 // If a loop contains an MTableSwitch instruction that has more than this many
33 // successors, it won't be LICM'd.
34 static constexpr size_t LargestAllowedTableSwitch
= 25;
36 // Test whether any instruction in the loop possiblyCalls().
37 static bool LoopContainsPossibleCall(MIRGraph
& graph
, MBasicBlock
* header
,
38 MBasicBlock
* backedge
) {
39 for (auto i(graph
.rpoBegin(header
));; ++i
) {
40 MOZ_ASSERT(i
!= graph
.rpoEnd(),
41 "Reached end of graph searching for blocks in loop");
42 MBasicBlock
* block
= *i
;
43 if (!block
->isMarked()) {
47 for (auto insIter(block
->begin()), insEnd(block
->end()); insIter
!= insEnd
;
49 MInstruction
* ins
= *insIter
;
50 if (ins
->possiblyCalls()) {
52 JitSpew(JitSpew_LICM
, " Possible call found at %s%u", ins
->opName(),
59 if (block
== backedge
) {
66 // Tests whether any instruction in the loop is a table-switch with more than
67 // `LargestAllowedTableSwitch` successors. If it returns true, it also
68 // returns the actual number of successors of the instruction in question,
69 // although that is used only for statistics/debug printing.
70 static bool LoopContainsBigTableSwitch(MIRGraph
& graph
, MBasicBlock
* header
,
71 /*OUT*/ size_t* numSuccessors
) {
72 MBasicBlock
* backedge
= header
->backedge();
74 for (auto i(graph
.rpoBegin(header
));; ++i
) {
75 MOZ_ASSERT(i
!= graph
.rpoEnd(),
76 "Reached end of graph searching for blocks in loop");
77 MBasicBlock
* block
= *i
;
78 if (!block
->isMarked()) {
82 for (auto insIter(block
->begin()), insEnd(block
->end()); insIter
!= insEnd
;
84 MInstruction
* ins
= *insIter
;
85 if (ins
->isTableSwitch() &&
86 ins
->toTableSwitch()->numSuccessors() > LargestAllowedTableSwitch
) {
87 *numSuccessors
= ins
->toTableSwitch()->numSuccessors();
92 if (block
== backedge
) {
99 // When a nested loop has no exits back into what would be its parent loop,
100 // MarkLoopBlocks on the parent loop doesn't mark the blocks of the nested
101 // loop, since they technically aren't part of the loop. However, AliasAnalysis
102 // currently does consider such nested loops to be part of their parent
103 // loops. Consequently, we can't use IsInLoop on dependency() values; we must
104 // test whether a dependency() is *before* the loop, even if it is not
105 // technically in the loop.
106 static bool IsBeforeLoop(MDefinition
* ins
, MBasicBlock
* header
) {
107 return ins
->block()->id() < header
->id();
110 // Test whether the given instruction is inside the loop (and thus not
112 static bool IsInLoop(MDefinition
* ins
) { return ins
->block()->isMarked(); }
114 // Test whether the given instruction is cheap and not worth hoisting unless
115 // one of its users will be hoisted as well.
116 static bool RequiresHoistedUse(const MDefinition
* ins
, bool hasCalls
) {
118 MOZ_ASSERT(!ins
->toBox()->input()->isBox(),
119 "Box of a box could lead to unbounded recursion");
123 // Integer constants are usually cheap and aren't worth hoisting on their
124 // own, in general. Floating-point constants typically are worth hoisting,
125 // unless they'll end up being spilled (eg. due to a call).
126 if (ins
->isConstant() && (!IsFloatingPointType(ins
->type()) || hasCalls
)) {
133 // Test whether the given instruction has any operands defined within the loop.
134 static bool HasOperandInLoop(MInstruction
* ins
, bool hasCalls
) {
135 // An instruction is only loop invariant if it and all of its operands can
136 // be safely hoisted into the loop preheader.
137 for (size_t i
= 0, e
= ins
->numOperands(); i
!= e
; ++i
) {
138 MDefinition
* op
= ins
->getOperand(i
);
144 if (RequiresHoistedUse(op
, hasCalls
)) {
145 // Recursively test for loop invariance. Note that the recursion is
146 // bounded because we require RequiresHoistedUse to be set at each
148 if (!HasOperandInLoop(op
->toInstruction(), hasCalls
)) {
158 // Test whether the given instruction is hoistable, ignoring memory
160 static bool IsHoistableIgnoringDependency(MInstruction
* ins
, bool hasCalls
) {
161 return ins
->isMovable() && !ins
->isEffectful() &&
162 !HasOperandInLoop(ins
, hasCalls
);
165 // Test whether the given instruction has a memory dependency inside the loop.
166 static bool HasDependencyInLoop(MInstruction
* ins
, MBasicBlock
* header
) {
167 // Don't hoist if this instruction depends on a store inside the loop.
168 if (MDefinition
* dep
= ins
->dependency()) {
169 return !IsBeforeLoop(dep
, header
);
174 // Test whether the given instruction is hoistable.
175 static bool IsHoistable(MInstruction
* ins
, MBasicBlock
* header
, bool hasCalls
) {
176 return IsHoistableIgnoringDependency(ins
, hasCalls
) &&
177 !HasDependencyInLoop(ins
, header
);
180 // In preparation for hoisting an instruction, hoist any of its operands which
181 // were too cheap to hoist on their own.
182 static void MoveDeferredOperands(MInstruction
* ins
, MInstruction
* hoistPoint
,
184 // If any of our operands were waiting for a user to be hoisted, make a note
186 for (size_t i
= 0, e
= ins
->numOperands(); i
!= e
; ++i
) {
187 MDefinition
* op
= ins
->getOperand(i
);
191 MOZ_ASSERT(RequiresHoistedUse(op
, hasCalls
),
192 "Deferred loop-invariant operand is not cheap");
193 MInstruction
* opIns
= op
->toInstruction();
195 // Recursively move the operands. Note that the recursion is bounded
196 // because we require RequiresHoistedUse to be set at each level.
197 MoveDeferredOperands(opIns
, hoistPoint
, hasCalls
);
200 JitSpew(JitSpew_LICM
,
201 " Hoisting %s%u (now that a user will be hoisted)",
202 opIns
->opName(), opIns
->id());
205 opIns
->block()->moveBefore(hoistPoint
, opIns
);
206 opIns
->setBailoutKind(BailoutKind::LICM
);
210 static void VisitLoopBlock(MBasicBlock
* block
, MBasicBlock
* header
,
211 MInstruction
* hoistPoint
, bool hasCalls
) {
212 for (auto insIter(block
->begin()), insEnd(block
->end()); insIter
!= insEnd
;) {
213 MInstruction
* ins
= *insIter
++;
215 if (!IsHoistable(ins
, header
, hasCalls
)) {
217 if (IsHoistableIgnoringDependency(ins
, hasCalls
)) {
218 JitSpew(JitSpew_LICM
,
219 " %s%u isn't hoistable due to dependency on %s%u",
220 ins
->opName(), ins
->id(), ins
->dependency()->opName(),
221 ins
->dependency()->id());
227 // Don't hoist a cheap constant if it doesn't enable us to hoist one of
228 // its uses. We want those instructions as close as possible to their
229 // use, to minimize register pressure.
230 if (RequiresHoistedUse(ins
, hasCalls
)) {
232 JitSpew(JitSpew_LICM
, " %s%u will be hoisted only if its users are",
233 ins
->opName(), ins
->id());
238 // Hoist operands which were too cheap to hoist on their own.
239 MoveDeferredOperands(ins
, hoistPoint
, hasCalls
);
242 JitSpew(JitSpew_LICM
, " Hoisting %s%u", ins
->opName(), ins
->id());
245 // Move the instruction to the hoistPoint.
246 block
->moveBefore(hoistPoint
, ins
);
247 ins
->setBailoutKind(BailoutKind::LICM
);
251 static void VisitLoop(MIRGraph
& graph
, MBasicBlock
* header
) {
252 MInstruction
* hoistPoint
= header
->loopPredecessor()->lastIns();
255 JitSpew(JitSpew_LICM
, " Visiting loop with header block%u, hoisting to %s%u",
256 header
->id(), hoistPoint
->opName(), hoistPoint
->id());
259 MBasicBlock
* backedge
= header
->backedge();
261 // This indicates whether the loop contains calls or other things which
262 // clobber most or all floating-point registers. In such loops,
263 // floating-point constants should not be hoisted unless it enables further
265 bool hasCalls
= LoopContainsPossibleCall(graph
, header
, backedge
);
267 for (auto i(graph
.rpoBegin(header
));; ++i
) {
268 MOZ_ASSERT(i
!= graph
.rpoEnd(),
269 "Reached end of graph searching for blocks in loop");
270 MBasicBlock
* block
= *i
;
271 if (!block
->isMarked()) {
276 JitSpew(JitSpew_LICM
, " Visiting block%u", block
->id());
279 VisitLoopBlock(block
, header
, hoistPoint
, hasCalls
);
281 if (block
== backedge
) {
287 bool jit::LICM(MIRGenerator
* mir
, MIRGraph
& graph
) {
288 JitSpew(JitSpew_LICM
, "Beginning LICM pass");
290 // Iterate in RPO to visit outer loops before inner loops. We'd hoist the
291 // same things either way, but outer first means we do a little less work.
292 for (auto i(graph
.rpoBegin()), e(graph
.rpoEnd()); i
!= e
; ++i
) {
293 MBasicBlock
* header
= *i
;
294 if (!header
->isLoopHeader()) {
299 size_t numBlocks
= MarkLoopBlocks(graph
, header
, &canOsr
);
301 if (numBlocks
== 0) {
302 JitSpew(JitSpew_LICM
,
303 " Skipping loop with header block%u -- contains zero blocks",
308 // There are various reasons why we might choose not to LICM a given loop:
310 // (a) Hoisting out of a loop that has an entry from the OSR block in
311 // addition to its normal entry is tricky. In theory we could clone
312 // the instruction and insert phis. In practice we don't bother.
314 // (b) If the loop contains a large number of blocks, we play safe and
315 // punt, in order to reduce the risk of creating excessive register
316 // pressure by hoisting lots of values out of the loop. In a larger
317 // loop there's more likely to be duplication of invariant expressions
318 // within the loop body, and that duplication will be GVN'd but only
319 // within the scope of the loop body, so there's less loss from not
320 // lifting them out of the loop entirely.
322 // (c) If the loop contains a multiway switch with many successors, there
323 // could be paths with low probabilities, from which LICMing will be a
324 // net loss, especially if a large number of values are hoisted out.
325 // See bug 1708381 for a spectacular example and bug 1712078 for
326 // further discussion.
328 // It's preferable to perform test (c) only if (a) and (b) pass since (c)
329 // is more expensive to determine -- requiring a visit to all the MIR
330 // nodes -- than (a) or (b), which only involve visiting all blocks.
334 JitSpew(JitSpew_LICM
, " Skipping loop with header block%u due to OSR",
337 } else if (numBlocks
> LargestAllowedLoop
) {
338 JitSpew(JitSpew_LICM
,
339 " Skipping loop with header block%u "
340 "due to too many blocks (%u > thresh %u)",
341 header
->id(), (uint32_t)numBlocks
, (uint32_t)LargestAllowedLoop
);
344 size_t switchSize
= 0;
345 if (LoopContainsBigTableSwitch(graph
, header
, &switchSize
)) {
346 JitSpew(JitSpew_LICM
,
347 " Skipping loop with header block%u "
348 "due to oversize tableswitch (%u > thresh %u)",
349 header
->id(), (uint32_t)switchSize
,
350 (uint32_t)LargestAllowedTableSwitch
);
356 VisitLoop(graph
, header
);
359 UnmarkLoopBlocks(graph
, header
);
361 if (mir
->shouldCancel("LICM (main loop)")) {