1 cananian 1.1.2.1 // SSIToSSA.java, created Wed May 31 16:35:30 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.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.AllocationInformationMap;
7 cananian 1.1.2.1 import harpoon.Analysis.Maps.AllocationInformation;
8 cananian 1.1.2.1 import harpoon.Analysis.Maps.Derivation;
9 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
10 cananian 1.1.2.1 import harpoon.ClassFile.HCodeEdge;
11 cananian 1.1.2.1 import harpoon.ClassFile.HCodeElement;
12 cananian 1.1.2.3 import harpoon.IR.Quads.Code;
13 cananian 1.1.2.1 import harpoon.IR.LowQuad.DerivationMap;
14 cananian 1.1.2.1 import harpoon.IR.LowQuad.LowQuadFactory;
15 cananian 1.1.2.1 import harpoon.IR.LowQuad.LowQuadVisitor;
16 cananian 1.1.2.1 import harpoon.IR.LowQuad.PCALL;
17 cananian 1.1.2.1 import harpoon.Temp.CloningTempMap;
18 cananian 1.1.2.1 import harpoon.Temp.Temp;
19 cananian 1.1.2.1 import harpoon.Temp.TempFactory;
20 cananian 1.1.2.1 import harpoon.Temp.TempMap;
21 cananian 1.7 import net.cscott.jutil.DisjointSet;
22 cananian 1.1.2.1 import harpoon.Util.Util;
23 cananian 1.1.2.1
24 cananian 1.1.2.1 import java.util.Collections;
25 cananian 1.1.2.1 import java.util.HashMap;
26 cananian 1.1.2.1 import java.util.Iterator;
27 cananian 1.1.2.1 import java.util.Map;
28 cananian 1.1.2.1 /**
29 cananian 1.1.2.1 * <code>SSIToSSA</code> renames variables to eliminate sigma functions
30 cananian 1.1.2.1 * in an SSI-form codeview, yielding an SSA codeview.
31 cananian 1.1.2.1 *
32 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
33 cananian 1.7 * @version $Id: SSIToSSA.java,v 1.7 2004/02/08 01:55:25 cananian Exp $
34 cananian 1.1.2.1 */
35 cananian 1.1.2.1 public class SSIToSSA {
36 cananian 1.1.2.1 // Return values for the algorithm:
37 cananian 1.1.2.1
38 cananian 1.1.2.5 /** New root element (of the SSA-form graph) */
39 cananian 1.5 public final HEADER rootQuad;
40 cananian 1.1.2.1 /** Map from old ssi temps to new ssa temps. */
41 cananian 1.1.2.1 public final TempMap tempMap;
42 cananian 1.6 /** Map from new ssa temps to old ssi temps. */
43 cananian 1.6 public final TempMap revTempMap;
44 cananian 1.1.2.1 /** Map from old ssi quads to new ssa quads. */
45 cananian 1.5 public final Map<Quad,Quad> quadMap;
46 cananian 1.6 /** Map from new ssa quads to old ssi quads. */
47 cananian 1.6 public final Map<Quad,Quad> revQuadMap;
48 cananian 1.1.2.1 /** <code>AllocationInformation</code> for the new quads, or
49 cananian 1.1.2.1 * <code>null</code> if no allocation information for the old
50 cananian 1.1.2.1 * quads was supplied. */
51 cananian 1.5 public final AllocationInformation<Quad> allocInfo;
52 cananian 1.1.2.1 /** <code>Derivation</code> for the new quads, or <code>null</code>
53 cananian 1.1.2.1 * if no <code>Derivation</code> for the old quads was supplied. */
54 cananian 1.5 public final Derivation<Quad> derivation;
55 cananian 1.1.2.1
56 cananian 1.1.2.1 /** Converts the given code (in SSI form) to a graph graph in
57 cananian 1.1.2.1 * SSA form created using the given code factory <code>nqf</code>. */
58 cananian 1.1.2.1 public SSIToSSA(final Code c, final QuadFactory nqf) {
59 cananian 1.5 HEADER oldhead = c.getRootElement();
60 cananian 1.1.2.1 // first, zip through quads, renaming sigma dests to sources.
61 cananian 1.1.2.1 Scanner scanner = new Scanner(c, oldhead.getFactory().tempFactory(),
62 cananian 1.1.2.1 nqf.tempFactory());
63 cananian 1.1.2.1 // now clone quads, doing the renaming and clearing sigma funcs.
64 cananian 1.1.2.1 Cloner cloner = new Cloner(c, nqf, scanner,
65 cananian 1.1.2.1 c.getDerivation(),
66 cananian 1.1.2.1 c.getAllocationInformation());
67 cananian 1.1.2.1 // finally, link all the cloned quads together properly.
68 cananian 1.1.2.1 Linker linker = new Linker(c, cloner.old2new);
69 cananian 1.1.2.1
70 cananian 1.1.2.1 // set instance fields to return values.
71 cananian 1.1.2.1 this.rootQuad = (HEADER) cloner.old2new.get(oldhead);
72 cananian 1.1.2.1 this.tempMap = scanner.unmodifiable();
73 cananian 1.1.2.1 this.quadMap = Collections.unmodifiableMap(cloner.old2new);
74 cananian 1.6 this.revTempMap = scanner.reverseTempMap();
75 cananian 1.6 this.revQuadMap = Collections.unmodifiableMap(cloner.new2old);
76 cananian 1.1.2.1 this.allocInfo = cloner.naim;
77 cananian 1.1.2.1 this.derivation = cloner.nderiv;
78 cananian 1.1.2.1 }
79 cananian 1.1.2.1
80 cananian 1.1.2.1 // create map of sigmas dsts to sources.
81 cananian 1.1.2.1 // use this to implement cloningtempmap with appropriate merges.
82 cananian 1.1.2.1 static class Scanner extends LowQuadVisitor implements TempMap {
83 cananian 1.5 final DisjointSet<Temp> map = new DisjointSet<Temp>();
84 cananian 1.1.2.1 final CloningTempMap ctm;
85 cananian 1.6 final Map<Temp,Temp> reverseMap = new HashMap<Temp,Temp>();
86 cananian 1.1.2.1 Scanner(Code c, TempFactory oldtf, TempFactory newtf) {
87 cananian 1.1.2.1 super(c instanceof harpoon.IR.LowQuad.Code);// strictness.
88 cananian 1.1.2.1 this.ctm = new CloningTempMap(oldtf, newtf);
89 cananian 1.1.2.1 // visit all elements.
90 cananian 1.5 for (Iterator<Quad> it=c.getElementsI(); it.hasNext(); )
91 cananian 1.5 it.next().accept(this);
92 cananian 1.1.2.1 }
93 cananian 1.1.2.1 // implement TempMap via CloningTempMap.
94 cananian 1.6 public Temp tempMap(Temp t) {
95 cananian 1.6 Temp r = ctm.tempMap(map.find(t));
96 cananian 1.6 reverseMap.put(r, t);
97 cananian 1.6 return r;
98 cananian 1.6 }
99 cananian 1.1.2.1 public TempMap unmodifiable() {
100 cananian 1.1.2.1 final TempMap uctm = ctm.unmodifiable();
101 cananian 1.1.2.1 return new TempMap() {
102 cananian 1.1.2.1 public Temp tempMap(Temp t) {
103 cananian 1.5 return uctm.tempMap(map.find(t));
104 cananian 1.1.2.1 }
105 cananian 1.1.2.1 };
106 cananian 1.1.2.1 }
107 cananian 1.6 public TempMap reverseTempMap() {
108 cananian 1.6 return new TempMap() {
109 cananian 1.6 public Temp tempMap(Temp t) {
110 cananian 1.6 return reverseMap.get(t);
111 cananian 1.6 }
112 cananian 1.6 };
113 cananian 1.6 }
114 cananian 1.1.2.1
115 cananian 1.1.2.1 // implement visitor.
116 cananian 1.1.2.1 public void visit(Quad q) { /* do nothing. */ }
117 cananian 1.1.2.1 public void visit(SIGMA q) {
118 cananian 1.1.2.1 final int numSigmas = q.numSigmas();
119 cananian 1.1.2.1 final int arity = q.arity();
120 cananian 1.1.2.1 for (int i=0; i<numSigmas; i++)
121 cananian 1.1.2.1 for (int j=0; j<arity; j++)
122 cananian 1.1.2.1 map.union(q.dst(i, j), q.src(i));
123 cananian 1.1.2.1 }
124 cananian 1.1.2.1 }
125 cananian 1.1.2.1 // create map of old quads to new quads.
126 cananian 1.1.2.1 static class Cloner extends LowQuadVisitor {
127 cananian 1.1.2.1 /** Maps SSI quads to SSA quads. */
128 cananian 1.5 final Map<Quad,Quad> old2new = new HashMap<Quad,Quad>();
129 cananian 1.6 /** Maps SSA quads to SSI quads. */
130 cananian 1.6 final Map<Quad,Quad> new2old = new HashMap<Quad,Quad>();
131 cananian 1.1.2.1 /** Maps old temps to new temps. */
132 cananian 1.1.2.1 final TempMap tm;
133 cananian 1.1.2.1 /** QuadFactory to use for new Quads. */
134 cananian 1.1.2.1 final QuadFactory nqf;
135 cananian 1.1.2.1 /** AllocationInformation for old Quads */
136 cananian 1.5 final AllocationInformation<Quad> oaim;
137 cananian 1.1.2.1 /** AllocationInformationMap for new Quads */
138 cananian 1.5 final AllocationInformationMap<Quad> naim;
139 cananian 1.1.2.1 /** Derivation for old Quads */
140 cananian 1.5 final Derivation<Quad> oderiv;
141 cananian 1.1.2.1 /** Derivation map for new Quads */
142 cananian 1.5 final DerivationMap<Quad> nderiv;
143 cananian 1.1.2.1
144 cananian 1.1.2.1 Cloner(Code c, QuadFactory nqf, TempMap tm,
145 cananian 1.5 Derivation<Quad> oderiv, AllocationInformation<Quad> oaim) {
146 cananian 1.1.2.1 super(c instanceof harpoon.IR.LowQuad.Code);// strictness.
147 cananian 1.1.2.1 // setup cloner fields.
148 cananian 1.1.2.1 this.nqf = nqf; this.tm = tm;
149 cananian 1.1.2.1 this.oaim = oaim;
150 cananian 1.1.2.1 this.naim = (oaim==null) ? null : new AllocationInformationMap();
151 cananian 1.1.2.1 this.oderiv= oderiv;
152 cananian 1.1.2.1 this.nderiv= (oderiv==null) ? null : new DerivationMap();
153 cananian 1.1.2.1 // visit all elements.
154 cananian 1.5 for (Iterator<Quad> it=c.getElementsI(); it.hasNext(); )
155 cananian 1.5 it.next().accept(this);
156 cananian 1.1.2.1 }
157 cananian 1.1.2.1 private void record(Quad oldq, Quad newq, boolean transferDeriv) {
158 cananian 1.1.2.1 old2new.put(oldq, newq);
159 cananian 1.6 new2old.put(newq, oldq);
160 cananian 1.1.2.1 if (transferDeriv && nderiv!=null)
161 cananian 1.1.2.1 nderiv.transfer(newq, oldq, oldq.def(), tm, oderiv);
162 cananian 1.1.2.1 if (newq instanceof ANEW || newq instanceof NEW)
163 cananian 1.1.2.1 if (naim!=null) naim.transfer(newq, oldq, tm, oaim);
164 cananian 1.1.2.1 }
165 cananian 1.1.2.1 public void visit(Quad q) {
166 cananian 1.1.2.1 Quad nq = q.rename(nqf, tm, tm);
167 cananian 1.1.2.1 record(q, nq, true);
168 cananian 1.1.2.1 }
169 cananian 1.1.2.1 // instances of sigma functions.
170 cananian 1.1.2.1 public void visit(SIGMA q) {
171 cananian 1.1.2.1 // should be caught by specific case.
172 cananian 1.3.2.1 assert false : ("unknown sigma function: "+q);
173 cananian 1.1.2.1 }
174 cananian 1.1.2.1 public void visit(CALL q) {
175 cananian 1.1.2.1 // create CALL with no sigma functions.
176 cananian 1.1.2.1 CALL nq = new CALL(nqf, q, q.method(), map(q.params()),
177 cananian 1.1.2.1 map(q.retval()), map(q.retex()),
178 cananian 1.1.2.1 q.isVirtual(), q.isTailCall(), new Temp[0]);
179 cananian 1.1.2.1 record(q, nq, false);
180 cananian 1.1.2.1 if (nderiv!=null) {
181 cananian 1.1.2.1 Temp[] odefs = (q.retval()!=null) ?
182 cananian 1.1.2.1 new Temp[] { q.retval(), q.retex() } :
183 cananian 1.1.2.1 new Temp[] { q.retex() };
184 cananian 1.1.2.1 nderiv.transfer(nq, q, odefs, tm, oderiv);
185 cananian 1.1.2.1 }
186 cananian 1.1.2.1 }
187 cananian 1.1.2.1 public void visit(CJMP q) {
188 cananian 1.1.2.1 CJMP nq = new CJMP(nqf, q, map(q.test()), new Temp[0]);
189 cananian 1.1.2.1 record(q, nq, false);
190 cananian 1.1.2.1 }
191 cananian 1.1.2.1 public void visit(PCALL q) {
192 cananian 1.1.2.1 PCALL nq = new PCALL((LowQuadFactory)nqf, q,
193 cananian 1.1.2.1 map(q.ptr()), map(q.params()),
194 cananian 1.1.2.1 map(q.retval()), map(q.retex()),
195 cananian 1.1.2.1 new Temp[0], q.isVirtual(), q.isTailCall());
196 cananian 1.1.2.1 record(q, nq, false);
197 cananian 1.1.2.1 if (nderiv!=null) {
198 cananian 1.1.2.1 Temp[] odefs = (q.retval()!=null) ?
199 cananian 1.1.2.1 new Temp[] { q.retval(), q.retex() } :
200 cananian 1.1.2.1 new Temp[] { q.retex() };
201 cananian 1.1.2.1 nderiv.transfer(nq, q, odefs, tm, oderiv);
202 cananian 1.1.2.1 }
203 cananian 1.1.2.1 }
204 cananian 1.1.2.1 public void visit(SWITCH q) {
205 cananian 1.1.2.1 SWITCH nq = new SWITCH(nqf, q, map(q.index()), q.keys(),
206 cananian 1.1.2.1 new Temp[0]);
207 cananian 1.1.2.2 record(q, nq, false);
208 cananian 1.1.2.2 }
209 cananian 1.1.2.2 public void visit(TYPESWITCH q) {
210 cananian 1.1.2.2 TYPESWITCH nq = new TYPESWITCH(nqf, q, map(q.index()), q.keys(),
211 cananian 1.1.2.4 new Temp[0], q.hasDefault());
212 cananian 1.1.2.1 record(q, nq, false);
213 cananian 1.1.2.1 }
214 cananian 1.1.2.1 // convenience mapping functions.
215 cananian 1.1.2.1 private Temp map(Temp t) { return t==null?null:tm.tempMap(t); }
216 cananian 1.1.2.1 private Temp[] map(Temp[] ta) {
217 cananian 1.1.2.1 Temp[] result = new Temp[ta.length];
218 cananian 1.1.2.1 for (int i=0; i<ta.length; i++)
219 cananian 1.1.2.1 result[i] = map(ta[i]);
220 cananian 1.1.2.1 return result;
221 cananian 1.1.2.1 }
222 cananian 1.1.2.1 }
223 cananian 1.1.2.1 // link quads together.
224 cananian 1.1.2.1 static class Linker {
225 cananian 1.5 Linker(Code c, Map<Quad,Quad> old2new) {
226 cananian 1.1.2.1 // visit all elements, linking together.
227 cananian 1.5 for (Iterator<Quad> it=c.getElementsI(); it.hasNext(); ) {
228 cananian 1.5 Quad q = it.next();
229 cananian 1.1.2.1 int n = q.nextLength();
230 cananian 1.1.2.1 for (int i=0; i<n; i++) {
231 cananian 1.1.2.1 Edge e = q.nextEdge(i);
232 cananian 1.5 Quad nfrm = old2new.get(e.from());
233 cananian 1.5 Quad nto = old2new.get(e.to());
234 cananian 1.1.2.1 Quad.addEdge(nfrm, e.which_succ(), nto, e.which_pred());
235 cananian 1.1.2.1 }
236 cananian 1.1.2.1 }
237 cananian 1.1.2.1 }
238 cananian 1.1.2.1 }
239 cananian 1.2 }