Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java

   1 package Analysis.OwnershipAnalysis;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.*;
   7
   8
   9 public class TokenTupleSet extends Canonical {
  10
  11   private HashSet<TokenTuple> tokenTuples;
  12
  13
  14   public TokenTupleSet() {
  15     tokenTuples = new HashSet<TokenTuple>();
  16   }
  17
  18   public TokenTupleSet(TokenTuple tt) {
  19     this();
  20     assert tt != null;
  21     tokenTuples.add(tt);
  22   }
  23
  24   public TokenTupleSet(TokenTupleSet tts) {
  25     assert tts != null;
  26     // okay to clone, TokenTuple and TokenTupleSet should be canonical
  27     tokenTuples = (HashSet<TokenTuple>)tts.tokenTuples.clone();
  28   }
  29
  30
  31   public TokenTupleSet makeCanonical() {
  32     return (TokenTupleSet) Canonical.makeCanonical(this);
  33   }
  34
  35   public Iterator iterator() {
  36     return tokenTuples.iterator();
  37   }
  38
  39   public boolean isEmpty() {
  40     return tokenTuples.isEmpty();
  41   }
  42
  43   public boolean isSubset(TokenTupleSet ttsIn) {
  44     assert ttsIn != null;
  45     return ttsIn.tokenTuples.containsAll(this.tokenTuples);
  46   }
  47
  48   public boolean containsTuple(TokenTuple tt) {
  49     assert tt != null;
  50     return tokenTuples.contains(tt);
  51   }
  52
  53
  54   public TokenTupleSet union(TokenTupleSet ttsIn) {
  55     assert ttsIn != null;
  56     TokenTupleSet ttsOut = new TokenTupleSet(this);
  57     ttsOut.tokenTuples.addAll(ttsIn.tokenTuples);
  58     return ttsOut.makeCanonical();
  59   }
  60
  61   public TokenTupleSet unionUpArity(TokenTupleSet ttsIn) {
  62     assert ttsIn != null;
  63     TokenTupleSet ttsOut = new TokenTupleSet();
  64
  65     Iterator<TokenTuple> ttItr = this.iterator();
  66     while( ttItr.hasNext() ) {
  67       TokenTuple tt = ttItr.next();
  68
  69       if( ttsIn.containsToken(tt.getToken() ) ) {
  70         ttsOut.tokenTuples.add(tt.increaseArity());
  71       } else {
  72         ttsOut.tokenTuples.add(tt);
  73       }
  74     }
  75
  76     ttItr = ttsIn.iterator();
  77     while( ttItr.hasNext() ) {
  78       TokenTuple tt = ttItr.next();
  79
  80       if( !ttsOut.containsToken(tt.getToken()) ) {
  81         ttsOut.tokenTuples.add(tt);
  82       }
  83     }
  84
  85     return ttsOut.makeCanonical();
  86   }
  87
  88   public TokenTupleSet add(TokenTuple tt) {
  89     assert tt != null;
  90     TokenTupleSet ttsOut = new TokenTupleSet(tt);
  91     return ttsOut.union(this);
  92   }
  93
  94
  95   // this should only be done with a multiple-object heap region's token!
  96   public TokenTupleSet increaseArity(Integer token) {
  97     assert token != null;
  98     TokenTupleSet ttsOut = new TokenTupleSet(this);
  99     TokenTuple tt
 100     = new TokenTuple(token, true, TokenTuple.ARITY_ONE).makeCanonical();
 101     if( ttsOut.tokenTuples.contains(tt) ) {
 102       ttsOut.tokenTuples.remove(tt);
 103       ttsOut.tokenTuples.add(
 104         new TokenTuple(token, true, TokenTuple.ARITY_MANY).makeCanonical()
 105         );
 106     }
 107
 108     return ttsOut.makeCanonical();
 109   }
 110
 111
 112   public boolean equals(Object o) {
 113     if( o == null ) {
 114       return false;
 115     }
 116
 117     if( !(o instanceof TokenTupleSet) ) {
 118       return false;
 119     }
 120
 121     TokenTupleSet tts = (TokenTupleSet) o;
 122     return tokenTuples.equals(tts.tokenTuples);
 123   }
 124
 125   public int hashCode() {
 126     return tokenTuples.hashCode();
 127   }
 128
 129
 130   // this should be a hash table so we can do this by key
 131   public boolean containsToken(Integer token) {
 132     assert token != null;
 133
 134     Iterator itr = tokenTuples.iterator();
 135     while( itr.hasNext() ) {
 136       TokenTuple tt = (TokenTuple) itr.next();
 137       if( token.equals(tt.getToken() ) ) {
 138         return true;
 139       }
 140     }
 141     return false;
 142   }
 143
 144
 145   public TokenTupleSet ageTokens(AllocationSite as) {
 146     assert as != null;
 147
 148     TokenTupleSet ttsOut = new TokenTupleSet();
 149
 150     TokenTuple ttSummary = null;
 151     boolean foundOldest  = false;
 152
 153     Iterator itrT = this.iterator();
 154     while( itrT.hasNext() ) {
 155       TokenTuple tt = (TokenTuple) itrT.next();
 156
 157       Integer token = tt.getToken();
 158       int age = as.getAgeCategory(token);
 159
 160       // tokens not associated with
 161       // the site should be left alone
 162       if( age == AllocationSite.AGE_notInThisSite ) {
 163         ttsOut.tokenTuples.add(tt);
 164
 165       } else if( age == AllocationSite.AGE_summary ) {
 166         // remember the summary tuple, but don't add it
 167         // we may combine it with the oldest tuple
 168         ttSummary = tt;
 169
 170       } else if( age == AllocationSite.AGE_oldest ) {
 171         // found an oldest token, again just remember
 172         // for later
 173         foundOldest = true;
 174
 175       } else {
 176         assert age == AllocationSite.AGE_in_I;
 177
 178         Integer I = as.getAge(token);
 179         assert I != null;
 180
 181         // otherwise, we change this token to the
 182         // next older token
 183         Integer tokenToChangeTo = as.getIthOldest(I + 1);
 184         TokenTuple ttAged       = tt.changeTokenTo(tokenToChangeTo);
 185         ttsOut.tokenTuples.add(ttAged);
 186       }
 187     }
 188
 189     // there are four cases to consider here
 190     // 1. we found a summary tuple and no oldest tuple
 191     //    Here we just pass the summary unchanged
 192     // 2. we found an oldest tuple, no summary
 193     //    Make a new, arity-one summary tuple
 194     // 3. we found both a summary and an oldest
 195     //    Merge them by increasing arity of summary
 196     // 4. (not handled) we found neither, do nothing
 197     if       ( ttSummary != null && !foundOldest ) {
 198       ttsOut.tokenTuples.add(ttSummary);
 199
 200     } else if( ttSummary == null &&  foundOldest ) {
 201       ttsOut.tokenTuples.add(new TokenTuple(as.getSummary(),
 202                                             true,
 203                                             TokenTuple.ARITY_ONE).makeCanonical() );
 204
 205     } else if( ttSummary != null &&  foundOldest ) {
 206       ttsOut.tokenTuples.add(ttSummary.increaseArity() );
 207     }
 208
 209     return ttsOut.makeCanonical();
 210   }
 211
 212
 213   public TokenTupleSet unshadowTokens(AllocationSite as) {
 214     assert as != null;
 215
 216     TokenTupleSet ttsOut = new TokenTupleSet();
 217
 218     TokenTuple ttSummary = null;
 219     boolean foundShadowSummary = false;
 220
 221     Iterator itrT = this.iterator();
 222     while( itrT.hasNext() ) {
 223       TokenTuple tt = (TokenTuple) itrT.next();
 224
 225       Integer token = tt.getToken();
 226       int shadowAge = as.getShadowAgeCategory(token);
 227
 228       if( shadowAge == AllocationSite.AGE_summary ) {
 229         // remember the summary tuple, but don't add it
 230         // we may combine it with the oldest tuple
 231         ttSummary = tt;
 232
 233       } else if( shadowAge == AllocationSite.SHADOWAGE_notInThisSite ) {
 234         ttsOut.tokenTuples.add(tt);
 235
 236       } else if( shadowAge == AllocationSite.SHADOWAGE_summary ) {
 237         // found the shadow summary token, again just remember
 238         // for later
 239         foundShadowSummary = true;
 240
 241       } else if( shadowAge == AllocationSite.SHADOWAGE_oldest ) {
 242         Integer tokenToChangeTo = as.getOldest();
 243         TokenTuple ttNormal = tt.changeTokenTo(tokenToChangeTo);
 244         ttsOut.tokenTuples.add(ttNormal);
 245
 246       } else {
 247         assert shadowAge == AllocationSite.SHADOWAGE_in_I;
 248
 249         Integer I = as.getShadowAge(token);
 250         assert I != null;
 251
 252         Integer tokenToChangeTo = as.getIthOldest(-I);
 253         TokenTuple ttNormal = tt.changeTokenTo(tokenToChangeTo);
 254         ttsOut.tokenTuples.add(ttNormal);
 255       }
 256     }
 257
 258     if       ( ttSummary != null && !foundShadowSummary ) {
 259       ttsOut.tokenTuples.add(ttSummary);
 260
 261     } else if( ttSummary == null &&  foundShadowSummary ) {
 262       ttSummary = new TokenTuple(as.getSummary(),
 263                                  true,
 264                                  TokenTuple.ARITY_ONE).makeCanonical();
 265       ttsOut.tokenTuples.add(ttSummary);
 266
 267     } else if( ttSummary != null &&  foundShadowSummary ) {
 268       ttsOut.tokenTuples.add(ttSummary.increaseArity() );
 269     }
 270
 271     return ttsOut.makeCanonical();
 272   }
 273
 274
 275   public TokenTupleSet toShadowTokens(AllocationSite as) {
 276     assert as != null;
 277
 278     TokenTupleSet ttsOut = new TokenTupleSet();
 279
 280     Iterator itrT = this.iterator();
 281     while( itrT.hasNext() ) {
 282       TokenTuple tt = (TokenTuple) itrT.next();
 283
 284       Integer token = tt.getToken();
 285       int age = as.getAgeCategory(token);
 286
 287       // summary tokens and tokens not associated with
 288       // the site should be left alone
 289       if( age == AllocationSite.AGE_notInThisSite ) {
 290         ttsOut.tokenTuples.add(tt);
 291
 292       } else if( age == AllocationSite.AGE_summary ) {
 293         ttsOut.tokenTuples.add(tt.changeTokenTo(as.getSummaryShadow() ));
 294
 295       } else if( age == AllocationSite.AGE_oldest ) {
 296         ttsOut.tokenTuples.add(tt.changeTokenTo(as.getOldestShadow() ));
 297
 298       } else {
 299         assert age == AllocationSite.AGE_in_I;
 300
 301         Integer I = as.getAge(token);
 302         assert I != null;
 303
 304         ttsOut.tokenTuples.add(tt.changeTokenTo(as.getIthOldestShadow(I) ));
 305       }
 306     }
 307
 308     return ttsOut.makeCanonical();
 309   }
 310
 311
 312   public ReachabilitySet rewriteToken(TokenTuple tokenToRewrite,
 313                                       ReachabilitySet replacements,
 314                                       boolean makeChangeSet,
 315                                       Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > forChangeSet) {
 316
 317     ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
 318
 319     if( !tokenTuples.contains(tokenToRewrite) ) {
 320       rsOut = rsOut.add(this);
 321
 322     } else {
 323       TokenTupleSet ttsMinusToken = new TokenTupleSet(this);
 324       ttsMinusToken.tokenTuples.remove(tokenToRewrite);
 325
 326       Iterator<TokenTupleSet> replaceItr = replacements.iterator();
 327       while( replaceItr.hasNext() ) {
 328         TokenTupleSet replacement = replaceItr.next();
 329         TokenTupleSet replaced = new TokenTupleSet(ttsMinusToken);
 330         replaced = replaced.unionUpArity(replacement);
 331         rsOut = rsOut.add(replaced);
 332
 333         if( makeChangeSet ) {
 334           assert forChangeSet != null;
 335
 336           if( forChangeSet.get(this) == null ) {
 337             forChangeSet.put(this, new HashSet<TokenTupleSet>() );
 338           }
 339
 340           forChangeSet.get(this).add(replaced);
 341         }
 342       }
 343     }
 344
 345     return rsOut.makeCanonical();
 346   }
 347
 348
 349   public String toString() {
 350     return tokenTuples.toString();
 351   }
 352 }