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/. */
7 ///////////////////////////////////////////////////////////////////////////////
9 // Documentation. Code starts about 670 lines down from here. //
11 ///////////////////////////////////////////////////////////////////////////////
13 // [SMDOC] An overview of Ion's register allocator
15 // The intent of this documentation is to give maintainers a map with which to
16 // navigate the allocator. As further understanding is obtained, it should be
17 // added to this overview.
19 // Where possible, invariants are stated and are marked "(INVAR)". Many
20 // details are omitted because their workings are currently unknown. In
21 // particular, this overview doesn't explain how Intel-style "modify" (tied)
22 // operands are handled. Facts or invariants that are speculative -- believed
23 // to be true, but not verified at the time of writing -- are marked "(SPEC)".
25 // The various concepts are interdependent, so a single forwards reading of the
26 // following won't make much sense. Many concepts are explained only after
27 // they are mentioned.
29 // Where possible examples are shown. Without those the description is
30 // excessively abstract.
32 // Names of the form ::name mean BacktrackingAllocator::name.
34 // The description falls into two sections:
36 // * Section 1: A tour of the data structures
37 // * Section 2: The core allocation loop, and bundle splitting
39 // The allocator sometimes produces poor allocations, with excessive spilling
40 // and register-to-register moves (bugs 1752520, bug 1714280 bug 1746596).
41 // Work in bug 1752582 shows we can get better quality allocations from this
42 // framework without having to make any large (conceptual) changes, by having
43 // better splitting heuristics.
45 // At https://bugzilla.mozilla.org/show_bug.cgi?id=1758274#c17
46 // (https://bugzilla.mozilla.org/attachment.cgi?id=9288467) is a document
47 // written at the same time as these comments. It describes some improvements
48 // we could make to our splitting heuristics, particularly in the presence of
49 // loops and calls, and shows why the current implementation sometimes produces
50 // excessive spilling. It builds on the commentary in this SMDOC.
55 // There are three major phases in allocation. They run sequentially, at a
56 // per-function granularity.
58 // (1) Liveness analysis and bundle formation
59 // (2) Bundle allocation and last-chance allocation
60 // (3) Rewriting the function to create MoveGroups and to "install"
63 // The input language (LIR) is in SSA form, and phases (1) and (3) depend on
64 // that SSAness. Without it the allocator wouldn't work.
66 // The top level function is ::go. The phases are divided into functions as
69 // (1) ::buildLivenessInfo, ::mergeAndQueueRegisters
70 // (2) ::processBundle, ::tryAllocatingRegistersForSpillBundles,
72 // (3) ::createMoveGroupsFromLiveRangeTransitions, ::installAllocationsInLIR,
73 // ::populateSafepoints, ::annotateMoveGroups
75 // The code in this file is structured as much as possible in the same sequence
76 // as flow through the pipeline. Hence, top level function ::go is right at
77 // the end. Where a function depends on helper function(s), the helpers appear
81 // ========================================================================
83 // ==== Section 1: A tour of the data structures ====
85 // ========================================================================
87 // Here are the key data structures necessary for understanding what follows.
89 // Some basic data structures
90 // ~~~~~~~~~~~~~~~~~~~~~~~~~~
94 // A CodePosition is an unsigned 32-bit int that indicates an instruction index
95 // in the incoming LIR. Each LIR actually has two code positions, one to
96 // denote the "input" point (where, one might imagine, the operands are read,
97 // at least useAtStart ones) and the "output" point, where operands are
100 // Block 0 [successor 2] [successor 1]
101 // 2-3 WasmParameter [def v1<g>:r14]
102 // 4-5 WasmCall [use v1:F:r14]
103 // 6-7 WasmLoadTls [def v2<o>] [use v1:R]
104 // 8-9 WasmNullConstant [def v3<o>]
105 // 10-11 Compare [def v4<i>] [use v2:R] [use v3:A]
106 // 12-13 TestIAndBranch [use v4:R]
108 // So for example the WasmLoadTls insn has its input CodePosition as 6 and
109 // output point as 7. Input points are even numbered, output points are odd
110 // numbered. CodePositions 0 and 1 never appear, because LIR instruction IDs
111 // start at 1. Indeed, CodePosition 0 is assumed to be invalid and hence is
112 // used as a marker for "unusual conditions" in various places.
114 // Phi nodes exist in the instruction stream too. They always appear at the
115 // start of blocks (of course) (SPEC), but their start and end points are
116 // printed for the group as a whole. This is to emphasise that they are really
117 // parallel assignments and that printing them sequentially would misleadingly
118 // imply that they are executed sequentially. Example:
120 // Block 6 [successor 7] [successor 8]
121 // 56-59 Phi [def v19<o>] [use v2:A] [use v5:A] [use v13:A]
122 // 56-59 Phi [def v20<o>] [use v7:A] [use v14:A] [use v12:A]
123 // 60-61 WasmLoadSlot [def v21<o>] [use v1:R]
124 // 62-63 Compare [def v22<i>] [use v20:R] [use v21:A]
125 // 64-65 TestIAndBranch [use v22:R]
127 // See that both Phis are printed with limits 56-59, even though they are
128 // stored in the LIR array like regular LIRs and so have code points 56-57 and
131 // The process of allocation adds MoveGroup LIRs to the function. Each
132 // incoming LIR has its own private list of MoveGroups (actually, 3 lists; two
133 // for moves that conceptually take place before the instruction, and one for
134 // moves after it). Hence the CodePositions for LIRs (the "62-63", etc, above)
135 // do not change as a result of allocation.
137 // Virtual registers (vregs) in LIR
138 // --------------------------------
139 // The MIR from which the LIR is derived, is standard SSA. That SSAness is
140 // carried through into the LIR (SPEC). In the examples here, LIR SSA names
141 // (virtual registers, a.k.a. vregs) are printed as "v<number>". v0 never
142 // appears and is presumed to be a special value, perhaps "invalid" (SPEC).
144 // The allocator core has a type VirtualRegister, but this is private to the
145 // allocator and not part of the LIR. It carries far more information than
146 // merely the name of the vreg. The allocator creates one VirtualRegister
147 // structure for each vreg in the LIR.
149 // LDefinition and LUse
150 // --------------------
151 // These are part of the incoming LIR. Each LIR instruction defines zero or
152 // more values, and contains one LDefinition for each defined value (SPEC).
153 // Each instruction has zero or more input operands, each of which has its own
156 // Both LDefinition and LUse hold both a virtual register name and, in general,
157 // a real (physical) register identity. The incoming LIR has the real register
158 // fields unset, except in places where the incoming LIR has fixed register
159 // constraints (SPEC). Phase 3 of allocation will visit all of the
160 // LDefinitions and LUses so as to write into the real register fields the
161 // decisions made by the allocator. For LUses, this is done by overwriting the
162 // complete LUse with a different LAllocation, for example LStackSlot. That's
163 // possible because LUse is a child class of LAllocation.
165 // This action of reading and then later updating LDefinition/LUses is the core
166 // of the allocator's interface to the outside world.
168 // To make visiting of LDefinitions/LUses possible, the allocator doesn't work
169 // with LDefinition and LUse directly. Rather it has pointers to them
170 // (VirtualRegister::def_, UsePosition::use_). Hence Phase 3 can modify the
173 // (INVARs, all SPEC):
175 // - The collective VirtualRegister::def_ values should be unique, and there
176 // should be a 1:1 mapping between the VirtualRegister::def_ values and the
177 // LDefinitions in the LIR. (So that the LIR LDefinition has exactly one
178 // VirtualRegister::def_ to track it). But only for the valid LDefinitions.
179 // If isBogusTemp() is true, the definition is invalid and doesn't have a
182 // - The same for uses: there must be a 1:1 correspondence between the
183 // CodePosition::use_ values and the LIR LUses.
185 // - The allocation process must preserve these 1:1 mappings. That implies
186 // (weaker) that the number of VirtualRegisters and of UsePositions must
187 // remain constant through allocation. (Eg: losing them would mean that some
188 // LIR def or use would necessarily not get annotated with its final
189 // allocation decision. Duplicating them would lead to the possibility of
190 // conflicting allocation decisions.)
192 // Other comments regarding LIR
193 // ----------------------------
194 // The incoming LIR is structured into basic blocks and a CFG, as one would
195 // expect. These (insns, block boundaries, block edges etc) are available
196 // through the BacktrackingAllocator object. They are important for Phases 1
197 // and 3 but not for Phase 2.
199 // Phase 3 "rewrites" the input LIR so as to "install" the final allocation.
200 // It has to insert MoveGroup instructions, but that isn't done by pushing them
201 // into the instruction array. Rather, each LIR has 3 auxiliary sets of
202 // MoveGroups (SPEC): two that "happen" conceptually before the LIR, and one
203 // that happens after it. The rewriter inserts MoveGroups into one of these 3
204 // sets, and later code generation phases presumably insert the sets (suitably
205 // translated) into the final machine code (SPEC).
208 // Key data structures: LiveRange, VirtualRegister and LiveBundle
209 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
211 // These three have central roles in allocation. Of them, LiveRange is the
212 // most central. VirtualRegister is conceptually important throughout, but
213 // appears less frequently in the allocator code. LiveBundle is important only
214 // in Phase 2 (where it is central) and at the end of Phase 1, but plays no
217 // It's important to understand that LiveRange and VirtualRegister correspond
218 // to concepts visible in the incoming LIR, which is in SSA form. LiveBundle
219 // by comparison is related to neither the structure of LIR nor its SSA
220 // properties. Instead, LiveBundle is an essentially adminstrative structure
221 // used to accelerate allocation and to implement a crude form of
224 // VirtualRegisters and LiveRanges are (almost) static throughout the process,
225 // because they reflect aspects of the incoming LIR, which does not change.
226 // LiveBundles by contrast come and go; they are created, but may be split up
227 // into new bundles, and old ones abandoned.
229 // Each LiveRange is a member of two different linked lists, chained through
230 // fields registerLink and bundleLink.
232 // A VirtualRegister (described in detail below) has a list of LiveRanges that
233 // it "owns". These are chained through LiveRange::registerLink.
235 // A LiveBundle (also described below) also has a list LiveRanges that it
236 // "owns", chained through LiveRange::bundleLink.
238 // Hence each LiveRange is "owned" by one VirtualRegister and one LiveBundle.
239 // LiveRanges may have their owning LiveBundle changed as a result of
240 // splitting. By contrast a LiveRange stays with its "owning" VirtualRegister
243 // A few LiveRanges have no VirtualRegister. This is used to implement
244 // register spilling for calls. Each physical register that's not preserved
245 // across a call has a small range that covers the call. It is
246 // ::buildLivenessInfo that adds these small ranges.
248 // Iterating over every VirtualRegister in the system is a common operation and
249 // is straightforward because (somewhat redundantly?) the LIRGraph knows the
250 // number of vregs, and more importantly because BacktrackingAllocator::vregs
251 // is a vector of all VirtualRegisters. By contrast iterating over every
252 // LiveBundle in the system is more complex because there is no top-level
253 // registry of them. It is still possible though. See ::dumpLiveRangesByVReg
254 // and ::dumpLiveRangesByBundle for example code.
258 // Fundamentally, a LiveRange (often written just "range") is a request for
259 // storage of a LIR vreg for some contiguous sequence of LIRs. A LiveRange
260 // generally covers only a fraction of a vreg's overall lifetime, so multiple
261 // LiveRanges are generally needed to cover the whole lifetime.
263 // A LiveRange contains (amongst other things):
265 // * the vreg for which it is for, as a VirtualRegister*
267 // * the range of CodePositions for which it is for, as a LiveRange::Range
269 // * auxiliary information:
271 // - a boolean that indicates whether this LiveRange defines a value for the
272 // vreg. If so, that definition is regarded as taking place at the first
273 // CodePoint of the range.
275 // - a linked list of uses of the vreg within this range. Each use is a pair
276 // of a CodePosition and an LUse*. (INVAR): the uses are maintained in
277 // increasing order of CodePosition. Multiple uses at the same
278 // CodePosition are permitted, since that is necessary to represent an LIR
279 // that uses the same vreg in more than one of its operand slots.
281 // Some important facts about LiveRanges are best illustrated with examples:
283 // v25 75-82 { 75_def:R 78_v25:A 82_v25:A }
285 // This LiveRange is for vreg v25. The value is defined at CodePosition 75,
286 // with the LIR requiring that it be in a register. It is used twice at
287 // positions 78 and 82, both with no constraints (A meaning "any"). The range
288 // runs from position 75 to 82 inclusive. Note however that LiveRange::Range
289 // uses non-inclusive range ends; hence its .to field would be 83, not 82.
291 // v26 84-85 { 85_v26:R }
293 // This LiveRange is for vreg v26. Here, there's only a single use of it at
294 // position 85. Presumably it is defined in some other LiveRange.
298 // This LiveRange is for vreg v19. There is no def and no uses, so at first
299 // glance this seems redundant. But it isn't: it still expresses a request for
300 // storage for v19 across 74-79, because Phase 1 regards v19 as being live in
301 // this range (meaning: having a value that, if changed in this range, would
302 // cause the program to fail).
306 // * (INVAR) Each vreg/VirtualRegister has at least one LiveRange.
308 // * (INVAR) Exactly one LiveRange of a vreg gives a definition for the value.
309 // All other LiveRanges must consist only of uses (including zero uses, for a
310 // "flow-though" range as mentioned above). This requirement follows from
311 // the fact that LIR is in SSA form.
313 // * It follows from this, that the LiveRanges for a VirtualRegister must form
314 // a tree, where the parent-child relationship is "control flows directly
315 // from a parent LiveRange (anywhere in the LiveRange) to a child LiveRange
316 // (start)". The entire tree carries only one value. This is a use of
317 // SSAness in the allocator which is fundamental: without SSA input, this
318 // design would not work.
320 // The root node (LiveRange) in the tree must be one that defines the value,
321 // and all other nodes must only use or be flow-throughs for the value. It's
322 // OK for LiveRanges in the tree to overlap, providing that there is a unique
323 // root node -- otherwise it would be unclear which LiveRange provides the
326 // The function ::createMoveGroupsFromLiveRangeTransitions runs after all
327 // LiveBundles have been allocated. It visits each VirtualRegister tree in
328 // turn. For every parent->child edge in a tree, it creates a MoveGroup that
329 // copies the value from the parent into the child -- this is how the
330 // allocator decides where to put MoveGroups. There are various other
331 // details not described here.
333 // * It's important to understand that a LiveRange carries no meaning about
334 // control flow beyond that implied by the SSA (hence, dominance)
335 // relationship between a def and its uses. In particular, there's no
336 // implication that execution "flowing into" the start of the range implies
337 // that it will "flow out" of the end. Or that any particular use will or
338 // will not be executed.
340 // * (very SPEC) Indeed, even if a range has a def, there's no implication that
341 // a use later in the range will have been immediately preceded by execution
342 // of the def. It could be that the def is executed, flow jumps somewhere
343 // else, and later jumps back into the middle of the range, where there are
346 // * Uses of a vreg by a phi node are not mentioned in the use list of a
347 // LiveRange. The reasons for this are unknown, but it is speculated that
348 // this is because we don't need to know about phi uses where we use the list
349 // of positions. See comments on VirtualRegister::usedByPhi_.
351 // * Similarly, a definition of a vreg by a phi node is not regarded as being a
352 // definition point (why not?), at least as the view of
353 // LiveRange::hasDefinition_.
355 // * LiveRanges that nevertheless include a phi-defined value have their first
356 // point set to the first of the block of phis, even if the var isn't defined
357 // by that specific phi. Eg:
359 // Block 6 [successor 7] [successor 8]
360 // 56-59 Phi [def v19<o>] [use v2:A] [use v5:A] [use v13:A]
361 // 56-59 Phi [def v20<o>] [use v7:A] [use v14:A] [use v12:A]
362 // 60-61 WasmLoadSlot [def v21<o>] [use v1:R]
363 // 62-63 Compare [def v22<i>] [use v20:R] [use v21:A]
365 // The relevant live range for v20 is
367 // v20 56-65 { 63_v20:R }
369 // Observe that it starts at 56, not 58.
373 // Each VirtualRegister is associated with an SSA value created by the LIR.
374 // Fundamentally it is a container to hold all of the LiveRanges that together
375 // indicate where the value must be kept live. This is a linked list beginning
376 // at VirtualRegister::ranges_, and which, as described above, is chained
377 // through LiveRange::registerLink. The set of LiveRanges must logically form
378 // a tree, rooted at the LiveRange which defines the value.
380 // For adminstrative convenience, the linked list must contain the LiveRanges
381 // in order of increasing start point.
383 // There are various auxiliary fields, most importantly the LIR node and the
384 // associated LDefinition that define the value.
386 // It is OK, and quite common, for LiveRanges of a VirtualRegister to overlap.
387 // The effect will be that, in an overlapped area, there are two storage
388 // locations holding the value. This is OK -- although wasteful of storage
389 // resources -- because the SSAness means the value must be the same in both
390 // locations. Hence there's no questions like "which LiveRange holds the most
391 // up-to-date value?", since it's all just one value anyway.
393 // Note by contrast, it is *not* OK for the LiveRanges of a LiveBundle to
398 // Similar to VirtualRegister, a LiveBundle is also, fundamentally, a container
399 // for a set of LiveRanges. The set is stored as a linked list, rooted at
400 // LiveBundle::ranges_ and chained through LiveRange::bundleLink.
402 // However, the similarity ends there:
404 // * The LiveRanges in a LiveBundle absolutely must not overlap. They must
405 // indicate disjoint sets of CodePositions, and must be stored in the list in
406 // order of increasing CodePosition. Because of the no-overlap requirement,
407 // these ranges form a total ordering regardless of whether one uses the
408 // LiveRange::Range::from_ or ::to_ fields for comparison.
410 // * The LiveRanges in a LiveBundle can otherwise be entirely arbitrary and
411 // unrelated. They can be from different VirtualRegisters and can have no
412 // particular mutual significance w.r.t. the SSAness or structure of the
415 // LiveBundles are the fundamental unit of allocation. The allocator attempts
416 // to find a single storage location that will work for all LiveRanges in the
417 // bundle. That's why the ranges must not overlap. If no such location can be
418 // found, the allocator may decide to split the bundle into multiple smaller
419 // bundles. Each of those may be allocated independently.
421 // The other really important field is LiveBundle::alloc_, indicating the
422 // chosen storage location.
424 // Here's an example, for a LiveBundle before it has been allocated:
426 // LB2(parent=none v3 8-21 { 16_v3:A } ## v3 24-25 { 25_v3:F:xmm0 })
428 // LB merely indicates "LiveBundle", and the 2 is the debugId_ value (see
429 // below). This bundle has two LiveRanges
431 // v3 8-21 { 16_v3:A }
432 // v3 24-25 { 25_v3:F:xmm0 }
434 // both of which (coincidentally) are for the same VirtualRegister, v3.The
435 // second LiveRange has a fixed use in `xmm0`, whilst the first one doesn't
436 // care (A meaning "any location") so the allocator *could* choose `xmm0` for
437 // the bundle as a whole.
439 // One might ask: why bother with LiveBundle at all? After all, it would be
440 // possible to get correct allocations by allocating each LiveRange
441 // individually, then leaving ::createMoveGroupsFromLiveRangeTransitions to add
442 // MoveGroups to join up LiveRanges that form each SSA value tree (that is,
443 // LiveRanges belonging to each VirtualRegister).
445 // There are two reasons:
447 // (1) By putting multiple LiveRanges into each LiveBundle, we can end up with
448 // many fewer LiveBundles than LiveRanges. Since the cost of allocating a
449 // LiveBundle is substantially less than the cost of allocating each of its
450 // LiveRanges individually, the allocator will run faster.
452 // (2) It provides a crude form of move-coalescing. There are situations where
453 // it would be beneficial, although not mandatory, to have two LiveRanges
454 // assigned to the same storage unit. Most importantly: (a) LiveRanges
455 // that form all of the inputs, and the output, of a phi node. (b)
456 // LiveRanges for the output and first-operand values in the case where we
457 // are targetting Intel-style instructions.
459 // In such cases, if the bundle can be allocated as-is, then no extra moves
460 // are necessary. If not (and the bundle is split), then
461 // ::createMoveGroupsFromLiveRangeTransitions will later fix things up by
462 // inserting MoveGroups in the right places.
464 // Merging of LiveRanges into LiveBundles is done in Phase 1, by
465 // ::mergeAndQueueRegisters, after liveness analysis (which generates only
468 // For the bundle mentioned above, viz
470 // LB2(parent=none v3 8-21 { 16_v3:A } ## v3 24-25 { 25_v3:F:xmm0 })
472 // the allocator did not in the end choose to allocate it to `xmm0`. Instead
473 // it was split into two bundles, LB6 (a "spill parent", or root node in the
474 // trees described above), and LB9, a leaf node, that points to its parent LB6:
476 // LB6(parent=none v3 8-21 %xmm1.s { 16_v3:A } ## v3 24-25 %xmm1.s { })
477 // LB9(parent=LB6 v3 24-25 %xmm0.s { 25_v3:F:rax })
479 // Note that both bundles now have an allocation, and that is printed,
480 // redundantly, for each LiveRange in the bundle -- hence the repeated
481 // `%xmm1.s` in the lines above. Since all LiveRanges in a LiveBundle must be
482 // allocated to the same storage location, we never expect to see output like
485 // LB6(parent=none v3 8-21 %xmm1.s { 16_v3:A } ## v3 24-25 %xmm2.s { })
487 // and that is in any case impossible, since a LiveRange doesn't have an
488 // LAllocation field. Instead it has a pointer to its LiveBundle, and the
489 // LAllocation lives in the LiveBundle.
491 // For the resulting allocation (LB6 and LB9), all the LiveRanges are use-only
492 // or flow-through. There are no definitions. But they are all for the same
493 // VirtualReg, v3, so they all have the same value. An important question is
494 // where they "get their value from". The answer is that
495 // ::createMoveGroupsFromLiveRangeTransitions will have to insert suitable
496 // MoveGroups so that each LiveRange for v3 can "acquire" the value from a
497 // previously-executed LiveRange, except for the range that defines it. The
498 // defining LiveRange is not visible here; either it is in some other
499 // LiveBundle, not shown, or (more likely) the value is defined by a phi-node,
500 // in which case, as mentioned previously, it is not shown as having an
501 // explicit definition in any LiveRange.
503 // LiveBundles also have a `SpillSet* spill_` field (see below) and a
504 // `LiveBundle* spillParent_`. The latter is used to ensure that all bundles
505 // originating from an "original" bundle share the same spill slot. The
506 // `spillParent_` pointers can be thought of creating a 1-level tree, where
507 // each node points at its parent. Since the tree can be only 1-level, the
508 // following invariant (INVAR) must be maintained:
510 // * if a LiveBundle has a non-null spillParent_ field, then it is a leaf node,
511 // and no other LiveBundle can point at this one.
513 // * else (it has a null spillParent_ field) it is a root node, and so other
514 // LiveBundles may point at it.
516 // When compiled with JS_JITSPEW, LiveBundle has a 32-bit `debugId_` field.
517 // This is used only for debug printing, and makes it easier to see
518 // parent-child relationships induced by the `spillParent_` pointers.
520 // The "life cycle" of LiveBundles is described in Section 2 below.
523 // Secondary data structures: SpillSet, Requirement
524 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
528 // A SpillSet is a container for a set of LiveBundles that have been spilled,
529 // all of which are assigned the same spill slot. The set is represented as a
530 // vector of points to LiveBundles. SpillSet also contains the identity of the
531 // spill slot (its LAllocation).
533 // A LiveBundle, if it is to be spilled, has a pointer to the relevant
534 // SpillSet, and the SpillSet in turn has a pointer back to the LiveBundle in
535 // its vector thereof. So LiveBundles (that are to be spilled) and SpillSets
536 // point at each other.
538 // (SPEC) LiveBundles that are not to be spilled (or for which the decision has
539 // yet to be made, have their SpillSet pointers as null. (/SPEC)
543 // Requirements are used transiently during the main allocation loop. It
544 // summarises the set of constraints on storage location (must be any register,
545 // must be this specific register, must be stack, etc) for a LiveBundle. This
546 // is so that the main allocation loop knows what kind of storage location it
547 // must choose in order to satisfy all of the defs and uses within the bundle.
549 // What Requirement provides is (a) a partially ordered set of locations, and
550 // (b) a constraint-merging method `merge`.
552 // Requirement needs a rewrite (and, in fact, that has already happened in
553 // un-landed code in bug 1758274) for the following reasons:
555 // * it's potentially buggy (bug 1761654), although that doesn't currently
556 // affect us, for reasons which are unclear.
558 // * the partially ordered set has a top point, meaning "no constraint", but it
559 // doesn't have a corresponding bottom point, meaning "impossible
560 // constraints". (So it's a partially ordered set, but not a lattice). This
561 // leads to awkward coding in some places, which would be simplified if there
562 // were an explicit way to indicate "impossible constraint".
568 // Here's some not-very-good ASCII art that tries to summarise the data
569 // structures that persist for the entire allocation of a function:
571 // BacktrackingAllocator
577 // VirtualRegister -->--(ins)--> LNode
578 // | | `->--(def)--> LDefinition
583 // `--v->--. | ,-->--v-->-------------->--v-->--. ,--NULL
585 // LiveRange LiveRange LiveRange
587 // ,--b->--' / `-->--b-->--' `--NULL
593 // LiveBundle --s-->- LiveBundle
596 // (spill) ^ ^ (spill)
601 // `--->---> SpillSet <--'
603 // --b-- LiveRange::bundleLink: links in the list of LiveRanges that belong to
606 // --v-- LiveRange::registerLink: links in the list of LiveRanges that belong
607 // to a VirtualRegister
609 // --s-- LiveBundle::spillParent: a possible link to my "spill parent bundle"
612 // * LiveRange is in the center. Each LiveRange is a member of two different
613 // linked lists, the --b-- list and the --v-- list.
615 // * VirtualRegister has a pointer `ranges` that points to the start of its
616 // --v-- list of LiveRanges.
618 // * LiveBundle has a pointer `ranges` that points to the start of its --b--
619 // list of LiveRanges.
621 // * LiveRange points back at both its owning VirtualRegister (`vreg`) and its
622 // owning LiveBundle (`bundle`).
624 // * LiveBundle has a pointer --s-- `spillParent`, which may be null, to its
625 // conceptual "spill parent bundle", as discussed in detail above.
627 // * LiveBundle has a pointer `spill` to its SpillSet.
629 // * SpillSet has a vector `list` of pointers back to the LiveBundles that
632 // * VirtualRegister has pointers `ins` to the LNode that defines the value and
633 // `def` to the LDefinition within that LNode.
635 // * BacktrackingAllocator has a vector `vregs` of pointers to all the
636 // VirtualRegisters for the function. There is no equivalent top-level table
637 // of all the LiveBundles for the function.
639 // Note that none of these pointers are "owning" in the C++-storage-management
640 // sense. Rather, everything is stored in single arena which is freed when
641 // compilation of the function is complete. For this reason,
642 // BacktrackingAllocator.{h,cpp} is almost completely free of the usual C++
643 // storage-management artefacts one would normally expect to see.
646 // ========================================================================
648 // ==== Section 2: The core allocation loop, and bundle splitting ====
650 // ========================================================================
652 // Phase 1 of the allocator (described at the start of this SMDOC) computes
653 // live ranges, merges them into bundles, and places the bundles in a priority
654 // queue ::allocationQueue, ordered by what ::computePriority computes.
657 // The allocation loops
658 // ~~~~~~~~~~~~~~~~~~~~
659 // The core of the allocation machinery consists of two loops followed by a
660 // call to ::pickStackSlots. The latter is uninteresting. The two loops live
661 // in ::go and are documented in detail there.
666 // If the first of the two abovementioned loops cannot find a register for a
667 // bundle, either directly or as a result of evicting conflicting bundles, then
668 // it will have to either split or spill the bundle. The entry point to the
669 // split/spill subsystem is ::chooseBundleSplit. See comments there.
671 ///////////////////////////////////////////////////////////////////////////////
673 // End of documentation //
675 ///////////////////////////////////////////////////////////////////////////////
677 #include "jit/BacktrackingAllocator.h"
681 #include "jit/BitSet.h"
682 #include "jit/CompileInfo.h"
683 #include "js/Printf.h"
686 using namespace js::jit
;
688 using mozilla::DebugOnly
;
690 // This is a big, complex file. Code is grouped into various sections, each
691 // preceded by a box comment. Sections not marked as "Misc helpers" are
692 // pretty much the top level flow, and are presented roughly in the same order
693 // in which the allocation pipeline operates. BacktrackingAllocator::go,
694 // right at the end of the file, is a good starting point.
696 ///////////////////////////////////////////////////////////////////////////////
698 // Misc helpers: linked-list management //
700 ///////////////////////////////////////////////////////////////////////////////
702 static inline bool SortBefore(UsePosition
* a
, UsePosition
* b
) {
703 return a
->pos
<= b
->pos
;
706 static inline bool SortBefore(LiveRange::BundleLink
* a
,
707 LiveRange::BundleLink
* b
) {
708 LiveRange
* rangea
= LiveRange::get(a
);
709 LiveRange
* rangeb
= LiveRange::get(b
);
710 MOZ_ASSERT(!rangea
->intersects(rangeb
));
711 return rangea
->from() < rangeb
->from();
714 static inline bool SortBefore(LiveRange::RegisterLink
* a
,
715 LiveRange::RegisterLink
* b
) {
716 return LiveRange::get(a
)->from() <= LiveRange::get(b
)->from();
719 template <typename T
>
720 static inline void InsertSortedList(InlineForwardList
<T
>& list
, T
* value
) {
722 list
.pushFront(value
);
726 if (SortBefore(list
.back(), value
)) {
727 list
.pushBack(value
);
732 for (InlineForwardListIterator
<T
> iter
= list
.begin(); iter
; iter
++) {
733 if (SortBefore(value
, *iter
)) {
740 list
.insertAfter(prev
, value
);
742 list
.pushFront(value
);
746 ///////////////////////////////////////////////////////////////////////////////
748 // Misc helpers: methods for class SpillSet //
750 ///////////////////////////////////////////////////////////////////////////////
752 void SpillSet::setAllocation(LAllocation alloc
) {
753 for (size_t i
= 0; i
< numSpilledBundles(); i
++) {
754 spilledBundle(i
)->setAllocation(alloc
);
758 ///////////////////////////////////////////////////////////////////////////////
760 // Misc helpers: methods for class LiveRange //
762 ///////////////////////////////////////////////////////////////////////////////
764 static size_t SpillWeightFromUsePolicy(LUse::Policy policy
) {
778 inline void LiveRange::noteAddedUse(UsePosition
* use
) {
779 LUse::Policy policy
= use
->usePolicy();
780 usesSpillWeight_
+= SpillWeightFromUsePolicy(policy
);
781 if (policy
== LUse::FIXED
) {
786 inline void LiveRange::noteRemovedUse(UsePosition
* use
) {
787 LUse::Policy policy
= use
->usePolicy();
788 usesSpillWeight_
-= SpillWeightFromUsePolicy(policy
);
789 if (policy
== LUse::FIXED
) {
792 MOZ_ASSERT_IF(!hasUses(), !usesSpillWeight_
&& !numFixedUses_
);
795 void LiveRange::addUse(UsePosition
* use
) {
796 MOZ_ASSERT(covers(use
->pos
));
797 InsertSortedList(uses_
, use
);
801 UsePosition
* LiveRange::popUse() {
802 UsePosition
* ret
= uses_
.popFront();
807 void LiveRange::tryToMoveDefAndUsesInto(LiveRange
* other
) {
808 MOZ_ASSERT(&other
->vreg() == &vreg());
809 MOZ_ASSERT(this != other
);
811 // Move over all uses which fit in |other|'s boundaries.
812 for (UsePositionIterator iter
= usesBegin(); iter
;) {
813 UsePosition
* use
= *iter
;
814 if (other
->covers(use
->pos
)) {
815 uses_
.removeAndIncrement(iter
);
823 // Distribute the definition to |other| as well, if possible.
824 if (hasDefinition() && from() == other
->from()) {
825 other
->setHasDefinition();
829 bool LiveRange::contains(LiveRange
* other
) const {
830 return from() <= other
->from() && to() >= other
->to();
833 void LiveRange::intersect(LiveRange
* other
, Range
* pre
, Range
* inside
,
835 MOZ_ASSERT(pre
->empty() && inside
->empty() && post
->empty());
837 CodePosition innerFrom
= from();
838 if (from() < other
->from()) {
839 if (to() < other
->from()) {
843 *pre
= Range(from(), other
->from());
844 innerFrom
= other
->from();
847 CodePosition innerTo
= to();
848 if (to() > other
->to()) {
849 if (from() >= other
->to()) {
853 *post
= Range(other
->to(), to());
854 innerTo
= other
->to();
857 if (innerFrom
!= innerTo
) {
858 *inside
= Range(innerFrom
, innerTo
);
862 bool LiveRange::intersects(LiveRange
* other
) const {
863 Range pre
, inside
, post
;
864 intersect(other
, &pre
, &inside
, &post
);
865 return !inside
.empty();
868 ///////////////////////////////////////////////////////////////////////////////
870 // Misc helpers: methods for class LiveBundle //
872 ///////////////////////////////////////////////////////////////////////////////
875 size_t LiveBundle::numRanges() const {
877 for (LiveRange::BundleLinkIterator iter
= rangesBegin(); iter
; iter
++) {
884 LiveRange
* LiveBundle::rangeFor(CodePosition pos
) const {
885 for (LiveRange::BundleLinkIterator iter
= rangesBegin(); iter
; iter
++) {
886 LiveRange
* range
= LiveRange::get(*iter
);
887 if (range
->covers(pos
)) {
894 void LiveBundle::addRange(LiveRange
* range
) {
895 MOZ_ASSERT(!range
->bundle());
896 range
->setBundle(this);
897 InsertSortedList(ranges_
, &range
->bundleLink
);
900 bool LiveBundle::addRange(TempAllocator
& alloc
, VirtualRegister
* vreg
,
901 CodePosition from
, CodePosition to
) {
902 LiveRange
* range
= LiveRange::FallibleNew(alloc
, vreg
, from
, to
);
910 bool LiveBundle::addRangeAndDistributeUses(TempAllocator
& alloc
,
912 CodePosition from
, CodePosition to
) {
913 LiveRange
* range
= LiveRange::FallibleNew(alloc
, &oldRange
->vreg(), from
, to
);
918 oldRange
->tryToMoveDefAndUsesInto(range
);
922 LiveRange
* LiveBundle::popFirstRange() {
923 LiveRange::BundleLinkIterator iter
= rangesBegin();
928 LiveRange
* range
= LiveRange::get(*iter
);
929 ranges_
.removeAt(iter
);
931 range
->setBundle(nullptr);
935 void LiveBundle::removeRange(LiveRange
* range
) {
936 for (LiveRange::BundleLinkIterator iter
= rangesBegin(); iter
; iter
++) {
937 LiveRange
* existing
= LiveRange::get(*iter
);
938 if (existing
== range
) {
939 ranges_
.removeAt(iter
);
946 ///////////////////////////////////////////////////////////////////////////////
948 // Misc helpers: methods for class VirtualRegister //
950 ///////////////////////////////////////////////////////////////////////////////
952 bool VirtualRegister::addInitialRange(TempAllocator
& alloc
, CodePosition from
,
953 CodePosition to
, size_t* numRanges
) {
954 MOZ_ASSERT(from
< to
);
956 // Mark [from,to) as a live range for this register during the initial
957 // liveness analysis, coalescing with any existing overlapping ranges.
959 // On some pathological graphs there might be a huge number of different
960 // live ranges. Allow non-overlapping live range to be merged if the
961 // number of ranges exceeds the cap below.
962 static const size_t CoalesceLimit
= 100000;
964 LiveRange
* prev
= nullptr;
965 LiveRange
* merged
= nullptr;
966 for (LiveRange::RegisterLinkIterator
iter(rangesBegin()); iter
;) {
967 LiveRange
* existing
= LiveRange::get(*iter
);
969 if (from
> existing
->to() && *numRanges
< CoalesceLimit
) {
970 // The new range should go after this one.
976 if (to
.next() < existing
->from()) {
977 // The new range should go before this one.
982 // This is the first old range we've found that overlaps the new
983 // range. Extend this one to cover its union with the new range.
986 if (from
< existing
->from()) {
987 existing
->setFrom(from
);
989 if (to
> existing
->to()) {
993 // Continue searching to see if any other old ranges can be
994 // coalesced with the new merged range.
999 // Coalesce this range into the previous range we merged into.
1000 MOZ_ASSERT(existing
->from() >= merged
->from());
1001 if (existing
->to() > merged
->to()) {
1002 merged
->setTo(existing
->to());
1005 MOZ_ASSERT(!existing
->hasDefinition());
1006 existing
->tryToMoveDefAndUsesInto(merged
);
1007 MOZ_ASSERT(!existing
->hasUses());
1009 ranges_
.removeAndIncrement(iter
);
1013 // The new range does not overlap any existing range for the vreg.
1014 LiveRange
* range
= LiveRange::FallibleNew(alloc
, this, from
, to
);
1020 ranges_
.insertAfter(&prev
->registerLink
, &range
->registerLink
);
1022 ranges_
.pushFront(&range
->registerLink
);
1031 void VirtualRegister::addInitialUse(UsePosition
* use
) {
1032 LiveRange::get(*rangesBegin())->addUse(use
);
1035 void VirtualRegister::setInitialDefinition(CodePosition from
) {
1036 LiveRange
* first
= LiveRange::get(*rangesBegin());
1037 MOZ_ASSERT(from
>= first
->from());
1038 first
->setFrom(from
);
1039 first
->setHasDefinition();
1042 LiveRange
* VirtualRegister::rangeFor(CodePosition pos
,
1043 bool preferRegister
/* = false */) const {
1044 LiveRange
* found
= nullptr;
1045 for (LiveRange::RegisterLinkIterator iter
= rangesBegin(); iter
; iter
++) {
1046 LiveRange
* range
= LiveRange::get(*iter
);
1047 if (range
->covers(pos
)) {
1048 if (!preferRegister
|| range
->bundle()->allocation().isRegister()) {
1059 void VirtualRegister::addRange(LiveRange
* range
) {
1060 InsertSortedList(ranges_
, &range
->registerLink
);
1063 void VirtualRegister::removeRange(LiveRange
* range
) {
1064 for (LiveRange::RegisterLinkIterator iter
= rangesBegin(); iter
; iter
++) {
1065 LiveRange
* existing
= LiveRange::get(*iter
);
1066 if (existing
== range
) {
1067 ranges_
.removeAt(iter
);
1074 ///////////////////////////////////////////////////////////////////////////////
1076 // Misc helpers: queries about uses //
1078 ///////////////////////////////////////////////////////////////////////////////
1080 static inline LDefinition
* FindReusingDefOrTemp(LNode
* node
,
1081 LAllocation
* alloc
) {
1082 if (node
->isPhi()) {
1083 MOZ_ASSERT(node
->toPhi()->numDefs() == 1);
1084 MOZ_ASSERT(node
->toPhi()->getDef(0)->policy() !=
1085 LDefinition::MUST_REUSE_INPUT
);
1089 LInstruction
* ins
= node
->toInstruction();
1091 for (size_t i
= 0; i
< ins
->numDefs(); i
++) {
1092 LDefinition
* def
= ins
->getDef(i
);
1093 if (def
->policy() == LDefinition::MUST_REUSE_INPUT
&&
1094 ins
->getOperand(def
->getReusedInput()) == alloc
) {
1098 for (size_t i
= 0; i
< ins
->numTemps(); i
++) {
1099 LDefinition
* def
= ins
->getTemp(i
);
1100 if (def
->policy() == LDefinition::MUST_REUSE_INPUT
&&
1101 ins
->getOperand(def
->getReusedInput()) == alloc
) {
1108 bool BacktrackingAllocator::isReusedInput(LUse
* use
, LNode
* ins
,
1109 bool considerCopy
) {
1110 if (LDefinition
* def
= FindReusingDefOrTemp(ins
, use
)) {
1111 return considerCopy
|| !vregs
[def
->virtualRegister()].mustCopyInput();
1116 bool BacktrackingAllocator::isRegisterUse(UsePosition
* use
, LNode
* ins
,
1117 bool considerCopy
) {
1118 switch (use
->usePolicy()) {
1120 return isReusedInput(use
->use(), ins
, considerCopy
);
1122 case LUse::REGISTER
:
1131 bool BacktrackingAllocator::isRegisterDefinition(LiveRange
* range
) {
1132 if (!range
->hasDefinition()) {
1136 VirtualRegister
& reg
= range
->vreg();
1137 if (reg
.ins()->isPhi()) {
1141 if (reg
.def()->policy() == LDefinition::FIXED
&&
1142 !reg
.def()->output()->isRegister()) {
1149 ///////////////////////////////////////////////////////////////////////////////
1151 // Misc helpers: atomic LIR groups //
1153 ///////////////////////////////////////////////////////////////////////////////
1155 // The following groupings contain implicit (invisible to ::buildLivenessInfo)
1156 // value flows, and therefore no split points may be requested inside them.
1157 // This is an otherwise unstated part of the contract between LIR generation
1158 // and the allocator.
1160 // (1) (any insn) ; OsiPoint
1162 // [Further group definitions and supporting code to come, pending rework
1163 // of the wasm atomic-group situation.]
1165 CodePosition
RegisterAllocator::minimalDefEnd(LNode
* ins
) const {
1166 // Compute the shortest interval that captures vregs defined by ins.
1167 // Watch for instructions that are followed by an OSI point.
1168 // If moves are introduced between the instruction and the OSI point then
1169 // safepoint information for the instruction may be incorrect.
1171 LNode
* next
= insData
[ins
->id() + 1];
1172 if (!next
->isOsiPoint()) {
1178 return outputOf(ins
);
1181 ///////////////////////////////////////////////////////////////////////////////
1183 // Misc helpers: computation of bundle priorities and spill weights //
1185 ///////////////////////////////////////////////////////////////////////////////
1187 size_t BacktrackingAllocator::computePriority(LiveBundle
* bundle
) {
1188 // The priority of a bundle is its total length, so that longer lived
1189 // bundles will be processed before shorter ones (even if the longer ones
1190 // have a low spill weight). See processBundle().
1191 size_t lifetimeTotal
= 0;
1193 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
1195 LiveRange
* range
= LiveRange::get(*iter
);
1196 lifetimeTotal
+= range
->to() - range
->from();
1199 return lifetimeTotal
;
1202 bool BacktrackingAllocator::minimalDef(LiveRange
* range
, LNode
* ins
) {
1203 // Whether this is a minimal range capturing a definition at ins.
1204 return (range
->to() <= minimalDefEnd(ins
).next()) &&
1205 ((!ins
->isPhi() && range
->from() == inputOf(ins
)) ||
1206 range
->from() == outputOf(ins
));
1209 bool BacktrackingAllocator::minimalUse(LiveRange
* range
, UsePosition
* use
) {
1210 // Whether this is a minimal range capturing |use|.
1211 LNode
* ins
= insData
[use
->pos
];
1212 return (range
->from() == inputOf(ins
)) &&
1214 (use
->use()->usedAtStart() ? outputOf(ins
) : outputOf(ins
).next()));
1217 bool BacktrackingAllocator::minimalBundle(LiveBundle
* bundle
, bool* pfixed
) {
1218 LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin();
1219 LiveRange
* range
= LiveRange::get(*iter
);
1221 if (!range
->hasVreg()) {
1226 // If a bundle contains multiple ranges, splitAtAllRegisterUses will split
1227 // each range into a separate bundle.
1232 if (range
->hasDefinition()) {
1233 VirtualRegister
& reg
= range
->vreg();
1235 *pfixed
= reg
.def()->policy() == LDefinition::FIXED
&&
1236 reg
.def()->output()->isRegister();
1238 return minimalDef(range
, reg
.ins());
1241 bool fixed
= false, minimal
= false, multiple
= false;
1243 for (UsePositionIterator iter
= range
->usesBegin(); iter
; iter
++) {
1244 if (iter
!= range
->usesBegin()) {
1248 switch (iter
->usePolicy()) {
1254 if (minimalUse(range
, *iter
)) {
1259 case LUse::REGISTER
:
1260 if (minimalUse(range
, *iter
)) {
1270 // If a range contains a fixed use and at least one other use,
1271 // splitAtAllRegisterUses will split each use into a different bundle.
1272 if (multiple
&& fixed
) {
1282 size_t BacktrackingAllocator::computeSpillWeight(LiveBundle
* bundle
) {
1283 // Minimal bundles have an extremely high spill weight, to ensure they
1284 // can evict any other bundles and be allocated to a register.
1286 if (minimalBundle(bundle
, &fixed
)) {
1287 return fixed
? 2000000 : 1000000;
1290 size_t usesTotal
= 0;
1293 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
1295 LiveRange
* range
= LiveRange::get(*iter
);
1297 if (range
->hasDefinition()) {
1298 VirtualRegister
& reg
= range
->vreg();
1299 if (reg
.def()->policy() == LDefinition::FIXED
&&
1300 reg
.def()->output()->isRegister()) {
1303 } else if (!reg
.ins()->isPhi()) {
1308 usesTotal
+= range
->usesSpillWeight();
1309 if (range
->numFixedUses() > 0) {
1314 // Bundles with fixed uses are given a higher spill weight, since they must
1315 // be allocated to a specific register.
1316 if (testbed
&& fixed
) {
1320 // Compute spill weight as a use density, lowering the weight for long
1321 // lived bundles with relatively few uses.
1322 size_t lifetimeTotal
= computePriority(bundle
);
1323 return lifetimeTotal
? usesTotal
/ lifetimeTotal
: 0;
1326 size_t BacktrackingAllocator::maximumSpillWeight(
1327 const LiveBundleVector
& bundles
) {
1328 size_t maxWeight
= 0;
1329 for (size_t i
= 0; i
< bundles
.length(); i
++) {
1330 maxWeight
= std::max(maxWeight
, computeSpillWeight(bundles
[i
]));
1335 ///////////////////////////////////////////////////////////////////////////////
1337 // Initialization of the allocator //
1339 ///////////////////////////////////////////////////////////////////////////////
1341 // This function pre-allocates and initializes as much global state as possible
1342 // to avoid littering the algorithms with memory management cruft.
1343 bool BacktrackingAllocator::init() {
1344 if (!RegisterAllocator::init()) {
1348 liveIn
= mir
->allocate
<BitSet
>(graph
.numBlockIds());
1353 size_t numVregs
= graph
.numVirtualRegisters();
1354 if (!vregs
.init(mir
->alloc(), numVregs
)) {
1357 for (uint32_t i
= 0; i
< numVregs
; i
++) {
1358 new (&vregs
[i
]) VirtualRegister();
1361 // Build virtual register objects.
1362 for (size_t i
= 0; i
< graph
.numBlocks(); i
++) {
1363 if (mir
->shouldCancel("Create data structures (main loop)")) {
1367 LBlock
* block
= graph
.getBlock(i
);
1368 for (LInstructionIterator ins
= block
->begin(); ins
!= block
->end();
1370 if (mir
->shouldCancel("Create data structures (inner loop 1)")) {
1374 for (size_t j
= 0; j
< ins
->numDefs(); j
++) {
1375 LDefinition
* def
= ins
->getDef(j
);
1376 if (def
->isBogusTemp()) {
1379 vreg(def
).init(*ins
, def
, /* isTemp = */ false);
1382 for (size_t j
= 0; j
< ins
->numTemps(); j
++) {
1383 LDefinition
* def
= ins
->getTemp(j
);
1384 if (def
->isBogusTemp()) {
1387 vreg(def
).init(*ins
, def
, /* isTemp = */ true);
1390 for (size_t j
= 0; j
< block
->numPhis(); j
++) {
1391 LPhi
* phi
= block
->getPhi(j
);
1392 LDefinition
* def
= phi
->getDef(0);
1393 vreg(def
).init(phi
, def
, /* isTemp = */ false);
1397 LiveRegisterSet
remainingRegisters(allRegisters_
.asLiveSet());
1398 while (!remainingRegisters
.emptyGeneral()) {
1399 AnyRegister reg
= AnyRegister(remainingRegisters
.takeAnyGeneral());
1400 registers
[reg
.code()].allocatable
= true;
1402 while (!remainingRegisters
.emptyFloat()) {
1404 AnyRegister(remainingRegisters
.takeAnyFloat
<RegTypeName::Any
>());
1405 registers
[reg
.code()].allocatable
= true;
1408 LifoAlloc
* lifoAlloc
= mir
->alloc().lifoAlloc();
1409 for (size_t i
= 0; i
< AnyRegister::Total
; i
++) {
1410 registers
[i
].reg
= AnyRegister::FromCode(i
);
1411 registers
[i
].allocations
.setAllocator(lifoAlloc
);
1414 hotcode
.setAllocator(lifoAlloc
);
1415 callRanges
.setAllocator(lifoAlloc
);
1417 // Partition the graph into hot and cold sections, for helping to make
1418 // splitting decisions. Since we don't have any profiling data this is a
1419 // crapshoot, so just mark the bodies of inner loops as hot and everything
1422 LBlock
* backedge
= nullptr;
1423 for (size_t i
= 0; i
< graph
.numBlocks(); i
++) {
1424 LBlock
* block
= graph
.getBlock(i
);
1426 // If we see a loop header, mark the backedge so we know when we have
1427 // hit the end of the loop. Don't process the loop immediately, so that
1428 // if there is an inner loop we will ignore the outer backedge.
1429 if (block
->mir()->isLoopHeader()) {
1430 backedge
= block
->mir()->backedge()->lir();
1433 if (block
== backedge
) {
1434 LBlock
* header
= block
->mir()->loopHeaderOfBackedge()->lir();
1435 LiveRange
* range
= LiveRange::FallibleNew(
1436 alloc(), nullptr, entryOf(header
), exitOf(block
).next());
1437 if (!range
|| !hotcode
.insert(range
)) {
1446 ///////////////////////////////////////////////////////////////////////////////
1448 // Liveness analysis //
1450 ///////////////////////////////////////////////////////////////////////////////
1452 // Helper for ::buildLivenessInfo
1453 bool BacktrackingAllocator::addInitialFixedRange(AnyRegister reg
,
1456 LiveRange
* range
= LiveRange::FallibleNew(alloc(), nullptr, from
, to
);
1460 LiveRangePlus
rangePlus(range
);
1461 return registers
[reg
.code()].allocations
.insert(rangePlus
);
1464 // Helper for ::buildLivenessInfo
1466 // Returns true iff ins has a def/temp reusing the input allocation.
1467 static bool IsInputReused(LInstruction
* ins
, LUse
* use
) {
1468 for (size_t i
= 0; i
< ins
->numDefs(); i
++) {
1469 if (ins
->getDef(i
)->policy() == LDefinition::MUST_REUSE_INPUT
&&
1470 ins
->getOperand(ins
->getDef(i
)->getReusedInput())->toUse() == use
) {
1475 for (size_t i
= 0; i
< ins
->numTemps(); i
++) {
1476 if (ins
->getTemp(i
)->policy() == LDefinition::MUST_REUSE_INPUT
&&
1477 ins
->getOperand(ins
->getTemp(i
)->getReusedInput())->toUse() == use
) {
1487 * This function builds up liveness ranges for all virtual registers
1488 * defined in the function.
1490 * The algorithm is based on the one published in:
1492 * Wimmer, Christian, and Michael Franz. "Linear Scan Register Allocation on
1493 * SSA Form." Proceedings of the International Symposium on Code Generation
1494 * and Optimization. Toronto, Ontario, Canada, ACM. 2010. 170-79. PDF.
1496 * The algorithm operates on blocks ordered such that dominators of a block
1497 * are before the block itself, and such that all blocks of a loop are
1498 * contiguous. It proceeds backwards over the instructions in this order,
1499 * marking registers live at their uses, ending their live ranges at
1500 * definitions, and recording which registers are live at the top of every
1501 * block. To deal with loop backedges, registers live at the beginning of
1502 * a loop gain a range covering the entire loop.
1504 bool BacktrackingAllocator::buildLivenessInfo() {
1505 JitSpew(JitSpew_RegAlloc
, "Beginning liveness analysis");
1507 Vector
<MBasicBlock
*, 1, SystemAllocPolicy
> loopWorkList
;
1508 BitSet
loopDone(graph
.numBlockIds());
1509 if (!loopDone
.init(alloc())) {
1513 size_t numRanges
= 0;
1515 for (size_t i
= graph
.numBlocks(); i
> 0; i
--) {
1516 if (mir
->shouldCancel("Build Liveness Info (main loop)")) {
1520 LBlock
* block
= graph
.getBlock(i
- 1);
1521 MBasicBlock
* mblock
= block
->mir();
1523 BitSet
& live
= liveIn
[mblock
->id()];
1524 new (&live
) BitSet(graph
.numVirtualRegisters());
1525 if (!live
.init(alloc())) {
1529 // Propagate liveIn from our successors to us.
1530 for (size_t i
= 0; i
< mblock
->lastIns()->numSuccessors(); i
++) {
1531 MBasicBlock
* successor
= mblock
->lastIns()->getSuccessor(i
);
1532 // Skip backedges, as we fix them up at the loop header.
1533 if (mblock
->id() < successor
->id()) {
1534 live
.insertAll(liveIn
[successor
->id()]);
1538 // Add successor phis.
1539 if (mblock
->successorWithPhis()) {
1540 LBlock
* phiSuccessor
= mblock
->successorWithPhis()->lir();
1541 for (unsigned int j
= 0; j
< phiSuccessor
->numPhis(); j
++) {
1542 LPhi
* phi
= phiSuccessor
->getPhi(j
);
1543 LAllocation
* use
= phi
->getOperand(mblock
->positionInPhiSuccessor());
1544 uint32_t reg
= use
->toUse()->virtualRegister();
1546 vreg(use
).setUsedByPhi();
1550 // Registers are assumed alive for the entire block, a define shortens
1551 // the range to the point of definition.
1552 for (BitSet::Iterator
liveRegId(live
); liveRegId
; ++liveRegId
) {
1553 if (!vregs
[*liveRegId
].addInitialRange(alloc(), entryOf(block
),
1554 exitOf(block
).next(), &numRanges
))
1558 // Shorten the front end of ranges for live variables to their point of
1559 // definition, if found.
1560 for (LInstructionReverseIterator ins
= block
->rbegin();
1561 ins
!= block
->rend(); ins
++) {
1562 // Calls may clobber registers, so force a spill and reload around the
1564 if (ins
->isCall()) {
1565 for (AnyRegisterIterator
iter(allRegisters_
.asLiveSet()); iter
.more();
1568 for (size_t i
= 0; i
< ins
->numDefs(); i
++) {
1569 if (ins
->getDef(i
)->isFixed() &&
1570 ins
->getDef(i
)->output()->aliases(LAllocation(*iter
))) {
1575 // If this register doesn't have an explicit def above, mark
1576 // it as clobbered by the call unless it is actually
1578 if (!found
&& !ins
->isCallPreserved(*iter
)) {
1579 if (!addInitialFixedRange(*iter
, outputOf(*ins
),
1580 outputOf(*ins
).next())) {
1586 CallRange
* callRange
= new (alloc().fallible())
1587 CallRange(outputOf(*ins
), outputOf(*ins
).next());
1592 callRangesList
.pushFront(callRange
);
1593 if (!callRanges
.insert(callRange
)) {
1598 for (size_t i
= 0; i
< ins
->numDefs(); i
++) {
1599 LDefinition
* def
= ins
->getDef(i
);
1600 if (def
->isBogusTemp()) {
1604 CodePosition from
= outputOf(*ins
);
1606 if (def
->policy() == LDefinition::MUST_REUSE_INPUT
) {
1607 // MUST_REUSE_INPUT is implemented by allocating an output
1608 // register and moving the input to it. Register hints are
1609 // used to avoid unnecessary moves. We give the input an
1610 // LUse::ANY policy to avoid allocating a register for the
1612 LUse
* inputUse
= ins
->getOperand(def
->getReusedInput())->toUse();
1613 MOZ_ASSERT(inputUse
->policy() == LUse::REGISTER
);
1614 MOZ_ASSERT(inputUse
->usedAtStart());
1615 *inputUse
= LUse(inputUse
->virtualRegister(), LUse::ANY
,
1616 /* usedAtStart = */ true);
1619 if (!vreg(def
).addInitialRange(alloc(), from
, from
.next(),
1623 vreg(def
).setInitialDefinition(from
);
1624 live
.remove(def
->virtualRegister());
1627 for (size_t i
= 0; i
< ins
->numTemps(); i
++) {
1628 LDefinition
* temp
= ins
->getTemp(i
);
1629 if (temp
->isBogusTemp()) {
1633 // Normally temps are considered to cover both the input
1634 // and output of the associated instruction. In some cases
1635 // though we want to use a fixed register as both an input
1636 // and clobbered register in the instruction, so watch for
1637 // this and shorten the temp to cover only the output.
1638 CodePosition from
= inputOf(*ins
);
1639 if (temp
->policy() == LDefinition::FIXED
) {
1640 AnyRegister reg
= temp
->output()->toRegister();
1641 for (LInstruction::InputIterator
alloc(**ins
); alloc
.more();
1643 if (alloc
->isUse()) {
1644 LUse
* use
= alloc
->toUse();
1645 if (use
->isFixedRegister()) {
1646 if (GetFixedRegister(vreg(use
).def(), use
) == reg
) {
1647 from
= outputOf(*ins
);
1654 // * For non-call instructions, temps cover both the input and output,
1655 // so temps never alias uses (even at-start uses) or defs.
1656 // * For call instructions, temps only cover the input (the output is
1657 // used for the force-spill ranges added above). This means temps
1658 // still don't alias uses but they can alias the (fixed) defs. For now
1659 // we conservatively require temps to have a fixed register for call
1660 // instructions to prevent a footgun.
1661 MOZ_ASSERT_IF(ins
->isCall(), temp
->policy() == LDefinition::FIXED
);
1663 ins
->isCall() ? outputOf(*ins
) : outputOf(*ins
).next();
1665 if (!vreg(temp
).addInitialRange(alloc(), from
, to
, &numRanges
)) {
1668 vreg(temp
).setInitialDefinition(from
);
1671 DebugOnly
<bool> hasUseRegister
= false;
1672 DebugOnly
<bool> hasUseRegisterAtStart
= false;
1674 for (LInstruction::InputIterator
inputAlloc(**ins
); inputAlloc
.more();
1675 inputAlloc
.next()) {
1676 if (inputAlloc
->isUse()) {
1677 LUse
* use
= inputAlloc
->toUse();
1679 // Call uses should always be at-start, since calls use all
1681 MOZ_ASSERT_IF(ins
->isCall() && !inputAlloc
.isSnapshotInput(),
1682 use
->usedAtStart());
1685 // If there are both useRegisterAtStart(x) and useRegister(y)
1686 // uses, we may assign the same register to both operands
1687 // (bug 772830). Don't allow this for now.
1688 if (use
->policy() == LUse::REGISTER
) {
1689 if (use
->usedAtStart()) {
1690 if (!IsInputReused(*ins
, use
)) {
1691 hasUseRegisterAtStart
= true;
1694 hasUseRegister
= true;
1697 MOZ_ASSERT(!(hasUseRegister
&& hasUseRegisterAtStart
));
1700 // Don't treat RECOVERED_INPUT uses as keeping the vreg alive.
1701 if (use
->policy() == LUse::RECOVERED_INPUT
) {
1705 CodePosition to
= use
->usedAtStart() ? inputOf(*ins
) : outputOf(*ins
);
1706 if (use
->isFixedRegister()) {
1707 LAllocation
reg(AnyRegister::FromCode(use
->registerCode()));
1708 for (size_t i
= 0; i
< ins
->numDefs(); i
++) {
1709 LDefinition
* def
= ins
->getDef(i
);
1710 if (def
->policy() == LDefinition::FIXED
&&
1711 *def
->output() == reg
) {
1717 if (!vreg(use
).addInitialRange(alloc(), entryOf(block
), to
.next(),
1721 UsePosition
* usePosition
=
1722 new (alloc().fallible()) UsePosition(use
, to
);
1726 vreg(use
).addInitialUse(usePosition
);
1727 live
.insert(use
->virtualRegister());
1732 // Phis have simultaneous assignment semantics at block begin, so at
1733 // the beginning of the block we can be sure that liveIn does not
1734 // contain any phi outputs.
1735 for (unsigned int i
= 0; i
< block
->numPhis(); i
++) {
1736 LDefinition
* def
= block
->getPhi(i
)->getDef(0);
1737 if (live
.contains(def
->virtualRegister())) {
1738 live
.remove(def
->virtualRegister());
1740 // This is a dead phi, so add a dummy range over all phis. This
1741 // can go away if we have an earlier dead code elimination pass.
1742 CodePosition entryPos
= entryOf(block
);
1743 if (!vreg(def
).addInitialRange(alloc(), entryPos
, entryPos
.next(),
1750 if (mblock
->isLoopHeader()) {
1751 // A divergence from the published algorithm is required here, as
1752 // our block order does not guarantee that blocks of a loop are
1753 // contiguous. As a result, a single live range spanning the
1754 // loop is not possible. Additionally, we require liveIn in a later
1755 // pass for resolution, so that must also be fixed up here.
1756 MBasicBlock
* loopBlock
= mblock
->backedge();
1758 // Blocks must already have been visited to have a liveIn set.
1759 MOZ_ASSERT(loopBlock
->id() >= mblock
->id());
1761 // Add a range for this entire loop block
1762 CodePosition from
= entryOf(loopBlock
->lir());
1763 CodePosition to
= exitOf(loopBlock
->lir()).next();
1765 for (BitSet::Iterator
liveRegId(live
); liveRegId
; ++liveRegId
) {
1766 if (!vregs
[*liveRegId
].addInitialRange(alloc(), from
, to
,
1772 // Fix up the liveIn set.
1773 liveIn
[loopBlock
->id()].insertAll(live
);
1775 // Make sure we don't visit this node again
1776 loopDone
.insert(loopBlock
->id());
1778 // If this is the loop header, any predecessors are either the
1779 // backedge or out of the loop, so skip any predecessors of
1781 if (loopBlock
!= mblock
) {
1782 for (size_t i
= 0; i
< loopBlock
->numPredecessors(); i
++) {
1783 MBasicBlock
* pred
= loopBlock
->getPredecessor(i
);
1784 if (loopDone
.contains(pred
->id())) {
1787 if (!loopWorkList
.append(pred
)) {
1793 // Terminate loop if out of work.
1794 if (loopWorkList
.empty()) {
1798 // Grab the next block off the work list, skipping any OSR block.
1799 MBasicBlock
* osrBlock
= graph
.mir().osrBlock();
1800 while (!loopWorkList
.empty()) {
1801 loopBlock
= loopWorkList
.popCopy();
1802 if (loopBlock
!= osrBlock
) {
1807 // If end is reached without finding a non-OSR block, then no more work
1808 // items were found.
1809 if (loopBlock
== osrBlock
) {
1810 MOZ_ASSERT(loopWorkList
.empty());
1815 // Clear the done set for other loops
1819 MOZ_ASSERT_IF(!mblock
->numPredecessors(), live
.empty());
1822 JitSpew(JitSpew_RegAlloc
, "Completed liveness analysis");
1826 ///////////////////////////////////////////////////////////////////////////////
1828 // Merging and queueing of LiveRange groups //
1830 ///////////////////////////////////////////////////////////////////////////////
1832 // Helper for ::tryMergeBundles
1833 static bool IsArgumentSlotDefinition(LDefinition
* def
) {
1834 return def
->policy() == LDefinition::FIXED
&& def
->output()->isArgument();
1837 // Helper for ::tryMergeBundles
1838 static bool IsThisSlotDefinition(LDefinition
* def
) {
1839 return IsArgumentSlotDefinition(def
) &&
1840 def
->output()->toArgument()->index() <
1841 THIS_FRAME_ARGSLOT
+ sizeof(Value
);
1844 // Helper for ::tryMergeBundles
1845 static bool HasStackPolicy(LDefinition
* def
) {
1846 return def
->policy() == LDefinition::STACK
;
1849 // Helper for ::tryMergeBundles
1850 static bool CanMergeTypesInBundle(LDefinition::Type a
, LDefinition::Type b
) {
1851 // Fast path for the common case.
1856 // Only merge if the sizes match, so that we don't get confused about the
1857 // width of spill slots.
1858 return StackSlotAllocator::width(a
) == StackSlotAllocator::width(b
);
1861 // Helper for ::tryMergeReusedRegister
1862 bool BacktrackingAllocator::tryMergeBundles(LiveBundle
* bundle0
,
1863 LiveBundle
* bundle1
) {
1864 // See if bundle0 and bundle1 can be merged together.
1865 if (bundle0
== bundle1
) {
1869 // Get a representative virtual register from each bundle.
1870 VirtualRegister
& reg0
= bundle0
->firstRange()->vreg();
1871 VirtualRegister
& reg1
= bundle1
->firstRange()->vreg();
1873 MOZ_ASSERT(CanMergeTypesInBundle(reg0
.type(), reg1
.type()));
1874 MOZ_ASSERT(reg0
.isCompatible(reg1
));
1876 // Registers which might spill to the frame's |this| slot can only be
1877 // grouped with other such registers. The frame's |this| slot must always
1878 // hold the |this| value, as required by JitFrame tracing and by the Ion
1879 // constructor calling convention.
1880 if (IsThisSlotDefinition(reg0
.def()) || IsThisSlotDefinition(reg1
.def())) {
1881 if (*reg0
.def()->output() != *reg1
.def()->output()) {
1886 // Registers which might spill to the frame's argument slots can only be
1887 // grouped with other such registers if the frame might access those
1888 // arguments through a lazy arguments object or rest parameter.
1889 if (IsArgumentSlotDefinition(reg0
.def()) ||
1890 IsArgumentSlotDefinition(reg1
.def())) {
1891 if (graph
.mir().entryBlock()->info().mayReadFrameArgsDirectly()) {
1892 if (*reg0
.def()->output() != *reg1
.def()->output()) {
1898 // When we make a call to a WebAssembly function that returns multiple
1899 // results, some of those results can go on the stack. The callee is passed a
1900 // pointer to this stack area, which is represented as having policy
1901 // LDefinition::STACK (with type LDefinition::STACKRESULTS). Individual
1902 // results alias parts of the stack area with a value-appropriate type, but
1903 // policy LDefinition::STACK. This aliasing between allocations makes it
1904 // unsound to merge anything with a LDefinition::STACK policy.
1905 if (HasStackPolicy(reg0
.def()) || HasStackPolicy(reg1
.def())) {
1909 // Limit the number of times we compare ranges if there are many ranges in
1910 // one of the bundles, to avoid quadratic behavior.
1911 static const size_t MAX_RANGES
= 200;
1913 // Make sure that ranges in the bundles do not overlap.
1914 LiveRange::BundleLinkIterator iter0
= bundle0
->rangesBegin(),
1915 iter1
= bundle1
->rangesBegin();
1917 while (iter0
&& iter1
) {
1918 if (++count
>= MAX_RANGES
) {
1922 LiveRange
* range0
= LiveRange::get(*iter0
);
1923 LiveRange
* range1
= LiveRange::get(*iter1
);
1925 if (range0
->from() >= range1
->to()) {
1927 } else if (range1
->from() >= range0
->to()) {
1934 // Move all ranges from bundle1 into bundle0.
1935 while (LiveRange
* range
= bundle1
->popFirstRange()) {
1936 bundle0
->addRange(range
);
1942 // Helper for ::mergeAndQueueRegisters
1943 void BacktrackingAllocator::allocateStackDefinition(VirtualRegister
& reg
) {
1944 LInstruction
* ins
= reg
.ins()->toInstruction();
1945 if (reg
.def()->type() == LDefinition::STACKRESULTS
) {
1946 LStackArea
alloc(ins
->toInstruction());
1947 stackSlotAllocator
.allocateStackArea(&alloc
);
1948 reg
.def()->setOutput(alloc
);
1950 // Because the definitions are visited in order, the area has been allocated
1951 // before we reach this result, so we know the operand is an LStackArea.
1952 const LUse
* use
= ins
->getOperand(0)->toUse();
1953 VirtualRegister
& area
= vregs
[use
->virtualRegister()];
1954 const LStackArea
* areaAlloc
= area
.def()->output()->toStackArea();
1955 reg
.def()->setOutput(areaAlloc
->resultAlloc(ins
, reg
.def()));
1959 // Helper for ::mergeAndQueueRegisters
1960 bool BacktrackingAllocator::tryMergeReusedRegister(VirtualRegister
& def
,
1961 VirtualRegister
& input
) {
1962 // def is a vreg which reuses input for its output physical register. Try
1963 // to merge ranges for def with those of input if possible, as avoiding
1964 // copies before def's instruction is crucial for generated code quality
1965 // (MUST_REUSE_INPUT is used for all arithmetic on x86/x64).
1967 if (def
.rangeFor(inputOf(def
.ins()))) {
1968 MOZ_ASSERT(def
.isTemp());
1969 def
.setMustCopyInput();
1973 if (!CanMergeTypesInBundle(def
.type(), input
.type())) {
1974 def
.setMustCopyInput();
1978 LiveRange
* inputRange
= input
.rangeFor(outputOf(def
.ins()));
1980 // The input is not live after the instruction, either in a safepoint
1981 // for the instruction or in subsequent code. The input and output
1982 // can thus be in the same group.
1983 return tryMergeBundles(def
.firstBundle(), input
.firstBundle());
1986 // Avoid merging in very large live ranges as merging has non-linear
1987 // complexity. The cutoff value is hard to gauge. 1M was chosen because it
1988 // is "large" and yet usefully caps compile time on AutoCad-for-the-web to
1989 // something reasonable on a 2017-era desktop system.
1990 const uint32_t RANGE_SIZE_CUTOFF
= 1000000;
1991 if (inputRange
->to() - inputRange
->from() > RANGE_SIZE_CUTOFF
) {
1992 def
.setMustCopyInput();
1996 // The input is live afterwards, either in future instructions or in a
1997 // safepoint for the reusing instruction. This is impossible to satisfy
1998 // without copying the input.
2000 // It may or may not be better to split the input into two bundles at the
2001 // point of the definition, which may permit merging. One case where it is
2002 // definitely better to split is if the input never has any register uses
2003 // after the instruction. Handle this splitting eagerly.
2005 LBlock
* block
= def
.ins()->block();
2007 // The input's lifetime must end within the same block as the definition,
2008 // otherwise it could live on in phis elsewhere.
2009 if (inputRange
!= input
.lastRange() || inputRange
->to() > exitOf(block
)) {
2010 def
.setMustCopyInput();
2014 // If we already split the input for some other register, don't make a
2016 if (inputRange
->bundle() != input
.firstRange()->bundle()) {
2017 def
.setMustCopyInput();
2021 // If the input will start out in memory then adding a separate bundle for
2022 // memory uses after the def won't help.
2023 if (input
.def()->isFixed() && !input
.def()->output()->isRegister()) {
2024 def
.setMustCopyInput();
2028 // The input cannot have register or reused uses after the definition.
2029 for (UsePositionIterator iter
= inputRange
->usesBegin(); iter
; iter
++) {
2030 if (iter
->pos
<= inputOf(def
.ins())) {
2034 LUse
* use
= iter
->use();
2035 if (FindReusingDefOrTemp(insData
[iter
->pos
], use
)) {
2036 def
.setMustCopyInput();
2039 if (iter
->usePolicy() != LUse::ANY
&&
2040 iter
->usePolicy() != LUse::KEEPALIVE
) {
2041 def
.setMustCopyInput();
2046 LiveRange
* preRange
= LiveRange::FallibleNew(
2047 alloc(), &input
, inputRange
->from(), outputOf(def
.ins()));
2052 // The new range starts at reg's input position, which means it overlaps
2053 // with the old range at one position. This is what we want, because we
2054 // need to copy the input before the instruction.
2055 LiveRange
* postRange
= LiveRange::FallibleNew(
2056 alloc(), &input
, inputOf(def
.ins()), inputRange
->to());
2061 inputRange
->tryToMoveDefAndUsesInto(preRange
);
2062 inputRange
->tryToMoveDefAndUsesInto(postRange
);
2063 MOZ_ASSERT(!inputRange
->hasUses());
2065 JitSpewIfEnabled(JitSpew_RegAlloc
,
2066 " splitting reused input at %u to try to help grouping",
2067 inputOf(def
.ins()).bits());
2069 LiveBundle
* firstBundle
= inputRange
->bundle();
2070 input
.removeRange(inputRange
);
2071 input
.addRange(preRange
);
2072 input
.addRange(postRange
);
2074 firstBundle
->removeRange(inputRange
);
2075 firstBundle
->addRange(preRange
);
2077 // The new range goes in a separate bundle, where it will be spilled during
2079 LiveBundle
* secondBundle
= LiveBundle::FallibleNew(alloc(), nullptr, nullptr);
2080 if (!secondBundle
) {
2083 secondBundle
->addRange(postRange
);
2085 return tryMergeBundles(def
.firstBundle(), input
.firstBundle());
2088 bool BacktrackingAllocator::mergeAndQueueRegisters() {
2089 MOZ_ASSERT(!vregs
[0u].hasRanges());
2091 // Create a bundle for each register containing all its ranges.
2092 for (size_t i
= 1; i
< graph
.numVirtualRegisters(); i
++) {
2093 VirtualRegister
& reg
= vregs
[i
];
2094 if (!reg
.hasRanges()) {
2098 LiveBundle
* bundle
= LiveBundle::FallibleNew(alloc(), nullptr, nullptr);
2102 for (LiveRange::RegisterLinkIterator iter
= reg
.rangesBegin(); iter
;
2104 LiveRange
* range
= LiveRange::get(*iter
);
2105 bundle
->addRange(range
);
2109 // If there is an OSR block, merge parameters in that block with the
2110 // corresponding parameters in the initial block.
2111 if (MBasicBlock
* osr
= graph
.mir().osrBlock()) {
2112 size_t original
= 1;
2113 for (LInstructionIterator iter
= osr
->lir()->begin();
2114 iter
!= osr
->lir()->end(); iter
++) {
2115 if (iter
->isParameter()) {
2116 for (size_t i
= 0; i
< iter
->numDefs(); i
++) {
2117 DebugOnly
<bool> found
= false;
2118 VirtualRegister
& paramVreg
= vreg(iter
->getDef(i
));
2119 for (; original
< paramVreg
.vreg(); original
++) {
2120 VirtualRegister
& originalVreg
= vregs
[original
];
2121 if (*originalVreg
.def()->output() == *iter
->getDef(i
)->output()) {
2122 MOZ_ASSERT(originalVreg
.ins()->isParameter());
2123 if (!tryMergeBundles(originalVreg
.firstBundle(),
2124 paramVreg
.firstBundle())) {
2137 // Try to merge registers with their reused inputs.
2138 for (size_t i
= 1; i
< graph
.numVirtualRegisters(); i
++) {
2139 VirtualRegister
& reg
= vregs
[i
];
2140 if (!reg
.hasRanges()) {
2144 if (reg
.def()->policy() == LDefinition::MUST_REUSE_INPUT
) {
2145 LUse
* use
= reg
.ins()
2147 ->getOperand(reg
.def()->getReusedInput())
2149 if (!tryMergeReusedRegister(reg
, vreg(use
))) {
2155 // Try to merge phis with their inputs.
2156 for (size_t i
= 0; i
< graph
.numBlocks(); i
++) {
2157 LBlock
* block
= graph
.getBlock(i
);
2158 for (size_t j
= 0; j
< block
->numPhis(); j
++) {
2159 LPhi
* phi
= block
->getPhi(j
);
2160 VirtualRegister
& outputVreg
= vreg(phi
->getDef(0));
2161 for (size_t k
= 0, kend
= phi
->numOperands(); k
< kend
; k
++) {
2162 VirtualRegister
& inputVreg
= vreg(phi
->getOperand(k
)->toUse());
2163 if (!tryMergeBundles(inputVreg
.firstBundle(),
2164 outputVreg
.firstBundle())) {
2171 // Add all bundles to the allocation queue, and create spill sets for them.
2172 for (size_t i
= 1; i
< graph
.numVirtualRegisters(); i
++) {
2173 VirtualRegister
& reg
= vregs
[i
];
2175 // Eagerly allocate stack result areas and their component stack results.
2176 if (reg
.def() && reg
.def()->policy() == LDefinition::STACK
) {
2177 allocateStackDefinition(reg
);
2180 for (LiveRange::RegisterLinkIterator iter
= reg
.rangesBegin(); iter
;
2182 LiveRange
* range
= LiveRange::get(*iter
);
2183 LiveBundle
* bundle
= range
->bundle();
2184 if (range
== bundle
->firstRange()) {
2185 if (!alloc().ensureBallast()) {
2189 SpillSet
* spill
= SpillSet::New(alloc());
2193 bundle
->setSpillSet(spill
);
2195 size_t priority
= computePriority(bundle
);
2196 if (!allocationQueue
.insert(QueueItem(bundle
, priority
))) {
2206 ///////////////////////////////////////////////////////////////////////////////
2208 // Code for the splitting/spilling subsystem begins here. //
2210 // The code that follows is structured in the following sequence: //
2212 // (1) Routines that are helpers for ::splitAt. //
2213 // (2) ::splitAt itself, which implements splitting decisions. //
2214 // (3) heuristic routines (eg ::splitAcrossCalls), which decide where //
2215 // splits should be made. They then call ::splitAt to perform the //
2217 // (4) The top level driver, ::chooseBundleSplit. //
2219 // There are further comments on ::splitAt and ::chooseBundleSplit below. //
2221 ///////////////////////////////////////////////////////////////////////////////
2223 ///////////////////////////////////////////////////////////////////////////////
2225 // Implementation of splitting decisions, but not the making of those //
2226 // decisions: various helper functions //
2228 ///////////////////////////////////////////////////////////////////////////////
2230 bool BacktrackingAllocator::updateVirtualRegisterListsThenRequeueBundles(
2231 LiveBundle
* bundle
, const LiveBundleVector
& newBundles
) {
2233 if (newBundles
.length() == 1) {
2234 LiveBundle
* newBundle
= newBundles
[0];
2235 if (newBundle
->numRanges() == bundle
->numRanges() &&
2236 computePriority(newBundle
) == computePriority(bundle
)) {
2237 bool different
= false;
2238 LiveRange::BundleLinkIterator oldRanges
= bundle
->rangesBegin();
2239 LiveRange::BundleLinkIterator newRanges
= newBundle
->rangesBegin();
2241 LiveRange
* oldRange
= LiveRange::get(*oldRanges
);
2242 LiveRange
* newRange
= LiveRange::get(*newRanges
);
2243 if (oldRange
->from() != newRange
->from() ||
2244 oldRange
->to() != newRange
->to()) {
2252 // This is likely to trigger an infinite loop in register allocation. This
2253 // can be the result of invalid register constraints, making regalloc
2254 // impossible; consider relaxing those.
2255 MOZ_ASSERT(different
,
2256 "Split results in the same bundle with the same priority");
2261 if (JitSpewEnabled(JitSpew_RegAlloc
)) {
2262 JitSpew(JitSpew_RegAlloc
, " .. into:");
2263 for (size_t i
= 0; i
< newBundles
.length(); i
++) {
2264 JitSpew(JitSpew_RegAlloc
, " %s", newBundles
[i
]->toString().get());
2268 // Remove all ranges in the old bundle from their register's list.
2269 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
2271 LiveRange
* range
= LiveRange::get(*iter
);
2272 range
->vreg().removeRange(range
);
2275 // Add all ranges in the new bundles to their register's list.
2276 for (size_t i
= 0; i
< newBundles
.length(); i
++) {
2277 LiveBundle
* newBundle
= newBundles
[i
];
2278 for (LiveRange::BundleLinkIterator iter
= newBundle
->rangesBegin(); iter
;
2280 LiveRange
* range
= LiveRange::get(*iter
);
2281 range
->vreg().addRange(range
);
2285 // Queue the new bundles for register assignment.
2286 for (size_t i
= 0; i
< newBundles
.length(); i
++) {
2287 LiveBundle
* newBundle
= newBundles
[i
];
2288 size_t priority
= computePriority(newBundle
);
2289 if (!allocationQueue
.insert(QueueItem(newBundle
, priority
))) {
2297 // Helper for ::splitAt
2298 // When splitting a bundle according to a list of split positions, return
2299 // whether a use or range at |pos| should use a different bundle than the last
2300 // position this was called for.
2301 static bool UseNewBundle(const SplitPositionVector
& splitPositions
,
2302 CodePosition pos
, size_t* activeSplitPosition
) {
2303 if (splitPositions
.empty()) {
2304 // When the split positions are empty we are splitting at all uses.
2308 if (*activeSplitPosition
== splitPositions
.length()) {
2309 // We've advanced past all split positions.
2313 if (splitPositions
[*activeSplitPosition
] > pos
) {
2314 // We haven't gotten to the next split position yet.
2318 // We've advanced past the next split position, find the next one which we
2320 while (*activeSplitPosition
< splitPositions
.length() &&
2321 splitPositions
[*activeSplitPosition
] <= pos
) {
2322 (*activeSplitPosition
)++;
2327 // Helper for ::splitAt
2328 static bool HasPrecedingRangeSharingVreg(LiveBundle
* bundle
, LiveRange
* range
) {
2329 MOZ_ASSERT(range
->bundle() == bundle
);
2331 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
2333 LiveRange
* prevRange
= LiveRange::get(*iter
);
2334 if (prevRange
== range
) {
2337 if (&prevRange
->vreg() == &range
->vreg()) {
2345 // Helper for ::splitAt
2346 static bool HasFollowingRangeSharingVreg(LiveBundle
* bundle
, LiveRange
* range
) {
2347 MOZ_ASSERT(range
->bundle() == bundle
);
2349 bool foundRange
= false;
2350 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
2352 LiveRange
* prevRange
= LiveRange::get(*iter
);
2353 if (foundRange
&& &prevRange
->vreg() == &range
->vreg()) {
2356 if (prevRange
== range
) {
2361 MOZ_ASSERT(foundRange
);
2365 ///////////////////////////////////////////////////////////////////////////////
2367 // Implementation of splitting decisions, but not the making of those //
2371 ///////////////////////////////////////////////////////////////////////////////
2375 // It would be nice to be able to interpret ::splitAt as simply performing
2376 // whatever split the heuristic routines decide on. Unfortunately it
2377 // tries to "improve" on the initial locations, which as
2378 // https://bugzilla.mozilla.org/show_bug.cgi?id=1758274#c17 shows, often
2379 // leads to excessive spilling. So there is no clean distinction between
2380 // policy (where to split, computed by the heuristic routines) and
2381 // implementation (done by ::splitAt).
2383 // ::splitAt -- creation of spill parent bundles
2384 // ---------------------------------------------
2385 // To understand what ::splitAt does, we must refer back to Section 1's
2386 // description of LiveBundle::spillParent_.
2388 // Initially (as created by Phase 1), all bundles have `spillParent_` being
2389 // NULL. If ::splitAt is asked to split such a bundle, it will first create a
2390 // "spill bundle" or "spill parent" bundle. This is a copy of the original,
2391 // with two changes:
2393 // * all register uses have been removed, so that only stack-compatible uses
2396 // * for all LiveRanges in the bundle that define a register, the start point
2397 // of the range is moved one CodePosition forwards, thusly:
2399 // from = minimalDefEnd(insData[from]).next();
2401 // The reason for the latter relates to the idea described in Section 1, that
2402 // all LiveRanges for any given VirtualRegister must form a tree rooted at the
2403 // defining LiveRange. If the spill-bundle definition range start points are
2404 // the same as those in the original bundle, then we will end up with two roots
2405 // for the tree, and it is then unclear which one should supply "the value".
2407 // Putting the spill-bundle start point one CodePosition further along causes
2408 // the range containing the register def (after splitting) to still be the
2409 // defining point. ::createMoveGroupsFromLiveRangeTransitions will observe the
2410 // equivalent spill-bundle range starting one point later and add a MoveGroup
2411 // to move the value into it. Since the spill bundle is intended to be stack
2412 // resident, the effect is to force creation of the MoveGroup that will
2413 // actually spill this value onto the stack.
2415 // If the bundle provided to ::splitAt already has a spill parent, then
2416 // ::splitAt doesn't create a new spill parent. This situation will happen
2417 // when the bundle to be split was itself created by splitting. The effect is
2418 // that *all* bundles created from an "original bundle" share the same spill
2419 // parent, and hence they will share the same spill slot, which guarantees that
2420 // all the spilled fragments of a VirtualRegister share the same spill slot,
2421 // which means we'll never have to move a VirtualRegister between different
2422 // spill slots during its lifetime.
2424 // ::splitAt -- creation of other bundles
2425 // --------------------------------------
2426 // With the spill parent bundle question out of the way, ::splitAt then goes on
2427 // to create the remaining new bundles, using near-incomprehensible logic
2428 // steered by `UseNewBundle`.
2430 // This supposedly splits the bundle at the positions given by the
2431 // `SplitPositionVector` parameter to ::splitAt, putting them in a temporary
2432 // vector `newBundles`. Whether it really splits at the requested positions or
2433 // not is hard to say; more important is what happens next.
2435 // ::splitAt -- "improvement" ("filtering") of the split bundles
2436 // -------------------------------------------------------------
2437 // ::splitAt now tries to reduce the length of the LiveRanges that make up the
2438 // new bundles (not including the "spill parent"). I assume this is to remove
2439 // sections of the bundles that carry no useful value (eg, extending after the
2440 // last using a range), thereby removing the demand for registers in those
2441 // parts. This does however mean that ::splitAt is no longer really splitting
2442 // where the heuristic routines wanted, and that can lead to a big increase in
2443 // spilling in loops, as
2444 // https://bugzilla.mozilla.org/show_bug.cgi?id=1758274#c17 describes.
2446 // ::splitAt -- meaning of the incoming `SplitPositionVector`
2447 // ----------------------------------------------------------
2448 // ::splitAt has one last mystery which is important to document. The split
2449 // positions are specified as CodePositions, but this leads to ambiguity
2450 // because, in a sequence of N (LIR) instructions, there are 2N valid
2451 // CodePositions. For example:
2453 // 6-7 WasmLoadTls [def v2<o>] [use v1:R]
2454 // 8-9 WasmNullConstant [def v3<o>]
2456 // Consider splitting the range for `v2`, which starts at CodePosition 7.
2457 // What's the difference between saying "split it at 7" and "split it at 8" ?
2458 // Not much really, since in both cases what we intend is for the range to be
2459 // split in between the two instructions.
2461 // Hence I believe the semantics is:
2463 // * splitting at an even numbered CodePosition (eg, 8), which is an input-side
2464 // position, means "split before the instruction containing this position".
2466 // * splitting at an odd numbered CodePositin (eg, 7), which is an output-side
2467 // position, means "split after the instruction containing this position".
2469 // Hence in the example, we could specify either 7 or 8 to mean the same
2470 // placement of the split. Well, almost true, but actually:
2472 // (SPEC) specifying 8 means
2474 // "split between these two insns, and any resulting MoveGroup goes in the
2475 // list to be emitted before the start of the second insn"
2477 // (SPEC) specifying 7 means
2479 // "split between these two insns, and any resulting MoveGroup goes in the
2480 // list to be emitted after the end of the first insn"
2482 // In most cases we don't care on which "side of the valley" the MoveGroup ends
2483 // up, in which case we can use either convention.
2485 // (SPEC) I believe these semantics are implied by the logic in
2486 // ::createMoveGroupsFromLiveRangeTransitions. They are certainly not
2487 // documented anywhere in the code.
2489 bool BacktrackingAllocator::splitAt(LiveBundle
* bundle
,
2490 const SplitPositionVector
& splitPositions
) {
2491 // Split the bundle at the given split points. Register uses which have no
2492 // intervening split points are consolidated into the same bundle. If the
2493 // list of split points is empty, then all register uses are placed in
2496 // splitPositions should be sorted.
2497 for (size_t i
= 1; i
< splitPositions
.length(); ++i
) {
2498 MOZ_ASSERT(splitPositions
[i
- 1] < splitPositions
[i
]);
2501 // We don't need to create a new spill bundle if there already is one.
2502 bool spillBundleIsNew
= false;
2503 LiveBundle
* spillBundle
= bundle
->spillParent();
2505 spillBundle
= LiveBundle::FallibleNew(alloc(), bundle
->spillSet(), nullptr);
2509 spillBundleIsNew
= true;
2511 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
2513 LiveRange
* range
= LiveRange::get(*iter
);
2515 CodePosition from
= range
->from();
2516 if (isRegisterDefinition(range
)) {
2517 from
= minimalDefEnd(insData
[from
]).next();
2520 if (from
< range
->to()) {
2521 if (!spillBundle
->addRange(alloc(), &range
->vreg(), from
,
2526 if (range
->hasDefinition() && !isRegisterDefinition(range
)) {
2527 spillBundle
->lastRange()->setHasDefinition();
2533 LiveBundleVector newBundles
;
2535 // The bundle which ranges are currently being added to.
2536 LiveBundle
* activeBundle
=
2537 LiveBundle::FallibleNew(alloc(), bundle
->spillSet(), spillBundle
);
2538 if (!activeBundle
|| !newBundles
.append(activeBundle
)) {
2542 // State for use by UseNewBundle.
2543 size_t activeSplitPosition
= 0;
2545 // Make new bundles according to the split positions, and distribute ranges
2546 // and uses to them.
2547 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
2549 LiveRange
* range
= LiveRange::get(*iter
);
2551 if (UseNewBundle(splitPositions
, range
->from(), &activeSplitPosition
)) {
2553 LiveBundle::FallibleNew(alloc(), bundle
->spillSet(), spillBundle
);
2554 if (!activeBundle
|| !newBundles
.append(activeBundle
)) {
2559 LiveRange
* activeRange
= LiveRange::FallibleNew(alloc(), &range
->vreg(),
2560 range
->from(), range
->to());
2564 activeBundle
->addRange(activeRange
);
2566 if (isRegisterDefinition(range
)) {
2567 activeRange
->setHasDefinition();
2570 while (range
->hasUses()) {
2571 UsePosition
* use
= range
->popUse();
2572 LNode
* ins
= insData
[use
->pos
];
2574 // Any uses of a register that appear before its definition has
2575 // finished must be associated with the range for that definition.
2576 if (isRegisterDefinition(range
) &&
2577 use
->pos
<= minimalDefEnd(insData
[range
->from()])) {
2578 activeRange
->addUse(use
);
2579 } else if (isRegisterUse(use
, ins
)) {
2580 // Place this register use into a different bundle from the
2581 // last one if there are any split points between the two uses.
2582 // UseNewBundle always returns true if we are splitting at all
2583 // register uses, but we can still reuse the last range and
2584 // bundle if they have uses at the same position, except when
2585 // either use is fixed (the two uses might require incompatible
2587 if (UseNewBundle(splitPositions
, use
->pos
, &activeSplitPosition
) &&
2588 (!activeRange
->hasUses() ||
2589 activeRange
->usesBegin()->pos
!= use
->pos
||
2590 activeRange
->usesBegin()->usePolicy() == LUse::FIXED
||
2591 use
->usePolicy() == LUse::FIXED
)) {
2593 LiveBundle::FallibleNew(alloc(), bundle
->spillSet(), spillBundle
);
2594 if (!activeBundle
|| !newBundles
.append(activeBundle
)) {
2597 activeRange
= LiveRange::FallibleNew(alloc(), &range
->vreg(),
2598 range
->from(), range
->to());
2602 activeBundle
->addRange(activeRange
);
2605 activeRange
->addUse(use
);
2607 MOZ_ASSERT(spillBundleIsNew
);
2608 spillBundle
->rangeFor(use
->pos
)->addUse(use
);
2613 LiveBundleVector filteredBundles
;
2615 // Trim the ends of ranges in each new bundle when there are no other
2616 // earlier or later ranges in the same bundle with the same vreg.
2617 for (size_t i
= 0; i
< newBundles
.length(); i
++) {
2618 LiveBundle
* bundle
= newBundles
[i
];
2620 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;) {
2621 LiveRange
* range
= LiveRange::get(*iter
);
2623 if (!range
->hasDefinition()) {
2624 if (!HasPrecedingRangeSharingVreg(bundle
, range
)) {
2625 if (range
->hasUses()) {
2626 UsePosition
* use
= *range
->usesBegin();
2627 range
->setFrom(inputOf(insData
[use
->pos
]));
2629 bundle
->removeRangeAndIncrementIterator(iter
);
2635 if (!HasFollowingRangeSharingVreg(bundle
, range
)) {
2636 if (range
->hasUses()) {
2637 UsePosition
* use
= range
->lastUse();
2638 range
->setTo(use
->pos
.next());
2639 } else if (range
->hasDefinition()) {
2640 range
->setTo(minimalDefEnd(insData
[range
->from()]).next());
2642 bundle
->removeRangeAndIncrementIterator(iter
);
2650 if (bundle
->hasRanges() && !filteredBundles
.append(bundle
)) {
2655 if (spillBundleIsNew
&& !filteredBundles
.append(spillBundle
)) {
2659 return updateVirtualRegisterListsThenRequeueBundles(bundle
, filteredBundles
);
2662 ///////////////////////////////////////////////////////////////////////////////
2664 // Creation of splitting decisions, but not their implementation: //
2665 // ::splitAcrossCalls //
2666 // ::trySplitAcrossHotcode //
2667 // ::trySplitAfterLastRegisterUse //
2668 // ::trySplitBeforeFirstRegisterUse //
2670 ///////////////////////////////////////////////////////////////////////////////
2672 bool BacktrackingAllocator::splitAcrossCalls(LiveBundle
* bundle
) {
2673 // Split the bundle to separate register uses and non-register uses and
2674 // allow the vreg to be spilled across its range.
2676 // Find the locations of all calls in the bundle's range.
2677 SplitPositionVector callPositions
;
2678 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
2680 LiveRange
* range
= LiveRange::get(*iter
);
2681 CallRange
searchRange(range
->from(), range
->to());
2682 CallRange
* callRange
;
2683 if (!callRanges
.contains(&searchRange
, &callRange
)) {
2684 // There are no calls inside this range.
2687 MOZ_ASSERT(range
->covers(callRange
->range
.from
));
2689 // The search above returns an arbitrary call within the range. Walk
2690 // backwards to find the first call in the range.
2691 for (CallRangeList::reverse_iterator riter
=
2692 callRangesList
.rbegin(callRange
);
2693 riter
!= callRangesList
.rend(); ++riter
) {
2694 CodePosition pos
= riter
->range
.from
;
2695 if (range
->covers(pos
)) {
2702 // Add all call positions within the range, by walking forwards.
2703 for (CallRangeList::iterator iter
= callRangesList
.begin(callRange
);
2704 iter
!= callRangesList
.end(); ++iter
) {
2705 CodePosition pos
= iter
->range
.from
;
2706 if (!range
->covers(pos
)) {
2710 // Calls at the beginning of the range are ignored; there is no splitting
2712 if (range
->covers(pos
.previous())) {
2713 MOZ_ASSERT_IF(callPositions
.length(), pos
> callPositions
.back());
2714 if (!callPositions
.append(pos
)) {
2720 MOZ_ASSERT(callPositions
.length());
2723 JitSpewStart(JitSpew_RegAlloc
, " .. split across calls at ");
2724 for (size_t i
= 0; i
< callPositions
.length(); ++i
) {
2725 JitSpewCont(JitSpew_RegAlloc
, "%s%u", i
!= 0 ? ", " : "",
2726 callPositions
[i
].bits());
2728 JitSpewFin(JitSpew_RegAlloc
);
2731 return splitAt(bundle
, callPositions
);
2734 bool BacktrackingAllocator::trySplitAcrossHotcode(LiveBundle
* bundle
,
2736 // If this bundle has portions that are hot and portions that are cold,
2737 // split it at the boundaries between hot and cold code.
2739 LiveRange
* hotRange
= nullptr;
2741 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
2743 LiveRange
* range
= LiveRange::get(*iter
);
2744 if (hotcode
.contains(range
, &hotRange
)) {
2749 // Don't split if there is no hot code in the bundle.
2751 JitSpew(JitSpew_RegAlloc
, " .. bundle does not contain hot code");
2755 // Don't split if there is no cold code in the bundle.
2756 bool coldCode
= false;
2757 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
2759 LiveRange
* range
= LiveRange::get(*iter
);
2760 if (!hotRange
->contains(range
)) {
2766 JitSpew(JitSpew_RegAlloc
, " .. bundle does not contain cold code");
2770 JitSpewIfEnabled(JitSpew_RegAlloc
, " .. split across hot range %s",
2771 hotRange
->toString().get());
2773 // Tweak the splitting method when compiling wasm code to look at actual
2774 // uses within the hot/cold code. This heuristic is in place as the below
2775 // mechanism regresses several asm.js tests. Hopefully this will be fixed
2776 // soon and this special case removed. See bug 948838.
2777 if (compilingWasm()) {
2778 SplitPositionVector splitPositions
;
2779 if (!splitPositions
.append(hotRange
->from()) ||
2780 !splitPositions
.append(hotRange
->to())) {
2784 return splitAt(bundle
, splitPositions
);
2787 LiveBundle
* hotBundle
= LiveBundle::FallibleNew(alloc(), bundle
->spillSet(),
2788 bundle
->spillParent());
2792 LiveBundle
* preBundle
= nullptr;
2793 LiveBundle
* postBundle
= nullptr;
2794 LiveBundle
* coldBundle
= nullptr;
2797 coldBundle
= LiveBundle::FallibleNew(alloc(), bundle
->spillSet(),
2798 bundle
->spillParent());
2804 // Accumulate the ranges of hot and cold code in the bundle. Note that
2805 // we are only comparing with the single hot range found, so the cold code
2806 // may contain separate hot ranges.
2807 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
2809 LiveRange
* range
= LiveRange::get(*iter
);
2810 LiveRange::Range hot
, coldPre
, coldPost
;
2811 range
->intersect(hotRange
, &coldPre
, &hot
, &coldPost
);
2814 if (!hotBundle
->addRangeAndDistributeUses(alloc(), range
, hot
.from
,
2820 if (!coldPre
.empty()) {
2822 if (!coldBundle
->addRangeAndDistributeUses(alloc(), range
, coldPre
.from
,
2828 preBundle
= LiveBundle::FallibleNew(alloc(), bundle
->spillSet(),
2829 bundle
->spillParent());
2834 if (!preBundle
->addRangeAndDistributeUses(alloc(), range
, coldPre
.from
,
2841 if (!coldPost
.empty()) {
2843 if (!coldBundle
->addRangeAndDistributeUses(
2844 alloc(), range
, coldPost
.from
, coldPost
.to
)) {
2849 postBundle
= LiveBundle::FallibleNew(alloc(), bundle
->spillSet(),
2850 bundle
->spillParent());
2855 if (!postBundle
->addRangeAndDistributeUses(
2856 alloc(), range
, coldPost
.from
, coldPost
.to
)) {
2863 MOZ_ASSERT(hotBundle
->numRanges() != 0);
2865 LiveBundleVector newBundles
;
2866 if (!newBundles
.append(hotBundle
)) {
2871 MOZ_ASSERT(coldBundle
->numRanges() != 0);
2872 if (!newBundles
.append(coldBundle
)) {
2876 MOZ_ASSERT(preBundle
|| postBundle
);
2877 if (preBundle
&& !newBundles
.append(preBundle
)) {
2880 if (postBundle
&& !newBundles
.append(postBundle
)) {
2886 return updateVirtualRegisterListsThenRequeueBundles(bundle
, newBundles
);
2889 bool BacktrackingAllocator::trySplitAfterLastRegisterUse(LiveBundle
* bundle
,
2890 LiveBundle
* conflict
,
2892 // If this bundle's later uses do not require it to be in a register,
2893 // split it after the last use which does require a register. If conflict
2894 // is specified, only consider register uses before the conflict starts.
2896 CodePosition lastRegisterFrom
, lastRegisterTo
, lastUse
;
2898 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
2900 LiveRange
* range
= LiveRange::get(*iter
);
2902 // If the range defines a register, consider that a register use for
2903 // our purposes here.
2904 if (isRegisterDefinition(range
)) {
2905 CodePosition spillStart
= minimalDefEnd(insData
[range
->from()]).next();
2906 if (!conflict
|| spillStart
< conflict
->firstRange()->from()) {
2907 lastUse
= lastRegisterFrom
= range
->from();
2908 lastRegisterTo
= spillStart
;
2912 for (UsePositionIterator
iter(range
->usesBegin()); iter
; iter
++) {
2913 LNode
* ins
= insData
[iter
->pos
];
2915 // Uses in the bundle should be sorted.
2916 MOZ_ASSERT(iter
->pos
>= lastUse
);
2917 lastUse
= inputOf(ins
);
2919 if (!conflict
|| outputOf(ins
) < conflict
->firstRange()->from()) {
2920 if (isRegisterUse(*iter
, ins
, /* considerCopy = */ true)) {
2921 lastRegisterFrom
= inputOf(ins
);
2922 lastRegisterTo
= iter
->pos
.next();
2928 // Can't trim non-register uses off the end by splitting.
2929 if (!lastRegisterFrom
.bits()) {
2930 JitSpew(JitSpew_RegAlloc
, " .. bundle has no register uses");
2933 if (lastUse
< lastRegisterTo
) {
2934 JitSpew(JitSpew_RegAlloc
, " .. bundle's last use is a register use");
2938 JitSpewIfEnabled(JitSpew_RegAlloc
, " .. split after last register use at %u",
2939 lastRegisterTo
.bits());
2941 SplitPositionVector splitPositions
;
2942 if (!splitPositions
.append(lastRegisterTo
)) {
2946 return splitAt(bundle
, splitPositions
);
2949 bool BacktrackingAllocator::trySplitBeforeFirstRegisterUse(LiveBundle
* bundle
,
2950 LiveBundle
* conflict
,
2952 // If this bundle's earlier uses do not require it to be in a register,
2953 // split it before the first use which does require a register. If conflict
2954 // is specified, only consider register uses after the conflict ends.
2956 if (isRegisterDefinition(bundle
->firstRange())) {
2957 JitSpew(JitSpew_RegAlloc
, " .. bundle is defined by a register");
2960 if (!bundle
->firstRange()->hasDefinition()) {
2961 JitSpew(JitSpew_RegAlloc
, " .. bundle does not have definition");
2965 CodePosition firstRegisterFrom
;
2967 CodePosition conflictEnd
;
2969 for (LiveRange::BundleLinkIterator iter
= conflict
->rangesBegin(); iter
;
2971 LiveRange
* range
= LiveRange::get(*iter
);
2972 if (range
->to() > conflictEnd
) {
2973 conflictEnd
= range
->to();
2978 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
2980 LiveRange
* range
= LiveRange::get(*iter
);
2982 if (!conflict
|| range
->from() > conflictEnd
) {
2983 if (range
->hasDefinition() && isRegisterDefinition(range
)) {
2984 firstRegisterFrom
= range
->from();
2989 for (UsePositionIterator
iter(range
->usesBegin()); iter
; iter
++) {
2990 LNode
* ins
= insData
[iter
->pos
];
2992 if (!conflict
|| outputOf(ins
) >= conflictEnd
) {
2993 if (isRegisterUse(*iter
, ins
, /* considerCopy = */ true)) {
2994 firstRegisterFrom
= inputOf(ins
);
2999 if (firstRegisterFrom
.bits()) {
3004 if (!firstRegisterFrom
.bits()) {
3005 // Can't trim non-register uses off the beginning by splitting.
3006 JitSpew(JitSpew_RegAlloc
, " bundle has no register uses");
3010 JitSpewIfEnabled(JitSpew_RegAlloc
,
3011 " .. split before first register use at %u",
3012 firstRegisterFrom
.bits());
3014 SplitPositionVector splitPositions
;
3015 if (!splitPositions
.append(firstRegisterFrom
)) {
3019 return splitAt(bundle
, splitPositions
);
3022 ///////////////////////////////////////////////////////////////////////////////
3024 // The top level driver for the splitting machinery //
3026 ///////////////////////////////////////////////////////////////////////////////
3028 // ::chooseBundleSplit
3029 // -------------------
3030 // If the first allocation loop (in ::go) can't allocate a bundle, it hands it
3031 // off to ::chooseBundleSplit, which is the "entry point" of the bundle-split
3032 // machinery. This tries four heuristics in turn, to see if any can split the
3035 // * ::trySplitAcrossHotcode
3036 // * ::splitAcrossCalls (in some cases)
3037 // * ::trySplitBeforeFirstRegisterUse
3038 // * ::trySplitAfterLastRegisterUse
3040 // These routines have similar structure: they try to decide on one or more
3041 // CodePositions at which to split the bundle, using whatever heuristics they
3042 // have to hand. If suitable CodePosition(s) are found, they are put into a
3043 // `SplitPositionVector`, and the bundle and the vector are handed off to
3044 // ::splitAt, which performs the split (at least in theory) at the chosen
3045 // positions. It also arranges for the new bundles to be added to
3046 // ::allocationQueue.
3048 // ::trySplitAcrossHotcode has a special case for JS -- it modifies the
3049 // bundle(s) itself, rather than using ::splitAt.
3051 // If none of the heuristic routines apply, then ::splitAt is called with an
3052 // empty vector of split points. This is interpreted to mean "split at all
3053 // register uses". When combined with how ::splitAt works, the effect is to
3054 // spill the bundle.
3056 bool BacktrackingAllocator::chooseBundleSplit(LiveBundle
* bundle
, bool fixed
,
3057 LiveBundle
* conflict
) {
3058 bool success
= false;
3060 JitSpewIfEnabled(JitSpew_RegAlloc
, " Splitting %s ..",
3061 bundle
->toString().get());
3063 if (!trySplitAcrossHotcode(bundle
, &success
)) {
3071 return splitAcrossCalls(bundle
);
3074 if (!trySplitBeforeFirstRegisterUse(bundle
, conflict
, &success
)) {
3081 if (!trySplitAfterLastRegisterUse(bundle
, conflict
, &success
)) {
3088 // Split at all register uses.
3089 SplitPositionVector emptyPositions
;
3090 return splitAt(bundle
, emptyPositions
);
3093 ///////////////////////////////////////////////////////////////////////////////
3095 // Bundle allocation //
3097 ///////////////////////////////////////////////////////////////////////////////
3099 static const size_t MAX_ATTEMPTS
= 2;
3101 bool BacktrackingAllocator::computeRequirement(LiveBundle
* bundle
,
3102 Requirement
* requirement
,
3103 Requirement
* hint
) {
3104 // Set any requirement or hint on bundle according to its definition and
3105 // uses. Return false if there are conflicting requirements which will
3106 // require the bundle to be split.
3108 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
3110 LiveRange
* range
= LiveRange::get(*iter
);
3111 VirtualRegister
& reg
= range
->vreg();
3113 if (range
->hasDefinition()) {
3114 // Deal with any definition constraints/hints.
3115 LDefinition::Policy policy
= reg
.def()->policy();
3116 if (policy
== LDefinition::FIXED
|| policy
== LDefinition::STACK
) {
3117 // Fixed and stack policies get a FIXED requirement. (In the stack
3118 // case, the allocation should have been performed already by
3119 // mergeAndQueueRegisters.)
3120 JitSpewIfEnabled(JitSpew_RegAlloc
,
3121 " Requirement %s, fixed by definition",
3122 reg
.def()->output()->toString().get());
3123 if (!requirement
->merge(Requirement(*reg
.def()->output()))) {
3126 } else if (reg
.ins()->isPhi()) {
3127 // Phis don't have any requirements, but they should prefer their
3128 // input allocations. This is captured by the group hints above.
3130 // Non-phis get a REGISTER requirement.
3131 if (!requirement
->merge(Requirement(Requirement::REGISTER
))) {
3137 // Search uses for requirements.
3138 for (UsePositionIterator iter
= range
->usesBegin(); iter
; iter
++) {
3139 LUse::Policy policy
= iter
->usePolicy();
3140 if (policy
== LUse::FIXED
) {
3141 AnyRegister required
= GetFixedRegister(reg
.def(), iter
->use());
3143 JitSpewIfEnabled(JitSpew_RegAlloc
, " Requirement %s, due to use at %u",
3144 required
.name(), iter
->pos
.bits());
3146 // If there are multiple fixed registers which the bundle is
3147 // required to use, fail. The bundle will need to be split before
3148 // it can be allocated.
3149 if (!requirement
->merge(Requirement(LAllocation(required
)))) {
3152 } else if (policy
== LUse::REGISTER
) {
3153 if (!requirement
->merge(Requirement(Requirement::REGISTER
))) {
3156 } else if (policy
== LUse::ANY
) {
3157 // ANY differs from KEEPALIVE by actively preferring a register.
3158 if (!hint
->merge(Requirement(Requirement::REGISTER
))) {
3163 // The only case of STACK use policies is individual stack results using
3164 // their containing stack result area, which is given a fixed allocation
3166 MOZ_ASSERT_IF(policy
== LUse::STACK
,
3167 requirement
->kind() == Requirement::FIXED
);
3168 MOZ_ASSERT_IF(policy
== LUse::STACK
,
3169 requirement
->allocation().isStackArea());
3176 bool BacktrackingAllocator::tryAllocateRegister(PhysicalRegister
& r
,
3178 bool* success
, bool* pfixed
,
3179 LiveBundleVector
& conflicting
) {
3182 if (!r
.allocatable
) {
3186 LiveBundleVector aliasedConflicting
;
3188 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
3190 LiveRange
* range
= LiveRange::get(*iter
);
3191 LiveRangePlus
rangePlus(range
);
3193 // All ranges in the bundle must be compatible with the physical register.
3194 MOZ_ASSERT(range
->vreg().isCompatible(r
.reg
));
3196 const size_t numAliased
= r
.reg
.numAliased();
3197 for (size_t a
= 0; a
< numAliased
; a
++) {
3198 PhysicalRegister
& rAlias
= registers
[r
.reg
.aliased(a
).code()];
3199 LiveRangePlus existingPlus
;
3200 if (!rAlias
.allocations
.contains(rangePlus
, &existingPlus
)) {
3203 const LiveRange
* existing
= existingPlus
.liveRange();
3204 if (existing
->hasVreg()) {
3205 MOZ_ASSERT(existing
->bundle()->allocation().toRegister() == rAlias
.reg
);
3206 bool duplicate
= false;
3207 for (size_t i
= 0; i
< aliasedConflicting
.length(); i
++) {
3208 if (aliasedConflicting
[i
] == existing
->bundle()) {
3213 if (!duplicate
&& !aliasedConflicting
.append(existing
->bundle())) {
3217 JitSpewIfEnabled(JitSpew_RegAlloc
, " %s collides with fixed use %s",
3218 rAlias
.reg
.name(), existing
->toString().get());
3222 MOZ_ASSERT(r
.reg
.numAliased() == numAliased
);
3226 if (!aliasedConflicting
.empty()) {
3227 // One or more aliased registers is allocated to another bundle
3228 // overlapping this one. Keep track of the conflicting set, and in the
3229 // case of multiple conflicting sets keep track of the set with the
3230 // lowest maximum spill weight.
3232 // The #ifdef guards against "unused variable 'existing'" bustage.
3234 if (JitSpewEnabled(JitSpew_RegAlloc
)) {
3235 if (aliasedConflicting
.length() == 1) {
3236 LiveBundle
* existing
= aliasedConflicting
[0];
3237 JitSpew(JitSpew_RegAlloc
, " %s collides with %s [weight %zu]",
3238 r
.reg
.name(), existing
->toString().get(),
3239 computeSpillWeight(existing
));
3241 JitSpew(JitSpew_RegAlloc
, " %s collides with the following",
3243 for (size_t i
= 0; i
< aliasedConflicting
.length(); i
++) {
3244 LiveBundle
* existing
= aliasedConflicting
[i
];
3245 JitSpew(JitSpew_RegAlloc
, " %s [weight %zu]",
3246 existing
->toString().get(), computeSpillWeight(existing
));
3252 if (conflicting
.empty()) {
3253 conflicting
= std::move(aliasedConflicting
);
3255 if (maximumSpillWeight(aliasedConflicting
) <
3256 maximumSpillWeight(conflicting
)) {
3257 conflicting
= std::move(aliasedConflicting
);
3263 JitSpewIfEnabled(JitSpew_RegAlloc
, " allocated to %s", r
.reg
.name());
3265 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
3267 LiveRange
* range
= LiveRange::get(*iter
);
3268 if (!alloc().ensureBallast()) {
3271 LiveRangePlus
rangePlus(range
);
3272 if (!r
.allocations
.insert(rangePlus
)) {
3277 bundle
->setAllocation(LAllocation(r
.reg
));
3282 bool BacktrackingAllocator::tryAllocateAnyRegister(
3283 LiveBundle
* bundle
, bool* success
, bool* pfixed
,
3284 LiveBundleVector
& conflicting
) {
3285 // Search for any available register which the bundle can be allocated to.
3287 LDefinition::Type type
= bundle
->firstRange()->vreg().type();
3289 if (LDefinition::isFloatReg(type
)) {
3290 for (size_t i
= AnyRegister::FirstFloatReg
; i
< AnyRegister::Total
; i
++) {
3291 if (!LDefinition::isFloatRegCompatible(type
, registers
[i
].reg
.fpu())) {
3294 if (!tryAllocateRegister(registers
[i
], bundle
, success
, pfixed
,
3305 for (size_t i
= 0; i
< AnyRegister::FirstFloatReg
; i
++) {
3306 if (!tryAllocateRegister(registers
[i
], bundle
, success
, pfixed
,
3317 bool BacktrackingAllocator::evictBundle(LiveBundle
* bundle
) {
3318 JitSpewIfEnabled(JitSpew_RegAlloc
,
3319 " Evicting %s [priority %zu] [weight %zu]",
3320 bundle
->toString().get(), computePriority(bundle
),
3321 computeSpillWeight(bundle
));
3323 AnyRegister
reg(bundle
->allocation().toRegister());
3324 PhysicalRegister
& physical
= registers
[reg
.code()];
3325 MOZ_ASSERT(physical
.reg
== reg
&& physical
.allocatable
);
3327 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
3329 LiveRange
* range
= LiveRange::get(*iter
);
3330 LiveRangePlus
rangePlus(range
);
3331 physical
.allocations
.remove(rangePlus
);
3334 bundle
->setAllocation(LAllocation());
3336 size_t priority
= computePriority(bundle
);
3337 return allocationQueue
.insert(QueueItem(bundle
, priority
));
3340 bool BacktrackingAllocator::tryAllocateFixed(LiveBundle
* bundle
,
3341 Requirement requirement
,
3342 bool* success
, bool* pfixed
,
3343 LiveBundleVector
& conflicting
) {
3344 // Spill bundles which are required to be in a certain stack slot.
3345 if (!requirement
.allocation().isRegister()) {
3346 JitSpew(JitSpew_RegAlloc
, " stack allocation requirement");
3347 bundle
->setAllocation(requirement
.allocation());
3352 AnyRegister reg
= requirement
.allocation().toRegister();
3353 return tryAllocateRegister(registers
[reg
.code()], bundle
, success
, pfixed
,
3357 bool BacktrackingAllocator::tryAllocateNonFixed(LiveBundle
* bundle
,
3358 Requirement requirement
,
3359 Requirement hint
, bool* success
,
3361 LiveBundleVector
& conflicting
) {
3362 // If we want, but do not require a bundle to be in a specific register,
3363 // only look at that register for allocating and evict or spill if it is
3364 // not available. Picking a separate register may be even worse than
3365 // spilling, as it will still necessitate moves and will tie up more
3366 // registers than if we spilled.
3367 if (hint
.kind() == Requirement::FIXED
) {
3368 AnyRegister reg
= hint
.allocation().toRegister();
3369 if (!tryAllocateRegister(registers
[reg
.code()], bundle
, success
, pfixed
,
3378 // Spill bundles which have no hint or register requirement.
3379 if (requirement
.kind() == Requirement::NONE
&&
3380 hint
.kind() != Requirement::REGISTER
) {
3381 JitSpew(JitSpew_RegAlloc
,
3382 " postponed spill (no hint or register requirement)");
3383 if (!spilledBundles
.append(bundle
)) {
3390 if (conflicting
.empty() || minimalBundle(bundle
)) {
3391 if (!tryAllocateAnyRegister(bundle
, success
, pfixed
, conflicting
)) {
3399 // Spill bundles which have no register requirement if they didn't get
3401 if (requirement
.kind() == Requirement::NONE
) {
3402 JitSpew(JitSpew_RegAlloc
, " postponed spill (no register requirement)");
3403 if (!spilledBundles
.append(bundle
)) {
3410 // We failed to allocate this bundle.
3411 MOZ_ASSERT(!*success
);
3415 bool BacktrackingAllocator::processBundle(MIRGenerator
* mir
,
3416 LiveBundle
* bundle
) {
3417 JitSpewIfEnabled(JitSpew_RegAlloc
,
3418 "Allocating %s [priority %zu] [weight %zu]",
3419 bundle
->toString().get(), computePriority(bundle
),
3420 computeSpillWeight(bundle
));
3422 // A bundle can be processed by doing any of the following:
3424 // - Assigning the bundle a register. The bundle cannot overlap any other
3425 // bundle allocated for that physical register.
3427 // - Spilling the bundle, provided it has no register uses.
3429 // - Splitting the bundle into two or more bundles which cover the original
3430 // one. The new bundles are placed back onto the priority queue for later
3433 // - Evicting one or more existing allocated bundles, and then doing one
3434 // of the above operations. Evicted bundles are placed back on the
3435 // priority queue. Any evicted bundles must have a lower spill weight
3436 // than the bundle being processed.
3438 // As long as this structure is followed, termination is guaranteed.
3439 // In general, we want to minimize the amount of bundle splitting (which
3440 // generally necessitates spills), so allocate longer lived, lower weight
3441 // bundles first and evict and split them later if they prevent allocation
3442 // for higher weight bundles.
3444 Requirement requirement
, hint
;
3445 bool canAllocate
= computeRequirement(bundle
, &requirement
, &hint
);
3448 LiveBundleVector conflicting
;
3449 for (size_t attempt
= 0;; attempt
++) {
3450 if (mir
->shouldCancel("Backtracking Allocation (processBundle loop)")) {
3455 bool success
= false;
3457 conflicting
.clear();
3459 // Ok, let's try allocating for this bundle.
3460 if (requirement
.kind() == Requirement::FIXED
) {
3461 if (!tryAllocateFixed(bundle
, requirement
, &success
, &fixed
,
3466 if (!tryAllocateNonFixed(bundle
, requirement
, hint
, &success
, &fixed
,
3472 // If that worked, we're done!
3477 // If that didn't work, but we have one or more non-fixed bundles
3478 // known to be conflicting, maybe we can evict them and try again.
3479 if ((attempt
< MAX_ATTEMPTS
|| minimalBundle(bundle
)) && !fixed
&&
3480 !conflicting
.empty() &&
3481 maximumSpillWeight(conflicting
) < computeSpillWeight(bundle
)) {
3482 for (size_t i
= 0; i
< conflicting
.length(); i
++) {
3483 if (!evictBundle(conflicting
[i
])) {
3491 // A minimal bundle cannot be split any further. If we try to split it
3492 // it at this point we will just end up with the same bundle and will
3493 // enter an infinite loop. Weights and the initial live ranges must
3494 // be constructed so that any minimal bundle is allocatable.
3495 MOZ_ASSERT(!minimalBundle(bundle
));
3497 LiveBundle
* conflict
= conflicting
.empty() ? nullptr : conflicting
[0];
3498 return chooseBundleSplit(bundle
, canAllocate
&& fixed
, conflict
);
3502 // Helper for ::tryAllocatingRegistersForSpillBundles
3503 bool BacktrackingAllocator::spill(LiveBundle
* bundle
) {
3504 JitSpew(JitSpew_RegAlloc
, " Spilling bundle");
3505 MOZ_ASSERT(bundle
->allocation().isBogus());
3507 if (LiveBundle
* spillParent
= bundle
->spillParent()) {
3508 JitSpew(JitSpew_RegAlloc
, " Using existing spill bundle");
3509 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
3511 LiveRange
* range
= LiveRange::get(*iter
);
3512 LiveRange
* parentRange
= spillParent
->rangeFor(range
->from());
3513 MOZ_ASSERT(parentRange
->contains(range
));
3514 MOZ_ASSERT(&range
->vreg() == &parentRange
->vreg());
3515 range
->tryToMoveDefAndUsesInto(parentRange
);
3516 MOZ_ASSERT(!range
->hasUses());
3517 range
->vreg().removeRange(range
);
3522 return bundle
->spillSet()->addSpilledBundle(bundle
);
3525 bool BacktrackingAllocator::tryAllocatingRegistersForSpillBundles() {
3526 for (auto it
= spilledBundles
.begin(); it
!= spilledBundles
.end(); it
++) {
3527 LiveBundle
* bundle
= *it
;
3528 LiveBundleVector conflicting
;
3530 bool success
= false;
3532 if (mir
->shouldCancel("Backtracking Try Allocating Spilled Bundles")) {
3536 JitSpewIfEnabled(JitSpew_RegAlloc
, "Spill or allocate %s",
3537 bundle
->toString().get());
3539 if (!tryAllocateAnyRegister(bundle
, &success
, &fixed
, conflicting
)) {
3543 // If the bundle still has no register, spill the bundle.
3544 if (!success
&& !spill(bundle
)) {
3552 ///////////////////////////////////////////////////////////////////////////////
3554 // Rewriting of the LIR after bundle processing is done: //
3555 // ::pickStackSlots //
3556 // ::createMoveGroupsFromLiveRangeTransitions //
3557 // ::installAllocationsInLIR //
3558 // ::populateSafepoints //
3559 // ::annotateMoveGroups //
3561 ///////////////////////////////////////////////////////////////////////////////
3563 // Helper for ::pickStackSlot
3564 bool BacktrackingAllocator::insertAllRanges(LiveRangePlusSet
& set
,
3565 LiveBundle
* bundle
) {
3566 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
3568 LiveRange
* range
= LiveRange::get(*iter
);
3569 if (!alloc().ensureBallast()) {
3572 LiveRangePlus
rangePlus(range
);
3573 if (!set
.insert(rangePlus
)) {
3580 // Helper for ::pickStackSlots
3581 bool BacktrackingAllocator::pickStackSlot(SpillSet
* spillSet
) {
3582 // Look through all ranges that have been spilled in this set for a
3583 // register definition which is fixed to a stack or argument slot. If we
3584 // find one, use it for all bundles that have been spilled. tryMergeBundles
3585 // makes sure this reuse is possible when an initial bundle contains ranges
3586 // from multiple virtual registers.
3587 for (size_t i
= 0; i
< spillSet
->numSpilledBundles(); i
++) {
3588 LiveBundle
* bundle
= spillSet
->spilledBundle(i
);
3589 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
3591 LiveRange
* range
= LiveRange::get(*iter
);
3592 if (range
->hasDefinition()) {
3593 LDefinition
* def
= range
->vreg().def();
3594 if (def
->policy() == LDefinition::FIXED
) {
3595 MOZ_ASSERT(!def
->output()->isRegister());
3596 MOZ_ASSERT(!def
->output()->isStackSlot());
3597 spillSet
->setAllocation(*def
->output());
3604 LDefinition::Type type
=
3605 spillSet
->spilledBundle(0)->firstRange()->vreg().type();
3607 SpillSlotList
* slotList
;
3608 switch (StackSlotAllocator::width(type
)) {
3610 slotList
= &normalSlots
;
3613 slotList
= &doubleSlots
;
3616 slotList
= &quadSlots
;
3619 MOZ_CRASH("Bad width");
3622 // Maximum number of existing spill slots we will look at before giving up
3623 // and allocating a new slot.
3624 static const size_t MAX_SEARCH_COUNT
= 10;
3626 size_t searches
= 0;
3627 SpillSlot
* stop
= nullptr;
3628 while (!slotList
->empty()) {
3629 SpillSlot
* spillSlot
= *slotList
->begin();
3632 } else if (stop
== spillSlot
) {
3633 // We looked through every slot in the list.
3637 bool success
= true;
3638 for (size_t i
= 0; i
< spillSet
->numSpilledBundles(); i
++) {
3639 LiveBundle
* bundle
= spillSet
->spilledBundle(i
);
3640 for (LiveRange::BundleLinkIterator iter
= bundle
->rangesBegin(); iter
;
3642 LiveRange
* range
= LiveRange::get(*iter
);
3643 LiveRangePlus
rangePlus(range
);
3644 LiveRangePlus existingPlus
;
3645 if (spillSlot
->allocated
.contains(rangePlus
, &existingPlus
)) {
3655 // We can reuse this physical stack slot for the new bundles.
3656 // Update the allocated ranges for the slot.
3657 for (size_t i
= 0; i
< spillSet
->numSpilledBundles(); i
++) {
3658 LiveBundle
* bundle
= spillSet
->spilledBundle(i
);
3659 if (!insertAllRanges(spillSlot
->allocated
, bundle
)) {
3663 spillSet
->setAllocation(spillSlot
->alloc
);
3667 // On a miss, move the spill to the end of the list. This will cause us
3668 // to make fewer attempts to allocate from slots with a large and
3669 // highly contended range.
3670 slotList
->popFront();
3671 slotList
->pushBack(spillSlot
);
3673 if (++searches
== MAX_SEARCH_COUNT
) {
3678 // We need a new physical stack slot.
3679 uint32_t stackSlot
= stackSlotAllocator
.allocateSlot(type
);
3681 SpillSlot
* spillSlot
=
3682 new (alloc().fallible()) SpillSlot(stackSlot
, alloc().lifoAlloc());
3687 for (size_t i
= 0; i
< spillSet
->numSpilledBundles(); i
++) {
3688 LiveBundle
* bundle
= spillSet
->spilledBundle(i
);
3689 if (!insertAllRanges(spillSlot
->allocated
, bundle
)) {
3694 spillSet
->setAllocation(spillSlot
->alloc
);
3696 slotList
->pushFront(spillSlot
);
3700 bool BacktrackingAllocator::pickStackSlots() {
3701 for (size_t i
= 1; i
< graph
.numVirtualRegisters(); i
++) {
3702 VirtualRegister
& reg
= vregs
[i
];
3704 if (mir
->shouldCancel("Backtracking Pick Stack Slots")) {
3708 for (LiveRange::RegisterLinkIterator iter
= reg
.rangesBegin(); iter
;
3710 LiveRange
* range
= LiveRange::get(*iter
);
3711 LiveBundle
* bundle
= range
->bundle();
3713 if (bundle
->allocation().isBogus()) {
3714 if (!pickStackSlot(bundle
->spillSet())) {
3717 MOZ_ASSERT(!bundle
->allocation().isBogus());
3725 // Helper for ::createMoveGroupsFromLiveRangeTransitions
3726 bool BacktrackingAllocator::moveAtEdge(LBlock
* predecessor
, LBlock
* successor
,
3727 LiveRange
* from
, LiveRange
* to
,
3728 LDefinition::Type type
) {
3729 if (successor
->mir()->numPredecessors() > 1) {
3730 MOZ_ASSERT(predecessor
->mir()->numSuccessors() == 1);
3731 return moveAtExit(predecessor
, from
, to
, type
);
3734 return moveAtEntry(successor
, from
, to
, type
);
3737 // Helper for ::createMoveGroupsFromLiveRangeTransitions
3738 bool BacktrackingAllocator::deadRange(LiveRange
* range
) {
3739 // Check for direct uses of this range.
3740 if (range
->hasUses() || range
->hasDefinition()) {
3744 CodePosition start
= range
->from();
3745 LNode
* ins
= insData
[start
];
3746 if (start
== entryOf(ins
->block())) {
3750 VirtualRegister
& reg
= range
->vreg();
3752 // Check if there are later ranges for this vreg.
3753 LiveRange::RegisterLinkIterator iter
= reg
.rangesBegin(range
);
3754 for (iter
++; iter
; iter
++) {
3755 LiveRange
* laterRange
= LiveRange::get(*iter
);
3756 if (laterRange
->from() > range
->from()) {
3761 // Check if this range ends at a loop backedge.
3762 LNode
* last
= insData
[range
->to().previous()];
3763 if (last
->isGoto() &&
3764 last
->toGoto()->target()->id() < last
->block()->mir()->id()) {
3768 // Check if there are phis which this vreg flows to.
3769 if (reg
.usedByPhi()) {
3776 bool BacktrackingAllocator::createMoveGroupsFromLiveRangeTransitions() {
3777 // Add moves to handle changing assignments for vregs over their lifetime.
3778 JitSpew(JitSpew_RegAlloc
, "ResolveControlFlow: begin");
3780 JitSpew(JitSpew_RegAlloc
,
3781 " ResolveControlFlow: adding MoveGroups within blocks");
3783 // Look for places where a register's assignment changes in the middle of a
3785 MOZ_ASSERT(!vregs
[0u].hasRanges());
3786 for (size_t i
= 1; i
< graph
.numVirtualRegisters(); i
++) {
3787 VirtualRegister
& reg
= vregs
[i
];
3789 if (mir
->shouldCancel(
3790 "Backtracking Resolve Control Flow (vreg outer loop)")) {
3794 for (LiveRange::RegisterLinkIterator iter
= reg
.rangesBegin(); iter
;) {
3795 LiveRange
* range
= LiveRange::get(*iter
);
3797 if (mir
->shouldCancel(
3798 "Backtracking Resolve Control Flow (vreg inner loop)")) {
3802 // Remove ranges which will never be used.
3803 if (deadRange(range
)) {
3804 reg
.removeRangeAndIncrement(iter
);
3808 // The range which defines the register does not have a predecessor
3809 // to add moves from.
3810 if (range
->hasDefinition()) {
3815 // Ignore ranges that start at block boundaries. We will handle
3816 // these in the next phase.
3817 CodePosition start
= range
->from();
3818 LNode
* ins
= insData
[start
];
3819 if (start
== entryOf(ins
->block())) {
3824 // If we already saw a range which covers the start of this range
3825 // and has the same allocation, we don't need an explicit move at
3826 // the start of this range.
3828 for (LiveRange::RegisterLinkIterator prevIter
= reg
.rangesBegin();
3829 prevIter
!= iter
; prevIter
++) {
3830 LiveRange
* prevRange
= LiveRange::get(*prevIter
);
3831 if (prevRange
->covers(start
) && prevRange
->bundle()->allocation() ==
3832 range
->bundle()->allocation()) {
3842 if (!alloc().ensureBallast()) {
3846 LiveRange
* predecessorRange
=
3847 reg
.rangeFor(start
.previous(), /* preferRegister = */ true);
3848 if (start
.subpos() == CodePosition::INPUT
) {
3849 JitSpewIfEnabled(JitSpew_RegAlloc
, " moveInput (%s) <- (%s)",
3850 range
->toString().get(),
3851 predecessorRange
->toString().get());
3852 if (!moveInput(ins
->toInstruction(), predecessorRange
, range
,
3857 JitSpew(JitSpew_RegAlloc
, " (moveAfter)");
3858 if (!moveAfter(ins
->toInstruction(), predecessorRange
, range
,
3868 JitSpew(JitSpew_RegAlloc
,
3869 " ResolveControlFlow: adding MoveGroups for phi nodes");
3871 for (size_t i
= 0; i
< graph
.numBlocks(); i
++) {
3872 if (mir
->shouldCancel("Backtracking Resolve Control Flow (block loop)")) {
3876 LBlock
* successor
= graph
.getBlock(i
);
3877 MBasicBlock
* mSuccessor
= successor
->mir();
3878 if (mSuccessor
->numPredecessors() < 1) {
3882 // Resolve phis to moves.
3883 for (size_t j
= 0; j
< successor
->numPhis(); j
++) {
3884 LPhi
* phi
= successor
->getPhi(j
);
3885 MOZ_ASSERT(phi
->numDefs() == 1);
3886 LDefinition
* def
= phi
->getDef(0);
3887 VirtualRegister
& reg
= vreg(def
);
3888 LiveRange
* to
= reg
.rangeFor(entryOf(successor
));
3891 for (size_t k
= 0; k
< mSuccessor
->numPredecessors(); k
++) {
3892 LBlock
* predecessor
= mSuccessor
->getPredecessor(k
)->lir();
3893 MOZ_ASSERT(predecessor
->mir()->numSuccessors() == 1);
3895 LAllocation
* input
= phi
->getOperand(k
);
3896 LiveRange
* from
= vreg(input
).rangeFor(exitOf(predecessor
),
3897 /* preferRegister = */ true);
3900 if (!alloc().ensureBallast()) {
3904 // Note: we have to use moveAtEdge both here and below (for edge
3905 // resolution) to avoid conflicting moves. See bug 1493900.
3906 JitSpew(JitSpew_RegAlloc
, " (moveAtEdge#1)");
3907 if (!moveAtEdge(predecessor
, successor
, from
, to
, def
->type())) {
3914 JitSpew(JitSpew_RegAlloc
,
3915 " ResolveControlFlow: adding MoveGroups to fix conflicted edges");
3917 // Add moves to resolve graph edges with different allocations at their
3918 // source and target.
3919 for (size_t i
= 1; i
< graph
.numVirtualRegisters(); i
++) {
3920 VirtualRegister
& reg
= vregs
[i
];
3921 for (LiveRange::RegisterLinkIterator iter
= reg
.rangesBegin(); iter
;
3923 LiveRange
* targetRange
= LiveRange::get(*iter
);
3925 size_t firstBlockId
= insData
[targetRange
->from()]->block()->mir()->id();
3926 if (!targetRange
->covers(entryOf(graph
.getBlock(firstBlockId
)))) {
3929 for (size_t id
= firstBlockId
; id
< graph
.numBlocks(); id
++) {
3930 LBlock
* successor
= graph
.getBlock(id
);
3931 if (!targetRange
->covers(entryOf(successor
))) {
3935 BitSet
& live
= liveIn
[id
];
3936 if (!live
.contains(i
)) {
3940 for (size_t j
= 0; j
< successor
->mir()->numPredecessors(); j
++) {
3941 LBlock
* predecessor
= successor
->mir()->getPredecessor(j
)->lir();
3942 if (targetRange
->covers(exitOf(predecessor
))) {
3946 if (!alloc().ensureBallast()) {
3949 JitSpew(JitSpew_RegAlloc
, " (moveAtEdge#2)");
3950 LiveRange
* from
= reg
.rangeFor(exitOf(predecessor
), true);
3951 if (!moveAtEdge(predecessor
, successor
, from
, targetRange
,
3960 JitSpew(JitSpew_RegAlloc
, "ResolveControlFlow: end");
3964 // Helper for ::addLiveRegistersForRange
3965 size_t BacktrackingAllocator::findFirstNonCallSafepoint(CodePosition from
) {
3967 for (; i
< graph
.numNonCallSafepoints(); i
++) {
3968 const LInstruction
* ins
= graph
.getNonCallSafepoint(i
);
3969 if (from
<= inputOf(ins
)) {
3976 // Helper for ::installAllocationsInLIR
3977 void BacktrackingAllocator::addLiveRegistersForRange(VirtualRegister
& reg
,
3979 // Fill in the live register sets for all non-call safepoints.
3980 LAllocation a
= range
->bundle()->allocation();
3981 if (!a
.isRegister()) {
3985 // Don't add output registers to the safepoint.
3986 CodePosition start
= range
->from();
3987 if (range
->hasDefinition() && !reg
.isTemp()) {
3988 #ifdef CHECK_OSIPOINT_REGISTERS
3989 // We don't add the output register to the safepoint,
3990 // but it still might get added as one of the inputs.
3991 // So eagerly add this reg to the safepoint clobbered registers.
3992 if (reg
.ins()->isInstruction()) {
3993 if (LSafepoint
* safepoint
= reg
.ins()->toInstruction()->safepoint()) {
3994 safepoint
->addClobberedRegister(a
.toRegister());
3998 start
= start
.next();
4001 size_t i
= findFirstNonCallSafepoint(start
);
4002 for (; i
< graph
.numNonCallSafepoints(); i
++) {
4003 LInstruction
* ins
= graph
.getNonCallSafepoint(i
);
4004 CodePosition pos
= inputOf(ins
);
4006 // Safepoints are sorted, so we can shortcut out of this loop
4007 // if we go out of range.
4008 if (range
->to() <= pos
) {
4012 MOZ_ASSERT(range
->covers(pos
));
4014 LSafepoint
* safepoint
= ins
->safepoint();
4015 safepoint
->addLiveRegister(a
.toRegister());
4017 #ifdef CHECK_OSIPOINT_REGISTERS
4019 safepoint
->addClobberedRegister(a
.toRegister());
4025 // Helper for ::installAllocationsInLIR
4026 static inline size_t NumReusingDefs(LInstruction
* ins
) {
4028 for (size_t i
= 0; i
< ins
->numDefs(); i
++) {
4029 LDefinition
* def
= ins
->getDef(i
);
4030 if (def
->policy() == LDefinition::MUST_REUSE_INPUT
) {
4037 bool BacktrackingAllocator::installAllocationsInLIR() {
4038 JitSpew(JitSpew_RegAlloc
, "Installing Allocations");
4040 MOZ_ASSERT(!vregs
[0u].hasRanges());
4041 for (size_t i
= 1; i
< graph
.numVirtualRegisters(); i
++) {
4042 VirtualRegister
& reg
= vregs
[i
];
4044 if (mir
->shouldCancel("Backtracking Install Allocations (main loop)")) {
4048 for (LiveRange::RegisterLinkIterator iter
= reg
.rangesBegin(); iter
;
4050 LiveRange
* range
= LiveRange::get(*iter
);
4052 if (range
->hasDefinition()) {
4053 reg
.def()->setOutput(range
->bundle()->allocation());
4054 if (reg
.ins()->recoversInput()) {
4055 LSnapshot
* snapshot
= reg
.ins()->toInstruction()->snapshot();
4056 for (size_t i
= 0; i
< snapshot
->numEntries(); i
++) {
4057 LAllocation
* entry
= snapshot
->getEntry(i
);
4058 if (entry
->isUse() &&
4059 entry
->toUse()->policy() == LUse::RECOVERED_INPUT
) {
4060 *entry
= *reg
.def()->output();
4066 for (UsePositionIterator
iter(range
->usesBegin()); iter
; iter
++) {
4067 LAllocation
* alloc
= iter
->use();
4068 *alloc
= range
->bundle()->allocation();
4070 // For any uses which feed into MUST_REUSE_INPUT definitions,
4071 // add copies if the use and def have different allocations.
4072 LNode
* ins
= insData
[iter
->pos
];
4073 if (LDefinition
* def
= FindReusingDefOrTemp(ins
, alloc
)) {
4074 LiveRange
* outputRange
= vreg(def
).rangeFor(outputOf(ins
));
4075 LAllocation res
= outputRange
->bundle()->allocation();
4076 LAllocation sourceAlloc
= range
->bundle()->allocation();
4078 if (res
!= *alloc
) {
4079 if (!this->alloc().ensureBallast()) {
4082 if (NumReusingDefs(ins
->toInstruction()) <= 1) {
4083 LMoveGroup
* group
= getInputMoveGroup(ins
->toInstruction());
4084 if (!group
->addAfter(sourceAlloc
, res
, reg
.type())) {
4088 LMoveGroup
* group
= getFixReuseMoveGroup(ins
->toInstruction());
4089 if (!group
->add(sourceAlloc
, res
, reg
.type())) {
4098 addLiveRegistersForRange(reg
, range
);
4102 graph
.setLocalSlotsSize(stackSlotAllocator
.stackHeight());
4106 // Helper for ::populateSafepoints
4107 size_t BacktrackingAllocator::findFirstSafepoint(CodePosition pos
,
4109 size_t i
= startFrom
;
4110 for (; i
< graph
.numSafepoints(); i
++) {
4111 LInstruction
* ins
= graph
.getSafepoint(i
);
4112 if (pos
<= inputOf(ins
)) {
4119 // Helper for ::populateSafepoints
4120 static inline bool IsNunbox(VirtualRegister
& reg
) {
4122 return reg
.type() == LDefinition::TYPE
|| reg
.type() == LDefinition::PAYLOAD
;
4128 // Helper for ::populateSafepoints
4129 static inline bool IsSlotsOrElements(VirtualRegister
& reg
) {
4130 return reg
.type() == LDefinition::SLOTS
;
4133 // Helper for ::populateSafepoints
4134 static inline bool IsTraceable(VirtualRegister
& reg
) {
4135 if (reg
.type() == LDefinition::OBJECT
||
4136 reg
.type() == LDefinition::WASM_ANYREF
) {
4140 if (reg
.type() == LDefinition::BOX
) {
4144 if (reg
.type() == LDefinition::STACKRESULTS
) {
4145 MOZ_ASSERT(reg
.def());
4146 const LStackArea
* alloc
= reg
.def()->output()->toStackArea();
4147 for (auto iter
= alloc
->results(); iter
; iter
.next()) {
4148 if (iter
.isWasmAnyRef()) {
4156 bool BacktrackingAllocator::populateSafepoints() {
4157 JitSpew(JitSpew_RegAlloc
, "Populating Safepoints");
4159 size_t firstSafepoint
= 0;
4161 MOZ_ASSERT(!vregs
[0u].def());
4162 for (uint32_t i
= 1; i
< graph
.numVirtualRegisters(); i
++) {
4163 VirtualRegister
& reg
= vregs
[i
];
4166 (!IsTraceable(reg
) && !IsSlotsOrElements(reg
) && !IsNunbox(reg
))) {
4170 firstSafepoint
= findFirstSafepoint(inputOf(reg
.ins()), firstSafepoint
);
4171 if (firstSafepoint
>= graph
.numSafepoints()) {
4175 for (LiveRange::RegisterLinkIterator iter
= reg
.rangesBegin(); iter
;
4177 LiveRange
* range
= LiveRange::get(*iter
);
4179 for (size_t j
= firstSafepoint
; j
< graph
.numSafepoints(); j
++) {
4180 LInstruction
* ins
= graph
.getSafepoint(j
);
4182 if (!range
->covers(inputOf(ins
))) {
4183 if (inputOf(ins
) >= range
->to()) {
4189 // Include temps but not instruction outputs. Also make sure
4190 // MUST_REUSE_INPUT is not used with gcthings or nunboxes, or
4191 // we would have to add the input reg to this safepoint.
4192 if (ins
== reg
.ins() && !reg
.isTemp()) {
4193 DebugOnly
<LDefinition
*> def
= reg
.def();
4194 MOZ_ASSERT_IF(def
->policy() == LDefinition::MUST_REUSE_INPUT
,
4195 def
->type() == LDefinition::GENERAL
||
4196 def
->type() == LDefinition::INT32
||
4197 def
->type() == LDefinition::FLOAT32
||
4198 def
->type() == LDefinition::DOUBLE
||
4199 def
->type() == LDefinition::SIMD128
);
4203 LSafepoint
* safepoint
= ins
->safepoint();
4205 LAllocation a
= range
->bundle()->allocation();
4206 if (a
.isGeneralReg() && ins
->isCall()) {
4210 switch (reg
.type()) {
4211 case LDefinition::OBJECT
:
4212 if (!safepoint
->addGcPointer(a
)) {
4216 case LDefinition::SLOTS
:
4217 if (!safepoint
->addSlotsOrElementsPointer(a
)) {
4221 case LDefinition::WASM_ANYREF
:
4222 if (!safepoint
->addWasmAnyRef(a
)) {
4226 case LDefinition::STACKRESULTS
: {
4227 MOZ_ASSERT(a
.isStackArea());
4228 for (auto iter
= a
.toStackArea()->results(); iter
; iter
.next()) {
4229 if (iter
.isWasmAnyRef()) {
4230 if (!safepoint
->addWasmAnyRef(iter
.alloc())) {
4238 case LDefinition::TYPE
:
4239 if (!safepoint
->addNunboxType(i
, a
)) {
4243 case LDefinition::PAYLOAD
:
4244 if (!safepoint
->addNunboxPayload(i
, a
)) {
4249 case LDefinition::BOX
:
4250 if (!safepoint
->addBoxedValue(a
)) {
4256 MOZ_CRASH("Bad register type");
4265 bool BacktrackingAllocator::annotateMoveGroups() {
4266 // Annotate move groups in the LIR graph with any register that is not
4267 // allocated at that point and can be used as a scratch register. This is
4268 // only required for x86, as other platforms always have scratch registers
4269 // available for use.
4270 #ifdef JS_CODEGEN_X86
4271 LiveRange
* range
= LiveRange::FallibleNew(alloc(), nullptr, CodePosition(),
4272 CodePosition().next());
4277 for (size_t i
= 0; i
< graph
.numBlocks(); i
++) {
4278 if (mir
->shouldCancel("Backtracking Annotate Move Groups")) {
4282 LBlock
* block
= graph
.getBlock(i
);
4283 LInstruction
* last
= nullptr;
4284 for (LInstructionIterator iter
= block
->begin(); iter
!= block
->end();
4286 if (iter
->isMoveGroup()) {
4287 CodePosition from
= last
? outputOf(last
) : entryOf(block
);
4288 range
->setTo(from
.next());
4289 range
->setFrom(from
);
4291 for (size_t i
= 0; i
< AnyRegister::Total
; i
++) {
4292 PhysicalRegister
& reg
= registers
[i
];
4293 if (reg
.reg
.isFloat() || !reg
.allocatable
) {
4297 // This register is unavailable for use if (a) it is in use
4298 // by some live range immediately before the move group,
4299 // or (b) it is an operand in one of the group's moves. The
4300 // latter case handles live ranges which end immediately
4301 // before the move group or start immediately after.
4302 // For (b) we need to consider move groups immediately
4303 // preceding or following this one.
4305 if (iter
->toMoveGroup()->uses(reg
.reg
.gpr())) {
4309 LInstructionIterator
niter(iter
);
4310 for (niter
++; niter
!= block
->end(); niter
++) {
4311 if (niter
->isMoveGroup()) {
4312 if (niter
->toMoveGroup()->uses(reg
.reg
.gpr())) {
4320 if (iter
!= block
->begin()) {
4321 LInstructionIterator
riter(iter
);
4324 if (riter
->isMoveGroup()) {
4325 if (riter
->toMoveGroup()->uses(reg
.reg
.gpr())) {
4332 } while (riter
!= block
->begin());
4338 LiveRangePlus existingPlus
;
4339 LiveRangePlus
rangePlus(range
);
4340 if (reg
.allocations
.contains(rangePlus
, &existingPlus
)) {
4344 iter
->toMoveGroup()->setScratchRegister(reg
.reg
.gpr());
4357 ///////////////////////////////////////////////////////////////////////////////
4359 // Debug-printing support //
4361 ///////////////////////////////////////////////////////////////////////////////
4365 UniqueChars
LiveRange::toString() const {
4366 AutoEnterOOMUnsafeRegion oomUnsafe
;
4368 UniqueChars buf
= JS_smprintf("v%u %u-%u", hasVreg() ? vreg().vreg() : 0,
4369 from().bits(), to().bits() - 1);
4371 if (buf
&& bundle() && !bundle()->allocation().isBogus()) {
4372 buf
= JS_sprintf_append(std::move(buf
), " %s",
4373 bundle()->allocation().toString().get());
4376 buf
= JS_sprintf_append(std::move(buf
), " {");
4378 if (buf
&& hasDefinition()) {
4379 buf
= JS_sprintf_append(std::move(buf
), " %u_def", from().bits());
4381 // If the definition has a fixed requirement, print it too.
4382 const LDefinition
* def
= vreg().def();
4383 LDefinition::Policy policy
= def
->policy();
4384 if (policy
== LDefinition::FIXED
|| policy
== LDefinition::STACK
) {
4386 buf
= JS_sprintf_append(std::move(buf
), ":F:%s",
4387 def
->output()->toString().get());
4393 for (UsePositionIterator iter
= usesBegin(); buf
&& iter
; iter
++) {
4394 buf
= JS_sprintf_append(std::move(buf
), " %u_%s", iter
->pos
.bits(),
4395 iter
->use()->toString().get());
4398 buf
= JS_sprintf_append(std::move(buf
), " }");
4401 oomUnsafe
.crash("LiveRange::toString()");
4407 UniqueChars
LiveBundle::toString() const {
4408 AutoEnterOOMUnsafeRegion oomUnsafe
;
4410 UniqueChars buf
= JS_smprintf("LB%u(", debugId());
4413 if (spillParent()) {
4414 buf
= JS_sprintf_append(std::move(buf
), "parent=LB%u",
4415 spillParent()->debugId());
4417 buf
= JS_sprintf_append(std::move(buf
), "parent=none");
4421 for (LiveRange::BundleLinkIterator iter
= rangesBegin(); buf
&& iter
;
4424 buf
= JS_sprintf_append(std::move(buf
), "%s %s",
4425 (iter
== rangesBegin()) ? "" : " ##",
4426 LiveRange::get(*iter
)->toString().get());
4431 buf
= JS_sprintf_append(std::move(buf
), ")");
4435 oomUnsafe
.crash("LiveBundle::toString()");
4441 void BacktrackingAllocator::dumpLiveRangesByVReg(const char* who
) {
4442 MOZ_ASSERT(!vregs
[0u].hasRanges());
4444 JitSpewCont(JitSpew_RegAlloc
, "\n");
4445 JitSpew(JitSpew_RegAlloc
, "Live ranges by virtual register (%s):", who
);
4447 for (uint32_t i
= 1; i
< graph
.numVirtualRegisters(); i
++) {
4448 JitSpewHeader(JitSpew_RegAlloc
);
4449 JitSpewCont(JitSpew_RegAlloc
, " ");
4450 VirtualRegister
& reg
= vregs
[i
];
4451 for (LiveRange::RegisterLinkIterator iter
= reg
.rangesBegin(); iter
;
4453 if (iter
!= reg
.rangesBegin()) {
4454 JitSpewCont(JitSpew_RegAlloc
, " ## ");
4456 JitSpewCont(JitSpew_RegAlloc
, "%s",
4457 LiveRange::get(*iter
)->toString().get());
4459 JitSpewCont(JitSpew_RegAlloc
, "\n");
4463 void BacktrackingAllocator::dumpLiveRangesByBundle(const char* who
) {
4464 MOZ_ASSERT(!vregs
[0u].hasRanges());
4466 JitSpewCont(JitSpew_RegAlloc
, "\n");
4467 JitSpew(JitSpew_RegAlloc
, "Live ranges by bundle (%s):", who
);
4469 for (uint32_t i
= 1; i
< graph
.numVirtualRegisters(); i
++) {
4470 VirtualRegister
& reg
= vregs
[i
];
4471 for (LiveRange::RegisterLinkIterator baseIter
= reg
.rangesBegin(); baseIter
;
4473 LiveRange
* range
= LiveRange::get(*baseIter
);
4474 LiveBundle
* bundle
= range
->bundle();
4475 if (range
== bundle
->firstRange()) {
4476 JitSpew(JitSpew_RegAlloc
, " %s", bundle
->toString().get());
4482 void BacktrackingAllocator::dumpAllocations() {
4483 JitSpew(JitSpew_RegAlloc
, "Allocations:");
4485 dumpLiveRangesByBundle("in dumpAllocations()");
4487 JitSpewCont(JitSpew_RegAlloc
, "\n");
4488 JitSpew(JitSpew_RegAlloc
, "Allocations by physical register:");
4490 for (size_t i
= 0; i
< AnyRegister::Total
; i
++) {
4491 if (registers
[i
].allocatable
&& !registers
[i
].allocations
.empty()) {
4492 JitSpewHeader(JitSpew_RegAlloc
);
4493 JitSpewCont(JitSpew_RegAlloc
, " %s:", AnyRegister::FromCode(i
).name());
4495 LiveRangePlusSet::Iter
lrpIter(®isters
[i
].allocations
);
4496 while (lrpIter
.hasMore()) {
4497 LiveRange
* range
= lrpIter
.next().liveRange();
4501 fprintf(stderr
, " /");
4503 fprintf(stderr
, " %s", range
->toString().get());
4505 JitSpewCont(JitSpew_RegAlloc
, "\n");
4509 JitSpewCont(JitSpew_RegAlloc
, "\n");
4512 #endif // JS_JITSPEW
4514 ///////////////////////////////////////////////////////////////////////////////
4516 // Top level of the register allocation machinery //
4518 ///////////////////////////////////////////////////////////////////////////////
4520 bool BacktrackingAllocator::go() {
4521 JitSpewCont(JitSpew_RegAlloc
, "\n");
4522 JitSpew(JitSpew_RegAlloc
, "Beginning register allocation");
4524 JitSpewCont(JitSpew_RegAlloc
, "\n");
4525 if (JitSpewEnabled(JitSpew_RegAlloc
)) {
4526 dumpInstructions("(Pre-allocation LIR)");
4533 if (!buildLivenessInfo()) {
4538 if (JitSpewEnabled(JitSpew_RegAlloc
)) {
4539 dumpLiveRangesByVReg("after liveness analysis");
4543 if (!allocationQueue
.reserve(graph
.numVirtualRegisters() * 3 / 2)) {
4547 JitSpewCont(JitSpew_RegAlloc
, "\n");
4548 JitSpew(JitSpew_RegAlloc
, "Beginning grouping and queueing registers");
4549 if (!mergeAndQueueRegisters()) {
4552 JitSpew(JitSpew_RegAlloc
, "Completed grouping and queueing registers");
4555 if (JitSpewEnabled(JitSpew_RegAlloc
)) {
4556 dumpLiveRangesByBundle("after grouping/queueing regs");
4560 // There now follow two allocation loops, which are really the heart of the
4561 // allocator. First, the "main" allocation loop. This does almost all of
4562 // the allocation work, by repeatedly pulling bundles out of
4563 // ::allocationQueue and calling ::processBundle on it, until there are no
4564 // bundles left in the queue. Note that ::processBundle can add new smaller
4565 // bundles to the queue if it needs to split or spill a bundle.
4567 // For each bundle in turn pulled out of ::allocationQueue, ::processBundle:
4569 // * calls ::computeRequirement to discover the overall constraint for the
4572 // * tries to find a register for it, by calling either ::tryAllocateFixed or
4573 // ::tryAllocateNonFixed.
4575 // * if that fails, but ::tryAllocateFixed / ::tryAllocateNonFixed indicate
4576 // that there is some other bundle with lower spill weight that can be
4577 // evicted, then that bundle is evicted (hence, put back into
4578 // ::allocationQueue), and we try again.
4580 // * at most MAX_ATTEMPTS may be made.
4582 // * If that still fails to find a register, then the bundle is handed off to
4583 // ::chooseBundleSplit. That will choose to either split the bundle,
4584 // yielding multiple pieces which are put back into ::allocationQueue, or
4585 // it will spill the bundle. Note that the same mechanism applies to both;
4586 // there's no clear boundary between splitting and spilling, because
4587 // spilling can be interpreted as an extreme form of splitting.
4589 // ::processBundle and its callees contains much gnarly and logic which isn't
4590 // easy to understand, particularly in the area of how eviction candidates
4591 // are chosen. But it works well enough, and tinkering doesn't seem to
4592 // improve the resulting allocations. More important is the splitting logic,
4593 // because that controls where spill/reload instructions are placed.
4595 // Eventually ::allocationQueue becomes empty, and each LiveBundle has either
4596 // been allocated a register or is marked for spilling. In the latter case
4597 // it will have been added to ::spilledBundles.
4599 JitSpewCont(JitSpew_RegAlloc
, "\n");
4600 JitSpew(JitSpew_RegAlloc
, "Beginning main allocation loop");
4601 JitSpewCont(JitSpew_RegAlloc
, "\n");
4603 // Allocate, spill and split bundles until finished.
4604 while (!allocationQueue
.empty()) {
4605 if (mir
->shouldCancel("Backtracking Allocation")) {
4609 QueueItem item
= allocationQueue
.removeHighest();
4610 if (!processBundle(mir
, item
.bundle
)) {
4615 // And here's the second allocation loop (hidden inside
4616 // ::tryAllocatingRegistersForSpillBundles). It makes one last attempt to
4617 // find a register for each spill bundle. There's no attempt to free up
4618 // registers by eviction. In at least 99% of cases this attempt fails, in
4619 // which case the bundle is handed off to ::spill. The lucky remaining 1%
4620 // get a register. Unfortunately this scheme interacts badly with the
4621 // splitting strategy, leading to excessive register-to-register copying in
4622 // some very simple cases. See bug 1752520.
4624 // A modest but probably worthwhile amount of allocation time can be saved by
4625 // making ::tryAllocatingRegistersForSpillBundles use specialised versions of
4626 // ::tryAllocateAnyRegister and its callees, that don't bother to create sets
4627 // of conflicting bundles. Creating those sets is expensive and, here,
4628 // pointless, since we're not going to do any eviction based on them. This
4629 // refinement is implemented in the un-landed patch at bug 1758274 comment
4632 JitSpewCont(JitSpew_RegAlloc
, "\n");
4633 JitSpew(JitSpew_RegAlloc
,
4634 "Main allocation loop complete; "
4635 "beginning spill-bundle allocation loop");
4636 JitSpewCont(JitSpew_RegAlloc
, "\n");
4638 if (!tryAllocatingRegistersForSpillBundles()) {
4642 JitSpewCont(JitSpew_RegAlloc
, "\n");
4643 JitSpew(JitSpew_RegAlloc
, "Spill-bundle allocation loop complete");
4644 JitSpewCont(JitSpew_RegAlloc
, "\n");
4646 if (!pickStackSlots()) {
4651 if (JitSpewEnabled(JitSpew_RegAlloc
)) {
4656 if (!createMoveGroupsFromLiveRangeTransitions()) {
4660 if (!installAllocationsInLIR()) {
4664 if (!populateSafepoints()) {
4668 if (!annotateMoveGroups()) {
4672 JitSpewCont(JitSpew_RegAlloc
, "\n");
4673 if (JitSpewEnabled(JitSpew_RegAlloc
)) {
4674 dumpInstructions("(Post-allocation LIR)");
4677 JitSpew(JitSpew_RegAlloc
, "Finished register allocation");
4682 ///////////////////////////////////////////////////////////////////////////////
4684 ///////////////////////////////////////////////////////////////////////////////