diff options
Diffstat (limited to 'build-support')
| -rw-r--r-- | build-support/AllocMetrics.java.in | 177 | ||||
| -rw-r--r-- | build-support/capture-alloc-sources.py | 28 | ||||
| -rw-r--r-- | build-support/chapter-release.mk | 7 | ||||
| -rw-r--r-- | build-support/early-chapter.mk | 51 | ||||
| -rw-r--r-- | build-support/measure-alloc.py | 45 | ||||
| -rw-r--r-- | build-support/spill-matrix.py | 181 |
6 files changed, 489 insertions, 0 deletions
diff --git a/build-support/AllocMetrics.java.in b/build-support/AllocMetrics.java.in new file mode 100644 index 00000000..f9ee7772 --- /dev/null +++ b/build-support/AllocMetrics.java.in @@ -0,0 +1,177 @@ +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(); + EXTERNFUNCTIONS + 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/chapter-release.mk b/build-support/chapter-release.mk new file mode 100644 index 00000000..74e216f4 --- /dev/null +++ b/build-support/chapter-release.mk @@ -0,0 +1,7 @@ +# Jar packaging for chapters predating the existing release target. +.PHONY: release +release: build/release/simple.jar + +build/release/simple.jar: $(main_classes) $(test_classes) + @mkdir -p build/release + jar cf $@ -C $(CLZDIR)/main . -C $(CLZDIR)/test . diff --git a/build-support/early-chapter.mk b/build-support/early-chapter.mk new file mode 100644 index 00000000..d0135b74 --- /dev/null +++ b/build-support/early-chapter.mk @@ -0,0 +1,51 @@ +# Chapters 1-3 and 5 previously only had Maven builds. +# Included with the chapter as the working directory. +SHELL := /bin/bash +.DEFAULT_GOAL := tests +.DELETE_ON_ERROR: +SIMPLE := com/seaofnodes/simple +SRC := src/main/java +TST := src/test/java +CLZDIR := build/classes +SEP := $(if $(filter Windows_NT,$(OS)),;,:) +CTAGS ?= ctags +JAVAC_ARGS ?= -g +main_javas := $(wildcard $(SRC)/$(SIMPLE)/*.java $(SRC)/$(SIMPLE)/*/*.java) +test_javas := $(wildcard $(TST)/$(SIMPLE)/*.java $(TST)/$(SIMPLE)/*/*.java) +test_cp := $(patsubst $(TST)/$(SIMPLE)/%.java,com.seaofnodes.simple.%,$(wildcard $(TST)/$(SIMPLE)/*Test.java)) +jars := lib/junit-4.12.jar$(SEP)lib/hamcrest-core-1.3.jar +main_classes := $(CLZDIR)/main/.mtag +test_classes := $(CLZDIR)/test/.ttag + +include $(firstword $(wildcard ../graph/graph.mk graph/graph.mk)) +include $(firstword $(wildcard ../print/print.mk print/print.mk)) + +.PHONY: build +build: $(main_classes) + +$(main_classes): $(main_javas) + @mkdir -p $(CLZDIR)/main + javac $(JAVAC_ARGS) -d $(CLZDIR)/main $(main_javas) + @touch $@ + +$(test_classes): $(test_javas) $(main_classes) lib/junit-4.12.jar lib/hamcrest-core-1.3.jar + @mkdir -p $(CLZDIR)/test + javac $(JAVAC_ARGS) -cp "$(CLZDIR)/main$(SEP)$(jars)" -d $(CLZDIR)/test $(test_javas) + @touch $@ + +.PHONY: tests tags lib +tests: $(test_classes) + java -ea -cp "$(CLZDIR)/main$(SEP)$(CLZDIR)/test$(SEP)$(jars)" org.junit.runner.JUnitCore $(test_cp) + +tags: + $(CTAGS) -e --recurse=yes --fields=+fksaiS $(SRC) $(TST) + +lib: lib/junit-4.12.jar lib/hamcrest-core-1.3.jar +lib/junit-4.12.jar: + @mkdir -p lib + wget -O $@ https://repo1.maven.org/maven2/junit/junit/4.12/junit-4.12.jar +lib/hamcrest-core-1.3.jar: + @mkdir -p lib + wget -O $@ https://repo1.maven.org/maven2/org/hamcrest/hamcrest-core/1.3/hamcrest-core-1.3.jar + +include $(firstword $(wildcard ../build-support/chapter-release.mk build-support/chapter-release.mk)) diff --git a/build-support/measure-alloc.py b/build-support/measure-alloc.py new file mode 100644 index 00000000..ed899713 --- /dev/null +++ b/build-support/measure-alloc.py @@ -0,0 +1,45 @@ +"""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)', + 'EXTERNFUNCTIONS':'''var functionField=CodeGen.class.getDeclaredField("_externFunc");functionField.setAccessible(true); + @SuppressWarnings("unchecked") var functionNames=(Map<Integer,String>)functionField.get(c); + for(String name:functionNames.values()) + c._encoding._externalAddresses.put(name,name.equals("calloc")?-4:name.equals("write")?-8:name.equals("read")?-12:-16);''' if ch==25 else '', + '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 new file mode 100644 index 00000000..9ee8f7eb --- /dev/null +++ b/build-support/spill-matrix.py @@ -0,0 +1,181 @@ +#!/usr/bin/env python3 +"""Measure fixed cohorts: dynamic ARM/RISC-V ops, allocator ops, and x86 estimates.""" +import argparse +from collections import Counter, defaultdict +from pathlib import Path +import re +import subprocess +import sys + +ROOT = Path(__file__).resolve().parent.parent +CHAPTERS = range(20, 26) +START = "<!-- spill-matrix:start -->" +END = "<!-- spill-matrix:end -->" + + +def read_log(path): + data = path.read_bytes() + return data.decode("utf-16" if data.startswith((b"\xff\xfe", b"\xfe\xff")) else "utf-8") + + +def read_results(log_dir): + results = {} + for chapter in CHAPTERS: + path = log_dir / f"spill-matrix-{chapter}.log" + text = read_log(path) + if re.search(r"FAILED|(?:[Ff]ailures|Spill golden failures): [1-9]", text): + raise ValueError(f"Chapter {chapter} failed; see {path}") + if not re.search(r"(?:Tests:|Historical allocations:).*failures: 0", text): + raise ValueError(f"Chapter {chapter} has no successful completion record") + cohorts = defaultdict(list) + sums = {} + for line in text.splitlines(): + if line.startswith("allocation,"): + _, cohort, test, cpu, abi, moves, scaled = line.split(",") + cohort = int(cohort.removeprefix("Chapter")) + # These two Chapter 20 programs moved into Chapter20Test in 21. + if cohort == 20 and test in ("BrainFuckTest.testBrainfuck", "MergeSortTest.testMergeSort"): + test = "Chapter20Test." + test.split(".")[1] + abi = "win64" if abi.lower() == "win64" else abi + cohorts[cohort].append((test, cpu, abi, int(moves), int(scaled))) + elif re.match(r"Chapter\d+,ALL,ALL,", line): + cohort, _, _, count, moves, scaled = line.split(",") + sums[int(cohort.removeprefix("Chapter"))] = (int(count), int(moves), int(scaled)) + expected = set(range(20, chapter + 1)) + if set(cohorts) != expected or set(sums) != expected: + raise ValueError(f"Chapter {chapter}: missing or unexpected cohorts") + for cohort, rows in cohorts.items(): + measured = (len(rows), sum(r[3] for r in rows), sum(r[4] for r in rows)) + if measured != sums[cohort]: + raise ValueError(f"Chapter {chapter}, cohort {cohort}: inconsistent report totals") + results[chapter] = cohorts + # A count alone can hide a missing case replaced by a different one. + for cohort in CHAPTERS: + baseline = Counter(r[:3] for r in results[cohort][cohort]) + for chapter in range(cohort + 1, 26): + actual = Counter(r[:3] for r in results[chapter][cohort]) + if actual != baseline: + raise ValueError(f"Chapter {chapter}, cohort {cohort}: membership differs\n" + f" missing: {baseline - actual}\n extra: {actual - baseline}") + return results + + +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 | Cases D / X | " + " | ".join(f"Ch {c}: Ops / RA / X" for c in chapters) + " |", + "|---|---:|" + "---:|" * len(chapters)] + for cohort 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) + + +def update_doc(path, matrix): + text = path.read_text(encoding="utf-8") + if text.count(START) != 1 or text.count(END) != 1: + raise ValueError(f"Missing or duplicate matrix markers in {path}") + before, rest = text.split(START) + _, after = rest.split(END) + path.write_text(before + START + "\n" + matrix + "\n" + END + after, + encoding="utf-8", newline="\n") + + +def main(): + parser = argparse.ArgumentParser(description=__doc__) + parser.add_argument("--log-dir", type=Path, default=ROOT / "build/spill-stats") + parser.add_argument("--reuse", action="store_true", help="read completed logs without rerunning tests") + parser.add_argument("--update-docs", action="store_true", help="refresh the marked tables in docs and READMEs") + args = parser.parse_args() + args.log_dir.mkdir(parents=True, exist_ok=True) + if not args.reuse: + for chapter in CHAPTERS: + path = args.log_dir / f"spill-matrix-{chapter}.log" + print(f"Measuring chapter {chapter}: {path}", flush=True) + with path.open("wb") as log: + run = subprocess.run(["make", "-C", str(ROOT / f"chapter{chapter}"), "spill-stats"], + 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) + 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, dynamic, c)) for c in CHAPTERS] + # Validate all destinations before changing any document. + for path, _ in paths: + text = path.read_text(encoding="utf-8") + if text.count(START) != 1 or text.count(END) != 1: + raise ValueError(f"Missing or duplicate matrix markers in {path}") + for path, value in paths: + update_doc(path, value) + print(matrix) + + +if __name__ == "__main__": + try: + main() + except (ValueError, OSError) as error: + sys.exit(str(error)) |