001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 1997-1999 Raja Vallee-Rai
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: /*
021: * Modified by the Sable Research Group and others 1997-1999.
022: * See the 'credits' file distributed with Soot for the complete list of
023: * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
024: */
025:
026: package soot.jimple.toolkits.scalar;
027:
028: import soot.options.*;
029:
030: import soot.*;
031: import soot.jimple.*;
032: import soot.toolkits.scalar.*;
033: import soot.util.*;
034: import soot.toolkits.graph.*;
035: import java.util.*;
036:
037: public class DeadAssignmentEliminator extends BodyTransformer {
038: public DeadAssignmentEliminator(Singletons.Global g) {
039: }
040:
041: public static DeadAssignmentEliminator v() {
042: return G.v()
043: .soot_jimple_toolkits_scalar_DeadAssignmentEliminator();
044: }
045:
046: /** Eliminates dead code in a linear fashion. Complexity is linear
047: with respect to the statements.
048:
049: Does not work on grimp code because of the check on the right hand
050: side for side effects.
051: */
052:
053: protected void internalTransform(Body b, String phaseName,
054: Map options) {
055: boolean eliminateOnlyStackLocals = PhaseOptions.getBoolean(
056: options, "only-stack-locals");
057:
058: if (Options.v().verbose())
059: G.v().out.println("[" + b.getMethod().getName()
060: + "] Eliminating dead code...");
061:
062: if (Options.v().time())
063: Timers.v().deadCodeTimer.start();
064:
065: Set<Stmt> essentialStmts = new HashSet<Stmt>();
066: LinkedList<Stmt> toVisit = new LinkedList<Stmt>();
067: Chain units = b.getUnits();
068:
069: // Make a first pass through the statements, noting
070: // the statements we must absolutely keep.
071: {
072: Iterator stmtIt = units.iterator();
073:
074: while (stmtIt.hasNext()) {
075: Stmt s = (Stmt) stmtIt.next();
076: boolean isEssential = true;
077:
078: if (s instanceof NopStmt)
079: isEssential = false;
080:
081: if (s instanceof AssignStmt) {
082: AssignStmt as = (AssignStmt) s;
083:
084: if (as.getLeftOp() instanceof Local
085: && (!eliminateOnlyStackLocals || ((Local) as
086: .getLeftOp()).getName().startsWith(
087: "$"))) {
088: Value rhs = as.getRightOp();
089:
090: isEssential = false;
091:
092: if (rhs instanceof InvokeExpr
093: || rhs instanceof ArrayRef) {
094: // Note that ArrayRef and InvokeExpr all can
095: // have side effects (like throwing a null pointer exception)
096:
097: isEssential = true;
098: }
099:
100: if (rhs instanceof InstanceFieldRef
101: && !(!b.getMethod().isStatic() && ((InstanceFieldRef) rhs)
102: .getBase() == b.getThisLocal())) {
103: // Any InstanceFieldRef may have side effects,
104: // unless the base is reading from 'this'
105: // in a non-static method
106: isEssential = true;
107: }
108:
109: else if (rhs instanceof DivExpr
110: || rhs instanceof RemExpr) {
111: BinopExpr expr = (BinopExpr) rhs;
112:
113: if (expr.getOp1().getType().equals(
114: IntType.v())
115: || expr.getOp2().getType().equals(
116: IntType.v())
117: || expr.getOp1().getType().equals(
118: LongType.v())
119: || expr.getOp2().getType().equals(
120: LongType.v())) {
121: // Can trigger a division by zero
122: isEssential = true;
123: }
124: }
125:
126: else if (rhs instanceof CastExpr) {
127: // Can trigger ClassCastException
128: isEssential = true;
129: } else if (rhs instanceof NewArrayExpr
130: || rhs instanceof NewMultiArrayExpr) {
131: // can throw exception
132: isEssential = true;
133: } else if (rhs instanceof NewExpr
134: || (rhs instanceof FieldRef && !(rhs instanceof InstanceFieldRef))) {
135: // Can trigger class initialization
136: isEssential = true;
137: }
138: }
139: }
140:
141: if (isEssential) {
142: essentialStmts.add(s);
143: toVisit.addLast(s);
144: }
145: }
146: }
147:
148: ExceptionalUnitGraph graph = new ExceptionalUnitGraph(b);
149: LocalDefs defs = new SmartLocalDefs(graph,
150: new SimpleLiveLocals(graph));
151: LocalUses uses = new SimpleLocalUses(graph, defs);
152:
153: // Add all the statements which are used to compute values
154: // for the essential statements, recursively
155: {
156:
157: while (!toVisit.isEmpty()) {
158: Stmt s = toVisit.removeFirst();
159: Iterator boxIt = s.getUseBoxes().iterator();
160:
161: while (boxIt.hasNext()) {
162: ValueBox box = (ValueBox) boxIt.next();
163:
164: if (box.getValue() instanceof Local) {
165: Iterator<Unit> defIt = defs.getDefsOfAt(
166: (Local) box.getValue(), s).iterator();
167:
168: while (defIt.hasNext()) {
169: // Add all the definitions as essential stmts
170:
171: Stmt def = (Stmt) defIt.next();
172:
173: if (!essentialStmts.contains(def)) {
174: essentialStmts.add(def);
175: toVisit.addLast(def);
176: }
177: }
178: }
179: }
180: }
181: }
182:
183: // Remove the dead statements
184: {
185: Iterator stmtIt = units.iterator();
186:
187: while (stmtIt.hasNext()) {
188: Stmt s = (Stmt) stmtIt.next();
189:
190: if (!essentialStmts.contains(s)) {
191: stmtIt.remove();
192: s.clearUnitBoxes();
193: } else if (s instanceof AssignStmt
194: && ((AssignStmt) s).getLeftOp() == ((AssignStmt) s)
195: .getRightOp()
196: && ((AssignStmt) s).getLeftOp() instanceof Local) {
197: // Stmt is of the form a = a which is useless
198:
199: stmtIt.remove();
200: s.clearUnitBoxes();
201: }
202: }
203: }
204:
205: // Eliminate dead assignments from invokes such as x = f(), where
206: // x is no longer used
207: {
208: Iterator stmtIt = units.snapshotIterator();
209:
210: while (stmtIt.hasNext()) {
211: Stmt s = (Stmt) stmtIt.next();
212:
213: if (s instanceof AssignStmt && s.containsInvokeExpr()) {
214: Local l = (Local) ((AssignStmt) s).getLeftOp();
215: InvokeExpr e = s.getInvokeExpr();
216:
217: // Just find one use of l which is essential
218: {
219: Iterator useIt = uses.getUsesOf(s).iterator();
220: boolean isEssential = false;
221:
222: while (useIt.hasNext()) {
223: UnitValueBoxPair pair = (UnitValueBoxPair) useIt
224: .next();
225:
226: if (essentialStmts.contains(pair.unit)) {
227: isEssential = true;
228: break;
229: }
230: }
231:
232: if (!isEssential) {
233: // Transform it into a simple invoke.
234:
235: Stmt newInvoke = Jimple.v()
236: .newInvokeStmt(e);
237: newInvoke.addAllTagsOf(s);
238:
239: units.swapWith(s, newInvoke);
240: }
241: }
242: }
243: }
244: }
245:
246: if (Options.v().time())
247: Timers.v().deadCodeTimer.end();
248:
249: }
250: }
|