DeadCodeElimination


1   /*
2    * Copyright 2007 Google Inc.
3    * 
4    * Licensed under the Apache License, Version 2.0 (the "License"); you may not
5    * use this file except in compliance with the License. You may obtain a copy of
6    * the License at
7    * 
8    * http://www.apache.org/licenses/LICENSE-2.0
9    * 
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13   * License for the specific language governing permissions and limitations under
14   * the License.
15   */
16  package com.google.gwt.dev.jjs.impl;
17  
18  import com.google.gwt.dev.jjs.ast.Context;
19  import com.google.gwt.dev.jjs.ast.JBinaryOperation;
20  import com.google.gwt.dev.jjs.ast.JBinaryOperator;
21  import com.google.gwt.dev.jjs.ast.JBlock;
22  import com.google.gwt.dev.jjs.ast.JBooleanLiteral;
23  import com.google.gwt.dev.jjs.ast.JBreakStatement;
24  import com.google.gwt.dev.jjs.ast.JCharLiteral;
25  import com.google.gwt.dev.jjs.ast.JConditional;
26  import com.google.gwt.dev.jjs.ast.JContinueStatement;
27  import com.google.gwt.dev.jjs.ast.JDoStatement;
28  import com.google.gwt.dev.jjs.ast.JDoubleLiteral;
29  import com.google.gwt.dev.jjs.ast.JExpression;
30  import com.google.gwt.dev.jjs.ast.JExpressionStatement;
31  import com.google.gwt.dev.jjs.ast.JForStatement;
32  import com.google.gwt.dev.jjs.ast.JIfStatement;
33  import com.google.gwt.dev.jjs.ast.JIntLiteral;
34  import com.google.gwt.dev.jjs.ast.JLocalRef;
35  import com.google.gwt.dev.jjs.ast.JLongLiteral;
36  import com.google.gwt.dev.jjs.ast.JMethod;
37  import com.google.gwt.dev.jjs.ast.JMethodCall;
38  import com.google.gwt.dev.jjs.ast.JModVisitor;
39  import com.google.gwt.dev.jjs.ast.JPrefixOperation;
40  import com.google.gwt.dev.jjs.ast.JProgram;
41  import com.google.gwt.dev.jjs.ast.JReferenceType;
42  import com.google.gwt.dev.jjs.ast.JStatement;
43  import com.google.gwt.dev.jjs.ast.JStringLiteral;
44  import com.google.gwt.dev.jjs.ast.JTryStatement;
45  import com.google.gwt.dev.jjs.ast.JType;
46  import com.google.gwt.dev.jjs.ast.JUnaryOperator;
47  import com.google.gwt.dev.jjs.ast.JValueLiteral;
48  import com.google.gwt.dev.jjs.ast.JVisitor;
49  import com.google.gwt.dev.jjs.ast.JWhileStatement;
50  
51  import java.lang.reflect.Method  ;
52  import java.util.ArrayList  ;
53  import java.util.IdentityHashMap  ;
54  import java.util.Iterator  ;
55  import java.util.List  ;
56  import java.util.Map  ;
57  
58  /**
59   * Attempts to remove dead code.
60   */
61  public class DeadCodeElimination {
62  
63    /**
64     * Eliminates dead or unreachable code when possible.
65     */
66    public class DeadCodeVisitor extends JModVisitor {
67  
68      /**
69       * Short circuit binary operations.
70       */
71      public void endVisit(JBinaryOperation x, Context ctx) {
72        JBinaryOperator op = x.getOp();
73        JExpression lhs = x.getLhs();
74        JExpression rhs = x.getRhs();
75        if (op == JBinaryOperator.AND) {
76          // simplify short circuit AND expressions
77          if (lhs instanceof JBooleanLiteral) {
78            // eg: if (false && isWhatever()) -> if (false)
79            // eg: if (true && isWhatever()) -> if (isWhatever())
80            JBooleanLiteral booleanLiteral = (JBooleanLiteral) lhs;
81            if (booleanLiteral.getValue()) {
82              ctx.replaceMe(rhs);
83            } else {
84              ctx.replaceMe(lhs);
85            }
86  
87          } else if (rhs instanceof JBooleanLiteral) {
88            // eg: if (isWhatever() && true) -> if (isWhatever())
89            // eg: if (isWhatever() && false) -> if (false), unless side effects
90            JBooleanLiteral booleanLiteral = (JBooleanLiteral) rhs;
91            if (booleanLiteral.getValue()) {
92              ctx.replaceMe(lhs);
93            } else if (!lhs.hasSideEffects()) {
94              ctx.replaceMe(rhs);
95            }
96          }
97  
98        } else if (op == JBinaryOperator.OR) {
99          // simplify short circuit OR expressions
100         if (lhs instanceof JBooleanLiteral) {
101           // eg: if (true || isWhatever()) -> if (true)
102           // eg: if (false || isWhatever()) -> if (isWhatever())
103           JBooleanLiteral booleanLiteral = (JBooleanLiteral) lhs;
104           if (booleanLiteral.getValue()) {
105             ctx.replaceMe(lhs);
106           } else {
107             ctx.replaceMe(rhs);
108           }
109 
110         } else if (rhs instanceof JBooleanLiteral) {
111           // eg: if (isWhatever() || false) -> if (isWhatever())
112           // eg: if (isWhatever() && true) -> if (true), unless side effects
113           JBooleanLiteral booleanLiteral = (JBooleanLiteral) rhs;
114           if (!booleanLiteral.getValue()) {
115             ctx.replaceMe(lhs);
116           } else if (!lhs.hasSideEffects()) {
117             ctx.replaceMe(rhs);
118           }
119         }
120       } else if (op == JBinaryOperator.EQ) {
121         // simplify: null == null -> true
122         if (lhs.getType() == program.getTypeNull()
123             && rhs.getType() == program.getTypeNull()) {
124           ctx.replaceMe(program.getLiteralBoolean(true));
125         }
126       } else if (op == JBinaryOperator.NEQ) {
127         // simplify: null != null -> false
128         if (lhs.getType() == program.getTypeNull()
129             && rhs.getType() == program.getTypeNull()) {
130           ctx.replaceMe(program.getLiteralBoolean(false));
131         }
132       } else if (op == JBinaryOperator.ADD
133           && x.getType() == program.getTypeJavaLangString()) {
134         // try to statically evaluate concatentation
135         if (lhs instanceof JValueLiteral && rhs instanceof JValueLiteral) {
136           Object   lhsObj = ((JValueLiteral) lhs).getValueObj();
137           Object   rhsObj = ((JValueLiteral) rhs).getValueObj();
138           ctx.replaceMe(program.getLiteralString(String.valueOf(lhsObj)
139               + String.valueOf(rhsObj)));
140         }
141       }
142     }
143 
144     /**
145      * Prune empty blocks.
146      */
147     public void endVisit(JBlock x, Context ctx) {
148       if (x.statements.size() == 0) {
149         if (ctx.canRemove()) {
150           ctx.removeMe();
151         }
152       }
153     }
154 
155     public void endVisit(JConditional x, Context ctx) {
156       JExpression condExpr = x.getIfTest();
157       JExpression thenExpr = x.getThenExpr();
158       JExpression elseExpr = x.getElseExpr();
159       if (condExpr instanceof JBooleanLiteral) {
160         if (((JBooleanLiteral) condExpr).getValue()) {
161           // e.g. (true ? then : else) -> then
162           ctx.replaceMe(thenExpr);
163         } else {
164           // e.g. (false ? then : else) -> else
165           ctx.replaceMe(elseExpr);
166         }
167       } else if (thenExpr instanceof JBooleanLiteral) {
168         if (((JBooleanLiteral) thenExpr).getValue()) {
169           // e.g. (cond ? true : else) -> cond || else
170           JBinaryOperation binOp = new JBinaryOperation(program,
171               x.getSourceInfo(), x.getType(), JBinaryOperator.OR, condExpr,
172               elseExpr);
173           ctx.replaceMe(binOp);
174         } else {
175           // e.g. (cond ? false : else) -> !cond && else
176           JPrefixOperation notCondExpr = new JPrefixOperation(program,
177               condExpr.getSourceInfo(), JUnaryOperator.NOT, condExpr);
178           JBinaryOperation binOp = new JBinaryOperation(program,
179               x.getSourceInfo(), x.getType(), JBinaryOperator.AND, notCondExpr,
180               elseExpr);
181           ctx.replaceMe(binOp);
182         }
183       } else if (elseExpr instanceof JBooleanLiteral) {
184         if (((JBooleanLiteral) elseExpr).getValue()) {
185           // e.g. (cond ? then : true) -> !cond || then
186           JPrefixOperation notCondExpr = new JPrefixOperation(program,
187               condExpr.getSourceInfo(), JUnaryOperator.NOT, condExpr);
188           JBinaryOperation binOp = new JBinaryOperation(program,
189               x.getSourceInfo(), x.getType(), JBinaryOperator.OR, notCondExpr,
190               thenExpr);
191           ctx.replaceMe(binOp);
192         } else {
193           // e.g. (cond ? then : false) -> cond && then
194           JBinaryOperation binOp = new JBinaryOperation(program,
195               x.getSourceInfo(), x.getType(), JBinaryOperator.AND, condExpr,
196               thenExpr);
197           ctx.replaceMe(binOp);
198         }
199       }
200     }
201 
202     /**
203      * Convert do { } while (false); into a block.
204      */
205     public void endVisit(JDoStatement x, Context ctx) {
206       JExpression expression = x.getTestExpr();
207       if (expression instanceof JBooleanLiteral) {
208         JBooleanLiteral booleanLiteral = (JBooleanLiteral) expression;
209 
210         // If false, replace do with do's body
211         if (!booleanLiteral.getValue()) {
212           // Unless it contains break/continue statements
213           FindBreakContinueStatementsVisitor visitor = new FindBreakContinueStatementsVisitor();
214           visitor.accept(x.getBody());
215           if (!visitor.hasBreakContinueStatements()) {
216             ctx.replaceMe(x.getBody());
217           }
218         }
219       }
220     }
221 
222     public void endVisit(JExpressionStatement x, Context ctx) {
223       if (!x.getExpr().hasSideEffects()) {
224         removeMe(x, ctx);
225       }
226     }
227 
228     /**
229      * Prune for (X; false; Y) statements, but make sure X is run.
230      */
231     public void endVisit(JForStatement x, Context ctx) {
232       JExpression expression = x.getTestExpr();
233       if (expression instanceof JBooleanLiteral) {
234         JBooleanLiteral booleanLiteral = (JBooleanLiteral) expression;
235 
236         // If false, replace the for statement with its initializers
237         if (!booleanLiteral.getValue()) {
238           JBlock block = new JBlock(program, x.getSourceInfo());
239           block.statements.addAll(x.getInitializers());
240           ctx.replaceMe(block);
241         }
242       }
243     }
244 
245     /**
246      * Simplify if statements.
247      */
248     public void endVisit(JIfStatement x, Context ctx) {
249       JExpression expr = x.getIfExpr();
250       JStatement thenStmt = x.getThenStmt();
251       JStatement elseStmt = x.getElseStmt();
252       if (expr instanceof JBooleanLiteral) {
253         JBooleanLiteral booleanLiteral = (JBooleanLiteral) expr;
254         boolean boolVal = booleanLiteral.getValue();
255         if (boolVal && !isEmpty(thenStmt)) {
256           // If true, replace myself with then statement
257           ctx.replaceMe(thenStmt);
258         } else if (!boolVal && !isEmpty(elseStmt)) {
259           // If false, replace myself with else statement
260           ctx.replaceMe(elseStmt);
261         } else {
262           // just prune me
263           removeMe(x, ctx);
264         }
265       } else if (isEmpty(thenStmt) && isEmpty(elseStmt)) {
266         ctx.replaceMe(expr.makeStatement());
267       }
268     }
269 
270     /**
271      * Resolve method calls that can be computed statically.
272      */
273     public void endVisit(JMethodCall x, Context ctx) {
274       JMethod method = x.getTarget();
275       if (method.getEnclosingType() == program.getTypeJavaLangString()) {
276         tryOptimizeStringCall(x, ctx, method);
277       }
278     }
279 
280     /**
281      * Simplify the ! operator if possible.
282      */
283     public void endVisit(JPrefixOperation x, Context ctx) {
284       if (x.getOp() == JUnaryOperator.NOT) {
285         JExpression arg = x.getArg();
286         if (arg instanceof JBooleanLiteral) {
287           // e.g. !true -> false; !false -> true
288           JBooleanLiteral booleanLiteral = (JBooleanLiteral) arg;
289           ctx.replaceMe(program.getLiteralBoolean(!booleanLiteral.getValue()));
290         } else if (arg instanceof JBinaryOperation) {
291           // try to invert the binary operator
292           JBinaryOperation argOp = (JBinaryOperation) arg;
293           JBinaryOperator op = argOp.getOp();
294           JBinaryOperator newOp = null;
295           if (op == JBinaryOperator.EQ) {
296             // e.g. !(x == y) -> x != y
297             newOp = JBinaryOperator.NEQ;
298           } else if (op == JBinaryOperator.NEQ) {
299             // e.g. !(x != y) -> x == y
300             newOp = JBinaryOperator.EQ;
301           } else if (op == JBinaryOperator.GT) {
302             // e.g. !(x > y) -> x <= y
303             newOp = JBinaryOperator.LTE;
304           } else if (op == JBinaryOperator.LTE) {
305             // e.g. !(x <= y) -> x > y
306             newOp = JBinaryOperator.GT;
307           } else if (op == JBinaryOperator.GTE) {
308             // e.g. !(x >= y) -> x < y
309             newOp = JBinaryOperator.LT;
310           } else if (op == JBinaryOperator.LT) {
311             // e.g. !(x < y) -> x >= y
312             newOp = JBinaryOperator.GTE;
313           }
314           if (newOp != null) {
315             JBinaryOperation newBinOp = new JBinaryOperation(program,
316                 argOp.getSourceInfo(), argOp.getType(), newOp, argOp.getLhs(),
317                 argOp.getRhs());
318             ctx.replaceMe(newBinOp);
319           }
320         } else if (arg instanceof JPrefixOperation) {
321           // try to invert the unary operator
322           JPrefixOperation argOp = (JPrefixOperation) arg;
323           JUnaryOperator op = argOp.getOp();
324           // e.g. !!x -> x
325           if (op == JUnaryOperator.NOT) {
326             ctx.replaceMe(argOp.getArg());
327           }
328         }
329       }
330     }
331 
332     /**
333      * 1) Remove catch blocks whose exception type is not instantiable. 2) Prune
334      * try statements with no body. 3) Hoist up try statements with no catches
335      * and an empty finally.
336      */
337     public void endVisit(JTryStatement x, Context ctx) {
338       // 1) Remove catch blocks whose exception type is not instantiable.
339       List   catchArgs = x.getCatchArgs();
340       List   catchBlocks = x.getCatchBlocks();
341       for (Iterator   itA = catchArgs.iterator(), itB = catchBlocks.iterator(); itA.hasNext();) {
342         JLocalRef localRef = (JLocalRef) itA.next();
343         itB.next();
344         JReferenceType type = (JReferenceType) localRef.getType();
345         if (!program.typeOracle.isInstantiatedType(type)
346             || type == program.getTypeNull()) {
347           itA.remove();
348           itB.remove();
349         }
350       }
351 
352       // Compute properties regarding the state of this try statement
353       boolean noTry = isEmpty(x.getTryBlock());
354       boolean noCatch = catchArgs.size() == 0;
355       boolean noFinally = isEmpty(x.getFinallyBlock());
356 
357       if (noTry) {
358         // 2) Prune try statements with no body.
359         if (noFinally) {
360           // if there's no finally, prune the whole thing
361           removeMe(x, ctx);
362         } else {
363           // replace the try statement with just the contents of the finally
364           ctx.replaceMe(x.getFinallyBlock());
365         }
366       } else if (noCatch && noFinally) {
367         // 3) Hoist up try statements with no catches and an empty finally.
368         // If there's no catch or finally, there's no point in this even being
369         // a try statement, replace myself with the try block
370         ctx.replaceMe(x.getTryBlock());
371       }
372     }
373 
374     /**
375      * Prune while (false) statements.
376      */
377     public void endVisit(JWhileStatement x, Context ctx) {
378       JExpression expression = x.getTestExpr();
379       if (expression instanceof JBooleanLiteral) {
380         JBooleanLiteral booleanLiteral = (JBooleanLiteral) expression;
381 
382         // If false, prune the while statement
383         if (!booleanLiteral.getValue()) {
384           removeMe(x, ctx);
385         }
386       }
387     }
388 
389     /**
390      * TODO: if the AST were normalized, we wouldn't need this.
391      */
392     private boolean isEmpty(JStatement stmt) {
393       if (stmt == null) {
394         return true;
395       }
396       return (stmt instanceof JBlock && ((JBlock) stmt).statements.isEmpty());
397     }
398 
399     private Class   mapType(JType type) {
400       return (Class  ) typeClassMap.get(type);
401     }
402 
403     private void removeMe(JStatement stmt, Context ctx) {
404       if (ctx.canRemove()) {
405         ctx.removeMe();
406       } else {
407         // empty block statement
408         ctx.replaceMe(new JBlock(program, stmt.getSourceInfo()));
409       }
410     }
411 
412     /**
413      * Replace String methods having literal args with the static result.
414      */
415     private void tryOptimizeStringCall(JMethodCall x, Context ctx,
416         JMethod method) {
417 
418       if (method.getType() == program.getTypeVoid()) {
419         return;
420       }
421 
422       int skip = 0;
423       Object   instance;
424       if (program.isStaticImpl(method)) {
425         // is it static implementation for instance method?
426         method = program.staticImplFor(method);
427         instance = tryTranslateLiteral((JExpression) x.getArgs().get(0),
428             String  .class);
429         skip = 1;
430       } else {
431         // instance may be null
432         instance = tryTranslateLiteral(x.getInstance(), String  .class);
433       }
434 
435       if (instance == null && !method.isStatic()) {
436         return;
437       }
438 
439       List   params = method.getOriginalParamTypes();
440       Class   paramTypes[] = new Class  [params.size()];
441       Object   paramValues[] = new Object  [params.size()];
442       ArrayList   args = x.getArgs();
443       for (int i = 0; i != params.size(); ++i) {
444         paramTypes[i] = mapType((JType) params.get(i));
445         if (paramTypes[i] == null) {
446           return;
447         }
448         paramValues[i] = tryTranslateLiteral((JExpression) args.get(i + skip),
449             paramTypes[i]);
450         if (paramValues[i] == null) {
451           return;
452         }
453       }
454 
455       try {
456         Method actual = String  .class.getMethod(method.getName(), paramTypes);
457         if (actual == null) {
458           return;
459         }
460         Object   result = actual.invoke(instance, paramValues);
461         if (result instanceof String  ) {
462           ctx.replaceMe(program.getLiteralString((String  ) result));
463         } else if (result instanceof Boolean  ) {
464           ctx.replaceMe(program.getLiteralBoolean(((Boolean  ) result).booleanValue()));
465         } else if (result instanceof Character  ) {
466           ctx.replaceMe(program.getLiteralChar(((Character  ) result).charValue()));
467         } else if (result instanceof Integer  ) {
468           ctx.replaceMe(program.getLiteralInt(((Integer  ) result).intValue()));
469         } else {
470           boolean stopHere = true;
471         }
472       } catch (Exception   e) {
473         // If the call threw an exception, just don't optimize
474         boolean stopHere = true;
475       }
476     }
477 
478     private Object   tryTranslateLiteral(JExpression maybeLit, Class   type) {
479       if (!(maybeLit instanceof JValueLiteral)) {
480         return null;
481       }
482       // TODO: make this way better by a mile
483       if (type == boolean.class && maybeLit instanceof JBooleanLiteral) {
484         return Boolean.valueOf(((JBooleanLiteral) maybeLit).getValue());
485       }
486       if (type == char.class && maybeLit instanceof JCharLiteral) {
487         return new Character  (((JCharLiteral) maybeLit).getValue());
488       }
489       if (type == double.class && maybeLit instanceof JDoubleLiteral) {
490         return new Double  (((JDoubleLiteral) maybeLit).getValue());
491       }
492       if (type == float.class && maybeLit instanceof JIntLiteral) {
493         return new Float  (((JIntLiteral) maybeLit).getValue());
494       }
495       if (type == int.class && maybeLit instanceof JIntLiteral) {
496         return new Integer  (((JIntLiteral) maybeLit).getValue());
497       }
498       if (type == long.class && maybeLit instanceof JLongLiteral) {
499         return new Long  (((JLongLiteral) maybeLit).getValue());
500       }
501       if (type == String  .class && maybeLit instanceof JStringLiteral) {
502         return ((JStringLiteral) maybeLit).getValue();
503       }
504       if (type == Object  .class && maybeLit instanceof JValueLiteral) {
505         return ((JValueLiteral) maybeLit).getValueObj();
506       }
507       return null;
508     }
509   }
510 
511   /**
512    * Examines code to find out whether it contains any break or continue
513    * statements.
514    */
515   public static class FindBreakContinueStatementsVisitor extends JVisitor {
516     private boolean hasBreakContinueStatements = false;
517 
518     public void endVisit(JBreakStatement x, Context ctx) {
519       hasBreakContinueStatements = true;
520     }
521 
522     public void endVisit(JContinueStatement x, Context ctx) {
523       hasBreakContinueStatements = true;
524     }
525 
526     protected boolean hasBreakContinueStatements() {
527       return hasBreakContinueStatements;
528     }
529   }
530 
531   public static boolean exec(JProgram program) {
532     return new DeadCodeElimination(program).execImpl();
533   }
534 
535   private final JProgram program;
536 
537   private final Map   typeClassMap = new IdentityHashMap  ();
538 
539   public DeadCodeElimination(JProgram program) {
540     this.program = program;
541     typeClassMap.put(program.getTypeJavaLangObject(), Object  .class);
542     typeClassMap.put(program.getTypeJavaLangString(), String  .class);
543     typeClassMap.put(program.getTypePrimitiveBoolean(), boolean.class);
544     typeClassMap.put(program.getTypePrimitiveByte(), byte.class);
545     typeClassMap.put(program.getTypePrimitiveChar(), char.class);
546     typeClassMap.put(program.getTypePrimitiveDouble(), double.class);
547     typeClassMap.put(program.getTypePrimitiveFloat(), float.class);
548     typeClassMap.put(program.getTypePrimitiveInt(), int.class);
549     typeClassMap.put(program.getTypePrimitiveLong(), long.class);
550     typeClassMap.put(program.getTypePrimitiveShort(), short.class);
551   }
552 
553   private boolean execImpl() {
554     boolean madeChanges = false;
555     while (true) {
556       DeadCodeVisitor deadCodeVisitor = new DeadCodeVisitor();
557       deadCodeVisitor.accept(program);
558       if (!deadCodeVisitor.didChange()) {
559         break;
560       }
561       madeChanges = true;
562     }
563     return madeChanges;
564   }
565 }
566
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags