X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FOoOJava%2FOoOJavaAnalysis.java;h=4a5283d57b4a1135d48e4184ff089b5d8089b28a;hp=aa0db186d5dd2c7ac2be3db21d2da8161545ad40;hb=4c0d447e6e01694c4bc2aaa7e9edcc6c8d22f109;hpb=6bd44ebe9bdaf3982470ad744f4bf6a356639cce diff --git a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java index aa0db186..4a5283d5 100644 --- a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java +++ b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java @@ -1,49 +1,15 @@ package Analysis.OoOJava; -import java.io.BufferedWriter; -import java.io.FileWriter; -import java.io.IOException; -import java.util.Enumeration; -import java.util.HashSet; -import java.util.Hashtable; -import java.util.Iterator; -import java.util.Map; -import java.util.Set; -import java.util.Stack; -import java.util.Map.Entry; - -import Analysis.ArrayReferencees; -import Analysis.Liveness; -import Analysis.CallGraph.CallGraph; -import Analysis.Disjoint.DisjointAnalysis; -import Analysis.Disjoint.Effect; -import Analysis.Disjoint.EffectsAnalysis; -import Analysis.Disjoint.Taint; -import Analysis.MLP.CodePlan; -import Analysis.MLP.SESEandAgePair; -import Analysis.MLP.VSTWrapper; -import Analysis.MLP.VarSrcTokTable; -import Analysis.MLP.VariableSourceToken; -import IR.Descriptor; -import IR.MethodDescriptor; -import IR.Operation; -import IR.State; -import IR.TypeUtil; -import IR.Flat.FKind; -import IR.Flat.FlatCall; -import IR.Flat.FlatEdge; -import IR.Flat.FlatElementNode; -import IR.Flat.FlatFieldNode; -import IR.Flat.FlatMethod; -import IR.Flat.FlatNew; -import IR.Flat.FlatNode; -import IR.Flat.FlatOpNode; -import IR.Flat.FlatSESEEnterNode; -import IR.Flat.FlatSESEExitNode; -import IR.Flat.FlatSetElementNode; -import IR.Flat.FlatSetFieldNode; -import IR.Flat.FlatWriteDynamicVarNode; -import IR.Flat.TempDescriptor; +import java.io.*; +import java.util.*; + +import Analysis.*; +import Analysis.CallGraph.*; +import Analysis.Disjoint.*; +import Analysis.Pointer.*; +import Util.*; +import IR.*; +import IR.Flat.*; public class OoOJavaAnalysis { @@ -51,12 +17,15 @@ public class OoOJavaAnalysis { private State state; private TypeUtil typeUtil; private CallGraph callGraph; + private Liveness liveness; private RBlockRelationAnalysis rblockRel; - private RBlockStatusAnalysis rblockStatus; - private DisjointAnalysis disjointAnalysisTaints; + private HeapAnalysis disjointAnalysisTaints; private DisjointAnalysis disjointAnalysisReach; + private BuildStateMachines buildStateMachines; + + private Set descriptorsToAnalyze; - private Hashtable> livenessRootView; + private Hashtable> livenessGlobalView; private Hashtable> livenessVirtualReads; private Hashtable variableResults; private Hashtable> notAvailableResults; @@ -66,8 +35,13 @@ public class OoOJavaAnalysis { private Hashtable wdvNodesToSpliceIn; - // temporal data structures to track analysis progress. - static private int uniqueLockSetId = 0; + private Hashtable fn2contextTaskNames; + + // get the flat method that contains any given flat node + private Hashtable fn2fm; + + // temporal data structures to track analysis progress. + static private int uniqueLockSetId = 0; // mapping of a conflict graph to its compiled lock private Hashtable> conflictGraph2SESELock; // mapping of a sese block to its conflict graph @@ -85,237 +59,316 @@ public class OoOJavaAnalysis { return cp; } - public OoOJavaAnalysis(State state, TypeUtil typeUtil, CallGraph callGraph, Liveness liveness, - ArrayReferencees arrayReferencees) { + public Set getNodesWithPlans() { + return codePlans.keySet(); + } + + public ContextTaskNames getContextTaskNames(FlatMethod fm) { + ContextTaskNames out = fn2contextTaskNames.get(fm); + if (out == null) { + out = new ContextTaskNames(); + } + return out; + } + + public ContextTaskNames getContextTaskNames(FlatSESEEnterNode fsen) { + ContextTaskNames out = fn2contextTaskNames.get(fsen); + if (out == null) { + out = new ContextTaskNames(); + } + return out; + } - double timeStartAnalysis = (double) System.nanoTime(); + public FlatMethod getContainingFlatMethod(FlatNode fn) { + FlatMethod fm = fn2fm.get(fn); + assert fm != null; + return fm; + } + + public HeapAnalysis getHeapAnalysis() { + return disjointAnalysisTaints; + } + + public BuildStateMachines getBuildStateMachines() { + return buildStateMachines; + } + + public OoOJavaAnalysis(State state, TypeUtil typeUtil, CallGraph callGraph, Liveness liveness, + ArrayReferencees arrayReferencees) { + State.logEvent("Starting OoOJavaAnalysis"); this.state = state; this.typeUtil = typeUtil; this.callGraph = callGraph; - this.maxSESEage = state.MLP_MAXSESEAGE; + this.liveness = liveness; + this.maxSESEage = state.OOO_MAXSESEAGE; - livenessRootView = new Hashtable>(); + livenessGlobalView = new Hashtable>(); livenessVirtualReads = new Hashtable>(); variableResults = new Hashtable(); notAvailableResults = new Hashtable>(); codePlans = new Hashtable(); wdvNodesToSpliceIn = new Hashtable(); - notAvailableIntoSESE = new Hashtable>(); - sese2conflictGraph = new Hashtable(); conflictGraph2SESELock = new Hashtable>(); + fn2contextTaskNames = new Hashtable(); + fn2fm = new Hashtable(); + + // state machines support heap examiners with + // state transitions to improve precision + if (state.RCR) { + buildStateMachines = new BuildStateMachines(); + } // add all methods transitively reachable from the // source's main to set for analysis MethodDescriptor mdSourceEntry = typeUtil.getMain(); FlatMethod fmMain = state.getMethodFlat(mdSourceEntry); - Set descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry); + descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry); descriptorsToAnalyze.add(mdSourceEntry); - - // 1st pass, find basic rblock relations & status + // 0th pass, setup a useful mapping of any flat node to the + // flat method it is a part of + Iterator methItr = descriptorsToAnalyze.iterator(); + while (methItr.hasNext()) { + Descriptor d = methItr.next(); + FlatMethod fm = state.getMethodFlat(d); + buildFlatNodeToFlatMethod(fm); + } + State.logEvent("OoOJavaAnalysis Oth pass completed"); + + // 1st pass, find basic rblock relations & potential stall sites rblockRel = new RBlockRelationAnalysis(state, typeUtil, callGraph); - rblockStatus = new RBlockStatusAnalysis(state, typeUtil, callGraph, rblockRel); + VarSrcTokTable.rblockRel = rblockRel; + State.logEvent("OoOJavaAnalysis 1st pass completed"); // 2nd pass, liveness, in-set out-set (no virtual reads yet!) - Iterator rootItr = rblockRel.getRootSESEs().iterator(); - while (rootItr.hasNext()) { - FlatSESEEnterNode root = rootItr.next(); - livenessAnalysisBackward(root, true, null); - } + // run liveness analysis for each sese blocks + Iterator seseItr = rblockRel.getAllSESEs().iterator(); + while (seseItr.hasNext()) { + FlatSESEEnterNode sese = seseItr.next(); + livenessAnalysisBackward(sese); + } + + State.logEvent("OoOJavaAnalysis 2nd pass completed"); // 3rd pass, variable analysis - Iterator methItr = descriptorsToAnalyze.iterator(); + methItr = rblockRel.getMethodsWithSESEs().iterator(); while (methItr.hasNext()) { Descriptor d = methItr.next(); FlatMethod fm = state.getMethodFlat(d); - // starting from roots do a forward, fixed-point // variable analysis for refinement and stalls variableAnalysisForward(fm); } + State.logEvent("OoOJavaAnalysis 3rd pass completed"); + // 4th pass, compute liveness contribution from // virtual reads discovered in variable pass - rootItr = rblockRel.getRootSESEs().iterator(); - while (rootItr.hasNext()) { - FlatSESEEnterNode root = rootItr.next(); - livenessAnalysisBackward(root, true, null); + seseItr = rblockRel.getLocalRootSESEs().iterator(); + while (seseItr.hasNext()) { + FlatSESEEnterNode sese = seseItr.next(); + livenessAnalysisBackward(sese); } + State.logEvent("OoOJavaAnalysis 4th pass completed"); + // 5th pass, use disjointness with NO FLAGGED REGIONS // to compute taints and effects - disjointAnalysisTaints = - new DisjointAnalysis(state, - typeUtil, - callGraph, - liveness, - arrayReferencees, - null, // no FlatNew set to flag - rblockRel, - rblockStatus - ); - + if (state.POINTER) { + disjointAnalysisTaints = + new Pointer(state, typeUtil, callGraph, rblockRel, liveness, buildStateMachines); + ((Pointer) disjointAnalysisTaints).doAnalysis(); + } else { + disjointAnalysisTaints = + new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, null, + rblockRel, buildStateMachines, + !state.OOODEBUG // only print out in OoOJava debug mode + ); + } + State.logEvent("OoOJavaAnalysis 5th pass completed"); + // 6th pass, not available analysis FOR VARIABLES! - methItr = descriptorsToAnalyze.iterator(); + methItr = rblockRel.getMethodsWithSESEs().iterator(); while (methItr.hasNext()) { Descriptor d = methItr.next(); FlatMethod fm = state.getMethodFlat(d); - // compute what is not available at every program // point, in a forward fixed-point pass notAvailableForward(fm); } - - // 7th pass, make conflict graph - // conflict graph is maintained by each parent sese, - Iterator descItr=disjointAnalysisTaints.getDescriptorsToAnalyze().iterator(); - while (descItr.hasNext()) { - Descriptor d = (Descriptor)descItr.next(); - FlatMethod fm = state.getMethodFlat(d); - if(fm != null) - makeConflictGraph(fm); + State.logEvent("OoOJavaAnalysis 6th pass completed"); + // 7th pass, start conflict graphs where a parent's graph has a + // node for possibly conflicting children and its own stall sites + startConflictGraphs(); + State.logEvent("OoOJavaAnalysis 7th pass completed"); + // 8th pass, calculate all possible conflicts without using + // reachability info and identify set of FlatNew that next + // disjoint reach. analysis should flag + Set sitesToFlag = new HashSet(); + calculateConflicts(sitesToFlag, false); + State.logEvent("OoOJavaAnalysis 8th pass completed"); + if (!state.RCR) { + // 9th pass, ask disjoint analysis to compute reachability + // for objects that may cause heap conflicts so the most + // efficient method to deal with conflict can be computed + // later + disjointAnalysisReach = + new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, sitesToFlag, + null, // don't do effects analysis again! + null, // no BuildStateMachines needed + !state.OOODEBUG // only print out in OoOJava debug mode + ); + State.logEvent("OoOJavaAnalysis 9th pass completed"); + // 10th pass, calculate conflicts with reachability info + calculateConflicts(null, true); + State.logEvent("OoOJavaAnalysis 10th pass completed"); + } else { + // in RCR/DFJ we want to do some extra processing on the + // state machines before they get handed off to code gen, + // and we're doing the same effect-conflict traversal needed + // to identify heap examiners that are weakly connected, so + // accomplish both at the same time + pruneMachinesAndFindWeaklyConnectedExaminers(); + State.logEvent("OoOJavaAnalysis RCR pruneMachines pass completed"); } - // debug routine - /* - Iterator iter = sese2conflictGraph.entrySet().iterator(); - while (iter.hasNext()) { - Entry e = (Entry) iter.next(); - FlatNode fn = (FlatNode) e.getKey(); - ConflictGraph conflictGraph = (ConflictGraph) e.getValue(); - System.out.println("---------------------------------------"); - System.out.println("CONFLICT GRAPH for " + fn); - Set keySet = conflictGraph.id2cn.keySet(); - for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { - String key = (String) iterator.next(); - ConflictNode node = conflictGraph.id2cn.get(key); - System.out.println("key=" + key + " \n" + node.toStringAllEffects()); - } - } - */ - - // 8th pass, calculate all possible conflicts without using reachability info - // and identify set of FlatNew that next disjoint reach. analysis should flag - Set sitesToFlag = new HashSet(); - calculateConflicts(sitesToFlag,false); - - // 9th pass, ask disjoint analysis to compute reachability - // for objects that may cause heap conflicts so the most - // efficient method to deal with conflict can be computed - // later - - disjointAnalysisReach = - new DisjointAnalysis(state, - typeUtil, - callGraph, - liveness, - arrayReferencees, - sitesToFlag, - null, // don't do effects analysis again! - null // don't do effects analysis again! - ); - // 10th pass, calculate conflicts with reachability info - calculateConflicts(null, true); - - // 11th pass, compiling locks + // 11th pass, compiling memory Qs! The name "lock" is a legacy + // term for the heap dependence queue, or memQ as the runtime calls it synthesizeLocks(); - + State.logEvent("OoOJavaAnalysis 11th pass completed"); + // 12th pass, compute a plan for code injections - methItr =descriptorsToAnalyze.iterator(); - while( methItr.hasNext() ) { - Descriptor d = methItr.next(); - FlatMethod fm = state.getMethodFlat( d ); - codePlansForward( fm ); + methItr = descriptorsToAnalyze.iterator(); + while (methItr.hasNext()) { + Descriptor d = methItr.next(); + FlatMethod fm = state.getMethodFlat(d); + codePlansForward(fm); } - + + State.logEvent("OoOJavaAnalysis 12th pass completed"); // 13th pass, // splice new IR nodes into graph after all // analysis passes are complete Iterator spliceItr = wdvNodesToSpliceIn.entrySet().iterator(); - while( spliceItr.hasNext() ) { - Map.Entry me = (Map.Entry) spliceItr.next(); + while (spliceItr.hasNext()) { + Map.Entry me = (Map.Entry)spliceItr.next(); FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue(); fwdvn.spliceIntoIR(); } - - - if( state.OOODEBUG ) { + State.logEvent("OoOJavaAnalysis 13th pass completed"); + + if (state.OOODEBUG) { try { - writeReports( "" ); - disjointAnalysisTaints.getEffectsAnalysis().writeEffects( "effects.txt" ); + writeReports(""); + disjointAnalysisTaints.getEffectsAnalysis().writeEffects("effects.txt"); writeConflictGraph(); - } catch( IOException e ) {} - } - - } - - private void writeFile(Set sitesToFlag){ - - try{ - BufferedWriter bw = new BufferedWriter( new FileWriter( "sitesToFlag.txt" ) ); - - for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext();) { - FlatNew fn = (FlatNew) iterator.next(); - bw.write( fn+"\n" ); - } - bw.close(); - }catch(IOException e){ - + } catch (IOException e) { + } } - + State.logEvent("OoOJavaAnalysis completed"); } - private void livenessAnalysisBackward(FlatSESEEnterNode fsen, boolean toplevel, - Hashtable> liveout) { - - // start from an SESE exit, visit nodes in reverse up to - // SESE enter in a fixed-point scheme, where children SESEs - // should already be analyzed and therefore can be skipped - // because child SESE enter node has all necessary info + private void buildFlatNodeToFlatMethod(FlatMethod fm) { Set flatNodesToVisit = new HashSet(); + flatNodesToVisit.add(fm); - if (toplevel) { - flatNodesToVisit.add(fsen.getfmEnclosing().getFlatExit()); - } else { - flatNodesToVisit.add(fsen.getFlatExit()); + Set flatNodesVisited = new HashSet(); + + while (!flatNodesToVisit.isEmpty()) { + FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); + flatNodesToVisit.remove(fn); + flatNodesVisited.add(fn); + + fn2fm.put(fn, fm); + + for (int i = 0; i < fn.numNext(); i++) { + FlatNode nn = fn.getNext(i); + if (!flatNodesVisited.contains(nn)) { + flatNodesToVisit.add(nn); + } + } } + } - Hashtable> livenessResults = new Hashtable>(); + // debug routine + /* + * Iterator iter = sese2conflictGraph.entrySet().iterator(); while + * (iter.hasNext()) { Entry e = (Entry) iter.next(); FlatNode fn = (FlatNode) + * e.getKey(); ConflictGraph conflictGraph = (ConflictGraph) e.getValue(); + * System.out.println("---------------------------------------"); + * System.out.println("CONFLICT GRAPH for " + fn); Set keySet = + * conflictGraph.id2cn.keySet(); for (Iterator iterator = keySet.iterator(); + * iterator.hasNext();) { String key = (String) iterator.next(); ConflictNode + * node = conflictGraph.id2cn.get(key); System.out.println("key=" + key + + * " \n" + node.toStringAllEffects()); } } + */ + + private void writeFile(Set sitesToFlag) { + + try { + BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt")); + + for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext(); ) { + FlatNew fn = (FlatNew) iterator.next(); + bw.write(fn + "\n"); + } + bw.close(); + } catch (IOException e) { - if (toplevel) { - liveout = new Hashtable>(); } + } + + + private void livenessAnalysisBackward(FlatSESEEnterNode fsen) { + + // each task maintains a local liveness result + Hashtable> livenessLocalView = + new Hashtable>(); + + // flow backward across nodes to compute liveness. + // it contributes liveness results to the global view + // only if the current flat node belongs directly to the currently analyzing + // sese. + Set flatNodesToVisit = new HashSet(); + flatNodesToVisit.add(fsen.getFlatExit()); + while (!flatNodesToVisit.isEmpty()) { FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); flatNodesToVisit.remove(fn); - Set prev = livenessResults.get(fn); + Set prev = livenessLocalView.get(fn); // merge sets from control flow joins - Set u = new HashSet(); + Set livein = new HashSet(); for (int i = 0; i < fn.numNext(); i++) { FlatNode nn = fn.getNext(i); - Set s = livenessResults.get(nn); + Set s = livenessLocalView.get(nn); if (s != null) { - u.addAll(s); + livein.addAll(s); } } - Set curr = liveness_nodeActions(fn, u, fsen, toplevel, liveout); + Set curr = liveness_nodeActions(fsen, fn, livein); // if a new result, schedule backward nodes for analysis if (!curr.equals(prev)) { - livenessResults.put(fn, curr); - // don't flow backwards past current SESE enter - if (!fn.equals(fsen)) { + if (fn != fsen) { + livenessLocalView.put(fn, curr); + + if (rblockRel.getLocalInnerRBlock(fn).equals(fsen)) { + // the current flat node belongs to the currently analyzing sese + // store its liveness in the gloval view + livenessGlobalView.put(fn, curr); + } + for (int i = 0; i < fn.numPrev(); i++) { FlatNode nn = fn.getPrev(i); flatNodesToVisit.add(nn); @@ -323,40 +376,24 @@ public class OoOJavaAnalysis { } } } - - Set s = livenessResults.get(fsen); - if (s != null) { - fsen.addInVarSet(s); - } - - // remember liveness per node from the root view as the - // global liveness of variables for later passes to use - if (toplevel) { - livenessRootView.putAll(livenessResults); - } - - // post-order traversal, so do children first - Iterator childItr = fsen.getChildren().iterator(); - while (childItr.hasNext()) { - FlatSESEEnterNode fsenChild = childItr.next(); - livenessAnalysisBackward(fsenChild, false, liveout); - } } - private Set liveness_nodeActions(FlatNode fn, Set liveIn, - FlatSESEEnterNode currentSESE, boolean toplevel, - Hashtable> liveout) { + private Set liveness_nodeActions(FlatSESEEnterNode currSESE, FlatNode fn, + Set liveIn) { + switch (fn.kind()) { - case FKind.FlatSESEExitNode: - if (toplevel) { - FlatSESEExitNode fsexn = (FlatSESEExitNode) fn; - if (!liveout.containsKey(fsexn)) { - liveout.put(fsexn, new HashSet()); + case FKind.FlatSESEEnterNode: { + // add whatever is live-in at a task enter to that + // task's in-var set + FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn; + if (currSESE.equals(fsen)) { + if (liveIn != null) { + fsen.addInVarSet(liveIn); } - liveout.get(fsexn).addAll(liveIn); + // no break, should also execute default actions } - // no break, sese exits should also execute default actions + } default: { // handle effects of statement in reverse, writes then reads @@ -364,13 +401,17 @@ public class OoOJavaAnalysis { for (int i = 0; i < writeTemps.length; ++i) { liveIn.remove(writeTemps[i]); - if (!toplevel) { - FlatSESEExitNode fsexn = currentSESE.getFlatExit(); - Set livetemps = liveout.get(fsexn); + // if we are analyzing code declared directly in a task, + FlatSESEEnterNode fsen = rblockRel.getLocalInnerRBlock(fn); + if (fsen != null) { + // check to see if we are writing to variables that will + // be live-out at the task's exit (and therefore should + // go in the task's out-var set) + FlatSESEExitNode fsexn = fsen.getFlatExit(); + // note: liveness analysis can have corresponding decisions + Set livetemps = liveness.getLiveInTemps(fsen.getfmEnclosing(), fsexn); if (livetemps != null && livetemps.contains(writeTemps[i])) { - // write to a live out temp... - // need to put in SESE liveout set - currentSESE.addOutVar(writeTemps[i]); + fsen.addOutVar(writeTemps[i]); } } } @@ -384,7 +425,6 @@ public class OoOJavaAnalysis { if (virtualReadTemps != null) { liveIn.addAll(virtualReadTemps); } - } break; @@ -402,9 +442,6 @@ public class OoOJavaAnalysis { FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); flatNodesToVisit.remove(fn); - Stack seseStack = rblockRel.getRBlockStacks(fm, fn); - assert seseStack != null; - VarSrcTokTable prev = variableResults.get(fn); // merge sets from control flow joins @@ -415,10 +452,13 @@ public class OoOJavaAnalysis { curr.merge(incoming); } - if (!seseStack.empty()) { - variable_nodeActions(fn, curr, seseStack.peek()); + FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock(fn); + if (currentSESE == null) { + currentSESE = rblockRel.getCallerProxySESE(); } + variable_nodeActions(fn, curr, currentSESE); + // if a new result, schedule forward nodes for analysis if (!curr.equals(prev)) { variableResults.put(fn, curr); @@ -432,22 +472,24 @@ public class OoOJavaAnalysis { } private void variable_nodeActions(FlatNode fn, VarSrcTokTable vstTable, - FlatSESEEnterNode currentSESE) { + FlatSESEEnterNode currentSESE) { switch (fn.kind()) { case FKind.FlatSESEEnterNode: { FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn; - assert fsen.equals(currentSESE); - - vstTable.age(currentSESE); + // ignore currently executing SESE, at this point + // the analysis considers a new instance is becoming + // the current SESE + vstTable.age(fsen); vstTable.assertConsistency(); } - break; + break; case FKind.FlatSESEExitNode: { FlatSESEExitNode fsexn = (FlatSESEExitNode) fn; + + // fsen is the child of currently executing tasks FlatSESEEnterNode fsen = fsexn.getFlatEnter(); - assert currentSESE.getChildren().contains(fsen); // remap all of this child's children tokens to be // from this child as the child exits @@ -457,15 +499,21 @@ public class OoOJavaAnalysis { // written by an SESE and should be added to the in-set // anything virtually read by this SESE should be pruned // of parent or sibling sources - Set liveVars = livenessRootView.get(fn); - Set fsenVirtReads = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens( - fsen, liveVars); + // Set liveVars = liveness.getLiveInTemps(fsen.getfmEnclosing(), fn); + Set liveVars = livenessGlobalView.get(fn); + + Set fsenVirtReads = + vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen, liveVars); + Set fsenVirtReadsOld = livenessVirtualReads.get(fn); if (fsenVirtReadsOld != null) { fsenVirtReads.addAll(fsenVirtReadsOld); } livenessVirtualReads.put(fn, fsenVirtReads); + // virtual reads are forced in-vars! + fsen.addInVarSet(fsenVirtReads); + // then all child out-set tokens are guaranteed // to be filled in, so clobber those entries with // the latest, clean sources @@ -479,9 +527,8 @@ public class OoOJavaAnalysis { vstTable.add(vst); } vstTable.assertConsistency(); - } - break; + break; case FKind.FlatOpNode: { FlatOpNode fon = (FlatOpNode) fn; @@ -501,10 +548,21 @@ public class OoOJavaAnalysis { HashSet ts = new HashSet(); ts.add(lhs); - if (currentSESE.getChildren().contains(vst.getSESE())) { + // when we do x = y for variables, just copy over from a child, + // there are two cases: + // 1. if the current task is the caller proxy, any local root is a + // child + boolean case1 = + currentSESE.getIsCallerProxySESE() + && rblockRel.getLocalRootSESEs().contains(vst.getSESE()); + + // 2. if the child task is a locally-defined child of the current task + boolean case2 = currentSESE.getLocalChildren().contains(vst.getSESE()); + + if (case1 || case2) { // if the source comes from a child, copy it over forAddition.add(new VariableSourceToken(ts, vst.getSESE(), vst.getAge(), vst - .getAddrVar())); + .getAddrVar())); } else { // otherwise, stamp it as us as the source forAddition.add(new VariableSourceToken(ts, currentSESE, new Integer(0), lhs)); @@ -520,8 +578,8 @@ public class OoOJavaAnalysis { } } - // note that FlatOpNode's that aren't ASSIGN - // fall through to this default case + // note that FlatOpNode's that aren't ASSIGN + // fall through to this default case default: { TempDescriptor[] writeTemps = fn.writesTemps(); if (writeTemps.length > 0) { @@ -529,7 +587,6 @@ public class OoOJavaAnalysis { // for now, when writeTemps > 1, make sure // its a call node, programmer enforce only // doing stuff like calling a print routine - // assert writeTemps.length == 1; if (writeTemps.length > 1) { assert fn.kind() == FKind.FlatCall || fn.kind() == FKind.FlatMethod; break; @@ -545,7 +602,7 @@ public class OoOJavaAnalysis { vstTable.assertConsistency(); } - break; + break; } // end switch } @@ -559,9 +616,6 @@ public class OoOJavaAnalysis { FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); flatNodesToVisit.remove(fn); - Stack seseStack = rblockRel.getRBlockStacks(fm, fn); - assert seseStack != null; - Set prev = notAvailableResults.get(fn); Set curr = new HashSet(); @@ -573,10 +627,13 @@ public class OoOJavaAnalysis { } } - if (!seseStack.empty()) { - notAvailable_nodeActions(fn, curr, seseStack.peek()); + FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock(fn); + if (currentSESE == null) { + currentSESE = rblockRel.getCallerProxySESE(); } + notAvailable_nodeActions(fn, curr, currentSESE); + // if a new result, schedule forward nodes for analysis if (!curr.equals(prev)) { notAvailableResults.put(fn, curr); @@ -590,7 +647,7 @@ public class OoOJavaAnalysis { } private void notAvailable_nodeActions(FlatNode fn, Set notAvailSet, - FlatSESEEnterNode currentSESE) { + FlatSESEEnterNode currentSESE) { // any temps that are removed from the not available set // at this node should be marked in this node's code plan @@ -600,7 +657,6 @@ public class OoOJavaAnalysis { case FKind.FlatSESEEnterNode: { FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn; - assert fsen.equals(currentSESE); // keep a copy of what's not available into the SESE // and restore it at the matching exit node @@ -613,25 +669,24 @@ public class OoOJavaAnalysis { notAvailSet.clear(); } - break; + break; case FKind.FlatSESEExitNode: { FlatSESEExitNode fsexn = (FlatSESEExitNode) fn; FlatSESEEnterNode fsen = fsexn.getFlatEnter(); - assert currentSESE.getChildren().contains(fsen); notAvailSet.addAll(fsen.getOutVarSet()); Set notAvailIn = notAvailableIntoSESE.get(fsen); assert notAvailIn != null; notAvailSet.addAll(notAvailIn); - } - break; + break; case FKind.FlatMethod: { notAvailSet.clear(); } + break; case FKind.FlatOpNode: { FlatOpNode fon = (FlatOpNode) fn; @@ -653,8 +708,8 @@ public class OoOJavaAnalysis { } } - // note that FlatOpNode's that aren't ASSIGN - // fall through to this default case + // note that FlatOpNode's that aren't ASSIGN + // fall through to this default case default: { TempDescriptor[] writeTemps = fn.writesTemps(); for (int i = 0; i < writeTemps.length; i++) { @@ -677,8 +732,8 @@ public class OoOJavaAnalysis { VariableSourceToken vst = vstIfStatic.vst; - Iterator availItr = vstTable.get(vst.getSESE(), vst.getAge()) - .iterator(); + Iterator availItr = + vstTable.get(vst.getSESE(), vst.getAge()).iterator(); // look through things that are also available from same source while (availItr.hasNext()) { @@ -691,8 +746,8 @@ public class OoOJavaAnalysis { // if a variable is available from the same source, AND it ALSO // only comes from one statically known source, mark it available VSTWrapper vstIfStaticNotUsed = new VSTWrapper(); - Integer srcTypeAlso = vstTable.getRefVarSrcType(refVarAlso, currentSESE, - vstIfStaticNotUsed); + Integer srcTypeAlso = + vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed); if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) { notAvailSet.remove(refVarAlso); } @@ -701,90 +756,80 @@ public class OoOJavaAnalysis { } } } - break; + break; } // end switch } - -private void codePlansForward( FlatMethod fm ) { - + private void codePlansForward(FlatMethod fm) { + // start from flat method top, visit every node in // method exactly once Set flatNodesToVisit = new HashSet(); - flatNodesToVisit.add( fm ); + flatNodesToVisit.add(fm); - Set visited = new HashSet(); + Set visited = new HashSet(); - while( !flatNodesToVisit.isEmpty() ) { + while (!flatNodesToVisit.isEmpty()) { Iterator fnItr = flatNodesToVisit.iterator(); FlatNode fn = fnItr.next(); - flatNodesToVisit.remove( fn ); - visited.add( fn ); - - Stack seseStack = rblockRel.getRBlockStacks(fm, fn); - assert seseStack != null; + flatNodesToVisit.remove(fn); + visited.add(fn); // use incoming results as "dot statement" or just // before the current statement VarSrcTokTable dotSTtable = new VarSrcTokTable(); - for( int i = 0; i < fn.numPrev(); i++ ) { - FlatNode nn = fn.getPrev( i ); - dotSTtable.merge( variableResults.get( nn ) ); + for (int i = 0; i < fn.numPrev(); i++) { + FlatNode nn = fn.getPrev(i); + dotSTtable.merge(variableResults.get(nn)); } // find dt-st notAvailableSet also - Set dotSTnotAvailSet = new HashSet(); - for( int i = 0; i < fn.numPrev(); i++ ) { - FlatNode nn = fn.getPrev( i ); - Set notAvailIn = notAvailableResults.get( nn ); - if( notAvailIn != null ) { - dotSTnotAvailSet.addAll( notAvailIn ); + Set dotSTnotAvailSet = new HashSet(); + for (int i = 0; i < fn.numPrev(); i++) { + FlatNode nn = fn.getPrev(i); + Set notAvailIn = notAvailableResults.get(nn); + if (notAvailIn != null) { + dotSTnotAvailSet.addAll(notAvailIn); } } - Set dotSTlive = livenessRootView.get( fn ); + Set dotSTlive = livenessGlobalView.get(fn); - if( !seseStack.empty() ) { - codePlans_nodeActions( fn, - dotSTlive, - dotSTtable, - dotSTnotAvailSet, - seseStack.peek() - ); + FlatSESEEnterNode currentSESE = rblockRel.getLocalInnerRBlock(fn); + if (currentSESE == null) { + currentSESE = rblockRel.getCallerProxySESE(); } - for( int i = 0; i < fn.numNext(); i++ ) { - FlatNode nn = fn.getNext( i ); + codePlans_nodeActions(fm, fn, dotSTtable, dotSTnotAvailSet, currentSESE); - if( !visited.contains( nn ) ) { - flatNodesToVisit.add( nn ); - } + for (int i = 0; i < fn.numNext(); i++) { + FlatNode nn = fn.getNext(i); + + if (!visited.contains(nn)) { + flatNodesToVisit.add(nn); + } } } } - private void codePlans_nodeActions( FlatNode fn, - Set liveSetIn, - VarSrcTokTable vstTableIn, - Set notAvailSetIn, - FlatSESEEnterNode currentSESE ) { - - CodePlan plan = new CodePlan( currentSESE); + private void codePlans_nodeActions(FlatMethod fm, FlatNode fn, VarSrcTokTable vstTableIn, + Set notAvailSetIn, FlatSESEEnterNode currentSESE) { + + CodePlan plan = new CodePlan(currentSESE); - switch( fn.kind() ) { + switch (fn.kind()) { case FKind.FlatSESEEnterNode: { FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn; - assert fsen.equals( currentSESE ); // track the source types of the in-var set so generated // code at this SESE issue can compute the number of // dependencies properly Iterator inVarItr = fsen.getInVarSet().iterator(); - while( inVarItr.hasNext() ) { - TempDescriptor inVar = inVarItr.next(); + while (inVarItr.hasNext()) { + TempDescriptor inVar = inVarItr.next(); // when we get to an SESE enter node we change the // currentSESE variable of this analysis to the @@ -792,232 +837,364 @@ private void codePlansForward( FlatMethod fm ) { // in order to classify in-vars correctly, pass // the parent SESE in--at other FlatNode types just // use the currentSESE + FlatSESEEnterNode parent = rblockRel.getLocalInnerRBlock(fn); + if (parent == null) { + parent = rblockRel.getCallerProxySESE(); + } + VSTWrapper vstIfStatic = new VSTWrapper(); - Integer srcType = - vstTableIn.getRefVarSrcType( inVar, - fsen.getParent(), - vstIfStatic - ); - - // the current SESE needs a local space to track the dynamic - // variable and the child needs space in its SESE record - if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) { - fsen.addDynamicInVar( inVar ); - fsen.getParent().addDynamicVar( inVar ); - - } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) { - fsen.addStaticInVar( inVar ); - VariableSourceToken vst = vstIfStatic.vst; - fsen.putStaticInVar2src( inVar, vst ); - fsen.addStaticInVarSrc( new SESEandAgePair( vst.getSESE(), - vst.getAge() - ) - ); - } else { - assert srcType.equals( VarSrcTokTable.SrcType_READY ); - fsen.addReadyInVar( inVar ); - } - } + Integer srcType = vstTableIn.getRefVarSrcType(inVar, parent, vstIfStatic); + + // the current SESE needs a local space to track the dynamic + // variable and the child needs space in its SESE record + if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) { + fsen.addDynamicInVar(inVar); + addDynamicVar(parent, fm, inVar); - } break; + } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) { + fsen.addStaticInVar(inVar); + VariableSourceToken vst = vstIfStatic.vst; + fsen.putStaticInVar2src(inVar, vst); + fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge())); + + } else { + assert srcType.equals(VarSrcTokTable.SrcType_READY); + fsen.addReadyInVar(inVar); + } + } + } + break; case FKind.FlatSESEExitNode: { FlatSESEExitNode fsexn = (FlatSESEExitNode) fn; - } break; + + // Classify the sources of out-set variables so code + // gen can acquire them from children if necessary + // before this task exits + FlatSESEEnterNode exiter = fsexn.getFlatEnter(); + + Iterator outVarItr = exiter.getOutVarSet().iterator(); + while (outVarItr.hasNext()) { + TempDescriptor outVar = outVarItr.next(); + + VSTWrapper vstIfStatic = new VSTWrapper(); + Integer srcType = vstTableIn.getRefVarSrcType(outVar, exiter, vstIfStatic); + + if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) { + // if the out-var is dynamic, put it in the set of dyn out vars + // so exiting code gen knows to look for the value, but also put + // it in the set of dynamic vars the exiter must track! + exiter.addDynamicOutVar(outVar); + addDynamicVar(exiter, fm, outVar); + + } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) { + exiter.addStaticOutVar(outVar); + VariableSourceToken vst = vstIfStatic.vst; + exiter.putStaticOutVar2src(outVar, vst); + exiter.addStaticOutVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge())); + + } else { + assert srcType.equals(VarSrcTokTable.SrcType_READY); + exiter.addReadyOutVar(outVar); + } + } + } + break; case FKind.FlatOpNode: { FlatOpNode fon = (FlatOpNode) fn; - if( fon.getOp().getOp() == Operation.ASSIGN ) { - TempDescriptor lhs = fon.getDest(); - TempDescriptor rhs = fon.getLeft(); + if (fon.getOp().getOp() == Operation.ASSIGN) { + TempDescriptor lhs = fon.getDest(); + TempDescriptor rhs = fon.getLeft(); - // if this is an op node, don't stall, copy - // source and delay until we need to use value + // if this is an op node, don't stall, copy + // source and delay until we need to use value - // ask whether lhs and rhs sources are dynamic, static, etc. + // ask whether lhs and rhs sources are dynamic, static, etc. VSTWrapper vstIfStatic = new VSTWrapper(); - Integer lhsSrcType - = vstTableIn.getRefVarSrcType( lhs, - currentSESE, - vstIfStatic - ); - Integer rhsSrcType - = vstTableIn.getRefVarSrcType( rhs, - currentSESE, - vstIfStatic - ); - - if( rhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) { - // if rhs is dynamic going in, lhs will definitely be dynamic - // going out of this node, so track that here - plan.addDynAssign( lhs, rhs ); - currentSESE.addDynamicVar( lhs ); - currentSESE.addDynamicVar( rhs ); - - } else if( lhsSrcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) { - // otherwise, if the lhs is dynamic, but the rhs is not, we - // need to update the variable's dynamic source as "current SESE" - plan.addDynAssign( lhs ); - } - - // only break if this is an ASSIGN op node, - // otherwise fall through to default case - break; + Integer lhsSrcType = vstTableIn.getRefVarSrcType(lhs, currentSESE, vstIfStatic); + Integer rhsSrcType = vstTableIn.getRefVarSrcType(rhs, currentSESE, vstIfStatic); + + if (rhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) { + // if rhs is dynamic going in, lhs will definitely be dynamic + // going out of this node, so track that here + plan.addDynAssign(lhs, rhs); + addDynamicVar(currentSESE, fm, lhs); + addDynamicVar(currentSESE, fm, rhs); + + } else if (lhsSrcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) { + // otherwise, if the lhs is dynamic, but the rhs is not, we + // need to update the variable's dynamic source as "current SESE" + plan.addDynAssign(lhs); + } + + // only break if this is an ASSIGN op node, + // otherwise fall through to default case + break; } } // note that FlatOpNode's that aren't ASSIGN // fall through to this default case - default: { + default: { // a node with no live set has nothing to stall for - if( liveSetIn == null ) { - break; - } + // note: no reason to check here, remove this.... + // if (liveSetIn == null) { + // break; + // } TempDescriptor[] readarray = fn.readsTemps(); - for( int i = 0; i < readarray.length; i++ ) { + for (int i = 0; i < readarray.length; i++) { TempDescriptor readtmp = readarray[i]; - // ignore temps that are definitely available - // when considering to stall on it - if( !notAvailSetIn.contains( readtmp ) ) { - continue; - } + // ignore temps that are definitely available + // when considering to stall on it + if (!notAvailSetIn.contains(readtmp)) { + continue; + } - // check the source type of this variable + // check the source type of this variable VSTWrapper vstIfStatic = new VSTWrapper(); - Integer srcType - = vstTableIn.getRefVarSrcType( readtmp, - currentSESE, - vstIfStatic - ); - - if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) { - // 1) It is not clear statically where this variable will - // come from, so dynamically we must keep track - // along various control paths, and therefore when we stall, - // just stall for the exact thing we need and move on - plan.addDynamicStall( readtmp ); - currentSESE.addDynamicVar( readtmp ); - - } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) { - // 2) Single token/age pair: Stall for token/age pair, and copy - // all live variables with same token/age pair at the same - // time. This is the same stuff that the notavaialable analysis - // marks as now available. - VariableSourceToken vst = vstIfStatic.vst; - - Iterator availItr = - vstTableIn.get( vst.getSESE(), vst.getAge() ).iterator(); - - while( availItr.hasNext() ) { - VariableSourceToken vstAlsoAvail = availItr.next(); - - // only grab additional stuff that is live - Set copySet = new HashSet(); - - Iterator refVarItr = vstAlsoAvail.getRefVars().iterator(); - while( refVarItr.hasNext() ) { - TempDescriptor refVar = refVarItr.next(); - if( liveSetIn.contains( refVar ) ) { - copySet.add( refVar ); - } - } + Integer srcType = vstTableIn.getRefVarSrcType(readtmp, currentSESE, vstIfStatic); + + if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) { + // 1) It is not clear statically where this variable will + // come from, so dynamically we must keep track + // along various control paths, and therefore when we stall, + // just stall for the exact thing we need and move on + plan.addDynamicStall(readtmp); + addDynamicVar(currentSESE, fm, readtmp); + + } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) { + // 2) Single token/age pair: Stall for token/age pair, and copy + // all live variables with same token/age pair at the same + // time. This is the same stuff that the notavaialable analysis + // marks as now available. + VariableSourceToken vst = vstIfStatic.vst; - if( !copySet.isEmpty() ) { - plan.addStall2CopySet( vstAlsoAvail, copySet ); - } - } + Iterator availItr = + vstTableIn.get(vst.getSESE(), vst.getAge()).iterator(); - } else { - // the other case for srcs is READY, so do nothing - } + while (availItr.hasNext()) { + VariableSourceToken vstAlsoAvail = availItr.next(); - // assert that everything being stalled for is in the - // "not available" set coming into this flat node and - // that every VST identified is in the possible "stall set" - // that represents VST's from children SESE's + // only grab additional stuff that is live + Set copySet = new HashSet(); - } - } break; - - } // end switch + Iterator refVarItr = vstAlsoAvail.getRefVars().iterator(); + + while (refVarItr.hasNext()) { + TempDescriptor refVar = refVarItr.next(); + // note: this should just use normal liveness in...only want to + // copy live variables... + if (liveness.getLiveInTemps(fm, fn).contains(refVar)) { + copySet.add(refVar); + } + } + + if (!copySet.isEmpty()) { + plan.addStall2CopySet(vstAlsoAvail, copySet); + } + } + + } else { + // the other case for srcs is READY, so do nothing + } + + // assert that everything being stalled for is in the + // "not available" set coming into this flat node and + // that every VST identified is in the possible "stall set" + // that represents VST's from children SESE's + + } + } + break; + } // end switch // identify sese-age pairs that are statically useful // and should have an associated SESE variable in code // JUST GET ALL SESE/AGE NAMES FOR NOW, PRUNE LATER, - // AND ALWAYS GIVE NAMES TO PARENTS + // AND ALWAYS GIVE NAMES TO LOCAL PARENTS Set staticSet = vstTableIn.get(); Iterator vstItr = staticSet.iterator(); - while( vstItr.hasNext() ) { + while (vstItr.hasNext()) { VariableSourceToken vst = vstItr.next(); - // placeholder source tokens are useful results, but - // the placeholder static name is never needed - if( vst.getSESE().getIsCallerSESEplaceholder() ) { - continue; + // the caller proxy generates useful analysis facts, but we + // never need to generate another name for it in code (it is + // ALWAYS the task executing the local method context) + if (vst.getSESE().getIsCallerProxySESE()) { + continue; } + SESEandAgePair sap = new SESEandAgePair(vst.getSESE(), vst.getAge()); + sap.getSESE().mustTrackAtLeastAge(sap.getAge()); + FlatSESEEnterNode sese = currentSESE; - while( sese != null ) { - sese.addNeededStaticName( - new SESEandAgePair( vst.getSESE(), vst.getAge() ) - ); - sese.mustTrackAtLeastAge( vst.getAge() ); - - sese = sese.getParent(); + while (sese != null) { + addNeededStaticName(sese, fm, sap); + sese = sese.getLocalParent(); } } + codePlans.put(fn, plan); - codePlans.put( fn, plan ); - - - // if any variables at this-node-*dot* have a static source (exactly one vst) + // if any variables at this-node-*dot* have a static source (exactly one + // vst) // but go to a dynamic source at next-node-*dot*, create a new IR graph // node on that edge to track the sources dynamically - VarSrcTokTable thisVstTable = variableResults.get( fn ); - for( int i = 0; i < fn.numNext(); i++ ) { - FlatNode nn = fn.getNext( i ); - VarSrcTokTable nextVstTable = variableResults.get( nn ); - Set nextLiveIn = livenessRootView.get( nn ); + // NOTE: for this calculation use the currentSESE variable, except when the + // FlatNode fn is an Exit--in that case currentSESE is for the exiting task, + // be we want to consider that the parent is tracking a variable coming out + // of the exiting task + FlatSESEEnterNode fsenDoingTracking; + if (fn instanceof FlatSESEExitNode) { + fsenDoingTracking = currentSESE.getLocalParent(); + + if (fsenDoingTracking == null) { + // if there is no local parent, there are one of two cases + // 1) the current task is main, in which case this FlatNode + // is the main's exit, and doesn't need to do any of the + // following dynamic tracking + // 2) the current task is defined in a method, so use the + // caller proxy in the variable source calcs below + if (currentSESE.equals(rblockRel.getMainSESE())) { + return; + } else { + fsenDoingTracking = rblockRel.getCallerProxySESE(); + } + } + } else { + fsenDoingTracking = currentSESE; + } + + VarSrcTokTable thisVstTable = variableResults.get(fn); + for (int i = 0; i < fn.numNext(); i++) { + FlatNode nn = fn.getNext(i); + VarSrcTokTable nextVstTable = variableResults.get(nn); + // note: using the result of liveness analysis regardless of task + // structures + Set nextLiveIn = liveness.getLiveInTemps(fm, nn); // the table can be null if it is one of the few IR nodes // completely outside of the root SESE scope - if( nextVstTable != null && nextLiveIn != null ) { - - Hashtable readyOrStatic2dynamicSet = - thisVstTable.getReadyOrStatic2DynamicSet( nextVstTable, - nextLiveIn, - currentSESE - ); - - if( !readyOrStatic2dynamicSet.isEmpty() ) { - - // either add these results to partial fixed-point result - // or make a new one if we haven't made any here yet - FlatEdge fe = new FlatEdge( fn, nn ); - FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get( fe ); - - if( fwdvn == null ) { - fwdvn = new FlatWriteDynamicVarNode( fn, - nn, - readyOrStatic2dynamicSet, - currentSESE - ); - wdvNodesToSpliceIn.put( fe, fwdvn ); + if (nextVstTable != null && nextLiveIn != null) { + + Hashtable readyOrStatic2dynamicSet = + thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, fsenDoingTracking); + + if (!readyOrStatic2dynamicSet.isEmpty()) { + + // either add these results to partial fixed-point result + // or make a new one if we haven't made any here yet + FlatEdge fe = new FlatEdge(fn, nn); + FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe); + + if (fwdvn == null) { + fwdvn = + new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, fsenDoingTracking); + wdvNodesToSpliceIn.put(fe, fwdvn); + } else { + fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet); + } + } + } + } + } + + private void addDynamicVar(FlatSESEEnterNode fsen, FlatMethod fm, TempDescriptor var) { + FlatNode fnContext; + + // note: dynamic variable declarations are always located in the flat method + // that encloses task block + // there is no need to set fnContext to fsen + if (fsen.getIsCallerProxySESE()) { + // attach the dynamic variable to track to + // the flat method, so it can be declared at entry + fnContext = fm; + } else { + // otherwise the code context is a task body + fnContext = fsen; + } + // fnContext=fm; + + ContextTaskNames ctn = fn2contextTaskNames.get(fnContext); + if (ctn == null) { + ctn = new ContextTaskNames(); + } + + ctn.addDynamicVar(var); + fn2contextTaskNames.put(fnContext, ctn); + + } + + private void addNeededStaticName(FlatSESEEnterNode fsen, FlatMethod fm, SESEandAgePair sap) { + FlatNode fnContext; + + if (fsen.getIsCallerProxySESE()) { + // attach the dynamic variable to track to + // the flat method, so it can be declared at entry + fnContext = fm; } else { - fwdvn.addMoreVar2Src( readyOrStatic2dynamicSet ); + // otherwise the code context is a task body + fnContext = fsen; + } + + ContextTaskNames ctn = fn2contextTaskNames.get(fnContext); + if (ctn == null) { + ctn = new ContextTaskNames(); } + + ctn.addNeededStaticName(sap); + + fn2contextTaskNames.put(fnContext, ctn); } + + private void startConflictGraphs() { + + // first, for each task, consider whether it has any children, and if + // effects analysis says they should be a conflict node in the that + // parent's conflict graph + Set allSESEs = rblockRel.getAllSESEs(); + for (Iterator iterator = allSESEs.iterator(); iterator.hasNext(); ) { + + FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next(); + if (parent.getIsLeafSESE()) { + continue; + } + + EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis(); + ConflictGraph conflictGraph = sese2conflictGraph.get(parent); + assert conflictGraph == null; + conflictGraph = new ConflictGraph(state); + + Set children = parent.getChildren(); + for (Iterator iterator2 = children.iterator(); iterator2.hasNext(); ) { + FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next(); + Hashtable> taint2Effects = effectsAnalysis.get(child); + conflictGraph.addLiveIn(taint2Effects); + } + + sese2conflictGraph.put(parent, conflictGraph); + } + + // then traverse all methods looking for potential stall sites, and + // add those stall sites as nodes in any task's conflict graph that + // might be executing at the point of the stall site + Iterator descItr = descriptorsToAnalyze.iterator(); + while (descItr.hasNext()) { + MethodDescriptor md = descItr.next(); + FlatMethod fm = state.getMethodFlat(md); + if (fm != null) { + addStallSitesToConflictGraphs(fm); } } } - - private void makeConflictGraph(FlatMethod fm) { + + private void addStallSitesToConflictGraphs(FlatMethod fm) { Set flatNodesToVisit = new HashSet(); flatNodesToVisit.add(fm); @@ -1029,18 +1206,9 @@ private void codePlansForward( FlatMethod fm ) { flatNodesToVisit.remove(fn); visited.add(fn); - Stack seseStack = rblockRel.getRBlockStacks(fm, fn); - assert seseStack != null; + Set currentSESEs = rblockRel.getPossibleExecutingRBlocks(fn); - if (!seseStack.isEmpty()) { - - ConflictGraph conflictGraph = sese2conflictGraph.get(seseStack.peek()); - if (conflictGraph == null) { - conflictGraph = new ConflictGraph(); - } - - conflictGraph_nodeAction(fn, seseStack.peek()); - } + conflictGraph_nodeAction(fn, currentSESEs, fm.getMethod().getClassDesc()); // schedule forward nodes for analysis for (int i = 0; i < fn.numNext(); i++) { @@ -1049,135 +1217,94 @@ private void codePlansForward( FlatMethod fm ) { flatNodesToVisit.add(nn); } } - } - } - - private void conflictGraph_nodeAction(FlatNode fn, FlatSESEEnterNode currentSESE) { - - ConflictGraph conflictGraph; - TempDescriptor lhs; - TempDescriptor rhs; + private void conflictGraph_nodeAction(FlatNode fn, Set currentSESEs, + ClassDescriptor cd) { EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis(); - switch (fn.kind()) { + Hashtable> taint2Effects = effectsAnalysis.get(fn); - case FKind.FlatSESEEnterNode: { + // repeat the process of adding a stall site to a conflict graph + // for each task that might be executing at a possible stall site + Iterator seseItr = currentSESEs.iterator(); + while (seseItr.hasNext()) { + FlatSESEEnterNode currentSESE = seseItr.next(); - if (currentSESE.getParent() == null) { - return; - } - conflictGraph = sese2conflictGraph.get(currentSESE.getParent()); + ConflictGraph conflictGraph = sese2conflictGraph.get(currentSESE); if (conflictGraph == null) { - conflictGraph = new ConflictGraph(); + assert currentSESE.getIsLeafSESE(); + continue; } - FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn; + TempDescriptor lhs; + TempDescriptor rhs; - if (!fsen.getIsCallerSESEplaceholder() && currentSESE.getParent() != null) { - // collects effects set of invar set and generates invar node - Hashtable> taint2Effects = effectsAnalysis.get(currentSESE); - conflictGraph.addLiveIn(taint2Effects); - } + switch (fn.kind()) { - if (conflictGraph.id2cn.size() > 0) { - sese2conflictGraph.put(currentSESE.getParent(), conflictGraph); - } + case FKind.FlatFieldNode: + case FKind.FlatElementNode: { - } - break; - - case FKind.FlatFieldNode: - case FKind.FlatElementNode: { - - conflictGraph = sese2conflictGraph.get(currentSESE); - if (conflictGraph == null) { - conflictGraph = new ConflictGraph(); - } - - if (fn instanceof FlatFieldNode) { - FlatFieldNode ffn = (FlatFieldNode) fn; - rhs = ffn.getSrc(); - } else { - FlatElementNode fen = (FlatElementNode) fn; - rhs = fen.getSrc(); - } - - // add stall site - Hashtable> taint2Effects = effectsAnalysis.get(fn); - conflictGraph.addStallSite(taint2Effects, rhs); + if (fn instanceof FlatFieldNode) { + FlatFieldNode ffn = (FlatFieldNode) fn; + rhs = ffn.getSrc(); + } else { + FlatElementNode fen = (FlatElementNode) fn; + rhs = fen.getSrc(); + } - if (conflictGraph.id2cn.size() > 0) { - sese2conflictGraph.put(currentSESE, conflictGraph); + conflictGraph.addStallSite(taint2Effects, rhs, cd); } - } break; - case FKind.FlatSetFieldNode: - case FKind.FlatSetElementNode: { + case FKind.FlatSetFieldNode: + case FKind.FlatSetElementNode: { - conflictGraph = sese2conflictGraph.get(currentSESE); - if (conflictGraph == null) { - conflictGraph = new ConflictGraph(); - } + if (fn instanceof FlatSetFieldNode) { + FlatSetFieldNode fsfn = (FlatSetFieldNode) fn; + lhs = fsfn.getDst(); + rhs = fsfn.getSrc(); + } else { + FlatSetElementNode fsen = (FlatSetElementNode) fn; + lhs = fsen.getDst(); + rhs = fsen.getSrc(); + } - if (fn instanceof FlatSetFieldNode) { - FlatSetFieldNode fsfn = (FlatSetFieldNode) fn; - lhs = fsfn.getDst(); - rhs = fsfn.getSrc(); - } else { - FlatSetElementNode fsen = (FlatSetElementNode) fn; - lhs = fsen.getDst(); - rhs = fsen.getSrc(); + conflictGraph.addStallSite(taint2Effects, rhs, cd); + conflictGraph.addStallSite(taint2Effects, lhs, cd); } + break; - // collects effects of stall site and generates stall site node - Hashtable> taint2Effects = effectsAnalysis.get(fn); - conflictGraph.addStallSite(taint2Effects, rhs); - conflictGraph.addStallSite(taint2Effects, lhs); + case FKind.FlatCall: { + FlatCall fc = (FlatCall) fn; + lhs = fc.getThis(); - if (conflictGraph.id2cn.size() > 0) { - sese2conflictGraph.put(currentSESE, conflictGraph); + conflictGraph.addStallSite(taint2Effects, lhs, cd); } - } break; - case FKind.FlatCall: { - conflictGraph = sese2conflictGraph.get(currentSESE); - if (conflictGraph == null) { - conflictGraph = new ConflictGraph(); } - FlatCall fc = (FlatCall) fn; - lhs = fc.getThis(); - - // collects effects of stall site and generates stall site node - Hashtable> taint2Effects = effectsAnalysis.get(fn); - conflictGraph.addStallSite(taint2Effects, lhs); if (conflictGraph.id2cn.size() > 0) { sese2conflictGraph.put(currentSESE, conflictGraph); } } - - break; - - } - } private void calculateConflicts(Set sitesToFlag, boolean useReachInfo) { + // decide fine-grain edge or coarse-grain edge among all vertexes by // pair-wise comparison Iterator seseIter = sese2conflictGraph.keySet().iterator(); while (seseIter.hasNext()) { FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next(); ConflictGraph conflictGraph = sese2conflictGraph.get(sese); + if (useReachInfo) { // clear current conflict before recalculating with reachability info - conflictGraph.clearAllConflictEdge(); + conflictGraph.clearAllConflictEdge(); conflictGraph.setDisJointAnalysis(disjointAnalysisReach); conflictGraph.setFMEnclosing(sese.getfmEnclosing()); } @@ -1185,7 +1312,7 @@ private void codePlansForward( FlatMethod fm ) { sese2conflictGraph.put(sese, conflictGraph); } } - + private void writeConflictGraph() { Enumeration keyEnum = sese2conflictGraph.keys(); while (keyEnum.hasMoreElements()) { @@ -1201,17 +1328,30 @@ private void codePlansForward( FlatMethod fm ) { } } } - + + // the traversal for pruning state machines and finding + // machines that are weakly connected BOTH consider conflicting + // effects between heap roots, so it is smart to compute all of + // this together + public void pruneMachinesAndFindWeaklyConnectedExaminers() { + ProcessStateMachines psm = new ProcessStateMachines(buildStateMachines, rblockRel); + psm.doProcess(); + buildStateMachines.writeStateMachines("pruned"); + } + private void synthesizeLocks() { - Set> graphEntrySet = sese2conflictGraph.entrySet(); - for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) { - Entry graphEntry = (Entry) iterator.next(); + // for every conflict graph, generate a set of memory queues + // (called SESELock in this code!) to cover the graph + Set> graphEntrySet = sese2conflictGraph.entrySet(); + for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext(); ) { + Map.Entry graphEntry = + (Map.Entry)iterator.next(); FlatNode sese = graphEntry.getKey(); ConflictGraph conflictGraph = graphEntry.getValue(); calculateCovering(conflictGraph); } } - + private void calculateCovering(ConflictGraph conflictGraph) { uniqueLockSetId = 0; // reset lock counter for every new conflict graph HashSet fineToCover = new HashSet(); @@ -1219,7 +1359,7 @@ private void codePlansForward( FlatMethod fm ) { HashSet lockSet = new HashSet(); Set tempCover = conflictGraph.getEdgeSet(); - for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) { + for (Iterator iterator = tempCover.iterator(); iterator.hasNext(); ) { ConflictEdge conflictEdge = (ConflictEdge) iterator.next(); if (conflictEdge.isCoarseEdge()) { coarseToCover.add(conflictEdge); @@ -1243,7 +1383,7 @@ private void codePlansForward( FlatMethod fm ) { changed = false; - for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) { + for (Iterator iterator = fineToCover.iterator(); iterator.hasNext(); ) { int type; ConflictEdge edge = (ConflictEdge) iterator.next(); @@ -1288,8 +1428,8 @@ private void codePlansForward( FlatMethod fm ) { changed = true; seseLock.addConflictEdge(edge); fineToCover.remove(edge); - break;// exit iterator loop - }// end of initial setup + break; // exit iterator loop + } // end of initial setup ConflictNode newNode; if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) { @@ -1299,8 +1439,8 @@ private void codePlansForward( FlatMethod fm ) { // but the edge must remain uncovered. changed = true; - - if(seseLock.containsConflictNode(newNode)){ + + if (seseLock.containsConflictNode(newNode)) { seseLock.addEdge(edge); fineToCover.remove(edge); break; @@ -1324,7 +1464,7 @@ private void codePlansForward( FlatMethod fm ) { seseLock.addEdge(edge); Set edgeSet = newNode.getEdgeSet(); - for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) { + for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext(); ) { ConflictEdge conflictEdge = (ConflictEdge) iterator2.next(); // mark all fine edges between new node and nodes in the group as @@ -1345,15 +1485,16 @@ private void codePlansForward( FlatMethod fm ) { } - break;// exit iterator loop + break; // exit iterator loop } } } while (changed); + HashSet notCovered = new HashSet(); do { // coarse changed = false; int type; - for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) { + for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext(); ) { ConflictEdge edge = (ConflictEdge) iterator.next(); if (seseLock.getConflictNodeSet().size() == 0) { @@ -1364,18 +1505,26 @@ private void codePlansForward( FlatMethod fm ) { // and it is not parent type = ConflictNode.SCC; } else { - type = ConflictNode.PARENT_WRITE; + if (state.RCR) { + type = ConflictNode.PARENT_COARSE; + } else { + type = ConflictNode.PARENT_WRITE; + } } seseLock.addConflictNode(edge.getVertexU(), type); } else { if (edge.getVertexU().isStallSiteNode()) { - if(edge.getVertexU().getWriteEffectSet().isEmpty()){ - type = ConflictNode.PARENT_READ; - }else{ - type = ConflictNode.PARENT_WRITE; + if (state.RCR) { + type = ConflictNode.PARENT_COARSE; + } else { + if (edge.getVertexU().getWriteEffectSet().isEmpty()) { + type = ConflictNode.PARENT_READ; + } else { + type = ConflictNode.PARENT_WRITE; + } } } else { - type = ConflictNode.COARSE; + type = ConflictNode.COARSE; } seseLock.addConflictNode(edge.getVertexU(), type); } @@ -1385,16 +1534,24 @@ private void codePlansForward( FlatMethod fm ) { // and it is not parent type = ConflictNode.SCC; } else { - type = ConflictNode.PARENT_WRITE; + if (state.RCR) { + type = ConflictNode.PARENT_COARSE; + } else { + type = ConflictNode.PARENT_WRITE; + } } seseLock.addConflictNode(edge.getVertexV(), type); } else { - if (edge.getVertexV().isStallSiteNode()) { - if(edge.getVertexV().getWriteEffectSet().isEmpty()){ - type = ConflictNode.PARENT_READ; - }else{ - type = ConflictNode.PARENT_WRITE; - } + if (edge.getVertexV().isStallSiteNode()) { + if (state.RCR) { + type = ConflictNode.PARENT_COARSE; + } else { + if (edge.getVertexV().getWriteEffectSet().isEmpty()) { + type = ConflictNode.PARENT_READ; + } else { + type = ConflictNode.PARENT_WRITE; + } + } } else { type = ConflictNode.COARSE; } @@ -1403,20 +1560,26 @@ private void codePlansForward( FlatMethod fm ) { changed = true; coarseToCover.remove(edge); seseLock.addConflictEdge(edge); - break;// exit iterator loop - }// end of initial setup + break; // exit iterator loop + } // end of initial setup ConflictNode newNode; if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) { // new node has a coarse-grained edge to all fine-read, fine-write, // parent changed = true; - - if(newNode.isInVarNode() && - (!seseLock.hasSelfCoarseEdge(newNode)) && - seseLock.hasCoarseEdgeWithParentCoarse(newNode)){ + + if (newNode.isInVarNode() && (!seseLock.hasSelfCoarseEdge(newNode)) + && seseLock.hasCoarseEdgeWithParentCoarse(newNode)) { // this case can't be covered by this queue coarseToCover.remove(edge); + notCovered.add(edge); + break; + } + + if (seseLock.containsConflictNode(newNode)) { + seseLock.addEdge(edge); + coarseToCover.remove(edge); break; } @@ -1439,7 +1602,7 @@ private void codePlansForward( FlatMethod fm ) { seseLock.addEdge(edge); Set edgeSet = newNode.getEdgeSet(); - for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) { + for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext(); ) { ConflictEdge conflictEdge = (ConflictEdge) iterator2.next(); // mark all coarse edges between new node and nodes in the group // as covered @@ -1458,7 +1621,7 @@ private void codePlansForward( FlatMethod fm ) { } } - break;// exit iterator loop + break; // exit iterator loop } } @@ -1467,6 +1630,7 @@ private void codePlansForward( FlatMethod fm ) { lockSet.add(seseLock); toCover.clear(); + coarseToCover.addAll(notCovered); toCover.addAll(fineToCover); toCover.addAll(coarseToCover); @@ -1474,145 +1638,138 @@ private void codePlansForward( FlatMethod fm ) { conflictGraph2SESELock.put(conflictGraph, lockSet); } - - public ConflictGraph getConflictGraph(FlatNode sese){ - return sese2conflictGraph.get(sese); + + public ConflictGraph getConflictGraph(FlatNode sese) { + return sese2conflictGraph.get(sese); } - - public Set getLockMappings(ConflictGraph graph){ + + public Set getLockMappings(ConflictGraph graph) { return conflictGraph2SESELock.get(graph); } - + public Set getAllSESEs() { return rblockRel.getAllSESEs(); } - + public FlatSESEEnterNode getMainSESE() { return rblockRel.getMainSESE(); } - - public void writeReports( String timeReport ) throws java.io.IOException { - - BufferedWriter bw = new BufferedWriter( new FileWriter( "mlpReport_summary.txt" ) ); - bw.write( "MLP Analysis Results\n\n" ); - bw.write( timeReport+"\n\n" ); - printSESEHierarchy( bw ); - bw.write( "\n" ); - printSESEInfo( bw ); + + public FlatSESEEnterNode getCallerProxySESE() { + return rblockRel.getCallerProxySESE(); + } + + public Set getPossibleExecutingRBlocks(FlatNode fn) { + return rblockRel.getPossibleExecutingRBlocks(fn); + } + + public void writeReports(String timeReport) throws java.io.IOException { + + BufferedWriter bw = new BufferedWriter(new FileWriter("ooojReport_summary.txt")); + bw.write("OoOJava Analysis Results\n\n"); + bw.write(timeReport + "\n\n"); + printSESEHierarchy(bw); + bw.write("\n"); + printSESEInfo(bw); bw.close(); - Iterator methItr = disjointAnalysisTaints.getDescriptorsToAnalyze().iterator(); - while( methItr.hasNext() ) { - MethodDescriptor md = (MethodDescriptor) methItr.next(); - FlatMethod fm = state.getMethodFlat( md ); - if (fm!=null) { + Iterator methItr = descriptorsToAnalyze.iterator(); + while (methItr.hasNext()) { + MethodDescriptor md = methItr.next(); + FlatMethod fm = state.getMethodFlat(md); + if (fm != null) { bw = - new BufferedWriter(new FileWriter("mlpReport_" + md.getClassMethodName() - + md.getSafeMethodDescriptor() + ".txt")); - bw.write("MLP Results for " + md + "\n-------------------\n"); - - FlatSESEEnterNode implicitSESE = (FlatSESEEnterNode) fm.getNext(0); - if (!implicitSESE.getIsCallerSESEplaceholder() && implicitSESE != rblockRel.getMainSESE()) { - System.out.println(implicitSESE + " is not implicit?!"); - System.exit(-1); - } - bw.write("Dynamic vars to manage:\n " + implicitSESE.getDynamicVarSet()); + new BufferedWriter(new FileWriter("ooojReport_" + md.getClassMethodName() + + md.getSafeMethodDescriptor() + ".txt")); + bw.write("OoOJava Results for " + md + "\n-------------------\n"); + + bw.write("Dynamic vars to manage:\n " + getContextTaskNames(fm).getDynamicVarSet()); - bw.write("\n\nLive-In, Root View\n------------------\n" + fm.printMethod(livenessRootView)); + bw.write("\n\nLive-In, Root View\n------------------\n" + + fm.printMethod(livenessGlobalView)); bw.write("\n\nVariable Results-Out\n----------------\n" + fm.printMethod(variableResults)); bw.write("\n\nNot Available Results-Out\n---------------------\n" - + fm.printMethod(notAvailableResults)); + + fm.printMethod(notAvailableResults)); bw.write("\n\nCode Plans\n----------\n" + fm.printMethod(codePlans)); bw.close(); } } } - - private void printSESEHierarchy( BufferedWriter bw ) throws java.io.IOException { - bw.write( "SESE Hierarchy\n--------------\n" ); - Iterator rootItr = rblockRel.getRootSESEs().iterator(); - while( rootItr.hasNext() ) { + + private void printSESEHierarchy(BufferedWriter bw) throws java.io.IOException { + bw.write("SESE Local Hierarchy\n--------------\n"); + Iterator rootItr = rblockRel.getLocalRootSESEs().iterator(); + while (rootItr.hasNext()) { FlatSESEEnterNode root = rootItr.next(); - if( root.getIsCallerSESEplaceholder() ) { - if( !root.getChildren().isEmpty() ) { - printSESEHierarchyTree( bw, root, 0 ); - } - } else { - printSESEHierarchyTree( bw, root, 0 ); - } + printSESEHierarchyTree(bw, root, 0); } } - private void printSESEHierarchyTree( BufferedWriter bw, - FlatSESEEnterNode fsen, - int depth - ) throws java.io.IOException { - for( int i = 0; i < depth; ++i ) { - bw.write( " " ); + private void printSESEHierarchyTree(BufferedWriter bw, FlatSESEEnterNode fsen, int depth) + throws java.io.IOException { + for (int i = 0; i < depth; ++i) { + bw.write(" "); } - bw.write( "- "+fsen.getPrettyIdentifier()+"\n" ); + bw.write("- " + fsen.getPrettyIdentifier() + "\n"); - Iterator childItr = fsen.getChildren().iterator(); - while( childItr.hasNext() ) { + Iterator childItr = fsen.getLocalChildren().iterator(); + while (childItr.hasNext()) { FlatSESEEnterNode fsenChild = childItr.next(); - printSESEHierarchyTree( bw, fsenChild, depth + 1 ); + printSESEHierarchyTree(bw, fsenChild, depth + 1); } } - - private void printSESEInfo( BufferedWriter bw ) throws java.io.IOException { - bw.write("\nSESE info\n-------------\n" ); - Iterator rootItr = rblockRel.getRootSESEs().iterator(); - while( rootItr.hasNext() ) { - FlatSESEEnterNode root = rootItr.next(); - if( root.getIsCallerSESEplaceholder() ) { - if( !root.getChildren().isEmpty() ) { - printSESEInfoTree( bw, root ); - } - } else { - printSESEInfoTree( bw, root ); + private void printSESEInfo(BufferedWriter bw) throws java.io.IOException { + bw.write("\nSESE info\n-------------\n"); + Iterator fsenItr = rblockRel.getAllSESEs().iterator(); + while (fsenItr.hasNext()) { + FlatSESEEnterNode fsen = fsenItr.next(); + + bw.write("SESE " + fsen.getPrettyIdentifier()); + if (fsen.getIsLeafSESE()) { + bw.write(" (leaf)"); } - } - } - - public DisjointAnalysis getDisjointAnalysis(){ - return disjointAnalysisReach; - } + bw.write(" {\n"); - private void printSESEInfoTree( BufferedWriter bw, - FlatSESEEnterNode fsen - ) throws java.io.IOException { + bw.write(" in-set: " + fsen.getInVarSet() + "\n"); + Iterator tItr = fsen.getInVarSet().iterator(); + while (tItr.hasNext()) { + TempDescriptor inVar = tItr.next(); + if (fsen.getReadyInVarSet().contains(inVar)) { + bw.write(" (ready) " + inVar + "\n"); + } + if (fsen.getStaticInVarSet().contains(inVar)) { + bw.write(" (static) " + inVar + " from " + fsen.getStaticInVarSrc(inVar) + "\n"); + } + if (fsen.getDynamicInVarSet().contains(inVar)) { + bw.write(" (dynamic)" + inVar + "\n"); + } + } - if( !fsen.getIsCallerSESEplaceholder() ) { - bw.write( "SESE "+fsen.getPrettyIdentifier()+" {\n" ); + bw.write(" Dynamic vars to manage: " + getContextTaskNames(fsen).getDynamicVarSet() + "\n"); - bw.write( " in-set: "+fsen.getInVarSet()+"\n" ); - Iterator tItr = fsen.getInVarSet().iterator(); - while( tItr.hasNext() ) { - TempDescriptor inVar = tItr.next(); - if( fsen.getReadyInVarSet().contains( inVar ) ) { - bw.write( " (ready) "+inVar+"\n" ); - } - if( fsen.getStaticInVarSet().contains( inVar ) ) { - bw.write( " (static) "+inVar+" from "+ - fsen.getStaticInVarSrc( inVar )+"\n" ); - } - if( fsen.getDynamicInVarSet().contains( inVar ) ) { - bw.write( " (dynamic)"+inVar+"\n" ); - } + bw.write(" out-set: " + fsen.getOutVarSet() + "\n"); + tItr = fsen.getOutVarSet().iterator(); + while (tItr.hasNext()) { + TempDescriptor outVar = tItr.next(); + if (fsen.getReadyOutVarSet().contains(outVar)) { + bw.write(" (ready) " + outVar + "\n"); + } + if (fsen.getStaticOutVarSet().contains(outVar)) { + bw.write(" (static) " + outVar + " from " + fsen.getStaticOutVarSrc(outVar) + "\n"); + } + if (fsen.getDynamicOutVarSet().contains(outVar)) { + bw.write(" (dynamic)" + outVar + "\n"); + } } - - bw.write( " Dynamic vars to manage: "+fsen.getDynamicVarSet()+"\n"); - - bw.write( " out-set: "+fsen.getOutVarSet()+"\n" ); - bw.write( "}\n" ); - } - Iterator childItr = fsen.getChildren().iterator(); - while( childItr.hasNext() ) { - FlatSESEEnterNode fsenChild = childItr.next(); - printSESEInfoTree( bw, fsenChild ); + bw.write(" local parent: " + fsen.getLocalParent() + "\n"); + bw.write(" local children: " + fsen.getLocalChildren() + "\n"); + + bw.write(" possible parents: " + fsen.getParents() + "\n"); + bw.write(" possible children: " + fsen.getChildren() + "\n"); + + bw.write("}\n"); } } - }