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-1999.
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.scalar.pre;
027:
028: import soot.options.*;
029: import soot.jimple.toolkits.graph.*;
030: import soot.jimple.toolkits.scalar.*;
031: import soot.*;
032: import soot.toolkits.scalar.*;
033: import soot.toolkits.graph.*;
034: import soot.jimple.*;
035: import java.util.*;
036: import soot.util.*;
037: import soot.jimple.toolkits.pointer.PASideEffectTester;
038: import soot.options.LCMOptions;
039:
040: /**
041: * Performs a partial redundancy elimination (= code motion). This is done, by
042: * introducing helper-vars, that store an already computed value, or if a
043: * compuation only arrives partially (not from all predecessors) inserts a new
044: * computation on these paths afterwards).<p>
045: *
046: * In order to catch every redundant expression, this transformation must be
047: * done on a graph without critical edges. Therefore the first thing we do, is
048: * removing them. A subsequent pass can then easily remove the synthetic nodes
049: * we have introduced.<p>
050: *
051: * The term "lazy" refers to the fact, that we move computations only if
052: * necessary.
053: *
054: * @see soot.jimple.toolkits.graph.CriticalEdgeRemover
055: */
056: public class LazyCodeMotion extends BodyTransformer {
057: public LazyCodeMotion(Singletons.Global g) {
058: }
059:
060: public static LazyCodeMotion v() {
061: return G.v().soot_jimple_toolkits_scalar_pre_LazyCodeMotion();
062: }
063:
064: private static final String PREFIX = "$lcm";
065:
066: /**
067: * performs the lazy code motion.
068: */
069: protected void internalTransform(Body b, String phaseName, Map opts) {
070: LCMOptions options = new LCMOptions(opts);
071: HashMap<EquivalentValue, Local> expToHelper = new HashMap<EquivalentValue, Local>();
072: Chain unitChain = b.getUnits();
073:
074: if (Options.v().verbose())
075: G.v().out.println("[" + b.getMethod().getName()
076: + "] Performing Lazy Code Motion...");
077:
078: if (options.unroll())
079: new LoopConditionUnroller()
080: .transform(b, phaseName + ".lcu");
081:
082: CriticalEdgeRemover.v().transform(b, phaseName + ".cer");
083:
084: UnitGraph graph = new BriefUnitGraph(b);
085:
086: /* map each unit to its RHS. only take binary expressions */
087: Map unitToEquivRhs = new UnitMap(b, graph.size() + 1, 0.7f) {
088: protected Object mapTo(Unit unit) {
089: Value tmp = SootFilter.noInvokeRhs(unit);
090: Value tmp2 = SootFilter.binop(tmp);
091: if (tmp2 == null)
092: tmp2 = SootFilter.concreteRef(tmp);
093: return SootFilter.equiVal(tmp2);
094: }
095: };
096:
097: /* same as before, but without exception-throwing expressions */
098: Map unitToNoExceptionEquivRhs = new UnitMap(b,
099: graph.size() + 1, 0.7f) {
100: protected Object mapTo(Unit unit) {
101: Value tmp = SootFilter.binopRhs(unit);
102: tmp = SootFilter.noExceptionThrowing(tmp);
103: return SootFilter.equiVal(tmp);
104: }
105: };
106:
107: FlowUniverse universe = new CollectionFlowUniverse(
108: unitToEquivRhs.values());
109: BoundedFlowSet set = new ArrayPackedSet(universe);
110:
111: /* if a more precise sideeffect-tester comes out, please change it here! */
112: SideEffectTester sideEffect;
113: if (Scene.v().hasCallGraph() && !options.naive_side_effect()) {
114: sideEffect = new PASideEffectTester();
115: } else {
116: sideEffect = new NaiveSideEffectTester();
117: }
118: sideEffect.newMethod(b.getMethod());
119: UpSafetyAnalysis upSafe;
120: DownSafetyAnalysis downSafe;
121: EarliestnessComputation earliest;
122: DelayabilityAnalysis delay;
123: NotIsolatedAnalysis notIsolated;
124: LatestComputation latest;
125:
126: if (options.safety() == LCMOptions.safety_safe)
127: upSafe = new UpSafetyAnalysis(graph,
128: unitToNoExceptionEquivRhs, sideEffect, set);
129: else
130: upSafe = new UpSafetyAnalysis(graph, unitToEquivRhs,
131: sideEffect, set);
132:
133: if (options.safety() == LCMOptions.safety_unsafe)
134: downSafe = new DownSafetyAnalysis(graph, unitToEquivRhs,
135: sideEffect, set);
136: else {
137: downSafe = new DownSafetyAnalysis(graph,
138: unitToNoExceptionEquivRhs, sideEffect, set);
139: /* we include the exception-throwing expressions at their uses */
140: Iterator unitIt = unitChain.iterator();
141: while (unitIt.hasNext()) {
142: Unit currentUnit = (Unit) unitIt.next();
143: Object rhs = unitToEquivRhs.get(currentUnit);
144: if (rhs != null)
145: ((FlowSet) downSafe.getFlowBefore(currentUnit))
146: .add(rhs);
147: }
148: }
149:
150: earliest = new EarliestnessComputation(graph, upSafe, downSafe,
151: sideEffect, set);
152: delay = new DelayabilityAnalysis(graph, earliest,
153: unitToEquivRhs, set);
154: latest = new LatestComputation(graph, delay, unitToEquivRhs,
155: set);
156: notIsolated = new NotIsolatedAnalysis(graph, latest,
157: unitToEquivRhs, set);
158:
159: LocalCreation localCreation = new LocalCreation(b.getLocals(),
160: PREFIX);
161:
162: /* debug */
163: /*
164: {
165: G.v().out.println("========" + b.getMethod().getName());
166: Iterator unitIt = unitChain.iterator();
167: while (unitIt.hasNext()) {
168: Unit currentUnit = (Unit) unitIt.next();
169: Value equiVal = (Value)unitToEquivRhs.get(currentUnit);
170: FlowSet latestSet = (FlowSet)latest.getFlowBefore(currentUnit);
171: FlowSet notIsolatedSet =
172: (FlowSet)notIsolated.getFlowAfter(currentUnit);
173: FlowSet delaySet = (FlowSet)delay.getFlowBefore(currentUnit);
174: FlowSet earlySet = ((FlowSet)earliest.getFlowBefore(currentUnit));
175: FlowSet upSet = (FlowSet)upSafe.getFlowBefore(currentUnit);
176: FlowSet downSet = (FlowSet)downSafe.getFlowBefore(currentUnit);
177: G.v().out.println(currentUnit);
178: G.v().out.println(" rh: " + equiVal);
179: G.v().out.println(" up: " + upSet);
180: G.v().out.println(" do: " + downSet);
181: G.v().out.println(" is: " + notIsolatedSet);
182: G.v().out.println(" ea: " + earlySet);
183: G.v().out.println(" db: " + delaySet);
184: G.v().out.println(" la: " + latestSet);
185: }
186: }
187: */
188:
189: { /* insert the computations */
190: Iterator unitIt = unitChain.snapshotIterator();
191: while (unitIt.hasNext()) {
192: Unit currentUnit = (Unit) unitIt.next();
193: FlowSet latestSet = (FlowSet) latest
194: .getFlowBefore(currentUnit);
195: FlowSet notIsolatedSet = (FlowSet) notIsolated
196: .getFlowAfter(currentUnit);
197: FlowSet insertHere = latestSet.clone();
198: insertHere.intersection(notIsolatedSet, insertHere);
199: Iterator insertIt = insertHere.iterator();
200: while (insertIt.hasNext()) {
201: EquivalentValue equiVal = (EquivalentValue) insertIt
202: .next();
203: /* get the unic helper-name for this expression */
204: Local helper = expToHelper.get(equiVal);
205: if (helper == null) {
206: helper = localCreation.newLocal(equiVal
207: .getType());
208: expToHelper.put(equiVal, helper);
209: }
210:
211: /* insert a new Assignment-stmt before the currentUnit */
212: Value insertValue = Jimple.cloneIfNecessary(equiVal
213: .getValue());
214: Unit firstComp = Jimple.v().newAssignStmt(helper,
215: insertValue);
216: unitChain.insertBefore(firstComp, currentUnit);
217: // G.v().out.print("x");
218: }
219: }
220: }
221:
222: { /* replace old computations by the helper-vars */
223: Iterator unitIt = unitChain.iterator();
224: while (unitIt.hasNext()) {
225: Unit currentUnit = (Unit) unitIt.next();
226: EquivalentValue rhs = (EquivalentValue) unitToEquivRhs
227: .get(currentUnit);
228: if (rhs != null) {
229: FlowSet latestSet = (FlowSet) latest
230: .getFlowBefore(currentUnit);
231: FlowSet notIsolatedSet = (FlowSet) notIsolated
232: .getFlowAfter(currentUnit);
233: if (!latestSet.contains(rhs)
234: && notIsolatedSet.contains(rhs)) {
235: Local helper = expToHelper.get(rhs);
236:
237: try {
238: ((AssignStmt) currentUnit)
239: .setRightOp(helper);
240: } catch (RuntimeException e) {
241: G.v().out.println("Error on "
242: + b.getMethod().getName());
243: G.v().out.println(currentUnit.toString());
244:
245: G.v().out.println(latestSet);
246:
247: G.v().out.println(notIsolatedSet);
248:
249: throw e;
250: }
251:
252: // G.v().out.print(".");
253: }
254: }
255: }
256: }
257: if (Options.v().verbose())
258: G.v().out.println("[" + b.getMethod().getName()
259: + "] Lazy Code Motion done.");
260: }
261: }
|