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   public TokenTupleSet unionUpArity( TokenTupleSet ttsIn ) {
  62     assert ttsIn != null;
  63     TokenTupleSet ttsOut = new TokenTupleSet();
  64
  65     Iterator<TokenTuple> ttItr = this.iterator();
  66     while( ttItr.hasNext() ) {
  67       TokenTuple tt = ttItr.next();
  68
  69       if( ttsIn.containsToken( tt.getToken() ) ) {
  70         ttsOut.tokenTuples.add(tt.increaseArity());
  71       } else {
  72         ttsOut.tokenTuples.add(tt);
  73       }
  74     }
  75
  76     ttItr = ttsIn.iterator();
  77     while( ttItr.hasNext() ) {
  78       TokenTuple tt = ttItr.next();
  79
  80       if( !ttsOut.containsToken(tt.getToken()) ) {
  81         ttsOut.tokenTuples.add(tt);
  82       }
  83     }
  84
  85     return ttsOut.makeCanonical();
  86   }
  87
  88   public TokenTupleSet add(TokenTuple tt) {
  89     assert tt != null;
  90     TokenTupleSet ttsOut = new TokenTupleSet(tt);
  91     return ttsOut.union(this);
  92   }
  93
  94
  95   // this should only be done with a multiple-object heap region's token!
  96   public TokenTupleSet increaseArity(Integer token) {
  97     assert token != null;
  98     TokenTupleSet ttsOut = new TokenTupleSet(this);
  99     TokenTuple tt
 100     = new TokenTuple(token, true, TokenTuple.ARITY_ONE).makeCanonical();
 101     if( ttsOut.tokenTuples.contains(tt) ) {
 102       ttsOut.tokenTuples.remove(tt);
 103       ttsOut.tokenTuples.add(
 104         new TokenTuple(token, true, TokenTuple.ARITY_MANY).makeCanonical()
 105         );
 106     }
 107
 108     return ttsOut.makeCanonical();
 109   }
 110
 111
 112   public boolean equals(Object o) {
 113     if( o == null ) {
 114       return false;
 115     }
 116
 117     if( !(o instanceof TokenTupleSet) ) {
 118       return false;
 119     }
 120
 121     TokenTupleSet tts = (TokenTupleSet) o;
 122     return tokenTuples.equals(tts.tokenTuples);
 123   }
 124
 125   public int hashCode() {
 126     return tokenTuples.hashCode();
 127   }
 128
 129
 130   // this should be a hash table so we can do this by key
 131   public boolean containsToken(Integer token) {
 132     assert token != null;
 133
 134     Iterator itr = tokenTuples.iterator();
 135     while( itr.hasNext() ) {
 136       TokenTuple tt = (TokenTuple) itr.next();
 137       if( token.equals(tt.getToken() ) ) {
 138         return true;
 139       }
 140     }
 141     return false;
 142   }
 143
 144
 145   public TokenTupleSet ageTokens(AllocationSite as) {
 146     assert as != null;
 147
 148     TokenTupleSet ttsOut = new TokenTupleSet();
 149
 150     TokenTuple ttSummary = null;
 151     boolean foundOldest  = false;
 152
 153     Iterator itrT = this.iterator();
 154     while( itrT.hasNext() ) {
 155       TokenTuple tt = (TokenTuple) itrT.next();
 156
 157       Integer token = tt.getToken();
 158       int age = as.getAge(token);
 159
 160       // summary tokens and tokens not associated with
 161       // the site should be left alone
 162       if( age == AllocationSite.AGE_notInThisSite ) {
 163         ttsOut.tokenTuples.add(tt);
 164
 165       } else {
 166         if( age == AllocationSite.AGE_summary ) {
 167           // remember the summary tuple, but don't add it
 168           // we may combine it with the oldest tuple
 169           ttSummary = tt;
 170
 171         } else if( age == AllocationSite.AGE_oldest ) {
 172           // found an oldest token, again just remember
 173           // for later
 174           foundOldest = true;
 175
 176         } else {
 177           // otherwise, we change this token to the
 178           // next older token
 179           Integer tokenToChangeTo = as.getIthOldest(age + 1);
 180           TokenTuple ttAged       = tt.changeTokenTo(tokenToChangeTo);
 181           ttsOut.tokenTuples.add(ttAged);
 182         }
 183
 184       }
 185     }
 186
 187     // there are four cases to consider here
 188     // 1. we found a summary tuple and no oldest tuple
 189     //    Here we just pass the summary unchanged
 190     // 2. we found an oldest tuple, no summary
 191     //    Make a new, arity-one summary tuple
 192     // 3. we found both a summary and an oldest
 193     //    Merge them by increasing arity of summary
 194     // 4. (not handled) we found neither, do nothing
 195     if       ( ttSummary != null && !foundOldest ) {
 196       ttsOut.tokenTuples.add(ttSummary);
 197
 198     } else if( ttSummary == null &&  foundOldest ) {
 199       ttsOut.tokenTuples.add(new TokenTuple(as.getSummary(),
 200                                             true,
 201                                             TokenTuple.ARITY_ONE).makeCanonical() );
 202
 203     } else if( ttSummary != null &&  foundOldest ) {
 204       ttsOut.tokenTuples.add(ttSummary.increaseArity() );
 205     }
 206
 207     return ttsOut.makeCanonical();
 208   }
 209
 210
 211   public ReachabilitySet rewriteToken( TokenTuple tokenToRewrite,
 212                                        ReachabilitySet replacements,
 213                                        boolean makeChangeSet,
 214                                        Hashtable<TokenTupleSet, TokenTupleSet> forChangeSet ) {
 215
 216     ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
 217
 218     if( !tokenTuples.contains( tokenToRewrite ) ) {
 219       rsOut = rsOut.add( this );
 220
 221     } else {
 222       TokenTupleSet ttsMinusToken = new TokenTupleSet( this );
 223       ttsMinusToken.tokenTuples.remove( tokenToRewrite );
 224
 225       Iterator<TokenTupleSet> replaceItr = replacements.iterator();
 226       while( replaceItr.hasNext() ) {
 227         TokenTupleSet replacement = replaceItr.next();
 228         TokenTupleSet replaced = new TokenTupleSet( ttsMinusToken );
 229         replaced = replaced.unionUpArity( replacement );
 230         rsOut = rsOut.add( replaced );
 231
 232         if( makeChangeSet ) {
 233           assert forChangeSet != null;
 234           forChangeSet.put( this, replaced );
 235         }
 236       }
 237     }
 238
 239     return rsOut.makeCanonical();
 240   }
 241
 242
 243   public String toString() {
 244     return tokenTuples.toString();
 245   }
 246 }