1 kkz 1.1.2.1 // ReachingDefsImpl.java, created Wed Feb 9 16:35:43 2000 by kkz
2 cananian 1.1.2.17 // Copyright (C) 2000 Karen K. Zee <kkz@alum.mit.edu>
3 kkz 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 kkz 1.1.2.1 package harpoon.Analysis;
5 kkz 1.1.2.1
6 kkz 1.1.2.1 import harpoon.ClassFile.HCode;
7 kkz 1.1.2.1 import harpoon.ClassFile.HCodeElement;
8 kkz 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
9 kkz 1.1.2.1 import harpoon.Temp.Temp;
10 cananian 1.5 import net.cscott.jutil.BitSetFactory;
11 cananian 1.1.2.5 import harpoon.Util.Util;
12 kkz 1.1.2.1 import harpoon.Util.Worklist;
13 cananian 1.1.2.19 import harpoon.Util.Collections.WorkSet;
14 pnkfelix 1.1.2.9 import harpoon.IR.Properties.UseDefer;
15 salcianu 1.1.2.7 import harpoon.IR.Quads.TYPECAST;
16 cananian 1.5 import net.cscott.jutil.Default;
17 kkz 1.1.2.1
18 cananian 1.5 import java.util.ArrayList;
19 kkz 1.1.2.1 import java.util.Collections;
20 salcianu 1.1.2.7 import java.util.Collection;
21 kkz 1.1.2.1 import java.util.HashMap;
22 kkz 1.1.2.1 import java.util.HashSet;
23 kkz 1.1.2.1 import java.util.Iterator;
24 cananian 1.5 import java.util.List;
25 kkz 1.1.2.1 import java.util.Map;
26 kkz 1.1.2.1 import java.util.Set;
27 kkz 1.1.2.1 /**
28 kkz 1.1.2.1 * <code>ReachingDefsImpl</code> defines an implementation
29 kkz 1.1.2.1 * for analyzing reaching definitions. Since results are
30 kkz 1.1.2.1 * cached, a new <code>ReachingDefsImpl</code> should be
31 kkz 1.1.2.1 * created if the code has been modified.
32 kkz 1.1.2.1 *
33 cananian 1.1.2.17 * @author Karen K. Zee <kkz@alum.mit.edu>
34 cananian 1.6 * @version $Id: ReachingDefsImpl.java,v 1.6 2004/02/08 03:19:12 cananian Exp $
35 kkz 1.1.2.1 */
36 cananian 1.3.2.2 public class ReachingDefsImpl<HCE extends HCodeElement> extends ReachingDefs<HCE> {
37 cananian 1.3.2.2 final private CFGrapher<HCE> cfger;
38 cananian 1.3.2.2 final protected BasicBlock.Factory<HCE> bbf;
39 cananian 1.3.2.2 final protected Map<Temp,BitSetFactory<HCE>> Temp_to_BitSetFactories =
40 cananian 1.3.2.2 new HashMap<Temp,BitSetFactory<HCE>>();
41 cananian 1.5 final protected Map<BasicBlock<HCE>,Map<Temp,List<Set<HCE>>>> cache =
42 cananian 1.5 new HashMap<BasicBlock<HCE>,Map<Temp,List<Set<HCE>>>>(); // maps BasicBlocks to in/out Sets
43 pnkfelix 1.1.2.11 final protected boolean check_typecast; // demand the special treatment of TYPECAST
44 cananian 1.3.2.2 final protected UseDefer<HCE> ud;
45 kkz 1.1.2.1 /** Creates a <code>ReachingDefsImpl</code> object for the
46 pnkfelix 1.1.2.9 provided <code>HCode</code> for an IR implementing
47 cananian 1.1.2.15 <code>UseDefable</code> using the provided <code>CFGrapher</code>.
48 pnkfelix 1.1.2.9 This may take a while since the analysis is done at this time.
49 kkz 1.1.2.1 */
50 cananian 1.3.2.2 public ReachingDefsImpl(HCode<HCE> hc, CFGrapher<HCE> cfger) {
51 cananian 1.5 this(hc, cfger, (UseDefer<HCE>) UseDefer.DEFAULT);
52 pnkfelix 1.1.2.9 }
53 pnkfelix 1.1.2.9 /** Creates a <code>ReachingDefsImpl</code> object for the
54 pnkfelix 1.1.2.9 provided <code>HCode</code> using the provided
55 pnkfelix 1.1.2.9 <code>CFGrapher</code> and <code>UseDefer</code>. This may
56 pnkfelix 1.1.2.9 take a while since the analysis is done at this time.
57 pnkfelix 1.1.2.9 */
58 cananian 1.3.2.2 public ReachingDefsImpl(HCode<HCE> hc, CFGrapher<HCE> cfger, UseDefer<HCE> ud) {
59 kkz 1.1.2.1 super(hc);
60 kkz 1.1.2.1 this.cfger = cfger;
61 cananian 1.3.2.2 this.bbf = new BasicBlock.Factory<HCE>(hc, cfger);
62 pnkfelix 1.1.2.9 this.ud = ud;
63 salcianu 1.1.2.7 // sometimes, TYPECAST need to be treated specially
64 salcianu 1.1.2.7 check_typecast =
65 salcianu 1.1.2.7 hc.getName().equals(harpoon.IR.Quads.QuadNoSSA.codename);
66 kkz 1.1.2.1 analyze();
67 kkz 1.1.2.1 }
68 kkz 1.1.2.1 /** Creates a <code>ReachingDefsImpl</code> object for the
69 kkz 1.1.2.6 provided <code>HCode</code> using <code>CFGrapher.DEFAULT</code>.
70 kkz 1.1.2.6 This may take a while since the analysis is done at this time.
71 kkz 1.1.2.1 */
72 cananian 1.3.2.2 public ReachingDefsImpl(HCode<HCE> hc) {
73 cananian 1.5 this(hc, (CFGrapher<HCE>) CFGrapher.DEFAULT);
74 kkz 1.1.2.1 }
75 kkz 1.1.2.1 /** Returns the Set of <code>HCodeElement</code>s providing definitions
76 kkz 1.1.2.1 * of <code>Temp</code> <code>t</code> which reach
77 kkz 1.1.2.18 * <code>HCodeElement</code> <code>hce</code>. Returns the empty
78 kkz 1.1.2.18 * Set if the given <code>HCodeElement</code> is unreachable. */
79 cananian 1.3.2.2 public Set<HCE> reachingDefs(HCE hce, Temp t) {
80 kkz 1.1.2.1 // find out which BasicBlock this HCodeElement is from
81 cananian 1.3.2.2 BasicBlock<HCE> b = bbf.getBlock(hce);
82 kkz 1.1.2.18 if (b == null) {
83 kkz 1.1.2.18 // dead code, no definitions reach
84 kkz 1.1.2.18 return java.util.Collections.EMPTY_SET;
85 kkz 1.1.2.18 }
86 kkz 1.1.2.1 // get the map for the BasicBlock
87 cananian 1.5 Map<Temp,List<Set<HCE>>> m = cache.get(b);
88 kkz 1.1.2.1 // get the BitSetFactory
89 cananian 1.3.2.2 BitSetFactory<HCE> bsf = Temp_to_BitSetFactories.get(t);
90 cananian 1.3.2.1 assert m.get(t) != null : t.toString();
91 kkz 1.1.2.2 // make a copy of the in Set for the Temp
92 cananian 1.5 Set<HCE> results = bsf.makeSet(m.get(t).get(IN));
93 kkz 1.1.2.2 // propagate in Set through the HCodeElements
94 kkz 1.1.2.2 // of the BasicBlock in correct order
95 cananian 1.6 for(HCE curr : b.statements()) {
96 kkz 1.1.2.2 if (curr == hce) return results;
97 cananian 1.3.2.2 Collection<Temp> defC = null;
98 salcianu 1.1.2.7 // special treatment of TYPECAST
99 salcianu 1.1.2.7 if(check_typecast && (curr instanceof TYPECAST))
100 salcianu 1.1.2.7 defC = Collections.singleton(((TYPECAST)curr).objectref());
101 salcianu 1.1.2.7 else
102 pnkfelix 1.1.2.9 defC = ud.defC(curr);
103 salcianu 1.1.2.7 if (defC.contains(t))
104 kkz 1.1.2.1 results = bsf.makeSet(Collections.singleton(curr));
105 kkz 1.1.2.1 }
106 cananian 1.3.2.1 assert false;
107 kkz 1.1.2.2 return null; // should never happen
108 kkz 1.1.2.1 }
109 kkz 1.1.2.1 // do analysis
110 kkz 1.1.2.1 private void analyze() {
111 kkz 1.1.2.1 final Map Temp_to_DefPts = getDefPts();
112 kkz 1.1.2.1 getBitSets(Temp_to_DefPts);
113 kkz 1.1.2.1
114 kkz 1.1.2.1 // build Gen and Kill sets
115 kkz 1.1.2.1 buildGenKillSets(Temp_to_DefPts);
116 kkz 1.1.2.2
117 kkz 1.1.2.1 // solve for fixed point
118 kkz 1.1.2.1 solve();
119 kkz 1.1.2.1 // store only essential information
120 cananian 1.6 for(BasicBlock<HCE> b : cache.keySet()) {
121 cananian 1.5 Map<Temp,List<Set<HCE>>> m = cache.get(b);
122 cananian 1.6 for(Temp t : m.keySet()) {
123 cananian 1.5 List<Set<HCE>> results = m.get(t);
124 cananian 1.5 m.put(t, Collections.singletonList( results.get(IN) ));
125 kkz 1.1.2.1 }
126 kkz 1.1.2.1 }
127 kkz 1.1.2.1 }
128 kkz 1.1.2.2 // create a mapping of Temps to a Set of possible definition points
129 cananian 1.3.2.2 private Map<Temp,Set<HCE>> getDefPts() {
130 cananian 1.3.2.2 Map<Temp,Set<HCE>> m = new HashMap<Temp,Set<HCE>>();
131 cananian 1.6 for(HCE hce : cfger.getElements(hc)) {
132 pnkfelix 1.1.2.9 StringBuffer strbuf = new StringBuffer();
133 salcianu 1.1.2.7 Temp[] tArray = null;
134 pnkfelix 1.1.2.9 report("Getting defs in: "+hce+" (defC:"+new java.util.ArrayList
135 pnkfelix 1.1.2.9 (ud.defC(hce))+")");
136 salcianu 1.1.2.7 // special treatment of TYPECAST
137 kkz 1.1.2.8 if(check_typecast && (hce instanceof TYPECAST)) {
138 pnkfelix 1.1.2.9 strbuf.append("TYPECAST: ");
139 salcianu 1.1.2.7 tArray = new Temp[]{((TYPECAST)hce).objectref()};
140 pnkfelix 1.1.2.9 } else {
141 pnkfelix 1.1.2.9 tArray = ud.def(hce);
142 pnkfelix 1.1.2.9 if (tArray.length > 0)
143 pnkfelix 1.1.2.9 strbuf.append("DEFINES: ");
144 pnkfelix 1.1.2.9 }
145 kkz 1.1.2.2 for(int i=0; i < tArray.length; i++) {
146 kkz 1.1.2.2 Temp t = tArray[i];
147 pnkfelix 1.1.2.9 strbuf.append(t+" ");
148 cananian 1.3.2.2 Set<HCE> defPts = m.get(t);
149 kkz 1.1.2.2 if (defPts == null) {
150 kkz 1.1.2.2 // have not yet encountered this Temp
151 cananian 1.3.2.2 defPts = new HashSet<HCE>();
152 kkz 1.1.2.6 // add to map
153 kkz 1.1.2.2 m.put(t, defPts);
154 kkz 1.1.2.2 }
155 kkz 1.1.2.6 // add this definition point
156 kkz 1.1.2.6 defPts.add(hce);
157 kkz 1.1.2.2 }
158 pnkfelix 1.1.2.9 /* for debugging purposes only */
159 cananian 1.3.2.2 Collection<Temp> col = ud.useC(hce);
160 pnkfelix 1.1.2.9 if (!col.isEmpty()) strbuf.append("\nUSES: ");
161 cananian 1.3.2.2 for(Iterator<Temp> it2 = col.iterator(); it2.hasNext(); )
162 pnkfelix 1.1.2.9 strbuf.append(it2.next().toString() + " ");
163 pnkfelix 1.1.2.9 if (strbuf.length() > 0)
164 pnkfelix 1.1.2.9 report(strbuf.toString());
165 pnkfelix 1.1.2.9
166 kkz 1.1.2.2 }
167 pnkfelix 1.1.2.9 StringBuffer strbuf2 = new StringBuffer("Have entry for Temp(s): ");
168 cananian 1.3.2.2 for(Iterator<Temp> keys = m.keySet().iterator(); keys.hasNext(); )
169 pnkfelix 1.1.2.9 strbuf2.append(keys.next()+" ");
170 pnkfelix 1.1.2.9 report(strbuf2.toString());
171 kkz 1.1.2.2 return m;
172 kkz 1.1.2.2 }
173 kkz 1.1.2.2 // create a mapping of Temps to BitSetFactories
174 kkz 1.1.2.2 // using a mapping of Temps to Sets of definitions points
175 cananian 1.3.2.2 private void getBitSets(Map<Temp,Set<HCE>> input) {
176 cananian 1.6 for(Temp t : input.keySet()) {
177 cananian 1.3.2.2 BitSetFactory<HCE> bsf = new BitSetFactory<HCE>(input.get(t));
178 kkz 1.1.2.2 Temp_to_BitSetFactories.put(t, bsf);
179 kkz 1.1.2.2 }
180 kkz 1.1.2.2 }
181 kkz 1.1.2.2 private final int IN = 0;
182 kkz 1.1.2.2 private final int OUT = 1;
183 kkz 1.1.2.2 private final int GEN = 2;
184 kkz 1.1.2.2 private final int KILL = 3;
185 kkz 1.1.2.1 // return a mapping of BasicBlocks to a mapping of Temps to
186 kkz 1.1.2.1 // an array of bitsets where the indices are organized as follows:
187 kkz 1.1.2.1 // 0 - gen Set
188 kkz 1.1.2.1 // 1 - kill Set
189 kkz 1.1.2.1 // 2 - in Set
190 kkz 1.1.2.1 // 3 - out Set
191 cananian 1.3.2.2 private void buildGenKillSets(Map<Temp,Set<HCE>> DefPts) {
192 kkz 1.1.2.6 // calculate Gen and Kill sets for each basic block
193 cananian 1.6 for(BasicBlock<HCE> b : bbf.blockSet()) {
194 cananian 1.5 Map<Temp,List<Set<HCE>>> Temp_to_BitSets =
195 cananian 1.5 new HashMap<Temp,List<Set<HCE>>>();
196 kkz 1.1.2.6 // iterate through the instructions in the basic block
197 cananian 1.6 for(HCE hce : b.statements()) {
198 salcianu 1.1.2.7 Temp[] tArray = null;
199 salcianu 1.1.2.7 // special treatment of TYPECAST
200 salcianu 1.1.2.7 if(check_typecast && (hce instanceof TYPECAST))
201 salcianu 1.1.2.7 tArray = new Temp[]{((TYPECAST)hce).objectref()};
202 salcianu 1.1.2.7 else
203 pnkfelix 1.1.2.9 tArray = ud.def(hce);
204 kkz 1.1.2.1 for(int i=0; i < tArray.length; i++) {
205 kkz 1.1.2.1 Temp t = tArray[i];
206 cananian 1.3.2.2 BitSetFactory<HCE> bsf
207 cananian 1.3.2.2 = Temp_to_BitSetFactories.get(t);
208 cananian 1.5 List<Set<HCE>> bitSets = new ArrayList<Set<HCE>>
209 cananian 1.5 // 0 is Gen, 1 is Kill
210 cananian 1.5 (Collections.<Set<HCE>>nCopies(4, null));
211 cananian 1.5 bitSets.set(GEN, bsf.makeSet(Collections.singleton(hce)));
212 cananian 1.3.2.2 Set<HCE> kill = new HashSet<HCE>(DefPts.get(t));
213 kkz 1.1.2.1 kill.remove(hce);
214 cananian 1.5 bitSets.set(KILL, bsf.makeSet(kill));
215 kkz 1.1.2.1 Temp_to_BitSets.put(t, bitSets);
216 kkz 1.1.2.1 }
217 cananian 1.6 for(Temp t : DefPts.keySet()) {
218 cananian 1.5 List<Set<HCE>> bitSets = Temp_to_BitSets.get(t);
219 cananian 1.3.2.2 BitSetFactory<HCE> bsf = Temp_to_BitSetFactories.get(t);
220 kkz 1.1.2.1 if (bitSets == null) {
221 cananian 1.5 bitSets = new ArrayList<Set<HCE>>
222 cananian 1.5 (Collections.<Set<HCE>>nCopies(4, null));
223 kkz 1.1.2.1 Temp_to_BitSets.put(t, bitSets);
224 cananian 1.5 bitSets.set(GEN, bsf.makeSet(Default.<HCE>EMPTY_SET()));
225 cananian 1.5 bitSets.set(KILL, bsf.makeSet(Default.<HCE>EMPTY_SET()));
226 kkz 1.1.2.1 }
227 cananian 1.5 bitSets.set(IN, bsf.makeSet(Default.<HCE>EMPTY_SET()));//in
228 cananian 1.5 bitSets.set(OUT, bsf.makeSet(Default.<HCE>EMPTY_SET()));//out
229 kkz 1.1.2.1 }
230 kkz 1.1.2.1 }
231 kkz 1.1.2.2 cache.put(b, Temp_to_BitSets);
232 kkz 1.1.2.1 }
233 kkz 1.1.2.1 }
234 kkz 1.1.2.1 // uses Worklist algorithm to solve for reaching definitions
235 kkz 1.1.2.1 // given a map of BasicBlocks to Maps of Temps to arrays of bit Sets
236 kkz 1.1.2.1 private void solve() {
237 pnkfelix 1.1.2.12 int revisits = 0;
238 pnkfelix 1.1.2.12 Set blockSet = bbf.blockSet();
239 cananian 1.3.2.2 WorkSet<BasicBlock<HCE>> worklist;
240 pnkfelix 1.1.2.12 if (true) {
241 cananian 1.3.2.2 worklist = new WorkSet<BasicBlock<HCE>>(blockSet.size());
242 cananian 1.3.2.2 Iterator<BasicBlock<HCE>> iter = bbf.postorderBlocksIter();
243 pnkfelix 1.1.2.12 while(iter.hasNext()) {
244 pnkfelix 1.1.2.12 worklist.push(iter.next());
245 pnkfelix 1.1.2.12 }
246 pnkfelix 1.1.2.12 } else {
247 cananian 1.5 worklist = new WorkSet<BasicBlock<HCE>>((Set<BasicBlock<HCE>>)blockSet);
248 pnkfelix 1.1.2.12 }
249 pnkfelix 1.1.2.12
250 kkz 1.1.2.1 while(!worklist.isEmpty()) {
251 cananian 1.3.2.2 BasicBlock<HCE> b = worklist.pull();
252 pnkfelix 1.1.2.13 revisits++;
253 kkz 1.1.2.2 // get all the bitSets for this BasicBlock
254 cananian 1.5 Map<Temp,List<Set<HCE>>> bitSets = cache.get(b);
255 cananian 1.6 for(Temp t : bitSets.keySet()) {
256 cananian 1.5 List<Set<HCE>> bitSet = bitSets.get(t);
257 cananian 1.3.2.2 BitSetFactory bsf = Temp_to_BitSetFactories.get(t);
258 cananian 1.5 Set<HCE> oldIn, oldOut;
259 cananian 1.5 oldIn = bsf.makeSet(bitSet.get(IN)); // clone old in Set
260 cananian 1.5 bitSet.get(IN).clear();
261 cananian 1.6 for(BasicBlock<HCE> pred : b.prevSet()) {
262 cananian 1.5 List<Set<HCE>> pBitSet = cache.get(pred).get(t);
263 cananian 1.5 bitSet.get(IN).addAll(pBitSet.get(OUT)); // union
264 kkz 1.1.2.1 }
265 cananian 1.5 oldOut = bitSet.get(OUT); // keep old out Set
266 cananian 1.5 bitSet.set(OUT, bsf.makeSet(bitSet.get(IN)));
267 cananian 1.5 bitSet.get(OUT).removeAll(bitSet.get(KILL));
268 cananian 1.5 bitSet.get(OUT).addAll(bitSet.get(GEN));
269 cananian 1.5 if (oldIn.equals(bitSet.get(IN)) && oldOut.equals(bitSet.get(OUT)))
270 kkz 1.1.2.1 continue;
271 cananian 1.6 for(BasicBlock<HCE> block : b.nextSet()){
272 pnkfelix 1.1.2.14 worklist.addLast(block);
273 pnkfelix 1.1.2.12 }
274 kkz 1.1.2.1 }
275 kkz 1.1.2.1 }
276 pnkfelix 1.1.2.13 if (TIME) System.out.print("(r:"+revisits+"/"+blockSet.size()+")");
277 pnkfelix 1.1.2.12
278 kkz 1.1.2.1 }
279 kkz 1.1.2.2 // debugging utility
280 kkz 1.1.2.3 private final boolean DEBUG = false;
281 kkz 1.1.2.2 private void report(String str) {
282 kkz 1.1.2.2 if (DEBUG) System.out.println(str);
283 kkz 1.1.2.1 }
284 kkz 1.1.2.1 }