1 package Analysis.OoOJava;
7 import Analysis.CallGraph.*;
8 import Analysis.Disjoint.*;
9 import Analysis.Pointer.*;
14 public class OoOJavaAnalysis {
16 // data from the compiler
18 private TypeUtil typeUtil;
19 private CallGraph callGraph;
20 private RBlockRelationAnalysis rblockRel;
21 private HeapAnalysis disjointAnalysisTaints;
22 private DisjointAnalysis disjointAnalysisReach;
23 private BuildStateMachines buildStateMachines;
25 private Set<MethodDescriptor> descriptorsToAnalyze;
27 private Hashtable<FlatNode, Set<TempDescriptor>> livenessGlobalView;
28 private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
29 private Hashtable<FlatNode, VarSrcTokTable> variableResults;
30 private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
31 private Hashtable<FlatNode, CodePlan> codePlans;
33 private Hashtable<FlatSESEEnterNode, Set<TempDescriptor>> notAvailableIntoSESE;
35 private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
37 private Hashtable<FlatNode, ContextTaskNames> fn2contextTaskNames;
39 // get the flat method that contains any given flat node
40 private Hashtable<FlatNode, FlatMethod> fn2fm;
42 // temporal data structures to track analysis progress.
43 static private int uniqueLockSetId = 0;
44 // mapping of a conflict graph to its compiled lock
45 private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraph2SESELock;
46 // mapping of a sese block to its conflict graph
47 private Hashtable<FlatNode, ConflictGraph> sese2conflictGraph;
49 public static int maxSESEage = -1;
51 public int getMaxSESEage() {
56 public CodePlan getCodePlan(FlatNode fn) {
57 CodePlan cp = codePlans.get(fn);
61 public Set<FlatNode> getNodesWithPlans() {
62 return codePlans.keySet();
65 public ContextTaskNames getContextTaskNames( FlatMethod fm ) {
66 ContextTaskNames out = fn2contextTaskNames.get( fm );
68 out = new ContextTaskNames();
73 public ContextTaskNames getContextTaskNames( FlatSESEEnterNode fsen ) {
74 ContextTaskNames out = fn2contextTaskNames.get( fsen );
76 out = new ContextTaskNames();
81 public FlatMethod getContainingFlatMethod( FlatNode fn ) {
82 FlatMethod fm = fn2fm.get( fn );
87 public HeapAnalysis getDisjointAnalysis() {
88 return disjointAnalysisTaints;
91 public OoOJavaAnalysis( State state,
95 ArrayReferencees arrayReferencees ) {
97 double timeStartAnalysis = (double) System.nanoTime();
100 this.typeUtil = typeUtil;
101 this.callGraph = callGraph;
102 this.maxSESEage = state.OOO_MAXSESEAGE;
104 livenessGlobalView = new Hashtable<FlatNode, Set<TempDescriptor>>();
105 livenessVirtualReads = new Hashtable<FlatNode, Set<TempDescriptor>>();
106 variableResults = new Hashtable<FlatNode, VarSrcTokTable>();
107 notAvailableResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
108 codePlans = new Hashtable<FlatNode, CodePlan>();
109 wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
110 notAvailableIntoSESE = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
111 sese2conflictGraph = new Hashtable<FlatNode, ConflictGraph>();
112 conflictGraph2SESELock = new Hashtable<ConflictGraph, HashSet<SESELock>>();
113 fn2contextTaskNames = new Hashtable<FlatNode, ContextTaskNames>();
114 fn2fm = new Hashtable<FlatNode, FlatMethod>();
116 // state machines support heap examiners with
117 // state transitions to improve precision
119 buildStateMachines = new BuildStateMachines();
122 // add all methods transitively reachable from the
123 // source's main to set for analysis
124 MethodDescriptor mdSourceEntry = typeUtil.getMain();
125 FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
127 descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
129 descriptorsToAnalyze.add(mdSourceEntry);
131 // 0th pass, setup a useful mapping of any flat node to the
132 // flat method it is a part of
133 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
134 while (methItr.hasNext()) {
135 Descriptor d = methItr.next();
136 FlatMethod fm = state.getMethodFlat( d );
137 buildFlatNodeToFlatMethod( fm );
140 // 1st pass, find basic rblock relations & potential stall sites
141 rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
142 VarSrcTokTable.rblockRel = rblockRel;
144 // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
145 methItr = descriptorsToAnalyze.iterator();
146 while (methItr.hasNext()) {
147 Descriptor d = methItr.next();
148 FlatMethod fm = state.getMethodFlat(d);
150 // note we can't use the general liveness analysis already in
151 // the compiler because this analysis is task-aware
152 livenessAnalysisBackward(fm);
155 // 3rd pass, variable analysis
156 methItr = descriptorsToAnalyze.iterator();
157 while (methItr.hasNext()) {
158 Descriptor d = methItr.next();
159 FlatMethod fm = state.getMethodFlat(d);
161 // starting from roots do a forward, fixed-point
162 // variable analysis for refinement and stalls
163 variableAnalysisForward(fm);
166 // 4th pass, compute liveness contribution from
167 // virtual reads discovered in variable pass
168 methItr = descriptorsToAnalyze.iterator();
169 while (methItr.hasNext()) {
170 Descriptor d = methItr.next();
171 FlatMethod fm = state.getMethodFlat(d);
172 livenessAnalysisBackward(fm);
175 // 5th pass, use disjointness with NO FLAGGED REGIONS
176 // to compute taints and effects
178 disjointAnalysisTaints = new Pointer(state, typeUtil, callGraph, rblockRel);
179 ((Pointer)disjointAnalysisTaints).doAnalysis();
181 disjointAnalysisTaints =
182 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null,
183 rblockRel, buildStateMachines,
184 true ); // suppress output--this is an intermediate pass
186 // 6th pass, not available analysis FOR VARIABLES!
187 methItr = descriptorsToAnalyze.iterator();
188 while (methItr.hasNext()) {
189 Descriptor d = methItr.next();
190 FlatMethod fm = state.getMethodFlat(d);
192 // compute what is not available at every program
193 // point, in a forward fixed-point pass
194 notAvailableForward(fm);
197 // 7th pass, start conflict graphs where a parent's graph has a
198 // node for possibly conflicting children and its own stall sites
199 startConflictGraphs();
201 // 8th pass, calculate all possible conflicts without using
202 // reachability info and identify set of FlatNew that next
203 // disjoint reach. analysis should flag
204 Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
205 calculateConflicts(sitesToFlag, false);
208 // 9th pass, ask disjoint analysis to compute reachability
209 // for objects that may cause heap conflicts so the most
210 // efficient method to deal with conflict can be computed
212 disjointAnalysisReach =
213 new DisjointAnalysis(state, typeUtil, callGraph, liveness,
214 arrayReferencees, sitesToFlag,
215 null, // don't do effects analysis again!
216 null, // no BuildStateMachines needed
217 false // don't suppress progress output
220 // 10th pass, calculate conflicts with reachability info
221 calculateConflicts(null, true);
224 // in RCR/DFJ we want to do some extra processing on the
225 // state machines before they get handed off to code gen,
226 // and we're doing the same effect-conflict traversal needed
227 // to identify heap examiners that are weakly connected, so
228 // accomplish both at the same time
229 pruneMachinesAndFindWeaklyConnectedExaminers();
232 // 11th pass, compiling memory Qs! The name "lock" is a legacy
233 // term for the heap dependence queue, or memQ as the runtime calls it
236 // 12th pass, compute a plan for code injections
237 methItr = descriptorsToAnalyze.iterator();
238 while (methItr.hasNext()) {
239 Descriptor d = methItr.next();
240 FlatMethod fm = state.getMethodFlat(d);
241 codePlansForward(fm);
245 // splice new IR nodes into graph after all
246 // analysis passes are complete
247 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
248 while (spliceItr.hasNext()) {
249 Map.Entry me = (Map.Entry) spliceItr.next();
250 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
251 fwdvn.spliceIntoIR();
255 if (state.OOODEBUG) {
258 disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt");
259 writeConflictGraph();
260 } catch (IOException e) {}
266 private void buildFlatNodeToFlatMethod( FlatMethod fm ) {
267 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
268 flatNodesToVisit.add( fm );
270 Set<FlatNode> flatNodesVisited = new HashSet<FlatNode>();
272 while( !flatNodesToVisit.isEmpty() ) {
273 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
274 flatNodesToVisit.remove( fn );
275 flatNodesVisited.add( fn );
279 for( int i = 0; i < fn.numNext(); i++ ) {
280 FlatNode nn = fn.getNext( i );
281 if( !flatNodesVisited.contains( nn ) ) {
282 flatNodesToVisit.add( nn );
291 * Iterator iter = sese2conflictGraph.entrySet().iterator(); while
292 * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn =
293 * (FlatNode) e.getKey(); ConflictGraph conflictGraph = (ConflictGraph)
295 * System.out.println("---------------------------------------");
296 * System.out.println("CONFLICT GRAPH for " + fn); Set<String> keySet =
297 * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator();
298 * iterator.hasNext();) { String key = (String) iterator.next();
299 * ConflictNode node = conflictGraph.id2cn.get(key);
300 * System.out.println("key=" + key + " \n" + node.toStringAllEffects()); } }
306 private void writeFile(Set<FlatNew> sitesToFlag) {
309 BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt"));
311 for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext();) {
312 FlatNew fn = (FlatNew) iterator.next();
316 } catch (IOException e) {
323 private void livenessAnalysisBackward(FlatMethod fm) {
325 // flow backward across nodes to compute liveness, and
326 // take special care with sese enter/exit nodes that
327 // alter this from normal liveness analysis
328 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
329 flatNodesToVisit.add( fm.getFlatExit() );
331 while( !flatNodesToVisit.isEmpty() ) {
332 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
333 flatNodesToVisit.remove( fn );
335 Set<TempDescriptor> prev = livenessGlobalView.get( fn );
337 // merge sets from control flow joins
338 Set<TempDescriptor> livein = new HashSet<TempDescriptor>();
339 for (int i = 0; i < fn.numNext(); i++) {
340 FlatNode nn = fn.getNext( i );
341 Set<TempDescriptor> s = livenessGlobalView.get( nn );
347 Set<TempDescriptor> curr = liveness_nodeActions( fn, livein );
349 // if a new result, schedule backward nodes for analysis
350 if( !curr.equals( prev ) ) {
351 livenessGlobalView.put( fn, curr );
353 for( int i = 0; i < fn.numPrev(); i++ ) {
354 FlatNode nn = fn.getPrev( i );
355 flatNodesToVisit.add( nn );
361 private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
362 Set<TempDescriptor> liveIn
364 switch( fn.kind() ) {
366 case FKind.FlatSESEEnterNode: {
367 // add whatever is live-in at a task enter to that
369 FlatSESEEnterNode fsen = (FlatSESEEnterNode)fn;
370 if( liveIn != null ) {
371 fsen.addInVarSet( liveIn );
373 // no break, should also execute default actions
377 // handle effects of statement in reverse, writes then reads
378 TempDescriptor[] writeTemps = fn.writesTemps();
379 for( int i = 0; i < writeTemps.length; ++i ) {
380 liveIn.remove( writeTemps[i] );
382 // if we are analyzing code declared directly in a task,
383 FlatSESEEnterNode fsen = rblockRel.getLocalInnerRBlock( fn );
385 // check to see if we are writing to variables that will
386 // be live-out at the task's exit (and therefore should
387 // go in the task's out-var set)
388 FlatSESEExitNode fsexn = fsen.getFlatExit();
389 Set<TempDescriptor> livetemps = livenessGlobalView.get( fsexn );
390 if( livetemps != null && livetemps.contains( writeTemps[i] ) ) {
391 fsen.addOutVar( writeTemps[i] );
396 TempDescriptor[] readTemps = fn.readsTemps();
397 for( int i = 0; i < readTemps.length; ++i ) {
398 liveIn.add( readTemps[i] );
401 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
402 if( virtualReadTemps != null ) {
403 liveIn.addAll( virtualReadTemps );
413 private void variableAnalysisForward(FlatMethod fm) {
415 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
416 flatNodesToVisit.add(fm);
418 while (!flatNodesToVisit.isEmpty()) {
419 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
420 flatNodesToVisit.remove(fn);
422 VarSrcTokTable prev = variableResults.get(fn);
424 // merge sets from control flow joins
425 VarSrcTokTable curr = new VarSrcTokTable();
426 for (int i = 0; i < fn.numPrev(); i++) {
427 FlatNode nn = fn.getPrev(i);
428 VarSrcTokTable incoming = variableResults.get(nn);
429 curr.merge(incoming);
432 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
433 if( currentSESE == null ) {
434 currentSESE = rblockRel.getCallerProxySESE();
437 variable_nodeActions(fn, curr, currentSESE);
439 // if a new result, schedule forward nodes for analysis
440 if (!curr.equals(prev)) {
441 variableResults.put(fn, curr);
443 for (int i = 0; i < fn.numNext(); i++) {
444 FlatNode nn = fn.getNext(i);
445 flatNodesToVisit.add(nn);
451 private void variable_nodeActions(FlatNode fn,
452 VarSrcTokTable vstTable,
453 FlatSESEEnterNode currentSESE) {
457 case FKind.FlatSESEEnterNode: {
458 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
459 // ignore currently executing SESE, at this point
460 // the analysis considers a new instance is becoming
463 vstTable.assertConsistency();
467 case FKind.FlatSESEExitNode: {
468 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
470 // fsen is the child of currently executing tasks
471 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
473 // remap all of this child's children tokens to be
474 // from this child as the child exits
475 vstTable.remapChildTokens(fsen);
477 // liveness virtual reads are things that might be
478 // written by an SESE and should be added to the in-set
479 // anything virtually read by this SESE should be pruned
480 // of parent or sibling sources
481 Set<TempDescriptor> liveVars = livenessGlobalView.get(fn);
482 Set<TempDescriptor> fsenVirtReads =
483 vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen,
486 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
487 if (fsenVirtReadsOld != null) {
488 fsenVirtReads.addAll(fsenVirtReadsOld);
490 livenessVirtualReads.put(fn, fsenVirtReads);
492 // then all child out-set tokens are guaranteed
493 // to be filled in, so clobber those entries with
494 // the latest, clean sources
495 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
496 while (outVarItr.hasNext()) {
497 TempDescriptor outVar = outVarItr.next();
498 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
500 VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
501 vstTable.remove(outVar);
504 vstTable.assertConsistency();
508 case FKind.FlatOpNode: {
509 FlatOpNode fon = (FlatOpNode) fn;
511 if (fon.getOp().getOp() == Operation.ASSIGN) {
512 TempDescriptor lhs = fon.getDest();
513 TempDescriptor rhs = fon.getLeft();
515 vstTable.remove(lhs);
517 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
519 Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
520 while (itr.hasNext()) {
521 VariableSourceToken vst = itr.next();
523 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
526 // when we do x = y for variables, just copy over from a child,
527 // there are two cases:
528 // 1. if the current task is the caller proxy, any local root is a child
530 currentSESE.getIsCallerProxySESE() &&
531 rblockRel.getLocalRootSESEs().contains( vst.getSESE() );
533 // 2. if the child task is a locally-defined child of the current task
534 boolean case2 = currentSESE.getLocalChildren().contains( vst.getSESE() );
536 if( case1 || case2 ) {
537 // if the source comes from a child, copy it over
538 forAddition.add( new VariableSourceToken( ts,
545 // otherwise, stamp it as us as the source
546 forAddition.add( new VariableSourceToken( ts,
555 vstTable.addAll( forAddition );
557 // only break if this is an ASSIGN op node,
558 // otherwise fall through to default case
559 vstTable.assertConsistency();
564 // note that FlatOpNode's that aren't ASSIGN
565 // fall through to this default case
567 TempDescriptor[] writeTemps = fn.writesTemps();
568 if( writeTemps.length > 0 ) {
570 // for now, when writeTemps > 1, make sure
571 // its a call node, programmer enforce only
572 // doing stuff like calling a print routine
573 if( writeTemps.length > 1 ) {
574 assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
578 vstTable.remove( writeTemps[0] );
580 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
581 ts.add( writeTemps[0] );
583 vstTable.add( new VariableSourceToken( ts,
591 vstTable.assertConsistency();
598 private void notAvailableForward(FlatMethod fm) {
600 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
601 flatNodesToVisit.add(fm);
603 while (!flatNodesToVisit.isEmpty()) {
604 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
605 flatNodesToVisit.remove(fn);
607 Set<TempDescriptor> prev = notAvailableResults.get(fn);
609 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
610 for (int i = 0; i < fn.numPrev(); i++) {
611 FlatNode nn = fn.getPrev(i);
612 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
613 if (notAvailIn != null) {
614 curr.addAll(notAvailIn);
618 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
619 if( currentSESE == null ) {
620 currentSESE = rblockRel.getCallerProxySESE();
623 notAvailable_nodeActions(fn, curr, currentSESE);
625 // if a new result, schedule forward nodes for analysis
626 if (!curr.equals(prev)) {
627 notAvailableResults.put(fn, curr);
629 for (int i = 0; i < fn.numNext(); i++) {
630 FlatNode nn = fn.getNext(i);
631 flatNodesToVisit.add(nn);
637 private void notAvailable_nodeActions(FlatNode fn,
638 Set<TempDescriptor> notAvailSet,
639 FlatSESEEnterNode currentSESE
642 // any temps that are removed from the not available set
643 // at this node should be marked in this node's code plan
644 // as temps to be grabbed at runtime!
648 case FKind.FlatSESEEnterNode: {
649 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
651 // keep a copy of what's not available into the SESE
652 // and restore it at the matching exit node
653 Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
654 Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
655 while (tdItr.hasNext()) {
656 notAvailCopy.add(tdItr.next());
658 notAvailableIntoSESE.put(fsen, notAvailCopy);
663 case FKind.FlatSESEExitNode: {
664 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
665 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
667 notAvailSet.addAll(fsen.getOutVarSet());
669 Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
670 assert notAvailIn != null;
671 notAvailSet.addAll(notAvailIn);
674 case FKind.FlatMethod: {
678 case FKind.FlatOpNode: {
679 FlatOpNode fon = (FlatOpNode) fn;
681 if (fon.getOp().getOp() == Operation.ASSIGN) {
682 TempDescriptor lhs = fon.getDest();
683 TempDescriptor rhs = fon.getLeft();
685 // copy makes lhs same availability as rhs
686 if (notAvailSet.contains(rhs)) {
687 notAvailSet.add(lhs);
689 notAvailSet.remove(lhs);
692 // only break if this is an ASSIGN op node,
693 // otherwise fall through to default case
698 // note that FlatOpNode's that aren't ASSIGN
699 // fall through to this default case
701 TempDescriptor[] writeTemps = fn.writesTemps();
702 for (int i = 0; i < writeTemps.length; i++) {
703 TempDescriptor wTemp = writeTemps[i];
704 notAvailSet.remove(wTemp);
706 TempDescriptor[] readTemps = fn.readsTemps();
707 for (int i = 0; i < readTemps.length; i++) {
708 TempDescriptor rTemp = readTemps[i];
709 notAvailSet.remove(rTemp);
711 // if this variable has exactly one source, potentially
712 // get other things from this source as well
713 VarSrcTokTable vstTable = variableResults.get(fn);
715 VSTWrapper vstIfStatic = new VSTWrapper();
716 Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
718 if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
720 VariableSourceToken vst = vstIfStatic.vst;
722 Iterator<VariableSourceToken> availItr =
723 vstTable.get(vst.getSESE(), vst.getAge()).iterator();
725 // look through things that are also available from same source
726 while (availItr.hasNext()) {
727 VariableSourceToken vstAlsoAvail = availItr.next();
729 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
730 while (refVarItr.hasNext()) {
731 TempDescriptor refVarAlso = refVarItr.next();
733 // if a variable is available from the same source, AND it ALSO
734 // only comes from one statically known source, mark it available
735 VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
736 Integer srcTypeAlso =
737 vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed);
738 if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
739 notAvailSet.remove(refVarAlso);
751 private void codePlansForward(FlatMethod fm) {
753 // start from flat method top, visit every node in
754 // method exactly once
755 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
756 flatNodesToVisit.add(fm);
758 Set<FlatNode> visited = new HashSet<FlatNode>();
760 while (!flatNodesToVisit.isEmpty()) {
761 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
762 FlatNode fn = fnItr.next();
764 flatNodesToVisit.remove(fn);
767 // use incoming results as "dot statement" or just
768 // before the current statement
769 VarSrcTokTable dotSTtable = new VarSrcTokTable();
770 for (int i = 0; i < fn.numPrev(); i++) {
771 FlatNode nn = fn.getPrev(i);
772 dotSTtable.merge(variableResults.get(nn));
775 // find dt-st notAvailableSet also
776 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
777 for (int i = 0; i < fn.numPrev(); i++) {
778 FlatNode nn = fn.getPrev(i);
779 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
780 if (notAvailIn != null) {
781 dotSTnotAvailSet.addAll(notAvailIn);
785 Set<TempDescriptor> dotSTlive = livenessGlobalView.get(fn);
787 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
788 if( currentSESE == null ) {
789 currentSESE = rblockRel.getCallerProxySESE();
792 codePlans_nodeActions(fm, fn,
793 dotSTlive, dotSTtable, dotSTnotAvailSet,
796 for (int i = 0; i < fn.numNext(); i++) {
797 FlatNode nn = fn.getNext(i);
799 if (!visited.contains(nn)) {
800 flatNodesToVisit.add(nn);
806 private void codePlans_nodeActions(FlatMethod fm,
808 Set<TempDescriptor> liveSetIn,
809 VarSrcTokTable vstTableIn,
810 Set<TempDescriptor> notAvailSetIn,
811 FlatSESEEnterNode currentSESE) {
813 CodePlan plan = new CodePlan(currentSESE);
817 case FKind.FlatSESEEnterNode: {
818 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
820 // track the source types of the in-var set so generated
821 // code at this SESE issue can compute the number of
822 // dependencies properly
823 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
824 while (inVarItr.hasNext()) {
825 TempDescriptor inVar = inVarItr.next();
827 // when we get to an SESE enter node we change the
828 // currentSESE variable of this analysis to the
829 // child that is declared by the enter node, so
830 // in order to classify in-vars correctly, pass
831 // the parent SESE in--at other FlatNode types just
832 // use the currentSESE
833 FlatSESEEnterNode parent = rblockRel.getLocalInnerRBlock( fn );
834 if( parent == null ) {
835 parent = rblockRel.getCallerProxySESE();
838 VSTWrapper vstIfStatic = new VSTWrapper();
839 Integer srcType = vstTableIn.getRefVarSrcType(inVar, parent, vstIfStatic);
841 // the current SESE needs a local space to track the dynamic
842 // variable and the child needs space in its SESE record
843 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
844 fsen.addDynamicInVar(inVar);
845 addDynamicVar( fsen, fm, inVar );
847 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
848 fsen.addStaticInVar(inVar);
849 VariableSourceToken vst = vstIfStatic.vst;
850 fsen.putStaticInVar2src(inVar, vst);
851 fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
853 assert srcType.equals(VarSrcTokTable.SrcType_READY);
854 fsen.addReadyInVar(inVar);
859 case FKind.FlatSESEExitNode: {
860 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
861 //TODO! Shouldn't there be a code plan for task exit
862 // where the exiting task calculates whether its own
863 // siblings need variables from its children, so the
864 // exiter should copy those variables into its own out-set
865 // and make the available?
868 case FKind.FlatOpNode: {
869 FlatOpNode fon = (FlatOpNode) fn;
871 if (fon.getOp().getOp() == Operation.ASSIGN) {
872 TempDescriptor lhs = fon.getDest();
873 TempDescriptor rhs = fon.getLeft();
875 // if this is an op node, don't stall, copy
876 // source and delay until we need to use value
878 // ask whether lhs and rhs sources are dynamic, static, etc.
879 VSTWrapper vstIfStatic = new VSTWrapper();
880 Integer lhsSrcType = vstTableIn.getRefVarSrcType(lhs, currentSESE, vstIfStatic);
881 Integer rhsSrcType = vstTableIn.getRefVarSrcType(rhs, currentSESE, vstIfStatic);
883 if (rhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
884 // if rhs is dynamic going in, lhs will definitely be dynamic
885 // going out of this node, so track that here
886 plan.addDynAssign( lhs, rhs );
887 addDynamicVar( currentSESE, fm, lhs );
888 addDynamicVar( currentSESE, fm, rhs );
890 } else if (lhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
891 // otherwise, if the lhs is dynamic, but the rhs is not, we
892 // need to update the variable's dynamic source as "current SESE"
893 plan.addDynAssign(lhs);
896 // only break if this is an ASSIGN op node,
897 // otherwise fall through to default case
902 // note that FlatOpNode's that aren't ASSIGN
903 // fall through to this default case
906 // a node with no live set has nothing to stall for
907 if (liveSetIn == null) {
911 TempDescriptor[] readarray = fn.readsTemps();
912 for (int i = 0; i < readarray.length; i++) {
913 TempDescriptor readtmp = readarray[i];
915 // ignore temps that are definitely available
916 // when considering to stall on it
917 if (!notAvailSetIn.contains(readtmp)) {
921 // check the source type of this variable
922 VSTWrapper vstIfStatic = new VSTWrapper();
923 Integer srcType = vstTableIn.getRefVarSrcType(readtmp, currentSESE, vstIfStatic);
925 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
926 // 1) It is not clear statically where this variable will
927 // come from, so dynamically we must keep track
928 // along various control paths, and therefore when we stall,
929 // just stall for the exact thing we need and move on
930 plan.addDynamicStall( readtmp );
931 addDynamicVar( currentSESE, fm, readtmp );
933 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
934 // 2) Single token/age pair: Stall for token/age pair, and copy
935 // all live variables with same token/age pair at the same
936 // time. This is the same stuff that the notavaialable analysis
937 // marks as now available.
938 VariableSourceToken vst = vstIfStatic.vst;
940 Iterator<VariableSourceToken> availItr =
941 vstTableIn.get(vst.getSESE(), vst.getAge()).iterator();
943 while (availItr.hasNext()) {
944 VariableSourceToken vstAlsoAvail = availItr.next();
946 // only grab additional stuff that is live
947 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
949 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
950 while (refVarItr.hasNext()) {
951 TempDescriptor refVar = refVarItr.next();
952 if (liveSetIn.contains(refVar)) {
957 if (!copySet.isEmpty()) {
958 plan.addStall2CopySet(vstAlsoAvail, copySet);
963 // the other case for srcs is READY, so do nothing
966 // assert that everything being stalled for is in the
967 // "not available" set coming into this flat node and
968 // that every VST identified is in the possible "stall set"
969 // that represents VST's from children SESE's
977 // identify sese-age pairs that are statically useful
978 // and should have an associated SESE variable in code
979 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
980 // AND ALWAYS GIVE NAMES TO LOCAL PARENTS
981 Set<VariableSourceToken> staticSet = vstTableIn.get();
982 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
983 while (vstItr.hasNext()) {
984 VariableSourceToken vst = vstItr.next();
986 // the caller proxy generates useful analysis facts, but we
987 // never need to generate another name for it in code (it is
988 // ALWAYS the task executing the local method context)
989 if( vst.getSESE().getIsCallerProxySESE() ) {
993 SESEandAgePair sap = new SESEandAgePair( vst.getSESE(), vst.getAge() );
994 sap.getSESE().mustTrackAtLeastAge( sap.getAge() );
996 FlatSESEEnterNode sese = currentSESE;
997 while( sese != null ) {
998 addNeededStaticName( sese, fm, sap );
999 sese = sese.getLocalParent();
1003 codePlans.put(fn, plan);
1005 // if any variables at this-node-*dot* have a static source (exactly one
1007 // but go to a dynamic source at next-node-*dot*, create a new IR graph
1008 // node on that edge to track the sources dynamically
1009 VarSrcTokTable thisVstTable = variableResults.get(fn);
1010 for (int i = 0; i < fn.numNext(); i++) {
1011 FlatNode nn = fn.getNext(i);
1012 VarSrcTokTable nextVstTable = variableResults.get(nn);
1013 Set<TempDescriptor> nextLiveIn = livenessGlobalView.get(nn);
1015 // the table can be null if it is one of the few IR nodes
1016 // completely outside of the root SESE scope
1017 if (nextVstTable != null && nextLiveIn != null) {
1019 Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
1020 thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, currentSESE);
1022 if (!readyOrStatic2dynamicSet.isEmpty()) {
1024 // either add these results to partial fixed-point result
1025 // or make a new one if we haven't made any here yet
1026 FlatEdge fe = new FlatEdge(fn, nn);
1027 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe);
1029 if (fwdvn == null) {
1030 fwdvn = new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, currentSESE);
1031 wdvNodesToSpliceIn.put(fe, fwdvn);
1033 fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet);
1040 private void addDynamicVar( FlatSESEEnterNode fsen,
1042 TempDescriptor var ) {
1045 if( fsen.getIsCallerProxySESE() ) {
1046 // attach the dynamic variable to track to
1047 // the flat method, so it can be declared at entry
1050 // otherwise the code context is a task body
1054 ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1056 ctn = new ContextTaskNames();
1059 ctn.addDynamicVar( var );
1060 fn2contextTaskNames.put( fnContext, ctn );
1063 private void addNeededStaticName( FlatSESEEnterNode fsen,
1065 SESEandAgePair sap ) {
1068 if( fsen.getIsCallerProxySESE() ) {
1069 // attach the dynamic variable to track to
1070 // the flat method, so it can be declared at entry
1073 // otherwise the code context is a task body
1077 ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1079 ctn = new ContextTaskNames();
1082 ctn.addNeededStaticName( sap );
1084 fn2contextTaskNames.put( fnContext, ctn );
1088 private void startConflictGraphs() {
1090 // first, for each task, consider whether it has any children, and if
1091 // effects analysis says they should be a conflict node in the that
1092 // parent's conflict graph
1093 Set<FlatSESEEnterNode> allSESEs = rblockRel.getAllSESEs();
1094 for( Iterator iterator = allSESEs.iterator(); iterator.hasNext(); ) {
1096 FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
1097 if( parent.getIsLeafSESE() ) {
1101 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1102 ConflictGraph conflictGraph = sese2conflictGraph.get( parent );
1103 assert conflictGraph == null;
1104 conflictGraph = new ConflictGraph( state );
1106 Set<FlatSESEEnterNode> children = parent.getChildren();
1107 for( Iterator iterator2 = children.iterator(); iterator2.hasNext(); ) {
1108 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
1109 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get( child );
1110 conflictGraph.addLiveIn( taint2Effects );
1113 sese2conflictGraph.put( parent, conflictGraph );
1116 // then traverse all methods looking for potential stall sites, and
1117 // add those stall sites as nodes in any task's conflict graph that
1118 // might be executing at the point of the stall site
1119 Iterator<MethodDescriptor> descItr = descriptorsToAnalyze.iterator();
1120 while( descItr.hasNext() ) {
1121 MethodDescriptor md = descItr.next();
1122 FlatMethod fm = state.getMethodFlat( md );
1124 addStallSitesToConflictGraphs( fm );
1129 private void addStallSitesToConflictGraphs( FlatMethod fm ) {
1131 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1132 flatNodesToVisit.add( fm );
1134 Set<FlatNode> visited = new HashSet<FlatNode>();
1136 while( !flatNodesToVisit.isEmpty() ) {
1137 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1138 flatNodesToVisit.remove( fn );
1141 Set<FlatSESEEnterNode> currentSESEs =
1142 rblockRel.getPossibleExecutingRBlocks( fn );
1144 conflictGraph_nodeAction( fn, currentSESEs );
1146 // schedule forward nodes for analysis
1147 for( int i = 0; i < fn.numNext(); i++ ) {
1148 FlatNode nn = fn.getNext( i );
1149 if( !visited.contains( nn ) ) {
1150 flatNodesToVisit.add( nn );
1156 private void conflictGraph_nodeAction( FlatNode fn,
1157 Set<FlatSESEEnterNode> currentSESEs
1160 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1162 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get( fn );
1165 // repeat the process of adding a stall site to a conflict graph
1166 // for each task that might be executing at a possible stall site
1167 Iterator<FlatSESEEnterNode> seseItr = currentSESEs.iterator();
1168 while( seseItr.hasNext() ) {
1169 FlatSESEEnterNode currentSESE = seseItr.next();
1171 ConflictGraph conflictGraph = sese2conflictGraph.get( currentSESE );
1172 if( conflictGraph == null ) {
1173 assert currentSESE.getIsLeafSESE();
1180 switch( fn.kind() ) {
1183 case FKind.FlatFieldNode:
1184 case FKind.FlatElementNode: {
1186 if( fn instanceof FlatFieldNode ) {
1187 FlatFieldNode ffn = (FlatFieldNode) fn;
1190 FlatElementNode fen = (FlatElementNode) fn;
1194 conflictGraph.addStallSite( taint2Effects, rhs );
1198 case FKind.FlatSetFieldNode:
1199 case FKind.FlatSetElementNode: {
1201 if( fn instanceof FlatSetFieldNode ) {
1202 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1203 lhs = fsfn.getDst();
1204 rhs = fsfn.getSrc();
1206 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1207 lhs = fsen.getDst();
1208 rhs = fsen.getSrc();
1211 conflictGraph.addStallSite( taint2Effects, rhs );
1212 conflictGraph.addStallSite( taint2Effects, lhs );
1216 case FKind.FlatCall: {
1217 FlatCall fc = (FlatCall) fn;
1220 conflictGraph.addStallSite( taint2Effects, lhs );
1225 if( conflictGraph.id2cn.size() > 0 ) {
1226 sese2conflictGraph.put( currentSESE, conflictGraph );
1232 private void calculateConflicts( Set<FlatNew> sitesToFlag,
1233 boolean useReachInfo ) {
1235 // decide fine-grain edge or coarse-grain edge among all vertexes by
1236 // pair-wise comparison
1237 Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
1238 while (seseIter.hasNext()) {
1239 FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next();
1240 ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
1243 // clear current conflict before recalculating with reachability info
1244 conflictGraph.clearAllConflictEdge();
1245 conflictGraph.setDisJointAnalysis(disjointAnalysisReach);
1246 conflictGraph.setFMEnclosing(sese.getfmEnclosing());
1248 conflictGraph.analyzeConflicts(sitesToFlag, useReachInfo);
1249 sese2conflictGraph.put(sese, conflictGraph);
1254 private void writeConflictGraph() {
1255 Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
1256 while (keyEnum.hasMoreElements()) {
1257 FlatNode key = (FlatNode) keyEnum.nextElement();
1258 ConflictGraph cg = sese2conflictGraph.get(key);
1260 if (cg.hasConflictEdge()) {
1261 cg.writeGraph("ConflictGraphFor" + key, false);
1263 } catch (IOException e) {
1264 System.out.println("Error writing");
1272 // the traversal for pruning state machines and finding
1273 // machines that are weakly connected BOTH consider conflicting
1274 // effects between heap roots, so it is smart to compute all of
1276 public void pruneMachinesAndFindWeaklyConnectedExaminers() {
1278 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1280 // visit every conflict graph once, so iterate through the
1281 // the non-leaf tasks to find them all
1282 Set<FlatSESEEnterNode> allSESEs = rblockRel.getAllSESEs();
1283 for( Iterator allItr = allSESEs.iterator(); allItr.hasNext(); ) {
1285 FlatSESEEnterNode parent = (FlatSESEEnterNode) allItr.next();
1286 if( parent.getIsLeafSESE() ) {
1290 ConflictGraph conflictGraph = sese2conflictGraph.get( parent );
1291 assert conflictGraph != null;
1293 // from the conflict graph we want to extract all conflicting effects
1294 // and use them to identify (1) weakly connected heap examiners and
1295 // (2) states/examiner nodes with a conflicting effect that will later
1296 // support the examiner pruning process
1297 Set<ConflictEdge> conflictEdges = conflictGraph.getEdgeSet();
1298 for( Iterator edgeItr = conflictEdges.iterator(); edgeItr.hasNext(); ) {
1299 ConflictEdge conflictEdge = (ConflictEdge) edgeItr.next();
1310 private void synthesizeLocks() {
1311 // for every conflict graph, generate a set of memory queues
1312 // (called SESELock in this code!) to cover the graph
1313 Set<Map.Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
1314 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
1315 Map.Entry<FlatNode, ConflictGraph> graphEntry = (Map.Entry<FlatNode, ConflictGraph>) iterator.next();
1316 FlatNode sese = graphEntry.getKey();
1317 ConflictGraph conflictGraph = graphEntry.getValue();
1318 calculateCovering(conflictGraph);
1322 private void calculateCovering(ConflictGraph conflictGraph) {
1323 uniqueLockSetId = 0; // reset lock counter for every new conflict graph
1324 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1325 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1326 HashSet<SESELock> lockSet = new HashSet<SESELock>();
1328 Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1329 for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
1330 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1331 if (conflictEdge.isCoarseEdge()) {
1332 coarseToCover.add(conflictEdge);
1334 fineToCover.add(conflictEdge);
1338 HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
1339 toCover.addAll(fineToCover);
1340 toCover.addAll(coarseToCover);
1342 while (!toCover.isEmpty()) {
1344 SESELock seseLock = new SESELock();
1345 seseLock.setID(uniqueLockSetId++);
1349 do { // fine-grained edge
1353 for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) {
1356 ConflictEdge edge = (ConflictEdge) iterator.next();
1357 if (seseLock.getConflictNodeSet().size() == 0) {
1359 if (seseLock.isWriteNode(edge.getVertexU())) {
1360 // mark as fine_write
1361 if (edge.getVertexU().isStallSiteNode()) {
1362 type = ConflictNode.PARENT_WRITE;
1364 type = ConflictNode.FINE_WRITE;
1366 seseLock.addConflictNode(edge.getVertexU(), type);
1368 // mark as fine_read
1369 if (edge.getVertexU().isStallSiteNode()) {
1370 type = ConflictNode.PARENT_READ;
1372 type = ConflictNode.FINE_READ;
1374 seseLock.addConflictNode(edge.getVertexU(), type);
1376 if (edge.getVertexV() != edge.getVertexU()) {
1377 if (seseLock.isWriteNode(edge.getVertexV())) {
1378 // mark as fine_write
1379 if (edge.getVertexV().isStallSiteNode()) {
1380 type = ConflictNode.PARENT_WRITE;
1382 type = ConflictNode.FINE_WRITE;
1384 seseLock.addConflictNode(edge.getVertexV(), type);
1386 // mark as fine_read
1387 if (edge.getVertexV().isStallSiteNode()) {
1388 type = ConflictNode.PARENT_READ;
1390 type = ConflictNode.FINE_READ;
1392 seseLock.addConflictNode(edge.getVertexV(), type);
1396 seseLock.addConflictEdge(edge);
1397 fineToCover.remove(edge);
1398 break;// exit iterator loop
1399 }// end of initial setup
1401 ConflictNode newNode;
1402 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1403 // new node has a fine-grained edge to all current node
1404 // If there is a coarse grained edge where need a fine edge, it's
1405 // okay to add the node
1406 // but the edge must remain uncovered.
1410 if (seseLock.containsConflictNode(newNode)) {
1411 seseLock.addEdge(edge);
1412 fineToCover.remove(edge);
1416 if (seseLock.isWriteNode(newNode)) {
1417 if (newNode.isStallSiteNode()) {
1418 type = ConflictNode.PARENT_WRITE;
1420 type = ConflictNode.FINE_WRITE;
1422 seseLock.setNodeType(newNode, type);
1424 if (newNode.isStallSiteNode()) {
1425 type = ConflictNode.PARENT_READ;
1427 type = ConflictNode.FINE_READ;
1429 seseLock.setNodeType(newNode, type);
1432 seseLock.addEdge(edge);
1433 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1434 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1435 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1437 // mark all fine edges between new node and nodes in the group as
1439 if (!conflictEdge.getVertexU().equals(newNode)) {
1440 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1442 seseLock.addConflictEdge(conflictEdge);
1443 fineToCover.remove(conflictEdge);
1445 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1446 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1448 seseLock.addConflictEdge(conflictEdge);
1449 fineToCover.remove(conflictEdge);
1455 break;// exit iterator loop
1460 HashSet<ConflictEdge> notCovered=new HashSet<ConflictEdge>();
1464 for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) {
1466 ConflictEdge edge = (ConflictEdge) iterator.next();
1467 if (seseLock.getConflictNodeSet().size() == 0) {
1469 if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
1470 // node has a coarse-grained edge with itself
1471 if (!(edge.getVertexU().isStallSiteNode())) {
1472 // and it is not parent
1473 type = ConflictNode.SCC;
1476 type = ConflictNode.PARENT_COARSE;
1478 type = ConflictNode.PARENT_WRITE;
1481 seseLock.addConflictNode(edge.getVertexU(), type);
1483 if (edge.getVertexU().isStallSiteNode()) {
1485 type = ConflictNode.PARENT_COARSE;
1487 if (edge.getVertexU().getWriteEffectSet().isEmpty()) {
1488 type = ConflictNode.PARENT_READ;
1490 type = ConflictNode.PARENT_WRITE;
1494 type = ConflictNode.COARSE;
1496 seseLock.addConflictNode(edge.getVertexU(), type);
1498 if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
1499 // node has a coarse-grained edge with itself
1500 if (!(edge.getVertexV().isStallSiteNode())) {
1501 // and it is not parent
1502 type = ConflictNode.SCC;
1505 type = ConflictNode.PARENT_COARSE;
1507 type = ConflictNode.PARENT_WRITE;
1510 seseLock.addConflictNode(edge.getVertexV(), type);
1512 if (edge.getVertexV().isStallSiteNode()) {
1514 type = ConflictNode.PARENT_COARSE;
1516 if (edge.getVertexV().getWriteEffectSet().isEmpty()) {
1517 type = ConflictNode.PARENT_READ;
1519 type = ConflictNode.PARENT_WRITE;
1523 type = ConflictNode.COARSE;
1525 seseLock.addConflictNode(edge.getVertexV(), type);
1528 coarseToCover.remove(edge);
1529 seseLock.addConflictEdge(edge);
1530 break;// exit iterator loop
1531 }// end of initial setup
1533 ConflictNode newNode;
1534 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1535 // new node has a coarse-grained edge to all fine-read, fine-write,
1539 if (newNode.isInVarNode() && (!seseLock.hasSelfCoarseEdge(newNode))
1540 && seseLock.hasCoarseEdgeWithParentCoarse(newNode)) {
1541 // this case can't be covered by this queue
1542 coarseToCover.remove(edge);
1543 notCovered.add(edge);
1547 if (seseLock.containsConflictNode(newNode)) {
1548 seseLock.addEdge(edge);
1549 coarseToCover.remove(edge);
1553 if (seseLock.hasSelfCoarseEdge(newNode)) {
1555 if (newNode.isStallSiteNode()) {
1556 type = ConflictNode.PARENT_COARSE;
1558 type = ConflictNode.SCC;
1560 seseLock.setNodeType(newNode, type);
1562 if (newNode.isStallSiteNode()) {
1563 type = ConflictNode.PARENT_COARSE;
1565 type = ConflictNode.COARSE;
1567 seseLock.setNodeType(newNode, type);
1570 seseLock.addEdge(edge);
1571 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1572 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1573 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1574 // mark all coarse edges between new node and nodes in the group
1576 if (!conflictEdge.getVertexU().equals(newNode)) {
1577 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1579 seseLock.addConflictEdge(conflictEdge);
1580 coarseToCover.remove(conflictEdge);
1582 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1583 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1585 seseLock.addConflictEdge(conflictEdge);
1586 coarseToCover.remove(conflictEdge);
1591 break;// exit iterator loop
1597 lockSet.add(seseLock);
1600 coarseToCover.addAll(notCovered);
1601 toCover.addAll(fineToCover);
1602 toCover.addAll(coarseToCover);
1606 conflictGraph2SESELock.put(conflictGraph, lockSet);
1609 public ConflictGraph getConflictGraph(FlatNode sese) {
1610 return sese2conflictGraph.get(sese);
1613 public Set<SESELock> getLockMappings(ConflictGraph graph) {
1614 return conflictGraph2SESELock.get(graph);
1617 public Set<FlatSESEEnterNode> getAllSESEs() {
1618 return rblockRel.getAllSESEs();
1621 public FlatSESEEnterNode getMainSESE() {
1622 return rblockRel.getMainSESE();
1625 public FlatSESEEnterNode getCallerProxySESE() {
1626 return rblockRel.getCallerProxySESE();
1629 public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks( FlatNode fn ) {
1630 return rblockRel.getPossibleExecutingRBlocks( fn );
1634 public void writeReports(String timeReport) throws java.io.IOException {
1636 BufferedWriter bw = new BufferedWriter(new FileWriter("ooojReport_summary.txt"));
1637 bw.write("OoOJava Analysis Results\n\n");
1638 bw.write(timeReport + "\n\n");
1639 printSESEHierarchy(bw);
1644 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
1645 while (methItr.hasNext()) {
1646 MethodDescriptor md = methItr.next();
1647 FlatMethod fm = state.getMethodFlat(md);
1649 bw = new BufferedWriter(new FileWriter("ooojReport_" +
1650 md.getClassMethodName() +
1651 md.getSafeMethodDescriptor() +
1653 bw.write("OoOJava Results for " + md + "\n-------------------\n");
1655 bw.write("Dynamic vars to manage:\n " + getContextTaskNames( fm ).getDynamicVarSet() );
1657 bw.write("\n\nLive-In, Root View\n------------------\n" + fm.printMethod(livenessGlobalView));
1658 bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults));
1659 bw.write("\n\nNot Available Results-Out\n---------------------\n" + fm.printMethod(notAvailableResults));
1660 bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans));
1666 private void printSESEHierarchy(BufferedWriter bw) throws java.io.IOException {
1667 bw.write("SESE Local Hierarchy\n--------------\n");
1668 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getLocalRootSESEs().iterator();
1669 while (rootItr.hasNext()) {
1670 FlatSESEEnterNode root = rootItr.next();
1671 printSESEHierarchyTree(bw, root, 0);
1675 private void printSESEHierarchyTree(BufferedWriter bw,
1676 FlatSESEEnterNode fsen,
1678 ) throws java.io.IOException {
1679 for (int i = 0; i < depth; ++i) {
1682 bw.write("- " + fsen.getPrettyIdentifier() + "\n");
1684 Iterator<FlatSESEEnterNode> childItr = fsen.getLocalChildren().iterator();
1685 while (childItr.hasNext()) {
1686 FlatSESEEnterNode fsenChild = childItr.next();
1687 printSESEHierarchyTree(bw, fsenChild, depth + 1);
1691 private void printSESEInfo(BufferedWriter bw) throws java.io.IOException {
1692 bw.write("\nSESE info\n-------------\n");
1693 Iterator<FlatSESEEnterNode> fsenItr = rblockRel.getAllSESEs().iterator();
1694 while( fsenItr.hasNext() ) {
1695 FlatSESEEnterNode fsen = fsenItr.next();
1697 bw.write("SESE " + fsen.getPrettyIdentifier());
1698 if( fsen.getIsLeafSESE() ) {
1699 bw.write(" (leaf)");
1703 bw.write(" in-set: " + fsen.getInVarSet() + "\n");
1704 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1705 while (tItr.hasNext()) {
1706 TempDescriptor inVar = tItr.next();
1707 if (fsen.getReadyInVarSet().contains(inVar)) {
1708 bw.write(" (ready) " + inVar + "\n");
1710 if (fsen.getStaticInVarSet().contains(inVar)) {
1711 bw.write(" (static) " + inVar + " from " + fsen.getStaticInVarSrc(inVar) + "\n");
1713 if (fsen.getDynamicInVarSet().contains(inVar)) {
1714 bw.write(" (dynamic)" + inVar + "\n");
1718 bw.write(" Dynamic vars to manage: " + getContextTaskNames( fsen ).getDynamicVarSet() + "\n");
1720 bw.write(" out-set: " + fsen.getOutVarSet() + "\n");
1722 bw.write(" local parent: " + fsen.getLocalParent() + "\n");
1723 bw.write(" local children: " + fsen.getLocalChildren() + "\n");
1725 bw.write(" possible parents: " + fsen.getParents() + "\n");
1726 bw.write(" possible children: " + fsen.getChildren() + "\n");