1 cananian 1.1.2.1 // ToTreeHelpers.java, created Fri Feb 11 15:11:20 2000 by cananian
2 cananian 1.1.2.1 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.IR.Tree;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.ReachingDefs;
7 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
8 cananian 1.1.2.1 import harpoon.ClassFile.HCodeEdge;
9 cananian 1.1.2.1 import harpoon.ClassFile.HCodeElement;
10 cananian 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
11 cananian 1.1.2.1 import harpoon.IR.Properties.UseDefer;
12 cananian 1.1.2.4 import harpoon.IR.Quads.PHI;
13 cananian 1.1.2.3 import harpoon.IR.Quads.MONITORENTER;
14 cananian 1.1.2.3 import harpoon.IR.Quads.MONITOREXIT;
15 cananian 1.1.2.4 import harpoon.IR.Quads.SIGMA;
16 cananian 1.1.2.3 import harpoon.IR.Quads.Quad;
17 cananian 1.1.2.3 import harpoon.IR.LowQuad.PCALL;
18 cananian 1.1.2.8 import harpoon.IR.LowQuad.PGET;
19 cananian 1.1.2.3 import harpoon.IR.LowQuad.PSET;
20 cananian 1.1.2.1 import harpoon.Temp.Temp;
21 cananian 1.6 import net.cscott.jutil.BinaryHeap;
22 cananian 1.6 import net.cscott.jutil.BinomialHeap;
23 cananian 1.6 import net.cscott.jutil.FibonacciHeap;
24 cananian 1.6 import net.cscott.jutil.Heap;
25 cananian 1.6 import net.cscott.jutil.Environment;
26 cananian 1.6 import net.cscott.jutil.HashEnvironment;
27 cananian 1.1.2.1 import harpoon.Util.Util;
28 cananian 1.1.2.1
29 cananian 1.1.2.4 import java.util.ArrayList;
30 cananian 1.1.2.4 import java.util.Arrays;
31 cananian 1.1.2.1 import java.util.Collections;
32 cananian 1.1.2.1 import java.util.HashMap;
33 cananian 1.1.2.3 import java.util.HashSet;
34 cananian 1.1.2.1 import java.util.Iterator;
35 cananian 1.1.2.1 import java.util.Map;
36 cananian 1.1.2.1 import java.util.Set;
37 cananian 1.1.2.1 /**
38 cananian 1.1.2.1 * <code>ToTreeHelpers</code>
39 cananian 1.1.2.1 *
40 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
41 cananian 1.6 * @version $Id: ToTreeHelpers.java,v 1.6 2004/02/08 01:55:51 cananian Exp $
42 cananian 1.1.2.1 */
43 cananian 1.1.2.1 abstract class ToTreeHelpers {
44 cananian 1.1.2.1 //------------ EdgeOracle IMPLEMENTATIONS ------------------
45 cananian 1.1.2.1
46 cananian 1.1.2.1 /** The <code>DefaultEdgeOracle</code> always follows the zeroth
47 cananian 1.1.2.1 * outgoing edge. Very simple. */
48 cananian 1.1.2.1 static class DefaultEdgeOracle implements ToTree.EdgeOracle {
49 cananian 1.1.2.1 DefaultEdgeOracle() { }
50 cananian 1.1.2.1 public int defaultEdge(HCodeElement hce) { return 0; }
51 cananian 1.1.2.9 }
52 cananian 1.1.2.9 /** The <code>SourceSimilarEdgeOracle</code> tries to lay out code
53 cananian 1.1.2.9 * in the same order as in the original java file, when it has the
54 cananian 1.1.2.9 * information to do so. Otherwide, it falls back on a provided
55 cananian 1.1.2.9 * default edge oracle. */
56 cananian 1.1.2.9 static class SourceSimilarEdgeOracle implements ToTree.EdgeOracle {
57 cananian 1.1.2.9 final CFGrapher cfg;
58 cananian 1.1.2.9 final ToTree.EdgeOracle eo;
59 cananian 1.1.2.9 SourceSimilarEdgeOracle(ToTree.EdgeOracle eo) {
60 cananian 1.1.2.9 this(CFGrapher.DEFAULT, eo);
61 cananian 1.1.2.9 }
62 cananian 1.1.2.9 SourceSimilarEdgeOracle(CFGrapher cfg, ToTree.EdgeOracle eo) {
63 cananian 1.1.2.9 this.cfg = cfg;
64 cananian 1.1.2.9 this.eo = eo;
65 cananian 1.1.2.9 }
66 cananian 1.1.2.9 public int defaultEdge(HCodeElement hce) {
67 cananian 1.5 HCodeEdge[] succ = (HCodeEdge[]) cfg.succC(hce).toArray(new HCodeEdge[0]);
68 cananian 1.1.2.9 int ln[] = new int[succ.length];
69 cananian 1.1.2.9 for (int i=0; i<succ.length; i++)
70 cananian 1.1.2.9 ln[i] = succ[i].to().getLineNumber();
71 cananian 1.1.2.9 if (ln.length>0) {
72 cananian 1.1.2.9 int min = 0;
73 cananian 1.1.2.9 boolean ismin = true;
74 cananian 1.1.2.9 for (int i=1; i<ln.length; i++) {
75 cananian 1.1.2.9 if (ln[i] == ln[min])
76 cananian 1.1.2.9 ismin=false;
77 cananian 1.1.2.9 else if (ln[i] < ln[min]) { min=i; ismin=true; }
78 cananian 1.1.2.9 }
79 cananian 1.1.2.9 if (ismin) return min;
80 cananian 1.1.2.9 }
81 cananian 1.1.2.9 // no clear guidance. fall back.
82 cananian 1.1.2.9 return eo.defaultEdge(hce);
83 cananian 1.1.2.9 }
84 cananian 1.1.2.1 }
85 cananian 1.1.2.1
86 cananian 1.1.2.1 /** The <code>MinMaxEdgeOracle</code> lays code out according to the
87 cananian 1.1.2.1 * computed shortest paths to the footer. That is, it computes
88 cananian 1.1.2.1 * an approximation to the single-source longest paths problem
89 cananian 1.1.2.1 * and tries to lay out code such that the longest paths in the
90 cananian 1.1.2.1 * method have no branches. Since LONGEST-PATH is NP-complete,
91 cananian 1.1.2.1 * this class actual sets the default successor edge to be the
92 cananian 1.1.2.1 * one which has the longest shortest path to the footer.
93 cananian 1.1.2.1 * <p>
94 cananian 1.1.2.1 * See Karger, Motwani, and Ramkumar, "On Approximating the Longest
95 cananian 1.1.2.1 * Path in a Graph" in <i>Algorithmica</i> 1997 18:82-98; and
96 cananian 1.1.2.1 * Young, Johnson, Karger, and Smith, "Near-optimal intraprocedural
97 cananian 1.1.2.1 * Branch Alignment" in PLDI'97 for some tangentially-related work.
98 cananian 1.1.2.1 *
99 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
100 cananian 1.1.2.1 */
101 cananian 1.1.2.1 static class MinMaxEdgeOracle implements ToTree.EdgeOracle {
102 cananian 1.1.2.1 final CFGrapher cfg;
103 cananian 1.1.2.1 /** Convenience constructor. */
104 cananian 1.1.2.1 MinMaxEdgeOracle(HCode hc) { this(hc, CFGrapher.DEFAULT); }
105 cananian 1.1.2.1 /** Compute single-source shortest paths on edge-reversed graph,
106 cananian 1.1.2.1 * using the technique of CLR, 25.2 (Dijkstra's algorithm).
107 cananian 1.1.2.1 * Uses a binomial heap, for an O(E lg V) runtime. If we're
108 cananian 1.1.2.1 * feeling bored, we could use a fibonacci heap instead for
109 cananian 1.1.2.1 * an O(V lg V + E) runtime. I don't think the difference is
110 cananian 1.1.2.1 * enough to care about. */
111 cananian 1.1.2.1 MinMaxEdgeOracle(HCode hc, CFGrapher cfg) {
112 cananian 1.1.2.1 this.cfg = cfg;
113 cananian 1.1.2.1 // get the 'single-source', which is the unique FOOTER node.
114 cananian 1.3.2.1 assert hc.getLeafElements().length==1;
115 cananian 1.1.2.1 HCodeElement s = hc.getLeafElements()[0];
116 cananian 1.1.2.1 // we're going to need a mapping from HCodeElements to Map.Entry's
117 cananian 1.1.2.1 Map m = new HashMap();
118 cananian 1.1.2.1 // make the priority queue, and initialize it.
119 cananian 1.1.2.3 Heap Q = new BinaryHeap(); // new FibonacciHeap();
120 cananian 1.1.2.1 for (Iterator it=hc.getElementsI(); it.hasNext(); ) {
121 cananian 1.1.2.1 HCodeElement hce = (HCodeElement) it.next();
122 cananian 1.1.2.1 // d[v] = infinity.
123 cananian 1.1.2.1 Map.Entry entry= Q.insert(new Integer(Integer.MAX_VALUE), hce);
124 cananian 1.1.2.1 // don't forget entry-to-hce correlation.
125 cananian 1.1.2.1 m.put(hce, entry);
126 cananian 1.1.2.1 }
127 cananian 1.1.2.1 // INITIALIZE-SINGLE-SOURCE by lowering source to 0.
128 cananian 1.1.2.1 set_d(s, 0, Q, m);
129 cananian 1.1.2.1 // now do Dijkstra's algorithm.
130 cananian 1.1.2.1 while (!Q.isEmpty()) {
131 cananian 1.1.2.1 HCodeElement u = (HCodeElement) Q.extractMinimum().getValue();
132 cananian 1.1.2.1 for (Iterator it=cfg.predC(u).iterator(); it.hasNext(); ) {
133 cananian 1.1.2.1 HCodeElement v = ((HCodeEdge) it.next()).from();
134 cananian 1.1.2.1 // RELAX step.
135 cananian 1.1.2.1 if (d(v) > (d(u)+1))
136 cananian 1.1.2.1 set_d(v, d(u)+1, Q, m);
137 cananian 1.1.2.1 }
138 cananian 1.1.2.1 }
139 cananian 1.1.2.1 // Look, Ma! d[v] is loaded & ready to go!
140 cananian 1.1.2.1 }
141 cananian 1.1.2.1 /** Path weights mapping. */
142 cananian 1.1.2.1 final Map d = new HashMap();
143 cananian 1.1.2.1 // convenience functions for working with the path weights.
144 cananian 1.1.2.1 private int d(HCodeElement v) {
145 cananian 1.1.2.1 if (!d.containsKey(v)) return Integer.MAX_VALUE;
146 cananian 1.1.2.1 return ((Integer)d.get(v)).intValue();
147 cananian 1.1.2.1 }
148 cananian 1.1.2.2 private void set_d(HCodeElement v, int k, Heap Q, Map m) {
149 cananian 1.3.2.1 assert d(v) > k;
150 cananian 1.3.2.1 assert ((Map.Entry)m.get(v)).getKey()
151 cananian 1.3.2.1 .equals(new Integer(d(v)));
152 cananian 1.1.2.1 d.put(v, new Integer(k));
153 cananian 1.1.2.1 Q.decreaseKey((Map.Entry)m.get(v), new Integer(k));
154 cananian 1.3.2.1 assert ((Map.Entry)m.get(v)).getKey()
155 cananian 1.3.2.1 .equals(new Integer(d(v)));
156 cananian 1.1.2.1 }
157 cananian 1.1.2.1 /** defaultEdge corresponds to the edge with largest shortest path */
158 cananian 1.1.2.1 public int defaultEdge(HCodeElement hce) {
159 cananian 1.5 HCodeEdge[] succ = (HCodeEdge[]) cfg.succC(hce).toArray(new HCodeEdge[0]);
160 cananian 1.1.2.1 // hacks for SWITCH & other common cases.
161 cananian 1.1.2.1 if (succ.length!=2) return 0;
162 cananian 1.1.2.1 int maxedge=0, maxscore=d(succ[0].to());
163 cananian 1.1.2.1 for (int i=1; i<succ.length; i++) {
164 cananian 1.1.2.1 int score = d(succ[i].to());
165 cananian 1.1.2.1 if (score > maxscore) {
166 cananian 1.1.2.1 maxedge=i; maxscore=score;
167 cananian 1.1.2.1 }
168 cananian 1.1.2.1 }
169 cananian 1.1.2.1 return maxedge;
170 cananian 1.1.2.1 }
171 cananian 1.1.2.1 }
172 cananian 1.1.2.1
173 cananian 1.1.2.1 //------------ FoldNanny IMPLEMENTATIONS ------------------
174 cananian 1.1.2.1 static class DefaultFoldNanny implements ToTree.FoldNanny {
175 cananian 1.1.2.1 DefaultFoldNanny() { }
176 cananian 1.1.2.1 public boolean canFold(HCodeElement hce, Temp t) { return false; }
177 cananian 1.1.2.3 }
178 cananian 1.1.2.6 static class SSXSimpleFoldNanny implements ToTree.FoldNanny {
179 cananian 1.1.2.8 // Set to 'false' to enable foldings which break derived types.
180 cananian 1.1.2.8 final private static boolean RESTRICT_DERIVED_TYPES = true;
181 cananian 1.1.2.3 final Set safe = new HashSet();
182 cananian 1.1.2.6 SSXSimpleFoldNanny(HCode hc) {
183 cananian 1.1.2.3 // first, find all the single-use variables
184 cananian 1.1.2.3 HashSet singleUse = new HashSet(), multiUse = new HashSet();
185 cananian 1.1.2.3 for (Iterator it = hc.getElementsI(); it.hasNext(); ) {
186 cananian 1.1.2.3 Quad q = (Quad) it.next();
187 cananian 1.1.2.4 // SIGMAs count multiple times... (see uses() method)
188 cananian 1.1.2.4 for (Iterator it2 = uses(q); it2.hasNext(); ) {
189 cananian 1.1.2.3 Temp t = (Temp) it2.next();
190 cananian 1.1.2.3 if (multiUse.contains(t)) continue;
191 cananian 1.1.2.3 if (singleUse.contains(t)) {
192 cananian 1.1.2.3 multiUse.add(t); singleUse.remove(t);
193 cananian 1.1.2.3 } else singleUse.add(t);
194 cananian 1.1.2.3 }
195 cananian 1.1.2.3 }
196 cananian 1.1.2.3 multiUse = null;
197 cananian 1.1.2.3 // now filter the safe set.
198 cananian 1.1.2.3 // we don't want anything folded which is live over a memory
199 cananian 1.1.2.3 // store or a synchronization. we're going to be a bit
200 cananian 1.1.2.3 // conservative here.
201 cananian 1.1.2.8 // ALSO: we need to be careful about derived types.
202 cananian 1.1.2.3 dfs((Quad)hc.getRootElement(), new HashSet(),
203 cananian 1.1.2.3 new HashEnvironment(), singleUse);
204 cananian 1.1.2.3 // done!
205 cananian 1.1.2.3 //System.err.print("[FOLDING: "+safe+"]");
206 cananian 1.1.2.3 }
207 cananian 1.1.2.3 void dfs(Quad q, Set seen, Environment reachingDefs, Set singleUse) {
208 cananian 1.3.2.1 assert !seen.contains(q);
209 cananian 1.1.2.3 seen.add(q);
210 cananian 1.1.2.3 { // if def reached this use, add to safe set.
211 cananian 1.1.2.3 Temp[] use = q.use();
212 cananian 1.1.2.3 for (int i=0; i<use.length; i++)
213 cananian 1.1.2.3 if (reachingDefs.containsKey(use[i]))
214 cananian 1.1.2.3 safe.add(use[i]); // reaching def means its safe.
215 cananian 1.1.2.3 }
216 cananian 1.1.2.4 if (isBarrier(q)) {
217 cananian 1.1.2.4 // stores and syncs clear the defs
218 cananian 1.1.2.4 reachingDefs.clear();
219 cananian 1.1.2.3 }
220 cananian 1.1.2.4 if (!isUnfoldableDef(q)) {
221 cananian 1.1.2.4 // add environment entries for all appropriate defs
222 cananian 1.1.2.3 Temp[] def = q.def();
223 cananian 1.1.2.3 for (int i=0; i<def.length; i++)
224 cananian 1.1.2.3 if (singleUse.contains(def[i]))
225 cananian 1.1.2.4 reachingDefs.put(def[i], def[i]);
226 cananian 1.1.2.3 }
227 cananian 1.1.2.3 { // recurse.
228 cananian 1.1.2.3 Quad[] next = q.next();
229 cananian 1.1.2.3 Environment.Mark m = reachingDefs.getMark();
230 cananian 1.1.2.3 for (int i=0; i<next.length; i++) {
231 cananian 1.1.2.3 if (!seen.contains(next[i])) {
232 cananian 1.1.2.3 dfs(next[i], seen, reachingDefs, singleUse);
233 cananian 1.1.2.3 reachingDefs.undoToMark(m);
234 cananian 1.1.2.3 }
235 cananian 1.1.2.3 }
236 cananian 1.1.2.3 }
237 cananian 1.1.2.3 }
238 cananian 1.1.2.8 // the folded expression BINOP<p>(+, CONST(x), PGET(y)) is untypeable
239 cananian 1.1.2.8 // in our system, because derived types must reference a base pointer
240 cananian 1.1.2.8 // IN A TEMPORARY -- we can't represent bases in memory. So to be
241 cananian 1.1.2.8 // safe (if a bit conservative) we don't fold non-primitive fetches
242 cananian 1.1.2.8 // (PGETs).
243 cananian 1.1.2.4 public static boolean isUnfoldableDef(Quad q) {
244 cananian 1.1.2.4 if (q instanceof PCALL) return true; // CALLS CAN NOT BE FOLDED
245 cananian 1.1.2.8 if (q instanceof PGET && !((PGET)q).type().isPrimitive() &&
246 cananian 1.1.2.8 RESTRICT_DERIVED_TYPES) return true; // MAY BE UNTYPEABLE
247 cananian 1.1.2.4 if (q instanceof PHI) return true; // multiple definitions
248 cananian 1.1.2.4 return false;
249 cananian 1.1.2.4 }
250 cananian 1.1.2.3 public static boolean isBarrier(Quad q) {
251 cananian 1.1.2.3 // ASET,CALL,SET are Quad-only. We only deal with LowQuads here
252 cananian 1.1.2.3 if (q instanceof MONITORENTER || q instanceof MONITOREXIT ||
253 cananian 1.1.2.5 q instanceof PCALL || q instanceof PSET) return true;
254 cananian 1.1.2.5 return false;
255 cananian 1.1.2.4 }
256 cananian 1.1.2.4 public Iterator uses(Quad q) {
257 cananian 1.1.2.4 if (q instanceof SIGMA) return uses((SIGMA)q);
258 cananian 1.1.2.4 else return q.useC().iterator();
259 cananian 1.1.2.4 }
260 cananian 1.1.2.4 public Iterator uses(SIGMA q) {
261 cananian 1.1.2.4 ArrayList al = new ArrayList(q.useC());
262 cananian 1.1.2.4 // add in multiple copies of quads used by sigma functions
263 cananian 1.1.2.4 for (int i=1; i<q.nextLength(); i++)
264 cananian 1.1.2.4 al.addAll(Arrays.asList(q.src()));
265 cananian 1.1.2.4 return al.iterator();
266 cananian 1.1.2.3 }
267 cananian 1.1.2.3 public boolean canFold(HCodeElement hce, Temp t) {
268 cananian 1.1.2.3 return safe.contains(t);
269 cananian 1.1.2.3 }
270 cananian 1.1.2.1 }
271 cananian 1.2 }