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 the method-local, inner-most nested task that
93 // is executing a flat node, it is either here or null.
98 // bar(); <-- here 'a' is the localInnerSESE
101 // baz(); <-- here there is no locally-defined SESE, would be null
103 protected Hashtable<FlatNode, FlatSESEEnterNode> fn2localInnerSESE;
105 // indicates whether this statement might occur in a task and
106 // after some child task definition such that, without looking at
107 // the flat node itself, the parent might have to stall for child
108 protected Hashtable<FlatNode, Boolean> fn2isPotentialStallSite;
111 ////////////////////////
113 ////////////////////////
114 public FlatSESEEnterNode getMainSESE() {
118 public FlatSESEEnterNode getCallerProxySESE() {
119 return callerProxySESE;
122 public Set<FlatSESEEnterNode> getAllSESEs() {
126 public Set<FlatSESEEnterNode> getLocalRootSESEs() {
127 return allLocalRootSESEs;
130 public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks( FlatNode fn ) {
131 return fn2currentSESEs.get( fn );
134 public FlatSESEEnterNode getLocalInnerRBlock( FlatNode fn ) {
135 return fn2localInnerSESE.get( fn );
138 public boolean isPotentialStallSite( FlatNode fn ) {
139 Boolean ipss = fn2isPotentialStallSite.get( fn );
147 public RBlockRelationAnalysis( State state,
149 CallGraph callGraph ) {
151 this.typeUtil = typeUtil;
152 this.callGraph = callGraph;
154 callerProxySESE = new FlatSESEEnterNode( null );
156 allSESEs = new HashSet<FlatSESEEnterNode>();
157 allLocalRootSESEs = new HashSet<FlatSESEEnterNode>();
158 methodsContainingSESEs = new HashSet<MethodDescriptor>();
159 md2localRootSESEs = new Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>>();
160 fn2currentSESEs = new Hashtable<FlatNode, Set<FlatSESEEnterNode>>();
161 fn2localInnerSESE = new Hashtable<FlatNode, FlatSESEEnterNode>();
162 fn2isPotentialStallSite = new Hashtable<FlatNode, Boolean>();
165 MethodDescriptor mdSourceEntry = typeUtil.getMain();
166 FlatMethod fmMain = state.getMethodFlat( mdSourceEntry );
168 mainSESE = (FlatSESEEnterNode) fmMain.getNext( 0 );
169 mainSESE.setfmEnclosing( fmMain );
170 mainSESE.setmdEnclosing( fmMain.getMethod() );
171 mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
174 // add all methods transitively reachable from the
175 // source's main to set to find rblocks
176 Set<MethodDescriptor> descriptorsToAnalyze =
177 callGraph.getAllMethods( mdSourceEntry );
179 descriptorsToAnalyze.add( mdSourceEntry );
181 findRblocksAndLocalParentChildRelations( descriptorsToAnalyze );
183 findTransitiveParentChildRelations();
185 findPossibleExecutingRBlocksAndStallSites();
188 // Uncomment this phase to debug the marking of potential
189 // stall sites for parents between/after children tasks.
190 // After this debug thing runs in calls System.exit()
191 //debugPrintPotentialStallSites( descriptorsToAnalyze );
197 protected void findRblocksAndLocalParentChildRelations( Set<MethodDescriptor> descriptorsToAnalyze ) {
199 Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
200 while( mdItr.hasNext() ) {
201 FlatMethod fm = state.getMethodFlat( mdItr.next() );
203 // start from flat method top, visit every node in
204 // method exactly once, find SESE stack on every
205 // control path: this will discover every reachable
206 // SESE in the program, and define the local parent
207 // and local children relations
208 Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
209 new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
211 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
212 flatNodesToVisit.add( fm );
214 Set<FlatNode> visited = new HashSet<FlatNode>();
216 Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
217 seseStacks.put( fm, seseStackFirst );
219 while( !flatNodesToVisit.isEmpty() ) {
220 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
221 FlatNode fn = fnItr.next();
223 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
224 assert seseStack != null;
226 flatNodesToVisit.remove( fn );
229 if( !seseStack.isEmpty() ) {
230 fn2localInnerSESE.put( fn, seseStack.peek() );
233 nodeActions( fn, seseStack, fm );
235 for( int i = 0; i < fn.numNext(); i++ ) {
236 FlatNode nn = fn.getNext( i );
238 if( !visited.contains( nn ) ) {
239 flatNodesToVisit.add( nn );
241 // clone stack and send along each control path
242 seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
249 protected void nodeActions( FlatNode fn,
250 Stack<FlatSESEEnterNode> seseStack,
252 switch( fn.kind() ) {
254 case FKind.FlatSESEEnterNode: {
255 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
257 allSESEs.add( fsen );
258 methodsContainingSESEs.add( fm.getMethod() );
260 fsen.setfmEnclosing( fm );
261 fsen.setmdEnclosing( fm.getMethod() );
262 fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
264 if( seseStack.empty() ) {
266 fsen.setLocalParent( null );
268 allLocalRootSESEs.add( fsen );
270 Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get( fm.getMethod() );
271 if( seseSet == null ) {
272 seseSet = new HashSet<FlatSESEEnterNode>();
275 md2localRootSESEs.put( fm.getMethod(), seseSet );
278 // otherwise a local parent/child relation
279 // which is also the broader parent/child
281 seseStack.peek().addLocalChild( fsen );
282 fsen.setLocalParent( seseStack.peek() );
284 seseStack.peek().addChild( fsen );
285 fsen.addParent( seseStack.peek() );
288 seseStack.push( fsen );
291 case FKind.FlatSESEExitNode: {
292 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
293 assert !seseStack.empty();
294 FlatSESEEnterNode fsen = seseStack.pop();
297 case FKind.FlatReturnNode: {
298 FlatReturnNode frn = (FlatReturnNode) fn;
299 if( !seseStack.empty() ) {
300 throw new Error( "Error: return statement enclosed within SESE "+
301 seseStack.peek().getPrettyIdentifier() );
310 protected void findTransitiveParentChildRelations() {
312 for (Iterator<FlatSESEEnterNode> itr = allSESEs.iterator(); itr.hasNext();) {
313 FlatSESEEnterNode fsen = itr.next();
315 boolean hasNoNestedChildren = fsen.getLocalChildren().isEmpty();
316 boolean hasNoChildrenByCall = !hasChildrenByCall( fsen );
318 fsen.setIsLeafSESE( hasNoNestedChildren && hasNoChildrenByCall );
322 protected boolean hasChildrenByCall( FlatSESEEnterNode fsen ) {
324 boolean hasChildrenByCall = false;
326 // visit every flat node in SESE body, find method calls that
327 // may transitively call methods with SESEs enclosed
328 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
329 flatNodesToVisit.add( fsen );
331 Set<FlatNode> visited = new HashSet<FlatNode>();
333 while( !flatNodesToVisit.isEmpty() ) {
334 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
335 FlatNode fn = fnItr.next();
337 flatNodesToVisit.remove( fn );
340 if( fn.kind() == FKind.FlatCall ) {
341 FlatCall fc = (FlatCall) fn;
342 MethodDescriptor mdCallee = fc.getMethod();
343 Set reachable = new HashSet();
345 reachable.add( mdCallee );
346 reachable.addAll( callGraph.getAllMethods( mdCallee ) );
347 reachable.retainAll( methodsContainingSESEs );
349 if( !reachable.isEmpty() ) {
350 hasChildrenByCall = true;
352 Set reachableSESEMethodSet =
353 callGraph.getFirstReachableMethodContainingSESE( mdCallee, methodsContainingSESEs );
355 reachableSESEMethodSet.add( mdCallee );
356 reachableSESEMethodSet.retainAll( methodsContainingSESEs );
358 for( Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext(); ) {
359 MethodDescriptor md = (MethodDescriptor) iterator.next();
360 Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get( md );
361 if( seseSet != null ) {
362 fsen.addChildren( seseSet );
363 for( Iterator iterator2 = seseSet.iterator(); iterator2.hasNext(); ) {
364 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
365 child.addParent( fsen );
372 if( fn == fsen.getFlatExit() ) {
373 // don't enqueue any futher nodes
377 for( int i = 0; i < fn.numNext(); i++ ) {
378 FlatNode nn = fn.getNext( i );
380 if( !visited.contains( nn ) ) {
381 flatNodesToVisit.add( nn );
386 return hasChildrenByCall;
391 protected void findPossibleExecutingRBlocksAndStallSites() {
392 for( Iterator<FlatSESEEnterNode> fsenItr = allSESEs.iterator(); fsenItr.hasNext(); ) {
393 FlatSESEEnterNode fsen = fsenItr.next();
395 // walk the program points, including across method calls, reachable within
396 // this sese/rblock/task and mark that this rblock might be executing.
397 // Important: skip the body of child rblocks, BUT DO mark the child ENTER
398 // and EXIT flat nodes as the parent being the current executing rblock!
399 Hashtable<FlatNode, FlatMethod> flatNodesToVisit =
400 new Hashtable<FlatNode, FlatMethod>();
402 for( int i = 0; i < fsen.numNext(); i++ ) {
403 FlatNode nn = fsen.getNext( i );
404 flatNodesToVisit.put( nn, fsen.getfmEnclosing() );
405 mergeIsPotentialStallSite( nn, false );
408 Set<FlatNode> visited = new HashSet<FlatNode>();
410 while( !flatNodesToVisit.isEmpty() ) {
411 Map.Entry me = (Map.Entry) flatNodesToVisit.entrySet().iterator().next();
412 FlatNode fn = (FlatNode) me.getKey();
413 FlatMethod fm = (FlatMethod) me.getValue();
415 flatNodesToVisit.remove( fn );
419 // the "is potential stall site" strategy is to propagate
420 // "false" from the beginning of a task until you hit a
421 // child, then from the child's exit propagate "true" for
422 // the parent statements after children. When you pull a node
423 // out of the bag for traversal and it happens to be an
424 // enter or an exit node, fix the dumb propagation that
425 // your IR predecessor pushed on you
426 Boolean isPotentialStallSite = isPotentialStallSite( fn );
428 if( fn instanceof FlatSESEEnterNode ||
429 fn instanceof FlatSESEExitNode ) {
430 // fix it so this is never a potential stall site, but from
431 // a child definition onward propagate 'true'
432 setIsPotentialStallSite( fn, false );
433 isPotentialStallSite = true;
437 if( fn == fsen.getFlatExit() ) {
438 // don't enqueue any futher nodes when you find your exit,
439 // NOR mark your own flat as a statement you are currently
440 // executing, your parent(s) will mark it
445 // the purpose of this traversal is to find program
446 // points where rblock 'fsen' might be executing
447 addPossibleExecutingRBlock( fn, fsen );
450 if( fn instanceof FlatSESEEnterNode ) {
451 // don't visit internal nodes of child,
452 // just enqueue the exit node
453 FlatSESEEnterNode child = (FlatSESEEnterNode) fn;
454 assert fsen.getChildren().contains( child );
455 assert child.getParents().contains( fsen );
456 flatNodesToVisit.put( child.getFlatExit(), fm );
458 // explicitly do this to handle the case that you
459 // should mark yourself as possibly executing at
460 // your own exit, because one instance can
461 // recursively invoke another
462 addPossibleExecutingRBlock( child.getFlatExit(), fsen );
467 if( fn instanceof FlatCall ) {
468 // start visiting nodes in other contexts
469 FlatCall fc = (FlatCall) fn;
470 MethodDescriptor mdCallee = fc.getMethod();
472 Set<MethodDescriptor> implementations = new HashSet<MethodDescriptor>();
474 if( mdCallee.isStatic() ) {
475 implementations.add( mdCallee );
477 TypeDescriptor typeDesc = fc.getThis().getType();
478 implementations.addAll( callGraph.getMethods( mdCallee, typeDesc ) );
481 for( Iterator imps = implementations.iterator(); imps.hasNext(); ) {
482 MethodDescriptor mdImp = (MethodDescriptor) imps.next();
483 FlatMethod fmImp = state.getMethodFlat( mdImp );
484 flatNodesToVisit.put( fmImp, fmImp );
486 // propagate your IR graph predecessor's stall site potential
487 mergeIsPotentialStallSite( fmImp, isPotentialStallSite );
489 // don't 'continue' out of this loop, also enqueue
490 // flat nodes that flow in the current method context
493 // otherwise keep visiting nodes in same context
494 for( int i = 0; i < fn.numNext(); i++ ) {
495 FlatNode nn = fn.getNext( i );
497 if( !visited.contains( nn ) ) {
498 flatNodesToVisit.put( nn, fm );
500 // propagate your IR graph predecessor's stall site potential
501 mergeIsPotentialStallSite( nn, isPotentialStallSite );
510 protected void addPossibleExecutingRBlock( FlatNode fn,
511 FlatSESEEnterNode fsen ) {
513 Set<FlatSESEEnterNode> currentSESEs = fn2currentSESEs.get( fn );
514 if( currentSESEs == null ) {
515 currentSESEs = new HashSet<FlatSESEEnterNode>();
518 currentSESEs.add( fsen );
519 fn2currentSESEs.put( fn, currentSESEs );
523 // definitively set whether a statement is a potential stall site
524 // such as a task exit is FALSE and the statement following an exit
526 protected void setIsPotentialStallSite( FlatNode fn,
528 fn2isPotentialStallSite.put( fn, ipss );
532 // Use this to OR the previous result with a new result
533 protected void mergeIsPotentialStallSite( FlatNode fn,
535 Boolean ipssPrev = isPotentialStallSite( fn );
536 setIsPotentialStallSite( fn, ipssPrev || ipss );
543 /////////////////////////////////////////////////
545 /////////////////////////////////////////////////
546 protected void debugPrintPotentialStallSites(Set<MethodDescriptor> descriptorsToAnalyze) {
547 Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
548 while (mdItr.hasNext()) {
549 FlatMethod fm = state.getMethodFlat(mdItr.next());
555 protected void printStatusMap(FlatMethod fm) {
557 System.out.println("\n\n=== "+fm+" ===");
559 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
560 flatNodesToVisit.add(fm);
562 Set<FlatNode> visited = new HashSet<FlatNode>();
564 while (!flatNodesToVisit.isEmpty()) {
565 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
566 FlatNode fn = fnItr.next();
568 flatNodesToVisit.remove(fn);
571 System.out.println(fn+"[["+isPotentialStallSite(fn)+"]]");
573 for (int i = 0; i < fn.numNext(); i++) {
574 FlatNode nn = fn.getNext(i);
576 if (!visited.contains(nn)) {
577 flatNodesToVisit.add(nn);