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 private Hashtable<FlatNode, ContextTaskNames> fn2contextTaskNames;
67 // get the flat method that contains any given flat node
68 private Hashtable<FlatNode, FlatMethod> fn2fm;
70 // temporal data structures to track analysis progress.
71 static private int uniqueLockSetId = 0;
72 // mapping of a conflict graph to its compiled lock
73 private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraph2SESELock;
74 // mapping of a sese block to its conflict graph
75 private Hashtable<FlatNode, ConflictGraph> sese2conflictGraph;
77 public static int maxSESEage = -1;
79 public int getMaxSESEage() {
84 public CodePlan getCodePlan(FlatNode fn) {
85 CodePlan cp = codePlans.get(fn);
89 public Set<FlatNode> getNodesWithPlans() {
90 return codePlans.keySet();
93 public ContextTaskNames getContextTaskNames( FlatMethod fm ) {
94 ContextTaskNames out = fn2contextTaskNames.get( fm );
96 out = new ContextTaskNames();
101 public ContextTaskNames getContextTaskNames( FlatSESEEnterNode fsen ) {
102 ContextTaskNames out = fn2contextTaskNames.get( fsen );
104 out = new ContextTaskNames();
109 public FlatMethod getContainingFlatMethod( FlatNode fn ) {
110 FlatMethod fm = fn2fm.get( fn );
115 public DisjointAnalysis getDisjointAnalysis() {
116 return disjointAnalysisTaints;
120 public OoOJavaAnalysis(State state,
124 ArrayReferencees arrayReferencees) {
126 double timeStartAnalysis = (double) System.nanoTime();
129 this.typeUtil = typeUtil;
130 this.callGraph = callGraph;
131 this.maxSESEage = state.OOO_MAXSESEAGE;
133 livenessGlobalView = new Hashtable<FlatNode, Set<TempDescriptor>>();
134 livenessVirtualReads = new Hashtable<FlatNode, Set<TempDescriptor>>();
135 variableResults = new Hashtable<FlatNode, VarSrcTokTable>();
136 notAvailableResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
137 codePlans = new Hashtable<FlatNode, CodePlan>();
138 wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
139 notAvailableIntoSESE = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
140 sese2conflictGraph = new Hashtable<FlatNode, ConflictGraph>();
141 conflictGraph2SESELock = new Hashtable<ConflictGraph, HashSet<SESELock>>();
142 fn2contextTaskNames = new Hashtable<FlatNode, ContextTaskNames>();
144 // add all methods transitively reachable from the
145 // source's main to set for analysis
146 MethodDescriptor mdSourceEntry = typeUtil.getMain();
147 FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
149 descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
151 descriptorsToAnalyze.add(mdSourceEntry);
153 // 0th pass, setup a useful mapping of any flat node to the
154 // flat method it is a part of
155 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
156 while (methItr.hasNext()) {
157 Descriptor d = methItr.next();
158 FlatMethod fm = state.getMethodFlat( d );
159 buildFlatNodeToFlatMethod( fm );
162 // 1st pass, find basic rblock relations & potential stall sites
163 rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
164 VarSrcTokTable.rblockRel = rblockRel;
166 // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
167 methItr = descriptorsToAnalyze.iterator();
168 while (methItr.hasNext()) {
169 Descriptor d = methItr.next();
170 FlatMethod fm = state.getMethodFlat(d);
172 // note we can't use the general liveness analysis already in
173 // the compiler because this analysis is task-aware
174 livenessAnalysisBackward(fm);
177 // 3rd pass, variable analysis
178 methItr = descriptorsToAnalyze.iterator();
179 while (methItr.hasNext()) {
180 Descriptor d = methItr.next();
181 FlatMethod fm = state.getMethodFlat(d);
183 // starting from roots do a forward, fixed-point
184 // variable analysis for refinement and stalls
185 variableAnalysisForward(fm);
188 // 4th pass, compute liveness contribution from
189 // virtual reads discovered in variable pass
190 methItr = descriptorsToAnalyze.iterator();
191 while (methItr.hasNext()) {
192 Descriptor d = methItr.next();
193 FlatMethod fm = state.getMethodFlat(d);
194 livenessAnalysisBackward(fm);
197 // 5th pass, use disjointness with NO FLAGGED REGIONS
198 // to compute taints and effects
199 disjointAnalysisTaints =
200 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null,
202 true ); // suppress output--this is an intermediate pass
204 // 6th pass, not available analysis FOR VARIABLES!
205 methItr = descriptorsToAnalyze.iterator();
206 while (methItr.hasNext()) {
207 Descriptor d = methItr.next();
208 FlatMethod fm = state.getMethodFlat(d);
210 // compute what is not available at every program
211 // point, in a forward fixed-point pass
212 notAvailableForward(fm);
215 // 7th pass, make conflict graph
216 // conflict graph is maintained by each parent sese,
217 // where its' own stall sites and children may appear
218 Set<FlatSESEEnterNode> allSESEs=rblockRel.getAllSESEs();
219 for (Iterator iterator = allSESEs.iterator(); iterator.hasNext();) {
221 FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
222 if (!parent.getIsLeafSESE()) {
224 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
225 ConflictGraph conflictGraph = sese2conflictGraph.get(parent);
226 if (conflictGraph == null) {
227 conflictGraph = new ConflictGraph(state);
230 Set<FlatSESEEnterNode> children = parent.getChildren();
231 for (Iterator iterator2 = children.iterator(); iterator2.hasNext();) {
232 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
233 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(child);
234 conflictGraph.addLiveIn(taint2Effects);
235 sese2conflictGraph.put(parent, conflictGraph);
240 Iterator descItr = descriptorsToAnalyze.iterator();
241 while (descItr.hasNext()) {
242 Descriptor d = (Descriptor) descItr.next();
243 FlatMethod fm = state.getMethodFlat(d);
245 makeConflictGraph(fm);
250 // 8th pass, calculate all possible conflicts without using
251 // reachability info and identify set of FlatNew that next
252 // disjoint reach. analysis should flag
253 Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
254 calculateConflicts(sitesToFlag, false);
258 // 9th pass, ask disjoint analysis to compute reachability
259 // for objects that may cause heap conflicts so the most
260 // efficient method to deal with conflict can be computed
262 disjointAnalysisReach =
263 new DisjointAnalysis(state, typeUtil, callGraph, liveness,
264 arrayReferencees, sitesToFlag,
265 null // don't do effects analysis again!
268 // 10th pass, calculate conflicts with reachability info
269 calculateConflicts(null, true);
272 // 11th pass, compiling locks
275 // 12th pass, compute a plan for code injections
276 methItr = descriptorsToAnalyze.iterator();
277 while (methItr.hasNext()) {
278 Descriptor d = methItr.next();
279 FlatMethod fm = state.getMethodFlat(d);
280 codePlansForward(fm);
284 // splice new IR nodes into graph after all
285 // analysis passes are complete
286 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
287 while (spliceItr.hasNext()) {
288 Map.Entry me = (Map.Entry) spliceItr.next();
289 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
290 fwdvn.spliceIntoIR();
294 if (state.OOODEBUG) {
297 disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt");
298 writeConflictGraph();
299 } catch (IOException e) {}
303 System.out.println("\n\n\n##########################################################\n"+
304 "Warning, lots of code changes going on, OoOJava and RCR/DFJ\n"+
305 "systems are being cleaned up. Until the analyses and code gen\n"+
306 "are fully altered and coordinated, these systems will not run\n"+
307 "to completion. Partial stable check-ins are necessary to manage\n"+
308 "the number of files getting touched.\n"+
309 "##########################################################" );
314 private void buildFlatNodeToFlatMethod( FlatMethod fm ) {
315 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
316 flatNodesToVisit.add( fm.getFlatExit() );
318 Set<FlatNode> flatNodesVisited = new HashSet<FlatNode>();
320 while( !flatNodesToVisit.isEmpty() ) {
321 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
322 flatNodesToVisit.remove( fn );
323 flatNodesVisited.add( fn );
327 for( int i = 0; i < fn.numNext(); i++ ) {
328 FlatNode nn = fn.getNext( i );
329 if( !flatNodesVisited.contains( nn ) ) {
330 flatNodesToVisit.add( nn );
339 * Iterator iter = sese2conflictGraph.entrySet().iterator(); while
340 * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn =
341 * (FlatNode) e.getKey(); ConflictGraph conflictGraph = (ConflictGraph)
343 * System.out.println("---------------------------------------");
344 * System.out.println("CONFLICT GRAPH for " + fn); Set<String> keySet =
345 * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator();
346 * iterator.hasNext();) { String key = (String) iterator.next();
347 * ConflictNode node = conflictGraph.id2cn.get(key);
348 * System.out.println("key=" + key + " \n" + node.toStringAllEffects()); } }
354 private void writeFile(Set<FlatNew> sitesToFlag) {
357 BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt"));
359 for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext();) {
360 FlatNew fn = (FlatNew) iterator.next();
364 } catch (IOException e) {
371 private void livenessAnalysisBackward(FlatMethod fm) {
373 // flow backward across nodes to compute liveness, and
374 // take special care with sese enter/exit nodes that
375 // alter this from normal liveness analysis
376 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
377 flatNodesToVisit.add( fm.getFlatExit() );
379 while( !flatNodesToVisit.isEmpty() ) {
380 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
381 flatNodesToVisit.remove( fn );
383 Set<TempDescriptor> prev = livenessGlobalView.get( fn );
385 // merge sets from control flow joins
386 Set<TempDescriptor> livein = new HashSet<TempDescriptor>();
387 for (int i = 0; i < fn.numNext(); i++) {
388 FlatNode nn = fn.getNext( i );
389 Set<TempDescriptor> s = livenessGlobalView.get( nn );
395 Set<TempDescriptor> curr = liveness_nodeActions( fn, livein );
397 // if a new result, schedule backward nodes for analysis
398 if( !curr.equals( prev ) ) {
399 livenessGlobalView.put( fn, curr );
401 for( int i = 0; i < fn.numPrev(); i++ ) {
402 FlatNode nn = fn.getPrev( i );
403 flatNodesToVisit.add( nn );
409 private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
410 Set<TempDescriptor> liveIn
412 switch( fn.kind() ) {
414 case FKind.FlatSESEEnterNode: {
415 // add whatever is live-in at a task enter to that
417 FlatSESEEnterNode fsen = (FlatSESEEnterNode)fn;
418 if( liveIn != null ) {
419 fsen.addInVarSet( liveIn );
421 // no break, should also execute default actions
425 // handle effects of statement in reverse, writes then reads
426 TempDescriptor[] writeTemps = fn.writesTemps();
427 for( int i = 0; i < writeTemps.length; ++i ) {
428 liveIn.remove( writeTemps[i] );
430 // if we are analyzing code declared directly in a task,
431 FlatSESEEnterNode fsen = rblockRel.getLocalInnerRBlock( fn );
433 // check to see if we are writing to variables that will
434 // be live-out at the task's exit (and therefore should
435 // go in the task's out-var set)
436 FlatSESEExitNode fsexn = fsen.getFlatExit();
437 Set<TempDescriptor> livetemps = livenessGlobalView.get( fsexn );
438 if( livetemps != null && livetemps.contains( writeTemps[i] ) ) {
439 fsen.addOutVar( writeTemps[i] );
444 TempDescriptor[] readTemps = fn.readsTemps();
445 for( int i = 0; i < readTemps.length; ++i ) {
446 liveIn.add( readTemps[i] );
449 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
450 if( virtualReadTemps != null ) {
451 liveIn.addAll( virtualReadTemps );
461 private void variableAnalysisForward(FlatMethod fm) {
463 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
464 flatNodesToVisit.add(fm);
466 while (!flatNodesToVisit.isEmpty()) {
467 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
468 flatNodesToVisit.remove(fn);
470 VarSrcTokTable prev = variableResults.get(fn);
472 // merge sets from control flow joins
473 VarSrcTokTable curr = new VarSrcTokTable();
474 for (int i = 0; i < fn.numPrev(); i++) {
475 FlatNode nn = fn.getPrev(i);
476 VarSrcTokTable incoming = variableResults.get(nn);
477 curr.merge(incoming);
480 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
481 if( currentSESE == null ) {
482 currentSESE = rblockRel.getCallerProxySESE();
485 variable_nodeActions(fn, curr, currentSESE);
487 // if a new result, schedule forward nodes for analysis
488 if (!curr.equals(prev)) {
489 variableResults.put(fn, curr);
491 for (int i = 0; i < fn.numNext(); i++) {
492 FlatNode nn = fn.getNext(i);
493 flatNodesToVisit.add(nn);
499 private void variable_nodeActions(FlatNode fn,
500 VarSrcTokTable vstTable,
501 FlatSESEEnterNode currentSESE) {
505 case FKind.FlatSESEEnterNode: {
506 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
507 // ignore currently executing SESE, at this point
508 // the analysis considers a new instance is becoming
511 vstTable.assertConsistency();
515 case FKind.FlatSESEExitNode: {
516 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
518 // fsen is the child of currently executing tasks
519 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
521 // remap all of this child's children tokens to be
522 // from this child as the child exits
523 vstTable.remapChildTokens(fsen);
525 // liveness virtual reads are things that might be
526 // written by an SESE and should be added to the in-set
527 // anything virtually read by this SESE should be pruned
528 // of parent or sibling sources
529 Set<TempDescriptor> liveVars = livenessGlobalView.get(fn);
530 Set<TempDescriptor> fsenVirtReads =
531 vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen,
534 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
535 if (fsenVirtReadsOld != null) {
536 fsenVirtReads.addAll(fsenVirtReadsOld);
538 livenessVirtualReads.put(fn, fsenVirtReads);
540 // then all child out-set tokens are guaranteed
541 // to be filled in, so clobber those entries with
542 // the latest, clean sources
543 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
544 while (outVarItr.hasNext()) {
545 TempDescriptor outVar = outVarItr.next();
546 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
548 VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
549 vstTable.remove(outVar);
552 vstTable.assertConsistency();
556 case FKind.FlatOpNode: {
557 FlatOpNode fon = (FlatOpNode) fn;
559 if (fon.getOp().getOp() == Operation.ASSIGN) {
560 TempDescriptor lhs = fon.getDest();
561 TempDescriptor rhs = fon.getLeft();
563 vstTable.remove(lhs);
565 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
567 Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
568 while (itr.hasNext()) {
569 VariableSourceToken vst = itr.next();
571 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
574 // when we do x = y for variables, just copy over from a child,
575 // there are two cases:
576 // 1. if the current task is the caller proxy, any local root is a child
578 currentSESE.getIsCallerProxySESE() &&
579 rblockRel.getLocalRootSESEs().contains( vst.getSESE() );
581 // 2. if the child task is a locally-defined child of the current task
582 boolean case2 = currentSESE.getLocalChildren().contains( vst.getSESE() );
584 if( case1 || case2 ) {
585 // if the source comes from a child, copy it over
586 forAddition.add( new VariableSourceToken( ts,
593 // otherwise, stamp it as us as the source
594 forAddition.add( new VariableSourceToken( ts,
603 vstTable.addAll( forAddition );
605 // only break if this is an ASSIGN op node,
606 // otherwise fall through to default case
607 vstTable.assertConsistency();
612 // note that FlatOpNode's that aren't ASSIGN
613 // fall through to this default case
615 TempDescriptor[] writeTemps = fn.writesTemps();
616 if( writeTemps.length > 0 ) {
618 // for now, when writeTemps > 1, make sure
619 // its a call node, programmer enforce only
620 // doing stuff like calling a print routine
621 if( writeTemps.length > 1 ) {
622 assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
626 vstTable.remove( writeTemps[0] );
628 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
629 ts.add( writeTemps[0] );
631 vstTable.add( new VariableSourceToken( ts,
639 vstTable.assertConsistency();
646 private void notAvailableForward(FlatMethod fm) {
648 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
649 flatNodesToVisit.add(fm);
651 while (!flatNodesToVisit.isEmpty()) {
652 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
653 flatNodesToVisit.remove(fn);
655 Set<TempDescriptor> prev = notAvailableResults.get(fn);
657 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
658 for (int i = 0; i < fn.numPrev(); i++) {
659 FlatNode nn = fn.getPrev(i);
660 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
661 if (notAvailIn != null) {
662 curr.addAll(notAvailIn);
666 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
667 if( currentSESE == null ) {
668 currentSESE = rblockRel.getCallerProxySESE();
671 notAvailable_nodeActions(fn, curr, currentSESE);
673 // if a new result, schedule forward nodes for analysis
674 if (!curr.equals(prev)) {
675 notAvailableResults.put(fn, curr);
677 for (int i = 0; i < fn.numNext(); i++) {
678 FlatNode nn = fn.getNext(i);
679 flatNodesToVisit.add(nn);
685 private void notAvailable_nodeActions(FlatNode fn,
686 Set<TempDescriptor> notAvailSet,
687 FlatSESEEnterNode currentSESE
690 // any temps that are removed from the not available set
691 // at this node should be marked in this node's code plan
692 // as temps to be grabbed at runtime!
696 case FKind.FlatSESEEnterNode: {
697 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
699 // keep a copy of what's not available into the SESE
700 // and restore it at the matching exit node
701 Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
702 Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
703 while (tdItr.hasNext()) {
704 notAvailCopy.add(tdItr.next());
706 notAvailableIntoSESE.put(fsen, notAvailCopy);
711 case FKind.FlatSESEExitNode: {
712 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
713 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
715 notAvailSet.addAll(fsen.getOutVarSet());
717 Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
718 assert notAvailIn != null;
719 notAvailSet.addAll(notAvailIn);
722 case FKind.FlatMethod: {
726 case FKind.FlatOpNode: {
727 FlatOpNode fon = (FlatOpNode) fn;
729 if (fon.getOp().getOp() == Operation.ASSIGN) {
730 TempDescriptor lhs = fon.getDest();
731 TempDescriptor rhs = fon.getLeft();
733 // copy makes lhs same availability as rhs
734 if (notAvailSet.contains(rhs)) {
735 notAvailSet.add(lhs);
737 notAvailSet.remove(lhs);
740 // only break if this is an ASSIGN op node,
741 // otherwise fall through to default case
746 // note that FlatOpNode's that aren't ASSIGN
747 // fall through to this default case
749 TempDescriptor[] writeTemps = fn.writesTemps();
750 for (int i = 0; i < writeTemps.length; i++) {
751 TempDescriptor wTemp = writeTemps[i];
752 notAvailSet.remove(wTemp);
754 TempDescriptor[] readTemps = fn.readsTemps();
755 for (int i = 0; i < readTemps.length; i++) {
756 TempDescriptor rTemp = readTemps[i];
757 notAvailSet.remove(rTemp);
759 // if this variable has exactly one source, potentially
760 // get other things from this source as well
761 VarSrcTokTable vstTable = variableResults.get(fn);
763 VSTWrapper vstIfStatic = new VSTWrapper();
764 Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
766 if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
768 VariableSourceToken vst = vstIfStatic.vst;
770 Iterator<VariableSourceToken> availItr =
771 vstTable.get(vst.getSESE(), vst.getAge()).iterator();
773 // look through things that are also available from same source
774 while (availItr.hasNext()) {
775 VariableSourceToken vstAlsoAvail = availItr.next();
777 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
778 while (refVarItr.hasNext()) {
779 TempDescriptor refVarAlso = refVarItr.next();
781 // if a variable is available from the same source, AND it ALSO
782 // only comes from one statically known source, mark it available
783 VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
784 Integer srcTypeAlso =
785 vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed);
786 if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
787 notAvailSet.remove(refVarAlso);
799 private void codePlansForward(FlatMethod fm) {
801 // start from flat method top, visit every node in
802 // method exactly once
803 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
804 flatNodesToVisit.add(fm);
806 Set<FlatNode> visited = new HashSet<FlatNode>();
808 while (!flatNodesToVisit.isEmpty()) {
809 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
810 FlatNode fn = fnItr.next();
812 flatNodesToVisit.remove(fn);
815 // use incoming results as "dot statement" or just
816 // before the current statement
817 VarSrcTokTable dotSTtable = new VarSrcTokTable();
818 for (int i = 0; i < fn.numPrev(); i++) {
819 FlatNode nn = fn.getPrev(i);
820 dotSTtable.merge(variableResults.get(nn));
823 // find dt-st notAvailableSet also
824 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
825 for (int i = 0; i < fn.numPrev(); i++) {
826 FlatNode nn = fn.getPrev(i);
827 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
828 if (notAvailIn != null) {
829 dotSTnotAvailSet.addAll(notAvailIn);
833 Set<TempDescriptor> dotSTlive = livenessGlobalView.get(fn);
835 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
836 if( currentSESE == null ) {
837 currentSESE = rblockRel.getCallerProxySESE();
840 codePlans_nodeActions(fm, fn,
841 dotSTlive, dotSTtable, dotSTnotAvailSet,
844 for (int i = 0; i < fn.numNext(); i++) {
845 FlatNode nn = fn.getNext(i);
847 if (!visited.contains(nn)) {
848 flatNodesToVisit.add(nn);
854 private void codePlans_nodeActions(FlatMethod fm,
856 Set<TempDescriptor> liveSetIn,
857 VarSrcTokTable vstTableIn,
858 Set<TempDescriptor> notAvailSetIn,
859 FlatSESEEnterNode currentSESE) {
861 CodePlan plan = new CodePlan(currentSESE);
865 case FKind.FlatSESEEnterNode: {
866 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
868 // track the source types of the in-var set so generated
869 // code at this SESE issue can compute the number of
870 // dependencies properly
871 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
872 while (inVarItr.hasNext()) {
873 TempDescriptor inVar = inVarItr.next();
875 // when we get to an SESE enter node we change the
876 // currentSESE variable of this analysis to the
877 // child that is declared by the enter node, so
878 // in order to classify in-vars correctly, pass
879 // the parent SESE in--at other FlatNode types just
880 // use the currentSESE
881 FlatSESEEnterNode parent = rblockRel.getLocalInnerRBlock( fn );
882 if( parent == null ) {
883 parent = rblockRel.getCallerProxySESE();
886 VSTWrapper vstIfStatic = new VSTWrapper();
887 Integer srcType = vstTableIn.getRefVarSrcType(inVar, parent, vstIfStatic);
889 // the current SESE needs a local space to track the dynamic
890 // variable and the child needs space in its SESE record
891 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
892 fsen.addDynamicInVar(inVar);
893 addDynamicVar( fsen, fm, inVar );
895 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
896 fsen.addStaticInVar(inVar);
897 VariableSourceToken vst = vstIfStatic.vst;
898 fsen.putStaticInVar2src(inVar, vst);
899 fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
901 assert srcType.equals(VarSrcTokTable.SrcType_READY);
902 fsen.addReadyInVar(inVar);
907 case FKind.FlatSESEExitNode: {
908 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
909 //TODO! Shouldn't there be a code plan for task exit
910 // where the exiting task calculates whether its own
911 // siblings need variables from its children, so the
912 // exiter should copy those variables into its own out-set
913 // and make the available?
916 case FKind.FlatOpNode: {
917 FlatOpNode fon = (FlatOpNode) fn;
919 if (fon.getOp().getOp() == Operation.ASSIGN) {
920 TempDescriptor lhs = fon.getDest();
921 TempDescriptor rhs = fon.getLeft();
923 // if this is an op node, don't stall, copy
924 // source and delay until we need to use value
926 // ask whether lhs and rhs sources are dynamic, static, etc.
927 VSTWrapper vstIfStatic = new VSTWrapper();
928 Integer lhsSrcType = vstTableIn.getRefVarSrcType(lhs, currentSESE, vstIfStatic);
929 Integer rhsSrcType = vstTableIn.getRefVarSrcType(rhs, currentSESE, vstIfStatic);
931 if (rhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
932 // if rhs is dynamic going in, lhs will definitely be dynamic
933 // going out of this node, so track that here
934 plan.addDynAssign( lhs, rhs );
935 addDynamicVar( currentSESE, fm, lhs );
936 addDynamicVar( currentSESE, fm, rhs );
938 } else if (lhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
939 // otherwise, if the lhs is dynamic, but the rhs is not, we
940 // need to update the variable's dynamic source as "current SESE"
941 plan.addDynAssign(lhs);
944 // only break if this is an ASSIGN op node,
945 // otherwise fall through to default case
950 // note that FlatOpNode's that aren't ASSIGN
951 // fall through to this default case
954 // a node with no live set has nothing to stall for
955 if (liveSetIn == null) {
959 TempDescriptor[] readarray = fn.readsTemps();
960 for (int i = 0; i < readarray.length; i++) {
961 TempDescriptor readtmp = readarray[i];
963 // ignore temps that are definitely available
964 // when considering to stall on it
965 if (!notAvailSetIn.contains(readtmp)) {
969 // check the source type of this variable
970 VSTWrapper vstIfStatic = new VSTWrapper();
971 Integer srcType = vstTableIn.getRefVarSrcType(readtmp, currentSESE, vstIfStatic);
973 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
974 // 1) It is not clear statically where this variable will
975 // come from, so dynamically we must keep track
976 // along various control paths, and therefore when we stall,
977 // just stall for the exact thing we need and move on
978 plan.addDynamicStall( readtmp );
979 addDynamicVar( currentSESE, fm, readtmp );
981 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
982 // 2) Single token/age pair: Stall for token/age pair, and copy
983 // all live variables with same token/age pair at the same
984 // time. This is the same stuff that the notavaialable analysis
985 // marks as now available.
986 VariableSourceToken vst = vstIfStatic.vst;
988 Iterator<VariableSourceToken> availItr =
989 vstTableIn.get(vst.getSESE(), vst.getAge()).iterator();
991 while (availItr.hasNext()) {
992 VariableSourceToken vstAlsoAvail = availItr.next();
994 // only grab additional stuff that is live
995 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
997 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
998 while (refVarItr.hasNext()) {
999 TempDescriptor refVar = refVarItr.next();
1000 if (liveSetIn.contains(refVar)) {
1001 copySet.add(refVar);
1005 if (!copySet.isEmpty()) {
1006 plan.addStall2CopySet(vstAlsoAvail, copySet);
1011 // the other case for srcs is READY, so do nothing
1014 // assert that everything being stalled for is in the
1015 // "not available" set coming into this flat node and
1016 // that every VST identified is in the possible "stall set"
1017 // that represents VST's from children SESE's
1025 // identify sese-age pairs that are statically useful
1026 // and should have an associated SESE variable in code
1027 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
1028 // AND ALWAYS GIVE NAMES TO LOCAL PARENTS
1029 Set<VariableSourceToken> staticSet = vstTableIn.get();
1030 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
1031 while (vstItr.hasNext()) {
1032 VariableSourceToken vst = vstItr.next();
1034 // the caller proxy generates useful analysis facts, but we
1035 // never need to generate another name for it in code (it is
1036 // ALWAYS the task executing the local method context)
1037 if( vst.getSESE().getIsCallerProxySESE() ) {
1041 SESEandAgePair sap = new SESEandAgePair( vst.getSESE(), vst.getAge() );
1042 sap.getSESE().mustTrackAtLeastAge( sap.getAge() );
1044 FlatSESEEnterNode sese = currentSESE;
1045 while( sese != null ) {
1046 addNeededStaticName( sese, fm, sap );
1047 sese = sese.getLocalParent();
1051 codePlans.put(fn, plan);
1053 // if any variables at this-node-*dot* have a static source (exactly one
1055 // but go to a dynamic source at next-node-*dot*, create a new IR graph
1056 // node on that edge to track the sources dynamically
1057 VarSrcTokTable thisVstTable = variableResults.get(fn);
1058 for (int i = 0; i < fn.numNext(); i++) {
1059 FlatNode nn = fn.getNext(i);
1060 VarSrcTokTable nextVstTable = variableResults.get(nn);
1061 Set<TempDescriptor> nextLiveIn = livenessGlobalView.get(nn);
1063 // the table can be null if it is one of the few IR nodes
1064 // completely outside of the root SESE scope
1065 if (nextVstTable != null && nextLiveIn != null) {
1067 Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
1068 thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, currentSESE);
1070 if (!readyOrStatic2dynamicSet.isEmpty()) {
1072 // either add these results to partial fixed-point result
1073 // or make a new one if we haven't made any here yet
1074 FlatEdge fe = new FlatEdge(fn, nn);
1075 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe);
1077 if (fwdvn == null) {
1078 fwdvn = new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, currentSESE);
1079 wdvNodesToSpliceIn.put(fe, fwdvn);
1081 fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet);
1088 private void addDynamicVar( FlatSESEEnterNode fsen,
1090 TempDescriptor var ) {
1093 if( fsen.getIsCallerProxySESE() ) {
1094 // attach the dynamic variable to track to
1095 // the flat method, so it can be declared at entry
1098 // otherwise the code context is a task body
1102 ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1104 ctn = new ContextTaskNames();
1107 ctn.addDynamicVar( var );
1108 fn2contextTaskNames.put( fnContext, ctn );
1111 private void addNeededStaticName( FlatSESEEnterNode fsen,
1113 SESEandAgePair sap ) {
1116 if( fsen.getIsCallerProxySESE() ) {
1117 // attach the dynamic variable to track to
1118 // the flat method, so it can be declared at entry
1121 // otherwise the code context is a task body
1125 ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1127 ctn = new ContextTaskNames();
1130 ctn.addNeededStaticName( sap );
1132 fn2contextTaskNames.put( fnContext, ctn );
1136 private void makeConflictGraph(FlatMethod fm) {
1138 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1139 flatNodesToVisit.add(fm);
1141 Set<FlatNode> visited = new HashSet<FlatNode>();
1143 while (!flatNodesToVisit.isEmpty()) {
1144 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1145 flatNodesToVisit.remove(fn);
1148 Set<FlatSESEEnterNode> currentSESEs =
1149 rblockRel.getPossibleExecutingRBlocks( fn );
1151 conflictGraph_nodeAction(fn, currentSESEs);
1153 // schedule forward nodes for analysis
1154 for (int i = 0; i < fn.numNext(); i++) {
1155 FlatNode nn = fn.getNext(i);
1156 if (!visited.contains(nn)) {
1157 flatNodesToVisit.add(nn);
1165 private void conflictGraph_nodeAction(FlatNode fn,
1166 Set<FlatSESEEnterNode> currentSESEs
1168 ConflictGraph conflictGraph;
1172 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1175 switch (fn.kind()) {
1178 case FKind.FlatFieldNode:
1179 case FKind.FlatElementNode: {
1181 if (fn instanceof FlatFieldNode) {
1182 FlatFieldNode ffn = (FlatFieldNode) fn;
1185 FlatElementNode fen = (FlatElementNode) fn;
1189 for( Iterator<FlatSESEEnterNode> itr = currentSESEs.iterator();
1192 FlatSESEEnterNode currentSESE = itr.next();
1194 conflictGraph = sese2conflictGraph.get(currentSESE);
1195 if (conflictGraph == null) {
1196 conflictGraph = new ConflictGraph(state);
1200 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1201 conflictGraph.addStallSite(taint2Effects, rhs);
1203 if (conflictGraph.id2cn.size() > 0) {
1204 sese2conflictGraph.put(currentSESE, conflictGraph);
1210 case FKind.FlatSetFieldNode:
1211 case FKind.FlatSetElementNode: {
1213 if (fn instanceof FlatSetFieldNode) {
1214 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1215 lhs = fsfn.getDst();
1216 rhs = fsfn.getSrc();
1218 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1219 lhs = fsen.getDst();
1220 rhs = fsen.getSrc();
1223 for( Iterator<FlatSESEEnterNode> itr = currentSESEs.iterator();
1226 FlatSESEEnterNode currentSESE = itr.next();
1228 conflictGraph = sese2conflictGraph.get(currentSESE);
1229 if (conflictGraph == null) {
1230 conflictGraph = new ConflictGraph(state);
1233 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1234 conflictGraph.addStallSite(taint2Effects, rhs);
1235 conflictGraph.addStallSite(taint2Effects, lhs);
1237 if (conflictGraph.id2cn.size() > 0) {
1238 sese2conflictGraph.put(currentSESE, conflictGraph);
1244 case FKind.FlatCall: {
1245 FlatCall fc = (FlatCall) fn;
1248 for( Iterator<FlatSESEEnterNode> itr = currentSESEs.iterator();
1251 FlatSESEEnterNode currentSESE = itr.next();
1253 conflictGraph = sese2conflictGraph.get(currentSESE);
1254 if (conflictGraph == null) {
1255 conflictGraph = new ConflictGraph(state);
1258 // collects effects of stall site and generates stall site node
1259 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1261 conflictGraph.addStallSite(taint2Effects, lhs);
1262 if (conflictGraph.id2cn.size() > 0) {
1263 sese2conflictGraph.put(currentSESE, conflictGraph);
1272 private void calculateConflicts( Set<FlatNew> sitesToFlag,
1273 boolean useReachInfo ) {
1275 // decide fine-grain edge or coarse-grain edge among all vertexes by
1276 // pair-wise comparison
1277 Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
1278 while (seseIter.hasNext()) {
1279 FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next();
1280 ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
1283 // clear current conflict before recalculating with reachability info
1284 conflictGraph.clearAllConflictEdge();
1285 conflictGraph.setDisJointAnalysis(disjointAnalysisReach);
1286 conflictGraph.setFMEnclosing(sese.getfmEnclosing());
1288 conflictGraph.analyzeConflicts(sitesToFlag, useReachInfo);
1289 sese2conflictGraph.put(sese, conflictGraph);
1294 private void writeConflictGraph() {
1295 Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
1296 while (keyEnum.hasMoreElements()) {
1297 FlatNode key = (FlatNode) keyEnum.nextElement();
1298 ConflictGraph cg = sese2conflictGraph.get(key);
1300 if (cg.hasConflictEdge()) {
1301 cg.writeGraph("ConflictGraphFor" + key, false);
1303 } catch (IOException e) {
1304 System.out.println("Error writing");
1310 private void synthesizeLocks() {
1311 Set<Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
1312 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
1313 Entry<FlatNode, ConflictGraph> graphEntry = (Entry<FlatNode, ConflictGraph>) iterator.next();
1314 FlatNode sese = graphEntry.getKey();
1315 ConflictGraph conflictGraph = graphEntry.getValue();
1316 calculateCovering(conflictGraph);
1320 private void calculateCovering(ConflictGraph conflictGraph) {
1321 uniqueLockSetId = 0; // reset lock counter for every new conflict graph
1322 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1323 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1324 HashSet<SESELock> lockSet = new HashSet<SESELock>();
1326 Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1327 for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
1328 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1329 if (conflictEdge.isCoarseEdge()) {
1330 coarseToCover.add(conflictEdge);
1332 fineToCover.add(conflictEdge);
1336 HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
1337 toCover.addAll(fineToCover);
1338 toCover.addAll(coarseToCover);
1340 while (!toCover.isEmpty()) {
1342 SESELock seseLock = new SESELock();
1343 seseLock.setID(uniqueLockSetId++);
1347 do { // fine-grained edge
1351 for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) {
1354 ConflictEdge edge = (ConflictEdge) iterator.next();
1355 if (seseLock.getConflictNodeSet().size() == 0) {
1357 if (seseLock.isWriteNode(edge.getVertexU())) {
1358 // mark as fine_write
1359 if (edge.getVertexU().isStallSiteNode()) {
1360 type = ConflictNode.PARENT_WRITE;
1362 type = ConflictNode.FINE_WRITE;
1364 seseLock.addConflictNode(edge.getVertexU(), type);
1366 // mark as fine_read
1367 if (edge.getVertexU().isStallSiteNode()) {
1368 type = ConflictNode.PARENT_READ;
1370 type = ConflictNode.FINE_READ;
1372 seseLock.addConflictNode(edge.getVertexU(), type);
1374 if (edge.getVertexV() != edge.getVertexU()) {
1375 if (seseLock.isWriteNode(edge.getVertexV())) {
1376 // mark as fine_write
1377 if (edge.getVertexV().isStallSiteNode()) {
1378 type = ConflictNode.PARENT_WRITE;
1380 type = ConflictNode.FINE_WRITE;
1382 seseLock.addConflictNode(edge.getVertexV(), type);
1384 // mark as fine_read
1385 if (edge.getVertexV().isStallSiteNode()) {
1386 type = ConflictNode.PARENT_READ;
1388 type = ConflictNode.FINE_READ;
1390 seseLock.addConflictNode(edge.getVertexV(), type);
1394 seseLock.addConflictEdge(edge);
1395 fineToCover.remove(edge);
1396 break;// exit iterator loop
1397 }// end of initial setup
1399 ConflictNode newNode;
1400 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1401 // new node has a fine-grained edge to all current node
1402 // If there is a coarse grained edge where need a fine edge, it's
1403 // okay to add the node
1404 // but the edge must remain uncovered.
1408 if (seseLock.containsConflictNode(newNode)) {
1409 seseLock.addEdge(edge);
1410 fineToCover.remove(edge);
1414 if (seseLock.isWriteNode(newNode)) {
1415 if (newNode.isStallSiteNode()) {
1416 type = ConflictNode.PARENT_WRITE;
1418 type = ConflictNode.FINE_WRITE;
1420 seseLock.setNodeType(newNode, type);
1422 if (newNode.isStallSiteNode()) {
1423 type = ConflictNode.PARENT_READ;
1425 type = ConflictNode.FINE_READ;
1427 seseLock.setNodeType(newNode, type);
1430 seseLock.addEdge(edge);
1431 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1432 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1433 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1435 // mark all fine edges between new node and nodes in the group as
1437 if (!conflictEdge.getVertexU().equals(newNode)) {
1438 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1440 seseLock.addConflictEdge(conflictEdge);
1441 fineToCover.remove(conflictEdge);
1443 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1444 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1446 seseLock.addConflictEdge(conflictEdge);
1447 fineToCover.remove(conflictEdge);
1453 break;// exit iterator loop
1458 HashSet<ConflictEdge> notCovered=new HashSet<ConflictEdge>();
1462 for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) {
1464 ConflictEdge edge = (ConflictEdge) iterator.next();
1465 if (seseLock.getConflictNodeSet().size() == 0) {
1467 if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
1468 // node has a coarse-grained edge with itself
1469 if (!(edge.getVertexU().isStallSiteNode())) {
1470 // and it is not parent
1471 type = ConflictNode.SCC;
1474 type = ConflictNode.PARENT_COARSE;
1476 type = ConflictNode.PARENT_WRITE;
1479 seseLock.addConflictNode(edge.getVertexU(), type);
1481 if (edge.getVertexU().isStallSiteNode()) {
1483 type = ConflictNode.PARENT_COARSE;
1485 if (edge.getVertexU().getWriteEffectSet().isEmpty()) {
1486 type = ConflictNode.PARENT_READ;
1488 type = ConflictNode.PARENT_WRITE;
1492 type = ConflictNode.COARSE;
1494 seseLock.addConflictNode(edge.getVertexU(), type);
1496 if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
1497 // node has a coarse-grained edge with itself
1498 if (!(edge.getVertexV().isStallSiteNode())) {
1499 // and it is not parent
1500 type = ConflictNode.SCC;
1503 type = ConflictNode.PARENT_COARSE;
1505 type = ConflictNode.PARENT_WRITE;
1508 seseLock.addConflictNode(edge.getVertexV(), type);
1510 if (edge.getVertexV().isStallSiteNode()) {
1512 type = ConflictNode.PARENT_COARSE;
1514 if (edge.getVertexV().getWriteEffectSet().isEmpty()) {
1515 type = ConflictNode.PARENT_READ;
1517 type = ConflictNode.PARENT_WRITE;
1521 type = ConflictNode.COARSE;
1523 seseLock.addConflictNode(edge.getVertexV(), type);
1526 coarseToCover.remove(edge);
1527 seseLock.addConflictEdge(edge);
1528 break;// exit iterator loop
1529 }// end of initial setup
1531 ConflictNode newNode;
1532 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1533 // new node has a coarse-grained edge to all fine-read, fine-write,
1537 if (newNode.isInVarNode() && (!seseLock.hasSelfCoarseEdge(newNode))
1538 && seseLock.hasCoarseEdgeWithParentCoarse(newNode)) {
1539 // this case can't be covered by this queue
1540 coarseToCover.remove(edge);
1541 notCovered.add(edge);
1545 if (seseLock.containsConflictNode(newNode)) {
1546 seseLock.addEdge(edge);
1547 coarseToCover.remove(edge);
1551 if (seseLock.hasSelfCoarseEdge(newNode)) {
1553 if (newNode.isStallSiteNode()) {
1554 type = ConflictNode.PARENT_COARSE;
1556 type = ConflictNode.SCC;
1558 seseLock.setNodeType(newNode, type);
1560 if (newNode.isStallSiteNode()) {
1561 type = ConflictNode.PARENT_COARSE;
1563 type = ConflictNode.COARSE;
1565 seseLock.setNodeType(newNode, type);
1568 seseLock.addEdge(edge);
1569 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1570 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1571 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1572 // mark all coarse edges between new node and nodes in the group
1574 if (!conflictEdge.getVertexU().equals(newNode)) {
1575 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1577 seseLock.addConflictEdge(conflictEdge);
1578 coarseToCover.remove(conflictEdge);
1580 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1581 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1583 seseLock.addConflictEdge(conflictEdge);
1584 coarseToCover.remove(conflictEdge);
1589 break;// exit iterator loop
1595 lockSet.add(seseLock);
1598 coarseToCover.addAll(notCovered);
1599 toCover.addAll(fineToCover);
1600 toCover.addAll(coarseToCover);
1604 conflictGraph2SESELock.put(conflictGraph, lockSet);
1607 public ConflictGraph getConflictGraph(FlatNode sese) {
1608 return sese2conflictGraph.get(sese);
1611 public Set<SESELock> getLockMappings(ConflictGraph graph) {
1612 return conflictGraph2SESELock.get(graph);
1615 public Set<FlatSESEEnterNode> getAllSESEs() {
1616 return rblockRel.getAllSESEs();
1619 public FlatSESEEnterNode getMainSESE() {
1620 return rblockRel.getMainSESE();
1623 public FlatSESEEnterNode getCallerProxySESE() {
1624 return rblockRel.getCallerProxySESE();
1628 public void writeReports(String timeReport) throws java.io.IOException {
1630 BufferedWriter bw = new BufferedWriter(new FileWriter("ooojReport_summary.txt"));
1631 bw.write("OoOJava Analysis Results\n\n");
1632 bw.write(timeReport + "\n\n");
1633 printSESEHierarchy(bw);
1638 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
1639 while (methItr.hasNext()) {
1640 MethodDescriptor md = methItr.next();
1641 FlatMethod fm = state.getMethodFlat(md);
1643 bw = new BufferedWriter(new FileWriter("ooojReport_" +
1644 md.getClassMethodName() +
1645 md.getSafeMethodDescriptor() +
1647 bw.write("OoOJava Results for " + md + "\n-------------------\n");
1649 bw.write("Dynamic vars to manage:\n " + getContextTaskNames( fm ).getDynamicVarSet() );
1651 bw.write("\n\nLive-In, Root View\n------------------\n" + fm.printMethod(livenessGlobalView));
1652 bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults));
1653 bw.write("\n\nNot Available Results-Out\n---------------------\n" + fm.printMethod(notAvailableResults));
1654 bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans));
1660 private void printSESEHierarchy(BufferedWriter bw) throws java.io.IOException {
1661 bw.write("SESE Local Hierarchy\n--------------\n");
1662 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getLocalRootSESEs().iterator();
1663 while (rootItr.hasNext()) {
1664 FlatSESEEnterNode root = rootItr.next();
1665 printSESEHierarchyTree(bw, root, 0);
1669 private void printSESEHierarchyTree(BufferedWriter bw,
1670 FlatSESEEnterNode fsen,
1672 ) throws java.io.IOException {
1673 for (int i = 0; i < depth; ++i) {
1676 bw.write("- " + fsen.getPrettyIdentifier() + "\n");
1678 Iterator<FlatSESEEnterNode> childItr = fsen.getLocalChildren().iterator();
1679 while (childItr.hasNext()) {
1680 FlatSESEEnterNode fsenChild = childItr.next();
1681 printSESEHierarchyTree(bw, fsenChild, depth + 1);
1685 private void printSESEInfo(BufferedWriter bw) throws java.io.IOException {
1686 bw.write("\nSESE info\n-------------\n");
1687 Iterator<FlatSESEEnterNode> fsenItr = rblockRel.getAllSESEs().iterator();
1688 while( fsenItr.hasNext() ) {
1689 FlatSESEEnterNode fsen = fsenItr.next();
1691 bw.write("SESE " + fsen.getPrettyIdentifier());
1692 if( fsen.getIsLeafSESE() ) {
1693 bw.write(" (leaf)");
1697 bw.write(" in-set: " + fsen.getInVarSet() + "\n");
1698 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1699 while (tItr.hasNext()) {
1700 TempDescriptor inVar = tItr.next();
1701 if (fsen.getReadyInVarSet().contains(inVar)) {
1702 bw.write(" (ready) " + inVar + "\n");
1704 if (fsen.getStaticInVarSet().contains(inVar)) {
1705 bw.write(" (static) " + inVar + " from " + fsen.getStaticInVarSrc(inVar) + "\n");
1707 if (fsen.getDynamicInVarSet().contains(inVar)) {
1708 bw.write(" (dynamic)" + inVar + "\n");
1712 bw.write(" Dynamic vars to manage: " + getContextTaskNames( fsen ).getDynamicVarSet() + "\n");
1714 bw.write(" out-set: " + fsen.getOutVarSet() + "\n");
1716 bw.write(" local parent: " + fsen.getLocalParent() + "\n");
1717 bw.write(" local children: " + fsen.getLocalChildren() + "\n");
1719 bw.write(" possible parents: " + fsen.getParents() + "\n");
1720 bw.write(" possible children: " + fsen.getChildren() + "\n");