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
  62   public TokenTupleSet unionUpArity(TokenTupleSet ttsIn) {
  63     assert ttsIn != null;
  64     TokenTupleSet ttsOut = new TokenTupleSet();
  65
  66     Iterator<TokenTuple> ttItr = this.iterator();
  67     while( ttItr.hasNext() ) {
  68       TokenTuple ttThis = ttItr.next();
  69       TokenTuple ttIn   = ttsIn.containsToken( ttThis.getToken() );
  70
  71       if( ttIn != null ) {
  72         ttsOut.tokenTuples.add( ttThis.unionArity( ttIn ) );
  73       } else {
  74         ttsOut.tokenTuples.add( ttThis );
  75       }
  76     }
  77
  78     ttItr = ttsIn.iterator();
  79     while( ttItr.hasNext() ) {
  80       TokenTuple ttIn   = ttItr.next();
  81       TokenTuple ttThis = ttsOut.containsToken( ttIn.getToken() );
  82
  83       if( ttThis == null ) {
  84         ttsOut.tokenTuples.add( ttIn );
  85       }
  86     }
  87
  88     return ttsOut.makeCanonical();
  89   }
  90
  91
  92   public TokenTupleSet add(TokenTuple tt) {
  93     assert tt != null;
  94     TokenTupleSet ttsOut = new TokenTupleSet(tt);
  95     return ttsOut.union(this);
  96   }
  97
  98
  99   public boolean equals(Object o) {
 100     if( o == null ) {
 101       return false;
 102     }
 103
 104     if( !(o instanceof TokenTupleSet) ) {
 105       return false;
 106     }
 107
 108     TokenTupleSet tts = (TokenTupleSet) o;
 109     return tokenTuples.equals(tts.tokenTuples);
 110   }
 111
 112   public int hashCode() {
 113     return tokenTuples.hashCode();
 114   }
 115
 116
 117   // this should be a hash table so we can do this by key
 118   public TokenTuple containsToken(Integer token) {
 119     assert token != null;
 120
 121     Iterator itr = tokenTuples.iterator();
 122     while( itr.hasNext() ) {
 123       TokenTuple tt = (TokenTuple) itr.next();
 124       if( token.equals(tt.getToken() ) ) {
 125         return tt;
 126       }
 127     }
 128     return null;
 129   }
 130
 131
 132   public TokenTupleSet ageTokens(AllocationSite as) {
 133     assert as != null;
 134
 135     TokenTupleSet ttsOut = new TokenTupleSet();
 136
 137     TokenTuple ttSummary = null;
 138     TokenTuple ttOldest  = null;
 139
 140     Iterator itrT = this.iterator();
 141     while( itrT.hasNext() ) {
 142       TokenTuple tt = (TokenTuple) itrT.next();
 143
 144       Integer token = tt.getToken();
 145       int age = as.getAgeCategory(token);
 146
 147       // tokens not associated with
 148       // the site should be left alone
 149       if( age == AllocationSite.AGE_notInThisSite ) {
 150         ttsOut.tokenTuples.add(tt);
 151
 152       } else if( age == AllocationSite.AGE_summary ) {
 153         // remember the summary tuple, but don't add it
 154         // we may combine it with the oldest tuple
 155         ttSummary = tt;
 156
 157       } else if( age == AllocationSite.AGE_oldest ) {
 158         // found an oldest token, again just remember
 159         // for later
 160         ttOldest = tt;
 161
 162       } else {
 163         assert age == AllocationSite.AGE_in_I;
 164
 165         Integer I = as.getAge(token);
 166         assert I != null;
 167
 168         // otherwise, we change this token to the
 169         // next older token
 170         Integer tokenToChangeTo = as.getIthOldest(I + 1);
 171         TokenTuple ttAged       = tt.changeTokenTo(tokenToChangeTo);
 172         ttsOut.tokenTuples.add(ttAged);
 173       }
 174     }
 175
 176     // there are four cases to consider here
 177     // 1. we found a summary tuple and no oldest tuple
 178     //    Here we just pass the summary unchanged
 179     // 2. we found an oldest tuple, no summary
 180     //    Make a new, arity-one summary tuple
 181     // 3. we found both a summary and an oldest
 182     //    Merge them by arity
 183     // 4. (not handled) we found neither, do nothing
 184     if       ( ttSummary != null && ttOldest == null ) {
 185       ttsOut.tokenTuples.add(ttSummary);
 186
 187     } else if( ttSummary == null && ttOldest != null ) {
 188       ttsOut.tokenTuples.add(new TokenTuple(as.getSummary(),
 189                                             true,
 190                                             ttOldest.getArity()
 191                                            ).makeCanonical()
 192                              );
 193
 194     } else if( ttSummary != null && ttOldest != null ) {
 195       ttsOut.tokenTuples.add(ttSummary.unionArity(new TokenTuple(as.getSummary(),
 196                                                                  true,
 197                                                                  ttOldest.getArity()
 198                                                                  ).makeCanonical()
 199                                                   )
 200                              );
 201     }
 202
 203     return ttsOut.makeCanonical();
 204   }
 205
 206
 207   public TokenTupleSet unshadowTokens(AllocationSite as) {
 208     assert as != null;
 209
 210     TokenTupleSet ttsOut = new TokenTupleSet();
 211
 212     TokenTuple ttSummary       = null;
 213     TokenTuple ttShadowSummary = null;
 214
 215     Iterator itrT = this.iterator();
 216     while( itrT.hasNext() ) {
 217       TokenTuple tt = (TokenTuple) itrT.next();
 218
 219       Integer token = tt.getToken();
 220       int shadowAge = as.getShadowAgeCategory(token);
 221
 222       if( shadowAge == AllocationSite.AGE_summary ) {
 223         // remember the summary tuple, but don't add it
 224         // we may combine it with the oldest tuple
 225         ttSummary = tt;
 226
 227       } else if( shadowAge == AllocationSite.SHADOWAGE_notInThisSite ) {
 228         ttsOut.tokenTuples.add(tt);
 229
 230       } else if( shadowAge == AllocationSite.SHADOWAGE_summary ) {
 231         // found the shadow summary token, again just remember
 232         // for later
 233         ttShadowSummary = tt;
 234
 235       } else if( shadowAge == AllocationSite.SHADOWAGE_oldest ) {
 236         Integer tokenToChangeTo = as.getOldest();
 237         TokenTuple ttNormal = tt.changeTokenTo(tokenToChangeTo);
 238         ttsOut.tokenTuples.add(ttNormal);
 239
 240       } else {
 241         assert shadowAge == AllocationSite.SHADOWAGE_in_I;
 242
 243         Integer I = as.getShadowAge(token);
 244         assert I != null;
 245
 246         Integer tokenToChangeTo = as.getIthOldest(-I);
 247         TokenTuple ttNormal = tt.changeTokenTo(tokenToChangeTo);
 248         ttsOut.tokenTuples.add(ttNormal);
 249       }
 250     }
 251
 252     if       ( ttSummary != null && ttShadowSummary == null ) {
 253       ttsOut.tokenTuples.add(ttSummary);
 254
 255     } else if( ttSummary == null && ttShadowSummary != null ) {
 256       ttsOut.tokenTuples.add( new TokenTuple(as.getSummary(),
 257                                              true,
 258                                              ttShadowSummary.getArity()
 259                                              ).makeCanonical()
 260                               );
 261
 262     } else if( ttSummary != null && ttShadowSummary != null ) {
 263       ttsOut.tokenTuples.add(ttSummary.unionArity( new TokenTuple(as.getSummary(),
 264                                                                   true,
 265                                                                   ttShadowSummary.getArity()
 266                                                                   ).makeCanonical()
 267                                                    )
 268                              );
 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().makeCanonical();
 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 TokenTupleSet makeArityZeroOrMore() {
 350     TokenTupleSet ttsOut = new TokenTupleSet().makeCanonical();
 351
 352     Iterator<TokenTuple> itrThis = this.iterator();
 353     while( itrThis.hasNext() ) {
 354       TokenTuple tt = itrThis.next();
 355
 356       ttsOut.tokenTuples.add( new TokenTuple( tt.getToken(),
 357                                              tt.isMultiObject(),
 358                                              TokenTuple.ARITY_ZEROORMORE
 359                                             ).makeCanonical()
 360                               );
 361     }
 362
 363     return ttsOut.makeCanonical();
 364   }
 365
 366
 367   public String toString() {
 368     return tokenTuples.toString();
 369   }
 370 }