tools/tree/Vset.java

/*
 * Copyright (c) 1996, 2003, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package sun.tools.tree;

import sun.tools.java.*;

/**
 * WARNING: The contents of this source file are not part of any
 * supported API.  Code that depends on them does so at its own risk:
 * they are subject to change or removal without notice.
 */
public final
class Vset implements Constants {
    long vset;                  // DA bits for first 64 variables
    long uset;                  // DU bits for first 64 variables

    // The extension array is interleaved, consisting of alternating
    // blocks of 64 DA bits followed by 64 DU bits followed by 64 DA
    // bits, and so on.

    long x[];                   // extension array for more bits

    // An infinite vector of zeroes or an infinite vector of ones is
    // represented by a special value of the extension array.
    //
    // IMPORTANT: The condition 'this.x == fullX' is used as a marker for
    // unreachable code, i.e., for a dead-end.  We maintain the invariant
    // that (this.x != fullX || (this.vset == -1 && this.uset == -1)).
    // A dead-end has the peculiar property that all variables are both
    // definitely assigned and definitely unassigned.  We always force this
    // condition to hold, even when the normal bitvector operations performed
    // during DA/DU analysis would produce a different result.  This supresses
    // reporting of DA/DU errors in unreachable code.

    static final long emptyX[] = new long[0]; // all zeroes
    static final long fullX[]  = new long[0]; // all ones

    // For more thorough testing of long vset support, it is helpful to
    // temporarily redefine this value to a smaller number, such as 1 or 2.

    static final int VBITS = 64; // number of bits in vset (uset)

    /**
     * This is the Vset which reports all vars assigned and unassigned.
     * This impossibility is degenerately true exactly when
     * control flow cannot reach this point.
     */

    // We distinguish a canonical dead-end value generated initially for
    // statements that do not complete normally, making the next one unreachable.
    // Once an unreachable statement is reported, a non-canonical dead-end value
    // is used for subsequent statements in order to suppress redundant error
    // messages.

    static final Vset DEAD_END = new Vset(-1, -1, fullX);

    /**
     * Create an empty Vset.
     */
    public Vset() {
        this.x = emptyX;
    }

    private Vset(long vset, long uset, long x[]) {
        this.vset = vset;
        this.uset = uset;
        this.x = x;
    }

    /**
     * Create an copy of the given Vset.
     * (However, DEAD_END simply returns itself.)
     */
    public Vset copy() {
        if (this == DEAD_END) {
            return this;
        }
        Vset vs = new Vset(vset, uset, x);
        if (x.length > 0) {
            vs.growX(x.length); // recopy the extension vector
        }
        return vs;
    }

    private void growX(int length) {
        long newX[] = new long[length];
        long oldX[] = x;
        for (int i = 0; i < oldX.length; i++) {
            newX[i] = oldX[i];
        }
        x = newX;
    }

    /**
     * Ask if this is a vset for a dead end.
     * Answer true only for the canonical dead-end, DEAD_END.
     * A canonical dead-end is produced only as a result of
     * a statement that cannot complete normally, as specified
     * by the JLS.  Due to the special-case rules for if-then
     * and if-then-else, this may fail to detect actual unreachable
     * code that could easily be identified.
     */

    public boolean isDeadEnd() {
        return (this == DEAD_END);
    }

    /**
     * Ask if this is a vset for a dead end.
     * Answer true for any dead-end.
     * Since 'clearDeadEnd' has no effect on this predicate,
     * if-then and if-then-else are handled in the more 'obvious'
     * and precise way.  This predicate is to be preferred for
     * dead code elimination purposes.
     * (Presently used in workaround for bug 4173473 in MethodExpression.java)
     */
    public boolean isReallyDeadEnd() {
        return (x == fullX);
    }

    /**
     * Replace canonical DEAD_END with a distinct but
     * equivalent Vset.  The bits are unaltered, but
     * the result does not answer true to 'isDeadEnd'.
     * <p>
     * Used mostly for error recovery, but see
     * 'IfStatement.check', where it is used to
     * implement the special-case treatment of
     * statement reachability for such statements.
     */
    public Vset clearDeadEnd() {
        if (this == DEAD_END) {
            return new Vset(-1, -1, fullX);
        }
        return this;
    }

    /**
     * Ask if a var is definitely assigned.
     */
    public boolean testVar(int varNumber) {
        long bit = (1L << varNumber);
        if (varNumber >= VBITS) {
            int i = (varNumber / VBITS - 1) * 2;
            if (i >= x.length) {
                return (x == fullX);
            }
            return (x[i] & bit) != 0;
        } else {
            return (vset & bit) != 0;
        }
    }

