diff options
| author | Cliff Click <cliffc@acm.org> | 2026-10-07 21:31:18 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-07 21:31:18 -0700 |
| commit | 87a75c83b75480e65147a4d425fddd14a05df4d9 (patch) | |
| tree | f486050aa3a13e218ad17ab57efaccbe35336483 | |
| parent | 2eba63966bdc3d9cfdf41ee085f35cbb6d529bbc (diff) | |
| download | Simple-87a75c83b75480e65147a4d425fddd14a05df4d9.tar.gz Simple-87a75c83b75480e65147a4d425fddd14a05df4d9.zip | |
More test case vs RA cleanup
Missing a few risc/arm encodings.
Make private many tests, so they don't escape and the escaped fcn inflate x86 spill numbers
62 files changed, 829 insertions, 284 deletions
diff --git a/build-support/AllocMetrics.java.in b/build-support/AllocMetrics.java.in new file mode 100644 index 00000000..bcf97f0d --- /dev/null +++ b/build-support/AllocMetrics.java.in @@ -0,0 +1,176 @@ +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.isa.eval.*; +import java.nio.file.*; +import java.util.*; + +// Compiled separately against each chapter. No compiler or emulator mutation. +public class Measure { + static final int CH=CHAPTER; + static int start(Encoding e,Node n) { return OPSTART; } + static int length(Encoding e,Node n) { return OPLEN & 255; } + static final Map<String,Type> returns=new HashMap<>(); + static CodeGen compile(String src,String cpu) { + CodeGen c=CONSTRUCTOR.driver(CodeGen.Phase.TypeCheck); + EXTERNDATA + returns.clear(); + c._stop.walk(n->{if(n instanceof FunNode f && f.ret()!=null)returns.put(f._name,f.ret().expr()._type);return null;}); + RESUME + } + static byte[] image(CodeGen c) throws Exception { + c.encode(); + var externalField=Encoding.class.getDeclaredField("_externals");externalField.setAccessible(true); + @SuppressWarnings("unchecked") var externals=(Map<Node,String>)externalField.get(c._encoding); + var extra=new LinkedHashMap<Node,String>(); + for(var e:externals.entrySet())if(!e.getValue().equals("calloc")&&!e.getValue().equals("write")){extra.put(e.getKey(),e.getValue());e.setValue("write");} + EXPORT; + for(var e:extra.entrySet()){ + Node n=e.getKey();String name=e.getValue();externals.put(n,name); + int target=name.equals("read")?-12:name.equals("errno")?0x3808:-16; + ((RIPRelSize)n).patch(c._encoding,start(c._encoding,n),(byte)length(c._encoding,n),target-start(c._encoding,n)); + } + byte[] image=new byte[16<<20]; + var e=c._encoding; + System.arraycopy(e.bits(),0,image,0,e._bits.size()); + COPYPOOLS + return image; + } + static class CPU { + EvalRisc5 r; EvalArm64 a; long[] regs; double[] fregs; byte[] mem; + long ops,ra; BitSet added; int inputPos; + final byte[] input="[4, 3, 2, 1]".getBytes(java.nio.charset.StandardCharsets.UTF_8); + CPU(String cpu,byte[] img,BitSet additions) { + mem=img; added=additions; + if(cpu.equals("riscv")) { r=new EvalRisc5(img,1<<20); regs=r.regs; fregs=r.fregs; } + else { a=new EvalArm64(img,1<<20); regs=a.regs; fregs=a.fregs; } + } + int base(){return r!=null?10:0;} + int pc(){return r!=null?r._pc:a._pc;} + void pc(int p){if(r!=null)r._pc=p;else a._pc=p;} + long load(int p,int sz){long x=0;for(int i=0;i<sz;i++)x|=(mem[p+i]&255L)<<(8*i);return x;} + void store(int p,long x,int sz){for(int i=0;i<sz;i++)mem[p+i]=(byte)(x>>(8*i));} + String stdout(){var s=r!=null?r._stdout:a._stdout;return s==null?"":s.toString(java.nio.charset.StandardCharsets.UTF_8);} + void run(int entry) { + pc(entry);regs[r!=null?1:30]=0; + for(int i=0;i<2_000_000;i++) { + int p=pc(),ir=(int)load(p,4); + int target=Integer.MAX_VALUE; + if(r!=null) { + if((ir&127)==0x67)target=(int)((regs[(ir>>>15)&31]+(ir>>20))&~1L); + else if((ir&127)==0x6f){int d=((ir>>31)<<20)|((ir>>>21&1023)<<1)|((ir>>>20&1)<<11)|(ir&0xff000);target=p+d;} + }else if((ir&0xfc000000)==0x94000000)target=p+((ir<<6)>>4); + else if((ir&0xfffffc1f)==0xd63f0000)target=(int)regs[(ir>>>5)&31]; + if(target==-12) { + int len=Math.min((int)regs[base()+2],input.length-inputPos); + System.arraycopy(input,inputPos,mem,(int)regs[base()+1],len);inputPos+=len; + regs[base()]=len;regs[r!=null?1:30]=p+4;pc(p+4); + ops++;if(added.get(p))ra++;continue; + } + boolean ret=r!=null + ? (ir&127)==0x67 && ((regs[(ir>>>15)&31]+(ir>>20))&~1L)==0 + : (ir&0xfffffc1f)==0xd65f0000 && regs[(ir>>>5)&31]==0; + int trap=r!=null?r.step(1):a.step(1); + if(trap!=0)throw new IllegalStateException("trap="+trap+" pc="+p+" ir="+Integer.toHexString(ir)); + if((pc()&3)!=0)throw new IllegalStateException("unaligned next pc="+pc()+" from="+p+" ir="+Integer.toHexString(ir)+" rpc="+regs[r!=null?1:30]); + ops++;if(added.get(p))ra++; + if(ret)return; + } + throw new IllegalStateException("instruction budget exhausted"); + } + } + static String result(CPU cpu,Type t,long x,int depth) { + if(depth>4)return "..."; + if(t instanceof TypeInteger ti) return Long.toString(x); + if(t instanceof TypeFloat) return Double.toString(Double.longBitsToDouble(x)); + if(t instanceof TypeMemPtr p) { + if(x==0)return "null"; + TypeStruct s=p._obj;int addr=(int)x; + if(s.isAry()) { + int len=(int)cpu.load(addr,4); + if(len<0||len>10000)throw new AssertionError("array length "+len); + int scale=s.aryScale(),base=s.aryBase(); + var out=new StringBuilder("["); + for(int i=0;i<len;i++)out.append(cpu.load(addr+base+(i<<scale),1<<scale)).append(','); + return out.append(']').toString(); + } + var out=new StringBuilder("{"); + for(int i=0;i<s._fields.length;i++) { + Type ft=s._fields[i]._t; + out.append(s._fields[i]._fname).append('='); + out.append(result(cpu,ft,cpu.load(addr+s.offset(i),1<<ft.log_size()),depth+1)).append(','); + } + return out.append('}').toString(); + } + return Long.toString(x); + } + public static void main(String[] args)throws Exception { + Path index=Path.of(args[0]); + int attempts=0, failures=0; + for(String line:Files.readAllLines(index)) { + if(line.startsWith("#")||line.isBlank())continue; + String[] row=line.split("\t"); + String cohort=row[0],test=row[1],cpu=row[2],file=row[4]; + if(!cpu.equals("arm")&&!cpu.equals("riscv"))continue; + String shortTest=test.substring(test.indexOf('.')+1); + String filter=System.getenv("DYNAMIC_CASE"); + if(filter!=null&&!test.equals(filter))continue; + // Inputs are fixed per program and shared across compiler chapters. + String entry=switch(shortTest){case "testFibExport"->"fib";case "testNewtonExport"->"test_sqrt";case "testSieve"->"sieve";case "testBubbleSort"->"main";default->"";}; + boolean skip=switch(shortTest){case "testString","testStringExport","testFltArg","testInfinite","testInfiniteReturn","testPerson","testArgCount","testStackArguments","testMergeSort0","testBrainFuck"->true;default->false;}; + if(skip){System.out.println("skip,"+cohort+","+test+","+cpu+",needs driver or does not terminate");continue;} + long[] inputs=switch(shortTest){case "testAlloc2"->new long[]{0,1,2};case "testFibExport"->new long[]{9};case "testSieve"->new long[]{100};case "testNewtonExport","testNewtonFloat","testNewtonInteger","testArray1","testMergeSort","testAlloc0"->new long[]{16};case "testStack13","testFlags1","testFlags2","testCast","testAndPtr","testOrRhsLoopLocal","testOrRhsLoopMemory"->new long[]{0,1,2,3};default->new long[]{0};}; + attempts++; + try { + CodeGen c=compile(Files.readString(index.getParent().resolve(file)),cpu); + Set<Node> before=Collections.newSetFromMap(new IdentityHashMap<>()); + for(var bb:c._cfg){before.add(bb);for(Node n:bb._outputs)before.add(n);} + c.regAlloc(); + Set<Node> added=Collections.newSetFromMap(new IdentityHashMap<>()); + for(var bb:c._cfg)for(Node n:bb._outputs) + if(n instanceof SplitNode || (!before.contains(n)&&n instanceof MachNode m&&m.isClone()))added.add(n); + byte[] img=image(c); + if(filter!=null)System.out.println(c.asm()); + BitSet pcs=new BitSet(); + for(Node n:added){int s=start(c._encoding,n),len=length(c._encoding,n);if(s>=0&&len>0)pcs.set(s,s+len);} + FunNode init=null,fun=null; + for(var bb:c._cfg)if(bb instanceof FunNode f){ + if(f._name.equals(CH==25?"class:Test.<clinit>":"main"))init=f; + if(f._name.equals(entry))fun=f; + } + if(entry.isEmpty())fun=init; + if(fun==null)throw new IllegalStateException("No entry "+entry); + Type ret=returns.get(fun._name); + long ops=0,ra=0;var results=new ArrayList<String>(); + for(long arg:inputs){ + CPU machine=new CPU(cpu,img.clone(),pcs); + if(shortTest.equals("testExternDataEncoding"))machine.store(0x3800,-7,4); + if(!entry.isEmpty()&&init!=null&&init!=fun)machine.run(start(c._encoding,init)); + for(Node n:fun._outputs)if(n instanceof ParmNode parm && n instanceof MachNode m && !parm.label().equals("$rpc")) { + if(parm._type instanceof TypeInteger)machine.regs[m.outregmap().firstReg()]=arg; + if(parm._type instanceof TypeFloat)machine.fregs[m.outregmap().firstReg()-32]=arg; + } + machine.run(start(c._encoding,fun)); + long value=ret instanceof TypeFloat?Double.doubleToRawLongBits(machine.fregs[cpu.equals("riscv")?10:0]):machine.regs[machine.base()]; + switch(shortTest) { + case "testNewtonInteger": if(value!=8)throw new AssertionError("Newton integer result");break; + case "testNewtonFloat": if(!(Math.abs(Double.longBitsToDouble(value)-(4+Math.sqrt(18)))<=1e-12))throw new AssertionError("Newton float result");break; + case "testNewtonExport": if(!(Math.abs(Double.longBitsToDouble(value)-4)<=1e-12))throw new AssertionError("Newton export result");break; + case "testStack13": if(value!=(arg==0?1:0))throw new AssertionError("Nested equality result");break; + case "testFlags1": if(value!=(arg==1?2:0))throw new AssertionError("Equality result for "+arg+": "+value);break; + case "testArray1": if(value!=1006)throw new AssertionError("Array result");break; + case "testFibExport": if(value!=55)throw new AssertionError("Fibonacci result");break; + case "testOrRhsLoopLocal", "testOrRhsLoopMemory": if(value!=((arg&1)==0?44:1))throw new AssertionError("Short-circuit result");break; + case "testBubbleSort": if(value!=0||!machine.stdout().equals("[1, 2, 3, 4]"))throw new AssertionError("Bubble Sort result: "+value+" stdout="+machine.stdout());break; + case "testExternDataEncoding": if(value!=-4||machine.load(0x3800,4)!=0xfffffffcL)throw new AssertionError("C data result");break; + } + results.add(result(machine,ret,value,0)+"/"+machine.stdout().replace("\n","\\n").replace(",",";")); + ops+=machine.ops;ra+=machine.ra; + } + System.out.println("dynamic,"+cohort+","+test+","+cpu+","+inputs.length+","+ops+","+ra+","+String.join("|",results).replace(",",";")+","+Arrays.toString(inputs).replace(",",";")); + }catch(Throwable e){failures++;System.out.println("FAILED,"+cohort+","+test+","+cpu+","+e); e.printStackTrace(System.err);} + } + System.out.println("Dynamic cases: "+attempts+"; failures: "+failures); + if(failures!=0)System.exit(1); + } +} diff --git a/build-support/capture-alloc-sources.py b/build-support/capture-alloc-sources.py new file mode 100644 index 00000000..f474ac55 --- /dev/null +++ b/build-support/capture-alloc-sources.py @@ -0,0 +1,28 @@ +"""Capture historical spill sources with a temporary instrumented test listener.""" +from pathlib import Path +import subprocess,sys,os +root=Path(__file__).resolve().parents[1] +ch=int(sys.argv[1]); chapter=root/f'chapter{ch}' +if ch not in range(21,25): raise SystemExit("Capture supports chapters 21-24") +out=root/'build/dynamic-stats'/str(ch); out.mkdir(parents=True,exist_ok=True) +src=(chapter/'src/test/java/com/seaofnodes/simple/SpillStats.java').read_text() +needle='String test = ACTIVE._test.getTestClass().getSimpleName()+"."+ACTIVE._test.getMethodName();' +extra=''' + try { + var dir=java.nio.file.Path.of("../build/dynamic-stats/CH/captured"); + java.nio.file.Files.createDirectories(dir); + String name=test+"-"+cpu+"-"+abi+"-"+(_capture++)+".smp"; + java.nio.file.Files.writeString(dir.resolve(name),code._src); + java.nio.file.Files.writeString(dir.resolve("index.tsv"),cohort+"\\t"+test+"\\t"+cpu+"\\t"+abi+"\\t"+name+"\\n",java.nio.file.StandardOpenOption.CREATE,java.nio.file.StandardOpenOption.APPEND); + } catch(java.io.IOException e) { throw new RuntimeException(e); } +'''.replace('CH',str(ch)) +assert needle in src +src=src.replace(needle,needle+extra).replace('private static SpillStats ACTIVE;','private static SpillStats ACTIVE;\n private static int _capture;') +(out/'SpillStats.java').write_text(src,newline='\n') +cp=os.pathsep.join([str(chapter/'build/classes/main'),str(chapter/'build/classes/test'),str(chapter/'lib/*')]) +subprocess.run(['javac','-cp',cp,'-d',str(out),str(out/'SpillStats.java')],check=True) +idx=out/'captured/index.tsv' +if idx.exists(): idx.write_text('') +with (out/'capture.log').open('w') as log: + subprocess.run(['java','-ea','-cp',str(out)+os.pathsep+cp,'com.seaofnodes.simple.SpillStats'],cwd=chapter,stdout=log,stderr=subprocess.STDOUT,check=True) +print(ch,'captured',len(idx.read_text().splitlines())) diff --git a/build-support/measure-alloc.py b/build-support/measure-alloc.py new file mode 100644 index 00000000..61ae31e2 --- /dev/null +++ b/build-support/measure-alloc.py @@ -0,0 +1,41 @@ +"""Compile the shared measurement harness against one chapter's existing classes.""" +from pathlib import Path +import json,os,re,subprocess,sys +root=Path(__file__).resolve().parents[1]; ch=int(sys.argv[1]); chapter=root/f'chapter{ch}' +if ch not in range(21,26): raise SystemExit("Dynamic measurement supports chapters 21-25") +out=root/'build/dynamic-stats'/str(ch);out.mkdir(parents=True,exist_ok=True) +src=(root/'build-support/AllocMetrics.java.in').read_text() +subs={'CHAPTER':str(ch),'OPSTART':'e.opStart(n)' if ch==25 else 'e._opStart[n._nid]', + 'OPLEN':'e.opLen(n)' if ch==25 else 'e._opLen[n._nid]', + 'CONSTRUCTOR':'new CodeGen(src,123L,true)' if ch==25 else 'new CodeGen(src,TypeInteger.BOT,123L,true)', + 'EXPORT':'c.exportELF(true,false)' if ch==25 else 'c.exportELF(null)', + 'EXTERNDATA':'c._externDataAddresses.put("counter",0x3800);c._externDataAddresses.put("errno",0x3808);' if ch==25 else '', + 'RESUME':'return c.loopTree().instSelect(cpu,"SystemV").GCM().localSched();' if ch==21 else 'return c.driver(CodeGen.Phase.LocalSched,cpu,"SystemV");', + 'COPYPOOLS':'''int cp=(e._bits.size()+15)&-16,sd=(cp+e._cpool.size()+15)&-16; + System.arraycopy(e._cpool.buf(),0,image,cp,e._cpool.size()); + System.arraycopy(e._sdata.buf(),0,image,sd,e._sdata.size());''' if ch==25 else ''} +for a,b in subs.items():src=src.replace(a,b) +if ch<=22: + src=src.replace('TypeInteger.BOT,123L,true','TypeInteger.BOT,123L').replace('s._fields[i]._t','s._fields[i]._type') +(out/'Measure.java').write_text(src,newline='\n') +cp=os.pathsep.join([str(chapter/'build/classes/main'),str(chapter/'build/classes/test'),str(chapter/'lib/*')]) +subprocess.run(['javac','-cp',cp,'-d',str(out),str(out/'Measure.java')],check=True) +subprocess.run(['javac','-cp',cp,'-d',str(out),*[str(p) for p in (root/'isa/src/test-support/java/com/seaofnodes/isa/eval').glob('*.java')]],check=True) +if ch==25: + p=root/'chapter25/src/test/java/com/seaofnodes/simple/spill' + index=out/'index.tsv' + rows=[] + for line in (p/'cohorts.tsv').read_text().splitlines(): + if line.startswith('#') or not line:continue + r=line.split('\t');rows.append('\t'.join(r[:4]+[str(p/r[5])])) + test=(chapter/'src/test/java/com/seaofnodes/simple/Chapter25Test.java').read_text(encoding='utf-8') + body=test.split('void testExternDataEncoding()',1)[1].split('@Test',1)[0] + literal=re.search(r'new CheckedCodeGen\(("(?:\\.|[^"\\])*")\)',body) + if literal is None: raise SystemExit('Cannot capture testExternDataEncoding source') + extra=out/'extern-data.smp';extra.write_text(json.loads(literal[1])+'\n',encoding='utf-8',newline='\n') + for cpu in ['arm','riscv']:rows.append('\t'.join(['Chapter25','Chapter25Test.testExternDataEncoding',cpu,'SystemV',str(extra)])) + index.write_text('\n'.join(rows)+'\n') +else:index=out/'captured/index.tsv' +with (out/'dynamic.log').open('w') as log: + subprocess.run(['java','-ea','-cp',str(out)+os.pathsep+cp,'Measure',str(index)],cwd=chapter,stdout=log,stderr=subprocess.STDOUT,check=True) +print(ch, 'done') diff --git a/build-support/spill-matrix.py b/build-support/spill-matrix.py index 77c617a1..9ee8f7eb 100644 --- a/build-support/spill-matrix.py +++ b/build-support/spill-matrix.py @@ -1,5 +1,5 @@ #!/usr/bin/env python3 -"""Measure allocator chapters, check cohort membership, and render scaled spills.""" +"""Measure fixed cohorts: dynamic ARM/RISC-V ops, allocator ops, and x86 estimates.""" import argparse from collections import Counter, defaultdict from pathlib import Path @@ -60,13 +60,69 @@ def read_results(log_dir): return results -def table(results, last=25): +def read_dynamic(results): + dynamic = {} + values = {} + records = [] + for chapter in range(21, 26): + path = ROOT / f"build/dynamic-stats/{chapter}/dynamic.log" + text = read_log(path) + if "FAILED," in text: + raise ValueError(f"Dynamic measurement failed; see {path}") + completion = re.search(r"Dynamic cases: (\d+); failures: 0", text) + if not completion: + raise ValueError(f"Incomplete dynamic measurement; see {path}") + cohorts = defaultdict(list) + for line in text.splitlines(): + if not line.startswith("dynamic,"): + continue + _, cohort, test, cpu, count, ops, ra, value, inputs = line.split(",") + cohort = int(cohort.removeprefix("Chapter")) + test = test.removeprefix("Chapter25Test.") if cohort == 25 else test + row = (test, cpu, inputs, int(count), int(ops), int(ra)) + cohorts[cohort].append(row) + identity = (cohort, test, inputs) + if identity in values and values[identity] != value: + raise ValueError(f"Dynamic results disagree: {identity}: {values[identity]} vs {value}") + values[identity] = value + records.append(f"{chapter},{cohort},{test},{cpu},{inputs},{count},{ops},{ra},{value}") + if set(cohorts) != set(range(20, chapter+1)): + raise ValueError(f"Missing dynamic cohort in Chapter {chapter}") + if sum(map(len, cohorts.values())) != int(completion[1]): + raise ValueError(f"Dynamic record count differs from completion record in {path}") + for cohort, rows in cohorts.items(): + available = Counter((r[0], r[1]) for r in results[chapter][cohort]) + measured = Counter(r[:2] for r in rows) + if measured - available: + raise ValueError(f"Dynamic cases absent from static cohort {chapter}/{cohort}") + dynamic[chapter] = cohorts + for cohort in CHAPTERS: + first = max(21, cohort) + baseline = Counter(r[:4] for r in dynamic[first][cohort]) + for chapter in range(first+1, 26): + if Counter(r[:4] for r in dynamic[chapter][cohort]) != baseline: + raise ValueError(f"Dynamic membership/inputs changed: {chapter}/{cohort}") + header = "compiler,cohort,test,cpu,inputs,runs,instructions,allocator_instructions,result\n" + (ROOT / "build/spill-stats/dynamic-counts.csv").write_text(header+"\n".join(records)+"\n", encoding="utf-8", newline="\n") + return dynamic + + +def table(results, dynamic, last=25): chapters = range(20, last + 1) - lines = ["| Test cohort | # tests | " + " | ".join(f"Ch {c}" for c in chapters) + " |", + lines = ["| Test cohort | Cases D / X | " + " | ".join(f"Ch {c}: Ops / RA / X" for c in chapters) + " |", "|---|---:|" + "---:|" * len(chapters)] for cohort in chapters: - cells = [f"Ch {cohort}", str(len(results[cohort][cohort]))] - cells += ["" if c < cohort else f"{sum(r[4] for r in results[c][cohort]):,}" for c in chapters] + count = len(dynamic[max(21,cohort)][cohort]) + nx = sum(r[1]=="x86_64_v2" for r in results[cohort][cohort]) + cells = [f"Ch {cohort}", f"{count} / {nx}"] + for c in chapters: + if c < cohort: + cells.append("") + continue + x = sum(r[4] for r in results[c][cohort] if r[1]=="x86_64_v2") + ops = f"{sum(r[4] for r in dynamic[c][cohort]):,}" if c>=21 else "—" + ra = f"{sum(r[5] for r in dynamic[c][cohort]):,}" if c>=21 else "—" + cells.append(f"{ops} / {ra} / {x:,}") lines.append("| " + " | ".join(cells) + " |") return "\n".join(lines) @@ -97,12 +153,17 @@ def main(): stdout=log, stderr=subprocess.STDOUT) if run.returncode: raise ValueError(f"Chapter {chapter} failed (exit {run.returncode}); see {path}") + for chapter in range(21, 26): + if chapter < 25: + subprocess.run([sys.executable, str(ROOT / "build-support/capture-alloc-sources.py"), str(chapter)], check=True) + subprocess.run([sys.executable, str(ROOT / "build-support/measure-alloc.py"), str(chapter)], check=True) results = read_results(args.log_dir) - matrix = table(results) + dynamic = read_dynamic(results) + matrix = table(results, dynamic) (args.log_dir / "matrix.md").write_text(matrix + "\n", encoding="utf-8", newline="\n") if args.update_docs: paths = [(ROOT / "docs/regalloc-spills.md", matrix)] - paths += [(ROOT / f"chapter{c}/README.md", table(results, c)) for c in CHAPTERS] + paths += [(ROOT / f"chapter{c}/README.md", table(results, dynamic, c)) for c in CHAPTERS] # Validate all destinations before changing any document. for path, _ in paths: text = path.read_text(encoding="utf-8") diff --git a/chapter20/README.md b/chapter20/README.md index 9f7cb1c5..96803e51 100644 --- a/chapter20/README.md +++ b/chapter20/README.md @@ -503,16 +503,18 @@ two-address operands, and Phi register agreement; tiny machine graphs exercise hard conflicts independently of optimizer choices. Native execution comes with encoding in Chapter 21. -Rows are fixed test cohorts; columns are the compiler/allocator chapters. -Each cell is the sum of `_spillScaled`: retained split moves, including register -copies, weighted by `8^loopDepth`. Lower is better. **# tests counts compilations** -(program/CPU/ABI cases), including zero-spill cases, rather than JUnit methods. -The count and membership of each row stay fixed across columns. +Rows are fixed test cohorts; columns are compiler chapters. Each cell gives +**Ops / RA / X**: executed ARM+RISC-V instructions, the subset emitted for +allocator copies/rematerializations, and x86's loop-weighted split-move estimate. +**Cases D / X** counts measured dynamic program/target cases and x86 compilations; +membership and inputs stay fixed across columns. Native-library work is excluded. +Chapter 20 has no encoder, hence no dynamic counts. Lower is better within each +metric; see the [measurement details](../docs/regalloc-spills.md) for coverage. <!-- spill-matrix:start --> -| Test cohort | # tests | Ch 20 | +| Test cohort | Cases D / X | Ch 20: Ops / RA / X | |---|---:|---:| -| Ch 20 | 39 | 360 | +| Ch 20 | 22 / 13 | — / — / 161 | <!-- spill-matrix:end --> These Windows measurements use optimizer seed 123 for cohorts 20-24 and include diff --git a/chapter21/README.md b/chapter21/README.md index 63b02ae9..80304c1a 100644 --- a/chapter21/README.md +++ b/chapter21/README.md @@ -147,22 +147,24 @@ its two-address operand. For example, `mov rpc=s8; st1 [rpc+4],s1` becomes Phi and control-flow users are excluded. This local cleanup leaves spill selection unchanged; it complements coalescing without another CFG analysis. -For looking at allocator progress, we will keep a table of weighted spill costs +For looking at allocator progress, we will keep a table of execution and allocation costs a chapters' tests - and use the later chapter compiler and register allocator on them. The later chapters also modify the graph (sometimes adding boiler plate graph) so its not really a 100% fair comparison of how well this *heuristic* does, but it does give us some idea that we're not losing ground. -Rows are fixed test cohorts; columns are the compiler/allocator chapters. Each -cell is the sum of `_spillScaled`: retained split moves, including register -copies, weighted by loopDepth. Lower is better. **# tests counts -compilations** (program/CPU/ABI cases), including zero-spill cases, rather than -JUnit methods. The count and membership of each row stay fixed across columns. +Rows are fixed test cohorts; columns are compiler chapters. Each cell gives +**Ops / RA / X**: executed ARM+RISC-V instructions, the subset emitted for +allocator copies/rematerializations, and x86's loop-weighted split-move estimate. +**Cases D / X** counts measured dynamic program/target cases and x86 compilations; +membership and inputs stay fixed across columns. Native-library work is excluded. +Chapter 20 has no encoder, hence no dynamic counts. Lower is better within each +metric; see the [measurement details](../docs/regalloc-spills.md) for coverage. <!-- spill-matrix:start --> -| Test cohort | # tests | Ch 20 | Ch 21 | +| Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | |---|---:|---:|---:| -| Ch 20 | 39 | 360 | 576 | -| Ch 21 | 52 | | 1,072 | +| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | +| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | <!-- spill-matrix:end --> diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java index 5fa68e19..6fd4274a 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java @@ -17,7 +17,7 @@ public class LoadARM extends MemOpARM { super(ld, base, idx, off, 0); } @Override public String op() { return "ld"+_sz; } - @Override public RegMask outregmap() { return size() >= 4 ? arm.MEM_MASK : arm.RMASK; } + @Override public RegMask outregmap() { return size() >= 4 ? arm.MEM_MASK : arm.WMASK; } private static final int[] OP_LOADS = new int[]{ Arm64.OP_LOAD_IMM_8, Arm64.OP_LOAD_IMM_16, Arm64.OP_LOAD_IMM_32, Arm64.OP_LOAD_IMM_64, }; diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java index 5c388bab..ec017032 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java @@ -19,9 +19,9 @@ public class NotARM extends MachConcreteNode implements MachNode{ // subtracting zero from rs will just yield rs, it sets the zero flag and then it's used in cset short self = enc.reg(this ); short reg1 = enc.reg(in(1)); - int subs = Arm64.imm_inst(Arm64.OP_SUBS, 0, reg1, self); + int subs = Arm64.imm_inst(Arm64.OP_SUBS, 0, reg1, 31); enc.add4(subs); - int cset = Arm64.cond_set(Arm64.OP_CSET, 31, Arm64.COND.EQ, 63, reg1); + int cset = Arm64.cset(Arm64.OP_CSET, 31, Arm64.COND.EQ, 31, self); enc.add4(cset); } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index 4006565e..66a59fde 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java @@ -215,7 +215,7 @@ public class arm extends Machine { public static void f_cmp(Encoding enc, Node n) { short reg1 = (short)(enc.reg(n.in(1))-D_OFFSET); short reg2 = (short)(enc.reg(n.in(2))-D_OFFSET); - int body = Arm64.f_cmp(0b00011110, 3, reg1, reg2); + int body = Arm64.f_cmp(0b00011110, 3, reg2, reg1); enc.add4(body); } @@ -325,7 +325,7 @@ public class arm extends Machine { private Node cmp(BoolNode bool){ Node cmp = _cmp(bool); - return new SetARM(cmp, IfNode.negate(bool.op())); + return new SetARM(cmp, bool.op()); } private Node _cmp(BoolNode bool) { if( bool.isFloat() ) diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java index 469221f3..6aefc54b 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java @@ -15,7 +15,8 @@ public class NotRISC extends MachConcreteNode implements MachNode { @Override public void encoding( Encoding enc ) { short dst = enc.reg(this ); short src = enc.reg(in(1)); - enc.add4(RiscV.i_type(RiscV.OP_IMM, dst, 2, src, 1)); + // SEQZ is unsigned: negative nonzero inputs must also produce false. + enc.add4(RiscV.i_type(RiscV.OP_IMM, dst, 3, src, 1)); } @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)); } } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java index f270bf12..8b6512e1 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java @@ -7,7 +7,11 @@ import com.seaofnodes.simple.node.Node; public class SetIRISC extends ImmRISC { final boolean _unsigned; // slti vs sltiu public SetIRISC( Node src, int imm12, boolean unsigned ) { - super(src,imm12); + this(src,imm12,unsigned,true); + } + public SetIRISC( Node src, int imm12, boolean unsigned, boolean pop ) { + super(src,imm12,pop); + if( !pop ) _inputs.setLen(2); _unsigned = unsigned; } @Override public String op() { return "slt" + (_unsigned ? "u":"") + "i"; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java index 7e840509..335347e9 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java @@ -304,7 +304,7 @@ public class riscv extends Machine { // x <= y - flip and negate; !(y < x); `slt tmp=y,x; xori dst=tmp,#1` case "<=" -> new XorIRISC(new SetRISC(bool.swap12(), false),1); // x == y - sub and vs0 == `sub tmp=x-y; sltu dst=tmp,#1` - case "==" -> new SetIRISC(new SubRISC(bool),1,true); + case "==" -> new SetIRISC(new SubRISC(bool),1,true,false); default -> throw Utils.TODO(); }; } diff --git a/chapter22/README.md b/chapter22/README.md index 1f839de5..00ae6183 100644 --- a/chapter22/README.md +++ b/chapter22/README.md @@ -203,16 +203,18 @@ are small preferences, not a general cost model. Grouping popular values by register class is left for Chapter 23, cold loop splits for 24, and area/cost ranking for 25. -Rows are fixed test cohorts; columns are the compiler/allocator chapters. Each -cell is the sum of `_spillScaled`: retained split moves, including register -copies, weighted by loopDepth. Lower is better. **# tests counts -compilations** (program/CPU/ABI cases), including zero-spill cases, rather than -JUnit methods. The count and membership of each row stay fixed across columns. +Rows are fixed test cohorts; columns are compiler chapters. Each cell gives +**Ops / RA / X**: executed ARM+RISC-V instructions, the subset emitted for +allocator copies/rematerializations, and x86's loop-weighted split-move estimate. +**Cases D / X** counts measured dynamic program/target cases and x86 compilations; +membership and inputs stay fixed across columns. Native-library work is excluded. +Chapter 20 has no encoder, hence no dynamic counts. Lower is better within each +metric; see the [measurement details](../docs/regalloc-spills.md) for coverage. <!-- spill-matrix:start --> -| Test cohort | # tests | Ch 20 | Ch 21 | Ch 22 | +| Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | Ch 22: Ops / RA / X | |---|---:|---:|---:|---:| -| Ch 20 | 39 | 360 | 576 | 430 | -| Ch 21 | 52 | | 1,072 | 960 | -| Ch 22 | 26 | | | 63 | +| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | +| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | 6,324 / 379 / 475 | +| Ch 22 | 14 / 8 | | | 198 / 60 / 7 | <!-- spill-matrix:end --> diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java index 5fa68e19..6fd4274a 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java @@ -17,7 +17,7 @@ public class LoadARM extends MemOpARM { super(ld, base, idx, off, 0); } @Override public String op() { return "ld"+_sz; } - @Override public RegMask outregmap() { return size() >= 4 ? arm.MEM_MASK : arm.RMASK; } + @Override public RegMask outregmap() { return size() >= 4 ? arm.MEM_MASK : arm.WMASK; } private static final int[] OP_LOADS = new int[]{ Arm64.OP_LOAD_IMM_8, Arm64.OP_LOAD_IMM_16, Arm64.OP_LOAD_IMM_32, Arm64.OP_LOAD_IMM_64, }; diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java index 5c388bab..ec017032 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java @@ -19,9 +19,9 @@ public class NotARM extends MachConcreteNode implements MachNode{ // subtracting zero from rs will just yield rs, it sets the zero flag and then it's used in cset short self = enc.reg(this ); short reg1 = enc.reg(in(1)); - int subs = Arm64.imm_inst(Arm64.OP_SUBS, 0, reg1, self); + int subs = Arm64.imm_inst(Arm64.OP_SUBS, 0, reg1, 31); enc.add4(subs); - int cset = Arm64.cond_set(Arm64.OP_CSET, 31, Arm64.COND.EQ, 63, reg1); + int cset = Arm64.cset(Arm64.OP_CSET, 31, Arm64.COND.EQ, 31, self); enc.add4(cset); } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index da5e6d4b..ddd9797b 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java @@ -215,7 +215,7 @@ public class arm extends Machine { public static void f_cmp(Encoding enc, Node n) { short reg1 = (short)(enc.reg(n.in(1))-D_OFFSET); short reg2 = (short)(enc.reg(n.in(2))-D_OFFSET); - int body = Arm64.f_cmp(0b00011110, 3, reg1, reg2); + int body = Arm64.f_cmp(0b00011110, 3, reg2, reg1); enc.add4(body); } @@ -327,7 +327,7 @@ public class arm extends Machine { private Node cmp(BoolNode bool){ Node cmp = _cmp(bool); - return new SetARM(cmp, IfNode.negate(bool.op())); + return new SetARM(cmp, bool.op()); } private Node _cmp(BoolNode bool) { if( bool.isFloat() ) diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java index 469221f3..6aefc54b 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java @@ -15,7 +15,8 @@ public class NotRISC extends MachConcreteNode implements MachNode { @Override public void encoding( Encoding enc ) { short dst = enc.reg(this ); short src = enc.reg(in(1)); - enc.add4(RiscV.i_type(RiscV.OP_IMM, dst, 2, src, 1)); + // SEQZ is unsigned: negative nonzero inputs must also produce false. + enc.add4(RiscV.i_type(RiscV.OP_IMM, dst, 3, src, 1)); } @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)); } } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java index f270bf12..8b6512e1 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java @@ -7,7 +7,11 @@ import com.seaofnodes.simple.node.Node; public class SetIRISC extends ImmRISC { final boolean _unsigned; // slti vs sltiu public SetIRISC( Node src, int imm12, boolean unsigned ) { - super(src,imm12); + this(src,imm12,unsigned,true); + } + public SetIRISC( Node src, int imm12, boolean unsigned, boolean pop ) { + super(src,imm12,pop); + if( !pop ) _inputs.setLen(2); _unsigned = unsigned; } @Override public String op() { return "slt" + (_unsigned ? "u":"") + "i"; } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java index a1e3b767..f2d1e0b9 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java @@ -305,7 +305,7 @@ public class riscv extends Machine { // x <= y - flip and negate; !(y < x); `slt tmp=y,x; xori dst=tmp,#1` case "<=" -> new XorIRISC(new SetRISC(bool.swap12(), false),1,false); // x == y - sub and vs0 == `sub tmp=x-y; sltu dst=tmp,#1` - case "==" -> new SetIRISC(new SubRISC(bool),1,true); + case "==" -> new SetIRISC(new SubRISC(bool),1,true,false); default -> throw Utils.TODO(); }; } diff --git a/chapter23/README.md b/chapter23/README.md index 7dbe385b..85a5b201 100644 --- a/chapter23/README.md +++ b/chapter23/README.md @@ -445,17 +445,19 @@ the fallback, including splitting an existing copy when all uses have the same loop depth. Cold-first loop splitting is left for Chapter 24; area/cost spill ranking remains for Chapter 25. -Rows are fixed test cohorts; columns are the compiler/allocator chapters. Each -cell is the sum of `_spillScaled`: retained split moves, including register -copies, weighted by loopDepth. Lower is better. **# tests counts -compilations** (program/CPU/ABI cases), including zero-spill cases, rather than -JUnit methods. The count and membership of each row stay fixed across columns. +Rows are fixed test cohorts; columns are compiler chapters. Each cell gives +**Ops / RA / X**: executed ARM+RISC-V instructions, the subset emitted for +allocator copies/rematerializations, and x86's loop-weighted split-move estimate. +**Cases D / X** counts measured dynamic program/target cases and x86 compilations; +membership and inputs stay fixed across columns. Native-library work is excluded. +Chapter 20 has no encoder, hence no dynamic counts. Lower is better within each +metric; see the [measurement details](../docs/regalloc-spills.md) for coverage. <!-- spill-matrix:start --> -| Test cohort | # tests | Ch 20 | Ch 21 | Ch 22 | Ch 23 | +| Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | Ch 22: Ops / RA / X | Ch 23: Ops / RA / X | |---|---:|---:|---:|---:|---:| -| Ch 20 | 39 | 360 | 576 | 430 | 442 | -| Ch 21 | 52 | | 1,072 | 960 | 961 | -| Ch 22 | 26 | | | 63 | 63 | -| Ch 23 | 24 | | | | 103 | +| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | 58,736 / 9,084 / 184 | +| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | 6,324 / 379 / 475 | 6,326 / 381 / 475 | +| Ch 22 | 14 / 8 | | | 198 / 60 / 7 | 194 / 56 / 7 | +| Ch 23 | 14 / 8 | | | | 630 / 160 / 36 | <!-- spill-matrix:end --> diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java index f3bbbbeb..8fc22a67 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java @@ -17,7 +17,7 @@ public class LoadARM extends MemOpARM { super(ld, base, idx, off, 0); } @Override public String op() { return "ld"+_sz; } - @Override public RegMask outregmap() { return size() >= 4 ? arm.MEM_MASK : arm.RMASK; } + @Override public RegMask outregmap() { return size() >= 4 ? arm.MEM_MASK : arm.WMASK; } private static final int[] OP_LOADS = new int[]{ Arm64.OP_LOAD_IMM_8, Arm64.OP_LOAD_IMM_16, Arm64.OP_LOAD_IMM_32, Arm64.OP_LOAD_IMM_64, }; diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java index 8cf72aaf..f8e450f6 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java @@ -18,9 +18,9 @@ public class NotARM extends MachConcreteNode implements MachNode{ // subtracting zero from rs will just yield rs, it sets the zero flag and then it's used in cset short self = enc.reg(this ); short reg1 = enc.reg(in(1)); - int subs = Arm64.imm_inst(Arm64.OP_SUBS, 0, reg1, self); + int subs = Arm64.imm_inst(Arm64.OP_SUBS, 0, reg1, 31); enc.add4(subs); - int cset = Arm64.cond_set(Arm64.OP_CSET, 31, Arm64.COND.EQ, 63, reg1); + int cset = Arm64.cset(Arm64.OP_CSET, 31, Arm64.COND.EQ, 31, self); enc.add4(cset); } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index 8bdcfe10..9faf1d40 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java @@ -215,7 +215,7 @@ public class arm extends Machine { public static void f_cmp(Encoding enc, Node n) { short reg1 = (short)(enc.reg(n.in(1))-D_OFFSET); short reg2 = (short)(enc.reg(n.in(2))-D_OFFSET); - int body = Arm64.f_cmp(0b00011110, 3, reg1, reg2); + int body = Arm64.f_cmp(0b00011110, 3, reg2, reg1); enc.add4(body); } @@ -327,7 +327,7 @@ public class arm extends Machine { private Node cmp(BoolNode bool){ Node cmp = _cmp(bool); - return new SetARM(cmp, IfNode.negate(bool.op())); + return new SetARM(cmp, bool.op()); } private Node _cmp(BoolNode bool) { if( bool.isFloat() ) diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java index dbe9ceb0..6f499db1 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java @@ -15,7 +15,8 @@ public class NotRISC extends MachConcreteNode implements MachNode { @Override public void encoding( Encoding enc ) { short dst = enc.reg(this ); short src = enc.reg(in(1)); - enc.add4(RiscV.i_type(RiscV.OP_IMM, dst, 2, src, 1)); + // SEQZ is unsigned: negative nonzero inputs must also produce false. + enc.add4(RiscV.i_type(RiscV.OP_IMM, dst, 3, src, 1)); } @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)); } } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java index 690e2102..9bc86565 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java @@ -7,7 +7,11 @@ import com.seaofnodes.simple.node.Node; public class SetIRISC extends ImmRISC { final boolean _unsigned; // slti vs sltiu public SetIRISC( Node src, int imm12, boolean unsigned ) { - super(src,imm12); + this(src,imm12,unsigned,true); + } + public SetIRISC( Node src, int imm12, boolean unsigned, boolean pop ) { + super(src,imm12,pop); + if( !pop ) _inputs.setLen(2); _unsigned = unsigned; } @Override public String op() { return "slt" + (_unsigned ? "u":"") + "i"; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java index 78d21f3b..7c994624 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java @@ -305,7 +305,7 @@ public class riscv extends Machine { // x <= y - flip and negate; !(y < x); `slt tmp=y,x; xori dst=tmp,#1` case "<=" -> new XorIRISC(new SetRISC(bool.swap12(), false),1,false); // x == y - sub and vs0 == `sub tmp=x-y; sltu dst=tmp,#1` - case "==" -> new SetIRISC(new SubRISC(bool),1,true); + case "==" -> new SetIRISC(new SubRISC(bool),1,true,false); default -> throw Utils.TODO(); }; } diff --git a/chapter24/README.md b/chapter24/README.md index 07c63ee3..ceb7e03e 100644 --- a/chapter24/README.md +++ b/chapter24/README.md @@ -305,19 +305,21 @@ also covers a backedge-only conflict where the first attempt inserts no copy: that attempt must still consume the one permitted delay. A regression checks both the cheaper first attempt and the mandatory fallback. -Rows are fixed test cohorts; columns are the compiler/allocator chapters. Each -cell is the sum of `_spillScaled`: retained split moves, including register -copies, weighted by loopDepth. Lower is better. **# tests counts -compilations** (program/CPU/ABI cases), including zero-spill cases, rather than -JUnit methods. The count and membership of each row stay fixed across columns. +Rows are fixed test cohorts; columns are compiler chapters. Each cell gives +**Ops / RA / X**: executed ARM+RISC-V instructions, the subset emitted for +allocator copies/rematerializations, and x86's loop-weighted split-move estimate. +**Cases D / X** counts measured dynamic program/target cases and x86 compilations; +membership and inputs stay fixed across columns. Native-library work is excluded. +Chapter 20 has no encoder, hence no dynamic counts. Lower is better within each +metric; see the [measurement details](../docs/regalloc-spills.md) for coverage. <!-- spill-matrix:start --> -| Test cohort | # tests | Ch 20 | Ch 21 | Ch 22 | Ch 23 | Ch 24 | +| Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | Ch 22: Ops / RA / X | Ch 23: Ops / RA / X | Ch 24: Ops / RA / X | |---|---:|---:|---:|---:|---:|---:| -| Ch 20 | 39 | 360 | 576 | 430 | 442 | 441 | -| Ch 21 | 52 | | 1,072 | 960 | 961 | 948 | -| Ch 22 | 26 | | | 63 | 63 | 63 | -| Ch 23 | 24 | | | | 103 | 103 | -| Ch 24 | 58 | | | | | 1,387 | +| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | 58,736 / 9,084 / 184 | 58,720 / 9,068 / 183 | +| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | 6,324 / 379 / 475 | 6,326 / 381 / 475 | 6,325 / 380 / 470 | +| Ch 22 | 14 / 8 | | | 198 / 60 / 7 | 194 / 56 / 7 | 194 / 56 / 7 | +| Ch 23 | 14 / 8 | | | | 630 / 160 / 36 | 630 / 160 / 36 | +| Ch 24 | 36 / 20 | | | | | 4,923 / 1,341 / 790 | <!-- spill-matrix:end --> diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java index f3bbbbeb..8fc22a67 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java @@ -17,7 +17,7 @@ public class LoadARM extends MemOpARM { super(ld, base, idx, off, 0); } @Override public String op() { return "ld"+_sz; } - @Override public RegMask outregmap() { return size() >= 4 ? arm.MEM_MASK : arm.RMASK; } + @Override public RegMask outregmap() { return size() >= 4 ? arm.MEM_MASK : arm.WMASK; } private static final int[] OP_LOADS = new int[]{ Arm64.OP_LOAD_IMM_8, Arm64.OP_LOAD_IMM_16, Arm64.OP_LOAD_IMM_32, Arm64.OP_LOAD_IMM_64, }; diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java index ac21c706..f8e450f6 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java @@ -18,9 +18,9 @@ public class NotARM extends MachConcreteNode implements MachNode{ // subtracting zero from rs will just yield rs, it sets the zero flag and then it's used in cset short self = enc.reg(this ); short reg1 = enc.reg(in(1)); - int subs = Arm64.imm_inst(Arm64.OP_SUBS, 0, reg1, self); + int subs = Arm64.imm_inst(Arm64.OP_SUBS, 0, reg1, 31); enc.add4(subs); - int cset = Arm64.cond_set(Arm64.OP_CSET, 31, Arm64.COND.EQ, 31, reg1); + int cset = Arm64.cset(Arm64.OP_CSET, 31, Arm64.COND.EQ, 31, self); enc.add4(cset); } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index defec5ef..32c1e2fc 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java @@ -215,7 +215,7 @@ public class arm extends Machine { public static void f_cmp(Encoding enc, Node n) { short reg1 = (short)(enc.reg(n.in(1))-D_OFFSET); short reg2 = (short)(enc.reg(n.in(2))-D_OFFSET); - int body = Arm64.f_cmp(0b00011110, 3, reg1, reg2); + int body = Arm64.f_cmp(0b00011110, 3, reg2, reg1); enc.add4(body); } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java index dbe9ceb0..6f499db1 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java @@ -15,7 +15,8 @@ public class NotRISC extends MachConcreteNode implements MachNode { @Override public void encoding( Encoding enc ) { short dst = enc.reg(this ); short src = enc.reg(in(1)); - enc.add4(RiscV.i_type(RiscV.OP_IMM, dst, 2, src, 1)); + // SEQZ is unsigned: negative nonzero inputs must also produce false. + enc.add4(RiscV.i_type(RiscV.OP_IMM, dst, 3, src, 1)); } @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)); } } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java index 690e2102..9bc86565 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java @@ -7,7 +7,11 @@ import com.seaofnodes.simple.node.Node; public class SetIRISC extends ImmRISC { final boolean _unsigned; // slti vs sltiu public SetIRISC( Node src, int imm12, boolean unsigned ) { - super(src,imm12); + this(src,imm12,unsigned,true); + } + public SetIRISC( Node src, int imm12, boolean unsigned, boolean pop ) { + super(src,imm12,pop); + if( !pop ) _inputs.setLen(2); _unsigned = unsigned; } @Override public String op() { return "slt" + (_unsigned ? "u":"") + "i"; } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java index 78d21f3b..7c994624 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java @@ -305,7 +305,7 @@ public class riscv extends Machine { // x <= y - flip and negate; !(y < x); `slt tmp=y,x; xori dst=tmp,#1` case "<=" -> new XorIRISC(new SetRISC(bool.swap12(), false),1,false); // x == y - sub and vs0 == `sub tmp=x-y; sltu dst=tmp,#1` - case "==" -> new SetIRISC(new SubRISC(bool),1,true); + case "==" -> new SetIRISC(new SubRISC(bool),1,true,false); default -> throw Utils.TODO(); }; } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java index bb89aa16..9a657855 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java @@ -585,17 +585,21 @@ return 0 < arg < arg+1 < 4; """; TestC.run(src, "stacked_r_13x", null, stack12,0); - // Evaluate on RISC5 emulator + // Compile once per target, then check false, true and negative inputs. EvalRisc5 R5 = TestRisc5.build("stacked_r_13", src2, 1, 0, false); - int trap = R5.step(100); - assertEquals(0,trap); - assertEquals(1,R5.regs[riscv.A0]); - - // Evaluate on ARM emulator + for( int arg : new int[]{-1,0,1} ) { + R5._pc = 0; + R5.regs[riscv.A0] = arg; + assertEquals(0,R5.step(100)); + assertEquals(arg==0 ? 1 : 0,R5.regs[riscv.A0]); + } EvalArm64 arm = TestArm64.build("stacked_r_13", src2, 1, 0, false); - trap = arm.step(100); - assertEquals(0,trap); - assertEquals(1,arm.regs[0]); + for( int arg : new int[]{-1,0,1} ) { + arm._pc = 0; + arm.regs[0] = arg; + assertEquals(0,arm.step(100)); + assertEquals(arg==0 ? 1 : 0,arm.regs[0]); + } } @Test diff --git a/chapter25/README.md b/chapter25/README.md index ec8a8ea8..6d2a376b 100644 --- a/chapter25/README.md +++ b/chapter25/README.md @@ -183,21 +183,23 @@ calculation next to the use adds no instruction and avoids preserving a callee-save register merely to hold the constant. Adjacent uses and multi-use addresses retain the area/cost ranking. -Rows are fixed test cohorts; columns are the compiler/allocator chapters. Each -cell is the sum of `_spillScaled`: retained split moves, including register -copies, weighted by loopDepth. Lower is better. **# tests counts -compilations** (program/CPU/ABI cases), including zero-spill cases, rather than -JUnit methods. The count and membership of each row stay fixed across columns. +Rows are fixed test cohorts; columns are compiler chapters. Each cell gives +**Ops / RA / X**: executed ARM+RISC-V instructions, the subset emitted for +allocator copies/rematerializations, and x86's loop-weighted split-move estimate. +**Cases D / X** counts measured dynamic program/target cases and x86 compilations; +membership and inputs stay fixed across columns. Native-library work is excluded. +Chapter 20 has no encoder, hence no dynamic counts. Lower is better within each +metric; see the [measurement details](../docs/regalloc-spills.md) for coverage. <!-- spill-matrix:start --> -| Test cohort | # tests | Ch 20 | Ch 21 | Ch 22 | Ch 23 | Ch 24 | Ch 25 | +| Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | Ch 22: Ops / RA / X | Ch 23: Ops / RA / X | Ch 24: Ops / RA / X | Ch 25: Ops / RA / X | |---|---:|---:|---:|---:|---:|---:|---:| -| Ch 20 | 39 | 360 | 576 | 430 | 442 | 441 | 491 | -| Ch 21 | 52 | | 1,072 | 960 | 961 | 948 | 1,077 | -| Ch 22 | 26 | | | 63 | 63 | 63 | 71 | -| Ch 23 | 24 | | | | 103 | 103 | 152 | -| Ch 24 | 58 | | | | | 1,387 | 1,503 | -| Ch 25 | 14 | | | | | | 1,862 | +| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | 58,736 / 9,084 / 184 | 58,720 / 9,068 / 183 | 59,043 / 9,094 / 209 | +| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | 6,324 / 379 / 475 | 6,326 / 381 / 475 | 6,325 / 380 / 470 | 6,233 / 219 / 533 | +| Ch 22 | 14 / 8 | | | 198 / 60 / 7 | 194 / 56 / 7 | 194 / 56 / 7 | 332 / 136 / 11 | +| Ch 23 | 14 / 8 | | | | 630 / 160 / 36 | 630 / 160 / 36 | 1,106 / 442 / 36 | +| Ch 24 | 36 / 20 | | | | | 4,923 / 1,341 / 790 | 5,044 / 1,470 / 609 | +| Ch 25 | 2 / 12 | | | | | | 20 / 0 / 1,862 | <!-- spill-matrix:end --> diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java index 4fbd6840..53494092 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java @@ -17,7 +17,7 @@ public class LoadARM extends MemOpARM { super(ld, base, idx, off, 0); } @Override public String op() { return "ld"+_sz; } - @Override public RegMask outregmap() { return size() >= 4 ? arm.MEM_MASK : arm.RMASK; } + @Override public RegMask outregmap() { return size() >= 4 ? arm.MEM_MASK : arm.WMASK; } private static final int[] OP_LOADS = new int[]{ Arm64.OP_LOAD_IMM_8, Arm64.OP_LOAD_IMM_16, Arm64.OP_LOAD_IMM_32, Arm64.OP_LOAD_IMM_64, }; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java index ac21c706..f8e450f6 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java @@ -18,9 +18,9 @@ public class NotARM extends MachConcreteNode implements MachNode{ // subtracting zero from rs will just yield rs, it sets the zero flag and then it's used in cset short self = enc.reg(this ); short reg1 = enc.reg(in(1)); - int subs = Arm64.imm_inst(Arm64.OP_SUBS, 0, reg1, self); + int subs = Arm64.imm_inst(Arm64.OP_SUBS, 0, reg1, 31); enc.add4(subs); - int cset = Arm64.cond_set(Arm64.OP_CSET, 31, Arm64.COND.EQ, 31, reg1); + int cset = Arm64.cset(Arm64.OP_CSET, 31, Arm64.COND.EQ, 31, self); enc.add4(cset); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java index dbe9ceb0..6f499db1 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NotRISC.java @@ -15,7 +15,8 @@ public class NotRISC extends MachConcreteNode implements MachNode { @Override public void encoding( Encoding enc ) { short dst = enc.reg(this ); short src = enc.reg(in(1)); - enc.add4(RiscV.i_type(RiscV.OP_IMM, dst, 2, src, 1)); + // SEQZ is unsigned: negative nonzero inputs must also produce false. + enc.add4(RiscV.i_type(RiscV.OP_IMM, dst, 3, src, 1)); } @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)); } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java index 690e2102..9bc86565 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java @@ -7,7 +7,11 @@ import com.seaofnodes.simple.node.Node; public class SetIRISC extends ImmRISC { final boolean _unsigned; // slti vs sltiu public SetIRISC( Node src, int imm12, boolean unsigned ) { - super(src,imm12); + this(src,imm12,unsigned,true); + } + public SetIRISC( Node src, int imm12, boolean unsigned, boolean pop ) { + super(src,imm12,pop); + if( !pop ) _inputs.setLen(2); _unsigned = unsigned; } @Override public String op() { return "slt" + (_unsigned ? "u":"") + "i"; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java index ae69b439..19b91866 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java @@ -317,7 +317,7 @@ public class riscv extends Machine { // x <= y - flip and negate; !(y < x); `slt tmp=y,x; xori dst=tmp,#1` case "<=" -> new XorIRISC(new SetRISC(bool.swap12(), false),1,false); // x == y - sub and vs0 == `sub tmp=x-y; sltu dst=tmp,#1` - case "==" -> new SetIRISC(new SubRISC(bool),1,true); + case "==" -> new SetIRISC(new SubRISC(bool),1,true,false); default -> throw Utils.TODO(); }; } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java index ef65c6d9..3e21c73e 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java @@ -226,19 +226,21 @@ return (10 < something_specific < 20) String src2 = "return 0 == arg == 1;"; TestC.runC(src, "stacked_r_13x", "1",0); - // Evaluate on RISC5 emulator + // Compile once per target, then check false, true and negative inputs. EvalRisc5 R5 = TestRisc5.build( src2, "stacked_r_13", 1, 0, false); - R5.regs[riscv.A1] = 1; // Arg in A1, Test.class in A0 - int trap = R5.step(100); - assertEquals(0,trap); - assertEquals(1,R5.regs[riscv.A0]); - - // Evaluate on ARM emulator + for( int arg : new int[]{-1,0,1} ) { + R5._pc = 0; + R5.regs[riscv.A1] = arg; + assertEquals(0,R5.step(100)); + assertEquals(arg==0 ? 1 : 0,R5.regs[riscv.A0]); + } EvalArm64 arm = TestArm64.build("stacked_r_13", src2, 1, 0, false); - arm.regs[1] = 1; // Arg in r1, Test.class in r0 - trap = arm.step(100); - assertEquals(0,trap); - assertEquals(1,arm.regs[0]); + for( int arg : new int[]{-1,0,1} ) { + arm._pc = 0; + arm.regs[1] = arg; + assertEquals(0,arm.step(100)); + assertEquals(arg==0 ? 1 : 0,arm.regs[0]); + } } @Test diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21AllocTest-testString.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21AllocTest-testString.smp index 586ccb85..a18a5b88 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21AllocTest-testString.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21AllocTest-testString.smp @@ -1,12 +1,12 @@ // -*- mode: java; -*- -struct String { +struct _String { u8[] cs; int _hashCode; - new String = { u8[] data -> cs=data; }; + new _String = { u8[] data -> cs=data; }; }; // Compare two Strings -val equals = { !String !self, !String s -> +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++ ) @@ -16,13 +16,13 @@ val equals = { !String !self, !String s -> }; // Return the String hashCode (cached, and never 0) -val hashCode = { !String self -> +val hashCode = { !_String self -> self._hashCode ? self._hashCode : (self._hashCode = _hashCodeString(self)); }; -val _hashCodeString = { !String self -> +val _hashCodeString = { !_String self -> int hash=0; if( self.cs ) for( int i=0; i< self.cs#; i++ ) @@ -30,3 +30,6 @@ val _hashCodeString = { !String self -> if( !hash ) hash = 123456789; return hash; }; + +// This fixture exports its API, not the last declaration as a result. +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testAntiDeps1.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testAntiDeps1.smp index 950e282d..315cc5b6 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testAntiDeps1.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testAntiDeps1.smp @@ -1,7 +1,7 @@ -struct S { int f; }; -var v0 = new S; -!S? !v1; -if (arg) v1 = new S; +struct _S { int f; }; +var v0 = new _S; +!_S? !v1; +if (arg) v1 = new _S; if (v1) { v0.f = v1.f; } else { diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testInfinite.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testInfinite.smp index 5e517b61..1804ad59 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testInfinite.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testInfinite.smp @@ -1 +1 @@ -struct S { int i; }; !S !s = new S; while(1) s.i++; +struct _S { int i; }; !_S !s = new _S; while(1) s.i++; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testStringExport.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testStringExport.smp index f3d34b0a..ee5a0560 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testStringExport.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testStringExport.smp @@ -28,3 +28,6 @@ val _hashCodeString = { !String self -> if( !hash ) hash = 123456789; return hash; }; + +// This fixture exports its API, not the last declaration as a result. +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23AllocTest-testString.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23AllocTest-testString.smp index 4ef375e9..49c80a99 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23AllocTest-testString.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23AllocTest-testString.smp @@ -1,12 +1,12 @@ // -*- mode: java; -*- -struct String { +struct _String { u8[] cs; int _hashCode; - new String = { u8[] data -> cs=data; }; + new _String = { u8[] data -> cs=data; }; }; // Compare two Strings -val equals = { !String !self, !String s -> +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++ ) @@ -16,16 +16,19 @@ val equals = { !String !self, !String s -> }; // Return the String hashCode (cached, and never 0) -val hashCode = { !String self -> +val hashCode = { !_String self -> self._hashCode ? self._hashCode : (self._hashCode = _hashCodeString(self)); }; -val _hashCodeString = { !String self -> +val _hashCodeString = { !_String self -> int hash=0; for( int i=0; i< self.cs#; i++ ) hash = hash*31 + self.cs[i]; if( !hash ) hash = 123456789; return hash; }; + +// This fixture exports its API, not the last declaration as a result. +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testAndPtr.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testAndPtr.smp index 556a1375..a1e4e9ab 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testAndPtr.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testAndPtr.smp @@ -1,8 +1,8 @@ {i32 i64 u32 -> u32} write="C"; val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; -struct S { !S? !fld; new S={ !S? f -> fld=f; }; }; +struct _S { !_S? !fld; new _S={ !_S? f -> fld=f; }; }; -val ptr = arg == 1 ? null : new S(arg==1 ? null : new S(null)); +val ptr = arg == 1 ? null : new _S(arg==1 ? null : new _S(null)); if( ptr && ptr.fld ) { _p("true"); } else { diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testFRefFields.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testFRefFields.smp index 00fcb589..eac0a542 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testFRefFields.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testFRefFields.smp @@ -1,8 +1,8 @@ // A hypothetical scanner class -struct Scan { +struct _Scan { int !x; u8[~] buf; - new Scan={ u8[~] b -> buf=b; }; + new _Scan={ u8[~] b -> buf=b; }; // Skip whitespace val skip = { -> while( buf[x] <= ' ' ) @@ -16,5 +16,5 @@ struct Scan { return true; }; }; -!Scan !s = new Scan(" q"); +!_Scan !s = new _Scan(" q"); return s.peek('q'); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testFuncCall.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testFuncCall.smp index b522a811..8a7b90d9 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testFuncCall.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testFuncCall.smp @@ -4,11 +4,11 @@ val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; int a = 1; int b = 1; -var sq = { int x -> +var _sq = { int x -> x*x; }; -if(a && sq(0)) { +if(a && _sq(0)) { _p("And"); } else { _p("Or"); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testMethod.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testMethod.smp index 27a19988..ced649e3 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testMethod.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testMethod.smp @@ -1,8 +1,8 @@ // A hypothetical scanner class -struct Scan { +struct _Scan { int !x; u8[~] buf; - new Scan={ u8[~] b -> buf=b; }; + new _Scan={ u8[~] b -> buf=b; }; // Skip whitespace val skip = { -> while( buf[x] <= ' ' ) @@ -13,5 +13,5 @@ struct Scan { buf[x++]==ch; }; }; -!Scan !s = new Scan(" [1,2]"); +!_Scan !s = new _Scan(" [1,2]"); return s.require('['); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOrRhsLoopLocal.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOrRhsLoopLocal.smp index cf6d93ab..c4e4f9b5 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOrRhsLoopLocal.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOrRhsLoopLocal.smp @@ -1,10 +1,10 @@ -struct S { int f; }; +struct _S { int f; }; int x=0; int result=arg&1; if(!result) { - !S !s=new S; + !_S !s=new _S; while(x<3) x++; s.f=++x; - result=!!s.f; + result=s.f; } return x*10+result; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOrRhsLoopMemory.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOrRhsLoopMemory.smp index 370bfb8d..79478408 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOrRhsLoopMemory.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOrRhsLoopMemory.smp @@ -1,11 +1,11 @@ -struct S { int f; }; -!S !s=new S; +struct _S { int f; }; +!_S !s=new _S; int result=arg&1; if(!result) { - !S !t=new S; + !_S !t=new _S; while(s.f<3) s.f++; s.f++; t.f=s.f; - result=!!t.f; + result=t.f; } return s.f*10+result; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testBubbleSort.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testBubbleSort.smp index 7aeeaa35..f292254e 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testBubbleSort.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testBubbleSort.smp @@ -16,22 +16,22 @@ i32 MAP_PRIVATE = 2; i32 MAP_ANON = 32; - val copy = { u8[] dst, int doff, u8[~] src, int soff, int len -> + val _copy = { u8[] dst, int doff, u8[~] src, int soff, int len -> for( int i=0; i<len; i++ ) dst[i+doff] = src[i+soff]; return dst; }; - struct aryu8 { + struct _aryu8 { u32 !len = 0; u8[] !buf; - new aryu8={ u8[] b -> buf=b; }; + new _aryu8={ u8[] b -> buf=b; }; // Grow as needed val _grow = { int len2 -> if( len+len2 < buf# ) return self; int newlen = buf# * 2; while( len+len2 >= newlen ) newlen *= 2; u8[] !buf2 = new u8[newlen]; - copy(buf2,0,buf,0,buf#); + _copy(buf2,0,buf,0,buf#); buf = buf2; self; }; @@ -45,7 +45,7 @@ // Add a plain array to the aryu8 val addAry = { u8[~] ary -> _grow(ary#); - copy(buf,len,ary,0,ary#); + _copy(buf,len,ary,0,ary#); len += ary#; self; }; @@ -75,10 +75,10 @@ // Write to fd, returns the number of bytes written (len). val write = { i32 fd -> i64 ptr = buf; write(fd,ptr,len); }; }; -struct Scan { +struct _Scan { int !x; u8[~] buf; - new Scan={ u8[~] b -> buf=b; }; + new _Scan={ u8[~] b -> buf=b; }; // Skip whitespace val skip = { -> @@ -105,10 +105,10 @@ struct Scan { return neg ? -n : n; }; }; -struct aryi64 { +struct _aryi64 { u32 !len = 0; i64[] !buf; - new aryi64={ i64[] b -> buf=b; }; + new _aryi64={ i64[] b -> buf=b; }; // Grow as needed val _grow = { int len2 -> if( len+len2 < buf# ) return self; @@ -130,17 +130,17 @@ struct aryi64 { // Write to aryu8 val str = { -> // TODO: clunky default constructor syntax - var str = new aryu8(new u8[1]).add('['); + var str = new _aryu8(new u8[1]).add('['); for( int i=0; i<len; i++ ) str.num(buf[i]).add(',').add(' '); str.undo(2).add(']'); }; }; - val parseAryI64 = { u8[~] str -> - !Scan !s = new Scan(str); + val _parseAryI64 = { u8[~] str -> + !_Scan !s = new _Scan(str); if( !s.match('[') ) return null; // Array of parsed results - var nums = new aryi64(new i64[1]); + var nums = new _aryi64(new i64[1]); // Parse a list of numbers if( !s.match(']') ) { // Handle the empty list // Parse "123, " until a something else @@ -156,13 +156,13 @@ struct aryi64 { // Print string to stdout - val p = { u8[~] str -> + val _p = { u8[~] str -> i64 ptr = str; // cast array base to i64 return write(1,ptr,str#); }; // Return stdin as a u8[] - val stdin = { -> + val _stdin = { -> var buf = new u8[8*1024]; i64 ptr = buf; int len = 0; @@ -176,7 +176,7 @@ struct aryi64 { } // Compress var dst = new u8[len]; - return copy(dst,0,buf,0,len); + return _copy(dst,0,buf,0,len); }; // -*- mode: java; -*- @@ -185,7 +185,7 @@ struct aryi64 { // // Bubble sort, with reading (parsing) and writing (formatting) the data. -val sort = { !aryi64 nums -> +val _sort = { !_aryi64 nums -> var done = false; while( !done ) { done = true; @@ -202,14 +202,14 @@ val sort = { !aryi64 nums -> // Read from stdin a line of the form "[ 4, 3, 2, 1]" and print it sorted. val main = { -> // Parse array of numbers from stdin - var nums = parseAryI64( stdin() ); + var nums = _parseAryI64( _stdin() ); if( !nums ) { - p("stdin must look like [4, 3, 2, 1]"); + _p("stdin must look like [4, 3, 2, 1]"); return 1; } // Bubble sort array of integers - sort(nums); + _sort(nums); // Print a list of numbers to stdout nums.str().write(1); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack3.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack3.smp index 6a3db406..4700f8ce 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack3.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack3.smp @@ -1,11 +1,11 @@ {i32 i64 u32 -> u32} write="C"; val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; -var sq = { int x -> +var _sq = { int x -> x*x; }; int score = 5; -val str = (sq(2) <= score < sq(3)) ? "In Range" : "Out of range"; +val str = (_sq(2) <= score < _sq(3)) ? "In Range" : "Out of range"; _p(str); return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack5.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack5.smp index e4660752..3c2c4208 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack5.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack5.smp @@ -1,12 +1,12 @@ {i32 i64 u32 -> u32} write="C"; val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; -var sq = { int x -> +var _sq = { int x -> x*x; }; int score = 5; -if (sq(2) <= score < sq(3)) { +if (_sq(2) <= score < _sq(3)) { _p("In Range"); } else { _p("Out of range"); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/README.md b/chapter25/src/test/java/com/seaofnodes/simple/spill/README.md index 08371ae9..b5ab9d80 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/README.md +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/README.md @@ -35,7 +35,10 @@ Chapter 25 cannot parse all earlier sources unchanged. Adaptations are explicit: sources are a new comparison baseline; their totals cannot be compared as identical inputs with the earlier constructor-free fixtures. - The two short-circuit RHS initializer loops become equivalent guarded blocks, - preserving allocation, side effects, and the final result. + preserving allocation, side effects, and the final result. Their RHS assigns + the field value directly: Simple's `||` returns an operand, not a normalized + boolean. The 2026-10-07 cleanup removes an erroneous `!!` in those adaptations; + both fixtures return 44 for even arguments and 1 for odd arguments. - Simple I/O cases include the old `write` binding and print helper directly. Bubble Sort includes the old library bodies, with namespace prefixes flattened, explicit constructors, and mutable replacement buffers. This retains the old @@ -50,6 +53,14 @@ Chapter 25 cannot parse all earlier sources unchanged. Adaptations are explicit: StringExport, Person and the C-return wrappers, retain their public names. These visibility adaptations change the generated workload and are recorded separately from the allocator improvement in the cross-chapter comparison. +- The remaining visibility cleanup makes local classes/functions private in + AntiDeps1, Infinite, the Chapter 21/23 allocation String cases, the Chapter 23 + scanner/pointer/short-circuit/function cases, and Stack3/Stack5. Bubble Sort's + copied library implementation is private; its `main` stays public. The three + adapted String API fixtures end in `return 0;`, avoiding an accidental return + of the last declared function. Their equality/hash APIs stay public, and the + named StringExport fixture also keeps its public String factory. No cohort + entries, workload operations, or intentional export APIs are removed. - Other source texts are retained. All entries replay **through RegAlloc**, checking scheduled register constraints. diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index fdc4eff4..49288607 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -465,6 +465,19 @@ lines beyond the original extraction. ## Pending corrections +- **Residual allocation comparisons (investigated 2026-10-07; no compiler fix).** + After fixture cleanup, cohort 23 is 103 in Chapter 24 versus 104 in 25; + cohort 24 improves 1,387 to 1,315. The small actionable case is Win64 + NewtonExport: six moves in both chapters, but Chapter 25 puts five in the loop + rather than four (34 to 41 weighted). Inspect destructive-add operand choice, + coalescing and Phi/return-register bias. Bubble Sort + now executes fewer instructions on both ARM and RISC-V; its higher static + weight does not represent more executed allocator instructions. + Ordinary Newton's larger static score mostly counts duplicated inlined loops: + a no-inline diagnostic nearly matches Chapter 24. The + [remaining-differences report](regalloc-spills.md#remaining-differences-after-fixture-cleanup) + separates these findings from the deferred inliner work below. + - **Chapter 25 deterministic inlining (deferred until after the Chapter 25 split).** As of 2026-10-07, ordinary functions reject `_approxUIDs >= 100` before checking the optimized body. `_approxUIDs` counts node IDs consumed during parsing and @@ -609,9 +622,9 @@ which checks matching test/CPU/ABI membership with assertions enabled. | 20 | Basic coloring, rematerialization and loop splitting, with shared legality/progress fixes | 39 | | 21 | Conservative copy coalescing and adjacent-copy forwarding | 39, 52 | | 22 | Stronger copy-chain/backedge bias and cheap-spill ordering | 39, 52, 26 | -| 23 | Group popular single-def uses by compatible register classes | 39, 52, 26, 30 | -| 24 | One cold-only attempt for loop-Phi self-conflicts, then mandatory fallback | 39, 52, 26, 30, 67 | -| 25 | Existing area/cost ranking and later conflict strategies | 39, 52, 26, 30, 67, 14 | +| 23 | Group popular single-def uses by compatible register classes | 39, 52, 26, 24 | +| 24 | One cold-only attempt for loop-Phi self-conflicts, then mandatory fallback | 39, 52, 26, 24, 58 | +| 25 | Existing area/cost ranking and later conflict strategies | 39, 52, 26, 24, 58, 14 | Shared corrections include RegMask/LRG bookkeeping, null use masks, kills without an output LRG, self-conflict splitting, compatible rematerialization, clobber-aware @@ -635,7 +648,8 @@ registers removes that conflict. Encoding must then use the allocated register bank, with five-bit register numbers, for both immediate and indexed loads/stores. The emulator must preserve floating bits and scale double offsets by eight. -Chapter 25 freezes the 214 earlier compilation entries in +Chapter 25 freezes 199 earlier compilation entries, after excluding Jig scratch +tests, in [documented source fixtures](../chapter25/src/test/java/com/seaofnodes/simple/spill/README.md). Constructor/library adaptations change IR, so this is a program-cohort comparison, not identical machine graphs. Those rows replay allocation and legality checks; @@ -677,6 +691,52 @@ The top-level runner accepts explicit chapter lists, e.g. ## Validation record +- **Equality and ARM execution corrections, 2026-10-07.** Chapters 21-25 + retain RISC-V's subtraction when expanding equality and use unsigned SEQZ + for logical-not (including negative inputs), exclude SP/XZR from + narrow ARM load destinations, and encode ARM logical-not with CMP-to-XZR + followed by CSET-to-result. ARM condition inversion is corrected in 21-23; + FCMP operand order in 21-24. Chapter 20 has different selection/stub encoders + and does not contain these faulty expansions. Shared evaluators now use + unsigned SLT/SLTIU comparisons and discard ARM XZR destination writes. + The existing Chapter 24 nested-equality test in 24/25 expected the wrong + result for argument 1; it now checks -1, 0 and 1. Independent ISA checks and full + Make suites pass in 21-25 (including native/system tests). All previously + excluded measurement cases execute successfully; the reporter also checks + nested equality at 0-3. Logs: `build/dynamic-stats/fix-tests{21..25}.log` + and `fix-isa.log`. The expanded matrices and a measured breakdown of the + Chapter 24-to-25 increase are in [the allocation report](regalloc-spills.md). + Cohort 23's +476 Ops is chiefly class-field initialization; its +282 RA + instructions comprise 280 rematerializations and only two extra splits. + +- **Dynamic allocation metrics, 2026-10-07.** Chapter 20-25 README matrices now + report executed ARM/RISC-V instructions, the allocator-created subset (copies, + spills/reloads and rematerializations), and x86-only weighted split estimates. + Dynamic membership and input vectors are fixed per cohort, with results + checked across compilers/targets. Native-library bodies are excluded. Chapter + 20 has no encoder. The dynamic rows cover 22/20/14/14/36/2 program-target + cases; compilation-only/API exclusions are explicit. + The original full allocation cohorts are unchanged. Expanded shared evaluator + support fixes ARM SDIV, ORR-immediate and false CSET values, and RISC-V floating + stores and FEQ/FLT decoding. Independent instruction-word checks pass in + `make -C isa tests`; full Make suites pass in 21-25, including Chapter 25's + native/system groups. Logs: `build/dynamic-stats/tests-{21..25}.log` and + `isa-tests.log`. The reporter validates cohort identities, inputs and results; + generated per-case records are in `build/spill-stats/dynamic-counts.csv`. + +- **Remaining replay fixture cleanup, 2026-10-07.** Fourteen Chapter 25 replay + sources make implementation helpers/classes private while retaining export + APIs, explicitly return zero from three String API fixtures, and correct two + guarded short-circuit adaptations to return their RHS value (not `!!value`). + Disposable Eval2 checks at arguments 0-3 return 44, 1, 44, 1 for both loops. + `make -C chapter25 spill-stats CTAGS=` passes all 199 historical allocations, + fresh library encoding, 23 native tests and spill expectations. Fixed cohort + membership remains unchanged. Cohort 21 changes 1,077 to 1,036; 23 changes + 152 to 104; 24 changes 1,503 to 1,315. Other rows are unchanged. The matrix + reporter validates membership against saved Chapter 20-24 reports and updates + the documentation. No compiler changes or permanent tests were added. + Logs and disposable allocation/assembly probes: `build/fixture-cleanup/`. + - **Ignore debugging Jigs (2026-10-07).** All `testJig*` methods are scratch placeholders, not regression tests. Added missing `@Ignore` annotations in Chapters 14-25, preserving their bodies, and removed all 15 Jig entries and diff --git a/docs/regalloc-spills.md b/docs/regalloc-spills.md index 9b96a30b..4f738fe5 100644 --- a/docs/regalloc-spills.md +++ b/docs/regalloc-spills.md @@ -1,108 +1,142 @@ # Register allocation across chapters -Read a row from left to right to follow a fixed test cohort through successive -compilers. Columns identify the compiler/allocator chapter; each cell is its -sum of `_spillScaled`. Blank cells precede the cohort's introduction. -There is no total across different cohorts. +Read a row left to right to follow a fixed cohort through successive compilers. +Each cell gives **Ops / RA / X**: + +- **Ops:** executed ARM + RISC-V machine instructions, with fixed inputs. +- **RA:** executed instructions belonging to allocator-created copies, + spills/reloads and rematerializations; a subset of Ops. A replacement constant + materialization counts even when it adds no instruction relative to the + original program. This measures allocator-generated code, not a net overhead. +- **X:** x86-only `_spillScaled`, counting retained split moves (including + register copies) with weight `8^loopDepth`. It is a static estimate and does + not count rematerializations. + +**Cases D / X** counts dynamic program/target cases and x86 compilations. +Repeated historical compilation entries remain repeated. These are independent +coverage counts, not a sum; dynamic cases may use several inputs. Membership, +inputs and returned values are checked across compiler columns. Chapter 20 has +no encoder, so its dynamic cells are unavailable. There is no cross-cohort total. <!-- spill-matrix:start --> -| Test cohort | # tests | Ch 20 | Ch 21 | Ch 22 | Ch 23 | Ch 24 | Ch 25 | +| Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | Ch 22: Ops / RA / X | Ch 23: Ops / RA / X | Ch 24: Ops / RA / X | Ch 25: Ops / RA / X | |---|---:|---:|---:|---:|---:|---:|---:| -| Ch 20 | 39 | 360 | 576 | 430 | 442 | 441 | 491 | -| Ch 21 | 52 | | 1,072 | 960 | 961 | 948 | 1,077 | -| Ch 22 | 26 | | | 63 | 63 | 63 | 71 | -| Ch 23 | 24 | | | | 103 | 103 | 152 | -| Ch 24 | 58 | | | | | 1,387 | 1,503 | -| Ch 25 | 14 | | | | | | 1,862 | +| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | 58,736 / 9,084 / 184 | 58,720 / 9,068 / 183 | 59,043 / 9,094 / 209 | +| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | 6,324 / 379 / 475 | 6,326 / 381 / 475 | 6,325 / 380 / 470 | 6,233 / 219 / 533 | +| Ch 22 | 14 / 8 | | | 198 / 60 / 7 | 194 / 56 / 7 | 194 / 56 / 7 | 332 / 136 / 11 | +| Ch 23 | 14 / 8 | | | | 630 / 160 / 36 | 630 / 160 / 36 | 1,106 / 442 / 36 | +| Ch 24 | 36 / 20 | | | | | 4,923 / 1,341 / 790 | 5,044 / 1,470 / 609 | +| Ch 25 | 2 / 12 | | | | | | 20 / 0 / 1,862 | <!-- spill-matrix:end --> -Here **# tests counts compilations**, including the same program on different -CPU/ABI combinations and separately recorded compilation phases. It is not the -number of JUnit methods. Every filled cell in a row uses the same number of -compilations and the same test/CPU/ABI membership, including zero-spill cases. -The reporter checks the multiset of those identities before emitting the table. -Jig methods are temporary debugging placeholders and are always ignored. Their -15 replay entries are excluded consistently: six from cohort 23 and nine from -cohort 24. The two cohort-23 Jigs duplicated one Fibonacci scratch program; -Chapters 23-24 discarded its default main, while 25 compiled it and an exported -function. Its removal eliminates 228 weighted moves from the Chapter 25 column -without changing the compiler. -Chapter 20's BrainFuck and MergeSort tests were moved into Chapter20Test in 21; -the reporter recognizes that rename. - -`_spillScaled` counts retained SplitNodes, including register-to-register moves, -weighted by `8^loopDepth`. Lower is better; these are estimated move costs, -not measured memory traffic or execution time. - -Measured on Windows x86-64, 2026-10-07. The earlier cohorts combine x86-64 -SystemV/Win64 with ARM and RISC-V SystemV, at optimizer seed 123. Cohort 25 -contains 13 recorded native-test allocations at their existing seeds and a -fresh system-library compilation at seed 456. - -The rows compare whole chapter compilers. Optimizations, scheduling, ABI -lowering, and library representation also change, so a row need not decrease -at every step. In particular, Chapter 25 replays earlier programs with the -[documented syntax, constructor and visibility adaptations](../chapter25/src/test/java/com/seaofnodes/simple/spill/README.md). -The two Chapter 22 C-return ABI cases are included there as well, keeping that -row at 26 compilations. They cost no moves in 22-25 after Chapter 25's targeted -function-address rematerialization preference. -Use a controlled comparison within one compiler to isolate an allocator heuristic. - -The Chapter 25 comparison below separates that allocator change from making -local helpers/classes private in eleven replay fixtures. The ranking trial uses -the same sources, seeds, targets and ABIs as its baseline. Private names remove -unneeded exported bodies and allocation factories; their effect is a change to -the lowered program, not an allocator gain. Export/API fixtures stay public. - -| Test cohort | Before | Ranking only | + Private helpers | + Tiny-body check | -|---|---:|---:|---:|---:| -| Ch 20 | 608 | 608 | 491 | 491 | -| Ch 21 | 1,170 | 1,170 | 1,077 | 1,077 | -| Ch 22 | 127 | 99 | 71 | 71 | -| Ch 23 | 152 | 152 | 152 | 152 | -| Ch 24 | 1,558 | 1,545 | 1,506 | 1,503 | -| Ch 25 | 1,851 | 1,829 | 1,829 | 1,862 | - -These four successful Chapter 25 reports have been recomputed from their saved -per-allocation records with the Jig entries excluded, leaving 199 replay -allocations. They also passed fresh library encoding and 23 native/system tests. -The final compiler also passes its complete -Make suite and a fresh SystemV library encoding on Windows. The earlier compiler -columns are unchanged. - -The tiny-body check bypasses an oversized parse-time estimate only for recognized -straight-line boilerplate containing at most 15 nodes. Parsing an initializer -also builds its nested methods, so that estimate can greatly exceed the surviving -body. Dependencies on Return inputs and the bounded inspected prefix allow retries -after folding, without walking a large body on every change. The walk follows uses -from entry to Return, with bounded fanout, avoiding sparse memory input arrays. -This removes six constructor calls in the replay corpus, all in Bubble Sort: -estimates 276, 352 and 479 represented bodies of only 11, 11 and 14 nodes. Public -constructor bodies remain exported. The optimized-body limits remain 100 for -ordinary functions and 200 for `<new>`/instance `<init>`; selection order is unchanged. -It reproduces all 213 retained allocation records from the preceding 1,000-node constructor -parse-allowance trial, replacing that allowance with a bounded structural check. - -This is a boilerplate reduction, not a uniform spill improvement. Bubble Sort's -weighted moves change by -10 on x86, +3 on ARM and +4 on RISC-V. The fresh Win64 -library improves 842 to 809 and Dijkstra 584 to 582, while FileIO rises 293 to 361. -The separately checked SystemV library improves 803 to 777. The broader inliner -redesign is deferred until after the Chapter 25 split. - -Chapters 20-24 also recognize these tiny bodies, copying only straight-line -stores and memory merges after ordinary peepholes settle. They already expand -constructor defaults directly, so there are no analogous constructor calls to -remove. Rerunning their full suites and allocation reports after this backport -changed no raw or scaled allocation record; the matrix above remains unchanged. - -Run `make spill-stats` from the repository root to rerun all six chapters and -write logs plus `matrix.md` under `build/spill-stats/`. A failed test or changed -cohort membership makes the command fail; partial results are not published. -To refresh these tables after a successful run: +Measured on Windows, 2026-10-07, using optimizer seed 123 for the historical +cohorts. The x86 Chapter 25 cohort retains its native-test seeds and the fresh +system-library compilation at seed 456. Dynamic counts include generated class +initializers and calls, but exclude the bodies of native `calloc`, `read` and +`write`. Their deterministic emulator stubs provide allocation and fixed I/O. +No clock timings, native-library instruction counts or code-size metric are mixed in. + +## Inputs and coverage + +| Cohort | Dynamic cases | Executions per compiler | x86 compilations | +|---|---:|---:|---:| +| Ch 20 | 22 | 44 | 13 | +| Ch 21 | 20 | 20 | 18 | +| Ch 22 | 14 | 14 | 8 | +| Ch 23 | 14 | 26 | 8 | +| Ch 24 | 36 | 48 | 20 | +| Ch 25 | 2 | 2 | 12 | + +Newton, array-fill and Merge Sort use argument 16; allocation-index tests use +0, 1 and 2. Branch/short-circuit and nested-equality cases use 0-3, Fibonacci uses 9, and Sieve uses +100. Bubble Sort reads `[4, 3, 2, 1]`; BrainFuck runs its embedded Hello World +program. Other measured cases use argument 0. The Chapter 25 dynamic row is only +the two existing external-data emulator cases, with `counter` initialized to -7; +it does not represent execution of the whole system library or native suite. + +String/Person APIs, the returned mixed-argument function, exported Merge Sort +and BrainFuck, and mixed/stack-argument API tests still need explicit emulator +drivers. Deliberately infinite programs remain compilation-only. The original +allocation cohorts are preserved; these cases are not silently measured as zero. +The previously excluded equality, ARM Newton and ARM Bubble Sort cases now run +in every applicable compiler column. The measurement harness checks their +answers, including nested equality at arguments 0-3, finite Newton results and +Bubble Sort's complete output. The shared ISA tests and full Chapter 21-25 +Make suites pass after the backend/evaluator corrections. + +## Remaining differences after fixture cleanup + +The Chapter 24-to-25 comparison, using the same inputs and cases in each row: + +| Cohort | Ch 24 Ops | Ch 25 Ops | Change | +|---|---:|---:|---:| +| Ch 20 | 58,720 | 59,043 | +0.6% | +| Ch 21 | 6,325 | 6,233 | -1.5% | +| Ch 22 | 194 | 332 | +71.1% | +| Ch 23 | 630 | 1,106 | +75.6% | +| Ch 24 | 4,923 | 5,044 | +2.5% | + +Chapter 25 retains top-level bindings in the compilation unit's class object. +Initializing its fields generates stores, function-pointer constants and class +addresses, even when helper calls have already inlined and folded. Chapters +through 24 can eliminate these bindings as locals. Small programs make this +fixed initialization cost particularly visible. + +For example, `Chapter23Test.testAnd` takes 12 instructions per target in 24 and +32 in 25. The extra 20 are four field stores, four instructions materializing +two function pointers, ten materializing the class address at five uses +(including the hidden call argument), and two integer constants. The actual +short-circuit expression has already folded in both chapters. + +Across the entire Chapter 23 cohort, executed-node attribution accounts for +the **476** extra instructions: + +| Generated work | Instruction change | +|---|---:| +| Field stores | +126 | +| Function-pointer materialization | +108 | +| Pointer-address materialization | +240 | +| Integer constants | +50 | +| Allocator copies/spills/reloads | +2 | +| Unconditional jumps | +2 | +| Calls, prologues/returns, extensions and loads removed | -52 | + +Its RA subset rises **160 to 442**, comprising **224** extra pointer-address +rematerialization instructions, **56** extra integer rematerializations and +only **2** extra copies/spills/reloads. RA labels allocator-created code; it +does not mean all 282 extra instructions are stack traffic. `testAndPtr` also +loses a helper call per execution, so inlining has improved despite the larger +whole-program count. Moving constant initialization to static data would +remove much of this work; reusing class addresses could reduce the repeated +materialization. Neither optimization is included in this measurement update. + +Both Bubble Sort targets improve: RISC-V **2,062 / 591 to 1,877 / 493**, and +ARM **2,040 / 579 to 1,868 / 478** (Ops / RA). Together they save 357 instructions; +the other Chapter 24 cases add 478, leaving a net increase of 121. Newton +integer improves **136 / 36 to 116 / 17** across both targets. In the Chapter 20 +BrainFuck case, ARM adds 95 instructions: 88 net extra integer materializations +plus seven initialization instructions; its executed split count stays at 33. +These tables compare whole chapter compilers, including frontend and inlining +changes, rather than isolating allocator rankings. + +## Reproduce + +Run `make spill-stats` at the repository root to compile/run the static cohorts, +capture their historical sources, execute the dynamic cases and validate the +comparison. Capture uses temporary instrumented copies of the existing +SpillStats listeners under `build/dynamic-stats`; it does not edit chapter code. +The measured machine graph is stopped before allocation to identify subsequently +inserted copies/cloned constants. After encoding, their instruction ranges are +matched against the emulator's executed PCs, including multi-instruction expansions. + +After a successful run, update the marked tables with: ```sh python build-support/spill-matrix.py --reuse --update-docs ``` -Each Chapter 20-25 README contains the matrix up to that chapter. The per-chapter -`make spill-stats` commands still provide individual allocations and CPU/ABI sums. +Per-program inputs, results and dynamic counts are written to +`build/spill-stats/dynamic-counts.csv`; emulator logs and explicit skips live +under `build/dynamic-stats/{21..25}/dynamic.log`. The x86 records remain in +`build/spill-stats/spill-matrix-{20..25}.log`. The source adaptations for Chapter +25 are documented in the [replay README](../chapter25/src/test/java/com/seaofnodes/simple/spill/README.md). diff --git a/isa/src/test-support/java/com/seaofnodes/isa/eval/EvalArm64.java b/isa/src/test-support/java/com/seaofnodes/isa/eval/EvalArm64.java index 2fa4aec1..1ff77f59 100644 --- a/isa/src/test-support/java/com/seaofnodes/isa/eval/EvalArm64.java +++ b/isa/src/test-support/java/com/seaofnodes/isa/eval/EvalArm64.java @@ -329,6 +329,11 @@ public class EvalArm64 { rval = regs[rn] & immediate; break; } + case 0xB2: { // ORR (immediate) + int rn = (ir >>> 5) & 31; + rval = (rn==31 ? 0 : regs[rn]) | Arm64.decodeImm12((ir >>> 10) & 0x1FFF); + break; + } case 0x93, 0xD3: { // SBFM/UBFM: shifts and signed/unsigned extracts int immr = (ir >>> 16) & 63; int imms = (ir >>> 10) & 63; @@ -372,6 +377,12 @@ public class EvalArm64 { } case 0x9A: { + if( (ir & 0xFFE0FC00)==0x9AC00C00 ) { // SDIV Xd,Xn,Xm + int rn=(ir >>> 5)&31, rm=(ir >>> 16)&31; + long lhs=rn==31 ? 0 : regs[rn], rhs=rm==31 ? 0 : regs[rm]; + rval = rhs==0 ? 0 : lhs/rhs; + break; + } int encodedCond = (ir >> 12) & 0xF; int decodedCond = encodedCond ^ 1; // conditional select(csel) @@ -394,7 +405,7 @@ public class EvalArm64 { case 0xF -> false ; // never default -> throw new UnsupportedOperationException(); }; - if( cond ) rval = 1; + rval = cond ? 1 : 0; break; } case 0x9B: { // mul @@ -761,7 +772,8 @@ public class EvalArm64 { } if(rdid != -1) { if(is_f) fregs[rdid] = frval; - else regs[rdid] = rval; + // Register 31 is XZR except for ADD/SUB immediate, which writes SP. + else if( rdid!=31 || opcode1==0x91 || opcode1==0xD1 ) regs[rdid] = rval; } pc += 4; diff --git a/isa/src/test-support/java/com/seaofnodes/isa/eval/EvalRisc5.java b/isa/src/test-support/java/com/seaofnodes/isa/eval/EvalRisc5.java index 46baf447..e6860ccd 100644 --- a/isa/src/test-support/java/com/seaofnodes/isa/eval/EvalRisc5.java +++ b/isa/src/test-support/java/com/seaofnodes/isa/eval/EvalRisc5.java @@ -203,6 +203,17 @@ public class EvalRisc5 { break; } + case 0x27: { // FSW/FSD + int rs1=(int)regs[(ir >>> 15)&31], rs2=(ir >>> 20)&31; + int addr=rs1+((ir >> 25)<<5)+((ir >>> 7)&31); + switch((ir >>> 12)&7) { + case 2: st4(addr,Float.floatToRawIntBits((float)fregs[rs2])); break; + case 3: st8(addr,Double.doubleToRawLongBits(fregs[rs2])); break; + default: trap=3; + } + rdid=0; + break; + } case 0x23: { // Store 0b0100011 int rs1 = (int)regs[(ir >> 15) & 0x1f]; // Address chop to 32b long rs2 = regs[(ir >> 20) & 0x1f]; @@ -252,7 +263,7 @@ public class EvalRisc5 { case 0 -> (is_reg && (ir & 0x40000000) != 0) ? (rs1 - rs2) : (rs1 + rs2); case 1 -> rs1 << (rs2 & 0x3F); case 2 -> (rs1 < rs2) ? 1 : 0; - case 3 -> (rs1 < rs2) ? 1 : 0; + case 3 -> Long.compareUnsigned(rs1,rs2)<0 ? 1 : 0; case 4 -> rs1 ^ rs2; case 5 -> (ir & 0x40000000) != 0 ? (rs1 >> (rs2 & 0x3F)) : (rs1 >>> (rs2 & 0x3F)); case 6 -> rs1 | rs2; @@ -329,8 +340,8 @@ public class EvalRisc5 { is_f = false; // Output into a GPR rval = switch( (ir >> 12) & 7 ) { case 0 -> lhs <= rhs ? 1 : 0; - case 1 -> lhs == rhs ? 1 : 0; - case 2 -> lhs < rhs ? 1 : 0; + case 1 -> lhs < rhs ? 1 : 0; + case 2 -> lhs == rhs ? 1 : 0; default -> throw new UnsupportedOperationException(); }; break; diff --git a/isa/src/test/java/com/seaofnodes/isa/RiscTest.java b/isa/src/test/java/com/seaofnodes/isa/RiscTest.java index 0cef8531..d10f97a4 100644 --- a/isa/src/test/java/com/seaofnodes/isa/RiscTest.java +++ b/isa/src/test/java/com/seaofnodes/isa/RiscTest.java @@ -9,6 +9,47 @@ public class RiscTest { assert expected==actual : String.format("Expected %08x, got %08x",expected,actual); } public static void main(String[] args) { + // Instructions encountered by dynamic allocation measurements. + for( long[] pair : new long[][]{{17,3},{-17,3},{17,0},{Long.MIN_VALUE,-1}} ) { + var a=new EvalArm64(new byte[1024],512); + a.st4(4,0x9AC20C20); // sdiv x0,x1,x2 + a._pc=4;a.regs[1]=pair[0];a.regs[2]=pair[1]; + assert a.step(1)==0; + assert a.regs[0]==(pair[1]==0 ? 0 : pair[0]/pair[1]); + } + var discard=new EvalArm64(new byte[1024],512); + discard.st4(4,0x3862683F); // ldrb wzr,[x1,x2]; discard without changing SP + discard._pc=4;discard.regs[1]=100;discard.regs[2]=4;discard.st1(104,91); + assert discard.step(1)==0 && discard.regs[31]==512; + for(long value:new long[]{-1,0,1,Long.MIN_VALUE}) { + var unsigned=new EvalRisc5(new byte[1024],512); + unsigned.st4(4,0x00113193); // sltiu x3,x2,1 (seqz) + unsigned._pc=4;unsigned.regs[2]=value; + assert unsigned.step(1)==0; + assert unsigned.regs[3]==(value==0 ? 1 : 0); + } + var logical=new EvalArm64(new byte[1024],512); + logical.st4(4,0xB27F0020); // orr x0,x1,#2 + logical.st4(8,0x9A9F17E2); // cset x2,eq; false must not retain prior result + logical._pc=4;logical.regs[1]=8; + assert logical.step(2)==0; + assert logical.regs[0]==10 && logical.regs[2]==0; + for(double rhs:new double[]{1,2,3,Double.NaN}) { + var r=new EvalRisc5(new byte[1024],512); + r.st4(4,0xA220A1D3); // feq.d x3,f1,f2 + r.st4(8,0xA2209253); // flt.d x4,f1,f2 + r._pc=4;r.fregs[1]=2;r.fregs[2]=rhs; + assert r.step(2)==0; + assert r.regs[3]==(2==rhs ? 1 : 0); + assert r.regs[4]==(2<rhs ? 1 : 0); + } + var store=new EvalRisc5(new byte[1024],512); + store.st4(4,0x00113827); // fsd f1,16(sp) + store.st4(8,0xFE112E27); // fsw f1,-4(sp) + store._pc=4;store.fregs[1]=-3.25; + assert store.step(2)==0; + assert store.ld8(528)==Double.doubleToRawLongBits(-3.25); + assert store.ld4s(508)==Float.floatToRawIntBits(-3.25f); word(0x9E780020,Arm64.floatToInteger(1,0)); // FCVTZS x0,d1 for( double value : new double[]{0.0,-0.0,6.92,-6.92,0.99,-0.99, 0x1p63,Math.nextDown(0x1p63),-0x1p63,Math.nextDown(-0x1p63), diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index 2fd52938..36c5ee56 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -37,6 +37,12 @@ For shared viewer work, read [the graph viewer notes](graph-viewer-codex-notes.m They must not become benchmarks or regression tests just because their current contents compile. Cohorts 23/24 now contain 24/58 allocations (199 total replay entries), after removing all 15 frozen Jig entries. +- Historical replay adaptations must preserve operand-valued short-circuit + expressions: replacing a `||` RHS with `!!rhs` changes its result. Compare + actual results as well as allocation legality when rewriting these fixtures. + Static `_spillScaled` also counts each inlined loop copy separately, without + credit for eliminated calls; inspect the optimized call graph before calling + a higher cross-chapter score an allocator regression. - Prefer concrete ArrayList to List, common base classes to unnecessary interfaces, and short names (`pred`, `proj`, `def`, `use`). Avoid redundant Objects.requireNonNull. Prefer int[]/AryInt to List<Integer>; avoid large boxed @@ -877,3 +883,15 @@ Cliff removed the frozen Chapter 18 fixture, replay tests, related reductions, and seed-list entry on 2026-09-27 as unnecessary test overhead. Retain the evaluator fixes; do not recreate that test suite. Do not describe timeout-skipped comparisons as equal runtime results. + +- Dynamic ARM/RISC counts must validate results, not just termination. RISC + equality expands to SUB then unsigned SLTIU; the second node must consume + the SUB, not copy its inputs. ARM register 31 is XZR for load destinations, + so narrow loads use WMASK, never RMASK. Logical-not uses CMP to XZR followed + by CSET to its result register. Shared emulator fixes and Chapter 21-25 + backports are recorded in `docs/chapter-backports.md`. +- Cohort 23's dynamic increase from compiler 24 to 25 is primarily class-field + initialization: Ops 630->1106. RA 160->442 includes 224 extra pointer-address + and 56 integer rematerialization instructions, but only two extra splits. + Do not call that 282 additional spills. ARM and RISC Bubble Sort both improve + when executed. The measured breakdown lives in `docs/regalloc-spills.md`. |