Reachability bug fixes. Tokens propagate and age in allocation sites,

and the example programs produce results that are almost correct.  One
thing to note is that token propagation through many allocation sites
in a loop doesn't work properly, where the same field-by-field construction of
a single complex object does propagate the tokens.

diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java
index de8be2150fd625049237fcfed816486a32d3a18c..a7dfd223138f57ed3c1c690c189f582b3db1ffd3 100644 (file)
--- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java
+++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java
@@ -280,7 +280,7 @@ public class OwnershipAnalysis {
            if( !og.equals( ogPrev ) ) {
                mapDescriptorToCompleteOwnershipGraph.put( d, og );
 
-               og.writeGraph( d, true, false );
+               og.writeGraph( d, true, true, false );
 
                // only methods have dependents, tasks cannot
                // be invoked by any user program calls

diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java
index a7a65cd016d70a45c3e1f88da000bc53c783e796..7010de5bbdb71d575c7d8aee8d04434e5b41d813 100644 (file)
--- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java
+++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java
@@ -405,22 +405,9 @@ public class OwnershipGraph {
 
                addReferenceEdge( hrn, hrnSrc, repNew );
 
-
-
                ChangeTupleSet Cy = O.unionUpArityToChangeSet( R );
-               //ChangeTupleSet Cx = R.unionUpArityToChangeSet( O );
 
                propagateTokens( hrnSrc, Cy, nodesWithNewAlpha, edgesWithNewBeta );
-               //propagateTokens( hrn,    Cx, nodesWithNewAlpha, edgesWithNewBeta );
-
-               /*
-               // note that this picks up the beta after the propogation has
-               // been applied
-               ReferenceEdgeProperties repNew 
-                   = new ReferenceEdgeProperties( false, false, repSrc.getBetaNew() );
-
-               addReferenceEdge( hrn, hrnSrc, repNew );
-               */
            }
        }       
 
@@ -587,26 +574,6 @@ public class OwnershipGraph {
            Map.Entry               me  = (Map.Entry)               itrReferencee.next();
            hrnReferencee               = (HeapRegionNode)          me.getKey();
            ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
-           
-           // determine if another summary node is already referencing this referencee
-           /*
-           boolean       hasSummaryReferencer = false;
-           OwnershipNode onReferencer         = null;
-           Iterator      itrReferencer        = hrnReferencee.iteratorToReferencers();
-           while( itrReferencer.hasNext() ) {
-               onReferencer = (OwnershipNode) itrReferencer.next();
-               if( onReferencer instanceof HeapRegionNode ) {
-                   HeapRegionNode hrnPossibleSummary = (HeapRegionNode) onReferencer;
-                   if( hrnPossibleSummary.isNewSummary() ) {
-                       hasSummaryReferencer = true;
-                   }
-               }
-           }
-
-           addReferenceEdge( hrnSummary,
-                             hrnReferencee,
-                             new ReferenceEdgeProperties( !hasSummaryReferencer ) );
-           */
 
            ReferenceEdgeProperties repSummary = hrnSummary.getReferenceTo( hrnReferencee );
            ReferenceEdgeProperties repMerged = rep.copy();
@@ -644,6 +611,9 @@ public class OwnershipGraph {
            addReferenceEdge( onReferencer, hrnSummary, repMerged );
        }
 
+       // then merge alpha_k reachability into alpha_s
+       hrnSummary.setAlpha( hrnSummary.getAlpha().union( hrnK.getAlpha() ) );
+
        
        // then move down the line of heap region nodes
        // clobbering the ith and transferring all references
@@ -684,6 +654,9 @@ public class OwnershipGraph {
 
                addReferenceEdge( onReferencer, hrnI, rep.copy() );
            }       
+
+           // replace hrnI reachability with hrnImin1
+           hrnI.setAlpha( hrnImin1.getAlpha() );
        }
 
        // as stated above, the newest node alpha_0 should have had its
@@ -697,11 +670,12 @@ public class OwnershipGraph {
        // have touched this node, therefore assert it is non-null
        assert hrn0 != null;
 
+
        // clear all references in and out of newest node
        clearReferenceEdgesFrom( hrn0 );
        clearReferenceEdgesTo  ( hrn0 );
+       
 
-       /*
        // now tokens in reachability sets need to "age" as well
        ReferenceEdgeProperties repToAge = null;
        Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
@@ -717,7 +691,6 @@ public class OwnershipGraph {
                ageTokens( as, repToAge );
            }
        }
-
        HeapRegionNode hrnToAge = null;
        Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
        while( itrAllHRNodes.hasNext() ) {
@@ -734,8 +707,15 @@ public class OwnershipGraph {
                ageTokens( as, repToAge );
            }
        }
-       */
-       
+
+
+       // after tokens have been aged, reset newest node's reachability
+       hrn0.setAlpha( new ReachabilitySet( 
+                          new TokenTupleSet( 
+                              new TokenTuple( hrn0 ) 
+                                           ) 
+                                         ).makeCanonical() 
+                      );
     }
 
     protected void ageTokens( AllocationSite as, ReferenceEdgeProperties rep ) {
@@ -828,9 +808,9 @@ public class OwnershipGraph {
                        //System.out.println( "idCallee is "+idCallee );
                        //System.out.println( "idChildCallee is "+idChildCallee );
                        
-                       try {
-                           writeGraph( "caller", false, false );
-                           ogCallee.writeGraph( "callee", false, false );
+                       try {                       
+                           writeGraph( "caller", false, false, false );
+                           ogCallee.writeGraph( "callee", false, false, false );                           
                        } catch( IOException e ) {}
                    }
 
@@ -1517,6 +1497,22 @@ public class OwnershipGraph {
 
 
     // for writing ownership graphs to dot files
+    public void writeGraph( Descriptor methodDesc,
+                           FlatNode   fn,
+                           boolean    writeLabels,
+                           boolean    labelSelect,
+                           boolean    writeReferencers 
+                           ) throws java.io.IOException {
+       writeGraph(
+                  methodDesc.getSymbol() +
+                  methodDesc.getNum() +
+                  fn.toString(),
+                  writeLabels,
+                  labelSelect,
+                  writeReferencers
+                  );
+    }
+
     public void writeGraph( Descriptor methodDesc,
                            FlatNode   fn,
                            boolean    writeLabels,
@@ -1527,6 +1523,7 @@ public class OwnershipGraph {
                   methodDesc.getNum() +
                   fn.toString(),
                   writeLabels,
+                  false,
                   writeReferencers
                   );
     }
@@ -1540,12 +1537,29 @@ public class OwnershipGraph {
                   methodDesc.getNum() +
                   "COMPLETE",
                   writeLabels,
+                  false,
+                  writeReferencers
+                   );
+    }
+
+    public void writeGraph( Descriptor methodDesc,
+                           boolean    writeLabels,
+                           boolean    labelSelect,
+                           boolean    writeReferencers 
+                           ) throws java.io.IOException {
+       writeGraph( 
+                  methodDesc.getSymbol() +
+                  methodDesc.getNum() +
+                  "COMPLETE",
+                  writeLabels,
+                  labelSelect,
                   writeReferencers
                    );
     }
 
     public void writeGraph( String graphName,
                            boolean writeLabels,
+                           boolean labelSelect,
                            boolean writeReferencers 
                            ) throws java.io.IOException {
 
@@ -1587,6 +1601,16 @@ public class OwnershipGraph {
                Map.Entry me = (Map.Entry) i.next();
                LabelNode ln = (LabelNode) me.getValue();
                
+               if( labelSelect ) {
+                   String labelStr = ln.getTempDescriptorString();
+                   if( labelStr.startsWith( "___temp"      ) ||
+                       labelStr.startsWith( "___dst"       ) ||
+                       labelStr.startsWith( "___srctmp"   ) ||
+                       labelStr.startsWith( "___neverused" )   ) {
+                       continue;
+                   }
+               }
+
                HeapRegionNode hrn = null;
                Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
                while( heapRegionsItr.hasNext() ) {

diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java
index b3a35fcfb1d3641c45bcccf5d7aeddb92351c726..d412cffd9b3c8a343a4b9294c459d63923fb74c9 100644 (file)
--- a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java
+++ b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java
@@ -201,7 +201,8 @@ public class ReachabilitySet extends Canonical {
     }
 
 
-    public ReachabilitySet ageTokens( AllocationSite as ) {
+    public ReachabilitySet ageTokens( AllocationSite as ) {    
+
        ReachabilitySet rsOut = new ReachabilitySet();
 
        Iterator itrS = this.iterator();

diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java
index c9c96abe94a21f73f0cb641f9c1dea3b675d95de..edd9edccdd105dc098c693038fc346cee253ea77 100644 (file)
--- a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java
+++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java
@@ -31,10 +31,12 @@ public class TokenTupleSet extends Canonical {
        return tokenTuples.iterator();
     }
 
+    /*
     public TokenTupleSet add( TokenTuple tt ) {
        TokenTupleSet ttsOut = new TokenTupleSet( tt );
        return this.union( ttsOut );
     }
+    */
 
     public TokenTupleSet union( TokenTupleSet ttsIn ) {
        TokenTupleSet ttsOut = new TokenTupleSet( this );
@@ -144,7 +146,7 @@ public class TokenTupleSet extends Canonical {
     }
 
     public TokenTupleSet ageTokens( AllocationSite as ) {
-       TokenTupleSet ttsOut = new TokenTupleSet( this );
+       TokenTupleSet ttsOut = new TokenTupleSet();
 
        TokenTuple ttSummary = null;
        boolean foundOldest  = false;
@@ -158,26 +160,29 @@ public class TokenTupleSet extends Canonical {
 
            // summary tokens and tokens not associated with
            // the site should be left alone
-           if( age != AllocationSite.AGE_notInThisSite ) {
+           if( age == AllocationSite.AGE_notInThisSite ) {
+               ttsOut.tokenTuples.add( tt );
 
+           } else {
                if( age == AllocationSite.AGE_summary ) {
                    // remember the summary tuple, but don't add it
                    // we may combine it with the oldest tuple
                    ttSummary = tt;
 
                } else if( age == AllocationSite.AGE_oldest ) {
-                   // found a token                
+                   // found an oldest token, again just remember
+                   // for later
                    foundOldest = true;
 
                } else {
                    // otherwise, we change this token to the
                    // next older token
                    Integer tokenToChangeTo = as.getIthOldest( age + 1 );                  
-                   tt = tt.changeTokenTo( tokenToChangeTo );
+                   TokenTuple ttAged       = tt.changeTokenTo( tokenToChangeTo );
+                   ttsOut.tokenTuples.add( ttAged );
                }
-           }
 
-           ttsOut.add( tt );
+           }
        }
 
        // there are four cases to consider here
@@ -189,15 +194,15 @@ public class TokenTupleSet extends Canonical {
        //    Merge them by increasing arity of summary
        // 4. (not handled) we found neither, do nothing
        if       ( ttSummary != null && !foundOldest ) {
-           ttsOut.add( ttSummary );
+           ttsOut.tokenTuples.add( ttSummary );
 
        } else if( ttSummary == null &&  foundOldest ) {
-           ttsOut.add( new TokenTuple( as.getSummary(),
+           ttsOut.tokenTuples.add( new TokenTuple( as.getSummary(),
                                        true,
                                        TokenTuple.ARITY_ONE ).makeCanonical() );          
        
        } else if( ttSummary != null &&  foundOldest ) {
-           ttsOut.add( ttSummary.increaseArity() );
+           ttsOut.tokenTuples.add( ttSummary.increaseArity() );
        }
 
        return ttsOut.makeCanonical();

diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java
index 8b843453d3311ee1856a245effc719a5b87287cf..c616953a207ea306d115f900cd28bb620bf97d9c 100644 (file)
--- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java
+++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java
@@ -53,29 +53,28 @@ public class Foo {
 // look for the parameter s as a label referencing
 // a heap region that is multi-object, flagged, not summary
 task Startup( StartupObject s{ initialstate } ) {
-
+    
     while( false ) {
        Foo a = new Foo();
        a.x   = new Foo();
+       a.x.x = new Foo();
     }
-
-    /*
+    
+    
     Foo b;
     while( false ) {
        Foo c = new Foo();
        c.x = b;
        b = c;
     }
-    */
-
-    /*
-    Foo a = new Foo();
-    Foo b = new Foo();
-    Foo c = new Foo();
+    
+    
+    Foo d = new Foo();
+    Foo e = new Foo();
+    Foo f = new Foo();
 
-    a.x = b;
-    b.x = c;    
-    */
+    d.x = e;
+    e.x = f;    
 
     taskexit( s{ !initialstate } );
 }