From 8b6b38e755b8ed7f9a50dc95c2b7a54b4fadc0ed Mon Sep 17 00:00:00 2001 From: jjenista <jjenista> Date: Thu, 11 Feb 2010 23:32:38 +0000 Subject: [PATCH] reevaluating abstract garbage collection, for now leave code but don't use it --- Robust/src/Analysis/Disjoint/AllocSite.java | 9 + .../Analysis/Disjoint/DisjointAnalysis.java | 200 ++++++++++-------- .../src/Analysis/Disjoint/ExistPredSet.java | 6 + Robust/src/Analysis/Disjoint/ReachGraph.java | 50 +++-- .../Tests/disjoint/predicateTest2/makefile | 6 +- .../Tests/disjoint/predicateTest2/test.java | 5 +- 6 files changed, 164 insertions(+), 112 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/AllocSite.java b/Robust/src/Analysis/Disjoint/AllocSite.java index 55f60961..ba857de5 100644 --- a/Robust/src/Analysis/Disjoint/AllocSite.java +++ b/Robust/src/Analysis/Disjoint/AllocSite.java @@ -214,6 +214,15 @@ public class AllocSite { "\\n"+getType().toPrettyString(); } } + + public String toStringWithIDs() { + String s = "allocSite "; + for( int i = 0; i < ithOldest.size(); ++i ) { + s += i+"("+ithOldest.get( i )+") "; + } + s += "summary("+summary+")"; + return s; + } public void setFlag( boolean flag ) { this.flag = flag; diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index e144b6dd..914b1092 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -157,19 +157,19 @@ public class DisjointAnalysis { // this analysis generates a disjoint reachability // graph for every reachable method in the program - public DisjointAnalysis( State s, - TypeUtil tu, - CallGraph cg, - Liveness l, + public DisjointAnalysis( State s, + TypeUtil tu, + CallGraph cg, + Liveness l, ArrayReferencees ar ) throws java.io.IOException { init( s, tu, cg, l, ar ); } - protected void init( State state, - TypeUtil typeUtil, - CallGraph callGraph, - Liveness liveness, + protected void init( State state, + TypeUtil typeUtil, + CallGraph callGraph, + Liveness liveness, ArrayReferencees arrayReferencees ) throws java.io.IOException { @@ -351,12 +351,12 @@ public class DisjointAnalysis { // modify rg with appropriate transfer function analyzeFlatNode( d, fm, fn, setReturns, rg ); - /* + if( takeDebugSnapshots && d.getSymbol().equals( descSymbolDebug ) ) { - debugSnapshot(og,fn); + debugSnapshot( rg, fn ); } - */ + // if the results of the new graph are different from // the current graph at this node, replace the graph @@ -403,10 +403,7 @@ public class DisjointAnalysis { // any variables that are no longer live should be // nullified in the graph to reduce edges - // NOTE: it is not clear we need this. It costs a - // liveness calculation for every method, so only - // turn it on if we find we actually need it. - // rg.nullifyDeadVars( liveness.getLiveInTemps( fmContaining, fn ) ); + //rg.nullifyDeadVars( liveness.getLiveInTemps( fmContaining, fn ) ); TempDescriptor lhs; @@ -441,15 +438,7 @@ public class DisjointAnalysis { // 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: @@ -599,7 +588,17 @@ public class DisjointAnalysis { ReachGraph heapForThisCall_cur = rg.makeCalleeView( fc, fmCallee ); + + try { + heapForThisCall_old.writeGraph( "old_"+fc+"TO"+mdCallee, true, false, false, false, false, false ); + heapForThisCall_cur.writeGraph( "cur_"+fc+"TO"+mdCallee, true, false, false, false, false, false ); + } catch( IOException e ) {} + + if( !heapForThisCall_cur.equals( heapForThisCall_old ) ) { + + System.out.println( fc+"TO"+mdCallee+" not equal" ); + // if heap at call site changed, update the contribution, // and reschedule the callee for analysis addIHMcontribution( mdCallee, fc, heapForThisCall_cur ); @@ -623,7 +622,16 @@ public class DisjointAnalysis { break; } // end switch + + // dead variables were removed before the above transfer function + // was applied, so eliminate heap regions and edges that are no + // longer part of the abstractly-live heap graph, and sweep up + // and reachability effects that are altered by the reduction + //rg.abstractGarbageCollect(); + //rg.globalSweep(); + + // at this point rg should be the correct update // by an above transfer function, or untouched if // the flat node type doesn't affect the heap @@ -667,7 +675,7 @@ public class DisjointAnalysis { rg.writeGraph( "COMPLETE"+d, true, // write labels (variables) true, // selectively hide intermediate temp vars - false, // prune unreachable heap regions + true, // prune unreachable heap regions false, // show back edges to confirm graph validity true, // hide subset reachability states true ); // hide edge taints @@ -691,8 +699,8 @@ public class DisjointAnalysis { try { rg.writeGraph( "IHMPARTFOR"+d+"FROM"+fc, true, // write labels (variables) - true, // selectively hide intermediate temp vars - false, // prune unreachable heap regions + false, // selectively hide intermediate temp vars + false, // prune unreachable heap regions false, // show back edges to confirm graph validity true, // hide subset reachability states true ); // hide edge taints @@ -911,72 +919,7 @@ public class DisjointAnalysis { } */ - - /* - // insert a call to debugSnapshot() somewhere in the analysis - // to get successive captures of the analysis state - boolean takeDebugSnapshots = false; - String mcDescSymbolDebug = "setRoute"; - boolean stopAfterCapture = true; - - // increments every visit to debugSnapshot, don't fiddle with it - // IMPORTANT NOTE FOR SETTING THE FOLLOWING VALUES: this - // counter increments just after every node is analyzed - // from the body of the method whose symbol is specified - // above. - int debugCounter = 0; - - // the value of debugCounter to start reporting the debugCounter - // to the screen to let user know what debug iteration we're at - int numStartCountReport = 0; - - // the frequency of debugCounter values to print out, 0 no report - int freqCountReport = 0; - - // the debugCounter value at which to start taking snapshots - int iterStartCapture = 0; - - // the number of snapshots to take - int numIterToCapture = 300; - - void debugSnapshot(ReachabilityGraph og, FlatNode fn) { - if( debugCounter > iterStartCapture + numIterToCapture ) { - return; - } - - ++debugCounter; - if( debugCounter > numStartCountReport && - freqCountReport > 0 && - debugCounter % freqCountReport == 0 ) { - System.out.println(" @@@ debug counter = "+debugCounter); - } - if( debugCounter > iterStartCapture ) { - System.out.println(" @@@ capturing debug "+(debugCounter-iterStartCapture)+" @@@"); - String graphName = String.format("snap%04d",debugCounter-iterStartCapture); - if( fn != null ) { - graphName = graphName+fn; - } - try { - og.writeGraph(graphName, - true, // write labels (variables) - true, // selectively hide intermediate temp vars - true, // prune unreachable heap regions - false, // show back edges to confirm graph validity - false, // show parameter indices (unmaintained!) - true, // hide subset reachability states - true); // hide edge taints - } catch( Exception e ) { - System.out.println("Error writing debug capture."); - System.exit(0); - } - } - - if( debugCounter == iterStartCapture + numIterToCapture && stopAfterCapture ) { - System.out.println("Stopping analysis after debug captures."); - System.exit(0); - } - } - */ + // Take in source entry which is the program's compiled entry and @@ -1180,6 +1123,7 @@ public class DisjointAnalysis { if( heapsFromCallers == null ) { heapsFromCallers = new Hashtable<FlatCall, ReachGraph>(); + mapDescriptorToIHMcontributions.put( d, heapsFromCallers ); } return heapsFromCallers; @@ -1208,4 +1152,74 @@ public class DisjointAnalysis { heapsFromCallers.put( fc, rg ); } + + + + + // get successive captures of the analysis state + boolean takeDebugSnapshots = false; + String descSymbolDebug = "addSomething"; + boolean stopAfterCapture = true; + + // increments every visit to debugSnapshot, don't fiddle with it + int debugCounter = 0; + + // the value of debugCounter to start reporting the debugCounter + // to the screen to let user know what debug iteration we're at + int numStartCountReport = 0; + + // the frequency of debugCounter values to print out, 0 no report + int freqCountReport = 0; + + // the debugCounter value at which to start taking snapshots + int iterStartCapture = 0; + + // the number of snapshots to take + int numIterToCapture = 300; + + void debugSnapshot( ReachGraph rg, FlatNode fn ) { + if( debugCounter > iterStartCapture + numIterToCapture ) { + return; + } + + ++debugCounter; + if( debugCounter > numStartCountReport && + freqCountReport > 0 && + debugCounter % freqCountReport == 0 + ) { + System.out.println( " @@@ debug counter = "+ + debugCounter ); + } + if( debugCounter > iterStartCapture ) { + System.out.println( " @@@ capturing debug "+ + (debugCounter - iterStartCapture)+ + " @@@" ); + String graphName = + String.format( "snap%04d", + debugCounter - iterStartCapture ); + if( fn != null ) { + graphName = graphName + fn; + } + try { + rg.writeGraph( graphName, + true, // write labels (variables) + true, // selectively hide intermediate temp vars + false, // prune unreachable heap regions + false, // show back edges to confirm graph validity + true, // hide subset reachability states + true );// hide edge taints + } catch( Exception e ) { + System.out.println( "Error writing debug capture." ); + System.exit( 0 ); + } + } + + if( debugCounter == iterStartCapture + numIterToCapture && + stopAfterCapture + ) { + System.out.println( "Stopping analysis after debug captures." ); + System.exit( 0 ); + } + } + } diff --git a/Robust/src/Analysis/Disjoint/ExistPredSet.java b/Robust/src/Analysis/Disjoint/ExistPredSet.java index 75d0dfe8..c6ef5c3e 100644 --- a/Robust/src/Analysis/Disjoint/ExistPredSet.java +++ b/Robust/src/Analysis/Disjoint/ExistPredSet.java @@ -50,6 +50,12 @@ public class ExistPredSet extends Canonical { } + + public boolean equals( Object o ) { + return true; + } + + public String toString() { String s = "P["; Iterator<ExistPred> predItr = preds.iterator(); diff --git a/Robust/src/Analysis/Disjoint/ReachGraph.java b/Robust/src/Analysis/Disjoint/ReachGraph.java index 97fa5dd7..53a7886f 100644 --- a/Robust/src/Analysis/Disjoint/ReachGraph.java +++ b/Robust/src/Analysis/Disjoint/ReachGraph.java @@ -376,13 +376,12 @@ public class ReachGraph { } // anytime you might remove edges between heap regions - // you must global sweep to clean up broken reachability + // you must global sweep to clean up broken reachability if( !impossibleEdges.isEmpty() ) { if( !DISABLE_GLOBAL_SWEEP ) { - abstractGarbageCollect(); globalSweep(); } - } + } } @@ -540,13 +539,12 @@ public class ReachGraph { } // if there was a strong update, make sure to improve - // reachability with a global sweep + // reachability with a global sweep if( strongUpdate || !impossibleEdges.isEmpty() ) { if( !DISABLE_GLOBAL_SWEEP ) { - abstractGarbageCollect(); globalSweep(); } - } + } } @@ -600,9 +598,6 @@ public class ReachGraph { ); addRefEdge( lnX, hrnNewest, edgeNew ); - - abstractGarbageCollect(); - globalSweep(); } @@ -626,7 +621,6 @@ public class ReachGraph { // in this graph for efficiency with other operations allocSites.add( as ); - // if there is a k-th oldest node, it merges into // the summary node Integer idK = as.getOldest(); @@ -1344,12 +1338,12 @@ public class ReachGraph { } - + /* try { - rg.writeGraph( "calleeview", true, true, true, false, true, true ); + rg.writeGraph( "calleeview", true, false, false, false, true, true ); } catch( IOException e ) {} - /* + if( fc.getMethod().getSymbol().equals( "addSomething" ) ) { System.exit( 0 ); } @@ -1476,14 +1470,35 @@ public class ReachGraph { // predicates efficiently // //////////////////////////////////////////////////// - public void abstractGarbageCollect() { + public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) { // calculate a root set, will be different for Java // version of analysis versus Bamboo version Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>(); - Iterator<VariableNode> vnItr = td2vn.values().iterator(); - while( vnItr.hasNext() ) { - toVisit.add( vnItr.next() ); + + // visit every variable in graph while building root + // set, and do iterating on a copy, so we can remove + // dead variables while we're at this + Iterator makeCopyItr = td2vn.entrySet().iterator(); + Set entrysCopy = new HashSet(); + while( makeCopyItr.hasNext() ) { + entrysCopy.add( makeCopyItr.next() ); + } + + Iterator eItr = entrysCopy.iterator(); + while( eItr.hasNext() ) { + Map.Entry me = (Map.Entry) eItr.next(); + TempDescriptor td = (TempDescriptor) me.getKey(); + VariableNode vn = (VariableNode) me.getValue(); + + if( liveSet.contains( td ) ) { + toVisit.add( vn ); + + } else { + // dead var, remove completely from graph + td2vn.remove( td ); + clearRefEdgesFrom( vn, null, null, true ); + } } // everything visited in a traversal is @@ -1520,6 +1535,7 @@ public class ReachGraph { HeapRegionNode hrn = hrnAllItr.next(); if( !visited.contains( hrn ) ) { + // heap region nodes are compared across ReachGraph // objects by their integer ID, so when discarding // garbage nodes we must also discard entries in diff --git a/Robust/src/Tests/disjoint/predicateTest2/makefile b/Robust/src/Tests/disjoint/predicateTest2/makefile index 8dcb226e..0b6c6980 100644 --- a/Robust/src/Tests/disjoint/predicateTest2/makefile +++ b/Robust/src/Tests/disjoint/predicateTest2/makefile @@ -3,7 +3,7 @@ PROGRAM=test SOURCE_FILES=$(PROGRAM).java BUILDSCRIPT=~/research/Robust/src/buildscript -BSFLAGS= -mainclass Test -justanalyze -disjoint -disjoint-k 1 -disjoint-write-dots final -disjoint-write-ihms -disjoint-alias-file aliases.txt normal -enable-assertions +BSFLAGS= -mainclass Test -justanalyze -disjoint -disjoint-k 2 -disjoint-write-dots final -disjoint-write-ihms -disjoint-alias-file aliases.txt normal -enable-assertions all: $(PROGRAM).bin @@ -18,6 +18,10 @@ DOTs: $(PROGRAM).bin $(PROGRAM).bin: $(SOURCE_FILES) $(BUILDSCRIPT) $(BSFLAGS) -o $(PROGRAM) $(SOURCE_FILES) +OLDBSFLAGS= -mainclass Test -justanalyze -ownership -ownallocdepth 1 -ownwritedots final -enable-assertions +old: $(SOURCE_FILES) + $(BUILDSCRIPT) $(OLDBSFLAGS) -o $(PROGRAM) $(SOURCE_FILES) + clean: rm -f $(PROGRAM).bin rm -fr tmpbuilddirectory diff --git a/Robust/src/Tests/disjoint/predicateTest2/test.java b/Robust/src/Tests/disjoint/predicateTest2/test.java index 28d5be3c..071d50a9 100644 --- a/Robust/src/Tests/disjoint/predicateTest2/test.java +++ b/Robust/src/Tests/disjoint/predicateTest2/test.java @@ -8,13 +8,16 @@ public class Bar { } public class Test { + static public void main( String[] args ) { Foo f1 = new Foo(); addSomething( f1 ); + /* Foo f2 = new Foo(); - addSomething( f2 ); + addSomething( f2 ); + */ } public static void addSomething( Foo f ) { -- 2.34.1