import Analysis.OwnershipAnalysis.*;
import IR.*;
import IR.Flat.*;
+import IR.Tree.*;
import java.util.*;
import java.io.*;
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 FlatSESEEnterNode rootSESE;
+ private Set<FlatSESEEnterNode> allSESEs;
- private Stack<FlatSESEEnterNode> seseStack;
- private Set<FlatSESEEnterNode> seseRoots;
+ 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< FlatNode, Set<VariableSourceToken> > pointResults;
+ private static int maxSESEage = -1;
- public MLPAnalysis( State state,
- TypeUtil tu,
- CallGraph callGraph,
+ // 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,
+ CallGraph callGraph,
OwnershipAnalysis ownAnalysis
) {
this.typeUtil = tu;
this.callGraph = callGraph;
this.ownAnalysis = ownAnalysis;
+ this.maxSESEage = state.MLP_MAXSESEAGE;
// initialize analysis data structures
- seseStack = new Stack <FlatSESEEnterNode>();
- seseRoots = new HashSet<FlatSESEEnterNode>();
+ 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 >();
- pointResults = new Hashtable< FlatNode, Set<VariableSourceToken> >();
+ 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
// reachability analysis already computed this so reuse
Iterator<Descriptor> methItr = ownAnalysis.descriptorsToAnalyze.iterator();
while( methItr.hasNext() ) {
- Descriptor d = methItr.next();
-
- FlatMethod fm;
- if( d instanceof MethodDescriptor ) {
- fm = state.getMethodFlat( (MethodDescriptor) d);
- } else {
- assert d instanceof TaskDescriptor;
- fm = state.getMethodFlat( (TaskDescriptor) d);
- }
+ Descriptor d = methItr.next();
+ FlatMethod fm = state.getMethodFlat( d );
// find every SESE from methods that may be called
// and organize them into roots and children
buildForestForward( fm );
}
- Iterator<FlatSESEEnterNode> seseItr = seseRoots.iterator();
- while( seseItr.hasNext() ) {
- FlatSESEEnterNode fsen = seseItr.next();
- // do a post-order traversal of the forest so that
- // a child is analyzed before a parent. Start from
- // SESE's exit and do a backward data-flow analysis
- // for the source of variables
- computeReadAndWriteSetBackward( fsen );
+ // 2nd pass, results are saved in FlatSESEEnterNode, so
+ // intermediate results, for safety, are discarded
+ livenessAnalysisBackward( rootSESE, true, null, fmMain.getFlatExit() );
+
+
+ // 3rd pass
+ methItr = ownAnalysis.descriptorsToAnalyze.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 );
+ }
+
+
+ // 4th pass, compute liveness contribution from
+ // virtual reads discovered in variable pass
+ livenessAnalysisBackward( rootSESE, true, null, fmMain.getFlatExit() );
+
+
+ // 5th 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
+ methItr = ownAnalysis.descriptorsToAnalyze.iterator();
+ while( methItr.hasNext() ) {
+ Descriptor d = methItr.next();
+ FlatMethod fm = state.getMethodFlat( d );
+
+ // compute a plan for code injections
+ computeStallsForward( fm );
+ }
+
+
+ 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> flatNodesToVisit = new HashSet<FlatNode>();
flatNodesToVisit.add( fm );
- Set<FlatNode> visited = new HashSet<FlatNode>();
+ Set<FlatNode> visited = new HashSet<FlatNode>();
+
+ Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
+ seseStacks.put( fm, seseStackFirst );
while( !flatNodesToVisit.isEmpty() ) {
Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
FlatNode fn = fnItr.next();
- System.out.println( " considering "+fn );
-
- // only analyze sese exit nodes when all the nodes between
- // it and its matching enter have been analyzed
- if( !seseStack.empty() &&
- fn.equals( seseStack.peek().getFlatExit() ) &&
- flatNodesToVisit.size() != 1 ) {
- // not ready for this exit node yet, just grab another
- fn = fnItr.next();
- }
+ Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
+ assert seseStack != null;
flatNodesToVisit.remove( fn );
visited.add( fn );
- System.out.println( " visiting "+fn );
-
- analyzeFlatNode( fn, true, null, null );
-
- // initialize for backward computation in next step
- pointResults.put( fn, new HashSet<VariableSourceToken>() );
+ buildForest_nodeActions( fn, seseStack, fm );
for( int i = 0; i < fn.numNext(); i++ ) {
FlatNode nn = fn.getNext( i );
if( !visited.contains( nn ) ) {
flatNodesToVisit.add( nn );
+
+ // clone stack and send along each analysis path
+ seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
}
}
}
}
+ private void buildForest_nodeActions( FlatNode fn,
+ Stack<FlatSESEEnterNode> seseStack,
+ FlatMethod fm ) {
+ switch( fn.kind() ) {
+
+ case FKind.FlatSESEEnterNode: {
+ 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.FlatSESEExitNode: {
+ FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
+ assert !seseStack.empty();
+ FlatSESEEnterNode fsen = seseStack.pop();
+ } break;
+
+ case FKind.FlatReturnNode: {
+ FlatReturnNode frn = (FlatReturnNode) fn;
+ if( !seseStack.empty() ) {
+ 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 computeReadAndWriteSetBackward( FlatSESEEnterNode fsen ) {
+ 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
// should already be analyzed and therefore can be skipped
// because child SESE enter node has all necessary info
Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
- flatNodesToVisit.add( fsen.getFlatExit() );
+ 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==true)
+ liveout=new Hashtable<FlatSESEExitNode, Set<TempDescriptor>>();
+
while( !flatNodesToVisit.isEmpty() ) {
FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
flatNodesToVisit.remove( fn );
-
- Set<VariableSourceToken> prev = pointResults.get( fn );
+
+ Set<TempDescriptor> prev = livenessResults.get( fn );
// merge sets from control flow joins
- Set<VariableSourceToken> merge = new HashSet<VariableSourceToken>();
+ Set<TempDescriptor> u = new HashSet<TempDescriptor>();
for( int i = 0; i < fn.numNext(); i++ ) {
- FlatNode nn = fn.getNext( i );
- merge = mergeVSTsets( merge, pointResults.get( nn ) );
+ FlatNode nn = fn.getNext( i );
+ Set<TempDescriptor> s = livenessResults.get( nn );
+ if( s != null ) {
+ u.addAll( s );
+ }
}
-
- Set<VariableSourceToken> curr = analyzeFlatNode( fn, false, merge, fsen );
+
+ Set<TempDescriptor> curr = liveness_nodeActions( fn, u, fsen, toplevel, liveout);
// if a new result, schedule backward nodes for analysis
- if( !prev.equals( curr ) ) {
-
- System.out.println( " "+fn+":" );
- System.out.println( " prev ="+prev );
- System.out.println( " merge="+merge );
- System.out.println( " curr ="+curr );
- System.out.println( "" );
+ if( !curr.equals( prev ) ) {
+ livenessResults.put( fn, curr );
- pointResults.put( fn, curr );
-
- // don't flow backwards past SESE enter
- if( !fn.equals( fsen ) ) {
+ // don't flow backwards past current SESE enter
+ if( !fn.equals( fsen ) ) {
for( int i = 0; i < fn.numPrev(); i++ ) {
- FlatNode nn = fn.getPrev( i );
- flatNodesToVisit.add( nn );
+ 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 == true ) {
+ livenessRootView = livenessResults;
+ }
- if( state.MLPDEBUG ) {
- System.out.println( "SESE "+fsen.getPrettyIdentifier()+" has in-set:" );
- Iterator<VariableSourceToken> tItr = pointResults.get( fsen ).iterator();
- while( tItr.hasNext() ) {
- System.out.println( " "+tItr.next() );
- }
+ // 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 );
}
}
+ private Set<TempDescriptor> liveness_nodeActions( FlatNode fn,
+ Set<TempDescriptor> liveIn,
+ FlatSESEEnterNode currentSESE,
+ boolean toplevel,
+ Hashtable< FlatSESEExitNode, Set<TempDescriptor> > liveout ) {
- private Set<VariableSourceToken> analyzeFlatNode( FlatNode fn,
- boolean buildForest,
- Set<VariableSourceToken> vstSet,
- FlatSESEEnterNode currentSESE ) {
-
- // use node type to decide what alterations to make
- // to the ownership graph
switch( fn.kind() ) {
- case FKind.FlatSESEEnterNode: {
- FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
+ 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);
+ }
+ // no break, sese exits should also execute default actions
+
+ default: {
+ // handle effects of statement in reverse, writes then reads
+ 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( buildForest ) {
- if( seseStack.empty() ) {
- seseRoots.add( fsen );
- } else {
- seseStack.peek().addChild( fsen );
+ TempDescriptor [] readTemps = fn.readsTemps();
+ 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 );
}
- seseStack.push( fsen );
- System.out.println( " pushed "+fsen );
}
} break;
- case FKind.FlatSESEExitNode: {
- FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
+ } // 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 ) {
- if( buildForest ) {
- assert !seseStack.empty();
- FlatSESEEnterNode fsen = seseStack.pop();
- System.out.println( " popped "+fsen );
+ Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
+ flatNodesToVisit.add( fm );
+
+ while( !flatNodesToVisit.isEmpty() ) {
+ FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
+ flatNodesToVisit.remove( fn );
+
+ Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
+ assert seseStack != null;
+
+ VarSrcTokTable prev = variableResults.get( fn );
+
+ // merge sets from control flow joins
+ VarSrcTokTable curr = new VarSrcTokTable();
+ for( int i = 0; i < fn.numPrev(); i++ ) {
+ FlatNode nn = fn.getPrev( i );
+ VarSrcTokTable incoming = variableResults.get( nn );
+ curr.merge( incoming );
}
-
- //FlatSESEEnterNode fsen = fsexn.getFlatEnter();
- //assert fsen == seseStack.pop();
- //seseStack.peek().addInVarSet ( fsen.getInVarSet() );
- //seseStack.peek().addOutVarSet( fsen.getOutVarSet() );
- } break;
- /*
- case FKind.FlatMethod: {
- FlatMethod fm = (FlatMethod) fn;
- } break;
- */
-
- case FKind.FlatOpNode:
- case FKind.FlatCastNode:
- case FKind.FlatFieldNode:
- case FKind.FlatSetFieldNode:
- case FKind.FlatElementNode:
- case FKind.FlatSetElementNode: {
- if( !buildForest ) {
- // handle effects of statement in reverse, writes then reads
- TempDescriptor [] writeTemps = fn.writesTemps();
- for( int i = 0; i < writeTemps.length; ++i ) {
- vstSet = killTemp( vstSet, writeTemps[i] );
- }
+ if( !seseStack.empty() ) {
+ variable_nodeActions( fn, curr, seseStack.peek() );
+ }
+
+ // if a new result, schedule forward nodes for analysis
+ if( !curr.equals( prev ) ) {
+ variableResults.put( fn, curr );
- TempDescriptor [] readTemps = fn.readsTemps();
- for( int i = 0; i < readTemps.length; ++i ) {
- Set<VariableSourceToken> vstNew = new HashSet<VariableSourceToken>();
- vstNew.add( new VariableSourceToken( currentSESE,
- readTemps[i],
- new Integer( 0 ) ) );
- vstSet = mergeVSTsets( vstSet, vstNew );
+ for( int i = 0; i < fn.numNext(); i++ ) {
+ FlatNode nn = fn.getNext( i );
+ flatNodesToVisit.add( nn );
}
}
+ }
+ }
+
+ 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;
- /*
- case FKind.FlatNew: {
- FlatNew fnn = (FlatNew) fn;
- lhs = fnn.getDst();
- if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
- //AllocationSite as = getAllocationSiteFromFlatNewPRIVATE( fnn );
+ case FKind.FlatSESEExitNode: {
+ FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
+ FlatSESEEnterNode fsen = fsexn.getFlatEnter();
+ assert currentSESE.getChildren().contains( fsen );
+ vstTable.remapChildTokens( fsen );
+
+ Set<TempDescriptor> liveIn = currentSESE.getInVarSet();
+ Set<TempDescriptor> virLiveIn = vstTable.removeParentAndSiblingTokens( fsen, liveIn );
+ Set<TempDescriptor> virLiveInOld = livenessVirtualReads.get( fn );
+ if( virLiveInOld != null ) {
+ virLiveIn.addAll( virLiveInOld );
}
+ livenessVirtualReads.put( fn, virLiveIn );
+ vstTable.assertConsistency();
} break;
- */
- /*
- case FKind.FlatCall: {
- FlatCall fc = (FlatCall) fn;
- MethodDescriptor md = fc.getMethod();
- FlatMethod flatm = state.getMethodFlat( md );
+ case FKind.FlatOpNode: {
+ FlatOpNode fon = (FlatOpNode) fn;
+
+ if( fon.getOp().getOp() == Operation.ASSIGN ) {
+ TempDescriptor lhs = fon.getDest();
+ TempDescriptor rhs = fon.getLeft();
+
+ vstTable.remove( lhs );
+
+ Set<VariableSourceToken> forAddition = new HashSet<VariableSourceToken>();
+
+ Iterator<VariableSourceToken> itr = vstTable.get( rhs ).iterator();
+ while( itr.hasNext() ) {
+ VariableSourceToken vst = itr.next();
+
+ 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
+ )
+ );
+ }
+ }
+ vstTable.addAll( forAddition );
- if( md.isStatic() ) {
+ // only break if this is an ASSIGN op node,
+ // otherwise fall through to default case
+ vstTable.assertConsistency();
+ break;
+ }
+ }
- } else {
- // if the method descriptor is virtual, then there could be a
- // set of possible methods that will actually be invoked, so
- // find all of them and merge all of their results together
- TypeDescriptor typeDesc = fc.getThis().getType();
- Set possibleCallees = callGraph.getMethods( md, typeDesc );
+ // note that FlatOpNode's that aren't ASSIGN
+ // fall through to this default case
+ default: {
+ TempDescriptor [] writeTemps = fn.writesTemps();
+ if( writeTemps.length > 0 ) {
- Iterator i = possibleCallees.iterator();
- while( i.hasNext() ) {
- MethodDescriptor possibleMd = (MethodDescriptor) i.next();
- FlatMethod pflatm = state.getMethodFlat( possibleMd );
- }
- }
+ // 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;
+ }
- } break;
- */
- case FKind.FlatReturnNode: {
- FlatReturnNode frn = (FlatReturnNode) fn;
- if( buildForest && !seseStack.empty() ) {
- throw new Error( "Error: return statement enclosed within "+seseStack.peek() );
- }
+ vstTable.remove( writeTemps[0] );
+
+ HashSet<TempDescriptor> ts = new HashSet<TempDescriptor>();
+ ts.add( writeTemps[0] );
+
+ vstTable.add( new VariableSourceToken( ts,
+ currentSESE,
+ new Integer( 0 ),
+ writeTemps[0]
+ )
+ );
+ }
+
+ vstTable.assertConsistency();
} break;
} // end switch
+ }
+
+
+ private void notAvailableForward( FlatMethod fm ) {
+
+ Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
+ flatNodesToVisit.add( fm );
+
+ while( !flatNodesToVisit.isEmpty() ) {
+ FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
+ flatNodesToVisit.remove( fn );
+
+ Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
+ assert seseStack != null;
+
+ Set<TempDescriptor> prev = notAvailableResults.get( fn );
+
+ 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 ) {
+ curr.addAll( notAvailIn );
+ }
+ }
+
+ if( !seseStack.empty() ) {
+ notAvailable_nodeActions( fn, curr, seseStack.peek() );
+ }
+ // if a new result, schedule forward nodes for analysis
+ if( !curr.equals( prev ) ) {
+ notAvailableResults.put( fn, curr );
- return vstSet;
+ for( int i = 0; i < fn.numNext(); i++ ) {
+ FlatNode nn = fn.getNext( i );
+ flatNodesToVisit.add( nn );
+ }
+ }
+ }
}
+ 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
+ // as temps to be grabbed at runtime!
+
+ switch( fn.kind() ) {
+
+ case FKind.FlatSESEEnterNode: {
+ FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
+ assert fsen.equals( currentSESE );
+ notAvailSet.clear();
+ } break;
+
+ case FKind.FlatSESEExitNode: {
+ FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
+ FlatSESEEnterNode fsen = fsexn.getFlatEnter();
+ assert currentSESE.getChildren().contains( fsen );
+
+ Set<TempDescriptor> liveTemps = livenessRootView.get( fn );
+ assert liveTemps != null;
- private Set<VariableSourceToken> killTemp( Set<VariableSourceToken> s,
- TempDescriptor t ) {
- Set<VariableSourceToken> out = new HashSet<VariableSourceToken>();
+ VarSrcTokTable vstTable = variableResults.get( fn );
+ assert vstTable != null;
- Iterator<VariableSourceToken> vstitr = s.iterator();
- while( vstitr.hasNext() ) {
- VariableSourceToken vst = vstitr.next();
+ Set<TempDescriptor> notAvailAtEnter = notAvailableResults.get( fsen );
+ assert notAvailAtEnter != null;
- if( !vst.getVar().equals( t ) ) {
- out.add( vst );
+ 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;
+ }
+ }
+ } break;
+
+ case FKind.FlatOpNode: {
+ FlatOpNode fon = (FlatOpNode) fn;
+
+ if( fon.getOp().getOp() == Operation.ASSIGN ) {
+ TempDescriptor lhs = fon.getDest();
+ TempDescriptor rhs = fon.getLeft();
+
+ // copy makes lhs same availability as rhs
+ if( notAvailSet.contains( rhs ) ) {
+ notAvailSet.add( lhs );
+ } else {
+ notAvailSet.remove( lhs );
+ }
+
+ // only break if this is an ASSIGN op node,
+ // otherwise fall through to default case
+ break;
}
}
- return out;
+ // 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++ ) {
+ TempDescriptor wTemp = writeTemps[i];
+ notAvailSet.remove( wTemp );
+ }
+ TempDescriptor [] readTemps = fn.readsTemps();
+ for( int i = 0; i < readTemps.length; i++ ) {
+ 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( 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() );
+ }
+ }
+ }
+ } break;
+
+ } // end switch
}
- private Set<VariableSourceToken> mergeVSTsets( Set<VariableSourceToken> s1,
- Set<VariableSourceToken> s2 ) {
+ private void computeStallsForward( FlatMethod fm ) {
- Set<VariableSourceToken> out = new HashSet<VariableSourceToken>();
+ // start from flat method top, visit every node in
+ // method exactly once
+ Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
+ flatNodesToVisit.add( fm );
- Iterator<VariableSourceToken> vst1itr = s1.iterator();
- while( vst1itr.hasNext() ) {
- VariableSourceToken vst1 = vst1itr.next();
+ Set<FlatNode> visited = new HashSet<FlatNode>();
- int changeAge = -1;
-
- Iterator<VariableSourceToken> vst2itr = s2.iterator();
- while( vst2itr.hasNext() ) {
- VariableSourceToken vst2 = vst2itr.next();
-
- if( vst1.getSESE().equals( vst2.getSESE() ) &&
- vst1.getVar() .equals( vst2.getVar() ) ) {
- changeAge = vst1.getAge();
- int a = vst2.getAge();
- if( a < changeAge ) {
- changeAge = a;
- }
- break;
+ while( !flatNodesToVisit.isEmpty() ) {
+ Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
+ FlatNode fn = fnItr.next();
+
+ flatNodesToVisit.remove( fn );
+ visited.add( fn );
+
+ Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
+ assert seseStack != null;
+
+ // use incoming results as "dot statement" or just
+ // before the current statement
+ VarSrcTokTable dotSTtable = new VarSrcTokTable();
+ for( int i = 0; i < fn.numPrev(); i++ ) {
+ FlatNode nn = fn.getPrev( i );
+ dotSTtable.merge( variableResults.get( nn ) );
+ }
+
+ // 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( !visited.contains( nn ) ) {
+ flatNodesToVisit.add( nn );
}
}
+ }
+ }
+
+ private void computeStalls_nodeActions( FlatNode fn,
+ VarSrcTokTable vstTable,
+ Set<TempDescriptor> notAvailSet,
+ FlatSESEEnterNode currentSESE ) {
+ CodePlan plan = new CodePlan();
- if( changeAge < 0 ) {
- out.add( vst1 );
- } else {
- out.add( new VariableSourceToken( vst1.getSESE(),
- vst1.getVar(),
- new Integer( changeAge ) ) );
+
+ switch( fn.kind() ) {
+
+ case FKind.FlatSESEEnterNode: {
+ 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: {
- Iterator<VariableSourceToken> vst2itr = s2.iterator();
- while( vst2itr.hasNext() ) {
- VariableSourceToken vst2 = vst2itr.next();
+ // decide if we must stall for variables dereferenced at this node
+ Set<VariableSourceToken> potentialStallSet =
+ vstTable.getChildrenVSTs( currentSESE );
- boolean matchSESEandVar = false;
+ // a node with no live set has nothing to stall for
+ Set<TempDescriptor> liveSet = livenessRootView.get( fn );
+ if( liveSet == null ) {
+ break;
+ }
- vst1itr = s1.iterator();
- while( vst1itr.hasNext() ) {
- VariableSourceToken vst1 = vst1itr.next();
+ TempDescriptor[] readarray = fn.readsTemps();
+ for( int i = 0; i < readarray.length; i++ ) {
+ TempDescriptor readtmp = readarray[i];
- if( vst1.getSESE().equals( vst2.getSESE() ) &&
- vst1.getVar() .equals( vst2.getVar() ) ) {
- matchSESEandVar = true;
- break;
+ // ignore temps that are definitely available
+ // when considering to stall on it
+ if( !notAvailSet.contains( readtmp ) ) {
+ continue;
}
- }
- if( !matchSESEandVar ) {
- out.add( vst2 );
+ // Two cases:
+ Set<VariableSourceToken> srcs = vstTable.get( readtmp );
+ assert !srcs.isEmpty();
+
+ // 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
+
+
+ // 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 ) );
}
}
-
- return out;
+ if( !static2dynamicSet.isEmpty() ) {
+ plan.setWriteToDynamicSrc( static2dynamicSet );
+ }
+
+ codePlans.put( fn, plan );
}
}
-
-
projects / IRC.git / blobdiff