KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > graph > LoopConditionUnroller


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2002 Florian Loitsch
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19
20 /*
21  * Modified by the Sable Research Group and others 1997-2002.
22  * See the 'credits' file distributed with Soot for the complete list of
23  * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
24  */
25
26 package soot.jimple.toolkits.graph;
27 import soot.options.*;
28
29
30 import soot.*;
31 import soot.util.*;
32 import java.util.*;
33 import soot.jimple.*;
34 import soot.toolkits.graph.*;
35 import soot.jimple.internal.*;
36
37 /**
38  * "unrolls" the condition of while/for loops.<br>
39  * before the first test of a while-loop, we can't be sure, if the body will be
40  * taken or not, and several optimizations (especially LCM) can't be done. In
41  * this class we try to solve this problem by unrolling the condition of the
42  * while-block: we make a copy of the condition-block, and redirect the
43  * back-edge of the while-loop to the new block.<br>
44  * After this transformation the edge between the original condition-block and
45  * the loop-body is only executed once (and hence suitable for LCM) and we can
46  * be sure, that the loop-body will get executed.<br>
47  * Exceptions are ignored (the transformation is done on a
48  * <code>BriefBlockGraph</code>.
49  */
50 public class LoopConditionUnroller extends BodyTransformer {
51   /**
52    * contained blocks are currently visiting successors. We need this to find
53    * back-edges. The "visitedBlocks" is not enough, as Java Bytecodes migth not
54    * be in tree-form.
55    */
56   private Set visitingSuccs;
57
58   private Set visitedBlocks;
59   private int maxSize;
60   private Body body;
61
62   private Map unitsToTraps;
63
64   /**
65    * unrolls conditions.
66    */
67   /* this implementation still fails in finding all possible while-loops, but
68    * does a good job. */
69   protected void internalTransform(Body body, String JavaDoc phaseName, Map options) {
70     if(Options.v().verbose())
71       G.v().out.println("[" + body.getMethod().getName() +
72                          "] Unrolling Loop Conditions...");
73
74     visitingSuccs = new HashSet();
75     visitedBlocks = new HashSet();
76     this.body = body;
77     this.maxSize = PhaseOptions.getInt(options, "maxSize");
78     
79     BlockGraph bg = new BriefBlockGraph(body);
80     Iterator headIter = bg.getHeads().iterator();
81     while (headIter.hasNext())
82       unrollConditions((Block)headIter.next());
83
84     if(Options.v().verbose())
85       G.v().out.println("[" + body.getMethod().getName() +
86                          "] Unrolling Loop Conditions done.");
87   }
88     
89   /**
90    * inserts a Jimple<code>Goto</code> to <code> target, directly after
91    * <code>node</code> in the <code>unitChain</code> of the body.<br>
92    * As we use <code>JGoto</code> the chain must contain Jimple-stmts.
93    *
94    * @param node the <code>Goto</code> will be inserted just after this node.
95    * @param target is the Unit the <code>goto</code> will jump to.
96    * @return the newly inserted <code>Goto</code>
97    */
98   private Unit insertGotoAfter(Unit node, Unit target) {
99     Unit newGoto = Jimple.v().newGotoStmt(target);
100     body.getUnits().insertAfter(newGoto, node);
101     return newGoto;
102   }
103
104   /**
105    * inserts a clone of <code>toClone</code> after <code>node</code> in the
106    * <code>unitChain</code>.<br>
107    * Everything is done in Jimple.
108    *
109    * @param node the Unit after which we insert the clone.
110    * @param toClone the Unit that will get cloned and then inserted.
111    */
112   private Unit insertCloneAfter(Chain unitChain, Unit node, Unit toClone)
113   {
114     Unit clone = (Unit)toClone.clone();
115     body.getUnits().insertAfter(clone, node);
116     return clone;
117   }
118
119   /**
120    * inserts a Jimple<code>Goto</code> to <code> target, directly before
121    * <code>node</code> in the <code>unitChain</code> of the body.<br>
122    *
123    * @param node the <code>Goto</code> will be inserted just before this node.
124    * @param target is the Unit the <code>goto</code> will jump to.
125    * @return the newly inserted <code>Goto</code>
126    */
127   /*note, that this method has slightly more overhead than the insertGotoAfter*/
128   private Unit insertGotoBefore(Chain unitChain, Unit node, Unit target)
129   {
130     Unit newGoto = Jimple.v().newGotoStmt(target);
131     body.getUnits().insertBefore(newGoto, node);
132     newGoto.redirectJumpsToThisTo(node);
133     return newGoto;
134   }
135
136   /**
137    * takes <code>node</code> and redirects all branches to <code>oldTarget</code>
138    * to <code>newTarget</code>.
139    *
140    * @param node the Unit where we redirect
141    * @param oldTarget
142    * @param newTarget
143    **/
144   private void redirectBranch(Unit node, Unit oldTarget, Unit newTarget) {
145     Iterator targetIt = node.getUnitBoxes().iterator();
146     while (targetIt.hasNext()) {
147       UnitBox targetBox = (UnitBox)targetIt.next();
148       Unit target = (Unit)targetBox.getUnit();
149       if (target == oldTarget)
150         targetBox.setUnit(newTarget);
151     }
152   }
153
154   /**
155    * "calculates" the length of the given block in Units.
156    *
157    * @param block
158    * @return the size of <code>block</code>.
159    */
160   private int getSize(Block block) {
161     int size = 0;
162     Chain unitChain = body.getUnits();
163     for (Unit unit = block.getHead(); unit != block.getTail();
164          unit = (Unit)unitChain.getSuccOf(unit))
165       size++;
166     size++; //add 1 for the tail we did not take into account.
167 return size;
168   }
169
170   /**
171    * returns a mapping of units to trap-changes. whenever the scope of
172    * a trap changes (ie. a trap opens or closes), an entry is added in
173    * the map, and the unit is mapped to the trap. The values
174    * associated to the keys are lists, as more than one exception can
175    * change at a unit.<br> Even if a trap opens and closes at a unit,
176    * this trap is only reported once (ie. is only once in the list).
177    *
178    * @return the map of units to changing traps. */
179   private Map getTraps() {
180     /* if we already did the "calculation" return the cached result.*/
181     if (unitsToTraps != null)
182       return unitsToTraps;
183     unitsToTraps = new HashMap();
184     Iterator trapsIt = body.getTraps().iterator();
185     while (trapsIt.hasNext()) {
186       Trap trap = (Trap)trapsIt.next();
187       Unit beginUnit = trap.getBeginUnit();
188       List unitTraps = (List)unitsToTraps.get(beginUnit);
189       if (unitTraps == null) {
190         unitTraps = new ArrayList();
191         unitsToTraps.put(beginUnit, unitTraps);
192       }
193       unitTraps.add(trap);
194       Unit endUnit = trap.getEndUnit();
195       if (endUnit != beginUnit) {
196         unitTraps = (List)unitsToTraps.get(endUnit);
197         if (unitTraps == null) {
198           unitTraps = new ArrayList();
199           unitsToTraps.put(endUnit, unitTraps);
200         }
201         unitTraps.add(trap);
202       }
203     }
204     return unitsToTraps;
205   }
206     
207   /**
208    * puts a copy (clone) of the given block in the unitChain. The
209    * block is ensured to have the same exceptions as the original
210    * block. (So we will modify the exception-chain). Furthermore the
211    * inserted block will not change the behaviour of the program.<br>
212    * Without any further modifications the returned block is
213    * unreachable. To make it reachable one must <code>goto</code> to
214    * the returned head of the new block.
215    *
216    * @param block the Block to clone.
217    * @return the head of the copied block. */
218   private Unit copyBlock(Block block) {
219     Map traps = getTraps();
220     Set openedTraps = new HashSet();
221     Map copiedTraps = new HashMap();
222     Chain unitChain = body.getUnits();
223
224     Unit tail = block.getTail();
225     Unit immediateSucc = (Unit)unitChain.getSuccOf(tail);
226     Unit newGoto = insertGotoAfter(tail, immediateSucc);
227     Unit last = newGoto; //the last inserted unit.
228 boolean first = true;
229     Unit copiedHead = null;
230     for (Unit currentUnit = block.getHead(); currentUnit != newGoto;
231          currentUnit = (Unit)unitChain.getSuccOf(currentUnit)) {
232       last = insertCloneAfter(unitChain, last, currentUnit);
233       if (first) {
234         first = false;
235         copiedHead = last;
236       }
237       /* the traps...: if a trap is closed (in the original block) that hasn't
238        * been opened before, we have to open it at the beginning of the copied
239        * block. If a trap gets opened, but not closed, we only have to close it
240        * at the end of the (original) block (as it will be open at the end of
241        * the copied block.)*/
242       List currentTraps = (List)traps.get(currentUnit);
243       if (currentTraps != null) {
244         Iterator trapIt = currentTraps.iterator();
245         while(trapIt.hasNext()) {
246           Trap trap = (Trap)trapIt.next();
247           if (trap.getBeginUnit() == currentUnit) {
248             Trap copiedTrap = (Trap)trap.clone();
249             copiedTrap.setBeginUnit(last);
250             copiedTraps.put(trap, copiedTrap);
251
252             openedTraps.add(copiedTrap);
253             // insertAfter(toInsert, point)
254 body.getTraps().insertAfter(copiedTrap, trap);
255
256           }
257           if (trap.getEndUnit() == currentUnit) {
258             Trap copiedTrap = (Trap)copiedTraps.get(trap);
259             if (copiedTrap == null) {
260               /* trap has been opened before the current block */
261               copiedTrap = (Trap)trap.clone();
262               copiedTrap.setBeginUnit(copiedHead);
263
264               body.getTraps().insertAfter(copiedTrap, trap);
265             } else {
266           openedTraps.remove(copiedTrap);
267         }
268
269             copiedTrap.setEndUnit(last);
270           }
271         }
272       }
273     }
274     /* close all open traps */
275     Iterator openedIterator = openedTraps.iterator();
276     while(openedIterator.hasNext()) {
277       ((Trap)openedIterator.next()).setEndUnit(last);
278     }
279     return copiedHead;
280   }
281
282   /**
283    * recursively searches for back-edges. if the found block is a
284    * condition-block makes a clone and redirects the back-edge.
285    *
286    * @param block the current Block.
287    */
288   private void unrollConditions(Block block) {
289     /* if the block was already visited we can leave... */
290     if (visitedBlocks.contains(block)) return; // should never happen
291 visitedBlocks.add(block);
292     visitingSuccs.add(block); //currently visiting successors
293 Iterator succsIt = block.getSuccs().iterator();
294     while (succsIt.hasNext()) {
295       Block succ = (Block)succsIt.next();
296
297       if (visitedBlocks.contains(succ)) {
298         if (succ != block && visitingSuccs.contains(succ)) {
299           /* we only want blocks with at least 2 predecessors, to avoid that a
300            * copied while-condition gets copied again in a future pass of
301            * unrollConditions */
302           if (succ.getPreds().size() >= 2 && succ.getSuccs().size() == 2) {
303             Block condition = succ; //just renaming for clearer code
304 Block loopTailBlock = block; //just renaming for clearer code
305
306             if (getSize(condition) <= maxSize) {
307               Unit copiedHead = copyBlock(condition);
308               /* now just redirect the tail of the loop-body */
309               Unit loopTail = loopTailBlock.getTail();
310               if (loopTail instanceof GotoStmt)
311                 ((GotoStmt)loopTail).setTarget(copiedHead);
312               else if (loopTail instanceof IfStmt) {
313                 if (((IfStmt)loopTail).getTarget() == condition.getHead())
314                   ((IfStmt)loopTail).setTarget(copiedHead);
315                 else
316                   insertGotoAfter(loopTail, copiedHead);
317               } else
318                 insertGotoAfter(loopTail, copiedHead);
319             }
320           }
321         }
322       } else {
323         /* unvisited successor */
324         unrollConditions(succ);
325       }
326     }
327     visitingSuccs.remove(block);
328   }
329 }
330
Popular Tags