From 556b6ddd037f9f879a02a32f0f4c1a0be6df00b1 Mon Sep 17 00:00:00 2001 From: jjenista Date: Mon, 22 Mar 2010 23:02:03 +0000 Subject: [PATCH] fix bug that a hrn ID integer and a boolean out-of-context --identify-- an out-of-context node --- .../Analysis/Disjoint/DisjointAnalysis.java | 17 ++--- .../src/Analysis/Disjoint/HeapRegionNode.java | 24 +++++++ Robust/src/Analysis/Disjoint/HrnIdOoc.java | 61 +++++++++++++++++ Robust/src/Analysis/Disjoint/ReachGraph.java | 65 ++++++++++++------- Robust/src/Benchmarks/disjoint/makefile | 4 +- 5 files changed, 139 insertions(+), 32 deletions(-) create mode 100644 Robust/src/Analysis/Disjoint/HrnIdOoc.java diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index 2c3b4d73..5b8cb1fd 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -1808,7 +1808,7 @@ getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) { // get successive captures of the analysis state boolean takeDebugSnapshots = false; - String descSymbolDebug = "addSomething"; + String descSymbolDebug = "MDRunner"; boolean stopAfterCapture = true; // increments every visit to debugSnapshot, don't fiddle with it @@ -1819,13 +1819,13 @@ getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) { int numStartCountReport = 0; // the frequency of debugCounter values to print out, 0 no report - int freqCountReport = 0; + int freqCountReport = 50; // the debugCounter value at which to start taking snapshots - int iterStartCapture = 25; + int iterStartCapture = 350; // the number of snapshots to take - int numIterToCapture = 300; + int numIterToCapture = 400; void debugSnapshot( ReachGraph rg, FlatNode fn, boolean in ) { @@ -1839,7 +1839,8 @@ getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) { if( debugCounter > numStartCountReport && freqCountReport > 0 && - debugCounter % freqCountReport == 0 + debugCounter % freqCountReport == 0 && + in ) { System.out.println( " @@@ debug counter = "+ debugCounter ); @@ -1847,15 +1848,15 @@ getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) { if( debugCounter > iterStartCapture ) { System.out.println( " @@@ capturing debug "+ - (debugCounter - iterStartCapture)+ + (debugCounter /*- iterStartCapture*/)+ " @@@" ); String graphName; if( in ) { graphName = String.format( "snap%04din", - debugCounter - iterStartCapture ); + debugCounter ); //- iterStartCapture ); } else { graphName = String.format( "snap%04dout", - debugCounter - iterStartCapture ); + debugCounter ); //- iterStartCapture ); } if( fn != null ) { graphName = graphName + fn; diff --git a/Robust/src/Analysis/Disjoint/HeapRegionNode.java b/Robust/src/Analysis/Disjoint/HeapRegionNode.java index 7ca1fdd2..392eefb2 100644 --- a/Robust/src/Analysis/Disjoint/HeapRegionNode.java +++ b/Robust/src/Analysis/Disjoint/HeapRegionNode.java @@ -250,6 +250,30 @@ public class HeapRegionNode extends RefSrcNode { } + // use this method to assert that an out-of-context + // heap region node has only out-of-context symbols + // in its reachability + public boolean reachHasOnlyOOC() { + assert isOutOfContext; + + Iterator stateItr = alpha.iterator(); + while( stateItr.hasNext() ) { + ReachState state = stateItr.next(); + + Iterator rtItr = state.iterator(); + while( rtItr.hasNext() ) { + ReachTuple rt = rtItr.next(); + + if( !rt.isOutOfContext() ) { + return false; + } + } + } + + return true; + } + + public String getIDString() { String s; diff --git a/Robust/src/Analysis/Disjoint/HrnIdOoc.java b/Robust/src/Analysis/Disjoint/HrnIdOoc.java new file mode 100644 index 00000000..92398204 --- /dev/null +++ b/Robust/src/Analysis/Disjoint/HrnIdOoc.java @@ -0,0 +1,61 @@ +package Analysis.Disjoint; + +import IR.*; +import IR.Flat.*; +import java.util.*; +import java.io.*; + +// a heap region node has an integer ID, but heap regions can +// also have reach tuples with the same ID but out-of-context +// so 17 and 17? mean something different in reachability states +public class HrnIdOoc { + protected Integer id; + protected Boolean ooc; + + public HrnIdOoc( Integer id, Boolean ooc ) { + this.id = id; + this.ooc = ooc; + } + + public Integer getId() { + return id; + } + + public Boolean getOoc() { + return ooc; + } + + public boolean equals( Object o ) { + if( o == null ) { + return false; + } + + if( !(o instanceof HrnIdOoc) ) { + return false; + } + + HrnIdOoc hio = (HrnIdOoc) o; + + return + id.equals( hio.id ) && + ooc.equals( hio.ooc ); + } + + public int hashCode() { + int hash = id.intValue(); + if( ooc.booleanValue() ) { + hash = ~hash; + } + return hash; + } + + public String toString() { + String s = id.toString(); + + if( ooc ) { + s += "?"; + } + + return s; + } +} diff --git a/Robust/src/Analysis/Disjoint/ReachGraph.java b/Robust/src/Analysis/Disjoint/ReachGraph.java index acb7e8fd..eaa55704 100644 --- a/Robust/src/Analysis/Disjoint/ReachGraph.java +++ b/Robust/src/Analysis/Disjoint/ReachGraph.java @@ -1291,9 +1291,9 @@ public class ReachGraph { // used below to convert a ReachSet to its callee-context // equivalent with respect to allocation sites in this graph - protected ReachSet toCalleeContext( ReachSet rs, - ExistPredSet preds, - Set oocTuples + protected ReachSet toCalleeContext( ReachSet rs, + ExistPredSet preds, + Set oocHrnIdOoc2callee ) { ReachSet out = ReachSet.factory(); @@ -1314,7 +1314,10 @@ public class ReachGraph { // only translate this tuple if it is // in the out-callee-context bag - if( !oocTuples.contains( rt ) ) { + HrnIdOoc hio = new HrnIdOoc( rt.getHrnID(), + rt.isOutOfContext() + ); + if( !oocHrnIdOoc2callee.contains( hio ) ) { stateNew = Canonical.add( stateNew, rt ); continue; } @@ -1518,9 +1521,10 @@ public class ReachGraph { } // end iterating over parameters as starting points - // now collect out-of-context reach tuples and - // more out-of-context edges - Set oocTuples = new HashSet(); + // now collect out-of-callee-context IDs and + // map them to whether the ID is out of the caller + // context as well + Set oocHrnIdOoc2callee = new HashSet(); Iterator itrInContext = callerNodeIDsCopiedToCallee.iterator(); @@ -1567,13 +1571,15 @@ public class ReachGraph { while( rtItr.hasNext() ) { ReachTuple rt = rtItr.next(); - oocTuples.add( rt ); + oocHrnIdOoc2callee.add( new HrnIdOoc( rt.getHrnID(), + rt.isOutOfContext() + ) + ); } } } } - // the callee view is a new graph: DON'T MODIFY *THIS* graph ReachGraph rg = new ReachGraph(); @@ -1597,11 +1603,11 @@ public class ReachGraph { hrnCaller.getAllocSite(), toCalleeContext( hrnCaller.getInherent(), preds, - oocTuples + oocHrnIdOoc2callee ), toCalleeContext( hrnCaller.getAlpha(), preds, - oocTuples + oocHrnIdOoc2callee ), preds, hrnCaller.getDescription() @@ -1646,7 +1652,7 @@ public class ReachGraph { reArg.getField(), toCalleeContext( reArg.getBeta(), preds, - oocTuples + oocHrnIdOoc2callee ), preds ); @@ -1692,7 +1698,7 @@ public class ReachGraph { reCaller.getField(), toCalleeContext( reCaller.getBeta(), preds, - oocTuples + oocHrnIdOoc2callee ), preds ); @@ -1789,11 +1795,11 @@ public class ReachGraph { null, // alloc site, shouldn't be used toCalleeContext( oocReach, preds, - oocTuples + oocHrnIdOoc2callee ), toCalleeContext( oocReach, preds, - oocTuples + oocHrnIdOoc2callee ), preds, "out-of-context" @@ -1818,27 +1824,30 @@ public class ReachGraph { null, // alloc site, shouldn't be used toCalleeContext( oocReach, preds, - oocTuples + oocHrnIdOoc2callee ), toCalleeContext( oocReach, preds, - oocTuples + oocHrnIdOoc2callee ), preds, "out-of-context" ); + } else { // otherwise it is there, so merge reachability hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(), toCalleeContext( oocReach, preds, - oocTuples + oocHrnIdOoc2callee ) ) ); } } + assert hrnCalleeAndOutContext.reachHasOnlyOOC(); + rg.addRefEdge( hrnCalleeAndOutContext, hrnDstCallee, new RefEdge( hrnCalleeAndOutContext, @@ -1847,7 +1856,7 @@ public class ReachGraph { reCaller.getField(), toCalleeContext( reCaller.getBeta(), preds, - oocTuples + oocHrnIdOoc2callee ), preds ) @@ -1858,7 +1867,7 @@ public class ReachGraph { oocEdgeExisting.setBeta( Canonical.unionORpreds( oocEdgeExisting.getBeta(), toCalleeContext( reCaller.getBeta(), preds, - oocTuples + oocHrnIdOoc2callee ) ) ); @@ -1873,12 +1882,12 @@ public class ReachGraph { hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(), toCalleeContext( oocReach, preds, - oocTuples + oocHrnIdOoc2callee ) ) ); - + assert hrnCalleeAndOutContext.reachHasOnlyOOC(); } } @@ -2885,10 +2894,13 @@ public class ReachGraph { assert rsetEmpty.equals( edge.getBetaNew() ); } - // calculate boldB for this flagged node, or out-of-context node + // make a mapping of IDs to heap regions they propagate from if( hrn.isFlagged() ) { assert !hrn.isOutOfContext(); assert !icID2srcs.containsKey( hrn.getID() ); + + // in-context flagged node IDs simply propagate from the + // node they name Set srcs = new HashSet(); srcs.add( hrn ); icID2srcs.put( hrn.getID(), srcs ); @@ -2897,6 +2909,13 @@ public class ReachGraph { if( hrn.isOutOfContext() ) { assert !hrn.isFlagged(); + // the reachability states on an out-of-context + // node are not really important (combinations of + // IDs or arity)--what matters is that the states + // specify which nodes this out-of-context node + // stands in for. For example, if the state [17?, 19*] + // appears on the ooc node, it may serve as a source + // for node 17? and a source for node 19. Iterator stateItr = hrn.getAlpha().iterator(); while( stateItr.hasNext() ) { ReachState state = stateItr.next(); diff --git a/Robust/src/Benchmarks/disjoint/makefile b/Robust/src/Benchmarks/disjoint/makefile index c6467d44..f1964338 100644 --- a/Robust/src/Benchmarks/disjoint/makefile +++ b/Robust/src/Benchmarks/disjoint/makefile @@ -1,9 +1,11 @@ BUILDSCRIPT=~/research/Robust/src/buildscript +#DEBUGFLAGS= -disjoint-debug-callsite MDRunner t3 100 + BSFLAGS= -recover -justanalyze -disjoint -disjoint-k 1 -disjoint-write-dots final -disjoint-alias-file aliases.txt normal -enable-assertions all: - $(BUILDSCRIPT) $(BSFLAGS) *.java + $(BUILDSCRIPT) $(BSFLAGS) $(DEBUGFLAGS) *.java clean: rm -f *.bin -- 2.34.1