KickJava   Java API By Example, From Geeks To Geeks.

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


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 1997-2000 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-2000.
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     2000, March 20 - Updated code provided by Patrick Lam
29                             <plam@sable.mcgill.ca>
30                      from 1.beta.4.dev.60
31                      to 1.beta.6.dev.34
32                      Plus some bug fixes.
33                      -- Janus <janus@place.org>
34
35
36      KNOWN LIMITATION: the analysis doesn't handle traps since traps
37                handler statements have predecessors, but they
38                don't have the trap handler as successor. This
39                might be a limitation of the CompleteUnitGraph
40                tho.
41 */
42
43
44 package soot.toolkits.scalar;
45
46 import soot.*;
47 import soot.toolkits.graph.*;
48 import soot.util.*;
49 import java.util.*;
50 import soot.toolkits.graph.interaction.*;
51 import soot.options.*;
52
53 /** Abstract class providing an engine for branched forward flow analysis. */
54 public abstract class ForwardBranchedFlowAnalysis extends BranchedFlowAnalysis
55 {
56     public ForwardBranchedFlowAnalysis(UnitGraph graph)
57     {
58         super(graph);
59     }
60
61     protected boolean isForward()
62     {
63         return true;
64     }
65
66     // Accumulate the previous afterFlow sets.
67 private void accumulateAfterFlowSets(Unit s, Object JavaDoc[] flowRepositories, List previousAfterFlows)
68     {
69         int repCount = 0;
70         
71         previousAfterFlows.clear();
72         if (s.fallsThrough())
73         {
74             copy(((List) unitToAfterFallFlow.get(s)).get(0), flowRepositories[repCount]);
75             previousAfterFlows.add(flowRepositories[repCount++]);
76         }
77         
78         if (s.branches())
79         {
80             List l = (List)(unitToAfterBranchFlow.get(s));
81             Iterator it = l.iterator();
82
83             while (it.hasNext())
84             {
85                 Object JavaDoc fs = (Object JavaDoc) (it.next());
86                 copy(fs, flowRepositories[repCount]);
87                 previousAfterFlows.add(flowRepositories[repCount++]);
88             }
89         }
90     } // end accumulateAfterFlowSets
91
92
93     protected void doAnalysis()
94     {
95         final Map numbers = new HashMap();
96         List orderedUnits = new PseudoTopologicalOrderer().newList(graph);
97         {
98             int i = 1;
99             for( Iterator uIt = orderedUnits.iterator(); uIt.hasNext(); ) {
100                 final Unit u = (Unit) uIt.next();
101                 numbers.put(u, new Integer JavaDoc(i));
102                 i++;
103             }
104         }
105
106         TreeSet changedUnits = new TreeSet( new Comparator() {
107             public int compare(Object JavaDoc o1, Object JavaDoc o2) {
108                 Integer JavaDoc i1 = (Integer JavaDoc) numbers.get(o1);
109                 Integer JavaDoc i2 = (Integer JavaDoc) numbers.get(o2);
110                 return (i1.intValue() - i2.intValue());
111             }
112         } );
113
114         Map unitToIncomingFlowSets = new HashMap(graph.size() * 2 + 1, 0.7f);
115         List heads = graph.getHeads();
116         int numNodes = graph.size();
117         int numComputations = 0;
118         int maxBranchSize = 0;
119         
120         // initialize unitToIncomingFlowSets
121 {
122             Iterator it = graph.iterator();
123
124             while (it.hasNext())
125             {
126                 Unit s = (Unit) it.next();
127
128                 unitToIncomingFlowSets.put(s, new ArrayList());
129             }
130         }
131
132         // Set initial values and nodes to visit.
133 // WARNING: DO NOT HANDLE THE CASE OF THE TRAPS
134 {
135             Chain sl = ((UnitGraph)graph).getBody().getUnits();
136             Iterator it = graph.iterator();
137
138             while(it.hasNext())
139             {
140                 Unit s = (Unit) it.next();
141
142                 changedUnits.add(s);
143
144                 unitToBeforeFlow.put(s, newInitialFlow());
145
146                 if (s.fallsThrough())
147                 {
148                     ArrayList fl = new ArrayList();
149
150                     fl.add((Object JavaDoc) (newInitialFlow()));
151                     unitToAfterFallFlow.put(s, fl);
152
153             Unit succ=(Unit) sl.getSuccOf(s);
154             // it's possible for someone to insert some (dead)
155 // fall through code at the very end of a method body
156 if(succ!=null) {
157             List l = (List)
158                 (unitToIncomingFlowSets.get(sl.getSuccOf(s)));
159             l.addAll(fl);
160             }
161                 }
162                 else
163                     unitToAfterFallFlow.put(s, new ArrayList());
164
165                 if (s.branches())
166                 {
167                     ArrayList l = new ArrayList();
168                     List incList;
169                     Iterator boxIt = s.getUnitBoxes().iterator();
170
171                     while (boxIt.hasNext())
172                     {
173                         Object JavaDoc f = (Object JavaDoc) (newInitialFlow());
174
175                         l.add(f);
176                         Unit ss = ((UnitBox) (boxIt.next())).getUnit();
177                         incList = (List) (unitToIncomingFlowSets.get(ss));
178                                           
179                         incList.add(f);
180                     }
181                     unitToAfterBranchFlow.put(s, l);
182                 }
183                 else
184                     unitToAfterBranchFlow.put(s, new ArrayList());
185
186                 if (s.getUnitBoxes().size() > maxBranchSize)
187                     maxBranchSize = s.getUnitBoxes().size();
188             }
189         }
190
191         // Feng Qian: March 07, 2002
192 // init entry points
193 {
194             Iterator it = heads.iterator();
195
196             while (it.hasNext()) {
197                 Object JavaDoc s = it.next();
198                 // this is a forward flow analysis
199 unitToBeforeFlow.put(s, entryInitialFlow());
200             }
201         }
202
203         if (treatTrapHandlersAsEntries())
204         {
205             Iterator trapIt = ((UnitGraph)graph).getBody().
206                                    getTraps().iterator();
207             while(trapIt.hasNext()) {
208                 Trap trap = (Trap) trapIt.next();
209                 Unit handler = trap.getHandlerUnit();
210                 unitToBeforeFlow.put(handler, entryInitialFlow());
211             }
212         }
213
214         // Perform fixed point flow analysis
215 {
216             List previousAfterFlows = new ArrayList();
217             List afterFlows = new ArrayList();
218             Object JavaDoc[] flowRepositories = new Object JavaDoc[maxBranchSize+1];
219             for (int i = 0; i < maxBranchSize+1; i++)
220                 flowRepositories[i] = (Object JavaDoc) newInitialFlow();
221             Object JavaDoc[] previousFlowRepositories = new Object JavaDoc[maxBranchSize+1];
222             for (int i = 0; i < maxBranchSize+1; i++)
223                 previousFlowRepositories[i] = (Object JavaDoc) newInitialFlow();
224
225             while(!changedUnits.isEmpty())
226             {
227                 Object JavaDoc beforeFlow;
228
229                 Unit s = (Unit) changedUnits.first();
230                 changedUnits.remove(s);
231                 boolean isHead = heads.contains(s);
232
233                 accumulateAfterFlowSets(s, previousFlowRepositories, previousAfterFlows);
234
235                 // Compute and store beforeFlow
236 {
237                     List preds = (List) (unitToIncomingFlowSets.get(s));
238
239                     beforeFlow = unitToBeforeFlow.get(s);
240
241                     if(preds.size() == 1)
242                         copy(preds.get(0), beforeFlow);
243                     else if(preds.size() != 0)
244                     {
245                         Iterator predIt = preds.iterator();
246
247                         copy(predIt.next(), beforeFlow);
248
249                         while(predIt.hasNext())
250                         {
251                             Object JavaDoc otherBranchFlow = predIt.next();
252                             Object JavaDoc newBeforeFlow = newInitialFlow();
253                             merge(beforeFlow, otherBranchFlow, newBeforeFlow);
254                             copy(newBeforeFlow, beforeFlow);
255                         }
256                     }
257
258                     if(isHead && preds.size() != 0)
259                         merge(beforeFlow, entryInitialFlow());
260                 }
261
262                 // Compute afterFlow and store it.
263 {
264                     Object JavaDoc afterFallFlow = unitToAfterFallFlow.get(s);
265                     Object JavaDoc afterBranchFlow = unitToAfterBranchFlow.get(s);
266                     if (Options.v().interactive_mode()){
267                         Object JavaDoc savedFlow = newInitialFlow();
268                         copy(beforeFlow, savedFlow);
269                         FlowInfo fi = new FlowInfo(savedFlow, s, true);
270                         if (InteractionHandler.v().getStopUnitList() != null && InteractionHandler.v().getStopUnitList().contains(s)){
271                             InteractionHandler.v().handleStopAtNodeEvent(s);
272                         }
273                         InteractionHandler.v().handleBeforeAnalysisEvent(fi);
274                     }
275                     flowThrough(beforeFlow, s, (List) afterFallFlow, (List) afterBranchFlow);
276                     if (Options.v().interactive_mode()){
277                         ArrayList l = new ArrayList();
278                         if (!((List)afterFallFlow).isEmpty()){
279                             l.addAll((List)afterFallFlow);
280                         }
281                         if (!((List)afterBranchFlow).isEmpty()){
282                             l.addAll((List)afterBranchFlow);
283                         }
284                         
285                         /*if (s instanceof soot.jimple.IfStmt){
286                             l.addAll((List)afterFallFlow);
287                             l.addAll((List)afterBranchFlow);
288                         }
289                         else {
290                             l.addAll((List)afterFallFlow);
291                         }*/
292                         FlowInfo fi = new FlowInfo(l, s, false);
293                         InteractionHandler.v().handleAfterAnalysisEvent(fi);
294                     }
295                     numComputations++;
296                 }
297
298                 accumulateAfterFlowSets(s, flowRepositories, afterFlows);
299
300                 // Update queue appropriately
301 if(!afterFlows.equals(previousAfterFlows))
302                 {
303                     Iterator succIt = graph.getSuccsOf(s).iterator();
304
305                     while(succIt.hasNext())
306                     {
307                         Unit succ = (Unit) succIt.next();
308                             
309                         changedUnits.add(succ);
310                     }
311                 }
312             }
313         }
314         
315         // G.v().out.println(graph.getBody().getMethod().getSignature() + " numNodes: " + numNodes +
316 // " numComputations: " + numComputations + " avg: " + Main.truncatedOf((double) numComputations / numNodes, 2));
317
318         Timers.v().totalFlowNodes += numNodes;
319         Timers.v().totalFlowComputations += numComputations;
320
321     } // end doAnalysis
322
323 } // end class ForwardBranchedFlowAnalysis
324
Popular Tags