From 40925bd1d325e02a61893cbf21a6dfeecdf91c16 Mon Sep 17 00:00:00 2001 From: jjenista <jjenista> Date: Wed, 6 May 2009 23:08:02 +0000 Subject: [PATCH] add frame for another pass to compute whether variables are available, then use to do computation for stalls --- Robust/src/Analysis/MLP/MLPAnalysis.java | 89 ++++++++++++++++++++++++ 1 file changed, 89 insertions(+) diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index 2309c29d..77de936c 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -22,8 +22,10 @@ public class MLPAnalysis { private FlatSESEExitNode rootExit; 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> > isAvailableResults; private Hashtable< FlatNode, CodePlan > codePlans; @@ -44,9 +46,11 @@ public class MLPAnalysis { seseStacks = new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >(); livenessVirtualReads = new Hashtable< FlatNode, Set<TempDescriptor> >(); variableResults = new Hashtable< FlatNode, VarSrcTokTable >(); + isAvailableResults = 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 ); @@ -93,6 +97,18 @@ public class MLPAnalysis { 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 is available for every live variable at + // every program point, in a forward fixed-point pass + isAvailableForward( fm ); + } + + // 5th pass methItr = ownAnalysis.descriptorsToAnalyze.iterator(); while( methItr.hasNext() ) { @@ -276,6 +292,13 @@ public class MLPAnalysis { } 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 ) { + livenessRootView = livenessResults; + } + // post-order traversal, so do children first Iterator<FlatSESEEnterNode> childItr = fsen.getChildren().iterator(); while( childItr.hasNext() ) { @@ -485,6 +508,72 @@ public class MLPAnalysis { } + private void isAvailableForward( 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 = isAvailableResults.get( fn ); + + // merge control flow joins where something is available + // into this node only if it is available on every incoming + // node, so do intersect of all incoming nodes with live in + HashSet<TempDescriptor> rootLiveSet = (HashSet<TempDescriptor>) livenessRootView.get( fn ); + Set<TempDescriptor> inIntersect = (Set<TempDescriptor>) rootLiveSet.clone(); + + for( int i = 0; i < fn.numPrev(); i++ ) { + FlatNode nn = fn.getPrev( i ); + Set<TempDescriptor> availIn = isAvailableResults.get( nn ); + inIntersect.retainAll( availIn ); + } + + Set<TempDescriptor> curr = isAvailable_nodeActions( fn, inIntersect, seseStack.peek() ); + + // if a new result, schedule forward nodes for analysis + if( !curr.equals( prev ) ) { + isAvailableResults.put( fn, curr ); + + for( int i = 0; i < fn.numNext(); i++ ) { + FlatNode nn = fn.getNext( i ); + flatNodesToVisit.add( nn ); + } + } + } + } + + private Set<TempDescriptor> isAvailable_nodeActions( FlatNode fn, + Set<TempDescriptor> isAvailSet, + FlatSESEEnterNode currentSESE ) { + switch( fn.kind() ) { + + case FKind.FlatSESEEnterNode: { + FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn; + assert fsen.equals( currentSESE ); + } break; + + case FKind.FlatSESEExitNode: { + FlatSESEExitNode fsexn = (FlatSESEExitNode) fn; + FlatSESEEnterNode fsen = fsexn.getFlatEnter(); + assert currentSESE.getChildren().contains( fsen ); + } break; + + default: { + TempDescriptor [] writeTemps = fn.writesTemps(); + } break; + + } // end switch + + return isAvailSet; + } + + private void computeStallsForward( FlatMethod fm ) { // start from flat method top, visit every node in -- 2.34.1