1 cananian 1.1.2.1 // DerivationGenerator.java, created Tue Feb 1 01:31:34 2000 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.IR.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.Analysis.Maps.Derivation.DList;
8 cananian 1.1.2.1 import harpoon.Analysis.Maps.TypeMap.TypeNotKnownException;
9 cananian 1.1.2.1 import harpoon.Temp.Temp;
10 cananian 1.1.2.5 import harpoon.Temp.TempMap;
11 cananian 1.1.2.1 import harpoon.Util.Util;
12 cananian 1.1.2.1
13 cananian 1.1.2.1 import java.util.HashMap;
14 cananian 1.1.2.1 import java.util.Iterator;
15 cananian 1.1.2.1 import java.util.Map;
16 cananian 1.1.2.1 /**
17 cananian 1.1.2.1 * <code>DerivationGenerator</code> takes a partial map of
18 cananian 1.1.2.1 * <code>Tree.Exp</code>s-to-type/derivations and answers
19 cananian 1.1.2.1 * type/derivation queries as if the complete map were
20 cananian 1.1.2.1 * present. In particular, only <code>Tree.TEMP</code>s
21 cananian 1.1.2.1 * and <code>Tree.MEM</code>s are typically explicitly
22 cananian 1.1.2.1 * typed in the map; types for the rest of the
23 cananian 1.1.2.1 * <code>Tree.Exp</code>s can be inferred from these.
24 cananian 1.1.2.1 *
25 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
26 cananian 1.4 * @version $Id: DerivationGenerator.java,v 1.4 2002/04/10 03:05:44 cananian Exp $
27 cananian 1.1.2.1 */
28 cananian 1.1.2.3 public class DerivationGenerator implements TreeDerivation {
29 cananian 1.1.2.1 /** private partial type map */
30 cananian 1.1.2.1 private Map dtM = new HashMap();
31 cananian 1.1.2.1
32 cananian 1.1.2.1 /** Creates a <code>DerivationGenerator</code>. */
33 cananian 1.1.2.3 public DerivationGenerator() { }
34 cananian 1.1.2.1
35 cananian 1.1.2.1 /** internal structure of type/derivation information */
36 cananian 1.1.2.1 private static class TypeAndDerivation {
37 cananian 1.1.2.1 /** non-null for base pointers */
38 cananian 1.1.2.1 public final HClass type;
39 cananian 1.1.2.1 /** non-null for derived pointers */
40 cananian 1.1.2.1 public final DList derivation;
41 cananian 1.1.2.1 /** for some base pointers, indicates the temp containing this type */
42 cananian 1.1.2.1 public final Temp temp;
43 cananian 1.1.2.1 // public constructors
44 cananian 1.1.2.1 TypeAndDerivation(HClass type) { this(type, null, null); }
45 cananian 1.1.2.1 TypeAndDerivation(DList deriv) { this(null, deriv, null); }
46 cananian 1.1.2.1 TypeAndDerivation(HClass type, Temp temp) { this(type, null, temp); }
47 cananian 1.1.2.1 /** private constructor */
48 cananian 1.1.2.1 private TypeAndDerivation(HClass type, DList derivation, Temp temp) {
49 cananian 1.3.2.1 assert type!=null ^ derivation!=null;
50 cananian 1.1.2.1 this.type = type;
51 cananian 1.1.2.1 this.derivation = derivation;
52 cananian 1.1.2.1 this.temp = temp;
53 cananian 1.1.2.1 }
54 cananian 1.1.2.5 TypeAndDerivation rename(TempMap tm) {
55 cananian 1.1.2.5 if (this.derivation!=null)
56 cananian 1.1.2.5 return new TypeAndDerivation(DList.rename(this.derivation,tm));
57 cananian 1.1.2.5 if (this.temp!=null && tm!=null)
58 cananian 1.1.2.5 return new TypeAndDerivation(this.type, tm.tempMap(this.temp));
59 cananian 1.1.2.5 // no need to create a new object, as tad's are immutable.
60 cananian 1.1.2.5 return this;
61 cananian 1.1.2.5 }
62 cananian 1.1.2.1 }
63 cananian 1.1.2.1
64 cananian 1.1.2.1 // public interface
65 cananian 1.1.2.1 public HClass typeMap(Exp exp) throws TypeNotKnownException {
66 cananian 1.1.2.1 TypeAndDerivation tad = getDT(exp);
67 cananian 1.1.2.1 if (tad==null) throw new TypeNotKnownException(exp, null);
68 cananian 1.1.2.1 if (!dtM.containsKey(exp)) dtM.put(exp, tad); // cache this result.
69 cananian 1.1.2.1 return tad.type;
70 cananian 1.1.2.1 }
71 cananian 1.1.2.1 public DList derivation(Exp exp) throws TypeNotKnownException {
72 cananian 1.1.2.1 TypeAndDerivation tad = getDT(exp);
73 cananian 1.1.2.1 if (tad==null) throw new TypeNotKnownException(exp, null);
74 cananian 1.1.2.1 if (!dtM.containsKey(exp)) dtM.put(exp, tad); // cache this result.
75 cananian 1.1.2.1 return tad.derivation;
76 cananian 1.1.2.1 }
77 cananian 1.1.2.1
78 cananian 1.1.2.1 // allow implementations to add explicit type/derivation information
79 cananian 1.1.2.3 /** Add a mapping from the given <code>Tree.Exp</code> <code>exp</code>
80 cananian 1.1.2.3 * to the given <code>HClass</code> <code>type</code> to this
81 cananian 1.1.2.3 * <code>DerivationGenerator</code>. */
82 cananian 1.1.2.3 public void putType(Exp exp, HClass type) {
83 cananian 1.3.2.1 assert exp!=null && type!=null;
84 cananian 1.3.2.1 assert !dtM.containsKey(exp);
85 cananian 1.1.2.1 dtM.put(exp, new TypeAndDerivation(type));
86 cananian 1.1.2.1 }
87 cananian 1.1.2.3 /** Add a mapping from the given <code>Tree.Exp</code> <code>exp</code>
88 cananian 1.1.2.3 * to the given <code>HClass</code> <code>type</code> to the
89 cananian 1.1.2.3 * <code>DerivationGenerator</code>, indicating that this value lives
90 cananian 1.1.2.3 * in <code>Temp</code> <code>temp</code>. */
91 cananian 1.1.2.3 public void putTypeAndTemp(Exp exp, HClass type, Temp temp) {
92 cananian 1.3.2.1 assert exp!=null && type!=null && temp!=null;
93 cananian 1.3.2.1 assert !dtM.containsKey(exp);
94 cananian 1.1.2.1 dtM.put(exp, new TypeAndDerivation(type, temp));
95 cananian 1.1.2.1 }
96 cananian 1.1.2.3 /** Add a mapping from the given <code>Tree.Exp</code> <code>exp</code>
97 cananian 1.1.2.3 * to the given <code>Derivation.DList</code> <code>derivation</code>.
98 cananian 1.1.2.3 */
99 cananian 1.1.2.3 public void putDerivation(Exp exp, DList derivation) {
100 cananian 1.3.2.1 assert exp!=null && derivation!=null;
101 cananian 1.3.2.1 assert !dtM.containsKey(exp);
102 cananian 1.1.2.1 dtM.put(exp, new TypeAndDerivation(derivation));
103 cananian 1.1.2.4 }
104 cananian 1.1.2.6 /** Transfer typing from one exp to another. */
105 cananian 1.1.2.6 public void update(Exp oldE, Exp newE) {
106 cananian 1.1.2.6 if (dtM.containsKey(oldE))
107 cananian 1.1.2.6 dtM.put(newE, dtM.remove(oldE));
108 cananian 1.1.2.6 }
109 cananian 1.1.2.4 // allow implementations to flush old data from the derivation generator
110 cananian 1.1.2.4 /** Remove all type and derivation mappings for the given
111 cananian 1.1.2.4 * <code>Tree.Exp</code>. Used for memory management purposes. */
112 cananian 1.1.2.4 public void remove(Exp exp) {
113 cananian 1.1.2.4 dtM.remove(exp);
114 cananian 1.1.2.5 }
115 cananian 1.1.2.5
116 cananian 1.1.2.5 // provide for cloning.
117 cananian 1.1.2.5 public Tree.CloneCallback cloneCallback(final TreeDerivation oldDeriv) {
118 cananian 1.1.2.5 if (oldDeriv instanceof DerivationGenerator)
119 cananian 1.1.2.5 return cloneCallback((DerivationGenerator)oldDeriv);
120 cananian 1.1.2.5 // okay, just brute-force add all MEM/NAME/TEMP types to map.
121 cananian 1.1.2.5 return new Tree.CloneCallback() {
122 cananian 1.1.2.5 public Tree callback(Tree oldTree, Tree newTree, TempMap tm) {
123 cananian 1.1.2.5 if (newTree instanceof MEM || newTree instanceof NAME ||
124 cananian 1.1.2.5 newTree instanceof TEMP) {
125 cananian 1.1.2.5 Exp oldExp = (Exp) oldTree, newExp = (Exp) newTree;
126 cananian 1.1.2.5 HClass hc = oldDeriv.typeMap(oldExp);
127 cananian 1.1.2.5 TypeAndDerivation tad = (hc == null)
128 cananian 1.1.2.5 ? new TypeAndDerivation(oldDeriv.derivation(oldExp))
129 cananian 1.1.2.5 : (newExp instanceof TEMP)
130 cananian 1.1.2.5 ? new TypeAndDerivation(hc, ((TEMP)newExp).temp)
131 cananian 1.1.2.5 : new TypeAndDerivation(hc);
132 cananian 1.1.2.5 DerivationGenerator.this.dtM.put(newExp, tad.rename(tm));
133 cananian 1.1.2.5 }
134 cananian 1.1.2.5 return newTree;
135 cananian 1.1.2.5 }
136 cananian 1.1.2.5 };
137 cananian 1.1.2.5 }
138 cananian 1.1.2.5 private Tree.CloneCallback cloneCallback(final
139 cananian 1.1.2.5 DerivationGenerator oldDeriv) {
140 cananian 1.1.2.5 return new Tree.CloneCallback() {
141 cananian 1.1.2.5 public Tree callback(Tree oldTree, Tree newTree, TempMap tm) {
142 cananian 1.1.2.5 if (oldDeriv.dtM.containsKey(oldTree)) {
143 cananian 1.1.2.5 TypeAndDerivation tad =
144 cananian 1.1.2.5 (TypeAndDerivation) oldDeriv.dtM.get(oldTree);
145 cananian 1.1.2.5 DerivationGenerator.this.dtM.put(newTree, tad.rename(tm));
146 cananian 1.1.2.5 }
147 cananian 1.1.2.5 return newTree;
148 cananian 1.1.2.5 }
149 cananian 1.1.2.5 };
150 cananian 1.1.2.1 }
151 cananian 1.1.2.1
152 cananian 1.1.2.1 // private interface
153 cananian 1.1.2.1 private TypeAndDerivation getDT(Exp exp) {
154 cananian 1.1.2.1 if (dtM.containsKey(exp)) return (TypeAndDerivation) dtM.get(exp);
155 cananian 1.1.2.1 return new DTVisitor(exp).tad;
156 cananian 1.1.2.1 }
157 cananian 1.1.2.1 private class DTVisitor extends TreeVisitor {
158 cananian 1.1.2.1 public TypeAndDerivation tad;
159 cananian 1.1.2.1 DTVisitor(Exp exp) { exp.accept(this); }
160 cananian 1.3.2.1 public void visit(Tree e) { assert false : ("Can't type: "+e); }
161 cananian 1.1.2.1 public void visit(CONST e) {
162 cananian 1.1.2.1 // e.type()==Type.POINTER means null constant.
163 cananian 1.1.2.1 this.tad = (e.type() != Type.POINTER) ? type2tad(e.type()) : Void;
164 cananian 1.1.2.1 }
165 cananian 1.1.2.1 public void visit(ESEQ e) {
166 cananian 1.1.2.1 this.tad = getDT(e.getExp());
167 cananian 1.1.2.1 }
168 cananian 1.1.2.1 public void visit(MEM e) {
169 cananian 1.3.2.1 assert e.type() != Type.POINTER : "Can't determine type for MEM.";
170 cananian 1.1.2.1 this.tad = type2tad(e.type());
171 cananian 1.1.2.1 }
172 cananian 1.1.2.1 public void visit(NAME e) {
173 cananian 1.1.2.1 // be careful with NAMEs of pre-constructed objects
174 cananian 1.1.2.1 this.tad = Void;
175 cananian 1.1.2.1 }
176 cananian 1.1.2.1 public void visit(BINOP e) {
177 cananian 1.1.2.1 TypeAndDerivation lefttad = getDT(e.getLeft());
178 cananian 1.1.2.1 TypeAndDerivation righttad = getDT(e.getRight());
179 cananian 1.1.2.1 if (e.type() != Type.POINTER)
180 cananian 1.1.2.1 this.tad = type2tad(e.type());
181 cananian 1.1.2.1 else switch (e.op) { // this is a pointer operation
182 cananian 1.1.2.1 case Bop.ADD:
183 cananian 1.1.2.8 case Bop.AND: // XXX: not quite right.
184 cananian 1.1.2.1 this.tad = TADadd(getDT(e.getLeft()), getDT(e.getRight()));
185 cananian 1.1.2.1 break;
186 cananian 1.1.2.1 default:
187 cananian 1.3.2.1 assert false : ("Illegal pointer operation: "+e);
188 cananian 1.1.2.1 }
189 cananian 1.1.2.1 }
190 cananian 1.1.2.1 public void visit(UNOP e) {
191 cananian 1.1.2.1 if (e.type() != Type.POINTER)
192 cananian 1.1.2.1 this.tad = type2tad(e.type());
193 cananian 1.1.2.1 else switch (e.op) { // this is a pointer operation
194 cananian 1.1.2.1 case Uop.NEG:
195 cananian 1.1.2.1 this.tad = TADnegate(getDT(e.getOperand()));
196 cananian 1.1.2.1 break;
197 cananian 1.1.2.1 default:
198 cananian 1.3.2.1 assert false : ("Illegal pointer operation: "+e);
199 cananian 1.1.2.1 }
200 cananian 1.1.2.1 }
201 cananian 1.1.2.1 public void visit(TEMP e) {
202 cananian 1.3.2.1 assert e.type != Type.POINTER : "Can't determine type for TEMP "+e+".";
203 cananian 1.1.2.1 this.tad = type2tad(e.type());
204 cananian 1.1.2.1 }
205 cananian 1.1.2.1 }
206 cananian 1.1.2.1 // common types.
207 cananian 1.1.2.1 private static final TypeAndDerivation
208 cananian 1.1.2.1 Void = new TypeAndDerivation(HClass.Void),
209 cananian 1.1.2.1 Int = new TypeAndDerivation(HClass.Int),
210 cananian 1.1.2.1 Long = new TypeAndDerivation(HClass.Long),
211 cananian 1.1.2.1 Float = new TypeAndDerivation(HClass.Float),
212 cananian 1.1.2.1 Double = new TypeAndDerivation(HClass.Double);
213 cananian 1.1.2.1 // utility methods for operating on/generating types and derivations
214 cananian 1.1.2.1 private static TypeAndDerivation type2tad(int ty) {
215 cananian 1.1.2.1 switch(ty) {
216 cananian 1.1.2.1 case Type.INT: return Int;
217 cananian 1.1.2.1 case Type.LONG: return Long;
218 cananian 1.1.2.1 case Type.FLOAT: return Float;
219 cananian 1.1.2.1 case Type.DOUBLE: return Double;
220 cananian 1.1.2.1 case Type.POINTER:
221 cananian 1.1.2.1 throw new RuntimeException("Pointers do not have inherent types");
222 cananian 1.1.2.1 default:
223 cananian 1.1.2.1 throw new RuntimeException("Unknown type!");
224 cananian 1.1.2.1 }
225 cananian 1.1.2.1 }
226 cananian 1.1.2.1 private static DList makeDL(TypeAndDerivation tad) {
227 cananian 1.1.2.1 if (tad.derivation != null) return tad.derivation;
228 cananian 1.1.2.1 // have to derive from base pointer.
229 cananian 1.3.2.1 assert tad.type != null;
230 cananian 1.3.2.1 assert tad.type == HClass.Void || !tad.type.isPrimitive();
231 cananian 1.3.2.1 assert tad.temp != null : "Can't derive type if we don't know temp.";
232 cananian 1.1.2.1 return new DList(tad.temp, true, null);
233 cananian 1.1.2.1 }
234 cananian 1.1.2.1 private static TypeAndDerivation TADadd(TypeAndDerivation lefttad,
235 cananian 1.1.2.1 TypeAndDerivation righttad) {
236 cananian 1.1.2.1 // if there's a constant, put it on the right.
237 cananian 1.1.2.6 if (lefttad.type!=null && lefttad.type.isPrimitive() &&
238 cananian 1.1.2.6 !(righttad.type!=null && righttad.type.isPrimitive()))
239 cananian 1.1.2.1 return TADadd(righttad, lefttad);
240 cananian 1.1.2.1 // okay, deal with adding constants (including opaque pointers)
241 cananian 1.1.2.1 if (righttad.type!=null && righttad.type.isPrimitive())
242 cananian 1.1.2.1 if (lefttad.type!=null && lefttad.type.isPrimitive())
243 cananian 1.1.2.1 return new TypeAndDerivation(HClass.Void); // opaque!
244 cananian 1.1.2.1 else // we're adding a constant to a base or derived pointer.
245 cananian 1.1.2.1 return new TypeAndDerivation(makeDL(lefttad));
246 cananian 1.1.2.1 // okay, at this point we have two derived pointers to add.
247 cananian 1.1.2.2 // deal with possible cancellations by adding them the simple
248 cananian 1.1.2.2 // way and then canonicalizing.
249 cananian 1.1.2.2 DList result = makeDL(lefttad);
250 cananian 1.1.2.2 for (DList dl=makeDL(righttad); dl!=null; dl=dl.next)
251 cananian 1.1.2.2 result = new DList(dl.base, dl.sign, result);
252 cananian 1.1.2.2 result = result.canonicalize();
253 cananian 1.1.2.1 return (result==null) ? Void : new TypeAndDerivation(result);
254 cananian 1.1.2.1 }
255 cananian 1.1.2.1 private static TypeAndDerivation TADnegate(TypeAndDerivation tad) {
256 cananian 1.1.2.1 return new TypeAndDerivation(DLnegate(makeDL(tad)));
257 cananian 1.1.2.1 }
258 cananian 1.1.2.1 private static DList DLnegate(DList dl) { // recursive! whee!
259 cananian 1.1.2.1 return (dl==null) ? null :
260 cananian 1.1.2.1 new DList(dl.base, !dl.sign, DLnegate(dl.next));
261 cananian 1.1.2.1 }
262 cananian 1.2 }