From eb3e364c0a9a1a90aa6e445c91f2cedcfde74f7f Mon Sep 17 00:00:00 2001 From: jjenista Date: Thu, 10 Nov 2011 00:38:35 +0000 Subject: [PATCH] AWESOME. Used just the R relation of definite reach to successfully improve the reachability results of a simple example --- .../Disjoint/DefiniteReachAnalysis.java | 7 ++ .../Analysis/Disjoint/DefiniteReachState.java | 22 ++-- .../Analysis/Disjoint/DisjointAnalysis.java | 19 ++-- Robust/src/Analysis/Disjoint/ReachGraph.java | 101 ++++++++++-------- Robust/src/Tests/disjoint/definite/test.java | 19 +--- 5 files changed, 89 insertions(+), 79 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/DefiniteReachAnalysis.java b/Robust/src/Analysis/Disjoint/DefiniteReachAnalysis.java index f8a252ee..e327fcec 100644 --- a/Robust/src/Analysis/Disjoint/DefiniteReachAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DefiniteReachAnalysis.java @@ -34,6 +34,13 @@ public class DefiniteReachAnalysis { } + public boolean isAlreadyReachable( TempDescriptor a, + TempDescriptor b, + FlatNode fn ) { + return makeIn( fn ).isAlreadyReachable( a, b ); + } + + private void addPartialResult( FlatNode fn, DefiniteReachState state ) { fn2state.put( fn, state ); fnHasPartial.add( fn ); diff --git a/Robust/src/Analysis/Disjoint/DefiniteReachState.java b/Robust/src/Analysis/Disjoint/DefiniteReachState.java index e78ab480..d9b0af12 100644 --- a/Robust/src/Analysis/Disjoint/DefiniteReachState.java +++ b/Robust/src/Analysis/Disjoint/DefiniteReachState.java @@ -52,8 +52,6 @@ public class DefiniteReachState { - - // call before instantiating this class static public void initBuilders() { RBuilder = @@ -96,6 +94,15 @@ public class DefiniteReachState { } + + public boolean isAlreadyReachable( TempDescriptor a, + TempDescriptor b ) { + return !R.get( viewR01, MultiKey.factory( a, b ) ).isEmpty(); + } + + + + public void methodEntry( Set parameters ) { methodEntryR( parameters ); @@ -188,14 +195,14 @@ public class DefiniteReachState { public void methodEntryR( Set parameters ) { - //R.clear(); + R.clear(); } public void copyR( TempDescriptor x, TempDescriptor y ) { // consider that x and y can be the same, so do the // parts of the update in the right order: - /* + // first get all info for update MultiKey keyY = MultiKey.factory( y ); Map mapY0 = R.get( viewR0, keyY ); @@ -219,14 +226,12 @@ public class DefiniteReachState { fullKeyY.get( 2 ) ); R.put( fullKeyX, MultiViewMap.dummyValue ); } - */ } public void loadR( TempDescriptor x, TempDescriptor y, FieldDescriptor f, Set edgeKeysForLoad ) { - /* // consider that x and y can be the same, so do the // parts of the update in the right order: @@ -255,7 +260,6 @@ public class DefiniteReachState { MultiViewMap.dummyValue ); } } - */ } public void storeR( TempDescriptor x, @@ -274,19 +278,15 @@ public class DefiniteReachState { } public void newObjectR( TempDescriptor x ) { - /* MultiKey keyX = MultiKey.factory( x ); R.remove( viewR0, keyX ); R.remove( viewR1, keyX ); - */ } public void methodCallR( TempDescriptor retVal ) { - /* MultiKey keyRetVal = MultiKey.factory( retVal ); R.remove( viewR0, keyRetVal ); R.remove( viewR1, keyRetVal ); - */ } public void mergeR( DefiniteReachState that ) { diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index 4b9b4f0d..3128519e 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -1302,6 +1302,7 @@ public class DisjointAnalysis implements HeapAnalysis { FlatSESEEnterNode sese; FlatSESEExitNode fsexn; + boolean alreadyReachable; Set edgeKeysForLoad; Set edgeKeysRemoved; Set edgeKeysAdded; @@ -1495,11 +1496,13 @@ public class DisjointAnalysis implements HeapAnalysis { boolean strongUpdate = false; - edgeKeysRemoved = null; - edgeKeysAdded = null; + alreadyReachable = false; + edgeKeysRemoved = null; + edgeKeysAdded = null; if( doDefiniteReachAnalysis ) { - edgeKeysRemoved = new HashSet(); - edgeKeysAdded = new HashSet(); + alreadyReachable = definiteReachAnalysis.isAlreadyReachable( rhs, lhs, fn ); + edgeKeysRemoved = new HashSet(); + edgeKeysAdded = new HashSet(); } // before transfer func, possibly inject @@ -1529,6 +1532,7 @@ public class DisjointAnalysis implements HeapAnalysis { fld, rhs, fn, + alreadyReachable, edgeKeysRemoved, edgeKeysAdded ); if( doDefiniteReachAnalysis ) { @@ -1609,9 +1613,11 @@ public class DisjointAnalysis implements HeapAnalysis { tdElement = lhs.getType().dereference(); fdElement = getArrayField(tdElement); - edgeKeysRemoved = null; - edgeKeysAdded = null; + alreadyReachable = false; + edgeKeysRemoved = null; + edgeKeysAdded = null; if( doDefiniteReachAnalysis ) { + alreadyReachable = definiteReachAnalysis.isAlreadyReachable( rhs, lhs, fn ); edgeKeysRemoved = new HashSet(); edgeKeysAdded = new HashSet(); } @@ -1645,6 +1651,7 @@ public class DisjointAnalysis implements HeapAnalysis { fdElement, rhs, fn, + alreadyReachable, edgeKeysRemoved, edgeKeysAdded ); } diff --git a/Robust/src/Analysis/Disjoint/ReachGraph.java b/Robust/src/Analysis/Disjoint/ReachGraph.java index 69bece23..8de46b97 100644 --- a/Robust/src/Analysis/Disjoint/ReachGraph.java +++ b/Robust/src/Analysis/Disjoint/ReachGraph.java @@ -426,6 +426,7 @@ public class ReachGraph { fdStringBytesField, tdStrLiteralBytes, null, + false, null, null ); } @@ -594,6 +595,7 @@ public class ReachGraph { FieldDescriptor f, TempDescriptor y, FlatNode currentProgramPoint, + boolean alreadyReachable, Set edgeKeysRemoved, Set edgeKeysAdded ) { @@ -641,53 +643,58 @@ public class ReachGraph { } } - // then do all token propagation - itrXhrn = lnX.iteratorToReferencees(); - while( itrXhrn.hasNext() ) { - RefEdge edgeX = itrXhrn.next(); - HeapRegionNode hrnX = edgeX.getDst(); - ReachSet betaX = edgeX.getBeta(); - ReachSet R = Canonical.intersection(hrnX.getAlpha(), - edgeX.getBeta() - ); - Iterator itrYhrn = lnY.iteratorToReferencees(); - while( itrYhrn.hasNext() ) { - RefEdge edgeY = itrYhrn.next(); - HeapRegionNode hrnY = edgeY.getDst(); - ReachSet O = edgeY.getBeta(); + // definite reachability analysis can elide reachability propagation + if( !alreadyReachable ) { - // check for impossible edges - if( !isSuperiorType(f.getType(), edgeY.getType() ) ) { - impossibleEdges.add(edgeY); - continue; - } + // then do all token propagation + itrXhrn = lnX.iteratorToReferencees(); + while( itrXhrn.hasNext() ) { + RefEdge edgeX = itrXhrn.next(); + HeapRegionNode hrnX = edgeX.getDst(); + ReachSet betaX = edgeX.getBeta(); + ReachSet R = Canonical.intersection(hrnX.getAlpha(), + edgeX.getBeta() + ); - // propagate tokens over nodes starting from hrnSrc, and it will - // take care of propagating back up edges from any touched nodes - ChangeSet Cy = Canonical.unionUpArityToChangeSet(O, R); - propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta); + Iterator itrYhrn = lnY.iteratorToReferencees(); + while( itrYhrn.hasNext() ) { + RefEdge edgeY = itrYhrn.next(); + HeapRegionNode hrnY = edgeY.getDst(); + ReachSet O = edgeY.getBeta(); - // then propagate back just up the edges from hrn - ChangeSet Cx = Canonical.unionUpArityToChangeSet(R, O); - HashSet todoEdges = new HashSet(); + // check for impossible edges + if( !isSuperiorType(f.getType(), edgeY.getType() ) ) { + impossibleEdges.add(edgeY); + continue; + } - Hashtable edgePlannedChanges = - new Hashtable(); + // propagate tokens over nodes starting from hrnSrc, and it will + // take care of propagating back up edges from any touched nodes + ChangeSet Cy = Canonical.unionUpArityToChangeSet(O, R); + propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta); - Iterator referItr = hrnX.iteratorToReferencers(); - while( referItr.hasNext() ) { - RefEdge edgeUpstream = referItr.next(); - todoEdges.add(edgeUpstream); - edgePlannedChanges.put(edgeUpstream, Cx); - } + // then propagate back just up the edges from hrn + ChangeSet Cx = Canonical.unionUpArityToChangeSet(R, O); + HashSet todoEdges = new HashSet(); + + Hashtable edgePlannedChanges = + new Hashtable(); - propagateTokensOverEdges(todoEdges, - edgePlannedChanges, - edgesWithNewBeta); + Iterator referItr = hrnX.iteratorToReferencers(); + while( referItr.hasNext() ) { + RefEdge edgeUpstream = referItr.next(); + todoEdges.add(edgeUpstream); + edgePlannedChanges.put(edgeUpstream, Cx); + } + + propagateTokensOverEdges(todoEdges, + edgePlannedChanges, + edgesWithNewBeta); + } } } - + // apply the updates to reachability Iterator nodeItr = nodesWithNewAlpha.iterator(); @@ -745,17 +752,23 @@ public class ReachGraph { currentProgramPoint); } + + ReachSet betaNew; + if( alreadyReachable ) { + betaNew = edgeY.getBeta(); + } else { + betaNew = Canonical.pruneBy( edgeY.getBeta(), + hrnX.getAlpha() ); + } + + RefEdge edgeNew = new RefEdge(hrnX, hrnY, tdNewEdge, f.getSymbol(), - Canonical.changePredsTo( - Canonical.pruneBy(edgeY.getBeta(), - hrnX.getAlpha() - ), - predsTrue - ), + Canonical.changePredsTo( betaNew, + predsTrue ), predsTrue, taints ); diff --git a/Robust/src/Tests/disjoint/definite/test.java b/Robust/src/Tests/disjoint/definite/test.java index e3ef1b1f..df900914 100644 --- a/Robust/src/Tests/disjoint/definite/test.java +++ b/Robust/src/Tests/disjoint/definite/test.java @@ -9,22 +9,6 @@ public class Test { static public void main( String args[] ) { - Foo x = getFlagged(); - Foo y = getUnflagged(); - - x.f = y; - - gendefreach QWQ1; - - Foo z = x; - while( false ) { - gendefreach QWQ2; - z = z.f; - } - - gendefreach QWQ3; - - /* gendefreach yn1; Foo x = getFlagged(); @@ -54,9 +38,8 @@ public class Test { // of objects y is reachable from. gendefreach y2; genreach y2; - */ - System.out.println( " "+x+y+z ); + System.out.println( " "+x+y ); } static public Foo getFlagged() { -- 2.34.1