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   /*
 896   public static ReachSet toCalleeContext( ReachSet  rs,
 897                                           AllocSite as ) {
 898     assert rs != null;
 899     assert as != null;
 900     assert rs.isCanonical();
 901     assert as.isCanonical();
 902
 903     CanonicalOp op =
 904       new CanonicalOp( CanonicalOp.REACHSET_TOCALLEECONTEXT_ALLOCSITE,
 905                        rs,
 906                        as );
 907
 908     Canonical result = op2result.get( op );
 909     if( result != null ) {
 910       return (ReachSet) result;
 911     }
 912
 913     // otherwise, no cached result...
 914     ReachSet out = ReachSet.factory();
 915     Iterator<ReachState> itr = rs.iterator();
 916     while( itr.hasNext() ) {
 917       ReachState state = itr.next();
 918       out = Canonical.add( out,
 919                            Canonical.toCalleeContext( state, as )
 920                            );
 921     }
 922
 923     assert out.isCanonical();
 924     op2result.put( op, out );
 925     return out;
 926   }
 927   */
 928
 929   /*
 930   public static ReachState toCalleeContext( ReachState state,
 931                                             AllocSite  as ) {
 932     assert state != null;
 933     assert as    != null;
 934     assert state.isCanonical();
 935     assert as.isCanonical();
 936
 937     CanonicalOp op =
 938       new CanonicalOp( CanonicalOp.REACHSTATE_TOCALLEECONTEXT_ALLOCSITE,
 939                        state,
 940                        as );
 941
 942     Canonical result = op2result.get( op );
 943     if( result != null ) {
 944       return (ReachState) result;
 945     }
 946
 947     // otherwise, no cached result...
 948     ReachState out = ReachState.factory();
 949     Iterator<ReachTuple> itr = state.iterator();
 950     while( itr.hasNext() ) {
 951       ReachTuple rt = itr.next();
 952
 953       int age = as.getAgeCategory( rt.getHrnID() );
 954
 955       // this is the current mapping, where 0, 1, 2S were allocated
 956       // in the current context, 0?, 1? and 2S? were allocated in a
 957       // previous context, and we're translating to a future context
 958       //
 959       // 0    -> 0?
 960       // 1    -> 1?
 961       // 2S   -> 2S?
 962       // 2S*  -> 2S?*
 963       //
 964       // 0?   -> 2S?
 965       // 1?   -> 2S?
 966       // 2S?  -> 2S?
 967       // 2S?* -> 2S?*
 968
 969       if( age == AllocSite.AGE_notInThisSite ) {
 970         // things not from the site just go back in
 971         out = Canonical.union( out, rt );
 972
 973       } else if( age == AllocSite.AGE_summary ||
 974                  rt.isOutOfContext()
 975                  ) {
 976         // the in-context summary and all existing out-of-context
 977         // stuff all become
 978         out = Canonical.union( out,
 979                                ReachTuple.factory( as.getSummary(),
 980                                                    true, // multi
 981                                                    rt.getArity(),
 982                                                    true  // out-of-context
 983                                                    )
 984                                );
 985       } else {
 986         // otherwise everything else just goes to an out-of-context
 987         // version, everything else the same
 988         Integer I = as.getAge( rt.getHrnID() );
 989         assert I != null;
 990
 991         assert !rt.isMultiObject();
 992
 993         out = Canonical.union( out,
 994                                ReachTuple.factory( rt.getHrnID(),
 995                                                    rt.isMultiObject(),
 996                                                    rt.getArity(),
 997                                                    true  // out-of-context
 998                                                    )
 999                                );
1000       }
1001     }
1002
1003     out = Canonical.attach( out,
1004                             state.getPreds()
1005                             );
1006
1007     assert out.isCanonical();
1008     op2result.put( op, out );
1009     return out;
1010   }
1011   */
1012
1013
1014   public static ReachSet toCallerContext( ReachSet  rs,
1015                                           AllocSite as ) {
1016     assert rs != null;
1017     assert as != null;
1018     assert rs.isCanonical();
1019     assert as.isCanonical();
1020
1021     CanonicalOp op =
1022       new CanonicalOp( CanonicalOp.REACHSET_TOCALLERCONTEXT_ALLOCSITE,
1023                        rs,
1024                        as );
1025
1026     Canonical result = op2result.get( op );
1027     if( result != null ) {
1028       return (ReachSet) result;
1029     }
1030
1031     // otherwise, no cached result...
1032     ReachSet out = ReachSet.factory();
1033     Iterator<ReachState> itr = rs.iterator();
1034     while( itr.hasNext() ) {
1035       ReachState state = itr.next();
1036       out = Canonical.unionORpreds( out,
1037                                     Canonical.toCallerContext( state, as )
1038                                     );
1039     }
1040
1041     assert out.isCanonical();
1042     op2result.put( op, out );
1043     return out;
1044   }
1045
1046
1047   public static ReachSet toCallerContext( ReachState state,
1048                                           AllocSite  as ) {
1049     assert state != null;
1050     assert as    != null;
1051     assert state.isCanonical();
1052     assert as.isCanonical();
1053
1054     CanonicalOp op =
1055       new CanonicalOp( CanonicalOp.REACHSTATE_TOCALLERCONTEXT_ALLOCSITE,
1056                        state,
1057                        as );
1058
1059     Canonical result = op2result.get( op );
1060     if( result != null ) {
1061       return (ReachSet) result;
1062     }
1063
1064     // otherwise, no cached result...
1065     ReachSet out = ReachSet.factory();
1066
1067     // this method returns a ReachSet instead of a ReachState
1068     // because the companion method, toCallee, translates
1069     // symbols many-to-one, so state->state
1070     // but this method does an ~inverse mapping, one-to-many
1071     // so one state can split into a set of branched states
1072
1073     // 0    -> -0
1074     // 1    -> -1
1075     // 2S   -> -2S
1076     // 2S*  -> -2S*
1077     //
1078     // 0?   -> 0
1079     // 1?   -> 1
1080     // 2S?  -> 2S
1081     //      -> 0?
1082     //      -> 1?
1083     //      -> 2S?
1084     // 2S?* -> {2S*, 2S?*}
1085
1086     boolean found2Sooc = false;
1087
1088     ReachState baseState = ReachState.factory();
1089
1090     Iterator<ReachTuple> itr = state.iterator();
1091     while( itr.hasNext() ) {
1092       ReachTuple rt = itr.next();
1093
1094       int age = as.getAgeCategory( rt.getHrnID() );
1095
1096       if( age == AllocSite.AGE_notInThisSite ) {
1097         // things not from the site just go back in
1098         baseState = Canonical.add( baseState, rt );
1099
1100       } else if( age == AllocSite.AGE_summary ) {
1101
1102         if( rt.isOutOfContext() ) {
1103           // if its out-of-context, we only deal here with the ZERO-OR-MORE
1104           // arity, if ARITY-ONE we'll branch the base state after the loop
1105           if( rt.getArity() == ReachTuple.ARITY_ZEROORMORE ) {
1106             // add two overly conservative symbols to reach state (PUNTING)
1107             baseState = Canonical.add( baseState,
1108                                        ReachTuple.factory( as.getSummary(),
1109                                                            true, // multi
1110                                                            ReachTuple.ARITY_ZEROORMORE,
1111                                                            false // out-of-context
1112                                                            )
1113                                          );
1114             baseState = Canonical.add( baseState,
1115                                        ReachTuple.factory( as.getSummary(),
1116                                                            true, // multi
1117                                                            ReachTuple.ARITY_ZEROORMORE,
1118                                                            true  // out-of-context
1119                                                            )
1120                                        );
1121           } else {
1122             assert rt.getArity() == ReachTuple.ARITY_ONE;
1123             found2Sooc = true;
1124           }
1125
1126         } else {
1127           // the in-context just becomes shadow
1128           baseState = Canonical.add( baseState,
1129                                      ReachTuple.factory( as.getSummaryShadow(),
1130                                                          true, // multi
1131                                                          rt.getArity(),
1132                                                          false  // out-of-context
1133                                                          )
1134                                      );
1135         }
1136
1137
1138       } else {
1139         // otherwise age is in range [0, k]
1140         Integer I = as.getAge( rt.getHrnID() );
1141         assert I != null;
1142         assert !rt.isMultiObject();
1143         assert rt.getArity() == ReachTuple.ARITY_ONE;
1144
1145         if( rt.isOutOfContext() ) {
1146           // becomes the in-context version
1147           baseState = Canonical.add( baseState,
1148                                      ReachTuple.factory( rt.getHrnID(),
1149                                                          false, // multi
1150                                                          ReachTuple.ARITY_ONE,
1151                                                          false  // out-of-context
1152                                                          )
1153                                      );
1154
1155         } else {
1156           // otherwise the ith symbol becomes shadowed
1157           baseState = Canonical.add( baseState,
1158                                      ReachTuple.factory( -rt.getHrnID(),
1159                                                          false, // multi
1160                                                          ReachTuple.ARITY_ONE,
1161                                                          false  // out-of-context
1162                                                          )
1163                                      );
1164         }
1165       }
1166     }
1167
1168     // now either make branches if we have 2S?, or
1169     // the current baseState is the only state we need
1170     if( found2Sooc ) {
1171       // make a branch with every possibility of the one-to-many
1172       // mapping for 2S? appended to the baseState
1173       out = Canonical.add( out,
1174                            Canonical.add( baseState,
1175                                           ReachTuple.factory( as.getSummary(),
1176                                                               true, // multi
1177                                                               ReachTuple.ARITY_ONE,
1178                                                               false  // out-of-context
1179                                                               )
1180                                           )
1181                            );
1182
1183       out = Canonical.add( out,
1184                            Canonical.add( baseState,
1185                                           ReachTuple.factory( as.getSummary(),
1186                                                               true, // multi
1187                                                               ReachTuple.ARITY_ONE,
1188                                                               true  // out-of-context
1189                                                               )
1190                                           )
1191                            );
1192
1193       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1194         out = Canonical.add( out,
1195                              Canonical.add( baseState,
1196                                             ReachTuple.factory( as.getIthOldest( i ),
1197                                                                 false, // multi
1198                                                                 ReachTuple.ARITY_ONE,
1199                                                                 true  // out-of-context
1200                                                                 )
1201                                             )
1202                              );
1203       }
1204
1205     } else {
1206       // just use current baseState
1207       out = Canonical.add( out,
1208                            baseState );
1209     }
1210
1211
1212     assert out.isCanonical();
1213     op2result.put( op, out );
1214     return out;
1215   }
1216
1217
1218   public static ReachSet unshadow( ReachSet  rs,
1219                                    AllocSite as ) {
1220     assert rs != null;
1221     assert as != null;
1222     assert rs.isCanonical();
1223     assert as.isCanonical();
1224
1225     CanonicalOp op =
1226       new CanonicalOp( CanonicalOp.REACHSET_UNSHADOW_ALLOCSITE,
1227                        rs,
1228                        as );
1229
1230     Canonical result = op2result.get( op );
1231     if( result != null ) {
1232       return (ReachSet) result;
1233     }
1234
1235     // otherwise, no cached result...
1236     ReachSet out = ReachSet.factory();
1237     Iterator<ReachState> itr = rs.iterator();
1238     while( itr.hasNext() ) {
1239       ReachState state = itr.next();
1240       out = Canonical.add( out,
1241                            Canonical.unshadow( state, as )
1242                            );
1243     }
1244
1245     assert out.isCanonical();
1246     op2result.put( op, out );
1247     return out;
1248   }
1249
1250   public static ReachState unshadow( ReachState state,
1251                                      AllocSite  as ) {
1252     assert state != null;
1253     assert as    != null;
1254     assert state.isCanonical();
1255     assert as.isCanonical();
1256
1257     CanonicalOp op =
1258       new CanonicalOp( CanonicalOp.REACHSTATE_UNSHADOW_ALLOCSITE,
1259                        state,
1260                        as );
1261
1262     Canonical result = op2result.get( op );
1263     if( result != null ) {
1264       return (ReachState) result;
1265     }
1266
1267     // this is the current mapping, where 0, 1, 2S were allocated
1268     // in the current context, 0?, 1? and 2S? were allocated in a
1269     // previous context, and we're translating to a future context
1270     //
1271     // -0   -> 0
1272     // -1   -> 1
1273     // -2S  -> 2S
1274
1275     // otherwise, no cached result...
1276     ReachState out = ReachState.factory();
1277     Iterator<ReachTuple> itr = state.iterator();
1278     while( itr.hasNext() ) {
1279       ReachTuple rt = itr.next();
1280
1281       int age = as.getShadowAgeCategory( rt.getHrnID() );
1282
1283       if( age == AllocSite.SHADOWAGE_notInThisSite ) {
1284         // things not from the site just go back in
1285         out = Canonical.add( out, rt );
1286
1287       } else {
1288         assert !rt.isOutOfContext();
1289
1290         // otherwise unshadow it
1291         out = Canonical.add( out,
1292                              ReachTuple.factory( -rt.getHrnID(),
1293                                                  rt.isMultiObject(),
1294                                                  rt.getArity(),
1295                                                  false
1296                                                  )
1297                              );
1298       }
1299     }
1300
1301     out = Canonical.attach( out,
1302                             state.getPreds()
1303                             );
1304
1305     assert out.isCanonical();
1306     op2result.put( op, out );
1307     return out;
1308   }
1309
1310
1311
1312   public static ReachState makePredsTrue( ReachState rs ) {
1313     assert rs != null;
1314     assert rs.isCanonical();
1315
1316     // ops require two canonicals, in this case always supply
1317     // the empty reach state as the second, it's never used,
1318     // but makes the hashing happy
1319     CanonicalOp op =
1320       new CanonicalOp( CanonicalOp.REACHSTATE_MAKEPREDSTRUE,
1321                        rs,
1322                        ReachState.factory() );
1323
1324     Canonical result = op2result.get( op );
1325     if( result != null ) {
1326       return (ReachState) result;
1327     }
1328
1329     // otherwise, no cached result...
1330     ReachState out = new ReachState();
1331
1332     // just remake state with the true predicate attached
1333     out.reachTuples.addAll( rs.reachTuples );
1334     out.preds = ExistPredSet.factory( ExistPred.factory() );
1335
1336     out = (ReachState) makeCanonical( out );
1337     op2result.put( op, out );
1338     return out;
1339   }
1340
1341
1342   public static ReachSet makePredsTrue( ReachSet rs ) {
1343     assert rs != null;
1344     assert rs.isCanonical();
1345
1346     // ops require two canonicals, in this case always supply
1347     // the empty reach set as the second, it's never used,
1348     // but makes the hashing happy
1349     CanonicalOp op =
1350       new CanonicalOp( CanonicalOp.REACHSET_MAKEPREDSTRUE,
1351                        rs,
1352                        ReachSet.factory() );
1353
1354     Canonical result = op2result.get( op );
1355     if( result != null ) {
1356       return (ReachSet) result;
1357     }
1358
1359     // otherwise, no cached result...
1360     ReachSet out = ReachSet.factory();
1361     Iterator<ReachState> itr = rs.iterator();
1362     while( itr.hasNext() ) {
1363       ReachState state = itr.next();
1364       out = Canonical.add( out,
1365                            Canonical.makePredsTrue( state )
1366                            );
1367     }
1368
1369     out = (ReachSet) makeCanonical( out );
1370     op2result.put( op, out );
1371     return out;
1372   }
1373
1374
1375   public static TaintSet add( TaintSet ts,
1376                               Taint    t ) {
1377     assert ts != null;
1378     assert t  != null;
1379     assert ts.isCanonical();
1380     assert t.isCanonical();
1381
1382     CanonicalOp op =
1383       new CanonicalOp( CanonicalOp.TAINTSET_ADD_TAINT,
1384                        ts,
1385                        t );
1386
1387     Canonical result = op2result.get( op );
1388     if( result != null ) {
1389       return (TaintSet) result;
1390     }
1391
1392     // otherwise, no cached result...
1393     TaintSet out = new TaintSet();
1394     out.taints.addAll( ts.taints );
1395     out.taints.add( t );
1396
1397     out = (TaintSet) makeCanonical( out );
1398     op2result.put( op, out );
1399     return out;
1400   }
1401
1402   public static TaintSet union( TaintSet ts1,
1403                                 TaintSet ts2 ) {
1404     assert ts1 != null;
1405     assert ts2 != null;
1406     assert ts1.isCanonical();
1407     assert ts2.isCanonical();
1408
1409     CanonicalOp op =
1410       new CanonicalOp( CanonicalOp.TAINTSET_UNION_TAINTSET,
1411                        ts1,
1412                        ts2 );
1413
1414     Canonical result = op2result.get( op );
1415     if( result != null ) {
1416       return (TaintSet) result;
1417     }
1418
1419     // otherwise, no cached result...
1420     TaintSet out = new TaintSet();
1421     out.taints.addAll( ts1.taints );
1422     out.taints.addAll( ts2.taints );
1423
1424     out = (TaintSet) makeCanonical( out );
1425     op2result.put( op, out );
1426     return out;
1427   }
1428
1429 }