Introduced ZEROORMORE arity, something appears to be broken so another change is...
authorjjenista <jjenista>
Mon, 29 Sep 2008 18:43:31 +0000 (18:43 +0000)
committerjjenista <jjenista>
Mon, 29 Sep 2008 18:43:31 +0000 (18:43 +0000)
Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java
Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java
Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java
Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java
Robust/src/buildscript

index 6684415753748b96e25413dfbadb8ba1b9f406ae..7e3f6af3d00dc308072ab66fa0d23367a8a6f628 100644 (file)
@@ -925,10 +925,10 @@ public class OwnershipGraph {
     Hashtable<Integer, TokenTuple> paramIndex2paramToken =
       new Hashtable<Integer, TokenTuple>();
 
     Hashtable<Integer, TokenTuple> paramIndex2paramToken =
       new Hashtable<Integer, TokenTuple>();
 
-    Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex =
+    Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex =
       new Hashtable<TokenTuple, Integer>();
 
       new Hashtable<TokenTuple, Integer>();
 
-    Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar =
+    Hashtable<Integer, TokenTuple> paramIndex2paramTokenPlus =
       new Hashtable<Integer, TokenTuple>();
 
     Hashtable<Integer, LabelNode> paramIndex2ln =
       new Hashtable<Integer, TokenTuple>();
 
     Hashtable<Integer, LabelNode> paramIndex2ln =
@@ -943,7 +943,7 @@ public class OwnershipGraph {
     Integer bogusID = new Integer(-1);
     Integer bogusIndex = new Integer(-1);
     TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE);
     Integer bogusID = new Integer(-1);
     Integer bogusIndex = new Integer(-1);
     TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE);
-    TokenTuple bogusTokenStar = new TokenTuple(bogusID, true, TokenTuple.ARITY_MANY);
+    TokenTuple bogusTokenPlus = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONEORMORE);
     ReachabilitySet rsIdentity =
       new ReachabilitySet(new TokenTupleSet(bogusToken).makeCanonical() ).makeCanonical();
 
     ReachabilitySet rsIdentity =
       new ReachabilitySet(new TokenTupleSet(bogusToken).makeCanonical() ).makeCanonical();
 
@@ -951,8 +951,8 @@ public class OwnershipGraph {
     paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
     paramToken2paramIndex.put(bogusToken, bogusIndex);
     paramIndex2paramToken.put(bogusIndex, bogusToken);
     paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
     paramToken2paramIndex.put(bogusToken, bogusIndex);
     paramIndex2paramToken.put(bogusIndex, bogusToken);
-    paramTokenStar2paramIndex.put(bogusTokenStar, bogusIndex);
-    paramIndex2paramTokenStar.put(bogusIndex, bogusTokenStar);
+    paramTokenPlus2paramIndex.put(bogusTokenPlus, bogusIndex);
+    paramIndex2paramTokenPlus.put(bogusIndex, bogusTokenPlus);
 
 
     for( int i = 0; i < fm.numParameters(); ++i ) {
 
 
     for( int i = 0; i < fm.numParameters(); ++i ) {
@@ -991,11 +991,11 @@ public class OwnershipGraph {
       paramToken2paramIndex.put(p_i, paramIndex);
       paramIndex2paramToken.put(paramIndex, p_i);
 
       paramToken2paramIndex.put(p_i, paramIndex);
       paramIndex2paramToken.put(paramIndex, p_i);
 
-      TokenTuple p_i_star = new TokenTuple(hrnParam.getID(),
+      TokenTuple p_i_plus = new TokenTuple(hrnParam.getID(),
                                            true,
                                            true,
-                                           TokenTuple.ARITY_MANY).makeCanonical();
-      paramTokenStar2paramIndex.put(p_i_star, paramIndex);
-      paramIndex2paramTokenStar.put(paramIndex, p_i_star);
+                                           TokenTuple.ARITY_ONEORMORE).makeCanonical();
+      paramTokenPlus2paramIndex.put(p_i_plus, paramIndex);
+      paramIndex2paramTokenPlus.put(paramIndex, p_i_plus);
 
       // now depending on whether the callee is static or not
       // we need to account for a "this" argument in order to
 
       // now depending on whether the callee is static or not
       // we need to account for a "this" argument in order to
@@ -1091,7 +1091,7 @@ public class OwnershipGraph {
                                  paramIndex2rewriteD,
                                  paramIndex2paramToken.get(index),
                                  paramToken2paramIndex,
                                  paramIndex2rewriteD,
                                  paramIndex2paramToken.get(index),
                                  paramToken2paramIndex,
-                                 paramTokenStar2paramIndex,
+                                 paramTokenPlus2paramIndex,
                                  false,
                                  null);
 
                                  false,
                                  null);
 
@@ -1140,7 +1140,7 @@ public class OwnershipGraph {
                                  paramIndex2rewriteD,
                                  paramIndex2paramToken.get(index),
                                  paramToken2paramIndex,
                                  paramIndex2rewriteD,
                                  paramIndex2paramToken.get(index),
                                  paramToken2paramIndex,
-                                 paramTokenStar2paramIndex,
+                                 paramTokenPlus2paramIndex,
                                  false,
                                  null);
 
                                  false,
                                  null);
 
@@ -1163,7 +1163,7 @@ public class OwnershipGraph {
                                  paramIndex2rewriteD,
                                  paramIndex2paramToken.get(index),
                                  paramToken2paramIndex,
                                  paramIndex2rewriteD,
                                  paramIndex2paramToken.get(index),
                                  paramToken2paramIndex,
-                                 paramTokenStar2paramIndex,
+                                 paramTokenPlus2paramIndex,
                                  true,
                                  edgeUpstreamPlannedChanges);
 
                                  true,
                                  edgeUpstreamPlannedChanges);
 
@@ -1222,7 +1222,7 @@ public class OwnershipGraph {
                                paramIndex2rewriteD,
                                bogusToken,
                                paramToken2paramIndex,
                                paramIndex2rewriteD,
                                bogusToken,
                                paramToken2paramIndex,
-                               paramTokenStar2paramIndex,
+                               paramTokenPlus2paramIndex,
                                false,
                                null);
 
                                false,
                                null);
 
