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);
53 public boolean containsBoth(TokenTuple tt1, TokenTuple tt2) {
54 return containsTuple(tt1) && containsTuple(tt2);
57 public boolean containsWithZeroes(TokenTupleSet tts) {
60 // first establish that every token tuple from tts is
62 Iterator<TokenTuple> ttItrIn = tts.iterator();
63 while( ttItrIn.hasNext() ) {
64 TokenTuple ttIn = ttItrIn.next();
65 TokenTuple ttThis = this.containsToken(ttIn.getToken() );
67 if( ttThis == null ) {
72 // then establish that anything in this set that is
73 // not in tts is a zero-arity token tuple, which is okay
74 Iterator<TokenTuple> ttItrThis = this.iterator();
75 while( ttItrThis.hasNext() ) {
76 TokenTuple ttThis = ttItrThis.next();
77 TokenTuple ttIn = tts.containsToken(ttThis.getToken() );
80 ttThis.getArity() != TokenTuple.ARITY_ZEROORMORE ) {
85 // if so this set contains tts with zeroes
89 public TokenTupleSet union(TokenTuple ttIn) {
91 ReachOperation ro=new ReachOperation(this, ttIn);
92 if (unionhash.containsKey(ro))
93 return (TokenTupleSet) unionhash.get(ro).c;
95 TokenTupleSet ttsOut = new TokenTupleSet(this);
96 ttsOut.tokenTuples.add(ttIn);
97 ro.c=ttsOut=ttsOut.makeCanonical();
103 public TokenTupleSet union(TokenTupleSet ttsIn) {
104 assert ttsIn != null;
105 ReachOperation ro=new ReachOperation(this, ttsIn);
106 if (unionhash.containsKey(ro)) {
107 return (TokenTupleSet) unionhash.get(ro).c;
109 TokenTupleSet ttsOut = new TokenTupleSet(this);
110 ttsOut.tokenTuples.addAll(ttsIn.tokenTuples);
111 ro.c=ttsOut=ttsOut.makeCanonical();
112 unionhash.put(ro,ro);
118 public TokenTupleSet unionUpArity(TokenTupleSet ttsIn) {
119 assert ttsIn != null;
120 TokenTupleSet ttsOut = new TokenTupleSet();
122 Iterator<TokenTuple> ttItr = this.iterator();
123 while( ttItr.hasNext() ) {
124 TokenTuple ttThis = ttItr.next();
125 TokenTuple ttIn = ttsIn.containsToken(ttThis.getToken() );
128 ttsOut.tokenTuples.add(ttThis.unionArity(ttIn) );
130 ttsOut.tokenTuples.add(ttThis);
134 ttItr = ttsIn.iterator();
135 while( ttItr.hasNext() ) {
136 TokenTuple ttIn = ttItr.next();
137 TokenTuple ttThis = ttsOut.containsToken(ttIn.getToken() );
139 if( ttThis == null ) {
140 ttsOut.tokenTuples.add(ttIn);
144 return ttsOut.makeCanonical();
148 public TokenTupleSet add(TokenTuple tt) {
150 return this.union(tt);
154 public TokenTupleSet remove(TokenTuple tt) {
156 TokenTupleSet ttsOut = new TokenTupleSet(this);
157 ttsOut.tokenTuples.remove(tt);
158 return ttsOut.makeCanonical();
162 public boolean equals(Object o) {
167 if( !(o instanceof TokenTupleSet) ) {
171 TokenTupleSet tts = (TokenTupleSet) o;
172 return tokenTuples.equals(tts.tokenTuples);
175 boolean hashcodecomputed=false;
179 public int hashCode() {
180 if (hashcodecomputed)
183 ourhashcode=tokenTuples.hashCode();
184 hashcodecomputed=true;
190 // this should be a hash table so we can do this by key
191 public TokenTuple containsToken(Integer token) {
192 assert token != null;
194 Iterator itr = tokenTuples.iterator();
195 while( itr.hasNext() ) {
196 TokenTuple tt = (TokenTuple) itr.next();
197 if( token.equals(tt.getToken() ) ) {
205 public TokenTupleSet ageTokens(AllocationSite as) {
208 TokenTupleSet ttsOut = new TokenTupleSet();
210 TokenTuple ttSummary = null;
211 TokenTuple ttOldest = null;
213 Iterator itrT = this.iterator();
214 while( itrT.hasNext() ) {
215 TokenTuple tt = (TokenTuple) itrT.next();
217 Integer token = tt.getToken();
218 int age = as.getAgeCategory(token);
220 // tokens not associated with
221 // the site should be left alone
222 if( age == AllocationSite.AGE_notInThisSite ) {
223 ttsOut.tokenTuples.add(tt);
225 } else if( age == AllocationSite.AGE_summary ) {
226 // remember the summary tuple, but don't add it
227 // we may combine it with the oldest tuple
230 } else if( age == AllocationSite.AGE_oldest ) {
231 // found an oldest token, again just remember
236 assert age == AllocationSite.AGE_in_I;
238 Integer I = as.getAge(token);
241 // otherwise, we change this token to the
243 Integer tokenToChangeTo = as.getIthOldest(I + 1);
244 TokenTuple ttAged = tt.changeTokenTo(tokenToChangeTo);
245 ttsOut.tokenTuples.add(ttAged);
249 // there are four cases to consider here
250 // 1. we found a summary tuple and no oldest tuple
251 // Here we just pass the summary unchanged
252 // 2. we found an oldest tuple, no summary
253 // Make a new, arity-one summary tuple
254 // 3. we found both a summary and an oldest
255 // Merge them by arity
256 // 4. (not handled) we found neither, do nothing
257 if ( ttSummary != null && ttOldest == null ) {
258 ttsOut.tokenTuples.add(ttSummary);
260 } else if( ttSummary == null && ttOldest != null ) {
261 ttsOut.tokenTuples.add(new TokenTuple(as.getSummary(),
267 } else if( ttSummary != null && ttOldest != null ) {
268 ttsOut.tokenTuples.add(ttSummary.unionArity(new TokenTuple(as.getSummary(),
276 return ttsOut.makeCanonical();
280 public TokenTupleSet unshadowTokens(AllocationSite as) {
283 TokenTupleSet ttsOut = new TokenTupleSet();
285 TokenTuple ttSummary = null;
286 TokenTuple ttShadowSummary = null;
288 Iterator itrT = this.iterator();
289 while( itrT.hasNext() ) {
290 TokenTuple tt = (TokenTuple) itrT.next();
292 Integer token = tt.getToken();
293 int shadowAge = as.getShadowAgeCategory(token);
295 if( shadowAge == AllocationSite.AGE_summary ) {
296 // remember the summary tuple, but don't add it
297 // we may combine it with the oldest tuple
300 } else if( shadowAge == AllocationSite.SHADOWAGE_notInThisSite ) {
301 ttsOut.tokenTuples.add(tt);
303 } else if( shadowAge == AllocationSite.SHADOWAGE_summary ) {
304 // found the shadow summary token, again just remember
306 ttShadowSummary = tt;
308 } else if( shadowAge == AllocationSite.SHADOWAGE_oldest ) {
309 Integer tokenToChangeTo = as.getOldest();
310 TokenTuple ttNormal = tt.changeTokenTo(tokenToChangeTo);
311 ttsOut.tokenTuples.add(ttNormal);
314 assert shadowAge == AllocationSite.SHADOWAGE_in_I;
316 Integer I = as.getShadowAge(token);
319 Integer tokenToChangeTo = as.getIthOldest(-I);
320 TokenTuple ttNormal = tt.changeTokenTo(tokenToChangeTo);
321 ttsOut.tokenTuples.add(ttNormal);
325 if ( ttSummary != null && ttShadowSummary == null ) {
326 ttsOut.tokenTuples.add(ttSummary);
328 } else if( ttSummary == null && ttShadowSummary != null ) {
329 ttsOut.tokenTuples.add(new TokenTuple(as.getSummary(),
331 ttShadowSummary.getArity()
335 } else if( ttSummary != null && ttShadowSummary != null ) {
336 ttsOut.tokenTuples.add(ttSummary.unionArity(new TokenTuple(as.getSummary(),
338 ttShadowSummary.getArity()
344 return ttsOut.makeCanonical();
348 public TokenTupleSet toShadowTokens(AllocationSite as) {
351 TokenTupleSet ttsOut = new TokenTupleSet().makeCanonical();
353 Iterator itrT = this.iterator();
354 while( itrT.hasNext() ) {
355 TokenTuple tt = (TokenTuple) itrT.next();
357 Integer token = tt.getToken();
358 int age = as.getAgeCategory(token);
360 // summary tokens and tokens not associated with
361 // the site should be left alone
362 if( age == AllocationSite.AGE_notInThisSite ) {
363 ttsOut = ttsOut.union(tt);
365 } else if( age == AllocationSite.AGE_summary ) {
366 ttsOut = ttsOut.union(tt.changeTokenTo(as.getSummaryShadow() ));
368 } else if( age == AllocationSite.AGE_oldest ) {
369 ttsOut = ttsOut.union(tt.changeTokenTo(as.getOldestShadow() ));
372 assert age == AllocationSite.AGE_in_I;
374 Integer I = as.getAge(token);
377 ttsOut = ttsOut.union(tt.changeTokenTo(as.getIthOldestShadow(I) ));
381 return ttsOut.makeCanonical();
385 public ReachabilitySet rewriteToken(TokenTuple tokenToRewrite,
386 ReachabilitySet replacements,
387 boolean makeChangeSet,
388 Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > forChangeSet) {
390 ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
392 if( !tokenTuples.contains(tokenToRewrite) ) {
393 rsOut = rsOut.add(this);
396 TokenTupleSet ttsMinusToken = new TokenTupleSet(this);
397 ttsMinusToken.tokenTuples.remove(tokenToRewrite);
399 Iterator<TokenTupleSet> replaceItr = replacements.iterator();
400 while( replaceItr.hasNext() ) {
401 TokenTupleSet replacement = replaceItr.next();
402 TokenTupleSet replaced = new TokenTupleSet(ttsMinusToken).makeCanonical();
403 replaced = replaced.unionUpArity(replacement);
404 rsOut = rsOut.add(replaced);
406 if( makeChangeSet ) {
407 assert forChangeSet != null;
409 if( forChangeSet.get(this) == null ) {
410 forChangeSet.put(this, new HashSet<TokenTupleSet>() );
413 forChangeSet.get(this).add(replaced);
418 return rsOut.makeCanonical();
422 public TokenTupleSet makeArityZeroOrMore() {
423 TokenTupleSet ttsOut = new TokenTupleSet().makeCanonical();
425 Iterator<TokenTuple> itrThis = this.iterator();
426 while( itrThis.hasNext() ) {
427 TokenTuple tt = itrThis.next();
429 ttsOut = ttsOut.union(new TokenTuple(tt.getToken(),
431 TokenTuple.ARITY_ZEROORMORE
436 return ttsOut.makeCanonical();
439 public String toString() {
440 return tokenTuples.toString();