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 remove( ReachState rs, ReachTuple rt ) {
 302     assert rs != null;
 303     assert rt != null;
 304
 305     CanonicalOp op =
 306       new CanonicalOp( CanonicalOp.REACHSTATE_REMOVE_REACHTUPLE,
 307                        rs,
 308                        rt );
 309
 310     Canonical result = op2result.get( op );
 311     if( result != null ) {
 312       return (ReachState) result;
 313     }
 314
 315     // otherwise, no cached result...
 316     ReachState out = new ReachState();
 317     out.reachTuples.addAll( rs.reachTuples );
 318     out.reachTuples.remove( rt );
 319     out.preds = rs.preds;
 320
 321     out = (ReachState) makeCanonical( out );
 322     op2result.put( op, out );
 323     return out;
 324   }
 325
 326
 327   public static ReachState ageTuplesFrom( ReachState rs,
 328                                           AllocSite  as ) {
 329     assert rs != null;
 330     assert as != null;
 331     assert rs.isCanonical();
 332     assert as.isCanonical();
 333
 334     CanonicalOp op =
 335       new CanonicalOp( CanonicalOp.REACHSTATE_AGETUPLESFROM_ALLOCSITE,
 336                        rs,
 337                        as );
 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
 347     ReachTuple rtSummary = null;
 348     ReachTuple rtOldest  = null;
 349
 350     Iterator<ReachTuple> rtItr = rs.iterator();
 351     while( rtItr.hasNext() ) {
 352       ReachTuple rt    = rtItr.next();
 353       Integer    hrnID = rt.getHrnID();
 354       int        age   = as.getAgeCategory( hrnID );
 355
 356       // hrnIDs not associated with
 357       // the site should be left alone, and
 358       // those from this site but out-of-context
 359       if( age == AllocSite.AGE_notInThisSite ||
 360           rt.isOutOfContext()
 361           ) {
 362         out.reachTuples.add( rt );
 363
 364       } else if( age == AllocSite.AGE_summary ) {
 365         // remember the summary tuple, but don't add it
 366         // we may combine it with the oldest tuple
 367         rtSummary = rt;
 368
 369       } else if( age == AllocSite.AGE_oldest ) {
 370         // found an oldest hrnID, again just remember
 371         // for later
 372         rtOldest = rt;
 373
 374       } else {
 375         assert age == AllocSite.AGE_in_I;
 376
 377         Integer I = as.getAge( hrnID );
 378         assert I != null;
 379
 380         // otherwise, we change this hrnID to the
 381         // next older hrnID
 382         Integer hrnIDToChangeTo = as.getIthOldest( I + 1 );
 383         ReachTuple rtAged =
 384           Canonical.changeHrnIDTo( rt, hrnIDToChangeTo );
 385         out.reachTuples.add( rtAged );
 386       }
 387     }
 388
 389     // there are four cases to consider here
 390     // 1. we found a summary tuple and no oldest tuple
 391     //    Here we just pass the summary unchanged
 392     // 2. we found an oldest tuple, no summary
 393     //    Make a new, arity-one summary tuple
 394     // 3. we found both a summary and an oldest
 395     //    Merge them by arity
 396     // 4. (not handled) we found neither, do nothing
 397     if( rtSummary != null && rtOldest == null ) {
 398       out.reachTuples.add( rtSummary );
 399
 400     } else if( rtSummary == null && rtOldest != null ) {
 401       out.reachTuples.add( ReachTuple.factory( as.getSummary(),
 402                                                true, // multi
 403                                                rtOldest.getArity(),
 404                                                false // out-of-context
 405                                                )
 406                            );
 407
 408     } else if( rtSummary != null && rtOldest != null ) {
 409       out.reachTuples.add( Canonical.unionUpArity( rtSummary,
 410                                                    ReachTuple.factory( as.getSummary(),
 411                                                                        true, // muli
 412                                                                        rtOldest.getArity(),
 413                                                                        false // out-of-context
 414                                                                        )
 415                                                    )
 416                            );
 417     }
 418
 419     out.preds = rs.preds;
 420
 421     out = (ReachState) makeCanonical( out );
 422     op2result.put( op, out );
 423     return out;
 424   }
 425
 426
 427
 428   public static ReachSet unionORpreds( ReachSet rs1,
 429                                        ReachSet rs2 ) {
 430     assert rs1 != null;
 431     assert rs2 != null;
 432     assert rs1.isCanonical();
 433     assert rs2.isCanonical();
 434
 435     CanonicalOp op =
 436       new CanonicalOp( CanonicalOp.REACHSET_UNIONORPREDS_REACHSET,
 437                        rs1,
 438                        rs2 );
 439
 440     Canonical result = op2result.get( op );
 441     if( result != null ) {
 442       return (ReachSet) result;
 443     }
 444
 445     // otherwise, no cached result...
 446     ReachSet out = new ReachSet();
 447
 448     // first add everything from 1, and if it was also in 2
 449     // take the OR of the predicates
 450     Iterator<ReachState> stateItr = rs1.iterator();
 451     while( stateItr.hasNext() ) {
 452       ReachState state1 = stateItr.next();
 453       ReachState state2 = rs2.containsIgnorePreds( state1 );
 454
 455       if( state2 != null ) {
 456         out.reachStates.add( ReachState.factory( state1.reachTuples,
 457                                                  Canonical.join( state1.preds,
 458                                                                  state2.preds
 459                                                                  )
 460                                                  ) );
 461       } else {
 462         out.reachStates.add( state1 );
 463       }
 464     }
 465
 466     // then add everything in 2 that wasn't in 1
 467     stateItr = rs2.iterator();
 468     while( stateItr.hasNext() ) {
 469       ReachState state2 = stateItr.next();
 470       ReachState state1 = rs1.containsIgnorePreds( state2 );
 471
 472       if( state1 == null ) {
 473         out.reachStates.add( state2 );
 474       }
 475     }
 476
 477     out = (ReachSet) makeCanonical( out );
 478     op2result.put( op, out );
 479     return out;
 480   }
 481
 482
 483   // NOTE: when taking the intersection of two reach sets it
 484   // is possible for a reach state to be in both sets, but
 485   // have different predicates.  Conceptully the best new
 486   // predicate is an AND of the source predicates, but to
 487   // avoid eploding states we'll take an overapproximation
 488   // by preferring the predicates from the state in the FIRST
 489   // set, so order of arguments matters
 490   public static ReachSet intersection( ReachSet rs1,
 491                                        ReachSet rs2 ) {
 492     assert rs1 != null;
 493     assert rs2 != null;
 494     assert rs1.isCanonical();
 495     assert rs2.isCanonical();
 496
 497     CanonicalOp op =
 498       new CanonicalOp( CanonicalOp.REACHSET_INTERSECTION_REACHSET,
 499                        rs1,
 500                        rs2 );
 501
 502     Canonical result = op2result.get( op );
 503     if( result != null ) {
 504       return (ReachSet) result;
 505     }
 506
 507     // otherwise, no cached result...
 508     ReachSet out = new ReachSet();
 509     Iterator<ReachState> itr = rs1.iterator();
 510     while( itr.hasNext() ) {
 511       ReachState state1 = (ReachState) itr.next();
 512       ReachState state2 = rs2.containsIgnorePreds( state1 );
 513       if( state2 != null ) {
 514         // prefer the predicates on state1, an overapproximation
 515         // of state1 preds AND state2 preds
 516         out.reachStates.add( state1 );
 517       }
 518     }
 519
 520     out = (ReachSet) makeCanonical( out );
 521     op2result.put( op, out );
 522     return out;
 523   }
 524
 525
 526   public static ReachSet add( ReachSet   rs,
 527                               ReachState state ) {
 528     return unionORpreds( rs,
 529                          ReachSet.factory( state )
 530                          );
 531   }
 532
 533   public static ReachSet remove( ReachSet   rs,
 534                                  ReachState state ) {
 535     assert rs    != null;
 536     assert state != null;
 537     assert rs.isCanonical();
 538     assert state.isCanonical();
 539
 540     CanonicalOp op =
 541       new CanonicalOp( CanonicalOp.REACHSET_REMOVE_REACHSTATE,
 542                        rs,
 543                        state );
 544
 545     Canonical result = op2result.get( op );
 546     if( result != null ) {
 547       return (ReachSet) result;
 548     }
 549
 550     // otherwise, no cached result...
 551     ReachSet out = new ReachSet();
 552     out.reachStates.addAll( rs.reachStates );
 553     out.reachStates.remove( state );
 554
 555     out = (ReachSet) makeCanonical( out );
 556     op2result.put( op, out );
 557     return out;
 558   }
 559
 560
 561   public static ReachSet applyChangeSet( ReachSet  rs,
 562                                          ChangeSet cs,
 563                                          boolean   keepSourceState ) {
 564     assert rs != null;
 565     assert cs != null;
 566     assert rs.isCanonical();
 567     assert cs.isCanonical();
 568
 569     // this primitive operand stuff is just a way to
 570     // ensure distinct inputs to a CanonicalOp
 571     int primOperand;
 572     if( keepSourceState ) {
 573       primOperand = 0x1f;
 574     } else {
 575       primOperand = 0x2b;
 576     }
 577
 578     CanonicalOp op =
 579       new CanonicalOp( CanonicalOp.REACHSET_APPLY_CHANGESET,
 580                        rs,
 581                        cs,
 582                        primOperand );
 583
 584     Canonical result = op2result.get( op );
 585     if( result != null ) {
 586       return (ReachSet) result;
 587     }
 588
 589     // otherwise, no cached result...
 590     ReachSet out = new ReachSet();
 591
 592     Iterator<ReachState> stateItr = rs.iterator();
 593     while( stateItr.hasNext() ) {
 594       ReachState stateOrig = stateItr.next();
 595
 596       boolean changeFound = false;
 597
 598       Iterator<ChangeTuple> ctItr = cs.iterator();
 599       while( ctItr.hasNext() ) {
 600         ChangeTuple ct = ctItr.next();
 601
 602         if( stateOrig.equalsIgnorePreds( ct.getStateToMatch() ) ) {
 603           // use the new state, but the original predicates
 604           ReachState stateNew =
 605             ReachState.factory( ct.getStateToAdd().reachTuples,
 606                                 stateOrig.preds
 607                                 );
 608           out.reachStates.add( stateNew );
 609           changeFound = true;
 610         }
 611       }
 612
 613       if( keepSourceState || !changeFound ) {
 614         out.reachStates.add( stateOrig );
 615       }
 616     }
 617
 618     out = (ReachSet) makeCanonical( out );
 619     op2result.put( op, out );
 620     return out;
 621   }
 622
 623
 624   public static ChangeSet unionUpArityToChangeSet( ReachSet rsO,
 625                                                    ReachSet rsR ) {
 626     assert rsO != null;
 627     assert rsR != null;
 628     assert rsO.isCanonical();
 629     assert rsR.isCanonical();
 630
 631     CanonicalOp op =
 632       new CanonicalOp( CanonicalOp.REACHSET_UNIONTOCHANGESET_REACHSET,
 633                        rsO,
 634                        rsR );
 635
 636     Canonical result = op2result.get( op );
 637     if( result != null ) {
 638       return (ChangeSet) result;
 639     }
 640
 641     // otherwise, no cached result...
 642     ChangeSet out = ChangeSet.factory();
 643
 644     Iterator<ReachState> itrO = rsO.iterator();
 645     while( itrO.hasNext() ) {
 646       ReachState o = itrO.next();
 647
 648       Iterator<ReachState> itrR = rsR.iterator();
 649       while( itrR.hasNext() ) {
 650         ReachState r = itrR.next();
 651
 652         ReachState theUnion = ReachState.factory();
 653
 654         Iterator<ReachTuple> itrRelement = r.iterator();
 655         while( itrRelement.hasNext() ) {
 656           ReachTuple rtR = itrRelement.next();
 657           ReachTuple rtO = o.containsHrnID( rtR.getHrnID(),
 658                                             rtR.isOutOfContext()
 659                                             );
 660           if( rtO != null ) {
 661             theUnion = Canonical.add( theUnion,
 662                                       Canonical.unionUpArity( rtR,
 663                                                               rtO
 664                                                               )
 665                                       );
 666           } else {
 667             theUnion = Canonical.add( theUnion,
 668                                       rtR
 669                                       );
 670           }
 671         }
 672
 673         Iterator<ReachTuple> itrOelement = o.iterator();
 674         while( itrOelement.hasNext() ) {
 675           ReachTuple rtO = itrOelement.next();
 676           ReachTuple rtR = theUnion.containsHrnID( rtO.getHrnID(),
 677                                                    rtO.isOutOfContext()
 678                                                    );
 679           if( rtR == null ) {
 680             theUnion = Canonical.add( theUnion,
 681                                       rtO
 682                                       );
 683           }
 684         }
 685
 686         if( !theUnion.isEmpty() ) {
 687           out =
 688             Canonical.union( out,
 689                              ChangeSet.factory(
 690                                                ChangeTuple.factory( o, theUnion )
 691                                                 )
 692                              );
 693         }
 694       }
 695     }
 696
 697     assert out.isCanonical();
 698     op2result.put( op, out );
 699     return out;
 700   }
 701
 702
 703   public static ReachSet ageTuplesFrom( ReachSet  rs,
 704                                         AllocSite as ) {
 705     assert rs != null;
 706     assert as != null;
 707     assert rs.isCanonical();
 708     assert as.isCanonical();
 709
 710     CanonicalOp op =
 711       new CanonicalOp( CanonicalOp.REACHSET_AGETUPLESFROM_ALLOCSITE,
 712                        rs,
 713                        as );
 714
 715     Canonical result = op2result.get( op );
 716     if( result != null ) {
 717       return (ReachSet) result;
 718     }
 719
 720     // otherwise, no cached result...
 721     ReachSet out = new ReachSet();
 722
 723     Iterator<ReachState> itrS = rs.iterator();
 724     while( itrS.hasNext() ) {
 725       ReachState state = itrS.next();
 726       out.reachStates.add( Canonical.ageTuplesFrom( state, as ) );
 727     }
 728
 729     out = (ReachSet) makeCanonical( out );
 730     op2result.put( op, out );
 731     return out;
 732   }
 733
 734
 735   public static ReachSet pruneBy( ReachSet rsO,
 736                                   ReachSet rsP ) {
 737     assert rsO != null;
 738     assert rsP != null;
 739     assert rsO.isCanonical();
 740     assert rsP.isCanonical();
 741
 742     CanonicalOp op =
 743       new CanonicalOp( CanonicalOp.REACHSET_PRUNEBY_REACHSET,
 744                        rsO,
 745                        rsP );
 746
 747     Canonical result = op2result.get( op );
 748     if( result != null ) {
 749       return (ReachSet) result;
 750     }
 751
 752     // otherwise, no cached result...
 753     ReachSet out = new ReachSet();
 754
 755     Iterator<ReachState> itrO = rsO.iterator();
 756     while( itrO.hasNext() ) {
 757       ReachState stateO = itrO.next();
 758
 759       boolean subsetExists = false;
 760
 761       Iterator<ReachState> itrP = rsP.iterator();
 762       while( itrP.hasNext() && !subsetExists ) {
 763         ReachState stateP = itrP.next();
 764
 765         if( stateP.isSubset( stateO ) ) {
 766           subsetExists = true;
 767         }
 768       }
 769
 770       if( subsetExists ) {
 771         out.reachStates.add( stateO );
 772       }
 773     }
 774
 775     out = (ReachSet) makeCanonical( out );
 776     op2result.put( op, out );
 777     return out;
 778   }
 779
 780
 781   public static ChangeSet union( ChangeSet cs1,
 782                                  ChangeSet cs2 ) {
 783     assert cs1 != null;
 784     assert cs2 != null;
 785     assert cs1.isCanonical();
 786     assert cs2.isCanonical();
 787
 788     CanonicalOp op =
 789       new CanonicalOp( CanonicalOp.CHANGESET_UNION_CHANGESET,
 790                        cs1,
 791                        cs2 );
 792
 793     Canonical result = op2result.get( op );
 794     if( result != null ) {
 795       return (ChangeSet) result;
 796     }
 797
 798     // otherwise, no cached result...
 799     ChangeSet out = new ChangeSet();
 800     out.changeTuples.addAll( cs1.changeTuples );
 801     out.changeTuples.addAll( cs2.changeTuples );
 802
 803     out = (ChangeSet) makeCanonical( out );
 804     op2result.put( op, out );
 805     return out;
 806   }
 807
 808   public static ChangeSet add( ChangeSet   cs,
 809                                ChangeTuple ct ) {
 810     assert cs != null;
 811     assert ct != null;
 812     assert cs.isCanonical();
 813     assert ct.isCanonical();
 814
 815     CanonicalOp op =
 816       new CanonicalOp( CanonicalOp.CHANGESET_UNION_CHANGETUPLE,
 817                        cs,
 818                        ct );
 819
 820     Canonical result = op2result.get( op );
 821     if( result != null ) {
 822       return (ChangeSet) result;
 823     }
 824
 825     // otherwise, no cached result...
 826     ChangeSet out = new ChangeSet();
 827     out.changeTuples.addAll( cs.changeTuples );
 828     out.changeTuples.add( ct );
 829
 830     out = (ChangeSet) makeCanonical( out );
 831     op2result.put( op, out );
 832     return out;
 833   }
 834
 835
 836
 837   public static ExistPredSet join( ExistPredSet eps1,
 838                                    ExistPredSet eps2 ) {
 839
 840     assert eps1 != null;
 841     assert eps2 != null;
 842     assert eps1.isCanonical();
 843     assert eps2.isCanonical();
 844
 845     CanonicalOp op =
 846       new CanonicalOp( CanonicalOp.EXISTPREDSET_JOIN_EXISTPREDSET,
 847                        eps1,
 848                        eps2 );
 849
 850     Canonical result = op2result.get( op );
 851     if( result != null ) {
 852       return (ExistPredSet) result;
 853     }
 854
 855     // otherwise, no cached result...
 856     ExistPredSet out = new ExistPredSet();
 857     out.preds.addAll( eps1.preds );
 858     out.preds.addAll( eps2.preds );
 859
 860     out = (ExistPredSet) makeCanonical( out );
 861     op2result.put( op, out );
 862     return out;
 863   }
 864
 865   public static ExistPredSet add( ExistPredSet eps,
 866                                   ExistPred    ep ) {
 867
 868
 869     assert eps != null;
 870     assert ep  != null;
 871     assert eps.isCanonical();
 872     assert ep.isCanonical();
 873
 874     CanonicalOp op =
 875       new CanonicalOp( CanonicalOp.EXISTPREDSET_ADD_EXISTPRED,
 876                        eps,
 877                        ep );
 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( eps.preds );
 887     out.preds.add( ep );
 888
 889     out = (ExistPredSet) makeCanonical( out );
 890     op2result.put( op, out );
 891     return out;
 892   }
 893
 894
 895   public static ReachSet toCallerContext( ReachSet  rs,
 896                                           AllocSite as ) {
 897     assert rs != null;
 898     assert as != null;
 899     assert rs.isCanonical();
 900     assert as.isCanonical();
 901
 902     CanonicalOp op =
 903       new CanonicalOp( CanonicalOp.REACHSET_TOCALLERCONTEXT_ALLOCSITE,
 904                        rs,
 905                        as );
 906
 907     Canonical result = op2result.get( op );
 908     if( result != null ) {
 909       return (ReachSet) result;
 910     }
 911
 912     // otherwise, no cached result...
 913     ReachSet out = ReachSet.factory();
 914     Iterator<ReachState> itr = rs.iterator();
 915     while( itr.hasNext() ) {
 916       ReachState state = itr.next();
 917       out = Canonical.unionORpreds( out,
 918                                     Canonical.toCallerContext( state, as )
 919                                     );
 920     }
 921
 922     assert out.isCanonical();
 923     op2result.put( op, out );
 924     return out;
 925   }
 926
 927
 928   public static ReachSet toCallerContext( ReachState state,
 929                                           AllocSite  as ) {
 930     assert state != null;
 931     assert as    != null;
 932     assert state.isCanonical();
 933     assert as.isCanonical();
 934
 935     CanonicalOp op =
 936       new CanonicalOp( CanonicalOp.REACHSTATE_TOCALLERCONTEXT_ALLOCSITE,
 937                        state,
 938                        as );
 939
 940     Canonical result = op2result.get( op );
 941     if( result != null ) {
 942       return (ReachSet) result;
 943     }
 944
 945     // otherwise, no cached result...
 946     ReachSet out = ReachSet.factory();
 947
 948     // this method returns a ReachSet instead of a ReachState
 949     // because the companion method, toCallee, translates
 950     // symbols many-to-one, so state->state
 951     // but this method does an ~inverse mapping, one-to-many
 952     // so one state can split into a set of branched states
 953
 954     // 0    -> -0
 955     // 1    -> -1
 956     // 2S   -> -2S
 957     // 2S*  -> -2S*
 958     //
 959     // 0?   -> 0
 960     // 1?   -> 1
 961     // 2S?  -> 2S
 962     //      -> 0?
 963     //      -> 1?
 964     //      -> 2S?
 965     // 2S?* -> {2S*, 2S?*}
 966
 967     boolean found2Sooc = false;
 968
 969     ReachState baseState = ReachState.factory();
 970
 971     Iterator<ReachTuple> itr = state.iterator();
 972     while( itr.hasNext() ) {
 973       ReachTuple rt = itr.next();
 974
 975       int age = as.getAgeCategory( rt.getHrnID() );
 976
 977       if( age == AllocSite.AGE_notInThisSite ) {
 978         // things not from the site just go back in
 979         baseState = Canonical.add( baseState, rt );
 980
 981       } else if( age == AllocSite.AGE_summary ) {
 982
 983         if( rt.isOutOfContext() ) {
 984           // if its out-of-context, we only deal here with the ZERO-OR-MORE
 985           // arity, if ARITY-ONE we'll branch the base state after the loop
 986           if( rt.getArity() == ReachTuple.ARITY_ZEROORMORE ) {
 987             // add two overly conservative symbols to reach state (PUNTING)
 988             baseState = Canonical.add( baseState,
 989                                        ReachTuple.factory( as.getSummary(),
 990                                                            true, // multi
 991                                                            ReachTuple.ARITY_ZEROORMORE,
 992                                                            false // out-of-context
 993                                                            )
 994                                          );
 995             baseState = Canonical.add( baseState,
 996                                        ReachTuple.factory( as.getSummary(),
 997                                                            true, // multi
 998                                                            ReachTuple.ARITY_ZEROORMORE,
 999                                                            true  // out-of-context
1000                                                            )
1001                                        );
1002           } else {
1003             assert rt.getArity() == ReachTuple.ARITY_ONE;
1004             found2Sooc = true;
1005           }
1006
1007         } else {
1008           // the in-context just becomes shadow
1009           baseState = Canonical.add( baseState,
1010                                      ReachTuple.factory( as.getSummaryShadow(),
1011                                                          true, // multi
1012                                                          rt.getArity(),
1013                                                          false  // out-of-context
1014                                                          )
1015                                      );
1016         }
1017
1018
1019       } else {
1020         // otherwise age is in range [0, k]
1021         Integer I = as.getAge( rt.getHrnID() );
1022         assert I != null;
1023         assert !rt.isMultiObject();
1024         assert rt.getArity() == ReachTuple.ARITY_ONE;
1025
1026         if( rt.isOutOfContext() ) {
1027           // becomes the in-context version
1028           baseState = Canonical.add( baseState,
1029                                      ReachTuple.factory( rt.getHrnID(),
1030                                                          false, // multi
1031                                                          ReachTuple.ARITY_ONE,
1032                                                          false  // out-of-context
1033                                                          )
1034                                      );
1035
1036         } else {
1037           // otherwise the ith symbol becomes shadowed
1038           baseState = Canonical.add( baseState,
1039                                      ReachTuple.factory( -rt.getHrnID(),
1040                                                          false, // multi
1041                                                          ReachTuple.ARITY_ONE,
1042                                                          false  // out-of-context
1043                                                          )
1044                                      );
1045         }
1046       }
1047     }
1048
1049     // now either make branches if we have 2S?, or
1050     // the current baseState is the only state we need
1051     if( found2Sooc ) {
1052       // make a branch with every possibility of the one-to-many
1053       // mapping for 2S? appended to the baseState
1054       out = Canonical.add( out,
1055                            Canonical.add( baseState,
1056                                           ReachTuple.factory( as.getSummary(),
1057                                                               true, // multi
1058                                                               ReachTuple.ARITY_ONE,
1059                                                               false  // out-of-context
1060                                                               )
1061                                           )
1062                            );
1063
1064       out = Canonical.add( out,
1065                            Canonical.add( baseState,
1066                                           ReachTuple.factory( as.getSummary(),
1067                                                               true, // multi
1068                                                               ReachTuple.ARITY_ONE,
1069                                                               true  // out-of-context
1070                                                               )
1071                                           )
1072                            );
1073
1074       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1075         out = Canonical.add( out,
1076                              Canonical.add( baseState,
1077                                             ReachTuple.factory( as.getIthOldest( i ),
1078                                                                 false, // multi
1079                                                                 ReachTuple.ARITY_ONE,
1080                                                                 true  // out-of-context
1081                                                                 )
1082                                             )
1083                              );
1084       }
1085
1086     } else {
1087       // just use current baseState
1088       out = Canonical.add( out,
1089                            baseState );
1090     }
1091
1092
1093     assert out.isCanonical();
1094     op2result.put( op, out );
1095     return out;
1096   }
1097
1098
1099   public static ReachSet unshadow( ReachSet  rs,
1100                                    AllocSite as ) {
1101     assert rs != null;
1102     assert as != null;
1103     assert rs.isCanonical();
1104     assert as.isCanonical();
1105
1106     CanonicalOp op =
1107       new CanonicalOp( CanonicalOp.REACHSET_UNSHADOW_ALLOCSITE,
1108                        rs,
1109                        as );
1110
1111     Canonical result = op2result.get( op );
1112     if( result != null ) {
1113       return (ReachSet) result;
1114     }
1115
1116     // otherwise, no cached result...
1117     ReachSet out = ReachSet.factory();
1118     Iterator<ReachState> itr = rs.iterator();
1119     while( itr.hasNext() ) {
1120       ReachState state = itr.next();
1121       out = Canonical.add( out,
1122                            Canonical.unshadow( state, as )
1123                            );
1124     }
1125
1126     assert out.isCanonical();
1127     op2result.put( op, out );
1128     return out;
1129   }
1130
1131   public static ReachState unshadow( ReachState state,
1132                                      AllocSite  as ) {
1133     assert state != null;
1134     assert as    != null;
1135     assert state.isCanonical();
1136     assert as.isCanonical();
1137
1138     CanonicalOp op =
1139       new CanonicalOp( CanonicalOp.REACHSTATE_UNSHADOW_ALLOCSITE,
1140                        state,
1141                        as );
1142
1143     Canonical result = op2result.get( op );
1144     if( result != null ) {
1145       return (ReachState) result;
1146     }
1147
1148     // this is the current mapping, where 0, 1, 2S were allocated
1149     // in the current context, 0?, 1? and 2S? were allocated in a
1150     // previous context, and we're translating to a future context
1151     //
1152     // -0   -> 0
1153     // -1   -> 1
1154     // -2S  -> 2S
1155
1156     // otherwise, no cached result...
1157     ReachState out = ReachState.factory();
1158     Iterator<ReachTuple> itr = state.iterator();
1159     while( itr.hasNext() ) {
1160       ReachTuple rt = itr.next();
1161
1162       int age = as.getShadowAgeCategory( rt.getHrnID() );
1163
1164       if( age == AllocSite.SHADOWAGE_notInThisSite ) {
1165         // things not from the site just go back in
1166         out = Canonical.add( out, rt );
1167
1168       } else {
1169         assert !rt.isOutOfContext();
1170
1171         // otherwise unshadow it
1172         out = Canonical.add( out,
1173                              ReachTuple.factory( -rt.getHrnID(),
1174                                                  rt.isMultiObject(),
1175                                                  rt.getArity(),
1176                                                  false
1177                                                  )
1178                              );
1179       }
1180     }
1181
1182     out = Canonical.attach( out,
1183                             state.getPreds()
1184                             );
1185
1186     assert out.isCanonical();
1187     op2result.put( op, out );
1188     return out;
1189   }
1190
1191
1192
1193   public static ReachState makePredsTrue( ReachState rs ) {
1194     assert rs != null;
1195     assert rs.isCanonical();
1196
1197     // ops require two canonicals, in this case always supply
1198     // the empty reach state as the second, it's never used,
1199     // but makes the hashing happy
1200     CanonicalOp op =
1201       new CanonicalOp( CanonicalOp.REACHSTATE_MAKEPREDSTRUE,
1202                        rs,
1203                        ReachState.factory() );
1204
1205     Canonical result = op2result.get( op );
1206     if( result != null ) {
1207       return (ReachState) result;
1208     }
1209
1210     // otherwise, no cached result...
1211     ReachState out = new ReachState();
1212
1213     // just remake state with the true predicate attached
1214     out.reachTuples.addAll( rs.reachTuples );
1215     out.preds = ExistPredSet.factory( ExistPred.factory() );
1216
1217     out = (ReachState) makeCanonical( out );
1218     op2result.put( op, out );
1219     return out;
1220   }
1221
1222
1223   public static ReachSet makePredsTrue( ReachSet rs ) {
1224     assert rs != null;
1225     assert rs.isCanonical();
1226
1227     // ops require two canonicals, in this case always supply
1228     // the empty reach set as the second, it's never used,
1229     // but makes the hashing happy
1230     CanonicalOp op =
1231       new CanonicalOp( CanonicalOp.REACHSET_MAKEPREDSTRUE,
1232                        rs,
1233                        ReachSet.factory() );
1234
1235     Canonical result = op2result.get( op );
1236     if( result != null ) {
1237       return (ReachSet) result;
1238     }
1239
1240     // otherwise, no cached result...
1241     ReachSet out = ReachSet.factory();
1242     Iterator<ReachState> itr = rs.iterator();
1243     while( itr.hasNext() ) {
1244       ReachState state = itr.next();
1245       out = Canonical.add( out,
1246                            Canonical.makePredsTrue( state )
1247                            );
1248     }
1249
1250     out = (ReachSet) makeCanonical( out );
1251     op2result.put( op, out );
1252     return out;
1253   }
1254
1255
1256   public static Taint attach( Taint        t,
1257                               ExistPredSet preds ) {
1258     assert t     != null;
1259     assert preds != null;
1260     assert t.isCanonical();
1261     assert preds.isCanonical();
1262
1263     CanonicalOp op =
1264       new CanonicalOp( CanonicalOp.TAINT_ATTACH_EXISTPREDSET,
1265                        t,
1266                        preds );
1267
1268     Canonical result = op2result.get( op );
1269     if( result != null ) {
1270       return (Taint) result;
1271     }
1272
1273     // otherwise, no cached result...
1274     Taint out = new Taint( t );
1275     out.preds = Canonical.join( t.preds,
1276                                 preds );
1277
1278     out = (Taint) makeCanonical( out );
1279     op2result.put( op, out );
1280     return out;
1281   }
1282
1283   public static TaintSet add( TaintSet ts,
1284                               Taint    t ) {
1285     assert ts != null;
1286     assert t  != null;
1287     assert ts.isCanonical();
1288     assert t.isCanonical();
1289
1290     CanonicalOp op =
1291       new CanonicalOp( CanonicalOp.TAINTSET_ADD_TAINT,
1292                        ts,
1293                        t );
1294
1295     Canonical result = op2result.get( op );
1296     if( result != null ) {
1297       return (TaintSet) result;
1298     }
1299
1300     // otherwise, no cached result...
1301     TaintSet out = new TaintSet();
1302     out.taints.addAll( ts.taints );
1303     out.taints.add( t );
1304
1305     out = (TaintSet) makeCanonical( out );
1306     op2result.put( op, out );
1307     return out;
1308   }
1309
1310   public static TaintSet union( TaintSet ts1,
1311                                 TaintSet ts2 ) {
1312     assert ts1 != null;
1313     assert ts2 != null;
1314     assert ts1.isCanonical();
1315     assert ts2.isCanonical();
1316
1317     CanonicalOp op =
1318       new CanonicalOp( CanonicalOp.TAINTSET_UNION_TAINTSET,
1319                        ts1,
1320                        ts2 );
1321
1322     Canonical result = op2result.get( op );
1323     if( result != null ) {
1324       return (TaintSet) result;
1325     }
1326
1327     // otherwise, no cached result...
1328     TaintSet out = new TaintSet();
1329
1330     // first add everything from 1, and if it was also in 2
1331     // take the OR of the predicates
1332     Iterator<Taint> tItr = ts1.iterator();
1333     while( tItr.hasNext() ) {
1334       Taint t1 = tItr.next();
1335       Taint t2 = ts2.containsIgnorePreds( t1 );
1336
1337       if( t2 != null ) {
1338         Taint tNew = new Taint( t1 );
1339         tNew.preds = Canonical.join( t1.preds,
1340                                      t2.preds
1341                                      );
1342         tNew = (Taint) makeCanonical( tNew );
1343         out.taints.add( tNew );
1344       } else {
1345         out.taints.add( t1 );
1346       }
1347     }
1348
1349     // then add everything in 2 that wasn't in 1
1350     tItr = ts2.iterator();
1351     while( tItr.hasNext() ) {
1352       Taint t2 = tItr.next();
1353       Taint t1 = ts1.containsIgnorePreds( t2 );
1354
1355       if( t1 == null ) {
1356         out.taints.add( t2 );
1357       }
1358     }
1359
1360     out = (TaintSet) makeCanonical( out );
1361     op2result.put( op, out );
1362     return out;
1363   }
1364
1365   public static TaintSet unionORpreds( TaintSet ts1,
1366                                        TaintSet ts2 ) {
1367     assert ts1 != null;
1368     assert ts2 != null;
1369     assert ts1.isCanonical();
1370     assert ts2.isCanonical();
1371
1372     CanonicalOp op =
1373       new CanonicalOp( CanonicalOp.TAINTSET_UNIONORPREDS_TAINTSET,
1374                        ts1,
1375                        ts2 );
1376
1377     Canonical result = op2result.get( op );
1378     if( result != null ) {
1379       return (TaintSet) result;
1380     }
1381
1382     // otherwise, no cached result...
1383     TaintSet out = new TaintSet();
1384
1385     // first add everything from 1, and if it was also in 2
1386     // take the OR of the predicates
1387     Iterator<Taint> tItr = ts1.iterator();
1388     while( tItr.hasNext() ) {
1389       Taint t1 = tItr.next();
1390       Taint t2 = ts2.containsIgnorePreds( t1 );
1391
1392       if( t2 != null ) {
1393         Taint tNew = new Taint( t1 );
1394         tNew.preds = Canonical.join( t1.preds,
1395                                      t2.preds
1396                                      );
1397         tNew = (Taint) makeCanonical( tNew );
1398         out.taints.add( tNew );
1399       } else {
1400         out.taints.add( t1 );
1401       }
1402     }
1403
1404     // then add everything in 2 that wasn't in 1
1405     tItr = ts2.iterator();
1406     while( tItr.hasNext() ) {
1407       Taint t2 = tItr.next();
1408       Taint t1 = ts1.containsIgnorePreds( t2 );
1409
1410       if( t1 == null ) {
1411         out.taints.add( t2 );
1412       }
1413     }
1414
1415     out = (TaintSet) makeCanonical( out );
1416     op2result.put( op, out );
1417     return out;
1418   }
1419
1420
1421   // BOO, HISS! SESE (rblock) operand does NOT extend
1422   // Canonical, so we can't cache this op by its
1423   // canonical arguments--THINK ABOUT A BETTER WAY!
1424   public static TaintSet removeTaintsBy( TaintSet          ts,
1425                                          FlatSESEEnterNode sese ) {
1426     assert ts != null;
1427     assert ts.isCanonical();
1428     assert sese != null;
1429
1430     // NEVER a cached result... (cry)
1431     TaintSet out = new TaintSet();
1432
1433     Iterator<Taint> tItr = ts.iterator();
1434     while( tItr.hasNext() ) {
1435       Taint t = tItr.next();
1436
1437       if( !t.getSESE().equals( sese ) ) {
1438         out.taints.add( t );
1439       }
1440     }
1441
1442     out = (TaintSet) makeCanonical( out );
1443     //op2result.put( op, out ); CRY CRY
1444     return out;
1445   }
1446
1447
1448   public static Taint changePredsTo( Taint t, ExistPredSet preds ) {
1449     assert t != null;
1450     assert t.isCanonical();
1451
1452     // ops require two canonicals, in this case always supply
1453     // the empty reach state as the second, it's never used,
1454     // but makes the hashing happy
1455     CanonicalOp op =
1456       new CanonicalOp( CanonicalOp.TAINT_CHANGEPREDSTO,
1457                        t,
1458                        t );
1459
1460     Canonical result = op2result.get( op );
1461     if( result != null ) {
1462       return (Taint) result;
1463     }
1464
1465     // otherwise, no cached result...
1466     Taint out = new Taint( t.sese,
1467                            t.stallSite,
1468                            t.var,
1469                            t.allocSite,
1470                            preds
1471                            );
1472
1473     out = (Taint) makeCanonical( out );
1474     op2result.put( op, out );
1475     return out;
1476   }
1477
1478
1479   public static TaintSet changePredsTo( TaintSet ts, ExistPredSet preds ) {
1480     assert ts != null;
1481     assert ts.isCanonical();
1482
1483     // ops require two canonicals, in this case always supply
1484     // the empty reach set as the second, it's never used,
1485     // but makes the hashing happy
1486     CanonicalOp op =
1487       new CanonicalOp( CanonicalOp.TAINTSET_CHANGEPREDSTO,
1488                        ts,
1489                        ts );
1490
1491     Canonical result = op2result.get( op );
1492     if( result != null ) {
1493       return (TaintSet) result;
1494     }
1495
1496     // otherwise, no cached result...
1497     TaintSet out = TaintSet.factory();
1498     Iterator<Taint> itr = ts.iterator();
1499     while( itr.hasNext() ) {
1500       Taint t = itr.next();
1501       out = Canonical.add( out,
1502                            Canonical.changePredsTo( t, preds )
1503                            );
1504     }
1505
1506     out = (TaintSet) makeCanonical( out );
1507     op2result.put( op, out );
1508     return out;
1509   }
1510 }