diff options
| author | Cliff Click <cliffc@acm.org> | 2025-02-07 08:58:36 -0800 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2025-02-07 08:58:36 -0800 |
| commit | 2aa8c5d1d0659bd1c828134f1a1f14d025a2d0f1 (patch) | |
| tree | 0532f3ba5d74de006fcaa906dad9b787ebb06e2e /src/main/java/com/seaofnodes/simple/node | |
| parent | 68dc63b9390bbe4ec50cc1b814d4e559e459c057 (diff) | |
| download | Simple-linear-chapter19.tar.gz Simple-linear-chapter19.zip | |
Ch# Chapter 19: Instruction Selection and Portable Compilationlinear-chapter19
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/node')
71 files changed, 2200 insertions, 230 deletions
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..6c74042b 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; + Node shf = con(shift); + if( shf._type==TypeInteger.ZERO ) + return val; + //return peep(new SarNode(null,peep(new ShlNode(null,val,shf.keep())),shf.unkeep())); + throw Utils.TODO(); + } } 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; + } + +} |
