001: /*
002: * Copyright 2007 Google Inc.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License"); you may not
005: * use this file except in compliance with the License. You may obtain a copy of
006: * the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
012: * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
013: * License for the specific language governing permissions and limitations under
014: * the License.
015: */
016: package com.google.gwt.dev.jjs.impl;
017:
018: import com.google.gwt.dev.jjs.ast.Context;
019: import com.google.gwt.dev.jjs.ast.JBinaryOperation;
020: import com.google.gwt.dev.jjs.ast.JBinaryOperator;
021: import com.google.gwt.dev.jjs.ast.JBlock;
022: import com.google.gwt.dev.jjs.ast.JBooleanLiteral;
023: import com.google.gwt.dev.jjs.ast.JBreakStatement;
024: import com.google.gwt.dev.jjs.ast.JCaseStatement;
025: import com.google.gwt.dev.jjs.ast.JCharLiteral;
026: import com.google.gwt.dev.jjs.ast.JConditional;
027: import com.google.gwt.dev.jjs.ast.JContinueStatement;
028: import com.google.gwt.dev.jjs.ast.JDoStatement;
029: import com.google.gwt.dev.jjs.ast.JDoubleLiteral;
030: import com.google.gwt.dev.jjs.ast.JExpression;
031: import com.google.gwt.dev.jjs.ast.JExpressionStatement;
032: import com.google.gwt.dev.jjs.ast.JFieldRef;
033: import com.google.gwt.dev.jjs.ast.JForStatement;
034: import com.google.gwt.dev.jjs.ast.JIfStatement;
035: import com.google.gwt.dev.jjs.ast.JIntLiteral;
036: import com.google.gwt.dev.jjs.ast.JLocalDeclarationStatement;
037: import com.google.gwt.dev.jjs.ast.JLocalRef;
038: import com.google.gwt.dev.jjs.ast.JLongLiteral;
039: import com.google.gwt.dev.jjs.ast.JMethod;
040: import com.google.gwt.dev.jjs.ast.JMethodCall;
041: import com.google.gwt.dev.jjs.ast.JModVisitor;
042: import com.google.gwt.dev.jjs.ast.JNode;
043: import com.google.gwt.dev.jjs.ast.JPrefixOperation;
044: import com.google.gwt.dev.jjs.ast.JProgram;
045: import com.google.gwt.dev.jjs.ast.JReferenceType;
046: import com.google.gwt.dev.jjs.ast.JStatement;
047: import com.google.gwt.dev.jjs.ast.JStringLiteral;
048: import com.google.gwt.dev.jjs.ast.JSwitchStatement;
049: import com.google.gwt.dev.jjs.ast.JTryStatement;
050: import com.google.gwt.dev.jjs.ast.JType;
051: import com.google.gwt.dev.jjs.ast.JUnaryOperator;
052: import com.google.gwt.dev.jjs.ast.JValueLiteral;
053: import com.google.gwt.dev.jjs.ast.JVisitor;
054: import com.google.gwt.dev.jjs.ast.JWhileStatement;
055: import com.google.gwt.dev.jjs.ast.js.JMultiExpression;
056:
057: import java.lang.reflect.Method;
058: import java.util.ArrayList;
059: import java.util.HashSet;
060: import java.util.IdentityHashMap;
061: import java.util.Iterator;
062: import java.util.List;
063: import java.util.Map;
064: import java.util.Set;
065:
066: /**
067: * Attempts to remove dead code.
068: */
069: public class DeadCodeElimination {
070:
071: /**
072: * Eliminates dead or unreachable code when possible.
073: */
074: public class DeadCodeVisitor extends JModVisitor {
075:
076: /**
077: * An expression whose result does not matter.
078: */
079: private JExpression ignoringExpressionOutput;
080:
081: private Set<JBlock> switchBlocks = new HashSet<JBlock>();
082:
083: /**
084: * Short circuit binary operations.
085: */
086: @Override
087: public void endVisit(JBinaryOperation x, Context ctx) {
088: JBinaryOperator op = x.getOp();
089: JExpression lhs = x.getLhs();
090: JExpression rhs = x.getRhs();
091: if (op == JBinaryOperator.AND) {
092: // simplify short circuit AND expressions
093: if (lhs instanceof JBooleanLiteral) {
094: // eg: if (false && isWhatever()) -> if (false)
095: // eg: if (true && isWhatever()) -> if (isWhatever())
096: JBooleanLiteral booleanLiteral = (JBooleanLiteral) lhs;
097: if (booleanLiteral.getValue()) {
098: ctx.replaceMe(rhs);
099: } else {
100: ctx.replaceMe(lhs);
101: }
102:
103: } else if (rhs instanceof JBooleanLiteral) {
104: // eg: if (isWhatever() && true) -> if (isWhatever())
105: // eg: if (isWhatever() && false) -> if (false), unless side effects
106: JBooleanLiteral booleanLiteral = (JBooleanLiteral) rhs;
107: if (booleanLiteral.getValue()) {
108: ctx.replaceMe(lhs);
109: } else if (!lhs.hasSideEffects()) {
110: ctx.replaceMe(rhs);
111: }
112: }
113:
114: } else if (op == JBinaryOperator.OR) {
115: // simplify short circuit OR expressions
116: if (lhs instanceof JBooleanLiteral) {
117: // eg: if (true || isWhatever()) -> if (true)
118: // eg: if (false || isWhatever()) -> if (isWhatever())
119: JBooleanLiteral booleanLiteral = (JBooleanLiteral) lhs;
120: if (booleanLiteral.getValue()) {
121: ctx.replaceMe(lhs);
122: } else {
123: ctx.replaceMe(rhs);
124: }
125:
126: } else if (rhs instanceof JBooleanLiteral) {
127: // eg: if (isWhatever() || false) -> if (isWhatever())
128: // eg: if (isWhatever() && true) -> if (true), unless side effects
129: JBooleanLiteral booleanLiteral = (JBooleanLiteral) rhs;
130: if (!booleanLiteral.getValue()) {
131: ctx.replaceMe(lhs);
132: } else if (!lhs.hasSideEffects()) {
133: ctx.replaceMe(rhs);
134: }
135: }
136: } else if (op == JBinaryOperator.EQ) {
137: // simplify: null == null -> true
138: if (lhs.getType() == program.getTypeNull()
139: && rhs.getType() == program.getTypeNull()) {
140: ctx.replaceMe(program.getLiteralBoolean(true));
141: }
142: } else if (op == JBinaryOperator.NEQ) {
143: // simplify: null != null -> false
144: if (lhs.getType() == program.getTypeNull()
145: && rhs.getType() == program.getTypeNull()) {
146: ctx.replaceMe(program.getLiteralBoolean(false));
147: }
148: } else if (op == JBinaryOperator.ADD
149: && x.getType() == program.getTypeJavaLangString()) {
150: // try to statically evaluate concatentation
151: if (lhs instanceof JValueLiteral
152: && rhs instanceof JValueLiteral) {
153: Object lhsObj = ((JValueLiteral) lhs).getValueObj();
154: Object rhsObj = ((JValueLiteral) rhs).getValueObj();
155: ctx.replaceMe(program.getLiteralString(String
156: .valueOf(lhsObj)
157: + String.valueOf(rhsObj)));
158: }
159: }
160: }
161:
162: /**
163: * Prune dead statements and empty blocks.
164: */
165: @Override
166: public void endVisit(JBlock x, Context ctx) {
167: // Switch blocks require special optimization code
168: if (switchBlocks.contains(x)) {
169: return;
170: }
171:
172: /*
173: * Remove any dead statements after an abrupt change in code flow and
174: * promote safe statements within nested blocks to this block.
175: */
176: for (int i = 0; i < x.statements.size(); i++) {
177: JStatement stmt = x.statements.get(i);
178:
179: if (stmt instanceof JBlock) {
180: /*
181: * Promote a sub-block's children to the current block, unless the
182: * sub-block contains local declarations as children.
183: */
184: JBlock block = (JBlock) stmt;
185: if (canPromoteBlock(block)) {
186: x.statements.remove(i);
187: x.statements.addAll(i, block.statements);
188: i--;
189: didChange = true;
190: continue;
191: }
192: }
193:
194: if (stmt.unconditionalControlBreak()) {
195: // Abrupt change in flow, chop the remaining items from this block
196: for (int j = i + 1; j < x.statements.size();) {
197: x.statements.remove(j);
198: didChange = true;
199: }
200: }
201: }
202:
203: if (ctx.canRemove() && x.statements.size() == 0) {
204: // Remove blocks with no effect
205: ctx.removeMe();
206: }
207: }
208:
209: @Override
210: public void endVisit(JConditional x, Context ctx) {
211: JExpression condExpr = x.getIfTest();
212: JExpression thenExpr = x.getThenExpr();
213: JExpression elseExpr = x.getElseExpr();
214: if (condExpr instanceof JBooleanLiteral) {
215: if (((JBooleanLiteral) condExpr).getValue()) {
216: // e.g. (true ? then : else) -> then
217: ctx.replaceMe(thenExpr);
218: } else {
219: // e.g. (false ? then : else) -> else
220: ctx.replaceMe(elseExpr);
221: }
222: } else if (thenExpr instanceof JBooleanLiteral) {
223: if (((JBooleanLiteral) thenExpr).getValue()) {
224: // e.g. (cond ? true : else) -> cond || else
225: JBinaryOperation binOp = new JBinaryOperation(
226: program, x.getSourceInfo(), x.getType(),
227: JBinaryOperator.OR, condExpr, elseExpr);
228: ctx.replaceMe(binOp);
229: } else {
230: // e.g. (cond ? false : else) -> !cond && else
231: JPrefixOperation notCondExpr = new JPrefixOperation(
232: program, condExpr.getSourceInfo(),
233: JUnaryOperator.NOT, condExpr);
234: JBinaryOperation binOp = new JBinaryOperation(
235: program, x.getSourceInfo(), x.getType(),
236: JBinaryOperator.AND, notCondExpr, elseExpr);
237: ctx.replaceMe(binOp);
238: }
239: } else if (elseExpr instanceof JBooleanLiteral) {
240: if (((JBooleanLiteral) elseExpr).getValue()) {
241: // e.g. (cond ? then : true) -> !cond || then
242: JPrefixOperation notCondExpr = new JPrefixOperation(
243: program, condExpr.getSourceInfo(),
244: JUnaryOperator.NOT, condExpr);
245: JBinaryOperation binOp = new JBinaryOperation(
246: program, x.getSourceInfo(), x.getType(),
247: JBinaryOperator.OR, notCondExpr, thenExpr);
248: ctx.replaceMe(binOp);
249: } else {
250: // e.g. (cond ? then : false) -> cond && then
251: JBinaryOperation binOp = new JBinaryOperation(
252: program, x.getSourceInfo(), x.getType(),
253: JBinaryOperator.AND, condExpr, thenExpr);
254: ctx.replaceMe(binOp);
255: }
256: }
257: }
258:
259: /**
260: * Convert do { } while (false); into a block.
261: */
262: @Override
263: public void endVisit(JDoStatement x, Context ctx) {
264: JExpression expression = x.getTestExpr();
265: if (expression instanceof JBooleanLiteral) {
266: JBooleanLiteral booleanLiteral = (JBooleanLiteral) expression;
267:
268: // If false, replace do with do's body
269: if (!booleanLiteral.getValue()) {
270: // Unless it contains break/continue statements
271: FindBreakContinueStatementsVisitor visitor = new FindBreakContinueStatementsVisitor();
272: visitor.accept(x.getBody());
273: if (!visitor.hasBreakContinueStatements()) {
274: ctx.replaceMe(x.getBody());
275: }
276: }
277: }
278: }
279:
280: @Override
281: public void endVisit(JExpressionStatement x, Context ctx) {
282: if (!x.getExpr().hasSideEffects()) {
283: removeMe(x, ctx);
284: }
285: }
286:
287: /**
288: * Prune for (X; false; Y) statements, but make sure X is run.
289: */
290: @Override
291: public void endVisit(JForStatement x, Context ctx) {
292: JExpression expression = x.getTestExpr();
293: if (expression instanceof JBooleanLiteral) {
294: JBooleanLiteral booleanLiteral = (JBooleanLiteral) expression;
295:
296: // If false, replace the for statement with its initializers
297: if (!booleanLiteral.getValue()) {
298: JBlock block = new JBlock(program, x
299: .getSourceInfo());
300: block.statements.addAll(x.getInitializers());
301: ctx.replaceMe(block);
302: }
303: }
304: }
305:
306: /**
307: * Simplify if statements.
308: */
309: @Override
310: public void endVisit(JIfStatement x, Context ctx) {
311: JExpression expr = x.getIfExpr();
312: JStatement thenStmt = x.getThenStmt();
313: JStatement elseStmt = x.getElseStmt();
314: if (expr instanceof JBooleanLiteral) {
315: JBooleanLiteral booleanLiteral = (JBooleanLiteral) expr;
316: boolean boolVal = booleanLiteral.getValue();
317: if (boolVal && !isEmpty(thenStmt)) {
318: // If true, replace myself with then statement
319: ctx.replaceMe(thenStmt);
320: } else if (!boolVal && !isEmpty(elseStmt)) {
321: // If false, replace myself with else statement
322: ctx.replaceMe(elseStmt);
323: } else {
324: // just prune me
325: removeMe(x, ctx);
326: }
327: } else if (isEmpty(thenStmt) && isEmpty(elseStmt)) {
328: ctx.replaceMe(expr.makeStatement());
329: }
330: }
331:
332: /**
333: * Resolve method calls that can be computed statically.
334: */
335: @Override
336: public void endVisit(JMethodCall x, Context ctx) {
337: JMethod target = x.getTarget();
338: JReferenceType targetType = target.getEnclosingType();
339: if (targetType == program.getTypeJavaLangString()) {
340: tryOptimizeStringCall(x, ctx, target);
341: } else if (program.isClinit(target)) {
342: // Eliminate the call if the target is now empty.
343: if (!program.typeOracle.hasClinit(targetType)) {
344: ctx.replaceMe(program.getLiteralNull());
345: }
346: }
347: }
348:
349: /**
350: * Remove any parts of JMultiExpression that have no side-effect.
351: */
352: @Override
353: public void endVisit(JMultiExpression x, Context ctx) {
354: /*
355: * If we're ignoring the output of this expression, we don't need to
356: * maintain the final multi value.
357: */
358: for (int i = 0; i < numRemovableExpressions(x); i++) {
359: JExpression expr = x.exprs.get(i);
360: if (!expr.hasSideEffects()) {
361: x.exprs.remove(i);
362: i--;
363: continue;
364: }
365:
366: // Remove nested JMultiExpressions
367: if (expr instanceof JMultiExpression) {
368: x.exprs.remove(i);
369: x.exprs.addAll(i, ((JMultiExpression) expr).exprs);
370: i--;
371: continue;
372: }
373:
374: if (expr instanceof JFieldRef) {
375: JFieldRef fieldRef = (JFieldRef) expr;
376: JExpression instance = fieldRef.getInstance();
377: if (instance == null || !instance.hasSideEffects()) {
378: // If the instance doesn't have side-effects, but the field ref
379: // does, it's because a clinit() needs to happen.
380: JMethod clinit = fieldRef.getField()
381: .getEnclosingType().methods.get(0);
382: assert (clinit.getName().equals("$clinit"));
383:
384: // Replace the field ref with a direct call to the clinit.
385: JMethodCall methodCall = new JMethodCall(
386: program, expr.getSourceInfo(),
387: instance, clinit);
388: x.exprs.set(i, methodCall);
389: }
390: }
391: }
392:
393: if (x.exprs.size() == 1) {
394: ctx.replaceMe(x.exprs.get(0));
395: }
396: }
397:
398: /**
399: * Simplify the ! operator if possible.
400: */
401: @Override
402: public void endVisit(JPrefixOperation x, Context ctx) {
403: if (x.getOp() == JUnaryOperator.NOT) {
404: JExpression arg = x.getArg();
405: if (arg instanceof JBooleanLiteral) {
406: // e.g. !true -> false; !false -> true
407: JBooleanLiteral booleanLiteral = (JBooleanLiteral) arg;
408: ctx.replaceMe(program
409: .getLiteralBoolean(!booleanLiteral
410: .getValue()));
411: } else if (arg instanceof JBinaryOperation) {
412: // try to invert the binary operator
413: JBinaryOperation argOp = (JBinaryOperation) arg;
414: JBinaryOperator op = argOp.getOp();
415: JBinaryOperator newOp = null;
416: if (op == JBinaryOperator.EQ) {
417: // e.g. !(x == y) -> x != y
418: newOp = JBinaryOperator.NEQ;
419: } else if (op == JBinaryOperator.NEQ) {
420: // e.g. !(x != y) -> x == y
421: newOp = JBinaryOperator.EQ;
422: } else if (op == JBinaryOperator.GT) {
423: // e.g. !(x > y) -> x <= y
424: newOp = JBinaryOperator.LTE;
425: } else if (op == JBinaryOperator.LTE) {
426: // e.g. !(x <= y) -> x > y
427: newOp = JBinaryOperator.GT;
428: } else if (op == JBinaryOperator.GTE) {
429: // e.g. !(x >= y) -> x < y
430: newOp = JBinaryOperator.LT;
431: } else if (op == JBinaryOperator.LT) {
432: // e.g. !(x < y) -> x >= y
433: newOp = JBinaryOperator.GTE;
434: }
435: if (newOp != null) {
436: JBinaryOperation newBinOp = new JBinaryOperation(
437: program, argOp.getSourceInfo(), argOp
438: .getType(), newOp, argOp
439: .getLhs(), argOp.getRhs());
440: ctx.replaceMe(newBinOp);
441: }
442: } else if (arg instanceof JPrefixOperation) {
443: // try to invert the unary operator
444: JPrefixOperation argOp = (JPrefixOperation) arg;
445: JUnaryOperator op = argOp.getOp();
446: // e.g. !!x -> x
447: if (op == JUnaryOperator.NOT) {
448: ctx.replaceMe(argOp.getArg());
449: }
450: }
451: }
452: }
453:
454: /**
455: * Optimize switch statements.
456: */
457: public void endVisit(JSwitchStatement x, Context ctx) {
458: switchBlocks.remove(x.getBody());
459:
460: if (hasNoDefaultCase(x)) {
461: removeEmptyCases(x);
462: }
463: removeDoubleBreaks(x);
464: tryRemoveSwitch(x, ctx);
465: }
466:
467: /**
468: * 1) Remove catch blocks whose exception type is not instantiable. 2) Prune
469: * try statements with no body. 3) Hoist up try statements with no catches
470: * and an empty finally.
471: */
472: @Override
473: public void endVisit(JTryStatement x, Context ctx) {
474: // 1) Remove catch blocks whose exception type is not instantiable.
475: List<JLocalRef> catchArgs = x.getCatchArgs();
476: List<JBlock> catchBlocks = x.getCatchBlocks();
477: Iterator<JLocalRef> itA = catchArgs.iterator();
478: Iterator<JBlock> itB = catchBlocks.iterator();
479: while (itA.hasNext()) {
480: JLocalRef localRef = itA.next();
481: itB.next();
482: JReferenceType type = (JReferenceType) localRef
483: .getType();
484: if (!program.typeOracle.isInstantiatedType(type)
485: || type == program.getTypeNull()) {
486: itA.remove();
487: itB.remove();
488: }
489: }
490:
491: // Compute properties regarding the state of this try statement
492: boolean noTry = isEmpty(x.getTryBlock());
493: boolean noCatch = catchArgs.size() == 0;
494: boolean noFinally = isEmpty(x.getFinallyBlock());
495:
496: if (noTry) {
497: // 2) Prune try statements with no body.
498: if (noFinally) {
499: // if there's no finally, prune the whole thing
500: removeMe(x, ctx);
501: } else {
502: // replace the try statement with just the contents of the finally
503: ctx.replaceMe(x.getFinallyBlock());
504: }
505: } else if (noCatch && noFinally) {
506: // 3) Hoist up try statements with no catches and an empty finally.
507: // If there's no catch or finally, there's no point in this even being
508: // a try statement, replace myself with the try block
509: ctx.replaceMe(x.getTryBlock());
510: }
511: }
512:
513: /**
514: * Prune while (false) statements.
515: */
516: @Override
517: public void endVisit(JWhileStatement x, Context ctx) {
518: JExpression expression = x.getTestExpr();
519: if (expression instanceof JBooleanLiteral) {
520: JBooleanLiteral booleanLiteral = (JBooleanLiteral) expression;
521:
522: // If false, prune the while statement
523: if (!booleanLiteral.getValue()) {
524: removeMe(x, ctx);
525: }
526: }
527: }
528:
529: @Override
530: public boolean visit(JExpressionStatement x, Context ctx) {
531: ignoringExpressionOutput = x.getExpr();
532: return true;
533: }
534:
535: @Override
536: public boolean visit(JSwitchStatement x, Context ctx) {
537: switchBlocks.add(x.getBody());
538: return true;
539: }
540:
541: /**
542: * Returns true if a block can be merged into its parent block. This is true
543: * when the block contains no local declarations.
544: */
545: private boolean canPromoteBlock(JBlock block) {
546: for (JStatement nestedStmt : block.statements) {
547: if (nestedStmt instanceof JLocalDeclarationStatement) {
548: return false;
549: }
550: }
551: return true;
552: }
553:
554: private boolean hasNoDefaultCase(JSwitchStatement x) {
555: JBlock body = x.getBody();
556: boolean inDefault = false;
557: for (JStatement statement : body.statements) {
558: if (statement instanceof JCaseStatement) {
559: JCaseStatement caseStmt = (JCaseStatement) statement;
560: if (caseStmt.getExpr() == null) {
561: inDefault = true;
562: }
563: } else if (isUnconditionalBreak(statement)) {
564: inDefault = false;
565: } else {
566: // We have some code to execute other than a break.
567: if (inDefault) {
568: // We have a default case with real code.
569: return false;
570: }
571: }
572: }
573: // We found no default case that wasn't empty.
574: return true;
575: }
576:
577: /**
578: * TODO: if the AST were normalized, we wouldn't need this.
579: */
580: private boolean isEmpty(JStatement stmt) {
581: if (stmt == null) {
582: return true;
583: }
584: return (stmt instanceof JBlock && ((JBlock) stmt).statements
585: .isEmpty());
586: }
587:
588: private boolean isUnconditionalBreak(JStatement statement) {
589: if (statement instanceof JBreakStatement) {
590: return true;
591: } else if (statement instanceof JBlock) {
592: JBlock block = (JBlock) statement;
593: List<JStatement> blockStmts = block.statements;
594: return blockStmts.size() > 0
595: && isUnconditionalBreak(blockStmts.get(0));
596: } else {
597: return false;
598: }
599: }
600:
601: private Class<?> mapType(JType type) {
602: return typeClassMap.get(type);
603: }
604:
605: private int numRemovableExpressions(JMultiExpression x) {
606: if (x == ignoringExpressionOutput) {
607: // All expressions can be removed.
608: return x.exprs.size();
609: } else {
610: // The last expression cannot be removed.
611: return x.exprs.size() - 1;
612: }
613: }
614:
615: /**
616: * Removes any break statements that appear one after another.
617: */
618: private void removeDoubleBreaks(JSwitchStatement x) {
619: JBlock body = x.getBody();
620: boolean lastWasBreak = true;
621: for (Iterator<JStatement> it = body.statements.iterator(); it
622: .hasNext();) {
623: JStatement statement = it.next();
624: boolean isBreak = isUnconditionalBreak(statement);
625: if (isBreak && lastWasBreak) {
626: it.remove();
627: }
628: lastWasBreak = isBreak;
629: }
630:
631: // Remove a trailing break statement from a case block
632: if (lastWasBreak && body.statements.size() > 0) {
633: body.statements.remove(body.statements.size() - 1);
634: }
635: }
636:
637: /**
638: * A switch with no default case can have its empty cases pruned.
639: */
640: private void removeEmptyCases(JSwitchStatement x) {
641: JBlock body = x.getBody();
642: List<JStatement> noOpCaseStatements = new ArrayList<JStatement>();
643: List<JStatement> potentialNoOpCaseStatements = new ArrayList<JStatement>();
644: /*
645: * A case statement has no effect if there is no code between it and
646: * either an unconditional break or the end of the switch.
647: */
648: for (JStatement statement : body.statements) {
649: if (statement instanceof JCaseStatement) {
650: potentialNoOpCaseStatements.add(statement);
651: } else if (isUnconditionalBreak(statement)) {
652: // If we have any potential no-ops, they now become real no-ops.
653: noOpCaseStatements
654: .addAll(potentialNoOpCaseStatements);
655: potentialNoOpCaseStatements.clear();
656: } else {
657: // Any other kind of statement makes these case statements are useful.
658: potentialNoOpCaseStatements.clear();
659: }
660: }
661: // None of the remaining case statements have any effect
662: noOpCaseStatements.addAll(potentialNoOpCaseStatements);
663:
664: if (noOpCaseStatements.size() > 0) {
665: for (JStatement statement : noOpCaseStatements) {
666: body.statements.remove(statement);
667: }
668: }
669: }
670:
671: private void removeMe(JStatement stmt, Context ctx) {
672: if (ctx.canRemove()) {
673: ctx.removeMe();
674: } else {
675: // empty block statement
676: ctx
677: .replaceMe(new JBlock(program, stmt
678: .getSourceInfo()));
679: }
680: }
681:
682: /**
683: * Replace String methods having literal args with the static result.
684: */
685: private void tryOptimizeStringCall(JMethodCall x, Context ctx,
686: JMethod method) {
687:
688: if (method.getType() == program.getTypeVoid()) {
689: return;
690: }
691:
692: if (method.getOriginalParamTypes().size() != method.params
693: .size()) {
694: // One or more parameters were pruned, abort.
695: return;
696: }
697:
698: if (method.getName().endsWith("hashCode")) {
699: // This cannot be computed at compile time because our implementation
700: // differs from the JRE.
701: return;
702: }
703:
704: int skip = 0;
705: Object instance;
706: if (program.isStaticImpl(method)) {
707: // is it static implementation for instance method?
708: method = program.staticImplFor(method);
709: instance = tryTranslateLiteral(x.getArgs().get(0),
710: String.class);
711: skip = 1;
712: } else {
713: // instance may be null
714: instance = tryTranslateLiteral(x.getInstance(),
715: String.class);
716: }
717:
718: if (instance == null && !method.isStatic()) {
719: return;
720: }
721:
722: List<JType> params = method.getOriginalParamTypes();
723: Class<?> paramTypes[] = new Class<?>[params.size()];
724: Object paramValues[] = new Object[params.size()];
725: ArrayList<JExpression> args = x.getArgs();
726: for (int i = 0; i != params.size(); ++i) {
727: paramTypes[i] = mapType(params.get(i));
728: if (paramTypes[i] == null) {
729: return;
730: }
731: paramValues[i] = tryTranslateLiteral(
732: args.get(i + skip), paramTypes[i]);
733: if (paramValues[i] == null) {
734: return;
735: }
736: }
737:
738: try {
739: Method actual = String.class.getMethod(
740: method.getName(), paramTypes);
741: if (actual == null) {
742: return;
743: }
744: Object result = actual.invoke(instance, paramValues);
745: if (result instanceof String) {
746: ctx.replaceMe(program
747: .getLiteralString((String) result));
748: } else if (result instanceof Boolean) {
749: ctx.replaceMe(program
750: .getLiteralBoolean(((Boolean) result)
751: .booleanValue()));
752: } else if (result instanceof Character) {
753: ctx.replaceMe(program
754: .getLiteralChar(((Character) result)
755: .charValue()));
756: } else if (result instanceof Integer) {
757: ctx.replaceMe(program
758: .getLiteralInt(((Integer) result)
759: .intValue()));
760: }
761: } catch (Exception e) {
762: // If the call threw an exception, just don't optimize
763: }
764: }
765:
766: private void tryRemoveSwitch(JSwitchStatement x, Context ctx) {
767: JBlock body = x.getBody();
768: if (body.statements.size() == 0) {
769: // Empty switch; just run the switch condition.
770: ctx.replaceMe(x.getExpr().makeStatement());
771: } else if (body.statements.size() == 2) {
772: /*
773: * If there are only two statements, we know it's a case statement and
774: * something with an effect.
775: *
776: * TODO: make this more sophisticated; what we should really care about
777: * is how many case statements it contains, not how many statements:
778: *
779: * switch(i) { default: a(); b(); c(); }
780: *
781: * becomes { a(); b(); c(); }
782: *
783: * switch(i) { case 1: a(); b(); c(); }
784: *
785: * becomes if (i == 1) { a(); b(); c(); }
786: *
787: * switch(i) { case 1: a(); b(); break; default: c(); d(); }
788: *
789: * becomes if (i == 1) { a(); b(); } else { c(); d(); }
790: */
791: JCaseStatement caseStatement = (JCaseStatement) body.statements
792: .get(0);
793: JStatement statement = body.statements.get(1);
794:
795: FindBreakContinueStatementsVisitor visitor = new FindBreakContinueStatementsVisitor();
796: visitor.accept(statement);
797: if (visitor.hasBreakContinueStatements()) {
798: // Cannot optimize.
799: return;
800: }
801:
802: if (caseStatement.getExpr() != null) {
803: // Create an if statement equivalent to the single-case switch.
804: JBinaryOperation compareOperation = new JBinaryOperation(
805: program, x.getSourceInfo(), program
806: .getTypePrimitiveBoolean(),
807: JBinaryOperator.EQ, x.getExpr(),
808: caseStatement.getExpr());
809: JBlock block = new JBlock(program, x
810: .getSourceInfo());
811: block.statements.add(statement);
812: JIfStatement ifStatement = new JIfStatement(
813: program, x.getSourceInfo(),
814: compareOperation, block, null);
815: ctx.replaceMe(ifStatement);
816: } else {
817: // All we have is a default case; convert to a JBlock.
818: JBlock block = new JBlock(program, x
819: .getSourceInfo());
820: block.statements.add(x.getExpr().makeStatement());
821: block.statements.add(statement);
822: ctx.replaceMe(block);
823: }
824: }
825: }
826:
827: private Object tryTranslateLiteral(JExpression maybeLit,
828: Class<?> type) {
829: if (!(maybeLit instanceof JValueLiteral)) {
830: return null;
831: }
832: // TODO: make this way better by a mile
833: if (type == boolean.class
834: && maybeLit instanceof JBooleanLiteral) {
835: return Boolean.valueOf(((JBooleanLiteral) maybeLit)
836: .getValue());
837: }
838: if (type == char.class && maybeLit instanceof JCharLiteral) {
839: return new Character(((JCharLiteral) maybeLit)
840: .getValue());
841: }
842: if (type == double.class
843: && maybeLit instanceof JDoubleLiteral) {
844: return new Double(((JDoubleLiteral) maybeLit)
845: .getValue());
846: }
847: if (type == float.class && maybeLit instanceof JIntLiteral) {
848: return new Float(((JIntLiteral) maybeLit).getValue());
849: }
850: if (type == int.class && maybeLit instanceof JIntLiteral) {
851: return new Integer(((JIntLiteral) maybeLit).getValue());
852: }
853: if (type == long.class && maybeLit instanceof JLongLiteral) {
854: return new Long(((JLongLiteral) maybeLit).getValue());
855: }
856: if (type == String.class
857: && maybeLit instanceof JStringLiteral) {
858: return ((JStringLiteral) maybeLit).getValue();
859: }
860: if (type == Object.class
861: && maybeLit instanceof JValueLiteral) {
862: return ((JValueLiteral) maybeLit).getValueObj();
863: }
864: return null;
865: }
866: }
867:
868: /**
869: * Examines code to find out whether it contains any break or continue
870: * statements.
871: *
872: * TODO: We could be more sophisticated with this. A nested while loop with an
873: * unlabeled break should not cause this visitor to return false. Nor should a
874: * labeled break break to another context.
875: */
876: public static class FindBreakContinueStatementsVisitor extends
877: JVisitor {
878: private boolean hasBreakContinueStatements = false;
879:
880: @Override
881: public void endVisit(JBreakStatement x, Context ctx) {
882: hasBreakContinueStatements = true;
883: }
884:
885: @Override
886: public void endVisit(JContinueStatement x, Context ctx) {
887: hasBreakContinueStatements = true;
888: }
889:
890: protected boolean hasBreakContinueStatements() {
891: return hasBreakContinueStatements;
892: }
893: }
894:
895: public static boolean exec(JProgram program) {
896: return new DeadCodeElimination(program).execImpl(program);
897: }
898:
899: public static boolean exec(JProgram program, JNode node) {
900: return new DeadCodeElimination(program).execImpl(node);
901: }
902:
903: private final JProgram program;
904:
905: private final Map<JType, Class<?>> typeClassMap = new IdentityHashMap<JType, Class<?>>();
906:
907: public DeadCodeElimination(JProgram program) {
908: this .program = program;
909: typeClassMap.put(program.getTypeJavaLangObject(), Object.class);
910: typeClassMap.put(program.getTypeJavaLangString(), String.class);
911: typeClassMap.put(program.getTypePrimitiveBoolean(),
912: boolean.class);
913: typeClassMap.put(program.getTypePrimitiveByte(), byte.class);
914: typeClassMap.put(program.getTypePrimitiveChar(), char.class);
915: typeClassMap
916: .put(program.getTypePrimitiveDouble(), double.class);
917: typeClassMap.put(program.getTypePrimitiveFloat(), float.class);
918: typeClassMap.put(program.getTypePrimitiveInt(), int.class);
919: typeClassMap.put(program.getTypePrimitiveLong(), long.class);
920: typeClassMap.put(program.getTypePrimitiveShort(), short.class);
921: }
922:
923: private boolean execImpl(JNode node) {
924: boolean madeChanges = false;
925: while (true) {
926: DeadCodeVisitor deadCodeVisitor = new DeadCodeVisitor();
927: deadCodeVisitor.accept(node);
928: if (!deadCodeVisitor.didChange()) {
929: break;
930: }
931: madeChanges = true;
932: }
933: return madeChanges;
934: }
935: }
|