001: /* ***** BEGIN LICENSE BLOCK *****
002: * Version: MPL 1.1/GPL 2.0
003: *
004: * The contents of this file are subject to the Mozilla Public License Version
005: * 1.1 (the "License"); you may not use this file except in compliance with
006: * the License. You may obtain a copy of the License at
007: * http://www.mozilla.org/MPL/
008: *
009: * Software distributed under the License is distributed on an "AS IS" basis,
010: * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
011: * for the specific language governing rights and limitations under the
012: * License.
013: *
014: * The Original Code is Rhino code, released
015: * May 6, 1999.
016: *
017: * The Initial Developer of the Original Code is
018: * Netscape Communications Corporation.
019: * Portions created by the Initial Developer are Copyright (C) 1997-1999
020: * the Initial Developer. All Rights Reserved.
021: *
022: * Contributor(s):
023: * Norris Boyd
024: * Igor Bukanov
025: * Roger Lawrence
026: *
027: * Alternatively, the contents of this file may be used under the terms of
028: * the GNU General Public License Version 2 or later (the "GPL"), in which
029: * case the provisions of the GPL are applicable instead of those above. If
030: * you wish to allow use of your version of this file only under the terms of
031: * the GPL and not to allow others to use your version of this file under the
032: * MPL, indicate your decision by deleting the provisions above and replacing
033: * them with the notice and other provisions required by the GPL. If you do
034: * not delete the provisions above, a recipient may use your version of this
035: * file under either the MPL or the GPL.
036: *
037: * ***** END LICENSE BLOCK ***** */
038:
039: package org.mozilla.javascript.optimizer;
040:
041: import org.mozilla.javascript.*;
042:
043: import java.util.Hashtable;
044:
045: import java.io.PrintWriter;
046: import java.io.StringWriter;
047:
048: class Block {
049:
050: private static class FatBlock {
051:
052: private static Block[] reduceToArray(ObjToIntMap map) {
053: Block[] result = null;
054: if (!map.isEmpty()) {
055: result = new Block[map.size()];
056: int i = 0;
057: ObjToIntMap.Iterator iter = map.newIterator();
058: for (iter.start(); !iter.done(); iter.next()) {
059: FatBlock fb = (FatBlock) (iter.getKey());
060: result[i++] = fb.realBlock;
061: }
062: }
063: return result;
064: }
065:
066: void addSuccessor(FatBlock b) {
067: successors.put(b, 0);
068: }
069:
070: void addPredecessor(FatBlock b) {
071: predecessors.put(b, 0);
072: }
073:
074: Block[] getSuccessors() {
075: return reduceToArray(successors);
076: }
077:
078: Block[] getPredecessors() {
079: return reduceToArray(predecessors);
080: }
081:
082: // all the Blocks that come immediately after this
083: private ObjToIntMap successors = new ObjToIntMap();
084: // all the Blocks that come immediately before this
085: private ObjToIntMap predecessors = new ObjToIntMap();
086:
087: Block realBlock;
088: }
089:
090: Block(int startNodeIndex, int endNodeIndex) {
091: itsStartNodeIndex = startNodeIndex;
092: itsEndNodeIndex = endNodeIndex;
093: }
094:
095: static void runFlowAnalyzes(OptFunctionNode fn,
096: Node[] statementNodes) {
097: int paramCount = fn.fnode.getParamCount();
098: int varCount = fn.fnode.getParamAndVarCount();
099: int[] varTypes = new int[varCount];
100: // If the variable is a parameter, it could have any type.
101: for (int i = 0; i != paramCount; ++i) {
102: varTypes[i] = Optimizer.AnyType;
103: }
104: // If the variable is from a "var" statement, its typeEvent will be set
105: // when we see the setVar node.
106: for (int i = paramCount; i != varCount; ++i) {
107: varTypes[i] = Optimizer.NoType;
108: }
109:
110: Block[] theBlocks = buildBlocks(statementNodes);
111:
112: if (DEBUG) {
113: ++debug_blockCount;
114: System.out.println("-------------------"
115: + fn.fnode.getFunctionName() + " "
116: + debug_blockCount + "--------");
117: System.out.println(toString(theBlocks, statementNodes));
118: }
119:
120: reachingDefDataFlow(fn, statementNodes, theBlocks, varTypes);
121: typeFlow(fn, statementNodes, theBlocks, varTypes);
122:
123: if (DEBUG) {
124: for (int i = 0; i < theBlocks.length; i++) {
125: System.out.println("For block "
126: + theBlocks[i].itsBlockID);
127: theBlocks[i].printLiveOnEntrySet(fn);
128: }
129: System.out.println("Variable Table, size = " + varCount);
130: for (int i = 0; i != varCount; i++) {
131: System.out.println("[" + i + "] type: " + varTypes[i]);
132: }
133: }
134:
135: for (int i = paramCount; i != varCount; i++) {
136: if (varTypes[i] == Optimizer.NumberType) {
137: fn.setIsNumberVar(i);
138: }
139: }
140:
141: }
142:
143: private static Block[] buildBlocks(Node[] statementNodes) {
144: // a mapping from each target node to the block it begins
145: Hashtable theTargetBlocks = new Hashtable();
146: ObjArray theBlocks = new ObjArray();
147:
148: // there's a block that starts at index 0
149: int beginNodeIndex = 0;
150:
151: for (int i = 0; i < statementNodes.length; i++) {
152: switch (statementNodes[i].getType()) {
153: case Token.TARGET: {
154: if (i != beginNodeIndex) {
155: FatBlock fb = newFatBlock(beginNodeIndex, i - 1);
156: if (statementNodes[beginNodeIndex].getType() == Token.TARGET)
157: theTargetBlocks.put(
158: statementNodes[beginNodeIndex], fb);
159: theBlocks.add(fb);
160: // start the next block at this node
161: beginNodeIndex = i;
162: }
163: }
164: break;
165: case Token.IFNE:
166: case Token.IFEQ:
167: case Token.GOTO: {
168: FatBlock fb = newFatBlock(beginNodeIndex, i);
169: if (statementNodes[beginNodeIndex].getType() == Token.TARGET)
170: theTargetBlocks.put(statementNodes[beginNodeIndex],
171: fb);
172: theBlocks.add(fb);
173: // start the next block at the next node
174: beginNodeIndex = i + 1;
175: }
176: break;
177: }
178: }
179:
180: if (beginNodeIndex != statementNodes.length) {
181: FatBlock fb = newFatBlock(beginNodeIndex,
182: statementNodes.length - 1);
183: if (statementNodes[beginNodeIndex].getType() == Token.TARGET)
184: theTargetBlocks.put(statementNodes[beginNodeIndex], fb);
185: theBlocks.add(fb);
186: }
187:
188: // build successor and predecessor links
189:
190: for (int i = 0; i < theBlocks.size(); i++) {
191: FatBlock fb = (FatBlock) (theBlocks.get(i));
192:
193: Node blockEndNode = statementNodes[fb.realBlock.itsEndNodeIndex];
194: int blockEndNodeType = blockEndNode.getType();
195:
196: if ((blockEndNodeType != Token.GOTO)
197: && (i < (theBlocks.size() - 1))) {
198: FatBlock fallThruTarget = (FatBlock) (theBlocks
199: .get(i + 1));
200: fb.addSuccessor(fallThruTarget);
201: fallThruTarget.addPredecessor(fb);
202: }
203:
204: if ((blockEndNodeType == Token.IFNE)
205: || (blockEndNodeType == Token.IFEQ)
206: || (blockEndNodeType == Token.GOTO)) {
207: Node target = ((Node.Jump) blockEndNode).target;
208: FatBlock branchTargetBlock = (FatBlock) (theTargetBlocks
209: .get(target));
210: target.putProp(Node.TARGETBLOCK_PROP,
211: branchTargetBlock.realBlock);
212: fb.addSuccessor(branchTargetBlock);
213: branchTargetBlock.addPredecessor(fb);
214: }
215: }
216:
217: Block[] result = new Block[theBlocks.size()];
218:
219: for (int i = 0; i < theBlocks.size(); i++) {
220: FatBlock fb = (FatBlock) (theBlocks.get(i));
221: Block b = fb.realBlock;
222: b.itsSuccessors = fb.getSuccessors();
223: b.itsPredecessors = fb.getPredecessors();
224: b.itsBlockID = i;
225: result[i] = b;
226: }
227:
228: return result;
229: }
230:
231: private static FatBlock newFatBlock(int startNodeIndex,
232: int endNodeIndex) {
233: FatBlock fb = new FatBlock();
234: fb.realBlock = new Block(startNodeIndex, endNodeIndex);
235: return fb;
236: }
237:
238: private static String toString(Block[] blockList,
239: Node[] statementNodes) {
240: if (!DEBUG)
241: return null;
242:
243: StringWriter sw = new StringWriter();
244: PrintWriter pw = new PrintWriter(sw);
245:
246: pw.println(blockList.length + " Blocks");
247: for (int i = 0; i < blockList.length; i++) {
248: Block b = blockList[i];
249: pw.println("#" + b.itsBlockID);
250: pw.println("from " + b.itsStartNodeIndex + " "
251: + statementNodes[b.itsStartNodeIndex].toString());
252: pw.println("thru " + b.itsEndNodeIndex + " "
253: + statementNodes[b.itsEndNodeIndex].toString());
254: pw.print("Predecessors ");
255: if (b.itsPredecessors != null) {
256: for (int j = 0; j < b.itsPredecessors.length; j++)
257: pw.print(b.itsPredecessors[j].itsBlockID + " ");
258: pw.println();
259: } else
260: pw.println("none");
261: pw.print("Successors ");
262: if (b.itsSuccessors != null) {
263: for (int j = 0; j < b.itsSuccessors.length; j++)
264: pw.print(b.itsSuccessors[j].itsBlockID + " ");
265: pw.println();
266: } else
267: pw.println("none");
268: }
269: return sw.toString();
270: }
271:
272: private static void reachingDefDataFlow(OptFunctionNode fn,
273: Node[] statementNodes, Block theBlocks[], int[] varTypes) {
274: /*
275: initialize the liveOnEntry and liveOnExit sets, then discover the variables
276: that are def'd by each function, and those that are used before being def'd
277: (hence liveOnEntry)
278: */
279: for (int i = 0; i < theBlocks.length; i++) {
280: theBlocks[i].initLiveOnEntrySets(fn, statementNodes);
281: }
282: /*
283: this visits every block starting at the last, re-adding the predecessors of
284: any block whose inputs change as a result of the dataflow.
285: REMIND, better would be to visit in CFG postorder
286: */
287: boolean visit[] = new boolean[theBlocks.length];
288: boolean doneOnce[] = new boolean[theBlocks.length];
289: int vIndex = theBlocks.length - 1;
290: boolean needRescan = false;
291: visit[vIndex] = true;
292: while (true) {
293: if (visit[vIndex] || !doneOnce[vIndex]) {
294: doneOnce[vIndex] = true;
295: visit[vIndex] = false;
296: if (theBlocks[vIndex].doReachedUseDataFlow()) {
297: Block pred[] = theBlocks[vIndex].itsPredecessors;
298: if (pred != null) {
299: for (int i = 0; i < pred.length; i++) {
300: int index = pred[i].itsBlockID;
301: visit[index] = true;
302: needRescan |= (index > vIndex);
303: }
304: }
305: }
306: }
307: if (vIndex == 0) {
308: if (needRescan) {
309: vIndex = theBlocks.length - 1;
310: needRescan = false;
311: } else
312: break;
313: } else
314: vIndex--;
315: }
316: /*
317: if any variable is live on entry to block 0, we have to mark it as
318: not jRegable - since it means that someone is trying to access the
319: 'undefined'-ness of that variable.
320: */
321:
322: theBlocks[0].markAnyTypeVariables(varTypes);
323: }
324:
325: private static void typeFlow(OptFunctionNode fn,
326: Node[] statementNodes, Block theBlocks[], int[] varTypes) {
327: boolean visit[] = new boolean[theBlocks.length];
328: boolean doneOnce[] = new boolean[theBlocks.length];
329: int vIndex = 0;
330: boolean needRescan = false;
331: visit[vIndex] = true;
332: while (true) {
333: if (visit[vIndex] || !doneOnce[vIndex]) {
334: doneOnce[vIndex] = true;
335: visit[vIndex] = false;
336: if (theBlocks[vIndex].doTypeFlow(fn, statementNodes,
337: varTypes)) {
338: Block succ[] = theBlocks[vIndex].itsSuccessors;
339: if (succ != null) {
340: for (int i = 0; i < succ.length; i++) {
341: int index = succ[i].itsBlockID;
342: visit[index] = true;
343: needRescan |= (index < vIndex);
344: }
345: }
346: }
347: }
348: if (vIndex == (theBlocks.length - 1)) {
349: if (needRescan) {
350: vIndex = 0;
351: needRescan = false;
352: } else
353: break;
354: } else
355: vIndex++;
356: }
357: }
358:
359: private static boolean assignType(int[] varTypes, int index,
360: int type) {
361: return type != (varTypes[index] |= type);
362: }
363:
364: private void markAnyTypeVariables(int[] varTypes) {
365: for (int i = 0; i != varTypes.length; i++) {
366: if (itsLiveOnEntrySet.test(i)) {
367: assignType(varTypes, i, Optimizer.AnyType);
368: }
369: }
370:
371: }
372:
373: /*
374: We're tracking uses and defs - in order to
375: build the def set and to identify the last use
376: nodes.
377:
378: The itsNotDefSet is built reversed then flipped later.
379:
380: */
381: private void lookForVariableAccess(OptFunctionNode fn, Node n) {
382: switch (n.getType()) {
383: case Token.DEC:
384: case Token.INC: {
385: Node child = n.getFirstChild();
386: if (child.getType() == Token.GETVAR) {
387: int varIndex = fn.getVarIndex(child);
388: if (!itsNotDefSet.test(varIndex))
389: itsUseBeforeDefSet.set(varIndex);
390: itsNotDefSet.set(varIndex);
391: }
392: }
393: break;
394: case Token.SETVAR: {
395: Node lhs = n.getFirstChild();
396: Node rhs = lhs.getNext();
397: lookForVariableAccess(fn, rhs);
398: itsNotDefSet.set(fn.getVarIndex(n));
399: }
400: break;
401: case Token.GETVAR: {
402: int varIndex = fn.getVarIndex(n);
403: if (!itsNotDefSet.test(varIndex))
404: itsUseBeforeDefSet.set(varIndex);
405: }
406: break;
407: default:
408: Node child = n.getFirstChild();
409: while (child != null) {
410: lookForVariableAccess(fn, child);
411: child = child.getNext();
412: }
413: break;
414: }
415: }
416:
417: /*
418: build the live on entry/exit sets.
419: Then walk the trees looking for defs/uses of variables
420: and build the def and useBeforeDef sets.
421: */
422: private void initLiveOnEntrySets(OptFunctionNode fn,
423: Node[] statementNodes) {
424: int listLength = fn.getVarCount();
425: itsUseBeforeDefSet = new DataFlowBitSet(listLength);
426: itsNotDefSet = new DataFlowBitSet(listLength);
427: itsLiveOnEntrySet = new DataFlowBitSet(listLength);
428: itsLiveOnExitSet = new DataFlowBitSet(listLength);
429: for (int i = itsStartNodeIndex; i <= itsEndNodeIndex; i++) {
430: Node n = statementNodes[i];
431: lookForVariableAccess(fn, n);
432: }
433: itsNotDefSet.not(); // truth in advertising
434: }
435:
436: /*
437: the liveOnEntry of each successor is the liveOnExit for this block.
438: The liveOnEntry for this block is -
439: liveOnEntry = liveOnExit - defsInThisBlock + useBeforeDefsInThisBlock
440:
441: */
442: private boolean doReachedUseDataFlow() {
443: itsLiveOnExitSet.clear();
444: if (itsSuccessors != null)
445: for (int i = 0; i < itsSuccessors.length; i++)
446: itsLiveOnExitSet.or(itsSuccessors[i].itsLiveOnEntrySet);
447: return itsLiveOnEntrySet.df2(itsLiveOnExitSet,
448: itsUseBeforeDefSet, itsNotDefSet);
449: }
450:
451: /*
452: the type of an expression is relatively unknown. Cases we can be sure
453: about are -
454: Literals,
455: Arithmetic operations - always return a Number
456: */
457: private static int findExpressionType(OptFunctionNode fn, Node n,
458: int[] varTypes) {
459: switch (n.getType()) {
460: case Token.NUMBER:
461: return Optimizer.NumberType;
462:
463: case Token.CALL:
464: case Token.NEW:
465: case Token.REF_CALL:
466: return Optimizer.AnyType;
467:
468: case Token.GETELEM:
469: return Optimizer.AnyType;
470:
471: case Token.GETVAR:
472: return varTypes[fn.getVarIndex(n)];
473:
474: case Token.INC:
475: case Token.DEC:
476: case Token.DIV:
477: case Token.MOD:
478: case Token.BITOR:
479: case Token.BITXOR:
480: case Token.BITAND:
481: case Token.LSH:
482: case Token.RSH:
483: case Token.URSH:
484: case Token.SUB:
485: return Optimizer.NumberType;
486:
487: case Token.ARRAYLIT:
488: case Token.OBJECTLIT:
489: return Optimizer.AnyType; // XXX: actually, we know it's not
490: // number, but no type yet for that
491:
492: case Token.ADD: {
493: // if the lhs & rhs are known to be numbers, we can be sure that's
494: // the result, otherwise it could be a string.
495: Node child = n.getFirstChild();
496: int lType = findExpressionType(fn, child, varTypes);
497: int rType = findExpressionType(fn, child.getNext(),
498: varTypes);
499: return lType | rType; // we're not distinguishing strings yet
500: }
501: }
502:
503: Node child = n.getFirstChild();
504: if (child == null) {
505: return Optimizer.AnyType;
506: } else {
507: int result = Optimizer.NoType;
508: while (child != null) {
509: result |= findExpressionType(fn, child, varTypes);
510: child = child.getNext();
511: }
512: return result;
513: }
514: }
515:
516: private static boolean findDefPoints(OptFunctionNode fn, Node n,
517: int[] varTypes) {
518: boolean result = false;
519: Node child = n.getFirstChild();
520: switch (n.getType()) {
521: default:
522: while (child != null) {
523: result |= findDefPoints(fn, child, varTypes);
524: child = child.getNext();
525: }
526: break;
527: case Token.DEC:
528: case Token.INC:
529: if (child.getType() == Token.GETVAR) {
530: // theVar is a Number now
531: int i = fn.getVarIndex(child);
532: result |= assignType(varTypes, i, Optimizer.NumberType);
533: }
534: break;
535: case Token.SETPROP:
536: case Token.SETPROP_OP:
537: if (child.getType() == Token.GETVAR) {
538: int i = fn.getVarIndex(child);
539: assignType(varTypes, i, Optimizer.AnyType);
540: }
541: while (child != null) {
542: result |= findDefPoints(fn, child, varTypes);
543: child = child.getNext();
544: }
545: break;
546: case Token.SETVAR: {
547: Node rValue = child.getNext();
548: int theType = findExpressionType(fn, rValue, varTypes);
549: int i = fn.getVarIndex(n);
550: result |= assignType(varTypes, i, theType);
551: break;
552: }
553: }
554: return result;
555: }
556:
557: private boolean doTypeFlow(OptFunctionNode fn,
558: Node[] statementNodes, int[] varTypes) {
559: boolean changed = false;
560:
561: for (int i = itsStartNodeIndex; i <= itsEndNodeIndex; i++) {
562: Node n = statementNodes[i];
563: if (n != null)
564: changed |= findDefPoints(fn, n, varTypes);
565: }
566:
567: return changed;
568: }
569:
570: private void printLiveOnEntrySet(OptFunctionNode fn) {
571: if (DEBUG) {
572: for (int i = 0; i < fn.getVarCount(); i++) {
573: String name = fn.fnode.getParamOrVarName(i);
574: if (itsUseBeforeDefSet.test(i))
575: System.out.println(name + " is used before def'd");
576: if (itsNotDefSet.test(i))
577: System.out.println(name + " is not def'd");
578: if (itsLiveOnEntrySet.test(i))
579: System.out.println(name + " is live on entry");
580: if (itsLiveOnExitSet.test(i))
581: System.out.println(name + " is live on exit");
582: }
583: }
584: }
585:
586: // all the Blocks that come immediately after this
587: private Block[] itsSuccessors;
588: // all the Blocks that come immediately before this
589: private Block[] itsPredecessors;
590:
591: private int itsStartNodeIndex; // the Node at the start of the block
592: private int itsEndNodeIndex; // the Node at the end of the block
593:
594: private int itsBlockID; // a unique index for each block
595:
596: // reaching def bit sets -
597: private DataFlowBitSet itsLiveOnEntrySet;
598: private DataFlowBitSet itsLiveOnExitSet;
599: private DataFlowBitSet itsUseBeforeDefSet;
600: private DataFlowBitSet itsNotDefSet;
601:
602: static final boolean DEBUG = false;
603: private static int debug_blockCount;
604:
605: }
|