1 package Analysis.OwnershipAnalysis;
9 public class TokenTupleSet extends Canonical {
11 private HashSet<TokenTuple> tokenTuples;
14 public TokenTupleSet() {
15 tokenTuples = new HashSet<TokenTuple>();
18 public TokenTupleSet(TokenTuple tt) {
24 public TokenTupleSet(TokenTupleSet tts) {
26 // okay to clone, TokenTuple and TokenTupleSet should be canonical
27 tokenTuples = (HashSet<TokenTuple>)tts.tokenTuples.clone();
31 public TokenTupleSet makeCanonical() {
32 return (TokenTupleSet) Canonical.makeCanonical(this);
35 public Iterator iterator() {
36 return tokenTuples.iterator();
39 public boolean isEmpty() {
40 return tokenTuples.isEmpty();
43 public boolean isSubset(TokenTupleSet ttsIn) {
45 return ttsIn.tokenTuples.containsAll(this.tokenTuples);
48 public boolean containsTuple(TokenTuple tt) {
50 return tokenTuples.contains(tt);
54 public TokenTupleSet union(TokenTuple ttIn) {
56 TokenTupleSet ttsOut = new TokenTupleSet(this);
57 ttsOut.tokenTuples.add(ttIn);
58 return ttsOut.makeCanonical();
61 public TokenTupleSet union(TokenTupleSet ttsIn) {
63 TokenTupleSet ttsOut = new TokenTupleSet(this);
64 ttsOut.tokenTuples.addAll(ttsIn.tokenTuples);
65 return ttsOut.makeCanonical();
69 public TokenTupleSet unionUpArity(TokenTupleSet ttsIn) {
71 TokenTupleSet ttsOut = new TokenTupleSet();
73 Iterator<TokenTuple> ttItr = this.iterator();
74 while( ttItr.hasNext() ) {
75 TokenTuple ttThis = ttItr.next();
76 TokenTuple ttIn = ttsIn.containsToken( ttThis.getToken() );
79 ttsOut.tokenTuples.add( ttThis.unionArity( ttIn ) );
81 ttsOut.tokenTuples.add( ttThis );
85 ttItr = ttsIn.iterator();
86 while( ttItr.hasNext() ) {
87 TokenTuple ttIn = ttItr.next();
88 TokenTuple ttThis = ttsOut.containsToken( ttIn.getToken() );
90 if( ttThis == null ) {
91 ttsOut.tokenTuples.add( ttIn );
95 return ttsOut.makeCanonical();
99 public TokenTupleSet add(TokenTuple tt) {
101 TokenTupleSet ttsOut = new TokenTupleSet(tt);
102 return ttsOut.union(this);
106 public boolean equals(Object o) {
111 if( !(o instanceof TokenTupleSet) ) {
115 TokenTupleSet tts = (TokenTupleSet) o;
116 return tokenTuples.equals(tts.tokenTuples);
121 private boolean oldHashSet = false;
122 private int oldHash = 0;
123 public int hashCode() {
124 int currentHash = tokenTuples.hashCode();
126 if( oldHashSet == false ) {
127 oldHash = currentHash;
130 if( oldHash != currentHash ) {
131 System.out.println( "IF YOU SEE THIS A CANONICAL TokenTupleSet CHANGED" );
141 // this should be a hash table so we can do this by key
142 public TokenTuple containsToken(Integer token) {
143 assert token != null;
145 Iterator itr = tokenTuples.iterator();
146 while( itr.hasNext() ) {
147 TokenTuple tt = (TokenTuple) itr.next();
148 if( token.equals(tt.getToken() ) ) {
156 public TokenTupleSet ageTokens(AllocationSite as) {
159 TokenTupleSet ttsOut = new TokenTupleSet();
161 TokenTuple ttSummary = null;
162 TokenTuple ttOldest = null;
164 Iterator itrT = this.iterator();
165 while( itrT.hasNext() ) {
166 TokenTuple tt = (TokenTuple) itrT.next();
168 Integer token = tt.getToken();
169 int age = as.getAgeCategory(token);
171 // tokens not associated with
172 // the site should be left alone
173 if( age == AllocationSite.AGE_notInThisSite ) {
174 ttsOut.tokenTuples.add(tt);
176 } else if( age == AllocationSite.AGE_summary ) {
177 // remember the summary tuple, but don't add it
178 // we may combine it with the oldest tuple
181 } else if( age == AllocationSite.AGE_oldest ) {
182 // found an oldest token, again just remember
187 assert age == AllocationSite.AGE_in_I;
189 Integer I = as.getAge(token);
192 // otherwise, we change this token to the
194 Integer tokenToChangeTo = as.getIthOldest(I + 1);
195 TokenTuple ttAged = tt.changeTokenTo(tokenToChangeTo);
196 ttsOut.tokenTuples.add(ttAged);
200 // there are four cases to consider here
201 // 1. we found a summary tuple and no oldest tuple
202 // Here we just pass the summary unchanged
203 // 2. we found an oldest tuple, no summary
204 // Make a new, arity-one summary tuple
205 // 3. we found both a summary and an oldest
206 // Merge them by arity
207 // 4. (not handled) we found neither, do nothing
208 if ( ttSummary != null && ttOldest == null ) {
209 ttsOut.tokenTuples.add(ttSummary);
211 } else if( ttSummary == null && ttOldest != null ) {
212 ttsOut.tokenTuples.add(new TokenTuple(as.getSummary(),
218 } else if( ttSummary != null && ttOldest != null ) {
219 ttsOut.tokenTuples.add(ttSummary.unionArity(new TokenTuple(as.getSummary(),
227 return ttsOut.makeCanonical();
231 public TokenTupleSet unshadowTokens(AllocationSite as) {
234 TokenTupleSet ttsOut = new TokenTupleSet();
236 TokenTuple ttSummary = null;
237 TokenTuple ttShadowSummary = null;
239 Iterator itrT = this.iterator();
240 while( itrT.hasNext() ) {
241 TokenTuple tt = (TokenTuple) itrT.next();
243 Integer token = tt.getToken();
244 int shadowAge = as.getShadowAgeCategory(token);
246 if( shadowAge == AllocationSite.AGE_summary ) {
247 // remember the summary tuple, but don't add it
248 // we may combine it with the oldest tuple
251 } else if( shadowAge == AllocationSite.SHADOWAGE_notInThisSite ) {
252 ttsOut.tokenTuples.add(tt);
254 } else if( shadowAge == AllocationSite.SHADOWAGE_summary ) {
255 // found the shadow summary token, again just remember
257 ttShadowSummary = tt;
259 } else if( shadowAge == AllocationSite.SHADOWAGE_oldest ) {
260 Integer tokenToChangeTo = as.getOldest();
261 TokenTuple ttNormal = tt.changeTokenTo(tokenToChangeTo);
262 ttsOut.tokenTuples.add(ttNormal);
265 assert shadowAge == AllocationSite.SHADOWAGE_in_I;
267 Integer I = as.getShadowAge(token);
270 Integer tokenToChangeTo = as.getIthOldest(-I);
271 TokenTuple ttNormal = tt.changeTokenTo(tokenToChangeTo);
272 ttsOut.tokenTuples.add(ttNormal);
276 if ( ttSummary != null && ttShadowSummary == null ) {
277 ttsOut.tokenTuples.add(ttSummary);
279 } else if( ttSummary == null && ttShadowSummary != null ) {
280 ttsOut.tokenTuples.add( new TokenTuple(as.getSummary(),
282 ttShadowSummary.getArity()
286 } else if( ttSummary != null && ttShadowSummary != null ) {
287 ttsOut.tokenTuples.add(ttSummary.unionArity( new TokenTuple(as.getSummary(),
289 ttShadowSummary.getArity()
295 return ttsOut.makeCanonical();
299 public TokenTupleSet toShadowTokens(AllocationSite as) {
302 TokenTupleSet ttsOut = new TokenTupleSet().makeCanonical();
304 Iterator itrT = this.iterator();
305 while( itrT.hasNext() ) {
306 TokenTuple tt = (TokenTuple) itrT.next();
308 Integer token = tt.getToken();
309 int age = as.getAgeCategory(token);
311 // summary tokens and tokens not associated with
312 // the site should be left alone
313 if( age == AllocationSite.AGE_notInThisSite ) {
314 ttsOut = ttsOut.union(tt);
316 } else if( age == AllocationSite.AGE_summary ) {
317 ttsOut = ttsOut.union(tt.changeTokenTo(as.getSummaryShadow() ));
319 } else if( age == AllocationSite.AGE_oldest ) {
320 ttsOut = ttsOut.union(tt.changeTokenTo(as.getOldestShadow() ));
323 assert age == AllocationSite.AGE_in_I;
325 Integer I = as.getAge(token);
328 ttsOut = ttsOut.union(tt.changeTokenTo(as.getIthOldestShadow(I) ));
332 return ttsOut.makeCanonical();
336 public ReachabilitySet rewriteToken(TokenTuple tokenToRewrite,
337 ReachabilitySet replacements,
338 boolean makeChangeSet,
339 Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > forChangeSet) {
341 ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
343 if( !tokenTuples.contains(tokenToRewrite) ) {
344 rsOut = rsOut.add(this);
347 TokenTupleSet ttsMinusToken = new TokenTupleSet(this);
348 ttsMinusToken.tokenTuples.remove(tokenToRewrite);
350 Iterator<TokenTupleSet> replaceItr = replacements.iterator();
351 while( replaceItr.hasNext() ) {
352 TokenTupleSet replacement = replaceItr.next();
353 TokenTupleSet replaced = new TokenTupleSet(ttsMinusToken).makeCanonical();
354 replaced = replaced.unionUpArity(replacement);
355 rsOut = rsOut.add(replaced);
357 if( makeChangeSet ) {
358 assert forChangeSet != null;
360 if( forChangeSet.get(this) == null ) {
361 forChangeSet.put(this, new HashSet<TokenTupleSet>() );
364 forChangeSet.get(this).add(replaced);
369 return rsOut.makeCanonical();
373 public TokenTupleSet makeArityZeroOrMore() {
374 TokenTupleSet ttsOut = new TokenTupleSet().makeCanonical();
376 Iterator<TokenTuple> itrThis = this.iterator();
377 while( itrThis.hasNext() ) {
378 TokenTuple tt = itrThis.next();
380 ttsOut = ttsOut.union( new TokenTuple( tt.getToken(),
382 TokenTuple.ARITY_ZEROORMORE
387 return ttsOut.makeCanonical();
390 public String toString() {
391 return tokenTuples.toString();