View Javadoc
1   /*
2    * Copyright (c) 1996, 2003, Oracle and/or its affiliates. All rights reserved.
3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4    *
5    * This code is free software; you can redistribute it and/or modify it
6    * under the terms of the GNU General Public License version 2 only, as
7    * published by the Free Software Foundation.  Oracle designates this
8    * particular file as subject to the "Classpath" exception as provided
9    * by Oracle in the LICENSE file that accompanied this code.
10   *
11   * This code is distributed in the hope that it will be useful, but WITHOUT
12   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14   * version 2 for more details (a copy is included in the LICENSE file that
15   * accompanied this code).
16   *
17   * You should have received a copy of the GNU General Public License version
18   * 2 along with this work; if not, write to the Free Software Foundation,
19   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20   *
21   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22   * or visit www.oracle.com if you need additional information or have any
23   * questions.
24   */
25  
26  package sun.tools.tree;
27  
28  import sun.tools.java.*;
29  
30  /**
31   * WARNING: The contents of this source file are not part of any
32   * supported API.  Code that depends on them does so at its own risk:
33   * they are subject to change or removal without notice.
34   */
35  public final
36  class Vset implements Constants {
37      long vset;                  // DA bits for first 64 variables
38      long uset;                  // DU bits for first 64 variables
39  
40      // The extension array is interleaved, consisting of alternating
41      // blocks of 64 DA bits followed by 64 DU bits followed by 64 DA
42      // bits, and so on.
43  
44      long x[];                   // extension array for more bits
45  
46      // An infinite vector of zeroes or an infinite vector of ones is
47      // represented by a special value of the extension array.
48      //
49      // IMPORTANT: The condition 'this.x == fullX' is used as a marker for
50      // unreachable code, i.e., for a dead-end.  We maintain the invariant
51      // that (this.x != fullX || (this.vset == -1 && this.uset == -1)).
52      // A dead-end has the peculiar property that all variables are both
53      // definitely assigned and definitely unassigned.  We always force this
54      // condition to hold, even when the normal bitvector operations performed
55      // during DA/DU analysis would produce a different result.  This supresses
56      // reporting of DA/DU errors in unreachable code.
57  
58      static final long emptyX[] = new long[0]; // all zeroes
59      static final long fullX[]  = new long[0]; // all ones
60  
61      // For more thorough testing of long vset support, it is helpful to
62      // temporarily redefine this value to a smaller number, such as 1 or 2.
63  
64      static final int VBITS = 64; // number of bits in vset (uset)
65  
66      /**
67       * This is the Vset which reports all vars assigned and unassigned.
68       * This impossibility is degenerately true exactly when
69       * control flow cannot reach this point.
70       */
71  
72      // We distinguish a canonical dead-end value generated initially for
73      // statements that do not complete normally, making the next one unreachable.
74      // Once an unreachable statement is reported, a non-canonical dead-end value
75      // is used for subsequent statements in order to suppress redundant error
76      // messages.
77  
78      static final Vset DEAD_END = new Vset(-1, -1, fullX);
79  
80      /**
81       * Create an empty Vset.
82       */
83      public Vset() {
84          this.x = emptyX;
85      }
86  
87      private Vset(long vset, long uset, long x[]) {
88          this.vset = vset;
89          this.uset = uset;
90          this.x = x;
91      }
92  
93      /**
94       * Create an copy of the given Vset.
95       * (However, DEAD_END simply returns itself.)
96       */
97      public Vset copy() {
98          if (this == DEAD_END) {
99              return this;
100         }
101         Vset vs = new Vset(vset, uset, x);
102         if (x.length > 0) {
103             vs.growX(x.length); // recopy the extension vector
104         }
105         return vs;
106     }
107 
108     private void growX(int length) {
109         long newX[] = new long[length];
110         long oldX[] = x;
111         for (int i = 0; i < oldX.length; i++) {
112             newX[i] = oldX[i];
113         }
114         x = newX;
115     }
116 
117     /**
118      * Ask if this is a vset for a dead end.
119      * Answer true only for the canonical dead-end, DEAD_END.
120      * A canonical dead-end is produced only as a result of
121      * a statement that cannot complete normally, as specified
122      * by the JLS.  Due to the special-case rules for if-then
123      * and if-then-else, this may fail to detect actual unreachable
124      * code that could easily be identified.
125      */
126 
127     public boolean isDeadEnd() {
128         return (this == DEAD_END);
129     }
130 
131     /**
132      * Ask if this is a vset for a dead end.
133      * Answer true for any dead-end.
134      * Since 'clearDeadEnd' has no effect on this predicate,
135      * if-then and if-then-else are handled in the more 'obvious'
136      * and precise way.  This predicate is to be preferred for
137      * dead code elimination purposes.
138      * (Presently used in workaround for bug 4173473 in MethodExpression.java)
139      */
140     public boolean isReallyDeadEnd() {
141         return (x == fullX);
142     }
143 
144     /**
145      * Replace canonical DEAD_END with a distinct but
146      * equivalent Vset.  The bits are unaltered, but
147      * the result does not answer true to 'isDeadEnd'.
148      * <p>
149      * Used mostly for error recovery, but see
150      * 'IfStatement.check', where it is used to
151      * implement the special-case treatment of
152      * statement reachability for such statements.
153      */
154     public Vset clearDeadEnd() {
155         if (this == DEAD_END) {
156             return new Vset(-1, -1, fullX);
157         }
158         return this;
159     }
160 
161     /**
162      * Ask if a var is definitely assigned.
163      */
164     public boolean testVar(int varNumber) {
165         long bit = (1L << varNumber);
166         if (varNumber >= VBITS) {
167             int i = (varNumber / VBITS - 1) * 2;
168             if (i >= x.length) {
169                 return (x == fullX);
170             }
171             return (x[i] & bit) != 0;
172         } else {
173             return (vset & bit) != 0;
174         }
175     }
176 
177     /**
178      * Ask if a var is definitely un-assigned.
179      * (This is not just the negation of testVar:
180      * It's possible for neither to be true.)
181      */
182     public boolean testVarUnassigned(int varNumber) {
183         long bit = (1L << varNumber);
184         if (varNumber >= VBITS) {
185             // index "uset" extension
186             int i = ((varNumber / VBITS - 1) * 2) + 1;
187             if (i >= x.length) {
188                 return (x == fullX);
189             }
190             return (x[i] & bit) != 0;
191         } else {
192             return (uset & bit) != 0;
193         }
194     }
195 
196     /**
197      * Note that a var is definitely assigned.
198      * (Side-effecting.)
199      */
200     public Vset addVar(int varNumber) {
201         if (x == fullX) {
202             return this;
203         }
204 
205         // gen DA, kill DU
206 
207         long bit = (1L << varNumber);
208         if (varNumber >= VBITS) {
209             int i = (varNumber / VBITS - 1) * 2;
210             if (i >= x.length) {
211                 growX(i+1);
212             }
213             x[i] |= bit;
214             if (i+1 < x.length) {
215                 x[i+1] &=~ bit;
216             }
217         } else {
218             vset |= bit;
219             uset &=~ bit;
220         }
221         return this;
222     }
223 
224     /**
225      * Note that a var is definitely un-assigned.
226      * (Side-effecting.)
227      */
228     public Vset addVarUnassigned(int varNumber) {
229         if (x == fullX) {
230             return this;
231         }
232 
233         // gen DU, kill DA
234 
235         long bit = (1L << varNumber);
236         if (varNumber >= VBITS) {
237             // index "uset" extension
238             int i = ((varNumber / VBITS - 1) * 2) + 1;
239             if (i >= x.length) {
240                 growX(i+1);
241             }
242             x[i] |= bit;
243             x[i-1] &=~ bit;
244         } else {
245             uset |= bit;
246             vset &=~ bit;
247         }
248         return this;
249     }
250 
251     /**
252      * Retract any assertion about the var.
253      * This operation is ineffective on a dead-end.
254      * (Side-effecting.)
255      */
256     public Vset clearVar(int varNumber) {
257         if (x == fullX) {
258             return this;
259         }
260         long bit = (1L << varNumber);
261         if (varNumber >= VBITS) {
262             int i = (varNumber / VBITS - 1) * 2;
263             if (i >= x.length) {
264                 return this;
265             }
266             x[i] &=~ bit;
267             if (i+1 < x.length) {
268                 x[i+1] &=~ bit;
269             }
270         } else {
271             vset &=~ bit;
272             uset &=~ bit;
273         }
274         return this;
275     }
276 
277     /**
278      * Join with another vset.  This is set intersection.
279      * (Side-effecting.)
280      */
281     public Vset join(Vset other) {
282 
283         // Return a dead-end if both vsets are dead-ends.
284         // Return the canonical DEAD_END only if both vsets
285         // are the canonical DEAD_END.  Otherwise, an incoming
286         // dead-end vset has already produced an error message,
287         // and is now assumed to be reachable.
288         if (this == DEAD_END) {
289             return other.copy();
290         }
291         if (other == DEAD_END) {
292             return this;
293         }
294         if (x == fullX) {
295             return other.copy();
296         }
297         if (other.x == fullX) {
298             return this;
299         }
300 
301         // DA = DA intersection DA
302         // DU = DU intersection DU
303 
304         vset &= other.vset;
305         uset &= other.uset;
306 
307         if (other.x == emptyX) {
308             x = emptyX;
309         } else {
310             // ASSERT(otherX.length > 0);
311             long otherX[] = other.x;
312             int selfLength = x.length;
313             int limit = (otherX.length < selfLength) ? otherX.length : selfLength;
314             for (int i = 0; i < limit; i++) {
315                 x[i] &= otherX[i];
316             }
317             // If self is longer than other, all remaining
318             // bits are implicitly 0.  In the result, then,
319             // the remaining DA and DU bits are cleared.
320             for (int i = limit; i < selfLength; i++) {
321                 x[i] = 0;
322             }
323         }
324         return this;
325     }
326 
327     /**
328      * Add in the definite assignment bits of another vset,
329      * but join the definite unassignment bits.  This unusual
330      * operation is used only for 'finally' blocks.  The
331      * original vset 'this' is destroyed by this operation.
332      * (Part of fix for 4068688.)
333      */
334 
335     public Vset addDAandJoinDU(Vset other) {
336 
337         // Return a dead-end if either vset is a dead end.
338         // If either vset is the canonical DEAD_END, the
339         // result is also the canonical DEAD_END.
340         if (this == DEAD_END) {
341             return this;
342         }
343         if (other == DEAD_END) {
344             return other;
345         }
346         if (x == fullX) {
347             return this;
348         }
349         if (other.x == fullX) {
350             return other.copy();
351         }
352 
353         // DA = DA union DA'
354         // DU = (DU intersection DU') - DA'
355 
356         vset = vset | other.vset;
357         uset = (uset & other.uset) & ~other.vset;
358 
359         int selfLength = x.length;
360         long otherX[] = other.x;
361         int otherLength = otherX.length;
362 
363         if (otherX != emptyX) {
364             // ASSERT(otherX.length > 0);
365             if (otherLength > selfLength) {
366                 growX(otherLength);
367             }
368             int i = 0;
369             while (i < otherLength) {
370                 x[i] |= otherX[i];
371                 i++;
372                 if (i == otherLength) 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     /**
390      * Construct a vset consisting of the DA bits of the first argument
391      * and the DU bits of the second argument.  This is a higly unusual
392      * operation, as it implies a case where the flowgraph for DA analysis
393      * differs from that for DU analysis.  It is only needed for analysing
394      * 'try' blocks.  The result is a dead-end iff the first argument is
395      * dead-end. (Part of fix for 4068688.)
396      */
397 
398     public static Vset firstDAandSecondDU(Vset sourceDA, Vset sourceDU) {
399 
400         // Note that reachability status is received via 'sourceDA' only!
401         // This is a consequence of the fact that reachability and DA
402         // analysis are performed on an identical flow graph, whereas the
403         // flowgraph for DU analysis differs in the case of a 'try' statement.
404         if (sourceDA.x == fullX) {
405             return sourceDA.copy();
406         }
407 
408         long sourceDAx[] = sourceDA.x;
409         int lenDA = sourceDAx.length;
410         long sourceDUx[] = sourceDU.x;
411         int lenDU = sourceDUx.length;
412         int limit = (lenDA > lenDU) ? lenDA : lenDU;
413         long x[] = emptyX;
414 
415         if (limit > 0) {
416             x = new long[limit];
417             for (int i = 0; i < lenDA; i += 2) {
418                 x[i] = sourceDAx[i];
419             }
420             for (int i = 1; i < lenDU; i += 2) {
421                 x[i] = sourceDUx[i];
422             }
423         }
424 
425         return new Vset(sourceDA.vset, sourceDU.uset, x);
426     }
427 
428     /**
429      * Remove variables from the vset that are no longer part of
430      * a context.  Zeroes are stored past varNumber.
431      * (Side-effecting.)<p>
432      * However, if this is a dead end, keep it so.
433      * That is, leave an infinite tail of bits set.
434      */
435     public Vset removeAdditionalVars(int varNumber) {
436         if (x == fullX) {
437             return this;
438         }
439         long bit = (1L << varNumber);
440         if (varNumber >= VBITS) {
441             int i = (varNumber / VBITS - 1) * 2;
442             if (i < x.length) {
443                 x[i] &= (bit - 1);
444                 if (++i < x.length) {
445                     x[i] &= (bit - 1); // do the "uset" extension also
446                 }
447                 while (++i < x.length) {
448                     x[i] = 0;
449                 }
450             }
451         } else {
452             if (x.length > 0) {
453                 x = emptyX;
454             }
455             vset &= (bit - 1);
456             uset &= (bit - 1);
457         }
458         return this;
459     }
460 
461     /**
462      * Return one larger than the highest bit set.
463      */
464     public int varLimit() {
465         long vset;
466         int result;
467     scan: {
468             for (int i = (x.length / 2) * 2; i >= 0; i -= 2) {
469                 if (i == x.length)  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 }