001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2002 Florian Loitsch
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-2002.
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.graph;
027:
028: import soot.options.*;
029:
030: import soot.*;
031: import soot.util.*;
032: import java.util.*;
033:
034: import soot.jimple.*;
035:
036: /**
037: * removes all critical edges.<br>
038: * A critical edge is an edge from Block A to block B, if B has more than one
039: * predecessor and A has more the one successor.<br>
040: * As an example: If we wanted a computation to be only on the path A->B
041: * this computation must be directly on the edge. Otherwise it is either
042: * executed on the path through the second predecessor of A or throught the
043: * second successor of B.<br>
044: * Our critical edge-remover overcomes this problem by introducing synthetic
045: * nodes on this critical edges.<br>
046: * Exceptions will be ignored.
047: */
048: public class CriticalEdgeRemover extends BodyTransformer {
049: public CriticalEdgeRemover(Singletons.Global g) {
050: }
051:
052: public static CriticalEdgeRemover v() {
053: return G.v().soot_jimple_toolkits_graph_CriticalEdgeRemover();
054: }
055:
056: /**
057: * performs critical edge-removing.
058: */
059: protected void internalTransform(Body b, String phaseName,
060: Map options) {
061: if (Options.v().verbose())
062: G.v().out.println("[" + b.getMethod().getName()
063: + "] Removing Critical Edges...");
064: removeCriticalEdges(b);
065: if (Options.v().verbose())
066: G.v().out.println("[" + b.getMethod().getName()
067: + "] Removing Critical Edges done.");
068:
069: }
070:
071: /**
072: * inserts a Jimple<code>Goto</code> to <code> target, directly after
073: * <code>node</code> in the given <code>unitChain</code>.<br>
074: * As we use <code>JGoto</code> the chain must contain Jimple-stmts.
075: *
076: * @param unitChain the Chain where we will insert the <code>Goto</code>.
077: * @param node the <code>Goto</code> will be inserted just after this node.
078: * @param target is the Unit the <code>goto</code> will jump to.
079: * @return the newly inserted <code>Goto</code>
080: */
081: private static Unit insertGotoAfter(Chain unitChain, Unit node,
082: Unit target) {
083: Unit newGoto = Jimple.v().newGotoStmt(target);
084: unitChain.insertAfter(newGoto, node);
085: return newGoto;
086: }
087:
088: /**
089: * inserts a Jimple<code>Goto</code> to <code> target, directly before
090: * <code>node</code> in the given <code>unitChain</code>.<br>
091: * As we use <code>JGoto</code> the chain must contain Jimple-stmts.
092: *
093: * @param unitChain the Chain where we will insert the <code>Goto</code>.
094: * @param node the <code>Goto</code> will be inserted just before this node.
095: * @param target is the Unit the <code>goto</code> will jump to.
096: * @return the newly inserted <code>Goto</code>
097: */
098: /*note, that this method has slightly more overhead than the insertGotoAfter*/
099: private static Unit insertGotoBefore(Chain unitChain, Unit node,
100: Unit target) {
101: Unit newGoto = Jimple.v().newGotoStmt(target);
102: unitChain.insertBefore(newGoto, node);
103: newGoto.redirectJumpsToThisTo(node);
104: return newGoto;
105: }
106:
107: /**
108: * takes <code>node</code> and redirects all branches to <code>oldTarget</code>
109: * to <code>newTarget</code>.
110: *
111: * @param node the Unit where we redirect
112: * @param oldTarget
113: * @param newTarget
114: */
115: private static void redirectBranch(Unit node, Unit oldTarget,
116: Unit newTarget) {
117: Iterator targetIt = node.getUnitBoxes().iterator();
118: while (targetIt.hasNext()) {
119: UnitBox targetBox = (UnitBox) targetIt.next();
120: Unit target = targetBox.getUnit();
121: if (target == oldTarget)
122: targetBox.setUnit(newTarget);
123: }
124: }
125:
126: /**
127: * splits critical edges by introducing synthetic nodes.<br>
128: * This method <b>will modify</b> the <code>UnitGraph</code> of the body.
129: * Synthetic nodes are always <code>JGoto</code>s. Therefore the body must be
130: * in <tt>Jimple</tt>.<br>
131: * As a side-effect, after the transformation, the direct predecessor of a
132: * block/node with multiple predecessors will will not fall through anymore.
133: * This simplifies the algorithm and is nice to work with afterwards.
134: *
135: * @param b the Jimple-body that will be physicly modified so that there are
136: * no critical edges anymore.
137: */
138: /* note, that critical edges can only appear on edges between blocks!.
139: Our algorithm will *not* take into account exceptions. (this is nearly
140: impossible anyways) */
141: private void removeCriticalEdges(Body b) {
142: Chain unitChain = b.getUnits();
143: int size = unitChain.size();
144: Map<Unit, List> predecessors = new HashMap<Unit, List>(
145: 2 * size + 1, 0.7f);
146:
147: /* First get the predecessors of each node (although direct predecessors are
148: * predecessors too, we'll not include them in the lists) */
149: {
150: Iterator unitIt = unitChain.snapshotIterator();
151: while (unitIt.hasNext()) {
152: Unit currentUnit = (Unit) unitIt.next();
153:
154: Iterator succsIt = currentUnit.getUnitBoxes()
155: .iterator();
156: while (succsIt.hasNext()) {
157: Unit target = ((UnitBox) succsIt.next()).getUnit();
158: List<Unit> predList = predecessors.get(target);
159: if (predList == null) {
160: predList = new ArrayList<Unit>();
161: predList.add(currentUnit);
162: predecessors.put(target, predList);
163: } else
164: predList.add(currentUnit);
165: }
166: }
167: }
168:
169: {
170: /* for each node: if we have more than two predecessors, split these edges
171: * if the node at the other end has more than one successor. */
172:
173: /* we need a snapshotIterator, as we'll modify the structure */
174: Iterator unitIt = unitChain.snapshotIterator();
175:
176: Unit currentUnit = null;
177: Unit directPredecessor;
178: while (unitIt.hasNext()) {
179: directPredecessor = currentUnit;
180: currentUnit = (Unit) unitIt.next();
181:
182: List predList = predecessors.get(currentUnit);
183: int nbPreds = (predList == null) ? 0 : predList.size();
184: if (directPredecessor != null
185: && directPredecessor.fallsThrough())
186: nbPreds++;
187:
188: if (nbPreds >= 2) {
189: /* redirect the directPredecessor (if it falls through), so we can
190: * easily insert the synthetic nodes. This redirection might not be
191: * necessary, but is pleasant anyways (see the Javadoc for this
192: * method)*/
193: if (directPredecessor != null
194: && directPredecessor.fallsThrough()) {
195: directPredecessor = insertGotoAfter(unitChain,
196: directPredecessor, currentUnit);
197: }
198:
199: /* if the predecessors have more than one successor insert the synthetic
200: * node. */
201: Iterator predIt = predList.iterator();
202: while (predIt.hasNext()) {
203: Unit predecessor = (Unit) predIt.next();
204: /* Although in Jimple there should be only two ways of having more
205: * than one successor (If and Case) we'll do it the hard way:) */
206: int nbSuccs = predecessor.getUnitBoxes().size();
207: nbSuccs += predecessor.fallsThrough() ? 1 : 0;
208: if (nbSuccs >= 2) {
209: /* insert synthetic node (insertGotoAfter should be slightly
210: * faster)*/
211: if (directPredecessor == null)
212: directPredecessor = insertGotoBefore(
213: unitChain, currentUnit,
214: currentUnit);
215: else
216: directPredecessor = insertGotoAfter(
217: unitChain, directPredecessor,
218: currentUnit);
219: /* update the branch */
220: redirectBranch(predecessor, currentUnit,
221: directPredecessor);
222: }
223: }
224: }
225: }
226: }
227: }
228: }
|