From f62fd7a4d334ffd30e154b40d4b4937ad3c21bc4 Mon Sep 17 00:00:00 2001 From: jjenista Date: Wed, 24 Mar 2010 17:03:02 +0000 Subject: [PATCH] bug fixes, display improvements, sharing query changes, still losing preds during call site transfer func... --- .../Analysis/Disjoint/DisjointAnalysis.java | 101 ++-- Robust/src/Analysis/Disjoint/ExistPred.java | 10 +- Robust/src/Analysis/Disjoint/ReachGraph.java | 534 ++++++++++-------- Robust/src/Benchmarks/disjoint/makefile | 2 + 4 files changed, 367 insertions(+), 280 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index 87df1db5..253cd78c 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -35,7 +35,7 @@ public class DisjointAnalysis { return mapHrnIdToAllocSite.get(id); } - public Set createsPotentialAliases(Descriptor taskOrMethod, + public Set hasPotentialSharing(Descriptor taskOrMethod, int paramIndex1, int paramIndex2) { checkAnalysisComplete(); @@ -45,7 +45,7 @@ public class DisjointAnalysis { return rg.mayReachSharedObjects(fm, paramIndex1, paramIndex2); } - public Set createsPotentialAliases(Descriptor taskOrMethod, + public Set hasPotentialSharing(Descriptor taskOrMethod, int paramIndex, AllocSite alloc) { checkAnalysisComplete(); ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod); @@ -54,7 +54,7 @@ public class DisjointAnalysis { return rg.mayReachSharedObjects(fm, paramIndex, alloc); } - public Set createsPotentialAliases(Descriptor taskOrMethod, + public Set hasPotentialSharing(Descriptor taskOrMethod, AllocSite alloc, int paramIndex) { checkAnalysisComplete(); ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod); @@ -63,7 +63,7 @@ public class DisjointAnalysis { return rg.mayReachSharedObjects(fm, paramIndex, alloc); } - public Set createsPotentialAliases(Descriptor taskOrMethod, + public Set hasPotentialSharing(Descriptor taskOrMethod, AllocSite alloc1, AllocSite alloc2) { checkAnalysisComplete(); ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod); @@ -136,10 +136,24 @@ public class DisjointAnalysis { FlatMethod fm = state.getMethodFlat(td); for (int i = 0; i < fm.numParameters(); ++i) { + // skip parameters with types that cannot reference + // into the heap + if( !shouldAnalysisTrack( fm.getParameter( i ).getType() ) ) { + continue; + } + // for the ith parameter check for aliases to all // higher numbered parameters for (int j = i + 1; j < fm.numParameters(); ++j) { - common = createsPotentialAliases(td, i, j); + + // skip parameters with types that cannot reference + // into the heap + if( !shouldAnalysisTrack( fm.getParameter( j ).getType() ) ) { + continue; + } + + + common = hasPotentialSharing(td, i, j); if (!common.isEmpty()) { foundSomeAlias = true; if (!tabularOutput) { @@ -158,7 +172,7 @@ public class DisjointAnalysis { Iterator allocItr = allocSites.iterator(); while (allocItr.hasNext()) { AllocSite as = (AllocSite) allocItr.next(); - common = createsPotentialAliases(td, i, as); + common = hasPotentialSharing(td, i, as); if (!common.isEmpty()) { foundSomeAlias = true; if (!tabularOutput) { @@ -185,7 +199,7 @@ public class DisjointAnalysis { AllocSite as2 = (AllocSite) allocItr2.next(); if (!outerChecked.contains(as2)) { - common = createsPotentialAliases(td, as1, as2); + common = hasPotentialSharing(td, as1, as2); if (!common.isEmpty()) { foundSomeAlias = true; @@ -260,7 +274,7 @@ public class DisjointAnalysis { AllocSite as2 = (AllocSite) allocItr2.next(); if (!outerChecked.contains(as2)) { - Set common = createsPotentialAliases(d, + Set common = hasPotentialSharing(d, as1, as2); if (!common.isEmpty()) { @@ -1035,14 +1049,12 @@ public class DisjointAnalysis { Descriptor d = (Descriptor) me.getKey(); ReachGraph rg = (ReachGraph) me.getValue(); - try { - rg.writeGraph( "COMPLETE"+d, - true, // write labels (variables) - true, // selectively hide intermediate temp vars - true, // prune unreachable heap regions - false, // hide subset reachability states - true ); // hide edge taints - } catch( IOException e ) {} + rg.writeGraph( "COMPLETE"+d, + true, // write labels (variables) + true, // selectively hide intermediate temp vars + true, // prune unreachable heap regions + false, // hide subset reachability states + true ); // hide edge taints } } @@ -1059,14 +1071,12 @@ public class DisjointAnalysis { FlatCall fc = (FlatCall) me2.getKey(); ReachGraph rg = (ReachGraph) me2.getValue(); - try { - rg.writeGraph( "IHMPARTFOR"+d+"FROM"+fc, - true, // write labels (variables) - false, // selectively hide intermediate temp vars - false, // prune unreachable heap regions - false, // hide subset reachability states - true ); // hide edge taints - } catch( IOException e ) {} + rg.writeGraph( "IHMPARTFOR"+d+"FROM"+fc, + true, // write labels (variables) + false, // selectively hide intermediate temp vars + false, // prune unreachable heap regions + false, // hide subset reachability states + true ); // hide edge taints } } } @@ -1090,14 +1100,12 @@ public class DisjointAnalysis { } Integer n = mapDescriptorToNumUpdates.get( d ); - try { - rg.writeGraph( d+"COMPLETE"+String.format( "%05d", n ), - true, // write labels (variables) - true, // selectively hide intermediate temp vars - true, // prune unreachable heap regions - false, // hide subset reachability states - true ); // hide edge taints - } catch( IOException e ) {} + rg.writeGraph( d+"COMPLETE"+String.format( "%05d", n ), + true, // write labels (variables) + true, // selectively hide intermediate temp vars + true, // prune unreachable heap regions + false, // hide subset reachability states + true ); // hide edge taints mapDescriptorToNumUpdates.put( d, n + 1 ); } @@ -1826,9 +1834,9 @@ getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) { // get successive captures of the analysis state - boolean takeDebugSnapshots = false; - String descSymbolDebug = "MDRunner"; - boolean stopAfterCapture = true; + boolean takeDebugSnapshots = true; + String descSymbolDebug = "calcGoodFeature"; + boolean stopAfterCapture = false; // increments every visit to debugSnapshot, don't fiddle with it int debugCounter = 0; @@ -1838,13 +1846,13 @@ getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) { int numStartCountReport = 0; // the frequency of debugCounter values to print out, 0 no report - int freqCountReport = 50; + int freqCountReport = 0; // the debugCounter value at which to start taking snapshots - int iterStartCapture = 350; + int iterStartCapture = 0; // the number of snapshots to take - int numIterToCapture = 400; + int numIterToCapture = 4000; void debugSnapshot( ReachGraph rg, FlatNode fn, boolean in ) { @@ -1880,17 +1888,12 @@ getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) { if( fn != null ) { graphName = graphName + fn; } - try { - rg.writeGraph( graphName, - true, // write labels (variables) - true, // selectively hide intermediate temp vars - true, // prune unreachable heap regions - false, // hide subset reachability states - true );// hide edge taints - } catch( Exception e ) { - System.out.println( "Error writing debug capture." ); - System.exit( 0 ); - } + rg.writeGraph( graphName, + true, // write labels (variables) + true, // selectively hide intermediate temp vars + true, // prune unreachable heap regions + false, // hide subset reachability states + true );// hide edge taints } if( debugCounter == iterStartCapture + numIterToCapture && diff --git a/Robust/src/Analysis/Disjoint/ExistPred.java b/Robust/src/Analysis/Disjoint/ExistPred.java index 749b98f7..817db240 100644 --- a/Robust/src/Analysis/Disjoint/ExistPred.java +++ b/Robust/src/Analysis/Disjoint/ExistPred.java @@ -71,9 +71,14 @@ public class ExistPred extends Canonical { // a reference has a field name and type protected TypeDescriptor e_type; - protected String e_field; + protected String e_field; // edge uses same ReachState ne_state as node type above + + + // a static debug flag for higher abstraction code + // to enable debug info at this level + public static boolean debug = false; // to make the true predicate @@ -182,12 +187,12 @@ public class ExistPred extends Canonical { public ExistPredSet isSatisfiedBy( ReachGraph rg, Set calleeReachableNodes ) { - if( predType == TYPE_TRUE ) { return ExistPredSet.factory( ExistPred.factory() ); } if( predType == TYPE_NODE ) { + // first find node HeapRegionNode hrn = rg.id2hrn.get( n_hrnID ); if( hrn == null ) { @@ -215,6 +220,7 @@ public class ExistPred extends Canonical { } if( predType == TYPE_EDGE ) { + // first establish whether the source of the // reference edge exists VariableNode vnSrc = null; diff --git a/Robust/src/Analysis/Disjoint/ReachGraph.java b/Robust/src/Analysis/Disjoint/ReachGraph.java index 3560467a..e2661459 100644 --- a/Robust/src/Analysis/Disjoint/ReachGraph.java +++ b/Robust/src/Analysis/Disjoint/ReachGraph.java @@ -1873,7 +1873,7 @@ public class ReachGraph { ); oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(), - reCaller.getPreds() + preds ) ); @@ -1893,14 +1893,12 @@ public class ReachGraph { if( writeDebugDOTs ) { - try { - rg.writeGraph( "calleeview", - resolveMethodDebugDOTwriteLabels, - resolveMethodDebugDOTselectTemps, - resolveMethodDebugDOTpruneGarbage, - resolveMethodDebugDOThideSubsetReach, - resolveMethodDebugDOThideEdgeTaints ); - } catch( IOException e ) {} + rg.writeGraph( "calleeview", + resolveMethodDebugDOTwriteLabels, + resolveMethodDebugDOTselectTemps, + resolveMethodDebugDOTpruneGarbage, + resolveMethodDebugDOThideSubsetReach, + resolveMethodDebugDOThideEdgeTaints ); } return rg; @@ -1927,24 +1925,21 @@ public class ReachGraph { boolean writeDebugDOTs ) { - if( writeDebugDOTs ) { - try { - rgCallee.writeGraph( "callee", - resolveMethodDebugDOTwriteLabels, - resolveMethodDebugDOTselectTemps, - resolveMethodDebugDOTpruneGarbage, - resolveMethodDebugDOThideSubsetReach, - resolveMethodDebugDOThideEdgeTaints ); - - writeGraph( "caller00In", - resolveMethodDebugDOTwriteLabels, - resolveMethodDebugDOTselectTemps, - resolveMethodDebugDOTpruneGarbage, - resolveMethodDebugDOThideSubsetReach, - resolveMethodDebugDOThideEdgeTaints, - callerNodeIDsCopiedToCallee ); - } catch( IOException e ) {} + rgCallee.writeGraph( "callee", + resolveMethodDebugDOTwriteLabels, + resolveMethodDebugDOTselectTemps, + resolveMethodDebugDOTpruneGarbage, + resolveMethodDebugDOThideSubsetReach, + resolveMethodDebugDOThideEdgeTaints ); + + writeGraph( "caller00In", + resolveMethodDebugDOTwriteLabels, + resolveMethodDebugDOTselectTemps, + resolveMethodDebugDOTpruneGarbage, + resolveMethodDebugDOThideSubsetReach, + resolveMethodDebugDOThideEdgeTaints, + callerNodeIDsCopiedToCallee ); } @@ -1961,7 +1956,6 @@ public class ReachGraph { // 5. Global sweep it. - // 1. mark what callee elements have satisfied predicates Hashtable calleeNodesSatisfied = new Hashtable(); @@ -1989,6 +1983,7 @@ public class ReachGraph { hrnCallee.getPreds().isSatisfiedBy( this, callerNodeIDsCopiedToCallee ); + if( predsIfSatis != null ) { calleeNodesSatisfied.put( hrnCallee, predsIfSatis ); } else { @@ -2044,7 +2039,7 @@ public class ReachGraph { HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() ); if( hrnDstCaller == null ) { continue; - } + } Iterator reDstItr = hrnDstCaller.iteratorToReferencers(); while( reDstItr.hasNext() ) { @@ -2059,6 +2054,7 @@ public class ReachGraph { RefSrcNode rsnCaller = reCaller.getSrc(); if( rsnCaller instanceof VariableNode ) { + // a variable node matches an OOC region with null type if( hrnSrcCallee.getType() != null ) { continue; @@ -2096,6 +2092,7 @@ public class ReachGraph { reCallee.getPreds().isSatisfiedBy( this, callerNodeIDsCopiedToCallee ); + if( predsIfSatis != null ) { calleeEdgesSatisfied.put( reCallee, predsIfSatis ); @@ -2172,14 +2169,12 @@ public class ReachGraph { if( writeDebugDOTs ) { - try { - writeGraph( "caller20BeforeWipe", - resolveMethodDebugDOTwriteLabels, - resolveMethodDebugDOTselectTemps, - resolveMethodDebugDOTpruneGarbage, - resolveMethodDebugDOThideSubsetReach, - resolveMethodDebugDOThideEdgeTaints ); - } catch( IOException e ) {} + writeGraph( "caller20BeforeWipe", + resolveMethodDebugDOTwriteLabels, + resolveMethodDebugDOTselectTemps, + resolveMethodDebugDOTpruneGarbage, + resolveMethodDebugDOThideSubsetReach, + resolveMethodDebugDOThideEdgeTaints ); } @@ -2198,14 +2193,12 @@ public class ReachGraph { if( writeDebugDOTs ) { - try { - writeGraph( "caller30BeforeAddingNodes", - resolveMethodDebugDOTwriteLabels, - resolveMethodDebugDOTselectTemps, - resolveMethodDebugDOTpruneGarbage, - resolveMethodDebugDOThideSubsetReach, - resolveMethodDebugDOThideEdgeTaints ); - } catch( IOException e ) {} + writeGraph( "caller30BeforeAddingNodes", + resolveMethodDebugDOTwriteLabels, + resolveMethodDebugDOTselectTemps, + resolveMethodDebugDOTpruneGarbage, + resolveMethodDebugDOThideSubsetReach, + resolveMethodDebugDOThideEdgeTaints ); } @@ -2267,14 +2260,12 @@ public class ReachGraph { if( writeDebugDOTs ) { - try { - writeGraph( "caller31BeforeAddingEdges", - resolveMethodDebugDOTwriteLabels, - resolveMethodDebugDOTselectTemps, - resolveMethodDebugDOTpruneGarbage, - resolveMethodDebugDOThideSubsetReach, - resolveMethodDebugDOThideEdgeTaints ); - } catch( IOException e ) {} + writeGraph( "caller31BeforeAddingEdges", + resolveMethodDebugDOTwriteLabels, + resolveMethodDebugDOTselectTemps, + resolveMethodDebugDOTpruneGarbage, + resolveMethodDebugDOThideSubsetReach, + resolveMethodDebugDOThideEdgeTaints ); } @@ -2314,7 +2305,6 @@ public class ReachGraph { Set oocCallers = calleeEdges2oocCallerSrcMatches.get( reCallee ); - boolean oocEdges = false; if( oocCallers == null ) { // there are no out-of-context matches, so it's @@ -2332,8 +2322,8 @@ public class ReachGraph { // shouldn't this NEVER HAPPEN? assert false; } + rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) ); - oocEdges = true; } else { // otherwise source is in context, one region @@ -2375,7 +2365,6 @@ public class ReachGraph { // that should NOT be translated to shadow nodes assert !oocCallers.isEmpty(); rsnCallers.addAll( oocCallers ); - oocEdges = true; } // now make all caller edges we've identified from @@ -2471,14 +2460,12 @@ public class ReachGraph { if( writeDebugDOTs ) { - try { - writeGraph( "caller35BeforeAssignReturnValue", - resolveMethodDebugDOTwriteLabels, - resolveMethodDebugDOTselectTemps, - resolveMethodDebugDOTpruneGarbage, - resolveMethodDebugDOThideSubsetReach, - resolveMethodDebugDOThideEdgeTaints ); - } catch( IOException e ) {} + writeGraph( "caller35BeforeAssignReturnValue", + resolveMethodDebugDOTwriteLabels, + resolveMethodDebugDOTselectTemps, + resolveMethodDebugDOTpruneGarbage, + resolveMethodDebugDOThideSubsetReach, + resolveMethodDebugDOThideEdgeTaints ); } @@ -2557,14 +2544,12 @@ public class ReachGraph { if( writeDebugDOTs ) { - try { - writeGraph( "caller38propagateReach", - resolveMethodDebugDOTwriteLabels, - resolveMethodDebugDOTselectTemps, - resolveMethodDebugDOTpruneGarbage, - resolveMethodDebugDOThideSubsetReach, - resolveMethodDebugDOThideEdgeTaints ); - } catch( IOException e ) {} + writeGraph( "caller38propagateReach", + resolveMethodDebugDOTwriteLabels, + resolveMethodDebugDOTselectTemps, + resolveMethodDebugDOTpruneGarbage, + resolveMethodDebugDOThideSubsetReach, + resolveMethodDebugDOThideEdgeTaints ); } // propagate callee reachability changes to the rest @@ -2587,14 +2572,12 @@ public class ReachGraph { if( writeDebugDOTs ) { - try { - writeGraph( "caller40BeforeShadowMerge", - resolveMethodDebugDOTwriteLabels, - resolveMethodDebugDOTselectTemps, - resolveMethodDebugDOTpruneGarbage, - resolveMethodDebugDOThideSubsetReach, - resolveMethodDebugDOThideEdgeTaints ); - } catch( IOException e ) {} + writeGraph( "caller40BeforeShadowMerge", + resolveMethodDebugDOTwriteLabels, + resolveMethodDebugDOTselectTemps, + resolveMethodDebugDOTpruneGarbage, + resolveMethodDebugDOThideSubsetReach, + resolveMethodDebugDOThideEdgeTaints ); } @@ -2688,14 +2671,12 @@ public class ReachGraph { if( writeDebugDOTs ) { - try { - writeGraph( "caller45BeforeUnshadow", - resolveMethodDebugDOTwriteLabels, - resolveMethodDebugDOTselectTemps, - resolveMethodDebugDOTpruneGarbage, - resolveMethodDebugDOThideSubsetReach, - resolveMethodDebugDOThideEdgeTaints ); - } catch( IOException e ) {} + writeGraph( "caller45BeforeUnshadow", + resolveMethodDebugDOTwriteLabels, + resolveMethodDebugDOTselectTemps, + resolveMethodDebugDOTpruneGarbage, + resolveMethodDebugDOThideSubsetReach, + resolveMethodDebugDOThideEdgeTaints ); } @@ -2716,14 +2697,12 @@ public class ReachGraph { if( writeDebugDOTs ) { - try { - writeGraph( "caller50BeforeGlobalSweep", - resolveMethodDebugDOTwriteLabels, - resolveMethodDebugDOTselectTemps, - resolveMethodDebugDOTpruneGarbage, - resolveMethodDebugDOThideSubsetReach, - resolveMethodDebugDOThideEdgeTaints ); - } catch( IOException e ) {} + writeGraph( "caller50BeforeGlobalSweep", + resolveMethodDebugDOTwriteLabels, + resolveMethodDebugDOTselectTemps, + resolveMethodDebugDOTpruneGarbage, + resolveMethodDebugDOThideSubsetReach, + resolveMethodDebugDOThideEdgeTaints ); } @@ -2735,14 +2714,12 @@ public class ReachGraph { if( writeDebugDOTs ) { - try { - writeGraph( "caller90AfterTransfer", - resolveMethodDebugDOTwriteLabels, - resolveMethodDebugDOTselectTemps, - resolveMethodDebugDOTpruneGarbage, - resolveMethodDebugDOThideSubsetReach, - resolveMethodDebugDOThideEdgeTaints ); - } catch( IOException e ) {} + writeGraph( "caller90AfterTransfer", + resolveMethodDebugDOTwriteLabels, + resolveMethodDebugDOTselectTemps, + resolveMethodDebugDOTpruneGarbage, + resolveMethodDebugDOThideSubsetReach, + resolveMethodDebugDOThideEdgeTaints ); } } @@ -3107,9 +3084,7 @@ public class ReachGraph { if( !id2hrn.containsKey( rtOld.getHrnID() ) ) { System.out.println( "\nLooking for "+rtOld ); - try { - writeGraph( "dbgz", true, true, true, true, true ); - } catch( IOException e ) {} + writeGraph( "dbgz" ); } @@ -3864,13 +3839,25 @@ public class ReachGraph { + // the default signature for quick-and-dirty debugging + public void writeGraph( String graphName ) { + writeGraph( graphName, + true, // write labels + true, // label select + true, // prune garbage + true, // hide subset reachability + true, // hide edge taints + null // in-context boundary + ); + } + public void writeGraph( String graphName, boolean writeLabels, boolean labelSelect, boolean pruneGarbage, boolean hideSubsetReachability, boolean hideEdgeTaints - ) throws java.io.IOException { + ) { writeGraph( graphName, writeLabels, labelSelect, @@ -3887,94 +3874,57 @@ public class ReachGraph { boolean hideSubsetReachability, boolean hideEdgeTaints, Set callerNodeIDsCopiedToCallee - ) throws java.io.IOException { + ) { - // remove all non-word characters from the graph name so - // the filename and identifier in dot don't cause errors - graphName = graphName.replaceAll( "[\\W]", "" ); - - BufferedWriter bw = - new BufferedWriter( new FileWriter( graphName+".dot" ) ); - - bw.write( "digraph "+graphName+" {\n" ); + try { + // remove all non-word characters from the graph name so + // the filename and identifier in dot don't cause errors + graphName = graphName.replaceAll( "[\\W]", "" ); + BufferedWriter bw = + new BufferedWriter( new FileWriter( graphName+".dot" ) ); - // this is an optional step to form the callee-reachable - // "cut-out" into a DOT cluster for visualization - if( callerNodeIDsCopiedToCallee != null ) { + bw.write( "digraph "+graphName+" {\n" ); - bw.write( " subgraph cluster0 {\n" ); - bw.write( " color=blue;\n" ); - - Iterator i = id2hrn.entrySet().iterator(); - while( i.hasNext() ) { - Map.Entry me = (Map.Entry) i.next(); - HeapRegionNode hrn = (HeapRegionNode) me.getValue(); + + // this is an optional step to form the callee-reachable + // "cut-out" into a DOT cluster for visualization + if( callerNodeIDsCopiedToCallee != null ) { - if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) { - bw.write( " "+hrn.toString()+ - hrn.toStringDOT( hideSubsetReachability )+ - ";\n" ); + bw.write( " subgraph cluster0 {\n" ); + bw.write( " color=blue;\n" ); + + Iterator i = id2hrn.entrySet().iterator(); + while( i.hasNext() ) { + Map.Entry me = (Map.Entry) i.next(); + HeapRegionNode hrn = (HeapRegionNode) me.getValue(); + if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) { + bw.write( " "+hrn.toString()+ + hrn.toStringDOT( hideSubsetReachability )+ + ";\n" ); + + } } + + bw.write( " }\n" ); } - - bw.write( " }\n" ); - } - - - Set visited = new HashSet(); - - // then visit every heap region node - Iterator i = id2hrn.entrySet().iterator(); - while( i.hasNext() ) { - Map.Entry me = (Map.Entry) i.next(); - HeapRegionNode hrn = (HeapRegionNode) me.getValue(); - - // only visit nodes worth writing out--for instance - // not every node at an allocation is referenced - // (think of it as garbage-collected), etc. - if( !pruneGarbage || - hrn.isOutOfContext() - ) { - - if( !visited.contains( hrn ) ) { - traverseHeapRegionNodes( hrn, - bw, - null, - visited, - hideSubsetReachability, - hideEdgeTaints, - callerNodeIDsCopiedToCallee ); - } - } - } - - bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" ); - - - // then visit every label node, useful for debugging - if( writeLabels ) { - i = td2vn.entrySet().iterator(); + + + Set visited = new HashSet(); + + // then visit every heap region node + Iterator i = id2hrn.entrySet().iterator(); while( i.hasNext() ) { - Map.Entry me = (Map.Entry) i.next(); - VariableNode vn = (VariableNode) me.getValue(); - - if( labelSelect ) { - String labelStr = vn.getTempDescriptorString(); - if( labelStr.startsWith( "___temp" ) || - labelStr.startsWith( "___dst" ) || - labelStr.startsWith( "___srctmp" ) || - labelStr.startsWith( "___neverused" ) - ) { - continue; - } - } + Map.Entry me = (Map.Entry) i.next(); + HeapRegionNode hrn = (HeapRegionNode) me.getValue(); - Iterator heapRegionsItr = vn.iteratorToReferencees(); - while( heapRegionsItr.hasNext() ) { - RefEdge edge = heapRegionsItr.next(); - HeapRegionNode hrn = edge.getDst(); + // only visit nodes worth writing out--for instance + // not every node at an allocation is referenced + // (think of it as garbage-collected), etc. + if( !pruneGarbage || + hrn.isOutOfContext() + ) { if( !visited.contains( hrn ) ) { traverseHeapRegionNodes( hrn, @@ -3985,17 +3935,59 @@ public class ReachGraph { hideEdgeTaints, callerNodeIDsCopiedToCallee ); } + } + } + + bw.write( " graphTitle[label=\""+graphName+"\",shape=box];\n" ); + + + // then visit every label node, useful for debugging + if( writeLabels ) { + i = td2vn.entrySet().iterator(); + while( i.hasNext() ) { + Map.Entry me = (Map.Entry) i.next(); + VariableNode vn = (VariableNode) me.getValue(); - bw.write( " "+vn.toString()+ - " -> "+hrn.toString()+ - edge.toStringDOT( hideSubsetReachability, "" )+ - ";\n" ); + if( labelSelect ) { + String labelStr = vn.getTempDescriptorString(); + if( labelStr.startsWith( "___temp" ) || + labelStr.startsWith( "___dst" ) || + labelStr.startsWith( "___srctmp" ) || + labelStr.startsWith( "___neverused" ) + ) { + continue; + } + } + + Iterator heapRegionsItr = vn.iteratorToReferencees(); + while( heapRegionsItr.hasNext() ) { + RefEdge edge = heapRegionsItr.next(); + HeapRegionNode hrn = edge.getDst(); + + if( !visited.contains( hrn ) ) { + traverseHeapRegionNodes( hrn, + bw, + null, + visited, + hideSubsetReachability, + hideEdgeTaints, + callerNodeIDsCopiedToCallee ); + } + + bw.write( " "+vn.toString()+ + " -> "+hrn.toString()+ + edge.toStringDOT( hideSubsetReachability, "" )+ + ";\n" ); + } } } - } - bw.write( "}\n" ); - bw.close(); + bw.write( "}\n" ); + bw.close(); + + } catch( IOException e ) { + throw new Error( "Error writing out DOT graph "+graphName ); + } } protected void traverseHeapRegionNodes( HeapRegionNode hrn, @@ -4117,23 +4109,29 @@ public class ReachGraph { ReachTuple.ARITY_ONE, false ); // ooc? - ReachTuple h1star = - ReachTuple.factory( hrn1.getID(), - !hrn1.isSingleObject(), - ReachTuple.ARITY_ZEROORMORE, - false ); + ReachTuple h1star = null; + if( !hrn1.isSingleObject() ) { + h1star = + ReachTuple.factory( hrn1.getID(), + !hrn1.isSingleObject(), + ReachTuple.ARITY_ZEROORMORE, + false ); + } ReachTuple h2 = ReachTuple.factory( hrn2.getID(), !hrn2.isSingleObject(), ReachTuple.ARITY_ONE, false ); - - ReachTuple h2star = - ReachTuple.factory( hrn2.getID(), - !hrn2.isSingleObject(), - ReachTuple.ARITY_ZEROORMORE, - false ); + + ReachTuple h2star = null; + if( !hrn2.isSingleObject() ) { + h2star = + ReachTuple.factory( hrn2.getID(), + !hrn2.isSingleObject(), + ReachTuple.ARITY_ZEROORMORE, + false ); + } // then get the merged beta of all out-going edges from these heap // regions @@ -4158,34 +4156,88 @@ public class ReachGraph { Canonical.unionORpreds( proofOfSharing, beta1.getStatesWithBoth( h1, h2 ) ); - proofOfSharing = - Canonical.unionORpreds( proofOfSharing, - beta1.getStatesWithBoth( h1star, h2 ) - ); - proofOfSharing = - Canonical.unionORpreds( proofOfSharing, - beta1.getStatesWithBoth( h1, h2star ) - ); - proofOfSharing = - Canonical.unionORpreds( proofOfSharing, - beta1.getStatesWithBoth( h1star, h2star ) - ); - proofOfSharing = Canonical.unionORpreds( proofOfSharing, beta2.getStatesWithBoth( h1, h2 ) ); + + if( !hrn1.isSingleObject() ) { + proofOfSharing = + Canonical.unionORpreds( proofOfSharing, + beta1.getStatesWithBoth( h1star, h2 ) + ); + proofOfSharing = + Canonical.unionORpreds( proofOfSharing, + beta2.getStatesWithBoth( h1star, h2 ) + ); + } + + if( !hrn2.isSingleObject() ) { + proofOfSharing = + Canonical.unionORpreds( proofOfSharing, + beta1.getStatesWithBoth( h1, h2star ) + ); + proofOfSharing = + Canonical.unionORpreds( proofOfSharing, + beta2.getStatesWithBoth( h1, h2star ) + ); + } + + if( !hrn1.isSingleObject() && + !hrn2.isSingleObject() + ) { + proofOfSharing = + Canonical.unionORpreds( proofOfSharing, + beta1.getStatesWithBoth( h1star, h2star ) + ); + proofOfSharing = + Canonical.unionORpreds( proofOfSharing, + beta2.getStatesWithBoth( h1star, h2star ) + ); + } + + Set common = new HashSet(); + if( !proofOfSharing.isEmpty() ) { + common = findCommonReachableNodes( proofOfSharing ); + if( !DISABLE_STRONG_UPDATES && + !DISABLE_GLOBAL_SWEEP + ) { + assert !common.isEmpty(); + } + } + + return common; + } + + // this version of the above method checks whether there is sharing + // among the objects in a summary node + public Set mayReachSharedObjects(HeapRegionNode hrn) { + assert hrn != null; + assert hrn.isNewSummary(); + assert !hrn.isOutOfContext(); + assert belongsToThis( hrn ); + + ReachTuple hstar = + ReachTuple.factory( hrn.getID(), + true, // multi + ReachTuple.ARITY_ZEROORMORE, + false ); // ooc + + // then get the merged beta of all out-going edges from + // this heap region + + ReachSet beta = ReachSet.factory(); + Iterator itrEdge = hrn.iteratorToReferencees(); + while (itrEdge.hasNext()) { + RefEdge edge = itrEdge.next(); + beta = Canonical.unionORpreds(beta, edge.getBeta()); + } + + ReachSet proofOfSharing = ReachSet.factory(); + proofOfSharing = Canonical.unionORpreds( proofOfSharing, - beta2.getStatesWithBoth( h1star, h2 ) - ); - proofOfSharing = - Canonical.unionORpreds( proofOfSharing, - beta2.getStatesWithBoth( h1, h2star ) - ); - proofOfSharing = - Canonical.unionORpreds( proofOfSharing, - beta2.getStatesWithBoth( h1star, h2star ) + beta.getStatesWithBoth( hstar, hstar ) ); Set common = new HashSet(); @@ -4197,7 +4249,7 @@ public class ReachGraph { assert !common.isEmpty(); } } - + return common; } @@ -4208,13 +4260,29 @@ public class ReachGraph { // get parameter's heap regions TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue()); + assert this.hasVariable( paramTemp1 ); VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1); + + + if( !(paramVar1.getNumReferencees() == 1) ) { + System.out.println( "\n fm="+fm+"\n param="+paramTemp1 ); + writeGraph( "whatup" ); + } + + assert paramVar1.getNumReferencees() == 1; RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next(); HeapRegionNode hrnParam1 = paramEdge1.getDst(); TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue()); + assert this.hasVariable( paramTemp2 ); VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2); + + if( !(paramVar2.getNumReferencees() == 1) ) { + System.out.println( "\n fm="+fm+"\n param="+paramTemp2 ); + writeGraph( "whatup" ); + } + assert paramVar2.getNumReferencees() == 1; RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next(); HeapRegionNode hrnParam2 = paramEdge2.getDst(); @@ -4231,6 +4299,7 @@ public class ReachGraph { // get parameter's heap regions TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue()); + assert this.hasVariable( paramTemp ); VariableNode paramVar = getVariableNodeFromTemp(paramTemp); assert paramVar.getNumReferencees() == 1; RefEdge paramEdge = paramVar.iteratorToReferencees().next(); @@ -4281,10 +4350,15 @@ public class ReachGraph { } Set common = new HashSet(); - if(hrnSum1!=null && hrnSum2!=null){ + if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2){ common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2)); } + if(hrnSum1!=null){ + // ask if objects from this summary share among each other + common.addAll(mayReachSharedObjects(hrnSum1)); + } + // check sum2 against alloc1 nodes if(hrnSum2!=null){ for (int i = 0; i < as1.getAllocationDepth(); ++i) { @@ -4294,6 +4368,9 @@ public class ReachGraph { assert hrnI1 != null; common.addAll(mayReachSharedObjects(hrnI1, hrnSum2)); } + + // also ask if objects from this summary share among each other + common.addAll(mayReachSharedObjects(hrnSum2)); } // check sum1 against alloc2 nodes @@ -4325,6 +4402,5 @@ public class ReachGraph { } return common; - } - + } } diff --git a/Robust/src/Benchmarks/disjoint/makefile b/Robust/src/Benchmarks/disjoint/makefile index f1964338..8e0d62ae 100644 --- a/Robust/src/Benchmarks/disjoint/makefile +++ b/Robust/src/Benchmarks/disjoint/makefile @@ -1,6 +1,8 @@ BUILDSCRIPT=~/research/Robust/src/buildscript #DEBUGFLAGS= -disjoint-debug-callsite MDRunner t3 100 +DEBUGFLAGS= -disjoint-debug-callsite calcGoodFeature calcGoodFeature 100 + BSFLAGS= -recover -justanalyze -disjoint -disjoint-k 1 -disjoint-write-dots final -disjoint-alias-file aliases.txt normal -enable-assertions -- 2.34.1