Robust/src/Analysis/Disjoint/ReachSet.java

   1 package Analysis.Disjoint;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.*;
   7
   8
   9 public class ReachSet extends Canonical {
  10
  11   private HashSet<ReachState> possibleReachabilities;
  12
  13   public ReachSet() {
  14     possibleReachabilities = new HashSet<ReachState>();
  15   }
  16
  17   public ReachSet(ReachState tts) {
  18     this();
  19     assert tts != null;
  20     possibleReachabilities.add(tts);
  21   }
  22
  23   public ReachSet(ReachTuple tt) {
  24     // can't assert before calling this(), it will
  25     // do the checking though
  26     this( new ReachState(tt).makeCanonical() );
  27   }
  28
  29   public ReachSet(HashSet<ReachState> possibleReachabilities) {
  30     assert possibleReachabilities != null;
  31     this.possibleReachabilities = possibleReachabilities;
  32   }
  33
  34   public ReachSet(ReachSet rs) {
  35     assert rs != null;
  36     // okay to clone, ReachSet should be canonical
  37     possibleReachabilities = (HashSet<ReachState>)rs.possibleReachabilities.clone();
  38   }
  39
  40
  41   public ReachSet makeCanonical() {
  42     return (ReachSet) ReachSet.makeCanonical(this);
  43   }
  44
  45   public Iterator<ReachState> 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(ReachState tts) {
  59     assert tts != null;
  60     return possibleReachabilities.contains(tts);
  61   }
  62
  63   public boolean containsWithZeroes(ReachState 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       ReachState ttsThis = (ReachState) itr.next();
  73       if( ttsThis.containsWithZeroes(tts) ) {
  74         return true;
  75       }
  76     }
  77
  78     return false;
  79   }
  80
  81
  82   public boolean containsSuperSet(ReachState tts) {
  83     return containsSuperSet( tts, false );
  84   }
  85
  86   public boolean containsStrictSuperSet(ReachState tts) {
  87     return containsSuperSet( tts, true );
  88   }
  89
  90   public boolean containsSuperSet(ReachState 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       ReachState ttsThis = (ReachState) 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(ReachTuple tt) {
 116     Iterator itr = iterator();
 117     while( itr.hasNext() ) {
 118       ReachState tts = (ReachState) itr.next();
 119       if( tts.containsTuple(tt) ) {
 120         return true;
 121       }
 122     }
 123     return false;
 124   }
 125
 126   public boolean containsTupleSetWithBoth(ReachTuple tt1, ReachTuple tt2) {
 127     Iterator itr = iterator();
 128     while( itr.hasNext() ) {
 129       ReachState tts = (ReachState) itr.next();
 130       if( tts.containsTuple(tt1) && tts.containsTuple(tt2) ) {
 131         return true;
 132       }
 133     }
 134     return false;
 135   }
 136
 137     public static ReachSet factory(ReachState tts) {
 138       CanonicalWrapper cw=new CanonicalWrapper(tts);
 139       if (lookuphash.containsKey(cw))
 140           return (ReachSet)lookuphash.get(cw).b;
 141       ReachSet rs=new ReachSet(tts);
 142       rs=rs.makeCanonical();
 143       cw.b=rs;
 144       lookuphash.put(cw,cw);
 145       return rs;
 146   }
 147
 148     public ReachSet union(ReachState ttsIn) {
 149         ReachOperation ro=new ReachOperation(this, ttsIn);
 150         if (unionhash.containsKey(ro)) {
 151             return (ReachSet) unionhash.get(ro).c;
 152         } else {
 153             ReachSet rsOut = new ReachSet(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 ReachSet union(ReachSet 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 (ReachSet) unionhash.get(ro).c;
 171     else {
 172         ReachSet rsOut = new ReachSet(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 ReachSet intersection(ReachSet 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 (ReachSet) interhash.get(ro).c;
 189     else {
 190         ReachSet rsOut = new ReachSet();
 191         Iterator i = this.iterator();
 192         while( i.hasNext() ) {
 193             ReachState tts = (ReachState) 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 ReachSet add(ReachState tts) {
 206     assert tts != null;
 207     return union(tts);
 208   }
 209
 210   public ReachSet remove(ReachState tts) {
 211     assert tts != null;
 212     ReachSet rsOut = new ReachSet(this);
 213     assert rsOut.possibleReachabilities.remove(tts);
 214     return rsOut.makeCanonical();
 215   }
 216
 217   public ReachSet removeTokenAIfTokenB(ReachTuple ttA,
 218                                               ReachTuple ttB) {
 219     assert ttA != null;
 220     assert ttB != null;
 221
 222     ReachSet rsOut = new ReachSet();
 223
 224     Iterator i = this.iterator();
 225     while( i.hasNext() ) {
 226       ReachState tts = (ReachState) 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 ReachSet applyChangeSet(ChangeSet C, boolean keepSourceState) {
 239     assert C != null;
 240
 241     ReachSet rsOut = new ReachSet();
 242
 243     Iterator i = this.iterator();
 244     while( i.hasNext() ) {
 245       ReachState tts = (ReachState) 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 ChangeSet unionUpArityToChangeSet(ReachSet rsIn) {
 269     assert rsIn != null;
 270
 271     ChangeSet ctsOut = new ChangeSet();
 272
 273     Iterator itrO = this.iterator();
 274     while( itrO.hasNext() ) {
 275       ReachState o = (ReachState) itrO.next();
 276
 277       Iterator itrR = rsIn.iterator();
 278       while( itrR.hasNext() ) {
 279         ReachState r = (ReachState) itrR.next();
 280
 281         ReachState theUnion = new ReachState().makeCanonical();
 282
 283         Iterator itrRelement = r.iterator();
 284         while( itrRelement.hasNext() ) {
 285           ReachTuple ttR = (ReachTuple) itrRelement.next();
 286           ReachTuple ttO = o.containsToken(ttR.getToken() );
 287
 288           if( ttO != null ) {
 289               theUnion = theUnion.union((new ReachState(ttR.unionArity(ttO)).makeCanonical() ) );
 290           } else {
 291               theUnion = theUnion.union((new ReachState(ttR)).makeCanonical() );
 292           }
 293         }
 294
 295         Iterator itrOelement = o.iterator();
 296         while( itrOelement.hasNext() ) {
 297           ReachTuple ttO = (ReachTuple) itrOelement.next();
 298           ReachTuple ttR = theUnion.containsToken(ttO.getToken() );
 299
 300           if( ttR == null ) {
 301               theUnion = theUnion.union(new ReachState(ttO).makeCanonical() );
 302           }
 303         }
 304
 305         if( !theUnion.isEmpty() ) {
 306             ctsOut = ctsOut.union((new ChangeSet(new ChangeTuple(o, theUnion) )).makeCanonical() );
 307         }
 308       }
 309     }
 310
 311     return ctsOut.makeCanonical();
 312   }
 313
 314
 315   public ReachSet ageTokens(AllocSite as) {
 316     assert as != null;
 317
 318     ReachSet rsOut = new ReachSet();
 319
 320     Iterator itrS = this.iterator();
 321     while( itrS.hasNext() ) {
 322       ReachState tts = (ReachState) itrS.next();
 323       rsOut.possibleReachabilities.add(tts.ageTokens(as) );
 324     }
 325
 326     return rsOut.makeCanonical();
 327   }
 328
 329
 330   public ReachSet unshadowTokens(AllocSite as) {
 331     assert as != null;
 332
 333     ReachSet rsOut = new ReachSet();
 334
 335     Iterator itrS = this.iterator();
 336     while( itrS.hasNext() ) {
 337       ReachState tts = (ReachState) itrS.next();
 338       rsOut.possibleReachabilities.add(tts.unshadowTokens(as) );
 339     }
 340
 341     return rsOut.makeCanonical();
 342   }
 343
 344
 345   public ReachSet toShadowTokens(AllocSite as) {
 346     assert as != null;
 347
 348     ReachSet rsOut = new ReachSet();
 349
 350     Iterator itrS = this.iterator();
 351     while( itrS.hasNext() ) {
 352       ReachState tts = (ReachState) itrS.next();
 353       rsOut.possibleReachabilities.add(tts.toShadowTokens(as) );
 354     }
 355
 356     return rsOut.makeCanonical();
 357   }
 358
 359
 360   public ReachSet pruneBy(ReachSet rsIn) {
 361     assert rsIn != null;
 362
 363     ReachSet rsOut = new ReachSet();
 364
 365     Iterator itrB = this.iterator();
 366     while( itrB.hasNext() ) {
 367       ReachState ttsB = (ReachState) itrB.next();
 368
 369       boolean subsetExists = false;
 370
 371       Iterator itrA = rsIn.iterator();
 372       while( itrA.hasNext() && !subsetExists ) {
 373         ReachState ttsA = (ReachState) 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 ReachSet exhaustiveArityCombinations() {
 390       ReachSet rsOut = (new ReachSet()).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       ReachState ttsImprecise = new ReachState().makeCanonical();
 398
 399       Iterator<ReachState> itrThis = this.iterator();
 400       while( itrThis.hasNext() ) {
 401         ReachState 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       ReachState ttsCoordinate = new ReachState().makeCanonical();
 426       Iterator<ReachState> ttsItr = this.iterator();
 427       for( int i = 0; i < numDimensions; ++i ) {
 428         assert ttsItr.hasNext();
 429         ReachState 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 ReachSet) ) {
 461       return false;
 462     }
 463
 464     ReachSet rs = (ReachSet) 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 ReachSet CHANGED");
 480         Integer x = null;
 481         x.toString();
 482       }
 483     }
 484
 485     return currentHash;
 486   }
 487
 488
 489   public String toStringEscNewline( boolean hideSubsetReachability ) {
 490     String s = "[";
 491
 492     Iterator<ReachState> i = this.iterator();
 493     while( i.hasNext() ) {
 494       ReachState 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<ReachState> i = this.iterator();
 521     while( i.hasNext() ) {
 522       ReachState 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 }