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) ) {
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;
64 abstract public boolean equalsSpecific(Object o);
66 final public boolean equals(Object o) {
71 if( !(o instanceof Canonical) ) {
75 Canonical c = (Canonical) o;
77 if( this.canonicalValue == 0 ||
80 return equalsSpecific(o);
83 return this.canonicalValue == c.canonicalValue;
87 // canonical objects should never be modified
88 // and therefore have changing hash codes, so
89 // use a standard canonical hash code method to
90 // enforce this, and define a specific hash code
91 // method each specific subclass should implement
92 abstract public int hashCodeSpecific();
94 private boolean hasHash = false;
96 final public int hashCode() {
99 if( DisjointAnalysis.releaseMode && hasHash ) {
104 int hash = hashCodeSpecific();
107 if( oldHash != hash ) {
108 throw new Error("A CANONICAL HASH CHANGED");
119 // mapping of a non-trivial operation to its result
120 private static Hashtable<CanonicalOp, Canonical>
121 op2result = new Hashtable<CanonicalOp, Canonical>();
125 ///////////////////////////////////////////////////////////
127 // Everything below are static methods that implement
128 // "mutating" operations on Canonical objects by returning
129 // the canonical result. If the op is non-trivial the
130 // canonical result is hashed by its defining CononicalOp
132 ///////////////////////////////////////////////////////////
135 // not weighty, don't bother with caching
136 public static ReachTuple unionUpArity(ReachTuple rt1,
140 assert rt1.isCanonical();
141 assert rt2.isCanonical();
142 assert rt1.hrnID == rt2.hrnID;
143 assert rt1.isMultiObject == rt2.isMultiObject;
144 assert rt1.isOutOfContext == rt2.isOutOfContext;
148 if( rt1.isMultiObject ) {
149 // on two non-ZERO arity multi regions, union arity is always
151 out = ReachTuple.factory(rt1.hrnID,
153 ReachTuple.ARITY_ZEROORMORE,
157 // a single object region can only be ARITY_ONE (or zero by
159 assert rt1.arity == ReachTuple.ARITY_ONE;
163 assert out.isCanonical();
167 // not weighty, no caching
168 public static ReachTuple changeHrnIDTo(ReachTuple rt,
169 Integer hrnIDToChangeTo) {
171 assert hrnIDToChangeTo != null;
173 ReachTuple out = ReachTuple.factory(hrnIDToChangeTo,
178 assert out.isCanonical();
183 public static ReachState attach(ReachState rs,
184 ExistPredSet preds) {
186 assert preds != null;
187 assert rs.isCanonical();
188 assert preds.isCanonical();
191 new CanonicalOp(CanonicalOp.REACHSTATE_ATTACH_EXISTPREDSET,
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(rs.reachTuples);
203 out.preds = Canonical.join(rs.preds,
206 out = (ReachState) makeCanonical(out);
207 op2result.put(op, out);
212 public static ReachState add(ReachState rs,
217 // this is only safe if we are certain the new tuple's
218 // ID doesn't already appear in the reach state
219 assert rs.containsHrnID(rt.getHrnID(),
220 rt.isOutOfContext() ) == null;
223 new CanonicalOp(CanonicalOp.REACHSTATE_ADD_REACHTUPLE,
227 Canonical result = op2result.get(op);
228 if( result != null ) {
229 return (ReachState) result;
232 // otherwise, no cached result...
233 ReachState out = new ReachState();
234 out.reachTuples.addAll(rs.reachTuples);
235 out.reachTuples.add(rt);
236 out.preds = rs.preds;
238 out = (ReachState) makeCanonical(out);
239 op2result.put(op, out);
244 public static ReachState unionUpArity(ReachState rs1,
248 assert rs1.isCanonical();
249 assert rs2.isCanonical();
252 new CanonicalOp(CanonicalOp.REACHSTATE_UNIONUPARITY_REACHSTATE,
256 Canonical result = op2result.get(op);
257 if( result != null ) {
258 return (ReachState) result;
261 // otherwise, no cached result...
262 ReachState out = new ReachState();
264 // first add everything from 1, and if it is
265 // also in 2 take the union of the tuple arities
266 Iterator<ReachTuple> rtItr = rs1.iterator();
267 while( rtItr.hasNext() ) {
268 ReachTuple rt1 = rtItr.next();
269 ReachTuple rt2 = rs2.containsHrnID(rt1.getHrnID(),
273 out.reachTuples.add(unionUpArity(rt1, rt2) );
275 out.reachTuples.add(rt1);
279 // then add everything in 2 that wasn't in 1
280 rtItr = rs2.iterator();
281 while( rtItr.hasNext() ) {
282 ReachTuple rt2 = rtItr.next();
283 ReachTuple rt1 = rs1.containsHrnID(rt2.getHrnID(),
287 out.reachTuples.add(rt2);
291 out.preds = Canonical.join(rs1.getPreds(),
295 out = (ReachState) makeCanonical(out);
296 op2result.put(op, out);
301 public static ReachState addUpArity(ReachState rs,
307 new CanonicalOp(CanonicalOp.REACHSTATE_ADDUPARITY_REACHTUPLE,
311 Canonical result = op2result.get(op);
312 if( result != null ) {
313 return (ReachState) result;
316 // otherwise, no cached result...
319 // the reason for this add is that we are aware a tuple
320 // with the same hrnID might already be in the state, so
321 // if it is we should combine properly
322 ReachState rtOnly = ReachState.factory(rt);
323 out = Canonical.unionUpArity(rs, rtOnly);
325 op2result.put(op, out);
330 public static ReachState remove(ReachState rs, ReachTuple rt) {
335 new CanonicalOp(CanonicalOp.REACHSTATE_REMOVE_REACHTUPLE,
339 Canonical result = op2result.get(op);
340 if( result != null ) {
341 return (ReachState) result;
344 // otherwise, no cached result...
345 ReachState out = new ReachState();
346 out.reachTuples.addAll(rs.reachTuples);
347 out.reachTuples.remove(rt);
348 out.preds = rs.preds;
350 out = (ReachState) makeCanonical(out);
351 op2result.put(op, out);
356 public static ReachState ageTuplesFrom(ReachState rs,
360 assert rs.isCanonical();
361 assert as.isCanonical();
364 new CanonicalOp(CanonicalOp.REACHSTATE_AGETUPLESFROM_ALLOCSITE,
368 Canonical result = op2result.get(op);
369 if( result != null ) {
370 return (ReachState) result;
373 // otherwise, no cached result...
374 ReachState out = new ReachState();
376 ReachTuple rtSummary = null;
377 ReachTuple rtOldest = null;
379 Iterator<ReachTuple> rtItr = rs.iterator();
380 while( rtItr.hasNext() ) {
381 ReachTuple rt = rtItr.next();
382 Integer hrnID = rt.getHrnID();
383 int age = as.getAgeCategory(hrnID);
385 // hrnIDs not associated with
386 // the site should be left alone, and
387 // those from this site but out-of-context
388 if( age == AllocSite.AGE_notInThisSite ||
391 out.reachTuples.add(rt);
393 } else if( age == AllocSite.AGE_summary ) {
394 // remember the summary tuple, but don't add it
395 // we may combine it with the oldest tuple
398 } else if( age == AllocSite.AGE_oldest ) {
399 // found an oldest hrnID, again just remember
404 assert age == AllocSite.AGE_in_I;
406 Integer I = as.getAge(hrnID);
409 // otherwise, we change this hrnID to the
411 Integer hrnIDToChangeTo = as.getIthOldest(I + 1);
413 Canonical.changeHrnIDTo(rt, hrnIDToChangeTo);
414 out.reachTuples.add(rtAged);
418 // there are four cases to consider here
419 // 1. we found a summary tuple and no oldest tuple
420 // Here we just pass the summary unchanged
421 // 2. we found an oldest tuple, no summary
422 // Make a new, arity-one summary tuple
423 // 3. we found both a summary and an oldest
424 // Merge them by arity
425 // 4. (not handled) we found neither, do nothing
426 if( rtSummary != null && rtOldest == null ) {
427 out.reachTuples.add(rtSummary);
429 } else if( rtSummary == null && rtOldest != null ) {
430 out.reachTuples.add(ReachTuple.factory(as.getSummary(),
433 false // out-of-context
437 } else if( rtSummary != null && rtOldest != null ) {
438 out.reachTuples.add(Canonical.unionUpArity(rtSummary,
439 ReachTuple.factory(as.getSummary(),
442 false // out-of-context
448 out.preds = rs.preds;
450 out = (ReachState) makeCanonical(out);
451 op2result.put(op, out);
457 public static ReachSet unionORpreds(ReachSet rs1,
461 assert rs1.isCanonical();
462 assert rs2.isCanonical();
465 new CanonicalOp(CanonicalOp.REACHSET_UNIONORPREDS_REACHSET,
469 Canonical result = op2result.get(op);
470 if( result != null ) {
471 return (ReachSet) result;
474 // otherwise, no cached result...
475 ReachSet out = new ReachSet();
477 // first add everything from 1, and if it was also in 2
478 // take the OR of the predicates
479 Iterator<ReachState> stateItr = rs1.iterator();
480 while( stateItr.hasNext() ) {
481 ReachState state1 = stateItr.next();
482 ReachState state2 = rs2.containsIgnorePreds(state1);
484 if( state2 != null ) {
485 out.reachStates.add(ReachState.factory(state1.reachTuples,
486 Canonical.join(state1.preds,
491 out.reachStates.add(state1);
495 // then add everything in 2 that wasn't in 1
496 stateItr = rs2.iterator();
497 while( stateItr.hasNext() ) {
498 ReachState state2 = stateItr.next();
499 ReachState state1 = rs1.containsIgnorePreds(state2);
501 if( state1 == null ) {
502 out.reachStates.add(state2);
506 out = (ReachSet) makeCanonical(out);
507 op2result.put(op, out);
512 // NOTE: when taking the intersection of two reach sets it
513 // is possible for a reach state to be in both sets, but
514 // have different predicates. Conceptully the best new
515 // predicate is an AND of the source predicates, but to
516 // avoid eploding states we'll take an overapproximation
517 // by preferring the predicates from the state in the FIRST
518 // set, so order of arguments matters
519 public static ReachSet intersection(ReachSet rs1,
523 assert rs1.isCanonical();
524 assert rs2.isCanonical();
527 new CanonicalOp(CanonicalOp.REACHSET_INTERSECTION_REACHSET,
531 Canonical result = op2result.get(op);
532 if( result != null ) {
533 return (ReachSet) result;
536 // otherwise, no cached result...
537 ReachSet out = new ReachSet();
538 Iterator<ReachState> itr = rs1.iterator();
539 while( itr.hasNext() ) {
540 ReachState state1 = (ReachState) itr.next();
541 ReachState state2 = rs2.containsIgnorePreds(state1);
542 if( state2 != null ) {
543 // prefer the predicates on state1, an overapproximation
544 // of state1 preds AND state2 preds
545 out.reachStates.add(state1);
549 out = (ReachSet) makeCanonical(out);
550 op2result.put(op, out);
555 public static ReachSet add(ReachSet rs,
557 return unionORpreds(rs,
558 ReachSet.factory(state)
562 public static ReachSet remove(ReachSet rs,
565 assert state != null;
566 assert rs.isCanonical();
567 assert state.isCanonical();
570 new CanonicalOp(CanonicalOp.REACHSET_REMOVE_REACHSTATE,
574 Canonical result = op2result.get(op);
575 if( result != null ) {
576 return (ReachSet) result;
579 // otherwise, no cached result...
580 ReachSet out = new ReachSet();
581 out.reachStates.addAll(rs.reachStates);
582 out.reachStates.remove(state);
584 out = (ReachSet) makeCanonical(out);
585 op2result.put(op, out);
590 public static ReachSet applyChangeSet(ReachSet rs,
592 boolean keepSourceState) {
595 assert rs.isCanonical();
596 assert cs.isCanonical();
598 // this primitive operand stuff is just a way to
599 // ensure distinct inputs to a CanonicalOp
601 if( keepSourceState ) {
608 new CanonicalOp(CanonicalOp.REACHSET_APPLY_CHANGESET,
613 Canonical result = op2result.get(op);
614 if( result != null ) {
615 return (ReachSet) result;
618 // otherwise, no cached result...
619 ReachSet out = new ReachSet();
621 Iterator<ReachState> stateItr = rs.iterator();
622 while( stateItr.hasNext() ) {
623 ReachState stateOrig = stateItr.next();
625 boolean changeFound = false;
627 Iterator<ChangeTuple> ctItr = cs.iterator();
628 while( ctItr.hasNext() ) {
629 ChangeTuple ct = ctItr.next();
631 if( stateOrig.equalsIgnorePreds(ct.getStateToMatch() ) ) {
632 // use the new state, but the original predicates
633 ReachState stateNew =
634 ReachState.factory(ct.getStateToAdd().reachTuples,
637 out.reachStates.add(stateNew);
642 if( keepSourceState || !changeFound ) {
643 out.reachStates.add(stateOrig);
647 out = (ReachSet) makeCanonical(out);
648 op2result.put(op, out);
653 public static ChangeSet unionUpArityToChangeSet(ReachSet rsO,
657 assert rsO.isCanonical();
658 assert rsR.isCanonical();
661 new CanonicalOp(CanonicalOp.REACHSET_UNIONTOCHANGESET_REACHSET,
665 Canonical result = op2result.get(op);
666 if( result != null ) {
667 return (ChangeSet) result;
670 // otherwise, no cached result...
671 ChangeSet out = ChangeSet.factory();
673 Iterator<ReachState> itrO = rsO.iterator();
674 while( itrO.hasNext() ) {
675 ReachState o = itrO.next();
677 Iterator<ReachState> itrR = rsR.iterator();
678 while( itrR.hasNext() ) {
679 ReachState r = itrR.next();
681 ReachState theUnion = ReachState.factory();
683 Iterator<ReachTuple> itrRelement = r.iterator();
684 while( itrRelement.hasNext() ) {
685 ReachTuple rtR = itrRelement.next();
686 ReachTuple rtO = o.containsHrnID(rtR.getHrnID(),
690 theUnion = Canonical.add(theUnion,
691 Canonical.unionUpArity(rtR,
696 theUnion = Canonical.add(theUnion,
702 Iterator<ReachTuple> itrOelement = o.iterator();
703 while( itrOelement.hasNext() ) {
704 ReachTuple rtO = itrOelement.next();
705 ReachTuple rtR = theUnion.containsHrnID(rtO.getHrnID(),
709 theUnion = Canonical.add(theUnion,
715 if( !theUnion.isEmpty() ) {
719 ChangeTuple.factory(o, theUnion)
726 assert out.isCanonical();
727 op2result.put(op, out);
732 public static ReachSet ageTuplesFrom(ReachSet rs,
736 assert rs.isCanonical();
737 assert as.isCanonical();
740 new CanonicalOp(CanonicalOp.REACHSET_AGETUPLESFROM_ALLOCSITE,
744 Canonical result = op2result.get(op);
745 if( result != null ) {
746 return (ReachSet) result;
749 // otherwise, no cached result...
750 ReachSet out = new ReachSet();
752 Iterator<ReachState> itrS = rs.iterator();
753 while( itrS.hasNext() ) {
754 ReachState state = itrS.next();
755 out.reachStates.add(Canonical.ageTuplesFrom(state, as) );
758 out = (ReachSet) makeCanonical(out);
759 op2result.put(op, out);
764 public static ReachSet pruneBy(ReachSet rsO,
768 assert rsO.isCanonical();
769 assert rsP.isCanonical();
772 new CanonicalOp(CanonicalOp.REACHSET_PRUNEBY_REACHSET,
776 Canonical result = op2result.get(op);
777 if( result != null ) {
778 return (ReachSet) result;
781 // otherwise, no cached result...
782 ReachSet out = new ReachSet();
784 Iterator<ReachState> itrO = rsO.iterator();
785 while( itrO.hasNext() ) {
786 ReachState stateO = itrO.next();
788 boolean subsetExists = false;
790 Iterator<ReachState> itrP = rsP.iterator();
791 while( itrP.hasNext() && !subsetExists ) {
792 ReachState stateP = itrP.next();
794 if( stateP.isSubset(stateO) ) {
800 out.reachStates.add(stateO);
804 out = (ReachSet) makeCanonical(out);
805 op2result.put(op, out);
810 public static ChangeSet union(ChangeSet cs1,
814 assert cs1.isCanonical();
815 assert cs2.isCanonical();
818 new CanonicalOp(CanonicalOp.CHANGESET_UNION_CHANGESET,
822 Canonical result = op2result.get(op);
823 if( result != null ) {
824 return (ChangeSet) result;
827 // otherwise, no cached result...
828 ChangeSet out = new ChangeSet();
829 out.changeTuples.addAll(cs1.changeTuples);
830 out.changeTuples.addAll(cs2.changeTuples);
832 out = (ChangeSet) makeCanonical(out);
833 op2result.put(op, out);
837 public static ChangeSet add(ChangeSet cs,
841 assert cs.isCanonical();
842 assert ct.isCanonical();
845 new CanonicalOp(CanonicalOp.CHANGESET_UNION_CHANGETUPLE,
849 Canonical result = op2result.get(op);
850 if( result != null ) {
851 return (ChangeSet) result;
854 // otherwise, no cached result...
855 ChangeSet out = new ChangeSet();
856 out.changeTuples.addAll(cs.changeTuples);
857 out.changeTuples.add(ct);
859 out = (ChangeSet) makeCanonical(out);
860 op2result.put(op, out);
866 public static ExistPredSet join(ExistPredSet eps1,
871 assert eps1.isCanonical();
872 assert eps2.isCanonical();
875 new CanonicalOp(CanonicalOp.EXISTPREDSET_JOIN_EXISTPREDSET,
879 Canonical result = op2result.get(op);
880 if( result != null ) {
881 return (ExistPredSet) result;
884 // otherwise, no cached result...
885 ExistPredSet out = new ExistPredSet();
886 out.preds.addAll(eps1.preds);
887 out.preds.addAll(eps2.preds);
889 out = (ExistPredSet) makeCanonical(out);
890 op2result.put(op, out);
894 public static ExistPredSet add(ExistPredSet eps,
900 assert eps.isCanonical();
901 assert ep.isCanonical();
904 new CanonicalOp(CanonicalOp.EXISTPREDSET_ADD_EXISTPRED,
908 Canonical result = op2result.get(op);
909 if( result != null ) {
910 return (ExistPredSet) result;
913 // otherwise, no cached result...
914 ExistPredSet out = new ExistPredSet();
915 out.preds.addAll(eps.preds);
918 out = (ExistPredSet) makeCanonical(out);
919 op2result.put(op, out);
924 public static ReachSet toCallerContext(ReachSet rs,
928 assert rs.isCanonical();
929 assert as.isCanonical();
932 new CanonicalOp(CanonicalOp.REACHSET_TOCALLERCONTEXT_ALLOCSITE,
936 Canonical result = op2result.get(op);
937 if( result != null ) {
938 return (ReachSet) result;
941 // otherwise, no cached result...
942 ReachSet out = ReachSet.factory();
943 Iterator<ReachState> itr = rs.iterator();
944 while( itr.hasNext() ) {
945 ReachState state = itr.next();
946 out = Canonical.unionORpreds(out,
947 Canonical.toCallerContext(state, as)
951 assert out.isCanonical();
952 op2result.put(op, out);
957 public static ReachSet toCallerContext(ReachState state,
959 assert state != null;
961 assert state.isCanonical();
962 assert as.isCanonical();
965 new CanonicalOp(CanonicalOp.REACHSTATE_TOCALLERCONTEXT_ALLOCSITE,
969 Canonical result = op2result.get(op);
970 if( result != null ) {
971 return (ReachSet) result;
974 // otherwise, no cached result...
975 ReachSet out = ReachSet.factory();
977 // this method returns a ReachSet instead of a ReachState
978 // because the companion method, toCallee, translates
979 // symbols many-to-one, so state->state
980 // but this method does an ~inverse mapping, one-to-many
981 // so one state can split into a set of branched states
994 // 2S?* -> {2S*, 2S?*}
996 boolean found2Sooc = false;
998 ReachState baseState = ReachState.factory();
1000 Iterator<ReachTuple> itr = state.iterator();
1001 while( itr.hasNext() ) {
1002 ReachTuple rt = itr.next();
1004 int age = as.getAgeCategory(rt.getHrnID() );
1006 if( age == AllocSite.AGE_notInThisSite ) {
1007 // things not from the site just go back in
1008 baseState = Canonical.addUpArity(baseState, rt);
1010 } else if( age == AllocSite.AGE_summary ) {
1012 if( rt.isOutOfContext() ) {
1013 // if its out-of-context, we only deal here with the ZERO-OR-MORE
1014 // arity, if ARITY-ONE we'll branch the base state after the loop
1015 if( rt.getArity() == ReachTuple.ARITY_ZEROORMORE ) {
1016 // add two overly conservative symbols to reach state (PUNTING)
1018 baseState = Canonical.addUpArity(baseState,
1019 ReachTuple.factory(as.getSummary(),
1021 ReachTuple.ARITY_ZEROORMORE,
1022 false // out-of-context
1026 baseState = Canonical.addUpArity(baseState,
1027 ReachTuple.factory(as.getSummary(),
1029 ReachTuple.ARITY_ZEROORMORE,
1030 true // out-of-context
1034 assert rt.getArity() == ReachTuple.ARITY_ONE;
1039 // the in-context just becomes shadow
1040 baseState = Canonical.addUpArity(baseState,
1041 ReachTuple.factory(as.getSummaryShadow(),
1044 false // out-of-context
1051 // otherwise age is in range [0, k]
1052 Integer I = as.getAge(rt.getHrnID() );
1054 assert !rt.isMultiObject();
1055 assert rt.getArity() == ReachTuple.ARITY_ONE;
1057 if( rt.isOutOfContext() ) {
1058 // becomes the in-context version
1059 baseState = Canonical.addUpArity(baseState,
1060 ReachTuple.factory(rt.getHrnID(),
1062 ReachTuple.ARITY_ONE,
1063 false // out-of-context
1068 // otherwise the ith symbol becomes shadowed
1069 baseState = Canonical.addUpArity(baseState,
1070 ReachTuple.factory(-rt.getHrnID(),
1072 ReachTuple.ARITY_ONE,
1073 false // out-of-context
1080 // now either make branches if we have 2S?, or
1081 // the current baseState is the only state we need
1083 // make a branch with every possibility of the one-to-many
1084 // mapping for 2S? appended to the baseState
1085 out = Canonical.add(out,
1086 Canonical.addUpArity(baseState,
1087 ReachTuple.factory(as.getSummary(),
1089 ReachTuple.ARITY_ONE,
1090 false // out-of-context
1095 out = Canonical.add(out,
1096 Canonical.addUpArity(baseState,
1097 ReachTuple.factory(as.getSummary(),
1099 ReachTuple.ARITY_ONE,
1100 true // out-of-context
1105 for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1106 out = Canonical.add(out,
1107 Canonical.addUpArity(baseState,
1108 ReachTuple.factory(as.getIthOldest(i),
1110 ReachTuple.ARITY_ONE,
1111 true // out-of-context
1118 // just use current baseState
1119 out = Canonical.add(out,
1124 assert out.isCanonical();
1125 op2result.put(op, out);
1130 public static ReachSet unshadow(ReachSet rs,
1134 assert rs.isCanonical();
1135 assert as.isCanonical();
1138 new CanonicalOp(CanonicalOp.REACHSET_UNSHADOW_ALLOCSITE,
1142 Canonical result = op2result.get(op);
1143 if( result != null ) {
1144 return (ReachSet) result;
1147 // otherwise, no cached result...
1148 ReachSet out = ReachSet.factory();
1149 Iterator<ReachState> itr = rs.iterator();
1150 while( itr.hasNext() ) {
1151 ReachState state = itr.next();
1152 out = Canonical.add(out,
1153 Canonical.unshadow(state, as)
1157 assert out.isCanonical();
1158 op2result.put(op, out);
1162 public static ReachState unshadow(ReachState state,
1164 assert state != null;
1166 assert state.isCanonical();
1167 assert as.isCanonical();
1170 new CanonicalOp(CanonicalOp.REACHSTATE_UNSHADOW_ALLOCSITE,
1174 Canonical result = op2result.get(op);
1175 if( result != null ) {
1176 return (ReachState) result;
1179 // this is the current mapping, where 0, 1, 2S were allocated
1180 // in the current context, 0?, 1? and 2S? were allocated in a
1181 // previous context, and we're translating to a future context
1187 // otherwise, no cached result...
1188 ReachState out = ReachState.factory();
1189 Iterator<ReachTuple> itr = state.iterator();
1190 while( itr.hasNext() ) {
1191 ReachTuple rt = itr.next();
1193 int age = as.getShadowAgeCategory(rt.getHrnID() );
1195 if( age == AllocSite.SHADOWAGE_notInThisSite ) {
1196 // things not from the site just go back in
1197 out = Canonical.addUpArity(out, rt);
1200 assert !rt.isOutOfContext();
1202 // otherwise unshadow it
1203 out = Canonical.addUpArity(out,
1204 ReachTuple.factory(-rt.getHrnID(),
1213 out = Canonical.attach(out,
1217 assert out.isCanonical();
1218 op2result.put(op, out);
1224 public static ReachState changePredsTo(ReachState rs,
1225 ExistPredSet preds) {
1227 assert rs.isCanonical();
1230 new CanonicalOp(CanonicalOp.REACHSTATE_CHANGEPREDSTO_EXISTPREDSET,
1234 Canonical result = op2result.get(op);
1235 if( result != null ) {
1236 return (ReachState) result;
1239 // otherwise, no cached result...
1240 ReachState out = new ReachState();
1242 // just remake state with the true predicate attached
1243 out.reachTuples.addAll(rs.reachTuples);
1246 out = (ReachState) makeCanonical(out);
1247 op2result.put(op, out);
1252 public static ReachSet changePredsTo(ReachSet rs,
1253 ExistPredSet preds) {
1255 assert rs.isCanonical();
1258 new CanonicalOp(CanonicalOp.REACHSET_CHANGEPREDSTO_EXISTPREDSET,
1262 Canonical result = op2result.get(op);
1263 if( result != null ) {
1264 return (ReachSet) result;
1267 // otherwise, no cached result...
1268 ReachSet out = ReachSet.factory();
1269 Iterator<ReachState> itr = rs.iterator();
1270 while( itr.hasNext() ) {
1271 ReachState state = itr.next();
1272 out = Canonical.add(out,
1273 Canonical.changePredsTo(state,
1279 out = (ReachSet) makeCanonical(out);
1280 op2result.put(op, out);
1285 public static Taint attach(Taint t,
1286 ExistPredSet preds) {
1288 assert preds != null;
1289 assert t.isCanonical();
1290 assert preds.isCanonical();
1293 new CanonicalOp(CanonicalOp.TAINT_ATTACH_EXISTPREDSET,
1297 Canonical result = op2result.get(op);
1298 if( result != null ) {
1299 return (Taint) result;
1302 // otherwise, no cached result...
1303 Taint out = new Taint(t);
1304 out.preds = Canonical.join(t.preds,
1307 out = (Taint) makeCanonical(out);
1308 op2result.put(op, out);
1312 public static TaintSet add(TaintSet ts,
1316 assert ts.isCanonical();
1317 assert t.isCanonical();
1320 new CanonicalOp(CanonicalOp.TAINTSET_ADD_TAINT,
1324 Canonical result = op2result.get(op);
1325 if( result != null ) {
1326 return (TaintSet) result;
1329 // otherwise, no cached result...
1330 TaintSet out = new TaintSet();
1331 out.taints.addAll(ts.taints);
1334 out = (TaintSet) makeCanonical(out);
1335 op2result.put(op, out);
1340 public static TaintSet addPTR(TaintSet ts,
1345 public static TaintSet union(TaintSet ts1,
1349 assert ts1.isCanonical();
1350 assert ts2.isCanonical();
1353 new CanonicalOp(CanonicalOp.TAINTSET_UNION_TAINTSET,
1357 Canonical result = op2result.get(op);
1358 if( result != null ) {
1359 return (TaintSet) result;
1362 // otherwise, no cached result...
1363 TaintSet out = new TaintSet();
1365 // first add everything from 1, and if it was also in 2
1366 // take the OR of the predicates
1367 Iterator<Taint> tItr = ts1.iterator();
1368 while( tItr.hasNext() ) {
1369 Taint t1 = tItr.next();
1370 Taint t2 = ts2.containsIgnorePreds(t1);
1373 Taint tNew = new Taint(t1);
1374 tNew.preds = Canonical.join(t1.preds,
1377 tNew = (Taint) makeCanonical(tNew);
1378 out.taints.add(tNew);
1384 // then add everything in 2 that wasn't in 1
1385 tItr = ts2.iterator();
1386 while( tItr.hasNext() ) {
1387 Taint t2 = tItr.next();
1388 Taint t1 = ts1.containsIgnorePreds(t2);
1395 out = (TaintSet) makeCanonical(out);
1396 op2result.put(op, out);
1400 public static TaintSet unionPTR(TaintSet ts1,
1404 assert ts1.isCanonical();
1405 assert ts2.isCanonical();
1408 new CanonicalOp(CanonicalOp.TAINTSET_UNION_TAINTSET,
1412 Canonical result = op2result.get(op);
1413 if( result != null ) {
1414 return (TaintSet) result;
1417 // otherwise, no cached result...
1418 TaintSet out = new TaintSet();
1420 out.taints.addAll(ts1.taints);
1421 out.taints.addAll(ts2.taints);
1422 out= (TaintSet) Canonical.makeCanonical(out);
1423 op2result.put(op, out);
1427 public static TaintSet unionORpreds(TaintSet ts1,
1431 assert ts1.isCanonical();
1432 assert ts2.isCanonical();
1435 new CanonicalOp(CanonicalOp.TAINTSET_UNIONORPREDS_TAINTSET,
1439 Canonical result = op2result.get(op);
1440 if( result != null ) {
1441 return (TaintSet) result;
1444 // otherwise, no cached result...
1445 TaintSet out = new TaintSet();
1447 // first add everything from 1, and if it was also in 2
1448 // take the OR of the predicates
1449 Iterator<Taint> tItr = ts1.iterator();
1450 while( tItr.hasNext() ) {
1451 Taint t1 = tItr.next();
1452 Taint t2 = ts2.containsIgnorePreds(t1);
1455 Taint tNew = new Taint(t1);
1456 tNew.preds = Canonical.join(t1.preds,
1459 tNew = (Taint) makeCanonical(tNew);
1460 out.taints.add(tNew);
1466 // then add everything in 2 that wasn't in 1
1467 tItr = ts2.iterator();
1468 while( tItr.hasNext() ) {
1469 Taint t2 = tItr.next();
1470 Taint t1 = ts1.containsIgnorePreds(t2);
1477 out = (TaintSet) makeCanonical(out);
1478 op2result.put(op, out);
1483 // BOO, HISS! SESE (rblock) operand does NOT extend
1484 // Canonical, so we can't cache this op by its
1485 // canonical arguments--THINK ABOUT A BETTER WAY!
1486 public static TaintSet removeInContextTaints(TaintSet ts,
1487 FlatSESEEnterNode sese) {
1489 assert ts.isCanonical();
1490 assert sese != null;
1492 // NEVER a cached result... (cry)
1493 TaintSet out = new TaintSet();
1495 Iterator<Taint> tItr = ts.iterator();
1496 while( tItr.hasNext() ) {
1497 Taint t = tItr.next();
1499 // what is allowed through? stall site taints always
1500 // go through, anything where rblock doesn't match is
1501 // unaffected, and if the taint has a non-empty predicate
1502 // it is out of context so it should go through, too
1503 if( t.getSESE() == null ||
1504 !t.getSESE().equals(sese) ||
1505 !t.getPreds().isEmpty()
1511 out = (TaintSet) makeCanonical(out);
1512 //op2result.put( op, out ); CRY CRY
1516 // BOO, HISS! SESE (rblock) operand does NOT extend
1517 // Canonical, so we can't cache this op by its
1518 // canonical arguments--THINK ABOUT A BETTER WAY!
1519 public static TaintSet removeSESETaints(TaintSet ts,
1520 Set<FlatSESEEnterNode> seseSet) {
1522 assert ts.isCanonical();
1524 // NEVER a cached result... (cry)
1525 TaintSet out = new TaintSet();
1527 Iterator<Taint> tItr = ts.iterator();
1528 while( tItr.hasNext() ) {
1529 Taint t = tItr.next();
1531 // what is allowed through? stall site taints always
1532 // go through, anything where rblock doesn't match is
1533 // unaffected, and if the taint has a non-empty predicate
1534 // it is out of context so it should go through, too
1535 if( t.getSESE() == null ||
1536 !seseSet.contains(t)) {
1541 out = (TaintSet) makeCanonical(out);
1542 //op2result.put( op, out ); CRY CRY
1546 public static TaintSet removeInContextTaintsNP(TaintSet ts,
1547 FlatSESEEnterNode sese) {
1549 assert ts.isCanonical();
1551 // NEVER a cached result... (cry)
1552 TaintSet out = new TaintSet();
1554 Iterator<Taint> tItr = ts.iterator();
1555 while( tItr.hasNext() ) {
1556 Taint t = tItr.next();
1558 // what is allowed through? stall site taints always
1559 // go through, anything where rblock doesn't match is
1560 // unaffected, and if the taint has a non-empty predicate
1561 // it is out of context so it should go through, too
1562 if( t.getSESE()!=null && t.getSESE()!=sese) {
1567 out = (TaintSet) makeCanonical(out);
1571 public static TaintSet removeStallSiteTaints(TaintSet ts) {
1573 assert ts.isCanonical();
1576 new CanonicalOp(CanonicalOp.TAINTSET_REMOVESTALLSITETAINTS,
1580 Canonical result = op2result.get(op);
1581 if( result != null ) {
1582 return (TaintSet) result;
1585 // otherwise, no cached result...
1586 TaintSet out = new TaintSet();
1588 Iterator<Taint> tItr = ts.iterator();
1589 while( tItr.hasNext() ) {
1590 Taint t = tItr.next();
1592 // only take non-stall site taints onward
1593 if( t.getStallSite() == null ) {
1598 out = (TaintSet) makeCanonical(out);
1599 op2result.put(op, out);
1604 public static Taint changePredsTo(Taint t,
1605 ExistPredSet preds) {
1607 assert t.isCanonical();
1610 new CanonicalOp(CanonicalOp.TAINT_CHANGEPREDSTO_EXISTPREDSET,
1614 Canonical result = op2result.get(op);
1615 if( result != null ) {
1616 return (Taint) result;
1619 // otherwise, no cached result...
1620 Taint out = new Taint(t.sese,
1628 out = (Taint) makeCanonical(out);
1629 op2result.put(op, out);
1634 public static TaintSet changePredsTo(TaintSet ts,
1635 ExistPredSet preds) {
1637 assert ts.isCanonical();
1640 new CanonicalOp(CanonicalOp.TAINTSET_CHANGEPREDSTO_EXISTPREDSET,
1644 Canonical result = op2result.get(op);
1645 if( result != null ) {
1646 return (TaintSet) result;
1649 // otherwise, no cached result...
1650 TaintSet out = TaintSet.factory();
1651 Iterator<Taint> itr = ts.iterator();
1652 while( itr.hasNext() ) {
1653 Taint t = itr.next();
1654 out = Canonical.add(out,
1655 Canonical.changePredsTo(t, preds)
1659 out = (TaintSet) makeCanonical(out);
1660 op2result.put(op, out);
1666 // BOO, HISS! FlatNode operand does NOT extend
1667 // Canonical, so we can't cache this op by its
1668 // canonical arguments--THINK ABOUT A BETTER WAY!
1669 public static Taint changeWhereDefined(Taint t,
1672 assert t.isCanonical();
1674 // never a cached result...
1675 Taint out = new Taint(t.sese,
1683 out = (Taint) makeCanonical(out);
1684 //op2result.put( op, out ); CRY CRY
1688 // BOO, HISS! FlatNode operand does NOT extend
1689 // Canonical, so we can't cache this op by its
1690 // canonical arguments--THINK ABOUT A BETTER WAY!
1691 public static TaintSet changeWhereDefined(TaintSet ts,
1694 assert ts.isCanonical();
1696 // never a cached result...
1697 TaintSet out = TaintSet.factory();
1698 Iterator<Taint> itr = ts.iterator();
1699 while( itr.hasNext() ) {
1700 Taint t = itr.next();
1701 out = Canonical.add(out,
1702 Canonical.changeWhereDefined(t, pp)
1706 out = (TaintSet) makeCanonical(out);
1707 //op2result.put( op, out ); CRY CRY