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 BuildStateMachines getBuildStateMachines() {
92 return buildStateMachines;
95 public OoOJavaAnalysis( State state,
99 ArrayReferencees arrayReferencees ) {
101 State.logEvent("Starting OoOJavaAnalysis");
103 this.typeUtil = typeUtil;
104 this.callGraph = callGraph;
105 this.maxSESEage = state.OOO_MAXSESEAGE;
107 livenessGlobalView = new Hashtable<FlatNode, Set<TempDescriptor>>();
108 livenessVirtualReads = new Hashtable<FlatNode, Set<TempDescriptor>>();
109 variableResults = new Hashtable<FlatNode, VarSrcTokTable>();
110 notAvailableResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
111 codePlans = new Hashtable<FlatNode, CodePlan>();
112 wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
113 notAvailableIntoSESE = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
114 sese2conflictGraph = new Hashtable<FlatNode, ConflictGraph>();
115 conflictGraph2SESELock = new Hashtable<ConflictGraph, HashSet<SESELock>>();
116 fn2contextTaskNames = new Hashtable<FlatNode, ContextTaskNames>();
117 fn2fm = new Hashtable<FlatNode, FlatMethod>();
119 // state machines support heap examiners with
120 // state transitions to improve precision
122 buildStateMachines = new BuildStateMachines();
125 // add all methods transitively reachable from the
126 // source's main to set for analysis
127 MethodDescriptor mdSourceEntry = typeUtil.getMain();
128 FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
130 descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
132 descriptorsToAnalyze.add(mdSourceEntry);
135 // 0th pass, setup a useful mapping of any flat node to the
136 // flat method it is a part of
137 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
138 while (methItr.hasNext()) {
139 Descriptor d = methItr.next();
140 FlatMethod fm = state.getMethodFlat( d );
141 buildFlatNodeToFlatMethod( fm );
143 State.logEvent("OoOJavaAnalysis Oth pass completed");
145 // 1st pass, find basic rblock relations & potential stall sites
146 rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
147 VarSrcTokTable.rblockRel = rblockRel;
149 State.logEvent("OoOJavaAnalysis 1st pass completed");
151 // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
152 methItr = descriptorsToAnalyze.iterator();
153 while (methItr.hasNext()) {
154 Descriptor d = methItr.next();
155 FlatMethod fm = state.getMethodFlat(d);
157 // note we can't use the general liveness analysis already in
158 // the compiler because this analysis is task-aware
159 livenessAnalysisBackward(fm);
162 State.logEvent("OoOJavaAnalysis 2nd pass completed");
164 // 3rd pass, variable analysis
165 methItr = descriptorsToAnalyze.iterator();
166 while (methItr.hasNext()) {
167 Descriptor d = methItr.next();
168 FlatMethod fm = state.getMethodFlat(d);
170 // starting from roots do a forward, fixed-point
171 // variable analysis for refinement and stalls
172 variableAnalysisForward(fm);
174 State.logEvent("OoOJavaAnalysis 3rd pass completed");
175 // 4th pass, compute liveness contribution from
176 // virtual reads discovered in variable pass
177 methItr = descriptorsToAnalyze.iterator();
178 while (methItr.hasNext()) {
179 Descriptor d = methItr.next();
180 FlatMethod fm = state.getMethodFlat(d);
181 livenessAnalysisBackward(fm);
183 State.logEvent("OoOJavaAnalysis 4th pass completed");
185 // 5th pass, use disjointness with NO FLAGGED REGIONS
186 // to compute taints and effects
188 disjointAnalysisTaints = new Pointer(state, typeUtil, callGraph, rblockRel, liveness, buildStateMachines);
189 ((Pointer)disjointAnalysisTaints).doAnalysis();
191 disjointAnalysisTaints =
192 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null,
193 rblockRel, buildStateMachines,
194 true ); // suppress output--this is an intermediate pass
196 State.logEvent("OoOJavaAnalysis 5th pass completed");
198 // 6th pass, not available analysis FOR VARIABLES!
199 methItr = descriptorsToAnalyze.iterator();
200 while (methItr.hasNext()) {
201 Descriptor d = methItr.next();
202 FlatMethod fm = state.getMethodFlat(d);
204 // compute what is not available at every program
205 // point, in a forward fixed-point pass
206 notAvailableForward(fm);
208 State.logEvent("OoOJavaAnalysis 6th pass completed");
209 // 7th pass, start conflict graphs where a parent's graph has a
210 // node for possibly conflicting children and its own stall sites
211 startConflictGraphs();
212 State.logEvent("OoOJavaAnalysis 7th pass completed");
213 // 8th pass, calculate all possible conflicts without using
214 // reachability info and identify set of FlatNew that next
215 // disjoint reach. analysis should flag
216 Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
217 calculateConflicts(sitesToFlag, false);
218 State.logEvent("OoOJavaAnalysis 8th pass completed");
220 // 9th pass, ask disjoint analysis to compute reachability
221 // for objects that may cause heap conflicts so the most
222 // efficient method to deal with conflict can be computed
224 disjointAnalysisReach =
225 new DisjointAnalysis(state, typeUtil, callGraph, liveness,
226 arrayReferencees, sitesToFlag,
227 null, // don't do effects analysis again!
228 null, // no BuildStateMachines needed
229 false // don't suppress progress output
231 State.logEvent("OoOJavaAnalysis 9th pass completed");
232 // 10th pass, calculate conflicts with reachability info
233 calculateConflicts(null, true);
234 State.logEvent("OoOJavaAnalysis 10th pass completed");
236 // in RCR/DFJ we want to do some extra processing on the
237 // state machines before they get handed off to code gen,
238 // and we're doing the same effect-conflict traversal needed
239 // to identify heap examiners that are weakly connected, so
240 // accomplish both at the same time
241 pruneMachinesAndFindWeaklyConnectedExaminers();
242 State.logEvent("OoOJavaAnalysis RCR pruneMachines pass completed");
245 // 11th pass, compiling memory Qs! The name "lock" is a legacy
246 // term for the heap dependence queue, or memQ as the runtime calls it
248 State.logEvent("OoOJavaAnalysis 11th pass completed");
250 // 12th pass, compute a plan for code injections
251 methItr = descriptorsToAnalyze.iterator();
252 while (methItr.hasNext()) {
253 Descriptor d = methItr.next();
254 FlatMethod fm = state.getMethodFlat(d);
255 codePlansForward(fm);
258 State.logEvent("OoOJavaAnalysis 12th pass completed");
260 // splice new IR nodes into graph after all
261 // analysis passes are complete
262 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
263 while (spliceItr.hasNext()) {
264 Map.Entry me = (Map.Entry) spliceItr.next();
265 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
266 fwdvn.spliceIntoIR();
268 State.logEvent("OoOJavaAnalysis 13th pass completed");
270 if (state.OOODEBUG) {
273 disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt");
274 writeConflictGraph();
275 } catch (IOException e) {}
277 State.logEvent("OoOJavaAnalysis completed");
281 private void buildFlatNodeToFlatMethod( FlatMethod fm ) {
282 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
283 flatNodesToVisit.add( fm );
285 Set<FlatNode> flatNodesVisited = new HashSet<FlatNode>();
287 while( !flatNodesToVisit.isEmpty() ) {
288 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
289 flatNodesToVisit.remove( fn );
290 flatNodesVisited.add( fn );
294 for( int i = 0; i < fn.numNext(); i++ ) {
295 FlatNode nn = fn.getNext( i );
296 if( !flatNodesVisited.contains( nn ) ) {
297 flatNodesToVisit.add( nn );
306 * Iterator iter = sese2conflictGraph.entrySet().iterator(); while
307 * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn =
308 * (FlatNode) e.getKey(); ConflictGraph conflictGraph = (ConflictGraph)
310 * System.out.println("---------------------------------------");
311 * System.out.println("CONFLICT GRAPH for " + fn); Set<String> keySet =
312 * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator();
313 * iterator.hasNext();) { String key = (String) iterator.next();
314 * ConflictNode node = conflictGraph.id2cn.get(key);
315 * System.out.println("key=" + key + " \n" + node.toStringAllEffects()); } }
321 private void writeFile(Set<FlatNew> sitesToFlag) {
324 BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt"));
326 for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext();) {
327 FlatNew fn = (FlatNew) iterator.next();
331 } catch (IOException e) {
338 private void livenessAnalysisBackward(FlatMethod fm) {
340 // flow backward across nodes to compute liveness, and
341 // take special care with sese enter/exit nodes that
342 // alter this from normal liveness analysis
343 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
344 flatNodesToVisit.add( fm.getFlatExit() );
346 while( !flatNodesToVisit.isEmpty() ) {
347 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
348 flatNodesToVisit.remove( fn );
350 Set<TempDescriptor> prev = livenessGlobalView.get( fn );
352 // merge sets from control flow joins
353 Set<TempDescriptor> livein = new HashSet<TempDescriptor>();
354 for (int i = 0; i < fn.numNext(); i++) {
355 FlatNode nn = fn.getNext( i );
356 Set<TempDescriptor> s = livenessGlobalView.get( nn );
362 Set<TempDescriptor> curr = liveness_nodeActions( fn, livein );
364 // if a new result, schedule backward nodes for analysis
365 if( !curr.equals( prev ) ) {
366 livenessGlobalView.put( fn, curr );
368 for( int i = 0; i < fn.numPrev(); i++ ) {
369 FlatNode nn = fn.getPrev( i );
370 flatNodesToVisit.add( nn );
376 private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
377 Set<TempDescriptor> liveIn
379 switch( fn.kind() ) {
381 case FKind.FlatSESEEnterNode: {
382 // add whatever is live-in at a task enter to that
384 FlatSESEEnterNode fsen = (FlatSESEEnterNode)fn;
385 if( liveIn != null ) {
386 fsen.addInVarSet( liveIn );
388 // no break, should also execute default actions
392 // handle effects of statement in reverse, writes then reads
393 TempDescriptor[] writeTemps = fn.writesTemps();
394 for( int i = 0; i < writeTemps.length; ++i ) {
395 liveIn.remove( writeTemps[i] );
397 // if we are analyzing code declared directly in a task,
398 FlatSESEEnterNode fsen = rblockRel.getLocalInnerRBlock( fn );
400 // check to see if we are writing to variables that will
401 // be live-out at the task's exit (and therefore should
402 // go in the task's out-var set)
403 FlatSESEExitNode fsexn = fsen.getFlatExit();
404 Set<TempDescriptor> livetemps = livenessGlobalView.get( fsexn );
405 if( livetemps != null && livetemps.contains( writeTemps[i] ) ) {
406 fsen.addOutVar( writeTemps[i] );
411 TempDescriptor[] readTemps = fn.readsTemps();
412 for( int i = 0; i < readTemps.length; ++i ) {
413 liveIn.add( readTemps[i] );
416 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
417 if( virtualReadTemps != null ) {
418 liveIn.addAll( virtualReadTemps );
428 private void variableAnalysisForward(FlatMethod fm) {
430 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
431 flatNodesToVisit.add(fm);
433 while (!flatNodesToVisit.isEmpty()) {
434 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
435 flatNodesToVisit.remove(fn);
437 VarSrcTokTable prev = variableResults.get(fn);
439 // merge sets from control flow joins
440 VarSrcTokTable curr = new VarSrcTokTable();
441 for (int i = 0; i < fn.numPrev(); i++) {
442 FlatNode nn = fn.getPrev(i);
443 VarSrcTokTable incoming = variableResults.get(nn);
444 curr.merge(incoming);
447 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
448 if( currentSESE == null ) {
449 currentSESE = rblockRel.getCallerProxySESE();
452 variable_nodeActions(fn, curr, currentSESE);
454 // if a new result, schedule forward nodes for analysis
455 if (!curr.equals(prev)) {
456 variableResults.put(fn, curr);
458 for (int i = 0; i < fn.numNext(); i++) {
459 FlatNode nn = fn.getNext(i);
460 flatNodesToVisit.add(nn);
466 private void variable_nodeActions(FlatNode fn,
467 VarSrcTokTable vstTable,
468 FlatSESEEnterNode currentSESE) {
472 case FKind.FlatSESEEnterNode: {
473 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
474 // ignore currently executing SESE, at this point
475 // the analysis considers a new instance is becoming
478 vstTable.assertConsistency();
482 case FKind.FlatSESEExitNode: {
483 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
485 // fsen is the child of currently executing tasks
486 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
488 // remap all of this child's children tokens to be
489 // from this child as the child exits
490 vstTable.remapChildTokens(fsen);
492 // liveness virtual reads are things that might be
493 // written by an SESE and should be added to the in-set
494 // anything virtually read by this SESE should be pruned
495 // of parent or sibling sources
496 Set<TempDescriptor> liveVars = livenessGlobalView.get(fn);
497 Set<TempDescriptor> fsenVirtReads =
498 vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen,
501 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
502 if (fsenVirtReadsOld != null) {
503 fsenVirtReads.addAll(fsenVirtReadsOld);
505 livenessVirtualReads.put(fn, fsenVirtReads);
507 // then all child out-set tokens are guaranteed
508 // to be filled in, so clobber those entries with
509 // the latest, clean sources
510 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
511 while (outVarItr.hasNext()) {
512 TempDescriptor outVar = outVarItr.next();
513 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
515 VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
516 vstTable.remove(outVar);
519 vstTable.assertConsistency();
523 case FKind.FlatOpNode: {
524 FlatOpNode fon = (FlatOpNode) fn;
526 if (fon.getOp().getOp() == Operation.ASSIGN) {
527 TempDescriptor lhs = fon.getDest();
528 TempDescriptor rhs = fon.getLeft();
530 vstTable.remove(lhs);
532 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
534 Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
535 while (itr.hasNext()) {
536 VariableSourceToken vst = itr.next();
538 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
541 // when we do x = y for variables, just copy over from a child,
542 // there are two cases:
543 // 1. if the current task is the caller proxy, any local root is a child
545 currentSESE.getIsCallerProxySESE() &&
546 rblockRel.getLocalRootSESEs().contains( vst.getSESE() );
548 // 2. if the child task is a locally-defined child of the current task
549 boolean case2 = currentSESE.getLocalChildren().contains( vst.getSESE() );
551 if( case1 || case2 ) {
552 // if the source comes from a child, copy it over
553 forAddition.add( new VariableSourceToken( ts,
560 // otherwise, stamp it as us as the source
561 forAddition.add( new VariableSourceToken( ts,
570 vstTable.addAll( forAddition );
572 // only break if this is an ASSIGN op node,
573 // otherwise fall through to default case
574 vstTable.assertConsistency();
579 // note that FlatOpNode's that aren't ASSIGN
580 // fall through to this default case
582 TempDescriptor[] writeTemps = fn.writesTemps();
583 if( writeTemps.length > 0 ) {
585 // for now, when writeTemps > 1, make sure
586 // its a call node, programmer enforce only
587 // doing stuff like calling a print routine
588 if( writeTemps.length > 1 ) {
589 assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
593 vstTable.remove( writeTemps[0] );
595 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
596 ts.add( writeTemps[0] );
598 vstTable.add( new VariableSourceToken( ts,
606 vstTable.assertConsistency();
613 private void notAvailableForward(FlatMethod fm) {
615 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
616 flatNodesToVisit.add(fm);
618 while (!flatNodesToVisit.isEmpty()) {
619 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
620 flatNodesToVisit.remove(fn);
622 Set<TempDescriptor> prev = notAvailableResults.get(fn);
624 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
625 for (int i = 0; i < fn.numPrev(); i++) {
626 FlatNode nn = fn.getPrev(i);
627 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
628 if (notAvailIn != null) {
629 curr.addAll(notAvailIn);
633 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
634 if( currentSESE == null ) {
635 currentSESE = rblockRel.getCallerProxySESE();
638 notAvailable_nodeActions(fn, curr, currentSESE);
640 // if a new result, schedule forward nodes for analysis
641 if (!curr.equals(prev)) {
642 notAvailableResults.put(fn, curr);
644 for (int i = 0; i < fn.numNext(); i++) {
645 FlatNode nn = fn.getNext(i);
646 flatNodesToVisit.add(nn);
652 private void notAvailable_nodeActions(FlatNode fn,
653 Set<TempDescriptor> notAvailSet,
654 FlatSESEEnterNode currentSESE
657 // any temps that are removed from the not available set
658 // at this node should be marked in this node's code plan
659 // as temps to be grabbed at runtime!
663 case FKind.FlatSESEEnterNode: {
664 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
666 // keep a copy of what's not available into the SESE
667 // and restore it at the matching exit node
668 Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
669 Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
670 while (tdItr.hasNext()) {
671 notAvailCopy.add(tdItr.next());
673 notAvailableIntoSESE.put(fsen, notAvailCopy);
678 case FKind.FlatSESEExitNode: {
679 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
680 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
682 notAvailSet.addAll(fsen.getOutVarSet());
684 Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
685 assert notAvailIn != null;
686 notAvailSet.addAll(notAvailIn);
689 case FKind.FlatMethod: {
693 case FKind.FlatOpNode: {
694 FlatOpNode fon = (FlatOpNode) fn;
696 if (fon.getOp().getOp() == Operation.ASSIGN) {
697 TempDescriptor lhs = fon.getDest();
698 TempDescriptor rhs = fon.getLeft();
700 // copy makes lhs same availability as rhs
701 if (notAvailSet.contains(rhs)) {
702 notAvailSet.add(lhs);
704 notAvailSet.remove(lhs);
707 // only break if this is an ASSIGN op node,
708 // otherwise fall through to default case
713 // note that FlatOpNode's that aren't ASSIGN
714 // fall through to this default case
716 TempDescriptor[] writeTemps = fn.writesTemps();
717 for (int i = 0; i < writeTemps.length; i++) {
718 TempDescriptor wTemp = writeTemps[i];
719 notAvailSet.remove(wTemp);
721 TempDescriptor[] readTemps = fn.readsTemps();
722 for (int i = 0; i < readTemps.length; i++) {
723 TempDescriptor rTemp = readTemps[i];
724 notAvailSet.remove(rTemp);
726 // if this variable has exactly one source, potentially
727 // get other things from this source as well
728 VarSrcTokTable vstTable = variableResults.get(fn);
730 VSTWrapper vstIfStatic = new VSTWrapper();
731 Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
733 if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
735 VariableSourceToken vst = vstIfStatic.vst;
737 Iterator<VariableSourceToken> availItr =
738 vstTable.get(vst.getSESE(), vst.getAge()).iterator();
740 // look through things that are also available from same source
741 while (availItr.hasNext()) {
742 VariableSourceToken vstAlsoAvail = availItr.next();
744 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
745 while (refVarItr.hasNext()) {
746 TempDescriptor refVarAlso = refVarItr.next();
748 // if a variable is available from the same source, AND it ALSO
749 // only comes from one statically known source, mark it available
750 VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
751 Integer srcTypeAlso =
752 vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed);
753 if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
754 notAvailSet.remove(refVarAlso);
766 private void codePlansForward(FlatMethod fm) {
768 // start from flat method top, visit every node in
769 // method exactly once
770 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
771 flatNodesToVisit.add(fm);
773 Set<FlatNode> visited = new HashSet<FlatNode>();
775 while (!flatNodesToVisit.isEmpty()) {
776 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
777 FlatNode fn = fnItr.next();
779 flatNodesToVisit.remove(fn);
782 // use incoming results as "dot statement" or just
783 // before the current statement
784 VarSrcTokTable dotSTtable = new VarSrcTokTable();
785 for (int i = 0; i < fn.numPrev(); i++) {
786 FlatNode nn = fn.getPrev(i);
787 dotSTtable.merge(variableResults.get(nn));
790 // find dt-st notAvailableSet also
791 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
792 for (int i = 0; i < fn.numPrev(); i++) {
793 FlatNode nn = fn.getPrev(i);
794 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
795 if (notAvailIn != null) {
796 dotSTnotAvailSet.addAll(notAvailIn);
800 Set<TempDescriptor> dotSTlive = livenessGlobalView.get(fn);
802 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
803 if( currentSESE == null ) {
804 currentSESE = rblockRel.getCallerProxySESE();
807 codePlans_nodeActions(fm, fn,
808 dotSTlive, dotSTtable, dotSTnotAvailSet,
811 for (int i = 0; i < fn.numNext(); i++) {
812 FlatNode nn = fn.getNext(i);
814 if (!visited.contains(nn)) {
815 flatNodesToVisit.add(nn);
821 private void codePlans_nodeActions(FlatMethod fm,
823 Set<TempDescriptor> liveSetIn,
824 VarSrcTokTable vstTableIn,
825 Set<TempDescriptor> notAvailSetIn,
826 FlatSESEEnterNode currentSESE) {
828 CodePlan plan = new CodePlan(currentSESE);
832 case FKind.FlatSESEEnterNode: {
833 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
835 // track the source types of the in-var set so generated
836 // code at this SESE issue can compute the number of
837 // dependencies properly
838 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
839 while (inVarItr.hasNext()) {
840 TempDescriptor inVar = inVarItr.next();
842 // when we get to an SESE enter node we change the
843 // currentSESE variable of this analysis to the
844 // child that is declared by the enter node, so
845 // in order to classify in-vars correctly, pass
846 // the parent SESE in--at other FlatNode types just
847 // use the currentSESE
848 FlatSESEEnterNode parent = rblockRel.getLocalInnerRBlock( fn );
849 if( parent == null ) {
850 parent = rblockRel.getCallerProxySESE();
853 VSTWrapper vstIfStatic = new VSTWrapper();
854 Integer srcType = vstTableIn.getRefVarSrcType(inVar, parent, vstIfStatic);
856 // the current SESE needs a local space to track the dynamic
857 // variable and the child needs space in its SESE record
858 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
859 fsen.addDynamicInVar(inVar);
860 addDynamicVar( fsen, fm, inVar );
862 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
863 fsen.addStaticInVar(inVar);
864 VariableSourceToken vst = vstIfStatic.vst;
865 fsen.putStaticInVar2src(inVar, vst);
866 fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
868 assert srcType.equals(VarSrcTokTable.SrcType_READY);
869 fsen.addReadyInVar(inVar);
874 case FKind.FlatSESEExitNode: {
875 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
876 //TODO! Shouldn't there be a code plan for task exit
877 // where the exiting task calculates whether its own
878 // siblings need variables from its children, so the
879 // exiter should copy those variables into its own out-set
880 // and make the available?
883 case FKind.FlatOpNode: {
884 FlatOpNode fon = (FlatOpNode) fn;
886 if (fon.getOp().getOp() == Operation.ASSIGN) {
887 TempDescriptor lhs = fon.getDest();
888 TempDescriptor rhs = fon.getLeft();
890 // if this is an op node, don't stall, copy
891 // source and delay until we need to use value
893 // ask whether lhs and rhs sources are dynamic, static, etc.
894 VSTWrapper vstIfStatic = new VSTWrapper();
895 Integer lhsSrcType = vstTableIn.getRefVarSrcType(lhs, currentSESE, vstIfStatic);
896 Integer rhsSrcType = vstTableIn.getRefVarSrcType(rhs, currentSESE, vstIfStatic);
898 if (rhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
899 // if rhs is dynamic going in, lhs will definitely be dynamic
900 // going out of this node, so track that here
901 plan.addDynAssign( lhs, rhs );
902 addDynamicVar( currentSESE, fm, lhs );
903 addDynamicVar( currentSESE, fm, rhs );
905 } else if (lhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
906 // otherwise, if the lhs is dynamic, but the rhs is not, we
907 // need to update the variable's dynamic source as "current SESE"
908 plan.addDynAssign(lhs);
911 // only break if this is an ASSIGN op node,
912 // otherwise fall through to default case
917 // note that FlatOpNode's that aren't ASSIGN
918 // fall through to this default case
921 // a node with no live set has nothing to stall for
922 if (liveSetIn == null) {
926 TempDescriptor[] readarray = fn.readsTemps();
927 for (int i = 0; i < readarray.length; i++) {
928 TempDescriptor readtmp = readarray[i];
930 // ignore temps that are definitely available
931 // when considering to stall on it
932 if (!notAvailSetIn.contains(readtmp)) {
936 // check the source type of this variable
937 VSTWrapper vstIfStatic = new VSTWrapper();
938 Integer srcType = vstTableIn.getRefVarSrcType(readtmp, currentSESE, vstIfStatic);
940 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
941 // 1) It is not clear statically where this variable will
942 // come from, so dynamically we must keep track
943 // along various control paths, and therefore when we stall,
944 // just stall for the exact thing we need and move on
945 plan.addDynamicStall( readtmp );
946 addDynamicVar( currentSESE, fm, readtmp );
948 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
949 // 2) Single token/age pair: Stall for token/age pair, and copy
950 // all live variables with same token/age pair at the same
951 // time. This is the same stuff that the notavaialable analysis
952 // marks as now available.
953 VariableSourceToken vst = vstIfStatic.vst;
955 Iterator<VariableSourceToken> availItr =
956 vstTableIn.get(vst.getSESE(), vst.getAge()).iterator();
958 while (availItr.hasNext()) {
959 VariableSourceToken vstAlsoAvail = availItr.next();
961 // only grab additional stuff that is live
962 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
964 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
965 while (refVarItr.hasNext()) {
966 TempDescriptor refVar = refVarItr.next();
967 if (liveSetIn.contains(refVar)) {
972 if (!copySet.isEmpty()) {
973 plan.addStall2CopySet(vstAlsoAvail, copySet);
978 // the other case for srcs is READY, so do nothing
981 // assert that everything being stalled for is in the
982 // "not available" set coming into this flat node and
983 // that every VST identified is in the possible "stall set"
984 // that represents VST's from children SESE's
992 // identify sese-age pairs that are statically useful
993 // and should have an associated SESE variable in code
994 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
995 // AND ALWAYS GIVE NAMES TO LOCAL PARENTS
996 Set<VariableSourceToken> staticSet = vstTableIn.get();
997 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
998 while (vstItr.hasNext()) {
999 VariableSourceToken vst = vstItr.next();
1001 // the caller proxy generates useful analysis facts, but we
1002 // never need to generate another name for it in code (it is
1003 // ALWAYS the task executing the local method context)
1004 if( vst.getSESE().getIsCallerProxySESE() ) {
1008 SESEandAgePair sap = new SESEandAgePair( vst.getSESE(), vst.getAge() );
1009 sap.getSESE().mustTrackAtLeastAge( sap.getAge() );
1011 FlatSESEEnterNode sese = currentSESE;
1012 while( sese != null ) {
1013 addNeededStaticName( sese, fm, sap );
1014 sese = sese.getLocalParent();
1018 codePlans.put(fn, plan);
1020 // if any variables at this-node-*dot* have a static source (exactly one
1022 // but go to a dynamic source at next-node-*dot*, create a new IR graph
1023 // node on that edge to track the sources dynamically
1024 VarSrcTokTable thisVstTable = variableResults.get(fn);
1025 for (int i = 0; i < fn.numNext(); i++) {
1026 FlatNode nn = fn.getNext(i);
1027 VarSrcTokTable nextVstTable = variableResults.get(nn);
1028 Set<TempDescriptor> nextLiveIn = livenessGlobalView.get(nn);
1030 // the table can be null if it is one of the few IR nodes
1031 // completely outside of the root SESE scope
1032 if (nextVstTable != null && nextLiveIn != null) {
1034 Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
1035 thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, currentSESE);
1037 if (!readyOrStatic2dynamicSet.isEmpty()) {
1039 // either add these results to partial fixed-point result
1040 // or make a new one if we haven't made any here yet
1041 FlatEdge fe = new FlatEdge(fn, nn);
1042 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe);
1044 if (fwdvn == null) {
1045 fwdvn = new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, currentSESE);
1046 wdvNodesToSpliceIn.put(fe, fwdvn);
1048 fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet);
1055 private void addDynamicVar( FlatSESEEnterNode fsen,
1057 TempDescriptor var ) {
1060 if( fsen.getIsCallerProxySESE() ) {
1061 // attach the dynamic variable to track to
1062 // the flat method, so it can be declared at entry
1065 // otherwise the code context is a task body
1069 ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1071 ctn = new ContextTaskNames();
1074 ctn.addDynamicVar( var );
1075 fn2contextTaskNames.put( fnContext, ctn );
1078 private void addNeededStaticName( FlatSESEEnterNode fsen,
1080 SESEandAgePair sap ) {
1083 if( fsen.getIsCallerProxySESE() ) {
1084 // attach the dynamic variable to track to
1085 // the flat method, so it can be declared at entry
1088 // otherwise the code context is a task body
1092 ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1094 ctn = new ContextTaskNames();
1097 ctn.addNeededStaticName( sap );
1099 fn2contextTaskNames.put( fnContext, ctn );
1103 private void startConflictGraphs() {
1105 // first, for each task, consider whether it has any children, and if
1106 // effects analysis says they should be a conflict node in the that
1107 // parent's conflict graph
1108 Set<FlatSESEEnterNode> allSESEs = rblockRel.getAllSESEs();
1109 for( Iterator iterator = allSESEs.iterator(); iterator.hasNext(); ) {
1111 FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
1112 if( parent.getIsLeafSESE() ) {
1116 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1117 ConflictGraph conflictGraph = sese2conflictGraph.get( parent );
1118 assert conflictGraph == null;
1119 conflictGraph = new ConflictGraph( state );
1121 Set<FlatSESEEnterNode> children = parent.getChildren();
1122 for( Iterator iterator2 = children.iterator(); iterator2.hasNext(); ) {
1123 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
1124 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get( child );
1125 conflictGraph.addLiveIn( taint2Effects );
1128 sese2conflictGraph.put( parent, conflictGraph );
1131 // then traverse all methods looking for potential stall sites, and
1132 // add those stall sites as nodes in any task's conflict graph that
1133 // might be executing at the point of the stall site
1134 Iterator<MethodDescriptor> descItr = descriptorsToAnalyze.iterator();
1135 while( descItr.hasNext() ) {
1136 MethodDescriptor md = descItr.next();
1137 FlatMethod fm = state.getMethodFlat( md );
1139 addStallSitesToConflictGraphs( fm );
1144 private void addStallSitesToConflictGraphs( FlatMethod fm ) {
1146 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1147 flatNodesToVisit.add( fm );
1149 Set<FlatNode> visited = new HashSet<FlatNode>();
1151 while( !flatNodesToVisit.isEmpty() ) {
1152 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1153 flatNodesToVisit.remove( fn );
1156 Set<FlatSESEEnterNode> currentSESEs =
1157 rblockRel.getPossibleExecutingRBlocks( fn );
1159 conflictGraph_nodeAction( fn, currentSESEs );
1161 // schedule forward nodes for analysis
1162 for( int i = 0; i < fn.numNext(); i++ ) {
1163 FlatNode nn = fn.getNext( i );
1164 if( !visited.contains( nn ) ) {
1165 flatNodesToVisit.add( nn );
1171 private void conflictGraph_nodeAction( FlatNode fn,
1172 Set<FlatSESEEnterNode> currentSESEs
1175 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1177 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get( fn );
1180 // repeat the process of adding a stall site to a conflict graph
1181 // for each task that might be executing at a possible stall site
1182 Iterator<FlatSESEEnterNode> seseItr = currentSESEs.iterator();
1183 while( seseItr.hasNext() ) {
1184 FlatSESEEnterNode currentSESE = seseItr.next();
1186 ConflictGraph conflictGraph = sese2conflictGraph.get( currentSESE );
1187 if( conflictGraph == null ) {
1188 assert currentSESE.getIsLeafSESE();
1195 switch( fn.kind() ) {
1198 case FKind.FlatFieldNode:
1199 case FKind.FlatElementNode: {
1201 if( fn instanceof FlatFieldNode ) {
1202 FlatFieldNode ffn = (FlatFieldNode) fn;
1205 FlatElementNode fen = (FlatElementNode) fn;
1209 conflictGraph.addStallSite( taint2Effects, rhs );
1213 case FKind.FlatSetFieldNode:
1214 case FKind.FlatSetElementNode: {
1216 if( fn instanceof FlatSetFieldNode ) {
1217 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1218 lhs = fsfn.getDst();
1219 rhs = fsfn.getSrc();
1221 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1222 lhs = fsen.getDst();
1223 rhs = fsen.getSrc();
1226 conflictGraph.addStallSite( taint2Effects, rhs );
1227 conflictGraph.addStallSite( taint2Effects, lhs );
1231 case FKind.FlatCall: {
1232 FlatCall fc = (FlatCall) fn;
1235 conflictGraph.addStallSite( taint2Effects, lhs );
1240 if( conflictGraph.id2cn.size() > 0 ) {
1241 sese2conflictGraph.put( currentSESE, conflictGraph );
1247 private void calculateConflicts( Set<FlatNew> sitesToFlag,
1248 boolean useReachInfo ) {
1250 // decide fine-grain edge or coarse-grain edge among all vertexes by
1251 // pair-wise comparison
1252 Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
1253 while (seseIter.hasNext()) {
1254 FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next();
1255 ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
1258 // clear current conflict before recalculating with reachability info
1259 conflictGraph.clearAllConflictEdge();
1260 conflictGraph.setDisJointAnalysis(disjointAnalysisReach);
1261 conflictGraph.setFMEnclosing(sese.getfmEnclosing());
1263 conflictGraph.analyzeConflicts(sitesToFlag, useReachInfo);
1264 sese2conflictGraph.put(sese, conflictGraph);
1269 private void writeConflictGraph() {
1270 Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
1271 while (keyEnum.hasMoreElements()) {
1272 FlatNode key = (FlatNode) keyEnum.nextElement();
1273 ConflictGraph cg = sese2conflictGraph.get(key);
1275 if (cg.hasConflictEdge()) {
1276 cg.writeGraph("ConflictGraphFor" + key, false);
1278 } catch (IOException e) {
1279 System.out.println("Error writing");
1286 // the traversal for pruning state machines and finding
1287 // machines that are weakly connected BOTH consider conflicting
1288 // effects between heap roots, so it is smart to compute all of
1290 public void pruneMachinesAndFindWeaklyConnectedExaminers() {
1293 // TODO, calcualte the set of taints that lead to conflicts (for which
1294 // traversers must be built...)
1296 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1298 // visit every conflict graph once, so iterate through the
1299 // the non-leaf tasks to find them all
1300 Set<FlatSESEEnterNode> allSESEs = rblockRel.getAllSESEs();
1301 for( Iterator allItr = allSESEs.iterator(); allItr.hasNext(); ) {
1303 FlatSESEEnterNode parent = (FlatSESEEnterNode) allItr.next();
1304 if( parent.getIsLeafSESE() ) {
1308 ConflictGraph conflictGraph = sese2conflictGraph.get( parent );
1309 assert conflictGraph != null;
1311 // from the conflict graph we want to extract all conflicting effects
1312 // and use them to identify (1) weakly connected heap examiners and
1313 // (2) states/examiner nodes with a conflicting effect that will later
1314 // support the examiner pruning process
1315 Hashtable<Taint, Set<Effect>> conflicts = conflictGraph.getConflictEffectSet( fsen ) );
1323 private void synthesizeLocks() {
1324 // for every conflict graph, generate a set of memory queues
1325 // (called SESELock in this code!) to cover the graph
1326 Set<Map.Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
1327 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
1328 Map.Entry<FlatNode, ConflictGraph> graphEntry = (Map.Entry<FlatNode, ConflictGraph>) iterator.next();
1329 FlatNode sese = graphEntry.getKey();
1330 ConflictGraph conflictGraph = graphEntry.getValue();
1331 calculateCovering(conflictGraph);
1335 private void calculateCovering(ConflictGraph conflictGraph) {
1336 uniqueLockSetId = 0; // reset lock counter for every new conflict graph
1337 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1338 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1339 HashSet<SESELock> lockSet = new HashSet<SESELock>();
1341 Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1342 for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
1343 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1344 if (conflictEdge.isCoarseEdge()) {
1345 coarseToCover.add(conflictEdge);
1347 fineToCover.add(conflictEdge);
1351 HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
1352 toCover.addAll(fineToCover);
1353 toCover.addAll(coarseToCover);
1355 while (!toCover.isEmpty()) {
1357 SESELock seseLock = new SESELock();
1358 seseLock.setID(uniqueLockSetId++);
1362 do { // fine-grained edge
1366 for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) {
1369 ConflictEdge edge = (ConflictEdge) iterator.next();
1370 if (seseLock.getConflictNodeSet().size() == 0) {
1372 if (seseLock.isWriteNode(edge.getVertexU())) {
1373 // mark as fine_write
1374 if (edge.getVertexU().isStallSiteNode()) {
1375 type = ConflictNode.PARENT_WRITE;
1377 type = ConflictNode.FINE_WRITE;
1379 seseLock.addConflictNode(edge.getVertexU(), type);
1381 // mark as fine_read
1382 if (edge.getVertexU().isStallSiteNode()) {
1383 type = ConflictNode.PARENT_READ;
1385 type = ConflictNode.FINE_READ;
1387 seseLock.addConflictNode(edge.getVertexU(), type);
1389 if (edge.getVertexV() != edge.getVertexU()) {
1390 if (seseLock.isWriteNode(edge.getVertexV())) {
1391 // mark as fine_write
1392 if (edge.getVertexV().isStallSiteNode()) {
1393 type = ConflictNode.PARENT_WRITE;
1395 type = ConflictNode.FINE_WRITE;
1397 seseLock.addConflictNode(edge.getVertexV(), type);
1399 // mark as fine_read
1400 if (edge.getVertexV().isStallSiteNode()) {
1401 type = ConflictNode.PARENT_READ;
1403 type = ConflictNode.FINE_READ;
1405 seseLock.addConflictNode(edge.getVertexV(), type);
1409 seseLock.addConflictEdge(edge);
1410 fineToCover.remove(edge);
1411 break;// exit iterator loop
1412 }// end of initial setup
1414 ConflictNode newNode;
1415 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1416 // new node has a fine-grained edge to all current node
1417 // If there is a coarse grained edge where need a fine edge, it's
1418 // okay to add the node
1419 // but the edge must remain uncovered.
1423 if (seseLock.containsConflictNode(newNode)) {
1424 seseLock.addEdge(edge);
1425 fineToCover.remove(edge);
1429 if (seseLock.isWriteNode(newNode)) {
1430 if (newNode.isStallSiteNode()) {
1431 type = ConflictNode.PARENT_WRITE;
1433 type = ConflictNode.FINE_WRITE;
1435 seseLock.setNodeType(newNode, type);
1437 if (newNode.isStallSiteNode()) {
1438 type = ConflictNode.PARENT_READ;
1440 type = ConflictNode.FINE_READ;
1442 seseLock.setNodeType(newNode, type);
1445 seseLock.addEdge(edge);
1446 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1447 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1448 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1450 // mark all fine edges between new node and nodes in the group as
1452 if (!conflictEdge.getVertexU().equals(newNode)) {
1453 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1455 seseLock.addConflictEdge(conflictEdge);
1456 fineToCover.remove(conflictEdge);
1458 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1459 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1461 seseLock.addConflictEdge(conflictEdge);
1462 fineToCover.remove(conflictEdge);
1468 break;// exit iterator loop
1473 HashSet<ConflictEdge> notCovered=new HashSet<ConflictEdge>();
1477 for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) {
1479 ConflictEdge edge = (ConflictEdge) iterator.next();
1480 if (seseLock.getConflictNodeSet().size() == 0) {
1482 if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
1483 // node has a coarse-grained edge with itself
1484 if (!(edge.getVertexU().isStallSiteNode())) {
1485 // and it is not parent
1486 type = ConflictNode.SCC;
1489 type = ConflictNode.PARENT_COARSE;
1491 type = ConflictNode.PARENT_WRITE;
1494 seseLock.addConflictNode(edge.getVertexU(), type);
1496 if (edge.getVertexU().isStallSiteNode()) {
1498 type = ConflictNode.PARENT_COARSE;
1500 if (edge.getVertexU().getWriteEffectSet().isEmpty()) {
1501 type = ConflictNode.PARENT_READ;
1503 type = ConflictNode.PARENT_WRITE;
1507 type = ConflictNode.COARSE;
1509 seseLock.addConflictNode(edge.getVertexU(), type);
1511 if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
1512 // node has a coarse-grained edge with itself
1513 if (!(edge.getVertexV().isStallSiteNode())) {
1514 // and it is not parent
1515 type = ConflictNode.SCC;
1518 type = ConflictNode.PARENT_COARSE;
1520 type = ConflictNode.PARENT_WRITE;
1523 seseLock.addConflictNode(edge.getVertexV(), type);
1525 if (edge.getVertexV().isStallSiteNode()) {
1527 type = ConflictNode.PARENT_COARSE;
1529 if (edge.getVertexV().getWriteEffectSet().isEmpty()) {
1530 type = ConflictNode.PARENT_READ;
1532 type = ConflictNode.PARENT_WRITE;
1536 type = ConflictNode.COARSE;
1538 seseLock.addConflictNode(edge.getVertexV(), type);
1541 coarseToCover.remove(edge);
1542 seseLock.addConflictEdge(edge);
1543 break;// exit iterator loop
1544 }// end of initial setup
1546 ConflictNode newNode;
1547 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1548 // new node has a coarse-grained edge to all fine-read, fine-write,
1552 if (newNode.isInVarNode() && (!seseLock.hasSelfCoarseEdge(newNode))
1553 && seseLock.hasCoarseEdgeWithParentCoarse(newNode)) {
1554 // this case can't be covered by this queue
1555 coarseToCover.remove(edge);
1556 notCovered.add(edge);
1560 if (seseLock.containsConflictNode(newNode)) {
1561 seseLock.addEdge(edge);
1562 coarseToCover.remove(edge);
1566 if (seseLock.hasSelfCoarseEdge(newNode)) {
1568 if (newNode.isStallSiteNode()) {
1569 type = ConflictNode.PARENT_COARSE;
1571 type = ConflictNode.SCC;
1573 seseLock.setNodeType(newNode, type);
1575 if (newNode.isStallSiteNode()) {
1576 type = ConflictNode.PARENT_COARSE;
1578 type = ConflictNode.COARSE;
1580 seseLock.setNodeType(newNode, type);
1583 seseLock.addEdge(edge);
1584 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1585 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1586 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1587 // mark all coarse edges between new node and nodes in the group
1589 if (!conflictEdge.getVertexU().equals(newNode)) {
1590 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1592 seseLock.addConflictEdge(conflictEdge);
1593 coarseToCover.remove(conflictEdge);
1595 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1596 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1598 seseLock.addConflictEdge(conflictEdge);
1599 coarseToCover.remove(conflictEdge);
1604 break;// exit iterator loop
1610 lockSet.add(seseLock);
1613 coarseToCover.addAll(notCovered);
1614 toCover.addAll(fineToCover);
1615 toCover.addAll(coarseToCover);
1619 conflictGraph2SESELock.put(conflictGraph, lockSet);
1622 public ConflictGraph getConflictGraph(FlatNode sese) {
1623 return sese2conflictGraph.get(sese);
1626 public Set<SESELock> getLockMappings(ConflictGraph graph) {
1627 return conflictGraph2SESELock.get(graph);
1630 public Set<FlatSESEEnterNode> getAllSESEs() {
1631 return rblockRel.getAllSESEs();
1634 public FlatSESEEnterNode getMainSESE() {
1635 return rblockRel.getMainSESE();
1638 public FlatSESEEnterNode getCallerProxySESE() {
1639 return rblockRel.getCallerProxySESE();
1642 public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks( FlatNode fn ) {
1643 return rblockRel.getPossibleExecutingRBlocks( fn );
1647 public void writeReports(String timeReport) throws java.io.IOException {
1649 BufferedWriter bw = new BufferedWriter(new FileWriter("ooojReport_summary.txt"));
1650 bw.write("OoOJava Analysis Results\n\n");
1651 bw.write(timeReport + "\n\n");
1652 printSESEHierarchy(bw);
1657 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
1658 while (methItr.hasNext()) {
1659 MethodDescriptor md = methItr.next();
1660 FlatMethod fm = state.getMethodFlat(md);
1662 bw = new BufferedWriter(new FileWriter("ooojReport_" +
1663 md.getClassMethodName() +
1664 md.getSafeMethodDescriptor() +
1666 bw.write("OoOJava Results for " + md + "\n-------------------\n");
1668 bw.write("Dynamic vars to manage:\n " + getContextTaskNames( fm ).getDynamicVarSet() );
1670 bw.write("\n\nLive-In, Root View\n------------------\n" + fm.printMethod(livenessGlobalView));
1671 bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults));
1672 bw.write("\n\nNot Available Results-Out\n---------------------\n" + fm.printMethod(notAvailableResults));
1673 bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans));
1679 private void printSESEHierarchy(BufferedWriter bw) throws java.io.IOException {
1680 bw.write("SESE Local Hierarchy\n--------------\n");
1681 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getLocalRootSESEs().iterator();
1682 while (rootItr.hasNext()) {
1683 FlatSESEEnterNode root = rootItr.next();
1684 printSESEHierarchyTree(bw, root, 0);
1688 private void printSESEHierarchyTree(BufferedWriter bw,
1689 FlatSESEEnterNode fsen,
1691 ) throws java.io.IOException {
1692 for (int i = 0; i < depth; ++i) {
1695 bw.write("- " + fsen.getPrettyIdentifier() + "\n");
1697 Iterator<FlatSESEEnterNode> childItr = fsen.getLocalChildren().iterator();
1698 while (childItr.hasNext()) {
1699 FlatSESEEnterNode fsenChild = childItr.next();
1700 printSESEHierarchyTree(bw, fsenChild, depth + 1);
1704 private void printSESEInfo(BufferedWriter bw) throws java.io.IOException {
1705 bw.write("\nSESE info\n-------------\n");
1706 Iterator<FlatSESEEnterNode> fsenItr = rblockRel.getAllSESEs().iterator();
1707 while( fsenItr.hasNext() ) {
1708 FlatSESEEnterNode fsen = fsenItr.next();
1710 bw.write("SESE " + fsen.getPrettyIdentifier());
1711 if( fsen.getIsLeafSESE() ) {
1712 bw.write(" (leaf)");
1716 bw.write(" in-set: " + fsen.getInVarSet() + "\n");
1717 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1718 while (tItr.hasNext()) {
1719 TempDescriptor inVar = tItr.next();
1720 if (fsen.getReadyInVarSet().contains(inVar)) {
1721 bw.write(" (ready) " + inVar + "\n");
1723 if (fsen.getStaticInVarSet().contains(inVar)) {
1724 bw.write(" (static) " + inVar + " from " + fsen.getStaticInVarSrc(inVar) + "\n");
1726 if (fsen.getDynamicInVarSet().contains(inVar)) {
1727 bw.write(" (dynamic)" + inVar + "\n");
1731 bw.write(" Dynamic vars to manage: " + getContextTaskNames( fsen ).getDynamicVarSet() + "\n");
1733 bw.write(" out-set: " + fsen.getOutVarSet() + "\n");
1735 bw.write(" local parent: " + fsen.getLocalParent() + "\n");
1736 bw.write(" local children: " + fsen.getLocalChildren() + "\n");
1738 bw.write(" possible parents: " + fsen.getParents() + "\n");
1739 bw.write(" possible children: " + fsen.getChildren() + "\n");