aboutsummaryrefslogtreecommitdiffstats
path: root/infrastructure/rhino1_7R1/src/org/mozilla/javascript/optimizer/Block.java
diff options
context:
space:
mode:
Diffstat (limited to 'infrastructure/rhino1_7R1/src/org/mozilla/javascript/optimizer/Block.java')
-rw-r--r--infrastructure/rhino1_7R1/src/org/mozilla/javascript/optimizer/Block.java615
1 files changed, 615 insertions, 0 deletions
diff --git a/infrastructure/rhino1_7R1/src/org/mozilla/javascript/optimizer/Block.java b/infrastructure/rhino1_7R1/src/org/mozilla/javascript/optimizer/Block.java
new file mode 100644
index 0000000..bd56714
--- /dev/null
+++ b/infrastructure/rhino1_7R1/src/org/mozilla/javascript/optimizer/Block.java
@@ -0,0 +1,615 @@
+/* ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0
+ *
+ * The contents of this file are subject to the Mozilla 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/MPL/
+ *
+ * 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 the Initial Developer are Copyright (C) 1997-1999
+ * the Initial Developer. 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 General Public License Version 2 or later (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
+ * MPL, indicate your decision by deleting the provisions above and replacing
+ * 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 MPL or the GPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+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;
+ }
+ 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.ARRAYLIT:
+ case Token.OBJECTLIT:
+ return Optimizer.AnyType; // XXX: actually, we know it's not
+ // number, but no type yet for that
+
+ 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 distinguishing 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 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;
+
+}
+