KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > scalar > pre > LazyCodeMotion


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-1999.
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.scalar.pre;
28 import soot.options.*;
29 import soot.jimple.toolkits.graph.*;
30 import soot.jimple.toolkits.scalar.*;
31 import soot.*;
32 import soot.toolkits.scalar.*;
33 import soot.toolkits.graph.*;
34 import soot.jimple.*;
35 import java.util.*;
36 import soot.util.*;
37 import soot.jimple.toolkits.pointer.PASideEffectTester;
38 import soot.options.LCMOptions;
39
40 /**
41  * Performs a partial redundancy elimination (= code motion). This is done, by
42  * introducing helper-vars, that store an already computed value, or if a
43  * compuation only arrives partially (not from all predecessors) inserts a new
44  * computation on these paths afterwards).<p>
45  *
46  * In order to catch every redundant expression, this transformation must be
47  * done on a graph without critical edges. Therefore the first thing we do, is
48  * removing them. A subsequent pass can then easily remove the synthetic nodes
49  * we have introduced.<p>
50  *
51  * The term "lazy" refers to the fact, that we move computations only if
52  * necessary.
53  *
54  * @see soot.jimple.toolkits.graph.CriticalEdgeRemover
55  */
56 public class LazyCodeMotion extends BodyTransformer {
57     public LazyCodeMotion( Singletons.Global g ) {}
58     public static LazyCodeMotion v() { return G.v().soot_jimple_toolkits_scalar_pre_LazyCodeMotion(); }
59
60   private static final String JavaDoc PREFIX = "$lcm";
61
62   /**
63    * performs the lazy code motion.
64    */
65   protected void internalTransform(Body b, String JavaDoc phaseName, Map opts) {
66     LCMOptions options = new LCMOptions( opts );
67     HashMap expToHelper = new HashMap();
68     Chain unitChain = b.getUnits();
69
70     if(Options.v().verbose()) G.v().out.println("[" + b.getMethod().getName() +
71                                           "] Performing Lazy Code Motion...");
72
73     if (options.unroll()) new LoopConditionUnroller().transform(b, phaseName + ".lcu");
74
75     CriticalEdgeRemover.v().transform(b, phaseName + ".cer");
76
77     UnitGraph graph = new BriefUnitGraph(b);
78
79     /* map each unit to its RHS. only take binary expressions */
80     Map unitToEquivRhs = new UnitMap(b, graph.size() + 1, 0.7f) {
81     protected Object JavaDoc mapTo(Unit unit) {
82       Value tmp = SootFilter.noInvokeRhs(unit);
83       Value tmp2 = SootFilter.binop(tmp);
84       if (tmp2 == null) tmp2 = SootFilter.concreteRef(tmp);
85       return SootFilter.equiVal(tmp2);
86     }
87       };
88
89     /* same as before, but without exception-throwing expressions */
90     Map unitToNoExceptionEquivRhs = new UnitMap(b, graph.size() + 1, 0.7f) {
91     protected Object JavaDoc mapTo(Unit unit) {
92       Value tmp = SootFilter.binopRhs(unit);
93       tmp = SootFilter.noExceptionThrowing(tmp);
94       return SootFilter.equiVal(tmp);
95     }
96       };
97
98     FlowUniverse universe = new CollectionFlowUniverse(unitToEquivRhs.values());
99     BoundedFlowSet set = new ArrayPackedSet(universe);
100
101     /* if a more precise sideeffect-tester comes out, please change it here! */
102     SideEffectTester sideEffect;
103     if( Scene.v().hasCallGraph() && !options.naive_side_effect() ) {
104         sideEffect = new PASideEffectTester();
105     } else {
106         sideEffect = new NaiveSideEffectTester();
107     }
108     sideEffect.newMethod( b.getMethod() );
109     UpSafetyAnalysis upSafe;
110     DownSafetyAnalysis downSafe;
111     EarliestnessComputation earliest;
112     DelayabilityAnalysis delay;
113     NotIsolatedAnalysis notIsolated;
114     LatestComputation latest;
115
116     if (options.safety() == LCMOptions.safety_safe)
117       upSafe = new UpSafetyAnalysis(graph, unitToNoExceptionEquivRhs,
118                                     sideEffect, set);
119     else
120       upSafe = new UpSafetyAnalysis(graph, unitToEquivRhs, sideEffect, set);
121
122     if (options.safety() == LCMOptions.safety_unsafe)
123       downSafe = new DownSafetyAnalysis(graph, unitToEquivRhs, sideEffect, set);
124     else {
125       downSafe = new DownSafetyAnalysis(graph, unitToNoExceptionEquivRhs,
126                     sideEffect, set);
127       /* we include the exception-throwing expressions at their uses */
128       Iterator unitIt = unitChain.iterator();
129       while (unitIt.hasNext()) {
130     Unit currentUnit = (Unit)unitIt.next();
131     Object JavaDoc rhs = unitToEquivRhs.get(currentUnit);
132     if (rhs != null)
133       ((FlowSet)downSafe.getFlowBefore(currentUnit)).add(rhs);
134       }
135     }
136
137     earliest = new EarliestnessComputation(graph, upSafe, downSafe, sideEffect,
138                                            set);
139     delay = new DelayabilityAnalysis(graph, earliest, unitToEquivRhs, set);
140     latest = new LatestComputation(graph, delay, unitToEquivRhs, set);
141     notIsolated = new NotIsolatedAnalysis(graph, latest, unitToEquivRhs, set);
142
143     LocalCreation localCreation = new LocalCreation(b.getLocals(), PREFIX);
144
145     /* debug */
146     /*
147     {
148       G.v().out.println("========" + b.getMethod().getName());
149       Iterator unitIt = unitChain.iterator();
150       while (unitIt.hasNext()) {
151     Unit currentUnit = (Unit) unitIt.next();
152         Value equiVal = (Value)unitToEquivRhs.get(currentUnit);
153         FlowSet latestSet = (FlowSet)latest.getFlowBefore(currentUnit);
154         FlowSet notIsolatedSet =
155           (FlowSet)notIsolated.getFlowAfter(currentUnit);
156         FlowSet delaySet = (FlowSet)delay.getFlowBefore(currentUnit);
157         FlowSet earlySet = ((FlowSet)earliest.getFlowBefore(currentUnit));
158     FlowSet upSet = (FlowSet)upSafe.getFlowBefore(currentUnit);
159     FlowSet downSet = (FlowSet)downSafe.getFlowBefore(currentUnit);
160     G.v().out.println(currentUnit);
161         G.v().out.println(" rh: " + equiVal);
162         G.v().out.println(" up: " + upSet);
163     G.v().out.println(" do: " + downSet);
164         G.v().out.println(" is: " + notIsolatedSet);
165     G.v().out.println(" ea: " + earlySet);
166         G.v().out.println(" db: " + delaySet);
167         G.v().out.println(" la: " + latestSet);
168       }
169     }
170     */
171
172     { /* insert the computations */
173       Iterator unitIt = unitChain.snapshotIterator();
174       while (unitIt.hasNext()) {
175         Unit currentUnit = (Unit)unitIt.next();
176         FlowSet latestSet = (FlowSet)latest.getFlowBefore(currentUnit);
177         FlowSet notIsolatedSet =
178           (FlowSet)notIsolated.getFlowAfter(currentUnit);
179         FlowSet insertHere = (FlowSet)latestSet.clone();
180         insertHere.intersection(notIsolatedSet, insertHere);
181         Iterator insertIt = insertHere.iterator();
182         while (insertIt.hasNext()) {
183           EquivalentValue equiVal = (EquivalentValue)insertIt.next();
184           /* get the unic helper-name for this expression */
185           Local helper = (Local)expToHelper.get(equiVal);
186           if (helper == null) {
187             helper = localCreation.newLocal(equiVal.getType());
188             expToHelper.put(equiVal, helper);
189           }
190
191           /* insert a new Assignment-stmt before the currentUnit */
192           Value insertValue = Jimple.cloneIfNecessary(equiVal.getValue());
193           Unit firstComp = Jimple.v().newAssignStmt(helper, insertValue);
194           unitChain.insertBefore(firstComp, currentUnit);
195       // G.v().out.print("x");
196 }
197       }
198     }
199
200     { /* replace old computations by the helper-vars */
201       Iterator unitIt = unitChain.iterator();
202       while (unitIt.hasNext()) {
203         Unit currentUnit = (Unit)unitIt.next();
204         EquivalentValue rhs = (EquivalentValue)unitToEquivRhs.get(currentUnit);
205         if (rhs != null) {
206           FlowSet latestSet = (FlowSet)latest.getFlowBefore(currentUnit);
207           FlowSet notIsolatedSet =
208             (FlowSet)notIsolated.getFlowAfter(currentUnit);
209           if (!latestSet.contains(rhs) && notIsolatedSet.contains(rhs)) {
210             Local helper = (Local)expToHelper.get(rhs);
211
212         try {
213           ((AssignStmt)currentUnit).setRightOp(helper);
214         } catch (RuntimeException JavaDoc e){
215           G.v().out.println("Error on "+b.getMethod().getName());
216           G.v().out.println(currentUnit.toString());
217
218           G.v().out.println(latestSet);
219           
220           G.v().out.println(notIsolatedSet);
221
222           throw e;
223         }
224            
225         // G.v().out.print(".");
226 }
227         }
228       }
229     }
230     if(Options.v().verbose())
231       G.v().out.println("[" + b.getMethod().getName() +
232                          "] Lazy Code Motion done.");
233   }
234 }
235
Popular Tags