@@ -1254,7 +1254,7 @@ public class OwnershipGraph {
                                  paramIndex2rewriteD,
                                  bogusToken,
                                  paramToken2paramIndex,
                                  paramIndex2rewriteD,
                                  bogusToken,
                                  paramToken2paramIndex,
-                                 paramTokenStar2paramIndex,
+                                 paramTokenPlus2paramIndex,
                                  false,
                                  null);
 
                                  false,
                                  null);
 
@@ -1306,7 +1306,7 @@ public class OwnershipGraph {
                                    paramIndex2rewriteD,
                                    bogusToken,
                                    paramToken2paramIndex,
                                    paramIndex2rewriteD,
                                    bogusToken,
                                    paramToken2paramIndex,
-                                   paramTokenStar2paramIndex,
+                                   paramTokenPlus2paramIndex,
                                    false,
                                    null);
 
                                    false,
                                    null);
 
@@ -1392,7 +1392,7 @@ public class OwnershipGraph {
                                  paramIndex2rewriteD,
                                  bogusToken,
                                  paramToken2paramIndex,
                                  paramIndex2rewriteD,
                                  bogusToken,
                                  paramToken2paramIndex,
-                                 paramTokenStar2paramIndex,
+                                 paramTokenPlus2paramIndex,
                                  false,
                                  null);
 
                                  false,
                                  null);
 
@@ -1595,7 +1595,7 @@ public class OwnershipGraph {
                                         Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
                                         TokenTuple p_i,
                                         Hashtable<TokenTuple, Integer> paramToken2paramIndex,
                                         Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
                                         TokenTuple p_i,
                                         Hashtable<TokenTuple, Integer> paramToken2paramIndex,
-                                        Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex,
+                                        Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex,
                                         boolean makeChangeSet,
                                         Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
     assert (hrn == null && edge != null) || 
                                         boolean makeChangeSet,
                                         Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
     assert (hrn == null && edge != null) || 
@@ -1651,9 +1651,9 @@ public class OwnershipGraph {
          ttCalleeRewrites = paramIndex2rewrite_d.get( paramIndex_j );
          assert ttCalleeRewrites != null;
 
          ttCalleeRewrites = paramIndex2rewrite_d.get( paramIndex_j );
          assert ttCalleeRewrites != null;
 
-       } else if( paramTokenStar2paramIndex.containsKey( ttCallee ) ) {
+       } else if( paramTokenPlus2paramIndex.containsKey( ttCallee ) ) {
          // worse, use big D
          // worse, use big D
-         Integer paramIndex_j = paramTokenStar2paramIndex.get( ttCallee );
+         Integer paramIndex_j = paramTokenPlus2paramIndex.get( ttCallee );
          assert paramIndex_j != null;
          ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
          assert ttCalleeRewrites != null;
          assert paramIndex_j != null;
          ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
          assert ttCalleeRewrites != null;
@@ -2252,9 +2252,13 @@ public class OwnershipGraph {
                                    true,
                                    TokenTuple.ARITY_ONE).makeCanonical();
 
                                    true,
                                    TokenTuple.ARITY_ONE).makeCanonical();
 
+    TokenTuple pPlus1 = new TokenTuple(hrnParam1.getID(),
+                                       true,
+                                       TokenTuple.ARITY_ONEORMORE).makeCanonical();
+
     TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
                                        true,
     TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
                                        true,
-                                       TokenTuple.ARITY_MANY).makeCanonical();
+                                       TokenTuple.ARITY_ZEROORMORE).makeCanonical();
 
 
     // get tokens for the other parameter
 
 
     // get tokens for the other parameter
@@ -2269,9 +2273,13 @@ public class OwnershipGraph {
                                    true,
                                    TokenTuple.ARITY_ONE).makeCanonical();
 
                                    true,
                                    TokenTuple.ARITY_ONE).makeCanonical();
 
+    TokenTuple pPlus2 = new TokenTuple(hrnParam2.getID(),
+                                       true,
+                                       TokenTuple.ARITY_ONEORMORE).makeCanonical();
+
     TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
                                        true,
     TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
                                        true,
-                                       TokenTuple.ARITY_MANY).makeCanonical();
+                                       TokenTuple.ARITY_ZEROORMORE).makeCanonical();
 
 
     // get special label p_q for first parameter
 
 
     // get special label p_q for first parameter
@@ -2289,18 +2297,15 @@ public class OwnershipGraph {
     ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
     assert beta1 != null;
 
     ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
     assert beta1 != null;
 
-    if( beta1.containsTupleSetWithBoth(p1,     p2) ) {
-      return true;
-    }
-    if( beta1.containsTupleSetWithBoth(pStar1, p2) ) {
-      return true;
-    }
-    if( beta1.containsTupleSetWithBoth(p1,     pStar2) ) {
-      return true;
-    }
-    if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) {
-      return true;
-    }
+    if( beta1.containsTupleSetWithBoth(p1,     p2    ) ) { return true; }
+    if( beta1.containsTupleSetWithBoth(pPlus1, p2    ) ) { return true; }
+    if( beta1.containsTupleSetWithBoth(pStar1, p2    ) ) { return true; }
+    if( beta1.containsTupleSetWithBoth(p1,     pPlus2) ) { return true; }
+    if( beta1.containsTupleSetWithBoth(pPlus1, pPlus2) ) { return true; }
+    if( beta1.containsTupleSetWithBoth(pStar1, pPlus2) ) { return true; }
+    if( beta1.containsTupleSetWithBoth(p1,     pStar2) ) { return true; }
+    if( beta1.containsTupleSetWithBoth(pPlus1, pStar2) ) { return true; }
+    if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) { return true; }
 
     return false;
   }
 
     return false;
   }
