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