diff options
Diffstat (limited to 'graph/src/main/java')
3 files changed, 105 insertions, 20 deletions
diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphGroups.java b/graph/src/main/java/com/seaofnodes/graph/GraphGroups.java index 75bb90e0..7e46f809 100644 --- a/graph/src/main/java/com/seaofnodes/graph/GraphGroups.java +++ b/graph/src/main/java/com/seaofnodes/graph/GraphGroups.java @@ -10,7 +10,7 @@ final class GraphGroups { static ArrayList<Group> build(ArrayList<Node> nodes) { var result = new ArrayList<Group>(); boolean any=false; - for( Node n : nodes ) if( n.kind()==Kind.FUN || n.kind()==Kind.LOOP ) { any=true; break; } + for( Node n : nodes ) if( n.kind()==Kind.FUN || n.kind()==Kind.LOOP || n.label().equals("If") ) { any=true; break; } if( !any ) return result; int len = nodes.getLast().id()+1; Node[] ns = new Node[len]; @@ -49,13 +49,13 @@ final class GraphGroups { // Natural loops: walk backwards from the backedge, stopping at the // header. An unfinished loop has only its header until it closes. - var loops = new ArrayList<Node>(); + var parts = new ArrayList<Node>(); BitSet[] body = new BitSet[len]; for( Node n : nodes ) if( n.kind()==Kind.LOOP ) { int id = n.id(), back = def(n,2); BitSet set = body[id] = new BitSet(); set.set(id); - loops.add(n); + parts.add(n); if( back==0 || ns[back]==null ) continue; head=tail=0; if( back!=id ) { set.set(back); work[tail++]=back; } @@ -71,14 +71,42 @@ final class GraphGroups { } if( outside || !closed ) { set.clear(); set.set(id); } } - // Outer loops first. Simple's structured CFG makes these sets nested - // or disjoint. - loops.sort((a,b) -> Integer.compare(body[b.id()].cardinality(),body[a.id()].cardinality())); + // Look for a closed If/Region diamond. Reachable joins are considered + // nearest first; a candidate must have no other CFG entry or exit. + for( Node n : nodes ) if( n.kind()==Kind.CTRL && n.label().equals("If") && uses[n.id()].length==2 ) { + BitSet seen = new BitSet(); + head=tail=0; + work[tail++]=n.id(); seen.set(n.id()); + while( head<tail ) { + int id=work[head++]; + if( ns[id].kind()==Kind.REGION ) { + BitSet set=diamond(n.id(),id,ns,preds,uses); + if( set!=null ) { body[n.id()]=set; parts.add(n); break; } + } + for( int use : uses[id] ) if( !seen.get(use) ) { + seen.set(use); work[tail++]=use; + } + } + } + // Outer regions first. Only nested or disjoint sets can form boxes; + // overlapping loop/diamond candidates keep the already accepted group. + parts.sort((a,b) -> Integer.compare(body[b.id()].cardinality(),body[a.id()].cardinality())); int[] par = new int[len], home = new int[len]; Arrays.fill(home,-1); for( Node n : nodes ) if( cfg(n) ) home[n.id()] = fun[n.id()]; - for( Node n : loops ) { + var accepted = new ArrayList<Node>(); + BitSet gids = new BitSet(); + for( Node n : parts ) { int id=n.id(); + boolean fits=true; + for( Node p : accepted ) if( body[id].intersects(body[p.id()]) ) { + BitSet rest=(BitSet)body[id].clone(); + rest.andNot(body[p.id()]); + if( !rest.isEmpty() || body[id].get(p.id()) ) { fits=false; break; } + } + if( !fits ) continue; + accepted.add(n); + gids.set(id); par[id]=home[id]; for( int i=body[id].nextSetBit(0); i>=0; i=body[id].nextSetBit(i+1) ) home[i]=id; } @@ -92,32 +120,51 @@ final class GraphGroups { anchor!=0 && ns[anchor]!=null && cfg(ns[anchor]) ) home[id]=home[anchor]; } - // Floating values belong to the common enclosing group of their uses. - // A Phi's input is used on the corresponding predecessor, not at the - // header (especially the entry input of a loop Phi). + // Compute input and output ownership independently, so a floating chain + // between two regions cannot pull itself into either end. Null slots and + // parser/lifetime associations do not nominate a region. Phi uses refer + // to the Phi itself, not to its incoming CFG path. BitSet fixed = new BitSet(); for( Node n : nodes ) if( home[n.id()]>=0 ) fixed.set(n.id()); + int[] ins=home.clone(), outs=home.clone(); boolean changed; do { changed=false; for( Node n : nodes ) for( Edge e : n.edges() ) { int id=e.def(); - if( id==0 || ns[id]==null || fixed.get(id) || e.role()==Role.ASSOC ) continue; - int site=n.id(); - if( n.kind()==Kind.PHI && e.idx()>0 ) { - Node reg=ns[def(n,0)]; - site=reg==null ? 0 : def(reg,e.idx()); + if( id==0 || ns[id]==null || e.role()==Role.ASSOC ) continue; + if( !fixed.get(n.id()) && ins[id]>=0 ) { + int next=lca(ins[n.id()],ins[id],par); + if( next!=ins[n.id()] ) { ins[n.id()]=next; changed=true; } + } + if( !fixed.get(id) && outs[n.id()]>=0 ) { + int next=lca(outs[id],outs[n.id()],par); + if( next!=outs[id] ) { outs[id]=next; changed=true; } } - int grp=site==0 ? 0 : home[site]; - if( grp<0 ) continue; - int next=lca(home[id],grp,par); + } + } while( changed ); + for( Node n : nodes ) if( !fixed.get(n.id()) ) { + home[n.id()]=owner(ins[n.id()],outs[n.id()],par); + } + // Unattached floating users may have no directional anchor. Check the + // actual neighbors too, widening unsupported claims until they settle. + // Only moving outward avoids self-supporting cycles of floating nodes. + do { + changed=false; + Arrays.fill(ins,-1); Arrays.fill(outs,-1); + for( Node n : nodes ) for( Edge e : n.edges() ) if( e.def()!=0 && e.role()!=Role.ASSOC ) { + ins[n.id()]=lca(ins[n.id()],home[e.def()],par); + outs[e.def()]=lca(outs[e.def()],home[n.id()],par); + } + for( Node n : nodes ) if( !fixed.get(n.id()) ) { + int id=n.id(), next=lca(home[id],owner(ins[id],outs[id],par),par); if( next!=home[id] ) { home[id]=next; changed=true; } } } while( changed ); // Projections and their MultiNode are one display box. for( Node n : nodes ) if( n.proj()!=null && n.proj().par()!=0 ) home[n.id()]=home[n.proj().par()]; - for( Node n : nodes ) if( n.kind()==Kind.FUN || n.kind()==Kind.LOOP ) { + for( Node n : nodes ) if( n.kind()==Kind.FUN || gids.get(n.id()) ) { int id=n.id(), size=0; for( Node m : nodes ) if( home[m.id()]==id ) size++; int[] ids = new int[size]; @@ -128,6 +175,30 @@ final class GraphGroups { return result; } + private static BitSet diamond(int entry, int exit, Node[] ns, int[][] preds, int[][] uses) { + BitSet set=new BitSet(); + int[] todo=new int[ns.length]; + int head=0, tail=0; + todo[tail++]=entry; set.set(entry); + while( head<tail ) { + int id=todo[head++]; + if( id==exit ) continue; + if( uses[id].length==0 || ns[id].kind()==Kind.FUN || + ns[id].kind()==Kind.START || ns[id].kind()==Kind.UNIT ) return null; + for( int use : uses[id] ) if( !set.get(use) ) { set.set(use); todo[tail++]=use; } + } + if( !set.get(exit) ) return null; + for( int id=set.nextSetBit(0); id>=0; id=set.nextSetBit(id+1) ) if( id!=entry ) + for( int p : preds[id] ) if( !set.get(p) ) return null; + // Reject trapped cycles as well as paths to another exit. + BitSet reaches=new BitSet(); + head=tail=0; + todo[tail++]=exit; reaches.set(exit); + while( head<tail ) for( int p : preds[todo[head++]] ) + if( set.get(p) && !reaches.get(p) ) { reaches.set(p); todo[tail++]=p; } + return reaches.equals(set) ? set : null; + } + private static int lca(int a, int b, int[] par) { if( a<0 ) return b; for( int x=a; x!=0; x=par[x] ) @@ -135,6 +206,15 @@ final class GraphGroups { return 0; } + private static int owner(int a, int b, int[] par) { + a=Math.max(0,a); b=Math.max(0,b); + if( a==0 ) return b; + if( b==0 || a==b ) return a; + // Sibling nominations leave the node between the regions. Nested + // nominations agree on the enclosing region (e.g. a function and loop). + return lca(a,b,par); + } + private static int def(Node n, int idx) { for( Edge e : n.edges() ) if( e.idx()==idx ) return e.def(); return 0; diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphJson.java b/graph/src/main/java/com/seaofnodes/graph/GraphJson.java index fd37d5a9..004f6827 100644 --- a/graph/src/main/java/com/seaofnodes/graph/GraphJson.java +++ b/graph/src/main/java/com/seaofnodes/graph/GraphJson.java @@ -63,6 +63,7 @@ public class GraphJson { str(sb, edge.role().name()); sb.append(",\"label\":"); str(sb, edge.label()); + if( edge.jump()!=0 ) sb.append(",\"jump\":").append(edge.jump()); sb.append('}'); } sb.append("],\"proj\":"); diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java b/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java index 4d14ed10..b53f3211 100644 --- a/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java +++ b/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java @@ -34,8 +34,12 @@ public record GraphSnapshot(int ver, String comp, long step, * idx is the input slot on that use: use.in(idx) == def. * Each slot has a record, including holes (def == 0). * label is an optional binding name, not markup. + * jump is a known function entry for a CallEnd link, or zero; def stays the + * actual Return. The browser can replace the drawn link with a shortcut. */ - public record Edge(int idx, int def, Role role, String label) { } + public record Edge(int idx, int def, Role role, String label, int jump) { + public Edge(int idx, int def, Role role, String label) { this(idx,def,role,label,0); } + } /** Projections remain real nodes; par == 0 means no parent is attached. */ public record Projection(int par, int idx) { } |