From 3018771c3bcdbccf4c9732666f2fd04ec7db3e63 Mon Sep 17 00:00:00 2001 From: jjenista Date: Tue, 3 Mar 2009 21:52:38 +0000 Subject: [PATCH] Bug fix: report aliases between allocated objects in presence of shared references --- .../OwnershipAnalysis/AllocationSite.java | 10 +- .../OwnershipAnalysis/OwnershipAnalysis.java | 82 ++++++-- .../OwnershipAnalysis/OwnershipGraph.java | 183 +++++++++++++++++- .../OwnershipAnalysisTest/test05/makefile | 27 +++ .../OwnershipAnalysisTest/test05/test.java | 37 ++++ .../OwnershipAnalysisTest/testArrays/makefile | 2 +- 6 files changed, 313 insertions(+), 28 deletions(-) create mode 100644 Robust/src/Tests/OwnershipAnalysisTest/test05/makefile create mode 100644 Robust/src/Tests/OwnershipAnalysisTest/test05/test.java diff --git a/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java b/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java index c53c7285..5867a992 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java +++ b/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java @@ -176,11 +176,17 @@ public class AllocationSite { } public String toString() { - return "allocSite" + id; + if( disjointId == null ) { + return "allocSite" + id; + } + return "allocSite "+disjointId+" ("+id+")"; } public String toStringVerbose() { - return "allocSite" + id + " "+flatNew.getType().toPrettyString(); + if( disjointId == null ) { + return "allocSite" + id + " "+flatNew.getType().toPrettyString(); + } + return "allocSite "+disjointId+" ("+id+") "+flatNew.getType().toPrettyString(); } public String toStringForDOT() { diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index 551399e3..7e7817ac 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -164,6 +164,47 @@ public class OwnershipAnalysis { bw.close(); } + + // this version of writeAllAliases is for Java programs that have no tasks + public void writeAllAliasesJava(String outputFile) throws java.io.IOException { + assert !state.TASK; + + BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) ); + + bw.write("Conducting ownership analysis with allocation depth = "+allocationDepth+"\n"); + boolean foundSomeAlias = false; + + Descriptor d = typeUtil.getMain(); + HashSet allocSites = getFlaggedAllocationSites(d); + + // for each allocation site check for aliases with + // other allocation sites in the context of execution + // of this task + HashSet outerChecked = new HashSet(); + Iterator allocItr1 = allocSites.iterator(); + while( allocItr1.hasNext() ) { + AllocationSite as1 = (AllocationSite) allocItr1.next(); + + Iterator allocItr2 = allocSites.iterator(); + while( allocItr2.hasNext() ) { + AllocationSite as2 = (AllocationSite) allocItr2.next(); + + if( !outerChecked.contains(as2) && + createsPotentialAliases(d, as1, as2) ) { + foundSomeAlias = true; + bw.write("Potential alias between "+as1.getDisjointId()+" and "+as2.getDisjointId()+".\n"); + } + } + + outerChecked.add(as1); + } + + if( !foundSomeAlias ) { + bw.write("No aliases between flagged objects found.\n"); + } + + bw.close(); + } /////////////////////////////////////////// // // end public interface @@ -294,24 +335,8 @@ public class OwnershipAnalysis { } else { // we are not in task mode, just normal Java, so start with // the main method - Descriptor d = tu.getMain(); + Descriptor d = typeUtil.getMain(); scheduleAllCallees(d); - - /* - Iterator classItr = state.getClassSymbolTable().getDescriptorsIterator(); - while( classItr.hasNext() ) { - ClassDescriptor cd = (ClassDescriptor) classItr.next(); - - Iterator methItr = cd.getMethods(); - while( methItr.hasNext() ) { - Descriptor d = (Descriptor) methItr.next(); - - if( d.getSymbol().equals( "main" ) ) { - scheduleAllCallees(d); - } - } - } - */ } @@ -357,7 +382,11 @@ public class OwnershipAnalysis { System.out.println( treport ); if( aliasFile != null ) { - writeAllAliases(aliasFile); + if( state.TASK ) { + writeAllAliases(aliasFile); + } else { + writeAllAliasesJava(aliasFile); + } } } @@ -892,6 +921,23 @@ public class OwnershipAnalysis { } + private HashSet getFlaggedAllocationSites(Descriptor d) { + + HashSet out = new HashSet(); + + HashSet asSet = getAllocationSiteSet(d); + Iterator asItr = asSet.iterator(); + while( asItr.hasNext() ) { + AllocationSite as = (AllocationSite) asItr.next(); + if( as.getDisjointId() != null ) { + out.add(as); + } + } + + return out; + } + + private HashSet getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) { diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index e627dc54..6af319cb 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -2667,6 +2667,114 @@ public class OwnershipGraph { return id2paramIndexSet.size() == og.id2paramIndexSet.size(); } + + public boolean hasPotentialAlias( HeapRegionNode hrn1, HeapRegionNode hrn2 ) { + assert hrn1 != null; + assert hrn2 != null; + + // then get the various tokens for these heap regions + TokenTuple h1 = new TokenTuple(hrn1.getID(), + !hrn1.isSingleObject(), + TokenTuple.ARITY_ONE).makeCanonical(); + + TokenTuple h1plus = new TokenTuple(hrn1.getID(), + !hrn1.isSingleObject(), + TokenTuple.ARITY_ONEORMORE).makeCanonical(); + + TokenTuple h1star = new TokenTuple(hrn1.getID(), + !hrn1.isSingleObject(), + TokenTuple.ARITY_ZEROORMORE).makeCanonical(); + + TokenTuple h2 = new TokenTuple(hrn2.getID(), + !hrn2.isSingleObject(), + TokenTuple.ARITY_ONE).makeCanonical(); + + TokenTuple h2plus = new TokenTuple(hrn2.getID(), + !hrn2.isSingleObject(), + TokenTuple.ARITY_ONEORMORE).makeCanonical(); + + TokenTuple h2star = new TokenTuple(hrn2.getID(), + !hrn2.isSingleObject(), + TokenTuple.ARITY_ZEROORMORE).makeCanonical(); + + // then get the merged beta of all out-going edges from these heap regions + ReachabilitySet beta1 = new ReachabilitySet(); + Iterator itrEdge = hrn1.iteratorToReferencees(); + while( itrEdge.hasNext() ) { + ReferenceEdge edge = itrEdge.next(); + beta1 = beta1.union( edge.getBeta() ); + } + + ReachabilitySet beta2 = new ReachabilitySet(); + itrEdge = hrn2.iteratorToReferencees(); + while( itrEdge.hasNext() ) { + ReferenceEdge edge = itrEdge.next(); + beta2 = beta2.union( edge.getBeta() ); + } + + // only do this one if they are different tokens + if( h1 != h2 && + beta1.containsTupleSetWithBoth(h1, h2) ) { + return true; + } + if( beta1.containsTupleSetWithBoth(h1plus, h2) ) { + return true; + } + if( beta1.containsTupleSetWithBoth(h1star, h2) ) { + return true; + } + if( beta1.containsTupleSetWithBoth(h1, h2plus) ) { + return true; + } + if( beta1.containsTupleSetWithBoth(h1plus, h2plus) ) { + return true; + } + if( beta1.containsTupleSetWithBoth(h1star, h2plus) ) { + return true; + } + if( beta1.containsTupleSetWithBoth(h1, h2star) ) { + return true; + } + if( beta1.containsTupleSetWithBoth(h1plus, h2star) ) { + return true; + } + if( beta1.containsTupleSetWithBoth(h1star, h2star) ) { + return true; + } + + if( h1 != h2 && + beta2.containsTupleSetWithBoth(h1, h2) ) { + return true; + } + if( beta2.containsTupleSetWithBoth(h1plus, h2) ) { + return true; + } + if( beta2.containsTupleSetWithBoth(h1star, h2) ) { + return true; + } + if( beta2.containsTupleSetWithBoth(h1, h2plus) ) { + return true; + } + if( beta2.containsTupleSetWithBoth(h1plus, h2plus) ) { + return true; + } + if( beta2.containsTupleSetWithBoth(h1star, h2plus) ) { + return true; + } + if( beta2.containsTupleSetWithBoth(h1, h2star) ) { + return true; + } + if( beta2.containsTupleSetWithBoth(h1plus, h2star) ) { + return true; + } + if( beta2.containsTupleSetWithBoth(h1star, h2star) ) { + return true; + } + + return false; + } + + public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) { // get parameter's heap region @@ -2677,6 +2785,7 @@ public class OwnershipGraph { HeapRegionNode hrnParam1 = id2hrn.get(idParam1); assert hrnParam1 != null; + /* // get tokens for this parameter TokenTuple p1 = new TokenTuple(hrnParam1.getID(), true, @@ -2689,7 +2798,7 @@ public class OwnershipGraph { TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(), true, TokenTuple.ARITY_ZEROORMORE).makeCanonical(); - + */ // get tokens for the other parameter assert paramIndex2id.containsKey(paramIndex2); @@ -2699,6 +2808,12 @@ public class OwnershipGraph { HeapRegionNode hrnParam2 = id2hrn.get(idParam2); assert hrnParam2 != null; + + return hasPotentialAlias( hrnParam1, hrnParam2 ); + + + /* + TokenTuple p2 = new TokenTuple(hrnParam2.getID(), true, TokenTuple.ARITY_ONE).makeCanonical(); @@ -2754,8 +2869,9 @@ public class OwnershipGraph { if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) { return true; } - + return false; + */ } @@ -2769,6 +2885,8 @@ public class OwnershipGraph { HeapRegionNode hrnParam = id2hrn.get(idParam); assert hrnParam != null; + + /* // get tokens for this parameter TokenTuple p = new TokenTuple(hrnParam.getID(), true, @@ -2795,7 +2913,7 @@ public class OwnershipGraph { // look through this beta set for potential aliases ReachabilitySet beta = edgeSpecialQ.getBeta(); assert beta != null; - + // get tokens for summary node TokenTuple gs = new TokenTuple(as.getSummary(), @@ -2838,10 +2956,27 @@ public class OwnershipGraph { if( beta.containsTupleSetWithBoth(pStar, gsStar) ) { return true; } + */ + + assert id2hrn.containsKey( as.getSummary() ); + HeapRegionNode hrnSummary = id2hrn.get( as.getSummary() ); + assert hrnSummary != null; + if( hasPotentialAlias( hrnParam, hrnSummary ) ) { + return true; + } // check for other nodes for( int i = 0; i < as.getAllocationDepth(); ++i ) { + assert id2hrn.containsKey( as.getIthOldest( i ) ); + HeapRegionNode hrnIthOldest = id2hrn.get( as.getIthOldest( i ) ); + assert hrnIthOldest != null; + if( hasPotentialAlias( hrnParam, hrnIthOldest ) ) { + return true; + } + + + /* // the other nodes of an allocation site are single, no plus TokenTuple gi = new TokenTuple(as.getIthOldest(i), false, @@ -2869,14 +3004,15 @@ public class OwnershipGraph { if( beta.containsTupleSetWithBoth(pStar, giStar) ) { return true; } + */ } - return false; + return false; } public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) { - + /* // get tokens for summary nodes TokenTuple gs1 = new TokenTuple(as1.getSummary(), true, @@ -2889,15 +3025,18 @@ public class OwnershipGraph { TokenTuple gsStar1 = new TokenTuple(as1.getSummary(), true, TokenTuple.ARITY_ZEROORMORE).makeCanonical(); + */ // get summary node's alpha Integer idSum1 = as1.getSummary(); assert id2hrn.containsKey(idSum1); HeapRegionNode hrnSum1 = id2hrn.get(idSum1); assert hrnSum1 != null; + + /* ReachabilitySet alphaSum1 = hrnSum1.getAlpha(); assert alphaSum1 != null; - + // and for the other one TokenTuple gs2 = new TokenTuple(as2.getSummary(), @@ -2911,15 +3050,23 @@ public class OwnershipGraph { TokenTuple gsStar2 = new TokenTuple(as2.getSummary(), true, TokenTuple.ARITY_ZEROORMORE).makeCanonical(); + */ // get summary node's alpha Integer idSum2 = as2.getSummary(); assert id2hrn.containsKey(idSum2); HeapRegionNode hrnSum2 = id2hrn.get(idSum2); assert hrnSum2 != null; + + if( hasPotentialAlias( hrnSum1, hrnSum2 ) ) { + return true; + } + + /* ReachabilitySet alphaSum2 = hrnSum2.getAlpha(); assert alphaSum2 != null; + // does either one report reachability from the other tokens? if( alphaSum1.containsTuple(gsPlus2) ) { return true; @@ -2943,7 +3090,7 @@ public class OwnershipGraph { return true; } } - + */ // check sum2 against alloc1 nodes for( int i = 0; i < as1.getAllocationDepth(); ++i ) { @@ -2951,9 +3098,16 @@ public class OwnershipGraph { assert id2hrn.containsKey(idI1); HeapRegionNode hrnI1 = id2hrn.get(idI1); assert hrnI1 != null; + + if( hasPotentialAlias( hrnI1, hrnSum2 ) ) { + return true; + } + + /* ReachabilitySet alphaI1 = hrnI1.getAlpha(); assert alphaI1 != null; + // the other nodes of an allocation site are single, no stars TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i), false, @@ -2978,6 +3132,7 @@ public class OwnershipGraph { if( alphaI1.containsTuple(gsStar2) ) { return true; } + */ } // check sum1 against alloc2 nodes @@ -2986,6 +3141,12 @@ public class OwnershipGraph { assert id2hrn.containsKey(idI2); HeapRegionNode hrnI2 = id2hrn.get(idI2); assert hrnI2 != null; + + if( hasPotentialAlias( hrnSum1, hrnI2 ) ) { + return true; + } + + /* ReachabilitySet alphaI2 = hrnI2.getAlpha(); assert alphaI2 != null; @@ -3012,6 +3173,7 @@ public class OwnershipGraph { if( alphaI2.containsTuple(gsStar1) ) { return true; } + */ // while we're at it, do an inner loop for alloc2 vs alloc1 nodes for( int j = 0; j < as1.getAllocationDepth(); ++j ) { @@ -3024,6 +3186,12 @@ public class OwnershipGraph { } HeapRegionNode hrnI1 = id2hrn.get(idI1); + + if( hasPotentialAlias( hrnI1, hrnI2 ) ) { + return true; + } + + /* ReachabilitySet alphaI1 = hrnI1.getAlpha(); TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j), false, @@ -3045,6 +3213,7 @@ public class OwnershipGraph { if( alphaI1.containsTuple(giStar2) ) { return true; } + */ } } diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test05/makefile b/Robust/src/Tests/OwnershipAnalysisTest/test05/makefile new file mode 100644 index 00000000..fdfcf351 --- /dev/null +++ b/Robust/src/Tests/OwnershipAnalysisTest/test05/makefile @@ -0,0 +1,27 @@ +PROGRAM=test + +SOURCE_FILES=$(PROGRAM).java + +BUILDSCRIPT=~/research/Robust/src/buildscript +BSFLAGS= -mainclass Test -justanalyze -ownership -ownallocdepth 1 -ownwritedots final -ownaliasfile aliases.txt -enable-assertions + +all: $(PROGRAM).bin + +view: PNGs + eog *.png & + +PNGs: DOTs + d2p *COMPLETE*.dot + +DOTs: $(PROGRAM).bin + +$(PROGRAM).bin: $(SOURCE_FILES) + $(BUILDSCRIPT) $(BSFLAGS) -o $(PROGRAM) $(SOURCE_FILES) + +clean: + rm -f $(PROGRAM).bin + rm -fr tmpbuilddirectory + rm -f *~ + rm -f *.dot + rm -f *.png + rm -f aliases.txt diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test05/test.java b/Robust/src/Tests/OwnershipAnalysisTest/test05/test.java new file mode 100644 index 00000000..b1fc0d65 --- /dev/null +++ b/Robust/src/Tests/OwnershipAnalysisTest/test05/test.java @@ -0,0 +1,37 @@ +// x=disjoint "X" new X() +// y=disjoint "Y" new Y() +// x.f=y +// z=x +// a=z.f +// x.f=g +// +// What is B(a)? + + +public class X extends Y { + public Y f; + public X() {} +} + +public class Y { + public Y() {} +} + + +public class Test { + + static public void main( String[] args ) { + X x; + X z; + Y y; + Y a; + Y g = new Y(); + + x=disjoint X new X(); + y=disjoint Y new Y(); + x.f=y; + z=x; + a=z.f; + x.f=g; + } +} diff --git a/Robust/src/Tests/OwnershipAnalysisTest/testArrays/makefile b/Robust/src/Tests/OwnershipAnalysisTest/testArrays/makefile index f0449643..1d29e243 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/testArrays/makefile +++ b/Robust/src/Tests/OwnershipAnalysisTest/testArrays/makefile @@ -3,7 +3,7 @@ PROGRAM=test SOURCE_FILES=$(PROGRAM).java BUILDSCRIPT=~/research/Robust/src/buildscript -BSFLAGS= -justanalyze -ownership -ownallocdepth 1 -ownwritedots final -enable-assertions +BSFLAGS= -mainclass TestArrays -justanalyze -ownership -ownallocdepth 1 -ownwritedots final -ownaliasfile aliases.txt -enable-assertions all: $(PROGRAM).bin -- 2.34.1