KickJava   Java API By Example, From Geeks To Geeks.

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


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
27 package soot.jimple.toolkits.graph;
28 import soot.options.*;
29
30
31 import soot.*;
32 import soot.util.*;
33 import java.util.*;
34 import soot.jimple.*;
35 import soot.jimple.internal.*;
36
37 /**
38  * removes all critical edges.<br>
39  * A critical edge is an edge from Block A to block B, if B has more than one
40  * predecessor and A has more the one successor.<br>
41  * As an example: If we wanted a computation to be only on the path A-&gt;B
42  * this computation must be directly on the edge. Otherwise it is either
43  * executed on the path through the second predecessor of A or throught the
44  * second successor of B.<br>
45  * Our critical edge-remover overcomes this problem by introducing synthetic
46  * nodes on this critical edges.<br>
47  * Exceptions will be ignored.
48  */
49 public class CriticalEdgeRemover extends BodyTransformer {
50     public CriticalEdgeRemover( Singletons.Global g ) {}
51     public static CriticalEdgeRemover v() { return G.v().soot_jimple_toolkits_graph_CriticalEdgeRemover(); }
52
53   /**
54    * performs critical edge-removing.
55    */
56   protected void internalTransform(Body b, String JavaDoc phaseName, Map options) {
57     if(Options.v().verbose())
58       G.v().out.println("[" + b.getMethod().getName() +
59                          "] Removing Critical Edges...");
60     removeCriticalEdges(b);
61     if(Options.v().verbose())
62       G.v().out.println("[" + b.getMethod().getName() +
63                          "] Removing Critical Edges done.");
64
65   }
66
67   /**
68    * inserts a Jimple<code>Goto</code> to <code> target, directly after
69    * <code>node</code> in the given <code>unitChain</code>.<br>
70    * As we use <code>JGoto</code> the chain must contain Jimple-stmts.
71    *
72    * @param unitChain the Chain where we will insert the <code>Goto</code>.
73    * @param node the <code>Goto</code> will be inserted just after this node.
74    * @param target is the Unit the <code>goto</code> will jump to.
75    * @return the newly inserted <code>Goto</code>
76    */
77   private static Unit insertGotoAfter(Chain unitChain, Unit node, Unit target) {
78     Unit newGoto = Jimple.v().newGotoStmt(target);
79     unitChain.insertAfter(newGoto, node);
80     return newGoto;
81   }
82
83   /**
84    * inserts a Jimple<code>Goto</code> to <code> target, directly before
85    * <code>node</code> in the given <code>unitChain</code>.<br>
86    * As we use <code>JGoto</code> the chain must contain Jimple-stmts.
87    *
88    * @param unitChain the Chain where we will insert the <code>Goto</code>.
89    * @param node the <code>Goto</code> will be inserted just before this node.
90    * @param target is the Unit the <code>goto</code> will jump to.
91    * @return the newly inserted <code>Goto</code>
92    */
93   /*note, that this method has slightly more overhead than the insertGotoAfter*/
94   private static Unit insertGotoBefore(Chain unitChain, Unit node, Unit target)
95   {
96     Unit newGoto = Jimple.v().newGotoStmt(target);
97     unitChain.insertBefore(newGoto, node);
98     newGoto.redirectJumpsToThisTo(node);
99     return newGoto;
100   }
101
102   /**
103    * takes <code>node</code> and redirects all branches to <code>oldTarget</code>
104    * to <code>newTarget</code>.
105    *
106    * @param node the Unit where we redirect
107    * @param oldTarget
108    * @param newTarget
109    */
110   private static void redirectBranch(Unit node, Unit oldTarget, Unit newTarget) {
111     Iterator targetIt = node.getUnitBoxes().iterator();
112     while (targetIt.hasNext()) {
113       UnitBox targetBox = (UnitBox)targetIt.next();
114       Unit target = (Unit)targetBox.getUnit();
115       if (target == oldTarget)
116         targetBox.setUnit(newTarget);
117     }
118   }
119
120   /**
121    * splits critical edges by introducing synthetic nodes.<br>
122    * This method <b>will modify</b> the <code>UnitGraph</code> of the body.
123    * Synthetic nodes are always <code>JGoto</code>s. Therefore the body must be
124    * in <tt>Jimple</tt>.<br>
125    * As a side-effect, after the transformation, the direct predecessor of a
126    * block/node with multiple predecessors will will not fall through anymore.
127    * This simplifies the algorithm and is nice to work with afterwards.
128    *
129    * @param b the Jimple-body that will be physicly modified so that there are
130    * no critical edges anymore.
131    */
132   /* note, that critical edges can only appear on edges between blocks!.
133      Our algorithm will *not* take into account exceptions. (this is nearly
134      impossible anyways) */
135   private void removeCriticalEdges(Body b) {
136     Chain unitChain = b.getUnits();
137     int size = unitChain.size();
138     Map predecessors = new HashMap(2 * size + 1, 0.7f);
139
140     /* First get the predecessors of each node (although direct predecessors are
141      * predecessors too, we'll not include them in the lists) */
142     {
143       Iterator unitIt = unitChain.snapshotIterator();
144       while (unitIt.hasNext()) {
145         Unit currentUnit = (Unit)unitIt.next();
146
147         Iterator succsIt = currentUnit.getUnitBoxes().iterator();
148         while (succsIt.hasNext()) {
149           Unit target = ((UnitBox)succsIt.next()).getUnit();
150           List predList = (List)predecessors.get(target);
151           if (predList == null) {
152             predList = new ArrayList();
153             predList.add(currentUnit);
154             predecessors.put(target, predList);
155           } else
156             predList.add(currentUnit);
157         }
158       }
159     }
160
161
162     {
163       /* for each node: if we have more than two predecessors, split these edges
164        * if the node at the other end has more than one successor. */
165
166       /* we need a snapshotIterator, as we'll modify the structure */
167       Iterator unitIt = unitChain.snapshotIterator();
168
169       Unit currentUnit = null;
170       Unit directPredecessor;
171       while (unitIt.hasNext()) {
172         directPredecessor = currentUnit;
173         currentUnit = (Unit)unitIt.next();
174
175         List predList = (List)predecessors.get(currentUnit);
176         int nbPreds = (predList == null)? 0: predList.size();
177         if (directPredecessor != null && directPredecessor.fallsThrough())
178           nbPreds++;
179
180         if (nbPreds >= 2) {
181           /* redirect the directPredecessor (if it falls through), so we can
182            * easily insert the synthetic nodes. This redirection might not be
183            * necessary, but is pleasant anyways (see the Javadoc for this
184            * method)*/
185           if (directPredecessor != null &&
186               directPredecessor.fallsThrough()) {
187             directPredecessor = insertGotoAfter(unitChain, directPredecessor,
188                 currentUnit);
189           }
190
191           /* if the predecessors have more than one successor insert the synthetic
192            * node. */
193           Iterator predIt = predList.iterator();
194           while (predIt.hasNext()) {
195             Unit predecessor = (Unit)predIt.next();
196             /* Although in Jimple there should be only two ways of having more
197              * than one successor (If and Case) we'll do it the hard way:) */
198             int nbSuccs = predecessor.getUnitBoxes().size();
199             nbSuccs += predecessor.fallsThrough()? 1: 0;
200             if (nbSuccs >= 2) {
201               /* insert synthetic node (insertGotoAfter should be slightly
202                * faster)*/
203               if (directPredecessor == null)
204                 directPredecessor = insertGotoBefore(unitChain, currentUnit,
205                     currentUnit);
206               else
207                 directPredecessor = insertGotoAfter(unitChain,
208                     directPredecessor, currentUnit);
209               /* update the branch */
210               redirectBranch(predecessor, currentUnit, directPredecessor);
211             }
212           }
213         }
214       }
215     }
216   }
217 }
218
Popular Tags