From 07324c54720d88201f8ec15fee473e151acde429 Mon Sep 17 00:00:00 2001 From: jjenista Date: Wed, 7 Apr 2010 22:53:39 +0000 Subject: [PATCH] deterministic mode works --- .../Disjoint/DescriptorComparator.java | 21 +++++ .../Analysis/Disjoint/DisjointAnalysis.java | 94 ++++++++++++++++--- Robust/src/Analysis/Disjoint/ReachGraph.java | 23 ++--- Robust/src/Benchmarks/disjoint/makefile | 37 +++++--- Robust/src/IR/State.java | 7 +- Robust/src/Main/Main.java | 30 ++++-- 6 files changed, 161 insertions(+), 51 deletions(-) create mode 100644 Robust/src/Analysis/Disjoint/DescriptorComparator.java diff --git a/Robust/src/Analysis/Disjoint/DescriptorComparator.java b/Robust/src/Analysis/Disjoint/DescriptorComparator.java new file mode 100644 index 00000000..9fdc4abd --- /dev/null +++ b/Robust/src/Analysis/Disjoint/DescriptorComparator.java @@ -0,0 +1,21 @@ +package Analysis.Disjoint; + +import IR.*; +import IR.Flat.*; +import java.util.*; +import java.io.*; + +public class DescriptorComparator implements Comparator { + + public int compare( Object o1, Object o2 ) { + + assert o1 instanceof Descriptor; + assert o2 instanceof Descriptor; + + Descriptor d1 = (Descriptor) o1; + Descriptor d2 = (Descriptor) o2; + + return d1.getNum() - d2.getNum(); + } + +} diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index bbd63083..f9f909de 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -465,8 +465,17 @@ public class DisjointAnalysis { // allocate various structures that are not local // to a single class method--should be done once - protected void allocateStructures() { - descriptorsToAnalyze = new HashSet(); + protected void allocateStructures() { + + if( determinismDesired ) { + // use an ordered set + descriptorsToAnalyze + = new TreeSet( new DescriptorComparator() ); + + } else { + // otherwise use a speedy hashset + descriptorsToAnalyze = new HashSet(); + } mapDescriptorToCompleteReachGraph = new Hashtable(); @@ -521,6 +530,8 @@ public class DisjointAnalysis { mapDescriptorToReachGraph = new Hashtable(); + + pm = new PointerMethod(); } @@ -564,7 +575,6 @@ public class DisjointAnalysis { this.stopAfterCapture = state.DISJOINTSNAPSTOPAFTER; this.snapVisitCounter = 1; // count visits from 1 (user will write 1, means 1st visit) this.snapNodeCounter = 0; // count nodes from 0 - this.pm=new PointerMethod(); assert state.DISJOINTDVISITSTACK || @@ -578,7 +588,19 @@ public class DisjointAnalysis { ReachGraph.allocationDepth = allocationDepth; ReachGraph.typeUtil = typeUtil; - ReachGraph.debugCallSiteVisitsUntilExit = state.DISJOINTDEBUGCALLCOUNT; + ReachGraph.debugCallSiteVisitStartCapture + = state.DISJOINTDEBUGCALLVISITTOSTART; + + ReachGraph.debugCallSiteNumVisitsToCapture + = state.DISJOINTDEBUGCALLNUMVISITS; + + ReachGraph.debugCallSiteStopAfter + = state.DISJOINTDEBUGCALLSTOPAFTER; + + ReachGraph.debugCallSiteVisitCounter + = 0; // count visits from 1, is incremented before first visit + + allocateStructures(); @@ -1050,21 +1072,48 @@ public class DisjointAnalysis { break; case FKind.FlatCall: { - //TODO: temporal fix for task descriptor case - //MethodDescriptor mdCaller = fmContaining.getMethod(); Descriptor mdCaller; - if(fmContaining.getMethod()!=null){ - mdCaller = fmContaining.getMethod(); - }else{ - mdCaller = fmContaining.getTask(); + if( fmContaining.getMethod() != null ){ + mdCaller = fmContaining.getMethod(); + } else { + mdCaller = fmContaining.getTask(); } FlatCall fc = (FlatCall) fn; MethodDescriptor mdCallee = fc.getMethod(); FlatMethod fmCallee = state.getMethodFlat( mdCallee ); - boolean writeDebugDOTs = + + boolean debugCallSite = mdCaller.getSymbol().equals( state.DISJOINTDEBUGCALLER ) && - mdCallee.getSymbol().equals( state.DISJOINTDEBUGCALLEE ); + mdCallee.getSymbol().equals( state.DISJOINTDEBUGCALLEE ); + + boolean writeDebugDOTs = false; + boolean stopAfter = false; + if( debugCallSite ) { + ++ReachGraph.debugCallSiteVisitCounter; + System.out.println( " $$$ Debug call site visit "+ + ReachGraph.debugCallSiteVisitCounter+ + " $$$" + ); + if( + (ReachGraph.debugCallSiteVisitCounter >= + ReachGraph.debugCallSiteVisitStartCapture) && + + (ReachGraph.debugCallSiteVisitCounter < + ReachGraph.debugCallSiteVisitStartCapture + + ReachGraph.debugCallSiteNumVisitsToCapture) + ) { + writeDebugDOTs = true; + System.out.println( " $$$ Capturing this call site visit $$$" ); + if( ReachGraph.debugCallSiteStopAfter && + (ReachGraph.debugCallSiteVisitCounter == + ReachGraph.debugCallSiteVisitStartCapture + + ReachGraph.debugCallSiteNumVisitsToCapture - 1) + ) { + stopAfter = true; + } + } + } // calculate the heap this call site can reach--note this is @@ -1157,6 +1206,12 @@ public class DisjointAnalysis { } + if( stopAfter ) { + System.out.println( "$$$ Exiting after requested captures of call site. $$$" ); + System.exit( 0 ); + } + + // now that we've taken care of building heap models for // callee analysis, finish this transformation rg = rgMergeOfEffects; @@ -1399,8 +1454,19 @@ public class DisjointAnalysis { protected LinkedList topologicalSort( Set toSort ) { - Set discovered = new HashSet (); - LinkedList sorted = new LinkedList(); + Set discovered; + + if( determinismDesired ) { + // use an ordered set + discovered + = new TreeSet( new DescriptorComparator() ); + + } else { + // otherwise use a speedy hashset + discovered = new HashSet(); + } + + LinkedList sorted = new LinkedList(); Iterator itr = toSort.iterator(); while( itr.hasNext() ) { diff --git a/Robust/src/Analysis/Disjoint/ReachGraph.java b/Robust/src/Analysis/Disjoint/ReachGraph.java index 860cc2a4..9368e4dd 100644 --- a/Robust/src/Analysis/Disjoint/ReachGraph.java +++ b/Robust/src/Analysis/Disjoint/ReachGraph.java @@ -1883,7 +1883,7 @@ public class ReachGraph { if( writeDebugDOTs ) { - debugGraphPrefix = String.format( "call%02d", debugCallSiteVisits ); + debugGraphPrefix = String.format( "call%02d", debugCallSiteVisitCounter ); rg.writeGraph( debugGraphPrefix+"calleeview", resolveMethodDebugDOTwriteLabels, resolveMethodDebugDOTselectTemps, @@ -1907,8 +1907,10 @@ public class ReachGraph { private static boolean resolveMethodDebugDOThideEdgeTaints = true; static String debugGraphPrefix; - static int debugCallSiteVisits = 0; - static int debugCallSiteVisitsUntilExit = 0; + static int debugCallSiteVisitCounter; + static int debugCallSiteVisitStartCapture; + static int debugCallSiteNumVisitsToCapture; + static boolean debugCallSiteStopAfter; public void @@ -1921,11 +1923,11 @@ public class ReachGraph { if( writeDebugDOTs ) { System.out.println( " Writing out visit "+ - debugCallSiteVisits+ + debugCallSiteVisitCounter+ " to debug call site" ); debugGraphPrefix = String.format( "call%02d", - debugCallSiteVisits ); + debugCallSiteVisitCounter ); rgCallee.writeGraph( debugGraphPrefix+"callee", resolveMethodDebugDOTwriteLabels, @@ -2676,22 +2678,13 @@ public class ReachGraph { } - - - if( writeDebugDOTs ) { writeGraph( debugGraphPrefix+"caller90AfterTransfer", resolveMethodDebugDOTwriteLabels, resolveMethodDebugDOTselectTemps, resolveMethodDebugDOTpruneGarbage, resolveMethodDebugDOThideSubsetReach, - resolveMethodDebugDOThideEdgeTaints ); - - ++debugCallSiteVisits; - if( debugCallSiteVisits >= debugCallSiteVisitsUntilExit ) { - System.out.println( "!!! Exiting after requested visits to call site. !!!" ); - System.exit( 0 ); - } + resolveMethodDebugDOThideEdgeTaints ); } } diff --git a/Robust/src/Benchmarks/disjoint/makefile b/Robust/src/Benchmarks/disjoint/makefile index 107207c8..7ae40543 100644 --- a/Robust/src/Benchmarks/disjoint/makefile +++ b/Robust/src/Benchmarks/disjoint/makefile @@ -2,29 +2,36 @@ BUILDSCRIPT=~/research/Robust/src/buildscript ################################################# ## -## 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 +## To debug a call site supply: +## 1. callee symbol +## 2. caller symbol +## 3. number of analysis call site visits to skip, +## before starting to capture (early visits +## are usually uninteresting) +## 4. number of call site visits to capture +## 5. whether to halt analysis immediately +## after capture (or let it run on normally) ## ################################################# -#DEBUGFLAGS= -disjoint-debug-callsite setClusters innerKMeansSetting 20 -#DEBUGFLAGS= -disjoint-debug-callsite ensureCapacity addElement 100 -#DEBUGFLAGS= -disjoint-debug-callsite setPartial reduceOutput 100 +#DEBUGFLAGS= -disjoint-debug-callsite addInterOutput t6 50 5 false + ################################################# ## ## 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 +## node in a method, supply: +## 1. method symbol +## 2. number of methods visits to skip, +## before starting to capture (early visits +## are usually uninteresting) +## 3. number of analysis method visits to capture +## 4. whether to halt analysis immediately +## after capture (or let it run on normally) ## ################################################# #SNAPFLAGS= -disjoint-debug-snap-method calcGoodFeatureTask 5 10 true #SNAPFLAGS= -disjoint-debug-snap-method calcGoodFeature 5 1 true -SNAPFLAGS= -disjoint-debug-snap-method t6 20 5 true +SNAPFLAGS= -disjoint-debug-snap-method t6 30 1 false #SNAPFLAGS= -disjoint-debug-snap-method reduceOutput 5 50 true #SNAPFLAGS= -disjoint-debug-snap-method setReduceFinish 5 50 true #SNAPFLAGS= -disjoint-debug-snap-method setPartial 1 50 true @@ -34,8 +41,8 @@ BAMBOOFLAGS= -recover JAVAFLAGS= -mainclass test #VISITMODE= -disjoint-dvisit-stack -VISITMODE= -disjoint-dvisit-pqueue -#VISITMODE= -disjoint-dvisit-stack-callees-on-top +#VISITMODE= -disjoint-dvisit-pqueue +VISITMODE= -disjoint-dvisit-stack-callees-on-top DEBUGMODE= -enable-assertions -disjoint-write-dots final -disjoint-alias-file aliases.txt normal -disjoint-desire-determinism RELEASEMODE= -disjoint-release-mode -disjoint-alias-file aliases.txt tabbed diff --git a/Robust/src/IR/State.java b/Robust/src/IR/State.java index ecada3b4..97ee6e81 100644 --- a/Robust/src/IR/State.java +++ b/Robust/src/IR/State.java @@ -77,13 +77,18 @@ public class State { public boolean DISJOINTWRITEIHMS=false; public String DISJOINTALIASFILE=null; public boolean DISJOINTALIASTAB=false; - public int DISJOINTDEBUGCALLCOUNT=0; + public String DISJOINTDEBUGCALLEE=null; public String DISJOINTDEBUGCALLER=null; + public int DISJOINTDEBUGCALLVISITTOSTART=0; + public int DISJOINTDEBUGCALLNUMVISITS=0; + public boolean DISJOINTDEBUGCALLSTOPAFTER=false; + public String DISJOINTSNAPSYMBOL=null; public int DISJOINTSNAPVISITTOSTART=0; public int DISJOINTSNAPNUMVISITS=0; public boolean DISJOINTSNAPSTOPAFTER=false; + public boolean DISJOINTDVISITSTACK=true; public boolean DISJOINTDVISITPQUE=false; public boolean DISJOINTDVISITSTACKEESONTOP=false; diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java index 84a6302c..c186b6c2 100644 --- a/Robust/src/Main/Main.java +++ b/Robust/src/Main/Main.java @@ -196,13 +196,23 @@ public class Main { } else if( arg.equals("tabbed") ) { state.DISJOINTALIASTAB = true; } else { - throw new Error("disjoint-alias-file requires arguments "); + throw new Error("disjoint-alias-file requires arguments: "); } } else if (option.equals("-disjoint-debug-callsite")) { state.DISJOINTDEBUGCALLEE=args[++i]; state.DISJOINTDEBUGCALLER=args[++i]; - state.DISJOINTDEBUGCALLCOUNT=Integer.parseInt(args[++i]); + state.DISJOINTDEBUGCALLVISITTOSTART=Integer.parseInt(args[++i]); + state.DISJOINTDEBUGCALLNUMVISITS=Integer.parseInt(args[++i]); + String arg = args[++i]; + if( arg.equals("true") ) { + state.DISJOINTDEBUGCALLSTOPAFTER = true; + } else if( arg.equals("false") ) { + state.DISJOINTDEBUGCALLSTOPAFTER = false; + } else { + throw new Error("disjoint-debug-callsite requires arguments:\n"+ + " <# visit to start> <# visits to capture> "); + } } else if (option.equals("-disjoint-debug-snap-method")) { state.DISJOINTSNAPSYMBOL=args[++i]; @@ -214,15 +224,13 @@ public class Main { } else if( arg.equals("false") ) { state.DISJOINTSNAPSTOPAFTER = false; } else { - throw new Error("disjoint-debug-snap-method requires arguments <# visit to start> <# visits to snap> "); + throw new Error("disjoint-debug-snap-method requires arguments:\n"+ + " <# visit to start> <# visits to snap> "); } } else if( option.equals( "-disjoint-release-mode" ) ) { state.DISJOINTRELEASEMODE = true; - } else if( option.equals( "-disjoint-desire-determinism" ) ) { - state.DISJOINTDETERMINISM = true; - } else if( option.equals( "-disjoint-dvisit-stack" ) ) { state.DISJOINTDVISITSTACK = true; state.DISJOINTDVISITPQUE = false; @@ -237,6 +245,16 @@ public class Main { state.DISJOINTDVISITSTACKEESONTOP = true; state.DISJOINTDVISITPQUE = false; state.DISJOINTDVISITSTACK = false; + + } else if( option.equals( "-disjoint-desire-determinism" ) ) { + state.DISJOINTDETERMINISM = true; + + // when asking analysis for a deterministic result, force + // a stack-based visiting scheme, because the priority queue + // requires a non-deterministic topological sort + state.DISJOINTDVISITSTACKEESONTOP = true; + state.DISJOINTDVISITPQUE = false; + state.DISJOINTDVISITSTACK = false; } -- 2.34.1