1 package Analysis.OoOJava;
7 import Analysis.CallGraph.*;
8 import Analysis.Disjoint.*;
9 import Analysis.Pointer.*;
13 public class OoOJavaAnalysis {
15 // data from the compiler
17 private TypeUtil typeUtil;
18 private CallGraph callGraph;
19 private Liveness liveness;
20 private RBlockRelationAnalysis rblockRel;
21 private HeapAnalysis disjointAnalysisTaints;
22 private DisjointAnalysis disjointAnalysisReach;
23 private BuildStateMachines buildStateMachines;
25 private Set<MethodDescriptor> descriptorsToAnalyze;
27 private Hashtable<FlatNode, Set<TempDescriptor>> livenessGlobalView;
28 private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
29 private Hashtable<FlatNode, VarSrcTokTable> variableResults;
30 private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
31 private Hashtable<FlatNode, CodePlan> codePlans;
33 private Hashtable<FlatSESEEnterNode, Set<TempDescriptor>> notAvailableIntoSESE;
35 private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
37 private Hashtable<FlatNode, ContextTaskNames> fn2contextTaskNames;
39 // get the flat method that contains any given flat node
40 private Hashtable<FlatNode, FlatMethod> fn2fm;
42 // temporal data structures to track analysis progress.
43 static private int uniqueLockSetId = 0;
44 // mapping of a conflict graph to its compiled lock
45 private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraph2SESELock;
46 // mapping of a sese block to its conflict graph
47 private Hashtable<FlatNode, ConflictGraph> sese2conflictGraph;
49 public static int maxSESEage = -1;
51 public int getMaxSESEage() {
56 public CodePlan getCodePlan(FlatNode fn) {
57 CodePlan cp = codePlans.get(fn);
61 public Set<FlatNode> getNodesWithPlans() {
62 return codePlans.keySet();
65 public ContextTaskNames getContextTaskNames(FlatMethod fm) {
66 ContextTaskNames out = fn2contextTaskNames.get(fm);
68 out = new ContextTaskNames();
73 public ContextTaskNames getContextTaskNames(FlatSESEEnterNode fsen) {
74 ContextTaskNames out = fn2contextTaskNames.get(fsen);
76 out = new ContextTaskNames();
81 public FlatMethod getContainingFlatMethod(FlatNode fn) {
82 FlatMethod fm = fn2fm.get(fn);
87 public HeapAnalysis getDisjointAnalysis() {
88 return disjointAnalysisTaints;
91 public BuildStateMachines getBuildStateMachines() {
92 return buildStateMachines;
95 public OoOJavaAnalysis(State state, TypeUtil typeUtil, CallGraph callGraph, Liveness liveness,
96 ArrayReferencees arrayReferencees) {
98 State.logEvent("Starting OoOJavaAnalysis");
100 this.typeUtil = typeUtil;
101 this.callGraph = callGraph;
102 this.liveness = liveness;
103 this.maxSESEage = state.OOO_MAXSESEAGE;
105 livenessGlobalView = new Hashtable<FlatNode, Set<TempDescriptor>>();
106 livenessVirtualReads = new Hashtable<FlatNode, Set<TempDescriptor>>();
107 variableResults = new Hashtable<FlatNode, VarSrcTokTable>();
108 notAvailableResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
109 codePlans = new Hashtable<FlatNode, CodePlan>();
110 wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
111 notAvailableIntoSESE = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
112 sese2conflictGraph = new Hashtable<FlatNode, ConflictGraph>();
113 conflictGraph2SESELock = new Hashtable<ConflictGraph, HashSet<SESELock>>();
114 fn2contextTaskNames = new Hashtable<FlatNode, ContextTaskNames>();
115 fn2fm = new Hashtable<FlatNode, FlatMethod>();
117 // state machines support heap examiners with
118 // state transitions to improve precision
120 buildStateMachines = new BuildStateMachines();
123 // add all methods transitively reachable from the
124 // source's main to set for analysis
125 MethodDescriptor mdSourceEntry = typeUtil.getMain();
126 FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
128 descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
130 descriptorsToAnalyze.add(mdSourceEntry);
132 // 0th pass, setup a useful mapping of any flat node to the
133 // flat method it is a part of
134 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
135 while (methItr.hasNext()) {
136 Descriptor d = methItr.next();
137 FlatMethod fm = state.getMethodFlat(d);
138 buildFlatNodeToFlatMethod(fm);
140 State.logEvent("OoOJavaAnalysis Oth pass completed");
142 // 1st pass, find basic rblock relations & potential stall sites
143 rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
144 VarSrcTokTable.rblockRel = rblockRel;
146 State.logEvent("OoOJavaAnalysis 1st pass completed");
148 // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
149 Iterator<FlatSESEEnterNode> seseItr = rblockRel.getLocalRootSESEs().iterator();
150 while (seseItr.hasNext()) {
151 FlatSESEEnterNode sese = seseItr.next();
152 livenessAnalysisBackward(sese);
155 State.logEvent("OoOJavaAnalysis 2nd pass completed");
157 // 3rd pass, variable analysis
158 methItr = rblockRel.getMethodsWithSESEs().iterator();
159 while (methItr.hasNext()) {
160 Descriptor d = methItr.next();
161 FlatMethod fm = state.getMethodFlat(d);
162 // starting from roots do a forward, fixed-point
163 // variable analysis for refinement and stalls
164 variableAnalysisForward(fm);
167 State.logEvent("OoOJavaAnalysis 3rd pass completed");
169 // 4th pass, compute liveness contribution from
170 // virtual reads discovered in variable pass
171 seseItr = rblockRel.getLocalRootSESEs().iterator();
172 while (seseItr.hasNext()) {
173 FlatSESEEnterNode sese = seseItr.next();
174 livenessAnalysisBackward(sese);
177 State.logEvent("OoOJavaAnalysis 4th pass completed");
179 // 5th pass, use disjointness with NO FLAGGED REGIONS
180 // to compute taints and effects
182 disjointAnalysisTaints =
183 new Pointer(state, typeUtil, callGraph, rblockRel, liveness, buildStateMachines);
184 ((Pointer) disjointAnalysisTaints).doAnalysis();
186 disjointAnalysisTaints =
187 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null,
188 rblockRel, buildStateMachines, true); // suppress output--this is
189 // an intermediate pass
191 State.logEvent("OoOJavaAnalysis 5th pass completed");
193 // 6th pass, not available analysis FOR VARIABLES!
194 methItr = rblockRel.getMethodsWithSESEs().iterator();
195 while (methItr.hasNext()) {
196 Descriptor d = methItr.next();
197 FlatMethod fm = state.getMethodFlat(d);
198 // compute what is not available at every program
199 // point, in a forward fixed-point pass
200 notAvailableForward(fm);
202 State.logEvent("OoOJavaAnalysis 6th pass completed");
203 // 7th pass, start conflict graphs where a parent's graph has a
204 // node for possibly conflicting children and its own stall sites
205 startConflictGraphs();
206 State.logEvent("OoOJavaAnalysis 7th pass completed");
207 // 8th pass, calculate all possible conflicts without using
208 // reachability info and identify set of FlatNew that next
209 // disjoint reach. analysis should flag
210 Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
211 calculateConflicts(sitesToFlag, false);
212 State.logEvent("OoOJavaAnalysis 8th pass completed");
214 // 9th pass, ask disjoint analysis to compute reachability
215 // for objects that may cause heap conflicts so the most
216 // efficient method to deal with conflict can be computed
218 disjointAnalysisReach =
219 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, sitesToFlag,
220 null, // don't do effects analysis again!
221 null, // no BuildStateMachines needed
222 !state.OOODEBUG // only print out in OoOJava debug mode
224 State.logEvent("OoOJavaAnalysis 9th pass completed");
225 // 10th pass, calculate conflicts with reachability info
226 calculateConflicts(null, true);
227 State.logEvent("OoOJavaAnalysis 10th pass completed");
229 // in RCR/DFJ we want to do some extra processing on the
230 // state machines before they get handed off to code gen,
231 // and we're doing the same effect-conflict traversal needed
232 // to identify heap examiners that are weakly connected, so
233 // accomplish both at the same time
234 pruneMachinesAndFindWeaklyConnectedExaminers();
235 State.logEvent("OoOJavaAnalysis RCR pruneMachines pass completed");
238 // 11th pass, compiling memory Qs! The name "lock" is a legacy
239 // term for the heap dependence queue, or memQ as the runtime calls it
241 State.logEvent("OoOJavaAnalysis 11th pass completed");
243 // 12th pass, compute a plan for code injections
244 methItr = descriptorsToAnalyze.iterator();
245 while (methItr.hasNext()) {
246 Descriptor d = methItr.next();
247 FlatMethod fm = state.getMethodFlat(d);
248 codePlansForward(fm);
251 State.logEvent("OoOJavaAnalysis 12th pass completed");
253 // splice new IR nodes into graph after all
254 // analysis passes are complete
255 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
256 while (spliceItr.hasNext()) {
257 Map.Entry me = (Map.Entry)spliceItr.next();
258 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
259 fwdvn.spliceIntoIR();
261 State.logEvent("OoOJavaAnalysis 13th pass completed");
263 if (state.OOODEBUG) {
266 disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt");
267 writeConflictGraph();
268 } catch (IOException e) {
271 State.logEvent("OoOJavaAnalysis completed");
274 private void buildFlatNodeToFlatMethod(FlatMethod fm) {
275 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
276 flatNodesToVisit.add(fm);
278 Set<FlatNode> flatNodesVisited = new HashSet<FlatNode>();
280 while (!flatNodesToVisit.isEmpty()) {
281 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
282 flatNodesToVisit.remove(fn);
283 flatNodesVisited.add(fn);
287 for (int i = 0; i < fn.numNext(); i++) {
288 FlatNode nn = fn.getNext(i);
289 if (!flatNodesVisited.contains(nn)) {
290 flatNodesToVisit.add(nn);
298 * Iterator iter = sese2conflictGraph.entrySet().iterator(); while
299 * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn = (FlatNode)
300 * e.getKey(); ConflictGraph conflictGraph = (ConflictGraph) e.getValue();
301 * System.out.println("---------------------------------------");
302 * System.out.println("CONFLICT GRAPH for " + fn); Set<String> keySet =
303 * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator();
304 * iterator.hasNext();) { String key = (String) iterator.next(); ConflictNode
305 * node = conflictGraph.id2cn.get(key); System.out.println("key=" + key +
306 * " \n" + node.toStringAllEffects()); } }
309 private void writeFile(Set<FlatNew> sitesToFlag) {
312 BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt"));
314 for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext(); ) {
315 FlatNew fn = (FlatNew) iterator.next();
319 } catch (IOException e) {
325 private void livenessAnalysisBackward(FlatSESEEnterNode fsen) {
327 // flow backward across nodes to compute liveness, and
328 // take special care with sese enter/exit nodes that
329 // alter this from normal liveness analysis
330 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
331 // flatNodesToVisit.add( fm.getFlatExit() );
332 flatNodesToVisit.add(fsen.getFlatExit());
334 while (!flatNodesToVisit.isEmpty()) {
335 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
336 flatNodesToVisit.remove(fn);
338 Set<TempDescriptor> prev = livenessGlobalView.get(fn);
340 // merge sets from control flow joins
341 Set<TempDescriptor> livein = new HashSet<TempDescriptor>();
342 for (int i = 0; i < fn.numNext(); i++) {
343 FlatNode nn = fn.getNext(i);
344 Set<TempDescriptor> s = livenessGlobalView.get(nn);
350 Set<TempDescriptor> curr = liveness_nodeActions(fn, livein);
352 // if a new result, schedule backward nodes for analysis
353 if (!curr.equals(prev)) {
356 livenessGlobalView.put(fn, curr);
357 for (int i = 0; i < fn.numPrev(); i++) {
358 FlatNode nn = fn.getPrev(i);
359 flatNodesToVisit.add(nn);
366 private Set<TempDescriptor> liveness_nodeActions(FlatNode fn, Set<TempDescriptor> liveIn) {
369 case FKind.FlatSESEEnterNode: {
370 // add whatever is live-in at a task enter to that
372 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
373 if (liveIn != null) {
374 fsen.addInVarSet(liveIn);
376 // no break, should also execute default actions
380 // handle effects of statement in reverse, writes then reads
381 TempDescriptor[] writeTemps = fn.writesTemps();
382 for (int i = 0; i < writeTemps.length; ++i) {
383 liveIn.remove(writeTemps[i]);
385 // if we are analyzing code declared directly in a task,
386 FlatSESEEnterNode fsen = rblockRel.getLocalInnerRBlock(fn);
388 // check to see if we are writing to variables that will
389 // be live-out at the task's exit (and therefore should
390 // go in the task's out-var set)
391 FlatSESEExitNode fsexn = fsen.getFlatExit();
392 // note: liveness analysis can have corresponding decisions
393 Set<TempDescriptor> livetemps = liveness.getLiveInTemps(fsen.getfmEnclosing(), fsexn);
394 if (livetemps != null && livetemps.contains(writeTemps[i])) {
395 fsen.addOutVar(writeTemps[i]);
400 TempDescriptor[] readTemps = fn.readsTemps();
401 for (int i = 0; i < readTemps.length; ++i) {
402 liveIn.add(readTemps[i]);
405 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get(fn);
406 if (virtualReadTemps != null) {
407 liveIn.addAll(virtualReadTemps);
417 private void variableAnalysisForward(FlatMethod fm) {
419 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
420 flatNodesToVisit.add(fm);
422 while (!flatNodesToVisit.isEmpty()) {
423 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
424 flatNodesToVisit.remove(fn);
426 VarSrcTokTable prev = variableResults.get(fn);
428 // merge sets from control flow joins
429 VarSrcTokTable curr = new VarSrcTokTable();
430 for (int i = 0; i < fn.numPrev(); i++) {
431 FlatNode nn = fn.getPrev(i);
432 VarSrcTokTable incoming = variableResults.get(nn);
433 curr.merge(incoming);
436 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock(fn);
437 if (currentSESE == null) {
438 currentSESE = rblockRel.getCallerProxySESE();
441 variable_nodeActions(fn, curr, currentSESE);
443 // if a new result, schedule forward nodes for analysis
444 if (!curr.equals(prev)) {
445 variableResults.put(fn, curr);
447 for (int i = 0; i < fn.numNext(); i++) {
448 FlatNode nn = fn.getNext(i);
449 flatNodesToVisit.add(nn);
455 private void variable_nodeActions(FlatNode fn, VarSrcTokTable vstTable,
456 FlatSESEEnterNode currentSESE) {
459 case FKind.FlatSESEEnterNode: {
460 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
461 // ignore currently executing SESE, at this point
462 // the analysis considers a new instance is becoming
465 vstTable.assertConsistency();
469 case FKind.FlatSESEExitNode: {
470 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
472 // fsen is the child of currently executing tasks
473 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
475 // remap all of this child's children tokens to be
476 // from this child as the child exits
477 vstTable.remapChildTokens(fsen);
479 // liveness virtual reads are things that might be
480 // written by an SESE and should be added to the in-set
481 // anything virtually read by this SESE should be pruned
482 // of parent or sibling sources
483 Set<TempDescriptor> liveVars = liveness.getLiveInTemps(fsen.getfmEnclosing(), fn);
485 Set<TempDescriptor> fsenVirtReads =
486 vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen, liveVars);
488 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
489 if (fsenVirtReadsOld != null) {
490 fsenVirtReads.addAll(fsenVirtReadsOld);
492 livenessVirtualReads.put(fn, fsenVirtReads);
494 // virtual reads are forced in-vars!
495 fsen.addInVarSet(fsenVirtReads);
497 // then all child out-set tokens are guaranteed
498 // to be filled in, so clobber those entries with
499 // the latest, clean sources
500 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
501 while (outVarItr.hasNext()) {
502 TempDescriptor outVar = outVarItr.next();
503 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
505 VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
506 vstTable.remove(outVar);
509 vstTable.assertConsistency();
513 case FKind.FlatOpNode: {
514 FlatOpNode fon = (FlatOpNode) fn;
516 if (fon.getOp().getOp() == Operation.ASSIGN) {
517 TempDescriptor lhs = fon.getDest();
518 TempDescriptor rhs = fon.getLeft();
520 vstTable.remove(lhs);
522 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
524 Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
525 while (itr.hasNext()) {
526 VariableSourceToken vst = itr.next();
528 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
531 // when we do x = y for variables, just copy over from a child,
532 // there are two cases:
533 // 1. if the current task is the caller proxy, any local root is a
536 currentSESE.getIsCallerProxySESE()
537 && rblockRel.getLocalRootSESEs().contains(vst.getSESE());
539 // 2. if the child task is a locally-defined child of the current task
540 boolean case2 = currentSESE.getLocalChildren().contains(vst.getSESE());
542 if (case1 || case2) {
543 // if the source comes from a child, copy it over
544 forAddition.add(new VariableSourceToken(ts, vst.getSESE(), vst.getAge(), vst
547 // otherwise, stamp it as us as the source
548 forAddition.add(new VariableSourceToken(ts, currentSESE, new Integer(0), lhs));
552 vstTable.addAll(forAddition);
554 // only break if this is an ASSIGN op node,
555 // otherwise fall through to default case
556 vstTable.assertConsistency();
561 // note that FlatOpNode's that aren't ASSIGN
562 // fall through to this default case
564 TempDescriptor[] writeTemps = fn.writesTemps();
565 if (writeTemps.length > 0) {
567 // for now, when writeTemps > 1, make sure
568 // its a call node, programmer enforce only
569 // doing stuff like calling a print routine
570 if (writeTemps.length > 1) {
571 assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
575 vstTable.remove(writeTemps[0]);
577 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
578 ts.add(writeTemps[0]);
580 vstTable.add(new VariableSourceToken(ts, currentSESE, new Integer(0), writeTemps[0]));
583 vstTable.assertConsistency();
590 private void notAvailableForward(FlatMethod fm) {
592 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
593 flatNodesToVisit.add(fm);
595 while (!flatNodesToVisit.isEmpty()) {
596 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
597 flatNodesToVisit.remove(fn);
599 Set<TempDescriptor> prev = notAvailableResults.get(fn);
601 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
602 for (int i = 0; i < fn.numPrev(); i++) {
603 FlatNode nn = fn.getPrev(i);
604 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
605 if (notAvailIn != null) {
606 curr.addAll(notAvailIn);
610 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock(fn);
611 if (currentSESE == null) {
612 currentSESE = rblockRel.getCallerProxySESE();
615 notAvailable_nodeActions(fn, curr, currentSESE);
617 // if a new result, schedule forward nodes for analysis
618 if (!curr.equals(prev)) {
619 notAvailableResults.put(fn, curr);
621 for (int i = 0; i < fn.numNext(); i++) {
622 FlatNode nn = fn.getNext(i);
623 flatNodesToVisit.add(nn);
629 private void notAvailable_nodeActions(FlatNode fn, Set<TempDescriptor> notAvailSet,
630 FlatSESEEnterNode currentSESE) {
632 // any temps that are removed from the not available set
633 // at this node should be marked in this node's code plan
634 // as temps to be grabbed at runtime!
638 case FKind.FlatSESEEnterNode: {
639 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
641 // keep a copy of what's not available into the SESE
642 // and restore it at the matching exit node
643 Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
644 Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
645 while (tdItr.hasNext()) {
646 notAvailCopy.add(tdItr.next());
648 notAvailableIntoSESE.put(fsen, notAvailCopy);
654 case FKind.FlatSESEExitNode: {
655 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
656 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
658 notAvailSet.addAll(fsen.getOutVarSet());
660 Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
661 assert notAvailIn != null;
662 notAvailSet.addAll(notAvailIn);
666 case FKind.FlatMethod: {
671 case FKind.FlatOpNode: {
672 FlatOpNode fon = (FlatOpNode) fn;
674 if (fon.getOp().getOp() == Operation.ASSIGN) {
675 TempDescriptor lhs = fon.getDest();
676 TempDescriptor rhs = fon.getLeft();
678 // copy makes lhs same availability as rhs
679 if (notAvailSet.contains(rhs)) {
680 notAvailSet.add(lhs);
682 notAvailSet.remove(lhs);
685 // only break if this is an ASSIGN op node,
686 // otherwise fall through to default case
691 // note that FlatOpNode's that aren't ASSIGN
692 // fall through to this default case
694 TempDescriptor[] writeTemps = fn.writesTemps();
695 for (int i = 0; i < writeTemps.length; i++) {
696 TempDescriptor wTemp = writeTemps[i];
697 notAvailSet.remove(wTemp);
699 TempDescriptor[] readTemps = fn.readsTemps();
700 for (int i = 0; i < readTemps.length; i++) {
701 TempDescriptor rTemp = readTemps[i];
702 notAvailSet.remove(rTemp);
704 // if this variable has exactly one source, potentially
705 // get other things from this source as well
706 VarSrcTokTable vstTable = variableResults.get(fn);
708 VSTWrapper vstIfStatic = new VSTWrapper();
709 Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
711 if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
713 VariableSourceToken vst = vstIfStatic.vst;
715 Iterator<VariableSourceToken> availItr =
716 vstTable.get(vst.getSESE(), vst.getAge()).iterator();
718 // look through things that are also available from same source
719 while (availItr.hasNext()) {
720 VariableSourceToken vstAlsoAvail = availItr.next();
722 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
723 while (refVarItr.hasNext()) {
724 TempDescriptor refVarAlso = refVarItr.next();
726 // if a variable is available from the same source, AND it ALSO
727 // only comes from one statically known source, mark it available
728 VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
729 Integer srcTypeAlso =
730 vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed);
731 if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
732 notAvailSet.remove(refVarAlso);
744 private void codePlansForward(FlatMethod fm) {
746 // start from flat method top, visit every node in
747 // method exactly once
748 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
749 flatNodesToVisit.add(fm);
751 Set<FlatNode> visited = new HashSet<FlatNode>();
753 while (!flatNodesToVisit.isEmpty()) {
754 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
755 FlatNode fn = fnItr.next();
757 flatNodesToVisit.remove(fn);
760 // use incoming results as "dot statement" or just
761 // before the current statement
762 VarSrcTokTable dotSTtable = new VarSrcTokTable();
763 for (int i = 0; i < fn.numPrev(); i++) {
764 FlatNode nn = fn.getPrev(i);
765 dotSTtable.merge(variableResults.get(nn));
768 // find dt-st notAvailableSet also
769 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
770 for (int i = 0; i < fn.numPrev(); i++) {
771 FlatNode nn = fn.getPrev(i);
772 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
773 if (notAvailIn != null) {
774 dotSTnotAvailSet.addAll(notAvailIn);
778 Set<TempDescriptor> dotSTlive = livenessGlobalView.get(fn);
780 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock(fn);
781 if (currentSESE == null) {
782 currentSESE = rblockRel.getCallerProxySESE();
785 codePlans_nodeActions(fm, fn, dotSTtable, dotSTnotAvailSet, currentSESE);
787 for (int i = 0; i < fn.numNext(); i++) {
788 FlatNode nn = fn.getNext(i);
790 if (!visited.contains(nn)) {
791 flatNodesToVisit.add(nn);
797 private void codePlans_nodeActions(FlatMethod fm, FlatNode fn, VarSrcTokTable vstTableIn,
798 Set<TempDescriptor> notAvailSetIn, FlatSESEEnterNode currentSESE) {
800 CodePlan plan = new CodePlan(currentSESE);
804 case FKind.FlatSESEEnterNode: {
805 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
807 // track the source types of the in-var set so generated
808 // code at this SESE issue can compute the number of
809 // dependencies properly
810 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
811 while (inVarItr.hasNext()) {
812 TempDescriptor inVar = inVarItr.next();
814 // when we get to an SESE enter node we change the
815 // currentSESE variable of this analysis to the
816 // child that is declared by the enter node, so
817 // in order to classify in-vars correctly, pass
818 // the parent SESE in--at other FlatNode types just
819 // use the currentSESE
820 FlatSESEEnterNode parent = rblockRel.getLocalInnerRBlock(fn);
821 if (parent == null) {
822 parent = rblockRel.getCallerProxySESE();
825 VSTWrapper vstIfStatic = new VSTWrapper();
826 Integer srcType = vstTableIn.getRefVarSrcType(inVar, parent, vstIfStatic);
828 // the current SESE needs a local space to track the dynamic
829 // variable and the child needs space in its SESE record
830 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
831 fsen.addDynamicInVar(inVar);
832 addDynamicVar(parent, fm, inVar);
834 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
835 fsen.addStaticInVar(inVar);
836 VariableSourceToken vst = vstIfStatic.vst;
837 fsen.putStaticInVar2src(inVar, vst);
838 fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
841 assert srcType.equals(VarSrcTokTable.SrcType_READY);
842 fsen.addReadyInVar(inVar);
848 case FKind.FlatSESEExitNode: {
849 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
851 // Classify the sources of out-set variables so code
852 // gen can acquire them from children if necessary
853 // before this task exits
854 FlatSESEEnterNode exiter = fsexn.getFlatEnter();
856 Iterator<TempDescriptor> outVarItr = exiter.getOutVarSet().iterator();
857 while (outVarItr.hasNext()) {
858 TempDescriptor outVar = outVarItr.next();
860 VSTWrapper vstIfStatic = new VSTWrapper();
861 Integer srcType = vstTableIn.getRefVarSrcType(outVar, exiter, vstIfStatic);
863 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
864 // if the out-var is dynamic, put it in the set of dyn out vars
865 // so exiting code gen knows to look for the value, but also put
866 // it in the set of dynamic vars the exiter must track!
867 exiter.addDynamicOutVar(outVar);
868 addDynamicVar(exiter, fm, outVar);
870 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
871 exiter.addStaticOutVar(outVar);
872 VariableSourceToken vst = vstIfStatic.vst;
873 exiter.putStaticOutVar2src(outVar, vst);
874 exiter.addStaticOutVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
877 assert srcType.equals(VarSrcTokTable.SrcType_READY);
878 exiter.addReadyOutVar(outVar);
884 case FKind.FlatOpNode: {
885 FlatOpNode fon = (FlatOpNode) fn;
887 if (fon.getOp().getOp() == Operation.ASSIGN) {
888 TempDescriptor lhs = fon.getDest();
889 TempDescriptor rhs = fon.getLeft();
891 // if this is an op node, don't stall, copy
892 // source and delay until we need to use value
894 // ask whether lhs and rhs sources are dynamic, static, etc.
895 VSTWrapper vstIfStatic = new VSTWrapper();
896 Integer lhsSrcType = vstTableIn.getRefVarSrcType(lhs, currentSESE, vstIfStatic);
897 Integer rhsSrcType = vstTableIn.getRefVarSrcType(rhs, currentSESE, vstIfStatic);
899 if (rhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
900 // if rhs is dynamic going in, lhs will definitely be dynamic
901 // going out of this node, so track that here
902 plan.addDynAssign(lhs, rhs);
903 addDynamicVar(currentSESE, fm, lhs);
904 addDynamicVar(currentSESE, fm, rhs);
906 } else if (lhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
907 // otherwise, if the lhs is dynamic, but the rhs is not, we
908 // need to update the variable's dynamic source as "current SESE"
909 plan.addDynAssign(lhs);
912 // only break if this is an ASSIGN op node,
913 // otherwise fall through to default case
918 // note that FlatOpNode's that aren't ASSIGN
919 // fall through to this default case
922 // a node with no live set has nothing to stall for
923 // note: no reason to check here, remove this....
924 // if (liveSetIn == null) {
928 TempDescriptor[] readarray = fn.readsTemps();
929 for (int i = 0; i < readarray.length; i++) {
930 TempDescriptor readtmp = readarray[i];
932 // ignore temps that are definitely available
933 // when considering to stall on it
934 if (!notAvailSetIn.contains(readtmp)) {
938 // check the source type of this variable
939 VSTWrapper vstIfStatic = new VSTWrapper();
940 Integer srcType = vstTableIn.getRefVarSrcType(readtmp, currentSESE, vstIfStatic);
942 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
943 // 1) It is not clear statically where this variable will
944 // come from, so dynamically we must keep track
945 // along various control paths, and therefore when we stall,
946 // just stall for the exact thing we need and move on
947 plan.addDynamicStall(readtmp);
948 addDynamicVar(currentSESE, fm, readtmp);
950 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
951 // 2) Single token/age pair: Stall for token/age pair, and copy
952 // all live variables with same token/age pair at the same
953 // time. This is the same stuff that the notavaialable analysis
954 // marks as now available.
955 VariableSourceToken vst = vstIfStatic.vst;
957 Iterator<VariableSourceToken> availItr =
958 vstTableIn.get(vst.getSESE(), vst.getAge()).iterator();
960 while (availItr.hasNext()) {
961 VariableSourceToken vstAlsoAvail = availItr.next();
963 // only grab additional stuff that is live
964 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
966 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
968 while (refVarItr.hasNext()) {
969 TempDescriptor refVar = refVarItr.next();
970 // note: this should just use normal liveness in...only want to
971 // copy live variables...
972 if (liveness.getLiveInTemps(fm, fn).contains(refVar)) {
977 if (!copySet.isEmpty()) {
978 plan.addStall2CopySet(vstAlsoAvail, copySet);
983 // the other case for srcs is READY, so do nothing
986 // assert that everything being stalled for is in the
987 // "not available" set coming into this flat node and
988 // that every VST identified is in the possible "stall set"
989 // that represents VST's from children SESE's
997 // identify sese-age pairs that are statically useful
998 // and should have an associated SESE variable in code
999 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
1000 // AND ALWAYS GIVE NAMES TO LOCAL PARENTS
1001 Set<VariableSourceToken> staticSet = vstTableIn.get();
1002 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
1003 while (vstItr.hasNext()) {
1004 VariableSourceToken vst = vstItr.next();
1006 // the caller proxy generates useful analysis facts, but we
1007 // never need to generate another name for it in code (it is
1008 // ALWAYS the task executing the local method context)
1009 if (vst.getSESE().getIsCallerProxySESE()) {
1013 SESEandAgePair sap = new SESEandAgePair(vst.getSESE(), vst.getAge());
1014 sap.getSESE().mustTrackAtLeastAge(sap.getAge());
1016 FlatSESEEnterNode sese = currentSESE;
1017 while (sese != null) {
1018 addNeededStaticName(sese, fm, sap);
1019 sese = sese.getLocalParent();
1023 codePlans.put(fn, plan);
1025 // if any variables at this-node-*dot* have a static source (exactly one
1027 // but go to a dynamic source at next-node-*dot*, create a new IR graph
1028 // node on that edge to track the sources dynamically
1029 // NOTE: for this calculation use the currentSESE variable, except when the
1030 // FlatNode fn is an Exit--in that case currentSESE is for the exiting task,
1031 // be we want to consider that the parent is tracking a variable coming out
1032 // of the exiting task
1033 FlatSESEEnterNode fsenDoingTracking;
1034 if (fn instanceof FlatSESEExitNode) {
1035 fsenDoingTracking = currentSESE.getLocalParent();
1037 if (fsenDoingTracking == null) {
1038 // if there is no local parent, there are one of two cases
1039 // 1) the current task is main, in which case this FlatNode
1040 // is the main's exit, and doesn't need to do any of the
1041 // following dynamic tracking
1042 // 2) the current task is defined in a method, so use the
1043 // caller proxy in the variable source calcs below
1044 if (currentSESE.equals(rblockRel.getMainSESE())) {
1047 fsenDoingTracking = rblockRel.getCallerProxySESE();
1051 fsenDoingTracking = currentSESE;
1054 VarSrcTokTable thisVstTable = variableResults.get(fn);
1055 for (int i = 0; i < fn.numNext(); i++) {
1056 FlatNode nn = fn.getNext(i);
1057 VarSrcTokTable nextVstTable = variableResults.get(nn);
1058 // note: using the result of liveness analysis regardless of task
1060 Set<TempDescriptor> nextLiveIn = liveness.getLiveInTemps(fm, nn);
1062 // the table can be null if it is one of the few IR nodes
1063 // completely outside of the root SESE scope
1064 if (nextVstTable != null && nextLiveIn != null) {
1066 Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
1067 thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, fsenDoingTracking);
1069 if (!readyOrStatic2dynamicSet.isEmpty()) {
1071 // either add these results to partial fixed-point result
1072 // or make a new one if we haven't made any here yet
1073 FlatEdge fe = new FlatEdge(fn, nn);
1074 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe);
1076 if (fwdvn == null) {
1078 new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, fsenDoingTracking);
1079 wdvNodesToSpliceIn.put(fe, fwdvn);
1081 fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet);
1088 private void addDynamicVar(FlatSESEEnterNode fsen, FlatMethod fm, TempDescriptor var) {
1091 // note: dynamic variable declarations are always located in the flat method
1092 // that encloses task block
1093 // there is no need to set fnContext to fsen
1094 if (fsen.getIsCallerProxySESE()) {
1095 // attach the dynamic variable to track to
1096 // the flat method, so it can be declared at entry
1099 // otherwise the code context is a task body
1104 ContextTaskNames ctn = fn2contextTaskNames.get(fnContext);
1106 ctn = new ContextTaskNames();
1109 ctn.addDynamicVar(var);
1110 fn2contextTaskNames.put(fnContext, ctn);
1114 private void addNeededStaticName(FlatSESEEnterNode fsen, FlatMethod fm, SESEandAgePair sap) {
1117 if (fsen.getIsCallerProxySESE()) {
1118 // attach the dynamic variable to track to
1119 // the flat method, so it can be declared at entry
1122 // otherwise the code context is a task body
1126 ContextTaskNames ctn = fn2contextTaskNames.get(fnContext);
1128 ctn = new ContextTaskNames();
1131 ctn.addNeededStaticName(sap);
1133 fn2contextTaskNames.put(fnContext, ctn);
1136 private void startConflictGraphs() {
1138 // first, for each task, consider whether it has any children, and if
1139 // effects analysis says they should be a conflict node in the that
1140 // parent's conflict graph
1141 Set<FlatSESEEnterNode> allSESEs = rblockRel.getAllSESEs();
1142 for (Iterator iterator = allSESEs.iterator(); iterator.hasNext(); ) {
1144 FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
1145 if (parent.getIsLeafSESE()) {
1149 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1150 ConflictGraph conflictGraph = sese2conflictGraph.get(parent);
1151 assert conflictGraph == null;
1152 conflictGraph = new ConflictGraph(state);
1154 Set<FlatSESEEnterNode> children = parent.getChildren();
1155 for (Iterator iterator2 = children.iterator(); iterator2.hasNext(); ) {
1156 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
1157 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(child);
1158 conflictGraph.addLiveIn(taint2Effects);
1161 sese2conflictGraph.put(parent, conflictGraph);
1164 // then traverse all methods looking for potential stall sites, and
1165 // add those stall sites as nodes in any task's conflict graph that
1166 // might be executing at the point of the stall site
1167 Iterator<MethodDescriptor> descItr = descriptorsToAnalyze.iterator();
1168 while (descItr.hasNext()) {
1169 MethodDescriptor md = descItr.next();
1170 FlatMethod fm = state.getMethodFlat(md);
1172 addStallSitesToConflictGraphs(fm);
1177 private void addStallSitesToConflictGraphs(FlatMethod fm) {
1179 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1180 flatNodesToVisit.add(fm);
1182 Set<FlatNode> visited = new HashSet<FlatNode>();
1184 while (!flatNodesToVisit.isEmpty()) {
1185 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1186 flatNodesToVisit.remove(fn);
1189 Set<FlatSESEEnterNode> currentSESEs = rblockRel.getPossibleExecutingRBlocks(fn);
1191 conflictGraph_nodeAction(fn, currentSESEs, fm.getMethod().getClassDesc());
1193 // schedule forward nodes for analysis
1194 for (int i = 0; i < fn.numNext(); i++) {
1195 FlatNode nn = fn.getNext(i);
1196 if (!visited.contains(nn)) {
1197 flatNodesToVisit.add(nn);
1203 private void conflictGraph_nodeAction(FlatNode fn, Set<FlatSESEEnterNode> currentSESEs,
1204 ClassDescriptor cd) {
1206 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1208 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1210 // repeat the process of adding a stall site to a conflict graph
1211 // for each task that might be executing at a possible stall site
1212 Iterator<FlatSESEEnterNode> seseItr = currentSESEs.iterator();
1213 while (seseItr.hasNext()) {
1214 FlatSESEEnterNode currentSESE = seseItr.next();
1216 ConflictGraph conflictGraph = sese2conflictGraph.get(currentSESE);
1217 if (conflictGraph == null) {
1218 assert currentSESE.getIsLeafSESE();
1225 switch (fn.kind()) {
1227 case FKind.FlatFieldNode:
1228 case FKind.FlatElementNode: {
1230 if (fn instanceof FlatFieldNode) {
1231 FlatFieldNode ffn = (FlatFieldNode) fn;
1234 FlatElementNode fen = (FlatElementNode) fn;
1238 conflictGraph.addStallSite(taint2Effects, rhs, cd);
1242 case FKind.FlatSetFieldNode:
1243 case FKind.FlatSetElementNode: {
1245 if (fn instanceof FlatSetFieldNode) {
1246 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1247 lhs = fsfn.getDst();
1248 rhs = fsfn.getSrc();
1250 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1251 lhs = fsen.getDst();
1252 rhs = fsen.getSrc();
1255 conflictGraph.addStallSite(taint2Effects, rhs, cd);
1256 conflictGraph.addStallSite(taint2Effects, lhs, cd);
1260 case FKind.FlatCall: {
1261 FlatCall fc = (FlatCall) fn;
1264 conflictGraph.addStallSite(taint2Effects, lhs, cd);
1270 if (conflictGraph.id2cn.size() > 0) {
1271 sese2conflictGraph.put(currentSESE, conflictGraph);
1276 private void calculateConflicts(Set<FlatNew> sitesToFlag, boolean useReachInfo) {
1278 // decide fine-grain edge or coarse-grain edge among all vertexes by
1279 // pair-wise comparison
1280 Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
1281 while (seseIter.hasNext()) {
1282 FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next();
1283 ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
1286 // clear current conflict before recalculating with reachability info
1287 conflictGraph.clearAllConflictEdge();
1288 conflictGraph.setDisJointAnalysis(disjointAnalysisReach);
1289 conflictGraph.setFMEnclosing(sese.getfmEnclosing());
1291 conflictGraph.analyzeConflicts(sitesToFlag, useReachInfo);
1292 sese2conflictGraph.put(sese, conflictGraph);
1296 private void writeConflictGraph() {
1297 Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
1298 while (keyEnum.hasMoreElements()) {
1299 FlatNode key = (FlatNode) keyEnum.nextElement();
1300 ConflictGraph cg = sese2conflictGraph.get(key);
1302 if (cg.hasConflictEdge()) {
1303 cg.writeGraph("ConflictGraphFor" + key, false);
1305 } catch (IOException e) {
1306 System.out.println("Error writing");
1312 // the traversal for pruning state machines and finding
1313 // machines that are weakly connected BOTH consider conflicting
1314 // effects between heap roots, so it is smart to compute all of
1316 public void pruneMachinesAndFindWeaklyConnectedExaminers() {
1317 ProcessStateMachines psm = new ProcessStateMachines(buildStateMachines, rblockRel);
1319 buildStateMachines.writeStateMachines("pruned");
1322 private void synthesizeLocks() {
1323 // for every conflict graph, generate a set of memory queues
1324 // (called SESELock in this code!) to cover the graph
1325 Set<Map.Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
1326 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext(); ) {
1327 Map.Entry<FlatNode, ConflictGraph> graphEntry =
1328 (Map.Entry<FlatNode, ConflictGraph>)iterator.next();
1329 FlatNode sese = graphEntry.getKey();
1330 ConflictGraph conflictGraph = graphEntry.getValue();
1331 calculateCovering(conflictGraph);
1335 private void calculateCovering(ConflictGraph conflictGraph) {
1336 uniqueLockSetId = 0; // reset lock counter for every new conflict graph
1337 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1338 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1339 HashSet<SESELock> lockSet = new HashSet<SESELock>();
1341 Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1342 for (Iterator iterator = tempCover.iterator(); iterator.hasNext(); ) {
1343 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1344 if (conflictEdge.isCoarseEdge()) {
1345 coarseToCover.add(conflictEdge);
1347 fineToCover.add(conflictEdge);
1351 HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
1352 toCover.addAll(fineToCover);
1353 toCover.addAll(coarseToCover);
1355 while (!toCover.isEmpty()) {
1357 SESELock seseLock = new SESELock();
1358 seseLock.setID(uniqueLockSetId++);
1362 do { // fine-grained edge
1366 for (Iterator iterator = fineToCover.iterator(); iterator.hasNext(); ) {
1369 ConflictEdge edge = (ConflictEdge) iterator.next();
1370 if (seseLock.getConflictNodeSet().size() == 0) {
1372 if (seseLock.isWriteNode(edge.getVertexU())) {
1373 // mark as fine_write
1374 if (edge.getVertexU().isStallSiteNode()) {
1375 type = ConflictNode.PARENT_WRITE;
1377 type = ConflictNode.FINE_WRITE;
1379 seseLock.addConflictNode(edge.getVertexU(), type);
1381 // mark as fine_read
1382 if (edge.getVertexU().isStallSiteNode()) {
1383 type = ConflictNode.PARENT_READ;
1385 type = ConflictNode.FINE_READ;
1387 seseLock.addConflictNode(edge.getVertexU(), type);
1389 if (edge.getVertexV() != edge.getVertexU()) {
1390 if (seseLock.isWriteNode(edge.getVertexV())) {
1391 // mark as fine_write
1392 if (edge.getVertexV().isStallSiteNode()) {
1393 type = ConflictNode.PARENT_WRITE;
1395 type = ConflictNode.FINE_WRITE;
1397 seseLock.addConflictNode(edge.getVertexV(), type);
1399 // mark as fine_read
1400 if (edge.getVertexV().isStallSiteNode()) {
1401 type = ConflictNode.PARENT_READ;
1403 type = ConflictNode.FINE_READ;
1405 seseLock.addConflictNode(edge.getVertexV(), type);
1409 seseLock.addConflictEdge(edge);
1410 fineToCover.remove(edge);
1411 break; // exit iterator loop
1412 } // end of initial setup
1414 ConflictNode newNode;
1415 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1416 // new node has a fine-grained edge to all current node
1417 // If there is a coarse grained edge where need a fine edge, it's
1418 // okay to add the node
1419 // but the edge must remain uncovered.
1423 if (seseLock.containsConflictNode(newNode)) {
1424 seseLock.addEdge(edge);
1425 fineToCover.remove(edge);
1429 if (seseLock.isWriteNode(newNode)) {
1430 if (newNode.isStallSiteNode()) {
1431 type = ConflictNode.PARENT_WRITE;
1433 type = ConflictNode.FINE_WRITE;
1435 seseLock.setNodeType(newNode, type);
1437 if (newNode.isStallSiteNode()) {
1438 type = ConflictNode.PARENT_READ;
1440 type = ConflictNode.FINE_READ;
1442 seseLock.setNodeType(newNode, type);
1445 seseLock.addEdge(edge);
1446 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1447 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext(); ) {
1448 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1450 // mark all fine edges between new node and nodes in the group as
1452 if (!conflictEdge.getVertexU().equals(newNode)) {
1453 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1455 seseLock.addConflictEdge(conflictEdge);
1456 fineToCover.remove(conflictEdge);
1458 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1459 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1461 seseLock.addConflictEdge(conflictEdge);
1462 fineToCover.remove(conflictEdge);
1468 break; // exit iterator loop
1473 HashSet<ConflictEdge> notCovered = new HashSet<ConflictEdge>();
1477 for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext(); ) {
1479 ConflictEdge edge = (ConflictEdge) iterator.next();
1480 if (seseLock.getConflictNodeSet().size() == 0) {
1482 if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
1483 // node has a coarse-grained edge with itself
1484 if (!(edge.getVertexU().isStallSiteNode())) {
1485 // and it is not parent
1486 type = ConflictNode.SCC;
1489 type = ConflictNode.PARENT_COARSE;
1491 type = ConflictNode.PARENT_WRITE;
1494 seseLock.addConflictNode(edge.getVertexU(), type);
1496 if (edge.getVertexU().isStallSiteNode()) {
1498 type = ConflictNode.PARENT_COARSE;
1500 if (edge.getVertexU().getWriteEffectSet().isEmpty()) {
1501 type = ConflictNode.PARENT_READ;
1503 type = ConflictNode.PARENT_WRITE;
1507 type = ConflictNode.COARSE;
1509 seseLock.addConflictNode(edge.getVertexU(), type);
1511 if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
1512 // node has a coarse-grained edge with itself
1513 if (!(edge.getVertexV().isStallSiteNode())) {
1514 // and it is not parent
1515 type = ConflictNode.SCC;
1518 type = ConflictNode.PARENT_COARSE;
1520 type = ConflictNode.PARENT_WRITE;
1523 seseLock.addConflictNode(edge.getVertexV(), type);
1525 if (edge.getVertexV().isStallSiteNode()) {
1527 type = ConflictNode.PARENT_COARSE;
1529 if (edge.getVertexV().getWriteEffectSet().isEmpty()) {
1530 type = ConflictNode.PARENT_READ;
1532 type = ConflictNode.PARENT_WRITE;
1536 type = ConflictNode.COARSE;
1538 seseLock.addConflictNode(edge.getVertexV(), type);
1541 coarseToCover.remove(edge);
1542 seseLock.addConflictEdge(edge);
1543 break; // exit iterator loop
1544 } // end of initial setup
1546 ConflictNode newNode;
1547 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1548 // new node has a coarse-grained edge to all fine-read, fine-write,
1552 if (newNode.isInVarNode() && (!seseLock.hasSelfCoarseEdge(newNode))
1553 && seseLock.hasCoarseEdgeWithParentCoarse(newNode)) {
1554 // this case can't be covered by this queue
1555 coarseToCover.remove(edge);
1556 notCovered.add(edge);
1560 if (seseLock.containsConflictNode(newNode)) {
1561 seseLock.addEdge(edge);
1562 coarseToCover.remove(edge);
1566 if (seseLock.hasSelfCoarseEdge(newNode)) {
1568 if (newNode.isStallSiteNode()) {
1569 type = ConflictNode.PARENT_COARSE;
1571 type = ConflictNode.SCC;
1573 seseLock.setNodeType(newNode, type);
1575 if (newNode.isStallSiteNode()) {
1576 type = ConflictNode.PARENT_COARSE;
1578 type = ConflictNode.COARSE;
1580 seseLock.setNodeType(newNode, type);
1583 seseLock.addEdge(edge);
1584 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1585 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext(); ) {
1586 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1587 // mark all coarse edges between new node and nodes in the group
1589 if (!conflictEdge.getVertexU().equals(newNode)) {
1590 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1592 seseLock.addConflictEdge(conflictEdge);
1593 coarseToCover.remove(conflictEdge);
1595 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1596 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1598 seseLock.addConflictEdge(conflictEdge);
1599 coarseToCover.remove(conflictEdge);
1604 break; // exit iterator loop
1610 lockSet.add(seseLock);
1613 coarseToCover.addAll(notCovered);
1614 toCover.addAll(fineToCover);
1615 toCover.addAll(coarseToCover);
1619 conflictGraph2SESELock.put(conflictGraph, lockSet);
1622 public ConflictGraph getConflictGraph(FlatNode sese) {
1623 return sese2conflictGraph.get(sese);
1626 public Set<SESELock> getLockMappings(ConflictGraph graph) {
1627 return conflictGraph2SESELock.get(graph);
1630 public Set<FlatSESEEnterNode> getAllSESEs() {
1631 return rblockRel.getAllSESEs();
1634 public FlatSESEEnterNode getMainSESE() {
1635 return rblockRel.getMainSESE();
1638 public FlatSESEEnterNode getCallerProxySESE() {
1639 return rblockRel.getCallerProxySESE();
1642 public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks(FlatNode fn) {
1643 return rblockRel.getPossibleExecutingRBlocks(fn);
1646 public void writeReports(String timeReport) throws java.io.IOException {
1648 BufferedWriter bw = new BufferedWriter(new FileWriter("ooojReport_summary.txt"));
1649 bw.write("OoOJava Analysis Results\n\n");
1650 bw.write(timeReport + "\n\n");
1651 printSESEHierarchy(bw);
1656 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
1657 while (methItr.hasNext()) {
1658 MethodDescriptor md = methItr.next();
1659 FlatMethod fm = state.getMethodFlat(md);
1662 new BufferedWriter(new FileWriter("ooojReport_" + md.getClassMethodName()
1663 + md.getSafeMethodDescriptor() + ".txt"));
1664 bw.write("OoOJava Results for " + md + "\n-------------------\n");
1666 bw.write("Dynamic vars to manage:\n " + getContextTaskNames(fm).getDynamicVarSet());
1668 bw.write("\n\nLive-In, Root View\n------------------\n"
1669 + fm.printMethod(livenessGlobalView));
1670 bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults));
1671 bw.write("\n\nNot Available Results-Out\n---------------------\n"
1672 + fm.printMethod(notAvailableResults));
1673 bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans));
1679 private void printSESEHierarchy(BufferedWriter bw) throws java.io.IOException {
1680 bw.write("SESE Local Hierarchy\n--------------\n");
1681 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getLocalRootSESEs().iterator();
1682 while (rootItr.hasNext()) {
1683 FlatSESEEnterNode root = rootItr.next();
1684 printSESEHierarchyTree(bw, root, 0);
1688 private void printSESEHierarchyTree(BufferedWriter bw, FlatSESEEnterNode fsen, int depth)
1689 throws java.io.IOException {
1690 for (int i = 0; i < depth; ++i) {
1693 bw.write("- " + fsen.getPrettyIdentifier() + "\n");
1695 Iterator<FlatSESEEnterNode> childItr = fsen.getLocalChildren().iterator();
1696 while (childItr.hasNext()) {
1697 FlatSESEEnterNode fsenChild = childItr.next();
1698 printSESEHierarchyTree(bw, fsenChild, depth + 1);
1702 private void printSESEInfo(BufferedWriter bw) throws java.io.IOException {
1703 bw.write("\nSESE info\n-------------\n");
1704 Iterator<FlatSESEEnterNode> fsenItr = rblockRel.getAllSESEs().iterator();
1705 while (fsenItr.hasNext()) {
1706 FlatSESEEnterNode fsen = fsenItr.next();
1708 bw.write("SESE " + fsen.getPrettyIdentifier());
1709 if (fsen.getIsLeafSESE()) {
1710 bw.write(" (leaf)");
1714 bw.write(" in-set: " + fsen.getInVarSet() + "\n");
1715 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1716 while (tItr.hasNext()) {
1717 TempDescriptor inVar = tItr.next();
1718 if (fsen.getReadyInVarSet().contains(inVar)) {
1719 bw.write(" (ready) " + inVar + "\n");
1721 if (fsen.getStaticInVarSet().contains(inVar)) {
1722 bw.write(" (static) " + inVar + " from " + fsen.getStaticInVarSrc(inVar) + "\n");
1724 if (fsen.getDynamicInVarSet().contains(inVar)) {
1725 bw.write(" (dynamic)" + inVar + "\n");
1729 bw.write(" Dynamic vars to manage: " + getContextTaskNames(fsen).getDynamicVarSet() + "\n");
1731 bw.write(" out-set: " + fsen.getOutVarSet() + "\n");
1732 tItr = fsen.getOutVarSet().iterator();
1733 while (tItr.hasNext()) {
1734 TempDescriptor outVar = tItr.next();
1735 if (fsen.getReadyOutVarSet().contains(outVar)) {
1736 bw.write(" (ready) " + outVar + "\n");
1738 if (fsen.getStaticOutVarSet().contains(outVar)) {
1739 bw.write(" (static) " + outVar + " from " + fsen.getStaticOutVarSrc(outVar) + "\n");
1741 if (fsen.getDynamicOutVarSet().contains(outVar)) {
1742 bw.write(" (dynamic)" + outVar + "\n");
1746 bw.write(" local parent: " + fsen.getLocalParent() + "\n");
1747 bw.write(" local children: " + fsen.getLocalChildren() + "\n");
1749 bw.write(" possible parents: " + fsen.getParents() + "\n");
1750 bw.write(" possible children: " + fsen.getChildren() + "\n");