From 39f4a5e70b2ceb9ccd273b8d8ec7ea9f44269edf Mon Sep 17 00:00:00 2001 From: jjenista Date: Mon, 4 Jan 2010 23:02:37 +0000 Subject: [PATCH] more implementation --- .../Analysis/Disjoint/DisjointAnalysis.java | 3 +- Robust/src/Analysis/Disjoint/ReachGraph.java | 160 +++++++++++++++++- Robust/src/Analysis/Disjoint/RefSrcNode.java | 14 +- Robust/src/Tests/disjoint/simple/test.java | 11 +- 4 files changed, 172 insertions(+), 16 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index 40a3919a..ffec0c9b 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -548,7 +548,8 @@ public class DisjointAnalysis { ReachGraph heapForThisCall_old = getIHMcontribution( mdCallee, fc ); - ReachGraph heapForThisCall_cur = rg.makeCalleeView( fc ); + ReachGraph heapForThisCall_cur = rg.makeCalleeView( fc, + fmCallee ); if( !heapForThisCall_cur.equals( heapForThisCall_old ) ) { // if heap at call site changed, update the contribution, diff --git a/Robust/src/Analysis/Disjoint/ReachGraph.java b/Robust/src/Analysis/Disjoint/ReachGraph.java index 7cd6adde..068c5a96 100644 --- a/Robust/src/Analysis/Disjoint/ReachGraph.java +++ b/Robust/src/Analysis/Disjoint/ReachGraph.java @@ -28,7 +28,7 @@ public class ReachGraph { // use to disable improvements for comparison protected static final boolean DISABLE_STRONG_UPDATES = false; - protected static final boolean DISABLE_GLOBAL_SWEEP = false; + protected static final boolean DISABLE_GLOBAL_SWEEP = true; protected static int allocationDepth = -1; protected static TypeUtil typeUtil = null; @@ -87,6 +87,7 @@ public class ReachGraph { TypeDescriptor typeToUse = null; if( allocSite != null ) { typeToUse = allocSite.getType(); + allocSites.add( allocSite ); } else { typeToUse = type; } @@ -3325,14 +3326,159 @@ public class ReachGraph { // use this method to make a new reach graph that is - // what the callee from the FlatCall would start with - // from arguments and heap taken from this reach graph - public ReachGraph makeCalleeView( FlatCall fc ) { - ReachGraph calleeView = new ReachGraph(); + // what heap the FlatMethod callee from the FlatCall + // would start with reaching from its arguments in + // this reach graph + public ReachGraph makeCalleeView( FlatCall fc, + FlatMethod fm ) { + + // the callee view is a new graph: DON'T MODIFY + // *THIS* graph + ReachGraph rg = new ReachGraph(); + + // track what parts of this graph have already been + // added to callee view, variables not needed. + // Note that we need this because when we traverse + // this caller graph for each parameter we may find + // nodes and edges more than once (which the per-param + // "visit" sets won't show) and we only want to create + // an element in the new callee view one time + Set callerNodesCopiedToCallee = new HashSet(); + Set callerEdgesCopiedToCallee = new HashSet(); + + // a conservative starting point is to take the + // mechanically-reachable-from-arguments graph + // as opposed to using reachability information + // to prune the graph further + for( int i = 0; i < fm.numParameters(); ++i ) { - return calleeView; - } + // for each parameter index, get the symbol in the + // caller view and callee view + + // argument defined here is the symbol in the caller + TempDescriptor tdArg = fc.getArgMatchingParamIndex( fm, i ); + + // parameter defined here is the symbol in the callee + TempDescriptor tdParam = fm.getParameter( i ); + + // use these two VariableNode objects to translate + // between caller and callee--its easy to compare + // a HeapRegionNode across callee and caller because + // they will have the same heap region ID + VariableNode vnCaller = this.getVariableNodeFromTemp( tdArg ); + VariableNode vnCallee = rg.getVariableNodeFromTemp( tdParam ); + + // now traverse the caller view using the argument to + // build the callee view which has the parameter symbol + Set toVisitInCaller = new HashSet(); + Set visitedInCaller = new HashSet(); + toVisitInCaller.add( vnCaller ); + + while( !toVisitInCaller.isEmpty() ) { + RefSrcNode rsnCaller = toVisitInCaller.iterator().next(); + RefSrcNode rsnCallee; + + toVisitInCaller.remove( rsnCaller ); + visitedInCaller.add( rsnCaller ); + + // FIRST - setup the source end of an edge + + if( rsnCaller == vnCaller ) { + // if the caller node is the param symbol, we + // have to do this translation for the callee + rsnCallee = vnCallee; + } else { + // otherwise the callee-view node is a heap + // region with the same ID, that may or may + // not have been created already + assert rsnCaller instanceof HeapRegionNode; + + HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller; + if( !callerNodesCopiedToCallee.contains( rsnCaller ) ) { + rsnCallee = + rg.createNewHeapRegionNode( hrnSrcCaller.getID(), + hrnSrcCaller.isSingleObject(), + hrnSrcCaller.isNewSummary(), + hrnSrcCaller.isFlagged(), + hrnSrcCaller.getType(), + hrnSrcCaller.getAllocSite(), + hrnSrcCaller.getAlpha(), + hrnSrcCaller.getDescription() + ); + callerNodesCopiedToCallee.add( rsnCaller ); + } else { + rsnCallee = rg.id2hrn.get( hrnSrcCaller.getID() ); + } + } + + // SECOND - go over all edges from that source + + Iterator itrRefEdges = rsnCaller.iteratorToReferencees(); + while( itrRefEdges.hasNext() ) { + RefEdge reCaller = itrRefEdges.next(); + HeapRegionNode hrnCaller = reCaller.getDst(); + HeapRegionNode hrnCallee; + + // THIRD - setup destination ends of edges + + if( !callerNodesCopiedToCallee.contains( hrnCaller ) ) { + hrnCallee = + rg.createNewHeapRegionNode( hrnCaller.getID(), + hrnCaller.isSingleObject(), + hrnCaller.isNewSummary(), + hrnCaller.isFlagged(), + hrnCaller.getType(), + hrnCaller.getAllocSite(), + hrnCaller.getAlpha(), + hrnCaller.getDescription() + ); + callerNodesCopiedToCallee.add( hrnCaller ); + } else { + hrnCallee = rg.id2hrn.get( hrnCaller.getID() ); + } + + // FOURTH - copy edge over if needed + if( !callerEdgesCopiedToCallee.contains( reCaller ) ) { + rg.addRefEdge( rsnCallee, + hrnCallee, + new RefEdge( rsnCallee, + hrnCallee, + reCaller.getType(), + reCaller.getField(), + true, // isInitialParam + reCaller.getBeta() + ) + ); + callerEdgesCopiedToCallee.add( reCaller ); + } + + // keep traversing nodes reachable from param i + // that we haven't visited yet + if( !visitedInCaller.contains( hrnCaller ) ) { + toVisitInCaller.add( hrnCaller ); + } + + } // end edge iteration + } // end visiting heap nodes in caller + } // end iterating over parameters as starting points + + // Now take the callee view graph we've built from the + // caller and look backwards: for every node in the callee + // look back in the caller for "upstream" reference edges. + // We need to add special elements to the callee view that + // capture relevant effects for mapping back + try { + rg.writeGraph( "calleeview", true, true, true, false, true, true ); + } catch( IOException e ) {} + + if( fc.getMethod().getSymbol().equals( "f1" ) ) { + System.exit( 0 ); + } + + return rg; + } + /* public Set findCommonReachableNodes( HeapRegionNode hrn1, diff --git a/Robust/src/Analysis/Disjoint/RefSrcNode.java b/Robust/src/Analysis/Disjoint/RefSrcNode.java index 3db99187..304ac127 100644 --- a/Robust/src/Analysis/Disjoint/RefSrcNode.java +++ b/Robust/src/Analysis/Disjoint/RefSrcNode.java @@ -37,17 +37,19 @@ public abstract class RefSrcNode { referencees.remove( edge ); } - public RefEdge getReferenceTo(HeapRegionNode hrn, - TypeDescriptor type, - String field) { + public RefEdge getReferenceTo( HeapRegionNode hrn, + TypeDescriptor type, + String field + ) { assert hrn != null; Iterator itrEdge = referencees.iterator(); while( itrEdge.hasNext() ) { RefEdge edge = itrEdge.next(); - if( edge.getDst().equals(hrn) && - edge.typeEquals( type ) && - edge.fieldEquals( field ) ) { + if( edge.getDst().equals( hrn ) && + edge.typeEquals( type ) && + edge.fieldEquals( field ) + ) { return edge; } } diff --git a/Robust/src/Tests/disjoint/simple/test.java b/Robust/src/Tests/disjoint/simple/test.java index df62d233..4a89947a 100644 --- a/Robust/src/Tests/disjoint/simple/test.java +++ b/Robust/src/Tests/disjoint/simple/test.java @@ -1,8 +1,15 @@ +public class Foo { + public Foo() {} + public Foo f; +} + public class Test { static public void main( String[] args ) { - f1(); + Foo a = new Foo(); + a.f = new Foo(); + f1( a ); } - static public void f1() { + static public void f1( Foo b ) { } } -- 2.34.1