KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > toolkits > scalar > LocalSplitter


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 package soot.toolkits.scalar;
31 import soot.options.*;
32
33 import soot.*;
34 import soot.jimple.*;
35 import soot.toolkits.graph.*;
36 import soot.util.*;
37 import java.util.*;
38
39 /**
40  * A BodyTransformer that attemps to indentify and separate uses of a local
41  * varible that are independent of each other. Conceptually the inverse transform
42  * with respect to the LocalPacker transform.
43  *
44  * For example the code:
45  *
46  * for(int i; i < k; i++);
47  * for(int i; i < k; i++);
48  *
49  * would be transformed into:
50  * for(int i; i < k; i++);
51  * for(int j; j < k; j++);
52  *
53  *
54  * @see BodyTransformer
55  * @see LocalPacker
56  * @see Body
57  */
58 public class LocalSplitter extends BodyTransformer
59 {
60     public LocalSplitter( Singletons.Global g ) {}
61     public static LocalSplitter v() { return G.v().soot_toolkits_scalar_LocalSplitter(); }
62
63     protected void internalTransform(Body body, String JavaDoc phaseName, Map options)
64     {
65         Chain units = body.getUnits();
66         List webs = new ArrayList();
67
68         if(Options.v().verbose())
69             G.v().out.println("[" + body.getMethod().getName() + "] Splitting locals...");
70
71         Map boxToSet = new HashMap(units.size() * 2 + 1, 0.7f);
72
73         if(Options.v().time())
74                 Timers.v().splitPhase1Timer.start();
75
76         // Go through the definitions, building the webs
77 {
78             ExceptionalUnitGraph graph = new ExceptionalUnitGraph(body);
79
80             LocalDefs localDefs;
81             
82             localDefs = new SmartLocalDefs(graph, new SimpleLiveLocals(graph));
83
84             LocalUses localUses = new SimpleLocalUses(graph, localDefs);
85             
86             if(Options.v().time())
87                 Timers.v().splitPhase1Timer.end();
88     
89             if(Options.v().time())
90                 Timers.v().splitPhase2Timer.start();
91
92             Set markedBoxes = new HashSet();
93             Map boxToUnit = new HashMap(units.size() * 2 + 1, 0.7f);
94             
95             Iterator codeIt = units.iterator();
96
97             while(codeIt.hasNext())
98             {
99                 Unit s = (Unit) codeIt.next();
100
101                 if (s.getDefBoxes().size() > 1)
102                     throw new RuntimeException JavaDoc("stmt with more than 1 defbox!");
103
104                 if (s.getDefBoxes().size() < 1)
105                     continue;
106
107                 ValueBox loBox = (ValueBox)s.getDefBoxes().get(0);
108                 Value lo = loBox.getValue();
109
110                 if(lo instanceof Local && !markedBoxes.contains(loBox))
111                 {
112                     LinkedList defsToVisit = new LinkedList();
113                     LinkedList boxesToVisit = new LinkedList();
114
115                     List web = new ArrayList();
116                     webs.add(web);
117                                         
118                     defsToVisit.add(s);
119                     markedBoxes.add(loBox);
120                     
121                     while(!boxesToVisit.isEmpty() || !defsToVisit.isEmpty())
122                     {
123                         if(!defsToVisit.isEmpty())
124                         {
125                             Unit d = (Unit) defsToVisit.removeFirst();
126
127                             web.add(d.getDefBoxes().get(0));
128
129                             // Add all the uses of this definition to the queue
130 {
131                                 List uses = localUses.getUsesOf(d);
132                                 Iterator useIt = uses.iterator();
133     
134                                 while(useIt.hasNext())
135                                 {
136                                     UnitValueBoxPair use = (UnitValueBoxPair) useIt.next();
137     
138                                     if(!markedBoxes.contains(use.valueBox))
139                                     {
140                                         markedBoxes.add(use.valueBox);
141                                         boxesToVisit.addLast(use.valueBox);
142                                         boxToUnit.put(use.valueBox, use.unit);
143                                     }
144                                 }
145                             }
146                         }
147                         else {
148                             ValueBox box = (ValueBox) boxesToVisit.removeFirst();
149
150                             web.add(box);
151
152                             // Add all the definitions of this use to the queue.
153 {
154                                 List defs = localDefs.getDefsOfAt((Local) box.getValue(),
155                                     (Unit) boxToUnit.get(box));
156                                 Iterator defIt = defs.iterator();
157     
158                                 while(defIt.hasNext())
159                                 {
160                                     Unit u = (Unit) defIt.next();
161
162                                     Iterator defBoxesIter = u.getDefBoxes().iterator();
163                                     ValueBox b;
164
165                                     for (; defBoxesIter.hasNext(); )
166                                     {
167                                         b = (ValueBox)defBoxesIter.next();
168                                         if(!markedBoxes.contains(b))
169                                         {
170                                             markedBoxes.add(b);
171                                             defsToVisit.addLast(u);
172                                         }
173                                     }
174                                 }
175                             }
176                         }
177                     }
178                 }
179             }
180         }
181
182         // Assign locals appropriately.
183 {
184             Map localToUseCount = new HashMap(body.getLocalCount() * 2 + 1, 0.7f);
185             Iterator webIt = webs.iterator();
186
187             while(webIt.hasNext())
188             {
189                 List web = (List) webIt.next();
190
191                 ValueBox rep = (ValueBox) web.get(0);
192                 Local desiredLocal = (Local) rep.getValue();
193
194                 if(!localToUseCount.containsKey(desiredLocal))
195                 {
196                     // claim this local for this set
197
198                     localToUseCount.put(desiredLocal, new Integer JavaDoc(1));
199                 }
200                 else {
201                     // generate a new local
202
203                     int useCount = ((Integer JavaDoc) localToUseCount.get(desiredLocal)).intValue() + 1;
204                     localToUseCount.put(desiredLocal, new Integer JavaDoc(useCount));
205         
206                     Local local = (Local) desiredLocal.clone();
207                     local.setName(desiredLocal.getName() + "#" + useCount);
208                     
209                     body.getLocals().add(local);
210
211                     // Change all boxes to point to this new local
212 {
213                         Iterator j = web.iterator();
214
215                         while(j.hasNext())
216                         {
217                             ValueBox box = (ValueBox) j.next();
218
219                             box.setValue(local);
220                         }
221                     }
222                 }
223             }
224         }
225         
226         if(Options.v().time())
227             Timers.v().splitPhase2Timer.end();
228
229     }
230 }
231
Popular Tags