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