1 cananian 1.1 // SingularFinder.java, created Sat May 3 20:00:14 2003 by cananian
2 cananian 1.1 // Copyright (C) 2003 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1 package harpoon.Analysis.Companions;
5 cananian 1.1
6 cananian 1.1 import harpoon.ClassFile.HCode;
7 cananian 1.1 import harpoon.ClassFile.HCodeFactory;
8 cananian 1.1 import harpoon.ClassFile.HMethod;
9 cananian 1.3 import harpoon.IR.Quads.ANEW;
10 cananian 1.3 import harpoon.IR.Quads.Edge;
11 cananian 1.3 import harpoon.IR.Quads.METHOD;
12 cananian 1.3 import harpoon.IR.Quads.MOVE;
13 cananian 1.3 import harpoon.IR.Quads.NEW;
14 cananian 1.3 import harpoon.IR.Quads.PHI;
15 cananian 1.3 import harpoon.IR.Quads.SIGMA;
16 cananian 1.1 import harpoon.IR.Quads.Quad;
17 cananian 1.1 import harpoon.Temp.Temp;
18 cananian 1.5 import net.cscott.jutil.Default;
19 cananian 1.5 import net.cscott.jutil.AggregateMapFactory;
20 cananian 1.5 import net.cscott.jutil.AggregateSetFactory;
21 cananian 1.2 import harpoon.Util.Collections.Graph;
22 cananian 1.5 import net.cscott.jutil.MapFactory;
23 cananian 1.5 import net.cscott.jutil.SetFactory;
24 cananian 1.5 import net.cscott.jutil.WorkSet;
25 cananian 1.1 import java.util.ArrayList;
26 cananian 1.1 import java.util.Arrays;
27 cananian 1.1 import java.util.Collection;
28 cananian 1.3 import java.util.Collections;
29 cananian 1.1 import java.util.HashMap;
30 cananian 1.1 import java.util.HashSet;
31 cananian 1.1 import java.util.Iterator;
32 cananian 1.1 import java.util.List;
33 cananian 1.1 import java.util.Map;
34 cananian 1.1 import java.util.Set;
35 cananian 1.4 import java.util.TreeMap;
36 cananian 1.3 import java.util.TreeSet;
37 cananian 1.1 /**
38 cananian 1.1 * <code>SingularFinder</code> is an implementation of
39 cananian 1.1 * <code>SingularOracle</code> for quad IRs.
40 cananian 1.1 *
41 cananian 1.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
42 cananian 1.6 * @version $Id: SingularFinder.java,v 1.6 2004/02/08 03:19:17 cananian Exp $
43 cananian 1.1 */
44 cananian 1.1 public class SingularFinder implements SingularOracle<Quad> {
45 cananian 1.1 private final HCodeFactory hcf;
46 cananian 1.1 /** Creates a <code>SingularFinder</code>. */
47 cananian 1.1 public SingularFinder(HCodeFactory hcf) {
48 cananian 1.1 this.hcf = hcf;
49 cananian 1.1 }
50 cananian 1.1
51 cananian 1.1 public Set<Temp> conditionallySingular(HMethod m, StaticValue<Quad> sv) {
52 cananian 1.3 return mutuallySingular(m, Collections.singleton(sv));
53 cananian 1.1 }
54 cananian 1.1
55 cananian 1.4 // XXX cache this result?
56 cananian 1.1 public Set<Temp> mutuallySingular(HMethod m,
57 cananian 1.1 Collection<StaticValue<Quad>> svs) {
58 cananian 1.3 if (!methodCache.containsKey(m))
59 cananian 1.3 computeSingularity(m);
60 cananian 1.3 assert methodCache.containsKey(m);
61 cananian 1.3 PerMethodInfo pmi = methodCache.get(m);
62 cananian 1.3 Set<StaticValue<Quad>> svsset = new HashSet<StaticValue<Quad>>(svs);
63 cananian 1.3 Set<Temp> result = new TreeSet<Temp>();// compactness?
64 cananian 1.3 // mutually singular iff
65 cananian 1.3 // \forall <v,s> \in svs : RDin[s](v)!=\bot &&
66 cananian 1.3 // {} = (svs \intersect RUin[s][RDin[s](v)])
67 cananian 1.6 for (StaticValue<Quad> sv : svs) {
68 cananian 1.3 assert pmi.rdResult.containsKey(sv.right());
69 cananian 1.3 // first condition.
70 cananian 1.3 Set<DefPoint> dps = pmi.rdResult.get(sv.right()).get(sv.left());
71 cananian 1.3 if (dps==null)
72 cananian 1.3 return null; // this static value is not singular!
73 cananian 1.3 // second condition. first, compute RUin[s] of all dp in dps.
74 cananian 1.6 for (DefPoint dp : dps) {
75 cananian 1.3 Set<StaticValue<Quad>> ru=pmi.ruResult.get(sv.right()).get(dp);
76 cananian 1.3 // check that none are in svs
77 cananian 1.3 for (Iterator<StaticValue<Quad>> it3=ru.iterator();
78 cananian 1.3 it3.hasNext(); )
79 cananian 1.3 if (svsset.contains(it3.next()))
80 cananian 1.3 return null;//not mutually singular with some sv in svs
81 cananian 1.3 // also keep track of P union {dps}
82 cananian 1.3 if (dp.right() instanceof METHOD)
83 cananian 1.3 result.add(dp.left());
84 cananian 1.1 }
85 cananian 1.1 }
86 cananian 1.3 // well, these are mutually singular. Boo-yah!
87 cananian 1.3 return Collections.unmodifiableSet(result);
88 cananian 1.1 }
89 cananian 1.1
90 cananian 1.1 private void computeSingularity(HMethod m) {
91 cananian 1.1 assert !methodCache.containsKey(m);
92 cananian 1.3 QuadFlowGraph qfg = new QuadFlowGraph
93 cananian 1.3 ((harpoon.IR.Quads.Code) hcf.convert(m));
94 cananian 1.3 Map<QNode,RDInfo> rdResult = new RDSolver().compute(qfg);
95 cananian 1.3 Map<QNode,RUInfo> ruResult = new RUSolver(rdResult).compute(qfg);
96 cananian 1.4 // trim these; XXX could be trimmed much further.
97 cananian 1.4 // (for example, I think the only relevant keys are
98 cananian 1.4 // array/field stores and calls, and only the defpoints
99 cananian 1.4 // mentioned in the trimmed-down rdResult's RDInfos are
100 cananian 1.4 // relevant keys in the ruResult's RUInfo.)
101 cananian 1.4 Map<Quad,RDInfo> _rdResult = new TreeMap<Quad,RDInfo>();
102 cananian 1.4 Map<Quad,RUInfo> _ruResult = new TreeMap<Quad,RUInfo>();
103 cananian 1.6 for (QNode qn : qfg.nodes()) {
104 cananian 1.4 if (qn.isPhiEntrance() || qn.isSigmaExit()) continue;
105 cananian 1.4 _rdResult.put(qn.baseQuad(), rdResult.get(qn));
106 cananian 1.4 _ruResult.put(qn.baseQuad(), ruResult.get(qn));
107 cananian 1.4 }
108 cananian 1.4 methodCache.put(m, new PerMethodInfo(_rdResult, _ruResult));
109 cananian 1.1 assert methodCache.containsKey(m);
110 cananian 1.1 }
111 cananian 1.1
112 cananian 1.1 private final Map<HMethod, PerMethodInfo> methodCache =
113 cananian 1.1 new HashMap<HMethod,PerMethodInfo>();
114 cananian 1.1
115 cananian 1.1 static class PerMethodInfo {
116 cananian 1.4 final Map<Quad,RDInfo> rdResult;
117 cananian 1.4 final Map<Quad,RUInfo> ruResult;
118 cananian 1.4 PerMethodInfo(Map<Quad,RDInfo> rdResult, Map<Quad,RUInfo> ruResult) {
119 cananian 1.4 this.rdResult = rdResult; this.ruResult = ruResult;
120 cananian 1.3 }
121 cananian 1.1 }
122 cananian 1.1
123 cananian 1.3 static class DefPoint extends Default.PairList<Temp,Quad> {
124 cananian 1.3 DefPoint(Temp v, Quad def) { super(v, def); }
125 cananian 1.3 }
126 cananian 1.3 static abstract class Info<I extends Info<I,K,V>,K,V> {
127 cananian 1.3 final MapFactory<K,Set<V>> mf;
128 cananian 1.3 final Map<K,Set<V>> map;
129 cananian 1.3 Info(MapFactory<K,Set<V>> mf, Map<K,Set<V>> map) {
130 cananian 1.3 this.mf = mf;
131 cananian 1.3 this.map = map;
132 cananian 1.3 }
133 cananian 1.3 protected abstract I thisInfo();
134 cananian 1.3 protected abstract I newInfo(MapFactory<K,Set<V>> mf, Map<K,Set<V>> map);
135 cananian 1.3 Set<V> get(K k) {
136 cananian 1.3 if (map.containsKey(k)) return map.get(k);
137 cananian 1.3 return Collections.EMPTY_SET;
138 cananian 1.3 }
139 cananian 1.3 I put(K k, Set<V> s) {
140 cananian 1.3 if (s==null || s.size()>0) {
141 cananian 1.3 if (map.containsKey(k) &&
142 cananian 1.3 (s==null ? null==map.get(k) : s.equals(map.get(k))))
143 cananian 1.3 return thisInfo(); // no change necessary.
144 cananian 1.3 I result = newInfo(this.mf, mf.makeMap(this.map));
145 cananian 1.3 result.map.put(k, s);
146 cananian 1.3 return result;
147 cananian 1.3 } else return removeKey(k);
148 cananian 1.3 }
149 cananian 1.3 I removeKey(K k) {
150 cananian 1.3 if (!map.containsKey(k)) return thisInfo();
151 cananian 1.3 I result = newInfo(this.mf, mf.makeMap(this.map));
152 cananian 1.3 result.map.remove(k);
153 cananian 1.3 return result;
154 cananian 1.3 }
155 cananian 1.3 I add(SetFactory<V> sf, K k, V v) {
156 cananian 1.3 Set<V> s = get(k);
157 cananian 1.3 if (s.contains(v)) return thisInfo();
158 cananian 1.3 s = sf.makeSet(s);
159 cananian 1.3 s.add(v);
160 cananian 1.3 return put(k, s);
161 cananian 1.3 }
162 cananian 1.3 public int hashCode() { return map.hashCode(); }
163 cananian 1.3 public boolean equals(Object o) {
164 cananian 1.3 if (this==o) return true;
165 cananian 1.3 if (!(o instanceof Info)) return false;
166 cananian 1.3 return this.map.equals(((Info)o).map);
167 cananian 1.3 }
168 cananian 1.3 }
169 cananian 1.3 static class RDInfo extends Info<RDInfo,Temp,DefPoint> {
170 cananian 1.3 RDInfo(MapFactory<Temp,Set<DefPoint>> mf) {
171 cananian 1.3 this(mf, mf.makeMap());
172 cananian 1.3 }
173 cananian 1.3 private RDInfo(MapFactory<Temp,Set<DefPoint>> mf,
174 cananian 1.3 Map<Temp,Set<DefPoint>> map) {
175 cananian 1.3 super(mf, map);
176 cananian 1.3 }
177 cananian 1.3 protected RDInfo thisInfo() { return this; }
178 cananian 1.3 protected RDInfo newInfo(MapFactory<Temp,Set<DefPoint>> mf,
179 cananian 1.3 Map<Temp,Set<DefPoint>> map) {
180 cananian 1.3 return new RDInfo(mf, map);
181 cananian 1.3 }
182 cananian 1.3 static RDInfo join(MapFactory<Temp,Set<DefPoint>> mf,
183 cananian 1.3 SetFactory<DefPoint> sf,
184 cananian 1.3 RDInfo rd1, RDInfo rd2) {
185 cananian 1.3 RDInfo result = new RDInfo
186 cananian 1.3 (mf, multiMapJoin(mf, sf, rd1.map, rd2.map));
187 cananian 1.3 if (result.equals(rd1)) return rd1; // reuse if possible
188 cananian 1.3 if (result.equals(rd2)) return rd2; // reuse if possible
189 cananian 1.3 return result;
190 cananian 1.3 }
191 cananian 1.3 }
192 cananian 1.3 static class RDSolver extends DataFlowSolver.Forward<QNode,QEdge,RDInfo> {
193 cananian 1.3 MapFactory<Temp,Set<DefPoint>> mf =
194 cananian 1.3 new AggregateMapFactory<Temp,Set<DefPoint>>();
195 cananian 1.3 SetFactory<DefPoint> sf =
196 cananian 1.3 new AggregateSetFactory<DefPoint>();
197 cananian 1.3 RDInfo EMPTY = new RDInfo(mf);
198 cananian 1.3
199 cananian 1.3 // initialize to \q. \v. {} (except for method quad)
200 cananian 1.3 protected RDInfo init(QNode qn) {
201 cananian 1.3 Quad q = qn.baseQuad();
202 cananian 1.3 if (!(q instanceof METHOD)) return EMPTY;
203 cananian 1.3 METHOD m = (METHOD) q;
204 cananian 1.3 RDInfo result = new RDInfo(mf);
205 cananian 1.3 for (int i=0; i<m.paramsLength(); i++)
206 cananian 1.3 result.put(m.params(i),
207 cananian 1.3 Collections.singleton(new DefPoint(m.params(i),m)));
208 cananian 1.3 return result;
209 cananian 1.3 }
210 cananian 1.3 // join rule for RDInfo.
211 cananian 1.3 protected RDInfo join(RDInfo rd1, RDInfo rd2) {
212 cananian 1.3 return RDInfo.join(mf, sf, rd1, rd2);
213 cananian 1.3 }
214 cananian 1.3 protected RDInfo out(QNode qn, RDInfo in) {
215 cananian 1.3 Quad q = qn.baseQuad();
216 cananian 1.3 RDInfo out = in;
217 cananian 1.3 if (qn.isPhiEntrance() || qn.isSigmaExit()) {
218 cananian 1.3 Iterator<Temp> useI = qn.useC().iterator();
219 cananian 1.3 Iterator<Temp> defI = qn.defC().iterator();
220 cananian 1.3 while (useI.hasNext() && defI.hasNext())
221 cananian 1.3 out = doMove(out, defI.next(), useI.next());
222 cananian 1.3 assert !useI.hasNext();
223 cananian 1.3 assert !defI.hasNext();
224 cananian 1.3 } else if (q instanceof MOVE) {
225 cananian 1.3 MOVE move = (MOVE) q;
226 cananian 1.3 out = doMove(out, move.dst(), move.src());
227 cananian 1.3 } else if (q instanceof NEW) {
228 cananian 1.3 NEW n = (NEW) q;
229 cananian 1.3 out = out.put(n.dst(), Collections.singleton
230 cananian 1.3 (new DefPoint(n.dst(), n)));
231 cananian 1.3 } else if (q instanceof ANEW) {
232 cananian 1.3 ANEW n = (ANEW) q;
233 cananian 1.3 out = out.put(n.dst(), Collections.singleton
234 cananian 1.3 (new DefPoint(n.dst(), n)));
235 cananian 1.3 } else {
236 cananian 1.3 for (Iterator<Temp> it=qn.defC().iterator(); it.hasNext(); )
237 cananian 1.3 out = out.put(it.next(), null);
238 cananian 1.1 }
239 cananian 1.3 return out;
240 cananian 1.3 }
241 cananian 1.3 RDInfo doMove(RDInfo in, Temp dst, Temp src) {
242 cananian 1.3 return in.put(dst, in.get(src));
243 cananian 1.3 }
244 cananian 1.3 }
245 cananian 1.3 static class RUInfo extends Info<RUInfo,DefPoint,StaticValue<Quad>> {
246 cananian 1.3 RUInfo(MapFactory<DefPoint,Set<StaticValue<Quad>>> mf) {
247 cananian 1.3 this(mf, mf.makeMap());
248 cananian 1.3 }
249 cananian 1.3 private RUInfo(MapFactory<DefPoint,Set<StaticValue<Quad>>> mf,
250 cananian 1.3 Map<DefPoint,Set<StaticValue<Quad>>> map) {
251 cananian 1.3 super(mf, map);
252 cananian 1.3 }
253 cananian 1.3 protected RUInfo thisInfo() { return this; }
254 cananian 1.3 protected RUInfo newInfo(MapFactory<DefPoint,Set<StaticValue<Quad>>> mf,
255 cananian 1.3 Map<DefPoint,Set<StaticValue<Quad>>> map) {
256 cananian 1.3 return new RUInfo(mf, map);
257 cananian 1.3 }
258 cananian 1.3 static RUInfo join(MapFactory<DefPoint,Set<StaticValue<Quad>>> mf,
259 cananian 1.3 SetFactory<StaticValue<Quad>> sf,
260 cananian 1.3 RUInfo ru1, RUInfo ru2) {
261 cananian 1.3 RUInfo result = new RUInfo
262 cananian 1.3 (mf, multiMapJoin(mf, sf, ru1.map, ru2.map));
263 cananian 1.3 if (result.equals(ru1)) return ru1; // reuse if possible
264 cananian 1.3 if (result.equals(ru2)) return ru2; // reuse if possible
265 cananian 1.3 return result;
266 cananian 1.3 }
267 cananian 1.3 }
268 cananian 1.3 static class RUSolver extends DataFlowSolver.Forward<QNode,QEdge,RUInfo> {
269 cananian 1.3 Map<QNode,RDInfo> rdResult;
270 cananian 1.3 MapFactory<DefPoint,Set<StaticValue<Quad>>> mf =
271 cananian 1.3 new AggregateMapFactory<DefPoint,Set<StaticValue<Quad>>>();
272 cananian 1.3 SetFactory<StaticValue<Quad>> sf =
273 cananian 1.3 new AggregateSetFactory<StaticValue<Quad>>();
274 cananian 1.3 RUInfo EMPTY = new RUInfo(mf);
275 cananian 1.3
276 cananian 1.3 RUSolver(Map<QNode,RDInfo> rdResult) { this.rdResult=rdResult; }
277 cananian 1.3
278 cananian 1.3 // initialize to \q. \sv. {}
279 cananian 1.3 protected RUInfo init(QNode qn) { return EMPTY; }
280 cananian 1.3 // join rule for RUInfo.
281 cananian 1.3 protected RUInfo join(RUInfo ru1, RUInfo ru2) {
282 cananian 1.3 return RUInfo.join(mf, sf, ru1, ru2);
283 cananian 1.3 }
284 cananian 1.3 RDInfo getRD(QNode qn) { assert false:"unimplemented";return null; }
285 cananian 1.3 protected RUInfo out(QNode qn, RUInfo in) {
286 cananian 1.3 Quad q = qn.baseQuad();
287 cananian 1.3 RUInfo out = in;
288 cananian 1.3 if (qn.isPhiEntrance() || qn.isSigmaExit() ||
289 cananian 1.3 q instanceof MOVE) {
290 cananian 1.3 // out = in.
291 cananian 1.3 } else {
292 cananian 1.3 // use QNode's useC/defC for CALL/TYPESWITCH/SWITCH/CJMP
293 cananian 1.3 RDInfo rd = rdResult.get(qn);
294 cananian 1.3 // first, gen for uses.
295 cananian 1.6 for (Temp u : qn.useC()) {
296 cananian 1.3 Set<DefPoint> s = rd.get(u);
297 cananian 1.3 if (s!=null)
298 cananian 1.6 for (DefPoint dp : s) {
299 cananian 1.3 out = out.add(sf, dp, new StaticValue<Quad>(u, q));
300 cananian 1.3 }
301 cananian 1.3 }
302 cananian 1.3 // last, kill for defs.
303 cananian 1.3 for (Iterator<Temp> it=qn.defC().iterator(); it.hasNext(); )
304 cananian 1.3 out = out.removeKey(new DefPoint(it.next(), q));
305 cananian 1.1 }
306 cananian 1.3 return out;
307 cananian 1.3 }
308 cananian 1.3 }
309 cananian 1.3
310 cananian 1.3 private static <V> Set<V> union(SetFactory<V> sf, Set<V> s1, Set<V> s2) {
311 cananian 1.3 // try to reuse sets.
312 cananian 1.3 if (s1.size()==0) return s2;
313 cananian 1.3 if (s2.size()==0) return s1;
314 cananian 1.3 // XXX these tests are slow =(
315 cananian 1.3 if (s1.containsAll(s2)) return s1;
316 cananian 1.3 if (s2.containsAll(s1)) return s2;
317 cananian 1.3 // okay, have to create new set.
318 cananian 1.3 Set<V> result = sf.makeSet(s1); result.addAll(s2);
319 cananian 1.3 return result;
320 cananian 1.3 }
321 cananian 1.3 private static <K,V> Map<K,Set<V>> multiMapJoin(MapFactory<K,Set<V>> mf,
322 cananian 1.3 SetFactory<V> sf,
323 cananian 1.3 Map<K,Set<V>> m1,
324 cananian 1.3 Map<K,Set<V>> m2) {
325 cananian 1.3 Map<K,Set<V>> result = mf.makeMap(m1);
326 cananian 1.6 for (K key : m2.keySet()) {
327 cananian 1.3 Set<V> s1 = result.get(key);
328 cananian 1.3 Set<V> s2 = m2.get(key);
329 cananian 1.3 assert m2.containsKey(key);
330 cananian 1.3 if (!result.containsKey(key))
331 cananian 1.3 result.put(key, s2);
332 cananian 1.3 else if (s1==null || s2==null)
333 cananian 1.3 result.put(key, null); // bottom.
334 cananian 1.3 else
335 cananian 1.3 result.put(key, union(sf, s1, s2));
336 cananian 1.1 }
337 cananian 1.3 if (result.equals(m1)) return m1; // reuse maps if possible
338 cananian 1.3 if (result.equals(m2)) return m2; // reuse maps if possible.
339 cananian 1.3 return result;
340 cananian 1.1 }
341 cananian 1.1 }