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 {
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<MethodDescriptor> descriptorsToAnalyze;
- private Hashtable<FlatNode, Set<TempDescriptor>> livenessRootView;
+ private Hashtable<FlatNode, Set<TempDescriptor>> livenessGlobalView;
private Hashtable<FlatNode, Set<TempDescriptor>> livenessVirtualReads;
private Hashtable<FlatNode, VarSrcTokTable> variableResults;
private Hashtable<FlatNode, Set<TempDescriptor>> notAvailableResults;
private Hashtable<FlatEdge, FlatWriteDynamicVarNode> wdvNodesToSpliceIn;
+ private Hashtable<FlatNode, ContextTaskNames> fn2contextTaskNames;
+
+ // get the flat method that contains any given flat node
+ private Hashtable<FlatNode, FlatMethod> fn2fm;
+
// temporal data structures to track analysis progress.
static private int uniqueLockSetId = 0;
// mapping of a conflict graph to its compiled lock
return codePlans.keySet();
}
- public OoOJavaAnalysis(State state, TypeUtil typeUtil, CallGraph callGraph, Liveness liveness,
- ArrayReferencees arrayReferencees) {
+ 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;
+ }
+
+ 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;
+ }
- double timeStartAnalysis = (double) System.nanoTime();
+ 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<FlatNode, Set<TempDescriptor>>();
+ livenessGlobalView = new Hashtable<FlatNode, Set<TempDescriptor>>();
livenessVirtualReads = new Hashtable<FlatNode, Set<TempDescriptor>>();
variableResults = new Hashtable<FlatNode, VarSrcTokTable>();
notAvailableResults = new Hashtable<FlatNode, Set<TempDescriptor>>();
codePlans = new Hashtable<FlatNode, CodePlan>();
wdvNodesToSpliceIn = new Hashtable<FlatEdge, FlatWriteDynamicVarNode>();
-
notAvailableIntoSESE = new Hashtable<FlatSESEEnterNode, Set<TempDescriptor>>();
-
sese2conflictGraph = new Hashtable<FlatNode, ConflictGraph>();
conflictGraph2SESELock = new Hashtable<ConflictGraph, HashSet<SESELock>>();
+ fn2contextTaskNames = new Hashtable<FlatNode, ContextTaskNames>();
+ fn2fm = new Hashtable<FlatNode, FlatMethod>();
+
+ // 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<MethodDescriptor> 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<MethodDescriptor> 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<FlatSESEEnterNode> rootItr = rblockRel.getRootSESEs().iterator();
- while (rootItr.hasNext()) {
- FlatSESEEnterNode root = rootItr.next();
- livenessAnalysisBackward(root, true, null);
- }
+ // run liveness analysis for each sese blocks
+ Iterator<FlatSESEEnterNode> seseItr = rblockRel.getAllSESEs().iterator();
+ while (seseItr.hasNext()) {
+ FlatSESEEnterNode sese = seseItr.next();
+ livenessAnalysisBackward(sese);
+ }
+
+ State.logEvent("OoOJavaAnalysis 2nd pass completed");
// 3rd pass, variable analysis
- Iterator<MethodDescriptor> 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,
- rblockRel, rblockStatus,
- true ); // suppress output--this is an intermediate pass
+ 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,
-
- Set<FlatSESEEnterNode> allSESEs=rblockRel.getAllSESEs();
- for (Iterator iterator = allSESEs.iterator(); iterator.hasNext();) {
-
- FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
- if (!parent.getIsLeafSESE()) {
-
- EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
- ConflictGraph conflictGraph = sese2conflictGraph.get(parent);
- if (conflictGraph == null) {
- conflictGraph = new ConflictGraph(state);
- }
-
- Set<FlatSESEEnterNode> children = parent.getSESEChildren();
- for (Iterator iterator2 = children.iterator(); iterator2.hasNext();) {
- FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
- Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(child);
- conflictGraph.addLiveIn(taint2Effects);
- sese2conflictGraph.put(parent, conflictGraph);
- }
- }
- }
-
- Iterator descItr = disjointAnalysisTaints.getDescriptorsToAnalyze().iterator();
- while (descItr.hasNext()) {
- Descriptor d = (Descriptor) descItr.next();
- FlatMethod fm = state.getMethodFlat(d);
- if (fm != null)
- makeConflictGraph(fm);
- }
-
-
-
- // 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<String> 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
+ 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<FlatNew> sitesToFlag = new HashSet<FlatNew>();
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
+ // later
disjointAnalysisReach =
new DisjointAnalysis(state, typeUtil, callGraph, liveness, arrayReferencees, sitesToFlag,
- null, // don't do effects analysis again!
- null // don't do effects analysis again!
- );
+ 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");
}
- // 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();
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();
+ Map.Entry me = (Map.Entry)spliceItr.next();
FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
fwdvn.spliceIntoIR();
}
+ State.logEvent("OoOJavaAnalysis 13th pass completed");
if (state.OOODEBUG) {
try {
} catch (IOException e) {
}
}
+ State.logEvent("OoOJavaAnalysis completed");
+ }
+
+ private void buildFlatNodeToFlatMethod(FlatMethod fm) {
+ Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
+ flatNodesToVisit.add(fm);
+
+ Set<FlatNode> flatNodesVisited = new HashSet<FlatNode>();
+
+ 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);
+ }
+ }
+ }
}
-
+
+ // 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<String> 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<FlatNew> sitesToFlag) {
try {
BufferedWriter bw = new BufferedWriter(new FileWriter("sitesToFlag.txt"));
- for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext();) {
+ for (Iterator iterator = sitesToFlag.iterator(); iterator.hasNext(); ) {
FlatNew fn = (FlatNew) iterator.next();
bw.write(fn + "\n");
}
}
- private void livenessAnalysisBackward(FlatSESEEnterNode fsen, boolean toplevel,
- Hashtable<FlatSESEExitNode, Set<TempDescriptor>> 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
- Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
+ private void livenessAnalysisBackward(FlatSESEEnterNode fsen) {
- if (toplevel) {
- flatNodesToVisit.add(fsen.getfmEnclosing().getFlatExit());
- } else {
- flatNodesToVisit.add(fsen.getFlatExit());
- }
-
- Hashtable<FlatNode, Set<TempDescriptor>> livenessResults =
+ // each task maintains a local liveness result
+ Hashtable<FlatNode, Set<TempDescriptor>> livenessLocalView =
new Hashtable<FlatNode, Set<TempDescriptor>>();
- if (toplevel) {
- liveout = new Hashtable<FlatSESEExitNode, Set<TempDescriptor>>();
- }
+ // 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<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
+ flatNodesToVisit.add(fsen.getFlatExit());
while (!flatNodesToVisit.isEmpty()) {
FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
flatNodesToVisit.remove(fn);
- Set<TempDescriptor> prev = livenessResults.get(fn);
+ Set<TempDescriptor> prev = livenessLocalView.get(fn);
// merge sets from control flow joins
- Set<TempDescriptor> u = new HashSet<TempDescriptor>();
+ Set<TempDescriptor> livein = new HashSet<TempDescriptor>();
for (int i = 0; i < fn.numNext(); i++) {
FlatNode nn = fn.getNext(i);
- Set<TempDescriptor> s = livenessResults.get(nn);
+ Set<TempDescriptor> s = livenessLocalView.get(nn);
if (s != null) {
- u.addAll(s);
+ livein.addAll(s);
}
}
- Set<TempDescriptor> curr = liveness_nodeActions(fn, u, fsen, toplevel, liveout);
+ Set<TempDescriptor> 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);
}
}
}
-
- Set<TempDescriptor> 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<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
- while (childItr.hasNext()) {
- FlatSESEEnterNode fsenChild = childItr.next();
- livenessAnalysisBackward(fsenChild, false, liveout);
- }
}
- private Set<TempDescriptor> liveness_nodeActions(FlatNode fn, Set<TempDescriptor> liveIn,
- FlatSESEEnterNode currentSESE, boolean toplevel,
- Hashtable<FlatSESEExitNode, Set<TempDescriptor>> liveout) {
+ private Set<TempDescriptor> liveness_nodeActions(FlatSESEEnterNode currSESE, FlatNode fn,
+ Set<TempDescriptor> liveIn) {
+
switch (fn.kind()) {
- case FKind.FlatSESEExitNode:
- if (toplevel) {
- FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
- if (!liveout.containsKey(fsexn)) {
- liveout.put(fsexn, new HashSet<TempDescriptor>());
+ 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
for (int i = 0; i < writeTemps.length; ++i) {
liveIn.remove(writeTemps[i]);
- if (!toplevel) {
- FlatSESEExitNode fsexn = currentSESE.getFlatExit();
- Set<TempDescriptor> 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<TempDescriptor> 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]);
}
}
}
if (virtualReadTemps != null) {
liveIn.addAll(virtualReadTemps);
}
-
}
break;
FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
flatNodesToVisit.remove(fn);
- Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
- assert seseStack != null;
-
VarSrcTokTable prev = variableResults.get(fn);
// merge sets from control flow joins
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);
}
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
// 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<TempDescriptor> liveVars = livenessRootView.get(fn);
+ // Set<TempDescriptor> liveVars = liveness.getLiveInTemps(fsen.getfmEnclosing(), fn);
+ Set<TempDescriptor> liveVars = livenessGlobalView.get(fn);
+
Set<TempDescriptor> fsenVirtReads =
- vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen, liveVars);
+ vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen, liveVars);
+
Set<TempDescriptor> 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
vstTable.add(vst);
}
vstTable.assertConsistency();
-
}
- break;
+ break;
case FKind.FlatOpNode: {
FlatOpNode fon = (FlatOpNode) fn;
HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
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));
}
}
- // 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) {
// 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;
vstTable.assertConsistency();
}
- break;
+ break;
} // end switch
}
FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
flatNodesToVisit.remove(fn);
- Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
- assert seseStack != null;
-
Set<TempDescriptor> prev = notAvailableResults.get(fn);
Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
}
}
- 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);
}
private void notAvailable_nodeActions(FlatNode fn, Set<TempDescriptor> 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
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
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<TempDescriptor> 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;
}
}
- // 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++) {
VariableSourceToken vst = vstIfStatic.vst;
Iterator<VariableSourceToken> availItr =
- vstTable.get(vst.getSESE(), vst.getAge()).iterator();
+ vstTable.get(vst.getSESE(), vst.getAge()).iterator();
// look through things that are also available from same source
while (availItr.hasNext()) {
// only comes from one statically known source, mark it available
VSTWrapper vstIfStaticNotUsed = new VSTWrapper();
Integer srcTypeAlso =
- vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed);
+ vstTable.getRefVarSrcType(refVarAlso, currentSESE, vstIfStaticNotUsed);
if (srcTypeAlso.equals(VarSrcTokTable.SrcType_STATIC)) {
notAvailSet.remove(refVarAlso);
}
}
}
}
- break;
+ break;
} // end switch
}
flatNodesToVisit.remove(fn);
visited.add(fn);
- Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
- assert seseStack != null;
-
// use incoming results as "dot statement" or just
// before the current statement
VarSrcTokTable dotSTtable = new VarSrcTokTable();
}
}
- Set<TempDescriptor> dotSTlive = livenessRootView.get(fn);
+ Set<TempDescriptor> 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();
}
+ codePlans_nodeActions(fm, fn, dotSTtable, dotSTnotAvailSet, currentSESE);
+
for (int i = 0; i < fn.numNext(); i++) {
FlatNode nn = fn.getNext(i);
}
}
- private void codePlans_nodeActions(FlatNode fn, Set<TempDescriptor> liveSetIn,
- VarSrcTokTable vstTableIn, Set<TempDescriptor> notAvailSetIn, FlatSESEEnterNode currentSESE) {
+ private void codePlans_nodeActions(FlatMethod fm, FlatNode fn, VarSrcTokTable vstTableIn,
+ Set<TempDescriptor> notAvailSetIn, FlatSESEEnterNode currentSESE) {
CodePlan plan = new CodePlan(currentSESE);
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
// 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);
+ 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);
- fsen.getParent().addDynamicVar(inVar);
+ addDynamicVar(parent, fm, 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);
}
}
-
}
- break;
+ break;
case FKind.FlatSESEExitNode: {
FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
+
+ // 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<TempDescriptor> 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;
+ break;
case FKind.FlatOpNode: {
FlatOpNode fon = (FlatOpNode) fn;
// 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);
+ 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
}
}
- // 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: {
// 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++) {
// 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);
+ addDynamicVar(currentSESE, fm, readtmp);
} else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) {
// 2) Single token/age pair: Stall for token/age pair, and copy
VariableSourceToken vst = vstIfStatic.vst;
Iterator<VariableSourceToken> availItr =
- vstTableIn.get(vst.getSESE(), vst.getAge()).iterator();
+ vstTableIn.get(vst.getSESE(), vst.getAge()).iterator();
while (availItr.hasNext()) {
VariableSourceToken vstAlsoAvail = availItr.next();
Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
+
while (refVarItr.hasNext()) {
TempDescriptor refVar = refVarItr.next();
- if (liveSetIn.contains(refVar)) {
+ // note: this should just use normal liveness in...only want to
+ // copy live variables...
+ if (liveness.getLiveInTemps(fm, fn).contains(refVar)) {
copySet.add(refVar);
}
}
}
}
- break;
+ 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<VariableSourceToken> staticSet = vstTableIn.get();
Iterator<VariableSourceToken> vstItr = staticSet.iterator();
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()) {
+ // 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();
+ addNeededStaticName(sese, fm, sap);
+ sese = sese.getLocalParent();
}
}
// 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
+ // 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);
- Set<TempDescriptor> nextLiveIn = livenessRootView.get(nn);
+ // note: using the result of liveness analysis regardless of task
+ // structures
+ Set<TempDescriptor> 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<TempDescriptor, VSTWrapper> readyOrStatic2dynamicSet =
- thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, currentSESE);
+ thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, fsenDoingTracking);
if (!readyOrStatic2dynamicSet.isEmpty()) {
FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe);
if (fwdvn == null) {
- fwdvn = new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, currentSESE);
+ fwdvn =
+ new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, fsenDoingTracking);
wdvNodesToSpliceIn.put(fe, fwdvn);
} else {
fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet);
}
}
- private void makeConflictGraph(FlatMethod fm) {
+ 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 {
+ // 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<FlatSESEEnterNode> 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<FlatSESEEnterNode> children = parent.getChildren();
+ for (Iterator iterator2 = children.iterator(); iterator2.hasNext(); ) {
+ FlatSESEEnterNode child = (FlatSESEEnterNode) iterator2.next();
+ Hashtable<Taint, Set<Effect>> 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<MethodDescriptor> descItr = descriptorsToAnalyze.iterator();
+ while (descItr.hasNext()) {
+ MethodDescriptor md = descItr.next();
+ FlatMethod fm = state.getMethodFlat(md);
+ if (fm != null) {
+ addStallSitesToConflictGraphs(fm);
+ }
+ }
+ }
+
+ private void addStallSitesToConflictGraphs(FlatMethod fm) {
Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
flatNodesToVisit.add(fm);
flatNodesToVisit.remove(fn);
visited.add(fn);
- Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
- assert seseStack != null;
+ Set<FlatSESEEnterNode> currentSESEs = rblockRel.getPossibleExecutingRBlocks(fn);
- if (!seseStack.isEmpty()) {
- 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++) {
flatNodesToVisit.add(nn);
}
}
-
}
-
}
- private void conflictGraph_nodeAction(FlatNode fn, FlatSESEEnterNode currentSESE) {
+ private void conflictGraph_nodeAction(FlatNode fn, Set<FlatSESEEnterNode> currentSESEs,
+ ClassDescriptor cd) {
- ConflictGraph conflictGraph;
- TempDescriptor lhs;
- TempDescriptor rhs;
-
EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
- switch (fn.kind()) {
-
- case FKind.FlatFieldNode:
- case FKind.FlatElementNode: {
-
- if (fn instanceof FlatFieldNode) {
- FlatFieldNode ffn = (FlatFieldNode) fn;
- rhs = ffn.getSrc();
- } else {
- FlatElementNode fen = (FlatElementNode) fn;
- rhs = fen.getSrc();
- }
-
- // jjenista - I think the following code is WRONG!!!
- // We are looking at some non-task FlatNode fn that is a stall site and
- // considering what conflicts it might have with CHILDREN of the CURRENT TASK
- // that contains fn. WE SHOULD NOT BE GETTING THE PARENT OF currentSESE
- // because in this scenario currentSESE IS the parent in relation to other
- // tasks that might conflict with this fn.
- // OK, why not fix it? Because code all over the place is built on
- // being able to retrieve the correct conflict graph, which is associated
- // with the wrong task, but at least consistently, SO LEAVE IT BUT REALIZE
- // WHAT IS HAPPENING
-
- Set<FlatSESEEnterNode> parentSet = currentSESE.getSESEParent();
- for (Iterator iterator = parentSet.iterator(); iterator.hasNext();) {
- FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
-// System.out.println("##current="+currentSESE.getmdEnclosing()+" PARENT=" + parent);
- conflictGraph = sese2conflictGraph.get(parent);
- if (conflictGraph == null) {
- conflictGraph = new ConflictGraph(state);
- }
+ Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
- // add stall site
- Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
- conflictGraph.addStallSite(taint2Effects, rhs);
- if (taint2Effects != null)
-// System.out.println("add =" + taint2Effects + "currentSESE=" + parent
-// + " into conflictGraph=" + conflictGraph);
+ // 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<FlatSESEEnterNode> seseItr = currentSESEs.iterator();
+ while (seseItr.hasNext()) {
+ FlatSESEEnterNode currentSESE = seseItr.next();
- if (conflictGraph.id2cn.size() > 0) {
- sese2conflictGraph.put(parent, conflictGraph);
- }
+ ConflictGraph conflictGraph = sese2conflictGraph.get(currentSESE);
+ if (conflictGraph == null) {
+ assert currentSESE.getIsLeafSESE();
+ continue;
}
- }
- break;
+ TempDescriptor lhs;
+ TempDescriptor rhs;
- case FKind.FlatSetFieldNode:
- case FKind.FlatSetElementNode: {
+ switch (fn.kind()) {
- 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();
- }
+ case FKind.FlatFieldNode:
+ case FKind.FlatElementNode: {
- // jjenista - I think the following code is WRONG!!!
- // We are looking at some non-task FlatNode fn that is a stall site and
- // considering what conflicts it might have with CHILDREN of the CURRENT TASK
- // that contains fn. WE SHOULD NOT BE GETTING THE PARENT OF currentSESE
- // because in this scenario currentSESE IS the parent in relation to other
- // tasks that might conflict with this fn.
- // OK, why not fix it? Because code all over the place is built on
- // being able to retrieve the correct conflict graph, which is associated
- // with the wrong task, but at least consistently, SO LEAVE IT BUT REALIZE
- // WHAT IS HAPPENING
-
- // collects effects of stall site and generates stall site node
- Set<FlatSESEEnterNode> parentSet = currentSESE.getSESEParent();
- for (Iterator iterator = parentSet.iterator(); iterator.hasNext();) {
- FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
- conflictGraph = sese2conflictGraph.get(parent);
- if (conflictGraph == null) {
- conflictGraph = new ConflictGraph(state);
+ if (fn instanceof FlatFieldNode) {
+ FlatFieldNode ffn = (FlatFieldNode) fn;
+ rhs = ffn.getSrc();
+ } else {
+ FlatElementNode fen = (FlatElementNode) fn;
+ rhs = fen.getSrc();
}
- Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
- conflictGraph.addStallSite(taint2Effects, rhs);
- conflictGraph.addStallSite(taint2Effects, lhs);
-
- if (conflictGraph.id2cn.size() > 0) {
- sese2conflictGraph.put(parent, conflictGraph);
- }
+ conflictGraph.addStallSite(taint2Effects, rhs, cd);
}
-
- }
break;
- case FKind.FlatCall: {
- conflictGraph = sese2conflictGraph.get(currentSESE);
- if (conflictGraph == null) {
- conflictGraph = new ConflictGraph(state);
- }
-
- FlatCall fc = (FlatCall) fn;
- lhs = fc.getThis();
-
- // collects effects of stall site and generates stall site node
- Hashtable<Taint, Set<Effect>> taint2Effects = effectsAnalysis.get(fn);
-
- // jjenista - I think the following code is WRONG!!!
- // We are looking at some non-task FlatNode fn that is a stall site and
- // considering what conflicts it might have with CHILDREN of the CURRENT TASK
- // that contains fn. WE SHOULD NOT BE GETTING THE PARENT OF currentSESE
- // because in this scenario currentSESE IS the parent in relation to other
- // tasks that might conflict with this fn.
- // OK, why not fix it? Because code all over the place is built on
- // being able to retrieve the correct conflict graph, which is associated
- // with the wrong task, but at least consistently, SO LEAVE IT BUT REALIZE
- // WHAT IS HAPPENING
-
- Set<FlatSESEEnterNode> parentSet = currentSESE.getSESEParent();
- for (Iterator iterator = parentSet.iterator(); iterator.hasNext();) {
- FlatSESEEnterNode parent = (FlatSESEEnterNode) iterator.next();
- conflictGraph = sese2conflictGraph.get(parent);
- if (conflictGraph == null) {
- conflictGraph = new ConflictGraph(state);
- }
+ case FKind.FlatSetFieldNode:
+ case FKind.FlatSetElementNode: {
- conflictGraph.addStallSite(taint2Effects, lhs);
- if (conflictGraph.id2cn.size() > 0) {
- sese2conflictGraph.put(parent, 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();
}
+ conflictGraph.addStallSite(taint2Effects, rhs, cd);
+ conflictGraph.addStallSite(taint2Effects, lhs, cd);
}
+ break;
- }
+ case FKind.FlatCall: {
+ FlatCall fc = (FlatCall) fn;
+ lhs = fc.getThis();
+ conflictGraph.addStallSite(taint2Effects, lhs, cd);
+ }
break;
- }
+ }
+ if (conflictGraph.id2cn.size() > 0) {
+ sese2conflictGraph.put(currentSESE, conflictGraph);
+ }
+ }
}
private void calculateConflicts(Set<FlatNew> sitesToFlag, boolean useReachInfo) {
+
// decide fine-grain edge or coarse-grain edge among all vertexes by
// pair-wise comparison
Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
while (seseIter.hasNext()) {
FlatSESEEnterNode sese = (FlatSESEEnterNode) seseIter.next();
ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
-// System.out.println("# CALCULATING SESE CONFLICT="+sese);
+
if (useReachInfo) {
// clear current conflict before recalculating with reachability info
conflictGraph.clearAllConflictEdge();
}
}
+ // 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<Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
- for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
- Entry<FlatNode, ConflictGraph> graphEntry = (Entry<FlatNode, ConflictGraph>) iterator.next();
+ // for every conflict graph, generate a set of memory queues
+ // (called SESELock in this code!) to cover the graph
+ Set<Map.Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
+ for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext(); ) {
+ Map.Entry<FlatNode, ConflictGraph> graphEntry =
+ (Map.Entry<FlatNode, ConflictGraph>)iterator.next();
FlatNode sese = graphEntry.getKey();
ConflictGraph conflictGraph = graphEntry.getValue();
calculateCovering(conflictGraph);
HashSet<SESELock> lockSet = new HashSet<SESELock>();
Set<ConflictEdge> 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);
changed = false;
- for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) {
+ for (Iterator iterator = fineToCover.iterator(); iterator.hasNext(); ) {
int type;
ConflictEdge edge = (ConflictEdge) iterator.next();
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) {
seseLock.addEdge(edge);
Set<ConflictEdge> 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
}
- break;// exit iterator loop
+ break; // exit iterator loop
}
}
} while (changed);
- HashSet<ConflictEdge> notCovered=new HashSet<ConflictEdge>();
+ HashSet<ConflictEdge> notCovered = new HashSet<ConflictEdge>();
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) {
// and it is not parent
type = ConflictNode.SCC;
} else {
- if(state.RCR){
+ if (state.RCR) {
type = ConflictNode.PARENT_COARSE;
- }else{
+ } else {
type = ConflictNode.PARENT_WRITE;
}
}
seseLock.addConflictNode(edge.getVertexU(), type);
} else {
if (edge.getVertexU().isStallSiteNode()) {
- if(state.RCR){
+ if (state.RCR) {
type = ConflictNode.PARENT_COARSE;
- }else{
+ } else {
if (edge.getVertexU().getWriteEffectSet().isEmpty()) {
type = ConflictNode.PARENT_READ;
} else {
// and it is not parent
type = ConflictNode.SCC;
} else {
- if(state.RCR){
+ if (state.RCR) {
type = ConflictNode.PARENT_COARSE;
- }else{
+ } else {
type = ConflictNode.PARENT_WRITE;
}
}
seseLock.addConflictNode(edge.getVertexV(), type);
} else {
if (edge.getVertexV().isStallSiteNode()) {
- if(state.RCR){
+ if (state.RCR) {
type = ConflictNode.PARENT_COARSE;
- }else{
+ } else {
if (edge.getVertexV().getWriteEffectSet().isEmpty()) {
type = ConflictNode.PARENT_READ;
} else {
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)) {
// this case can't be covered by this queue
coarseToCover.remove(edge);
break;
}
-
+
if (seseLock.hasSelfCoarseEdge(newNode)) {
// SCC
if (newNode.isStallSiteNode()) {
seseLock.addEdge(edge);
Set<ConflictEdge> 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
}
}
- break;// exit iterator loop
+ break; // exit iterator loop
}
}
return rblockRel.getMainSESE();
}
+ public FlatSESEEnterNode getCallerProxySESE() {
+ return rblockRel.getCallerProxySESE();
+ }
+
+ public Set<FlatSESEEnterNode> getPossibleExecutingRBlocks(FlatNode fn) {
+ return rblockRel.getPossibleExecutingRBlocks(fn);
+ }
+
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");
+ 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<Descriptor> methItr = disjointAnalysisTaints.getDescriptorsToAnalyze().iterator();
+ Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
while (methItr.hasNext()) {
- MethodDescriptor md = (MethodDescriptor) methItr.next();
+ 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("\n\nLive-In, Root View\n------------------\n" + fm.printMethod(livenessRootView));
+ bw.write("Dynamic vars to manage:\n " + getContextTaskNames(fm).getDynamicVarSet());
+
+ 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<FlatSESEEnterNode> rootItr = rblockRel.getRootSESEs().iterator();
+ bw.write("SESE Local Hierarchy\n--------------\n");
+ Iterator<FlatSESEEnterNode> 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 {
+ throws java.io.IOException {
for (int i = 0; i < depth; ++i) {
bw.write(" ");
}
bw.write("- " + fsen.getPrettyIdentifier() + "\n");
- Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
+ Iterator<FlatSESEEnterNode> childItr = fsen.getLocalChildren().iterator();
while (childItr.hasNext()) {
FlatSESEEnterNode fsenChild = childItr.next();
printSESEHierarchyTree(bw, fsenChild, depth + 1);
private void printSESEInfo(BufferedWriter bw) throws java.io.IOException {
bw.write("\nSESE info\n-------------\n");
- Iterator<FlatSESEEnterNode> 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);
- }
- }
- }
+ Iterator<FlatSESEEnterNode> fsenItr = rblockRel.getAllSESEs().iterator();
+ while (fsenItr.hasNext()) {
+ FlatSESEEnterNode fsen = fsenItr.next();
- public DisjointAnalysis getDisjointAnalysis() {
- return disjointAnalysisTaints;
- }
-
- private void printSESEInfoTree(BufferedWriter bw, FlatSESEEnterNode fsen)
- throws java.io.IOException {
-
- if (!fsen.getIsCallerSESEplaceholder()) {
bw.write("SESE " + fsen.getPrettyIdentifier());
- if( fsen.getIsLeafSESE() ) {
+ if (fsen.getIsLeafSESE()) {
bw.write(" (leaf)");
}
bw.write(" {\n");
}
}
- bw.write(" Dynamic vars to manage: " + fsen.getDynamicVarSet() + "\n");
+ bw.write(" Dynamic vars to manage: " + getContextTaskNames(fsen).getDynamicVarSet() + "\n");
bw.write(" out-set: " + fsen.getOutVarSet() + "\n");
- bw.write("}\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");
+ }
+ }
- Iterator<FlatSESEEnterNode> 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");
}
}
-
}