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) ReachabilitySet.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
  82   public boolean containsSuperSet(TokenTupleSet tts) {
  83     return containsSuperSet(tts, false);
  84   }
  85
  86   public boolean containsStrictSuperSet(TokenTupleSet tts) {
  87     return containsSuperSet(tts, true);
  88   }
  89
  90   public boolean containsSuperSet(TokenTupleSet tts, boolean strict) {
  91     assert tts != null;
  92
  93     if( !strict && possibleReachabilities.contains(tts) ) {
  94       return true;
  95     }
  96
  97     Iterator itr = iterator();
  98     while( itr.hasNext() ) {
  99       TokenTupleSet ttsThis = (TokenTupleSet) itr.next();
 100       if( strict ) {
 101         if( !tts.equals(ttsThis) && tts.isSubset(ttsThis) ) {
 102           return true;
 103         }
 104       } else {
 105         if( tts.isSubset(ttsThis) ) {
 106           return true;
 107         }
 108       }
 109     }
 110
 111     return false;
 112   }
 113
 114
 115   public boolean containsTuple(TokenTuple tt) {
 116     Iterator itr = iterator();
 117     while( itr.hasNext() ) {
 118       TokenTupleSet tts = (TokenTupleSet) itr.next();
 119       if( tts.containsTuple(tt) ) {
 120         return true;
 121       }
 122     }
 123     return false;
 124   }
 125
 126   public boolean containsTupleSetWithBoth(TokenTuple tt1, TokenTuple tt2) {
 127     Iterator itr = iterator();
 128     while( itr.hasNext() ) {
 129       TokenTupleSet tts = (TokenTupleSet) itr.next();
 130       if( tts.containsTuple(tt1) && tts.containsTuple(tt2) ) {
 131         return true;
 132       }
 133     }
 134     return false;
 135   }
 136
 137   public static ReachabilitySet factory(TokenTupleSet tts) {
 138     CanonicalWrapper cw=new CanonicalWrapper(tts);
 139     if (lookuphash.containsKey(cw))
 140       return (ReachabilitySet)lookuphash.get(cw).b;
 141     ReachabilitySet rs=new ReachabilitySet(tts);
 142     rs=rs.makeCanonical();
 143     cw.b=rs;
 144     lookuphash.put(cw,cw);
 145     return rs;
 146   }
 147
 148   public ReachabilitySet union(TokenTupleSet ttsIn) {
 149     ReachOperation ro=new ReachOperation(this, ttsIn);
 150     if (unionhash.containsKey(ro)) {
 151       return (ReachabilitySet) unionhash.get(ro).c;
 152     } else {
 153       ReachabilitySet rsOut = new ReachabilitySet(this);
 154       rsOut.possibleReachabilities.add(ttsIn);
 155       ro.c=rsOut=rsOut.makeCanonical();
 156       unionhash.put(ro,ro);
 157       return rsOut;
 158     }
 159   }
 160
 161
 162   public ReachabilitySet union(ReachabilitySet rsIn) {
 163     //    assert rsIn != null;
 164
 165     //    assert can.containsKey(this);
 166     //    assert can.containsKey(rsIn);
 167
 168     ReachOperation ro=new ReachOperation(this, rsIn);
 169     if (unionhash.containsKey(ro))
 170       return (ReachabilitySet) unionhash.get(ro).c;
 171     else {
 172       ReachabilitySet rsOut = new ReachabilitySet(this);
 173       rsOut.possibleReachabilities.addAll(rsIn.possibleReachabilities);
 174       ro.c=rsOut=rsOut.makeCanonical();
 175       unionhash.put(ro, ro);
 176       return rsOut;
 177     }
 178   }
 179
 180   public ReachabilitySet intersection(ReachabilitySet rsIn) {
 181     //    assert rsIn != null;
 182
 183     //    assert can.containsKey(this);
 184     //    assert can.containsKey(rsIn);
 185
 186     ReachOperation ro=new ReachOperation(this, rsIn);
 187     if (interhash.containsKey(ro))
 188       return (ReachabilitySet) interhash.get(ro).c;
 189     else {
 190       ReachabilitySet rsOut = new ReachabilitySet();
 191       Iterator i = this.iterator();
 192       while( i.hasNext() ) {
 193         TokenTupleSet tts = (TokenTupleSet) i.next();
 194         if( rsIn.possibleReachabilities.contains(tts) ) {
 195           rsOut.possibleReachabilities.add(tts);
 196         }
 197       }
 198       ro.c=rsOut=rsOut.makeCanonical();
 199       interhash.put(ro,ro);
 200       return rsOut;
 201     }
 202   }
 203
 204
 205   public ReachabilitySet add(TokenTupleSet tts) {
 206     assert tts != null;
 207     return union(tts);
 208   }
 209
 210   public ReachabilitySet remove(TokenTupleSet tts) {
 211     assert tts != null;
 212     ReachabilitySet rsOut = new ReachabilitySet(this);
 213     assert rsOut.possibleReachabilities.remove(tts);
 214     return rsOut.makeCanonical();
 215   }
 216
 217   public ReachabilitySet removeTokenAIfTokenB(TokenTuple ttA,
 218                                               TokenTuple ttB) {
 219     assert ttA != null;
 220     assert ttB != null;
 221
 222     ReachabilitySet rsOut = new ReachabilitySet();
 223
 224     Iterator i = this.iterator();
 225     while( i.hasNext() ) {
 226       TokenTupleSet tts = (TokenTupleSet) i.next();
 227       if( tts.containsTuple(ttB) ) {
 228         rsOut.possibleReachabilities.add(tts.remove(ttA) );
 229       } else {
 230         rsOut.possibleReachabilities.add(tts);
 231       }
 232     }
 233
 234     return rsOut.makeCanonical();
 235   }
 236
 237
 238   public ReachabilitySet applyChangeSet(ChangeTupleSet C, boolean keepSourceState) {
 239     assert C != null;
 240
 241     ReachabilitySet rsOut = new ReachabilitySet();
 242
 243     Iterator i = this.iterator();
 244     while( i.hasNext() ) {
 245       TokenTupleSet tts = (TokenTupleSet) i.next();
 246
 247       boolean changeFound = false;
 248
 249       Iterator<ChangeTuple> itrC = C.iterator();
 250       while( itrC.hasNext() ) {
 251         ChangeTuple c = itrC.next();
 252
 253         if( tts.equals(c.getSetToMatch() ) ) {
 254           rsOut.possibleReachabilities.add(c.getSetToAdd() );
 255           changeFound = true;
 256         }
 257       }
 258
 259       if( keepSourceState || !changeFound ) {
 260         rsOut.possibleReachabilities.add(tts);
 261       }
 262     }
 263
 264     return rsOut.makeCanonical();
 265   }
 266
 267
 268   public ChangeTupleSet unionUpArityToChangeSet(ReachabilitySet rsIn) {
 269     assert rsIn != null;
 270
 271     ChangeTupleSet ctsOut = new ChangeTupleSet();
 272
 273     Iterator itrO = this.iterator();
 274     while( itrO.hasNext() ) {
 275       TokenTupleSet o = (TokenTupleSet) itrO.next();
 276
 277       Iterator itrR = rsIn.iterator();
 278       while( itrR.hasNext() ) {
 279         TokenTupleSet r = (TokenTupleSet) itrR.next();
 280
 281         TokenTupleSet theUnion = new TokenTupleSet().makeCanonical();
 282
 283         Iterator itrRelement = r.iterator();
 284         while( itrRelement.hasNext() ) {
 285           TokenTuple ttR = (TokenTuple) itrRelement.next();
 286           TokenTuple ttO = o.containsToken(ttR.getToken() );
 287
 288           if( ttO != null ) {
 289             theUnion = theUnion.union((new TokenTupleSet(ttR.unionArity(ttO)).makeCanonical() ) );
 290           } else {
 291             theUnion = theUnion.union((new TokenTupleSet(ttR)).makeCanonical() );
 292           }
 293         }
 294
 295         Iterator itrOelement = o.iterator();
 296         while( itrOelement.hasNext() ) {
 297           TokenTuple ttO = (TokenTuple) itrOelement.next();
 298           TokenTuple ttR = theUnion.containsToken(ttO.getToken() );
 299
 300           if( ttR == null ) {
 301             theUnion = theUnion.union(new TokenTupleSet(ttO).makeCanonical() );
 302           }
 303         }
 304
 305         if( !theUnion.isEmpty() ) {
 306           ctsOut = ctsOut.union((new ChangeTupleSet(new ChangeTuple(o, theUnion) )).makeCanonical() );
 307         }
 308       }
 309     }
 310
 311     return ctsOut.makeCanonical();
 312   }
 313
 314
 315   public ReachabilitySet ageTokens(AllocationSite as) {
 316     assert as != null;
 317
 318     ReachabilitySet rsOut = new ReachabilitySet();
 319
 320     Iterator itrS = this.iterator();
 321     while( itrS.hasNext() ) {
 322       TokenTupleSet tts = (TokenTupleSet) itrS.next();
 323       rsOut.possibleReachabilities.add(tts.ageTokens(as) );
 324     }
 325
 326     return rsOut.makeCanonical();
 327   }
 328
 329
 330   public ReachabilitySet unshadowTokens(AllocationSite as) {
 331     assert as != null;
 332
 333     ReachabilitySet rsOut = new ReachabilitySet();
 334
 335     Iterator itrS = this.iterator();
 336     while( itrS.hasNext() ) {
 337       TokenTupleSet tts = (TokenTupleSet) itrS.next();
 338       rsOut.possibleReachabilities.add(tts.unshadowTokens(as) );
 339     }
 340
 341     return rsOut.makeCanonical();
 342   }
 343
 344
 345   public ReachabilitySet toShadowTokens(AllocationSite as) {
 346     assert as != null;
 347
 348     ReachabilitySet rsOut = new ReachabilitySet();
 349
 350     Iterator itrS = this.iterator();
 351     while( itrS.hasNext() ) {
 352       TokenTupleSet tts = (TokenTupleSet) itrS.next();
 353       rsOut.possibleReachabilities.add(tts.toShadowTokens(as) );
 354     }
 355
 356     return rsOut.makeCanonical();
 357   }
 358
 359
 360   public ReachabilitySet pruneBy(ReachabilitySet rsIn) {
 361     assert rsIn != null;
 362
 363     ReachabilitySet rsOut = new ReachabilitySet();
 364
 365     Iterator itrB = this.iterator();
 366     while( itrB.hasNext() ) {
 367       TokenTupleSet ttsB = (TokenTupleSet) itrB.next();
 368
 369       boolean subsetExists = false;
 370
 371       Iterator itrA = rsIn.iterator();
 372       while( itrA.hasNext() && !subsetExists ) {
 373         TokenTupleSet ttsA = (TokenTupleSet) itrA.next();
 374
 375         if( ttsA.isSubset(ttsB) ) {
 376           subsetExists = true;
 377         }
 378       }
 379
 380       if( subsetExists ) {
 381         rsOut.possibleReachabilities.add(ttsB);
 382       }
 383     }
 384
 385     return rsOut.makeCanonical();
 386   }
 387
 388
 389   public ReachabilitySet exhaustiveArityCombinations() {
 390     ReachabilitySet rsOut = (new ReachabilitySet()).makeCanonical();
 391
 392     int numDimensions = this.possibleReachabilities.size();
 393
 394     if( numDimensions > 3 ) {
 395       // for problems that are too big, punt and use less
 396       // precise arity for reachability information
 397       TokenTupleSet ttsImprecise = new TokenTupleSet().makeCanonical();
 398
 399       Iterator<TokenTupleSet> itrThis = this.iterator();
 400       while( itrThis.hasNext() ) {
 401         TokenTupleSet ttsUnit = itrThis.next();
 402         ttsImprecise = ttsImprecise.unionUpArity(ttsUnit.makeArityZeroOrMore() );
 403       }
 404
 405       //rsOut = this.union( ttsImprecise );
 406       rsOut = rsOut.union(ttsImprecise);
 407       return rsOut;
 408     }
 409
 410     // add an extra digit to detect termination
 411     int[] digits = new int[numDimensions+1];
 412
 413     int minArity = 0;
 414     int maxArity = 2;
 415
 416     // start with the minimum possible coordinate
 417     for( int i = 0; i < numDimensions+1; ++i ) {
 418       digits[i] = minArity;
 419     }
 420
 421     // and stop when the highest-ordered axis rolls above the minimum
 422     while( digits[numDimensions] == minArity ) {
 423
 424       // spit out a "coordinate" made from these digits
 425       TokenTupleSet ttsCoordinate = new TokenTupleSet().makeCanonical();
 426       Iterator<TokenTupleSet> ttsItr = this.iterator();
 427       for( int i = 0; i < numDimensions; ++i ) {
 428         assert ttsItr.hasNext();
 429         TokenTupleSet ttsUnit = ttsItr.next();
 430         for( int j = 0; j < digits[i]; ++j ) {
 431           ttsCoordinate = ttsCoordinate.unionUpArity(ttsUnit);
 432         }
 433       }
 434       rsOut = rsOut.add(ttsCoordinate.makeCanonical() );
 435
 436       // increment
 437       for( int i = 0; i < numDimensions+1; ++i ) {
 438         digits[i]++;
 439
 440         if( digits[i] > maxArity ) {
 441           // this axis reached its max, so roll it back to min and increment next higher digit
 442           digits[i] = minArity;
 443
 444         } else {
 445           // this axis did not reach its max so we just enumerated a new unique coordinate, stop
 446           break;
 447         }
 448       }
 449     }
 450
 451     return rsOut.makeCanonical();
 452   }
 453
 454
 455   public boolean equals(Object o) {
 456     if( o == null ) {
 457       return false;
 458     }
 459
 460     if( !(o instanceof ReachabilitySet) ) {
 461       return false;
 462     }
 463
 464     ReachabilitySet rs = (ReachabilitySet) o;
 465     return possibleReachabilities.equals(rs.possibleReachabilities);
 466   }
 467
 468
 469   private boolean oldHashSet = false;
 470   private int oldHash    = 0;
 471   public int hashCode() {
 472     int currentHash = possibleReachabilities.hashCode();
 473
 474     if( oldHashSet == false ) {
 475       oldHash = currentHash;
 476       oldHashSet = true;
 477     } else {
 478       if( oldHash != currentHash ) {
 479         System.out.println("IF YOU SEE THIS A CANONICAL ReachabilitySet CHANGED");
 480         Integer x = null;
 481         x.toString();
 482       }
 483     }
 484
 485     return currentHash;
 486   }
 487
 488
 489   public String toStringEscapeNewline(boolean hideSubsetReachability) {
 490     String s = "[";
 491
 492     Iterator<TokenTupleSet> i = this.iterator();
 493     while( i.hasNext() ) {
 494       TokenTupleSet tts = i.next();
 495
 496       // skip this if there is a superset already
 497       if( hideSubsetReachability &&
 498           containsStrictSuperSet(tts) ) {
 499         continue;
 500       }
 501
 502       s += tts;
 503       if( i.hasNext() ) {
 504         s += "\\n";
 505       }
 506     }
 507
 508     s += "]";
 509     return s;
 510   }
 511
 512
 513   public String toString() {
 514     return toString(false);
 515   }
 516
 517   public String toString(boolean hideSubsetReachability) {
 518     String s = "[";
 519
 520     Iterator<TokenTupleSet> i = this.iterator();
 521     while( i.hasNext() ) {
 522       TokenTupleSet tts = i.next();
 523
 524       // skip this if there is a superset already
 525       if( hideSubsetReachability &&
 526           containsStrictSuperSet(tts) ) {
 527         continue;
 528       }
 529
 530       s += tts;
 531       if( i.hasNext() ) {
 532         s += "\n";
 533       }
 534     }
 535
 536     s += "]";
 537     return s;
 538   }
 539 }