@@ -2321,9 +2326,13 @@ public class OwnershipGraph {
                                   true,
                                   TokenTuple.ARITY_ONE).makeCanonical();
 
                                   true,
                                   TokenTuple.ARITY_ONE).makeCanonical();
 
+    TokenTuple pPlus = new TokenTuple(hrnParam.getID(),
+                                      true,
+                                      TokenTuple.ARITY_ONEORMORE).makeCanonical();
+
     TokenTuple pStar = new TokenTuple(hrnParam.getID(),
                                       true,
     TokenTuple pStar = new TokenTuple(hrnParam.getID(),
                                       true,
-                                      TokenTuple.ARITY_MANY).makeCanonical();
+                                      TokenTuple.ARITY_ZEROORMORE).makeCanonical();
 
     // get special label p_q
     TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
 
     // get special label p_q
     TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
@@ -2345,37 +2354,43 @@ public class OwnershipGraph {
                                    true,
                                    TokenTuple.ARITY_ONE).makeCanonical();
 
                                    true,
                                    TokenTuple.ARITY_ONE).makeCanonical();
 
+    TokenTuple gsPlus = new TokenTuple(as.getSummary(),
+                                       true,
+                                       TokenTuple.ARITY_ONEORMORE).makeCanonical();
+
     TokenTuple gsStar = new TokenTuple(as.getSummary(),
                                        true,
     TokenTuple gsStar = new TokenTuple(as.getSummary(),
                                        true,
-                                       TokenTuple.ARITY_MANY).makeCanonical();
+                                       TokenTuple.ARITY_ZEROORMORE).makeCanonical();
 
 
-    if( beta.containsTupleSetWithBoth(p,     gs) ) {
-      return true;
-    }
-    if( beta.containsTupleSetWithBoth(pStar, gs) ) {
-      return true;
-    }
-    if( beta.containsTupleSetWithBoth(p,     gsStar) ) {
-      return true;
-    }
-    if( beta.containsTupleSetWithBoth(pStar, gsStar) ) {
-      return true;
-    }
+
+    if( beta.containsTupleSetWithBoth(p,     gs    ) ) { return true; }
+    if( beta.containsTupleSetWithBoth(pPlus, gs    ) ) { return true; }
+    if( beta.containsTupleSetWithBoth(pStar, gs    ) ) { return true; }
+    if( beta.containsTupleSetWithBoth(p,     gsPlus) ) { return true; }
+    if( beta.containsTupleSetWithBoth(pPlus, gsPlus) ) { return true; }
+    if( beta.containsTupleSetWithBoth(pStar, gsPlus) ) { return true; }
+    if( beta.containsTupleSetWithBoth(p,     gsStar) ) { return true; }
+    if( beta.containsTupleSetWithBoth(pPlus, gsStar) ) { return true; }
+    if( beta.containsTupleSetWithBoth(pStar, gsStar) ) { return true; }
 
     // check for other nodes
     for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 
 
     // check for other nodes
     for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 
-      // the other nodes of an allocation site are single, no stars
+      // the other nodes of an allocation site are single, no plus
       TokenTuple gi = new TokenTuple(as.getIthOldest(i),
                                      false,
                                      TokenTuple.ARITY_ONE).makeCanonical();
 
       TokenTuple gi = new TokenTuple(as.getIthOldest(i),
                                      false,
                                      TokenTuple.ARITY_ONE).makeCanonical();
 
-      if( beta.containsTupleSetWithBoth(p,     gi) ) {
-       return true;
-      }
-      if( beta.containsTupleSetWithBoth(pStar, gi) ) {
-       return true;
-      }
+      TokenTuple giStar = new TokenTuple(as.getIthOldest(i),
+                                        false,
+                                        TokenTuple.ARITY_ZEROORMORE).makeCanonical();
+
+      if( beta.containsTupleSetWithBoth(p,     gi    ) ) { return true; }
+      if( beta.containsTupleSetWithBoth(pPlus, gi    ) ) { return true; }
+      if( beta.containsTupleSetWithBoth(pStar, gi    ) ) { return true; }
+      if( beta.containsTupleSetWithBoth(p,     giStar) ) { return true; }
+      if( beta.containsTupleSetWithBoth(pPlus, giStar) ) { return true; }
+      if( beta.containsTupleSetWithBoth(pStar, giStar) ) { return true; }
     }
 
     return false;
     }
 
     return false;
@@ -2389,9 +2404,13 @@ public class OwnershipGraph {
                                     true,
                                     TokenTuple.ARITY_ONE).makeCanonical();
 
                                     true,
                                     TokenTuple.ARITY_ONE).makeCanonical();
 
+    TokenTuple gsPlus1 = new TokenTuple(as1.getSummary(),
+                                        true,
+                                        TokenTuple.ARITY_ONEORMORE).makeCanonical();
+
     TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
                                         true,
     TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
                                         true,
-                                        TokenTuple.ARITY_MANY).makeCanonical();
+                                        TokenTuple.ARITY_ZEROORMORE).makeCanonical();
 
     // get summary node's alpha
     Integer idSum1 = as1.getSummary();
 
     // get summary node's alpha
     Integer idSum1 = as1.getSummary();
@@ -2407,9 +2426,13 @@ public class OwnershipGraph {
                                     true,
                                     TokenTuple.ARITY_ONE).makeCanonical();
 
                                     true,
                                     TokenTuple.ARITY_ONE).makeCanonical();
 
+    TokenTuple gsPlus2 = new TokenTuple(as2.getSummary(),
+                                        true,
+                                        TokenTuple.ARITY_ONEORMORE).makeCanonical();
+
     TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
                                         true,
     TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
                                         true,
