1 cananian 1.1.2.1 // NewMover.java, created Wed Nov 7 22:20:28 2001 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.4 import harpoon.Analysis.Transformation.MethodMutator;
7 cananian 1.1.2.4 import harpoon.ClassFile.CachingCodeFactory;
8 cananian 1.1.2.4 import harpoon.ClassFile.HCode;
9 cananian 1.1.2.4 import harpoon.ClassFile.HCodeAndMaps;
10 cananian 1.1.2.4 import harpoon.ClassFile.HCodeFactory;
11 cananian 1.1.2.4 import harpoon.IR.Quads.CALL;
12 cananian 1.1.2.4 import harpoon.IR.Quads.Edge;
13 cananian 1.1.2.4 import harpoon.IR.Quads.FOOTER;
14 cananian 1.1.2.4 import harpoon.IR.Quads.HEADER;
15 cananian 1.1.2.4 import harpoon.IR.Quads.METHOD;
16 cananian 1.1.2.4 import harpoon.IR.Quads.MOVE;
17 cananian 1.1.2.4 import harpoon.IR.Quads.NEW;
18 cananian 1.1.2.4 import harpoon.IR.Quads.PHI;
19 cananian 1.1.2.4 import harpoon.IR.Quads.Quad;
20 cananian 1.1.2.4 import harpoon.IR.Quads.QuadVisitor;
21 cananian 1.1.2.4 import harpoon.IR.Quads.SIGMA;
22 cananian 1.1.2.4 import harpoon.Temp.Temp;
23 cananian 1.6 import net.cscott.jutil.GenericInvertibleMultiMap;
24 cananian 1.6 import net.cscott.jutil.InvertibleMultiMap;
25 cananian 1.6 import net.cscott.jutil.CombineIterator;
26 cananian 1.1.2.4 import harpoon.Util.Util;
27 cananian 1.1.2.1
28 cananian 1.1.2.4 import java.util.Collection;
29 cananian 1.1.2.4 import java.util.HashMap;
30 cananian 1.1.2.4 import java.util.HashSet;
31 cananian 1.1.2.4 import java.util.Iterator;
32 cananian 1.1.2.4 import java.util.Map;
33 cananian 1.1.2.4 import java.util.Set;
34 cananian 1.1.2.1 /**
35 cananian 1.1.2.1 * The <code>NewMover</code> class moves <code>NEW</code> operations
36 cananian 1.1.2.1 * as close as possible to the <code>CALL</code> to their initializers.
37 cananian 1.1.2.1 * In java bytecode, these two operations can be arbitrarily far apart
38 cananian 1.1.2.1 * in expressions such as:
39 cananian 1.1.2.1 * <ul><li><code>new Foo(new Bar(blah(), 2+5, ...), ...)</code></li></ul>
40 cananian 1.1.2.1 * <p>
41 cananian 1.1.2.1 * This movement is illegal if a <code>OutOfMemoryException</code> may
42 cananian 1.1.2.1 * ever be thrown, as moving the <code>NEW</code> changes where the
43 cananian 1.1.2.1 * exception would be thrown. However, FLEX operates under the assumption
44 cananian 1.1.2.1 * that such exceptions are never thrown.
45 cananian 1.1.2.1 * <p>
46 cananian 1.1.2.1 * <code>NewMover</code> works best on <code>QuadWithTry</code> form.
47 cananian 1.1.2.1 *
48 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
49 cananian 1.7 * @version $Id: NewMover.java,v 1.7 2004/02/08 03:20:10 cananian Exp $
50 cananian 1.1.2.1 */
51 cananian 1.1.2.1 public class NewMover extends MethodMutator {
52 cananian 1.1.2.4 /** If true, then the NewMover will attempt to move NEWs across SIGMAs.
53 cananian 1.1.2.4 * This yields better results when applied to QuadNoSSA form, but
54 cananian 1.1.2.4 * increases code size w/ no appreciable benefit on QuadWithTry form. */
55 cananian 1.1.2.5 private static final boolean movePastSigmas=false;
56 cananian 1.1.2.1 /** Creates a <code>NewMover</code> that uses the given
57 cananian 1.1.2.1 * <code>HCodeFactory</code> <code>hcf</code>. */
58 cananian 1.1.2.1 public NewMover(HCodeFactory hcf) {
59 cananian 1.1.2.1 super(new CachingCodeFactory(/*QuadWithTry.codeFactory*/(hcf)));
60 cananian 1.1.2.1 }
61 cananian 1.1.2.1 protected HCode mutateHCode(HCodeAndMaps input) {
62 cananian 1.1.2.1 HCode hc = input.hcode();
63 cananian 1.1.2.1 HEADER header = (HEADER) hc.getRootElement();
64 cananian 1.1.2.3 METHOD method = (METHOD) header.next(1);
65 cananian 1.1.2.3 // traverse all edges from method (handler blocks and regular code)
66 cananian 1.1.2.3 MoveVisitor mv = new MoveVisitor();
67 cananian 1.1.2.3 for (int i=0; i<method.nextLength(); i++) {
68 cananian 1.1.2.3 mv.state = new State();
69 cananian 1.1.2.3 traverseBlock(mv, method.nextEdge(i));
70 cananian 1.1.2.3 }
71 cananian 1.1.2.3 // done!
72 cananian 1.1.2.1 return hc;
73 cananian 1.1.2.1 }
74 cananian 1.1.2.1 // recursive traversal of all paths.
75 cananian 1.1.2.1 void traverseBlock(MoveVisitor mv, Edge in) {
76 cananian 1.1.2.1 mv.from = in;
77 cananian 1.1.2.1 mv.done = false;
78 cananian 1.1.2.1 while (!mv.done)
79 cananian 1.1.2.1 ((Quad)mv.from.to()).accept(mv);
80 cananian 1.1.2.1 // okay, recursively invoke on the one that stopped us.
81 cananian 1.1.2.1 Quad stopper = (Quad) mv.from.to();
82 cananian 1.1.2.1 if (stopper instanceof FOOTER) return; // end-of-the-line!
83 cananian 1.1.2.4 if (mv.seen.add(stopper)) {
84 cananian 1.1.2.4 // haven't started with this one before, so do it!
85 cananian 1.1.2.4 State s = mv.state;
86 cananian 1.1.2.4 for (int i=0; i<stopper.nextLength(); i++) {
87 cananian 1.1.2.4 mv.state = (i<stopper.nextLength()-1) ? new State(s) : s;
88 cananian 1.1.2.1 traverseBlock(mv, stopper.nextEdge(i));
89 cananian 1.1.2.4 }
90 cananian 1.3.2.1 } else assert stopper instanceof PHI;
91 cananian 1.1.2.1 }
92 cananian 1.1.2.2 static class State {
93 cananian 1.1.2.2 /** Set of NEWs we are moving, maintained as a map from dst->NEW. */
94 cananian 1.1.2.2 final Map moving;
95 cananian 1.1.2.2 /** MultiMap of aliases for a given Temp (defined by a NEW) */
96 cananian 1.1.2.2 final InvertibleMultiMap aliases;
97 cananian 1.1.2.2 State() {
98 cananian 1.1.2.2 this.moving=new HashMap();
99 cananian 1.1.2.2 this.aliases=new GenericInvertibleMultiMap();
100 cananian 1.1.2.2 }
101 cananian 1.1.2.2 State(State s) {
102 cananian 1.1.2.4 this.moving=new HashMap();
103 cananian 1.1.2.2 this.aliases=new GenericInvertibleMultiMap(s.aliases);
104 cananian 1.1.2.4 // copy/clone mappings from s.moving.
105 cananian 1.7 for (Object oldQO : s.moving.values()) {
106 cananian 1.7 NEW oldQ = (NEW) oldQO;
107 cananian 1.1.2.4 NEW newQ = (NEW) oldQ.clone();
108 cananian 1.1.2.4 newQ.addHandlers(oldQ.handlers());
109 cananian 1.1.2.4 this.moving.put(newQ.dst(), newQ);
110 cananian 1.1.2.4 }
111 cananian 1.1.2.2 }
112 cananian 1.6 public State clone() { return new State(this); }
113 cananian 1.1.2.4 public String toString() { return moving+" / "+aliases; }
114 cananian 1.1.2.2 }
115 cananian 1.1.2.1 class MoveVisitor extends QuadVisitor {
116 cananian 1.1.2.1 Edge from; boolean done;
117 cananian 1.1.2.2 State state = new State();
118 cananian 1.1.2.1 Set seen = new HashSet();
119 cananian 1.1.2.1 public void visit(Quad q) {
120 cananian 1.5 // if this quad uses or redefines any NEWs which are in 'moving',
121 cananian 1.1.2.2 // (or any temps which are in aliases.values())
122 cananian 1.1.2.2 // drop them before here. (MOVEs to aliases follow NEWs)
123 cananian 1.3.2.1 assert q.prevLength()==1;
124 cananian 1.1.2.1 Edge e = q.prevEdge(0);
125 cananian 1.5 for (Iterator it=new CombineIterator
126 cananian 1.5 (q.useC().iterator(), q.defC().iterator());
127 cananian 1.5 it.hasNext(); ) {
128 cananian 1.1.2.1 Temp t = (Temp) it.next();
129 cananian 1.1.2.2 if (!state.aliases.values().contains(t)) continue; //boring.
130 cananian 1.1.2.2 // unmap alias to canonical temp (defined by NEW)
131 cananian 1.1.2.2 Temp src = (Temp) state.aliases.invert().get(t);
132 cananian 1.3.2.1 assert state.aliases.invert().getValues(t).size()==1;
133 cananian 1.1.2.2 // dump it!
134 cananian 1.1.2.2 e = dumpOne(e, src);
135 cananian 1.1.2.2 state.moving.remove(src);
136 cananian 1.1.2.2 state.aliases.remove(src);
137 cananian 1.1.2.1 }
138 cananian 1.1.2.1 // done.
139 cananian 1.3.2.1 assert q.nextLength()==1;
140 cananian 1.1.2.1 from = q.nextEdge(0);
141 cananian 1.1.2.1 }
142 cananian 1.1.2.1 public void visit(NEW q) {
143 cananian 1.1.2.1 // pick this guy up
144 cananian 1.1.2.1 Edge in = q.prevEdge(0), out = q.nextEdge(0);
145 cananian 1.1.2.1 from = Quad.addEdge((Quad)in.from(), in.which_succ(),
146 cananian 1.1.2.1 (Quad)out.to(), out.which_pred());
147 cananian 1.1.2.1 // note that q is still in handler sets, which is what we want.
148 cananian 1.1.2.2 state.moving.put(q.dst(), q);
149 cananian 1.1.2.2 state.aliases.add(q.dst(), q.dst()); // always alias to itself.
150 cananian 1.1.2.1 }
151 cananian 1.1.2.1 public void visit(MOVE q) {
152 cananian 1.1.2.1 // if this MOVE uses the result of a NEW which we're moving,
153 cananian 1.1.2.1 // pick it up, too.
154 cananian 1.1.2.2 if (state.aliases.values().contains(q.src())) {
155 cananian 1.1.2.2 // get 'real' source (filter through inverted aliasMap)
156 cananian 1.1.2.2 Temp src = (Temp) state.aliases.invert().get(q.src());
157 cananian 1.1.2.2 // add a new alias.
158 cananian 1.1.2.2 state.aliases.add(src, q.dst());
159 cananian 1.1.2.2 // remove this guy.
160 cananian 1.1.2.2 from = q.remove();
161 cananian 1.1.2.1 } else visit((Quad) q); // fallback to boring.
162 cananian 1.1.2.1 }
163 cananian 1.1.2.2 Edge dumpOne(Edge e, Temp t) {
164 cananian 1.3.2.1 assert state.moving.containsKey(t);
165 cananian 1.1.2.2 // first dump the NEW
166 cananian 1.1.2.2 NEW qN = (NEW) state.moving.get(t);
167 cananian 1.1.2.2 e = addAt(e, qN);
168 cananian 1.1.2.2 // then dump all associated MOVEs.
169 cananian 1.3.2.1 Temp src = qN.dst(); assert t.equals(src);
170 cananian 1.7 for (Object dstO : state.aliases.getValues(src)) {
171 cananian 1.7 Temp dst = (Temp) dstO;
172 cananian 1.1.2.2 if (src.equals(dst)) continue;
173 cananian 1.1.2.2 // no handler for the MOVE, but we don't care.
174 cananian 1.1.2.2 e = addAt(e, new MOVE(qN.getFactory(), qN, dst, src));
175 cananian 1.1.2.2 }
176 cananian 1.1.2.2 // done!
177 cananian 1.1.2.2 return e;
178 cananian 1.1.2.2 }
179 cananian 1.1.2.1 void visitPhiSigma(Quad q) {
180 cananian 1.1.2.1 // stop here, dump all moving MOVEs and NEWs on 'from'
181 cananian 1.1.2.1 Edge e = from;
182 cananian 1.1.2.2 for (Iterator it=state.moving.keySet().iterator(); it.hasNext(); )
183 cananian 1.1.2.2 e = dumpOne(e, (Temp)it.next());
184 cananian 1.1.2.2 state.moving.clear();
185 cananian 1.1.2.2 state.aliases.clear();
186 cananian 1.1.2.1 }
187 cananian 1.1.2.1 public void visit(PHI q) {
188 cananian 1.1.2.1 visitPhiSigma(q);
189 cananian 1.1.2.1 if (seen.add(q))
190 cananian 1.1.2.1 // not seen before. keep going with next edge.
191 cananian 1.1.2.1 from = q.nextEdge(0);
192 cananian 1.1.2.1 else
193 cananian 1.1.2.1 // seen before. we're done with this.
194 cananian 1.1.2.1 done = true;
195 cananian 1.1.2.1 }
196 cananian 1.1.2.1 public void visit(SIGMA q) {
197 cananian 1.1.2.4 // keep state, but bail out of the iteration to recurse.
198 cananian 1.1.2.4 if (!movePastSigmas)
199 cananian 1.1.2.4 visitPhiSigma(q); // don't push past sigmas.
200 cananian 1.1.2.4 else { // check for vars used by sigma.
201 cananian 1.1.2.4 Edge e = from;
202 cananian 1.7 for (Object tO : q.useC()) {
203 cananian 1.7 Temp t = (Temp) tO;
204 cananian 1.1.2.4 if (!state.aliases.values().contains(t)) continue;//boring.
205 cananian 1.1.2.4 // unmap alias to canonical temp (defined by NEW)
206 cananian 1.1.2.4 Temp src = (Temp) state.aliases.invert().get(t);
207 cananian 1.3.2.1 assert state.aliases.invert().getValues(t).size()==1;
208 cananian 1.1.2.4 // dump it!
209 cananian 1.1.2.4 e = dumpOne(e, src);
210 cananian 1.1.2.4 state.moving.remove(src);
211 cananian 1.1.2.4 state.aliases.remove(src);
212 cananian 1.1.2.4 }
213 cananian 1.1.2.4 }
214 cananian 1.1.2.4 from = q.prevEdge(0);
215 cananian 1.1.2.1 done = true;
216 cananian 1.1.2.1 }
217 cananian 1.1.2.1 public void visit(CALL q) {
218 cananian 1.1.2.1 // calls aren't really sigmas in quad-with-try form.
219 cananian 1.1.2.1 if (q.retex()==null)
220 cananian 1.1.2.1 visit((Quad)q); // an ordinary joe.
221 cananian 1.1.2.1 else
222 cananian 1.1.2.1 visit((SIGMA)q); // a sigma!
223 cananian 1.1.2.1 }
224 cananian 1.1.2.1 public void visit(FOOTER q) {
225 cananian 1.1.2.1 // if we haven't used the MOVE/NEW by now, discard it.
226 cananian 1.7 for (Object qNO : state.moving.values()){
227 cananian 1.7 NEW qN = (NEW) qNO;
228 cananian 1.1.2.4 // remove the NEW from any handler sets, too.
229 cananian 1.1.2.4 qN.removeHandlers(qN.handlers());
230 cananian 1.1.2.4 }
231 cananian 1.1.2.2 state.moving.clear();
232 cananian 1.1.2.2 state.aliases.clear();
233 cananian 1.1.2.1 done=true;
234 cananian 1.1.2.1 }
235 cananian 1.1.2.1 }
236 cananian 1.1.2.1 // private helper functions.
237 cananian 1.1.2.1 private static Edge addAt(Edge e, Quad q) { return addAt(e, 0, q, 0); }
238 cananian 1.1.2.1 private static Edge addAt(Edge e, int which_pred, Quad q, int which_succ) {
239 cananian 1.1.2.1 Quad frm = (Quad) e.from(); int frm_succ = e.which_succ();
240 cananian 1.1.2.1 Quad to = (Quad) e.to(); int to_pred = e.which_pred();
241 cananian 1.1.2.1 Quad.addEdge(frm, frm_succ, q, which_pred);
242 cananian 1.1.2.1 Quad.addEdge(q, which_succ, to, to_pred);
243 cananian 1.1.2.1 return to.prevEdge(to_pred);
244 cananian 1.1.2.1 }
245 cananian 1.1.2.1 private static Edge addReversedAt(Edge e, Quad q) {
246 cananian 1.1.2.1 return addReversedAt(e, 0, q, 0);
247 cananian 1.1.2.1 }
248 cananian 1.1.2.1 private static Edge addReversedAt(Edge e,
249 cananian 1.1.2.1 int which_pred, Quad q, int which_succ) {
250 cananian 1.1.2.1 Quad frm = (Quad) e.from(); int frm_succ = e.which_succ();
251 cananian 1.1.2.1 Quad to = (Quad) e.to(); int to_pred = e.which_pred();
252 cananian 1.1.2.1 Quad.addEdge(frm, frm_succ, q, which_pred);
253 cananian 1.1.2.1 Quad.addEdge(q, which_succ, to, to_pred);
254 cananian 1.1.2.1 return frm.nextEdge(frm_succ);
255 cananian 1.1.2.1 }
256 cananian 1.2 }