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   public static TaintSet union( TaintSet ts1,
1340                                 TaintSet ts2 ) {
1341     assert ts1 != null;
1342     assert ts2 != null;
1343     assert ts1.isCanonical();
1344     assert ts2.isCanonical();
1345
1346     CanonicalOp op =
1347       new CanonicalOp( CanonicalOp.TAINTSET_UNION_TAINTSET,
1348                        ts1,
1349                        ts2 );
1350
1351     Canonical result = op2result.get( op );
1352     if( result != null ) {
1353       return (TaintSet) result;
1354     }
1355
1356     // otherwise, no cached result...
1357     TaintSet out = new TaintSet();
1358
1359     // first add everything from 1, and if it was also in 2
1360     // take the OR of the predicates
1361     Iterator<Taint> tItr = ts1.iterator();
1362     while( tItr.hasNext() ) {
1363       Taint t1 = tItr.next();
1364       Taint t2 = ts2.containsIgnorePreds( t1 );
1365
1366       if( t2 != null ) {
1367         Taint tNew = new Taint( t1 );
1368         tNew.preds = Canonical.join( t1.preds,
1369                                      t2.preds
1370                                      );
1371         tNew = (Taint) makeCanonical( tNew );
1372         out.taints.add( tNew );
1373       } else {
1374         out.taints.add( t1 );
1375       }
1376     }
1377
1378     // then add everything in 2 that wasn't in 1
1379     tItr = ts2.iterator();
1380     while( tItr.hasNext() ) {
1381       Taint t2 = tItr.next();
1382       Taint t1 = ts1.containsIgnorePreds( t2 );
1383
1384       if( t1 == null ) {
1385         out.taints.add( t2 );
1386       }
1387     }
1388
1389     out = (TaintSet) makeCanonical( out );
1390     op2result.put( op, out );
1391     return out;
1392   }
1393
1394   public static TaintSet unionORpreds( TaintSet ts1,
1395                                        TaintSet ts2 ) {
1396     assert ts1 != null;
1397     assert ts2 != null;
1398     assert ts1.isCanonical();
1399     assert ts2.isCanonical();
1400
1401     CanonicalOp op =
1402       new CanonicalOp( CanonicalOp.TAINTSET_UNIONORPREDS_TAINTSET,
1403                        ts1,
1404                        ts2 );
1405
1406     Canonical result = op2result.get( op );
1407     if( result != null ) {
1408       return (TaintSet) result;
1409     }
1410
1411     // otherwise, no cached result...
1412     TaintSet out = new TaintSet();
1413
1414     // first add everything from 1, and if it was also in 2
1415     // take the OR of the predicates
1416     Iterator<Taint> tItr = ts1.iterator();
1417     while( tItr.hasNext() ) {
1418       Taint t1 = tItr.next();
1419       Taint t2 = ts2.containsIgnorePreds( t1 );
1420
1421       if( t2 != null ) {
1422         Taint tNew = new Taint( t1 );
1423         tNew.preds = Canonical.join( t1.preds,
1424                                      t2.preds
1425                                      );
1426         tNew = (Taint) makeCanonical( tNew );
1427         out.taints.add( tNew );
1428       } else {
1429         out.taints.add( t1 );
1430       }
1431     }
1432
1433     // then add everything in 2 that wasn't in 1
1434     tItr = ts2.iterator();
1435     while( tItr.hasNext() ) {
1436       Taint t2 = tItr.next();
1437       Taint t1 = ts1.containsIgnorePreds( t2 );
1438
1439       if( t1 == null ) {
1440         out.taints.add( t2 );
1441       }
1442     }
1443
1444     out = (TaintSet) makeCanonical( out );
1445     op2result.put( op, out );
1446     return out;
1447   }
1448
1449
1450   // BOO, HISS! SESE (rblock) operand does NOT extend
1451   // Canonical, so we can't cache this op by its
1452   // canonical arguments--THINK ABOUT A BETTER WAY!
1453   public static TaintSet removeInContextTaints( TaintSet          ts,
1454                                                 FlatSESEEnterNode sese ) {
1455     assert ts != null;
1456     assert ts.isCanonical();
1457     assert sese != null;
1458
1459     // NEVER a cached result... (cry)
1460     TaintSet out = new TaintSet();
1461
1462     Iterator<Taint> tItr = ts.iterator();
1463     while( tItr.hasNext() ) {
1464       Taint t = tItr.next();
1465
1466       // what is allowed through?  stall site taints always
1467       // go through, anything where rblock doesn't match is
1468       // unaffected, and if the taint has a non-empty predicate
1469       // it is out of context so it should go through, too
1470       if( t.getSESE() == null ||
1471           !t.getSESE().equals( sese ) ||
1472           !t.getPreds().isEmpty()
1473           ) {
1474         out.taints.add( t );
1475       }
1476     }
1477
1478     out = (TaintSet) makeCanonical( out );
1479     //op2result.put( op, out ); CRY CRY
1480     return out;
1481   }
1482
1483   public static TaintSet removeStallSiteTaints( TaintSet ts ) {
1484     assert ts != null;
1485     assert ts.isCanonical();
1486
1487     CanonicalOp op =
1488       new CanonicalOp( CanonicalOp.TAINTSET_REMOVESTALLSITETAINTS,
1489                        ts,
1490                        ts );
1491
1492     Canonical result = op2result.get( op );
1493     if( result != null ) {
1494       return (TaintSet) result;
1495     }
1496
1497     // otherwise, no cached result...
1498     TaintSet out = new TaintSet();
1499
1500     Iterator<Taint> tItr = ts.iterator();
1501     while( tItr.hasNext() ) {
1502       Taint t = tItr.next();
1503
1504       // only take non-stall site taints onward
1505       if( t.getStallSite() == null ) {
1506         out.taints.add( t );
1507       }
1508     }
1509
1510     out = (TaintSet) makeCanonical( out );
1511     op2result.put( op, out );
1512     return out;
1513   }
1514
1515
1516   public static Taint changePredsTo( Taint        t,
1517                                      ExistPredSet preds ) {
1518     assert t != null;
1519     assert t.isCanonical();
1520
1521     CanonicalOp op =
1522       new CanonicalOp( CanonicalOp.TAINT_CHANGEPREDSTO_EXISTPREDSET,
1523                        t,
1524                        preds );
1525
1526     Canonical result = op2result.get( op );
1527     if( result != null ) {
1528       return (Taint) result;
1529     }
1530
1531     // otherwise, no cached result...
1532     Taint out = new Taint( t.sese,
1533                            t.stallSite,
1534                            t.var,
1535                            t.allocSite,
1536                            t.fnDefined,
1537                            preds
1538                            );
1539
1540     out = (Taint) makeCanonical( out );
1541     op2result.put( op, out );
1542     return out;
1543   }
1544
1545
1546   public static TaintSet changePredsTo( TaintSet     ts,
1547                                         ExistPredSet preds ) {
1548     assert ts != null;
1549     assert ts.isCanonical();
1550
1551     CanonicalOp op =
1552       new CanonicalOp( CanonicalOp.TAINTSET_CHANGEPREDSTO_EXISTPREDSET,
1553                        ts,
1554                        preds );
1555
1556     Canonical result = op2result.get( op );
1557     if( result != null ) {
1558       return (TaintSet) result;
1559     }
1560
1561     // otherwise, no cached result...
1562     TaintSet out = TaintSet.factory();
1563     Iterator<Taint> itr = ts.iterator();
1564     while( itr.hasNext() ) {
1565       Taint t = itr.next();
1566       out = Canonical.add( out,
1567                            Canonical.changePredsTo( t, preds )
1568                            );
1569     }
1570
1571     out = (TaintSet) makeCanonical( out );
1572     op2result.put( op, out );
1573     return out;
1574   }
1575 }