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;
23 import IR.MethodDescriptor;
28 import IR.Flat.FlatCall;
29 import IR.Flat.FlatEdge;
30 import IR.Flat.FlatElementNode;
31 import IR.Flat.FlatFieldNode;
32 import IR.Flat.FlatMethod;
33 import IR.Flat.FlatNew;
34 import IR.Flat.FlatNode;
35 import IR.Flat.FlatOpNode;
36 import IR.Flat.FlatSESEEnterNode;
37 import IR.Flat.FlatSESEExitNode;
38 import IR.Flat.FlatSetElementNode;
39 import IR.Flat.FlatSetFieldNode;
40 import IR.Flat.FlatWriteDynamicVarNode;
41 import IR.Flat.TempDescriptor;
43 public class OoOJavaAnalysis {
45 // data from the compiler
47 private TypeUtil typeUtil;
48 private CallGraph callGraph;
49 private RBlockRelationAnalysis rblockRel;
50 private DisjointAnalysis disjointAnalysisTaints;
51 private DisjointAnalysis disjointAnalysisReach;
53 private Set<MethodDescriptor> descriptorsToAnalyze;
55 private Hashtable<FlatNode, Set<TempDescriptor>> livenessGlobalView;
56 private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
57 private Hashtable<FlatNode, VarSrcTokTable> variableResults;
58 private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
59 private Hashtable<FlatNode, CodePlan> codePlans;
61 private Hashtable<FlatSESEEnterNode, Set<TempDescriptor>> notAvailableIntoSESE;
63 private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
65 // temporal data structures to track analysis progress.
66 static private int uniqueLockSetId = 0;
67 // mapping of a conflict graph to its compiled lock
68 private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraph2SESELock;
69 // mapping of a sese block to its conflict graph
70 private Hashtable<FlatNode, ConflictGraph> sese2conflictGraph;
72 public static int maxSESEage = -1;
74 public int getMaxSESEage() {
79 public CodePlan getCodePlan(FlatNode fn) {
80 CodePlan cp = codePlans.get(fn);
84 public Set<FlatNode> getNodesWithPlans() {
85 return codePlans.keySet();
88 public DisjointAnalysis getDisjointAnalysis() {
89 return disjointAnalysisTaints;
93 public OoOJavaAnalysis(State state,
97 ArrayReferencees arrayReferencees) {
99 double timeStartAnalysis = (double) System.nanoTime();
102 this.typeUtil = typeUtil;
103 this.callGraph = callGraph;
104 this.maxSESEage = state.OOO_MAXSESEAGE;
106 livenessGlobalView = new Hashtable<FlatNode, Set<TempDescriptor>>();
107 livenessVirtualReads = new Hashtable<FlatNode, Set<TempDescriptor>>();
108 variableResults = new Hashtable<FlatNode, VarSrcTokTable>();
109 notAvailableResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
110 codePlans = new Hashtable<FlatNode, CodePlan>();
111 wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
112 notAvailableIntoSESE = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
113 sese2conflictGraph = new Hashtable<FlatNode, ConflictGraph>();
114 conflictGraph2SESELock = new Hashtable<ConflictGraph, HashSet<SESELock>>();
116 // add all methods transitively reachable from the
117 // source's main to set for analysis
118 MethodDescriptor mdSourceEntry = typeUtil.getMain();
119 FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
121 descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
123 descriptorsToAnalyze.add(mdSourceEntry);
125 // 1st pass, find basic rblock relations & potential stall sites
126 rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
127 VarSrcTokTable.rblockRel = rblockRel;
129 // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
130 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
131 while (methItr.hasNext()) {
132 Descriptor d = methItr.next();
133 FlatMethod fm = state.getMethodFlat(d);
135 // note we can't use the general liveness analysis already in
136 // the compiler because this analysis is task-aware
137 livenessAnalysisBackward(fm);
140 // 3rd pass, variable analysis
141 methItr = descriptorsToAnalyze.iterator();
142 while (methItr.hasNext()) {
143 Descriptor d = methItr.next();
144 FlatMethod fm = state.getMethodFlat(d);
146 // starting from roots do a forward, fixed-point
147 // variable analysis for refinement and stalls
148 variableAnalysisForward(fm);
151 // 4th pass, compute liveness contribution from
152 // virtual reads discovered in variable pass
153 methItr = descriptorsToAnalyze.iterator();
154 while (methItr.hasNext()) {
155 Descriptor d = methItr.next();
156 FlatMethod fm = state.getMethodFlat(d);
157 livenessAnalysisBackward(fm);
160 // 5th pass, use disjointness with NO FLAGGED REGIONS
161 // to compute taints and effects
162 disjointAnalysisTaints =
163 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null,
165 true ); // suppress output--this is an intermediate pass
167 // 6th pass, not available analysis FOR VARIABLES!
168 methItr = descriptorsToAnalyze.iterator();
169 while (methItr.hasNext()) {
170 Descriptor d = methItr.next();
171 FlatMethod fm = state.getMethodFlat(d);
173 // compute what is not available at every program
174 // point, in a forward fixed-point pass
175 notAvailableForward(fm);
178 // 7th pass, make conflict graph
179 // conflict graph is maintained by each parent sese,
180 // where its' own stall sites and children may appear
181 Set<FlatSESEEnterNode> allSESEs=rblockRel.getAllSESEs();
182 for (Iterator iterator = allSESEs.iterator(); iterator.hasNext();) {
184 FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
185 if (!parent.getIsLeafSESE()) {
187 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
188 ConflictGraph conflictGraph = sese2conflictGraph.get(parent);
189 if (conflictGraph == null) {
190 conflictGraph = new ConflictGraph(state);
193 Set<FlatSESEEnterNode> children = parent.getChildren();
194 for (Iterator iterator2 = children.iterator(); iterator2.hasNext();) {
195 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
196 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(child);
197 conflictGraph.addLiveIn(taint2Effects);
198 sese2conflictGraph.put(parent, conflictGraph);
203 Iterator descItr = descriptorsToAnalyze.iterator();
204 while (descItr.hasNext()) {
205 Descriptor d = (Descriptor) descItr.next();
206 FlatMethod fm = state.getMethodFlat(d);
208 makeConflictGraph(fm);
213 // 8th pass, calculate all possible conflicts without using
214 // reachability info and identify set of FlatNew that next
215 // disjoint reach. analysis should flag
216 Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
217 calculateConflicts(sitesToFlag, false);
221 // 9th pass, ask disjoint analysis to compute reachability
222 // for objects that may cause heap conflicts so the most
223 // efficient method to deal with conflict can be computed
225 disjointAnalysisReach =
226 new DisjointAnalysis(state, typeUtil, callGraph, liveness,
227 arrayReferencees, sitesToFlag,
228 null // don't do effects analysis again!
231 // 10th pass, calculate conflicts with reachability info
232 calculateConflicts(null, true);
235 // 11th pass, compiling locks
238 // 12th pass, compute a plan for code injections
239 methItr = descriptorsToAnalyze.iterator();
240 while (methItr.hasNext()) {
241 Descriptor d = methItr.next();
242 FlatMethod fm = state.getMethodFlat(d);
243 codePlansForward(fm);
247 // splice new IR nodes into graph after all
248 // analysis passes are complete
249 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
250 while (spliceItr.hasNext()) {
251 Map.Entry me = (Map.Entry) spliceItr.next();
252 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
253 fwdvn.spliceIntoIR();
257 if (state.OOODEBUG) {
260 disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt");
261 writeConflictGraph();
262 } catch (IOException e) {}
266 System.out.println("\n\n\n##########################################################\n"+
267 "Warning, lots of code changes going on, OoOJava and RCR/DFJ\n"+
268 "systems are being cleaned up. Until the analyses and code gen\n"+
269 "are fully altered and coordinated, these systems will not run\n"+
270 "to completion. Partial stable check-ins are necessary to manage\n"+
271 "the number of files getting touched.\n"+
272 "##########################################################" );
280 * Iterator iter = sese2conflictGraph.entrySet().iterator(); while
281 * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn =
282 * (FlatNode) e.getKey(); ConflictGraph conflictGraph = (ConflictGraph)
284 * System.out.println("---------------------------------------");
285 * System.out.println("CONFLICT GRAPH for " + fn); Set<String> keySet =
286 * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator();
287 * iterator.hasNext();) { String key = (String) iterator.next();
288 * ConflictNode node = conflictGraph.id2cn.get(key);
289 * System.out.println("key=" + key + " \n" + node.toStringAllEffects()); } }
295 private void writeFile(Set<FlatNew> sitesToFlag) {
298 BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt"));
300 for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext();) {
301 FlatNew fn = (FlatNew) iterator.next();
305 } catch (IOException e) {
312 private void livenessAnalysisBackward(FlatMethod fm) {
314 // flow backward across nodes to compute liveness, and
315 // take special care with sese enter/exit nodes that
316 // alter this from normal liveness analysis
317 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
318 flatNodesToVisit.add( fm.getFlatExit() );
320 while( !flatNodesToVisit.isEmpty() ) {
321 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
322 flatNodesToVisit.remove( fn );
324 Set<TempDescriptor> prev = livenessGlobalView.get( fn );
326 // merge sets from control flow joins
327 Set<TempDescriptor> livein = new HashSet<TempDescriptor>();
328 for (int i = 0; i < fn.numNext(); i++) {
329 FlatNode nn = fn.getNext( i );
330 Set<TempDescriptor> s = livenessGlobalView.get( nn );
336 Set<TempDescriptor> curr = liveness_nodeActions( fn, livein );
338 // if a new result, schedule backward nodes for analysis
339 if( !curr.equals( prev ) ) {
340 livenessGlobalView.put( fn, curr );
342 for( int i = 0; i < fn.numPrev(); i++ ) {
343 FlatNode nn = fn.getPrev( i );
344 flatNodesToVisit.add( nn );
350 private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
351 Set<TempDescriptor> liveIn
353 switch( fn.kind() ) {
355 case FKind.FlatSESEEnterNode: {
356 // add whatever is live-in at a task enter to that
358 FlatSESEEnterNode fsen = (FlatSESEEnterNode)fn;
359 if( liveIn != null ) {
360 fsen.addInVarSet( liveIn );
362 // no break, should also execute default actions
366 // handle effects of statement in reverse, writes then reads
367 TempDescriptor[] writeTemps = fn.writesTemps();
368 for( int i = 0; i < writeTemps.length; ++i ) {
369 liveIn.remove( writeTemps[i] );
371 // if we are analyzing code declared directly in a task,
372 FlatSESEEnterNode fsen = rblockRel.getLocalInnerRBlock( fn );
374 // check to see if we are writing to variables that will
375 // be live-out at the task's exit (and therefore should
376 // go in the task's out-var set)
377 FlatSESEExitNode fsexn = fsen.getFlatExit();
378 Set<TempDescriptor> livetemps = livenessGlobalView.get( fsexn );
379 if( livetemps != null && livetemps.contains( writeTemps[i] ) ) {
380 fsen.addOutVar( writeTemps[i] );
385 TempDescriptor[] readTemps = fn.readsTemps();
386 for( int i = 0; i < readTemps.length; ++i ) {
387 liveIn.add( readTemps[i] );
390 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
391 if( virtualReadTemps != null ) {
392 liveIn.addAll( virtualReadTemps );
402 private void variableAnalysisForward(FlatMethod fm) {
404 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
405 flatNodesToVisit.add(fm);
407 while (!flatNodesToVisit.isEmpty()) {
408 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
409 flatNodesToVisit.remove(fn);
411 VarSrcTokTable prev = variableResults.get(fn);
413 // merge sets from control flow joins
414 VarSrcTokTable curr = new VarSrcTokTable();
415 for (int i = 0; i < fn.numPrev(); i++) {
416 FlatNode nn = fn.getPrev(i);
417 VarSrcTokTable incoming = variableResults.get(nn);
418 curr.merge(incoming);
421 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
422 if( currentSESE == null ) {
423 currentSESE = rblockRel.getCallerProxySESE();
426 variable_nodeActions(fn, curr, currentSESE);
428 // if a new result, schedule forward nodes for analysis
429 if (!curr.equals(prev)) {
430 variableResults.put(fn, curr);
432 for (int i = 0; i < fn.numNext(); i++) {
433 FlatNode nn = fn.getNext(i);
434 flatNodesToVisit.add(nn);
440 private void variable_nodeActions(FlatNode fn,
441 VarSrcTokTable vstTable,
442 FlatSESEEnterNode currentSESE) {
446 case FKind.FlatSESEEnterNode: {
447 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
448 // ignore currently executing SESE, at this point
449 // the analysis considers a new instance is becoming
452 vstTable.assertConsistency();
456 case FKind.FlatSESEExitNode: {
457 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
459 // fsen is the child of currently executing tasks
460 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
462 // remap all of this child's children tokens to be
463 // from this child as the child exits
464 vstTable.remapChildTokens(fsen);
466 // liveness virtual reads are things that might be
467 // written by an SESE and should be added to the in-set
468 // anything virtually read by this SESE should be pruned
469 // of parent or sibling sources
470 Set<TempDescriptor> liveVars = livenessGlobalView.get(fn);
471 Set<TempDescriptor> fsenVirtReads =
472 vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen,
475 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
476 if (fsenVirtReadsOld != null) {
477 fsenVirtReads.addAll(fsenVirtReadsOld);
479 livenessVirtualReads.put(fn, fsenVirtReads);
481 // then all child out-set tokens are guaranteed
482 // to be filled in, so clobber those entries with
483 // the latest, clean sources
484 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
485 while (outVarItr.hasNext()) {
486 TempDescriptor outVar = outVarItr.next();
487 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
489 VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
490 vstTable.remove(outVar);
493 vstTable.assertConsistency();
497 case FKind.FlatOpNode: {
498 FlatOpNode fon = (FlatOpNode) fn;
500 if (fon.getOp().getOp() == Operation.ASSIGN) {
501 TempDescriptor lhs = fon.getDest();
502 TempDescriptor rhs = fon.getLeft();
504 vstTable.remove(lhs);
506 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
508 Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
509 while (itr.hasNext()) {
510 VariableSourceToken vst = itr.next();
512 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
515 // when we do x = y for variables, just copy over from a child,
516 // there are two cases:
517 // 1. if the current task is the caller proxy, any local root is a child
519 currentSESE.getIsCallerProxySESE() &&
520 rblockRel.getLocalRootSESEs().contains( vst.getSESE() );
522 // 2. if the child task is a locally-defined child of the current task
523 boolean case2 = currentSESE.getLocalChildren().contains( vst.getSESE() );
525 if( case1 || case2 ) {
526 // if the source comes from a child, copy it over
527 forAddition.add( new VariableSourceToken( ts,
534 // otherwise, stamp it as us as the source
535 forAddition.add( new VariableSourceToken( ts,
544 vstTable.addAll( forAddition );
546 // only break if this is an ASSIGN op node,
547 // otherwise fall through to default case
548 vstTable.assertConsistency();
553 // note that FlatOpNode's that aren't ASSIGN
554 // fall through to this default case
556 TempDescriptor[] writeTemps = fn.writesTemps();
557 if( writeTemps.length > 0 ) {
559 // for now, when writeTemps > 1, make sure
560 // its a call node, programmer enforce only
561 // doing stuff like calling a print routine
562 if( writeTemps.length > 1 ) {
563 assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
567 vstTable.remove( writeTemps[0] );
569 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
570 ts.add( writeTemps[0] );
572 vstTable.add( new VariableSourceToken( ts,
580 vstTable.assertConsistency();
587 private void notAvailableForward(FlatMethod fm) {
589 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
590 flatNodesToVisit.add(fm);
592 while (!flatNodesToVisit.isEmpty()) {
593 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
594 flatNodesToVisit.remove(fn);
596 Set<TempDescriptor> prev = notAvailableResults.get(fn);
598 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
599 for (int i = 0; i < fn.numPrev(); i++) {
600 FlatNode nn = fn.getPrev(i);
601 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
602 if (notAvailIn != null) {
603 curr.addAll(notAvailIn);
607 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
608 if( currentSESE == null ) {
609 currentSESE = rblockRel.getCallerProxySESE();
612 notAvailable_nodeActions(fn, curr, currentSESE);
614 // if a new result, schedule forward nodes for analysis
615 if (!curr.equals(prev)) {
616 notAvailableResults.put(fn, curr);
618 for (int i = 0; i < fn.numNext(); i++) {
619 FlatNode nn = fn.getNext(i);
620 flatNodesToVisit.add(nn);
626 private void notAvailable_nodeActions(FlatNode fn,
627 Set<TempDescriptor> notAvailSet,
628 FlatSESEEnterNode currentSESE
631 // any temps that are removed from the not available set
632 // at this node should be marked in this node's code plan
633 // as temps to be grabbed at runtime!
637 case FKind.FlatSESEEnterNode: {
638 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
640 // keep a copy of what's not available into the SESE
641 // and restore it at the matching exit node
642 Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
643 Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
644 while (tdItr.hasNext()) {
645 notAvailCopy.add(tdItr.next());
647 notAvailableIntoSESE.put(fsen, notAvailCopy);
652 case FKind.FlatSESEExitNode: {
653 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
654 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
656 notAvailSet.addAll(fsen.getOutVarSet());
658 Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
659 assert notAvailIn != null;
660 notAvailSet.addAll(notAvailIn);
663 case FKind.FlatMethod: {
667 case FKind.FlatOpNode: {
668 FlatOpNode fon = (FlatOpNode) fn;
670 if (fon.getOp().getOp() == Operation.ASSIGN) {
671 TempDescriptor lhs = fon.getDest();
672 TempDescriptor rhs = fon.getLeft();
674 // copy makes lhs same availability as rhs
675 if (notAvailSet.contains(rhs)) {
676 notAvailSet.add(lhs);
678 notAvailSet.remove(lhs);
681 // only break if this is an ASSIGN op node,
682 // otherwise fall through to default case
687 // note that FlatOpNode's that aren't ASSIGN
688 // fall through to this default case
690 TempDescriptor[] writeTemps = fn.writesTemps();
691 for (int i = 0; i < writeTemps.length; i++) {
692 TempDescriptor wTemp = writeTemps[i];
693 notAvailSet.remove(wTemp);
695 TempDescriptor[] readTemps = fn.readsTemps();
696 for (int i = 0; i < readTemps.length; i++) {
697 TempDescriptor rTemp = readTemps[i];
698 notAvailSet.remove(rTemp);
700 // if this variable has exactly one source, potentially
701 // get other things from this source as well
702 VarSrcTokTable vstTable = variableResults.get(fn);
704 VSTWrapper vstIfStatic = new VSTWrapper();
705 Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
707 if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
709 VariableSourceToken vst = vstIfStatic.vst;
711 Iterator<VariableSourceToken> availItr =
712 vstTable.get(vst.getSESE(), vst.getAge()).iterator();
714 // look through things that are also available from same source
715 while (availItr.hasNext()) {
716 VariableSourceToken vstAlsoAvail = availItr.next();
718 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
719 while (refVarItr.hasNext()) {
720 TempDescriptor refVarAlso = refVarItr.next();
722 // if a variable is available from the same source, AND it ALSO
723 // only comes from one statically known source, mark it available
724 VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
725 Integer srcTypeAlso =
726 vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed);
727 if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
728 notAvailSet.remove(refVarAlso);
740 private void codePlansForward(FlatMethod fm) {
742 // start from flat method top, visit every node in
743 // method exactly once
744 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
745 flatNodesToVisit.add(fm);
747 Set<FlatNode> visited = new HashSet<FlatNode>();
749 while (!flatNodesToVisit.isEmpty()) {
750 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
751 FlatNode fn = fnItr.next();
753 flatNodesToVisit.remove(fn);
756 // use incoming results as "dot statement" or just
757 // before the current statement
758 VarSrcTokTable dotSTtable = new VarSrcTokTable();
759 for (int i = 0; i < fn.numPrev(); i++) {
760 FlatNode nn = fn.getPrev(i);
761 dotSTtable.merge(variableResults.get(nn));
764 // find dt-st notAvailableSet also
765 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
766 for (int i = 0; i < fn.numPrev(); i++) {
767 FlatNode nn = fn.getPrev(i);
768 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
769 if (notAvailIn != null) {
770 dotSTnotAvailSet.addAll(notAvailIn);
774 Set<TempDescriptor> dotSTlive = livenessGlobalView.get(fn);
776 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
777 if( currentSESE == null ) {
778 currentSESE = rblockRel.getCallerProxySESE();
781 codePlans_nodeActions(fn, dotSTlive, dotSTtable, dotSTnotAvailSet, currentSESE);
783 for (int i = 0; i < fn.numNext(); i++) {
784 FlatNode nn = fn.getNext(i);
786 if (!visited.contains(nn)) {
787 flatNodesToVisit.add(nn);
793 private void codePlans_nodeActions(FlatNode fn,
794 Set<TempDescriptor> liveSetIn,
795 VarSrcTokTable vstTableIn,
796 Set<TempDescriptor> notAvailSetIn,
797 FlatSESEEnterNode currentSESE) {
799 CodePlan plan = new CodePlan(currentSESE);
803 case FKind.FlatSESEEnterNode: {
804 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
806 // track the source types of the in-var set so generated
807 // code at this SESE issue can compute the number of
808 // dependencies properly
809 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
810 while (inVarItr.hasNext()) {
811 TempDescriptor inVar = inVarItr.next();
813 // when we get to an SESE enter node we change the
814 // currentSESE variable of this analysis to the
815 // child that is declared by the enter node, so
816 // in order to classify in-vars correctly, pass
817 // the parent SESE in--at other FlatNode types just
818 // use the currentSESE
819 FlatSESEEnterNode parent = rblockRel.getLocalInnerRBlock( fn );
821 System.out.println( "-----\nfsen="+fsen+", parent="+parent );
823 assert fsen == parent;
827 if( currentSESE == null ) {
828 currentSESE = rblockRel.getCallerProxySESE();
832 VSTWrapper vstIfStatic = new VSTWrapper();
833 Integer srcType = vstTableIn.getRefVarSrcType(inVar, fsen.getParent(), vstIfStatic);
835 // the current SESE needs a local space to track the dynamic
836 // variable and the child needs space in its SESE record
837 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
838 fsen.addDynamicInVar(inVar);
839 // %@%@%@%@%@%@%@% TODO!!!! @%@%@%@%@% fsen.getParent().addDynamicVar(inVar);
841 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
842 fsen.addStaticInVar(inVar);
843 VariableSourceToken vst = vstIfStatic.vst;
844 fsen.putStaticInVar2src(inVar, vst);
845 fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
847 assert srcType.equals(VarSrcTokTable.SrcType_READY);
848 fsen.addReadyInVar(inVar);
856 case FKind.FlatSESEExitNode: {
857 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
861 case FKind.FlatOpNode: {
862 FlatOpNode fon = (FlatOpNode) fn;
864 if (fon.getOp().getOp() == Operation.ASSIGN) {
865 TempDescriptor lhs = fon.getDest();
866 TempDescriptor rhs = fon.getLeft();
868 // if this is an op node, don't stall, copy
869 // source and delay until we need to use value
871 // ask whether lhs and rhs sources are dynamic, static, etc.
872 VSTWrapper vstIfStatic = new VSTWrapper();
873 Integer lhsSrcType = vstTableIn.getRefVarSrcType(lhs, currentSESE, vstIfStatic);
874 Integer rhsSrcType = vstTableIn.getRefVarSrcType(rhs, currentSESE, vstIfStatic);
876 if (rhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
877 // if rhs is dynamic going in, lhs will definitely be dynamic
878 // going out of this node, so track that here
879 plan.addDynAssign(lhs, rhs);
880 currentSESE.addDynamicVar(lhs);
881 currentSESE.addDynamicVar(rhs);
883 } else if (lhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
884 // otherwise, if the lhs is dynamic, but the rhs is not, we
885 // need to update the variable's dynamic source as "current SESE"
886 plan.addDynAssign(lhs);
889 // only break if this is an ASSIGN op node,
890 // otherwise fall through to default case
895 // note that FlatOpNode's that aren't ASSIGN
896 // fall through to this default case
899 // a node with no live set has nothing to stall for
900 if (liveSetIn == null) {
904 TempDescriptor[] readarray = fn.readsTemps();
905 for (int i = 0; i < readarray.length; i++) {
906 TempDescriptor readtmp = readarray[i];
908 // ignore temps that are definitely available
909 // when considering to stall on it
910 if (!notAvailSetIn.contains(readtmp)) {
914 // check the source type of this variable
915 VSTWrapper vstIfStatic = new VSTWrapper();
916 Integer srcType = vstTableIn.getRefVarSrcType(readtmp, currentSESE, vstIfStatic);
918 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
919 // 1) It is not clear statically where this variable will
920 // come from, so dynamically we must keep track
921 // along various control paths, and therefore when we stall,
922 // just stall for the exact thing we need and move on
923 plan.addDynamicStall(readtmp);
924 currentSESE.addDynamicVar(readtmp);
926 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
927 // 2) Single token/age pair: Stall for token/age pair, and copy
928 // all live variables with same token/age pair at the same
929 // time. This is the same stuff that the notavaialable analysis
930 // marks as now available.
931 VariableSourceToken vst = vstIfStatic.vst;
933 Iterator<VariableSourceToken> availItr =
934 vstTableIn.get(vst.getSESE(), vst.getAge()).iterator();
936 while (availItr.hasNext()) {
937 VariableSourceToken vstAlsoAvail = availItr.next();
939 // only grab additional stuff that is live
940 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
942 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
943 while (refVarItr.hasNext()) {
944 TempDescriptor refVar = refVarItr.next();
945 if (liveSetIn.contains(refVar)) {
950 if (!copySet.isEmpty()) {
951 plan.addStall2CopySet(vstAlsoAvail, copySet);
956 // the other case for srcs is READY, so do nothing
959 // assert that everything being stalled for is in the
960 // "not available" set coming into this flat node and
961 // that every VST identified is in the possible "stall set"
962 // that represents VST's from children SESE's
970 // identify sese-age pairs that are statically useful
971 // and should have an associated SESE variable in code
972 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
973 // AND ALWAYS GIVE NAMES TO PARENTS
974 Set<VariableSourceToken> staticSet = vstTableIn.get();
975 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
976 while (vstItr.hasNext()) {
977 VariableSourceToken vst = vstItr.next();
979 // placeholder source tokens are useful results, but
980 // the placeholder static name is never needed
981 //if (vst.getSESE().getIsCallerSESEplaceholder()) {
985 FlatSESEEnterNode sese = currentSESE;
986 while (sese != null) {
987 sese.addNeededStaticName(new SESEandAgePair(vst.getSESE(), vst.getAge()));
988 sese.mustTrackAtLeastAge(vst.getAge());
990 //@%@%@%@%@%@% TODO!!!!! @%@%@%@%@%@% sese = sese.getParent();
994 codePlans.put(fn, plan);
996 // if any variables at this-node-*dot* have a static source (exactly one
998 // but go to a dynamic source at next-node-*dot*, create a new IR graph
999 // node on that edge to track the sources dynamically
1000 VarSrcTokTable thisVstTable = variableResults.get(fn);
1001 for (int i = 0; i < fn.numNext(); i++) {
1002 FlatNode nn = fn.getNext(i);
1003 VarSrcTokTable nextVstTable = variableResults.get(nn);
1004 Set<TempDescriptor> nextLiveIn = livenessGlobalView.get(nn);
1006 // the table can be null if it is one of the few IR nodes
1007 // completely outside of the root SESE scope
1008 if (nextVstTable != null && nextLiveIn != null) {
1010 Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
1011 thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, currentSESE);
1013 if (!readyOrStatic2dynamicSet.isEmpty()) {
1015 // either add these results to partial fixed-point result
1016 // or make a new one if we haven't made any here yet
1017 FlatEdge fe = new FlatEdge(fn, nn);
1018 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe);
1020 if (fwdvn == null) {
1021 fwdvn = new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, currentSESE);
1022 wdvNodesToSpliceIn.put(fe, fwdvn);
1024 fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet);
1032 private void makeConflictGraph(FlatMethod fm) {
1034 //System.out.println( "Creating conflict graph for "+fm );
1036 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1037 flatNodesToVisit.add(fm);
1039 Set<FlatNode> visited = new HashSet<FlatNode>();
1041 while (!flatNodesToVisit.isEmpty()) {
1042 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1043 flatNodesToVisit.remove(fn);
1046 Set<FlatSESEEnterNode> currentSESEs =
1047 rblockRel.getPossibleExecutingRBlocks( fn );
1049 conflictGraph_nodeAction(fn, currentSESEs);
1051 // schedule forward nodes for analysis
1052 for (int i = 0; i < fn.numNext(); i++) {
1053 FlatNode nn = fn.getNext(i);
1054 if (!visited.contains(nn)) {
1055 flatNodesToVisit.add(nn);
1063 private void conflictGraph_nodeAction(FlatNode fn,
1064 Set<FlatSESEEnterNode> currentSESEs
1066 ConflictGraph conflictGraph;
1070 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1073 switch (fn.kind()) {
1076 case FKind.FlatFieldNode:
1077 case FKind.FlatElementNode: {
1079 if (fn instanceof FlatFieldNode) {
1080 FlatFieldNode ffn = (FlatFieldNode) fn;
1083 FlatElementNode fen = (FlatElementNode) fn;
1087 for( Iterator<FlatSESEEnterNode> itr = currentSESEs.iterator();
1090 FlatSESEEnterNode currentSESE = itr.next();
1092 conflictGraph = sese2conflictGraph.get(currentSESE);
1093 if (conflictGraph == null) {
1094 conflictGraph = new ConflictGraph(state);
1098 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1099 conflictGraph.addStallSite(taint2Effects, rhs);
1101 if (conflictGraph.id2cn.size() > 0) {
1102 sese2conflictGraph.put(currentSESE, conflictGraph);
1108 case FKind.FlatSetFieldNode:
1109 case FKind.FlatSetElementNode: {
1111 if (fn instanceof FlatSetFieldNode) {
1112 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1113 lhs = fsfn.getDst();
1114 rhs = fsfn.getSrc();
1116 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1117 lhs = fsen.getDst();
1118 rhs = fsen.getSrc();
1121 for( Iterator<FlatSESEEnterNode> itr = currentSESEs.iterator();
1124 FlatSESEEnterNode currentSESE = itr.next();
1126 conflictGraph = sese2conflictGraph.get(currentSESE);
1127 if (conflictGraph == null) {
1128 conflictGraph = new ConflictGraph(state);
1131 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1132 conflictGraph.addStallSite(taint2Effects, rhs);
1133 conflictGraph.addStallSite(taint2Effects, lhs);
1135 if (conflictGraph.id2cn.size() > 0) {
1136 sese2conflictGraph.put(currentSESE, conflictGraph);
1142 case FKind.FlatCall: {
1143 FlatCall fc = (FlatCall) fn;
1146 for( Iterator<FlatSESEEnterNode> itr = currentSESEs.iterator();
1149 FlatSESEEnterNode currentSESE = itr.next();
1151 conflictGraph = sese2conflictGraph.get(currentSESE);
1152 if (conflictGraph == null) {
1153 conflictGraph = new ConflictGraph(state);
1156 // collects effects of stall site and generates stall site node
1157 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1159 conflictGraph.addStallSite(taint2Effects, lhs);
1160 if (conflictGraph.id2cn.size() > 0) {
1161 sese2conflictGraph.put(currentSESE, conflictGraph);
1170 private void calculateConflicts(Set<FlatNew> sitesToFlag, boolean useReachInfo) {
1171 // decide fine-grain edge or coarse-grain edge among all vertexes by
1172 // pair-wise comparison
1173 Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
1174 while (seseIter.hasNext()) {
1175 FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next();
1176 ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
1177 // System.out.println("# CALCULATING SESE CONFLICT="+sese);
1179 // clear current conflict before recalculating with reachability info
1180 conflictGraph.clearAllConflictEdge();
1181 conflictGraph.setDisJointAnalysis(disjointAnalysisReach);
1182 conflictGraph.setFMEnclosing(sese.getfmEnclosing());
1184 conflictGraph.analyzeConflicts(sitesToFlag, useReachInfo);
1185 sese2conflictGraph.put(sese, conflictGraph);
1189 private void writeConflictGraph() {
1190 Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
1191 while (keyEnum.hasMoreElements()) {
1192 FlatNode key = (FlatNode) keyEnum.nextElement();
1193 ConflictGraph cg = sese2conflictGraph.get(key);
1195 if (cg.hasConflictEdge()) {
1196 cg.writeGraph("ConflictGraphFor" + key, false);
1198 } catch (IOException e) {
1199 System.out.println("Error writing");
1205 private void synthesizeLocks() {
1206 Set<Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
1207 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
1208 Entry<FlatNode, ConflictGraph> graphEntry = (Entry<FlatNode, ConflictGraph>) iterator.next();
1209 FlatNode sese = graphEntry.getKey();
1210 ConflictGraph conflictGraph = graphEntry.getValue();
1211 calculateCovering(conflictGraph);
1215 private void calculateCovering(ConflictGraph conflictGraph) {
1216 uniqueLockSetId = 0; // reset lock counter for every new conflict graph
1217 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1218 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1219 HashSet<SESELock> lockSet = new HashSet<SESELock>();
1221 Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1222 for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
1223 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1224 if (conflictEdge.isCoarseEdge()) {
1225 coarseToCover.add(conflictEdge);
1227 fineToCover.add(conflictEdge);
1231 HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
1232 toCover.addAll(fineToCover);
1233 toCover.addAll(coarseToCover);
1235 while (!toCover.isEmpty()) {
1237 SESELock seseLock = new SESELock();
1238 seseLock.setID(uniqueLockSetId++);
1242 do { // fine-grained edge
1246 for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) {
1249 ConflictEdge edge = (ConflictEdge) iterator.next();
1250 if (seseLock.getConflictNodeSet().size() == 0) {
1252 if (seseLock.isWriteNode(edge.getVertexU())) {
1253 // mark as fine_write
1254 if (edge.getVertexU().isStallSiteNode()) {
1255 type = ConflictNode.PARENT_WRITE;
1257 type = ConflictNode.FINE_WRITE;
1259 seseLock.addConflictNode(edge.getVertexU(), type);
1261 // mark as fine_read
1262 if (edge.getVertexU().isStallSiteNode()) {
1263 type = ConflictNode.PARENT_READ;
1265 type = ConflictNode.FINE_READ;
1267 seseLock.addConflictNode(edge.getVertexU(), type);
1269 if (edge.getVertexV() != edge.getVertexU()) {
1270 if (seseLock.isWriteNode(edge.getVertexV())) {
1271 // mark as fine_write
1272 if (edge.getVertexV().isStallSiteNode()) {
1273 type = ConflictNode.PARENT_WRITE;
1275 type = ConflictNode.FINE_WRITE;
1277 seseLock.addConflictNode(edge.getVertexV(), type);
1279 // mark as fine_read
1280 if (edge.getVertexV().isStallSiteNode()) {
1281 type = ConflictNode.PARENT_READ;
1283 type = ConflictNode.FINE_READ;
1285 seseLock.addConflictNode(edge.getVertexV(), type);
1289 seseLock.addConflictEdge(edge);
1290 fineToCover.remove(edge);
1291 break;// exit iterator loop
1292 }// end of initial setup
1294 ConflictNode newNode;
1295 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1296 // new node has a fine-grained edge to all current node
1297 // If there is a coarse grained edge where need a fine edge, it's
1298 // okay to add the node
1299 // but the edge must remain uncovered.
1303 if (seseLock.containsConflictNode(newNode)) {
1304 seseLock.addEdge(edge);
1305 fineToCover.remove(edge);
1309 if (seseLock.isWriteNode(newNode)) {
1310 if (newNode.isStallSiteNode()) {
1311 type = ConflictNode.PARENT_WRITE;
1313 type = ConflictNode.FINE_WRITE;
1315 seseLock.setNodeType(newNode, type);
1317 if (newNode.isStallSiteNode()) {
1318 type = ConflictNode.PARENT_READ;
1320 type = ConflictNode.FINE_READ;
1322 seseLock.setNodeType(newNode, type);
1325 seseLock.addEdge(edge);
1326 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1327 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1328 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1330 // mark all fine edges between new node and nodes in the group as
1332 if (!conflictEdge.getVertexU().equals(newNode)) {
1333 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1335 seseLock.addConflictEdge(conflictEdge);
1336 fineToCover.remove(conflictEdge);
1338 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1339 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1341 seseLock.addConflictEdge(conflictEdge);
1342 fineToCover.remove(conflictEdge);
1348 break;// exit iterator loop
1353 HashSet<ConflictEdge> notCovered=new HashSet<ConflictEdge>();
1357 for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) {
1359 ConflictEdge edge = (ConflictEdge) iterator.next();
1360 if (seseLock.getConflictNodeSet().size() == 0) {
1362 if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
1363 // node has a coarse-grained edge with itself
1364 if (!(edge.getVertexU().isStallSiteNode())) {
1365 // and it is not parent
1366 type = ConflictNode.SCC;
1369 type = ConflictNode.PARENT_COARSE;
1371 type = ConflictNode.PARENT_WRITE;
1374 seseLock.addConflictNode(edge.getVertexU(), type);
1376 if (edge.getVertexU().isStallSiteNode()) {
1378 type = ConflictNode.PARENT_COARSE;
1380 if (edge.getVertexU().getWriteEffectSet().isEmpty()) {
1381 type = ConflictNode.PARENT_READ;
1383 type = ConflictNode.PARENT_WRITE;
1387 type = ConflictNode.COARSE;
1389 seseLock.addConflictNode(edge.getVertexU(), type);
1391 if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
1392 // node has a coarse-grained edge with itself
1393 if (!(edge.getVertexV().isStallSiteNode())) {
1394 // and it is not parent
1395 type = ConflictNode.SCC;
1398 type = ConflictNode.PARENT_COARSE;
1400 type = ConflictNode.PARENT_WRITE;
1403 seseLock.addConflictNode(edge.getVertexV(), type);
1405 if (edge.getVertexV().isStallSiteNode()) {
1407 type = ConflictNode.PARENT_COARSE;
1409 if (edge.getVertexV().getWriteEffectSet().isEmpty()) {
1410 type = ConflictNode.PARENT_READ;
1412 type = ConflictNode.PARENT_WRITE;
1416 type = ConflictNode.COARSE;
1418 seseLock.addConflictNode(edge.getVertexV(), type);
1421 coarseToCover.remove(edge);
1422 seseLock.addConflictEdge(edge);
1423 break;// exit iterator loop
1424 }// end of initial setup
1426 ConflictNode newNode;
1427 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1428 // new node has a coarse-grained edge to all fine-read, fine-write,
1432 if (newNode.isInVarNode() && (!seseLock.hasSelfCoarseEdge(newNode))
1433 && seseLock.hasCoarseEdgeWithParentCoarse(newNode)) {
1434 // this case can't be covered by this queue
1435 coarseToCover.remove(edge);
1436 notCovered.add(edge);
1440 if (seseLock.containsConflictNode(newNode)) {
1441 seseLock.addEdge(edge);
1442 coarseToCover.remove(edge);
1446 if (seseLock.hasSelfCoarseEdge(newNode)) {
1448 if (newNode.isStallSiteNode()) {
1449 type = ConflictNode.PARENT_COARSE;
1451 type = ConflictNode.SCC;
1453 seseLock.setNodeType(newNode, type);
1455 if (newNode.isStallSiteNode()) {
1456 type = ConflictNode.PARENT_COARSE;
1458 type = ConflictNode.COARSE;
1460 seseLock.setNodeType(newNode, type);
1463 seseLock.addEdge(edge);
1464 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1465 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1466 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1467 // mark all coarse edges between new node and nodes in the group
1469 if (!conflictEdge.getVertexU().equals(newNode)) {
1470 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1472 seseLock.addConflictEdge(conflictEdge);
1473 coarseToCover.remove(conflictEdge);
1475 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1476 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1478 seseLock.addConflictEdge(conflictEdge);
1479 coarseToCover.remove(conflictEdge);
1484 break;// exit iterator loop
1490 lockSet.add(seseLock);
1493 coarseToCover.addAll(notCovered);
1494 toCover.addAll(fineToCover);
1495 toCover.addAll(coarseToCover);
1499 conflictGraph2SESELock.put(conflictGraph, lockSet);
1502 public ConflictGraph getConflictGraph(FlatNode sese) {
1503 return sese2conflictGraph.get(sese);
1506 public Set<SESELock> getLockMappings(ConflictGraph graph) {
1507 return conflictGraph2SESELock.get(graph);
1510 public Set<FlatSESEEnterNode> getAllSESEs() {
1511 return rblockRel.getAllSESEs();
1514 public FlatSESEEnterNode getMainSESE() {
1515 return rblockRel.getMainSESE();
1519 public void writeReports(String timeReport) throws java.io.IOException {
1521 BufferedWriter bw = new BufferedWriter(new FileWriter("ooojReport_summary.txt"));
1522 bw.write("OoOJava Analysis Results\n\n");
1523 bw.write(timeReport + "\n\n");
1524 printSESEHierarchy(bw);
1529 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
1530 while (methItr.hasNext()) {
1531 MethodDescriptor md = methItr.next();
1532 FlatMethod fm = state.getMethodFlat(md);
1534 bw = new BufferedWriter(new FileWriter("ooojReport_" +
1535 md.getClassMethodName() +
1536 md.getSafeMethodDescriptor() +
1538 bw.write("OoOJava Results for " + md + "\n-------------------\n");
1540 //FlatSESEEnterNode implicitSESE = (FlatSESEEnterNode) fm.getNext(0);
1541 //if (!implicitSESE.getIsCallerSESEplaceholder() && implicitSESE != rblockRel.getMainSESE()) {
1542 // System.out.println(implicitSESE + " is not implicit?!");
1545 //bw.write("Dynamic vars to manage:\n " + implicitSESE.getDynamicVarSet());
1547 bw.write("\n\nLive-In, Root View\n------------------\n" + fm.printMethod(livenessGlobalView));
1548 bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults));
1549 //bw.write("\n\nNot Available Results-Out\n---------------------\n"
1550 // + fm.printMethod(notAvailableResults));
1551 //bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans));
1557 private void printSESEHierarchy(BufferedWriter bw) throws java.io.IOException {
1558 bw.write("SESE Local Hierarchy\n--------------\n");
1559 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getLocalRootSESEs().iterator();
1560 while (rootItr.hasNext()) {
1561 FlatSESEEnterNode root = rootItr.next();
1562 printSESEHierarchyTree(bw, root, 0);
1566 private void printSESEHierarchyTree(BufferedWriter bw,
1567 FlatSESEEnterNode fsen,
1569 ) throws java.io.IOException {
1570 for (int i = 0; i < depth; ++i) {
1573 bw.write("- " + fsen.getPrettyIdentifier() + "\n");
1575 Iterator<FlatSESEEnterNode> childItr = fsen.getLocalChildren().iterator();
1576 while (childItr.hasNext()) {
1577 FlatSESEEnterNode fsenChild = childItr.next();
1578 printSESEHierarchyTree(bw, fsenChild, depth + 1);
1582 private void printSESEInfo(BufferedWriter bw) throws java.io.IOException {
1583 bw.write("\nSESE info\n-------------\n");
1584 Iterator<FlatSESEEnterNode> fsenItr = rblockRel.getAllSESEs().iterator();
1585 while( fsenItr.hasNext() ) {
1586 FlatSESEEnterNode fsen = fsenItr.next();
1588 bw.write("SESE " + fsen.getPrettyIdentifier());
1589 if( fsen.getIsLeafSESE() ) {
1590 bw.write(" (leaf)");
1594 bw.write(" in-set: " + fsen.getInVarSet() + "\n");
1595 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1596 while (tItr.hasNext()) {
1597 TempDescriptor inVar = tItr.next();
1598 if (fsen.getReadyInVarSet().contains(inVar)) {
1599 bw.write(" (ready) " + inVar + "\n");
1601 if (fsen.getStaticInVarSet().contains(inVar)) {
1602 bw.write(" (static) " + inVar + " from " + fsen.getStaticInVarSrc(inVar) + "\n");
1604 if (fsen.getDynamicInVarSet().contains(inVar)) {
1605 bw.write(" (dynamic)" + inVar + "\n");
1609 bw.write(" Dynamic vars to manage: " + fsen.getDynamicVarSet() + "\n");
1611 bw.write(" out-set: " + fsen.getOutVarSet() + "\n");
1613 bw.write(" local parent: " + fsen.getLocalParent() + "\n");
1614 bw.write(" local children: " + fsen.getLocalChildren() + "\n");
1616 bw.write(" possible parents: " + fsen.getParents() + "\n");
1617 bw.write(" possible children: " + fsen.getChildren() + "\n");