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