KickJava   Java API By Example, From Geeks To Geeks.

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


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2003 Navindra Umanee <navindra@cs.mcgill.ca>
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 package soot.toolkits.scalar;
21
22 import java.util.*;
23 import soot.*;
24 import soot.options.*;
25 import soot.toolkits.graph.*;
26 import soot.util.*;
27
28 /**
29  * Find all locals guaranteed to be defined at (just before) a given
30  * program point.
31  *
32  * @author Navindra Umanee
33  **/
34 public class GuaranteedDefs
35 {
36     protected Map unitToGuaranteedDefs;
37
38     public GuaranteedDefs(UnitGraph graph)
39     {
40         if(Options.v().verbose())
41             G.v().out.println("[" + graph.getBody().getMethod().getName() +
42                                "] Constructing GuaranteedDefs...");
43
44         GuaranteedDefsAnalysis analysis = new GuaranteedDefsAnalysis(graph);
45
46         // build map
47 {
48             unitToGuaranteedDefs = new HashMap(graph.size() * 2 + 1, 0.7f);
49             Iterator unitIt = graph.iterator();
50
51             while(unitIt.hasNext()){
52                 Unit s = (Unit) unitIt.next();
53                 FlowSet set = (FlowSet) analysis.getFlowBefore(s);
54                 unitToGuaranteedDefs.put
55                     (s, Collections.unmodifiableList(set.toList()));
56             }
57         }
58     }
59
60     /**
61      * Returns a list of locals guaranteed to be defined at (just
62      * before) program point <tt>s</tt>.
63      **/
64     public List getGuaranteedDefs(Unit s)
65     {
66         return (List) unitToGuaranteedDefs.get(s);
67     }
68 }
69
70 /**
71  * Flow analysis to determine all locals guaranteed to be defined at a
72  * given program point.
73  **/
74 class GuaranteedDefsAnalysis extends ForwardFlowAnalysis
75 {
76     FlowSet emptySet = new ArraySparseSet();
77     Map unitToGenerateSet;
78
79     GuaranteedDefsAnalysis(UnitGraph graph)
80     {
81         super(graph);
82         DominatorsFinder df = new MHGDominatorsFinder(graph);
83         unitToGenerateSet = new HashMap(graph.size() * 2 + 1, 0.7f);
84
85         // pre-compute generate sets
86 for(Iterator unitIt = graph.iterator(); unitIt.hasNext();){
87             Unit s = (Unit) unitIt.next();
88             FlowSet genSet = (FlowSet) emptySet.clone();
89             
90             for(Iterator domsIt = df.getDominators(s).iterator(); domsIt.hasNext();){
91                 Unit dom = (Unit) domsIt.next();
92                 for(Iterator boxIt = dom.getDefBoxes().iterator(); boxIt.hasNext();){
93                     ValueBox box = (ValueBox) boxIt.next();
94                     if(box.getValue() instanceof Local)
95                         genSet.add(box.getValue(), genSet);
96                 }
97             }
98             
99             unitToGenerateSet.put(s, genSet);
100         }
101
102         doAnalysis();
103     }
104
105     /**
106      * All INs are initialized to the empty set.
107      **/
108     protected Object JavaDoc newInitialFlow()
109     {
110         return emptySet.clone();
111     }
112
113     /**
114      * IN(Start) is the empty set
115      **/
116     protected Object JavaDoc entryInitialFlow()
117     {
118         return emptySet.clone();
119     }
120
121     /**
122      * OUT is the same as IN plus the genSet.
123      **/
124     protected void flowThrough(Object JavaDoc inValue, Object JavaDoc unit, Object JavaDoc outValue)
125     {
126         FlowSet
127             in = (FlowSet) inValue,
128             out = (FlowSet) outValue;
129
130         // perform generation (kill set is empty)
131 in.union((FlowSet) unitToGenerateSet.get(unit), out);
132     }
133
134     /**
135      * All paths == Intersection.
136      **/
137     protected void merge(Object JavaDoc in1, Object JavaDoc in2, Object JavaDoc out)
138     {
139         FlowSet
140             inSet1 = (FlowSet) in1,
141             inSet2 = (FlowSet) in2,
142             outSet = (FlowSet) out;
143
144         inSet1.intersection(inSet2, outSet);
145     }
146
147     protected void copy(Object JavaDoc source, Object JavaDoc dest)
148     {
149         FlowSet
150             sourceSet = (FlowSet) source,
151             destSet = (FlowSet) dest;
152
153         sourceSet.copy(destSet);
154     }
155 }
156
Popular Tags