From 43316b84a9cc0b7ac03a4d85fa4f4dff0f26ccd5 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 7 Feb 2025 09:12:14 -0800 Subject: Chapter 20: Graph Coloring Register Allocation MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: godalming123 <68993177+godalming123@users.noreply.github.com> Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- docs/chapter20/README.md | 529 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 529 insertions(+) create mode 100644 docs/chapter20/README.md (limited to 'docs/chapter20/README.md') diff --git a/docs/chapter20/README.md b/docs/chapter20/README.md new file mode 100644 index 00000000..543bbd84 --- /dev/null +++ b/docs/chapter20/README.md @@ -0,0 +1,529 @@ +# Chapter 20: Graph Coloring Register Allocation + +English | [日本語](README.ja.md) + +[Previous: Chapter 19](../chapter19/README.md) | +[Next: Chapter 21](../chapter21/README.md) + +The grammar is unchanged from [Chapter 18](../chapter18/18-grammar.md). + +## Some Reading Material + +This is a Briggs-Chaitin-Click allocator, and is very similar to the one used +in HotSpot's C2 allocator for the past 25 years with great success. + +Wikipedia has a nice overview of register allocation in general: https://en.wikipedia.org/wiki/Register_allocation + +Chaitin's original: https://en.wikipedia.org/wiki/Register_allocation#CITEREFChaitin1982 + +Briggs additions: https://dl.acm.org/doi/10.1145/177492.177575 + +Nice lecture slides pdf of Briggs/Chaitin: https://aktemur.github.io/cs544/lectures/chapter%2013%20registerAllocation.pdf + +There are several other useful links that can be found by searching for Briggs +or Chaitin in combination. Basically there was a spate of register allocation +improvements in this era that made it into many high-end mainstream compilers. + +I've included a very old unpublished paper on speeding up graph coloring +allocators: [Interference Graph Trimming](ifg_trim.pdf). + + +## Meta-Issues / Code-Dev Issues of Instruction Selection, Register Allocation and Encodings + +The output of Register Allocation - an allocation of registers to ops - is +difficult to test in bulk without an execution strategy. We won't have an +execution strategy until all three of Instruction Selection, Register Allocation +and Encodings are done. Hence in and around the completion of Encoding we +expect to find lots of bugs in Instruction Selection and Register Allocation. +We certainly hand-inspect the output and fix obvious problems, but still lots of +bugs linger until we can actually run the code. + +This means that other chapters have updates and bug-fixes to the work being +described here. + +Specific to the register allocator, we will be gradually adding improvements to +it, chapter by chapter for quite a few chapters. Register allocators generally +end with a large number of heuristics which we will add slowly. + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter20) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter19...linear-chapter20) it to the previous chapter. + + +## The Basic Theory + +The reading material includes several explanations of the basic concepts, but +at the risk of being redundant I'll present a short version again here. + +I assume you (the reader) know *why* register allocation is required: machine +registers are a high value finite resource, and as with all finite resources +they need to be allocated well. + +Graph Coloring is one such allocation method; machine registers are treated as +colors; a *live range interference graph* is built, with each *live range* +requiring its own register/color. Coloring the graph ensures every live range +gets a unique register, specifically when it overlaps or *interferes* with +another live range. + +A successful coloring ends the allocation and after some bookkeeping the +program is ready for e.g. code emission. A failed coloring requires spilling +or splitting conflicting live ranges; in this allocator we will be doing live +range *splitting*. Splitting live ranges makes them more colorable; they +become shorter with fewer interfering other live ranges. Generally large +functions might require a few rounds of splitting before becoming colorable. +Since the problem is NP-complete there are no guarantees here, the final +allocation quality becomes heavily dependent on splitting and coloring +heuristics. + +Hence, much of the "high theory" will be used to drive the core coloring +algorithm, but much of the actual success will depend on a large collection +of heuristics. + +### Coloring Rounds + +Coloring proceeds in rounds until we get a coloring: + +- Build the Live Ranges; live ranges require the same register for all + instructions in the live range. Phi functions will force unrelated def/use + edges to become part of the same live range and this can drive large + interconnected live ranges with a lot of conflicts. Some hardware ops + require the same register for both inputs and outputs (X86 is notorious here) + which also makes fewer larger live ranges. We'll be using the disjoint + Union-Find algorithm to rapidly build up live ranges in one forward pass over + the program. + +- Build the Interference Graph: every live range which is alive at the same time + as any other, now *interferes* or conflicts. This is built using a LIVE-ness + pass, which is a backwards pass over the CFG, and can require more than one + pass according to loop nesting depth. The data structure here is generally a + 2-D bitset, triangulated to cut its size in half. As part of LIVE, we'll + also have a set of reaching defs per-block. + +- Color the interference graph. Nodes (live ranges) in the graph which are + strictly low degree (more available registers than neighbors) are guaranteed + to get a color. These can be removed from the graph - since they will + guaranteed get a register (color) because they have so few conflicting + neighbors. Removing these trivial nodes makes more nodes go trivial, and + this process repeats until either we run out (and are guaranteed a coloring) + or we find a high-degree clique: a set of mutually interfering live ranges + where none of them are guaranteed a color. In this case we pull an "at risk" + live range out; this one might not color. Once the graph is emptied, we + reverse and re-insert the live ranges, coloring as we go. All the trivial + live ranges will color; the at-risk ones may or may not. + +- If every live range gets a color, then Register Allocation is done. If not, + we enter a round of splitting. Live ranges which did not color are now split + via a series of heuristics into lots of small live ranges. Splitting has a + tension: too much and you got a lot of spills (and a generally poor + allocation). Too little, and you remain uncolorable - and do not make + progress towards an allocation. Once we're done splitting, we start a new + round of coloring (Building the Live Ranges, then the Interference Graph, + then Coloring). + + +## Registers and Register Masks + +Registers are the thing that Register Allocation is all about! They are +represented as a small dense integer, starting up from 0, and the numbering +generally follows from the hardware encodings. So for an X86_64, RAX will be +register 0, RCX register 1 and so on up to the 16 GPRs. The XMM register numbers start at +16 and go through 31. Register numbers must be unique; this is how the register +allocator tracks them. + +#### Why a RegMask class and not a simple `long`? + +A collection of registers live in a Register Mask. For smaller and simpler +machines it suffices to make such masks an i64 or i128 (64 or 128 bit +integers), and this presentation is by far the better way to go... if all +register allocations can fit in this bit limitation. The allocator will need +bits for stack-based parameters and for splits which cannot get a register. +For a 32-register machine like the X86, add 1 for flags - gives 33 registers. +Using a Java `long` has 64 bits, leaving 31 for spills and stack passing. This +is adequate for nearly all allocations; only the largest allocations will run +this out. However, if we move to a chip with 64 registers we'll immediately +run out, and need at least a 128 bit mask. Since you cannot *return* a 128 +bit value directly in Java, Simple will pick up a `RegMask` class object. + +#### Stack Slots + +One of the Click extensions is this notion of treating "stack slots" as Just +Another Register. They get colored like other registers, which in turn leads +to very efficient use of the stack; C2 is known for having very small stack +frames. Another benefit is callee save registers will get split preferentially +(they have very long lifetime and only one def on entry and one use on +exit)... which the splits then end up coloring to the stack, building the call +prolog and epilog naturally. This allocator will not otherwise dedicate any +effort to stack frame management; it will "fall out in the wash". + +Many of the register masks are immutable; e.g. allowed registers for particular +opcodes, or describing registers for calling conventions. Other masks +represent mutable bitsets with the allocator routinely masking off bits when +accumulating a set of constraints. To help keep these uses apart, the +`RegMask` class includes mutable and immutable variants. + +#### Memory + +Memory edges exist to enforce ordering, but do not get any registers. +The allocator basically ignores them. + + +### Callee/Caller Save Registers + +In this allocator, callee- and caller-save registers get almost no special +treatment and no special prolog nor epilog is built to save and restore them. +At the start of the allocator, SoN graph edges are added between each `Return` +and a `CalleeSave` from each `Fun`. These edges are given register masks +pinning them to the callee-save set as defined by the normal ABI. + +Callee-save live ranges thus have a single def (a `CalleeSave` at function +start) and a single use (the `Return`), are cheap to spill and free a register +over a large area - they make ideal spill candidates. When the allocator needs +to spill something to get some more registers, these will be the first to +spill. A prolog and epilog will get built as a consequence of the normal live +range splitting process. + +`Calls` kill the caller-save registers (just the inverted callee-save mask), +and this is computed during the normal interference graph building process just +like any other operation that kills registers. Killing a bunch of registers at +a call typically removes all the free registers from whatever is currently +alive - and will thus force spilling... which will quickly end up spilling +callee-save registers as ideal candidates. + + +## Live Ranges + +A live range is a set of nodes and edges which must get the same register. +Live ranges form an interconnected web with almost no limits on their shape. +Live ranges also gather the set of register constraints from all their parts. + +Live ranges are held in `LRG` class instances. Most of the fields in this +class are for spill heuristics, but there are a few key ones that define what a +LRG is. `RegAlloc` has several functions dealing with LRGs, including a lookup +table from Nodes i.e., a mapping from `Node` to `LRG` (which is very similar to +having a dedicated LRG field in each Node... except that LRGs are only used +during RegAlloc and the field would be dead weight otherwise). + +LRGs have a unique dense integer `_lrg` number which names the LRG. New `_lrg` +numbers come from the `RegAlloc._lrg_num` counter. LRGs can be unioned +together - +[this is the Union-Find algorithm](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) +- and when this happens the lower numbered `_lrg` wins. Unioning only happens +during `BuildLRG` and happens because either a `Phi` is forcing all its inputs +and outputs into the same register, or because of a 2-address instruction. +LRGs have matching `union` and `find` calls, and a set `_leader` field. + +Post-allocation the `LRG._reg` field holds the chosen register. During +allocation the `LRG._mask` field holds the set of available registers, +typically all the defaults, minus various conflicts. + +The `LRG._adj` holds a list of adjacent neighbors as part of the larger +Interference Graph, and is only used during the Coloring phase. +[See more about graphs here.](https://en.wikipedia.org/wiki/Graph_(abstract_data_type)) +This is an "adjacency list" form of a Graph description, and is built from the +IFG's 2-D collection of bits (itself a 1-D list of `BitSet`s). Graph coloring +register allocation is one of the few places where changing the layout of a +data structure mid-algorithm pays out. + +The rest of the fields are dedicated to various spilling heuristics: + +- `_machDef` `_machUse` `_uidx` - A sample def and use. +- `_splitDef` `_splitUse` - Sample splits involved with this LRG; biased + coloring attempts to align register choices to remove these. +- `_selfConflicts` - A partial set of *self-conflicting* nodes. These are + detected during the Interference Graph build phase, and require aggressive + splitting. +- `_1regDefCnt` `_1regUseCnt` - Count of defs and uses which are pinned to a + single register. These typically require a hard-split just before (use) or + after (def) to free up the register choices. + + +## Live Ranges and Conflicts + +If the live range `_mask` field goes empty, you might have a *hard conflict* or +have gotten *killed*. Live ranges can self-interfere, making a +*self-conflict*. During coloring you might discover an uncolorable clique of +interfering live ranges, leading to a *capacity spill*. This leads to a set of +levels of conflicts within a live range (and different heuristics for handling +them). + +### Hard-Conflicts + +A live range can have a *hard conflict*: conflicting register requirements, +leading to no valid register choices. The obvious case is an incoming +parameter fixed in e.g. `rdx` but also required as an exit value in `rax`. You +can't pick both registers at once, so a split is required. During the build +live ranges phase, every register constraint from every def and use are AND'd +together; the `RegMask` might lose all valid registers, or remain with just a +handful of register choices. + +Hard-conflicts are usually found while building live ranges, and will trigger a +round of splitting before building the interference graph or coloring. They +can also be found during interference graph building, generally caused by a +1-register kill. + +### Avoiding interferences + +One of the Click extensions to the Briggs-Chaitin allocator is to take +advantage of register constraints to lower the interference graph degree (which +otherwise becomes an O(n^2) edge collection). If a live range LR1 is reduced +to a single register (such as a call argument requiring `rdx`) and would +otherwise conflict with another live range LR2 which has more choices - we +remove `rdx` from the LR2's choices. Without having `rdx`, LR1 and LR2 have no +registers in common - and hence do not conflict. We just don't add the +interference graph edge between them. Call argument restrictions are very +common and this kind of edge-removal can dramatically shrink the O(n^2) edge +collection - and hence speedup allocation by a large constant factor. + +### Self-Conflicts + +A live-range can *self-conflict*: be alive twice with 2 different values but +require the same register. This live range *must* split and thus picks up a +copy from the split. This happens with loop-carried dependencies as seen in +e.g. a simple `fib` program: + +```java + int x=1, y=1; + while( true ) { + tmp = x + y; + y = x; + x = tmp; + }; + +``` + +In SoN SSA form: +```java + int x0 = 1, y0 = 1; + while( true ) { + x1 = phi(x0,x2); + y1 = phi(y0,x1); + x2 = x1 + y1; + } +``` + +The variables `x0,x1,x2,y0,y1` all form part of the same live range, since they +are all joined by `Phis`. However, `x1` and `y1` hold different values from +different iterations of `fib`. The SSA form does not have a copy, but the +register-allocated form - just like the original code - DOES require a copy. + +Self-conflicts are found during building the interference graph, and will +trigger a round of splits before attempting the coloring phase. + + +## Coloring Heuristics + +Both register coloring and register splitting are full of heuristics, and the +quality of these heuristics goes a long way to deciding the quality of the +final allocation. Graph coloring is NP-complete; there is no efficient +algorithm for coloring and many programs are simply not colorable without +splitting in any case. + + +### Biased Coloring + +Biased coloring is a heuristic that attempts to "pick a better color" or "bias +the color choice", such that a Split is removed. A Split splits one live range +into two; sometimes some are inserted that are not required (i.e., over- +splitting has already happened). If one side (live range) of a split is +already colored and we can color the other side (live range) the same color - +then this split can be removed. If neither side is colored, but one or the +other side is recursively connected to a colored live range, we can still bias +the color in the hopes that a chain of splits will all get the same color and +thus all get removed. + +When the coloring process is reversing, and colors are being picked for live +ranges, we often have many register choices. A first choice is made +arbitrarily (lowest numbered register), and then we go looking for a better +color. Biased coloring inspects first a sample def (if there is only one, then +the One Def is inspected), and then a sample use. Inspection looks to see if +"the other side" of a split is already colored; if so, and that color is +available it is chosen. If there is a split, but it is not colored - we +recursively repeat the process on that split's other side. This is also done +for the other input of two-address ops and one of a Phi node inputs. + +In all cases, the goal is to pick a valid available color - that might also +eventually be pick-able for this Split's other side - and lead to this split +having the same color for both sides, and then being removed. + + +### Pick Risky + +Here we are forced to pick one of several *live ranges* that form a large +clique: they have too many mutual neighbors so that no one of them is +guaranteed a color. There is a conflicting tension here: + +Picking a live range with a large "area" (i.e. covering much of the program), +and low "cost" to spill (i.e. fewer defs and uses, and outside of loops) will +give a large win. A register will become free over a large part of the program +and allow coloring to succeed elsewhere. The normal ABI callee-save registers +are ideal in this case, defined on entry and used only on exit they cover the +entire program. Also, spilling means only a single split on entry and another +at exit. Spilling such live ranges basically builds a classic function +prolog/epilog sequence. Here though, the allocator is allowed to e.g. spill +outside a fast-path exit. + +``` + // No registers saved if the initial RDI is null + test rdi + jne BIG_AND_SLOW + xor rax,rax + ret // Fast path exit: null argument means null result +BIG_AND_SLOW: + add rsp,#12 + mov [rsp+0],rbx // begin spilling callee-save registers + mov [rsp+4],r12 // + // lots of code needing callee-save registers +``` + +The other side of the tension is to pick live ranges that are likely to color +more by chance. If a live range is "very nearly colorable" - say only one more +neighbor than available registers/colors then by chance (and Biased Coloring) +some neighbors might use the same color... freeing up a color and allowing this +risky live range to color after all. + + +## Splitting + +Here we failed to get a coloring - and need to split. Some specific live +ranges did not color and we will need to decide how to split. Again there are +tensions here: too much splitting leads to a bad allocation, too little leads to +no-progress bugs (manifested as too many rounds of splitting past some +arbitrary cutoff). + +We start by sorting the spills to be deterministic (else they are sorted by +HashMap visitation order), then looking at each spilling live range in turn +and deciding on a splitting strategy. + + +### Split Self Conflict + +Self-conflict live ranges are discovered during the "Build the Interference +Graph" stage. If this happens we don't attempt a coloring (it's nonsensical +with self conflicts), but go straight to splitting. During the IFG building we +gathered a subset of the conflicting definitions for this live range. Now +we visit all those definition points and insert spills: + +- Before slot #1 on a Phi (which breaks loop-entry Phis from the loop-body) and + also after the Phi. +- Before a two-address instruction, breaking the live range before the op from + afterwards. +- Before any use that extends a live range. + +This set of splits is fairly aggressive... but test cases requiring a split in +each of the listed locations are included in Chapter 20's test cases. We +cannot even attempt a color while we have self conflicts, so it's important to +break up these live ranges quickly. This tends to over-split and the allocator +leans on Biased Coloring and the final copy cleanup to remove some of the +extras. Conservative coalescing will be introduced in a later chapter. + + +### Split Hard Conflict + +Hard conflicts are discovered during the "Build the Live Ranges" pass for +direct def/use conflicts (e.g. defined in `rdi` and used in `rax`). They also +can be discovered during the "Build the Interference Graph" pass (e.g. incoming +argument in `rdi` used later in the program and killed by a `Call`). + +For simple hard-conflicts (a single def and single use), we have the exact def +and use kept in the Live Range itself. We split once after the def and once +before the use (and only on sides with restricted registers). + +For more complex cases we use the capacity spilling/loop-nest technique. +Cloneable values can be recreated near their uses, but only when the clone's +output register class can satisfy that use. Otherwise we need a move. A fixed +register constant with flexible uses must also split at its uses; doing nothing +at its definition would repeat the same hard conflict forever. + +Popular constants (e.g. 0) often have many uses requiring different registers. +Grouping these uses into register classes can save moves, but we defer that +heuristic to a later chapter. + + +### Split By Loop Nest + +Here we typically see capacity spills: we just need more registers. This +easily happens when a `Call` crushes all the temporary registers and we need to +carry some values past the call - but it can also happen any time we have a +larger function with lots of things going on at once. + +The heuristic here is to split *around* loops, attempting to keep some free +registers available so the hot loop body does not spill. Live ranges are split +into successively deeper loop nests in progressive rounds of splitting, and in +the final case will split once after each def and before each use, even in the +innermost loop. + +The heuristic starts by discovering the min and max loop depth for all defs and +uses. If these vary, we will split *around* the outermost loop, putting in +splits at the loop border and keeping an inner untouched live range that has no +constraints from outside. If this fails to color, on the next round of +splitting the outermost loop will have moved in one layer, and we will be +splitting around the next inner loop nest. This process repeats until we end +up splitting in the inner-most loops. + + +### Helpers + +RA uses a series of helper functions, each is fairly self-contained. + +- **findAllLRG** - find all the defs and uses of a live range in time O(|LRG|) + instead of time O(N). +- **insertBefore** and **insertAfter** - insert a split either before a use or + after a def. Includes the work to put the split in its proper ordering in + a Basic Block and do all edge maintenance. +- **makeSplit** - Make a split (either clone a clonable constant, or ask the + `Machine` for a port-specific `SplitNode`). +- **ldepth** - Given a min&max loop depth (compacted in a `long`), expand the + loop depth range for a given node `n`. Used to decide when a def or use is + "inside" a loop, which in turn is used to split around loops. + + +## Post Allocation + +After a successful coloring, we want to pull out any same-same register splits. +A quick pass over the splits and after checking registers, we pull out the +useless splits (and track the rest for "scoring" our allocation). We'll also +bypass some split-after-splits, which can remove some redundant copying. + +The registers remain available in the `RegAlloc` object via `alloc.regnum( Node n )` +and will be used by a following instruction encoding pass. + + +## RegAlloc improvements: correctness and a measured baseline + +This chapter starts with a small allocator. Hard conflicts must actually be +broken: a split cannot be skipped just because another copy is in the same +block, nor folded away when that would restore the conflict. Loop backedges +need the same care, especially when Phis represent parallel assignments. +Register kills apply even to instructions with no output value. Finally, +removing a redundant copy requires a backward scan for intervening definitions +and register kills. These are correctness rules, independent of spill quality. + +We sort failed live ranges before splitting so changes in identity-map order do +not decide the allocation. The allocator also has null-safe split printing and +an optional function-local-edge diagnostic. The tests check register masks, +two-address operands, and Phi register agreement; tiny machine graphs exercise +hard conflicts independently of optimizer choices. Native execution comes with +encoding in Chapter 21. + +Rows are fixed test cohorts; columns are compiler chapters. Each cell gives +**Ops / RA / X**: executed ARM+RISC-V instructions, the subset emitted for +allocator copies/rematerializations, and x86's loop-weighted split-move estimate. +**Cases D / X** counts measured dynamic program/target cases and x86 compilations; +membership and inputs stay fixed across columns. Native-library work is excluded. +Chapter 20 has no encoder, hence no dynamic counts. Lower is better within each +metric; see the [measurement details](../regalloc-spills.md) for coverage. + + +| Test cohort | Cases D / X | Ch 20: Ops / RA / X | +|---|---:|---:| +| Ch 20 | 22 / 13 | — / — / 161 | + + +These Windows measurements use optimizer seed 123 for cohorts 20-24 and include +x86-64 SystemV/Win64 and ARM/RISC-V SystemV as applicable. Run `make spill-stats` +here for this compiler, or at the repository root to rebuild the full matrix +and check cohort membership. See the [complete comparison](../regalloc-spills.md) +for measurement details and reproduction commands. + +Cohort 20 contains 11 Chapter20Test programs plus BrainFuck and MergeSort, +each on three SystemV targets: 39 compilations. Synthetic allocator graphs +check correctness separately. This is the baseline; later chapters extend the +columns while keeping these programs and targets fixed. -- cgit v1.2.3