From 1b77ac3ea83a06ef7e94101194b06670ebbb9a89 Mon Sep 17 00:00:00 2001 From: jjenista Date: Wed, 23 Sep 2009 23:09:00 +0000 Subject: [PATCH] new parameter decomposition, can't chain results yet --- .../OwnershipAnalysis/OwnershipAnalysis.java | 52 +++-- .../OwnershipAnalysis/OwnershipGraph.java | 57 ++++- .../ParameterDecomposition.java | 205 ++++++++++++++++-- Robust/src/Tests/mlp/param-decomp/makefile | 28 +++ Robust/src/Tests/mlp/param-decomp/test.java | 58 +++++ 5 files changed, 360 insertions(+), 40 deletions(-) create mode 100644 Robust/src/Tests/mlp/param-decomp/makefile create mode 100644 Robust/src/Tests/mlp/param-decomp/test.java diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index 1baddb53..5cfdcb59 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -20,21 +20,24 @@ public class OwnershipAnalysis { public HashSet getFlaggedAllocationSitesReachableFromTask(TaskDescriptor td) { + checkAnalysisComplete(); return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td); } public AllocationSite getAllocationSiteFromFlatNew(FlatNew fn) { + checkAnalysisComplete(); return getAllocationSiteFromFlatNewPRIVATE(fn); } public AllocationSite getAllocationSiteFromHeapRegionNodeID(Integer id) { + checkAnalysisComplete(); return mapHrnIdToAllocationSite.get(id); } public Set createsPotentialAliases(Descriptor taskOrMethod, int paramIndex1, int paramIndex2) { - + checkAnalysisComplete(); OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod); assert(og != null); return og.hasPotentialAlias(paramIndex1, paramIndex2); @@ -43,7 +46,7 @@ public class OwnershipAnalysis { public Set createsPotentialAliases(Descriptor taskOrMethod, int paramIndex, AllocationSite alloc) { - + checkAnalysisComplete(); OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod); assert(og != null); return og.hasPotentialAlias(paramIndex, alloc); @@ -52,7 +55,7 @@ public class OwnershipAnalysis { public Set createsPotentialAliases(Descriptor taskOrMethod, AllocationSite alloc, int paramIndex) { - + checkAnalysisComplete(); OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod); assert(og != null); return og.hasPotentialAlias(paramIndex, alloc); @@ -61,7 +64,7 @@ public class OwnershipAnalysis { public Set createsPotentialAliases(Descriptor taskOrMethod, AllocationSite alloc1, AllocationSite alloc2) { - + checkAnalysisComplete(); OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod); assert(og != null); return og.hasPotentialAlias(alloc1, alloc2); @@ -69,6 +72,8 @@ public class OwnershipAnalysis { protected OwnershipGraph getGraphOfAllContextsFromDescriptor(Descriptor d) { + checkAnalysisComplete(); + assert d != null; OwnershipGraph og = new OwnershipGraph( allocationDepth, typeUtil ); @@ -89,7 +94,9 @@ public class OwnershipAnalysis { } - public String prettyPrintNodeSet( Set s ) { + public String prettyPrintNodeSet( Set s ) { + checkAnalysisComplete(); + String out = "{\n"; Iterator i = s.iterator(); @@ -113,6 +120,7 @@ public class OwnershipAnalysis { // between task parameters and flagged allocation sites reachable // from the task public void writeAllAliases(String outputFile, String timeReport) throws java.io.IOException { + checkAnalysisComplete(); BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) ); @@ -202,6 +210,8 @@ public class OwnershipAnalysis { // this version of writeAllAliases is for Java programs that have no tasks public void writeAllAliasesJava(String outputFile, String timeReport) throws java.io.IOException { + checkAnalysisComplete(); + assert !state.TASK; BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) ); @@ -253,18 +263,25 @@ public class OwnershipAnalysis { // /////////////////////////////////////////// - - + protected void checkAnalysisComplete() { + if( !analysisComplete ) { + throw new Error("Warning: public interface method called while analysis is running."); + } + } // data from the compiler - private State state; - private TypeUtil typeUtil; - private CallGraph callGraph; - private int allocationDepth; + public State state; + public CallGraph callGraph; + public TypeUtil typeUtil; + public int allocationDepth; + + // for public interface methods to warn that they + // are grabbing results during analysis + private boolean analysisComplete; // used to identify HeapRegionNode objects // A unique ID equates an object in one @@ -280,7 +297,7 @@ public class OwnershipAnalysis { // TaskDescriptor and MethodDescriptor are combined // together, with a common parent class Descriptor private Hashtable mapMethodContextToInitialParamAllocGraph; - private Hashtable mapMethodContextToCompleteOwnershipGraph; + public Hashtable mapMethodContextToCompleteOwnershipGraph; private Hashtable mapFlatNewToAllocationSite; private Hashtable > mapDescriptorToAllocationSiteSet; private Hashtable mapMethodContextToNumUpdates; @@ -330,7 +347,7 @@ public class OwnershipAnalysis { boolean writeAllDOTs, String aliasFile) throws java.io.IOException { - double timeStartAnalysis = (double) System.nanoTime(); + analysisComplete = false; this.state = state; this.typeUtil = tu; @@ -371,6 +388,9 @@ public class OwnershipAnalysis { } + double timeStartAnalysis = (double) System.nanoTime(); + + if( state.TASK ) { // initialize methods to visit as the set of all tasks in the // program and then any method that could be called starting @@ -420,6 +440,8 @@ public class OwnershipAnalysis { // as mentioned above, analyze methods one-by-one, possibly revisiting // a method if the methods that it calls are updated analyzeMethods(); + analysisComplete = true; + double timeEndAnalysis = (double) System.nanoTime(); double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) ); @@ -835,7 +857,7 @@ public class OwnershipAnalysis { } } else { - ogMergeOfAllPossibleCalleeResults.resolveMethodCall(fc, md.isStatic(), flatm, onlyPossibleCallee, mc); + ogMergeOfAllPossibleCalleeResults.resolveMethodCall(fc, md.isStatic(), flatm, onlyPossibleCallee, mc, null); } } else { @@ -877,7 +899,7 @@ public class OwnershipAnalysis { } } else { - ogCopy.resolveMethodCall(fc, possibleMd.isStatic(), pflatm, ogPotentialCallee, mc); + ogCopy.resolveMethodCall(fc, possibleMd.isStatic(), pflatm, ogPotentialCallee, mc, null); } ogMergeOfAllPossibleCalleeResults.merge(ogCopy); diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 717b612c..448b3308 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -1780,6 +1780,8 @@ public class OwnershipGraph { return rsOut; } + // detects strong updates to the primary parameter object and + // effects the removal of old edges in the calling graph private void effectCalleeStrongUpdates( Integer paramIndex, OwnershipGraph ogCallee, HeapRegionNode hrnCaller @@ -1827,13 +1829,21 @@ public class OwnershipGraph { return true; } - public void resolveMethodCall(FlatCall fc, - boolean isStatic, - FlatMethod fm, - OwnershipGraph ogCallee, - MethodContext mc + // resolveMethodCall() is used to incorporate a callee graph's effects into + // *this* graph, which is the caller. This method can also be used, after + // the entire analysis is complete, to perform parameter decomposition for + // a given call chain. + public void resolveMethodCall(FlatCall fc, // call site in caller method + boolean isStatic, // whether it is a static method + FlatMethod fm, // the callee method (when virtual, can be many) + OwnershipGraph ogCallee, // the callee's current ownership graph + MethodContext mc, // the aliasing context for this call + ParameterDecomposition pd // if this is not null, we're calling after analysis ) { + + // this debug snippet is harmless for regular use and INVALUABLE at debug time + // to see what potentially goes wrong when a specific method calls another String debugCaller = "foo"; String debugCallee = "bar"; //String debugCaller = "StandardEngine"; @@ -1854,6 +1864,7 @@ public class OwnershipGraph { } + // define rewrite rules and other structures to organize data by parameter/argument index Hashtable paramIndex2rewriteH_p = new Hashtable(); Hashtable paramIndex2rewriteH_s = new Hashtable(); @@ -2132,6 +2143,42 @@ public class OwnershipGraph { assert defParamObj.size() <= fm.numParameters(); + // if we're in parameter decomposition mode, report some results here + if( pd != null ) { + Iterator mapItr; + + // report primary parameter object mappings + mapItr = pi2dr.entrySet().iterator(); + while( mapItr.hasNext() ) { + Map.Entry me = (Map.Entry) mapItr.next(); + Integer paramIndex = (Integer) me.getKey(); + Set hrnAset = (Set) me.getValue(); + + Iterator hrnItr = hrnAset.iterator(); + while( hrnItr.hasNext() ) { + HeapRegionNode hrnA = hrnItr.next(); + pd.mapRegionToParamObject( hrnA, paramIndex ); + } + } + + // report parameter-reachable mappings + mapItr = pi2r.entrySet().iterator(); + while( mapItr.hasNext() ) { + Map.Entry me = (Map.Entry) mapItr.next(); + Integer paramIndex = (Integer) me.getKey(); + Set hrnRset = (Set) me.getValue(); + + Iterator hrnItr = hrnRset.iterator(); + while( hrnItr.hasNext() ) { + HeapRegionNode hrnR = hrnItr.next(); + pd.mapRegionToParamReachable( hrnR, paramIndex ); + } + } + + // and we're done in this method for special param decomp mode + return; + } + // now iterate over reachable nodes to rewrite their alpha, and // classify edges found for beta rewrite diff --git a/Robust/src/Analysis/OwnershipAnalysis/ParameterDecomposition.java b/Robust/src/Analysis/OwnershipAnalysis/ParameterDecomposition.java index 69900a05..2015f367 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ParameterDecomposition.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ParameterDecomposition.java @@ -4,7 +4,7 @@ import IR.*; import IR.Flat.*; import java.util.*; -// This class is useful to instantiate from objects out +// This class must be instantiated from objects out // of a completed analysis. Given a method's reachability // graph and a call site, what heap regions might the // parameter regions be decomposed into? @@ -14,42 +14,207 @@ import java.util.*; // flat call one step back in the chain. public class ParameterDecomposition { - // used to help user realize when they are - // asking for results of an invalid call chain - MethodDescriptor mdCallee; - MethodDescriptor mdCaller; - public ParameterDecomposition( MethodDescriptor md, - FlatCall fc ) { + // the ownership analysis results to compute from + protected OwnershipAnalysis oa; + + // info needed to use OwnershipGraph.resolveMethodCall() + // to do the parameter decomp mapping itself + protected FlatCall fcInCaller; + protected FlatMethod fmPossible; + protected MethodContext mcCallSite; + protected OwnershipGraph ogCallee; + protected OwnershipGraph ogCaller; + + // computed information: + // a IDs are heap regions that map the primary parameter object region + // r IDs are regions that map to the gamma parameter region + // allocation sites are any that provide the regions a param could map to + // type descriptors are any types of any allocation site from above + protected Hashtable > pi2a_id; + protected Hashtable > pi2r_id; + protected Hashtable > pi2a_as; + protected Hashtable > pi2r_as; + protected Hashtable > pi2a_td; + protected Hashtable > pi2r_td; + + + public ParameterDecomposition( OwnershipAnalysis oa, + FlatCall fc, + FlatMethod fm, + MethodContext mc, + OwnershipGraph cee, + OwnershipGraph cer ) { + oa.checkAnalysisComplete(); + this.oa = oa; + + MethodDescriptor md = (MethodDescriptor) mc.getDescriptor(); + // the call site should be calling the method in question + assert fc.getMethod() == md; + + this.fcInCaller = fc; + this.fmPossible = fm; + this.mcCallSite = mc; + + // make copies of the graphs so that resolveMethodCall can + // destroy the graph while calculating the stuff we want + this.ogCallee = new OwnershipGraph( oa.allocationDepth, oa.typeUtil ); + this.ogCallee.merge( cee ); + this.ogCaller = new OwnershipGraph( oa.allocationDepth, oa.typeUtil ); + this.ogCaller.merge( cer ); + + allocOutputStructs(); + + computeDecompositon(); } + /* public ParameterDecomposition( ParameterDecomposition pd, FlatCall fc ) { - + this.oa = pd.oa; + + // the call site should be calling the caller of + // the input parameter decomposition object + assert fc.getMethod() == pd.mdCaller; + + mdCallee = pd.mdCaller; + mdCaller = getCaller( fc ); + } + */ + + protected void allocOutputStructs() { + pi2a_id = new Hashtable >(); + pi2r_id = new Hashtable >(); + pi2a_as = new Hashtable >(); + pi2r_as = new Hashtable >(); + pi2a_td = new Hashtable >(); + pi2r_td = new Hashtable >(); + } + + protected void computeDecompositon() { + MethodDescriptor mdCallee = (MethodDescriptor) mcCallSite.getDescriptor(); + + ogCaller.resolveMethodCall( fcInCaller, + mdCallee.isStatic(), + fmPossible, + ogCallee, + mcCallSite, + this ); + } + + // called by resolveMethodCall in decomp mode + // to report mapping results + protected void mapRegionToParamObject( HeapRegionNode hrn, Integer paramIndex ) { + + // extract region's intergraph ID + Set hrnIDs = pi2a_id.get( paramIndex ); + if( hrnIDs == null ) { + hrnIDs = new HashSet(); + } + hrnIDs.add( hrn.getID() ); + pi2a_id.put( paramIndex, hrnIDs ); + + // the regions allocation site (if any) + AllocationSite as = hrn.getAllocationSite(); + if( as != null ) { + Set asSet = pi2a_as.get( paramIndex ); + if( asSet == null ) { + asSet = new HashSet(); + } + asSet.add( as ); + pi2a_as.put( paramIndex, asSet ); + + // and if there is an allocation site, grab type + Set tdSet = pi2a_td.get( paramIndex ); + if( tdSet == null ) { + tdSet = new HashSet(); + } + tdSet.add( as.getType() ); + pi2a_td.put( paramIndex, tdSet ); + } + } + + protected void mapRegionToParamReachable( HeapRegionNode hrn, Integer paramIndex ) { + + // extract region's intergraph ID + Set hrnIDs = pi2r_id.get( paramIndex ); + if( hrnIDs == null ) { + hrnIDs = new HashSet(); + } + hrnIDs.add( hrn.getID() ); + pi2r_id.put( paramIndex, hrnIDs ); + + // the regions allocation site (if any) + AllocationSite as = hrn.getAllocationSite(); + if( as != null ) { + Set asSet = pi2r_as.get( paramIndex ); + if( asSet == null ) { + asSet = new HashSet(); + } + asSet.add( as ); + pi2r_as.put( paramIndex, asSet ); + + // and if there is an allocation site, grab type + Set tdSet = pi2r_td.get( paramIndex ); + if( tdSet == null ) { + tdSet = new HashSet(); + } + tdSet.add( as.getType() ); + pi2r_td.put( paramIndex, tdSet ); + } } + // this family of "gets" returns, for some // parameter index, all of the associated data // that parameter might decompose into - public Set - getHeapRegionNodeIDs( Integer paramIndex ) { - return null; + public Set getParamObject_hrnIDs( Integer paramIndex ) { + Set hrnIDs = pi2a_id.get( paramIndex ); + if( hrnIDs == null ) { + hrnIDs = new HashSet(); + } + return hrnIDs; } - public Set - getHeapRegionNodes( Integer paramIndex ) { - return null; + public Set getParamObject_allocSites( Integer paramIndex ) { + Set asSet = pi2a_as.get( paramIndex ); + if( asSet == null ) { + asSet = new HashSet(); + } + return asSet; } - public Set - getAllocationSites( Integer paramIndex ) { - return null; + public Set getParamObject_TypeDescs( Integer paramIndex ) { + Set tdSet = pi2a_td.get( paramIndex ); + if( tdSet == null ) { + tdSet = new HashSet(); + } + return tdSet; } - public Set - getTypeDescriptors( Integer paramIndex ) { - return null; + + public Set getParamReachable_hrnIDs( Integer paramIndex ) { + Set hrnIDs = pi2r_id.get( paramIndex ); + if( hrnIDs == null ) { + hrnIDs = new HashSet(); + } + return hrnIDs; + } + + public Set getParamReachable_allocSites( Integer paramIndex ) { + Set asSet = pi2r_as.get( paramIndex ); + if( asSet == null ) { + asSet = new HashSet(); + } + return asSet; } + public Set getParamReachable_TypeDescs( Integer paramIndex ) { + Set tdSet = pi2r_td.get( paramIndex ); + if( tdSet == null ) { + tdSet = new HashSet(); + } + return tdSet; + } } diff --git a/Robust/src/Tests/mlp/param-decomp/makefile b/Robust/src/Tests/mlp/param-decomp/makefile new file mode 100644 index 00000000..0c63f33a --- /dev/null +++ b/Robust/src/Tests/mlp/param-decomp/makefile @@ -0,0 +1,28 @@ +PROGRAM1=testSingle +PROGRAM2=testMulti + +SOURCE_FILES=test.java + +BUILDSCRIPT=~/research/Robust/src/buildscript + +USEMLP= -mlp 8 2 -mlpdebug # use to turn mlp on and off and make sure rest of build not broken +BSFLAGS= -justanalyze -nooptimize -debug -garbagestats -mainclass Test -ownership -ownwritedots final -ownallocdepth 1 -enable-assertions -ownaliasfile aliases.txt + +all: $(PROGRAM2).bin # $(PROGRAM1).bin + +$(PROGRAM1).bin: $(SOURCE_FILES) + $(BUILDSCRIPT) $(BSFLAGS) -o $(PROGRAM1) $(SOURCE_FILES) + +$(PROGRAM2).bin: $(SOURCE_FILES) + $(BUILDSCRIPT) $(USEMLP) $(BSFLAGS) -o $(PROGRAM2) $(SOURCE_FILES) + +clean: + rm -f $(PROGRAM1).bin + rm -f $(PROGRAM2).bin + rm -fr tmpbuilddirectory + rm -f *~ + rm -f *.dot + rm -f *.png + rm -f aliases.txt + rm -f mlpReport*txt + rm -f results*txt diff --git a/Robust/src/Tests/mlp/param-decomp/test.java b/Robust/src/Tests/mlp/param-decomp/test.java new file mode 100644 index 00000000..eaf75d0c --- /dev/null +++ b/Robust/src/Tests/mlp/param-decomp/test.java @@ -0,0 +1,58 @@ +public class Foo { + public Foo f; + public Bar b; + public Foo() {} +} + +public class Bar { + public Foo f; + public Bar b; + public Bar() {} +} + +public class ChildFoo extends Foo { + public ChildFoo() {} +} + +public class ChildBar extends Bar { + public ChildBar() {} +} + + +public class Test { + + public static void main( String args[] ) { + m0(); + } + + public static void m0() { + Foo f1 = new Foo(); + f1.b = new Bar(); + f1.b.b = new ChildBar(); + if( true ) { + f1.b = new Bar(); + } + m1( f1 ); + } + + public static void m1( Foo f ) { + Bar b2 = new Bar(); + b2.f = f; + b2.b = new Bar(); + Foo f2 = new ChildFoo(); + if( true ) { + f2.b = b2.b; + } else if( true ) { + f2.b = new ChildBar(); + } else { + f2.b = f.b; + } + m2( f2, b2 ); + } + + public static void m2( Foo f, Bar b ) { + f.f = new ChildFoo(); + b.f = new ChildFoo(); + f.b.f = b.f; + } +} -- 2.34.1