public class MLPAnalysis {
// data from the compiler
- private State state;
- private TypeUtil typeUtil;
- private CallGraph callGraph;
+ private State state;
+ private TypeUtil typeUtil;
+ private CallGraph callGraph;
private OwnershipAnalysis ownAnalysis;
- private SESENode rootTree;
- private FlatSESEEnterNode rootSESE;
- private FlatSESEExitNode rootExit;
+ // an implicit SESE is automatically spliced into
+ // the IR graph around the C main before this analysis--it
+ // is nothing special except that we can make assumptions
+ // about it, such as the whole program ends when it ends
+ private FlatSESEEnterNode mainSESE;
+
+ // SESEs that are the root of an SESE tree belong to this
+ // set--the main SESE is always a root, statically SESEs
+ // inside methods are a root because we don't know how they
+ // will fit into the runtime tree of SESEs
+ private Set<FlatSESEEnterNode> rootSESEs;
+
+ // simply a set of every reachable SESE in the program, not
+ // including caller placeholder SESEs
private Set<FlatSESEEnterNode> allSESEs;
+
+ // A mapping of flat nodes to the stack of SESEs for that node, where
+ // an SESE is the child of the SESE directly below it on the stack.
+ // These stacks do not reflect the heirarchy over methods calls--whenever
+ // there is an empty stack it means all variables are available.
private Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks;
+
private Hashtable< FlatNode, Set<TempDescriptor> > livenessRootView;
private Hashtable< FlatNode, Set<TempDescriptor> > livenessVirtualReads;
private Hashtable< FlatNode, VarSrcTokTable > variableResults;
private Hashtable< FlatNode, Set<TempDescriptor> > notAvailableResults;
private Hashtable< FlatNode, CodePlan > codePlans;
+ private Hashtable< FlatEdge, FlatWriteDynamicVarNode > wdvNodesToSpliceIn;
+
+ public static int maxSESEage = -1;
+
// use these methods in BuildCode to have access to analysis results
+ public FlatSESEEnterNode getMainSESE() {
+ return mainSESE;
+ }
+
+ public Set<FlatSESEEnterNode> getRootSESEs() {
+ return rootSESEs;
+ }
+
public Set<FlatSESEEnterNode> getAllSESEs() {
return allSESEs;
}
+ public int getMaxSESEage() {
+ return maxSESEage;
+ }
+
+ // may be null
public CodePlan getCodePlan( FlatNode fn ) {
CodePlan cp = codePlans.get( fn );
- assert cp != null;
return cp;
}
this.typeUtil = tu;
this.callGraph = callGraph;
this.ownAnalysis = ownAnalysis;
+ this.maxSESEage = state.MLP_MAXSESEAGE;
- // initialize analysis data structures
- allSESEs = new HashSet<FlatSESEEnterNode>();
+ rootSESEs = new HashSet<FlatSESEEnterNode>();
+ allSESEs = new HashSet<FlatSESEEnterNode>();
- seseStacks = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
+ seseStacks = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
+ livenessRootView = 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 >();
- // build an implicit root SESE to wrap contents of main method
- rootTree = new SESENode( "root" );
- rootSESE = new FlatSESEEnterNode( rootTree );
- rootExit = new FlatSESEExitNode ( rootTree );
- rootSESE.setFlatExit ( rootExit );
- rootExit.setFlatEnter( rootSESE );
+ FlatMethod fmMain = state.getMethodFlat( typeUtil.getMain() );
- FlatMethod fmMain = state.getMethodFlat( tu.getMain() );
+ mainSESE = (FlatSESEEnterNode) fmMain.getNext(0);
+ mainSESE.setfmEnclosing( fmMain );
+ mainSESE.setmdEnclosing( fmMain.getMethod() );
+ mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
// 1st pass
// 2nd pass, results are saved in FlatSESEEnterNode, so
// intermediate results, for safety, are discarded
- livenessAnalysisBackward( rootSESE, true, null, fmMain.getFlatExit() );
+ Iterator<FlatSESEEnterNode> rootItr = rootSESEs.iterator();
+ while( rootItr.hasNext() ) {
+ FlatSESEEnterNode root = rootItr.next();
+ livenessAnalysisBackward( root,
+ true,
+ null );
+ }
// 3rd pass
variableAnalysisForward( fm );
}
-
// 4th pass, compute liveness contribution from
// virtual reads discovered in variable pass
- livenessAnalysisBackward( rootSESE, true, null, fmMain.getFlatExit() );
+ rootItr = rootSESEs.iterator();
+ while( rootItr.hasNext() ) {
+ FlatSESEEnterNode root = rootItr.next();
+ livenessAnalysisBackward( root,
+ true,
+ null );
+ }
+ /*
+ SOMETHING IS WRONG WITH THIS, DON'T USE IT UNTIL IT CAN BE FIXED
+
// 5th pass
methItr = ownAnalysis.descriptorsToAnalyze.iterator();
while( methItr.hasNext() ) {
Descriptor d = methItr.next();
FlatMethod fm = state.getMethodFlat( d );
+ // prune variable results in one traversal
+ // by removing reference variables that are not live
+ pruneVariableResultsWithLiveness( fm );
+ }
+ */
+
+
+ // 6th pass
+ methItr = ownAnalysis.descriptorsToAnalyze.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 );
}
- // 5th pass
+ // 7th pass
methItr = ownAnalysis.descriptorsToAnalyze.iterator();
while( methItr.hasNext() ) {
Descriptor d = methItr.next();
FlatMethod fm = state.getMethodFlat( d );
// compute a plan for code injections
- computeStallsForward( fm );
+ codePlansForward( fm );
}
- if( state.MLPDEBUG ) {
- System.out.println( "" );
- //printSESEHierarchy();
- //printSESELiveness();
- //System.out.println( fmMain.printMethod( livenessRootView ) );
- //System.out.println( fmMain.printMethod( variableResults ) );
- //System.out.println( fmMain.printMethod( notAvailableResults ) );
- System.out.println( "CODE PLANS\n"+fmMain.printMethod( codePlans ) );
+ // 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();
+ FlatWriteDynamicVarNode fwdvn = (FlatWriteDynamicVarNode) me.getValue();
+ fwdvn.spliceIntoIR();
}
double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
String treport = String.format( "The mlp analysis took %.3f sec.", dt );
System.out.println( treport );
+
+ if( state.MLPDEBUG ) {
+ try {
+ writeReports( treport );
+ } catch( IOException e ) {}
+ }
}
Set<FlatNode> visited = new HashSet<FlatNode>();
Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
- seseStackFirst.push( rootSESE );
seseStacks.put( fm, seseStackFirst );
while( !flatNodesToVisit.isEmpty() ) {
case FKind.FlatSESEEnterNode: {
FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
- allSESEs.add( fsen );
- fsen.setEnclosingFlatMeth( fm );
+ if( !fsen.getIsCallerSESEplaceholder() ) {
+ allSESEs.add( fsen );
+ }
+
+ fsen.setfmEnclosing( fm );
+ fsen.setmdEnclosing( fm.getMethod() );
+ fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
+
+ if( seseStack.empty() ) {
+ rootSESEs.add( fsen );
+ fsen.setParent( null );
+ } else {
+ seseStack.peek().addChild( fsen );
+ fsen.setParent( seseStack.peek() );
+ }
- assert !seseStack.empty();
- seseStack.peek().addChild( fsen );
- fsen.setParent( seseStack.peek() );
seseStack.push( fsen );
} break;
case FKind.FlatReturnNode: {
FlatReturnNode frn = (FlatReturnNode) fn;
- if( !seseStack.empty() &&
- !seseStack.peek().equals( rootSESE ) ) {
- throw new Error( "Error: return statement enclosed within "+seseStack.peek() );
+ if( !seseStack.empty() &&
+ !seseStack.peek().getIsCallerSESEplaceholder()
+ ) {
+ throw new Error( "Error: return statement enclosed within SESE "+
+ seseStack.peek().getPrettyIdentifier() );
}
} break;
}
}
- private void printSESEHierarchy() {
- // our forest is actually a tree now that
- // there is an implicit root SESE
- printSESEHierarchyTree( rootSESE, 0 );
- System.out.println( "" );
- }
-
- private void printSESEHierarchyTree( FlatSESEEnterNode fsen, int depth ) {
- for( int i = 0; i < depth; ++i ) {
- System.out.print( " " );
- }
- System.out.println( fsen.getPrettyIdentifier() );
-
- Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
- while( childItr.hasNext() ) {
- FlatSESEEnterNode fsenChild = childItr.next();
- printSESEHierarchyTree( fsenChild, depth + 1 );
- }
- }
-
private void livenessAnalysisBackward( FlatSESEEnterNode fsen,
boolean toplevel,
- Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout,
- FlatExit fexit ) {
+ 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
// because child SESE enter node has all necessary info
Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
- FlatSESEExitNode fsexn = fsen.getFlatExit();
- if (toplevel) {
- //handle root SESE
- flatNodesToVisit.add( fexit );
- } else
- flatNodesToVisit.add( fsexn );
- Hashtable<FlatNode, Set<TempDescriptor>> livenessResults=new Hashtable<FlatNode, Set<TempDescriptor>>();
+ if( toplevel ) {
+ flatNodesToVisit.add( fsen.getfmEnclosing().getFlatExit() );
+ } else {
+ flatNodesToVisit.add( fsen.getFlatExit() );
+ }
+
+ Hashtable<FlatNode, Set<TempDescriptor>> livenessResults =
+ new Hashtable< FlatNode, Set<TempDescriptor> >();
+
+ if( toplevel ) {
+ liveout = new Hashtable< FlatSESEExitNode, Set<TempDescriptor> >();
+ }
- if (toplevel==true)
- liveout=new Hashtable<FlatSESEExitNode, Set<TempDescriptor>>();
-
while( !flatNodesToVisit.isEmpty() ) {
FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
flatNodesToVisit.remove( fn );
u.addAll( s );
}
}
-
+
Set<TempDescriptor> curr = liveness_nodeActions( fn, u, fsen, toplevel, liveout);
// if a new result, schedule backward nodes for analysis
- if(!curr.equals(prev)) {
+ if( !curr.equals( prev ) ) {
livenessResults.put( fn, curr );
// don't flow backwards past current SESE enter
// remember liveness per node from the root view as the
// global liveness of variables for later passes to use
- if( toplevel == true ) {
- livenessRootView = livenessResults;
+ 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, null);
+ livenessAnalysisBackward( fsenChild, false, liveout );
}
}
Set<TempDescriptor> liveIn,
FlatSESEEnterNode currentSESE,
boolean toplevel,
- Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout ) {
-
+ Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout
+ ) {
switch( fn.kind() ) {
-
+
case FKind.FlatSESEExitNode:
- if (toplevel==true) {
- FlatSESEExitNode exitn=(FlatSESEExitNode) fn;
- //update liveout set for FlatSESEExitNode
- if (!liveout.containsKey(exitn))
- liveout.put(exitn, new HashSet<TempDescriptor>());
- liveout.get(exitn).addAll(liveIn);
+ if( toplevel ) {
+ FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
+ if( !liveout.containsKey( fsexn ) ) {
+ liveout.put( fsexn, new HashSet<TempDescriptor>() );
+ }
+ liveout.get( fsexn ).addAll( liveIn );
}
// no break, sese exits should also execute default actions
TempDescriptor [] writeTemps = fn.writesTemps();
for( int i = 0; i < writeTemps.length; ++i ) {
liveIn.remove( writeTemps[i] );
-
- if (!toplevel) {
- FlatSESEExitNode exitnode=currentSESE.getFlatExit();
- Set<TempDescriptor> livetemps=liveout.get(exitnode);
- if (livetemps.contains(writeTemps[i])) {
- //write to a live out temp...
- //need to put in SESE liveout set
- currentSESE.addOutVar(writeTemps[i]);
- }
+
+ if( !toplevel ) {
+ FlatSESEExitNode fsexn = currentSESE.getFlatExit();
+ Set<TempDescriptor> livetemps = liveout.get( 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] );
+ }
}
}
for( int i = 0; i < readTemps.length; ++i ) {
liveIn.add( readTemps[i] );
}
-
+
Set<TempDescriptor> virtualReadTemps = livenessVirtualReads.get( fn );
if( virtualReadTemps != null ) {
- Iterator<TempDescriptor> vrItr = virtualReadTemps.iterator();
- while( vrItr.hasNext() ) {
- TempDescriptor vrt = vrItr.next();
- liveIn.add( vrt );
- }
- }
+ liveIn.addAll( virtualReadTemps );
+ }
+
} break;
} // end switch
return liveIn;
}
- private void printSESELiveness() {
- // our forest is actually a tree now that
- // there is an implicit root SESE
- printSESELivenessTree( rootSESE );
- System.out.println( "" );
- }
-
- private void printSESELivenessTree( FlatSESEEnterNode fsen ) {
-
- System.out.println( "SESE "+fsen.getPrettyIdentifier()+" has in-set:" );
- Iterator<TempDescriptor> tItr = fsen.getInVarSet().iterator();
- while( tItr.hasNext() ) {
- System.out.println( " "+tItr.next() );
- }
- System.out.println( "and out-set:" );
- tItr = fsen.getOutVarSet().iterator();
- while( tItr.hasNext() ) {
- System.out.println( " "+tItr.next() );
- }
- System.out.println( "" );
-
-
- Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
- while( childItr.hasNext() ) {
- FlatSESEEnterNode fsenChild = childItr.next();
- printSESELivenessTree( fsenChild );
- }
- }
-
private void variableAnalysisForward( FlatMethod fm ) {
-
+
Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
flatNodesToVisit.add( fm );
VarSrcTokTable prev = variableResults.get( fn );
// merge sets from control flow joins
- VarSrcTokTable inUnion = new VarSrcTokTable();
+ VarSrcTokTable curr = new VarSrcTokTable();
for( int i = 0; i < fn.numPrev(); i++ ) {
FlatNode nn = fn.getPrev( i );
VarSrcTokTable incoming = variableResults.get( nn );
- inUnion.merge( incoming );
+ curr.merge( incoming );
}
- VarSrcTokTable curr = variable_nodeActions( fn, inUnion, seseStack.peek() );
+ if( !seseStack.empty() ) {
+ variable_nodeActions( fn, curr, seseStack.peek() );
+ }
// if a new result, schedule forward nodes for analysis
if( !curr.equals( prev ) ) {
}
}
- private VarSrcTokTable variable_nodeActions( FlatNode fn,
- VarSrcTokTable vstTable,
- FlatSESEEnterNode currentSESE ) {
+ private void variable_nodeActions( FlatNode fn,
+ VarSrcTokTable vstTable,
+ FlatSESEEnterNode currentSESE ) {
switch( fn.kind() ) {
case FKind.FlatSESEEnterNode: {
FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
assert fsen.equals( currentSESE );
+
vstTable.age( currentSESE );
vstTable.assertConsistency();
} break;
FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
FlatSESEEnterNode fsen = fsexn.getFlatEnter();
assert currentSESE.getChildren().contains( fsen );
+
vstTable.remapChildTokens( fsen );
+
+ // liveness virtual reads are things that might be
+ // 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> fsenVirtReads = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens( fsen, liveVars );
+ Set<TempDescriptor> fsenVirtReadsOld = livenessVirtualReads.get( fn );
+ if( fsenVirtReadsOld != null ) {
+ fsenVirtReads.addAll( fsenVirtReadsOld );
+ }
+ livenessVirtualReads.put( fn, fsenVirtReads );
+
- Set<TempDescriptor> liveIn = currentSESE.getInVarSet();
- Set<TempDescriptor> virLiveIn = vstTable.removeParentAndSiblingTokens( fsen, liveIn );
- Set<TempDescriptor> virLiveInOld = livenessVirtualReads.get( fn );
- if( virLiveInOld != null ) {
- virLiveIn.addAll( virLiveInOld );
+ // then all child out-set tokens are guaranteed
+ // to be filled in, so clobber those entries with
+ // the latest, clean sources
+ Iterator<TempDescriptor> outVarItr = fsen.getOutVarSet().iterator();
+ while( outVarItr.hasNext() ) {
+ TempDescriptor outVar = outVarItr.next();
+ HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
+ ts.add( outVar );
+ VariableSourceToken vst =
+ new VariableSourceToken( ts,
+ fsen,
+ new Integer( 0 ),
+ outVar
+ );
+ vstTable.remove( outVar );
+ vstTable.add( vst );
}
- livenessVirtualReads.put( fn, virLiveIn );
vstTable.assertConsistency();
+
} break;
case FKind.FlatOpNode: {
if( fon.getOp().getOp() == Operation.ASSIGN ) {
TempDescriptor lhs = fon.getDest();
- TempDescriptor rhs = fon.getLeft();
+ TempDescriptor rhs = fon.getLeft();
vstTable.remove( lhs );
HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
ts.add( lhs );
- // if this is from a child, keep the source information
- if( currentSESE.getChildren().contains( vst.getSESE() ) ) {
- forAddition.add( new VariableSourceToken( ts,
- vst.getSESE(),
- vst.getAge(),
- vst.getAddrVar()
- )
- );
-
- // otherwise, it's our or an ancestor's token so we
- // can assume we have everything we need
- } else {
- forAddition.add( new VariableSourceToken( ts,
- currentSESE,
- new Integer( 0 ),
- lhs
- )
- );
- }
+ if( currentSESE.getChildren().contains( vst.getSESE() ) ) {
+ // if the source comes from a child, copy it over
+ forAddition.add( new VariableSourceToken( ts,
+ vst.getSESE(),
+ vst.getAge(),
+ vst.getAddrVar()
+ )
+ );
+ } else {
+ // otherwise, stamp it as us as the source
+ forAddition.add( new VariableSourceToken( ts,
+ currentSESE,
+ new Integer( 0 ),
+ lhs
+ )
+ );
+ }
}
vstTable.addAll( forAddition );
break;
}
-
vstTable.remove( writeTemps[0] );
HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
} break;
} // end switch
+ }
+
+
+ private void pruneVariableResultsWithLiveness( FlatMethod fm ) {
+
+ // start from flat method top, visit every node in
+ // method exactly once
+ Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
+ flatNodesToVisit.add( fm );
+
+ Set<FlatNode> visited = new HashSet<FlatNode>();
+
+ while( !flatNodesToVisit.isEmpty() ) {
+ Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
+ FlatNode fn = fnItr.next();
+
+ flatNodesToVisit.remove( fn );
+ visited.add( fn );
- return vstTable;
+ Set<TempDescriptor> rootLiveSet = livenessRootView.get( fn );
+ VarSrcTokTable vstTable = variableResults.get( fn );
+
+ vstTable.pruneByLiveness( rootLiveSet );
+
+ for( int i = 0; i < fn.numNext(); i++ ) {
+ FlatNode nn = fn.getNext( i );
+
+ if( !visited.contains( nn ) ) {
+ flatNodesToVisit.add( nn );
+ }
+ }
+ }
}
Set<TempDescriptor> prev = notAvailableResults.get( fn );
- Set<TempDescriptor> inUnion = new HashSet<TempDescriptor>();
+ Set<TempDescriptor> curr = new HashSet<TempDescriptor>();
for( int i = 0; i < fn.numPrev(); i++ ) {
FlatNode nn = fn.getPrev( i );
Set<TempDescriptor> notAvailIn = notAvailableResults.get( nn );
if( notAvailIn != null ) {
- inUnion.addAll( notAvailIn );
+ curr.addAll( notAvailIn );
}
}
-
- Set<TempDescriptor> curr = notAvailable_nodeActions( fn, inUnion, seseStack.peek() );
+
+ if( !seseStack.empty() ) {
+ notAvailable_nodeActions( fn, curr, seseStack.peek() );
+ }
// if a new result, schedule forward nodes for analysis
if( !curr.equals( prev ) ) {
}
}
- private Set<TempDescriptor> notAvailable_nodeActions( FlatNode fn,
- Set<TempDescriptor> notAvailSet,
- FlatSESEEnterNode currentSESE ) {
+ private void notAvailable_nodeActions( FlatNode fn,
+ Set<TempDescriptor> notAvailSet,
+ FlatSESEEnterNode currentSESE ) {
// any temps that are removed from the not available set
// at this node should be marked in this node's code plan
FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
FlatSESEEnterNode fsen = fsexn.getFlatEnter();
assert currentSESE.getChildren().contains( fsen );
-
- Set<TempDescriptor> liveTemps = livenessRootView.get( fn );
- assert liveTemps != null;
-
- VarSrcTokTable vstTable = variableResults.get( fn );
- assert vstTable != null;
-
- Set<TempDescriptor> notAvailAtEnter = notAvailableResults.get( fsen );
- assert notAvailAtEnter != null;
-
- Iterator<TempDescriptor> tdItr = liveTemps.iterator();
- while( tdItr.hasNext() ) {
- TempDescriptor td = tdItr.next();
-
- if( vstTable.get( fsen, td ).size() > 0 ) {
- // there is at least one child token for this variable
- notAvailSet.add( td );
- continue;
- }
-
- if( notAvailAtEnter.contains( td ) ) {
- // wasn't available at enter, not available now
- notAvailSet.add( td );
- continue;
- }
- }
+ notAvailSet.addAll( fsen.getOutVarSet() );
} break;
+ case FKind.FlatMethod: {
+ notAvailSet.clear();
+ }
+
case FKind.FlatOpNode: {
FlatOpNode fon = (FlatOpNode) fn;
TempDescriptor rTemp = readTemps[i];
notAvailSet.remove( rTemp );
- // if this variable has exactly one source, mark everything
- // else from that source as available as well
- VarSrcTokTable table = variableResults.get( fn );
- Set<VariableSourceToken> srcs = table.get( rTemp );
+ // if this variable has exactly one source, potentially
+ // get other things from this source as well
+ VarSrcTokTable vstTable = variableResults.get( fn );
- if( srcs.size() == 1 ) {
- VariableSourceToken vst = srcs.iterator().next();
-
- Iterator<VariableSourceToken> availItr = table.get( vst.getSESE(),
- vst.getAge()
- ).iterator();
+ Integer srcType =
+ vstTable.getRefVarSrcType( rTemp,
+ currentSESE,
+ currentSESE.getParent() );
+
+ if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) {
+
+ VariableSourceToken vst = vstTable.get( rTemp ).iterator().next();
+
+ Iterator<VariableSourceToken> availItr = vstTable.get( vst.getSESE(),
+ vst.getAge()
+ ).iterator();
+
+ // look through things that are also available from same source
while( availItr.hasNext() ) {
VariableSourceToken vstAlsoAvail = availItr.next();
- notAvailSet.removeAll( vstAlsoAvail.getRefVars() );
+
+ Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
+ while( refVarItr.hasNext() ) {
+ TempDescriptor refVarAlso = refVarItr.next();
+
+ // if a variable is available from the same source, AND it ALSO
+ // only comes from one statically known source, mark it available
+ Integer srcTypeAlso =
+ vstTable.getRefVarSrcType( refVarAlso,
+ currentSESE,
+ currentSESE.getParent() );
+ if( srcTypeAlso.equals( VarSrcTokTable.SrcType_STATIC ) ) {
+ notAvailSet.remove( refVarAlso );
+ }
+ }
}
}
}
} break;
} // end switch
-
- return notAvailSet;
}
- private void computeStallsForward( FlatMethod fm ) {
+ private void codePlansForward( FlatMethod fm ) {
// start from flat method top, visit every node in
// method exactly once
}
}
- computeStalls_nodeActions( fn, dotSTtable, dotSTnotAvailSet, seseStack.peek() );
+ Set<TempDescriptor> dotSTlive = livenessRootView.get( fn );
+
+ if( !seseStack.empty() ) {
+ codePlans_nodeActions( fn,
+ dotSTlive,
+ dotSTtable,
+ dotSTnotAvailSet,
+ seseStack.peek()
+ );
+ }
for( int i = 0; i < fn.numNext(); i++ ) {
FlatNode nn = fn.getNext( i );
}
}
- private void computeStalls_nodeActions( FlatNode fn,
- VarSrcTokTable vstTable,
- Set<TempDescriptor> notAvailSet,
- FlatSESEEnterNode currentSESE ) {
- CodePlan plan = new CodePlan();
-
+ private void codePlans_nodeActions( FlatNode fn,
+ Set<TempDescriptor> liveSetIn,
+ VarSrcTokTable vstTableIn,
+ Set<TempDescriptor> notAvailSetIn,
+ FlatSESEEnterNode currentSESE ) {
+
+ CodePlan plan = new CodePlan( currentSESE);
switch( fn.kind() ) {
case FKind.FlatSESEEnterNode: {
FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
- plan.setSESEtoIssue( fsen );
+
+ // track the source types of the in-var set so generated
+ // code at this SESE issue can compute the number of
+ // dependencies properly
+ Iterator<TempDescriptor> inVarItr = fsen.getInVarSet().iterator();
+ while( inVarItr.hasNext() ) {
+ TempDescriptor inVar = inVarItr.next();
+ Integer srcType =
+ vstTableIn.getRefVarSrcType( inVar,
+ fsen,
+ fsen.getParent() );
+
+ // 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 = vstTableIn.get( inVar ).iterator().next();
+ 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: {
FlatOpNode fon = (FlatOpNode) fn;
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
+ // ask whether lhs and rhs sources are dynamic, static, etc.
+ Integer lhsSrcType
+ = vstTableIn.getRefVarSrcType( lhs,
+ currentSESE,
+ currentSESE.getParent() );
+
+ Integer rhsSrcType
+ = vstTableIn.getRefVarSrcType( rhs,
+ currentSESE,
+ currentSESE.getParent() );
+
+ 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;
// note that FlatOpNode's that aren't ASSIGN
// fall through to this default case
default: {
- // decide if we must stall for variables dereferenced at this node
- Set<VariableSourceToken> stallSet = vstTable.getStallSet( currentSESE );
+
+ // a node with no live set has nothing to stall for
+ if( liveSetIn == null ) {
+ break;
+ }
TempDescriptor[] readarray = fn.readsTemps();
for( int i = 0; i < readarray.length; i++ ) {
// ignore temps that are definitely available
// when considering to stall on it
- if( !notAvailSet.contains( readtmp ) ) {
+ if( !notAvailSetIn.contains( readtmp ) ) {
continue;
}
- Set<VariableSourceToken> readSet = vstTable.get( readtmp );
+ // check the source type of this variable
+ Integer srcType
+ = vstTableIn.getRefVarSrcType( readtmp,
+ currentSESE,
+ currentSESE.getParent() );
- //Two cases:
-
- //1) Multiple token/age pairs or unknown age: Stall for
- //dynamic name only.
-
+ if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) {
+ // 1) It is not clear statically where this variable will
+ // come from statically, 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.
- //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 = vstTableIn.get( readtmp ).iterator().next();
- //VarSrcTokTable table = variableResults.get( fn );
- //Set<VariableSourceToken> srcs = table.get( rTemp );
+ Iterator<VariableSourceToken> availItr =
+ vstTableIn.get( vst.getSESE(), vst.getAge() ).iterator();
- //XXXXXXXXXX: Note: We have to generate code to do these
- //copies in the codeplan. Note we should only copy the
- //variables that are live!
-
- /*
- if( srcs.size() == 1 ) {
- VariableSourceToken vst = srcs.iterator().next();
-
- Iterator<VariableSourceToken> availItr = table.get( vst.getSESE(),
- vst.getAge()
- ).iterator();
while( availItr.hasNext() ) {
VariableSourceToken vstAlsoAvail = availItr.next();
- notAvailSet.removeAll( vstAlsoAvail.getRefVars() );
- }
- }
- */
+ // only grab additional stuff that is live
+ Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
- // assert notAvailSet.containsAll( writeSet );
+ Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
+ while( refVarItr.hasNext() ) {
+ TempDescriptor refVar = refVarItr.next();
+ if( liveSetIn.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
- /*
- for( Iterator<VariableSourceToken> readit = readSet.iterator();
- readit.hasNext(); ) {
- VariableSourceToken vst = readit.next();
- if( stallSet.contains( vst ) ) {
- if( before == null ) {
- before = "**STALL for:";
- }
- before += "("+vst+" "+readtmp+")";
- }
- }
- */
}
} break;
-
+
} // end switch
- // if any variable at this node has a static source (exactly one sese)
- // but goes to a dynamic source at a next node, write its dynamic addr
- Set<VariableSourceToken> static2dynamicSet = new HashSet<VariableSourceToken>();
- for( int i = 0; i < fn.numNext(); i++ ) {
- FlatNode nn = fn.getNext( i );
- VarSrcTokTable nextVstTable = variableResults.get( nn );
- assert nextVstTable != null;
- static2dynamicSet.addAll( vstTable.getStatic2DynamicSet( nextVstTable ) );
- }
- /*
- Iterator<VariableSourceToken> vstItr = static2dynamicSet.iterator();
+ // 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
+ Set<VariableSourceToken> staticSet = vstTableIn.get();
+ Iterator<VariableSourceToken> vstItr = staticSet.iterator();
while( vstItr.hasNext() ) {
VariableSourceToken vst = vstItr.next();
- if( after == null ) {
- after = "** Write dynamic: ";
+
+ // placeholder source tokens are useful results, but
+ // the placeholder static name is never needed
+ if( vst.getSESE().getIsCallerSESEplaceholder() ) {
+ continue;
+ }
+
+ FlatSESEEnterNode sese = currentSESE;
+ while( sese != null ) {
+ sese.addNeededStaticName(
+ new SESEandAgePair( vst.getSESE(), vst.getAge() )
+ );
+ sese.mustTrackAtLeastAge( vst.getAge() );
+
+ sese = sese.getParent();
}
- after += "("+vst+")";
}
- */
+
codePlans.put( fn, plan );
+
+
+ // 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<TempDescriptor> nextLiveIn = livenessRootView.get( 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, VariableSourceToken> static2dynamicSet =
+ thisVstTable.getStatic2DynamicSet( nextVstTable,
+ nextLiveIn,
+ currentSESE,
+ currentSESE.getParent()
+ );
+
+ if( !static2dynamicSet.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,
+ static2dynamicSet,
+ currentSESE
+ );
+ wdvNodesToSpliceIn.put( fe, fwdvn );
+ } else {
+ fwdvn.addMoreVar2Src( static2dynamicSet );
+ }
+ }
+ }
+ }
+ }
+
+
+ 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 );
+ bw.close();
+
+ Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
+ while( methItr.hasNext() ) {
+ MethodDescriptor md = (MethodDescriptor) methItr.next();
+ FlatMethod fm = state.getMethodFlat( md );
+ bw = new BufferedWriter( new FileWriter( "mlpReport_"+
+ md.getClassMethodName()+
+ md.getSafeMethodDescriptor()+
+ ".txt" ) );
+ bw.write( "MLP Results for "+md+"\n-------------------\n");
+ bw.write( "\n\nLive-In, Root View\n------------------\n" +fm.printMethod( livenessRootView ) );
+ bw.write( "\n\nVariable Results-Out\n----------------\n" +fm.printMethod( variableResults ) );
+ bw.write( "\n\nNot Available Results-Out\n---------------------\n"+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 = rootSESEs.iterator();
+ while( rootItr.hasNext() ) {
+ FlatSESEEnterNode root = rootItr.next();
+ if( root.getIsCallerSESEplaceholder() ) {
+ if( !root.getChildren().isEmpty() ) {
+ printSESEHierarchyTree( bw, root, 0 );
+ }
+ } else {
+ 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( " " );
+ }
+ bw.write( "- "+fsen.getPrettyIdentifier()+"\n" );
+
+ Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().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 = rootSESEs.iterator();
+ while( rootItr.hasNext() ) {
+ FlatSESEEnterNode root = rootItr.next();
+ if( root.getIsCallerSESEplaceholder() ) {
+ if( !root.getChildren().isEmpty() ) {
+ printSESEInfoTree( bw, root );
+ }
+ } else {
+ printSESEInfoTree( bw, root );
+ }
+ }
+ }
+
+ private void printSESEInfoTree( BufferedWriter bw,
+ FlatSESEEnterNode fsen
+ ) throws java.io.IOException {
+
+ if( !fsen.getIsCallerSESEplaceholder() ) {
+ bw.write( "SESE "+fsen.getPrettyIdentifier()+" {\n" );
+
+ bw.write( " in-set: "+fsen.getInVarSet()+"\n" );
+ Iterator<TempDescriptor> 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+"\n" );
+ }
+ if( fsen.getDynamicInVarSet().contains( inVar ) ) {
+ bw.write( " (dynamic)"+inVar+"\n" );
+ }
+ }
+
+ bw.write( " out-set: "+fsen.getOutVarSet()+"\n" );
+ bw.write( "}\n" );
+ }
+
+ Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
+ while( childItr.hasNext() ) {
+ FlatSESEEnterNode fsenChild = childItr.next();
+ printSESEInfoTree( bw, fsenChild );
+ }
}
}
projects / IRC.git / blobdiff