From 559454fc35f7bdf2a8e5ba5e9c71d8ac20d23bc7 Mon Sep 17 00:00:00 2001 From: jjenista Date: Mon, 4 May 2009 17:29:24 +0000 Subject: [PATCH] convert token tables into triples that sets of reference temps map to, instead of quadruples that duplicate data. Moved table consistency checks from analysis level to the exit of table-modification methods. Note: this capture compiles but fails consistency checks\! --- Robust/src/Analysis/MLP/MLPAnalysis.java | 47 ++-- Robust/src/Analysis/MLP/VarSrcTokTable.java | 207 ++++++++++++++---- .../src/Analysis/MLP/VariableSourceToken.java | 45 ++-- 3 files changed, 200 insertions(+), 99 deletions(-) diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index 0b4c9504..1413fbc5 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -297,21 +297,21 @@ public class MLPAnalysis { 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 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]); - } + 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]); + } } } @@ -349,13 +349,6 @@ 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++ ) { @@ -364,18 +357,8 @@ public class MLPAnalysis { inUnion.merge( variableResults.get( nn ) ); } - // check merge results before sending - if( state.MLPDEBUG ) { - inUnion.assertConsistency(); - } - VarSrcTokTable curr = variable_nodeActions( fn, inUnion, seseStack.peek() ); - // a sanity check after table operations before we proceed - if( state.MLPDEBUG ) { - curr.assertConsistency(); - } - // if a new result, schedule forward nodes for analysis if( !curr.equals( prev ) ) { @@ -428,19 +411,22 @@ public class MLPAnalysis { while( itr.hasNext() ) { VariableSourceToken vst = itr.next(); + HashSet ts = new HashSet(); + ts.add( lhs ); + // if this is from a child, keep the source information if( currentSESE.getChildren().contains( vst.getSESE() ) ) { - vstTable.add( new VariableSourceToken( lhs, + vstTable.add( new VariableSourceToken( ts, vst.getSESE(), vst.getAge(), - vst.getVarSrc() + vst.getAddrVar() ) ); // otherwise, it's our or an ancestor's token so we // can assume we have everything we need } else { - vstTable.add( new VariableSourceToken( lhs, + vstTable.add( new VariableSourceToken( ts, currentSESE, new Integer( 0 ), lhs @@ -464,7 +450,10 @@ public class MLPAnalysis { vstTable.remove( writeTemps[0] ); - vstTable.add( new VariableSourceToken( writeTemps[0], + HashSet ts = new HashSet(); + ts.add( writeTemps[0] ); + + vstTable.add( new VariableSourceToken( ts, currentSESE, new Integer( 0 ), writeTemps[0] diff --git a/Robust/src/Analysis/MLP/VarSrcTokTable.java b/Robust/src/Analysis/MLP/VarSrcTokTable.java index b01a16f6..6191ce7a 100644 --- a/Robust/src/Analysis/MLP/VarSrcTokTable.java +++ b/Robust/src/Analysis/MLP/VarSrcTokTable.java @@ -71,6 +71,8 @@ public class VarSrcTokTable { sv2vst.put( key, (HashSet) (s1.clone()) ); } + + assertConsistency(); } @@ -86,20 +88,26 @@ public class VarSrcTokTable { s.add( vst ); sese2vst.put( vst.getSESE(), s ); - s = var2vst.get( vst.getVarLive() ); - if( s == null ) { - s = new HashSet(); - } - s.add( vst ); - var2vst.put( vst.getVarLive(), s ); + Iterator refVarItr = vst.getRefVars().iterator(); + while( refVarItr.hasNext() ) { + TempDescriptor refVar = refVarItr.next(); + s = var2vst.get( refVar ); + if( s == null ) { + s = new HashSet(); + } + s.add( vst ); + var2vst.put( refVar, s ); - SVKey key = new SVKey( vst.getSESE(), vst.getVarLive() ); - s = sv2vst.get( key ); - if( s == null ) { - s = new HashSet(); + SVKey key = new SVKey( vst.getSESE(), refVar ); + s = sv2vst.get( key ); + if( s == null ) { + s = new HashSet(); + } + s.add( vst ); + sv2vst.put( key, s ); } - s.add( vst ); - sv2vst.put( key, s ); + + assertConsistency(); } public void addAll( Set s ) { @@ -132,7 +140,9 @@ public class VarSrcTokTable { return s; } - public Set get( SVKey key ) { + public Set get( FlatSESEEnterNode sese, + TempDescriptor refVar ) { + SVKey key = new SVKey( sese, refVar ); Set s = sv2vst.get( key ); if( s == null ) { s = new HashSet(); @@ -141,6 +151,23 @@ public class VarSrcTokTable { return s; } + public Set get( FlatSESEEnterNode sese, + Integer age ) { + Set s = sese2vst.get( sese ); + if( s == null ) { + s = new HashSet(); + sese2vst.put( sese, s ); + } + Iterator sItr = s.iterator(); + while( sItr.hasNext() ) { + VariableSourceToken vst = sItr.next(); + if( !vst.getAge().equals( age ) ) { + s.remove( vst ); + } + } + return s; + } + public void merge( VarSrcTokTable tableIn ) { @@ -234,6 +261,8 @@ public class VarSrcTokTable { this.sv2vst.put( key, s2 ); } } + + assertConsistency(); } @@ -247,11 +276,18 @@ public class VarSrcTokTable { s = get( vst.getSESE() ); if( s != null ) { s.remove( vst ); } - s = get( vst.getVarLive() ); - if( s != null ) { s.remove( vst ); } + Iterator refVarItr = vst.getRefVars().iterator(); + while( refVarItr.hasNext() ) { + TempDescriptor refVar = refVarItr.next(); - s = get( new SVKey( vst.getSESE(), vst.getVarLive() ) ); - if( s != null ) { s.remove( vst ); } + s = get( refVar ); + if( s != null ) { s.remove( vst ); } + + s = get( vst.getSESE(), refVar ); + if( s != null ) { s.remove( vst ); } + } + + assertConsistency(); } public void remove( FlatSESEEnterNode sese ) { @@ -259,31 +295,56 @@ public class VarSrcTokTable { if( s == null ) { return; } - - trueSet.removeAll( s ); - sese2vst.remove( sese ); Iterator itr = s.iterator(); while( itr.hasNext() ) { VariableSourceToken vst = itr.next(); remove( vst ); } + + sese2vst.remove( sese ); + + assertConsistency(); } - public void remove( TempDescriptor var ) { - Set s = var2vst.get( var ); + public void remove( TempDescriptor refVar ) { + Set s = var2vst.get( refVar ); if( s == null ) { return; } - trueSet.removeAll( s ); - var2vst.remove( var ); + Set forRemoval = new HashSet(); + // iterate over tokens that this temp can reference, make a set + // of tokens that need this temp stripped out of them Iterator itr = s.iterator(); while( itr.hasNext() ) { + VariableSourceToken vst = itr.next(); + Set refVars = vst.getRefVars(); + assert refVars.contains( refVar ); + forRemoval.add( vst ); + } + + itr = forRemoval.iterator(); + while( itr.hasNext() ) { + // here's a token marked for removal, take it out as it is + // in this state VariableSourceToken vst = itr.next(); remove( vst ); + + // if there are other references to the token, alter the + // token and then readd it to this table, because it has + // a new hash value now + Set refVars = vst.getRefVars(); + refVars.remove( refVar ); + if( refVars.size() > 0 ) { + add( vst ); + } } + + //var2vst.remove( var ); + + assertConsistency(); } public void remove( FlatSESEEnterNode sese, @@ -295,14 +356,15 @@ public class VarSrcTokTable { return; } - trueSet.removeAll( s ); - sv2vst.remove( key ); - Iterator itr = s.iterator(); while( itr.hasNext() ) { VariableSourceToken vst = itr.next(); remove( vst ); } + + sv2vst.remove( key ); + + assertConsistency(); } @@ -328,15 +390,16 @@ public class VarSrcTokTable { out.remove( vst ); - out.add( new VariableSourceToken( vst.getVarLive(), + out.add( new VariableSourceToken( vst.getRefVars(), curr, newAge, - vst.getVarSrc() + vst.getAddrVar() ) ); } } + out.assertConsistency(); return out; } @@ -354,12 +417,16 @@ public class VarSrcTokTable { remove( vst ); - add( new VariableSourceToken( vst.getVarLive(), + add( new VariableSourceToken( vst.getRefVars(), curr, new Integer( 0 ), - vst.getVarLive() ) ); + vst.getAddrVar() + ) + ); } } + + assertConsistency(); } @@ -388,6 +455,7 @@ public class VarSrcTokTable { } } + assertConsistency(); return virtualLiveIn; } @@ -402,26 +470,23 @@ public class VarSrcTokTable { Iterator vstItr = get( a ).iterator(); while( vstItr.hasNext() ) { - VariableSourceToken vst = vstItr.next(); - TempDescriptor varLive = vst.getVarLive(); - Set bSet = get( new SVKey( b, varLive ) ); + VariableSourceToken vst = vstItr.next(); + Iterator refVarItr = vst.getRefVars().iterator(); + while( refVarItr.hasNext() ) { + TempDescriptor refVar = refVarItr.next(); + Set bSet = get( b, refVar ); - if( !bSet.isEmpty() ) { - forRemoval.add( vst ); - - // mark this variable as a virtual read as well - //if( liveInCurrentSESE.contains( varLive ) ) { ??????????? - virtualLiveIn.add( varLive ); - //} + if( !bSet.isEmpty() ) { + forRemoval.add( vst ); + + // mark this variable as a virtual read as well + //if( liveInCurrentSESE.contains( varLive ) ) { ??????????? + virtualLiveIn.add( refVar ); + //} + } } } - /* - System.out.println( "remove "+a.getPrettyIdentifier()+" if "+b.getPrettyIdentifier() ); - System.out.println( "THIS "+toStringPretty() ); - System.out.println( "for removal="+forRemoval ); - */ - vstItr = forRemoval.iterator(); while( vstItr.hasNext() ) { VariableSourceToken vst = vstItr.next(); @@ -453,7 +518,6 @@ public class VarSrcTokTable { Set s; Set trueSetByAlts = new HashSet(); - itr = sese2vst.entrySet().iterator(); while( itr.hasNext() ) { Map.Entry me = (Map.Entry) itr.next(); @@ -473,7 +537,54 @@ public class VarSrcTokTable { // add s1 to a running union--at the end check if trueSet has extra trueSetByAlts.addAll( s1 ); } + // make sure trueSet isn't too big + assert trueSetByAlts.containsAll( trueSet ); + + + trueSetByAlts = new HashSet(); + itr = var2vst.entrySet().iterator(); + while( itr.hasNext() ) { + Map.Entry me = (Map.Entry) itr.next(); + TempDescriptor var = (TempDescriptor) me.getKey(); + HashSet s1 = (HashSet) me.getValue(); + assert s1 != null; + + // the trueSet should have all entries in s1 + assert trueSet.containsAll( s1 ); + + // s1 should not have anything that doesn't appear in trueset + Set sInt = (Set) s1.clone(); + sInt.removeAll( trueSet ); + + assert sInt.isEmpty(); + // add s1 to a running union--at the end check if trueSet has extra + trueSetByAlts.addAll( s1 ); + } + // make sure trueSet isn't too big + assert trueSetByAlts.containsAll( trueSet ); + + + trueSetByAlts = new HashSet(); + itr = sv2vst.entrySet().iterator(); + while( itr.hasNext() ) { + Map.Entry me = (Map.Entry) itr.next(); + SVKey key = (SVKey) me.getKey(); + HashSet s1 = (HashSet) me.getValue(); + assert s1 != null; + + // the trueSet should have all entries in s1 + assert trueSet.containsAll( s1 ); + + // s1 should not have anything that doesn't appear in trueset + Set sInt = (Set) s1.clone(); + sInt.removeAll( trueSet ); + + assert sInt.isEmpty(); + + // add s1 to a running union--at the end check if trueSet has extra + trueSetByAlts.addAll( s1 ); + } // make sure trueSet isn't too big assert trueSetByAlts.containsAll( trueSet ); } diff --git a/Robust/src/Analysis/MLP/VariableSourceToken.java b/Robust/src/Analysis/MLP/VariableSourceToken.java index 26a18aae..a8fd33ce 100644 --- a/Robust/src/Analysis/MLP/VariableSourceToken.java +++ b/Robust/src/Analysis/MLP/VariableSourceToken.java @@ -7,36 +7,36 @@ import java.io.*; public class VariableSourceToken { - private TempDescriptor varLive; - private FlatSESEEnterNode seseSrc; - private Integer seseAge; - private TempDescriptor varSrc; + private Set refVars; + private FlatSESEEnterNode sese; + private Integer seseAge; + private TempDescriptor addrVar; - public VariableSourceToken( TempDescriptor varLive, - FlatSESEEnterNode seseSrc, - Integer seseAge, - TempDescriptor varSrc + public VariableSourceToken( Set refVars, + FlatSESEEnterNode sese, + Integer seseAge, + TempDescriptor addrVar ) { - this.varLive = varLive; - this.seseSrc = seseSrc; + this.refVars = refVars; + this.sese = sese; this.seseAge = seseAge; - this.varSrc = varSrc; + this.addrVar = addrVar; } - public TempDescriptor getVarLive() { - return varLive; + public Set getRefVars() { + return refVars; } public FlatSESEEnterNode getSESE() { - return seseSrc; + return sese; } public Integer getAge() { return seseAge; } - public TempDescriptor getVarSrc() { - return varSrc; + public TempDescriptor getAddrVar() { + return addrVar; } public boolean equals( Object o ) { @@ -50,18 +50,19 @@ public class VariableSourceToken { VariableSourceToken vst = (VariableSourceToken) o; - return seseSrc.equals( vst.seseSrc ) && - varSrc.equals( vst.varSrc ) && - seseAge.equals( vst.seseAge ) && - varLive.equals( vst.varLive ); + // the reference vars have no bearing on equality + return sese.equals( vst.sese ) && + addrVar.equals( vst.addrVar ) && + seseAge.equals( vst.seseAge ); } public int hashCode() { - return (seseSrc.hashCode() << 3) + (varSrc.hashCode() << 4) * (varLive.hashCode() << 2) ^ seseAge.intValue(); + // the reference vars have no bearing on hashCode + return (sese.hashCode() << 3) * (addrVar.hashCode() << 4) ^ seseAge.intValue(); } public String toString() { - return varLive+" from "+varSrc+" in "+seseSrc.getPrettyIdentifier()+"("+seseAge+")"; + return refVars+" ref "+addrVar+"@"+sese.getPrettyIdentifier()+"("+seseAge+")"; } } -- 2.34.1