From 87a75c83b75480e65147a4d425fddd14a05df4d9 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Wed, 7 Oct 2026 21:31:18 -0700 Subject: 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 --- build-support/AllocMetrics.java.in | 176 +++++++++++++++++++++++++++++++++ build-support/capture-alloc-sources.py | 28 ++++++ build-support/measure-alloc.py | 41 ++++++++ build-support/spill-matrix.py | 75 ++++++++++++-- 4 files changed, 313 insertions(+), 7 deletions(-) create mode 100644 build-support/AllocMetrics.java.in create mode 100644 build-support/capture-alloc-sources.py create mode 100644 build-support/measure-alloc.py (limited to 'build-support') 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 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)externalField.get(c._encoding); + var extra=new LinkedHashMap(); + 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>(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"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 before=Collections.newSetFromMap(new IdentityHashMap<>()); + for(var bb:c._cfg){before.add(bb);for(Node n:bb._outputs)before.add(n);} + c.regAlloc(); + Set 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.":"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(); + 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") -- cgit v1.2.3