    /**
     * Ask if a var is definitely un-assigned.
     * (This is not just the negation of testVar:
     * It's possible for neither to be true.)
     */
    public boolean testVarUnassigned(int varNumber) {
        long bit = (1L << varNumber);
        if (varNumber >= VBITS) {
            // index "uset" extension
            int i = ((varNumber / VBITS - 1) * 2) + 1;
            if (i >= x.length) {
                return (x == fullX);
            }
            return (x[i] & bit) != 0;
        } else {
            return (uset & bit) != 0;
        }
    }

    /**
     * Note that a var is definitely assigned.
     * (Side-effecting.)
     */
    public Vset addVar(int varNumber) {
        if (x == fullX) {
            return this;
        }

        // gen DA, kill DU

        long bit = (1L << varNumber);
        if (varNumber >= VBITS) {
            int i = (varNumber / VBITS - 1) * 2;
            if (i >= x.length) {
                growX(i+1);
            }
            x[i] |= bit;
            if (i+1 < x.length) {
                x[i+1] &=~ bit;
            }
        } else {
            vset |= bit;
            uset &=~ bit;
        }
        return this;
    }

    /**
     * Note that a var is definitely un-assigned.
     * (Side-effecting.)
     */
    public Vset addVarUnassigned(int varNumber) {
        if (x == fullX) {
            return this;
        }

        // gen DU, kill DA

        long bit = (1L << varNumber);
        if (varNumber >= VBITS) {
            // index "uset" extension
            int i = ((varNumber / VBITS - 1) * 2) + 1;
            if (i >= x.length) {
                growX(i+1);
            }
            x[i] |= bit;
            x[i-1] &=~ bit;
        } else {
            uset |= bit;
            vset &=~ bit;
        }
        return this;
    }

    /**
     * Retract any assertion about the var.
     * This operation is ineffective on a dead-end.
     * (Side-effecting.)
     */
    public Vset clearVar(int varNumber) {
        if (x == fullX) {
            return this;
        }
        long bit = (1L << varNumber);
        if (varNumber >= VBITS) {
            int i = (varNumber / VBITS - 1) * 2;
            if (i >= x.length) {
                return this;
            }
            x[i] &=~ bit;
            if (i+1 < x.length) {
                x[i+1] &=~ bit;
            }
        } else {
            vset &=~ bit;
            uset &=~ bit;
        }
        return this;
    }

    /**
     * Join with another vset.  This is set intersection.
     * (Side-effecting.)
     */
    public Vset join(Vset other) {

        // Return a dead-end if both vsets are dead-ends.
        // Return the canonical DEAD_END only if both vsets
        // are the canonical DEAD_END.  Otherwise, an incoming
        // dead-end vset has already produced an error message,
        // and is now assumed to be reachable.
        if (this == DEAD_END) {
            return other.copy();
        }
        if (other == DEAD_END) {
            return this;
        }
        if (x == fullX) {
            return other.copy();
        }
        if (other.x == fullX) {
            return this;
        }

        // DA = DA intersection DA
        // DU = DU intersection DU

        vset &= other.vset;
        uset &= other.uset;

        if (other.x == emptyX) {
            x = emptyX;
        } else {
            // ASSERT(otherX.length > 0);
            long otherX[] = other.x;
            int selfLength = x.length;
            int limit = (otherX.length < selfLength) ? otherX.length : selfLength;
            for (int i = 0; i < limit; i++) {
                x[i] &= otherX[i];
            }
            // If self is longer than other, all remaining
            // bits are implicitly 0.  In the result, then,
            // the remaining DA and DU bits are cleared.
            for (int i = limit; i < selfLength; i++) {
                x[i] = 0;
            }
        }
        return this;
    }

    /**
     * Add in the definite assignment bits of another vset,
     * but join the definite unassignment bits.  This unusual
     * operation is used only for 'finally' blocks.  The
     * original vset 'this' is destroyed by this operation.
     * (Part of fix for 4068688.)
     */

