// current descriptors to visit in fixed-point
// interprocedural analysis, prioritized by
// dependency in the call graph
- protected Stack<DescriptorQWrapper>
- //protected PriorityQueue<DescriptorQWrapper>
+ protected Stack<DescriptorQWrapper>
+ descriptorsToVisitStack;
+ protected PriorityQueue<DescriptorQWrapper>
descriptorsToVisitQ;
// a duplication of the above structure, but
protected Hashtable< Descriptor, Hashtable< FlatCall, ReachGraph > >
mapDescriptorToIHMcontributions;
- // TODO -- CHANGE EDGE/TYPE/FIELD storage!
public static final String arrayElementFieldName = "___element_";
static protected Hashtable<TypeDescriptor, FieldDescriptor>
mapTypeToArrayField;
//map task descriptor to initial task parameter
protected Hashtable<Descriptor, ReachGraph>
- mapDescriptorToReachGraph;
+ mapDescriptorToReachGraph;
protected PointerMethod pm;
- protected Hashtable<FlatMethod, ReachGraph> hackmap;
+ static protected Hashtable<FlatNode, ReachGraph> fn2rg =
+ new Hashtable<FlatNode, ReachGraph>();
// allocate various structures that are not local
mapTypeToArrayField =
new Hashtable <TypeDescriptor, FieldDescriptor>();
- descriptorsToVisitQ =
- new Stack<DescriptorQWrapper>();
- //new PriorityQueue<DescriptorQWrapper>();
+ if( state.DISJOINTDVISITSTACK ) {
+ descriptorsToVisitStack =
+ new Stack<DescriptorQWrapper>();
+ }
+
+ if( state.DISJOINTDVISITPQUE ) {
+ descriptorsToVisitQ =
+ new PriorityQueue<DescriptorQWrapper>();
+ }
descriptorsToVisitSet =
new HashSet<Descriptor>();
mapDescriptorToReachGraph =
new Hashtable<Descriptor, ReachGraph>();
-
- hackmap = new Hashtable<FlatMethod, ReachGraph>();
}
this.snapNodeCounter = 0; // count nodes from 0
this.pm=new PointerMethod();
+ assert state.DISJOINTDVISITSTACK || state.DISJOINTDVISITPQUE;
+ assert !(state.DISJOINTDVISITSTACK && state.DISJOINTDVISITPQUE);
// set some static configuration for ReachGraphs
ReachGraph.allocationDepth = allocationDepth;
}
+ protected boolean moreDescriptorsToVisit() {
+ if( state.DISJOINTDVISITSTACK ) {
+ return !descriptorsToVisitStack.isEmpty();
+
+ } else if( state.DISJOINTDVISITPQUE ) {
+ return !descriptorsToVisitQ.isEmpty();
+ }
+
+ throw new Error( "Neither descriptor visiting mode set" );
+ }
+
+
// fixed-point computation over the call graph--when a
// method's callees are updated, it must be reanalyzed
protected void analyzeMethods() throws java.io.IOException {
Iterator<Descriptor> dItr = sortedDescriptors.iterator();
while( dItr.hasNext() ) {
Descriptor d = dItr.next();
+
mapDescriptorToPriority.put( d, new Integer( p ) );
- descriptorsToVisitQ.add( new DescriptorQWrapper( p, d ) );
+
+ if( state.DISJOINTDVISITSTACK ) {
+ descriptorsToVisitStack.add( new DescriptorQWrapper( p, d ) );
+
+ } else if( state.DISJOINTDVISITPQUE ) {
+ descriptorsToVisitQ.add( new DescriptorQWrapper( p, d ) );
+ }
+
descriptorsToVisitSet.add( d );
++p;
}
// analyze methods from the priority queue until it is empty
- while( !descriptorsToVisitQ.isEmpty() ) {
- Descriptor d = descriptorsToVisitQ.pop().getDescriptor();
- //Descriptor d = descriptorsToVisitQ.poll().getDescriptor();
+ while( moreDescriptorsToVisit() ) {
+ Descriptor d = null;
+
+ if( state.DISJOINTDVISITSTACK ) {
+ d = descriptorsToVisitStack.pop().getDescriptor();
+
+ } else if( state.DISJOINTDVISITPQUE ) {
+ d = descriptorsToVisitQ.poll().getDescriptor();
+ }
assert descriptorsToVisitSet.contains( d );
descriptorsToVisitSet.remove( d );
} else {
fm = state.getMethodFlat( d );
}
- pm.analyzeMethod(fm);
+ pm.analyzeMethod( fm );
+
// intraprocedural work set
Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
flatNodesToVisit.add( fm );
+
+ Set<FlatNode> debugVisited = new HashSet<FlatNode>();
// mapping of current partial results
Hashtable<FlatNode, ReachGraph> mapFlatNodeToReachGraph =
FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
flatNodesToVisit.remove( fn );
+ debugVisited.add( fn );
+
// effect transfer function defined by this node,
// then compare it to the old graph at this node
// to see if anything was updated.
}
}
+
+ // assert that the fixed-point results for each
+ // node in the method is no smaller than the last
+ // time this method was analyzed (monotonicity)
+ /*
+ Iterator<FlatNode> nItr = fm.getNodeSet().iterator();
+ while( nItr.hasNext() ) {
+ FlatNode fn = nItr.next();
+ ReachGraph last = fn2rg.get( fn );
+ ReachGraph newest = mapFlatNodeToReachGraph.get( fn );
+
+ if( newest == null ) {
+ System.out.println( "**********\nfn null result: "+fn+
+ "\nnum visited="+debugVisited.size()+", num in set="+fm.getNodeSet().size()+
+ "\nvisited:"+debugVisited );
+ }
+
+ assert newest != null;
+ if( last != null ) {
+ if( !ReachGraph.isNoSmallerThan( last, newest ) ) {
+ last.writeGraph( "last", true, false, false, true, true );
+ newest.writeGraph( "newest", true, false, false, true, true );
+ throw new Error( "transfer func for "+fn+" was not monotic" );
+ }
+ }
+ fn2rg.put( fn, newest );
+ }
+ */
+
// end by merging all return nodes into a complete
- // ownership graph that represents all possible heap
+ // reach graph that represents all possible heap
// states after the flat method returns
ReachGraph completeGraph = new ReachGraph();
rg.merge_diffMethodContext( rgContrib );
}
- FlatMethod hackfm=(FlatMethod)fn;
- if (hackmap.containsKey(hackfm)) {
- rg.merge(hackmap.get(hackfm));
- }
- hackmap.put(hackfm, rg);
} break;
case FKind.FlatOpNode:
return rg;
}
+
// this method should generate integers strictly greater than zero!
// special "shadow" regions are made from a heap region by negating
protected void enqueue( Descriptor d ) {
if( !descriptorsToVisitSet.contains( d ) ) {
Integer priority = mapDescriptorToPriority.get( d );
- descriptorsToVisitQ.add( new DescriptorQWrapper( priority,
- d )
- );
+
+ if( state.DISJOINTDVISITSTACK ) {
+ descriptorsToVisitStack.add( new DescriptorQWrapper( priority,
+ d )
+ );
+
+ } else if( state.DISJOINTDVISITPQUE ) {
+ descriptorsToVisitQ.add( new DescriptorQWrapper( priority,
+ d )
+ );
+ }
+
descriptorsToVisitSet.add( d );
}
}
public class ReachGraph {
// use to disable improvements for comparison
- protected static final boolean DISABLE_STRONG_UPDATES = false;
+ protected static final boolean DISABLE_STRONG_UPDATES = true;
protected static final boolean DISABLE_GLOBAL_SWEEP = false;
// a special out-of-scope temp
) {
if( writeDebugDOTs ) {
- debugGraphPrefix = String.format( "call%02d", debugCallSiteVisits );
+ System.out.println( " Writing out visit "+
+ debugCallSiteVisits+
+ " to debug call site" );
+
+ debugGraphPrefix = String.format( "call%02d",
+ debugCallSiteVisits );
rgCallee.writeGraph( debugGraphPrefix+"callee",
resolveMethodDebugDOTwriteLabels,
return false;
}
+
+
return true;
}
}
+ // can be used to assert monotonicity
+ static public boolean isNoSmallerThan( ReachGraph rgA,
+ ReachGraph rgB ) {
+
+ //System.out.println( "*** Asking if A is no smaller than B ***" );
+
+
+ Iterator iA = rgA.id2hrn.entrySet().iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry) iA.next();
+ Integer idA = (Integer) meA.getKey();
+ HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
+
+ if( !rgB.id2hrn.containsKey( idA ) ) {
+ System.out.println( " regions smaller" );
+ return false;
+ }
+
+ //HeapRegionNode hrnB = rgB.id2hrn.get( idA );
+ /* NOT EQUALS, NO SMALLER THAN!
+ if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
+ System.out.println( " regions smaller" );
+ return false;
+ }
+ */
+ }
+
+ // this works just fine, no smaller than
+ if( !areallVNinAalsoinBandequal( rgA, rgB ) ) {
+ System.out.println( " vars smaller:" );
+ System.out.println( " A:"+rgA.td2vn.keySet() );
+ System.out.println( " B:"+rgB.td2vn.keySet() );
+ return false;
+ }
+
+
+ iA = rgA.id2hrn.entrySet().iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry) iA.next();
+ Integer idA = (Integer) meA.getKey();
+ HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
+
+ Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
+ while( reItr.hasNext() ) {
+ RefEdge edgeA = reItr.next();
+ RefSrcNode rsnA = edgeA.getSrc();
+
+ // we already checked that nodes were present
+ HeapRegionNode hrnB = rgB.id2hrn.get( hrnA.getID() );
+ assert hrnB != null;
+
+ RefSrcNode rsnB;
+ if( rsnA instanceof VariableNode ) {
+ VariableNode vnA = (VariableNode) rsnA;
+ rsnB = rgB.td2vn.get( vnA.getTempDescriptor() );
+
+ } else {
+ HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
+ rsnB = rgB.id2hrn.get( hrnSrcA.getID() );
+ }
+ assert rsnB != null;
+
+ RefEdge edgeB = rsnB.getReferenceTo( hrnB,
+ edgeA.getType(),
+ edgeA.getField()
+ );
+ if( edgeB == null ) {
+ System.out.println( " edges smaller:" );
+ return false;
+ }
+
+ // REMEMBER, IS NO SMALLER THAN
+ /*
+ System.out.println( " edges smaller" );
+ return false;
+ }
+ */
+
+ }
+ }
+
+
+ return true;
+ }
+
+
+
+
// this analysis no longer has the "match anything"
// type which was represented by null
BUILDSCRIPT=~/research/Robust/src/buildscript
-#DEBUGFLAGS= -disjoint-debug-callsite MDRunner t3 100
-#DEBUGFLAGS= -disjoint-debug-callsite calcGoodFeature calcGoodFeatureTask 100
-#DEBUGFLAGS= -disjoint-debug-callsite getRows calcGoodFeature 4
-#DEBUGFLAGS= -disjoint-debug-callsite setKMeans t3 500
-#DEBUGFLAGS= -disjoint-debug-callsite innerKMeansSetting t6 20
+#################################################
+##
+## To debug a call site, supply the symbols for
+## the callee, then caller, then max number of
+## analysis visits to the call site to write out
+##
+#################################################
#DEBUGFLAGS= -disjoint-debug-callsite setClusters innerKMeansSetting 20
-
+DEBUGFLAGS= -disjoint-debug-callsite ensureCapacity addElement 100
+
+
+#################################################
+##
+## To get snapshots (graphs) for the exit of every
+## node in a method, supply method symbol then the
+## number of analysis visits to the method to skip
+## (early visits usually uninteresting), then the
+## number of visits to take snapshots for, finally
+## a boolean value indicating if the analysis should
+## immediately terminate after the last snapshot visit
+##
+#################################################
#SNAPFLAGS= -disjoint-debug-snap-method calcGoodFeatureTask 5 10 true
#SNAPFLAGS= -disjoint-debug-snap-method calcGoodFeature 5 1 true
-
#SNAPFLAGS= -disjoint-debug-snap-method t3 1 1 true
-#SNAPFLAGS= -disjoint-debug-snap-method t6 5 20 true
-
-#SNAPFLAGS= -disjoint-debug-snap-method innerKMeansSetting 1 20 true
BAMBOOFLAGS= -recover
JAVAFLAGS= -mainclass test
+VISITMODE= -disjoint-dvisit-stack
+#VISITMODE= -disjoint-dvisit-pqueue
+
DEBUGMODE= -enable-assertions -disjoint-write-dots final -disjoint-alias-file aliases.txt normal
RELEASEMODE= -disjoint-release-mode -disjoint-alias-file aliases.txt tabbed
-BSFLAGS= -justanalyze -disjoint -disjoint-k 1
+BSFLAGS= -justanalyze -disjoint -disjoint-k 1 -flatirusermethods
all:
echo 'pass another arg: <bamboo/bamboo-release/java/java-release>'
bamboo:
- $(BUILDSCRIPT) $(BAMBOOFLAGS) $(DEBUGMODE) $(BSFLAGS) $(DEBUGFLAGS) $(SNAPFLAGS) *.java
+ $(BUILDSCRIPT) $(BAMBOOFLAGS) $(DEBUGMODE) $(VISITMODE) $(BSFLAGS) $(DEBUGFLAGS) $(SNAPFLAGS) *.java
bamboo-release:
- $(BUILDSCRIPT) $(BAMBOOFLAGS) $(RELEASEMODE) $(BSFLAGS) $(DEBUGFLAGS) $(SNAPFLAGS) *.java
+ $(BUILDSCRIPT) $(BAMBOOFLAGS) $(RELEASEMODE) $(VISITMODE) $(BSFLAGS) $(DEBUGFLAGS) $(SNAPFLAGS) *.java
java:
- $(BUILDSCRIPT) $(JAVAFLAGS) $(DEBUGMODE) $(BSFLAGS) $(DEBUGFLAGS) $(SNAPFLAGS) *.java
+ $(BUILDSCRIPT) $(JAVAFLAGS) $(DEBUGMODE) $(VISITMODE) $(BSFLAGS) $(DEBUGFLAGS) $(SNAPFLAGS) *.java
java-release:
- $(BUILDSCRIPT) $(JAVAFLAGS) $(RELEASEMODE) $(BSFLAGS) $(DEBUGFLAGS) $(SNAPFLAGS) *.java
+ $(BUILDSCRIPT) $(JAVAFLAGS) $(RELEASEMODE) $(VISITMODE) $(BSFLAGS) $(DEBUGFLAGS) $(SNAPFLAGS) *.java
clean:
rm -f *.bin
projects / IRC.git / commitdiff