From 368602cf7f0d7082a043fb9da596589f6ca3349f Mon Sep 17 00:00:00 2001 From: jjenista Date: Mon, 22 Sep 2008 22:06:06 +0000 Subject: [PATCH] rewriting of callee tokens into caller tokens was incorrect --- .../OwnershipAnalysis/ChangeTupleSet.java | 4 + .../OwnershipAnalysis/OwnershipGraph.java | 373 +++++++++++------- .../OwnershipAnalysis/ReachabilitySet.java | 3 + Robust/src/Benchmarks/Ownership/makefile | 2 +- 4 files changed, 228 insertions(+), 154 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/ChangeTupleSet.java b/Robust/src/Analysis/OwnershipAnalysis/ChangeTupleSet.java index 9bb1f54c..32a50de1 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ChangeTupleSet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ChangeTupleSet.java @@ -31,6 +31,10 @@ public class ChangeTupleSet extends Canonical { return changeTuples.iterator(); } + public int size() { + return changeTuples.size(); + } + public ChangeTupleSet union(ChangeTupleSet ctsIn) { assert ctsIn != null; diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 4084da96..72726ed4 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -889,6 +889,13 @@ public class OwnershipGraph { FlatMethod fm, OwnershipGraph ogCallee) { + + try { + writeGraph( "caller", true, false, false, false, false ); + ogCallee.writeGraph( "callee", true, false, false, false, false ); + } catch( Exception e ) {} + + // define rewrite rules and other structures to organize // data by parameter/argument index Hashtable paramIndex2rewriteH = @@ -989,7 +996,7 @@ public class OwnershipGraph { if( isStatic ) { argTemp_i = fc.getArg(paramIndex); } else { - if( paramIndex == 0 ) { + if( paramIndex.equals( 0 ) ) { argTemp_i = fc.getThis(); } else { argTemp_i = fc.getArg(paramIndex - 1); @@ -1074,7 +1081,9 @@ public class OwnershipGraph { paramIndex2rewriteH, paramIndex2rewriteD, paramIndex2paramToken, - paramIndex2paramTokenStar); + paramIndex2paramTokenStar, + paramToken2paramIndex, + paramTokenStar2paramIndex); nodesWithNewAlpha.add(hrn); @@ -1120,6 +1129,8 @@ public class OwnershipGraph { paramIndex2rewriteD, paramIndex2paramToken, paramIndex2paramTokenStar, + paramToken2paramIndex, + paramTokenStar2paramIndex, false, null); @@ -1141,6 +1152,8 @@ public class OwnershipGraph { paramIndex2rewriteD, paramIndex2paramToken, paramIndex2paramTokenStar, + paramToken2paramIndex, + paramTokenStar2paramIndex, true, edgeUpstreamPlannedChanges); @@ -1197,7 +1210,9 @@ public class OwnershipGraph { paramIndex2rewriteH, paramIndex2rewriteD, paramIndex2paramToken, - paramIndex2paramTokenStar); + paramIndex2paramTokenStar, + paramToken2paramIndex, + paramTokenStar2paramIndex); hrnShadowSummary.applyAlphaNew(); @@ -1225,7 +1240,9 @@ public class OwnershipGraph { paramIndex2rewriteH, paramIndex2rewriteD, paramIndex2paramToken, - paramIndex2paramTokenStar); + paramIndex2paramTokenStar, + paramToken2paramIndex, + paramTokenStar2paramIndex); hrnIthShadow.applyAlphaNew(); } @@ -1274,6 +1291,8 @@ public class OwnershipGraph { paramIndex2rewriteD, paramIndex2paramToken, paramIndex2paramTokenStar, + paramToken2paramIndex, + paramTokenStar2paramIndex, false, null); @@ -1358,6 +1377,8 @@ public class OwnershipGraph { paramIndex2rewriteD, paramIndex2paramToken, paramIndex2paramTokenStar, + paramToken2paramIndex, + paramTokenStar2paramIndex, false, null); @@ -1552,43 +1573,97 @@ public class OwnershipGraph { } + + // TODO: this and rewriteCallerEdgeBeta turned out to be almost + // the same code, combine into a single more flexible method + private void rewriteCallerNodeAlpha(int numParameters, Integer paramIndex, HeapRegionNode hrn, Hashtable paramIndex2rewriteH, Hashtable paramIndex2rewriteD, Hashtable paramIndex2paramToken, - Hashtable paramIndex2paramTokenStar) { + Hashtable paramIndex2paramTokenStar, + Hashtable paramToken2paramIndex, + Hashtable paramTokenStar2paramIndex ) { + + ReachabilitySet callerReachability = new ReachabilitySet().makeCanonical(); ReachabilitySet rules = paramIndex2rewriteH.get(paramIndex); assert rules != null; - TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex); - assert tokenToRewrite != null; + TokenTuple p_i = paramIndex2paramToken.get(paramIndex); + assert p_i != null; + + Iterator rulesItr = rules.iterator(); + while(rulesItr.hasNext()) { + TokenTupleSet rule = rulesItr.next(); + + TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical(); + ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical(); + + Iterator ruleItr = rule.iterator(); + while(ruleItr.hasNext()) { + TokenTuple ttCallee = ruleItr.next(); + + // compute the possibilities for rewriting this callee token + ReachabilitySet ttCalleeRewrites = null; + + if( ttCallee.equals( p_i ) ) { + // replace the arity-one token of the current parameter with the reachability + // information from the caller node + ttCalleeRewrites = hrn.getAlpha(); + + } else if( paramToken2paramIndex.containsKey( ttCallee ) || + paramTokenStar2paramIndex.containsKey( ttCallee ) ) { + // this token is another callee parameter, or any ARITY_MANY callee parameter, + // so rewrite it with the D rules for that parameter + Integer paramIndex_j; + if( paramToken2paramIndex.containsKey( ttCallee ) ) { + paramIndex_j = paramToken2paramIndex.get( ttCallee ); + } else { + paramIndex_j = paramTokenStar2paramIndex.get( ttCallee ); + } - ReachabilitySet r0 = new ReachabilitySet().makeCanonical(); - Iterator ttsItr = rules.iterator(); - while( ttsItr.hasNext() ) { - TokenTupleSet tts = ttsItr.next(); - r0 = r0.union(tts.rewriteToken(tokenToRewrite, - hrn.getAlpha(), - false, - null) ); - } + ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j ); + assert ttCalleeRewrites != null; - ReachabilitySet r1 = new ReachabilitySet().makeCanonical(); - ttsItr = r0.iterator(); - while( ttsItr.hasNext() ) { - TokenTupleSet tts = ttsItr.next(); - r1 = r1.union(rewriteDpass(numParameters, - paramIndex, - tts, - paramIndex2rewriteD, - paramIndex2paramToken, - paramIndex2paramTokenStar) ); + } else { + // otherwise there's no need for a rewrite, just pass this one on + TokenTupleSet ttsCaller = new TokenTupleSet(ttCallee).makeCanonical(); + ttCalleeRewrites = new ReachabilitySet(ttsCaller).makeCanonical(); + } + + // branch every version of the working rewritten rule with + // the possibilities for rewriting the current callee token + ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical(); + + Iterator rewrittenRuleItr = rewrittenRule.iterator(); + while( rewrittenRuleItr.hasNext() ) { + TokenTupleSet ttsRewritten = rewrittenRuleItr.next(); + + Iterator ttCalleeRewritesItr = ttCalleeRewrites.iterator(); + while( ttCalleeRewritesItr.hasNext() ) { + TokenTupleSet ttsBranch = ttCalleeRewritesItr.next(); + + rewrittenRuleWithTTCallee = + rewrittenRuleWithTTCallee.union( ttsRewritten.unionUpArity( ttsBranch ) ); + } + } + + // now the rewritten rule's possibilities have been extended by + // rewriting the current callee token, remember result + rewrittenRule = rewrittenRuleWithTTCallee; + } + + // the rule has been entirely rewritten into the caller context + // now, so add it to the new reachability information + callerReachability = + callerReachability.union( rewrittenRule ); } - hrn.setAlphaNew(hrn.getAlphaNew().union(r1) ); + // finally update caller node with new information + hrn.setAlphaNew(hrn.getAlphaNew().union(callerReachability) ); } @@ -1599,155 +1674,147 @@ public class OwnershipGraph { Hashtable paramIndex2rewriteD, Hashtable paramIndex2paramToken, Hashtable paramIndex2paramTokenStar, + Hashtable paramToken2paramIndex, + Hashtable paramTokenStar2paramIndex, boolean makeChangeSet, Hashtable edgePlannedChanges) { - ReachabilitySet rules = paramIndex2rewriteJorK.get(paramIndex); - assert rules != null; - - TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex); - assert tokenToRewrite != null; + ReachabilitySet callerReachability = new ReachabilitySet().makeCanonical(); - ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical(); + // for initializing structures in this method + TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical(); - Iterator ttsItr = rules.iterator(); - while( ttsItr.hasNext() ) { - TokenTupleSet tts = ttsItr.next(); + // use this to construct a change set if required; the idea is to + // map every partially rewritten token tuple set to the set of + // caller-context token tuple sets that were used to generate it + Hashtable > rewritten2source = + new Hashtable >(); + rewritten2source.put(ttsEmpty, new HashSet() ); - Hashtable > forChangeSet = - new Hashtable >(); - - ReachabilitySet rTemp = tts.rewriteToken(tokenToRewrite, - edge.getBeta(), - true, - forChangeSet); + ReachabilitySet rules = paramIndex2rewriteJorK.get(paramIndex); + assert rules != null; - Iterator fcsItr = forChangeSet.entrySet().iterator(); - while( fcsItr.hasNext() ) { - Map.Entry me = (Map.Entry)fcsItr.next(); - TokenTupleSet ttsMatch = (TokenTupleSet) me.getKey(); - HashSet ttsAddSet = (HashSet) me.getValue(); - Iterator ttsAddItr = ttsAddSet.iterator(); - while( ttsAddItr.hasNext() ) { - TokenTupleSet ttsAdd = ttsAddItr.next(); + TokenTuple p_i = paramIndex2paramToken.get(paramIndex); + assert p_i != null; + + Iterator rulesItr = rules.iterator(); + while(rulesItr.hasNext()) { + TokenTupleSet rule = rulesItr.next(); + + ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical(); + + Iterator ruleItr = rule.iterator(); + while(ruleItr.hasNext()) { + TokenTuple ttCallee = ruleItr.next(); + + // compute the possibilities for rewriting this callee token + ReachabilitySet ttCalleeRewrites = null; + boolean callerSourceUsed = false; + + if( ttCallee.equals( p_i ) ) { + // replace the arity-one token of the current parameter with the reachability + // information from the caller edge + ttCalleeRewrites = edge.getBeta(); + callerSourceUsed = true; + + } else if( paramToken2paramIndex.containsKey( ttCallee ) || + paramTokenStar2paramIndex.containsKey( ttCallee ) ) { + // this token is another callee parameter, or any ARITY_MANY callee parameter, + // so rewrite it with the D rules for that parameter + Integer paramIndex_j; + if( paramToken2paramIndex.containsKey( ttCallee ) ) { + paramIndex_j = paramToken2paramIndex.get( ttCallee ); + } else { + paramIndex_j = paramTokenStar2paramIndex.get( ttCallee ); + } - ChangeTuple ct = new ChangeTuple(ttsMatch, - ttsAdd - ).makeCanonical(); + ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j ); + assert ttCalleeRewrites != null; - cts0 = cts0.union(ct); + } else { + // otherwise there's no need for a rewrite, just pass this one on + TokenTupleSet ttsCaller = new TokenTupleSet(ttCallee).makeCanonical(); + ttCalleeRewrites = new ReachabilitySet(ttsCaller).makeCanonical(); } - } - } - - - ReachabilitySet r1 = new ReachabilitySet().makeCanonical(); - ChangeTupleSet cts1 = new ChangeTupleSet().makeCanonical(); - - Iterator ctItr = cts0.iterator(); - while( ctItr.hasNext() ) { - ChangeTuple ct = ctItr.next(); - - ReachabilitySet rTemp = rewriteDpass(numParameters, - paramIndex, - ct.getSetToAdd(), - paramIndex2rewriteD, - paramIndex2paramToken, - paramIndex2paramTokenStar - ).makeCanonical(); - r1 = r1.union(rTemp); - - if( makeChangeSet ) { - assert edgePlannedChanges != null; - - Iterator ttsTempItr = rTemp.iterator(); - while( ttsTempItr.hasNext() ) { - TokenTupleSet tts = ttsTempItr.next(); - - ChangeTuple ctFinal = new ChangeTuple(ct.getSetToMatch(), - tts - ).makeCanonical(); + + // branch every version of the working rewritten rule with + // the possibilities for rewriting the current callee token + ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical(); + + Iterator rewrittenRuleItr = rewrittenRule.iterator(); + while( rewrittenRuleItr.hasNext() ) { + TokenTupleSet ttsRewritten = rewrittenRuleItr.next(); + + Iterator ttCalleeRewritesItr = ttCalleeRewrites.iterator(); + while( ttCalleeRewritesItr.hasNext() ) { + TokenTupleSet ttsBranch = ttCalleeRewritesItr.next(); + + TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity( ttsBranch ); + + if( makeChangeSet ) { + // in order to keep the list of source token tuple sets + // start with the sets used to make the partially rewritten + // rule up to this point + HashSet sourceSets = rewritten2source.get( ttsRewritten ); + assert sourceSets != null; + + // make a shallow copy for possible modification + sourceSets = (HashSet) sourceSets.clone(); + + // if we used something from the caller to rewrite it, remember + if( callerSourceUsed ) { + sourceSets.add( ttsBranch ); + } - cts1 = cts1.union(ctFinal); + // set mapping for the further rewritten rule + rewritten2source.put( ttsRewrittenNext, sourceSets ); + } + + rewrittenRuleWithTTCallee = + rewrittenRuleWithTTCallee.union( ttsRewrittenNext ); + } } + + // now the rewritten rule's possibilities have been extended by + // rewriting the current callee token, remember result + rewrittenRule = rewrittenRuleWithTTCallee; } - } - if( makeChangeSet ) { - edgePlannedChanges.put(edge, cts1); + // the rule has been entirely rewritten into the caller context + // now, so add it to the new reachability information + callerReachability = + callerReachability.union( rewrittenRule ); } - edge.setBetaNew(edge.getBetaNew().union(r1) ); - } - - - private ReachabilitySet rewriteDpass(int numParameters, - Integer paramIndex, - TokenTupleSet ttsIn, - Hashtable paramIndex2rewriteD, - Hashtable paramIndex2paramToken, - Hashtable paramIndex2paramTokenStar) { - - ReachabilitySet rsOut = new ReachabilitySet().makeCanonical(); - - boolean rewritten = false; - - for( int j = 0; j < numParameters; ++j ) { - Integer paramIndexJ = new Integer(j); - ReachabilitySet D_j = paramIndex2rewriteD.get(paramIndexJ); - assert D_j != null; - - if( paramIndexJ != paramIndex ) { - TokenTuple tokenToRewriteJ = paramIndex2paramToken.get(paramIndexJ); - assert tokenToRewriteJ != null; - if( ttsIn.containsTuple(tokenToRewriteJ) ) { - ReachabilitySet r = ttsIn.rewriteToken(tokenToRewriteJ, - D_j, - false, - null); - Iterator ttsItr = r.iterator(); - while( ttsItr.hasNext() ) { - TokenTupleSet tts = ttsItr.next(); - rsOut = rsOut.union(rewriteDpass(numParameters, - paramIndex, - tts, - paramIndex2rewriteD, - paramIndex2paramToken, - paramIndex2paramTokenStar) ); - rewritten = true; - } - } - } - - TokenTuple tokenStarToRewriteJ = paramIndex2paramTokenStar.get(paramIndexJ); - assert tokenStarToRewriteJ != null; - if( ttsIn.containsTuple(tokenStarToRewriteJ) ) { - ReachabilitySet r = ttsIn.rewriteToken(tokenStarToRewriteJ, - D_j, - false, - null); - Iterator ttsItr = r.iterator(); - while( ttsItr.hasNext() ) { - TokenTupleSet tts = ttsItr.next(); - rsOut = rsOut.union(rewriteDpass(numParameters, - paramIndex, - tts, - paramIndex2rewriteD, - paramIndex2paramToken, - paramIndex2paramTokenStar) ); - rewritten = true; + if( makeChangeSet ) { + ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical(); + + // each possibility for the final reachability should have a set of + // caller sources mapped to it, use to create the change set + Iterator callerReachabilityItr = callerReachability.iterator(); + while( callerReachabilityItr.hasNext() ) { + TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next(); + HashSet sourceSets = rewritten2source.get( ttsRewrittenFinal ); + assert sourceSets != null; + + Iterator sourceSetsItr = sourceSets.iterator(); + while( sourceSetsItr.hasNext() ) { + TokenTupleSet ttsSource = sourceSetsItr.next(); + + callerChangeSet = + callerChangeSet.union( new ChangeTuple( ttsSource, ttsRewrittenFinal ) ); } } - } - if( !rewritten ) { - rsOut = rsOut.union(ttsIn); + assert edgePlannedChanges != null; + edgePlannedChanges.put(edge, callerChangeSet); } - return rsOut; + edge.setBetaNew(edge.getBetaNew().union(callerReachability) ); } + private HashSet getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee, HeapRegionNode hrnCallee, @@ -2638,7 +2705,7 @@ public class OwnershipGraph { } } - bw.write(ln.toString() + ";\n"); + //bw.write(" "+ln.toString() + ";\n"); Iterator heapRegionsItr = ln.iteratorToReferencees(); while( heapRegionsItr.hasNext() ) { diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java index 3c1fa840..8e6576d1 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java @@ -51,6 +51,9 @@ public class ReachabilitySet extends Canonical { return possibleReachabilities.size(); } + public boolean isEmpty() { + return possibleReachabilities.isEmpty(); + } public boolean contains(TokenTupleSet tts) { assert tts != null; diff --git a/Robust/src/Benchmarks/Ownership/makefile b/Robust/src/Benchmarks/Ownership/makefile index ef4eedfd..7c6e1803 100644 --- a/Robust/src/Benchmarks/Ownership/makefile +++ b/Robust/src/Benchmarks/Ownership/makefile @@ -1,5 +1,5 @@ BUILDSCRIPT=~/research/Robust/src/buildscript -BSFLAGS= -recover -ownership -ownaliasfile aliases.txt -enable-assertions #-flatirtasks -ownwritedots final +BSFLAGS= -recover -ownership -ownaliasfile aliases.txt -enable-assertions -ownwritedots final #-flatirtasks AD1= -ownallocdepth 1 AD3= -ownallocdepth 3 AD5= -ownallocdepth 5 -- 2.34.1