Robust/src/Analysis/Disjoint/Canonical.java

   1 package Analysis.Disjoint;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.*;
   7
   8
   9 ////////////////////////////////////////////////
  10 //
  11 //  important note!  The static operations in this class that take
  12 //  canonicals and produce a canonical result sometimes need a
  13 //  "working copy" that IS NOT CANONICAL.  So, even though it isn't
  14 //  perfectly clean, Canonical constructors have been changed from
  15 //  private to protected and they may be used in this file--however,
  16 //  only use a constructor for an object that will mutate during the
  17 //  calculation--use the factory method to obtain everything else!
  18 //  This is CRITICAL!
  19 //
  20 //  What this boils down to is that the only normally constructed
  21 //  object in a canonical operation should be the result out.
  22 //
  23 ////////////////////////////////////////////////
  24
  25
  26 abstract public class Canonical {
  27
  28   // for generating unique canonical values
  29   private static int canonicalCount = 1;
  30
  31   // the canon of objects
  32   private static Hashtable<Canonical, Canonical>
  33   canon =  new Hashtable<Canonical, Canonical>();
  34
  35
  36
  37   public static Canonical makeCanonical(Canonical c) {
  38
  39     if( canon.containsKey(c) ) {
  40       return canon.get(c);
  41     }
  42
  43     c.canonicalValue = canonicalCount;
  44     ++canonicalCount;
  45     canon.put(c, c);
  46     return c;
  47   }
  48
  49
  50   // any Canonical with value still 0 is NOT CANONICAL!
  51   private int canonicalValue = 0;
  52
  53   public boolean isCanonical() {
  54     return canonicalValue != 0;
  55   }
  56
  57   public int getCanonicalValue() {
  58     assert isCanonical();
  59     return canonicalValue;
  60   }
  61
  62
  63
  64   abstract public boolean equalsSpecific(Object o);
  65
  66   final public boolean equals(Object o) {
  67     if( o == null ) {
  68       return false;
  69     }
  70
  71     if( !(o instanceof Canonical) ) {
  72       return false;
  73     }
  74
  75     Canonical c = (Canonical) o;
  76
  77     if( this.canonicalValue == 0 ||
  78         c.canonicalValue == 0
  79         ) {
  80       return equalsSpecific(o);
  81     }
  82
  83     return this.canonicalValue == c.canonicalValue;
  84   }
  85
  86
  87   // canonical objects should never be modified
  88   // and therefore have changing hash codes, so
  89   // use a standard canonical hash code method to
  90   // enforce this, and define a specific hash code
  91   // method each specific subclass should implement
  92   abstract public int hashCodeSpecific();
  93
  94   private boolean hasHash = false;
  95   private int oldHash;
  96   final public int hashCode() {
  97
  98     // the quick mode
  99     if( DisjointAnalysis.releaseMode && hasHash ) {
 100       return oldHash;
 101     }
 102
 103     // the safe mode
 104     int hash = hashCodeSpecific();
 105
 106     if( hasHash ) {
 107       if( oldHash != hash ) {
 108         throw new Error("A CANONICAL HASH CHANGED");
 109       }
 110     } else {
 111       hasHash = true;
 112       oldHash = hash;
 113     }
 114
 115     return hash;
 116   }
 117
 118
 119   // mapping of a non-trivial operation to its result
 120   private static Hashtable<CanonicalOp, Canonical>
 121   op2result = new Hashtable<CanonicalOp, Canonical>();
 122
 123
 124
 125   ///////////////////////////////////////////////////////////
 126   //
 127   //  Everything below are static methods that implement
 128   //  "mutating" operations on Canonical objects by returning
 129   //  the canonical result.  If the op is non-trivial the
 130   //  canonical result is hashed by its defining CononicalOp
 131   //
 132   ///////////////////////////////////////////////////////////
 133
 134
 135   // not weighty, don't bother with caching
 136   public static ReachTuple unionUpArity(ReachTuple rt1,
 137                                         ReachTuple rt2) {
 138     assert rt1 != null;
 139     assert rt2 != null;
 140     assert rt1.isCanonical();
 141     assert rt2.isCanonical();
 142     assert rt1.hrnID          == rt2.hrnID;
 143     assert rt1.isMultiObject  == rt2.isMultiObject;
 144     assert rt1.isOutOfContext == rt2.isOutOfContext;
 145
 146     ReachTuple out;
 147
 148     if( rt1.isMultiObject ) {
 149       // on two non-ZERO arity multi regions, union arity is always
 150       // ZERO-OR-MORE
 151       out = ReachTuple.factory(rt1.hrnID,
 152                                true,
 153                                ReachTuple.ARITY_ZEROORMORE,
 154                                rt1.isOutOfContext);
 155
 156     } else {
 157       // a single object region can only be ARITY_ONE (or zero by
 158       // being absent)
 159       assert rt1.arity == ReachTuple.ARITY_ONE;
 160       out = rt1;
 161     }
 162
 163     assert out.isCanonical();
 164     return out;
 165   }
 166
 167   // not weighty, no caching
 168   public static ReachTuple changeHrnIDTo(ReachTuple rt,
 169                                          Integer hrnIDToChangeTo) {
 170     assert rt              != null;
 171     assert hrnIDToChangeTo != null;
 172
 173     ReachTuple out = ReachTuple.factory(hrnIDToChangeTo,
 174                                         rt.isMultiObject,
 175                                         rt.arity,
 176                                         rt.isOutOfContext
 177                                         );
 178     assert out.isCanonical();
 179     return out;
 180   }
 181
 182
 183   public static ReachState attach(ReachState rs,
 184                                   ExistPredSet preds) {
 185     assert rs    != null;
 186     assert preds != null;
 187     assert rs.isCanonical();
 188     assert preds.isCanonical();
 189
 190     CanonicalOp op =
 191       new CanonicalOp(CanonicalOp.REACHSTATE_ATTACH_EXISTPREDSET,
 192                       rs,
 193                       preds);
 194
 195     Canonical result = op2result.get(op);
 196     if( result != null ) {
 197       return (ReachState) result;
 198     }
 199
 200     // otherwise, no cached result...
 201     ReachState out = new ReachState();
 202     out.reachTuples.addAll(rs.reachTuples);
 203     out.preds = Canonical.join(rs.preds,
 204                                preds);
 205
 206     out = (ReachState) makeCanonical(out);
 207     op2result.put(op, out);
 208     return out;
 209   }
 210
 211
 212   public static ReachState add(ReachState rs,
 213                                ReachTuple rt) {
 214     assert rs != null;
 215     assert rt != null;
 216
 217     // this is only safe if we are certain the new tuple's
 218     // ID doesn't already appear in the reach state
 219     assert rs.containsHrnID(rt.getHrnID(),
 220                             rt.isOutOfContext() ) == null;
 221
 222     CanonicalOp op =
 223       new CanonicalOp(CanonicalOp.REACHSTATE_ADD_REACHTUPLE,
 224                       rs,
 225                       rt);
 226
 227     Canonical result = op2result.get(op);
 228     if( result != null ) {
 229       return (ReachState) result;
 230     }
 231
 232     // otherwise, no cached result...
 233     ReachState out = new ReachState();
 234     out.reachTuples.addAll(rs.reachTuples);
 235     out.reachTuples.add(rt);
 236     out.preds = rs.preds;
 237
 238     out = (ReachState) makeCanonical(out);
 239     op2result.put(op, out);
 240     return out;
 241   }
 242
 243
 244   public static ReachState unionUpArity(ReachState rs1,
 245                                         ReachState rs2) {
 246     assert rs1 != null;
 247     assert rs2 != null;
 248     assert rs1.isCanonical();
 249     assert rs2.isCanonical();
 250
 251     CanonicalOp op =
 252       new CanonicalOp(CanonicalOp.REACHSTATE_UNIONUPARITY_REACHSTATE,
 253                       rs1,
 254                       rs2);
 255
 256     Canonical result = op2result.get(op);
 257     if( result != null ) {
 258       return (ReachState) result;
 259     }
 260
 261     // otherwise, no cached result...
 262     ReachState out = new ReachState();
 263
 264     // first add everything from 1, and if it is
 265     // also in 2 take the union of the tuple arities
 266     Iterator<ReachTuple> rtItr = rs1.iterator();
 267     while( rtItr.hasNext() ) {
 268       ReachTuple rt1 = rtItr.next();
 269       ReachTuple rt2 = rs2.containsHrnID(rt1.getHrnID(),
 270                                          rt1.isOutOfContext()
 271                                          );
 272       if( rt2 != null ) {
 273         out.reachTuples.add(unionUpArity(rt1, rt2) );
 274       } else {
 275         out.reachTuples.add(rt1);
 276       }
 277     }
 278
 279     // then add everything in 2 that wasn't in 1
 280     rtItr = rs2.iterator();
 281     while( rtItr.hasNext() ) {
 282       ReachTuple rt2 = rtItr.next();
 283       ReachTuple rt1 = rs1.containsHrnID(rt2.getHrnID(),
 284                                          rt2.isOutOfContext()
 285                                          );
 286       if( rt1 == null ) {
 287         out.reachTuples.add(rt2);
 288       }
 289     }
 290
 291     out.preds = Canonical.join(rs1.getPreds(),
 292                                rs2.getPreds()
 293                                );
 294
 295     out = (ReachState) makeCanonical(out);
 296     op2result.put(op, out);
 297     return out;
 298   }
 299
 300
 301   public static ReachState addUpArity(ReachState rs,
 302                                       ReachTuple rt) {
 303     assert rs != null;
 304     assert rt != null;
 305
 306     CanonicalOp op =
 307       new CanonicalOp(CanonicalOp.REACHSTATE_ADDUPARITY_REACHTUPLE,
 308                       rs,
 309                       rt);
 310
 311     Canonical result = op2result.get(op);
 312     if( result != null ) {
 313       return (ReachState) result;
 314     }
 315
 316     // otherwise, no cached result...
 317     ReachState out;
 318
 319     // the reason for this add is that we are aware a tuple
 320     // with the same hrnID might already be in the state, so
 321     // if it is we should combine properly
 322     ReachState rtOnly = ReachState.factory(rt);
 323     out = Canonical.unionUpArity(rs, rtOnly);
 324
 325     op2result.put(op, out);
 326     return out;
 327   }
 328
 329
 330   public static ReachState remove(ReachState rs, ReachTuple rt) {
 331     assert rs != null;
 332     assert rt != null;
 333
 334     CanonicalOp op =
 335       new CanonicalOp(CanonicalOp.REACHSTATE_REMOVE_REACHTUPLE,
 336                       rs,
 337                       rt);
 338
 339     Canonical result = op2result.get(op);
 340     if( result != null ) {
 341       return (ReachState) result;
 342     }
 343
 344     // otherwise, no cached result...
 345     ReachState out = new ReachState();
 346     out.reachTuples.addAll(rs.reachTuples);
 347     out.reachTuples.remove(rt);
 348     out.preds = rs.preds;
 349
 350     out = (ReachState) makeCanonical(out);
 351     op2result.put(op, out);
 352     return out;
 353   }
 354
 355
 356   public static ReachState ageTuplesFrom(ReachState rs,
 357                                          AllocSite as) {
 358     assert rs != null;
 359     assert as != null;
 360     assert rs.isCanonical();
 361     assert as.isCanonical();
 362
 363     CanonicalOp op =
 364       new CanonicalOp(CanonicalOp.REACHSTATE_AGETUPLESFROM_ALLOCSITE,
 365                       rs,
 366                       as);
 367
 368     Canonical result = op2result.get(op);
 369     if( result != null ) {
 370       return (ReachState) result;
 371     }
 372
 373     // otherwise, no cached result...
 374     ReachState out = new ReachState();
 375
 376     ReachTuple rtSummary = null;
 377     ReachTuple rtOldest  = null;
 378
 379     Iterator<ReachTuple> rtItr = rs.iterator();
 380     while( rtItr.hasNext() ) {
 381       ReachTuple rt    = rtItr.next();
 382       Integer hrnID = rt.getHrnID();
 383       int age   = as.getAgeCategory(hrnID);
 384
 385       // hrnIDs not associated with
 386       // the site should be left alone, and
 387       // those from this site but out-of-context
 388       if( age == AllocSite.AGE_notInThisSite ||
 389           rt.isOutOfContext()
 390           ) {
 391         out.reachTuples.add(rt);
 392
 393       } else if( age == AllocSite.AGE_summary ) {
 394         // remember the summary tuple, but don't add it
 395         // we may combine it with the oldest tuple
 396         rtSummary = rt;
 397
 398       } else if( age == AllocSite.AGE_oldest ) {
 399         // found an oldest hrnID, again just remember
 400         // for later
 401         rtOldest = rt;
 402
 403       } else {
 404         assert age == AllocSite.AGE_in_I;
 405
 406         Integer I = as.getAge(hrnID);
 407         assert I != null;
 408
 409         // otherwise, we change this hrnID to the
 410         // next older hrnID
 411         Integer hrnIDToChangeTo = as.getIthOldest(I + 1);
 412         ReachTuple rtAged =
 413           Canonical.changeHrnIDTo(rt, hrnIDToChangeTo);
 414         out.reachTuples.add(rtAged);
 415       }
 416     }
 417
 418     // there are four cases to consider here
 419     // 1. we found a summary tuple and no oldest tuple
 420     //    Here we just pass the summary unchanged
 421     // 2. we found an oldest tuple, no summary
 422     //    Make a new, arity-one summary tuple
 423     // 3. we found both a summary and an oldest
 424     //    Merge them by arity
 425     // 4. (not handled) we found neither, do nothing
 426     if( rtSummary != null && rtOldest == null ) {
 427       out.reachTuples.add(rtSummary);
 428
 429     } else if( rtSummary == null && rtOldest != null ) {
 430       out.reachTuples.add(ReachTuple.factory(as.getSummary(),
 431                                              true,   // multi
 432                                              rtOldest.getArity(),
 433                                              false   // out-of-context
 434                                              )
 435                           );
 436
 437     } else if( rtSummary != null && rtOldest != null ) {
 438       out.reachTuples.add(Canonical.unionUpArity(rtSummary,
 439                                                  ReachTuple.factory(as.getSummary(),
 440                                                                     true,    // muli
 441                                                                     rtOldest.getArity(),
 442                                                                     false    // out-of-context
 443                                                                     )
 444                                                  )
 445                           );
 446     }
 447
 448     out.preds = rs.preds;
 449
 450     out = (ReachState) makeCanonical(out);
 451     op2result.put(op, out);
 452     return out;
 453   }
 454
 455
 456
 457   public static ReachSet unionORpreds(ReachSet rs1,
 458                                       ReachSet rs2) {
 459     assert rs1 != null;
 460     assert rs2 != null;
 461     assert rs1.isCanonical();
 462     assert rs2.isCanonical();
 463
 464     CanonicalOp op =
 465       new CanonicalOp(CanonicalOp.REACHSET_UNIONORPREDS_REACHSET,
 466                       rs1,
 467                       rs2);
 468
 469     Canonical result = op2result.get(op);
 470     if( result != null ) {
 471       return (ReachSet) result;
 472     }
 473
 474     // otherwise, no cached result...
 475     ReachSet out = new ReachSet();
 476
 477     // first add everything from 1, and if it was also in 2
 478     // take the OR of the predicates
 479     Iterator<ReachState> stateItr = rs1.iterator();
 480     while( stateItr.hasNext() ) {
 481       ReachState state1 = stateItr.next();
 482       ReachState state2 = rs2.containsIgnorePreds(state1);
 483
 484       if( state2 != null ) {
 485         out.reachStates.add(ReachState.factory(state1.reachTuples,
 486                                                Canonical.join(state1.preds,
 487                                                               state2.preds
 488                                                               )
 489                                                ) );
 490       } else {
 491         out.reachStates.add(state1);
 492       }
 493     }
 494
 495     // then add everything in 2 that wasn't in 1
 496     stateItr = rs2.iterator();
 497     while( stateItr.hasNext() ) {
 498       ReachState state2 = stateItr.next();
 499       ReachState state1 = rs1.containsIgnorePreds(state2);
 500
 501       if( state1 == null ) {
 502         out.reachStates.add(state2);
 503       }
 504     }
 505
 506     out = (ReachSet) makeCanonical(out);
 507     op2result.put(op, out);
 508     return out;
 509   }
 510
 511
 512   // NOTE: when taking the intersection of two reach sets it
 513   // is possible for a reach state to be in both sets, but
 514   // have different predicates.  Conceptully the best new
 515   // predicate is an AND of the source predicates, but to
 516   // avoid eploding states we'll take an overapproximation
 517   // by preferring the predicates from the state in the FIRST
 518   // set, so order of arguments matters
 519   public static ReachSet intersection(ReachSet rs1,
 520                                       ReachSet rs2) {
 521     assert rs1 != null;
 522     assert rs2 != null;
 523     assert rs1.isCanonical();
 524     assert rs2.isCanonical();
 525
 526     CanonicalOp op =
 527       new CanonicalOp(CanonicalOp.REACHSET_INTERSECTION_REACHSET,
 528                       rs1,
 529                       rs2);
 530
 531     Canonical result = op2result.get(op);
 532     if( result != null ) {
 533       return (ReachSet) result;
 534     }
 535
 536     // otherwise, no cached result...
 537     ReachSet out = new ReachSet();
 538     Iterator<ReachState> itr = rs1.iterator();
 539     while( itr.hasNext() ) {
 540       ReachState state1 = (ReachState) itr.next();
 541       ReachState state2 = rs2.containsIgnorePreds(state1);
 542       if( state2 != null ) {
 543         // prefer the predicates on state1, an overapproximation
 544         // of state1 preds AND state2 preds
 545         out.reachStates.add(state1);
 546       }
 547     }
 548
 549     out = (ReachSet) makeCanonical(out);
 550     op2result.put(op, out);
 551     return out;
 552   }
 553
 554
 555   public static ReachSet add(ReachSet rs,
 556                              ReachState state) {
 557     return unionORpreds(rs,
 558                         ReachSet.factory(state)
 559                         );
 560   }
 561
 562   public static ReachSet remove(ReachSet rs,
 563                                 ReachState state) {
 564     assert rs    != null;
 565     assert state != null;
 566     assert rs.isCanonical();
 567     assert state.isCanonical();
 568
 569     CanonicalOp op =
 570       new CanonicalOp(CanonicalOp.REACHSET_REMOVE_REACHSTATE,
 571                       rs,
 572                       state);
 573
 574     Canonical result = op2result.get(op);
 575     if( result != null ) {
 576       return (ReachSet) result;
 577     }
 578
 579     // otherwise, no cached result...
 580     ReachSet out = new ReachSet();
 581     out.reachStates.addAll(rs.reachStates);
 582     out.reachStates.remove(state);
 583
 584     out = (ReachSet) makeCanonical(out);
 585     op2result.put(op, out);
 586     return out;
 587   }
 588
 589
 590   public static ReachSet applyChangeSet(ReachSet rs,
 591                                         ChangeSet cs,
 592                                         boolean keepSourceState) {
 593     assert rs != null;
 594     assert cs != null;
 595     assert rs.isCanonical();
 596     assert cs.isCanonical();
 597
 598     // this primitive operand stuff is just a way to
 599     // ensure distinct inputs to a CanonicalOp
 600     int primOperand;
 601     if( keepSourceState ) {
 602       primOperand = 0x1f;
 603     } else {
 604       primOperand = 0x2b;
 605     }
 606
 607     CanonicalOp op =
 608       new CanonicalOp(CanonicalOp.REACHSET_APPLY_CHANGESET,
 609                       rs,
 610                       cs,
 611                       primOperand);
 612
 613     Canonical result = op2result.get(op);
 614     if( result != null ) {
 615       return (ReachSet) result;
 616     }
 617
 618     // otherwise, no cached result...
 619     ReachSet out = new ReachSet();
 620
 621     Iterator<ReachState> stateItr = rs.iterator();
 622     while( stateItr.hasNext() ) {
 623       ReachState stateOrig = stateItr.next();
 624
 625       boolean changeFound = false;
 626
 627       Iterator<ChangeTuple> ctItr = cs.iterator();
 628       while( ctItr.hasNext() ) {
 629         ChangeTuple ct = ctItr.next();
 630
 631         if( stateOrig.equalsIgnorePreds(ct.getStateToMatch() ) ) {
 632           // use the new state, but the original predicates
 633           ReachState stateNew =
 634             ReachState.factory(ct.getStateToAdd().reachTuples,
 635                                stateOrig.preds
 636                                );
 637           out.reachStates.add(stateNew);
 638           changeFound = true;
 639         }
 640       }
 641
 642       if( keepSourceState || !changeFound ) {
 643         out.reachStates.add(stateOrig);
 644       }
 645     }
 646
 647     out = (ReachSet) makeCanonical(out);
 648     op2result.put(op, out);
 649     return out;
 650   }
 651
 652
 653   public static ChangeSet unionUpArityToChangeSet(ReachSet rsO,
 654                                                   ReachSet rsR) {
 655     assert rsO != null;
 656     assert rsR != null;
 657     assert rsO.isCanonical();
 658     assert rsR.isCanonical();
 659
 660     CanonicalOp op =
 661       new CanonicalOp(CanonicalOp.REACHSET_UNIONTOCHANGESET_REACHSET,
 662                       rsO,
 663                       rsR);
 664
 665     Canonical result = op2result.get(op);
 666     if( result != null ) {
 667       return (ChangeSet) result;
 668     }
 669
 670     // otherwise, no cached result...
 671     ChangeSet out = ChangeSet.factory();
 672
 673     Iterator<ReachState> itrO = rsO.iterator();
 674     while( itrO.hasNext() ) {
 675       ReachState o = itrO.next();
 676
 677       Iterator<ReachState> itrR = rsR.iterator();
 678       while( itrR.hasNext() ) {
 679         ReachState r = itrR.next();
 680
 681         ReachState theUnion = ReachState.factory();
 682
 683         Iterator<ReachTuple> itrRelement = r.iterator();
 684         while( itrRelement.hasNext() ) {
 685           ReachTuple rtR = itrRelement.next();
 686           ReachTuple rtO = o.containsHrnID(rtR.getHrnID(),
 687                                            rtR.isOutOfContext()
 688                                            );
 689           if( rtO != null ) {
 690             theUnion = Canonical.add(theUnion,
 691                                      Canonical.unionUpArity(rtR,
 692                                                             rtO
 693                                                             )
 694                                      );
 695           } else {
 696             theUnion = Canonical.add(theUnion,
 697                                      rtR
 698                                      );
 699           }
 700         }
 701
 702         Iterator<ReachTuple> itrOelement = o.iterator();
 703         while( itrOelement.hasNext() ) {
 704           ReachTuple rtO = itrOelement.next();
 705           ReachTuple rtR = theUnion.containsHrnID(rtO.getHrnID(),
 706                                                   rtO.isOutOfContext()
 707                                                   );
 708           if( rtR == null ) {
 709             theUnion = Canonical.add(theUnion,
 710                                      rtO
 711                                      );
 712           }
 713         }
 714
 715         if( !theUnion.isEmpty() ) {
 716           out =
 717             Canonical.union(out,
 718                             ChangeSet.factory(
 719                               ChangeTuple.factory(o, theUnion)
 720                               )
 721                             );
 722         }
 723       }
 724     }
 725
 726     assert out.isCanonical();
 727     op2result.put(op, out);
 728     return out;
 729   }
 730
 731
 732   public static ReachSet ageTuplesFrom(ReachSet rs,
 733                                        AllocSite as) {
 734     assert rs != null;
 735     assert as != null;
 736     assert rs.isCanonical();
 737     assert as.isCanonical();
 738
 739     CanonicalOp op =
 740       new CanonicalOp(CanonicalOp.REACHSET_AGETUPLESFROM_ALLOCSITE,
 741                       rs,
 742                       as);
 743
 744     Canonical result = op2result.get(op);
 745     if( result != null ) {
 746       return (ReachSet) result;
 747     }
 748
 749     // otherwise, no cached result...
 750     ReachSet out = new ReachSet();
 751
 752     Iterator<ReachState> itrS = rs.iterator();
 753     while( itrS.hasNext() ) {
 754       ReachState state = itrS.next();
 755       out.reachStates.add(Canonical.ageTuplesFrom(state, as) );
 756     }
 757
 758     out = (ReachSet) makeCanonical(out);
 759     op2result.put(op, out);
 760     return out;
 761   }
 762
 763
 764   public static ReachSet pruneBy(ReachSet rsO,
 765                                  ReachSet rsP) {
 766     assert rsO != null;
 767     assert rsP != null;
 768     assert rsO.isCanonical();
 769     assert rsP.isCanonical();
 770
 771     CanonicalOp op =
 772       new CanonicalOp(CanonicalOp.REACHSET_PRUNEBY_REACHSET,
 773                       rsO,
 774                       rsP);
 775
 776     Canonical result = op2result.get(op);
 777     if( result != null ) {
 778       return (ReachSet) result;
 779     }
 780
 781     // otherwise, no cached result...
 782     ReachSet out = new ReachSet();
 783
 784     Iterator<ReachState> itrO = rsO.iterator();
 785     while( itrO.hasNext() ) {
 786       ReachState stateO = itrO.next();
 787
 788       boolean subsetExists = false;
 789
 790       Iterator<ReachState> itrP = rsP.iterator();
 791       while( itrP.hasNext() && !subsetExists ) {
 792         ReachState stateP = itrP.next();
 793
 794         if( stateP.isSubset(stateO) ) {
 795           subsetExists = true;
 796         }
 797       }
 798
 799       if( subsetExists ) {
 800         out.reachStates.add(stateO);
 801       }
 802     }
 803
 804     out = (ReachSet) makeCanonical(out);
 805     op2result.put(op, out);
 806     return out;
 807   }
 808
 809
 810   public static ChangeSet union(ChangeSet cs1,
 811                                 ChangeSet cs2) {
 812     assert cs1 != null;
 813     assert cs2 != null;
 814     assert cs1.isCanonical();
 815     assert cs2.isCanonical();
 816
 817     CanonicalOp op =
 818       new CanonicalOp(CanonicalOp.CHANGESET_UNION_CHANGESET,
 819                       cs1,
 820                       cs2);
 821
 822     Canonical result = op2result.get(op);
 823     if( result != null ) {
 824       return (ChangeSet) result;
 825     }
 826
 827     // otherwise, no cached result...
 828     ChangeSet out = new ChangeSet();
 829     out.changeTuples.addAll(cs1.changeTuples);
 830     out.changeTuples.addAll(cs2.changeTuples);
 831
 832     out = (ChangeSet) makeCanonical(out);
 833     op2result.put(op, out);
 834     return out;
 835   }
 836
 837   public static ChangeSet add(ChangeSet cs,
 838                               ChangeTuple ct) {
 839     assert cs != null;
 840     assert ct != null;
 841     assert cs.isCanonical();
 842     assert ct.isCanonical();
 843
 844     CanonicalOp op =
 845       new CanonicalOp(CanonicalOp.CHANGESET_UNION_CHANGETUPLE,
 846                       cs,
 847                       ct);
 848
 849     Canonical result = op2result.get(op);
 850     if( result != null ) {
 851       return (ChangeSet) result;
 852     }
 853
 854     // otherwise, no cached result...
 855     ChangeSet out = new ChangeSet();
 856     out.changeTuples.addAll(cs.changeTuples);
 857     out.changeTuples.add(ct);
 858
 859     out = (ChangeSet) makeCanonical(out);
 860     op2result.put(op, out);
 861     return out;
 862   }
 863
 864
 865
 866   public static ExistPredSet join(ExistPredSet eps1,
 867                                   ExistPredSet eps2) {
 868
 869     assert eps1 != null;
 870     assert eps2 != null;
 871     assert eps1.isCanonical();
 872     assert eps2.isCanonical();
 873
 874     CanonicalOp op =
 875       new CanonicalOp(CanonicalOp.EXISTPREDSET_JOIN_EXISTPREDSET,
 876                       eps1,
 877                       eps2);
 878
 879     Canonical result = op2result.get(op);
 880     if( result != null ) {
 881       return (ExistPredSet) result;
 882     }
 883
 884     // otherwise, no cached result...
 885     ExistPredSet out = new ExistPredSet();
 886     out.preds.addAll(eps1.preds);
 887     out.preds.addAll(eps2.preds);
 888
 889     out = (ExistPredSet) makeCanonical(out);
 890     op2result.put(op, out);
 891     return out;
 892   }
 893
 894   public static ExistPredSet add(ExistPredSet eps,
 895                                  ExistPred ep) {
 896
 897
 898     assert eps != null;
 899     assert ep  != null;
 900     assert eps.isCanonical();
 901     assert ep.isCanonical();
 902
 903     CanonicalOp op =
 904       new CanonicalOp(CanonicalOp.EXISTPREDSET_ADD_EXISTPRED,
 905                       eps,
 906                       ep);
 907
 908     Canonical result = op2result.get(op);
 909     if( result != null ) {
 910       return (ExistPredSet) result;
 911     }
 912
 913     // otherwise, no cached result...
 914     ExistPredSet out = new ExistPredSet();
 915     out.preds.addAll(eps.preds);
 916     out.preds.add(ep);
 917
 918     out = (ExistPredSet) makeCanonical(out);
 919     op2result.put(op, out);
 920     return out;
 921   }
 922
 923
 924   public static ReachSet toCallerContext(ReachSet rs,
 925                                          AllocSite as) {
 926     assert rs != null;
 927     assert as != null;
 928     assert rs.isCanonical();
 929     assert as.isCanonical();
 930
 931     CanonicalOp op =
 932       new CanonicalOp(CanonicalOp.REACHSET_TOCALLERCONTEXT_ALLOCSITE,
 933                       rs,
 934                       as);
 935
 936     Canonical result = op2result.get(op);
 937     if( result != null ) {
 938       return (ReachSet) result;
 939     }
 940
 941     // otherwise, no cached result...
 942     ReachSet out = ReachSet.factory();
 943     Iterator<ReachState> itr = rs.iterator();
 944     while( itr.hasNext() ) {
 945       ReachState state = itr.next();
 946       out = Canonical.unionORpreds(out,
 947                                    Canonical.toCallerContext(state, as)
 948                                    );
 949     }
 950
 951     assert out.isCanonical();
 952     op2result.put(op, out);
 953     return out;
 954   }
 955
 956
 957   public static ReachSet toCallerContext(ReachState state,
 958                                          AllocSite as) {
 959     assert state != null;
 960     assert as    != null;
 961     assert state.isCanonical();
 962     assert as.isCanonical();
 963
 964     CanonicalOp op =
 965       new CanonicalOp(CanonicalOp.REACHSTATE_TOCALLERCONTEXT_ALLOCSITE,
 966                       state,
 967                       as);
 968
 969     Canonical result = op2result.get(op);
 970     if( result != null ) {
 971       return (ReachSet) result;
 972     }
 973
 974     // otherwise, no cached result...
 975     ReachSet out = ReachSet.factory();
 976
 977     // this method returns a ReachSet instead of a ReachState
 978     // because the companion method, toCallee, translates
 979     // symbols many-to-one, so state->state
 980     // but this method does an ~inverse mapping, one-to-many
 981     // so one state can split into a set of branched states
 982
 983     // 0    -> -0
 984     // 1    -> -1
 985     // 2S   -> -2S
 986     // 2S*  -> -2S*
 987     //
 988     // 0?   -> 0
 989     // 1?   -> 1
 990     // 2S?  -> 2S
 991     //      -> 0?
 992     //      -> 1?
 993     //      -> 2S?
 994     // 2S?* -> {2S*, 2S?*}
 995
 996     boolean found2Sooc = false;
 997
 998     ReachState baseState = ReachState.factory();
 999
1000     Iterator<ReachTuple> itr = state.iterator();
1001     while( itr.hasNext() ) {
1002       ReachTuple rt = itr.next();
1003
1004       int age = as.getAgeCategory(rt.getHrnID() );
1005
1006       if( age == AllocSite.AGE_notInThisSite ) {
1007         // things not from the site just go back in
1008         baseState = Canonical.addUpArity(baseState, rt);
1009
1010       } else if( age == AllocSite.AGE_summary ) {
1011
1012         if( rt.isOutOfContext() ) {
1013           // if its out-of-context, we only deal here with the ZERO-OR-MORE
1014           // arity, if ARITY-ONE we'll branch the base state after the loop
1015           if( rt.getArity() == ReachTuple.ARITY_ZEROORMORE ) {
1016             // add two overly conservative symbols to reach state (PUNTING)
1017
1018             baseState = Canonical.addUpArity(baseState,
1019                                              ReachTuple.factory(as.getSummary(),
1020                                                                 true,   // multi
1021                                                                 ReachTuple.ARITY_ZEROORMORE,
1022                                                                 false   // out-of-context
1023                                                                 )
1024                                              );
1025
1026             baseState = Canonical.addUpArity(baseState,
1027                                              ReachTuple.factory(as.getSummary(),
1028                                                                 true,   // multi
1029                                                                 ReachTuple.ARITY_ZEROORMORE,
1030                                                                 true    // out-of-context
1031                                                                 )
1032                                              );
1033           } else {
1034             assert rt.getArity() == ReachTuple.ARITY_ONE;
1035             found2Sooc = true;
1036           }
1037
1038         } else {
1039           // the in-context just becomes shadow
1040           baseState = Canonical.addUpArity(baseState,
1041                                            ReachTuple.factory(as.getSummaryShadow(),
1042                                                               true,   // multi
1043                                                               rt.getArity(),
1044                                                               false    // out-of-context
1045                                                               )
1046                                            );
1047         }
1048
1049
1050       } else {
1051         // otherwise age is in range [0, k]
1052         Integer I = as.getAge(rt.getHrnID() );
1053         assert I != null;
1054         assert !rt.isMultiObject();
1055         assert rt.getArity() == ReachTuple.ARITY_ONE;
1056
1057         if( rt.isOutOfContext() ) {
1058           // becomes the in-context version
1059           baseState = Canonical.addUpArity(baseState,
1060                                            ReachTuple.factory(rt.getHrnID(),
1061                                                               false,   // multi
1062                                                               ReachTuple.ARITY_ONE,
1063                                                               false    // out-of-context
1064                                                               )
1065                                            );
1066
1067         } else {
1068           // otherwise the ith symbol becomes shadowed
1069           baseState = Canonical.addUpArity(baseState,
1070                                            ReachTuple.factory(-rt.getHrnID(),
1071                                                               false,   // multi
1072                                                               ReachTuple.ARITY_ONE,
1073                                                               false    // out-of-context
1074                                                               )
1075                                            );
1076         }
1077       }
1078     }
1079
1080     // now either make branches if we have 2S?, or
1081     // the current baseState is the only state we need
1082     if( found2Sooc ) {
1083       // make a branch with every possibility of the one-to-many
1084       // mapping for 2S? appended to the baseState
1085       out = Canonical.add(out,
1086                           Canonical.addUpArity(baseState,
1087                                                ReachTuple.factory(as.getSummary(),
1088                                                                   true,    // multi
1089                                                                   ReachTuple.ARITY_ONE,
1090                                                                   false     // out-of-context
1091                                                                   )
1092                                                )
1093                           );
1094
1095       out = Canonical.add(out,
1096                           Canonical.addUpArity(baseState,
1097                                                ReachTuple.factory(as.getSummary(),
1098                                                                   true,    // multi
1099                                                                   ReachTuple.ARITY_ONE,
1100                                                                   true     // out-of-context
1101                                                                   )
1102                                                )
1103                           );
1104
1105       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1106         out = Canonical.add(out,
1107                             Canonical.addUpArity(baseState,
1108                                                  ReachTuple.factory(as.getIthOldest(i),
1109                                                                     false,    // multi
1110                                                                     ReachTuple.ARITY_ONE,
1111                                                                     true     // out-of-context
1112                                                                     )
1113                                                  )
1114                             );
1115       }
1116
1117     } else {
1118       // just use current baseState
1119       out = Canonical.add(out,
1120                           baseState);
1121     }
1122
1123
1124     assert out.isCanonical();
1125     op2result.put(op, out);
1126     return out;
1127   }
1128
1129
1130   public static ReachSet unshadow(ReachSet rs,
1131                                   AllocSite as) {
1132     assert rs != null;
1133     assert as != null;
1134     assert rs.isCanonical();
1135     assert as.isCanonical();
1136
1137     CanonicalOp op =
1138       new CanonicalOp(CanonicalOp.REACHSET_UNSHADOW_ALLOCSITE,
1139                       rs,
1140                       as);
1141
1142     Canonical result = op2result.get(op);
1143     if( result != null ) {
1144       return (ReachSet) result;
1145     }
1146
1147     // otherwise, no cached result...
1148     ReachSet out = ReachSet.factory();
1149     Iterator<ReachState> itr = rs.iterator();
1150     while( itr.hasNext() ) {
1151       ReachState state = itr.next();
1152       out = Canonical.add(out,
1153                           Canonical.unshadow(state, as)
1154                           );
1155     }
1156
1157     assert out.isCanonical();
1158     op2result.put(op, out);
1159     return out;
1160   }
1161
1162   public static ReachState unshadow(ReachState state,
1163                                     AllocSite as) {
1164     assert state != null;
1165     assert as    != null;
1166     assert state.isCanonical();
1167     assert as.isCanonical();
1168
1169     CanonicalOp op =
1170       new CanonicalOp(CanonicalOp.REACHSTATE_UNSHADOW_ALLOCSITE,
1171                       state,
1172                       as);
1173
1174     Canonical result = op2result.get(op);
1175     if( result != null ) {
1176       return (ReachState) result;
1177     }
1178
1179     // this is the current mapping, where 0, 1, 2S were allocated
1180     // in the current context, 0?, 1? and 2S? were allocated in a
1181     // previous context, and we're translating to a future context
1182     //
1183     // -0   -> 0
1184     // -1   -> 1
1185     // -2S  -> 2S
1186
1187     // otherwise, no cached result...
1188     ReachState out = ReachState.factory();
1189     Iterator<ReachTuple> itr = state.iterator();
1190     while( itr.hasNext() ) {
1191       ReachTuple rt = itr.next();
1192
1193       int age = as.getShadowAgeCategory(rt.getHrnID() );
1194
1195       if( age == AllocSite.SHADOWAGE_notInThisSite ) {
1196         // things not from the site just go back in
1197         out = Canonical.addUpArity(out, rt);
1198
1199       } else {
1200         assert !rt.isOutOfContext();
1201
1202         // otherwise unshadow it
1203         out = Canonical.addUpArity(out,
1204                                    ReachTuple.factory(-rt.getHrnID(),
1205                                                       rt.isMultiObject(),
1206                                                       rt.getArity(),
1207                                                       false
1208                                                       )
1209                                    );
1210       }
1211     }
1212
1213     out = Canonical.attach(out,
1214                            state.getPreds()
1215                            );
1216
1217     assert out.isCanonical();
1218     op2result.put(op, out);
1219     return out;
1220   }
1221
1222
1223
1224   public static ReachState changePredsTo(ReachState rs,
1225                                          ExistPredSet preds) {
1226     assert rs != null;
1227     assert rs.isCanonical();
1228
1229     CanonicalOp op =
1230       new CanonicalOp(CanonicalOp.REACHSTATE_CHANGEPREDSTO_EXISTPREDSET,
1231                       rs,
1232                       preds);
1233
1234     Canonical result = op2result.get(op);
1235     if( result != null ) {
1236       return (ReachState) result;
1237     }
1238
1239     // otherwise, no cached result...
1240     ReachState out = new ReachState();
1241
1242     // just remake state with the true predicate attached
1243     out.reachTuples.addAll(rs.reachTuples);
1244     out.preds = preds;
1245
1246     out = (ReachState) makeCanonical(out);
1247     op2result.put(op, out);
1248     return out;
1249   }
1250
1251
1252   public static ReachSet changePredsTo(ReachSet rs,
1253                                        ExistPredSet preds) {
1254     assert rs != null;
1255     assert rs.isCanonical();
1256
1257     CanonicalOp op =
1258       new CanonicalOp(CanonicalOp.REACHSET_CHANGEPREDSTO_EXISTPREDSET,
1259                       rs,
1260                       preds);
1261
1262     Canonical result = op2result.get(op);
1263     if( result != null ) {
1264       return (ReachSet) result;
1265     }
1266
1267     // otherwise, no cached result...
1268     ReachSet out = ReachSet.factory();
1269     Iterator<ReachState> itr = rs.iterator();
1270     while( itr.hasNext() ) {
1271       ReachState state = itr.next();
1272       out = Canonical.add(out,
1273                           Canonical.changePredsTo(state,
1274                                                   preds
1275                                                   )
1276                           );
1277     }
1278
1279     out = (ReachSet) makeCanonical(out);
1280     op2result.put(op, out);
1281     return out;
1282   }
1283
1284
1285   public static Taint attach(Taint t,
1286                              ExistPredSet preds) {
1287     assert t     != null;
1288     assert preds != null;
1289     assert t.isCanonical();
1290     assert preds.isCanonical();
1291
1292     CanonicalOp op =
1293       new CanonicalOp(CanonicalOp.TAINT_ATTACH_EXISTPREDSET,
1294                       t,
1295                       preds);
1296
1297     Canonical result = op2result.get(op);
1298     if( result != null ) {
1299       return (Taint) result;
1300     }
1301
1302     // otherwise, no cached result...
1303     Taint out = new Taint(t);
1304     out.preds = Canonical.join(t.preds,
1305                                preds);
1306
1307     out = (Taint) makeCanonical(out);
1308     op2result.put(op, out);
1309     return out;
1310   }
1311
1312   public static TaintSet add(TaintSet ts,
1313                              Taint t) {
1314     assert ts != null;
1315     assert t  != null;
1316     assert ts.isCanonical();
1317     assert t.isCanonical();
1318
1319     CanonicalOp op =
1320       new CanonicalOp(CanonicalOp.TAINTSET_ADD_TAINT,
1321                       ts,
1322                       t);
1323
1324     Canonical result = op2result.get(op);
1325     if( result != null ) {
1326       return (TaintSet) result;
1327     }
1328
1329     // otherwise, no cached result...
1330     TaintSet out = new TaintSet();
1331     out.taints.addAll(ts.taints);
1332     out.taints.add(t);
1333
1334     out = (TaintSet) makeCanonical(out);
1335     op2result.put(op, out);
1336     return out;
1337   }
1338
1339
1340   public static TaintSet addPTR(TaintSet ts,
1341                                 Taint t) {
1342     return add(ts, t);
1343   }
1344
1345   public static TaintSet union(TaintSet ts1,
1346                                TaintSet ts2) {
1347     assert ts1 != null;
1348     assert ts2 != null;
1349     assert ts1.isCanonical();
1350     assert ts2.isCanonical();
1351
1352     CanonicalOp op =
1353       new CanonicalOp(CanonicalOp.TAINTSET_UNION_TAINTSET,
1354                       ts1,
1355                       ts2);
1356
1357     Canonical result = op2result.get(op);
1358     if( result != null ) {
1359       return (TaintSet) result;
1360     }
1361
1362     // otherwise, no cached result...
1363     TaintSet out = new TaintSet();
1364
1365     // first add everything from 1, and if it was also in 2
1366     // take the OR of the predicates
1367     Iterator<Taint> tItr = ts1.iterator();
1368     while( tItr.hasNext() ) {
1369       Taint t1 = tItr.next();
1370       Taint t2 = ts2.containsIgnorePreds(t1);
1371
1372       if( t2 != null ) {
1373         Taint tNew = new Taint(t1);
1374         tNew.preds = Canonical.join(t1.preds,
1375                                     t2.preds
1376                                     );
1377         tNew = (Taint) makeCanonical(tNew);
1378         out.taints.add(tNew);
1379       } else {
1380         out.taints.add(t1);
1381       }
1382     }
1383
1384     // then add everything in 2 that wasn't in 1
1385     tItr = ts2.iterator();
1386     while( tItr.hasNext() ) {
1387       Taint t2 = tItr.next();
1388       Taint t1 = ts1.containsIgnorePreds(t2);
1389
1390       if( t1 == null ) {
1391         out.taints.add(t2);
1392       }
1393     }
1394
1395     out = (TaintSet) makeCanonical(out);
1396     op2result.put(op, out);
1397     return out;
1398   }
1399
1400   public static TaintSet unionPTR(TaintSet ts1,
1401                                   TaintSet ts2) {
1402     assert ts1 != null;
1403     assert ts2 != null;
1404     assert ts1.isCanonical();
1405     assert ts2.isCanonical();
1406
1407     CanonicalOp op =
1408       new CanonicalOp(CanonicalOp.TAINTSET_UNION_TAINTSET,
1409                       ts1,
1410                       ts2);
1411
1412     Canonical result = op2result.get(op);
1413     if( result != null ) {
1414       return (TaintSet) result;
1415     }
1416
1417     // otherwise, no cached result...
1418     TaintSet out = new TaintSet();
1419
1420     out.taints.addAll(ts1.taints);
1421     out.taints.addAll(ts2.taints);
1422     out= (TaintSet) Canonical.makeCanonical(out);
1423     op2result.put(op, out);
1424     return out;
1425   }
1426
1427   public static TaintSet unionORpreds(TaintSet ts1,
1428                                       TaintSet ts2) {
1429     assert ts1 != null;
1430     assert ts2 != null;
1431     assert ts1.isCanonical();
1432     assert ts2.isCanonical();
1433
1434     CanonicalOp op =
1435       new CanonicalOp(CanonicalOp.TAINTSET_UNIONORPREDS_TAINTSET,
1436                       ts1,
1437                       ts2);
1438
1439     Canonical result = op2result.get(op);
1440     if( result != null ) {
1441       return (TaintSet) result;
1442     }
1443
1444     // otherwise, no cached result...
1445     TaintSet out = new TaintSet();
1446
1447     // first add everything from 1, and if it was also in 2
1448     // take the OR of the predicates
1449     Iterator<Taint> tItr = ts1.iterator();
1450     while( tItr.hasNext() ) {
1451       Taint t1 = tItr.next();
1452       Taint t2 = ts2.containsIgnorePreds(t1);
1453
1454       if( t2 != null ) {
1455         Taint tNew = new Taint(t1);
1456         tNew.preds = Canonical.join(t1.preds,
1457                                     t2.preds
1458                                     );
1459         tNew = (Taint) makeCanonical(tNew);
1460         out.taints.add(tNew);
1461       } else {
1462         out.taints.add(t1);
1463       }
1464     }
1465
1466     // then add everything in 2 that wasn't in 1
1467     tItr = ts2.iterator();
1468     while( tItr.hasNext() ) {
1469       Taint t2 = tItr.next();
1470       Taint t1 = ts1.containsIgnorePreds(t2);
1471
1472       if( t1 == null ) {
1473         out.taints.add(t2);
1474       }
1475     }
1476
1477     out = (TaintSet) makeCanonical(out);
1478     op2result.put(op, out);
1479     return out;
1480   }
1481
1482
1483   // BOO, HISS! SESE (rblock) operand does NOT extend
1484   // Canonical, so we can't cache this op by its
1485   // canonical arguments--THINK ABOUT A BETTER WAY!
1486   public static TaintSet removeInContextTaints(TaintSet ts,
1487                                                FlatSESEEnterNode sese) {
1488     assert ts != null;
1489     assert ts.isCanonical();
1490     assert sese != null;
1491
1492     // NEVER a cached result... (cry)
1493     TaintSet out = new TaintSet();
1494
1495     Iterator<Taint> tItr = ts.iterator();
1496     while( tItr.hasNext() ) {
1497       Taint t = tItr.next();
1498
1499       // what is allowed through?  stall site taints always
1500       // go through, anything where rblock doesn't match is
1501       // unaffected, and if the taint has a non-empty predicate
1502       // it is out of context so it should go through, too
1503       if( t.getSESE() == null ||
1504           !t.getSESE().equals(sese) ||
1505           !t.getPreds().isEmpty()
1506           ) {
1507         out.taints.add(t);
1508       }
1509     }
1510
1511     out = (TaintSet) makeCanonical(out);
1512     //op2result.put( op, out ); CRY CRY
1513     return out;
1514   }
1515
1516   // BOO, HISS! SESE (rblock) operand does NOT extend
1517   // Canonical, so we can't cache this op by its
1518   // canonical arguments--THINK ABOUT A BETTER WAY!
1519   public static TaintSet removeSESETaints(TaintSet ts,
1520                                           Set<FlatSESEEnterNode> seseSet) {
1521     assert ts != null;
1522     assert ts.isCanonical();
1523
1524     // NEVER a cached result... (cry)
1525     TaintSet out = new TaintSet();
1526
1527     Iterator<Taint> tItr = ts.iterator();
1528     while( tItr.hasNext() ) {
1529       Taint t = tItr.next();
1530
1531       // what is allowed through?  stall site taints always
1532       // go through, anything where rblock doesn't match is
1533       // unaffected, and if the taint has a non-empty predicate
1534       // it is out of context so it should go through, too
1535       if( t.getSESE() == null ||
1536           !seseSet.contains(t)) {
1537         out.taints.add(t);
1538       }
1539     }
1540
1541     out = (TaintSet) makeCanonical(out);
1542     //op2result.put( op, out ); CRY CRY
1543     return out;
1544   }
1545
1546   public static TaintSet removeInContextTaintsNP(TaintSet ts,
1547                                                  FlatSESEEnterNode sese) {
1548     assert ts != null;
1549     assert ts.isCanonical();
1550
1551     // NEVER a cached result... (cry)
1552     TaintSet out = new TaintSet();
1553
1554     Iterator<Taint> tItr = ts.iterator();
1555     while( tItr.hasNext() ) {
1556       Taint t = tItr.next();
1557
1558       // what is allowed through?  stall site taints always
1559       // go through, anything where rblock doesn't match is
1560       // unaffected, and if the taint has a non-empty predicate
1561       // it is out of context so it should go through, too
1562       if( t.getSESE()!=null && t.getSESE()!=sese) {
1563         out.taints.add(t);
1564       }
1565     }
1566
1567     out = (TaintSet) makeCanonical(out);
1568     return out;
1569   }
1570
1571   public static TaintSet removeStallSiteTaints(TaintSet ts) {
1572     assert ts != null;
1573     assert ts.isCanonical();
1574
1575     CanonicalOp op =
1576       new CanonicalOp(CanonicalOp.TAINTSET_REMOVESTALLSITETAINTS,
1577                       ts,
1578                       ts);
1579
1580     Canonical result = op2result.get(op);
1581     if( result != null ) {
1582       return (TaintSet) result;
1583     }
1584
1585     // otherwise, no cached result...
1586     TaintSet out = new TaintSet();
1587
1588     Iterator<Taint> tItr = ts.iterator();
1589     while( tItr.hasNext() ) {
1590       Taint t = tItr.next();
1591
1592       // only take non-stall site taints onward
1593       if( t.getStallSite() == null ) {
1594         out.taints.add(t);
1595       }
1596     }
1597
1598     out = (TaintSet) makeCanonical(out);
1599     op2result.put(op, out);
1600     return out;
1601   }
1602
1603
1604   public static Taint changePredsTo(Taint t,
1605                                     ExistPredSet preds) {
1606     assert t != null;
1607     assert t.isCanonical();
1608
1609     CanonicalOp op =
1610       new CanonicalOp(CanonicalOp.TAINT_CHANGEPREDSTO_EXISTPREDSET,
1611                       t,
1612                       preds);
1613
1614     Canonical result = op2result.get(op);
1615     if( result != null ) {
1616       return (Taint) result;
1617     }
1618
1619     // otherwise, no cached result...
1620     Taint out = new Taint(t.sese,
1621                           t.stallSite,
1622                           t.var,
1623                           t.allocSite,
1624                           t.fnDefined,
1625                           preds
1626                           );
1627
1628     out = (Taint) makeCanonical(out);
1629     op2result.put(op, out);
1630     return out;
1631   }
1632
1633
1634   public static TaintSet changePredsTo(TaintSet ts,
1635                                        ExistPredSet preds) {
1636     assert ts != null;
1637     assert ts.isCanonical();
1638
1639     CanonicalOp op =
1640       new CanonicalOp(CanonicalOp.TAINTSET_CHANGEPREDSTO_EXISTPREDSET,
1641                       ts,
1642                       preds);
1643
1644     Canonical result = op2result.get(op);
1645     if( result != null ) {
1646       return (TaintSet) result;
1647     }
1648
1649     // otherwise, no cached result...
1650     TaintSet out = TaintSet.factory();
1651     Iterator<Taint> itr = ts.iterator();
1652     while( itr.hasNext() ) {
1653       Taint t = itr.next();
1654       out = Canonical.add(out,
1655                           Canonical.changePredsTo(t, preds)
1656                           );
1657     }
1658
1659     out = (TaintSet) makeCanonical(out);
1660     op2result.put(op, out);
1661     return out;
1662   }
1663
1664
1665
1666   // BOO, HISS! FlatNode operand does NOT extend
1667   // Canonical, so we can't cache this op by its
1668   // canonical arguments--THINK ABOUT A BETTER WAY!
1669   public static Taint changeWhereDefined(Taint t,
1670                                          FlatNode pp) {
1671     assert t != null;
1672     assert t.isCanonical();
1673
1674     // never a cached result...
1675     Taint out = new Taint(t.sese,
1676                           t.stallSite,
1677                           t.var,
1678                           t.allocSite,
1679                           pp,
1680                           t.preds
1681                           );
1682
1683     out = (Taint) makeCanonical(out);
1684     //op2result.put( op, out ); CRY CRY
1685     return out;
1686   }
1687
1688   // BOO, HISS! FlatNode operand does NOT extend
1689   // Canonical, so we can't cache this op by its
1690   // canonical arguments--THINK ABOUT A BETTER WAY!
1691   public static TaintSet changeWhereDefined(TaintSet ts,
1692                                             FlatNode pp) {
1693     assert ts != null;
1694     assert ts.isCanonical();
1695
1696     // never a cached result...
1697     TaintSet out = TaintSet.factory();
1698     Iterator<Taint> itr = ts.iterator();
1699     while( itr.hasNext() ) {
1700       Taint t = itr.next();
1701       out = Canonical.add(out,
1702                           Canonical.changeWhereDefined(t, pp)
1703                           );
1704     }
1705
1706     out = (TaintSet) makeCanonical(out);
1707     //op2result.put( op, out ); CRY CRY
1708     return out;
1709   }
1710
1711 }