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: import soot.toolkits.graph.*;
036:
037: /**
038: * "unrolls" the condition of while/for loops.<br>
039: * before the first test of a while-loop, we can't be sure, if the body will be
040: * taken or not, and several optimizations (especially LCM) can't be done. In
041: * this class we try to solve this problem by unrolling the condition of the
042: * while-block: we make a copy of the condition-block, and redirect the
043: * back-edge of the while-loop to the new block.<br>
044: * After this transformation the edge between the original condition-block and
045: * the loop-body is only executed once (and hence suitable for LCM) and we can
046: * be sure, that the loop-body will get executed.<br>
047: * Exceptions are ignored (the transformation is done on a
048: * <code>BriefBlockGraph</code>.
049: */
050: public class LoopConditionUnroller extends BodyTransformer {
051: /**
052: * contained blocks are currently visiting successors. We need this to find
053: * back-edges. The "visitedBlocks" is not enough, as Java Bytecodes migth not
054: * be in tree-form.
055: */
056: private Set<Block> visitingSuccs;
057:
058: private Set<Block> visitedBlocks;
059: private int maxSize;
060: private Body body;
061:
062: private Map<Unit, List> unitsToTraps;
063:
064: /**
065: * unrolls conditions.
066: */
067: /* this implementation still fails in finding all possible while-loops, but
068: * does a good job. */
069: protected void internalTransform(Body body, String phaseName,
070: Map options) {
071: if (Options.v().verbose())
072: G.v().out.println("[" + body.getMethod().getName()
073: + "] Unrolling Loop Conditions...");
074:
075: visitingSuccs = new HashSet<Block>();
076: visitedBlocks = new HashSet<Block>();
077: this .body = body;
078: this .maxSize = PhaseOptions.getInt(options, "maxSize");
079:
080: BlockGraph bg = new BriefBlockGraph(body);
081: Iterator headIter = bg.getHeads().iterator();
082: while (headIter.hasNext())
083: unrollConditions((Block) headIter.next());
084:
085: if (Options.v().verbose())
086: G.v().out.println("[" + body.getMethod().getName()
087: + "] Unrolling Loop Conditions done.");
088: }
089:
090: /**
091: * inserts a Jimple<code>Goto</code> to <code> target, directly after
092: * <code>node</code> in the <code>unitChain</code> of the body.<br>
093: * As we use <code>JGoto</code> the chain must contain Jimple-stmts.
094: *
095: * @param node the <code>Goto</code> will be inserted just after this node.
096: * @param target is the Unit the <code>goto</code> will jump to.
097: * @return the newly inserted <code>Goto</code>
098: */
099: private Unit insertGotoAfter(Unit node, Unit target) {
100: Unit newGoto = Jimple.v().newGotoStmt(target);
101: body.getUnits().insertAfter(newGoto, node);
102: return newGoto;
103: }
104:
105: /**
106: * inserts a clone of <code>toClone</code> after <code>node</code> in the
107: * <code>unitChain</code>.<br>
108: * Everything is done in Jimple.
109: *
110: * @param node the Unit after which we insert the clone.
111: * @param toClone the Unit that will get cloned and then inserted.
112: */
113: private Unit insertCloneAfter(Chain unitChain, Unit node,
114: Unit toClone) {
115: Unit clone = (Unit) toClone.clone();
116: body.getUnits().insertAfter(clone, node);
117: return clone;
118: }
119:
120: /**
121: * "calculates" the length of the given block in Units.
122: *
123: * @param block
124: * @return the size of <code>block</code>.
125: */
126: private int getSize(Block block) {
127: int size = 0;
128: Chain unitChain = body.getUnits();
129: for (Unit unit = block.getHead(); unit != block.getTail(); unit = (Unit) unitChain
130: .getSuccOf(unit))
131: size++;
132: size++; //add 1 for the tail we did not take into account.
133: return size;
134: }
135:
136: /**
137: * returns a mapping of units to trap-changes. whenever the scope of
138: * a trap changes (ie. a trap opens or closes), an entry is added in
139: * the map, and the unit is mapped to the trap. The values
140: * associated to the keys are lists, as more than one exception can
141: * change at a unit.<br> Even if a trap opens and closes at a unit,
142: * this trap is only reported once (ie. is only once in the list).
143: *
144: * @return the map of units to changing traps. */
145: private Map<Unit, List> getTraps() {
146: /* if we already did the "calculation" return the cached result.*/
147: if (unitsToTraps != null)
148: return unitsToTraps;
149: unitsToTraps = new HashMap<Unit, List>();
150: Iterator trapsIt = body.getTraps().iterator();
151: while (trapsIt.hasNext()) {
152: Trap trap = (Trap) trapsIt.next();
153: Unit beginUnit = trap.getBeginUnit();
154: List<Trap> unitTraps = unitsToTraps.get(beginUnit);
155: if (unitTraps == null) {
156: unitTraps = new ArrayList<Trap>();
157: unitsToTraps.put(beginUnit, unitTraps);
158: }
159: unitTraps.add(trap);
160: Unit endUnit = trap.getEndUnit();
161: if (endUnit != beginUnit) {
162: unitTraps = unitsToTraps.get(endUnit);
163: if (unitTraps == null) {
164: unitTraps = new ArrayList<Trap>();
165: unitsToTraps.put(endUnit, unitTraps);
166: }
167: unitTraps.add(trap);
168: }
169: }
170: return unitsToTraps;
171: }
172:
173: /**
174: * puts a copy (clone) of the given block in the unitChain. The
175: * block is ensured to have the same exceptions as the original
176: * block. (So we will modify the exception-chain). Furthermore the
177: * inserted block will not change the behaviour of the program.<br>
178: * Without any further modifications the returned block is
179: * unreachable. To make it reachable one must <code>goto</code> to
180: * the returned head of the new block.
181: *
182: * @param block the Block to clone.
183: * @return the head of the copied block. */
184: private Unit copyBlock(Block block) {
185: Map<Unit, List> traps = getTraps();
186: Set<Trap> openedTraps = new HashSet<Trap>();
187: Map<Trap, Trap> copiedTraps = new HashMap<Trap, Trap>();
188: Chain unitChain = body.getUnits();
189:
190: Unit tail = block.getTail();
191: Unit immediateSucc = (Unit) unitChain.getSuccOf(tail);
192: Unit newGoto = insertGotoAfter(tail, immediateSucc);
193: Unit last = newGoto; //the last inserted unit.
194: boolean first = true;
195: Unit copiedHead = null;
196: for (Unit currentUnit = block.getHead(); currentUnit != newGoto; currentUnit = (Unit) unitChain
197: .getSuccOf(currentUnit)) {
198: last = insertCloneAfter(unitChain, last, currentUnit);
199: if (first) {
200: first = false;
201: copiedHead = last;
202: }
203: /* the traps...: if a trap is closed (in the original block) that hasn't
204: * been opened before, we have to open it at the beginning of the copied
205: * block. If a trap gets opened, but not closed, we only have to close it
206: * at the end of the (original) block (as it will be open at the end of
207: * the copied block.)*/
208: List currentTraps = traps.get(currentUnit);
209: if (currentTraps != null) {
210: Iterator trapIt = currentTraps.iterator();
211: while (trapIt.hasNext()) {
212: Trap trap = (Trap) trapIt.next();
213: if (trap.getBeginUnit() == currentUnit) {
214: Trap copiedTrap = (Trap) trap.clone();
215: copiedTrap.setBeginUnit(last);
216: copiedTraps.put(trap, copiedTrap);
217:
218: openedTraps.add(copiedTrap);
219: // insertAfter(toInsert, point)
220: body.getTraps().insertAfter(copiedTrap, trap);
221:
222: }
223: if (trap.getEndUnit() == currentUnit) {
224: Trap copiedTrap = copiedTraps.get(trap);
225: if (copiedTrap == null) {
226: /* trap has been opened before the current block */
227: copiedTrap = (Trap) trap.clone();
228: copiedTrap.setBeginUnit(copiedHead);
229:
230: body.getTraps().insertAfter(copiedTrap,
231: trap);
232: } else {
233: openedTraps.remove(copiedTrap);
234: }
235:
236: copiedTrap.setEndUnit(last);
237: }
238: }
239: }
240: }
241: /* close all open traps */
242: Iterator<Trap> openedIterator = openedTraps.iterator();
243: while (openedIterator.hasNext()) {
244: openedIterator.next().setEndUnit(last);
245: }
246: return copiedHead;
247: }
248:
249: /**
250: * recursively searches for back-edges. if the found block is a
251: * condition-block makes a clone and redirects the back-edge.
252: *
253: * @param block the current Block.
254: */
255: private void unrollConditions(Block block) {
256: /* if the block was already visited we can leave... */
257: if (visitedBlocks.contains(block))
258: return; // should never happen
259: visitedBlocks.add(block);
260: visitingSuccs.add(block); //currently visiting successors
261: Iterator succsIt = block.getSuccs().iterator();
262: while (succsIt.hasNext()) {
263: Block succ = (Block) succsIt.next();
264:
265: if (visitedBlocks.contains(succ)) {
266: if (succ != block && visitingSuccs.contains(succ)) {
267: /* we only want blocks with at least 2 predecessors, to avoid that a
268: * copied while-condition gets copied again in a future pass of
269: * unrollConditions */
270: if (succ.getPreds().size() >= 2
271: && succ.getSuccs().size() == 2) {
272: Block condition = succ; //just renaming for clearer code
273: Block loopTailBlock = block; //just renaming for clearer code
274:
275: if (getSize(condition) <= maxSize) {
276: Unit copiedHead = copyBlock(condition);
277: /* now just redirect the tail of the loop-body */
278: Unit loopTail = loopTailBlock.getTail();
279: if (loopTail instanceof GotoStmt)
280: ((GotoStmt) loopTail)
281: .setTarget(copiedHead);
282: else if (loopTail instanceof IfStmt) {
283: if (((IfStmt) loopTail).getTarget() == condition
284: .getHead())
285: ((IfStmt) loopTail)
286: .setTarget(copiedHead);
287: else
288: insertGotoAfter(loopTail,
289: copiedHead);
290: } else
291: insertGotoAfter(loopTail, copiedHead);
292: }
293: }
294: }
295: } else {
296: /* unvisited successor */
297: unrollConditions(succ);
298: }
299: }
300: visitingSuccs.remove(block);
301: }
302: }
|