001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 1999 Phong Co
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-2003.
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.util.*;
031: import soot.*;
032: import soot.jimple.*;
033: import java.util.*;
034:
035: import soot.toolkits.graph.*;
036: import soot.toolkits.exceptions.PedanticThrowAnalysis;
037:
038: public class UnreachableCodeEliminator extends BodyTransformer {
039: public UnreachableCodeEliminator(Singletons.Global g) {
040: }
041:
042: public static UnreachableCodeEliminator v() {
043: return G
044: .v()
045: .soot_jimple_toolkits_scalar_UnreachableCodeEliminator();
046: }
047:
048: protected void internalTransform(Body b, String phaseName,
049: Map options) {
050: new Instance().internalTransform(b, phaseName, options);
051: }
052:
053: class Instance {
054: ExceptionalUnitGraph stmtGraph;
055: HashSet<Object> visited;
056: int numPruned;
057:
058: protected void internalTransform(Body b, String phaseName,
059: Map options) {
060: StmtBody body = (StmtBody) b;
061:
062: if (Options.v().verbose())
063: G.v().out.println("[" + body.getMethod().getName()
064: + "] Eliminating unreachable code...");
065:
066: numPruned = 0;
067:
068: if (PhaseOptions.getBoolean(options,
069: "remove-unreachable-traps")) {
070: stmtGraph = new ExceptionalUnitGraph(body);
071: } else {
072: // Force a conservative ExceptionalUnitGraph() which
073: // necessarily includes an edge from every trapped Unit to
074: // its handler, so that we retain Traps in the case where
075: // trapped units remain, but the default ThrowAnalysis
076: // says that none of them can throw the caught exception.
077: stmtGraph = new ExceptionalUnitGraph(body,
078: PedanticThrowAnalysis.v(), false);
079: }
080: visited = new HashSet<Object>();
081:
082: // We need a map from Units that handle Traps, to a Set of their
083: // Traps, so we can remove the Traps should we remove the handler.
084: Map<Unit, Set> handlerToTraps = new HashMap<Unit, Set>();
085: for (Iterator trapIt = body.getTraps().iterator(); trapIt
086: .hasNext();) {
087: final Trap trap = (Trap) trapIt.next();
088: Unit handler = trap.getHandlerUnit();
089: Set<Trap> handlersTraps = handlerToTraps.get(handler);
090: if (handlersTraps == null) {
091: handlersTraps = new ArraySet(3);
092: handlerToTraps.put(handler, handlersTraps);
093: }
094: handlersTraps.add(trap);
095: }
096:
097: // Used to be: "mark first statement and all its successors, recursively"
098: // Bad idea! Some methods are extremely long. It broke because the recursion reached the
099: // 3799th level.
100:
101: if (!body.getUnits().isEmpty()) {
102: LinkedList<Unit> startPoints = new LinkedList<Unit>();
103: startPoints.addLast(body.getUnits().getFirst());
104:
105: visitStmts(startPoints);
106: }
107:
108: Iterator stmtIt = body.getUnits().snapshotIterator();
109: while (stmtIt.hasNext()) {
110: // find unmarked nodes
111: Stmt stmt = (Stmt) stmtIt.next();
112:
113: if (!visited.contains(stmt)) {
114: body.getUnits().remove(stmt);
115: Set traps = handlerToTraps.get(stmt);
116: if (traps != null) {
117: for (Iterator trapIt = traps.iterator(); trapIt
118: .hasNext();) {
119: final Trap trap = (Trap) trapIt.next();
120: body.getTraps().remove(trap);
121: }
122: }
123: numPruned++;
124: }
125: }
126: if (Options.v().verbose())
127: G.v().out.println("[" + body.getMethod().getName()
128: + "] Removed " + numPruned
129: + " statements...");
130:
131: // Now eliminate empty traps.
132: //
133: // For the most part, this is an atavism, an an artifact of
134: // pre-ExceptionalUnitGraph code, when the only way for a trap to
135: // become unreachable was if all its trapped units were removed, and
136: // the stmtIt loop did not remove Traps as it removed handler units.
137: // We've left this separate test for empty traps here, even though
138: // most such traps would already have been eliminated by the preceding
139: // loop, because in arbitrary bytecode you could have
140: // handler unit that was still reachable by normal control flow, even
141: // though it no longer trapped any units (though such code is unlikely
142: // to occur in practice, and certainly no in code generated from Java
143: // source.
144: {
145: Iterator trapIt = b.getTraps().iterator();
146:
147: while (trapIt.hasNext()) {
148: Trap t = (Trap) trapIt.next();
149:
150: if (t.getBeginUnit() == t.getEndUnit())
151: trapIt.remove();
152: }
153: }
154:
155: } // pruneUnreachables
156:
157: private void visitStmts(LinkedList<Unit> st) {
158:
159: // Do DFS of the unit graph, starting from the passed nodes.
160:
161: while (!st.isEmpty()) {
162: Unit stmt = st.removeLast();
163: if (!visited.contains(stmt)) {
164: visited.add(stmt);
165: Iterator<Unit> succIt = stmtGraph.getSuccsOf(stmt)
166: .iterator();
167: while (succIt.hasNext()) {
168: Unit o = succIt.next();
169: if (!visited.contains(o))
170: st.addLast(o);
171: }
172: }
173: }
174: } // visitStmts
175:
176: }
177: } // UnreachablePruner
|