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   public static ReachSet intersection( ReachSet rs1,
 455                                        ReachSet rs2 ) {
 456     assert rs1 != null;
 457     assert rs2 != null;
 458     assert rs1.isCanonical();
 459     assert rs2.isCanonical();
 460
 461     CanonicalOp op =
 462       new CanonicalOp( CanonicalOp.REACHSET_INTERSECTION_REACHSET,
 463                        rs1,
 464                        rs2 );
 465
 466     Canonical result = op2result.get( op );
 467     if( result != null ) {
 468       return (ReachSet) result;
 469     }
 470
 471     // otherwise, no cached result...
 472     ReachSet out = new ReachSet();
 473     Iterator<ReachState> itr = rs1.iterator();
 474     while( itr.hasNext() ) {
 475       ReachState state = (ReachState) itr.next();
 476       if( rs2.reachStates.contains( state ) ) {
 477         out.reachStates.add( state );
 478       }
 479     }
 480
 481     out = (ReachSet) makeCanonical( out );
 482     op2result.put( op, out );
 483     return out;
 484   }
 485
 486
 487   public static ReachSet add( ReachSet   rs,
 488                               ReachState state ) {
 489     return unionORpreds( rs,
 490                          ReachSet.factory( state )
 491                          );
 492   }
 493
 494   public static ReachSet remove( ReachSet   rs,
 495                                  ReachState state ) {
 496     assert rs    != null;
 497     assert state != null;
 498     assert rs.isCanonical();
 499     assert state.isCanonical();
 500
 501     CanonicalOp op =
 502       new CanonicalOp( CanonicalOp.REACHSET_REMOVE_REACHSTATE,
 503                        rs,
 504                        state );
 505
 506     Canonical result = op2result.get( op );
 507     if( result != null ) {
 508       return (ReachSet) result;
 509     }
 510
 511     // otherwise, no cached result...
 512     ReachSet out = new ReachSet();
 513     out.reachStates.addAll( rs.reachStates );
 514     out.reachStates.remove( state );
 515
 516     out = (ReachSet) makeCanonical( out );
 517     op2result.put( op, out );
 518     return out;
 519   }
 520
 521
 522   public static ReachSet applyChangeSet( ReachSet  rs,
 523                                          ChangeSet cs,
 524                                          boolean   keepSourceState ) {
 525     assert rs != null;
 526     assert cs != null;
 527     assert rs.isCanonical();
 528     assert cs.isCanonical();
 529
 530     // this primitive operand stuff is just a way to
 531     // ensure distinct inputs to a CanonicalOp
 532     int primOperand;
 533     if( keepSourceState ) {
 534       primOperand = 0x1f;
 535     } else {
 536       primOperand = 0x2b;
 537     }
 538
 539     CanonicalOp op =
 540       new CanonicalOp( CanonicalOp.REACHSET_APPLY_CHANGESET,
 541                        rs,
 542                        cs,
 543                        primOperand );
 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
 553     Iterator<ReachState> stateItr = rs.iterator();
 554     while( stateItr.hasNext() ) {
 555       ReachState state = stateItr.next();
 556
 557       boolean changeFound = false;
 558
 559       Iterator<ChangeTuple> ctItr = cs.iterator();
 560       while( ctItr.hasNext() ) {
 561         ChangeTuple ct = ctItr.next();
 562
 563         if( state.equals( ct.getSetToMatch() ) ) {
 564           out.reachStates.add( ct.getSetToAdd() );
 565           changeFound = true;
 566         }
 567       }
 568
 569       if( keepSourceState || !changeFound ) {
 570         out.reachStates.add( state );
 571       }
 572     }
 573
 574     out = (ReachSet) makeCanonical( out );
 575     op2result.put( op, out );
 576     return out;
 577   }
 578
 579
 580   public static ChangeSet unionUpArityToChangeSet( ReachSet rsO,
 581                                                    ReachSet rsR ) {
 582     assert rsO != null;
 583     assert rsR != null;
 584     assert rsO.isCanonical();
 585     assert rsR.isCanonical();
 586
 587     CanonicalOp op =
 588       new CanonicalOp( CanonicalOp.REACHSET_UNIONTOCHANGESET_REACHSET,
 589                        rsO,
 590                        rsR );
 591
 592     Canonical result = op2result.get( op );
 593     if( result != null ) {
 594       return (ChangeSet) result;
 595     }
 596
 597     // otherwise, no cached result...
 598     ChangeSet out = ChangeSet.factory();
 599
 600     Iterator<ReachState> itrO = rsO.iterator();
 601     while( itrO.hasNext() ) {
 602       ReachState o = itrO.next();
 603
 604       Iterator<ReachState> itrR = rsR.iterator();
 605       while( itrR.hasNext() ) {
 606         ReachState r = itrR.next();
 607
 608         ReachState theUnion = ReachState.factory();
 609
 610         Iterator<ReachTuple> itrRelement = r.iterator();
 611         while( itrRelement.hasNext() ) {
 612           ReachTuple rtR = itrRelement.next();
 613           ReachTuple rtO = o.containsHrnID( rtR.getHrnID(),
 614                                             rtR.isOutOfContext()
 615                                             );
 616           if( rtO != null ) {
 617             theUnion = Canonical.add( theUnion,
 618                                       Canonical.unionUpArity( rtR,
 619                                                               rtO
 620                                                               )
 621                                       );
 622           } else {
 623             theUnion = Canonical.add( theUnion,
 624                                       rtR
 625                                       );
 626           }
 627         }
 628
 629         Iterator<ReachTuple> itrOelement = o.iterator();
 630         while( itrOelement.hasNext() ) {
 631           ReachTuple rtO = itrOelement.next();
 632           ReachTuple rtR = theUnion.containsHrnID( rtO.getHrnID(),
 633                                                    rtO.isOutOfContext()
 634                                                    );
 635           if( rtR == null ) {
 636             theUnion = Canonical.add( theUnion,
 637                                       rtO
 638                                       );
 639           }
 640         }
 641
 642         if( !theUnion.isEmpty() ) {
 643           out =
 644             Canonical.union( out,
 645                              ChangeSet.factory(
 646                                                ChangeTuple.factory( o, theUnion )
 647                                                 )
 648                              );
 649         }
 650       }
 651     }
 652
 653     assert out.isCanonical();
 654     op2result.put( op, out );
 655     return out;
 656   }
 657
 658
 659   public static ReachSet ageTuplesFrom( ReachSet  rs,
 660                                         AllocSite as ) {
 661     assert rs != null;
 662     assert as != null;
 663     assert rs.isCanonical();
 664     assert as.isCanonical();
 665
 666     CanonicalOp op =
 667       new CanonicalOp( CanonicalOp.REACHSET_AGETUPLESFROM_ALLOCSITE,
 668                        rs,
 669                        as );
 670
 671     Canonical result = op2result.get( op );
 672     if( result != null ) {
 673       return (ReachSet) result;
 674     }
 675
 676     // otherwise, no cached result...
 677     ReachSet out = new ReachSet();
 678
 679     Iterator<ReachState> itrS = rs.iterator();
 680     while( itrS.hasNext() ) {
 681       ReachState state = itrS.next();
 682       out.reachStates.add( Canonical.ageTuplesFrom( state, as ) );
 683     }
 684
 685     out = (ReachSet) makeCanonical( out );
 686     op2result.put( op, out );
 687     return out;
 688   }
 689
 690
 691   public static ReachSet pruneBy( ReachSet rsO,
 692                                   ReachSet rsP ) {
 693     assert rsO != null;
 694     assert rsP != null;
 695     assert rsO.isCanonical();
 696     assert rsP.isCanonical();
 697
 698     CanonicalOp op =
 699       new CanonicalOp( CanonicalOp.REACHSET_PRUNEBY_REACHSET,
 700                        rsO,
 701                        rsP );
 702
 703     Canonical result = op2result.get( op );
 704     if( result != null ) {
 705       return (ReachSet) result;
 706     }
 707
 708     // otherwise, no cached result...
 709     ReachSet out = new ReachSet();
 710
 711     Iterator<ReachState> itrO = rsO.iterator();
 712     while( itrO.hasNext() ) {
 713       ReachState stateO = itrO.next();
 714
 715       boolean subsetExists = false;
 716
 717       Iterator<ReachState> itrP = rsP.iterator();
 718       while( itrP.hasNext() && !subsetExists ) {
 719         ReachState stateP = itrP.next();
 720
 721         if( stateP.isSubset( stateO ) ) {
 722           subsetExists = true;
 723         }
 724       }
 725
 726       if( subsetExists ) {
 727         out.reachStates.add( stateO );
 728       }
 729     }
 730
 731     out = (ReachSet) makeCanonical( out );
 732     op2result.put( op, out );
 733     return out;
 734   }
 735
 736
 737   public static ChangeSet union( ChangeSet cs1,
 738                                  ChangeSet cs2 ) {
 739     assert cs1 != null;
 740     assert cs2 != null;
 741     assert cs1.isCanonical();
 742     assert cs2.isCanonical();
 743
 744     CanonicalOp op =
 745       new CanonicalOp( CanonicalOp.CHANGESET_UNION_CHANGESET,
 746                        cs1,
 747                        cs2 );
 748
 749     Canonical result = op2result.get( op );
 750     if( result != null ) {
 751       return (ChangeSet) result;
 752     }
 753
 754     // otherwise, no cached result...
 755     ChangeSet out = new ChangeSet();
 756     out.changeTuples.addAll( cs1.changeTuples );
 757     out.changeTuples.addAll( cs2.changeTuples );
 758
 759     out = (ChangeSet) makeCanonical( out );
 760     op2result.put( op, out );
 761     return out;
 762   }
 763
 764   public static ChangeSet union( ChangeSet   cs,
 765                                  ChangeTuple ct ) {
 766     assert cs != null;
 767     assert ct != null;
 768     assert cs.isCanonical();
 769     assert ct.isCanonical();
 770
 771     CanonicalOp op =
 772       new CanonicalOp( CanonicalOp.CHANGESET_UNION_CHANGETUPLE,
 773                        cs,
 774                        ct );
 775
 776     Canonical result = op2result.get( op );
 777     if( result != null ) {
 778       return (ChangeSet) result;
 779     }
 780
 781     // otherwise, no cached result...
 782     ChangeSet out = new ChangeSet();
 783     out.changeTuples.addAll( cs.changeTuples );
 784     out.changeTuples.add( ct );
 785
 786     out = (ChangeSet) makeCanonical( out );
 787     op2result.put( op, out );
 788     return out;
 789   }
 790
 791
 792
 793   public static ExistPredSet join( ExistPredSet eps1,
 794                                    ExistPredSet eps2 ) {
 795
 796     assert eps1 != null;
 797     assert eps2 != null;
 798     assert eps1.isCanonical();
 799     assert eps2.isCanonical();
 800
 801     CanonicalOp op =
 802       new CanonicalOp( CanonicalOp.EXISTPREDSET_JOIN_EXISTPREDSET,
 803                        eps1,
 804                        eps2 );
 805
 806     Canonical result = op2result.get( op );
 807     if( result != null ) {
 808       return (ExistPredSet) result;
 809     }
 810
 811     // otherwise, no cached result...
 812     ExistPredSet out = new ExistPredSet();
 813     out.preds.addAll( eps1.preds );
 814     out.preds.addAll( eps2.preds );
 815
 816     out = (ExistPredSet) makeCanonical( out );
 817     op2result.put( op, out );
 818     return out;
 819   }
 820
 821   public static ExistPredSet add( ExistPredSet eps,
 822                                   ExistPred    ep ) {
 823
 824
 825     assert eps != null;
 826     assert ep  != null;
 827     assert eps.isCanonical();
 828     assert ep.isCanonical();
 829
 830     CanonicalOp op =
 831       new CanonicalOp( CanonicalOp.EXISTPREDSET_ADD_EXISTPRED,
 832                        eps,
 833                        ep );
 834
 835     Canonical result = op2result.get( op );
 836     if( result != null ) {
 837       return (ExistPredSet) result;
 838     }
 839
 840     // otherwise, no cached result...
 841     ExistPredSet out = new ExistPredSet();
 842     out.preds.addAll( eps.preds );
 843     out.preds.add( ep );
 844
 845     out = (ExistPredSet) makeCanonical( out );
 846     op2result.put( op, out );
 847     return out;
 848   }
 849
 850
 851   /*
 852   public static ReachSet toCalleeContext( ReachSet  rs,
 853                                           AllocSite as ) {
 854     assert rs != null;
 855     assert as != null;
 856     assert rs.isCanonical();
 857     assert as.isCanonical();
 858
 859     CanonicalOp op =
 860       new CanonicalOp( CanonicalOp.REACHSET_TOCALLEECONTEXT_ALLOCSITE,
 861                        rs,
 862                        as );
 863
 864     Canonical result = op2result.get( op );
 865     if( result != null ) {
 866       return (ReachSet) result;
 867     }
 868
 869     // otherwise, no cached result...
 870     ReachSet out = ReachSet.factory();
 871     Iterator<ReachState> itr = rs.iterator();
 872     while( itr.hasNext() ) {
 873       ReachState state = itr.next();
 874       out = Canonical.add( out,
 875                            Canonical.toCalleeContext( state, as )
 876                            );
 877     }
 878
 879     assert out.isCanonical();
 880     op2result.put( op, out );
 881     return out;
 882   }
 883   */
 884
 885   /*
 886   public static ReachState toCalleeContext( ReachState state,
 887                                             AllocSite  as ) {
 888     assert state != null;
 889     assert as    != null;
 890     assert state.isCanonical();
 891     assert as.isCanonical();
 892
 893     CanonicalOp op =
 894       new CanonicalOp( CanonicalOp.REACHSTATE_TOCALLEECONTEXT_ALLOCSITE,
 895                        state,
 896                        as );
 897
 898     Canonical result = op2result.get( op );
 899     if( result != null ) {
 900       return (ReachState) result;
 901     }
 902
 903     // otherwise, no cached result...
 904     ReachState out = ReachState.factory();
 905     Iterator<ReachTuple> itr = state.iterator();
 906     while( itr.hasNext() ) {
 907       ReachTuple rt = itr.next();
 908
 909       int age = as.getAgeCategory( rt.getHrnID() );
 910
 911       // this is the current mapping, where 0, 1, 2S were allocated
 912       // in the current context, 0?, 1? and 2S? were allocated in a
 913       // previous context, and we're translating to a future context
 914       //
 915       // 0    -> 0?
 916       // 1    -> 1?
 917       // 2S   -> 2S?
 918       // 2S*  -> 2S?*
 919       //
 920       // 0?   -> 2S?
 921       // 1?   -> 2S?
 922       // 2S?  -> 2S?
 923       // 2S?* -> 2S?*
 924
 925       if( age == AllocSite.AGE_notInThisSite ) {
 926         // things not from the site just go back in
 927         out = Canonical.union( out, rt );
 928
 929       } else if( age == AllocSite.AGE_summary ||
 930                  rt.isOutOfContext()
 931                  ) {
 932         // the in-context summary and all existing out-of-context
 933         // stuff all become
 934         out = Canonical.union( out,
 935                                ReachTuple.factory( as.getSummary(),
 936                                                    true, // multi
 937                                                    rt.getArity(),
 938                                                    true  // out-of-context
 939                                                    )
 940                                );
 941       } else {
 942         // otherwise everything else just goes to an out-of-context
 943         // version, everything else the same
 944         Integer I = as.getAge( rt.getHrnID() );
 945         assert I != null;
 946
 947         assert !rt.isMultiObject();
 948
 949         out = Canonical.union( out,
 950                                ReachTuple.factory( rt.getHrnID(),
 951                                                    rt.isMultiObject(),
 952                                                    rt.getArity(),
 953                                                    true  // out-of-context
 954                                                    )
 955                                );
 956       }
 957     }
 958
 959     out = Canonical.attach( out,
 960                             state.getPreds()
 961                             );
 962
 963     assert out.isCanonical();
 964     op2result.put( op, out );
 965     return out;
 966   }
 967   */
 968
 969
 970   public static ReachSet toCallerContext( ReachSet  rs,
 971                                           AllocSite as ) {
 972     assert rs != null;
 973     assert as != null;
 974     assert rs.isCanonical();
 975     assert as.isCanonical();
 976
 977     CanonicalOp op =
 978       new CanonicalOp( CanonicalOp.REACHSET_TOCALLERCONTEXT_ALLOCSITE,
 979                        rs,
 980                        as );
 981
 982     Canonical result = op2result.get( op );
 983     if( result != null ) {
 984       return (ReachSet) result;
 985     }
 986
 987     // otherwise, no cached result...
 988     ReachSet out = ReachSet.factory();
 989     Iterator<ReachState> itr = rs.iterator();
 990     while( itr.hasNext() ) {
 991       ReachState state = itr.next();
 992       out = Canonical.unionORpreds( out,
 993                                     Canonical.toCallerContext( state, as )
 994                                     );
 995     }
 996
 997     assert out.isCanonical();
 998     op2result.put( op, out );
 999     return out;
1000   }
1001
1002
1003   public static ReachSet toCallerContext( ReachState state,
1004                                           AllocSite  as ) {
1005     assert state != null;
1006     assert as    != null;
1007     assert state.isCanonical();
1008     assert as.isCanonical();
1009
1010     CanonicalOp op =
1011       new CanonicalOp( CanonicalOp.REACHSTATE_TOCALLERCONTEXT_ALLOCSITE,
1012                        state,
1013                        as );
1014
1015     Canonical result = op2result.get( op );
1016     if( result != null ) {
1017       return (ReachSet) result;
1018     }
1019
1020     // otherwise, no cached result...
1021     ReachSet out = ReachSet.factory();
1022
1023     // this method returns a ReachSet instead of a ReachState
1024     // because the companion method, toCallee, translates
1025     // symbols many-to-one, so state->state
1026     // but this method does an ~inverse mapping, one-to-many
1027     // so one state can split into a set of branched states
1028
1029     // 0    -> -0
1030     // 1    -> -1
1031     // 2S   -> -2S
1032     // 2S*  -> -2S*
1033     //
1034     // 0?   -> 0
1035     // 1?   -> 1
1036     // 2S?  -> 2S
1037     //      -> 0?
1038     //      -> 1?
1039     //      -> 2S?
1040     // 2S?* -> {2S*, 2S?*}
1041
1042     boolean found2Sooc = false;
1043
1044     ReachState baseState = ReachState.factory();
1045
1046     Iterator<ReachTuple> itr = state.iterator();
1047     while( itr.hasNext() ) {
1048       ReachTuple rt = itr.next();
1049
1050       int age = as.getAgeCategory( rt.getHrnID() );
1051
1052       if( age == AllocSite.AGE_notInThisSite ) {
1053         // things not from the site just go back in
1054         baseState = Canonical.add( baseState, rt );
1055
1056       } else if( age == AllocSite.AGE_summary ) {
1057
1058         if( rt.isOutOfContext() ) {
1059           // if its out-of-context, we only deal here with the ZERO-OR-MORE
1060           // arity, if ARITY-ONE we'll branch the base state after the loop
1061           if( rt.getArity() == ReachTuple.ARITY_ZEROORMORE ) {
1062             // add two overly conservative symbols to reach state (PUNTING)
1063             baseState = Canonical.add( baseState,
1064                                        ReachTuple.factory( as.getSummary(),
1065                                                            true, // multi
1066                                                            ReachTuple.ARITY_ZEROORMORE,
1067                                                            false // out-of-context
1068                                                            )
1069                                          );
1070             baseState = Canonical.add( baseState,
1071                                        ReachTuple.factory( as.getSummary(),
1072                                                            true, // multi
1073                                                            ReachTuple.ARITY_ZEROORMORE,
1074                                                            true  // out-of-context
1075                                                            )
1076                                        );
1077           } else {
1078             assert rt.getArity() == ReachTuple.ARITY_ONE;
1079             found2Sooc = true;
1080           }
1081
1082         } else {
1083           // the in-context just becomes shadow
1084           baseState = Canonical.add( baseState,
1085                                      ReachTuple.factory( as.getSummaryShadow(),
1086                                                          true, // multi
1087                                                          rt.getArity(),
1088                                                          false  // out-of-context
1089                                                          )
1090                                      );
1091         }
1092
1093
1094       } else {
1095         // otherwise age is in range [0, k]
1096         Integer I = as.getAge( rt.getHrnID() );
1097         assert I != null;
1098         assert !rt.isMultiObject();
1099         assert rt.getArity() == ReachTuple.ARITY_ONE;
1100
1101         if( rt.isOutOfContext() ) {
1102           // becomes the in-context version
1103           baseState = Canonical.add( baseState,
1104                                      ReachTuple.factory( rt.getHrnID(),
1105                                                          false, // multi
1106                                                          ReachTuple.ARITY_ONE,
1107                                                          false  // out-of-context
1108                                                          )
1109                                      );
1110
1111         } else {
1112           // otherwise the ith symbol becomes shadowed
1113           baseState = Canonical.add( baseState,
1114                                      ReachTuple.factory( -rt.getHrnID(),
1115                                                          false, // multi
1116                                                          ReachTuple.ARITY_ONE,
1117                                                          false  // out-of-context
1118                                                          )
1119                                      );
1120         }
1121       }
1122     }
1123
1124     // now either make branches if we have 2S?, or
1125     // the current baseState is the only state we need
1126     if( found2Sooc ) {
1127       // make a branch with every possibility of the one-to-many
1128       // mapping for 2S? appended to the baseState
1129       out = Canonical.add( out,
1130                            Canonical.add( baseState,
1131                                           ReachTuple.factory( as.getSummary(),
1132                                                               true, // multi
1133                                                               ReachTuple.ARITY_ONE,
1134                                                               false  // out-of-context
1135                                                               )
1136                                           )
1137                            );
1138
1139       out = Canonical.add( out,
1140                            Canonical.add( baseState,
1141                                           ReachTuple.factory( as.getSummary(),
1142                                                               true, // multi
1143                                                               ReachTuple.ARITY_ONE,
1144                                                               true  // out-of-context
1145                                                               )
1146                                           )
1147                            );
1148
1149       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1150         out = Canonical.add( out,
1151                              Canonical.add( baseState,
1152                                             ReachTuple.factory( as.getIthOldest( i ),
1153                                                                 false, // multi
1154                                                                 ReachTuple.ARITY_ONE,
1155                                                                 true  // out-of-context
1156                                                                 )
1157                                             )
1158                              );
1159       }
1160
1161     } else {
1162       // just use current baseState
1163       out = Canonical.add( out,
1164                            baseState );
1165     }
1166
1167
1168     assert out.isCanonical();
1169     op2result.put( op, out );
1170     return out;
1171   }
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181   public static ReachSet unshadow( ReachSet  rs,
1182                                    AllocSite as ) {
1183     assert rs != null;
1184     assert as != null;
1185     assert rs.isCanonical();
1186     assert as.isCanonical();
1187
1188     CanonicalOp op =
1189       new CanonicalOp( CanonicalOp.REACHSET_UNSHADOW_ALLOCSITE,
1190                        rs,
1191                        as );
1192
1193     Canonical result = op2result.get( op );
1194     if( result != null ) {
1195       return (ReachSet) result;
1196     }
1197
1198     // otherwise, no cached result...
1199     ReachSet out = ReachSet.factory();
1200     Iterator<ReachState> itr = rs.iterator();
1201     while( itr.hasNext() ) {
1202       ReachState state = itr.next();
1203       out = Canonical.add( out,
1204                            Canonical.unshadow( state, as )
1205                            );
1206     }
1207
1208     assert out.isCanonical();
1209     op2result.put( op, out );
1210     return out;
1211   }
1212
1213   public static ReachState unshadow( ReachState state,
1214                                      AllocSite  as ) {
1215     assert state != null;
1216     assert as    != null;
1217     assert state.isCanonical();
1218     assert as.isCanonical();
1219
1220     CanonicalOp op =
1221       new CanonicalOp( CanonicalOp.REACHSTATE_UNSHADOW_ALLOCSITE,
1222                        state,
1223                        as );
1224
1225     Canonical result = op2result.get( op );
1226     if( result != null ) {
1227       return (ReachState) result;
1228     }
1229
1230     // this is the current mapping, where 0, 1, 2S were allocated
1231     // in the current context, 0?, 1? and 2S? were allocated in a
1232     // previous context, and we're translating to a future context
1233     //
1234     // -0   -> 0
1235     // -1   -> 1
1236     // -2S  -> 2S
1237
1238     // otherwise, no cached result...
1239     ReachState out = ReachState.factory();
1240     Iterator<ReachTuple> itr = state.iterator();
1241     while( itr.hasNext() ) {
1242       ReachTuple rt = itr.next();
1243
1244       int age = as.getShadowAgeCategory( rt.getHrnID() );
1245
1246       if( age == AllocSite.SHADOWAGE_notInThisSite ) {
1247         // things not from the site just go back in
1248         out = Canonical.add( out, rt );
1249
1250       } else {
1251         assert !rt.isOutOfContext();
1252
1253         // otherwise unshadow it
1254         out = Canonical.add( out,
1255                              ReachTuple.factory( -rt.getHrnID(),
1256                                                  rt.isMultiObject(),
1257                                                  rt.getArity(),
1258                                                  false
1259                                                  )
1260                              );
1261       }
1262     }
1263
1264     out = Canonical.attach( out,
1265                             state.getPreds()
1266                             );
1267
1268     assert out.isCanonical();
1269     op2result.put( op, out );
1270     return out;
1271   }
1272
1273 }