more implementation

diff --git a/Robust/src/Analysis/Disjoint/AllocSite.java b/Robust/src/Analysis/Disjoint/AllocSite.java
index 70bf0794d318c6b36fbc852ae2ed5a9d08cc171e..55f6096199bbedb343067f908bebbbdeda6c7ca3 100644 (file)
--- 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<Integer> 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<Integer> 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<Integer>(allocationDepth);
+    ithOldest = new Vector<Integer>( 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 d85979c1d36209f9dd95d7693e8e4ca035aa3983..9fb1f9c94f31c13c99149c707f5a42ca79a46f55 100644 (file)
--- 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 e40902f3a6db7203b4031ef7e3cf1d56f71e85c6..5213aa6bf1fbd1ef0bf30ec05da45cfa550b7193 100644 (file)
--- 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 8b151731c320b51ddccf4c1cc65d15398be97e2d..253c883b690ba8c1a357d73d45d3711727220bb0 100644 (file)
--- 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<AllocSite> allocItr = ogCallee.allocSites.iterator();
+    Iterator<AllocSite> 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 c6b136c4872212da17f813063167ffc1a692853b..c0f6cc7f13169c3fd1cc80430eb0c6be0eec949a 100644 (file)
--- 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 (file)
index 0000000..dcb012a
--- /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 (file)
index 0000000..c6b136c
--- /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 );
+  }
+}