SimpleLocalDefs


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.toolkits.scalar;
32  import soot.options.*;
33  
34  import soot.jimple.*;
35  import soot.toolkits.graph.*;
36  import soot.*;
37  import soot.util.*;
38  import java.util.*;
39  
40  
41  // FSet version
42  
43  
44  
45  /**
46   *   Analysis that provides an implementation of the LocalDefs interface.
47   */
48  public class SimpleLocalDefs implements LocalDefs
49  {
50      Map localUnitPairToDefs;
51  
52  
53      /**
54       *   Computes the analysis given a UnitGraph computed from a method body.
55       *   It is recommended that a ExceptionalUnitGraph (or similar) be provided
56       *   for correct results in the case of exceptional control flow.
57       *   @param g a graph on which to compute the analysis.
58       *   
59       *   @see ExceptionalUnitGraph
60       */
61      public SimpleLocalDefs(UnitGraph g)
62      {
63          if(Options.v().time())
64              Timers.v().defsTimer.start();
65          
66          if(Options.v().verbose())
67              G.v().out.println("[" + g.getBody().getMethod().getName() +
68                                 "]     Constructing SimpleLocalDefs...");
69      
70          LocalDefsFlowAnalysis analysis = new LocalDefsFlowAnalysis(g);
71          
72          if(Options.v().time())
73              Timers.v().defsPostTimer.start();
74  
75          // Build localUnitPairToDefs map
76          {
77              Iterator unitIt = g.iterator();
78  
79              localUnitPairToDefs = new HashMap(g.size() * 2 + 1, 0.7f);
80  
81              while(unitIt.hasNext())
82                  {
83                      Unit s = (Unit) unitIt.next();
84  
85                      Iterator boxIt = s.getUseBoxes().iterator();
86  
87                      while(boxIt.hasNext())
88                          {
89                              ValueBox box = (ValueBox) boxIt.next();
90  
91                              if(box.getValue() instanceof Local)
92                                  {
93                                      Local l = (Local) box.getValue();
94                                      LocalUnitPair pair = new LocalUnitPair(l, s);
95  
96                                      if(!localUnitPairToDefs.containsKey(pair))
97                                          {
98                                              IntPair intPair = (IntPair) analysis.localToIntPair.get(l);
99                          
100                                             ArrayPackedSet value = (ArrayPackedSet) analysis.getFlowBefore(s);
101 
102                                             List unitLocalDefs = value.toList(intPair.op1, intPair.op2);
103 
104                                             localUnitPairToDefs.put(pair, Collections.unmodifiableList(unitLocalDefs));
105                                         }
106                                 }
107                         }
108                 }
109         }
110 
111         if(Options.v().time())
112             Timers.v().defsPostTimer.end();
113                 
114         if(Options.v().time())
115             Timers.v().defsTimer.end();
116 
117     if(Options.v().verbose())
118         G.v().out.println("[" + g.getBody().getMethod().getName() +
119                                "]     SimpleLocalDefs finished.");
120     }
121 
122     public boolean hasDefsAt(Local l, Unit s)
123     {
124         return localUnitPairToDefs.containsKey( new LocalUnitPair(l,s) );
125     }
126     public List getDefsOfAt(Local l, Unit s)
127     {
128         LocalUnitPair pair = new LocalUnitPair(l, s);
129 
130         List toReturn = (List) localUnitPairToDefs.get(pair);
131         
132         if(toReturn == null)
133             throw new RuntimeException  ("Illegal LocalDefs query; local " + l + " has no definition at " + 
134                                        s.toString());
135                
136         
137         return toReturn;
138     }
139 
140     /*
141       public List getDefsOfBefore(Local l, Unit s)
142       {
143       IntPair pair = (IntPair) analysis.localToIntPair.get(l);
144       FSet value = (FSet) analysis.getValueBeforeUnit(s);
145 
146       List unitLocalDefs = value.toList(pair.op1, pair.op2);
147 
148       return unitLocalDefs;
149       }*/
150 
151     /*
152       Object[] elements = ((FSet) analysis.getValueBeforeUnit(s)).toArray();
153       List listOfDefs = new LinkedList();
154 
155       // Extract those defs which correspond to this local
156       {
157       for(int i = 0; i < elements.length; i++)
158       {
159       DefinitionUnit d = (DefinitionUnit) elements[i];
160 
161       if(d.getLeftOp() == l)
162       listOfDefs.add(d);
163       }
164       }
165 
166       // Convert the array so that it's of an appropriate form
167       {
168       Object[] objects = listOfDefs.toArray();
169       DefinitionUnit[] defs = new DefinitionUnit[objects.length];
170 
171       for(int i = 0; i < defs.length; i++)
172       defs[i] = (DefinitionUnit) objects[i];
173 
174       return defs;
175       }
176 
177       }
178       }
179     */
180 
181     /*
182       public DefinitionUnit[] getDefsOfAfter(Local l, Unit s)
183       {
184       Object[] elements = ((FSet) analysis.getValueAfterUnit(s)).toArray();
185       List listOfDefs = new LinkedList();
186 
187       // Extract those defs which correspond to this local
188       {
189       for(int i = 0; i < elements.length; i++)
190       {
191       DefinitionUnit d = (DefinitionUnit) elements[i];
192 
193       if(d.getLeftOp() == l)
194       listOfDefs.add(d);
195       }
196       }
197 
198       // Convert the array so that it's of an appropriate form
199       {
200       Object[] objects = listOfDefs.toArray();
201       DefinitionUnit[] defs = new DefinitionUnit[objects.length];
202 
203       for(int i = 0; i < defs.length; i++)
204       defs[i] = (DefinitionUnit) objects[i];
205 
206       return defs;
207       }
208       }
209 
210       public DefinitionUnit[] getDefsBefore(Unit s)
211       {
212       Object[] elements = ((FSet) analysis.getValueBeforeUnit(s)).toArray();
213       DefinitionUnit[] defs = new DefinitionUnit[elements.length];
214 
215       for(int i = 0; i < elements.length; i++)
216       defs[i] = (DefinitionUnit) elements[i];
217 
218       return defs;
219       }
220 
221       public DefinitionUnit[] getDefsAfter(Unit s)
222       {
223       Object[] elements = ((FSet) analysis.getValueAfterUnit(s)).toArray();
224       DefinitionUnit[] defs = new DefinitionUnit[elements.length];
225 
226       for(int i = 0; i < elements.length; i++)
227       defs[i] = (DefinitionUnit) elements[i];
228 
229       return defs;
230       }
231     */
232 }
233 
234 class IntPair
235 {
236     int op1, op2;
237 
238     public IntPair(int op1, int op2)
239     {
240         this.op1 = op1;
241         this.op2 = op2;
242     }
243 
244 }
245 
246 class LocalDefsFlowAnalysis extends ForwardFlowAnalysis
247 {
248     FlowSet emptySet;
249     Map localToPreserveSet;
250     Map localToIntPair;
251 
252     public LocalDefsFlowAnalysis(UnitGraph g)
253     {
254         super(g);
255 
256         Object  [] defs;
257         FlowUniverse defUniverse;
258 
259         if(Options.v().time())
260             Timers.v().defsSetupTimer.start();
261 
262         // Create a list of all the definitions and group defs of the same local together
263         {
264             Map localToDefList = new HashMap(g.getBody().getLocalCount() * 2 + 1, 0.7f);
265 
266             // Initialize the set of defs for each local to empty
267             {
268                 Iterator localIt = g.getBody().getLocals().iterator();
269 
270                 while(localIt.hasNext())
271                     {
272                         Local l = (Local) localIt.next();
273 
274                         localToDefList.put(l, new ArrayList());
275                     }
276             }
277 
278             // Fill the sets up
279             {
280                 Iterator it = g.iterator();
281 
282                 while(it.hasNext())
283                     {
284                         Unit s = (Unit) it.next();
285 
286                     
287                         List defBoxes = s.getDefBoxes();
288                         if(!defBoxes.isEmpty()) {
289                             if(!(defBoxes.size() ==1)) 
290                                 throw new RuntimeException  ("invalid number of def boxes");
291                             
292                             if(((ValueBox)defBoxes.get(0)).getValue() instanceof Local) {
293                                 Local defLocal = (Local) ((ValueBox)defBoxes.get(0)).getValue();
294                                 List l = (List) localToDefList.get(defLocal);
295                             
296                                 if(l == null)
297                                     throw new RuntimeException  ("local " + defLocal + " is used but not declared!");
298                                 else
299                                     l.add(s);
300                             }
301                         }
302                     
303                     }
304             }
305 
306             // Generate the list & localToIntPair
307             {
308                 Iterator it = g.getBody().getLocals().iterator();
309                 List defList = new LinkedList();
310 
311                 int startPos = 0;
312 
313                 localToIntPair = new HashMap(g.getBody().getLocalCount() * 2 + 1, 0.7f);
314 
315                 // For every local, add all its defs
316                 {
317                     while(it.hasNext())
318                         {
319                             Local l = (Local) it.next();
320                             Iterator jt = ((List) localToDefList.get(l)).iterator();
321 
322                             int endPos = startPos - 1;
323 
324                             while(jt.hasNext())
325                                 {
326                                     defList.add(jt.next());
327                                     endPos++;
328                                 }
329 
330                             localToIntPair.put(l, new IntPair(startPos, endPos));
331 
332                             // G.v().out.println(startPos + ":" + endPos);
333 
334                             startPos = endPos + 1;
335                         }
336                 }
337 
338                 defs = defList.toArray();
339                 defUniverse = new ArrayFlowUniverse(defs);
340             }
341         }
342 
343         emptySet = new ArrayPackedSet(defUniverse);
344 
345         // Create the preserve sets for each local.
346         {
347             Map localToKillSet = new HashMap(g.getBody().getLocalCount() * 2 + 1, 0.7f);
348             localToPreserveSet = new HashMap(g.getBody().getLocalCount() * 2 + 1, 0.7f);
349 
350             Chain locals = g.getBody().getLocals();
351 
352             // Initialize to empty set
353             {
354                 Iterator localIt = locals.iterator();
355 
356                 while(localIt.hasNext())
357                     {
358                         Local l = (Local) localIt.next();
359 
360                         localToKillSet.put(l, emptySet.clone());
361                     }
362             }
363 
364             // Add every definition of this local
365             for(int i = 0; i < defs.length; i++)
366                 {
367                     Unit s = (Unit) defs[i];
368                     
369                     List defBoxes = s.getDefBoxes();
370                     if(!(defBoxes.size() ==1)) 
371                         throw new RuntimeException  ("SimpleLocalDefs: invalid number of def boxes");
372                             
373                     if(((ValueBox)defBoxes.get(0)).getValue() instanceof Local) {
374                         Local defLocal = (Local) ((ValueBox)defBoxes.get(0)).getValue();
375                         BoundedFlowSet killSet = (BoundedFlowSet) localToKillSet.get(defLocal);
376                         killSet.add(s, killSet);
377                         
378                     }
379                 }
380             
381             // Store complement
382             {
383                 Iterator localIt = locals.iterator();
384 
385                 while(localIt.hasNext())
386                     {
387                         Local l = (Local) localIt.next();
388 
389                         BoundedFlowSet killSet = (BoundedFlowSet) localToKillSet.get(l);
390 
391                         killSet.complement(killSet);
392 
393                         localToPreserveSet.put(l, killSet);
394                     }
395             }
396         }
397 
398         if(Options.v().time())
399             Timers.v().defsSetupTimer.end();
400 
401         if(Options.v().time())
402             Timers.v().defsAnalysisTimer.start();
403 
404         doAnalysis();
405         
406         if(Options.v().time())
407             Timers.v().defsAnalysisTimer.end();
408     }
409     
410     protected Object   newInitialFlow()
411     {
412         return emptySet.clone();
413     }
414 
415     protected Object   entryInitialFlow()
416     {
417         return emptySet.clone();
418     }
419 
420     protected void flowThrough(Object   inValue, Object   d, Object   outValue)
421     {
422         FlowSet in = (FlowSet) inValue, out = (FlowSet) outValue;
423         Unit unit = (Unit)d;
424 
425         List defBoxes = unit.getDefBoxes();
426         if(!defBoxes.isEmpty()) {
427             if(!(defBoxes.size() ==1)) 
428                 throw new RuntimeException  ("SimpleLocalDefs: invalid number of def boxes");
429                           
430             Value value = ((ValueBox)defBoxes.get(0)).getValue();
431             if(value  instanceof Local) {
432                 Local defLocal = (Local) value;
433             
434                 // Perform kill on value
435                 in.intersection((FlowSet) localToPreserveSet.get(defLocal), out);
436 
437                 // Perform generation
438                 out.add(unit, out);
439             } else { 
440                 in.copy(out);
441                 return;
442             }
443 
444 
445         
446 
447         }
448         else
449             in.copy(out);
450     }
451 
452     protected void copy(Object   source, Object   dest)
453     {
454         FlowSet sourceSet = (FlowSet) source,
455             destSet = (FlowSet) dest;
456         
457         sourceSet.copy(destSet);
458     }
459 
460     protected void merge(Object   in1, Object   in2, Object   out)
461     {
462         FlowSet inSet1 = (FlowSet) in1,
463             inSet2 = (FlowSet) in2;
464         
465         FlowSet outSet = (FlowSet) out;
466         
467         inSet1.union(inSet2, outSet);
468     }
469 }
470
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags