From 9dd253fb3f37647f295d83bbaad2fbd92a15a216 Mon Sep 17 00:00:00 2001 From: jjenista Date: Wed, 1 Oct 2008 21:51:48 +0000 Subject: [PATCH] Tighten up use of canonical objects and halt system if a canonical object's hashcode changes. --- .../OwnershipAnalysis/ChangeTuple.java | 19 ++++- .../OwnershipAnalysis/ChangeTupleSet.java | 19 ++++- .../OwnershipAnalysis/HeapRegionNode.java | 5 +- .../OwnershipAnalysis/OwnershipAnalysis.java | 11 ++- .../OwnershipAnalysis/OwnershipGraph.java | 44 ++++++---- .../OwnershipAnalysis/ReachabilitySet.java | 24 +++++- .../OwnershipAnalysis/TokenTuple.java | 17 +++- .../OwnershipAnalysis/TokenTupleSet.java | 39 +++++++-- .../OwnershipAnalysisTest/test01/test01.java | 85 +++++++++++++------ 9 files changed, 197 insertions(+), 66 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/ChangeTuple.java b/Robust/src/Analysis/OwnershipAnalysis/ChangeTuple.java index 116db256..c94a0cc9 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ChangeTuple.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ChangeTuple.java @@ -34,6 +34,7 @@ public class ChangeTuple extends Canonical return toAdd; } + public boolean equals(Object o) { if( o == null ) { return false; @@ -49,10 +50,26 @@ public class ChangeTuple extends Canonical toAdd.equals(ct.getSetToAdd() ); } + private boolean oldHashSet = false; + private int oldHash = 0; public int hashCode() { - return toMatch.hashCode() + toAdd.hashCode()*3; + int currentHash = toMatch.hashCode() + toAdd.hashCode()*3; + + if( oldHashSet == false ) { + oldHash = currentHash; + oldHashSet = true; + } else { + if( oldHash != currentHash ) { + System.out.println( "IF YOU SEE THIS A CANONICAL ChangeTuple CHANGED" ); + Integer x = null; + x.toString(); + } + } + + return currentHash; } + public String toString() { return new String("("+toMatch+" -> "+toAdd+")"); } diff --git a/Robust/src/Analysis/OwnershipAnalysis/ChangeTupleSet.java b/Robust/src/Analysis/OwnershipAnalysis/ChangeTupleSet.java index 32a50de1..4f2fe4a8 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ChangeTupleSet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ChangeTupleSet.java @@ -60,6 +60,7 @@ public class ChangeTupleSet extends Canonical { return ctsIn.changeTuples.containsAll(this.changeTuples); } + public boolean equals(Object o) { if( o == null ) { return false; @@ -73,10 +74,26 @@ public class ChangeTupleSet extends Canonical { return changeTuples.equals(cts.changeTuples); } + private boolean oldHashSet = false; + private int oldHash = 0; public int hashCode() { - return changeTuples.hashCode(); + int currentHash = changeTuples.hashCode(); + + if( oldHashSet == false ) { + oldHash = currentHash; + oldHashSet = true; + } else { + if( oldHash != currentHash ) { + System.out.println( "IF YOU SEE THIS A CANONICAL ChangeTupleSet CHANGED" ); + Integer x = null; + x.toString(); + } + } + + return currentHash; } + public String toString() { String s = "["; diff --git a/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java b/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java index f5009b22..e474ad63 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java +++ b/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java @@ -172,11 +172,8 @@ public class HeapRegionNode extends OwnershipNode { public void applyAlphaNew() { assert alphaNew != null; - alpha = alphaNew; - - alphaNew = new ReachabilitySet(); - alphaNew = alphaNew.makeCanonical(); + alphaNew = new ReachabilitySet().makeCanonical(); } diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index f28ce127..5972b801 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -421,7 +421,6 @@ public class OwnershipAnalysis { og); - //debugSnapshot(og,fn); @@ -613,10 +612,10 @@ public class OwnershipAnalysis { // insert a call to debugSnapshot() somewhere in the analysis to get // successive captures of the analysis state int debugCounter = 0; - int numStartCountReport = 10000; - int freqCountReport = 10; - int iterStartCapture = 50; - int numIterToCapture = 16; + int numStartCountReport = 0; + int freqCountReport = 1000; + int iterStartCapture = 20000; + int numIterToCapture = 400; void debugSnapshot( OwnershipGraph og, FlatNode fn ) { ++debugCounter; if( debugCounter > numStartCountReport && @@ -630,7 +629,7 @@ public class OwnershipAnalysis { graphName = graphName+fn; } try { - og.writeGraph( graphName, true, true, true, false, false ); + og.writeGraph( graphName, true, true, false, false, false ); } catch( Exception e ) { System.out.println( "Error writing debug capture." ); System.exit( 0 ); diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 7e3f6af3..10376cfb 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -84,12 +84,15 @@ public class OwnershipGraph { if( alpha == null ) { if( isFlagged || isParameter ) { - alpha = new ReachabilitySet(new TokenTuple(id, + alpha = new ReachabilitySet( + new TokenTuple(id, !isSingleObject, - TokenTuple.ARITY_ONE) + TokenTuple.ARITY_ONE + ).makeCanonical() ).makeCanonical(); } else { - alpha = new ReachabilitySet(new TokenTupleSet() + alpha = new ReachabilitySet( + new TokenTupleSet().makeCanonical() ).makeCanonical(); } } @@ -451,9 +454,13 @@ public class OwnershipGraph { edgesWithNewBeta); - if( edgeY.getBetaNew().equals( new ReachabilitySet() ) ) { + // THIS IS A HACK--NEED TO CHANGE GENERATATION OF BETA-NEW SO THIS DOESN'T + // HAPPEN OTHERWISE PROPAGATION FAILS + if( edgeY.getBetaNew().equals( new ReachabilitySet().makeCanonical() ) ) { edgeY.setBetaNew( new ReachabilitySet( new TokenTupleSet().makeCanonical() ).makeCanonical() ); } + + /* System.out.println( "---------------------------\n" + @@ -553,7 +560,8 @@ public class OwnershipGraph { ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID, true, - TokenTuple.ARITY_ONE) ); + TokenTuple.ARITY_ONE).makeCanonical() + ).makeCanonical(); // heap regions for parameters are always multiple object (see above) // and have a reference to themselves, because we can't know the @@ -707,13 +715,15 @@ public class OwnershipGraph { // after tokens have been aged, reset newest node's reachability if( hrn0.isFlagged() ) { - hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet( - new TokenTuple(hrn0) - ) + hrn0.setAlpha(new ReachabilitySet( + new TokenTupleSet( + new TokenTuple(hrn0).makeCanonical() + ).makeCanonical() ).makeCanonical() ); } else { - hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet() + hrn0.setAlpha(new ReachabilitySet( + new TokenTupleSet().makeCanonical() ).makeCanonical() ); } @@ -942,10 +952,12 @@ public class OwnershipGraph { // of new callee nodes and edges, doesn't belong to any parameter Integer bogusID = new Integer(-1); Integer bogusIndex = new Integer(-1); - TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE); - TokenTuple bogusTokenPlus = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONEORMORE); + TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE).makeCanonical(); + TokenTuple bogusTokenPlus = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONEORMORE).makeCanonical(); ReachabilitySet rsIdentity = - new ReachabilitySet(new TokenTupleSet(bogusToken).makeCanonical() ).makeCanonical(); + new ReachabilitySet( + new TokenTupleSet(bogusToken).makeCanonical() + ).makeCanonical(); paramIndex2rewriteH.put(bogusIndex, rsIdentity); paramIndex2rewriteJ.put(bogusIndex, rsIdentity); @@ -1296,7 +1308,8 @@ public class OwnershipGraph { null, edgeCallee.getFieldDesc(), false, - toShadowTokens(ogCallee, edgeCallee.getBeta() ) + toShadowTokens(ogCallee, + edgeCallee.getBeta() ) ); rewriteCallerReachability(bogusIndex, null, @@ -1382,7 +1395,8 @@ public class OwnershipGraph { null, edgeCallee.getFieldDesc(), false, - toShadowTokens(ogCallee, edgeCallee.getBeta() ) + toShadowTokens(ogCallee, + edgeCallee.getBeta() ) ); rewriteCallerReachability(bogusIndex, null, @@ -1574,7 +1588,7 @@ public class OwnershipGraph { private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee, ReachabilitySet rsIn) { - ReachabilitySet rsOut = new ReachabilitySet(rsIn); + ReachabilitySet rsOut = new ReachabilitySet(rsIn).makeCanonical(); Iterator allocItr = ogCallee.allocationSites.iterator(); while( allocItr.hasNext() ) { diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java index caedeade..143db1a8 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java @@ -135,7 +135,7 @@ public class ReachabilitySet extends Canonical { while( itrR.hasNext() ) { TokenTupleSet r = (TokenTupleSet) itrR.next(); - TokenTupleSet theUnion = new TokenTupleSet(); + TokenTupleSet theUnion = new TokenTupleSet().makeCanonical(); Iterator itrRelement = r.iterator(); while( itrRelement.hasNext() ) { @@ -248,7 +248,7 @@ public class ReachabilitySet extends Canonical { int numDimensions = this.possibleReachabilities.size(); - if( numDimensions > 6 ) { + if( numDimensions > 1 ) { // for problems that are too big, punt and use less // precise arity for reachability information TokenTupleSet ttsImprecise = new TokenTupleSet().makeCanonical(); @@ -259,11 +259,11 @@ public class ReachabilitySet extends Canonical { ttsImprecise = ttsImprecise.unionUpArity( ttsUnit.makeArityZeroOrMore() ); } + //rsOut = this.union( ttsImprecise ); rsOut = rsOut.union( ttsImprecise ); return rsOut; } - // add an extra digit to detect termination int[] digits = new int[numDimensions+1]; @@ -322,8 +322,24 @@ public class ReachabilitySet extends Canonical { return possibleReachabilities.equals(rs.possibleReachabilities); } + + private boolean oldHashSet = false; + private int oldHash = 0; public int hashCode() { - return possibleReachabilities.hashCode(); + int currentHash = possibleReachabilities.hashCode(); + + if( oldHashSet == false ) { + oldHash = currentHash; + oldHashSet = true; + } else { + if( oldHash != currentHash ) { + System.out.println( "IF YOU SEE THIS A CANONICAL ReachabilitySet CHANGED" ); + Integer x = null; + x.toString(); + } + } + + return currentHash; } diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java index 30c07379..83226ad5 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java +++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java @@ -109,8 +109,23 @@ public class TokenTuple extends Canonical { arity == tt.getArity(); } + private boolean oldHashSet = false; + private int oldHash = 0; public int hashCode() { - return token.intValue()*31 + arity; + int currentHash = token.intValue()*31 + arity; + + if( oldHashSet == false ) { + oldHash = currentHash; + oldHashSet = true; + } else { + if( oldHash != currentHash ) { + System.out.println( "IF YOU SEE THIS A CANONICAL TokenTuple CHANGED" ); + Integer x = null; + x.toString(); + } + } + + return currentHash; } diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java index af72503a..30f135b3 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java @@ -51,6 +51,13 @@ public class TokenTupleSet extends Canonical { } + public TokenTupleSet union(TokenTuple ttIn) { + assert ttIn != null; + TokenTupleSet ttsOut = new TokenTupleSet(this); + ttsOut.tokenTuples.add(ttIn); + return ttsOut.makeCanonical(); + } + public TokenTupleSet union(TokenTupleSet ttsIn) { assert ttsIn != null; TokenTupleSet ttsOut = new TokenTupleSet(this); @@ -109,8 +116,25 @@ public class TokenTupleSet extends Canonical { return tokenTuples.equals(tts.tokenTuples); } + + + private boolean oldHashSet = false; + private int oldHash = 0; public int hashCode() { - return tokenTuples.hashCode(); + int currentHash = tokenTuples.hashCode(); + + if( oldHashSet == false ) { + oldHash = currentHash; + oldHashSet = true; + } else { + if( oldHash != currentHash ) { + System.out.println( "IF YOU SEE THIS A CANONICAL TokenTupleSet CHANGED" ); + Integer x = null; + x.toString(); + } + } + + return currentHash; } @@ -287,13 +311,13 @@ public class TokenTupleSet extends Canonical { // summary tokens and tokens not associated with // the site should be left alone if( age == AllocationSite.AGE_notInThisSite ) { - ttsOut.tokenTuples.add(tt); + ttsOut = ttsOut.union(tt); } else if( age == AllocationSite.AGE_summary ) { - ttsOut.tokenTuples.add(tt.changeTokenTo(as.getSummaryShadow() )); + ttsOut = ttsOut.union(tt.changeTokenTo(as.getSummaryShadow() )); } else if( age == AllocationSite.AGE_oldest ) { - ttsOut.tokenTuples.add(tt.changeTokenTo(as.getOldestShadow() )); + ttsOut = ttsOut.union(tt.changeTokenTo(as.getOldestShadow() )); } else { assert age == AllocationSite.AGE_in_I; @@ -301,7 +325,7 @@ public class TokenTupleSet extends Canonical { Integer I = as.getAge(token); assert I != null; - ttsOut.tokenTuples.add(tt.changeTokenTo(as.getIthOldestShadow(I) )); + ttsOut = ttsOut.union(tt.changeTokenTo(as.getIthOldestShadow(I) )); } } @@ -326,7 +350,7 @@ public class TokenTupleSet extends Canonical { Iterator replaceItr = replacements.iterator(); while( replaceItr.hasNext() ) { TokenTupleSet replacement = replaceItr.next(); - TokenTupleSet replaced = new TokenTupleSet(ttsMinusToken); + TokenTupleSet replaced = new TokenTupleSet(ttsMinusToken).makeCanonical(); replaced = replaced.unionUpArity(replacement); rsOut = rsOut.add(replaced); @@ -362,8 +386,7 @@ public class TokenTupleSet extends Canonical { return ttsOut.makeCanonical(); } - - + public String toString() { return tokenTuples.toString(); } diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java index 77510319..e4c750ab 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java @@ -3,15 +3,15 @@ public class Parameter { flag w; int a; int b; - //Parameter f; - //Parameter g; - //Penguin p; - //Foo h; + Parameter f; + Parameter g; + Penguin p; + Foo h; - public Parameter() {} // a = 0; b = 0; f = null; g = null; } + public Parameter() {} - //public void bar() { foo(); } - //public void foo() { bar(); } + public void bar() { foo(); } + public void foo() { bar(); } static public void proof( Fooz p0, Fooz p1 ) { Fooz c = new Fooz(); @@ -28,7 +28,6 @@ public class Fooz { public Fooz x; } -/* public class Penguin { int x; int y; @@ -180,8 +179,15 @@ public class Foo { p0.y = p1; p1.y = p0; } + + static public void m9_( Foo p0, Foo p1 ) { + Foo g0 = new Foo(); + + p1.x = p1.y; + p1.y = g0; + } } -*/ + // this empty task should still create a non-empty @@ -196,20 +202,11 @@ task Startup( StartupObject s{ initialstate } ) { Parameter.proof( null, null ); - /* - int a = 1; - int b = 2; - int c = 3; - - b = c; - a = b; - */ - taskexit( s{ !initialstate } ); } - /* + task NewObjectA( Foo a{ f }, Foo b{ f } ) { Foo c = new Foo(); @@ -471,9 +468,8 @@ task getNewFromMethod( Foo p0{ f } ) { taskexit( p0{ !f } ); } -*/ -/* + task methodTest01_( Foo p0{ f }, Foo p1{ f } ) { Foo a0before = new Foo(); @@ -495,9 +491,8 @@ task methodTest01_( Foo p0{ f }, Foo p1{ f } ) { taskexit( p0{ !f }, p1{ !f } ); } -*/ -/* + task methodTest02_( Foo p0{ f }, Foo p1{ f } ) { Foo a0before = new Foo(); @@ -620,7 +615,7 @@ task methodTest06_( Foo p0{ f }, Foo p1{ f } ) { a1after.x = new Foo(); } - Foo.m6_( a0after, a1after ); + //Foo.m6_( a0after, a1after ); taskexit( p0{ !f }, p1{ !f } ); @@ -657,7 +652,7 @@ task methodTest07_( Foo p0{ f }, Foo p1{ f } ) { a1after.x = new Foo(); } - Foo.m7_( a0after, a1after ); + //Foo.m7_( a0after, a1after ); taskexit( p0{ !f }, p1{ !f } ); @@ -694,9 +689,47 @@ task methodTest08_( Foo p0{ f }, Foo p1{ f } ) { a1after.x = new Foo(); } - Foo.m8_( a0after, a1after ); + //Foo.m8_( a0after, a1after ); taskexit( p0{ !f }, p1{ !f } ); } */ + + +task methodTest09_( Foo p0{ f }, Foo p1{ f } ) { + + Foo a0before = new Foo(); + if( false ) { + a0before.x = new Foo(); + } else { + a0before.x = new Foo(); + } + + Foo a0after = new Foo(); + if( false ) { + a0after.x = new Foo(); + } else { + a0after.x = new Foo(); + } + + Foo a1before = new Foo(); + if( false ) { + a1before.x = new Foo(); + } else { + a1before.x = new Foo(); + } + + Foo a1after = new Foo(); + if( false ) { + a1after.x = new Foo(); + } else { + a1after.x = new Foo(); + } + + Foo.m9_( a0after, a1after ); + + + taskexit( p0{ !f }, p1{ !f } ); +} + -- 2.34.1