1 package Analysis.Disjoint;
9 ////////////////////////////////////////////////
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!
20 // What this boils down to is that the only normally constructed
21 // object in a canonical operation should be the result out.
23 ////////////////////////////////////////////////
26 abstract public class Canonical {
28 // for generating unique canonical values
29 private static int canonicalCount = 1;
31 // the canon of objects
32 private static Hashtable<Canonical, Canonical>
33 canon = new Hashtable<Canonical, Canonical>();
37 public static Canonical makeCanonical( Canonical c ) {
39 if( canon.containsKey( c ) ) {
40 return canon.get( c );
43 c.canonicalValue = canonicalCount;
50 // any Canonical with value still 0 is NOT CANONICAL!
51 private int canonicalValue = 0;
53 public boolean isCanonical() {
54 return canonicalValue != 0;
57 public int getCanonicalValue() {
59 return canonicalValue;
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();
70 private boolean hasHash = false;
72 final public int hashCode() {
73 int hash = hashCodeSpecific();
76 if( oldHash != hash ) {
77 throw new Error( "A CANONICAL HASH CHANGED" );
90 // mapping of a non-trivial operation to its result
91 private static Hashtable<CanonicalOp, Canonical>
92 op2result = new Hashtable<CanonicalOp, Canonical>();
96 ///////////////////////////////////////////////////////////
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
103 ///////////////////////////////////////////////////////////
106 // not weighty, don't bother with caching
107 public static ReachTuple unionArity( ReachTuple rt1,
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;
119 if( rt1.isMultiObject ) {
120 // on two non-ZERO arity multi regions, union arity is always
122 out = ReachTuple.factory( rt1.hrnID,
124 ReachTuple.ARITY_ZEROORMORE,
125 rt1.isOutOfContext );
128 // a single object region can only be ARITY_ONE (or zero by
130 assert rt1.arity == ReachTuple.ARITY_ONE;
134 assert out.isCanonical();
138 // not weighty, no caching
139 public static ReachTuple changeHrnIDTo( ReachTuple rt,
140 Integer hrnIDToChangeTo ) {
142 assert hrnIDToChangeTo != null;
144 ReachTuple out = ReachTuple.factory( hrnIDToChangeTo,
149 assert out.isCanonical();
154 public static ReachState union( ReachState rs1,
158 assert rs1.isCanonical();
159 assert rs2.isCanonical();
162 new CanonicalOp( CanonicalOp.REACHSTATE_UNION_REACHSTATE,
166 Canonical result = op2result.get( op );
167 if( result != null ) {
168 return (ReachState) result;
171 // otherwise, no cached result...
172 ReachState out = new ReachState();
173 out.reachTuples.addAll( rs1.reachTuples );
174 out.reachTuples.addAll( rs2.reachTuples );
176 out = (ReachState) makeCanonical( out );
177 op2result.put( op, out );
181 // this is just a convenience version of above
182 public static ReachState union( ReachState rs,
188 new CanonicalOp( CanonicalOp.REACHSTATE_UNION_REACHTUPLE,
192 Canonical result = op2result.get( op );
193 if( result != null ) {
194 return (ReachState) result;
197 // otherwise, no cached result...
198 ReachState out = new ReachState();
199 out.reachTuples.addAll( rs.reachTuples );
200 out.reachTuples.add( rt );
202 out = (ReachState) makeCanonical( out );
203 op2result.put( op, out );
208 public static ReachState unionUpArity( ReachState rs1,
212 assert rs1.isCanonical();
213 assert rs2.isCanonical();
216 new CanonicalOp( CanonicalOp.REACHSTATE_UNIONUPARITY_REACHSTATE,
220 Canonical result = op2result.get( op );
221 if( result != null ) {
222 return (ReachState) result;
225 // otherwise, no cached result...
226 ReachState out = new ReachState();
228 Iterator<ReachTuple> rtItr = rs1.iterator();
229 while( rtItr.hasNext() ) {
230 ReachTuple rt1 = rtItr.next();
231 ReachTuple rt2 = rs2.containsHrnID( rt1.getHrnID(),
235 out.reachTuples.add( unionArity( rt1, rt2 ) );
237 out.reachTuples.add( rt1 );
241 rtItr = rs2.iterator();
242 while( rtItr.hasNext() ) {
243 ReachTuple rt2 = rtItr.next();
244 ReachTuple rto = out.containsHrnID( rt2.getHrnID(),
248 out.reachTuples.add( rto );
252 out = (ReachState) makeCanonical( out );
253 op2result.put( op, out );
257 public static ReachState add( ReachState rs, ReachTuple rt ) {
258 return union( rs, rt );
261 public static ReachState remove( ReachState rs, ReachTuple rt ) {
266 new CanonicalOp( CanonicalOp.REACHSTATE_REMOVE_REACHTUPLE,
270 Canonical result = op2result.get( op );
271 if( result != null ) {
272 return (ReachState) result;
275 // otherwise, no cached result...
276 ReachState out = new ReachState();
277 out.reachTuples.addAll( rs.reachTuples );
278 out.reachTuples.remove( rt );
280 out = (ReachState) makeCanonical( out );
281 op2result.put( op, out );
286 public static ReachState ageTuplesFrom( ReachState rs,
290 assert rs.isCanonical();
291 assert as.isCanonical();
294 new CanonicalOp( CanonicalOp.REACHSTATE_AGETUPLESFROM_ALLOCSITE,
298 Canonical result = op2result.get( op );
299 if( result != null ) {
300 return (ReachState) result;
303 // otherwise, no cached result...
304 ReachState out = new ReachState();
306 ReachTuple rtSummary = null;
307 ReachTuple rtOldest = null;
309 Iterator<ReachTuple> rtItr = rs.iterator();
310 while( rtItr.hasNext() ) {
311 ReachTuple rt = rtItr.next();
312 Integer hrnID = rt.getHrnID();
313 int age = as.getAgeCategory( hrnID );
315 // hrnIDs not associated with
316 // the site should be left alone, and
317 // those from this site but out-of-context
318 if( age == AllocSite.AGE_notInThisSite ||
321 out.reachTuples.add( rt );
323 } else if( age == AllocSite.AGE_summary ) {
324 // remember the summary tuple, but don't add it
325 // we may combine it with the oldest tuple
328 } else if( age == AllocSite.AGE_oldest ) {
329 // found an oldest hrnID, again just remember
334 assert age == AllocSite.AGE_in_I;
336 Integer I = as.getAge( hrnID );
339 // otherwise, we change this hrnID to the
341 Integer hrnIDToChangeTo = as.getIthOldest( I + 1 );
343 Canonical.changeHrnIDTo( rt, hrnIDToChangeTo );
344 out.reachTuples.add( rtAged );
348 // there are four cases to consider here
349 // 1. we found a summary tuple and no oldest tuple
350 // Here we just pass the summary unchanged
351 // 2. we found an oldest tuple, no summary
352 // Make a new, arity-one summary tuple
353 // 3. we found both a summary and an oldest
354 // Merge them by arity
355 // 4. (not handled) we found neither, do nothing
356 if( rtSummary != null && rtOldest == null ) {
357 out.reachTuples.add( rtSummary );
359 } else if( rtSummary == null && rtOldest != null ) {
360 out.reachTuples.add( ReachTuple.factory( as.getSummary(),
363 false // out-of-context
367 } else if( rtSummary != null && rtOldest != null ) {
368 out.reachTuples.add( Canonical.unionArity( rtSummary,
369 ReachTuple.factory( as.getSummary(),
372 false // out-of-context
378 out = (ReachState) makeCanonical( out );
379 op2result.put( op, out );
385 public static ReachSet union( ReachSet rs1,
389 assert rs1.isCanonical();
390 assert rs2.isCanonical();
393 new CanonicalOp( CanonicalOp.REACHSET_UNION_REACHSET,
397 Canonical result = op2result.get( op );
398 if( result != null ) {
399 return (ReachSet) result;
402 // otherwise, no cached result...
403 ReachSet out = new ReachSet();
404 out.reachStates.addAll( rs1.reachStates );
405 out.reachStates.addAll( rs2.reachStates );
407 out = (ReachSet) makeCanonical( out );
408 op2result.put( op, out );
412 public static ReachSet union( ReachSet rs,
416 assert state != null;
417 assert rs.isCanonical();
418 assert state.isCanonical();
421 new CanonicalOp( CanonicalOp.REACHSET_UNION_REACHSTATE,
425 Canonical result = op2result.get( op );
426 if( result != null ) {
427 return (ReachSet) result;
430 // otherwise, no cached result...
431 ReachSet out = new ReachSet();
432 out.reachStates.addAll( rs.reachStates );
433 out.reachStates.add( state );
435 out = (ReachSet) makeCanonical( out );
436 op2result.put( op, out );
440 public static ReachSet intersection( ReachSet rs1,
444 assert rs1.isCanonical();
445 assert rs2.isCanonical();
448 new CanonicalOp( CanonicalOp.REACHSET_INTERSECTION_REACHSET,
452 Canonical result = op2result.get( op );
453 if( result != null ) {
454 return (ReachSet) result;
457 // otherwise, no cached result...
458 ReachSet out = new ReachSet();
459 Iterator<ReachState> itr = rs1.iterator();
460 while( itr.hasNext() ) {
461 ReachState state = (ReachState) itr.next();
462 if( rs2.reachStates.contains( state ) ) {
463 out.reachStates.add( state );
467 out = (ReachSet) makeCanonical( out );
468 op2result.put( op, out );
473 public static ReachSet add( ReachSet rs,
475 return union( rs, state );
478 public static ReachSet remove( ReachSet rs,
481 assert state != null;
482 assert rs.isCanonical();
483 assert state.isCanonical();
486 new CanonicalOp( CanonicalOp.REACHSET_REMOVE_REACHSTATE,
490 Canonical result = op2result.get( op );
491 if( result != null ) {
492 return (ReachSet) result;
495 // otherwise, no cached result...
496 ReachSet out = new ReachSet();
497 out.reachStates.addAll( rs.reachStates );
498 out.reachStates.remove( state );
500 out = (ReachSet) makeCanonical( out );
501 op2result.put( op, out );
506 public static ReachSet applyChangeSet( ReachSet rs,
508 boolean keepSourceState ) {
511 assert rs.isCanonical();
512 assert cs.isCanonical();
514 // this primitive operand stuff is just a way to
515 // ensure distinct inputs to a CanonicalOp
517 if( keepSourceState ) {
524 new CanonicalOp( CanonicalOp.REACHSET_APPLY_CHANGESET,
529 Canonical result = op2result.get( op );
530 if( result != null ) {
531 return (ReachSet) result;
534 // otherwise, no cached result...
535 ReachSet out = new ReachSet();
537 Iterator<ReachState> stateItr = rs.iterator();
538 while( stateItr.hasNext() ) {
539 ReachState state = stateItr.next();
541 boolean changeFound = false;
543 Iterator<ChangeTuple> ctItr = cs.iterator();
544 while( ctItr.hasNext() ) {
545 ChangeTuple ct = ctItr.next();
547 if( state.equals( ct.getSetToMatch() ) ) {
548 out.reachStates.add( ct.getSetToAdd() );
553 if( keepSourceState || !changeFound ) {
554 out.reachStates.add( state );
558 out = (ReachSet) makeCanonical( out );
559 op2result.put( op, out );
564 public static ChangeSet unionUpArityToChangeSet( ReachSet rsO,
568 assert rsO.isCanonical();
569 assert rsR.isCanonical();
572 new CanonicalOp( CanonicalOp.REACHSET_UNIONTOCHANGESET_REACHSET,
576 Canonical result = op2result.get( op );
577 if( result != null ) {
578 return (ChangeSet) result;
581 // otherwise, no cached result...
582 ChangeSet out = ChangeSet.factory();
584 Iterator<ReachState> itrO = rsO.iterator();
585 while( itrO.hasNext() ) {
586 ReachState o = itrO.next();
588 Iterator<ReachState> itrR = rsR.iterator();
589 while( itrR.hasNext() ) {
590 ReachState r = itrR.next();
592 ReachState theUnion = ReachState.factory();
594 Iterator<ReachTuple> itrRelement = r.iterator();
595 while( itrRelement.hasNext() ) {
596 ReachTuple rtR = itrRelement.next();
597 ReachTuple rtO = o.containsHrnID( rtR.getHrnID(),
601 theUnion = Canonical.union( theUnion,
602 Canonical.unionArity( rtR,
607 theUnion = Canonical.union( theUnion,
613 Iterator<ReachTuple> itrOelement = o.iterator();
614 while( itrOelement.hasNext() ) {
615 ReachTuple rtO = itrOelement.next();
616 ReachTuple rtR = theUnion.containsHrnID( rtO.getHrnID(),
620 theUnion = Canonical.union( theUnion,
626 if( !theUnion.isEmpty() ) {
628 Canonical.union( out,
630 ChangeTuple.factory( o, theUnion )
637 assert out.isCanonical();
638 op2result.put( op, out );
643 public static ReachSet ageTuplesFrom( ReachSet rs,
647 assert rs.isCanonical();
648 assert as.isCanonical();
651 new CanonicalOp( CanonicalOp.REACHSET_AGETUPLESFROM_ALLOCSITE,
655 Canonical result = op2result.get( op );
656 if( result != null ) {
657 return (ReachSet) result;
660 // otherwise, no cached result...
661 ReachSet out = new ReachSet();
663 Iterator<ReachState> itrS = rs.iterator();
664 while( itrS.hasNext() ) {
665 ReachState state = itrS.next();
666 out.reachStates.add( Canonical.ageTuplesFrom( state, as ) );
669 out = (ReachSet) makeCanonical( out );
670 op2result.put( op, out );
675 public static ReachSet pruneBy( ReachSet rsO,
679 assert rsO.isCanonical();
680 assert rsP.isCanonical();
683 new CanonicalOp( CanonicalOp.REACHSET_PRUNEBY_REACHSET,
687 Canonical result = op2result.get( op );
688 if( result != null ) {
689 return (ReachSet) result;
692 // otherwise, no cached result...
693 ReachSet out = new ReachSet();
695 Iterator<ReachState> itrO = rsO.iterator();
696 while( itrO.hasNext() ) {
697 ReachState stateO = itrO.next();
699 boolean subsetExists = false;
701 Iterator<ReachState> itrP = rsP.iterator();
702 while( itrP.hasNext() && !subsetExists ) {
703 ReachState stateP = itrP.next();
705 if( stateP.isSubset( stateO ) ) {
711 out.reachStates.add( stateO );
715 out = (ReachSet) makeCanonical( out );
716 op2result.put( op, out );
721 public static ChangeSet union( ChangeSet cs1,
725 assert cs1.isCanonical();
726 assert cs2.isCanonical();
729 new CanonicalOp( CanonicalOp.CHANGESET_UNION_CHANGESET,
733 Canonical result = op2result.get( op );
734 if( result != null ) {
735 return (ChangeSet) result;
738 // otherwise, no cached result...
739 ChangeSet out = new ChangeSet();
740 out.changeTuples.addAll( cs1.changeTuples );
741 out.changeTuples.addAll( cs2.changeTuples );
743 out = (ChangeSet) makeCanonical( out );
744 op2result.put( op, out );
748 public static ChangeSet union( ChangeSet cs,
752 assert cs.isCanonical();
753 assert ct.isCanonical();
756 new CanonicalOp( CanonicalOp.CHANGESET_UNION_CHANGETUPLE,
760 Canonical result = op2result.get( op );
761 if( result != null ) {
762 return (ChangeSet) result;
765 // otherwise, no cached result...
766 ChangeSet out = new ChangeSet();
767 out.changeTuples.addAll( cs.changeTuples );
768 out.changeTuples.add( ct );
770 out = (ChangeSet) makeCanonical( out );
771 op2result.put( op, out );
777 public static ExistPredSet join( ExistPredSet eps1,
778 ExistPredSet eps2 ) {
782 assert eps1.isCanonical();
783 assert eps2.isCanonical();
786 new CanonicalOp( CanonicalOp.EXISTPREDSET_JOIN_EXISTPREDSET,
790 Canonical result = op2result.get( op );
791 if( result != null ) {
792 return (ExistPredSet) result;
795 // otherwise, no cached result...
796 ExistPredSet out = new ExistPredSet();
797 out.preds.addAll( eps1.preds );
798 out.preds.addAll( eps2.preds );
800 out = (ExistPredSet) makeCanonical( out );
801 op2result.put( op, out );
805 public static ExistPredSet add( ExistPredSet eps,
811 assert eps.isCanonical();
812 assert ep.isCanonical();
815 new CanonicalOp( CanonicalOp.EXISTPREDSET_ADD_EXISTPRED,
819 Canonical result = op2result.get( op );
820 if( result != null ) {
821 return (ExistPredSet) result;
824 // otherwise, no cached result...
825 ExistPredSet out = new ExistPredSet();
826 out.preds.addAll( eps.preds );
829 out = (ExistPredSet) makeCanonical( out );
830 op2result.put( op, out );
836 public static ReachSet toCalleeContext( ReachSet rs,
840 assert rs.isCanonical();
841 assert as.isCanonical();
844 new CanonicalOp( CanonicalOp.REACHSET_TOCALLEECONTEXT_ALLOCSITE,
848 Canonical result = op2result.get( op );
849 if( result != null ) {
850 return (ReachSet) result;
853 // otherwise, no cached result...
854 ReachSet out = ReachSet.factory();
855 Iterator<ReachState> itr = rs.iterator();
856 while( itr.hasNext() ) {
857 ReachState state = itr.next();
858 out = Canonical.add( out,
859 Canonical.toCalleeContext( state, as )
863 assert out.isCanonical();
864 op2result.put( op, out );
868 public static ReachState toCalleeContext( ReachState state,
870 assert state != null;
872 assert state.isCanonical();
873 assert as.isCanonical();
876 new CanonicalOp( CanonicalOp.REACHSTATE_TOCALLEECONTEXT_ALLOCSITE,
880 Canonical result = op2result.get( op );
881 if( result != null ) {
882 return (ReachState) result;
885 // otherwise, no cached result...
886 ReachState out = ReachState.factory();
887 Iterator<ReachTuple> itr = state.iterator();
888 while( itr.hasNext() ) {
889 ReachTuple rt = itr.next();
891 int age = as.getAgeCategory( rt.getHrnID() );
893 // this is the current mapping, where 0, 1, 2S were allocated
894 // in the current context, 0?, 1? and 2S? were allocated in a
895 // previous context, and we're translating to a future context
907 if( age == AllocSite.AGE_notInThisSite ) {
908 // things not from the site just go back in
909 out = Canonical.union( out, rt );
911 } else if( age == AllocSite.AGE_summary ||
914 // the in-context summary and all existing out-of-context
916 out = Canonical.union( out,
917 ReachTuple.factory( as.getSummary(),
920 true // out-of-context
924 // otherwise everything else just goes to an out-of-context
925 // version, everything else the same
926 Integer I = as.getAge( rt.getHrnID() );
929 assert !rt.isMultiObject();
931 out = Canonical.union( out,
932 ReachTuple.factory( rt.getHrnID(),
935 true // out-of-context
941 assert out.isCanonical();
942 op2result.put( op, out );