/* * The contents of this file are subject to the Netscape Public * License Version 1.1 (the "License"); you may not use this file * except in compliance with the License. You may obtain a copy of * the License at http://www.mozilla.org/NPL/ * * Software distributed under the License is distributed on an "AS * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or * implied. See the License for the specific language governing * rights and limitations under the License. * * The Original Code is Rhino code, released * May 6, 1999. * * The Initial Developer of the Original Code is Netscape * Communications Corporation.  Portions created by Netscape are * Copyright (C) 1997-1999 Netscape Communications Corporation. All * Rights Reserved. * * Contributor(s): * Norris Boyd * Igor Bukanov * Roger Lawrence * * Alternatively, the contents of this file may be used under the * terms of the GNU Public License (the "GPL"), in which case the * provisions of the GPL are applicable instead of those above. * If you wish to allow use of your version of this file only * under the terms of the GPL and not to allow others to use your * version of this file under the NPL, indicate your decision by * deleting the provisions above and replace them with the notice * and other provisions required by the GPL.  If you do not delete * the provisions above, a recipient may use your version of this * file under either the NPL or the GPL. */package org.mozilla.javascript.optimizer;import org.mozilla.javascript.*;import java.util.Hashtable;import java.io.PrintWriter;import java.io.StringWriter;class Block{    private static class FatBlock    {        private static Block[] reduceToArray(ObjToIntMap map)        {            Block[] result = null;            if (!map.isEmpty()) {                result = new Block[map.size()];                int i = 0;                ObjToIntMap.Iterator iter = map.newIterator();                for (iter.start(); !iter.done(); iter.next()) {                    FatBlock fb = (FatBlock)(iter.getKey());                    result[i++] = fb.realBlock;                }            }            return result;        }        void addSuccessor(FatBlock b)  { successors.put(b, 0); }        void addPredecessor(FatBlock b)  { predecessors.put(b, 0); }        Block[] getSuccessors() { return reduceToArray(successors); }        Block[] getPredecessors() { return reduceToArray(predecessors); }            // all the Blocks that come immediately after this        private ObjToIntMap successors = new ObjToIntMap();            // all the Blocks that come immediately before this        private ObjToIntMap predecessors = new ObjToIntMap();        Block realBlock;    }    Block(int startNodeIndex, int endNodeIndex)    {        itsStartNodeIndex = startNodeIndex;        itsEndNodeIndex = endNodeIndex;    }    static void runFlowAnalyzes(OptFunctionNode fn, Node[] statementNodes)    {        int paramCount = fn.fnode.getParamCount();        int varCount = fn.fnode.getParamAndVarCount();        int[] varTypes = new int[varCount];        // If the variable is a parameter, it could have any type.        for (int i = 0; i != paramCount; ++i) {            varTypes[i] = Optimizer.AnyType;        }        // If the variable is from a "var" statement, its typeEvent will be set        // when we see the setVar node.        for (int i = paramCount; i != varCount; ++i) {            varTypes[i] = Optimizer.NoType;        }        Block[] theBlocks = buildBlocks(statementNodes);        if (DEBUG) {            ++debug_blockCount;            System.out.println("-------------------"+fn.fnode.getFunctionName()+"  "+debug_blockCount+"--------");            System.out.println(toString(theBlocks, statementNodes));        }        reachingDefDataFlow(fn, statementNodes, theBlocks, varTypes);        typeFlow(fn, statementNodes, theBlocks, varTypes);        if (DEBUG) {            for (int i = 0; i < theBlocks.length; i++) {                System.out.println("For block " + theBlocks[i].itsBlockID);                theBlocks[i].printLiveOnEntrySet(fn);            }            System.out.println("Variable Table, size = " + varCount);            for (int i = 0; i != varCount; i++) {                System.out.println("["+i+"] type: "+varTypes[i]);            }        }        for (int i = paramCount; i != varCount; i++) {            if (varTypes[i] == Optimizer.NumberType) {                fn.setIsNumberVar(i);            }        }    }    private static Block[] buildBlocks(Node[] statementNodes)    {            // a mapping from each target node to the block it begins        Hashtable theTargetBlocks = new Hashtable();        ObjArray theBlocks = new ObjArray();            // there's a block that starts at index 0        int beginNodeIndex = 0;        for (int i = 0; i < statementNodes.length; i++) {            switch (statementNodes[i].getType()) {                case Token.TARGET :                    {                        if (i != beginNodeIndex) {                            FatBlock fb = newFatBlock(beginNodeIndex, i - 1);                            if (statementNodes[beginNodeIndex].getType()                                                        == Token.TARGET)                                theTargetBlocks.put(statementNodes[beginNodeIndex], fb);                            theBlocks.add(fb);                             // start the next block at this node                            beginNodeIndex = i;                        }                    }                    break;                case Token.IFNE :                case Token.IFEQ :                case Token.GOTO :                    {                        FatBlock fb = newFatBlock(beginNodeIndex, i);                        if (statementNodes[beginNodeIndex].getType()                                                       == Token.TARGET)                            theTargetBlocks.put(statementNodes[beginNodeIndex], fb);                        theBlocks.add(fb);                            // start the next block at the next node                        beginNodeIndex = i + 1;                    }                    break;            }        }        if (beginNodeIndex != statementNodes.length) {            FatBlock fb = newFatBlock(beginNodeIndex, statementNodes.length - 1);            if (statementNodes[beginNodeIndex].getType() == Token.TARGET)                theTargetBlocks.put(statementNodes[beginNodeIndex], fb);            theBlocks.add(fb);        }        // build successor and predecessor links        for (int i = 0; i < theBlocks.size(); i++) {            FatBlock fb = (FatBlock)(theBlocks.get(i));            Node blockEndNode = statementNodes[fb.realBlock.itsEndNodeIndex];            int blockEndNodeType = blockEndNode.getType();            if ((blockEndNodeType != Token.GOTO)                                         && (i < (theBlocks.size() - 1))) {                FatBlock fallThruTarget = (FatBlock)(theBlocks.get(i + 1));                fb.addSuccessor(fallThruTarget);                fallThruTarget.addPredecessor(fb);            }            if ( (blockEndNodeType == Token.IFNE)                        || (blockEndNodeType == Token.IFEQ)                                || (blockEndNodeType == Token.GOTO) ) {                Node target = ((Node.Jump)blockEndNode).target;                FatBlock branchTargetBlock                                    = (FatBlock)(theTargetBlocks.get(target));                target.putProp(Node.TARGETBLOCK_PROP,                                           branchTargetBlock.realBlock);                fb.addSuccessor(branchTargetBlock);                branchTargetBlock.addPredecessor(fb);            }        }        Block[] result = new Block[theBlocks.size()];        for (int i = 0; i < theBlocks.size(); i++) {            FatBlock fb = (FatBlock)(theBlocks.get(i));            Block b = fb.realBlock;            b.itsSuccessors = fb.getSuccessors();            b.itsPredecessors = fb.getPredecessors();            b.itsBlockID = i;            result[i] = b;        }        return result;    }    private static FatBlock newFatBlock(int startNodeIndex, int endNodeIndex)    {        FatBlock fb = new FatBlock();        fb.realBlock = new Block(startNodeIndex, endNodeIndex);        return fb;    }    private static String toString(Block[] blockList, Node[] statementNodes)    {        if (!DEBUG) return null;        StringWriter sw = new StringWriter();        PrintWriter pw = new PrintWriter(sw);        pw.println(blockList.length + " Blocks");        for (int i = 0; i < blockList.length; i++) {            Block b = blockList[i];            pw.println("#" + b.itsBlockID);            pw.println("from " + b.itsStartNodeIndex                            + " "                            + statementNodes[b.itsStartNodeIndex].toString());            pw.println("thru " + b.itsEndNodeIndex                            + " "                            + statementNodes[b.itsEndNodeIndex].toString());            pw.print("Predecessors ");            if (b.itsPredecessors != null) {                for (int j = 0; j < b.itsPredecessors.length; j++)                    pw.print(b.itsPredecessors[j].itsBlockID + " ");                pw.println();            }            else                pw.println("none");            pw.print("Successors ");            if (b.itsSuccessors != null) {                for (int j = 0; j < b.itsSuccessors.length; j++)                    pw.print(b.itsSuccessors[j].itsBlockID + " ");                pw.println();            }            else                pw.println("none");        }        return sw.toString();    }    private static void reachingDefDataFlow(OptFunctionNode fn, Node[] statementNodes, Block theBlocks[], int[] varTypes)    {/*    initialize the liveOnEntry and liveOnExit sets, then discover the variables    that are def'd by each function, and those that are used before being def'd    (hence liveOnEntry)*/        for (int i = 0; i < theBlocks.length; i++) {            theBlocks[i].initLiveOnEntrySets(fn, statementNodes);        }/*    this visits every block starting at the last, re-adding the predecessors of    any block whose inputs change as a result of the dataflow.    REMIND, better would be to visit in CFG postorder*/        boolean visit[] = new boolean[theBlocks.length];        boolean doneOnce[] = new boolean[theBlocks.length];        int vIndex = theBlocks.length - 1;        boolean needRescan = false;        visit[vIndex] = true;        while (true) {            if (visit[vIndex] || !doneOnce[vIndex]) {                doneOnce[vIndex] = true;                visit[vIndex] = false;                if (theBlocks[vIndex].doReachedUseDataFlow()) {                    Block pred[] = theBlocks[vIndex].itsPredecessors;                    if (pred != null) {                        for (int i = 0; i < pred.length; i++) {                            int index = pred[i].itsBlockID;                            visit[index] = true;                            needRescan |= (index > vIndex);                        }                    }                }            }            if (vIndex == 0) {                if (needRescan) {                    vIndex = theBlocks.length - 1;                    needRescan = false;                }                else                    break;