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.BCMOptions;
039:
040: /**
041: * Performs a partial redundancy elimination (= code motion). This is
042: * done, by moving <b>every</b>computation as high as possible (it is
043: * easy to show, that they are computationally optimal), and then
044: * replacing the original computation by a reference to this new high
045: * computation. This implies, that we introduce <b>many</b> new
046: * helper-variables (that can easily be eliminated afterwards).<br> In
047: * order to catch every redundant expression, this transformation must
048: * be done on a graph without critical edges. Therefore the first
049: * thing we do, is removing them. A subsequent pass can then easily
050: * remove the synthetic nodes we have introduced.<br> The term "busy"
051: * refers to the fact, that we <b>always</b> move computations as high
052: * as possible. Even, if this is not necessary.
053: *
054: * @see soot.jimple.toolkits.graph.CriticalEdgeRemover
055: */
056: public class BusyCodeMotion extends BodyTransformer {
057: public BusyCodeMotion(Singletons.Global g) {
058: }
059:
060: public static BusyCodeMotion v() {
061: return G.v().soot_jimple_toolkits_scalar_pre_BusyCodeMotion();
062: }
063:
064: private static final String PREFIX = "$bcm";
065:
066: /**
067: * performs the busy code motion.
068: */
069: protected void internalTransform(Body b, String phaseName, Map opts) {
070: BCMOptions options = new BCMOptions(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 Busy Code Motion...");
077:
078: CriticalEdgeRemover.v().transform(b, phaseName + ".cer");
079:
080: UnitGraph graph = new BriefUnitGraph(b);
081:
082: /* map each unit to its RHS. only take binary expressions */
083: Map unitToEquivRhs = new UnitMap(b, graph.size() + 1, 0.7f) {
084: protected Object mapTo(Unit unit) {
085: Value tmp = SootFilter.noInvokeRhs(unit);
086: Value tmp2 = SootFilter.binop(tmp);
087: if (tmp2 == null)
088: tmp2 = SootFilter.concreteRef(tmp);
089: return SootFilter.equiVal(tmp2);
090: }
091: };
092:
093: /* same as before, but without exception-throwing expressions */
094: Map unitToNoExceptionEquivRhs = new UnitMap(b,
095: graph.size() + 1, 0.7f) {
096: protected Object mapTo(Unit unit) {
097: Value tmp = SootFilter.binopRhs(unit);
098: tmp = SootFilter.noExceptionThrowing(tmp);
099: return SootFilter.equiVal(tmp);
100: }
101: };
102:
103: /* if a more precise sideeffect-tester comes out, please change it here! */
104: SideEffectTester sideEffect;
105: if (Scene.v().hasCallGraph() && !options.naive_side_effect()) {
106: sideEffect = new PASideEffectTester();
107: } else {
108: sideEffect = new NaiveSideEffectTester();
109: }
110: sideEffect.newMethod(b.getMethod());
111: UpSafetyAnalysis upSafe = new UpSafetyAnalysis(graph,
112: unitToEquivRhs, sideEffect);
113: DownSafetyAnalysis downSafe = new DownSafetyAnalysis(graph,
114: unitToNoExceptionEquivRhs, sideEffect);
115: EarliestnessComputation earliest = new EarliestnessComputation(
116: graph, upSafe, downSafe, sideEffect);
117:
118: LocalCreation localCreation = new LocalCreation(b.getLocals(),
119: PREFIX);
120:
121: Iterator unitIt = unitChain.snapshotIterator();
122:
123: { /* insert the computations at the earliest positions */
124: while (unitIt.hasNext()) {
125: Unit currentUnit = (Unit) unitIt.next();
126: Iterator earliestIt = ((FlowSet) earliest
127: .getFlowBefore(currentUnit)).iterator();
128: while (earliestIt.hasNext()) {
129: EquivalentValue equiVal = (EquivalentValue) earliestIt
130: .next();
131: Value exp = equiVal.getValue();
132: /* get the unic helper-name for this expression */
133: Local helper = expToHelper.get(equiVal);
134: if (helper == null) {
135: helper = localCreation.newLocal(equiVal
136: .getType());
137: expToHelper.put(equiVal, helper);
138: }
139:
140: /* insert a new Assignment-stmt before the currentUnit */
141: Value insertValue = Jimple.cloneIfNecessary(equiVal
142: .getValue());
143: Unit firstComp = Jimple.v().newAssignStmt(helper,
144: insertValue);
145: unitChain.insertBefore(firstComp, currentUnit);
146: }
147: }
148: }
149:
150: { /* replace old computations by the helper-vars */
151: unitIt = unitChain.iterator();
152: while (unitIt.hasNext()) {
153: Unit currentUnit = (Unit) unitIt.next();
154: EquivalentValue rhs = (EquivalentValue) unitToEquivRhs
155: .get(currentUnit);
156: if (rhs != null) {
157: Local helper = expToHelper.get(rhs);
158: if (helper != null)
159: ((AssignStmt) currentUnit).setRightOp(helper);
160: }
161: }
162: }
163: if (Options.v().verbose())
164: G.v().out.println("[" + b.getMethod().getName()
165: + "] Busy Code Motion done!");
166: }
167: }
|