1 package Analysis.OoOJava;
3 import java.io.IOException;
4 import java.util.Enumeration;
5 import java.util.HashSet;
6 import java.util.Hashtable;
7 import java.util.Iterator;
9 import java.util.Stack;
10 import java.util.Map.Entry;
12 import Analysis.ArrayReferencees;
13 import Analysis.Liveness;
14 import Analysis.CallGraph.CallGraph;
15 import Analysis.Disjoint.DisjointAnalysis;
16 import Analysis.Disjoint.Effect;
17 import Analysis.Disjoint.EffectsAnalysis;
18 import Analysis.Disjoint.Taint;
20 import IR.MethodDescriptor;
25 import IR.Flat.FlatEdge;
26 import IR.Flat.FlatFieldNode;
27 import IR.Flat.FlatMethod;
28 import IR.Flat.FlatNode;
29 import IR.Flat.FlatOpNode;
30 import IR.Flat.FlatNew;
31 import IR.Flat.FlatSESEEnterNode;
32 import IR.Flat.FlatSESEExitNode;
33 import IR.Flat.FlatSetFieldNode;
34 import IR.Flat.FlatWriteDynamicVarNode;
35 import IR.Flat.TempDescriptor;
37 public class OoOJavaAnalysis {
39 // data from the compiler
41 private TypeUtil typeUtil;
42 private CallGraph callGraph;
43 private RBlockRelationAnalysis rblockRel;
44 private RBlockStatusAnalysis rblockStatus;
45 private DisjointAnalysis disjointAnalysisTaints;
46 private DisjointAnalysis disjointAnalysisReach;
48 private Hashtable<FlatNode, Set<TempDescriptor>> livenessRootView;
49 private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
50 private Hashtable<FlatNode, VarSrcTokTable> variableResults;
51 private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
52 private Hashtable<FlatNode, CodePlan> codePlans;
54 private Hashtable<FlatSESEEnterNode, Set<TempDescriptor>> notAvailableIntoSESE;
56 private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
58 // temporal data structures to track analysis progress.
59 static private int uniqueLockSetId = 0;
60 // mapping of a conflict graph to its compiled lock
61 private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraph2SESELock;
62 // mapping of a sese block to its conflict graph
63 private Hashtable<FlatNode, ConflictGraph> sese2conflictGraph;
68 // private Hashtable<FlatNode, ParentChildConflictsMap> conflictsResults;
69 // private Hashtable<FlatMethod, MethodSummary> methodSummaryResults;
70 // private OwnershipAnalysis ownAnalysisForSESEConflicts;
72 // static private int uniqueLockSetId = 0;
74 public static int maxSESEage = -1;
76 public int getMaxSESEage() {
81 public CodePlan getCodePlan(FlatNode fn) {
82 CodePlan cp = codePlans.get(fn);
86 public OoOJavaAnalysis(State state, TypeUtil typeUtil, CallGraph callGraph, Liveness liveness,
87 ArrayReferencees arrayReferencees) {
89 double timeStartAnalysis = (double) System.nanoTime();
92 this.typeUtil = typeUtil;
93 this.callGraph = callGraph;
94 this.maxSESEage = state.MLP_MAXSESEAGE;
96 livenessRootView = new Hashtable<FlatNode, Set<TempDescriptor>>();
97 livenessVirtualReads = new Hashtable<FlatNode, Set<TempDescriptor>>();
98 variableResults = new Hashtable<FlatNode, VarSrcTokTable>();
99 notAvailableResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
100 codePlans = new Hashtable<FlatNode, CodePlan>();
101 wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
103 notAvailableIntoSESE = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
105 sese2conflictGraph = new Hashtable<FlatNode, ConflictGraph>();
106 conflictGraph2SESELock = new Hashtable<ConflictGraph, HashSet<SESELock>>();
108 // add all methods transitively reachable from the
109 // source's main to set for analysis
110 MethodDescriptor mdSourceEntry = typeUtil.getMain();
111 FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
113 Set<MethodDescriptor> descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
115 descriptorsToAnalyze.add(mdSourceEntry);
117 // conflictsResults = new Hashtable<FlatNode, ParentChildConflictsMap>();
118 // methodSummaryResults = new Hashtable<FlatMethod, MethodSummary>();
119 // conflictGraphResults = new Hashtable<FlatNode, ConflictGraph>();
121 // seseSummaryMap = new Hashtable<FlatNode, SESESummary>();
122 // isAfterChildSESEIndicatorMap = new Hashtable<FlatNode, Boolean>();
123 // conflictGraphLockMap = new Hashtable<ConflictGraph, HashSet<SESELock>>();
125 // 1st pass, find basic rblock relations
126 rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
128 rblockStatus = new RBlockStatusAnalysis(state, typeUtil, callGraph, rblockRel);
131 // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
132 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getRootSESEs().iterator();
133 while (rootItr.hasNext()) {
134 FlatSESEEnterNode root = rootItr.next();
135 livenessAnalysisBackward(root, true, null);
138 // 3rd pass, variable analysis
139 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
140 while (methItr.hasNext()) {
141 Descriptor d = methItr.next();
142 FlatMethod fm = state.getMethodFlat(d);
144 // starting from roots do a forward, fixed-point
145 // variable analysis for refinement and stalls
146 variableAnalysisForward(fm);
149 // 4th pass, compute liveness contribution from
150 // virtual reads discovered in variable pass
151 rootItr = rblockRel.getRootSESEs().iterator();
152 while (rootItr.hasNext()) {
153 FlatSESEEnterNode root = rootItr.next();
154 livenessAnalysisBackward(root, true, null);
157 // 5th pass, use disjointness with NO FLAGGED REGIONS
158 // to compute taints and effects
159 disjointAnalysisTaints =
160 new DisjointAnalysis(state,
165 null, // no FlatNew set to flag
170 // 6th pass, not available analysis FOR VARIABLES!
171 methItr = descriptorsToAnalyze.iterator();
172 while (methItr.hasNext()) {
173 Descriptor d = methItr.next();
174 FlatMethod fm = state.getMethodFlat(d);
176 // compute what is not available at every program
177 // point, in a forward fixed-point pass
178 notAvailableForward(fm);
181 // 7th pass, make conflict graph
182 // conflict graph is maintained by each parent sese,
183 // and while making the graph identify set of FlatNew
184 // that next disjoint reach. analysis should flag
185 Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
187 methItr = descriptorsToAnalyze.iterator();
188 while (methItr.hasNext()) {
189 Descriptor d = methItr.next();
190 FlatMethod fm = state.getMethodFlat(d);
191 makeConflictGraph(fm, sitesToFlag);
195 Iterator iter = sese2conflictGraph.entrySet().iterator();
196 while (iter.hasNext()) {
197 Entry e = (Entry) iter.next();
198 FlatNode fn = (FlatNode) e.getKey();
199 ConflictGraph conflictGraph = (ConflictGraph) e.getValue();
200 System.out.println("CONFLICT GRAPH for " + fn);
201 Set<String> keySet = conflictGraph.id2cn.keySet();
202 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
203 String key = (String) iterator.next();
204 ConflictNode node = conflictGraph.id2cn.get(key);
205 System.out.println("key=" + key + " --\n" + node.toString());
209 // 8th pass, ask disjoint analysis to compute reachability
210 // for objects that may cause heap conflicts so the most
211 // efficient method to deal with conflict can be computed
213 disjointAnalysisReach =
214 new DisjointAnalysis(state,
220 null, // don't do effects analysis again!
221 null // don't do effects analysis again!
224 // 9th pass, calculate conflicts
225 //calculateConflicts();
228 // #th pass, compiling locks
231 // #th pass, writing conflict graph
232 writeConflictGraph();
237 private void livenessAnalysisBackward(FlatSESEEnterNode fsen, boolean toplevel,
238 Hashtable<FlatSESEExitNode, Set<TempDescriptor>> liveout) {
240 // start from an SESE exit, visit nodes in reverse up to
241 // SESE enter in a fixed-point scheme, where children SESEs
242 // should already be analyzed and therefore can be skipped
243 // because child SESE enter node has all necessary info
244 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
247 flatNodesToVisit.add(fsen.getfmEnclosing().getFlatExit());
249 flatNodesToVisit.add(fsen.getFlatExit());
252 Hashtable<FlatNode, Set<TempDescriptor>> livenessResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
255 liveout = new Hashtable<FlatSESEExitNode, Set<TempDescriptor>>();
258 while (!flatNodesToVisit.isEmpty()) {
259 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
260 flatNodesToVisit.remove(fn);
262 Set<TempDescriptor> prev = livenessResults.get(fn);
264 // merge sets from control flow joins
265 Set<TempDescriptor> u = new HashSet<TempDescriptor>();
266 for (int i = 0; i < fn.numNext(); i++) {
267 FlatNode nn = fn.getNext(i);
268 Set<TempDescriptor> s = livenessResults.get(nn);
274 Set<TempDescriptor> curr = liveness_nodeActions(fn, u, fsen, toplevel, liveout);
276 // if a new result, schedule backward nodes for analysis
277 if (!curr.equals(prev)) {
278 livenessResults.put(fn, curr);
280 // don't flow backwards past current SESE enter
281 if (!fn.equals(fsen)) {
282 for (int i = 0; i < fn.numPrev(); i++) {
283 FlatNode nn = fn.getPrev(i);
284 flatNodesToVisit.add(nn);
290 Set<TempDescriptor> s = livenessResults.get(fsen);
295 // remember liveness per node from the root view as the
296 // global liveness of variables for later passes to use
298 livenessRootView.putAll(livenessResults);
301 // post-order traversal, so do children first
302 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
303 while (childItr.hasNext()) {
304 FlatSESEEnterNode fsenChild = childItr.next();
305 livenessAnalysisBackward(fsenChild, false, liveout);
309 private Set<TempDescriptor> liveness_nodeActions(FlatNode fn, Set<TempDescriptor> liveIn,
310 FlatSESEEnterNode currentSESE, boolean toplevel,
311 Hashtable<FlatSESEExitNode, Set<TempDescriptor>> liveout) {
314 case FKind.FlatSESEExitNode:
316 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
317 if (!liveout.containsKey(fsexn)) {
318 liveout.put(fsexn, new HashSet<TempDescriptor>());
320 liveout.get(fsexn).addAll(liveIn);
322 // no break, sese exits should also execute default actions
325 // handle effects of statement in reverse, writes then reads
326 TempDescriptor[] writeTemps = fn.writesTemps();
327 for (int i = 0; i < writeTemps.length; ++i) {
328 liveIn.remove(writeTemps[i]);
331 FlatSESEExitNode fsexn = currentSESE.getFlatExit();
332 Set<TempDescriptor> livetemps = liveout.get(fsexn);
333 if (livetemps != null && livetemps.contains(writeTemps[i])) {
334 // write to a live out temp...
335 // need to put in SESE liveout set
336 currentSESE.addOutVar(writeTemps[i]);
341 TempDescriptor[] readTemps = fn.readsTemps();
342 for (int i = 0; i < readTemps.length; ++i) {
343 liveIn.add(readTemps[i]);
346 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get(fn);
347 if (virtualReadTemps != null) {
348 liveIn.addAll(virtualReadTemps);
359 private void variableAnalysisForward(FlatMethod fm) {
361 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
362 flatNodesToVisit.add(fm);
364 while (!flatNodesToVisit.isEmpty()) {
365 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
366 flatNodesToVisit.remove(fn);
368 Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
369 assert seseStack != null;
371 VarSrcTokTable prev = variableResults.get(fn);
373 // merge sets from control flow joins
374 VarSrcTokTable curr = new VarSrcTokTable();
375 for (int i = 0; i < fn.numPrev(); i++) {
376 FlatNode nn = fn.getPrev(i);
377 VarSrcTokTable incoming = variableResults.get(nn);
378 curr.merge(incoming);
381 if (!seseStack.empty()) {
382 variable_nodeActions(fn, curr, seseStack.peek());
385 // if a new result, schedule forward nodes for analysis
386 if (!curr.equals(prev)) {
387 variableResults.put(fn, curr);
389 for (int i = 0; i < fn.numNext(); i++) {
390 FlatNode nn = fn.getNext(i);
391 flatNodesToVisit.add(nn);
397 private void variable_nodeActions(FlatNode fn, VarSrcTokTable vstTable,
398 FlatSESEEnterNode currentSESE) {
401 case FKind.FlatSESEEnterNode: {
402 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
403 assert fsen.equals(currentSESE);
405 vstTable.age(currentSESE);
406 vstTable.assertConsistency();
410 case FKind.FlatSESEExitNode: {
411 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
412 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
413 assert currentSESE.getChildren().contains(fsen);
415 // remap all of this child's children tokens to be
416 // from this child as the child exits
417 vstTable.remapChildTokens(fsen);
419 // liveness virtual reads are things that might be
420 // written by an SESE and should be added to the in-set
421 // anything virtually read by this SESE should be pruned
422 // of parent or sibling sources
423 Set<TempDescriptor> liveVars = livenessRootView.get(fn);
424 Set<TempDescriptor> fsenVirtReads = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(
426 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
427 if (fsenVirtReadsOld != null) {
428 fsenVirtReads.addAll(fsenVirtReadsOld);
430 livenessVirtualReads.put(fn, fsenVirtReads);
432 // then all child out-set tokens are guaranteed
433 // to be filled in, so clobber those entries with
434 // the latest, clean sources
435 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
436 while (outVarItr.hasNext()) {
437 TempDescriptor outVar = outVarItr.next();
438 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
440 VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
441 vstTable.remove(outVar);
444 vstTable.assertConsistency();
449 case FKind.FlatOpNode: {
450 FlatOpNode fon = (FlatOpNode) fn;
452 if (fon.getOp().getOp() == Operation.ASSIGN) {
453 TempDescriptor lhs = fon.getDest();
454 TempDescriptor rhs = fon.getLeft();
456 vstTable.remove(lhs);
458 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
460 Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
461 while (itr.hasNext()) {
462 VariableSourceToken vst = itr.next();
464 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
467 if (currentSESE.getChildren().contains(vst.getSESE())) {
468 // if the source comes from a child, copy it over
469 forAddition.add(new VariableSourceToken(ts, vst.getSESE(), vst.getAge(), vst
472 // otherwise, stamp it as us as the source
473 forAddition.add(new VariableSourceToken(ts, currentSESE, new Integer(0), lhs));
477 vstTable.addAll(forAddition);
479 // only break if this is an ASSIGN op node,
480 // otherwise fall through to default case
481 vstTable.assertConsistency();
486 // note that FlatOpNode's that aren't ASSIGN
487 // fall through to this default case
489 TempDescriptor[] writeTemps = fn.writesTemps();
490 if (writeTemps.length > 0) {
492 // for now, when writeTemps > 1, make sure
493 // its a call node, programmer enforce only
494 // doing stuff like calling a print routine
495 // assert writeTemps.length == 1;
496 if (writeTemps.length > 1) {
497 assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
501 vstTable.remove(writeTemps[0]);
503 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
504 ts.add(writeTemps[0]);
506 vstTable.add(new VariableSourceToken(ts, currentSESE, new Integer(0), writeTemps[0]));
509 vstTable.assertConsistency();
516 private void notAvailableForward(FlatMethod fm) {
518 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
519 flatNodesToVisit.add(fm);
521 while (!flatNodesToVisit.isEmpty()) {
522 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
523 flatNodesToVisit.remove(fn);
525 Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
526 assert seseStack != null;
528 Set<TempDescriptor> prev = notAvailableResults.get(fn);
530 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
531 for (int i = 0; i < fn.numPrev(); i++) {
532 FlatNode nn = fn.getPrev(i);
533 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
534 if (notAvailIn != null) {
535 curr.addAll(notAvailIn);
539 if (!seseStack.empty()) {
540 notAvailable_nodeActions(fn, curr, seseStack.peek());
543 // if a new result, schedule forward nodes for analysis
544 if (!curr.equals(prev)) {
545 notAvailableResults.put(fn, curr);
547 for (int i = 0; i < fn.numNext(); i++) {
548 FlatNode nn = fn.getNext(i);
549 flatNodesToVisit.add(nn);
555 private void notAvailable_nodeActions(FlatNode fn, Set<TempDescriptor> notAvailSet,
556 FlatSESEEnterNode currentSESE) {
558 // any temps that are removed from the not available set
559 // at this node should be marked in this node's code plan
560 // as temps to be grabbed at runtime!
564 case FKind.FlatSESEEnterNode: {
565 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
566 assert fsen.equals(currentSESE);
568 // keep a copy of what's not available into the SESE
569 // and restore it at the matching exit node
570 Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
571 Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
572 while (tdItr.hasNext()) {
573 notAvailCopy.add(tdItr.next());
575 notAvailableIntoSESE.put(fsen, notAvailCopy);
581 case FKind.FlatSESEExitNode: {
582 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
583 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
584 assert currentSESE.getChildren().contains(fsen);
586 notAvailSet.addAll(fsen.getOutVarSet());
588 Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
589 assert notAvailIn != null;
590 notAvailSet.addAll(notAvailIn);
595 case FKind.FlatMethod: {
599 case FKind.FlatOpNode: {
600 FlatOpNode fon = (FlatOpNode) fn;
602 if (fon.getOp().getOp() == Operation.ASSIGN) {
603 TempDescriptor lhs = fon.getDest();
604 TempDescriptor rhs = fon.getLeft();
606 // copy makes lhs same availability as rhs
607 if (notAvailSet.contains(rhs)) {
608 notAvailSet.add(lhs);
610 notAvailSet.remove(lhs);
613 // only break if this is an ASSIGN op node,
614 // otherwise fall through to default case
619 // note that FlatOpNode's that aren't ASSIGN
620 // fall through to this default case
622 TempDescriptor[] writeTemps = fn.writesTemps();
623 for (int i = 0; i < writeTemps.length; i++) {
624 TempDescriptor wTemp = writeTemps[i];
625 notAvailSet.remove(wTemp);
627 TempDescriptor[] readTemps = fn.readsTemps();
628 for (int i = 0; i < readTemps.length; i++) {
629 TempDescriptor rTemp = readTemps[i];
630 notAvailSet.remove(rTemp);
632 // if this variable has exactly one source, potentially
633 // get other things from this source as well
634 VarSrcTokTable vstTable = variableResults.get(fn);
636 VSTWrapper vstIfStatic = new VSTWrapper();
637 Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
639 if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
641 VariableSourceToken vst = vstIfStatic.vst;
643 Iterator<VariableSourceToken> availItr = vstTable.get(vst.getSESE(), vst.getAge())
646 // look through things that are also available from same source
647 while (availItr.hasNext()) {
648 VariableSourceToken vstAlsoAvail = availItr.next();
650 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
651 while (refVarItr.hasNext()) {
652 TempDescriptor refVarAlso = refVarItr.next();
654 // if a variable is available from the same source, AND it ALSO
655 // only comes from one statically known source, mark it available
656 VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
657 Integer srcTypeAlso = vstTable.getRefVarSrcType(refVarAlso, currentSESE,
659 if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
660 notAvailSet.remove(refVarAlso);
672 private void makeConflictGraph(FlatMethod fm, Set<FlatNew> sitesToFlag) {
674 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
675 flatNodesToVisit.add(fm);
677 Set<FlatNode> visited = new HashSet<FlatNode>();
679 while (!flatNodesToVisit.isEmpty()) {
680 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
681 flatNodesToVisit.remove(fn);
684 Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
685 assert seseStack != null;
687 if (!seseStack.isEmpty()) {
689 ConflictGraph conflictGraph = sese2conflictGraph.get(seseStack.peek());
690 if (conflictGraph == null) {
691 conflictGraph = new ConflictGraph();
694 conflictGraph_nodeAction(fn, seseStack.peek(), sitesToFlag);
697 // schedule forward nodes for analysis
698 for (int i = 0; i < fn.numNext(); i++) {
699 FlatNode nn = fn.getNext(i);
700 if (!visited.contains(nn)) {
701 flatNodesToVisit.add(nn);
710 private void conflictGraph_nodeAction(FlatNode fn, FlatSESEEnterNode currentSESE, Set<FlatNew> sitesToFlag) {
712 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
713 ConflictGraph conflictGraph = sese2conflictGraph.get(currentSESE.getParent());
714 if (conflictGraph == null) {
715 conflictGraph = new ConflictGraph();
720 case FKind.FlatSESEEnterNode: {
722 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
724 if (!fsen.getIsCallerSESEplaceholder() && currentSESE.getParent() != null) {
725 // collects effects set of invar set and generates invar node
726 Hashtable<Taint, Set<Effect>> taint2Effects=effectsAnalysis.get(currentSESE);
727 conflictGraph.addLiveIn(taint2Effects);
732 case FKind.FlatFieldNode:
733 case FKind.FlatElementNode: {
735 FlatFieldNode ffn = (FlatFieldNode) fn;
736 TempDescriptor rhs = ffn.getSrc();
739 //Hashtable<Taint, Set<Effect>> taint2Effects=effectsAnalysis.get(fn, rhs);
740 //conflictGraph.addStallSite(taint2Effects);
745 case FKind.FlatSetFieldNode:
746 case FKind.FlatSetElementNode: {
748 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
749 TempDescriptor lhs = fsfn.getDst();
750 TempDescriptor rhs = fsfn.getSrc();
752 // collects effects of stall site and generates stall site node
753 //Hashtable<Taint, Set<Effect>> taint2Effects=effectsAnalysis.get(fn, rhs);
754 //conflictGraph.addStallSite(taint2Effects);
756 //taint2Effects=effectsAnalysis.get(fn, lhs);
757 //conflictGraph.addStallSite(taint2Effects);
763 if (conflictGraph.id2cn.size() > 0) {
764 sese2conflictGraph.put(currentSESE.getParent(), conflictGraph);
769 private void calculateConflicts() {
770 // decide fine-grain edge or coarse-grain edge among all vertexes by
771 // pair-wise comparison
773 Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
774 while (seseIter.hasNext()) {
775 FlatNode sese = seseIter.next();
776 ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
777 conflictGraph.analyzeConflicts();
778 sese2conflictGraph.put(sese, conflictGraph);
782 private void writeConflictGraph() {
783 Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
784 while (keyEnum.hasMoreElements()) {
785 FlatNode key = (FlatNode) keyEnum.nextElement();
786 ConflictGraph cg = sese2conflictGraph.get(key);
788 if (cg.hasConflictEdge()) {
789 cg.writeGraph("ConflictGraphFor" + key, false);
791 } catch (IOException e) {
792 System.out.println("Error writing");
798 private void synthesizeLocks() {
799 Set<Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
800 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
801 Entry<FlatNode, ConflictGraph> graphEntry = (Entry<FlatNode, ConflictGraph>) iterator.next();
802 FlatNode sese = graphEntry.getKey();
803 ConflictGraph conflictGraph = graphEntry.getValue();
804 calculateCovering(conflictGraph);
808 private void calculateCovering(ConflictGraph conflictGraph) {
809 uniqueLockSetId = 0; // reset lock counter for every new conflict graph
810 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
811 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
812 HashSet<SESELock> lockSet = new HashSet<SESELock>();
814 Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
815 for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
816 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
817 if (conflictEdge.isCoarseEdge()) {
818 coarseToCover.add(conflictEdge);
820 fineToCover.add(conflictEdge);
824 HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
825 toCover.addAll(fineToCover);
826 toCover.addAll(coarseToCover);
828 while (!toCover.isEmpty()) {
830 SESELock seseLock = new SESELock();
831 seseLock.setID(uniqueLockSetId++);
835 do { // fine-grained edge
839 for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) {
842 ConflictEdge edge = (ConflictEdge) iterator.next();
843 if (seseLock.getConflictNodeSet().size() == 0) {
845 if (seseLock.isWriteNode(edge.getVertexU())) {
846 // mark as fine_write
847 if (edge.getVertexU().isStallSiteNode()) {
848 type = ConflictNode.PARENT_WRITE;
850 type = ConflictNode.FINE_WRITE;
852 seseLock.addConflictNode(edge.getVertexU(), type);
855 if (edge.getVertexU().isStallSiteNode()) {
856 type = ConflictNode.PARENT_READ;
858 type = ConflictNode.FINE_READ;
860 seseLock.addConflictNode(edge.getVertexU(), type);
862 if (edge.getVertexV() != edge.getVertexU()) {
863 if (seseLock.isWriteNode(edge.getVertexV())) {
864 // mark as fine_write
865 if (edge.getVertexV().isStallSiteNode()) {
866 type = ConflictNode.PARENT_WRITE;
868 type = ConflictNode.FINE_WRITE;
870 seseLock.addConflictNode(edge.getVertexV(), type);
873 if (edge.getVertexV().isStallSiteNode()) {
874 type = ConflictNode.PARENT_READ;
876 type = ConflictNode.FINE_READ;
878 seseLock.addConflictNode(edge.getVertexV(), type);
882 seseLock.addConflictEdge(edge);
883 fineToCover.remove(edge);
884 break;// exit iterator loop
885 }// end of initial setup
887 ConflictNode newNode;
888 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
889 // new node has a fine-grained edge to all current node
890 // If there is a coarse grained edge where need a fine edge, it's
891 // okay to add the node
892 // but the edge must remain uncovered.
896 if (seseLock.isWriteNode(newNode)) {
897 if (newNode.isStallSiteNode()) {
898 type = ConflictNode.PARENT_WRITE;
900 type = ConflictNode.FINE_WRITE;
902 seseLock.setNodeType(newNode, type);
904 if (newNode.isStallSiteNode()) {
905 type = ConflictNode.PARENT_READ;
907 type = ConflictNode.FINE_READ;
909 seseLock.setNodeType(newNode, type);
912 seseLock.addEdge(edge);
913 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
914 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
915 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
917 // mark all fine edges between new node and nodes in the group as
919 if (!conflictEdge.getVertexU().equals(newNode)) {
920 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
922 seseLock.addConflictEdge(conflictEdge);
923 fineToCover.remove(conflictEdge);
925 } else if (!conflictEdge.getVertexV().equals(newNode)) {
926 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
928 seseLock.addConflictEdge(conflictEdge);
929 fineToCover.remove(conflictEdge);
935 break;// exit iterator loop
943 for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) {
945 ConflictEdge edge = (ConflictEdge) iterator.next();
947 if (seseLock.getConflictNodeSet().size() == 0) {
949 if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
950 // node has a coarse-grained edge with itself
951 if (!(edge.getVertexU().isStallSiteNode())) {
952 // and it is not parent
953 type = ConflictNode.SCC;
955 type = ConflictNode.PARENT_COARSE;
957 seseLock.addConflictNode(edge.getVertexU(), type);
959 if (edge.getVertexU().isStallSiteNode()) {
960 type = ConflictNode.PARENT_COARSE;
962 type = ConflictNode.COARSE;
964 seseLock.addConflictNode(edge.getVertexU(), type);
966 if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
967 // node has a coarse-grained edge with itself
968 if (!(edge.getVertexV().isStallSiteNode())) {
969 // and it is not parent
970 type = ConflictNode.SCC;
972 type = ConflictNode.PARENT_COARSE;
974 seseLock.addConflictNode(edge.getVertexV(), type);
976 if (edge.getVertexV().isStallSiteNode()) {
977 type = ConflictNode.PARENT_COARSE;
979 type = ConflictNode.COARSE;
981 seseLock.addConflictNode(edge.getVertexV(), type);
984 coarseToCover.remove(edge);
985 seseLock.addConflictEdge(edge);
986 break;// exit iterator loop
987 }// end of initial setup
989 ConflictNode newNode;
990 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
991 // new node has a coarse-grained edge to all fine-read, fine-write,
995 if (seseLock.hasSelfCoarseEdge(newNode)) {
997 if (newNode.isStallSiteNode()) {
998 type = ConflictNode.PARENT_COARSE;
1000 type = ConflictNode.SCC;
1002 seseLock.setNodeType(newNode, type);
1004 if (newNode.isStallSiteNode()) {
1005 type = ConflictNode.PARENT_COARSE;
1007 type = ConflictNode.COARSE;
1009 seseLock.setNodeType(newNode, type);
1012 seseLock.addEdge(edge);
1013 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1014 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1015 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1016 // mark all coarse edges between new node and nodes in the group
1018 if (!conflictEdge.getVertexU().equals(newNode)) {
1019 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1021 seseLock.addConflictEdge(conflictEdge);
1022 coarseToCover.remove(conflictEdge);
1024 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1025 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1027 seseLock.addConflictEdge(conflictEdge);
1028 coarseToCover.remove(conflictEdge);
1033 break;// exit iterator loop
1039 lockSet.add(seseLock);
1042 toCover.addAll(fineToCover);
1043 toCover.addAll(coarseToCover);
1047 conflictGraph2SESELock.put(conflictGraph, lockSet);