1 cananian 1.1 // SyncRemover.java, created Wed Jul 9 11:57:51 2003 by cananian
2 cananian 1.1 // Copyright (C) 2003 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1 package harpoon.Analysis.DynamicSyncRemoval;
5 cananian 1.1
6 cananian 1.4 import harpoon.Analysis.AllocationInformationMap;
7 cananian 1.4 import harpoon.Analysis.Maps.AllocationInformation;
8 cananian 1.1 import harpoon.Backend.Generic.Frame;
9 cananian 1.1 import harpoon.ClassFile.CachingCodeFactory;
10 cananian 1.1 import harpoon.ClassFile.HClass;
11 cananian 1.1 import harpoon.ClassFile.HCode;
12 cananian 1.1 import harpoon.ClassFile.HCodeAndMaps;
13 cananian 1.1 import harpoon.ClassFile.HCodeFactory;
14 cananian 1.1 import harpoon.ClassFile.HMethod;
15 cananian 1.1 import harpoon.ClassFile.Linker;
16 cananian 1.4 import harpoon.IR.Quads.ANEW;
17 cananian 1.1 import harpoon.IR.Quads.CALL;
18 cananian 1.1 import harpoon.IR.Quads.CJMP;
19 cananian 1.4 import harpoon.IR.Quads.Code;
20 cananian 1.1 import harpoon.IR.Quads.Edge;
21 cananian 1.1 import harpoon.IR.Quads.HEADER;
22 cananian 1.1 import harpoon.IR.Quads.METHOD;
23 cananian 1.1 import harpoon.IR.Quads.MONITORENTER;
24 cananian 1.1 import harpoon.IR.Quads.MONITOREXIT;
25 cananian 1.4 import harpoon.IR.Quads.NEW;
26 cananian 1.1 import harpoon.IR.Quads.PHI;
27 cananian 1.1 import harpoon.IR.Quads.Quad;
28 cananian 1.1 import harpoon.IR.Quads.QuadFactory;
29 cananian 1.1 import harpoon.IR.Quads.QuadNoSSA;
30 cananian 1.1 import harpoon.IR.Quads.QuadValueVisitor;
31 cananian 1.1 import harpoon.Temp.Temp;
32 cananian 1.1 import harpoon.Temp.TempFactory;
33 cananian 1.1 import harpoon.Temp.TempMap;
34 cananian 1.5 import net.cscott.jutil.WorkSet;
35 cananian 1.1 import java.util.ArrayList;
36 cananian 1.1 import java.util.Arrays;
37 cananian 1.1 import java.util.Collection;
38 cananian 1.1 import java.util.HashSet;
39 cananian 1.1 import java.util.Iterator;
40 cananian 1.1 import java.util.LinkedHashMap;
41 cananian 1.1 import java.util.List;
42 cananian 1.1 import java.util.Map;
43 cananian 1.1 import java.util.Set;
44 cananian 1.1
45 cananian 1.1 /**
46 cananian 1.1 * <code>SyncRemover</code> calls a "magic" native method to determine
47 cananian 1.1 * if synchronization should be done on this object, and skips the
48 cananian 1.1 * <code>MONITORENTER</code>/<code>MONITOREXIT</code> sequence if the
49 cananian 1.1 * answer is no. We need to duplication and split the code between
50 cananian 1.1 * <code>MONITORENTER</code> and <code>MONITOREXIT</code> for this to
51 cananian 1.1 * play nicely with the Transactions transformation.
52 cananian 1.1 *
53 cananian 1.1 * For best results, run <code>TreePostPass</code> after this
54 cananian 1.1 * transformation.
55 cananian 1.1 *
56 cananian 1.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
57 cananian 1.6 * @version $Id: SyncRemover.java,v 1.6 2004/02/08 03:19:25 cananian Exp $
58 cananian 1.1 */
59 cananian 1.1 public class SyncRemover
60 cananian 1.1 extends harpoon.Analysis.Transformation.MethodMutator<Quad> {
61 cananian 1.1 private final HMethod checkMethod;
62 cananian 1.1
63 cananian 1.1 /** Creates a <code>SyncRemover</code>. */
64 cananian 1.1 public SyncRemover(HCodeFactory parent, Linker l) {
65 cananian 1.1 // force a caching quad-no-ssa code factory.
66 cananian 1.1 this(new CachingCodeFactory(QuadNoSSA.codeFactory(parent)), l);
67 cananian 1.1 }
68 cananian 1.1 /** The private constructor knows that the code factory is cached and
69 cananian 1.1 * produces quad-no-ssa form. */
70 cananian 1.1 private SyncRemover(CachingCodeFactory parent, Linker l) {
71 cananian 1.1 super(parent);
72 cananian 1.1 // get the reference to the discriminator method.
73 cananian 1.2 checkMethod = l.forName("harpoon.Runtime.DynamicSyncImpl")
74 cananian 1.3 .getMethod("isNoSync",new HClass[]{l.forName("java.lang.Object")});
75 cananian 1.1 }
76 cananian 1.1 /** Return an <code>HCodeFactory</code> that will clean up the
77 cananian 1.1 * tree form of the transformed code by performing some optimizations
78 cananian 1.1 * which can't be represented in quad form. */
79 cananian 1.1 public static HCodeFactory treeCodeFactory(Frame f, HCodeFactory hcf) {
80 cananian 1.1 return new TreeCallOpt(f).codeFactory(hcf);
81 cananian 1.1 }
82 cananian 1.1 protected HCode<Quad> mutateHCode(HCodeAndMaps<Quad> input) {
83 cananian 1.1 Code hc = (Code) input.hcode();
84 cananian 1.1 METHOD qM = hc.getRootElement().method();
85 cananian 1.4 AllocationInformationMap aim = (AllocationInformationMap)//heh heh
86 cananian 1.4 hc.getAllocationInformation();
87 cananian 1.1 // recursively traverse graph, rewriting as we go.
88 cananian 1.4 munge(new Munger(qM.getFactory(), aim), qM);
89 cananian 1.1 return hc;
90 cananian 1.1 }
91 cananian 1.1 private void munge(Munger munger, Quad start) {
92 cananian 1.1 WorkSet<Quad> toDo = new WorkSet<Quad>();
93 cananian 1.1 Set<Quad> done = new HashSet<Quad>();
94 cananian 1.1 toDo.add(start);
95 cananian 1.1 while (!toDo.isEmpty()) {
96 cananian 1.1 Quad q = toDo.removeFirst();
97 cananian 1.1 if (done.contains(q)) continue;
98 cananian 1.6 for (Edge e : q.accept(munger)){
99 cananian 1.1 toDo.add(e.to());
100 cananian 1.1 }
101 cananian 1.1 done.add(q);
102 cananian 1.1 }
103 cananian 1.1 }
104 cananian 1.1
105 cananian 1.1 private class Munger extends QuadValueVisitor<Collection<Edge>> {
106 cananian 1.1 final Collection<Edge> NO_EDGES = Arrays.asList(new Edge[0]);
107 cananian 1.4 final AllocationInformationMap aim;
108 cananian 1.1 final QuadFactory qf;
109 cananian 1.1 final TempFactory tf;
110 cananian 1.4 Munger(QuadFactory qf, AllocationInformationMap aim) {
111 cananian 1.1 this.qf = qf;
112 cananian 1.1 this.tf = qf.tempFactory();
113 cananian 1.4 this.aim = aim;
114 cananian 1.1 }
115 cananian 1.1
116 cananian 1.1 public Collection<Edge> visit(Quad q) {
117 cananian 1.1 return q.succC();
118 cananian 1.1 }
119 cananian 1.1 public Collection<Edge> visit(MONITOREXIT q) {
120 cananian 1.1 // don't visit beyond a monitorexit.
121 cananian 1.1 return NO_EDGES;
122 cananian 1.1 }
123 cananian 1.1 public Collection<Edge> visit(MONITORENTER q) {
124 cananian 1.1 // rewrite this monitor enter, recurse into contents, and
125 cananian 1.1 // then continue after block.
126 cananian 1.1
127 cananian 1.1 Collection<Edge> result = new ArrayList<Edge>();
128 cananian 1.1 // rewrite contents.
129 cananian 1.1 munge(this, q.next(0));
130 cananian 1.1 // now copy contents
131 cananian 1.4 CopyInfo ci = copyGraph(q, aim);
132 cananian 1.1 // now rewrite as follows:
133 cananian 1.1
134 cananian 1.1 // MONITORENTER(lock)
135 cananian 1.1 // statements
136 cananian 1.1 // MONITOREXIT(lock)
137 cananian 1.1 // --- becomes ---
138 cananian 1.1 // if (isSync(lock)) {
139 cananian 1.1 // MONITORENTER(lock)
140 cananian 1.1 // statements
141 cananian 1.1 // MONITOREXIT(lock)
142 cananian 1.1 // } else {
143 cananian 1.1 // statements
144 cananian 1.1 // }
145 cananian 1.3 Temp retval = new Temp(tf, "isNoSync");
146 cananian 1.1 Temp retex = new Temp(tf, "ignore");
147 cananian 1.1 Edge in = q.prevEdge(0);
148 cananian 1.1 CALL q0 = new CALL(qf, q, checkMethod, new Temp[] { q.lock() },
149 cananian 1.1 retval, retex, false, false, new Temp[0]);
150 cananian 1.2 CJMP q1 = new CJMP(qf, q, retval, new Temp[0]);
151 cananian 1.2 PHI q2 = new PHI(qf, q, new Temp[0], 2);
152 cananian 1.1 in = addAt(in, q0);
153 cananian 1.3 in = addAt(in, q1); // monitorenter on 'false' edge
154 cananian 1.2 in = addAt(in, q2);
155 cananian 1.2 Quad.addEdge(q0, 1, q2, 1);
156 cananian 1.3 // add edge past copied monitorenter on 'true' edge.
157 cananian 1.1 Edge e = ci.start.copy.nextEdge(0);
158 cananian 1.3 Quad.addEdge(q1, 1, e.to(), e.which_pred());
159 cananian 1.1
160 cananian 1.1 // now for every MONITOREXIT in copyMap, add a phi like so:
161 cananian 1.1 //
162 cananian 1.1 // orig1 orig1 ...
163 cananian 1.1 // \ \ /
164 cananian 1.1 // MONITOREXIT -> MONITOREXIT copy1
165 cananian 1.1 // \ \ /
166 cananian 1.1 // orig2 PHI
167 cananian 1.1 // |
168 cananian 1.1 // orig2
169 cananian 1.6 for (CopyPair<MONITOREXIT> exit : ci.endList) {
170 cananian 1.1 PHI qP = new PHI(qf, exit.orig, new Temp[0], 2);
171 cananian 1.1 addAt(exit.orig.nextEdge(0), qP);
172 cananian 1.1 // now add edge from before copied monitorexit
173 cananian 1.1 Edge ee = exit.copy.prevEdge(0);
174 cananian 1.1 Quad.addEdge(ee.from(), ee.which_succ(), qP, 1);
175 cananian 1.1 // add to our successors list
176 cananian 1.1 result.addAll(qP.succC());
177 cananian 1.1 }
178 cananian 1.1 // done!
179 cananian 1.1 return result;
180 cananian 1.1 }
181 cananian 1.1 /** helper routine to add a quad on an edge. */
182 cananian 1.1 private Edge addAt(Edge e, Quad q) { return addAt(e, 0, q, 0); }
183 cananian 1.1 /** helper routine to add a quad on an edge. */
184 cananian 1.1 private Edge addAt(Edge e, int which_pred, Quad q, int which_succ) {
185 cananian 1.1 Quad frm = e.from(); int frm_succ = e.which_succ();
186 cananian 1.1 Quad to = e.to(); int to_pred = e.which_pred();
187 cananian 1.1 Quad.addEdge(frm, frm_succ, q, which_pred);
188 cananian 1.1 Quad.addEdge(q, which_succ, to, to_pred);
189 cananian 1.1 return to.prevEdge(to_pred);
190 cananian 1.1 }
191 cananian 1.1 }
192 cananian 1.1 private static class CopyPair<T> {
193 cananian 1.1 public final T orig, copy;
194 cananian 1.1 CopyPair(T orig, T copy) { this.orig = orig; this.copy = copy; }
195 cananian 1.1 }
196 cananian 1.1 private static class CopyInfo {
197 cananian 1.1 // left of pair is orig; right of pair is copy
198 cananian 1.1 final CopyPair<MONITORENTER> start;
199 cananian 1.1 final List<CopyPair<MONITOREXIT>> endList =
200 cananian 1.1 new ArrayList<CopyPair<MONITOREXIT>>();
201 cananian 1.1 CopyInfo(MONITORENTER origStart, MONITORENTER copyStart) {
202 cananian 1.1 this.start = new CopyPair<MONITORENTER>(origStart, copyStart);
203 cananian 1.1 }
204 cananian 1.1 }
205 cananian 1.4 private static CopyInfo copyGraph(MONITORENTER start,
206 cananian 1.4 AllocationInformationMap aim) {
207 cananian 1.1 WorkSet<Quad> frontier = new WorkSet<Quad>();
208 cananian 1.1 List<Edge> toLink = new ArrayList<Edge>();
209 cananian 1.1 Map<Quad,Quad> copyMap = new LinkedHashMap<Quad,Quad>();
210 cananian 1.1
211 cananian 1.1 // initialize: deal with start node.
212 cananian 1.1 CopyInfo result = new CopyInfo
213 cananian 1.1 (start, (MONITORENTER)
214 cananian 1.1 start.rename(identityTempMap, identityTempMap));
215 cananian 1.1 copyMap.put(result.start.orig, result.start.copy);
216 cananian 1.1 frontier.addAll(Arrays.asList(result.start.orig.next()));
217 cananian 1.1 toLink.addAll(result.start.orig.succC());
218 cananian 1.1
219 cananian 1.1 while(!frontier.isEmpty()) {
220 cananian 1.1 Quad q = frontier.removeFirst();
221 cananian 1.1 if (copyMap.containsKey(q)) continue;
222 cananian 1.1 // handle subgraphs first.
223 cananian 1.1 if (q instanceof MONITORENTER) {
224 cananian 1.1 // this is a subgraph: recurse.
225 cananian 1.4 CopyInfo ci = copyGraph((MONITORENTER)q, aim);
226 cananian 1.1 // now merge the info, including the mapping for q
227 cananian 1.1 copyMap.put(ci.start.orig, ci.start.copy);
228 cananian 1.1 // continue from the subgraph's exit points.
229 cananian 1.6 for (CopyPair<MONITOREXIT> exit : ci.endList) {
230 cananian 1.1 frontier.addAll(Arrays.asList(exit.orig.next()));
231 cananian 1.1 toLink.addAll(exit.orig.succC());
232 cananian 1.1 copyMap.put(exit.orig, exit.copy);
233 cananian 1.1 }
234 cananian 1.1 continue;
235 cananian 1.1 }
236 cananian 1.1 // otherwise, clone q:
237 cananian 1.1 Quad qq = q.rename(identityTempMap, identityTempMap);
238 cananian 1.1 // add to the mapping.
239 cananian 1.1 copyMap.put(q, qq);
240 cananian 1.4 // clone allocation properties
241 cananian 1.4 if (q instanceof ANEW || q instanceof NEW)
242 cananian 1.4 if (aim!=null) aim.transfer(qq, q, identityTempMap, aim);
243 cananian 1.1 // find connected quads.
244 cananian 1.1 if (q instanceof MONITOREXIT) {
245 cananian 1.1 // don't go past MONITOREXIT, but add it to the endList
246 cananian 1.1 result.endList.add(new CopyPair<MONITOREXIT>
247 cananian 1.1 ((MONITOREXIT)q, (MONITOREXIT)qq));
248 cananian 1.1 } else {
249 cananian 1.1 // okay, it's normal, keep going through.
250 cananian 1.1 frontier.addAll(Arrays.asList(q.next()));
251 cananian 1.1 // note that we need to link this up eventually
252 cananian 1.1 toLink.addAll(q.succC());
253 cananian 1.1 }
254 cananian 1.1 }
255 cananian 1.1 // now link all the outgoing edges.
256 cananian 1.6 for (Edge e : toLink) {
257 cananian 1.1 Quad.addEdge(copyMap.get(e.from()), e.which_succ(),
258 cananian 1.1 copyMap.get(e.to()), e.which_pred());
259 cananian 1.1 }
260 cananian 1.1 // done!
261 cananian 1.1 return result;
262 cananian 1.1 }
263 cananian 1.1 private static final TempMap identityTempMap = new TempMap() {
264 cananian 1.1 public Temp tempMap(Temp t) { return t; }
265 cananian 1.1 };
266 cananian 1.1 }