KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > base > Aggregator


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 /* Reference Version: $SootVersion: 1.2.5.dev.5 $ */
27
28 package soot.jimple.toolkits.base;
29 import soot.options.*;
30
31 import soot.*;
32 import soot.jimple.*;
33 import soot.toolkits.scalar.*;
34 import soot.toolkits.graph.*;
35 import soot.util.*;
36 import java.util.*;
37
38 public class Aggregator extends BodyTransformer
39 {
40     public Aggregator( Singletons.Global g ) {}
41     public static Aggregator v() { return G.v().soot_jimple_toolkits_base_Aggregator(); }
42
43     /** Traverse the statements in the given body, looking for
44       * aggregation possibilities; that is, given a def d and a use u,
45       * d has no other uses, u has no other defs, collapse d and u.
46       *
47       * option: only-stack-locals; if this is true, only aggregate variables
48                         starting with $ */
49     protected void internalTransform(Body b, String JavaDoc phaseName, Map options)
50     {
51         StmtBody body = (StmtBody)b;
52         boolean onlyStackVars = PhaseOptions.getBoolean(options, "only-stack-locals");
53
54         int aggregateCount = 1;
55
56         if(Options.v().time())
57             Timers.v().aggregationTimer.start();
58          boolean changed = false;
59
60         Map boxToZone = new HashMap(body.getUnits().size() * 2 + 1, 0.7f);
61
62         // Determine the zone of every box
63 {
64             Zonation zonation = new Zonation(body);
65             
66             Iterator unitIt = body.getUnits().iterator();
67             
68             while(unitIt.hasNext())
69             {
70                 Unit u = (Unit) unitIt.next();
71                 Zone zone = (Zone) zonation.getZoneOf(u);
72                 
73                 Iterator boxIt = u.getUseBoxes().iterator();
74                 while(boxIt.hasNext())
75                 {
76                     ValueBox box = (ValueBox) boxIt.next();
77                     boxToZone.put(box, zone);
78                 }
79                 boxIt = u.getDefBoxes().iterator();
80                 while(boxIt.hasNext())
81                 {
82                     ValueBox box = (ValueBox) boxIt.next();
83                     boxToZone.put(box, zone);
84                 }
85             }
86         }
87         
88                      
89         do {
90             if(Options.v().verbose())
91                 G.v().out.println("[" + body.getMethod().getName() + "] Aggregating iteration " + aggregateCount + "...");
92         
93             // body.printTo(new java.io.PrintWriter(G.v().out, true));
94
95             changed = internalAggregate(body, boxToZone, onlyStackVars);
96             
97             aggregateCount++;
98         } while(changed);
99         
100         if(Options.v().time())
101             Timers.v().aggregationTimer.end();
102             
103     }
104   
105   private static boolean internalAggregate(StmtBody body, Map boxToZone, boolean onlyStackVars)
106     {
107       Iterator stmtIt;
108       LocalUses localUses;
109       LocalDefs localDefs;
110       ExceptionalUnitGraph graph;
111       boolean hadAggregation = false;
112       Chain units = body.getUnits();
113       
114       graph = new ExceptionalUnitGraph(body);
115       localDefs = new SmartLocalDefs(graph, new SimpleLiveLocals(graph));
116       localUses = new SimpleLocalUses(graph, localDefs);
117           
118       stmtIt = (new PseudoTopologicalOrderer()).newList(graph).iterator();
119       
120       while (stmtIt.hasNext())
121         {
122           Stmt s = (Stmt)(stmtIt.next());
123               
124           if (!(s instanceof AssignStmt))
125             continue;
126           
127           Value lhs = ((AssignStmt)s).getLeftOp();
128           if (!(lhs instanceof Local))
129             continue;
130     
131           if(onlyStackVars && !((Local) lhs).getName().startsWith("$"))
132             continue;
133             
134           List lu = localUses.getUsesOf((AssignStmt)s);
135           if (lu.size() != 1)
136             continue;
137             
138           UnitValueBoxPair usepair = (UnitValueBoxPair)lu.get(0);
139           Unit use = usepair.unit;
140           ValueBox useBox = usepair.valueBox;
141               
142           List ld = localDefs.getDefsOfAt((Local)lhs, use);
143           if (ld.size() != 1)
144             continue;
145    
146           // Check to make sure aggregation pair in the same zone
147 if(boxToZone.get(((AssignStmt) s).getRightOpBox()) != boxToZone.get(usepair.valueBox))
148             {
149                 continue;
150             }
151              
152           /* we need to check the path between def and use */
153           /* to see if there are any intervening re-defs of RHS */
154           /* in fact, we should check that this path is unique. */
155           /* if the RHS uses only locals, then we know what
156              to do; if RHS has a method invocation f(a, b,
157              c) or field access, we must ban field writes, other method
158              calls and (as usual) writes to a, b, c. */
159           
160           boolean cantAggr = false;
161           boolean propagatingInvokeExpr = false;
162           boolean propagatingFieldRef = false;
163           boolean propagatingArrayRef = false;
164           ArrayList fieldRefList = new ArrayList();
165       
166           Value rhs = ((AssignStmt)s).getRightOp();
167           LinkedList localsUsed = new LinkedList();
168           for (Iterator useIt = (s.getUseBoxes()).iterator();
169                useIt.hasNext(); )
170             {
171               Value v = ((ValueBox)(useIt.next())).getValue();
172                 if (v instanceof Local)
173                     localsUsed.add(v);
174                 else if (v instanceof InvokeExpr)
175                     propagatingInvokeExpr = true;
176                 else if(v instanceof ArrayRef)
177                     propagatingArrayRef = true;
178                 else if(v instanceof FieldRef)
179                 {
180                     propagatingFieldRef = true;
181                     fieldRefList.add(v);
182                 }
183             }
184           
185           // look for a path from s to use in graph.
186 // only look in an extended basic block, though.
187
188           List path = graph.getExtendedBasicBlockPathBetween(s, use);
189       
190           if (path == null)
191             continue;
192
193           Iterator pathIt = path.iterator();
194
195           // skip s.
196 if (pathIt.hasNext())
197             pathIt.next();
198
199           while (pathIt.hasNext() && !cantAggr)
200           {
201               Stmt between = (Stmt)(pathIt.next());
202           
203               if(between != use)
204               {
205                 // Check for killing definitions
206
207                 for (Iterator it = between.getDefBoxes().iterator();
208                        it.hasNext(); )
209                   {
210                       Value v = ((ValueBox)(it.next())).getValue();
211                       if (localsUsed.contains(v))
212                       {
213                             cantAggr = true;
214                             break;
215                       }
216                       
217                       if (propagatingInvokeExpr || propagatingFieldRef || propagatingArrayRef)
218                       {
219                           if (v instanceof FieldRef)
220                           {
221                               if(propagatingInvokeExpr)
222                               {
223                                   cantAggr = true;
224                                   break;
225                               }
226                               else if(propagatingFieldRef)
227                               {
228                                   // Can't aggregate a field access if passing a definition of a field
229 // with the same name, because they might be aliased
230
231                                   Iterator frIt = fieldRefList.iterator();
232                                   while (frIt.hasNext())
233                                   {
234                                       FieldRef fieldRef = (FieldRef) frIt.next();
235                                       if(((FieldRef) v).getField() == fieldRef.getField())
236                                       {
237                                           cantAggr = true;
238                                           break;
239                                       }
240                                   }
241                               }
242                            }
243                            else if(v instanceof ArrayRef)
244                            {
245                                 if(propagatingInvokeExpr)
246                                 {
247                                     // Cannot aggregate an invoke expr past an array write
248 cantAggr = true;
249                                     break;
250                                 }
251                                 else if(propagatingArrayRef)
252                                 {
253                                     // cannot aggregate an array read past a write
254 // this is somewhat conservative
255 // (if types differ they may not be aliased)
256
257                                     cantAggr = true;
258                                     break;
259                                 }
260                            }
261                       }
262                   }
263                   
264                   // Make sure not propagating past a {enter,exit}Monitor
265 if(propagatingInvokeExpr && between instanceof MonitorStmt)
266                         cantAggr = true;
267               }
268                             
269               // Check for intervening side effects due to method calls
270 if(propagatingInvokeExpr || propagatingFieldRef || propagatingArrayRef)
271                     {
272                       for( Iterator boxIt = (between.getUseBoxes()).iterator(); boxIt.hasNext(); ) {
273                           final ValueBox box = (ValueBox) boxIt.next();
274                           
275                           if(between == use && box == useBox)
276                           {
277                                 // Reached use point, stop looking for
278 // side effects
279 break;
280                           }
281                           
282                           Value v = box.getValue();
283                           
284                             if (v instanceof InvokeExpr ||
285                                 (propagatingInvokeExpr && (v instanceof FieldRef || v instanceof ArrayRef)))
286                             {
287                                 cantAggr = true;
288                                 break;
289                             }
290                             
291                         }
292                     }
293             }
294
295           // we give up: can't aggregate.
296 if (cantAggr)
297           {
298             continue;
299           }
300           /* assuming that the d-u chains are correct, */
301           /* we need not check the actual contents of ld */
302           
303           Value aggregatee = ((AssignStmt)s).getRightOp();
304           
305           if (usepair.valueBox.canContainValue(aggregatee))
306             {
307               boolean wasSimpleCopy = isSimpleCopy( usepair.unit );
308               usepair.valueBox.setValue(aggregatee);
309               units.remove(s);
310               hadAggregation = true;
311               // clean up the tags. If s was not a simple copy, the new statement should get
312 // the tags of s.
313 // OK, this fix was wrong. The condition should not be
314 // "If s was not a simple copy", but rather "If usepair.unit
315 // was a simple copy". This way, when there's a load of a constant
316 // followed by an invoke, the invoke gets the tags.
317 if( wasSimpleCopy ) {
318                   //usepair.unit.removeAllTags();
319 usepair.unit.addAllTagsOf( s );
320               }
321             }
322           else
323             {/*
324             if(Options.v().verbose())
325             {
326                 G.v().out.println("[debug] failed aggregation");
327                   G.v().out.println("[debug] tried to put "+aggregatee+
328                                  " into "+usepair.stmt +
329                                  ": in particular, "+usepair.valueBox);
330                   G.v().out.println("[debug] aggregatee instanceof Expr: "
331                                  +(aggregatee instanceof Expr));
332             }*/
333             }
334         }
335       return hadAggregation;
336     }
337   private static boolean isSimpleCopy( Unit u ) {
338       if( !(u instanceof DefinitionStmt) ) return false;
339       DefinitionStmt defstmt = (DefinitionStmt) u;
340       if( !( defstmt.getRightOp() instanceof Local ) ) return false;
341       if( !( defstmt.getLeftOp() instanceof Local ) ) return false;
342       return true;
343   }
344         
345 }
346
347
Popular Tags