From 4c7ed430e496bcd617e764efc5291cd467f292d6 Mon Sep 17 00:00:00 2001 From: jjenista Date: Tue, 30 Mar 2010 21:31:09 +0000 Subject: [PATCH] bug fixes, make stack/Q method-visiting a cmd line arg, some code for debugging monotonicity problem, commented out in this commit --- .../Analysis/Disjoint/DisjointAnalysis.java | 120 ++++++++++++++---- .../src/Analysis/Disjoint/PointerMethod.java | 3 +- Robust/src/Analysis/Disjoint/ReachGraph.java | 99 ++++++++++++++- Robust/src/Analysis/Disjoint/ReachSet.java | 20 --- Robust/src/Benchmarks/disjoint/makefile | 44 ++++--- Robust/src/IR/State.java | 2 + Robust/src/Main/Main.java | 8 +- 7 files changed, 233 insertions(+), 63 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index 8ecc2dfa..81eeb496 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -360,8 +360,9 @@ public class DisjointAnalysis { // current descriptors to visit in fixed-point // interprocedural analysis, prioritized by // dependency in the call graph - protected Stack - //protected PriorityQueue + protected Stack + descriptorsToVisitStack; + protected PriorityQueue descriptorsToVisitQ; // a duplication of the above structure, but @@ -409,7 +410,6 @@ public class DisjointAnalysis { protected Hashtable< Descriptor, Hashtable< FlatCall, ReachGraph > > mapDescriptorToIHMcontributions; - // TODO -- CHANGE EDGE/TYPE/FIELD storage! public static final String arrayElementFieldName = "___element_"; static protected Hashtable mapTypeToArrayField; @@ -426,11 +426,12 @@ public class DisjointAnalysis { //map task descriptor to initial task parameter protected Hashtable - mapDescriptorToReachGraph; + mapDescriptorToReachGraph; protected PointerMethod pm; - protected Hashtable hackmap; + static protected Hashtable fn2rg = + new Hashtable(); // allocate various structures that are not local @@ -459,9 +460,15 @@ public class DisjointAnalysis { mapTypeToArrayField = new Hashtable (); - descriptorsToVisitQ = - new Stack(); - //new PriorityQueue(); + if( state.DISJOINTDVISITSTACK ) { + descriptorsToVisitStack = + new Stack(); + } + + if( state.DISJOINTDVISITPQUE ) { + descriptorsToVisitQ = + new PriorityQueue(); + } descriptorsToVisitSet = new HashSet(); @@ -474,8 +481,6 @@ public class DisjointAnalysis { mapDescriptorToReachGraph = new Hashtable(); - - hackmap = new Hashtable(); } @@ -520,6 +525,8 @@ public class DisjointAnalysis { 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; @@ -564,6 +571,18 @@ public class DisjointAnalysis { } + 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 { @@ -614,16 +633,30 @@ public class DisjointAnalysis { Iterator 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 ); @@ -665,10 +698,13 @@ public class DisjointAnalysis { } else { fm = state.getMethodFlat( d ); } - pm.analyzeMethod(fm); + pm.analyzeMethod( fm ); + // intraprocedural work set Set flatNodesToVisit = new HashSet(); flatNodesToVisit.add( fm ); + + Set debugVisited = new HashSet(); // mapping of current partial results Hashtable mapFlatNodeToReachGraph = @@ -682,6 +718,8 @@ public class DisjointAnalysis { 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. @@ -743,8 +781,37 @@ public class DisjointAnalysis { } } + + // 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 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(); @@ -829,11 +896,6 @@ public class DisjointAnalysis { 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: @@ -1054,6 +1116,7 @@ public class DisjointAnalysis { return rg; } + // this method should generate integers strictly greater than zero! // special "shadow" regions are made from a heap region by negating @@ -1330,9 +1393,18 @@ public class DisjointAnalysis { 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 ); } } diff --git a/Robust/src/Analysis/Disjoint/PointerMethod.java b/Robust/src/Analysis/Disjoint/PointerMethod.java index c7b1d919..1062c163 100644 --- a/Robust/src/Analysis/Disjoint/PointerMethod.java +++ b/Robust/src/Analysis/Disjoint/PointerMethod.java @@ -44,7 +44,8 @@ public class PointerMethod { if (analysisCares(fn)) { HashSet myset=new HashSet(); for(int i=0;i 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 diff --git a/Robust/src/Analysis/Disjoint/ReachSet.java b/Robust/src/Analysis/Disjoint/ReachSet.java index 01882156..e299f71a 100644 --- a/Robust/src/Analysis/Disjoint/ReachSet.java +++ b/Robust/src/Analysis/Disjoint/ReachSet.java @@ -77,26 +77,6 @@ public class ReachSet extends Canonical { return null; } - /* - public boolean containsWithZeroes( ReachState state ) { - assert state != null; - - if( reachStates.contains( state ) ) { - return true; - } - - Iterator itr = iterator(); - while( itr.hasNext() ) { - ReachState stateThis = itr.next(); - if( stateThis.containsWithZeroes( state ) ) { - return true; - } - } - - return false; - } - */ - public boolean containsSuperSet( ReachState state ) { return containsSuperSet( state, false ); } diff --git a/Robust/src/Benchmarks/disjoint/makefile b/Robust/src/Benchmarks/disjoint/makefile index 1b7e685c..39ec62e5 100644 --- a/Robust/src/Benchmarks/disjoint/makefile +++ b/Robust/src/Benchmarks/disjoint/makefile @@ -1,19 +1,30 @@ 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 @@ -21,25 +32,28 @@ BUILDSCRIPT=~/research/Robust/src/buildscript 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: - $(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 diff --git a/Robust/src/IR/State.java b/Robust/src/IR/State.java index 88ddfca8..065c72c7 100644 --- a/Robust/src/IR/State.java +++ b/Robust/src/IR/State.java @@ -83,6 +83,8 @@ public class State { public int DISJOINTSNAPVISITTOSTART=0; public int DISJOINTSNAPNUMVISITS=0; public boolean DISJOINTSNAPSTOPAFTER=false; + public boolean DISJOINTDVISITSTACK=true; + public boolean DISJOINTDVISITPQUE=false; public boolean OPTIONAL=false; public boolean ARRAYPAD=false; diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java index 7471b415..d7f6175c 100644 --- a/Robust/src/Main/Main.java +++ b/Robust/src/Main/Main.java @@ -218,7 +218,13 @@ public class Main { } } else if( option.equals( "-disjoint-release-mode" ) ) { - state.DISJOINTRELEASEMODE = true; + state.DISJOINTRELEASEMODE = true; + + } else if( option.equals( "-disjoint-dvisit-stack" ) ) { + state.DISJOINTDVISITSTACK = true; + + } else if( option.equals( "-disjoint-dvisit-pqueue" ) ) { + state.DISJOINTDVISITPQUE = true; } -- 2.34.1