001: /* ====================================================================
002: * Tea - Copyright (c) 1997-2000 Walt Disney Internet Group
003: * ====================================================================
004: * The Tea Software License, Version 1.1
005: *
006: * Copyright (c) 2000 Walt Disney Internet Group. All rights reserved.
007: *
008: * Redistribution and use in source and binary forms, with or without
009: * modification, are permitted provided that the following conditions
010: * are met:
011: *
012: * 1. Redistributions of source code must retain the above copyright
013: * notice, this list of conditions and the following disclaimer.
014: *
015: * 2. Redistributions in binary form must reproduce the above copyright
016: * notice, this list of conditions and the following disclaimer in
017: * the documentation and/or other materials provided with the
018: * distribution.
019: *
020: * 3. The end-user documentation included with the redistribution,
021: * if any, must include the following acknowledgment:
022: * "This product includes software developed by the
023: * Walt Disney Internet Group (http://opensource.go.com/)."
024: * Alternately, this acknowledgment may appear in the software itself,
025: * if and wherever such third-party acknowledgments normally appear.
026: *
027: * 4. The names "Tea", "TeaServlet", "Kettle", "Trove" and "BeanDoc" must
028: * not be used to endorse or promote products derived from this
029: * software without prior written permission. For written
030: * permission, please contact opensource@dig.com.
031: *
032: * 5. Products derived from this software may not be called "Tea",
033: * "TeaServlet", "Kettle" or "Trove", nor may "Tea", "TeaServlet",
034: * "Kettle", "Trove" or "BeanDoc" appear in their name, without prior
035: * written permission of the Walt Disney Internet Group.
036: *
037: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
038: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
039: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
040: * DISCLAIMED. IN NO EVENT SHALL THE WALT DISNEY INTERNET GROUP OR ITS
041: * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
042: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
043: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
044: * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
045: * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
046: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
047: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
048: * ====================================================================
049: *
050: * For more information about Tea, please see http://opensource.go.com/.
051: */
052:
053: package com.go.tea.compiler;
054:
055: import java.util.Vector;
056: import com.go.tea.parsetree.*;
057:
058: /******************************************************************************
059: * The BasicOptimizer only performs two optimizations: constant
060: * folding and dead code elimination.
061: *
062: * <p>Expressions that contain known values at compile time can
063: * be replaced with a constant expression. This basic optimization is
064: * known as constant folding. It improves runtime performance and reduces
065: * the size of generated code.
066: *
067: * <p>Statements that are known at compile time to be unreachable (sometimes
068: * as a result of constant folding) can be removed. This is dead code
069: * elimination, and it mainly reduces the size of generated code. It can also
070: * improve runtime performance.
071: *
072: * @author Brian S O'Neill
073: * @version
074: * <!--$$Revision:--> 45 <!-- $--> 6 <!-- $$JustDate:--> 5/31/01 <!-- $-->
075: */
076: public class BasicOptimizer {
077: private Node mTree;
078:
079: public BasicOptimizer(Node tree) {
080: mTree = tree;
081: }
082:
083: public Node optimize() {
084: return (Node) mTree.accept(new Visitor());
085: }
086:
087: private static class Visitor extends TreeMutator {
088: public Object visit(Statement node) {
089: return null;
090: }
091:
092: public Object visit(StatementList node) {
093: Statement[] stmts = optimizeStatements(node.getStatements());
094: if (stmts == null || stmts.length == 0) {
095: return null;
096: }
097:
098: if (stmts.length == 1) {
099: return stmts[0];
100: }
101:
102: return new StatementList(node.getSourceInfo(), stmts);
103: }
104:
105: public Object visit(Block node) {
106: Statement[] stmts = optimizeStatements(node.getStatements());
107:
108: Statement init = node.getInitializer();
109: if (init != null) {
110: init = (Statement) init.accept(this );
111: }
112:
113: Statement fin = node.getFinalizer();
114: if (fin != null) {
115: fin = (Statement) fin.accept(this );
116: }
117:
118: if (stmts == null || stmts.length == 0) {
119: if (init == null && fin == null) {
120: return null;
121: } else {
122: node = new Block(node.getSourceInfo());
123: }
124: } else {
125: node = new Block(node.getSourceInfo(), stmts);
126: }
127:
128: node.setInitializer(init);
129: node.setFinalizer(fin);
130:
131: return node;
132: }
133:
134: private Statement[] optimizeStatements(Statement[] stmts) {
135: if (stmts == null) {
136: return null;
137: }
138:
139: int length = stmts.length;
140: Vector v = new Vector(length);
141:
142: for (int i = 0; i < length; i++) {
143: Statement stmt = (Statement) stmts[i].accept(this );
144: if (stmt != null) {
145: v.addElement(stmt);
146: }
147: }
148:
149: Statement[] newStmts = new Statement[v.size()];
150: v.copyInto(newStmts);
151:
152: return newStmts;
153: }
154:
155: public Object visit(BreakStatement node) {
156: return (BreakStatement) super .visit(node);
157: }
158:
159: public Object visit(ForeachStatement node) {
160: node = (ForeachStatement) super .visit(node);
161:
162: Expression range = node.getRange();
163: Expression endRange = node.getEndRange();
164: if (endRange != null && range.isValueKnown()
165: && endRange.isValueKnown()) {
166:
167: Object rangeValue = range.getValue();
168: Object endRangeValue = endRange.getValue();
169:
170: if (rangeValue instanceof Number
171: && endRangeValue instanceof Number) {
172:
173: if (((Number) rangeValue).intValue() > ((Number) endRangeValue)
174: .intValue()) {
175:
176: // Will loop zero times. Set the body to null
177: // instead of returning null because the loop
178: // variable still should be set to the first value.
179: // It is possible that the loop variable is
180: // accessed outside the loop, so it must be
181: // set to the correct value.
182:
183: node.setBody(null);
184: }
185: }
186: }
187:
188: return node;
189: }
190:
191: public Object visit(IfStatement node) {
192: Expression condition = visitExpression(node.getCondition());
193:
194: Block thenPart;
195: Block elsePart;
196:
197: // If the condition is a constant boolean...
198: if (condition.isValueKnown()
199: && condition.getType().getObjectClass() == Boolean.class) {
200: // ... and the condition's value is true...
201: if (((Boolean) condition.getValue()).booleanValue()) {
202: // ... then the then part will always execute.
203: thenPart = node.getThenPart();
204: if (thenPart != null) {
205: thenPart = (Block) thenPart.accept(this );
206: }
207:
208: return thenPart;
209: } else {
210: // ... else the else part will always execute.
211: elsePart = node.getElsePart();
212: if (elsePart != null) {
213: elsePart = (Block) elsePart.accept(this );
214: }
215:
216: return elsePart;
217: }
218: }
219:
220: thenPart = node.getThenPart();
221: if (thenPart != null) {
222: thenPart = (Block) thenPart.accept(this );
223: }
224:
225: elsePart = node.getElsePart();
226: if (elsePart != null) {
227: elsePart = (Block) elsePart.accept(this );
228: }
229:
230: // if there is no then part, but there is an else part,
231: // invert the condition and make the else part the then part.
232: if (thenPart == null && elsePart != null) {
233: thenPart = elsePart;
234: elsePart = null;
235: condition.convertTo(Type.BOOLEAN_TYPE);
236: condition = new NotExpression(
237: condition.getSourceInfo(), condition);
238: condition.convertTo(Type.BOOLEAN_TYPE);
239: }
240:
241: node.setCondition(condition);
242: node.setThenPart(thenPart);
243: node.setElsePart(elsePart);
244:
245: return node;
246: }
247:
248: public Object visit(ParenExpression node) {
249: return node.getExpression().accept(this );
250: }
251:
252: public Object visit(NegateExpression node) {
253: SourceInfo info = node.getSourceInfo();
254: Expression expr = visitExpression(node.getExpression());
255:
256: if (expr.isValueKnown()) {
257: Object value = expr.getValue();
258:
259: if (value instanceof Number) {
260: Number number = (Number) value;
261:
262: if (value instanceof Integer) {
263: return new NumberLiteral(info, -number
264: .intValue());
265: } else if (value instanceof Long) {
266: return new NumberLiteral(info, -number
267: .longValue());
268: } else if (value instanceof Float) {
269: return new NumberLiteral(info, -number
270: .floatValue());
271: } else if (value instanceof Double) {
272: return new NumberLiteral(info, -number
273: .doubleValue());
274: }
275: }
276: } else if (expr instanceof NegateExpression) {
277: return ((NegateExpression) expr).getExpression();
278: }
279:
280: node.setExpression(expr);
281: return node;
282: }
283:
284: public Object visit(NotExpression node) {
285: SourceInfo info = node.getSourceInfo();
286: Expression expr = visitExpression(node.getExpression());
287:
288: if (expr.isValueKnown()) {
289: Object value = expr.getValue();
290:
291: if (value instanceof Boolean) {
292: boolean bv = ((Boolean) value).booleanValue();
293: return new BooleanLiteral(info, !bv);
294: }
295: } else if (expr instanceof NotExpression) {
296: return ((NotExpression) expr).getExpression();
297: }
298:
299: node.setExpression(expr);
300: return node;
301: }
302:
303: public Object visit(ConcatenateExpression node) {
304: SourceInfo info = node.getSourceInfo();
305:
306: Expression left = visitExpression(node.getLeftExpression());
307: Expression right = visitExpression(node
308: .getRightExpression());
309:
310: if (left.isValueKnown()
311: && left.getValue() instanceof String) {
312: String leftValue = (String) left.getValue();
313: if (right.isValueKnown()
314: && right.getValue() instanceof String) {
315:
316: String rightValue = (String) right.getValue();
317: return new StringLiteral(info, leftValue
318: + rightValue);
319: }
320:
321: if (leftValue.length() == 0) {
322: return right;
323: }
324: } else if (right.isValueKnown()
325: && right.getValue() instanceof String) {
326:
327: if (((String) right.getValue()).length() == 0) {
328: return left;
329: }
330: }
331:
332: node.setLeftExpression(left);
333: node.setRightExpression(right);
334: return node;
335: }
336:
337: public strictfp Object visit(ArithmeticExpression node) {
338: SourceInfo info = node.getSourceInfo();
339: Token operator = node.getOperator();
340:
341: Expression left = visitExpression(node.getLeftExpression());
342: Expression right = visitExpression(node
343: .getRightExpression());
344:
345: if (node.getType() != null && left.isValueKnown()
346: && right.isValueKnown()) {
347: int ID = operator.getID();
348: Object leftValue = left.getValue();
349: Object rightValue = right.getValue();
350:
351: Type type = left.getType();
352:
353: if (leftValue instanceof Number
354: && rightValue instanceof Number
355: && type.equals(right.getType())) {
356:
357: Class clazz = type.getObjectClass();
358:
359: Number lv = (Number) leftValue;
360: Number rv = (Number) rightValue;
361:
362: try {
363: if (clazz == Integer.class) {
364: int i1 = lv.intValue();
365: int i2 = rv.intValue();
366:
367: switch (ID) {
368: case Token.PLUS:
369: return new NumberLiteral(info, i1 + i2);
370: case Token.MINUS:
371: return new NumberLiteral(info, i1 - i2);
372: case Token.MULT:
373: return new NumberLiteral(info, i1 * i2);
374: case Token.DIV:
375: return new NumberLiteral(info, i1 / i2);
376: case Token.MOD:
377: return new NumberLiteral(info, i1 % i2);
378: }
379: } else if (clazz == Float.class) {
380: float f1 = lv.floatValue();
381: float f2 = rv.floatValue();
382:
383: switch (ID) {
384: case Token.PLUS:
385: return new NumberLiteral(info, f1 + f2);
386: case Token.MINUS:
387: return new NumberLiteral(info, f1 - f2);
388: case Token.MULT:
389: return new NumberLiteral(info, f1 * f2);
390: case Token.DIV:
391: return new NumberLiteral(info, f1 / f2);
392: case Token.MOD:
393: return new NumberLiteral(info, f1 % f2);
394: }
395: } else if (clazz == Long.class) {
396: long L1 = lv.longValue();
397: long L2 = rv.longValue();
398:
399: switch (ID) {
400: case Token.PLUS:
401: return new NumberLiteral(info, L1 + L2);
402: case Token.MINUS:
403: return new NumberLiteral(info, L1 - L2);
404: case Token.MULT:
405: return new NumberLiteral(info, L1 * L2);
406: case Token.DIV:
407: return new NumberLiteral(info, L1 / L2);
408: case Token.MOD:
409: return new NumberLiteral(info, L1 % L2);
410: }
411: } else if (clazz == Double.class) {
412: double d1 = lv.doubleValue();
413: double d2 = rv.doubleValue();
414:
415: switch (ID) {
416: case Token.PLUS:
417: return new NumberLiteral(info, d1 + d2);
418: case Token.MINUS:
419: return new NumberLiteral(info, d1 - d2);
420: case Token.MULT:
421: return new NumberLiteral(info, d1 * d2);
422: case Token.DIV:
423: return new NumberLiteral(info, d1 / d2);
424: case Token.MOD:
425: return new NumberLiteral(info, d1 % d2);
426: }
427: }
428: } catch (ArithmeticException e) {
429: // A divide or mod by 0 is ignored, and expression
430: // is left as is. Runtime will detect and throw
431: // divide by zero. The compiler is not required
432: // to detect divide by zero, because it can't
433: // always perform this check.
434: }
435: }
436: }
437:
438: node.setLeftExpression(left);
439: node.setRightExpression(right);
440: return node;
441: }
442:
443: public Object visit(RelationalExpression node) {
444: SourceInfo info = node.getSourceInfo();
445: Token operator = node.getOperator();
446: int ID = operator.getID();
447:
448: Expression left = visitExpression(node.getLeftExpression());
449: Type leftType = left.getType();
450: Object leftValue = left.getValue();
451:
452: if (ID == Token.ISA) {
453: Type rightType = node.getIsaTypeName().getType();
454:
455: if (rightType.getObjectClass().isAssignableFrom(
456: leftType.getObjectClass())) {
457: // Widening case. i.e. (5 isa Number) is always true.
458: return new BooleanLiteral(info, true);
459: }
460:
461: node.setLeftExpression(left);
462: return node;
463: }
464:
465: Expression right = visitExpression(node
466: .getRightExpression());
467: Type rightType = right.getType();
468: Object rightValue = right.getValue();
469:
470: if (node.getType() != null && left.isValueKnown()
471: && right.isValueKnown() && leftValue != null
472: && rightValue != null) {
473:
474: Type type = leftType;
475:
476: // TODO: support JDK1.2 Comparable interface
477:
478: if (leftValue instanceof Number
479: && rightValue instanceof Number
480: && type.equals(rightType)) {
481:
482: Class clazz = type.getObjectClass();
483:
484: Number lv = (Number) leftValue;
485: Number rv = (Number) rightValue;
486:
487: if (clazz == Integer.class) {
488: int i1 = lv.intValue();
489: int i2 = rv.intValue();
490:
491: switch (ID) {
492: case Token.EQ:
493: return new BooleanLiteral(info, i1 == i2);
494: case Token.NE:
495: return new BooleanLiteral(info, i1 != i2);
496: case Token.LT:
497: return new BooleanLiteral(info, i1 < i2);
498: case Token.GT:
499: return new BooleanLiteral(info, i1 > i2);
500: case Token.LE:
501: return new BooleanLiteral(info, i1 <= i2);
502: case Token.GE:
503: return new BooleanLiteral(info, i1 >= i2);
504: }
505: } else if (clazz == Float.class) {
506: float f1 = lv.floatValue();
507: float f2 = rv.floatValue();
508:
509: switch (ID) {
510: case Token.EQ:
511: return new BooleanLiteral(info, f1 == f2);
512: case Token.NE:
513: return new BooleanLiteral(info, f1 != f2);
514: case Token.LT:
515: return new BooleanLiteral(info, f1 < f2);
516: case Token.GT:
517: return new BooleanLiteral(info, f1 > f2);
518: case Token.LE:
519: return new BooleanLiteral(info, f1 <= f2);
520: case Token.GE:
521: return new BooleanLiteral(info, f1 >= f2);
522: }
523: } else if (clazz == Long.class) {
524: long L1 = lv.longValue();
525: long L2 = rv.longValue();
526:
527: switch (ID) {
528: case Token.EQ:
529: return new BooleanLiteral(info, L1 == L2);
530: case Token.NE:
531: return new BooleanLiteral(info, L1 != L2);
532: case Token.LT:
533: return new BooleanLiteral(info, L1 < L2);
534: case Token.GT:
535: return new BooleanLiteral(info, L1 > L2);
536: case Token.LE:
537: return new BooleanLiteral(info, L1 <= L2);
538: case Token.GE:
539: return new BooleanLiteral(info, L1 >= L2);
540: }
541: } else if (clazz == Double.class) {
542: double d1 = lv.doubleValue();
543: double d2 = rv.doubleValue();
544:
545: switch (ID) {
546: case Token.EQ:
547: return new BooleanLiteral(info, d1 == d2);
548: case Token.NE:
549: return new BooleanLiteral(info, d1 != d2);
550: case Token.LT:
551: return new BooleanLiteral(info, d1 < d2);
552: case Token.GT:
553: return new BooleanLiteral(info, d1 > d2);
554: case Token.LE:
555: return new BooleanLiteral(info, d1 <= d2);
556: case Token.GE:
557: return new BooleanLiteral(info, d1 >= d2);
558: }
559: }
560: } else if (leftValue instanceof String
561: && rightValue instanceof String) {
562:
563: int result = ((String) leftValue)
564: .compareTo((String) rightValue);
565:
566: switch (ID) {
567: case Token.EQ:
568: return new BooleanLiteral(info, result == 0);
569: case Token.NE:
570: return new BooleanLiteral(info, result != 0);
571: case Token.LT:
572: return new BooleanLiteral(info, result < 0);
573: case Token.GT:
574: return new BooleanLiteral(info, result > 0);
575: case Token.LE:
576: return new BooleanLiteral(info, result <= 0);
577: case Token.GE:
578: return new BooleanLiteral(info, result >= 0);
579: }
580: }
581: }
582:
583: if (leftType.isNonNull() && rightType.isNonNull()
584: && leftType.getObjectClass() == Boolean.class
585: && rightType.getObjectClass() == Boolean.class) {
586:
587: if (left.isValueKnown() && leftValue != null) {
588: boolean lv = ((Boolean) leftValue).booleanValue();
589:
590: if (right.isValueKnown() && rightValue != null) {
591: boolean rv = ((Boolean) rightValue)
592: .booleanValue();
593:
594: if (ID == Token.EQ) {
595: return new BooleanLiteral(info, lv == rv);
596: } else if (ID == Token.NE) {
597: return new BooleanLiteral(info, lv != rv);
598: }
599: } else {
600: if (lv) {
601: // (true == (right)) is always (right)
602: if (ID == Token.EQ) {
603: return right;
604: }
605: // (true != (right)) is always !(right)
606: else if (ID == Token.NE) {
607: right.convertTo(Type.BOOLEAN_TYPE);
608: right = new NotExpression(info, right);
609: right.convertTo(Type.BOOLEAN_TYPE);
610: return right;
611: }
612: } else {
613: // (false == (right)) is always !(right)
614: if (ID == Token.EQ) {
615: right.convertTo(Type.BOOLEAN_TYPE);
616: right = new NotExpression(info, right);
617: right.convertTo(Type.BOOLEAN_TYPE);
618: return right;
619: }
620: // (false != (right)) is always (right)
621: else if (ID == Token.NE) {
622: return right;
623: }
624: }
625: }
626: } else if (right.isValueKnown() && rightValue != null) {
627: boolean rv = ((Boolean) rightValue).booleanValue();
628:
629: if (rv) {
630: // ((left) == true) is always (left)
631: if (ID == Token.EQ) {
632: return left;
633: }
634: // ((left) != true) is always !(left)
635: else if (ID == Token.NE) {
636: left.convertTo(Type.BOOLEAN_TYPE);
637: left = new NotExpression(info, left);
638: left.setType(Type.BOOLEAN_TYPE);
639: return left;
640: }
641: } else {
642: // ((left) == false) is always !(left)
643: if (ID == Token.EQ) {
644: left.convertTo(Type.BOOLEAN_TYPE);
645: left = new NotExpression(info, left);
646: left.setType(Type.BOOLEAN_TYPE);
647: return left;
648: }
649: // ((left) != false) is always (left)
650: else if (ID == Token.NE) {
651: return left;
652: }
653: }
654: }
655: }
656:
657: // Optimize tests against null.
658:
659: boolean leftIsNull = left.isValueKnown()
660: && leftValue == null;
661: boolean rightIsNull = right.isValueKnown()
662: && rightValue == null;
663:
664: if (leftIsNull && rightIsNull) {
665: if (ID == Token.EQ) {
666: return new BooleanLiteral(info, true);
667: } else if (ID == Token.NE) {
668: return new BooleanLiteral(info, false);
669: }
670: }
671: /* This optimization may eliminate expressions with side effects.
672: else if (leftIsNull && rightType.isNonNull() ||
673: rightIsNull && leftType.isNonNull()) {
674: */
675: else if (leftIsNull
676: && rightType.isNonNull()
677: && (right instanceof Literal || right instanceof VariableRef)
678: || rightIsNull
679: && leftType.isNonNull()
680: && (left instanceof Literal || left instanceof VariableRef)) {
681:
682: if (ID == Token.EQ) {
683: return new BooleanLiteral(info, false);
684: } else if (ID == Token.NE) {
685: return new BooleanLiteral(info, true);
686: }
687: }
688:
689: node.setLeftExpression(left);
690: node.setRightExpression(right);
691: return node;
692: }
693:
694: public Object visit(AndExpression node) {
695: SourceInfo info = node.getSourceInfo();
696:
697: Expression left = visitExpression(node.getLeftExpression());
698: Expression right = visitExpression(node
699: .getRightExpression());
700:
701: if (left.isValueKnown()) {
702: Object leftValue = left.getValue();
703: if (leftValue instanceof Boolean) {
704: if (((Boolean) leftValue).booleanValue()) {
705: // "And"ing with true has no effect. Simply return the
706: // right expression.
707: return right;
708: } else {
709: // Short circuit result if value is false.
710: return new BooleanLiteral(info, false);
711: }
712: }
713: }
714:
715: if (right.isValueKnown()) {
716: Object rightValue = right.getValue();
717: if (rightValue instanceof Boolean) {
718: if (((Boolean) rightValue).booleanValue()) {
719: // "And"ing with true has no effect. Simply return the
720: // left expression.
721: return left;
722: } else {
723: // Don't short cicuit in this case.
724: }
725: }
726: }
727:
728: node.setLeftExpression(left);
729: node.setRightExpression(right);
730: return node;
731: }
732:
733: public Object visit(OrExpression node) {
734: SourceInfo info = node.getSourceInfo();
735:
736: Expression left = visitExpression(node.getLeftExpression());
737: Expression right = visitExpression(node
738: .getRightExpression());
739:
740: if (left.isValueKnown()) {
741: Object leftValue = left.getValue();
742: if (leftValue instanceof Boolean) {
743: if (((Boolean) leftValue).booleanValue()) {
744: // Short circuit result if value is true.
745: return new BooleanLiteral(info, true);
746: } else {
747: // "Or"ing with false has no effect. Simply return the
748: // right expression.
749: return right;
750: }
751: }
752: }
753:
754: if (right.isValueKnown()) {
755: Object rightValue = right.getValue();
756: if (rightValue instanceof Boolean) {
757: if (((Boolean) rightValue).booleanValue()) {
758: // Don't short cicuit in this case.
759: } else {
760: // "Or"ing with false has no effect. Simply return the
761: // left expression.
762: return left;
763: }
764: }
765: }
766:
767: node.setLeftExpression(left);
768: node.setRightExpression(right);
769: return node;
770: }
771: }
772: }
|