1 pnkfelix 1.1.2.1 // ReachingDefsAltImpl.java, created Fri Jul 14 14:12:18 2000 by pnkfelix
2 pnkfelix 1.1.2.1 // Copyright (C) 2000 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.1 package harpoon.Analysis;
5 pnkfelix 1.1.2.1
6 pnkfelix 1.1.2.1 import harpoon.ClassFile.HCode;
7 pnkfelix 1.1.2.1 import harpoon.ClassFile.HCodeElement;
8 pnkfelix 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
9 pnkfelix 1.1.2.1 import harpoon.Temp.Temp;
10 cananian 1.5 import net.cscott.jutil.SetFactory;
11 cananian 1.5 import net.cscott.jutil.BitSetFactory;
12 cananian 1.5 import net.cscott.jutil.Factories;
13 pnkfelix 1.1.2.1 import harpoon.Util.Util;
14 cananian 1.5 import net.cscott.jutil.Default;
15 pnkfelix 1.1.2.1 import harpoon.Util.Worklist;
16 cananian 1.1.2.17 import harpoon.Util.Collections.WorkSet;
17 cananian 1.5 import net.cscott.jutil.Indexer;
18 pnkfelix 1.1.2.1 import harpoon.IR.Properties.UseDefer;
19 pnkfelix 1.1.2.1 import harpoon.IR.Quads.TYPECAST;
20 pnkfelix 1.1.2.1
21 pnkfelix 1.1.2.1 import java.util.Collections;
22 pnkfelix 1.1.2.1 import java.util.Collection;
23 pnkfelix 1.1.2.1 import java.util.HashMap;
24 pnkfelix 1.1.2.1 import java.util.HashSet;
25 pnkfelix 1.1.2.1 import java.util.Iterator;
26 pnkfelix 1.1.2.1 import java.util.Map;
27 pnkfelix 1.1.2.1 import java.util.List;
28 pnkfelix 1.1.2.12 import java.util.ArrayList;
29 pnkfelix 1.1.2.4 import java.util.ListIterator;
30 pnkfelix 1.1.2.1 import java.util.Set;
31 pnkfelix 1.1.2.1
32 pnkfelix 1.1.2.1 /**
33 pnkfelix 1.1.2.1 * <code>ReachingDefsAltImpl</code>
34 pnkfelix 1.1.2.1 *
35 pnkfelix 1.1.2.1 * @author Felix S. Klock II <pnkfelix@mit.edu>
36 cananian 1.6 * @version $Id: ReachingDefsAltImpl.java,v 1.6 2004/02/08 03:19:12 cananian Exp $
37 pnkfelix 1.1.2.1 */
38 cananian 1.3.2.2 public class ReachingDefsAltImpl<HCE extends HCodeElement>
39 cananian 1.3.2.2 extends ReachingDefs<HCE> {
40 pnkfelix 1.1.2.15
41 cananian 1.3.2.2 final private CFGrapher<HCE> cfger;
42 cananian 1.3.2.2 final protected BasicBlock.Factory<HCE> bbf;
43 pnkfelix 1.1.2.1
44 pnkfelix 1.1.2.1 // produces Set<Pair<Temp:t, HCodeElement:h>> where `h' is
45 pnkfelix 1.1.2.1 // a definition point for `t'
46 pnkfelix 1.1.2.13 final protected AugSetFactory bsf;
47 pnkfelix 1.1.2.1
48 pnkfelix 1.1.2.1 // maps Temp:t -> Set:d where `bsf'-produced `d' contains all (t,x)
49 cananian 1.3.2.3 final protected Map<Temp,Set<Map.Entry<Temp,HCE>>> tempToAllDefs;
50 pnkfelix 1.1.2.1
51 cananian 1.3.2.2 final protected Map<BasicBlock<HCE>,Record> cache =
52 cananian 1.3.2.2 new HashMap<BasicBlock<HCE>,Record>(); // maps BasicBlocks to in Sets
53 pnkfelix 1.1.2.1 final protected boolean check_typecast; // demand the special treatment of TYPECAST
54 cananian 1.3.2.2 final protected UseDefer<HCE> ud;
55 pnkfelix 1.1.2.1
56 pnkfelix 1.1.2.4
57 pnkfelix 1.1.2.1 /** Creates a <code>ReachingDefsImpl</code> object for the
58 pnkfelix 1.1.2.1 provided <code>HCode</code> using <code>CFGrapher.DEFAULT</code> and
59 pnkfelix 1.1.2.1 <code>UseDefer.DEFAULT</code>.
60 pnkfelix 1.1.2.1 This may take a while since the analysis is done at this time.
61 pnkfelix 1.1.2.1 */
62 cananian 1.3.2.2 public ReachingDefsAltImpl(HCode<HCE> hc) {
63 cananian 1.5 this(hc, (CFGrapher<HCE>) CFGrapher.DEFAULT);
64 pnkfelix 1.1.2.1 }
65 pnkfelix 1.1.2.1
66 pnkfelix 1.1.2.1 /** Creates a <code>ReachingDefsImpl</code> object for the
67 pnkfelix 1.1.2.1 provided <code>HCode</code> for an IR implementing
68 cananian 1.1.2.14 <code>UseDefable</code> using the provided <code>CFGrapher</code>.
69 pnkfelix 1.1.2.1 This may take a while since the analysis is done at this time.
70 pnkfelix 1.1.2.1 */
71 cananian 1.3.2.2 public ReachingDefsAltImpl(HCode<HCE> hc, CFGrapher<HCE> cfger) {
72 cananian 1.5 this(hc, cfger, (UseDefer<HCE>) UseDefer.DEFAULT);
73 pnkfelix 1.1.2.1 }
74 pnkfelix 1.1.2.1 /** Creates a <code>ReachingDefsImpl</code> object for the
75 pnkfelix 1.1.2.1 provided <code>HCode</code> using the provided
76 pnkfelix 1.1.2.1 <code>CFGrapher</code> and <code>UseDefer</code>. This may
77 pnkfelix 1.1.2.1 take a while since the analysis is done at this time.
78 pnkfelix 1.1.2.1 */
79 cananian 1.3.2.2 public ReachingDefsAltImpl(final HCode<HCE> hc, CFGrapher<HCE> cfger, final UseDefer<HCE> ud) {
80 pnkfelix 1.1.2.1 super(hc);
81 pnkfelix 1.1.2.1 this.cfger = cfger;
82 cananian 1.3.2.2 this.bbf = new BasicBlock.Factory<HCE>(hc, cfger);
83 pnkfelix 1.1.2.1 this.ud = ud;
84 pnkfelix 1.1.2.1 // sometimes, TYPECAST need to be treated specially
85 pnkfelix 1.1.2.1 check_typecast =
86 pnkfelix 1.1.2.1 hc.getName().equals(harpoon.IR.Quads.QuadNoSSA.codename);
87 pnkfelix 1.1.2.12 report("Entering analyze() ");
88 pnkfelix 1.1.2.12
89 pnkfelix 1.1.2.12 final DefPtRecord dpr = getDefPts();
90 pnkfelix 1.1.2.12 tempToAllDefs = dpr.tempToPairs;
91 pnkfelix 1.1.2.1
92 pnkfelix 1.1.2.12 // System.out.print("constucting universe");
93 cananian 1.3.2.3 Iterator<Set<Map.Entry<Temp,HCE>>> pairsets = tempToAllDefs.values().iterator();
94 cananian 1.3.2.3 Set<Map.Entry<Temp,HCE>> universe = new HashSet<Map.Entry<Temp,HCE>>(tempToAllDefs.values().size());
95 pnkfelix 1.1.2.12 int totalsz = 0, numsets = 0, totsqsz = 0;
96 pnkfelix 1.1.2.13 int maxsz=0, minsz=Integer.MAX_VALUE;
97 pnkfelix 1.1.2.2 while(pairsets.hasNext()) {
98 cananian 1.3.2.3 Set<Map.Entry<Temp,HCE>> pairset = pairsets.next();
99 pnkfelix 1.1.2.12 universe.addAll(pairset);
100 pnkfelix 1.1.2.12
101 pnkfelix 1.1.2.13 if (pairset.size() > maxsz) maxsz = pairset.size();
102 pnkfelix 1.1.2.13 if (pairset.size() < minsz) minsz = pairset.size();
103 pnkfelix 1.1.2.12 totalsz += pairset.size();
104 pnkfelix 1.1.2.12 totsqsz += (pairset.size()*pairset.size());
105 pnkfelix 1.1.2.12 numsets++;
106 pnkfelix 1.1.2.2 }
107 pnkfelix 1.1.2.12
108 pnkfelix 1.1.2.2
109 pnkfelix 1.1.2.12 report(" totalsz:"+totalsz +" totsqsz:"+totsqsz +
110 pnkfelix 1.1.2.13 " maxsz:"+maxsz+" minsz:"+minsz+
111 pnkfelix 1.1.2.12 " numsets:"+numsets +" mean sz:"+(totalsz/numsets));
112 pnkfelix 1.1.2.12 report(" numblks:"+bbf.blockSet().size()+
113 pnkfelix 1.1.2.12 " numtmps:"+tempToAllDefs.keySet().size());
114 pnkfelix 1.1.2.12 final int meanSize = totalsz / numsets;
115 pnkfelix 1.1.2.12
116 pnkfelix 1.1.2.13 report("constucting AugmentedSetFactory (uni:"+universe.size()+")");
117 pnkfelix 1.1.2.12
118 pnkfelix 1.1.2.13 bsf = new AugSetFactory(universe);
119 pnkfelix 1.1.2.12
120 pnkfelix 1.1.2.12 if (true) {
121 pnkfelix 1.1.2.12 report("s/HashSet/AugSet/");
122 pnkfelix 1.1.2.12 // replace HashSets with AugSets in tempToAllDefs.values()
123 cananian 1.3.2.3 Iterator<Map.Entry<Temp,Set<Map.Entry<Temp,HCE>>>> es = tempToAllDefs.entrySet().iterator();
124 pnkfelix 1.1.2.13 while(es.hasNext()) {
125 cananian 1.3.2.3 Map.Entry<Temp,Set<Map.Entry<Temp,HCE>>> e = es.next();
126 cananian 1.3.2.3 Set<Map.Entry<Temp,HCE>> pairs = e.getValue();
127 pnkfelix 1.1.2.13 e.setValue(bsf.makeSet(pairs));
128 pnkfelix 1.1.2.12 }
129 pnkfelix 1.1.2.13 bsf.stats();
130 pnkfelix 1.1.2.13
131 pnkfelix 1.1.2.12 }
132 pnkfelix 1.1.2.12
133 pnkfelix 1.1.2.12 report("performing analysis");
134 pnkfelix 1.1.2.2 analyze(tempToAllDefs);
135 pnkfelix 1.1.2.1 report("Leaving analyze()");
136 pnkfelix 1.1.2.2
137 pnkfelix 1.1.2.2
138 pnkfelix 1.1.2.1 }
139 pnkfelix 1.1.2.1
140 pnkfelix 1.1.2.1 /** Returns the Set of <code>HCodeElement</code>s providing definitions
141 pnkfelix 1.1.2.1 * of <code>Temp</code> <code>t</code> which reach
142 pnkfelix 1.1.2.8 * <code>HCodeElement</code> <code>hce</code>.
143 pnkfelix 1.1.2.8 * Any use that is not explicitly defined is assumed to be
144 pnkfelix 1.1.2.8 * implicitly defined by the root element of the
145 pnkfelix 1.1.2.8 * <code>HCode</code> for <code>this</code>.
146 pnkfelix 1.1.2.8 */
147 cananian 1.3.2.2 public Set<HCE> reachingDefs(HCE hce, Temp t) {
148 pnkfelix 1.1.2.3 // report("Processing HCodeElement: "+hce+" Temp: "+t);
149 pnkfelix 1.1.2.1 // find out which BasicBlock this HCodeElement is from
150 cananian 1.3.2.2 BasicBlock<HCE> b = bbf.getBlock(hce);
151 cananian 1.3.2.1 //assert b != null : "no block" /* +" for "+hce */;
152 witchel 1.1.2.10 if(b == null) {
153 cananian 1.3.2.3 if (true) return java.util.Collections.EMPTY_SET;
154 witchel 1.1.2.10 System.out.println("\nSuccC " + cfger.succC(hce));
155 witchel 1.1.2.10 System.out.println("PredC " + cfger.predC(hce));
156 cananian 1.3.2.1 assert false : "no block"+" for "+hce;
157 witchel 1.1.2.10 }
158 pnkfelix 1.1.2.3 // report("In BasicBlock: "+b.toString());
159 pnkfelix 1.1.2.4
160 pnkfelix 1.1.2.4 boolean sawIt = false;
161 cananian 1.3.2.2 List<HCE> stms = b.statements();
162 cananian 1.3.2.2 ListIterator<HCE> iter = stms.listIterator(stms.size());
163 pnkfelix 1.1.2.4 while(iter.hasPrevious()) {
164 cananian 1.3.2.2 HCE curr = iter.previous();
165 pnkfelix 1.1.2.4 if (curr == hce) {
166 pnkfelix 1.1.2.4 sawIt = true;
167 pnkfelix 1.1.2.4 break;
168 pnkfelix 1.1.2.4 }
169 pnkfelix 1.1.2.4 }
170 cananian 1.3.2.1 assert sawIt;
171 pnkfelix 1.1.2.4
172 pnkfelix 1.1.2.4 // broke out of loop, so now we need to see if exists a
173 pnkfelix 1.1.2.4 // definition in remaining hces
174 pnkfelix 1.1.2.4 while(iter.hasPrevious()) {
175 cananian 1.3.2.2 HCE curr = iter.previous();
176 pnkfelix 1.1.2.4
177 cananian 1.3.2.2 Collection<Temp> defC = null;
178 pnkfelix 1.1.2.4
179 pnkfelix 1.1.2.4 // special treatment of TYPECAST
180 pnkfelix 1.1.2.4 if(check_typecast && (curr instanceof TYPECAST))
181 pnkfelix 1.1.2.4 defC = Collections.singleton(((TYPECAST)curr).objectref());
182 pnkfelix 1.1.2.4 else
183 pnkfelix 1.1.2.4 defC = ud.defC(curr);
184 pnkfelix 1.1.2.4
185 pnkfelix 1.1.2.4 if (defC.contains(t)) {
186 pnkfelix 1.1.2.5 // System.out.print(" I");
187 pnkfelix 1.1.2.4 return Collections.singleton(curr);
188 pnkfelix 1.1.2.4 }
189 pnkfelix 1.1.2.4 }
190 pnkfelix 1.1.2.4
191 pnkfelix 1.1.2.4 // if we got here, then there isn't a def in the remainder
192 pnkfelix 1.1.2.4 // of the basic block... do a lookup
193 pnkfelix 1.1.2.4
194 pnkfelix 1.1.2.1 // get the map for the BasicBlock
195 cananian 1.3.2.3 Record r = cache.get(b);
196 pnkfelix 1.1.2.1
197 pnkfelix 1.1.2.1 // find HCodeElements associated with `t' in the IN Set
198 cananian 1.3.2.3 Set<Map.Entry<Temp,HCE>> results = bsf.makeSet(r.IN);
199 cananian 1.3.2.3 Set<Map.Entry<Temp,HCE>> defs = tempToAllDefs.get(t);
200 pnkfelix 1.1.2.8 if (defs == null) {
201 pnkfelix 1.1.2.9 // no def for t
202 pnkfelix 1.1.2.9 defs = Collections.EMPTY_SET;
203 pnkfelix 1.1.2.8 }
204 pnkfelix 1.1.2.7 results.retainAll(defs);
205 pnkfelix 1.1.2.2
206 cananian 1.3.2.3 Iterator<Map.Entry<Temp,HCE>> pairs = results.iterator();
207 cananian 1.3.2.3 Set<HCE> results2 = new HashSet<HCE>();
208 pnkfelix 1.1.2.1 while(pairs.hasNext()) {
209 cananian 1.3.2.3 results2.add( pairs.next().getValue() );
210 pnkfelix 1.1.2.1 }
211 pnkfelix 1.1.2.2
212 cananian 1.3.2.3 return results2;
213 pnkfelix 1.1.2.1 }
214 pnkfelix 1.1.2.1
215 pnkfelix 1.1.2.1 // do analysis
216 cananian 1.3.2.3 private void analyze(Map<Temp,Set<Map.Entry<Temp,HCE>>> Temp_To_Pairs) {
217 pnkfelix 1.1.2.15 if (TIME) System.out.print("(");
218 pnkfelix 1.1.2.1 // build Gen and Kill sets
219 pnkfelix 1.1.2.12 report("Entering buildGenKillSets()");
220 pnkfelix 1.1.2.2 buildGenKillSets(Temp_To_Pairs);
221 pnkfelix 1.1.2.13
222 pnkfelix 1.1.2.13 bsf.stats();
223 pnkfelix 1.1.2.3 // report("Leaving buildGenKillSets()");
224 pnkfelix 1.1.2.15
225 pnkfelix 1.1.2.1 // solve for fixed point
226 pnkfelix 1.1.2.15 report("Entering solve()"); if (TIME) System.out.print("S");
227 pnkfelix 1.1.2.1 solve();
228 pnkfelix 1.1.2.3 // report("Leaving solve()");
229 pnkfelix 1.1.2.1 // store only essential information
230 cananian 1.3.2.3 Iterator<Record> records = cache.values().iterator();
231 pnkfelix 1.1.2.1 while(records.hasNext()) {
232 cananian 1.3.2.3 Record r = records.next();
233 pnkfelix 1.1.2.1 r.OUT = null; r.KILL = null; r.GEN = null;
234 pnkfelix 1.1.2.1 }
235 pnkfelix 1.1.2.15
236 pnkfelix 1.1.2.15 if (TIME) System.out.print(")");
237 pnkfelix 1.1.2.1 }
238 pnkfelix 1.1.2.1
239 pnkfelix 1.1.2.12 class DefPtRecord {
240 pnkfelix 1.1.2.12 // Temp -> Set of Pair< Temp, Defpt > >
241 cananian 1.3.2.3 private Map<Temp,Set<Map.Entry<Temp,HCE>>> tempToPairs;
242 pnkfelix 1.1.2.12 // List of Pair< Temp, Defpt >
243 pnkfelix 1.1.2.12 private ArrayList defpts;
244 pnkfelix 1.1.2.12 DefPtRecord(int mapsz) {
245 cananian 1.3.2.3 tempToPairs = new HashMap<Temp,Set<Map.Entry<Temp,HCE>>>(mapsz);
246 pnkfelix 1.1.2.12 defpts = new ArrayList();
247 pnkfelix 1.1.2.12 }
248 pnkfelix 1.1.2.12 }
249 pnkfelix 1.1.2.12
250 pnkfelix 1.1.2.12 // create a mapping of Temps to a Set of (t, defPt) Pairs,
251 pnkfelix 1.1.2.12 // as well as a list of defPts defining more than one Temp.
252 pnkfelix 1.1.2.12 // (the latter is to allow a more efficient indexer definition.
253 pnkfelix 1.1.2.12 private DefPtRecord getDefPts() {
254 cananian 1.3.2.2 Collection<HCE> hceL = cfger.getElements(hc);
255 pnkfelix 1.1.2.12 DefPtRecord dpr = new DefPtRecord(hceL.size());
256 cananian 1.3.2.3 Map<Temp,Set<Map.Entry<Temp,HCE>>> m = dpr.tempToPairs;
257 pnkfelix 1.1.2.12 List multDefns = dpr.defpts;
258 cananian 1.6 for(HCE hce : hceL) {
259 pnkfelix 1.1.2.1 StringBuffer strbuf = new StringBuffer();
260 pnkfelix 1.1.2.1 Temp[] tArray = null;
261 pnkfelix 1.1.2.3 //report("Getting defs in: "+hce+" (defC:"+new java.util.ArrayList(ud.defC(hce))+")");
262 pnkfelix 1.1.2.1 // special treatment of TYPECAST
263 pnkfelix 1.1.2.1 if(check_typecast && (hce instanceof TYPECAST)) {
264 pnkfelix 1.1.2.1 strbuf.append("TYPECAST: ");
265 pnkfelix 1.1.2.1 tArray = new Temp[]{((TYPECAST)hce).objectref()};
266 pnkfelix 1.1.2.1 } else {
267 pnkfelix 1.1.2.1 tArray = ud.def(hce);
268 pnkfelix 1.1.2.1 if (tArray.length > 0)
269 pnkfelix 1.1.2.1 strbuf.append("DEFINES: ");
270 pnkfelix 1.1.2.1 }
271 pnkfelix 1.1.2.1 for(int i=0; i < tArray.length; i++) {
272 pnkfelix 1.1.2.1 Temp t = tArray[i];
273 pnkfelix 1.1.2.1 strbuf.append(t+" ");
274 cananian 1.3.2.3 Set<Map.Entry<Temp,HCE>> defPts = m.get(t);
275 pnkfelix 1.1.2.1 if (defPts == null) {
276 pnkfelix 1.1.2.1 // have not yet encountered this Temp
277 cananian 1.3.2.3 defPts = new HashSet<Map.Entry<Temp,HCE>>();
278 pnkfelix 1.1.2.1 // add to map
279 pnkfelix 1.1.2.1 m.put(t, defPts);
280 pnkfelix 1.1.2.1 }
281 pnkfelix 1.1.2.1 // add this definition point
282 cananian 1.3.2.3 Map.Entry<Temp,HCE> pair = Default.entry(t,hce);
283 pnkfelix 1.1.2.12 defPts.add(pair);
284 pnkfelix 1.1.2.12 if (tArray.length > 1) {
285 pnkfelix 1.1.2.12 multDefns.add(pair);
286 pnkfelix 1.1.2.12 }
287 pnkfelix 1.1.2.1 }
288 pnkfelix 1.1.2.12 if (false && DEBUG) {
289 pnkfelix 1.1.2.1 Collection col = ud.useC(hce);
290 pnkfelix 1.1.2.1 if (!col.isEmpty()) strbuf.append("\nUSES: ");
291 pnkfelix 1.1.2.1 for(Iterator it2 = col.iterator(); it2.hasNext(); )
292 pnkfelix 1.1.2.1 strbuf.append(it2.next().toString() + " ");
293 pnkfelix 1.1.2.1 if (strbuf.length() > 0)
294 pnkfelix 1.1.2.1 report(strbuf.toString());
295 pnkfelix 1.1.2.1 }
296 pnkfelix 1.1.2.1 }
297 pnkfelix 1.1.2.12 if (false && DEBUG) {
298 pnkfelix 1.1.2.1 StringBuffer strbuf2 =
299 pnkfelix 1.1.2.1 new StringBuffer("Have entry for Temp(s): ");
300 pnkfelix 1.1.2.1 for(Iterator keys = m.keySet().iterator(); keys.hasNext(); )
301 pnkfelix 1.1.2.1 strbuf2.append(keys.next()+" ");
302 pnkfelix 1.1.2.1 report(strbuf2.toString());
303 pnkfelix 1.1.2.1 }
304 pnkfelix 1.1.2.12 return dpr;
305 pnkfelix 1.1.2.1 }
306 pnkfelix 1.1.2.2
307 pnkfelix 1.1.2.1 final class Record {
308 cananian 1.3.2.3 Set<Map.Entry<Temp,HCE>> IN, OUT, GEN, KILL;
309 pnkfelix 1.1.2.12 boolean haveSeen = false;
310 pnkfelix 1.1.2.1 Record() {
311 pnkfelix 1.1.2.1 IN = bsf.makeSet();
312 pnkfelix 1.1.2.1 OUT = bsf.makeSet();
313 pnkfelix 1.1.2.1 GEN = bsf.makeSet();
314 pnkfelix 1.1.2.1 KILL = bsf.makeSet();
315 pnkfelix 1.1.2.1 }
316 pnkfelix 1.1.2.1 }
317 pnkfelix 1.1.2.1 // builds a BasicBlock -> Record mapping in `cache'
318 cananian 1.3.2.3 private void buildGenKillSets(Map<Temp,Set<Map.Entry<Temp,HCE>>> Temp_To_Pairs) {
319 pnkfelix 1.1.2.1 // calculate Gen and Kill sets for each basic block
320 cananian 1.6 for(BasicBlock<HCE> b : bbf.blockSet()) {
321 pnkfelix 1.1.2.1 Record bitSets = new Record();
322 pnkfelix 1.1.2.1 cache.put(b, bitSets);
323 pnkfelix 1.1.2.1
324 pnkfelix 1.1.2.1 // iterate through the instructions in the basic block
325 cananian 1.6 for(HCE hce : b.statements()) {
326 pnkfelix 1.1.2.1 Temp[] tArray = null;
327 pnkfelix 1.1.2.1 // special treatment of TYPECAST
328 pnkfelix 1.1.2.1 if(check_typecast && (hce instanceof TYPECAST))
329 pnkfelix 1.1.2.1 tArray = new Temp[]{((TYPECAST)hce).objectref()};
330 pnkfelix 1.1.2.1 else
331 pnkfelix 1.1.2.1 tArray = ud.def(hce);
332 pnkfelix 1.1.2.1 for(int i=0; i < tArray.length; i++) {
333 pnkfelix 1.1.2.1 Temp t = tArray[i];
334 cananian 1.3.2.3 Map.Entry<Temp,HCE> def = Default.entry(t, hce);
335 pnkfelix 1.1.2.12 bitSets.GEN.add(def);
336 cananian 1.3.2.3 Set<Map.Entry<Temp,HCE>> kill = bsf.makeSet(Temp_To_Pairs.get(t));
337 pnkfelix 1.1.2.12 kill.remove(def);
338 pnkfelix 1.1.2.12 bitSets.KILL.addAll(kill);
339 pnkfelix 1.1.2.1 }
340 pnkfelix 1.1.2.1 }
341 pnkfelix 1.1.2.1 }
342 pnkfelix 1.1.2.1 }
343 pnkfelix 1.1.2.1 // uses Worklist algorithm to solve for reaching definitions
344 pnkfelix 1.1.2.1 // given a BasicBlock -> Record map
345 pnkfelix 1.1.2.1 private void solve() {
346 pnkfelix 1.1.2.1 int revisits = 0;
347 pnkfelix 1.1.2.1 WorkSet worklist;
348 pnkfelix 1.1.2.12
349 pnkfelix 1.1.2.12 worklist = new WorkSet(bbf.blockSet().size());
350 pnkfelix 1.1.2.12 Iterator iter = bbf.postorderBlocksIter();
351 pnkfelix 1.1.2.12 while(iter.hasNext()) {
352 pnkfelix 1.1.2.12 worklist.addFirst(iter.next());
353 pnkfelix 1.1.2.1 }
354 pnkfelix 1.1.2.1
355 pnkfelix 1.1.2.1 while(!worklist.isEmpty()) {
356 pnkfelix 1.1.2.12 // System.out.print(worklist.size() + " ");
357 pnkfelix 1.1.2.12
358 pnkfelix 1.1.2.12 // FSK is unsure of these changes (11/13/2000)
359 pnkfelix 1.1.2.12 // BasicBlock b = (BasicBlock)worklist.pull();
360 pnkfelix 1.1.2.12 BasicBlock b = (BasicBlock)worklist.removeFirst();
361 pnkfelix 1.1.2.12
362 pnkfelix 1.1.2.1 revisits++;
363 pnkfelix 1.1.2.1 // get all the bitSets for this BasicBlock
364 cananian 1.3.2.3 Record bitSet = cache.get(b);
365 pnkfelix 1.1.2.1 Set oldIN, oldOUT;
366 pnkfelix 1.1.2.1 oldIN = bsf.makeSet(bitSet.IN); // clone old in Set
367 pnkfelix 1.1.2.1 bitSet.IN.clear();
368 cananian 1.6 for(Object predO : b.prevSet()) {
369 cananian 1.6 BasicBlock pred = (BasicBlock) predO;
370 cananian 1.3.2.3 Record pBitSet = cache.get(pred);
371 pnkfelix 1.1.2.1 bitSet.IN.addAll(pBitSet.OUT); // union
372 pnkfelix 1.1.2.1 }
373 pnkfelix 1.1.2.12
374 pnkfelix 1.1.2.12 // FSK is unsure of these changes (11/13/2000)
375 pnkfelix 1.1.2.12 if (bitSet.haveSeen && oldIN.equals(bitSet.IN)) {
376 pnkfelix 1.1.2.12 // OUT is a function of IN, so if, by some miracle, IN
377 pnkfelix 1.1.2.12 // has not changed, we continue
378 pnkfelix 1.1.2.12 // System.out.print(" MIRACLE! ");
379 pnkfelix 1.1.2.12 continue;
380 pnkfelix 1.1.2.12 }
381 pnkfelix 1.1.2.12
382 pnkfelix 1.1.2.1 oldOUT = bitSet.OUT; // keep old out Set
383 pnkfelix 1.1.2.1 bitSet.OUT = bsf.makeSet(bitSet.IN);
384 pnkfelix 1.1.2.1 bitSet.OUT.removeAll(bitSet.KILL);
385 pnkfelix 1.1.2.1 bitSet.OUT.addAll(bitSet.GEN);
386 pnkfelix 1.1.2.12 bitSet.haveSeen = true;
387 pnkfelix 1.1.2.12
388 pnkfelix 1.1.2.12 // FSK is unsure of these changes (11/13/2000)
389 pnkfelix 1.1.2.12 // if (oldIN.equals(bitSet.IN) && oldOUT.equals(bitSet.OUT))
390 pnkfelix 1.1.2.12 if (oldOUT.equals(bitSet.OUT)) {
391 pnkfelix 1.1.2.12 // System.out.print(" GIFT! ");
392 pnkfelix 1.1.2.1 continue;
393 pnkfelix 1.1.2.12 }
394 pnkfelix 1.1.2.1 for(Iterator succs=b.nextSet().iterator();succs.hasNext();){
395 pnkfelix 1.1.2.1 Object block = (BasicBlock)succs.next();
396 pnkfelix 1.1.2.12 worklist.addLast(block);
397 pnkfelix 1.1.2.1 }
398 pnkfelix 1.1.2.1 }
399 pnkfelix 1.1.2.15 if (TIME) System.out.print("#iter:"+revisits+
400 pnkfelix 1.1.2.15 " #bbs:"+bbf.blockSet().size());
401 pnkfelix 1.1.2.1
402 pnkfelix 1.1.2.1 }
403 pnkfelix 1.1.2.1 // debugging utility
404 pnkfelix 1.1.2.3 private static final boolean DEBUG = false;
405 pnkfelix 1.1.2.13 private static void report(String str) {
406 pnkfelix 1.1.2.12 if (DEBUG) System.out.println(str+" "+new java.util.Date());
407 pnkfelix 1.1.2.13 }
408 pnkfelix 1.1.2.13
409 pnkfelix 1.1.2.13 class AugSetFactory extends SetFactory {
410 pnkfelix 1.1.2.13 AugSetFactory(Set universe) {
411 pnkfelix 1.1.2.15
412 cananian 1.5 // universe = new net.cscott.jutil.LinearSet(universe);
413 pnkfelix 1.1.2.15 // FSK: oog; don't do the above (BSF methods need fast
414 pnkfelix 1.1.2.15 // universe.contains(..) method implementation
415 pnkfelix 1.1.2.15
416 pnkfelix 1.1.2.13 bitSetFact = new BitSetFactory(universe);
417 pnkfelix 1.1.2.13 final int unisize = universe.size();
418 pnkfelix 1.1.2.13 linToBitThreshold = unisize / 1000;
419 pnkfelix 1.1.2.13 bitToLinThreshold = unisize / 10000;
420 pnkfelix 1.1.2.13 }
421 pnkfelix 1.1.2.13
422 pnkfelix 1.1.2.13 final BitSetFactory bitSetFact;
423 pnkfelix 1.1.2.13 //final SetFactory linSetFact = Factories.linearSetFactory;
424 pnkfelix 1.1.2.13 final SetFactory linSetFact =
425 cananian 1.5 new net.cscott.jutil.AggregateSetFactory();
426 pnkfelix 1.1.2.13 final int linToBitThreshold, bitToLinThreshold;
427 pnkfelix 1.1.2.13
428 pnkfelix 1.1.2.13 int linToBitSwitches = 0;
429 pnkfelix 1.1.2.13 int bitToLinSwitches = 0;
430 pnkfelix 1.1.2.13 int startedAsBit = 0;
431 pnkfelix 1.1.2.13 int startedAsLin = 0;
432 pnkfelix 1.1.2.13
433 pnkfelix 1.1.2.13 public void stats() {
434 pnkfelix 1.1.2.13 report("stats: "+
435 pnkfelix 1.1.2.13 "l2b: "+linToBitSwitches+" "+
436 pnkfelix 1.1.2.13 "b2l: "+bitToLinSwitches+" "+
437 pnkfelix 1.1.2.13 "sal: "+startedAsLin+" "+
438 pnkfelix 1.1.2.13 "sab: "+startedAsBit);
439 pnkfelix 1.1.2.13 }
440 pnkfelix 1.1.2.13
441 pnkfelix 1.1.2.13 class AugSet extends java.util.AbstractSet {
442 pnkfelix 1.1.2.13 boolean bitSetRep;
443 pnkfelix 1.1.2.13 Set bSet;
444 pnkfelix 1.1.2.13
445 pnkfelix 1.1.2.13 // FSK: maybe change to add HashSets for medium size
446 pnkfelix 1.1.2.13 // (O(size-of-set) vs O(size-of-universe)
447 pnkfelix 1.1.2.13
448 pnkfelix 1.1.2.13 public AugSet(Collection c){ this(c, (c.size() > linToBitThreshold));}
449 pnkfelix 1.1.2.13 public AugSet(Collection c, boolean useBitSetRep) {
450 pnkfelix 1.1.2.13 if (useBitSetRep) {
451 pnkfelix 1.1.2.13 startedAsBit++;
452 pnkfelix 1.1.2.13 bitSetRep = true;
453 pnkfelix 1.1.2.13 if (c instanceof AugSet) {
454 pnkfelix 1.1.2.13 bSet = bitSetFact.makeSet( ((AugSet)c).bSet );
455 pnkfelix 1.1.2.13 } else {
456 pnkfelix 1.1.2.13 bSet = bitSetFact.makeSet(c);
457 pnkfelix 1.1.2.13 }
458 pnkfelix 1.1.2.13 } else {
459 pnkfelix 1.1.2.13 startedAsLin++;
460 pnkfelix 1.1.2.13 bitSetRep = false;
461 pnkfelix 1.1.2.13 bSet = linSetFact.makeSet(c);
462 pnkfelix 1.1.2.13 }
463 pnkfelix 1.1.2.13 }
464 pnkfelix 1.1.2.13 public boolean equals(Object o) {
465 pnkfelix 1.1.2.13 if (o instanceof AugSet) {
466 pnkfelix 1.1.2.13 return bSet.equals( ((AugSet)o).bSet );
467 pnkfelix 1.1.2.13 } else {
468 pnkfelix 1.1.2.13 return super.equals(o);
469 pnkfelix 1.1.2.13 }
470 pnkfelix 1.1.2.13 }
471 pnkfelix 1.1.2.13 public int size() { return bSet.size(); }
472 pnkfelix 1.1.2.13 public Iterator iterator() { return bSet.iterator(); }
473 pnkfelix 1.1.2.13 public void clear() { bSet.clear(); }
474 pnkfelix 1.1.2.13 public boolean add(Object o) { return mayConvert(bSet.add(o)); }
475 pnkfelix 1.1.2.13 public boolean remove(Object o){return mayConvert(bSet.remove(o));}
476 pnkfelix 1.1.2.13 public boolean addAll(Collection c) {
477 pnkfelix 1.1.2.13 boolean b;
478 pnkfelix 1.1.2.13 mayConvert(c.size() + bSet.size());
479 pnkfelix 1.1.2.13 if (c instanceof AugSet) {
480 pnkfelix 1.1.2.13 // System.out.print("AU_");
481 pnkfelix 1.1.2.13 b = bSet.addAll( ((AugSet)c).bSet );
482 pnkfelix 1.1.2.13 // System.out.print(size());
483 pnkfelix 1.1.2.13 } else {
484 pnkfelix 1.1.2.13 // System.out.print("SU_");
485 pnkfelix 1.1.2.13 b = bSet.addAll(c);
486 pnkfelix 1.1.2.13 // System.out.print(size());
487 pnkfelix 1.1.2.13 }
488 pnkfelix 1.1.2.13 mayConvert();
489 pnkfelix 1.1.2.13 return b;
490 pnkfelix 1.1.2.13 }
491 pnkfelix 1.1.2.13 public boolean removeAll(Collection c) {
492 pnkfelix 1.1.2.13 return ((c instanceof AugSet) ?
493 pnkfelix 1.1.2.13 bSet.removeAll(((AugSet)c).bSet):
494 pnkfelix 1.1.2.13 bSet.removeAll(c));
495 pnkfelix 1.1.2.13 }
496 pnkfelix 1.1.2.13 public boolean retainAll(Collection c) {
497 pnkfelix 1.1.2.13 return ((c instanceof AugSet) ?
498 pnkfelix 1.1.2.13 bSet.retainAll(((AugSet)c).bSet):
499 pnkfelix 1.1.2.13 bSet.retainAll(c));
500 pnkfelix 1.1.2.13 }
501 pnkfelix 1.1.2.13
502 pnkfelix 1.1.2.13 // macro to prettify other code
503 pnkfelix 1.1.2.13 private boolean mayConvert(boolean b) {mayConvert(); return b;}
504 pnkfelix 1.1.2.13 private void mayConvert() { mayConvert(this.size()); }
505 pnkfelix 1.1.2.13 private void mayConvert(int sz) {
506 pnkfelix 1.1.2.13 if (bitSetRep) {
507 pnkfelix 1.1.2.13 if (sz < bitToLinThreshold) {
508 pnkfelix 1.1.2.13 // switch to tight rep
509 pnkfelix 1.1.2.13 bitSetRep = false;
510 pnkfelix 1.1.2.13 bitToLinSwitches++;
511 pnkfelix 1.1.2.13 bSet = linSetFact.makeSet(this);
512 pnkfelix 1.1.2.13 }
513 pnkfelix 1.1.2.13 } else {
514 pnkfelix 1.1.2.13 if (sz > linToBitThreshold ) {
515 pnkfelix 1.1.2.13 // switch to bitset rep
516 pnkfelix 1.1.2.13 bitSetRep = true;
517 pnkfelix 1.1.2.13 linToBitSwitches++;
518 pnkfelix 1.1.2.13 bSet = bitSetFact.makeSet(this);
519 pnkfelix 1.1.2.13 }
520 pnkfelix 1.1.2.13 }
521 pnkfelix 1.1.2.13 }
522 pnkfelix 1.1.2.13
523 pnkfelix 1.1.2.13 }
524 pnkfelix 1.1.2.13 public Set makeSet(Collection c) {
525 pnkfelix 1.1.2.13 return new AugSet(c);
526 pnkfelix 1.1.2.13 }
527 pnkfelix 1.1.2.13
528 pnkfelix 1.1.2.1 }
529 cananian 1.2 }