diff options
Diffstat (limited to 'chapter20')
14 files changed, 233 insertions, 23 deletions
diff --git a/chapter20/README.md b/chapter20/README.md index ae2b9df0..ab1d9ca4 100644 --- a/chapter20/README.md +++ b/chapter20/README.md @@ -11,7 +11,9 @@ Chaitin's original: https://en.wikipedia.org/wiki/Register_allocation#CITEREFCha Briggs additions: https://dl.acm.org/doi/10.1145/177492.177575 -There are several other useful link that can be found by searching for Briggs +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. @@ -19,6 +21,20 @@ I've included a very old unpublished paper on speeding up graph coloring allocators: [Interference Graph Triming](docs/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 stratgy 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 +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. + + 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. @@ -48,7 +64,7 @@ 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 +algorithm, but much of the actual success will depend on a large collection of heuristics. ### Coloring Rounds @@ -72,8 +88,8 @@ Coloring proceeds in rounds until we get a coloring: 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) will guaranteed - get a color. These can be removed from the graph - since they will + 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) @@ -214,8 +230,8 @@ 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 thus a different heuristics for -handling them). +levels of conflicts within a live range (and different heuristics for handling +them). ### Hard-Conflicts @@ -247,7 +263,7 @@ 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 +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: @@ -357,12 +373,13 @@ risky live range to color after all. 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, to little leads to +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 looking at each spilling live range in turn, and deciding -on a splitting strategy. +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 @@ -383,7 +400,7 @@ This set of splits is fairly aggressive... but test cases requiring a split in each of the listed locations are including in Chapter 20's test cases. We cannot even attempt a color while we have self conflicts, so its important to break up these live ranges quickly. This tends to over-split and the allocator -leans on Biased Coloring to remove some of the extras. +leans on Biased Coloring and Coalescing to remove some of the extras. ### Split Hard Conflict @@ -393,9 +410,14 @@ 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, 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 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). + +Another common case is popular constants (e.g. 0): a single def with many uses, +and some of the uses require certain registers. Instead of splitting the +popular constant everywhere, we first split it into "register classes" and see +if we can remove the hard conflict with fewer spills. For more complex cases we use the capacity spilling/loop-nest technique. @@ -422,6 +444,22 @@ 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. diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 9e607349..badec740 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -123,7 +123,7 @@ public class RegAlloc { } - public int regnum( Node n ) { + public short regnum( Node n ) { LRG lrg = lrg(n); return lrg==null ? -1 : lrg._reg; } diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java index c5cd95f0..37d08fb0 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -170,12 +170,11 @@ public abstract class CFGNode extends Node { return pre; } - boolean skip(CFGNode usecfg) { + private boolean skip(CFGNode usecfg) { // Only walk control users that are alive. // Do not walk from a Call to linked Fun's. return usecfg instanceof XCtrlNode || (this instanceof CallNode && usecfg instanceof FunNode) || (this instanceof ReturnNode && usecfg instanceof CallEndNode); } - } diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java new file mode 100644 index 00000000..28ebd60d --- /dev/null +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java @@ -0,0 +1,26 @@ +package com.seaofnodes.simple.node.cpus.arm; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.LRG; +import com.seaofnodes.simple.codegen.RegMask; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +import com.seaofnodes.simple.node.MachConcreteNode; + +public class NotARM extends MachConcreteNode implements MachNode{ + NotARM(NotNode not) {super(not);} + @Override public RegMask regmap(int i) { return arm.RMASK; } + @Override public RegMask outregmap() { return arm.RMASK; } + + @Override public int twoAddress( ) { return 0; } + + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)); } + @Override public String op() { return "not"; } +} diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/SubIARM.java b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/SubIARM.java new file mode 100644 index 00000000..d19210cb --- /dev/null +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/SubIARM.java @@ -0,0 +1,42 @@ +package com.seaofnodes.simple.node.cpus.arm; + +import com.seaofnodes.simple.node.MachConcreteNode; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.LRG; +import com.seaofnodes.simple.codegen.RegMask; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class SubIARM extends MachConcreteNode implements MachNode { + final TypeInteger _ti; + SubIARM(Node sub, TypeInteger ti) { + super(sub); + _inputs.pop(); + _ti = ti; + } + + // Register mask allowed on input i. + @Override public RegMask regmap(int i) { return arm.RMASK; } + + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return arm.RMASK; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form: "subi rd = rs1 - imm" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" - #"); + _ti.print(sb); + } + + @Override public String op() { + return (_ti.value() == -1 ? "dec" : "subi"); + } + +} diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java new file mode 100644 index 00000000..6d30cd1c --- /dev/null +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java @@ -0,0 +1,25 @@ +package com.seaofnodes.simple.node.cpus.riscv; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.LRG; +import com.seaofnodes.simple.codegen.RegMask; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.MachConcreteNode; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class NotRISC extends MachConcreteNode implements MachNode { + NotRISC(NotNode not) {super(not);} + @Override public RegMask regmap(int i) { return riscv.RMASK; } + @Override public RegMask outregmap() { return riscv.RMASK; } + + @Override public int twoAddress( ) { return 0; } + + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)); } + @Override public String op() { return "not"; } +} diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java index ec6f9993..ac35d17b 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java @@ -21,7 +21,12 @@ public class CallRX86 extends CallNode implements MachNode { // Encoding is appended into the byte array; size is returned @Override public int encoding(ByteArrayOutputStream bytes) { - throw Utils.TODO(); + bytes.write(0xe8); + int beforeSize = bytes.size(); + // address + //TODO: relocs + bytes.write(0x00); + return bytes.size() - beforeSize; } @Override public void asm(CodeGen code, SB sb) { diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java index 959ec81e..e2f68c1f 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java @@ -32,7 +32,13 @@ public class CallX86 extends CallNode implements MachNode { // Encoding is appended into the byte array; size is returned @Override public int encoding(ByteArrayOutputStream bytes) { - throw Utils.TODO(); + // linker will fix this up + bytes.write(0xe8); + int beforeSize = bytes.size(); + // TODO: relocs + // address + bytes.write(0x00); + return bytes.size() - beforeSize; } @Override public void asm(CodeGen code, SB sb) { diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FunX86.java b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FunX86.java index 5239670b..7346ae05 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FunX86.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FunX86.java @@ -17,6 +17,6 @@ public class FunX86 extends FunNode implements MachNode { // Encoding is appended into the byte array; size is returned @Override public int encoding(ByteArrayOutputStream bytes) { - throw Utils.TODO(); + return 0; } } diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java new file mode 100644 index 00000000..a4b82de8 --- /dev/null +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java @@ -0,0 +1,26 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.LRG; +import com.seaofnodes.simple.codegen.RegMask; +import com.seaofnodes.simple.node.*; +import java.io.ByteArrayOutputStream; + +public class NotX86 extends MachConcreteNode implements MachNode { + NotX86(NotNode not) {super(not);} + @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; } + @Override public RegMask outregmap() { return x86_64_v2.RMASK; } + + @Override public int twoAddress( ) { return 0; } + + // NotNode(BoolNode) = Inverted BoolNode(1) + // NotNode(NotNode(BoolNode)) = BoolNode(2) + // anything else to test & setz(3) + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)); } + @Override public String op() { return "not"; } +} diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ParmX86.java b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ParmX86.java index 4d47f76d..69ebb74e 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ParmX86.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ParmX86.java @@ -21,5 +21,7 @@ public class ParmX86 extends ParmNode implements MachNode { @Override public RegMask outregmap() { return _rmask; } // Encoding is appended into the byte array. Returns size - @Override public int encoding(ByteArrayOutputStream bytes) { return 0; } + @Override public int encoding(ByteArrayOutputStream bytes) { + return 0; + } } diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ProjX86.java b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ProjX86.java index 40d8b6c2..7ac014e6 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ProjX86.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ProjX86.java @@ -18,6 +18,6 @@ public class ProjX86 extends ProjNode implements MachNode { // Encoding is appended into the byte array; size is returned @Override public int encoding(ByteArrayOutputStream bytes) { - throw Utils.TODO(); + return 0; } } diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RetX86.java b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RetX86.java index cdb20fd4..433f64cc 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RetX86.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RetX86.java @@ -28,7 +28,12 @@ public class RetX86 extends ReturnNode implements MachNode { // Encoding is appended into the byte array; size is returned @Override public int encoding(ByteArrayOutputStream bytes) { - throw Utils.TODO(); + // Without imm form + // Near return + int beforeSize = bytes.size(); + bytes.write(0xC3); // opcode + + return bytes.size() - beforeSize; } @Override public void asm(CodeGen code, SB sb) { diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/XorX86.java b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/XorX86.java new file mode 100644 index 00000000..3322d951 --- /dev/null +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/XorX86.java @@ -0,0 +1,36 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.LRG; +import com.seaofnodes.simple.codegen.RegMask; +import com.seaofnodes.simple.node.MachConcreteNode; +import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class XorX86 extends MachConcreteNode implements MachNode{ + XorX86(Node xor) {super(xor);} + + @Override public RegMask regmap(int i) { return x86_64_v2.WMASK; } + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "xor ^ reg + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" ^ ").p(code.reg(in(2))); + } + + @Override public String op() { return "xor"; } + +} |