Split from ch25, SCCP and interprocedural SCCPmain

4 files changed, 640 insertions, 0 deletions

diff --git a/chapter-sccp/src/test/java/com/seaofnodes/simple/codegen/FlagSpillTestSupport.java b/chapter-sccp/src/test/java/com/seaofnodes/simple/codegen/FlagSpillTestSupport.java
new file mode 100644
index 00000000..00d86c63
--- /dev/null
+++ b/chapter-sccp/src/test/java/com/seaofnodes/simple/codegen/FlagSpillTestSupport.java
@@ -0,0 +1,145 @@
+package com.seaofnodes.simple.codegen;
+
+import com.seaofnodes.isa.X86;
+import com.seaofnodes.isa.eval.EvalArm64;
+import com.seaofnodes.simple.TestC;
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.node.cpus.arm.arm;
+import com.seaofnodes.simple.node.cpus.x86_64_v2.x86_64_v2;
+import com.seaofnodes.simple.type.TypeInteger;
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import static org.junit.Assert.*;
+
+// Force overlapping flags, then force every GPR unavailable across the gap.
+public class FlagSpillTestSupport {
+    private static class Op extends MachConcreteNode {
+        final RegMask _def, _use, _kill;
+        Op(RegMask def,RegMask use,RegMask kill,Node... ins) {
+            super(ins); _def=def; _use=use; _kill=kill; _type=TypeInteger.BOT;
+        }
+        @Override public String op() { return "flagsProbe"; }
+        @Override public RegMask outregmap() { return _def; }
+        @Override public RegMask regmap(int i) { return _use; }
+        @Override public RegMask killmap() { return _kill; }
+        @Override public void encoding(Encoding enc) { throw new AssertionError(); }
+    }
+
+    public static void run() throws Exception {
+        StringBuilder asm = new StringBuilder(".text\n");
+        for( boolean isArm : new boolean[]{false,true} )
+            for( boolean stack : new boolean[]{false,true} ) {
+                CodeGen code = new CodeGen("");
+                code._callingConv="SystemV";
+                code._mach=isArm ? new arm(code) : new x86_64_v2(code);
+                RegionNode block = new RegionNode(null,code._start,code._start);
+                code._cfg.add(block);
+                int flagsReg=isArm ? 64 : 32, firstStack=flagsReg+1;
+                RegMask flags = new RegMask(flagsReg);
+                Op def = new Op(flags,null,null,block);
+                RegMask killMask = stack ? (isArm ? new RegMask(0x7fffffffL,1L) : new RegMask(0x1ffffffefL)) : flags;
+                Op kill = new Op(null,null,killMask,block);
+                new Op(null,flags,null,block,def);
+                RegAlloc alloc = new RegAlloc(code);
+                alloc.regAlloc();
+
+                int splits=0, slots=0;
+                for( Node n : block._outputs ) if( n instanceof SplitNode split ) {
+                    int dst=alloc.regnum(n), src=alloc.regnum(n.in(1));
+                    assertTrue(split.outregmap().test(dst));
+                    assertTrue(split.regmap(1).test(src));
+                    for( int fp=isArm ? 32 : 16; fp<flagsReg; fp++ ) {
+                        assertFalse("FP output allowed",split.outregmap().test(fp));
+                        assertFalse("FP input allowed",split.regmap(1).test(fp));
+                    }
+                    if( dst>=firstStack || src>=firstStack ) slots++;
+                    splits++;
+                }
+                assertTrue(splits>=2);
+                assertEquals(stack,slots!=0);
+
+                code._regAlloc=alloc;
+                FunNode frame = new FunNode(null,null,"flags",(Node)null);
+                Encoding save = new Encoding(code), restore = new Encoding(code);
+                save._fun=restore._fun=frame;
+                Encoding enc = save;
+                for( Node n : block._outputs ) {
+                    if( n==kill ) enc=restore;
+                    if( n instanceof SplitNode split ) split.encoding(enc);
+                }
+                if( isArm ) {
+                    for( int bits=0; bits<16; bits++ ) {
+                        EvalArm64 cpu = new EvalArm64(new byte[1024],512);
+                        System.arraycopy(save._bits.buf(),0,cpu._buf,0,save._bits.size());
+                        System.arraycopy(restore._bits.buf(),0,cpu._buf,save._bits.size(),restore._bits.size());
+                        cpu.N=(bits&8)!=0; cpu.Z=(bits&4)!=0; cpu.C=(bits&2)!=0; cpu.V=(bits&1)!=0;
+                        assertEquals(0,cpu.step(save._bits.size()/4));
+                        cpu.N=cpu.Z=cpu.C=cpu.V=false;
+                        if( stack ) for( int r=0; r<31; r++ ) cpu.regs[r]=0;
+                        assertEquals(0,cpu.step(restore._bits.size()/4));
+                        assertEquals((bits&8)!=0,cpu.N); assertEquals((bits&4)!=0,cpu.Z);
+                        assertEquals((bits&2)!=0,cpu.C); assertEquals((bits&1)!=0,cpu.V);
+                        assertEquals(512,cpu.regs[31]);
+                    }
+                } else {
+                    Encoding body = new Encoding(code);
+                    int[] preserved={3,5,6,7,12,13,14,15};
+                    for( int r : preserved ) pushPop(body,r,false);
+                    X86.imm(body,0x81,5,4,16); // Reserve spill storage.
+                    X86.flags(body,TestC.OS.startsWith("Windows") ? 1 : 7,true);
+                    bytes(body,save);
+                    if( stack ) {
+                        for( int r=0; r<16; r++ ) if( r!=4 ) X86.constant(body,r,0);
+                    } else X86.reg(body,0x39,0,0); // CMP rax,rax clobbers only flags.
+                    bytes(body,restore);
+                    X86.flags(body,0,false); // Return the restored flags.
+                    X86.imm(body,0x81,0,4,16);
+                    for( int i=preserved.length-1; i>=0; i-- ) pushPop(body,preserved[i],true);
+                    X86.ret(body);
+                    String name=stack ? "flags_stack" : "flags_reg";
+                    asm.append(".globl ").append(name).append('\n').append(name).append(":\n.byte ");
+                    for( int i=0; i<body._bits.size(); i++ ) {
+                        if( i!=0 ) asm.append(',');
+                        asm.append(body._bits.buf()[i]&255);
+                    }
+                    asm.append('\n');
+                }
+            }
+        Path dir=Files.createTempDirectory(Path.of("build/objs"),"flag_spills_");
+        Files.writeString(dir.resolve("flags.s"),asm);
+        Files.writeString(dir.resolve("flags.c"),"""
+            typedef unsigned long long u64;
+            u64 __attribute__((CALL_CONV)) flags_reg(u64);
+            u64 __attribute__((CALL_CONV)) flags_stack(u64);
+            int main(void) {
+                const int positions[]={0,2,4,6,7,11};
+                for(int bits=0; bits<64; bits++) {
+                    u64 flags=0x202;
+                    for(int i=0;i<6;i++) if(bits&(1<<i)) flags|=1ULL<<positions[i];
+                    if((flags_reg(flags)&0x8d5)!=(flags&0x8d5)) return 1;
+                    if((flags_stack(flags)&0x8d5)!=(flags&0x8d5)) return 2;
+                }
+                return 0;
+            }
+            """);
+        String exe=dir.resolve(TestC.OS.startsWith("Windows") ? "flags.exe" : "flags").toString();
+        exec("gcc","-DCALL_CONV="+(TestC.OS.startsWith("Windows") ? "ms_abi" : "sysv_abi"),
+            "-o",exe,dir.resolve("flags.c").toString(),dir.resolve("flags.s").toString());
+        exec(exe);
+    }
+
+    private static void exec(String... command) throws Exception {
+        Process process = new ProcessBuilder(command).redirectErrorStream(true).start();
+        String output = new String(process.getInputStream().readAllBytes(),java.nio.charset.StandardCharsets.UTF_8);
+        assertEquals(String.join(" ",command)+"\n"+output,0,process.waitFor());
+    }
+
+    private static void bytes(Encoding dst,Encoding src) {
+        for( int i=0; i<src._bits.size(); i++ ) dst.add1(src._bits.buf()[i]&255);
+    }
+    private static void pushPop(Encoding enc,int reg,boolean pop) {
+        if( reg>=8 ) enc.add1(0x41);
+        enc.add1((pop ? 0x58 : 0x50)+(reg&7));
+    }
+}
diff --git a/chapter-sccp/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java b/chapter-sccp/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java
new file mode 100644
index 00000000..b9b49c9f
--- /dev/null
+++ b/chapter-sccp/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java
@@ -0,0 +1,26 @@
+package com.seaofnodes.simple.codegen;
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+import static org.junit.Assert.*;
+public class PrintRegTestSupport {
+    public static void check() throws Exception {
+        var code = new CodeGen("return 0;").parse();
+        var alloc = new RegAlloc(code);
+        var n = new ConstantNode(TypeInteger.ZERO);
+        var a = new LRG((short)1);
+        var b = new LRG((short)2);
+        var c = new LRG((short)3);
+        a._reg = -1;
+        c._leader = b;
+        b._leader = a;
+        var field = RegAlloc.class.getDeclaredField("_lrgs");
+        field.setAccessible(true);
+        var map = (java.util.Map<Node,LRG>)field.get(alloc);
+        map.put(n,c);
+        assertEquals("V1",alloc.reg(n));
+        assertEquals(-1,alloc.regnum(n));
+        assertSame(c,map.get(n));
+        assertSame(b,c._leader);
+        assertSame(a,b._leader);
+    }
+}
diff --git a/chapter-sccp/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter-sccp/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
new file mode 100644
index 00000000..0304c6a1
--- /dev/null
+++ b/chapter-sccp/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
@@ -0,0 +1,346 @@
+package com.seaofnodes.simple.codegen;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.node.cpus.x86_64_v2.x86_64_v2;
+import com.seaofnodes.simple.type.TypeInteger;
+import static org.junit.Assert.*;
+
+// Small scheduled machine graphs isolate register constraints from peepholes.
+public class RegAllocTestSupport {
+    private static final RegMask A = new RegMask(0), B = new RegMask(1);
+    private static class Op extends MachConcreteNode {
+        final RegMask _def, _use, _kill;
+        final boolean _clone;
+        Op(RegMask def, RegMask use, RegMask kill, boolean clone, Node... ins) {
+            super(ins); _def=def; _use=use; _kill=kill; _clone=clone; _type=TypeInteger.BOT;
+        }
+        @Override public String op() { return "testOp"; }
+        @Override public RegMask outregmap() { return _def; }
+        @Override public RegMask regmap(int i) { return _use; }
+        @Override public RegMask killmap() { return _kill; }
+        @Override public boolean isClone() { return _clone; }
+        @Override public Node copy() { return new Op(_def,_use,_kill,_clone,(Node)null); }
+        @Override public void encoding(Encoding enc) { throw new AssertionError(); }
+    }
+    private static SplitNode testSplit(CodeGen code, MachNode def) {
+        LRG lrg = new LRG((short)0);
+        lrg._machDef = def;
+        return code._mach.split("test",(byte)0,lrg);
+    }
+    private static CodeGen graph() {
+        CodeGen code = new CodeGen("");
+        code._mach = new x86_64_v2(code);
+        code._cfg.add(code._start);
+        return code;
+    }
+
+    public static void uncoloredFixedNeighbor() throws Exception {
+        CodeGen code = graph();
+        RegAlloc alloc = new RegAlloc(code);
+        Op def = new Op(new RegMask(3L),null,null,false,code._start);
+        LRG lrg = alloc.newLRG(def);
+        LRG neighbor = new LRG((short)99);
+        neighbor._mask = A;
+        lrg.addNeighbor(neighbor); // Uncolored, but its only possible color is A.
+        var bias = IFG.class.getDeclaredMethod("biasColorNeighbors",RegAlloc.class,Node.class,RegMask.class);
+        bias.setAccessible(true);
+        assertEquals((short)1,bias.invoke(null,alloc,def,new RegMaskRW(3L,0L)));
+    }
+
+    public static void masks() {
+        for( int reg : new int[]{0,63,64,65,127} ) {
+            RegMask mask = new RegMask(reg);
+            assertEquals(reg,mask.firstReg());
+            assertEquals(1,mask.size());
+        }
+        assertEquals(-1,new RegMask(0L).firstReg());
+        assertFalse(new RegMask(0L).size1());
+        RegMask boundary = new RegMask(Long.MIN_VALUE,Long.MIN_VALUE|1);
+        assertEquals(64,boundary.nextReg((short)63));
+        assertEquals(127,boundary.nextReg((short)64));
+        assertEquals(-1,boundary.nextReg((short)127));
+    }
+
+    public static void union() {
+        CodeGen code = graph();
+        Op use = new Op(null,B,null,false,code._start);
+        LRG a = new LRG((short)1), b = new LRG((short)2);
+        a._mask = new RegMask(3L);
+        b._mask = new RegMask(6L);
+        b.machUse(use,(short)2,true);
+        LRG both = a.union(b);
+        assertNotNull(both._mask);
+        assertEquals(1,both._mask.firstReg());
+        assertEquals(1,both._mask.size());
+        assertSame(use,both._machUse);
+        assertEquals(2,both._uidx);
+    }
+
+    public static void killWithoutResult() {
+        CodeGen code = graph();
+        Op def = new Op(A,null,null,false,code._start);
+        new Op(null,null,A,false,code._start); // Clobbers A, produces no value.
+        new Op(null,A,null,false,code._start,def);
+        RegAlloc alloc = new RegAlloc(code);
+        assertTrue(BuildLRG.run(0,alloc));
+        assertFalse("A live value cannot survive a register kill",IFG.build(0,alloc));
+    }
+
+    public static void nullUseMask() {
+        CodeGen code = graph();
+        Op def = new Op(A,null,null,false,code._start);
+        new Op(null,null,null,false,code._start,def); // Scheduling dependency only.
+        RegAlloc alloc = new RegAlloc(code);
+        assertTrue(BuildLRG.run(0,alloc));
+        assertTrue(IFG.build(0,alloc));
+    }
+
+    public static void cloneRegisterClass() {
+        for( RegMask required : new RegMask[]{B,new RegMask(6L)} ) {
+            CodeGen code = graph();
+            Op def = new Op(A,null,null,true,code._start);
+            Op use = new Op(null,required,null,false,code._start,def);
+            Op use2 = new Op(null,required,null,false,code._start,def);
+            RegAlloc alloc = new RegAlloc(code);
+            alloc.regAlloc(); // Re-cloning an A-only value cannot satisfy B/C uses.
+            assertEquals(0,alloc.regnum(def));
+            assertTrue(required.test(alloc.regnum(use.in(1))));
+            assertTrue(required.test(alloc.regnum(use2.in(1))));
+            assertTrue(use.in(1) instanceof SplitNode);
+        }
+    }
+
+    public static void commutativePhi() {
+        CodeGen code = graph();
+        Op a = new Op(A,null,null,false,code._start);
+        Op b = new Op(A,null,null,false,code._start);
+        Op add = new Op(A,A,null,false,code._start,a,b) {
+            @Override public boolean commutes() { return true; }
+        };
+        RegionNode region = new RegionNode(null,code._start,code._start);
+        new PhiNode("sum",TypeInteger.BOT,region,add,a);
+        code._cfg.add(region);
+        assertTrue(BuildLRG.run(0,new RegAlloc(code)));
+    }
+
+    private static class CallOp extends CallNode implements MachNode {
+        CallOp(Node ctrl, Node def) { super(null,ctrl,null,def,def); }
+        @Override public RegMask regmap(int i) { return i==2 ? A : i==3 ? B : null; }
+        @Override public RegMask outregmap() { return null; }
+        @Override public void encoding(Encoding enc) { throw new AssertionError(); }
+    }
+
+    public static void popularUses() {
+        for( int calls=0; calls<=2; calls++ ) {
+            CodeGen code = graph();
+            RegAlloc alloc = new RegAlloc(code);
+            RegionNode block = new RegionNode(null,code._start,code._start);
+            Op def = new Op(new RegMask(7L),null,null,false,block);
+            LRG lrg = alloc.newLRG(def);
+            lrg._machDef = def;
+            lrg._mask = new RegMask(0L);
+            Op ab = new Op(null,new RegMask(3L),null,false,block,def);
+            Op bc = new Op(null,new RegMask(6L),null,false,block,def);
+            Op a = new Op(null,A,null,false,block,def,def);
+            Op b = new Op(null,B,null,false,block,def);
+            Op dep = new Op(null,null,null,false,block,def);
+            CallOp call = calls>0 ? new CallOp(block,def) : null;
+            if( calls==2 ) new CallOp(block,def);
+            boolean split = alloc.splitEmptyMaskByUse((byte)0,lrg);
+            assertEquals(calls<2,split);
+            if( !split ) { assertSame(def,a.in(1)); assertSame(def,b.in(1)); continue; }
+            // Two shared copies, even with overlapping masks and repeated inputs.
+            assertTrue(a.in(1) instanceof SplitNode);
+            assertTrue(b.in(1) instanceof SplitNode);
+            assertNotSame(a.in(1),b.in(1));
+            assertSame(a.in(1),a.in(2));
+            assertSame(b.in(1),ab.in(1));
+            assertSame(b.in(1),bc.in(1));
+            assertSame(def,dep.in(1)); // A scheduling dependency has no register.
+            assertEquals(3,def.nOuts()); // Two copies and the dependency.
+            if( call!=null ) {
+                assertSame(a.in(1),call.in(2));
+                assertSame(b.in(1),call.in(3));
+            }
+        }
+    }
+
+    // Check the scheduled graph before encoding adds untyped branches or rewrites tail calls.
+    public static class CheckedCodeGen extends CodeGen {
+        public CheckedCodeGen(String src) { super(src); }
+        public CheckedCodeGen(String src, TypeInteger arg) { super(src,arg); }
+        @Override public CodeGen regAlloc() {
+            super.regAlloc();
+            checkRegisters(this);
+            return this;
+        }
+    }
+
+    public static void topPhi() {
+        // Either arm can be the synthetic exit.  Both predecessors share a
+        // block here so making TOP live would conflict with the real value.
+        for( int slot=1; slot<=2; slot++ ) {
+            CodeGen code = graph();
+            RegAlloc alloc = new RegAlloc(code);
+            Op def = new Op(A,null,null,false,code._start);
+            Node top = new ConstantNode(com.seaofnodes.simple.type.Type.TOP);
+            RegionNode region = new RegionNode(null,code._start,code._start);
+            PhiNode phi = new PhiNode("value",TypeInteger.BOT,region,slot==1 ? top : def,slot==2 ? top : def);
+            phi._type = TypeInteger.BOT;
+            new Op(null,A,null,false,region,phi);
+            code._cfg.add(region);
+            assertTrue(BuildLRG.run(0,alloc));
+            assertNull(alloc.lrg(top));
+            assertSame(alloc.lrg(def),alloc.lrg(phi));
+            assertTrue(IFG.build(0,alloc));
+            alloc.insertBefore(phi,slot,"test",(byte)0,alloc.lrg(phi));
+            assertSame(top,phi.in(slot));
+        }
+    }
+
+    public static void checkRegisters(CodeGen code) {
+        assertTrue(code._regAlloc.verifyFunctionLocalEdges());
+        for( CFGNode bb : code._cfg )
+            for( Node n : bb._outputs ) {
+                if( n instanceof MachNode mach ) {
+                    if( code._regAlloc.regnum(n)>=0 && mach.outregmap()!=null )
+                        assertTrue(n.getClass().getSimpleName()+"#"+n._nid,code._regAlloc.regnum(n)>=0 && mach.outregmap().test(code._regAlloc.regnum(n)));
+                    for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ )
+                        if( n.in(i)!=null && code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i)!=null )
+                            assertTrue(n.getClass().getSimpleName()+"#"+n._nid+" input "+i,code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i).test(code._regAlloc.regnum(n.in(i))));
+                    if( mach.twoAddress()!=0 )
+                        assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(mach.twoAddress())));
+                }
+                if( n instanceof PhiNode && code._regAlloc.regnum(n)>=0 )
+                    for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ )
+                        if( n.in(i)._type==com.seaofnodes.simple.type.Type.TOP )
+                            assertNull(code._regAlloc.lrg(n.in(i)));
+                        else
+                            assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i)));
+            }
+    }
+
+    public static void copyClobber() throws Exception {
+        for( boolean killed : new boolean[]{false,true} ) {
+            CodeGen code = graph();
+            RegAlloc alloc = new RegAlloc(code);
+            Op def = new Op(A,null,null,false,code._start);
+            alloc.newLRG(def)._reg=0;
+            SplitNode hi = testSplit(code,def);
+            hi.setDef(0,code._start); hi.setDef(1,def);
+            alloc.newLRG(hi)._reg=1;
+            new Op(null,null,killed ? A : null,false,code._start);
+            SplitNode lo = testSplit(code,hi);
+            lo.setDef(0,code._start); lo.setDef(1,hi);
+            alloc.newLRG(lo)._reg=0;
+            Op use = new Op(null,A,null,false,code._start,lo);
+            var post = RegAlloc.class.getDeclaredMethod("postColor");
+            post.setAccessible(true); post.invoke(alloc);
+            assertSame(killed ? lo : def,use.in(1));
+        }
+        CodeGen pre = graph();
+        RegAlloc uncolored = new RegAlloc(pre);
+        Op def0 = new Op(A,null,null,false,pre._start);
+        uncolored.newLRG(def0)._mask=A;
+        Op fixed = new Op(A,null,null,false,pre._start);
+        uncolored.newLRG(fixed)._mask=A;
+        SplitNode copy = testSplit(pre,def0);
+        copy.setDef(0,pre._start); copy.setDef(1,def0);
+        assertFalse("A fixed definition clobbers even before coloring",uncolored.sameBlockNoClobber(copy));
+    }
+
+    public static void coldLoopSelfConflict() {
+        for( boolean phiConflict : new boolean[]{false,true} ) {
+            CodeGen code = graph();
+            RegAlloc alloc = new RegAlloc(code);
+            Op init = new Op(A,null,null,false,code._start);
+            LoopNode loop = new LoopNode(null,code._start);
+            PhiNode phi = new PhiNode("loop",TypeInteger.BOT,loop,init,null);
+            Op back = new Op(A,A,null,false,loop,phi);
+            phi.setDef(2,back);
+            Op use = new Op(null,A,null,false,loop,phi);
+            loop.setDef(2,loop);
+            LRG lrg = alloc.newLRG(phi);
+            lrg._mask = A;
+            alloc.union(lrg,init); alloc.union(lrg,back);
+            lrg.selfConflict(back);
+            if( phiConflict ) lrg.selfConflict(phi);
+            assertTrue(alloc.splitSelfConflict((byte)0,lrg));
+            assertSame(phi,use.in(1)); // First try leaves the hot definition alone.
+            assertSame(back,phi.in(2));
+            if( phiConflict ) assertTrue(phi.in(1) instanceof SplitNode);
+            // Even if the first attempt made no graph change, retry must split.
+            assertTrue(alloc.splitSelfConflict((byte)1,lrg));
+            assertTrue(phi.in(2) instanceof SplitNode);
+            if( phiConflict ) assertTrue(use.in(1) instanceof SplitNode);
+        }
+    }
+
+    public static void copyForward() throws Exception {
+        // Forwarding, fixed operand, two-address tie, intervening clobber,
+        // another user, and a scheduling-only edge.
+        for( int kind=0; kind<6; kind++ ) {
+            CodeGen code = graph();
+            RegAlloc alloc = new RegAlloc(code);
+            Op def = new Op(A,null,null,false,code._start);
+            alloc.newLRG(def)._reg=0;
+            SplitNode copy = testSplit(code,def);
+            copy.setDef(0,code._start); copy.setDef(1,def);
+            alloc.newLRG(copy)._reg=1;
+            if( kind==3 ) new Op(null,null,A,false,code._start);
+            int twoAddress = kind==2 ? 1 : 0;
+            RegMask mask = kind==1 ? B : kind==5 ? null : new RegMask(3L);
+            Op use = new Op(null,mask,null,false,code._start,copy) {
+                @Override public int twoAddress() { return twoAddress; }
+            };
+            if( kind==4 ) new Op(null,B,null,false,code._start,copy);
+            var post = RegAlloc.class.getDeclaredMethod("postColor");
+            post.setAccessible(true); post.invoke(alloc);
+            assertSame("copy case "+kind,kind==0 ? def : copy,use.in(1));
+            assertEquals(kind==0 ? 0 : 1,alloc._spills);
+        }
+    }
+
+    public static void coalescing() {
+        // Merge, incompatible masks, interference, capacity, and adjacency remapping.
+        for( int kind=0; kind<5; kind++ ) {
+            CodeGen code = graph();
+            RegAlloc alloc = new RegAlloc(code);
+            Op def = new Op(new RegMask(3L),null,null,false,code._start);
+            SplitNode copy = testSplit(code,def);
+            copy.setDef(0,code._start); copy.setDef(1,def);
+            Op use = new Op(null,new RegMask(3L),null,false,code._start,copy);
+            LRG from = alloc.newLRG(def), to = alloc.newLRG(copy);
+            from._mask = kind==1 ? A : new RegMask(3L);
+            to._mask = kind==1 ? B : new RegMask(3L);
+            from.machDef(def,false); from.machUse(copy,(short)1,false);
+            to.machDef(copy,false); to.machUse(use,(short)1,false);
+            LRG left = new LRG((short)100), right = new LRG((short)101);
+            if( kind==2 ) { from.addNeighbor(to); to.addNeighbor(from); }
+            if( kind>=3 ) {
+                from.addNeighbor(left); left.addNeighbor(from);
+                if( kind==3 ) { to.addNeighbor(right); right.addNeighbor(to); }
+                else { to.addNeighbor(left); left.addNeighbor(to); }
+            }
+            int fcnt=from.nadj(), tcnt=to.nadj();
+            assertTrue(Coalesce.coalesce(0,alloc));
+            if( kind==0 || kind==4 ) {
+                assertSame(def,use.in(1));
+                assertSame(alloc.lrg(def),alloc.lrg(copy));
+                assertSame(use,alloc.lrg(def)._machUse);
+                assertEquals(1,alloc.lrg(def)._uidx);
+                if( kind==4 ) {
+                    assertEquals(1,left.nadj());
+                    assertSame(alloc.lrg(def),left._adj.at(0));
+                    assertSame(left,alloc.lrg(def)._adj.at(0));
+                }
+            } else {
+                assertSame(copy,use.in(1));
+                assertNotSame(alloc.lrg(def),alloc.lrg(copy));
+                assertEquals(fcnt,from.nadj());
+                assertEquals(tcnt,to.nadj());
+            }
+        }
+    }
+
+}
diff --git a/chapter-sccp/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java b/chapter-sccp/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java
new file mode 100644
index 00000000..0914d916
--- /dev/null
+++ b/chapter-sccp/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java
@@ -0,0 +1,123 @@
+package com.seaofnodes.simple.codegen;
+
+import com.seaofnodes.simple.node.Node;
+import com.seaofnodes.simple.node.cpus.x86_64_v2.CmpMemX86;
+import com.seaofnodes.simple.node.cpus.x86_64_v2.NotX86;
+import com.seaofnodes.simple.node.cpus.x86_64_v2.MulIX86;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+public class X86EncodingTest {
+
+    @Test
+    public void testLogicalNotRegisters() {
+        CodeGen code = new CodeGen("return !arg;")
+            .driver(CodeGen.Phase.Select, "x86_64_v2", "SystemV");
+        var not = code._stop.walk(n -> n instanceof NotX86 ? (NotX86)n : null);
+        assertNotNull("Must exercise logical not", not);
+        int[][] registers = {{0,0}, {1,1}, {7,7}, {9,9}, {1,9}, {9,1}, {6,0}, {15,8}};
+        // TEST src,src; SETZ dstb; MOVZX dst32,dstb. Include overlapping
+        // registers, low-byte registers requiring REX, and extended registers.
+        String[] expected = {
+            "4885c00f94c00fb6c0", "4885c90f94c10fb6c9",
+            "4885ff400f94c7400fb6ff", "4d85c9410f94c1450fb6c9",
+            "4d85c90f94c10fb6c9", "4885c9410f94c1450fb6c9",
+            "4885c0400f94c6400fb6f6", "4d85c0410f94c7450fb6ff"
+        };
+        for (int i = 0; i < registers.length; i++) {
+            int dst = registers[i][0], src = registers[i][1];
+            var enc = new FixedRegisterEncoding(code, not, dst, not.in(1), src);
+            not.encoding(enc);
+            assertArrayEquals("Logical not dst=" + dst + ", src=" + src,
+                java.util.HexFormat.of().parseHex(expected[i]), enc._bits.toByteArray());
+        }
+    }
+
+    @Test
+    public void testLogicalNotExecution() throws java.io.IOException {
+        var dir = java.nio.file.Path.of("build/objs");
+        java.nio.file.Files.createDirectories(dir);
+        java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.smp"),
+            "val logicalNot = { int x -> return !x; };");
+        java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.c"), """
+            #include <limits.h>
+            extern long long logicalNot(long long);
+            int main(void) {
+                long long inputs[] = {0, 1, -1, LLONG_MIN, LLONG_MAX, 1LL << 32};
+                for (unsigned i = 0; i < sizeof(inputs)/sizeof(inputs[0]); i++)
+                    if (logicalNot(inputs[i]) != (inputs[i] == 0)) return 1;
+                return 0;
+            }
+            """);
+        com.seaofnodes.simple.TestC.run("build/objs", "x86LogicalNot", "", -1);
+    }
+
+    @Test
+    public void testMultiplyImmediateRegisters() {
+        // Destination, source, expected REX and ModRM. Cross the register-8
+        // boundary in both directions, with low/low and high/high controls.
+        int[][] cases = {{1, 9, 0x49, 0xC9}, {9, 1, 0x4C, 0xC9},
+                         {1, 2, 0x48, 0xCA}, {9, 10, 0x4D, 0xCA}};
+        for (int immediate : new int[]{11, -11, 123456789, -123456789}) {
+            CodeGen code = new CodeGen("return arg * " + immediate + ";")
+                .driver(CodeGen.Phase.Select, "x86_64_v2", "SystemV");
+            var mul = code._stop.walk(n -> n instanceof MulIX86 ? n : null);
+            assertNotNull("Must exercise immediate multiply", mul);
+            for (int[] regs : cases) {
+                var enc = new FixedRegisterEncoding(
+                    code, mul, regs[0], mul.in(1), regs[1]);
+                ((MulIX86)mul).encoding(enc);
+                boolean small = immediate == 11 || immediate == -11;
+                assertEquals("REX for dst=" + regs[0] + ", src=" + regs[1], regs[2], enc.read1(0));
+                assertEquals(small ? 0x6B : 0x69, enc.read1(1));
+                assertEquals(regs[3], enc.read1(2));
+                assertEquals(small ? 4 : 7, enc._bits.size());
+                assertEquals(immediate, small ? (byte)enc.read1(3) : enc.read4(3));
+            }
+        }
+    }
+    @Test
+    public void testMemoryCompare64Immediate32() {
+        for (int immediate : new int[]{123456789, -123456789}) {
+            String src = "int[] !a = new int[2]; a[0] = arg; return a[arg & 1] == " + immediate + ";";
+            CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding, "x86_64_v2", "SystemV");
+            var cmp = code._stop.walk(n -> n instanceof CmpMemX86 ? n : null);
+            assertNotNull("Must exercise a memory comparison", cmp);
+            var enc = code._encoding;
+            int start = enc._opStart[cmp._nid];
+
+            // REX.W, 81 /7, SIB with scale 8, disp8, and a sign-extended imm32.
+            assertEquals(0x48, enc.read1(start) & 0xF8);
+            assertEquals(0x81, enc.read1(start + 1));
+            assertEquals(0x7C, enc.read1(start + 2));
+            assertEquals(0xC0, enc.read1(start + 3) & 0xC0);
+            assertEquals(8, enc.read1(start + 4));
+            assertEquals(immediate, enc.read4(start + 5));
+            assertEquals("CMP r/m64 uses four immediate bytes", 9, enc._opLen[cmp._nid]);
+
+            // SETE must immediately follow the CPU's nine-byte CMP instruction.
+            assertEquals(0x0F, enc.read1(start + 9));
+            assertEquals(0x94, enc.read1(start + 10));
+        }
+    }
+
+    /** Exercise instruction encoders with explicit registers, independent of allocator choices. */
+    private static class FixedRegisterEncoding extends Encoding {
+        private final Node _dst, _src;
+        private final short _dstReg, _srcReg;
+
+        FixedRegisterEncoding(CodeGen code, Node dst, int dstReg, Node src, int srcReg) {
+            super(code);
+            _dst = dst;
+            _src = src;
+            _dstReg = (short)dstReg;
+            _srcReg = (short)srcReg;
+        }
+
+        @Override public short reg(Node n) {
+            if (n == _dst) return _dstReg;
+            if (n == _src) return _srcReg;
+            throw new AssertionError("Unexpected register lookup");
+        }
+    }
+}