KickJava   Java API By Example, From Geeks To Geeks.

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


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 package soot.toolkits.scalar;
28
29 import soot.*;
30 import soot.toolkits.graph.*;
31 import soot.util.*;
32 import java.util.*;
33 import soot.options.*;
34 import soot.toolkits.graph.interaction.*;
35
36 /**
37  * Abstract class that provides the fixed point iteration functionality
38  * required by all ForwardFlowAnalyses.
39  *
40  */
41 public abstract class ForwardFlowAnalysis extends FlowAnalysis
42 {
43     /** Construct the analysis from a DirectedGraph representation of a Body. */
44     public ForwardFlowAnalysis(DirectedGraph graph)
45     {
46         super(graph);
47     }
48
49     protected boolean isForward()
50     {
51         return true;
52     }
53
54     protected void doAnalysis()
55     {
56         final Map numbers = new HashMap();
57         List orderedUnits = new PseudoTopologicalOrderer().newList(graph);
58         int i = 1;
59         for( Iterator uIt = orderedUnits.iterator(); uIt.hasNext(); ) {
60             final Object JavaDoc u = (Object JavaDoc) uIt.next();
61             numbers.put(u, new Integer JavaDoc(i));
62             i++;
63         }
64
65         TreeSet changedUnits = new TreeSet( new Comparator() {
66             public int compare(Object JavaDoc o1, Object JavaDoc o2) {
67                 Integer JavaDoc i1 = (Integer JavaDoc) numbers.get(o1);
68                 Integer JavaDoc i2 = (Integer JavaDoc) numbers.get(o2);
69                 return (i1.intValue() - i2.intValue());
70             }
71         } );
72
73         List heads = graph.getHeads();
74         int numNodes = graph.size();
75         int numComputations = 0;
76         
77         // Set initial values and nodes to visit.
78 {
79             Iterator it = graph.iterator();
80
81             while(it.hasNext())
82             {
83                 Object JavaDoc s = it.next();
84
85                 changedUnits.add(s);
86
87                 unitToBeforeFlow.put(s, newInitialFlow());
88                 unitToAfterFlow.put(s, newInitialFlow());
89             }
90         }
91
92         // Feng Qian: March 07, 2002
93 // Set initial values for entry points
94 {
95             Iterator it = heads.iterator();
96             
97             while (it.hasNext()) {
98                 Object JavaDoc s = it.next();
99                 // this is a forward flow analysis
100 unitToBeforeFlow.put(s, entryInitialFlow());
101             }
102         }
103         
104         // Perform fixed point flow analysis
105 {
106             Object JavaDoc previousAfterFlow = newInitialFlow();
107
108             int iterationCounter = 0;
109             while(!changedUnits.isEmpty())
110             {
111                 Object JavaDoc beforeFlow;
112                 Object JavaDoc afterFlow;
113
114                 Object JavaDoc s = changedUnits.first();
115                 changedUnits.remove(s);
116                 boolean isHead = heads.contains(s);
117
118                 copy(unitToAfterFlow.get(s), previousAfterFlow);
119
120                 // Compute and store beforeFlow
121 {
122                     List preds = graph.getPredsOf(s);
123
124                     beforeFlow = unitToBeforeFlow.get(s);
125
126                     if(preds.size() == 1)
127                         copy(unitToAfterFlow.get(preds.get(0)), beforeFlow);
128                     else if(preds.size() != 0)
129                     {
130                         Iterator predIt = preds.iterator();
131
132                         copy(unitToAfterFlow.get(predIt.next()), beforeFlow);
133
134                         while(predIt.hasNext())
135                         {
136                             Object JavaDoc otherBranchFlow = unitToAfterFlow.get(predIt.
137 next());
138                             merge(beforeFlow, otherBranchFlow);
139                         }
140                     }
141
142                     if(isHead && preds.size() != 0)
143                         merge(beforeFlow, entryInitialFlow());
144                 }
145
146                 // Compute afterFlow and store it.
147 {
148                     afterFlow = unitToAfterFlow.get(s);
149                     if (Options.v().interactive_mode()){
150                         
151                         Object JavaDoc savedInfo = newInitialFlow();
152                         if (filterUnitToBeforeFlow != null){
153                             savedInfo = filterUnitToBeforeFlow.get(s);
154                             copy(filterUnitToBeforeFlow.get(s), savedInfo);
155                         }
156                         else {
157                             copy(beforeFlow, savedInfo);
158                         }
159                         FlowInfo fi = new FlowInfo(savedInfo, s, true);
160                         if (InteractionHandler.v().getStopUnitList() != null && InteractionHandler.v().getStopUnitList().contains(s)){
161                             InteractionHandler.v().handleStopAtNodeEvent(s);
162                         }
163                         InteractionHandler.v().handleBeforeAnalysisEvent(fi);
164                     }
165                     flowThrough(beforeFlow, s, afterFlow);
166                     if (Options.v().interactive_mode()){
167                         Object JavaDoc aSavedInfo = newInitialFlow();
168                         if (filterUnitToAfterFlow != null){
169                             aSavedInfo = filterUnitToAfterFlow.get(s);
170                             copy(filterUnitToAfterFlow.get(s), aSavedInfo);
171                         }
172                         else {
173                             copy(afterFlow, aSavedInfo);
174                         }
175                         FlowInfo fi = new FlowInfo(aSavedInfo, s, false);
176                         InteractionHandler.v().handleAfterAnalysisEvent(fi);
177                     }
178                     numComputations++;
179                 }
180
181                 // Update queue appropriately
182 if(!afterFlow.equals(previousAfterFlow))
183                     {
184                         Iterator succIt = graph.getSuccsOf(s).iterator();
185
186                         while(succIt.hasNext())
187                         {
188                             Object JavaDoc succ = succIt.next();
189                             
190                             changedUnits.add(succ);
191                         }
192                     }
193             }
194         }
195         
196         // G.v().out.println(graph.getBody().getMethod().getSignature() + " numNodes: " + numNodes +
197 // " numComputations: " + numComputations + " avg: " + Main.truncatedOf((double) numComputations / numNodes, 2));
198
199         Timers.v().totalFlowNodes += numNodes;
200         Timers.v().totalFlowComputations += numComputations;
201     }
202 }
203
204
205
Popular Tags