1 cananian 1.1.2.4 // Peephole.java, created Sun Dec 27 19:37:24 1998 by cananian
2 cananian 1.1.2.7 // Copyright (C) 1998 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.7 // 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.Temp.Temp;
7 cananian 1.1.2.4 import harpoon.Temp.TempMap;
8 bdemsky 1.1.2.11 import harpoon.Util.Tuple;
9 cananian 1.5 import net.cscott.jutil.UniqueStack;
10 cananian 1.1.2.4 import harpoon.Util.Util;
11 cananian 1.1.2.4
12 cananian 1.1.2.14 import java.util.HashSet;
13 bdemsky 1.1.2.11 import java.util.Map;
14 cananian 1.1.2.14 import java.util.Set;
15 cananian 1.1.2.1 /**
16 cananian 1.1.2.4 * <code>Peephole</code> performs peephole optimizations (mostly
17 cananian 1.1.2.4 * <code>MOVE</code> collation) on <code>QuadWithTry</code> and
18 cananian 1.1.2.4 * <code>QuadNoSSA</code> forms.
19 cananian 1.1.2.1 *
20 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
21 cananian 1.5 * @version $Id: Peephole.java,v 1.5 2004/02/08 01:55:25 cananian Exp $
22 cananian 1.1.2.1 */
23 cananian 1.1.2.1
24 cananian 1.1.2.4 final class Peephole {
25 cananian 1.1.2.4 final static void normalize(Quad head) {
26 cananian 1.1.2.19 SwapVisitor sv = new SwapVisitor(null, head);
27 cananian 1.1.2.4 sv.optimize(head); // usually things are screwy after trans.
28 cananian 1.1.2.1 }
29 bdemsky 1.1.2.11
30 bdemsky 1.1.2.11 final static void normalize(Quad head, Map typemap) {
31 cananian 1.1.2.19 SwapVisitor sv = new SwapVisitor(typemap, head);
32 bdemsky 1.1.2.11 sv.optimize(head); // usually things are screwy after trans.
33 bdemsky 1.1.2.11 }
34 bdemsky 1.1.2.11
35 cananian 1.1.2.20 final static void optimize(Quad head) {
36 cananian 1.1.2.20 optimize(head, null);
37 bdemsky 1.1.2.11 }
38 bdemsky 1.1.2.11
39 cananian 1.1.2.20 final static void optimize(Quad head, Map typemap) {
40 cananian 1.1.2.19 PeepholeVisitor pv = new PeepholeVisitor(typemap, head);
41 cananian 1.1.2.4 while (pv.optimize(head))
42 cananian 1.1.2.4 /*repeat*/;
43 cananian 1.1.2.4 }
44 bdemsky 1.1.2.11
45 cananian 1.1.2.19 private static class CheckStack extends UniqueStack {
46 cananian 1.1.2.19 public void push(Object o) {
47 cananian 1.3.2.1 assert o!=null;
48 cananian 1.1.2.4 Quad[] ql = ((Quad)o).next();
49 cananian 1.1.2.4 for (int i=0; i<ql.length; i++)
50 cananian 1.3.2.1 assert ql[i]!=null;
51 cananian 1.1.2.19 super.push(o);
52 cananian 1.1.2.1 }
53 cananian 1.1.2.4 }
54 cananian 1.1.2.4 private abstract static class SuperVisitor extends QuadVisitor {
55 cananian 1.1.2.19 final METHOD method;
56 cananian 1.1.2.19 SuperVisitor(Quad head) { this.method = (METHOD) head.next(1); }
57 cananian 1.1.2.19
58 cananian 1.1.2.19 final UniqueStack todo = new CheckStack();
59 pnkfelix 1.1.2.6 final Set visited = new HashSet();
60 cananian 1.1.2.4 boolean changed = false;
61 cananian 1.1.2.4
62 cananian 1.1.2.4 public boolean optimize(Quad head) {
63 cananian 1.1.2.4 changed = false;
64 cananian 1.1.2.19 todo.clear();
65 cananian 1.1.2.4 visited.clear();
66 cananian 1.1.2.4
67 cananian 1.1.2.4 todo.push(head);
68 cananian 1.1.2.4 while (!todo.empty()) {
69 cananian 1.1.2.4 Quad q = (Quad) todo.pop();
70 cananian 1.1.2.4 if (!visited.contains(q)) {
71 cananian 1.1.2.9 q.accept(this);
72 cananian 1.1.2.4 }
73 cananian 1.1.2.4 }
74 cananian 1.1.2.4 return changed;
75 cananian 1.1.2.4 }
76 cananian 1.1.2.19 protected boolean sameHandlers(Quad q1, Quad q2) {
77 cananian 1.1.2.19 for (int i=1; i<method.nextLength(); i++) {
78 cananian 1.1.2.19 HANDLER handler = (HANDLER) method.next(i);
79 cananian 1.1.2.19 if (handler.isProtected(q1) != handler.isProtected(q2))
80 cananian 1.1.2.19 return false;
81 cananian 1.1.2.19 }
82 cananian 1.1.2.19 return true;
83 cananian 1.1.2.19 }
84 cananian 1.1.2.4 }
85 cananian 1.1.2.4 private final static class SwapVisitor extends SuperVisitor {
86 bdemsky 1.1.2.11 private Map typemap;
87 bdemsky 1.1.2.11
88 cananian 1.1.2.19 public SwapVisitor(Map typemap, Quad head) {
89 cananian 1.1.2.19 super(head);
90 bdemsky 1.1.2.11 this.typemap=typemap;
91 bdemsky 1.1.2.11 }
92 bdemsky 1.1.2.11
93 cananian 1.1.2.4 public void visit(Quad q) {
94 cananian 1.1.2.4 Quad[] ql=q.next();
95 cananian 1.1.2.19 // very specific case for swaparoo:
96 cananian 1.1.2.19 // tA = oper .. -\ tB = oper ..
97 cananian 1.1.2.19 // tB = MOVE tA -/ tA = MOVE tB
98 cananian 1.1.2.19 // ONLY VALID IF BOTH ARE IN SAME HANDLER CONTEXT!
99 cananian 1.1.2.4 if (ql.length==1 && ql[0] instanceof MOVE &&
100 bdemsky 1.1.2.17 !(q instanceof METHOD) && q.def().length==1 &&
101 cananian 1.1.2.19 q.def()[0]==((MOVE)ql[0]).src() &&
102 cananian 1.1.2.19 sameHandlers(q, ql[0])) {
103 cananian 1.1.2.4 MOVE Qm = (MOVE)ql[0];
104 cananian 1.1.2.4 TempMap tm0 = new OneToOneMap(Qm.src(), Qm.dst());
105 cananian 1.1.2.4 TempMap tm1 = new OneToOneMap(Qm.dst(), Qm.src());
106 cananian 1.1.2.4 Quad q1 = q.rename(q.qf, tm0, null);
107 cananian 1.1.2.4 Quad q2 = Qm.rename(Qm.qf, tm1, tm0);
108 bdemsky 1.1.2.11 if (typemap!=null) {
109 bdemsky 1.1.2.11 typemap.put(new Tuple(new Object[]{q1,Qm.dst() }),
110 bdemsky 1.1.2.11 typemap.get(new Tuple(new Object[]{Qm, Qm.dst()})));
111 bdemsky 1.1.2.11 Temp uses[]=q.use();
112 bdemsky 1.1.2.11 for (int i=0;i<uses.length;i++)
113 bdemsky 1.1.2.11 typemap.put(new Tuple(new Object[]{q1, uses[i]}),
114 bdemsky 1.1.2.11 typemap.get(new Tuple(new Object[] {q, uses[i]})));
115 bdemsky 1.1.2.11 typemap.put(new Tuple(new Object[]{q2, Qm.src()}),
116 bdemsky 1.1.2.11 typemap.get(new Tuple(new Object[] {Qm, Qm.src()})));
117 bdemsky 1.1.2.11 typemap.put(new Tuple(new Object[]{q2, Qm.dst()}),
118 bdemsky 1.1.2.11 typemap.get(new Tuple(new Object[] {Qm, Qm.dst()})));
119 bdemsky 1.1.2.11
120 bdemsky 1.1.2.11 }
121 cananian 1.1.2.12 replace(q, q1);
122 cananian 1.1.2.12 replace(Qm, q2);
123 cananian 1.1.2.14 visited.add(q1); visited.add(q2);
124 cananian 1.1.2.4 todo.push(q2.next(0));
125 cananian 1.1.2.4 changed=true;
126 cananian 1.1.2.4 } else {
127 cananian 1.1.2.4 // garden variety instruction.
128 cananian 1.1.2.4 for (int i=0; i<ql.length; i++)
129 cananian 1.1.2.4 todo.push(ql[i]);
130 cananian 1.1.2.14 visited.add(q);
131 cananian 1.1.2.4 }
132 cananian 1.1.2.4 }
133 cananian 1.1.2.4 }
134 cananian 1.1.2.4 private final static class PeepholeVisitor extends SuperVisitor {
135 bdemsky 1.1.2.11 private Map typemap;
136 bdemsky 1.1.2.11
137 cananian 1.1.2.19 PeepholeVisitor(Map typemap, Quad head) {
138 cananian 1.1.2.19 super(head);
139 bdemsky 1.1.2.11 this.typemap=typemap;
140 bdemsky 1.1.2.11 }
141 bdemsky 1.1.2.11
142 cananian 1.1.2.4 public void visit(Quad q) {
143 cananian 1.1.2.4 Quad[] ql=q.next();
144 cananian 1.1.2.4 for (int i=0; i<ql.length; i++)
145 cananian 1.1.2.4 todo.push(ql[i]);
146 cananian 1.1.2.14 visited.add(q);
147 cananian 1.1.2.4 }
148 bdemsky 1.1.2.11
149 bdemsky 1.1.2.11 void fixmap(Quad old, Quad newq, TempMap tm) {
150 bdemsky 1.1.2.11 if (typemap!=null) {
151 bdemsky 1.1.2.11 Temp[] defs=old.def();
152 bdemsky 1.1.2.11 for (int i=0;i<defs.length;i++) {
153 bdemsky 1.1.2.11 typemap.put(new Tuple(new Object[]{newq, defs[i]}),
154 bdemsky 1.1.2.11 typemap.get(new Tuple(new Object[]{old, defs[i]})));
155 bdemsky 1.1.2.11 }
156 bdemsky 1.1.2.11 Temp[] uses=old.use();
157 bdemsky 1.1.2.11 for (int i=0;i<uses.length;i++) {
158 bdemsky 1.1.2.13 if (tm==null)
159 bdemsky 1.1.2.11 typemap.put(new Tuple(new Object[]{newq, uses[i]}),
160 bdemsky 1.1.2.11 typemap.get(new Tuple(new Object[]{old, uses[i]})));
161 bdemsky 1.1.2.11 else
162 bdemsky 1.1.2.11 typemap.put(new Tuple(new Object[]{newq, tm.tempMap(uses[i])}),
163 bdemsky 1.1.2.11 typemap.get(new Tuple(new Object[]{old, uses[i]})));
164 bdemsky 1.1.2.11 }
165 bdemsky 1.1.2.11 }
166 bdemsky 1.1.2.11 }
167 bdemsky 1.1.2.11
168 cananian 1.1.2.4 public void visit(final MOVE q) {
169 cananian 1.1.2.4 final Quad Qnext = q.next(0);
170 cananian 1.1.2.4 if (q.dst() == q.src()) {
171 cananian 1.1.2.4 // dst==src, delete.
172 cananian 1.1.2.4 todo.push(unlink(q));
173 cananian 1.1.2.4 changed=true;
174 cananian 1.1.2.4 } else if (isMember(q.dst(), Qnext.def())) {
175 cananian 1.1.2.4 // rename Qnext & delete MOVE.
176 cananian 1.1.2.4 TempMap tm = new OneToOneMap(q.dst(), q.src());
177 bdemsky 1.1.2.11 Quad newquad=Qnext.rename(Qnext.qf, null, tm);
178 bdemsky 1.1.2.11 fixmap(Qnext, newquad, tm);
179 cananian 1.1.2.12 replace(Qnext, newquad);
180 cananian 1.1.2.4 // unlink MOVE
181 cananian 1.1.2.4 todo.push(unlink(q));
182 cananian 1.1.2.4 changed=true;
183 cananian 1.1.2.4 } else {
184 cananian 1.1.2.4 // see if we can move the MOVE forward.
185 cananian 1.1.2.4 // (we can move it ahead until someone redefines our src/def)
186 cananian 1.1.2.4 Quad Qp; boolean pastNonMove=false;
187 cananian 1.1.2.4 boolean moveit=false, deleteit=false;
188 cananian 1.1.2.10 for (Qp=Qnext; true; Qp=Qp.next(0)) {
189 cananian 1.1.2.4 if (Qp instanceof FOOTER) {
190 cananian 1.1.2.4 // move isn't useful after return!
191 cananian 1.1.2.4 deleteit=true;
192 cananian 1.1.2.4 break;
193 cananian 1.1.2.4 }
194 cananian 1.1.2.19 // we stop as soon as we come to:
195 cananian 1.1.2.19 // - a quad belonging to a different handler set
196 cananian 1.1.2.19 // - a PHI or SIGMA (only optimize within basic blocks)
197 cananian 1.1.2.19 // - a statement which destroys the source temp
198 cananian 1.1.2.19 if (!sameHandlers(q, Qp) ||
199 cananian 1.1.2.19 Qp instanceof PHI || Qp instanceof SIGMA ||
200 cananian 1.1.2.19 isMember(q.src(), Qp.def())) {
201 cananian 1.1.2.4 if (pastNonMove) moveit=true;
202 cananian 1.1.2.19 // enable more moves
203 cananian 1.1.2.19 //if (Qp instanceof SIGMA) moveit=true;
204 cananian 1.1.2.4 break;
205 cananian 1.1.2.4 }
206 cananian 1.1.2.19
207 cananian 1.1.2.4 if (isMember(q.dst(), Qp.def())) {
208 cananian 1.1.2.4 // destroys def, so move isn't useful anymore.
209 cananian 1.1.2.4 if (pastNonMove) moveit=true;
210 cananian 1.1.2.4 // BE CAREFUL: Qp may *use* q.dst(), so 'deleteit' is
211 cananian 1.1.2.4 // not correct.
212 cananian 1.1.2.4 break;
213 cananian 1.1.2.4 }
214 cananian 1.1.2.4 if (!(Qp instanceof MOVE)) pastNonMove=true;
215 cananian 1.1.2.4 }
216 cananian 1.1.2.10 // we're going to unlink and move this quad if:
217 cananian 1.1.2.10 // -- moveit is true, or
218 cananian 1.1.2.10 // -- deleteit is true, or
219 cananian 1.1.2.10 // -- Qp is a 'safe' sigma function where safe means:
220 cananian 1.1.2.19 // - belongs to same handlers as q
221 cananian 1.1.2.10 // note that we'll move quads even if Qp is unsafe, if
222 cananian 1.1.2.10 // moveit is true. deleteit can't be true if Qp is a
223 cananian 1.1.2.10 // SIGMA.
224 cananian 1.1.2.19 if (moveit || deleteit) {
225 cananian 1.1.2.4 TempMap tm = new OneToOneMap(q.dst(), q.src());
226 cananian 1.1.2.4 Edge lstE;
227 cananian 1.1.2.4 for (lstE=q.nextEdge(0); lstE.to() != Qp; ) {
228 cananian 1.1.2.4 Quad qq = (Quad)lstE.to();
229 bdemsky 1.1.2.11 Quad newquad=qq.rename(qq.qf, null, tm);
230 bdemsky 1.1.2.11 fixmap(qq,newquad,tm);
231 cananian 1.1.2.12 replace(qq, newquad);
232 cananian 1.1.2.4 lstE=((Quad)lstE.from()).next(0).nextEdge(0);
233 cananian 1.1.2.4 }
234 cananian 1.1.2.15 HandlerSet hs=q.handlers();
235 cananian 1.1.2.4 todo.push(unlink(q));
236 cananian 1.1.2.10 // usually we relink the MOVE quad before Qp, but
237 cananian 1.1.2.10 // we'll relink *after* a sigma if we can -- this
238 cananian 1.1.2.10 // helps keep the MOVEs propagating. Relink *after*
239 cananian 1.1.2.10 // if sigma doesn't redefine the source of the MOVE
240 cananian 1.1.2.19 // and if sigma belongs to the same handler region.
241 cananian 1.1.2.19 if (Qp instanceof SIGMA && sameHandlers(q, Qp) &&
242 cananian 1.1.2.10 !(Qp instanceof CALL &&
243 cananian 1.1.2.10 (q.src()==((CALL)Qp).retval() ||
244 cananian 1.1.2.10 q.src()==((CALL)Qp).retex()))) {
245 cananian 1.1.2.4 SIGMA Qs = (SIGMA) Qp.rename(Qp.qf, null, tm);
246 bdemsky 1.1.2.11 fixmap(Qp, Qs, tm);
247 cananian 1.1.2.4 todo.removeElement(Qp); // remove old SIGMA from todo
248 cananian 1.1.2.12 replace(Qp, Qs);
249 cananian 1.1.2.10 // we can just delete the MOVE if the CALL
250 cananian 1.1.2.10 // overwrites the destination.
251 cananian 1.1.2.10 if (Qp instanceof CALL &&
252 cananian 1.1.2.10 (q.dst() == ((CALL)Qp).retval() ||
253 cananian 1.1.2.10 q.dst() == ((CALL)Qp).retex())) {
254 cananian 1.1.2.10 // the move is gone & we don't need it any mo'
255 cananian 1.1.2.10 changed=true;
256 cananian 1.1.2.10 return;
257 cananian 1.1.2.10 }
258 cananian 1.1.2.4 Edge[] el = Qs.nextEdge();
259 cananian 1.1.2.4 for (int i=0; i<el.length; i++) {
260 cananian 1.1.2.4 MOVE Qm = (i==0) ? q : (MOVE)q.clone();
261 bdemsky 1.1.2.13 if (i!=0)
262 bdemsky 1.1.2.13 fixmap(q, Qm, null);
263 cananian 1.1.2.4 Quad.addEdge((Quad)el[i].from(),el[i].which_succ(),
264 cananian 1.1.2.4 Qm, 0);
265 cananian 1.1.2.4 Quad.addEdge(Qm, 0,
266 cananian 1.1.2.4 (Quad)el[i].to(), el[i].which_pred());
267 cananian 1.1.2.4 // those nasty HANDLERs
268 cananian 1.1.2.15 Qm.addHandlers(hs);
269 cananian 1.1.2.4 }
270 cananian 1.1.2.4 } else if (moveit) { // relink before Qend
271 cananian 1.1.2.4 Quad.addEdge((Quad)lstE.from(),lstE.which_succ(), q,0);
272 cananian 1.1.2.4 Quad.addEdge(q,0, (Quad)lstE.to(), lstE.which_pred());
273 cananian 1.1.2.15 q.addHandlers(hs);
274 cananian 1.3.2.1 } else assert deleteit;
275 cananian 1.1.2.4 changed=true;
276 cananian 1.1.2.4 } else {
277 cananian 1.1.2.4 // do nothing.
278 cananian 1.1.2.14 visited.add(q);
279 cananian 1.1.2.4 todo.push(Qnext);
280 cananian 1.1.2.4 }
281 cananian 1.1.2.4 }
282 cananian 1.1.2.4 }
283 cananian 1.1.2.4 private static Quad unlink(Quad q) {
284 cananian 1.1.2.4 Edge in = q.prevEdge(0), out = q.nextEdge(0);
285 cananian 1.1.2.4 Quad.addEdge((Quad)in.from(), in.which_succ(),
286 cananian 1.1.2.4 (Quad)out.to(), out.which_pred());
287 cananian 1.1.2.15 q.removeHandlers(q.handlers());
288 cananian 1.1.2.4 return (Quad)out.to();
289 cananian 1.1.2.4 }
290 cananian 1.1.2.4 private static boolean isMember(Temp t, Temp[] Tset) {
291 cananian 1.1.2.4 for (int i=0; i<Tset.length; i++)
292 cananian 1.1.2.4 if (t == Tset[i]) return true;
293 cananian 1.1.2.4 return false;
294 cananian 1.1.2.4 }
295 cananian 1.1.2.4 }
296 cananian 1.1.2.12 // replace oldQ with newQ, updating handlers, too.
297 cananian 1.1.2.12 private static void replace(Quad oldQ, Quad newQ) {
298 cananian 1.1.2.12 Quad.replace(oldQ, newQ);
299 cananian 1.1.2.12 Quad.transferHandlers(oldQ, newQ);
300 cananian 1.1.2.12 }
301 cananian 1.1.2.12 // simple temp mapping.
302 cananian 1.1.2.4 private static class OneToOneMap implements TempMap {
303 cananian 1.1.2.4 final Temp from;
304 cananian 1.1.2.4 final Temp to;
305 cananian 1.1.2.4 OneToOneMap(Temp from, Temp to) { this.from=from; this.to=to; }
306 cananian 1.1.2.4 public Temp tempMap(Temp t) { return (t==from) ? to : t; }
307 cananian 1.1.2.1 }
308 cananian 1.2 }