import IR.State;
import IR.TypeUtil;
-import Analysis.CallGraph.CallGraph;
import IR.MethodDescriptor;
+import IR.TypeDescriptor;
import IR.Flat.*;
+import Util.Pair;
+import Analysis.CallGraph.CallGraph;
import java.util.*;
-// This analysis computes relations between rblocks
-// and identifies important rblocks.
+
+// This analysis finds all reachable rblocks in the
+// program and computes parent/child relations
+// between those rblocks
+
+// SPECIAL NOTE!
+// There is a distict between parent/child and
+// local parent/local child! "Local" means defined
+// and nested within a single method context.
+// Otherwise, SESE/rblocks/tasks may have many
+// parents and many non-method-context-local
+// children considering the call graph
+
+// Also this analysis should identify "critical regions"
+// in the context of interprocedural sese/rblock/task relations
+// where a statement may conflict with some previously executing
+// child task, even if it is in another method context.
+//
+// Ex:
+//
+// void main() {
+// task a {
+// Foo f = new Foo();
+// task achild1 {
+// f.z = 1;
+// }
+// doSomething( f );
+// }
+// }
+//
+// void doSomething( Foo f ) {
+// f.z++; <-------- These two statements are in the critical
+// f.z--; <-------- region of 'a' after 'c1' and before 'c2'
+// task achild2 {
+// f.z--;
+// }
+// }
+
public class RBlockRelationAnalysis {
// compiler data
- State state;
- TypeUtil typeUtil;
+ State state;
+ TypeUtil typeUtil;
CallGraph callGraph;
// an implicit SESE is automatically spliced into
// about it, such as the whole program ends when it ends
protected FlatSESEEnterNode mainSESE;
- // SESEs that are the root of an SESE tree belong to this
- // set--the main SESE is always a root, statically SESEs
- // inside methods are a root because we don't know how they
- // will fit into the runtime tree of SESEs
- protected Set<FlatSESEEnterNode> rootSESEs;
+ // this is a special task object, it is not in any IR graph
+ // and it does not appear to have any children or parents.
+ // It is a stand-in for whichever task is running when a
+ // method context starts such that intraprocedural task
+ // analyses have one static name for "the task who invoked
+ // this method" to attach facts to. It GREATLY simplifies
+ // the OoOJava variable analysis, for instance
+ protected FlatSESEEnterNode callerProxySESE;
- // simply a set of every reachable SESE in the program, not
- // including caller placeholder SESEs
+ // simply the set of every reachable SESE in the program
protected Set<FlatSESEEnterNode> allSESEs;
-
- // a set of every bogus palceholder SESEs
- protected Set<FlatSESEEnterNode> allBogusSESEs;
-
- // per method-per node-rblock stacks
- protected Hashtable< FlatMethod,
- Hashtable< FlatNode,
- Stack<FlatSESEEnterNode>
- >
- > fm2relmap;
// to support calculation of leaf SESEs (no children even
// through method calls) for optimization during code gen
protected Set<MethodDescriptor> methodsContainingSESEs;
-
+
// maps method descriptor to SESE defined inside of it
- // only contains top-level SESE definition in corresponding method
- protected Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>> md2seseSet;
-
- public RBlockRelationAnalysis( State state,
- TypeUtil typeUtil,
- CallGraph callGraph ) {
+ // only contains local root SESE definitions in corresponding method
+ // (has no parent in the local method context)
+ protected Hashtable< MethodDescriptor, Set<FlatSESEEnterNode> > md2localRootSESEs;
+
+ // the set of every local root SESE in the program (SESE that
+ // has no parent in the local method context)
+ protected Set<FlatSESEEnterNode> allLocalRootSESEs;
+
+ // if you want to know which rblocks might be executing a given flat
+ // node it will be in this set
+ protected Hashtable< FlatNode, Set<FlatSESEEnterNode> > fn2currentSESEs;
+
+ // if you want to know which rblocks might be TRANSITIVELY executing
+ // a given flat node it will be in this set
+ protected Hashtable< FlatNode, Set<FlatSESEEnterNode> > fn2allSESEs;
+
+ // if you want to know the method-local, inner-most nested task that
+ // is executing a flat node, it is either here or null.
+ //
+ // ex:
+ // void foo() {
+ // task a {
+ // bar(); <-- here 'a' is the localInnerSESE
+ // }
+ // void bar() {
+ // baz(); <-- here there is no locally-defined SESE, would be null
+ // }
+ protected Hashtable<FlatNode, FlatSESEEnterNode> fn2localInnerSESE;
+
+ // indicates whether this statement might occur in a task and
+ // after some child task definition such that, without looking at
+ // the flat node itself, the parent might have to stall for child
+ protected Hashtable<FlatNode, Boolean> fn2isPotentialStallSite;
+
+ HashMap<MethodDescriptor, Set<Pair<FlatCall, MethodDescriptor>>> methodmap=
+ new HashMap<MethodDescriptor, Set<Pair<FlatCall, MethodDescriptor>>>();
+
+
+
+ ////////////////////////
+ // public interface
+ ////////////////////////
+ public FlatSESEEnterNode getMainSESE() {
+ return mainSESE;
+ }
+
+ public Set<FlatSESEEnterNode> getAllSESEs() {
+ return allSESEs;
+ }
+
+ public Set<FlatSESEEnterNode> getLocalRootSESEs() {
+ return allLocalRootSESEs;
+ }
+
+ public Set<FlatSESEEnterNode> getLocalRootSESEs(FlatMethod fm) {
+ Set<FlatSESEEnterNode> out = md2localRootSESEs.get(fm);
+ if( out == null ) {
+ out = new HashSet<FlatSESEEnterNode>();
+ }
+ return out;
+ }
+
+ public Set<MethodDescriptor> getMethodsWithSESEs() {
+ return methodsContainingSESEs;
+ }
+
+ /* Returns all SESE's that this fn can be a member of
+ * transitively. */
+
+ public Set<FlatSESEEnterNode> getTransitiveExecutingRBlocks(FlatNode fn) {
+ if (fn2allSESEs.containsKey(fn))
+ return fn2allSESEs.get(fn);
+
+ //Compute and memoize result
+ HashSet<FlatSESEEnterNode> seseSet=new HashSet<FlatSESEEnterNode>();
+ fn2allSESEs.put(fn, seseSet);
+ Stack<FlatNode> toprocess=new Stack<FlatNode>();
+ toprocess.add(fn);
+ while(!toprocess.isEmpty()) {
+ FlatNode curr=toprocess.pop();
+ Set<FlatSESEEnterNode> callers=fn2currentSESEs.get(curr);
+ if (callers!=null) {
+ for(FlatSESEEnterNode sese : callers) {
+ if (!seseSet.contains(sese)) {
+ seseSet.add(sese);
+ toprocess.add(fn);
+ }
+ }
+ }
+ }
+ return seseSet;
+ }
+
+ public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks(FlatNode fn) {
+ Set<FlatSESEEnterNode> out = fn2currentSESEs.get(fn);
+ if( out == null ) {
+ out = new HashSet<FlatSESEEnterNode>();
+ }
+ return out;
+ }
+
+ public FlatSESEEnterNode getLocalInnerRBlock(FlatNode fn) {
+ return fn2localInnerSESE.get(fn);
+ }
+
+ // the "caller proxy" is a static name for whichever
+ // task invoked the current method context. It is very
+ // convenient to know this is ALWAYS a different instance
+ // of any task defined within the current method context,
+ // and so using its name simplifies many intraprocedural
+ // analyses
+ public FlatSESEEnterNode getCallerProxySESE() {
+ return callerProxySESE;
+ }
+
+ public boolean isPotentialStallSite(FlatNode fn) {
+ Boolean ipss = fn2isPotentialStallSite.get(fn);
+ if( ipss == null ) {
+ return false;
+ }
+ return ipss;
+ }
+
+
+ public RBlockRelationAnalysis(State state,
+ TypeUtil typeUtil,
+ CallGraph callGraph) {
this.state = state;
this.typeUtil = typeUtil;
this.callGraph = callGraph;
- rootSESEs = new HashSet<FlatSESEEnterNode>();
- allSESEs = new HashSet<FlatSESEEnterNode>();
- allBogusSESEs = new HashSet<FlatSESEEnterNode>();
+ callerProxySESE = new FlatSESEEnterNode(null);
+ callerProxySESE.setIsCallerProxySESE();
- methodsContainingSESEs = new HashSet<MethodDescriptor>();
+ allSESEs = new HashSet<FlatSESEEnterNode>();
+ allLocalRootSESEs = new HashSet<FlatSESEEnterNode>();
+ methodsContainingSESEs = new HashSet<MethodDescriptor>();
+ md2localRootSESEs = new Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>>();
+ fn2currentSESEs = new Hashtable<FlatNode, Set<FlatSESEEnterNode>>();
+ fn2localInnerSESE = new Hashtable<FlatNode, FlatSESEEnterNode>();
+ fn2isPotentialStallSite = new Hashtable<FlatNode, Boolean>();
+ fn2allSESEs = new Hashtable< FlatNode, Set<FlatSESEEnterNode>>();
- fm2relmap =
- new Hashtable< FlatMethod, Hashtable< FlatNode, Stack<FlatSESEEnterNode> > >();
-
- md2seseSet = new Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>>();
-
MethodDescriptor mdSourceEntry = typeUtil.getMain();
- FlatMethod fmMain = state.getMethodFlat( mdSourceEntry );
+ FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
+
+ mainSESE = (FlatSESEEnterNode) fmMain.getNext(0);
+ mainSESE.setfmEnclosing(fmMain);
+ mainSESE.setmdEnclosing(fmMain.getMethod() );
+ mainSESE.setcdEnclosing(fmMain.getMethod().getClassDesc() );
+
- mainSESE = (FlatSESEEnterNode) fmMain.getNext( 0 );
- mainSESE.setfmEnclosing( fmMain );
- mainSESE.setmdEnclosing( fmMain.getMethod() );
- mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
-
// add all methods transitively reachable from the
- // source's main to set for analysis
- Set<MethodDescriptor> descriptorsToAnalyze =
- callGraph.getAllMethods( mdSourceEntry );
-
- descriptorsToAnalyze.add( mdSourceEntry );
+ // source's main to set to find rblocks
+ Set<MethodDescriptor> descriptorsToAnalyze =
+ callGraph.getAllMethods(mdSourceEntry);
- analyzeMethods( descriptorsToAnalyze );
+ descriptorsToAnalyze.add(mdSourceEntry);
- computeLeafSESEs();
- }
+ findRblocksAndLocalParentChildRelations(descriptorsToAnalyze);
+ findTransitiveParentChildRelations();
- public FlatSESEEnterNode getMainSESE() {
- return mainSESE;
- }
+ findPossibleExecutingRBlocksAndStallSites();
- public Set<FlatSESEEnterNode> getRootSESEs() {
- return rootSESEs;
- }
- public Set<FlatSESEEnterNode> getAllSESEs() {
- return allSESEs;
- }
-
- public Stack<FlatSESEEnterNode> getRBlockStacks( FlatMethod fm,
- FlatNode fn ) {
- if( !fm2relmap.containsKey( fm ) ) {
- fm2relmap.put( fm, computeRBlockRelations( fm ) );
- }
- return fm2relmap.get( fm ).get( fn );
+ // Uncomment this phase to debug the marking of potential
+ // stall sites for parents between/after children tasks.
+ // After this debug thing runs in calls System.exit()
+ // debugPrintPotentialStallSites( descriptorsToAnalyze );
}
- protected void analyzeMethods( Set<MethodDescriptor> descriptorsToAnalyze ) {
+
+
+ protected void findRblocksAndLocalParentChildRelations(Set<MethodDescriptor> descriptorsToAnalyze) {
Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
while( mdItr.hasNext() ) {
- FlatMethod fm = state.getMethodFlat( mdItr.next() );
-
- Hashtable< FlatNode, Stack<FlatSESEEnterNode> > relmap =
- computeRBlockRelations( fm );
+ FlatMethod fm = state.getMethodFlat(mdItr.next() );
- fm2relmap.put( fm, relmap );
- }
- }
-
- public Hashtable< FlatNode, Stack<FlatSESEEnterNode> >
- computeRBlockRelations( FlatMethod fm ) {
-
- Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
- new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
-
- // start from flat method top, visit every node in
- // method exactly once, find SESE stack on every
- // control path
- Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
- flatNodesToVisit.add( fm );
-
- Set<FlatNode> visited = new HashSet<FlatNode>();
+ // start from flat method top, visit every node in
+ // method exactly once, find SESE stack on every
+ // control path: this will discover every reachable
+ // SESE in the program, and define the local parent
+ // and local children relations
+ Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
+ new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
- Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
- seseStacks.put( fm, seseStackFirst );
+ Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
+ flatNodesToVisit.add(fm);
- while( !flatNodesToVisit.isEmpty() ) {
- Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
- FlatNode fn = fnItr.next();
+ Set<FlatNode> visited = new HashSet<FlatNode>();
- Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
- assert seseStack != null;
+ Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
+ seseStacks.put(fm, seseStackFirst);
- flatNodesToVisit.remove( fn );
- visited.add( fn );
-
- nodeActions( fn, seseStack, fm );
+ while( !flatNodesToVisit.isEmpty() ) {
+ Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
+ FlatNode fn = fnItr.next();
- for( int i = 0; i < fn.numNext(); i++ ) {
- FlatNode nn = fn.getNext( i );
-
- if( !visited.contains( nn ) ) {
- flatNodesToVisit.add( nn );
-
- // clone stack and send along each control path
- seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
- }
- }
- }
+ Stack<FlatSESEEnterNode> seseStack = seseStacks.get(fn);
+ assert seseStack != null;
+
+ flatNodesToVisit.remove(fn);
+ visited.add(fn);
- return seseStacks;
+ if( !seseStack.isEmpty() ) {
+ fn2localInnerSESE.put(fn, seseStack.peek() );
+ }
+
+ nodeActions(fn, seseStack, fm);
+
+ for( int i = 0; i < fn.numNext(); i++ ) {
+ FlatNode nn = fn.getNext(i);
+
+ if( !visited.contains(nn) ) {
+ flatNodesToVisit.add(nn);
+
+ // clone stack and send along each control path
+ seseStacks.put(nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
+ }
+ }
+ }
+ }
}
-
- protected void nodeActions( FlatNode fn,
- Stack<FlatSESEEnterNode> seseStack,
- FlatMethod fm ) {
+
+ protected void nodeActions(FlatNode fn,
+ Stack<FlatSESEEnterNode> seseStack,
+ FlatMethod fm) {
switch( fn.kind() ) {
case FKind.FlatSESEEnterNode: {
FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
- if( !fsen.getIsCallerSESEplaceholder() ) {
- allSESEs.add( fsen );
- methodsContainingSESEs.add( fm.getMethod() );
- }else{
- allBogusSESEs.add(fsen);
- }
+ allSESEs.add(fsen);
+ methodsContainingSESEs.add(fm.getMethod() );
+
+ fsen.setfmEnclosing(fm);
+ fsen.setmdEnclosing(fm.getMethod() );
+ fsen.setcdEnclosing(fm.getMethod().getClassDesc() );
- fsen.setfmEnclosing( fm );
- fsen.setmdEnclosing( fm.getMethod() );
- fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
-
- if(!fsen.getIsCallerSESEplaceholder() && fsen.getParent()==null ){
- Set<FlatSESEEnterNode> seseSet=md2seseSet.get(fm.getMethod());
- if(seseSet==null){
- seseSet=new HashSet<FlatSESEEnterNode>();
+ if( seseStack.empty() ) {
+ // no local parent
+ fsen.setLocalParent(null);
+
+ allLocalRootSESEs.add(fsen);
+
+ Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get(fm.getMethod() );
+ if( seseSet == null ) {
+ seseSet = new HashSet<FlatSESEEnterNode>();
}
seseSet.add(fsen);
- md2seseSet.put(fm.getMethod(), seseSet);
- }
-
- if( seseStack.empty() ) {
- rootSESEs.add( fsen );
- fsen.setParent( null );
+ md2localRootSESEs.put(fm.getMethod(), seseSet);
+
} else {
- seseStack.peek().addChild( fsen );
- fsen.setParent( seseStack.peek() );
- // if the top of stack is not bogus one, it should be a non-bogus parent to the current sese
- if(!seseStack.peek().getIsCallerSESEplaceholder()){
- fsen.addSESEParent(seseStack.peek());
- }
+ // otherwise a local parent/child relation
+ // which is also the broader parent/child
+ // relation as well
+ seseStack.peek().addLocalChild(fsen);
+ fsen.setLocalParent(seseStack.peek() );
+
+ seseStack.peek().addChild(fsen);
+ fsen.addParent(seseStack.peek() );
}
- seseStack.push( fsen );
+ seseStack.push(fsen);
} break;
case FKind.FlatSESEExitNode: {
case FKind.FlatReturnNode: {
FlatReturnNode frn = (FlatReturnNode) fn;
- if( !seseStack.empty() &&
- !seseStack.peek().getIsCallerSESEplaceholder()
- ) {
- throw new Error( "Error: return statement enclosed within SESE "+
- seseStack.peek().getPrettyIdentifier() );
+ if( !seseStack.empty() ) {
+ throw new Error("Error: return statement enclosed within SESE "+
+ seseStack.peek().getPrettyIdentifier() );
}
} break;
-
+
}
}
- protected void computeLeafSESEs() {
-
- Set<FlatSESEEnterNode> all=new HashSet<FlatSESEEnterNode>();
- all.addAll(allSESEs);
- all.addAll(allBogusSESEs);
-
- for (Iterator<FlatSESEEnterNode> itr = all.iterator(); itr.hasNext();) {
+
+ protected void findTransitiveParentChildRelations() {
+
+ for (Iterator<FlatSESEEnterNode> itr = allSESEs.iterator(); itr.hasNext(); ) {
FlatSESEEnterNode fsen = itr.next();
- boolean hasNoNestedChildren = fsen.getChildren().isEmpty();
+ boolean hasNoNestedChildren = fsen.getLocalChildren().isEmpty();
boolean hasNoChildrenByCall = !hasChildrenByCall(fsen);
fsen.setIsLeafSESE(hasNoNestedChildren && hasNoChildrenByCall);
}
-
- // for( Iterator<FlatSESEEnterNode> itr = allSESEs.iterator();
- // itr.hasNext();
- // ) {
- // FlatSESEEnterNode fsen = itr.next();
- //
- // boolean hasNoNestedChildren = fsen.getChildren().isEmpty();
- // boolean hasNoChildrenByCall = !hasChildrenByCall( fsen );
- //
- // fsen.setIsLeafSESE( hasNoNestedChildren &&
- // hasNoChildrenByCall );
- // }
}
-
protected boolean hasChildrenByCall(FlatSESEEnterNode fsen) {
- boolean hasChildrenByCall=false;
+
+ boolean hasChildrenByCall = false;
// visit every flat node in SESE body, find method calls that
// may transitively call methods with SESEs enclosed
Set<FlatNode> visited = new HashSet<FlatNode>();
- while (!flatNodesToVisit.isEmpty()) {
+ while( !flatNodesToVisit.isEmpty() ) {
Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
FlatNode fn = fnItr.next();
flatNodesToVisit.remove(fn);
visited.add(fn);
-
- if (fn.kind() == FKind.FlatCall) {
- FlatCall fc = (FlatCall) fn;
- MethodDescriptor mdCallee = fc.getMethod();
+
+ if( fn.kind() == FKind.FlatCall ) {
+ FlatCall fc = (FlatCall) fn;
+ MethodDescriptor mdCallee = fc.getMethod();
Set reachable = new HashSet();
reachable.add(mdCallee);
- reachable.addAll(callGraph.getAllMethods(mdCallee));
-
+ reachable.addAll(callGraph.getAllMethods(mdCallee) );
reachable.retainAll(methodsContainingSESEs);
- if (!reachable.isEmpty()) {
+ if( !reachable.isEmpty() ) {
hasChildrenByCall = true;
- if (!fsen.getIsCallerSESEplaceholder()) {
- Set reachableSESEMethodSet =
- callGraph.getFirstReachableMethodContainingSESE(mdCallee, methodsContainingSESEs);
+ Set reachableSESEMethodSet =
+ callGraph.getFirstReachableMethodContainingSESE(mdCallee, methodsContainingSESEs);
+
+ reachableSESEMethodSet.add(mdCallee);
+ reachableSESEMethodSet.retainAll(methodsContainingSESEs);
+
+ for( Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext(); ) {
+ MethodDescriptor md = (MethodDescriptor) iterator.next();
+ Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get(md);
+ if( seseSet != null ) {
+ fsen.addChildren(seseSet);
+ for( Iterator iterator2 = seseSet.iterator(); iterator2.hasNext(); ) {
+ FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
+ child.addParent(fsen);
+ }
+ }
+ }
+ }
+ }
+
+ if( fn == fsen.getFlatExit() ) {
+ // don't enqueue any futher nodes
+ continue;
+ }
+
+ for( int i = 0; i < fn.numNext(); i++ ) {
+ FlatNode nn = fn.getNext(i);
+
+ if( !visited.contains(nn) ) {
+ flatNodesToVisit.add(nn);
+ }
+ }
+ }
+
+ return hasChildrenByCall;
+ }
+
+ protected void findPossibleExecutingRBlocksAndStallSites() {
+ for( Iterator<FlatSESEEnterNode> fsenItr = allSESEs.iterator(); fsenItr.hasNext(); ) {
+ FlatSESEEnterNode fsen = fsenItr.next();
+
+ // walk the program points, including across method calls, reachable within
+ // this sese/rblock/task and mark that this rblock might be executing.
+ // Important: skip the body of child rblocks, BUT DO mark the child ENTER
+ // and EXIT flat nodes as the parent being the current executing rblock!
+ Hashtable<FlatNode, FlatMethod> flatNodesToVisit =
+ new Hashtable<FlatNode, FlatMethod>();
+
+ for( int i = 0; i < fsen.numNext(); i++ ) {
+ FlatNode nn = fsen.getNext(i);
+ flatNodesToVisit.put(nn, fsen.getfmEnclosing() );
+ }
+
+ Set<FlatNode> visited = new HashSet<FlatNode>();
+
+ while (!flatNodesToVisit.isEmpty()) {
+ Map.Entry me = (Map.Entry)flatNodesToVisit.entrySet().iterator().next();
+ FlatNode fn = (FlatNode) me.getKey();
+ FlatMethod fm = (FlatMethod) me.getValue();
+
+ flatNodesToVisit.remove(fn);
+ visited.add(fn);
+
+ // the "is potential stall site" strategy is to propagate
+ // "false" from the beginning of a task until you hit a
+ // child, then from the child's exit propagate "true" for
+ // the parent statements after children. When you pull a node
+ // out of the bag for traversal and it happens to be an
+ // enter or an exit node, fix the dumb propagation that
+ // your IR predecessor pushed on you
+ Boolean isPotentialStallSite = isPotentialStallSite(fn);
+
+ if (fn == fsen.getFlatExit()) {
+ // don't enqueue any further nodes when you find your exit,
+ // NOR mark your own flat as a statement you are currently
+ // executing, your parent(s) will mark it
+ continue;
+ }
+
+ if (fn instanceof FlatSESEExitNode) {
+ setIsPotentialStallSite(fn, false);
+ isPotentialStallSite = true;
+ }
+
+ // the purpose of this traversal is to find program
+ // points where rblock 'fsen' might be executing
+ addPossibleExecutingRBlock(fn, fsen);
+
+ if (fn instanceof FlatSESEEnterNode) {
+ // don't visit internal nodes of child,
+ // just enqueue the exit node
+ FlatSESEEnterNode child = (FlatSESEEnterNode) fn;
+ assert fsen.getChildren().contains(child);
+ assert child.getParents().contains(fsen);
+ flatNodesToVisit.put(child.getFlatExit(), fm);
+ setIsPotentialStallSite(fn, false);
+
+ // explicitly do this to handle the case that you
+ // should mark yourself as possibly executing at
+ // your own exit, because one instance can
+ // recursively invoke another
+ addPossibleExecutingRBlock(child.getFlatExit(), fsen);
+
+ continue;
+ }
+
+ // if previous flat nodes have any changes,,
+ // propagate predecessor's status of stall site potential
+
+ if (fn instanceof FlatCall) {
+
+ // start visiting nodes in other contexts
+ FlatCall fc = (FlatCall) fn;
+ MethodDescriptor mdCallee = fc.getMethod();
+
+ Set<MethodDescriptor> implementations = new HashSet<MethodDescriptor>();
+
+ if (mdCallee.isStatic()) {
+ implementations.add(mdCallee);
+ } else {
+ TypeDescriptor typeDesc = fc.getThis().getType();
+ implementations.addAll(callGraph.getMethods(mdCallee, typeDesc));
+ }
- reachableSESEMethodSet.add(mdCallee);
+ for (Iterator imps = implementations.iterator(); imps.hasNext(); ) {
+ MethodDescriptor mdImp = (MethodDescriptor) imps.next();
+ FlatMethod fmImp = state.getMethodFlat(mdImp);
- for (Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext();) {
- MethodDescriptor md = (MethodDescriptor) iterator.next();
- FlatMethod fm = state.getMethodFlat(md);
- FlatSESEEnterNode fsenBogus = (FlatSESEEnterNode) fm.getNext(0);
- fsenBogus.addSESEParent(fsen);
+ // keep mapping from fc's md to <fc,caller's md>
+ // later, when return node of callee becomes a potential stall site,
+ // following flat nodes of fc should be re-analyzied
+ if(!methodmap.containsKey(fmImp)) {
+ methodmap.put(mdImp, new HashSet<Pair<FlatCall,MethodDescriptor>>());
}
+ methodmap.get(mdImp).add(new Pair<FlatCall,MethodDescriptor>(fc,fm.getMethod()));
- reachableSESEMethodSet.retainAll(methodsContainingSESEs);
+ if ((isPotentialStallSite && !isPotentialStallSite(fmImp)) || !visited.contains(fmImp)) {
+ flatNodesToVisit.put(fmImp, fmImp);
+
+ // propagate your IR graph predecessor's stall site potential
+ mergeIsPotentialStallSite(fmImp, isPotentialStallSite);
+ }
+
+ }
+ // don't 'continue' out of this loop, also enqueue
+ // flat nodes that flow in the current method context
+ }
- for (Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext();) {
- MethodDescriptor md = (MethodDescriptor) iterator.next();
- Set<FlatSESEEnterNode> seseSet = md2seseSet.get(md);
- if (seseSet != null) {
- fsen.addSESEChildren(seseSet);
- for (Iterator iterator2 = seseSet.iterator(); iterator2.hasNext();) {
- FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
- child.addSESEParent(fsen);
+ if (fn instanceof FlatReturnNode) {
+ // if return node is potential stall site, need to inform its caller
+ if (isPotentialStallSite) {
+ Set<Pair<FlatCall, MethodDescriptor>> callset = methodmap.get(fm.getMethod());
+ if (callset != null) {
+ for (Pair<FlatCall, MethodDescriptor> fcallpair : callset) {
+ FlatCall fcall = fcallpair.getFirst();
+ MethodDescriptor mdcaller = fcallpair.getSecond();
+ for (int i = 0; i < fcall.numNext(); i++) {
+ FlatNode nn = fcall.getNext(i);
+ if ( visited.contains(nn) && (!isPotentialStallSite(nn)) ) {
+ mergeIsPotentialStallSite(nn, isPotentialStallSite);
+ FlatMethod fmcaller = state.getMethodFlat(mdcaller);
+ flatNodesToVisit.put(nn, fmcaller);
+ }
}
}
}
+ }
+ }
+ // note: only when current flat node has a change on the status of potential
+ // stall site, need to visit following flat nodes
+ for (int i = 0; i < fn.numNext(); i++) {
+ FlatNode nn = fn.getNext(i);
+ if ((isPotentialStallSite && !isPotentialStallSite(nn)) || !visited.contains(nn)) {
+ flatNodesToVisit.put(nn, fm);
+ mergeIsPotentialStallSite(nn, isPotentialStallSite);
}
}
-
}
+ }
+ }
+
+
+
+ protected void addPossibleExecutingRBlock(FlatNode fn,
+ FlatSESEEnterNode fsen) {
+
+ Set<FlatSESEEnterNode> currentSESEs = fn2currentSESEs.get(fn);
+ if( currentSESEs == null ) {
+ currentSESEs = new HashSet<FlatSESEEnterNode>();
+ }
+
+ currentSESEs.add(fsen);
+ fn2currentSESEs.put(fn, currentSESEs);
+ }
+
+
+ // definitively set whether a statement is a potential stall site
+ // such as a task exit is FALSE and the statement following an exit
+ // is TRUE
+ protected void setIsPotentialStallSite(FlatNode fn,
+ Boolean ipss) {
+ fn2isPotentialStallSite.put(fn, ipss);
+ }
+
+
+ // Use this to OR the previous result with a new result
+ protected void mergeIsPotentialStallSite(FlatNode fn,
+ Boolean ipss) {
+ Boolean ipssPrev = isPotentialStallSite(fn);
+ setIsPotentialStallSite(fn, ipssPrev || ipss);
+ }
+
+
- if (fn == fsen.getFlatExit()) {
- // don't enqueue any futher nodes
- continue;
- }
+
+
+ /////////////////////////////////////////////////
+ // for DEBUG
+ /////////////////////////////////////////////////
+ protected void debugPrintPotentialStallSites(Set<MethodDescriptor> descriptorsToAnalyze) {
+ Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
+ while (mdItr.hasNext()) {
+ FlatMethod fm = state.getMethodFlat(mdItr.next());
+ printStatusMap(fm);
+ }
+ System.exit(0);
+ }
+
+ protected void printStatusMap(FlatMethod fm) {
+
+ System.out.println("\n\n=== "+fm+" ===");
+
+ Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
+ flatNodesToVisit.add(fm);
+
+ Set<FlatNode> visited = new HashSet<FlatNode>();
+
+ while (!flatNodesToVisit.isEmpty()) {
+ Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
+ FlatNode fn = fnItr.next();
+
+ flatNodesToVisit.remove(fn);
+ visited.add(fn);
+
+ System.out.println(fn+"[["+isPotentialStallSite(fn)+"]]");
for (int i = 0; i < fn.numNext(); i++) {
FlatNode nn = fn.getNext(i);
}
}
}
-
- return hasChildrenByCall;
}
-
-}
+}
\ No newline at end of file
projects / IRC.git / blobdiff