Chapter 20: Graph Coloring Register Allocation

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 <robert.obkircher@gmail.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

34 files changed, 651 insertions, 116 deletions

diff --git a/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
index 8f09cb3d..c23bb301 100644
--- a/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
+++ b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
@@ -1,10 +1,11 @@
 package com.seaofnodes.simple;
 
-import com.seaofnodes.simple.evaluator.Evaluator;
+import com.seaofnodes.simple.codegen.CodeGen;
 import java.nio.charset.StandardCharsets;
 import org.junit.Test;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
+import static com.seaofnodes.simple.Main.PORTS;
 
 public class BrainFuckTest {
 
@@ -17,8 +18,7 @@ public class BrainFuckTest {
             encoded.append("program[").append(i).append("] = ").append(value).append(";");
         }
 
-        CodeGen code = new CodeGen(
-                encoded + """
+        String src = encoded + """
 
 int d = 0;
 u8[] !output = new u8[0];
@@ -62,8 +62,10 @@ for( int pc = 0; pc < program#; pc++ ) {
     }
 }
 return output;
-                """);
-        code.parse().opto().typeCheck()/*.instSelect("x86_64_v2", "SystemV")*/.GCM().localSched();
-        assertEquals("Hello World!\n", Eval2.eval(code, 0, 10000));
+""";
+        Chapter20Test.testCPU(src,"x86_64_v2", "SystemV",28,null);
+        Chapter20Test.testCPU(src,"riscv"    , "SystemV",18,null);
+        Chapter20Test.testCPU(src,"arm"      , "SystemV",12,null);
+        //assertEquals("Hello World!\n", Eval2.eval(code, 0, 10000));
     }
 }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java
index 934eda76..cddbdfcf 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.TypeInteger;
 import org.junit.Test;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java
index 8b7a2f66..a51ac202 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.TypeInteger;
 import org.junit.Test;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
