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 Liveness liveness;
20 private RBlockRelationAnalysis rblockRel;
21 private HeapAnalysis disjointAnalysisTaints;
22 private DisjointAnalysis disjointAnalysisReach;
23 private BuildStateMachines buildStateMachines;
25 private Set<MethodDescriptor> descriptorsToAnalyze;
27 private Hashtable<FlatNode, Set<TempDescriptor>> livenessGlobalView;
28 private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
29 private Hashtable<FlatNode, VarSrcTokTable> variableResults;
30 private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
31 private Hashtable<FlatNode, CodePlan> codePlans;
33 private Hashtable<FlatSESEEnterNode, Set<TempDescriptor>> notAvailableIntoSESE;
35 private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
37 private Hashtable<FlatNode, ContextTaskNames> fn2contextTaskNames;
39 // get the flat method that contains any given flat node
40 private Hashtable<FlatNode, FlatMethod> fn2fm;
42 // temporal data structures to track analysis progress.
43 static private int uniqueLockSetId = 0;
44 // mapping of a conflict graph to its compiled lock
45 private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraph2SESELock;
46 // mapping of a sese block to its conflict graph
47 private Hashtable<FlatNode, ConflictGraph> sese2conflictGraph;
49 public static int maxSESEage = -1;
51 public int getMaxSESEage() {
56 public CodePlan getCodePlan(FlatNode fn) {
57 CodePlan cp = codePlans.get(fn);
61 public Set<FlatNode> getNodesWithPlans() {
62 return codePlans.keySet();
65 public ContextTaskNames getContextTaskNames( FlatMethod fm ) {
66 ContextTaskNames out = fn2contextTaskNames.get( fm );
68 out = new ContextTaskNames();
73 public ContextTaskNames getContextTaskNames( FlatSESEEnterNode fsen ) {
74 ContextTaskNames out = fn2contextTaskNames.get( fsen );
76 out = new ContextTaskNames();
81 public FlatMethod getContainingFlatMethod( FlatNode fn ) {
82 FlatMethod fm = fn2fm.get( fn );
87 public HeapAnalysis getDisjointAnalysis() {
88 return disjointAnalysisTaints;
91 public BuildStateMachines getBuildStateMachines() {
92 return buildStateMachines;
95 public OoOJavaAnalysis( State state,
99 ArrayReferencees arrayReferencees ) {
101 State.logEvent("Starting OoOJavaAnalysis");
103 this.typeUtil = typeUtil;
104 this.callGraph = callGraph;
105 this.liveness = liveness;
106 this.maxSESEage = state.OOO_MAXSESEAGE;
108 livenessGlobalView = new Hashtable<FlatNode, Set<TempDescriptor>>();
109 livenessVirtualReads = new Hashtable<FlatNode, Set<TempDescriptor>>();
110 variableResults = new Hashtable<FlatNode, VarSrcTokTable>();
111 notAvailableResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
112 codePlans = new Hashtable<FlatNode, CodePlan>();
113 wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
114 notAvailableIntoSESE = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
115 sese2conflictGraph = new Hashtable<FlatNode, ConflictGraph>();
116 conflictGraph2SESELock = new Hashtable<ConflictGraph, HashSet<SESELock>>();
117 fn2contextTaskNames = new Hashtable<FlatNode, ContextTaskNames>();
118 fn2fm = new Hashtable<FlatNode, FlatMethod>();
120 // state machines support heap examiners with
121 // state transitions to improve precision
123 buildStateMachines = new BuildStateMachines();
126 // add all methods transitively reachable from the
127 // source's main to set for analysis
128 MethodDescriptor mdSourceEntry = typeUtil.getMain();
129 FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
131 descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
133 descriptorsToAnalyze.add(mdSourceEntry);
136 // 0th pass, setup a useful mapping of any flat node to the
137 // flat method it is a part of
138 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
139 while (methItr.hasNext()) {
140 Descriptor d = methItr.next();
141 FlatMethod fm = state.getMethodFlat( d );
142 buildFlatNodeToFlatMethod( fm );
144 State.logEvent("OoOJavaAnalysis Oth pass completed");
146 // 1st pass, find basic rblock relations & potential stall sites
147 rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
148 VarSrcTokTable.rblockRel = rblockRel;
150 State.logEvent("OoOJavaAnalysis 1st pass completed");
153 // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
154 Iterator<FlatSESEEnterNode> seseItr = rblockRel.getLocalRootSESEs().iterator();
155 while (seseItr.hasNext()) {
156 FlatSESEEnterNode sese = seseItr.next();
157 livenessAnalysisBackward(sese);
161 State.logEvent("OoOJavaAnalysis 2nd pass completed");
163 // 3rd pass, variable analysis
164 methItr = rblockRel.getMethodsWithSESEs().iterator();
165 while (methItr.hasNext()) {
166 Descriptor d = methItr.next();
167 FlatMethod fm = state.getMethodFlat(d);
168 // starting from roots do a forward, fixed-point
169 // variable analysis for refinement and stalls
170 variableAnalysisForward(fm);
173 State.logEvent("OoOJavaAnalysis 3rd pass completed");
175 // 4th pass, compute liveness contribution from
176 // virtual reads discovered in variable pass
177 seseItr = rblockRel.getLocalRootSESEs().iterator();
178 while (seseItr.hasNext()) {
179 FlatSESEEnterNode sese = seseItr.next();
180 livenessAnalysisBackward(sese);
183 State.logEvent("OoOJavaAnalysis 4th pass completed");
185 // 5th pass, use disjointness with NO FLAGGED REGIONS
186 // to compute taints and effects
188 disjointAnalysisTaints = new Pointer(state, typeUtil, callGraph, rblockRel, liveness, buildStateMachines);
189 ((Pointer)disjointAnalysisTaints).doAnalysis();
191 disjointAnalysisTaints =
192 new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null,
193 rblockRel, buildStateMachines,
194 true ); // suppress output--this is an intermediate pass
196 State.logEvent("OoOJavaAnalysis 5th pass completed");
198 // 6th pass, not available analysis FOR VARIABLES!
199 methItr = rblockRel.getMethodsWithSESEs().iterator();
200 while (methItr.hasNext()) {
201 Descriptor d = methItr.next();
202 FlatMethod fm = state.getMethodFlat(d);
203 // compute what is not available at every program
204 // point, in a forward fixed-point pass
205 notAvailableForward(fm);
207 State.logEvent("OoOJavaAnalysis 6th pass completed");
208 // 7th pass, start conflict graphs where a parent's graph has a
209 // node for possibly conflicting children and its own stall sites
210 startConflictGraphs();
211 State.logEvent("OoOJavaAnalysis 7th pass completed");
212 // 8th pass, calculate all possible conflicts without using
213 // reachability info and identify set of FlatNew that next
214 // disjoint reach. analysis should flag
215 Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
216 calculateConflicts(sitesToFlag, false);
217 State.logEvent("OoOJavaAnalysis 8th pass completed");
219 // 9th pass, ask disjoint analysis to compute reachability
220 // for objects that may cause heap conflicts so the most
221 // efficient method to deal with conflict can be computed
223 disjointAnalysisReach =
224 new DisjointAnalysis(state, typeUtil, callGraph, liveness,
225 arrayReferencees, sitesToFlag,
226 null, // don't do effects analysis again!
227 null, // no BuildStateMachines needed
228 !state.OOODEBUG // only print out in OoOJava debug mode
230 State.logEvent("OoOJavaAnalysis 9th pass completed");
231 // 10th pass, calculate conflicts with reachability info
232 calculateConflicts(null, true);
233 State.logEvent("OoOJavaAnalysis 10th pass completed");
235 // in RCR/DFJ we want to do some extra processing on the
236 // state machines before they get handed off to code gen,
237 // and we're doing the same effect-conflict traversal needed
238 // to identify heap examiners that are weakly connected, so
239 // accomplish both at the same time
240 pruneMachinesAndFindWeaklyConnectedExaminers();
241 State.logEvent("OoOJavaAnalysis RCR pruneMachines pass completed");
244 // 11th pass, compiling memory Qs! The name "lock" is a legacy
245 // term for the heap dependence queue, or memQ as the runtime calls it
247 State.logEvent("OoOJavaAnalysis 11th pass completed");
249 // 12th pass, compute a plan for code injections
250 methItr = descriptorsToAnalyze.iterator();
251 while (methItr.hasNext()) {
252 Descriptor d = methItr.next();
253 FlatMethod fm = state.getMethodFlat(d);
254 codePlansForward(fm);
257 State.logEvent("OoOJavaAnalysis 12th pass completed");
259 // splice new IR nodes into graph after all
260 // analysis passes are complete
261 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
262 while (spliceItr.hasNext()) {
263 Map.Entry me = (Map.Entry) spliceItr.next();
264 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
265 fwdvn.spliceIntoIR();
267 State.logEvent("OoOJavaAnalysis 13th pass completed");
269 if (state.OOODEBUG) {
272 disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt");
273 writeConflictGraph();
274 } catch (IOException e) {}
276 State.logEvent("OoOJavaAnalysis completed");
280 private void buildFlatNodeToFlatMethod( FlatMethod fm ) {
281 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
282 flatNodesToVisit.add( fm );
284 Set<FlatNode> flatNodesVisited = new HashSet<FlatNode>();
286 while( !flatNodesToVisit.isEmpty() ) {
287 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
288 flatNodesToVisit.remove( fn );
289 flatNodesVisited.add( fn );
293 for( int i = 0; i < fn.numNext(); i++ ) {
294 FlatNode nn = fn.getNext( i );
295 if( !flatNodesVisited.contains( nn ) ) {
296 flatNodesToVisit.add( nn );
305 * Iterator iter = sese2conflictGraph.entrySet().iterator(); while
306 * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn =
307 * (FlatNode) e.getKey(); ConflictGraph conflictGraph = (ConflictGraph)
309 * System.out.println("---------------------------------------");
310 * System.out.println("CONFLICT GRAPH for " + fn); Set<String> keySet =
311 * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator();
312 * iterator.hasNext();) { String key = (String) iterator.next();
313 * ConflictNode node = conflictGraph.id2cn.get(key);
314 * System.out.println("key=" + key + " \n" + node.toStringAllEffects()); } }
320 private void writeFile(Set<FlatNew> sitesToFlag) {
323 BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt"));
325 for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext();) {
326 FlatNew fn = (FlatNew) iterator.next();
330 } catch (IOException e) {
337 private void livenessAnalysisBackward(FlatSESEEnterNode fsen) {
339 // flow backward across nodes to compute liveness, and
340 // take special care with sese enter/exit nodes that
341 // alter this from normal liveness analysis
342 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
343 // flatNodesToVisit.add( fm.getFlatExit() );
344 flatNodesToVisit.add(fsen.getFlatExit());
346 while( !flatNodesToVisit.isEmpty() ) {
347 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
348 flatNodesToVisit.remove( fn );
350 Set<TempDescriptor> prev = livenessGlobalView.get( fn );
352 // merge sets from control flow joins
353 Set<TempDescriptor> livein = new HashSet<TempDescriptor>();
354 for (int i = 0; i < fn.numNext(); i++) {
355 FlatNode nn = fn.getNext( i );
356 Set<TempDescriptor> s = livenessGlobalView.get( nn );
362 Set<TempDescriptor> curr = liveness_nodeActions( fn, livein );
364 // if a new result, schedule backward nodes for analysis
365 if( !curr.equals( prev ) ) {
368 livenessGlobalView.put( fn, curr );
369 for( int i = 0; i < fn.numPrev(); i++ ) {
370 FlatNode nn = fn.getPrev( i );
371 flatNodesToVisit.add( nn );
378 private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
379 Set<TempDescriptor> liveIn
381 switch( fn.kind() ) {
383 case FKind.FlatSESEEnterNode: {
384 // add whatever is live-in at a task enter to that
386 FlatSESEEnterNode fsen = (FlatSESEEnterNode)fn;
387 if( liveIn != null ) {
388 fsen.addInVarSet( liveIn );
390 // no break, should also execute default actions
394 // handle effects of statement in reverse, writes then reads
395 TempDescriptor[] writeTemps = fn.writesTemps();
396 for( int i = 0; i < writeTemps.length; ++i ) {
397 liveIn.remove( writeTemps[i] );
399 // if we are analyzing code declared directly in a task,
400 FlatSESEEnterNode fsen = rblockRel.getLocalInnerRBlock( fn );
402 // check to see if we are writing to variables that will
403 // be live-out at the task's exit (and therefore should
404 // go in the task's out-var set)
405 FlatSESEExitNode fsexn = fsen.getFlatExit();
406 //note: liveness analysis can have corresponding decisions
407 Set<TempDescriptor> livetemps= liveness.getLiveInTemps(fsen.getfmEnclosing(), fsexn);
408 if( livetemps != null && livetemps.contains( writeTemps[i] ) ) {
409 fsen.addOutVar( writeTemps[i] );
414 TempDescriptor[] readTemps = fn.readsTemps();
415 for( int i = 0; i < readTemps.length; ++i ) {
416 liveIn.add( readTemps[i] );
419 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
420 if( virtualReadTemps != null ) {
421 liveIn.addAll( virtualReadTemps );
431 private void variableAnalysisForward(FlatMethod fm) {
433 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
434 flatNodesToVisit.add(fm);
436 while (!flatNodesToVisit.isEmpty()) {
437 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
438 flatNodesToVisit.remove(fn);
440 VarSrcTokTable prev = variableResults.get(fn);
442 // merge sets from control flow joins
443 VarSrcTokTable curr = new VarSrcTokTable();
444 for (int i = 0; i < fn.numPrev(); i++) {
445 FlatNode nn = fn.getPrev(i);
446 VarSrcTokTable incoming = variableResults.get(nn);
447 curr.merge(incoming);
450 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
451 if( currentSESE == null ) {
452 currentSESE = rblockRel.getCallerProxySESE();
455 variable_nodeActions(fn, curr, currentSESE);
457 // if a new result, schedule forward nodes for analysis
458 if (!curr.equals(prev)) {
459 variableResults.put(fn, curr);
461 for (int i = 0; i < fn.numNext(); i++) {
462 FlatNode nn = fn.getNext(i);
463 flatNodesToVisit.add(nn);
469 private void variable_nodeActions(FlatNode fn,
470 VarSrcTokTable vstTable,
471 FlatSESEEnterNode currentSESE) {
475 case FKind.FlatSESEEnterNode: {
476 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
477 // ignore currently executing SESE, at this point
478 // the analysis considers a new instance is becoming
481 vstTable.assertConsistency();
485 case FKind.FlatSESEExitNode: {
486 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
488 // fsen is the child of currently executing tasks
489 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
491 // remap all of this child's children tokens to be
492 // from this child as the child exits
493 vstTable.remapChildTokens(fsen);
495 // liveness virtual reads are things that might be
496 // written by an SESE and should be added to the in-set
497 // anything virtually read by this SESE should be pruned
498 // of parent or sibling sources
499 Set<TempDescriptor> liveVars = liveness.getLiveInTemps(fsen.getfmEnclosing(),
502 Set<TempDescriptor> fsenVirtReads =
503 vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen,
506 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
507 if (fsenVirtReadsOld != null) {
508 fsenVirtReads.addAll(fsenVirtReadsOld);
510 livenessVirtualReads.put(fn, fsenVirtReads);
512 // virtual reads are forced in-vars!
513 fsen.addInVarSet( fsenVirtReads );
516 // then all child out-set tokens are guaranteed
517 // to be filled in, so clobber those entries with
518 // the latest, clean sources
519 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
520 while (outVarItr.hasNext()) {
521 TempDescriptor outVar = outVarItr.next();
522 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
524 VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
525 vstTable.remove(outVar);
528 vstTable.assertConsistency();
532 case FKind.FlatOpNode: {
533 FlatOpNode fon = (FlatOpNode) fn;
535 if (fon.getOp().getOp() == Operation.ASSIGN) {
536 TempDescriptor lhs = fon.getDest();
537 TempDescriptor rhs = fon.getLeft();
539 vstTable.remove(lhs);
541 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
543 Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
544 while (itr.hasNext()) {
545 VariableSourceToken vst = itr.next();
547 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
550 // when we do x = y for variables, just copy over from a child,
551 // there are two cases:
552 // 1. if the current task is the caller proxy, any local root is a child
554 currentSESE.getIsCallerProxySESE() &&
555 rblockRel.getLocalRootSESEs().contains( vst.getSESE() );
557 // 2. if the child task is a locally-defined child of the current task
558 boolean case2 = currentSESE.getLocalChildren().contains( vst.getSESE() );
560 if( case1 || case2 ) {
561 // if the source comes from a child, copy it over
562 forAddition.add( new VariableSourceToken( ts,
569 // otherwise, stamp it as us as the source
570 forAddition.add( new VariableSourceToken( ts,
579 vstTable.addAll( forAddition );
581 // only break if this is an ASSIGN op node,
582 // otherwise fall through to default case
583 vstTable.assertConsistency();
588 // note that FlatOpNode's that aren't ASSIGN
589 // fall through to this default case
591 TempDescriptor[] writeTemps = fn.writesTemps();
592 if( writeTemps.length > 0 ) {
594 // for now, when writeTemps > 1, make sure
595 // its a call node, programmer enforce only
596 // doing stuff like calling a print routine
597 if( writeTemps.length > 1 ) {
598 assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
602 vstTable.remove( writeTemps[0] );
604 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
605 ts.add( writeTemps[0] );
607 vstTable.add( new VariableSourceToken( ts,
615 vstTable.assertConsistency();
622 private void notAvailableForward(FlatMethod fm) {
624 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
625 flatNodesToVisit.add(fm);
627 while (!flatNodesToVisit.isEmpty()) {
628 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
629 flatNodesToVisit.remove(fn);
631 Set<TempDescriptor> prev = notAvailableResults.get(fn);
633 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
634 for (int i = 0; i < fn.numPrev(); i++) {
635 FlatNode nn = fn.getPrev(i);
636 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
637 if (notAvailIn != null) {
638 curr.addAll(notAvailIn);
642 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
643 if( currentSESE == null ) {
644 currentSESE = rblockRel.getCallerProxySESE();
647 notAvailable_nodeActions(fn, curr, currentSESE);
649 // if a new result, schedule forward nodes for analysis
650 if (!curr.equals(prev)) {
651 notAvailableResults.put(fn, curr);
653 for (int i = 0; i < fn.numNext(); i++) {
654 FlatNode nn = fn.getNext(i);
655 flatNodesToVisit.add(nn);
661 private void notAvailable_nodeActions(FlatNode fn,
662 Set<TempDescriptor> notAvailSet,
663 FlatSESEEnterNode currentSESE
666 // any temps that are removed from the not available set
667 // at this node should be marked in this node's code plan
668 // as temps to be grabbed at runtime!
672 case FKind.FlatSESEEnterNode: {
673 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
675 // keep a copy of what's not available into the SESE
676 // and restore it at the matching exit node
677 Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
678 Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
679 while (tdItr.hasNext()) {
680 notAvailCopy.add(tdItr.next());
682 notAvailableIntoSESE.put(fsen, notAvailCopy);
687 case FKind.FlatSESEExitNode: {
688 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
689 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
691 notAvailSet.addAll(fsen.getOutVarSet());
693 Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
694 assert notAvailIn != null;
695 notAvailSet.addAll(notAvailIn);
698 case FKind.FlatMethod: {
702 case FKind.FlatOpNode: {
703 FlatOpNode fon = (FlatOpNode) fn;
705 if (fon.getOp().getOp() == Operation.ASSIGN) {
706 TempDescriptor lhs = fon.getDest();
707 TempDescriptor rhs = fon.getLeft();
709 // copy makes lhs same availability as rhs
710 if (notAvailSet.contains(rhs)) {
711 notAvailSet.add(lhs);
713 notAvailSet.remove(lhs);
716 // only break if this is an ASSIGN op node,
717 // otherwise fall through to default case
722 // note that FlatOpNode's that aren't ASSIGN
723 // fall through to this default case
725 TempDescriptor[] writeTemps = fn.writesTemps();
726 for (int i = 0; i < writeTemps.length; i++) {
727 TempDescriptor wTemp = writeTemps[i];
728 notAvailSet.remove(wTemp);
730 TempDescriptor[] readTemps = fn.readsTemps();
731 for (int i = 0; i < readTemps.length; i++) {
732 TempDescriptor rTemp = readTemps[i];
733 notAvailSet.remove(rTemp);
735 // if this variable has exactly one source, potentially
736 // get other things from this source as well
737 VarSrcTokTable vstTable = variableResults.get(fn);
739 VSTWrapper vstIfStatic = new VSTWrapper();
740 Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
742 if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
744 VariableSourceToken vst = vstIfStatic.vst;
746 Iterator<VariableSourceToken> availItr =
747 vstTable.get(vst.getSESE(), vst.getAge()).iterator();
749 // look through things that are also available from same source
750 while (availItr.hasNext()) {
751 VariableSourceToken vstAlsoAvail = availItr.next();
753 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
754 while (refVarItr.hasNext()) {
755 TempDescriptor refVarAlso = refVarItr.next();
757 // if a variable is available from the same source, AND it ALSO
758 // only comes from one statically known source, mark it available
759 VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
760 Integer srcTypeAlso =
761 vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed);
762 if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
763 notAvailSet.remove(refVarAlso);
775 private void codePlansForward(FlatMethod fm) {
777 // start from flat method top, visit every node in
778 // method exactly once
779 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
780 flatNodesToVisit.add(fm);
782 Set<FlatNode> visited = new HashSet<FlatNode>();
784 while (!flatNodesToVisit.isEmpty()) {
785 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
786 FlatNode fn = fnItr.next();
788 flatNodesToVisit.remove(fn);
791 // use incoming results as "dot statement" or just
792 // before the current statement
793 VarSrcTokTable dotSTtable = new VarSrcTokTable();
794 for (int i = 0; i < fn.numPrev(); i++) {
795 FlatNode nn = fn.getPrev(i);
796 dotSTtable.merge(variableResults.get(nn));
799 // find dt-st notAvailableSet also
800 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
801 for (int i = 0; i < fn.numPrev(); i++) {
802 FlatNode nn = fn.getPrev(i);
803 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
804 if (notAvailIn != null) {
805 dotSTnotAvailSet.addAll(notAvailIn);
809 Set<TempDescriptor> dotSTlive = livenessGlobalView.get(fn);
811 FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock( fn );
812 if( currentSESE == null ) {
813 currentSESE = rblockRel.getCallerProxySESE();
816 codePlans_nodeActions(fm, fn,
817 dotSTtable, dotSTnotAvailSet,
820 for (int i = 0; i < fn.numNext(); i++) {
821 FlatNode nn = fn.getNext(i);
823 if (!visited.contains(nn)) {
824 flatNodesToVisit.add(nn);
830 private void codePlans_nodeActions(FlatMethod fm,
832 VarSrcTokTable vstTableIn,
833 Set<TempDescriptor> notAvailSetIn,
834 FlatSESEEnterNode currentSESE) {
836 CodePlan plan = new CodePlan(currentSESE);
840 case FKind.FlatSESEEnterNode: {
841 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
843 // track the source types of the in-var set so generated
844 // code at this SESE issue can compute the number of
845 // dependencies properly
846 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
847 while (inVarItr.hasNext()) {
848 TempDescriptor inVar = inVarItr.next();
850 // when we get to an SESE enter node we change the
851 // currentSESE variable of this analysis to the
852 // child that is declared by the enter node, so
853 // in order to classify in-vars correctly, pass
854 // the parent SESE in--at other FlatNode types just
855 // use the currentSESE
856 FlatSESEEnterNode parent = rblockRel.getLocalInnerRBlock( fn );
857 if( parent == null ) {
858 parent = rblockRel.getCallerProxySESE();
861 VSTWrapper vstIfStatic = new VSTWrapper();
862 Integer srcType = vstTableIn.getRefVarSrcType(inVar, parent, vstIfStatic);
864 // the current SESE needs a local space to track the dynamic
865 // variable and the child needs space in its SESE record
866 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
867 fsen.addDynamicInVar(inVar);
868 addDynamicVar( parent, fm, inVar );
870 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
871 fsen.addStaticInVar(inVar);
872 VariableSourceToken vst = vstIfStatic.vst;
873 fsen.putStaticInVar2src(inVar, vst);
874 fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge()));
877 assert srcType.equals(VarSrcTokTable.SrcType_READY);
878 fsen.addReadyInVar(inVar);
883 case FKind.FlatSESEExitNode: {
884 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
886 // Classify the sources of out-set variables so code
887 // gen can acquire them from children if necessary
888 // before this task exits
889 FlatSESEEnterNode exiter = fsexn.getFlatEnter();
891 Iterator<TempDescriptor> outVarItr = exiter.getOutVarSet().iterator();
892 while( outVarItr.hasNext() ) {
893 TempDescriptor outVar = outVarItr.next();
895 VSTWrapper vstIfStatic = new VSTWrapper();
896 Integer srcType = vstTableIn.getRefVarSrcType( outVar,
901 if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
902 // if the out-var is dynamic, put it in the set of dyn out vars
903 // so exiting code gen knows to look for the value, but also put
904 // it in the set of dynamic vars the exiter must track!
905 exiter.addDynamicOutVar( outVar );
906 addDynamicVar( exiter, fm, outVar );
908 } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
909 exiter.addStaticOutVar( outVar );
910 VariableSourceToken vst = vstIfStatic.vst;
911 exiter.putStaticOutVar2src( outVar, vst );
912 exiter.addStaticOutVarSrc( new SESEandAgePair( vst.getSESE(), vst.getAge() ) );
915 assert srcType.equals( VarSrcTokTable.SrcType_READY );
916 exiter.addReadyOutVar( outVar );
921 case FKind.FlatOpNode: {
922 FlatOpNode fon = (FlatOpNode) fn;
924 if (fon.getOp().getOp() == Operation.ASSIGN) {
925 TempDescriptor lhs = fon.getDest();
926 TempDescriptor rhs = fon.getLeft();
928 // if this is an op node, don't stall, copy
929 // source and delay until we need to use value
931 // ask whether lhs and rhs sources are dynamic, static, etc.
932 VSTWrapper vstIfStatic = new VSTWrapper();
933 Integer lhsSrcType = vstTableIn.getRefVarSrcType(lhs, currentSESE, vstIfStatic);
934 Integer rhsSrcType = vstTableIn.getRefVarSrcType(rhs, currentSESE, vstIfStatic);
936 if (rhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
937 // if rhs is dynamic going in, lhs will definitely be dynamic
938 // going out of this node, so track that here
939 plan.addDynAssign( lhs, rhs );
940 addDynamicVar( currentSESE, fm, lhs );
941 addDynamicVar( currentSESE, fm, rhs );
943 } else if (lhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
944 // otherwise, if the lhs is dynamic, but the rhs is not, we
945 // need to update the variable's dynamic source as "current SESE"
946 plan.addDynAssign(lhs);
949 // only break if this is an ASSIGN op node,
950 // otherwise fall through to default case
955 // note that FlatOpNode's that aren't ASSIGN
956 // fall through to this default case
959 // a node with no live set has nothing to stall for
960 // note: no reason to check here, remove this....
961 // if (liveSetIn == null) {
965 TempDescriptor[] readarray = fn.readsTemps();
966 for (int i = 0; i < readarray.length; i++) {
967 TempDescriptor readtmp = readarray[i];
969 // ignore temps that are definitely available
970 // when considering to stall on it
971 if (!notAvailSetIn.contains(readtmp)) {
975 // check the source type of this variable
976 VSTWrapper vstIfStatic = new VSTWrapper();
977 Integer srcType = vstTableIn.getRefVarSrcType(readtmp, currentSESE, vstIfStatic);
979 if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
980 // 1) It is not clear statically where this variable will
981 // come from, so dynamically we must keep track
982 // along various control paths, and therefore when we stall,
983 // just stall for the exact thing we need and move on
984 plan.addDynamicStall( readtmp );
985 addDynamicVar( currentSESE, fm, readtmp );
987 } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
988 // 2) Single token/age pair: Stall for token/age pair, and copy
989 // all live variables with same token/age pair at the same
990 // time. This is the same stuff that the notavaialable analysis
991 // marks as now available.
992 VariableSourceToken vst = vstIfStatic.vst;
994 Iterator<VariableSourceToken> availItr =
995 vstTableIn.get(vst.getSESE(), vst.getAge()).iterator();
997 while (availItr.hasNext()) {
998 VariableSourceToken vstAlsoAvail = availItr.next();
1000 // only grab additional stuff that is live
1001 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
1003 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
1005 while (refVarItr.hasNext()) {
1006 TempDescriptor refVar = refVarItr.next();
1007 //note: this should just use normal liveness in...only want to copy live variables...
1008 if(liveness.getLiveInTemps(fm, fn).contains(refVar)){
1009 copySet.add(refVar);
1013 if (!copySet.isEmpty()) {
1014 plan.addStall2CopySet(vstAlsoAvail, copySet);
1019 // the other case for srcs is READY, so do nothing
1022 // assert that everything being stalled for is in the
1023 // "not available" set coming into this flat node and
1024 // that every VST identified is in the possible "stall set"
1025 // that represents VST's from children SESE's
1033 // identify sese-age pairs that are statically useful
1034 // and should have an associated SESE variable in code
1035 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
1036 // AND ALWAYS GIVE NAMES TO LOCAL PARENTS
1037 Set<VariableSourceToken> staticSet = vstTableIn.get();
1038 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
1039 while (vstItr.hasNext()) {
1040 VariableSourceToken vst = vstItr.next();
1042 // the caller proxy generates useful analysis facts, but we
1043 // never need to generate another name for it in code (it is
1044 // ALWAYS the task executing the local method context)
1045 if( vst.getSESE().getIsCallerProxySESE() ) {
1049 SESEandAgePair sap = new SESEandAgePair( vst.getSESE(), vst.getAge() );
1050 sap.getSESE().mustTrackAtLeastAge( sap.getAge() );
1052 FlatSESEEnterNode sese = currentSESE;
1053 while( sese != null ) {
1054 addNeededStaticName( sese, fm, sap );
1055 sese = sese.getLocalParent();
1059 codePlans.put(fn, plan);
1064 // if any variables at this-node-*dot* have a static source (exactly one vst)
1065 // but go to a dynamic source at next-node-*dot*, create a new IR graph
1066 // node on that edge to track the sources dynamically
1067 // NOTE: for this calculation use the currentSESE variable, except when the
1068 // FlatNode fn is an Exit--in that case currentSESE is for the exiting task,
1069 // be we want to consider that the parent is tracking a variable coming out
1070 // of the exiting task
1071 FlatSESEEnterNode fsenDoingTracking;
1072 if( fn instanceof FlatSESEExitNode ) {
1073 fsenDoingTracking = currentSESE.getLocalParent();
1075 if( fsenDoingTracking == null ) {
1076 // if there is no local parent, there are one of two cases
1077 // 1) the current task is main, in which case this FlatNode
1078 // is the main's exit, and doesn't need to do any of the
1079 // following dynamic tracking
1080 // 2) the current task is defined in a method, so use the
1081 // caller proxy in the variable source calcs below
1082 if( currentSESE.equals( rblockRel.getMainSESE() ) ) {
1085 fsenDoingTracking = rblockRel.getCallerProxySESE();
1089 fsenDoingTracking = currentSESE;
1093 if( fsenDoingTracking.getPrettyIdentifier().equals( "workLoop" ) ) {
1094 System.out.println( "\n\nWriteDyn for "+fsenDoingTracking+" at "+fn );
1098 VarSrcTokTable thisVstTable = variableResults.get(fn);
1099 for (int i = 0; i < fn.numNext(); i++) {
1100 FlatNode nn = fn.getNext(i);
1101 VarSrcTokTable nextVstTable = variableResults.get(nn);
1102 // note: using the result of liveness analysis regardless of task structures
1103 Set<TempDescriptor> nextLiveIn=liveness.getLiveInTemps(fm, nn);
1105 // the table can be null if it is one of the few IR nodes
1106 // completely outside of the root SESE scope
1107 if (nextVstTable != null && nextLiveIn != null) {
1109 Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
1110 thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, fsenDoingTracking);
1112 if (!readyOrStatic2dynamicSet.isEmpty()) {
1116 if( fsenDoingTracking.getPrettyIdentifier().equals( "workLoop" ) ) {
1117 System.out.println( " found newly dyn vars: "+readyOrStatic2dynamicSet );
1121 // either add these results to partial fixed-point result
1122 // or make a new one if we haven't made any here yet
1123 FlatEdge fe = new FlatEdge(fn, nn);
1124 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe);
1126 if (fwdvn == null) {
1127 fwdvn = new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, fsenDoingTracking);
1128 wdvNodesToSpliceIn.put(fe, fwdvn);
1130 fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet);
1136 if( fsenDoingTracking.getPrettyIdentifier().equals( "workLoop" ) ) {
1137 System.out.println( "WriteDyn for "+fsenDoingTracking+" at "+fn+" is done\n\n" );
1141 private void addDynamicVar( FlatSESEEnterNode fsen,
1143 TempDescriptor var ) {
1146 // note: dynamic variable declarations are always located in the flat method that encloses task block
1147 // there is no need to set fnContext to fsen
1148 if( fsen.getIsCallerProxySESE() ) {
1149 // attach the dynamic variable to track to
1150 // the flat method, so it can be declared at entry
1153 // otherwise the code context is a task body
1158 ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1160 ctn = new ContextTaskNames();
1163 ctn.addDynamicVar( var );
1164 fn2contextTaskNames.put( fnContext, ctn );
1168 private void addNeededStaticName( FlatSESEEnterNode fsen,
1170 SESEandAgePair sap ) {
1173 if( fsen.getIsCallerProxySESE() ) {
1174 // attach the dynamic variable to track to
1175 // the flat method, so it can be declared at entry
1178 // otherwise the code context is a task body
1182 ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
1184 ctn = new ContextTaskNames();
1187 ctn.addNeededStaticName( sap );
1189 fn2contextTaskNames.put( fnContext, ctn );
1193 private void startConflictGraphs() {
1195 // first, for each task, consider whether it has any children, and if
1196 // effects analysis says they should be a conflict node in the that
1197 // parent's conflict graph
1198 Set<FlatSESEEnterNode> allSESEs = rblockRel.getAllSESEs();
1199 for( Iterator iterator = allSESEs.iterator(); iterator.hasNext(); ) {
1201 FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
1202 if( parent.getIsLeafSESE() ) {
1206 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1207 ConflictGraph conflictGraph = sese2conflictGraph.get( parent );
1208 assert conflictGraph == null;
1209 conflictGraph = new ConflictGraph( state );
1211 Set<FlatSESEEnterNode> children = parent.getChildren();
1212 for( Iterator iterator2 = children.iterator(); iterator2.hasNext(); ) {
1213 FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
1214 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get( child );
1215 conflictGraph.addLiveIn( taint2Effects );
1218 sese2conflictGraph.put( parent, conflictGraph );
1221 // then traverse all methods looking for potential stall sites, and
1222 // add those stall sites as nodes in any task's conflict graph that
1223 // might be executing at the point of the stall site
1224 Iterator<MethodDescriptor> descItr = descriptorsToAnalyze.iterator();
1225 while( descItr.hasNext() ) {
1226 MethodDescriptor md = descItr.next();
1227 FlatMethod fm = state.getMethodFlat( md );
1229 addStallSitesToConflictGraphs( fm );
1234 private void addStallSitesToConflictGraphs( FlatMethod fm ) {
1236 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1237 flatNodesToVisit.add( fm );
1239 Set<FlatNode> visited = new HashSet<FlatNode>();
1241 while( !flatNodesToVisit.isEmpty() ) {
1242 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1243 flatNodesToVisit.remove( fn );
1246 Set<FlatSESEEnterNode> currentSESEs =
1247 rblockRel.getPossibleExecutingRBlocks( fn );
1249 conflictGraph_nodeAction( fn, currentSESEs );
1251 // schedule forward nodes for analysis
1252 for( int i = 0; i < fn.numNext(); i++ ) {
1253 FlatNode nn = fn.getNext( i );
1254 if( !visited.contains( nn ) ) {
1255 flatNodesToVisit.add( nn );
1261 private void conflictGraph_nodeAction( FlatNode fn,
1262 Set<FlatSESEEnterNode> currentSESEs
1265 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1267 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get( fn );
1270 // repeat the process of adding a stall site to a conflict graph
1271 // for each task that might be executing at a possible stall site
1272 Iterator<FlatSESEEnterNode> seseItr = currentSESEs.iterator();
1273 while( seseItr.hasNext() ) {
1274 FlatSESEEnterNode currentSESE = seseItr.next();
1276 ConflictGraph conflictGraph = sese2conflictGraph.get( currentSESE );
1277 if( conflictGraph == null ) {
1278 assert currentSESE.getIsLeafSESE();
1285 switch( fn.kind() ) {
1288 case FKind.FlatFieldNode:
1289 case FKind.FlatElementNode: {
1291 if( fn instanceof FlatFieldNode ) {
1292 FlatFieldNode ffn = (FlatFieldNode) fn;
1295 FlatElementNode fen = (FlatElementNode) fn;
1299 conflictGraph.addStallSite( taint2Effects, rhs );
1303 case FKind.FlatSetFieldNode:
1304 case FKind.FlatSetElementNode: {
1306 if( fn instanceof FlatSetFieldNode ) {
1307 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1308 lhs = fsfn.getDst();
1309 rhs = fsfn.getSrc();
1311 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1312 lhs = fsen.getDst();
1313 rhs = fsen.getSrc();
1316 conflictGraph.addStallSite( taint2Effects, rhs );
1317 conflictGraph.addStallSite( taint2Effects, lhs );
1321 case FKind.FlatCall: {
1322 FlatCall fc = (FlatCall) fn;
1325 conflictGraph.addStallSite( taint2Effects, lhs );
1330 if( conflictGraph.id2cn.size() > 0 ) {
1331 sese2conflictGraph.put( currentSESE, conflictGraph );
1337 private void calculateConflicts( Set<FlatNew> sitesToFlag,
1338 boolean useReachInfo ) {
1340 // decide fine-grain edge or coarse-grain edge among all vertexes by
1341 // pair-wise comparison
1342 Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
1343 while (seseIter.hasNext()) {
1344 FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next();
1345 ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
1348 // clear current conflict before recalculating with reachability info
1349 conflictGraph.clearAllConflictEdge();
1350 conflictGraph.setDisJointAnalysis(disjointAnalysisReach);
1351 conflictGraph.setFMEnclosing(sese.getfmEnclosing());
1353 conflictGraph.analyzeConflicts(sitesToFlag, useReachInfo);
1354 sese2conflictGraph.put(sese, conflictGraph);
1359 private void writeConflictGraph() {
1360 Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
1361 while (keyEnum.hasMoreElements()) {
1362 FlatNode key = (FlatNode) keyEnum.nextElement();
1363 ConflictGraph cg = sese2conflictGraph.get(key);
1365 if (cg.hasConflictEdge()) {
1366 cg.writeGraph("ConflictGraphFor" + key, false);
1368 } catch (IOException e) {
1369 System.out.println("Error writing");
1376 // the traversal for pruning state machines and finding
1377 // machines that are weakly connected BOTH consider conflicting
1378 // effects between heap roots, so it is smart to compute all of
1380 public void pruneMachinesAndFindWeaklyConnectedExaminers() {
1381 ProcessStateMachines psm=new ProcessStateMachines(buildStateMachines, rblockRel);
1383 buildStateMachines.writeStateMachines("pruned");
1388 private void synthesizeLocks() {
1389 // for every conflict graph, generate a set of memory queues
1390 // (called SESELock in this code!) to cover the graph
1391 Set<Map.Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
1392 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
1393 Map.Entry<FlatNode, ConflictGraph> graphEntry = (Map.Entry<FlatNode, ConflictGraph>) iterator.next();
1394 FlatNode sese = graphEntry.getKey();
1395 ConflictGraph conflictGraph = graphEntry.getValue();
1396 calculateCovering(conflictGraph);
1400 private void calculateCovering(ConflictGraph conflictGraph) {
1401 uniqueLockSetId = 0; // reset lock counter for every new conflict graph
1402 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1403 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1404 HashSet<SESELock> lockSet = new HashSet<SESELock>();
1406 Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1407 for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
1408 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1409 if (conflictEdge.isCoarseEdge()) {
1410 coarseToCover.add(conflictEdge);
1412 fineToCover.add(conflictEdge);
1416 HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
1417 toCover.addAll(fineToCover);
1418 toCover.addAll(coarseToCover);
1420 while (!toCover.isEmpty()) {
1422 SESELock seseLock = new SESELock();
1423 seseLock.setID(uniqueLockSetId++);
1427 do { // fine-grained edge
1431 for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) {
1434 ConflictEdge edge = (ConflictEdge) iterator.next();
1435 if (seseLock.getConflictNodeSet().size() == 0) {
1437 if (seseLock.isWriteNode(edge.getVertexU())) {
1438 // mark as fine_write
1439 if (edge.getVertexU().isStallSiteNode()) {
1440 type = ConflictNode.PARENT_WRITE;
1442 type = ConflictNode.FINE_WRITE;
1444 seseLock.addConflictNode(edge.getVertexU(), type);
1446 // mark as fine_read
1447 if (edge.getVertexU().isStallSiteNode()) {
1448 type = ConflictNode.PARENT_READ;
1450 type = ConflictNode.FINE_READ;
1452 seseLock.addConflictNode(edge.getVertexU(), type);
1454 if (edge.getVertexV() != edge.getVertexU()) {
1455 if (seseLock.isWriteNode(edge.getVertexV())) {
1456 // mark as fine_write
1457 if (edge.getVertexV().isStallSiteNode()) {
1458 type = ConflictNode.PARENT_WRITE;
1460 type = ConflictNode.FINE_WRITE;
1462 seseLock.addConflictNode(edge.getVertexV(), type);
1464 // mark as fine_read
1465 if (edge.getVertexV().isStallSiteNode()) {
1466 type = ConflictNode.PARENT_READ;
1468 type = ConflictNode.FINE_READ;
1470 seseLock.addConflictNode(edge.getVertexV(), type);
1474 seseLock.addConflictEdge(edge);
1475 fineToCover.remove(edge);
1476 break;// exit iterator loop
1477 }// end of initial setup
1479 ConflictNode newNode;
1480 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1481 // new node has a fine-grained edge to all current node
1482 // If there is a coarse grained edge where need a fine edge, it's
1483 // okay to add the node
1484 // but the edge must remain uncovered.
1488 if (seseLock.containsConflictNode(newNode)) {
1489 seseLock.addEdge(edge);
1490 fineToCover.remove(edge);
1494 if (seseLock.isWriteNode(newNode)) {
1495 if (newNode.isStallSiteNode()) {
1496 type = ConflictNode.PARENT_WRITE;
1498 type = ConflictNode.FINE_WRITE;
1500 seseLock.setNodeType(newNode, type);
1502 if (newNode.isStallSiteNode()) {
1503 type = ConflictNode.PARENT_READ;
1505 type = ConflictNode.FINE_READ;
1507 seseLock.setNodeType(newNode, type);
1510 seseLock.addEdge(edge);
1511 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1512 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1513 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1515 // mark all fine edges between new node and nodes in the group as
1517 if (!conflictEdge.getVertexU().equals(newNode)) {
1518 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1520 seseLock.addConflictEdge(conflictEdge);
1521 fineToCover.remove(conflictEdge);
1523 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1524 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1526 seseLock.addConflictEdge(conflictEdge);
1527 fineToCover.remove(conflictEdge);
1533 break;// exit iterator loop
1538 HashSet<ConflictEdge> notCovered=new HashSet<ConflictEdge>();
1542 for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) {
1544 ConflictEdge edge = (ConflictEdge) iterator.next();
1545 if (seseLock.getConflictNodeSet().size() == 0) {
1547 if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
1548 // node has a coarse-grained edge with itself
1549 if (!(edge.getVertexU().isStallSiteNode())) {
1550 // and it is not parent
1551 type = ConflictNode.SCC;
1554 type = ConflictNode.PARENT_COARSE;
1556 type = ConflictNode.PARENT_WRITE;
1559 seseLock.addConflictNode(edge.getVertexU(), type);
1561 if (edge.getVertexU().isStallSiteNode()) {
1563 type = ConflictNode.PARENT_COARSE;
1565 if (edge.getVertexU().getWriteEffectSet().isEmpty()) {
1566 type = ConflictNode.PARENT_READ;
1568 type = ConflictNode.PARENT_WRITE;
1572 type = ConflictNode.COARSE;
1574 seseLock.addConflictNode(edge.getVertexU(), type);
1576 if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
1577 // node has a coarse-grained edge with itself
1578 if (!(edge.getVertexV().isStallSiteNode())) {
1579 // and it is not parent
1580 type = ConflictNode.SCC;
1583 type = ConflictNode.PARENT_COARSE;
1585 type = ConflictNode.PARENT_WRITE;
1588 seseLock.addConflictNode(edge.getVertexV(), type);
1590 if (edge.getVertexV().isStallSiteNode()) {
1592 type = ConflictNode.PARENT_COARSE;
1594 if (edge.getVertexV().getWriteEffectSet().isEmpty()) {
1595 type = ConflictNode.PARENT_READ;
1597 type = ConflictNode.PARENT_WRITE;
1601 type = ConflictNode.COARSE;
1603 seseLock.addConflictNode(edge.getVertexV(), type);
1606 coarseToCover.remove(edge);
1607 seseLock.addConflictEdge(edge);
1608 break;// exit iterator loop
1609 }// end of initial setup
1611 ConflictNode newNode;
1612 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1613 // new node has a coarse-grained edge to all fine-read, fine-write,
1617 if (newNode.isInVarNode() && (!seseLock.hasSelfCoarseEdge(newNode))
1618 && seseLock.hasCoarseEdgeWithParentCoarse(newNode)) {
1619 // this case can't be covered by this queue
1620 coarseToCover.remove(edge);
1621 notCovered.add(edge);
1625 if (seseLock.containsConflictNode(newNode)) {
1626 seseLock.addEdge(edge);
1627 coarseToCover.remove(edge);
1631 if (seseLock.hasSelfCoarseEdge(newNode)) {
1633 if (newNode.isStallSiteNode()) {
1634 type = ConflictNode.PARENT_COARSE;
1636 type = ConflictNode.SCC;
1638 seseLock.setNodeType(newNode, type);
1640 if (newNode.isStallSiteNode()) {
1641 type = ConflictNode.PARENT_COARSE;
1643 type = ConflictNode.COARSE;
1645 seseLock.setNodeType(newNode, type);
1648 seseLock.addEdge(edge);
1649 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1650 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1651 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1652 // mark all coarse edges between new node and nodes in the group
1654 if (!conflictEdge.getVertexU().equals(newNode)) {
1655 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1657 seseLock.addConflictEdge(conflictEdge);
1658 coarseToCover.remove(conflictEdge);
1660 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1661 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1663 seseLock.addConflictEdge(conflictEdge);
1664 coarseToCover.remove(conflictEdge);
1669 break;// exit iterator loop
1675 lockSet.add(seseLock);
1678 coarseToCover.addAll(notCovered);
1679 toCover.addAll(fineToCover);
1680 toCover.addAll(coarseToCover);
1684 conflictGraph2SESELock.put(conflictGraph, lockSet);
1687 public ConflictGraph getConflictGraph(FlatNode sese) {
1688 return sese2conflictGraph.get(sese);
1691 public Set<SESELock> getLockMappings(ConflictGraph graph) {
1692 return conflictGraph2SESELock.get(graph);
1695 public Set<FlatSESEEnterNode> getAllSESEs() {
1696 return rblockRel.getAllSESEs();
1699 public FlatSESEEnterNode getMainSESE() {
1700 return rblockRel.getMainSESE();
1703 public FlatSESEEnterNode getCallerProxySESE() {
1704 return rblockRel.getCallerProxySESE();
1707 public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks( FlatNode fn ) {
1708 return rblockRel.getPossibleExecutingRBlocks( fn );
1712 public void writeReports(String timeReport) throws java.io.IOException {
1714 BufferedWriter bw = new BufferedWriter(new FileWriter("ooojReport_summary.txt"));
1715 bw.write("OoOJava Analysis Results\n\n");
1716 bw.write(timeReport + "\n\n");
1717 printSESEHierarchy(bw);
1722 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
1723 while (methItr.hasNext()) {
1724 MethodDescriptor md = methItr.next();
1725 FlatMethod fm = state.getMethodFlat(md);
1727 bw = new BufferedWriter(new FileWriter("ooojReport_" +
1728 md.getClassMethodName() +
1729 md.getSafeMethodDescriptor() +
1731 bw.write("OoOJava Results for " + md + "\n-------------------\n");
1733 bw.write("Dynamic vars to manage:\n " + getContextTaskNames( fm ).getDynamicVarSet() );
1735 bw.write("\n\nLive-In, Root View\n------------------\n" + fm.printMethod(livenessGlobalView));
1736 bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults));
1737 bw.write("\n\nNot Available Results-Out\n---------------------\n" + fm.printMethod(notAvailableResults));
1738 bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans));
1744 private void printSESEHierarchy(BufferedWriter bw) throws java.io.IOException {
1745 bw.write("SESE Local Hierarchy\n--------------\n");
1746 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getLocalRootSESEs().iterator();
1747 while (rootItr.hasNext()) {
1748 FlatSESEEnterNode root = rootItr.next();
1749 printSESEHierarchyTree(bw, root, 0);
1753 private void printSESEHierarchyTree(BufferedWriter bw,
1754 FlatSESEEnterNode fsen,
1756 ) throws java.io.IOException {
1757 for (int i = 0; i < depth; ++i) {
1760 bw.write("- " + fsen.getPrettyIdentifier() + "\n");
1762 Iterator<FlatSESEEnterNode> childItr = fsen.getLocalChildren().iterator();
1763 while (childItr.hasNext()) {
1764 FlatSESEEnterNode fsenChild = childItr.next();
1765 printSESEHierarchyTree(bw, fsenChild, depth + 1);
1769 private void printSESEInfo(BufferedWriter bw) throws java.io.IOException {
1770 bw.write("\nSESE info\n-------------\n");
1771 Iterator<FlatSESEEnterNode> fsenItr = rblockRel.getAllSESEs().iterator();
1772 while( fsenItr.hasNext() ) {
1773 FlatSESEEnterNode fsen = fsenItr.next();
1775 bw.write("SESE " + fsen.getPrettyIdentifier());
1776 if( fsen.getIsLeafSESE() ) {
1777 bw.write(" (leaf)");
1781 bw.write(" in-set: " + fsen.getInVarSet() + "\n");
1782 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1783 while (tItr.hasNext()) {
1784 TempDescriptor inVar = tItr.next();
1785 if (fsen.getReadyInVarSet().contains(inVar)) {
1786 bw.write(" (ready) " + inVar + "\n");
1788 if (fsen.getStaticInVarSet().contains(inVar)) {
1789 bw.write(" (static) " + inVar + " from " + fsen.getStaticInVarSrc(inVar) + "\n");
1791 if (fsen.getDynamicInVarSet().contains(inVar)) {
1792 bw.write(" (dynamic)" + inVar + "\n");
1796 bw.write(" Dynamic vars to manage: " + getContextTaskNames( fsen ).getDynamicVarSet() + "\n");
1798 bw.write(" out-set: " + fsen.getOutVarSet() + "\n");
1799 tItr = fsen.getOutVarSet().iterator();
1800 while (tItr.hasNext()) {
1801 TempDescriptor outVar = tItr.next();
1802 if (fsen.getReadyOutVarSet().contains(outVar)) {
1803 bw.write(" (ready) " + outVar + "\n");
1805 if (fsen.getStaticOutVarSet().contains(outVar)) {
1806 bw.write(" (static) " + outVar + " from " + fsen.getStaticOutVarSrc(outVar) + "\n");
1808 if (fsen.getDynamicOutVarSet().contains(outVar)) {
1809 bw.write(" (dynamic)" + outVar + "\n");
1813 bw.write(" local parent: " + fsen.getLocalParent() + "\n");
1814 bw.write(" local children: " + fsen.getLocalChildren() + "\n");
1816 bw.write(" possible parents: " + fsen.getParents() + "\n");
1817 bw.write(" possible children: " + fsen.getChildren() + "\n");