1 cananian 1.1.2.4 // ReachingHCodeElements.java, created Fri Dec 3 1:47:33 1999 by duncan
2 cananian 1.1.2.4 // Copyright (C) 1998 Felix S. Klock II <pnkfelix@mit.edu>
3 cananian 1.1.2.4 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 duncan 1.1.2.1 package harpoon.Analysis.DataFlow;
5 duncan 1.1.2.1
6 duncan 1.1.2.1 import harpoon.Analysis.BasicBlock;
7 salcianu 1.3 import harpoon.Analysis.BasicBlockInterf;
8 duncan 1.1.2.1 import harpoon.ClassFile.HCodeElement;
9 duncan 1.1.2.1 import harpoon.IR.Properties.CFGraphable;
10 cananian 1.1.2.9 import harpoon.IR.Properties.UseDefable;
11 duncan 1.1.2.1 import harpoon.Temp.Temp;
12 duncan 1.1.2.1 import harpoon.Util.Util;
13 cananian 1.4 import net.cscott.jutil.SetFactory;
14 duncan 1.1.2.1
15 duncan 1.1.2.1 import java.util.HashMap;
16 duncan 1.1.2.1 import java.util.HashSet;
17 duncan 1.1.2.1 import java.util.Iterator;
18 duncan 1.1.2.1 import java.util.Map;
19 duncan 1.1.2.1 import java.util.Set;
20 duncan 1.1.2.1
21 duncan 1.1.2.1 /**
22 duncan 1.1.2.1 * <code>ReachingHCodeElements</code> is an extension of
23 duncan 1.1.2.1 * <code>ReachingDefs</code> for performing reaching definitions analysis on
24 duncan 1.1.2.1 * <code>HCodeElements</code>s.
25 duncan 1.1.2.1 *
26 duncan 1.1.2.1 * @author Felix S. Klock II <pnkfelix@mit.edu>
27 cananian 1.1.2.10 * @author Duncan Bryce <duncan@lcs.mit.edu>
28 cananian 1.5 * @version $Id: ReachingHCodeElements.java,v 1.5 2004/02/08 03:19:21 cananian Exp $
29 duncan 1.1.2.1 */
30 pnkfelix 1.1.2.7 public class ReachingHCodeElements extends ReachingDefs.BBVisitor {
31 cananian 1.1.2.8 private BasicBlock.Factory bbfactory;
32 duncan 1.1.2.1 private Map tempsToPrsvs;
33 duncan 1.1.2.1 private Set universe;
34 duncan 1.1.2.3 private Map rdCache = new HashMap();
35 duncan 1.1.2.3
36 duncan 1.1.2.1
37 duncan 1.1.2.1 /**
38 duncan 1.1.2.1 * Constructs a new <code>ReachingHCodeElements</code> for
39 cananian 1.1.2.8 * the basic blocks in the supplied <code>BasicBlock.Factory</code>.
40 duncan 1.1.2.1 *
41 duncan 1.1.2.1 * <BR><B>requires:</B>
42 duncan 1.1.2.1 * <OL>
43 cananian 1.1.2.8 * <LI> <code>bbfactory</code> is a valid
44 cananian 1.1.2.8 * <code>BasicBlock.Factory</code>.
45 duncan 1.1.2.1 * <LI> All of the instructions in <code>basicBlocks</code> implement
46 cananian 1.1.2.9 * <code>UseDefable</code>,
47 duncan 1.1.2.1 * </OL>
48 duncan 1.1.2.1 * <BR> <B>effects:</B> constructs a new <code>BasicBlockVisitor</code>
49 duncan 1.1.2.1 * and initializes internal datasets for analysis of the
50 cananian 1.1.2.8 * <code>BasicBlock</code>s in <code>bbfactory</code>.
51 duncan 1.1.2.1 *
52 cananian 1.1.2.8 * @param bbfactory <code>BasicBlock.Factory</code> of
53 cananian 1.1.2.8 * <code>BasicBlock</code>s to be analyzed.
54 duncan 1.1.2.1 */
55 cananian 1.1.2.8 public ReachingHCodeElements(BasicBlock.Factory bbfactory) {
56 cananian 1.1.2.8 super(bbfactory.blocksIterator());
57 cananian 1.1.2.8 this.bbfactory = bbfactory;
58 duncan 1.1.2.1 }
59 duncan 1.1.2.1
60 duncan 1.1.2.1 /**
61 duncan 1.1.2.1 * Constructs a new <code>ReachingHCodeElements</code> for
62 cananian 1.1.2.8 * the basic blocks in the supplied <code>BasicBlock.Factory</code>.
63 cananian 1.1.2.8 * Allows the user to specify their own <code>SetFactory</code> for
64 cananian 1.1.2.8 * constructing sets of <code>HCodeElements</code> in the analysis.
65 duncan 1.1.2.1 *
66 duncan 1.1.2.1 * <BR><B>requires:</B>
67 duncan 1.1.2.1 * <OL>
68 cananian 1.1.2.8 * <LI> <code>bbfactory</code> is a valid
69 cananian 1.1.2.8 * <code>BasicBlock.Factory</code>.
70 duncan 1.1.2.1 * <LI> All of the instructions in <code>basicBlocks</code> implement
71 cananian 1.1.2.9 * <code>UseDefable</code>,
72 duncan 1.1.2.1 * <LI> All of the <code>HCodeElements</code> in <code>basicBlocks</code>
73 duncan 1.1.2.1 * which have non-empty def sets are members of the universe of
74 duncan 1.1.2.1 * <code>setFact</code>.
75 duncan 1.1.2.1 * </OL>
76 duncan 1.1.2.1 * <BR> <B>effects:</B> constructs a new <code>BasicBlockVisitor</code>
77 duncan 1.1.2.1 * and initializes internal datasets for analysis of the
78 cananian 1.1.2.8 * <code>BasicBlock</code>s in <code>bbfactory</code>.
79 duncan 1.1.2.1 *
80 cananian 1.1.2.8 * @param bbfactory <code>BasicBlock.Factory</code> of
81 cananian 1.1.2.8 * <code>BasicBlock</code>s to be analyzed.
82 duncan 1.1.2.1 * @param setFact the <code>SetFactory</code> to be used in
83 duncan 1.1.2.1 * the construction of sets of
84 duncan 1.1.2.1 * <code>HCodeElements</code>.
85 duncan 1.1.2.1 */
86 cananian 1.1.2.8 public ReachingHCodeElements(BasicBlock.Factory bbfactory,
87 cananian 1.1.2.8 SetFactory setFact) {
88 cananian 1.1.2.8 super(bbfactory.blocksIterator(), setFact);
89 cananian 1.1.2.8 this.bbfactory = bbfactory;
90 duncan 1.1.2.1 }
91 duncan 1.1.2.1
92 duncan 1.1.2.1
93 duncan 1.1.2.1 /**
94 duncan 1.1.2.1 * Constructs a <code>Set</code> of all of the <code>HCodeElement</code>s
95 duncan 1.1.2.1 * in <code>blocks</code> which have non-empty def sets.
96 duncan 1.1.2.1 *
97 duncan 1.1.2.1 * <BR><B>requires:</B>
98 duncan 1.1.2.1 * <OL>
99 duncan 1.1.2.1 * <LI> <code>blocks</code> is an <code>Iterator</code> of
100 duncan 1.1.2.1 * <code>BasicBlock</code>s.
101 duncan 1.1.2.1 * <LI> All of the instructions in each element of <code>blocks</code>
102 cananian 1.1.2.9 * implement <code>UseDefable</code>.
103 duncan 1.1.2.1 * </OL>
104 duncan 1.1.2.1 * <BR> <B>modifies:</B> <code>blocks</code>
105 duncan 1.1.2.1 * <BR> <B>effects:</B>
106 duncan 1.1.2.1 * Iterates through all of the instructions contained in each element
107 duncan 1.1.2.1 * of <code>blocks</code>, adding each instruction which has a non-empty
108 duncan 1.1.2.1 * def set to a universe of values, returning the universe after all of
109 duncan 1.1.2.1 * the instructions have been visited. Internally maintains a reference
110 duncan 1.1.2.1 * to this computed dataset.
111 duncan 1.1.2.1 */
112 duncan 1.1.2.1 protected Set findUniverse(Iterator blocks) {
113 duncan 1.1.2.1 this.universe = new HashSet();
114 duncan 1.1.2.1
115 duncan 1.1.2.1 for (; blocks.hasNext(); ) {
116 duncan 1.1.2.1 BasicBlock bb = (BasicBlock) blocks.next();
117 cananian 1.5 for (Object udNextO : bb.statements()) {
118 cananian 1.5 UseDefable udNext = (UseDefable) udNextO;
119 duncan 1.1.2.1 if (udNext.def().length > 0) {
120 duncan 1.1.2.1 this.universe.add(udNext);
121 duncan 1.1.2.1 }
122 duncan 1.1.2.1 }
123 duncan 1.1.2.1 }
124 duncan 1.1.2.1 return this.universe;
125 duncan 1.1.2.1 }
126 duncan 1.1.2.1
127 duncan 1.1.2.1 /**
128 duncan 1.1.2.1 * Initializes a mapping of temps to the Set of <code>HCodeElement</code>s
129 duncan 1.1.2.1 * which do not define them.
130 duncan 1.1.2.1 *
131 duncan 1.1.2.1 * <BR><B>Requires:</B>
132 duncan 1.1.2.1 * <OL>
133 duncan 1.1.2.1 * <LI> <code>blocks</code> is an <code>Iterator</code> of
134 duncan 1.1.2.1 * <code>BasicBlock</code>s.
135 duncan 1.1.2.1 * <LI> All of the instructions in each element of <code>blocks</code>
136 cananian 1.1.2.9 * implement <code>UseDefable</code>.
137 duncan 1.1.2.1 * <LI> All of the <code>HCodeElements</code> in <code>basicBlocks</code>
138 duncan 1.1.2.1 * which have non-empty def sets are members of the universe of
139 duncan 1.1.2.1 * <code>setFact</code>.
140 duncan 1.1.2.1 */
141 duncan 1.1.2.1 protected void initializeGenPrsv(Iterator blocks, SetFactory sf) {
142 duncan 1.1.2.3 this.tempsToPrsvs = new HashMap();
143 duncan 1.1.2.1
144 duncan 1.1.2.2 // Update the universe to use a compatible set factory.
145 duncan 1.1.2.2 // This is usually much more efficient.
146 duncan 1.1.2.2 this.universe = sf.makeSet(this.universe);
147 duncan 1.1.2.2
148 duncan 1.1.2.1 while (blocks.hasNext()) {
149 duncan 1.1.2.1 BasicBlock bb = (BasicBlock)blocks.next();
150 cananian 1.5 for (Object udNextO : bb.statements()) {
151 cananian 1.5 UseDefable udNext = (UseDefable) udNextO;
152 duncan 1.1.2.1 Temp[] defs = udNext.def();
153 duncan 1.1.2.1 for (int i=0, n=defs.length; i<n; ++i) {
154 duncan 1.1.2.1 Temp t = defs[i];
155 duncan 1.1.2.1 Set prsv = (Set)tempsToPrsvs.get(t);
156 duncan 1.1.2.1 if (prsv == null) {
157 duncan 1.1.2.3 tempsToPrsvs.put(t, prsv = sf.makeSet(this.universe));
158 duncan 1.1.2.1 }
159 duncan 1.1.2.1 prsv.remove(udNext);
160 duncan 1.1.2.1 }
161 duncan 1.1.2.1 }
162 duncan 1.1.2.1 }
163 duncan 1.1.2.1 }
164 duncan 1.1.2.1
165 duncan 1.1.2.1 /**
166 duncan 1.1.2.1 * Initializes the GEN/PRSV information for 'bb' and stores in in
167 duncan 1.1.2.1 * the returned <code>ReachingDefInfo</code>.
168 duncan 1.1.2.1 *
169 duncan 1.1.2.1 * <BR><B>Requires:</B>
170 duncan 1.1.2.1 * <code>initializeGenPrsv</code> has already been called on this
171 duncan 1.1.2.1 * <code>ReachingHCodeElements</code> object, and <code>bb</code> was
172 duncan 1.1.2.1 * one of the blocks in the <code>Iterator</code> parameter to the last
173 duncan 1.1.2.1 * such invocation.
174 duncan 1.1.2.1 */
175 duncan 1.1.2.1 protected ReachingDefInfo makeGenPrsv(BasicBlock bb, SetFactory sf) {
176 duncan 1.1.2.1 ReachingDefInfo info = new ReachingDefInfo(sf);
177 duncan 1.1.2.1
178 duncan 1.1.2.1 info.prsv.addAll(this.universe);
179 duncan 1.1.2.1
180 cananian 1.5 for (Object udNextO : bb.statements()) {
181 cananian 1.5 UseDefable udNext = (UseDefable) udNextO;
182 duncan 1.1.2.1 Temp[] defs = udNext.def();
183 duncan 1.1.2.1 for (int i=0, n=defs.length; i<n; ++i) {
184 duncan 1.1.2.1 Temp t = defs[i];
185 duncan 1.1.2.1 Set prsv = (Set)tempsToPrsvs.get(t);
186 duncan 1.1.2.1 info.prsv.retainAll(prsv);
187 duncan 1.1.2.1 info.gen.retainAll(prsv);
188 duncan 1.1.2.1 info.gen.add(udNext);
189 duncan 1.1.2.1 }
190 duncan 1.1.2.1 }
191 duncan 1.1.2.1 return info;
192 duncan 1.1.2.1 }
193 duncan 1.1.2.1
194 duncan 1.1.2.1 /**
195 duncan 1.1.2.1 * Returns the <code>Set</code> of <code>HCodeElements</code>s
196 duncan 1.1.2.1 * which represent a definition that reaches the point directly before
197 duncan 1.1.2.1 * <code>hce</code>. If <code>hce</code> represents more than one
198 duncan 1.1.2.1 * definition, all definitions which it represents must reach this point.
199 duncan 1.1.2.1 * Because of this, the <code>ReachingHCodeElements</code> class is
200 duncan 1.1.2.1 * most useful for intermediate representations in which each
201 duncan 1.1.2.1 * <code>HCodeElement</code> can represent only 1 definition.
202 duncan 1.1.2.1 *
203 duncan 1.1.2.1 * <BR><B>requires:</B>
204 duncan 1.1.2.1 * A DataFlow Equation Solver has been run to completion on the graph
205 duncan 1.1.2.1 * of <code>BasicBlock</code>s containing some block that contains
206 duncan 1.1.2.1 * <code>hce</code>, with <code>this</code> as the
207 duncan 1.1.2.1 * <code>DataFlowBasicBlockVisitor</code>.
208 duncan 1.1.2.1 *
209 duncan 1.1.2.1 * <BR> <B>effects:</B>
210 duncan 1.1.2.1 * Returns a <code>Set</code> of <code>Temp</code>s that are live on
211 duncan 1.1.2.1 * entry to <code>hce</code>.
212 duncan 1.1.2.1 */
213 duncan 1.1.2.1 public Set getReachingBefore(HCodeElement hce) {
214 duncan 1.1.2.3
215 duncan 1.1.2.3 if (!this.rdCache.containsKey(hce)) {
216 cananian 1.1.2.8 BasicBlock bb = bbfactory.getBlock(hce);
217 duncan 1.1.2.3 Set reachBefore = new HashSet();
218 duncan 1.1.2.3
219 duncan 1.1.2.3 reachBefore.addAll(this.getReachingOnEntry(bb));
220 duncan 1.1.2.3
221 duncan 1.1.2.3 // Starting from the first element in hce's basic block, traverse
222 duncan 1.1.2.3 // the block until hce is reached. Each step updates the
223 duncan 1.1.2.3 // reaching def information.
224 cananian 1.5 for (Object udCurrentO : bb.statements()) {
225 cananian 1.5 UseDefable udCurrent = (UseDefable) udCurrentO;
226 duncan 1.1.2.3 this.rdCache.put(udCurrent, reachBefore);
227 duncan 1.1.2.3 Temp[] defs = udCurrent.def();
228 duncan 1.1.2.3 for (int n=0; n<defs.length; n++) {
229 duncan 1.1.2.3 reachBefore.retainAll
230 duncan 1.1.2.3 ((Set)this.tempsToPrsvs.get(defs[n]));
231 duncan 1.1.2.3 reachBefore.add((HCodeElement)udCurrent);
232 duncan 1.1.2.3 }
233 duncan 1.1.2.1 }
234 duncan 1.1.2.1 }
235 duncan 1.1.2.1
236 duncan 1.1.2.3 return (Set)this.rdCache.get(hce);
237 duncan 1.1.2.1 }
238 duncan 1.1.2.1
239 duncan 1.1.2.1 /**
240 duncan 1.1.2.1 * Returns the <code>Set</code> of <code>HCodeElements</code>s
241 duncan 1.1.2.1 * which represent a definition that reaches the point directly after
242 duncan 1.1.2.1 * <code>hce</code>. If <code>hce</code> represents more than one
243 duncan 1.1.2.1 * definition, all definitions which it represents must reach this point.
244 duncan 1.1.2.1 * Because of this, the <code>ReachingHCodeElements</code> class is
245 duncan 1.1.2.1 * most useful for intermediate representations in which each
246 duncan 1.1.2.1 * <code>HCodeElement</code> can represent only 1 definition.
247 duncan 1.1.2.1 *
248 duncan 1.1.2.1 * <BR><B>requires:</B>
249 duncan 1.1.2.1 * A DataFlow Equation Solver has been run to completion on the graph
250 duncan 1.1.2.1 * of <code>BasicBlock</code>s containing some block that contains
251 duncan 1.1.2.1 * <code>hce</code>, with <code>this</code> as the
252 duncan 1.1.2.1 * <code>DataFlowBasicBlockVisitor</code>.
253 duncan 1.1.2.1 *
254 duncan 1.1.2.1 * <BR> <B>effects:</B>
255 duncan 1.1.2.1 * Returns a <code>Set</code> of <code>Temp</code>s that are live on
256 duncan 1.1.2.1 * entry to <code>hce</code>.
257 duncan 1.1.2.1 */
258 duncan 1.1.2.1 public Set getReachingAfter(HCodeElement hce) {
259 duncan 1.1.2.1 Set reachAfter = this.getReachingBefore(hce);
260 duncan 1.1.2.2
261 cananian 1.1.2.9 Temp[] defs = ((UseDefable)hce).def();
262 duncan 1.1.2.1 for (int i=0; i<defs.length; i++) {
263 duncan 1.1.2.1 reachAfter.retainAll((Set)this.tempsToPrsvs.get(defs[i]));
264 duncan 1.1.2.1 }
265 duncan 1.1.2.1 reachAfter.add(hce);
266 duncan 1.1.2.1
267 duncan 1.1.2.1 return reachAfter;
268 duncan 1.1.2.1 }
269 duncan 1.1.2.1 }
270 duncan 1.1.2.1
271 cananian 1.2