From 9aaefc32be32010976981a1fe735c4d21e2e725e Mon Sep 17 00:00:00 2001 From: jjenista Date: Mon, 7 Nov 2011 21:50:35 +0000 Subject: [PATCH] transfer funcs for the R relation of def reach coded, but buggy, results are empty --- .../Disjoint/DefiniteReachAnalysis.java | 8 ++- .../Analysis/Disjoint/DefiniteReachState.java | 52 ++++++++++++------- .../Analysis/Disjoint/DisjointAnalysis.java | 23 ++++++++ Robust/src/Tests/disjoint/definite/test.java | 3 +- Robust/src/Util/MultiViewMap.java | 23 ++++++++ 5 files changed, 86 insertions(+), 23 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/DefiniteReachAnalysis.java b/Robust/src/Analysis/Disjoint/DefiniteReachAnalysis.java index 6477a8f5..97f2a416 100644 --- a/Robust/src/Analysis/Disjoint/DefiniteReachAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DefiniteReachAnalysis.java @@ -68,11 +68,15 @@ public class DefiniteReachAnalysis { public void methodCall( FlatNode fn, TempDescriptor retVal ) { DefiniteReachState state = makeIn( fn ); - state.methodCall( retVal ); + if( retVal != null ) { + state.methodCall( retVal ); + } fn2state.put( fn, state ); } - + public void otherStatement( FlatNode fn ) { + fn2state.put( fn, makeIn( fn ) ); + } public void writeState( FlatNode fn, String outputName ) { diff --git a/Robust/src/Analysis/Disjoint/DefiniteReachState.java b/Robust/src/Analysis/Disjoint/DefiniteReachState.java index 8006656b..7ab37d97 100644 --- a/Robust/src/Analysis/Disjoint/DefiniteReachState.java +++ b/Robust/src/Analysis/Disjoint/DefiniteReachState.java @@ -17,8 +17,10 @@ public class DefiniteReachState { // NOTE: Use EdgeKey instead of edges because this analysis's // scope is beyond the scope of a single reach graph. private static MultiViewMapBuilder RBuilder; + private static BitSet viewRfull; private static BitSet viewR0; private static BitSet viewR1; + private static BitSet viewR2; private static BitSet viewR01; private MultiViewMap R; @@ -59,9 +61,11 @@ public class DefiniteReachState { TempDescriptor.class, EdgeKey.class }, new JoinOpNop() ); - viewR0 = RBuilder.addPartialView( 0 ); - viewR1 = RBuilder.addPartialView( 1 ); - viewR01 = RBuilder.addPartialView( 0, 1 ); + viewRfull = RBuilder.getFullView(); + viewR0 = RBuilder.addPartialView( 0 ); + viewR1 = RBuilder.addPartialView( 1 ); + viewR2 = RBuilder.addPartialView( 2 ); + viewR01 = RBuilder.addPartialView( 0, 1 ); RBuilder.setCheckTypes( true ); RBuilder.setCheckConsistency( true ); @@ -251,30 +255,34 @@ public class DefiniteReachState { TempDescriptor y, Set edgeKeysRemoved, Set edgeKeysAdded ) { - // I think this should be if there is ANY ->e' IN Eremove, then kill all - // R' := (R - {->e | ->e in R, A->e' in R, e' notin Eremove}) U - // {->e | e in E(x) x {f} x E(y)} - // R' = new Map(R) - // R'.remove(?); some e's... - // R'.put(, E(x) x {f} x E(y)); + + for( EdgeKey edgeKeyWZ : edgeKeysRemoved ) { + R.remove( viewR2, MultiKey.factory( edgeKeyWZ ) ); + } + + for( EdgeKey edgeKeyXY : edgeKeysAdded ) { + R.put( MultiKey.factory( y, x, edgeKeyXY ), MultiViewMap.dummyValue ); + } } public void newObjectR( TempDescriptor x ) { - // R' := (R - - <*,x>) - // R' = new Map(R) - // R'.remove(view0, x); - // R'.remove(view1, x); + MultiKey keyX = MultiKey.factory( x ); + R.remove( viewR0, keyX ); + R.remove( viewR1, keyX ); } public void methodCallR( TempDescriptor retVal ) { - // R' := (R - - <*,x>) - // R' = new Map(R) - // R'.remove(view0, x); - // R'.remove(view1, x); + MultiKey keyRetVal = MultiKey.factory( retVal ); + R.remove( viewR0, keyRetVal ); + R.remove( viewR1, keyRetVal ); } public void mergeR( DefiniteReachState that ) { - // R' := ->e iff its in all incoming edges + for( MultiKey key : this.R.get().keySet() ) { + if( that.R.get( viewRfull, key ).isEmpty() ) { + this.R.remove( viewRfull, key ); + } + } } @@ -334,7 +342,13 @@ public class DefiniteReachState { public String toString() { - StringBuilder s = new StringBuilder( "R_s = {" ); + StringBuilder s = new StringBuilder(); + + s.append( "R = {\n" ); + s.append( R.toString( 2 ) ); + s.append( "}\n" ); + + //s.append( "R_s = {" ); //for( TempDescriptor x : Rs.keySet() ) { // s.append( " "+x+"->"+Rs.get( x ) ); //} diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index 6bde8d8d..37ea4205 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -1313,6 +1313,12 @@ public class DisjointAnalysis implements HeapAnalysis { + + boolean didDefReachTransfer = false; + + + + // use node type to decide what transfer function // to apply to the reachability graph switch( fn.kind() ) { @@ -1379,6 +1385,7 @@ public class DisjointAnalysis implements HeapAnalysis { params.add( fm.getParameter( i ) ); } definiteReachAnalysis.methodEntry( fn, params ); + didDefReachTransfer = true; } } break; @@ -1403,6 +1410,7 @@ public class DisjointAnalysis implements HeapAnalysis { if( doDefiniteReachAnalysis ) { definiteReachAnalysis.copy( fn, lhs, rhs ); + didDefReachTransfer = true; } } break; @@ -1430,6 +1438,7 @@ public class DisjointAnalysis implements HeapAnalysis { if( doDefiniteReachAnalysis ) { definiteReachAnalysis.copy( fn, lhs, rhs ); + didDefReachTransfer = true; } break; @@ -1468,6 +1477,7 @@ public class DisjointAnalysis implements HeapAnalysis { if( doDefiniteReachAnalysis ) { definiteReachAnalysis.load( fn, lhs, rhs, fld, edgeKeysForLoad ); + didDefReachTransfer = true; } } @@ -1530,6 +1540,7 @@ public class DisjointAnalysis implements HeapAnalysis { rhs, edgeKeysRemoved, edgeKeysAdded ); + didDefReachTransfer = true; } } @@ -1578,6 +1589,7 @@ public class DisjointAnalysis implements HeapAnalysis { if( doDefiniteReachAnalysis ) { definiteReachAnalysis.load( fn, lhs, rhs, fdElement, edgeKeysForLoad ); + didDefReachTransfer = true; } } @@ -1646,6 +1658,7 @@ public class DisjointAnalysis implements HeapAnalysis { rhs, edgeKeysRemoved, edgeKeysAdded ); + didDefReachTransfer = true; } } @@ -1675,6 +1688,7 @@ public class DisjointAnalysis implements HeapAnalysis { if( doDefiniteReachAnalysis ) { definiteReachAnalysis.newObject( fn, lhs ); + didDefReachTransfer = true; } } break; @@ -1743,6 +1757,7 @@ public class DisjointAnalysis implements HeapAnalysis { if( doDefiniteReachAnalysis ) { definiteReachAnalysis.methodCall( fn, fc.getReturnTemp() ); + didDefReachTransfer = true; } @@ -1931,6 +1946,14 @@ public class DisjointAnalysis implements HeapAnalysis { } // end switch + + if( doDefiniteReachAnalysis && !didDefReachTransfer ) { + definiteReachAnalysis.otherStatement( fn ); + } + + + + // dead variables were removed before the above transfer function // was applied, so eliminate heap regions and edges that are no // longer part of the abstractly-live heap graph, and sweep up diff --git a/Robust/src/Tests/disjoint/definite/test.java b/Robust/src/Tests/disjoint/definite/test.java index 5e6ea0c0..e2f10cc0 100644 --- a/Robust/src/Tests/disjoint/definite/test.java +++ b/Robust/src/Tests/disjoint/definite/test.java @@ -33,9 +33,8 @@ public class Test { // so we conservatively increase the arity // of objects y is reachable from. genreach y2; + gendefreach y2; - - //gendefreach yo; System.out.println( x+","+y ); } diff --git a/Robust/src/Util/MultiViewMap.java b/Robust/src/Util/MultiViewMap.java index a9ee707f..0a0b8878 100644 --- a/Robust/src/Util/MultiViewMap.java +++ b/Robust/src/Util/MultiViewMap.java @@ -138,6 +138,13 @@ public class MultiViewMap { } + public Map get() { + Map fullKey2valueALL = new HashMap(); + fullKey2valueALL.putAll( fullKey2value ); + return fullKey2valueALL; + } + + public Map get( final BitSet view, MultiKey partialKey ) { checkView( view ); @@ -332,4 +339,20 @@ public class MultiViewMap { return true; } + + public String toString() { + return toString( 0 ); + } + + public String toString( int indent ) { + StringBuilder s = new StringBuilder(); + + for( MultiKey key : fullKey2value.keySet() ) { + for( int i = 0; i < indent; ++i ) { + s.append( ' ' ); + } + s.append( key+" -> "+fullKey2value.get( key )+"\n" ); + } + return s.toString(); + } } -- 2.34.1