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