1 package Analysis.OoOJava;
5 import IR.MethodDescriptor;
6 import IR.TypeDescriptor;
8 import Analysis.CallGraph.CallGraph;
12 // This analysis finds all reachable rblocks in the
13 // program and computes parent/child relations
14 // between those rblocks
17 // There is a distict between parent/child and
18 // local parent/local child! "Local" means defined
19 // and nested within a single method context.
20 // Otherwise, SESE/rblocks/tasks may have many
21 // parents and many non-method-context-local
22 // children considering the call graph
24 // Also this analysis should identify "critical regions"
25 // in the context of interprocedural sese/rblock/task relations
26 // where a statement may conflict with some previously executing
27 // child task, even if it is in another method context.
41 // void doSomething( Foo f ) {
42 // f.z++; <-------- These two statements are in the critical
43 // f.z--; <-------- region of 'a' after 'c1' and before 'c2'
50 public class RBlockRelationAnalysis {
57 // an implicit SESE is automatically spliced into
58 // the IR graph around the C main before this analysis--it
59 // is nothing special except that we can make assumptions
60 // about it, such as the whole program ends when it ends
61 protected FlatSESEEnterNode mainSESE;
63 // this is a special task object, it is not in any IR graph
64 // and it does not appear to have any children or parents.
65 // It is a stand-in for whichever task is running when a
66 // method context starts such that intraprocedural task
67 // analyses have one static name for "the task who invoked
68 // this method" to attach facts to. It GREATLY simplifies
69 // the OoOJava variable analysis, for instance
70 protected FlatSESEEnterNode callerProxySESE;
72 // simply the set of every reachable SESE in the program
73 protected Set<FlatSESEEnterNode> allSESEs;
75 // to support calculation of leaf SESEs (no children even
76 // through method calls) for optimization during code gen
77 protected Set<MethodDescriptor> methodsContainingSESEs;
79 // maps method descriptor to SESE defined inside of it
80 // only contains local root SESE definitions in corresponding method
81 // (has no parent in the local method context)
82 protected Hashtable< MethodDescriptor, Set<FlatSESEEnterNode> > md2localRootSESEs;
84 // the set of every local root SESE in the program (SESE that
85 // has no parent in the local method context)
86 protected Set<FlatSESEEnterNode> allLocalRootSESEs;
88 // if you want to know which rblocks might be executing a given flat
89 // node it will be in this set
90 protected Hashtable< FlatNode, Set<FlatSESEEnterNode> > fn2currentSESEs;
92 // if you want to know which rblocks might be executing a given flat
93 // node it will be in this set
94 protected Hashtable< FlatNode, Set<FlatSESEEnterNode> > fn2allSESEs;
96 // if you want to know the method-local, inner-most nested task that
97 // is executing a flat node, it is either here or null.
102 // bar(); <-- here 'a' is the localInnerSESE
105 // baz(); <-- here there is no locally-defined SESE, would be null
107 protected Hashtable<FlatNode, FlatSESEEnterNode> fn2localInnerSESE;
109 // indicates whether this statement might occur in a task and
110 // after some child task definition such that, without looking at
111 // the flat node itself, the parent might have to stall for child
112 protected Hashtable<FlatNode, Boolean> fn2isPotentialStallSite;
115 ////////////////////////
117 ////////////////////////
118 public FlatSESEEnterNode getMainSESE() {
122 public Set<FlatSESEEnterNode> getAllSESEs() {
126 public Set<FlatSESEEnterNode> getLocalRootSESEs() {
127 return allLocalRootSESEs;
130 public Set<FlatSESEEnterNode> getLocalRootSESEs( FlatMethod fm ) {
131 Set<FlatSESEEnterNode> out = md2localRootSESEs.get( fm );
133 out = new HashSet<FlatSESEEnterNode>();
138 public Set<MethodDescriptor> getMethodsWithSESEs() {
139 return methodsContainingSESEs;
142 /* Returns all SESE's that this fn can be a member of
145 public Set<FlatSESEEnterNode> getTransitiveExecutingRBlocks(FlatNode fn) {
146 if (fn2allSESEs.containsKey(fn))
147 return fn2allSESEs.get(fn);
149 //Compute and memoize result
150 HashSet<FlatSESEEnterNode> seseSet=new HashSet<FlatSESEEnterNode>();
151 fn2allSESEs.put(fn, seseSet);
152 Stack<FlatNode> toprocess=new Stack<FlatNode>();
154 while(!toprocess.isEmpty()) {
155 FlatNode curr=toprocess.pop();
156 Set<FlatSESEEnterNode> callers=fn2currentSESEs.get(curr);
158 for(FlatSESEEnterNode sese:callers) {
159 if (!seseSet.contains(sese)) {
169 public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks( FlatNode fn ) {
170 Set<FlatSESEEnterNode> out = fn2currentSESEs.get( fn );
172 out = new HashSet<FlatSESEEnterNode>();
177 public FlatSESEEnterNode getLocalInnerRBlock( FlatNode fn ) {
178 return fn2localInnerSESE.get( fn );
181 // the "caller proxy" is a static name for whichever
182 // task invoked the current method context. It is very
183 // convenient to know this is ALWAYS a different instance
184 // of any task defined within the current method context,
185 // and so using its name simplifies many intraprocedural
187 public FlatSESEEnterNode getCallerProxySESE() {
188 return callerProxySESE;
191 public boolean isPotentialStallSite( FlatNode fn ) {
192 Boolean ipss = fn2isPotentialStallSite.get( fn );
200 public RBlockRelationAnalysis( State state,
202 CallGraph callGraph ) {
204 this.typeUtil = typeUtil;
205 this.callGraph = callGraph;
207 callerProxySESE = new FlatSESEEnterNode( null );
208 callerProxySESE.setIsCallerProxySESE();
210 allSESEs = new HashSet<FlatSESEEnterNode>();
211 allLocalRootSESEs = new HashSet<FlatSESEEnterNode>();
212 methodsContainingSESEs = new HashSet<MethodDescriptor>();
213 md2localRootSESEs = new Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>>();
214 fn2currentSESEs = new Hashtable<FlatNode, Set<FlatSESEEnterNode>>();
215 fn2localInnerSESE = new Hashtable<FlatNode, FlatSESEEnterNode>();
216 fn2isPotentialStallSite = new Hashtable<FlatNode, Boolean>();
217 fn2allSESEs = new Hashtable< FlatNode, Set<FlatSESEEnterNode>>();
220 MethodDescriptor mdSourceEntry = typeUtil.getMain();
221 FlatMethod fmMain = state.getMethodFlat( mdSourceEntry );
223 mainSESE = (FlatSESEEnterNode) fmMain.getNext( 0 );
224 mainSESE.setfmEnclosing( fmMain );
225 mainSESE.setmdEnclosing( fmMain.getMethod() );
226 mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
229 // add all methods transitively reachable from the
230 // source's main to set to find rblocks
231 Set<MethodDescriptor> descriptorsToAnalyze =
232 callGraph.getAllMethods( mdSourceEntry );
234 descriptorsToAnalyze.add( mdSourceEntry );
236 findRblocksAndLocalParentChildRelations( descriptorsToAnalyze );
238 findTransitiveParentChildRelations();
240 findPossibleExecutingRBlocksAndStallSites();
243 // Uncomment this phase to debug the marking of potential
244 // stall sites for parents between/after children tasks.
245 // After this debug thing runs in calls System.exit()
246 //debugPrintPotentialStallSites( descriptorsToAnalyze );
252 protected void findRblocksAndLocalParentChildRelations( Set<MethodDescriptor> descriptorsToAnalyze ) {
254 Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
255 while( mdItr.hasNext() ) {
256 FlatMethod fm = state.getMethodFlat( mdItr.next() );
258 // start from flat method top, visit every node in
259 // method exactly once, find SESE stack on every
260 // control path: this will discover every reachable
261 // SESE in the program, and define the local parent
262 // and local children relations
263 Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
264 new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
266 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
267 flatNodesToVisit.add( fm );
269 Set<FlatNode> visited = new HashSet<FlatNode>();
271 Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
272 seseStacks.put( fm, seseStackFirst );
274 while( !flatNodesToVisit.isEmpty() ) {
275 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
276 FlatNode fn = fnItr.next();
278 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
279 assert seseStack != null;
281 flatNodesToVisit.remove( fn );
284 if( !seseStack.isEmpty() ) {
285 fn2localInnerSESE.put( fn, seseStack.peek() );
288 nodeActions( fn, seseStack, fm );
290 for( int i = 0; i < fn.numNext(); i++ ) {
291 FlatNode nn = fn.getNext( i );
293 if( !visited.contains( nn ) ) {
294 flatNodesToVisit.add( nn );
296 // clone stack and send along each control path
297 seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
304 protected void nodeActions( FlatNode fn,
305 Stack<FlatSESEEnterNode> seseStack,
307 switch( fn.kind() ) {
309 case FKind.FlatSESEEnterNode: {
310 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
312 allSESEs.add( fsen );
313 methodsContainingSESEs.add( fm.getMethod() );
315 fsen.setfmEnclosing( fm );
316 fsen.setmdEnclosing( fm.getMethod() );
317 fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
319 if( seseStack.empty() ) {
321 fsen.setLocalParent( null );
323 allLocalRootSESEs.add( fsen );
325 Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get( fm.getMethod() );
326 if( seseSet == null ) {
327 seseSet = new HashSet<FlatSESEEnterNode>();
330 md2localRootSESEs.put( fm.getMethod(), seseSet );
333 // otherwise a local parent/child relation
334 // which is also the broader parent/child
336 seseStack.peek().addLocalChild( fsen );
337 fsen.setLocalParent( seseStack.peek() );
339 seseStack.peek().addChild( fsen );
340 fsen.addParent( seseStack.peek() );
343 seseStack.push( fsen );
346 case FKind.FlatSESEExitNode: {
347 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
348 assert !seseStack.empty();
349 FlatSESEEnterNode fsen = seseStack.pop();
352 case FKind.FlatReturnNode: {
353 FlatReturnNode frn = (FlatReturnNode) fn;
354 if( !seseStack.empty() ) {
355 throw new Error( "Error: return statement enclosed within SESE "+
356 seseStack.peek().getPrettyIdentifier() );
365 protected void findTransitiveParentChildRelations() {
367 for (Iterator<FlatSESEEnterNode> itr = allSESEs.iterator(); itr.hasNext();) {
368 FlatSESEEnterNode fsen = itr.next();
370 boolean hasNoNestedChildren = fsen.getLocalChildren().isEmpty();
371 boolean hasNoChildrenByCall = !hasChildrenByCall( fsen );
373 fsen.setIsLeafSESE( hasNoNestedChildren && hasNoChildrenByCall );
377 protected boolean hasChildrenByCall( FlatSESEEnterNode fsen ) {
379 boolean hasChildrenByCall = false;
381 // visit every flat node in SESE body, find method calls that
382 // may transitively call methods with SESEs enclosed
383 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
384 flatNodesToVisit.add( fsen );
386 Set<FlatNode> visited = new HashSet<FlatNode>();
388 while( !flatNodesToVisit.isEmpty() ) {
389 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
390 FlatNode fn = fnItr.next();
392 flatNodesToVisit.remove( fn );
395 if( fn.kind() == FKind.FlatCall ) {
396 FlatCall fc = (FlatCall) fn;
397 MethodDescriptor mdCallee = fc.getMethod();
398 Set reachable = new HashSet();
400 reachable.add( mdCallee );
401 reachable.addAll( callGraph.getAllMethods( mdCallee ) );
402 reachable.retainAll( methodsContainingSESEs );
404 if( !reachable.isEmpty() ) {
405 hasChildrenByCall = true;
407 Set reachableSESEMethodSet =
408 callGraph.getFirstReachableMethodContainingSESE( mdCallee, methodsContainingSESEs );
410 reachableSESEMethodSet.add( mdCallee );
411 reachableSESEMethodSet.retainAll( methodsContainingSESEs );
413 for( Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext(); ) {
414 MethodDescriptor md = (MethodDescriptor) iterator.next();
415 Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get( md );
416 if( seseSet != null ) {
417 fsen.addChildren( seseSet );
418 for( Iterator iterator2 = seseSet.iterator(); iterator2.hasNext(); ) {
419 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
420 child.addParent( fsen );
427 if( fn == fsen.getFlatExit() ) {
428 // don't enqueue any futher nodes
432 for( int i = 0; i < fn.numNext(); i++ ) {
433 FlatNode nn = fn.getNext( i );
435 if( !visited.contains( nn ) ) {
436 flatNodesToVisit.add( nn );
441 return hasChildrenByCall;
444 protected void findPossibleExecutingRBlocksAndStallSites() {
445 for( Iterator<FlatSESEEnterNode> fsenItr = allSESEs.iterator(); fsenItr.hasNext(); ) {
446 FlatSESEEnterNode fsen = fsenItr.next();
448 // walk the program points, including across method calls, reachable within
449 // this sese/rblock/task and mark that this rblock might be executing.
450 // Important: skip the body of child rblocks, BUT DO mark the child ENTER
451 // and EXIT flat nodes as the parent being the current executing rblock!
452 Hashtable<FlatNode, FlatMethod> flatNodesToVisit =
453 new Hashtable<FlatNode, FlatMethod>();
455 for( int i = 0; i < fsen.numNext(); i++ ) {
456 FlatNode nn = fsen.getNext( i );
457 flatNodesToVisit.put( nn, fsen.getfmEnclosing() );
458 mergeIsPotentialStallSite( nn, false );
461 Set<FlatNode> visited = new HashSet<FlatNode>();
463 while( !flatNodesToVisit.isEmpty() ) {
464 Map.Entry me = (Map.Entry) flatNodesToVisit.entrySet().iterator().next();
465 FlatNode fn = (FlatNode) me.getKey();
466 FlatMethod fm = (FlatMethod) me.getValue();
468 flatNodesToVisit.remove( fn );
472 // the "is potential stall site" strategy is to propagate
473 // "false" from the beginning of a task until you hit a
474 // child, then from the child's exit propagate "true" for
475 // the parent statements after children. When you pull a node
476 // out of the bag for traversal and it happens to be an
477 // enter or an exit node, fix the dumb propagation that
478 // your IR predecessor pushed on you
479 Boolean isPotentialStallSite = isPotentialStallSite( fn );
481 if( fn instanceof FlatSESEEnterNode ||
482 fn instanceof FlatSESEExitNode ) {
483 // fix it so this is never a potential stall site, but from
484 // a child definition onward propagate 'true'
485 setIsPotentialStallSite( fn, false );
486 isPotentialStallSite = true;
490 if( fn == fsen.getFlatExit() ) {
491 // don't enqueue any futher nodes when you find your exit,
492 // NOR mark your own flat as a statement you are currently
493 // executing, your parent(s) will mark it
498 // the purpose of this traversal is to find program
499 // points where rblock 'fsen' might be executing
500 addPossibleExecutingRBlock( fn, fsen );
503 if( fn instanceof FlatSESEEnterNode ) {
504 // don't visit internal nodes of child,
505 // just enqueue the exit node
506 FlatSESEEnterNode child = (FlatSESEEnterNode) fn;
507 assert fsen.getChildren().contains( child );
508 assert child.getParents().contains( fsen );
509 flatNodesToVisit.put( child.getFlatExit(), fm );
511 // explicitly do this to handle the case that you
512 // should mark yourself as possibly executing at
513 // your own exit, because one instance can
514 // recursively invoke another
515 addPossibleExecutingRBlock( child.getFlatExit(), fsen );
520 if( fn instanceof FlatCall ) {
521 // start visiting nodes in other contexts
522 FlatCall fc = (FlatCall) fn;
523 MethodDescriptor mdCallee = fc.getMethod();
525 Set<MethodDescriptor> implementations = new HashSet<MethodDescriptor>();
527 if( mdCallee.isStatic() ) {
528 implementations.add( mdCallee );
530 TypeDescriptor typeDesc = fc.getThis().getType();
531 implementations.addAll( callGraph.getMethods( mdCallee, typeDesc ) );
534 for( Iterator imps = implementations.iterator(); imps.hasNext(); ) {
535 MethodDescriptor mdImp = (MethodDescriptor) imps.next();
536 FlatMethod fmImp = state.getMethodFlat( mdImp );
537 flatNodesToVisit.put( fmImp, fmImp );
539 // propagate your IR graph predecessor's stall site potential
540 mergeIsPotentialStallSite( fmImp, isPotentialStallSite );
542 // don't 'continue' out of this loop, also enqueue
543 // flat nodes that flow in the current method context
546 // otherwise keep visiting nodes in same context
547 for( int i = 0; i < fn.numNext(); i++ ) {
548 FlatNode nn = fn.getNext( i );
550 if( !visited.contains( nn ) ) {
551 flatNodesToVisit.put( nn, fm );
553 // propagate your IR graph predecessor's stall site potential
554 mergeIsPotentialStallSite( nn, isPotentialStallSite );
563 protected void addPossibleExecutingRBlock( FlatNode fn,
564 FlatSESEEnterNode fsen ) {
566 Set<FlatSESEEnterNode> currentSESEs = fn2currentSESEs.get( fn );
567 if( currentSESEs == null ) {
568 currentSESEs = new HashSet<FlatSESEEnterNode>();
571 currentSESEs.add( fsen );
572 fn2currentSESEs.put( fn, currentSESEs );
576 // definitively set whether a statement is a potential stall site
577 // such as a task exit is FALSE and the statement following an exit
579 protected void setIsPotentialStallSite( FlatNode fn,
581 fn2isPotentialStallSite.put( fn, ipss );
585 // Use this to OR the previous result with a new result
586 protected void mergeIsPotentialStallSite( FlatNode fn,
588 Boolean ipssPrev = isPotentialStallSite( fn );
589 setIsPotentialStallSite( fn, ipssPrev || ipss );
596 /////////////////////////////////////////////////
598 /////////////////////////////////////////////////
599 protected void debugPrintPotentialStallSites(Set<MethodDescriptor> descriptorsToAnalyze) {
600 Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
601 while (mdItr.hasNext()) {
602 FlatMethod fm = state.getMethodFlat(mdItr.next());
608 protected void printStatusMap(FlatMethod fm) {
610 System.out.println("\n\n=== "+fm+" ===");
612 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
613 flatNodesToVisit.add(fm);
615 Set<FlatNode> visited = new HashSet<FlatNode>();
617 while (!flatNodesToVisit.isEmpty()) {
618 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
619 FlatNode fn = fnItr.next();
621 flatNodesToVisit.remove(fn);
624 System.out.println(fn+"[["+isPotentialStallSite(fn)+"]]");
626 for (int i = 0; i < fn.numNext(); i++) {
627 FlatNode nn = fn.getNext(i);
629 if (!visited.contains(nn)) {
630 flatNodesToVisit.add(nn);