From 381227eeb0262378f44a68b4b39b8248399a02b6 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 3 Jan 2025 17:01:34 -0800 Subject: Handle recursive functions Define a "Return PC" type, which maps a simple bit vector to call sites. Returns take an RPC; function headers merge RPC from all callers. Work over the Eval2 control path to support recursion; probably 90% to closures now as well. --- .../main/java/com/seaofnodes/simple/Parser.java | 4 +- .../java/com/seaofnodes/simple/node/CallNode.java | 2 +- .../java/com/seaofnodes/simple/node/FunNode.java | 54 ++++++++++- .../com/seaofnodes/simple/node/ReturnNode.java | 11 ++- .../main/java/com/seaofnodes/simple/type/Type.java | 2 + .../java/com/seaofnodes/simple/type/TypeRPC.java | 100 +++++++++++++++++++++ 6 files changed, 163 insertions(+), 10 deletions(-) create mode 100644 chapter18/src/main/java/com/seaofnodes/simple/type/TypeRPC.java (limited to 'chapter18/src/main') 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 _rpcs; + + // If true, invert the meaning of the bits + final boolean _any; + + private TypeRPC(boolean any, HashSet rpcs) { + super(TRPC); + _any = any; + _rpcs = rpcs; + } + private static TypeRPC make(boolean any, HashSet rpcs) { + return new TypeRPC(any,rpcs).intern(); + } + + public static TypeRPC constant(int cend) { + HashSet 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 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 lhs = _rpcs, rhs = rpc._rpcs; + // Smaller on left + if( lhs.size() > rhs.size() ) { lhs = rpc._rpcs; rhs = _rpcs; } + + HashSet 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 sub = _any ? rpc._rpcs : _rpcs; + HashSet 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); + } + +} -- cgit v1.2.3