1 package Analysis.OoOJava;
7 import Analysis.CallGraph.*;
8 import Analysis.Disjoint.*;
9 import Analysis.Pointer.*;
13 public class OoOJavaAnalysis {
15 // data from the compiler
17 private TypeUtil typeUtil;
18 private CallGraph callGraph;
19 private RBlockRelationAnalysis rblockRel;
20 private HeapAnalysis disjointAnalysisTaints;
21 private DisjointAnalysis disjointAnalysisReach;
22 private BuildStateMachines buildStateMachines;
24 private Set<MethodDescriptor> descriptorsToAnalyze;
26 private Hashtable<FlatNode, Set<TempDescriptor>> livenessGlobalView;
27 private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
28 private Hashtable<FlatNode, VarSrcTokTable> variableResults;
29 private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
30 private Hashtable<FlatNode, CodePlan> codePlans;
32 private Hashtable<FlatSESEEnterNode, Set<TempDescriptor>> notAvailableIntoSESE;
34 private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
36 private Hashtable<FlatNode, ContextTaskNames> fn2contextTaskNames;
38 // get the flat method that contains any given flat node
39 private Hashtable<FlatNode, FlatMethod> fn2fm;
41 // temporal data structures to track analysis progress.
42 static private int uniqueLockSetId = 0;
43 // mapping of a conflict graph to its compiled lock
44 private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraph2SESELock;
45 // mapping of a sese block to its conflict graph
46 private Hashtable<FlatNode, ConflictGraph> sese2conflictGraph;
48 public static int maxSESEage = -1;
50 public int getMaxSESEage() {
55 public CodePlan getCodePlan(FlatNode fn) {
56 CodePlan cp = codePlans.get(fn);
60 public Set<FlatNode> getNodesWithPlans() {
61 return codePlans.keySet();
64 public ContextTaskNames getContextTaskNames( FlatMethod fm ) {
65 ContextTaskNames out = fn2contextTaskNames.get( fm );
67 out = new ContextTaskNames();
72 public ContextTaskNames getContextTaskNames( FlatSESEEnterNode fsen ) {
73 ContextTaskNames out = fn2contextTaskNames.get( fsen );
75 out = new ContextTaskNames();
80 public FlatMethod getContainingFlatMethod( FlatNode fn ) {
81 FlatMethod fm = fn2fm.get( fn );
86 public HeapAnalysis getDisjointAnalysis() {
87 return disjointAnalysisTaints;
90 public BuildStateMachines getBuildStateMachines() {
91 return buildStateMachines;
94 public OoOJavaAnalysis( State state,
98 ArrayReferencees arrayReferencees ) {
100 State.logEvent("Starting OoOJavaAnalysis");
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>>();
115 fn2contextTaskNames = new Hashtable<FlatNode, ContextTaskNames>();
116 fn2fm = new Hashtable<FlatNode, FlatMethod>();
118 // state machines support heap examiners with
119 // state transitions to improve precision
121 buildStateMachines = new BuildStateMachines();
124 // add all methods transitively reachable from the
125 // source's main to set for analysis
126 MethodDescriptor mdSourceEntry = typeUtil.getMain();
127 FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
129 descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
131 descriptorsToAnalyze.add(mdSourceEntry);
134 // 0th pass, setup a useful mapping of any flat node to the
135 // flat method it is a part of
136 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
137 while (methItr.hasNext()) {
138 Descriptor d = methItr.next();
139 FlatMethod fm = state.getMethodFlat( d );
140 buildFlatNodeToFlatMethod( fm );
142 State.logEvent("OoOJavaAnalysis Oth pass completed");
144 // 1st pass, find basic rblock relations & potential stall sites
145 rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
146 VarSrcTokTable.rblockRel = rblockRel;
148 State.logEvent("OoOJavaAnalysis 1st pass completed");
151 // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
152 Iterator<FlatSESEEnterNode> seseItr = rblockRel.getLocalRootSESEs().iterator();
153 while (seseItr.hasNext()) {
154 FlatSESEEnterNode sese = seseItr.next();
155 livenessAnalysisBackward(sese,liveness);
159 State.logEvent("OoOJavaAnalysis 2nd pass completed");
161 // 3rd pass, variable analysis
162 methItr = rblockRel.getMethodsWithSESEs().iterator();
163 while (methItr.hasNext()) {
164 Descriptor d = methItr.next();
165 FlatMethod fm = state.getMethodFlat(d);
166 // starting from roots do a forward, fixed-point
167 // variable analysis for refinement and stalls
168 variableAnalysisForward(fm);
171 State.logEvent("OoOJavaAnalysis 3rd pass completed");
173 // 4th pass, compute liveness contribution from
174 // virtual reads discovered in variable pass
175 seseItr = rblockRel.getLocalRootSESEs().iterator();
176 while (seseItr.hasNext()) {
177 FlatSESEEnterNode sese = seseItr.next();
178 livenessAnalysisBackward(sese,liveness);
181 State.logEvent("OoOJavaAnalysis 4th pass completed");
183 // 5th pass, use disjointness with NO FLAGGED REGIONS
184 // to compute taints and effects
186 disjointAnalysisTaints = new Pointer(state, typeUtil, callGraph, rblockRel, liveness, buildStateMachines);
187 ((Pointer)disjointAnalysisTaints).doAnalysis();
189 disjointAnalysisTaints =
190 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null,
191 rblockRel, buildStateMachines,
192 true ); // suppress output--this is an intermediate pass
194 State.logEvent("OoOJavaAnalysis 5th pass completed");
196 // 6th pass, not available analysis FOR VARIABLES!
197 methItr = rblockRel.getMethodsWithSESEs().iterator();
198 while (methItr.hasNext()) {
199 Descriptor d = methItr.next();
200 FlatMethod fm = state.getMethodFlat(d);
201 // compute what is not available at every program
202 // point, in a forward fixed-point pass
203 notAvailableForward(fm);
205 State.logEvent("OoOJavaAnalysis 6th pass completed");
206 // 7th pass, start conflict graphs where a parent's graph has a
207 // node for possibly conflicting children and its own stall sites
208 startConflictGraphs();
209 State.logEvent("OoOJavaAnalysis 7th pass completed");
210 // 8th pass, calculate all possible conflicts without using
211 // reachability info and identify set of FlatNew that next
212 // disjoint reach. analysis should flag
213 Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
214 calculateConflicts(sitesToFlag, false);
215 State.logEvent("OoOJavaAnalysis 8th pass completed");
217 // 9th pass, ask disjoint analysis to compute reachability
218 // for objects that may cause heap conflicts so the most
219 // efficient method to deal with conflict can be computed
221 disjointAnalysisReach =
222 new DisjointAnalysis(state, typeUtil, callGraph, liveness,
223 arrayReferencees, sitesToFlag,
224 null, // don't do effects analysis again!
225 null, // no BuildStateMachines needed
226 !state.OOODEBUG // only print out in OoOJava debug mode
228 State.logEvent("OoOJavaAnalysis 9th pass completed");
229 // 10th pass, calculate conflicts with reachability info
230 calculateConflicts(null, true);
231 State.logEvent("OoOJavaAnalysis 10th pass completed");
233 // in RCR/DFJ we want to do some extra processing on the
234 // state machines before they get handed off to code gen,
235 // and we're doing the same effect-conflict traversal needed
236 // to identify heap examiners that are weakly connected, so
237 // accomplish both at the same time
238 pruneMachinesAndFindWeaklyConnectedExaminers();
239 State.logEvent("OoOJavaAnalysis RCR pruneMachines pass completed");
242 // 11th pass, compiling memory Qs! The name "lock" is a legacy
243 // term for the heap dependence queue, or memQ as the runtime calls it
245 State.logEvent("OoOJavaAnalysis 11th pass completed");
247 // 12th pass, compute a plan for code injections
248 methItr = descriptorsToAnalyze.iterator();
249 while (methItr.hasNext()) {
250 Descriptor d = methItr.next();
251 FlatMethod fm = state.getMethodFlat(d);
252 codePlansForward(fm,liveness);
255 State.logEvent("OoOJavaAnalysis 12th pass completed");
257 // splice new IR nodes into graph after all
258 // analysis passes are complete
259 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
260 while (spliceItr.hasNext()) {
261 Map.Entry me = (Map.Entry) spliceItr.next();
262 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
263 fwdvn.spliceIntoIR();
265 State.logEvent("OoOJavaAnalysis 13th pass completed");
267 if (state.OOODEBUG) {
270 disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt");
271 writeConflictGraph();
272 } catch (IOException e) {}
274 State.logEvent("OoOJavaAnalysis completed");
278 private void buildFlatNodeToFlatMethod( FlatMethod fm ) {
279 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
280 flatNodesToVisit.add( fm );
282 Set<FlatNode> flatNodesVisited = new HashSet<FlatNode>();
284 while( !flatNodesToVisit.isEmpty() ) {
285 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
286 flatNodesToVisit.remove( fn );
287 flatNodesVisited.add( fn );
291 for( int i = 0; i < fn.numNext(); i++ ) {
292 FlatNode nn = fn.getNext( i );
293 if( !flatNodesVisited.contains( nn ) ) {
294 flatNodesToVisit.add( nn );
303 * Iterator iter = sese2conflictGraph.entrySet().iterator(); while
304 * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn =
305 * (FlatNode) e.getKey(); ConflictGraph conflictGraph = (ConflictGraph)
307 * System.out.println("---------------------------------------");
308 * System.out.println("CONFLICT GRAPH for " + fn); Set<String> keySet =
309 * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator();
310 * iterator.hasNext();) { String key = (String) iterator.next();
311 * ConflictNode node = conflictGraph.id2cn.get(key);
312 * System.out.println("key=" + key + " \n" + node.toStringAllEffects()); } }
318 private void writeFile(Set<FlatNew> sitesToFlag) {
321 BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt"));
323 for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext();) {
324 FlatNew fn = (FlatNew) iterator.next();
328 } catch (IOException e) {
335 private void livenessAnalysisBackward(FlatSESEEnterNode fsen,Liveness liveness) {
337 // flow backward across nodes to compute liveness, and
338 // take special care with sese enter/exit nodes that
339 // alter this from normal liveness analysis
340 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
341 // flatNodesToVisit.add( fm.getFlatExit() );
342 flatNodesToVisit.add(fsen.getFlatExit());
344 while( !flatNodesToVisit.isEmpty() ) {
345 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
346 flatNodesToVisit.remove( fn );
348 Set<TempDescriptor> prev = livenessGlobalView.get( fn );
350 // merge sets from control flow joins
351 Set<TempDescriptor> livein = new HashSet<TempDescriptor>();
352 for (int i = 0; i < fn.numNext(); i++) {
353 FlatNode nn = fn.getNext( i );
354 Set<TempDescriptor> s = livenessGlobalView.get( nn );
360 Set<TempDescriptor> curr = liveness_nodeActions( fn, livein, liveness );
362 // if a new result, schedule backward nodes for analysis
363 if( !curr.equals( prev ) ) {
366 livenessGlobalView.put( fn, curr );
367 for( int i = 0; i < fn.numPrev(); i++ ) {
368 FlatNode nn = fn.getPrev( i );
369 flatNodesToVisit.add( nn );
376 private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
377 Set<TempDescriptor> liveIn, Liveness liveness
379 switch( fn.kind() ) {
381 case FKind.FlatSESEEnterNode: {
382 // add whatever is live-in at a task enter to that
384 FlatSESEEnterNode fsen = (FlatSESEEnterNode)fn;
385 if( liveIn != null ) {
386 fsen.addInVarSet( liveIn );
388 // no break, should also execute default actions
392 // handle effects of statement in reverse, writes then reads
393 TempDescriptor[] writeTemps = fn.writesTemps();
394 for( int i = 0; i < writeTemps.length; ++i ) {
395 liveIn.remove( writeTemps[i] );
397 // if we are analyzing code declared directly in a task,
398 FlatSESEEnterNode fsen = rblockRel.getLocalInnerRBlock( fn );
400 // check to see if we are writing to variables that will
401 // be live-out at the task's exit (and therefore should
402 // go in the task's out-var set)
403 FlatSESEExitNode fsexn = fsen.getFlatExit();
404 //note: liveness analysis can have corresponding decisions
405 Set<TempDescriptor> livetemps= liveness.getLiveInTemps(fsen.getfmEnclosing(), fsexn);
406 // Set<TempDescriptor> livetemps = livenessGlobalView.get( fsexn );
407 if( livetemps != null && livetemps.contains( writeTemps[i] ) ) {
408 fsen.addOutVar( writeTemps[i] );
413 TempDescriptor[] readTemps = fn.readsTemps();
414 for( int i = 0; i < readTemps.length; ++i ) {
415 liveIn.add( readTemps[i] );
418 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
419 if( virtualReadTemps != null ) {
420 liveIn.addAll( virtualReadTemps );
430 private void variableAnalysisForward(FlatMethod fm) {
432 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
433 flatNodesToVisit.add(fm);
435 while (!flatNodesToVisit.isEmpty()) {
436 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
437 flatNodesToVisit.remove(fn);
439 VarSrcTokTable prev = variableResults.get(fn);
441 // merge sets from control flow joins
442 VarSrcTokTable curr = new VarSrcTokTable();
443 for (int i = 0; i < fn.numPrev(); i++) {
444 FlatNode nn = fn.getPrev(i);
445 VarSrcTokTable incoming = variableResults.get(nn);
446 curr.merge(incoming);
449 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
450 if( currentSESE == null ) {
451 currentSESE = rblockRel.getCallerProxySESE();
454 variable_nodeActions(fn, curr, currentSESE);
456 // if a new result, schedule forward nodes for analysis
457 if (!curr.equals(prev)) {
458 variableResults.put(fn, curr);
460 for (int i = 0; i < fn.numNext(); i++) {
461 FlatNode nn = fn.getNext(i);
462 flatNodesToVisit.add(nn);
468 private void variable_nodeActions(FlatNode fn,
469 VarSrcTokTable vstTable,
470 FlatSESEEnterNode currentSESE) {
474 case FKind.FlatSESEEnterNode: {
475 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
476 // ignore currently executing SESE, at this point
477 // the analysis considers a new instance is becoming
480 vstTable.assertConsistency();
484 case FKind.FlatSESEExitNode: {
485 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
487 // fsen is the child of currently executing tasks
488 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
490 // remap all of this child's children tokens to be
491 // from this child as the child exits
492 vstTable.remapChildTokens(fsen);
494 // liveness virtual reads are things that might be
495 // written by an SESE and should be added to the in-set
496 // anything virtually read by this SESE should be pruned
497 // of parent or sibling sources
498 Set<TempDescriptor> liveVars = livenessGlobalView.get(fn);
499 Set<TempDescriptor> fsenVirtReads =
500 vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen,
503 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
504 if (fsenVirtReadsOld != null) {
505 fsenVirtReads.addAll(fsenVirtReadsOld);
507 livenessVirtualReads.put(fn, fsenVirtReads);
509 // then all child out-set tokens are guaranteed
510 // to be filled in, so clobber those entries with
511 // the latest, clean sources
512 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
513 while (outVarItr.hasNext()) {
514 TempDescriptor outVar = outVarItr.next();
515 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
517 VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
518 vstTable.remove(outVar);
521 vstTable.assertConsistency();
525 case FKind.FlatOpNode: {
526 FlatOpNode fon = (FlatOpNode) fn;
528 if (fon.getOp().getOp() == Operation.ASSIGN) {
529 TempDescriptor lhs = fon.getDest();
530 TempDescriptor rhs = fon.getLeft();
532 vstTable.remove(lhs);
534 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
536 Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
537 while (itr.hasNext()) {
538 VariableSourceToken vst = itr.next();
540 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
543 // when we do x = y for variables, just copy over from a child,
544 // there are two cases:
545 // 1. if the current task is the caller proxy, any local root is a child
547 currentSESE.getIsCallerProxySESE() &&
548 rblockRel.getLocalRootSESEs().contains( vst.getSESE() );
550 // 2. if the child task is a locally-defined child of the current task
551 boolean case2 = currentSESE.getLocalChildren().contains( vst.getSESE() );
553 if( case1 || case2 ) {
554 // if the source comes from a child, copy it over
555 forAddition.add( new VariableSourceToken( ts,
562 // otherwise, stamp it as us as the source
563 forAddition.add( new VariableSourceToken( ts,
572 vstTable.addAll( forAddition );
574 // only break if this is an ASSIGN op node,
575 // otherwise fall through to default case
576 vstTable.assertConsistency();
581 // note that FlatOpNode's that aren't ASSIGN
582 // fall through to this default case
584 TempDescriptor[] writeTemps = fn.writesTemps();
585 if( writeTemps.length > 0 ) {
587 // for now, when writeTemps > 1, make sure
588 // its a call node, programmer enforce only
589 // doing stuff like calling a print routine
590 if( writeTemps.length > 1 ) {
591 assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
595 vstTable.remove( writeTemps[0] );
597 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
598 ts.add( writeTemps[0] );
600 vstTable.add( new VariableSourceToken( ts,
608 vstTable.assertConsistency();
615 private void notAvailableForward(FlatMethod fm) {
617 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
618 flatNodesToVisit.add(fm);
620 while (!flatNodesToVisit.isEmpty()) {
621 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
622 flatNodesToVisit.remove(fn);
624 Set<TempDescriptor> prev = notAvailableResults.get(fn);
626 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
627 for (int i = 0; i < fn.numPrev(); i++) {
628 FlatNode nn = fn.getPrev(i);
629 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
630 if (notAvailIn != null) {
631 curr.addAll(notAvailIn);
635 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
636 if( currentSESE == null ) {
637 currentSESE = rblockRel.getCallerProxySESE();
640 notAvailable_nodeActions(fn, curr, currentSESE);
642 // if a new result, schedule forward nodes for analysis
643 if (!curr.equals(prev)) {
644 notAvailableResults.put(fn, curr);
646 for (int i = 0; i < fn.numNext(); i++) {
647 FlatNode nn = fn.getNext(i);
648 flatNodesToVisit.add(nn);
654 private void notAvailable_nodeActions(FlatNode fn,
655 Set<TempDescriptor> notAvailSet,
656 FlatSESEEnterNode currentSESE
659 // any temps that are removed from the not available set
660 // at this node should be marked in this node's code plan
661 // as temps to be grabbed at runtime!
665 case FKind.FlatSESEEnterNode: {
666 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
668 // keep a copy of what's not available into the SESE
669 // and restore it at the matching exit node
670 Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
671 Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
672 while (tdItr.hasNext()) {
673 notAvailCopy.add(tdItr.next());
675 notAvailableIntoSESE.put(fsen, notAvailCopy);
680 case FKind.FlatSESEExitNode: {
681 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
682 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
684 notAvailSet.addAll(fsen.getOutVarSet());
686 Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
687 assert notAvailIn != null;
688 notAvailSet.addAll(notAvailIn);
691 case FKind.FlatMethod: {
695 case FKind.FlatOpNode: {
696 FlatOpNode fon = (FlatOpNode) fn;
698 if (fon.getOp().getOp() == Operation.ASSIGN) {
699 TempDescriptor lhs = fon.getDest();
700 TempDescriptor rhs = fon.getLeft();
702 // copy makes lhs same availability as rhs
703 if (notAvailSet.contains(rhs)) {
704 notAvailSet.add(lhs);
706 notAvailSet.remove(lhs);
709 // only break if this is an ASSIGN op node,
710 // otherwise fall through to default case
715 // note that FlatOpNode's that aren't ASSIGN
716 // fall through to this default case
718 TempDescriptor[] writeTemps = fn.writesTemps();
719 for (int i = 0; i < writeTemps.length; i++) {
720 TempDescriptor wTemp = writeTemps[i];
721 notAvailSet.remove(wTemp);
723 TempDescriptor[] readTemps = fn.readsTemps();
724 for (int i = 0; i < readTemps.length; i++) {
725 TempDescriptor rTemp = readTemps[i];
726 notAvailSet.remove(rTemp);
728 // if this variable has exactly one source, potentially
729 // get other things from this source as well
730 VarSrcTokTable vstTable = variableResults.get(fn);
732 VSTWrapper vstIfStatic = new VSTWrapper();
733 Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
735 if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
737 VariableSourceToken vst = vstIfStatic.vst;
739 Iterator<VariableSourceToken> availItr =
740 vstTable.get(vst.getSESE(), vst.getAge()).iterator();
742 // look through things that are also available from same source
743 while (availItr.hasNext()) {
744 VariableSourceToken vstAlsoAvail = availItr.next();
746 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
747 while (refVarItr.hasNext()) {
748 TempDescriptor refVarAlso = refVarItr.next();
750 // if a variable is available from the same source, AND it ALSO
751 // only comes from one statically known source, mark it available
752 VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
753 Integer srcTypeAlso =
754 vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed);
755 if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
756 notAvailSet.remove(refVarAlso);
768 private void codePlansForward(FlatMethod fm, Liveness liveness) {
770 // start from flat method top, visit every node in
771 // method exactly once
772 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
773 flatNodesToVisit.add(fm);
775 Set<FlatNode> visited = new HashSet<FlatNode>();
777 while (!flatNodesToVisit.isEmpty()) {
778 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
779 FlatNode fn = fnItr.next();
781 flatNodesToVisit.remove(fn);
784 // use incoming results as "dot statement" or just
785 // before the current statement
786 VarSrcTokTable dotSTtable = new VarSrcTokTable();
787 for (int i = 0; i < fn.numPrev(); i++) {
788 FlatNode nn = fn.getPrev(i);
789 dotSTtable.merge(variableResults.get(nn));
792 // find dt-st notAvailableSet also
793 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
794 for (int i = 0; i < fn.numPrev(); i++) {
795 FlatNode nn = fn.getPrev(i);
796 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
797 if (notAvailIn != null) {
798 dotSTnotAvailSet.addAll(notAvailIn);
802 Set<TempDescriptor> dotSTlive = livenessGlobalView.get(fn);
804 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
805 if( currentSESE == null ) {
806 currentSESE = rblockRel.getCallerProxySESE();
809 codePlans_nodeActions(fm, fn,
810 /*dotSTlive*/liveness, dotSTtable, dotSTnotAvailSet,
813 for (int i = 0; i < fn.numNext(); i++) {
814 FlatNode nn = fn.getNext(i);
816 if (!visited.contains(nn)) {
817 flatNodesToVisit.add(nn);
823 private void codePlans_nodeActions(FlatMethod fm,
825 // Set<TempDescriptor> liveSetIn,
827 VarSrcTokTable vstTableIn,
828 Set<TempDescriptor> notAvailSetIn,
829 FlatSESEEnterNode currentSESE) {
831 CodePlan plan = new CodePlan(currentSESE);
835 case FKind.FlatSESEEnterNode: {
836 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
838 // track the source types of the in-var set so generated
839 // code at this SESE issue can compute the number of
840 // dependencies properly
841 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
842 while (inVarItr.hasNext()) {
843 TempDescriptor inVar = inVarItr.next();
845 // when we get to an SESE enter node we change the
846 // currentSESE variable of this analysis to the
847 // child that is declared by the enter node, so
848 // in order to classify in-vars correctly, pass
849 // the parent SESE in--at other FlatNode types just
850 // use the currentSESE
851 FlatSESEEnterNode parent = rblockRel.getLocalInnerRBlock( fn );
852 if( parent == null ) {
853 parent = rblockRel.getCallerProxySESE();
856 VSTWrapper vstIfStatic = new VSTWrapper();
857 Integer srcType = vstTableIn.getRefVarSrcType(inVar, parent, vstIfStatic);
859 // the current SESE needs a local space to track the dynamic
860 // variable and the child needs space in its SESE record
861 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
862 fsen.addDynamicInVar(inVar);
863 addDynamicVar( fsen, fm, inVar );
865 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
866 fsen.addStaticInVar(inVar);
867 VariableSourceToken vst = vstIfStatic.vst;
868 fsen.putStaticInVar2src(inVar, vst);
869 fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
871 assert srcType.equals(VarSrcTokTable.SrcType_READY);
872 fsen.addReadyInVar(inVar);
877 case FKind.FlatSESEExitNode: {
878 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
879 //TODO! Shouldn't there be a code plan for task exit
880 // where the exiting task calculates whether its own
881 // siblings need variables from its children, so the
882 // exiter should copy those variables into its own out-set
883 // and make the available?
886 case FKind.FlatOpNode: {
887 FlatOpNode fon = (FlatOpNode) fn;
889 if (fon.getOp().getOp() == Operation.ASSIGN) {
890 TempDescriptor lhs = fon.getDest();
891 TempDescriptor rhs = fon.getLeft();
893 // if this is an op node, don't stall, copy
894 // source and delay until we need to use value
896 // ask whether lhs and rhs sources are dynamic, static, etc.
897 VSTWrapper vstIfStatic = new VSTWrapper();
898 Integer lhsSrcType = vstTableIn.getRefVarSrcType(lhs, currentSESE, vstIfStatic);
899 Integer rhsSrcType = vstTableIn.getRefVarSrcType(rhs, currentSESE, vstIfStatic);
901 if (rhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
902 // if rhs is dynamic going in, lhs will definitely be dynamic
903 // going out of this node, so track that here
904 plan.addDynAssign( lhs, rhs );
905 addDynamicVar( currentSESE, fm, lhs );
906 addDynamicVar( currentSESE, fm, rhs );
908 } else if (lhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
909 // otherwise, if the lhs is dynamic, but the rhs is not, we
910 // need to update the variable's dynamic source as "current SESE"
911 plan.addDynAssign(lhs);
914 // only break if this is an ASSIGN op node,
915 // otherwise fall through to default case
920 // note that FlatOpNode's that aren't ASSIGN
921 // fall through to this default case
924 // a node with no live set has nothing to stall for
925 // note: no reason to check here, remove this....
926 // if (liveSetIn == null) {
930 TempDescriptor[] readarray = fn.readsTemps();
931 for (int i = 0; i < readarray.length; i++) {
932 TempDescriptor readtmp = readarray[i];
934 // ignore temps that are definitely available
935 // when considering to stall on it
936 if (!notAvailSetIn.contains(readtmp)) {
940 // check the source type of this variable
941 VSTWrapper vstIfStatic = new VSTWrapper();
942 Integer srcType = vstTableIn.getRefVarSrcType(readtmp, currentSESE, vstIfStatic);
944 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
945 // 1) It is not clear statically where this variable will
946 // come from, so dynamically we must keep track
947 // along various control paths, and therefore when we stall,
948 // just stall for the exact thing we need and move on
949 plan.addDynamicStall( readtmp );
950 addDynamicVar( currentSESE, fm, readtmp );
952 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
953 // 2) Single token/age pair: Stall for token/age pair, and copy
954 // all live variables with same token/age pair at the same
955 // time. This is the same stuff that the notavaialable analysis
956 // marks as now available.
957 VariableSourceToken vst = vstIfStatic.vst;
959 Iterator<VariableSourceToken> availItr =
960 vstTableIn.get(vst.getSESE(), vst.getAge()).iterator();
962 while (availItr.hasNext()) {
963 VariableSourceToken vstAlsoAvail = availItr.next();
965 // only grab additional stuff that is live
966 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
968 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
970 while (refVarItr.hasNext()) {
971 TempDescriptor refVar = refVarItr.next();
972 //note: this should just use normal liveness in...only want to copy live variables...
973 // if (liveSetIn.contains(refVar)) {
974 // copySet.add(refVar);
976 if(liveness.getLiveInTemps(fm, fn).contains(refVar)){
981 if (!copySet.isEmpty()) {
982 plan.addStall2CopySet(vstAlsoAvail, copySet);
987 // the other case for srcs is READY, so do nothing
990 // assert that everything being stalled for is in the
991 // "not available" set coming into this flat node and
992 // that every VST identified is in the possible "stall set"
993 // that represents VST's from children SESE's
1001 // identify sese-age pairs that are statically useful
1002 // and should have an associated SESE variable in code
1003 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
1004 // AND ALWAYS GIVE NAMES TO LOCAL PARENTS
1005 Set<VariableSourceToken> staticSet = vstTableIn.get();
1006 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
1007 while (vstItr.hasNext()) {
1008 VariableSourceToken vst = vstItr.next();
1010 // the caller proxy generates useful analysis facts, but we
1011 // never need to generate another name for it in code (it is
1012 // ALWAYS the task executing the local method context)
1013 if( vst.getSESE().getIsCallerProxySESE() ) {
1017 SESEandAgePair sap = new SESEandAgePair( vst.getSESE(), vst.getAge() );
1018 sap.getSESE().mustTrackAtLeastAge( sap.getAge() );
1020 FlatSESEEnterNode sese = currentSESE;
1021 while( sese != null ) {
1022 addNeededStaticName( sese, fm, sap );
1023 sese = sese.getLocalParent();
1027 codePlans.put(fn, plan);
1029 // if any variables at this-node-*dot* have a static source (exactly one
1031 // but go to a dynamic source at next-node-*dot*, create a new IR graph
1032 // node on that edge to track the sources dynamically
1033 VarSrcTokTable thisVstTable = variableResults.get(fn);
1034 for (int i = 0; i < fn.numNext(); i++) {
1035 FlatNode nn = fn.getNext(i);
1036 VarSrcTokTable nextVstTable = variableResults.get(nn);
1037 // note: using the result of liveness analysis regardless of task structures
1038 // Set<TempDescriptor> nextLiveIn = livenessGlobalView.get(nn);
1039 Set<TempDescriptor> nextLiveIn=liveness.getLiveInTemps(fm, nn);
1041 // the table can be null if it is one of the few IR nodes
1042 // completely outside of the root SESE scope
1043 if (nextVstTable != null && nextLiveIn != null) {
1045 Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
1046 thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, currentSESE);
1048 if (!readyOrStatic2dynamicSet.isEmpty()) {
1050 // either add these results to partial fixed-point result
1051 // or make a new one if we haven't made any here yet
1052 FlatEdge fe = new FlatEdge(fn, nn);
1053 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe);
1055 if (fwdvn == null) {
1056 fwdvn = new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, currentSESE);
1057 wdvNodesToSpliceIn.put(fe, fwdvn);
1059 fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet);
1066 private void addDynamicVar( FlatSESEEnterNode fsen,
1068 TempDescriptor var ) {
1071 // note: dynamic variable declarations are always located in the flat method that encloses task block
1072 // there is no need to set fnContext to fsen
1073 // if( fsen.getIsCallerProxySESE() ) {
1074 // // attach the dynamic variable to track to
1075 // // the flat method, so it can be declared at entry
1078 // // otherwise the code context is a task body
1079 // fnContext = fsen;
1083 ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1085 ctn = new ContextTaskNames();
1088 ctn.addDynamicVar( var );
1089 fn2contextTaskNames.put( fnContext, ctn );
1093 private void addNeededStaticName( FlatSESEEnterNode fsen,
1095 SESEandAgePair sap ) {
1098 if( fsen.getIsCallerProxySESE() ) {
1099 // attach the dynamic variable to track to
1100 // the flat method, so it can be declared at entry
1103 // otherwise the code context is a task body
1107 ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1109 ctn = new ContextTaskNames();
1112 ctn.addNeededStaticName( sap );
1114 fn2contextTaskNames.put( fnContext, ctn );
1118 private void startConflictGraphs() {
1120 // first, for each task, consider whether it has any children, and if
1121 // effects analysis says they should be a conflict node in the that
1122 // parent's conflict graph
1123 Set<FlatSESEEnterNode> allSESEs = rblockRel.getAllSESEs();
1124 for( Iterator iterator = allSESEs.iterator(); iterator.hasNext(); ) {
1126 FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
1127 if( parent.getIsLeafSESE() ) {
1131 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1132 ConflictGraph conflictGraph = sese2conflictGraph.get( parent );
1133 assert conflictGraph == null;
1134 conflictGraph = new ConflictGraph( state );
1136 Set<FlatSESEEnterNode> children = parent.getChildren();
1137 for( Iterator iterator2 = children.iterator(); iterator2.hasNext(); ) {
1138 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
1139 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get( child );
1140 conflictGraph.addLiveIn( taint2Effects );
1143 sese2conflictGraph.put( parent, conflictGraph );
1146 // then traverse all methods looking for potential stall sites, and
1147 // add those stall sites as nodes in any task's conflict graph that
1148 // might be executing at the point of the stall site
1149 Iterator<MethodDescriptor> descItr = descriptorsToAnalyze.iterator();
1150 while( descItr.hasNext() ) {
1151 MethodDescriptor md = descItr.next();
1152 FlatMethod fm = state.getMethodFlat( md );
1154 addStallSitesToConflictGraphs( fm );
1159 private void addStallSitesToConflictGraphs( FlatMethod fm ) {
1161 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1162 flatNodesToVisit.add( fm );
1164 Set<FlatNode> visited = new HashSet<FlatNode>();
1166 while( !flatNodesToVisit.isEmpty() ) {
1167 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1168 flatNodesToVisit.remove( fn );
1171 Set<FlatSESEEnterNode> currentSESEs =
1172 rblockRel.getPossibleExecutingRBlocks( fn );
1174 conflictGraph_nodeAction( fn, currentSESEs );
1176 // schedule forward nodes for analysis
1177 for( int i = 0; i < fn.numNext(); i++ ) {
1178 FlatNode nn = fn.getNext( i );
1179 if( !visited.contains( nn ) ) {
1180 flatNodesToVisit.add( nn );
1186 private void conflictGraph_nodeAction( FlatNode fn,
1187 Set<FlatSESEEnterNode> currentSESEs
1190 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1192 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get( fn );
1195 // repeat the process of adding a stall site to a conflict graph
1196 // for each task that might be executing at a possible stall site
1197 Iterator<FlatSESEEnterNode> seseItr = currentSESEs.iterator();
1198 while( seseItr.hasNext() ) {
1199 FlatSESEEnterNode currentSESE = seseItr.next();
1201 ConflictGraph conflictGraph = sese2conflictGraph.get( currentSESE );
1202 if( conflictGraph == null ) {
1203 assert currentSESE.getIsLeafSESE();
1210 switch( fn.kind() ) {
1213 case FKind.FlatFieldNode:
1214 case FKind.FlatElementNode: {
1216 if( fn instanceof FlatFieldNode ) {
1217 FlatFieldNode ffn = (FlatFieldNode) fn;
1220 FlatElementNode fen = (FlatElementNode) fn;
1224 conflictGraph.addStallSite( taint2Effects, rhs );
1228 case FKind.FlatSetFieldNode:
1229 case FKind.FlatSetElementNode: {
1231 if( fn instanceof FlatSetFieldNode ) {
1232 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1233 lhs = fsfn.getDst();
1234 rhs = fsfn.getSrc();
1236 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1237 lhs = fsen.getDst();
1238 rhs = fsen.getSrc();
1241 conflictGraph.addStallSite( taint2Effects, rhs );
1242 conflictGraph.addStallSite( taint2Effects, lhs );
1246 case FKind.FlatCall: {
1247 FlatCall fc = (FlatCall) fn;
1250 conflictGraph.addStallSite( taint2Effects, lhs );
1255 if( conflictGraph.id2cn.size() > 0 ) {
1256 sese2conflictGraph.put( currentSESE, conflictGraph );
1262 private void calculateConflicts( Set<FlatNew> sitesToFlag,
1263 boolean useReachInfo ) {
1265 // decide fine-grain edge or coarse-grain edge among all vertexes by
1266 // pair-wise comparison
1267 Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
1268 while (seseIter.hasNext()) {
1269 FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next();
1270 ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
1273 // clear current conflict before recalculating with reachability info
1274 conflictGraph.clearAllConflictEdge();
1275 conflictGraph.setDisJointAnalysis(disjointAnalysisReach);
1276 conflictGraph.setFMEnclosing(sese.getfmEnclosing());
1278 conflictGraph.analyzeConflicts(sitesToFlag, useReachInfo);
1279 sese2conflictGraph.put(sese, conflictGraph);
1284 private void writeConflictGraph() {
1285 Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
1286 while (keyEnum.hasMoreElements()) {
1287 FlatNode key = (FlatNode) keyEnum.nextElement();
1288 ConflictGraph cg = sese2conflictGraph.get(key);
1290 if (cg.hasConflictEdge()) {
1291 cg.writeGraph("ConflictGraphFor" + key, false);
1293 } catch (IOException e) {
1294 System.out.println("Error writing");
1301 // the traversal for pruning state machines and finding
1302 // machines that are weakly connected BOTH consider conflicting
1303 // effects between heap roots, so it is smart to compute all of
1305 public void pruneMachinesAndFindWeaklyConnectedExaminers() {
1306 ProcessStateMachines psm=new ProcessStateMachines(buildStateMachines, rblockRel);
1308 buildStateMachines.writeStateMachines("pruned");
1313 private void synthesizeLocks() {
1314 // for every conflict graph, generate a set of memory queues
1315 // (called SESELock in this code!) to cover the graph
1316 Set<Map.Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
1317 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
1318 Map.Entry<FlatNode, ConflictGraph> graphEntry = (Map.Entry<FlatNode, ConflictGraph>) iterator.next();
1319 FlatNode sese = graphEntry.getKey();
1320 ConflictGraph conflictGraph = graphEntry.getValue();
1321 calculateCovering(conflictGraph);
1325 private void calculateCovering(ConflictGraph conflictGraph) {
1326 uniqueLockSetId = 0; // reset lock counter for every new conflict graph
1327 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1328 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1329 HashSet<SESELock> lockSet = new HashSet<SESELock>();
1331 Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1332 for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
1333 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1334 if (conflictEdge.isCoarseEdge()) {
1335 coarseToCover.add(conflictEdge);
1337 fineToCover.add(conflictEdge);
1341 HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
1342 toCover.addAll(fineToCover);
1343 toCover.addAll(coarseToCover);
1345 while (!toCover.isEmpty()) {
1347 SESELock seseLock = new SESELock();
1348 seseLock.setID(uniqueLockSetId++);
1352 do { // fine-grained edge
1356 for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) {
1359 ConflictEdge edge = (ConflictEdge) iterator.next();
1360 if (seseLock.getConflictNodeSet().size() == 0) {
1362 if (seseLock.isWriteNode(edge.getVertexU())) {
1363 // mark as fine_write
1364 if (edge.getVertexU().isStallSiteNode()) {
1365 type = ConflictNode.PARENT_WRITE;
1367 type = ConflictNode.FINE_WRITE;
1369 seseLock.addConflictNode(edge.getVertexU(), type);
1371 // mark as fine_read
1372 if (edge.getVertexU().isStallSiteNode()) {
1373 type = ConflictNode.PARENT_READ;
1375 type = ConflictNode.FINE_READ;
1377 seseLock.addConflictNode(edge.getVertexU(), type);
1379 if (edge.getVertexV() != edge.getVertexU()) {
1380 if (seseLock.isWriteNode(edge.getVertexV())) {
1381 // mark as fine_write
1382 if (edge.getVertexV().isStallSiteNode()) {
1383 type = ConflictNode.PARENT_WRITE;
1385 type = ConflictNode.FINE_WRITE;
1387 seseLock.addConflictNode(edge.getVertexV(), type);
1389 // mark as fine_read
1390 if (edge.getVertexV().isStallSiteNode()) {
1391 type = ConflictNode.PARENT_READ;
1393 type = ConflictNode.FINE_READ;
1395 seseLock.addConflictNode(edge.getVertexV(), type);
1399 seseLock.addConflictEdge(edge);
1400 fineToCover.remove(edge);
1401 break;// exit iterator loop
1402 }// end of initial setup
1404 ConflictNode newNode;
1405 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1406 // new node has a fine-grained edge to all current node
1407 // If there is a coarse grained edge where need a fine edge, it's
1408 // okay to add the node
1409 // but the edge must remain uncovered.
1413 if (seseLock.containsConflictNode(newNode)) {
1414 seseLock.addEdge(edge);
1415 fineToCover.remove(edge);
1419 if (seseLock.isWriteNode(newNode)) {
1420 if (newNode.isStallSiteNode()) {
1421 type = ConflictNode.PARENT_WRITE;
1423 type = ConflictNode.FINE_WRITE;
1425 seseLock.setNodeType(newNode, type);
1427 if (newNode.isStallSiteNode()) {
1428 type = ConflictNode.PARENT_READ;
1430 type = ConflictNode.FINE_READ;
1432 seseLock.setNodeType(newNode, type);
1435 seseLock.addEdge(edge);
1436 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1437 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1438 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1440 // mark all fine edges between new node and nodes in the group as
1442 if (!conflictEdge.getVertexU().equals(newNode)) {
1443 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1445 seseLock.addConflictEdge(conflictEdge);
1446 fineToCover.remove(conflictEdge);
1448 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1449 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1451 seseLock.addConflictEdge(conflictEdge);
1452 fineToCover.remove(conflictEdge);
1458 break;// exit iterator loop
1463 HashSet<ConflictEdge> notCovered=new HashSet<ConflictEdge>();
1467 for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) {
1469 ConflictEdge edge = (ConflictEdge) iterator.next();
1470 if (seseLock.getConflictNodeSet().size() == 0) {
1472 if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
1473 // node has a coarse-grained edge with itself
1474 if (!(edge.getVertexU().isStallSiteNode())) {
1475 // and it is not parent
1476 type = ConflictNode.SCC;
1479 type = ConflictNode.PARENT_COARSE;
1481 type = ConflictNode.PARENT_WRITE;
1484 seseLock.addConflictNode(edge.getVertexU(), type);
1486 if (edge.getVertexU().isStallSiteNode()) {
1488 type = ConflictNode.PARENT_COARSE;
1490 if (edge.getVertexU().getWriteEffectSet().isEmpty()) {
1491 type = ConflictNode.PARENT_READ;
1493 type = ConflictNode.PARENT_WRITE;
1497 type = ConflictNode.COARSE;
1499 seseLock.addConflictNode(edge.getVertexU(), type);
1501 if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
1502 // node has a coarse-grained edge with itself
1503 if (!(edge.getVertexV().isStallSiteNode())) {
1504 // and it is not parent
1505 type = ConflictNode.SCC;
1508 type = ConflictNode.PARENT_COARSE;
1510 type = ConflictNode.PARENT_WRITE;
1513 seseLock.addConflictNode(edge.getVertexV(), type);
1515 if (edge.getVertexV().isStallSiteNode()) {
1517 type = ConflictNode.PARENT_COARSE;
1519 if (edge.getVertexV().getWriteEffectSet().isEmpty()) {
1520 type = ConflictNode.PARENT_READ;
1522 type = ConflictNode.PARENT_WRITE;
1526 type = ConflictNode.COARSE;
1528 seseLock.addConflictNode(edge.getVertexV(), type);
1531 coarseToCover.remove(edge);
1532 seseLock.addConflictEdge(edge);
1533 break;// exit iterator loop
1534 }// end of initial setup
1536 ConflictNode newNode;
1537 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1538 // new node has a coarse-grained edge to all fine-read, fine-write,
1542 if (newNode.isInVarNode() && (!seseLock.hasSelfCoarseEdge(newNode))
1543 && seseLock.hasCoarseEdgeWithParentCoarse(newNode)) {
1544 // this case can't be covered by this queue
1545 coarseToCover.remove(edge);
1546 notCovered.add(edge);
1550 if (seseLock.containsConflictNode(newNode)) {
1551 seseLock.addEdge(edge);
1552 coarseToCover.remove(edge);
1556 if (seseLock.hasSelfCoarseEdge(newNode)) {
1558 if (newNode.isStallSiteNode()) {
1559 type = ConflictNode.PARENT_COARSE;
1561 type = ConflictNode.SCC;
1563 seseLock.setNodeType(newNode, type);
1565 if (newNode.isStallSiteNode()) {
1566 type = ConflictNode.PARENT_COARSE;
1568 type = ConflictNode.COARSE;
1570 seseLock.setNodeType(newNode, type);
1573 seseLock.addEdge(edge);
1574 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1575 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1576 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1577 // mark all coarse edges between new node and nodes in the group
1579 if (!conflictEdge.getVertexU().equals(newNode)) {
1580 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1582 seseLock.addConflictEdge(conflictEdge);
1583 coarseToCover.remove(conflictEdge);
1585 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1586 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1588 seseLock.addConflictEdge(conflictEdge);
1589 coarseToCover.remove(conflictEdge);
1594 break;// exit iterator loop
1600 lockSet.add(seseLock);
1603 coarseToCover.addAll(notCovered);
1604 toCover.addAll(fineToCover);
1605 toCover.addAll(coarseToCover);
1609 conflictGraph2SESELock.put(conflictGraph, lockSet);
1612 public ConflictGraph getConflictGraph(FlatNode sese) {
1613 return sese2conflictGraph.get(sese);
1616 public Set<SESELock> getLockMappings(ConflictGraph graph) {
1617 return conflictGraph2SESELock.get(graph);
1620 public Set<FlatSESEEnterNode> getAllSESEs() {
1621 return rblockRel.getAllSESEs();
1624 public FlatSESEEnterNode getMainSESE() {
1625 return rblockRel.getMainSESE();
1628 public FlatSESEEnterNode getCallerProxySESE() {
1629 return rblockRel.getCallerProxySESE();
1632 public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks( FlatNode fn ) {
1633 return rblockRel.getPossibleExecutingRBlocks( fn );
1637 public void writeReports(String timeReport) throws java.io.IOException {
1639 BufferedWriter bw = new BufferedWriter(new FileWriter("ooojReport_summary.txt"));
1640 bw.write("OoOJava Analysis Results\n\n");
1641 bw.write(timeReport + "\n\n");
1642 printSESEHierarchy(bw);
1647 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
1648 while (methItr.hasNext()) {
1649 MethodDescriptor md = methItr.next();
1650 FlatMethod fm = state.getMethodFlat(md);
1652 bw = new BufferedWriter(new FileWriter("ooojReport_" +
1653 md.getClassMethodName() +
1654 md.getSafeMethodDescriptor() +
1656 bw.write("OoOJava Results for " + md + "\n-------------------\n");
1658 bw.write("Dynamic vars to manage:\n " + getContextTaskNames( fm ).getDynamicVarSet() );
1660 bw.write("\n\nLive-In, Root View\n------------------\n" + fm.printMethod(livenessGlobalView));
1661 bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults));
1662 bw.write("\n\nNot Available Results-Out\n---------------------\n" + fm.printMethod(notAvailableResults));
1663 bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans));
1669 private void printSESEHierarchy(BufferedWriter bw) throws java.io.IOException {
1670 bw.write("SESE Local Hierarchy\n--------------\n");
1671 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getLocalRootSESEs().iterator();
1672 while (rootItr.hasNext()) {
1673 FlatSESEEnterNode root = rootItr.next();
1674 printSESEHierarchyTree(bw, root, 0);
1678 private void printSESEHierarchyTree(BufferedWriter bw,
1679 FlatSESEEnterNode fsen,
1681 ) throws java.io.IOException {
1682 for (int i = 0; i < depth; ++i) {
1685 bw.write("- " + fsen.getPrettyIdentifier() + "\n");
1687 Iterator<FlatSESEEnterNode> childItr = fsen.getLocalChildren().iterator();
1688 while (childItr.hasNext()) {
1689 FlatSESEEnterNode fsenChild = childItr.next();
1690 printSESEHierarchyTree(bw, fsenChild, depth + 1);
1694 private void printSESEInfo(BufferedWriter bw) throws java.io.IOException {
1695 bw.write("\nSESE info\n-------------\n");
1696 Iterator<FlatSESEEnterNode> fsenItr = rblockRel.getAllSESEs().iterator();
1697 while( fsenItr.hasNext() ) {
1698 FlatSESEEnterNode fsen = fsenItr.next();
1700 bw.write("SESE " + fsen.getPrettyIdentifier());
1701 if( fsen.getIsLeafSESE() ) {
1702 bw.write(" (leaf)");
1706 bw.write(" in-set: " + fsen.getInVarSet() + "\n");
1707 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1708 while (tItr.hasNext()) {
1709 TempDescriptor inVar = tItr.next();
1710 if (fsen.getReadyInVarSet().contains(inVar)) {
1711 bw.write(" (ready) " + inVar + "\n");
1713 if (fsen.getStaticInVarSet().contains(inVar)) {
1714 bw.write(" (static) " + inVar + " from " + fsen.getStaticInVarSrc(inVar) + "\n");
1716 if (fsen.getDynamicInVarSet().contains(inVar)) {
1717 bw.write(" (dynamic)" + inVar + "\n");
1721 bw.write(" Dynamic vars to manage: " + getContextTaskNames( fsen ).getDynamicVarSet() + "\n");
1723 bw.write(" out-set: " + fsen.getOutVarSet() + "\n");
1725 bw.write(" local parent: " + fsen.getLocalParent() + "\n");
1726 bw.write(" local children: " + fsen.getLocalChildren() + "\n");
1728 bw.write(" possible parents: " + fsen.getParents() + "\n");
1729 bw.write(" possible children: " + fsen.getChildren() + "\n");