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 unionUpArity( 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 attach( ReachState   rs,
 155                                    ExistPredSet preds ) {
 156     assert rs    != null;
 157     assert preds != null;
 158     assert rs.isCanonical();
 159     assert preds.isCanonical();
 160
 161     CanonicalOp op =
 162       new CanonicalOp( CanonicalOp.REACHSTATE_ATTACH_EXISTPREDSET,
 163                        rs,
 164                        preds );
 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( rs.reachTuples );
 174     out.preds = Canonical.join( rs.preds,
 175                                 preds );
 176
 177     out = (ReachState) makeCanonical( out );
 178     op2result.put( op, out );
 179     return out;
 180   }
 181
 182
 183   public static ReachState add( ReachState rs,
 184                                 ReachTuple rt ) {
 185     assert rs != null;
 186     assert rt != null;
 187
 188     // this is only safe if we are certain the new tuple's
 189     // ID doesn't already appear in the reach state
 190     assert rs.containsHrnID( rt.getHrnID(),
 191                              rt.isOutOfContext() ) == null;
 192
 193     CanonicalOp op =
 194       new CanonicalOp( CanonicalOp.REACHSTATE_ADD_REACHTUPLE,
 195                        rs,
 196                        rt );
 197
 198     Canonical result = op2result.get( op );
 199     if( result != null ) {
 200       return (ReachState) result;
 201     }
 202
 203     // otherwise, no cached result...
 204     ReachState out = new ReachState();
 205     out.reachTuples.addAll( rs.reachTuples );
 206     out.reachTuples.add( rt );
 207     out.preds = rs.preds;
 208
 209     out = (ReachState) makeCanonical( out );
 210     op2result.put( op, out );
 211     return out;
 212   }
 213
 214
 215   public static ReachState unionUpArity( ReachState rs1,
 216                                          ReachState rs2 ) {
 217     assert rs1 != null;
 218     assert rs2 != null;
 219     assert rs1.isCanonical();
 220     assert rs2.isCanonical();
 221
 222     CanonicalOp op =
 223       new CanonicalOp( CanonicalOp.REACHSTATE_UNIONUPARITY_REACHSTATE,
 224                        rs1,
 225                        rs2 );
 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
 235     // first add everything from 1, and if it is
 236     // also in 2 take the union of the tuple arities
 237     Iterator<ReachTuple> rtItr = rs1.iterator();
 238     while( rtItr.hasNext() ) {
 239       ReachTuple rt1 = rtItr.next();
 240       ReachTuple rt2 = rs2.containsHrnID( rt1.getHrnID(),
 241                                           rt1.isOutOfContext()
 242                                           );
 243       if( rt2 != null ) {
 244         out.reachTuples.add( unionUpArity( rt1, rt2 ) );
 245       } else {
 246         out.reachTuples.add( rt1 );
 247       }
 248     }
 249
 250     // then add everything in 2 that wasn't in 1
 251     rtItr = rs2.iterator();
 252     while( rtItr.hasNext() ) {
 253       ReachTuple rt2 = rtItr.next();
 254       ReachTuple rt1 = rs1.containsHrnID( rt2.getHrnID(),
 255                                           rt2.isOutOfContext()
 256                                           );
 257       if( rt1 == null ) {
 258         out.reachTuples.add( rt2 );
 259       }
 260     }
 261
 262     out.preds = Canonical.join( rs1.getPreds(),
 263                                 rs2.getPreds()
 264                                 );
 265
 266     out = (ReachState) makeCanonical( out );
 267     op2result.put( op, out );
 268     return out;
 269   }
 270
 271
 272   public static ReachState remove( ReachState rs, ReachTuple rt ) {
 273     assert rs != null;
 274     assert rt != null;
 275
 276     CanonicalOp op =
 277       new CanonicalOp( CanonicalOp.REACHSTATE_REMOVE_REACHTUPLE,
 278                        rs,
 279                        rt );
 280
 281     Canonical result = op2result.get( op );
 282     if( result != null ) {
 283       return (ReachState) result;
 284     }
 285
 286     // otherwise, no cached result...
 287     ReachState out = new ReachState();
 288     out.reachTuples.addAll( rs.reachTuples );
 289     out.reachTuples.remove( rt );
 290     out.preds = rs.preds;
 291
 292     out = (ReachState) makeCanonical( out );
 293     op2result.put( op, out );
 294     return out;
 295   }
 296
 297
 298   public static ReachState ageTuplesFrom( ReachState rs,
 299                                           AllocSite  as ) {
 300     assert rs != null;
 301     assert as != null;
 302     assert rs.isCanonical();
 303     assert as.isCanonical();
 304
 305     CanonicalOp op =
 306       new CanonicalOp( CanonicalOp.REACHSTATE_AGETUPLESFROM_ALLOCSITE,
 307                        rs,
 308                        as );
 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
 318     ReachTuple rtSummary = null;
 319     ReachTuple rtOldest  = null;
 320
 321     Iterator<ReachTuple> rtItr = rs.iterator();
 322     while( rtItr.hasNext() ) {
 323       ReachTuple rt    = rtItr.next();
 324       Integer    hrnID = rt.getHrnID();
 325       int        age   = as.getAgeCategory( hrnID );
 326
 327       // hrnIDs not associated with
 328       // the site should be left alone, and
 329       // those from this site but out-of-context
 330       if( age == AllocSite.AGE_notInThisSite ||
 331           rt.isOutOfContext()
 332           ) {
 333         out.reachTuples.add( rt );
 334
 335       } else if( age == AllocSite.AGE_summary ) {
 336         // remember the summary tuple, but don't add it
 337         // we may combine it with the oldest tuple
 338         rtSummary = rt;
 339
 340       } else if( age == AllocSite.AGE_oldest ) {
 341         // found an oldest hrnID, again just remember
 342         // for later
 343         rtOldest = rt;
 344
 345       } else {
 346         assert age == AllocSite.AGE_in_I;
 347
 348         Integer I = as.getAge( hrnID );
 349         assert I != null;
 350
 351         // otherwise, we change this hrnID to the
 352         // next older hrnID
 353         Integer hrnIDToChangeTo = as.getIthOldest( I + 1 );
 354         ReachTuple rtAged =
 355           Canonical.changeHrnIDTo( rt, hrnIDToChangeTo );
 356         out.reachTuples.add( rtAged );
 357       }
 358     }
 359
 360     // there are four cases to consider here
 361     // 1. we found a summary tuple and no oldest tuple
 362     //    Here we just pass the summary unchanged
 363     // 2. we found an oldest tuple, no summary
 364     //    Make a new, arity-one summary tuple
 365     // 3. we found both a summary and an oldest
 366     //    Merge them by arity
 367     // 4. (not handled) we found neither, do nothing
 368     if( rtSummary != null && rtOldest == null ) {
 369       out.reachTuples.add( rtSummary );
 370
 371     } else if( rtSummary == null && rtOldest != null ) {
 372       out.reachTuples.add( ReachTuple.factory( as.getSummary(),
 373                                                true, // multi
 374                                                rtOldest.getArity(),
 375                                                false // out-of-context
 376                                                )
 377                            );
 378
 379     } else if( rtSummary != null && rtOldest != null ) {
 380       out.reachTuples.add( Canonical.unionUpArity( rtSummary,
 381                                                    ReachTuple.factory( as.getSummary(),
 382                                                                        true, // muli
 383                                                                        rtOldest.getArity(),
 384                                                                        false // out-of-context
 385                                                                        )
 386                                                    )
 387                            );
 388     }
 389
 390     out.preds = rs.preds;
 391
 392     out = (ReachState) makeCanonical( out );
 393     op2result.put( op, out );
 394     return out;
 395   }
 396
 397
 398
 399   public static ReachSet unionORpreds( ReachSet rs1,
 400                                        ReachSet rs2 ) {
 401     assert rs1 != null;
 402     assert rs2 != null;
 403     assert rs1.isCanonical();
 404     assert rs2.isCanonical();
 405
 406     CanonicalOp op =
 407       new CanonicalOp( CanonicalOp.REACHSET_UNIONORPREDS_REACHSET,
 408                        rs1,
 409                        rs2 );
 410
 411     Canonical result = op2result.get( op );
 412     if( result != null ) {
 413       return (ReachSet) result;
 414     }
 415
 416     // otherwise, no cached result...
 417     ReachSet out = new ReachSet();
 418
 419     // first add everything from 1, and if it was also in 2
 420     // take the OR of the predicates
 421     Iterator<ReachState> stateItr = rs1.iterator();
 422     while( stateItr.hasNext() ) {
 423       ReachState state1 = stateItr.next();
 424       ReachState state2 = rs2.containsIgnorePreds( state1 );
 425
 426       if( state2 != null ) {
 427         out.reachStates.add( ReachState.factory( state1.reachTuples,
 428                                                  Canonical.join( state1.preds,
 429                                                                  state2.preds
 430                                                                  )
 431                                                  ) );
 432       } else {
 433         out.reachStates.add( state1 );
 434       }
 435     }
 436
 437     // then add everything in 2 that wasn't in 1
 438     stateItr = rs2.iterator();
 439     while( stateItr.hasNext() ) {
 440       ReachState state2 = stateItr.next();
 441       ReachState state1 = rs1.containsIgnorePreds( state2 );
 442
 443       if( state1 == null ) {
 444         out.reachStates.add( state2 );
 445       }
 446     }
 447
 448     out = (ReachSet) makeCanonical( out );
 449     op2result.put( op, out );
 450     return out;
 451   }
 452
 453
 454   // NOTE: when taking the intersection of two reach sets it
 455   // is possible for a reach state to be in both sets, but
 456   // have different predicates.  Conceptully the best new
 457   // predicate is an AND of the source predicates, but to
 458   // avoid eploding states we'll take an overapproximation
 459   // by preferring the predicates from the state in the FIRST
 460   // set, so order of arguments matters
 461   public static ReachSet intersection( ReachSet rs1,
 462                                        ReachSet rs2 ) {
 463     assert rs1 != null;
 464     assert rs2 != null;
 465     assert rs1.isCanonical();
 466     assert rs2.isCanonical();
 467
 468     CanonicalOp op =
 469       new CanonicalOp( CanonicalOp.REACHSET_INTERSECTION_REACHSET,
 470                        rs1,
 471                        rs2 );
 472
 473     Canonical result = op2result.get( op );
 474     if( result != null ) {
 475       return (ReachSet) result;
 476     }
 477
 478     // otherwise, no cached result...
 479     ReachSet out = new ReachSet();
 480     Iterator<ReachState> itr = rs1.iterator();
 481     while( itr.hasNext() ) {
 482       ReachState state1 = (ReachState) itr.next();
 483       ReachState state2 = rs2.containsIgnorePreds( state1 );
 484       if( state2 != null ) {
 485         // prefer the predicates on state1, an overapproximation
 486         // of state1 preds AND state2 preds
 487         out.reachStates.add( state1 );
 488       }
 489     }
 490
 491     out = (ReachSet) makeCanonical( out );
 492     op2result.put( op, out );
 493     return out;
 494   }
 495
 496
 497   public static ReachSet add( ReachSet   rs,
 498                               ReachState state ) {
 499     return unionORpreds( rs,
 500                          ReachSet.factory( state )
 501                          );
 502   }
 503
 504   public static ReachSet remove( ReachSet   rs,
 505                                  ReachState state ) {
 506     assert rs    != null;
 507     assert state != null;
 508     assert rs.isCanonical();
 509     assert state.isCanonical();
 510
 511     CanonicalOp op =
 512       new CanonicalOp( CanonicalOp.REACHSET_REMOVE_REACHSTATE,
 513                        rs,
 514                        state );
 515
 516     Canonical result = op2result.get( op );
 517     if( result != null ) {
 518       return (ReachSet) result;
 519     }
 520
 521     // otherwise, no cached result...
 522     ReachSet out = new ReachSet();
 523     out.reachStates.addAll( rs.reachStates );
 524     out.reachStates.remove( state );
 525
 526     out = (ReachSet) makeCanonical( out );
 527     op2result.put( op, out );
 528     return out;
 529   }
 530
 531
 532   public static ReachSet applyChangeSet( ReachSet  rs,
 533                                          ChangeSet cs,
 534                                          boolean   keepSourceState ) {
 535     assert rs != null;
 536     assert cs != null;
 537     assert rs.isCanonical();
 538     assert cs.isCanonical();
 539
 540     // this primitive operand stuff is just a way to
 541     // ensure distinct inputs to a CanonicalOp
 542     int primOperand;
 543     if( keepSourceState ) {
 544       primOperand = 0x1f;
 545     } else {
 546       primOperand = 0x2b;
 547     }
 548
 549     CanonicalOp op =
 550       new CanonicalOp( CanonicalOp.REACHSET_APPLY_CHANGESET,
 551                        rs,
 552                        cs,
 553                        primOperand );
 554
 555     Canonical result = op2result.get( op );
 556     if( result != null ) {
 557       return (ReachSet) result;
 558     }
 559
 560     // otherwise, no cached result...
 561     ReachSet out = new ReachSet();
 562
 563     Iterator<ReachState> stateItr = rs.iterator();
 564     while( stateItr.hasNext() ) {
 565       ReachState stateOrig = stateItr.next();
 566
 567       boolean changeFound = false;
 568
 569       Iterator<ChangeTuple> ctItr = cs.iterator();
 570       while( ctItr.hasNext() ) {
 571         ChangeTuple ct = ctItr.next();
 572
 573         if( stateOrig.equalsIgnorePreds( ct.getStateToMatch() ) ) {
 574           // use the new state, but the original predicates
 575           ReachState stateNew =
 576             ReachState.factory( ct.getStateToAdd().reachTuples,
 577                                 stateOrig.preds
 578                                 );
 579           out.reachStates.add( stateNew );
 580           changeFound = true;
 581         }
 582       }
 583
 584       if( keepSourceState || !changeFound ) {
 585         out.reachStates.add( stateOrig );
 586       }
 587     }
 588
 589     out = (ReachSet) makeCanonical( out );
 590     op2result.put( op, out );
 591     return out;
 592   }
 593
 594
 595   public static ChangeSet unionUpArityToChangeSet( ReachSet rsO,
 596                                                    ReachSet rsR ) {
 597     assert rsO != null;
 598     assert rsR != null;
 599     assert rsO.isCanonical();
 600     assert rsR.isCanonical();
 601
 602     CanonicalOp op =
 603       new CanonicalOp( CanonicalOp.REACHSET_UNIONTOCHANGESET_REACHSET,
 604                        rsO,
 605                        rsR );
 606
 607     Canonical result = op2result.get( op );
 608     if( result != null ) {
 609       return (ChangeSet) result;
 610     }
 611
 612     // otherwise, no cached result...
 613     ChangeSet out = ChangeSet.factory();
 614
 615     Iterator<ReachState> itrO = rsO.iterator();
 616     while( itrO.hasNext() ) {
 617       ReachState o = itrO.next();
 618
 619       Iterator<ReachState> itrR = rsR.iterator();
 620       while( itrR.hasNext() ) {
 621         ReachState r = itrR.next();
 622
 623         ReachState theUnion = ReachState.factory();
 624
 625         Iterator<ReachTuple> itrRelement = r.iterator();
 626         while( itrRelement.hasNext() ) {
 627           ReachTuple rtR = itrRelement.next();
 628           ReachTuple rtO = o.containsHrnID( rtR.getHrnID(),
 629                                             rtR.isOutOfContext()
 630                                             );
 631           if( rtO != null ) {
 632             theUnion = Canonical.add( theUnion,
 633                                       Canonical.unionUpArity( rtR,
 634                                                               rtO
 635                                                               )
 636                                       );
 637           } else {
 638             theUnion = Canonical.add( theUnion,
 639                                       rtR
 640                                       );
 641           }
 642         }
 643
 644         Iterator<ReachTuple> itrOelement = o.iterator();
 645         while( itrOelement.hasNext() ) {
 646           ReachTuple rtO = itrOelement.next();
 647           ReachTuple rtR = theUnion.containsHrnID( rtO.getHrnID(),
 648                                                    rtO.isOutOfContext()
 649                                                    );
 650           if( rtR == null ) {
 651             theUnion = Canonical.add( theUnion,
 652                                       rtO
 653                                       );
 654           }
 655         }
 656
 657         if( !theUnion.isEmpty() ) {
 658           out =
 659             Canonical.union( out,
 660                              ChangeSet.factory(
 661                                                ChangeTuple.factory( o, theUnion )
 662                                                 )
 663                              );
 664         }
 665       }
 666     }
 667
 668     assert out.isCanonical();
 669     op2result.put( op, out );
 670     return out;
 671   }
 672
 673
 674   public static ReachSet ageTuplesFrom( ReachSet  rs,
 675                                         AllocSite as ) {
 676     assert rs != null;
 677     assert as != null;
 678     assert rs.isCanonical();
 679     assert as.isCanonical();
 680
 681     CanonicalOp op =
 682       new CanonicalOp( CanonicalOp.REACHSET_AGETUPLESFROM_ALLOCSITE,
 683                        rs,
 684                        as );
 685
 686     Canonical result = op2result.get( op );
 687     if( result != null ) {
 688       return (ReachSet) result;
 689     }
 690
 691     // otherwise, no cached result...
 692     ReachSet out = new ReachSet();
 693
 694     Iterator<ReachState> itrS = rs.iterator();
 695     while( itrS.hasNext() ) {
 696       ReachState state = itrS.next();
 697       out.reachStates.add( Canonical.ageTuplesFrom( state, as ) );
 698     }
 699
 700     out = (ReachSet) makeCanonical( out );
 701     op2result.put( op, out );
 702     return out;
 703   }
 704
 705
 706   public static ReachSet pruneBy( ReachSet rsO,
 707                                   ReachSet rsP ) {
 708     assert rsO != null;
 709     assert rsP != null;
 710     assert rsO.isCanonical();
 711     assert rsP.isCanonical();
 712
 713     CanonicalOp op =
 714       new CanonicalOp( CanonicalOp.REACHSET_PRUNEBY_REACHSET,
 715                        rsO,
 716                        rsP );
 717
 718     Canonical result = op2result.get( op );
 719     if( result != null ) {
 720       return (ReachSet) result;
 721     }
 722
 723     // otherwise, no cached result...
 724     ReachSet out = new ReachSet();
 725
 726     Iterator<ReachState> itrO = rsO.iterator();
 727     while( itrO.hasNext() ) {
 728       ReachState stateO = itrO.next();
 729
 730       boolean subsetExists = false;
 731
 732       Iterator<ReachState> itrP = rsP.iterator();
 733       while( itrP.hasNext() && !subsetExists ) {
 734         ReachState stateP = itrP.next();
 735
 736         if( stateP.isSubset( stateO ) ) {
 737           subsetExists = true;
 738         }
 739       }
 740
 741       if( subsetExists ) {
 742         out.reachStates.add( stateO );
 743       }
 744     }
 745
 746     out = (ReachSet) makeCanonical( out );
 747     op2result.put( op, out );
 748     return out;
 749   }
 750
 751
 752   public static ChangeSet union( ChangeSet cs1,
 753                                  ChangeSet cs2 ) {
 754     assert cs1 != null;
 755     assert cs2 != null;
 756     assert cs1.isCanonical();
 757     assert cs2.isCanonical();
 758
 759     CanonicalOp op =
 760       new CanonicalOp( CanonicalOp.CHANGESET_UNION_CHANGESET,
 761                        cs1,
 762                        cs2 );
 763
 764     Canonical result = op2result.get( op );
 765     if( result != null ) {
 766       return (ChangeSet) result;
 767     }
 768
 769     // otherwise, no cached result...
 770     ChangeSet out = new ChangeSet();
 771     out.changeTuples.addAll( cs1.changeTuples );
 772     out.changeTuples.addAll( cs2.changeTuples );
 773
 774     out = (ChangeSet) makeCanonical( out );
 775     op2result.put( op, out );
 776     return out;
 777   }
 778
 779   public static ChangeSet add( ChangeSet   cs,
 780                                ChangeTuple ct ) {
 781     assert cs != null;
 782     assert ct != null;
 783     assert cs.isCanonical();
 784     assert ct.isCanonical();
 785
 786     CanonicalOp op =
 787       new CanonicalOp( CanonicalOp.CHANGESET_UNION_CHANGETUPLE,
 788                        cs,
 789                        ct );
 790
 791     Canonical result = op2result.get( op );
 792     if( result != null ) {
 793       return (ChangeSet) result;
 794     }
 795
 796     // otherwise, no cached result...
 797     ChangeSet out = new ChangeSet();
 798     out.changeTuples.addAll( cs.changeTuples );
 799     out.changeTuples.add( ct );
 800
 801     out = (ChangeSet) makeCanonical( out );
 802     op2result.put( op, out );
 803     return out;
 804   }
 805
 806
 807
 808   public static ExistPredSet join( ExistPredSet eps1,
 809                                    ExistPredSet eps2 ) {
 810
 811     assert eps1 != null;
 812     assert eps2 != null;
 813     assert eps1.isCanonical();
 814     assert eps2.isCanonical();
 815
 816     CanonicalOp op =
 817       new CanonicalOp( CanonicalOp.EXISTPREDSET_JOIN_EXISTPREDSET,
 818                        eps1,
 819                        eps2 );
 820
 821     Canonical result = op2result.get( op );
 822     if( result != null ) {
 823       return (ExistPredSet) result;
 824     }
 825
 826     // otherwise, no cached result...
 827     ExistPredSet out = new ExistPredSet();
 828     out.preds.addAll( eps1.preds );
 829     out.preds.addAll( eps2.preds );
 830
 831     out = (ExistPredSet) makeCanonical( out );
 832     op2result.put( op, out );
 833     return out;
 834   }
 835
 836   public static ExistPredSet add( ExistPredSet eps,
 837                                   ExistPred    ep ) {
 838
 839
 840     assert eps != null;
 841     assert ep  != null;
 842     assert eps.isCanonical();
 843     assert ep.isCanonical();
 844
 845     CanonicalOp op =
 846       new CanonicalOp( CanonicalOp.EXISTPREDSET_ADD_EXISTPRED,
 847                        eps,
 848                        ep );
 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( eps.preds );
 858     out.preds.add( ep );
 859
 860     out = (ExistPredSet) makeCanonical( out );
 861     op2result.put( op, out );
 862     return out;
 863   }
 864
 865
 866   /*
 867   public static ReachSet toCalleeContext( ReachSet  rs,
 868                                           AllocSite as ) {
 869     assert rs != null;
 870     assert as != null;
 871     assert rs.isCanonical();
 872     assert as.isCanonical();
 873
 874     CanonicalOp op =
 875       new CanonicalOp( CanonicalOp.REACHSET_TOCALLEECONTEXT_ALLOCSITE,
 876                        rs,
 877                        as );
 878
 879     Canonical result = op2result.get( op );
 880     if( result != null ) {
 881       return (ReachSet) result;
 882     }
 883
 884     // otherwise, no cached result...
 885     ReachSet out = ReachSet.factory();
 886     Iterator<ReachState> itr = rs.iterator();
 887     while( itr.hasNext() ) {
 888       ReachState state = itr.next();
 889       out = Canonical.add( out,
 890                            Canonical.toCalleeContext( state, as )
 891                            );
 892     }
 893
 894     assert out.isCanonical();
 895     op2result.put( op, out );
 896     return out;
 897   }
 898   */
 899
 900   /*
 901   public static ReachState toCalleeContext( ReachState state,
 902                                             AllocSite  as ) {
 903     assert state != null;
 904     assert as    != null;
 905     assert state.isCanonical();
 906     assert as.isCanonical();
 907
 908     CanonicalOp op =
 909       new CanonicalOp( CanonicalOp.REACHSTATE_TOCALLEECONTEXT_ALLOCSITE,
 910                        state,
 911                        as );
 912
 913     Canonical result = op2result.get( op );
 914     if( result != null ) {
 915       return (ReachState) result;
 916     }
 917
 918     // otherwise, no cached result...
 919     ReachState out = ReachState.factory();
 920     Iterator<ReachTuple> itr = state.iterator();
 921     while( itr.hasNext() ) {
 922       ReachTuple rt = itr.next();
 923
 924       int age = as.getAgeCategory( rt.getHrnID() );
 925
 926       // this is the current mapping, where 0, 1, 2S were allocated
 927       // in the current context, 0?, 1? and 2S? were allocated in a
 928       // previous context, and we're translating to a future context
 929       //
 930       // 0    -> 0?
 931       // 1    -> 1?
 932       // 2S   -> 2S?
 933       // 2S*  -> 2S?*
 934       //
 935       // 0?   -> 2S?
 936       // 1?   -> 2S?
 937       // 2S?  -> 2S?
 938       // 2S?* -> 2S?*
 939
 940       if( age == AllocSite.AGE_notInThisSite ) {
 941         // things not from the site just go back in
 942         out = Canonical.union( out, rt );
 943
 944       } else if( age == AllocSite.AGE_summary ||
 945                  rt.isOutOfContext()
 946                  ) {
 947         // the in-context summary and all existing out-of-context
 948         // stuff all become
 949         out = Canonical.union( out,
 950                                ReachTuple.factory( as.getSummary(),
 951                                                    true, // multi
 952                                                    rt.getArity(),
 953                                                    true  // out-of-context
 954                                                    )
 955                                );
 956       } else {
 957         // otherwise everything else just goes to an out-of-context
 958         // version, everything else the same
 959         Integer I = as.getAge( rt.getHrnID() );
 960         assert I != null;
 961
 962         assert !rt.isMultiObject();
 963
 964         out = Canonical.union( out,
 965                                ReachTuple.factory( rt.getHrnID(),
 966                                                    rt.isMultiObject(),
 967                                                    rt.getArity(),
 968                                                    true  // out-of-context
 969                                                    )
 970                                );
 971       }
 972     }
 973
 974     out = Canonical.attach( out,
 975                             state.getPreds()
 976                             );
 977
 978     assert out.isCanonical();
 979     op2result.put( op, out );
 980     return out;
 981   }
 982   */
 983
 984
 985   public static ReachSet toCallerContext( ReachSet  rs,
 986                                           AllocSite as ) {
 987     assert rs != null;
 988     assert as != null;
 989     assert rs.isCanonical();
 990     assert as.isCanonical();
 991
 992     CanonicalOp op =
 993       new CanonicalOp( CanonicalOp.REACHSET_TOCALLERCONTEXT_ALLOCSITE,
 994                        rs,
 995                        as );
 996
 997     Canonical result = op2result.get( op );
 998     if( result != null ) {
 999       return (ReachSet) result;
1000     }
1001
1002     // otherwise, no cached result...
1003     ReachSet out = ReachSet.factory();
1004     Iterator<ReachState> itr = rs.iterator();
1005     while( itr.hasNext() ) {
1006       ReachState state = itr.next();
1007       out = Canonical.unionORpreds( out,
1008                                     Canonical.toCallerContext( state, as )
1009                                     );
1010     }
1011
1012     assert out.isCanonical();
1013     op2result.put( op, out );
1014     return out;
1015   }
1016
1017
1018   public static ReachSet toCallerContext( ReachState state,
1019                                           AllocSite  as ) {
1020     assert state != null;
1021     assert as    != null;
1022     assert state.isCanonical();
1023     assert as.isCanonical();
1024
1025     CanonicalOp op =
1026       new CanonicalOp( CanonicalOp.REACHSTATE_TOCALLERCONTEXT_ALLOCSITE,
1027                        state,
1028                        as );
1029
1030     Canonical result = op2result.get( op );
1031     if( result != null ) {
1032       return (ReachSet) result;
1033     }
1034
1035     // otherwise, no cached result...
1036     ReachSet out = ReachSet.factory();
1037
1038     // this method returns a ReachSet instead of a ReachState
1039     // because the companion method, toCallee, translates
1040     // symbols many-to-one, so state->state
1041     // but this method does an ~inverse mapping, one-to-many
1042     // so one state can split into a set of branched states
1043
1044     // 0    -> -0
1045     // 1    -> -1
1046     // 2S   -> -2S
1047     // 2S*  -> -2S*
1048     //
1049     // 0?   -> 0
1050     // 1?   -> 1
1051     // 2S?  -> 2S
1052     //      -> 0?
1053     //      -> 1?
1054     //      -> 2S?
1055     // 2S?* -> {2S*, 2S?*}
1056
1057     boolean found2Sooc = false;
1058
1059     ReachState baseState = ReachState.factory();
1060
1061     Iterator<ReachTuple> itr = state.iterator();
1062     while( itr.hasNext() ) {
1063       ReachTuple rt = itr.next();
1064
1065       int age = as.getAgeCategory( rt.getHrnID() );
1066
1067       if( age == AllocSite.AGE_notInThisSite ) {
1068         // things not from the site just go back in
1069         baseState = Canonical.add( baseState, rt );
1070
1071       } else if( age == AllocSite.AGE_summary ) {
1072
1073         if( rt.isOutOfContext() ) {
1074           // if its out-of-context, we only deal here with the ZERO-OR-MORE
1075           // arity, if ARITY-ONE we'll branch the base state after the loop
1076           if( rt.getArity() == ReachTuple.ARITY_ZEROORMORE ) {
1077             // add two overly conservative symbols to reach state (PUNTING)
1078             baseState = Canonical.add( baseState,
1079                                        ReachTuple.factory( as.getSummary(),
1080                                                            true, // multi
1081                                                            ReachTuple.ARITY_ZEROORMORE,
1082                                                            false // out-of-context
1083                                                            )
1084                                          );
1085             baseState = Canonical.add( baseState,
1086                                        ReachTuple.factory( as.getSummary(),
1087                                                            true, // multi
1088                                                            ReachTuple.ARITY_ZEROORMORE,
1089                                                            true  // out-of-context
1090                                                            )
1091                                        );
1092           } else {
1093             assert rt.getArity() == ReachTuple.ARITY_ONE;
1094             found2Sooc = true;
1095           }
1096
1097         } else {
1098           // the in-context just becomes shadow
1099           baseState = Canonical.add( baseState,
1100                                      ReachTuple.factory( as.getSummaryShadow(),
1101                                                          true, // multi
1102                                                          rt.getArity(),
1103                                                          false  // out-of-context
1104                                                          )
1105                                      );
1106         }
1107
1108
1109       } else {
1110         // otherwise age is in range [0, k]
1111         Integer I = as.getAge( rt.getHrnID() );
1112         assert I != null;
1113         assert !rt.isMultiObject();
1114         assert rt.getArity() == ReachTuple.ARITY_ONE;
1115
1116         if( rt.isOutOfContext() ) {
1117           // becomes the in-context version
1118           baseState = Canonical.add( baseState,
1119                                      ReachTuple.factory( rt.getHrnID(),
1120                                                          false, // multi
1121                                                          ReachTuple.ARITY_ONE,
1122                                                          false  // out-of-context
1123                                                          )
1124                                      );
1125
1126         } else {
1127           // otherwise the ith symbol becomes shadowed
1128           baseState = Canonical.add( baseState,
1129                                      ReachTuple.factory( -rt.getHrnID(),
1130                                                          false, // multi
1131                                                          ReachTuple.ARITY_ONE,
1132                                                          false  // out-of-context
1133                                                          )
1134                                      );
1135         }
1136       }
1137     }
1138
1139     // now either make branches if we have 2S?, or
1140     // the current baseState is the only state we need
1141     if( found2Sooc ) {
1142       // make a branch with every possibility of the one-to-many
1143       // mapping for 2S? appended to the baseState
1144       out = Canonical.add( out,
1145                            Canonical.add( baseState,
1146                                           ReachTuple.factory( as.getSummary(),
1147                                                               true, // multi
1148                                                               ReachTuple.ARITY_ONE,
1149                                                               false  // out-of-context
1150                                                               )
1151                                           )
1152                            );
1153
1154       out = Canonical.add( out,
1155                            Canonical.add( baseState,
1156                                           ReachTuple.factory( as.getSummary(),
1157                                                               true, // multi
1158                                                               ReachTuple.ARITY_ONE,
1159                                                               true  // out-of-context
1160                                                               )
1161                                           )
1162                            );
1163
1164       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1165         out = Canonical.add( out,
1166                              Canonical.add( baseState,
1167                                             ReachTuple.factory( as.getIthOldest( i ),
1168                                                                 false, // multi
1169                                                                 ReachTuple.ARITY_ONE,
1170                                                                 true  // out-of-context
1171                                                                 )
1172                                             )
1173                              );
1174       }
1175
1176     } else {
1177       // just use current baseState
1178       out = Canonical.add( out,
1179                            baseState );
1180     }
1181
1182
1183     assert out.isCanonical();
1184     op2result.put( op, out );
1185     return out;
1186   }
1187
1188
1189   public static ReachSet unshadow( ReachSet  rs,
1190                                    AllocSite as ) {
1191     assert rs != null;
1192     assert as != null;
1193     assert rs.isCanonical();
1194     assert as.isCanonical();
1195
1196     CanonicalOp op =
1197       new CanonicalOp( CanonicalOp.REACHSET_UNSHADOW_ALLOCSITE,
1198                        rs,
1199                        as );
1200
1201     Canonical result = op2result.get( op );
1202     if( result != null ) {
1203       return (ReachSet) result;
1204     }
1205
1206     // otherwise, no cached result...
1207     ReachSet out = ReachSet.factory();
1208     Iterator<ReachState> itr = rs.iterator();
1209     while( itr.hasNext() ) {
1210       ReachState state = itr.next();
1211       out = Canonical.add( out,
1212                            Canonical.unshadow( state, as )
1213                            );
1214     }
1215
1216     assert out.isCanonical();
1217     op2result.put( op, out );
1218     return out;
1219   }
1220
1221   public static ReachState unshadow( ReachState state,
1222                                      AllocSite  as ) {
1223     assert state != null;
1224     assert as    != null;
1225     assert state.isCanonical();
1226     assert as.isCanonical();
1227
1228     CanonicalOp op =
1229       new CanonicalOp( CanonicalOp.REACHSTATE_UNSHADOW_ALLOCSITE,
1230                        state,
1231                        as );
1232
1233     Canonical result = op2result.get( op );
1234     if( result != null ) {
1235       return (ReachState) result;
1236     }
1237
1238     // this is the current mapping, where 0, 1, 2S were allocated
1239     // in the current context, 0?, 1? and 2S? were allocated in a
1240     // previous context, and we're translating to a future context
1241     //
1242     // -0   -> 0
1243     // -1   -> 1
1244     // -2S  -> 2S
1245
1246     // otherwise, no cached result...
1247     ReachState out = ReachState.factory();
1248     Iterator<ReachTuple> itr = state.iterator();
1249     while( itr.hasNext() ) {
1250       ReachTuple rt = itr.next();
1251
1252       int age = as.getShadowAgeCategory( rt.getHrnID() );
1253
1254       if( age == AllocSite.SHADOWAGE_notInThisSite ) {
1255         // things not from the site just go back in
1256         out = Canonical.add( out, rt );
1257
1258       } else {
1259         assert !rt.isOutOfContext();
1260
1261         // otherwise unshadow it
1262         out = Canonical.add( out,
1263                              ReachTuple.factory( -rt.getHrnID(),
1264                                                  rt.isMultiObject(),
1265                                                  rt.getArity(),
1266                                                  false
1267                                                  )
1268                              );
1269       }
1270     }
1271
1272     out = Canonical.attach( out,
1273                             state.getPreds()
1274                             );
1275
1276     assert out.isCanonical();
1277     op2result.put( op, out );
1278     return out;
1279   }
1280
1281
1282
1283   public static ReachState makePredsTrue( ReachState rs ) {
1284     assert rs != null;
1285     assert rs.isCanonical();
1286
1287     // ops require two canonicals, in this case always supply
1288     // the empty reach state as the second, it's never used,
1289     // but makes the hashing happy
1290     CanonicalOp op =
1291       new CanonicalOp( CanonicalOp.REACHSTATE_MAKEPREDSTRUE,
1292                        rs,
1293                        ReachState.factory() );
1294
1295     Canonical result = op2result.get( op );
1296     if( result != null ) {
1297       return (ReachState) result;
1298     }
1299
1300     // otherwise, no cached result...
1301     ReachState out = new ReachState();
1302
1303     // just remake state with the true predicate attached
1304     out.reachTuples.addAll( rs.reachTuples );
1305     out.preds = ExistPredSet.factory( ExistPred.factory() );
1306
1307     out = (ReachState) makeCanonical( out );
1308     op2result.put( op, out );
1309     return out;
1310   }
1311
1312
1313   public static ReachSet makePredsTrue( ReachSet rs ) {
1314     assert rs != null;
1315     assert rs.isCanonical();
1316
1317     // ops require two canonicals, in this case always supply
1318     // the empty reach set as the second, it's never used,
1319     // but makes the hashing happy
1320     CanonicalOp op =
1321       new CanonicalOp( CanonicalOp.REACHSET_MAKEPREDSTRUE,
1322                        rs,
1323                        ReachSet.factory() );
1324
1325     Canonical result = op2result.get( op );
1326     if( result != null ) {
1327       return (ReachSet) result;
1328     }
1329
1330     // otherwise, no cached result...
1331     ReachSet out = ReachSet.factory();
1332     Iterator<ReachState> itr = rs.iterator();
1333     while( itr.hasNext() ) {
1334       ReachState state = itr.next();
1335       out = Canonical.add( out,
1336                            Canonical.makePredsTrue( state )
1337                            );
1338     }
1339
1340     out = (ReachSet) makeCanonical( out );
1341     op2result.put( op, out );
1342     return out;
1343   }
1344
1345 }