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 Liveness liveness;
21 private RBlockRelationAnalysis rblockRel;
22 private HeapAnalysis disjointAnalysisTaints;
23 private DisjointAnalysis disjointAnalysisReach;
24 private BuildStateMachines buildStateMachines;
26 private Set<MethodDescriptor> descriptorsToAnalyze;
28 private Hashtable<FlatNode, Set<TempDescriptor>> livenessGlobalView;
29 private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
30 private Hashtable<FlatNode, VarSrcTokTable> variableResults;
31 private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
32 private Hashtable<FlatNode, CodePlan> codePlans;
34 private Hashtable<FlatSESEEnterNode, Set<TempDescriptor>> notAvailableIntoSESE;
36 private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
38 private Hashtable<FlatNode, ContextTaskNames> fn2contextTaskNames;
40 // get the flat method that contains any given flat node
41 private Hashtable<FlatNode, FlatMethod> fn2fm;
43 // temporal data structures to track analysis progress.
44 static private int uniqueLockSetId = 0;
45 // mapping of a conflict graph to its compiled lock
46 private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraph2SESELock;
47 // mapping of a sese block to its conflict graph
48 private Hashtable<FlatNode, ConflictGraph> sese2conflictGraph;
50 public static int maxSESEage = -1;
52 public int getMaxSESEage() {
57 public CodePlan getCodePlan(FlatNode fn) {
58 CodePlan cp = codePlans.get(fn);
62 public Set<FlatNode> getNodesWithPlans() {
63 return codePlans.keySet();
66 public ContextTaskNames getContextTaskNames(FlatMethod fm) {
67 ContextTaskNames out = fn2contextTaskNames.get(fm);
69 out = new ContextTaskNames();
74 public ContextTaskNames getContextTaskNames(FlatSESEEnterNode fsen) {
75 ContextTaskNames out = fn2contextTaskNames.get(fsen);
77 out = new ContextTaskNames();
82 public FlatMethod getContainingFlatMethod(FlatNode fn) {
83 FlatMethod fm = fn2fm.get(fn);
88 public HeapAnalysis getHeapAnalysis() {
89 return disjointAnalysisTaints;
92 public BuildStateMachines getBuildStateMachines() {
93 return buildStateMachines;
96 public OoOJavaAnalysis(State state, TypeUtil typeUtil, CallGraph callGraph, Liveness liveness,
97 ArrayReferencees arrayReferencees) {
99 State.logEvent("Starting OoOJavaAnalysis");
101 this.typeUtil = typeUtil;
102 this.callGraph = callGraph;
103 this.liveness = liveness;
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);
133 // 0th pass, setup a useful mapping of any flat node to the
134 // flat method it is a part of
135 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
136 while (methItr.hasNext()) {
137 Descriptor d = methItr.next();
138 FlatMethod fm = state.getMethodFlat(d);
139 buildFlatNodeToFlatMethod(fm);
141 State.logEvent("OoOJavaAnalysis Oth pass completed");
143 // 1st pass, find basic rblock relations & potential stall sites
144 rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
145 VarSrcTokTable.rblockRel = rblockRel;
147 State.logEvent("OoOJavaAnalysis 1st pass completed");
149 // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
150 Iterator<FlatSESEEnterNode> seseItr = rblockRel.getLocalRootSESEs().iterator();
151 while (seseItr.hasNext()) {
152 FlatSESEEnterNode sese = seseItr.next();
153 livenessAnalysisBackward(sese);
156 State.logEvent("OoOJavaAnalysis 2nd pass completed");
158 // 3rd pass, variable analysis
159 methItr = rblockRel.getMethodsWithSESEs().iterator();
160 while (methItr.hasNext()) {
161 Descriptor d = methItr.next();
162 FlatMethod fm = state.getMethodFlat(d);
163 // starting from roots do a forward, fixed-point
164 // variable analysis for refinement and stalls
165 variableAnalysisForward(fm);
168 State.logEvent("OoOJavaAnalysis 3rd pass completed");
170 // 4th pass, compute liveness contribution from
171 // virtual reads discovered in variable pass
172 seseItr = rblockRel.getLocalRootSESEs().iterator();
173 while (seseItr.hasNext()) {
174 FlatSESEEnterNode sese = seseItr.next();
175 livenessAnalysisBackward(sese);
178 State.logEvent("OoOJavaAnalysis 4th pass completed");
180 // 5th pass, use disjointness with NO FLAGGED REGIONS
181 // to compute taints and effects
183 disjointAnalysisTaints =
184 new Pointer(state, typeUtil, callGraph, rblockRel, liveness, buildStateMachines);
185 ((Pointer) disjointAnalysisTaints).doAnalysis();
187 disjointAnalysisTaints =
188 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null,
189 rblockRel, buildStateMachines,
190 !state.OOODEBUG // only print out in OoOJava debug mode
193 State.logEvent("OoOJavaAnalysis 5th pass completed");
195 // 6th pass, not available analysis FOR VARIABLES!
196 methItr = rblockRel.getMethodsWithSESEs().iterator();
197 while (methItr.hasNext()) {
198 Descriptor d = methItr.next();
199 FlatMethod fm = state.getMethodFlat(d);
200 // compute what is not available at every program
201 // point, in a forward fixed-point pass
202 notAvailableForward(fm);
204 State.logEvent("OoOJavaAnalysis 6th pass completed");
205 // 7th pass, start conflict graphs where a parent's graph has a
206 // node for possibly conflicting children and its own stall sites
207 startConflictGraphs();
208 State.logEvent("OoOJavaAnalysis 7th pass completed");
209 // 8th pass, calculate all possible conflicts without using
210 // reachability info and identify set of FlatNew that next
211 // disjoint reach. analysis should flag
212 Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
213 calculateConflicts(sitesToFlag, false);
214 State.logEvent("OoOJavaAnalysis 8th pass completed");
216 // 9th pass, ask disjoint analysis to compute reachability
217 // for objects that may cause heap conflicts so the most
218 // efficient method to deal with conflict can be computed
220 disjointAnalysisReach =
221 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, sitesToFlag,
222 null, // don't do effects analysis again!
223 null, // no BuildStateMachines needed
224 !state.OOODEBUG // only print out in OoOJava debug mode
226 State.logEvent("OoOJavaAnalysis 9th pass completed");
227 // 10th pass, calculate conflicts with reachability info
228 calculateConflicts(null, true);
229 State.logEvent("OoOJavaAnalysis 10th pass completed");
231 // in RCR/DFJ we want to do some extra processing on the
232 // state machines before they get handed off to code gen,
233 // and we're doing the same effect-conflict traversal needed
234 // to identify heap examiners that are weakly connected, so
235 // accomplish both at the same time
236 pruneMachinesAndFindWeaklyConnectedExaminers();
237 State.logEvent("OoOJavaAnalysis RCR pruneMachines pass completed");
240 // 11th pass, compiling memory Qs! The name "lock" is a legacy
241 // term for the heap dependence queue, or memQ as the runtime calls it
243 State.logEvent("OoOJavaAnalysis 11th pass completed");
245 // 12th pass, compute a plan for code injections
246 methItr = descriptorsToAnalyze.iterator();
247 while (methItr.hasNext()) {
248 Descriptor d = methItr.next();
249 FlatMethod fm = state.getMethodFlat(d);
250 codePlansForward(fm);
253 State.logEvent("OoOJavaAnalysis 12th pass completed");
255 // splice new IR nodes into graph after all
256 // analysis passes are complete
257 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
258 while (spliceItr.hasNext()) {
259 Map.Entry me = (Map.Entry)spliceItr.next();
260 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
261 fwdvn.spliceIntoIR();
263 State.logEvent("OoOJavaAnalysis 13th pass completed");
265 if (state.OOODEBUG) {
268 disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt");
269 writeConflictGraph();
270 } catch (IOException e) {
273 State.logEvent("OoOJavaAnalysis completed");
276 private void buildFlatNodeToFlatMethod(FlatMethod fm) {
277 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
278 flatNodesToVisit.add(fm);
280 Set<FlatNode> flatNodesVisited = new HashSet<FlatNode>();
282 while (!flatNodesToVisit.isEmpty()) {
283 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
284 flatNodesToVisit.remove(fn);
285 flatNodesVisited.add(fn);
289 for (int i = 0; i < fn.numNext(); i++) {
290 FlatNode nn = fn.getNext(i);
291 if (!flatNodesVisited.contains(nn)) {
292 flatNodesToVisit.add(nn);
300 * Iterator iter = sese2conflictGraph.entrySet().iterator(); while
301 * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn = (FlatNode)
302 * e.getKey(); ConflictGraph conflictGraph = (ConflictGraph) e.getValue();
303 * System.out.println("---------------------------------------");
304 * System.out.println("CONFLICT GRAPH for " + fn); Set<String> keySet =
305 * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator();
306 * iterator.hasNext();) { String key = (String) iterator.next(); ConflictNode
307 * node = conflictGraph.id2cn.get(key); System.out.println("key=" + key +
308 * " \n" + node.toStringAllEffects()); } }
311 private void writeFile(Set<FlatNew> sitesToFlag) {
314 BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt"));
316 for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext(); ) {
317 FlatNew fn = (FlatNew) iterator.next();
321 } catch (IOException e) {
327 private void livenessAnalysisBackward(FlatSESEEnterNode fsen) {
329 // flow backward across nodes to compute liveness, and
330 // take special care with sese enter/exit nodes that
331 // alter this from normal liveness analysis
332 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
333 // flatNodesToVisit.add( fm.getFlatExit() );
334 flatNodesToVisit.add(fsen.getFlatExit());
336 while (!flatNodesToVisit.isEmpty()) {
337 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
338 flatNodesToVisit.remove(fn);
340 Set<TempDescriptor> prev = livenessGlobalView.get(fn);
342 // merge sets from control flow joins
343 Set<TempDescriptor> livein = new HashSet<TempDescriptor>();
344 for (int i = 0; i < fn.numNext(); i++) {
345 FlatNode nn = fn.getNext(i);
346 Set<TempDescriptor> s = livenessGlobalView.get(nn);
352 Set<TempDescriptor> curr = liveness_nodeActions(fn, livein);
354 // if a new result, schedule backward nodes for analysis
355 if (!curr.equals(prev)) {
358 livenessGlobalView.put(fn, curr);
359 for (int i = 0; i < fn.numPrev(); i++) {
360 FlatNode nn = fn.getPrev(i);
361 flatNodesToVisit.add(nn);
368 private Set<TempDescriptor> liveness_nodeActions(FlatNode fn, Set<TempDescriptor> liveIn) {
371 case FKind.FlatSESEEnterNode: {
372 // add whatever is live-in at a task enter to that
374 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
375 if (liveIn != null) {
376 fsen.addInVarSet(liveIn);
378 // no break, should also execute default actions
382 // handle effects of statement in reverse, writes then reads
383 TempDescriptor[] writeTemps = fn.writesTemps();
384 for (int i = 0; i < writeTemps.length; ++i) {
385 liveIn.remove(writeTemps[i]);
387 // if we are analyzing code declared directly in a task,
388 FlatSESEEnterNode fsen = rblockRel.getLocalInnerRBlock(fn);
390 // check to see if we are writing to variables that will
391 // be live-out at the task's exit (and therefore should
392 // go in the task's out-var set)
393 FlatSESEExitNode fsexn = fsen.getFlatExit();
394 // note: liveness analysis can have corresponding decisions
395 Set<TempDescriptor> livetemps = liveness.getLiveInTemps(fsen.getfmEnclosing(), fsexn);
396 if (livetemps != null && livetemps.contains(writeTemps[i])) {
397 fsen.addOutVar(writeTemps[i]);
402 TempDescriptor[] readTemps = fn.readsTemps();
403 for (int i = 0; i < readTemps.length; ++i) {
404 liveIn.add(readTemps[i]);
407 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get(fn);
408 if (virtualReadTemps != null) {
409 liveIn.addAll(virtualReadTemps);
419 private void variableAnalysisForward(FlatMethod fm) {
421 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
422 flatNodesToVisit.add(fm);
424 while (!flatNodesToVisit.isEmpty()) {
425 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
426 flatNodesToVisit.remove(fn);
428 VarSrcTokTable prev = variableResults.get(fn);
430 // merge sets from control flow joins
431 VarSrcTokTable curr = new VarSrcTokTable();
432 for (int i = 0; i < fn.numPrev(); i++) {
433 FlatNode nn = fn.getPrev(i);
434 VarSrcTokTable incoming = variableResults.get(nn);
435 curr.merge(incoming);
438 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock(fn);
439 if (currentSESE == null) {
440 currentSESE = rblockRel.getCallerProxySESE();
443 variable_nodeActions(fn, curr, currentSESE);
445 // if a new result, schedule forward nodes for analysis
446 if (!curr.equals(prev)) {
447 variableResults.put(fn, curr);
449 for (int i = 0; i < fn.numNext(); i++) {
450 FlatNode nn = fn.getNext(i);
451 flatNodesToVisit.add(nn);
457 private void variable_nodeActions(FlatNode fn, VarSrcTokTable vstTable,
458 FlatSESEEnterNode currentSESE) {
461 case FKind.FlatSESEEnterNode: {
462 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
463 // ignore currently executing SESE, at this point
464 // the analysis considers a new instance is becoming
467 vstTable.assertConsistency();
471 case FKind.FlatSESEExitNode: {
472 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
474 // fsen is the child of currently executing tasks
475 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
477 // remap all of this child's children tokens to be
478 // from this child as the child exits
479 vstTable.remapChildTokens(fsen);
481 // liveness virtual reads are things that might be
482 // written by an SESE and should be added to the in-set
483 // anything virtually read by this SESE should be pruned
484 // of parent or sibling sources
485 Set<TempDescriptor> liveVars = liveness.getLiveInTemps(fsen.getfmEnclosing(), fn);
487 Set<TempDescriptor> fsenVirtReads =
488 vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen, liveVars);
490 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
491 if (fsenVirtReadsOld != null) {
492 fsenVirtReads.addAll(fsenVirtReadsOld);
494 livenessVirtualReads.put(fn, fsenVirtReads);
496 // virtual reads are forced in-vars!
497 fsen.addInVarSet(fsenVirtReads);
499 // then all child out-set tokens are guaranteed
500 // to be filled in, so clobber those entries with
501 // the latest, clean sources
502 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
503 while (outVarItr.hasNext()) {
504 TempDescriptor outVar = outVarItr.next();
505 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
507 VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
508 vstTable.remove(outVar);
511 vstTable.assertConsistency();
515 case FKind.FlatOpNode: {
516 FlatOpNode fon = (FlatOpNode) fn;
518 if (fon.getOp().getOp() == Operation.ASSIGN) {
519 TempDescriptor lhs = fon.getDest();
520 TempDescriptor rhs = fon.getLeft();
522 vstTable.remove(lhs);
524 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
526 Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
527 while (itr.hasNext()) {
528 VariableSourceToken vst = itr.next();
530 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
533 // when we do x = y for variables, just copy over from a child,
534 // there are two cases:
535 // 1. if the current task is the caller proxy, any local root is a
538 currentSESE.getIsCallerProxySESE()
539 && rblockRel.getLocalRootSESEs().contains(vst.getSESE());
541 // 2. if the child task is a locally-defined child of the current task
542 boolean case2 = currentSESE.getLocalChildren().contains(vst.getSESE());
544 if (case1 || case2) {
545 // if the source comes from a child, copy it over
546 forAddition.add(new VariableSourceToken(ts, vst.getSESE(), vst.getAge(), vst
549 // otherwise, stamp it as us as the source
550 forAddition.add(new VariableSourceToken(ts, currentSESE, new Integer(0), lhs));
554 vstTable.addAll(forAddition);
556 // only break if this is an ASSIGN op node,
557 // otherwise fall through to default case
558 vstTable.assertConsistency();
563 // note that FlatOpNode's that aren't ASSIGN
564 // fall through to this default case
566 TempDescriptor[] writeTemps = fn.writesTemps();
567 if (writeTemps.length > 0) {
569 // for now, when writeTemps > 1, make sure
570 // its a call node, programmer enforce only
571 // doing stuff like calling a print routine
572 if (writeTemps.length > 1) {
573 assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
577 vstTable.remove(writeTemps[0]);
579 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
580 ts.add(writeTemps[0]);
582 vstTable.add(new VariableSourceToken(ts, currentSESE, new Integer(0), writeTemps[0]));
585 vstTable.assertConsistency();
592 private void notAvailableForward(FlatMethod fm) {
594 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
595 flatNodesToVisit.add(fm);
597 while (!flatNodesToVisit.isEmpty()) {
598 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
599 flatNodesToVisit.remove(fn);
601 Set<TempDescriptor> prev = notAvailableResults.get(fn);
603 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
604 for (int i = 0; i < fn.numPrev(); i++) {
605 FlatNode nn = fn.getPrev(i);
606 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
607 if (notAvailIn != null) {
608 curr.addAll(notAvailIn);
612 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock(fn);
613 if (currentSESE == null) {
614 currentSESE = rblockRel.getCallerProxySESE();
617 notAvailable_nodeActions(fn, curr, currentSESE);
619 // if a new result, schedule forward nodes for analysis
620 if (!curr.equals(prev)) {
621 notAvailableResults.put(fn, curr);
623 for (int i = 0; i < fn.numNext(); i++) {
624 FlatNode nn = fn.getNext(i);
625 flatNodesToVisit.add(nn);
631 private void notAvailable_nodeActions(FlatNode fn, Set<TempDescriptor> notAvailSet,
632 FlatSESEEnterNode currentSESE) {
634 // any temps that are removed from the not available set
635 // at this node should be marked in this node's code plan
636 // as temps to be grabbed at runtime!
640 case FKind.FlatSESEEnterNode: {
641 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
643 // keep a copy of what's not available into the SESE
644 // and restore it at the matching exit node
645 Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
646 Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
647 while (tdItr.hasNext()) {
648 notAvailCopy.add(tdItr.next());
650 notAvailableIntoSESE.put(fsen, notAvailCopy);
656 case FKind.FlatSESEExitNode: {
657 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
658 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
660 notAvailSet.addAll(fsen.getOutVarSet());
662 Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
663 assert notAvailIn != null;
664 notAvailSet.addAll(notAvailIn);
668 case FKind.FlatMethod: {
673 case FKind.FlatOpNode: {
674 FlatOpNode fon = (FlatOpNode) fn;
676 if (fon.getOp().getOp() == Operation.ASSIGN) {
677 TempDescriptor lhs = fon.getDest();
678 TempDescriptor rhs = fon.getLeft();
680 // copy makes lhs same availability as rhs
681 if (notAvailSet.contains(rhs)) {
682 notAvailSet.add(lhs);
684 notAvailSet.remove(lhs);
687 // only break if this is an ASSIGN op node,
688 // otherwise fall through to default case
693 // note that FlatOpNode's that aren't ASSIGN
694 // fall through to this default case
696 TempDescriptor[] writeTemps = fn.writesTemps();
697 for (int i = 0; i < writeTemps.length; i++) {
698 TempDescriptor wTemp = writeTemps[i];
699 notAvailSet.remove(wTemp);
701 TempDescriptor[] readTemps = fn.readsTemps();
702 for (int i = 0; i < readTemps.length; i++) {
703 TempDescriptor rTemp = readTemps[i];
704 notAvailSet.remove(rTemp);
706 // if this variable has exactly one source, potentially
707 // get other things from this source as well
708 VarSrcTokTable vstTable = variableResults.get(fn);
710 VSTWrapper vstIfStatic = new VSTWrapper();
711 Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
713 if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
715 VariableSourceToken vst = vstIfStatic.vst;
717 Iterator<VariableSourceToken> availItr =
718 vstTable.get(vst.getSESE(), vst.getAge()).iterator();
720 // look through things that are also available from same source
721 while (availItr.hasNext()) {
722 VariableSourceToken vstAlsoAvail = availItr.next();
724 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
725 while (refVarItr.hasNext()) {
726 TempDescriptor refVarAlso = refVarItr.next();
728 // if a variable is available from the same source, AND it ALSO
729 // only comes from one statically known source, mark it available
730 VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
731 Integer srcTypeAlso =
732 vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed);
733 if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
734 notAvailSet.remove(refVarAlso);
746 private void codePlansForward(FlatMethod fm) {
748 // start from flat method top, visit every node in
749 // method exactly once
750 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
751 flatNodesToVisit.add(fm);
753 Set<FlatNode> visited = new HashSet<FlatNode>();
755 while (!flatNodesToVisit.isEmpty()) {
756 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
757 FlatNode fn = fnItr.next();
759 flatNodesToVisit.remove(fn);
762 // use incoming results as "dot statement" or just
763 // before the current statement
764 VarSrcTokTable dotSTtable = new VarSrcTokTable();
765 for (int i = 0; i < fn.numPrev(); i++) {
766 FlatNode nn = fn.getPrev(i);
767 dotSTtable.merge(variableResults.get(nn));
770 // find dt-st notAvailableSet also
771 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
772 for (int i = 0; i < fn.numPrev(); i++) {
773 FlatNode nn = fn.getPrev(i);
774 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
775 if (notAvailIn != null) {
776 dotSTnotAvailSet.addAll(notAvailIn);
780 Set<TempDescriptor> dotSTlive = livenessGlobalView.get(fn);
782 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock(fn);
783 if (currentSESE == null) {
784 currentSESE = rblockRel.getCallerProxySESE();
787 codePlans_nodeActions(fm, fn, dotSTtable, dotSTnotAvailSet, currentSESE);
789 for (int i = 0; i < fn.numNext(); i++) {
790 FlatNode nn = fn.getNext(i);
792 if (!visited.contains(nn)) {
793 flatNodesToVisit.add(nn);
799 private void codePlans_nodeActions(FlatMethod fm, FlatNode fn, VarSrcTokTable vstTableIn,
800 Set<TempDescriptor> notAvailSetIn, FlatSESEEnterNode currentSESE) {
802 CodePlan plan = new CodePlan(currentSESE);
806 case FKind.FlatSESEEnterNode: {
807 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
809 // track the source types of the in-var set so generated
810 // code at this SESE issue can compute the number of
811 // dependencies properly
812 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
813 while (inVarItr.hasNext()) {
814 TempDescriptor inVar = inVarItr.next();
816 // when we get to an SESE enter node we change the
817 // currentSESE variable of this analysis to the
818 // child that is declared by the enter node, so
819 // in order to classify in-vars correctly, pass
820 // the parent SESE in--at other FlatNode types just
821 // use the currentSESE
822 FlatSESEEnterNode parent = rblockRel.getLocalInnerRBlock(fn);
823 if (parent == null) {
824 parent = rblockRel.getCallerProxySESE();
827 VSTWrapper vstIfStatic = new VSTWrapper();
828 Integer srcType = vstTableIn.getRefVarSrcType(inVar, parent, vstIfStatic);
830 // the current SESE needs a local space to track the dynamic
831 // variable and the child needs space in its SESE record
832 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
833 fsen.addDynamicInVar(inVar);
834 addDynamicVar(parent, fm, inVar);
836 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
837 fsen.addStaticInVar(inVar);
838 VariableSourceToken vst = vstIfStatic.vst;
839 fsen.putStaticInVar2src(inVar, vst);
840 fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
843 assert srcType.equals(VarSrcTokTable.SrcType_READY);
844 fsen.addReadyInVar(inVar);
850 case FKind.FlatSESEExitNode: {
851 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
853 // Classify the sources of out-set variables so code
854 // gen can acquire them from children if necessary
855 // before this task exits
856 FlatSESEEnterNode exiter = fsexn.getFlatEnter();
858 Iterator<TempDescriptor> outVarItr = exiter.getOutVarSet().iterator();
859 while (outVarItr.hasNext()) {
860 TempDescriptor outVar = outVarItr.next();
862 VSTWrapper vstIfStatic = new VSTWrapper();
863 Integer srcType = vstTableIn.getRefVarSrcType(outVar, exiter, vstIfStatic);
865 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
866 // if the out-var is dynamic, put it in the set of dyn out vars
867 // so exiting code gen knows to look for the value, but also put
868 // it in the set of dynamic vars the exiter must track!
869 exiter.addDynamicOutVar(outVar);
870 addDynamicVar(exiter, fm, outVar);
872 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
873 exiter.addStaticOutVar(outVar);
874 VariableSourceToken vst = vstIfStatic.vst;
875 exiter.putStaticOutVar2src(outVar, vst);
876 exiter.addStaticOutVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
879 assert srcType.equals(VarSrcTokTable.SrcType_READY);
880 exiter.addReadyOutVar(outVar);
886 case FKind.FlatOpNode: {
887 FlatOpNode fon = (FlatOpNode) fn;
889 if (fon.getOp().getOp() == Operation.ASSIGN) {
890 TempDescriptor lhs = fon.getDest();
891 TempDescriptor rhs = fon.getLeft();
893 // if this is an op node, don't stall, copy
894 // source and delay until we need to use value
896 // ask whether lhs and rhs sources are dynamic, static, etc.
897 VSTWrapper vstIfStatic = new VSTWrapper();
898 Integer lhsSrcType = vstTableIn.getRefVarSrcType(lhs, currentSESE, vstIfStatic);
899 Integer rhsSrcType = vstTableIn.getRefVarSrcType(rhs, currentSESE, vstIfStatic);
901 if (rhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
902 // if rhs is dynamic going in, lhs will definitely be dynamic
903 // going out of this node, so track that here
904 plan.addDynAssign(lhs, rhs);
905 addDynamicVar(currentSESE, fm, lhs);
906 addDynamicVar(currentSESE, fm, rhs);
908 } else if (lhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
909 // otherwise, if the lhs is dynamic, but the rhs is not, we
910 // need to update the variable's dynamic source as "current SESE"
911 plan.addDynAssign(lhs);
914 // only break if this is an ASSIGN op node,
915 // otherwise fall through to default case
920 // note that FlatOpNode's that aren't ASSIGN
921 // fall through to this default case
924 // a node with no live set has nothing to stall for
925 // note: no reason to check here, remove this....
926 // if (liveSetIn == null) {
930 TempDescriptor[] readarray = fn.readsTemps();
931 for (int i = 0; i < readarray.length; i++) {
932 TempDescriptor readtmp = readarray[i];
934 // ignore temps that are definitely available
935 // when considering to stall on it
936 if (!notAvailSetIn.contains(readtmp)) {
940 // check the source type of this variable
941 VSTWrapper vstIfStatic = new VSTWrapper();
942 Integer srcType = vstTableIn.getRefVarSrcType(readtmp, currentSESE, vstIfStatic);
944 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
945 // 1) It is not clear statically where this variable will
946 // come from, so dynamically we must keep track
947 // along various control paths, and therefore when we stall,
948 // just stall for the exact thing we need and move on
949 plan.addDynamicStall(readtmp);
950 addDynamicVar(currentSESE, fm, readtmp);
952 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
953 // 2) Single token/age pair: Stall for token/age pair, and copy
954 // all live variables with same token/age pair at the same
955 // time. This is the same stuff that the notavaialable analysis
956 // marks as now available.
957 VariableSourceToken vst = vstIfStatic.vst;
959 Iterator<VariableSourceToken> availItr =
960 vstTableIn.get(vst.getSESE(), vst.getAge()).iterator();
962 while (availItr.hasNext()) {
963 VariableSourceToken vstAlsoAvail = availItr.next();
965 // only grab additional stuff that is live
966 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
968 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
970 while (refVarItr.hasNext()) {
971 TempDescriptor refVar = refVarItr.next();
972 // note: this should just use normal liveness in...only want to
973 // copy live variables...
974 if (liveness.getLiveInTemps(fm, fn).contains(refVar)) {
979 if (!copySet.isEmpty()) {
980 plan.addStall2CopySet(vstAlsoAvail, copySet);
985 // the other case for srcs is READY, so do nothing
988 // assert that everything being stalled for is in the
989 // "not available" set coming into this flat node and
990 // that every VST identified is in the possible "stall set"
991 // that represents VST's from children SESE's
999 // identify sese-age pairs that are statically useful
1000 // and should have an associated SESE variable in code
1001 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
1002 // AND ALWAYS GIVE NAMES TO LOCAL PARENTS
1003 Set<VariableSourceToken> staticSet = vstTableIn.get();
1004 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
1005 while (vstItr.hasNext()) {
1006 VariableSourceToken vst = vstItr.next();
1008 // the caller proxy generates useful analysis facts, but we
1009 // never need to generate another name for it in code (it is
1010 // ALWAYS the task executing the local method context)
1011 if (vst.getSESE().getIsCallerProxySESE()) {
1015 SESEandAgePair sap = new SESEandAgePair(vst.getSESE(), vst.getAge());
1016 sap.getSESE().mustTrackAtLeastAge(sap.getAge());
1018 FlatSESEEnterNode sese = currentSESE;
1019 while (sese != null) {
1020 addNeededStaticName(sese, fm, sap);
1021 sese = sese.getLocalParent();
1025 codePlans.put(fn, plan);
1027 // if any variables at this-node-*dot* have a static source (exactly one
1029 // but go to a dynamic source at next-node-*dot*, create a new IR graph
1030 // node on that edge to track the sources dynamically
1031 // NOTE: for this calculation use the currentSESE variable, except when the
1032 // FlatNode fn is an Exit--in that case currentSESE is for the exiting task,
1033 // be we want to consider that the parent is tracking a variable coming out
1034 // of the exiting task
1035 FlatSESEEnterNode fsenDoingTracking;
1036 if (fn instanceof FlatSESEExitNode) {
1037 fsenDoingTracking = currentSESE.getLocalParent();
1039 if (fsenDoingTracking == null) {
1040 // if there is no local parent, there are one of two cases
1041 // 1) the current task is main, in which case this FlatNode
1042 // is the main's exit, and doesn't need to do any of the
1043 // following dynamic tracking
1044 // 2) the current task is defined in a method, so use the
1045 // caller proxy in the variable source calcs below
1046 if (currentSESE.equals(rblockRel.getMainSESE())) {
1049 fsenDoingTracking = rblockRel.getCallerProxySESE();
1053 fsenDoingTracking = currentSESE;
1056 VarSrcTokTable thisVstTable = variableResults.get(fn);
1057 for (int i = 0; i < fn.numNext(); i++) {
1058 FlatNode nn = fn.getNext(i);
1059 VarSrcTokTable nextVstTable = variableResults.get(nn);
1060 // note: using the result of liveness analysis regardless of task
1062 Set<TempDescriptor> nextLiveIn = liveness.getLiveInTemps(fm, nn);
1064 // the table can be null if it is one of the few IR nodes
1065 // completely outside of the root SESE scope
1066 if (nextVstTable != null && nextLiveIn != null) {
1068 Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
1069 thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, fsenDoingTracking);
1071 if (!readyOrStatic2dynamicSet.isEmpty()) {
1073 // either add these results to partial fixed-point result
1074 // or make a new one if we haven't made any here yet
1075 FlatEdge fe = new FlatEdge(fn, nn);
1076 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe);
1078 if (fwdvn == null) {
1080 new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, fsenDoingTracking);
1081 wdvNodesToSpliceIn.put(fe, fwdvn);
1083 fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet);
1090 private void addDynamicVar(FlatSESEEnterNode fsen, FlatMethod fm, TempDescriptor var) {
1093 // note: dynamic variable declarations are always located in the flat method
1094 // that encloses task block
1095 // there is no need to set fnContext to fsen
1096 if (fsen.getIsCallerProxySESE()) {
1097 // attach the dynamic variable to track to
1098 // the flat method, so it can be declared at entry
1101 // otherwise the code context is a task body
1106 ContextTaskNames ctn = fn2contextTaskNames.get(fnContext);
1108 ctn = new ContextTaskNames();
1111 ctn.addDynamicVar(var);
1112 fn2contextTaskNames.put(fnContext, ctn);
1116 private void addNeededStaticName(FlatSESEEnterNode fsen, FlatMethod fm, SESEandAgePair sap) {
1119 if (fsen.getIsCallerProxySESE()) {
1120 // attach the dynamic variable to track to
1121 // the flat method, so it can be declared at entry
1124 // otherwise the code context is a task body
1128 ContextTaskNames ctn = fn2contextTaskNames.get(fnContext);
1130 ctn = new ContextTaskNames();
1133 ctn.addNeededStaticName(sap);
1135 fn2contextTaskNames.put(fnContext, ctn);
1138 private void startConflictGraphs() {
1140 // first, for each task, consider whether it has any children, and if
1141 // effects analysis says they should be a conflict node in the that
1142 // parent's conflict graph
1143 Set<FlatSESEEnterNode> allSESEs = rblockRel.getAllSESEs();
1144 for (Iterator iterator = allSESEs.iterator(); iterator.hasNext(); ) {
1146 FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
1147 if (parent.getIsLeafSESE()) {
1151 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1152 ConflictGraph conflictGraph = sese2conflictGraph.get(parent);
1153 assert conflictGraph == null;
1154 conflictGraph = new ConflictGraph(state);
1156 Set<FlatSESEEnterNode> children = parent.getChildren();
1157 for (Iterator iterator2 = children.iterator(); iterator2.hasNext(); ) {
1158 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
1159 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(child);
1160 conflictGraph.addLiveIn(taint2Effects);
1163 sese2conflictGraph.put(parent, conflictGraph);
1166 // then traverse all methods looking for potential stall sites, and
1167 // add those stall sites as nodes in any task's conflict graph that
1168 // might be executing at the point of the stall site
1169 Iterator<MethodDescriptor> descItr = descriptorsToAnalyze.iterator();
1170 while (descItr.hasNext()) {
1171 MethodDescriptor md = descItr.next();
1172 FlatMethod fm = state.getMethodFlat(md);
1174 addStallSitesToConflictGraphs(fm);
1179 private void addStallSitesToConflictGraphs(FlatMethod fm) {
1181 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1182 flatNodesToVisit.add(fm);
1184 Set<FlatNode> visited = new HashSet<FlatNode>();
1186 while (!flatNodesToVisit.isEmpty()) {
1187 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1188 flatNodesToVisit.remove(fn);
1191 Set<FlatSESEEnterNode> currentSESEs = rblockRel.getPossibleExecutingRBlocks(fn);
1193 conflictGraph_nodeAction(fn, currentSESEs, fm.getMethod().getClassDesc());
1195 // schedule forward nodes for analysis
1196 for (int i = 0; i < fn.numNext(); i++) {
1197 FlatNode nn = fn.getNext(i);
1198 if (!visited.contains(nn)) {
1199 flatNodesToVisit.add(nn);
1205 private void conflictGraph_nodeAction(FlatNode fn, Set<FlatSESEEnterNode> currentSESEs,
1206 ClassDescriptor cd) {
1208 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1210 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1212 // repeat the process of adding a stall site to a conflict graph
1213 // for each task that might be executing at a possible stall site
1214 Iterator<FlatSESEEnterNode> seseItr = currentSESEs.iterator();
1215 while (seseItr.hasNext()) {
1216 FlatSESEEnterNode currentSESE = seseItr.next();
1218 ConflictGraph conflictGraph = sese2conflictGraph.get(currentSESE);
1219 if (conflictGraph == null) {
1220 assert currentSESE.getIsLeafSESE();
1227 switch (fn.kind()) {
1229 case FKind.FlatFieldNode:
1230 case FKind.FlatElementNode: {
1232 if (fn instanceof FlatFieldNode) {
1233 FlatFieldNode ffn = (FlatFieldNode) fn;
1236 FlatElementNode fen = (FlatElementNode) fn;
1240 conflictGraph.addStallSite(taint2Effects, rhs, cd);
1244 case FKind.FlatSetFieldNode:
1245 case FKind.FlatSetElementNode: {
1247 if (fn instanceof FlatSetFieldNode) {
1248 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1249 lhs = fsfn.getDst();
1250 rhs = fsfn.getSrc();
1252 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1253 lhs = fsen.getDst();
1254 rhs = fsen.getSrc();
1257 conflictGraph.addStallSite(taint2Effects, rhs, cd);
1258 conflictGraph.addStallSite(taint2Effects, lhs, cd);
1262 case FKind.FlatCall: {
1263 FlatCall fc = (FlatCall) fn;
1266 conflictGraph.addStallSite(taint2Effects, lhs, cd);
1272 if (conflictGraph.id2cn.size() > 0) {
1273 sese2conflictGraph.put(currentSESE, conflictGraph);
1278 private void calculateConflicts(Set<FlatNew> sitesToFlag, boolean useReachInfo) {
1280 // decide fine-grain edge or coarse-grain edge among all vertexes by
1281 // pair-wise comparison
1282 Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
1283 while (seseIter.hasNext()) {
1284 FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next();
1285 ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
1288 // clear current conflict before recalculating with reachability info
1289 conflictGraph.clearAllConflictEdge();
1290 conflictGraph.setDisJointAnalysis(disjointAnalysisReach);
1291 conflictGraph.setFMEnclosing(sese.getfmEnclosing());
1293 conflictGraph.analyzeConflicts(sitesToFlag, useReachInfo);
1294 sese2conflictGraph.put(sese, conflictGraph);
1298 private void writeConflictGraph() {
1299 Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
1300 while (keyEnum.hasMoreElements()) {
1301 FlatNode key = (FlatNode) keyEnum.nextElement();
1302 ConflictGraph cg = sese2conflictGraph.get(key);
1304 if (cg.hasConflictEdge()) {
1305 cg.writeGraph("ConflictGraphFor" + key, false);
1307 } catch (IOException e) {
1308 System.out.println("Error writing");
1314 // the traversal for pruning state machines and finding
1315 // machines that are weakly connected BOTH consider conflicting
1316 // effects between heap roots, so it is smart to compute all of
1318 public void pruneMachinesAndFindWeaklyConnectedExaminers() {
1319 ProcessStateMachines psm = new ProcessStateMachines(buildStateMachines, rblockRel);
1321 buildStateMachines.writeStateMachines("pruned");
1324 private void synthesizeLocks() {
1325 // for every conflict graph, generate a set of memory queues
1326 // (called SESELock in this code!) to cover the graph
1327 Set<Map.Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
1328 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext(); ) {
1329 Map.Entry<FlatNode, ConflictGraph> graphEntry =
1330 (Map.Entry<FlatNode, ConflictGraph>)iterator.next();
1331 FlatNode sese = graphEntry.getKey();
1332 ConflictGraph conflictGraph = graphEntry.getValue();
1333 calculateCovering(conflictGraph);
1337 private void calculateCovering(ConflictGraph conflictGraph) {
1338 uniqueLockSetId = 0; // reset lock counter for every new conflict graph
1339 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1340 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1341 HashSet<SESELock> lockSet = new HashSet<SESELock>();
1343 Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1344 for (Iterator iterator = tempCover.iterator(); iterator.hasNext(); ) {
1345 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1346 if (conflictEdge.isCoarseEdge()) {
1347 coarseToCover.add(conflictEdge);
1349 fineToCover.add(conflictEdge);
1353 HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
1354 toCover.addAll(fineToCover);
1355 toCover.addAll(coarseToCover);
1357 while (!toCover.isEmpty()) {
1359 SESELock seseLock = new SESELock();
1360 seseLock.setID(uniqueLockSetId++);
1364 do { // fine-grained edge
1368 for (Iterator iterator = fineToCover.iterator(); iterator.hasNext(); ) {
1371 ConflictEdge edge = (ConflictEdge) iterator.next();
1372 if (seseLock.getConflictNodeSet().size() == 0) {
1374 if (seseLock.isWriteNode(edge.getVertexU())) {
1375 // mark as fine_write
1376 if (edge.getVertexU().isStallSiteNode()) {
1377 type = ConflictNode.PARENT_WRITE;
1379 type = ConflictNode.FINE_WRITE;
1381 seseLock.addConflictNode(edge.getVertexU(), type);
1383 // mark as fine_read
1384 if (edge.getVertexU().isStallSiteNode()) {
1385 type = ConflictNode.PARENT_READ;
1387 type = ConflictNode.FINE_READ;
1389 seseLock.addConflictNode(edge.getVertexU(), type);
1391 if (edge.getVertexV() != edge.getVertexU()) {
1392 if (seseLock.isWriteNode(edge.getVertexV())) {
1393 // mark as fine_write
1394 if (edge.getVertexV().isStallSiteNode()) {
1395 type = ConflictNode.PARENT_WRITE;
1397 type = ConflictNode.FINE_WRITE;
1399 seseLock.addConflictNode(edge.getVertexV(), type);
1401 // mark as fine_read
1402 if (edge.getVertexV().isStallSiteNode()) {
1403 type = ConflictNode.PARENT_READ;
1405 type = ConflictNode.FINE_READ;
1407 seseLock.addConflictNode(edge.getVertexV(), type);
1411 seseLock.addConflictEdge(edge);
1412 fineToCover.remove(edge);
1413 break; // exit iterator loop
1414 } // end of initial setup
1416 ConflictNode newNode;
1417 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1418 // new node has a fine-grained edge to all current node
1419 // If there is a coarse grained edge where need a fine edge, it's
1420 // okay to add the node
1421 // but the edge must remain uncovered.
1425 if (seseLock.containsConflictNode(newNode)) {
1426 seseLock.addEdge(edge);
1427 fineToCover.remove(edge);
1431 if (seseLock.isWriteNode(newNode)) {
1432 if (newNode.isStallSiteNode()) {
1433 type = ConflictNode.PARENT_WRITE;
1435 type = ConflictNode.FINE_WRITE;
1437 seseLock.setNodeType(newNode, type);
1439 if (newNode.isStallSiteNode()) {
1440 type = ConflictNode.PARENT_READ;
1442 type = ConflictNode.FINE_READ;
1444 seseLock.setNodeType(newNode, type);
1447 seseLock.addEdge(edge);
1448 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1449 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext(); ) {
1450 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1452 // mark all fine edges between new node and nodes in the group as
1454 if (!conflictEdge.getVertexU().equals(newNode)) {
1455 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1457 seseLock.addConflictEdge(conflictEdge);
1458 fineToCover.remove(conflictEdge);
1460 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1461 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1463 seseLock.addConflictEdge(conflictEdge);
1464 fineToCover.remove(conflictEdge);
1470 break; // exit iterator loop
1475 HashSet<ConflictEdge> notCovered = new HashSet<ConflictEdge>();
1479 for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext(); ) {
1481 ConflictEdge edge = (ConflictEdge) iterator.next();
1482 if (seseLock.getConflictNodeSet().size() == 0) {
1484 if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
1485 // node has a coarse-grained edge with itself
1486 if (!(edge.getVertexU().isStallSiteNode())) {
1487 // and it is not parent
1488 type = ConflictNode.SCC;
1491 type = ConflictNode.PARENT_COARSE;
1493 type = ConflictNode.PARENT_WRITE;
1496 seseLock.addConflictNode(edge.getVertexU(), type);
1498 if (edge.getVertexU().isStallSiteNode()) {
1500 type = ConflictNode.PARENT_COARSE;
1502 if (edge.getVertexU().getWriteEffectSet().isEmpty()) {
1503 type = ConflictNode.PARENT_READ;
1505 type = ConflictNode.PARENT_WRITE;
1509 type = ConflictNode.COARSE;
1511 seseLock.addConflictNode(edge.getVertexU(), type);
1513 if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
1514 // node has a coarse-grained edge with itself
1515 if (!(edge.getVertexV().isStallSiteNode())) {
1516 // and it is not parent
1517 type = ConflictNode.SCC;
1520 type = ConflictNode.PARENT_COARSE;
1522 type = ConflictNode.PARENT_WRITE;
1525 seseLock.addConflictNode(edge.getVertexV(), type);
1527 if (edge.getVertexV().isStallSiteNode()) {
1529 type = ConflictNode.PARENT_COARSE;
1531 if (edge.getVertexV().getWriteEffectSet().isEmpty()) {
1532 type = ConflictNode.PARENT_READ;
1534 type = ConflictNode.PARENT_WRITE;
1538 type = ConflictNode.COARSE;
1540 seseLock.addConflictNode(edge.getVertexV(), type);
1543 coarseToCover.remove(edge);
1544 seseLock.addConflictEdge(edge);
1545 break; // exit iterator loop
1546 } // end of initial setup
1548 ConflictNode newNode;
1549 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1550 // new node has a coarse-grained edge to all fine-read, fine-write,
1554 if (newNode.isInVarNode() && (!seseLock.hasSelfCoarseEdge(newNode))
1555 && seseLock.hasCoarseEdgeWithParentCoarse(newNode)) {
1556 // this case can't be covered by this queue
1557 coarseToCover.remove(edge);
1558 notCovered.add(edge);
1562 if (seseLock.containsConflictNode(newNode)) {
1563 seseLock.addEdge(edge);
1564 coarseToCover.remove(edge);
1568 if (seseLock.hasSelfCoarseEdge(newNode)) {
1570 if (newNode.isStallSiteNode()) {
1571 type = ConflictNode.PARENT_COARSE;
1573 type = ConflictNode.SCC;
1575 seseLock.setNodeType(newNode, type);
1577 if (newNode.isStallSiteNode()) {
1578 type = ConflictNode.PARENT_COARSE;
1580 type = ConflictNode.COARSE;
1582 seseLock.setNodeType(newNode, type);
1585 seseLock.addEdge(edge);
1586 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1587 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext(); ) {
1588 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1589 // mark all coarse edges between new node and nodes in the group
1591 if (!conflictEdge.getVertexU().equals(newNode)) {
1592 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1594 seseLock.addConflictEdge(conflictEdge);
1595 coarseToCover.remove(conflictEdge);
1597 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1598 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1600 seseLock.addConflictEdge(conflictEdge);
1601 coarseToCover.remove(conflictEdge);
1606 break; // exit iterator loop
1612 lockSet.add(seseLock);
1615 coarseToCover.addAll(notCovered);
1616 toCover.addAll(fineToCover);
1617 toCover.addAll(coarseToCover);
1621 conflictGraph2SESELock.put(conflictGraph, lockSet);
1624 public ConflictGraph getConflictGraph(FlatNode sese) {
1625 return sese2conflictGraph.get(sese);
1628 public Set<SESELock> getLockMappings(ConflictGraph graph) {
1629 return conflictGraph2SESELock.get(graph);
1632 public Set<FlatSESEEnterNode> getAllSESEs() {
1633 return rblockRel.getAllSESEs();
1636 public FlatSESEEnterNode getMainSESE() {
1637 return rblockRel.getMainSESE();
1640 public FlatSESEEnterNode getCallerProxySESE() {
1641 return rblockRel.getCallerProxySESE();
1644 public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks(FlatNode fn) {
1645 return rblockRel.getPossibleExecutingRBlocks(fn);
1648 public void writeReports(String timeReport) throws java.io.IOException {
1650 BufferedWriter bw = new BufferedWriter(new FileWriter("ooojReport_summary.txt"));
1651 bw.write("OoOJava Analysis Results\n\n");
1652 bw.write(timeReport + "\n\n");
1653 printSESEHierarchy(bw);
1658 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
1659 while (methItr.hasNext()) {
1660 MethodDescriptor md = methItr.next();
1661 FlatMethod fm = state.getMethodFlat(md);
1664 new BufferedWriter(new FileWriter("ooojReport_" + md.getClassMethodName()
1665 + md.getSafeMethodDescriptor() + ".txt"));
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"
1671 + fm.printMethod(livenessGlobalView));
1672 bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults));
1673 bw.write("\n\nNot Available Results-Out\n---------------------\n"
1674 + fm.printMethod(notAvailableResults));
1675 bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans));
1681 private void printSESEHierarchy(BufferedWriter bw) throws java.io.IOException {
1682 bw.write("SESE Local Hierarchy\n--------------\n");
1683 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getLocalRootSESEs().iterator();
1684 while (rootItr.hasNext()) {
1685 FlatSESEEnterNode root = rootItr.next();
1686 printSESEHierarchyTree(bw, root, 0);
1690 private void printSESEHierarchyTree(BufferedWriter bw, FlatSESEEnterNode fsen, int depth)
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");
1734 tItr = fsen.getOutVarSet().iterator();
1735 while (tItr.hasNext()) {
1736 TempDescriptor outVar = tItr.next();
1737 if (fsen.getReadyOutVarSet().contains(outVar)) {
1738 bw.write(" (ready) " + outVar + "\n");
1740 if (fsen.getStaticOutVarSet().contains(outVar)) {
1741 bw.write(" (static) " + outVar + " from " + fsen.getStaticOutVarSrc(outVar) + "\n");
1743 if (fsen.getDynamicOutVarSet().contains(outVar)) {
1744 bw.write(" (dynamic)" + outVar + "\n");
1748 bw.write(" local parent: " + fsen.getLocalParent() + "\n");
1749 bw.write(" local children: " + fsen.getLocalChildren() + "\n");
1751 bw.write(" possible parents: " + fsen.getParents() + "\n");
1752 bw.write(" possible children: " + fsen.getChildren() + "\n");