| /* |
| * Copyright 2008 Google Inc. |
| * |
| * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT |
| * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the |
| * License for the specific language governing permissions and limitations under |
| * the License. |
| */ |
| package com.google.gwt.dev.jjs.impl; |
| |
| import com.google.gwt.dev.jjs.SourceInfo; |
| import com.google.gwt.dev.jjs.ast.Context; |
| import com.google.gwt.dev.jjs.ast.JBinaryOperation; |
| import com.google.gwt.dev.jjs.ast.JBinaryOperator; |
| import com.google.gwt.dev.jjs.ast.JBlock; |
| import com.google.gwt.dev.jjs.ast.JBooleanLiteral; |
| import com.google.gwt.dev.jjs.ast.JBreakStatement; |
| import com.google.gwt.dev.jjs.ast.JCaseStatement; |
| import com.google.gwt.dev.jjs.ast.JCastOperation; |
| import com.google.gwt.dev.jjs.ast.JCharLiteral; |
| import com.google.gwt.dev.jjs.ast.JClassType; |
| import com.google.gwt.dev.jjs.ast.JConditional; |
| import com.google.gwt.dev.jjs.ast.JContinueStatement; |
| import com.google.gwt.dev.jjs.ast.JDeclarationStatement; |
| import com.google.gwt.dev.jjs.ast.JDeclaredType; |
| import com.google.gwt.dev.jjs.ast.JDoStatement; |
| import com.google.gwt.dev.jjs.ast.JDoubleLiteral; |
| import com.google.gwt.dev.jjs.ast.JExpression; |
| import com.google.gwt.dev.jjs.ast.JExpressionStatement; |
| import com.google.gwt.dev.jjs.ast.JFieldRef; |
| import com.google.gwt.dev.jjs.ast.JForStatement; |
| import com.google.gwt.dev.jjs.ast.JIfStatement; |
| import com.google.gwt.dev.jjs.ast.JIntLiteral; |
| import com.google.gwt.dev.jjs.ast.JLiteral; |
| import com.google.gwt.dev.jjs.ast.JLocalRef; |
| import com.google.gwt.dev.jjs.ast.JLongLiteral; |
| import com.google.gwt.dev.jjs.ast.JMethod; |
| import com.google.gwt.dev.jjs.ast.JMethodCall; |
| import com.google.gwt.dev.jjs.ast.JModVisitor; |
| import com.google.gwt.dev.jjs.ast.JNewInstance; |
| import com.google.gwt.dev.jjs.ast.JNode; |
| import com.google.gwt.dev.jjs.ast.JParameterRef; |
| import com.google.gwt.dev.jjs.ast.JPostfixOperation; |
| import com.google.gwt.dev.jjs.ast.JPrefixOperation; |
| import com.google.gwt.dev.jjs.ast.JPrimitiveType; |
| import com.google.gwt.dev.jjs.ast.JProgram; |
| import com.google.gwt.dev.jjs.ast.JReferenceType; |
| import com.google.gwt.dev.jjs.ast.JStatement; |
| import com.google.gwt.dev.jjs.ast.JStringLiteral; |
| import com.google.gwt.dev.jjs.ast.JSwitchStatement; |
| import com.google.gwt.dev.jjs.ast.JTryStatement; |
| import com.google.gwt.dev.jjs.ast.JType; |
| import com.google.gwt.dev.jjs.ast.JUnaryOperator; |
| import com.google.gwt.dev.jjs.ast.JValueLiteral; |
| import com.google.gwt.dev.jjs.ast.JVariableRef; |
| import com.google.gwt.dev.jjs.ast.JVisitor; |
| import com.google.gwt.dev.jjs.ast.JWhileStatement; |
| import com.google.gwt.dev.jjs.ast.js.JMultiExpression; |
| import com.google.gwt.dev.util.log.speedtracer.CompilerEventType; |
| import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger; |
| import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger.Event; |
| |
| import java.lang.reflect.Method; |
| import java.util.ArrayList; |
| import java.util.HashSet; |
| import java.util.IdentityHashMap; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.Map; |
| import java.util.Set; |
| |
| /** |
| * Removes certain kinds of dead code, and simplifies certain expressions. This |
| * pass focuses on intraprocedural optimizations, that is, optimizations that |
| * can be performed inside of a single method body (and usually a single |
| * expression) rather than global transformations. Global optimizations done in |
| * other passes will feed into this, however. |
| */ |
| public class DeadCodeElimination { |
| /** |
| * Eliminates dead or unreachable code when possible, and makes local |
| * simplifications like changing "<code>x || true</code>" to "<code>x</code>". |
| * |
| * This visitor should perform all of its optimizations in a single pass. |
| * Except in rare cases, running this pass multiple times should produce no |
| * changes after the first pass. The only currently known exception to this |
| * rule is in {@link #endVisit(JNewInstance, Context)}, where the target |
| * constructor may be non-empty at the beginning of DCE and become empty |
| * during the run, which potentially unlocks optimizations at call sites. |
| * |
| * TODO: leverage ignoring expression output more to remove intermediary |
| * operations in favor of pure side effects. |
| * |
| * TODO: move more simplifications into methods like |
| * {@link #cast(JExpression, SourceInfo, JType, JExpression) simplifyCast}, so |
| * that more simplifications can be made on a single pass through a tree. |
| */ |
| public class DeadCodeVisitor extends JModVisitor { |
| private JMethod currentMethod = null; |
| |
| /** |
| * Expressions whose result does not matter. A parent node should add any |
| * children whose result does not matter to this set during the parent's |
| * <code>visit()</code> method. It should then remove those children during |
| * its own <code>endVisit()</code>. |
| * |
| * TODO: there's a latent bug here: some immutable nodes (such as literals) |
| * can be multiply referenced in the AST. In theory, one reference to that |
| * node could be put into this set while another reference actually contains |
| * a result that is needed. In practice this is okay at the moment since the |
| * existing uses of <code>ignoringExpressionOutput</code> are with mutable |
| * nodes. |
| */ |
| private final Set<JExpression> ignoringExpressionOutput = new HashSet<JExpression>(); |
| |
| private final JMethod isScriptMethod = program.getIndexedMethod("GWT.isScript"); |
| |
| /** |
| * Expressions being used as lvalues. |
| */ |
| private final Set<JExpression> lvalues = new HashSet<JExpression>(); |
| |
| private final Set<JBlock> switchBlocks = new HashSet<JBlock>(); |
| |
| /** |
| * Short circuit binary operations. |
| */ |
| @Override |
| public void endVisit(JBinaryOperation x, Context ctx) { |
| JBinaryOperator op = x.getOp(); |
| JExpression lhs = x.getLhs(); |
| JExpression rhs = x.getRhs(); |
| if ((lhs instanceof JValueLiteral) && (rhs instanceof JValueLiteral)) { |
| if (evalOpOnLiterals(op, (JValueLiteral) lhs, (JValueLiteral) rhs, ctx)) { |
| return; |
| } |
| } |
| switch (op) { |
| case AND: |
| maybeReplaceMe(x, simplifier.shortCircuitAnd(x, null, lhs, rhs), ctx); |
| break; |
| case OR: |
| maybeReplaceMe(x, simplifier.shortCircuitOr(x, null, lhs, rhs), ctx); |
| break; |
| case BIT_XOR: |
| simplifyXor(lhs, rhs, ctx); |
| break; |
| case EQ: |
| // simplify: null == null -> true |
| if (lhs.getType() == program.getTypeNull() && rhs.getType() == program.getTypeNull() |
| && !x.hasSideEffects()) { |
| ctx.replaceMe(program.getLiteralBoolean(true)); |
| return; |
| } |
| simplifyEq(lhs, rhs, ctx, false); |
| break; |
| case NEQ: |
| // simplify: null != null -> false |
| if (lhs.getType() == program.getTypeNull() && rhs.getType() == program.getTypeNull() |
| && !x.hasSideEffects()) { |
| ctx.replaceMe(program.getLiteralBoolean(false)); |
| return; |
| } |
| simplifyEq(lhs, rhs, ctx, true); |
| break; |
| case ADD: |
| simplifyAdd(lhs, rhs, ctx, x.getType()); |
| break; |
| case CONCAT: |
| evalConcat(x.getSourceInfo(), lhs, rhs, ctx); |
| break; |
| case SUB: |
| simplifySub(lhs, rhs, ctx, x.getType()); |
| break; |
| case MUL: |
| simplifyMul(lhs, rhs, ctx, x.getType()); |
| break; |
| case DIV: |
| simplifyDiv(lhs, rhs, ctx, x.getType()); |
| break; |
| case SHL: |
| case SHR: |
| case SHRU: |
| if (isLiteralZero(rhs)) { |
| ctx.replaceMe(lhs); |
| } |
| break; |
| default: |
| if (op.isAssignment()) { |
| lvalues.remove(lhs); |
| } |
| break; |
| } |
| } |
| |
| /** |
| * Prune dead statements and empty blocks. |
| */ |
| @Override |
| public void endVisit(JBlock x, Context ctx) { |
| // Switch blocks require special optimization code |
| if (switchBlocks.contains(x)) { |
| return; |
| } |
| |
| /* |
| * Remove any dead statements after an abrupt change in code flow and |
| * promote safe statements within nested blocks to this block. |
| */ |
| for (int i = 0; i < x.getStatements().size(); i++) { |
| JStatement stmt = x.getStatements().get(i); |
| |
| if (stmt instanceof JBlock) { |
| /* |
| * Promote a sub-block's children to the current block, unless the |
| * sub-block contains local declarations as children. |
| */ |
| JBlock block = (JBlock) stmt; |
| if (canPromoteBlock(block)) { |
| x.removeStmt(i); |
| x.addStmts(i, block.getStatements()); |
| i--; |
| madeChanges(); |
| continue; |
| } |
| } |
| |
| if (stmt instanceof JExpressionStatement) { |
| JExpressionStatement stmtExpr = (JExpressionStatement) stmt; |
| if (stmtExpr.getExpr() instanceof JMultiExpression) { |
| // Promote a multi's expressions to the current block |
| x.removeStmt(i); |
| int start = i; |
| JMultiExpression multi = ((JMultiExpression) stmtExpr.getExpr()); |
| for (JExpression expr : multi.exprs) { |
| x.addStmt(i++, expr.makeStatement()); |
| } |
| i = start - 1; |
| continue; |
| } |
| } |
| |
| if (stmt.unconditionalControlBreak()) { |
| // Abrupt change in flow, chop the remaining items from this block |
| for (int j = i + 1; j < x.getStatements().size();) { |
| x.removeStmt(j); |
| madeChanges(); |
| } |
| } |
| } |
| |
| if (ctx.canRemove() && x.getStatements().size() == 0) { |
| // Remove blocks with no effect |
| ctx.removeMe(); |
| } |
| } |
| |
| @Override |
| public void endVisit(JCastOperation x, Context ctx) { |
| maybeReplaceMe(x, simplifier.cast(x, x.getSourceInfo(), x.getCastType(), x.getExpr()), ctx); |
| } |
| |
| @Override |
| public void endVisit(JConditional x, Context ctx) { |
| maybeReplaceMe(x, simplifier.conditional(x, x.getSourceInfo(), x.getType(), x.getIfTest(), x |
| .getThenExpr(), x.getElseExpr()), ctx); |
| } |
| |
| @Override |
| public void endVisit(JDeclarationStatement x, Context ctx) { |
| JVariableRef variableRef = x.getVariableRef(); |
| lvalues.remove(variableRef); |
| } |
| |
| /** |
| * Convert do { } while (false); into a block. |
| */ |
| @Override |
| public void endVisit(JDoStatement x, Context ctx) { |
| JExpression expression = x.getTestExpr(); |
| if (expression instanceof JBooleanLiteral) { |
| JBooleanLiteral booleanLiteral = (JBooleanLiteral) expression; |
| |
| // If false, replace do with do's body |
| if (!booleanLiteral.getValue()) { |
| if (Simplifier.isEmpty(x.getBody())) { |
| ctx.removeMe(); |
| } else { // Unless it contains break/continue statements |
| FindBreakContinueStatementsVisitor visitor = new FindBreakContinueStatementsVisitor(); |
| visitor.accept(x.getBody()); |
| if (!visitor.hasBreakContinueStatements()) { |
| ctx.replaceMe(x.getBody()); |
| } |
| } |
| } |
| } |
| } |
| |
| @Override |
| public void endVisit(JExpressionStatement x, Context ctx) { |
| ignoringExpressionOutput.remove(x.getExpr()); |
| if (!x.getExpr().hasSideEffects()) { |
| removeMe(x, ctx); |
| } |
| } |
| |
| @Override |
| public void endVisit(JFieldRef x, Context ctx) { |
| JLiteral literal = tryGetConstant(x); |
| if (literal == null && !ignoringExpressionOutput.contains(x)) { |
| return; |
| } |
| /* |
| * At this point, either we have a constant replacement, or our value is |
| * irrelevant. We can inline the constant, if any, but we might also need |
| * to evaluate an instance and run a clinit. |
| */ |
| // We can inline the constant, but we might also need to evaluate an |
| // instance and run a clinit. |
| JMultiExpression multi = new JMultiExpression(x.getSourceInfo()); |
| |
| JExpression instance = x.getInstance(); |
| if (instance != null) { |
| multi.exprs.add(instance); |
| } |
| |
| if (x.hasClinit()) { |
| multi.exprs.add(createClinitCall(x.getSourceInfo(), x.getField().getEnclosingType())); |
| } |
| |
| if (literal != null) { |
| multi.exprs.add(literal); |
| } |
| |
| ctx.replaceMe(this.accept(multi)); |
| } |
| |
| /** |
| * Prune for (X; false; Y) statements, but make sure X is run. |
| */ |
| @Override |
| public void endVisit(JForStatement x, Context ctx) { |
| JExpression expression = x.getTestExpr(); |
| if (expression instanceof JBooleanLiteral) { |
| JBooleanLiteral booleanLiteral = (JBooleanLiteral) expression; |
| |
| // If false, replace the for statement with its initializers |
| if (!booleanLiteral.getValue()) { |
| JBlock block = new JBlock(x.getSourceInfo()); |
| block.addStmts(x.getInitializers()); |
| replaceMe(block, ctx); |
| } |
| } |
| } |
| |
| /** |
| * Simplify if statements. |
| */ |
| @Override |
| public void endVisit(JIfStatement x, Context ctx) { |
| maybeReplaceMe(x, simplifier.ifStatement(x, x.getSourceInfo(), x.getIfExpr(), |
| x.getThenStmt(), x.getElseStmt(), currentMethod), ctx); |
| } |
| |
| @Override |
| public void endVisit(JLocalRef x, Context ctx) { |
| JLiteral literal = tryGetConstant(x); |
| if (literal != null) { |
| assert (!x.hasSideEffects()); |
| ctx.replaceMe(literal); |
| } |
| } |
| |
| @Override |
| public void endVisit(JMethod x, Context ctx) { |
| currentMethod = null; |
| } |
| |
| /** |
| * Resolve method calls that can be computed statically. |
| */ |
| @Override |
| public void endVisit(JMethodCall x, Context ctx) { |
| // Restore ignored expressions. |
| JMethod target = x.getTarget(); |
| if (target.isStatic() && x.getInstance() != null) { |
| ignoringExpressionOutput.remove(x.getInstance()); |
| } |
| |
| int paramCount = target.getParams().size(); |
| for (int i = paramCount; i < x.getArgs().size(); ++i) { |
| JExpression arg = x.getArgs().get(i); |
| ignoringExpressionOutput.remove(arg); |
| if (!arg.hasSideEffects()) { |
| x.removeArg(i--); |
| madeChanges(); |
| } |
| } |
| |
| // Normal optimizations. |
| JDeclaredType targetType = target.getEnclosingType(); |
| if (targetType == program.getTypeJavaLangString()) { |
| tryOptimizeStringCall(x, ctx, target); |
| } else if (JProgram.isClinit(target)) { |
| // Eliminate the call if the target is now empty. |
| if (!targetType.hasClinit()) { |
| ctx.replaceMe(program.getLiteralNull()); |
| } else if (targetType != targetType.getClinitTarget()) { |
| // Tighten the target. |
| ctx.replaceMe(createClinitCall(x.getSourceInfo(), targetType.getClinitTarget())); |
| } |
| } else if (target == isScriptMethod) { |
| // optimize out in draftCompiles that don't do inlining |
| ctx.replaceMe(JBooleanLiteral.TRUE); |
| } |
| } |
| |
| /** |
| * Remove any parts of JMultiExpression that have no side-effect. |
| */ |
| @Override |
| public void endVisit(JMultiExpression x, Context ctx) { |
| List<JExpression> exprs = x.exprs; |
| if (exprs.size() > 0) { |
| if (ignoringExpressionOutput.contains(x)) { |
| // Remove all my children we previously added. |
| ignoringExpressionOutput.removeAll(exprs); |
| } else { |
| // Remove the non-final children we previously added. |
| List<JExpression> nonFinalChildren = exprs.subList(0, exprs.size() - 1); |
| ignoringExpressionOutput.removeAll(nonFinalChildren); |
| } |
| } |
| |
| for (int i = 0; i < numRemovableExpressions(x); ++i) { |
| JExpression expr = x.exprs.get(i); |
| if (!expr.hasSideEffects()) { |
| x.exprs.remove(i); |
| --i; |
| madeChanges(); |
| continue; |
| } |
| |
| // Remove nested JMultiExpressions |
| if (expr instanceof JMultiExpression) { |
| x.exprs.remove(i); |
| x.exprs.addAll(i, ((JMultiExpression) expr).exprs); |
| i--; |
| madeChanges(); |
| continue; |
| } |
| } |
| |
| if (x.exprs.size() == 1) { |
| maybeReplaceMe(x, x.exprs.get(0), ctx); |
| } |
| } |
| |
| @Override |
| public void endVisit(JNewInstance x, Context ctx) { |
| super.endVisit(x, ctx); |
| /* |
| * If the result of a new operation is ignored, we can remove it, provided |
| * / it has no side effects. |
| */ |
| if (ignoringExpressionOutput.contains(x)) { |
| if (!x.getTarget().isEmpty()) { |
| return; |
| } |
| JMultiExpression multi = new JMultiExpression(x.getSourceInfo()); |
| multi.exprs.addAll(x.getArgs()); |
| if (x.hasClinit()) { |
| multi.exprs.add(createClinitCall(x.getSourceInfo(), x.getTarget().getEnclosingType())); |
| } |
| ignoringExpressionOutput.add(multi); |
| ctx.replaceMe(this.accept(multi)); |
| ignoringExpressionOutput.remove(multi); |
| } |
| } |
| |
| @Override |
| public void endVisit(JParameterRef x, Context ctx) { |
| JLiteral literal = tryGetConstant(x); |
| if (literal != null) { |
| assert (!x.hasSideEffects()); |
| ctx.replaceMe(literal); |
| } |
| } |
| |
| /** |
| * Replace post-inc/dec with pre-inc/dec if the result doesn't matter. |
| */ |
| @Override |
| public void endVisit(JPostfixOperation x, Context ctx) { |
| if (x.getOp().isModifying()) { |
| lvalues.remove(x.getArg()); |
| } |
| if (ignoringExpressionOutput.contains(x)) { |
| JPrefixOperation newOp = new JPrefixOperation(x.getSourceInfo(), x.getOp(), x.getArg()); |
| ctx.replaceMe(newOp); |
| } |
| } |
| |
| /** |
| * Simplify the ! operator if possible. |
| */ |
| @Override |
| public void endVisit(JPrefixOperation x, Context ctx) { |
| if (x.getOp().isModifying()) { |
| lvalues.remove(x.getArg()); |
| } |
| if (x.getArg() instanceof JValueLiteral) { |
| if (evalOpOnLiteral(x.getOp(), (JValueLiteral) x.getArg(), ctx)) { |
| return; |
| } |
| } |
| if (x.getOp() == JUnaryOperator.NOT) { |
| maybeReplaceMe(x, simplifier.not(x, x.getSourceInfo(), x.getArg()), ctx); |
| return; |
| } else if (x.getOp() == JUnaryOperator.NEG) { |
| maybeReplaceMe(x, simplifyNegate(x, x.getArg()), ctx); |
| } |
| } |
| |
| /** |
| * Optimize switch statements. |
| */ |
| @Override |
| public void endVisit(JSwitchStatement x, Context ctx) { |
| switchBlocks.remove(x.getBody()); |
| |
| if (hasNoDefaultCase(x)) { |
| removeEmptyCases(x); |
| } |
| removeDoubleBreaks(x); |
| tryRemoveSwitch(x, ctx); |
| } |
| |
| /** |
| * 1) Remove catch blocks whose exception type is not instantiable. 2) Prune |
| * try statements with no body. 3) Hoist up try statements with no catches |
| * and an empty finally. |
| */ |
| @Override |
| public void endVisit(JTryStatement x, Context ctx) { |
| // 1) Remove catch blocks whose exception type is not instantiable. |
| List<JLocalRef> catchArgs = x.getCatchArgs(); |
| List<JBlock> catchBlocks = x.getCatchBlocks(); |
| Iterator<JLocalRef> itA = catchArgs.iterator(); |
| Iterator<JBlock> itB = catchBlocks.iterator(); |
| while (itA.hasNext()) { |
| JLocalRef localRef = itA.next(); |
| itB.next(); |
| JReferenceType type = (JReferenceType) localRef.getType(); |
| if (!program.typeOracle.isInstantiatedType(type) || type == program.getTypeNull()) { |
| itA.remove(); |
| itB.remove(); |
| madeChanges(); |
| } |
| } |
| |
| // Compute properties regarding the state of this try statement |
| boolean noTry = Simplifier.isEmpty(x.getTryBlock()); |
| boolean noCatch = catchArgs.size() == 0; |
| boolean noFinally = Simplifier.isEmpty(x.getFinallyBlock()); |
| |
| if (noTry) { |
| // 2) Prune try statements with no body. |
| if (noFinally) { |
| // if there's no finally, prune the whole thing |
| removeMe(x, ctx); |
| } else { |
| // replace the try statement with just the contents of the finally |
| replaceMe(x.getFinallyBlock(), ctx); |
| } |
| } else if (noCatch && noFinally) { |
| // 3) Hoist up try statements with no catches and an empty finally. |
| // If there's no catch or finally, there's no point in this even being |
| // a try statement, replace myself with the try block |
| replaceMe(x.getTryBlock(), ctx); |
| } |
| } |
| |
| /** |
| * Prune while (false) statements. |
| */ |
| @Override |
| public void endVisit(JWhileStatement x, Context ctx) { |
| JExpression expression = x.getTestExpr(); |
| if (expression instanceof JBooleanLiteral) { |
| JBooleanLiteral booleanLiteral = (JBooleanLiteral) expression; |
| |
| // If false, prune the while statement |
| if (!booleanLiteral.getValue()) { |
| removeMe(x, ctx); |
| } |
| } |
| } |
| |
| @Override |
| public boolean visit(JBinaryOperation x, Context ctx) { |
| if (x.getOp().isAssignment()) { |
| lvalues.add(x.getLhs()); |
| } |
| return true; |
| } |
| |
| @Override |
| public boolean visit(JClassType x, Context ctx) { |
| // We can't eliminate code from an external type |
| return !x.isExternal(); |
| } |
| |
| @Override |
| public boolean visit(JDeclarationStatement x, Context ctx) { |
| lvalues.add(x.getVariableRef()); |
| return true; |
| } |
| |
| @Override |
| public boolean visit(JExpressionStatement x, Context ctx) { |
| ignoringExpressionOutput.add(x.getExpr()); |
| return true; |
| } |
| |
| @Override |
| public boolean visit(JMethod x, Context ctx) { |
| currentMethod = x; |
| return true; |
| } |
| |
| @Override |
| public boolean visit(JMethodCall x, Context ctx) { |
| JMethod target = x.getTarget(); |
| if (target.isStatic() && x.getInstance() != null) { |
| ignoringExpressionOutput.add(x.getInstance()); |
| } |
| List<JExpression> args = x.getArgs(); |
| List<JExpression> ignoredArgs = args.subList(target.getParams().size(), args.size()); |
| ignoringExpressionOutput.addAll(ignoredArgs); |
| return true; |
| } |
| |
| @Override |
| public boolean visit(JMultiExpression x, Context ctx) { |
| List<JExpression> exprs = x.exprs; |
| if (exprs.size() > 0) { |
| if (ignoringExpressionOutput.contains(x)) { |
| // None of my children matter. |
| ignoringExpressionOutput.addAll(exprs); |
| } else { |
| // Only my final child matters. |
| List<JExpression> nonFinalChildren = exprs.subList(0, exprs.size() - 1); |
| ignoringExpressionOutput.addAll(nonFinalChildren); |
| } |
| } |
| return true; |
| } |
| |
| @Override |
| public boolean visit(JPostfixOperation x, Context ctx) { |
| if (x.getOp().isModifying()) { |
| lvalues.add(x.getArg()); |
| } |
| return true; |
| } |
| |
| @Override |
| public boolean visit(JPrefixOperation x, Context ctx) { |
| if (x.getOp().isModifying()) { |
| lvalues.add(x.getArg()); |
| } |
| return true; |
| } |
| |
| @Override |
| public boolean visit(JSwitchStatement x, Context ctx) { |
| switchBlocks.add(x.getBody()); |
| return true; |
| } |
| |
| /** |
| * Returns true if a block can be merged into its parent block. This is true |
| * when the block contains no local declarations. |
| */ |
| private boolean canPromoteBlock(JBlock block) { |
| for (JStatement nestedStmt : block.getStatements()) { |
| if (nestedStmt instanceof JDeclarationStatement) { |
| JDeclarationStatement decl = (JDeclarationStatement) nestedStmt; |
| if (decl.getVariableRef() instanceof JLocalRef) { |
| return false; |
| } |
| } |
| } |
| return true; |
| } |
| |
| private JMethodCall createClinitCall(SourceInfo sourceInfo, JDeclaredType targetType) { |
| JMethod clinit = targetType.getClinitTarget().getMethods().get(0); |
| assert (JProgram.isClinit(clinit)); |
| return new JMethodCall(sourceInfo, null, clinit); |
| } |
| |
| private void evalConcat(SourceInfo info, JExpression lhs, JExpression rhs, Context ctx) { |
| if (lhs instanceof JValueLiteral && rhs instanceof JValueLiteral) { |
| Object lhsObj = ((JValueLiteral) lhs).getValueObj(); |
| Object rhsObj = ((JValueLiteral) rhs).getValueObj(); |
| ctx.replaceMe(program.getLiteralString(info, String.valueOf(lhsObj) |
| + String.valueOf(rhsObj))); |
| } |
| } |
| |
| /** |
| * Evaluate <code>lhs == rhs</code>. |
| * |
| * @param lhs Any literal other than null. |
| * @param rhs Any literal other than null. |
| * @return Whether <code>lhs == rhs</code> will evaluate to |
| * <code>true</code> at run time. |
| */ |
| private boolean evalEq(JValueLiteral lhs, JValueLiteral rhs) { |
| if (isTypeBoolean(lhs)) { |
| return toBoolean(lhs) == toBoolean(rhs); |
| } |
| if (isTypeDouble(lhs) || isTypeDouble(rhs)) { |
| return toDouble(lhs) == toDouble(rhs); |
| } |
| if (isTypeFloat(lhs) || isTypeFloat(rhs)) { |
| return toFloat(lhs) == toFloat(rhs); |
| } |
| if (isTypeLong(lhs) || isTypeLong(rhs)) { |
| return toLong(lhs) == toLong(rhs); |
| } |
| return toInt(lhs) == toInt(rhs); |
| } |
| |
| /** |
| * Static evaluation of a unary operation on a literal. |
| * |
| * @return Whether a change was made |
| */ |
| private boolean evalOpOnLiteral(JUnaryOperator op, JValueLiteral exp, Context ctx) { |
| switch (op) { |
| case BIT_NOT: { |
| long value = toLong(exp); |
| long res = ~value; |
| if (isTypeLong(exp)) { |
| ctx.replaceMe(program.getLiteralLong(res)); |
| } else { |
| ctx.replaceMe(program.getLiteralInt((int) res)); |
| } |
| return true; |
| } |
| |
| case NEG: |
| if (isTypeLong(exp)) { |
| ctx.replaceMe(program.getLiteralLong(-toLong(exp))); |
| return true; |
| } |
| if (isTypeIntegral(exp)) { |
| ctx.replaceMe(program.getLiteralInt(-toInt(exp))); |
| return true; |
| } |
| if (isTypeDouble(exp)) { |
| ctx.replaceMe(program.getLiteralDouble(-toDouble(exp))); |
| return true; |
| } |
| if (isTypeFloat(exp)) { |
| ctx.replaceMe(program.getLiteralFloat(-toFloat(exp))); |
| return true; |
| } |
| return false; |
| |
| case NOT: { |
| JBooleanLiteral booleanLit = (JBooleanLiteral) exp; |
| ctx.replaceMe(program.getLiteralBoolean(!booleanLit.getValue())); |
| return true; |
| } |
| |
| default: |
| return false; |
| } |
| } |
| |
| /** |
| * Static evaluation of a binary operation on two literals. |
| * |
| * @return Whether a change was made |
| */ |
| private boolean evalOpOnLiterals(JBinaryOperator op, JValueLiteral lhs, JValueLiteral rhs, |
| Context ctx) { |
| if (isTypeString(lhs) || isTypeString(rhs) || isTypeNull(lhs) || isTypeNull(rhs)) { |
| // String simplifications are handled elsewhere. |
| // Null can only be used with String append, and with |
| // comparison with EQ and NEQ, and those simplifications |
| // are also handled elsewhere. |
| return false; |
| } |
| switch (op) { |
| case EQ: { |
| ctx.replaceMe(program.getLiteralBoolean(evalEq(lhs, rhs))); |
| return true; |
| } |
| |
| case NEQ: { |
| ctx.replaceMe(program.getLiteralBoolean(!evalEq(lhs, rhs))); |
| return true; |
| } |
| |
| case ADD: |
| case SUB: |
| case MUL: |
| case DIV: |
| case MOD: { |
| if (isTypeDouble(lhs) || isTypeFloat(lhs) || isTypeDouble(rhs) || isTypeFloat(rhs)) { |
| // do the op on doubles and cast back |
| double left = toDouble(lhs); |
| double right = toDouble(rhs); |
| double res; |
| switch (op) { |
| case ADD: |
| res = left + right; |
| break; |
| case SUB: |
| res = left - right; |
| break; |
| case MUL: |
| res = left * right; |
| break; |
| case DIV: |
| res = left / right; |
| break; |
| case MOD: |
| res = left % right; |
| break; |
| default: |
| assert false; |
| return false; |
| } |
| if (isTypeDouble(lhs) || isTypeDouble(rhs)) { |
| ctx.replaceMe(program.getLiteralDouble(res)); |
| } else { |
| ctx.replaceMe(program.getLiteralFloat((float) res)); |
| } |
| return true; |
| } else { |
| // do the op on longs and cast to the correct |
| // result type at the end |
| long left = toLong(lhs); |
| long right = toLong(rhs); |
| |
| long res; |
| switch (op) { |
| case ADD: |
| res = left + right; |
| break; |
| case SUB: |
| res = left - right; |
| break; |
| case MUL: |
| res = left * right; |
| break; |
| case DIV: |
| if (right == 0) { |
| // Don't divide by zero |
| return false; |
| } |
| res = left / right; |
| break; |
| case MOD: |
| if (right == 0) { |
| // Don't divide by zero |
| return false; |
| } |
| res = left % right; |
| break; |
| default: |
| assert false; |
| return false; |
| } |
| if (isTypeLong(lhs) || isTypeLong(rhs)) { |
| ctx.replaceMe(program.getLiteralLong(res)); |
| } else { |
| ctx.replaceMe(program.getLiteralInt((int) res)); |
| } |
| return true; |
| } |
| } |
| |
| case LT: |
| case LTE: |
| case GT: |
| case GTE: { |
| if (isTypeDouble(lhs) || isTypeDouble(rhs) || isTypeFloat(lhs) || isTypeFloat(rhs)) { |
| // operate on doubles |
| double left = toDouble(lhs); |
| double right = toDouble(rhs); |
| boolean res; |
| switch (op) { |
| case LT: |
| res = left < right; |
| break; |
| case LTE: |
| res = left <= right; |
| break; |
| case GT: |
| res = left > right; |
| break; |
| case GTE: |
| res = left >= right; |
| break; |
| default: |
| assert false; |
| return false; |
| } |
| ctx.replaceMe(program.getLiteralBoolean(res)); |
| return true; |
| } else { |
| // operate on longs |
| long left = toLong(lhs); |
| long right = toLong(rhs); |
| boolean res; |
| switch (op) { |
| case LT: |
| res = left < right; |
| break; |
| case LTE: |
| res = left <= right; |
| break; |
| case GT: |
| res = left > right; |
| break; |
| case GTE: |
| res = left >= right; |
| break; |
| default: |
| assert false; |
| return false; |
| } |
| ctx.replaceMe(program.getLiteralBoolean(res)); |
| return true; |
| } |
| } |
| |
| case BIT_AND: |
| case BIT_OR: |
| case BIT_XOR: |
| if (isTypeBoolean(lhs)) { |
| // TODO: maybe eval non-short-circuit boolean operators. |
| return false; |
| } else { |
| // operate on longs and then cast down |
| long left = toLong(lhs); |
| long right = toLong(rhs); |
| long res; |
| switch (op) { |
| case BIT_AND: |
| res = left & right; |
| break; |
| |
| case BIT_OR: |
| res = left | right; |
| break; |
| |
| case BIT_XOR: |
| res = left ^ right; |
| break; |
| |
| default: |
| assert false; |
| return false; |
| } |
| if (isTypeLong(lhs) || isTypeLong(rhs)) { |
| ctx.replaceMe(program.getLiteralLong(res)); |
| } else { |
| ctx.replaceMe(program.getLiteralInt((int) res)); |
| } |
| return true; |
| } |
| |
| case SHL: |
| case SHR: |
| case SHRU: { |
| if (isTypeLong(lhs)) { |
| long left = toLong(lhs); |
| int right = toInt(rhs); |
| long res; |
| switch (op) { |
| case SHL: |
| res = left << right; |
| break; |
| |
| case SHR: |
| res = left >> right; |
| break; |
| |
| case SHRU: |
| res = left >>> right; |
| break; |
| |
| default: |
| assert false; |
| return false; |
| } |
| |
| ctx.replaceMe(program.getLiteralLong(res)); |
| return true; |
| } else { |
| int left = toInt(lhs); |
| int right = toInt(rhs); |
| int res; |
| switch (op) { |
| case SHL: |
| res = left << right; |
| break; |
| |
| case SHR: |
| res = left >> right; |
| break; |
| |
| case SHRU: |
| res = left >>> right; |
| break; |
| |
| default: |
| assert false; |
| return false; |
| } |
| |
| ctx.replaceMe(program.getLiteralInt(res)); |
| return true; |
| } |
| } |
| |
| default: |
| return false; |
| } |
| } |
| |
| /** |
| * If the effect of <code>statement</code> is to immediately do a break, |
| * then return the {@link JBreakStatement} corresponding to that break. |
| */ |
| private JBreakStatement findUnconditionalBreak(JStatement statement) { |
| if (statement instanceof JBreakStatement) { |
| return (JBreakStatement) statement; |
| } else if (statement instanceof JBlock) { |
| JBlock block = (JBlock) statement; |
| List<JStatement> blockStmts = block.getStatements(); |
| if (blockStmts.size() > 0 && isUnconditionalBreak(blockStmts.get(0))) { |
| return (JBreakStatement) blockStmts.get(0); |
| } |
| } |
| return null; |
| } |
| |
| private boolean hasNoDefaultCase(JSwitchStatement x) { |
| JBlock body = x.getBody(); |
| boolean inDefault = false; |
| for (JStatement statement : body.getStatements()) { |
| if (statement instanceof JCaseStatement) { |
| JCaseStatement caseStmt = (JCaseStatement) statement; |
| if (caseStmt.getExpr() == null) { |
| inDefault = true; |
| } |
| } else if (isUnconditionalUnlabeledBreak(statement)) { |
| inDefault = false; |
| } else { |
| // We have some code to execute other than a break. |
| if (inDefault) { |
| // We have a default case with real code. |
| return false; |
| } |
| } |
| } |
| // We found no default case that wasn't empty. |
| return true; |
| } |
| |
| private boolean isLiteralNegativeOne(JExpression exp) { |
| if (exp instanceof JValueLiteral) { |
| JValueLiteral lit = (JValueLiteral) exp; |
| if (isTypeIntegral(lit)) { |
| if (toLong(lit) == -1) { |
| return true; |
| } |
| } |
| if (isTypeFloatOrDouble(lit)) { |
| if (toDouble(lit) == -1.0) { |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| private boolean isLiteralOne(JExpression exp) { |
| if (exp instanceof JValueLiteral) { |
| JValueLiteral lit = (JValueLiteral) exp; |
| if (isTypeIntegral(lit)) { |
| if (toLong(lit) == 1) { |
| return true; |
| } |
| } |
| if (isTypeFloatOrDouble(lit)) { |
| if (toDouble(lit) == 1.0) { |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| private boolean isLiteralZero(JExpression exp) { |
| if (exp instanceof JValueLiteral) { |
| JValueLiteral lit = (JValueLiteral) exp; |
| if (toDouble(lit) == 0.0) { |
| // Using toDouble only is safe even for integer types. All types but |
| // long will keep full precision. Longs will lose precision, but |
| // it will not affect whether the resulting double is zero or not. |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| private boolean isTypeBoolean(JExpression lhs) { |
| return lhs.getType() == program.getTypePrimitiveBoolean(); |
| } |
| |
| private boolean isTypeDouble(JExpression exp) { |
| return isTypeDouble(exp.getType()); |
| } |
| |
| private boolean isTypeDouble(JType type) { |
| return type == program.getTypePrimitiveDouble(); |
| } |
| |
| private boolean isTypeFloat(JExpression exp) { |
| return isTypeFloat(exp.getType()); |
| } |
| |
| private boolean isTypeFloat(JType type) { |
| return type == program.getTypePrimitiveFloat(); |
| } |
| |
| /** |
| * Return whether the type of the expression is float or double. |
| */ |
| private boolean isTypeFloatOrDouble(JExpression exp) { |
| return isTypeFloatOrDouble(exp.getType()); |
| } |
| |
| private boolean isTypeFloatOrDouble(JType type) { |
| return ((type == program.getTypePrimitiveDouble()) || (type == program |
| .getTypePrimitiveFloat())); |
| } |
| |
| /** |
| * Return whether the type of the expression is byte, char, short, int, or |
| * long. |
| */ |
| private boolean isTypeIntegral(JExpression exp) { |
| return isTypeIntegral(exp.getType()); |
| } |
| |
| private boolean isTypeIntegral(JType type) { |
| return ((type == program.getTypePrimitiveInt()) || (type == program.getTypePrimitiveLong()) |
| || (type == program.getTypePrimitiveChar()) || (type == program.getTypePrimitiveByte()) || (type == program |
| .getTypePrimitiveShort())); |
| } |
| |
| private boolean isTypeLong(JExpression exp) { |
| return isTypeLong(exp.getType()); |
| } |
| |
| private boolean isTypeLong(JType type) { |
| return type == program.getTypePrimitiveLong(); |
| } |
| |
| private boolean isTypeNull(JExpression exp) { |
| return isTypeNull(exp.getType()); |
| } |
| |
| private boolean isTypeNull(JType type) { |
| return type == program.getTypeNull(); |
| } |
| |
| private boolean isTypeString(JExpression exp) { |
| return program.isJavaLangString(exp.getType()); |
| } |
| |
| private boolean isUnconditionalBreak(JStatement statement) { |
| return findUnconditionalBreak(statement) != null; |
| } |
| |
| private boolean isUnconditionalUnlabeledBreak(JStatement statement) { |
| JBreakStatement breakStat = findUnconditionalBreak(statement); |
| return (breakStat != null) && (breakStat.getLabel() == null); |
| } |
| |
| private <T> T last(List<T> statements) { |
| return statements.get(statements.size() - 1); |
| } |
| |
| private Class<?> mapType(JType type) { |
| return typeClassMap.get(type); |
| } |
| |
| /** |
| * Replace me only if the the updated expression is different. |
| */ |
| private void maybeReplaceMe(JExpression x, JExpression updated, Context ctx) { |
| if (updated != x) { |
| ctx.replaceMe(updated); |
| } |
| } |
| |
| private void maybeReplaceMe(JStatement x, JStatement updated, Context ctx) { |
| if (updated != x) { |
| replaceMe(updated, ctx); |
| } |
| } |
| |
| private int numRemovableExpressions(JMultiExpression x) { |
| if (ignoringExpressionOutput.contains(x)) { |
| // The result doesn't matter: all expressions can be removed. |
| return x.exprs.size(); |
| } else { |
| // The last expression cannot be removed. |
| return x.exprs.size() - 1; |
| } |
| } |
| |
| /** |
| * Removes any break statements that appear one after another. |
| */ |
| private void removeDoubleBreaks(JSwitchStatement x) { |
| JBlock body = x.getBody(); |
| boolean lastWasBreak = true; |
| for (int i = 0; i < body.getStatements().size(); ++i) { |
| JStatement statement = body.getStatements().get(i); |
| boolean isBreak = isUnconditionalBreak(statement); |
| if (isBreak && lastWasBreak) { |
| body.removeStmt(i--); |
| madeChanges(); |
| } |
| lastWasBreak = isBreak; |
| } |
| |
| // Remove a trailing break statement from a case block |
| if (body.getStatements().size() > 0 |
| && isUnconditionalUnlabeledBreak(last(body.getStatements()))) { |
| body.removeStmt(body.getStatements().size() - 1); |
| madeChanges(); |
| } |
| } |
| |
| /** |
| * A switch with no default case can have its empty cases pruned. |
| */ |
| private void removeEmptyCases(JSwitchStatement x) { |
| JBlock body = x.getBody(); |
| List<JStatement> noOpCaseStatements = new ArrayList<JStatement>(); |
| List<JStatement> potentialNoOpCaseStatements = new ArrayList<JStatement>(); |
| /* |
| * A case statement has no effect if there is no code between it and |
| * either an unconditional break or the end of the switch. |
| */ |
| for (JStatement statement : body.getStatements()) { |
| if (statement instanceof JCaseStatement) { |
| potentialNoOpCaseStatements.add(statement); |
| } else if (isUnconditionalUnlabeledBreak(statement)) { |
| // If we have any potential no-ops, they now become real no-ops. |
| noOpCaseStatements.addAll(potentialNoOpCaseStatements); |
| potentialNoOpCaseStatements.clear(); |
| } else { |
| // Any other kind of statement makes these case statements are useful. |
| potentialNoOpCaseStatements.clear(); |
| } |
| } |
| // None of the remaining case statements have any effect |
| noOpCaseStatements.addAll(potentialNoOpCaseStatements); |
| |
| if (noOpCaseStatements.size() > 0) { |
| for (JStatement statement : noOpCaseStatements) { |
| body.removeStmt(body.getStatements().indexOf(statement)); |
| madeChanges(); |
| } |
| } |
| } |
| |
| /** |
| * Call this instead of directly calling <code>ctx.removeMe()</code> for |
| * Statements. |
| */ |
| private void removeMe(JStatement stmt, Context ctx) { |
| if (ctx.canRemove()) { |
| ctx.removeMe(); |
| } else { |
| // empty block statement |
| ctx.replaceMe(new JBlock(stmt.getSourceInfo())); |
| } |
| } |
| |
| /** |
| * |
| * Call this instead of directly calling <code>ctx.replaceMe()</code> for |
| * Statements. |
| */ |
| private void replaceMe(JStatement stmt, Context ctx) { |
| stmt = this.accept(stmt, ctx.canRemove()); |
| if (stmt == null) { |
| ctx.removeMe(); |
| } else { |
| ctx.replaceMe(stmt); |
| } |
| } |
| |
| private boolean simplifyAdd(JExpression lhs, JExpression rhs, Context ctx, JType type) { |
| if (isLiteralZero(rhs)) { |
| ctx.replaceMe(simplifier.cast(type, lhs)); |
| return true; |
| } |
| if (isLiteralZero(lhs)) { |
| ctx.replaceMe(simplifier.cast(type, rhs)); |
| return true; |
| } |
| |
| return false; |
| } |
| |
| /** |
| * Simplify <code>exp == bool</code>, where <code>bool</code> is a boolean |
| * literal. |
| */ |
| private void simplifyBooleanEq(JExpression exp, boolean bool, Context ctx) { |
| if (bool) { |
| ctx.replaceMe(exp); |
| } else { |
| ctx.replaceMe(new JPrefixOperation(exp.getSourceInfo(), JUnaryOperator.NOT, exp)); |
| } |
| } |
| |
| /** |
| * Simplify <code>lhs == rhs</code>, where <code>lhs</code> and |
| * <code>rhs</code> are known to be boolean. If <code>negate</code> is |
| * <code>true</code>, then treat it as <code>lhs != rhs</code> instead of |
| * <code>lhs == rhs</code>. Assumes that the case where both sides are |
| * literals has already been checked. |
| */ |
| private void simplifyBooleanEq(JExpression lhs, JExpression rhs, Context ctx, boolean negate) { |
| if (lhs instanceof JBooleanLiteral) { |
| boolean left = ((JBooleanLiteral) lhs).getValue(); |
| simplifyBooleanEq(rhs, left ^ negate, ctx); |
| return; |
| } |
| if (rhs instanceof JBooleanLiteral) { |
| boolean right = ((JBooleanLiteral) rhs).getValue(); |
| simplifyBooleanEq(lhs, right ^ negate, ctx); |
| return; |
| } |
| } |
| |
| private boolean simplifyDiv(JExpression lhs, JExpression rhs, Context ctx, JType type) { |
| if (isLiteralOne(rhs)) { |
| ctx.replaceMe(simplifier.cast(type, lhs)); |
| return true; |
| } |
| if (isLiteralNegativeOne(rhs)) { |
| ctx.replaceMe(simplifyNegate(simplifier.cast(type, lhs))); |
| return true; |
| } |
| |
| return false; |
| } |
| |
| /** |
| * Simplify <code>lhs == rhs</code>. If <code>negate</code> is true, then |
| * it's actually static evaluation of <code>lhs != rhs</code>. |
| */ |
| private void simplifyEq(JExpression lhs, JExpression rhs, Context ctx, boolean negated) { |
| if (isTypeBoolean(lhs) && isTypeBoolean(rhs)) { |
| simplifyBooleanEq(lhs, rhs, ctx, negated); |
| return; |
| } |
| } |
| |
| private boolean simplifyMul(JExpression lhs, JExpression rhs, Context ctx, JType type) { |
| if (isLiteralOne(rhs)) { |
| ctx.replaceMe(simplifier.cast(type, lhs)); |
| return true; |
| } |
| if (isLiteralOne(lhs)) { |
| ctx.replaceMe(simplifier.cast(type, rhs)); |
| return true; |
| } |
| if (isLiteralNegativeOne(rhs)) { |
| ctx.replaceMe(simplifyNegate(simplifier.cast(type, lhs))); |
| return true; |
| } |
| if (isLiteralNegativeOne(lhs)) { |
| ctx.replaceMe(simplifyNegate(simplifier.cast(type, rhs))); |
| return true; |
| } |
| if (isLiteralZero(rhs) && !lhs.hasSideEffects()) { |
| ctx.replaceMe(simplifier.cast(type, rhs)); |
| return true; |
| } |
| if (isLiteralZero(lhs) && !rhs.hasSideEffects()) { |
| ctx.replaceMe(simplifier.cast(type, lhs)); |
| return true; |
| } |
| return false; |
| } |
| |
| private JExpression simplifyNegate(JExpression exp) { |
| return simplifyNegate(null, exp); |
| } |
| |
| /** |
| * Simplify the expression <code>-exp</code>. |
| * |
| * @param original An expression equivalent to <code>-exp</code>. |
| * @param exp The expression to negate. |
| * |
| * @return A simplified expression equivalent to <code>- exp</code>. |
| */ |
| private JExpression simplifyNegate(JExpression original, JExpression exp) { |
| // - -x -> x |
| if (exp instanceof JPrefixOperation) { |
| JPrefixOperation prefarg = (JPrefixOperation) exp; |
| if (prefarg.getOp() == JUnaryOperator.NEG) { |
| return prefarg.getArg(); |
| } |
| } |
| |
| // no change |
| if (original != null) { |
| return original; |
| } |
| return new JPrefixOperation(exp.getSourceInfo(), JUnaryOperator.NEG, exp); |
| } |
| |
| private boolean simplifySub(JExpression lhs, JExpression rhs, Context ctx, JType type) { |
| if (isLiteralZero(rhs)) { |
| ctx.replaceMe(simplifier.cast(type, lhs)); |
| return true; |
| } |
| if (isLiteralZero(lhs) && !isTypeFloatOrDouble(type)) { |
| ctx.replaceMe(simplifyNegate(simplifier.cast(type, rhs))); |
| return true; |
| } |
| return false; |
| } |
| |
| private void simplifyXor(JExpression lhs, JBooleanLiteral rhs, Context ctx) { |
| if (rhs.getValue()) { |
| ctx.replaceMe(new JPrefixOperation(lhs.getSourceInfo(), JUnaryOperator.NOT, lhs)); |
| } else { |
| ctx.replaceMe(lhs); |
| } |
| } |
| |
| /** |
| * Simplify XOR expressions. |
| * |
| * <pre> |
| * true ^ x -> !x |
| * false ^ x -> x |
| * y ^ true -> !y |
| * y ^ false -> y |
| * </pre> |
| */ |
| private void simplifyXor(JExpression lhs, JExpression rhs, Context ctx) { |
| if (lhs instanceof JBooleanLiteral) { |
| JBooleanLiteral booleanLiteral = (JBooleanLiteral) lhs; |
| simplifyXor(rhs, booleanLiteral, ctx); |
| } else if (rhs instanceof JBooleanLiteral) { |
| JBooleanLiteral booleanLiteral = (JBooleanLiteral) rhs; |
| simplifyXor(lhs, booleanLiteral, ctx); |
| } |
| } |
| |
| private boolean toBoolean(JValueLiteral x) { |
| return ((JBooleanLiteral) x).getValue(); |
| } |
| |
| /** |
| * Cast a Java wrapper class (Integer, Double, Float, etc.) to a double. |
| */ |
| private double toDouble(JValueLiteral literal) { |
| Object valueObj = literal.getValueObj(); |
| if (valueObj instanceof Number) { |
| return ((Number) valueObj).doubleValue(); |
| } else { |
| return ((Character) valueObj).charValue(); |
| } |
| } |
| |
| private float toFloat(JValueLiteral x) { |
| return (float) toDouble(x); |
| } |
| |
| /** |
| * Cast a Java wrapper class (Integer, Double, Float, etc.) to a long. |
| */ |
| private int toInt(JValueLiteral literal) { |
| Object valueObj = literal.getValueObj(); |
| if (valueObj instanceof Number) { |
| return ((Number) valueObj).intValue(); |
| } else { |
| return ((Character) valueObj).charValue(); |
| } |
| } |
| |
| /** |
| * Cast a Java wrapper class (Integer, Double, Float, etc.) to a long. |
| */ |
| private long toLong(JValueLiteral literal) { |
| Object valueObj = literal.getValueObj(); |
| if (valueObj instanceof Number) { |
| return ((Number) valueObj).longValue(); |
| } else { |
| return ((Character) valueObj).charValue(); |
| } |
| } |
| |
| private JLiteral tryGetConstant(JVariableRef x) { |
| if (!lvalues.contains(x)) { |
| JLiteral lit = x.getTarget().getConstInitializer(); |
| if (lit != null) { |
| /* |
| * Upcast the initializer so that the semantics of any arithmetic on |
| * this value is not changed. |
| */ |
| // TODO(spoon): use simplifier.cast to shorten this |
| if ((x.getType() instanceof JPrimitiveType) && (lit instanceof JValueLiteral)) { |
| JPrimitiveType xTypePrim = (JPrimitiveType) x.getType(); |
| lit = xTypePrim.coerceLiteral((JValueLiteral) lit); |
| } |
| return lit; |
| } |
| } |
| return null; |
| } |
| |
| /** |
| * Replace String methods having literal args with the static result. |
| */ |
| private void tryOptimizeStringCall(JMethodCall x, Context ctx, JMethod method) { |
| |
| if (method.getType() == program.getTypeVoid()) { |
| return; |
| } |
| |
| if (method.getOriginalParamTypes().size() != method.getParams().size()) { |
| // One or more parameters were pruned, abort. |
| return; |
| } |
| |
| if (method.getName().endsWith("hashCode")) { |
| // This cannot be computed at compile time because our implementation |
| // differs from the JRE. |
| // TODO: actually, I think it DOES match now, so we can remove this? |
| return; |
| } |
| |
| if (method.getName().endsWith("toString")) { |
| // replaces s.toString() with s |
| if (program.isStaticImpl(method)) { |
| ctx.replaceMe(x.getArgs().get(0)); |
| } else { |
| ctx.replaceMe(x.getInstance()); |
| } |
| return; |
| } |
| |
| int skip = 0; |
| Object instance; |
| if (program.isStaticImpl(method)) { |
| // is it static implementation for instance method? |
| method = program.staticImplFor(method); |
| instance = tryTranslateLiteral(x.getArgs().get(0), String.class); |
| skip = 1; |
| } else { |
| // instance may be null |
| instance = tryTranslateLiteral(x.getInstance(), String.class); |
| } |
| |
| if (instance == null && !method.isStatic()) { |
| return; |
| } |
| |
| List<JType> params = method.getOriginalParamTypes(); |
| Class<?> paramTypes[] = new Class<?>[params.size()]; |
| Object paramValues[] = new Object[params.size()]; |
| List<JExpression> args = x.getArgs(); |
| for (int i = 0; i != params.size(); ++i) { |
| paramTypes[i] = mapType(params.get(i)); |
| if (paramTypes[i] == null) { |
| return; |
| } |
| paramValues[i] = tryTranslateLiteral(args.get(i + skip), paramTypes[i]); |
| if (paramValues[i] == null) { |
| return; |
| } |
| } |
| |
| try { |
| Method actual = String.class.getMethod(method.getName(), paramTypes); |
| if (actual == null) { |
| return; |
| } |
| Object result = actual.invoke(instance, paramValues); |
| if (result instanceof String) { |
| ctx.replaceMe(program.getLiteralString(x.getSourceInfo(), (String) result)); |
| } else if (result instanceof Boolean) { |
| ctx.replaceMe(program.getLiteralBoolean(((Boolean) result).booleanValue())); |
| } else if (result instanceof Character) { |
| ctx.replaceMe(program.getLiteralChar(((Character) result).charValue())); |
| } else if (result instanceof Integer) { |
| ctx.replaceMe(program.getLiteralInt(((Integer) result).intValue())); |
| } |
| } catch (RuntimeException e) { |
| // Don't eat RuntimeExceptions |
| throw e; |
| } catch (Exception e) { |
| // If the call threw an exception, just don't optimize |
| } |
| } |
| |
| private void tryRemoveSwitch(JSwitchStatement x, Context ctx) { |
| JBlock body = x.getBody(); |
| if (body.getStatements().size() == 0) { |
| // Empty switch; just run the switch condition. |
| replaceMe(x.getExpr().makeStatement(), ctx); |
| } else if (body.getStatements().size() == 2) { |
| /* |
| * If there are only two statements, we know it's a case statement and |
| * something with an effect. |
| * |
| * TODO: make this more sophisticated; what we should really care about |
| * is how many case statements it contains, not how many statements: |
| * |
| * switch(i) { default: a(); b(); c(); } |
| * |
| * becomes { a(); b(); c(); } |
| * |
| * switch(i) { case 1: a(); b(); c(); } |
| * |
| * becomes if (i == 1) { a(); b(); c(); } |
| * |
| * switch(i) { case 1: a(); b(); break; default: c(); d(); } |
| * |
| * becomes if (i == 1) { a(); b(); } else { c(); d(); } |
| */ |
| JCaseStatement caseStatement = (JCaseStatement) body.getStatements().get(0); |
| JStatement statement = body.getStatements().get(1); |
| |
| FindBreakContinueStatementsVisitor visitor = new FindBreakContinueStatementsVisitor(); |
| visitor.accept(statement); |
| if (visitor.hasBreakContinueStatements()) { |
| // Cannot optimize. |
| return; |
| } |
| |
| if (caseStatement.getExpr() != null) { |
| // Create an if statement equivalent to the single-case switch. |
| JBinaryOperation compareOperation = |
| new JBinaryOperation(x.getSourceInfo(), program.getTypePrimitiveBoolean(), |
| JBinaryOperator.EQ, x.getExpr(), caseStatement.getExpr()); |
| JBlock block = new JBlock(x.getSourceInfo()); |
| block.addStmt(statement); |
| JIfStatement ifStatement = |
| new JIfStatement(x.getSourceInfo(), compareOperation, block, null); |
| replaceMe(ifStatement, ctx); |
| } else { |
| // All we have is a default case; convert to a JBlock. |
| JBlock block = new JBlock(x.getSourceInfo()); |
| block.addStmt(x.getExpr().makeStatement()); |
| block.addStmt(statement); |
| replaceMe(block, ctx); |
| } |
| } |
| } |
| |
| private Object tryTranslateLiteral(JExpression maybeLit, Class<?> type) { |
| if (!(maybeLit instanceof JValueLiteral)) { |
| return null; |
| } |
| // TODO: make this way better by a mile |
| if (type == boolean.class && maybeLit instanceof JBooleanLiteral) { |
| return Boolean.valueOf(((JBooleanLiteral) maybeLit).getValue()); |
| } |
| if (type == char.class && maybeLit instanceof JCharLiteral) { |
| return Character.valueOf(((JCharLiteral) maybeLit).getValue()); |
| } |
| if (type == double.class && maybeLit instanceof JDoubleLiteral) { |
| return new Double(((JDoubleLiteral) maybeLit).getValue()); |
| } |
| if (type == float.class && maybeLit instanceof JIntLiteral) { |
| return new Float(((JIntLiteral) maybeLit).getValue()); |
| } |
| if (type == int.class && maybeLit instanceof JIntLiteral) { |
| return Integer.valueOf(((JIntLiteral) maybeLit).getValue()); |
| } |
| if (type == long.class && maybeLit instanceof JLongLiteral) { |
| return Long.valueOf(((JLongLiteral) maybeLit).getValue()); |
| } |
| if (type == String.class && maybeLit instanceof JStringLiteral) { |
| return ((JStringLiteral) maybeLit).getValue(); |
| } |
| if (type == Object.class) { |
| // We already know it is a JValueLiteral instance |
| return ((JValueLiteral) maybeLit).getValueObj(); |
| } |
| return null; |
| } |
| } |
| |
| /** |
| * Examines code to find out whether it contains any break or continue |
| * statements. |
| * |
| * TODO: We could be more sophisticated with this. A nested while loop with an |
| * unlabeled break should not cause this visitor to return false. Nor should a |
| * labeled break break to another context. |
| */ |
| public static class FindBreakContinueStatementsVisitor extends JVisitor { |
| private boolean hasBreakContinueStatements = false; |
| |
| @Override |
| public void endVisit(JBreakStatement x, Context ctx) { |
| hasBreakContinueStatements = true; |
| } |
| |
| @Override |
| public void endVisit(JContinueStatement x, Context ctx) { |
| hasBreakContinueStatements = true; |
| } |
| |
| protected boolean hasBreakContinueStatements() { |
| return hasBreakContinueStatements; |
| } |
| } |
| |
| public static final String NAME = DeadCodeElimination.class.getSimpleName(); |
| |
| public static OptimizerStats exec(JProgram program) { |
| return new DeadCodeElimination(program).execImpl(program); |
| } |
| |
| public static OptimizerStats exec(JProgram program, JNode node) { |
| return new DeadCodeElimination(program).execImpl(node); |
| } |
| |
| private final JProgram program; |
| private final Simplifier simplifier; |
| |
| private final Map<JType, Class<?>> typeClassMap = new IdentityHashMap<JType, Class<?>>(); |
| |
| public DeadCodeElimination(JProgram program) { |
| this.program = program; |
| simplifier = new Simplifier(program); |
| typeClassMap.put(program.getTypeJavaLangObject(), Object.class); |
| typeClassMap.put(program.getTypeJavaLangString(), String.class); |
| typeClassMap.put(program.getTypePrimitiveBoolean(), boolean.class); |
| typeClassMap.put(program.getTypePrimitiveByte(), byte.class); |
| typeClassMap.put(program.getTypePrimitiveChar(), char.class); |
| typeClassMap.put(program.getTypePrimitiveDouble(), double.class); |
| typeClassMap.put(program.getTypePrimitiveFloat(), float.class); |
| typeClassMap.put(program.getTypePrimitiveInt(), int.class); |
| typeClassMap.put(program.getTypePrimitiveLong(), long.class); |
| typeClassMap.put(program.getTypePrimitiveShort(), short.class); |
| } |
| |
| private OptimizerStats execImpl(JNode node) { |
| OptimizerStats stats = new OptimizerStats(NAME); |
| Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME); |
| |
| DeadCodeVisitor deadCodeVisitor = new DeadCodeVisitor(); |
| deadCodeVisitor.accept(node); |
| stats.recordModified(deadCodeVisitor.getNumMods()); |
| optimizeEvent.end("didChange", "" + stats.didChange()); |
| return stats; |
| } |
| } |
