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   // canonical objects should never be modified
  64   // and therefore have changing hash codes, so
  65   // use a standard canonical hash code method to
  66   // enforce this, and define a specific hash code
  67   // method each specific subclass should implement
  68   abstract public int hashCodeSpecific();
  69
  70   private boolean hasHash = false;
  71   private int     oldHash;
  72   final public int hashCode() {
  73     int hash = hashCodeSpecific();
  74
  75     if( hasHash ) {
  76       if( oldHash != hash ) {
  77         throw new Error( "A CANONICAL HASH CHANGED" );
  78       }
  79     } else {
  80       hasHash = true;
  81       oldHash = hash;
  82     }
  83
  84     return hash;
  85   }
  86
  87
  88
  89
  90   // mapping of a non-trivial operation to its result
  91   private static    Hashtable<CanonicalOp, Canonical>
  92     op2result = new Hashtable<CanonicalOp, Canonical>();
  93
  94
  95
  96   ///////////////////////////////////////////////////////////
  97   //
  98   //  Everything below are static methods that implement
  99   //  "mutating" operations on Canonical objects by returning
 100   //  the canonical result.  If the op is non-trivial the
 101   //  canonical result is hashed by its defining CononicalOp
 102   //
 103   ///////////////////////////////////////////////////////////
 104
 105
 106   // not weighty, don't bother with caching
 107   public static ReachTuple unionArity( ReachTuple rt1,
 108                                        ReachTuple rt2 ) {
 109     assert rt1 != null;
 110     assert rt2 != null;
 111     assert rt1.isCanonical();
 112     assert rt2.isCanonical();
 113     assert rt1.hrnID          == rt2.hrnID;
 114     assert rt1.isMultiObject  == rt2.isMultiObject;
 115     assert rt1.isOutOfContext == rt2.isOutOfContext;
 116
 117     ReachTuple out;
 118
 119     if( rt1.isMultiObject ) {
 120       // on two non-ZERO arity multi regions, union arity is always
 121       // ZERO-OR-MORE
 122       out = ReachTuple.factory( rt1.hrnID,
 123                                 true,
 124                                 ReachTuple.ARITY_ZEROORMORE,
 125                                 rt1.isOutOfContext );
 126
 127     } else {
 128       // a single object region can only be ARITY_ONE (or zero by
 129       // being absent)
 130       assert rt1.arity == ReachTuple.ARITY_ONE;
 131       out = rt1;
 132     }
 133
 134     assert out.isCanonical();
 135     return out;
 136   }
 137
 138   // not weighty, no caching
 139   public static ReachTuple changeHrnIDTo( ReachTuple rt,
 140                                           Integer    hrnIDToChangeTo ) {
 141     assert rt              != null;
 142     assert hrnIDToChangeTo != null;
 143
 144     ReachTuple out = ReachTuple.factory( hrnIDToChangeTo,
 145                                          rt.isMultiObject,
 146                                          rt.arity,
 147                                          rt.isOutOfContext
 148                                          );
 149     assert out.isCanonical();
 150     return out;
 151   }
 152
 153
 154   public static ReachState union( ReachState rs1,
 155                                   ReachState rs2 ) {
 156     assert rs1 != null;
 157     assert rs2 != null;
 158     assert rs1.isCanonical();
 159     assert rs2.isCanonical();
 160
 161     CanonicalOp op =
 162       new CanonicalOp( CanonicalOp.REACHSTATE_UNION_REACHSTATE,
 163                               rs1,
 164                               rs2 );
 165
 166     Canonical result = op2result.get( op );
 167     if( result != null ) {
 168       return (ReachState) result;
 169     }
 170
 171     // otherwise, no cached result...
 172     ReachState out = new ReachState();
 173     out.reachTuples.addAll( rs1.reachTuples );
 174     out.reachTuples.addAll( rs2.reachTuples );
 175
 176     out = (ReachState) makeCanonical( out );
 177     op2result.put( op, out );
 178     return out;
 179   }
 180
 181   // this is just a convenience version of above
 182   public static ReachState union( ReachState rs,
 183                                   ReachTuple rt ) {
 184     assert rs != null;
 185     assert rt != null;
 186
 187     CanonicalOp op =
 188       new CanonicalOp( CanonicalOp.REACHSTATE_UNION_REACHTUPLE,
 189                        rs,
 190                        rt );
 191
 192     Canonical result = op2result.get( op );
 193     if( result != null ) {
 194       return (ReachState) result;
 195     }
 196
 197     // otherwise, no cached result...
 198     ReachState out = new ReachState();
 199     out.reachTuples.addAll( rs.reachTuples );
 200     out.reachTuples.add( rt );
 201
 202     out = (ReachState) makeCanonical( out );
 203     op2result.put( op, out );
 204     return out;
 205   }
 206
 207
 208   public static ReachState unionUpArity( ReachState rs1,
 209                                          ReachState rs2 ) {
 210     assert rs1 != null;
 211     assert rs2 != null;
 212     assert rs1.isCanonical();
 213     assert rs2.isCanonical();
 214
 215     CanonicalOp op =
 216       new CanonicalOp( CanonicalOp.REACHSTATE_UNIONUPARITY_REACHSTATE,
 217                        rs1,
 218                        rs2 );
 219
 220     Canonical result = op2result.get( op );
 221     if( result != null ) {
 222       return (ReachState) result;
 223     }
 224
 225     // otherwise, no cached result...
 226     ReachState out = new ReachState();
 227
 228     Iterator<ReachTuple> rtItr = rs1.iterator();
 229     while( rtItr.hasNext() ) {
 230       ReachTuple rt1 = rtItr.next();
 231       ReachTuple rt2 = rs2.containsHrnID( rt1.getHrnID(),
 232                                           rt1.isOutOfContext()
 233                                           );
 234       if( rt2 != null ) {
 235         out.reachTuples.add( unionArity( rt1, rt2 ) );
 236       } else {
 237         out.reachTuples.add( rt1 );
 238       }
 239     }
 240
 241     rtItr = rs2.iterator();
 242     while( rtItr.hasNext() ) {
 243       ReachTuple rt2 = rtItr.next();
 244       ReachTuple rto = out.containsHrnID( rt2.getHrnID(),
 245                                           rt2.isOutOfContext()
 246                                           );
 247       if( rto == null ) {
 248         out.reachTuples.add( rto );
 249       }
 250     }
 251
 252     out = (ReachState) makeCanonical( out );
 253     op2result.put( op, out );
 254     return out;
 255   }
 256
 257   public static ReachState add( ReachState rs, ReachTuple rt ) {
 258     return union( rs, rt );
 259   }
 260
 261   public static ReachState remove( ReachState rs, ReachTuple rt ) {
 262     assert rs != null;
 263     assert rt != null;
 264
 265     CanonicalOp op =
 266       new CanonicalOp( CanonicalOp.REACHSTATE_REMOVE_REACHTUPLE,
 267                        rs,
 268                        rt );
 269
 270     Canonical result = op2result.get( op );
 271     if( result != null ) {
 272       return (ReachState) result;
 273     }
 274
 275     // otherwise, no cached result...
 276     ReachState out = new ReachState();
 277     out.reachTuples.addAll( rs.reachTuples );
 278     out.reachTuples.remove( rt );
 279
 280     out = (ReachState) makeCanonical( out );
 281     op2result.put( op, out );
 282     return out;
 283   }
 284
 285
 286   public static ReachState ageTuplesFrom( ReachState rs,
 287                                           AllocSite  as ) {
 288     assert rs != null;
 289     assert as != null;
 290     assert rs.isCanonical();
 291     assert as.isCanonical();
 292
 293     CanonicalOp op =
 294       new CanonicalOp( CanonicalOp.REACHSTATE_AGETUPLESFROM_ALLOCSITE,
 295                        rs,
 296                        as );
 297
 298     Canonical result = op2result.get( op );
 299     if( result != null ) {
 300       return (ReachState) result;
 301     }
 302
 303     // otherwise, no cached result...
 304     ReachState out = new ReachState();
 305
 306     ReachTuple rtSummary = null;
 307     ReachTuple rtOldest  = null;
 308
 309     Iterator<ReachTuple> rtItr = rs.iterator();
 310     while( rtItr.hasNext() ) {
 311       ReachTuple rt    = rtItr.next();
 312       Integer    hrnID = rt.getHrnID();
 313       int        age   = as.getAgeCategory( hrnID );
 314
 315       // hrnIDs not associated with
 316       // the site should be left alone, and
 317       // those from this site but out-of-context
 318       if( age == AllocSite.AGE_notInThisSite ||
 319           rt.isOutOfContext()
 320           ) {
 321         out.reachTuples.add( rt );
 322
 323       } else if( age == AllocSite.AGE_summary ) {
 324         // remember the summary tuple, but don't add it
 325         // we may combine it with the oldest tuple
 326         rtSummary = rt;
 327
 328       } else if( age == AllocSite.AGE_oldest ) {
 329         // found an oldest hrnID, again just remember
 330         // for later
 331         rtOldest = rt;
 332
 333       } else {
 334         assert age == AllocSite.AGE_in_I;
 335
 336         Integer I = as.getAge( hrnID );
 337         assert I != null;
 338
 339         // otherwise, we change this hrnID to the
 340         // next older hrnID
 341         Integer hrnIDToChangeTo = as.getIthOldest( I + 1 );
 342         ReachTuple rtAged =
 343           Canonical.changeHrnIDTo( rt, hrnIDToChangeTo );
 344         out.reachTuples.add( rtAged );
 345       }
 346     }
 347
 348     // there are four cases to consider here
 349     // 1. we found a summary tuple and no oldest tuple
 350     //    Here we just pass the summary unchanged
 351     // 2. we found an oldest tuple, no summary
 352     //    Make a new, arity-one summary tuple
 353     // 3. we found both a summary and an oldest
 354     //    Merge them by arity
 355     // 4. (not handled) we found neither, do nothing
 356     if( rtSummary != null && rtOldest == null ) {
 357       out.reachTuples.add( rtSummary );
 358
 359     } else if( rtSummary == null && rtOldest != null ) {
 360       out.reachTuples.add( ReachTuple.factory( as.getSummary(),
 361                                                true, // multi
 362                                                rtOldest.getArity(),
 363                                                false // out-of-context
 364                                                )
 365                            );
 366
 367     } else if( rtSummary != null && rtOldest != null ) {
 368       out.reachTuples.add( Canonical.unionArity( rtSummary,
 369                                                  ReachTuple.factory( as.getSummary(),
 370                                                                      true, // muli
 371                                                                      rtOldest.getArity(),
 372                                                                      false // out-of-context
 373                                                                      )
 374                                                  )
 375                            );
 376     }
 377
 378     out = (ReachState) makeCanonical( out );
 379     op2result.put( op, out );
 380     return out;
 381   }
 382
 383
 384
 385   public static ReachSet union( ReachSet rs1,
 386                                 ReachSet rs2 ) {
 387     assert rs1 != null;
 388     assert rs2 != null;
 389     assert rs1.isCanonical();
 390     assert rs2.isCanonical();
 391
 392     CanonicalOp op =
 393       new CanonicalOp( CanonicalOp.REACHSET_UNION_REACHSET,
 394                        rs1,
 395                        rs2 );
 396
 397     Canonical result = op2result.get( op );
 398     if( result != null ) {
 399       return (ReachSet) result;
 400     }
 401
 402     // otherwise, no cached result...
 403     ReachSet out = new ReachSet();
 404     out.reachStates.addAll( rs1.reachStates );
 405     out.reachStates.addAll( rs2.reachStates );
 406
 407     out = (ReachSet) makeCanonical( out );
 408     op2result.put( op, out );
 409     return out;
 410   }
 411
 412   public static ReachSet union( ReachSet   rs,
 413                                 ReachState state ) {
 414
 415     assert rs    != null;
 416     assert state != null;
 417     assert rs.isCanonical();
 418     assert state.isCanonical();
 419
 420     CanonicalOp op =
 421       new CanonicalOp( CanonicalOp.REACHSET_UNION_REACHSTATE,
 422                        rs,
 423                        state );
 424
 425     Canonical result = op2result.get( op );
 426     if( result != null ) {
 427       return (ReachSet) result;
 428     }
 429
 430     // otherwise, no cached result...
 431     ReachSet out = new ReachSet();
 432     out.reachStates.addAll( rs.reachStates );
 433     out.reachStates.add( state );
 434
 435     out = (ReachSet) makeCanonical( out );
 436     op2result.put( op, out );
 437     return out;
 438   }
 439
 440   public static ReachSet intersection( ReachSet rs1,
 441                                        ReachSet rs2 ) {
 442     assert rs1 != null;
 443     assert rs2 != null;
 444     assert rs1.isCanonical();
 445     assert rs2.isCanonical();
 446
 447     CanonicalOp op =
 448       new CanonicalOp( CanonicalOp.REACHSET_INTERSECTION_REACHSET,
 449                        rs1,
 450                        rs2 );
 451
 452     Canonical result = op2result.get( op );
 453     if( result != null ) {
 454       return (ReachSet) result;
 455     }
 456
 457     // otherwise, no cached result...
 458     ReachSet out = new ReachSet();
 459     Iterator<ReachState> itr = rs1.iterator();
 460     while( itr.hasNext() ) {
 461       ReachState state = (ReachState) itr.next();
 462       if( rs2.reachStates.contains( state ) ) {
 463         out.reachStates.add( state );
 464       }
 465     }
 466
 467     out = (ReachSet) makeCanonical( out );
 468     op2result.put( op, out );
 469     return out;
 470   }
 471
 472
 473   public static ReachSet add( ReachSet   rs,
 474                               ReachState state ) {
 475     return union( rs, state );
 476   }
 477
 478   public static ReachSet remove( ReachSet   rs,
 479                                  ReachState state ) {
 480     assert rs    != null;
 481     assert state != null;
 482     assert rs.isCanonical();
 483     assert state.isCanonical();
 484
 485     CanonicalOp op =
 486       new CanonicalOp( CanonicalOp.REACHSET_REMOVE_REACHSTATE,
 487                        rs,
 488                        state );
 489
 490     Canonical result = op2result.get( op );
 491     if( result != null ) {
 492       return (ReachSet) result;
 493     }
 494
 495     // otherwise, no cached result...
 496     ReachSet out = new ReachSet();
 497     out.reachStates.addAll( rs.reachStates );
 498     out.reachStates.remove( state );
 499
 500     out = (ReachSet) makeCanonical( out );
 501     op2result.put( op, out );
 502     return out;
 503   }
 504
 505
 506   public static ReachSet applyChangeSet( ReachSet  rs,
 507                                          ChangeSet cs,
 508                                          boolean   keepSourceState ) {
 509     assert rs != null;
 510     assert cs != null;
 511     assert rs.isCanonical();
 512     assert cs.isCanonical();
 513
 514     // this primitive operand stuff is just a way to
 515     // ensure distinct inputs to a CanonicalOp
 516     int primOperand;
 517     if( keepSourceState ) {
 518       primOperand = 0x1f;
 519     } else {
 520       primOperand = 0x2b;
 521     }
 522
 523     CanonicalOp op =
 524       new CanonicalOp( CanonicalOp.REACHSET_APPLY_CHANGESET,
 525                        rs,
 526                        cs,
 527                        primOperand );
 528
 529     Canonical result = op2result.get( op );
 530     if( result != null ) {
 531       return (ReachSet) result;
 532     }
 533
 534     // otherwise, no cached result...
 535     ReachSet out = new ReachSet();
 536
 537     Iterator<ReachState> stateItr = rs.iterator();
 538     while( stateItr.hasNext() ) {
 539       ReachState state = stateItr.next();
 540
 541       boolean changeFound = false;
 542
 543       Iterator<ChangeTuple> ctItr = cs.iterator();
 544       while( ctItr.hasNext() ) {
 545         ChangeTuple ct = ctItr.next();
 546
 547         if( state.equals( ct.getSetToMatch() ) ) {
 548           out.reachStates.add( ct.getSetToAdd() );
 549           changeFound = true;
 550         }
 551       }
 552
 553       if( keepSourceState || !changeFound ) {
 554         out.reachStates.add( state );
 555       }
 556     }
 557
 558     out = (ReachSet) makeCanonical( out );
 559     op2result.put( op, out );
 560     return out;
 561   }
 562
 563
 564   public static ChangeSet unionUpArityToChangeSet( ReachSet rsO,
 565                                                    ReachSet rsR ) {
 566     assert rsO != null;
 567     assert rsR != null;
 568     assert rsO.isCanonical();
 569     assert rsR.isCanonical();
 570
 571     CanonicalOp op =
 572       new CanonicalOp( CanonicalOp.REACHSET_UNIONTOCHANGESET_REACHSET,
 573                        rsO,
 574                        rsR );
 575
 576     Canonical result = op2result.get( op );
 577     if( result != null ) {
 578       return (ChangeSet) result;
 579     }
 580
 581     // otherwise, no cached result...
 582     ChangeSet out = ChangeSet.factory();
 583
 584     Iterator<ReachState> itrO = rsO.iterator();
 585     while( itrO.hasNext() ) {
 586       ReachState o = itrO.next();
 587
 588       Iterator<ReachState> itrR = rsR.iterator();
 589       while( itrR.hasNext() ) {
 590         ReachState r = itrR.next();
 591
 592         ReachState theUnion = ReachState.factory();
 593
 594         Iterator<ReachTuple> itrRelement = r.iterator();
 595         while( itrRelement.hasNext() ) {
 596           ReachTuple rtR = itrRelement.next();
 597           ReachTuple rtO = o.containsHrnID( rtR.getHrnID(),
 598                                             rtR.isOutOfContext()
 599                                             );
 600           if( rtO != null ) {
 601             theUnion = Canonical.union( theUnion,
 602                                         Canonical.unionArity( rtR,
 603                                                               rtO
 604                                                               )
 605                                         );
 606           } else {
 607             theUnion = Canonical.union( theUnion,
 608                                         rtR
 609                                         );
 610           }
 611         }
 612
 613         Iterator<ReachTuple> itrOelement = o.iterator();
 614         while( itrOelement.hasNext() ) {
 615           ReachTuple rtO = itrOelement.next();
 616           ReachTuple rtR = theUnion.containsHrnID( rtO.getHrnID(),
 617                                                    rtO.isOutOfContext()
 618                                                    );
 619           if( rtR == null ) {
 620             theUnion = Canonical.union( theUnion,
 621                                         rtO
 622                                         );
 623           }
 624         }
 625
 626         if( !theUnion.isEmpty() ) {
 627           out =
 628             Canonical.union( out,
 629                              ChangeSet.factory(
 630                                                ChangeTuple.factory( o, theUnion )
 631                                                 )
 632                              );
 633         }
 634       }
 635     }
 636
 637     assert out.isCanonical();
 638     op2result.put( op, out );
 639     return out;
 640   }
 641
 642
 643   public static ReachSet ageTuplesFrom( ReachSet  rs,
 644                                         AllocSite as ) {
 645     assert rs != null;
 646     assert as != null;
 647     assert rs.isCanonical();
 648     assert as.isCanonical();
 649
 650     CanonicalOp op =
 651       new CanonicalOp( CanonicalOp.REACHSET_AGETUPLESFROM_ALLOCSITE,
 652                        rs,
 653                        as );
 654
 655     Canonical result = op2result.get( op );
 656     if( result != null ) {
 657       return (ReachSet) result;
 658     }
 659
 660     // otherwise, no cached result...
 661     ReachSet out = new ReachSet();
 662
 663     Iterator<ReachState> itrS = rs.iterator();
 664     while( itrS.hasNext() ) {
 665       ReachState state = itrS.next();
 666       out.reachStates.add( Canonical.ageTuplesFrom( state, as ) );
 667     }
 668
 669     out = (ReachSet) makeCanonical( out );
 670     op2result.put( op, out );
 671     return out;
 672   }
 673
 674
 675   public static ReachSet pruneBy( ReachSet rsO,
 676                                   ReachSet rsP ) {
 677     assert rsO != null;
 678     assert rsP != null;
 679     assert rsO.isCanonical();
 680     assert rsP.isCanonical();
 681
 682     CanonicalOp op =
 683       new CanonicalOp( CanonicalOp.REACHSET_PRUNEBY_REACHSET,
 684                        rsO,
 685                        rsP );
 686
 687     Canonical result = op2result.get( op );
 688     if( result != null ) {
 689       return (ReachSet) result;
 690     }
 691
 692     // otherwise, no cached result...
 693     ReachSet out = new ReachSet();
 694
 695     Iterator<ReachState> itrO = rsO.iterator();
 696     while( itrO.hasNext() ) {
 697       ReachState stateO = itrO.next();
 698
 699       boolean subsetExists = false;
 700
 701       Iterator<ReachState> itrP = rsP.iterator();
 702       while( itrP.hasNext() && !subsetExists ) {
 703         ReachState stateP = itrP.next();
 704
 705         if( stateP.isSubset( stateO ) ) {
 706           subsetExists = true;
 707         }
 708       }
 709
 710       if( subsetExists ) {
 711         out.reachStates.add( stateO );
 712       }
 713     }
 714
 715     out = (ReachSet) makeCanonical( out );
 716     op2result.put( op, out );
 717     return out;
 718   }
 719
 720
 721   public static ChangeSet union( ChangeSet cs1,
 722                                  ChangeSet cs2 ) {
 723     assert cs1 != null;
 724     assert cs2 != null;
 725     assert cs1.isCanonical();
 726     assert cs2.isCanonical();
 727
 728     CanonicalOp op =
 729       new CanonicalOp( CanonicalOp.CHANGESET_UNION_CHANGESET,
 730                        cs1,
 731                        cs2 );
 732
 733     Canonical result = op2result.get( op );
 734     if( result != null ) {
 735       return (ChangeSet) result;
 736     }
 737
 738     // otherwise, no cached result...
 739     ChangeSet out = new ChangeSet();
 740     out.changeTuples.addAll( cs1.changeTuples );
 741     out.changeTuples.addAll( cs2.changeTuples );
 742
 743     out = (ChangeSet) makeCanonical( out );
 744     op2result.put( op, out );
 745     return out;
 746   }
 747
 748   public static ChangeSet union( ChangeSet   cs,
 749                                  ChangeTuple ct ) {
 750     assert cs != null;
 751     assert ct != null;
 752     assert cs.isCanonical();
 753     assert ct.isCanonical();
 754
 755     CanonicalOp op =
 756       new CanonicalOp( CanonicalOp.CHANGESET_UNION_CHANGETUPLE,
 757                        cs,
 758                        ct );
 759
 760     Canonical result = op2result.get( op );
 761     if( result != null ) {
 762       return (ChangeSet) result;
 763     }
 764
 765     // otherwise, no cached result...
 766     ChangeSet out = new ChangeSet();
 767     out.changeTuples.addAll( cs.changeTuples );
 768     out.changeTuples.add( ct );
 769
 770     out = (ChangeSet) makeCanonical( out );
 771     op2result.put( op, out );
 772     return out;
 773   }
 774
 775
 776
 777   public static ExistPredSet join( ExistPredSet eps1,
 778                                    ExistPredSet eps2 ) {
 779
 780     assert eps1 != null;
 781     assert eps2 != null;
 782     assert eps1.isCanonical();
 783     assert eps2.isCanonical();
 784
 785     CanonicalOp op =
 786       new CanonicalOp( CanonicalOp.EXISTPREDSET_JOIN_EXISTPREDSET,
 787                        eps1,
 788                        eps2 );
 789
 790     Canonical result = op2result.get( op );
 791     if( result != null ) {
 792       return (ExistPredSet) result;
 793     }
 794
 795     // otherwise, no cached result...
 796     ExistPredSet out = new ExistPredSet();
 797     out.preds.addAll( eps1.preds );
 798     out.preds.addAll( eps2.preds );
 799
 800     out = (ExistPredSet) makeCanonical( out );
 801     op2result.put( op, out );
 802     return out;
 803   }
 804
 805   public static ExistPredSet add( ExistPredSet eps,
 806                                   ExistPred    ep ) {
 807
 808
 809     assert eps != null;
 810     assert ep  != null;
 811     assert eps.isCanonical();
 812     assert ep.isCanonical();
 813
 814     CanonicalOp op =
 815       new CanonicalOp( CanonicalOp.EXISTPREDSET_ADD_EXISTPRED,
 816                        eps,
 817                        ep );
 818
 819     Canonical result = op2result.get( op );
 820     if( result != null ) {
 821       return (ExistPredSet) result;
 822     }
 823
 824     // otherwise, no cached result...
 825     ExistPredSet out = new ExistPredSet();
 826     out.preds.addAll( eps.preds );
 827     out.preds.add( ep );
 828
 829     out = (ExistPredSet) makeCanonical( out );
 830     op2result.put( op, out );
 831     return out;
 832   }
 833
 834
 835
 836   public static ReachSet toCalleeContext( ReachSet  rs,
 837                                           AllocSite as ) {
 838     assert rs != null;
 839     assert as != null;
 840     assert rs.isCanonical();
 841     assert as.isCanonical();
 842
 843     CanonicalOp op =
 844       new CanonicalOp( CanonicalOp.REACHSET_TOCALLEECONTEXT_ALLOCSITE,
 845                        rs,
 846                        as );
 847
 848     Canonical result = op2result.get( op );
 849     if( result != null ) {
 850       return (ReachSet) result;
 851     }
 852
 853     // otherwise, no cached result...
 854     ReachSet out = ReachSet.factory();
 855     Iterator<ReachState> itr = rs.iterator();
 856     while( itr.hasNext() ) {
 857       ReachState state = itr.next();
 858       out = Canonical.add( out,
 859                            Canonical.toCalleeContext( state, as )
 860                            );
 861     }
 862
 863     assert out.isCanonical();
 864     op2result.put( op, out );
 865     return out;
 866   }
 867
 868   public static ReachState toCalleeContext( ReachState state,
 869                                             AllocSite  as ) {
 870     assert state != null;
 871     assert as    != null;
 872     assert state.isCanonical();
 873     assert as.isCanonical();
 874
 875     CanonicalOp op =
 876       new CanonicalOp( CanonicalOp.REACHSTATE_TOCALLEECONTEXT_ALLOCSITE,
 877                        state,
 878                        as );
 879
 880     Canonical result = op2result.get( op );
 881     if( result != null ) {
 882       return (ReachState) result;
 883     }
 884
 885     // otherwise, no cached result...
 886     ReachState out = ReachState.factory();
 887     Iterator<ReachTuple> itr = state.iterator();
 888     while( itr.hasNext() ) {
 889       ReachTuple rt = itr.next();
 890
 891       int age = as.getAgeCategory( rt.getHrnID() );
 892
 893       // this is the current mapping, where 0, 1, 2S were allocated
 894       // in the current context, 0?, 1? and 2S? were allocated in a
 895       // previous context, and we're translating to a future context
 896       //
 897       // 0    -> 0?
 898       // 1    -> 1?
 899       // 2S   -> 2S?
 900       // 2S*  -> 2S?*
 901       //
 902       // 0?   -> 2S?
 903       // 1?   -> 2S?
 904       // 2S?  -> 2S?
 905       // 2S?* -> 2S?*
 906
 907       if( age == AllocSite.AGE_notInThisSite ) {
 908         // things not from the site just go back in
 909         out = Canonical.union( out, rt );
 910
 911       } else if( age == AllocSite.AGE_summary ||
 912                  rt.isOutOfContext()
 913                  ) {
 914         // the in-context summary and all existing out-of-context
 915         // stuff all become
 916         out = Canonical.union( out,
 917                                ReachTuple.factory( as.getSummary(),
 918                                                    true, // multi
 919                                                    rt.getArity(),
 920                                                    true  // out-of-context
 921                                                    )
 922                                );
 923       } else {
 924         // otherwise everything else just goes to an out-of-context
 925         // version, everything else the same
 926         Integer I = as.getAge( rt.getHrnID() );
 927         assert I != null;
 928
 929         assert !rt.isMultiObject();
 930
 931         out = Canonical.union( out,
 932                                ReachTuple.factory( rt.getHrnID(),
 933                                                    rt.isMultiObject(),
 934                                                    rt.getArity(),
 935                                                    true  // out-of-context
 936                                                    )
 937                                );
 938       }
 939     }
 940
 941     assert out.isCanonical();
 942     op2result.put( op, out );
 943     return out;
 944   }
 945
 946
 947 }