diff options
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/node')
20 files changed, 506 insertions, 114 deletions
diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index b57b305f..de5044d7 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -134,7 +134,7 @@ public class AddNode extends Node { for( int i=1; i<ns.length; i++ ) ns[i] = op.copy(lphi.in(i), rhs instanceof PhiNode ? rhs.in(i) : rhs).peephole(); String label = lphi._label + (rhs instanceof PhiNode rphi ? rphi._label : ""); - Node phi = new PhiNode(label,ns).peephole(); + Node phi = new PhiNode(label,lphi._declaredType,ns).peephole(); // Rotate needs another op, otherwise just the phi return lhs==lphi ? phi : op.copy(lhs.in(1),phi); } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 08ff3789..bf0d3a84 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeMemPtr; import java.util.BitSet; @@ -45,11 +46,25 @@ abstract public class BoolNode extends Node { if( in(1)==in(2) ) return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0)); + // Equals pushes constant to the right; 5==X becomes X==5. + if( this instanceof EQ ) { + if( !(in(2) instanceof ConstantNode) ) { + // con==noncon becomes noncon==con + if( in(1) instanceof ConstantNode ) + return new EQ(in(2),in(1)); + // Equals sorts by NID otherwise: non.high == non.low becomes non.low == non.high + else if( in(1)._nid > in(2)._nid ) + return new EQ(in(2),in(1)); + } + // Equals X==0 becomes a !X + if( (in(2)._type == TypeInteger.ZERO || in(2)._type == TypeMemPtr.NULLPTR) ) + return new NotNode(in(1)); + } + // Do we have ((phi cons) cmp con) ? // Do we have ((phi cons) cmp (phi cons)) ? // Push the compare up through the phi: (phi con0 cmp con, con1 cmp con...) - // No rotate: compares are not associative. - Node phicon = AddNode.phiCon(this,false); + Node phicon = AddNode.phiCon(this,this instanceof EQ); if( phicon!=null ) return phicon; return null; diff --git a/src/main/java/com/seaofnodes/simple/node/CastNode.java b/src/main/java/com/seaofnodes/simple/node/CastNode.java new file mode 100644 index 00000000..fec540f7 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -0,0 +1,38 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.IterPeeps; + +import java.util.BitSet; + +// Upcast (join) the input to a t. Used after guard test to lift an input. +// Can also be used to make a type-assertion if ctrl is null. +public class CastNode extends Node { + private final Type _t; + public CastNode(Type t, Node ctrl, Node in) { + super(ctrl, in); + _t = t; + setType(compute()); + } + + @Override public String label() { return "("+_t.str()+")"; } + + @Override + public String uniqueName() { return "Cast_" + _nid; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + return in(1)._print0(sb.append(label()), visited); + } + + @Override + public Type compute() { + return in(1)._type.join(_t); + } + + @Override + public Node idealize() { + return in(1)._type.isa(_t) ? in(1) : null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 8fd955e9..d760c0df 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -51,9 +51,4 @@ public class ConstantNode extends Node { @Override int hash() { return _con.hashCode(); } - - // Dead control is its own idom root - Node idom() { return null; } - @Override int idepth() { return 0; } - } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 460dce51..1cf4ddaf 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -1,15 +1,16 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeTuple; - import java.util.BitSet; public class IfNode extends MultiNode { public IfNode(Node ctrl, Node pred) { super(ctrl, pred); + IterPeeps.add(this); // Because idoms are complex, just add it } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java new file mode 100644 index 00000000..54689283 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -0,0 +1,72 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +import java.util.BitSet; + +/** + * Load represents extracting a value from inside a memory object, + * in chapter 10 this means Struct fields. + */ +public class LoadNode extends MemOpNode { + + Type _declaredType; + /** + * Load a value from a ptr.field. + * + * @param name The field we are loading + * @param memSlice The whole-memory node - this is updated after a Store + * @param memPtr The ptr to the struct from where we load a field + */ + public LoadNode(String name, Type glb, Node memSlice, Node memPtr) { + super(name, memSlice, memPtr, null); + _declaredType = glb; + } + + @Override + public String label() { return "Load"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); } + + @Override + public Type compute() { + return _declaredType; + } + + @Override + public Node idealize() { + + // Simple Load-after-Store on same address. + if( mem() instanceof StoreNode st && + ptr() == st.ptr() && _name.equals(st._name) ) { // Must check same object + return st.val(); + } + + // 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. + // BEFORE (2 Sts, 1 Ld): AFTER (1 St, 0 Ld): + // 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 ) { + // 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)) ) { + Node ld1 = new LoadNode(_name,_declaredType,memphi.in(1),ptr()).peephole(); + Node ld2 = new LoadNode(_name,_declaredType,memphi.in(2),ptr()).peephole(); + return new PhiNode(_name,_type,memphi.region(),ld1,ld2); + } + } + + return null; + } + + // 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() && _name.equals(st1._name); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index fa9d871e..a0ba973e 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -25,7 +25,7 @@ public class LoopNode extends RegionNode { return inProgress() ? null : super.idealize(); } + // Bypass Region idom, same as the default idom() using use entry in(1) instead of in(0) @Override int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } - @Override Node idom() { return entry(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java new file mode 100644 index 00000000..d811e71a --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -0,0 +1,37 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMemPtr; + +/** + * Convenience common base for Load and Store. + */ +public abstract class MemOpNode extends Node { + + public final String _name; + + public MemOpNode(String name, Node memSlice, Node memPtr, Node value) { + super(null, memSlice, memPtr, value); + _name = name; + } + + public Node mem() { return in(1); } + public Node ptr() { return in(2); } + + @Override + boolean eq(Node n) { + MemOpNode mem = (MemOpNode)n; // Invariant + return _name.equals(mem._name); + } + + @Override + int hash() { return _name.hashCode(); } + + @Override + String err() { + Type ptr = ptr()._type; + return (ptr==Type.BOTTOM || (ptr instanceof TypeMemPtr tmp && tmp._nil) ) + ? "Might be null accessing '" + _name + "'" + : null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 5b055089..8b1b73bf 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -24,5 +24,11 @@ public class MinusNode extends Node { } @Override - public Node idealize() { return null; } + public Node idealize() { + // -(-x) is x + if( in(1) instanceof MinusNode minus ) + return minus.in(1); + + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java new file mode 100644 index 00000000..b13462f5 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -0,0 +1,37 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMemPtr; + +import java.util.BitSet; + +public class NewNode extends Node { + + TypeMemPtr _ptr; + + public NewNode(TypeMemPtr ptr, Node ctrl) { + super(ctrl); + this._ptr = ptr; + } + + @Override + public String label() { return "new"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + sb.append("new "); + return sb.append(_ptr._obj.str()); + } + + @Override + public Type compute() { return _ptr; } + + @Override + public Node idealize() { return null; } + + @Override + boolean eq(Node n) { return this == n; } + + @Override + int hash() { return _ptr.hashCode(); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index a0ec0289..eb6c1697 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -53,15 +53,6 @@ public abstract class Node { /** - * Immediate dominator tree depth, used to approximate a real IDOM during - * parsing where we do not have the whole program, and also peepholes - * change the CFG incrementally. - * <p> - * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} - */ - char _idepth; - - /** * 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. @@ -83,7 +74,9 @@ public abstract class Node { public abstract String label(); // Unique label for debugging, e.g. "Add12" or "Region30" or "EQ99" - public String uniqueName() { return label() + _nid; } + public String uniqueName() { + return label() + _nid; + } // ------------------------------------------------------------------------ @@ -116,31 +109,6 @@ public abstract class Node { // Every Node implements this; a partial-line recursive print abstract StringBuilder _print1(StringBuilder sb, BitSet visited); - - // Print a node on 1 line, columnar aligned, as: - // NNID NNAME DDEF DDEF [[ UUSE UUSE ]] TYPE - // 1234 sssss 1234 1234 1234 1234 1234 1234 tttttt - public void _printLine(StringBuilder sb ) { - sb.append("%4d %-7.7s ".formatted(_nid,label())); - if( isDead() ) { - sb.append("DEAD\n"); - return; - } - for( Node def : _inputs ) - sb.append(def==null ? "____ " : "%4d ".formatted(def._nid)); - for( int i = _inputs.size(); i<3; i++ ) - sb.append(" "); - sb.append(" [[ "); - for( Node use : _outputs ) - sb.append(use==null ? "____ " : "%4d ".formatted(use._nid)); - int lim = 5 - Math.max(_inputs.size(),3); - for( int i = _outputs.size(); i<lim; i++ ) - sb.append(" "); - sb.append(" ]] "); - if( _type!= null ) _type.print(sb); - sb.append("\n"); - } - public String p(int depth) { return IRPrinter.prettyPrint(this,depth); } public boolean isMultiHead() { return false; } @@ -165,6 +133,8 @@ public abstract class Node { public boolean isCFG() { return false; } + public boolean isMem() { return false; } + /** * Change a <em>def</em> into a Node. Keeps the edges correct, by removing * the corresponding <em>use->def</em> edge. This may make the original @@ -195,6 +165,7 @@ public abstract class Node { old_def.kill(); // Kill old def // Set the new_def over the old (killed) edge _inputs.set(idx,new_def); + moveDepsToWorklist(); // Return self for easy flow-coding return new_def; } @@ -282,6 +253,8 @@ public abstract class Node { public <N extends Node> N keep() { addUse(null); return (N)this; } // Remove bogus null. public <N extends Node> N unkeep() { delUse(null); return (N)this; } + // Test "keep" status + public boolean iskeep() { return Utils.find(_outputs,null) != -1; } // Replace self with nnn in the graph, making 'this' go dead @@ -337,7 +310,7 @@ public abstract class Node { Type old = setType(compute()); // Replace constant computations from non-constants with a constant node - if (!(this instanceof ConstantNode) && _type.isHighOrConst() ) + if( !(this instanceof ConstantNode) && _type.isHighOrConst() ) return new ConstantNode(_type).peepholeOpt(); // Global Value Numbering @@ -372,7 +345,7 @@ public abstract class Node { private Node deadCodeElim(Node m) { // If self is going dead and not being returned here (Nodes returned // from peephole commonly have no uses (yet)), then kill self. - if( m != this && isUnused() ) { + if( m != this && isUnused() && !isDead() ) { // Killing self - and since self recursively kills self's inputs we // might end up killing 'm', which we are returning as a live Node. // So we add a bogus extra null output edge to stop kill(). @@ -472,9 +445,9 @@ public abstract class Node { public Node dep(int idx) { return _deps.get(idx); } /** - * Add a node to the list o dependencies. Only add it if its not - * an input or output of this node, that is, it is at least one step - * away. The node being added must benefit from this node being peepholed. + * Add a node to the list of dependencies. Only add it if its not an input + * or output of this node, that is, it is at least one step away. The node + * being added must benefit from this node being peepholed. */ Node addDep( Node dep ) { // Running peepholes during the big assert cannot have side effects @@ -563,14 +536,11 @@ public abstract class Node { } /** - * Does this node contain all constants? - * Ignores in(0), as is usually control. - * In an input is not a constant, we add dep as - * a dependency to it, because dep can make progress - * if the input becomes a constant later. - * It is sufficient for one of the non-const - * inputs to have the dependency so we don't bother - * checking the rest. + * Does this node contain all constants? Ignores in(0), as is usually + * control. In an input is not a constant, we add dep as a dependency to + * it because dep can make progress if the input becomes a constant later. + * It is sufficient for one of the non-const inputs to have the dependency, + * so we don't bother checking the rest. */ boolean allCons(Node dep) { for( int i=1; i<nIns(); i++ ) @@ -581,8 +551,15 @@ public abstract class Node { return true; } - // Return the immediate dominator of this Node and compute dom tree depth. - Node idom() { return in(0); } + + /** + * Immediate dominator tree depth, used to approximate a real IDOM depth + * during parsing where we do not have the whole program, and also + * peepholes change the CFG incrementally. + * <p> + * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} + */ + public char _idepth; // IDOM depth approx; Zero is unset; non-zero is cached legit // Find the lowest common ancestor in the current dominator tree. Node domLCA(Node rhs) { @@ -605,11 +582,17 @@ public abstract class Node { } + // Return the immediate dominator of this Node. + Node idom() { return in(0); } + // Make a shallow copy (same class) of this Node, with given inputs and // empty outputs and a new Node ID. The original inputs are ignored. // Does not need to be implemented in isCFG() nodes. Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } + // Report any post-optimize errors + String 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. diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index a9a69c59..83141836 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -1,8 +1,7 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeInteger; - +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.type.*; import java.util.BitSet; public class NotNode extends Node { @@ -18,9 +17,24 @@ public class NotNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 ) + Type t0 = in(1)._type; + switch( t0 ) { + case TypeInteger i0: return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0; - return in(1)._type==Type.TOP ? TypeInteger.TOP : TypeInteger.BOT; + case TypeMemPtr p0: + // top->top, bot->bot, null->1, *void->0, not-null ptr->0, ptr/nil->bot + // If input in null then true + // If input is not null ptr then false + if( p0 == TypeMemPtr.TOP ) return TypeInteger.TOP; + if( p0 == TypeMemPtr.NULLPTR ) return TypeInteger.constant(1); + if( !p0._nil ) return TypeInteger.constant(0); + return TypeInteger.BOT; + case Type t: + if( t0.getClass() != Type.class ) + // Only doing NOT on ints and ptrs + throw Utils.TODO(); + return t0==Type.TOP ? TypeInteger.TOP : TypeInteger.BOT; + } } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 13c9423d..bdf50847 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -1,6 +1,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.Utils; import java.util.BitSet; @@ -8,7 +10,11 @@ public class PhiNode extends Node { final String _label; - public PhiNode(String label, Node... inputs) { super(inputs); _label = label; } + // The Phi type we compute must stay within the domain of the Phi. + // 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; } @@ -29,17 +35,21 @@ public class PhiNode extends Node { Node region() { return in(0); } @Override public boolean isMultiTail() { return true; } + @Override + public boolean isMem() { return _declaredType instanceof TypeMem; } @Override public Type compute() { if( !(region() instanceof RegionNode r) ) return region()._type==Type.XCONTROL ? Type.TOP : _type; - if( r.inProgress() ) return Type.BOTTOM; - Type t = Type.TOP; + // During parsing Phis have to be computed type pessimistically. + if( r.inProgress() ) return _declaredType; + // Set type to local top of the starting type + Type t = _declaredType.glb().dual(); for (int i = 1; i < nIns(); i++) // If the region's control input is live, add this as a dependency // to the control because we can be peeped should it become dead. - if( r.in(i).addDep(this)._type != Type.XCONTROL && in(i) != this ) + if( r.in(i).addDep(this)._type != Type.XCONTROL ) t = t.meet(in(i)._type); return t; } @@ -69,11 +79,35 @@ public class PhiNode extends Node { lhss[i] = in(i).in(1); rhss[i] = in(i).in(2); } - Node phi_lhs = new PhiNode(_label,lhss).peephole(); - Node phi_rhs = new PhiNode(_label,rhss).peephole(); + 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. + if( nIns()==3 ) { + if( in(1) instanceof CastNode cast && cast.in(1).addDep(this)==in(2) ) return in(2); + if( in(2) instanceof CastNode cast && cast.in(1).addDep(this)==in(1) ) return in(1); + } + // If merging a null-checked null and the checked value, just use the value. + // if( val ) ..; phi(Region,False=0/null,True=val); + // then replace with plain val. + if( nIns()==3 ) { + int nullx = -1; + if( in(1)._type == in(1)._type.makeInit() ) nullx = 1; + if( in(2)._type == in(2)._type.makeInit() ) nullx = 2; + if( nullx != -1 ) { + Node val = in(3-nullx); + if( region().idom() instanceof IfNode iff && iff.pred().addDep(this)==val ) { + // Must walk the idom on the null side to make sure we hit False. + Node idom = region().in(nullx); + while( idom.in(0) != iff ) idom = idom.idom(); + if( idom instanceof ProjNode proj && proj._idx==1 ) + return val; + } + } + } + return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 0ed9441d..735fcdf3 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.type.TypeTuple; import java.util.BitSet; @@ -27,6 +28,7 @@ public class ProjNode extends Node { @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; } @Override public boolean isMultiTail() { return in(0).isMultiHead(); } + @Override public boolean isMem() { return _type instanceof TypeMem; } public MultiNode ctrl() { return (MultiNode)in(0); } @@ -38,8 +40,14 @@ public class ProjNode extends Node { @Override public Node idealize() { - if( ctrl()._type instanceof TypeTuple tt && tt._types[1-_idx]==Type.XCONTROL ) // Only true for IfNodes - return ctrl().in(0); // We become our input control + 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 ProjNode((MultiNode)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/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 71bef275..f7a56503 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -35,6 +35,7 @@ public class RegionNode extends Node { @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 @@ -51,15 +52,25 @@ public class RegionNode extends Node { while( nouts != nOuts() ) { nouts = nOuts(); for( int i=0; i<nOuts(); i++ ) - if( out(i) instanceof PhiNode phi && phi.nIns()==nIns() ) + if( out(i) instanceof PhiNode phi && phi.nIns()==nIns() ) { phi.delDef(path); + IterPeeps.addAll(phi._outputs); + } } return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path); } // If down to a single input, become that input - if( nIns()==2 && !hasPhi() ) { + 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( !hasPhi() && // No Phi users, just a control user + in(1) instanceof ProjNode p1 && + in(2) instanceof ProjNode p2 && + p1.in(0)==p2.in(0) && + p1.in(0) instanceof IfNode iff ) + return iff.ctrl(); + return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 922a3649..f13f3708 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -4,19 +4,11 @@ import com.seaofnodes.simple.type.*; import java.util.BitSet; -/** - * The Return node has two inputs. The first input is a control node and the - * second is the data node that supplies the return value. - * <p> - * In this presentation, Return functions as a Stop node, since multiple <code>return</code> statements are not possible. - * The Stop node will be introduced in Chapter 6 when we implement <code>if</code> statements. - * <p> - * The Return's output is the value from the data node. - */ +/** Keeps the return value and all preceding memory effects alive. */ public class ReturnNode extends Node { - public ReturnNode(Node ctrl, Node data) { - super(ctrl, data); + public ReturnNode(Node ctrl, Node data, ScopeNode scope) { + super(ctrl, data, scope.lookup("$mem")); } public Node ctrl() { return in(0); } @@ -27,7 +19,9 @@ public class ReturnNode extends Node { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - return expr()._print0(sb.append("return "), visited).append(";"); + sb.append("return "); + expr()._print0(sb, visited); + return sb.append(";"); } @Override public boolean isCFG() { return true; } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 3abea54d..455f4b3a 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.type.TypeMemPtr; import java.util.*; @@ -23,10 +25,16 @@ public class ScopeNode extends Node { */ public final Stack<HashMap<String, Integer>> _scopes; + /** + * Tracks declared types for every name + */ + public Stack<HashMap<String, Type>> _types; + // A new ScopeNode public ScopeNode() { _scopes = new Stack<>(); + _types = new Stack<>(); _type = Type.BOTTOM; } @@ -69,14 +77,15 @@ public class ScopeNode extends Node { @Override public Node idealize() { return null; } - public void push() { _scopes.push(new HashMap<>()); } - public void pop() { popN(_scopes.pop().size()); } + public void push() { _scopes.push(new HashMap<>()); _types.push(new HashMap<>()); } + public void pop() { popN(_scopes.pop().size()); _types.pop(); } /** * Create a new name in the current scope */ - public Node define( String name, Node n ) { + public Node define( String name, Type declaredType, Node n ) { HashMap<String,Integer> syms = _scopes.lastElement(); + _types.lastElement().put(name,declaredType); if( syms.put(name,nIns()) != null ) return null; // Double define return addDef(n); @@ -97,7 +106,7 @@ public class ScopeNode extends Node { public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); } /** * Both recursive lookup and update. - * + * <p> * A shared implementation allows us to create lazy phis both during * lookups and updates; the lazy phi creation is part of chapter 8. * @@ -120,12 +129,21 @@ public class ScopeNode extends Node { // Set real Phi in the loop head // The phi takes its one input (no backedge yet) from a recursive // lookup, which might have insert a Phi in every loop nest. - : loop.setDef(idx,new PhiNode(name,loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); + : loop.setDef(idx,new PhiNode(name, lookupDeclaredType(name),loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); setDef(idx,old); } return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer } + // Return declared type + public Type lookupDeclaredType( String name ) { + for( int i=_types.size(); i>0; i-- ) { + Type t = _types.get(i-1).get(name); + if( t != null ) return t; + } + return null; + } + public Node ctrl() { return in(0); } /** @@ -162,8 +180,10 @@ public class ScopeNode extends Node { // 3) Ensure that the order of defs is the same to allow easy merging for( HashMap<String,Integer> syms : _scopes ) dup._scopes.push(new HashMap<>(syms)); + for( HashMap<String,Type> ts : _types ) + dup._types.push(ts); // Types don't change, just keep stacks aligned - dup.addDef(ctrl()); // Control input is just copied + dup.addDef(ctrl()); // Control input is just copied for( int i=1; i<nIns(); i++ ) // For lazy phis on loops we use a sentinel // that will trigger phi creation on update @@ -187,8 +207,9 @@ public class ScopeNode extends Node { if( in(i) != that.in(i) ) // No need for redundant Phis // If we are in lazy phi mode we need to a lookup // by name as it will trigger a phi creation - setDef(i, new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); + setDef(i, new PhiNode(ns[i], this.lookupDeclaredType(ns[i]), r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); that.kill(); // Kill merged scope + IterPeeps.add(r); return r.unkeep().peephole(); } @@ -216,11 +237,68 @@ public class ScopeNode extends Node { IterPeeps.addAll(phi._outputs); phi.moveDepsToWorklist(); if( in != phi ) { - phi.subsume(in); + if( !phi.iskeep() ) // Keeping phi around for parser elsewhere + phi.subsume(in); setDef(i,in); // Set the update back into Scope } } } } + + + // Up-casting: using the results of an If to improve a value. + // E.g. "if( ptr ) ptr.field;" is legal because ptr is known not-null. + + // This Scope looks for direct variable uses, or certain simple + // combinations, and replaces the variable with the upcast variant. + public Node upcast( Node ctrl, Node pred, boolean invert ) { + if( ctrl._type==Type.XCONTROL ) return null; + // A single negation is handled below. For !!p (including p != null), + // also refine the underlying p without changing the Boolean result. + if( pred instanceof NotNode not && not.in(1) instanceof NotNode ) { + pred.keep(); // Recursive peepholes may rediscover this Not. + upcast(ctrl,not.in(1),!invert); + pred.unkeep(); + } + // Invert the If conditional + if( invert ) + pred = pred instanceof NotNode not ? not.in(1) : IterPeeps.add(new NotNode(pred).peephole()); + + // Direct use of a value as predicate. This is a zero/null test. + if( Utils.find(_inputs, pred) != -1 ) { + if( !(pred._type instanceof TypeMemPtr tmp) ) + // Must be an `int`, since int and ptr are the only two value types + // being tested. No representation for a generic not-null int, so no upcast. + return null; + if( tmp.isa(TypeMemPtr.VOIDPTR) ) + return null; // Already not-null, no reason to upcast + // Upcast the ptr to not-null ptr, and replace in scope + return replace(pred,new CastNode(TypeMemPtr.VOIDPTR,ctrl,pred).peephole()); + } + + if( pred instanceof NotNode not ) { + // Direct use of a !value as predicate. This is a zero/null test. + if( Utils.find(_inputs, not.in(1)) != -1 ) { + Type tinit = not.in(1)._type.makeInit(); + if( not.in(1)._type.isa(tinit) ) return null; // Already zero/null, no reason to upcast + return replace(not.in(1), new ConstantNode(tinit).peephole()); + } + } + // Apr/9/2024: Attempted to replace X with Y if guarded by a test of + // X==Y. This didn't seem to help very much, or at least in the test + // cases seen so far was a very minor help. + + // No upcast + return null; + } + + private Node replace( Node old, Node cast ) { + assert old!=null && old!=cast; + for( int i=0; i<nIns(); i++ ) + if( in(i)==old ) + setDef(i,cast); + return cast; + } + } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 1e3559ce..1ca52af0 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,25 +1,15 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeTuple; - +import com.seaofnodes.simple.type.*; import java.util.BitSet; -/** - * The Start node represents the start of the function. For now, we do not - * have any inputs to Start because our function does not yet accept - * parameters. When we add parameters the value of Start will be a tuple, and - * will require Projections to extract the values. We discuss this in detail - * in Chapter 9: Functions and Calls. - */ +/** The entry tuple: control, initial whole-memory state, and argument. */ public class StartNode extends MultiNode { - final TypeTuple _args; public StartNode(Type[] args) { super(); - _args = TypeTuple.make(args); - _type = _args; + _type = _args = TypeTuple.make(args); } @Override @@ -40,8 +30,6 @@ public class StartNode extends MultiNode { public Node idealize() { return null; } // No immediate dominator, and idepth==0 - @Override - Node idom() { return null; } @Override int idepth() { return 0; } - + @Override Node idom() { return null; } } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index 6ed80df4..cb4126f5 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.IterPeeps; @@ -51,9 +53,22 @@ public class StopNode extends Node { return null; } + @Override public Node idom() { return null; } + public Node addReturn(Node node) { return addDef(node); } - public StopNode iterate() { return IterPeeps.iterate(this); } + public StopNode iterate() { return IterPeeps.iterate(this).typeCheck(); } + public StopNode typeCheck() { + var obs = Parser.PARSER == null ? null : Parser.PARSER._obs; + String err = walk(n -> { + String msg = n.err(); + if( msg != null && obs != null ) obs.error(n, msg); + return msg; + }); + if( err != null ) throw new RuntimeException(err); + if( obs != null ) obs.phase("TypeCheck"); + return this; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java new file mode 100644 index 00000000..4bc67c3c --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -0,0 +1,66 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.*; + +import java.util.BitSet; + +/** + * Store represents setting a value to a memory based object, in chapter 10 + * this means a field inside a struct. + */ +public class StoreNode extends MemOpNode { + + /** + * @param name The struct field we are assigning to + * @param memSlice The whole-memory node - this is updated after a Store + * @param memPtr The ptr to the struct where we will store a value + * @param value Value to be stored + */ + public StoreNode(String name, Node memSlice, Node memPtr, Node value) { + super(name, memSlice, memPtr, value); + } + + @Override + public String label() { return "Store"; } + @Override + public boolean isMem() { return true; } + public Node val() { return in(3); } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + return sb.append(".").append(_name).append("=").append( val()).append(";"); + } + + @Override + public Type compute() { return TypeMem.BOT; } + + @Override + public Node idealize() { + + // Simple store-after-store on same address. Should pick up the + // required init-store being stomped by a first user store. + if( mem() instanceof StoreNode st && + ptr()==st.ptr() && _name.equals(st._name) && // Must check same object + 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. + st.checkNoUseBeyond(this) ) { + setDef(1,st.mem()); + return this; + } + + return null; + } + + // Check that `this` has no uses beyond `that` + private boolean checkNoUseBeyond(Node that) { + if( nOuts()==1 ) return true; + // Add deps on the other uses (can be e.g. ScopeNode mid-parse) so that + // when the other uses go away we can retry. + for( Node use : _outputs ) + if( use != that ) + use.addDep(that); + return false; + } + +} |