block.java

java中比较著名的js引擎当属mozilla开源的rhino

                    break;
            }
            else
                vIndex--;
        }
/*
        if any variable is live on entry to block 0, we have to mark it as
        not jRegable - since it means that someone is trying to access the
        'undefined'-ness of that variable.
*/

        theBlocks[0].markAnyTypeVariables(varTypes);
    }

    private static void typeFlow(OptFunctionNode fn, Node[] statementNodes, Block theBlocks[], int[] varTypes)
    {
        boolean visit[] = new boolean[theBlocks.length];
        boolean doneOnce[] = new boolean[theBlocks.length];
        int vIndex = 0;
        boolean needRescan = false;
        visit[vIndex] = true;
        while (true) {
            if (visit[vIndex] || !doneOnce[vIndex]) {
                doneOnce[vIndex] = true;
                visit[vIndex] = false;
                if (theBlocks[vIndex].doTypeFlow(fn, statementNodes, varTypes))
                {
                    Block succ[] = theBlocks[vIndex].itsSuccessors;
                    if (succ != null) {
                        for (int i = 0; i < succ.length; i++) {
                            int index = succ[i].itsBlockID;
                            visit[index] = true;
                            needRescan |= (index < vIndex);
                        }
                    }
                }
            }
            if (vIndex == (theBlocks.length - 1)) {
                if (needRescan) {
                    vIndex = 0;
                    needRescan = false;
                }
                else
                    break;
            }
            else
                vIndex++;
        }
    }

    private static boolean assignType(int[] varTypes, int index, int type)
    {
        return type != (varTypes[index] |= type);
    }

    private void markAnyTypeVariables(int[] varTypes)
    {
        for (int i = 0; i != varTypes.length; i++) {
            if (itsLiveOnEntrySet.test(i)) {
                assignType(varTypes, i, Optimizer.AnyType);
            }
        }

    }

    /*
        We're tracking uses and defs - in order to
        build the def set and to identify the last use
        nodes.

        The itsNotDefSet is built reversed then flipped later.

    */
    private void lookForVariableAccess(OptFunctionNode fn, Node n)
    {
        switch (n.getType()) {
            case Token.DEC :
            case Token.INC :
                {
                    Node child = n.getFirstChild();
                    if (child.getType() == Token.GETVAR) {
                        int varIndex = fn.getVarIndex(child);
                        if (!itsNotDefSet.test(varIndex))
                            itsUseBeforeDefSet.set(varIndex);
                        itsNotDefSet.set(varIndex);
                    }
                }
                break;
            case Token.SETVAR :
                {
                    Node lhs = n.getFirstChild();
                    Node rhs = lhs.getNext();
                    lookForVariableAccess(fn, rhs);
                    itsNotDefSet.set(fn.getVarIndex(n));
                }
                break;
            case Token.GETVAR :
                {
                    int varIndex = fn.getVarIndex(n);
                    if (!itsNotDefSet.test(varIndex))
                        itsUseBeforeDefSet.set(varIndex);
                }
                break;
            default :
                Node child = n.getFirstChild();
                while (child != null) {
                    lookForVariableAccess(fn, child);
                    child = child.getNext();
                }
                break;
        }
    }

    /*
        build the live on entry/exit sets.
        Then walk the trees looking for defs/uses of variables
        and build the def and useBeforeDef sets.
    */
    private void initLiveOnEntrySets(OptFunctionNode fn, Node[] statementNodes)
    {
        int listLength = fn.getVarCount();
        itsUseBeforeDefSet = new DataFlowBitSet(listLength);
        itsNotDefSet = new DataFlowBitSet(listLength);
        itsLiveOnEntrySet = new DataFlowBitSet(listLength);
        itsLiveOnExitSet = new DataFlowBitSet(listLength);
        for (int i = itsStartNodeIndex; i <= itsEndNodeIndex; i++) {
            Node n = statementNodes[i];
            lookForVariableAccess(fn, n);
        }
        itsNotDefSet.not();         // truth in advertising
    }

    /*
        the liveOnEntry of each successor is the liveOnExit for this block.
        The liveOnEntry for this block is -
        liveOnEntry = liveOnExit - defsInThisBlock + useBeforeDefsInThisBlock

    */
    private boolean doReachedUseDataFlow()
    {
        itsLiveOnExitSet.clear();
        if (itsSuccessors != null)
            for (int i = 0; i < itsSuccessors.length; i++)
                itsLiveOnExitSet.or(itsSuccessors[i].itsLiveOnEntrySet);
        return itsLiveOnEntrySet.df2(itsLiveOnExitSet,
                                            itsUseBeforeDefSet, itsNotDefSet);
    }

    /*
        the type of an expression is relatively unknown. Cases we can be sure
        about are -
            Literals,
            Arithmetic operations - always return a Number
    */
    private static int findExpressionType(OptFunctionNode fn, Node n,
                                          int[] varTypes)
    {
        switch (n.getType()) {
          case Token.NUMBER :
              return Optimizer.NumberType;

          case Token.CALL :
          case Token.NEW :
          case Token.REF_CALL :
              return Optimizer.AnyType;

          case Token.GETELEM :
             return Optimizer.AnyType;

          case Token.GETVAR :
              return varTypes[fn.getVarIndex(n)];

          case Token.INC :
          case Token.DEC :
          case Token.DIV:
          case Token.MOD:
          case Token.BITOR:
          case Token.BITXOR:
          case Token.BITAND:
          case Token.LSH:
          case Token.RSH:
          case Token.URSH:
          case Token.SUB :
              return Optimizer.NumberType;

          case Token.ADD : {
              // if the lhs & rhs are known to be numbers, we can be sure that's
              // the result, otherwise it could be a string.
              Node child = n.getFirstChild();
              int lType = findExpressionType(fn, child, varTypes);
              int rType = findExpressionType(fn, child.getNext(), varTypes);
              return lType | rType;    // we're not distinguishng strings yet
          }
        }

        Node child = n.getFirstChild();
        if (child == null) {
            return Optimizer.AnyType;
        } else {
            int result = Optimizer.NoType;
            while (child != null) {
                result |= findExpressionType(fn, child, varTypes);
                child = child.getNext();
            }
            return result;
        }
    }

    private static boolean findDefPoints(OptFunctionNode fn, Node n,
                                         int[] varTypes)
    {
        boolean result = false;
        Node child = n.getFirstChild();
        switch (n.getType()) {
          default :
            while (child != null) {
                result |= findDefPoints(fn, child, varTypes);
                child = child.getNext();
            }
            break;
          case Token.DEC :
          case Token.INC :
            if (child.getType() == Token.GETVAR) {
                // theVar is a Number now
                int i = fn.getVarIndex(child);
                result |= assignType(varTypes, i, Optimizer.NumberType);
            }
            break;
          case Token.SETPROP :
          case Token.SETPROP_OP :
            if (child.getType() == Token.GETVAR) {
                int i = fn.getVarIndex(child);
                assignType(varTypes, i, Optimizer.AnyType);
            }
            while (child != null) {
                result |= findDefPoints(fn, child, varTypes);
                child = child.getNext();
            }
            break;
          case Token.SETVAR : {
            Node rValue = child.getNext();
            int theType = findExpressionType(fn, rValue, varTypes);
            int i = fn.getVarIndex(n);
            result |= assignType(varTypes, i, theType);
            break;
          }
        }
        return result;
    }

    private boolean doTypeFlow(OptFunctionNode fn, Node[] statementNodes,
                               int[] varTypes)
    {
        boolean changed = false;

        for (int i = itsStartNodeIndex; i <= itsEndNodeIndex; i++) {
            Node n = statementNodes[i];
            if (n != null)
                changed |= findDefPoints(fn, n, varTypes);
        }

        return changed;
    }

    private boolean isLiveOnEntry(int index)
    {
        return (itsLiveOnEntrySet != null) && (itsLiveOnEntrySet.test(index));
    }

    private void printLiveOnEntrySet(OptFunctionNode fn)
    {
        if (DEBUG) {
            for (int i = 0; i < fn.getVarCount(); i++) {
                String name = fn.fnode.getParamOrVarName(i);
                if (itsUseBeforeDefSet.test(i))
                    System.out.println(name + " is used before def'd");
                if (itsNotDefSet.test(i))
                    System.out.println(name + " is not def'd");
                if (itsLiveOnEntrySet.test(i))
                    System.out.println(name + " is live on entry");
                if (itsLiveOnExitSet.test(i))
                    System.out.println(name + " is live on exit");
            }
        }
    }

        // all the Blocks that come immediately after this
    private Block[] itsSuccessors;
        // all the Blocks that come immediately before this
    private Block[] itsPredecessors;

    private int itsStartNodeIndex;       // the Node at the start of the block
    private int itsEndNodeIndex;         // the Node at the end of the block

    private int itsBlockID;               // a unique index for each block

// reaching def bit sets -
    private DataFlowBitSet itsLiveOnEntrySet;
    private DataFlowBitSet itsLiveOnExitSet;
    private DataFlowBitSet itsUseBeforeDefSet;
    private DataFlowBitSet itsNotDefSet;

    static final boolean DEBUG = false;
    private static int debug_blockCount;

}