diff options
21 files changed, 86 insertions, 47 deletions
diff --git a/.dir-locals.el b/.dir-locals.el index 1a9cb5e1..74fde018 100644 --- a/.dir-locals.el +++ b/.dir-locals.el @@ -2,5 +2,5 @@ ;;; For more information see (info "(emacs) Directory Variables") ( (dired-mode . ((c-basic-offset . 4))) - (java-mode . ((c-basic-offset . 4) (eval . (set-buffer-file-coding-system 'unix))) ) + (java-mode . ((c-basic-offset . 4))) ) diff --git a/.emacs/simple-mode.el b/.emacs/simple-mode.el new file mode 100644 index 00000000..47800806 --- /dev/null +++ b/.emacs/simple-mode.el @@ -0,0 +1,38 @@ +;;; simple-mode.el --- Major mode for Simple source files -*- lexical-binding: t; -*- + +(require 'cc-mode) + +(defconst simple-mode-primitive-types + '("int" "i8" "i16" "i32" "i64" "u8" "u16" "u32" "u64" + "byte" "bool" "flt" "f32" "f64" "val" "var") + "Primitive and built-in type names in Simple.") + +(defconst simple-mode-font-lock-keywords + `((,(regexp-opt simple-mode-primitive-types 'symbols) . font-lock-type-face) + (,(regexp-opt '("boolean" "long" "short" "char" "float" "double" "void") 'symbols) (0 nil t)) + ("\\_<new\\_>\\s-+\\(?:[[:alpha:]_][[:alnum:]_$]*\\.\\)*\\([[:alpha:]_][[:alnum:]_$]*\\)" (1 nil t))) + "Additional Simple keywords using Java's type face.") + +(defun simple-mode-set-indentation () + (setq-local c-basic-offset 4) + (setq-local indent-tabs-mode nil)) + +(define-derived-mode simple-mode java-mode "Simple" + "Major mode for Simple .smp source files." + (simple-mode-set-indentation) + (setq-local c-primitive-type-key + (concat "\\(" (regexp-opt simple-mode-primitive-types) "\\)" + "\\([^[:alnum:]_$]\\|$\\)")) + (setq-local font-lock-defaults + `((,@java-font-lock-keywords ,@simple-mode-font-lock-keywords) + nil nil ((?_ . "w") (?$ . "w")) + c-beginning-of-syntax + (font-lock-mark-block-function . c-mark-function))) + (setq-local font-lock-keywords nil) + (font-lock-set-defaults) + (font-lock-mode 1)) + +(add-hook 'simple-mode-hook #'simple-mode-set-indentation) + +(provide 'simple-mode) +;;; simple-mode.el ends here diff --git a/chapter25/docs/examples/A_helloWorld.smp b/chapter25/docs/examples/A_helloWorld.smp index ac399661..4ed6abdf 100644 --- a/chapter25/docs/examples/A_helloWorld.smp +++ b/chapter25/docs/examples/A_helloWorld.smp @@ -1,3 +1,2 @@ -// -*- mode: java; -*- sys.io.p("Hello, World!\n"); return 0; diff --git a/chapter25/docs/examples/BubbleSort.smp b/chapter25/docs/examples/BubbleSort.smp index 7327e461..ef92c29e 100644 --- a/chapter25/docs/examples/BubbleSort.smp +++ b/chapter25/docs/examples/BubbleSort.smp @@ -1,4 +1,3 @@ -// -*- mode: java; -*- // An implementation of // https://sampleprograms.io/projects/bubble-sort/ diff --git a/chapter25/docs/examples/Capitalize.smp b/chapter25/docs/examples/Capitalize.smp index 72b5df70..8e31c18f 100644 --- a/chapter25/docs/examples/Capitalize.smp +++ b/chapter25/docs/examples/Capitalize.smp @@ -1,4 +1,3 @@ -// -*- mode: java; -*- // An implementation of // https://sampleprograms.io/projects/capitalize/ diff --git a/chapter25/docs/examples/Dijkstra.smp b/chapter25/docs/examples/Dijkstra.smp index 57e1fad4..d2f1dc4f 100644 --- a/chapter25/docs/examples/Dijkstra.smp +++ b/chapter25/docs/examples/Dijkstra.smp @@ -1,4 +1,3 @@ -// -*- mode: java; -*- // An implementation of // https://sampleprograms.io/projects/dijkstra/ diff --git a/chapter25/docs/examples/FileIO.smp b/chapter25/docs/examples/FileIO.smp index 29f037bd..6966755a 100644 --- a/chapter25/docs/examples/FileIO.smp +++ b/chapter25/docs/examples/FileIO.smp @@ -1,4 +1,3 @@ -// -*- mode: java; -*- // An implementation of // https://sampleprograms.io/projects/file-input-output/ diff --git a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java index 532f5c70..83616053 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -62,16 +62,10 @@ public class IterPeeps { public void addAll( Ary<Node> ary ) { _work.addAll(ary); } - public void deferInline( CodeGen code, CallEndNode cend ) { - if( !code._midAssert ) - _workInline.push(cend); - } - /** * Iterate peepholes and inlining to a fixed point */ public void iterate( CodeGen code ) { - CallEndNode cend = null; boolean didInline = false; Ary<Node> defer = new Ary<>(Node.class); while( true ) { @@ -79,18 +73,19 @@ public class IterPeeps { iteratePeeps(code); // Pick an inline candidate, no real heuristic, first come, first served + boolean inlined = false; + CallEndNode cend; while( (cend=_workInline.pop()) != null) { if( cend.isDead() ) continue; - if( cend.inline() == -1 ) defer.add(cend); - if( cend.inline() > 0 ) break; - } - // Found an inline candidate, so inline - if( cend != null ) { - // Inline, run peeps until clean again - cend.doInline(); - didInline = true; - continue; + byte inline = cend.maybeInline(); + if( inline == -1 ) defer.add(cend); + if( inline > 0 ) { + inlined = true; + break; + } } + // Inlined, run peeps until clean again + if( inlined ) { didInline = true; continue; } // No more candidates, check the defer list if( !didInline ) break; // No more progress, so all the "maybe inline after cleanup" do not progress // Some inlining happened, retry all the "try again after cleanup" calls @@ -102,7 +97,7 @@ public class IterPeeps { // Run all the code-reduction and type-lifting peeps as possible private void iteratePeeps( CodeGen code ) { - assert progressOnList(code, _work, true); + assert !CodeGen.expensiveAssert(1) || progressOnList(code, _work, true); int cnt=0; Node n; @@ -110,6 +105,8 @@ public class IterPeeps { if( n.isDead() ) continue; cnt++; // Useful for debugging, searching which peephole broke things Node x = n.peepholeOpt(); + if( n instanceof CallEndNode cend ) + _workInline.push(cend); if( x != null ) { if( x.isDead() ) continue; // peepholeOpt can return brand-new nodes, needing an initial type set @@ -136,7 +133,8 @@ public class IterPeeps { // If there are distant neighbors, move to worklist n.moveDepsToWorklist(); JSViewer.show(); // Show again - assert progressOnList(code, _work, true); // Very expensive assert + // Very expensive assert. + assert !CodeGen.expensiveAssert(cnt) || progressOnList(code, _work, true); } if( n.isUnused() && !(n instanceof StopNode) ) n.kill(); // Just plain dead @@ -174,6 +172,11 @@ public class IterPeeps { assert !checkType || monotonic : "Non-monotonic peep: "+n+"#"+n._nid+" old="+n._type+" new="+nval+" inputs="+inputTypes(n)+" peep="+m; if( list.on(n) ) return null; + if( n instanceof CallEndNode cend ) { + if( code._iter._workInline.on(cend) ) + return null; + assert cend.maybeInline() <= 0 : "Inline fired and not on worklist, CallEndNode#"+cend._nid; + } assert n.nOuts() > 0 : "Unused live node: "+n; m = n.peepholeOpt(); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 50f5c33b..bcefe996 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -45,6 +45,19 @@ public class CodeGen { /** True when tests deliberately randomize Iter worklist order. */ public static boolean iterSeedOverridden() { return System.getProperty("simple.iter.seed") != null; } + // Expensive assert sampling: + // -Dsimple.assert.expensive=0 disables these checks + // -Dsimple.assert.expensive=1 checks every step + // -Dsimple.assert.expensive=N checks once every 1<<N steps + private static final int EXPENSIVE_ASSERT_LOG = Integer.getInteger("simple.assert.expensive",8); + public static boolean expensiveAssert() { return EXPENSIVE_ASSERT_LOG > 0; } + public static boolean expensiveAssert( int trip ) { + if( EXPENSIVE_ASSERT_LOG <= 0 ) return false; + if( EXPENSIVE_ASSERT_LOG == 1 ) return true; + int shift = Math.min(EXPENSIVE_ASSERT_LOG,30); + return (trip & ((1<<shift)-1)) == 0; + } + // --------------------------- // Module Source Root public final String _modDir; @@ -458,7 +471,8 @@ public class CodeGen { return null; }); _iter.iterate(this); - assert Opto.fixedPointCheck(this); + // Expensive assert. + assert !expensiveAssert() || Opto.fixedPointCheck(this); _times[Phase.Iter.ordinal()] = System.currentTimeMillis() - t0; return this; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 5d4c151d..e8062c90 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -246,8 +246,8 @@ abstract public class Opto { // Since n._type changed, visit all output neighbors code._iter.addAll(n._outputs); n.moveDepsToWorklist(code._iter); - // Quadratic (expensive) small-step assert - assert worklistCheck(code); + // Quadratic (expensive) small-step assert. + assert !CodeGen.expensiveAssert(count) || worklistCheck(code); } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 061232c7..c9029049 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -133,19 +133,18 @@ public class CallEndNode extends CFGNode implements MultiNode { @Override public Node idealize() { + return null; + } - _inline = inlineCandidate(); - if( _inline == 1 ) { - ReturnNode ret = (ReturnNode)in(1); - FunNode fun = ret.fun(); - doTrivialInlining(fun); - return this; - } - // Delay for cleanup, before cloning - if( _inline >= 2 ) - CodeGen.CODE._iter.deferInline(CodeGen.CODE,this); + public byte maybeInline() { + byte inline = inlineCandidate(); + if( CodeGen.CODE._midAssert ) + return inline; + _inline = inline; + if( _inline > 0 ) + doInline(); - return null; + return _inline; } // Check if candidate right now, sets no flags diff --git a/chapter25/src/main/smp/sys.smp b/chapter25/src/main/smp/sys.smp index 8aef5b68..7705a187 100644 --- a/chapter25/src/main/smp/sys.smp +++ b/chapter25/src/main/smp/sys.smp @@ -1,4 +1,3 @@ -// -*- mode: java; -*- // top-level default standard library import diff --git a/chapter25/src/main/smp/sys/adt.smp b/chapter25/src/main/smp/sys/adt.smp index efdad395..a4fe40bf 100644 --- a/chapter25/src/main/smp/sys/adt.smp +++ b/chapter25/src/main/smp/sys/adt.smp @@ -1,4 +1,3 @@ -// -*- mode: java; -*- // Abstract data types. val bitset = bitset; diff --git a/chapter25/src/main/smp/sys/adt/bitset.smp b/chapter25/src/main/smp/sys/adt/bitset.smp index f56f1cce..d02cd2fe 100644 --- a/chapter25/src/main/smp/sys/adt/bitset.smp +++ b/chapter25/src/main/smp/sys/adt/bitset.smp @@ -1,4 +1,3 @@ -// -*- mode: java; -*- // A set of non-negative integers, represented one bit per value. struct bitset { diff --git a/chapter25/src/main/smp/sys/ary.smp b/chapter25/src/main/smp/sys/ary.smp index feade0f5..8312e94c 100644 --- a/chapter25/src/main/smp/sys/ary.smp +++ b/chapter25/src/main/smp/sys/ary.smp @@ -1,4 +1,3 @@ -// -*- mode: java; -*- // Array utilities diff --git a/chapter25/src/main/smp/sys/aryi64.smp b/chapter25/src/main/smp/sys/aryi64.smp index e4c39ac3..22ee082e 100644 --- a/chapter25/src/main/smp/sys/aryi64.smp +++ b/chapter25/src/main/smp/sys/aryi64.smp @@ -1,4 +1,3 @@ -// -*- mode: java; -*- // Ary/Vector of i64s struct aryi64 { diff --git a/chapter25/src/main/smp/sys/aryu8.smp b/chapter25/src/main/smp/sys/aryu8.smp index 186a45a3..21cf920b 100644 --- a/chapter25/src/main/smp/sys/aryu8.smp +++ b/chapter25/src/main/smp/sys/aryu8.smp @@ -1,4 +1,3 @@ -// -*- mode: java; -*- // Ary/Vector of u8s - a resizable array of bytes. struct aryu8 { diff --git a/chapter25/src/main/smp/sys/char.smp b/chapter25/src/main/smp/sys/char.smp index de37968e..22ca4213 100644 --- a/chapter25/src/main/smp/sys/char.smp +++ b/chapter25/src/main/smp/sys/char.smp @@ -1,4 +1,3 @@ -// -*- mode: java; -*- val toupper = { u8 c -> return c >= 'a' && c <= 'z' ? c - ('a' - 'A') : c; diff --git a/chapter25/src/main/smp/sys/io.smp b/chapter25/src/main/smp/sys/io.smp index 3d6be512..33fbdb5e 100644 --- a/chapter25/src/main/smp/sys/io.smp +++ b/chapter25/src/main/smp/sys/io.smp @@ -1,4 +1,3 @@ -// -*- mode: java; -*- // Simple I/O Library diff --git a/chapter25/src/main/smp/sys/libc.smp b/chapter25/src/main/smp/sys/libc.smp index 6d750f7b..133b5bf7 100644 --- a/chapter25/src/main/smp/sys/libc.smp +++ b/chapter25/src/main/smp/sys/libc.smp @@ -1,4 +1,3 @@ -// -*- mode: java; -*- // libc bindings: // https://www.man7.org/linux/man-pages/man2/<libc call>.2.html diff --git a/chapter25/src/main/smp/sys/scan.smp b/chapter25/src/main/smp/sys/scan.smp index ba91003e..44bedaaa 100644 --- a/chapter25/src/main/smp/sys/scan.smp +++ b/chapter25/src/main/smp/sys/scan.smp @@ -1,4 +1,3 @@ -// -*- mode: java; -*- // Scanner; a simple string parser. struct scan { |