From 80a2da373483d77355fbcbc851e550f00d6f18d9 Mon Sep 17 00:00:00 2001 From: jjenista Date: Wed, 12 Aug 2009 00:09:43 +0000 Subject: [PATCH] Bug fixes in use of liveness analysis, bug fix in not-available analysis, something still wrong with computation of dynamic stalls --- Robust/src/Analysis/MLP/MLPAnalysis.java | 151 ++++++++++++-------- Robust/src/Analysis/MLP/VarSrcTokTable.java | 27 ++++ Robust/src/Tests/mlp/tinyTest/test.java | 13 +- 3 files changed, 128 insertions(+), 63 deletions(-) diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index 78d207dc..6766027e 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -121,17 +121,14 @@ public class MLPAnalysis { // variable analysis for refinement and stalls variableAnalysisForward( fm ); } - if( state.MLPDEBUG ) { - System.out.println( "\nVariable Results\n----------------\n"+fmMain.printMethod( variableResults ) ); - } // 4th pass, compute liveness contribution from // virtual reads discovered in variable pass livenessAnalysisBackward( rootSESE, true, null, fmMain.getFlatExit() ); if( state.MLPDEBUG ) { - //System.out.println( "\nSESE Liveness\n-------------\n" ); printSESELiveness(); - //System.out.println( "\nLiveness Root View\n------------------\n"+fmMain.printMethod( livenessRootView ) ); + //System.out.println( "\nLive-In, SESE View\n-------------\n" ); printSESELiveness(); + //System.out.println( "\nLive-In, Root View\n------------------\n"+fmMain.printMethod( livenessRootView ) ); } @@ -141,16 +138,31 @@ public class MLPAnalysis { 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 ); + } + if( state.MLPDEBUG ) { + //System.out.println( "\nVariable Results-Out\n----------------\n"+fmMain.printMethod( variableResults ) ); + } + + + // 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 ); } if( state.MLPDEBUG ) { - System.out.println( "\nNot Available Results\n---------------------\n"+fmMain.printMethod( notAvailableResults ) ); + System.out.println( "\nNot Available Results-Out\n---------------------\n"+fmMain.printMethod( notAvailableResults ) ); } - // 5th pass + // 7th pass methItr = ownAnalysis.descriptorsToAnalyze.iterator(); while( methItr.hasNext() ) { Descriptor d = methItr.next(); @@ -500,6 +512,25 @@ public class MLPAnalysis { } livenessVirtualReads.put( fn, virLiveIn ); vstTable.assertConsistency(); + + // then all child out-set tokens are guaranteed + // to be filled in, so clobber those entries with + // the latest, clean sources + Iterator outVarItr = fsen.getOutVarSet().iterator(); + while( outVarItr.hasNext() ) { + TempDescriptor outVar = outVarItr.next(); + HashSet ts = new HashSet(); + ts.add( outVar ); + VariableSourceToken vst = new VariableSourceToken( ts, + fsen, + new Integer( 0 ), + outVar + ); + vstTable.remove( outVar ); + vstTable.add( vst ); + } + vstTable.assertConsistency(); + } break; case FKind.FlatOpNode: { @@ -507,7 +538,7 @@ public class MLPAnalysis { if( fon.getOp().getOp() == Operation.ASSIGN ) { TempDescriptor lhs = fon.getDest(); - TempDescriptor rhs = fon.getLeft(); + TempDescriptor rhs = fon.getLeft(); vstTable.remove( lhs ); @@ -520,25 +551,12 @@ public class MLPAnalysis { HashSet ts = new HashSet(); 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 - ) - ); - } + forAddition.add( new VariableSourceToken( ts, + vst.getSESE(), + vst.getAge(), + vst.getAddrVar() + ) + ); } vstTable.addAll( forAddition ); @@ -588,6 +606,39 @@ public class MLPAnalysis { } + private void pruneVariableResultsWithLiveness( FlatMethod fm ) { + + // start from flat method top, visit every node in + // method exactly once + Set flatNodesToVisit = new HashSet(); + flatNodesToVisit.add( fm ); + + Set visited = new HashSet(); + + while( !flatNodesToVisit.isEmpty() ) { + Iterator fnItr = flatNodesToVisit.iterator(); + FlatNode fn = fnItr.next(); + + flatNodesToVisit.remove( fn ); + visited.add( fn ); + + Set rootLiveSet = livenessRootView.get( fn ); + VarSrcTokTable vstTable = variableResults.get( fn ); + + // fix later, not working, only wanted it to make tables easier to read + //vstTable.pruneByLiveness( rootLiveSet ); + + for( int i = 0; i < fn.numNext(); i++ ) { + FlatNode nn = fn.getNext( i ); + + if( !visited.contains( nn ) ) { + flatNodesToVisit.add( nn ); + } + } + } + } + + private void notAvailableForward( FlatMethod fm ) { Set flatNodesToVisit = new HashSet(); @@ -610,7 +661,7 @@ public class MLPAnalysis { curr.addAll( notAvailIn ); } } - + if( !seseStack.empty() ) { notAvailable_nodeActions( fn, curr, seseStack.peek() ); } @@ -651,28 +702,7 @@ public class MLPAnalysis { Set liveTemps = livenessRootView.get( fn ); assert liveTemps != null; - VarSrcTokTable vstTable = variableResults.get( fn ); - assert vstTable != null; - - Set notAvailAtEnter = notAvailableResults.get( fsen ); - assert notAvailAtEnter != null; - - Iterator 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( liveTemps ); } break; case FKind.FlatOpNode: { @@ -710,15 +740,20 @@ public class MLPAnalysis { // if this variable has exactly one source, mark everything // else from that source as available as well - VarSrcTokTable table = variableResults.get( fn ); - Set srcs = table.get( rTemp ); + VarSrcTokTable vstTable = variableResults.get( fn ); - if( srcs.size() == 1 ) { - VariableSourceToken vst = srcs.iterator().next(); - - Iterator 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 availItr = vstTable.get( vst.getSESE(), + vst.getAge() + ).iterator(); while( availItr.hasNext() ) { VariableSourceToken vstAlsoAvail = availItr.next(); notAvailSet.removeAll( vstAlsoAvail.getRefVars() ); diff --git a/Robust/src/Analysis/MLP/VarSrcTokTable.java b/Robust/src/Analysis/MLP/VarSrcTokTable.java index a9078cc8..226eb6a6 100644 --- a/Robust/src/Analysis/MLP/VarSrcTokTable.java +++ b/Robust/src/Analysis/MLP/VarSrcTokTable.java @@ -534,6 +534,33 @@ public class VarSrcTokTable { } + // any reference variables that are not live can be pruned + // from the table, and if any VSTs are then no longer + // referenced, they can be dropped as well + /* THIS CAUSES INCONSISTENCY, FIX LATER, NOT REQUIRED + public void pruneByLiveness( Set rootLiveSet ) { + + // the set of reference variables in the table minus the + // live set gives the set of reference variables to remove + Set deadRefVars = new HashSet(); + deadRefVars.addAll( var2vst.keySet() ); + + if( rootLiveSet != null ) { + deadRefVars.removeAll( rootLiveSet ); + } + + // just use the remove operation to prune the table now + Iterator deadItr = deadRefVars.iterator(); + while( deadItr.hasNext() ) { + TempDescriptor dead = deadItr.next(); + removePrivate( dead ); + } + + assertConsistency(); + } + */ + + // use as an aid for debugging, where true-set is checked // against the alternate mappings: assert that nothing is // missing or extra in the alternates diff --git a/Robust/src/Tests/mlp/tinyTest/test.java b/Robust/src/Tests/mlp/tinyTest/test.java index b316a5f0..a261f869 100644 --- a/Robust/src/Tests/mlp/tinyTest/test.java +++ b/Robust/src/Tests/mlp/tinyTest/test.java @@ -12,11 +12,13 @@ public class Test { public static void main( String args[] ) { - int x = Integer.parseInt( args[0] ); - int y = Integer.parseInt( args[1] ); - System.out.println( "root: x="+x+", y="+y ); + //int x = Integer.parseInt( args[0] ); + //int y = Integer.parseInt( args[1] ); + //System.out.println( "root: x="+x+", y="+y ); + int y = 2; - if( x > 3 ) { + //if( x > 3 ) { + if( true ) { sese fi { y = y + 10; } @@ -25,7 +27,8 @@ public class Test { // see that values from sese fi are // forwarded to this sibling //sese fo { - System.out.println( "fo: x="+x+", y="+y ); + //System.out.println( "fo: x="+x+", y="+y ); + System.out.println( "y="+y ); //} /* -- 2.34.1