-                                        TokenTuple.ARITY_MANY).makeCanonical();
+                                        TokenTuple.ARITY_ZEROORMORE).makeCanonical();
 
     // get summary node's alpha
     Integer idSum2 = as2.getSummary();
 
     // get summary node's alpha
     Integer idSum2 = as2.getSummary();
@@ -2420,21 +2443,15 @@ public class OwnershipGraph {
     assert alphaSum2 != null;
 
     // does either one report reachability from the other tokens?
     assert alphaSum2 != null;
 
     // does either one report reachability from the other tokens?
-    if( alphaSum1.containsTuple(gsStar2) ) {
-      return true;
-    }
-    if( alphaSum2.containsTuple(gsStar1) ) {
-      return true;
-    }
+    if( alphaSum1.containsTuple(gsPlus2) ) { return true; }
+    if( alphaSum1.containsTuple(gsStar2) ) { return true; }
+    if( alphaSum2.containsTuple(gsPlus1) ) { return true; }
+    if( alphaSum2.containsTuple(gsStar1) ) { return true; }
 
 
-    // only check non-star token if they are different sites
+    // only check ONE token if they are different sites
     if( as1 != as2 ) {
     if( as1 != as2 ) {
-      if( alphaSum1.containsTuple(gs2) ) {
-       return true;
-      }
-      if( alphaSum2.containsTuple(gs1) ) {
-       return true;
-      }
+      if( alphaSum1.containsTuple(gs2) ) { return true; }
+      if( alphaSum2.containsTuple(gs1) ) { return true; }
     }
 
 
     }
 
 
@@ -2452,15 +2469,15 @@ public class OwnershipGraph {
                                       false,
                                       TokenTuple.ARITY_ONE).makeCanonical();
 
                                       false,
                                       TokenTuple.ARITY_ONE).makeCanonical();
 
-      if( alphaSum2.containsTuple(gi1) ) {
-       return true;
-      }
-      if( alphaI1.containsTuple(gs2) ) {
-       return true;
-      }
-      if( alphaI1.containsTuple(gsStar2) ) {
-       return true;
-      }
+      TokenTuple giStar1 = new TokenTuple(as1.getIthOldest(i),
+                                         false,
+                                         TokenTuple.ARITY_ZEROORMORE).makeCanonical();
+
+      if( alphaSum2.containsTuple(gi1    ) ) { return true; }
+      if( alphaSum2.containsTuple(giStar1) ) { return true; }
+      if(   alphaI1.containsTuple(gs2    ) ) { return true; }
+      if(   alphaI1.containsTuple(gsPlus2) ) { return true; }
+      if(   alphaI1.containsTuple(gsStar2) ) { return true; }
     }
 
     // check sum1 against alloc2 nodes
     }
 
     // check sum1 against alloc2 nodes
@@ -2476,21 +2493,21 @@ public class OwnershipGraph {
                                       false,
                                       TokenTuple.ARITY_ONE).makeCanonical();
 
                                       false,
                                       TokenTuple.ARITY_ONE).makeCanonical();
 
-      if( alphaSum1.containsTuple(gi2) ) {
-       return true;
-      }
-      if( alphaI2.containsTuple(gs1) ) {
-       return true;
-      }
-      if( alphaI2.containsTuple(gsStar1) ) {
-       return true;
-      }
+      TokenTuple giStar2 = new TokenTuple(as2.getIthOldest(i),
+                                         false,
+                                         TokenTuple.ARITY_ZEROORMORE).makeCanonical();
+
+      if( alphaSum1.containsTuple(gi2    ) ) { return true; }
+      if( alphaSum1.containsTuple(giStar2) ) { return true; }
+      if(   alphaI2.containsTuple(gs1    ) ) { return true; }
+      if(   alphaI2.containsTuple(gsPlus1) ) { return true; }
+      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 ) {
        Integer idI1 = as1.getIthOldest(j);
 
 
       // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
       for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
        Integer idI1 = as1.getIthOldest(j);
 
-       // if these are the same site, don't look for the same token, no alias
+       // if these are the same site, don't look for the same token, no alias.
        // different tokens of the same site could alias together though
        if( idI1 == idI2 ) {
          continue;
        // different tokens of the same site could alias together though
        if( idI1 == idI2 ) {
          continue;
@@ -2501,12 +2518,15 @@ public class OwnershipGraph {
        TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
                                        false,
                                        TokenTuple.ARITY_ONE).makeCanonical();
        TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
                                        false,
                                        TokenTuple.ARITY_ONE).makeCanonical();
-       if( alphaI2.containsTuple(gi1) ) {
-         return true;
-       }
-       if( alphaI1.containsTuple(gi2) ) {
-         return true;
-       }
+
+       TokenTuple giStar1 = new TokenTuple(as1.getIthOldest(j),
+                                           false,
+                                           TokenTuple.ARITY_ZEROORMORE).makeCanonical();
+
+       if( alphaI2.containsTuple(gi1    ) ) { return true; }
+       if( alphaI2.containsTuple(giStar1) ) { return true; }
+       if( alphaI1.containsTuple(gi2    ) ) { return true; }
+       if( alphaI1.containsTuple(giStar2) ) { return true; }
       }
     }
 
       }
     }
 
index 8e6576d12665d94d0c2378d64d498255f8ee039b..caedeadedb1bd21d4c4b4e24415bbc2eb05eaeb7 100644 (file)
@@ -82,21 +82,6 @@ public class ReachabilitySet extends Canonical {
     return false;
   }
 
     return false;
   }
 
