001: /*
002: * Copyright 1996-2003 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026: package sun.tools.tree;
027:
028: import sun.tools.java.*;
029:
030: /**
031: * WARNING: The contents of this source file are not part of any
032: * supported API. Code that depends on them does so at its own risk:
033: * they are subject to change or removal without notice.
034: */
035: public final class Vset implements Constants {
036: long vset; // DA bits for first 64 variables
037: long uset; // DU bits for first 64 variables
038:
039: // The extension array is interleaved, consisting of alternating
040: // blocks of 64 DA bits followed by 64 DU bits followed by 64 DA
041: // bits, and so on.
042:
043: long x[]; // extension array for more bits
044:
045: // An infinite vector of zeroes or an infinite vector of ones is
046: // represented by a special value of the extension array.
047: //
048: // IMPORTANT: The condition 'this.x == fullX' is used as a marker for
049: // unreachable code, i.e., for a dead-end. We maintain the invariant
050: // that (this.x != fullX || (this.vset == -1 && this.uset == -1)).
051: // A dead-end has the peculiar property that all variables are both
052: // definitely assigned and definitely unassigned. We always force this
053: // condition to hold, even when the normal bitvector operations performed
054: // during DA/DU analysis would produce a different result. This supresses
055: // reporting of DA/DU errors in unreachable code.
056:
057: static final long emptyX[] = new long[0]; // all zeroes
058: static final long fullX[] = new long[0]; // all ones
059:
060: // For more thorough testing of long vset support, it is helpful to
061: // temporarily redefine this value to a smaller number, such as 1 or 2.
062:
063: static final int VBITS = 64; // number of bits in vset (uset)
064:
065: /**
066: * This is the Vset which reports all vars assigned and unassigned.
067: * This impossibility is degenerately true exactly when
068: * control flow cannot reach this point.
069: */
070:
071: // We distinguish a canonical dead-end value generated initially for
072: // statements that do not complete normally, making the next one unreachable.
073: // Once an unreachable statement is reported, a non-canonical dead-end value
074: // is used for subsequent statements in order to suppress redundant error
075: // messages.
076: static final Vset DEAD_END = new Vset(-1, -1, fullX);
077:
078: /**
079: * Create an empty Vset.
080: */
081: public Vset() {
082: this .x = emptyX;
083: }
084:
085: private Vset(long vset, long uset, long x[]) {
086: this .vset = vset;
087: this .uset = uset;
088: this .x = x;
089: }
090:
091: /**
092: * Create an copy of the given Vset.
093: * (However, DEAD_END simply returns itself.)
094: */
095: public Vset copy() {
096: if (this == DEAD_END) {
097: return this ;
098: }
099: Vset vs = new Vset(vset, uset, x);
100: if (x.length > 0) {
101: vs.growX(x.length); // recopy the extension vector
102: }
103: return vs;
104: }
105:
106: private void growX(int length) {
107: long newX[] = new long[length];
108: long oldX[] = x;
109: for (int i = 0; i < oldX.length; i++) {
110: newX[i] = oldX[i];
111: }
112: x = newX;
113: }
114:
115: /**
116: * Ask if this is a vset for a dead end.
117: * Answer true only for the canonical dead-end, DEAD_END.
118: * A canonical dead-end is produced only as a result of
119: * a statement that cannot complete normally, as specified
120: * by the JLS. Due to the special-case rules for if-then
121: * and if-then-else, this may fail to detect actual unreachable
122: * code that could easily be identified.
123: */
124:
125: public boolean isDeadEnd() {
126: return (this == DEAD_END);
127: }
128:
129: /**
130: * Ask if this is a vset for a dead end.
131: * Answer true for any dead-end.
132: * Since 'clearDeadEnd' has no effect on this predicate,
133: * if-then and if-then-else are handled in the more 'obvious'
134: * and precise way. This predicate is to be preferred for
135: * dead code elimination purposes.
136: * (Presently used in workaround for bug 4173473 in MethodExpression.java)
137: */
138: public boolean isReallyDeadEnd() {
139: return (x == fullX);
140: }
141:
142: /**
143: * Replace canonical DEAD_END with a distinct but
144: * equivalent Vset. The bits are unaltered, but
145: * the result does not answer true to 'isDeadEnd'.
146: * <p>
147: * Used mostly for error recovery, but see
148: * 'IfStatement.check', where it is used to
149: * implement the special-case treatment of
150: * statement reachability for such statements.
151: */
152: public Vset clearDeadEnd() {
153: if (this == DEAD_END) {
154: return new Vset(-1, -1, fullX);
155: }
156: return this ;
157: }
158:
159: /**
160: * Ask if a var is definitely assigned.
161: */
162: public boolean testVar(int varNumber) {
163: long bit = (1L << varNumber);
164: if (varNumber >= VBITS) {
165: int i = (varNumber / VBITS - 1) * 2;
166: if (i >= x.length) {
167: return (x == fullX);
168: }
169: return (x[i] & bit) != 0;
170: } else {
171: return (vset & bit) != 0;
172: }
173: }
174:
175: /**
176: * Ask if a var is definitely un-assigned.
177: * (This is not just the negation of testVar:
178: * It's possible for neither to be true.)
179: */
180: public boolean testVarUnassigned(int varNumber) {
181: long bit = (1L << varNumber);
182: if (varNumber >= VBITS) {
183: // index "uset" extension
184: int i = ((varNumber / VBITS - 1) * 2) + 1;
185: if (i >= x.length) {
186: return (x == fullX);
187: }
188: return (x[i] & bit) != 0;
189: } else {
190: return (uset & bit) != 0;
191: }
192: }
193:
194: /**
195: * Note that a var is definitely assigned.
196: * (Side-effecting.)
197: */
198: public Vset addVar(int varNumber) {
199: if (x == fullX) {
200: return this ;
201: }
202:
203: // gen DA, kill DU
204:
205: long bit = (1L << varNumber);
206: if (varNumber >= VBITS) {
207: int i = (varNumber / VBITS - 1) * 2;
208: if (i >= x.length) {
209: growX(i + 1);
210: }
211: x[i] |= bit;
212: if (i + 1 < x.length) {
213: x[i + 1] &= ~bit;
214: }
215: } else {
216: vset |= bit;
217: uset &= ~bit;
218: }
219: return this ;
220: }
221:
222: /**
223: * Note that a var is definitely un-assigned.
224: * (Side-effecting.)
225: */
226: public Vset addVarUnassigned(int varNumber) {
227: if (x == fullX) {
228: return this ;
229: }
230:
231: // gen DU, kill DA
232:
233: long bit = (1L << varNumber);
234: if (varNumber >= VBITS) {
235: // index "uset" extension
236: int i = ((varNumber / VBITS - 1) * 2) + 1;
237: if (i >= x.length) {
238: growX(i + 1);
239: }
240: x[i] |= bit;
241: x[i - 1] &= ~bit;
242: } else {
243: uset |= bit;
244: vset &= ~bit;
245: }
246: return this ;
247: }
248:
249: /**
250: * Retract any assertion about the var.
251: * This operation is ineffective on a dead-end.
252: * (Side-effecting.)
253: */
254: public Vset clearVar(int varNumber) {
255: if (x == fullX) {
256: return this ;
257: }
258: long bit = (1L << varNumber);
259: if (varNumber >= VBITS) {
260: int i = (varNumber / VBITS - 1) * 2;
261: if (i >= x.length) {
262: return this ;
263: }
264: x[i] &= ~bit;
265: if (i + 1 < x.length) {
266: x[i + 1] &= ~bit;
267: }
268: } else {
269: vset &= ~bit;
270: uset &= ~bit;
271: }
272: return this ;
273: }
274:
275: /**
276: * Join with another vset. This is set intersection.
277: * (Side-effecting.)
278: */
279: public Vset join(Vset other) {
280:
281: // Return a dead-end if both vsets are dead-ends.
282: // Return the canonical DEAD_END only if both vsets
283: // are the canonical DEAD_END. Otherwise, an incoming
284: // dead-end vset has already produced an error message,
285: // and is now assumed to be reachable.
286: if (this == DEAD_END) {
287: return other.copy();
288: }
289: if (other == DEAD_END) {
290: return this ;
291: }
292: if (x == fullX) {
293: return other.copy();
294: }
295: if (other.x == fullX) {
296: return this ;
297: }
298:
299: // DA = DA intersection DA
300: // DU = DU intersection DU
301:
302: vset &= other.vset;
303: uset &= other.uset;
304:
305: if (other.x == emptyX) {
306: x = emptyX;
307: } else {
308: // ASSERT(otherX.length > 0);
309: long otherX[] = other.x;
310: int selfLength = x.length;
311: int limit = (otherX.length < selfLength) ? otherX.length
312: : selfLength;
313: for (int i = 0; i < limit; i++) {
314: x[i] &= otherX[i];
315: }
316: // If self is longer than other, all remaining
317: // bits are implicitly 0. In the result, then,
318: // the remaining DA and DU bits are cleared.
319: for (int i = limit; i < selfLength; i++) {
320: x[i] = 0;
321: }
322: }
323: return this ;
324: }
325:
326: /**
327: * Add in the definite assignment bits of another vset,
328: * but join the definite unassignment bits. This unusual
329: * operation is used only for 'finally' blocks. The
330: * original vset 'this' is destroyed by this operation.
331: * (Part of fix for 4068688.)
332: */
333:
334: public Vset addDAandJoinDU(Vset other) {
335:
336: // Return a dead-end if either vset is a dead end.
337: // If either vset is the canonical DEAD_END, the
338: // result is also the canonical DEAD_END.
339: if (this == DEAD_END) {
340: return this ;
341: }
342: if (other == DEAD_END) {
343: return other;
344: }
345: if (x == fullX) {
346: return this ;
347: }
348: if (other.x == fullX) {
349: return other.copy();
350: }
351:
352: // DA = DA union DA'
353: // DU = (DU intersection DU') - DA'
354:
355: vset = vset | other.vset;
356: uset = (uset & other.uset) & ~other.vset;
357:
358: int selfLength = x.length;
359: long otherX[] = other.x;
360: int otherLength = otherX.length;
361:
362: if (otherX != emptyX) {
363: // ASSERT(otherX.length > 0);
364: if (otherLength > selfLength) {
365: growX(otherLength);
366: }
367: int i = 0;
368: while (i < otherLength) {
369: x[i] |= otherX[i];
370: i++;
371: if (i == otherLength)
372: break;
373: x[i] = ((x[i] & otherX[i]) & ~otherX[i - 1]);
374: i++;
375: }
376: }
377: // If self is longer than other, all remaining
378: // bits are implicitly 0. In the result, then,
379: // the remaining DA bits are left unchanged, and
380: // the DU bits are all cleared. First, align
381: // index to the next block of DU bits (odd index).
382: for (int i = (otherLength | 1); i < selfLength; i += 2) {
383: x[i] = 0;
384: }
385: return this ;
386: }
387:
388: /**
389: * Construct a vset consisting of the DA bits of the first argument
390: * and the DU bits of the second argument. This is a higly unusual
391: * operation, as it implies a case where the flowgraph for DA analysis
392: * differs from that for DU analysis. It is only needed for analysing
393: * 'try' blocks. The result is a dead-end iff the first argument is
394: * dead-end. (Part of fix for 4068688.)
395: */
396:
397: public static Vset firstDAandSecondDU(Vset sourceDA, Vset sourceDU) {
398:
399: // Note that reachability status is received via 'sourceDA' only!
400: // This is a consequence of the fact that reachability and DA
401: // analysis are performed on an identical flow graph, whereas the
402: // flowgraph for DU analysis differs in the case of a 'try' statement.
403: if (sourceDA.x == fullX) {
404: return sourceDA.copy();
405: }
406:
407: long sourceDAx[] = sourceDA.x;
408: int lenDA = sourceDAx.length;
409: long sourceDUx[] = sourceDU.x;
410: int lenDU = sourceDUx.length;
411: int limit = (lenDA > lenDU) ? lenDA : lenDU;
412: long x[] = emptyX;
413:
414: if (limit > 0) {
415: x = new long[limit];
416: for (int i = 0; i < lenDA; i += 2) {
417: x[i] = sourceDAx[i];
418: }
419: for (int i = 1; i < lenDU; i += 2) {
420: x[i] = sourceDUx[i];
421: }
422: }
423:
424: return new Vset(sourceDA.vset, sourceDU.uset, x);
425: }
426:
427: /**
428: * Remove variables from the vset that are no longer part of
429: * a context. Zeroes are stored past varNumber.
430: * (Side-effecting.)<p>
431: * However, if this is a dead end, keep it so.
432: * That is, leave an infinite tail of bits set.
433: */
434: public Vset removeAdditionalVars(int varNumber) {
435: if (x == fullX) {
436: return this ;
437: }
438: long bit = (1L << varNumber);
439: if (varNumber >= VBITS) {
440: int i = (varNumber / VBITS - 1) * 2;
441: if (i < x.length) {
442: x[i] &= (bit - 1);
443: if (++i < x.length) {
444: x[i] &= (bit - 1); // do the "uset" extension also
445: }
446: while (++i < x.length) {
447: x[i] = 0;
448: }
449: }
450: } else {
451: if (x.length > 0) {
452: x = emptyX;
453: }
454: vset &= (bit - 1);
455: uset &= (bit - 1);
456: }
457: return this ;
458: }
459:
460: /**
461: * Return one larger than the highest bit set.
462: */
463: public int varLimit() {
464: long vset;
465: int result;
466: scan: {
467: for (int i = (x.length / 2) * 2; i >= 0; i -= 2) {
468: if (i == x.length)
469: continue; // oops
470: vset = x[i];
471: if (i + 1 < x.length) {
472: vset |= x[i + 1]; // check the "uset" also
473: }
474: if (vset != 0) {
475: result = (i / 2 + 1) * VBITS;
476: break scan;
477: }
478: }
479: vset = this .vset;
480: vset |= this .uset; // check the "uset" also
481: if (vset != 0) {
482: result = 0;
483: break scan;
484: } else {
485: return 0;
486: }
487: }
488: while (vset != 0) {
489: result += 1;
490: vset >>>= 1;
491: }
492: return result;
493: }
494:
495: public String toString() {
496: if (this == DEAD_END)
497: return "{DEAD_END}";
498: StringBuffer sb = new StringBuffer("{");
499: int maxVar = VBITS * (1 + (x.length + 1) / 2);
500: for (int i = 0; i < maxVar; i++) {
501: if (!testVarUnassigned(i)) {
502: if (sb.length() > 1) {
503: sb.append(' ');
504: }
505: sb.append(i);
506: if (!testVar(i)) {
507: sb.append('?'); // not definitely unassigned
508: }
509: }
510: }
511: if (x == fullX) {
512: sb.append("...DEAD_END");
513: }
514: sb.append('}');
515: return sb.toString();
516: }
517:
518: }
|