1 cananian 1.1.2.1 // MemHoisting.java, created Wed Jun 6 16:52:24 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.Tree;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.ClassFile.HClass;
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.2 import harpoon.ClassFile.HCodeElement;
10 cananian 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
11 cananian 1.1.2.1 import harpoon.ClassFile.HMethod;
12 cananian 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
13 cananian 1.1.2.1 import harpoon.IR.Tree.CanonicalTreeCode;
14 cananian 1.1.2.1 import harpoon.IR.Tree.Code;
15 cananian 1.1.2.1 import harpoon.IR.Tree.DerivationGenerator;
16 cananian 1.1.2.1 import harpoon.IR.Tree.ESEQ;
17 cananian 1.1.2.1 import harpoon.IR.Tree.Exp;
18 cananian 1.1.2.1 import harpoon.IR.Tree.MEM;
19 cananian 1.1.2.1 import harpoon.IR.Tree.MOVE;
20 cananian 1.1.2.1 import harpoon.IR.Tree.Stm;
21 cananian 1.1.2.1 import harpoon.IR.Tree.TEMP;
22 cananian 1.1.2.1 import harpoon.IR.Tree.Tree;
23 cananian 1.1.2.1 import harpoon.IR.Tree.TreeFactory;
24 cananian 1.1.2.1 import harpoon.IR.Tree.TreeKind;
25 cananian 1.1.2.1 import harpoon.Temp.Temp;
26 cananian 1.1.2.1 import harpoon.Util.Util;
27 cananian 1.1.2.1
28 cananian 1.1.2.1 import java.util.Arrays;
29 cananian 1.1.2.1 import java.util.HashMap;
30 cananian 1.1.2.2 import java.util.HashSet;
31 cananian 1.1.2.1 import java.util.Iterator;
32 cananian 1.1.2.1 import java.util.List;
33 cananian 1.1.2.1 import java.util.Map;
34 cananian 1.1.2.2 import java.util.Set;
35 cananian 1.1.2.1 /**
36 cananian 1.1.2.1 * <code>MemHoisting</code> ensures that the ordering of MEM operations
37 cananian 1.1.2.1 * is well-defined in the tree, by creating a temporary for and hoisting
38 cananian 1.1.2.1 * all but one MEM in any given subexpression. Canonicalization completes
39 cananian 1.1.2.1 * the transformation.
40 cananian 1.1.2.1 *
41 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
42 cananian 1.4 * @version $Id: MemHoisting.java,v 1.4 2002/04/10 03:02:06 cananian Exp $
43 cananian 1.1.2.1 */
44 cananian 1.1.2.1 public abstract class MemHoisting extends Simplification {
45 cananian 1.1.2.1 // hide constructor
46 cananian 1.3.2.2 private MemHoisting() { }
47 cananian 1.1.2.1 /** Code factory for applying MemHoisting to a
48 cananian 1.1.2.1 * canonical tree. Clones the tree before doing
49 cananian 1.1.2.1 * transformation in-place. */
50 cananian 1.1.2.1 public static HCodeFactory codeFactory(final HCodeFactory parent) {
51 cananian 1.3.2.1 assert parent.getCodeName().equals(CanonicalTreeCode.codename);
52 cananian 1.1.2.1 return Canonicalize.codeFactory(new HCodeFactory() {
53 cananian 1.1.2.1 public HCode convert(HMethod m) {
54 cananian 1.1.2.1 HCode hc = parent.convert(m);
55 cananian 1.1.2.1 if (hc!=null) {
56 cananian 1.1.2.1 harpoon.IR.Tree.Code code = (harpoon.IR.Tree.Code) hc;
57 cananian 1.1.2.1 // clone code...
58 cananian 1.1.2.1 code = (harpoon.IR.Tree.Code) code.clone(m).hcode();
59 cananian 1.1.2.1 DerivationGenerator dg = null;
60 cananian 1.1.2.1 try {
61 cananian 1.1.2.1 dg = (DerivationGenerator) code.getTreeDerivation();
62 cananian 1.1.2.1 } catch (ClassCastException ex) { /* i guess not */ }
63 cananian 1.1.2.1 // ...do analysis and modify cloned code in-place.
64 cananian 1.1.2.1 simplify((Stm)code.getRootElement(), dg, HCE_RULES(code));
65 cananian 1.1.2.1 hc = code;
66 cananian 1.1.2.1 }
67 cananian 1.1.2.1 return hc;
68 cananian 1.1.2.1 }
69 cananian 1.1.2.1 public String getCodeName() { return parent.getCodeName(); }
70 cananian 1.1.2.1 public void clear(HMethod m) { parent.clear(m); }
71 cananian 1.1.2.1 });
72 cananian 1.1.2.1 }
73 cananian 1.1.2.1
74 cananian 1.3.2.2 private static int count(Tree tr, Map<Tree,Integer> m, int memcnt) {
75 cananian 1.1.2.3 memcnt += (tr.kind()==TreeKind.MEM) ? 1 : 0;
76 cananian 1.1.2.1 m.put(tr, new Integer(memcnt));
77 cananian 1.1.2.3 for (Tree tp=tr.getFirstChild(); tp!=null; tp=tp.getSibling())
78 cananian 1.1.2.3 memcnt=count(tp, m, memcnt);
79 cananian 1.1.2.1 return memcnt;
80 cananian 1.1.2.1 }
81 cananian 1.3.2.2 private static void recurse(Stm stm, CFGrapher<Tree> cfgr,
82 cananian 1.3.2.2 Set<Stm> done, Map<Tree,Integer> m) {
83 cananian 1.1.2.2 // do this one.
84 cananian 1.1.2.2 done.add(stm);
85 cananian 1.1.2.3 count(stm, m, 0);
86 cananian 1.1.2.2 // do successors.
87 cananian 1.3.2.2 for (Iterator<Tree> it=cfgr.succElemC(stm).iterator(); it.hasNext();) {
88 cananian 1.1.2.2 Stm next = (Stm) it.next();
89 cananian 1.1.2.2 if (!done.contains(next))
90 cananian 1.1.2.2 recurse(next, cfgr, done, m);
91 cananian 1.1.2.2 }
92 cananian 1.1.2.2 }
93 cananian 1.1.2.1
94 cananian 1.3.2.2 public static List<Rule> HCE_RULES(final harpoon.IR.Tree.Code code) {
95 cananian 1.3.2.2 final CFGrapher<Tree> cfgr = code.getGrapher();
96 cananian 1.1.2.1 // collect the number of MEMs in every subtree.
97 cananian 1.3.2.2 final Map<Tree,Integer> memmap = new HashMap<Tree,Integer>();
98 cananian 1.1.2.2
99 cananian 1.3.2.2 Set<Stm> done = new HashSet();
100 cananian 1.3.2.2 Tree[] roots = cfgr.getFirstElements(code);
101 cananian 1.1.2.2 for (int i=0; i<roots.length; i++)
102 cananian 1.1.2.2 recurse((Stm)roots[i], cfgr, done, memmap);
103 cananian 1.1.2.2 roots=null; done=null; // free memory.
104 cananian 1.1.2.1
105 cananian 1.1.2.1 // now make rules.
106 cananian 1.1.2.1 return Arrays.asList(new Rule[] {
107 cananian 1.1.2.1 // MEM(x) -> ESEQ(MOVE(t, MEM(x)), t)
108 cananian 1.1.2.1 new Rule("hoistMem") {
109 cananian 1.1.2.1 public boolean match(Exp e) {
110 cananian 1.1.2.1 if (e.kind() != TreeKind.MEM) return false;
111 cananian 1.1.2.4 // leave the first mem in a stm alone.
112 cananian 1.3.2.2 if (memmap.get(e).intValue() < 2) return false;
113 cananian 1.1.2.4 // assert that we're not messing with MOVE(t, MEM(x))
114 cananian 1.1.2.6 // or MOVE(MEM(x), ...) trees [but MOVE(MEM(x), MEM(y))
115 cananian 1.1.2.6 // is okay to touch, if we're hoisting the MEM(y) ]
116 cananian 1.1.2.5 if (e.getParent()!=null &&
117 cananian 1.1.2.6 e.getParent().kind() == TreeKind.MOVE) {
118 cananian 1.1.2.5 MOVE m = (MOVE) e.getParent();
119 cananian 1.3.2.1 assert m.getSrc().kind()==TreeKind.MEM &&
120 cananian 1.1.2.7 m.getDst().kind()==TreeKind.MEM &&
121 cananian 1.3.2.1 e == m.getSrc();
122 cananian 1.1.2.5 }
123 cananian 1.1.2.1 return true;
124 cananian 1.1.2.1 }
125 cananian 1.1.2.1 public Exp apply(TreeFactory tf,Exp e,DerivationGenerator dg) {
126 cananian 1.1.2.1 MEM mem = (MEM) e;
127 cananian 1.1.2.1 Temp t = new Temp(tf.tempFactory(), "memhoist");
128 cananian 1.1.2.1 TEMP T1 = new TEMP(tf, e, mem.type(), t);
129 cananian 1.1.2.1 TEMP T2 = new TEMP(tf, e, mem.type(), t);
130 cananian 1.1.2.2 MEM nmem = (MEM) mem.build(tf, mem.kids());
131 cananian 1.1.2.1 if (dg!=null) { // make types for the new TEMPs/Temp
132 cananian 1.1.2.1 HClass hc = dg.typeMap(mem);
133 cananian 1.1.2.1 if (hc!=null) {
134 cananian 1.1.2.1 dg.putTypeAndTemp(T1, hc, t);
135 cananian 1.1.2.1 dg.putTypeAndTemp(T2, hc, t);
136 cananian 1.1.2.2 dg.putType(nmem, hc);
137 cananian 1.1.2.1 } else {
138 cananian 1.1.2.1 dg.putDerivation(T1, dg.derivation(mem));
139 cananian 1.1.2.1 dg.putDerivation(T2, dg.derivation(mem));
140 cananian 1.1.2.2 dg.putDerivation(nmem, dg.derivation(mem));
141 cananian 1.1.2.1 }
142 cananian 1.1.2.2 dg.remove(mem);
143 cananian 1.1.2.1 }
144 cananian 1.1.2.7 memmap.put(nmem, new Integer(1)); memmap.remove(mem);
145 cananian 1.1.2.1 return new ESEQ(tf, e,
146 cananian 1.1.2.2 new MOVE(tf, e, T1, nmem),
147 cananian 1.1.2.1 T2);
148 cananian 1.1.2.1 }
149 cananian 1.1.2.1 },
150 cananian 1.1.2.1 });
151 cananian 1.1.2.1 }
152 cananian 1.2 }