KickJava   Java API By Example, From Geeks To Geeks.

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


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.BCMOptions;
39
40 /**
41  * Performs a partial redundancy elimination (= code motion). This is
42  * done, by moving <b>every</b>computation as high as possible (it is
43  * easy to show, that they are computationally optimal), and then
44  * replacing the original computation by a reference to this new high
45  * computation. This implies, that we introduce <b>many</b> new
46  * helper-variables (that can easily be eliminated afterwards).<br> In
47  * order to catch every redundant expression, this transformation must
48  * be done on a graph without critical edges. Therefore the first
49  * thing we do, is removing them. A subsequent pass can then easily
50  * remove the synthetic nodes we have introduced.<br> The term "busy"
51  * refers to the fact, that we <b>always</b> move computations as high
52  * as possible. Even, if this is not necessary.
53  *
54  * @see soot.jimple.toolkits.graph.CriticalEdgeRemover
55  */
56 public class BusyCodeMotion extends BodyTransformer {
57     public BusyCodeMotion( Singletons.Global g ) {}
58     public static BusyCodeMotion v() { return G.v().soot_jimple_toolkits_scalar_pre_BusyCodeMotion(); }
59
60   private static final String JavaDoc PREFIX = "$bcm";
61
62   /**
63    * performs the busy code motion.
64    */
65   protected void internalTransform(Body b, String JavaDoc phaseName, Map opts) {
66     BCMOptions options = new BCMOptions( opts );
67     int counter = 0;
68     HashMap expToHelper = new HashMap();
69     Chain unitChain = b.getUnits();
70
71     if(Options.v().verbose())
72       G.v().out.println("[" + b.getMethod().getName() +
73           "] performing Busy Code Motion...");
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     /* if a more precise sideeffect-tester comes out, please change it here! */
99     SideEffectTester sideEffect;
100     if( Scene.v().hasCallGraph() && !options.naive_side_effect() ) {
101         sideEffect = new PASideEffectTester();
102     } else {
103         sideEffect = new NaiveSideEffectTester();
104     }
105     sideEffect.newMethod( b.getMethod() );
106     UpSafetyAnalysis upSafe = new UpSafetyAnalysis(graph, unitToEquivRhs,
107             sideEffect );
108     DownSafetyAnalysis downSafe = new DownSafetyAnalysis(graph,
109         unitToNoExceptionEquivRhs, sideEffect );
110     EarliestnessComputation earliest = new EarliestnessComputation(graph,
111         upSafe, downSafe, sideEffect );
112
113     LocalCreation localCreation = new LocalCreation(b.getLocals(), PREFIX);
114
115     Iterator unitIt = unitChain.snapshotIterator();
116
117     { /* insert the computations at the earliest positions */
118       while (unitIt.hasNext()) {
119         Unit currentUnit = (Unit)unitIt.next();
120         Iterator earliestIt =
121           ((FlowSet)earliest.getFlowBefore(currentUnit)).iterator();
122         while (earliestIt.hasNext()) {
123           EquivalentValue equiVal = (EquivalentValue)earliestIt.next();
124           Value exp = equiVal.getValue();
125           /* get the unic helper-name for this expression */
126           Local helper = (Local)expToHelper.get(equiVal);
127           if (helper == null) {
128             helper = localCreation.newLocal(equiVal.getType());
129             expToHelper.put(equiVal, helper);
130           }
131
132           /* insert a new Assignment-stmt before the currentUnit */
133           Value insertValue = Jimple.cloneIfNecessary(equiVal.getValue());
134           Unit firstComp = Jimple.v().newAssignStmt(helper, insertValue);
135           unitChain.insertBefore(firstComp, currentUnit);
136         }
137       }
138     }
139
140     { /* replace old computations by the helper-vars */
141       unitIt = unitChain.iterator();
142       while (unitIt.hasNext()) {
143         Unit currentUnit = (Unit)unitIt.next();
144         EquivalentValue rhs = (EquivalentValue)unitToEquivRhs.get(currentUnit);
145         if (rhs != null) {
146           Local helper = (Local)expToHelper.get(rhs);
147           if (helper != null)
148             ((AssignStmt)currentUnit).setRightOp(helper);
149         }
150       }
151     }
152     if(Options.v().verbose())
153       G.v().out.println("[" + b.getMethod().getName() +
154           "] Busy Code Motion done!");
155   }
156 }
157
Popular Tags