1 cananian 1.1.2.11 // ReachingDefs.java, created Wed Mar 10 9:00:54 1999 by jwhaley
2 cananian 1.1.2.19 // Copyright (C) 1998 John Whaley <jwhaley@alum.mit.edu>
3 cananian 1.1.2.10 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 jwhaley 1.1.2.1 package harpoon.Analysis.DataFlow;
5 jwhaley 1.1.2.1
6 jwhaley 1.1.2.1
7 pnkfelix 1.1.2.12 import harpoon.Analysis.BasicBlock;
8 salcianu 1.3 import harpoon.Analysis.BasicBlockInterf;
9 pnkfelix 1.1.2.3 import harpoon.ClassFile.HCodeElement;
10 cananian 1.1.2.18 import harpoon.IR.Properties.UseDefable;
11 jwhaley 1.1.2.1 import harpoon.Temp.Temp;
12 duncan 1.1.2.15 import harpoon.Util.CloneableIterator;
13 pnkfelix 1.1.2.13 import harpoon.Util.Util;
14 cananian 1.5 import net.cscott.jutil.BitSetFactory;
15 cananian 1.5 import net.cscott.jutil.SetFactory;
16 pnkfelix 1.1.2.13
17 duncan 1.1.2.15 import java.util.HashMap;
18 duncan 1.1.2.15 import java.util.HashSet;
19 duncan 1.1.2.15 import java.util.Iterator;
20 duncan 1.1.2.15 import java.util.Map;
21 duncan 1.1.2.15 import java.util.Set;
22 pnkfelix 1.1.2.9
23 duncan 1.1.2.15 /**
24 duncan 1.1.2.15 * <code>ReachingDefs</code> is a <code>ForwardDataFlowBasicBlockVisitor</code>
25 duncan 1.1.2.15 * for performing reaching definitions analysis on any IR that implements
26 duncan 1.1.2.15 * <code>HCodeElement</code>, <code>CFGraphable</code>, and
27 cananian 1.1.2.18 * <code>UseDefable</code>.
28 duncan 1.1.2.15 *
29 cananian 1.1.2.19 * @author John Whaley <jwhaley@alum.mit.edu>
30 cananian 1.1.2.19 * @author Felix S. Klock II <pnkfelix@mit.edu>
31 duncan 1.1.2.15 * @author Duncan Bryce <duncan@lcs.mit.edu>
32 cananian 1.6 * @version $Id: ReachingDefs.java,v 1.6 2004/02/08 03:19:21 cananian Exp $
33 duncan 1.1.2.15 */
34 pnkfelix 1.1.2.17 public abstract class ReachingDefs {
35 pnkfelix 1.1.2.17
36 duncan 1.1.2.15 private static final boolean DEBUG = false;
37 pnkfelix 1.1.2.17
38 duncan 1.1.2.15
39 pnkfelix 1.1.2.17
40 pnkfelix 1.1.2.17 abstract static class BBVisitor extends ForwardDataFlowBasicBlockVisitor {
41 pnkfelix 1.1.2.17
42 pnkfelix 1.1.2.17 private Map bbToRdi;
43 pnkfelix 1.1.2.17
44 duncan 1.1.2.15 /**
45 duncan 1.1.2.15 * Constructs a new <code>ReachingDefs</code> for <code>basicblocks</code>.
46 duncan 1.1.2.15 *
47 duncan 1.1.2.15 * <BR><B>requires:</B>
48 duncan 1.1.2.15 * <OL>
49 duncan 1.1.2.15 * <LI> <code>basicBlocks</code> is an <code>Iterator</code> of
50 duncan 1.1.2.15 * <code>BasicBlock</code>s,
51 duncan 1.1.2.15 * <LI> All of the instructions in <code>basicBlocks</code> implement
52 cananian 1.1.2.18 * <code>UseDefable</code>,
53 duncan 1.1.2.15 * <LI> No element of <code>basicblocks</code> links to a
54 duncan 1.1.2.15 * <code>BasicBlock</code> not contained within
55 duncan 1.1.2.15 * <code>basicBlocks</code>,
56 duncan 1.1.2.15 * <LI> No <code>BasicBlock</code> is repeatedly iterated
57 duncan 1.1.2.15 * by <code>basicBlocks</code>
58 duncan 1.1.2.15 * </OL>
59 duncan 1.1.2.15 * <BR> <B>modifies:</B> <code>basicBlocks</code>
60 duncan 1.1.2.15 * <BR> <B>effects:</B> constructs a new <code>BasicBlockVisitor</code>
61 duncan 1.1.2.15 * and initializes internal datasets for analysis of the
62 duncan 1.1.2.15 * <code>BasicBlock</code>s in <code>basicBlocks</code>, iterating over
63 duncan 1.1.2.15 * all of <code>basicBlocks</code> in the process.
64 duncan 1.1.2.15 *
65 duncan 1.1.2.15 * @param basicBlocks <code>Iterator</code> of <code>BasicBlock</code>s
66 duncan 1.1.2.15 * to be analyzed.
67 duncan 1.1.2.15 */
68 pnkfelix 1.1.2.17 public BBVisitor(Iterator basicblocks) {
69 duncan 1.1.2.15 CloneableIterator blocks = new CloneableIterator(basicblocks);
70 duncan 1.1.2.15 Set universe = findUniverse((Iterator) blocks.clone());
71 duncan 1.1.2.15 SetFactory setFact = new BitSetFactory(universe);
72 duncan 1.1.2.15
73 duncan 1.1.2.15 this.initializeGenPrsv( (Iterator)blocks.clone(), setFact );
74 duncan 1.1.2.15 this.initializeBBtoRDI( blocks, setFact );
75 duncan 1.1.2.15 }
76 pnkfelix 1.1.2.6
77 duncan 1.1.2.15 /**
78 duncan 1.1.2.15 * Constructs a new <code>ReachingDefs</code> for
79 duncan 1.1.2.15 * <code>basicblocks</code>. Allows the user to specify their own
80 duncan 1.1.2.15 * <code>SetFactory</code> for constructing sets of definitions in the
81 duncan 1.1.2.15 * analysis.
82 duncan 1.1.2.15 *
83 duncan 1.1.2.15 * <BR><B>requires:</B>
84 duncan 1.1.2.15 * <OL>
85 duncan 1.1.2.15 * <LI> <code>basicBlocks</code> is an <code>Iterator</code> of
86 duncan 1.1.2.15 * <code>BasicBlock</code>s,
87 duncan 1.1.2.15 * <LI> All of the instructions in <code>basicBlocks</code> implement
88 cananian 1.1.2.18 * <code>UseDefable</code>,
89 duncan 1.1.2.15 * <LI> No element of <code>basicblocks</code> links to a
90 duncan 1.1.2.15 * <code>BasicBlock</code> not contained within
91 duncan 1.1.2.15 * <code>basicBlocks</code>,
92 duncan 1.1.2.15 * <LI> No <code>BasicBlock</code> is repeatedly iterated
93 duncan 1.1.2.15 * by <code>basicBlocks</code>
94 duncan 1.1.2.15 * </OL>
95 duncan 1.1.2.15 * <BR> <B>modifies:</B> <code>basicBlocks</code>
96 duncan 1.1.2.15 * <BR> <B>effects:</B> constructs a new <code>BasicBlockVisitor</code>
97 duncan 1.1.2.15 * and initializes internal datasets for analysis of the
98 duncan 1.1.2.15 * <code>BasicBlock</code>s in <code>basicBlocks</code>, iterating over
99 duncan 1.1.2.15 * all of <code>basicBlocks</code> in the process.
100 duncan 1.1.2.15 *
101 duncan 1.1.2.15 * @param basicBlocks <code>Iterator</code> of <code>BasicBlock</code>s
102 duncan 1.1.2.15 * to be analyzed.
103 duncan 1.1.2.15 * @param setFact the <code>SetFactory</code> to be used in
104 duncan 1.1.2.15 * the construction of sets of definitions.
105 duncan 1.1.2.15 */
106 pnkfelix 1.1.2.17 public BBVisitor(Iterator basicblocks, SetFactory setFact) {
107 duncan 1.1.2.15 CloneableIterator blocks = new CloneableIterator(basicblocks);
108 jwhaley 1.1.2.1
109 duncan 1.1.2.15 initializeBBtoRDI( blocks, setFact );
110 pnkfelix 1.1.2.3 }
111 pnkfelix 1.1.2.3
112 duncan 1.1.2.15 /**
113 duncan 1.1.2.15 * Initializes an internal mapping of <code>BasicBlock</code>s to
114 duncan 1.1.2.15 * <code>ReachingDefInfo</code>s.
115 duncan 1.1.2.15 */
116 duncan 1.1.2.15 protected void initializeBBtoRDI(Iterator blocks, SetFactory setFact) {
117 duncan 1.1.2.15 bbToRdi = new HashMap();
118 duncan 1.1.2.15
119 duncan 1.1.2.15 while(blocks.hasNext()) {
120 duncan 1.1.2.15 BasicBlock bb = (BasicBlock) blocks.next();
121 duncan 1.1.2.15 ReachingDefInfo rdi = makeGenPrsv(bb, setFact);
122 duncan 1.1.2.15 bbToRdi.put(bb, rdi);
123 pnkfelix 1.1.2.6 }
124 pnkfelix 1.1.2.6 }
125 duncan 1.1.2.15
126 duncan 1.1.2.15 /**
127 duncan 1.1.2.15 * Merge (Confluence) operator.
128 duncan 1.1.2.15 * <BR> RDin(bb) = Union over (j elem Pred(bb)) of ( RDout(j) )
129 duncan 1.1.2.15 * <code>from</code> corresponds to a member of Pred('bb'). It
130 duncan 1.1.2.15 * is the responsibility of the DataFlow Equation Solver to run
131 duncan 1.1.2.15 * <code>merge</code> on all of the Pred('bb')
132 duncan 1.1.2.15 *
133 duncan 1.1.2.15 * <BR> This method isn't meant to be called by application code;
134 duncan 1.1.2.15 * instead, look at one of the DataFlow Equation Solvers in
135 duncan 1.1.2.15 * the <code>harpoon.Analysis.DataFlow</code> package.
136 duncan 1.1.2.15 * <BR> <B>requires:</B>
137 duncan 1.1.2.15 * <code>child</code> and <code>parent</code> are contained in
138 duncan 1.1.2.15 * <code>this</code>
139 duncan 1.1.2.15 * <BR> <B>effects:</B>
140 duncan 1.1.2.15 * Updates the internal information associated with <code>to</code> to
141 duncan 1.1.2.15 * include information associated with <code>from</code>.
142 duncan 1.1.2.15 */
143 salcianu 1.3 public boolean merge(BasicBlockInterf from, BasicBlockInterf to) {
144 duncan 1.1.2.15 ReachingDefInfo fInfo = (ReachingDefInfo)this.bbToRdi.get(from);
145 duncan 1.1.2.15 ReachingDefInfo tInfo = (ReachingDefInfo)this.bbToRdi.get(to);
146 duncan 1.1.2.15 boolean result = tInfo.rdIN.addAll(fInfo.rdOUT);
147 duncan 1.1.2.15
148 duncan 1.1.2.15 if (DEBUG)
149 duncan 1.1.2.15 System.out.println
150 duncan 1.1.2.15 ("merge( from: " + from +" to: "+ to +" ) \n" +
151 duncan 1.1.2.15 from + ".rdOut: "+ fInfo.rdOUT + "\n" +
152 duncan 1.1.2.15 to + ".rdIN: "+ tInfo.rdIN + "\n");
153 pnkfelix 1.1.2.6
154 pnkfelix 1.1.2.6 return result;
155 pnkfelix 1.1.2.6 }
156 pnkfelix 1.1.2.6
157 duncan 1.1.2.15 /**
158 duncan 1.1.2.15 * Visit (Transfer) function.
159 duncan 1.1.2.15 * <BR> RDout(bb) = ( RDin(bb) intersection PRSV(bb) ) union GEN(bb)
160 duncan 1.1.2.15 */
161 duncan 1.1.2.15 public void visit(BasicBlock b) {
162 duncan 1.1.2.15 ReachingDefInfo info = (ReachingDefInfo)bbToRdi.get(b);
163 duncan 1.1.2.15 info.rdOUT.clear();
164 duncan 1.1.2.15 info.rdOUT.addAll(info.rdIN);
165 duncan 1.1.2.15 info.rdOUT.retainAll(info.prsv);
166 duncan 1.1.2.15 info.rdOUT.addAll(info.gen);
167 duncan 1.1.2.15
168 duncan 1.1.2.15 if (DEBUG)
169 duncan 1.1.2.15 System.out.println
170 duncan 1.1.2.15 ("visit( " + b + "):\n " +
171 duncan 1.1.2.15 b + ".LiveOut: " + info.rdOUT + "\n" +
172 duncan 1.1.2.15 b + ".LiveIn: " + info.rdIN + "\n");
173 jwhaley 1.1.2.1
174 pnkfelix 1.1.2.6 }
175 duncan 1.1.2.15
176 duncan 1.1.2.15 /**
177 duncan 1.1.2.15 * Constructs a <code>Set</code> of all of the referenced definitions in
178 duncan 1.1.2.15 * <code>blocks</code>.
179 duncan 1.1.2.15 *
180 duncan 1.1.2.15 * For example, in some analyses this universe will be made up of
181 duncan 1.1.2.15 * all of the <code>HCodeElement</code>s referenced in
182 duncan 1.1.2.15 * <code>blocks</code>. However, for flexibility I have allowed
183 duncan 1.1.2.15 * users to define their own universe of values.
184 duncan 1.1.2.15 */
185 duncan 1.1.2.15 protected abstract Set findUniverse(Iterator blocks);
186 duncan 1.1.2.15
187 duncan 1.1.2.15 /**
188 duncan 1.1.2.15 * Performs initialization necessary to calculate GEN/PRSV sets.
189 duncan 1.1.2.15 *
190 duncan 1.1.2.15 * For example, this might consist of constructing a mapping of
191 duncan 1.1.2.15 * <code>Temp</code>s to <code>HCodeElement</code>s which do not define
192 duncan 1.1.2.15 * them.
193 duncan 1.1.2.15 */
194 duncan 1.1.2.15 protected abstract void initializeGenPrsv(Iterator blocks, SetFactory sf);
195 pnkfelix 1.1.2.6
196 duncan 1.1.2.15 /**
197 duncan 1.1.2.15 * Initializes the GEN/PRSV information for bb and stores it in
198 duncan 1.1.2.15 * the returned <code>ReachingDefInfo</code>. An example implementation
199 duncan 1.1.2.15 * would use <code>HCodeElement</code>s to make up their
200 duncan 1.1.2.15 * <code>ReachingDefInfo</code>s.
201 duncan 1.1.2.15 */
202 duncan 1.1.2.15 protected abstract ReachingDefInfo makeGenPrsv(BasicBlock bb, SetFactory sf);
203 duncan 1.1.2.15
204 duncan 1.1.2.15 /**
205 duncan 1.1.2.15 * Returns the <code>Set</code> of definitions that reach the exit of
206 duncan 1.1.2.15 * <code>b</code>.
207 duncan 1.1.2.15 *
208 duncan 1.1.2.15 * <BR> <B>requires:</B> A DataFlow Equation Solver has been run to
209 duncan 1.1.2.15 * completion on the graph of <code>BasicBlock</code>s containing
210 duncan 1.1.2.15 * <code>b</code> with <code>this</code> as the
211 duncan 1.1.2.15 * <code>DataFlowBasicBlockVisitor</code>.
212 duncan 1.1.2.15 */
213 duncan 1.1.2.15 public Set getReachingOnEntry(BasicBlock b) {
214 duncan 1.1.2.15 ReachingDefInfo rdi = (ReachingDefInfo) bbToRdi.get(b);
215 duncan 1.1.2.15 return rdi.rdIN;
216 pnkfelix 1.1.2.6 }
217 duncan 1.1.2.15
218 duncan 1.1.2.15 /**
219 duncan 1.1.2.15 * Returns the <code>Set</code> of definitions that reach the exit of
220 duncan 1.1.2.15 * <code>b</code>.
221 duncan 1.1.2.15 *
222 duncan 1.1.2.15 * <BR> <B>requires:</B> A DataFlow Equation Solver has been run to
223 duncan 1.1.2.15 * completion on the graph of <code>BasicBlock</code>s containing
224 duncan 1.1.2.15 * <code>b</code> with <code>this</code> as the
225 duncan 1.1.2.15 * <code>DataFlowBasicBlockVisitor</code>.
226 duncan 1.1.2.15 */
227 duncan 1.1.2.15 public Set getReachingOnExit(BasicBlock b) {
228 duncan 1.1.2.15 ReachingDefInfo rdi = (ReachingDefInfo) bbToRdi.get(b);
229 duncan 1.1.2.15 return rdi.rdOUT;
230 duncan 1.1.2.15 }
231 duncan 1.1.2.15
232 pnkfelix 1.1.2.6 public String dump() {
233 pnkfelix 1.1.2.6 StringBuffer s = new StringBuffer();
234 cananian 1.6 for (Object bbO : this.bbToRdi.keySet()) {
235 cananian 1.6 BasicBlock bb = (BasicBlock) bbO;
236 pnkfelix 1.1.2.6 s.append("Basic block "+bb);
237 duncan 1.1.2.15 ReachingDefInfo rdi = (ReachingDefInfo)this.bbToRdi.get(bb);
238 pnkfelix 1.1.2.6 s.append("\n"+rdi);
239 pnkfelix 1.1.2.6 }
240 pnkfelix 1.1.2.6 return s.toString();
241 pnkfelix 1.1.2.6 }
242 duncan 1.1.2.15
243 duncan 1.1.2.15 // ReachingDefInfo is a record type grouping together four sets:
244 duncan 1.1.2.15 // gen(bb): set of definitions in 'bb' which are not subsequently killed
245 duncan 1.1.2.15 // in 'bb'.
246 duncan 1.1.2.15 // prsv(bb): set of definitions in 'bb' which are not killed in 'bb'.
247 duncan 1.1.2.15 // rdIN(bb): Union over (j elem Pred(bb)) of ( rdOUT(j) )
248 duncan 1.1.2.15 // rdOUT(bb): ( rdIN(bb) intersection prsv(bb) ) union ( gen(bb) )
249 duncan 1.1.2.15 //
250 duncan 1.1.2.15 protected static class ReachingDefInfo {
251 duncan 1.1.2.15 public Set gen;
252 duncan 1.1.2.15 public Set prsv;
253 duncan 1.1.2.15 public Set rdIN;
254 duncan 1.1.2.15 public Set rdOUT;
255 duncan 1.1.2.15
256 duncan 1.1.2.15 ReachingDefInfo(SetFactory sf) {
257 duncan 1.1.2.15 gen = sf.makeSet();
258 duncan 1.1.2.15 prsv = sf.makeSet();
259 duncan 1.1.2.15 rdIN = sf.makeSet();
260 duncan 1.1.2.15 rdOUT = sf.makeSet();
261 duncan 1.1.2.15 }
262 duncan 1.1.2.15
263 duncan 1.1.2.15 public String toString() {
264 duncan 1.1.2.15 StringBuffer s = new StringBuffer();
265 duncan 1.1.2.15 Iterator iter;
266 duncan 1.1.2.15 s.append("\tGEN set: " );
267 duncan 1.1.2.15 iter = gen.iterator();
268 duncan 1.1.2.15 while(iter.hasNext()) { s.append(iter.next() + " "); }
269 duncan 1.1.2.15 s.append("\n");
270 duncan 1.1.2.15
271 duncan 1.1.2.15 s.append("\tPRSV set: " );
272 duncan 1.1.2.15 iter = prsv.iterator();
273 duncan 1.1.2.15 while(iter.hasNext()) { s.append(iter.next() + " "); }
274 duncan 1.1.2.15 s.append("\n");
275 duncan 1.1.2.15
276 duncan 1.1.2.15 s.append("\tRDin set: " );
277 duncan 1.1.2.15 iter = rdIN.iterator();
278 duncan 1.1.2.15 while(iter.hasNext()) { s.append(iter.next() + " "); }
279 duncan 1.1.2.15 s.append("\n");
280 duncan 1.1.2.15
281 duncan 1.1.2.15 s.append("\tRDout set: " );
282 duncan 1.1.2.15 iter = rdOUT.iterator();
283 duncan 1.1.2.15 while(iter.hasNext()) { s.append(iter.next() + " "); }
284 duncan 1.1.2.15 s.append("\n");
285 duncan 1.1.2.15
286 duncan 1.1.2.15 return s.toString();
287 duncan 1.1.2.15 }
288 pnkfelix 1.1.2.17 }
289 duncan 1.1.2.15 }
290 jwhaley 1.1.2.1 }
291 cananian 1.2