1 package Analysis.OoOJava;
7 import Analysis.CallGraph.*;
8 import Analysis.Disjoint.*;
9 import Analysis.Pointer.*;
13 public class OoOJavaAnalysis {
15 // data from the compiler
17 private TypeUtil typeUtil;
18 private CallGraph callGraph;
19 private RBlockRelationAnalysis rblockRel;
20 private HeapAnalysis disjointAnalysisTaints;
21 private DisjointAnalysis disjointAnalysisReach;
22 private BuildStateMachines buildStateMachines;
24 private Set<MethodDescriptor> descriptorsToAnalyze;
26 private Hashtable<FlatNode, Set<TempDescriptor>> livenessGlobalView;
27 private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
28 private Hashtable<FlatNode, VarSrcTokTable> variableResults;
29 private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
30 private Hashtable<FlatNode, CodePlan> codePlans;
32 private Hashtable<FlatSESEEnterNode, Set<TempDescriptor>> notAvailableIntoSESE;
34 private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
36 private Hashtable<FlatNode, ContextTaskNames> fn2contextTaskNames;
38 // get the flat method that contains any given flat node
39 private Hashtable<FlatNode, FlatMethod> fn2fm;
41 // temporal data structures to track analysis progress.
42 static private int uniqueLockSetId = 0;
43 // mapping of a conflict graph to its compiled lock
44 private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraph2SESELock;
45 // mapping of a sese block to its conflict graph
46 private Hashtable<FlatNode, ConflictGraph> sese2conflictGraph;
48 public static int maxSESEage = -1;
50 public int getMaxSESEage() {
55 public CodePlan getCodePlan(FlatNode fn) {
56 CodePlan cp = codePlans.get(fn);
60 public Set<FlatNode> getNodesWithPlans() {
61 return codePlans.keySet();
64 public ContextTaskNames getContextTaskNames( FlatMethod fm ) {
65 ContextTaskNames out = fn2contextTaskNames.get( fm );
67 out = new ContextTaskNames();
72 public ContextTaskNames getContextTaskNames( FlatSESEEnterNode fsen ) {
73 ContextTaskNames out = fn2contextTaskNames.get( fsen );
75 out = new ContextTaskNames();
80 public FlatMethod getContainingFlatMethod( FlatNode fn ) {
81 FlatMethod fm = fn2fm.get( fn );
86 public HeapAnalysis getDisjointAnalysis() {
87 return disjointAnalysisTaints;
90 public BuildStateMachines getBuildStateMachines() {
91 return buildStateMachines;
94 public OoOJavaAnalysis( State state,
98 ArrayReferencees arrayReferencees ) {
100 State.logEvent("Starting OoOJavaAnalysis");
102 this.typeUtil = typeUtil;
103 this.callGraph = callGraph;
104 this.maxSESEage = state.OOO_MAXSESEAGE;
106 livenessGlobalView = new Hashtable<FlatNode, Set<TempDescriptor>>();
107 livenessVirtualReads = new Hashtable<FlatNode, Set<TempDescriptor>>();
108 variableResults = new Hashtable<FlatNode, VarSrcTokTable>();
109 notAvailableResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
110 codePlans = new Hashtable<FlatNode, CodePlan>();
111 wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
112 notAvailableIntoSESE = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
113 sese2conflictGraph = new Hashtable<FlatNode, ConflictGraph>();
114 conflictGraph2SESELock = new Hashtable<ConflictGraph, HashSet<SESELock>>();
115 fn2contextTaskNames = new Hashtable<FlatNode, ContextTaskNames>();
116 fn2fm = new Hashtable<FlatNode, FlatMethod>();
118 // state machines support heap examiners with
119 // state transitions to improve precision
121 buildStateMachines = new BuildStateMachines();
124 // add all methods transitively reachable from the
125 // source's main to set for analysis
126 MethodDescriptor mdSourceEntry = typeUtil.getMain();
127 FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
129 descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
131 descriptorsToAnalyze.add(mdSourceEntry);
134 // 0th pass, setup a useful mapping of any flat node to the
135 // flat method it is a part of
136 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
137 while (methItr.hasNext()) {
138 Descriptor d = methItr.next();
139 FlatMethod fm = state.getMethodFlat( d );
140 buildFlatNodeToFlatMethod( fm );
142 State.logEvent("OoOJavaAnalysis Oth pass completed");
144 // 1st pass, find basic rblock relations & potential stall sites
145 rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
146 VarSrcTokTable.rblockRel = rblockRel;
148 State.logEvent("OoOJavaAnalysis 1st pass completed");
150 // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
151 methItr = descriptorsToAnalyze.iterator();
152 while (methItr.hasNext()) {
153 Descriptor d = methItr.next();
154 FlatMethod fm = state.getMethodFlat(d);
156 // note we can't use the general liveness analysis already in
157 // the compiler because this analysis is task-aware
158 livenessAnalysisBackward(fm);
161 State.logEvent("OoOJavaAnalysis 2nd pass completed");
163 // 3rd pass, variable analysis
164 methItr = descriptorsToAnalyze.iterator();
165 while (methItr.hasNext()) {
166 Descriptor d = methItr.next();
167 FlatMethod fm = state.getMethodFlat(d);
169 // starting from roots do a forward, fixed-point
170 // variable analysis for refinement and stalls
171 variableAnalysisForward(fm);
173 State.logEvent("OoOJavaAnalysis 3rd pass completed");
174 // 4th pass, compute liveness contribution from
175 // virtual reads discovered in variable pass
176 methItr = descriptorsToAnalyze.iterator();
177 while (methItr.hasNext()) {
178 Descriptor d = methItr.next();
179 FlatMethod fm = state.getMethodFlat(d);
180 livenessAnalysisBackward(fm);
182 State.logEvent("OoOJavaAnalysis 4th pass completed");
184 // 5th pass, use disjointness with NO FLAGGED REGIONS
185 // to compute taints and effects
187 disjointAnalysisTaints = new Pointer(state, typeUtil, callGraph, rblockRel, liveness, buildStateMachines);
188 ((Pointer)disjointAnalysisTaints).doAnalysis();
190 disjointAnalysisTaints =
191 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null,
192 rblockRel, buildStateMachines,
193 true ); // suppress output--this is an intermediate pass
195 State.logEvent("OoOJavaAnalysis 5th pass completed");
197 // 6th pass, not available analysis FOR VARIABLES!
198 methItr = descriptorsToAnalyze.iterator();
199 while (methItr.hasNext()) {
200 Descriptor d = methItr.next();
201 FlatMethod fm = state.getMethodFlat(d);
203 // compute what is not available at every program
204 // point, in a forward fixed-point pass
205 notAvailableForward(fm);
207 State.logEvent("OoOJavaAnalysis 6th pass completed");
208 // 7th pass, start conflict graphs where a parent's graph has a
209 // node for possibly conflicting children and its own stall sites
210 startConflictGraphs();
211 State.logEvent("OoOJavaAnalysis 7th pass completed");
212 // 8th pass, calculate all possible conflicts without using
213 // reachability info and identify set of FlatNew that next
214 // disjoint reach. analysis should flag
215 Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
216 calculateConflicts(sitesToFlag, false);
217 State.logEvent("OoOJavaAnalysis 8th pass completed");
219 // 9th pass, ask disjoint analysis to compute reachability
220 // for objects that may cause heap conflicts so the most
221 // efficient method to deal with conflict can be computed
223 disjointAnalysisReach =
224 new DisjointAnalysis(state, typeUtil, callGraph, liveness,
225 arrayReferencees, sitesToFlag,
226 null, // don't do effects analysis again!
227 null, // no BuildStateMachines needed
228 false // don't suppress progress output
230 State.logEvent("OoOJavaAnalysis 9th pass completed");
231 // 10th pass, calculate conflicts with reachability info
232 calculateConflicts(null, true);
233 State.logEvent("OoOJavaAnalysis 10th pass completed");
235 // in RCR/DFJ we want to do some extra processing on the
236 // state machines before they get handed off to code gen,
237 // and we're doing the same effect-conflict traversal needed
238 // to identify heap examiners that are weakly connected, so
239 // accomplish both at the same time
240 pruneMachinesAndFindWeaklyConnectedExaminers();
241 State.logEvent("OoOJavaAnalysis RCR pruneMachines pass completed");
244 // 11th pass, compiling memory Qs! The name "lock" is a legacy
245 // term for the heap dependence queue, or memQ as the runtime calls it
247 State.logEvent("OoOJavaAnalysis 11th pass completed");
249 // 12th pass, compute a plan for code injections
250 methItr = descriptorsToAnalyze.iterator();
251 while (methItr.hasNext()) {
252 Descriptor d = methItr.next();
253 FlatMethod fm = state.getMethodFlat(d);
254 codePlansForward(fm);
257 State.logEvent("OoOJavaAnalysis 12th pass completed");
259 // splice new IR nodes into graph after all
260 // analysis passes are complete
261 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
262 while (spliceItr.hasNext()) {
263 Map.Entry me = (Map.Entry) spliceItr.next();
264 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
265 fwdvn.spliceIntoIR();
267 State.logEvent("OoOJavaAnalysis 13th pass completed");
269 if (state.OOODEBUG) {
272 disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt");
273 writeConflictGraph();
274 } catch (IOException e) {}
276 State.logEvent("OoOJavaAnalysis completed");
280 private void buildFlatNodeToFlatMethod( FlatMethod fm ) {
281 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
282 flatNodesToVisit.add( fm );
284 Set<FlatNode> flatNodesVisited = new HashSet<FlatNode>();
286 while( !flatNodesToVisit.isEmpty() ) {
287 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
288 flatNodesToVisit.remove( fn );
289 flatNodesVisited.add( fn );
293 for( int i = 0; i < fn.numNext(); i++ ) {
294 FlatNode nn = fn.getNext( i );
295 if( !flatNodesVisited.contains( nn ) ) {
296 flatNodesToVisit.add( nn );
305 * Iterator iter = sese2conflictGraph.entrySet().iterator(); while
306 * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn =
307 * (FlatNode) e.getKey(); ConflictGraph conflictGraph = (ConflictGraph)
309 * System.out.println("---------------------------------------");
310 * System.out.println("CONFLICT GRAPH for " + fn); Set<String> keySet =
311 * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator();
312 * iterator.hasNext();) { String key = (String) iterator.next();
313 * ConflictNode node = conflictGraph.id2cn.get(key);
314 * System.out.println("key=" + key + " \n" + node.toStringAllEffects()); } }
320 private void writeFile(Set<FlatNew> sitesToFlag) {
323 BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt"));
325 for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext();) {
326 FlatNew fn = (FlatNew) iterator.next();
330 } catch (IOException e) {
337 private void livenessAnalysisBackward(FlatMethod fm) {
339 // flow backward across nodes to compute liveness, and
340 // take special care with sese enter/exit nodes that
341 // alter this from normal liveness analysis
342 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
343 flatNodesToVisit.add( fm.getFlatExit() );
345 while( !flatNodesToVisit.isEmpty() ) {
346 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
347 flatNodesToVisit.remove( fn );
349 Set<TempDescriptor> prev = livenessGlobalView.get( fn );
351 // merge sets from control flow joins
352 Set<TempDescriptor> livein = new HashSet<TempDescriptor>();
353 for (int i = 0; i < fn.numNext(); i++) {
354 FlatNode nn = fn.getNext( i );
355 Set<TempDescriptor> s = livenessGlobalView.get( nn );
361 Set<TempDescriptor> curr = liveness_nodeActions( fn, livein );
363 // if a new result, schedule backward nodes for analysis
364 if( !curr.equals( prev ) ) {
365 livenessGlobalView.put( fn, curr );
367 for( int i = 0; i < fn.numPrev(); i++ ) {
368 FlatNode nn = fn.getPrev( i );
369 flatNodesToVisit.add( nn );
375 private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
376 Set<TempDescriptor> liveIn
378 switch( fn.kind() ) {
380 case FKind.FlatSESEEnterNode: {
381 // add whatever is live-in at a task enter to that
383 FlatSESEEnterNode fsen = (FlatSESEEnterNode)fn;
384 if( liveIn != null ) {
385 fsen.addInVarSet( liveIn );
387 // no break, should also execute default actions
391 // handle effects of statement in reverse, writes then reads
392 TempDescriptor[] writeTemps = fn.writesTemps();
393 for( int i = 0; i < writeTemps.length; ++i ) {
394 liveIn.remove( writeTemps[i] );
396 // if we are analyzing code declared directly in a task,
397 FlatSESEEnterNode fsen = rblockRel.getLocalInnerRBlock( fn );
399 // check to see if we are writing to variables that will
400 // be live-out at the task's exit (and therefore should
401 // go in the task's out-var set)
402 FlatSESEExitNode fsexn = fsen.getFlatExit();
403 Set<TempDescriptor> livetemps = livenessGlobalView.get( fsexn );
404 if( livetemps != null && livetemps.contains( writeTemps[i] ) ) {
405 fsen.addOutVar( writeTemps[i] );
410 TempDescriptor[] readTemps = fn.readsTemps();
411 for( int i = 0; i < readTemps.length; ++i ) {
412 liveIn.add( readTemps[i] );
415 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
416 if( virtualReadTemps != null ) {
417 liveIn.addAll( virtualReadTemps );
427 private void variableAnalysisForward(FlatMethod fm) {
429 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
430 flatNodesToVisit.add(fm);
432 while (!flatNodesToVisit.isEmpty()) {
433 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
434 flatNodesToVisit.remove(fn);
436 VarSrcTokTable prev = variableResults.get(fn);
438 // merge sets from control flow joins
439 VarSrcTokTable curr = new VarSrcTokTable();
440 for (int i = 0; i < fn.numPrev(); i++) {
441 FlatNode nn = fn.getPrev(i);
442 VarSrcTokTable incoming = variableResults.get(nn);
443 curr.merge(incoming);
446 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
447 if( currentSESE == null ) {
448 currentSESE = rblockRel.getCallerProxySESE();
451 variable_nodeActions(fn, curr, currentSESE);
453 // if a new result, schedule forward nodes for analysis
454 if (!curr.equals(prev)) {
455 variableResults.put(fn, curr);
457 for (int i = 0; i < fn.numNext(); i++) {
458 FlatNode nn = fn.getNext(i);
459 flatNodesToVisit.add(nn);
465 private void variable_nodeActions(FlatNode fn,
466 VarSrcTokTable vstTable,
467 FlatSESEEnterNode currentSESE) {
471 case FKind.FlatSESEEnterNode: {
472 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
473 // ignore currently executing SESE, at this point
474 // the analysis considers a new instance is becoming
477 vstTable.assertConsistency();
481 case FKind.FlatSESEExitNode: {
482 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
484 // fsen is the child of currently executing tasks
485 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
487 // remap all of this child's children tokens to be
488 // from this child as the child exits
489 vstTable.remapChildTokens(fsen);
491 // liveness virtual reads are things that might be
492 // written by an SESE and should be added to the in-set
493 // anything virtually read by this SESE should be pruned
494 // of parent or sibling sources
495 Set<TempDescriptor> liveVars = livenessGlobalView.get(fn);
496 Set<TempDescriptor> fsenVirtReads =
497 vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen,
500 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
501 if (fsenVirtReadsOld != null) {
502 fsenVirtReads.addAll(fsenVirtReadsOld);
504 livenessVirtualReads.put(fn, fsenVirtReads);
506 // then all child out-set tokens are guaranteed
507 // to be filled in, so clobber those entries with
508 // the latest, clean sources
509 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
510 while (outVarItr.hasNext()) {
511 TempDescriptor outVar = outVarItr.next();
512 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
514 VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
515 vstTable.remove(outVar);
518 vstTable.assertConsistency();
522 case FKind.FlatOpNode: {
523 FlatOpNode fon = (FlatOpNode) fn;
525 if (fon.getOp().getOp() == Operation.ASSIGN) {
526 TempDescriptor lhs = fon.getDest();
527 TempDescriptor rhs = fon.getLeft();
529 vstTable.remove(lhs);
531 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
533 Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
534 while (itr.hasNext()) {
535 VariableSourceToken vst = itr.next();
537 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
540 // when we do x = y for variables, just copy over from a child,
541 // there are two cases:
542 // 1. if the current task is the caller proxy, any local root is a child
544 currentSESE.getIsCallerProxySESE() &&
545 rblockRel.getLocalRootSESEs().contains( vst.getSESE() );
547 // 2. if the child task is a locally-defined child of the current task
548 boolean case2 = currentSESE.getLocalChildren().contains( vst.getSESE() );
550 if( case1 || case2 ) {
551 // if the source comes from a child, copy it over
552 forAddition.add( new VariableSourceToken( ts,
559 // otherwise, stamp it as us as the source
560 forAddition.add( new VariableSourceToken( ts,
569 vstTable.addAll( forAddition );
571 // only break if this is an ASSIGN op node,
572 // otherwise fall through to default case
573 vstTable.assertConsistency();
578 // note that FlatOpNode's that aren't ASSIGN
579 // fall through to this default case
581 TempDescriptor[] writeTemps = fn.writesTemps();
582 if( writeTemps.length > 0 ) {
584 // for now, when writeTemps > 1, make sure
585 // its a call node, programmer enforce only
586 // doing stuff like calling a print routine
587 if( writeTemps.length > 1 ) {
588 assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
592 vstTable.remove( writeTemps[0] );
594 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
595 ts.add( writeTemps[0] );
597 vstTable.add( new VariableSourceToken( ts,
605 vstTable.assertConsistency();
612 private void notAvailableForward(FlatMethod fm) {
614 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
615 flatNodesToVisit.add(fm);
617 while (!flatNodesToVisit.isEmpty()) {
618 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
619 flatNodesToVisit.remove(fn);
621 Set<TempDescriptor> prev = notAvailableResults.get(fn);
623 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
624 for (int i = 0; i < fn.numPrev(); i++) {
625 FlatNode nn = fn.getPrev(i);
626 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
627 if (notAvailIn != null) {
628 curr.addAll(notAvailIn);
632 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
633 if( currentSESE == null ) {
634 currentSESE = rblockRel.getCallerProxySESE();
637 notAvailable_nodeActions(fn, curr, currentSESE);
639 // if a new result, schedule forward nodes for analysis
640 if (!curr.equals(prev)) {
641 notAvailableResults.put(fn, curr);
643 for (int i = 0; i < fn.numNext(); i++) {
644 FlatNode nn = fn.getNext(i);
645 flatNodesToVisit.add(nn);
651 private void notAvailable_nodeActions(FlatNode fn,
652 Set<TempDescriptor> notAvailSet,
653 FlatSESEEnterNode currentSESE
656 // any temps that are removed from the not available set
657 // at this node should be marked in this node's code plan
658 // as temps to be grabbed at runtime!
662 case FKind.FlatSESEEnterNode: {
663 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
665 // keep a copy of what's not available into the SESE
666 // and restore it at the matching exit node
667 Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
668 Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
669 while (tdItr.hasNext()) {
670 notAvailCopy.add(tdItr.next());
672 notAvailableIntoSESE.put(fsen, notAvailCopy);
677 case FKind.FlatSESEExitNode: {
678 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
679 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
681 notAvailSet.addAll(fsen.getOutVarSet());
683 Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
684 assert notAvailIn != null;
685 notAvailSet.addAll(notAvailIn);
688 case FKind.FlatMethod: {
692 case FKind.FlatOpNode: {
693 FlatOpNode fon = (FlatOpNode) fn;
695 if (fon.getOp().getOp() == Operation.ASSIGN) {
696 TempDescriptor lhs = fon.getDest();
697 TempDescriptor rhs = fon.getLeft();
699 // copy makes lhs same availability as rhs
700 if (notAvailSet.contains(rhs)) {
701 notAvailSet.add(lhs);
703 notAvailSet.remove(lhs);
706 // only break if this is an ASSIGN op node,
707 // otherwise fall through to default case
712 // note that FlatOpNode's that aren't ASSIGN
713 // fall through to this default case
715 TempDescriptor[] writeTemps = fn.writesTemps();
716 for (int i = 0; i < writeTemps.length; i++) {
717 TempDescriptor wTemp = writeTemps[i];
718 notAvailSet.remove(wTemp);
720 TempDescriptor[] readTemps = fn.readsTemps();
721 for (int i = 0; i < readTemps.length; i++) {
722 TempDescriptor rTemp = readTemps[i];
723 notAvailSet.remove(rTemp);
725 // if this variable has exactly one source, potentially
726 // get other things from this source as well
727 VarSrcTokTable vstTable = variableResults.get(fn);
729 VSTWrapper vstIfStatic = new VSTWrapper();
730 Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
732 if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
734 VariableSourceToken vst = vstIfStatic.vst;
736 Iterator<VariableSourceToken> availItr =
737 vstTable.get(vst.getSESE(), vst.getAge()).iterator();
739 // look through things that are also available from same source
740 while (availItr.hasNext()) {
741 VariableSourceToken vstAlsoAvail = availItr.next();
743 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
744 while (refVarItr.hasNext()) {
745 TempDescriptor refVarAlso = refVarItr.next();
747 // if a variable is available from the same source, AND it ALSO
748 // only comes from one statically known source, mark it available
749 VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
750 Integer srcTypeAlso =
751 vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed);
752 if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
753 notAvailSet.remove(refVarAlso);
765 private void codePlansForward(FlatMethod fm) {
767 // start from flat method top, visit every node in
768 // method exactly once
769 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
770 flatNodesToVisit.add(fm);
772 Set<FlatNode> visited = new HashSet<FlatNode>();
774 while (!flatNodesToVisit.isEmpty()) {
775 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
776 FlatNode fn = fnItr.next();
778 flatNodesToVisit.remove(fn);
781 // use incoming results as "dot statement" or just
782 // before the current statement
783 VarSrcTokTable dotSTtable = new VarSrcTokTable();
784 for (int i = 0; i < fn.numPrev(); i++) {
785 FlatNode nn = fn.getPrev(i);
786 dotSTtable.merge(variableResults.get(nn));
789 // find dt-st notAvailableSet also
790 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
791 for (int i = 0; i < fn.numPrev(); i++) {
792 FlatNode nn = fn.getPrev(i);
793 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
794 if (notAvailIn != null) {
795 dotSTnotAvailSet.addAll(notAvailIn);
799 Set<TempDescriptor> dotSTlive = livenessGlobalView.get(fn);
801 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
802 if( currentSESE == null ) {
803 currentSESE = rblockRel.getCallerProxySESE();
806 codePlans_nodeActions(fm, fn,
807 dotSTlive, dotSTtable, dotSTnotAvailSet,
810 for (int i = 0; i < fn.numNext(); i++) {
811 FlatNode nn = fn.getNext(i);
813 if (!visited.contains(nn)) {
814 flatNodesToVisit.add(nn);
820 private void codePlans_nodeActions(FlatMethod fm,
822 Set<TempDescriptor> liveSetIn,
823 VarSrcTokTable vstTableIn,
824 Set<TempDescriptor> notAvailSetIn,
825 FlatSESEEnterNode currentSESE) {
827 CodePlan plan = new CodePlan(currentSESE);
831 case FKind.FlatSESEEnterNode: {
832 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
834 // track the source types of the in-var set so generated
835 // code at this SESE issue can compute the number of
836 // dependencies properly
837 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
838 while (inVarItr.hasNext()) {
839 TempDescriptor inVar = inVarItr.next();
841 // when we get to an SESE enter node we change the
842 // currentSESE variable of this analysis to the
843 // child that is declared by the enter node, so
844 // in order to classify in-vars correctly, pass
845 // the parent SESE in--at other FlatNode types just
846 // use the currentSESE
847 FlatSESEEnterNode parent = rblockRel.getLocalInnerRBlock( fn );
848 if( parent == null ) {
849 parent = rblockRel.getCallerProxySESE();
852 VSTWrapper vstIfStatic = new VSTWrapper();
853 Integer srcType = vstTableIn.getRefVarSrcType(inVar, parent, vstIfStatic);
855 // the current SESE needs a local space to track the dynamic
856 // variable and the child needs space in its SESE record
857 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
858 fsen.addDynamicInVar(inVar);
859 addDynamicVar( fsen, fm, inVar );
861 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
862 fsen.addStaticInVar(inVar);
863 VariableSourceToken vst = vstIfStatic.vst;
864 fsen.putStaticInVar2src(inVar, vst);
865 fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
867 assert srcType.equals(VarSrcTokTable.SrcType_READY);
868 fsen.addReadyInVar(inVar);
873 case FKind.FlatSESEExitNode: {
874 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
875 //TODO! Shouldn't there be a code plan for task exit
876 // where the exiting task calculates whether its own
877 // siblings need variables from its children, so the
878 // exiter should copy those variables into its own out-set
879 // and make the available?
882 case FKind.FlatOpNode: {
883 FlatOpNode fon = (FlatOpNode) fn;
885 if (fon.getOp().getOp() == Operation.ASSIGN) {
886 TempDescriptor lhs = fon.getDest();
887 TempDescriptor rhs = fon.getLeft();
889 // if this is an op node, don't stall, copy
890 // source and delay until we need to use value
892 // ask whether lhs and rhs sources are dynamic, static, etc.
893 VSTWrapper vstIfStatic = new VSTWrapper();
894 Integer lhsSrcType = vstTableIn.getRefVarSrcType(lhs, currentSESE, vstIfStatic);
895 Integer rhsSrcType = vstTableIn.getRefVarSrcType(rhs, currentSESE, vstIfStatic);
897 if (rhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
898 // if rhs is dynamic going in, lhs will definitely be dynamic
899 // going out of this node, so track that here
900 plan.addDynAssign( lhs, rhs );
901 addDynamicVar( currentSESE, fm, lhs );
902 addDynamicVar( currentSESE, fm, rhs );
904 } else if (lhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
905 // otherwise, if the lhs is dynamic, but the rhs is not, we
906 // need to update the variable's dynamic source as "current SESE"
907 plan.addDynAssign(lhs);
910 // only break if this is an ASSIGN op node,
911 // otherwise fall through to default case
916 // note that FlatOpNode's that aren't ASSIGN
917 // fall through to this default case
920 // a node with no live set has nothing to stall for
921 if (liveSetIn == null) {
925 TempDescriptor[] readarray = fn.readsTemps();
926 for (int i = 0; i < readarray.length; i++) {
927 TempDescriptor readtmp = readarray[i];
929 // ignore temps that are definitely available
930 // when considering to stall on it
931 if (!notAvailSetIn.contains(readtmp)) {
935 // check the source type of this variable
936 VSTWrapper vstIfStatic = new VSTWrapper();
937 Integer srcType = vstTableIn.getRefVarSrcType(readtmp, currentSESE, vstIfStatic);
939 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
940 // 1) It is not clear statically where this variable will
941 // come from, so dynamically we must keep track
942 // along various control paths, and therefore when we stall,
943 // just stall for the exact thing we need and move on
944 plan.addDynamicStall( readtmp );
945 addDynamicVar( currentSESE, fm, readtmp );
947 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
948 // 2) Single token/age pair: Stall for token/age pair, and copy
949 // all live variables with same token/age pair at the same
950 // time. This is the same stuff that the notavaialable analysis
951 // marks as now available.
952 VariableSourceToken vst = vstIfStatic.vst;
954 Iterator<VariableSourceToken> availItr =
955 vstTableIn.get(vst.getSESE(), vst.getAge()).iterator();
957 while (availItr.hasNext()) {
958 VariableSourceToken vstAlsoAvail = availItr.next();
960 // only grab additional stuff that is live
961 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
963 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
964 while (refVarItr.hasNext()) {
965 TempDescriptor refVar = refVarItr.next();
966 if (liveSetIn.contains(refVar)) {
971 if (!copySet.isEmpty()) {
972 plan.addStall2CopySet(vstAlsoAvail, copySet);
977 // the other case for srcs is READY, so do nothing
980 // assert that everything being stalled for is in the
981 // "not available" set coming into this flat node and
982 // that every VST identified is in the possible "stall set"
983 // that represents VST's from children SESE's
991 // identify sese-age pairs that are statically useful
992 // and should have an associated SESE variable in code
993 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
994 // AND ALWAYS GIVE NAMES TO LOCAL PARENTS
995 Set<VariableSourceToken> staticSet = vstTableIn.get();
996 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
997 while (vstItr.hasNext()) {
998 VariableSourceToken vst = vstItr.next();
1000 // the caller proxy generates useful analysis facts, but we
1001 // never need to generate another name for it in code (it is
1002 // ALWAYS the task executing the local method context)
1003 if( vst.getSESE().getIsCallerProxySESE() ) {
1007 SESEandAgePair sap = new SESEandAgePair( vst.getSESE(), vst.getAge() );
1008 sap.getSESE().mustTrackAtLeastAge( sap.getAge() );
1010 FlatSESEEnterNode sese = currentSESE;
1011 while( sese != null ) {
1012 addNeededStaticName( sese, fm, sap );
1013 sese = sese.getLocalParent();
1017 codePlans.put(fn, plan);
1019 // if any variables at this-node-*dot* have a static source (exactly one
1021 // but go to a dynamic source at next-node-*dot*, create a new IR graph
1022 // node on that edge to track the sources dynamically
1023 VarSrcTokTable thisVstTable = variableResults.get(fn);
1024 for (int i = 0; i < fn.numNext(); i++) {
1025 FlatNode nn = fn.getNext(i);
1026 VarSrcTokTable nextVstTable = variableResults.get(nn);
1027 Set<TempDescriptor> nextLiveIn = livenessGlobalView.get(nn);
1029 // the table can be null if it is one of the few IR nodes
1030 // completely outside of the root SESE scope
1031 if (nextVstTable != null && nextLiveIn != null) {
1033 Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
1034 thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, currentSESE);
1036 if (!readyOrStatic2dynamicSet.isEmpty()) {
1038 // either add these results to partial fixed-point result
1039 // or make a new one if we haven't made any here yet
1040 FlatEdge fe = new FlatEdge(fn, nn);
1041 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe);
1043 if (fwdvn == null) {
1044 fwdvn = new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, currentSESE);
1045 wdvNodesToSpliceIn.put(fe, fwdvn);
1047 fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet);
1054 private void addDynamicVar( FlatSESEEnterNode fsen,
1056 TempDescriptor var ) {
1059 if( fsen.getIsCallerProxySESE() ) {
1060 // attach the dynamic variable to track to
1061 // the flat method, so it can be declared at entry
1064 // otherwise the code context is a task body
1068 ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1070 ctn = new ContextTaskNames();
1073 ctn.addDynamicVar( var );
1074 fn2contextTaskNames.put( fnContext, ctn );
1077 private void addNeededStaticName( FlatSESEEnterNode fsen,
1079 SESEandAgePair sap ) {
1082 if( fsen.getIsCallerProxySESE() ) {
1083 // attach the dynamic variable to track to
1084 // the flat method, so it can be declared at entry
1087 // otherwise the code context is a task body
1091 ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1093 ctn = new ContextTaskNames();
1096 ctn.addNeededStaticName( sap );
1098 fn2contextTaskNames.put( fnContext, ctn );
1102 private void startConflictGraphs() {
1104 // first, for each task, consider whether it has any children, and if
1105 // effects analysis says they should be a conflict node in the that
1106 // parent's conflict graph
1107 Set<FlatSESEEnterNode> allSESEs = rblockRel.getAllSESEs();
1108 for( Iterator iterator = allSESEs.iterator(); iterator.hasNext(); ) {
1110 FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
1111 if( parent.getIsLeafSESE() ) {
1115 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1116 ConflictGraph conflictGraph = sese2conflictGraph.get( parent );
1117 assert conflictGraph == null;
1118 conflictGraph = new ConflictGraph( state );
1120 Set<FlatSESEEnterNode> children = parent.getChildren();
1121 for( Iterator iterator2 = children.iterator(); iterator2.hasNext(); ) {
1122 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
1123 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get( child );
1124 conflictGraph.addLiveIn( taint2Effects );
1127 sese2conflictGraph.put( parent, conflictGraph );
1130 // then traverse all methods looking for potential stall sites, and
1131 // add those stall sites as nodes in any task's conflict graph that
1132 // might be executing at the point of the stall site
1133 Iterator<MethodDescriptor> descItr = descriptorsToAnalyze.iterator();
1134 while( descItr.hasNext() ) {
1135 MethodDescriptor md = descItr.next();
1136 FlatMethod fm = state.getMethodFlat( md );
1138 addStallSitesToConflictGraphs( fm );
1143 private void addStallSitesToConflictGraphs( FlatMethod fm ) {
1145 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1146 flatNodesToVisit.add( fm );
1148 Set<FlatNode> visited = new HashSet<FlatNode>();
1150 while( !flatNodesToVisit.isEmpty() ) {
1151 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1152 flatNodesToVisit.remove( fn );
1155 Set<FlatSESEEnterNode> currentSESEs =
1156 rblockRel.getPossibleExecutingRBlocks( fn );
1158 conflictGraph_nodeAction( fn, currentSESEs );
1160 // schedule forward nodes for analysis
1161 for( int i = 0; i < fn.numNext(); i++ ) {
1162 FlatNode nn = fn.getNext( i );
1163 if( !visited.contains( nn ) ) {
1164 flatNodesToVisit.add( nn );
1170 private void conflictGraph_nodeAction( FlatNode fn,
1171 Set<FlatSESEEnterNode> currentSESEs
1174 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1176 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get( fn );
1179 // repeat the process of adding a stall site to a conflict graph
1180 // for each task that might be executing at a possible stall site
1181 Iterator<FlatSESEEnterNode> seseItr = currentSESEs.iterator();
1182 while( seseItr.hasNext() ) {
1183 FlatSESEEnterNode currentSESE = seseItr.next();
1185 ConflictGraph conflictGraph = sese2conflictGraph.get( currentSESE );
1186 if( conflictGraph == null ) {
1187 assert currentSESE.getIsLeafSESE();
1194 switch( fn.kind() ) {
1197 case FKind.FlatFieldNode:
1198 case FKind.FlatElementNode: {
1200 if( fn instanceof FlatFieldNode ) {
1201 FlatFieldNode ffn = (FlatFieldNode) fn;
1204 FlatElementNode fen = (FlatElementNode) fn;
1208 conflictGraph.addStallSite( taint2Effects, rhs );
1212 case FKind.FlatSetFieldNode:
1213 case FKind.FlatSetElementNode: {
1215 if( fn instanceof FlatSetFieldNode ) {
1216 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1217 lhs = fsfn.getDst();
1218 rhs = fsfn.getSrc();
1220 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1221 lhs = fsen.getDst();
1222 rhs = fsen.getSrc();
1225 conflictGraph.addStallSite( taint2Effects, rhs );
1226 conflictGraph.addStallSite( taint2Effects, lhs );
1230 case FKind.FlatCall: {
1231 FlatCall fc = (FlatCall) fn;
1234 conflictGraph.addStallSite( taint2Effects, lhs );
1239 if( conflictGraph.id2cn.size() > 0 ) {
1240 sese2conflictGraph.put( currentSESE, conflictGraph );
1246 private void calculateConflicts( Set<FlatNew> sitesToFlag,
1247 boolean useReachInfo ) {
1249 // decide fine-grain edge or coarse-grain edge among all vertexes by
1250 // pair-wise comparison
1251 Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
1252 while (seseIter.hasNext()) {
1253 FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next();
1254 ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
1257 // clear current conflict before recalculating with reachability info
1258 conflictGraph.clearAllConflictEdge();
1259 conflictGraph.setDisJointAnalysis(disjointAnalysisReach);
1260 conflictGraph.setFMEnclosing(sese.getfmEnclosing());
1262 conflictGraph.analyzeConflicts(sitesToFlag, useReachInfo);
1263 sese2conflictGraph.put(sese, conflictGraph);
1268 private void writeConflictGraph() {
1269 Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
1270 while (keyEnum.hasMoreElements()) {
1271 FlatNode key = (FlatNode) keyEnum.nextElement();
1272 ConflictGraph cg = sese2conflictGraph.get(key);
1274 if (cg.hasConflictEdge()) {
1275 cg.writeGraph("ConflictGraphFor" + key, false);
1277 } catch (IOException e) {
1278 System.out.println("Error writing");
1285 // the traversal for pruning state machines and finding
1286 // machines that are weakly connected BOTH consider conflicting
1287 // effects between heap roots, so it is smart to compute all of
1289 public void pruneMachinesAndFindWeaklyConnectedExaminers() {
1290 ProcessStateMachines psm=new ProcessStateMachines(buildStateMachines, rblockRel);
1292 buildStateMachines.writeStateMachines("pruned");
1297 private void synthesizeLocks() {
1298 // for every conflict graph, generate a set of memory queues
1299 // (called SESELock in this code!) to cover the graph
1300 Set<Map.Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
1301 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
1302 Map.Entry<FlatNode, ConflictGraph> graphEntry = (Map.Entry<FlatNode, ConflictGraph>) iterator.next();
1303 FlatNode sese = graphEntry.getKey();
1304 ConflictGraph conflictGraph = graphEntry.getValue();
1305 calculateCovering(conflictGraph);
1309 private void calculateCovering(ConflictGraph conflictGraph) {
1310 uniqueLockSetId = 0; // reset lock counter for every new conflict graph
1311 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1312 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1313 HashSet<SESELock> lockSet = new HashSet<SESELock>();
1315 Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1316 for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
1317 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1318 if (conflictEdge.isCoarseEdge()) {
1319 coarseToCover.add(conflictEdge);
1321 fineToCover.add(conflictEdge);
1325 HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
1326 toCover.addAll(fineToCover);
1327 toCover.addAll(coarseToCover);
1329 while (!toCover.isEmpty()) {
1331 SESELock seseLock = new SESELock();
1332 seseLock.setID(uniqueLockSetId++);
1336 do { // fine-grained edge
1340 for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) {
1343 ConflictEdge edge = (ConflictEdge) iterator.next();
1344 if (seseLock.getConflictNodeSet().size() == 0) {
1346 if (seseLock.isWriteNode(edge.getVertexU())) {
1347 // mark as fine_write
1348 if (edge.getVertexU().isStallSiteNode()) {
1349 type = ConflictNode.PARENT_WRITE;
1351 type = ConflictNode.FINE_WRITE;
1353 seseLock.addConflictNode(edge.getVertexU(), type);
1355 // mark as fine_read
1356 if (edge.getVertexU().isStallSiteNode()) {
1357 type = ConflictNode.PARENT_READ;
1359 type = ConflictNode.FINE_READ;
1361 seseLock.addConflictNode(edge.getVertexU(), type);
1363 if (edge.getVertexV() != edge.getVertexU()) {
1364 if (seseLock.isWriteNode(edge.getVertexV())) {
1365 // mark as fine_write
1366 if (edge.getVertexV().isStallSiteNode()) {
1367 type = ConflictNode.PARENT_WRITE;
1369 type = ConflictNode.FINE_WRITE;
1371 seseLock.addConflictNode(edge.getVertexV(), type);
1373 // mark as fine_read
1374 if (edge.getVertexV().isStallSiteNode()) {
1375 type = ConflictNode.PARENT_READ;
1377 type = ConflictNode.FINE_READ;
1379 seseLock.addConflictNode(edge.getVertexV(), type);
1383 seseLock.addConflictEdge(edge);
1384 fineToCover.remove(edge);
1385 break;// exit iterator loop
1386 }// end of initial setup
1388 ConflictNode newNode;
1389 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1390 // new node has a fine-grained edge to all current node
1391 // If there is a coarse grained edge where need a fine edge, it's
1392 // okay to add the node
1393 // but the edge must remain uncovered.
1397 if (seseLock.containsConflictNode(newNode)) {
1398 seseLock.addEdge(edge);
1399 fineToCover.remove(edge);
1403 if (seseLock.isWriteNode(newNode)) {
1404 if (newNode.isStallSiteNode()) {
1405 type = ConflictNode.PARENT_WRITE;
1407 type = ConflictNode.FINE_WRITE;
1409 seseLock.setNodeType(newNode, type);
1411 if (newNode.isStallSiteNode()) {
1412 type = ConflictNode.PARENT_READ;
1414 type = ConflictNode.FINE_READ;
1416 seseLock.setNodeType(newNode, type);
1419 seseLock.addEdge(edge);
1420 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1421 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1422 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1424 // mark all fine edges between new node and nodes in the group as
1426 if (!conflictEdge.getVertexU().equals(newNode)) {
1427 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1429 seseLock.addConflictEdge(conflictEdge);
1430 fineToCover.remove(conflictEdge);
1432 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1433 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1435 seseLock.addConflictEdge(conflictEdge);
1436 fineToCover.remove(conflictEdge);
1442 break;// exit iterator loop
1447 HashSet<ConflictEdge> notCovered=new HashSet<ConflictEdge>();
1451 for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) {
1453 ConflictEdge edge = (ConflictEdge) iterator.next();
1454 if (seseLock.getConflictNodeSet().size() == 0) {
1456 if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
1457 // node has a coarse-grained edge with itself
1458 if (!(edge.getVertexU().isStallSiteNode())) {
1459 // and it is not parent
1460 type = ConflictNode.SCC;
1463 type = ConflictNode.PARENT_COARSE;
1465 type = ConflictNode.PARENT_WRITE;
1468 seseLock.addConflictNode(edge.getVertexU(), type);
1470 if (edge.getVertexU().isStallSiteNode()) {
1472 type = ConflictNode.PARENT_COARSE;
1474 if (edge.getVertexU().getWriteEffectSet().isEmpty()) {
1475 type = ConflictNode.PARENT_READ;
1477 type = ConflictNode.PARENT_WRITE;
1481 type = ConflictNode.COARSE;
1483 seseLock.addConflictNode(edge.getVertexU(), type);
1485 if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
1486 // node has a coarse-grained edge with itself
1487 if (!(edge.getVertexV().isStallSiteNode())) {
1488 // and it is not parent
1489 type = ConflictNode.SCC;
1492 type = ConflictNode.PARENT_COARSE;
1494 type = ConflictNode.PARENT_WRITE;
1497 seseLock.addConflictNode(edge.getVertexV(), type);
1499 if (edge.getVertexV().isStallSiteNode()) {
1501 type = ConflictNode.PARENT_COARSE;
1503 if (edge.getVertexV().getWriteEffectSet().isEmpty()) {
1504 type = ConflictNode.PARENT_READ;
1506 type = ConflictNode.PARENT_WRITE;
1510 type = ConflictNode.COARSE;
1512 seseLock.addConflictNode(edge.getVertexV(), type);
1515 coarseToCover.remove(edge);
1516 seseLock.addConflictEdge(edge);
1517 break;// exit iterator loop
1518 }// end of initial setup
1520 ConflictNode newNode;
1521 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1522 // new node has a coarse-grained edge to all fine-read, fine-write,
1526 if (newNode.isInVarNode() && (!seseLock.hasSelfCoarseEdge(newNode))
1527 && seseLock.hasCoarseEdgeWithParentCoarse(newNode)) {
1528 // this case can't be covered by this queue
1529 coarseToCover.remove(edge);
1530 notCovered.add(edge);
1534 if (seseLock.containsConflictNode(newNode)) {
1535 seseLock.addEdge(edge);
1536 coarseToCover.remove(edge);
1540 if (seseLock.hasSelfCoarseEdge(newNode)) {
1542 if (newNode.isStallSiteNode()) {
1543 type = ConflictNode.PARENT_COARSE;
1545 type = ConflictNode.SCC;
1547 seseLock.setNodeType(newNode, type);
1549 if (newNode.isStallSiteNode()) {
1550 type = ConflictNode.PARENT_COARSE;
1552 type = ConflictNode.COARSE;
1554 seseLock.setNodeType(newNode, type);
1557 seseLock.addEdge(edge);
1558 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1559 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1560 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1561 // mark all coarse edges between new node and nodes in the group
1563 if (!conflictEdge.getVertexU().equals(newNode)) {
1564 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1566 seseLock.addConflictEdge(conflictEdge);
1567 coarseToCover.remove(conflictEdge);
1569 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1570 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1572 seseLock.addConflictEdge(conflictEdge);
1573 coarseToCover.remove(conflictEdge);
1578 break;// exit iterator loop
1584 lockSet.add(seseLock);
1587 coarseToCover.addAll(notCovered);
1588 toCover.addAll(fineToCover);
1589 toCover.addAll(coarseToCover);
1593 conflictGraph2SESELock.put(conflictGraph, lockSet);
1596 public ConflictGraph getConflictGraph(FlatNode sese) {
1597 return sese2conflictGraph.get(sese);
1600 public Set<SESELock> getLockMappings(ConflictGraph graph) {
1601 return conflictGraph2SESELock.get(graph);
1604 public Set<FlatSESEEnterNode> getAllSESEs() {
1605 return rblockRel.getAllSESEs();
1608 public FlatSESEEnterNode getMainSESE() {
1609 return rblockRel.getMainSESE();
1612 public FlatSESEEnterNode getCallerProxySESE() {
1613 return rblockRel.getCallerProxySESE();
1616 public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks( FlatNode fn ) {
1617 return rblockRel.getPossibleExecutingRBlocks( fn );
1621 public void writeReports(String timeReport) throws java.io.IOException {
1623 BufferedWriter bw = new BufferedWriter(new FileWriter("ooojReport_summary.txt"));
1624 bw.write("OoOJava Analysis Results\n\n");
1625 bw.write(timeReport + "\n\n");
1626 printSESEHierarchy(bw);
1631 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
1632 while (methItr.hasNext()) {
1633 MethodDescriptor md = methItr.next();
1634 FlatMethod fm = state.getMethodFlat(md);
1636 bw = new BufferedWriter(new FileWriter("ooojReport_" +
1637 md.getClassMethodName() +
1638 md.getSafeMethodDescriptor() +
1640 bw.write("OoOJava Results for " + md + "\n-------------------\n");
1642 bw.write("Dynamic vars to manage:\n " + getContextTaskNames( fm ).getDynamicVarSet() );
1644 bw.write("\n\nLive-In, Root View\n------------------\n" + fm.printMethod(livenessGlobalView));
1645 bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults));
1646 bw.write("\n\nNot Available Results-Out\n---------------------\n" + fm.printMethod(notAvailableResults));
1647 bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans));
1653 private void printSESEHierarchy(BufferedWriter bw) throws java.io.IOException {
1654 bw.write("SESE Local Hierarchy\n--------------\n");
1655 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getLocalRootSESEs().iterator();
1656 while (rootItr.hasNext()) {
1657 FlatSESEEnterNode root = rootItr.next();
1658 printSESEHierarchyTree(bw, root, 0);
1662 private void printSESEHierarchyTree(BufferedWriter bw,
1663 FlatSESEEnterNode fsen,
1665 ) throws java.io.IOException {
1666 for (int i = 0; i < depth; ++i) {
1669 bw.write("- " + fsen.getPrettyIdentifier() + "\n");
1671 Iterator<FlatSESEEnterNode> childItr = fsen.getLocalChildren().iterator();
1672 while (childItr.hasNext()) {
1673 FlatSESEEnterNode fsenChild = childItr.next();
1674 printSESEHierarchyTree(bw, fsenChild, depth + 1);
1678 private void printSESEInfo(BufferedWriter bw) throws java.io.IOException {
1679 bw.write("\nSESE info\n-------------\n");
1680 Iterator<FlatSESEEnterNode> fsenItr = rblockRel.getAllSESEs().iterator();
1681 while( fsenItr.hasNext() ) {
1682 FlatSESEEnterNode fsen = fsenItr.next();
1684 bw.write("SESE " + fsen.getPrettyIdentifier());
1685 if( fsen.getIsLeafSESE() ) {
1686 bw.write(" (leaf)");
1690 bw.write(" in-set: " + fsen.getInVarSet() + "\n");
1691 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1692 while (tItr.hasNext()) {
1693 TempDescriptor inVar = tItr.next();
1694 if (fsen.getReadyInVarSet().contains(inVar)) {
1695 bw.write(" (ready) " + inVar + "\n");
1697 if (fsen.getStaticInVarSet().contains(inVar)) {
1698 bw.write(" (static) " + inVar + " from " + fsen.getStaticInVarSrc(inVar) + "\n");
1700 if (fsen.getDynamicInVarSet().contains(inVar)) {
1701 bw.write(" (dynamic)" + inVar + "\n");
1705 bw.write(" Dynamic vars to manage: " + getContextTaskNames( fsen ).getDynamicVarSet() + "\n");
1707 bw.write(" out-set: " + fsen.getOutVarSet() + "\n");
1709 bw.write(" local parent: " + fsen.getLocalParent() + "\n");
1710 bw.write(" local children: " + fsen.getLocalChildren() + "\n");
1712 bw.write(" possible parents: " + fsen.getParents() + "\n");
1713 bw.write(" possible children: " + fsen.getChildren() + "\n");