From 49ed071cafa6dbe18aca5971d19e3f8ae9689b8b Mon Sep 17 00:00:00 2001 From: jjenista Date: Thu, 7 Jan 2010 00:09:39 +0000 Subject: [PATCH] more implementation --- Robust/src/Analysis/Disjoint/AllocSite.java | 106 ++++++++++-------- .../Analysis/Disjoint/DisjointAnalysis.java | 7 +- .../src/Analysis/Disjoint/HeapRegionNode.java | 5 +- Robust/src/Analysis/Disjoint/ReachGraph.java | 54 +++++---- Robust/src/Tests/disjoint/simple/test.java | 13 ++- .../disjoint/worstCaseRecursive/makefile | 27 +++++ .../disjoint/worstCaseRecursive/test.java | 17 +++ 7 files changed, 151 insertions(+), 78 deletions(-) create mode 100644 Robust/src/Tests/disjoint/worstCaseRecursive/makefile create mode 100644 Robust/src/Tests/disjoint/worstCaseRecursive/test.java diff --git a/Robust/src/Analysis/Disjoint/AllocSite.java b/Robust/src/Analysis/Disjoint/AllocSite.java index 70bf0794..55f60961 100644 --- a/Robust/src/Analysis/Disjoint/AllocSite.java +++ b/Robust/src/Analysis/Disjoint/AllocSite.java @@ -21,42 +21,49 @@ import java.util.*; public class AllocSite { - static private int uniqueIDcount = 0; - - protected Integer id; - protected int allocationDepth; - protected Vector ithOldest; - protected Integer summary; - protected FlatNew flatNew; - protected String disjointId; + static protected int uniqueIDcount = 0; public static final int AGE_notInThisSite = 100; public static final int AGE_in_I = 101; public static final int AGE_oldest = 102; public static final int AGE_summary = 103; + public static final int AGE_siteSummary = 200; public static final int SHADOWAGE_notInThisSite = -100; public static final int SHADOWAGE_in_I = -101; public static final int SHADOWAGE_oldest = -102; public static final int SHADOWAGE_summary = -103; - - private boolean flag=false; + public static final int SHADOWAGE_siteSummary = -200; + + protected Integer id; + protected int allocationDepth; + protected Vector ithOldest; + protected Integer summary; + protected Integer siteSummary; + protected FlatNew flatNew; + protected String disjointId; + protected boolean flag; - public AllocSite(int allocationDepth, FlatNew flatNew, String disjointId) { + public AllocSite( int allocationDepth, + FlatNew flatNew, + String disjointId + ) { + assert allocationDepth >= 1; this.allocationDepth = allocationDepth; this.flatNew = flatNew; this.disjointId = disjointId; + this.flag = false; - ithOldest = new Vector(allocationDepth); + ithOldest = new Vector( allocationDepth ); id = generateUniqueAllocSiteID(); } static public Integer generateUniqueAllocSiteID() { ++uniqueIDcount; - return new Integer(uniqueIDcount); + return new Integer( uniqueIDcount ); } @@ -69,37 +76,37 @@ public class AllocSite { return allocationDepth; } - public void setIthOldest(int i, Integer id) { + public void setIthOldest( int i, Integer id ) { assert i >= 0; assert i < allocationDepth; assert id != null; - ithOldest.add(i, id); + ithOldest.add( i, id ); } - public Integer getIthOldest(int i) { + public Integer getIthOldest( int i ) { assert i >= 0; assert i < allocationDepth; - return ithOldest.get(i); + return ithOldest.get( i ); } - public Integer getIthOldestShadow(int i) { + public Integer getIthOldestShadow( int i ) { assert i >= 0; assert i < allocationDepth; - return -ithOldest.get(i); + return -ithOldest.get( i ); } public Integer getOldest() { - return ithOldest.get(allocationDepth - 1); + return ithOldest.get( allocationDepth - 1 ); } public Integer getOldestShadow() { - return -ithOldest.get(allocationDepth - 1); + return -ithOldest.get( allocationDepth - 1 ); } - public void setSummary(Integer id) { + public void setSummary( Integer id ) { assert id != null; summary = id; } @@ -112,6 +119,11 @@ public class AllocSite { return -summary; } + public void setSiteSummary( Integer id ) { + assert id != null; + siteSummary = id; + } + public FlatNew getFlatNew() { return flatNew; } @@ -120,18 +132,18 @@ public class AllocSite { return flatNew.getType(); } - public int getAgeCategory(Integer id) { + public int getAgeCategory( Integer id ) { - if( id.equals(summary) ) { + if( id.equals( summary ) ) { return AGE_summary; } - if( id.equals(getOldest() ) ) { + if( id.equals( getOldest() ) ) { return AGE_oldest; } for( int i = 0; i < allocationDepth - 1; ++i ) { - if( id.equals(ithOldest.get(i) ) ) { + if( id.equals( ithOldest.get( i ) ) ) { return AGE_in_I; } } @@ -139,27 +151,27 @@ public class AllocSite { return AGE_notInThisSite; } - public Integer getAge(Integer id) { + public Integer getAge( Integer id ) { for( int i = 0; i < allocationDepth - 1; ++i ) { - if( id.equals(ithOldest.get(i) ) ) { - return new Integer(i); + if( id.equals( ithOldest.get( i ) ) ) { + return new Integer( i ); } } return null; } - public int getShadowAgeCategory(Integer id) { - if( id.equals(-summary) ) { + public int getShadowAgeCategory( Integer id ) { + if( id.equals( -summary ) ) { return SHADOWAGE_summary; } - if( id.equals(getOldestShadow() ) ) { + if( id.equals( getOldestShadow() ) ) { return SHADOWAGE_oldest; } for( int i = 0; i < allocationDepth - 1; ++i ) { - if( id.equals(getIthOldestShadow(i) ) ) { + if( id.equals( getIthOldestShadow( i ) ) ) { return SHADOWAGE_in_I; } } @@ -167,10 +179,10 @@ public class AllocSite { return SHADOWAGE_notInThisSite; } - public Integer getShadowAge(Integer id) { + public Integer getShadowAge( Integer id ) { for( int i = 0; i < allocationDepth - 1; ++i ) { - if( id.equals(getIthOldestShadow(i) ) ) { - return new Integer(-i); + if( id.equals( getIthOldestShadow( i ) ) ) { + return new Integer( -i ); } } @@ -179,31 +191,35 @@ public class AllocSite { public String toString() { if( disjointId == null ) { - return "allocSite" + id; + return "allocSite"+id; } return "allocSite "+disjointId+" ("+id+")"; } public String toStringVerbose() { if( disjointId == null ) { - return "allocSite" + id + " "+flatNew.getType().toPrettyString(); + return "allocSite"+id+" "+ + flatNew.getType().toPrettyString(); } - return "allocSite "+disjointId+" ("+id+") "+flatNew.getType().toPrettyString(); + return "allocSite "+disjointId+" ("+id+") "+ + flatNew.getType().toPrettyString(); } public String toStringForDOT() { if( disjointId != null ) { - return "disjoint "+disjointId+"\\n"+toString()+"\\n"+getType().toPrettyString(); + return "disjoint "+disjointId+"\\n"+toString()+ + "\\n"+getType().toPrettyString(); } else { - return toString()+"\\n"+getType().toPrettyString(); + return toString()+ + "\\n"+getType().toPrettyString(); } } - public void setFlag(boolean flag){ - this.flag=flag; + public void setFlag( boolean flag ) { + this.flag = flag; } - public boolean getFlag(){ - return flag; + public boolean getFlag() { + return flag; } } diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index d85979c1..9fb1f9c9 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -742,8 +742,11 @@ public class DisjointAnalysis { } // the oldest node is a summary node - Integer idSummary = generateUniqueHeapRegionNodeID(); - as.setSummary( idSummary ); + as.setSummary( generateUniqueHeapRegionNodeID() ); + + // and one special node is older than all + // nodes and shadow nodes for the site + as.setSiteSummary( generateUniqueHeapRegionNodeID() ); mapFlatNewToAllocSite.put( fnew, as ); } diff --git a/Robust/src/Analysis/Disjoint/HeapRegionNode.java b/Robust/src/Analysis/Disjoint/HeapRegionNode.java index e40902f3..5213aa6b 100644 --- a/Robust/src/Analysis/Disjoint/HeapRegionNode.java +++ b/Robust/src/Analysis/Disjoint/HeapRegionNode.java @@ -51,6 +51,7 @@ public class HeapRegionNode extends RefSrcNode { ReachSet alpha, String description ) { + this.id = id; this.isSingleObject = isSingleObject; this.isFlagged = isFlagged; @@ -135,11 +136,11 @@ public class HeapRegionNode extends RefSrcNode { } public boolean isOutOfContext() { - return isOutOfContext(); + return isOutOfContext; } public boolean isClean() { - return isClean(); + return isClean; } public void setIsClean( boolean isClean ) { diff --git a/Robust/src/Analysis/Disjoint/ReachGraph.java b/Robust/src/Analysis/Disjoint/ReachGraph.java index 8b151731..253c883b 100644 --- a/Robust/src/Analysis/Disjoint/ReachGraph.java +++ b/Robust/src/Analysis/Disjoint/ReachGraph.java @@ -2370,32 +2370,36 @@ public class ReachGraph { return typeUtil.isSuperorType(tdEdge, tdDst); } - /* - protected void unshadowTokens(AllocSite as, RefEdge edge) { - edge.setBeta(edge.getBeta().unshadowTokens(as) ); + + protected void unshadowTokens( AllocSite as, + RefEdge edge + ) { + edge.setBeta( edge.getBeta().unshadowTokens( as ) ); } - protected void unshadowTokens(AllocSite as, HeapRegionNode hrn) { - hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) ); + protected void unshadowTokens( AllocSite as, + HeapRegionNode hrn + ) { + hrn.setAlpha( hrn.getAlpha().unshadowTokens( as ) ); } - private ReachSet toShadowTokens(ReachGraph ogCallee, - ReachSet rsIn) { - - ReachSet rsOut = new ReachSet(rsIn).makeCanonical(); + private ReachSet toShadowTokens( ReachGraph rg, + ReachSet rsIn + ) { + ReachSet rsOut = new ReachSet( rsIn ).makeCanonical(); - Iterator allocItr = ogCallee.allocSites.iterator(); + Iterator allocItr = rg.allocSites.iterator(); while( allocItr.hasNext() ) { AllocSite as = allocItr.next(); - - rsOut = rsOut.toShadowTokens(as); + rsOut = rsOut.toShadowTokens( as ); } return rsOut.makeCanonical(); } + /* private void rewriteCallerReachability(Integer paramIndex, HeapRegionNode hrn, RefEdge edge, @@ -3433,8 +3437,8 @@ public class ReachGraph { false, // out-of-context? hrnSrcCaller.getType(), hrnSrcCaller.getAllocSite(), - hrnSrcCaller.getInherent(), - hrnSrcCaller.getAlpha(), + toShadowTokens( this, hrnSrcCaller.getInherent() ), + toShadowTokens( this, hrnSrcCaller.getAlpha() ), hrnSrcCaller.getDescription() ); callerNodesCopiedToCallee.add( rsnCaller ); @@ -3463,8 +3467,8 @@ public class ReachGraph { false, // out-of-context? hrnCaller.getType(), hrnCaller.getAllocSite(), - hrnCaller.getInherent(), - hrnCaller.getAlpha(), + toShadowTokens( this, hrnCaller.getInherent() ), + toShadowTokens( this, hrnCaller.getAlpha() ), hrnCaller.getDescription() ); callerNodesCopiedToCallee.add( hrnCaller ); @@ -3481,7 +3485,7 @@ public class ReachGraph { reCaller.getType(), reCaller.getField(), true, // clean? - reCaller.getBeta() + toShadowTokens( this, reCaller.getBeta() ) ) ); callerEdgesCopiedToCallee.add( reCaller ); @@ -3536,8 +3540,8 @@ public class ReachGraph { true, // out-of-context? hrnCallerAndOutContext.getType(), null, // alloc site, shouldn't be used - hrnCallerAndOutContext.getAlpha(), // inherent - hrnCallerAndOutContext.getAlpha(), // alpha + toShadowTokens( this, hrnCallerAndOutContext.getAlpha() ), // inherent + toShadowTokens( this, hrnCallerAndOutContext.getAlpha() ), // alpha "out-of-context" ); @@ -3551,7 +3555,7 @@ public class ReachGraph { edgeMightCross.getType(), edgeMightCross.getField(), true, // clean? - edgeMightCross.getBeta() + toShadowTokens( this, edgeMightCross.getBeta() ) ) ); @@ -3652,9 +3656,13 @@ public class ReachGraph { Map.Entry me = (Map.Entry) i.next(); HeapRegionNode hrn = (HeapRegionNode) me.getValue(); - if( !pruneGarbage || - (hrn.isFlagged() && hrn.getID() > 0) || - hrn.getDescription().startsWith( "param" ) + // only visit nodes worth writing out--for instance + // not every node at an allocation is referenced + // (think of it as garbage-collected), etc. + if( !pruneGarbage || + (hrn.isFlagged() && hrn.getID() > 0) || + hrn.getDescription().startsWith( "param" ) || + hrn.isOutOfContext() ) { if( !visited.contains( hrn ) ) { diff --git a/Robust/src/Tests/disjoint/simple/test.java b/Robust/src/Tests/disjoint/simple/test.java index c6b136c4..c0f6cc7f 100644 --- a/Robust/src/Tests/disjoint/simple/test.java +++ b/Robust/src/Tests/disjoint/simple/test.java @@ -5,13 +5,14 @@ public class Foo { public class Test { static public void main( String[] args ) { - Foo a = new Foo(); - f1( a ); + Foo a = disjoint A new Foo(); + Foo b = disjoint B new Foo(); + a.f = b; + f1( b ); } - static public void f1( Foo b ) { - Foo c = new Foo(); - b.f = c; - f1( c ); + static public void f1( Foo c ) { + Foo d = new Foo(); + c.f = d; } } diff --git a/Robust/src/Tests/disjoint/worstCaseRecursive/makefile b/Robust/src/Tests/disjoint/worstCaseRecursive/makefile new file mode 100644 index 00000000..dcb012af --- /dev/null +++ b/Robust/src/Tests/disjoint/worstCaseRecursive/makefile @@ -0,0 +1,27 @@ +PROGRAM=test + +SOURCE_FILES=$(PROGRAM).java + +BUILDSCRIPT=~/research/Robust/src/buildscript +BSFLAGS= -mainclass Test -justanalyze -disjoint -disjoint-k 1 -disjoint-write-dots final -disjoint-alias-file aliases.txt normal -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/disjoint/worstCaseRecursive/test.java b/Robust/src/Tests/disjoint/worstCaseRecursive/test.java new file mode 100644 index 00000000..c6b136c4 --- /dev/null +++ b/Robust/src/Tests/disjoint/worstCaseRecursive/test.java @@ -0,0 +1,17 @@ +public class Foo { + public Foo() {} + public Foo f; +} + +public class Test { + static public void main( String[] args ) { + Foo a = new Foo(); + f1( a ); + } + + static public void f1( Foo b ) { + Foo c = new Foo(); + b.f = c; + f1( c ); + } +} -- 2.34.1