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 // run liveness analysis for each sese blocks
151 Iterator<FlatSESEEnterNode> seseItr = rblockRel.getAllSESEs().iterator();
152 while (seseItr.hasNext()) {
153 FlatSESEEnterNode sese = seseItr.next();
154 livenessAnalysisBackward(sese);
157 State.logEvent("OoOJavaAnalysis 2nd pass completed");
159 // 3rd pass, variable analysis
160 methItr = rblockRel.getMethodsWithSESEs().iterator();
161 while (methItr.hasNext()) {
162 Descriptor d = methItr.next();
163 FlatMethod fm = state.getMethodFlat(d);
164 // starting from roots do a forward, fixed-point
165 // variable analysis for refinement and stalls
166 variableAnalysisForward(fm);
169 State.logEvent("OoOJavaAnalysis 3rd pass completed");
171 // 4th pass, compute liveness contribution from
172 // virtual reads discovered in variable pass
173 seseItr = rblockRel.getLocalRootSESEs().iterator();
174 while (seseItr.hasNext()) {
175 FlatSESEEnterNode sese = seseItr.next();
176 livenessAnalysisBackward(sese);
179 State.logEvent("OoOJavaAnalysis 4th pass completed");
181 // 5th pass, use disjointness with NO FLAGGED REGIONS
182 // to compute taints and effects
184 disjointAnalysisTaints =
185 new Pointer(state, typeUtil, callGraph, rblockRel, liveness, buildStateMachines);
186 ((Pointer) disjointAnalysisTaints).doAnalysis();
188 disjointAnalysisTaints =
189 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null,
190 rblockRel, buildStateMachines,
191 !state.OOODEBUG // only print out in OoOJava debug mode
194 State.logEvent("OoOJavaAnalysis 5th pass completed");
196 // 6th pass, not available analysis FOR VARIABLES!
197 methItr = rblockRel.getMethodsWithSESEs().iterator();
198 while (methItr.hasNext()) {
199 Descriptor d = methItr.next();
200 FlatMethod fm = state.getMethodFlat(d);
201 // compute what is not available at every program
202 // point, in a forward fixed-point pass
203 notAvailableForward(fm);
205 State.logEvent("OoOJavaAnalysis 6th pass completed");
206 // 7th pass, start conflict graphs where a parent's graph has a
207 // node for possibly conflicting children and its own stall sites
208 startConflictGraphs();
209 State.logEvent("OoOJavaAnalysis 7th pass completed");
210 // 8th pass, calculate all possible conflicts without using
211 // reachability info and identify set of FlatNew that next
212 // disjoint reach. analysis should flag
213 Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
214 calculateConflicts(sitesToFlag, false);
215 State.logEvent("OoOJavaAnalysis 8th pass completed");
217 // 9th pass, ask disjoint analysis to compute reachability
218 // for objects that may cause heap conflicts so the most
219 // efficient method to deal with conflict can be computed
221 disjointAnalysisReach =
222 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, sitesToFlag,
223 null, // don't do effects analysis again!
224 null, // no BuildStateMachines needed
225 !state.OOODEBUG // only print out in OoOJava debug mode
227 State.logEvent("OoOJavaAnalysis 9th pass completed");
228 // 10th pass, calculate conflicts with reachability info
229 calculateConflicts(null, true);
230 State.logEvent("OoOJavaAnalysis 10th pass completed");
232 // in RCR/DFJ we want to do some extra processing on the
233 // state machines before they get handed off to code gen,
234 // and we're doing the same effect-conflict traversal needed
235 // to identify heap examiners that are weakly connected, so
236 // accomplish both at the same time
237 pruneMachinesAndFindWeaklyConnectedExaminers();
238 State.logEvent("OoOJavaAnalysis RCR pruneMachines pass completed");
241 // 11th pass, compiling memory Qs! The name "lock" is a legacy
242 // term for the heap dependence queue, or memQ as the runtime calls it
244 State.logEvent("OoOJavaAnalysis 11th pass completed");
246 // 12th pass, compute a plan for code injections
247 methItr = descriptorsToAnalyze.iterator();
248 while (methItr.hasNext()) {
249 Descriptor d = methItr.next();
250 FlatMethod fm = state.getMethodFlat(d);
251 codePlansForward(fm);
254 State.logEvent("OoOJavaAnalysis 12th pass completed");
256 // splice new IR nodes into graph after all
257 // analysis passes are complete
258 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
259 while (spliceItr.hasNext()) {
260 Map.Entry me = (Map.Entry)spliceItr.next();
261 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
262 fwdvn.spliceIntoIR();
264 State.logEvent("OoOJavaAnalysis 13th pass completed");
266 if (state.OOODEBUG) {
269 disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt");
270 writeConflictGraph();
271 } catch (IOException e) {
274 State.logEvent("OoOJavaAnalysis completed");
277 private void buildFlatNodeToFlatMethod(FlatMethod fm) {
278 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
279 flatNodesToVisit.add(fm);
281 Set<FlatNode> flatNodesVisited = new HashSet<FlatNode>();
283 while (!flatNodesToVisit.isEmpty()) {
284 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
285 flatNodesToVisit.remove(fn);
286 flatNodesVisited.add(fn);
290 for (int i = 0; i < fn.numNext(); i++) {
291 FlatNode nn = fn.getNext(i);
292 if (!flatNodesVisited.contains(nn)) {
293 flatNodesToVisit.add(nn);
301 * Iterator iter = sese2conflictGraph.entrySet().iterator(); while
302 * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn = (FlatNode)
303 * e.getKey(); ConflictGraph conflictGraph = (ConflictGraph) e.getValue();
304 * System.out.println("---------------------------------------");
305 * System.out.println("CONFLICT GRAPH for " + fn); Set<String> keySet =
306 * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator();
307 * iterator.hasNext();) { String key = (String) iterator.next(); ConflictNode
308 * node = conflictGraph.id2cn.get(key); System.out.println("key=" + key +
309 * " \n" + node.toStringAllEffects()); } }
312 private void writeFile(Set<FlatNew> sitesToFlag) {
315 BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt"));
317 for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext(); ) {
318 FlatNew fn = (FlatNew) iterator.next();
322 } catch (IOException e) {
329 private void livenessAnalysisBackward(FlatSESEEnterNode fsen) {
331 // each task maintains a local liveness result
332 Hashtable<FlatNode, Set<TempDescriptor>> livenessLocalView =
333 new Hashtable<FlatNode, Set<TempDescriptor>>();
335 // flow backward across nodes to compute liveness.
336 // it contributes liveness results to the global view
337 // only if the current flat node belongs directly to the currently analyzing
339 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
340 flatNodesToVisit.add(fsen.getFlatExit());
342 while (!flatNodesToVisit.isEmpty()) {
343 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
344 flatNodesToVisit.remove(fn);
346 Set<TempDescriptor> prev = livenessLocalView.get(fn);
348 // merge sets from control flow joins
349 Set<TempDescriptor> livein = new HashSet<TempDescriptor>();
350 for (int i = 0; i < fn.numNext(); i++) {
351 FlatNode nn = fn.getNext(i);
352 Set<TempDescriptor> s = livenessLocalView.get(nn);
358 Set<TempDescriptor> curr = liveness_nodeActions(fsen, fn, livein);
360 // if a new result, schedule backward nodes for analysis
361 if (!curr.equals(prev)) {
364 livenessLocalView.put(fn, curr);
366 if (rblockRel.getLocalInnerRBlock(fn).equals(fsen)) {
367 // the current flat node belongs to the currently analyzing sese
368 // store its liveness in the gloval view
369 livenessGlobalView.put(fn, curr);
372 for (int i = 0; i < fn.numPrev(); i++) {
373 FlatNode nn = fn.getPrev(i);
374 flatNodesToVisit.add(nn);
381 private Set<TempDescriptor> liveness_nodeActions(FlatSESEEnterNode currSESE, FlatNode fn,
382 Set<TempDescriptor> liveIn) {
386 case FKind.FlatSESEEnterNode: {
387 // add whatever is live-in at a task enter to that
389 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
390 if (currSESE.equals(fsen)) {
391 if (liveIn != null) {
392 fsen.addInVarSet(liveIn);
394 // no break, should also execute default actions
399 // handle effects of statement in reverse, writes then reads
400 TempDescriptor[] writeTemps = fn.writesTemps();
401 for (int i = 0; i < writeTemps.length; ++i) {
402 liveIn.remove(writeTemps[i]);
404 // if we are analyzing code declared directly in a task,
405 FlatSESEEnterNode fsen = rblockRel.getLocalInnerRBlock(fn);
407 // check to see if we are writing to variables that will
408 // be live-out at the task's exit (and therefore should
409 // go in the task's out-var set)
410 FlatSESEExitNode fsexn = fsen.getFlatExit();
411 // note: liveness analysis can have corresponding decisions
412 Set<TempDescriptor> livetemps = liveness.getLiveInTemps(fsen.getfmEnclosing(), fsexn);
413 if (livetemps != null && livetemps.contains(writeTemps[i])) {
414 fsen.addOutVar(writeTemps[i]);
419 TempDescriptor[] readTemps = fn.readsTemps();
420 for (int i = 0; i < readTemps.length; ++i) {
421 liveIn.add(readTemps[i]);
424 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get(fn);
425 if (virtualReadTemps != null) {
426 liveIn.addAll(virtualReadTemps);
436 private void variableAnalysisForward(FlatMethod fm) {
438 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
439 flatNodesToVisit.add(fm);
441 while (!flatNodesToVisit.isEmpty()) {
442 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
443 flatNodesToVisit.remove(fn);
445 VarSrcTokTable prev = variableResults.get(fn);
447 // merge sets from control flow joins
448 VarSrcTokTable curr = new VarSrcTokTable();
449 for (int i = 0; i < fn.numPrev(); i++) {
450 FlatNode nn = fn.getPrev(i);
451 VarSrcTokTable incoming = variableResults.get(nn);
452 curr.merge(incoming);
455 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock(fn);
456 if (currentSESE == null) {
457 currentSESE = rblockRel.getCallerProxySESE();
460 variable_nodeActions(fn, curr, currentSESE);
462 // if a new result, schedule forward nodes for analysis
463 if (!curr.equals(prev)) {
464 variableResults.put(fn, curr);
466 for (int i = 0; i < fn.numNext(); i++) {
467 FlatNode nn = fn.getNext(i);
468 flatNodesToVisit.add(nn);
474 private void variable_nodeActions(FlatNode fn, VarSrcTokTable vstTable,
475 FlatSESEEnterNode currentSESE) {
478 case FKind.FlatSESEEnterNode: {
479 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
480 // ignore currently executing SESE, at this point
481 // the analysis considers a new instance is becoming
484 vstTable.assertConsistency();
488 case FKind.FlatSESEExitNode: {
489 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
491 // fsen is the child of currently executing tasks
492 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
494 // remap all of this child's children tokens to be
495 // from this child as the child exits
496 vstTable.remapChildTokens(fsen);
498 // liveness virtual reads are things that might be
499 // written by an SESE and should be added to the in-set
500 // anything virtually read by this SESE should be pruned
501 // of parent or sibling sources
502 // Set<TempDescriptor> liveVars = liveness.getLiveInTemps(fsen.getfmEnclosing(), fn);
503 Set<TempDescriptor> liveVars = livenessGlobalView.get(fn);
505 Set<TempDescriptor> fsenVirtReads =
506 vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen, liveVars);
508 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
509 if (fsenVirtReadsOld != null) {
510 fsenVirtReads.addAll(fsenVirtReadsOld);
512 livenessVirtualReads.put(fn, fsenVirtReads);
514 // virtual reads are forced in-vars!
515 fsen.addInVarSet(fsenVirtReads);
517 // then all child out-set tokens are guaranteed
518 // to be filled in, so clobber those entries with
519 // the latest, clean sources
520 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
521 while (outVarItr.hasNext()) {
522 TempDescriptor outVar = outVarItr.next();
523 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
525 VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
526 vstTable.remove(outVar);
529 vstTable.assertConsistency();
533 case FKind.FlatOpNode: {
534 FlatOpNode fon = (FlatOpNode) fn;
536 if (fon.getOp().getOp() == Operation.ASSIGN) {
537 TempDescriptor lhs = fon.getDest();
538 TempDescriptor rhs = fon.getLeft();
540 vstTable.remove(lhs);
542 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
544 Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
545 while (itr.hasNext()) {
546 VariableSourceToken vst = itr.next();
548 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
551 // when we do x = y for variables, just copy over from a child,
552 // there are two cases:
553 // 1. if the current task is the caller proxy, any local root is a
556 currentSESE.getIsCallerProxySESE()
557 && rblockRel.getLocalRootSESEs().contains(vst.getSESE());
559 // 2. if the child task is a locally-defined child of the current task
560 boolean case2 = currentSESE.getLocalChildren().contains(vst.getSESE());
562 if (case1 || case2) {
563 // if the source comes from a child, copy it over
564 forAddition.add(new VariableSourceToken(ts, vst.getSESE(), vst.getAge(), vst
567 // otherwise, stamp it as us as the source
568 forAddition.add(new VariableSourceToken(ts, currentSESE, new Integer(0), lhs));
572 vstTable.addAll(forAddition);
574 // only break if this is an ASSIGN op node,
575 // otherwise fall through to default case
576 vstTable.assertConsistency();
581 // note that FlatOpNode's that aren't ASSIGN
582 // fall through to this default case
584 TempDescriptor[] writeTemps = fn.writesTemps();
585 if (writeTemps.length > 0) {
587 // for now, when writeTemps > 1, make sure
588 // its a call node, programmer enforce only
589 // doing stuff like calling a print routine
590 if (writeTemps.length > 1) {
591 assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
595 vstTable.remove(writeTemps[0]);
597 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
598 ts.add(writeTemps[0]);
600 vstTable.add(new VariableSourceToken(ts, currentSESE, new Integer(0), writeTemps[0]));
603 vstTable.assertConsistency();
610 private void notAvailableForward(FlatMethod fm) {
612 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
613 flatNodesToVisit.add(fm);
615 while (!flatNodesToVisit.isEmpty()) {
616 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
617 flatNodesToVisit.remove(fn);
619 Set<TempDescriptor> prev = notAvailableResults.get(fn);
621 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
622 for (int i = 0; i < fn.numPrev(); i++) {
623 FlatNode nn = fn.getPrev(i);
624 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
625 if (notAvailIn != null) {
626 curr.addAll(notAvailIn);
630 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock(fn);
631 if (currentSESE == null) {
632 currentSESE = rblockRel.getCallerProxySESE();
635 notAvailable_nodeActions(fn, curr, currentSESE);
637 // if a new result, schedule forward nodes for analysis
638 if (!curr.equals(prev)) {
639 notAvailableResults.put(fn, curr);
641 for (int i = 0; i < fn.numNext(); i++) {
642 FlatNode nn = fn.getNext(i);
643 flatNodesToVisit.add(nn);
649 private void notAvailable_nodeActions(FlatNode fn, Set<TempDescriptor> notAvailSet,
650 FlatSESEEnterNode currentSESE) {
652 // any temps that are removed from the not available set
653 // at this node should be marked in this node's code plan
654 // as temps to be grabbed at runtime!
658 case FKind.FlatSESEEnterNode: {
659 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
661 // keep a copy of what's not available into the SESE
662 // and restore it at the matching exit node
663 Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
664 Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
665 while (tdItr.hasNext()) {
666 notAvailCopy.add(tdItr.next());
668 notAvailableIntoSESE.put(fsen, notAvailCopy);
674 case FKind.FlatSESEExitNode: {
675 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
676 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
678 notAvailSet.addAll(fsen.getOutVarSet());
680 Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
681 assert notAvailIn != null;
682 notAvailSet.addAll(notAvailIn);
686 case FKind.FlatMethod: {
691 case FKind.FlatOpNode: {
692 FlatOpNode fon = (FlatOpNode) fn;
694 if (fon.getOp().getOp() == Operation.ASSIGN) {
695 TempDescriptor lhs = fon.getDest();
696 TempDescriptor rhs = fon.getLeft();
698 // copy makes lhs same availability as rhs
699 if (notAvailSet.contains(rhs)) {
700 notAvailSet.add(lhs);
702 notAvailSet.remove(lhs);
705 // only break if this is an ASSIGN op node,
706 // otherwise fall through to default case
711 // note that FlatOpNode's that aren't ASSIGN
712 // fall through to this default case
714 TempDescriptor[] writeTemps = fn.writesTemps();
715 for (int i = 0; i < writeTemps.length; i++) {
716 TempDescriptor wTemp = writeTemps[i];
717 notAvailSet.remove(wTemp);
719 TempDescriptor[] readTemps = fn.readsTemps();
720 for (int i = 0; i < readTemps.length; i++) {
721 TempDescriptor rTemp = readTemps[i];
722 notAvailSet.remove(rTemp);
724 // if this variable has exactly one source, potentially
725 // get other things from this source as well
726 VarSrcTokTable vstTable = variableResults.get(fn);
728 VSTWrapper vstIfStatic = new VSTWrapper();
729 Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
731 if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
733 VariableSourceToken vst = vstIfStatic.vst;
735 Iterator<VariableSourceToken> availItr =
736 vstTable.get(vst.getSESE(), vst.getAge()).iterator();
738 // look through things that are also available from same source
739 while (availItr.hasNext()) {
740 VariableSourceToken vstAlsoAvail = availItr.next();
742 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
743 while (refVarItr.hasNext()) {
744 TempDescriptor refVarAlso = refVarItr.next();
746 // if a variable is available from the same source, AND it ALSO
747 // only comes from one statically known source, mark it available
748 VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
749 Integer srcTypeAlso =
750 vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed);
751 if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
752 notAvailSet.remove(refVarAlso);
764 private void codePlansForward(FlatMethod fm) {
766 // start from flat method top, visit every node in
767 // method exactly once
768 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
769 flatNodesToVisit.add(fm);
771 Set<FlatNode> visited = new HashSet<FlatNode>();
773 while (!flatNodesToVisit.isEmpty()) {
774 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
775 FlatNode fn = fnItr.next();
777 flatNodesToVisit.remove(fn);
780 // use incoming results as "dot statement" or just
781 // before the current statement
782 VarSrcTokTable dotSTtable = new VarSrcTokTable();
783 for (int i = 0; i < fn.numPrev(); i++) {
784 FlatNode nn = fn.getPrev(i);
785 dotSTtable.merge(variableResults.get(nn));
788 // find dt-st notAvailableSet also
789 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
790 for (int i = 0; i < fn.numPrev(); i++) {
791 FlatNode nn = fn.getPrev(i);
792 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
793 if (notAvailIn != null) {
794 dotSTnotAvailSet.addAll(notAvailIn);
798 Set<TempDescriptor> dotSTlive = livenessGlobalView.get(fn);
800 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock(fn);
801 if (currentSESE == null) {
802 currentSESE = rblockRel.getCallerProxySESE();
805 codePlans_nodeActions(fm, fn, dotSTtable, dotSTnotAvailSet, currentSESE);
807 for (int i = 0; i < fn.numNext(); i++) {
808 FlatNode nn = fn.getNext(i);
810 if (!visited.contains(nn)) {
811 flatNodesToVisit.add(nn);
817 private void codePlans_nodeActions(FlatMethod fm, FlatNode fn, VarSrcTokTable vstTableIn,
818 Set<TempDescriptor> notAvailSetIn, FlatSESEEnterNode currentSESE) {
820 CodePlan plan = new CodePlan(currentSESE);
824 case FKind.FlatSESEEnterNode: {
825 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
827 // track the source types of the in-var set so generated
828 // code at this SESE issue can compute the number of
829 // dependencies properly
830 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
831 while (inVarItr.hasNext()) {
832 TempDescriptor inVar = inVarItr.next();
834 // when we get to an SESE enter node we change the
835 // currentSESE variable of this analysis to the
836 // child that is declared by the enter node, so
837 // in order to classify in-vars correctly, pass
838 // the parent SESE in--at other FlatNode types just
839 // use the currentSESE
840 FlatSESEEnterNode parent = rblockRel.getLocalInnerRBlock(fn);
841 if (parent == null) {
842 parent = rblockRel.getCallerProxySESE();
845 VSTWrapper vstIfStatic = new VSTWrapper();
846 Integer srcType = vstTableIn.getRefVarSrcType(inVar, parent, vstIfStatic);
848 // the current SESE needs a local space to track the dynamic
849 // variable and the child needs space in its SESE record
850 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
851 fsen.addDynamicInVar(inVar);
852 addDynamicVar(parent, fm, inVar);
854 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
855 fsen.addStaticInVar(inVar);
856 VariableSourceToken vst = vstIfStatic.vst;
857 fsen.putStaticInVar2src(inVar, vst);
858 fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
861 assert srcType.equals(VarSrcTokTable.SrcType_READY);
862 fsen.addReadyInVar(inVar);
868 case FKind.FlatSESEExitNode: {
869 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
871 // Classify the sources of out-set variables so code
872 // gen can acquire them from children if necessary
873 // before this task exits
874 FlatSESEEnterNode exiter = fsexn.getFlatEnter();
876 Iterator<TempDescriptor> outVarItr = exiter.getOutVarSet().iterator();
877 while (outVarItr.hasNext()) {
878 TempDescriptor outVar = outVarItr.next();
880 VSTWrapper vstIfStatic = new VSTWrapper();
881 Integer srcType = vstTableIn.getRefVarSrcType(outVar, exiter, vstIfStatic);
883 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
884 // if the out-var is dynamic, put it in the set of dyn out vars
885 // so exiting code gen knows to look for the value, but also put
886 // it in the set of dynamic vars the exiter must track!
887 exiter.addDynamicOutVar(outVar);
888 addDynamicVar(exiter, fm, outVar);
890 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
891 exiter.addStaticOutVar(outVar);
892 VariableSourceToken vst = vstIfStatic.vst;
893 exiter.putStaticOutVar2src(outVar, vst);
894 exiter.addStaticOutVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
897 assert srcType.equals(VarSrcTokTable.SrcType_READY);
898 exiter.addReadyOutVar(outVar);
904 case FKind.FlatOpNode: {
905 FlatOpNode fon = (FlatOpNode) fn;
907 if (fon.getOp().getOp() == Operation.ASSIGN) {
908 TempDescriptor lhs = fon.getDest();
909 TempDescriptor rhs = fon.getLeft();
911 // if this is an op node, don't stall, copy
912 // source and delay until we need to use value
914 // ask whether lhs and rhs sources are dynamic, static, etc.
915 VSTWrapper vstIfStatic = new VSTWrapper();
916 Integer lhsSrcType = vstTableIn.getRefVarSrcType(lhs, currentSESE, vstIfStatic);
917 Integer rhsSrcType = vstTableIn.getRefVarSrcType(rhs, currentSESE, vstIfStatic);
919 if (rhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
920 // if rhs is dynamic going in, lhs will definitely be dynamic
921 // going out of this node, so track that here
922 plan.addDynAssign(lhs, rhs);
923 addDynamicVar(currentSESE, fm, lhs);
924 addDynamicVar(currentSESE, fm, rhs);
926 } else if (lhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
927 // otherwise, if the lhs is dynamic, but the rhs is not, we
928 // need to update the variable's dynamic source as "current SESE"
929 plan.addDynAssign(lhs);
932 // only break if this is an ASSIGN op node,
933 // otherwise fall through to default case
938 // note that FlatOpNode's that aren't ASSIGN
939 // fall through to this default case
942 // a node with no live set has nothing to stall for
943 // note: no reason to check here, remove this....
944 // if (liveSetIn == null) {
948 TempDescriptor[] readarray = fn.readsTemps();
949 for (int i = 0; i < readarray.length; i++) {
950 TempDescriptor readtmp = readarray[i];
952 // ignore temps that are definitely available
953 // when considering to stall on it
954 if (!notAvailSetIn.contains(readtmp)) {
958 // check the source type of this variable
959 VSTWrapper vstIfStatic = new VSTWrapper();
960 Integer srcType = vstTableIn.getRefVarSrcType(readtmp, currentSESE, vstIfStatic);
962 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
963 // 1) It is not clear statically where this variable will
964 // come from, so dynamically we must keep track
965 // along various control paths, and therefore when we stall,
966 // just stall for the exact thing we need and move on
967 plan.addDynamicStall(readtmp);
968 addDynamicVar(currentSESE, fm, readtmp);
970 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
971 // 2) Single token/age pair: Stall for token/age pair, and copy
972 // all live variables with same token/age pair at the same
973 // time. This is the same stuff that the notavaialable analysis
974 // marks as now available.
975 VariableSourceToken vst = vstIfStatic.vst;
977 Iterator<VariableSourceToken> availItr =
978 vstTableIn.get(vst.getSESE(), vst.getAge()).iterator();
980 while (availItr.hasNext()) {
981 VariableSourceToken vstAlsoAvail = availItr.next();
983 // only grab additional stuff that is live
984 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
986 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
988 while (refVarItr.hasNext()) {
989 TempDescriptor refVar = refVarItr.next();
990 // note: this should just use normal liveness in...only want to
991 // copy live variables...
992 if (liveness.getLiveInTemps(fm, fn).contains(refVar)) {
997 if (!copySet.isEmpty()) {
998 plan.addStall2CopySet(vstAlsoAvail, copySet);
1003 // the other case for srcs is READY, so do nothing
1006 // assert that everything being stalled for is in the
1007 // "not available" set coming into this flat node and
1008 // that every VST identified is in the possible "stall set"
1009 // that represents VST's from children SESE's
1017 // identify sese-age pairs that are statically useful
1018 // and should have an associated SESE variable in code
1019 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
1020 // AND ALWAYS GIVE NAMES TO LOCAL PARENTS
1021 Set<VariableSourceToken> staticSet = vstTableIn.get();
1022 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
1023 while (vstItr.hasNext()) {
1024 VariableSourceToken vst = vstItr.next();
1026 // the caller proxy generates useful analysis facts, but we
1027 // never need to generate another name for it in code (it is
1028 // ALWAYS the task executing the local method context)
1029 if (vst.getSESE().getIsCallerProxySESE()) {
1033 SESEandAgePair sap = new SESEandAgePair(vst.getSESE(), vst.getAge());
1034 sap.getSESE().mustTrackAtLeastAge(sap.getAge());
1036 FlatSESEEnterNode sese = currentSESE;
1037 while (sese != null) {
1038 addNeededStaticName(sese, fm, sap);
1039 sese = sese.getLocalParent();
1043 codePlans.put(fn, plan);
1045 // if any variables at this-node-*dot* have a static source (exactly one
1047 // but go to a dynamic source at next-node-*dot*, create a new IR graph
1048 // node on that edge to track the sources dynamically
1049 // NOTE: for this calculation use the currentSESE variable, except when the
1050 // FlatNode fn is an Exit--in that case currentSESE is for the exiting task,
1051 // be we want to consider that the parent is tracking a variable coming out
1052 // of the exiting task
1053 FlatSESEEnterNode fsenDoingTracking;
1054 if (fn instanceof FlatSESEExitNode) {
1055 fsenDoingTracking = currentSESE.getLocalParent();
1057 if (fsenDoingTracking == null) {
1058 // if there is no local parent, there are one of two cases
1059 // 1) the current task is main, in which case this FlatNode
1060 // is the main's exit, and doesn't need to do any of the
1061 // following dynamic tracking
1062 // 2) the current task is defined in a method, so use the
1063 // caller proxy in the variable source calcs below
1064 if (currentSESE.equals(rblockRel.getMainSESE())) {
1067 fsenDoingTracking = rblockRel.getCallerProxySESE();
1071 fsenDoingTracking = currentSESE;
1074 VarSrcTokTable thisVstTable = variableResults.get(fn);
1075 for (int i = 0; i < fn.numNext(); i++) {
1076 FlatNode nn = fn.getNext(i);
1077 VarSrcTokTable nextVstTable = variableResults.get(nn);
1078 // note: using the result of liveness analysis regardless of task
1080 Set<TempDescriptor> nextLiveIn = liveness.getLiveInTemps(fm, nn);
1082 // the table can be null if it is one of the few IR nodes
1083 // completely outside of the root SESE scope
1084 if (nextVstTable != null && nextLiveIn != null) {
1086 Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
1087 thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, fsenDoingTracking);
1089 if (!readyOrStatic2dynamicSet.isEmpty()) {
1091 // either add these results to partial fixed-point result
1092 // or make a new one if we haven't made any here yet
1093 FlatEdge fe = new FlatEdge(fn, nn);
1094 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe);
1096 if (fwdvn == null) {
1098 new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, fsenDoingTracking);
1099 wdvNodesToSpliceIn.put(fe, fwdvn);
1101 fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet);
1108 private void addDynamicVar(FlatSESEEnterNode fsen, FlatMethod fm, TempDescriptor var) {
1111 // note: dynamic variable declarations are always located in the flat method
1112 // that encloses task block
1113 // there is no need to set fnContext to fsen
1114 if (fsen.getIsCallerProxySESE()) {
1115 // attach the dynamic variable to track to
1116 // the flat method, so it can be declared at entry
1119 // otherwise the code context is a task body
1124 ContextTaskNames ctn = fn2contextTaskNames.get(fnContext);
1126 ctn = new ContextTaskNames();
1129 ctn.addDynamicVar(var);
1130 fn2contextTaskNames.put(fnContext, ctn);
1134 private void addNeededStaticName(FlatSESEEnterNode fsen, FlatMethod fm, SESEandAgePair sap) {
1137 if (fsen.getIsCallerProxySESE()) {
1138 // attach the dynamic variable to track to
1139 // the flat method, so it can be declared at entry
1142 // otherwise the code context is a task body
1146 ContextTaskNames ctn = fn2contextTaskNames.get(fnContext);
1148 ctn = new ContextTaskNames();
1151 ctn.addNeededStaticName(sap);
1153 fn2contextTaskNames.put(fnContext, ctn);
1156 private void startConflictGraphs() {
1158 // first, for each task, consider whether it has any children, and if
1159 // effects analysis says they should be a conflict node in the that
1160 // parent's conflict graph
1161 Set<FlatSESEEnterNode> allSESEs = rblockRel.getAllSESEs();
1162 for (Iterator iterator = allSESEs.iterator(); iterator.hasNext(); ) {
1164 FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
1165 if (parent.getIsLeafSESE()) {
1169 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1170 ConflictGraph conflictGraph = sese2conflictGraph.get(parent);
1171 assert conflictGraph == null;
1172 conflictGraph = new ConflictGraph(state);
1174 Set<FlatSESEEnterNode> children = parent.getChildren();
1175 for (Iterator iterator2 = children.iterator(); iterator2.hasNext(); ) {
1176 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
1177 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(child);
1178 conflictGraph.addLiveIn(taint2Effects);
1181 sese2conflictGraph.put(parent, conflictGraph);
1184 // then traverse all methods looking for potential stall sites, and
1185 // add those stall sites as nodes in any task's conflict graph that
1186 // might be executing at the point of the stall site
1187 Iterator<MethodDescriptor> descItr = descriptorsToAnalyze.iterator();
1188 while (descItr.hasNext()) {
1189 MethodDescriptor md = descItr.next();
1190 FlatMethod fm = state.getMethodFlat(md);
1192 addStallSitesToConflictGraphs(fm);
1197 private void addStallSitesToConflictGraphs(FlatMethod fm) {
1199 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1200 flatNodesToVisit.add(fm);
1202 Set<FlatNode> visited = new HashSet<FlatNode>();
1204 while (!flatNodesToVisit.isEmpty()) {
1205 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1206 flatNodesToVisit.remove(fn);
1209 Set<FlatSESEEnterNode> currentSESEs = rblockRel.getPossibleExecutingRBlocks(fn);
1211 conflictGraph_nodeAction(fn, currentSESEs, fm.getMethod().getClassDesc());
1213 // schedule forward nodes for analysis
1214 for (int i = 0; i < fn.numNext(); i++) {
1215 FlatNode nn = fn.getNext(i);
1216 if (!visited.contains(nn)) {
1217 flatNodesToVisit.add(nn);
1223 private void conflictGraph_nodeAction(FlatNode fn, Set<FlatSESEEnterNode> currentSESEs,
1224 ClassDescriptor cd) {
1226 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1228 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1230 // repeat the process of adding a stall site to a conflict graph
1231 // for each task that might be executing at a possible stall site
1232 Iterator<FlatSESEEnterNode> seseItr = currentSESEs.iterator();
1233 while (seseItr.hasNext()) {
1234 FlatSESEEnterNode currentSESE = seseItr.next();
1236 ConflictGraph conflictGraph = sese2conflictGraph.get(currentSESE);
1237 if (conflictGraph == null) {
1238 assert currentSESE.getIsLeafSESE();
1245 switch (fn.kind()) {
1247 case FKind.FlatFieldNode:
1248 case FKind.FlatElementNode: {
1250 if (fn instanceof FlatFieldNode) {
1251 FlatFieldNode ffn = (FlatFieldNode) fn;
1254 FlatElementNode fen = (FlatElementNode) fn;
1258 conflictGraph.addStallSite(taint2Effects, rhs, cd);
1262 case FKind.FlatSetFieldNode:
1263 case FKind.FlatSetElementNode: {
1265 if (fn instanceof FlatSetFieldNode) {
1266 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1267 lhs = fsfn.getDst();
1268 rhs = fsfn.getSrc();
1270 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1271 lhs = fsen.getDst();
1272 rhs = fsen.getSrc();
1275 conflictGraph.addStallSite(taint2Effects, rhs, cd);
1276 conflictGraph.addStallSite(taint2Effects, lhs, cd);
1280 case FKind.FlatCall: {
1281 FlatCall fc = (FlatCall) fn;
1284 conflictGraph.addStallSite(taint2Effects, lhs, cd);
1290 if (conflictGraph.id2cn.size() > 0) {
1291 sese2conflictGraph.put(currentSESE, conflictGraph);
1296 private void calculateConflicts(Set<FlatNew> sitesToFlag, boolean useReachInfo) {
1298 // decide fine-grain edge or coarse-grain edge among all vertexes by
1299 // pair-wise comparison
1300 Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
1301 while (seseIter.hasNext()) {
1302 FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next();
1303 ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
1306 // clear current conflict before recalculating with reachability info
1307 conflictGraph.clearAllConflictEdge();
1308 conflictGraph.setDisJointAnalysis(disjointAnalysisReach);
1309 conflictGraph.setFMEnclosing(sese.getfmEnclosing());
1311 conflictGraph.analyzeConflicts(sitesToFlag, useReachInfo);
1312 sese2conflictGraph.put(sese, conflictGraph);
1316 private void writeConflictGraph() {
1317 Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
1318 while (keyEnum.hasMoreElements()) {
1319 FlatNode key = (FlatNode) keyEnum.nextElement();
1320 ConflictGraph cg = sese2conflictGraph.get(key);
1322 if (cg.hasConflictEdge()) {
1323 cg.writeGraph("ConflictGraphFor" + key, false);
1325 } catch (IOException e) {
1326 System.out.println("Error writing");
1332 // the traversal for pruning state machines and finding
1333 // machines that are weakly connected BOTH consider conflicting
1334 // effects between heap roots, so it is smart to compute all of
1336 public void pruneMachinesAndFindWeaklyConnectedExaminers() {
1337 ProcessStateMachines psm = new ProcessStateMachines(buildStateMachines, rblockRel);
1339 buildStateMachines.writeStateMachines("pruned");
1342 private void synthesizeLocks() {
1343 // for every conflict graph, generate a set of memory queues
1344 // (called SESELock in this code!) to cover the graph
1345 Set<Map.Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
1346 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext(); ) {
1347 Map.Entry<FlatNode, ConflictGraph> graphEntry =
1348 (Map.Entry<FlatNode, ConflictGraph>)iterator.next();
1349 FlatNode sese = graphEntry.getKey();
1350 ConflictGraph conflictGraph = graphEntry.getValue();
1351 calculateCovering(conflictGraph);
1355 private void calculateCovering(ConflictGraph conflictGraph) {
1356 uniqueLockSetId = 0; // reset lock counter for every new conflict graph
1357 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1358 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1359 HashSet<SESELock> lockSet = new HashSet<SESELock>();
1361 Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1362 for (Iterator iterator = tempCover.iterator(); iterator.hasNext(); ) {
1363 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1364 if (conflictEdge.isCoarseEdge()) {
1365 coarseToCover.add(conflictEdge);
1367 fineToCover.add(conflictEdge);
1371 HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
1372 toCover.addAll(fineToCover);
1373 toCover.addAll(coarseToCover);
1375 while (!toCover.isEmpty()) {
1377 SESELock seseLock = new SESELock();
1378 seseLock.setID(uniqueLockSetId++);
1382 do { // fine-grained edge
1386 for (Iterator iterator = fineToCover.iterator(); iterator.hasNext(); ) {
1389 ConflictEdge edge = (ConflictEdge) iterator.next();
1390 if (seseLock.getConflictNodeSet().size() == 0) {
1392 if (seseLock.isWriteNode(edge.getVertexU())) {
1393 // mark as fine_write
1394 if (edge.getVertexU().isStallSiteNode()) {
1395 type = ConflictNode.PARENT_WRITE;
1397 type = ConflictNode.FINE_WRITE;
1399 seseLock.addConflictNode(edge.getVertexU(), type);
1401 // mark as fine_read
1402 if (edge.getVertexU().isStallSiteNode()) {
1403 type = ConflictNode.PARENT_READ;
1405 type = ConflictNode.FINE_READ;
1407 seseLock.addConflictNode(edge.getVertexU(), type);
1409 if (edge.getVertexV() != edge.getVertexU()) {
1410 if (seseLock.isWriteNode(edge.getVertexV())) {
1411 // mark as fine_write
1412 if (edge.getVertexV().isStallSiteNode()) {
1413 type = ConflictNode.PARENT_WRITE;
1415 type = ConflictNode.FINE_WRITE;
1417 seseLock.addConflictNode(edge.getVertexV(), type);
1419 // mark as fine_read
1420 if (edge.getVertexV().isStallSiteNode()) {
1421 type = ConflictNode.PARENT_READ;
1423 type = ConflictNode.FINE_READ;
1425 seseLock.addConflictNode(edge.getVertexV(), type);
1429 seseLock.addConflictEdge(edge);
1430 fineToCover.remove(edge);
1431 break; // exit iterator loop
1432 } // end of initial setup
1434 ConflictNode newNode;
1435 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1436 // new node has a fine-grained edge to all current node
1437 // If there is a coarse grained edge where need a fine edge, it's
1438 // okay to add the node
1439 // but the edge must remain uncovered.
1443 if (seseLock.containsConflictNode(newNode)) {
1444 seseLock.addEdge(edge);
1445 fineToCover.remove(edge);
1449 if (seseLock.isWriteNode(newNode)) {
1450 if (newNode.isStallSiteNode()) {
1451 type = ConflictNode.PARENT_WRITE;
1453 type = ConflictNode.FINE_WRITE;
1455 seseLock.setNodeType(newNode, type);
1457 if (newNode.isStallSiteNode()) {
1458 type = ConflictNode.PARENT_READ;
1460 type = ConflictNode.FINE_READ;
1462 seseLock.setNodeType(newNode, type);
1465 seseLock.addEdge(edge);
1466 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1467 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext(); ) {
1468 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1470 // mark all fine edges between new node and nodes in the group as
1472 if (!conflictEdge.getVertexU().equals(newNode)) {
1473 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1475 seseLock.addConflictEdge(conflictEdge);
1476 fineToCover.remove(conflictEdge);
1478 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1479 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1481 seseLock.addConflictEdge(conflictEdge);
1482 fineToCover.remove(conflictEdge);
1488 break; // exit iterator loop
1493 HashSet<ConflictEdge> notCovered = new HashSet<ConflictEdge>();
1497 for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext(); ) {
1499 ConflictEdge edge = (ConflictEdge) iterator.next();
1500 if (seseLock.getConflictNodeSet().size() == 0) {
1502 if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
1503 // node has a coarse-grained edge with itself
1504 if (!(edge.getVertexU().isStallSiteNode())) {
1505 // and it is not parent
1506 type = ConflictNode.SCC;
1509 type = ConflictNode.PARENT_COARSE;
1511 type = ConflictNode.PARENT_WRITE;
1514 seseLock.addConflictNode(edge.getVertexU(), type);
1516 if (edge.getVertexU().isStallSiteNode()) {
1518 type = ConflictNode.PARENT_COARSE;
1520 if (edge.getVertexU().getWriteEffectSet().isEmpty()) {
1521 type = ConflictNode.PARENT_READ;
1523 type = ConflictNode.PARENT_WRITE;
1527 type = ConflictNode.COARSE;
1529 seseLock.addConflictNode(edge.getVertexU(), type);
1531 if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
1532 // node has a coarse-grained edge with itself
1533 if (!(edge.getVertexV().isStallSiteNode())) {
1534 // and it is not parent
1535 type = ConflictNode.SCC;
1538 type = ConflictNode.PARENT_COARSE;
1540 type = ConflictNode.PARENT_WRITE;
1543 seseLock.addConflictNode(edge.getVertexV(), type);
1545 if (edge.getVertexV().isStallSiteNode()) {
1547 type = ConflictNode.PARENT_COARSE;
1549 if (edge.getVertexV().getWriteEffectSet().isEmpty()) {
1550 type = ConflictNode.PARENT_READ;
1552 type = ConflictNode.PARENT_WRITE;
1556 type = ConflictNode.COARSE;
1558 seseLock.addConflictNode(edge.getVertexV(), type);
1561 coarseToCover.remove(edge);
1562 seseLock.addConflictEdge(edge);
1563 break; // exit iterator loop
1564 } // end of initial setup
1566 ConflictNode newNode;
1567 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1568 // new node has a coarse-grained edge to all fine-read, fine-write,
1572 if (newNode.isInVarNode() && (!seseLock.hasSelfCoarseEdge(newNode))
1573 && seseLock.hasCoarseEdgeWithParentCoarse(newNode)) {
1574 // this case can't be covered by this queue
1575 coarseToCover.remove(edge);
1576 notCovered.add(edge);
1580 if (seseLock.containsConflictNode(newNode)) {
1581 seseLock.addEdge(edge);
1582 coarseToCover.remove(edge);
1586 if (seseLock.hasSelfCoarseEdge(newNode)) {
1588 if (newNode.isStallSiteNode()) {
1589 type = ConflictNode.PARENT_COARSE;
1591 type = ConflictNode.SCC;
1593 seseLock.setNodeType(newNode, type);
1595 if (newNode.isStallSiteNode()) {
1596 type = ConflictNode.PARENT_COARSE;
1598 type = ConflictNode.COARSE;
1600 seseLock.setNodeType(newNode, type);
1603 seseLock.addEdge(edge);
1604 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1605 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext(); ) {
1606 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1607 // mark all coarse edges between new node and nodes in the group
1609 if (!conflictEdge.getVertexU().equals(newNode)) {
1610 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1612 seseLock.addConflictEdge(conflictEdge);
1613 coarseToCover.remove(conflictEdge);
1615 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1616 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1618 seseLock.addConflictEdge(conflictEdge);
1619 coarseToCover.remove(conflictEdge);
1624 break; // exit iterator loop
1630 lockSet.add(seseLock);
1633 coarseToCover.addAll(notCovered);
1634 toCover.addAll(fineToCover);
1635 toCover.addAll(coarseToCover);
1639 conflictGraph2SESELock.put(conflictGraph, lockSet);
1642 public ConflictGraph getConflictGraph(FlatNode sese) {
1643 return sese2conflictGraph.get(sese);
1646 public Set<SESELock> getLockMappings(ConflictGraph graph) {
1647 return conflictGraph2SESELock.get(graph);
1650 public Set<FlatSESEEnterNode> getAllSESEs() {
1651 return rblockRel.getAllSESEs();
1654 public FlatSESEEnterNode getMainSESE() {
1655 return rblockRel.getMainSESE();
1658 public FlatSESEEnterNode getCallerProxySESE() {
1659 return rblockRel.getCallerProxySESE();
1662 public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks(FlatNode fn) {
1663 return rblockRel.getPossibleExecutingRBlocks(fn);
1666 public void writeReports(String timeReport) throws java.io.IOException {
1668 BufferedWriter bw = new BufferedWriter(new FileWriter("ooojReport_summary.txt"));
1669 bw.write("OoOJava Analysis Results\n\n");
1670 bw.write(timeReport + "\n\n");
1671 printSESEHierarchy(bw);
1676 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
1677 while (methItr.hasNext()) {
1678 MethodDescriptor md = methItr.next();
1679 FlatMethod fm = state.getMethodFlat(md);
1682 new BufferedWriter(new FileWriter("ooojReport_" + md.getClassMethodName()
1683 + md.getSafeMethodDescriptor() + ".txt"));
1684 bw.write("OoOJava Results for " + md + "\n-------------------\n");
1686 bw.write("Dynamic vars to manage:\n " + getContextTaskNames(fm).getDynamicVarSet());
1688 bw.write("\n\nLive-In, Root View\n------------------\n"
1689 + fm.printMethod(livenessGlobalView));
1690 bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults));
1691 bw.write("\n\nNot Available Results-Out\n---------------------\n"
1692 + fm.printMethod(notAvailableResults));
1693 bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans));
1699 private void printSESEHierarchy(BufferedWriter bw) throws java.io.IOException {
1700 bw.write("SESE Local Hierarchy\n--------------\n");
1701 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getLocalRootSESEs().iterator();
1702 while (rootItr.hasNext()) {
1703 FlatSESEEnterNode root = rootItr.next();
1704 printSESEHierarchyTree(bw, root, 0);
1708 private void printSESEHierarchyTree(BufferedWriter bw, FlatSESEEnterNode fsen, int depth)
1709 throws java.io.IOException {
1710 for (int i = 0; i < depth; ++i) {
1713 bw.write("- " + fsen.getPrettyIdentifier() + "\n");
1715 Iterator<FlatSESEEnterNode> childItr = fsen.getLocalChildren().iterator();
1716 while (childItr.hasNext()) {
1717 FlatSESEEnterNode fsenChild = childItr.next();
1718 printSESEHierarchyTree(bw, fsenChild, depth + 1);
1722 private void printSESEInfo(BufferedWriter bw) throws java.io.IOException {
1723 bw.write("\nSESE info\n-------------\n");
1724 Iterator<FlatSESEEnterNode> fsenItr = rblockRel.getAllSESEs().iterator();
1725 while (fsenItr.hasNext()) {
1726 FlatSESEEnterNode fsen = fsenItr.next();
1728 bw.write("SESE " + fsen.getPrettyIdentifier());
1729 if (fsen.getIsLeafSESE()) {
1730 bw.write(" (leaf)");
1734 bw.write(" in-set: " + fsen.getInVarSet() + "\n");
1735 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1736 while (tItr.hasNext()) {
1737 TempDescriptor inVar = tItr.next();
1738 if (fsen.getReadyInVarSet().contains(inVar)) {
1739 bw.write(" (ready) " + inVar + "\n");
1741 if (fsen.getStaticInVarSet().contains(inVar)) {
1742 bw.write(" (static) " + inVar + " from " + fsen.getStaticInVarSrc(inVar) + "\n");
1744 if (fsen.getDynamicInVarSet().contains(inVar)) {
1745 bw.write(" (dynamic)" + inVar + "\n");
1749 bw.write(" Dynamic vars to manage: " + getContextTaskNames(fsen).getDynamicVarSet() + "\n");
1751 bw.write(" out-set: " + fsen.getOutVarSet() + "\n");
1752 tItr = fsen.getOutVarSet().iterator();
1753 while (tItr.hasNext()) {
1754 TempDescriptor outVar = tItr.next();
1755 if (fsen.getReadyOutVarSet().contains(outVar)) {
1756 bw.write(" (ready) " + outVar + "\n");
1758 if (fsen.getStaticOutVarSet().contains(outVar)) {
1759 bw.write(" (static) " + outVar + " from " + fsen.getStaticOutVarSrc(outVar) + "\n");
1761 if (fsen.getDynamicOutVarSet().contains(outVar)) {
1762 bw.write(" (dynamic)" + outVar + "\n");
1766 bw.write(" local parent: " + fsen.getLocalParent() + "\n");
1767 bw.write(" local children: " + fsen.getLocalChildren() + "\n");
1769 bw.write(" possible parents: " + fsen.getParents() + "\n");
1770 bw.write(" possible children: " + fsen.getChildren() + "\n");