1 cananian 1.1.2.1 // SSIRename.java, created Fri Aug 27 17:58:00 1999 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1999 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.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.11 import harpoon.Analysis.AllocationInformationMap;
7 cananian 1.5 import harpoon.Analysis.Liveness;
8 cananian 1.1.2.1 import harpoon.Analysis.Place;
9 cananian 1.1.2.10 import harpoon.Analysis.Maps.AllocationInformation;
10 cananian 1.1.2.10 import harpoon.Analysis.Maps.Derivation;
11 cananian 1.1.2.7 import harpoon.Analysis.Quads.QuadLiveness;
12 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
13 cananian 1.1.2.1 import harpoon.ClassFile.HCodeEdge;
14 cananian 1.1.2.1 import harpoon.ClassFile.HCodeElement;
15 bdemsky 1.1.2.16 import harpoon.ClassFile.HClass;
16 cananian 1.1.2.6 import harpoon.IR.Properties.CFGraphable;
17 cananian 1.1.2.12 import harpoon.IR.LowQuad.DerivationMap;
18 cananian 1.1.2.9 import harpoon.IR.LowQuad.PCALL;
19 cananian 1.1.2.1 import harpoon.Temp.Temp;
20 cananian 1.1.2.1 import harpoon.Temp.TempFactory;
21 cananian 1.1.2.1 import harpoon.Temp.TempMap;
22 cananian 1.1.2.1 import harpoon.Temp.WritableTempMap;
23 cananian 1.5 import net.cscott.jutil.Environment;
24 cananian 1.5 import net.cscott.jutil.HashEnvironment;
25 bdemsky 1.1.2.16 import harpoon.Util.HClassUtil;
26 cananian 1.1.2.1 import harpoon.Util.Util;
27 cananian 1.5 import net.cscott.jutil.WorkSet;
28 bdemsky 1.1.2.16 import harpoon.Util.DataStructs.RelationImpl;
29 cananian 1.1.2.1
30 cananian 1.1.2.2 import java.util.Arrays;
31 cananian 1.1.2.2 import java.util.Collections;
32 cananian 1.1.2.1 import java.util.HashMap;
33 cananian 1.1.2.1 import java.util.HashSet;
34 cananian 1.1.2.1 import java.util.Iterator;
35 cananian 1.1.2.1 import java.util.LinkedList;
36 cananian 1.1.2.1 import java.util.Map;
37 cananian 1.1.2.1 import java.util.Set;
38 cananian 1.1.2.3 import java.util.Stack;
39 bdemsky 1.1.2.16
40 cananian 1.1.2.1 /**
41 cananian 1.1.2.1 * <code>SSIRename</code> is a new, improved, fast SSI-renaming
42 cananian 1.1.2.1 * algorithm. Detailed in the author's thesis. This Java version
43 cananian 1.1.2.1 * is hairy because of the big "efficiency-vs-immutable quads" fight.
44 cananian 1.1.2.12 * Also, we have to keep <code>Derivation</code>s and
45 cananian 1.1.2.12 * <code>AllocationInformation</code> up-to-date.
46 cananian 1.1.2.12 * XXX: DERIVATION INFORMATION FOR PHI/SIGMAS IS CURRENTLY LOST. [CSA]
47 cananian 1.1.2.1 *
48 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
49 cananian 1.6 * @version $Id: SSIRename.java,v 1.6 2004/02/08 03:21:24 cananian Exp $
50 cananian 1.1.2.1 */
51 cananian 1.1.2.9 public class SSIRename {
52 cananian 1.1.2.13 private static final boolean DEBUG = false;
53 cananian 1.1.2.2 private static final boolean sort_phisig = false;
54 cananian 1.1.2.10 // RETURN TUPLE FOR THE ALGORITHM
55 cananian 1.1.2.10 /** New root element (of the SSI-form graph) */
56 cananian 1.1.2.10 public final Quad rootQuad;
57 cananian 1.1.2.10 /** Map from old no-ssa temps to new ssi temps (incomplete). */
58 cananian 1.1.2.10 public final TempMap tempMap;
59 cananian 1.1.2.10 /** Map from old no-ssa quads to new ssi quads. */
60 cananian 1.5 public final Map<Quad,Quad> quadMap;
61 cananian 1.1.2.10 /** <code>AllocationInformation</code> for the new quads, or
62 cananian 1.1.2.10 * <code>null</code> if no allocation information for the old
63 cananian 1.1.2.10 * quads was supplied. */
64 cananian 1.5 public final AllocationInformation<Quad> allocInfo;
65 cananian 1.1.2.10 /** <code>Derivation</code> for the new quads, or <code>null</code>
66 cananian 1.1.2.10 * if no <code>Derivation</code> for the old quads was supplied. */
67 cananian 1.5 public final Derivation<Quad> derivation;
68 cananian 1.1.2.10
69 cananian 1.1.2.1 /** Return a copy of the given quad graph properly converted to
70 cananian 1.1.2.1 * SSI form. */
71 cananian 1.1.2.10 public SSIRename(final Code c, final QuadFactory nqf) {
72 cananian 1.1.2.11 final SearchState S = new SearchState(c, nqf,
73 cananian 1.1.2.12 c.getDerivation(),
74 cananian 1.1.2.11 c.getAllocationInformation());
75 cananian 1.5 this.rootQuad = S.old2new.get(c.getRootElement());
76 cananian 1.1.2.10 this.tempMap = S.varmap;
77 cananian 1.1.2.10 this.quadMap = S.old2new;
78 cananian 1.1.2.11 this.allocInfo = S.naim;
79 cananian 1.1.2.12 this.derivation = S.nderiv;
80 cananian 1.1.2.8 }
81 cananian 1.1.2.11
82 cananian 1.1.2.1 static class VarMap implements TempMap {
83 cananian 1.1.2.1 final TempFactory tf;
84 cananian 1.5 final Environment<Temp,Temp> vm = new HashEnvironment<Temp,Temp>();
85 cananian 1.1.2.1 Temp get(Temp t) {
86 cananian 1.1.2.1 if (!vm.containsKey(t)) { vm.put(t, t.clone(tf)); }
87 cananian 1.5 return vm.get(t);
88 cananian 1.1.2.1 }
89 cananian 1.1.2.1 Temp inc(Temp t) {
90 cananian 1.1.2.1 if (!vm.containsKey(t)) { vm.put(t, t.clone(tf)); }
91 cananian 1.1.2.1 else { vm.put(t, get(t).clone()); }
92 cananian 1.1.2.1 return get(t);
93 cananian 1.1.2.1 }
94 cananian 1.1.2.3 // environment interface.
95 cananian 1.5 Stack<Environment.Mark> s = new Stack<Environment.Mark>();
96 cananian 1.1.2.3 void beginScope() { s.push(vm.getMark()); }
97 cananian 1.5 void endScope() { vm.undoToMark(s.pop()); }
98 cananian 1.1.2.3
99 cananian 1.1.2.1 public Temp tempMap(Temp t) { return get(t); }
100 cananian 1.1.2.1 VarMap(TempFactory tf) { this.tf = tf; }
101 cananian 1.1.2.1 }
102 cananian 1.1.2.1
103 cananian 1.1.2.1 static class SearchState {
104 cananian 1.1.2.1 /** maps no-ssi quads to ssi quads */
105 cananian 1.5 final Map<Quad,Quad> old2new = new HashMap<Quad,Quad>();
106 cananian 1.1.2.1 /** shows where to place phi/sigs */
107 cananian 1.1.2.1 final Place place;
108 cananian 1.1.2.1 /** QuadFactory to use for new Quads. */
109 cananian 1.1.2.1 final QuadFactory nqf;
110 cananian 1.1.2.11 /** AllocationInformation for old Quads */
111 cananian 1.5 final AllocationInformation<Quad> oaim;
112 cananian 1.1.2.11 /** AllocationInformationMap for new Quads */
113 cananian 1.5 final AllocationInformationMap<Quad> naim;
114 cananian 1.1.2.12 /** Derivation for old Quads */
115 cananian 1.5 final Derivation<Quad> oderiv;
116 cananian 1.1.2.11 /** Derivation map for new Quads */
117 cananian 1.5 final DerivationMap<Quad> nderiv;
118 bdemsky 1.1.2.16 /** Derivation map for Sigma/Phis */
119 cananian 1.5 final Map<Temp,DerivType> derivmap;
120 cananian 1.1.2.1 // algorithm state
121 cananian 1.1.2.1 /** maps old variables to new variables */
122 cananian 1.1.2.1 final VarMap varmap;
123 cananian 1.1.2.3 /** edge stack to unroll dfs recursion. */
124 cananian 1.5 final Stack<Edge> We = new Stack<Edge>();
125 cananian 1.1.2.1 /** mark edges as we visit them */
126 cananian 1.5 final Set<Edge> marked = new HashSet<Edge>();
127 cananian 1.1.2.1
128 cananian 1.5 SearchState(HCode<Quad> c, QuadFactory nqf,
129 cananian 1.5 Derivation<Quad> oderiv, AllocationInformation<Quad> oaim){
130 cananian 1.5 this.place = new Place(c, (Liveness) new QuadLiveness(c));
131 cananian 1.1.2.1 this.varmap= new VarMap(nqf.tempFactory());
132 cananian 1.1.2.1 this.nqf = nqf;
133 cananian 1.1.2.11 this.oaim = oaim;
134 cananian 1.5 this.naim = (oaim==null) ? null : new AllocationInformationMap<Quad>();
135 cananian 1.1.2.12 this.oderiv= oderiv;
136 cananian 1.5 this.nderiv= (oderiv==null) ? null : new DerivationMap<Quad>();
137 cananian 1.5 this.derivmap= (oderiv==null) ? null : new HashMap<Temp,DerivType>();
138 cananian 1.1.2.1 setup(c);
139 cananian 1.1.2.1
140 cananian 1.6 for (Edge e : c.getRootElement().edgeC()) {
141 cananian 1.5 We.push(e);
142 cananian 1.5 }
143 cananian 1.1.2.1
144 cananian 1.1.2.1 while (!We.isEmpty()) {
145 cananian 1.5 Edge e = We.pop();
146 cananian 1.1.2.3 if (e==null) { varmap.endScope(); continue; }
147 cananian 1.1.2.3 We.push(null); varmap.beginScope();
148 cananian 1.1.2.1 search(e);
149 cananian 1.1.2.1 }
150 cananian 1.1.2.1
151 cananian 1.1.2.1 makePhiSig(c);
152 bdemsky 1.1.2.16 if (nderiv!=null)
153 bdemsky 1.1.2.16 fixPhiSigDeriv(c);
154 cananian 1.1.2.1
155 cananian 1.1.2.1 // now link edges
156 cananian 1.5 for (Iterator<Quad> it=c.getElementsI(); it.hasNext(); ) {
157 cananian 1.5 Quad q = it.next();
158 cananian 1.5 Quad fr = old2new.get(q);
159 cananian 1.1.2.1 for (int i = 0; i < q.nextLength(); i++) {
160 cananian 1.1.2.1 Edge e = q.nextEdge(i);
161 cananian 1.5 Quad to = old2new.get(e.to());
162 cananian 1.1.2.1 Quad.addEdge(fr, e.which_succ(), to, e.which_pred());
163 cananian 1.1.2.1 }
164 cananian 1.1.2.13 // check for unreachable code.
165 cananian 1.1.2.13 for (int i = 0; i < q.prevLength(); i++)
166 cananian 1.3.2.1 assert old2new.get(q.prev(i))!=null : (!DEBUG ? "unreachable predecessor" :
167 cananian 1.1.2.13 i+"th predecessor of "+q+" is unreachable");
168 cananian 1.1.2.1 }
169 cananian 1.1.2.1 }
170 cananian 1.1.2.1
171 cananian 1.1.2.4 final Map lhs = new HashMap();//lhs of phi/sigma
172 cananian 1.1.2.4 final Map rhs = new HashMap();//rhs of phi/sigma
173 cananian 1.1.2.4 final Map arg = new HashMap();//uses in a sigma
174 cananian 1.1.2.4 final Map sdf = new HashMap();//defs in a sigma
175 cananian 1.1.2.1 void setup(HCode c) {
176 cananian 1.1.2.1 for (Iterator it=c.getElementsI(); it.hasNext(); ) {
177 cananian 1.1.2.1 Quad q = (Quad) it.next();
178 cananian 1.1.2.1 if (q instanceof PHI) {
179 cananian 1.1.2.1 Temp[] l = place.phiNeeded(q);
180 cananian 1.1.2.2 if (sort_phisig) Collections.sort(Arrays.asList(l));
181 cananian 1.1.2.1 Temp[][] r = new Temp[l.length][((PHI)q).arity()];
182 cananian 1.1.2.1 for (int i = 0; i < r.length; i++)
183 cananian 1.1.2.1 for (int j = 0; j < r[i].length; j++)
184 cananian 1.1.2.1 r[i][j] = l[i];
185 cananian 1.1.2.1 lhs.put(q, l);
186 cananian 1.1.2.1 rhs.put(q, r);
187 cananian 1.1.2.1 } else if (q instanceof SIGMA) {
188 cananian 1.1.2.1 Temp[] r = place.sigNeeded(q);
189 cananian 1.1.2.2 if (sort_phisig) Collections.sort(Arrays.asList(r));
190 cananian 1.1.2.1 Temp[][] l = new Temp[r.length][((SIGMA)q).arity()];
191 cananian 1.1.2.1 for (int i = 0; i < l.length; i++)
192 cananian 1.1.2.1 for (int j = 0; j < l[i].length; j++)
193 cananian 1.1.2.1 l[i][j] = r[i];
194 cananian 1.1.2.1 lhs.put(q, l);
195 cananian 1.1.2.1 rhs.put(q, r);
196 cananian 1.1.2.1 }
197 cananian 1.1.2.1 }
198 cananian 1.1.2.1 }
199 cananian 1.1.2.1
200 cananian 1.1.2.1 final WritableTempMap wtm = new WritableTempMap() {
201 cananian 1.5 final Map<Temp,Temp> backing = new HashMap();
202 cananian 1.5 public Temp tempMap(Temp t) { return backing.get(t); }
203 cananian 1.1.2.1 public void associate(Temp o, Temp n) { backing.put(o,n); }
204 cananian 1.1.2.1 };
205 cananian 1.1.2.1 void search(Edge e) {
206 cananian 1.3.2.1 assert e.from() instanceof PHI ||
207 cananian 1.1.2.1 e.from() instanceof SIGMA ||
208 cananian 1.3.2.1 e.from() instanceof HEADER;
209 cananian 1.1.2.3 // handle dfs bookkeeping.
210 cananian 1.3.2.1 assert !marked.contains(e);
211 cananian 1.1.2.3 marked.add(e);
212 cananian 1.1.2.1 // setup 'from' state.
213 cananian 1.5 Quad from = e.from();
214 cananian 1.1.2.1 if (from instanceof HEADER) {
215 cananian 1.1.2.1 old2new.put(from, from.rename(nqf, null, null));
216 cananian 1.1.2.1 } else if (from instanceof PHI) {
217 cananian 1.1.2.1 Temp[] l = (Temp[]) lhs.get(from);
218 cananian 1.1.2.1 for (int i=0; i<l.length; i++)
219 cananian 1.1.2.1 l[i] = varmap.inc(l[i]);
220 cananian 1.1.2.1 } else if (from instanceof SIGMA) {
221 cananian 1.1.2.1 Temp[][] l = (Temp[][]) lhs.get(from);
222 cananian 1.1.2.1 int j = e.which_succ();
223 cananian 1.1.2.1 for (int i=0; i<l.length; i++)
224 cananian 1.1.2.1 l[i][j] = varmap.inc(l[i][j]);
225 cananian 1.1.2.1 }
226 cananian 1.1.2.9 // fixup defs in CALL/PCALL sigma appropriately
227 cananian 1.1.2.9 if (from instanceof CALL || from instanceof PCALL) {
228 cananian 1.1.2.9 Temp retval, retex;
229 cananian 1.1.2.9 if (from instanceof CALL) {
230 cananian 1.1.2.9 retval = ((CALL) from).retval();
231 cananian 1.1.2.9 retex = ((CALL) from).retex();
232 cananian 1.1.2.9 } else {
233 cananian 1.1.2.9 retval = ((PCALL) from).retval();
234 cananian 1.1.2.9 retex = ((PCALL) from).retex();
235 cananian 1.1.2.9 }
236 cananian 1.1.2.4 Temp[] defs = (Temp[]) sdf.get(from);
237 cananian 1.1.2.4 if (defs==null) { defs=new Temp[2]; sdf.put(from, defs); }
238 cananian 1.1.2.4 // use of inc() below serves to kill any aliases on this path
239 cananian 1.1.2.9 if (e.which_succ()==0 && retval!=null)
240 cananian 1.1.2.9 defs[0]=varmap.inc(retval);
241 cananian 1.1.2.4 if (e.which_succ()==1)
242 cananian 1.1.2.9 defs[1]=varmap.inc(retex);
243 cananian 1.1.2.4 }
244 cananian 1.1.2.1 // now go on renaming inside basic block until we get to a phi
245 cananian 1.1.2.1 // or sigma.
246 cananian 1.1.2.1 for (Quad q; ; e=q.nextEdge(0)) {
247 cananian 1.5 q = e.to();
248 cananian 1.1.2.1 if (q instanceof PHI) { /* update src */
249 cananian 1.1.2.1 Temp[][] r = (Temp[][]) rhs.get(q);
250 cananian 1.1.2.1 int j = e.which_pred();
251 cananian 1.1.2.1 for (int i=0; i < r.length; i++)
252 cananian 1.1.2.1 r[i][j] = varmap.get(r[i][j]);
253 cananian 1.1.2.3 break;
254 cananian 1.1.2.1 }
255 cananian 1.1.2.1 if (q instanceof SIGMA) { /* update src */
256 cananian 1.1.2.4 // rhs of sigma comes before any defs in the sigma.
257 cananian 1.1.2.1 Temp[] r = (Temp[]) rhs.get(q);
258 cananian 1.1.2.1 for (int i=0; i < r.length; i++)
259 cananian 1.1.2.1 r[i] = varmap.get(r[i]);
260 cananian 1.1.2.1 if (q instanceof CJMP)
261 cananian 1.1.2.1 arg.put(q, varmap.get(((CJMP)q).test()));
262 cananian 1.1.2.1 else if (q instanceof SWITCH)
263 cananian 1.1.2.1 arg.put(q, varmap.get(((SWITCH)q).index()));
264 cananian 1.1.2.14 else if (q instanceof TYPESWITCH)
265 cananian 1.1.2.14 arg.put(q, varmap.get(((TYPESWITCH)q).index()));
266 cananian 1.1.2.4 else if (q instanceof CALL) {
267 cananian 1.1.2.4 CALL Q = (CALL) q;
268 cananian 1.1.2.4 Temp[] args = new Temp[Q.paramsLength()];
269 cananian 1.1.2.4 for (int i=0; i<Q.paramsLength(); i++)
270 cananian 1.1.2.4 args[i] = varmap.get(Q.params(i));
271 cananian 1.1.2.4 arg.put(q, args);
272 cananian 1.1.2.9 } else if (q instanceof PCALL) {
273 cananian 1.1.2.9 PCALL Q = (PCALL) q;
274 cananian 1.1.2.9 Temp[] args = new Temp[1+Q.paramsLength()];
275 cananian 1.1.2.9 for (int i=0; i<Q.paramsLength(); i++)
276 cananian 1.1.2.9 args[i] = varmap.get(Q.params(i));
277 bdemsky 1.1.2.15 args[Q.paramsLength()] = varmap.get(Q.ptr());
278 cananian 1.1.2.9 arg.put(q, args);
279 cananian 1.1.2.4 } else throw new Error("Ack!");
280 cananian 1.1.2.3 break;
281 cananian 1.1.2.1 }
282 cananian 1.1.2.1 /* else, rename src, then rename dst */
283 cananian 1.1.2.1 Temp u[] = q.use(), d[] = q.def();
284 cananian 1.1.2.1 for (int i=0; i<u.length; i++)
285 cananian 1.1.2.1 wtm.associate(u[i], varmap.get(u[i]));
286 cananian 1.1.2.1 for (int i=0; i<d.length; i++)
287 cananian 1.1.2.1 varmap.inc(d[i]);
288 cananian 1.1.2.1 Quad nq = q.rename(nqf, varmap, wtm);
289 cananian 1.1.2.1 old2new.put(q, nq);
290 cananian 1.1.2.12 if (nderiv!=null)
291 bdemsky 1.1.2.16 transferderivation(nq, q, q.def(), varmap, oderiv);
292 cananian 1.1.2.11 if (nq instanceof ANEW || nq instanceof NEW)
293 cananian 1.1.2.11 if (naim!=null) naim.transfer(nq, q, varmap, oaim);
294 cananian 1.1.2.3 if (q instanceof FOOTER) break;
295 cananian 1.1.2.3 }
296 cananian 1.5 for (Iterator<Edge> it=e.to().succC().iterator();it.hasNext();) {
297 cananian 1.5 e = it.next();
298 cananian 1.1.2.3 if (!marked.contains(e))
299 cananian 1.1.2.3 We.push(e);
300 cananian 1.1.2.1 }
301 cananian 1.1.2.1 }
302 bdemsky 1.1.2.16
303 bdemsky 1.1.2.16 void transferderivation(Quad nq, Quad q, Temp[] defs, TempMap varmap, Derivation oderiv) {
304 bdemsky 1.1.2.16 nderiv.transfer(nq,q,defs,varmap,oderiv);
305 bdemsky 1.1.2.16 for(int i=0;i<defs.length;i++)
306 bdemsky 1.1.2.16 derivmap.put(varmap.tempMap(defs[i]),new DerivType(nderiv.derivation(nq,varmap.tempMap(defs[i])),nderiv.typeMap(nq,varmap.tempMap(defs[i]))));
307 bdemsky 1.1.2.16 }
308 bdemsky 1.1.2.16
309 bdemsky 1.1.2.16 void addType(Quad nq, Temp t,HClass type) {
310 bdemsky 1.1.2.16 nderiv.putType(nq,t,type);
311 bdemsky 1.1.2.16 derivmap.put(t, new DerivType(null,type));
312 bdemsky 1.1.2.16 }
313 bdemsky 1.1.2.16
314 bdemsky 1.1.2.16 static class DerivType {
315 bdemsky 1.1.2.16 Derivation.DList deriv;
316 bdemsky 1.1.2.16 HClass type;
317 bdemsky 1.1.2.16 DerivType(Derivation.DList deriv,HClass type) {
318 bdemsky 1.1.2.16 this.deriv=deriv;
319 bdemsky 1.1.2.16 this.type=type;
320 bdemsky 1.1.2.16 }
321 bdemsky 1.1.2.16
322 bdemsky 1.1.2.16 DerivType() {
323 bdemsky 1.1.2.16 this.deriv=null;
324 bdemsky 1.1.2.16 this.type=null;
325 bdemsky 1.1.2.16 }
326 bdemsky 1.1.2.16
327 bdemsky 1.1.2.16 void merge(DerivType dt) {
328 bdemsky 1.1.2.16 if (dt!=null) {
329 bdemsky 1.1.2.16 //Merge types
330 bdemsky 1.1.2.16 if ((type!=null)&&(dt.type!=null))
331 bdemsky 1.1.2.16 type=HClassUtil.commonParent(type,dt.type);
332 bdemsky 1.1.2.16 else if (type==null)
333 bdemsky 1.1.2.16 type=dt.type;
334 bdemsky 1.1.2.16
335 bdemsky 1.1.2.16 //Merge derivations
336 bdemsky 1.1.2.16 if (deriv==null)
337 bdemsky 1.1.2.16 this.deriv=dt.deriv;
338 bdemsky 1.1.2.16 }
339 bdemsky 1.1.2.16 }
340 bdemsky 1.1.2.16
341 bdemsky 1.1.2.16 HClass type() {
342 bdemsky 1.1.2.16 return type;
343 bdemsky 1.1.2.16 }
344 bdemsky 1.1.2.16
345 bdemsky 1.1.2.16 Derivation.DList deriv() {
346 bdemsky 1.1.2.16 return deriv;
347 bdemsky 1.1.2.16 }
348 bdemsky 1.1.2.16 }
349 bdemsky 1.1.2.16
350 bdemsky 1.1.2.16 static class PhiSigFunction {
351 bdemsky 1.1.2.16 Temp[] left,right;
352 bdemsky 1.1.2.16 PhiSigFunction(Temp[] left, Temp[] right) {
353 bdemsky 1.1.2.16 this.left=left;
354 bdemsky 1.1.2.16 this.right=right;
355 bdemsky 1.1.2.16 }
356 bdemsky 1.1.2.16 Temp[] left() {
357 bdemsky 1.1.2.16 return left;
358 bdemsky 1.1.2.16 }
359 bdemsky 1.1.2.16 Temp[] right() {
360 bdemsky 1.1.2.16 return right;
361 bdemsky 1.1.2.16 }
362 bdemsky 1.1.2.16 }
363 bdemsky 1.1.2.16
364 cananian 1.5 void fixPhiSigDeriv(HCode<Quad> c) {
365 bdemsky 1.1.2.16 WorkSet functionSet=new WorkSet();
366 bdemsky 1.1.2.16 RelationImpl rel=new RelationImpl();
367 bdemsky 1.1.2.16 HashSet phisig=new HashSet();
368 bdemsky 1.1.2.16 //Add Phi's and Sigmas to function set
369 bdemsky 1.1.2.16
370 cananian 1.5 for (Iterator<Quad> it=c.getElementsI(); it.hasNext(); ) {
371 cananian 1.5 Quad q = old2new.get(it.next());
372 bdemsky 1.1.2.16 if (q instanceof PHI) {
373 bdemsky 1.1.2.16 for(int i=0;i<((PHI)q).numPhis();i++) {
374 bdemsky 1.1.2.16 PhiSigFunction psf=new PhiSigFunction(new Temp[]{((PHI)q).dst(i)},((PHI)q).src(i));
375 bdemsky 1.1.2.16 functionSet.add(psf);
376 bdemsky 1.1.2.16 for(int j=0;j<((PHI)q).arity();j++) {
377 bdemsky 1.1.2.16 rel.add(((PHI)q).src(i,j),psf);
378 bdemsky 1.1.2.16 }
379 bdemsky 1.1.2.16 }
380 bdemsky 1.1.2.16 } else if (q instanceof SIGMA) {
381 bdemsky 1.1.2.16 for(int i=0;i<((SIGMA)q).numSigmas();i++) {
382 bdemsky 1.1.2.16 PhiSigFunction psf=new PhiSigFunction(((SIGMA)q).dst(i),new Temp[]{((SIGMA)q).src(i)});
383 bdemsky 1.1.2.16 functionSet.add(psf);
384 bdemsky 1.1.2.16 rel.add(((SIGMA)q).src(i),psf);
385 bdemsky 1.1.2.16 }
386 bdemsky 1.1.2.16 }
387 bdemsky 1.1.2.16 }
388 bdemsky 1.1.2.16 while(!functionSet.isEmpty()) {
389 bdemsky 1.1.2.16 PhiSigFunction psf=(PhiSigFunction)functionSet.pop();
390 bdemsky 1.1.2.16 Temp[] right=psf.right();
391 bdemsky 1.1.2.16 Temp[] left=psf.left();
392 bdemsky 1.1.2.16 DerivType best=new DerivType();
393 bdemsky 1.1.2.16 for(int i=0;i<right.length;i++) {
394 bdemsky 1.1.2.16 best.merge((DerivType)derivmap.get(right[i]));
395 bdemsky 1.1.2.16 }
396 bdemsky 1.1.2.16 for(int i=0;i<left.length;i++) {
397 bdemsky 1.1.2.16 DerivType old=(DerivType)derivmap.get(left[i]);
398 bdemsky 1.1.2.16 if (old==null) {
399 bdemsky 1.1.2.16 derivmap.put(left[i],best);
400 bdemsky 1.1.2.16 Set values=rel.getValues(left[i]);
401 bdemsky 1.1.2.16 Iterator it=values.iterator();
402 bdemsky 1.1.2.16 while(it.hasNext())
403 bdemsky 1.1.2.16 functionSet.add(it.next());
404 bdemsky 1.1.2.16 } else if ((old.type!=best.type)||((best.deriv!=null)&&(old.deriv==null))) {
405 bdemsky 1.1.2.16 derivmap.put(left[i],best);
406 bdemsky 1.1.2.16 Set values=rel.getValues(left[i]);
407 bdemsky 1.1.2.16 Iterator it=values.iterator();
408 bdemsky 1.1.2.16 while(it.hasNext())
409 bdemsky 1.1.2.16 functionSet.add(it.next());
410 bdemsky 1.1.2.16 }
411 bdemsky 1.1.2.16 }
412 bdemsky 1.1.2.16 }
413 bdemsky 1.1.2.16
414 cananian 1.5 for (Iterator<Quad> it=c.getElementsI(); it.hasNext(); ) {
415 cananian 1.5 Quad q = old2new.get(it.next());
416 bdemsky 1.1.2.16 if (q instanceof PHI) {
417 bdemsky 1.1.2.16 for(int i=0;i<((PHI)q).numPhis();i++) {
418 bdemsky 1.1.2.16 Temp t=((PHI)q).dst(i);
419 bdemsky 1.1.2.16 DerivType dt=(DerivType)derivmap.get(t);
420 bdemsky 1.1.2.16 if (dt.type()!=null)
421 bdemsky 1.1.2.16 nderiv.putType(q,t,dt.type());
422 bdemsky 1.1.2.16 if (dt.deriv()!=null)
423 bdemsky 1.1.2.16 nderiv.putDerivation(q,t,dt.deriv());
424 bdemsky 1.1.2.16 }
425 bdemsky 1.1.2.16 } else if (q instanceof SIGMA) {
426 bdemsky 1.1.2.16 for(int i=0;i<((SIGMA)q).numSigmas();i++) {
427 bdemsky 1.1.2.16 for(int j=0;j<((SIGMA)q).arity();j++) {
428 bdemsky 1.1.2.16 Temp t=((SIGMA)q).dst(i,j);
429 bdemsky 1.1.2.16 DerivType dt=(DerivType)derivmap.get(t);
430 bdemsky 1.1.2.16 if (dt.type()!=null)
431 bdemsky 1.1.2.16 nderiv.putType(q,t,dt.type());
432 bdemsky 1.1.2.16 if (dt.deriv()!=null)
433 bdemsky 1.1.2.16 nderiv.putDerivation(q,t,dt.deriv());
434 bdemsky 1.1.2.16 }
435 bdemsky 1.1.2.16 }
436 bdemsky 1.1.2.16 }
437 bdemsky 1.1.2.16 }
438 bdemsky 1.1.2.16 }
439 bdemsky 1.1.2.16
440 cananian 1.5 void makePhiSig(HCode<Quad> c) {
441 cananian 1.5 for (Iterator<Quad> it=c.getElementsI(); it.hasNext(); ) {
442 cananian 1.5 Quad q = it.next();
443 cananian 1.1.2.1 if (q instanceof PHI) {
444 cananian 1.1.2.1 Temp[] l = (Temp[]) lhs.get(q);
445 cananian 1.1.2.1 Temp[][] r = (Temp[][]) rhs.get(q);
446 cananian 1.1.2.1 Quad nq = new PHI(nqf, q, l, r, ((PHI)q).arity());
447 cananian 1.1.2.1 old2new.put(q, nq);
448 cananian 1.1.2.1 } else if (q instanceof SIGMA) {
449 cananian 1.1.2.1 Temp[][] l = (Temp[][]) lhs.get(q);
450 cananian 1.1.2.1 Temp[] r = (Temp[]) rhs.get(q);
451 cananian 1.1.2.1 Quad nq;
452 cananian 1.1.2.1 if (q instanceof CJMP)
453 cananian 1.1.2.4 nq = new CJMP(nqf, q, (Temp) arg.get(q), l, r);
454 cananian 1.1.2.1 else if (q instanceof SWITCH)
455 cananian 1.1.2.4 nq = new SWITCH(nqf, q, (Temp) arg.get(q),
456 cananian 1.1.2.4 ((SWITCH)q).keys(), l, r);
457 cananian 1.1.2.14 else if (q instanceof TYPESWITCH)
458 cananian 1.1.2.14 nq = new TYPESWITCH(nqf, q, (Temp) arg.get(q),
459 cananian 1.1.2.17 ((TYPESWITCH)q).keys(), l, r,
460 cananian 1.1.2.17 ((TYPESWITCH)q).hasDefault());
461 cananian 1.1.2.4 else if (q instanceof CALL) {
462 cananian 1.1.2.4 CALL Q = (CALL) q;
463 cananian 1.1.2.4 Temp[] defs = (Temp[]) sdf.get(q);
464 cananian 1.1.2.4 nq = new CALL(nqf, Q, Q.method(), (Temp[]) arg.get(q),
465 cananian 1.1.2.5 defs[0], defs[1],
466 cananian 1.1.2.5 Q.isVirtual(), Q.isTailCall(),
467 cananian 1.1.2.5 l, r);
468 bdemsky 1.1.2.16 if (nderiv!=null) {
469 bdemsky 1.1.2.16 addType(nq,defs[0],oderiv.typeMap(q,((CALL)q).retval()));
470 bdemsky 1.1.2.16 addType(nq,defs[1],oderiv.typeMap(q,((CALL)q).retex()));
471 bdemsky 1.1.2.16 }
472 cananian 1.1.2.9 } else if (q instanceof PCALL) {
473 cananian 1.1.2.9 harpoon.IR.LowQuad.LowQuadFactory lqf =
474 cananian 1.1.2.9 (harpoon.IR.LowQuad.LowQuadFactory) nqf;
475 cananian 1.1.2.9 PCALL Q = (PCALL) q;
476 cananian 1.1.2.9 Temp[] defs = (Temp[]) sdf.get(q);
477 cananian 1.1.2.9 Temp[] argsandptr = (Temp[]) arg.get(q);
478 cananian 1.1.2.9 Temp[] args = new Temp[argsandptr.length - 1];
479 cananian 1.1.2.9 System.arraycopy(argsandptr,0,args,0,args.length);
480 cananian 1.1.2.9 nq = new PCALL(lqf, Q, argsandptr[args.length],
481 cananian 1.1.2.9 args, defs[0], defs[1], l, r,
482 cananian 1.1.2.9 Q.isVirtual(), Q.isTailCall());
483 bdemsky 1.1.2.16 if (nderiv!=null) {
484 bdemsky 1.1.2.16 if (defs[0]!=null)
485 bdemsky 1.1.2.16 addType(nq,defs[0],oderiv.typeMap(q,((PCALL)q).retval()));
486 bdemsky 1.1.2.16 if (defs[1]!=null)
487 bdemsky 1.1.2.16 addType(nq,defs[1],oderiv.typeMap(q,((PCALL)q).retex()));
488 bdemsky 1.1.2.16 }
489 cananian 1.1.2.4 } else throw new Error("Ack!");
490 cananian 1.1.2.1 old2new.put(q, nq);
491 cananian 1.1.2.1 }
492 cananian 1.1.2.1 }
493 cananian 1.1.2.1 }
494 cananian 1.1.2.1 }
495 cananian 1.2 }