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   public boolean containsWithZeroes(TokenTupleSet tts) {
  54     assert tts != null;
  55
  56     // first establish that every token tuple from tts is
  57     // also in this set
  58     Iterator<TokenTuple> ttItrIn = tts.iterator();
  59     while( ttItrIn.hasNext() ) {
  60       TokenTuple ttIn   = ttItrIn.next();
  61       TokenTuple ttThis = this.containsToken(ttIn.getToken() );
  62
  63       if( ttThis == null ) {
  64         return false;
  65       }
  66     }
  67
  68     // then establish that anything in this set that is
  69     // not in tts is a zero-arity token tuple, which is okay
  70     Iterator<TokenTuple> ttItrThis = this.iterator();
  71     while( ttItrThis.hasNext() ) {
  72       TokenTuple ttThis = ttItrThis.next();
  73       TokenTuple ttIn   = tts.containsToken(ttThis.getToken() );
  74
  75       if( ttIn == null &&
  76           ttThis.getArity() != TokenTuple.ARITY_ZEROORMORE ) {
  77         return false;
  78       }
  79     }
  80
  81     // if so this set contains tts with zeroes
  82     return true;
  83   }
  84
  85   public TokenTupleSet union(TokenTuple ttIn) {
  86     assert ttIn != null;
  87     TokenTupleSet ttsOut = new TokenTupleSet(this);
  88     ttsOut.tokenTuples.add(ttIn);
  89     return ttsOut.makeCanonical();
  90   }
  91
  92   public TokenTupleSet union(TokenTupleSet ttsIn) {
  93     assert ttsIn != null;
  94     TokenTupleSet ttsOut = new TokenTupleSet(this);
  95     ttsOut.tokenTuples.addAll(ttsIn.tokenTuples);
  96     return ttsOut.makeCanonical();
  97   }
  98
  99
 100   public TokenTupleSet unionUpArity(TokenTupleSet ttsIn) {
 101     assert ttsIn != null;
 102     TokenTupleSet ttsOut = new TokenTupleSet();
 103
 104     Iterator<TokenTuple> ttItr = this.iterator();
 105     while( ttItr.hasNext() ) {
 106       TokenTuple ttThis = ttItr.next();
 107       TokenTuple ttIn   = ttsIn.containsToken(ttThis.getToken() );
 108
 109       if( ttIn != null ) {
 110         ttsOut.tokenTuples.add(ttThis.unionArity(ttIn) );
 111       } else {
 112         ttsOut.tokenTuples.add(ttThis);
 113       }
 114     }
 115
 116     ttItr = ttsIn.iterator();
 117     while( ttItr.hasNext() ) {
 118       TokenTuple ttIn   = ttItr.next();
 119       TokenTuple ttThis = ttsOut.containsToken(ttIn.getToken() );
 120
 121       if( ttThis == null ) {
 122         ttsOut.tokenTuples.add(ttIn);
 123       }
 124     }
 125
 126     return ttsOut.makeCanonical();
 127   }
 128
 129
 130   public TokenTupleSet add(TokenTuple tt) {
 131     assert tt != null;
 132     TokenTupleSet ttsOut = new TokenTupleSet(tt);
 133     return ttsOut.union(this);
 134   }
 135
 136
 137   public boolean equals(Object o) {
 138     if( o == null ) {
 139       return false;
 140     }
 141
 142     if( !(o instanceof TokenTupleSet) ) {
 143       return false;
 144     }
 145
 146     TokenTupleSet tts = (TokenTupleSet) o;
 147     return tokenTuples.equals(tts.tokenTuples);
 148   }
 149
 150
 151
 152   private boolean oldHashSet = false;
 153   private int oldHash    = 0;
 154   public int hashCode() {
 155     int currentHash = tokenTuples.hashCode();
 156
 157     if( oldHashSet == false ) {
 158       oldHash = currentHash;
 159       oldHashSet = true;
 160     } else {
 161       if( oldHash != currentHash ) {
 162         System.out.println("IF YOU SEE THIS A CANONICAL TokenTupleSet CHANGED");
 163         Integer x = null;
 164         x.toString();
 165       }
 166     }
 167
 168     return currentHash;
 169   }
 170
 171
 172   // this should be a hash table so we can do this by key
 173   public TokenTuple containsToken(Integer token) {
 174     assert token != null;
 175
 176     Iterator itr = tokenTuples.iterator();
 177     while( itr.hasNext() ) {
 178       TokenTuple tt = (TokenTuple) itr.next();
 179       if( token.equals(tt.getToken() ) ) {
 180         return tt;
 181       }
 182     }
 183     return null;
 184   }
 185
 186
 187   public TokenTupleSet ageTokens(AllocationSite as) {
 188     assert as != null;
 189
 190     TokenTupleSet ttsOut = new TokenTupleSet();
 191
 192     TokenTuple ttSummary = null;
 193     TokenTuple ttOldest  = null;
 194
 195     Iterator itrT = this.iterator();
 196     while( itrT.hasNext() ) {
 197       TokenTuple tt = (TokenTuple) itrT.next();
 198
 199       Integer token = tt.getToken();
 200       int age = as.getAgeCategory(token);
 201
 202       // tokens not associated with
 203       // the site should be left alone
 204       if( age == AllocationSite.AGE_notInThisSite ) {
 205         ttsOut.tokenTuples.add(tt);
 206
 207       } else if( age == AllocationSite.AGE_summary ) {
 208         // remember the summary tuple, but don't add it
 209         // we may combine it with the oldest tuple
 210         ttSummary = tt;
 211
 212       } else if( age == AllocationSite.AGE_oldest ) {
 213         // found an oldest token, again just remember
 214         // for later
 215         ttOldest = tt;
 216
 217       } else {
 218         assert age == AllocationSite.AGE_in_I;
 219
 220         Integer I = as.getAge(token);
 221         assert I != null;
 222
 223         // otherwise, we change this token to the
 224         // next older token
 225         Integer tokenToChangeTo = as.getIthOldest(I + 1);
 226         TokenTuple ttAged       = tt.changeTokenTo(tokenToChangeTo);
 227         ttsOut.tokenTuples.add(ttAged);
 228       }
 229     }
 230
 231     // there are four cases to consider here
 232     // 1. we found a summary tuple and no oldest tuple
 233     //    Here we just pass the summary unchanged
 234     // 2. we found an oldest tuple, no summary
 235     //    Make a new, arity-one summary tuple
 236     // 3. we found both a summary and an oldest
 237     //    Merge them by arity
 238     // 4. (not handled) we found neither, do nothing
 239     if       ( ttSummary != null && ttOldest == null ) {
 240       ttsOut.tokenTuples.add(ttSummary);
 241
 242     } else if( ttSummary == null && ttOldest != null ) {
 243       ttsOut.tokenTuples.add(new TokenTuple(as.getSummary(),
 244                                             true,
 245                                             ttOldest.getArity()
 246                                             ).makeCanonical()
 247                              );
 248
 249     } else if( ttSummary != null && ttOldest != null ) {
 250       ttsOut.tokenTuples.add(ttSummary.unionArity(new TokenTuple(as.getSummary(),
 251                                                                  true,
 252                                                                  ttOldest.getArity()
 253                                                                  ).makeCanonical()
 254                                                   )
 255                              );
 256     }
 257
 258     return ttsOut.makeCanonical();
 259   }
 260
 261
 262   public TokenTupleSet unshadowTokens(AllocationSite as) {
 263     assert as != null;
 264
 265     TokenTupleSet ttsOut = new TokenTupleSet();
 266
 267     TokenTuple ttSummary       = null;
 268     TokenTuple ttShadowSummary = null;
 269
 270     Iterator itrT = this.iterator();
 271     while( itrT.hasNext() ) {
 272       TokenTuple tt = (TokenTuple) itrT.next();
 273
 274       Integer token = tt.getToken();
 275       int shadowAge = as.getShadowAgeCategory(token);
 276
 277       if( shadowAge == AllocationSite.AGE_summary ) {
 278         // remember the summary tuple, but don't add it
 279         // we may combine it with the oldest tuple
 280         ttSummary = tt;
 281
 282       } else if( shadowAge == AllocationSite.SHADOWAGE_notInThisSite ) {
 283         ttsOut.tokenTuples.add(tt);
 284
 285       } else if( shadowAge == AllocationSite.SHADOWAGE_summary ) {
 286         // found the shadow summary token, again just remember
 287         // for later
 288         ttShadowSummary = tt;
 289
 290       } else if( shadowAge == AllocationSite.SHADOWAGE_oldest ) {
 291         Integer tokenToChangeTo = as.getOldest();
 292         TokenTuple ttNormal = tt.changeTokenTo(tokenToChangeTo);
 293         ttsOut.tokenTuples.add(ttNormal);
 294
 295       } else {
 296         assert shadowAge == AllocationSite.SHADOWAGE_in_I;
 297
 298         Integer I = as.getShadowAge(token);
 299         assert I != null;
 300
 301         Integer tokenToChangeTo = as.getIthOldest(-I);
 302         TokenTuple ttNormal = tt.changeTokenTo(tokenToChangeTo);
 303         ttsOut.tokenTuples.add(ttNormal);
 304       }
 305     }
 306
 307     if       ( ttSummary != null && ttShadowSummary == null ) {
 308       ttsOut.tokenTuples.add(ttSummary);
 309
 310     } else if( ttSummary == null && ttShadowSummary != null ) {
 311       ttsOut.tokenTuples.add(new TokenTuple(as.getSummary(),
 312                                             true,
 313                                             ttShadowSummary.getArity()
 314                                             ).makeCanonical()
 315                              );
 316
 317     } else if( ttSummary != null && ttShadowSummary != null ) {
 318       ttsOut.tokenTuples.add(ttSummary.unionArity(new TokenTuple(as.getSummary(),
 319                                                                  true,
 320                                                                  ttShadowSummary.getArity()
 321                                                                  ).makeCanonical()
 322                                                   )
 323                              );
 324     }
 325
 326     return ttsOut.makeCanonical();
 327   }
 328
 329
 330   public TokenTupleSet toShadowTokens(AllocationSite as) {
 331     assert as != null;
 332
 333     TokenTupleSet ttsOut = new TokenTupleSet().makeCanonical();
 334
 335     Iterator itrT = this.iterator();
 336     while( itrT.hasNext() ) {
 337       TokenTuple tt = (TokenTuple) itrT.next();
 338
 339       Integer token = tt.getToken();
 340       int age = as.getAgeCategory(token);
 341
 342       // summary tokens and tokens not associated with
 343       // the site should be left alone
 344       if( age == AllocationSite.AGE_notInThisSite ) {
 345         ttsOut = ttsOut.union(tt);
 346
 347       } else if( age == AllocationSite.AGE_summary ) {
 348         ttsOut = ttsOut.union(tt.changeTokenTo(as.getSummaryShadow() ));
 349
 350       } else if( age == AllocationSite.AGE_oldest ) {
 351         ttsOut = ttsOut.union(tt.changeTokenTo(as.getOldestShadow() ));
 352
 353       } else {
 354         assert age == AllocationSite.AGE_in_I;
 355
 356         Integer I = as.getAge(token);
 357         assert I != null;
 358
 359         ttsOut = ttsOut.union(tt.changeTokenTo(as.getIthOldestShadow(I) ));
 360       }
 361     }
 362
 363     return ttsOut.makeCanonical();
 364   }
 365
 366
 367   public ReachabilitySet rewriteToken(TokenTuple tokenToRewrite,
 368                                       ReachabilitySet replacements,
 369                                       boolean makeChangeSet,
 370                                       Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > forChangeSet) {
 371
 372     ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
 373
 374     if( !tokenTuples.contains(tokenToRewrite) ) {
 375       rsOut = rsOut.add(this);
 376
 377     } else {
 378       TokenTupleSet ttsMinusToken = new TokenTupleSet(this);
 379       ttsMinusToken.tokenTuples.remove(tokenToRewrite);
 380
 381       Iterator<TokenTupleSet> replaceItr = replacements.iterator();
 382       while( replaceItr.hasNext() ) {
 383         TokenTupleSet replacement = replaceItr.next();
 384         TokenTupleSet replaced = new TokenTupleSet(ttsMinusToken).makeCanonical();
 385         replaced = replaced.unionUpArity(replacement);
 386         rsOut = rsOut.add(replaced);
 387
 388         if( makeChangeSet ) {
 389           assert forChangeSet != null;
 390
 391           if( forChangeSet.get(this) == null ) {
 392             forChangeSet.put(this, new HashSet<TokenTupleSet>() );
 393           }
 394
 395           forChangeSet.get(this).add(replaced);
 396         }
 397       }
 398     }
 399
 400     return rsOut.makeCanonical();
 401   }
 402
 403
 404   public TokenTupleSet makeArityZeroOrMore() {
 405     TokenTupleSet ttsOut = new TokenTupleSet().makeCanonical();
 406
 407     Iterator<TokenTuple> itrThis = this.iterator();
 408     while( itrThis.hasNext() ) {
 409       TokenTuple tt = itrThis.next();
 410
 411       ttsOut = ttsOut.union(new TokenTuple(tt.getToken(),
 412                                            tt.isMultiObject(),
 413                                            TokenTuple.ARITY_ZEROORMORE
 414                                            ).makeCanonical()
 415                             );
 416     }
 417
 418     return ttsOut.makeCanonical();
 419   }
 420
 421   public String toString() {
 422     return tokenTuples.toString();
 423   }
 424 }