diff options
Diffstat (limited to 'src/main/java')
87 files changed, 2995 insertions, 535 deletions
diff --git a/src/main/java/com/seaofnodes/simple/ASMPrinter.java b/src/main/java/com/seaofnodes/simple/ASMPrinter.java new file mode 100644 index 00000000..5cc13210 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/ASMPrinter.java @@ -0,0 +1,140 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.type.TypeFunPtr; +import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.type.TypeRPC; + +public abstract class ASMPrinter { + + public static SB print(SB sb, CodeGen code) { + if( code._cfg==null ) + return sb.p("Need _cfg set, run after GCM"); + + // instruction address + int iadr = 0; + for( int i=0; i<code._cfg._len; i++ ) + if( code._cfg.at(i) instanceof FunNode fun ) + iadr = print(iadr,sb,code,fun,i); + return sb; + } + + private static int print(int iadr, SB sb, CodeGen code, FunNode fun, int cfgidx) { + // Function header + sb.nl().p("---"); + fun.sig().print(sb); + sb.p("---------------------------").nl(); + + + while( !(code._cfg.at(cfgidx) instanceof ReturnNode) ) + iadr = doBlock(iadr,sb,code,fun,cfgidx++); + + // Function separator + sb.p("---"); + fun.sig().print(sb); + sb.p("---------------------------").nl(); + return iadr; + } + + static int doBlock(int iadr, SB sb, CodeGen code, FunNode fun, int cfgidx) { + CFGNode bb = code._cfg.at(cfgidx); + if( bb != fun && !(bb instanceof IfNode) && !(bb instanceof CallEndNode) && !(bb instanceof CallNode) && !(bb instanceof CProjNode && bb.in(0) instanceof CallEndNode )) + sb.p("L").p(bb._nid).p(":").nl(); + + if( !(bb instanceof CallNode) ) + for( Node n : bb._outputs ) + iadr = doInst(iadr, sb,code,fun,bb,n); + + return iadr; + } + + static int doInst(int iadr, SB sb, CodeGen code, FunNode fun, CFGNode bb, Node n) { + final int encWidth = 8; + final int opWidth = 5; + final int argWidth = 30; + + if( n instanceof CProjNode ) return iadr; + + // Phis are useful before (and during) reg alloc + if( n instanceof PhiNode phi ) { + if( phi._type instanceof TypeMem || phi._type instanceof TypeRPC ) return iadr; // Nothing for the hidden ones + sb.fix(4," ").p(" ").fix(encWidth,"").p(" ").fix(opWidth,phi._label).p(" "); + sb.p(code.reg(n)); + if( !(n instanceof ParmNode) ) { + sb.p(" = phi( "); + for( int i=1; i<n.nIns(); i++ ) + sb.p("N").p(n.in(i)._nid).p(","); + sb.unchar().p(" )"); + } + sb.nl(); + return iadr; + } + + // All blocks ending in a Region will need to either fall into or jump + // to this block. Until the post-reg-alloc block layout cleanup, we + // need to assume a jump. There's no real hardware op here, yet. + if( n instanceof RegionNode && !(n instanceof FunNode) ) { + sb.hex4(iadr++).p(" ").fix(encWidth,"??").p(" ").fix(opWidth,"JMP").p(" ").fix(argWidth,"L"+n._nid).nl(); + return iadr; + } + + // ProjNodes following a multi (e.g. Call or New results), + // get indent slightly and just print their index & node# + if( n instanceof ProjNode proj ) { + if( proj._type instanceof TypeMem ) return iadr; // Nothing for the hidden ones + sb.fix(4," ").p(" ").fix(encWidth,"").p(" ").fix(opWidth,proj._label==null ? "---" : proj._label).p(" ").p(code.reg(n)).nl(); + return iadr; + } + + // ADDR ENCODING Op--- dst = src op src // Comment + // 1234 abcdefgh ld4 RAX = [Rbase + off] // Comment + sb.hex4(iadr); + sb.p(" "); + + // Encoding + int size = 1; // TODO: Fake encoding size + iadr += size; + sb.fix(encWidth,"??"); + sb.p(" "); + + // Op; generally "ld4" or "call" + sb.fix(opWidth, n instanceof MachNode mach ? mach.op() : n.label()); + sb.p(" "); + + // General asm args + if( n instanceof MachNode mach ) { + int old = sb.len(); + mach.asm(code,sb); + sb.fix(argWidth-(sb.len()-old),""); // Pad out + + } else if( !(n._type instanceof TypeMem) ) { + // Room for some inputs + sb.fix(5, n._nid+":" ); + int off = 0; + for( int i=0; i<n.nIns(); i++ ) { + sb.fix(5, n.in(i) == null ? "___" : String.valueOf(n.in(i)._nid)); + off += 5; + if( off >= argWidth ) break; + } + if( off < argWidth ) sb.fix(argWidth-off,""); + } + sb.p(" "); + + // Comment + String comment = n.comment(); + if( comment!=null ) sb.p("// ").p(comment); + + sb.nl(); + + // MultiNodes are immediately followed by projection(s) + if( !(n instanceof CFGNode) && n instanceof MultiNode ) { + for( Node proj : n._outputs ) { + assert proj instanceof ProjNode; + doInst(iadr,sb,code,fun,bb,proj); + } + } + + return iadr; + } +} diff --git a/src/main/java/com/seaofnodes/simple/Ary.java b/src/main/java/com/seaofnodes/simple/Ary.java index b5184948..73ada8e0 100644 --- a/src/main/java/com/seaofnodes/simple/Ary.java +++ b/src/main/java/com/seaofnodes/simple/Ary.java @@ -42,8 +42,7 @@ public class Ary<E> extends AbstractList<E> implements List<E> { } /** @return remove and return last element */ public E pop( ) { - range_check(0); - return _es[--_len]; + return _len==0 ? null : _es[--_len]; } @Override public E removeLast() { return pop(); } @@ -93,6 +92,22 @@ public class Ary<E> extends AbstractList<E> implements List<E> { return old; } + /** Set existing element + * @param i element to set + * @param e value to set + * @return old value + * @exception AIOOBE if !(0 <= i < _len) + */ + public E setX( int i, E e ) { + if( i >= _len ) { + while( i >= _es.length ) _es = Arrays.copyOf( _es, _es.length << 1 ); + _len = i+1; + } + E old = _es[i]; + _es[i] = e; + return old; + } + public Ary<E> setLen( int len ) { if( len > _len ) while( len>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); @@ -103,13 +118,14 @@ public class Ary<E> extends AbstractList<E> implements List<E> { return this; } - public void swap( int i, int j ) { + public E swap( int i, int j ) { range_check(i); range_check(j); - if( i==j ) return; E tmp = _es[i]; + if( i==j ) return tmp; _es[i] = _es[j]; _es[j] = tmp; + return tmp; } @@ -139,12 +155,12 @@ public class Ary<E> extends AbstractList<E> implements List<E> { return this; } - /** @return compact array version */ - public E[] asAry() { return Arrays.copyOf(_es,_len); } + /** @return compact array version */ + public E[] asAry() { return Arrays.copyOf(_es,_len); } - /** Sorts in-place - * @param c Comparator to sort by */ - public void sort_update(Comparator<? super E> c ) { Arrays.sort(_es, 0, _len, c); } + /** Sorts in-place + * @param c Comparator to sort by */ + public void sort_update(Comparator<? super E> c ) { Arrays.sort(_es, 0, _len, c); } /** Find the first matching element using ==, or -1 if none. Note that * most del calls shuffle the list, so the first element might be random. diff --git a/src/main/java/com/seaofnodes/simple/CodeGen.java b/src/main/java/com/seaofnodes/simple/CodeGen.java index 47616b51..c48a4162 100644 --- a/src/main/java/com/seaofnodes/simple/CodeGen.java +++ b/src/main/java/com/seaofnodes/simple/CodeGen.java @@ -1,72 +1,160 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.cpus.x86_64_v2.MemOpX86; import com.seaofnodes.simple.type.*; +import java.util.BitSet; import java.util.HashMap; +import java.util.IdentityHashMap; public class CodeGen { + // Last created CodeGen as a global; used all over to avoid passing about a + // "context". + public static CodeGen CODE; public enum Phase { - Parse, Opto, TypeCheck, Schedule, LocalSched, RegAlloc; + Parse, // Parse ASCII text into Sea-of-Nodes IR + Opto, // Run ideal optimizations + TypeCheck, // Last check for bad programs + InstructionSelection, // Convert to target hardware nodes + Schedule, // Global schedule (code motion) nodes + LocalSched, // Local schedule + RegAlloc; // Register allocation + } + public enum CallingConv { + Win64, + SystemV } public Phase _phase; + // --------------------------- + // Compilation source code public final String _src; // Compile-time known initial argument type public final TypeInteger _arg; + public CallingConv _callingConv; + + // --------------------------- + public CodeGen( String src ) { this(src, TypeInteger.BOT, 123L ); } + public CodeGen( String src, TypeInteger arg, long workListSeed ) { + CODE = this; + _phase = null; + _callingConv = null; + _start = new StartNode(arg); + _stop = new StopNode(src); + _src = src; + _arg = arg; + _iter = new IterPeeps(workListSeed); + P = new Parser(this,arg); + } + + + // --------------------------- + /** + * A counter, for unique node id generation. Starting with value 1, to + * avoid bugs confusing node ID 0 with uninitialized values. + */ + private int _uid = 1; + public int UID() { return _uid; } + public int getUID() { return _uid++; } + + // Next available memory alias number + private int _alias = 2; // 0 is for control, 1 for memory + public int getALIAS() { return _alias++; } + - public Parser P; + // Popular visit bitset, declared here, so it gets reused all over + public final BitSet _visit = new BitSet(); + public BitSet visit() { assert _visit.isEmpty(); return _visit; } + + // Start and stop; end points of the generated IR public StartNode _start; - public StopNode _stop ; + public StopNode _stop; + // Global Value Numbering. Hash over opcode and inputs; hits in this table + // are structurally equal. + public final HashMap<Node,Node> _gvn = new HashMap<>(); + + // Compute "function indices": FIDX. + // Each new request at the same signature gets a new FIDX. + private final HashMap<TypeTuple,Integer> FIDXS = new HashMap<>(); + public TypeFunPtr makeFun( TypeTuple sig, Type ret ) { + Integer i = FIDXS.get(sig); + int fidx = i==null ? 0 : i; + FIDXS.put(sig,fidx+1); // Track count per sig + assert fidx<64; // TODO: need a larger FIDX space + return TypeFunPtr.make((byte)2,sig,ret, 1L<<fidx ); + } + // Signature for MAIN + public TypeFunPtr _main = makeFun(TypeTuple.MAIN,Type.BOTTOM); + // Reverse from a constant function pointer to the IR function being called + public FunNode link( TypeFunPtr tfp ) { + assert tfp.isConstant(); + return _linker.get(tfp.makeFrom(Type.BOTTOM)); + } + + // 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); + } // "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<TypeFunPtr,FunNode> _linker = new HashMap<>(); + // Parser object + public final Parser P; - // Last created CodeGen as a global, for easier debugging prints - public static CodeGen CODE; - - CodeGen( String src, TypeInteger arg ) { _phase = null; _src = src; _arg=arg; CODE=this; } - public CodeGen( String src ) { this(src,TypeInteger.BOT); } - - public CodeGen parse() { return parse(false); } - public CodeGen parse(boolean disable) { + // Parse ASCII text into Sea-of-Nodes IR + public CodeGen parse() { assert _phase == null; _phase = Phase.Parse; - _linker.clear(); - P = new Parser(_src,_arg); - Node._disablePeephole = disable; - _stop = P.parse(); - _start = Parser.START; // Capture global start + P.parse(); JSViewer.show(); - P = null; // No longer parsing return this; } + + // --------------------------- + // Iterator peepholes. + public final IterPeeps _iter; + // Stop tracking deps while assertin + public boolean _midAssert; + // Statistics on peepholes + public int _iter_cnt, _iter_nop_cnt; + // Stat gathering + public void iterCnt() { if( !_midAssert ) _iter_cnt++; } + public void iterNop() { if( !_midAssert ) _iter_nop_cnt++; } + + // Run ideal optimizations public CodeGen opto() { assert _phase == Phase.Parse; _phase = Phase.Opto; - // Optimization - IterPeeps.iterate(_stop); + // Pessimistic peephole optimization on a worklist + _iter.iterate(this); // TODO: // Optimistic + // TODO: + // loop unroll, peel, RCE, etc return this; } + public <N extends Node> N add( N n ) { return (N)_iter.add(n); } + public void addAll( Ary<Node> ary ) { _iter.addAll(ary); } + + // --------------------------- + // Last check for bad programs public CodeGen typeCheck() { // Demand phase Opto for cleaning up dead control flow at least, - // required for the following GCM. Note that peeps can be disabled, - // but still the dead CFG will get cleaned. - assert _phase == Phase.Opto; + // required for the following GCM. + assert _phase.ordinal() <= Phase.Opto.ordinal(); _phase = Phase.TypeCheck; - // Type check Parser.ParseException err = _stop.walk( Node::err ); if( err != null ) throw err; @@ -74,22 +162,98 @@ public class CodeGen { } + // --------------------------- + // Code generation CPU target + public Machine _mach; + + // Convert to target hardware nodes + public CodeGen instSelect( String cpu, String callingConv ) { + assert _phase.ordinal() <= Phase.TypeCheck.ordinal(); + _phase = Phase.InstructionSelection; + + _callingConv = switch(callingConv) { + case "SystemV" -> CallingConv.SystemV; + case "Win64" -> CallingConv.Win64; + default -> throw Utils.TODO(); // Unknown calling convention + }; + + // Look for CPU in fixed named place: + // com.seaofnodes.simple.node.cpus."cpu"."cpu.class" + String clzFile = "com.seaofnodes.simple.node.cpus."+cpu+"."+cpu; + try { _mach = ((Class<Machine>) Class.forName( clzFile )).getDeclaredConstructor().newInstance(); } + catch( Exception e ) { throw new RuntimeException(e); } + + // Convert to machine ops + _uid = 1; // All new machine nodes reset numbering + var map = new IdentityHashMap<Node,Node>(); + _instSelect( _stop, map ); + _stop = ( StopNode)map.get(_stop ); + _start = (StartNode)map.get(_start); + _instOuts(_stop,visit()); + _visit.clear(); + return this; + } + + // Walk all ideal nodes, recursively mapping ideal to machine nodes, then + // make a machine node for "this". + private Node _instSelect( Node n, IdentityHashMap<Node,Node> map ) { + if( n==null ) return null; + Node x = map.get(n); + if( x !=null ) return x; // Been there, done that + + // If n is a MachConcrete, then its part of a multi-node expansion. + // It does not need instruction selection (already selected!) + // but it does need its inputs walked. + if( n instanceof MachConcreteNode || n instanceof MemOpX86 ) { + for( int i=0; i < n.nIns(); i++ ) + n._inputs.set(i, _instSelect(n.in(i),map) ); + return n; + } + + // Produce a machine node from n; map it to flag as done so stops cycles. + map.put(n, x=_mach.instSelect(n) ); + // Walk machine op and replace inputs with mapped inputs + for( int i=0; i < x.nIns(); i++ ) + x._inputs.set(i, _instSelect(x.in(i),map) ); + if( x instanceof MachNode mach ) + mach.postSelect(); // Post selection action + + // Updates forward edges only. + n._outputs.clear(); + return x; + } + + // Walk all machine Nodes, and set their output edges + private void _instOuts( Node n, BitSet visit ) { + if( visit.get(n._nid) ) return; + visit.set(n._nid); + for( Node in : n._inputs ) + if( in!=null ) { + in._outputs.push(n); + _instOuts(in,visit); + } + } + + + // --------------------------- + // Control Flow Graph in RPO order. + Ary<CFGNode> _cfg = new Ary<>(CFGNode.class); + + // Global schedule (code motion) nodes public CodeGen GCM() { return GCM(false); } public CodeGen GCM( boolean show) { - assert _phase == Phase.TypeCheck; + assert _phase.ordinal() <= Phase.InstructionSelection.ordinal(); _phase = Phase.Schedule; // Build the loop tree, fix never-exit loops _start.buildLoopTree(_stop); + GlobalCodeMotion.buildCFG(this); if( show ) System.out.println(new GraphVisualizer().generateDotOutput(_stop,null,null)); - - // TODO: - // loop unroll, peel, RCE, etc - GlobalCodeMotion.buildCFG(_start,_stop); return this; } + // --------------------------- // Local (basic block) scheduler phase, a classic list scheduler public CodeGen localSched() { assert _phase == Phase.Schedule; @@ -98,25 +262,26 @@ public class CodeGen { return this; } - // Reverse from a constant function pointer to the IR function being called - public FunNode link( TypeFunPtr tfp ) { - assert tfp.isConstant(); - return _linker.get(tfp.makeFrom(Type.BOTTOM)); - } - public void link(FunNode fun) { - _linker.put(fun.sig().makeFrom(Type.BOTTOM),fun); + // --------------------------- + public String reg(Node n) { + if( _phase == Phase.RegAlloc ) throw Utils.TODO(); + return "N"+ n._nid; } + + // --------------------------- + SB asm(SB sb) { return ASMPrinter.print(sb,this); } + String asm() { return asm(new SB()).toString(); } + + // Testing shortcuts Node ctrl() { return _stop.ret().ctrl(); } Node expr() { return _stop.ret().expr(); } String print() { return _stop.print(); } // Debugging helper - @Override public String toString() { - return _stop.p(9999); - } + @Override public String toString() { return _stop.p(9999); } // Debugging helper public Node f(int idx) { return _stop.find(idx); } diff --git a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index d3ee62c3..12dd9243 100644 --- a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -10,46 +10,54 @@ public abstract class GlobalCodeMotion { // Arrange that the existing isCFG() Nodes form a valid CFG. The // Node.use(0) is always a block tail (either IfNode or head of the // following block). There are no unreachable infinite loops. - public static void buildCFG( StartNode start, StopNode stop ) { - schedEarly(start); - schedLate(stop); + public static void buildCFG( CodeGen code ) { + Ary<CFGNode> rpo = new Ary<>(CFGNode.class); + _rpo_cfg(null, code._start, code.visit(), rpo); + // Reverse in-place + for( int i=0; i< rpo.size()>>1; i++ ) { + int j = rpo.size()-1-i; + CFGNode tmp = rpo.get(i); + rpo.set(i, rpo.get(j)); + rpo.set(j, tmp); + } + // Set global CFG + code._cfg = rpo; + + schedEarly(code); + code._visit.clear(); + schedLate (code); } + // Post-Order of CFG + private static void _rpo_cfg(CFGNode def, Node use, BitSet visit, Ary<CFGNode> rpo) { + if( !(use instanceof CFGNode cfg) || visit.get(cfg._nid) ) + return; // Been there, done that + if( def instanceof CallNode && cfg instanceof FunNode ) + return; // Ignore linked function calls + visit.set(cfg._nid); + for( Node useuse : cfg._outputs ) + _rpo_cfg(cfg,useuse,visit,rpo); + rpo.add(cfg); + } // ------------------------------------------------------------------------ // Visit all nodes in CFG Reverse Post-Order, essentially defs before uses // (except at loops). Since defs are visited first - and hoisted as early // as possible, when we come to a use we place it just after its deepest // input. - private static void schedEarly(StartNode start) { - ArrayList<CFGNode> rpo = new ArrayList<>(); - BitSet visit = new BitSet(); - _rpo_cfg(null, start, visit, rpo); + private static void schedEarly(CodeGen code) { // Reverse Post-Order on CFG - for( int j=rpo.size()-1; j>=0; j-- ) { - CFGNode cfg = rpo.get(j); + for( CFGNode cfg : code._cfg ) { cfg.loopDepth(); for( Node n : cfg._inputs ) - _schedEarly(n,visit); + _schedEarly(n,code._visit ); if( cfg instanceof RegionNode ) for( Node phi : cfg._outputs ) if( phi instanceof PhiNode ) - _schedEarly(phi,visit); + _schedEarly(phi,code._visit ); } } - // Post-Order of CFG - private static void _rpo_cfg(CFGNode def, Node use, BitSet visit, ArrayList<CFGNode> rpo) { - if( !(use instanceof CFGNode cfg) || visit.get(cfg._nid) ) - return; // Been there, done that - if( def instanceof CallNode && cfg instanceof FunNode ) - return; // Ignore linked function calls - visit.set(cfg._nid); - for( Node useuse : cfg._outputs ) - _rpo_cfg(cfg,useuse,visit,rpo); - rpo.add(cfg); - } - private static void _schedEarly(Node n, BitSet visit) { if( n==null || visit.get(n._nid) ) return; // Been there, done that assert !(n instanceof CFGNode); @@ -61,24 +69,25 @@ public abstract class GlobalCodeMotion { for( Node def : n._inputs ) if( def!=null && !(def instanceof PhiNode) ) _schedEarly(def,visit); + // If not-pinned (e.g. constants, projections, phi) and not-CFG if( !n.isPinned() ) { // Schedule at deepest input - CFGNode early = Parser.START; // Maximally early, lowest idepth + CFGNode early = CodeGen.CODE._start; // Maximally early, lowest idepth if( n.in(0) instanceof CFGNode cfg ) early = cfg; for( int i=1; i<n.nIns(); i++ ) if( n.in(i)!=null && n.in(i).cfg0().idepth() > early.idepth() ) early = n.in(i).cfg0(); // Latest/deepest input - n.setDef(0,early); // First place this can go + n.setDef(0,early); } } // ------------------------------------------------------------------------ - private static void schedLate( StopNode stop) { - CFGNode[] late = new CFGNode[Node.UID()]; - Node[] ns = new Node[Node.UID()]; + private static void schedLate( CodeGen code ) { + CFGNode[] late = new CFGNode[code.UID()]; + Node[] ns = new Node[code.UID()]; // Breadth-first scheduling - breadth(stop,ns,late); + breadth(code._stop,ns,late); // Copy the best placement choice into the control slot for( int i=0; i<late.length; i++ ) diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 5d6d3328..30e25916 100644 --- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -22,7 +22,7 @@ public class GraphVisualizer { public GraphVisualizer(boolean separateControlCluster) { this._separateControlCluster = separateControlCluster; } public GraphVisualizer() { this(false); } - public String generateDotOutput(Parser parse) { return generateDotOutput(parse.STOP,parse._scope,parse._xScopes); } + public String generateDotOutput(Parser parse) { return generateDotOutput(parse._code._stop,parse._scope,parse._xScopes); } public String generateDotOutput(StopNode stop, Node scope, Stack<ScopeNode> xScopes) { // Since the graph has cycles, we need to create a flat list of all the diff --git a/src/main/java/com/seaofnodes/simple/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java index aa498b16..3cddacfd 100644 --- a/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -6,7 +6,7 @@ import java.util.ArrayList; import java.util.BitSet; import java.util.HashMap; -public class IRPrinter { +public abstract class IRPrinter { // Print a node on 1 line, columnar aligned, as: // NNID NNAME DDEF DDEF [[ UUSE UUSE ]] TYPE @@ -55,10 +55,8 @@ public class IRPrinter { Node n = rpos.get(i); if( n instanceof CFGNode || n.isMultiHead() ) { if( !gap ) sb.p("\n"); // Blank before multihead - if( n instanceof FunNode fun ) { - TypeFunPtr sig = fun.sig(); - sig.print(sb.p("--- ").p(sig._name==null ? "" : sig._name).p(" "),false).p("----------------------\n"); - } + if( n instanceof FunNode fun ) + fun.sig().print(sb.p("--- ").p(fun._name==null ? "" : fun._name).p(" "),false).p("----------------------\n"); printLine( n, sb ); // Print head while( --i >= 0 ) { Node t = rpos.get(i); @@ -66,8 +64,8 @@ public class IRPrinter { printLine( t, sb ); } if( n instanceof ReturnNode ret ) { - TypeFunPtr sig = ret.fun().sig(); - sig.print(sb.p("--- ").p(sig._name==null ? "" : sig._name).p(" "),false).p("----------------------\n"); + FunNode fun = ret.fun(); + fun.sig().print(sb.p("--- ").p(fun._name==null ? "" : fun._name).p(" "),false).p("----------------------\n"); } if( !(n instanceof CallNode) ) { sb.p("\n"); // Blank after multitail @@ -176,12 +174,12 @@ public class IRPrinter { private static String _prettyPrintScheduled( Node node, int depth ) { // Backwards DFS walk to depth. HashMap<Integer,Integer> ds = new HashMap<>(); - ArrayList<Node> ns = new ArrayList<>(); + Ary<Node> ns = new Ary<>(Node.class); _walk(ds,ns,node,depth); // Remove data projections, these are force-printed behind their multinode head for( int i=0; i<ns.size(); i++ ) { if( ns.get(i) instanceof ProjNode proj && !(proj.in(0) instanceof CFGNode) ) { - Utils.del(ns,i--); + ns.del(i--); ds.remove(proj._nid); } } @@ -192,11 +190,11 @@ public class IRPrinter { CFGNode blk = null; for( Node n : ns ) { CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : n.cfg0(); - if( blk==null || cfg.idepth() < blk.idepth() || (blk instanceof FunNode && !(cfg instanceof FunNode))) + if( blk==null || cfg.idepth() < blk.idepth() ) blk = cfg; } Integer d = ds.remove(blk._nid); - ns.remove(blk); + ns.del(ns.find(blk)); // Print block header sb.p("%-13.13s".formatted(label(blk)+":")); @@ -244,7 +242,7 @@ public class IRPrinter { return sb.toString(); } - private static void _walk( HashMap<Integer,Integer> ds, ArrayList<Node> ns, Node node, int d ) { + private static void _walk( HashMap<Integer,Integer> ds, Ary<Node> ns, Node node, int d ) { Integer nd = ds.get(node._nid); if( nd!=null && d <= nd ) return; // Been there, done that Integer old = ds.put(node._nid,d) ; @@ -270,11 +268,12 @@ public class IRPrinter { if( !blk.blockHead() ) blk = blk.cfg(0); sb.p( "%-9.9s ".formatted( label( blk ) ) ); } - static void printLine( Node n, SB sb, Ary<Node> bns, int i, HashMap<Integer,Integer> ds, ArrayList<Node> ns ) { + static void printLine( Node n, SB sb, Ary<Node> bns, int i, HashMap<Integer,Integer> ds, Ary<Node> ns ) { printLine( n, sb ); if( i != -1 ) bns.del(i); ds.remove(n._nid); - ns.remove(n); + int idx = ns.find(n); + if( idx!=-1 ) ns.del(idx); } } diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java index 998bd4f0..265e0b21 100644 --- a/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -42,27 +42,25 @@ import java.util.Random; * progressOnList(stop);`</li> * </ul> */ -public abstract class IterPeeps { +public class IterPeeps { - private static final WorkList<Node> WORK = new WorkList<>(); + private final WorkList<Node> _work; - public static <N extends Node> N add( N n ) { - return (N)WORK.push(n); - } + IterPeeps( long seed ) { _work = new WorkList<>(seed); } - public static void addAll( Ary<Node> ary ) { - WORK.addAll(ary); - } + public <N extends Node> N add( N n ) { return (N)_work.push(n); } + + public void addAll( Ary<Node> ary ) { _work.addAll(ary); } /** * Iterate peepholes to a fixed point */ - public static void iterate( StopNode stop) { - assert progressOnList(stop); + public void iterate( CodeGen code ) { + assert progressOnList(code); int cnt=0; Node n; - while( (n=WORK.pop()) != null ) { + while( (n=_work.pop()) != null ) { if( n.isDead() ) continue; cnt++; // Useful for debugging, searching which peephole broke things Node x = n.peepholeOpt(); @@ -73,21 +71,21 @@ public abstract class IterPeeps { // Changes require neighbors onto the worklist if( x != n || !(x instanceof ConstantNode) ) { // All outputs of n (changing node) not x (prior existing node). - for( Node z : n._outputs ) WORK.push(z); + for( Node z : n._outputs ) _work.push(z); // Everybody gets a free "go again" in case they didn't get // made in their final form. - WORK.push(x); + _work.push(x); // If the result is not self, revisit all inputs (because // there's a new user), and replace in the graph. if( x != n ) { - for( Node z : n. _inputs ) WORK.push(z); + for( Node z : n. _inputs ) _work.push(z); n.subsume(x); } } // If there are distant neighbors, move to worklist n.moveDepsToWorklist(); JSViewer.show(); // Show again - assert progressOnList(stop); // Very expensive assert + assert progressOnList(code); // Very expensive assert } if( n.isUnused() && !(n instanceof StopNode) ) n.kill(); // Just plain dead @@ -96,7 +94,7 @@ public abstract class IterPeeps { } // Visit ALL nodes and confirm the invariant: - // Either you are on the WORK worklist OR running `iter()` makes no progress. + // Either you are on the _work worklist OR running `iter()` makes no progress. // This invariant ensures that no progress is missed, i.e., when the // worklist is empty we have indeed done all that can be done. To help @@ -107,30 +105,22 @@ public abstract 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 static boolean MID_ASSERT; - public static boolean midAssert() { return MID_ASSERT; } - private static boolean progressOnList(Node stop) { - MID_ASSERT = true; - int old_cnt = Node.ITER_CNT, old_nop = Node.ITER_NOP_CNT; - Node changed = stop.walk( n -> { + private boolean progressOnList(CodeGen code) { + 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; + if( _work.on(n) ) return null; m = n.peepholeOpt(); if( m==null ) return null; } System.err.println("BREAK HERE FOR BUG"); return m; }); - Node.ITER_CNT = old_cnt; Node.ITER_NOP_CNT = old_nop; - MID_ASSERT = false; + code._midAssert = false; return changed==null; } - public static void reset() { - WORK.clear(); - } - /** * Classic WorkList, with a fast add/remove, dup removal, random pull. * The Node's nid is used to check membership in the worklist. diff --git a/src/main/java/com/seaofnodes/simple/JSViewer.java b/src/main/java/com/seaofnodes/simple/JSViewer.java index 7422767a..fcb0c28a 100644 --- a/src/main/java/com/seaofnodes/simple/JSViewer.java +++ b/src/main/java/com/seaofnodes/simple/JSViewer.java @@ -6,6 +6,7 @@ import java.io.IOException; import java.util.Stack; import java.nio.file.Paths; import java.util.Collection; +import static com.seaofnodes.simple.CodeGen.CODE; public class JSViewer implements AutoCloseable { // Display programs in an endless loop @@ -21,7 +22,6 @@ public class JSViewer implements AutoCloseable { static SimpleWebSocket SERVER; static int N; // Dot frames - static CodeGen CODE; // JSViewer() throws Exception { // Launch server; handshake @@ -41,13 +41,13 @@ public class JSViewer implements AutoCloseable { try { N=0; // Use parser scope, xscope when building views - CODE = new CodeGen(src); + CodeGen code = new CodeGen(src); SHOW = true; show(); // Parse program, generating views at every parse point - CODE.parse(); + code.parse(); // No longer user parse internal state when building views - CODE.opto(); + code.opto(); // Catch and ignore Parser errors } catch(RuntimeException re) { @@ -68,10 +68,10 @@ public class JSViewer implements AutoCloseable { public static void show() { if( SERVER!=null && SHOW ) _show(); } private static void _show() { - boolean midParse = CODE.P!=null; // Skip util we at least get the Parse object made - if( !midParse && (CODE._phase==null || CODE._phase == CodeGen.Phase.Parse) ) + if( CODE._phase==null || CODE._phase.ordinal() < CodeGen.Phase.Parse.ordinal() ) return; + boolean midParse = CODE._phase == CodeGen.Phase.Parse; Stack<ScopeNode> xScopes = midParse ? CODE.P._xScopes : null; Collection<Node> all = GraphVisualizer.findAll(xScopes, CODE._stop, midParse ? CODE.P._scope: null); @@ -149,11 +149,13 @@ public class JSViewer implements AutoCloseable { sb.i().p("<TR>"); n._outputs.sort((x,y) -> x instanceof ProjNode xp && y instanceof ProjNode yp ? (xp._idx - yp._idx) : ((x==null ? 99999 : x._nid) - (y==null ? 99999 : y._nid))); boolean empty_row=true; - for( Node use : n._outputs ) - if( use instanceof MultiUse muse ) { - cell(sb,use.glabel(),use,"p"+muse.idx()); + for( Node use : n._outputs ) { + int idx = idx(n); + if( idx != -1 ) { + cell(sb,use.glabel(),use,"p"+idx); empty_row=false; } + } // At least one cell on row if( empty_row ) sb.p("<TD></TD>"); sb. p("</TR>").p("\n"); @@ -386,9 +388,15 @@ public class JSViewer implements AutoCloseable { } + // (C)Projection index or -1 + private static int idx(Node n) { + return n instanceof ProjNode p ? p._idx : (n instanceof CProjNode cp ? cp._idx : -1); + } + private static SB defPort(SB sb, Node def) { - return def instanceof MultiUse muse - ? sb.p(def.in(0).uniqueName()).p(":p").p(muse.idx()) + int idx = idx(def); + return idx != -1 + ? sb.p(def.in(0).uniqueName()).p(":p").p(idx) : sb.p(def.uniqueName()); } } diff --git a/src/main/java/com/seaofnodes/simple/ListScheduler.java b/src/main/java/com/seaofnodes/simple/ListScheduler.java index 252a8f8e..18055e19 100644 --- a/src/main/java/com/seaofnodes/simple/ListScheduler.java +++ b/src/main/java/com/seaofnodes/simple/ListScheduler.java @@ -7,91 +7,157 @@ import java.util.*; public abstract class ListScheduler { - private static final BitSet VISIT = new BitSet(); - private static int[] BCNTS; - public static void sched( CodeGen code ) { - assert VISIT.isEmpty(); - BCNTS = new int[Node.UID()]; - walk(code._start,VISIT); - VISIT.clear(); - } + // eXtra per-node stuff for scheduling. + private static final IdentityHashMap<Node,XSched> XS = new IdentityHashMap<>(); + private static class XSched { + static final Ary<XSched> FREE = new Ary<>(XSched.class); + static void alloc(CFGNode bb, Node n) { + XSched x = FREE.pop(); + XS.put(n, (x==null ? new XSched() : x).init(bb,n)); + } + void free() { _n = null; FREE.push(this); } - // Visit all CFG nodes - static void walk( CFGNode cfg, BitSet visit ) { - if( visit.get(cfg._nid) ) return; - visit.set(cfg._nid); - local(cfg); - for( Node n : cfg._outputs ) - if( n instanceof CFGNode c ) - walk(c,visit); - } + static XSched get(Node n) { return n==null ? null : XS.get(n); } - // Local schedule this one CFG - static void local( CFGNode bb ) { - if( !bb.blockHead() || bb instanceof StopNode ) return; - Node[] uses = bb._outputs._es; - int ulen = bb._outputs._len; - - // Count block-locals - for( int i=0; i<ulen; i++ ) { - Node use = uses[i]; - if( use.in(0)==bb && !(use instanceof PhiNode) ) { - // Normal basic block member: in(0)==bb and not a Phi - for( Node def : use._inputs ) - // Has defs from same block? Then block-local inputs - if( def != null && def.cfg0()==bb ) // Same block? - BCNTS[use._nid]++; // Raise block-local input count + private XSched init(CFGNode bb, Node n) { + _n = n; + _bcnt = 0; + _ruse = _rdef = _single = false; + + // Count block-locals and remote inputs + if( !(n instanceof PhiNode) ) + for( Node def : n._inputs ) + if( def != null && def != bb ) { + if( def.cfg0()==bb ) _bcnt++; // Raise block-local input count + else _ruse = true; + } + // Count remote outputs and allowed registers + if( n instanceof MultiNode ) + for( Node use : n._inputs ) + computeSingleRDef(bb,use); + else + computeSingleRDef(bb,n); + return this; + } + + private void computeSingleRDef(CFGNode bb, Node n) { + RegMaskRW rmask = n instanceof MachNode mach ? mach.outregmap().copy() : null; + for( Node use : n._outputs ) { + // Remote use, so this is a remote def + if( use!=null && use.cfg0()!=bb ) _rdef = true; + // And mask between n's def mask and all n's users masks' + if( use instanceof MachNode mach && rmask != null ) + for( int i=1; i<use.nIns(); i++ ) + if( use.in(i)==n ) + rmask.and(mach.regmap(i)); } + // Defines in a single register + _single = rmask!=null && rmask.size1(); + } + + // If _bcnt==0, declare ready; move user bcnts into rcnts. + boolean isReady() { + if( _bcnt > 0 || _rcnt > 0 ) return false; + if( _n instanceof MultiNode ) + for( Node use : _n._outputs ) + if( use instanceof ProjNode ) readyUp(use); + // anti-dep from a multireg directly + else _readyUp(use); + else + readyUp(_n); + return true; + } + private static void readyUp(Node n) { + for( Node use : n._outputs ) + _readyUp(use); + } + private static void _readyUp(Node use) { + XSched xs = get(use); + if( xs!=null && !(use instanceof PhiNode) ) + { assert xs._bcnt>0; xs._bcnt--; xs._rcnt++; } + } + + boolean decIsReady() { + assert _rcnt > 0; + _rcnt--; + return isReady(); } + Node _n; // Node this extra is for + int _bcnt; // Not-ready not-scheduled inputs + int _rcnt; // Ready not-scheduled inputs + boolean _ruse; // Node IS a "remote use", uses a other-block value + boolean _rdef; // Node IS a "remote def" of a value used in other block + boolean _single; // Defines a single register, likely to conflict + } + + + // List schedule every block + public static void sched( CodeGen code ) { + XS.clear(); + for( CFGNode bb : code._cfg ) + if( bb.blockHead() ) + local(bb); + } + + // Classic list scheduler + private static void local( CFGNode bb ) { + assert XS.isEmpty(); + int len = bb.nOuts(); + + // Count block-locals, remote inputs and outputs + for( int i=0; i<len; i++ ) + XSched.alloc(bb,bb.out(i)); + // Nodes are ready if they are not used by other nodes in this block. - // Move ready up front. We will never look at remaining nodes, later - // nodes are found by looking at users of ready nodes. + // Move ready up front. int ready = 0; - for( int i=0; i<ulen; i++ ) - if( BCNTS[uses[i]._nid]==0 ) // No block-local inputs? - uses[ready++] = uses[i]; // Move into ready set - assert ready > 0; + for( int i=0; i<len; i++ ) + if( XSched.get(bb.out(i)).isReady() ) // No block-local inputs? + bb._outputs.swap(ready++,i); // Move into ready set + assert len==0 || ready > 0; // Classic list scheduler. Behind sched is scheduled. Between sched // and ready have zero counts and are ready to schedule. Ahead of // ready is undefined. // - // As nodes are scheduled, the nodes they use decrement their _bcnt. Once + // As nodes are scheduled, the nodes they use decrement their bcnts[]. Once // that gets to 0, all the nodes using it are scheduled, so it's ready. int sched = 0; - while( sched < ulen ) { - assert sched < ready : "Scheduling nodes that are not ready. Probably due to duplicate nodes in the user list."; - int pick = best(uses, sched,ready); // Pick best - Node best = uses[pick]; // Swap best to head of ready - uses[pick] = uses[sched]; - uses[sched++] = best; // And move it into the scheduled set - // Lower ready count of users + while( sched < len ) { + assert sched < ready; + int pick = best(bb._outputs,sched,ready); // Pick best + Node best = bb._outputs.swap(pick,sched++); // Swap best to head of ready and move into the scheduled set + // Lower ready count of users, and since projections are ready as + // soon as their multi is ready, lower those now too. for( Node use : best._outputs ) - if( use instanceof ProjNode ) { + if( use instanceof ProjNode ) for( Node useuse : use._outputs ) ready = ready(bb,useuse,ready); - } else - ready = ready(bb, use,ready); + else + ready = ready(bb,use,ready); } + + // Reset for next block + for( XSched x : XS.values() ) + x.free(); + XS.clear(); } private static int ready(CFGNode bb, Node use, int ready) { - if( use != null && use.in(0)==bb && !(use instanceof PhiNode) ) { - assert BCNTS[use._nid] >= 1; - if( --BCNTS[use._nid] == 0 ) - bb._outputs._es[ready++] = use; // Became ready, move into ready set - } + if( use!=null && !(use instanceof PhiNode) && use.in(0)==bb && XSched.get(use).decIsReady() ) + bb._outputs.set(ready++, use); // Became ready, move into ready set + //bb._outputs.swap(ready++,use); // Became ready, move into ready set return ready; } // Pick best between sched and ready. - private static int best( Node[] uses, int sched, int ready ) { + private static int best( Ary<Node> blk, int sched, int ready ) { int pick = sched; - int score = score(uses[pick]); + int score = score(blk.at(pick)); for( int i=sched+1; i<ready; i++ ) { - int nscore = score(uses[i]); + int nscore = score(blk.at(i)); if( nscore > score ) { score = nscore; pick = i; } } @@ -99,12 +165,67 @@ public abstract class ListScheduler { } // Highest score wins. Max at 1000, min at 10, except specials. - private static int score( Node n ) { - if( n.isMultiTail() ) return 1001; // Pinned just behind the multi-head - if( n instanceof CFGNode ) return n instanceof ReturnNode ? 2 : 1; // Pinned at block exit + private static final int[] CNT = new int[3]; + static int score( Node n ) { + if( n instanceof ProjNode ) return 1001; // Pinned at block entry + if( n instanceof CProjNode ) return 1001; // Pinned at block entry + if( n instanceof PhiNode ) return 1000; + if( n instanceof CFGNode ) return 1; // Pinned at block exit + + int score = 500; + // Ideal nodes ignore register pressure scheduling + if( !(n instanceof MachNode) ) + return score; + + // Register pressure local scheduling: avoid overlapping specialized + // registers usages. + + // Subtract 10 if this op forces a live range to exist that cannot be + // resolved immediately; i.e., live count goes up. Scale to 20 if + // multi-def. + + // Subtract 100 if this op forces a single-def live range to exist + // which might conflict on the same register with other live ranges. + // Defines a single register based on def & uses, and the output is not + // ready. Scale to 200 for multi-def. + CNT[1]=CNT[2]=0; + XSched xn = XSched.get(n); + if( xn._rdef ) score = 200; // If defining a remote value, just generically stall alot + if( n instanceof MultiNode ) { + for( Node use : n._outputs ) + singleUseNotReady( use, xn._single ); + } else if( n.nOuts() == 1 ) + singleUseNotReady( n, xn._single ); + score += -10 * Math.min( CNT[1], 2 ); + score += -100 * Math.min( CNT[2], 2 ); + + // Add 10 if this op ends a single-def live range, add 20 for 2 or more. + // Scale to 100,200 if the single-def is also single-register. + CNT[1]=CNT[2]=0; + for( int i=1; i<n.nIns(); i++ ) { + XSched xd = XSched.get( n.in(i) ); + if( xd != null && xd._n.nOuts()==1 ) + CNT[xd._single || ((MachNode)n).regmap(i).size1() ? 2 : 1]++; + } + score += 10 * Math.min( CNT[1], 2 ); + score += 100 * Math.min( CNT[2], 2 ); + + //// Nothing special + //if( n instanceof Pe ) return 500; // RISC want to go after PE + //if( n instanceof Risc ) return 400; // RISC want to go after PE + assert 10 <= score && score <= 990; + return score; + } - // Nothing special - return 500; + // Single use, and that use is not ready to fire once this one does. + // If true, stalling 'n' might reduce 'n's lifetime. + // Return 0 for false, 1 if true, 10 if also single register + private static void singleUseNotReady( Node n, boolean single ) { + if( n.nOuts() != 1 ) return; + XSched xu = XSched.get(n.out(0)); + if( xu !=null && xu._bcnt==0 ) + return; + CNT[single ? 2 : 1]++; } } diff --git a/src/main/java/com/seaofnodes/simple/Machine.java b/src/main/java/com/seaofnodes/simple/Machine.java new file mode 100644 index 00000000..b29e9aba --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/Machine.java @@ -0,0 +1,21 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.node.CFGNode; +import com.seaofnodes.simple.node.IfNode; +import com.seaofnodes.simple.node.Node; + +abstract public class Machine { + // Human readable machine name. Something like "x86-64" or "arm" or "risc5" + public abstract String name(); + // Human-readable name for a register number, e.g. "RAX" or "R0" + public abstract String reg( int reg ); + // Create a split op; any register to any register, including stack slots + public abstract Node split(); + // Return a MachNode unconditional branch + public abstract CFGNode jump(); + // Break an infinite loop + public abstract IfNode never( CFGNode ctrl ); + // Instruction select from ideal nodes + public abstract Node instSelect( Node n ); +} diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index c16e3267..61a53d68 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; +import java.text.ParseException; import java.util.*; /** @@ -13,23 +14,12 @@ import java.util.*; */ public class Parser { - /** - * A Global Static, unique to each compilation. This is a public, so we - * can make constants everywhere without having to thread the StartNode - * through the entire parser and optimizer. - * <p> - * To make the compiler multithreaded, this field will have to move into a TLS. - */ - public static StartNode START; - public static ConstantNode ZERO; // Very common node, cached here public static ConstantNode NIL; // Very common node, cached here public static XCtrlNode XCTRL; // Very common node, cached here - // Next available memory alias number - static int ALIAS; - - public StopNode STOP; + // Compile driver + public final CodeGen _code; // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; @@ -51,7 +41,7 @@ public class Parser { /** * List of keywords disallowed as identifiers */ - private static final HashSet<String> KEYWORDS = new HashSet<>(){{ + public static final HashSet<String> KEYWORDS = new HashSet<>(){{ add("bool"); add("break"); add("byte"); @@ -98,21 +88,14 @@ public class Parser { public final HashMap<String, StructNode> INITS; - public Parser(String source) { this(source, TypeInteger.BOT); } - - public Parser(String source, TypeInteger arg) { - Node.reset(); - IterPeeps.reset(); - Type.reset(); - _lexer = new Lexer(source); + public Parser(CodeGen code, TypeInteger arg) { + _code = code; + _lexer = new Lexer(code._src); _scope = new ScopeNode(); _continueScope = _breakScope = null; - START = new StartNode(arg); - STOP = new StopNode(source); ZERO = con(TypeInteger.ZERO).keep(); NIL = con(Type.NIL).keep(); XCTRL= new XCtrlNode().peephole().keep(); - ALIAS = 2; // alias 0 for the control, 1 for memory TYPES = defaultTypes(); INITS = new HashMap<>(); } @@ -142,13 +125,13 @@ public class Parser { } // Debugging utility to find a Node by index - public static Node find(int nid) { return START.find(nid); } + public Node f(int nid) { return _code.f(nid); } private Node ctrl() { return _scope.ctrl(); } private <N extends Node> N ctrl(N n) { return _scope.ctrl(n); } - public StopNode parse() { return parse(false); } - public StopNode parse(boolean show) { + public void parse() { parse(false); } + public void parse(boolean show) { _xScopes.push(_scope); _scope.define(ScopeNode.CTRL, Type.CONTROL , false, null, _lexer); _scope.define(ScopeNode.MEM0, TypeMem.BOT , false, null, _lexer); @@ -158,7 +141,8 @@ public class Parser { _scope.mem(new MemMergeNode(false)); // Parse whole program, as-if function header "{ int arg -> body }" - parseFunctionBody(TypeFunPtr.MAIN,loc(),"arg"); + parseFunctionBody(_code._main,loc(),"arg"); + _code.link(_code._main)._name = "main"; if( !_lexer.isEOF() ) throw _errorSyntax("unexpected"); @@ -168,9 +152,8 @@ public class Parser { for( StructNode init : INITS.values() ) init.unkeep().kill(); INITS.clear(); - STOP.peephole(); + _code._stop.peephole(); if( show ) showGraph(); - return STOP; } /** @@ -184,24 +167,24 @@ public class Parser { ScopeNode breakScope = _breakScope; _breakScope = null; ScopeNode continueScope = _continueScope; _continueScope = null; - FunNode fun = _fun = (FunNode)peep(new FunNode(loc(),START,sig)); + FunNode fun = _fun = (FunNode)peep(new FunNode(loc(),sig,null,_code._start)); // Once the function header is available, install in linker table - // allowing recursive functions. Linker matches on declared args and // exact fidx, and ignores the return (because the fidx will only match // the exact single function). - CodeGen.CODE.link(fun); + _code.link(fun); Node rpc = new ParmNode("$rpc",0,TypeRPC.BOT,fun,con(TypeRPC.BOT)).peephole(); // Build a multi-exit return point for all function returns - RegionNode r = new RegionNode((Node)null,null).init(); + RegionNode r = new RegionNode((Lexer)null,null,null).init(); assert r.inProgress(); PhiNode rmem = new PhiNode(ScopeNode.MEM0,TypeMem.BOT,r,null).init(); PhiNode rrez = new PhiNode(ScopeNode.ARG0,Type.BOTTOM,r,null).init(); ReturnNode ret = new ReturnNode(r, rmem, rrez, rpc, fun).init(); fun.setRet(ret); assert ret.inProgress(); - STOP.addDef(ret); + _code._stop.addDef(ret); // Pre-call the function from Start, with worse-case arguments. This // represents all the future, yet-to-be-parsed functions calls and @@ -400,7 +383,7 @@ public class Parser { // Our current scope is the body Scope ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection _scope.addGuards(ifT,pred.unkeep(),false); // Up-cast predicate - Node expr = parseStatement().keep(); // Parse loop body + parseStatement(); // Parse loop body _scope.removeGuards(ifT); // Merge the loop bottom into other continue statements @@ -440,7 +423,7 @@ public class Parser { _xScopes.pop(); _xScopes.push(exit); _scope = exit; - return peep(expr.unkeep()); + return ZERO; } private ScopeNode jumpTo(ScopeNode toScope) { @@ -598,7 +581,7 @@ public class Parser { * @return {@code null} */ Node showGraph() { - System.out.println(new GraphVisualizer().generateDotOutput(STOP,_scope,_xScopes)); + System.out.println(new GraphVisualizer().generateDotOutput(_code._stop,_scope,_xScopes)); return null; } @@ -687,7 +670,6 @@ public class Parser { boolean hasBang = match("!"); Lexer loc = loc(); String name = requireId(); - // Optional initializing expression follows boolean xfinal = false; Node expr; @@ -711,7 +693,7 @@ public class Parser { if( !xfinal ) t = t.glb(); // Widen if not final } if( t instanceof TypeFunPtr && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) - tfp.setName(name); + _code.link(tfp)._name = name; } else { // Need an expression to infer the type. @@ -779,7 +761,7 @@ public class Parser { s.addDef(_scope.in(i)); Var v = _scope._vars.at(i); if( !v.isFRef() ) // Promote to outer scope, not defined here - fs.push(Field.make(v._name,v.type(),ALIAS++,v._final)); + fs.push(Field.make(v._name,v.type(),_code.getALIAS(),v._final)); } TypeStruct ts = s._ts = TypeStruct.make(typeName, fs.asAry()); TYPES.put(typeName, TypeMemPtr.make(ts)); @@ -835,7 +817,7 @@ public class Parser { int old2 = pos(); match("!"); String id = _lexer.matchId(); - if( !(peek(',') || peek(';')) ) + if( !(peek(',') || peek(';') || match("->")) ) return posT(old1); pos(old2); // Reset lexer to reparse if( id==null ) @@ -853,7 +835,7 @@ public class Parser { Type ta = TYPES.get(tname); if( ta != null ) return (TypeMemPtr)ta; // Need make an array type. - TypeStruct ts = TypeStruct.makeAry(TypeInteger.BOT,ALIAS++,t,ALIAS++); + TypeStruct ts = TypeStruct.makeAry(TypeInteger.U32,_code.getALIAS(),t,_code.getALIAS()); assert ts.str().equals(tname); TypeMemPtr tary = TypeMemPtr.make(ts); TYPES.put(tname,tary); @@ -1204,20 +1186,29 @@ public class Parser { if( fs==null ) throw error("Unknown struct type '" + obj._name + "'"); int len = fs.length; - Node[] ns = new Node[2+len+len]; + Node[] ns = new Node[2+len]; ns[0] = ctrl(); // Control in slot 0 // Total allocated length in bytes ns[1] = size; // Memory aliases for every field for( int i = 0; i < len; i++ ) - ns[2 +i] = memAlias(fs[i]._alias); - // Initial values for every field - for( int i = 0; i < len; i++ ) - ns[2+len+i] = init.get(i+idx); - Node nnn = new NewNode(TypeMemPtr.make(obj), ns).peephole(); + ns[2+i] = memAlias(fs[i]._alias); + Node nnn = new NewNode(TypeMemPtr.make(obj), ns).peephole().keep(); for( int i = 0; i < len; i++ ) memAlias(fs[i]._alias, new ProjNode(nnn,i+2,memName(fs[i]._alias)).peephole()); - return new ProjNode(nnn,1,obj._name).peephole(); + Node ptr = new ProjNode(nnn.unkeep(),1,obj._name).peephole().keep(); + + // Initial nonzero values for every field + for( int i = 0; i < len; i++ ) { + Node val = init.get( i + idx ); + if( val._type != val._type.makeZero() ) { + Node mem = memAlias(fs[i]._alias); + Node st = new StoreNode(loc(),fs[i]._fname,fs[i]._alias,fs[i]._type,mem,ptr,con(obj.offset(i)),val,true).peephole(); + memAlias(fs[i]._alias,st); + } + } + + return ptr.unkeep(); } private static final Ary<Node> ALTMP = new Ary<>(Node.class); @@ -1261,8 +1252,9 @@ public class Parser { throw error("Accessing unknown field '" + name + "' from 'null'"); // Sanity check expr for being a reference - if( !(expr._type instanceof TypeMemPtr ptr) ) - throw error("Expected reference but got " + expr._type.str()); + if( !(expr._type instanceof TypeMemPtr ptr) ) { + throw error( "Expected "+(name=="#" || name=="[]" ? "array" : "reference")+" but found " + expr._type.str() ); + } // Sanity check field name for existing TypeMemPtr tmp = (TypeMemPtr)TYPES.get(ptr._obj._name); @@ -1302,7 +1294,7 @@ public class Parser { // Arrays include control, as a proxy for a safety range check // Structs don't need this; they only need a NPE check which is // done via the type system. - if( base.isAry() ) load.setDef(0,ctrl()); + if( base.isAry() && !name.equals("#") ) load.setDef(0,ctrl()); load = peep(load); // Check for assign-update, "ptr.fld += expr" or "ary[idx]++" @@ -1366,7 +1358,7 @@ public class Parser { } require("->"); // Make a concrete function type, with a fidx - TypeFunPtr tfp = TypeFunPtr.makeFun(TypeTuple.make(ts.asAry()),Type.BOTTOM); + TypeFunPtr tfp = _code.makeFun(TypeTuple.make(ts.asAry()),Type.BOTTOM); ReturnNode ret = parseFunctionBody(tfp,loc,ids.asAry()); return con(ret._fun.sig()); } @@ -1400,6 +1392,14 @@ public class Parser { // Unkeep them all for( Node arg : args ) arg.unkeep(); + // Dead into the call? Skip all the node gen + if( ctrl()._type == Type.XCONTROL ) { + for( Node arg : args ) + if( arg.isUnused() ) + arg.kill(); + return con(Type.TOP); + } + // Into the call CallNode call = (CallNode)new CallNode(loc(), args.asAry()).peephole(); @@ -1656,7 +1656,6 @@ public class Parser { private String parseNumberString() { int old = _position; int len = Math.abs(isLongOrDouble()); - _position += len; return new String(_input,old,len); } diff --git a/src/main/java/com/seaofnodes/simple/RegMask.java b/src/main/java/com/seaofnodes/simple/RegMask.java new file mode 100644 index 00000000..20be7157 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/RegMask.java @@ -0,0 +1,39 @@ +package com.seaofnodes.simple; + +import java.util.BitSet; + +// A "register mask" - 1 bit set for each allowed register. In addition "stack +// slot" registers may be allowed, effectively making the set infinite. +public class RegMask { + + public static final RegMask EMPTY = new RegMask(); + + final BitSet _bits; + + public RegMask(long x ) { _bits = BitSet.valueOf(new long[]{x}); } + public RegMask(long[] xs) { _bits = BitSet.valueOf( xs); } + // Internal constructor + RegMask() { _bits = new BitSet(); } + RegMask(BitSet bs) { _bits = bs; } + + public boolean get(int r) { return _bits.get(r); } + + // Defensive writable copy + public RegMaskRW copy() { return new RegMaskRW( (BitSet)_bits.clone() ); } + + boolean size1() { return _bits.cardinality()==1; } +} + +class RegMaskRW extends RegMask { + public RegMaskRW() { super(); } + public RegMaskRW(long x) { super(new long[]{x}); } + public RegMaskRW(long[] xs) { super(xs); } + public RegMaskRW(BitSet bs) { super(bs); } + public void set(int r) { _bits.set(r); } + public void clr(int r) { _bits.clear(r); } + public void set(int r, boolean b) { _bits.set(r,b); } + public RegMaskRW and( RegMask r ) { + _bits.and(r._bits); + return this; + } +} diff --git a/src/main/java/com/seaofnodes/simple/SB.java b/src/main/java/com/seaofnodes/simple/SB.java index 6f5a29ee..7d580c21 100644 --- a/src/main/java/com/seaofnodes/simple/SB.java +++ b/src/main/java/com/seaofnodes/simple/SB.java @@ -29,6 +29,23 @@ public final class SB { public SB p( int s ) { _sb.append(s); return this; } public SB p( long s ) { _sb.append(s); return this; } public SB p( boolean s) { _sb.append(s); return this; } + // 4 hex digits + public SB hex4(int s) { + assert (s>>4*4)==0; // Fits in 16 bits + for( int i=0; i<4; i++ ) { + int digit = (s>>((3-i)*4)) & 0xf; + _sb.append((char)((digit <= 9 ? '0' : ('A'-10))+digit)); + } + return this; + } + // Fixed width field + public SB fix( int sz, String s ) { + assert sz >=0; + for( int i=0; i<sz; i++ ) + _sb.append( i < s.length() ? s.charAt(i) : ' '); + return this; + } + // Not spelled "p" on purpose: too easy to accidentally say "p(1.0)" and // suddenly call the autoboxed version. public SB pobj( Object s ) { _sb.append(s.toString()); return this; } diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index e6704ea6..6b7f2418 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -4,6 +4,8 @@ import com.seaofnodes.simple.type.*; import java.util.BitSet; +import static com.seaofnodes.simple.Parser.con; + public class AddNode extends Node { public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @@ -53,7 +55,7 @@ public class AddNode extends Node { // Add of same to a multiply by 2 if( lhs==rhs ) - return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole()); + return new ShlNode(null,lhs,con(1)); // Goal: a left-spine set of adds, with constants on the rhs (which then fold). @@ -126,6 +128,7 @@ public class AddNode extends Node { lphi = pcon(lhs.in(2),op); // Will rotate with the Phi push } if( lphi==null ) return null; + if( lphi.region().nIns() <=2 ) return null; // Phi is collapsing // RHS is a constant or a Phi of constants if( !(rhs instanceof ConstantNode) && pcon(rhs,op)==null ) diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index ae968ca1..84be11a9 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.*; - import java.util.BitSet; import static com.seaofnodes.simple.type.TypeInteger.*; @@ -13,7 +12,7 @@ abstract public class BoolNode extends Node { super(null, lhs, rhs); } - abstract String op(); // String opcode name + abstract public String op(); // String opcode name @Override public String label() { return getClass().getSimpleName(); } @@ -37,14 +36,14 @@ abstract public class BoolNode extends Node { return BOOL.dual(); if( in(1)==in(2) ) // LT fails, both EQ and LE succeed - return this instanceof LT ? TypeInteger.FALSE : TypeInteger.TRUE; + return this instanceof LT ? FALSE : TRUE; if( t1 instanceof TypeInteger i1 && t2 instanceof TypeInteger i2 ) return doOp(i1,i2); if( t1 instanceof TypeFloat f1 && t2 instanceof TypeFloat f2 && f1.isConstant() && f2.isConstant() ) - return doOp(f1.value(), f2.value()) ? TypeInteger.TRUE : TypeInteger.FALSE; + return doOp(f1.value(), f2.value()) ? TRUE : FALSE; return BOOL; } @@ -56,7 +55,7 @@ abstract public class BoolNode extends Node { public Node idealize() { // Compare of same if( in(1)==in(2) ) - return this instanceof LT ? Parser.ZERO : new ConstantNode(TypeInteger.TRUE); + return this instanceof LT ? Parser.ZERO : new ConstantNode(TRUE); // Equals pushes constant to the right; 5==X becomes X==5. if( this instanceof EQ ) { @@ -82,7 +81,7 @@ abstract public class BoolNode extends Node { public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } - String op() { return "=="; } + public String op() { return "=="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1==i2 && i1.isConstant() ) return TRUE; if( i1._max < i2._min || i1._min > i2._max ) return FALSE; @@ -93,7 +92,7 @@ abstract public class BoolNode extends Node { } public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } - String op() { return "<" ; } + public String op() { return "<" ; } public String glabel() { return "<"; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1._max < i2._min ) return TRUE; @@ -105,7 +104,7 @@ abstract public class BoolNode extends Node { } public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } - String op() { return "<="; } + public String op() { return "<="; } public String glabel() { return "<="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1._max <= i2._min ) return TRUE; @@ -120,4 +119,16 @@ abstract public class BoolNode extends Node { public static class LTF extends LT { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs < rhs; } } public static class LEF extends LE { public LEF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs <= rhs; } } + // Unsigned less that, for range checks. Not directly user writable. + public static class ULT extends BoolNode { + public ULT(Node lhs, Node rhs) { super(lhs,rhs); } + public String op() { return "u<" ; } + public String glabel() { return "u<"; } + TypeInteger doOp(TypeInteger i1, TypeInteger i2) { + if( Long.compareUnsigned(i1._max,i2._min) < 0 ) return TRUE; + if( Long.compareUnsigned(i1._min,i2._max) >= 0 ) return FALSE; + return BOOL; + } + Node copy(Node lhs, Node rhs) { return new ULT(lhs,rhs); } + } } diff --git a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index b051b3ce..174725f5 100644 --- a/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -1,12 +1,12 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.Utils; - +import com.seaofnodes.simple.type.*; import java.util.BitSet; -import java.util.HashSet; import java.util.HashMap; +import java.util.HashSet; /** Control Flow Graph Nodes * <p> @@ -21,7 +21,13 @@ import java.util.HashMap; */ public abstract class CFGNode extends Node { - public CFGNode(Node... nodes) { super(nodes); } + public CFGNode(Node... nodes) { super(nodes); } + public CFGNode(CFGNode cfg) { + super(cfg); + _idepth = cfg._idepth; + _ltree = cfg._ltree; + _pre = cfg._pre; + } public CFGNode cfg(int idx) { return (CFGNode)in(idx); } @@ -101,8 +107,8 @@ public abstract class CFGNode extends Node { _pre = pre++; // Pre-walk for( Node use : _outputs ) - if( use instanceof CFGNode usecfg && !skip(usecfg) ) - pre = usecfg._bltWalk(pre,use instanceof FunNode fuse ? fuse : fun,stop,post); + if( use instanceof CFGNode usecfg && !skip( usecfg ) ) + pre = usecfg._bltWalk( pre, use instanceof FunNode fuse ? fuse : fun, stop, post ); // Post-order work: find innermost loop LoopTree inner = null, ltree; diff --git a/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/src/main/java/com/seaofnodes/simple/node/CProjNode.java index 01119310..690ef590 100644 --- a/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.type.TypeTuple; import java.util.BitSet; -public class CProjNode extends CFGNode implements MultiUse { +public class CProjNode extends CFGNode { // Which slice of the incoming multipart value public final int _idx; @@ -19,9 +19,9 @@ public class CProjNode extends CFGNode implements MultiUse { _idx = idx; _label = label; } + public CProjNode(CProjNode c) { super(c); _idx = c._idx; _label = c._label; } @Override public String label() { return _label; } - @Override public int idx() { return _idx; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); } diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 07a2b5a3..4e50c1fc 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -1,8 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.*; import com.seaofnodes.simple.type.*; import java.util.BitSet; @@ -14,7 +12,8 @@ public class CallEndNode extends CFGNode implements MultiNode { // When set true, this Call/CallEnd/Fun/Return is being trivially inlined private boolean _folding; - public CallEndNode(CallNode call) { super(call); } + public CallEndNode(CallNode call) { super(new Node[]{call}); } + public CallEndNode(CallEndNode cend) { super(cend); } @Override public String label() { return "CallEnd"; } @@ -46,8 +45,7 @@ public class CallEndNode extends CFGNode implements MultiNode { // Trivial inlining: call site calls a single function; single function // is only called by this call site. - if( !_folding && nIns()==2 ) { - CallNode call = call(); + if( !_folding && nIns()==2 && in(0) instanceof CallNode call ) { Node fptr = call.fptr(); if( fptr.nOuts() == 1 && // Only user is this call fptr instanceof ConstantNode && // We have an immediate call @@ -72,7 +70,7 @@ public class CallEndNode extends CFGNode implements MultiNode { fun.setDef(1,Parser.XCTRL); // No default/unknown StartNode caller fun.setDef(2,call.ctrl()); // Bypass the Call; fun.ret().setDef(3,null); // Return is folding also - IterPeeps.addAll(fun._outputs); + CodeGen.CODE.addAll(fun._outputs); return this; } } else { diff --git a/src/main/java/com/seaofnodes/simple/node/CallNode.java b/src/main/java/com/seaofnodes/simple/node/CallNode.java index 246398ee..a9ca852c 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -17,17 +17,14 @@ public class CallNode extends CFGNode { public final Parser.Lexer _loc; public CallNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc = loc; } + public CallNode(CallNode call) { super(call); _loc = call._loc; } @Override public String label() { return "Call"; } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - String fname = null; - Node fptr = fptr(); - if( fptr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) - fname = tfp._name; - if( fname==null ) fptr._print0(sb,visited); + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { + String fname = name(); + if( fname == null ) fptr()._print0(sb,visited); else sb.append(fname); sb.append("( "); for( int i=2; i<nIns()-1; i++ ) @@ -35,6 +32,13 @@ public class CallNode extends CFGNode { sb.setLength(sb.length()-1); return sb.append(")"); } + public String name() { + if( fptr()._type instanceof TypeFunPtr tfp && tfp.isConstant() ) + return CodeGen.CODE.link(tfp)._name; + return null; + } + + Node ctrl() { return in(0); } Node mem () { return in(1); } @@ -118,7 +122,7 @@ public class CallNode extends CFGNode { if( use instanceof ParmNode parm ) parm.addDef(parm._idx==0 ? cend() : arg(parm._idx)); // Call end points to function return - IterPeeps.add(cend()).addDef(fun.ret()); + CodeGen.CODE.add(cend()).addDef(fun.ret()); assert linked(fun); } diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index e03bfb0e..d788cff7 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -1,9 +1,10 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.SB; import com.seaofnodes.simple.type.Type; - +import com.seaofnodes.simple.type.TypeFunPtr; import java.util.BitSet; /** @@ -18,12 +19,14 @@ import java.util.BitSet; * <p> * The Constant's value is the value stored in it. */ + public class ConstantNode extends Node { public final Type _con; public ConstantNode( Type type ) { - super(Parser.START); - _con = type; + super(new Node[]{CodeGen.CODE._start}); + _con = _type = type; } + public ConstantNode( ConstantNode con ) { super(con); _con = con._type; } public static Node make( Type type ) { if( type==Type. CONTROL ) return new CtrlNode(); @@ -39,6 +42,11 @@ public class ConstantNode extends Node { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { + if( _con instanceof TypeFunPtr tfp ) { + FunNode fun = CodeGen.CODE.link(tfp); + if( fun._name != null ) + return sb.append("{ ").append(fun._name).append("}"); + } return sb.append(_con.print(new SB())); } diff --git a/src/main/java/com/seaofnodes/simple/node/CtrlNode.java b/src/main/java/com/seaofnodes/simple/node/CtrlNode.java index 162417bb..0ea060bd 100644 --- a/src/main/java/com/seaofnodes/simple/node/CtrlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CtrlNode.java @@ -1,11 +1,12 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import java.util.BitSet; public class CtrlNode extends CFGNode { - public CtrlNode() { super(Parser.START); } + public CtrlNode() { super(CodeGen.CODE._start); } @Override public String label() { return "Ctrl"; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Cctrl"); } @Override public boolean isConst() { return true; } diff --git a/src/main/java/com/seaofnodes/simple/node/FunNode.java b/src/main/java/com/seaofnodes/simple/node/FunNode.java index 1f0c76eb..506e7758 100644 --- a/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.*; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFunPtr; import java.util.BitSet; +import static com.seaofnodes.simple.CodeGen.CODE; public class FunNode extends RegionNode { @@ -13,10 +14,13 @@ public class FunNode extends RegionNode { private TypeFunPtr _sig; // Initial signature private ReturnNode _ret; // Return pointer - public FunNode( Parser.Lexer loc, StartNode start, TypeFunPtr sig ) { super(loc,null,start); _sig=sig; } + public String _name; // Debug name + + public FunNode( Parser.Lexer loc, TypeFunPtr sig, Node... nodes ) { super(loc,nodes); _sig = sig; } + public FunNode( FunNode fun ) { super( fun, fun._loc ); _sig = fun.sig(); _name = fun._name; } @Override - public String label() { return _sig._name == null ? "$fun" : _sig._name; } + public String label() { return _name == null ? "$fun" : _name; } // Find the one CFG user from Fun. It's not always the Return, but always // the Return *is* a CFG user of Fun. @@ -45,9 +49,10 @@ public class FunNode extends RegionNode { public TypeFunPtr sig() { return _sig; } void setSig( TypeFunPtr sig ) { assert sig.isa(_sig); - if( _sig != sig ) - IterPeeps.add(this); - _sig = sig; + if( _sig != sig ) { + CODE.add(this); + _sig = sig; + } } @Override @@ -58,6 +63,15 @@ public class FunNode extends RegionNode { @Override public Node idealize() { + + // Some linked path dies + Node progress = deadPath(); + if( progress!=null ) { + if( nIns()==3 && in(2) instanceof CallNode call ) + CODE.add(call.cend()); // If Start and one call, check for inline + return progress; + } + // When can we assume no callers? Or no other callers (except main)? // In a partial compilation, we assume Start gets access to any/all // top-level public structures and recursively what they point to. @@ -66,16 +80,18 @@ public class FunNode extends RegionNode { // In a total compilation, we can start from Start and keep things // more contained. - // If no default/unknown caller, use the normal RegionNode ideal rules // to collapse if( unknownCallers() ) return null; - Node progress = super.idealize(); - if( progress!=null ) { - IterPeeps.add( CodeGen.CODE._stop); - IterPeeps.add( _ret ); + + // If down to a single input, become that input + if( nIns()==2 && !hasPhi() ) { + CODE.add( CODE._stop ); // Stop will remove dead path + CODE.add( _ret ); // Return will compute to TOP control + return in(1); // Collapse if no Phis; 1-input Phis will collapse on their own } - return progress; + + return null; } // Bypass Region idom, always assume depth == 1, one more than Start diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index eafcdf5b..9e6d2dff 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.*; import java.util.BitSet; @@ -9,8 +10,9 @@ public class IfNode extends CFGNode implements MultiNode { public IfNode(Node ctrl, Node pred) { super(ctrl, pred); - IterPeeps.add(this); // Because idoms are complex, just add it + CodeGen.CODE.add(this); // Because idoms are complex, just add it } + public IfNode(IfNode iff) { super(iff); } @Override public String label() { return "If"; } @@ -34,7 +36,6 @@ public class IfNode extends CFGNode implements MultiNode { // If the If node is not reachable then neither is any following Proj if (ctrl()._type != Type.CONTROL && ctrl()._type != Type.BOTTOM ) return TypeTuple.IF_NEITHER; - if( _disablePeephole ) return TypeTuple.IF_BOTH; Node pred = pred(); Type t = pred._type; // High types mean NEITHER side is reachable. @@ -59,7 +60,7 @@ public class IfNode extends CFGNode implements MultiNode { if( !pred()._type.isHighOrConst() ) for( CFGNode dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() ) if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof CProjNode prj ) { - setDef(1,new ConstantNode(TypeInteger.constant(prj._idx==0?1:0)).peephole()); + setDef(1,con( prj._idx==0 ? 1 : 0 )); return this; } return null; diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index eee5169d..4004f87f 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -47,31 +47,38 @@ public class LoadNode extends MemOpNode { @Override public Node idealize() { Node ptr = ptr(); + Node mem = mem(); // Simple Load-after-Store on same address. - if( mem() instanceof StoreNode st && + if( mem instanceof StoreNode st && ptr == st.ptr() && off() == st.off() ) { // Must check same object assert _name.equals(st._name); // Equiv class aliasing is perfect - return st.val(); + return extend(st.val()); } // Simple Load-after-New on same address. - if( mem() instanceof ProjNode p && p.in(0) instanceof NewNode nnn && + if( mem instanceof ProjNode p && p.in(0) instanceof NewNode nnn && ptr == nnn.proj(1) ) // Must check same object - return nnn.in(nnn.findAlias(_alias)); // Load from New init + return zero(nnn); // Load zero from new + + // Uplift control to a prior dominating load. + for( Node memuse : mem._outputs ) + // Find a prior load, has same mem,ptr,off but higher ctrl + if( memuse != this && memuse instanceof LoadNode ld && ptr==ld.ptr() && off()==ld.off() && + cfg0()!=null && cfg0()._idom(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier + return ld; // Load-after-Store on same address, but bypassing provably unrelated // stores. This is a more complex superset of the above two peeps. // "Provably unrelated" is really weak. if( ptr instanceof ReadOnlyNode ro ) ptr = ro.in(1); - Node mem = mem(); outer: while( true ) { switch( mem ) { case StoreNode st: if( ptr == st.ptr().addDep(this) && off() == st.off() ) - return castRO(st.val()); // Proved equal + return extend(castRO(st.val())); // Proved equal // Can we prove unequal? Offsets do not overlap? if( !off()._type.join(st.off()._type).isHigh() && // Offsets overlap !neverAlias(ptr,st.ptr()) ) // And might alias @@ -88,10 +95,10 @@ public class LoadNode extends MemOpNode { switch( mproj.in(0) ) { case NewNode nnn1: if( ptr instanceof ProjNode pproj && pproj.in(0) == mproj.in(0) ) - return castRO(nnn1.in(nnn1.findAlias(_alias))); // Load from New init - if( !(ptr instanceof ProjNode pproj && pproj.in(0) instanceof NewNode nnn2) ) + return zero(nnn1); + if( !(ptr instanceof ProjNode pproj && pproj.in(0) instanceof NewNode) ) break outer; // Cannot tell, ptr not related to New - mem = nnn1.in(_alias);// Bypass unrelated New + mem = nnn1.in(nnn1.findAlias(_alias));// Bypass unrelated New break; case StartNode start: break outer; case CallEndNode cend: break outer; // TODO: Bypass no-alias call @@ -131,6 +138,13 @@ public class LoadNode extends MemOpNode { return null; } + // Load a flavored zero from a New + private Node zero(NewNode nnn) { + TypeStruct ts = nnn._ptr._obj; + Type zero = ts._fields[ts.findAlias(_alias)]._type.makeZero(); + return castRO(new ConstantNode(zero).peephole()); + } + private Node ld( int idx ) { Node mem = mem(), ptr = ptr(); return new LoadNode(_loc,_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr, off()).peephole(); @@ -178,4 +192,19 @@ public class LoadNode extends MemOpNode { return new ReadOnlyNode(rez).peephole(); return rez; } + + // When a load bypasses a store, the store might truncate bits - and the + // load will need to zero/sign-extend. + private Node extend(Node val) { + if( !(_declaredType instanceof TypeInteger ti) ) return val; + if( ti._min==0 ) // Unsigned + return new AndNode(null,val,con(ti._max)); + // Signed extension + int shift = Long.numberOfLeadingZeros(ti._max)-1; + if( shift==0 ) + return val; + Node shf = con(shift); + Node shl = new ShlNode(null,val,shf.keep()).peephole(); + return new SarNode(null,shl,shf.unkeep()); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index f70a1012..d2b0e36c 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -10,6 +10,7 @@ import java.util.HashSet; public class LoopNode extends RegionNode { public LoopNode( Parser.Lexer loc, Node entry ) { super(loc,null,entry,null); } + public LoopNode( LoopNode loop ) { super(loop); } public CFGNode entry() { return cfg(1); } public CFGNode back () { return cfg(2); } diff --git a/src/main/java/com/seaofnodes/simple/node/MachConcreteNode.java b/src/main/java/com/seaofnodes/simple/node/MachConcreteNode.java new file mode 100644 index 00000000..0c49fc64 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MachConcreteNode.java @@ -0,0 +1,27 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.Utils; +import java.io.ByteArrayOutputStream; +import java.util.BitSet; + +// Generic machine-specific class, has a few Node implementations that have to +// exist (abstract) but are not useful past the optimizer. +public abstract class MachConcreteNode extends Node implements MachNode{ + + public MachConcreteNode(Node node) { super(node); } + public MachConcreteNode(Node[]nodes) { super(nodes); } + + @Override public String label() { return op(); } + @Override public Type compute () { throw Utils.TODO(); } + @Override public Node idealize() { throw Utils.TODO(); } + + @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { + sb.append("(").append(op()).append(","); + for( int i=1; i<nIns(); i++ ) + (in(i)==null ? sb.append(" ---") : in(i)._print0(sb, visited)).append(","); + sb.setLength(sb.length()-1); + return sb.append(")"); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/MachNode.java b/src/main/java/com/seaofnodes/simple/node/MachNode.java new file mode 100644 index 00000000..9f2fee85 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MachNode.java @@ -0,0 +1,49 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.*; +import java.io.ByteArrayOutputStream; + +public interface MachNode { + + // Easy access to the abstract Machine + default Machine machine() { return CodeGen.CODE._mach; } + + // Run a post-instruction-selection action + default void postSelect() { } + + // Register mask allowed on input i. 0 for no register. + abstract public RegMask regmap(int i); + // Register mask allowed as a result. 0 for no register. + abstract public RegMask outregmap(); + // Multi-reg-defining machine op; idx comes from Proj. + // Sometimes these Projs have no uses, and just exist to kill a register. + default RegMask outregmap(int idx) { throw Utils.TODO(); } + + // If this op updates the same register as input 'idx', e.g. many X86 "R1 += + // R2" style ops. This forces the output live range to equal the input live + // range, so they both get the same register. + + // This can hold true for projections, if the instruction updates many + // registers that it also takes in. Note that ops also use the same + // registers for both inputs and outputs but these are pinned and without any + // choices (e.g. always RCX for both an input and output) and are better + // served with just declaring as a fixed register. + + // Returns either 0 for not-two-adr or the updated input; for projections + // this is their Multi's updated input. + default int twoAddress( ) { return 0; } + + // Instructions cheaper to recreate than to spill, such as loading small constants + default boolean isClone() { return false; } + // Encoding is appended into the byte array; size is returned + abstract public int encoding(ByteArrayOutputStream bytes); + + // Human-readable form appended to the SB. Things like the encoding, + // indentation, leading address or block labels not printed here. + // Just something like "R17=[R18+12] // Load array base". + // General form: "dst=src+src". + default void asm(CodeGen code, SB sb) { throw Utils.TODO(); } + + // Human readable opcode; e.g. "ld4" or "call". + default String op() { throw Utils.TODO(); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 8a08853c..5363bb6f 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -1,11 +1,8 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Var; +import com.seaofnodes.simple.*; import com.seaofnodes.simple.type.*; import java.util.*; -import static com.seaofnodes.simple.Utils.TODO; /** * Memory Merge - a merge of many aliases into a "fat memory". All aliases @@ -21,6 +18,7 @@ public class MemMergeNode extends Node { public final boolean _inProgress; public MemMergeNode( boolean inProgress) { _type = TypeMem.BOT; _inProgress = inProgress; } + public MemMergeNode(MemMergeNode mem) { super(mem); _inProgress = false; } // If being used by a Scope, this is "in progress" from the Parser. @@ -139,7 +137,7 @@ public class MemMergeNode extends Node { if( in(i) instanceof PhiNode phi ) { // Do an eager useless-phi removal Node in = phi.peephole(); - IterPeeps.addAll(phi._outputs); + CodeGen.CODE.addAll(phi._outputs); phi.moveDepsToWorklist(); if( in != phi ) { if( !phi.iskeep() ) // Keeping phi around for parser elsewhere diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index f9df2a40..d9ab6b89 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -4,6 +4,8 @@ import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMemPtr; +import java.lang.StringBuilder; +import java.util.BitSet; /** * Convenience common base for Load and Store. @@ -29,6 +31,13 @@ public abstract class MemOpNode extends Node { this(loc,name, alias, glb, mem, ptr, off); addDef(value); } + public MemOpNode( Node mach, MemOpNode mop ) { + super(mach); + _name = mop._name; + _alias = mop._alias; + _declaredType = mop._declaredType; + _loc = mop._loc; + } // static String mlabel(String name) { return name.equals("[]") ? "ary" : (name.equals("#") ? "len" : name); } @@ -38,6 +47,10 @@ public abstract class MemOpNode extends Node { public Node ptr() { return in(2); } public Node off() { return in(3); } + @Override StringBuilder _print1( StringBuilder sb, BitSet visited ) { return _printMach(sb,visited); } + public StringBuilder _printMach( StringBuilder sb, BitSet visited ) { throw Utils.TODO(); } + + @Override boolean eq(Node n) { MemOpNode mem = (MemOpNode)n; // Invariant diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index b5ef91e9..4fdf987d 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; - import java.util.BitSet; public class MulNode extends Node { @@ -41,15 +41,33 @@ public class MulNode extends Node { Type t1 = lhs._type; Type t2 = rhs._type; - // Mul of 1. We do not check for (1*x) because this will already - // canonicalize to (x*1) - if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==1 ) - return lhs; - // Move constants to RHS: con*arg becomes arg*con if ( t1.isConstant() && !t2.isConstant() ) return swap12(); + // Multiply by constant + if ( t2.isConstant() && t2 instanceof TypeInteger i ) { + // Mul of 1. We do not check for (1*x) because this will already + // canonicalize to (x*1) + long c = i.value(); + if( c==1 ) return lhs; + if( c==0 ) return Parser.ZERO; + // Mul by a power of 2, +/-1. Bit patterns more complex than this + // are unlikely to win on an X86 vs the normal "imul", and so + // become machine-specific. + if( (c & (c-1)) == 0 ) + return new ShlNode(null,lhs,con(Long.numberOfTrailingZeros(c))); + // 2**n + 1, e.g. 9 + long d = c-1; + if( (d & (d-1)) == 0 ) + return new AddNode(new ShlNode(null,lhs,con(Long.numberOfTrailingZeros(d))).peephole(),lhs); + // 2**n - 1, e.g. 31 + long e = c+1; + if( (e & (e-1)) == 0 ) + return new SubNode(new ShlNode(null,lhs,con(Long.numberOfTrailingZeros(e))).peephole(),lhs); + + } + // Do we have ((x * (phi cons)) * con) ? // Do we have ((x * (phi cons)) * (phi cons)) ? // Push constant up through the phi: x * (phi con0*con0 con1*con1...) diff --git a/src/main/java/com/seaofnodes/simple/node/MultiUse.java b/src/main/java/com/seaofnodes/simple/node/MultiUse.java deleted file mode 100644 index 436d3432..00000000 --- a/src/main/java/com/seaofnodes/simple/node/MultiUse.java +++ /dev/null @@ -1,5 +0,0 @@ -package com.seaofnodes.simple.node; - -public interface MultiUse { - abstract int idx(); -} diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java index 34d695f4..80545d66 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -24,17 +24,16 @@ public class NewNode extends Node implements MultiNode { assert nodes[0]._type==Type.CONTROL || nodes[0]._type == Type.XCONTROL; // Malloc-length in slot 1 assert nodes[1]._type instanceof TypeInteger || nodes[1]._type==Type.NIL; - for( int i=0; i<_len; i++ ) { + for( int i=0; i<_len; i++ ) // Memory slices for all fields. - assert nodes[2+ i]._type.isa(TypeMem.BOT); - // Value slices for all fields. - assert nodes[2 + _len + i]._type != null; - } + assert nodes[2+i]._type.isa(TypeMem.BOT); } - @Override public String label() { - return "new_"+glabel(); - } + public NewNode(NewNode nnn) { super(nnn); _ptr = nnn._ptr; _len = nnn._len; } + + public Node mem (int idx) { return in(idx+2); } + + @Override public String label() { return "new_"+glabel(); } @Override public String glabel() { return _ptr._obj.isAry() ? "ary_"+_ptr._obj._fields[1]._type.str() : _ptr._obj.str(); } @@ -45,11 +44,17 @@ public class NewNode extends Node implements MultiNode { return sb.append(_ptr._obj.str()); } - // Find matching alias input int findAlias(int alias) { - return 2+_ptr._obj.findAlias(alias)+_len; + int idx = _ptr._obj.findAlias(alias); + assert idx!= -1; // Error, caller should be calling + return idx+2; // Skip ctrl, size } + // 0 - ctrl + // 1 - byte size + // 2-len+2 - aliases, one per field + // len+2 - 2*len+2 - initial values, one per field + public Node size() { return in(1); } @Override public TypeTuple compute() { @@ -60,8 +65,9 @@ public class NewNode extends Node implements MultiNode { for( int i=0; i<fs.length; i++ ) { Type mt = in(i+2)._type; TypeMem mem = mt==Type.TOP ? TypeMem.TOP : (TypeMem)mt; - Type tfld = in(2+_len+i)._type.meet(mem._t); - ts[i+2] = TypeMem.make(fs[i]._alias,tfld); + Type tfld = mem._t.meet(mem._t.makeZero()); + Type tfld2 = tfld.join(fs[i]._type); + ts[i+2] = TypeMem.make(fs[i]._alias,tfld2); } return TypeTuple.make(ts); } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 4c6cce16..bbf1ebe9 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -3,8 +3,10 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.*; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFloat; +import com.seaofnodes.simple.type.TypeInteger; import java.util.*; import java.util.function.Function; +import static com.seaofnodes.simple.CodeGen.CODE; /** * All Nodes in the Sea of Nodes IR inherit from the Node class. @@ -48,16 +50,8 @@ public abstract class Node { public Type _type; - /** - * A private Global Static mutable counter, for unique node id generation. - * To make the compiler multithreaded, this field will have to move into a TLS. - * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values. - * */ - private static int UNIQUE_ID = 1; - public static int UID() { return UNIQUE_ID; } - - protected Node(Node... inputs) { - _nid = UNIQUE_ID++; // allocate unique dense ID + Node(Node... inputs) { + _nid = CODE.getUID(); // allocate unique dense ID _inputs = new Ary<>(Node.class); Collections.addAll(_inputs,inputs); _outputs = new Ary<>(Node.class); @@ -66,6 +60,18 @@ public abstract class Node { n.addUse( this ); } + // Make a Node using the existing arrays of nodes. + // Used by any pass rewriting all Node classes but not the edges. + Node( Node n ) { + assert CodeGen.CODE._phase == CodeGen.Phase.InstructionSelection; + _nid = CODE.getUID(); // allocate unique dense ID + _inputs = new Ary<>(n._inputs.asAry()); + _outputs = new Ary<>(Node.class); + _type = n._type; + _deps = null; + _hash = 0; + } + // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ" public abstract String label(); @@ -79,6 +85,9 @@ public abstract class Node { // Graphical label, e.g. "+" or "Region" or "==" public String glabel() { return label(); } + // Extra fun stuff, for assembly printing. Jump labels, parser locations, + // variable types, etc. + public String comment() { return null; } // ------------------------------------------------------------------------ @@ -163,10 +172,10 @@ public abstract class Node { new_def.addUse(this); // Set the new_def over the old (killed) edge _inputs.set(idx,new_def); - if( old_def != null ) { // If the old def exists, remove a def->use edge - if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead - old_def.kill(); // Kill old def - else IterPeeps.add(old_def);// Else old lost a use, so onto worklist + if( old_def != null ) { // If the old def exists, remove a def->use edge + if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead + old_def.kill(); // Kill old def + else CODE.add(old_def); // Else old lost a use, so onto worklist } moveDepsToWorklist(); // Return new_def for easy flow-coding @@ -246,11 +255,9 @@ public abstract class Node { _type=null; // Flag as dead while( nIns()>0 ) { // Set all inputs to null, recursively killing unused Nodes Node old_def = _inputs.removeLast(); - if( old_def != null ) { - IterPeeps.add(old_def);// Revisit neighbor because removed use - if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead - old_def.kill(); // Kill old def - } + // Revisit neighbor because removed use + if( old_def != null && CODE.add(old_def).delUse(this) ) + old_def.kill(); // If we removed the last use, the old def is now dead } assert isDead(); // Really dead now } @@ -283,7 +290,7 @@ public abstract class Node { int idx = n._inputs.find(this); n._inputs.set(idx,nnn); nnn.addUse(n); - IterPeeps.addAll(n._outputs); + CODE.addAll(n._outputs); } kill(); } @@ -292,12 +299,6 @@ public abstract class Node { // Graph-based optimizations /** - * We allow disabling peephole opt so that we can observe the - * full graph, vs the optimized graph. - */ - public static boolean _disablePeephole = false; - - /** * Try to peephole at this node and return a better replacement Node. * Always returns some not-null Node (often this). */ @@ -329,28 +330,22 @@ public abstract class Node { * </ul> */ public final Node peepholeOpt( ) { - ITER_CNT++; + CODE.iterCnt(); // Compute initial or improved Type Type old = setType(compute()); - // Peepholes can be turned off - except for cleaning up dead CFG paths. - // These need to clean up so the following code motion algorithms don't - // get confused by dead or infinite paths. - if( _disablePeephole && !(this instanceof RegionNode) && !(this instanceof PhiNode) ) - return old==_type ? null : this; // Peephole optimizations turned off - // Replace constant computations from non-constants with a constant // node. If peeps are disabled, still allow high Phis to collapse; // they typically come from dead Regions, and we want the Region to // collapse, which requires the Phis to die first. - if( _type.isHighOrConst() && !isConst() && (!_disablePeephole || _type.isHigh()) ) - return ConstantNode.make(_type).peepholeOpt(); + if( _type.isHighOrConst() && !isConst() ) + return ConstantNode.make(_type).peephole(); // Global Value Numbering if( _hash==0 ) { - Node n = GVN.get(this); // Will set _hash as a side effect + Node n = CODE._gvn.get(this); // Will set _hash as a side effect if( n==null ) - GVN.put(this,this); // Put in table now + CODE._gvn.put(this,this); // Put in table now else { // Because of random worklist ordering, the two equal nodes // might have different types. Because of monotonicity, both @@ -368,10 +363,9 @@ public abstract class Node { return n; // Report progress if( old!=_type ) return this; // Report progress; - ITER_NOP_CNT++; + CODE.iterNop(); return null; // No progress } - public static int ITER_CNT, ITER_NOP_CNT; // m is the new Node, self is the old. // Return 'm', which may have zero uses but is alive nonetheless. @@ -415,7 +409,7 @@ public abstract class Node { assert old==null || type.isa(old); // Since _type not set, can just re-run this in assert in the debugger if( old == type ) return old; _type = type; // Set _type late for easier assert debugging - IterPeeps.addAll(_outputs); + CODE.addAll(_outputs); moveDepsToWorklist(); return old; } @@ -485,7 +479,8 @@ public abstract class Node { Node addDep( Node dep ) { // Running peepholes during the big assert cannot have side effects // like adding dependencies. - if( IterPeeps.midAssert() ) return this; + if( CODE._midAssert ) return this; + if( dep == null ) return this; if( _deps==null ) _deps = new Ary<>(Node.class); if( _deps .find(dep) != -1 ) return this; // Already on list if( _inputs .find(dep) != -1 ) return this; // No need for deps on immediate neighbors @@ -497,15 +492,11 @@ public abstract class Node { // Move the dependents onto a worklist, and clear for future dependents. public void moveDepsToWorklist( ) { if( _deps==null ) return; - IterPeeps.addAll(_deps); + CODE.addAll(_deps); _deps.clear(); } - // Global Value Numbering. Hash over opcode and inputs; hits in this table - // are structurally equal. - public static final HashMap<Node,Node> GVN = new HashMap<>(); - // 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 ) { @@ -534,7 +525,7 @@ public abstract class Node { // If the _hash is set, then the Node is in the GVN table; remove it. void unlock() { if( _hash==0 ) return; - Node old = GVN.remove(this); // Pull from table + Node old = CODE._gvn.remove(this); // Pull from table assert old==this; _hash=0; // Out of table now } @@ -618,31 +609,21 @@ public abstract class Node { // Report any post-optimize errors public Parser.ParseException err() { return null; } - /** - * Used to allow repeating tests in the same JVM. This just resets the - * Node unique id generator, and is done as part of making a new Parser. - */ - public static void reset() { - UNIQUE_ID = 1; - _disablePeephole=false; - GVN.clear(); - ITER_CNT = ITER_NOP_CNT = 0; - } - + // Common integer constants + public static ConstantNode con(long x) { return (ConstantNode)(new ConstantNode(TypeInteger.constant(x)).peephole()); } // Utility to walk the entire graph applying a function; return the first // not-null result. - private static final BitSet WVISIT = new BitSet(); final public <E> E walk( Function<Node,E> pred ) { - assert WVISIT.isEmpty(); + assert CODE._visit.isEmpty(); E rez = _walk(pred); - WVISIT.clear(); + CODE._visit.clear(); return rez; } private <E> E _walk( Function<Node,E> pred ) { - if( WVISIT.get(_nid) ) return null; // Been there, done that - WVISIT.set(_nid); + if( CODE._visit.get(_nid) ) return null; // Been there, done that + CODE._visit.set(_nid); E x = pred.apply(this); if( x != null ) return x; for( Node def : _inputs ) if( def != null && (x = def._walk(pred)) != null ) return x; diff --git a/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 784b9146..8d7c4205 100644 --- a/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -13,6 +13,7 @@ public class ParmNode extends PhiNode { super(label,declaredType,inputs); _idx = idx; } + public ParmNode(ParmNode parm) { super(parm, parm._label, parm._declaredType); _idx = parm._idx; } @Override public String label() { return MemOpNode.mlabel(_label); } @@ -22,7 +23,7 @@ public class ParmNode extends PhiNode { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - if( "main".equals(fun().sig()._name) && _label.equals("arg") ) + if( "main".equals(fun()._name) && _label.equals("arg") ) return sb.append("arg"); sb.append("Parm_").append(_label).append("("); for( Node in : _inputs ) { diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 9aed8287..17748afe 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -13,9 +13,11 @@ public class PhiNode extends Node { final Type _declaredType; public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; } + public PhiNode(PhiNode phi, String label, Type declaredType) { super(phi); _label = label; _declaredType = declaredType; } + public PhiNode(PhiNode phi) { super(phi); _label = phi._label; _declaredType = phi._declaredType; } public PhiNode(RegionNode r, Node sample) { - super(r); + super(new Node[]{r}); _label = ""; _declaredType = sample._type; while( nIns() < r.nIns() ) @@ -73,9 +75,6 @@ public class PhiNode extends Node { Node live = singleUniqueInput(); if (live != null) return live; - // No more fancy peeps - if( _disablePeephole ) - return null; // No bother if region is going to fold dead paths soon for( int i=1; i<nIns(); i++ ) diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index ea211dd2..ef7b17e4 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.type.TypeTuple; import java.util.BitSet; -public class ProjNode extends Node implements MultiUse { +public class ProjNode extends Node { // Which slice of the incoming multipart value public final int _idx; @@ -15,13 +15,13 @@ public class ProjNode extends Node implements MultiUse { public final String _label; public ProjNode(Node ctrl, int idx, String label) { - super(ctrl); + super(new Node[]{ctrl}); _idx = idx; _label = label; } + public ProjNode(ProjNode p) { super(p); _idx = p._idx; _label = p._label; } @Override public String label() { return _label; } - @Override public int idx() { return _idx; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { diff --git a/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java b/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java index fddcaa67..b755af3f 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java @@ -10,6 +10,7 @@ import java.util.BitSet; */ public class ReadOnlyNode extends Node { public ReadOnlyNode( Node n ) { super(null,n); } + public ReadOnlyNode( ReadOnlyNode n ) { super(n); } @Override public String label() { return "ReadOnly"; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index ea053c02..5d3db5c6 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -1,20 +1,16 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.*; import com.seaofnodes.simple.type.Type; -import java.util.ArrayList; -import java.util.Arrays; -import java.util.BitSet; -import java.util.HashSet; +import java.util.*; public class RegionNode extends CFGNode { // Source location for late discovered errors public Parser.Lexer _loc; - public RegionNode(Node... nodes) { this(null,nodes); } - public RegionNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc = loc; } + public RegionNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc = loc; } + public RegionNode(RegionNode r, Parser.Lexer loc) { super(r); _loc = loc; } + public RegionNode(RegionNode r) { super(r); _loc = r._loc; } @Override public String label() { return "Region"; } @@ -39,37 +35,16 @@ public class RegionNode extends CFGNode { @Override public Node idealize() { if( inProgress() ) return null; - // Delete dead paths into a Region - int path = findDeadInput(); - if( path != 0 && - // 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. - !(this instanceof LoopNode loop && loop.entry()==in(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 rare occasions we repeat the loop to get - // all the Phis. - int nouts = 0; - while( nouts != nOuts() ) { - nouts = nOuts(); - for( int i=0; i<nOuts(); i++ ) - if( out(i) instanceof PhiNode phi && phi.nIns()==nIns() ) { - phi.delDef(path); - IterPeeps.addAll(phi._outputs); - } - } - return isDead() ? Parser.XCTRL : delDef(path); - } + + Node progress = deadPath(); + if( progress!=null ) return progress; + // If down to a single input, become that input if( nIns()==2 && !hasPhi() ) return in(1); // Collapse if no Phis; 1-input Phis will collapse on their own // If a CFG diamond with no merging, delete: "if( pred ) {} else {};" - if( !_disablePeephole && // Optional - !hasPhi() && // No Phi users, just a control user + if( !hasPhi() && // No Phi users, just a control user in(1) instanceof CProjNode p1 && in(2) instanceof CProjNode p2 && p1.in(0).addDep(this)==p2.in(0).addDep(this) && @@ -84,6 +59,31 @@ public class RegionNode extends CFGNode { return null; } + Node deadPath() { + // Delete dead paths into a Region + int path = findDeadInput(); + 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; + // 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 + // rare occasions we repeat the loop to get all the Phis. + int nouts = 0; + while( nouts != nOuts() ) { + nouts = nOuts(); + for( int i=0; i<nOuts(); i++ ) + if( out(i) instanceof PhiNode phi && phi.nIns()==nIns() ) + CodeGen.CODE.addAll(phi.delDef(path)._outputs); + } + return isDead() ? Parser.XCTRL : delDef(path); + } + + private int findDeadInput() { for( int i=1; i<nIns(); i++ ) if( in(i)._type==Type.XCONTROL ) diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index e543f9ea..20b6c7b9 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -17,12 +17,13 @@ import java.util.BitSet; */ public class ReturnNode extends CFGNode { - public final FunNode _fun; + public FunNode _fun; public ReturnNode(Node ctrl, Node mem, Node data, Node rpc, FunNode fun ) { super(ctrl, mem, data, rpc); _fun = fun; } + public ReturnNode( ReturnNode ret, FunNode fun ) { super(ret); _fun = fun; } public Node ctrl() { return in(0); } public Node mem () { return in(1); } @@ -113,7 +114,7 @@ public class ReturnNode extends CFGNode { } @Override public Parser.ParseException err() { - return mt==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; + return expr()._type/*mt*/==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; } static Parser.ParseException mixerr( boolean ti, boolean tf, boolean tp, boolean tn, Parser.Lexer loc ) { diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index d0d86b79..1208ff63 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -276,7 +276,7 @@ public class ScopeNode extends MemMergeNode { mem()._merge(that.mem(),r); this ._merge(that ,r); that.kill(); // Kill merged scope - IterPeeps.add(r); + CodeGen.CODE.add(r); return r.unkeep(); } @@ -351,7 +351,7 @@ public class ScopeNode extends MemMergeNode { return; // Dead, do not add any guards // Invert the If conditional if( invert ) - pred = pred instanceof NotNode not ? not.in(1) : IterPeeps.add(new NotNode(pred).peephole()); + pred = pred instanceof NotNode not ? not.in(1) : CodeGen.CODE.add(new NotNode(pred).peephole()); // This is a zero/null test. // Compute the positive test type. Type tnz = pred._type.nonZero(); diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 50cba348..26e08535 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.*; import java.util.Arrays; @@ -18,7 +19,8 @@ public class StartNode extends LoopNode implements MultiNode { final Type _arg; - public StartNode(Type arg) { super(null,null); _arg = arg; _type = compute(); } + public StartNode(Type arg) { super((Parser.Lexer)null,null); _arg = arg; _type = compute(); } + public StartNode(StartNode start) { super(start); _arg = start._arg; } @Override public String label() { return "Start"; } @@ -37,7 +39,7 @@ public class StartNode extends LoopNode implements MultiNode { // Find "main", its the start. CFGNode C = null; for( Node use : _outputs ) - if( use instanceof FunNode fun && fun.sig().isa(TypeFunPtr.MAIN) ) + if( use instanceof FunNode fun && fun.sig().isa(CodeGen.CODE._main) ) { assert C==null; C = fun; } return C; } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index feb8347f..6aaba3b3 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -13,6 +13,7 @@ public class StopNode extends CFGNode { _src = src; _type = compute(); } + public StopNode(StopNode stop) { super(stop); _src = stop._src; } @Override public String label() { diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 0fa7d591..93294dba 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -1,8 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.*; import com.seaofnodes.simple.type.*; import java.util.BitSet; @@ -73,33 +71,20 @@ public class StoreNode extends MemOpNode { return this; } - // Simple store-after-new on same address. Should pick up - // an init-store being stomped by a first user store. - if( mem() instanceof ProjNode st && st .in(0) instanceof NewNode nnn && - ptr() instanceof ProjNode ptr && ptr.in(0) == nnn && - ptr()._type instanceof TypeMemPtr tmp && // No bother if weird dead pointers - // Cannot fold a store of a single element over the array body initializer value - !(tmp._obj.isAry() && tmp._obj._fields[1]._alias==_alias) && - // Very sad strong cutout: val has to be legal to hoist to a New - // input, which means it cannot depend on the New. Many, many - // things are legal here but difficult to check without doing a - // full dominator check. Example failure: - // "struct C { C? c; }; C self = new C { c=self; }" - val()._type.isHighOrConst() && - // Must have exactly one use of "this" or you get weird - // non-serializable memory effects in the worse case. - checkOnlyUse(st) && - // Folding away a broken store - err()==null ) { - nnn.setDef(nnn.findAlias(_alias),val()); - // Must *retype* the NewNode, this is not monotonic in isolation - // but is monotonic counting from this Store to the New. - nnn ._type = nnn .compute(); - mem()._type = mem().compute(); - IterPeeps.addAll(nnn._outputs); - return mem(); + // Value is automatically truncated by narrow store + if( val() instanceof AndNode and && and.in(2)._type.isConstant() ) { + int log = _declaredType.log_size(); + if( log<3 ) { // And-mask vs narrow store + long mask = ((TypeInteger)and.in(2)._type).value(); + long bits = (1L<<(8<<log))-1; + // Mask does not mask any of the stored bits + if( (bits&mask)==bits ) + // So and-mask is already covered by the store + { setDef(4,and.in(1)); return this; } + } } + return null; } @@ -119,9 +104,10 @@ public class StoreNode extends MemOpNode { Parser.ParseException err = super.err(); if( err != null ) return err; TypeMemPtr tmp = (TypeMemPtr)ptr()._type; - if( tmp._obj.field(_name)._final && !"[]".equals(_name) ) + if( tmp._obj.field(_name)._final && !_init ) return Parser.error("Cannot modify final field '"+_name+"'",_loc); Type t = val()._type; - return _init || t.isa(_declaredType) ? null : Parser.error("Cannot store "+t+" into field "+_declaredType+" "+_name,_loc); + //return _init || t.isa(_declaredType) ? null : Parser.error("Cannot store "+t+" into field "+_declaredType+" "+_name,_loc); + return null; } } diff --git a/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java index 3c6a5df3..9b4245c7 100644 --- a/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java @@ -1,11 +1,12 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import java.util.BitSet; public class XCtrlNode extends CFGNode { - public XCtrlNode() { super(Parser.START); } + public XCtrlNode() { super(new Node[]{CodeGen.CODE._start}); } @Override public String label() { return "Xctrl"; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Xctrl"); } @Override public boolean isConst() { return true; } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddFMemX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddFMemX86.java new file mode 100644 index 00000000..4f75edcd --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddFMemX86.java @@ -0,0 +1,33 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.node.*; + +public class AddFMemX86 extends MemOpX86 { + AddFMemX86( AddFNode add, LoadNode ld , Node base, Node idx, int off, int scale, Node val ) { + super(add,ld, base, idx, off, scale, 0, val ); + } + + @Override public RegMask regmap(int i) { + if( i==1 ) return RegMask.EMPTY; // Memory + if( i==2 ) return x86_64_v2.RMASK; // base + if( i==3 ) return x86_64_v2.RMASK; // index + if( i==4 ) return x86_64_v2.XMASK; // value + throw Utils.TODO(); + } + + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.XMASK; } + + + // General form: "add dst = src + [base + idx<<2 + 12]" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = "); + sb.p(val()==null ? "#"+_imm : code.reg(val())).p(" + "); + asm_address(code,sb); + } + @Override public String op() { return "addf"+_sz; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddFX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddFX86.java new file mode 100644 index 00000000..a3f5c7b3 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddFX86.java @@ -0,0 +1,29 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class AddFX86 extends MachConcreteNode implements MachNode { + AddFX86( Node addf ) { super(addf); } + + // Register mask allowed on input i. + @Override public RegMask regmap(int i) { assert i==1 || i==2; return x86_64_v2.XMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.XMASK; } + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form: "addf dst += src" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" + ").p(code.reg(in(2))); + } + + @Override public String op() { return "addf"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddIX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddIX86.java new file mode 100644 index 00000000..6a332ff5 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddIX86.java @@ -0,0 +1,39 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class AddIX86 extends MachConcreteNode implements MachNode { + final TypeInteger _ti; + AddIX86( Node add, TypeInteger ti ) { + super(add); + _inputs.pop(); + _ti = ti; + } + + // Register mask allowed on input i. + @Override public RegMask regmap(int i) { + // assert i== i; + return x86_64_v2.WMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form: "addi dst += #imm" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" + #"); + _ti.print(sb); + } + + @Override public String op() { + return _ti.value() == 1 ? "inc" : (_ti.value() == -1 ? "dec" : "addi"); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddMemX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddMemX86.java new file mode 100644 index 00000000..7d45d757 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddMemX86.java @@ -0,0 +1,25 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.node.*; + +public class AddMemX86 extends MemOpX86 { + AddMemX86( AddNode add, LoadNode ld , Node base, Node idx, int off, int scale, int imm, Node val ) { + super(add,ld, base, idx, off, scale, imm, val ); + } + + @Override public String op() { return "add"+_sz; } + + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + + // General form: "add dst = src + [base + idx<<2 + 12]" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = "); + sb.p(val()==null ? "#"+_imm : code.reg(val())).p(" + "); + asm_address(code,sb); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddX86.java new file mode 100644 index 00000000..61aa5a9e --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddX86.java @@ -0,0 +1,29 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class AddX86 extends MachConcreteNode implements MachNode { + AddX86( Node add ) { super(add); } + + // Register mask allowed on input i. + @Override public RegMask regmap(int i) { assert i==1 || i==2; return x86_64_v2.RMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form: "add dst += src" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" + ").p(code.reg(in(2))); + } + + @Override public String op() { return "add"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AndIX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AndIX86.java new file mode 100644 index 00000000..f2ee1c66 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AndIX86.java @@ -0,0 +1,42 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; +import java.util.BitSet; +import java.lang.StringBuilder; + +public class AndIX86 extends MachConcreteNode implements MachNode { + final TypeInteger _ti; + AndIX86(Node and, TypeInteger ti) { + super(and); + _inputs.pop(); + _ti = ti; + } + + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { assert i==1; return x86_64_v2.WMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "andi dst & #imm" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" & #"); + _ti.print(sb); + } + + @Override public String op() { return "andi"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java new file mode 100644 index 00000000..31d303ed --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFunPtr; +import java.io.ByteArrayOutputStream; + +public class CallRX86 extends CallNode implements MachNode { + CallRX86( CallNode call ) { super(call); } + + @Override public String label() { return op(); } + @Override public RegMask regmap(int i) { + return i==_inputs._len + ? x86_64_v2.WMASK // Function call target + : x86_64_v2.callInMask(i); // Normal argument + } + @Override public RegMask outregmap() { return x86_64_v2.RET_MASK; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(fptr())); + } + + @Override public String op() { return "callr"; } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java new file mode 100644 index 00000000..9c246c24 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java @@ -0,0 +1,40 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFunPtr; +import java.io.ByteArrayOutputStream; +import java.util.BitSet; + +public class CallX86 extends CallNode implements MachNode { + final TypeFunPtr _tfp; + final String _name; + CallX86( CallNode call, TypeFunPtr tfp ) { + super(call); + _inputs.pop(); // Pop constant target + assert tfp.isConstant(); + _tfp = tfp; + _name = CodeGen.CODE.link(tfp)._name; + } + + @Override public String label() { return op(); } + @Override public RegMask regmap(int i) { + return x86_64_v2.callInMask(i); // Normal argument + } + @Override public RegMask outregmap() { return x86_64_v2.RET_MASK; } + + @Override public String name() { return _name; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + @Override public void asm(CodeGen code, SB sb) { + sb.p(_name); + } + + @Override public String op() { return "call"; } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpIX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpIX86.java new file mode 100644 index 00000000..2fa7fbb1 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpIX86.java @@ -0,0 +1,43 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +// Compare immediate. Sets flags. +public class CmpIX86 extends MachConcreteNode implements MachNode { + final int _imm; + final String _bop; + CmpIX86( BoolNode bool, TypeInteger ti ) { + super(bool); + _inputs.pop(); // Toss ideal ConstantNode away, embedded into machine op + _bop = bool.op(); // One of <,<=,== + _imm = (int)ti.value(); + assert _imm == ti.value(); + } + CmpIX86( Node cmp, double ignore ) { + super(cmp); + _bop = "=="; + _imm = 0; + } + + @Override public RegMask regmap(int i) { assert i==1; return x86_64_v2.RMASK; } + @Override public RegMask outregmap() { return x86_64_v2.FLAGS_MASK; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + @Override public void asm(CodeGen code, SB sb) { + String dst = code.reg(this); + if( dst!="FLAGS" ) sb.p(dst).p(" = "); + sb.p(code.reg(in(1))); + if( _imm != 0 ) sb.p(", #").p(_imm); + } + + @Override public String op() { return _imm==0 ? "test" : "cmp"; } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java new file mode 100644 index 00000000..873ca9df --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java @@ -0,0 +1,33 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.node.*; + +public class CmpMemX86 extends MemOpX86 { + final boolean _invert; // Op switched LHS, RHS + CmpMemX86( BoolNode bool, LoadNode ld , Node base, Node idx, int off, int scale, int imm, Node val, boolean invert ) { + super(bool,ld, base, idx, off, scale, imm, val ); + _invert = invert; + } + + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.FLAGS_MASK; } + + // General form: "cmp dst = src, [base + idx<<2 + 12]" + @Override public void asm(CodeGen code, SB sb) { + String dst = code.reg(this); + if( dst!="FLAGS" ) sb.p(dst).p(" = "); + if( _invert ) asm_address(code,sb).p(","); + if( val()==null ) { + if( _imm!=0 ) sb.p("#").p(_imm); + } else { + sb.p(code.reg(val())); + } + if( !_invert ) asm_address(code,sb.p(", ")); + } + + @Override public String op() { return ((val()==null && _imm==0) ? "test" : "cmp") + _sz; } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java new file mode 100644 index 00000000..6b502249 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java @@ -0,0 +1,27 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class CmpX86 extends MachConcreteNode implements MachNode { + CmpX86( Node cmp ) { super(cmp); } + + @Override public RegMask regmap(int i) { assert i==1 || i==2; return x86_64_v2.RMASK; } + @Override public RegMask outregmap() { return x86_64_v2.FLAGS_MASK; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form: "add dst += src" + @Override public void asm(CodeGen code, SB sb) { + String dst = code.reg(this); + if( dst!="FLAGS" ) sb.p(dst).p(" = "); + sb.p(code.reg(in(1))).p(", ").p(code.reg(in(2))); + } + + @Override public String op() { return "cmp"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivFX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivFX86.java new file mode 100644 index 00000000..d73bfd5b --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivFX86.java @@ -0,0 +1,33 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class DivFX86 extends MachConcreteNode implements MachNode { + DivFX86( Node divf) { super(divf); } + + // Register mask allowed on input i. + @Override public RegMask regmap(int i) { assert i==1 || i==2; return x86_64_v2.XMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.XMASK; } + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + + // General form: "divf dst /= src" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" / ").p(code.reg(in(2))); + } + + @Override public String op() { + // 8 bytes = 64 bits + return "divf"; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java new file mode 100644 index 00000000..1dc20017 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class DivX86 extends MachConcreteNode implements MachNode { + DivX86( Node div ) { super(div); } + + // Register mask allowed on input i. + @Override public RegMask regmap(int i) { + assert i==1 || i==2; + return x86_64_v2.RMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form: "div dst /= src" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" / ").p(code.reg(in(2))); + } + + @Override public String op() { return "div"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FltX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FltX86.java new file mode 100644 index 00000000..21529f7b --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FltX86.java @@ -0,0 +1,36 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.MachNode; + +import java.io.ByteArrayOutputStream; + +public class FltX86 extends ConstantNode implements MachNode { + FltX86(ConstantNode con ) { super(con); } + + // Register mask allowed on input i. 0 for no register. + @Override public RegMask regmap(int i) { return RegMask.EMPTY; } + // General int registers + @Override public RegMask outregmap() { return x86_64_v2.XMASK; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // Human-readable form appended to the SB. Things like the encoding, + // indentation, leading address or block labels not printed here. + // Just something like "ld4\tR17=[R18+12] // Load array base". + // General form: "op\tdst=src+src" + @Override public void asm(CodeGen code, SB sb) { + _con.print(sb.p(code.reg(this)).p(" #")); + } + + @Override public String op() { + return "fld"; // Some fancier encoding + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FunX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FunX86.java new file mode 100644 index 00000000..f969fae4 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FunX86.java @@ -0,0 +1,21 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.FunNode; +import com.seaofnodes.simple.node.MachNode; +import java.io.ByteArrayOutputStream; + +public class FunX86 extends FunNode implements MachNode { + FunX86( FunNode fun ) { super(fun); } + + // Register mask allowed on input i. 0 for no register. + @Override public RegMask regmap(int i) { return RegMask.EMPTY; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return RegMask.EMPTY; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/I2f8X86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/I2f8X86.java new file mode 100644 index 00000000..983f817d --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/I2f8X86.java @@ -0,0 +1,28 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class I2f8X86 extends MachConcreteNode implements MachNode { + I2f8X86(Node i2f8 ) { super(i2f8); } + + // Register mask allowed on input i. + @Override public RegMask regmap(int i) { assert i==1; return x86_64_v2.WMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.XMASK; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form: "i2f8 (flt)int_value" + + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p("(flt)").p(code.reg(in(1))); + } + + @Override public String op() { return "i2f8"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/IntX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/IntX86.java new file mode 100644 index 00000000..2cd27c14 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/IntX86.java @@ -0,0 +1,45 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +import java.io.ByteArrayOutputStream; + +// Integer constants +public class IntX86 extends ConstantNode implements MachNode { + + IntX86( ConstantNode con ) { + super(con); + } + + // Register mask allowed on input i. 0 for no register. + @Override public RegMask regmap(int i) { return RegMask.EMPTY; } + // General int registers + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // Human-readable form appended to the SB. Things like the encoding, + // indentation, leading address or block labels not printed here. + // Just something like "ld4\tR17=[R18+12] // Load array base". + // General form: "op\tdst=src+src" + @Override public void asm(CodeGen code, SB sb) { + String reg = code.reg(this); + if( _con == Type.NIL || _con == TypeInteger.ZERO ) + sb.p(reg).p(",").p(reg); + else + _con.print(sb.p(reg).p(" #")); + } + + @Override public String op() { + if( _con == Type.NIL || _con == TypeInteger.ZERO ) + return "xor"; + return "ldi"; // Some fancier encoding + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java new file mode 100644 index 00000000..7cf4444c --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java @@ -0,0 +1,46 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +// Jump on flags, uses flags +public class JmpX86 extends IfNode implements MachNode { + final String _bop; + JmpX86( IfNode iff, String bop ) { + super(iff); + _bop = bop; + } + + @Override public String label() { return op(); } + + @Override public void postSelect() { + Node set = in(1); + Node cmp = set.in(1); + // Bypass an expected Set and just reference the cmp directly + if( set instanceof SetX86 && (cmp instanceof CmpX86 || cmp instanceof CmpIX86 || cmp instanceof CmpMemX86) ) + _inputs.set(1,cmp); + else + throw Utils.TODO(); + } + @Override public RegMask regmap(int i) { assert i==1; return x86_64_v2.FLAGS_MASK; } + @Override public RegMask outregmap() { return RegMask.EMPTY; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + @Override public void asm(CodeGen code, SB sb) { + String src = code.reg(in(1)); + if( src!="FLAGS" ) sb.p(src); + } + + @Override public String op() { return "j"+_bop; } + + @Override public String comment() { + return "L"+cproj(1)._nid+", L"+cproj(0)._nid; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/LeaX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/LeaX86.java new file mode 100644 index 00000000..a49b8d7f --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/LeaX86.java @@ -0,0 +1,42 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class LeaX86 extends MachConcreteNode implements MachNode { + final int _scale; + final long _offset; + LeaX86( Node add, Node base, Node idx, int scale, long offset ) { + super(add); + assert scale==1 || scale==2 || scale==4 || scale==8; + _inputs.pop(); + _inputs.pop(); + _inputs.push(base); + _inputs.push(idx); + _scale = scale; + _offset = offset; + } + + // Register mask allowed on input i. + @Override public RegMask regmap(int i) { assert i==1 || i==2; return x86_64_v2.RMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form: "lea dst = base + 4*idx + 12" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = "); + if( in(1) != null ) + sb.p(code.reg(in(1))).p(" + "); + sb.p(code.reg(in(2))).p("*").p(_scale); + if( _offset!=0 ) sb.p(" + #").p(_offset); + } + + @Override public String op() { return "lea"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/LoadX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/LoadX86.java new file mode 100644 index 00000000..02a9a4fe --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/LoadX86.java @@ -0,0 +1,25 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.node.LoadNode; +import com.seaofnodes.simple.node.Node; + +public class LoadX86 extends MemOpX86 { + LoadX86( LoadNode ld, Node base, Node idx, int off, int scale ) { + super(ld,ld, base, idx, off, scale, 0); + } + + @Override public String op() { return "ld"+_sz; } + + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + + // General form: "ldN dst,[base + idx<<2 + 12]" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(","); + asm_address(code,sb); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemAddX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemAddX86.java new file mode 100644 index 00000000..418f63f3 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemAddX86.java @@ -0,0 +1,28 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.node.*; + +public class MemAddX86 extends MemOpX86 { + MemAddX86( StoreNode st, Node base, Node idx, int off, int scale, int imm, Node val ) { + super(st, st, base, idx, off, scale, imm, val ); + } + + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return RegMask.EMPTY; } + + + // General form: "add [base + idx<<2 + 12] += src" + @Override public void asm(CodeGen code, SB sb) { + asm_address(code,sb); + if( val()==null ) { + if( _imm != 1 && _imm != -1 ) sb.p(" += #").p(_imm); + } else sb.p(" += ").p(code.reg(val())); + } + + @Override public String op() { + return (_imm == 1 ? "inc" : (_imm == -1 ? "dec" : "add")) + _sz; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java new file mode 100644 index 00000000..1e678a0b --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java @@ -0,0 +1,87 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import java.io.ByteArrayOutputStream; +import java.lang.StringBuilder; +import java.util.BitSet; + +// Generic X86 memory operand base. +// inputs: +// ctrl - will appear for possibly RCE (i.e. array ops) +// mem - memory dependence edge +// base - Basic object pointer +// idx/null - Scaled index offset, or null if none +// val/null - Value to store, as part of a op-to-mem or op-from-mem. Null for loads, or if an immediate is being used +// Constants: +// offset - offset added to base. Can be zero. +// scale - scale on index; only 0,1,2,4,8 allowed, 0 is only when index is null +// imm - immediate value to store or op-to-mem, and only when val is null +public abstract class MemOpX86 extends MemOpNode implements MachNode { + final int _off; // Limit 32 bits + final int _scale; // Limit 0,1,2,3 + final int _imm; // Limit 32 bits + final char _sz = (char)('0'+(1<<_declaredType.log_size())); + MemOpX86( Node op, MemOpNode mop, Node base, Node idx, int off, int scale, int imm ) { + super(op,mop); + assert base._type instanceof TypeMemPtr && !(base instanceof AddNode); + assert (idx==null && scale==0) || (idx!=null && 0<= scale && scale<=3); + + // Copy memory parts from eg the LoadNode over the opcode, e.g. an Add + if( op != mop ) { + _inputs.set(0,mop.in(0)); // Control from mem op + _inputs.set(1,mop.in(1)); // Memory from mem op + _inputs.set(2,base); // Base handed in + } + + assert ptr() == base; + _inputs.setX(3,idx); + _off = off; + _scale = scale; + _imm = imm; + } + + // Store-based flavors have a value edge + MemOpX86( Node op, MemOpNode mop, Node base, Node idx, int off, int scale, int imm, Node val ) { + this(op,mop,base,idx,off,scale,imm); + _inputs.setX(4,val); + } + + Node idx() { return in(3); } + Node val() { return in(4); } + + @Override public StringBuilder _printMach(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); } + + @Override public String label() { return op(); } + @Override public Type compute() { throw Utils.TODO(); } + @Override public Node idealize() { throw Utils.TODO(); } + + // Register mask allowed on input i. + @Override public RegMask regmap(int i) { + if( i==1 ) return RegMask.EMPTY; // Memory + if( i==2 ) return x86_64_v2.RMASK; // base + if( i==3 ) return x86_64_v2.RMASK; // index + if( i==4 ) return x86_64_v2.RMASK; // value + throw Utils.TODO(); + } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { throw Utils.TODO(); } + + @Override public int encoding(ByteArrayOutputStream bytes) { throw Utils.TODO(); } + + + // "[base + idx<<2 + 12]" + SB asm_address(CodeGen code, SB sb) { + sb.p("[").p(code.reg(ptr())); + if( idx() != null ) { + sb.p("+").p(code.reg(idx())); + if( _scale != 0 ) + sb.p("<<").p(_scale); + } + if( _off != 0 ) + sb.p("+").p(_off); + return sb.p("]"); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulFX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulFX86.java new file mode 100644 index 00000000..aef813e1 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulFX86.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeFloat; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class MulFX86 extends MachConcreteNode implements MachNode { + MulFX86( Node mulf) { super(mulf); } + + // Register mask allowed on input i. + @Override public RegMask regmap(int i) { assert i==1 || i==2; return x86_64_v2.XMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.XMASK; } + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form: "mulf dst *= src" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" * ").p(code.reg(in(2))); + } + + @Override public String op() { return "mulf"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulIX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulIX86.java new file mode 100644 index 00000000..7508cf4c --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulIX86.java @@ -0,0 +1,36 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class MulIX86 extends MachConcreteNode implements MachNode { + final TypeInteger _ti; + MulIX86(Node mul, TypeInteger ti) {super(mul); _inputs.pop(); _ti = ti;} + + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { + // assert i==1; + return x86_64_v2.WMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + // General form + // General form: "muli dst * #imm" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" * #"); + _ti.print(sb); + } + + @Override public String op() { return "muli"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulX86.java new file mode 100644 index 00000000..15fd9496 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulX86.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class MulX86 extends MachConcreteNode implements MachNode { + + MulX86( Node mul ) { super(mul); } + + // Register mask allowed on input i. + @Override public RegMask regmap(int i) { assert i==1 || i==2; return x86_64_v2.RMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form: "mul dst *= src" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" * ").p(code.reg(in(2))); + } + + @Override public String op() { return "mul"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NewX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NewX86.java new file mode 100644 index 00000000..4396a917 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NewX86.java @@ -0,0 +1,40 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import java.io.ByteArrayOutputStream; + +public class NewX86 extends NewNode implements MachNode { + + // A pre-zeroed chunk of memory. + NewX86( NewNode nnn ) { super(nnn); } + + // Register mask allowed on input i, the size + @Override public RegMask regmap(int i) { + // Size + if( i==1 ) return x86_64_v2.RDI_MASK; + // All the memory alias edges + return RegMask.EMPTY; + } + @Override public RegMask outregmap() { throw Utils.TODO(); } + + // Register mask allowed as a result. Pointer result in standard calling + // convention. + @Override public RegMask outregmap(int i) { + if( i == 1 ) return x86_64_v2.RET_MASK; + // All the memory aliases edges + return RegMask.EMPTY; + } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form: "alloc #bytes" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(size())); + } + + @Override public String op() { return "alloc"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/OrIX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/OrIX86.java new file mode 100644 index 00000000..513962c2 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/OrIX86.java @@ -0,0 +1,44 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.MachConcreteNode; +import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.TypeInteger; + +import java.io.ByteArrayOutputStream; + +public class OrIX86 extends MachConcreteNode implements MachNode { + + final TypeInteger _ti; + OrIX86(Node or, TypeInteger ti) {super(or); _inputs.pop(); _ti = ti;} + + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { + //assert i==1; + return x86_64_v2.WMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "ori ori | #imm" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" | #"); + _ti.print(sb); + } + + @Override public String op() { return "ori"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ParmX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ParmX86.java new file mode 100644 index 00000000..8a439644 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ParmX86.java @@ -0,0 +1,24 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.ParmNode; +import com.seaofnodes.simple.node.MachNode; +import java.io.ByteArrayOutputStream; + +public class ParmX86 extends ParmNode implements MachNode { + final RegMask _rmask; + ParmX86( ParmNode parm ) { + super(parm); + _rmask = x86_64_v2.callInMask(_idx); + } + + // Register mask allowed on input i. 0 for no register. + @Override public RegMask regmap(int i) { return RegMask.EMPTY; } + // Register mask allowed as a result. Calling convention register + @Override public RegMask outregmap() { return _rmask; } + + // Encoding is appended into the byte array. Returns size + @Override public int encoding(ByteArrayOutputStream bytes) { return 0; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ProjX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ProjX86.java new file mode 100644 index 00000000..2849b232 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ProjX86.java @@ -0,0 +1,23 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.ProjNode; +import com.seaofnodes.simple.node.MachNode; +import java.io.ByteArrayOutputStream; + +public class ProjX86 extends ProjNode implements MachNode { + + ProjX86( ProjNode p ) { super(p); } + + // Register mask allowed on input i. 0 for no register. + @Override public RegMask regmap(int i) { return RegMask.EMPTY; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return RegMask.EMPTY; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RetX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RetX86.java new file mode 100644 index 00000000..e6219ff4 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RetX86.java @@ -0,0 +1,48 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.FunNode; +import com.seaofnodes.simple.node.ReturnNode; +import com.seaofnodes.simple.node.MachNode; +import java.io.ByteArrayOutputStream; + +// Return +public class RetX86 extends ReturnNode implements MachNode { + RetX86( ReturnNode ret, FunNode fun ) { super(ret, fun); fun.setRet(this); } + + // Correct Nodes outside the normal edges + @Override public void postSelect() { + FunNode fun = (FunNode)rpc().in(0); + _fun = fun; + fun.setRet(this); + } + + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { + return switch( i ) { + case 0 -> RegMask.EMPTY; + case 1 -> RegMask.EMPTY; + case 2 -> x86_64_v2.RET_MASK; + case 3 -> RegMask.EMPTY; // RPC is always on stack + default -> throw Utils.TODO(); + }; + } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return RegMask.EMPTY; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // Human-readable form appended to the SB. Things like the encoding, + // indentation, leading address or block labels not printed here. + // Just something like "ld4\tR17=[R18+12] // Load array base". + // General form: "op\tdst=src+src" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(in(2))); + } + + @Override public String op() { return "ret"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarX86.java new file mode 100644 index 00000000..3d907eef --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarX86.java @@ -0,0 +1,40 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; +import java.util.BitSet; +import java.lang.StringBuilder; + + +public class SarX86 extends MachConcreteNode implements MachNode { + final TypeInteger _ti; + SarX86(Node sar, TypeInteger ti) {super(sar); _inputs.pop(); _ti = ti;} + + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { + // assert i==1; + return x86_64_v2.RMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "sari dst << #imm" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" >> #"); + _ti.print(sb); + } + + @Override public String op() { return "sari"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SetX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SetX86.java new file mode 100644 index 00000000..25367e03 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SetX86.java @@ -0,0 +1,39 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +// Compare immediate. Sets flags. +// Corresponds to the x86 instruction "sete && setne". +// Use result of comparison without jump. +public class SetX86 extends MachConcreteNode implements MachNode { + final String _bop; // One of <,<=,== + // Constructor expects input is an X86 and not an Ideal node. + SetX86( Node cmp, String bop ) { + super(cmp); + _inputs.setLen(1); // Pop the cmp inputs + // Replace with the matched cmp + _inputs.push(cmp); + _bop = bop; + } + + @Override public RegMask regmap(int i) { assert i==1; return x86_64_v2.FLAGS_MASK; } + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)); + String src = code.reg(in(1)); + if( src!="FLAGS" ) sb.p(" = ").p(src); + } + + @Override public String op() { return "set"+_bop; } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShlIX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShlIX86.java new file mode 100644 index 00000000..61e0d262 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShlIX86.java @@ -0,0 +1,38 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; +import java.util.BitSet; + +public class ShlIX86 extends MachConcreteNode implements MachNode{ + final TypeInteger _ti; + ShlIX86(Node shl, TypeInteger ti) {super(shl); _inputs.pop(); _ti = ti;} + + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { + //assert i==1; + return x86_64_v2.RMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "shli dst << #imm" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" << #"); + _ti.print(sb); + } + + @Override public String op() { return "shli"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrIX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrIX86.java new file mode 100644 index 00000000..08cae93e --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrIX86.java @@ -0,0 +1,39 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; +import java.util.BitSet; +import java.lang.StringBuilder; + +public class ShrIX86 extends MachConcreteNode implements MachNode{ + final TypeInteger _ti; + ShrIX86(Node shr, TypeInteger ti) {super(shr); _inputs.pop(); _ti = ti;} + + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { + //assert i==1; + return x86_64_v2.RMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "shri dst >>> #imm" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" >>> #"); + _ti.print(sb); + } + + @Override public String op() { return "shri"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/StoreX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/StoreX86.java new file mode 100644 index 00000000..c9191b87 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/StoreX86.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.StoreNode; +import java.util.BitSet; + +public class StoreX86 extends MemOpX86 { + StoreX86( StoreNode st, Node base, Node idx, int off, int scale, int imm, Node val ) { + super(st,st, base, idx, off, scale, imm, val); + } + + @Override public String op() { return "st"+_sz; } + + @Override public StringBuilder _printMach(StringBuilder sb, BitSet visited) { + return sb.append(".").append(_name).append("=").append(val()==null ? _imm : val()).append(";"); + } + + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return RegMask.EMPTY; } + + // General form: "stN [base + idx<<2 + 12],val" + @Override public void asm(CodeGen code, SB sb) { + asm_address(code,sb).p(","); + if( val()==null ) sb.p("#").p(_imm); + else sb.p(code.reg(val())); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SubFX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SubFX86.java new file mode 100644 index 00000000..ed19ad79 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SubFX86.java @@ -0,0 +1,29 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import java.io.ByteArrayOutputStream; + +public class SubFX86 extends MachConcreteNode implements MachNode { + SubFX86( Node subf) { super(subf); } + + + // Register mask allowed on input i. + @Override public RegMask regmap(int i) { assert i==1 || i==2; return x86_64_v2.XMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.XMASK; } + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form: "subf dst -= src" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" - ").p(code.reg(in(2))); + } + + @Override public String op() { return "subf"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SubX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SubX86.java new file mode 100644 index 00000000..cac59d3b --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SubX86.java @@ -0,0 +1,29 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class SubX86 extends MachConcreteNode implements MachNode { + SubX86( Node sub ) { super(sub); } + + // Register mask allowed on input i. + @Override public RegMask regmap(int i) { assert i==1 || i==2; return x86_64_v2.RMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form: "sub dst -= src" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" - ").p(code.reg(in(2))); + } + + @Override public String op() { return "sub"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java new file mode 100644 index 00000000..bd88011f --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFunPtr; + +import java.io.ByteArrayOutputStream; + +// Function constants +public class TFPX86 extends ConstantNode implements MachNode { + TFPX86( ConstantNode con ) { super(con); } + // Register mask allowed on input i. 0 for no register. + @Override public RegMask regmap(int i) { return RegMask.EMPTY; } + // General int registers + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // Human-readable form appended to the SB. Things like the encoding, + // indentation, leading address or block labels not printed here. + // Just something like "ld4\tR17=[R18+12] // Load array base". + // General form: "op\tdst=src+src" + @Override public void asm(CodeGen code, SB sb) { + String reg = code.reg(this); + if( _con == Type.NIL ) + sb.p(reg).p(",").p(reg); + else + _con.print(sb.p(reg).p(" #")); + } + + @Override public String op() { + if( _con == Type.NIL ) + return "xor"; + return "ldx"; // Some fancier encoding + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/XorIX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/XorIX86.java new file mode 100644 index 00000000..795fa814 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/XorIX86.java @@ -0,0 +1,42 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.MachConcreteNode; +import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.TypeInteger; + +import java.io.ByteArrayOutputStream; + +public class XorIX86 extends MachConcreteNode implements MachNode { + + final TypeInteger _ti; + XorIX86(Node xor, TypeInteger ti) {super(xor); _inputs.pop(); _ti = ti;} + + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { assert i==1; return x86_64_v2.WMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "ori xori ^ #imm" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" ^ #"); + _ti.print(sb); + } + + @Override public String op() { return "xori"; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java new file mode 100644 index 00000000..45ae19dc --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -0,0 +1,418 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.Machine; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + +public class x86_64_v2 extends Machine { + // X86-64 V2. Includes e.g. SSE4.2 and POPCNT. + @Override public String name() { return "x86_64_v2"; } + + public static int RAX = 0, RCX = 1, RDX = 2, RBX = 3, RSP = 4, RBP = 5, RSI = 6, RDI = 7; + public static int R08 = 8, R09 = 9, R10 = 10, R11 = 11, R12 = 12, R13 = 13, R14 = 14, R15 = 15; + public static int FLAGS = 32; + + public static int XMM0 = 16, XMM1 = 17, XMM2 = 18, XMM3 = 19, XMM4 = 20, XMM5 = 21, XMM6 = 22, XMM7 = 23; + public static int XMM8 = 24, XMM9 = 25, XMM10 = 26, XMM11 = 27, XMM12 = 28, XMM13 = 29, XMM14 = 30, XMM15 = 31; + + // General purpose register mask: pointers and ints, not floats + public static RegMask RMASK = new RegMask(0b1111111111111111); + // No RSP in the *write* general set. + public static RegMask WMASK = new RegMask(0b1111111111101111); + // Xmm register mask + public static RegMask XMASK = new RegMask( 0b1111111111111111L << XMM0); + + public static RegMask FLAGS_MASK = new RegMask(1L<<FLAGS); + + // Return single int/ptr register + public static RegMask RET_MASK = new RegMask(RAX); + + public static RegMask RDI_MASK = new RegMask(1L<<RDI); + public static RegMask RCX_MASK = new RegMask(1L<<RCX); + public static RegMask RDX_MASK = new RegMask(1L<<RDX); + public static RegMask R08_MASK = new RegMask(1L<<R08); + public static RegMask R09_MASK = new RegMask(1L<<R09); + public static RegMask RSI_MASK = new RegMask(1L<<RSI); + + // Calling conv metadata + public int GPR_COUNT_CONV_WIN64 = 4; // RCX, RDX, R9, R9 + public int XMM_COUNT_CONV_WIN64 = 4; // XMM0L, XMM1L, XMM2L, XMM3L + + public int GPR_COUNT_CONV_SYSTEM_V = 6; // RDI, RSI, RDX, RCX, R8, R9 + public int XMM_COUNT_CONV_SYSTEM_V = 4; // XMM0, XMM1, XMM2, XMM3 .... + // Human-readable name for a register number, e.g. "RAX". + // Hard crash for bad register number, fix yer bugs! + public static final String[] REGS = new String[] { + "rax" , "rcx" , "rdx" , "rbx" , "rsp" , "rbp" , "rsi" , "rdi" , + "r8" , "r9" , "r10" , "r11" , "r12" , "r13" , "r14" , "r15" , + "xmm0", "xmm1", "xmm2" , "xmm3" , "xmm4" , "xmm5" , "xmm6" , "xmm7" , + "xmm8", "xmm9", "xmm10", "xmm11", "xmm12", "xmm13", "xmm14", "xmm15", + }; + @Override public String reg( int reg ) { return REGS[reg]; } + + // Calling convention; returns a machine-specific register + // for incoming argument idx. + // index 0 for control, 1 for memory, real args start at index 2 + static int callInArg( int idx ) { + return switch( CodeGen.CODE._callingConv ) { + case CodeGen.CallingConv.SystemV -> callInArgSystemV(idx); + case CodeGen.CallingConv.Win64 -> callInArgWin64 (idx); + }; + } + + // WIN64(param passing) + static RegMask[] CALLINMASK_WIN64 = new RegMask[] { + RegMask.EMPTY, + RegMask.EMPTY, + RCX_MASK, + RDX_MASK, + R08_MASK, + R09_MASK, + RegMask.EMPTY, + RegMask.EMPTY + }; + static int[] CALLINARG_WIN64 = new int[] { + 0, // Control, no register + 0, // Memory, no register + RCX, // + RDX, + R08, + R09, + 0, + 0, + }; + static int callInArgWin64( int idx ) { return CALLINARG_WIN64[idx]; } + + // caller saved(win64) + public static final long WIN64_ABI_CALLER_SAVED = + (1L << RAX) | (1L << RCX) | (1L << RDX) | (1L << R08) | (1L << R09) | (1L << R10) | (1L << R11); + + // callee saved(win64) + public static final long WIN64_ABI_CALLEE_SAVED = ~WIN64_ABI_CALLER_SAVED; + + // SystemV(param passing) + static RegMask[] CALLINMASK_SYSTEMV = new RegMask[] { + RegMask.EMPTY, + RegMask.EMPTY, + RDI_MASK, + RSI_MASK, + RDX_MASK, + RCX_MASK, + R08_MASK, + R09_MASK + }; + static int[] CALLINARG_SYSTEMV = new int[] { + 0, // Control, no register + 0, // Memory, no register + RDI, + RSI, + RDX, + RCX, + R08, + R09, + }; + static int callInArgSystemV( int idx ) { return CALLINARG_SYSTEMV[idx]; } + + // caller saved(systemv) + // caller saved(win64) + public static final long SYSTEMV_ABI_CALLER_SAVED = + (1L << RAX) | (1L << RDI) | (1L << RSI) | (1L << RCX) | (1L << RDX) | (1L << R08) | (1L << R09) << (1L << R10) << (1L << R11); + // callee saved(systemv) + public static final long SYSTEMV_ABI_CALLE_SAVED = ~SYSTEMV_ABI_CALLER_SAVED; + + + static RegMask callInMask( int idx ) { + return switch( CodeGen.CODE._callingConv ) { + case CodeGen.CallingConv.SystemV -> CALLINMASK_SYSTEMV[idx]; + case CodeGen.CallingConv.Win64 -> CALLINMASK_WIN64 [idx]; + }; + } + + // Create a split op; any register to any register, including stack slots + @Override public Node split() { + throw Utils.TODO(); + } + + // Return a MachNode unconditional branch + @Override public CFGNode jump() { + throw Utils.TODO(); + } + + // Break an infinite loop + @Override public IfNode never( CFGNode ctrl ) { + throw Utils.TODO(); + } + + // Instruction selection + @Override public Node instSelect( Node n ) { + return switch( n ) { + case AddFNode addf -> addf(addf); + case AddNode add -> add(add); + case AndNode and -> and(and); + case BoolNode bool -> cmp(bool); + case CallEndNode cend -> new CallEndNode((CallNode)cend.in(0)); + case CallNode call -> call(call); + case CProjNode c -> new CProjNode(c); + case ConstantNode con -> con(con); + case DivFNode divf -> new DivFX86(divf); + case DivNode div -> new DivX86(div); + case FunNode fun -> new FunX86(fun); + case IfNode iff -> jmp(iff); + case LoadNode ld -> ld(ld); + case MemMergeNode mem -> new MemMergeNode(mem); + case MulFNode mulf -> new MulFX86(mulf); + case MulNode mul -> mul(mul); + case NewNode nnn -> new NewX86(nnn); + case OrNode or -> or(or); + case ParmNode parm -> new ParmX86(parm); + case PhiNode phi -> new PhiNode(phi); + case ProjNode prj -> prj(prj); + case ReadOnlyNode read -> new ReadOnlyNode(read); + case ReturnNode ret -> new RetX86(ret,ret.fun()); + case SarNode sar -> sar(sar); + case ShlNode shl -> shl(shl); + case ShrNode shr -> shr(shr); + case StartNode start -> new StartNode(start); + case StopNode stop -> new StopNode(stop); + case StoreNode st -> st(st); + case SubFNode subf -> new SubFX86(subf); + case SubNode sub -> sub(sub); + case ToFloatNode tfn -> i2f8(tfn); + case XorNode xor -> xor(xor); + + case LoopNode loop -> new LoopNode(loop); + case RegionNode region-> new RegionNode(region); + default -> throw Utils.TODO(); + }; + } + + + // Attempt a full LEA-style break down. + private Node add( AddNode add ) { + Node lhs = add.in(1); + Node rhs = add.in(2); + if( lhs instanceof LoadNode ld && ld.nOuts()==1 ) + return new AddMemX86(add,address(ld),ld.ptr(),idx,off,scale, imm(rhs),val); + + if( rhs instanceof LoadNode ld && ld.nOuts()==1 ) + throw Utils.TODO(); // Swap load sides + + // Attempt a full LEA-style break down. + // Returns one of AddX86, AddIX86, LeaX86, or LHS + if( rhs instanceof ConstantNode off && off._con instanceof TypeInteger toff ) { + if( lhs instanceof AddNode ladd ) + // ((base + (idx << scale)) + off) + return _lea(add,ladd.in(1),ladd.in(2),toff.value()); + if( lhs instanceof ShlNode shift ) + // (idx << scale) + off; no base + return _lea(add,null,shift,toff.value()); + + // lhs + rhs1 + if( toff.value()==0 ) return add; + return new AddIX86(add, toff); + } + return _lea(add,lhs,rhs,0); + } + + + private Node addf( AddFNode addf ) { + if( addf.in(1) instanceof LoadNode ld && ld.nOuts()==1 ) + return new AddFMemX86(addf,address(ld),ld.ptr(),idx,off,scale, addf.in(2)); + + if( addf.in(2) instanceof LoadNode ld && ld.nOuts()==1 ) + throw Utils.TODO(); // Swap load sides + + return new AddFX86(addf); + } + + + private Node _lea( Node add, Node base, Node idx, long off ) { + int scale = 1; + if( base instanceof ShlNode && !(idx instanceof ShlNode) ) throw Utils.TODO(); // Bug in canonicalization, should on RHS + if( idx instanceof ShlNode shift && shift.in(2) instanceof ConstantNode shfcon && + shfcon._con instanceof TypeInteger tscale && 0 <= tscale.value() && tscale.value() <= 3 ) { + idx = shift.in(1); + scale = 1 << ((int)tscale.value()); + } + // (base + idx) + off + return off==0 && scale==1 + ? new AddX86(add) + : new LeaX86(add,base,idx,scale,off); + } + + + private Node and(AndNode and) { + if( and.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti ) + return new AndIX86(and, ti); + throw Utils.TODO(); + } + + private Node call(CallNode call) { + if( call.fptr() instanceof ConstantNode con && con._con instanceof TypeFunPtr tfp ) + return new CallX86(call, tfp); + return new CallRX86( call ); + } + + // Because X86 flags, a normal ideal Bool is 2 X86 ops: a "cmp" and at "setz". + // Ideal If reading from a setz will skip it and use the "cmp" instead. + private Node cmp( BoolNode bool ) { + Node cmp = _cmp(bool); + return new SetX86(cmp,bool.op()); + } + private Node _cmp( BoolNode bool ) { + Node lhs = bool.in(1); + Node rhs = bool.in(2); + if( lhs instanceof LoadNode ld && ld.nOuts()==1 ) + return new CmpMemX86(bool,address(ld),ld.ptr(),idx,off,scale, imm(rhs),val,false); + + if( rhs instanceof LoadNode ld && ld.nOuts()==1 ) + return new CmpMemX86(bool,address(ld),ld.ptr(),idx,off,scale, imm(lhs),val,true); + + return rhs instanceof ConstantNode con && con._con instanceof TypeInteger ti + ? new CmpIX86(bool, ti) + : new CmpX86(bool); + } + + private Node con( ConstantNode con ) { + return switch( con._con ) { + case TypeInteger ti -> new IntX86(con); + case TypeFloat tf -> new FltX86(con); + case TypeFunPtr tfp -> new TFPX86(con); + case TypeMemPtr tmp -> new ConstantNode(con); + case TypeNil tn -> throw Utils.TODO(); + // TOP, BOTTOM, XCtrl, Ctrl, etc. Never any executable code. + case Type t -> new ConstantNode(con); + }; + } + + private Node i2f8(ToFloatNode tfn) { + assert tfn.in(1)._type instanceof TypeInteger ti; + return new I2f8X86(tfn); + } + + private Node jmp( IfNode iff ) { + // If/Bool combos will match to a Cmp/Set which sets flags. + // Most general arith ops will also set flags, which the Jmp needs directly. + // Loads do not set the flags, and will need an explicit TEST + if( !(iff.in(1) instanceof BoolNode) ) + iff.setDef(1,new BoolNode.EQ(iff.in(1),new ConstantNode(TypeInteger.ZERO))); + return new JmpX86(iff, ((BoolNode)iff.in(1)).op()); + } + + private Node ld( LoadNode ld ) { + return new LoadX86(address(ld),ld.ptr(),idx,off,scale); + } + + private Node mul(MulNode mul) { + return mul.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti + ? new MulIX86(mul, ti) + : new MulX86(mul); + } + + private Node or(OrNode or) { + if( or.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti) + return new OrIX86(or, ti); + throw Utils.TODO(); + } + + private Node prj( ProjNode prj ) { + return new ProjX86(prj); + } + + private Node sar( SarNode sar ) { + if( sar.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti) + return new SarX86(sar, ti); + throw Utils.TODO(); + } + + private Node shl( ShlNode shl ) { + if( shl.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti ) + return new ShlIX86(shl, ti); + throw Utils.TODO(); + } + + private Node shr(ShrNode shr) { + if( shr.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti ) + return new ShrIX86(shr, ti); + throw Utils.TODO(); + } + + private Node st( StoreNode st ) { + // Look for "*ptr op= val" + Node op = st.val(); + if( op instanceof AddNode ) { + if( op.in(1) instanceof LoadNode ld && + ld.in(0)==st.in(0) && + ld.mem()==st.mem() && + ld.ptr()==st.ptr() && + ld.off()==st.off() ) { + if( op instanceof AddNode ) { + return new MemAddX86(address(st),st.ptr(),idx,off,scale,imm(op.in(2)),val); + } + throw Utils.TODO(); + } + } + + return new StoreX86(address(st),st.ptr(),idx,off,scale,imm(st.val()),val); + } + + private Node sub( SubNode sub ) { + return sub.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti + ? new AddIX86(sub, TypeInteger.constant(-ti.value())) + : new SubX86(sub); + } + + private Node xor(XorNode xor) { + if(xor.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti) + return new XorIX86(xor, ti); + throw Utils.TODO(); + } + + + // Gather X86 addressing mode bits prior to constructing. This is a + // builder pattern, but saving the bits in a *local* *global* here to keep + // mess contained. + private static int off, scale, imm; + private static Node idx, val; + private <N extends MemOpNode> N address( N mop ) { + off = scale = imm = 0; // Reset + idx = val = null; + Node base = mop.ptr(); + // Skip/throw-away a ReadOnly, only used to typecheck + if( base instanceof ReadOnlyNode read ) base = read.in(1); + assert !(base instanceof AddNode) && base._type instanceof TypeMemPtr; // Base ptr always, not some derived + if( mop.off() instanceof AddNode add && add.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti ) { + off = (int)ti.value(); + assert off == ti.value(); // In 32-bit range + idx = add.in(1); + if( idx instanceof ShlNode shift && shift.in(2) instanceof ConstantNode shfcon && + shfcon._con instanceof TypeInteger tscale && 0 <= tscale.value() && tscale.value() <= 3 ) { + idx = shift.in(1); + scale = (int)tscale.value(); + } + } else { + if( mop.off() instanceof ConstantNode con && con._con instanceof TypeInteger ti ) { + off = (int)ti.value(); + assert off == ti.value(); // In 32-bit range + } else { + idx = mop.off(); + } + } + return mop; + } + private int imm( Node xval ) { + assert val==null && imm==0; + if( xval instanceof ConstantNode con && con._con instanceof TypeInteger ti ) { + val = null; + imm = (int)ti.value(); + assert imm == ti.value(); // In 32-bit range + } else { + val = xval; + } + return imm; + } + +} diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index b6757ef2..847235dd 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -232,8 +232,4 @@ public class Type { // This is used by error messages, and is a shorted print. public String str() { return STRS[_type]; } - - public static void reset() { - TypeFunPtr.reset(); - } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index cf92d3d7..be801c85 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -25,7 +25,6 @@ public class TypeFunPtr extends TypeNil { // within the TypeTuple. Can be upgraded to a BitSet for larger classes of // functions. Negative means "these 63 concrete bits plus infinite unknown more" public final long _fidxs; // 63 unique functions per signature - public String _name; // Optional debug function name; only for named single function private TypeFunPtr(byte nil, TypeTuple sig, Type ret, long fidxs) { super(TFUNPTR,nil); @@ -35,30 +34,16 @@ public class TypeFunPtr extends TypeNil { _fidxs = fidxs; } - static TypeFunPtr make( byte nil, TypeTuple sig, Type ret, long fidxs ) { return new TypeFunPtr(nil,sig,ret,fidxs).intern(); } + public static TypeFunPtr make( byte nil, TypeTuple sig, Type ret, long fidxs ) { return new TypeFunPtr(nil,sig,ret,fidxs).intern(); } public static TypeFunPtr make( boolean nil, TypeTuple sig, Type ret ) { return make((byte)(nil ? 3 : 2),sig,ret,-1); } - @Override TypeFunPtr makeFrom( byte nil ) { return nil ==_nil ? this : make( nil,_sig,_ret, _fidxs).setName(_name); } - public TypeFunPtr makeFrom( Type ret ) { return ret ==_ret ? this : make( _nil,_sig, ret, _fidxs).setName(_name); } - public TypeFunPtr makeFrom( int fidx ) { return make((byte)2, _sig,_ret,1L<<fidx ).setName(_name); } - - // Compute "function indices": FIDX - private static final HashMap<TypeTuple,Integer> FIDXS = new HashMap<>(); - private static int nextFIDX(TypeTuple sig) { - Integer i = FIDXS.get(sig); - int fidx = i==null ? 0 : i; - FIDXS.put(sig,fidx+1); // Track count per sig - assert fidx<64; // TODO: need a larger FIDX space - return fidx; // Return - } - public static TypeFunPtr makeFun( TypeTuple sig, Type ret ) { - return make((byte)2,sig,ret,1L<<nextFIDX(sig)); - } + @Override TypeFunPtr makeFrom( byte nil ) { return nil ==_nil ? this : make( nil,_sig,_ret, _fidxs); } + public TypeFunPtr makeFrom( Type ret ) { return ret ==_ret ? this : make( _nil,_sig, ret, _fidxs); } + public TypeFunPtr makeFrom( int fidx ) { return make((byte)2, _sig,_ret,1L<<fidx ); } public static TypeFunPtr BOT = make((byte)3,TypeTuple.BOT,Type.BOTTOM,-1); public static TypeFunPtr TEST = make((byte)2,TypeTuple.TEST,TypeInteger.BOT,1); public static TypeFunPtr TEST0 = make((byte)3,TypeTuple.TEST,TypeInteger.BOT,3); - public static TypeFunPtr MAIN = makeFun(TypeTuple.MAIN,Type.BOTTOM).setName("main"); - public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(TEST0); ts.add(BOT); ts.add(MAIN); } + public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(TEST0); ts.add(BOT); } @Override Type xmeet(Type t) { @@ -93,15 +78,6 @@ public class TypeFunPtr extends TypeNil { return _sig == ptr._sig && _ret == ptr._ret && _fidxs == ptr._fidxs && super.eq(ptr); } - public TypeFunPtr setName(String name) { - if( name==null ) return this; - assert _fidxs > 0 && Long.bitCount(_fidxs) == 1; - // Name can be set to different things, just for debug - //assert _name==null || _name.equals(name); - _name = name; - return this; - } - @Override public String str() { return print(new SB()).toString(); } @Override public SB print(SB sb) { return _print(sb,false,true); } public SB print(SB sb, boolean n) { return _print(sb,false,n); } @@ -109,32 +85,20 @@ public class TypeFunPtr extends TypeNil { private static SB _print(SB sb, boolean g, Type t) { return g ? t.gprint(sb) : t.print(sb); } private SB _print(SB sb, boolean g, boolean n) { sb.p(x()).p("{ "); - if( n && _name!=null ) sb.p(_name); - else { - if( _sig._types!=null ) - for( Type t : _sig._types ) - _print(sb,g,t).p(" "); - _print(sb.p(g ? "→ " : "-> "),g,_ret).p(" #"); - if( isHigh() ) sb.p("~"); - long fidxs = isHigh() ? ~_fidxs : _fidxs; - String fidx = fidxs==0 ? "" - : Long.bitCount(fidxs) == 1 ? ""+Long.numberOfTrailingZeros(fidxs) - : fidxs == -1 ? "ALL" - : "b"+Long.toBinaryString(fidxs); // Just some function bits - sb.p(fidx); - } - return sb.p("}").p(q()); + if( _sig._types!=null ) + for( Type t : _sig._types ) + _print(sb,g,t).p(" "); + _print(sb.p(g ? "→ " : "-> "),g,_ret).p(" #"); + if( isHigh() ) sb.p("~"); + long fidxs = isHigh() ? ~_fidxs : _fidxs; + String fidx = fidxs==0 ? "" + : Long.bitCount(fidxs) == 1 ? ""+Long.numberOfTrailingZeros(fidxs) + : fidxs == -1 ? "ALL" + : "b"+Long.toBinaryString(fidxs); // Just some function bits + return sb.p(fidx).p("}").p(q()); } // Usage: for( long fidxs=fidxs(); fidxs!=0; fidxs=nextFIDX(fidxs) { int fidxs = Long.numberOfTrailingZeros(fidxs); ... } public static long nextFIDX(long fidxs) { return fidxs & (fidxs-1); } - public static void reset() { - FIDXS.clear(); - FIDXS.put(MAIN._sig,1); - for( Type t : INTERN.keySet() ) - if( t instanceof TypeFunPtr tfp && tfp!=MAIN) - tfp._name = null; - } - } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index ee206579..6c5cb8d4 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -49,7 +49,8 @@ public class TypeStruct extends Type { // Array public static TypeStruct makeAry(TypeInteger len, int lenAlias, Type body, int bodyAlias) { - assert body instanceof TypeInteger || (body instanceof TypeNil tn && tn.nullable()); + assert body instanceof TypeInteger || body instanceof TypeFloat || (body instanceof TypeNil tn && tn.nullable()); + assert len.isa(TypeInteger.U32); return make("[" + body.str() + "]", Field.make("#" ,len , lenAlias,true ), Field.make("[]",body,bodyAlias,false)); @@ -61,7 +62,7 @@ public class TypeStruct extends Type { public static final TypeStruct S1 = make("S1", Field.make("a", TypeInteger.BOT, -1, false), Field.make("s2",TypeMemPtr.make((byte)2,S2F),-2, false) ); private static final TypeStruct S2 = make("S2", Field.make("b", TypeFloat .F64, -3, false), Field.make("s1",TypeMemPtr.make((byte)2,S1F),-4, false) ); - private static final TypeStruct ARY = makeAry(TypeInteger.BOT,-1,TypeInteger.BOT,-2); + private static final TypeStruct ARY = makeAry(TypeInteger.U32,-1,TypeInteger.BOT,-2); public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); ts.add(ARY); } @@ -215,6 +216,11 @@ public class TypeStruct extends Type { private int[] offsets() { // Field byte offsets // Compute a layout for a collection of fields assert _fields != null; // No forward refs + + // Array layout is different: len,[pad],body... + if( isAry() ) + return _offs = new int[]{ 0, _fields[1]._type.log_size() < 3 ? 4 : 8 }; + // Compute a layout int[] cnts = new int[4]; // Count of fields at log field size for( Field f : _fields ) |