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 unionUpArity( 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 attach( ReachState rs,
155 ExistPredSet preds ) {
157 assert preds != null;
158 assert rs.isCanonical();
159 assert preds.isCanonical();
162 new CanonicalOp( CanonicalOp.REACHSTATE_ATTACH_EXISTPREDSET,
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( rs.reachTuples );
174 out.preds = Canonical.join( rs.preds,
177 out = (ReachState) makeCanonical( out );
178 op2result.put( op, out );
183 public static ReachState add( ReachState rs,
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;
194 new CanonicalOp( CanonicalOp.REACHSTATE_ADD_REACHTUPLE,
198 Canonical result = op2result.get( op );
199 if( result != null ) {
200 return (ReachState) result;
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;
209 out = (ReachState) makeCanonical( out );
210 op2result.put( op, out );
215 public static ReachState unionUpArity( ReachState rs1,
219 assert rs1.isCanonical();
220 assert rs2.isCanonical();
223 new CanonicalOp( CanonicalOp.REACHSTATE_UNIONUPARITY_REACHSTATE,
227 Canonical result = op2result.get( op );
228 if( result != null ) {
229 return (ReachState) result;
232 // otherwise, no cached result...
233 ReachState out = new ReachState();
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(),
244 out.reachTuples.add( unionUpArity( rt1, rt2 ) );
246 out.reachTuples.add( rt1 );
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(),
258 out.reachTuples.add( rt2 );
262 out.preds = Canonical.join( rs1.getPreds(),
266 out = (ReachState) makeCanonical( out );
267 op2result.put( op, out );
272 public static ReachState remove( ReachState rs, ReachTuple rt ) {
277 new CanonicalOp( CanonicalOp.REACHSTATE_REMOVE_REACHTUPLE,
281 Canonical result = op2result.get( op );
282 if( result != null ) {
283 return (ReachState) result;
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;
292 out = (ReachState) makeCanonical( out );
293 op2result.put( op, out );
298 public static ReachState ageTuplesFrom( ReachState rs,
302 assert rs.isCanonical();
303 assert as.isCanonical();
306 new CanonicalOp( CanonicalOp.REACHSTATE_AGETUPLESFROM_ALLOCSITE,
310 Canonical result = op2result.get( op );
311 if( result != null ) {
312 return (ReachState) result;
315 // otherwise, no cached result...
316 ReachState out = new ReachState();
318 ReachTuple rtSummary = null;
319 ReachTuple rtOldest = null;
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 );
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 ||
333 out.reachTuples.add( rt );
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
340 } else if( age == AllocSite.AGE_oldest ) {
341 // found an oldest hrnID, again just remember
346 assert age == AllocSite.AGE_in_I;
348 Integer I = as.getAge( hrnID );
351 // otherwise, we change this hrnID to the
353 Integer hrnIDToChangeTo = as.getIthOldest( I + 1 );
355 Canonical.changeHrnIDTo( rt, hrnIDToChangeTo );
356 out.reachTuples.add( rtAged );
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 );
371 } else if( rtSummary == null && rtOldest != null ) {
372 out.reachTuples.add( ReachTuple.factory( as.getSummary(),
375 false // out-of-context
379 } else if( rtSummary != null && rtOldest != null ) {
380 out.reachTuples.add( Canonical.unionUpArity( rtSummary,
381 ReachTuple.factory( as.getSummary(),
384 false // out-of-context
390 out.preds = rs.preds;
392 out = (ReachState) makeCanonical( out );
393 op2result.put( op, out );
399 public static ReachSet unionORpreds( ReachSet rs1,
403 assert rs1.isCanonical();
404 assert rs2.isCanonical();
407 new CanonicalOp( CanonicalOp.REACHSET_UNIONORPREDS_REACHSET,
411 Canonical result = op2result.get( op );
412 if( result != null ) {
413 return (ReachSet) result;
416 // otherwise, no cached result...
417 ReachSet out = new ReachSet();
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 );
426 if( state2 != null ) {
427 out.reachStates.add( ReachState.factory( state1.reachTuples,
428 Canonical.join( state1.preds,
433 out.reachStates.add( state1 );
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 );
443 if( state1 == null ) {
444 out.reachStates.add( state2 );
448 out = (ReachSet) makeCanonical( out );
449 op2result.put( op, out );
454 // NOTE: when taking the intersection of two reach sets it
455 // is possible for a reach state to be in both sets, but
456 // have different predicates. Conceptully the best new
457 // predicate is an AND of the source predicates, but to
458 // avoid eploding states we'll take an overapproximation
459 // by preferring the predicates from the state in the FIRST
460 // set, so order of arguments matters
461 public static ReachSet intersection( ReachSet rs1,
465 assert rs1.isCanonical();
466 assert rs2.isCanonical();
469 new CanonicalOp( CanonicalOp.REACHSET_INTERSECTION_REACHSET,
473 Canonical result = op2result.get( op );
474 if( result != null ) {
475 return (ReachSet) result;
478 // otherwise, no cached result...
479 ReachSet out = new ReachSet();
480 Iterator<ReachState> itr = rs1.iterator();
481 while( itr.hasNext() ) {
482 ReachState state1 = (ReachState) itr.next();
483 ReachState state2 = rs2.containsIgnorePreds( state1 );
484 if( state2 != null ) {
485 // prefer the predicates on state1, an overapproximation
486 // of state1 preds AND state2 preds
487 out.reachStates.add( state1 );
491 out = (ReachSet) makeCanonical( out );
492 op2result.put( op, out );
497 public static ReachSet add( ReachSet rs,
499 return unionORpreds( rs,
500 ReachSet.factory( state )
504 public static ReachSet remove( ReachSet rs,
507 assert state != null;
508 assert rs.isCanonical();
509 assert state.isCanonical();
512 new CanonicalOp( CanonicalOp.REACHSET_REMOVE_REACHSTATE,
516 Canonical result = op2result.get( op );
517 if( result != null ) {
518 return (ReachSet) result;
521 // otherwise, no cached result...
522 ReachSet out = new ReachSet();
523 out.reachStates.addAll( rs.reachStates );
524 out.reachStates.remove( state );
526 out = (ReachSet) makeCanonical( out );
527 op2result.put( op, out );
532 public static ReachSet applyChangeSet( ReachSet rs,
534 boolean keepSourceState ) {
537 assert rs.isCanonical();
538 assert cs.isCanonical();
540 // this primitive operand stuff is just a way to
541 // ensure distinct inputs to a CanonicalOp
543 if( keepSourceState ) {
550 new CanonicalOp( CanonicalOp.REACHSET_APPLY_CHANGESET,
555 Canonical result = op2result.get( op );
556 if( result != null ) {
557 return (ReachSet) result;
560 // otherwise, no cached result...
561 ReachSet out = new ReachSet();
563 Iterator<ReachState> stateItr = rs.iterator();
564 while( stateItr.hasNext() ) {
565 ReachState stateOrig = stateItr.next();
567 boolean changeFound = false;
569 Iterator<ChangeTuple> ctItr = cs.iterator();
570 while( ctItr.hasNext() ) {
571 ChangeTuple ct = ctItr.next();
573 if( stateOrig.equalsIgnorePreds( ct.getStateToMatch() ) ) {
574 // use the new state, but the original predicates
575 ReachState stateNew =
576 ReachState.factory( ct.getStateToAdd().reachTuples,
579 out.reachStates.add( stateNew );
584 if( keepSourceState || !changeFound ) {
585 out.reachStates.add( stateOrig );
589 out = (ReachSet) makeCanonical( out );
590 op2result.put( op, out );
595 public static ChangeSet unionUpArityToChangeSet( ReachSet rsO,
599 assert rsO.isCanonical();
600 assert rsR.isCanonical();
603 new CanonicalOp( CanonicalOp.REACHSET_UNIONTOCHANGESET_REACHSET,
607 Canonical result = op2result.get( op );
608 if( result != null ) {
609 return (ChangeSet) result;
612 // otherwise, no cached result...
613 ChangeSet out = ChangeSet.factory();
615 Iterator<ReachState> itrO = rsO.iterator();
616 while( itrO.hasNext() ) {
617 ReachState o = itrO.next();
619 Iterator<ReachState> itrR = rsR.iterator();
620 while( itrR.hasNext() ) {
621 ReachState r = itrR.next();
623 ReachState theUnion = ReachState.factory();
625 Iterator<ReachTuple> itrRelement = r.iterator();
626 while( itrRelement.hasNext() ) {
627 ReachTuple rtR = itrRelement.next();
628 ReachTuple rtO = o.containsHrnID( rtR.getHrnID(),
632 theUnion = Canonical.add( theUnion,
633 Canonical.unionUpArity( rtR,
638 theUnion = Canonical.add( theUnion,
644 Iterator<ReachTuple> itrOelement = o.iterator();
645 while( itrOelement.hasNext() ) {
646 ReachTuple rtO = itrOelement.next();
647 ReachTuple rtR = theUnion.containsHrnID( rtO.getHrnID(),
651 theUnion = Canonical.add( theUnion,
657 if( !theUnion.isEmpty() ) {
659 Canonical.union( out,
661 ChangeTuple.factory( o, theUnion )
668 assert out.isCanonical();
669 op2result.put( op, out );
674 public static ReachSet ageTuplesFrom( ReachSet rs,
678 assert rs.isCanonical();
679 assert as.isCanonical();
682 new CanonicalOp( CanonicalOp.REACHSET_AGETUPLESFROM_ALLOCSITE,
686 Canonical result = op2result.get( op );
687 if( result != null ) {
688 return (ReachSet) result;
691 // otherwise, no cached result...
692 ReachSet out = new ReachSet();
694 Iterator<ReachState> itrS = rs.iterator();
695 while( itrS.hasNext() ) {
696 ReachState state = itrS.next();
697 out.reachStates.add( Canonical.ageTuplesFrom( state, as ) );
700 out = (ReachSet) makeCanonical( out );
701 op2result.put( op, out );
706 public static ReachSet pruneBy( ReachSet rsO,
710 assert rsO.isCanonical();
711 assert rsP.isCanonical();
714 new CanonicalOp( CanonicalOp.REACHSET_PRUNEBY_REACHSET,
718 Canonical result = op2result.get( op );
719 if( result != null ) {
720 return (ReachSet) result;
723 // otherwise, no cached result...
724 ReachSet out = new ReachSet();
726 Iterator<ReachState> itrO = rsO.iterator();
727 while( itrO.hasNext() ) {
728 ReachState stateO = itrO.next();
730 boolean subsetExists = false;
732 Iterator<ReachState> itrP = rsP.iterator();
733 while( itrP.hasNext() && !subsetExists ) {
734 ReachState stateP = itrP.next();
736 if( stateP.isSubset( stateO ) ) {
742 out.reachStates.add( stateO );
746 out = (ReachSet) makeCanonical( out );
747 op2result.put( op, out );
752 public static ChangeSet union( ChangeSet cs1,
756 assert cs1.isCanonical();
757 assert cs2.isCanonical();
760 new CanonicalOp( CanonicalOp.CHANGESET_UNION_CHANGESET,
764 Canonical result = op2result.get( op );
765 if( result != null ) {
766 return (ChangeSet) result;
769 // otherwise, no cached result...
770 ChangeSet out = new ChangeSet();
771 out.changeTuples.addAll( cs1.changeTuples );
772 out.changeTuples.addAll( cs2.changeTuples );
774 out = (ChangeSet) makeCanonical( out );
775 op2result.put( op, out );
779 public static ChangeSet add( ChangeSet cs,
783 assert cs.isCanonical();
784 assert ct.isCanonical();
787 new CanonicalOp( CanonicalOp.CHANGESET_UNION_CHANGETUPLE,
791 Canonical result = op2result.get( op );
792 if( result != null ) {
793 return (ChangeSet) result;
796 // otherwise, no cached result...
797 ChangeSet out = new ChangeSet();
798 out.changeTuples.addAll( cs.changeTuples );
799 out.changeTuples.add( ct );
801 out = (ChangeSet) makeCanonical( out );
802 op2result.put( op, out );
808 public static ExistPredSet join( ExistPredSet eps1,
809 ExistPredSet eps2 ) {
813 assert eps1.isCanonical();
814 assert eps2.isCanonical();
817 new CanonicalOp( CanonicalOp.EXISTPREDSET_JOIN_EXISTPREDSET,
821 Canonical result = op2result.get( op );
822 if( result != null ) {
823 return (ExistPredSet) result;
826 // otherwise, no cached result...
827 ExistPredSet out = new ExistPredSet();
828 out.preds.addAll( eps1.preds );
829 out.preds.addAll( eps2.preds );
831 out = (ExistPredSet) makeCanonical( out );
832 op2result.put( op, out );
836 public static ExistPredSet add( ExistPredSet eps,
842 assert eps.isCanonical();
843 assert ep.isCanonical();
846 new CanonicalOp( CanonicalOp.EXISTPREDSET_ADD_EXISTPRED,
850 Canonical result = op2result.get( op );
851 if( result != null ) {
852 return (ExistPredSet) result;
855 // otherwise, no cached result...
856 ExistPredSet out = new ExistPredSet();
857 out.preds.addAll( eps.preds );
860 out = (ExistPredSet) makeCanonical( out );
861 op2result.put( op, out );
867 public static ReachSet toCalleeContext( ReachSet rs,
871 assert rs.isCanonical();
872 assert as.isCanonical();
875 new CanonicalOp( CanonicalOp.REACHSET_TOCALLEECONTEXT_ALLOCSITE,
879 Canonical result = op2result.get( op );
880 if( result != null ) {
881 return (ReachSet) result;
884 // otherwise, no cached result...
885 ReachSet out = ReachSet.factory();
886 Iterator<ReachState> itr = rs.iterator();
887 while( itr.hasNext() ) {
888 ReachState state = itr.next();
889 out = Canonical.add( out,
890 Canonical.toCalleeContext( state, as )
894 assert out.isCanonical();
895 op2result.put( op, out );
901 public static ReachState toCalleeContext( ReachState state,
903 assert state != null;
905 assert state.isCanonical();
906 assert as.isCanonical();
909 new CanonicalOp( CanonicalOp.REACHSTATE_TOCALLEECONTEXT_ALLOCSITE,
913 Canonical result = op2result.get( op );
914 if( result != null ) {
915 return (ReachState) result;
918 // otherwise, no cached result...
919 ReachState out = ReachState.factory();
920 Iterator<ReachTuple> itr = state.iterator();
921 while( itr.hasNext() ) {
922 ReachTuple rt = itr.next();
924 int age = as.getAgeCategory( rt.getHrnID() );
926 // this is the current mapping, where 0, 1, 2S were allocated
927 // in the current context, 0?, 1? and 2S? were allocated in a
928 // previous context, and we're translating to a future context
940 if( age == AllocSite.AGE_notInThisSite ) {
941 // things not from the site just go back in
942 out = Canonical.union( out, rt );
944 } else if( age == AllocSite.AGE_summary ||
947 // the in-context summary and all existing out-of-context
949 out = Canonical.union( out,
950 ReachTuple.factory( as.getSummary(),
953 true // out-of-context
957 // otherwise everything else just goes to an out-of-context
958 // version, everything else the same
959 Integer I = as.getAge( rt.getHrnID() );
962 assert !rt.isMultiObject();
964 out = Canonical.union( out,
965 ReachTuple.factory( rt.getHrnID(),
968 true // out-of-context
974 out = Canonical.attach( out,
978 assert out.isCanonical();
979 op2result.put( op, out );
985 public static ReachSet toCallerContext( ReachSet rs,
989 assert rs.isCanonical();
990 assert as.isCanonical();
993 new CanonicalOp( CanonicalOp.REACHSET_TOCALLERCONTEXT_ALLOCSITE,
997 Canonical result = op2result.get( op );
998 if( result != null ) {
999 return (ReachSet) result;
1002 // otherwise, no cached result...
1003 ReachSet out = ReachSet.factory();
1004 Iterator<ReachState> itr = rs.iterator();
1005 while( itr.hasNext() ) {
1006 ReachState state = itr.next();
1007 out = Canonical.unionORpreds( out,
1008 Canonical.toCallerContext( state, as )
1012 assert out.isCanonical();
1013 op2result.put( op, out );
1018 public static ReachSet toCallerContext( ReachState state,
1020 assert state != null;
1022 assert state.isCanonical();
1023 assert as.isCanonical();
1026 new CanonicalOp( CanonicalOp.REACHSTATE_TOCALLERCONTEXT_ALLOCSITE,
1030 Canonical result = op2result.get( op );
1031 if( result != null ) {
1032 return (ReachSet) result;
1035 // otherwise, no cached result...
1036 ReachSet out = ReachSet.factory();
1038 // this method returns a ReachSet instead of a ReachState
1039 // because the companion method, toCallee, translates
1040 // symbols many-to-one, so state->state
1041 // but this method does an ~inverse mapping, one-to-many
1042 // so one state can split into a set of branched states
1055 // 2S?* -> {2S*, 2S?*}
1057 boolean found2Sooc = false;
1059 ReachState baseState = ReachState.factory();
1061 Iterator<ReachTuple> itr = state.iterator();
1062 while( itr.hasNext() ) {
1063 ReachTuple rt = itr.next();
1065 int age = as.getAgeCategory( rt.getHrnID() );
1067 if( age == AllocSite.AGE_notInThisSite ) {
1068 // things not from the site just go back in
1069 baseState = Canonical.add( baseState, rt );
1071 } else if( age == AllocSite.AGE_summary ) {
1073 if( rt.isOutOfContext() ) {
1074 // if its out-of-context, we only deal here with the ZERO-OR-MORE
1075 // arity, if ARITY-ONE we'll branch the base state after the loop
1076 if( rt.getArity() == ReachTuple.ARITY_ZEROORMORE ) {
1077 // add two overly conservative symbols to reach state (PUNTING)
1078 baseState = Canonical.add( baseState,
1079 ReachTuple.factory( as.getSummary(),
1081 ReachTuple.ARITY_ZEROORMORE,
1082 false // out-of-context
1085 baseState = Canonical.add( baseState,
1086 ReachTuple.factory( as.getSummary(),
1088 ReachTuple.ARITY_ZEROORMORE,
1089 true // out-of-context
1093 assert rt.getArity() == ReachTuple.ARITY_ONE;
1098 // the in-context just becomes shadow
1099 baseState = Canonical.add( baseState,
1100 ReachTuple.factory( as.getSummaryShadow(),
1103 false // out-of-context
1110 // otherwise age is in range [0, k]
1111 Integer I = as.getAge( rt.getHrnID() );
1113 assert !rt.isMultiObject();
1114 assert rt.getArity() == ReachTuple.ARITY_ONE;
1116 if( rt.isOutOfContext() ) {
1117 // becomes the in-context version
1118 baseState = Canonical.add( baseState,
1119 ReachTuple.factory( rt.getHrnID(),
1121 ReachTuple.ARITY_ONE,
1122 false // out-of-context
1127 // otherwise the ith symbol becomes shadowed
1128 baseState = Canonical.add( baseState,
1129 ReachTuple.factory( -rt.getHrnID(),
1131 ReachTuple.ARITY_ONE,
1132 false // out-of-context
1139 // now either make branches if we have 2S?, or
1140 // the current baseState is the only state we need
1142 // make a branch with every possibility of the one-to-many
1143 // mapping for 2S? appended to the baseState
1144 out = Canonical.add( out,
1145 Canonical.add( baseState,
1146 ReachTuple.factory( as.getSummary(),
1148 ReachTuple.ARITY_ONE,
1149 false // out-of-context
1154 out = Canonical.add( out,
1155 Canonical.add( baseState,
1156 ReachTuple.factory( as.getSummary(),
1158 ReachTuple.ARITY_ONE,
1159 true // out-of-context
1164 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1165 out = Canonical.add( out,
1166 Canonical.add( baseState,
1167 ReachTuple.factory( as.getIthOldest( i ),
1169 ReachTuple.ARITY_ONE,
1170 true // out-of-context
1177 // just use current baseState
1178 out = Canonical.add( out,
1183 assert out.isCanonical();
1184 op2result.put( op, out );
1189 public static ReachSet unshadow( ReachSet rs,
1193 assert rs.isCanonical();
1194 assert as.isCanonical();
1197 new CanonicalOp( CanonicalOp.REACHSET_UNSHADOW_ALLOCSITE,
1201 Canonical result = op2result.get( op );
1202 if( result != null ) {
1203 return (ReachSet) result;
1206 // otherwise, no cached result...
1207 ReachSet out = ReachSet.factory();
1208 Iterator<ReachState> itr = rs.iterator();
1209 while( itr.hasNext() ) {
1210 ReachState state = itr.next();
1211 out = Canonical.add( out,
1212 Canonical.unshadow( state, as )
1216 assert out.isCanonical();
1217 op2result.put( op, out );
1221 public static ReachState unshadow( ReachState state,
1223 assert state != null;
1225 assert state.isCanonical();
1226 assert as.isCanonical();
1229 new CanonicalOp( CanonicalOp.REACHSTATE_UNSHADOW_ALLOCSITE,
1233 Canonical result = op2result.get( op );
1234 if( result != null ) {
1235 return (ReachState) result;
1238 // this is the current mapping, where 0, 1, 2S were allocated
1239 // in the current context, 0?, 1? and 2S? were allocated in a
1240 // previous context, and we're translating to a future context
1246 // otherwise, no cached result...
1247 ReachState out = ReachState.factory();
1248 Iterator<ReachTuple> itr = state.iterator();
1249 while( itr.hasNext() ) {
1250 ReachTuple rt = itr.next();
1252 int age = as.getShadowAgeCategory( rt.getHrnID() );
1254 if( age == AllocSite.SHADOWAGE_notInThisSite ) {
1255 // things not from the site just go back in
1256 out = Canonical.add( out, rt );
1259 assert !rt.isOutOfContext();
1261 // otherwise unshadow it
1262 out = Canonical.add( out,
1263 ReachTuple.factory( -rt.getHrnID(),
1272 out = Canonical.attach( out,
1276 assert out.isCanonical();
1277 op2result.put( op, out );
1283 public static ReachState makePredsTrue( ReachState rs ) {
1285 assert rs.isCanonical();
1287 // ops require two canonicals, in this case always supply
1288 // the empty reach state as the second, it's never used,
1289 // but makes the hashing happy
1291 new CanonicalOp( CanonicalOp.REACHSTATE_MAKEPREDSTRUE,
1293 ReachState.factory() );
1295 Canonical result = op2result.get( op );
1296 if( result != null ) {
1297 return (ReachState) result;
1300 // otherwise, no cached result...
1301 ReachState out = new ReachState();
1303 // just remake state with the true predicate attached
1304 out.reachTuples.addAll( rs.reachTuples );
1305 out.preds = ExistPredSet.factory( ExistPred.factory() );
1307 out = (ReachState) makeCanonical( out );
1308 op2result.put( op, out );
1313 public static ReachSet makePredsTrue( ReachSet rs ) {
1315 assert rs.isCanonical();
1317 // ops require two canonicals, in this case always supply
1318 // the empty reach set as the second, it's never used,
1319 // but makes the hashing happy
1321 new CanonicalOp( CanonicalOp.REACHSET_MAKEPREDSTRUE,
1323 ReachSet.factory() );
1325 Canonical result = op2result.get( op );
1326 if( result != null ) {
1327 return (ReachSet) result;
1330 // otherwise, no cached result...
1331 ReachSet out = ReachSet.factory();
1332 Iterator<ReachState> itr = rs.iterator();
1333 while( itr.hasNext() ) {
1334 ReachState state = itr.next();
1335 out = Canonical.add( out,
1336 Canonical.makePredsTrue( state )
1340 out = (ReachSet) makeCanonical( out );
1341 op2result.put( op, out );