1 package Analysis.OoOJava;
3 import java.io.BufferedWriter;
4 import java.io.FileWriter;
5 import java.io.IOException;
6 import java.util.Enumeration;
7 import java.util.HashSet;
8 import java.util.Hashtable;
9 import java.util.Iterator;
12 import java.util.Stack;
13 import java.util.Map.Entry;
15 import Analysis.ArrayReferencees;
16 import Analysis.Liveness;
17 import Analysis.CallGraph.CallGraph;
18 import Analysis.Disjoint.DisjointAnalysis;
19 import Analysis.Disjoint.Effect;
20 import Analysis.Disjoint.EffectsAnalysis;
21 import Analysis.Disjoint.Taint;
22 import Analysis.MLP.CodePlan;
23 import Analysis.MLP.SESEandAgePair;
24 import Analysis.MLP.VSTWrapper;
25 import Analysis.MLP.VarSrcTokTable;
26 import Analysis.MLP.VariableSourceToken;
28 import IR.MethodDescriptor;
33 import IR.Flat.FlatCall;
34 import IR.Flat.FlatEdge;
35 import IR.Flat.FlatElementNode;
36 import IR.Flat.FlatFieldNode;
37 import IR.Flat.FlatMethod;
38 import IR.Flat.FlatNew;
39 import IR.Flat.FlatNode;
40 import IR.Flat.FlatOpNode;
41 import IR.Flat.FlatSESEEnterNode;
42 import IR.Flat.FlatSESEExitNode;
43 import IR.Flat.FlatSetElementNode;
44 import IR.Flat.FlatSetFieldNode;
45 import IR.Flat.FlatWriteDynamicVarNode;
46 import IR.Flat.TempDescriptor;
48 public class OoOJavaAnalysis {
50 // data from the compiler
52 private TypeUtil typeUtil;
53 private CallGraph callGraph;
54 private RBlockRelationAnalysis rblockRel;
55 private RBlockStatusAnalysis rblockStatus;
56 private DisjointAnalysis disjointAnalysisTaints;
57 private DisjointAnalysis disjointAnalysisReach;
59 private Hashtable<FlatNode, Set<TempDescriptor>> livenessRootView;
60 private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
61 private Hashtable<FlatNode, VarSrcTokTable> variableResults;
62 private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
63 private Hashtable<FlatNode, CodePlan> codePlans;
65 private Hashtable<FlatSESEEnterNode, Set<TempDescriptor>> notAvailableIntoSESE;
67 private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
69 // temporal data structures to track analysis progress.
70 static private int uniqueLockSetId = 0;
71 // mapping of a conflict graph to its compiled lock
72 private Hashtable<ConflictGraph, HashSet<SESELock>> conflictGraph2SESELock;
73 // mapping of a sese block to its conflict graph
74 private Hashtable<FlatNode, ConflictGraph> sese2conflictGraph;
76 public static int maxSESEage = -1;
78 public int getMaxSESEage() {
83 public CodePlan getCodePlan(FlatNode fn) {
84 CodePlan cp = codePlans.get(fn);
88 public OoOJavaAnalysis(State state, TypeUtil typeUtil, CallGraph callGraph, Liveness liveness,
89 ArrayReferencees arrayReferencees) {
91 double timeStartAnalysis = (double) System.nanoTime();
94 this.typeUtil = typeUtil;
95 this.callGraph = callGraph;
96 this.maxSESEage = state.MLP_MAXSESEAGE;
98 livenessRootView = new Hashtable<FlatNode, Set<TempDescriptor>>();
99 livenessVirtualReads = new Hashtable<FlatNode, Set<TempDescriptor>>();
100 variableResults = new Hashtable<FlatNode, VarSrcTokTable>();
101 notAvailableResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
102 codePlans = new Hashtable<FlatNode, CodePlan>();
103 wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
105 notAvailableIntoSESE = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
107 sese2conflictGraph = new Hashtable<FlatNode, ConflictGraph>();
108 conflictGraph2SESELock = new Hashtable<ConflictGraph, HashSet<SESELock>>();
110 // add all methods transitively reachable from the
111 // source's main to set for analysis
112 MethodDescriptor mdSourceEntry = typeUtil.getMain();
113 FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
115 Set<MethodDescriptor> descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
117 descriptorsToAnalyze.add(mdSourceEntry);
120 // 1st pass, find basic rblock relations & status
121 rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph);
122 rblockStatus = new RBlockStatusAnalysis(state, typeUtil, callGraph, rblockRel);
125 // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
126 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getRootSESEs().iterator();
127 while (rootItr.hasNext()) {
128 FlatSESEEnterNode root = rootItr.next();
129 livenessAnalysisBackward(root, true, null);
132 // 3rd pass, variable analysis
133 Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
134 while (methItr.hasNext()) {
135 Descriptor d = methItr.next();
136 FlatMethod fm = state.getMethodFlat(d);
138 // starting from roots do a forward, fixed-point
139 // variable analysis for refinement and stalls
140 variableAnalysisForward(fm);
143 // 4th pass, compute liveness contribution from
144 // virtual reads discovered in variable pass
145 rootItr = rblockRel.getRootSESEs().iterator();
146 while (rootItr.hasNext()) {
147 FlatSESEEnterNode root = rootItr.next();
148 livenessAnalysisBackward(root, true, null);
151 // 5th pass, use disjointness with NO FLAGGED REGIONS
152 // to compute taints and effects
153 disjointAnalysisTaints =
154 new DisjointAnalysis(state,
159 null, // no FlatNew set to flag
164 // 6th pass, not available analysis FOR VARIABLES!
165 methItr = descriptorsToAnalyze.iterator();
166 while (methItr.hasNext()) {
167 Descriptor d = methItr.next();
168 FlatMethod fm = state.getMethodFlat(d);
170 // compute what is not available at every program
171 // point, in a forward fixed-point pass
172 notAvailableForward(fm);
175 // 7th pass, make conflict graph
176 // conflict graph is maintained by each parent sese,
177 Iterator descItr=disjointAnalysisTaints.getDescriptorsToAnalyze().iterator();
178 while (descItr.hasNext()) {
179 Descriptor d = (Descriptor)descItr.next();
180 FlatMethod fm = state.getMethodFlat(d);
182 makeConflictGraph(fm);
187 Iterator iter = sese2conflictGraph.entrySet().iterator();
188 while (iter.hasNext()) {
189 Entry e = (Entry) iter.next();
190 FlatNode fn = (FlatNode) e.getKey();
191 ConflictGraph conflictGraph = (ConflictGraph) e.getValue();
192 System.out.println("---------------------------------------");
193 System.out.println("CONFLICT GRAPH for " + fn);
194 Set<String> keySet = conflictGraph.id2cn.keySet();
195 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
196 String key = (String) iterator.next();
197 ConflictNode node = conflictGraph.id2cn.get(key);
198 System.out.println("key=" + key + " \n" + node.toStringAllEffects());
203 // 8th pass, calculate all possible conflicts without using reachability info
204 // and identify set of FlatNew that next disjoint reach. analysis should flag
205 Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
206 calculateConflicts(sitesToFlag,false);
208 // 9th pass, ask disjoint analysis to compute reachability
209 // for objects that may cause heap conflicts so the most
210 // efficient method to deal with conflict can be computed
213 disjointAnalysisReach =
214 new DisjointAnalysis(state,
220 null, // don't do effects analysis again!
221 null // don't do effects analysis again!
223 // 10th pass, calculate conflicts with reachability info
224 calculateConflicts(null, true);
226 // 11th pass, compiling locks
229 // 12th pass, compute a plan for code injections
230 methItr =descriptorsToAnalyze.iterator();
231 while( methItr.hasNext() ) {
232 Descriptor d = methItr.next();
233 FlatMethod fm = state.getMethodFlat( d );
234 codePlansForward( fm );
238 // splice new IR nodes into graph after all
239 // analysis passes are complete
240 Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator();
241 while( spliceItr.hasNext() ) {
242 Map.Entry me = (Map.Entry) spliceItr.next();
243 FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
244 fwdvn.spliceIntoIR();
248 if( state.OOODEBUG ) {
251 disjointAnalysisTaints.getEffectsAnalysis().writeEffects( "effects.txt" );
252 writeConflictGraph();
253 } catch( IOException e ) {}
258 private void writeFile(Set<FlatNew> sitesToFlag){
261 BufferedWriter bw = new BufferedWriter( new FileWriter( "sitesToFlag.txt" ) );
263 for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext();) {
264 FlatNew fn = (FlatNew) iterator.next();
268 }catch(IOException e){
274 private void livenessAnalysisBackward(FlatSESEEnterNode fsen, boolean toplevel,
275 Hashtable<FlatSESEExitNode, Set<TempDescriptor>> liveout) {
277 // start from an SESE exit, visit nodes in reverse up to
278 // SESE enter in a fixed-point scheme, where children SESEs
279 // should already be analyzed and therefore can be skipped
280 // because child SESE enter node has all necessary info
281 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
284 flatNodesToVisit.add(fsen.getfmEnclosing().getFlatExit());
286 flatNodesToVisit.add(fsen.getFlatExit());
289 Hashtable<FlatNode, Set<TempDescriptor>> livenessResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
292 liveout = new Hashtable<FlatSESEExitNode, Set<TempDescriptor>>();
295 while (!flatNodesToVisit.isEmpty()) {
296 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
297 flatNodesToVisit.remove(fn);
299 Set<TempDescriptor> prev = livenessResults.get(fn);
301 // merge sets from control flow joins
302 Set<TempDescriptor> u = new HashSet<TempDescriptor>();
303 for (int i = 0; i < fn.numNext(); i++) {
304 FlatNode nn = fn.getNext(i);
305 Set<TempDescriptor> s = livenessResults.get(nn);
311 Set<TempDescriptor> curr = liveness_nodeActions(fn, u, fsen, toplevel, liveout);
313 // if a new result, schedule backward nodes for analysis
314 if (!curr.equals(prev)) {
315 livenessResults.put(fn, curr);
317 // don't flow backwards past current SESE enter
318 if (!fn.equals(fsen)) {
319 for (int i = 0; i < fn.numPrev(); i++) {
320 FlatNode nn = fn.getPrev(i);
321 flatNodesToVisit.add(nn);
327 Set<TempDescriptor> s = livenessResults.get(fsen);
332 // remember liveness per node from the root view as the
333 // global liveness of variables for later passes to use
335 livenessRootView.putAll(livenessResults);
338 // post-order traversal, so do children first
339 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
340 while (childItr.hasNext()) {
341 FlatSESEEnterNode fsenChild = childItr.next();
342 livenessAnalysisBackward(fsenChild, false, liveout);
346 private Set<TempDescriptor> liveness_nodeActions(FlatNode fn, Set<TempDescriptor> liveIn,
347 FlatSESEEnterNode currentSESE, boolean toplevel,
348 Hashtable<FlatSESEExitNode, Set<TempDescriptor>> liveout) {
351 case FKind.FlatSESEExitNode:
353 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
354 if (!liveout.containsKey(fsexn)) {
355 liveout.put(fsexn, new HashSet<TempDescriptor>());
357 liveout.get(fsexn).addAll(liveIn);
359 // no break, sese exits should also execute default actions
362 // handle effects of statement in reverse, writes then reads
363 TempDescriptor[] writeTemps = fn.writesTemps();
364 for (int i = 0; i < writeTemps.length; ++i) {
365 liveIn.remove(writeTemps[i]);
368 FlatSESEExitNode fsexn = currentSESE.getFlatExit();
369 Set<TempDescriptor> livetemps = liveout.get(fsexn);
370 if (livetemps != null && livetemps.contains(writeTemps[i])) {
371 // write to a live out temp...
372 // need to put in SESE liveout set
373 currentSESE.addOutVar(writeTemps[i]);
378 TempDescriptor[] readTemps = fn.readsTemps();
379 for (int i = 0; i < readTemps.length; ++i) {
380 liveIn.add(readTemps[i]);
383 Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get(fn);
384 if (virtualReadTemps != null) {
385 liveIn.addAll(virtualReadTemps);
396 private void variableAnalysisForward(FlatMethod fm) {
398 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
399 flatNodesToVisit.add(fm);
401 while (!flatNodesToVisit.isEmpty()) {
402 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
403 flatNodesToVisit.remove(fn);
405 Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
406 assert seseStack != null;
408 VarSrcTokTable prev = variableResults.get(fn);
410 // merge sets from control flow joins
411 VarSrcTokTable curr = new VarSrcTokTable();
412 for (int i = 0; i < fn.numPrev(); i++) {
413 FlatNode nn = fn.getPrev(i);
414 VarSrcTokTable incoming = variableResults.get(nn);
415 curr.merge(incoming);
418 if (!seseStack.empty()) {
419 variable_nodeActions(fn, curr, seseStack.peek());
422 // if a new result, schedule forward nodes for analysis
423 if (!curr.equals(prev)) {
424 variableResults.put(fn, curr);
426 for (int i = 0; i < fn.numNext(); i++) {
427 FlatNode nn = fn.getNext(i);
428 flatNodesToVisit.add(nn);
434 private void variable_nodeActions(FlatNode fn, VarSrcTokTable vstTable,
435 FlatSESEEnterNode currentSESE) {
438 case FKind.FlatSESEEnterNode: {
439 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
440 assert fsen.equals(currentSESE);
442 vstTable.age(currentSESE);
443 vstTable.assertConsistency();
447 case FKind.FlatSESEExitNode: {
448 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
449 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
450 assert currentSESE.getChildren().contains(fsen);
452 // remap all of this child's children tokens to be
453 // from this child as the child exits
454 vstTable.remapChildTokens(fsen);
456 // liveness virtual reads are things that might be
457 // written by an SESE and should be added to the in-set
458 // anything virtually read by this SESE should be pruned
459 // of parent or sibling sources
460 Set<TempDescriptor> liveVars = livenessRootView.get(fn);
461 Set<TempDescriptor> fsenVirtReads = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(
463 Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get(fn);
464 if (fsenVirtReadsOld != null) {
465 fsenVirtReads.addAll(fsenVirtReadsOld);
467 livenessVirtualReads.put(fn, fsenVirtReads);
469 // then all child out-set tokens are guaranteed
470 // to be filled in, so clobber those entries with
471 // the latest, clean sources
472 Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
473 while (outVarItr.hasNext()) {
474 TempDescriptor outVar = outVarItr.next();
475 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
477 VariableSourceToken vst = new VariableSourceToken(ts, fsen, new Integer(0), outVar);
478 vstTable.remove(outVar);
481 vstTable.assertConsistency();
486 case FKind.FlatOpNode: {
487 FlatOpNode fon = (FlatOpNode) fn;
489 if (fon.getOp().getOp() == Operation.ASSIGN) {
490 TempDescriptor lhs = fon.getDest();
491 TempDescriptor rhs = fon.getLeft();
493 vstTable.remove(lhs);
495 Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
497 Iterator<VariableSourceToken> itr = vstTable.get(rhs).iterator();
498 while (itr.hasNext()) {
499 VariableSourceToken vst = itr.next();
501 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
504 if (currentSESE.getChildren().contains(vst.getSESE())) {
505 // if the source comes from a child, copy it over
506 forAddition.add(new VariableSourceToken(ts, vst.getSESE(), vst.getAge(), vst
509 // otherwise, stamp it as us as the source
510 forAddition.add(new VariableSourceToken(ts, currentSESE, new Integer(0), lhs));
514 vstTable.addAll(forAddition);
516 // only break if this is an ASSIGN op node,
517 // otherwise fall through to default case
518 vstTable.assertConsistency();
523 // note that FlatOpNode's that aren't ASSIGN
524 // fall through to this default case
526 TempDescriptor[] writeTemps = fn.writesTemps();
527 if (writeTemps.length > 0) {
529 // for now, when writeTemps > 1, make sure
530 // its a call node, programmer enforce only
531 // doing stuff like calling a print routine
532 // assert writeTemps.length == 1;
533 if (writeTemps.length > 1) {
534 assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod;
538 vstTable.remove(writeTemps[0]);
540 HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
541 ts.add(writeTemps[0]);
543 vstTable.add(new VariableSourceToken(ts, currentSESE, new Integer(0), writeTemps[0]));
546 vstTable.assertConsistency();
553 private void notAvailableForward(FlatMethod fm) {
555 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
556 flatNodesToVisit.add(fm);
558 while (!flatNodesToVisit.isEmpty()) {
559 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
560 flatNodesToVisit.remove(fn);
562 Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
563 assert seseStack != null;
565 Set<TempDescriptor> prev = notAvailableResults.get(fn);
567 Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
568 for (int i = 0; i < fn.numPrev(); i++) {
569 FlatNode nn = fn.getPrev(i);
570 Set<TempDescriptor> notAvailIn = notAvailableResults.get(nn);
571 if (notAvailIn != null) {
572 curr.addAll(notAvailIn);
576 if (!seseStack.empty()) {
577 notAvailable_nodeActions(fn, curr, seseStack.peek());
580 // if a new result, schedule forward nodes for analysis
581 if (!curr.equals(prev)) {
582 notAvailableResults.put(fn, curr);
584 for (int i = 0; i < fn.numNext(); i++) {
585 FlatNode nn = fn.getNext(i);
586 flatNodesToVisit.add(nn);
592 private void notAvailable_nodeActions(FlatNode fn, Set<TempDescriptor> notAvailSet,
593 FlatSESEEnterNode currentSESE) {
595 // any temps that are removed from the not available set
596 // at this node should be marked in this node's code plan
597 // as temps to be grabbed at runtime!
601 case FKind.FlatSESEEnterNode: {
602 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
603 assert fsen.equals(currentSESE);
605 // keep a copy of what's not available into the SESE
606 // and restore it at the matching exit node
607 Set<TempDescriptor> notAvailCopy = new HashSet<TempDescriptor>();
608 Iterator<TempDescriptor> tdItr = notAvailSet.iterator();
609 while (tdItr.hasNext()) {
610 notAvailCopy.add(tdItr.next());
612 notAvailableIntoSESE.put(fsen, notAvailCopy);
618 case FKind.FlatSESEExitNode: {
619 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
620 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
621 assert currentSESE.getChildren().contains(fsen);
623 notAvailSet.addAll(fsen.getOutVarSet());
625 Set<TempDescriptor> notAvailIn = notAvailableIntoSESE.get(fsen);
626 assert notAvailIn != null;
627 notAvailSet.addAll(notAvailIn);
632 case FKind.FlatMethod: {
636 case FKind.FlatOpNode: {
637 FlatOpNode fon = (FlatOpNode) fn;
639 if (fon.getOp().getOp() == Operation.ASSIGN) {
640 TempDescriptor lhs = fon.getDest();
641 TempDescriptor rhs = fon.getLeft();
643 // copy makes lhs same availability as rhs
644 if (notAvailSet.contains(rhs)) {
645 notAvailSet.add(lhs);
647 notAvailSet.remove(lhs);
650 // only break if this is an ASSIGN op node,
651 // otherwise fall through to default case
656 // note that FlatOpNode's that aren't ASSIGN
657 // fall through to this default case
659 TempDescriptor[] writeTemps = fn.writesTemps();
660 for (int i = 0; i < writeTemps.length; i++) {
661 TempDescriptor wTemp = writeTemps[i];
662 notAvailSet.remove(wTemp);
664 TempDescriptor[] readTemps = fn.readsTemps();
665 for (int i = 0; i < readTemps.length; i++) {
666 TempDescriptor rTemp = readTemps[i];
667 notAvailSet.remove(rTemp);
669 // if this variable has exactly one source, potentially
670 // get other things from this source as well
671 VarSrcTokTable vstTable = variableResults.get(fn);
673 VSTWrapper vstIfStatic = new VSTWrapper();
674 Integer srcType = vstTable.getRefVarSrcType(rTemp, currentSESE, vstIfStatic);
676 if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
678 VariableSourceToken vst = vstIfStatic.vst;
680 Iterator<VariableSourceToken> availItr = vstTable.get(vst.getSESE(), vst.getAge())
683 // look through things that are also available from same source
684 while (availItr.hasNext()) {
685 VariableSourceToken vstAlsoAvail = availItr.next();
687 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
688 while (refVarItr.hasNext()) {
689 TempDescriptor refVarAlso = refVarItr.next();
691 // if a variable is available from the same source, AND it ALSO
692 // only comes from one statically known source, mark it available
693 VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
694 Integer srcTypeAlso = vstTable.getRefVarSrcType(refVarAlso, currentSESE,
696 if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
697 notAvailSet.remove(refVarAlso);
710 private void codePlansForward( FlatMethod fm ) {
712 // start from flat method top, visit every node in
713 // method exactly once
714 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
715 flatNodesToVisit.add( fm );
717 Set<FlatNode> visited = new HashSet<FlatNode>();
719 while( !flatNodesToVisit.isEmpty() ) {
720 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
721 FlatNode fn = fnItr.next();
723 flatNodesToVisit.remove( fn );
726 Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
727 assert seseStack != null;
729 // use incoming results as "dot statement" or just
730 // before the current statement
731 VarSrcTokTable dotSTtable = new VarSrcTokTable();
732 for( int i = 0; i < fn.numPrev(); i++ ) {
733 FlatNode nn = fn.getPrev( i );
734 dotSTtable.merge( variableResults.get( nn ) );
737 // find dt-st notAvailableSet also
738 Set<TempDescriptor> dotSTnotAvailSet = new HashSet<TempDescriptor>();
739 for( int i = 0; i < fn.numPrev(); i++ ) {
740 FlatNode nn = fn.getPrev( i );
741 Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
742 if( notAvailIn != null ) {
743 dotSTnotAvailSet.addAll( notAvailIn );
747 Set<TempDescriptor> dotSTlive = livenessRootView.get( fn );
749 if( !seseStack.empty() ) {
750 codePlans_nodeActions( fn,
758 for( int i = 0; i < fn.numNext(); i++ ) {
759 FlatNode nn = fn.getNext( i );
761 if( !visited.contains( nn ) ) {
762 flatNodesToVisit.add( nn );
768 private void codePlans_nodeActions( FlatNode fn,
769 Set<TempDescriptor> liveSetIn,
770 VarSrcTokTable vstTableIn,
771 Set<TempDescriptor> notAvailSetIn,
772 FlatSESEEnterNode currentSESE ) {
774 CodePlan plan = new CodePlan( currentSESE);
776 switch( fn.kind() ) {
778 case FKind.FlatSESEEnterNode: {
779 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
780 assert fsen.equals( currentSESE );
782 // track the source types of the in-var set so generated
783 // code at this SESE issue can compute the number of
784 // dependencies properly
785 Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
786 while( inVarItr.hasNext() ) {
787 TempDescriptor inVar = inVarItr.next();
789 // when we get to an SESE enter node we change the
790 // currentSESE variable of this analysis to the
791 // child that is declared by the enter node, so
792 // in order to classify in-vars correctly, pass
793 // the parent SESE in--at other FlatNode types just
794 // use the currentSESE
795 VSTWrapper vstIfStatic = new VSTWrapper();
797 vstTableIn.getRefVarSrcType( inVar,
802 // the current SESE needs a local space to track the dynamic
803 // variable and the child needs space in its SESE record
804 if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
805 fsen.addDynamicInVar( inVar );
806 fsen.getParent().addDynamicVar( inVar );
808 } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
809 fsen.addStaticInVar( inVar );
810 VariableSourceToken vst = vstIfStatic.vst;
811 fsen.putStaticInVar2src( inVar, vst );
812 fsen.addStaticInVarSrc( new SESEandAgePair( vst.getSESE(),
817 assert srcType.equals( VarSrcTokTable.SrcType_READY );
818 fsen.addReadyInVar( inVar );
824 case FKind.FlatSESEExitNode: {
825 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
828 case FKind.FlatOpNode: {
829 FlatOpNode fon = (FlatOpNode) fn;
831 if( fon.getOp().getOp() == Operation.ASSIGN ) {
832 TempDescriptor lhs = fon.getDest();
833 TempDescriptor rhs = fon.getLeft();
835 // if this is an op node, don't stall, copy
836 // source and delay until we need to use value
838 // ask whether lhs and rhs sources are dynamic, static, etc.
839 VSTWrapper vstIfStatic = new VSTWrapper();
841 = vstTableIn.getRefVarSrcType( lhs,
846 = vstTableIn.getRefVarSrcType( rhs,
851 if( rhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
852 // if rhs is dynamic going in, lhs will definitely be dynamic
853 // going out of this node, so track that here
854 plan.addDynAssign( lhs, rhs );
855 currentSESE.addDynamicVar( lhs );
856 currentSESE.addDynamicVar( rhs );
858 } else if( lhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
859 // otherwise, if the lhs is dynamic, but the rhs is not, we
860 // need to update the variable's dynamic source as "current SESE"
861 plan.addDynAssign( lhs );
864 // only break if this is an ASSIGN op node,
865 // otherwise fall through to default case
870 // note that FlatOpNode's that aren't ASSIGN
871 // fall through to this default case
874 // a node with no live set has nothing to stall for
875 if( liveSetIn == null ) {
879 TempDescriptor[] readarray = fn.readsTemps();
880 for( int i = 0; i < readarray.length; i++ ) {
881 TempDescriptor readtmp = readarray[i];
883 // ignore temps that are definitely available
884 // when considering to stall on it
885 if( !notAvailSetIn.contains( readtmp ) ) {
889 // check the source type of this variable
890 VSTWrapper vstIfStatic = new VSTWrapper();
892 = vstTableIn.getRefVarSrcType( readtmp,
897 if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
898 // 1) It is not clear statically where this variable will
899 // come from, so dynamically we must keep track
900 // along various control paths, and therefore when we stall,
901 // just stall for the exact thing we need and move on
902 plan.addDynamicStall( readtmp );
903 currentSESE.addDynamicVar( readtmp );
905 } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
906 // 2) Single token/age pair: Stall for token/age pair, and copy
907 // all live variables with same token/age pair at the same
908 // time. This is the same stuff that the notavaialable analysis
909 // marks as now available.
910 VariableSourceToken vst = vstIfStatic.vst;
912 Iterator<VariableSourceToken> availItr =
913 vstTableIn.get( vst.getSESE(), vst.getAge() ).iterator();
915 while( availItr.hasNext() ) {
916 VariableSourceToken vstAlsoAvail = availItr.next();
918 // only grab additional stuff that is live
919 Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
921 Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
922 while( refVarItr.hasNext() ) {
923 TempDescriptor refVar = refVarItr.next();
924 if( liveSetIn.contains( refVar ) ) {
925 copySet.add( refVar );
929 if( !copySet.isEmpty() ) {
930 plan.addStall2CopySet( vstAlsoAvail, copySet );
935 // the other case for srcs is READY, so do nothing
938 // assert that everything being stalled for is in the
939 // "not available" set coming into this flat node and
940 // that every VST identified is in the possible "stall set"
941 // that represents VST's from children SESE's
949 // identify sese-age pairs that are statically useful
950 // and should have an associated SESE variable in code
951 // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER,
952 // AND ALWAYS GIVE NAMES TO PARENTS
953 Set<VariableSourceToken> staticSet = vstTableIn.get();
954 Iterator<VariableSourceToken> vstItr = staticSet.iterator();
955 while( vstItr.hasNext() ) {
956 VariableSourceToken vst = vstItr.next();
958 // placeholder source tokens are useful results, but
959 // the placeholder static name is never needed
960 if( vst.getSESE().getIsCallerSESEplaceholder() ) {
964 FlatSESEEnterNode sese = currentSESE;
965 while( sese != null ) {
966 sese.addNeededStaticName(
967 new SESEandAgePair( vst.getSESE(), vst.getAge() )
969 sese.mustTrackAtLeastAge( vst.getAge() );
971 sese = sese.getParent();
976 codePlans.put( fn, plan );
979 // if any variables at this-node-*dot* have a static source (exactly one vst)
980 // but go to a dynamic source at next-node-*dot*, create a new IR graph
981 // node on that edge to track the sources dynamically
982 VarSrcTokTable thisVstTable = variableResults.get( fn );
983 for( int i = 0; i < fn.numNext(); i++ ) {
984 FlatNode nn = fn.getNext( i );
985 VarSrcTokTable nextVstTable = variableResults.get( nn );
986 Set<TempDescriptor> nextLiveIn = livenessRootView.get( nn );
988 // the table can be null if it is one of the few IR nodes
989 // completely outside of the root SESE scope
990 if( nextVstTable != null && nextLiveIn != null ) {
992 Hashtable<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
993 thisVstTable.getReadyOrStatic2DynamicSet( nextVstTable,
998 if( !readyOrStatic2dynamicSet.isEmpty() ) {
1000 // either add these results to partial fixed-point result
1001 // or make a new one if we haven't made any here yet
1002 FlatEdge fe = new FlatEdge( fn, nn );
1003 FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get( fe );
1005 if( fwdvn == null ) {
1006 fwdvn = new FlatWriteDynamicVarNode( fn,
1008 readyOrStatic2dynamicSet,
1011 wdvNodesToSpliceIn.put( fe, fwdvn );
1013 fwdvn.addMoreVar2Src( readyOrStatic2dynamicSet );
1020 private void makeConflictGraph(FlatMethod fm) {
1022 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1023 flatNodesToVisit.add(fm);
1025 Set<FlatNode> visited = new HashSet<FlatNode>();
1027 while (!flatNodesToVisit.isEmpty()) {
1028 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1029 flatNodesToVisit.remove(fn);
1032 Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
1033 assert seseStack != null;
1035 if (!seseStack.isEmpty()) {
1037 ConflictGraph conflictGraph = sese2conflictGraph.get(seseStack.peek());
1038 if (conflictGraph == null) {
1039 conflictGraph = new ConflictGraph();
1042 conflictGraph_nodeAction(fn, seseStack.peek());
1045 // schedule forward nodes for analysis
1046 for (int i = 0; i < fn.numNext(); i++) {
1047 FlatNode nn = fn.getNext(i);
1048 if (!visited.contains(nn)) {
1049 flatNodesToVisit.add(nn);
1058 private void conflictGraph_nodeAction(FlatNode fn, FlatSESEEnterNode currentSESE) {
1060 ConflictGraph conflictGraph;
1064 EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
1066 switch (fn.kind()) {
1068 case FKind.FlatSESEEnterNode: {
1070 if (currentSESE.getParent() == null) {
1073 conflictGraph = sese2conflictGraph.get(currentSESE.getParent());
1074 if (conflictGraph == null) {
1075 conflictGraph = new ConflictGraph();
1078 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
1080 if (!fsen.getIsCallerSESEplaceholder() && currentSESE.getParent() != null) {
1081 // collects effects set of invar set and generates invar node
1082 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(currentSESE);
1083 conflictGraph.addLiveIn(taint2Effects);
1086 if (conflictGraph.id2cn.size() > 0) {
1087 sese2conflictGraph.put(currentSESE.getParent(), conflictGraph);
1093 case FKind.FlatFieldNode:
1094 case FKind.FlatElementNode: {
1096 conflictGraph = sese2conflictGraph.get(currentSESE);
1097 if (conflictGraph == null) {
1098 conflictGraph = new ConflictGraph();
1101 if (fn instanceof FlatFieldNode) {
1102 FlatFieldNode ffn = (FlatFieldNode) fn;
1105 FlatElementNode fen = (FlatElementNode) fn;
1110 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1111 conflictGraph.addStallSite(taint2Effects, rhs);
1113 if (conflictGraph.id2cn.size() > 0) {
1114 sese2conflictGraph.put(currentSESE, conflictGraph);
1119 case FKind.FlatSetFieldNode:
1120 case FKind.FlatSetElementNode: {
1122 conflictGraph = sese2conflictGraph.get(currentSESE);
1123 if (conflictGraph == null) {
1124 conflictGraph = new ConflictGraph();
1127 if (fn instanceof FlatSetFieldNode) {
1128 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1129 lhs = fsfn.getDst();
1130 rhs = fsfn.getSrc();
1132 FlatSetElementNode fsen = (FlatSetElementNode) fn;
1133 lhs = fsen.getDst();
1134 rhs = fsen.getSrc();
1137 // collects effects of stall site and generates stall site node
1138 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1139 conflictGraph.addStallSite(taint2Effects, rhs);
1140 conflictGraph.addStallSite(taint2Effects, lhs);
1142 if (conflictGraph.id2cn.size() > 0) {
1143 sese2conflictGraph.put(currentSESE, conflictGraph);
1148 case FKind.FlatCall: {
1149 conflictGraph = sese2conflictGraph.get(currentSESE);
1150 if (conflictGraph == null) {
1151 conflictGraph = new ConflictGraph();
1154 FlatCall fc = (FlatCall) fn;
1157 // collects effects of stall site and generates stall site node
1158 Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
1159 conflictGraph.addStallSite(taint2Effects, lhs);
1160 if (conflictGraph.id2cn.size() > 0) {
1161 sese2conflictGraph.put(currentSESE, conflictGraph);
1171 private void calculateConflicts(Set<FlatNew> sitesToFlag, boolean useReachInfo) {
1172 // decide fine-grain edge or coarse-grain edge among all vertexes by
1173 // pair-wise comparison
1174 Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
1175 while (seseIter.hasNext()) {
1176 FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next();
1177 ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
1179 // clear current conflict before recalculating with reachability info
1180 conflictGraph.clearAllConflictEdge();
1181 conflictGraph.setDisJointAnalysis(disjointAnalysisReach);
1182 conflictGraph.setFMEnclosing(sese.getfmEnclosing());
1184 conflictGraph.analyzeConflicts(sitesToFlag, useReachInfo);
1185 sese2conflictGraph.put(sese, conflictGraph);
1189 private void writeConflictGraph() {
1190 Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
1191 while (keyEnum.hasMoreElements()) {
1192 FlatNode key = (FlatNode) keyEnum.nextElement();
1193 ConflictGraph cg = sese2conflictGraph.get(key);
1195 if (cg.hasConflictEdge()) {
1196 cg.writeGraph("ConflictGraphFor" + key, false);
1198 } catch (IOException e) {
1199 System.out.println("Error writing");
1205 private void synthesizeLocks() {
1206 Set<Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
1207 for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
1208 Entry<FlatNode, ConflictGraph> graphEntry = (Entry<FlatNode, ConflictGraph>) iterator.next();
1209 FlatNode sese = graphEntry.getKey();
1210 ConflictGraph conflictGraph = graphEntry.getValue();
1211 calculateCovering(conflictGraph);
1215 private void calculateCovering(ConflictGraph conflictGraph) {
1216 uniqueLockSetId = 0; // reset lock counter for every new conflict graph
1217 HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
1218 HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
1219 HashSet<SESELock> lockSet = new HashSet<SESELock>();
1221 Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
1222 for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
1223 ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
1224 if (conflictEdge.isCoarseEdge()) {
1225 coarseToCover.add(conflictEdge);
1227 fineToCover.add(conflictEdge);
1231 HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
1232 toCover.addAll(fineToCover);
1233 toCover.addAll(coarseToCover);
1235 while (!toCover.isEmpty()) {
1237 SESELock seseLock = new SESELock();
1238 seseLock.setID(uniqueLockSetId++);
1242 do { // fine-grained edge
1246 for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) {
1249 ConflictEdge edge = (ConflictEdge) iterator.next();
1250 if (seseLock.getConflictNodeSet().size() == 0) {
1252 if (seseLock.isWriteNode(edge.getVertexU())) {
1253 // mark as fine_write
1254 if (edge.getVertexU().isStallSiteNode()) {
1255 type = ConflictNode.PARENT_WRITE;
1257 type = ConflictNode.FINE_WRITE;
1259 seseLock.addConflictNode(edge.getVertexU(), type);
1261 // mark as fine_read
1262 if (edge.getVertexU().isStallSiteNode()) {
1263 type = ConflictNode.PARENT_READ;
1265 type = ConflictNode.FINE_READ;
1267 seseLock.addConflictNode(edge.getVertexU(), type);
1269 if (edge.getVertexV() != edge.getVertexU()) {
1270 if (seseLock.isWriteNode(edge.getVertexV())) {
1271 // mark as fine_write
1272 if (edge.getVertexV().isStallSiteNode()) {
1273 type = ConflictNode.PARENT_WRITE;
1275 type = ConflictNode.FINE_WRITE;
1277 seseLock.addConflictNode(edge.getVertexV(), type);
1279 // mark as fine_read
1280 if (edge.getVertexV().isStallSiteNode()) {
1281 type = ConflictNode.PARENT_READ;
1283 type = ConflictNode.FINE_READ;
1285 seseLock.addConflictNode(edge.getVertexV(), type);
1289 seseLock.addConflictEdge(edge);
1290 fineToCover.remove(edge);
1291 break;// exit iterator loop
1292 }// end of initial setup
1294 ConflictNode newNode;
1295 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1296 // new node has a fine-grained edge to all current node
1297 // If there is a coarse grained edge where need a fine edge, it's
1298 // okay to add the node
1299 // but the edge must remain uncovered.
1303 if(seseLock.containsConflictNode(newNode)){
1304 seseLock.addEdge(edge);
1305 fineToCover.remove(edge);
1309 if (seseLock.isWriteNode(newNode)) {
1310 if (newNode.isStallSiteNode()) {
1311 type = ConflictNode.PARENT_WRITE;
1313 type = ConflictNode.FINE_WRITE;
1315 seseLock.setNodeType(newNode, type);
1317 if (newNode.isStallSiteNode()) {
1318 type = ConflictNode.PARENT_READ;
1320 type = ConflictNode.FINE_READ;
1322 seseLock.setNodeType(newNode, type);
1325 seseLock.addEdge(edge);
1326 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1327 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1328 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1330 // mark all fine edges between new node and nodes in the group as
1332 if (!conflictEdge.getVertexU().equals(newNode)) {
1333 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1335 seseLock.addConflictEdge(conflictEdge);
1336 fineToCover.remove(conflictEdge);
1338 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1339 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1341 seseLock.addConflictEdge(conflictEdge);
1342 fineToCover.remove(conflictEdge);
1348 break;// exit iterator loop
1356 for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) {
1358 ConflictEdge edge = (ConflictEdge) iterator.next();
1359 if (seseLock.getConflictNodeSet().size() == 0) {
1361 if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
1362 // node has a coarse-grained edge with itself
1363 if (!(edge.getVertexU().isStallSiteNode())) {
1364 // and it is not parent
1365 type = ConflictNode.SCC;
1367 type = ConflictNode.PARENT_WRITE;
1369 seseLock.addConflictNode(edge.getVertexU(), type);
1371 if (edge.getVertexU().isStallSiteNode()) {
1372 if(edge.getVertexU().getWriteEffectSet().isEmpty()){
1373 type = ConflictNode.PARENT_READ;
1375 type = ConflictNode.PARENT_WRITE;
1378 type = ConflictNode.COARSE;
1380 seseLock.addConflictNode(edge.getVertexU(), type);
1382 if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
1383 // node has a coarse-grained edge with itself
1384 if (!(edge.getVertexV().isStallSiteNode())) {
1385 // and it is not parent
1386 type = ConflictNode.SCC;
1388 type = ConflictNode.PARENT_WRITE;
1390 seseLock.addConflictNode(edge.getVertexV(), type);
1392 if (edge.getVertexV().isStallSiteNode()) {
1393 if(edge.getVertexV().getWriteEffectSet().isEmpty()){
1394 type = ConflictNode.PARENT_READ;
1396 type = ConflictNode.PARENT_WRITE;
1399 type = ConflictNode.COARSE;
1401 seseLock.addConflictNode(edge.getVertexV(), type);
1404 coarseToCover.remove(edge);
1405 seseLock.addConflictEdge(edge);
1406 break;// exit iterator loop
1407 }// end of initial setup
1409 ConflictNode newNode;
1410 if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
1411 // new node has a coarse-grained edge to all fine-read, fine-write,
1415 if(newNode.isInVarNode() &&
1416 (!seseLock.hasSelfCoarseEdge(newNode)) &&
1417 seseLock.hasCoarseEdgeWithParentCoarse(newNode)){
1418 // this case can't be covered by this queue
1419 coarseToCover.remove(edge);
1423 if (seseLock.hasSelfCoarseEdge(newNode)) {
1425 if (newNode.isStallSiteNode()) {
1426 type = ConflictNode.PARENT_COARSE;
1428 type = ConflictNode.SCC;
1430 seseLock.setNodeType(newNode, type);
1432 if (newNode.isStallSiteNode()) {
1433 type = ConflictNode.PARENT_COARSE;
1435 type = ConflictNode.COARSE;
1437 seseLock.setNodeType(newNode, type);
1440 seseLock.addEdge(edge);
1441 Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
1442 for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
1443 ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
1444 // mark all coarse edges between new node and nodes in the group
1446 if (!conflictEdge.getVertexU().equals(newNode)) {
1447 if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
1449 seseLock.addConflictEdge(conflictEdge);
1450 coarseToCover.remove(conflictEdge);
1452 } else if (!conflictEdge.getVertexV().equals(newNode)) {
1453 if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
1455 seseLock.addConflictEdge(conflictEdge);
1456 coarseToCover.remove(conflictEdge);
1461 break;// exit iterator loop
1467 lockSet.add(seseLock);
1470 toCover.addAll(fineToCover);
1471 toCover.addAll(coarseToCover);
1475 conflictGraph2SESELock.put(conflictGraph, lockSet);
1478 public ConflictGraph getConflictGraph(FlatNode sese){
1479 return sese2conflictGraph.get(sese);
1482 public Set<SESELock> getLockMappings(ConflictGraph graph){
1483 return conflictGraph2SESELock.get(graph);
1486 public Set<FlatSESEEnterNode> getAllSESEs() {
1487 return rblockRel.getAllSESEs();
1490 public FlatSESEEnterNode getMainSESE() {
1491 return rblockRel.getMainSESE();
1494 public void writeReports( String timeReport ) throws java.io.IOException {
1496 BufferedWriter bw = new BufferedWriter( new FileWriter( "mlpReport_summary.txt" ) );
1497 bw.write( "MLP Analysis Results\n\n" );
1498 bw.write( timeReport+"\n\n" );
1499 printSESEHierarchy( bw );
1501 printSESEInfo( bw );
1504 Iterator<Descriptor> methItr = disjointAnalysisTaints.getDescriptorsToAnalyze().iterator();
1505 while( methItr.hasNext() ) {
1506 MethodDescriptor md = (MethodDescriptor) methItr.next();
1507 FlatMethod fm = state.getMethodFlat( md );
1510 new BufferedWriter(new FileWriter("mlpReport_" + md.getClassMethodName()
1511 + md.getSafeMethodDescriptor() + ".txt"));
1512 bw.write("MLP Results for " + md + "\n-------------------\n");
1514 FlatSESEEnterNode implicitSESE = (FlatSESEEnterNode) fm.getNext(0);
1515 if (!implicitSESE.getIsCallerSESEplaceholder() && implicitSESE != rblockRel.getMainSESE()) {
1516 System.out.println(implicitSESE + " is not implicit?!");
1519 bw.write("Dynamic vars to manage:\n " + implicitSESE.getDynamicVarSet());
1521 bw.write("\n\nLive-In, Root View\n------------------\n" + fm.printMethod(livenessRootView));
1522 bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults));
1523 bw.write("\n\nNot Available Results-Out\n---------------------\n"
1524 + fm.printMethod(notAvailableResults));
1525 bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans));
1531 private void printSESEHierarchy( BufferedWriter bw ) throws java.io.IOException {
1532 bw.write( "SESE Hierarchy\n--------------\n" );
1533 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getRootSESEs().iterator();
1534 while( rootItr.hasNext() ) {
1535 FlatSESEEnterNode root = rootItr.next();
1536 if( root.getIsCallerSESEplaceholder() ) {
1537 if( !root.getChildren().isEmpty() ) {
1538 printSESEHierarchyTree( bw, root, 0 );
1541 printSESEHierarchyTree( bw, root, 0 );
1546 private void printSESEHierarchyTree( BufferedWriter bw,
1547 FlatSESEEnterNode fsen,
1549 ) throws java.io.IOException {
1550 for( int i = 0; i < depth; ++i ) {
1553 bw.write( "- "+fsen.getPrettyIdentifier()+"\n" );
1555 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
1556 while( childItr.hasNext() ) {
1557 FlatSESEEnterNode fsenChild = childItr.next();
1558 printSESEHierarchyTree( bw, fsenChild, depth + 1 );
1563 private void printSESEInfo( BufferedWriter bw ) throws java.io.IOException {
1564 bw.write("\nSESE info\n-------------\n" );
1565 Iterator<FlatSESEEnterNode> rootItr = rblockRel.getRootSESEs().iterator();
1566 while( rootItr.hasNext() ) {
1567 FlatSESEEnterNode root = rootItr.next();
1568 if( root.getIsCallerSESEplaceholder() ) {
1569 if( !root.getChildren().isEmpty() ) {
1570 printSESEInfoTree( bw, root );
1573 printSESEInfoTree( bw, root );
1578 public DisjointAnalysis getDisjointAnalysis(){
1579 return disjointAnalysisReach;
1582 private void printSESEInfoTree( BufferedWriter bw,
1583 FlatSESEEnterNode fsen
1584 ) throws java.io.IOException {
1586 if( !fsen.getIsCallerSESEplaceholder() ) {
1587 bw.write( "SESE "+fsen.getPrettyIdentifier()+" {\n" );
1589 bw.write( " in-set: "+fsen.getInVarSet()+"\n" );
1590 Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
1591 while( tItr.hasNext() ) {
1592 TempDescriptor inVar = tItr.next();
1593 if( fsen.getReadyInVarSet().contains( inVar ) ) {
1594 bw.write( " (ready) "+inVar+"\n" );
1596 if( fsen.getStaticInVarSet().contains( inVar ) ) {
1597 bw.write( " (static) "+inVar+" from "+
1598 fsen.getStaticInVarSrc( inVar )+"\n" );
1600 if( fsen.getDynamicInVarSet().contains( inVar ) ) {
1601 bw.write( " (dynamic)"+inVar+"\n" );
1605 bw.write( " Dynamic vars to manage: "+fsen.getDynamicVarSet()+"\n");
1607 bw.write( " out-set: "+fsen.getOutVarSet()+"\n" );
1611 Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
1612 while( childItr.hasNext() ) {
1613 FlatSESEEnterNode fsenChild = childItr.next();
1614 printSESEInfoTree( bw, fsenChild );