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;
+ private FlatSESEEnterNode rootSESE;
+ private Set<FlatSESEEnterNode> allSESEs;
private Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks;
private Hashtable< FlatNode, Set<TempDescriptor> > livenessRootView;
private Hashtable< FlatNode, Set<TempDescriptor> > notAvailableResults;
private Hashtable< FlatNode, CodePlan > codePlans;
+ private static int maxSESEage = -1;
+
+
+ // use these methods in BuildCode to have access to analysis results
+ public FlatSESEEnterNode getRootSESE() {
+ return rootSESE;
+ }
+
+ public Set<FlatSESEEnterNode> getAllSESEs() {
+ return allSESEs;
+ }
+
+ public int getMaxSESEage() {
+ return maxSESEage;
+ }
+
+ // may be null
+ public CodePlan getCodePlan( FlatNode fn ) {
+ CodePlan cp = codePlans.get( fn );
+ return cp;
+ }
+
public MLPAnalysis( State state,
TypeUtil tu,
this.typeUtil = tu;
this.callGraph = callGraph;
this.ownAnalysis = ownAnalysis;
+ this.maxSESEage = state.MLP_MAXSESEAGE;
// initialize analysis data structures
+ allSESEs = new HashSet<FlatSESEEnterNode>();
+
seseStacks = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
livenessVirtualReads = new Hashtable< FlatNode, Set<TempDescriptor> >();
variableResults = new Hashtable< FlatNode, VarSrcTokTable >();
notAvailableResults = new Hashtable< FlatNode, Set<TempDescriptor> >();
codePlans = new Hashtable< FlatNode, CodePlan >();
-
-
- // 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( tu.getMain() );
+ rootSESE = (FlatSESEEnterNode) fmMain.getNext(0);
+ rootSESE.setfmEnclosing( fmMain );
+ rootSESE.setmdEnclosing( fmMain.getMethod() );
+ rootSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
+
// 1st pass
// run analysis on each method that is actually called
}
+ if( state.MLPDEBUG ) {
+ System.out.println( "" );
+ //System.out.println( "\nSESE Hierarchy\n--------------\n" ); printSESEHierarchy();
+ //System.out.println( "\nSESE Liveness\n-------------\n" ); printSESELiveness();
+ System.out.println( "\nLiveness Root View\n------------------\n"+fmMain.printMethod( livenessRootView ) );
+ System.out.println( "\nVariable Results\n----------------\n"+fmMain.printMethod( variableResults ) );
+ //System.out.println( "\nNot Available Results\n---------------------\n"+fmMain.printMethod( notAvailableResults ) );
+ System.out.println( "\nCode Plans\n----------\n"+fmMain.printMethod( codePlans ) );
+ }
+
+
double timeEndAnalysis = (double) System.nanoTime();
double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
String treport = String.format( "The mlp analysis took %.3f sec.", dt );
Set<FlatNode> visited = new HashSet<FlatNode>();
Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
- seseStackFirst.push( rootSESE );
seseStacks.put( fm, seseStackFirst );
while( !flatNodesToVisit.isEmpty() ) {
flatNodesToVisit.remove( fn );
visited.add( fn );
- buildForest_nodeActions( fn, seseStack );
+ buildForest_nodeActions( fn, seseStack, fm );
for( int i = 0; i < fn.numNext(); i++ ) {
FlatNode nn = fn.getNext( i );
}
}
}
-
- if( state.MLPDEBUG ) {
- printSESEForest();
- }
}
private void buildForest_nodeActions( FlatNode fn,
- Stack<FlatSESEEnterNode> seseStack ) {
+ Stack<FlatSESEEnterNode> seseStack,
+ FlatMethod fm ) {
switch( fn.kind() ) {
case FKind.FlatSESEEnterNode: {
- FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
- assert !seseStack.empty();
- seseStack.peek().addChild( fsen );
- fsen.setParent( seseStack.peek() );
+ FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
+
+ allSESEs.add( fsen );
+ fsen.setfmEnclosing( fm );
+ fsen.setmdEnclosing( fm.getMethod() );
+ fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
+
+ if( !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() ) {
+ throw new Error( "Error: return statement enclosed within SESE "+
+ seseStack.peek().getPrettyIdentifier() );
}
} break;
}
}
- private void printSESEForest() {
+ private void printSESEHierarchy() {
// our forest is actually a tree now that
// there is an implicit root SESE
- printSESETree( rootSESE, 0 );
+ printSESEHierarchyTree( rootSESE, 0 );
System.out.println( "" );
}
- private void printSESETree( FlatSESEEnterNode fsen, int depth ) {
+ private void printSESEHierarchyTree( FlatSESEEnterNode fsen, int depth ) {
for( int i = 0; i < depth; ++i ) {
System.out.print( " " );
}
- System.out.println( fsen.getPrettyIdentifier() );
+ System.out.println( "- "+fsen.getPrettyIdentifier() );
Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
while( childItr.hasNext() ) {
FlatSESEEnterNode fsenChild = childItr.next();
- printSESETree( fsenChild, depth + 1 );
+ printSESEHierarchyTree( fsenChild, depth + 1 );
}
}
- private void livenessAnalysisBackward( FlatSESEEnterNode fsen,
- boolean toplevel,
- Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout,
- FlatExit fexit ) {
+ private void livenessAnalysisBackward( FlatSESEEnterNode fsen,
+ boolean toplevel,
+ Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout,
+ FlatExit fexit ) {
// start from an SESE exit, visit nodes in reverse up to
// SESE enter in a fixed-point scheme, where children SESEs
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
fsen.addInVarSet( s );
}
- if( state.MLPDEBUG ) {
- 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( "" );
- }
-
// remember liveness per node from the root view as the
// global liveness of variables for later passes to use
if( toplevel == true ) {
Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator();
while( childItr.hasNext() ) {
FlatSESEEnterNode fsenChild = childItr.next();
- livenessAnalysisBackward( fsenChild, false, liveout, null);
+ livenessAnalysisBackward( fsenChild, false, liveout, null );
}
}
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 ) {
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: {
default: {
TempDescriptor [] writeTemps = fn.writesTemps();
if( writeTemps.length > 0 ) {
- assert writeTemps.length == 1;
+
+
+ // 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.remove( writeTemps[0] );
} break;
} // end switch
-
- return vstTable;
}
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
// else from that source as available as well
VarSrcTokTable table = variableResults.get( fn );
Set<VariableSourceToken> srcs = table.get( rTemp );
+
if( srcs.size() == 1 ) {
VariableSourceToken vst = srcs.iterator().next();
} break;
} // end switch
-
- return notAvailSet;
}
// use incoming results as "dot statement" or just
// before the current statement
- VarSrcTokTable dotST = new VarSrcTokTable();
+ VarSrcTokTable dotSTtable = new VarSrcTokTable();
for( int i = 0; i < fn.numPrev(); i++ ) {
FlatNode nn = fn.getPrev( i );
- dotST.merge( variableResults.get( nn ) );
+ dotSTtable.merge( variableResults.get( nn ) );
}
- computeStalls_nodeActions( fn, dotST, seseStack.peek() );
+ // find dt-st notAvailableSet also
+ Set<TempDescriptor> dotSTnotAvailSet = 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 ) {
+ dotSTnotAvailSet.addAll( notAvailIn );
+ }
+ }
+
+ if( !seseStack.empty() ) {
+ computeStalls_nodeActions( fn, dotSTtable, dotSTnotAvailSet, seseStack.peek() );
+ }
for( int i = 0; i < fn.numNext(); i++ ) {
FlatNode nn = fn.getNext( i );
}
}
}
-
- if( state.MLPDEBUG ) {
- //System.out.println( fm.printMethod( livenessRootView ) );
- //System.out.println( fm.printMethod( variableResults ) );
- //System.out.println( fm.printMethod( notAvailableResults ) );
- System.out.println( fm.printMethod( codePlans ) );
- }
}
private void computeStalls_nodeActions( FlatNode fn,
VarSrcTokTable vstTable,
+ Set<TempDescriptor> notAvailSet,
FlatSESEEnterNode currentSESE ) {
- String before = null;
- String after = null;
+ CodePlan plan = new CodePlan();
+
switch( fn.kind() ) {
case FKind.FlatSESEEnterNode: {
- FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
+ FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
} break;
case FKind.FlatSESEExitNode: {
FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
} break;
+ case FKind.FlatOpNode: {
+ FlatOpNode fon = (FlatOpNode) fn;
+
+ if( fon.getOp().getOp() == Operation.ASSIGN ) {
+ // if this is an op node, don't stall, copy
+ // source and delay until we need to use value
+
+ // 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<TempDescriptor> notAvailSet = notAvailableResults.get( fn );
- Set<VariableSourceToken> stallSet = vstTable.getStallSet( currentSESE );
+ Set<VariableSourceToken> potentialStallSet =
+ vstTable.getChildrenVSTs( currentSESE );
+
+ // a node with no live set has nothing to stall for
+ Set<TempDescriptor> liveSet = livenessRootView.get( fn );
+ if( liveSet == null ) {
+ break;
+ }
TempDescriptor[] readarray = fn.readsTemps();
for( int i = 0; i < readarray.length; i++ ) {
continue;
}
- Set<VariableSourceToken> readSet = vstTable.get( readtmp );
- //containsAny
- 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+")";
- }
- }
- }
+ // Two cases:
+ Set<VariableSourceToken> srcs = vstTable.get( readtmp );
+ assert !srcs.isEmpty();
- // 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();
- while( vstItr.hasNext() ) {
- VariableSourceToken vst = vstItr.next();
- if( after == null ) {
- after = "** Write dynamic: ";
- }
- after += "("+vst+")";
- }
-
+ // 1) Multiple token/age pairs or unknown age: Stall for
+ // dynamic name only.
+ if( srcs.size() > 1 ||
+ srcs.iterator().next().getAge() == maxSESEage ) {
+
+ // identify that this is a stall, and allocate an integer
+ // pointer in the generated code that keeps a pointer to
+ // the source SESE and the address of where to get this thing
+ // --then the stall is just wait for that, and copy the
+ // one thing because we're not sure if we can copy other stuff
+
+ // NEEDS WORK!
+
+
+
+ // 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.
+ } else {
+ VariableSourceToken vst = srcs.iterator().next();
+
+ Iterator<VariableSourceToken> availItr =
+ vstTable.get( vst.getSESE(), vst.getAge() ).iterator();
+
+ while( availItr.hasNext() ) {
+ VariableSourceToken vstAlsoAvail = availItr.next();
+
+ // only grab additional stuff that is live
+ Set<TempDescriptor> copySet = new HashSet<TempDescriptor>();
+
+ Iterator<TempDescriptor> refVarItr = vstAlsoAvail.getRefVars().iterator();
+ while( refVarItr.hasNext() ) {
+ TempDescriptor refVar = refVarItr.next();
+ if( liveSet.contains( refVar ) ) {
+ copySet.add( refVar );
+ }
+ }
+
+ if( !copySet.isEmpty() ) {
+ plan.addStall2CopySet( vstAlsoAvail, copySet );
+ }
+ }
+ }
+
+ // assert that everything being stalled for is in the
+ // "not available" set coming into this flat node and
+ // that every VST identified is in the possible "stall set"
+ // that represents VST's from children SESE's
+
+ }
} break;
} // end switch
- if( before == null ) {
- before = "";
+
+
+ // identify sese-age pairs that are statically useful
+ // and should have an associated SESE variable in code
+ Set<VariableSourceToken> staticSet = vstTable.getStaticSet();
+ Iterator<VariableSourceToken> vstItr = staticSet.iterator();
+ while( vstItr.hasNext() ) {
+ VariableSourceToken vst = vstItr.next();
+ currentSESE.addNeededStaticName(
+ new SESEandAgePair( vst.getSESE(), vst.getAge() )
+ );
+ }
+
+ // 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 );
+ // the table can be null if it is one of the few IR nodes
+ // completely outside of the root SESE scope
+ if( nextVstTable != null ) {
+ static2dynamicSet.addAll( vstTable.getStatic2DynamicSet( nextVstTable ) );
+ }
}
- if( after == null ) {
- after = "";
+ if( !static2dynamicSet.isEmpty() ) {
+ plan.setWriteToDynamicSrc( static2dynamicSet );
}
- codePlans.put( fn, new CodePlan( before, after ) );
+ codePlans.put( fn, plan );
}
}
projects / IRC.git / blobdiff