-  public ReachabilitySet increaseArity(Integer token) {
-    assert token != null;
-
-    HashSet<TokenTupleSet> possibleReachabilitiesNew = new HashSet<TokenTupleSet>();
-
-    Iterator itr = iterator();
-    while( itr.hasNext() ) {
-      TokenTupleSet tts = (TokenTupleSet) itr.next();
-      possibleReachabilitiesNew.add(tts.increaseArity(token) );
-    }
-
-    return new ReachabilitySet(possibleReachabilitiesNew).makeCanonical();
-  }
-
-
   public ReachabilitySet union(ReachabilitySet rsIn) {
     assert rsIn != null;
 
   public ReachabilitySet union(ReachabilitySet rsIn) {
     assert rsIn != null;
 
@@ -154,28 +139,28 @@ public class ReachabilitySet extends Canonical {
 
        Iterator itrRelement = r.iterator();
        while( itrRelement.hasNext() ) {
 
        Iterator itrRelement = r.iterator();
        while( itrRelement.hasNext() ) {
-         TokenTuple e = (TokenTuple) itrRelement.next();
+         TokenTuple ttR = (TokenTuple) itrRelement.next();
+         TokenTuple ttO = o.containsToken( ttR.getToken() );
 
 
-         if( o.containsToken(e.getToken() ) ) {
-           theUnion = theUnion.union(new TokenTupleSet(e.increaseArity() ) ).makeCanonical();
+         if( ttO != null ) {
+           theUnion = theUnion.union( new TokenTupleSet( ttR.unionArity(ttO) ) ).makeCanonical();
          } else {
          } else {
-           theUnion = theUnion.union(new TokenTupleSet(e) ).makeCanonical();
+           theUnion = theUnion.union( new TokenTupleSet( ttR                 ) ).makeCanonical();
          }
        }
 
        Iterator itrOelement = o.iterator();
        while( itrOelement.hasNext() ) {
          }
        }
 
        Iterator itrOelement = o.iterator();
        while( itrOelement.hasNext() ) {
-         TokenTuple e = (TokenTuple) itrOelement.next();
+         TokenTuple ttO = (TokenTuple) itrOelement.next();
+         TokenTuple ttR = theUnion.containsToken( ttO.getToken() );
 
 
-         if( !theUnion.containsToken(e.getToken() ) ) {
-           theUnion = theUnion.union(new TokenTupleSet(e) ).makeCanonical();
+         if( ttR == null ) {
+           theUnion = theUnion.union( new TokenTupleSet(ttO) ).makeCanonical();
          }
        }
          }
        }
-
+       
        if( !theUnion.isEmpty() ) {
        if( !theUnion.isEmpty() ) {
-         ctsOut = ctsOut.union(
-           new ChangeTupleSet(new ChangeTuple(o, theUnion) )
-           );
+         ctsOut = ctsOut.union( new ChangeTupleSet( new ChangeTuple(o, theUnion) ) );
        }
       }
     }
        }
       }
     }
