Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.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 ReachabilitySet extends Canonical {
  10
  11   private HashSet<TokenTupleSet> possibleReachabilities;
  12
  13   public ReachabilitySet() {
  14     possibleReachabilities = new HashSet<TokenTupleSet>();
  15   }
  16
  17   public ReachabilitySet(TokenTupleSet tts) {
  18     this();
  19     assert tts != null;
  20     possibleReachabilities.add(tts);
  21   }
  22
  23   public ReachabilitySet(TokenTuple tt) {
  24     // can't assert before calling this(), it will
  25     // do the checking though
  26     this( new TokenTupleSet(tt).makeCanonical() );
  27   }
  28
  29   public ReachabilitySet(HashSet<TokenTupleSet> possibleReachabilities) {
  30     assert possibleReachabilities != null;
  31     this.possibleReachabilities = possibleReachabilities;
  32   }
  33
  34   public ReachabilitySet(ReachabilitySet rs) {
  35     assert rs != null;
  36     // okay to clone, ReachabilitySet should be canonical
  37     possibleReachabilities = (HashSet<TokenTupleSet>)rs.possibleReachabilities.clone();
  38   }
  39
  40
  41   public ReachabilitySet makeCanonical() {
  42     return (ReachabilitySet) Canonical.makeCanonical(this);
  43   }
  44
  45   public Iterator<TokenTupleSet> iterator() {
  46     return possibleReachabilities.iterator();
  47   }
  48
  49
  50   public int size() {
  51     return possibleReachabilities.size();
  52   }
  53
  54   public boolean isEmpty() {
  55     return possibleReachabilities.isEmpty();
  56   }
  57
  58   public boolean contains(TokenTupleSet tts) {
  59     assert tts != null;
  60     return possibleReachabilities.contains(tts);
  61   }
  62
  63   public boolean containsWithZeroes(TokenTupleSet tts) {
  64     assert tts != null;
  65
  66     if( possibleReachabilities.contains(tts) ) {
  67       return true;
  68     }
  69
  70     Iterator itr = iterator();
  71     while( itr.hasNext() ) {
  72       TokenTupleSet ttsThis = (TokenTupleSet) itr.next();
  73       if( ttsThis.containsWithZeroes(tts) ) {
  74         return true;
  75       }
  76     }
  77
  78     return false;
  79   }
  80
  81   public boolean containsSuperSet(TokenTupleSet tts) {
  82     assert tts != null;
  83
  84     if( possibleReachabilities.contains(tts) ) {
  85       return true;
  86     }
  87
  88     Iterator itr = iterator();
  89     while( itr.hasNext() ) {
  90       TokenTupleSet ttsThis = (TokenTupleSet) itr.next();
  91       if( tts.isSubset(ttsThis) ) {
  92         return true;
  93       }
  94     }
  95
  96     return false;
  97   }
  98
  99
 100   public boolean containsTuple(TokenTuple tt) {
 101     Iterator itr = iterator();
 102     while( itr.hasNext() ) {
 103       TokenTupleSet tts = (TokenTupleSet) itr.next();
 104       if( tts.containsTuple(tt) ) {
 105         return true;
 106       }
 107     }
 108     return false;
 109   }
 110
 111   public boolean containsTupleSetWithBoth(TokenTuple tt1, TokenTuple tt2) {
 112     Iterator itr = iterator();
 113     while( itr.hasNext() ) {
 114       TokenTupleSet tts = (TokenTupleSet) itr.next();
 115       if( tts.containsTuple(tt1) && tts.containsTuple(tt2) ) {
 116         return true;
 117       }
 118     }
 119     return false;
 120   }
 121
 122   public ReachabilitySet union(ReachabilitySet rsIn) {
 123     assert rsIn != null;
 124
 125     ReachabilitySet rsOut = new ReachabilitySet(this);
 126     rsOut.possibleReachabilities.addAll(rsIn.possibleReachabilities);
 127     return rsOut.makeCanonical();
 128   }
 129
 130   public ReachabilitySet union(TokenTupleSet ttsIn) {
 131     assert ttsIn != null;
 132
 133     ReachabilitySet rsOut = new ReachabilitySet(this);
 134     rsOut.possibleReachabilities.add(ttsIn);
 135     return rsOut.makeCanonical();
 136   }
 137
 138   public ReachabilitySet intersection(ReachabilitySet rsIn) {
 139     assert rsIn != null;
 140
 141     ReachabilitySet rsOut = new ReachabilitySet();
 142
 143     Iterator i = this.iterator();
 144     while( i.hasNext() ) {
 145       TokenTupleSet tts = (TokenTupleSet) i.next();
 146       if( rsIn.possibleReachabilities.contains(tts) ) {
 147         rsOut.possibleReachabilities.add(tts);
 148       }
 149     }
 150
 151     return rsOut.makeCanonical();
 152   }
 153
 154
 155   public ReachabilitySet add(TokenTupleSet tts) {
 156     assert tts != null;
 157     ReachabilitySet rsOut = new ReachabilitySet(tts);
 158     return rsOut.union(this);
 159   }
 160
 161
 162   public ChangeTupleSet unionUpArityToChangeSet(ReachabilitySet rsIn) {
 163     assert rsIn != null;
 164
 165     ChangeTupleSet ctsOut = new ChangeTupleSet();
 166
 167     Iterator itrO = this.iterator();
 168     while( itrO.hasNext() ) {
 169       TokenTupleSet o = (TokenTupleSet) itrO.next();
 170
 171       Iterator itrR = rsIn.iterator();
 172       while( itrR.hasNext() ) {
 173         TokenTupleSet r = (TokenTupleSet) itrR.next();
 174
 175         TokenTupleSet theUnion = new TokenTupleSet().makeCanonical();
 176
 177         Iterator itrRelement = r.iterator();
 178         while( itrRelement.hasNext() ) {
 179           TokenTuple ttR = (TokenTuple) itrRelement.next();
 180           TokenTuple ttO = o.containsToken(ttR.getToken() );
 181
 182           if( ttO != null ) {
 183             theUnion = theUnion.union(new TokenTupleSet(ttR.unionArity(ttO) ) ).makeCanonical();
 184           } else {
 185             theUnion = theUnion.union(new TokenTupleSet(ttR) ).makeCanonical();
 186           }
 187         }
 188
 189         Iterator itrOelement = o.iterator();
 190         while( itrOelement.hasNext() ) {
 191           TokenTuple ttO = (TokenTuple) itrOelement.next();
 192           TokenTuple ttR = theUnion.containsToken(ttO.getToken() );
 193
 194           if( ttR == null ) {
 195             theUnion = theUnion.union(new TokenTupleSet(ttO) ).makeCanonical();
 196           }
 197         }
 198
 199         if( !theUnion.isEmpty() ) {
 200           ctsOut = ctsOut.union(new ChangeTupleSet(new ChangeTuple(o, theUnion) ) );
 201         }
 202       }
 203     }
 204
 205     return ctsOut.makeCanonical();
 206   }
 207
 208
 209   public ReachabilitySet ageTokens(AllocationSite as) {
 210     assert as != null;
 211
 212     ReachabilitySet rsOut = new ReachabilitySet();
 213
 214     Iterator itrS = this.iterator();
 215     while( itrS.hasNext() ) {
 216       TokenTupleSet tts = (TokenTupleSet) itrS.next();
 217       rsOut.possibleReachabilities.add(tts.ageTokens(as) );
 218     }
 219
 220     return rsOut.makeCanonical();
 221   }
 222
 223
 224   public ReachabilitySet unshadowTokens(AllocationSite as) {
 225     assert as != null;
 226
 227     ReachabilitySet rsOut = new ReachabilitySet();
 228
 229     Iterator itrS = this.iterator();
 230     while( itrS.hasNext() ) {
 231       TokenTupleSet tts = (TokenTupleSet) itrS.next();
 232       rsOut.possibleReachabilities.add(tts.unshadowTokens(as) );
 233     }
 234
 235     return rsOut.makeCanonical();
 236   }
 237
 238
 239   public ReachabilitySet toShadowTokens(AllocationSite as) {
 240     assert as != null;
 241
 242     ReachabilitySet rsOut = new ReachabilitySet();
 243
 244     Iterator itrS = this.iterator();
 245     while( itrS.hasNext() ) {
 246       TokenTupleSet tts = (TokenTupleSet) itrS.next();
 247       rsOut.possibleReachabilities.add(tts.toShadowTokens(as) );
 248     }
 249
 250     return rsOut.makeCanonical();
 251   }
 252
 253
 254   public ReachabilitySet pruneBy(ReachabilitySet rsIn) {
 255     assert rsIn != null;
 256
 257     ReachabilitySet rsOut = new ReachabilitySet();
 258
 259     Iterator itrB = this.iterator();
 260     while( itrB.hasNext() ) {
 261       TokenTupleSet ttsB = (TokenTupleSet) itrB.next();
 262
 263       boolean subsetExists = false;
 264
 265       Iterator itrA = rsIn.iterator();
 266       while( itrA.hasNext() && !subsetExists ) {
 267         TokenTupleSet ttsA = (TokenTupleSet) itrA.next();
 268
 269         if( ttsA.isSubset(ttsB) ) {
 270           subsetExists = true;
 271         }
 272       }
 273
 274       if( subsetExists ) {
 275         rsOut.possibleReachabilities.add(ttsB);
 276       }
 277     }
 278
 279     return rsOut.makeCanonical();
 280   }
 281
 282
 283   public ReachabilitySet exhaustiveArityCombinations() {
 284     ReachabilitySet rsOut = new ReachabilitySet();
 285
 286     int numDimensions = this.possibleReachabilities.size();
 287
 288     if( numDimensions > 1 ) {
 289       // for problems that are too big, punt and use less
 290       // precise arity for reachability information
 291       TokenTupleSet ttsImprecise = new TokenTupleSet().makeCanonical();
 292
 293       Iterator<TokenTupleSet> itrThis = this.iterator();
 294       while( itrThis.hasNext() ) {
 295         TokenTupleSet ttsUnit = itrThis.next();
 296         ttsImprecise = ttsImprecise.unionUpArity(ttsUnit.makeArityZeroOrMore() );
 297       }
 298
 299       //rsOut = this.union( ttsImprecise );
 300       rsOut = rsOut.union(ttsImprecise);
 301       return rsOut;
 302     }
 303
 304     // add an extra digit to detect termination
 305     int[] digits = new int[numDimensions+1];
 306
 307     int minArity = 0;
 308     int maxArity = 2;
 309
 310     // start with the minimum possible coordinate
 311     for( int i = 0; i < numDimensions+1; ++i ) {
 312       digits[i] = minArity;
 313     }
 314
 315     // and stop when the highest-ordered axis rolls above the minimum
 316     while( digits[numDimensions] == minArity ) {
 317
 318       // spit out a "coordinate" made from these digits
 319       TokenTupleSet ttsCoordinate = new TokenTupleSet().makeCanonical();
 320       Iterator<TokenTupleSet> ttsItr = this.iterator();
 321       for( int i = 0; i < numDimensions; ++i ) {
 322         assert ttsItr.hasNext();
 323         TokenTupleSet ttsUnit = ttsItr.next();
 324         for( int j = 0; j < digits[i]; ++j ) {
 325           ttsCoordinate = ttsCoordinate.unionUpArity(ttsUnit);
 326         }
 327       }
 328       rsOut = rsOut.add(ttsCoordinate.makeCanonical() );
 329
 330       // increment
 331       for( int i = 0; i < numDimensions+1; ++i ) {
 332         digits[i]++;
 333
 334         if( digits[i] > maxArity ) {
 335           // this axis reached its max, so roll it back to min and increment next higher digit
 336           digits[i] = minArity;
 337
 338         } else {
 339           // this axis did not reach its max so we just enumerated a new unique coordinate, stop
 340           break;
 341         }
 342       }
 343     }
 344
 345     return rsOut.makeCanonical();
 346   }
 347
 348
 349   public boolean equals(Object o) {
 350     if( o == null ) {
 351       return false;
 352     }
 353
 354     if( !(o instanceof ReachabilitySet) ) {
 355       return false;
 356     }
 357
 358     ReachabilitySet rs = (ReachabilitySet) o;
 359     return possibleReachabilities.equals(rs.possibleReachabilities);
 360   }
 361
 362
 363   private boolean oldHashSet = false;
 364   private int oldHash    = 0;
 365   public int hashCode() {
 366     int currentHash = possibleReachabilities.hashCode();
 367
 368     if( oldHashSet == false ) {
 369       oldHash = currentHash;
 370       oldHashSet = true;
 371     } else {
 372       if( oldHash != currentHash ) {
 373         System.out.println("IF YOU SEE THIS A CANONICAL ReachabilitySet CHANGED");
 374         Integer x = null;
 375         x.toString();
 376       }
 377     }
 378
 379     return currentHash;
 380   }
 381
 382
 383   public String toStringEscapeNewline() {
 384     String s = "[";
 385
 386     Iterator i = this.iterator();
 387     while( i.hasNext() ) {
 388       s += i.next();
 389       if( i.hasNext() ) {
 390         s += "\\n";
 391       }
 392     }
 393
 394     s += "]";
 395     return s;
 396   }
 397
 398   public String toString() {
 399     String s = "[";
 400
 401     Iterator i = this.iterator();
 402     while( i.hasNext() ) {
 403       s += i.next();
 404       if( i.hasNext() ) {
 405         s += "\n";
 406       }
 407     }
 408
 409     s += "]";
 410     return s;
 411   }
 412 }