KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > scalar > CopyPropagator


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 1997-1999 Raja Vallee-Rai
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
28
29
30
31 package soot.jimple.toolkits.scalar;
32 import soot.options.*;
33
34 import soot.*;
35 import soot.jimple.*;
36 import soot.toolkits.scalar.*;
37 import soot.toolkits.graph.*;
38 import soot.util.*;
39 import java.util.*;
40 import soot.options.CPOptions;
41
42 public class CopyPropagator extends BodyTransformer
43 {
44     public CopyPropagator( Singletons.Global g ) {}
45     public static CopyPropagator v() { return G.v().soot_jimple_toolkits_scalar_CopyPropagator(); }
46
47     /** Cascaded copy propagator.
48     
49         If it encounters situations of the form: A: a = ...; B: ... x = a; C:... use (x);
50         where a has only one definition, and x has only one definition (B), then it can
51         propagate immediately without checking between B and C for redefinitions
52         of a (namely) A because they cannot occur. In this case the propagator is global.
53         
54         Otherwise, if a has multiple definitions then it only checks for redefinitions of
55         Propagates constants and copies in extended basic blocks.
56         
57         Does not propagate stack locals when the "only-regular-locals" option is true.
58     */
59     protected void internalTransform(Body b, String JavaDoc phaseName, Map opts)
60     {
61         CPOptions options = new CPOptions( opts );
62         StmtBody stmtBody = (StmtBody)b;
63         int fastCopyPropagationCount = 0;
64         int slowCopyPropagationCount = 0;
65         
66         if(Options.v().verbose())
67             G.v().out.println("[" + stmtBody.getMethod().getName() +
68                 "] Propagating copies...");
69
70         if(Options.v().time())
71             Timers.v().propagatorTimer.start();
72                 
73         Chain units = stmtBody.getUnits();
74
75         Map localToDefCount = new HashMap();
76         
77         // Count number of definitions for each local.
78 {
79             Iterator stmtIt = units.iterator();
80         
81             while(stmtIt.hasNext())
82             {
83                 Stmt s = (Stmt) stmtIt.next();
84                 
85                 if(s instanceof DefinitionStmt &&
86                     ((DefinitionStmt) s).getLeftOp() instanceof Local)
87                 {
88                     Local l = (Local) ((DefinitionStmt) s).getLeftOp();
89                      
90                     if(!localToDefCount.containsKey(l))
91                         localToDefCount.put(l, new Integer JavaDoc(1));
92                     else
93                         localToDefCount.put(l, new Integer JavaDoc(((Integer JavaDoc) localToDefCount.get(l)).intValue() + 1));
94                 }
95                 
96             }
97         }
98         
99 // ((JimpleBody) stmtBody).printDebugTo(new java.io.PrintWriter(G.v().out, true));
100
101         ExceptionalUnitGraph graph = new ExceptionalUnitGraph(stmtBody);
102
103         LocalDefs localDefs;
104         
105         localDefs = new SmartLocalDefs(graph, new SimpleLiveLocals(graph));
106
107         LocalUses localUses = new SimpleLocalUses(graph, localDefs);
108
109         // Perform a local propagation pass.
110 {
111             Iterator stmtIt = (new PseudoTopologicalOrderer()).newList(graph).iterator();
112
113             while(stmtIt.hasNext())
114             {
115                 Stmt stmt = (Stmt) stmtIt.next();
116                 Iterator useBoxIt = stmt.getUseBoxes().iterator();
117
118                 while(useBoxIt.hasNext())
119                 {
120                     ValueBox useBox = (ValueBox) useBoxIt.next();
121
122                     if(useBox.getValue() instanceof Local)
123                     {
124                         Local l = (Local) useBox.getValue();
125
126                         if(options.only_regular_locals() && l.getName().startsWith("$"))
127                             continue;
128        
129                         if(options.only_stack_locals() && !l.getName().startsWith("$"))
130                             continue;
131                             
132                         List defsOfUse = localDefs.getDefsOfAt(l, stmt);
133
134                         if(defsOfUse.size() == 1)
135                         {
136                             DefinitionStmt def = (DefinitionStmt) defsOfUse.get(0);
137
138                             if(def.getRightOp() instanceof Local)
139                             {
140                                 Local m = (Local) def.getRightOp();
141
142                                 if(l != m)
143                                 {
144                                     Object JavaDoc dcObj = localToDefCount.get(m);
145
146                                     if (dcObj == null)
147                                         throw new RuntimeException JavaDoc("Variable " + m + " used without definition!");
148
149                                     int defCount = ((Integer JavaDoc)dcObj).intValue();
150                                     
151                                     if(defCount == 0)
152                                         throw new RuntimeException JavaDoc("Variable " + m + " used without definition!");
153                                     else if(defCount == 1)
154                                     {
155                                         useBox.setValue(m);
156                                         fastCopyPropagationCount++;
157                                         continue;
158                                     }
159
160                                     List path = graph.getExtendedBasicBlockPathBetween(def, stmt);
161                                     
162                                     if(path == null)
163                                     {
164                                         // no path in the extended basic block
165 continue;
166                                     }
167                                      
168                                     Iterator pathIt = path.iterator();
169                                     
170                                     // Skip first node
171 pathIt.next();
172                                         
173                                     // Make sure that m is not redefined along path
174 {
175                                         boolean isRedefined = false;
176                                         
177                                         while(pathIt.hasNext())
178                                         {
179                                             Stmt s = (Stmt) pathIt.next();
180                                             
181                                             if(stmt == s)
182                                             {
183                                                 // Don't look at the last statement
184 // since it is evaluated after the uses
185
186                                                 break;
187                                             }
188                                             if(s instanceof DefinitionStmt)
189                                             {
190                                                 if(((DefinitionStmt) s).getLeftOp() == m)
191                                                 {
192                                                     isRedefined = true;
193                                                     break;
194                                                 }
195                                             }
196                                         }
197                                         
198                                         if(isRedefined)
199                                             continue;
200                                             
201                                     }
202                                     
203                                     useBox.setValue(m);
204                                     slowCopyPropagationCount++;
205                                 }
206                             }
207                         }
208                     }
209
210                  }
211             }
212         }
213
214
215         if(Options.v().verbose())
216             G.v().out.println("[" + stmtBody.getMethod().getName() +
217                 "] Propagated: " +
218                 fastCopyPropagationCount + " fast copies " +
219                 slowCopyPropagationCount + " slow copies");
220      
221         if(Options.v().time())
222             Timers.v().propagatorTimer.end();
223     
224     }
225     
226 }
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
Popular Tags