From c7da5b2f6fdd4fb51e82721d1a71d739265bba37 Mon Sep 17 00:00:00 2001 From: jjenista Date: Thu, 31 Dec 2009 19:33:24 +0000 Subject: [PATCH] more implementation --- .../Analysis/Disjoint/DisjointAnalysis.java | 155 ++++++++++++++++-- Robust/src/Analysis/Disjoint/ReachGraph.java | 33 +++- 2 files changed, 169 insertions(+), 19 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index c6750d08..40a3919a 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -47,7 +47,26 @@ public class DisjointAnalysis { // the set of task and/or method descriptors // reachable in call graph - protected Set descriptorsToAnalyze; + protected Set + descriptorsToAnalyze; + + // current descriptors to visit in fixed-point + // interprocedural analysis, prioritized by + // dependency in the call graph + protected PriorityQueue + descriptorsToVisitQ; + + // a duplication of the above structure, but + // for efficient testing of inclusion + protected HashSet + descriptorsToVisitSet; + + // storage for priorities (doesn't make sense) + // to add it to the Descriptor class, just in + // this analysis + protected Hashtable + mapDescriptorToPriority; + // maps a descriptor to its current partial result // from the intraprocedural fixed-point analysis-- @@ -74,6 +93,14 @@ public class DisjointAnalysis { protected Hashtable mapHrnIdToAllocSite; + // maps a method to its initial heap model (IHM) that + // is the set of reachability graphs from every caller + // site, all merged together. The reason that we keep + // them separate is that any one call site's contribution + // to the IHM may changed along the path to the fixed point + protected Hashtable< Descriptor, Hashtable< FlatCall, ReachGraph > > + mapDescriptorToIHMcontributions; + // TODO -- CHANGE EDGE/TYPE/FIELD storage! public static final String arrayElementFieldName = "___element_"; static protected Hashtable @@ -107,11 +134,23 @@ public class DisjointAnalysis { mapFlatNewToAllocSite = new Hashtable(); + mapDescriptorToIHMcontributions = + new Hashtable< Descriptor, Hashtable< FlatCall, ReachGraph > >(); + mapHrnIdToAllocSite = new Hashtable(); mapTypeToArrayField = new Hashtable (); + + descriptorsToVisitQ = + new PriorityQueue(); + + descriptorsToVisitSet = + new HashSet(); + + mapDescriptorToPriority = + new Hashtable(); } @@ -217,15 +256,6 @@ public class DisjointAnalysis { // add sorted descriptors to priority queue, and duplicate // the queue as a set for efficiently testing whether some // method is marked for analysis - PriorityQueue descriptorsToVisitQ - = new PriorityQueue(); - - HashSet descriptorsToVisitSet - = new HashSet(); - - Hashtable mapDescriptorToPriority - = new Hashtable(); - int p = 0; Iterator dItr = sortedDescriptors.iterator(); while( dItr.hasNext() ) { @@ -390,9 +420,38 @@ public class DisjointAnalysis { // to apply to the reachability graph switch( fn.kind() ) { - case FKind.FlatMethod: - FlatMethod fm = (FlatMethod) fn; - break; + case FKind.FlatMethod: { + // construct this method's initial heap model (IHM) + // since we're working on the FlatMethod, we know + // the incoming ReachGraph 'rg' is empty + + Hashtable heapsFromCallers = + getIHMcontributions( d ); + + Set entrySet = heapsFromCallers.entrySet(); + Iterator itr = entrySet.iterator(); + while( itr.hasNext() ) { + Map.Entry me = (Map.Entry) itr.next(); + FlatCall fc = (FlatCall) me.getKey(); + ReachGraph rgContrib = (ReachGraph) me.getValue(); + + assert fc.getMethod().equals( d ); + + // some call sites are in same method context though, + // and all of them should be merged together first, + // then heaps from different contexts should be merged + // THIS ASSUMES DIFFERENT CONTEXTS NEED SPECIAL CONSIDERATION! + // such as, do allocation sites need to be aged? + + rg.merge_diffMethodContext( rgContrib ); + } + + FlatMethod fm = (FlatMethod) fn; + for( int i = 0; i < fm.numParameters(); ++i ) { + TempDescriptor tdParam = fm.getParameter( i ); + //assert rg.hasVariable( tdParam ); + } + } break; case FKind.FlatOpNode: FlatOpNode fon = (FlatOpNode) fn; @@ -481,11 +540,36 @@ public class DisjointAnalysis { } break; - case FKind.FlatCall: + case FKind.FlatCall: { + FlatCall fc = (FlatCall) fn; + MethodDescriptor mdCallee = fc.getMethod(); + FlatMethod fmCallee = state.getMethodFlat( mdCallee ); + + ReachGraph heapForThisCall_old = + getIHMcontribution( mdCallee, fc ); + + ReachGraph heapForThisCall_cur = rg.makeCalleeView( fc ); + + if( !heapForThisCall_cur.equals( heapForThisCall_old ) ) { + // if heap at call site changed, update the contribution, + // and reschedule the callee for analysis + addIHMcontribution( mdCallee, fc, heapForThisCall_cur ); + + if( !descriptorsToVisitSet.contains( mdCallee ) ) { + Integer priority = mapDescriptorToPriority.get( mdCallee ); + descriptorsToVisitQ.add( new DescriptorQWrapper( priority, + mdCallee ) + ); + descriptorsToVisitSet.add( mdCallee ); + } + } + + // now that we've got that taken care of, go ahead and update + // the reach graph for this FlatCall node by whatever callee + // result we do have + + /* - FlatCall fc = (FlatCall) fn; - MethodDescriptor md = fc.getMethod(); - FlatMethod flatm = state.getMethodFlat(md); ReachGraph ogMergeOfAllPossibleCalleeResults = new ReachGraph(); if( md.isStatic() ) { @@ -576,7 +660,7 @@ public class DisjointAnalysis { og = ogMergeOfAllPossibleCalleeResults; */ - break; + } break; case FKind.FlatReturnNode: @@ -1096,5 +1180,40 @@ public class DisjointAnalysis { return deps; } + + public Hashtable getIHMcontributions( Descriptor d ) { + + Hashtable heapsFromCallers = + mapDescriptorToIHMcontributions.get( d ); + + if( heapsFromCallers == null ) { + heapsFromCallers = new Hashtable(); + } + + return heapsFromCallers; + } + + public ReachGraph getIHMcontribution( Descriptor d, + FlatCall fc + ) { + Hashtable heapsFromCallers = + getIHMcontributions( d ); + + if( !heapsFromCallers.containsKey( fc ) ) { + heapsFromCallers.put( fc, new ReachGraph() ); + } + + return heapsFromCallers.get( fc ); + } + + public void addIHMcontribution( Descriptor d, + FlatCall fc, + ReachGraph rg + ) { + Hashtable heapsFromCallers = + getIHMcontributions( d ); + + heapsFromCallers.put( fc, rg ); + } } diff --git a/Robust/src/Analysis/Disjoint/ReachGraph.java b/Robust/src/Analysis/Disjoint/ReachGraph.java index 6c6c5fdc..7cd6adde 100644 --- a/Robust/src/Analysis/Disjoint/ReachGraph.java +++ b/Robust/src/Analysis/Disjoint/ReachGraph.java @@ -61,6 +61,10 @@ public class ReachGraph { return td2vn.get( td ); } + public boolean hasVariable( TempDescriptor td ) { + return td2vn.containsKey( td ); + } + // the reason for this method is to have the option // of creating new heap regions with specific IDs, or @@ -2879,6 +2883,23 @@ public class ReachGraph { + //////////////////////////////////////////////////// + // high-level merge operations + //////////////////////////////////////////////////// + public void merge_sameMethodContext( ReachGraph rg ) { + // when merging two graphs that abstract the heap + // of the same method context, we just call the + // basic merge operation + merge( rg ); + } + + public void merge_diffMethodContext( ReachGraph rg ) { + // when merging graphs for abstract heaps in + // different method contexts we should: + // 1) age the allocation sites? + merge( rg ); + } + //////////////////////////////////////////////////// // in merge() and equals() methods the suffix A // represents the passed in graph and the suffix @@ -2887,7 +2908,7 @@ public class ReachGraph { // merge it into B, so after the operation graph B // is the final result. //////////////////////////////////////////////////// - public void merge( ReachGraph rg ) { + protected void merge( ReachGraph rg ) { if( rg == null ) { return; @@ -3303,6 +3324,16 @@ 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(); + + return calleeView; + } + + /* public Set findCommonReachableNodes( HeapRegionNode hrn1, HeapRegionNode hrn2 ) { -- 2.34.1