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 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 union( ReachState rs1,
187 assert rs1.isCanonical();
188 assert rs2.isCanonical();
191 new CanonicalOp( CanonicalOp.REACHSTATE_UNION_REACHSTATE,
195 Canonical result = op2result.get( op );
196 if( result != null ) {
197 return (ReachState) result;
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(),
208 out = (ReachState) makeCanonical( out );
209 op2result.put( op, out );
213 // this is just a convenience version of above
214 public static ReachState union( ReachState rs,
220 new CanonicalOp( CanonicalOp.REACHSTATE_UNION_REACHTUPLE,
224 Canonical result = op2result.get( op );
225 if( result != null ) {
226 return (ReachState) result;
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;
235 out = (ReachState) makeCanonical( out );
236 op2result.put( op, out );
241 public static ReachState unionUpArity( ReachState rs1,
245 assert rs1.isCanonical();
246 assert rs2.isCanonical();
249 new CanonicalOp( CanonicalOp.REACHSTATE_UNIONUPARITY_REACHSTATE,
253 Canonical result = op2result.get( op );
254 if( result != null ) {
255 return (ReachState) result;
258 // otherwise, no cached result...
259 ReachState out = new ReachState();
261 Iterator<ReachTuple> rtItr = rs1.iterator();
262 while( rtItr.hasNext() ) {
263 ReachTuple rt1 = rtItr.next();
264 ReachTuple rt2 = rs2.containsHrnID( rt1.getHrnID(),
268 out.reachTuples.add( unionArity( rt1, rt2 ) );
270 out.reachTuples.add( rt1 );
274 rtItr = rs2.iterator();
275 while( rtItr.hasNext() ) {
276 ReachTuple rt2 = rtItr.next();
277 ReachTuple rto = out.containsHrnID( rt2.getHrnID(),
281 out.reachTuples.add( rto );
285 out.preds = Canonical.join( rs1.getPreds(),
289 out = (ReachState) makeCanonical( out );
290 op2result.put( op, out );
294 public static ReachState add( ReachState rs, ReachTuple rt ) {
295 return union( rs, rt );
298 public static ReachState remove( ReachState rs, ReachTuple rt ) {
303 new CanonicalOp( CanonicalOp.REACHSTATE_REMOVE_REACHTUPLE,
307 Canonical result = op2result.get( op );
308 if( result != null ) {
309 return (ReachState) result;
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;
318 out = (ReachState) makeCanonical( out );
319 op2result.put( op, out );
324 public static ReachState ageTuplesFrom( ReachState rs,
328 assert rs.isCanonical();
329 assert as.isCanonical();
332 new CanonicalOp( CanonicalOp.REACHSTATE_AGETUPLESFROM_ALLOCSITE,
336 Canonical result = op2result.get( op );
337 if( result != null ) {
338 return (ReachState) result;
341 // otherwise, no cached result...
342 ReachState out = new ReachState();
344 ReachTuple rtSummary = null;
345 ReachTuple rtOldest = null;
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 );
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 ||
359 out.reachTuples.add( rt );
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
366 } else if( age == AllocSite.AGE_oldest ) {
367 // found an oldest hrnID, again just remember
372 assert age == AllocSite.AGE_in_I;
374 Integer I = as.getAge( hrnID );
377 // otherwise, we change this hrnID to the
379 Integer hrnIDToChangeTo = as.getIthOldest( I + 1 );
381 Canonical.changeHrnIDTo( rt, hrnIDToChangeTo );
382 out.reachTuples.add( rtAged );
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 );
397 } else if( rtSummary == null && rtOldest != null ) {
398 out.reachTuples.add( ReachTuple.factory( as.getSummary(),
401 false // out-of-context
405 } else if( rtSummary != null && rtOldest != null ) {
406 out.reachTuples.add( Canonical.unionArity( rtSummary,
407 ReachTuple.factory( as.getSummary(),
410 false // out-of-context
416 out.preds = rs.preds;
418 out = (ReachState) makeCanonical( out );
419 op2result.put( op, out );
425 public static ReachSet union( ReachSet rs1,
429 assert rs1.isCanonical();
430 assert rs2.isCanonical();
433 new CanonicalOp( CanonicalOp.REACHSET_UNION_REACHSET,
437 Canonical result = op2result.get( op );
438 if( result != null ) {
439 return (ReachSet) result;
442 // otherwise, no cached result...
443 ReachSet out = new ReachSet();
444 out.reachStates.addAll( rs1.reachStates );
445 out.reachStates.addAll( rs2.reachStates );
447 out = (ReachSet) makeCanonical( out );
448 op2result.put( op, out );
452 public static ReachSet union( ReachSet rs,
456 assert state != null;
457 assert rs.isCanonical();
458 assert state.isCanonical();
461 new CanonicalOp( CanonicalOp.REACHSET_UNION_REACHSTATE,
465 Canonical result = op2result.get( op );
466 if( result != null ) {
467 return (ReachSet) result;
470 // otherwise, no cached result...
471 ReachSet out = new ReachSet();
472 out.reachStates.addAll( rs.reachStates );
473 out.reachStates.add( state );
475 out = (ReachSet) makeCanonical( out );
476 op2result.put( op, out );
480 public static ReachSet intersection( ReachSet rs1,
484 assert rs1.isCanonical();
485 assert rs2.isCanonical();
488 new CanonicalOp( CanonicalOp.REACHSET_INTERSECTION_REACHSET,
492 Canonical result = op2result.get( op );
493 if( result != null ) {
494 return (ReachSet) result;
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 );
507 out = (ReachSet) makeCanonical( out );
508 op2result.put( op, out );
513 public static ReachSet add( ReachSet rs,
515 return union( rs, state );
518 public static ReachSet remove( ReachSet rs,
521 assert state != null;
522 assert rs.isCanonical();
523 assert state.isCanonical();
526 new CanonicalOp( CanonicalOp.REACHSET_REMOVE_REACHSTATE,
530 Canonical result = op2result.get( op );
531 if( result != null ) {
532 return (ReachSet) result;
535 // otherwise, no cached result...
536 ReachSet out = new ReachSet();
537 out.reachStates.addAll( rs.reachStates );
538 out.reachStates.remove( state );
540 out = (ReachSet) makeCanonical( out );
541 op2result.put( op, out );
546 public static ReachSet applyChangeSet( ReachSet rs,
548 boolean keepSourceState ) {
551 assert rs.isCanonical();
552 assert cs.isCanonical();
554 // this primitive operand stuff is just a way to
555 // ensure distinct inputs to a CanonicalOp
557 if( keepSourceState ) {
564 new CanonicalOp( CanonicalOp.REACHSET_APPLY_CHANGESET,
569 Canonical result = op2result.get( op );
570 if( result != null ) {
571 return (ReachSet) result;
574 // otherwise, no cached result...
575 ReachSet out = new ReachSet();
577 Iterator<ReachState> stateItr = rs.iterator();
578 while( stateItr.hasNext() ) {
579 ReachState state = stateItr.next();
581 boolean changeFound = false;
583 Iterator<ChangeTuple> ctItr = cs.iterator();
584 while( ctItr.hasNext() ) {
585 ChangeTuple ct = ctItr.next();
587 if( state.equals( ct.getSetToMatch() ) ) {
588 out.reachStates.add( ct.getSetToAdd() );
593 if( keepSourceState || !changeFound ) {
594 out.reachStates.add( state );
598 out = (ReachSet) makeCanonical( out );
599 op2result.put( op, out );
604 public static ChangeSet unionUpArityToChangeSet( ReachSet rsO,
608 assert rsO.isCanonical();
609 assert rsR.isCanonical();
612 new CanonicalOp( CanonicalOp.REACHSET_UNIONTOCHANGESET_REACHSET,
616 Canonical result = op2result.get( op );
617 if( result != null ) {
618 return (ChangeSet) result;
621 // otherwise, no cached result...
622 ChangeSet out = ChangeSet.factory();
624 Iterator<ReachState> itrO = rsO.iterator();
625 while( itrO.hasNext() ) {
626 ReachState o = itrO.next();
628 Iterator<ReachState> itrR = rsR.iterator();
629 while( itrR.hasNext() ) {
630 ReachState r = itrR.next();
632 ReachState theUnion = ReachState.factory();
634 Iterator<ReachTuple> itrRelement = r.iterator();
635 while( itrRelement.hasNext() ) {
636 ReachTuple rtR = itrRelement.next();
637 ReachTuple rtO = o.containsHrnID( rtR.getHrnID(),
641 theUnion = Canonical.union( theUnion,
642 Canonical.unionArity( rtR,
647 theUnion = Canonical.union( theUnion,
653 Iterator<ReachTuple> itrOelement = o.iterator();
654 while( itrOelement.hasNext() ) {
655 ReachTuple rtO = itrOelement.next();
656 ReachTuple rtR = theUnion.containsHrnID( rtO.getHrnID(),
660 theUnion = Canonical.union( theUnion,
666 if( !theUnion.isEmpty() ) {
668 Canonical.union( out,
670 ChangeTuple.factory( o, theUnion )
677 assert out.isCanonical();
678 op2result.put( op, out );
683 public static ReachSet ageTuplesFrom( ReachSet rs,
687 assert rs.isCanonical();
688 assert as.isCanonical();
691 new CanonicalOp( CanonicalOp.REACHSET_AGETUPLESFROM_ALLOCSITE,
695 Canonical result = op2result.get( op );
696 if( result != null ) {
697 return (ReachSet) result;
700 // otherwise, no cached result...
701 ReachSet out = new ReachSet();
703 Iterator<ReachState> itrS = rs.iterator();
704 while( itrS.hasNext() ) {
705 ReachState state = itrS.next();
706 out.reachStates.add( Canonical.ageTuplesFrom( state, as ) );
709 out = (ReachSet) makeCanonical( out );
710 op2result.put( op, out );
715 public static ReachSet pruneBy( ReachSet rsO,
719 assert rsO.isCanonical();
720 assert rsP.isCanonical();
723 new CanonicalOp( CanonicalOp.REACHSET_PRUNEBY_REACHSET,
727 Canonical result = op2result.get( op );
728 if( result != null ) {
729 return (ReachSet) result;
732 // otherwise, no cached result...
733 ReachSet out = new ReachSet();
735 Iterator<ReachState> itrO = rsO.iterator();
736 while( itrO.hasNext() ) {
737 ReachState stateO = itrO.next();
739 boolean subsetExists = false;
741 Iterator<ReachState> itrP = rsP.iterator();
742 while( itrP.hasNext() && !subsetExists ) {
743 ReachState stateP = itrP.next();
745 if( stateP.isSubset( stateO ) ) {
751 out.reachStates.add( stateO );
755 out = (ReachSet) makeCanonical( out );
756 op2result.put( op, out );
761 public static ChangeSet union( ChangeSet cs1,
765 assert cs1.isCanonical();
766 assert cs2.isCanonical();
769 new CanonicalOp( CanonicalOp.CHANGESET_UNION_CHANGESET,
773 Canonical result = op2result.get( op );
774 if( result != null ) {
775 return (ChangeSet) result;
778 // otherwise, no cached result...
779 ChangeSet out = new ChangeSet();
780 out.changeTuples.addAll( cs1.changeTuples );
781 out.changeTuples.addAll( cs2.changeTuples );
783 out = (ChangeSet) makeCanonical( out );
784 op2result.put( op, out );
788 public static ChangeSet union( ChangeSet cs,
792 assert cs.isCanonical();
793 assert ct.isCanonical();
796 new CanonicalOp( CanonicalOp.CHANGESET_UNION_CHANGETUPLE,
800 Canonical result = op2result.get( op );
801 if( result != null ) {
802 return (ChangeSet) result;
805 // otherwise, no cached result...
806 ChangeSet out = new ChangeSet();
807 out.changeTuples.addAll( cs.changeTuples );
808 out.changeTuples.add( ct );
810 out = (ChangeSet) makeCanonical( out );
811 op2result.put( op, out );
817 public static ExistPredSet join( ExistPredSet eps1,
818 ExistPredSet eps2 ) {
822 assert eps1.isCanonical();
823 assert eps2.isCanonical();
826 new CanonicalOp( CanonicalOp.EXISTPREDSET_JOIN_EXISTPREDSET,
830 Canonical result = op2result.get( op );
831 if( result != null ) {
832 return (ExistPredSet) result;
835 // otherwise, no cached result...
836 ExistPredSet out = new ExistPredSet();
837 out.preds.addAll( eps1.preds );
838 out.preds.addAll( eps2.preds );
840 out = (ExistPredSet) makeCanonical( out );
841 op2result.put( op, out );
845 public static ExistPredSet add( ExistPredSet eps,
851 assert eps.isCanonical();
852 assert ep.isCanonical();
855 new CanonicalOp( CanonicalOp.EXISTPREDSET_ADD_EXISTPRED,
859 Canonical result = op2result.get( op );
860 if( result != null ) {
861 return (ExistPredSet) result;
864 // otherwise, no cached result...
865 ExistPredSet out = new ExistPredSet();
866 out.preds.addAll( eps.preds );
869 out = (ExistPredSet) makeCanonical( out );
870 op2result.put( op, out );
876 public static ReachSet toCalleeContext( ReachSet rs,
880 assert rs.isCanonical();
881 assert as.isCanonical();
884 new CanonicalOp( CanonicalOp.REACHSET_TOCALLEECONTEXT_ALLOCSITE,
888 Canonical result = op2result.get( op );
889 if( result != null ) {
890 return (ReachSet) result;
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 )
903 assert out.isCanonical();
904 op2result.put( op, out );
909 public static ReachState toCalleeContext( ReachState state,
911 assert state != null;
913 assert state.isCanonical();
914 assert as.isCanonical();
917 new CanonicalOp( CanonicalOp.REACHSTATE_TOCALLEECONTEXT_ALLOCSITE,
921 Canonical result = op2result.get( op );
922 if( result != null ) {
923 return (ReachState) result;
926 // otherwise, no cached result...
927 ReachState out = ReachState.factory();
928 Iterator<ReachTuple> itr = state.iterator();
929 while( itr.hasNext() ) {
930 ReachTuple rt = itr.next();
932 int age = as.getAgeCategory( rt.getHrnID() );
934 // this is the current mapping, where 0, 1, 2S were allocated
935 // in the current context, 0?, 1? and 2S? were allocated in a
936 // previous context, and we're translating to a future context
948 if( age == AllocSite.AGE_notInThisSite ) {
949 // things not from the site just go back in
950 out = Canonical.union( out, rt );
952 } else if( age == AllocSite.AGE_summary ||
955 // the in-context summary and all existing out-of-context
957 out = Canonical.union( out,
958 ReachTuple.factory( as.getSummary(),
961 true // out-of-context
965 // otherwise everything else just goes to an out-of-context
966 // version, everything else the same
967 Integer I = as.getAge( rt.getHrnID() );
970 assert !rt.isMultiObject();
972 out = Canonical.union( out,
973 ReachTuple.factory( rt.getHrnID(),
976 true // out-of-context
982 out = Canonical.attach( out,
986 assert out.isCanonical();
987 op2result.put( op, out );
993 public static ReachSet toCallerContext( ReachSet rs,
997 assert rs.isCanonical();
998 assert as.isCanonical();
1001 new CanonicalOp( CanonicalOp.REACHSET_TOCALLERCONTEXT_ALLOCSITE,
1005 Canonical result = op2result.get( op );
1006 if( result != null ) {
1007 return (ReachSet) result;
1010 // otherwise, no cached result...
1011 ReachSet out = ReachSet.factory();
1012 Iterator<ReachState> itr = rs.iterator();
1013 while( itr.hasNext() ) {
1014 ReachState state = itr.next();
1015 out = Canonical.union( out,
1016 Canonical.toCallerContext( state, as )
1020 assert out.isCanonical();
1021 op2result.put( op, out );
1026 public static ReachSet toCallerContext( ReachState state,
1028 assert state != null;
1030 assert state.isCanonical();
1031 assert as.isCanonical();
1034 new CanonicalOp( CanonicalOp.REACHSTATE_TOCALLERCONTEXT_ALLOCSITE,
1038 Canonical result = op2result.get( op );
1039 if( result != null ) {
1040 return (ReachSet) result;
1043 // otherwise, no cached result...
1044 ReachSet out = ReachSet.factory();
1046 // this method returns a ReachSet instead of a ReachState
1047 // because the companion method, toCallee, translates
1048 // symbols many-to-one, so state->state
1049 // but this method does an ~inverse mapping, one-to-many
1050 // so one state can split into a set of branched states
1063 // 2S?* -> {2S*, 2S?*}
1065 boolean found2Sooc = false;
1067 ReachState baseState = ReachState.factory();
1069 Iterator<ReachTuple> itr = state.iterator();
1070 while( itr.hasNext() ) {
1071 ReachTuple rt = itr.next();
1073 int age = as.getAgeCategory( rt.getHrnID() );
1075 if( age == AllocSite.AGE_notInThisSite ) {
1076 // things not from the site just go back in
1077 baseState = Canonical.union( baseState, rt );
1079 } else if( age == AllocSite.AGE_summary ) {
1081 if( rt.isOutOfContext() ) {
1082 // if its out-of-context, we only deal here with the ZERO-OR-MORE
1083 // arity, if ARITY-ONE we'll branch the base state after the loop
1084 if( rt.getArity() == ReachTuple.ARITY_ZEROORMORE ) {
1085 // add two overly conservative symbols to reach state (PUNTING)
1086 baseState = Canonical.union( baseState,
1087 ReachTuple.factory( as.getSummary(),
1089 ReachTuple.ARITY_ZEROORMORE,
1090 false // out-of-context
1093 baseState = Canonical.union( baseState,
1094 ReachTuple.factory( as.getSummary(),
1096 ReachTuple.ARITY_ZEROORMORE,
1097 true // out-of-context
1101 assert rt.getArity() == ReachTuple.ARITY_ONE;
1106 // the in-context just becomes shadow
1107 baseState = Canonical.union( baseState,
1108 ReachTuple.factory( as.getSummaryShadow(),
1111 false // out-of-context
1117 // otherwise the ith symbol becomes shadowed
1118 Integer I = as.getAge( rt.getHrnID() );
1121 assert !rt.isMultiObject();
1123 baseState = Canonical.union( baseState,
1124 ReachTuple.factory( -rt.getHrnID(),
1127 false // out-of-context
1133 // now either make branches if we have 2S?, or
1134 // the current baseState is the only state we need
1136 // make a branch with every possibility of the one-to-many
1137 // mapping for 2S? appended to the baseState
1138 out = Canonical.union( out,
1139 Canonical.union( baseState,
1140 ReachTuple.factory( as.getSummary(),
1142 ReachTuple.ARITY_ONE,
1143 false // out-of-context
1148 out = Canonical.union( out,
1149 Canonical.union( baseState,
1150 ReachTuple.factory( as.getSummary(),
1152 ReachTuple.ARITY_ONE,
1153 true // out-of-context
1158 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1159 out = Canonical.union( out,
1160 Canonical.union( baseState,
1161 ReachTuple.factory( as.getIthOldest( i ),
1163 ReachTuple.ARITY_ONE,
1164 true // out-of-context
1171 // just use current baseState
1172 out = Canonical.union( out,
1177 assert out.isCanonical();
1178 op2result.put( op, out );
1190 public static ReachSet unshadow( ReachSet rs,
1194 assert rs.isCanonical();
1195 assert as.isCanonical();
1198 new CanonicalOp( CanonicalOp.REACHSET_UNSHADOW_ALLOCSITE,
1202 Canonical result = op2result.get( op );
1203 if( result != null ) {
1204 return (ReachSet) result;
1207 // otherwise, no cached result...
1208 ReachSet out = ReachSet.factory();
1209 Iterator<ReachState> itr = rs.iterator();
1210 while( itr.hasNext() ) {
1211 ReachState state = itr.next();
1212 out = Canonical.add( out,
1213 Canonical.unshadow( state, as )
1217 assert out.isCanonical();
1218 op2result.put( op, out );
1222 public static ReachState unshadow( ReachState state,
1224 assert state != null;
1226 assert state.isCanonical();
1227 assert as.isCanonical();
1230 new CanonicalOp( CanonicalOp.REACHSTATE_UNSHADOW_ALLOCSITE,
1234 Canonical result = op2result.get( op );
1235 if( result != null ) {
1236 return (ReachState) result;
1239 // this is the current mapping, where 0, 1, 2S were allocated
1240 // in the current context, 0?, 1? and 2S? were allocated in a
1241 // previous context, and we're translating to a future context
1247 // otherwise, no cached result...
1248 ReachState out = ReachState.factory();
1249 Iterator<ReachTuple> itr = state.iterator();
1250 while( itr.hasNext() ) {
1251 ReachTuple rt = itr.next();
1253 int age = as.getShadowAgeCategory( rt.getHrnID() );
1255 if( age == AllocSite.SHADOWAGE_notInThisSite ) {
1256 // things not from the site just go back in
1257 out = Canonical.union( out, rt );
1260 assert !rt.isOutOfContext();
1262 // otherwise unshadow it
1263 out = Canonical.union( out,
1264 ReachTuple.factory( -rt.getHrnID(),
1273 out = Canonical.attach( out,
1277 assert out.isCanonical();
1278 op2result.put( op, out );