1 package Analysis.OoOJava;
5 import IR.MethodDescriptor;
6 import IR.TypeDescriptor;
9 import Analysis.CallGraph.CallGraph;
13 // This analysis finds all reachable rblocks in the
14 // program and computes parent/child relations
15 // between those rblocks
18 // There is a distict between parent/child and
19 // local parent/local child! "Local" means defined
20 // and nested within a single method context.
21 // Otherwise, SESE/rblocks/tasks may have many
22 // parents and many non-method-context-local
23 // children considering the call graph
25 // Also this analysis should identify "critical regions"
26 // in the context of interprocedural sese/rblock/task relations
27 // where a statement may conflict with some previously executing
28 // child task, even if it is in another method context.
42 // void doSomething( Foo f ) {
43 // f.z++; <-------- These two statements are in the critical
44 // f.z--; <-------- region of 'a' after 'c1' and before 'c2'
51 public class RBlockRelationAnalysis {
58 // an implicit SESE is automatically spliced into
59 // the IR graph around the C main before this analysis--it
60 // is nothing special except that we can make assumptions
61 // about it, such as the whole program ends when it ends
62 protected FlatSESEEnterNode mainSESE;
64 // this is a special task object, it is not in any IR graph
65 // and it does not appear to have any children or parents.
66 // It is a stand-in for whichever task is running when a
67 // method context starts such that intraprocedural task
68 // analyses have one static name for "the task who invoked
69 // this method" to attach facts to. It GREATLY simplifies
70 // the OoOJava variable analysis, for instance
71 protected FlatSESEEnterNode callerProxySESE;
73 // simply the set of every reachable SESE in the program
74 protected Set<FlatSESEEnterNode> allSESEs;
76 // to support calculation of leaf SESEs (no children even
77 // through method calls) for optimization during code gen
78 protected Set<MethodDescriptor> methodsContainingSESEs;
80 // maps method descriptor to SESE defined inside of it
81 // only contains local root SESE definitions in corresponding method
82 // (has no parent in the local method context)
83 protected Hashtable< MethodDescriptor, Set<FlatSESEEnterNode> > md2localRootSESEs;
85 // the set of every local root SESE in the program (SESE that
86 // has no parent in the local method context)
87 protected Set<FlatSESEEnterNode> allLocalRootSESEs;
89 // if you want to know which rblocks might be executing a given flat
90 // node it will be in this set
91 protected Hashtable< FlatNode, Set<FlatSESEEnterNode> > fn2currentSESEs;
93 // if you want to know which rblocks might be TRANSITIVELY executing
94 // a given flat node it will be in this set
95 protected Hashtable< FlatNode, Set<FlatSESEEnterNode> > fn2allSESEs;
97 // if you want to know the method-local, inner-most nested task that
98 // is executing a flat node, it is either here or null.
103 // bar(); <-- here 'a' is the localInnerSESE
106 // baz(); <-- here there is no locally-defined SESE, would be null
108 protected Hashtable<FlatNode, FlatSESEEnterNode> fn2localInnerSESE;
110 // indicates whether this statement might occur in a task and
111 // after some child task definition such that, without looking at
112 // the flat node itself, the parent might have to stall for child
113 protected Hashtable<FlatNode, Boolean> fn2isPotentialStallSite;
115 HashMap<MethodDescriptor, Set<Pair<FlatCall, MethodDescriptor>>> methodmap=
116 new HashMap<MethodDescriptor, Set<Pair<FlatCall, MethodDescriptor>>>();
120 ////////////////////////
122 ////////////////////////
123 public FlatSESEEnterNode getMainSESE() {
127 public Set<FlatSESEEnterNode> getAllSESEs() {
131 public Set<FlatSESEEnterNode> getLocalRootSESEs() {
132 return allLocalRootSESEs;
135 public Set<FlatSESEEnterNode> getLocalRootSESEs(FlatMethod fm) {
136 Set<FlatSESEEnterNode> out = md2localRootSESEs.get(fm);
138 out = new HashSet<FlatSESEEnterNode>();
143 public Set<MethodDescriptor> getMethodsWithSESEs() {
144 return methodsContainingSESEs;
147 /* Returns all SESE's that this fn can be a member of
150 public Set<FlatSESEEnterNode> getTransitiveExecutingRBlocks(FlatNode fn) {
151 if (fn2allSESEs.containsKey(fn))
152 return fn2allSESEs.get(fn);
154 //Compute and memoize result
155 HashSet<FlatSESEEnterNode> seseSet=new HashSet<FlatSESEEnterNode>();
156 fn2allSESEs.put(fn, seseSet);
157 Stack<FlatNode> toprocess=new Stack<FlatNode>();
159 while(!toprocess.isEmpty()) {
160 FlatNode curr=toprocess.pop();
161 Set<FlatSESEEnterNode> callers=fn2currentSESEs.get(curr);
163 for(FlatSESEEnterNode sese : callers) {
164 if (!seseSet.contains(sese)) {
174 public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks(FlatNode fn) {
175 Set<FlatSESEEnterNode> out = fn2currentSESEs.get(fn);
177 out = new HashSet<FlatSESEEnterNode>();
182 public FlatSESEEnterNode getLocalInnerRBlock(FlatNode fn) {
183 return fn2localInnerSESE.get(fn);
186 // the "caller proxy" is a static name for whichever
187 // task invoked the current method context. It is very
188 // convenient to know this is ALWAYS a different instance
189 // of any task defined within the current method context,
190 // and so using its name simplifies many intraprocedural
192 public FlatSESEEnterNode getCallerProxySESE() {
193 return callerProxySESE;
196 public boolean isPotentialStallSite(FlatNode fn) {
197 Boolean ipss = fn2isPotentialStallSite.get(fn);
205 public RBlockRelationAnalysis(State state,
207 CallGraph callGraph) {
209 this.typeUtil = typeUtil;
210 this.callGraph = callGraph;
212 callerProxySESE = new FlatSESEEnterNode(null);
213 callerProxySESE.setIsCallerProxySESE();
215 allSESEs = new HashSet<FlatSESEEnterNode>();
216 allLocalRootSESEs = new HashSet<FlatSESEEnterNode>();
217 methodsContainingSESEs = new HashSet<MethodDescriptor>();
218 md2localRootSESEs = new Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>>();
219 fn2currentSESEs = new Hashtable<FlatNode, Set<FlatSESEEnterNode>>();
220 fn2localInnerSESE = new Hashtable<FlatNode, FlatSESEEnterNode>();
221 fn2isPotentialStallSite = new Hashtable<FlatNode, Boolean>();
222 fn2allSESEs = new Hashtable< FlatNode, Set<FlatSESEEnterNode>>();
225 MethodDescriptor mdSourceEntry = typeUtil.getMain();
226 FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
228 mainSESE = (FlatSESEEnterNode) fmMain.getNext(0);
229 mainSESE.setfmEnclosing(fmMain);
230 mainSESE.setmdEnclosing(fmMain.getMethod() );
231 mainSESE.setcdEnclosing(fmMain.getMethod().getClassDesc() );
234 // add all methods transitively reachable from the
235 // source's main to set to find rblocks
236 Set<MethodDescriptor> descriptorsToAnalyze =
237 callGraph.getAllMethods(mdSourceEntry);
239 descriptorsToAnalyze.add(mdSourceEntry);
241 findRblocksAndLocalParentChildRelations(descriptorsToAnalyze);
243 findTransitiveParentChildRelations();
245 findPossibleExecutingRBlocksAndStallSites();
248 // Uncomment this phase to debug the marking of potential
249 // stall sites for parents between/after children tasks.
250 // After this debug thing runs in calls System.exit()
251 // debugPrintPotentialStallSites( descriptorsToAnalyze );
257 protected void findRblocksAndLocalParentChildRelations(Set<MethodDescriptor> descriptorsToAnalyze) {
259 Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
260 while( mdItr.hasNext() ) {
261 FlatMethod fm = state.getMethodFlat(mdItr.next() );
263 // start from flat method top, visit every node in
264 // method exactly once, find SESE stack on every
265 // control path: this will discover every reachable
266 // SESE in the program, and define the local parent
267 // and local children relations
268 Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
269 new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
271 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
272 flatNodesToVisit.add(fm);
274 Set<FlatNode> visited = new HashSet<FlatNode>();
276 Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
277 seseStacks.put(fm, seseStackFirst);
279 while( !flatNodesToVisit.isEmpty() ) {
280 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
281 FlatNode fn = fnItr.next();
283 Stack<FlatSESEEnterNode> seseStack = seseStacks.get(fn);
284 assert seseStack != null;
286 flatNodesToVisit.remove(fn);
289 if( !seseStack.isEmpty() ) {
290 fn2localInnerSESE.put(fn, seseStack.peek() );
293 nodeActions(fn, seseStack, fm);
295 for( int i = 0; i < fn.numNext(); i++ ) {
296 FlatNode nn = fn.getNext(i);
298 if( !visited.contains(nn) ) {
299 flatNodesToVisit.add(nn);
301 // clone stack and send along each control path
302 seseStacks.put(nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
309 protected void nodeActions(FlatNode fn,
310 Stack<FlatSESEEnterNode> seseStack,
312 switch( fn.kind() ) {
314 case FKind.FlatSESEEnterNode: {
315 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
318 methodsContainingSESEs.add(fm.getMethod() );
320 fsen.setfmEnclosing(fm);
321 fsen.setmdEnclosing(fm.getMethod() );
322 fsen.setcdEnclosing(fm.getMethod().getClassDesc() );
324 if( seseStack.empty() ) {
326 fsen.setLocalParent(null);
328 allLocalRootSESEs.add(fsen);
330 Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get(fm.getMethod() );
331 if( seseSet == null ) {
332 seseSet = new HashSet<FlatSESEEnterNode>();
335 md2localRootSESEs.put(fm.getMethod(), seseSet);
338 // otherwise a local parent/child relation
339 // which is also the broader parent/child
341 seseStack.peek().addLocalChild(fsen);
342 fsen.setLocalParent(seseStack.peek() );
344 seseStack.peek().addChild(fsen);
345 fsen.addParent(seseStack.peek() );
348 seseStack.push(fsen);
351 case FKind.FlatSESEExitNode: {
352 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
353 assert !seseStack.empty();
354 FlatSESEEnterNode fsen = seseStack.pop();
357 case FKind.FlatReturnNode: {
358 FlatReturnNode frn = (FlatReturnNode) fn;
359 if( !seseStack.empty() ) {
360 throw new Error("Error: return statement enclosed within SESE "+
361 seseStack.peek().getPrettyIdentifier() );
370 protected void findTransitiveParentChildRelations() {
372 for (Iterator<FlatSESEEnterNode> itr = allSESEs.iterator(); itr.hasNext(); ) {
373 FlatSESEEnterNode fsen = itr.next();
375 boolean hasNoNestedChildren = fsen.getLocalChildren().isEmpty();
376 boolean hasNoChildrenByCall = !hasChildrenByCall(fsen);
378 fsen.setIsLeafSESE(hasNoNestedChildren && hasNoChildrenByCall);
382 protected boolean hasChildrenByCall(FlatSESEEnterNode fsen) {
384 boolean hasChildrenByCall = false;
386 // visit every flat node in SESE body, find method calls that
387 // may transitively call methods with SESEs enclosed
388 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
389 flatNodesToVisit.add(fsen);
391 Set<FlatNode> visited = new HashSet<FlatNode>();
393 while( !flatNodesToVisit.isEmpty() ) {
394 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
395 FlatNode fn = fnItr.next();
397 flatNodesToVisit.remove(fn);
400 if( fn.kind() == FKind.FlatCall ) {
401 FlatCall fc = (FlatCall) fn;
402 MethodDescriptor mdCallee = fc.getMethod();
403 Set reachable = new HashSet();
405 reachable.add(mdCallee);
406 reachable.addAll(callGraph.getAllMethods(mdCallee) );
407 reachable.retainAll(methodsContainingSESEs);
409 if( !reachable.isEmpty() ) {
410 hasChildrenByCall = true;
412 Set reachableSESEMethodSet =
413 callGraph.getFirstReachableMethodContainingSESE(mdCallee, methodsContainingSESEs);
415 reachableSESEMethodSet.add(mdCallee);
416 reachableSESEMethodSet.retainAll(methodsContainingSESEs);
418 for( Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext(); ) {
419 MethodDescriptor md = (MethodDescriptor) iterator.next();
420 Set<FlatSESEEnterNode> seseSet = md2localRootSESEs.get(md);
421 if( seseSet != null ) {
422 fsen.addChildren(seseSet);
423 for( Iterator iterator2 = seseSet.iterator(); iterator2.hasNext(); ) {
424 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
425 child.addParent(fsen);
432 if( fn == fsen.getFlatExit() ) {
433 // don't enqueue any futher nodes
437 for( int i = 0; i < fn.numNext(); i++ ) {
438 FlatNode nn = fn.getNext(i);
440 if( !visited.contains(nn) ) {
441 flatNodesToVisit.add(nn);
446 return hasChildrenByCall;
449 protected void findPossibleExecutingRBlocksAndStallSites() {
450 for( Iterator<FlatSESEEnterNode> fsenItr = allSESEs.iterator(); fsenItr.hasNext(); ) {
451 FlatSESEEnterNode fsen = fsenItr.next();
453 // walk the program points, including across method calls, reachable within
454 // this sese/rblock/task and mark that this rblock might be executing.
455 // Important: skip the body of child rblocks, BUT DO mark the child ENTER
456 // and EXIT flat nodes as the parent being the current executing rblock!
457 Hashtable<FlatNode, FlatMethod> flatNodesToVisit =
458 new Hashtable<FlatNode, FlatMethod>();
460 for( int i = 0; i < fsen.numNext(); i++ ) {
461 FlatNode nn = fsen.getNext(i);
462 flatNodesToVisit.put(nn, fsen.getfmEnclosing() );
465 Set<FlatNode> visited = new HashSet<FlatNode>();
467 while (!flatNodesToVisit.isEmpty()) {
468 Map.Entry me = (Map.Entry)flatNodesToVisit.entrySet().iterator().next();
469 FlatNode fn = (FlatNode) me.getKey();
470 FlatMethod fm = (FlatMethod) me.getValue();
472 flatNodesToVisit.remove(fn);
475 // the "is potential stall site" strategy is to propagate
476 // "false" from the beginning of a task until you hit a
477 // child, then from the child's exit propagate "true" for
478 // the parent statements after children. When you pull a node
479 // out of the bag for traversal and it happens to be an
480 // enter or an exit node, fix the dumb propagation that
481 // your IR predecessor pushed on you
482 Boolean isPotentialStallSite = isPotentialStallSite(fn);
484 if (fn == fsen.getFlatExit()) {
485 // don't enqueue any further nodes when you find your exit,
486 // NOR mark your own flat as a statement you are currently
487 // executing, your parent(s) will mark it
491 if (fn instanceof FlatSESEExitNode) {
492 setIsPotentialStallSite(fn, false);
493 isPotentialStallSite = true;
496 // the purpose of this traversal is to find program
497 // points where rblock 'fsen' might be executing
498 addPossibleExecutingRBlock(fn, fsen);
500 if (fn instanceof FlatSESEEnterNode) {
501 // don't visit internal nodes of child,
502 // just enqueue the exit node
503 FlatSESEEnterNode child = (FlatSESEEnterNode) fn;
504 assert fsen.getChildren().contains(child);
505 assert child.getParents().contains(fsen);
506 flatNodesToVisit.put(child.getFlatExit(), fm);
507 setIsPotentialStallSite(fn, false);
509 // explicitly do this to handle the case that you
510 // should mark yourself as possibly executing at
511 // your own exit, because one instance can
512 // recursively invoke another
513 addPossibleExecutingRBlock(child.getFlatExit(), fsen);
518 // if previous flat nodes have any changes,,
519 // propagate predecessor's status of stall site potential
521 if (fn instanceof FlatCall) {
523 // start visiting nodes in other contexts
524 FlatCall fc = (FlatCall) fn;
525 MethodDescriptor mdCallee = fc.getMethod();
527 Set<MethodDescriptor> implementations = new HashSet<MethodDescriptor>();
529 if (mdCallee.isStatic()) {
530 implementations.add(mdCallee);
532 TypeDescriptor typeDesc = fc.getThis().getType();
533 implementations.addAll(callGraph.getMethods(mdCallee, typeDesc));
536 for (Iterator imps = implementations.iterator(); imps.hasNext(); ) {
537 MethodDescriptor mdImp = (MethodDescriptor) imps.next();
538 FlatMethod fmImp = state.getMethodFlat(mdImp);
540 // keep mapping from fc's md to <fc,caller's md>
541 // later, when return node of callee becomes a potential stall site,
542 // following flat nodes of fc should be re-analyzied
543 if(!methodmap.containsKey(fmImp)) {
544 methodmap.put(mdImp, new HashSet<Pair<FlatCall,MethodDescriptor>>());
546 methodmap.get(mdImp).add(new Pair<FlatCall,MethodDescriptor>(fc,fm.getMethod()));
548 if ((isPotentialStallSite && !isPotentialStallSite(fmImp)) || !visited.contains(fmImp)) {
549 flatNodesToVisit.put(fmImp, fmImp);
551 // propagate your IR graph predecessor's stall site potential
552 mergeIsPotentialStallSite(fmImp, isPotentialStallSite);
556 // don't 'continue' out of this loop, also enqueue
557 // flat nodes that flow in the current method context
560 if (fn instanceof FlatReturnNode) {
561 // if return node is potential stall site, need to inform its caller
562 if (isPotentialStallSite) {
563 Set<Pair<FlatCall, MethodDescriptor>> callset = methodmap.get(fm.getMethod());
564 if (callset != null) {
565 for (Pair<FlatCall, MethodDescriptor> fcallpair : callset) {
566 FlatCall fcall = fcallpair.getFirst();
567 MethodDescriptor mdcaller = fcallpair.getSecond();
568 for (int i = 0; i < fcall.numNext(); i++) {
569 FlatNode nn = fcall.getNext(i);
570 if ( visited.contains(nn) && (!isPotentialStallSite(nn)) ) {
571 mergeIsPotentialStallSite(nn, isPotentialStallSite);
572 FlatMethod fmcaller = state.getMethodFlat(mdcaller);
573 flatNodesToVisit.put(nn, fmcaller);
581 // note: only when current flat node has a change on the status of potential
582 // stall site, need to visit following flat nodes
583 for (int i = 0; i < fn.numNext(); i++) {
584 FlatNode nn = fn.getNext(i);
585 if ((isPotentialStallSite && !isPotentialStallSite(nn)) || !visited.contains(nn)) {
586 flatNodesToVisit.put(nn, fm);
587 mergeIsPotentialStallSite(nn, isPotentialStallSite);
596 protected void addPossibleExecutingRBlock(FlatNode fn,
597 FlatSESEEnterNode fsen) {
599 Set<FlatSESEEnterNode> currentSESEs = fn2currentSESEs.get(fn);
600 if( currentSESEs == null ) {
601 currentSESEs = new HashSet<FlatSESEEnterNode>();
604 currentSESEs.add(fsen);
605 fn2currentSESEs.put(fn, currentSESEs);
609 // definitively set whether a statement is a potential stall site
610 // such as a task exit is FALSE and the statement following an exit
612 protected void setIsPotentialStallSite(FlatNode fn,
614 fn2isPotentialStallSite.put(fn, ipss);
618 // Use this to OR the previous result with a new result
619 protected void mergeIsPotentialStallSite(FlatNode fn,
621 Boolean ipssPrev = isPotentialStallSite(fn);
622 setIsPotentialStallSite(fn, ipssPrev || ipss);
629 /////////////////////////////////////////////////
631 /////////////////////////////////////////////////
632 protected void debugPrintPotentialStallSites(Set<MethodDescriptor> descriptorsToAnalyze) {
633 Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
634 while (mdItr.hasNext()) {
635 FlatMethod fm = state.getMethodFlat(mdItr.next());
641 protected void printStatusMap(FlatMethod fm) {
643 System.out.println("\n\n=== "+fm+" ===");
645 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
646 flatNodesToVisit.add(fm);
648 Set<FlatNode> visited = new HashSet<FlatNode>();
650 while (!flatNodesToVisit.isEmpty()) {
651 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
652 FlatNode fn = fnItr.next();
654 flatNodesToVisit.remove(fn);
657 System.out.println(fn+"[["+isPotentialStallSite(fn)+"]]");
659 for (int i = 0; i < fn.numNext(); i++) {
660 FlatNode nn = fn.getNext(i);
662 if (!visited.contains(nn)) {
663 flatNodesToVisit.add(nn);