1 pnkfelix 1.1.2.1 // LiveVars.java, created Wed May 26 16:53:26 1999 by pnkfelix
2 cananian 1.1.2.29 // Copyright (C) 1999 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.18 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.18 package harpoon.Analysis.DataFlow;
5 pnkfelix 1.1.2.18
6 pnkfelix 1.1.2.18 import harpoon.Analysis.BasicBlock;
7 salcianu 1.3 import harpoon.Analysis.BasicBlockInterf;
8 pnkfelix 1.1.2.18 import harpoon.Analysis.Liveness;
9 pnkfelix 1.1.2.18
10 pnkfelix 1.1.2.18 import harpoon.ClassFile.HCode;
11 pnkfelix 1.1.2.18 import harpoon.ClassFile.HCodeElement;
12 pnkfelix 1.1.2.18
13 pnkfelix 1.1.2.18 import harpoon.IR.Properties.CFGrapher;
14 pnkfelix 1.1.2.18 import harpoon.IR.Properties.UseDefer;
15 pnkfelix 1.1.2.18
16 pnkfelix 1.1.2.18 import harpoon.Util.CloneableIterator;
17 cananian 1.4 import net.cscott.jutil.BitSetFactory;
18 cananian 1.4 import net.cscott.jutil.SetFactory;
19 pnkfelix 1.1.2.18
20 pnkfelix 1.1.2.18 import java.util.Set;
21 pnkfelix 1.1.2.18 import java.util.Map;
22 pnkfelix 1.1.2.18 import java.util.HashSet;
23 pnkfelix 1.1.2.18 import java.util.HashMap;
24 pnkfelix 1.1.2.18 import java.util.Iterator;
25 pnkfelix 1.1.2.18
26 pnkfelix 1.1.2.18 /**
27 pnkfelix 1.1.2.18 * <code>LiveVars</code> performs Liveness Analysis for the variables
28 pnkfelix 1.1.2.18 * in the <code>HCode</code>s passed to it.
29 pnkfelix 1.1.2.18 *
30 pnkfelix 1.1.2.18 * <P> It attempts to do this in efficient manner by <OL>
31 pnkfelix 1.1.2.18 * <LI> grouping the statements into <code>BasicBlock</code>s.
32 pnkfelix 1.1.2.18 * <LI> using bit strings as the underlying representation for the
33 pnkfelix 1.1.2.18 * <code>Set</code>s it works with.
34 pnkfelix 1.1.2.18 * <LI> using the dataflow analysis framework which provides
35 pnkfelix 1.1.2.18 * termination guarantees (as long as the transfer function and
36 pnkfelix 1.1.2.18 * lattice of values provided meet certain conditions).
37 pnkfelix 1.1.2.18 * </OL>
38 pnkfelix 1.1.2.18 *
39 pnkfelix 1.1.2.18 * <P> However, the implementation is also meant to be parameterized
40 pnkfelix 1.1.2.18 * and flexible. So it allows the user to pass in their own
41 pnkfelix 1.1.2.18 * <code>CFGrapher</code> and <code>UseDefer</code> for the code to be
42 pnkfelix 1.1.2.18 * analyzed.
43 pnkfelix 1.1.2.18 *
44 pnkfelix 1.1.2.18 * <P> <B>NOTE:</B> I need to document what constraints there are on
45 pnkfelix 1.1.2.18 * the <code>UseDefer</code> and <code>CFGrapher</code> parameters to
46 pnkfelix 1.1.2.18 * preserve the termination guarantees of the analysis. For the time
47 pnkfelix 1.1.2.18 * being, people who have no experience with Dataflow Analysis code
48 pnkfelix 1.1.2.18 * should avoid passing in strange <code>CFGrapher</code>s and
49 pnkfelix 1.1.2.18 * <code>UseDefer</code>s
50 pnkfelix 1.1.2.18 *
51 cananian 1.1.2.29 * @author Felix S. Klock II <pnkfelix@mit.edu>
52 cananian 1.5 * @version $Id: LiveVars.java,v 1.5 2004/02/08 03:19:21 cananian Exp $ */
53 cananian 1.1.2.23 public class LiveVars extends Liveness {
54 pnkfelix 1.1.2.18
55 pnkfelix 1.1.2.28 protected static final boolean DEBUG = false;
56 pnkfelix 1.1.2.18
57 pnkfelix 1.1.2.18 LiveTemps lv;
58 pnkfelix 1.1.2.18
59 pnkfelix 1.1.2.18 /** Constructs a new <code>LiveVars</code>.
60 pnkfelix 1.1.2.18 Note that since the dataflow analysis is done during
61 pnkfelix 1.1.2.26 construction, this can take a while.
62 pnkfelix 1.1.2.26 Uses the default <code>UseDefer</code> built into
63 pnkfelix 1.1.2.26 <code>hc</code> for its analysis. Requires that elements of
64 pnkfelix 1.1.2.26 <code>hc</code> implement <code>UseDefable</code>.
65 pnkfelix 1.1.2.26 @param hc Code to be analyzed
66 pnkfelix 1.1.2.26 @param gr Represents control-flow information for hc
67 pnkfelix 1.1.2.26 @param liveOnExit Set of Temps that are live on exit from hc
68 pnkfelix 1.1.2.26 */
69 pnkfelix 1.1.2.26 public LiveVars(HCode hc, CFGrapher gr, Set liveOnExit) {
70 pnkfelix 1.1.2.26 this(hc, gr, UseDefer.DEFAULT, liveOnExit);
71 pnkfelix 1.1.2.26 }
72 pnkfelix 1.1.2.26
73 pnkfelix 1.1.2.26 /** Constructs a new <code>LiveVars</code>.
74 pnkfelix 1.1.2.26 Note that since the dataflow analysis is done during
75 pnkfelix 1.1.2.18 construction, this can take a while.
76 pnkfelix 1.1.2.26 @param hc Code to be analyzed
77 pnkfelix 1.1.2.26 @param gr Represents control-flow information for hc
78 pnkfelix 1.1.2.26 @param ud Represents use/def information for elements of hc
79 pnkfelix 1.1.2.26 @param liveOnExit Set of Temps that are live on exit from hc
80 pnkfelix 1.1.2.18 */
81 pnkfelix 1.1.2.18 public LiveVars(HCode hc, CFGrapher gr, UseDefer ud, Set liveOnExit) {
82 pnkfelix 1.1.2.18 super(hc);
83 pnkfelix 1.1.2.20 BasicBlock.Factory bbFact =
84 cananian 1.1.2.24 new BasicBlock.Factory(hc, gr);
85 cananian 1.1.2.24 lv = new LiveTemps(bbFact, liveOnExit, ud);
86 pnkfelix 1.1.2.20 Solver.worklistSolve(bbFact.blockSet().iterator(), lv);
87 pnkfelix 1.1.2.18 }
88 pnkfelix 1.1.2.18
89 pnkfelix 1.1.2.18 public Set getLiveIn(HCodeElement hce) {
90 pnkfelix 1.1.2.18 return lv.getLiveBefore(hce);
91 pnkfelix 1.1.2.18 }
92 pnkfelix 1.1.2.18 public Set getLiveOut(HCodeElement hce) {
93 pnkfelix 1.1.2.18 return lv.getLiveAfter(hce);
94 pnkfelix 1.1.2.18 }
95 pnkfelix 1.1.2.18
96 pnkfelix 1.1.2.18
97 pnkfelix 1.1.2.18 public static abstract class BBVisitor extends BackwardDataFlowBasicBlockVisitor {
98 duncan 1.1.2.15
99 pnkfelix 1.1.2.13 // maps a BasicBlock 'bb' to the LiveVarInfo associated with 'bb'
100 duncan 1.1.2.15 private Map bbToLvi;
101 pnkfelix 1.1.2.13
102 pnkfelix 1.1.2.20 protected BasicBlock.Factory bbFact;
103 pnkfelix 1.1.2.20
104 pnkfelix 1.1.2.22 /** Special ctor for use by subclasses so that the system won't
105 pnkfelix 1.1.2.14 break when calling abstract methods that require data that
106 pnkfelix 1.1.2.14 subclasses haven't initialized yet.
107 pnkfelix 1.1.2.14 */
108 pnkfelix 1.1.2.22 protected BBVisitor(BasicBlock.Factory bbFact, boolean ignore) {
109 pnkfelix 1.1.2.21 this.bbFact = bbFact;
110 duncan 1.1.2.15 }
111 pnkfelix 1.1.2.14
112 pnkfelix 1.1.2.20
113 pnkfelix 1.1.2.13 /** Constructs a new <code>LiveVars</code> for <code>basicblocks</code>.
114 pnkfelix 1.1.2.20 <BR> <B>requires:</B> All of the statements in
115 cananian 1.1.2.25 <code>bbFact</code> implement <code>UseDefable</code>
116 pnkfelix 1.1.2.13 <BR> <B>effects:</B> constructs a new
117 pnkfelix 1.1.2.13 <code>BasicBlockVisitor</code> and initializes its
118 pnkfelix 1.1.2.13 internal datasets for analysis of the
119 pnkfelix 1.1.2.20 <code>BasicBlock</code>s in <code>bbFact</code>.
120 pnkfelix 1.1.2.20 @param bbFact <code>BasicBlock.Factory</code> containing
121 pnkfelix 1.1.2.20 <code>BasicBlock</code>s to be analyzed.
122 duncan 1.1.2.15 */
123 pnkfelix 1.1.2.20 public BBVisitor(BasicBlock.Factory bbFact) {
124 pnkfelix 1.1.2.20 Set universe = findUniverse(bbFact.blockSet());
125 pnkfelix 1.1.2.10 SetFactory setFact = new BitSetFactory(universe);
126 duncan 1.1.2.15
127 pnkfelix 1.1.2.20 initializeBBtoLVI( bbFact.blockSet(), setFact );
128 pnkfelix 1.1.2.11 }
129 pnkfelix 1.1.2.11
130 pnkfelix 1.1.2.12 /** Constructor for <code>LiveVars</code> that allows the user to
131 pnkfelix 1.1.2.12 pass in their own <code>SetFactory</code> for constructing
132 pnkfelix 1.1.2.12 sets of whatever variable types that are used in the analysis.
133 pnkfelix 1.1.2.20 <BR> <B>requires:</B> <OL>
134 pnkfelix 1.1.2.20 <LI> All <code>Temp</code>s in <code>bbFact</code> are
135 pnkfelix 1.1.2.20 members of the universe for
136 pnkfelix 1.1.2.20 <code>tempSetFact</code>.
137 pnkfelix 1.1.2.20 <LI> All of the statements in <code>bbFact</code>
138 cananian 1.1.2.25 implement <code>UseDefable</code>
139 pnkfelix 1.1.2.20 </OL>
140 pnkfelix 1.1.2.20 <BR> <B>effects:</B> constructs a new
141 pnkfelix 1.1.2.20 <code>BasicBlockVisitor</code> and initializes its
142 pnkfelix 1.1.2.20 internal datasets for analysis of the
143 pnkfelix 1.1.2.20 <code>BasicBlock</code>s in <code>bbFact</code>.
144 pnkfelix 1.1.2.11 */
145 pnkfelix 1.1.2.20 public BBVisitor(BasicBlock.Factory bbFact,
146 pnkfelix 1.1.2.20 SetFactory tempSetFact) {
147 pnkfelix 1.1.2.20 initializeBBtoLVI( bbFact.blockSet(), tempSetFact );
148 pnkfelix 1.1.2.11 }
149 pnkfelix 1.1.2.11
150 pnkfelix 1.1.2.20 protected void initializeBBtoLVI(Set blockSet, SetFactory setFact) {
151 pnkfelix 1.1.2.1 bbToLvi = new HashMap();
152 cananian 1.5 for (Object bbO : blockSet) {
153 cananian 1.5 BasicBlock bb = (BasicBlock) bbO;
154 pnkfelix 1.1.2.10 LiveVarInfo lvi = makeUseDef(bb, setFact);
155 pnkfelix 1.1.2.1 bbToLvi.put(bb, lvi);
156 pnkfelix 1.1.2.1 }
157 pnkfelix 1.1.2.8 }
158 pnkfelix 1.1.2.2
159 pnkfelix 1.1.2.12 /** Constructs a <code>Set</code> of all of the referenced
160 pnkfelix 1.1.2.12 variables in <code>blocks</code>.
161 pnkfelix 1.1.2.12 For example, in some analyses this universe will be made up of
162 pnkfelix 1.1.2.12 all of the <code>Temp</code>s referenced in
163 pnkfelix 1.1.2.12 <code>blocks</code>. However, for flexibility I have allowed
164 pnkfelix 1.1.2.12 users to define their own universe of values (such as
165 pnkfelix 1.1.2.12 <code>Web</code>s).
166 pnkfelix 1.1.2.11 */
167 pnkfelix 1.1.2.20 protected abstract Set findUniverse(Set blockSet);
168 pnkfelix 1.1.2.10
169 pnkfelix 1.1.2.5 /** Merge (Confluence) operator.
170 pnkfelix 1.1.2.2 <BR> LVout(bb) = Union over (j elem Succ(bb)) of ( LVin(j) )
171 pnkfelix 1.1.2.5 <BR> <code>parent</code> corresponds to 'bb' above, while
172 pnkfelix 1.1.2.5 <code>child</code> corresponds to a member of Succ('bb'). It
173 pnkfelix 1.1.2.5 is the responsibility of the DataFlow Equation Solver to run
174 pnkfelix 1.1.2.5 <code>merge</code> on all of the Succ('bb')
175 pnkfelix 1.1.2.5 <BR> This method isn't meant to be called by application code;
176 pnkfelix 1.1.2.5 instead, look at one of the DataFlow Equation Solvers in
177 pnkfelix 1.1.2.5 the <code>harpoon.Analysis.DataFlow</code> package.
178 pnkfelix 1.1.2.5 <BR> <B>requires:</B> <code>child</code> and <code>parent</code>
179 pnkfelix 1.1.2.5 are contained in <code>this</code>
180 pnkfelix 1.1.2.5 <BR> <B>effects:</B> Updates the internal information
181 pnkfelix 1.1.2.5 associated with <code>to</code> to
182 pnkfelix 1.1.2.5 include information associated with
183 pnkfelix 1.1.2.5 <code>from</code>
184 pnkfelix 1.1.2.5 @see harpoon.Analysis.DataFlow.InstrSolver
185 pnkfelix 1.1.2.2 */
186 salcianu 1.3 public boolean merge(BasicBlockInterf child, BasicBlockInterf parent) {
187 pnkfelix 1.1.2.5 LiveVarInfo finfo = (LiveVarInfo) bbToLvi.get(child);
188 pnkfelix 1.1.2.5 LiveVarInfo tinfo = (LiveVarInfo) bbToLvi.get(parent);
189 pnkfelix 1.1.2.5 if (DEBUG)
190 pnkfelix 1.1.2.5 System.out.println
191 pnkfelix 1.1.2.5 ("merge( succ: "+child+" pred: "+parent+" ) \n"+
192 pnkfelix 1.1.2.5 "pred.LiveOut: " + tinfo.lvOUT + "\n" +
193 pnkfelix 1.1.2.5 "succ.LiveIn: " + finfo.lvIN + "\n");
194 pnkfelix 1.1.2.28 boolean rtn = tinfo.lvOUT.addAll(finfo.lvIN);
195 pnkfelix 1.1.2.5 return rtn;
196 pnkfelix 1.1.2.1 }
197 pnkfelix 1.1.2.1
198 pnkfelix 1.1.2.2 /** Visit (Transfer) function.
199 pnkfelix 1.1.2.2 <BR> LVin(bb) = ( LVout(bb) - DEF(bb) ) union USE(bb)
200 pnkfelix 1.1.2.1 */
201 pnkfelix 1.1.2.1 public void visit(BasicBlock b) {
202 pnkfelix 1.1.2.1 LiveVarInfo info = (LiveVarInfo) bbToLvi.get(b);
203 pnkfelix 1.1.2.28
204 pnkfelix 1.1.2.28 info.lvIN = new HashSet(); if (DEBUG) System.out.print("visit("+b+")");
205 pnkfelix 1.1.2.28 info.lvIN.addAll(info.lvOUT); if (DEBUG) System.out.print(" add:"+info.lvOUT);
206 pnkfelix 1.1.2.28 info.lvIN.removeAll(info.def); if (DEBUG) System.out.print(" rem:"+info.def);
207 pnkfelix 1.1.2.28 info.lvIN.addAll(info.use); if (DEBUG) System.out.print(" add:"+info.use);
208 pnkfelix 1.1.2.1 }
209 duncan 1.1.2.15
210 pnkfelix 1.1.2.1 /** Initializes the USE/DEF information for bb and stores it in
211 pnkfelix 1.1.2.12 the returned LiveVarInfo. An example implementation would
212 pnkfelix 1.1.2.12 use <code>Temp</code>s to make up their
213 pnkfelix 1.1.2.12 <code>LiveVarInfo</code>s.
214 pnkfelix 1.1.2.1 */
215 pnkfelix 1.1.2.12 protected abstract LiveVarInfo makeUseDef(BasicBlock bb, SetFactory sf);
216 pnkfelix 1.1.2.2
217 pnkfelix 1.1.2.12 /** Returns the <code>Set</code> of variables that are
218 pnkfelix 1.1.2.12 live on entry to <code>b</code>.
219 pnkfelix 1.1.2.2 <BR> <B>requires:</B> A DataFlow Solver has been run to
220 pnkfelix 1.1.2.2 completion on the graph of <code>BasicBlock</code>s
221 pnkfelix 1.1.2.2 containing <code>b</code> with <code>this</code> as the
222 pnkfelix 1.1.2.2 <code>DataFlowBasicBlockVisitor</code>.
223 pnkfelix 1.1.2.2 */
224 pnkfelix 1.1.2.2 public Set getLiveOnEntry(BasicBlock b) {
225 pnkfelix 1.1.2.2 LiveVarInfo lvi = (LiveVarInfo) bbToLvi.get(b);
226 pnkfelix 1.1.2.2 return lvi.lvIN;
227 pnkfelix 1.1.2.3 }
228 pnkfelix 1.1.2.3
229 pnkfelix 1.1.2.12 /** Returns the <code>Set</code> of variables that are
230 pnkfelix 1.1.2.12 live on exit from <code>b</code>.
231 pnkfelix 1.1.2.5 <BR> <B>requires:</B> A DataFlow Equation Solver has been run
232 pnkfelix 1.1.2.12 to completion on the graph of <code>BasicBlock</code>s
233 pnkfelix 1.1.2.3 containing <code>b</code> with <code>this</code> as the
234 pnkfelix 1.1.2.3 <code>DataFlowBasicBlockVisitor</code>.
235 pnkfelix 1.1.2.3 */
236 pnkfelix 1.1.2.3 public Set getLiveOnExit(BasicBlock b) {
237 pnkfelix 1.1.2.3 LiveVarInfo lvi = (LiveVarInfo) bbToLvi.get(b);
238 pnkfelix 1.1.2.3 return lvi.lvOUT;
239 pnkfelix 1.1.2.1 }
240 pnkfelix 1.1.2.1
241 pnkfelix 1.1.2.26 public String dump() { return dump(true); }
242 pnkfelix 1.1.2.26
243 pnkfelix 1.1.2.26 public String dump(boolean dumpInstrs) {
244 pnkfelix 1.1.2.1 StringBuffer s = new StringBuffer();
245 cananian 1.5 for (Object bbO : bbToLvi.keySet()) {
246 cananian 1.5 BasicBlock bb = (BasicBlock) bbO;
247 pnkfelix 1.1.2.1 s.append("BasicBlock " + bb);
248 pnkfelix 1.1.2.28 s.append(" pred:"+bb.prevSet()+" succ:"+bb.nextSet());
249 pnkfelix 1.1.2.1 LiveVarInfo lvi = (LiveVarInfo) bbToLvi.get(bb);
250 pnkfelix 1.1.2.1 s.append("\n" + lvi);
251 pnkfelix 1.1.2.26 if (dumpInstrs)
252 pnkfelix 1.1.2.26 s.append(" -- " + bb + " INSTRS --\n" +
253 pnkfelix 1.1.2.26 bb.dumpElems() +
254 pnkfelix 1.1.2.26 " -- END " + bb + " --\n\n");
255 pnkfelix 1.1.2.1 }
256 pnkfelix 1.1.2.1 return s.toString();
257 pnkfelix 1.1.2.1 }
258 pnkfelix 1.1.2.1
259 pnkfelix 1.1.2.5 // LiveVarInfo is a record type grouping together four sets:
260 pnkfelix 1.1.2.1 // use(bb): set of vars used in 'bb' before being defined in 'bb',
261 pnkfelix 1.1.2.1 // if at all.
262 pnkfelix 1.1.2.1 // def(bb): set of vars defined in 'bb' before being used in 'bb',
263 pnkfelix 1.1.2.1 // if at all.
264 pnkfelix 1.1.2.1 // lvIN(bb): ( lvOUT(bb) - DEF(bb) ) U USE(bb)
265 pnkfelix 1.1.2.1 // lvOUT(bb): Union over (j elem Succ(bb)) of ( lvIN(j) )
266 pnkfelix 1.1.2.12 protected static class LiveVarInfo {
267 pnkfelix 1.1.2.13 public Set use;
268 pnkfelix 1.1.2.13 public Set def;
269 pnkfelix 1.1.2.13 public Set lvIN;
270 pnkfelix 1.1.2.13 public Set lvOUT;
271 pnkfelix 1.1.2.1
272 pnkfelix 1.1.2.17 public LiveVarInfo(SetFactory sf) {
273 pnkfelix 1.1.2.10 use = sf.makeSet();
274 pnkfelix 1.1.2.10 def = sf.makeSet();
275 pnkfelix 1.1.2.10 lvIN = sf.makeSet();
276 pnkfelix 1.1.2.10 lvOUT = sf.makeSet();
277 pnkfelix 1.1.2.1 }
278 pnkfelix 1.1.2.1
279 pnkfelix 1.1.2.1 public String toString() {
280 pnkfelix 1.1.2.1 StringBuffer s = new StringBuffer();
281 pnkfelix 1.1.2.1 Iterator iter;
282 pnkfelix 1.1.2.1 s.append("\tUSE set: " );
283 pnkfelix 1.1.2.1 iter = use.iterator();
284 pnkfelix 1.1.2.1 while(iter.hasNext()) { s.append(iter.next() + " "); }
285 pnkfelix 1.1.2.1 s.append("\n");
286 pnkfelix 1.1.2.1
287 pnkfelix 1.1.2.1 s.append("\tDEF set: " );
288 pnkfelix 1.1.2.1 iter = def.iterator();
289 pnkfelix 1.1.2.1 while(iter.hasNext()) { s.append(iter.next() + " "); }
290 pnkfelix 1.1.2.1 s.append("\n");
291 pnkfelix 1.1.2.1
292 pnkfelix 1.1.2.1 s.append("\tLVin set: " );
293 pnkfelix 1.1.2.1 iter = lvIN.iterator();
294 pnkfelix 1.1.2.1 while(iter.hasNext()) { s.append(iter.next() + " "); }
295 pnkfelix 1.1.2.1 s.append("\n");
296 pnkfelix 1.1.2.1
297 pnkfelix 1.1.2.1 s.append("\tLVout set: " );
298 pnkfelix 1.1.2.1 iter = lvOUT.iterator();
299 pnkfelix 1.1.2.1 while(iter.hasNext()) { s.append(iter.next() + " "); }
300 pnkfelix 1.1.2.1 s.append("\n");
301 pnkfelix 1.1.2.1
302 pnkfelix 1.1.2.1 return s.toString();
303 pnkfelix 1.1.2.1 }
304 pnkfelix 1.1.2.1 }
305 pnkfelix 1.1.2.1 }
306 pnkfelix 1.1.2.1
307 cananian 1.2 }