1 package Analysis.OoOJava;
3 import java.io.BufferedWriter;
4 import java.io.FileWriter;
5 import java.io.IOException;
6 import java.util.Enumeration;
7 import java.util.HashSet;
8 import java.util.Hashtable;
9 import java.util.Iterator;
12 import java.util.Stack;
13 import java.util.Map.Entry;
15 import Analysis.ArrayReferencees;
16 import Analysis.Liveness;
17 import Analysis.CallGraph.CallGraph;
18 import Analysis.Disjoint.DisjointAnalysis;
19 import Analysis.Disjoint.Effect;
20 import Analysis.Disjoint.EffectsAnalysis;
21 import Analysis.Disjoint.Taint;
22 import Analysis.MLP.CodePlan;
23 import Analysis.MLP.SESEandAgePair;
24 import Analysis.MLP.VSTWrapper;
25 import Analysis.MLP.VarSrcTokTable;
26 import Analysis.MLP.VariableSourceToken;
28 import IR.MethodDescriptor;
33 import IR.Flat.FlatCall;
34 import IR.Flat.FlatEdge;
35 import IR.Flat.FlatElementNode;
36 import IR.Flat.FlatFieldNode;
37 import IR.Flat.FlatMethod;
38 import IR.Flat.FlatNew;
39 import IR.Flat.FlatNode;
40 import IR.Flat.FlatOpNode;
41 import IR.Flat.FlatSESEEnterNode;
42 import IR.Flat.FlatSESEExitNode;
43 import IR.Flat.FlatSetElementNode;
44 import IR.Flat.FlatSetFieldNode;
45 import IR.Flat.FlatWriteDynamicVarNode;
46 import IR.Flat.TempDescriptor;
48 public class OoOJavaAnalysis {
50 // data from the compiler
52 private TypeUtil typeUtil;
53 private CallGraph callGraph;
54 private RBlockRelationAnalysis rblockRel;
55 private RBlockStatusAnalysis rblockStatus;
56 private DisjointAnalysis disjointAnalysisTaints;
57 private DisjointAnalysis disjointAnalysisReach;
59 private Hashtable<FlatNode, Set<TempDescriptor>> livenessRootView;
60 private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
61 private Hashtable<FlatNode, VarSrcTokTable> variableResults;
62 private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
63 private Hashtable<FlatNode, CodePlan> codePlans;
65 private Hashtable<FlatSESEEnterNode, Set<TempDescriptor>> notAvailableIntoSESE;
67 private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
69 // temporal data structures to track analysis progress.
70 static private int uniqueLockSetId = 0;
71 // mapping of a conflict graph to its compiled lock
72 private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraph2SESELock;
73 // mapping of a sese block to its conflict graph
74 private Hashtable<FlatNode, ConflictGraph> sese2conflictGraph;
76 public static int maxSESEage = -1;
78 public int getMaxSESEage() {
83 public CodePlan getCodePlan(FlatNode fn) {
84 CodePlan cp = codePlans.get(fn);
88 public OoOJavaAnalysis(State state, TypeUtil typeUtil, CallGraph callGraph, Liveness liveness,
89 ArrayReferencees arrayReferencees) {
91 double timeStartAnalysis = (double) System.nanoTime();
94 this.typeUtil = typeUtil;
95 this.callGraph = callGraph;
96 this.maxSESEage = state.MLP_MAXSESEAGE;
98 livenessRootView = new Hashtable<FlatNode, Set<TempDescriptor>>();
99 livenessVirtualReads = new Hashtable<FlatNode, Set<TempDescriptor>>();
100 variableResults = new Hashtable<FlatNode, VarSrcTokTable>();
101 notAvailableResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
102 codePlans = new Hashtable<FlatNode, CodePlan>();
103 wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
105 notAvailableIntoSESE = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
107 sese2conflictGraph = new Hashtable<FlatNode, ConflictGraph>();
108 conflictGraph2SESELock = new Hashtable<ConflictGraph, HashSet<SESELock>>();
110 // add all methods transitively reachable from the
111 // source's main to set for analysis
112 MethodDescriptor mdSourceEntry = typeUtil.getMain();
113 FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
115 Set<MethodDescriptor> descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
117 descriptorsToAnalyze.add(mdSourceEntry);
119 // 1st pass, find basic rblock relations & status
120 rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
121 rblockStatus = new RBlockStatusAnalysis(state, typeUtil, callGraph, rblockRel);
123 // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
124 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getRootSESEs().iterator();
125 while (rootItr.hasNext()) {
126 FlatSESEEnterNode root = rootItr.next();
127 livenessAnalysisBackward(root, true, null);
130 // 3rd pass, variable analysis
131 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
132 while (methItr.hasNext()) {
133 Descriptor d = methItr.next();
134 FlatMethod fm = state.getMethodFlat(d);
136 // starting from roots do a forward, fixed-point
137 // variable analysis for refinement and stalls
138 variableAnalysisForward(fm);
141 // 4th pass, compute liveness contribution from
142 // virtual reads discovered in variable pass
143 rootItr = rblockRel.getRootSESEs().iterator();
144 while (rootItr.hasNext()) {
145 FlatSESEEnterNode root = rootItr.next();
146 livenessAnalysisBackward(root, true, null);
149 // 5th pass, use disjointness with NO FLAGGED REGIONS
150 // to compute taints and effects
151 disjointAnalysisTaints =
152 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null,
153 rblockRel, rblockStatus,
154 true ); // suppress output--this is an intermediate pass
156 // 6th pass, not available analysis FOR VARIABLES!
157 methItr = descriptorsToAnalyze.iterator();
158 while (methItr.hasNext()) {
159 Descriptor d = methItr.next();
160 FlatMethod fm = state.getMethodFlat(d);
162 // compute what is not available at every program
163 // point, in a forward fixed-point pass
164 notAvailableForward(fm);
167 // 7th pass, make conflict graph
168 // conflict graph is maintained by each parent sese,
169 Iterator descItr = disjointAnalysisTaints.getDescriptorsToAnalyze().iterator();
170 while (descItr.hasNext()) {
171 Descriptor d = (Descriptor) descItr.next();
172 FlatMethod fm = state.getMethodFlat(d);
174 makeConflictGraph(fm);
179 * Iterator iter = sese2conflictGraph.entrySet().iterator(); while
180 * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn =
181 * (FlatNode) e.getKey(); ConflictGraph conflictGraph = (ConflictGraph)
183 * System.out.println("---------------------------------------");
184 * System.out.println("CONFLICT GRAPH for " + fn); Set<String> keySet =
185 * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator();
186 * iterator.hasNext();) { String key = (String) iterator.next();
187 * ConflictNode node = conflictGraph.id2cn.get(key);
188 * System.out.println("key=" + key + " \n" + node.toStringAllEffects()); } }
191 // 8th pass, calculate all possible conflicts without using reachability
193 // and identify set of FlatNew that next disjoint reach. analysis should
195 Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
196 calculateConflicts(sitesToFlag, false);
198 // 9th pass, ask disjoint analysis to compute reachability
199 // for objects that may cause heap conflicts so the most
200 // efficient method to deal with conflict can be computed
203 disjointAnalysisReach =
204 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, sitesToFlag,
205 null, // don't do effects analysis again!
206 null // don't do effects analysis again!
208 // 10th pass, calculate conflicts with reachability info
209 calculateConflicts(null, true);
211 // 11th pass, compiling locks
214 // 12th pass, compute a plan for code injections
215 methItr = descriptorsToAnalyze.iterator();
216 while (methItr.hasNext()) {
217 Descriptor d = methItr.next();
218 FlatMethod fm = state.getMethodFlat(d);
219 codePlansForward(fm);
223 // splice new IR nodes into graph after all
224 // analysis passes are complete
225 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
226 while (spliceItr.hasNext()) {
227 Map.Entry me = (Map.Entry) spliceItr.next();
228 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
229 fwdvn.spliceIntoIR();
232 if (state.OOODEBUG) {
235 disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt");
236 writeConflictGraph();
237 } catch (IOException e) {
243 private void writeFile(Set<FlatNew> sitesToFlag) {
246 BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt"));
248 for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext();) {
249 FlatNew fn = (FlatNew) iterator.next();
253 } catch (IOException e) {
259 private void livenessAnalysisBackward(FlatSESEEnterNode fsen, boolean toplevel,
260 Hashtable<FlatSESEExitNode, Set<TempDescriptor>> liveout) {
262 // start from an SESE exit, visit nodes in reverse up to
263 // SESE enter in a fixed-point scheme, where children SESEs
264 // should already be analyzed and therefore can be skipped
265 // because child SESE enter node has all necessary info
266 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
269 flatNodesToVisit.add(fsen.getfmEnclosing().getFlatExit());
271 flatNodesToVisit.add(fsen.getFlatExit());
274 Hashtable<FlatNode, Set<TempDescriptor>> livenessResults =
275 new Hashtable<FlatNode, Set<TempDescriptor>>();
278 liveout = new Hashtable<FlatSESEExitNode, Set<TempDescriptor>>();
281 while (!flatNodesToVisit.isEmpty()) {
282 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
283 flatNodesToVisit.remove(fn);
285 Set<TempDescriptor> prev = livenessResults.get(fn);
287 // merge sets from control flow joins
288 Set<TempDescriptor> u = new HashSet<TempDescriptor>();
289 for (int i = 0; i < fn.numNext(); i++) {
290 FlatNode nn = fn.getNext(i);
291 Set<TempDescriptor> s = livenessResults.get(nn);
297 Set<TempDescriptor> curr = liveness_nodeActions(fn, u, fsen, toplevel, liveout);
299 // if a new result, schedule backward nodes for analysis
300 if (!curr.equals(prev)) {
301 livenessResults.put(fn, curr);
303 // don't flow backwards past current SESE enter
304 if (!fn.equals(fsen)) {
305 for (int i = 0; i < fn.numPrev(); i++) {
306 FlatNode nn = fn.getPrev(i);
307 flatNodesToVisit.add(nn);
313 Set<TempDescriptor> s = livenessResults.get(fsen);
318 // remember liveness per node from the root view as the
319 // global liveness of variables for later passes to use
321 livenessRootView.putAll(livenessResults);
324 // post-order traversal, so do children first
325 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
326 while (childItr.hasNext()) {
327 FlatSESEEnterNode fsenChild = childItr.next();
328 livenessAnalysisBackward(fsenChild, false, liveout);
332 private Set<TempDescriptor> liveness_nodeActions(FlatNode fn, Set<TempDescriptor> liveIn,
333 FlatSESEEnterNode currentSESE, boolean toplevel,
334 Hashtable<FlatSESEExitNode, Set<TempDescriptor>> liveout) {
337 case FKind.FlatSESEExitNode:
339 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
340 if (!liveout.containsKey(fsexn)) {
341 liveout.put(fsexn, new HashSet<TempDescriptor>());
343 liveout.get(fsexn).addAll(liveIn);
345 // no break, sese exits should also execute default actions
348 // handle effects of statement in reverse, writes then reads
349 TempDescriptor[] writeTemps = fn.writesTemps();
350 for (int i = 0; i < writeTemps.length; ++i) {
351 liveIn.remove(writeTemps[i]);
354 FlatSESEExitNode fsexn = currentSESE.getFlatExit();
355 Set<TempDescriptor> livetemps = liveout.get(fsexn);
356 if (livetemps != null && livetemps.contains(writeTemps[i])) {
357 // write to a live out temp...
358 // need to put in SESE liveout set
359 currentSESE.addOutVar(writeTemps[i]);
364 TempDescriptor[] readTemps = fn.readsTemps();
365 for (int i = 0; i < readTemps.length; ++i) {
366 liveIn.add(readTemps[i]);
369 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get(fn);
370 if (virtualReadTemps != null) {
371 liveIn.addAll(virtualReadTemps);
382 private void variableAnalysisForward(FlatMethod fm) {
384 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
385 flatNodesToVisit.add(fm);
387 while (!flatNodesToVisit.isEmpty()) {
388 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
389 flatNodesToVisit.remove(fn);
391 Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
392 assert seseStack != null;
394 VarSrcTokTable prev = variableResults.get(fn);
396 // merge sets from control flow joins
397 VarSrcTokTable curr = new VarSrcTokTable();
398 for (int i = 0; i < fn.numPrev(); i++) {
399 FlatNode nn = fn.getPrev(i);
400 VarSrcTokTable incoming = variableResults.get(nn);
401 curr.merge(incoming);
404 if (!seseStack.empty()) {
405 variable_nodeActions(fn, curr, seseStack.peek());
408 // if a new result, schedule forward nodes for analysis
409 if (!curr.equals(prev)) {
410 variableResults.put(fn, curr);
412 for (int i = 0; i < fn.numNext(); i++) {
413 FlatNode nn = fn.getNext(i);
414 flatNodesToVisit.add(nn);
420 private void variable_nodeActions(FlatNode fn, VarSrcTokTable vstTable,
421 FlatSESEEnterNode currentSESE) {
424 case FKind.FlatSESEEnterNode: {
425 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
426 assert fsen.equals(currentSESE);
428 vstTable.age(currentSESE);
429 vstTable.assertConsistency();
433 case FKind.FlatSESEExitNode: {
434 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
435 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
436 assert currentSESE.getChildren().contains(fsen);
438 // remap all of this child's children tokens to be
439 // from this child as the child exits
440 vstTable.remapChildTokens(fsen);
442 // liveness virtual reads are things that might be
443 // written by an SESE and should be added to the in-set
444 // anything virtually read by this SESE should be pruned
445 // of parent or sibling sources
446 Set<TempDescriptor> liveVars = livenessRootView.get(fn);
447 Set<TempDescriptor> fsenVirtReads =
448 vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen, liveVars);
449 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
450 if (fsenVirtReadsOld != null) {
451 fsenVirtReads.addAll(fsenVirtReadsOld);
453 livenessVirtualReads.put(fn, fsenVirtReads);
455 // then all child out-set tokens are guaranteed
456 // to be filled in, so clobber those entries with
457 // the latest, clean sources
458 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
459 while (outVarItr.hasNext()) {
460 TempDescriptor outVar = outVarItr.next();
461 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
463 VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
464 vstTable.remove(outVar);
467 vstTable.assertConsistency();
472 case FKind.FlatOpNode: {
473 FlatOpNode fon = (FlatOpNode) fn;
475 if (fon.getOp().getOp() == Operation.ASSIGN) {
476 TempDescriptor lhs = fon.getDest();
477 TempDescriptor rhs = fon.getLeft();
479 vstTable.remove(lhs);
481 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
483 Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
484 while (itr.hasNext()) {
485 VariableSourceToken vst = itr.next();
487 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
490 if (currentSESE.getChildren().contains(vst.getSESE())) {
491 // if the source comes from a child, copy it over
492 forAddition.add(new VariableSourceToken(ts, vst.getSESE(), vst.getAge(), vst
495 // otherwise, stamp it as us as the source
496 forAddition.add(new VariableSourceToken(ts, currentSESE, new Integer(0), lhs));
500 vstTable.addAll(forAddition);
502 // only break if this is an ASSIGN op node,
503 // otherwise fall through to default case
504 vstTable.assertConsistency();
509 // note that FlatOpNode's that aren't ASSIGN
510 // fall through to this default case
512 TempDescriptor[] writeTemps = fn.writesTemps();
513 if (writeTemps.length > 0) {
515 // for now, when writeTemps > 1, make sure
516 // its a call node, programmer enforce only
517 // doing stuff like calling a print routine
518 // assert writeTemps.length == 1;
519 if (writeTemps.length > 1) {
520 assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
524 vstTable.remove(writeTemps[0]);
526 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
527 ts.add(writeTemps[0]);
529 vstTable.add(new VariableSourceToken(ts, currentSESE, new Integer(0), writeTemps[0]));
532 vstTable.assertConsistency();
539 private void notAvailableForward(FlatMethod fm) {
541 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
542 flatNodesToVisit.add(fm);
544 while (!flatNodesToVisit.isEmpty()) {
545 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
546 flatNodesToVisit.remove(fn);
548 Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
549 assert seseStack != null;
551 Set<TempDescriptor> prev = notAvailableResults.get(fn);
553 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
554 for (int i = 0; i < fn.numPrev(); i++) {
555 FlatNode nn = fn.getPrev(i);
556 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
557 if (notAvailIn != null) {
558 curr.addAll(notAvailIn);
562 if (!seseStack.empty()) {
563 notAvailable_nodeActions(fn, curr, seseStack.peek());
566 // if a new result, schedule forward nodes for analysis
567 if (!curr.equals(prev)) {
568 notAvailableResults.put(fn, curr);
570 for (int i = 0; i < fn.numNext(); i++) {
571 FlatNode nn = fn.getNext(i);
572 flatNodesToVisit.add(nn);
578 private void notAvailable_nodeActions(FlatNode fn, Set<TempDescriptor> notAvailSet,
579 FlatSESEEnterNode currentSESE) {
581 // any temps that are removed from the not available set
582 // at this node should be marked in this node's code plan
583 // as temps to be grabbed at runtime!
587 case FKind.FlatSESEEnterNode: {
588 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
589 assert fsen.equals(currentSESE);
591 // keep a copy of what's not available into the SESE
592 // and restore it at the matching exit node
593 Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
594 Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
595 while (tdItr.hasNext()) {
596 notAvailCopy.add(tdItr.next());
598 notAvailableIntoSESE.put(fsen, notAvailCopy);
604 case FKind.FlatSESEExitNode: {
605 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
606 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
607 assert currentSESE.getChildren().contains(fsen);
609 notAvailSet.addAll(fsen.getOutVarSet());
611 Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
612 assert notAvailIn != null;
613 notAvailSet.addAll(notAvailIn);
618 case FKind.FlatMethod: {
622 case FKind.FlatOpNode: {
623 FlatOpNode fon = (FlatOpNode) fn;
625 if (fon.getOp().getOp() == Operation.ASSIGN) {
626 TempDescriptor lhs = fon.getDest();
627 TempDescriptor rhs = fon.getLeft();
629 // copy makes lhs same availability as rhs
630 if (notAvailSet.contains(rhs)) {
631 notAvailSet.add(lhs);
633 notAvailSet.remove(lhs);
636 // only break if this is an ASSIGN op node,
637 // otherwise fall through to default case
642 // note that FlatOpNode's that aren't ASSIGN
643 // fall through to this default case
645 TempDescriptor[] writeTemps = fn.writesTemps();
646 for (int i = 0; i < writeTemps.length; i++) {
647 TempDescriptor wTemp = writeTemps[i];
648 notAvailSet.remove(wTemp);
650 TempDescriptor[] readTemps = fn.readsTemps();
651 for (int i = 0; i < readTemps.length; i++) {
652 TempDescriptor rTemp = readTemps[i];
653 notAvailSet.remove(rTemp);
655 // if this variable has exactly one source, potentially
656 // get other things from this source as well
657 VarSrcTokTable vstTable = variableResults.get(fn);
659 VSTWrapper vstIfStatic = new VSTWrapper();
660 Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
662 if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
664 VariableSourceToken vst = vstIfStatic.vst;
666 Iterator<VariableSourceToken> availItr =
667 vstTable.get(vst.getSESE(), vst.getAge()).iterator();
669 // look through things that are also available from same source
670 while (availItr.hasNext()) {
671 VariableSourceToken vstAlsoAvail = availItr.next();
673 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
674 while (refVarItr.hasNext()) {
675 TempDescriptor refVarAlso = refVarItr.next();
677 // if a variable is available from the same source, AND it ALSO
678 // only comes from one statically known source, mark it available
679 VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
680 Integer srcTypeAlso =
681 vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed);
682 if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
683 notAvailSet.remove(refVarAlso);
695 private void codePlansForward(FlatMethod fm) {
697 // start from flat method top, visit every node in
698 // method exactly once
699 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
700 flatNodesToVisit.add(fm);
702 Set<FlatNode> visited = new HashSet<FlatNode>();
704 while (!flatNodesToVisit.isEmpty()) {
705 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
706 FlatNode fn = fnItr.next();
708 flatNodesToVisit.remove(fn);
711 Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
712 assert seseStack != null;
714 // use incoming results as "dot statement" or just
715 // before the current statement
716 VarSrcTokTable dotSTtable = new VarSrcTokTable();
717 for (int i = 0; i < fn.numPrev(); i++) {
718 FlatNode nn = fn.getPrev(i);
719 dotSTtable.merge(variableResults.get(nn));
722 // find dt-st notAvailableSet also
723 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
724 for (int i = 0; i < fn.numPrev(); i++) {
725 FlatNode nn = fn.getPrev(i);
726 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
727 if (notAvailIn != null) {
728 dotSTnotAvailSet.addAll(notAvailIn);
732 Set<TempDescriptor> dotSTlive = livenessRootView.get(fn);
734 if (!seseStack.empty()) {
735 codePlans_nodeActions(fn, dotSTlive, dotSTtable, dotSTnotAvailSet, seseStack.peek());
738 for (int i = 0; i < fn.numNext(); i++) {
739 FlatNode nn = fn.getNext(i);
741 if (!visited.contains(nn)) {
742 flatNodesToVisit.add(nn);
748 private void codePlans_nodeActions(FlatNode fn, Set<TempDescriptor> liveSetIn,
749 VarSrcTokTable vstTableIn, Set<TempDescriptor> notAvailSetIn, FlatSESEEnterNode currentSESE) {
751 CodePlan plan = new CodePlan(currentSESE);
755 case FKind.FlatSESEEnterNode: {
756 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
757 assert fsen.equals(currentSESE);
759 // track the source types of the in-var set so generated
760 // code at this SESE issue can compute the number of
761 // dependencies properly
762 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
763 while (inVarItr.hasNext()) {
764 TempDescriptor inVar = inVarItr.next();
766 // when we get to an SESE enter node we change the
767 // currentSESE variable of this analysis to the
768 // child that is declared by the enter node, so
769 // in order to classify in-vars correctly, pass
770 // the parent SESE in--at other FlatNode types just
771 // use the currentSESE
772 VSTWrapper vstIfStatic = new VSTWrapper();
773 Integer srcType = vstTableIn.getRefVarSrcType(inVar, fsen.getParent(), vstIfStatic);
775 // the current SESE needs a local space to track the dynamic
776 // variable and the child needs space in its SESE record
777 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
778 fsen.addDynamicInVar(inVar);
779 fsen.getParent().addDynamicVar(inVar);
781 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
782 fsen.addStaticInVar(inVar);
783 VariableSourceToken vst = vstIfStatic.vst;
784 fsen.putStaticInVar2src(inVar, vst);
785 fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
787 assert srcType.equals(VarSrcTokTable.SrcType_READY);
788 fsen.addReadyInVar(inVar);
795 case FKind.FlatSESEExitNode: {
796 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
800 case FKind.FlatOpNode: {
801 FlatOpNode fon = (FlatOpNode) fn;
803 if (fon.getOp().getOp() == Operation.ASSIGN) {
804 TempDescriptor lhs = fon.getDest();
805 TempDescriptor rhs = fon.getLeft();
807 // if this is an op node, don't stall, copy
808 // source and delay until we need to use value
810 // ask whether lhs and rhs sources are dynamic, static, etc.
811 VSTWrapper vstIfStatic = new VSTWrapper();
812 Integer lhsSrcType = vstTableIn.getRefVarSrcType(lhs, currentSESE, vstIfStatic);
813 Integer rhsSrcType = vstTableIn.getRefVarSrcType(rhs, currentSESE, vstIfStatic);
815 if (rhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
816 // if rhs is dynamic going in, lhs will definitely be dynamic
817 // going out of this node, so track that here
818 plan.addDynAssign(lhs, rhs);
819 currentSESE.addDynamicVar(lhs);
820 currentSESE.addDynamicVar(rhs);
822 } else if (lhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
823 // otherwise, if the lhs is dynamic, but the rhs is not, we
824 // need to update the variable's dynamic source as "current SESE"
825 plan.addDynAssign(lhs);
828 // only break if this is an ASSIGN op node,
829 // otherwise fall through to default case
834 // note that FlatOpNode's that aren't ASSIGN
835 // fall through to this default case
838 // a node with no live set has nothing to stall for
839 if (liveSetIn == null) {
843 TempDescriptor[] readarray = fn.readsTemps();
844 for (int i = 0; i < readarray.length; i++) {
845 TempDescriptor readtmp = readarray[i];
847 // ignore temps that are definitely available
848 // when considering to stall on it
849 if (!notAvailSetIn.contains(readtmp)) {
853 // check the source type of this variable
854 VSTWrapper vstIfStatic = new VSTWrapper();
855 Integer srcType = vstTableIn.getRefVarSrcType(readtmp, currentSESE, vstIfStatic);
857 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
858 // 1) It is not clear statically where this variable will
859 // come from, so dynamically we must keep track
860 // along various control paths, and therefore when we stall,
861 // just stall for the exact thing we need and move on
862 plan.addDynamicStall(readtmp);
863 currentSESE.addDynamicVar(readtmp);
865 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
866 // 2) Single token/age pair: Stall for token/age pair, and copy
867 // all live variables with same token/age pair at the same
868 // time. This is the same stuff that the notavaialable analysis
869 // marks as now available.
870 VariableSourceToken vst = vstIfStatic.vst;
872 Iterator<VariableSourceToken> availItr =
873 vstTableIn.get(vst.getSESE(), vst.getAge()).iterator();
875 while (availItr.hasNext()) {
876 VariableSourceToken vstAlsoAvail = availItr.next();
878 // only grab additional stuff that is live
879 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
881 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
882 while (refVarItr.hasNext()) {
883 TempDescriptor refVar = refVarItr.next();
884 if (liveSetIn.contains(refVar)) {
889 if (!copySet.isEmpty()) {
890 plan.addStall2CopySet(vstAlsoAvail, copySet);
895 // the other case for srcs is READY, so do nothing
898 // assert that everything being stalled for is in the
899 // "not available" set coming into this flat node and
900 // that every VST identified is in the possible "stall set"
901 // that represents VST's from children SESE's
909 // identify sese-age pairs that are statically useful
910 // and should have an associated SESE variable in code
911 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
912 // AND ALWAYS GIVE NAMES TO PARENTS
913 Set<VariableSourceToken> staticSet = vstTableIn.get();
914 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
915 while (vstItr.hasNext()) {
916 VariableSourceToken vst = vstItr.next();
918 // placeholder source tokens are useful results, but
919 // the placeholder static name is never needed
920 if (vst.getSESE().getIsCallerSESEplaceholder()) {
924 FlatSESEEnterNode sese = currentSESE;
925 while (sese != null) {
926 sese.addNeededStaticName(new SESEandAgePair(vst.getSESE(), vst.getAge()));
927 sese.mustTrackAtLeastAge(vst.getAge());
929 sese = sese.getParent();
933 codePlans.put(fn, plan);
935 // if any variables at this-node-*dot* have a static source (exactly one
937 // but go to a dynamic source at next-node-*dot*, create a new IR graph
938 // node on that edge to track the sources dynamically
939 VarSrcTokTable thisVstTable = variableResults.get(fn);
940 for (int i = 0; i < fn.numNext(); i++) {
941 FlatNode nn = fn.getNext(i);
942 VarSrcTokTable nextVstTable = variableResults.get(nn);
943 Set<TempDescriptor> nextLiveIn = livenessRootView.get(nn);
945 // the table can be null if it is one of the few IR nodes
946 // completely outside of the root SESE scope
947 if (nextVstTable != null && nextLiveIn != null) {
949 Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
950 thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, currentSESE);
952 if (!readyOrStatic2dynamicSet.isEmpty()) {
954 // either add these results to partial fixed-point result
955 // or make a new one if we haven't made any here yet
956 FlatEdge fe = new FlatEdge(fn, nn);
957 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe);
960 fwdvn = new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, currentSESE);
961 wdvNodesToSpliceIn.put(fe, fwdvn);
963 fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet);
970 private void makeConflictGraph(FlatMethod fm) {
972 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
973 flatNodesToVisit.add(fm);
975 Set<FlatNode> visited = new HashSet<FlatNode>();
977 while (!flatNodesToVisit.isEmpty()) {
978 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
979 flatNodesToVisit.remove(fn);
982 Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
983 assert seseStack != null;
985 if (!seseStack.isEmpty()) {
987 ConflictGraph conflictGraph = sese2conflictGraph.get(seseStack.peek());
988 if (conflictGraph == null) {
989 conflictGraph = new ConflictGraph();
992 conflictGraph_nodeAction(fn, seseStack.peek());
995 // schedule forward nodes for analysis
996 for (int i = 0; i < fn.numNext(); i++) {
997 FlatNode nn = fn.getNext(i);
998 if (!visited.contains(nn)) {
999 flatNodesToVisit.add(nn);
1007 private void conflictGraph_nodeAction(FlatNode fn, FlatSESEEnterNode currentSESE) {
1009 ConflictGraph conflictGraph;
1013 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1015 switch (fn.kind()) {
1017 case FKind.FlatSESEEnterNode: {
1019 if (currentSESE.getParent() == null) {
1022 conflictGraph = sese2conflictGraph.get(currentSESE.getParent());
1023 if (conflictGraph == null) {
1024 conflictGraph = new ConflictGraph();
1027 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
1029 if (!fsen.getIsCallerSESEplaceholder() && currentSESE.getParent() != null) {
1030 // collects effects set of invar set and generates invar node
1031 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(currentSESE);
1032 conflictGraph.addLiveIn(taint2Effects);
1035 if (conflictGraph.id2cn.size() > 0) {
1036 sese2conflictGraph.put(currentSESE.getParent(), conflictGraph);
1042 case FKind.FlatFieldNode:
1043 case FKind.FlatElementNode: {
1045 conflictGraph = sese2conflictGraph.get(currentSESE);
1046 if (conflictGraph == null) {
1047 conflictGraph = new ConflictGraph();
1050 if (fn instanceof FlatFieldNode) {
1051 FlatFieldNode ffn = (FlatFieldNode) fn;
1054 FlatElementNode fen = (FlatElementNode) fn;
1059 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1060 conflictGraph.addStallSite(taint2Effects, rhs);
1062 if (conflictGraph.id2cn.size() > 0) {
1063 sese2conflictGraph.put(currentSESE, conflictGraph);
1068 case FKind.FlatSetFieldNode:
1069 case FKind.FlatSetElementNode: {
1071 conflictGraph = sese2conflictGraph.get(currentSESE);
1072 if (conflictGraph == null) {
1073 conflictGraph = new ConflictGraph();
1076 if (fn instanceof FlatSetFieldNode) {
1077 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1078 lhs = fsfn.getDst();
1079 rhs = fsfn.getSrc();
1081 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1082 lhs = fsen.getDst();
1083 rhs = fsen.getSrc();
1086 // collects effects of stall site and generates stall site node
1087 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1088 conflictGraph.addStallSite(taint2Effects, rhs);
1089 conflictGraph.addStallSite(taint2Effects, lhs);
1091 if (conflictGraph.id2cn.size() > 0) {
1092 sese2conflictGraph.put(currentSESE, conflictGraph);
1097 case FKind.FlatCall: {
1098 conflictGraph = sese2conflictGraph.get(currentSESE);
1099 if (conflictGraph == null) {
1100 conflictGraph = new ConflictGraph();
1103 FlatCall fc = (FlatCall) fn;
1106 // collects effects of stall site and generates stall site node
1107 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1108 conflictGraph.addStallSite(taint2Effects, lhs);
1109 if (conflictGraph.id2cn.size() > 0) {
1110 sese2conflictGraph.put(currentSESE, conflictGraph);
1120 private void calculateConflicts(Set<FlatNew> sitesToFlag, boolean useReachInfo) {
1121 // decide fine-grain edge or coarse-grain edge among all vertexes by
1122 // pair-wise comparison
1123 Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
1124 while (seseIter.hasNext()) {
1125 FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next();
1126 ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
1128 // clear current conflict before recalculating with reachability info
1129 conflictGraph.clearAllConflictEdge();
1130 conflictGraph.setDisJointAnalysis(disjointAnalysisReach);
1131 conflictGraph.setFMEnclosing(sese.getfmEnclosing());
1133 conflictGraph.analyzeConflicts(sitesToFlag, useReachInfo);
1134 sese2conflictGraph.put(sese, conflictGraph);
1138 private void writeConflictGraph() {
1139 Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
1140 while (keyEnum.hasMoreElements()) {
1141 FlatNode key = (FlatNode) keyEnum.nextElement();
1142 ConflictGraph cg = sese2conflictGraph.get(key);
1144 if (cg.hasConflictEdge()) {
1145 cg.writeGraph("ConflictGraphFor" + key, false);
1147 } catch (IOException e) {
1148 System.out.println("Error writing");
1154 private void synthesizeLocks() {
1155 Set<Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
1156 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
1157 Entry<FlatNode, ConflictGraph> graphEntry = (Entry<FlatNode, ConflictGraph>) iterator.next();
1158 FlatNode sese = graphEntry.getKey();
1159 ConflictGraph conflictGraph = graphEntry.getValue();
1160 calculateCovering(conflictGraph);
1164 private void calculateCovering(ConflictGraph conflictGraph) {
1165 uniqueLockSetId = 0; // reset lock counter for every new conflict graph
1166 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1167 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1168 HashSet<SESELock> lockSet = new HashSet<SESELock>();
1170 Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1171 for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
1172 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1173 if (conflictEdge.isCoarseEdge()) {
1174 coarseToCover.add(conflictEdge);
1176 fineToCover.add(conflictEdge);
1180 HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
1181 toCover.addAll(fineToCover);
1182 toCover.addAll(coarseToCover);
1184 while (!toCover.isEmpty()) {
1186 SESELock seseLock = new SESELock();
1187 seseLock.setID(uniqueLockSetId++);
1191 do { // fine-grained edge
1195 for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) {
1198 ConflictEdge edge = (ConflictEdge) iterator.next();
1199 if (seseLock.getConflictNodeSet().size() == 0) {
1201 if (seseLock.isWriteNode(edge.getVertexU())) {
1202 // mark as fine_write
1203 if (edge.getVertexU().isStallSiteNode()) {
1204 type = ConflictNode.PARENT_WRITE;
1206 type = ConflictNode.FINE_WRITE;
1208 seseLock.addConflictNode(edge.getVertexU(), type);
1210 // mark as fine_read
1211 if (edge.getVertexU().isStallSiteNode()) {
1212 type = ConflictNode.PARENT_READ;
1214 type = ConflictNode.FINE_READ;
1216 seseLock.addConflictNode(edge.getVertexU(), type);
1218 if (edge.getVertexV() != edge.getVertexU()) {
1219 if (seseLock.isWriteNode(edge.getVertexV())) {
1220 // mark as fine_write
1221 if (edge.getVertexV().isStallSiteNode()) {
1222 type = ConflictNode.PARENT_WRITE;
1224 type = ConflictNode.FINE_WRITE;
1226 seseLock.addConflictNode(edge.getVertexV(), type);
1228 // mark as fine_read
1229 if (edge.getVertexV().isStallSiteNode()) {
1230 type = ConflictNode.PARENT_READ;
1232 type = ConflictNode.FINE_READ;
1234 seseLock.addConflictNode(edge.getVertexV(), type);
1238 seseLock.addConflictEdge(edge);
1239 fineToCover.remove(edge);
1240 break;// exit iterator loop
1241 }// end of initial setup
1243 ConflictNode newNode;
1244 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1245 // new node has a fine-grained edge to all current node
1246 // If there is a coarse grained edge where need a fine edge, it's
1247 // okay to add the node
1248 // but the edge must remain uncovered.
1252 if (seseLock.containsConflictNode(newNode)) {
1253 seseLock.addEdge(edge);
1254 fineToCover.remove(edge);
1258 if (seseLock.isWriteNode(newNode)) {
1259 if (newNode.isStallSiteNode()) {
1260 type = ConflictNode.PARENT_WRITE;
1262 type = ConflictNode.FINE_WRITE;
1264 seseLock.setNodeType(newNode, type);
1266 if (newNode.isStallSiteNode()) {
1267 type = ConflictNode.PARENT_READ;
1269 type = ConflictNode.FINE_READ;
1271 seseLock.setNodeType(newNode, type);
1274 seseLock.addEdge(edge);
1275 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1276 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1277 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1279 // mark all fine edges between new node and nodes in the group as
1281 if (!conflictEdge.getVertexU().equals(newNode)) {
1282 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1284 seseLock.addConflictEdge(conflictEdge);
1285 fineToCover.remove(conflictEdge);
1287 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1288 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1290 seseLock.addConflictEdge(conflictEdge);
1291 fineToCover.remove(conflictEdge);
1297 break;// exit iterator loop
1302 HashSet<ConflictEdge> notCovered=new HashSet<ConflictEdge>();
1306 for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) {
1308 ConflictEdge edge = (ConflictEdge) iterator.next();
1309 if (seseLock.getConflictNodeSet().size() == 0) {
1311 if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
1312 // node has a coarse-grained edge with itself
1313 if (!(edge.getVertexU().isStallSiteNode())) {
1314 // and it is not parent
1315 type = ConflictNode.SCC;
1317 type = ConflictNode.PARENT_WRITE;
1319 seseLock.addConflictNode(edge.getVertexU(), type);
1321 if (edge.getVertexU().isStallSiteNode()) {
1322 if (edge.getVertexU().getWriteEffectSet().isEmpty()) {
1323 type = ConflictNode.PARENT_READ;
1325 type = ConflictNode.PARENT_WRITE;
1328 type = ConflictNode.COARSE;
1330 seseLock.addConflictNode(edge.getVertexU(), type);
1332 if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
1333 // node has a coarse-grained edge with itself
1334 if (!(edge.getVertexV().isStallSiteNode())) {
1335 // and it is not parent
1336 type = ConflictNode.SCC;
1338 type = ConflictNode.PARENT_WRITE;
1340 seseLock.addConflictNode(edge.getVertexV(), type);
1342 if (edge.getVertexV().isStallSiteNode()) {
1343 if (edge.getVertexV().getWriteEffectSet().isEmpty()) {
1344 type = ConflictNode.PARENT_READ;
1346 type = ConflictNode.PARENT_WRITE;
1349 type = ConflictNode.COARSE;
1351 seseLock.addConflictNode(edge.getVertexV(), type);
1354 coarseToCover.remove(edge);
1355 seseLock.addConflictEdge(edge);
1356 break;// exit iterator loop
1357 }// end of initial setup
1359 ConflictNode newNode;
1360 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1361 // new node has a coarse-grained edge to all fine-read, fine-write,
1365 if (newNode.isInVarNode() && (!seseLock.hasSelfCoarseEdge(newNode))
1366 && seseLock.hasCoarseEdgeWithParentCoarse(newNode)) {
1367 // this case can't be covered by this queue
1368 coarseToCover.remove(edge);
1369 notCovered.add(edge);
1373 if (seseLock.containsConflictNode(newNode)) {
1374 seseLock.addEdge(edge);
1375 coarseToCover.remove(edge);
1379 if (seseLock.hasSelfCoarseEdge(newNode)) {
1381 if (newNode.isStallSiteNode()) {
1382 type = ConflictNode.PARENT_COARSE;
1384 type = ConflictNode.SCC;
1386 seseLock.setNodeType(newNode, type);
1388 if (newNode.isStallSiteNode()) {
1389 type = ConflictNode.PARENT_COARSE;
1391 type = ConflictNode.COARSE;
1393 seseLock.setNodeType(newNode, type);
1396 seseLock.addEdge(edge);
1397 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1398 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1399 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1400 // mark all coarse edges between new node and nodes in the group
1402 if (!conflictEdge.getVertexU().equals(newNode)) {
1403 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1405 seseLock.addConflictEdge(conflictEdge);
1406 coarseToCover.remove(conflictEdge);
1408 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1409 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1411 seseLock.addConflictEdge(conflictEdge);
1412 coarseToCover.remove(conflictEdge);
1417 break;// exit iterator loop
1423 lockSet.add(seseLock);
1426 coarseToCover.addAll(notCovered);
1427 toCover.addAll(fineToCover);
1428 toCover.addAll(coarseToCover);
1432 conflictGraph2SESELock.put(conflictGraph, lockSet);
1435 public ConflictGraph getConflictGraph(FlatNode sese) {
1436 return sese2conflictGraph.get(sese);
1439 public Set<SESELock> getLockMappings(ConflictGraph graph) {
1440 return conflictGraph2SESELock.get(graph);
1443 public Set<FlatSESEEnterNode> getAllSESEs() {
1444 return rblockRel.getAllSESEs();
1447 public FlatSESEEnterNode getMainSESE() {
1448 return rblockRel.getMainSESE();
1451 public void writeReports(String timeReport) throws java.io.IOException {
1453 BufferedWriter bw = new BufferedWriter(new FileWriter("mlpReport_summary.txt"));
1454 bw.write("MLP Analysis Results\n\n");
1455 bw.write(timeReport + "\n\n");
1456 printSESEHierarchy(bw);
1461 Iterator<Descriptor> methItr = disjointAnalysisTaints.getDescriptorsToAnalyze().iterator();
1462 while (methItr.hasNext()) {
1463 MethodDescriptor md = (MethodDescriptor) methItr.next();
1464 FlatMethod fm = state.getMethodFlat(md);
1467 new BufferedWriter(new FileWriter("mlpReport_" + md.getClassMethodName()
1468 + md.getSafeMethodDescriptor() + ".txt"));
1469 bw.write("MLP Results for " + md + "\n-------------------\n");
1471 FlatSESEEnterNode implicitSESE = (FlatSESEEnterNode) fm.getNext(0);
1472 if (!implicitSESE.getIsCallerSESEplaceholder() && implicitSESE != rblockRel.getMainSESE()) {
1473 System.out.println(implicitSESE + " is not implicit?!");
1476 bw.write("Dynamic vars to manage:\n " + implicitSESE.getDynamicVarSet());
1478 bw.write("\n\nLive-In, Root View\n------------------\n" + fm.printMethod(livenessRootView));
1479 bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults));
1480 bw.write("\n\nNot Available Results-Out\n---------------------\n"
1481 + fm.printMethod(notAvailableResults));
1482 bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans));
1488 private void printSESEHierarchy(BufferedWriter bw) throws java.io.IOException {
1489 bw.write("SESE Hierarchy\n--------------\n");
1490 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getRootSESEs().iterator();
1491 while (rootItr.hasNext()) {
1492 FlatSESEEnterNode root = rootItr.next();
1493 if (root.getIsCallerSESEplaceholder()) {
1494 if (!root.getChildren().isEmpty()) {
1495 printSESEHierarchyTree(bw, root, 0);
1498 printSESEHierarchyTree(bw, root, 0);
1503 private void printSESEHierarchyTree(BufferedWriter bw, FlatSESEEnterNode fsen, int depth)
1504 throws java.io.IOException {
1505 for (int i = 0; i < depth; ++i) {
1508 bw.write("- " + fsen.getPrettyIdentifier() + "\n");
1510 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
1511 while (childItr.hasNext()) {
1512 FlatSESEEnterNode fsenChild = childItr.next();
1513 printSESEHierarchyTree(bw, fsenChild, depth + 1);
1517 private void printSESEInfo(BufferedWriter bw) throws java.io.IOException {
1518 bw.write("\nSESE info\n-------------\n");
1519 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getRootSESEs().iterator();
1520 while (rootItr.hasNext()) {
1521 FlatSESEEnterNode root = rootItr.next();
1522 if (root.getIsCallerSESEplaceholder()) {
1523 if (!root.getChildren().isEmpty()) {
1524 printSESEInfoTree(bw, root);
1527 printSESEInfoTree(bw, root);
1532 public DisjointAnalysis getDisjointAnalysis() {
1533 return disjointAnalysisTaints;
1536 private void printSESEInfoTree(BufferedWriter bw, FlatSESEEnterNode fsen)
1537 throws java.io.IOException {
1539 if (!fsen.getIsCallerSESEplaceholder()) {
1540 bw.write("SESE " + fsen.getPrettyIdentifier());
1541 if( fsen.getIsLeafSESE() ) {
1542 bw.write(" (leaf)");
1546 bw.write(" in-set: " + fsen.getInVarSet() + "\n");
1547 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1548 while (tItr.hasNext()) {
1549 TempDescriptor inVar = tItr.next();
1550 if (fsen.getReadyInVarSet().contains(inVar)) {
1551 bw.write(" (ready) " + inVar + "\n");
1553 if (fsen.getStaticInVarSet().contains(inVar)) {
1554 bw.write(" (static) " + inVar + " from " + fsen.getStaticInVarSrc(inVar) + "\n");
1556 if (fsen.getDynamicInVarSet().contains(inVar)) {
1557 bw.write(" (dynamic)" + inVar + "\n");
1561 bw.write(" Dynamic vars to manage: " + fsen.getDynamicVarSet() + "\n");
1563 bw.write(" out-set: " + fsen.getOutVarSet() + "\n");
1567 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
1568 while (childItr.hasNext()) {
1569 FlatSESEEnterNode fsenChild = childItr.next();
1570 printSESEInfoTree(bw, fsenChild);