diff options
Diffstat (limited to 'chapter18/src/main/java')
6 files changed, 163 insertions, 10 deletions
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java index 194ef4f2..9da49e7d 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java @@ -190,12 +190,14 @@ public class Parser { // the exact single function). CodeGen.CODE.link(fun); + Node rpc = new ParmNode("$rpc",0,TypeRPC.BOT,fun,con(TypeRPC.BOT)).peephole(); + // Build a multi-exit return point for all function returns RegionNode r = new RegionNode((Node)null,null); assert r.inProgress(); PhiNode rmem = new PhiNode(ScopeNode.MEM0,TypeMem.BOT,r,null); PhiNode rrez = new PhiNode(ScopeNode.ARG0,Type.BOTTOM,r,null); - ReturnNode ret = new ReturnNode(r, rmem, rrez, fun, fun._loc); + ReturnNode ret = new ReturnNode(r, rmem, rrez, rpc, fun); fun.setRet(ret); assert ret.inProgress(); STOP.addDef(ret); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java index b836188c..6645d69d 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -109,7 +109,7 @@ public class CallNode extends CFGNode { fun.addDef(this); for( Node use : fun._outputs ) if( use instanceof ParmNode parm ) - parm.addDef(arg(parm._idx)); + parm.addDef(parm._idx==0 ? cend() : arg(parm._idx)); // Call end points to function return cend().addDef(fun.ret()); assert linked(fun); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java index 84058e2b..2d01b4d4 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -1,10 +1,12 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Utils; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFunPtr; +import java.util.BitSet; public class FunNode extends RegionNode { @@ -29,6 +31,14 @@ public class FunNode extends RegionNode { return null; } + public ParmNode rpc() { + ParmNode rpc = null; + for( Node n : _outputs ) + if( n instanceof ParmNode parm && parm._idx==0 ) + { assert rpc==null; rpc=parm; } + return rpc; + } + // Cannot create the Return and Fun at the same time; one has to be first. // So setting the return requires a second step. public void setRet(ReturnNode ret) { _ret=ret; } @@ -78,4 +88,44 @@ public class FunNode extends RegionNode { // Add a new function exit point. public void addReturn(Node ctrl, Node mem, Node rez) { _ret.addReturn(ctrl,mem,rez); } + + // Build the function body + public BitSet body() { + + // Reverse up (stop to start) CFG only, collect bitmap. + BitSet cfgs = new BitSet(); + cfgs.set(_nid); + walkUp(ret(),cfgs ); + + // Top down (start to stop) all flavors. CFG limit to bitmap. + // If data use bottoms out in wrong CFG, returns false - but tries all outputs. + // If any output hits an in-CFG use (e.g. phi), then keep node. + BitSet body = new BitSet(); + walkDown(this, cfgs, body, new BitSet()); + return body; + } + + private static void walkUp(CFGNode n, BitSet cfgs) { + if( cfgs.get(n._nid) ) return; + cfgs.set(n._nid); + if( n instanceof RegionNode r ) + for( int i=1; i<n.nIns(); i++ ) + walkUp(n.cfg(i),cfgs); + else walkUp(n.cfg0(),cfgs); + } + + private static boolean walkDown( Node n, BitSet cfgs, BitSet body, BitSet visit ) { + if( visit.get(n._nid) ) return body.get(n._nid); + visit.set(n._nid); + + if( n instanceof CFGNode && !cfgs.get(n._nid) ) + return false; + if( n.in(0)!=null && !cfgs.get(n.in(0)._nid) ) + return false; + boolean in = n.in(0)!=null || n instanceof CFGNode; + for( Node use : n._outputs ) + in |= walkDown(use,cfgs,body,visit); + if( in ) body.set(n._nid); + return in; + } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 3820a28d..f42adcf6 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -18,17 +18,16 @@ import java.util.BitSet; public class ReturnNode extends CFGNode { public final FunNode _fun; - public final Parser.Lexer _loc; - public ReturnNode(Node ctrl, Node mem, Node data, FunNode fun, Parser.Lexer loc) { - super(ctrl, mem, data); + public ReturnNode(Node ctrl, Node mem, Node data, Node rpc, FunNode fun ) { + super(ctrl, mem, data, rpc); _fun = fun; - _loc = loc; } public Node ctrl() { return in(0); } public Node mem () { return in(1); } public Node expr() { return in(2); } + public Node rpc () { return in(3); } public FunNode fun() { return _fun; } @Override @@ -81,7 +80,7 @@ public class ReturnNode extends CFGNode { private boolean ti=false, tf=false, tp=false, tn=false; // Add a return exit to the current parsing function - void addReturn(Node ctrl, Node rmem, Node expr) { + void addReturn( Node ctrl, Node rmem, Node expr ) { assert inProgress(); // Gather parse-time return types for error reporting @@ -112,7 +111,7 @@ public class ReturnNode extends CFGNode { } @Override public Parser.ParseException err() { - return mt==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_loc) : null; + return 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/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java index cb51a847..ac7d559d 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java @@ -44,6 +44,7 @@ public class Type { static final byte TMEM =13; // All memory (alias 0) or A slice of memory - with specific alias static final byte TSTRUCT =14; // Structs; tuples with named fields static final byte TFLD =15; // Named fields in structs + static final byte TRPC =16; // Return Program Control (Return PC or RPC) public final byte _type; @@ -73,6 +74,7 @@ public class Type { Field.gather(ts); TypeStruct.gather(ts); TypeTuple.gather(ts); + TypeRPC.gather(ts); int sz = ts.size(); for( int i = 0; i < sz; i++ ) ts.add(ts.get(i).dual()); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeRPC.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeRPC.java new file mode 100644 index 00000000..ec2f5f0a --- /dev/null +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeRPC.java @@ -0,0 +1,100 @@ +package com.seaofnodes.simple.type; + +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import java.util.ArrayList; +import java.util.BitSet; +import java.util.HashSet; + +/** + * Return Program Control or Return PC or RPC + */ +public class TypeRPC extends Type { + + // A set of CallEndNode IDs (or StopNode); commonly just one. + // Basically a sparse bit set + final HashSet<Integer> _rpcs; + + // If true, invert the meaning of the bits + final boolean _any; + + private TypeRPC(boolean any, HashSet<Integer> rpcs) { + super(TRPC); + _any = any; + _rpcs = rpcs; + } + private static TypeRPC make(boolean any, HashSet<Integer> rpcs) { + return new TypeRPC(any,rpcs).intern(); + } + + public static TypeRPC constant(int cend) { + HashSet<Integer> rpcs = new HashSet<>(); + rpcs.add(cend); + return make(false,rpcs); + } + + public static final TypeRPC BOT = make(true,new HashSet<>()); + private static final TypeRPC TEST2 = constant(2); + private static final TypeRPC TEST3 = constant(2); + + public static void gather(ArrayList<Type> ts) { ts.add(BOT); ts.add(TEST2); ts.add(TEST3); } + + @Override public String str() { + if( _rpcs.isEmpty() ) + return _any ? "$[ALL]" : "$[]"; + if( _rpcs.size()==1 ) + for( Integer rpc : _rpcs ) + return _any ? "$[-"+rpc+"]" : "$["+rpc+"]"; + return "$["+(_any ? "-" : "")+_rpcs+"]"; + } + + @Override public boolean isConstant() { + return !_any && _rpcs.size()==1; + } + + @Override + public TypeRPC xmeet(Type other) { + TypeRPC rpc = (TypeRPC)other; + // If the two sets are equal, the _any must be unequal (invariant), + // so they cancel and all bits are set. + if( _rpcs.equals(rpc._rpcs) ) + return BOT; + // Classic union of bit sets (which might be infinite). + HashSet<Integer> lhs = _rpcs, rhs = rpc._rpcs; + // Smaller on left + if( lhs.size() > rhs.size() ) { lhs = rpc._rpcs; rhs = _rpcs; } + + HashSet<Integer> rpcs = new HashSet<>(); + boolean any = true; + // If both sets are infinite, intersect. + if( _any && rpc._any ) { + for( Integer i : lhs ) if( rhs.contains(i) ) rpcs.add(i); + + } else if( !_any && !rpc._any ) { + // if neither set is infinite, union. + rpcs.addAll( lhs ); + rpcs.addAll( rhs ); + any = false; + } else { + // If one is infinite, subtract the other from it. + HashSet<Integer> sub = _any ? rpc._rpcs : _rpcs; + HashSet<Integer> inf = _any ? _rpcs : rpc._rpcs; + for( Integer i : inf ) + if( inf.contains(i) && !sub.contains(i) ) + rpcs.add(i); + } + return make(any,rpcs); + } + + @Override + public Type dual() { return make(!_any,_rpcs); } + + @Override + int hash() { return _rpcs.hashCode() ^ (_any ? -1 : 0) ; } + @Override + public boolean eq( Type t ) { + TypeRPC rpc = (TypeRPC)t; // Contract + return _any==rpc._any && _rpcs.equals(rpc._rpcs); + } + +} |