From 67dc6202dee2ce983778ba3143cc3f00196aeb7c Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 12 Sep 2024 11:13:31 -0700 Subject: Chapter 15: Arrays Co-authored-by: XmiliaH Co-authored-by: Thalia Archibald Co-authored-by: Robert Obkircher --- .../java/com/seaofnodes/simple/node/AddNode.java | 5 +- .../java/com/seaofnodes/simple/node/AndNode.java | 1 - .../java/com/seaofnodes/simple/node/BoolNode.java | 22 +++-- .../java/com/seaofnodes/simple/node/CFGNode.java | 3 - .../java/com/seaofnodes/simple/node/CProjNode.java | 17 ++-- .../com/seaofnodes/simple/node/ConstantNode.java | 2 - .../java/com/seaofnodes/simple/node/DivNode.java | 2 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 99 +++++++++++++++++----- .../java/com/seaofnodes/simple/node/MemOpNode.java | 23 +++-- .../java/com/seaofnodes/simple/node/MinusNode.java | 4 +- .../java/com/seaofnodes/simple/node/NewNode.java | 52 ++++++++---- src/main/java/com/seaofnodes/simple/node/Node.java | 21 ++--- .../java/com/seaofnodes/simple/node/OrNode.java | 1 - .../java/com/seaofnodes/simple/node/PhiNode.java | 34 +++----- .../java/com/seaofnodes/simple/node/ProjNode.java | 5 +- .../com/seaofnodes/simple/node/RegionNode.java | 59 ++++++++++++- .../com/seaofnodes/simple/node/ReturnNode.java | 3 +- .../java/com/seaofnodes/simple/node/SarNode.java | 16 ++-- .../java/com/seaofnodes/simple/node/ScopeNode.java | 82 +++++++++--------- .../java/com/seaofnodes/simple/node/ShlNode.java | 18 ++-- .../java/com/seaofnodes/simple/node/ShrNode.java | 17 +--- .../java/com/seaofnodes/simple/node/StartNode.java | 47 +++++----- .../java/com/seaofnodes/simple/node/StoreNode.java | 31 ++++--- .../java/com/seaofnodes/simple/node/SubNode.java | 7 +- .../java/com/seaofnodes/simple/node/XorNode.java | 1 - 25 files changed, 346 insertions(+), 226 deletions(-) (limited to 'src/main/java/com/seaofnodes/simple/node') diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 9d425f7a..f3b213fb 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -22,7 +22,8 @@ public class AddNode extends Node { @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) return TypeInteger.TOP; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; if( t1 instanceof TypeInteger i1 && t2 instanceof TypeInteger i2 ) { if (i1.isConstant() && i2.isConstant()) @@ -36,7 +37,7 @@ public class AddNode extends Node { } private static boolean overflow( long x, long y ) { - if( (x ^ y ) < 0 ) return false; // unequal signs, never overflow + if( (x ^ y ) < 0 ) return false; // unequal signs, never overflow return (x ^ (x + y)) < 0; // sum has unequal signs, so overflow } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/AndNode.java b/src/main/java/com/seaofnodes/simple/node/AndNode.java index 350859db..7e4b898b 100644 --- a/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -21,7 +21,6 @@ public class AndNode extends Node { @Override public Type compute() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; if( in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index f0cca1e2..238be00e 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -37,9 +37,6 @@ abstract public class BoolNode extends Node { Type t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) return BOOL.dual(); - // Compare of same - if( in(1)==in(2) ) - return doOp(ZERO,ZERO); if( t1 instanceof TypeInteger i1 && t2 instanceof TypeInteger i2 ) return doOp(i1,i2); @@ -56,6 +53,10 @@ abstract public class BoolNode extends Node { @Override public Node idealize() { + // Compare of same + if( in(1)==in(2) ) + return new ConstantNode(doOp(ZERO,ZERO)); + // Equals pushes constant to the right; 5==X becomes X==5. if( this instanceof EQ ) { if( !(in(2) instanceof ConstantNode) ) { @@ -67,11 +68,14 @@ abstract public class BoolNode extends Node { // Equals X==0 becomes a !X if( (in(2)._type == ZERO || in(2)._type == TypeMemPtr.NULLPTR) ) return new NotNode(in(1)); - // Equals bool == 1 becomes bool - if( in(2)._type == TRUE && in(1)._type == BOOL ) - return in(1); } + // 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...) + Node phicon = AddNode.phiCon(this,this instanceof EQ); + if( phicon!=null ) return phicon; + return null; } @@ -109,8 +113,8 @@ abstract public class BoolNode extends Node { Node copyF() { return new LEF(null,null); } } - public static class EQF extends EQ { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQF(lhs,rhs); } } - public static class LTF extends LT { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LTF(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; } Node copy(Node lhs, Node rhs) { return new LEF(lhs,rhs); } } + public static class EQF extends EQ { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs == rhs; } } + 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; } } } diff --git a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 07ba0fa4..9e9d6970 100644 --- a/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -23,9 +23,6 @@ public abstract class CFGNode extends Node { public CFGNode(Node... nodes) { super(nodes); } - @Override public boolean isCFG() { return true; } - @Override public boolean isPinned() { return true; } - public CFGNode cfg(int idx) { return (CFGNode)in(idx); } // Block head is Start, Region, CProj, but not e.g. If, Return, Stop diff --git a/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/src/main/java/com/seaofnodes/simple/node/CProjNode.java index fb0ff879..3d6fd1fa 100644 --- a/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -37,14 +37,17 @@ public class CProjNode extends CFGNode { @Override public Node idealize() { - if ( ctrl() instanceof IfNode iff ) { - if ( iff._type instanceof TypeTuple tt && tt._types[1 - _idx] == Type.XCONTROL ) - return iff.in(0); // We become our input control - - // Flip a negating if-test, to remove the not - if( iff.pred().addDep(this) instanceof NotNode not ) - return new CProjNode(new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True"); + if( ctrl()._type instanceof TypeTuple tt ) { + if( tt._types[_idx]==Type.XCONTROL ) + return Parser.XCTRL; // We are dead + if( ctrl() instanceof IfNode && tt._types[1-_idx]==Type.XCONTROL ) // Only true for IfNodes + return ctrl().in(0); // We become our input control } + + // Flip a negating if-test, to remove the not + if( ctrl() instanceof IfNode iff && iff.pred().addDep(this) instanceof NotNode not ) + return new CProjNode(new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True"); + return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 016b0b9b..845b9d08 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -36,8 +36,6 @@ public class ConstantNode extends Node { } @Override public boolean isMultiTail() { return true; } - // The special forever-zero is pinned, all others can sink - @Override public boolean isPinned() { return this==Parser.ZERO; } @Override public Type compute() { return _con; } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index da9571db..76e98678 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -37,7 +37,7 @@ public class DivNode extends Node { @Override public Node idealize() { // Div of 1. - if( in(2)._type.isConstant() && in(2)._type instanceof TypeInteger i && i.value()==1 ) + if( in(2)._type == TypeInteger.TRUE ) return in(1); 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 78ccc8a9..0bdf86f0 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -1,8 +1,10 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; - +import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.type.TypeStruct; import java.util.BitSet; /** @@ -15,34 +17,82 @@ public class LoadNode extends MemOpNode { * Load a value from a ptr.field. * * @param name The field we are loading - * @param memSlice The memory alias node - this is updated after a Store - * @param memPtr The ptr to the struct from where we load a field + * @param mem The memory alias node - this is updated after a Store + * @param ptr The ptr to the struct base from where we load a field + * @param off The offset inside the struct base */ - public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) { - super(name, alias, glb, null, memSlice, memPtr); + public LoadNode(String name, int alias, Type glb, Node mem, Node ptr, Node off) { + super(name, alias, glb, mem, ptr, off); } - @Override public String label() { return _name; } - @Override public String glabel() { return "."+_name; } + // GraphVis DOT code (must be valid Java identifiers) and debugger labels + @Override public String label() { return "ld_"+mlabel(); } + // GraphVis node-internal labels + @Override public String glabel() { return "." +_name; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); } @Override public Type compute() { + if( mem()._type instanceof TypeMem mem && + // No constant folding if ptr might null-check + _declaredType != mem._t && err()==null ) { + assert mem._alias == _alias; + return _declaredType.join(mem._t); + } return _declaredType; } @Override public Node idealize() { + Node ptr = ptr(); // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && - ptr() == st.ptr() ) { // Must check same object + ptr == st.ptr() && off() == st.off() ) { // Must check same object assert _name.equals(st._name); // Equiv class aliasing is perfect return st.val(); } + // Simple Load-after-New on same address. + if( mem() instanceof ProjNode p && p.in(0) instanceof NewNode nnn && + ptr == nnn.proj(1) ) // Must check same object + return new ConstantNode(_declaredType.makeInit()); + + // 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. + Node mem = mem(); + outer: + while( true ) { + switch( mem ) { + case StoreNode st: + if( ptr == st.ptr() && off() == st.off() ) + return 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 + break outer; // Cannot tell, stop trying + // Pointers cannot overlap + mem = st.mem(); // Proved never equal + break; + case PhiNode phi: + break outer; // Assume related + case ProjNode mproj: + if( mproj.in(0) instanceof NewNode nnn1 ) { + if( ptr instanceof ProjNode pproj && pproj.in(0) == mproj.in(0) ) + return new ConstantNode(_declaredType.makeInit()); // Load from a New + if( !(ptr instanceof ProjNode pproj && pproj.in(0) instanceof NewNode nnn2) ) + break outer; // Cannot tell, ptr not related to New + mem = nnn1.in(_alias);// Bypass unrelated New + break; + } else throw Utils.TODO(); + default: + throw Utils.TODO(); + } + } + // Push a Load up through a Phi, as long as it collapses on at least // one arm. If at a Loop, the backedge MUST collapse - else we risk // spinning the same transform around the loop indefinitely. @@ -50,31 +100,38 @@ public class LoadNode extends MemOpNode { // if( pred ) ptr.x = e0; val = pred ? e0 // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; - if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) { + if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 && + off() instanceof ConstantNode ) { // Profit on RHS/Loop backedge if( profit(memphi,2) || // Else must not be a loop to count profit on LHS. (!(memphi.region() instanceof LoopNode) && profit(memphi,1)) ) { - if( ptr() instanceof NewNode || !(ptr() instanceof CastNode) ) { - if( !(ptr() instanceof NewNode) ) throw Utils.TODO(); // Validate - - Node ld1 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr()).peephole(); - Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr()).peephole(); - return new PhiNode(_name,_type,memphi.region(),ld1,ld2); - } + Node ld1 = ld(1); + Node ld2 = ld(2); + return new PhiNode(_name,_declaredType,memphi.region(),ld1,ld2); } } return null; } + private Node ld( int idx ) { + Node mem = mem(), ptr = ptr(); + return new LoadNode(_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr, off()).peephole(); + } + private static boolean neverAlias( Node ptr1, Node ptr2 ) { + return ptr1.in(0) != ptr2.in(0) && + // Unrelated allocations + ptr1 instanceof ProjNode && ptr1.in(0) instanceof NewNode && + ptr2 instanceof ProjNode && ptr2.in(0) instanceof NewNode; + } + // Profitable if we find a matching Store on this Phi arm. private boolean profit(PhiNode phi, int idx) { Node px = phi.in(idx); - return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr(); - } - - Node copy(Node mem, Node ptr) { - return new LoadNode(_name,_alias,_declaredType,mem,ptr); + if( px==null ) return false; + if( px._type instanceof TypeMem mem && mem._t.isHighOrConst() ) { px.addDep(this); return true; } + if( px instanceof StoreNode st1 && ptr()==st1.ptr() && off()==st1.off() ) { px.addDep(this); return true; } + return false; } } diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 76564db0..c7a1efec 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -13,16 +13,24 @@ public abstract class MemOpNode extends Node { public final int _alias; public final Type _declaredType; - - public MemOpNode(String name, int alias, Type glb, Node... nodes) { - super(nodes); + public MemOpNode(String name, int alias, Type glb, Node mem, Node ptr, Node off) { + super(null, mem, ptr, off); _name = name; _alias = alias; _declaredType = glb; } + public MemOpNode(String name, int alias, Type glb, Node mem, Node ptr, Node off, Node value) { + this(name, alias, glb, mem, ptr, off); + addDef(value); + } + + // + static String mlabel(String name) { return name.equals("[]") ? "ary" : (name.equals("#") ? "len" : name); } + String mlabel() { return mlabel(_name); } public Node mem() { return in(1); } public Node ptr() { return in(2); } + public Node off() { return in(3); } @Override boolean eq(Node n) { @@ -36,8 +44,11 @@ public abstract class MemOpNode extends Node { @Override String err() { Type ptr = ptr()._type; - return (ptr==Type.BOTTOM || (ptr instanceof TypeMemPtr tmp && tmp._nil) ) - ? "Might be null accessing '" + _name + "'" - : null; + // Already an error, but better error messages come from elsewhere + if( ptr == Type.BOTTOM ) return null; + // Better be a not-nil TMP + if( ptr instanceof TypeMemPtr tmp && !tmp._nil ) + return null; + return "Might be null accessing '" + _name + "'"; } } diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 8ba45d26..8a2c9406 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -22,9 +22,7 @@ public class MinusNode extends Node { public Type compute() { if( in(1)._type instanceof TypeInteger i0 ) { if( i0.isHigh() ) return TypeInteger.TOP; - // Catch overflow wrapping on `-Long.MIN_VALUE` - if( i0 == TypeInteger.BOT || i0._min == Long.MIN_VALUE ) return TypeInteger.BOT; - return TypeInteger.make(-i0._max,-i0._min); + return i0==TypeInteger.BOT ? TypeInteger.BOT : TypeInteger.make(-i0._max,-i0._min); } return TypeInteger.TOP.meet(in(1)._type); } diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java index 0724ec56..f06564cd 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -1,24 +1,34 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeMemPtr; - +import com.seaofnodes.simple.type.*; import java.util.BitSet; -public class NewNode extends Node { - - TypeMemPtr _ptr; - - public NewNode(TypeMemPtr ptr, Node ctrl) { - super(ctrl); - this._ptr = ptr; +/** + * Allocation! Allocate a chunk of memory, and pre-zero it. + * The inputs include control and size, and ALL aliases being set. + * The output is large tuple, one for every alias plus the created pointer. + * New is expected to be followed by projections for every alias. + */ +public class NewNode extends Node implements MultiNode { + + public TypeMemPtr _ptr; + + public NewNode(TypeMemPtr ptr, Node... nodes) { + super(nodes); + // Control in slot 0 + assert nodes[0]._type==Type.CONTROL || nodes[0]._type == Type.XCONTROL; + // Malloc-length in slot 1 + assert nodes[1]._type instanceof TypeInteger; + // Memory slices in remaining slots + for( int i=2; idef into a Node. Keeps the edges correct, by removing @@ -179,11 +179,10 @@ public abstract class Node implements OutNode { Node delDef(int idx) { unlock(); Node old_def = in(idx); - if( old_def != null && // If the old def exists, remove a def->use edge - old_def.delUse(this) ) // If we removed the last use, the old def is now dead + Utils.del(_inputs, idx); + if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def old_def.moveDepsToWorklist(); - Utils.del(_inputs, idx); return this; } @@ -295,7 +294,7 @@ public abstract class Node implements OutNode { return this; // Peephole optimizations turned off } Node n = peepholeOpt(); - return n==null ? this : deadCodeElim(n.peephole()); // Cannot return null for no-progress + return n==null ? this : deadCodeElim(n.peephole().keep()).unkeep(); // Cannot return null for no-progress } /** @@ -533,16 +532,13 @@ public abstract class Node implements OutNode { // ------------------------------------------------------------------------ // - /** Is this Node control-flow-graph related */ - public boolean isCFG() { return false; } - /** Is this Node Memory related */ public boolean isMem() { return false; } /** Return block start from a isCFG() */ public Node getBlockStart() { return null; } - /** Pinned in the schedule */ + /** Pinned in the schedule; these are data nodes whose input#0 is not allowed to change */ public boolean isPinned() { return false; } // Semantic change to the graph (so NOT a peephole), used by the Parser. @@ -631,12 +627,7 @@ public abstract class Node implements OutNode { E x = pred.apply(this); if( x != null ) return x; for( Node def : _inputs ) if( def != null && (x = def._walk(pred)) != null ) return x; - // Unroll iterator to survive junk CME - for( int i=0; i<_outputs.size(); i++ ) { - Node use = _outputs.get(i); - if( use != null && (x = use._walk(pred)) != null ) - return x; - } + for( Node use : _outputs ) if( use != null && (x = use._walk(pred)) != null ) return x; return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/OrNode.java b/src/main/java/com/seaofnodes/simple/node/OrNode.java index e18996b7..1b32d4fb 100644 --- a/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -21,7 +21,6 @@ public class OrNode extends Node { @Override public Type compute() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; if( in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 05584423..139e80a3 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -11,12 +11,12 @@ public class PhiNode extends Node { final String _label; // The Phi type we compute must stay within the domain of the Phi. - // Example Int stays Int, Ptr stays Ptr, Mem stays Mem. + // Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. final Type _declaredType; public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; } - @Override public String label() { return "Phi_"+_label; } + @Override public String label() { return "Phi_"+MemOpNode.mlabel(_label); } @Override public String glabel() { return "φ_"+_label; } @@ -73,7 +73,8 @@ public class PhiNode extends Node { // Phi(op(A,B),op(Q,R),op(X,Y)) becomes // op(Phi(A,Q,X), Phi(B,R,Y)). Node op = in(1); - if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { + if( op.nIns()==3 && op.in(0)==null && same_op() ) { + assert !(op instanceof CFGNode); Node[] lhss = new Node[nIns()]; Node[] rhss = new Node[nIns()]; lhss[0] = rhss[0] = in(0); // Set Region @@ -81,16 +82,9 @@ public class PhiNode extends Node { lhss[i] = in(i).in(1); rhss[i] = in(i).in(2); } - Node phi_lhs = new PhiNode(_label, in(1).in(1)._type.glb(),lhss).peephole(); - Node phi_rhs = new PhiNode(_label, in(1).in(2)._type.glb(),rhss).peephole(); - Node phi_op = op.copy(phi_lhs,phi_rhs); - phi_op.setType(phi_op.compute()); - // If losing precision, don't do it - if( !phi_op._type.isa(_type) ) { - phi_op.kill(); - return null; - } - return phi_op; + Node phi_lhs = new PhiNode(_label, _declaredType,lhss).peephole(); + Node phi_rhs = new PhiNode(_label, _declaredType,rhss).peephole(); + return op.copy(phi_lhs,phi_rhs); } // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. @@ -107,9 +101,9 @@ public class PhiNode extends Node { if( in(2)._type == in(2)._type.makeInit() ) nullx = 2; if( nullx != -1 ) { Node val = in(3-nullx); - if( region().idom(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) { + if( r.idom(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) { // Must walk the idom on the null side to make sure we hit False. - CFGNode idom = (CFGNode)region().in(nullx); + CFGNode idom = (CFGNode)r.in(nullx); while( idom.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom(); if( idom instanceof CProjNode proj && proj._idx==1 ) return val; @@ -121,13 +115,9 @@ public class PhiNode extends Node { } private boolean same_op() { - for( int i=2; i= 2 if( scope != null ) { String[] names = scope.reverseNames(); diff --git a/src/main/java/com/seaofnodes/simple/node/SarNode.java b/src/main/java/com/seaofnodes/simple/node/SarNode.java index 881a3812..ba99fde8 100644 --- a/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -21,14 +21,14 @@ public class SarNode extends Node { @Override public Type compute() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; - if (in(1)._type instanceof TypeInteger i1 && - in(2)._type instanceof TypeInteger i2) { - if( i1.isConstant() && i2.isConstant() ) - return TypeInteger.constant(i1.value()>>i2.value()); - if( i2._min < 0 || i2._max >= 64 ) - return TypeInteger.BOT; - return TypeInteger.make(i1._min>>i2._min,i1._max>>i2._min); + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if( i0.isConstant() && i1.isConstant() ) + return TypeInteger.constant(i0.value()>>i1.value()); + if( i1.isConstant() ) { + int log = (int)i1.value(); + return TypeInteger.make(-1L<<(63-log),(1L<<(63-log))-1); + } } return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 843ce733..877ae4a4 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,10 +1,9 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; -import com.seaofnodes.simple.type.TypeMemPtr; - +import com.seaofnodes.simple.type.*; import java.util.*; /** @@ -21,24 +20,22 @@ public class ScopeNode extends Node { public static final String ARG0 = "arg"; /** - * Names for every input edge + * Map variable names to Scope input edge */ - public final Stack> _scopes; + public final Stack> _idxs; /** - * Tracks declared types for every name + * Map variable names to declared Type */ - public Stack> _types; - + final Stack> _decls; // A new ScopeNode public ScopeNode() { - _scopes = new Stack<>(); - _types = new Stack<>(); + _idxs = new Stack<>(); + _decls= new Stack<>(); _type = Type.BOTTOM; } - @Override public String label() { return "Scope"; } @Override @@ -58,6 +55,20 @@ public class ScopeNode extends Node { return sb.append("]"); } + public Node ctrl() { return in(0); } + + /** + * The ctrl of a ScopeNode is always bound to the currently active + * control node in the graph, via a special name '$ctrl' that is not + * a valid identifier in the language grammar and hence cannot be + * referenced in Simple code. + * + * @param n The node to be bound to '$ctrl' + * + * @return Node that was bound + */ + public Node ctrl(Node n) { return setDef(0,n); } + /** * Recover the names for all variable bindings. * The result is an array of names that is aligned with the @@ -67,7 +78,7 @@ public class ScopeNode extends Node { */ public String[] reverseNames() { String[] names = new String[nIns()]; - for( HashMap syms : _scopes ) + for( HashMap syms : _idxs ) for( String name : syms.keySet() ) names[syms.get(name)] = name; return names; @@ -77,33 +88,34 @@ public class ScopeNode extends Node { @Override public Node idealize() { return null; } - public void push() { _scopes.push(new HashMap<>()); _types.push(new HashMap<>()); } - public void pop() { popN(_scopes.pop().size()); _types.pop(); } + public void push() { _idxs.push(new HashMap<>()); _decls.push(new HashMap<>()); } + public void pop() { popN(_idxs.pop().size()); _decls.pop(); } /** - * Create a new name in the current scope + * Create a new variable name in the current scope */ public Node define( String name, Type declaredType, Node n ) { - HashMap syms = _scopes.lastElement(); - _types.lastElement().put(name,declaredType); + HashMap syms = _idxs.lastElement(); + _decls.lastElement().put(name,declaredType); if( syms.put(name,nIns()) != null ) return null; // Double define return addDef(n); } + /** * Lookup a name in all scopes starting from most deeply nested. * * @param name Name to be looked up * @see #update(String, Node, int) */ - public Node lookup( String name ) { return update(name,null,_scopes.size()-1); } + public Node lookup( String name ) { return update(name,null,_idxs.size()-1); } /** * If the name is present in any scope, then redefine else null * * @param name Name being redefined * @param n The node to bind to the name */ - public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); } + public Node update( String name, Node n ) { return update(name,n,_idxs.size()-1); } /** * Both recursive lookup and update. *

@@ -117,7 +129,7 @@ public class ScopeNode extends Node { */ private Node update( String name, Node n, int nestingLevel ) { if( nestingLevel<0 ) return null; // Missed in all scopes, not found - var syms = _scopes.get(nestingLevel); // Get the symbol table for nesting level + var syms = _idxs.get(nestingLevel); // Get the symbol table for nesting level var idx = syms.get(name); if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope Node old = in(idx); @@ -135,29 +147,15 @@ public class ScopeNode extends Node { return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer } - // Return declared type + // Return declared type for a variable public Type lookupDeclaredType( String name ) { - for( int i=_types.size(); i>0; i-- ) { - Type t = _types.get(i-1).get(name); + for( int i=_decls.size(); i>0; i-- ) { + Type t = _decls.get(i-1).get(name); if( t != null ) return t; } return null; } - public Node ctrl() { return in(0); } - - /** - * The ctrl of a ScopeNode is always bound to the currently active - * control node in the graph, via a special name '$ctrl' that is not - * a valid identifier in the language grammar and hence cannot be - * referenced in Simple code. - * - * @param n The node to be bound to '$ctrl' - * - * @return Node that was bound - */ - public Node ctrl(Node n) { return setDef(0,n); } - /** * Duplicate a ScopeNode; including all levels, up to Nodes. So this is * neither shallow (would dup the Scope but not the internal HashMap @@ -165,7 +163,7 @@ public class ScopeNode extends Node { * also the program Nodes). *

* If the {@code loop} flag is set, the edges are filled in as the original - * Scope, as a indication of Lazy Phis at loop heads. The goal here is to + * Scope, as an indication of Lazy Phis at loop heads. The goal here is to * not make Phis at loop heads for variables which are never touched in the * loop body. *

@@ -178,10 +176,10 @@ public class ScopeNode extends Node { // 1) duplicate the name bindings of the ScopeNode across all stack levels // 2) Make the new ScopeNode a user of all the nodes bound // 3) Ensure that the order of defs is the same to allow easy merging - for( HashMap syms : _scopes ) - dup._scopes.push(new HashMap<>(syms)); - for( HashMap ts : _types ) - dup._types.push(ts); // Types don't change, just keep stacks aligned + for( HashMap syms : _idxs ) + dup._idxs.push(new HashMap<>(syms)); + for( HashMap ts : _decls ) + dup._decls.push(ts); // Types don't change, just keep stacks aligned dup.addDef(ctrl()); // Control input is just copied for( int i=1; i (x << i) + (c << i) + if( lhs instanceof AddNode add && add.in(2)._type instanceof TypeInteger c && c.isConstant() ) { + long sum = c.value() << shl.value(); + if( Integer.MIN_VALUE <= sum && sum <= Integer.MAX_VALUE ) + return new AddNode( new ShlNode(add.in(1),rhs).peephole(), Parser.con(sum) ); + } + } // TODO: x << 3 << (y ? 1 : 2) ==> x << (y ? 4 : 5) diff --git a/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/src/main/java/com/seaofnodes/simple/node/ShrNode.java index bed18d2b..16d78ebf 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -21,19 +21,10 @@ public class ShrNode extends Node { @Override public Type compute() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; - if (in(1)._type instanceof TypeInteger i1 && - in(2)._type instanceof TypeInteger i2) { - if( i1.isConstant() && i2.isConstant() ) - return TypeInteger.constant(i1.value()>>>i2.value()); - if( i2._min < 0 || i2._max >= 64 ) - return TypeInteger.BOT; - // Zero shifting a negative makes a larger positive - // so get the endpoints correct. - long s1 = i1._min>>>i2._min; - long s2 = i1._max>>>i2._min; - boolean wrap = i1._min < 0 && i1._max >=0; - return TypeInteger.make(wrap ? 0 : Math.min(s1,s2),Math.max(s1,s2)); + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if( i0.isConstant() && i1.isConstant() ) + return TypeInteger.constant(i0.value()>>>i1.value()); } return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 5f205ffd..5964e19f 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -4,7 +4,6 @@ import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.*; import java.util.Arrays; import java.util.BitSet; -import java.util.HashMap; import java.util.HashSet; /** @@ -19,16 +18,10 @@ public class StartNode extends CFGNode implements MultiNode { // This field is NOT final, because the tuple expands as we add memory aliases TypeTuple _args; - // The alias number of the first field in the struct. - // - public final HashMap _aliasStarts; - - public StartNode(Type[] args) { super(); _args = TypeTuple.make(args); _type = _args; - _aliasStarts = new HashMap<>(); } /** @@ -36,28 +29,29 @@ public class StartNode extends CFGNode implements MultiNode { * as the key. */ public void addMemProj( TypeStruct ts, ScopeNode scope) { - int len = _args._types.length; - _aliasStarts.put(ts._name,len); - - // resize the tuple's type array to include all fields of the struct - int max = len + ts._fields.length; - Type[] args = Arrays.copyOf(_args._types, max); - - // The new members of the tuple get a mem type with an alias - for( int alias = len; alias < max; alias++ ) - args[alias] = TypeMem.make(alias); - _type = _args = TypeTuple.make(args); - // For each of the fields we now add a mem projection. Note that the - // alias matches the slot of the field in the tuple - for( int alias = len; alias < max; alias++ ) { - String name = Parser.memName(alias); - Node n = new ProjNode(this, alias, name).peephole(); - scope.define(name, args[alias], n); + if( ts._fields.length==0 ) return; + // Expand args type for more memory projections + Type[] args = _args._types; + int max = args.length; + for( Field f : ts._fields ) + max = Math.max(max,f._alias); + args = Arrays.copyOf(args, max+1); + // For each of the fields we now add a mem projection. + for( Field f : ts._fields ) { + TypeMem tm_decl = TypeMem.make(f._alias,f._type.glb()); + args[f._alias] = tm_decl.dual(); + String name = Parser.memName(f._alias); + Node n = new ProjNode(this, f._alias, name); // No 'compute' until ScopeNode gets typed + n._type = args[f._alias]; + scope.define(name, tm_decl, n); } + for (int i = 0; i < args.length; i++) + if (args[i] == null) + args[i] = Type.TOP; // We parsed a nested struct/array. Avoid nulls until a caller replaces this alias. + _type = _args = TypeTuple.make(args); } - @Override - public String label() { return "Start"; } + @Override public String label() { return "Start"; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { @@ -66,6 +60,7 @@ public class StartNode extends CFGNode implements MultiNode { @Override public boolean isMultiHead() { return true; } @Override public boolean blockHead() { return true; } + @Override public CFGNode cfg0() { return this; } @Override public TypeTuple compute() { return _args; } diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 57e8b3ad..b1c74b94 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -14,21 +14,24 @@ public class StoreNode extends MemOpNode { private final boolean _init; // Initializing writes are allowed to write null /** - * @param name The struct field we are assigning to - * @param memSlice The memory alias node - this is updated after a Store - * @param memPtr The ptr to the struct where we will store a value + * @param name The struct field we are assigning to + * @param mem The memory alias node - this is updated after a Store + * @param ptr The ptr to the struct base where we will store a value + * @param off The offset inside the struct base * @param value Value to be stored */ - public StoreNode(String name, int alias, Type glb, Node ctrl, Node memSlice, Node memPtr, Node value, boolean init) { - super(name, alias, glb, ctrl, memSlice, memPtr, value); + public StoreNode(String name, int alias, Type glb, Node mem, Node ptr, Node off, Node value, boolean init) { + super(name, alias, glb, mem, ptr, off, value); _init = init; } - @Override public String label() { return "." +_name+"="; } + // GraphVis DOT code and debugger labels + @Override public String label() { return "st_"+mlabel(); } + // GraphVis node-internal labels @Override public String glabel() { return "." +_name+"="; } @Override public boolean isMem() { return true; } - public Node val() { return in(3); } + public Node val() { return in(4); } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { @@ -36,7 +39,14 @@ public class StoreNode extends MemOpNode { } @Override - public Type compute() { return TypeMem.make(_alias); } + public Type compute() { + Type val = val()._type; + TypeMem mem = (TypeMem)mem()._type; // Invariant + Type t = mem._alias==_alias + ? val.meet(mem._t) // Meet into existing memory + : Type.BOTTOM; + return TypeMem.make(_alias,t); + } @Override public Node idealize() { @@ -45,6 +55,7 @@ public class StoreNode extends MemOpNode { // required init-store being stomped by a first user store. if( mem() instanceof StoreNode st && ptr()==st.ptr() && // Must check same object + off()==st.off() && // And same offset ptr()._type instanceof TypeMemPtr && // No bother if weird dead pointers // Must have exactly one use of "this" or you get weird // non-serializable memory effects in the worse case. @@ -72,7 +83,7 @@ public class StoreNode extends MemOpNode { String err() { String err = super.err(); if( err != null ) return err; - Type ptr = val()._type; - return _init || ptr.isa(_declaredType) ? null : "Cannot store "+ptr+" into field "+_declaredType+" "+_name; + Type t = val()._type; + return _init || t.isa(_declaredType) ? null : "Cannot store "+t+" into field "+_declaredType+" "+_name; } } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 6d2f1711..009fb30e 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -22,10 +22,6 @@ public class SubNode extends Node { @Override public Type compute() { - // Sub of same is 0 - if( in(1)==in(2) ) - return TypeInteger.ZERO; - Type t1 = in(1)._type, t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) return TypeInteger.TOP; @@ -34,6 +30,9 @@ public class SubNode extends Node { if (i1.isConstant() && i2.isConstant()) return TypeInteger.constant(i1.value()-i2.value()); } + // Sub of same is 0 + if( in(1)==in(2) ) + return TypeInteger.ZERO; return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/XorNode.java b/src/main/java/com/seaofnodes/simple/node/XorNode.java index 3978f048..30a88dca 100644 --- a/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -21,7 +21,6 @@ public class XorNode extends Node { @Override public Type compute() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; if( in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) -- cgit v1.2.3