index 8212d246..8923566a 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
@@ -1,7 +1,7 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import org.junit.Test;
-
 import static org.junit.Assert.*;
 
 public class Chapter03Test {
diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java
index 934e794f..e5a16680 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.TypeInteger;
 import org.junit.Test;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index 7a9414a2..70cc6121 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.*;
 import org.junit.Test;
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
index 117531f0..24d12921 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.TypeInteger;
 import org.junit.Test;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java
index 6d6a3ce7..88554323 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter07Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.*;
 import org.junit.Test;
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java
index 350df18b..7e90d484 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.*;
 import org.junit.Assert;
 import org.junit.Test;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java
index 10f4a78b..401f346f 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter09Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java
@@ -1,6 +1,6 @@
 package com.seaofnodes.simple;
 
-import com.seaofnodes.simple.evaluator.Evaluator;
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 import org.junit.Assert;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index bcae373b..91505f41 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import org.junit.Test;
 import com.seaofnodes.simple.node.*;
 import java.util.BitSet;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
index 14819869..439333ca 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter11Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.*;
 import com.seaofnodes.simple.node.*;
 import org.junit.Test;
 import static org.junit.Assert.*;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java
index 90aaf631..4abc9117 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter12Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import org.junit.Ignore;
 import org.junit.Test;
 import static org.junit.Assert.assertEquals;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/src/test/java/com/seaofnodes/simple/Chapter13Test.java
index 584377e4..975946da 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter13Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter13Test.java
@@ -1,9 +1,9 @@
 package com.seaofnodes.simple;
+import com.seaofnodes.simple.codegen.CodeGen;
+import com.seaofnodes.simple.print.IRPrinter;
 
 
 import org.junit.Test;
-
-
 import static org.junit.Assert.assertEquals;
 
 public class Chapter13Test {
diff --git a/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java
index a40b4f04..6377bc14 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java
@@ -1,6 +1,6 @@
 package com.seaofnodes.simple;
 
-import com.seaofnodes.simple.evaluator.Evaluator;
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.StopNode;
 import org.junit.Ignore;
 import org.junit.Test;
@@ -84,7 +84,7 @@ while( 1 ) {
 return guess;
 """);
         code.parse().opto();
-        assertEquals("return Phi(Loop,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0f));", code.print());
+        assertEquals("return Phi(Loop,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)*0.5f));", code.print());
         assertEquals("3.0", Eval2.eval(code,  9));
         assertEquals("1.414213562373095", Eval2.eval(code,  2));
     }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/src/test/java/com/seaofnodes/simple/Chapter14Test.java
index 789a2113..f0fe7dcd 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter14Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter14Test.java
@@ -1,9 +1,9 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.StopNode;
 import org.junit.Ignore;
 import org.junit.Test;
-
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/src/test/java/com/seaofnodes/simple/Chapter15Test.java
index c38dfb00..6a22ff97 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter15Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter15Test.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import org.junit.Ignore;
 import org.junit.Test;
 import static org.junit.Assert.*;
@@ -302,18 +303,20 @@ return is[1];
 
     @Test
     public void testBad3() {
-        CodeGen code = new CodeGen(
-"""
+        CodeGen code = new CodeGen("""
 int[] is = new int[arg];
 return is[1];
 """);
         code.parse().opto();
         assertEquals("return 0;", code.print());
         assertEquals("0", Eval2.eval(code,  4));
-        try { Eval2.eval(code,0); }
-        catch( ArrayIndexOutOfBoundsException e ) { assertEquals("Array index 1 out of bounds for array length 0",e.getMessage()); }
-        try { Eval2.eval(code,-1); }
+        try { Eval2.eval(code,-1); fail(); }
         catch( NegativeArraySizeException e ) { assertEquals("-1",e.getMessage()); }
+        // This test will not pass (i.e., failed range-check) until we have range checks.
+        // Without the range check, the load `is[1]` optimizes against the `new int[]`
+        // and assumes it loads a zero then folds away, and the Eval2 never sees an OOB load.
+        //try { Eval2.eval(code,0); fail(); }
+        //catch( ArrayIndexOutOfBoundsException e ) { assertEquals("Array index 1 out of bounds for array length 0",e.getMessage()); }
     }
 
     @Test
diff --git a/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/src/test/java/com/seaofnodes/simple/Chapter16Test.java
index fd028d57..362388d6 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter16Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter16Test.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.evaluator.Evaluator;
 import com.seaofnodes.simple.node.StopNode;
 import org.junit.Ignore;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter17aTest.java b/src/test/java/com/seaofnodes/simple/Chapter17aTest.java
index ab92d439..16ffe967 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter17aTest.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter17aTest.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.evaluator.Evaluator;
 import com.seaofnodes.simple.node.StopNode;
 import org.junit.Test;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java
index 19cc25d9..da619ed3 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter17bTest.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import org.junit.Ignore;
 import org.junit.Test;
 import static org.junit.Assert.assertEquals;
@@ -12,11 +13,9 @@ public class Chapter17bTest {
     public void testJig() {
         CodeGen code = new CodeGen(
 """
-int i = 0;
-i=i=1;
-return i;
+return 1;
 """);
-        code.parse().opto();
+        code.parse().opto().typeCheck();
         assertEquals("return 1;", code.print());
         assertEquals("1", Eval2.eval(code,  0));
     }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/src/test/java/com/seaofnodes/simple/Chapter18Test.java
index f965edd4..dafd2f3a 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter18Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter18Test.java
@@ -3,10 +3,11 @@ import com.seaofnodes.simple.type.*;
 import com.seaofnodes.simple.node.*;
 
 
+import com.seaofnodes.simple.codegen.CodeGen;
+import org.junit.Ignore;
 import org.junit.Test;
 import static org.junit.Assert.*;
 import static org.junit.Assert.fail;
-import org.junit.Ignore;
 
 public class Chapter18Test {
     @Test public void testNeverExitLoopDepth() {
@@ -193,7 +194,7 @@ var sq = { int x ->
 return sq(arg)+sq(3);
 """);
         code.parse().opto().typeCheck().GCM().localSched();
-        assertEquals("Stop[ return (sq( 3)+sq( arg)); return (Parm_x(sq,int,3,arg)*x); ]", code._stop.toString());
+        assertEquals("Stop[ return (#2+#2); return (Parm_x(sq,int)*x); ]", code._stop.toString());
         assertEquals("13", Eval2.eval(code, 2));
     }
 
@@ -231,7 +232,7 @@ var fcn = arg ? { int x -> x*x; } : { int x -> x+x; };
 return fcn(3);
 """);
         code.parse().opto();
-        assertEquals("Stop[ return Phi(Region,{ int -> int #1},{ int -> int #2})( 3); return (Parm_x($fun,int,3)*x); return (Parm_x($fun,int,3)<<1); ]", code._stop.toString());
+        assertEquals("Stop[ return #2; return (Parm_x($fun1,int,3)*x); return (Parm_x($fun2,int,3)<<1); ]", code._stop.toString());
         assertEquals("6", Eval2.eval(code, 0));
         assertEquals("9", Eval2.eval(code, 1));
     }
@@ -241,7 +242,7 @@ return fcn(3);
     public void testFcn5() {
         CodeGen code = new CodeGen("val fact = { int x -> x <= 1 ? 1 : x*fact(x-1); }; return fact(arg);");
         code.parse().opto().typeCheck();
-        assertEquals("Stop[ return fact( arg); return Phi(Region,1,(Parm_x(fact,int,arg,(x-1))*fact( Sub))); ]", code._stop.toString());
+        assertEquals("Stop[ return #2; return Phi(Region,1,(Parm_x(fact,int,arg,(x-1))*#2)); ]", code._stop.toString());
         assertEquals( "1", Eval2.eval(code, 0));
         assertEquals( "1", Eval2.eval(code, 1));
         assertEquals( "2", Eval2.eval(code, 2));
@@ -291,7 +292,7 @@ for(;;) {
 }
 """);
         code.parse().opto().typeCheck().GCM().localSched();
-        assertEquals("Stop[ return x( Phi(Loop,arg,x( 3))); return Parm_i(x,int,3,Phi_arg); ]", code._stop.toString());
+        assertEquals("Stop[ return #2; return Parm_i(x,int); ]", code._stop.toString());
         assertEquals("3", Eval2.eval(code,  0));
     }
 
@@ -462,7 +463,7 @@ if (i2i) return i2i(arg);
 return f2f(o)(1);
 """);
         code.parse().opto().typeCheck().GCM().localSched();
-        assertEquals("Stop[ return Phi(Region,o( arg),o( 1)); return Parm_i(o,int,arg,1); ]", code._stop.toString());
+        assertEquals("Stop[ return Phi(Region,#2,1); return Parm_i(o,int); ]", code._stop.toString());
         assertEquals("1", Eval2.eval(code,  2));
     }
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/src/test/java/com/seaofnodes/simple/Chapter19Test.java
index 1abda81f..9bd75207 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter19Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter19Test.java
@@ -3,10 +3,12 @@ import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
 
 
+import com.seaofnodes.simple.codegen.CodeGen;
+import org.junit.Ignore;
 import org.junit.Test;
+import static com.seaofnodes.simple.Main.PORTS;
 import static org.junit.Assert.*;
 import static org.junit.Assert.fail;
-import org.junit.Ignore;
 
 public class Chapter19Test {
     @Test public void testPrintingFunctionLookup() {
@@ -78,107 +80,107 @@ val _hashCodeString = { !String self ->
 !String !s = new String { cs = new u8[17]; };
 s.cs[0] =  67; // C
 s.cs[1] = 108; // l
-hashCode(s);""");
+hashCode(s)+hashCode(s);""");
         code.parse().opto().typeCheck().GCM().localSched();
-        assertEquals("Stop[ return Phi(Region,123456789,Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash)))); return Phi(Region,1,0,0,1); ]", code._stop.toString());
-        assertEquals("-2449306563677080489", Eval2.eval(code,  2));
+        assertEquals("Stop[ return (#2+#2); return Phi(Region,1,0,0,1); return Phi(Region,._hashCode,Phi(Region,123456789,Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); ]", code._stop.toString());
+        assertEquals("-4898613127354160978", Eval2.eval(code,  2));
     }
 
     @Test
     public void testBasic0() {
-        CodeGen code = new CodeGen("return 0;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        CodeGen code = new CodeGen("return 0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return 0;", code._stop.toString());
     }
 
     @Test
     public void testBasic1() {
-        CodeGen code = new CodeGen("return arg+1;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        CodeGen code = new CodeGen("return arg+1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (inc,arg);", code._stop.toString());
     }
 
     @Test
     public void testBasic2() {
-        CodeGen code = new CodeGen("return -17;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        CodeGen code = new CodeGen("return -17;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return -17;", code._stop.toString());
     }
 
 
     @Test
     public void testBasic3() {
-        CodeGen code = new CodeGen("return arg==1;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        CodeGen code = new CodeGen("return arg==1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (set==,(cmp,arg));", code._stop.toString());
     }
 
     @Test
     public void testBasic4() {
-        CodeGen code = new CodeGen("return arg<<1;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        CodeGen code = new CodeGen("return arg<<1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (shli,arg);", code._stop.toString());
     }
 
     @Test
     public void testBasic5() {
-        CodeGen code = new CodeGen("return arg >> 1;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        CodeGen code = new CodeGen("return arg >> 1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (sari,arg);", code._stop.toString());
     }
 
     @Test
     public void testBasic6() {
-        CodeGen code = new CodeGen("return arg >>> 1;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        CodeGen code = new CodeGen("return arg >>> 1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (shri,arg);", code._stop.toString());
     }
 
     @Test
     public void testBasic7() {
-        CodeGen code = new CodeGen("return arg / 2;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        CodeGen code = new CodeGen("return arg / 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (div,arg,2);", code._stop.toString());
     }
 
     @Test
     public void testBasic8() {
-        CodeGen code = new CodeGen("return arg * 6;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        CodeGen code = new CodeGen("return arg * 6;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (muli,arg);", code._stop.toString());
     }
 
     @Test
     public void testBasic9() {
-        CodeGen code = new CodeGen("return arg & 2;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        CodeGen code = new CodeGen("return arg & 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (andi,arg);", code._stop.toString());
     }
 
     @Test
     public void testBasic10() {
-        CodeGen code = new CodeGen("return arg | 2;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        CodeGen code = new CodeGen("return arg | 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (ori,arg);", code._stop.toString());
     }
 
     @Test
     public void testBasic11() {
-        CodeGen code = new CodeGen("return arg ^ 2;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        CodeGen code = new CodeGen("return arg ^ 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (xori,arg);", code._stop.toString());
     }
 
     @Test
     public void testBasic12() {
-        CodeGen code = new CodeGen("return arg + 2.0;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        CodeGen code = new CodeGen("return arg + 2.0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (addf,(i2f8,arg),2.0f);", code._stop.toString());
     }
 
     @Test
     public void testBasic13() {
-        CodeGen code = new CodeGen("return arg - 2.0;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        CodeGen code = new CodeGen("return arg - 2.0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (subf,(i2f8,arg),2.0f);", code._stop.toString());
     }
 
     @Test
     public void testBasic14() {
-        CodeGen code = new CodeGen("return arg * 2.0;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        CodeGen code = new CodeGen("return arg * 2.0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (mulf,(i2f8,arg),2.0f);", code._stop.toString());
     }
 
     @Test
     public void testBasic15() {
-        CodeGen code = new CodeGen("return arg / 2.0;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
-        assertEquals("return (divf,(i2f8,arg),2.0f);", code._stop.toString());
+        CodeGen code = new CodeGen("return arg / 2.0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
+        assertEquals("return (mulf,(i2f8,arg),0.5f);", code._stop.toString());
     }
 
     @Test
@@ -187,7 +189,7 @@ hashCode(s);""");
 """
 int arg1 =  arg + 1;
 return arg1 / arg;""");
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (div,(inc,arg),arg);", code._stop.toString());
     }
 
@@ -198,50 +200,17 @@ return arg1 / arg;""");
 int arg1 =  arg + 1;
 return arg1 * arg;
 """);
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (mul,(inc,arg),arg);", code._stop.toString());
     }
 
     @Test
-    public void testBasic18() {
-        CodeGen code = new CodeGen(
-                """
-                int arg1 =  arg + 1;
-                return arg1 << arg;
-                """);
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
-        assertEquals("return (shl,(inc,arg),arg);", code._stop.toString());
-    }
-
-    @Test
-    public void testBasic19() {
-        CodeGen code = new CodeGen(
-                """
-                int arg1 =  arg + 1;
-                return arg1 >> arg;
-                """);
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
-        assertEquals("return (sar,(inc,arg),arg);", code._stop.toString());
-    }
-
-    @Test
-    public void testBasic20() {
-        CodeGen code = new CodeGen(
-                """
-                int arg1 =  arg + 1;
-                return arg1 >>> arg;
-                """);
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
-        assertEquals("return (shr,(inc,arg),arg);", code._stop.toString());
-    }
-
-    @Test
     public void testToFloat() {
         CodeGen code = new CodeGen("""
                 int a = arg;
                 return a + 2.0;
                 """
-        ).parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        ).parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (addf,(i2f8,arg),2.0f);", code._stop.toString());
     }
 
@@ -256,7 +225,7 @@ else {
     a = arg-3;
 }
 return a;""");
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return Phi(Region,(addi,arg),(addi,arg));", code.print());
     }
 
@@ -271,7 +240,7 @@ if( arg==1 )
 else
     a=b+1;
 return a+b;""");
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (add,(add,Phi(Region,(shli,arg),arg),arg),Phi(Region,4,5));", code.print());
     }
 
@@ -283,7 +252,7 @@ int sum=0;
 for( int i=0; i<arg; i++ )
     sum += i;
 return sum;""");
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return Phi(Loop,0,(add,Phi_sum,Phi(Loop,0,(inc,Phi_i))));", code.print());
     }
 
@@ -293,42 +262,42 @@ return sum;""");
 """
 struct S { int a; !S? !c; };
 return new S;""");
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return S;", code.print());
     }
 
     @Test
     public void testLea1() {
         CodeGen code = new CodeGen("int x = arg/3; return arg+x+7;");
-        code.parse().opto().typeCheck().instSelect("x86_64_v2",  "SystemV").GCM().localSched();
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2",  "SystemV").GCM().localSched();
         assertEquals("return (lea,arg,(div,arg,3));", code.print());
     }
 
     @Test
     public void testLea2() {
         CodeGen code = new CodeGen("int x = arg/3; return arg+x*4+7;");
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return (lea,arg,(div,arg,3));", code.print());
     }
 
     @Test
     public void testLea3() {
         CodeGen code = new CodeGen("int x = arg/3; return x*4+arg;");
-        code.parse().opto().typeCheck().instSelect("x86_64_v2",  "SystemV").GCM().localSched();
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2",  "SystemV").GCM().localSched();
         assertEquals("return (lea,arg,(div,arg,3));", code.print());
     }
 
     @Test
     public void testAlloc2() {
         CodeGen code = new CodeGen("int[] !xs = new int[3]; xs[arg]=1; return xs[arg&1];");
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return .[];", code.print());
     }
 
     @Test
     public void testAlloc3() {
         CodeGen code = new CodeGen("int[] !xs = new int[3]; xs[arg]=1; return xs[arg&1]+3;");
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return .[];", code.print());
     }
 
@@ -345,7 +314,7 @@ for( int i=0; i<ary#-1; i++ )
     ary[i+1] += ary[i];
 return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6
 """);
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return .[];", code.print());
     }
 
@@ -360,7 +329,7 @@ for( int i=0; i<A#; i++ )
 for( int i=0; i<A#; i++ )
     B[i] += A[i];
 """);
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return 0;", code.print());
     }
 
@@ -373,7 +342,7 @@ for( int i=0; i<A#; i++ )
     A[i]++;
 return A[1];
 """);
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return .[];", code.print());
     }
 
@@ -393,8 +362,8 @@ val sqrt = { flt x ->
 flt farg = arg;
 return sqrt(farg);
 """);
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
-        assertEquals("return Phi(Loop,(i2f8,arg),(divf,(addf,(divf,i2f8,Phi_guess),Phi_guess),2.0f));", code.print());
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
+        assertEquals("return Phi(Loop,(i2f8,arg),(mulf,(addf,(divf,i2f8,Phi_guess),Phi_guess),0.5f));", code.print());
     };
 
 
@@ -424,7 +393,7 @@ for( int j=0; j<nprimes; j++ )
     rez[j] = primes[j];
 return rez;
 """);
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("return [int];", code.print());
         //assertEquals("int[ 2,3,5,7,11,13,17,19]",Eval2.eval(code, 20));
     }
@@ -437,8 +406,8 @@ return rez;
 val fcn = arg ? { int x -> x*x; } : { int x -> x+x; };
 return fcn(2)*10 + fcn(3);
 """);
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
-        assertEquals("Stop[ return (add,Phi(Region,{ int -> int #1},{ int -> int #2})( 3),(muli,Phi_( 2))); return (mul,Parm_x($fun,int,3,2),x); return (shli,Parm_x($fun,int,3,2)); ]", code.print());
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
+        assertEquals("Stop[ return (add,#2,(muli,#2)); return (mul,Parm_x($fun1,int),x); return (shli,Parm_x($fun2,int)); ]", code.print());
     }
 
     @Test
@@ -448,17 +417,17 @@ return fcn(2)*10 + fcn(3);
 val sq = { int x -> x*x; };
 return sq(arg) + sq(3);
 """);
-        code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
-        assertEquals("Stop[ return (add,sq(),sq()); return (mul,Parm_x(sq,int,3,arg),x); ]", code.print());
+        code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched();
+        assertEquals("Stop[ return (add,#2,#2); return (mul,Parm_x(sq,int),x); ]", code.print());
     }
 
     @Test public void testSelectedMemory() {
-        for( String cpu : new String[]{"x86_64_v2","riscv"} )
+        for( String cpu : new String[]{"x86_64_v2","riscv","arm"} )
             for( String src : new String[]{Chapter10Test.NESTED_MEMORY,Chapter16Test.CONSTRUCTOR_MEMORY,
                                           Chapter18Test.CALL_MEMORY,Chapter18Test.RECURSIVE_MEMORY} ) {
                 var code = new CodeGen(src).parse().opto().typeCheck();
                 var aliases = memoryPhis(code._stop);
-                code.instSelect(cpu,"SystemV");
+                code.instSelect(PORTS,cpu,"SystemV");
                 assertEquals(aliases,memoryPhis(code._stop));
                 code.GCM().localSched();
                 code._stop.walk(n -> {
@@ -511,7 +480,7 @@ return sq(arg) + sq(3);
             int before = p.x + arg;
             a.x=33; b.x=44;
             return before;
-            """).parse().opto().typeCheck().instSelect("x86_64_v2","SystemV").GCM().localSched();
+            """).parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2","SystemV").GCM().localSched();
         var read = (MemOpNode)code._stop.walk(n ->
             n instanceof com.seaofnodes.simple.node.cpus.x86_64_v2.AddMemX86 ? n : null);
         assertNotNull(read);
diff --git a/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/src/test/java/com/seaofnodes/simple/Chapter20Test.java
new file mode 100644
index 00000000..104be01e
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter20Test.java
@@ -0,0 +1,272 @@
+package com.seaofnodes.simple;
+
+
+import com.seaofnodes.simple.codegen.CodeGen;
+import com.seaofnodes.simple.print.ASMPrinter;
+import org.junit.Assert;
+import org.junit.Ignore;
+import org.junit.Test;
+import static com.seaofnodes.simple.Main.PORTS;
+import static org.junit.Assert.*;
+
+public class Chapter20Test {
+    @Test public void testAllocatorTopPhi() { com.seaofnodes.simple.codegen.RegAllocTestSupport.topPhi(); }
+
+    @Test public void testAllocatorFixedNeighbor() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.uncoloredFixedNeighbor(); }
+
+    @Test public void testNarrowStoreMasks() {
+        for( String type : new String[]{"i8","u8","i16","u16"} ) {
+            CodeGen code = new CodeGen("struct S { "+type+" x; }; !S !s=new S; s.x=arg; return 0;")
+                .parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2","SystemV").GCM().localSched().regAlloc();
+            int stores=0;
+            for( var bb : code._cfg )
+                for( var node : bb.outs() )
+                    if( node instanceof com.seaofnodes.simple.node.cpus.x86_64_v2.StoreX86 st ) {
+                        stores++;
+                        assertEquals(-1,st.regmap(4).nextReg((short)15));
+                    }
+            assertEquals(1,stores);
+        }
+    }
+
+    @Test public void testInlinedReturnValue() {
+        String src = """
+struct S { int x; };
+val f = { !S s -> s.x = g(); };
+val g = { -> 123; };
+!S !s = new S;
+return f(s);
+""";
+        // The entry of g can disappear before its Return is folded into f.
+        // Exercise both worklist orders; deleting the entry does not kill 123.
+        for( int seed=0; seed<64; seed++ ) {
+            CodeGen code = new CodeGen(src,com.seaofnodes.simple.type.TypeInteger.BOT,seed).parse().opto().typeCheck();
+            assertEquals("seed "+seed, "123", Eval2.eval(code,0));
+        }
+    }
+
+
+    @org.junit.Rule public final org.junit.rules.ErrorCollector _errors = new org.junit.rules.ErrorCollector();
+    @Test public void testAllocatorMasks() { com.seaofnodes.simple.codegen.RegAllocTestSupport.masks(); }
+    @Test public void testAllocatorUnion() { com.seaofnodes.simple.codegen.RegAllocTestSupport.union(); }
+    @Test public void testAllocatorCopyClobber() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyClobber(); }
+    @Test public void testAllocatorCommutativePhi() { com.seaofnodes.simple.codegen.RegAllocTestSupport.commutativePhi(); }
+    @Test public void testAllocatorKills() { com.seaofnodes.simple.codegen.RegAllocTestSupport.killWithoutResult(); }
+    @Test public void testAllocatorDependencies() { com.seaofnodes.simple.codegen.RegAllocTestSupport.nullUseMask(); }
+    @Test public void testAllocatorCloneClass() { com.seaofnodes.simple.codegen.RegAllocTestSupport.cloneRegisterClass(); }
+
+    @Test public void testPrintingRegisters() throws Exception {
+        com.seaofnodes.simple.codegen.PrintRegTestSupport.check();
+    }
+
+
+    @Ignore
+    @Test
+    public void testJig() {
+        CodeGen code = new CodeGen("return 0;");
+        code.parse().opto().typeCheck();
+        assertEquals("return 0;", code._stop.toString());
+        assertEquals("0", Eval2.eval(code,  2));
+    }
+
+    // Collect differences so every target runs; JUnit still fails the test.
+    private void testTarget(String src, String cpu, String os, int spills, String stop) {
+        _errors.checkSucceeds(() -> { testCPU(src,cpu,os,spills,stop); return null; });
+    }
+
+    static void testCPU(String src, String cpu, String os, int spills, String stop) {
+        CodeGen code = new CodeGen(src);
+        code.parse().opto().typeCheck().instSelect(PORTS,cpu,os).GCM().localSched().regAlloc().encode();
+        com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code);
+        SpillStats.record(code,"Chapter20",cpu,os);
+        assertEquals("Expect spills: "+cpu,spills,code._regAlloc._spillScaled,Math.max(1,spills>>3));
+        if( stop!=null ) assertEquals(stop,code._stop.toString());
+    }
+
+    private void testAllCPUs( String src, int spills, String stop ) {
+        testTarget(src,"x86_64_v2", "SystemV",spills,stop);
+        testTarget(src,"riscv"    , "SystemV",spills,stop);
+        testTarget(src,"arm"      , "SystemV",spills,stop);
+    }
+
+    @Test public void testAlloc0() {
+        testAllCPUs("return new u8[arg];", 1, "return [u8];");
+    }
+
+    @Test public void testBasic1() {
+        String src = "return arg | 2;";
+        testTarget(src,"x86_64_v2", "SystemV",1,"return (ori,mov(arg));");
+        testTarget(src,"riscv"    , "SystemV",0,"return ( arg | #2 );");
+        testTarget(src,"arm"      , "SystemV",0,"return (ori,arg);");
+    }
+
+    @Test
+    public void testNewtonInteger() {
+        String src =
+"""
+// Newtons approximation to the square root
+val sqrt = { int x ->
+    int guess = x;
+    while( 1 ) {
+        int next = (x/guess + guess)/2;
+        if( next == guess ) return guess;
+        guess = next;
+    }
+};
+return sqrt(arg) + sqrt(arg+2);
+""";
+        testTarget(src,"x86_64_v2", "SystemV",26,null);
+        testTarget(src,"riscv"    , "SystemV",19,null);
+        testTarget(src,"arm"      , "SystemV",26,null);
+    }
+
+    @Test
+    public void testNewtonFloat() {
+        String src =
+"""
+// Newtons approximation to the square root
+val sqrt = { flt x ->
+    flt guess = x;
+    while( 1 ) {
+        flt next = (x/guess + guess)/2;
+        if( next == guess ) return guess;
+        guess = next;
+    }
+};
+flt farg = arg;
+return sqrt(farg) + sqrt(farg+2.0);
+""";
+        testTarget(src,"x86_64_v2", "SystemV",25,null);
+        testTarget(src,"riscv"    , "SystemV",21,null);
+        testTarget(src,"arm"      , "SystemV",18,null);
+    }
+
+    @Test
+    public void testAlloc2() {
+        String src = "int[] !xs = new int[3]; xs[arg]=1; return xs[arg&1];";
+        testAllCPUs(src,1,"return .[];");
+    }
+
+    @Test
+    public void testArray1() {
+        String src =
+"""
+int[] !ary = new int[arg];
+// Fill [0,1,2,3,4,...]
+for( int i=0; i<ary#; i++ )
+    ary[i] = i;
+// Fill [0,1,3,6,10,...]
+for( int i=0; i<ary#-1; i++ )
+    ary[i+1] += ary[i];
+return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6
+""";
+        testTarget(src,"x86_64_v2", "SystemV",13,"return .[];");
+        testTarget(src,"riscv"    , "SystemV",1,"return (add,.[],(mul,.[],1000));");
+        testTarget(src,"arm"      , "SystemV",1,"return (add,.[],(muli,.[]));");
+    }
+
+    @Test
+    public void testString() {
+        String src = """
+struct String {
+    u8[] !cs;
+    int _hashCode;
+};
+
+val equals = { !String !self, !String s ->
+    if( self == s ) return true;
+    if( self.cs# != s.cs# ) return false;
+    for( int i=0; i< self.cs#; i++ )
+        if( self.cs[i] != s.cs[i] )
+            return false;
+    return true;
+};
+
+val hashCode = { !String self ->
+    self._hashCode
+    ?  self._hashCode
+    : (self._hashCode = _hashCodeString(self));
+};
+
+val _hashCodeString = { !String self ->
+    int hash=0;
+    if( self.cs ) {
+        for( int i=0; i< self.cs#; i++ )
+            hash = hash*31 + self.cs[i];
+    }
+    if( !hash ) hash = 123456789;
+    return hash;
+};
+
+!String !s = new String { cs = new u8[17]; };
+s.cs[0] =  67; // C
+s.cs[1] = 108; // l
+hashCode(s);
+""";
+        testTarget(src,"x86_64_v2", "SystemV",21,null);
+        testTarget(src,"riscv"    , "SystemV", 3,null);
+        testTarget(src,"arm"      , "SystemV", 3,null);
+    }
+
+    @Test
+    public void testCast() {
+        String src = "struct Bar { int x; }; var b = arg ? new Bar;  return b ? b.x++ + b.x++ : -1;";
+        testAllCPUs(src,0,null);
+    }
+
+    @Test
+    public void testFltArg() {
+        String src = "return {int i, flt f, int j->return i+f+j;};";
+        testAllCPUs(src,0,null);
+    }
+
+    @Test
+    public void testFlags1() {
+        String src = """
+bool b1 = arg == 1;
+bool b2 = arg == 2;
+if (b2) if (b1) return 1;
+if (b1) return 2;
+return 0;
+""";
+        testTarget(src,"x86_64_v2", "SystemV",0,"return Phi(Region,1,2,0);");
+        testTarget(src,"riscv"    , "SystemV",0,"return Phi(Region,1,2,0);");
+        testTarget(src,"arm"      , "SystemV",0,"return Phi(Region,1,2,0);");
+    }
+
+    @Test
+    public void testFlags2() {
+        String src = """
+bool b1 = arg == 1;
+while (arg > 0) {
+    arg--;
+    if (b1) arg--;
+}
+return arg;
+""";
+        testTarget(src,"x86_64_v2", "SystemV",3,null);
+        testTarget(src,"riscv"    , "SystemV",2,null);
+        testTarget(src,"arm"      , "SystemV",2,null);
+    }
+
+    @Test public void testMemoryAllocation() {
+        for( String cpu : new String[]{"x86_64_v2","riscv","arm"} )
+            for( String src : new String[]{Chapter10Test.NESTED_MEMORY,Chapter16Test.CONSTRUCTOR_MEMORY,
+                                          Chapter18Test.CALL_MEMORY,Chapter18Test.RECURSIVE_MEMORY,
+                                          "int[] !a = new int[3]; a[arg]=arg; return a[0]+1;"} ) {
+                var code = new CodeGen(src).parse().opto().typeCheck()
+                    .instSelect(PORTS,cpu,"SystemV").GCM().localSched().regAlloc();
+                com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code);
+                code._stop.walk(n -> {
+                    // Whole memory, precise Phis, and memory projections need no register.
+                    if( n._type instanceof com.seaofnodes.simple.type.TypeMem )
+                        assertEquals(-1,code._regAlloc.regnum(n));
+                    if( n instanceof com.seaofnodes.simple.node.NewNode nn ) {
+                        assertTrue(code._regAlloc.regnum(nn.proj(0))>=0);
+                        assertEquals(-1,code._regAlloc.regnum(nn.proj(1)));
+                    }
+                    return null;
+                });
+            }
+    }
+}
diff --git a/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java b/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java
index 860827d7..48f739cf 100644
--- a/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java
+++ b/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java
@@ -1,6 +1,6 @@
 package com.seaofnodes.simple;
 
-
+import com.seaofnodes.simple.codegen.CodeGen;
 import org.junit.Test;
 import static org.junit.Assert.*;
 
diff --git a/src/test/java/com/seaofnodes/simple/Eval2.java b/src/test/java/com/seaofnodes/simple/Eval2.java
index 46251cef..3312ec6b 100644
--- a/src/test/java/com/seaofnodes/simple/Eval2.java
+++ b/src/test/java/com/seaofnodes/simple/Eval2.java
@@ -1,7 +1,9 @@
 package com.seaofnodes.simple;
 
-import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.print.IRPrinter;
+import com.seaofnodes.simple.type.*;
 import java.util.*;
 
 public abstract class Eval2 {
diff --git a/src/test/java/com/seaofnodes/simple/Main.java b/src/test/java/com/seaofnodes/simple/Main.java
index 523bd306..f3a6784c 100644
--- a/src/test/java/com/seaofnodes/simple/Main.java
+++ b/src/test/java/com/seaofnodes/simple/Main.java
@@ -1,9 +1,11 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import java.nio.file.Files;
 import java.nio.file.Path;
 
 public class Main {
+    public static final String PORTS = "com.seaofnodes.simple.node.cpus";
     // Compile and run a simple program
     public static void main( String[] args ) throws Exception {
         // First arg is file, 2nd+ args are program args
diff --git a/src/test/java/com/seaofnodes/simple/MergeSortTest.java b/src/test/java/com/seaofnodes/simple/MergeSortTest.java
index a352530f..31fbe3a4 100644
--- a/src/test/java/com/seaofnodes/simple/MergeSortTest.java
+++ b/src/test/java/com/seaofnodes/simple/MergeSortTest.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import org.junit.Test;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
@@ -8,7 +9,7 @@ public class MergeSortTest {
 
     @Test
     public void testMergeSort() {
-        CodeGen code = new CodeGen(
+        String src =
 """
 // based on the top-down version from https://en.wikipedia.org/wiki/Merge_sort
 
@@ -56,10 +57,11 @@ for (int i = 0; i < a#; i++)
 merge_sort(a, b, a#);
 
 return a;
-""");
-        code.parse().opto();
-        assertEquals("Stop[ return [int]; return 0; ]", code._stop.toString());
-        assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11));
+""";
+        Chapter20Test.testCPU(src,"x86_64_v2", "SystemV",46,"Stop[ return mov(mov([int])); return 0; ]");
+        Chapter20Test.testCPU(src,"riscv"    , "SystemV",36,"Stop[ return mov(mov([int])); return 0; ]");
+        Chapter20Test.testCPU(src,"arm"      , "SystemV",37,"Stop[ return mov(mov([int])); return 0; ]");
+//assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11));
     }
 
 }
diff --git a/src/test/java/com/seaofnodes/simple/MutabilityTest.java b/src/test/java/com/seaofnodes/simple/MutabilityTest.java
index 0861424f..7ae80314 100644
--- a/src/test/java/com/seaofnodes/simple/MutabilityTest.java
+++ b/src/test/java/com/seaofnodes/simple/MutabilityTest.java
@@ -2,6 +2,7 @@ package com.seaofnodes.simple;
 
 import org.junit.Test;
 import static org.junit.Assert.*;
+import com.seaofnodes.simple.codegen.CodeGen;
 
 public class MutabilityTest {
     private static void ok(String src, String result) {
diff --git a/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/src/test/java/com/seaofnodes/simple/SchedulerTest.java
index d29166a7..3b19857a 100644
--- a/src/test/java/com/seaofnodes/simple/SchedulerTest.java
+++ b/src/test/java/com/seaofnodes/simple/SchedulerTest.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.evaluator.Evaluator;
 import com.seaofnodes.simple.node.StopNode;
 import org.junit.Assert;
diff --git a/src/test/java/com/seaofnodes/simple/SpillStats.java b/src/test/java/com/seaofnodes/simple/SpillStats.java
new file mode 100644
index 00000000..9b03da7b
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/SpillStats.java
@@ -0,0 +1,48 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.codegen.CodeGen;
+import java.util.Map;
+import java.util.TreeMap;
+import org.junit.runner.*;
+import org.junit.runner.notification.*;
+
+// Run existing tests and sum actual allocations, including ones without goldens.
+// Helpers call record after allocation; ordinary JUnit runs collect nothing.
+public class SpillStats extends RunListener {
+    private static SpillStats ACTIVE;
+    private Description _test;
+    private final Map<String,long[]> _totals = new TreeMap<>();
+
+    @Override public void testStarted(Description test) { _test = test; }
+    public static void record(CodeGen code, String cohort, String cpu, String abi) {
+        if( ACTIVE==null ) return;
+        String test = ACTIVE._test.getTestClass().getSimpleName()+"."+ACTIVE._test.getMethodName();
+        for( String key : new String[]{cohort+","+cpu+","+abi,cohort+",ALL,ALL"} ) {
+            long[] sum = ACTIVE._totals.computeIfAbsent(key,k -> new long[3]);
+            sum[0]++; sum[1] += code._regAlloc._spills; sum[2] += code._regAlloc._spillScaled;
+        }
+        System.out.println("allocation,"+cohort+","+test+","+cpu+","+abi+","+
+                           code._regAlloc._spills+","+code._regAlloc._spillScaled);
+    }
+
+    public static void main(String[] args) throws ClassNotFoundException {
+        if( args.length==0 ) args = new String[]{"Chapter20Test","BrainFuckTest","MergeSortTest"};
+        Class<?>[] tests = new Class<?>[args.length];
+        for( int i=0; i<args.length; i++ )
+            tests[i] = Class.forName("com.seaofnodes.simple."+args[i]);
+        ACTIVE = new SpillStats();
+        JUnitCore junit = new JUnitCore();
+        junit.addListener(ACTIVE);
+        Result result = junit.run(tests);
+        if( !result.wasSuccessful() ) System.out.println("FAILED test run: totals are not a complete comparison.");
+        System.out.println("cohort,cpu,abi,allocations,splits,scaled");
+        for( var row : ACTIVE._totals.entrySet() ) {
+            long[] sum = row.getValue();
+            System.out.println(row.getKey()+","+sum[0]+","+sum[1]+","+sum[2]);
+        }
+        for( Failure failure : result.getFailures() ) System.err.println(failure.getTrace());
+        System.out.println("Tests: "+result.getRunCount()+", failures: "+result.getFailureCount());
+        ACTIVE = null;
+        if( !result.wasSuccessful() ) System.exit(1);
+    }
+}
diff --git a/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java b/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java
new file mode 100644
index 00000000..b9b49c9f
--- /dev/null
+++ b/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/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
new file mode 100644
index 00000000..2966cb00
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
@@ -0,0 +1,195 @@
+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 java.io.ByteArrayOutputStream;
+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 int encoding(ByteArrayOutputStream bytes) { throw new AssertionError(); }
+    }
+    private static CodeGen graph() {
+        CodeGen code = new CodeGen("");
+        code._mach = new x86_64_v2();
+        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)));
+    }
+
+    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 = code._mach.split("test",(byte)0,null);
+            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 = code._mach.split("test",(byte)0,null);
+            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 = pre._mach.split("test",(byte)0,null);
+        copy.setDef(0,pre._start); copy.setDef(1,def0);
+        assertFalse("A fixed definition clobbers even before coloring",uncolored.sameBlockNoClobber(copy));
+    }
+
+}
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java
index 851380cf..586924b2 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java
@@ -2,7 +2,7 @@ package com.seaofnodes.simple.fuzzer;
 
 import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.Eval2;
-import com.seaofnodes.simple.CodeGen;
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.Node;
 import java.util.ArrayList;
 import java.util.Objects;
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java
index 5c89a485..a2137314 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java
@@ -1,7 +1,7 @@
 package com.seaofnodes.simple.fuzzer;
 
-import com.seaofnodes.simple.CodeGen;
 import com.seaofnodes.simple.IterPeeps;
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.Node;
 import com.seaofnodes.simple.node.StopNode;
 import com.seaofnodes.simple.type.TypeInteger;