From 21ce4adf7bcd53baab74a1cfb6eff87efb4ff679 Mon Sep 17 00:00:00 2001 From: jjenista Date: Fri, 22 Aug 2008 21:28:43 +0000 Subject: [PATCH] steps 1-5 of method call algorithm implemented --- .../OwnershipAnalysis/OwnershipGraph.java | 194 +++++++++++++++++- .../OwnershipAnalysis/TokenTupleSet.java | 9 +- 2 files changed, 192 insertions(+), 11 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 42725d10..875615e5 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -264,14 +264,13 @@ public class OwnershipGraph { todoNodes.remove(n); } - propagateTokensOverEdges(todoEdges, edgePlannedChanges, nodesWithNewAlpha, edgesWithNewBeta); + propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta); } protected void propagateTokensOverEdges( HashSet todoEdges, Hashtable edgePlannedChanges, - HashSet nodesWithNewAlpha, HashSet edgesWithNewBeta) { @@ -444,7 +443,6 @@ public class OwnershipGraph { propagateTokensOverEdges(todoEdges, edgePlannedChanges, - nodesWithNewAlpha, edgesWithNewBeta); @@ -913,7 +911,7 @@ public class OwnershipGraph { Hashtable paramIndex2rewriteD = new Hashtable(); - + // helpful structures Hashtable paramToken2paramIndex = new Hashtable(); @@ -926,7 +924,6 @@ public class OwnershipGraph { Hashtable paramIndex2paramTokenStar = new Hashtable(); - Hashtable paramIndex2ln = new Hashtable(); @@ -1003,6 +1000,10 @@ public class OwnershipGraph { HashSet nodesWithNewAlpha = new HashSet(); + HashSet edgesWithNewBeta = new HashSet(); + + HashSet edgesReachable = new HashSet(); + HashSet edgesUpstream = new HashSet(); Iterator lnArgItr = paramIndex2ln.entrySet().iterator(); while( lnArgItr.hasNext() ) { @@ -1052,16 +1053,95 @@ public class OwnershipGraph { paramIndex2paramTokenStar ); nodesWithNewAlpha.add( hrn ); + + // look at all incoming edges to the reachable nodes + // and sort them as edges reachable from the argument + // label node, or upstream edges + Iterator edgeItr = hrn.iteratorToReferencers(); + while( edgeItr.hasNext() ) { + ReferenceEdge edge = edgeItr.next(); + + OwnershipNode on = edge.getSrc(); + + if( on instanceof LabelNode ) { + + LabelNode ln0 = (LabelNode) on; + if( ln0.equals( lnArg_i ) ) { + edgesReachable.add( edge ); + } else { + edgesUpstream.add( edge ); + } + + } else { + + HeapRegionNode hrn0 = (HeapRegionNode) on; + if( reachableNodes.contains( hrn0 ) ) { + edgesReachable.add( edge ); + } else { + edgesUpstream.add( edge ); + } + } + } + } + + + // update reachable edges + Iterator edgeReachableItr = edgesReachable.iterator(); + while( edgeReachableItr.hasNext() ) { + ReferenceEdge edgeReachable = edgeReachableItr.next(); + + rewriteCallerEdgeBeta( fm.numParameters(), + index, + edgeReachable, + paramIndex2rewriteJ, + paramIndex2rewriteD, + paramIndex2paramToken, + paramIndex2paramTokenStar, + false, + null ); + + edgesWithNewBeta.add( edgeReachable ); + } + + + // update upstream edges + Hashtable edgeUpstreamPlannedChanges + = new Hashtable(); + + Iterator edgeUpstreamItr = edgesUpstream.iterator(); + while( edgeUpstreamItr.hasNext() ) { + ReferenceEdge edgeUpstream = edgeUpstreamItr.next(); + + rewriteCallerEdgeBeta( fm.numParameters(), + index, + edgeUpstream, + paramIndex2rewriteK, + paramIndex2rewriteD, + paramIndex2paramToken, + paramIndex2paramTokenStar, + true, + edgeUpstreamPlannedChanges ); + + edgesWithNewBeta.add( edgeUpstream ); } + + propagateTokensOverEdges( edgesUpstream, + edgeUpstreamPlannedChanges, + edgesWithNewBeta ); } - // commit changes to alpha + // commit changes to alpha and beta Iterator nodeItr = nodesWithNewAlpha.iterator(); while( nodeItr.hasNext() ) { nodeItr.next().applyAlphaNew(); } + Iterator edgeItr = edgesWithNewBeta.iterator(); + while( edgeItr.hasNext() ) { + edgeItr.next().applyBetaNew(); + } + /* @@ -1160,7 +1240,10 @@ public class OwnershipGraph { Iterator ttsItr = rules.iterator(); while( ttsItr.hasNext() ) { TokenTupleSet tts = ttsItr.next(); - r0 = r0.union( tts.rewriteToken( tokenToRewrite, hrn.getAlpha() ) ); + r0 = r0.union( tts.rewriteToken( tokenToRewrite, + hrn.getAlpha(), + false, + null ) ); } ReachabilitySet r1 = new ReachabilitySet().makeCanonical(); @@ -1175,7 +1258,92 @@ public class OwnershipGraph { paramIndex2paramTokenStar ) ); } - hrn.setAlphaNew( r1 ); + hrn.setAlphaNew( hrn.getAlphaNew().union( r1 ) ); + } + + + private void rewriteCallerEdgeBeta( int numParameters, + Integer paramIndex, + ReferenceEdge edge, + Hashtable paramIndex2rewriteJorK, + Hashtable paramIndex2rewriteD, + Hashtable paramIndex2paramToken, + Hashtable paramIndex2paramTokenStar, + boolean makeChangeSet, + Hashtable edgePlannedChanges) { + + ReachabilitySet rules = paramIndex2rewriteJorK.get( paramIndex ); + assert rules != null; + + TokenTuple tokenToRewrite = paramIndex2paramToken.get( paramIndex ); + assert tokenToRewrite != null; + + ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical(); + + Iterator ttsItr = rules.iterator(); + while( ttsItr.hasNext() ) { + TokenTupleSet tts = ttsItr.next(); + + Hashtable forChangeSet = + new Hashtable(); + + ReachabilitySet rTemp = tts.rewriteToken( tokenToRewrite, + edge.getBeta(), + true, + forChangeSet ); + + Iterator fcsItr = forChangeSet.entrySet().iterator(); + while( fcsItr.hasNext() ) { + Map.Entry me = (Map.Entry) fcsItr.next(); + TokenTupleSet ttsMatch = (TokenTupleSet) me.getKey(); + TokenTupleSet ttsAdd = (TokenTupleSet) me.getValue(); + + ChangeTuple ct = new ChangeTuple( ttsMatch, + ttsAdd + ).makeCanonical(); + + cts0 = cts0.union( ct ); + } + } + + + 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(); + + cts1 = cts1.union( ctFinal ); + } + } + } + + if( makeChangeSet ) { + edgePlannedChanges.put( edge, cts1 ); + } + + edge.setBetaNew( edge.getBetaNew().union( r1 ) ); } @@ -1199,7 +1367,10 @@ public class OwnershipGraph { TokenTuple tokenToRewriteJ = paramIndex2paramToken.get( paramIndexJ ); assert tokenToRewriteJ != null; if( ttsIn.containsTuple( tokenToRewriteJ ) ) { - ReachabilitySet r = ttsIn.rewriteToken( tokenToRewriteJ, D_j ); + ReachabilitySet r = ttsIn.rewriteToken( tokenToRewriteJ, + D_j, + false, + null ); Iterator ttsItr = r.iterator(); while( ttsItr.hasNext() ) { TokenTupleSet tts = ttsItr.next(); @@ -1217,7 +1388,10 @@ public class OwnershipGraph { TokenTuple tokenStarToRewriteJ = paramIndex2paramTokenStar.get( paramIndexJ ); assert tokenStarToRewriteJ != null; if( ttsIn.containsTuple( tokenStarToRewriteJ ) ) { - ReachabilitySet r = ttsIn.rewriteToken( tokenStarToRewriteJ, D_j ); + ReachabilitySet r = ttsIn.rewriteToken( tokenStarToRewriteJ, + D_j, + false, + null ); Iterator ttsItr = r.iterator(); while( ttsItr.hasNext() ) { TokenTupleSet tts = ttsItr.next(); diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java index c3acc46b..8dbe4886 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java @@ -209,7 +209,9 @@ public class TokenTupleSet extends Canonical { public ReachabilitySet rewriteToken( TokenTuple tokenToRewrite, - ReachabilitySet replacements ) { + ReachabilitySet replacements, + boolean makeChangeSet, + Hashtable forChangeSet ) { ReachabilitySet rsOut = new ReachabilitySet().makeCanonical(); @@ -226,6 +228,11 @@ public class TokenTupleSet extends Canonical { TokenTupleSet replaced = new TokenTupleSet( ttsMinusToken ); replaced = replaced.unionUpArity( replacement ); rsOut = rsOut.add( replaced ); + + if( makeChangeSet ) { + assert forChangeSet != null; + forChangeSet.put( this, replaced ); + } } } -- 2.34.1