KickJava   Java API By Example, From Geeks To Geeks.

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


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
38 /**
39  * Abstract class that provides the fixed point iteration functionality
40  * required by all BackwardFlowAnalyses.
41  *
42  */
43 public abstract class BackwardFlowAnalysis extends FlowAnalysis
44 {
45     /** Construct the analysis from a DirectedGraph representation of a Body. */
46     public BackwardFlowAnalysis(DirectedGraph graph)
47     {
48         super(graph);
49     }
50
51     protected boolean isForward()
52     {
53         return false;
54     }
55
56     protected void doAnalysis()
57     {
58         final Map numbers = new HashMap();
59         List orderedUnits = new PseudoTopologicalOrderer().newList(graph);
60         int i = 1;
61         for( Iterator uIt = orderedUnits.iterator(); uIt.hasNext(); ) {
62             final Object JavaDoc u = (Object JavaDoc) uIt.next();
63             numbers.put(u, new Integer JavaDoc(i));
64             i++;
65         }
66
67         TreeSet changedUnits = new TreeSet( new Comparator() {
68             public int compare(Object JavaDoc o1, Object JavaDoc o2) {
69                 Integer JavaDoc i1 = (Integer JavaDoc) numbers.get(o1);
70                 Integer JavaDoc i2 = (Integer JavaDoc) numbers.get(o2);
71                 return -(i1.intValue() - i2.intValue());
72             }
73         } );
74
75
76         // Set initial Flows and nodes to visit.
77 {
78             Iterator it = graph.iterator();
79
80             while(it.hasNext())
81             {
82                 Object JavaDoc s = it.next();
83
84                 changedUnits.add(s);
85
86                 unitToBeforeFlow.put(s, newInitialFlow());
87                 unitToAfterFlow.put(s, newInitialFlow());
88             }
89         }
90
91         List tails = graph.getTails();
92         
93         // Feng Qian: March 07, 2002
94 // init entry points
95 {
96             Iterator it = tails.iterator();
97             
98             while (it.hasNext()) {
99                 Object JavaDoc s = it.next();
100                 // this is a backward flow analysis
101 unitToAfterFlow.put(s, entryInitialFlow());
102             }
103         }
104
105         // Perform fixed point flow analysis
106 {
107             Object JavaDoc previousBeforeFlow = newInitialFlow();
108
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 isTail = tails.contains(s);
117
118                 copy(unitToBeforeFlow.get(s), previousBeforeFlow);
119
120                 // Compute and store afterFlow
121 {
122                     List succs = graph.getSuccsOf(s);
123
124                     afterFlow = unitToAfterFlow.get(s);
125
126                     if(succs.size() == 1)
127                         copy(unitToBeforeFlow.get(succs.get(0)), afterFlow);
128                     else if(succs.size() != 0)
129                     {
130                         Iterator succIt = succs.iterator();
131
132                         copy(unitToBeforeFlow.get(succIt.next()), afterFlow);
133
134                         while(succIt.hasNext())
135                         {
136                             Object JavaDoc otherBranchFlow = unitToBeforeFlow.get(succIt.next());
137                             merge(afterFlow, otherBranchFlow);
138                         }
139
140                         if(isTail && succs.size() != 0)
141                             merge(afterFlow, entryInitialFlow());
142                     }
143                 }
144
145                 // Compute beforeFlow and store it.
146 {
147                     beforeFlow = unitToBeforeFlow.get(s);
148                     if (Options.v().interactive_mode()){
149                         Object JavaDoc savedFlow = newInitialFlow();
150                         if (filterUnitToAfterFlow != null){
151                             savedFlow = filterUnitToAfterFlow.get(s);
152                             copy(filterUnitToAfterFlow.get(s), savedFlow);
153                         }
154                         else {
155                             copy(afterFlow, savedFlow);
156                         }
157                         FlowInfo fi = new FlowInfo(savedFlow, s, false);
158                         if (InteractionHandler.v().getStopUnitList() != null && InteractionHandler.v().getStopUnitList().contains(s)){
159                             InteractionHandler.v().handleStopAtNodeEvent(s);
160                         }
161                         InteractionHandler.v().handleAfterAnalysisEvent(fi);
162                     }
163                     flowThrough(afterFlow, s, beforeFlow);
164                     if (Options.v().interactive_mode()){
165                         Object JavaDoc bSavedFlow = newInitialFlow();
166                         if (filterUnitToBeforeFlow != null){
167                             bSavedFlow = filterUnitToBeforeFlow.get(s);
168                             copy(filterUnitToBeforeFlow.get(s), bSavedFlow);
169                         }
170                         else {
171                             copy(beforeFlow, bSavedFlow);
172                         }
173                         FlowInfo fi = new FlowInfo(bSavedFlow, s, true);
174                         InteractionHandler.v().handleBeforeAnalysisEvent(fi);
175                     }
176                 }
177
178                 // Update queue appropriately
179 if(!beforeFlow.equals(previousBeforeFlow))
180                     {
181                         Iterator predIt = graph.getPredsOf(s).iterator();
182
183                         while(predIt.hasNext())
184                         {
185                             Object JavaDoc pred = predIt.next();
186                             
187                             changedUnits.add(pred);
188                         }
189                     }
190             }
191         }
192     }
193 }
194
195
196
197
Popular Tags