From 433a3c7010c85e446758db36496c593bae986c84 Mon Sep 17 00:00:00 2001 From: jjenista Date: Thu, 17 Nov 2011 23:31:18 +0000 Subject: [PATCH] case 3 of definite reach, all coded but has bugs because test case does the messy store anyway still --- .../Analysis/Disjoint/DefiniteReachState.java | 250 ++++++++++++++---- Robust/src/Tests/disjoint/definite3/makefile | 25 ++ Robust/src/Tests/disjoint/definite3/test.java | 56 ++++ 3 files changed, 282 insertions(+), 49 deletions(-) create mode 100644 Robust/src/Tests/disjoint/definite3/makefile create mode 100644 Robust/src/Tests/disjoint/definite3/test.java diff --git a/Robust/src/Analysis/Disjoint/DefiniteReachState.java b/Robust/src/Analysis/Disjoint/DefiniteReachState.java index 09f2ff4d..25e6a2f0 100644 --- a/Robust/src/Analysis/Disjoint/DefiniteReachState.java +++ b/Robust/src/Analysis/Disjoint/DefiniteReachState.java @@ -25,6 +25,7 @@ public class DefiniteReachState { private static BitSet viewR01; private MultiViewMap R; + // Rs // // Tracks whether the analysis must know the definite reachability @@ -41,10 +42,43 @@ public class DefiniteReachState { // Maps a variable that points to object o0 to the // set of variables that point to objects o1...oN // that have a reference to o0. - //private static MultiViewMapBuilder FuBuilder; - //private static BitSet viewFu0; - //private static BitSet viewFu1; - //private MultiViewMap Fu; + private class FuSource { + DefReachKnown isKnown; + TempDescriptor knownSrc; + public FuSource() { + this.isKnown = DefReachKnown.UNKNOWN; + this.knownSrc = null; + } + public FuSource( TempDescriptor src ) { + assert( src != null ); + this.isKnown = DefReachKnown.KNOWN; + this.knownSrc = src; + } + public boolean equals( Object o ) { + if( !(o instanceof FuSource) ) { + return false; + } + FuSource fus = (FuSource)o; + return + this.isKnown == fus.isKnown && + this.knownSrc == fus.knownSrc; + } + public int hashCode() { + int hash = 0; + if( isKnown == DefReachKnown.KNOWN ) { + hash = 123451; + } + if( knownSrc != null ) { + hash ^= knownSrc.hashCode(); + } + return hash; + } + } + private static MultiViewMapBuilder FuBuilder; + private static BitSet viewFufull; + private static BitSet viewFu0; + private static BitSet viewFu1; + private MultiViewMap Fu; // Fd (field downstream) @@ -74,6 +108,7 @@ public class DefiniteReachState { // call before instantiating this class static public void initBuilders() { + RBuilder = new MultiViewMapBuilder( new Class[] { TempDescriptor.class, @@ -87,16 +122,19 @@ public class DefiniteReachState { viewR01 = RBuilder.addPartialView( 0, 1 ); RBuilder.setCheckTypes( true ); RBuilder.setCheckConsistency( true ); + + + FuBuilder = + new MultiViewMapBuilder( new Class[] { + TempDescriptor.class, + FuSource.class}, + new JoinOpNop() ); + viewFufull = FuBuilder.getFullView(); + viewFu0 = FuBuilder.addPartialView( 0 ); + viewFu1 = FuBuilder.addPartialView( 1 ); + FuBuilder.setCheckTypes( true ); + FuBuilder.setCheckConsistency( true ); - //FuBuilder = - // new MultiViewMapBuilder( new Class[] { - // TempDescriptor.class, - // DefReachFuVal.class}, - // new JoinOpNop() ); - //viewFu0 = FuBuilder.addPartialView( 0 ); - //viewFu1 = FuBuilder.addPartialView( 1 ); - //FuBuilder.setCheckTypes( true ); - //FuBuilder.setCheckConsistency( true ); FdBuilder = new MultiViewMapBuilder( new Class[] { @@ -115,25 +153,52 @@ public class DefiniteReachState { public DefiniteReachState( DefiniteReachState toCopy ) { this.R = toCopy.R.clone( RBuilder ); this.Rs = new HashMap( toCopy.Rs ); + this.Fu = toCopy.Fu.clone( FuBuilder ); this.Fd = toCopy.Fd.clone( FdBuilder ); } public DefiniteReachState() { - R = RBuilder.build(); + R = RBuilder.build(); Rs = new HashMap(); - //Fu = FuBuilder.build(); + Fu = FuBuilder.build(); Fd = FdBuilder.build(); } + public boolean isAlreadyReachable( TempDescriptor a, TempDescriptor b ) { - return !R.get( viewR01, MultiKey.factory( a, b ) ).isEmpty(); + + boolean case1 = !R.get( viewR01, MultiKey.factory( a, b ) ).isEmpty(); + + boolean case3 = false; + if( Rs.get( b ) != null && + Rs.get( b ) == DefReachKnown.KNOWN && + Fu.get( viewFufull, MultiKey.factory( b, new FuSource() ) ).isEmpty() + ) { + boolean allEntriesOk = true; + for( MultiKey fullKeyB : Fu.get( viewFu0, + MultiKey.factory( b ) ).keySet() + ) { + if( !R.get( viewR01, + MultiKey.factory( a, + ((FuSource)fullKeyB.get( 1 )).knownSrc + ) ).isEmpty() + ) { + allEntriesOk = false; + break; + } + } + case3 = allEntriesOk; + } + + return case1 || case3; } + public Set edgesToElidePropagation( TempDescriptor x, TempDescriptor y ) { // return the set of edges that definite reach analysis tells @@ -172,6 +237,7 @@ public class DefiniteReachState { public void methodEntry( Set parameters ) { methodEntryR ( parameters ); methodEntryRs( parameters ); + methodEntryFu( parameters ); methodEntryFd( parameters ); } @@ -179,30 +245,8 @@ public class DefiniteReachState { TempDescriptor y ) { copyR ( x, y ); copyRs( x, y ); + copyFu( x, y ); copyFd( x, y ); - - // Fu' := (Fu - - <*, x>) U - // { | in Fu} U - // { | in Fu} U - // { | > in Fu} - //Fu.remove( viewFu0, MultiKey.factory( x ) ); - //Fu.remove( viewFu1, MultiKey.factory( x ) ); - //for( MultiKey key : Fu.get( viewFu0, MultiKey.factory( y ) ).keySet() ) { - // DefReachFuVal val = (DefReachFuVal) key.get( 1 ); - // Fu.put( MultiKey.factory( x, val ), dummy ); - //} - //for( MultiKey key : Fu.get( viewFu1, MultiKey.factory( y ) ).keySet() ) { - // TempDescriptor v = (TempDescriptor) key.get( 0 ); - // Fu.put( MultiKey.factory( v, DefReachFuVal.factory( x ) ), dummy ); - //} - //for( MultiKey key : - // Fu.get( viewFu1, - // MultiKey.factory( DefReachFuVal.factory( DefReachFuVal.Val.UNKNOWN ) ) - // ).keySet() - // ) { - // TempDescriptor z = (TempDescriptor) key.get( 0 ); - // Fu.put( MultiKey.factory( z, DefReachFuVal.factory( x ) ), dummy ); - //} } public void load( TempDescriptor x, @@ -212,6 +256,7 @@ public class DefiniteReachState { loadR ( x, y, f, edgeKeysForLoad ); loadRs( x, y, f, edgeKeysForLoad ); + loadFu( x, y, f, edgeKeysForLoad ); loadFd( x, y, f, edgeKeysForLoad ); } @@ -223,24 +268,28 @@ public class DefiniteReachState { storeR ( x, f, y, edgeKeysRemoved, edgeKeysAdded ); storeRs( x, f, y, edgeKeysRemoved, edgeKeysAdded ); + storeFu( x, f, y, edgeKeysRemoved, edgeKeysAdded ); storeFd( x, f, y, edgeKeysRemoved, edgeKeysAdded ); } public void newObject( TempDescriptor x ) { newObjectR ( x ); newObjectRs( x ); + newObjectFu( x ); newObjectFd( x ); } public void methodCall( TempDescriptor retVal ) { methodCallR ( retVal ); methodCallRs( retVal ); + methodCallFu( retVal ); methodCallFd( retVal ); } public void merge( DefiniteReachState that ) { mergeR ( that ); mergeRs( that ); + mergeFu( that ); mergeFd( that ); } @@ -395,16 +444,6 @@ public class DefiniteReachState { Rs.put( retVal, DefReachKnown.UNKNOWN ); } - /////////////////////////////////////////////////////////// - // - // This is WRONG - // - // It definitely tests the current R as well as Rs - // - // but also be careful what null means, is it actually - // equivalent to UNKOWN? I'd rather put nothing, meaning - // we have to do an analysis pass over all the incoming edges - // before there is a sensical answer. I think... private void mergeRs( DefiniteReachState that ) { Set allVars = new HashSet(); allVars.addAll( this.Rs.keySet() ); @@ -427,6 +466,119 @@ public class DefiniteReachState { + + public void methodEntryFu( Set parameters ) { + Fu.clear(); + } + + public void copyFu( 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 ); + MultiKey keyYsrc = MultiKey.factory( new FuSource( y ) ); + Map mapY0 = Fu.get( viewFu0, keyY ); + Map mapY1 = Fu.get( viewFu1, keyYsrc ); + + MultiKey keyXsrc = MultiKey.factory( new FuSource( x ) ); + Map mapX1 = Fu.get( viewFu1, keyXsrc ); + + // then remove anything + MultiKey keyX = MultiKey.factory( x ); + Fu.remove( viewFu0, keyX ); + Fu.remove( viewFu1, keyXsrc ); + + // then insert new stuff + for( MultiKey fullKeyY : mapY0.keySet() ) { + MultiKey fullKeyX = MultiKey.factory( x, + fullKeyY.get( 1 ) ); + Fu.put( fullKeyX, MultiViewMap.dummyValue ); + } + for( MultiKey fullKeyY : mapY1.keySet() ) { + MultiKey fullKeyX = MultiKey.factory( fullKeyY.get( 0 ), + new FuSource( x ) ); + Fu.put( fullKeyX, MultiViewMap.dummyValue ); + } + for( MultiKey fullKeyXsrc : mapX1.keySet() ) { + Fu.put( MultiKey.factory( fullKeyXsrc.get( 0 ), + new FuSource() ), + MultiViewMap.dummyValue ); + } + } + + public void loadFu( TempDescriptor x, + TempDescriptor y, + FieldDescriptor f, + Set edgeKeysForLoad ) { + + // first get all info for update + MultiKey keyXsrc = MultiKey.factory( new FuSource( x ) ); + Map mapX1 = Fu.get( viewFu1, keyXsrc ); + + MultiKey keyX = MultiKey.factory( x ); + // then remove anything + Fu.remove( viewFu0, keyX ); + Fu.remove( viewFu1, keyXsrc ); + + // then insert new stuff + for( MultiKey fullKeyXsrc : mapX1.keySet() ) { + Fu.put( MultiKey.factory( fullKeyXsrc.get( 0 ), + new FuSource() ), + MultiViewMap.dummyValue ); + } + } + + public void storeFu( TempDescriptor x, + FieldDescriptor f, + TempDescriptor y, + Set edgeKeysRemoved, + Set edgeKeysAdded ) { + + Fu.put( MultiKey.factory( y, new FuSource( x ) ), + MultiViewMap.dummyValue ); + } + + public void newObjectFu( TempDescriptor x ) { + MultiKey keyXsrc = MultiKey.factory( new FuSource( x ) ); + Map mapX1 = Fu.get( viewFu1, keyXsrc ); + + MultiKey keyX = MultiKey.factory( x ); + Fu.remove( viewFu0, keyX ); + Fu.remove( viewFu1, keyXsrc ); + + for( MultiKey fullKeyXsrc : mapX1.keySet() ) { + Fu.put( MultiKey.factory( fullKeyXsrc.get( 0 ), + new FuSource() ), + MultiViewMap.dummyValue ); + } + } + + public void methodCallFu( TempDescriptor retVal ) { + MultiKey keyRetValsrc = MultiKey.factory( new FuSource( retVal ) ); + Map mapRetVal1 = Fu.get( viewFu1, keyRetValsrc ); + + MultiKey keyRetVal = MultiKey.factory( retVal ); + Fu.remove( viewFu0, keyRetVal ); + Fu.remove( viewFu1, keyRetValsrc ); + + for( MultiKey fullKeyRetValsrc : mapRetVal1.keySet() ) { + Fu.put( MultiKey.factory( fullKeyRetValsrc.get( 0 ), + new FuSource() ), + MultiViewMap.dummyValue ); + } + } + + public void mergeFu( DefiniteReachState that ) { + this.Fu.merge( that.Fu ); + } + + + + + + public void methodEntryFd( Set parameters ) { Fd.clear(); } diff --git a/Robust/src/Tests/disjoint/definite3/makefile b/Robust/src/Tests/disjoint/definite3/makefile new file mode 100644 index 00000000..462f41d4 --- /dev/null +++ b/Robust/src/Tests/disjoint/definite3/makefile @@ -0,0 +1,25 @@ +PROGRAM=Test + +SOURCE_FILES=test.java + +BUILDSCRIPT=../../../buildscript + +DISJOINT= -disjoint -disjoint-k 1 -enable-assertions -do-definite-reach-analysis + +BSFLAGS= -justanalyze -mainclass $(PROGRAM) -heapsize-mb 1024 -noloop -joptimize -debug #-flatirusermethods + + +all: + $(BUILDSCRIPT) -thread $(BSFLAGS) $(DISJOINT) -o $(PROGRAM)s -builddir sing $(SOURCE_FILES) + +clean: + rm -f $(PROGRAM)s.bin + rm -fr sing + rm -f *~ + rm -f *.dot + rm -f *.png + rm -f *.txt + rm -f aliases.txt + rm -f mlpReport*txt + rm -f results*txt + rm -f coreprof.dat diff --git a/Robust/src/Tests/disjoint/definite3/test.java b/Robust/src/Tests/disjoint/definite3/test.java new file mode 100644 index 00000000..e332422a --- /dev/null +++ b/Robust/src/Tests/disjoint/definite3/test.java @@ -0,0 +1,56 @@ +public class Foo { + public Foo f; + public Foo g; +} + +public class Test { + + + + static public void main( String args[] ) { + + Foo a = getFlagged(); + Foo b = getUnflagged(); + a.f = b; + + // a is flagged and b is reachable from + // at most one object from that site + gendefreach z0; + genreach z0; + + Foo c = new Foo(); + a.g = c; + + Foo t = getFlagged(); + t = getFlagged(); + + Foo u = getUnflagged(); + u = getUnflagged(); + + // a is flagged and b is reachable from + // at most one object from that site, even + // though a and b are summarized now. a + // has a reference to a new object c + gendefreach z1; + genreach z1; + + c.f = b; + + // if we had definite reachability analysis + // we would realize b is already reachable + // from a + gendefreach z3; + genreach z3; + + System.out.println( " "+a+b+c ); + } + + static public Foo getFlagged() { + return disjoint jupiter new Foo(); + } + + static public Foo getUnflagged() { + return new Foo(); + } + +} -- 2.34.1