1 cananian 1.1.2.5 // TreeFolding.java, created Mon Apr 5 17:52:42 1999 by duncan
2 cananian 1.1.2.4 // Copyright (C) 1998 Duncan Bryce <duncan@lcs.mit.edu>
3 cananian 1.1.2.4 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 duncan 1.1.2.1 package harpoon.Analysis.Tree;
5 duncan 1.1.2.1
6 duncan 1.1.2.3 import harpoon.Analysis.DataFlow.TreeSolver;
7 pnkfelix 1.1.2.8 import harpoon.Analysis.BasicBlock;
8 salcianu 1.4 import harpoon.Analysis.BasicBlockInterf;
9 duncan 1.1.2.3 import harpoon.Analysis.DataFlow.ForwardDataFlowBasicBlockVisitor;
10 duncan 1.1.2.3 import harpoon.Analysis.DataFlow.ReversePostOrderIterator;
11 duncan 1.1.2.3 import harpoon.Analysis.EdgesIterator;
12 duncan 1.1.2.3 import harpoon.ClassFile.HCodeElement;
13 cananian 1.1.2.11 import harpoon.IR.Properties.CFGrapher;
14 cananian 1.1.2.18 import harpoon.IR.Properties.UseDefer;
15 duncan 1.1.2.3 import harpoon.IR.Tree.CanonicalTreeCode;
16 duncan 1.1.2.3 import harpoon.IR.Tree.Code;
17 duncan 1.1.2.1 import harpoon.IR.Tree.Exp;
18 duncan 1.1.2.1 import harpoon.IR.Tree.ExpList;
19 duncan 1.1.2.1 import harpoon.IR.Tree.MEM;
20 duncan 1.1.2.1 import harpoon.IR.Tree.MOVE;
21 duncan 1.1.2.1 import harpoon.IR.Tree.SEQ;
22 duncan 1.1.2.1 import harpoon.IR.Tree.Stm;
23 duncan 1.1.2.1 import harpoon.IR.Tree.TEMP;
24 duncan 1.1.2.1 import harpoon.IR.Tree.Tree;
25 duncan 1.1.2.3 import harpoon.IR.Tree.TreeKind;
26 duncan 1.1.2.1 import harpoon.Temp.Temp;
27 cananian 1.6 import net.cscott.jutil.BitString;
28 duncan 1.1.2.1 import harpoon.Util.Tuple;
29 duncan 1.1.2.1 import harpoon.Util.Util;
30 duncan 1.1.2.1
31 duncan 1.1.2.3 import java.util.HashMap;
32 duncan 1.1.2.3 import java.util.HashSet;
33 duncan 1.1.2.3 import java.util.Iterator;
34 duncan 1.1.2.3 import java.util.Map;
35 duncan 1.1.2.3 import java.util.Set;
36 duncan 1.1.2.3
37 duncan 1.1.2.3 /**
38 duncan 1.1.2.3 * The <code>TreeFolding</code> class performs tree folding on a
39 duncan 1.1.2.3 * tree code in canonical form. Tree folding is used to remove
40 duncan 1.1.2.3 * superfluous temp definitions in the tree form. For example,
41 duncan 1.1.2.3 * in the tree expression:
42 duncan 1.1.2.3 *
43 duncan 1.1.2.3 * <PRE>
44 duncan 1.1.2.3 * SEQ(
45 duncan 1.1.2.3 * MOVE(t1, 5)
46 duncan 1.1.2.3 * CJUMP(t1, L-true, L-false)
47 duncan 1.1.2.3 * )
48 duncan 1.1.2.3 * </PRE>
49 duncan 1.1.2.3 *
50 duncan 1.1.2.3 * the superfluous temp t1 would be removed, and its use would be replaced
51 duncan 1.1.2.3 * with the expression to which t1 was assigned:
52 duncan 1.1.2.3 *
53 duncan 1.1.2.3 * <PRE>
54 duncan 1.1.2.3 * CJUMP(5, L-true, L-false)
55 duncan 1.1.2.3 * </PRE>
56 duncan 1.1.2.3 *
57 duncan 1.1.2.3 *
58 duncan 1.1.2.3 * The algorithm for tree folding is as follows:
59 duncan 1.1.2.3 *
60 duncan 1.1.2.3 * <PRE>
61 duncan 1.1.2.3 * foreach TEMP t do
62 duncan 1.1.2.3 * if ((t has one DEF) AND
63 duncan 1.1.2.3 * (DEF(t) has one USE) AND
64 duncan 1.1.2.3 * (RHS(DEF(t)) is available))
65 duncan 1.1.2.3 * remove DEF(t)
66 duncan 1.1.2.3 * replace t with RHS(DEF(t))
67 duncan 1.1.2.3 * </PRE>
68 duncan 1.1.2.3 *
69 duncan 1.1.2.3 * <b>Issues:</b><p>
70 duncan 1.1.2.3 *
71 duncan 1.1.2.3 * At this time, memory writes kill all expressions. However, this is not
72 duncan 1.1.2.3 * really necessary. Furthermore, the algorithm is not especially efficient
73 duncan 1.1.2.3 * either in time or in space.
74 duncan 1.1.2.3 *
75 duncan 1.1.2.3 * @author Duncan Bryce <duncan@lcs.mit.edu>
76 cananian 1.7 * @version $Id: TreeFolding.java,v 1.7 2004/02/08 03:20:35 cananian Exp $
77 duncan 1.1.2.3 *
78 duncan 1.1.2.3 */
79 duncan 1.1.2.3 public class TreeFolding extends ForwardDataFlowBasicBlockVisitor {
80 duncan 1.1.2.3 private boolean initialized = false;
81 duncan 1.1.2.3
82 cananian 1.3.2.2 private final int maxTreeID;
83 cananian 1.3.2.2 private final Code code;
84 cananian 1.3.2.2 private final Map bb2tfi;
85 cananian 1.3.2.2 private final Map DUChains, UDChains;
86 cananian 1.3.2.2 private final Map tempsToPrsvs;
87 cananian 1.3.2.2 private final Stm root;
88 cananian 1.3.2.2 private final BasicBlock.Factory bbfactory;
89 duncan 1.1.2.3
90 cananian 1.1.2.11 private CFGrapher grapher;
91 cananian 1.1.2.18 private UseDefer usedefer;
92 cananian 1.1.2.11
93 duncan 1.1.2.3 /** Constructs a new <code>TreeFolding</code> object for the
94 duncan 1.1.2.3 * <code>code</code>.
95 duncan 1.1.2.3 *
96 duncan 1.1.2.3 * <BR> <B>requires:</B> <OL>
97 duncan 1.1.2.3 * <LI> <code>code</code> is a tree codeview in canonical form
98 duncan 1.1.2.3 * (<code>code.isCanonical()</code> should return
99 duncan 1.1.2.3 * <code>true</code>).
100 duncan 1.1.2.3 * <BR> <B>modifies:</B> nothing.
101 duncan 1.1.2.3 * <BR> <B>effects:</B> constructs a new
102 duncan 1.1.2.3 * <code>BasicBlockVisitor</code> and initializes its
103 duncan 1.1.2.3 * internal datasets for analysis of the
104 duncan 1.1.2.3 * <code>BasicBlock</code>s in <code>code</code>.
105 duncan 1.1.2.3 * However, the <code>visit()</code> and <code>merge()</code>
106 duncan 1.1.2.3 * methods should not be called directly. Rather, the folded
107 duncan 1.1.2.3 * tree code should be extracted by calling the calling the
108 duncan 1.1.2.3 * <code>fold()</code> method.
109 duncan 1.1.2.3 */
110 duncan 1.1.2.3 public TreeFolding(harpoon.IR.Tree.Code code) {
111 duncan 1.1.2.3 Map tempsToDefs = new HashMap();
112 duncan 1.1.2.3
113 cananian 1.3.2.1 assert code.isCanonical();
114 duncan 1.1.2.3
115 duncan 1.1.2.3 this.code = code;
116 duncan 1.1.2.3 this.root = (Stm)this.code.getRootElement();
117 cananian 1.1.2.11 this.grapher = code.getGrapher();
118 cananian 1.1.2.18 this.usedefer = code.getUseDefer();
119 duncan 1.1.2.3 this.maxTreeID = TreeSolver.getMaxID(RS(this.root));
120 duncan 1.1.2.3 this.bb2tfi = new HashMap();
121 duncan 1.1.2.3 this.DUChains = new HashMap();
122 duncan 1.1.2.3 this.UDChains = new HashMap();
123 duncan 1.1.2.3 this.tempsToPrsvs = new HashMap();
124 cananian 1.1.2.19 this.bbfactory = new BasicBlock.Factory(code, grapher);
125 cananian 1.1.2.16 BasicBlock rootbb = bbfactory.getRoot();
126 duncan 1.1.2.1
127 duncan 1.1.2.3 initTempsToPrsvs(tempsToPrsvs);
128 duncan 1.1.2.3 initTempsToDefs (tempsToDefs);
129 duncan 1.1.2.3
130 duncan 1.1.2.3 for (Iterator i = new ReversePostOrderIterator(rootbb);i.hasNext();) {
131 duncan 1.1.2.3 BasicBlock bb = (BasicBlock)i.next();
132 duncan 1.1.2.3 bb2tfi.put(bb, new TreeFoldingInfo(bb));
133 duncan 1.1.2.1 }
134 duncan 1.1.2.1
135 duncan 1.1.2.3 TreeSolver.forward_rpo_solver(rootbb, this);
136 cananian 1.1.2.16 computeUseDef(bbfactory, tempsToDefs);
137 duncan 1.1.2.1
138 duncan 1.1.2.3 initialized = true;
139 duncan 1.1.2.3 }
140 duncan 1.1.2.1
141 duncan 1.1.2.3 /**
142 duncan 1.1.2.3 * Performs the tree-folding optimization on this class's tree code.
143 duncan 1.1.2.3 *
144 duncan 1.1.2.3 * <BR> <B>Requires:</B>
145 duncan 1.1.2.3 * <BR> <B>Modifies:</B> this class's tree code
146 duncan 1.1.2.3 * <BR> <B>Effects:</B> Performs the tree-folding optimization on
147 duncan 1.1.2.3 * this class's tree code, and returns the resulting
148 cananian 1.1.2.9 * tree code. Preserves the <code>CFGraphable</code>
149 duncan 1.1.2.3 * interface correctly by calling the code's
150 duncan 1.1.2.3 * <code>recomputeEdges()</code> method.
151 duncan 1.1.2.3 */
152 duncan 1.1.2.3 public harpoon.IR.Tree.Code fold() {
153 duncan 1.1.2.3 Map IDsToTrees;
154 duncan 1.1.2.3 initIDsToTrees(IDsToTrees = new HashMap());
155 cananian 1.1.2.16 fold(bbfactory.getRoot(), IDsToTrees, this.DUChains, this.UDChains);
156 duncan 1.1.2.3 return this.code;
157 duncan 1.1.2.1 }
158 duncan 1.1.2.1
159 duncan 1.1.2.1
160 duncan 1.1.2.3 /** Visit (Transfer) function.
161 duncan 1.1.2.3 * <pre> OUT(bb) = GEN(bb) union (IN(bb) intersect PRSV(bb)) </pre>
162 duncan 1.1.2.3 * <pre> OUT_mem(bb) = IN_mem(bb) union KILL_mem(bb) </pre>.
163 duncan 1.1.2.3 *
164 duncan 1.1.2.3 * <B>Note:</B> this method should never be called directly, and will
165 duncan 1.1.2.3 * cause an assertion failure if it is called from outside of the
166 duncan 1.1.2.3 * <code>TreeFolding</code> class.
167 duncan 1.1.2.3 */
168 duncan 1.1.2.3 public void visit(BasicBlock bb) {
169 cananian 1.3.2.1 assert bb!=null;
170 cananian 1.3.2.1 assert !initialized;
171 duncan 1.1.2.3
172 duncan 1.1.2.3 //if (DEBUG) db("Visiting: " + bb);
173 duncan 1.1.2.3 TreeFoldingInfo info = (TreeFoldingInfo)bb2tfi.get(bb);
174 duncan 1.1.2.3
175 cananian 1.3.2.1 assert info!=null;
176 duncan 1.1.2.3 info.outSet[0].clearUpTo(maxTreeID);
177 duncan 1.1.2.3 info.outSet[0].or (info.prsvSet[0]);
178 duncan 1.1.2.3 info.outSet[0].and(info.inSet[0]);
179 duncan 1.1.2.3 info.outSet[0].or (info.genSet[0]);
180 duncan 1.1.2.3 info.outSet[1].clearUpTo(maxTreeID);
181 duncan 1.1.2.3 info.outSet[1].or(info.prsvSet[1]);
182 duncan 1.1.2.3 info.outSet[1].or(info.inSet[1]);
183 duncan 1.1.2.3 info.outSet[1].and(info.genSet[1]);
184 duncan 1.1.2.3 }
185 duncan 1.1.2.3
186 duncan 1.1.2.3 /**
187 duncan 1.1.2.3 * Merges operation on the from and to basic block. Returns true if
188 duncan 1.1.2.3 * the to basic block changes.
189 duncan 1.1.2.3 *
190 duncan 1.1.2.3 * <BR> <B>NOTE:</B> "changes" above refers to our knowledge about
191 duncan 1.1.2.3 * the basic block changing, not the contents of the basic block
192 duncan 1.1.2.3 * itself, which shouldn't be modified during Analysis. Thus, an
193 duncan 1.1.2.3 * appropriate "change" would be a variable being added to the
194 duncan 1.1.2.3 * IN-set of 'to' during Forward Dataflow Analysis
195 duncan 1.1.2.3 */
196 salcianu 1.4 public boolean merge(BasicBlockInterf from, BasicBlockInterf to) {
197 duncan 1.1.2.3 BitString fOUT, fOUT_mem, tIN, tIN_mem;
198 duncan 1.1.2.3 TreeFoldingInfo fInfo, tInfo;
199 duncan 1.1.2.3 boolean result;
200 duncan 1.1.2.1
201 cananian 1.3.2.1 assert !initialized;
202 duncan 1.1.2.1
203 duncan 1.1.2.3 //if (DEBUG) db("Merging: " + from + ", " + to);
204 duncan 1.1.2.1
205 duncan 1.1.2.3 fInfo = (TreeFoldingInfo)bb2tfi.get(from);
206 duncan 1.1.2.3 tInfo = (TreeFoldingInfo)bb2tfi.get(to);
207 duncan 1.1.2.3
208 duncan 1.1.2.3 fOUT = fInfo.outSet[0];
209 duncan 1.1.2.3 tIN = tInfo.inSet[0];
210 duncan 1.1.2.3 result = tIN.or_upTo(fOUT, maxTreeID);
211 duncan 1.1.2.3
212 duncan 1.1.2.3 fOUT_mem = fInfo.outSet[1];
213 duncan 1.1.2.3 tIN_mem = tInfo.inSet[1];
214 duncan 1.1.2.3 result = result || tIN_mem.or_upTo(fOUT_mem, maxTreeID);
215 duncan 1.1.2.1
216 duncan 1.1.2.3 return result;
217 duncan 1.1.2.3
218 duncan 1.1.2.3 }
219 duncan 1.1.2.3
220 duncan 1.1.2.3 /*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*
221 duncan 1.1.2.3 * *
222 duncan 1.1.2.3 * Initialization routines *
223 duncan 1.1.2.3 * *
224 duncan 1.1.2.3 *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
225 duncan 1.1.2.3
226 duncan 1.1.2.3 // Maps tree IDs to Tree objects
227 duncan 1.1.2.3 private void initIDsToTrees(Map IDsToTrees) {
228 cananian 1.1.2.11 for (Iterator i = new EdgesIterator(RS(root),grapher); i.hasNext();) {
229 duncan 1.1.2.3 Stm stm = (Stm)i.next();
230 duncan 1.1.2.3 int ID = stm.getID();
231 duncan 1.1.2.3 IDsToTrees.put(new Integer(ID), stm);
232 duncan 1.1.2.1 }
233 duncan 1.1.2.3 }
234 duncan 1.1.2.1
235 duncan 1.1.2.3 // Maps Temps to BitStrings representing the Tree IDs of the Trees
236 duncan 1.1.2.3 // they preserve
237 duncan 1.1.2.3 private void initTempsToPrsvs(Map tempsToPrsvs) {
238 cananian 1.1.2.7 for (Iterator i = ((Code.TreeFactory)root.getFactory()).getParent().getElementsI();
239 duncan 1.1.2.3 i.hasNext();) {
240 cananian 1.1.2.18 Tree u = (Tree)i.next();
241 cananian 1.1.2.18 Temp[] tmps = (u instanceof Stm)?usedefer.def(u):usedefer.use(u);
242 duncan 1.1.2.3 for (int n=0; n<tmps.length; n++) {
243 duncan 1.1.2.3 BitString bs = (BitString)tempsToPrsvs.get(tmps[n]);
244 duncan 1.1.2.3 if (bs==null) {
245 duncan 1.1.2.3 tempsToPrsvs.put(tmps[n], bs=new BitString(maxTreeID+1));
246 duncan 1.1.2.3 bs.setAll();
247 duncan 1.1.2.1 }
248 cananian 1.1.2.18 bs.clear(u.getID());
249 duncan 1.1.2.3 }
250 duncan 1.1.2.3 }
251 duncan 1.1.2.3 }
252 duncan 1.1.2.3
253 duncan 1.1.2.3 // Maps Temps to the Tree IDs of the statements where they are defined
254 duncan 1.1.2.3 private void initTempsToDefs(Map tempsToDefs) {
255 cananian 1.1.2.11 for (Iterator i = new EdgesIterator(RS(root),grapher); i.hasNext();) {
256 duncan 1.1.2.3 Stm stm = (Stm)i.next();
257 duncan 1.1.2.3 if (!((stm.kind()==TreeKind.CALL) ||
258 duncan 1.1.2.3 (stm.kind()==TreeKind.NATIVECALL))) {
259 cananian 1.3.2.1 Temp[] defs = usedefer.def(stm); assert defs.length<=1;
260 duncan 1.1.2.3 if (defs.length==1) {
261 duncan 1.1.2.3 MAP_TO_SET(defs[0], new Integer(stm.getID()), tempsToDefs);
262 duncan 1.1.2.1 }
263 duncan 1.1.2.1 }
264 duncan 1.1.2.1 }
265 duncan 1.1.2.3 }
266 duncan 1.1.2.1
267 duncan 1.1.2.3 // Computes UD and DU chains based on the computed IN and OUT sets
268 duncan 1.1.2.3 // FIX: this method could probably be cleaned up substantially
269 duncan 1.1.2.3 //
270 cananian 1.1.2.16 private void computeUseDef(BasicBlock.Factory bbf, Map tempsToDefs) {
271 cananian 1.1.2.16 for (Iterator i = bbf.blocksIterator(); i.hasNext();) {
272 duncan 1.1.2.3 BasicBlock bb = (BasicBlock)i.next();
273 duncan 1.1.2.3 TreeFoldingInfo bbInfo = (TreeFoldingInfo)bb2tfi.get(bb);
274 duncan 1.1.2.3 BitString bbIn = (BitString)((bbInfo.inSet[0]).clone());
275 pnkfelix 1.1.2.13 for (Iterator j = bb.statements().listIterator(); j.hasNext();) {
276 duncan 1.1.2.3 Stm stm = (Stm)j.next();
277 duncan 1.1.2.3 Integer useID = new Integer(stm.getID());
278 cananian 1.1.2.18 Temp[] uses = usedefer.use(stm);
279 duncan 1.1.2.3 for (int n=0; n<uses.length; n++) {
280 duncan 1.1.2.3 Temp use = uses[n];
281 duncan 1.1.2.3 Set defIDs = (Set)tempsToDefs.get(use);
282 cananian 1.3.2.1 //assert tempsToDefs.containsKey(use);
283 duncan 1.1.2.3 if (tempsToDefs.containsKey(use)) {
284 cananian 1.7 for (Object defIDO : defIDs) {
285 cananian 1.7 Integer defID = (Integer) defIDO;
286 duncan 1.1.2.3 if (bbIn.get(defID.intValue())) {
287 duncan 1.1.2.3 Tuple defT=new Tuple(new Object[]{defID,use});
288 duncan 1.1.2.3 Tuple useT=new Tuple(new Object[]{useID,use});
289 duncan 1.1.2.3 MAP_TO_SET(useT, defT, UDChains);
290 duncan 1.1.2.3 MAP_TO_SET(defT, useT, DUChains);
291 duncan 1.1.2.1 }
292 duncan 1.1.2.3 }
293 duncan 1.1.2.1 }
294 duncan 1.1.2.3 }
295 duncan 1.1.2.3 // Update IN set
296 cananian 1.1.2.18 Temp[] defs = usedefer.def(stm);
297 cananian 1.3.2.1 assert defs.length<=1 ||
298 duncan 1.1.2.3 stm.kind()==TreeKind.CALL ||
299 cananian 1.3.2.1 stm.kind()==TreeKind.NATIVECALL;
300 duncan 1.1.2.3 if (defs.length==1) {
301 duncan 1.1.2.3 bbIn.and((BitString)tempsToPrsvs.get(defs[0]));
302 duncan 1.1.2.3 bbIn.set(stm.getID());
303 duncan 1.1.2.1 }
304 duncan 1.1.2.1 }
305 duncan 1.1.2.1 }
306 duncan 1.1.2.3 }
307 duncan 1.1.2.3
308 duncan 1.1.2.3 // Performs the folding operation, using the suppiled DU and UD chains.
309 duncan 1.1.2.3 // FIX: this method could probably be cleaned up substantially
310 duncan 1.1.2.3 private void fold(BasicBlock root, Map IDsToTrees,
311 duncan 1.1.2.3 Map DUChains, Map UDChains) {
312 duncan 1.1.2.3 Map tm = new HashMap();
313 duncan 1.1.2.3 BasicBlock bb;
314 duncan 1.1.2.3 TreeFoldingInfo tfi;
315 duncan 1.1.2.3 BitString dataIn, memIn;
316 duncan 1.1.2.3 for (Iterator i = new ReversePostOrderIterator(root); i.hasNext();) {
317 duncan 1.1.2.3 bb = (BasicBlock)i.next();
318 duncan 1.1.2.3 tfi = (TreeFoldingInfo)bb2tfi.get(bb);
319 duncan 1.1.2.3 dataIn = (BitString)tfi.inSet[0].clone();
320 duncan 1.1.2.3 memIn = (BitString)tfi.inSet[1].clone();
321 duncan 1.1.2.1
322 pnkfelix 1.1.2.13 for (Iterator bbi = bb.statements().listIterator(); bbi.hasNext();) {
323 duncan 1.1.2.3 Stm stm = (Stm)bbi.next();
324 cananian 1.1.2.18 Temp[] uses = usedefer.use(stm);
325 duncan 1.1.2.3 for (int j=0; j<uses.length; j++) {
326 duncan 1.1.2.3 Tuple useT =
327 duncan 1.1.2.3 new Tuple(new Object[]
328 duncan 1.1.2.3 { new Integer(stm.getID()), uses[j] });
329 duncan 1.1.2.3 Set D = (Set)UDChains.get(useT);
330 duncan 1.1.2.3 // Is there only one DEF for this USE?
331 duncan 1.1.2.3 if (D!=null && D.size()==1) {
332 duncan 1.1.2.3 Tuple defT = (Tuple)(D.iterator().next());
333 duncan 1.1.2.3 Set U = (Set)DUChains.get(defT);
334 duncan 1.1.2.3 // is there only one USE for this DEF?
335 duncan 1.1.2.3 if (U.size()==1) {
336 cananian 1.3.2.1 //assert U contains use;
337 cananian 1.3.2.1 assert IDsToTrees.containsKey(defT.proj(0));
338 duncan 1.1.2.3
339 duncan 1.1.2.3 // Is memory valid here?
340 duncan 1.1.2.3 if (!memIn.get
341 duncan 1.1.2.3 (((Integer)defT.proj(0)).intValue())) {
342 duncan 1.1.2.3 // Is the expression we want available?
343 duncan 1.1.2.3 if (dataIn.get
344 duncan 1.1.2.3 (((Integer)defT.proj(0)).intValue())) {
345 duncan 1.1.2.3 Stm DStm =
346 duncan 1.1.2.3 (Stm)(IDsToTrees.get(defT.proj(0)));
347 duncan 1.1.2.3 DStm = (Stm)GET_TREE(tm, DStm);
348 duncan 1.1.2.12 code.remove(DStm);
349 duncan 1.1.2.3 Stm foldedStm =
350 duncan 1.1.2.3 stm.build
351 cananian 1.1.2.11 (replace(((MOVE)DStm).getSrc(),
352 duncan 1.1.2.3 GET_TREE(tm, stm).kids(),
353 duncan 1.1.2.3 uses[j]));
354 cananian 1.1.2.17 GET_TREE(tm, stm).replace(foldedStm);
355 duncan 1.1.2.3 MAP_TREE(tm, GET_TREE(tm, stm), foldedStm);
356 duncan 1.1.2.3 }
357 duncan 1.1.2.3 }
358 duncan 1.1.2.3 }
359 duncan 1.1.2.3 }
360 duncan 1.1.2.1 }
361 duncan 1.1.2.3 if (mayWriteMem(stm))
362 duncan 1.1.2.3 memIn.setAll();
363 duncan 1.1.2.3 else if (stm.kind()==TreeKind.MOVE) {
364 duncan 1.1.2.3 dataIn.and
365 cananian 1.1.2.18 ((BitString)tempsToPrsvs.get(usedefer.def(stm)[0]));
366 duncan 1.1.2.3 dataIn.set(stm.getID());
367 duncan 1.1.2.3 memIn.clear(stm.getID());
368 duncan 1.1.2.1 }
369 duncan 1.1.2.1 }
370 duncan 1.1.2.1 }
371 duncan 1.1.2.1 }
372 duncan 1.1.2.1
373 duncan 1.1.2.3 /*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*
374 duncan 1.1.2.3 * *
375 duncan 1.1.2.3 * Utility functions *
376 duncan 1.1.2.3 * *
377 duncan 1.1.2.3 *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
378 duncan 1.1.2.3
379 duncan 1.1.2.3 private void MAP_TREE(Map table, Tree key, Tree value) {
380 duncan 1.1.2.3 table.put(key, value);
381 duncan 1.1.2.3 }
382 duncan 1.1.2.3
383 duncan 1.1.2.3 private Tree GET_TREE(Map table, Tree key) {
384 duncan 1.1.2.3 while (table.containsKey(key)) key = (Tree)table.get(key);
385 duncan 1.1.2.3 return key;
386 duncan 1.1.2.3 }
387 duncan 1.1.2.1
388 duncan 1.1.2.3 private void MAP_TO_SET(Object key, Object value, Map map) {
389 duncan 1.1.2.3 Set set;
390 duncan 1.1.2.3 if (!map.containsKey(key)) {
391 duncan 1.1.2.3 set = new HashSet();
392 duncan 1.1.2.3 map.put(key, set);
393 duncan 1.1.2.1 }
394 duncan 1.1.2.3 else {
395 duncan 1.1.2.3 set = (Set)map.get(key);
396 duncan 1.1.2.1 }
397 duncan 1.1.2.3 set.add(value);
398 duncan 1.1.2.3 }
399 duncan 1.1.2.1
400 duncan 1.1.2.3
401 duncan 1.1.2.3 private Stm RS(Stm s) {
402 cananian 1.1.2.11 try { while (true) s = ((SEQ)s).getLeft(); }
403 duncan 1.1.2.3 catch (ClassCastException e) { return s; }
404 duncan 1.1.2.3 }
405 duncan 1.1.2.1
406 duncan 1.1.2.3 private ExpList replace(Exp src, ExpList use, Temp tUse) {
407 duncan 1.1.2.3 if (use==null||use.head==null) return null;
408 duncan 1.1.2.3 else {
409 duncan 1.1.2.3 if (use.head.kind()==TreeKind.TEMP) {
410 duncan 1.1.2.3 TEMP temp = (TEMP)use.head;
411 duncan 1.1.2.3 // Only replaces one instance of the temp
412 duncan 1.1.2.3 if (temp.temp==tUse) return new ExpList(src, use.tail);
413 duncan 1.1.2.3 else return new ExpList(temp, replace(src, use.tail, tUse));
414 duncan 1.1.2.3 }
415 duncan 1.1.2.3 else return new ExpList
416 duncan 1.1.2.3 (use.head.build(replace(src, use.head.kids(), tUse)),
417 duncan 1.1.2.3 replace(src, use.tail, tUse));
418 duncan 1.1.2.1 }
419 duncan 1.1.2.1 }
420 duncan 1.1.2.3
421 duncan 1.1.2.3 // TreeFoldingInfo is a record type grouping together four sets:
422 duncan 1.1.2.3 class TreeFoldingInfo {
423 duncan 1.1.2.3 final BitString[] genSet = new BitString[2];
424 duncan 1.1.2.3 final BitString[] prsvSet = new BitString[2];
425 duncan 1.1.2.3 final BitString[] inSet = new BitString[2];
426 duncan 1.1.2.3 final BitString[] outSet = new BitString[2];
427 duncan 1.1.2.1
428 duncan 1.1.2.3 TreeFoldingInfo(BasicBlock bb) {
429 duncan 1.1.2.3 this.genSet[0] = new BitString(maxTreeID+1);
430 duncan 1.1.2.3 this.genSet[1] = new BitString(maxTreeID+1);
431 duncan 1.1.2.3 this.inSet[0] = new BitString(maxTreeID+1);
432 duncan 1.1.2.3 this.inSet[1] = new BitString(maxTreeID+1);
433 duncan 1.1.2.3 this.outSet[0] = new BitString(maxTreeID+1);
434 duncan 1.1.2.3 this.outSet[1] = new BitString(maxTreeID+1);
435 duncan 1.1.2.3 this.prsvSet[0] = new BitString(maxTreeID+1);
436 duncan 1.1.2.3 this.prsvSet[1] = new BitString(maxTreeID+1);
437 duncan 1.1.2.3
438 duncan 1.1.2.3 computeGenPrsvSets(bb);
439 duncan 1.1.2.1 }
440 duncan 1.1.2.1
441 duncan 1.1.2.3 // Initializes the GEN and PRSV sets of this TreeFoldingInfo
442 duncan 1.1.2.3 // This method should be called just once after the object is
443 duncan 1.1.2.3 // created.
444 duncan 1.1.2.3 private void computeGenPrsvSets(BasicBlock bb) {
445 duncan 1.1.2.3 prsvSet[0].setAll();
446 duncan 1.1.2.3 prsvSet[1].setAll();
447 duncan 1.1.2.3 genSet[1].setAll();
448 pnkfelix 1.1.2.13 for (Iterator i = bb.statements().listIterator(); i.hasNext();) {
449 duncan 1.1.2.3 Stm stm = (Stm)i.next();
450 duncan 1.1.2.3 if (mayWriteMem(stm)) {
451 duncan 1.1.2.3 prsvSet[1].setAll();
452 duncan 1.1.2.1 }
453 duncan 1.1.2.3 else {
454 duncan 1.1.2.3 if (stm.kind()==TreeKind.MOVE) {
455 duncan 1.1.2.3 prsvSet[0].and
456 cananian 1.1.2.18 ((BitString)tempsToPrsvs.get(usedefer.def(stm)[0]));
457 duncan 1.1.2.3 genSet[0].set(stm.getID());
458 duncan 1.1.2.3 genSet[1].clear(stm.getID());
459 duncan 1.1.2.3 }
460 duncan 1.1.2.1 }
461 duncan 1.1.2.1 }
462 duncan 1.1.2.1 }
463 duncan 1.1.2.3
464 duncan 1.1.2.3 public String toString() {
465 duncan 1.1.2.3 StringBuffer s = new StringBuffer();
466 duncan 1.1.2.3 s.append( "tGen set: "+genSet[0].toString());
467 duncan 1.1.2.3 s.append("\n\tPrsv set: "+prsvSet[0].toString());
468 duncan 1.1.2.3 s.append("\n\tIn set: "+inSet[0].toString());
469 duncan 1.1.2.3 s.append("\n\tOut set: "+outSet[0].toString()+"\n");
470 duncan 1.1.2.3 return s.toString();
471 duncan 1.1.2.1 }
472 duncan 1.1.2.1 }
473 duncan 1.1.2.1
474 duncan 1.1.2.3
475 duncan 1.1.2.1
476 duncan 1.1.2.3 // Returns true if the parameter is a statement that might perform
477 duncan 1.1.2.3 // a memory write.
478 duncan 1.1.2.3 private static boolean mayWriteMem(Stm s) {
479 duncan 1.1.2.3 int s_kind = s.kind();
480 duncan 1.1.2.3 return
481 duncan 1.1.2.3 (s_kind==TreeKind.CALL) ||
482 duncan 1.1.2.3 (s_kind==TreeKind.NATIVECALL) ||
483 duncan 1.1.2.3 ((s_kind==TreeKind.MOVE) &&
484 cananian 1.1.2.11 ((((MOVE)s).getDst()).kind()==TreeKind.MEM));
485 duncan 1.1.2.1 }
486 duncan 1.1.2.1 }
487 duncan 1.1.2.1
488 duncan 1.1.2.3
489 cananian 1.2