From 1fffd91e99db27f5353bb6da0ccf27995fd36fdc Mon Sep 17 00:00:00 2001 From: jjenista Date: Thu, 10 Nov 2011 18:59:04 +0000 Subject: [PATCH] working on the second case where definite reach can improve results --- .../Analysis/Disjoint/DefiniteReachState.java | 264 +++++++++++++----- Robust/src/Tests/disjoint/definite2/makefile | 25 ++ Robust/src/Tests/disjoint/definite2/test.java | 58 ++++ 3 files changed, 282 insertions(+), 65 deletions(-) create mode 100644 Robust/src/Tests/disjoint/definite2/makefile create mode 100644 Robust/src/Tests/disjoint/definite2/test.java diff --git a/Robust/src/Analysis/Disjoint/DefiniteReachState.java b/Robust/src/Analysis/Disjoint/DefiniteReachState.java index d9b0af12..72238d9b 100644 --- a/Robust/src/Analysis/Disjoint/DefiniteReachState.java +++ b/Robust/src/Analysis/Disjoint/DefiniteReachState.java @@ -29,14 +29,14 @@ public class DefiniteReachState { // // Tracks whether the analysis must know the definite reachability // information of a given variable. - //private enum DefReachKnown { - // UNKNOWN, - // KNOWN, - //} - //private Map Rs; + private enum DefReachKnown { + UNKNOWN, + KNOWN, + } + private Map Rs; - // Fu (upstream) + // Fu (field upstream) // // Maps a variable that points to object o0 to the // set of variables that point to objects o1...oN @@ -47,7 +47,15 @@ public class DefiniteReachState { //private MultiViewMap Fu; - // Fd (downstream) + // Fd (field downstream) + // + // Entries mean x.f points directly at what + // y points at. + private static MultiViewMapBuilder FdBuilder; + private static BitSet viewFd0; + private static BitSet viewFd2; + private MultiViewMap Fd; + @@ -77,20 +85,33 @@ public class DefiniteReachState { //viewFu1 = FuBuilder.addPartialView( 1 ); //FuBuilder.setCheckTypes( true ); //FuBuilder.setCheckConsistency( true ); + + FdBuilder = + new MultiViewMapBuilder( new Class[] { + TempDescriptor.class, + FieldDescriptor.class, + TempDescriptor.class}, + new JoinOpNop() ); + viewFd0 = FdBuilder.addPartialView( 0 ); + viewFd2 = FdBuilder.addPartialView( 2 ); + FdBuilder.setCheckTypes( true ); + FdBuilder.setCheckConsistency( true ); } public DefiniteReachState( DefiniteReachState toCopy ) { - this.R = toCopy.R.clone( RBuilder ); + this.R = toCopy.R.clone( RBuilder ); + this.Rs = new HashMap( toCopy.Rs ); + this.Fd = toCopy.Fd.clone( FdBuilder ); } public DefiniteReachState() { R = RBuilder.build(); - //Rs = new HashMap(); - + Rs = new HashMap(); //Fu = FuBuilder.build(); + Fd = FdBuilder.build(); } @@ -104,24 +125,16 @@ public class DefiniteReachState { public void methodEntry( Set parameters ) { - methodEntryR( parameters ); - - //Rs.clear(); - //for( TempDescriptor p : parameters ) { - // Rs.put( p, DefReachKnown.UNKNOWN ); - //} - // - //Fu = FuBuilder.build(); + methodEntryR ( parameters ); + methodEntryRs( parameters ); + methodEntryFd( parameters ); } public void copy( TempDescriptor x, TempDescriptor y ) { - copyR( x, y ); - - // Rs' := (Rs - ) U { | in Rs} - //DefReachKnown valRs = Rs.get( y ); - //assert( valRs != null ); - //Rs.put( x, valRs ); + copyR ( x, y ); + copyRs( x, y ); + copyFd( x, y ); // Fu' := (Fu - - <*, x>) U // { | in Fu} U @@ -152,9 +165,9 @@ public class DefiniteReachState { FieldDescriptor f, Set edgeKeysForLoad ) { - loadR( x, y, f, edgeKeysForLoad ); - // Rs' := (Rs - ) U {} - //Rs.put( x, DefReachKnown.UNKNOWN ); + loadR ( x, y, f, edgeKeysForLoad ); + loadRs( x, y, f, edgeKeysForLoad ); + loadFd( x, y, f, edgeKeysForLoad ); } public void store( TempDescriptor x, @@ -163,30 +176,27 @@ public class DefiniteReachState { Set edgeKeysRemoved, Set edgeKeysAdded ) { - storeR( x, f, y, edgeKeysRemoved, edgeKeysAdded ); - // Rs' := Rs + storeR ( x, f, y, edgeKeysRemoved, edgeKeysAdded ); + storeRs( x, f, y, edgeKeysRemoved, edgeKeysAdded ); + storeFd( x, f, y, edgeKeysRemoved, edgeKeysAdded ); } public void newObject( TempDescriptor x ) { - newObjectR( x ); - - // Rs' := (Rs - ) U {} - //Rs.put( x, DefReachKnown.KNOWN ); - + newObjectR ( x ); + newObjectRs( x ); + newObjectFd( x ); } public void methodCall( TempDescriptor retVal ) { - methodCallR( retVal ); - - // Rs' := (Rs - ) U {} - //Rs.put( x, DefReachKnown.UNKNOWN ); + methodCallR ( retVal ); + methodCallRs( retVal ); + methodCallFd( retVal ); } public void merge( DefiniteReachState that ) { - mergeR( that ); - - // Rs' := iff in all incoming edges, otherwie - //mergeRs( that ); + mergeR ( that ); + mergeRs( that ); + mergeFd( that ); } @@ -293,10 +303,6 @@ public class DefiniteReachState { for( MultiKey key : this.R.get().keySet() ) { if( that.R.get( viewRfull, key ).isEmpty() ) { this.R.remove( viewRfull, key ); - } else { - // if the key is in this and that, we should join the - // values using the R.joinOp which is currently has no - // public interface } } } @@ -304,6 +310,46 @@ public class DefiniteReachState { + + + + + public void methodEntryRs( Set parameters ) { + Rs.clear(); + for( TempDescriptor p : parameters ) { + Rs.put( p, DefReachKnown.UNKNOWN ); + } + } + + public void copyRs( TempDescriptor x, + TempDescriptor y ) { + DefReachKnown valRs = Rs.get( y ); + assert( valRs != null ); + Rs.put( x, valRs ); + } + + public void loadRs( TempDescriptor x, + TempDescriptor y, + FieldDescriptor f, + Set edgeKeysForLoad ) { + Rs.put( x, DefReachKnown.UNKNOWN ); + } + + public void storeRs( TempDescriptor x, + FieldDescriptor f, + TempDescriptor y, + Set edgeKeysRemoved, + Set edgeKeysAdded ) { + } + + public void newObjectRs( TempDescriptor x ) { + Rs.put( x, DefReachKnown.KNOWN ); + } + + public void methodCallRs( TempDescriptor retVal ) { + Rs.put( retVal, DefReachKnown.UNKNOWN ); + } + /////////////////////////////////////////////////////////// // // This is WRONG @@ -315,21 +361,104 @@ public class DefiniteReachState { // 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 ) { - // merge "that" into "this" and leave "that" unchanged - //Set allVars = new HashSet(); - //allVars.addAll( this.Rs.keySet() ); - //allVars.addAll( that.Rs.keySet() ); - //for( TempDescriptor x : allVars ) { - // DefReachKnown vThis = this.Rs.get( x ); - // DefReachKnown vThat = that.Rs.get( x ); - // if( vThis != null && vThis.equals( DefReachKnown.KNOWN ) && - // vThat != null && vThat.equals( DefReachKnown.KNOWN ) ) { - // this.Rs.put( x, DefReachKnown.KNOWN ); - // } else { - // this.Rs.put( x, DefReachKnown.UNKNOWN ); - // } - //} + Set allVars = new HashSet(); + allVars.addAll( this.Rs.keySet() ); + allVars.addAll( that.Rs.keySet() ); + for( TempDescriptor x : allVars ) { + DefReachKnown vThis = this.Rs.get( x ); + DefReachKnown vThat = that.Rs.get( x ); + if( vThis != null && vThis.equals( DefReachKnown.KNOWN ) && + vThat != null && vThat.equals( DefReachKnown.KNOWN ) ) { + this.Rs.put( x, DefReachKnown.KNOWN ); + } else { + this.Rs.put( x, DefReachKnown.UNKNOWN ); + } + } + } + + + + + + + + public void methodEntryFd( Set parameters ) { + Fd.clear(); + } + + public void copyFd( 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 = Fd.get( viewFd0, keyY ); + Map mapY2 = Fd.get( viewFd2, keyY ); + + // then remove anything + MultiKey keyX = MultiKey.factory( x ); + Fd.remove( viewFd0, keyX ); + Fd.remove( viewFd2, keyX ); + + // then insert new stuff + for( MultiKey fullKeyY : mapY0.keySet() ) { + MultiKey fullKeyX = MultiKey.factory( x, + fullKeyY.get( 1 ), + fullKeyY.get( 2 ) ); + Fd.put( fullKeyX, MultiViewMap.dummyValue ); + } + for( MultiKey fullKeyY : mapY2.keySet() ) { + MultiKey fullKeyX = MultiKey.factory( fullKeyY.get( 0 ), + fullKeyY.get( 1 ), + x ); + Fd.put( fullKeyX, MultiViewMap.dummyValue ); + } } + + public void loadFd( TempDescriptor x, + TempDescriptor y, + FieldDescriptor f, + Set edgeKeysForLoad ) { + + MultiKey keyX = MultiKey.factory( x ); + Fd.remove( viewFd0, keyX ); + Fd.remove( viewFd2, keyX ); + } + + public void storeFd( TempDescriptor x, + FieldDescriptor f, + TempDescriptor y, + Set edgeKeysFdemoved, + Set edgeKeysAdded ) { + Fd.put( MultiKey.factory( x, f, y ), + MultiViewMap.dummyValue ); + } + + public void newObjectFd( TempDescriptor x ) { + MultiKey keyX = MultiKey.factory( x ); + Fd.remove( viewFd0, keyX ); + Fd.remove( viewFd2, keyX ); + } + + public void methodCallFd( TempDescriptor retVal ) { + MultiKey keyRetVal = MultiKey.factory( retVal ); + Fd.remove( viewFd0, keyRetVal ); + Fd.remove( viewFd2, keyRetVal ); + } + + public void mergeFd( DefiniteReachState that ) { + this.Fd.merge( that.Fd ); + } + + + + + + + + + @@ -374,11 +503,16 @@ public class DefiniteReachState { s.append( R.toString( 2 ) ); s.append( "}\n" ); - //s.append( "R_s = {" ); - //for( TempDescriptor x : Rs.keySet() ) { - // s.append( " "+x+"->"+Rs.get( x ) ); - //} - //s.append( "}" ); + s.append( "Rs = {\n" ); + for( TempDescriptor x : Rs.keySet() ) { + s.append( " "+x+"->"+Rs.get( x )+"\n" ); + } + s.append( "}\n" ); + + s.append( "Fd = {\n" ); + s.append( Fd.toString( 2 ) ); + s.append( "}\n" ); + return s.toString(); } } diff --git a/Robust/src/Tests/disjoint/definite2/makefile b/Robust/src/Tests/disjoint/definite2/makefile new file mode 100644 index 00000000..462f41d4 --- /dev/null +++ b/Robust/src/Tests/disjoint/definite2/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/definite2/test.java b/Robust/src/Tests/disjoint/definite2/test.java new file mode 100644 index 00000000..936dffd0 --- /dev/null +++ b/Robust/src/Tests/disjoint/definite2/test.java @@ -0,0 +1,58 @@ +public class Foo { + public Foo f; + public Foo g; +} + +public class Test { + + + + static public void main( String args[] ) { + + Foo x = getFlagged(); + Foo z = getUnflagged(); + x.f = z; + + // x is flagged and z is reachable from + // at most one object from that site + gendefreach z0; + genreach z0; + + Foo t = getFlagged(); + t = getFlagged(); + + Foo y = new Foo(); + + // x is flagged and z is reachable from + // at most one object from that site, even + // though x is summarized now + gendefreach z1; + genreach z1; + + y.f = z; + + gendefreach z2; + genreach z2; + + x.f = y; + + // if we had definite reachability analysis + // we would realize z is already reachable + // from x, but we don't and x is summarized + // so we conservatively increase the arity + // of objects by PROPAGATING through y. + gendefreach z3; + genreach z3; + + System.out.println( " "+x+y ); + } + + static public Foo getFlagged() { + return disjoint jupiter new Foo(); + } + + static public Foo getUnflagged() { + return new Foo(); + } + +} -- 2.34.1