From: jjenista Date: Tue, 28 Apr 2009 18:55:45 +0000 (+0000) Subject: added another liveness pass that picks up on virtual reads from stall pass, nasty... X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=commitdiff_plain;h=8e24bcf19e15c85da21afd25c77591f948344696 added another liveness pass that picks up on virtual reads from stall pass, nasty bug fix in token table merge that left tables inconsistent --- diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index f56bf8bf..7742b76c 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -23,6 +23,7 @@ public class MLPAnalysis { 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; @@ -41,10 +42,11 @@ public class MLPAnalysis { this.ownAnalysis = ownAnalysis; // initialize analysis data structures - seseStacks = new Hashtable< FlatNode, Stack >(); - livenessResults = new Hashtable< FlatNode, Set >(); - variableResults = new Hashtable< FlatNode, VarSrcTokTable >(); - codePlan = new Hashtable< FlatNode, String >(); + 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 >(); // build an implicit root SESE to wrap contents of main method @@ -95,6 +97,11 @@ public class MLPAnalysis { } + // 5th pass, compute liveness contribution from + // virtual reads discovered in stall pass + livenessAnalysisBackward( rootSESE ); + + 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 ); @@ -276,6 +283,14 @@ public class MLPAnalysis { for( int i = 0; i < readTemps.length; ++i ) { liveIn.add( readTemps[i] ); } + + Set virtualReadTemps = livenessVirtualReads.get( fn ); + if( virtualReadTemps != null ) { + Iterator vrItr = virtualReadTemps.iterator(); + while( vrItr.hasNext() ) { + liveIn.add( vrItr.next() ); + } + } } break; } // end switch @@ -298,10 +313,18 @@ public class MLPAnalysis { VarSrcTokTable prev = variableResults.get( fn ); + // to stay sane + if( state.MLPDEBUG ) { + if( prev != null ) { + prev.assertConsistency(); + } + } + // merge sets from control flow joins VarSrcTokTable inUnion = new VarSrcTokTable(); for( int i = 0; i < fn.numPrev(); i++ ) { FlatNode nn = fn.getPrev( i ); + inUnion.merge( variableResults.get( nn ) ); } @@ -314,9 +337,6 @@ public class MLPAnalysis { // a sanity check after table operations before we proceed if( state.MLPDEBUG ) { - if( prev != null ) { - prev.assertConsistency(); - } curr.assertConsistency(); } @@ -348,8 +368,16 @@ public class MLPAnalysis { FlatSESEExitNode fsexn = (FlatSESEExitNode) fn; FlatSESEEnterNode fsen = fsexn.getFlatEnter(); assert currentSESE.getChildren().contains( fsen ); - vstTable = vstTable.remapChildTokens( fsen ); - vstTable = vstTable.removeParentAndSiblingTokens( fsen ); + vstTable.remapChildTokens( fsen ); + + Set liveIn = livenessResults.get( fn ); + Set virLiveIn = vstTable.removeParentAndSiblingTokens( fsen, liveIn ); + Set virLiveInNew = livenessVirtualReads.get( fn ); + if( virLiveInNew == null ) { + virLiveInNew = new HashSet(); + } + virLiveInNew.addAll( virLiveIn ); + livenessVirtualReads.put( fn, virLiveInNew ); } break; case FKind.FlatOpNode: { diff --git a/Robust/src/Analysis/MLP/SVKey.java b/Robust/src/Analysis/MLP/SVKey.java index d23ea608..b344e99e 100644 --- a/Robust/src/Analysis/MLP/SVKey.java +++ b/Robust/src/Analysis/MLP/SVKey.java @@ -45,6 +45,6 @@ public class SVKey { public String toString() { - return "key["+sese+", "+var+"]"; + return "key["+sese.getPrettyIdentifier()+", "+var+"]"; } } diff --git a/Robust/src/Analysis/MLP/VarSrcTokTable.java b/Robust/src/Analysis/MLP/VarSrcTokTable.java index cc1a798b..9a4bb655 100644 --- a/Robust/src/Analysis/MLP/VarSrcTokTable.java +++ b/Robust/src/Analysis/MLP/VarSrcTokTable.java @@ -151,61 +151,89 @@ public class VarSrcTokTable { // make a copy for modification to use in the merge VarSrcTokTable table = new VarSrcTokTable( tableIn ); + trueSet.addAll( table.trueSet ); + Iterator itr; - Set s; - itr = sese2vst.entrySet().iterator(); + // merge sese2vst mappings + itr = this.sese2vst.entrySet().iterator(); while( itr.hasNext() ) { Map.Entry me = (Map.Entry) itr.next(); FlatSESEEnterNode sese = (FlatSESEEnterNode) me.getKey(); Set s1 = (Set) me.getValue(); - Set s2 = table.sese2vst.get( sese ); - + Set s2 = table.sese2vst.get( sese ); assert s1 != null; if( s2 != null ) { s1.addAll( s2 ); } } - s = table.sese2vst.entrySet(); - s.removeAll( sese2vst.entrySet() ); - sese2vst.putAll( table.sese2vst ); + itr = table.sese2vst.entrySet().iterator(); + while( itr.hasNext() ) { + Map.Entry me = (Map.Entry) itr.next(); + FlatSESEEnterNode sese = (FlatSESEEnterNode) me.getKey(); + Set s2 = (Set) me.getValue(); + Set s1 = this.sese2vst.get( sese ); + assert s2 != null; - itr = var2vst.entrySet().iterator(); + if( s1 == null ) { + this.sese2vst.put( sese, s2 ); + } + } + + // merge var2vst mappings + itr = this.var2vst.entrySet().iterator(); while( itr.hasNext() ) { Map.Entry me = (Map.Entry) itr.next(); TempDescriptor var = (TempDescriptor) me.getKey(); Set s1 = (Set) me.getValue(); - Set s2 = table.var2vst.get( var ); - + Set s2 = table.var2vst.get( var ); assert s1 != null; if( s2 != null ) { s1.addAll( s2 ); } } - s = table.var2vst.entrySet(); - s.removeAll( var2vst.entrySet() ); - var2vst.putAll( table.var2vst ); + itr = table.var2vst.entrySet().iterator(); + while( itr.hasNext() ) { + Map.Entry me = (Map.Entry) itr.next(); + TempDescriptor var = (TempDescriptor) me.getKey(); + Set s2 = (Set) me.getValue(); + Set s1 = this.var2vst.get( var ); + assert s2 != null; + + if( s1 == null ) { + this.var2vst.put( var, s2 ); + } + } - itr = sv2vst.entrySet().iterator(); + // merge sv2vst mappings + itr = this.sv2vst.entrySet().iterator(); while( itr.hasNext() ) { Map.Entry me = (Map.Entry) itr.next(); SVKey key = (SVKey) me.getKey(); Set s1 = (Set) me.getValue(); - Set s2 = table.sv2vst.get( key ); - + Set s2 = table.sv2vst.get( key ); assert s1 != null; if( s2 != null ) { s1.addAll( s2 ); } } - s = table.sv2vst.entrySet(); - s.removeAll( sv2vst.entrySet() ); - sv2vst.putAll( table.sv2vst ); + itr = table.sv2vst.entrySet().iterator(); + while( itr.hasNext() ) { + Map.Entry me = (Map.Entry) itr.next(); + SVKey key = (SVKey) me.getKey(); + Set s2 = (Set) me.getValue(); + Set s1 = this.sv2vst.get( key ); + assert s2 != null; + + if( s1 == null ) { + this.sv2vst.put( key, s2 ); + } + } } @@ -314,10 +342,7 @@ public class VarSrcTokTable { // for the given SESE, change child tokens into this parent - public VarSrcTokTable remapChildTokens( FlatSESEEnterNode curr ) { - - // create a table to modify as a copy of this - VarSrcTokTable out = new VarSrcTokTable( this ); + public void remapChildTokens( FlatSESEEnterNode curr ) { Iterator childItr = curr.getChildren().iterator(); if( childItr.hasNext() ) { @@ -327,61 +352,75 @@ public class VarSrcTokTable { while( vstItr.hasNext() ) { VariableSourceToken vst = vstItr.next(); - out.remove( vst ); + remove( vst ); - out.add( new VariableSourceToken( vst.getVarLive(), - curr, - new Integer( 0 ), - vst.getVarLive() ) ); + add( new VariableSourceToken( vst.getVarLive(), + curr, + new Integer( 0 ), + vst.getVarLive() ) ); } } - - return out; } // if we can get a value from the current SESE and the parent // or a sibling, just getting from the current SESE suffices now - public VarSrcTokTable removeParentAndSiblingTokens( FlatSESEEnterNode curr ) { + // return a set of temps that are virtually read + public Set removeParentAndSiblingTokens( FlatSESEEnterNode curr, + Set liveIn ) { - // create a table to modify as a copy of this - VarSrcTokTable out = new VarSrcTokTable( this ); + HashSet virtualLiveIn = new HashSet(); FlatSESEEnterNode parent = curr.getParent(); if( parent == null ) { // have no parent or siblings - return out; + return virtualLiveIn; } - out.remove_A_if_B( parent, curr ); + remove_A_if_B( parent, curr, liveIn, virtualLiveIn ); Iterator childItr = parent.getChildren().iterator(); if( childItr.hasNext() ) { FlatSESEEnterNode child = childItr.next(); if( !child.equals( curr ) ) { - out.remove_A_if_B( child, curr ); + remove_A_if_B( child, curr, liveIn, virtualLiveIn ); } } - return out; + return virtualLiveIn; } // if B is also a source for some variable, remove all entries - // of A as a source for that variable - protected void remove_A_if_B( FlatSESEEnterNode a, FlatSESEEnterNode b ) { + // of A as a source for that variable: s is virtual reads + protected void remove_A_if_B( FlatSESEEnterNode a, + FlatSESEEnterNode b, + Set liveIn, + Set virtualLiveIn ) { + + Set forRemoval = new HashSet(); Iterator vstItr = get( a ).iterator(); while( vstItr.hasNext() ) { - VariableSourceToken vst = vstItr.next(); - - Set bSet = get( new SVKey( b, vst.getVarLive() ) ); + VariableSourceToken vst = vstItr.next(); + TempDescriptor varLive = vst.getVarLive(); + Set bSet = get( new SVKey( b, varLive ) ); + if( !bSet.isEmpty() ) { - remove( vst ); + forRemoval.add( vst ); // mark this variable as a virtual read as well + if( liveIn.contains( varLive ) ) { + virtualLiveIn.add( varLive ); + } } } + + vstItr = forRemoval.iterator(); + while( vstItr.hasNext() ) { + VariableSourceToken vst = vstItr.next(); + remove( vst ); + } } @@ -421,7 +460,7 @@ public class VarSrcTokTable { // the trueSet should have all entries in s1 assert trueSet.containsAll( s1 ); - // s1 should not have anything that doesn't appear in truese + // s1 should not have anything that doesn't appear in trueset Set sInt = (Set) s1.clone(); sInt.removeAll( trueSet ); @@ -467,4 +506,70 @@ public class VarSrcTokTable { "var2vst ="+var2vst.toString()+"\n"+ "sv2vst ="+sv2vst.toString(); } + + public String toStringPretty() { + String tokHighlighter = "o"; + + String str = "VarSrcTokTable\n"; + + Set s; + Iterator itr; + Iterator vstItr; + + str += " trueSet\n"; + vstItr = trueSet.iterator(); + while( vstItr.hasNext() ) { + str += " "+tokHighlighter+" "+vstItr.next()+"\n"; + } + + str += " sese2vst\n"; + itr = sese2vst.entrySet().iterator(); + while( itr.hasNext() ) { + Map.Entry me = (Map.Entry) itr.next(); + FlatSESEEnterNode sese = (FlatSESEEnterNode) me.getKey(); + HashSet s1 = (HashSet) me.getValue(); + assert s1 != null; + + str += " "+sese.getPrettyIdentifier()+" -> \n"; + + vstItr = s1.iterator(); + while( vstItr.hasNext() ) { + str += " "+tokHighlighter+" "+vstItr.next()+"\n"; + } + } + + str += " var2vst\n"; + itr = var2vst.entrySet().iterator(); + while( itr.hasNext() ) { + Map.Entry me = (Map.Entry) itr.next(); + TempDescriptor var = (TempDescriptor) me.getKey(); + Set s1 = (Set) me.getValue(); + assert s1 != null; + + str += " "+var+" -> \n"; + + vstItr = s1.iterator(); + while( vstItr.hasNext() ) { + str += " "+tokHighlighter+" "+vstItr.next()+"\n"; + } + } + + str += " sv2vst\n"; + itr = sv2vst.entrySet().iterator(); + while( itr.hasNext() ) { + Map.Entry me = (Map.Entry) itr.next(); + SVKey key = (SVKey) me.getKey(); + Set s1 = (Set) me.getValue(); + assert s1 != null; + + str += " "+key+" -> \n"; + + vstItr = s1.iterator(); + while( vstItr.hasNext() ) { + str += " "+tokHighlighter+" "+vstItr.next()+"\n"; + } + } + + return str; + } } diff --git a/Robust/src/Tests/mlp/tinyTest/test.java b/Robust/src/Tests/mlp/tinyTest/test.java index 94291e5f..ebe0a08e 100644 --- a/Robust/src/Tests/mlp/tinyTest/test.java +++ b/Robust/src/Tests/mlp/tinyTest/test.java @@ -19,8 +19,12 @@ public class Test { int z = n + j; */ + int x = 1; + sese fi { - int x = 2; + if( true ) { + x = 2; + } } x = x + 1;