From 5407deb17c6dcba408dcb21c5454275f721d2cbf Mon Sep 17 00:00:00 2001 From: jjenista Date: Fri, 13 Mar 2009 22:49:19 +0000 Subject: [PATCH] Be more precise about enqueing dependent method contexts, and use topological sorted order of the call graph to give method contexts priority for analysis, targetting leaf methods first. --- .../OwnershipAnalysis/MethodContext.java | 21 +-- .../MethodContextQWrapper.java | 50 +++++++ .../OwnershipAnalysis/OwnershipAnalysis.java | 128 +++++++++++------- .../OwnershipAnalysisTest/test06/test.java | 32 ++++- 4 files changed, 169 insertions(+), 62 deletions(-) create mode 100644 Robust/src/Analysis/OwnershipAnalysis/MethodContextQWrapper.java diff --git a/Robust/src/Analysis/OwnershipAnalysis/MethodContext.java b/Robust/src/Analysis/OwnershipAnalysis/MethodContext.java index 2383cc38..def4891a 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/MethodContext.java +++ b/Robust/src/Analysis/OwnershipAnalysis/MethodContext.java @@ -10,6 +10,7 @@ public class MethodContext { private Descriptor descMethodOrTask; private Set aliasedParameterIndices; + public MethodContext( Descriptor d ) { descMethodOrTask = d; aliasedParameterIndices = new HashSet(); @@ -19,7 +20,17 @@ public class MethodContext { descMethodOrTask = d; aliasedParameterIndices = a; } - + + + public Descriptor getDescriptor() { + return descMethodOrTask; + } + + public Set getAliasedParamIndices() { + return aliasedParameterIndices; + } + + public boolean equals(Object o) { if( o == null ) { return false; @@ -40,14 +51,6 @@ public class MethodContext { aliasedParameterIndices.hashCode(); } - public Descriptor getDescriptor() { - return descMethodOrTask; - } - - public Set getAliasedParamIndices() { - return aliasedParameterIndices; - } - private String getAliasString() { if( aliasedParameterIndices.isEmpty() ) { diff --git a/Robust/src/Analysis/OwnershipAnalysis/MethodContextQWrapper.java b/Robust/src/Analysis/OwnershipAnalysis/MethodContextQWrapper.java new file mode 100644 index 00000000..0e1fc1e3 --- /dev/null +++ b/Robust/src/Analysis/OwnershipAnalysis/MethodContextQWrapper.java @@ -0,0 +1,50 @@ +package Analysis.OwnershipAnalysis; + +import IR.*; +import IR.Flat.*; +import java.util.*; +import java.io.*; + +public class MethodContextQWrapper implements Comparable { + + private int priority; + private MethodContext mc; + + public MethodContextQWrapper( Integer p, MethodContext m ) { + priority = p.intValue(); + mc = m; + } + + public MethodContextQWrapper( int p, MethodContext m ) { + priority = p; + mc = m; + } + + public MethodContext getMethodContext() { + return mc; + } + + public int compareTo( Object o ) throws ClassCastException { + + if( !(o instanceof MethodContextQWrapper) ) { + throw new ClassCastException(); + } + + MethodContextQWrapper mcqw = (MethodContextQWrapper) o; + return priority - mcqw.priority; + } + + public boolean equals(Object o) { + if( o == null ) { + return false; + } + + if( !( o instanceof MethodContextQWrapper) ) { + return false; + } + + MethodContextQWrapper mcqw = (MethodContextQWrapper) o; + + return mc.equals( mcqw.mc ); + } +} diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index d61ff012..142bd5dd 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -281,6 +281,7 @@ public class OwnershipAnalysis { private Hashtable > mapDescriptorToAllocationSiteSet; private Hashtable mapMethodContextToNumUpdates; private Hashtable > mapDescriptorToAllMethodContexts; + private Hashtable > mapMethodContextToDependentContexts; // Use these data structures to track progress of one pass of // processing the FlatNodes of a particular method @@ -296,16 +297,10 @@ public class OwnershipAnalysis { // descriptorsToVisit is initialized to descriptorsToAnalyze and is // reduced by visiting a descriptor during analysis. When dependents // must be scheduled, only those contained in descriptorsToAnalyze - // should be re-added to this set - private HashSet methodContextsToVisit; - - // used in conjunction with the methodContextsToVisit set, fill with - // a topological sort of methodContextsToVisit and then empty that set - // algorithm should analyze something in the linked list until it is - // empty, and then work on the set as normal. The sorted linked list - // is just another, specially sorted bucket that is part of the - // methodContextsToVisit set - private LinkedList sortedMethodContextsToVisit; + // should be re-added to this queue + private PriorityQueue methodContextsToVisitQ; + private Set methodContextsToVisitSet; + private Hashtable mapDescriptorToPriority; // special field descriptors for array elements @@ -369,6 +364,13 @@ public class OwnershipAnalysis { mapTypeToVarField = new Hashtable(); + mapMethodContextToDependentContexts = + new Hashtable >(); + + mapDescriptorToPriority = + new Hashtable(); + + if( writeAllDOTs ) { mapMethodContextToNumUpdates = new Hashtable(); } @@ -470,11 +472,10 @@ public class OwnershipAnalysis { // manage the set of tasks and methods to be analyzed // and be sure to reschedule tasks/methods when the methods // they call are updated - private void analyzeMethods() throws java.io.IOException { - - methodContextsToVisit = new HashSet (); - sortedMethodContextsToVisit = new LinkedList(); + private void analyzeMethods() throws java.io.IOException { + // first gather all of the method contexts to analyze + HashSet allContexts = new HashSet(); Iterator itrd2a = descriptorsToAnalyze.iterator(); while( itrd2a.hasNext() ) { HashSet mcs = mapDescriptorToAllMethodContexts.get( itrd2a.next() ); @@ -482,25 +483,32 @@ public class OwnershipAnalysis { Iterator itrmc = mcs.iterator(); while( itrmc.hasNext() ) { - methodContextsToVisit.add( itrmc.next() ); + allContexts.add( itrmc.next() ); } } - sortedMethodContextsToVisit = topologicalSort( methodContextsToVisit ); - methodContextsToVisit.clear(); + // topologically sort them according to the caller graph so leaf calls are + // ordered first; use that ordering to give method contexts priorities + LinkedList sortedMethodContexts = topologicalSort( allContexts ); - while( !methodContextsToVisit.isEmpty() || - !sortedMethodContextsToVisit.isEmpty() ) { - - MethodContext mc = null; + methodContextsToVisitQ = new PriorityQueue(); + methodContextsToVisitSet = new HashSet(); - if( !sortedMethodContextsToVisit.isEmpty() ) { - mc = sortedMethodContextsToVisit.removeFirst(); - } else { - mc = methodContextsToVisit.iterator().next(); - methodContextsToVisit.remove(mc); - } + int p = 0; + Iterator mcItr = sortedMethodContexts.iterator(); + while( mcItr.hasNext() ) { + MethodContext mc = mcItr.next(); + mapDescriptorToPriority.put( mc.getDescriptor(), new Integer( p ) ); + methodContextsToVisitQ.add( new MethodContextQWrapper( p, mc ) ); + methodContextsToVisitSet.add( mc ); + ++p; + } + // analyze methods from the priority queue until it is empty + while( !methodContextsToVisitQ.isEmpty() ) { + MethodContext mc = methodContextsToVisitQ.poll().getMethodContext(); + assert methodContextsToVisitSet.contains( mc ); + methodContextsToVisitSet.remove( mc ); // because the task or method descriptor just extracted // was in the "to visit" set it either hasn't been analyzed @@ -526,28 +534,15 @@ public class OwnershipAnalysis { if( !og.equals(ogPrev) ) { setGraphForMethodContext(mc, og); - // only methods have dependents, tasks cannot - // be invoked by any user program calls - if( d instanceof MethodDescriptor ) { - MethodDescriptor md = (MethodDescriptor) d; - Set dependents = callGraph.getCallerSet(md); - - if( dependents != null ) { - Iterator depItr = dependents.iterator(); - while( depItr.hasNext() ) { - Descriptor dependent = (Descriptor) depItr.next(); - if( descriptorsToAnalyze.contains(dependent) ) { - - HashSet mcs = mapDescriptorToAllMethodContexts.get( dependent ); - assert mcs != null; - - Iterator itrmc = mcs.iterator(); - while( itrmc.hasNext() ) { - MethodContext methodcontext=itrmc.next(); - methodContextsToVisit.add( methodcontext ); - } - } - } + Iterator depsItr = iteratorDependents( mc ); + while( depsItr.hasNext() ) { + MethodContext mcNext = depsItr.next(); + + if( !methodContextsToVisitSet.contains( mcNext ) ) { + //System.out.println( " queuing "+mcNext ); + methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( mcNext.getDescriptor() ), + mcNext ) ); + methodContextsToVisitSet.add( mcNext ); } } } @@ -837,12 +832,18 @@ public class OwnershipAnalysis { assert contexts != null; contexts.add( mcNew ); + addDependent( mc, mcNew ); + OwnershipGraph onlyPossibleCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew ); if( onlyPossibleCallee == null ) { // if this method context has never been analyzed just schedule it for analysis // and skip over this call site for now - methodContextsToVisit.add( mcNew ); + if( !methodContextsToVisitSet.contains( mcNew ) ) { + methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( md ), + mcNew ) ); + methodContextsToVisitSet.add( mcNew ); + } } else { ogMergeOfAllPossibleCalleeResults.resolveMethodCall(fc, md.isStatic(), flatm, onlyPossibleCallee, mc); @@ -873,12 +874,18 @@ public class OwnershipAnalysis { assert contexts != null; contexts.add( mcNew ); + addDependent( mc, mcNew ); + OwnershipGraph ogPotentialCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew ); if( ogPotentialCallee == null ) { // if this method context has never been analyzed just schedule it for analysis // and skip over this call site for now - methodContextsToVisit.add( mcNew ); + if( !methodContextsToVisitSet.contains( mcNew ) ) { + methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( md ), + mcNew ) ); + methodContextsToVisitSet.add( mcNew ); + } } else { ogCopy.resolveMethodCall(fc, possibleMd.isStatic(), pflatm, ogPotentialCallee, mc); @@ -931,6 +938,25 @@ public class OwnershipAnalysis { } + private void addDependent( MethodContext caller, MethodContext callee ) { + HashSet deps = mapMethodContextToDependentContexts.get( callee ); + if( deps == null ) { + deps = new HashSet(); + } + deps.add( caller ); + mapMethodContextToDependentContexts.put( callee, deps ); + } + + private Iterator iteratorDependents( MethodContext callee ) { + HashSet deps = mapMethodContextToDependentContexts.get( callee ); + if( deps == null ) { + deps = new HashSet(); + mapMethodContextToDependentContexts.put( callee, deps ); + } + return deps.iterator(); + } + + private void writeFinalContextGraphs() { // arguments to writeGraph are: // boolean writeLabels, diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test06/test.java b/Robust/src/Tests/OwnershipAnalysisTest/test06/test.java index 79128edd..df0dfb8e 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test06/test.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test06/test.java @@ -10,13 +10,41 @@ public class Test { static public void main( String[] args ) { Foo a = disjoint A new Foo(); + Foo b = new Foo(); + Foo c = new Foo(); + Foo d = new Foo(); - carolina( a ); + carolina( a, b, c, d ); } - static public void carolina( Foo p1 ) { + static public void carolina( Foo p1, Foo p2, Foo p3, Foo p4 ) { Foo z = disjoint Z new Foo(); p1.f = z; + + vermont( p1, p2, p3, p4 ); + + texas( p1, p2, p3, p4 ); + } + + static public void texas( Foo p1, Foo p2, Foo p3, Foo p4 ) { + if( false ) { + carolina( p3, p4, p1, p2 ); + } + } + + + static public void vermont( Foo p1, Foo p2, Foo p3, Foo p4 ) { + Foo y = new Foo(); + p3.f = y; + p4.g = y; + + utah( p1.f, p2, p3, p4 ); + } + + static public void utah( Foo p1, Foo p2, Foo p3, Foo p4 ) { + Foo x = new Foo(); + p1.f = x; + p2.f = x; } } -- 2.34.1