@@ -263,11 +248,22 @@ public class ReachabilitySet extends Canonical {
 
     int numDimensions = this.possibleReachabilities.size();
 
 
     int numDimensions = this.possibleReachabilities.size();
 
-    if( numDimensions > 10 ) {
-      System.out.println( "    exhaustiveArityCombinations numDimensions = "+numDimensions );
-      System.out.println( this );
+    if( numDimensions > 6 ) {
+      // for problems that are too big, punt and use less
+      // precise arity for reachability information
+      TokenTupleSet ttsImprecise = new TokenTupleSet().makeCanonical();
+
+      Iterator<TokenTupleSet> itrThis = this.iterator();
+      while( itrThis.hasNext() ) {
+       TokenTupleSet ttsUnit = itrThis.next();
+       ttsImprecise = ttsImprecise.unionUpArity( ttsUnit.makeArityZeroOrMore() );
+      }
+
+      rsOut = rsOut.union( ttsImprecise );
+      return rsOut;
     }
 
     }
 
+
     // add an extra digit to detect termination
     int[] digits = new int[numDimensions+1];
 
     // add an extra digit to detect termination
     int[] digits = new int[numDimensions+1];
 
@@ -283,7 +279,7 @@ public class ReachabilitySet extends Canonical {
     while( digits[numDimensions] == minArity ) {
 
       // spit out a "coordinate" made from these digits
     while( digits[numDimensions] == minArity ) {
 
       // spit out a "coordinate" made from these digits
-      TokenTupleSet ttsCoordinate = new TokenTupleSet();
+      TokenTupleSet ttsCoordinate = new TokenTupleSet().makeCanonical();
       Iterator<TokenTupleSet> ttsItr = this.iterator();
       for( int i = 0; i < numDimensions; ++i ) {
        assert ttsItr.hasNext();
       Iterator<TokenTupleSet> ttsItr = this.iterator();
       for( int i = 0; i < numDimensions; ++i ) {
        assert ttsItr.hasNext();
@@ -298,19 +294,6 @@ public class ReachabilitySet extends Canonical {
       for( int i = 0; i < numDimensions+1; ++i ) {
        digits[i]++;
 
       for( int i = 0; i < numDimensions+1; ++i ) {
        digits[i]++;
 
-
-       if( i == 11 ) {
-         System.out.print( "x" );
-       }
-
-       if( i == 15 ) {
-         System.out.print( "@" );
-       }
-
-       if( i == 17 ) {
-         System.out.print( "#" );
-       }
-
        if( digits[i] > maxArity ) {
          // this axis reached its max, so roll it back to min and increment next higher digit
          digits[i] = minArity;
        if( digits[i] > maxArity ) {
          // this axis reached its max, so roll it back to min and increment next higher digit
          digits[i] = minArity;
@@ -322,10 +305,6 @@ public class ReachabilitySet extends Canonical {
       }
     }
 
       }
     }
 
-    if( numDimensions > 10 ) {
-      System.out.println( "" );
-    }
-
     return rsOut.makeCanonical();
   }
 
     return rsOut.makeCanonical();
   }
 
index b48d5bd80f68051201338699302a5678b1711f1b..30c07379e9df7fe2a9a6e7a4fd4313e43905d757 100644 (file)
@@ -14,34 +14,30 @@ import java.io.*;
 public class TokenTuple extends Canonical {
 
   private Integer token;
 public class TokenTuple extends Canonical {
 
   private Integer token;
-  private boolean isNewSummary;
+  private boolean isMultiObject;
 
 
-
-  // only summary tokens should have ARITY_MANY?
-  // acutally, multiple-object regions can be arity-many
-  // so isNewSummary actually means "multi-object" in
-  // this class.  CHANGE THIS SOMETIME!
-  public static final int ARITY_ONE  = 1;
-  public static final int ARITY_MANY = 2;
+  public static final int ARITY_ZEROORMORE = 0;
+  public static final int ARITY_ONE        = 1;
+  public static final int ARITY_ONEORMORE  = 2;
   private int arity;
 
 
   public TokenTuple(HeapRegionNode hrn) {
     assert hrn != null;
 
   private int arity;
 
 
   public TokenTuple(HeapRegionNode hrn) {
     assert hrn != null;
 
-    token        = hrn.getID();
-    isNewSummary = hrn.isNewSummary();
-    arity        = ARITY_ONE;
+    token         = hrn.getID();
+    isMultiObject = !hrn.isSingleObject();
+    arity         = ARITY_ONE;
   }
 
   public TokenTuple(Integer token,
   }
 
   public TokenTuple(Integer token,
-                    boolean isNewSummary,
+                    boolean isMultiObject,
                     int arity) {
     assert token != null;
 
                     int arity) {
     assert token != null;
 
-    this.token        = token;
-    this.isNewSummary = isNewSummary;
-    this.arity        = arity;
+    this.token         = token;
+    this.isMultiObject = isMultiObject;
+    this.arity         = arity;
   }
 
 
   }
 
 
@@ -53,18 +49,39 @@ public class TokenTuple extends Canonical {
   public Integer getToken() {
     return token;
   }
   public Integer getToken() {
     return token;
   }
-  public int     getArity() {
+
+  public boolean isMultiObject() {
+    return isMultiObject;
+  }
+
+  public int getArity() {
     return arity;
   }
 
 
     return arity;
   }
 
 
-  public TokenTuple increaseArity() {
-    if( isNewSummary ) {
-      return (TokenTuple) Canonical.makeCanonical(
-               new TokenTuple(token, isNewSummary, ARITY_MANY)
-               );
+  public TokenTuple unionArity( TokenTuple tt ) {
+    assert tt            != null;
+    assert token         == tt.token;
+    assert isMultiObject == tt.isMultiObject;
+
+    if( isMultiObject ) {
+      // for multiple objects only zero-or-mores combined are still zero-or-more
+      // when two tokens are present (absence of a token is arity=zero and is
+      // handled outside of this method)
+      if( arity == ARITY_ZEROORMORE && tt.arity == ARITY_ZEROORMORE ) {
+       return new TokenTuple( token, true, ARITY_ZEROORMORE ).makeCanonical();
+      } else {
+       return new TokenTuple( token, true, ARITY_ONEORMORE ).makeCanonical();
+      }
+
+    } else {
+      // a single object region's token can only have ZEROORMORE or ONE
+      if( arity == ARITY_ZEROORMORE && tt.arity == ARITY_ZEROORMORE ) {
+       return new TokenTuple( token, false, ARITY_ZEROORMORE ).makeCanonical();
+      } else {
+       return new TokenTuple( token, false, ARITY_ONE ).makeCanonical();
+      }
     }
     }
-    return this;
   }
 
 
   }
 
 
@@ -72,7 +89,7 @@ public class TokenTuple extends Canonical {
     assert tokenToChangeTo != null;
 
     return new TokenTuple(tokenToChangeTo,
     assert tokenToChangeTo != null;
 
     return new TokenTuple(tokenToChangeTo,
-                          isNewSummary,
+                          isMultiObject,
                           arity).makeCanonical();
   }
 
                           arity).makeCanonical();
   }
 
@@ -89,7 +106,7 @@ public class TokenTuple extends Canonical {
     TokenTuple tt = (TokenTuple) o;
 
     return token.equals(tt.getToken() ) &&
     TokenTuple tt = (TokenTuple) o;
 
     return token.equals(tt.getToken() ) &&
-           arity ==      tt.getArity();
+           arity ==     tt.getArity();
   }
 
   public int hashCode() {
   }
 
   public int hashCode() {
@@ -100,12 +117,14 @@ public class TokenTuple extends Canonical {
   public String toString() {
     String s = token.toString();
 
   public String toString() {
     String s = token.toString();
 
-    if( isNewSummary ) {
-      s += "S";
+    if( isMultiObject ) {
+      s += "M";
     }
 
     }
 
-    if( arity == ARITY_MANY ) {
+    if( arity == ARITY_ZEROORMORE ) {
       s += "*";
       s += "*";
+    } else if( arity == ARITY_ONEORMORE ) {
+      s += "+";
     }
 
     return s;
     }
 
     return s;
index d190bed23f1723d56df81f1d5c40b83e856ba7f3..af72503a559faf7df83636b3bc7136866df515d2 100644 (file)
@@ -58,33 +58,37 @@ public class TokenTupleSet extends Canonical {
     return ttsOut.makeCanonical();
   }
 
     return ttsOut.makeCanonical();
   }
 
+
   public TokenTupleSet unionUpArity(TokenTupleSet ttsIn) {
     assert ttsIn != null;
     TokenTupleSet ttsOut = new TokenTupleSet();
 
     Iterator<TokenTuple> ttItr = this.iterator();
     while( ttItr.hasNext() ) {
   public TokenTupleSet unionUpArity(TokenTupleSet ttsIn) {
     assert ttsIn != null;
     TokenTupleSet ttsOut = new TokenTupleSet();
 
     Iterator<TokenTuple> ttItr = this.iterator();
     while( ttItr.hasNext() ) {
-      TokenTuple tt = ttItr.next();
+      TokenTuple ttThis = ttItr.next();
+      TokenTuple ttIn   = ttsIn.containsToken( ttThis.getToken() );
 
 
-      if( ttsIn.containsToken(tt.getToken() ) ) {
-       ttsOut.tokenTuples.add(tt.increaseArity());
+      if( ttIn != null ) {
+       ttsOut.tokenTuples.add( ttThis.unionArity( ttIn ) );
       } else {
       } else {
-       ttsOut.tokenTuples.add(tt);
+       ttsOut.tokenTuples.add( ttThis );
       }
     }
 
     ttItr = ttsIn.iterator();
     while( ttItr.hasNext() ) {
       }
     }
 
     ttItr = ttsIn.iterator();
     while( ttItr.hasNext() ) {
-      TokenTuple tt = ttItr.next();
+      TokenTuple ttIn   = ttItr.next();
+      TokenTuple ttThis = ttsOut.containsToken( ttIn.getToken() );
 
 
-      if( !ttsOut.containsToken(tt.getToken()) ) {
-       ttsOut.tokenTuples.add(tt);
+      if( ttThis == null ) {
+       ttsOut.tokenTuples.add( ttIn );
       }
     }
 
     return ttsOut.makeCanonical();
   }
 
       }
     }
 
     return ttsOut.makeCanonical();
   }
 
+
   public TokenTupleSet add(TokenTuple tt) {
     assert tt != null;
     TokenTupleSet ttsOut = new TokenTupleSet(tt);
   public TokenTupleSet add(TokenTuple tt) {
     assert tt != null;
     TokenTupleSet ttsOut = new TokenTupleSet(tt);
@@ -92,23 +96,6 @@ public class TokenTupleSet extends Canonical {
   }
 
 
   }
 
 
-  // this should only be done with a multiple-object heap region's token!
-  public TokenTupleSet increaseArity(Integer token) {
-    assert token != null;
-    TokenTupleSet ttsOut = new TokenTupleSet(this);
-    TokenTuple tt
-    = new TokenTuple(token, true, TokenTuple.ARITY_ONE).makeCanonical();
-    if( ttsOut.tokenTuples.contains(tt) ) {
-      ttsOut.tokenTuples.remove(tt);
-      ttsOut.tokenTuples.add(
-        new TokenTuple(token, true, TokenTuple.ARITY_MANY).makeCanonical()
-        );
-    }
-
-    return ttsOut.makeCanonical();
-  }
-
-
   public boolean equals(Object o) {
     if( o == null ) {
       return false;
   public boolean equals(Object o) {
     if( o == null ) {
       return false;
@@ -128,17 +115,17 @@ public class TokenTupleSet extends Canonical {
 
 
   // this should be a hash table so we can do this by key
 
 
   // this should be a hash table so we can do this by key
-  public boolean containsToken(Integer token) {
+  public TokenTuple containsToken(Integer token) {
     assert token != null;
 
     Iterator itr = tokenTuples.iterator();
     while( itr.hasNext() ) {
       TokenTuple tt = (TokenTuple) itr.next();
       if( token.equals(tt.getToken() ) ) {
     assert token != null;
 
     Iterator itr = tokenTuples.iterator();
     while( itr.hasNext() ) {
       TokenTuple tt = (TokenTuple) itr.next();
       if( token.equals(tt.getToken() ) ) {
-       return true;
+       return tt;
       }
     }
       }
     }
-    return false;
+    return null;
   }
 
 
   }
 
 
@@ -148,7 +135,7 @@ public class TokenTupleSet extends Canonical {
     TokenTupleSet ttsOut = new TokenTupleSet();
 
     TokenTuple ttSummary = null;
     TokenTupleSet ttsOut = new TokenTupleSet();
 
     TokenTuple ttSummary = null;
-    boolean foundOldest  = false;
+    TokenTuple ttOldest  = null;
 
     Iterator itrT = this.iterator();
     while( itrT.hasNext() ) {
 
     Iterator itrT = this.iterator();
     while( itrT.hasNext() ) {
@@ -170,7 +157,7 @@ public class TokenTupleSet extends Canonical {
       } else if( age == AllocationSite.AGE_oldest ) {
        // found an oldest token, again just remember
        // for later
       } else if( age == AllocationSite.AGE_oldest ) {
        // found an oldest token, again just remember
        // for later
-       foundOldest = true;
+       ttOldest = tt;
 
       } else {
        assert age == AllocationSite.AGE_in_I;
 
       } else {
        assert age == AllocationSite.AGE_in_I;
@@ -192,18 +179,25 @@ public class TokenTupleSet extends Canonical {
     // 2. we found an oldest tuple, no summary
     //    Make a new, arity-one summary tuple
     // 3. we found both a summary and an oldest
     // 2. we found an oldest tuple, no summary
     //    Make a new, arity-one summary tuple
     // 3. we found both a summary and an oldest
-    //    Merge them by increasing arity of summary
+    //    Merge them by arity
     // 4. (not handled) we found neither, do nothing
     // 4. (not handled) we found neither, do nothing
-    if       ( ttSummary != null && !foundOldest ) {
+    if       ( ttSummary != null && ttOldest == null ) {
       ttsOut.tokenTuples.add(ttSummary);
 
       ttsOut.tokenTuples.add(ttSummary);
 
-    } else if( ttSummary == null &&  foundOldest ) {
+    } else if( ttSummary == null && ttOldest != null ) {
       ttsOut.tokenTuples.add(new TokenTuple(as.getSummary(),
                                             true,
       ttsOut.tokenTuples.add(new TokenTuple(as.getSummary(),
                                             true,
-                                            TokenTuple.ARITY_ONE).makeCanonical() );
-
-    } else if( ttSummary != null &&  foundOldest ) {
-      ttsOut.tokenTuples.add(ttSummary.increaseArity() );
+                                            ttOldest.getArity() 
+                                          ).makeCanonical() 
+                            );
+
+    } else if( ttSummary != null && ttOldest != null ) {
+      ttsOut.tokenTuples.add(ttSummary.unionArity(new TokenTuple(as.getSummary(),
+                                                                true,
+                                                                ttOldest.getArity() 
+                                                                ).makeCanonical()
+                                                 )
+                            );
     }
 
     return ttsOut.makeCanonical();
     }
 
     return ttsOut.makeCanonical();
@@ -215,8 +209,8 @@ public class TokenTupleSet extends Canonical {
 
     TokenTupleSet ttsOut = new TokenTupleSet();
 
 
     TokenTupleSet ttsOut = new TokenTupleSet();
 
-    TokenTuple ttSummary = null;
-    boolean foundShadowSummary = false;
+    TokenTuple ttSummary       = null;
+    TokenTuple ttShadowSummary = null;
 
     Iterator itrT = this.iterator();
     while( itrT.hasNext() ) {
 
     Iterator itrT = this.iterator();
     while( itrT.hasNext() ) {
@@ -236,7 +230,7 @@ public class TokenTupleSet extends Canonical {
       } else if( shadowAge == AllocationSite.SHADOWAGE_summary ) {
        // found the shadow summary token, again just remember
        // for later
       } else if( shadowAge == AllocationSite.SHADOWAGE_summary ) {
        // found the shadow summary token, again just remember
        // for later
-       foundShadowSummary = true;
+       ttShadowSummary = tt;
 
       } else if( shadowAge == AllocationSite.SHADOWAGE_oldest ) {
        Integer tokenToChangeTo = as.getOldest();
 
       } else if( shadowAge == AllocationSite.SHADOWAGE_oldest ) {
        Integer tokenToChangeTo = as.getOldest();
@@ -255,17 +249,23 @@ public class TokenTupleSet extends Canonical {
       }
     }
 
       }
     }
 
-    if       ( ttSummary != null && !foundShadowSummary ) {
-      ttsOut.tokenTuples.add(ttSummary);
-
-    } else if( ttSummary == null &&  foundShadowSummary ) {
-      ttSummary = new TokenTuple(as.getSummary(),
-                                 true,
-                                 TokenTuple.ARITY_ONE).makeCanonical();
+    if       ( ttSummary != null && ttShadowSummary == null ) {
       ttsOut.tokenTuples.add(ttSummary);
 
       ttsOut.tokenTuples.add(ttSummary);
 
-    } else if( ttSummary != null &&  foundShadowSummary ) {
-      ttsOut.tokenTuples.add(ttSummary.increaseArity() );
+    } else if( ttSummary == null && ttShadowSummary != null ) {
+      ttsOut.tokenTuples.add( new TokenTuple(as.getSummary(),
+                                            true,
+                                            ttShadowSummary.getArity()
+                                            ).makeCanonical()
+                             );
+
+    } else if( ttSummary != null && ttShadowSummary != null ) {
+      ttsOut.tokenTuples.add(ttSummary.unionArity( new TokenTuple(as.getSummary(),
+                                                                 true,
+                                                                 ttShadowSummary.getArity()
+                                                                 ).makeCanonical()
+                                                  )
+                            );
     }
 
     return ttsOut.makeCanonical();
     }
 
     return ttsOut.makeCanonical();
@@ -275,7 +275,7 @@ public class TokenTupleSet extends Canonical {
   public TokenTupleSet toShadowTokens(AllocationSite as) {
     assert as != null;
 
   public TokenTupleSet toShadowTokens(AllocationSite as) {
     assert as != null;
 
-    TokenTupleSet ttsOut = new TokenTupleSet();
+    TokenTupleSet ttsOut = new TokenTupleSet().makeCanonical();
 
     Iterator itrT = this.iterator();
     while( itrT.hasNext() ) {
 
     Iterator itrT = this.iterator();
     while( itrT.hasNext() ) {
@@ -346,6 +346,24 @@ public class TokenTupleSet extends Canonical {
   }
 
 
   }
 
 
+  public TokenTupleSet makeArityZeroOrMore() {
+    TokenTupleSet ttsOut = new TokenTupleSet().makeCanonical();
+
+    Iterator<TokenTuple> itrThis = this.iterator();
+    while( itrThis.hasNext() ) {
+      TokenTuple tt = itrThis.next();
+
+      ttsOut.tokenTuples.add( new TokenTuple( tt.getToken(),
+                                            tt.isMultiObject(),
+                                            TokenTuple.ARITY_ZEROORMORE 
+                                           ).makeCanonical()
+                             );
+    }
+
+    return ttsOut.makeCanonical();
+  }
+
+
   public String toString() {
     return tokenTuples.toString();
   }
   public String toString() {
     return tokenTuples.toString();
   }
index f24420c131bec7399ca8c2ea70767ca7fd6bd465..1c449c9d63b9d264a3f18100e20a8821700cd578 100755 (executable)
@@ -247,7 +247,7 @@ else
 #if ! java -Xms5m -Xmx100m $JAVAFORWARDOPTS -classpath $ROBUSTROOT/../cup/:$ROBUSTROOT Main.Main -classlibrary \
 if ! $NOJAVA
 then
 #if ! java -Xms5m -Xmx100m $JAVAFORWARDOPTS -classpath $ROBUSTROOT/../cup/:$ROBUSTROOT Main.Main -classlibrary \
 if ! $NOJAVA
 then
-if ! java -Xms50m -Xmx200m $JAVAFORWARDOPTS -classpath $ROBUSTROOT/../cup/:$ROBUSTROOT Main.Main -classlibrary \
+if ! java -Xms50m -Xmx600m $JAVAFORWARDOPTS -classpath $ROBUSTROOT/../cup/:$ROBUSTROOT Main.Main -classlibrary \
 $ROBUSTROOT/ClassLibrary/ -dir $BUILDDIR -precise \
 $JAVAOPTS $SRCFILES
 then exit $?
 $ROBUSTROOT/ClassLibrary/ -dir $BUILDDIR -precise \
 $JAVAOPTS $SRCFILES
 then exit $?