From f6198ce8a17c1f00b66342c0f1a99da7a5190270 Mon Sep 17 00:00:00 2001 From: jjenista Date: Thu, 30 Apr 2009 21:25:17 +0000 Subject: [PATCH] fixed liveness to calculate live-out set, and a couple other bugs --- Robust/src/Analysis/MLP/MLPAnalysis.java | 90 ++++++++++++++---------- Robust/src/IR/Flat/BuildFlat.java | 4 +- Robust/src/IR/Flat/FlatMethod.java | 11 ++- 3 files changed, 62 insertions(+), 43 deletions(-) diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index 17ed7a27..c4961b63 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -22,7 +22,6 @@ public class MLPAnalysis { private FlatSESEExitNode rootExit; private Hashtable< FlatNode, Stack > seseStacks; - private Hashtable< FlatNode, Set > livenessResults; private Hashtable< FlatNode, Set > livenessVirtualReads; private Hashtable< FlatNode, VarSrcTokTable > variableResults; private Hashtable< FlatNode, String > codePlan; @@ -43,7 +42,6 @@ public class MLPAnalysis { // initialize analysis data structures seseStacks = new Hashtable< FlatNode, Stack >(); - livenessResults = new Hashtable< FlatNode, Set >(); livenessVirtualReads = new Hashtable< FlatNode, Set >(); variableResults = new Hashtable< FlatNode, VarSrcTokTable >(); codePlan = new Hashtable< FlatNode, String >(); @@ -56,6 +54,8 @@ public class MLPAnalysis { rootSESE.setFlatExit ( rootExit ); rootExit.setFlatEnter( rootSESE ); + FlatMethod fmMain = state.getMethodFlat( tu.getMain() ); + // 1st pass // run analysis on each method that is actually called @@ -73,8 +73,7 @@ public class MLPAnalysis { // 2nd pass, results are saved in FlatSESEEnterNode, so // intermediate results, for safety, are discarded - livenessAnalysisBackward( rootSESE ); - livenessResults = null; + livenessAnalysisBackward( rootSESE, true, null, fmMain.getFlatExit() ); // 3rd pass @@ -91,9 +90,7 @@ public class MLPAnalysis { // 4th pass, compute liveness contribution from // virtual reads discovered in variable pass - livenessResults = new Hashtable< FlatNode, Set >(); - livenessAnalysisBackward( rootSESE ); - livenessResults = null; + livenessAnalysisBackward( rootSESE, true, null, fmMain.getFlatExit() ); // 5th pass @@ -207,23 +204,24 @@ public class MLPAnalysis { } - private void livenessAnalysisBackward( FlatSESEEnterNode fsen ) { - - // post-order traversal, so do children first - Iterator childItr = fsen.getChildren().iterator(); - while( childItr.hasNext() ) { - FlatSESEEnterNode fsenChild = childItr.next(); - livenessAnalysisBackward( fsenChild ); - } - + private void livenessAnalysisBackward( FlatSESEEnterNode fsen, boolean toplevel, Hashtable> 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 flatNodesToVisit = new HashSet(); - FlatSESEExitNode fsexn = fsen.getFlatExit(); - flatNodesToVisit.add( fsexn ); + FlatSESEExitNode fsexn = fsen.getFlatExit(); + if (toplevel) { + //handle root SESE + flatNodesToVisit.add( fexit ); + } else + flatNodesToVisit.add( fsexn ); + Hashtable> livenessResults=new Hashtable>(); + + if (toplevel==true) + liveout=new Hashtable>(); + while( !flatNodesToVisit.isEmpty() ) { FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); flatNodesToVisit.remove( fn ); @@ -240,18 +238,17 @@ public class MLPAnalysis { } } - Set curr = liveness_nodeActions( fn, u, fsen ); + Set 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 - if( !fn.equals( fsen ) ) { + 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 ); } } } @@ -275,32 +272,47 @@ public class MLPAnalysis { } System.out.println( "" ); } + // post-order traversal, so do children first + Iterator childItr = fsen.getChildren().iterator(); + while( childItr.hasNext() ) { + FlatSESEEnterNode fsenChild = childItr.next(); + livenessAnalysisBackward( fsenChild, false, liveout, null); + } } private Set liveness_nodeActions( FlatNode fn, Set liveIn, - FlatSESEEnterNode currentSESE ) { + FlatSESEEnterNode currentSESE, + boolean toplevel, + Hashtable> 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()); + liveout.get(exitn).addAll(liveIn); + } + // no break, sese exits should also execute default actions + default: { - VarSrcTokTable table = variableResults.get( fn ); - // 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( table != null ) { - Iterator vstItr = table.get( writeTemps[i] ).iterator(); - while( vstItr.hasNext() ) { - VariableSourceToken vst = vstItr.next(); - - if( !vst.getSESE().equals( currentSESE ) ) { - currentSESE.addOutVar( writeTemps[i] ); - break; - } - } - } + if (!toplevel) { + FlatSESEExitNode exitnode=currentSESE.getFlatExit(); + Set 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]); + } + } } TempDescriptor [] readTemps = fn.readsTemps(); diff --git a/Robust/src/IR/Flat/BuildFlat.java b/Robust/src/IR/Flat/BuildFlat.java index 2ebadbac..d1b7ae92 100644 --- a/Robust/src/IR/Flat/BuildFlat.java +++ b/Robust/src/IR/Flat/BuildFlat.java @@ -55,7 +55,7 @@ public class BuildFlat { FlatFlagActionNode ffan=new FlatFlagActionNode(FlatFlagActionNode.PRE); ffan.addNext(fn); - FlatMethod fm=new FlatMethod(td); + FlatMethod fm=new FlatMethod(td, fe); fm.addNext(ffan); Hashtable visitedset=new Hashtable(); @@ -157,7 +157,7 @@ public class BuildFlat { rnflat.addNext(fe); } - FlatMethod fm=new FlatMethod(currmd); + FlatMethod fm=new FlatMethod(currmd, fe); fm.addNext(fn); if (!currmd.isStatic()) fm.addParameterTemp(getTempforParam(currmd.getThis())); diff --git a/Robust/src/IR/Flat/FlatMethod.java b/Robust/src/IR/Flat/FlatMethod.java index cc60be51..6fdc29bb 100644 --- a/Robust/src/IR/Flat/FlatMethod.java +++ b/Robust/src/IR/Flat/FlatMethod.java @@ -9,21 +9,24 @@ public class FlatMethod extends FlatNode { Vector parameterTemps; Vector tagTemps; Hashtable tagtointmap; + FlatExit flatExit; - FlatMethod(MethodDescriptor md) { + FlatMethod(MethodDescriptor md, FlatExit fe) { method=md; task=null; parameterTemps=new Vector(); tagTemps=new Vector(); tagtointmap=new Hashtable(); + flatExit=fe; } - FlatMethod(TaskDescriptor td) { + FlatMethod(TaskDescriptor td, FlatExit fe) { task=td; method=null; parameterTemps=new Vector(); tagTemps=new Vector(); tagtointmap=new Hashtable(); + flatExit=fe; } public String toString() { @@ -87,6 +90,10 @@ public class FlatMethod extends FlatNode { return (TempDescriptor) parameterTemps.get(i); } + public FlatExit getFlatExit() { + return flatExit; + } + /** This method returns a set of the nodes in this flat representation */ public Set getNodeSet() { -- 2.34.1