    public Vset addDAandJoinDU(Vset other) {

        // Return a dead-end if either vset is a dead end.
        // If either vset is the canonical DEAD_END, the
        // result is also the canonical DEAD_END.
        if (this == DEAD_END) {
            return this;
        }
        if (other == DEAD_END) {
            return other;
        }
        if (x == fullX) {
            return this;
        }
        if (other.x == fullX) {
            return other.copy();
        }

        // DA = DA union DA'
        // DU = (DU intersection DU') - DA'

        vset = vset | other.vset;
        uset = (uset & other.uset) & ~other.vset;

        int selfLength = x.length;
        long otherX[] = other.x;
        int otherLength = otherX.length;

        if (otherX != emptyX) {
            // ASSERT(otherX.length > 0);
            if (otherLength > selfLength) {
                growX(otherLength);
            }
            int i = 0;
            while (i < otherLength) {
                x[i] |= otherX[i];
                i++;
                if (i == otherLength) break;
                x[i] = ((x[i] & otherX[i]) & ~otherX[i-1]);
                i++;
            }
        }
        // If self is longer than other, all remaining
        // bits are implicitly 0. In the result, then,
        // the remaining DA bits are left unchanged, and
        // the DU bits are all cleared. First, align
        // index to the next block of DU bits (odd index).
        for (int i = (otherLength | 1); i < selfLength; i += 2) {
            x[i] = 0;
        }
        return this;
    }


    /**
     * Construct a vset consisting of the DA bits of the first argument
     * and the DU bits of the second argument.  This is a higly unusual
     * operation, as it implies a case where the flowgraph for DA analysis
     * differs from that for DU analysis.  It is only needed for analysing
     * 'try' blocks.  The result is a dead-end iff the first argument is
     * dead-end. (Part of fix for 4068688.)
     */

    public static Vset firstDAandSecondDU(Vset sourceDA, Vset sourceDU) {

        // Note that reachability status is received via 'sourceDA' only!
        // This is a consequence of the fact that reachability and DA
        // analysis are performed on an identical flow graph, whereas the
        // flowgraph for DU analysis differs in the case of a 'try' statement.
        if (sourceDA.x == fullX) {
            return sourceDA.copy();
        }

        long sourceDAx[] = sourceDA.x;
        int lenDA = sourceDAx.length;
        long sourceDUx[] = sourceDU.x;
        int lenDU = sourceDUx.length;
        int limit = (lenDA > lenDU) ? lenDA : lenDU;
        long x[] = emptyX;

        if (limit > 0) {
            x = new long[limit];
            for (int i = 0; i < lenDA; i += 2) {
                x[i] = sourceDAx[i];
            }
            for (int i = 1; i < lenDU; i += 2) {
                x[i] = sourceDUx[i];
            }
        }

        return new Vset(sourceDA.vset, sourceDU.uset, x);
    }

    /**
     * Remove variables from the vset that are no longer part of
     * a context.  Zeroes are stored past varNumber.
     * (Side-effecting.)<p>
     * However, if this is a dead end, keep it so.
     * That is, leave an infinite tail of bits set.
     */
    public Vset removeAdditionalVars(int varNumber) {
        if (x == fullX) {
            return this;
        }
        long bit = (1L << varNumber);
        if (varNumber >= VBITS) {
            int i = (varNumber / VBITS - 1) * 2;
            if (i < x.length) {
                x[i] &= (bit - 1);
                if (++i < x.length) {
                    x[i] &= (bit - 1); // do the "uset" extension also
                }
                while (++i < x.length) {
                    x[i] = 0;
                }
            }
        } else {
            if (x.length > 0) {
                x = emptyX;
            }
            vset &= (bit - 1);
            uset &= (bit - 1);
        }
        return this;
    }

    /**
     * Return one larger than the highest bit set.
     */
    public int varLimit() {
        long vset;
        int result;
    scan: {
            for (int i = (x.length / 2) * 2; i >= 0; i -= 2) {
                if (i == x.length)  continue; // oops
                vset = x[i];
                if (i+1 < x.length) {
                    vset |= x[i+1]; // check the "uset" also
                }
                if (vset != 0) {
                    result = (i/2 + 1) * VBITS;
                    break scan;
                }
            }
            vset = this.vset;
            vset |= this.uset;  // check the "uset" also
            if (vset != 0) {
                result = 0;
                break scan;
            } else {
                return 0;
            }
        }
        while (vset != 0) {
            result += 1;
            vset >>>= 1;
        }
        return result;
    }

    public String toString() {
        if (this == DEAD_END)
            return "{DEAD_END}";
        StringBuilder sb = new StringBuilder("{");
        int maxVar = VBITS * (1 + (x.length+1)/2);
        for (int i = 0; i < maxVar; i++) {
            if (!testVarUnassigned(i)) {
                if (sb.length() > 1) {
                    sb.append(' ');
                }
                sb.append(i);
                if (!testVar(i)) {
                    sb.append('?'); // not definitely unassigned
                }
            }
        }
        if (x == fullX) {
            sb.append("...DEAD_END");
        }
        sb.append('}');
        return sb.toString();
    }

}