1 cananian 1.1.2.1 // CoalescingToNoSSA.java, created Thu Nov 23 14:52:08 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.Analysis.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.Transformation.MethodMutator;
7 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
8 cananian 1.1.2.1 import harpoon.ClassFile.HCodeAndMaps;
9 cananian 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
10 cananian 1.1.2.1 import harpoon.ClassFile.HMethod;
11 cananian 1.1.2.1 import harpoon.IR.Quads.CALL;
12 cananian 1.1.2.1 import harpoon.IR.Quads.CJMP;
13 cananian 1.1.2.1 import harpoon.IR.Quads.Code;
14 cananian 1.1.2.1 import harpoon.IR.Quads.Edge;
15 cananian 1.1.2.1 import harpoon.IR.Quads.FOOTER;
16 cananian 1.1.2.1 import harpoon.IR.Quads.HEADER;
17 cananian 1.1.2.1 import harpoon.IR.Quads.MOVE;
18 cananian 1.1.2.1 import harpoon.IR.Quads.PHI;
19 cananian 1.1.2.1 import harpoon.IR.Quads.Quad;
20 cananian 1.1.2.1 import harpoon.IR.Quads.QuadFactory;
21 cananian 1.1.2.1 import harpoon.IR.Quads.QuadNoSSA;
22 cananian 1.1.2.1 import harpoon.IR.Quads.QuadRSSx;
23 cananian 1.1.2.1 import harpoon.IR.Quads.QuadSSA;
24 cananian 1.1.2.1 import harpoon.IR.Quads.QuadSSI;
25 cananian 1.1.2.1 import harpoon.IR.Quads.QuadVisitor;
26 cananian 1.1.2.1 import harpoon.IR.Quads.SIGMA;
27 cananian 1.1.2.1 import harpoon.IR.Quads.SWITCH;
28 cananian 1.1.2.1 import harpoon.IR.Quads.TYPESWITCH;
29 cananian 1.1.2.1 import harpoon.Temp.Temp;
30 cananian 1.1.2.1 import harpoon.Temp.TempMap;
31 cananian 1.5 import net.cscott.jutil.DisjointSet;
32 cananian 1.1.2.1 import harpoon.Util.Util;
33 cananian 1.1.2.1
34 cananian 1.1.2.1 import java.util.Iterator;
35 cananian 1.1.2.1 /**
36 cananian 1.1.2.1 * <code>CoalescingToNoSSA</code> converts SSA, SSI, and RSSx forms
37 cananian 1.1.2.1 * to No-SSA form, *coalescing* variables mentioned in phi and sigma
38 cananian 1.1.2.1 * statements where possible instead of inserting moves.
39 cananian 1.1.2.1 *
40 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
41 cananian 1.5 * @version $Id: CoalescingToNoSSA.java,v 1.5 2004/02/08 01:53:14 cananian Exp $
42 cananian 1.1.2.1 */
43 cananian 1.1.2.1 public class CoalescingToNoSSA extends MethodMutator {
44 cananian 1.1.2.1
45 cananian 1.1.2.1 /** Creates a <code>CoalescingToNoSSA</code>. */
46 cananian 1.1.2.1 public CoalescingToNoSSA(HCodeFactory parent) {
47 cananian 1.1.2.1 super(parent);
48 cananian 1.1.2.1 }
49 cananian 1.1.2.1 private static class MyNoSSA extends QuadNoSSA {
50 cananian 1.1.2.1 private MyNoSSA(HMethod m) { super(m, null); }
51 cananian 1.1.2.1 public static HCodeAndMaps cloneToNoSSA(harpoon.IR.Quads.Code c,
52 cananian 1.1.2.1 HMethod m) {
53 cananian 1.1.2.1 MyNoSSA r = new MyNoSSA(m);
54 cananian 1.1.2.1 return r.cloneHelper(c, r);
55 cananian 1.1.2.1 }
56 cananian 1.1.2.1 }
57 cananian 1.1.2.1 protected String mutateCodeName(String codeName) {
58 cananian 1.3.2.1 assert codeName.equals(QuadSSA.codename) ||
59 cananian 1.1.2.1 codeName.equals(QuadSSI.codename) ||
60 cananian 1.3.2.1 codeName.equals(QuadRSSx.codename);
61 cananian 1.1.2.1 return MyNoSSA.codename;
62 cananian 1.1.2.1 }
63 cananian 1.1.2.1 protected HCodeAndMaps cloneHCode(HCode hc, HMethod newmethod) {
64 cananian 1.3.2.1 assert hc.getName().equals(QuadSSA.codename) ||
65 cananian 1.1.2.1 hc.getName().equals(QuadSSI.codename) ||
66 cananian 1.3.2.1 hc.getName().equals(QuadRSSx.codename);
67 cananian 1.1.2.1 return MyNoSSA.cloneToNoSSA((harpoon.IR.Quads.Code)hc, newmethod);
68 cananian 1.1.2.1 }
69 cananian 1.1.2.1 protected HCode mutateHCode(HCodeAndMaps input) {
70 cananian 1.1.2.1 Code hc = (Code) input.hcode();
71 cananian 1.3.2.1 assert hc.getName().equals(QuadNoSSA.codename);
72 cananian 1.1.2.1 QuadVisitor qv = new TransformVisitor(hc);
73 cananian 1.1.2.1 Quad[] qa = (Quad[]) hc.getElements();
74 cananian 1.1.2.1 for (int i=0; i<qa.length; i++)
75 cananian 1.1.2.1 qa[i].accept(qv);
76 cananian 1.1.2.1 return hc;
77 cananian 1.1.2.1 }
78 cananian 1.1.2.1 private static class RenameVisitor extends QuadVisitor {
79 cananian 1.1.2.1 public final DisjointSet ds = new DisjointSet();
80 cananian 1.1.2.1 public final QuadInterferenceGraph qig;
81 cananian 1.1.2.1 RenameVisitor(Code hc) {
82 cananian 1.1.2.1 this.qig = new QuadInterferenceGraph(hc);
83 cananian 1.1.2.1 for (Iterator it=hc.getElementsI(); it.hasNext(); )
84 cananian 1.1.2.1 ((Quad) it.next()).accept(this);
85 cananian 1.1.2.1 }
86 cananian 1.1.2.1 public void visit(Quad q) { /* do nothing */ }
87 cananian 1.1.2.1 public void visit(PHI q) {
88 cananian 1.1.2.1 for (int i=0; i<q.numPhis(); i++)
89 cananian 1.1.2.1 for (int j=0; j<q.arity(); j++)
90 cananian 1.1.2.1 if (!qig.isEdge(q.dst(i), q.src(i, j)))
91 cananian 1.1.2.1 if (!ds.find(q.dst(i)).equals(ds.find(q.src(i, j))))
92 cananian 1.1.2.1 ds.union(q.dst(i), q.src(i, j));
93 cananian 1.1.2.1 }
94 cananian 1.1.2.1 public void visit(SIGMA q) {
95 cananian 1.1.2.1 for (int i=0; i<q.numSigmas(); i++)
96 cananian 1.1.2.1 for (int j=0; j<q.arity(); j++)
97 cananian 1.1.2.1 if (!qig.isEdge(q.dst(i, j), q.src(i)))
98 cananian 1.1.2.1 if (!ds.find(q.dst(i, j)).equals(ds.find(q.src(i))))
99 cananian 1.1.2.1 ds.union(q.dst(i, j), q.src(i));
100 cananian 1.1.2.1 }
101 cananian 1.1.2.1 }
102 cananian 1.1.2.1 private static class TransformVisitor extends QuadVisitor {
103 cananian 1.1.2.1 public final TempMap tm;
104 cananian 1.1.2.1 TransformVisitor(Code hc) {
105 cananian 1.1.2.1 final DisjointSet ds = new RenameVisitor(hc).ds;
106 cananian 1.1.2.1 this.tm = new TempMap() {
107 cananian 1.1.2.1 public Temp tempMap(Temp t) {
108 cananian 1.1.2.1 return (Temp) ds.find(t);
109 cananian 1.1.2.1 }
110 cananian 1.1.2.1 };
111 cananian 1.1.2.1 }
112 cananian 1.1.2.1 private Edge addAt(Edge e, Quad q) { return addAt(e, 0, q, 0); }
113 cananian 1.1.2.1 private Edge addAt(Edge e, int which_pred, Quad q, int which_succ) {
114 cananian 1.1.2.1 Quad frm = (Quad) e.from(); int frm_succ = e.which_succ();
115 cananian 1.1.2.1 Quad to = (Quad) e.to(); int to_pred = e.which_pred();
116 cananian 1.1.2.1 Quad.addEdge(frm, frm_succ, q, which_pred);
117 cananian 1.1.2.1 Quad.addEdge(q, which_succ, to, to_pred);
118 cananian 1.1.2.1 return to.prevEdge(to_pred);
119 cananian 1.1.2.1 }
120 cananian 1.1.2.1 public void visit(Quad q) { Quad.replace(q, q.rename(tm, tm)); }
121 cananian 1.1.2.1 public void visit(HEADER q) { /* do nothing. */ }
122 cananian 1.1.2.1 public void visit(FOOTER q) { /* do nothing. */ }
123 cananian 1.1.2.1 public void visit(PHI q) {
124 cananian 1.1.2.1 QuadFactory qf = q.getFactory();
125 cananian 1.1.2.1 Quad nq = new PHI(qf, q, new Temp[0], q.arity());
126 cananian 1.1.2.1 Quad.replace(q, nq);
127 cananian 1.1.2.1 for (int i=0; i<q.numPhis(); i++)
128 cananian 1.1.2.1 for (int j=0; j<q.arity(); j++) {
129 cananian 1.1.2.1 Temp d = map(q.dst(i));
130 cananian 1.1.2.1 Temp s = map(q.src(i, j));
131 cananian 1.1.2.1 if (!d.equals(s))
132 cananian 1.1.2.1 addAt(nq.prevEdge(j), new MOVE(qf, q, d, s));
133 cananian 1.1.2.1 }
134 cananian 1.1.2.1 }
135 cananian 1.3.2.1 public void visit(SIGMA q) { assert false; }
136 cananian 1.1.2.1 private void dosigma(QuadFactory qf, SIGMA q, SIGMA nq) {
137 cananian 1.1.2.1 Quad.replace(q, nq);
138 cananian 1.1.2.1 for (int i=0; i<q.numSigmas(); i++)
139 cananian 1.1.2.1 for (int j=0; j<q.arity(); j++) {
140 cananian 1.1.2.1 Temp d = map(q.dst(i, j));
141 cananian 1.1.2.1 Temp s = map(q.src(i));
142 cananian 1.1.2.1 if (!d.equals(s))
143 cananian 1.1.2.1 addAt(nq.nextEdge(j), new MOVE(qf, q, d, s));
144 cananian 1.1.2.1 }
145 cananian 1.1.2.1 }
146 cananian 1.1.2.1 public void visit(CJMP q) {
147 cananian 1.1.2.1 QuadFactory qf = q.getFactory();
148 cananian 1.1.2.1 dosigma(qf, q, new CJMP(qf, q, map(q.test()), new Temp[0]));
149 cananian 1.1.2.1 }
150 cananian 1.1.2.1 public void visit(SWITCH q) {
151 cananian 1.1.2.1 QuadFactory qf = q.getFactory();
152 cananian 1.1.2.1 dosigma(qf, q, new SWITCH(qf, q, map(q.index()), q.keys(),
153 cananian 1.1.2.1 new Temp[0]));
154 cananian 1.1.2.1 }
155 cananian 1.1.2.1 public void visit(TYPESWITCH q) {
156 cananian 1.1.2.1 QuadFactory qf = q.getFactory();
157 cananian 1.1.2.1 dosigma(qf, q, new TYPESWITCH(qf, q, map(q.index()), q.keys(),
158 cananian 1.1.2.1 new Temp[0], q.hasDefault()));
159 cananian 1.1.2.1 }
160 cananian 1.1.2.1 public void visit(CALL q) {
161 cananian 1.1.2.1 QuadFactory qf = q.getFactory();
162 cananian 1.1.2.1 dosigma(qf, q, new CALL(qf, q, q.method(), map(q.params()),
163 cananian 1.1.2.1 map(q.retval()), map(q.retex()),
164 cananian 1.1.2.1 q.isVirtual(), q.isTailCall(),
165 cananian 1.1.2.1 new Temp[0]));
166 cananian 1.1.2.1 }
167 cananian 1.1.2.1 private Temp map(Temp t) { return (t==null) ? null : tm.tempMap(t); }
168 cananian 1.1.2.1 private Temp[] map(Temp[] ta) {
169 cananian 1.1.2.1 Temp[] r = new Temp[ta.length];
170 cananian 1.1.2.1 for (int i=0; i<r.length; i++)
171 cananian 1.1.2.1 r[i] = tm.tempMap(ta[i]);
172 cananian 1.1.2.1 return r;
173 cananian 1.1.2.1 }
174 cananian 1.1.2.1 }
175 cananian 1.2 }