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