1 package Analysis.OoOJava;
3 import java.io.BufferedWriter;
4 import java.io.FileWriter;
5 import java.io.IOException;
6 import java.util.Enumeration;
7 import java.util.HashSet;
8 import java.util.Hashtable;
9 import java.util.Iterator;
12 import java.util.Stack;
13 import java.util.Map.Entry;
15 import Analysis.ArrayReferencees;
16 import Analysis.Liveness;
17 import Analysis.CallGraph.CallGraph;
18 import Analysis.Disjoint.DisjointAnalysis;
19 import Analysis.Disjoint.Effect;
20 import Analysis.Disjoint.EffectsAnalysis;
21 import Analysis.Disjoint.Taint;
23 import IR.MethodDescriptor;
28 import IR.Flat.FlatCall;
29 import IR.Flat.FlatEdge;
30 import IR.Flat.FlatElementNode;
31 import IR.Flat.FlatFieldNode;
32 import IR.Flat.FlatMethod;
33 import IR.Flat.FlatNew;
34 import IR.Flat.FlatNode;
35 import IR.Flat.FlatOpNode;
36 import IR.Flat.FlatSESEEnterNode;
37 import IR.Flat.FlatSESEExitNode;
38 import IR.Flat.FlatSetElementNode;
39 import IR.Flat.FlatSetFieldNode;
40 import IR.Flat.FlatWriteDynamicVarNode;
41 import IR.Flat.TempDescriptor;
43 public class OoOJavaAnalysis {
45 // data from the compiler
47 private TypeUtil typeUtil;
48 private CallGraph callGraph;
49 private RBlockRelationAnalysis rblockRel;
50 private DisjointAnalysis disjointAnalysisTaints;
51 private DisjointAnalysis disjointAnalysisReach;
53 private Set<MethodDescriptor> descriptorsToAnalyze;
55 private Hashtable<FlatNode, Set<TempDescriptor>> livenessGlobalView;
56 private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
57 private Hashtable<FlatNode, VarSrcTokTable> variableResults;
58 private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
59 private Hashtable<FlatNode, CodePlan> codePlans;
61 private Hashtable<FlatSESEEnterNode, Set<TempDescriptor>> notAvailableIntoSESE;
63 private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
65 private Hashtable<FlatNode, ContextTaskNames> fn2contextTaskNames;
67 // get the flat method that contains any given flat node
68 private Hashtable<FlatNode, FlatMethod> fn2fm;
70 // temporal data structures to track analysis progress.
71 static private int uniqueLockSetId = 0;
72 // mapping of a conflict graph to its compiled lock
73 private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraph2SESELock;
74 // mapping of a sese block to its conflict graph
75 private Hashtable<FlatNode, ConflictGraph> sese2conflictGraph;
77 public static int maxSESEage = -1;
79 public int getMaxSESEage() {
84 public CodePlan getCodePlan(FlatNode fn) {
85 CodePlan cp = codePlans.get(fn);
89 public Set<FlatNode> getNodesWithPlans() {
90 return codePlans.keySet();
93 public ContextTaskNames getContextTaskNames( FlatMethod fm ) {
94 ContextTaskNames out = fn2contextTaskNames.get( fm );
96 out = new ContextTaskNames();
101 public ContextTaskNames getContextTaskNames( FlatSESEEnterNode fsen ) {
102 ContextTaskNames out = fn2contextTaskNames.get( fsen );
104 out = new ContextTaskNames();
109 public FlatMethod getContainingFlatMethod( FlatNode fn ) {
110 FlatMethod fm = fn2fm.get( fn );
115 public DisjointAnalysis getDisjointAnalysis() {
116 return disjointAnalysisTaints;
120 public OoOJavaAnalysis( State state,
124 ArrayReferencees arrayReferencees ) {
126 double timeStartAnalysis = (double) System.nanoTime();
129 this.typeUtil = typeUtil;
130 this.callGraph = callGraph;
131 this.maxSESEage = state.OOO_MAXSESEAGE;
133 livenessGlobalView = new Hashtable<FlatNode, Set<TempDescriptor>>();
134 livenessVirtualReads = new Hashtable<FlatNode, Set<TempDescriptor>>();
135 variableResults = new Hashtable<FlatNode, VarSrcTokTable>();
136 notAvailableResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
137 codePlans = new Hashtable<FlatNode, CodePlan>();
138 wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
139 notAvailableIntoSESE = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
140 sese2conflictGraph = new Hashtable<FlatNode, ConflictGraph>();
141 conflictGraph2SESELock = new Hashtable<ConflictGraph, HashSet<SESELock>>();
142 fn2contextTaskNames = new Hashtable<FlatNode, ContextTaskNames>();
144 // add all methods transitively reachable from the
145 // source's main to set for analysis
146 MethodDescriptor mdSourceEntry = typeUtil.getMain();
147 FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
149 descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
151 descriptorsToAnalyze.add(mdSourceEntry);
153 // 0th pass, setup a useful mapping of any flat node to the
154 // flat method it is a part of
155 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
156 while (methItr.hasNext()) {
157 Descriptor d = methItr.next();
158 FlatMethod fm = state.getMethodFlat( d );
159 buildFlatNodeToFlatMethod( fm );
162 // 1st pass, find basic rblock relations & potential stall sites
163 rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
164 VarSrcTokTable.rblockRel = rblockRel;
166 // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
167 methItr = descriptorsToAnalyze.iterator();
168 while (methItr.hasNext()) {
169 Descriptor d = methItr.next();
170 FlatMethod fm = state.getMethodFlat(d);
172 // note we can't use the general liveness analysis already in
173 // the compiler because this analysis is task-aware
174 livenessAnalysisBackward(fm);
177 // 3rd pass, variable analysis
178 methItr = descriptorsToAnalyze.iterator();
179 while (methItr.hasNext()) {
180 Descriptor d = methItr.next();
181 FlatMethod fm = state.getMethodFlat(d);
183 // starting from roots do a forward, fixed-point
184 // variable analysis for refinement and stalls
185 variableAnalysisForward(fm);
188 // 4th pass, compute liveness contribution from
189 // virtual reads discovered in variable pass
190 methItr = descriptorsToAnalyze.iterator();
191 while (methItr.hasNext()) {
192 Descriptor d = methItr.next();
193 FlatMethod fm = state.getMethodFlat(d);
194 livenessAnalysisBackward(fm);
197 // 5th pass, use disjointness with NO FLAGGED REGIONS
198 // to compute taints and effects
199 disjointAnalysisTaints =
200 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null,
202 true ); // suppress output--this is an intermediate pass
204 // 6th pass, not available analysis FOR VARIABLES!
205 methItr = descriptorsToAnalyze.iterator();
206 while (methItr.hasNext()) {
207 Descriptor d = methItr.next();
208 FlatMethod fm = state.getMethodFlat(d);
210 // compute what is not available at every program
211 // point, in a forward fixed-point pass
212 notAvailableForward(fm);
215 // 7th pass, start conflict graphs where a parent's graph has a
216 // node for possibly conflicting children and its own stall sites
217 startConflictGraphs();
219 // 8th pass, calculate all possible conflicts without using
220 // reachability info and identify set of FlatNew that next
221 // disjoint reach. analysis should flag
222 Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
223 calculateConflicts(sitesToFlag, false);
226 // 9th pass, ask disjoint analysis to compute reachability
227 // for objects that may cause heap conflicts so the most
228 // efficient method to deal with conflict can be computed
230 disjointAnalysisReach =
231 new DisjointAnalysis(state, typeUtil, callGraph, liveness,
232 arrayReferencees, sitesToFlag,
233 null // don't do effects analysis again!
236 // 10th pass, calculate conflicts with reachability info
237 calculateConflicts(null, true);
240 // 11th pass, compiling memory Qs! The name "lock" is a legacy
241 // term for the heap dependence queue, or memQ as the runtime calls it
244 // 12th pass, compute a plan for code injections
245 methItr = descriptorsToAnalyze.iterator();
246 while (methItr.hasNext()) {
247 Descriptor d = methItr.next();
248 FlatMethod fm = state.getMethodFlat(d);
249 codePlansForward(fm);
253 // splice new IR nodes into graph after all
254 // analysis passes are complete
255 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
256 while (spliceItr.hasNext()) {
257 Map.Entry me = (Map.Entry) spliceItr.next();
258 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
259 fwdvn.spliceIntoIR();
263 if (state.OOODEBUG) {
266 disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt");
267 writeConflictGraph();
268 } catch (IOException e) {}
272 System.out.println("\n\n\n##########################################################\n"+
273 "Warning, lots of code changes going on, OoOJava and RCR/DFJ\n"+
274 "systems are being cleaned up. Until the analyses and code gen\n"+
275 "are fully altered and coordinated, these systems will not run\n"+
276 "to completion. Partial stable check-ins are necessary to manage\n"+
277 "the number of files getting touched.\n"+
278 "##########################################################" );
283 private void buildFlatNodeToFlatMethod( FlatMethod fm ) {
284 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
285 flatNodesToVisit.add( fm.getFlatExit() );
287 Set<FlatNode> flatNodesVisited = new HashSet<FlatNode>();
289 while( !flatNodesToVisit.isEmpty() ) {
290 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
291 flatNodesToVisit.remove( fn );
292 flatNodesVisited.add( fn );
296 for( int i = 0; i < fn.numNext(); i++ ) {
297 FlatNode nn = fn.getNext( i );
298 if( !flatNodesVisited.contains( nn ) ) {
299 flatNodesToVisit.add( nn );
308 * Iterator iter = sese2conflictGraph.entrySet().iterator(); while
309 * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn =
310 * (FlatNode) e.getKey(); ConflictGraph conflictGraph = (ConflictGraph)
312 * System.out.println("---------------------------------------");
313 * System.out.println("CONFLICT GRAPH for " + fn); Set<String> keySet =
314 * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator();
315 * iterator.hasNext();) { String key = (String) iterator.next();
316 * ConflictNode node = conflictGraph.id2cn.get(key);
317 * System.out.println("key=" + key + " \n" + node.toStringAllEffects()); } }
323 private void writeFile(Set<FlatNew> sitesToFlag) {
326 BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt"));
328 for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext();) {
329 FlatNew fn = (FlatNew) iterator.next();
333 } catch (IOException e) {
340 private void livenessAnalysisBackward(FlatMethod fm) {
342 // flow backward across nodes to compute liveness, and
343 // take special care with sese enter/exit nodes that
344 // alter this from normal liveness analysis
345 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
346 flatNodesToVisit.add( fm.getFlatExit() );
348 while( !flatNodesToVisit.isEmpty() ) {
349 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
350 flatNodesToVisit.remove( fn );
352 Set<TempDescriptor> prev = livenessGlobalView.get( fn );
354 // merge sets from control flow joins
355 Set<TempDescriptor> livein = new HashSet<TempDescriptor>();
356 for (int i = 0; i < fn.numNext(); i++) {
357 FlatNode nn = fn.getNext( i );
358 Set<TempDescriptor> s = livenessGlobalView.get( nn );
364 Set<TempDescriptor> curr = liveness_nodeActions( fn, livein );
366 // if a new result, schedule backward nodes for analysis
367 if( !curr.equals( prev ) ) {
368 livenessGlobalView.put( fn, curr );
370 for( int i = 0; i < fn.numPrev(); i++ ) {
371 FlatNode nn = fn.getPrev( i );
372 flatNodesToVisit.add( nn );
378 private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
379 Set<TempDescriptor> liveIn
381 switch( fn.kind() ) {
383 case FKind.FlatSESEEnterNode: {
384 // add whatever is live-in at a task enter to that
386 FlatSESEEnterNode fsen = (FlatSESEEnterNode)fn;
387 if( liveIn != null ) {
388 fsen.addInVarSet( liveIn );
390 // no break, should also execute default actions
394 // handle effects of statement in reverse, writes then reads
395 TempDescriptor[] writeTemps = fn.writesTemps();
396 for( int i = 0; i < writeTemps.length; ++i ) {
397 liveIn.remove( writeTemps[i] );
399 // if we are analyzing code declared directly in a task,
400 FlatSESEEnterNode fsen = rblockRel.getLocalInnerRBlock( fn );
402 // check to see if we are writing to variables that will
403 // be live-out at the task's exit (and therefore should
404 // go in the task's out-var set)
405 FlatSESEExitNode fsexn = fsen.getFlatExit();
406 Set<TempDescriptor> livetemps = livenessGlobalView.get( fsexn );
407 if( livetemps != null && livetemps.contains( writeTemps[i] ) ) {
408 fsen.addOutVar( writeTemps[i] );
413 TempDescriptor[] readTemps = fn.readsTemps();
414 for( int i = 0; i < readTemps.length; ++i ) {
415 liveIn.add( readTemps[i] );
418 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
419 if( virtualReadTemps != null ) {
420 liveIn.addAll( virtualReadTemps );
430 private void variableAnalysisForward(FlatMethod fm) {
432 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
433 flatNodesToVisit.add(fm);
435 while (!flatNodesToVisit.isEmpty()) {
436 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
437 flatNodesToVisit.remove(fn);
439 VarSrcTokTable prev = variableResults.get(fn);
441 // merge sets from control flow joins
442 VarSrcTokTable curr = new VarSrcTokTable();
443 for (int i = 0; i < fn.numPrev(); i++) {
444 FlatNode nn = fn.getPrev(i);
445 VarSrcTokTable incoming = variableResults.get(nn);
446 curr.merge(incoming);
449 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
450 if( currentSESE == null ) {
451 currentSESE = rblockRel.getCallerProxySESE();
454 variable_nodeActions(fn, curr, currentSESE);
456 // if a new result, schedule forward nodes for analysis
457 if (!curr.equals(prev)) {
458 variableResults.put(fn, curr);
460 for (int i = 0; i < fn.numNext(); i++) {
461 FlatNode nn = fn.getNext(i);
462 flatNodesToVisit.add(nn);
468 private void variable_nodeActions(FlatNode fn,
469 VarSrcTokTable vstTable,
470 FlatSESEEnterNode currentSESE) {
474 case FKind.FlatSESEEnterNode: {
475 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
476 // ignore currently executing SESE, at this point
477 // the analysis considers a new instance is becoming
480 vstTable.assertConsistency();
484 case FKind.FlatSESEExitNode: {
485 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
487 // fsen is the child of currently executing tasks
488 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
490 // remap all of this child's children tokens to be
491 // from this child as the child exits
492 vstTable.remapChildTokens(fsen);
494 // liveness virtual reads are things that might be
495 // written by an SESE and should be added to the in-set
496 // anything virtually read by this SESE should be pruned
497 // of parent or sibling sources
498 Set<TempDescriptor> liveVars = livenessGlobalView.get(fn);
499 Set<TempDescriptor> fsenVirtReads =
500 vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen,
503 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
504 if (fsenVirtReadsOld != null) {
505 fsenVirtReads.addAll(fsenVirtReadsOld);
507 livenessVirtualReads.put(fn, fsenVirtReads);
509 // then all child out-set tokens are guaranteed
510 // to be filled in, so clobber those entries with
511 // the latest, clean sources
512 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
513 while (outVarItr.hasNext()) {
514 TempDescriptor outVar = outVarItr.next();
515 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
517 VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
518 vstTable.remove(outVar);
521 vstTable.assertConsistency();
525 case FKind.FlatOpNode: {
526 FlatOpNode fon = (FlatOpNode) fn;
528 if (fon.getOp().getOp() == Operation.ASSIGN) {
529 TempDescriptor lhs = fon.getDest();
530 TempDescriptor rhs = fon.getLeft();
532 vstTable.remove(lhs);
534 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
536 Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
537 while (itr.hasNext()) {
538 VariableSourceToken vst = itr.next();
540 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
543 // when we do x = y for variables, just copy over from a child,
544 // there are two cases:
545 // 1. if the current task is the caller proxy, any local root is a child
547 currentSESE.getIsCallerProxySESE() &&
548 rblockRel.getLocalRootSESEs().contains( vst.getSESE() );
550 // 2. if the child task is a locally-defined child of the current task
551 boolean case2 = currentSESE.getLocalChildren().contains( vst.getSESE() );
553 if( case1 || case2 ) {
554 // if the source comes from a child, copy it over
555 forAddition.add( new VariableSourceToken( ts,
562 // otherwise, stamp it as us as the source
563 forAddition.add( new VariableSourceToken( ts,
572 vstTable.addAll( forAddition );
574 // only break if this is an ASSIGN op node,
575 // otherwise fall through to default case
576 vstTable.assertConsistency();
581 // note that FlatOpNode's that aren't ASSIGN
582 // fall through to this default case
584 TempDescriptor[] writeTemps = fn.writesTemps();
585 if( writeTemps.length > 0 ) {
587 // for now, when writeTemps > 1, make sure
588 // its a call node, programmer enforce only
589 // doing stuff like calling a print routine
590 if( writeTemps.length > 1 ) {
591 assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
595 vstTable.remove( writeTemps[0] );
597 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
598 ts.add( writeTemps[0] );
600 vstTable.add( new VariableSourceToken( ts,
608 vstTable.assertConsistency();
615 private void notAvailableForward(FlatMethod fm) {
617 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
618 flatNodesToVisit.add(fm);
620 while (!flatNodesToVisit.isEmpty()) {
621 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
622 flatNodesToVisit.remove(fn);
624 Set<TempDescriptor> prev = notAvailableResults.get(fn);
626 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
627 for (int i = 0; i < fn.numPrev(); i++) {
628 FlatNode nn = fn.getPrev(i);
629 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
630 if (notAvailIn != null) {
631 curr.addAll(notAvailIn);
635 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
636 if( currentSESE == null ) {
637 currentSESE = rblockRel.getCallerProxySESE();
640 notAvailable_nodeActions(fn, curr, currentSESE);
642 // if a new result, schedule forward nodes for analysis
643 if (!curr.equals(prev)) {
644 notAvailableResults.put(fn, curr);
646 for (int i = 0; i < fn.numNext(); i++) {
647 FlatNode nn = fn.getNext(i);
648 flatNodesToVisit.add(nn);
654 private void notAvailable_nodeActions(FlatNode fn,
655 Set<TempDescriptor> notAvailSet,
656 FlatSESEEnterNode currentSESE
659 // any temps that are removed from the not available set
660 // at this node should be marked in this node's code plan
661 // as temps to be grabbed at runtime!
665 case FKind.FlatSESEEnterNode: {
666 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
668 // keep a copy of what's not available into the SESE
669 // and restore it at the matching exit node
670 Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
671 Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
672 while (tdItr.hasNext()) {
673 notAvailCopy.add(tdItr.next());
675 notAvailableIntoSESE.put(fsen, notAvailCopy);
680 case FKind.FlatSESEExitNode: {
681 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
682 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
684 notAvailSet.addAll(fsen.getOutVarSet());
686 Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
687 assert notAvailIn != null;
688 notAvailSet.addAll(notAvailIn);
691 case FKind.FlatMethod: {
695 case FKind.FlatOpNode: {
696 FlatOpNode fon = (FlatOpNode) fn;
698 if (fon.getOp().getOp() == Operation.ASSIGN) {
699 TempDescriptor lhs = fon.getDest();
700 TempDescriptor rhs = fon.getLeft();
702 // copy makes lhs same availability as rhs
703 if (notAvailSet.contains(rhs)) {
704 notAvailSet.add(lhs);
706 notAvailSet.remove(lhs);
709 // only break if this is an ASSIGN op node,
710 // otherwise fall through to default case
715 // note that FlatOpNode's that aren't ASSIGN
716 // fall through to this default case
718 TempDescriptor[] writeTemps = fn.writesTemps();
719 for (int i = 0; i < writeTemps.length; i++) {
720 TempDescriptor wTemp = writeTemps[i];
721 notAvailSet.remove(wTemp);
723 TempDescriptor[] readTemps = fn.readsTemps();
724 for (int i = 0; i < readTemps.length; i++) {
725 TempDescriptor rTemp = readTemps[i];
726 notAvailSet.remove(rTemp);
728 // if this variable has exactly one source, potentially
729 // get other things from this source as well
730 VarSrcTokTable vstTable = variableResults.get(fn);
732 VSTWrapper vstIfStatic = new VSTWrapper();
733 Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
735 if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
737 VariableSourceToken vst = vstIfStatic.vst;
739 Iterator<VariableSourceToken> availItr =
740 vstTable.get(vst.getSESE(), vst.getAge()).iterator();
742 // look through things that are also available from same source
743 while (availItr.hasNext()) {
744 VariableSourceToken vstAlsoAvail = availItr.next();
746 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
747 while (refVarItr.hasNext()) {
748 TempDescriptor refVarAlso = refVarItr.next();
750 // if a variable is available from the same source, AND it ALSO
751 // only comes from one statically known source, mark it available
752 VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
753 Integer srcTypeAlso =
754 vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed);
755 if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
756 notAvailSet.remove(refVarAlso);
768 private void codePlansForward(FlatMethod fm) {
770 // start from flat method top, visit every node in
771 // method exactly once
772 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
773 flatNodesToVisit.add(fm);
775 Set<FlatNode> visited = new HashSet<FlatNode>();
777 while (!flatNodesToVisit.isEmpty()) {
778 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
779 FlatNode fn = fnItr.next();
781 flatNodesToVisit.remove(fn);
784 // use incoming results as "dot statement" or just
785 // before the current statement
786 VarSrcTokTable dotSTtable = new VarSrcTokTable();
787 for (int i = 0; i < fn.numPrev(); i++) {
788 FlatNode nn = fn.getPrev(i);
789 dotSTtable.merge(variableResults.get(nn));
792 // find dt-st notAvailableSet also
793 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
794 for (int i = 0; i < fn.numPrev(); i++) {
795 FlatNode nn = fn.getPrev(i);
796 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
797 if (notAvailIn != null) {
798 dotSTnotAvailSet.addAll(notAvailIn);
802 Set<TempDescriptor> dotSTlive = livenessGlobalView.get(fn);
804 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
805 if( currentSESE == null ) {
806 currentSESE = rblockRel.getCallerProxySESE();
809 codePlans_nodeActions(fm, fn,
810 dotSTlive, dotSTtable, dotSTnotAvailSet,
813 for (int i = 0; i < fn.numNext(); i++) {
814 FlatNode nn = fn.getNext(i);
816 if (!visited.contains(nn)) {
817 flatNodesToVisit.add(nn);
823 private void codePlans_nodeActions(FlatMethod fm,
825 Set<TempDescriptor> liveSetIn,
826 VarSrcTokTable vstTableIn,
827 Set<TempDescriptor> notAvailSetIn,
828 FlatSESEEnterNode currentSESE) {
830 CodePlan plan = new CodePlan(currentSESE);
834 case FKind.FlatSESEEnterNode: {
835 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
837 // track the source types of the in-var set so generated
838 // code at this SESE issue can compute the number of
839 // dependencies properly
840 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
841 while (inVarItr.hasNext()) {
842 TempDescriptor inVar = inVarItr.next();
844 // when we get to an SESE enter node we change the
845 // currentSESE variable of this analysis to the
846 // child that is declared by the enter node, so
847 // in order to classify in-vars correctly, pass
848 // the parent SESE in--at other FlatNode types just
849 // use the currentSESE
850 FlatSESEEnterNode parent = rblockRel.getLocalInnerRBlock( fn );
851 if( parent == null ) {
852 parent = rblockRel.getCallerProxySESE();
855 VSTWrapper vstIfStatic = new VSTWrapper();
856 Integer srcType = vstTableIn.getRefVarSrcType(inVar, parent, vstIfStatic);
858 // the current SESE needs a local space to track the dynamic
859 // variable and the child needs space in its SESE record
860 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
861 fsen.addDynamicInVar(inVar);
862 addDynamicVar( fsen, fm, inVar );
864 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
865 fsen.addStaticInVar(inVar);
866 VariableSourceToken vst = vstIfStatic.vst;
867 fsen.putStaticInVar2src(inVar, vst);
868 fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
870 assert srcType.equals(VarSrcTokTable.SrcType_READY);
871 fsen.addReadyInVar(inVar);
876 case FKind.FlatSESEExitNode: {
877 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
878 //TODO! Shouldn't there be a code plan for task exit
879 // where the exiting task calculates whether its own
880 // siblings need variables from its children, so the
881 // exiter should copy those variables into its own out-set
882 // and make the available?
885 case FKind.FlatOpNode: {
886 FlatOpNode fon = (FlatOpNode) fn;
888 if (fon.getOp().getOp() == Operation.ASSIGN) {
889 TempDescriptor lhs = fon.getDest();
890 TempDescriptor rhs = fon.getLeft();
892 // if this is an op node, don't stall, copy
893 // source and delay until we need to use value
895 // ask whether lhs and rhs sources are dynamic, static, etc.
896 VSTWrapper vstIfStatic = new VSTWrapper();
897 Integer lhsSrcType = vstTableIn.getRefVarSrcType(lhs, currentSESE, vstIfStatic);
898 Integer rhsSrcType = vstTableIn.getRefVarSrcType(rhs, currentSESE, vstIfStatic);
900 if (rhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
901 // if rhs is dynamic going in, lhs will definitely be dynamic
902 // going out of this node, so track that here
903 plan.addDynAssign( lhs, rhs );
904 addDynamicVar( currentSESE, fm, lhs );
905 addDynamicVar( currentSESE, fm, rhs );
907 } else if (lhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
908 // otherwise, if the lhs is dynamic, but the rhs is not, we
909 // need to update the variable's dynamic source as "current SESE"
910 plan.addDynAssign(lhs);
913 // only break if this is an ASSIGN op node,
914 // otherwise fall through to default case
919 // note that FlatOpNode's that aren't ASSIGN
920 // fall through to this default case
923 // a node with no live set has nothing to stall for
924 if (liveSetIn == null) {
928 TempDescriptor[] readarray = fn.readsTemps();
929 for (int i = 0; i < readarray.length; i++) {
930 TempDescriptor readtmp = readarray[i];
932 // ignore temps that are definitely available
933 // when considering to stall on it
934 if (!notAvailSetIn.contains(readtmp)) {
938 // check the source type of this variable
939 VSTWrapper vstIfStatic = new VSTWrapper();
940 Integer srcType = vstTableIn.getRefVarSrcType(readtmp, currentSESE, vstIfStatic);
942 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
943 // 1) It is not clear statically where this variable will
944 // come from, so dynamically we must keep track
945 // along various control paths, and therefore when we stall,
946 // just stall for the exact thing we need and move on
947 plan.addDynamicStall( readtmp );
948 addDynamicVar( currentSESE, fm, readtmp );
950 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
951 // 2) Single token/age pair: Stall for token/age pair, and copy
952 // all live variables with same token/age pair at the same
953 // time. This is the same stuff that the notavaialable analysis
954 // marks as now available.
955 VariableSourceToken vst = vstIfStatic.vst;
957 Iterator<VariableSourceToken> availItr =
958 vstTableIn.get(vst.getSESE(), vst.getAge()).iterator();
960 while (availItr.hasNext()) {
961 VariableSourceToken vstAlsoAvail = availItr.next();
963 // only grab additional stuff that is live
964 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
966 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
967 while (refVarItr.hasNext()) {
968 TempDescriptor refVar = refVarItr.next();
969 if (liveSetIn.contains(refVar)) {
974 if (!copySet.isEmpty()) {
975 plan.addStall2CopySet(vstAlsoAvail, copySet);
980 // the other case for srcs is READY, so do nothing
983 // assert that everything being stalled for is in the
984 // "not available" set coming into this flat node and
985 // that every VST identified is in the possible "stall set"
986 // that represents VST's from children SESE's
994 // identify sese-age pairs that are statically useful
995 // and should have an associated SESE variable in code
996 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
997 // AND ALWAYS GIVE NAMES TO LOCAL PARENTS
998 Set<VariableSourceToken> staticSet = vstTableIn.get();
999 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
1000 while (vstItr.hasNext()) {
1001 VariableSourceToken vst = vstItr.next();
1003 // the caller proxy generates useful analysis facts, but we
1004 // never need to generate another name for it in code (it is
1005 // ALWAYS the task executing the local method context)
1006 if( vst.getSESE().getIsCallerProxySESE() ) {
1010 SESEandAgePair sap = new SESEandAgePair( vst.getSESE(), vst.getAge() );
1011 sap.getSESE().mustTrackAtLeastAge( sap.getAge() );
1013 FlatSESEEnterNode sese = currentSESE;
1014 while( sese != null ) {
1015 addNeededStaticName( sese, fm, sap );
1016 sese = sese.getLocalParent();
1020 codePlans.put(fn, plan);
1022 // if any variables at this-node-*dot* have a static source (exactly one
1024 // but go to a dynamic source at next-node-*dot*, create a new IR graph
1025 // node on that edge to track the sources dynamically
1026 VarSrcTokTable thisVstTable = variableResults.get(fn);
1027 for (int i = 0; i < fn.numNext(); i++) {
1028 FlatNode nn = fn.getNext(i);
1029 VarSrcTokTable nextVstTable = variableResults.get(nn);
1030 Set<TempDescriptor> nextLiveIn = livenessGlobalView.get(nn);
1032 // the table can be null if it is one of the few IR nodes
1033 // completely outside of the root SESE scope
1034 if (nextVstTable != null && nextLiveIn != null) {
1036 Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
1037 thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, currentSESE);
1039 if (!readyOrStatic2dynamicSet.isEmpty()) {
1041 // either add these results to partial fixed-point result
1042 // or make a new one if we haven't made any here yet
1043 FlatEdge fe = new FlatEdge(fn, nn);
1044 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe);
1046 if (fwdvn == null) {
1047 fwdvn = new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, currentSESE);
1048 wdvNodesToSpliceIn.put(fe, fwdvn);
1050 fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet);
1057 private void addDynamicVar( FlatSESEEnterNode fsen,
1059 TempDescriptor var ) {
1062 if( fsen.getIsCallerProxySESE() ) {
1063 // attach the dynamic variable to track to
1064 // the flat method, so it can be declared at entry
1067 // otherwise the code context is a task body
1071 ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1073 ctn = new ContextTaskNames();
1076 ctn.addDynamicVar( var );
1077 fn2contextTaskNames.put( fnContext, ctn );
1080 private void addNeededStaticName( FlatSESEEnterNode fsen,
1082 SESEandAgePair sap ) {
1085 if( fsen.getIsCallerProxySESE() ) {
1086 // attach the dynamic variable to track to
1087 // the flat method, so it can be declared at entry
1090 // otherwise the code context is a task body
1094 ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1096 ctn = new ContextTaskNames();
1099 ctn.addNeededStaticName( sap );
1101 fn2contextTaskNames.put( fnContext, ctn );
1105 private void startConflictGraphs() {
1107 // first, for each task, consider whether it has any children, and if
1108 // effects analysis says they should be a conflict node in the that
1109 // parent's conflict graph
1110 Set<FlatSESEEnterNode> allSESEs = rblockRel.getAllSESEs();
1111 for( Iterator iterator = allSESEs.iterator(); iterator.hasNext(); ) {
1113 FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
1114 if( parent.getIsLeafSESE() ) {
1118 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1119 ConflictGraph conflictGraph = sese2conflictGraph.get( parent );
1120 assert conflictGraph == null;
1121 //if (conflictGraph == null) {
1122 conflictGraph = new ConflictGraph( state );
1125 Set<FlatSESEEnterNode> children = parent.getChildren();
1126 for( Iterator iterator2 = children.iterator(); iterator2.hasNext(); ) {
1127 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
1128 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get( child );
1129 conflictGraph.addLiveIn( taint2Effects );
1132 sese2conflictGraph.put( parent, conflictGraph );
1135 // then traverse all methods looking for potential stall sites, and
1136 // add those stall sites as nodes in any task's conflict graph that
1137 // might be executing at the point of the stall site
1138 Iterator<MethodDescriptor> descItr = descriptorsToAnalyze.iterator();
1139 while( descItr.hasNext() ) {
1140 MethodDescriptor md = descItr.next();
1141 FlatMethod fm = state.getMethodFlat( md );
1143 addStallSitesToConflictGraphs( fm );
1148 private void addStallSitesToConflictGraphs( FlatMethod fm ) {
1150 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1151 flatNodesToVisit.add( fm );
1153 Set<FlatNode> visited = new HashSet<FlatNode>();
1155 while( !flatNodesToVisit.isEmpty() ) {
1156 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1157 flatNodesToVisit.remove( fn );
1160 Set<FlatSESEEnterNode> currentSESEs =
1161 rblockRel.getPossibleExecutingRBlocks( fn );
1163 conflictGraph_nodeAction( fn, currentSESEs );
1165 // schedule forward nodes for analysis
1166 for( int i = 0; i < fn.numNext(); i++ ) {
1167 FlatNode nn = fn.getNext( i );
1168 if( !visited.contains( nn ) ) {
1169 flatNodesToVisit.add( nn );
1175 private void conflictGraph_nodeAction( FlatNode fn,
1176 Set<FlatSESEEnterNode> currentSESEs
1179 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1181 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get( fn );
1184 // repeat the process of adding a stall site to a conflict graph
1185 // for each task that might be executing at a possible stall site
1186 Iterator<FlatSESEEnterNode> seseItr = currentSESEs.iterator();
1187 while( seseItr.hasNext() ) {
1188 FlatSESEEnterNode currentSESE = seseItr.next();
1190 ConflictGraph conflictGraph = sese2conflictGraph.get( currentSESE );
1191 assert conflictGraph != null;
1192 //if (conflictGraph == null) {
1193 // conflictGraph = new ConflictGraph(state);
1199 switch( fn.kind() ) {
1202 case FKind.FlatFieldNode:
1203 case FKind.FlatElementNode: {
1205 if( fn instanceof FlatFieldNode ) {
1206 FlatFieldNode ffn = (FlatFieldNode) fn;
1209 FlatElementNode fen = (FlatElementNode) fn;
1213 conflictGraph.addStallSite( taint2Effects, rhs );
1217 case FKind.FlatSetFieldNode:
1218 case FKind.FlatSetElementNode: {
1220 if( fn instanceof FlatSetFieldNode ) {
1221 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1222 lhs = fsfn.getDst();
1223 rhs = fsfn.getSrc();
1225 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1226 lhs = fsen.getDst();
1227 rhs = fsen.getSrc();
1230 conflictGraph.addStallSite( taint2Effects, rhs );
1231 conflictGraph.addStallSite( taint2Effects, lhs );
1235 case FKind.FlatCall: {
1236 FlatCall fc = (FlatCall) fn;
1239 conflictGraph.addStallSite( taint2Effects, lhs );
1244 if( conflictGraph.id2cn.size() > 0 ) {
1245 sese2conflictGraph.put( currentSESE, conflictGraph );
1251 private void calculateConflicts( Set<FlatNew> sitesToFlag,
1252 boolean useReachInfo ) {
1254 // decide fine-grain edge or coarse-grain edge among all vertexes by
1255 // pair-wise comparison
1256 Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
1257 while (seseIter.hasNext()) {
1258 FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next();
1259 ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
1262 // clear current conflict before recalculating with reachability info
1263 conflictGraph.clearAllConflictEdge();
1264 conflictGraph.setDisJointAnalysis(disjointAnalysisReach);
1265 conflictGraph.setFMEnclosing(sese.getfmEnclosing());
1267 conflictGraph.analyzeConflicts(sitesToFlag, useReachInfo);
1268 sese2conflictGraph.put(sese, conflictGraph);
1273 private void writeConflictGraph() {
1274 Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
1275 while (keyEnum.hasMoreElements()) {
1276 FlatNode key = (FlatNode) keyEnum.nextElement();
1277 ConflictGraph cg = sese2conflictGraph.get(key);
1279 if (cg.hasConflictEdge()) {
1280 cg.writeGraph("ConflictGraphFor" + key, false);
1282 } catch (IOException e) {
1283 System.out.println("Error writing");
1290 private void synthesizeLocks() {
1291 // for every conflict graph, generate a set of memory queues
1292 // (called SESELock in this code!) to cover the graph
1293 Set<Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
1294 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
1295 Entry<FlatNode, ConflictGraph> graphEntry = (Entry<FlatNode, ConflictGraph>) iterator.next();
1296 FlatNode sese = graphEntry.getKey();
1297 ConflictGraph conflictGraph = graphEntry.getValue();
1298 calculateCovering(conflictGraph);
1302 private void calculateCovering(ConflictGraph conflictGraph) {
1303 uniqueLockSetId = 0; // reset lock counter for every new conflict graph
1304 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1305 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1306 HashSet<SESELock> lockSet = new HashSet<SESELock>();
1308 Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1309 for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
1310 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1311 if (conflictEdge.isCoarseEdge()) {
1312 coarseToCover.add(conflictEdge);
1314 fineToCover.add(conflictEdge);
1318 HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
1319 toCover.addAll(fineToCover);
1320 toCover.addAll(coarseToCover);
1322 while (!toCover.isEmpty()) {
1324 SESELock seseLock = new SESELock();
1325 seseLock.setID(uniqueLockSetId++);
1329 do { // fine-grained edge
1333 for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) {
1336 ConflictEdge edge = (ConflictEdge) iterator.next();
1337 if (seseLock.getConflictNodeSet().size() == 0) {
1339 if (seseLock.isWriteNode(edge.getVertexU())) {
1340 // mark as fine_write
1341 if (edge.getVertexU().isStallSiteNode()) {
1342 type = ConflictNode.PARENT_WRITE;
1344 type = ConflictNode.FINE_WRITE;
1346 seseLock.addConflictNode(edge.getVertexU(), type);
1348 // mark as fine_read
1349 if (edge.getVertexU().isStallSiteNode()) {
1350 type = ConflictNode.PARENT_READ;
1352 type = ConflictNode.FINE_READ;
1354 seseLock.addConflictNode(edge.getVertexU(), type);
1356 if (edge.getVertexV() != edge.getVertexU()) {
1357 if (seseLock.isWriteNode(edge.getVertexV())) {
1358 // mark as fine_write
1359 if (edge.getVertexV().isStallSiteNode()) {
1360 type = ConflictNode.PARENT_WRITE;
1362 type = ConflictNode.FINE_WRITE;
1364 seseLock.addConflictNode(edge.getVertexV(), type);
1366 // mark as fine_read
1367 if (edge.getVertexV().isStallSiteNode()) {
1368 type = ConflictNode.PARENT_READ;
1370 type = ConflictNode.FINE_READ;
1372 seseLock.addConflictNode(edge.getVertexV(), type);
1376 seseLock.addConflictEdge(edge);
1377 fineToCover.remove(edge);
1378 break;// exit iterator loop
1379 }// end of initial setup
1381 ConflictNode newNode;
1382 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1383 // new node has a fine-grained edge to all current node
1384 // If there is a coarse grained edge where need a fine edge, it's
1385 // okay to add the node
1386 // but the edge must remain uncovered.
1390 if (seseLock.containsConflictNode(newNode)) {
1391 seseLock.addEdge(edge);
1392 fineToCover.remove(edge);
1396 if (seseLock.isWriteNode(newNode)) {
1397 if (newNode.isStallSiteNode()) {
1398 type = ConflictNode.PARENT_WRITE;
1400 type = ConflictNode.FINE_WRITE;
1402 seseLock.setNodeType(newNode, type);
1404 if (newNode.isStallSiteNode()) {
1405 type = ConflictNode.PARENT_READ;
1407 type = ConflictNode.FINE_READ;
1409 seseLock.setNodeType(newNode, type);
1412 seseLock.addEdge(edge);
1413 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1414 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1415 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1417 // mark all fine edges between new node and nodes in the group as
1419 if (!conflictEdge.getVertexU().equals(newNode)) {
1420 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1422 seseLock.addConflictEdge(conflictEdge);
1423 fineToCover.remove(conflictEdge);
1425 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1426 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1428 seseLock.addConflictEdge(conflictEdge);
1429 fineToCover.remove(conflictEdge);
1435 break;// exit iterator loop
1440 HashSet<ConflictEdge> notCovered=new HashSet<ConflictEdge>();
1444 for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) {
1446 ConflictEdge edge = (ConflictEdge) iterator.next();
1447 if (seseLock.getConflictNodeSet().size() == 0) {
1449 if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
1450 // node has a coarse-grained edge with itself
1451 if (!(edge.getVertexU().isStallSiteNode())) {
1452 // and it is not parent
1453 type = ConflictNode.SCC;
1456 type = ConflictNode.PARENT_COARSE;
1458 type = ConflictNode.PARENT_WRITE;
1461 seseLock.addConflictNode(edge.getVertexU(), type);
1463 if (edge.getVertexU().isStallSiteNode()) {
1465 type = ConflictNode.PARENT_COARSE;
1467 if (edge.getVertexU().getWriteEffectSet().isEmpty()) {
1468 type = ConflictNode.PARENT_READ;
1470 type = ConflictNode.PARENT_WRITE;
1474 type = ConflictNode.COARSE;
1476 seseLock.addConflictNode(edge.getVertexU(), type);
1478 if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
1479 // node has a coarse-grained edge with itself
1480 if (!(edge.getVertexV().isStallSiteNode())) {
1481 // and it is not parent
1482 type = ConflictNode.SCC;
1485 type = ConflictNode.PARENT_COARSE;
1487 type = ConflictNode.PARENT_WRITE;
1490 seseLock.addConflictNode(edge.getVertexV(), type);
1492 if (edge.getVertexV().isStallSiteNode()) {
1494 type = ConflictNode.PARENT_COARSE;
1496 if (edge.getVertexV().getWriteEffectSet().isEmpty()) {
1497 type = ConflictNode.PARENT_READ;
1499 type = ConflictNode.PARENT_WRITE;
1503 type = ConflictNode.COARSE;
1505 seseLock.addConflictNode(edge.getVertexV(), type);
1508 coarseToCover.remove(edge);
1509 seseLock.addConflictEdge(edge);
1510 break;// exit iterator loop
1511 }// end of initial setup
1513 ConflictNode newNode;
1514 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1515 // new node has a coarse-grained edge to all fine-read, fine-write,
1519 if (newNode.isInVarNode() && (!seseLock.hasSelfCoarseEdge(newNode))
1520 && seseLock.hasCoarseEdgeWithParentCoarse(newNode)) {
1521 // this case can't be covered by this queue
1522 coarseToCover.remove(edge);
1523 notCovered.add(edge);
1527 if (seseLock.containsConflictNode(newNode)) {
1528 seseLock.addEdge(edge);
1529 coarseToCover.remove(edge);
1533 if (seseLock.hasSelfCoarseEdge(newNode)) {
1535 if (newNode.isStallSiteNode()) {
1536 type = ConflictNode.PARENT_COARSE;
1538 type = ConflictNode.SCC;
1540 seseLock.setNodeType(newNode, type);
1542 if (newNode.isStallSiteNode()) {
1543 type = ConflictNode.PARENT_COARSE;
1545 type = ConflictNode.COARSE;
1547 seseLock.setNodeType(newNode, type);
1550 seseLock.addEdge(edge);
1551 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1552 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1553 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1554 // mark all coarse edges between new node and nodes in the group
1556 if (!conflictEdge.getVertexU().equals(newNode)) {
1557 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1559 seseLock.addConflictEdge(conflictEdge);
1560 coarseToCover.remove(conflictEdge);
1562 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1563 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1565 seseLock.addConflictEdge(conflictEdge);
1566 coarseToCover.remove(conflictEdge);
1571 break;// exit iterator loop
1577 lockSet.add(seseLock);
1580 coarseToCover.addAll(notCovered);
1581 toCover.addAll(fineToCover);
1582 toCover.addAll(coarseToCover);
1586 conflictGraph2SESELock.put(conflictGraph, lockSet);
1589 public ConflictGraph getConflictGraph(FlatNode sese) {
1590 return sese2conflictGraph.get(sese);
1593 public Set<SESELock> getLockMappings(ConflictGraph graph) {
1594 return conflictGraph2SESELock.get(graph);
1597 public Set<FlatSESEEnterNode> getAllSESEs() {
1598 return rblockRel.getAllSESEs();
1601 public FlatSESEEnterNode getMainSESE() {
1602 return rblockRel.getMainSESE();
1605 public FlatSESEEnterNode getCallerProxySESE() {
1606 return rblockRel.getCallerProxySESE();
1609 public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks( FlatNode fn ) {
1610 return rblockRel.getPossibleExecutingRBlocks( fn );
1614 public void writeReports(String timeReport) throws java.io.IOException {
1616 BufferedWriter bw = new BufferedWriter(new FileWriter("ooojReport_summary.txt"));
1617 bw.write("OoOJava Analysis Results\n\n");
1618 bw.write(timeReport + "\n\n");
1619 printSESEHierarchy(bw);
1624 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
1625 while (methItr.hasNext()) {
1626 MethodDescriptor md = methItr.next();
1627 FlatMethod fm = state.getMethodFlat(md);
1629 bw = new BufferedWriter(new FileWriter("ooojReport_" +
1630 md.getClassMethodName() +
1631 md.getSafeMethodDescriptor() +
1633 bw.write("OoOJava Results for " + md + "\n-------------------\n");
1635 bw.write("Dynamic vars to manage:\n " + getContextTaskNames( fm ).getDynamicVarSet() );
1637 bw.write("\n\nLive-In, Root View\n------------------\n" + fm.printMethod(livenessGlobalView));
1638 bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults));
1639 bw.write("\n\nNot Available Results-Out\n---------------------\n" + fm.printMethod(notAvailableResults));
1640 bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans));
1646 private void printSESEHierarchy(BufferedWriter bw) throws java.io.IOException {
1647 bw.write("SESE Local Hierarchy\n--------------\n");
1648 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getLocalRootSESEs().iterator();
1649 while (rootItr.hasNext()) {
1650 FlatSESEEnterNode root = rootItr.next();
1651 printSESEHierarchyTree(bw, root, 0);
1655 private void printSESEHierarchyTree(BufferedWriter bw,
1656 FlatSESEEnterNode fsen,
1658 ) throws java.io.IOException {
1659 for (int i = 0; i < depth; ++i) {
1662 bw.write("- " + fsen.getPrettyIdentifier() + "\n");
1664 Iterator<FlatSESEEnterNode> childItr = fsen.getLocalChildren().iterator();
1665 while (childItr.hasNext()) {
1666 FlatSESEEnterNode fsenChild = childItr.next();
1667 printSESEHierarchyTree(bw, fsenChild, depth + 1);
1671 private void printSESEInfo(BufferedWriter bw) throws java.io.IOException {
1672 bw.write("\nSESE info\n-------------\n");
1673 Iterator<FlatSESEEnterNode> fsenItr = rblockRel.getAllSESEs().iterator();
1674 while( fsenItr.hasNext() ) {
1675 FlatSESEEnterNode fsen = fsenItr.next();
1677 bw.write("SESE " + fsen.getPrettyIdentifier());
1678 if( fsen.getIsLeafSESE() ) {
1679 bw.write(" (leaf)");
1683 bw.write(" in-set: " + fsen.getInVarSet() + "\n");
1684 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1685 while (tItr.hasNext()) {
1686 TempDescriptor inVar = tItr.next();
1687 if (fsen.getReadyInVarSet().contains(inVar)) {
1688 bw.write(" (ready) " + inVar + "\n");
1690 if (fsen.getStaticInVarSet().contains(inVar)) {
1691 bw.write(" (static) " + inVar + " from " + fsen.getStaticInVarSrc(inVar) + "\n");
1693 if (fsen.getDynamicInVarSet().contains(inVar)) {
1694 bw.write(" (dynamic)" + inVar + "\n");
1698 bw.write(" Dynamic vars to manage: " + getContextTaskNames( fsen ).getDynamicVarSet() + "\n");
1700 bw.write(" out-set: " + fsen.getOutVarSet() + "\n");
1702 bw.write(" local parent: " + fsen.getLocalParent() + "\n");
1703 bw.write(" local children: " + fsen.getLocalChildren() + "\n");
1705 bw.write(" possible parents: " + fsen.getParents() + "\n");
1706 bw.write(" possible children: " + fsen.getChildren() + "\n");