From e5acc8a2127432d19ff43e420602f24fafa8d51b Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 22 Sep 2025 10:08:43 -0700 Subject: Chaining Conditionals and SCCP (#230) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit * merge fixup * More x86,risc,arm call convention fixes Collect callee and caller save masks (inverts of each other, except for spills). Reorg layout to be closer to each other; remove dead mask definitions; add final keyword * lui fix up with 32 bit immediates * Callee-save registers Callee-save registers and masks and inserting LRGs for same and spilling and picking good spills. Insert CalleeSaveNodes and edges to RetXXXs and RegMasks for those edges. Iterators for regmask. Better printing post-allocation * RegMask supports 128 bits All regs available arm, risc. MergeSort compiles & runs * added flags splitting * Fix risc5 compares No flags on risc5. Branch takes 2 inputs (one can be imm12). Float compare only sets a GPR to 0/1. Bool has a isFloat Common risc5 imm-form handling * extend test cases * imm encoding, flags fixed * grep for Todo: relocs * float riscv fixed * flags for set * lui fix for small bits [0, 12] * arm init * arm last touches * fmov still needs fix * minor fixes * minor fixes(2) * got rid of unnecessary stuff * create ch21 * remove encodings from chapter20 dir * 1/2 pass cleaning up ARM encoding API * ARM encoding compiles * Risc R_TYPE and I_TYPE * Progress RISC encodings Missing lots of stuff still * progress risc encoding * risc encodings compile * Update README.md * Fold up redundant OP/OP-FP risc5 encoding * x86 mem opcodes first cut break out MemOp encodings into parts; change x86 indirectAdr to use Encoding class, remove redundant asserts & code * x86 mem op encodings * x86 reg+imm forms * most reg-reg forms * More x86 encodings * Last few encodings * switch to binary literals over decimals for opcodes * logical immediates fixed, bitwise ops imm forms * tfp and setArm fixed * PC relative float for riscv * readme init * Merged pr/169 * Fixed the array1 test encodings Clean up branch invert logic during BB layout Cleanup branch target printing for RISC,ARM ImmRISC ops mask imm12 to 12 bits Fix NewRISC; hardcode RPC as part of call Fix RISC inverting branchs >,>= * floatarm encoding * tfparm and intarm * uncontional jump encoding for arm and riscv * smarter IntARM, Intx86 does not always include rex. * REX after PREFIX * fixup load and store indirect * updated rex prefix, if its 0x40 then its not needed * Rex fix for floats, got rid of unnecessary stuff. * rename to camel case, better param name * add test export * merged * store opt * store and load optimised forms handled * tfp patch * Store/load float arm/riscv/x64 * got rid of debug print * splits for x86, riscv and arm * readme fixups * fix global symbol numbering for constants * fix TFP pathc on arm and riscv, keep symbols in good order. * fix opcode for store and loads, memOpRisc for Store and splitting * replace hard coded opcodes with major opcodes * replace hard coded opcodes with major opcodes * add asserts and fix reg numbering * add asserts and fix reg numbering * minor updates * revert changes * remove constant pool from encoder TODO: add flag for JIT * extend test cases * minor fixes * minor fixes * update float test case * stringHash fix on x64 * remove conditional ConstantPool write * brainfuck minor fixes * minor arm fixes * split fix * brainfuck and fib * brain fuck * arg_count, person * add ignore * typo * riscv test sieve attempt * minor changes * riscv5 emulator additions * arm eval setup * Update riscv.java * arm eval basics * delta fixes * arm fixes * testfib arm * arg_count * small update for test newton * small update for test newton * testNewton runs on x64, riscv and arm * arm additions * arm pc eval fix * arm workings * debugging * Progress sieve on ARM Most ops need WMASK as the output, to exclude RSP. calloc sentinal changes to multiple of 4 NewArm needs to set arg X0 to #1; arg X1 is length. Fix EvalARM calling calloc & not advancing PC. Fix EvalARM using ints vs longs. Fix EvalARM missing AndI encoding. * Fix some arm encoding Fix some OBOB in R5 calloc encoding. Sort EvalArm by major opcodes. Add ASL. Remove leading switch. Fix OBOB in calloc. Fix shift in ld/st with reg+offset * arm sieve test * test person push * brainFuck arm * "and" "or" syntactic sugar * update encoding * ch23 `and` `or` * hack parse trinary for and, or * close * fixed or issue * Update CallEndNode.java * fix type issue * fixed * Adjust parseTrinary precedence vs && || * Fix arm simulation return * Formatting * Formatting * simplify rn to be always 0. * ch24 init * stacked rel * stack init * stack rel * remove parenthesis * got rid of old test case * update * upgrade eval * arm encoding bugs encodeing cset had a shift wrong eval missed using 0 for r31 * remove debug prints * force main to encode first * fix for missing main * got rid of debug prints * backwards with ch23 * simple new test cases * update test cases * enable old test * got rid of own test case * fix test11 * inline Api * inline x86_64 * inline test cases * fix stacked_r_5 * got rid of redundant rdid -1 set * Several new fuzzer addDeps/keep bugs. Fix risc/arm spill code values for passing 20 args. * Update README Move ch23_ch24 branch into ROADMAP * Create TypeAnalysis.md * Update TypeAnalysis.md * Update TypeAnalysis.md * More lattices for main * Update TypeAnalysis.md * Update TypeAnalysis.md * TypeAnalysis continued * fix typos * pointers * typo fix in reader * Update TypeAnalysis.md * sccp first attempt * test * init * still debug * Update TypeAnalysis.md * more examples * More docs * Update TypeAnalysis.md * widen phi nodes in loops * extra debug stuff for opto * Work in progress opto pass * Progress on opto * opto missing deps ConFldOff needs String.equals in `eq` Fix monotonic xfer functions in - CallENd, CProj, Load, Arith Mostly if either TOP or BOT inputs, the output is the matching TOP or BOT * push mid-progress * progress sccp * Make all the default parser integer types pre-widen Function sigs to calls allow wide ints * progress sccp * Update TypeInteger.java * progress SCCP * Progress SCCP * Progress SCCP A series of minor fixes, generally making transfer functions monotonic, or p[reserving sanity for error test cases. * Progress on opto Most tests pass, a few failures remain. Split Opto code into a seperate file. Improve `compute` precision in several places showing up during opto. bugfix: "split-thru-phis" on Parms changes calling conventions. Not ready for that yet. * most tests pass Handle non-default main. Simplify trivial inlining cutout test. ParmNode excludes most Phi opts Region idom excludes dead paths RPC now interns * Fix arm NOT encoding * all tests pass Float math handles high types monotonically Minus node does not reset int widen. Phi widen handles non-int mintype Dead returns do not error complain. Better handling default vs dead main * If NewNode is high, produce high results * BrainFuck uses a string * README * Update README.md * Typos from copilot review * monotonic fix MinusF * Update TypeAnalysis.md * Update TypeInteger.java --------- Co-authored-by: Hadházy Tamás Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> --- .../main/java/com/seaofnodes/simple/IterPeeps.java | 36 +-- .../main/java/com/seaofnodes/simple/Parser.java | 36 ++- .../com/seaofnodes/simple/codegen/CodeGen.java | 76 ++---- .../simple/codegen/GlobalCodeMotion.java | 2 +- .../java/com/seaofnodes/simple/codegen/Opto.java | 264 +++++++++++++++++++++ .../java/com/seaofnodes/simple/node/AddFNode.java | 31 +-- .../java/com/seaofnodes/simple/node/AddNode.java | 2 +- .../com/seaofnodes/simple/node/ArithFNode.java | 32 +++ .../java/com/seaofnodes/simple/node/ArithNode.java | 4 +- .../java/com/seaofnodes/simple/node/CProjNode.java | 2 +- .../com/seaofnodes/simple/node/CallEndNode.java | 33 ++- .../java/com/seaofnodes/simple/node/CallNode.java | 5 +- .../com/seaofnodes/simple/node/ConFldOffNode.java | 6 +- .../java/com/seaofnodes/simple/node/DivFNode.java | 21 +- .../java/com/seaofnodes/simple/node/FunNode.java | 35 ++- .../java/com/seaofnodes/simple/node/IfNode.java | 1 + .../java/com/seaofnodes/simple/node/LoadNode.java | 28 ++- .../com/seaofnodes/simple/node/MemMergeNode.java | 7 +- .../com/seaofnodes/simple/node/MinusFNode.java | 3 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 2 +- .../java/com/seaofnodes/simple/node/MulFNode.java | 21 +- .../java/com/seaofnodes/simple/node/NewNode.java | 35 ++- .../main/java/com/seaofnodes/simple/node/Node.java | 21 +- .../java/com/seaofnodes/simple/node/ParmNode.java | 21 ++ .../java/com/seaofnodes/simple/node/PhiNode.java | 40 +++- .../java/com/seaofnodes/simple/node/ProjNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 19 +- .../com/seaofnodes/simple/node/ReturnNode.java | 7 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 2 + .../java/com/seaofnodes/simple/node/SubFNode.java | 27 +-- .../com/seaofnodes/simple/node/ToFloatNode.java | 8 +- .../seaofnodes/simple/node/cpus/arm/NotARM.java | 2 +- .../simple/node/cpus/riscv/MemOpRISC.java | 3 + .../main/java/com/seaofnodes/simple/type/Type.java | 7 +- .../com/seaofnodes/simple/type/TypeConAry.java | 2 + .../com/seaofnodes/simple/type/TypeConAryB.java | 2 +- .../com/seaofnodes/simple/type/TypeConAryI.java | 2 +- .../com/seaofnodes/simple/type/TypeFunPtr.java | 7 +- .../com/seaofnodes/simple/type/TypeInteger.java | 66 ++++-- .../com/seaofnodes/simple/type/TypeMemPtr.java | 1 + .../java/com/seaofnodes/simple/type/TypeRPC.java | 30 ++- .../com/seaofnodes/simple/type/TypeStruct.java | 6 + .../java/com/seaofnodes/simple/BrainFuckTest.java | 8 +- .../java/com/seaofnodes/simple/Chapter18Test.java | 12 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 5 - .../java/com/seaofnodes/simple/Chapter24Test.java | 96 +++++++- .../src/test/java/com/seaofnodes/simple/Eval2.java | 21 +- .../com/seaofnodes/simple/progs/stacked_r_12x.c | 13 + .../com/seaofnodes/simple/progs/stacked_r_13x.c | 13 + 50 files changed, 818 insertions(+), 309 deletions(-) create mode 100644 chapter24/src/main/java/com/seaofnodes/simple/codegen/Opto.java create mode 100644 chapter24/src/main/java/com/seaofnodes/simple/node/ArithFNode.java create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/progs/stacked_r_12x.c create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/progs/stacked_r_13x.c (limited to 'chapter24/src') diff --git a/chapter24/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter24/src/main/java/com/seaofnodes/simple/IterPeeps.java index 9ae4231e..18ff470a 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -1,6 +1,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.JSViewer; @@ -46,7 +48,7 @@ import java.util.Random; */ public class IterPeeps { - private final WorkList _work; + public final WorkList _work; public IterPeeps( long seed ) { _work = new WorkList<>(seed); } @@ -59,7 +61,7 @@ public class IterPeeps { * Iterate peepholes to a fixed point */ public void iterate( CodeGen code ) { - assert progressOnList(code); + assert progressOnList(code, _work, true); int cnt=0; Node n; @@ -89,7 +91,7 @@ public class IterPeeps { // If there are distant neighbors, move to worklist n.moveDepsToWorklist(); JSViewer.show(); // Show again - assert progressOnList(code); // Very expensive assert + assert progressOnList(code, _work, true); // Very expensive assert } if( n.isUnused() && !(n instanceof StopNode) ) n.kill(); // Just plain dead @@ -109,18 +111,24 @@ public class IterPeeps { // neighbors and these should fail, but will then try to add dependencies // {@link #Node.addDep} which is a side effect in an assert. The {@link // #midAssert} is used to stop this side effect. - private boolean progressOnList(CodeGen code) { + // Pessimistic solver assert + public static boolean progressOnList(CodeGen code, WorkList list, boolean dir ) { code._midAssert = true; Node changed = code._stop.walk( n -> { - Node m = n; - if( n.compute().isa(n._type) && (!n.iskeep() || n._nid<=6) ) { // Types must be forwards, even if on worklist - if( _work.on(n) ) return null; - m = n.peepholeOpt(); - if( m==null ) return null; - } - System.err.println("BREAK HERE FOR BUG"); - return m; - }); + Node m = n; + Type nval = n.compute(); + if( (!n.iskeep() || n._nid<=8) && // Types must be forwards, even if on worklist + ( dir + ? nval.isa(n._type) // Pesi: new value lifts over old + : n._type.isa(nval) // Opto: new value falls over old + ) ) { + if( list.on(n) ) return null; + m = n.peepholeOpt(); + if( m==null ) return null; + } + System.err.println("BREAK HERE FOR BUG"); + return m; + }); code._midAssert = false; return changed==null; } @@ -176,7 +184,7 @@ public class IterPeeps { /** * True if Node is on the WorkList */ - boolean on( E x ) { return _on.get(x._nid); } + public boolean on( E x ) { return _on.get(x._nid); } boolean isEmpty() { return _len==0; } /** diff --git a/chapter24/src/main/java/com/seaofnodes/simple/Parser.java b/chapter24/src/main/java/com/seaofnodes/simple/Parser.java index 65c4abf7..f80e8f2c 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/Parser.java @@ -160,18 +160,26 @@ public class Parser { // default main). FunNode main = _code.link(_code._main); StopNode stop = _code._stop; + // Gather an explicit main + FunNode xmain = null; + for( Node n : stop._inputs ) + if( n instanceof ReturnNode ret && "main".equals(ret.fun()._name) ) + if( xmain != null ) throw Utils.TODO(); + else xmain = ret.fun(); + if( main.ret().expr()._type==Type.TOP && main.uctrl()==null ) { // Kill an empty default main; so it does not attempt to put a // "main" in any final ELF file main.setDef(1,XCTRL); // Delete default start input stop.delDef(stop._inputs.find(main.ret())); + if( xmain != null ) + _code.setMain(xmain); + } else { // We have a non-empty default main. - // Check for an explicit main - for( Node n : stop._inputs ) - if( n instanceof FunNode fun && fun._name.equals("main") ) - // Found an explicit "main" AND we have a default "main" - throw error("Cannot define both an explicit main and a default main"); + if( xmain != null ) + // Found an explicit "main" AND we have a default "main" + throw error("Cannot define both an explicit main and a default main"); main._name = "main"; } @@ -245,8 +253,13 @@ public class Parser { last = parseStatement(); // Last expression is the return except for the top-level main - if( ctrl()._type==Type.CONTROL && fun.sig() != _code._main ) - fun.addReturn(ctrl(), _scope.mem().merge(), last); + if( ctrl()._type==Type.CONTROL ) + if( fun.sig() != _code._main ) + fun.addReturn(ctrl(), _scope.mem().merge(), last); + else { + fun.setDef(1,XCTRL); // Kill default main + _code.addAll(fun._outputs); + } // Pop off the inProgress node on the multi-exit Region merge assert r.inProgress(); @@ -706,7 +719,7 @@ public class Parser { // Type is sane if( et!=Type.BOTTOM && !et.shallowISA(t) ) - expr = peep(new CastNode(t,null,expr)); + expr = peep(new CastNode(t.isConstant() ? t : t.widen(),null,expr)); return expr; } @@ -812,7 +825,7 @@ public class Parser { // Lift type to the declaration. This will report as an error later if // we cannot lift the type. if( !lift._type.isa(t) ) - lift = peep(new CastNode(t,null,lift)); + lift = peep(new CastNode(t.widen(),null,lift)); // Define a new name if( !_scope.define(name,t,xfinal || fld_final,lift, loc) ) throw error("Redefining name '" + name + "'", loc); @@ -1057,7 +1070,7 @@ public class Parser { else if( !match("!=") ) break; lhs.keep(); Node rhs = parseComparison(); - lhs = peep(new BoolNode.EQ(lhs.unkeep(),rhs)); + lhs = peep(new BoolNode.EQ(lhs.unkeep(),rhs).widen()); if( !eq ) lhs = peep(new NotNode(lhs)); } return lhs; @@ -1538,6 +1551,8 @@ public class Parser { Type tf = f._t; if( tf instanceof TypeMemPtr ftmp && ftmp.isFRef() ) tf = ftmp.makeFrom(((TypeMemPtr)(TYPES.get(ftmp._obj._name)))._obj); + if( base.isAry() && tf instanceof TypeConAry con ) + tf = con.elem(); // Field offset; fixed for structs, computed for arrays Node off = (name.equals("[]") // If field is an array body @@ -1707,7 +1722,6 @@ public class Parser { // Into the call CallNode call = (CallNode)new CallNode(loc(), args.asAry()).peephole(); - // Post-call setup CallEndNode cend = (CallEndNode)new CallEndNode(call).peephole(); call.peephole(); // Rerun peeps after CallEnd, allows early inlining diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 3e5d656f..3715d015 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -7,6 +7,7 @@ import com.seaofnodes.simple.print.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; import java.io.IOException; import java.util.*; @@ -30,7 +31,6 @@ public class CodeGen { Export, // Export } public Phase _phase; - // --------------------------- // Compilation source code public final String _src; @@ -124,7 +124,7 @@ public class CodeGen { // are structurally equal. public final HashMap _gvn = new HashMap<>(); - // + // Source of unique function indices private int _fidx =0; public TypeFunPtr makeFun( TypeFunPtr fun ) { int fidx = _fidx++; @@ -132,26 +132,33 @@ public class CodeGen { return fun.makeFrom(fidx); } // Signature for MAIN - public final TypeFunPtr _main; - // Reverse from a constant function pointer to the IR function being called - public FunNode link( TypeFunPtr tfp ) { - assert tfp.isConstant(); - TypeFunPtr tfp_generic = tfp.makeFrom(Type.BOTTOM); - FunNode fun =_linker.get(tfp_generic); - if( fun!=null && fun.isDead() ) { _linker.remove(tfp_generic); fun = null; } + public TypeFunPtr _main; + public void setMain(FunNode main) { + _main = main.sig(); + link(main); + } + // Reverse from a constant function pointer to the IR function being called. + // Error to call with a non-constant TFP + public FunNode link( TypeFunPtr tfp ) { return link(tfp.fidx()); } + // Return the FunNode from a fidx + public FunNode link( int fidx ) { + FunNode fun =_linker.atX(fidx); + if( fun!=null && fun.isDead() ) { + _linker.setX(fidx,null); fun = null; } return fun; } // Insert linker mapping from constant function signature to the function // being called. public void link(FunNode fun) { - _linker.put(fun.sig().makeFrom(Type.BOTTOM),fun); + int fidx = fun.sig().fidx(); + _linker.setX(fidx,fun); } // "Linker" mapping from constant TypeFunPtrs to heads of function. These // TFPs all have exact single fidxs and their return is wiped to BOTTOM (so // the return is not part of the match). - private final HashMap _linker = new HashMap<>(); + final Ary _linker = new Ary<>(FunNode.class); // Parser object public final Parser P; @@ -188,59 +195,14 @@ public class CodeGen { _phase = Phase.Opto; long t0 = System.currentTimeMillis(); - // Pessimistic peephole optimization on a worklist - _iter.iterate(this); - - // OPTIMISTIC PASS GOES HERE - - // Not really a true optimistic pass, but look for unlinked functions. - // This can be removed, which may trigger another round of pessimistic. - // This is the point where we flip from a virtual Call Graph (any call - // can call any function) to having a correct (but conservative) CG. - int progress = 0; - while( progress != _start.nOuts() ) { - progress = _start.nOuts(); - FunNode main = link(_main); - for( int i=0; i<_start.nOuts(); i++ ) { - Node use = _start.out(i); - if( use instanceof FunNode fun && - fun.nIns()==2 && fun.in(1)==_start && fun != main && - (fun._name==null || fun._name.startsWith("sys.")) ) { - add(fun).setDef(1,Parser.XCTRL); - addAll(fun._outputs); - i--; - } - } - _iter.iterate(this); - } - - // Freeze field sizes; do struct layouts; convert field offsets into - // constants. - for( int i=0; i<_start.nOuts(); i++ ) { - Node use = _start.out(i); - if( use instanceof ConFldOffNode off ) { - TypeMemPtr tmp = (TypeMemPtr) Parser.TYPES.get(off._name); - off.subsume( off.asOffset(tmp._obj) ); - i--; - } - } - _iter.iterate(this); - - // To help with testing, sort StopNode returns by NID - Arrays.sort(_stop._inputs._es,0,_stop.nIns(),(x,y) -> x._nid - y._nid ); + Opto.opto(this); _tOpto = (int)(System.currentTimeMillis() - t0); - - // TODO: - // Optimistic - // TODO: - // loop unroll, peel, RCE, etc return this; } public N add( N n ) { return _iter.add(n); } public void addAll( Ary ary ) { _iter.addAll(ary); } - // --------------------------- // Last check for bad programs public int _tTypeCheck; diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 520a18a3..d9c7a6ad 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -36,7 +36,7 @@ public abstract class GlobalCodeMotion { return; // Been there, done that if( def instanceof ReturnNode && use instanceof CallEndNode ) return; - assert !( def instanceof CallNode && use instanceof FunNode ); + assert !( def instanceof CallNode && use instanceof FunNode ); // All calls unwired now visit.set(cfg._nid); for( Node useuse : cfg._outputs ) _rpo_cfg(cfg,useuse,visit,rpo); diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/Opto.java new file mode 100644 index 00000000..fa3770fd --- /dev/null +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -0,0 +1,264 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; +import java.util.Arrays; + +// Optimistic Algorithm +abstract public class Opto { + + // Optimistic analysis - extended SCCP + + // Start all Types at TOP, and propagate changes until stable. Unlike a + // normal Sparse Conditional Constant Propagation, this version is + // interprocedural, computing effectively CFA0 in linear time using the + // normal SCCP algorithm. + + // This algo also builds a Call Graph; as Calls become reachable (CONTROL + // not TOP nor XCONTROL), they "link" against the reaching function + // pointers - adding edges from the Call to the Fun, and from the Return to + // the CallEnd. This allows the normal algorithm to use the normal edge + // propagation rules as function argument types stabilize. In the end, we + // get a fairly precise set of Call Graph edges between CallNodes and + // FunNodes. + public static void opto(CodeGen code) { + + // Pessimistic peephole optimization on a worklist - this completes + // whatever peepholes can run after parsing. + code._iter.iterate(code); + + // Reset Types before running the worklist algorithm + Ary oldTypes = new Ary<>(Type.class); // Used for asserts only + resetToTop(code,oldTypes); + + // The whole-world assumption: we use it if compiling `main`, and not otherwise. + // The assumption is no unknown callers into functions: + // - during or past an Opto phase (but not before, since parse through + // pessimistic must assume somebody calls an unknown function which + // calls everybody). + // - Have a `main` to start tracing the Call Graph from + // - - True for most test cases + // - - False for lacking a main; we assume the linker will call all public functions + + // True if we can make the "whole world" assumption, which means we are + // compiling the program entry: `main`. + boolean wholeWorld = code.link(code._main) != null; + + + // If wholeWorld, remove the Start inputs to functions - they are not + // called unless they get linked (hence go dead and can be removed). + // If not wholeWorld, keep only public methods (and not the std lib). + unlinkStart(wholeWorld,code); + + + // OPTIMISTIC INTERPROCEDURAL SCCO + sccp(code, oldTypes); + + // After SCCP add everything changed to the worklist and see if + // peepholes can make more progress. + moveChangesToWorklist(code, oldTypes); + + // Progress with improved types. E.g. since we have a full Call Graph + // here, we might do better inlining. + code._iter.iterate(code); + + // TODO: + // loop unroll, peel, RCE, etc + + // Freeze field sizes; do struct layouts; convert field offsets into + // constants. + fieldSizes(code); + // Propagate field size constants + code._iter.iterate(code); + + // Throw away the Call Graph + + // The remaining passes assume all calls are unlinked; i.e. we are + // throwing away the Call Graph here. Functions only reachable from + // internal calls need to be re-hooked to stop/start less they go dead. + removeCallGraph(code); + + // To help with testing, sort StopNode Returns by NID + Arrays.sort(code._stop._inputs._es,0,code._stop.nIns(),(x,y) -> x._nid - y._nid ); + } + + // Reset Types before running the worklist algorithm + private static void resetToTop(CodeGen code, Ary oldTypes ) { + code._start.walk( x -> { + oldTypes.setX(x._nid,x._type); // Record original types for asserts + x._type = Type.TOP; // Reset all Nodes to TOP + code._iter.add(x); // Visit everybody at least once; most Nodes produce better than TOP + // Unlink all existing (conservative) linkages. + if( x instanceof CallNode call ) + call.unlink_all(); + return null; + } ); + } + + + // If wholeWorld, remove the Start inputs to functions - they are not + // called unless they get linked (hence go dead and can be removed). If + // not wholeWorld, keep only public methods (and not the std lib). + private static void unlinkStart(boolean wholeWorld, CodeGen code) { + for( FunNode fun : code._linker ) { + if( fun != null && !fun.isDead() && !funIsPublic(code,wholeWorld,fun) ) { + assert fun.in(1)==code._start; // Start always in slot 1 + fun.removeDeadPath(1); + // By same logic, remove stop->return linkage, without + // remove the (now dead) ReturnNode; it awaits in limbo + // for the opto phase to link to some valid call + code._stop._inputs.del(code._stop._inputs.find(fun.ret())); + fun.ret().delUse(code._stop); + } + } + } + + // Function is public (callable from Start directly). + // - Always true for main + // - Never true for stdlib, or anonymous functions + // - Named functions use `!wholeWorld` + private static boolean funIsPublic( CodeGen code, boolean wholeWorld, FunNode fun ) { + // Always true for main + if( fun.sig().fidx() == code._main.fidx() ) return true; + // Never true for stdlib or anonymous functions + if( fun._name == null || fun._name.startsWith("sys.") ) + return false; + // Named functions (and not stdlib) are callable if not whole-world. + return !wholeWorld; + } + + // As part of building a CallGraph, when opto finds a function ptr flowing + // into a Call, link the Call and Fun. + private static void linkCG(CodeGen code, TypeFunPtr tfp, CallNode call) { + if( tfp.nargs() != call.nargs() ) return; // Error calls hit this + for( long fidxs=tfp.fidxs(); fidxs!=0; fidxs=TypeFunPtr.nextFIDX(fidxs) ) { + int fidx = Long.numberOfTrailingZeros(fidxs); + FunNode fun = code.link(fidx); + // null here means an external function; i.e. this Call + // calls to an outside library and all its arguments escape. + if( fun != null && !call.linked(fun) ) { + call.link( fun ); + code._iter.add(fun); + code._iter.addAll(fun._outputs); + } + } + } + + // The core SCCP algorithm + private static void sccp( CodeGen code, Ary oldTypes ) { + // Iter workList is empty at this point + // OPTIMISTIC PASS + Node n; + int count = 0; // Debug counter + while( (n = code._iter._work.pop()) != null ) { + if( n.isDead() ) continue; + count++; + Type oval = n._type, nval = n.compute(); + if( oval == nval ) continue; + assert oval.isa(nval); // Types start high and always fall + Type pesiVal = oldTypes.at(n._nid); + assert nval.isa(pesiVal); // Never fall worse than the pessimistic pass + n._type = nval; + + // If a TFP adds a new function input to a call, link to the new Fun + if( nval instanceof TypeFunPtr tfp ) { + for( Node use : n._outputs ) + if( !use._type.isHigh() && use instanceof CallNode call && call.fptr() == n ) + linkCG(code,tfp,call); + } + + // Link a Call which becomes alive + if( n instanceof CallNode call && oval.isHigh() && !nval.isHigh() && call.fptr()._type instanceof TypeFunPtr ) + linkCG(code,call.tfp(),call); + + // Since n._type changed, visit all output neighbors + code._iter.addAll(n._outputs); + n.moveDepsToWorklist(code._iter); + // Quadratic (expensive) small-step assert + assert check(code); + } + } + + // Quadratic (expensive) small-step assert + private static boolean check(CodeGen code) { + code._start.walk( x -> { + Type xval = x.compute(); + assert xval == x._type || (x._type.isa( xval ) && code._iter._work.on( x )); + return null; + }); + return true; + } + + // After SCCP add everything changed to the worklist and see if peepholes + // can make more progress. + private static void moveChangesToWorklist(CodeGen code, Ary oldTypes) { + code._start.walk( x -> { + assert x.compute() == x._type; // Hit the fixed point + assert x._nid >= oldTypes._len || x._type.isa(oldTypes.at(x._nid)); // Hit at least the bottom-up type + code._iter.add(x); + return null; + }); + } + + // Freeze field sizes; do struct layouts; convert field offsets into + // constants. + private static void fieldSizes( CodeGen code ) { + for( int i=0; i { + // Unlink all existing (conservative) linkages. + if( x instanceof CallNode call ) { + for( Node y : call._outputs ) { + // Keep function alive and hooked to Start so it gets + // codegen'd. Function is callable by this call via + // TFP, although perhaps not by any other means. + if( y instanceof FunNode fun && !(fun.in(1) instanceof StartNode) ) { + ParmNode rpc = fun.rpc(); + if( rpc==null ) // Ensure valid RPC + rpc = makeRPC(fun); + // Insert a hook to Start and Stop + fun.insertDef(1,code._start); + for( Node use : fun._outputs ) + if( use instanceof ParmNode parm ) + parm.insertDef(1,ConstantNode.make(parm._type).peephole()); + code._stop.addDef(fun.ret()); + } + } + call.unlink_all(); + } + return null; + } ); + + } + + // Make a valid Parm RPC. + // First make sure a valid RPC; single-call into multi-fun will have each + // function having a single call site, so the RPC becomes a constant and + // folds - but since multiple targets, the Call never inlines. Recreate a + // valid RPC so codegen (and Eval2) understands the calling convention. + private static ParmNode makeRPC( FunNode fun ) { + ParmNode rpc = new ParmNode("$rpc",0,fun.ret().rpc()._type,fun); + for( int i=1; i= 2 && !lhs.inProgress() && - lhs.region()==rhs.region() && + lhs.region()==rhs.region() && !(lhs.region() instanceof FunNode) && lhs.nIns()>2 && // A 1-input Phi will collapse already // Disallow with self-looping phi; these will collapse (lhs.in(2)!=lhs && rhs.in(2)!=rhs) ) { diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/CProjNode.java index a6e21ea0..d18f779b 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -33,7 +33,7 @@ public class CProjNode extends CFGNode { @Override public Type compute() { Type t = ctrl()._type; - return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; + return t instanceof TypeTuple tt ? tt._types[_idx] : (t.isHigh() ? Type.TOP : Type.BOTTOM); } @Override diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 8c25c158..a7e50c39 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -39,16 +39,23 @@ public class CallEndNode extends CFGNode implements MultiNode { @Override public Type compute() { - if( !(in(0) instanceof CallNode call) ) + if( !(in(0) instanceof CallNode call) || call._type != Type.CONTROL ) return TypeTuple.RET.dual(); - Type ret = Type.BOTTOM; - if( addDep(call.fptr())._type instanceof TypeFunPtr tfp ) { + // Mid-fold, just take the one single callers' return type + if( _folding ) return in(1)._type; + // Grab the TFP and use the functions declared return type. + Type ftype = addDep(call.fptr())._type; + Type ret = ftype.isHigh() ? Type.TOP : Type.BOTTOM; + if( ftype instanceof TypeFunPtr tfp ) { ret = tfp.ret(); // Here, if I can figure out I've found *all* callers, then I can meet // across the linked returns and join with the function return type. - if( tfp.isConstant() && nIns()>1 ) { - assert nIns()==2; // Linked exactly once for a constant - ret = ((TypeTuple)in(1)._type).ret(); // Return type + if( 1+tfp.nfcns() == nIns() ) { // A linked function for every concrete function + ret = Type.TOP; + for( int i=1; i _deps; /** - * Add a node to the list of dependencies. Only add it if its not an input + * Add a node to the list of dependencies. Only add it if it's not an input * or output of this node, that is, it is at least one step away. The node * being added must benefit from this node being peepholed. */ @@ -569,13 +570,13 @@ public abstract class Node implements Cloneable { } // Move the dependents onto a worklist, and clear for future dependents. - public void moveDepsToWorklist( ) { - if( _deps==null ) return; - CODE.addAll(_deps); + public void moveDepsToWorklist( ) { moveDepsToWorklist(CODE._iter); } + public void moveDepsToWorklist( IterPeeps iter ) { + if( _deps == null ) return; + iter.addAll(_deps); _deps.clear(); } - // Two nodes are equal if they have the same inputs and the same "opcode" // which means the same Java class, plus same internal parts. @Override public final boolean equals( Object o ) { diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ParmNode.java index a14a4fb9..880f936c 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -1,6 +1,8 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMemPtr; import java.util.BitSet; public class ParmNode extends PhiNode { @@ -39,6 +41,25 @@ public class ParmNode extends PhiNode { // Always in-progress until we run out of unknown callers @Override public boolean inProgress() { return in(0) instanceof FunNode fun && fun.inProgress(); } + @Override + public Node idealize() { + if( !(region() instanceof FunNode) ) + return in(1); // Input has collapse to e.g. starting control. + // If function is folding, do all possible peeps + if( fun()._folding ) return super.idealize(); + + // Can upgrade minType even while in-progress + if( _minType instanceof TypeMemPtr tmp && _minType.isFRef() ) { + TypeMemPtr tmp2 = (TypeMemPtr) Parser.TYPES.get(tmp._obj._name); + if( tmp2!=null && tmp2 != _minType ) { + _minType = tmp2; + return this; + } + } + // Skip most phi optimizations on parms + return null; + } + @Override public boolean eq( Node n ) { return ((ParmNode)n)._idx==_idx && super.eq(n); } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java index fcbacbc9..bdc0d0fa 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -14,6 +14,8 @@ public class PhiNode extends Node { // Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. Type _minType; + int lattice_drop; + public PhiNode(String label, Type minType, Node... inputs) { super(inputs); _label = label; @@ -55,26 +57,43 @@ public class PhiNode extends Node { public CFGNode region() { return (CFGNode)in(0); } @Override public boolean isMem() { return _minType instanceof TypeMem; } @Override public boolean isPinned() { return true; } + boolean isRPC() { return false; } @Override public Type compute() { if( !(region() instanceof RegionNode r) ) - return region()._type==Type.XCONTROL ? (_type instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type; + return region()._type==Type.XCONTROL || region()._type==Type.TOP ? (_type instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type; // During parsing Phis have to be computed type pessimistically. - if( r.inProgress() ) return _minType; + if( r.inProgress() ) + // Loop-Phis must lift to the declared type, because that is how + // the Parser keeps precise types until the loop finishes parsing. + // Similar, ParmNodes use precise minType until all calls are + // linked (post opto). + return r instanceof LoopNode || (this instanceof ParmNode) ? _minType : Type.BOTTOM; // Set type to local top of the starting type - //Type t = _minType.dual(); Type t = Type.TOP; - for (int i = 1; i < nIns(); i++) + for (int i = 1; i < nIns(); i++) { // If the region's control input is live, add this as a dependency // to the control because we can be peeped should it become dead. - if( addDep(r.in(i))._type != Type.XCONTROL ) { + Type ctrl = addDep(r.in(i))._type; + if( ctrl != Type.XCONTROL && ctrl != Type.TOP ) { if( in(i)._type==Type.BOTTOM ) return Type.BOTTOM; t = t.meet(in(i)._type); } - t = t.join( _minType ); - return t; + } + Type newt = t.join( _minType ); + + // phi loop widening part + if( region() instanceof LoopNode && // Only around loops + newt instanceof TypeInteger newi && + // Types changed and are falling (the optimistic case, expected to fall forever) + newi != _type ) { + if( !newi.isConstant() && (!(_type instanceof TypeInteger oldi) || newi._widen <= oldi._widen) ) + return newi.same_but_slightly_wider_than(_minType); + } + + return newt; } @Override @@ -83,7 +102,7 @@ public class PhiNode extends Node { return in(1); // Input has collapse to e.g. starting control. // Can upgrade minType even while in-progress if( _minType instanceof TypeMemPtr tmp && _minType.isFRef() ) { - TypeMemPtr tmp2 = (TypeMemPtr)CodeGen.CODE.P.TYPES.get(tmp._obj._name); + TypeMemPtr tmp2 = (TypeMemPtr) Parser.TYPES.get(tmp._obj._name); if( tmp2!=null && tmp2 != _minType ) { _minType = tmp2; return this; @@ -136,13 +155,14 @@ public class PhiNode extends Node { Node val = in(3-nullx); if( val instanceof CastNode cast ) val = cast.in(1); - if( addDep(r.idom(this)) instanceof IfNode iff && addDep(iff.pred())==val ) { + Node ridom = r.idom(this); + if( ridom instanceof IfNode iff && addDep(iff.pred())==val ) { // Must walk the idom on the null side to make sure we hit False. CFGNode idom = (CFGNode)r.in(nullx); while( idom != null && idom.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom(); if( idom instanceof CProjNode proj && proj._idx==1 ) return val; - } + } else if( ridom != null ) addDep(ridom); } } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ProjNode.java index a0394e5b..586527c8 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -41,7 +41,7 @@ public class ProjNode extends Node { @Override public Type compute() { Type t = in(0)._type; - return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; + return t instanceof TypeTuple tt ? tt._types[_idx] : t.oob(); } @Override public Node idealize() { return ((MultiNode)in(0)).pcopy(_idx); } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 8f0bddb6..b115a260 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -37,7 +37,7 @@ public class RegionNode extends CFGNode { public Node idealize() { if( inProgress() ) return null; - Node progress = deadPath(); + Node progress = deadPath(false); if( progress!=null ) return progress; // If down to a single input, become that input @@ -83,16 +83,21 @@ public class RegionNode extends CFGNode { return null; } - Node deadPath() { + Node deadPath(boolean skipStart) { // Delete dead paths into a Region - int path = findDeadInput(); + int path = findDeadInput(skipStart ? 2 :1); if( path==0 ) return null; + // Do not delete the entry path of a loop (ok to remove the back edge // and make the loop a single-entry Region which folds away the Loop). // Folding the entry path confused the loop structure, moving the // backedge to the entry point. if( this instanceof LoopNode loop && loop.entry()==in(path) ) return null; + return removeDeadPath(path); + } + + public Node removeDeadPath(int path) { // Cannot use the obvious output iterator here, because a Phi deleting // an input might recursively delete *itself*. This shuffles the // output array, and we might miss iterating an unrelated Phi. So on @@ -109,9 +114,8 @@ public class RegionNode extends CFGNode { return isDead() ? Parser.XCTRL : delDef(path); } - - private int findDeadInput() { - for( int i=1; i return f() };` return Parser.error("No defined return type", loc); + // Rather ugly way to print conflicting return types + int cnt = (ti?1:0) + (tf?1:0) + (tp||tn?1:0); + if( cnt==1 ) return null; // Uniform return type, something else errored and will report SB sb = new SB().p("No common type amongst "); if( ti ) sb.p("int and "); if( tf ) sb.p("f64 and "); diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 5fb274db..8e33512a 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -132,6 +132,8 @@ public class StoreNode extends MemOpNode { public Parser.ParseException err() { Parser.ParseException err = super.err(); if( err != null ) return err; + if( ptr()._type == Type.TOP ) + return null; // This means we have an error input, report elsewhere TypeMemPtr tmp = (TypeMemPtr)ptr()._type; if( tmp._obj.field(_name)._final && !_init ) return Parser.error("Cannot modify final field '"+_name+"'",_loc); diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 5c7e969f..3fc4f7ca 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -5,38 +5,21 @@ import com.seaofnodes.simple.type.TypeFloat; import java.util.BitSet; -public class SubFNode extends Node { - public SubFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } +public class SubFNode extends ArithFNode { + public SubFNode(Node lhs, Node rhs) { super(lhs, rhs); } @Override public String label() { return "SubF"; } @Override public String glabel() { return "-"; } - @Override - public StringBuilder _print1(StringBuilder sb, BitSet visited) { - in(1)._print0(sb.append("("), visited); - in(2)._print0(sb.append("-"), visited); - return sb.append(")"); - } - - @Override - public Type compute() { - if (in(1)._type instanceof TypeFloat i0 && - in(2)._type instanceof TypeFloat i1) { - if (i0.isConstant() && i1.isConstant()) - return TypeFloat.constant(i0.value()-i1.value()); - } - return in(1)._type.meet(in(2)._type); - } + @Override double doOp( double x, double y ) { return x-y; } @Override public Node idealize() { - Node lhs = in(1); - Type t2 = in(2)._type; - // Sub of 0. + Type t2 = in(2)._type; if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 ) - return lhs; + return in(1); return null; } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java index c098ad99..e02183a0 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java @@ -20,12 +20,10 @@ public class ToFloatNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() ) return TypeFloat.F64.dual(); if( in(1)._type == Type.NIL ) return TypeFloat.FZERO; - if (in(1)._type instanceof TypeInteger i0 ) { - if( i0.isHigh() ) return TypeFloat.F64.dual(); - if( i0.isConstant() ) - return TypeFloat.constant(i0.value()); - } + if( in(1)._type instanceof TypeInteger i0 && i0.isConstant() ) + return TypeFloat.constant(i0.value()); return TypeFloat.F64; } 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 027a8128..d78421ca 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 @@ -19,7 +19,7 @@ public class NotARM extends MachConcreteNode implements MachNode{ short reg1 = enc.reg(in(1)); int subs = arm.imm_inst(arm.OP_SUBS, 0, reg1, self); enc.add4(subs); - int cset = arm.cond_set(arm.OP_CSET, 31, arm.COND.EQ, 63, reg1); + int cset = arm.cond_set(arm.OP_CSET, 31, arm.COND.EQ, 31, reg1); enc.add4(cset); } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MemOpRISC.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MemOpRISC.java index 93c90052..b9e6e5ba 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MemOpRISC.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MemOpRISC.java @@ -49,6 +49,9 @@ public abstract class MemOpRISC extends MemOpNode implements MachNode { if( _declaredType == TypeInteger.BOOL) func3=4; // LBU if( _declaredType == TypeInteger.U16 ) func3=5; // LHU if( _declaredType == TypeInteger.U32 ) func3=6; // LWU + if( _declaredType instanceof TypeInteger ti ) { + if( -128 <= ti._min && ti._max < 128 ) func3 = 0; // LB + } // float if( _declaredType == TypeFloat.F32) func3 = 2; // fLW fSW diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter24/src/main/java/com/seaofnodes/simple/type/Type.java index b7a8408e..2d5a6d04 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/Type.java @@ -316,7 +316,8 @@ public class Type /*implements Cloneable*/ { } // True if this "isa" t; e.g. 17 isa TypeInteger.BOT - public boolean isa( Type t ) { return meet(t)==t; } + // Applies for pessimistic case + public boolean isa( Type t ) { return meet(t)==t; } // True if this "isa" t up to named structures public boolean shallowISA( Type t ) { return isa(t); } @@ -329,6 +330,9 @@ public class Type /*implements Cloneable*/ { // Is forward-reference public boolean isFRef() { return false; } + // Cap at limits + public Type oob() { return isHigh() ? TOP : BOTTOM; } + // ---------------------------------------------------------- // Cyclic types! Flag the start of a cyclic type by putting a sentinel in @@ -477,6 +481,7 @@ public class Type /*implements Cloneable*/ { Type _glb(boolean mem) { assert is_simple(); return Type.BOTTOM; } Type _close() { return this; } + public Type widen() { return this; } // ---------------------------------------------------------- diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAry.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAry.java index d4003f87..c5543030 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAry.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAry.java @@ -51,6 +51,8 @@ public class TypeConAry extends Type { @Override public boolean isHigh() { return this==TOP; } @Override boolean _isConstant() { return true; } + @Override Type _glb(boolean mem) { return this; } + @Override boolean _isGLB(boolean mem) { return true; } // Meet-over-elements type public Type elem() { diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java index fd2b2635..9e5f0a2d 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java @@ -15,7 +15,7 @@ public class TypeConAryB extends TypeConAry { @Override public int len() { return _ary.length; } @Override public int log_size() { return 0; } @Override public String str() { return "[\""+new String(_ary)+"\"]"; } - @Override boolean eq(Type t) { return Arrays.equals(_ary,((TypeConAryB)t)._ary); } + @Override boolean eq(Type t) { return t instanceof TypeConAryB ary && Arrays.equals(_ary,ary._ary); } @Override int hash() { return Arrays.hashCode(_ary); } @Override public void write( ByteArrayOutputStream baos ) { baos.write(_ary,0,_ary.length); } } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java index 924e3d73..8228887e 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java @@ -12,6 +12,6 @@ public class TypeConAryI extends TypeConAry { @Override public int len() { return _ary.length; } @Override public int log_size() { return 2; } @Override public String str() { return "[i32]"; } - @Override boolean eq(Type t) { return Arrays.equals(_ary,((TypeConAryI)t)._ary); } + @Override boolean eq(Type t) { return t instanceof TypeConAryI ary && Arrays.equals(_ary,ary._ary); } @Override int hash() { return Arrays.hashCode(_ary); } } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index b21dd451..ddef9651 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -158,8 +158,13 @@ public class TypeFunPtr extends TypeNil { public Type ret() { return _ret; } public int nargs() { return _sig.length; } public int fidx() { assert Long.bitCount(_fidxs)==1; return Long.numberOfTrailingZeros(_fidxs); } + public int nfcns() { + if( _fidxs < 0 ) return Integer.MAX_VALUE; // Infinite choices + return Long.bitCount(_fidxs); + } + // Used to walk over type structures @Override int nkids() { return _sig.length+1; } @Override Type at( int idx ) { return idx == _sig.length ? _ret : _sig[idx]; @@ -235,7 +240,7 @@ public class TypeFunPtr extends TypeNil { return tilde+fidx; } - // Usage: for( long fidxs=fidxs(); fidxs!=0; fidxs=nextFIDX(fidxs) { int fidxs = Long.numberOfTrailingZeros(fidxs); ... } + // Usage: for( long fidxs=fidxs(); fidxs!=0; fidxs=nextFIDX(fidxs) ) { int fidx = Long.numberOfTrailingZeros(fidxs); ... } public static long nextFIDX(long fidxs) { return fidxs & (fidxs-1); } } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 99f237a9..97c17a34 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -18,24 +18,49 @@ public class TypeInteger extends Type { */ public long _min, _max; + public byte _widen; + private static final Ary FREE = new Ary<>(TypeInteger.class); - private TypeInteger(long min, long max) { super(TINT); init(min,max); } - private TypeInteger init(long min, long max) { _min = min; _max = max; return this; } - public static TypeInteger malloc(long lo, long hi) { return FREE.isEmpty() ? new TypeInteger(lo,hi) : FREE.pop().init(lo,hi); } - public static TypeInteger make(long lo, long hi) { - TypeInteger i = malloc(lo,hi); + private TypeInteger(long min, long max, byte widen) { super(TINT); init(min,max,widen); } + private TypeInteger init(long min, long max, byte widen) { + // Constants must always have a widen value of zero. Widening is only + // meaningful for ranges of values - which otherwide can increase in + // range size indefinitely. + assert min!=max || widen==0; // Constants always zero widen + _min = min; _max = max; _widen=widen; + return this; + } + public static TypeInteger malloc(long lo, long hi, byte widen) { return FREE.isEmpty() ? new TypeInteger(lo,hi,widen) : FREE.pop().init(lo,hi,widen); } + public static TypeInteger make(long lo, long hi) { return make(lo,hi,(byte)0); } + public static TypeInteger make(long lo, long hi, byte widen) { + TypeInteger i = malloc(lo,hi,lo==hi ? 0 : widen); TypeInteger t2 = i.intern(); return t2==i ? i : t2.free(i); } + public TypeInteger makeWide(byte widen) { + if( widen == _widen ) return this; + if( _min == Long.MIN_VALUE && _max == Long.MAX_VALUE ) + return TypeInteger.BOT; + if( _min==_max ) return this; // Leave constants always narrow + return make(_min,_max,widen); + } @Override TypeInteger free(Type t) { TypeInteger i = (TypeInteger)t; i._min = i._max = 0; + i._widen = 0; i._hash = 0; i._dual = null; FREE.push(i); return this; } + public Type same_but_slightly_wider_than( Type minType ) { + return _widen < 3 ? make(_min,_max, (byte)(_widen+1)) : minType; + } + // Force max widen + @Override public Type widen() { + return _widen==3 ? this : make(_min,_max,(byte)3); + } public static TypeInteger constant(long con) { return make(con, con); } public final static TypeInteger ZERO= make(0,0); @@ -43,20 +68,22 @@ public class TypeInteger extends Type { public final static TypeInteger TRUE= make(1,1); public final static TypeInteger TWO = make(2,2); // Shows up in some Simple tests as the starting argument - public final static TypeInteger I1 = make(-1,0); - public final static TypeInteger I8 = make(-128,127); - public final static TypeInteger I16 = make(-32768,32767); - public final static TypeInteger I32 = make(-1L<<31,(1L<<31)-1); - public final static TypeInteger BOT = make(Long.MIN_VALUE,Long.MAX_VALUE); + public final static TypeInteger I1 = make(-1,0,(byte)3); + public final static TypeInteger I8 = make(-128,127,(byte)3); + public final static TypeInteger I16 = make(-32768,32767,(byte)3); + public final static TypeInteger I32 = make(-1L<<31,(1L<<31)-1,(byte)3); + public final static TypeInteger BOT = make(Long.MIN_VALUE,Long.MAX_VALUE,(byte)3); public final static TypeInteger TOP = (TypeInteger)BOT.dual(); - public final static TypeInteger U1 = make(0,1); + public final static TypeInteger U1 = make(0,1,(byte)3); public final static TypeInteger BOOL= U1; - public final static TypeInteger U8 = make(0,255); - public final static TypeInteger U16 = make(0,65535); - public final static TypeInteger U32 = make(0,(1L<<32)-1); + public final static TypeInteger U8 = make(0,255,(byte)3); + public final static TypeInteger U16 = make(0,65535,(byte)3); + public final static TypeInteger U32 = make(0,(1L<<32)-1,(byte)3); + + public final static TypeInteger FATBOOL = make(0,1,(byte)2); - public static void gather(ArrayList ts) { ts.add(I32); ts.add(BOT); ts.add(U1); ts.add(I1); ts.add(U8); } + public static void gather(ArrayList ts) { ts.add(I32); ts.add(BOT); ts.add(U1); ts.add(I1); ts.add(U8); ts.add(ZERO); ts.add(FATBOOL); } @Override public String str() { if( _isConstant() ) return ""+_min; @@ -95,6 +122,7 @@ public class TypeInteger extends Type { else if (-0xFFFFFFFFL <= _min && _min <= 0xFFFFFFFFL) return 2; else return 3; } + if( -128 <= _min && _max < 128 ) return 0; // 1 byte throw Utils.TODO(); } @@ -122,11 +150,11 @@ public class TypeInteger extends Type { if( other instanceof TypeConAry ary ) return ary.imeet(this); // Invariant from caller: 'this' != 'other' and same class (TypeInteger) TypeInteger i = (TypeInteger)other; // Contract - return make(Math.min(_min,i._min), Math.max(_max,i._max)); + return make(Math.min(_min,i._min), Math.max(_max,i._max), (byte)Math.max(_widen,i._widen)); } @Override TypeInteger xdual() { - return _min==_max ? this : malloc(_max,_min); + return _min==_max ? this : malloc(_max,_min,(byte)(-_widen)); } @Override public TypeInteger nonZero() { @@ -146,8 +174,8 @@ public class TypeInteger extends Type { return isHigh() ? dual() : this; } - @Override int hash() { return Utils.fold(_min) * Utils.fold(_max); } + @Override int hash() { return Utils.fold(_min) * Utils.fold(_max) + _widen; } @Override public boolean eq( Type t ) { - return t instanceof TypeInteger i && _min==i._min && _max==i._max; + return t instanceof TypeInteger i && _min==i._min && _max==i._max && _widen==i._widen; } } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 6041155d..689b73ce 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -61,6 +61,7 @@ public class TypeMemPtr extends TypeNil { public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(_nil, obj, _one); } public TypeMemPtr makeNullable() { return makeFrom((byte)3); } @Override TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil, _obj, _one); } + public TypeMemPtr makeHigh() { return make((byte)0,_obj.makeHigh(),false); } // An abstract pointer, pointing to either a Struct or an Array. // Can also be null or not, so 4 choices {TOP,BOT} x {nil,not} diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeRPC.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeRPC.java index bd5e2923..a1389540 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeRPC.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeRPC.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.type; +import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.SB; import com.seaofnodes.simple.util.Utils; import java.util.ArrayList; @@ -13,19 +14,31 @@ public class TypeRPC extends Type { // A set of CallEndNode IDs (or StopNode); commonly just one. // Basically a sparse bit set - final HashSet _rpcs; + HashSet _rpcs; // If true, invert the meaning of the bits - final boolean _any; + boolean _any; - private TypeRPC(boolean any, HashSet rpcs) { - super(TRPC); - _any = any; - _rpcs = rpcs; + private static final Ary FREE = new Ary<>(TypeRPC.class); + private TypeRPC init(boolean any, HashSet rpcs) { _any=any; _rpcs=rpcs; return this; } + private TypeRPC() { super(TRPC); } + private static TypeRPC malloc(boolean any, HashSet rpcs) { + return (FREE.isEmpty() ? new TypeRPC() : FREE.pop()).init(any,rpcs); } private static TypeRPC make(boolean any, HashSet rpcs) { - return new TypeRPC(any,rpcs).intern(); + TypeRPC rpc = (FREE.isEmpty() ? new TypeRPC() : FREE.pop()).init(any,rpcs); + TypeRPC t2 = rpc.intern(); + return t2==rpc ? rpc : t2.free(rpc); } + @Override TypeRPC free(Type t) { + TypeRPC rpc = (TypeRPC)t; + rpc._rpcs = null; + rpc._dual = null; + rpc._hash = 0; + FREE.push(rpc); + return this; + } + @Override boolean isFree() { return _rpcs==null; } public static TypeRPC constant(int cend) { HashSet rpcs = new HashSet<>(); @@ -82,8 +95,7 @@ public class TypeRPC extends Type { return make(any,rpcs); } - @Override - Type xdual() { return new TypeRPC(!_any,_rpcs); } + @Override Type xdual() { return malloc(!_any,_rpcs); } @Override boolean _isConstant() { return !_any && _rpcs.size()==1; } @Override boolean _isGLB(boolean mem) { return true; } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 73fecdab..1cabbe32 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -68,6 +68,12 @@ public class TypeStruct extends Type { Field.make("#" ,len , lenAlias,true ,false), Field.make("[]",body,bodyAlias,efinal,false)); } + public TypeStruct makeHigh() { + Field[] fs = new Field[_fields.length]; + for( int i=0; i<_fields.length; i++ ) + fs[i] = _fields[i].makeFrom(Type.TOP); + return make(_name,false,fs); + } public TypeStruct add( Field f ) { assert _open && find(f._fname)==-1; // No double field names diff --git a/chapter24/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter24/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index c1467c07..de6c5a6b 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -1,8 +1,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.node.cpus.arm.arm; -import com.seaofnodes.simple.node.cpus.riscv.riscv; import java.io.IOException; import java.nio.file.Files; import java.nio.file.Path; @@ -18,7 +16,7 @@ public class BrainFuckTest { """ // -*- mode: java; -*- val brain_fuck = { -> - u8[] !program = new u8[106];program[0] = 43;program[1] = 43;program[2] = 43;program[3] = 43;program[4] = 43;program[5] = 43;program[6] = 43;program[7] = 43;program[8] = 91;program[9] = 62;program[10] = 43;program[11] = 43;program[12] = 43;program[13] = 43;program[14] = 91;program[15] = 62;program[16] = 43;program[17] = 43;program[18] = 62;program[19] = 43;program[20] = 43;program[21] = 43;program[22] = 62;program[23] = 43;program[24] = 43;program[25] = 43;program[26] = 62;program[27] = 43;program[28] = 60;program[29] = 60;program[30] = 60;program[31] = 60;program[32] = 45;program[33] = 93;program[34] = 62;program[35] = 43;program[36] = 62;program[37] = 43;program[38] = 62;program[39] = 45;program[40] = 62;program[41] = 62;program[42] = 43;program[43] = 91;program[44] = 60;program[45] = 93;program[46] = 60;program[47] = 45;program[48] = 93;program[49] = 62;program[50] = 62;program[51] = 46;program[52] = 62;program[53] = 45;program[54] = 45;program[55] = 45;program[56] = 46;program[57] = 43;program[58] = 43;program[59] = 43;program[60] = 43;program[61] = 43;program[62] = 43;program[63] = 43;program[64] = 46;program[65] = 46;program[66] = 43;program[67] = 43;program[68] = 43;program[69] = 46;program[70] = 62;program[71] = 62;program[72] = 46;program[73] = 60;program[74] = 45;program[75] = 46;program[76] = 60;program[77] = 46;program[78] = 43;program[79] = 43;program[80] = 43;program[81] = 46;program[82] = 45;program[83] = 45;program[84] = 45;program[85] = 45;program[86] = 45;program[87] = 45;program[88] = 46;program[89] = 45;program[90] = 45;program[91] = 45;program[92] = 45;program[93] = 45;program[94] = 45;program[95] = 45;program[96] = 45;program[97] = 46;program[98] = 62;program[99] = 62;program[100] = 43;program[101] = 46;program[102] = 62;program[103] = 43;program[104] = 43;program[105] = 46; + var !program = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++."; int d = 0; u8[] !output = new u8[0]; u8[] !data = new u8[100]; @@ -68,7 +66,7 @@ val brain_fuck = { -> EvalRisc5 R5 = TestRisc5.build("brain_fuck", src, 0, 28, false); int trap = R5.step(100000); assertEquals(0,trap); - int ptr = (int)R5.regs[riscv.A0]; + int ptr = (int)R5.regs[com.seaofnodes.simple.node.cpus.riscv.riscv.A0]; assertEquals(brain_fuck.length(),R5.ld4s(ptr)); for( int i=0; i int trap_arm = A5.step(100000); assertEquals(0,trap_arm); assertEquals(0,trap); - int ptr_arm = (int)A5.regs[arm.X0]; + int ptr_arm = (int)A5.regs[com.seaofnodes.simple.node.cpus.arm.arm.X0]; assertEquals(brain_fuck.length(),A5.ld4s(ptr_arm)); for( int i=0; i x*x; } : { int x -> x+x; }; return fcn(3); """); code.parse().opto(); - assertEquals("Stop[ return #2; return (Parm_x($fun21,i64,3)*x); return (Parm_x($fun22,i64,3)<<1); ]", code._stop.toString()); + assertEquals("Stop[ return #2; return 9; return 6; ]", code._stop.toString()); assertEquals("6", Eval2.eval(code, 0)); assertEquals("9", Eval2.eval(code, 1)); } @@ -126,7 +126,7 @@ return fcn(3); public void testFcn5() { CodeGen code = new CodeGen("val fact = { int x -> x <= 1 ? 1 : x*fact(x-1); }; return fact(arg);"); code.parse().opto().typeCheck(); - assertEquals("Stop[ return #2; return Phi(Region,1,(Parm_x(fact,i64,arg,(x-1))*#2)); ]", code._stop.toString()); + assertEquals("Stop[ return #2; return Phi(Region,1,(Parm_x(fact,i64)*#2)); ]", code._stop.toString()); assertEquals( "1", Eval2.eval(code, 0)); assertEquals( "1", Eval2.eval(code, 1)); assertEquals( "2", Eval2.eval(code, 2)); @@ -142,7 +142,7 @@ struct S { int i; }; val newS = { int x -> return new S { i=x; }; }; return newS(1).i; """); - code.parse().opto().typeCheck().GCM(); + code.parse().opto().typeCheck(); assertEquals("return 1;", code._stop.toString()); assertEquals("1", Eval2.eval(code, 0)); } @@ -157,8 +157,8 @@ val f = {->1;}; val g = {->2;}; return 2; """); - code.parse().opto().typeCheck().GCM(); - assertEquals("Stop[ return 1; return 1; return 2; ]", code._stop.toString()); + code.parse().opto().typeCheck(); + assertEquals("return 1;", code._stop.toString()); assertEquals("1", Eval2.eval(code, 0)); } @@ -292,7 +292,7 @@ for(;;) { val g = { -> g(); }; -return 0; +return g(); """); try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("No defined return type",e.getMessage()); } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 19d0f501..6d751946 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -391,7 +391,7 @@ val fcn = arg ? { int x -> x*x; } : { int x -> x+x; }; return fcn(2)*10 + fcn(3); """); code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); - assertEquals("Stop[ return (add,#2,(muli,#2)); return (mul,Parm_x($fun21,i64),x); return (shli,Parm_x($fun22,i64)); ]", code.print()); + assertEquals("Stop[ return (add,#2,(muli,#2)); return (mul,Parm_x($fun21,[2-3]),x); return (shli,Parm_x($fun22,[2-3])); ]", code.print()); } @Test diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java index b04ba24c..02de57a2 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -1,12 +1,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.print.ASMPrinter; import java.io.IOException; -import java.nio.file.Files; -import java.nio.file.Path; -import org.junit.Assert; -import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.*; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java index cf6290e4..1d67949a 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java @@ -2,12 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.riscv.riscv; - import java.io.IOException; -import java.nio.file.Files; -import java.nio.file.Path; - -import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; import static org.junit.Assert.*; @@ -514,7 +509,66 @@ return 0 < arg < arg+1 < 4; assertEquals(1,arm.regs[0]); } + // shows that it is parsed as + // ((0 != x) != 2) + @Test + public void testStack12() throws IOException { + String stack11 = "1"; + String src = + """ + var stack12 = { int x -> + 0 != x != 2; + }; + """; + String src2 = + """ + return 0 != arg != 2; + """; + TestC.run(src, "stacked_r_12x", null, stack11,0); + + // Evaluate on RISC5 emulator + EvalRisc5 R5 = TestRisc5.build("stacked_r_12", src2, 1, 0, false); + int trap = R5.step(100); + assertEquals(0,trap); + assertEquals(1,R5.regs[riscv.A0]); + + // Evaluate on ARM emulator + EvalArm64 arm = TestArm64.build("stacked_r_12", src2, 1, 0, false); + trap = arm.step(100); + assertEquals(0,trap); + assertEquals(1,arm.regs[0]); + } + + + // shows that it is parsed as + // ((0 == x) == 1) + @Test + public void testStack13() throws IOException { + String stack12 = "1"; + String src = + """ + var stack13 = { int x -> + 0 == x == 1; + }; + """; + String src2 = + """ + return 0 == arg == 1; + """; + TestC.run(src, "stacked_r_13x", null, stack12,0); + + // Evaluate on RISC5 emulator + 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 + EvalArm64 arm = TestArm64.build("stacked_r_13", src2, 1, 0, false); + trap = arm.step(100); + assertEquals(0,trap); + assertEquals(1,arm.regs[0]); + } @Test public void testFRefFields() { @@ -599,5 +653,37 @@ return s.require('['); testCPU(src,"x86_64_v2", "Win64" ,16,null); }; + @Test + public void testSCCP0() { + String src = +""" +int x = 1; +int cnt = 5; +while (cnt) { + cnt -= 1; + if (x == 0) { + x += 1; + } +} +return x; +"""; + CodeGen code = new CodeGen(src).parse().opto().typeCheck(); + assertEquals("return 1;", code._stop.toString()); + } + + @Test + public void testSCCP1() { + String src = +""" +int x = 1; +int cnt = 5; +while( cnt-- ) + if( x == 1 ) + x = 2-x; +return x; +"""; + CodeGen code = new CodeGen(src).parse().opto().typeCheck(); + assertEquals("return 1;", code._stop.toString()); + } } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter24/src/test/java/com/seaofnodes/simple/Eval2.java index 094b5143..5994e7e1 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Eval2.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Eval2.java @@ -308,14 +308,23 @@ public abstract class Eval2 { case TypeMem mem -> "MEM"; case TypeMemPtr tmp -> { if( tmp._obj.isAry() ) { // Constant array ptr - TypeConAry con = (TypeConAry)tmp._obj.field("[]")._t; - Object[] xs = new Object[con.len()]; - for( int i=0; i null; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/progs/stacked_r_12x.c b/chapter24/src/test/java/com/seaofnodes/simple/progs/stacked_r_12x.c new file mode 100644 index 00000000..a4e425cb --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/progs/stacked_r_12x.c @@ -0,0 +1,13 @@ +#include +#include +#include + +__attribute__ ((CALL_CONV)) +extern int stack12(int x); + +int main() { +int result = stack12(0); + +printf("%d", result); +return 0; +} \ No newline at end of file diff --git a/chapter24/src/test/java/com/seaofnodes/simple/progs/stacked_r_13x.c b/chapter24/src/test/java/com/seaofnodes/simple/progs/stacked_r_13x.c new file mode 100644 index 00000000..a3a51d0e --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/progs/stacked_r_13x.c @@ -0,0 +1,13 @@ +#include +#include +#include + +__attribute__ ((CALL_CONV)) +extern int stack13(int x); + +int main() { +int result = stack13(0); + +printf("%d", result); +return 0; +} \ No newline at end of file -- cgit v1.2.3