import IR.*;
import IR.Flat.*;
-
public class OoOJavaAnalysis {
// data from the compiler
private State state;
private TypeUtil typeUtil;
private CallGraph callGraph;
+ private Liveness liveness;
private RBlockRelationAnalysis rblockRel;
private HeapAnalysis disjointAnalysisTaints;
private DisjointAnalysis disjointAnalysisReach;
Liveness liveness,
ArrayReferencees arrayReferencees ) {
- double timeStartAnalysis = (double) System.nanoTime();
-
- this.state = state;
- this.typeUtil = typeUtil;
- this.callGraph = callGraph;
+ State.logEvent("Starting OoOJavaAnalysis");
+ this.state = state;
+ this.typeUtil = typeUtil;
+ this.callGraph = callGraph;
+ this.liveness = liveness;
this.maxSESEage = state.OOO_MAXSESEAGE;
livenessGlobalView = new Hashtable<FlatNode, Set<TempDescriptor>>();
descriptorsToAnalyze.add(mdSourceEntry);
+
// 0th pass, setup a useful mapping of any flat node to the
// flat method it is a part of
Iterator<MethodDescriptor> methItr = descriptorsToAnalyze.iterator();
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);
VarSrcTokTable.rblockRel = rblockRel;
- // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
- methItr = descriptorsToAnalyze.iterator();
- while (methItr.hasNext()) {
- Descriptor d = methItr.next();
- FlatMethod fm = state.getMethodFlat(d);
+ State.logEvent("OoOJavaAnalysis 1st pass completed");
- // note we can't use the general liveness analysis already in
- // the compiler because this analysis is task-aware
- livenessAnalysisBackward(fm);
+
+ // 2nd pass, liveness, in-set out-set (no virtual reads yet!)
+ Iterator<FlatSESEEnterNode> seseItr = rblockRel.getLocalRootSESEs().iterator();
+ while (seseItr.hasNext()) {
+ FlatSESEEnterNode sese = seseItr.next();
+ livenessAnalysisBackward(sese);
}
+
+
+ State.logEvent("OoOJavaAnalysis 2nd pass completed");
// 3rd pass, variable analysis
- 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);
+ 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
- methItr = descriptorsToAnalyze.iterator();
- while (methItr.hasNext()) {
- Descriptor d = methItr.next();
- FlatMethod fm = state.getMethodFlat(d);
- livenessAnalysisBackward(fm);
+ 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
if (state.POINTER) {
- disjointAnalysisTaints = new Pointer(state, typeUtil, callGraph, rblockRel);
+ disjointAnalysisTaints = new Pointer(state, typeUtil, callGraph, rblockRel, liveness, buildStateMachines);
((Pointer)disjointAnalysisTaints).doAnalysis();
} else
disjointAnalysisTaints =
rblockRel, buildStateMachines,
true ); // suppress output--this is an intermediate pass
+ 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);
}
-
+ 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
arrayReferencees, sitesToFlag,
null, // don't do effects analysis again!
null, // no BuildStateMachines needed
- false // don't suppress progress output
+ !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,
// 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 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
FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
fwdvn.spliceIntoIR();
}
-
+ State.logEvent("OoOJavaAnalysis 13th pass completed");
if (state.OOODEBUG) {
try {
writeConflictGraph();
} catch (IOException e) {}
}
-
+ State.logEvent("OoOJavaAnalysis completed");
}
}
- private void livenessAnalysisBackward(FlatMethod fm) {
+ private void livenessAnalysisBackward(FlatSESEEnterNode fsen) {
// flow backward across nodes to compute liveness, and
// take special care with sese enter/exit nodes that
// alter this from normal liveness analysis
Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
- flatNodesToVisit.add( fm.getFlatExit() );
+// flatNodesToVisit.add( fm.getFlatExit() );
+ flatNodesToVisit.add(fsen.getFlatExit());
while( !flatNodesToVisit.isEmpty() ) {
FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
// if a new result, schedule backward nodes for analysis
if( !curr.equals( prev ) ) {
- livenessGlobalView.put( fn, curr );
- for( int i = 0; i < fn.numPrev(); i++ ) {
- FlatNode nn = fn.getPrev( i );
- flatNodesToVisit.add( nn );
- }
+ if(fn!=fsen){
+ livenessGlobalView.put( fn, curr );
+ for( int i = 0; i < fn.numPrev(); i++ ) {
+ FlatNode nn = fn.getPrev( i );
+ flatNodesToVisit.add( nn );
+ }
+ }
}
}
}
// be live-out at the task's exit (and therefore should
// go in the task's out-var set)
FlatSESEExitNode fsexn = fsen.getFlatExit();
- Set<TempDescriptor> livetemps = livenessGlobalView.get( fsexn );
+ //note: liveness analysis can have corresponding decisions
+ Set<TempDescriptor> livetemps= liveness.getLiveInTemps(fsen.getfmEnclosing(), fsexn);
if( livetemps != null && livetemps.contains( writeTemps[i] ) ) {
fsen.addOutVar( writeTemps[i] );
}
// 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 = livenessGlobalView.get(fn);
+ Set<TempDescriptor> liveVars = liveness.getLiveInTemps(fsen.getfmEnclosing(),
+ fn);
+
Set<TempDescriptor> fsenVirtReads =
vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen,
liveVars);
}
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
}
codePlans_nodeActions(fm, fn,
- dotSTlive, dotSTtable, dotSTnotAvailSet,
+ dotSTtable, dotSTnotAvailSet,
currentSESE);
for (int i = 0; i < fn.numNext(); i++) {
private void codePlans_nodeActions(FlatMethod fm,
FlatNode fn,
- Set<TempDescriptor> liveSetIn,
VarSrcTokTable vstTableIn,
Set<TempDescriptor> notAvailSetIn,
FlatSESEEnterNode currentSESE) {
// variable and the child needs space in its SESE record
if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) {
fsen.addDynamicInVar(inVar);
- addDynamicVar( fsen, fm, 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);
case FKind.FlatSESEExitNode: {
FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
- //TODO! Shouldn't there be a code plan for task exit
- // where the exiting task calculates whether its own
- // siblings need variables from its children, so the
- // exiter should copy those variables into its own out-set
- // and make the available?
+
+ // 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;
case FKind.FlatOpNode: {
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++) {
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);
}
}
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
+ // 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;
+ }
+
+
+ if( fsenDoingTracking.getPrettyIdentifier().equals( "workLoop" ) ) {
+ System.out.println( "\n\nWriteDyn for "+fsenDoingTracking+" at "+fn );
+ }
+
+
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 = livenessGlobalView.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()) {
+
+
+ if( fsenDoingTracking.getPrettyIdentifier().equals( "workLoop" ) ) {
+ System.out.println( " found newly dyn vars: "+readyOrStatic2dynamicSet );
+ }
+
+
// 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);
+ fwdvn = new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, fsenDoingTracking);
wdvNodesToSpliceIn.put(fe, fwdvn);
} else {
fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet);
}
}
}
+
+ if( fsenDoingTracking.getPrettyIdentifier().equals( "workLoop" ) ) {
+ System.out.println( "WriteDyn for "+fsenDoingTracking+" at "+fn+" is done\n\n" );
+ }
}
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
// otherwise the code context is a task body
fnContext = fsen;
}
+ //fnContext=fm;
ContextTaskNames ctn = fn2contextTaskNames.get( fnContext );
if( ctn == null ) {
ctn.addDynamicVar( var );
fn2contextTaskNames.put( fnContext, ctn );
+
}
private void addNeededStaticName( FlatSESEEnterNode fsen,
// effects between heap roots, so it is smart to compute all of
// this together
public void pruneMachinesAndFindWeaklyConnectedExaminers() {
-
- /*
- // TODO, calcualte the set of taints that lead to conflicts (for which
- // traversers must be built...)
-
- EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
-
- // visit every conflict graph once, so iterate through the
- // the non-leaf tasks to find them all
- Set<FlatSESEEnterNode> allSESEs = rblockRel.getAllSESEs();
- for( Iterator allItr = allSESEs.iterator(); allItr.hasNext(); ) {
-
- FlatSESEEnterNode parent = (FlatSESEEnterNode) allItr.next();
- if( parent.getIsLeafSESE() ) {
- continue;
- }
-
- ConflictGraph conflictGraph = sese2conflictGraph.get( parent );
- assert conflictGraph != null;
-
- // from the conflict graph we want to extract all conflicting effects
- // and use them to identify (1) weakly connected heap examiners and
- // (2) states/examiner nodes with a conflicting effect that will later
- // support the examiner pruning process
- Hashtable<Taint, Set<Effect>> conflicts = conflictGraph.getConflictEffectSet( fsen ) );
-
- }
- */
+ ProcessStateMachines psm=new ProcessStateMachines(buildStateMachines, rblockRel);
+ psm.doProcess();
+ buildStateMachines.writeStateMachines("pruned");
}
bw.write(" Dynamic vars to manage: " + getContextTaskNames( fsen ).getDynamicVarSet() + "\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(" local parent: " + fsen.getLocalParent() + "\n");
bw.write(" local children: " + fsen.getLocalChildren() + "\n");
projects / IRC.git / blobdiff