1 cananian 1.1.2.25 // Tree.java, created Fri Feb 5 6:48:54 1999 by cananian
2 cananian 1.1.2.1 // Tree.java, created Fri Feb 5 05:53:33 1999 by cananian
3 cananian 1.1.2.1 // Copyright (C) 1999 C. Scott Ananian <cananian@alumni.princeton.edu>
4 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
5 cananian 1.1.2.1 package harpoon.IR.Tree;
6 cananian 1.1.2.1
7 cananian 1.1.2.30 import harpoon.Backend.Generic.RegFileInfo;
8 duncan 1.1.2.5 import harpoon.ClassFile.HCodeEdge;
9 duncan 1.1.2.10 import harpoon.ClassFile.HCodeElement;
10 duncan 1.1.2.2 import harpoon.Temp.CloningTempMap;
11 duncan 1.1.2.2 import harpoon.Temp.Temp;
12 duncan 1.1.2.2 import harpoon.Temp.TempMap;
13 cananian 1.1.2.1 import harpoon.Util.ArrayFactory;
14 sportbilly 1.1.2.8 import harpoon.Util.ArrayIterator;
15 cananian 1.7 import net.cscott.jutil.CombineIterator;
16 cananian 1.1.2.1 import harpoon.Util.Util;
17 cananian 1.1.2.1
18 sportbilly 1.1.2.8 import java.util.AbstractCollection;
19 sportbilly 1.1.2.8 import java.util.Arrays;
20 sportbilly 1.1.2.8 import java.util.Collection;
21 sportbilly 1.1.2.8 import java.util.Collections;
22 duncan 1.1.2.10 import java.util.HashSet;
23 sportbilly 1.1.2.8 import java.util.Iterator;
24 duncan 1.1.2.20 import java.util.LinkedList;
25 duncan 1.1.2.20 import java.util.List;
26 duncan 1.1.2.10 import java.util.Set;
27 duncan 1.1.2.10
28 cananian 1.1.2.1 /**
29 cananian 1.1.2.1 * <code>Tree</code> is the base class for the tree representation.
30 cananian 1.1.2.1 *
31 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
32 cananian 1.7 * @version $Id: Tree.java,v 1.7 2004/02/08 01:55:51 cananian Exp $
33 cananian 1.1.2.1 */
34 cananian 1.1.2.1 public abstract class Tree
35 cananian 1.1.2.32 implements HCodeElement
36 cananian 1.1.2.1 {
37 cananian 1.1.2.26 final TreeFactory tf;
38 cananian 1.1.2.26 final String source_file;
39 cananian 1.1.2.26 final int source_line;
40 cananian 1.1.2.26 final int id;
41 cananian 1.1.2.26 final private int hashCode;
42 cananian 1.1.2.26
43 cananian 1.1.2.26 private Tree parent = null;
44 cananian 1.1.2.26 private int which_child_of_parent;
45 cananian 1.1.2.26 protected final Tree[] child;
46 duncan 1.1.2.10
47 cananian 1.1.2.26 protected Tree(TreeFactory tf, HCodeElement source, int arity) {
48 cananian 1.3.2.1 assert tf!=null;
49 cananian 1.1.2.1 this.source_file = (source!=null)?source.getSourceFile():"unknown";
50 cananian 1.1.2.1 this.source_line = (source!=null)?source.getLineNumber(): 0;
51 cananian 1.1.2.1 this.id = tf.getUniqueID();
52 cananian 1.1.2.1 this.tf = tf;
53 cananian 1.1.2.26 this.child = new Tree[arity];
54 cananian 1.1.2.1 // cache hashcode for efficiency.
55 cananian 1.1.2.15 this.hashCode = this.id ^ tf.hashCode();
56 cananian 1.1.2.1 }
57 duncan 1.1.2.4
58 cananian 1.1.2.26 public final int hashCode() { return hashCode; }
59 cananian 1.1.2.1
60 cananian 1.1.2.1 /** Returns the <code>TreeFactory</code> that generated this
61 cananian 1.1.2.1 * <code>Tree</code>. */
62 cananian 1.1.2.26 public final TreeFactory getFactory() { return tf; }
63 duncan 1.1.2.20
64 duncan 1.1.2.20 //
65 duncan 1.1.2.20 // FIXME: add more documentation
66 duncan 1.1.2.20 // to the sibling/parent methods
67 duncan 1.1.2.20 //
68 duncan 1.1.2.20
69 duncan 1.1.2.20 /**
70 cananian 1.1.2.26 * Returns the leftmost child of this tree, or null if this
71 cananian 1.1.2.26 * node has no children.
72 duncan 1.1.2.20 */
73 cananian 1.1.2.26 public final Tree getFirstChild() {
74 cananian 1.1.2.26 return child.length > 0 ? child[0] : null;
75 cananian 1.1.2.26 }
76 duncan 1.1.2.20
77 duncan 1.1.2.20 /**
78 duncan 1.1.2.20 * Returns the right sibling of this tree, null if there are no
79 duncan 1.1.2.20 * siblings to the right of this node.
80 duncan 1.1.2.20 */
81 cananian 1.1.2.26 public final Tree getSibling() {
82 salcianu 1.6 assert parent!=null : "don't call getSibling() on the root!";
83 cananian 1.3.2.1 assert this==parent.child[which_child_of_parent];
84 cananian 1.1.2.26 int c = which_child_of_parent + 1;
85 cananian 1.1.2.26 return parent.child.length > c ? parent.child[c] : null;
86 cananian 1.1.2.26 }
87 duncan 1.1.2.20
88 duncan 1.1.2.20 /**
89 duncan 1.1.2.20 * Returns the parent of this tree. If this tree is the
90 duncan 1.1.2.20 * root node, then returns <code>null</code>.
91 duncan 1.1.2.20 */
92 cananian 1.1.2.26 public final Tree getParent() { return this.parent; }
93 cananian 1.1.2.26
94 cananian 1.1.2.26 /** Fetch from the child array -- for subclass use only. The subclass
95 cananian 1.1.2.26 * will provide named accessors to the public (ie, getDst(), getLeft()).
96 cananian 1.1.2.26 */
97 cananian 1.1.2.26 protected final Tree getChild(int which) { return child[which]; }
98 cananian 1.1.2.26 /**
99 cananian 1.1.2.26 * Modify the child array -- for subclass use only. The subclass will
100 cananian 1.1.2.26 * provide named accessors to the public (ie, setDst(), setLeft() ).
101 cananian 1.1.2.26 */
102 cananian 1.1.2.26 protected final void setChild(int which, Tree newChild) {
103 cananian 1.3.2.1 assert newChild!=null : "you can't set a tree child to null";
104 cananian 1.3.2.1 assert newChild.tf==this.tf : "tree factories must match";
105 salcianu 1.6 // if we enable this assertion, Canonicalize crashes
106 salcianu 1.6 //assert newChild.parent==null : "only one parent per node"; // [AS]
107 cananian 1.1.2.26 if (child[which]!=null) child[which].unlink();
108 cananian 1.1.2.26 child[which] = newChild;
109 cananian 1.1.2.26 newChild.parent = this;
110 cananian 1.1.2.26 newChild.which_child_of_parent = which;
111 cananian 1.5 // increment parent's modification count (for fail-fast iterator)
112 cananian 1.5 tf.incModCount();
113 cananian 1.1.2.26 }
114 cananian 1.1.2.26 /** Replace the tree rooted at <code>this</code> with a new tree. */
115 cananian 1.1.2.26 public final void replace(Tree newTree) {
116 cananian 1.1.2.26 parent.setChild(which_child_of_parent, newTree);
117 cananian 1.1.2.26 }
118 cananian 1.1.2.26 /** Make <code>this</code> a root-level tree, unlinking it from
119 cananian 1.1.2.26 * its parent. */
120 salcianu 1.6 public final void unlink() {
121 cananian 1.5 // increment parent's modification count (for fail-fast iterator)
122 cananian 1.5 tf.incModCount();
123 cananian 1.5 // do unlink.
124 salcianu 1.6 // unlinking = any link between parent and child disappears [AS]
125 salcianu 1.6 if(parent != null) {
126 salcianu 1.6 // parent -> child link removed [AS]
127 salcianu 1.6 parent.child[which_child_of_parent] = null;
128 salcianu 1.6 // child -> parent link removed [AS]
129 salcianu 1.6 parent=null;
130 salcianu 1.6 which_child_of_parent=0;
131 salcianu 1.6 }
132 cananian 1.5 }
133 duncan 1.1.2.20
134 cananian 1.1.2.1 /** Returns the original source file name that this <code>Tree</code> is
135 cananian 1.1.2.1 * derived from. */
136 cananian 1.1.2.26 public final String getSourceFile() { return source_file; }
137 cananian 1.1.2.1 /** Returns the line in the original source file that this
138 cananian 1.1.2.1 * <code>Tree</code> is derived from. */
139 cananian 1.1.2.26 public final int getLineNumber() { return source_line; }
140 cananian 1.1.2.1 /** Returns a unique numeric identifier for this <code>Tree</code>. */
141 cananian 1.1.2.26 public final int getID() { return id; }
142 cananian 1.1.2.1
143 duncan 1.1.2.9 /** Return an integer enumeration of the kind of this
144 duncan 1.1.2.9 * <code>Tree</code>. The enumerated values are defined in
145 duncan 1.1.2.9 * <code>TreeKind</code>. */
146 duncan 1.1.2.9 public abstract int kind();
147 duncan 1.1.2.9
148 cananian 1.1.2.1 /** Accept a visitor. */
149 cananian 1.1.2.16 public abstract void accept(TreeVisitor v);
150 cananian 1.1.2.1
151 cananian 1.1.2.1 /** Array factory: returns <code>Tree[]</code>. */
152 cananian 1.3.2.2 public static final ArrayFactory<Tree> arrayFactory =
153 cananian 1.3.2.2 new ArrayFactory<Tree>() {
154 cananian 1.3.2.2 public Tree[] newArray(int len) { return new Tree[len]; }
155 cananian 1.1.2.1 };
156 duncan 1.1.2.2
157 duncan 1.1.2.2
158 duncan 1.1.2.12 /**
159 cananian 1.1.2.28 * Returns a clone of <code>root</code>. The <code>callback()</code>
160 cananian 1.1.2.28 * method of the supplied <code>CloneCallback</code> will be invoked
161 cananian 1.1.2.28 * with every cloned subtree, from the bottom up to the root. The
162 cananian 1.1.2.28 * cloned subtree will be generated using the supplied
163 cananian 1.1.2.28 * <code>TreeFactory</code>, <code>ntf</code>.
164 cananian 1.1.2.28 * @return the root of the cloned tree.
165 cananian 1.1.2.28 * <p>
166 duncan 1.1.2.12 * NOTE: tree objects may actually contain temps from two different
167 duncan 1.1.2.12 * temp factories. The first temp factory with which a tree's
168 duncan 1.1.2.12 * temps may be associated is the <code>TempFactory</code>
169 duncan 1.1.2.12 * stored in their <code>TreeFactory</code>. The second
170 duncan 1.1.2.12 * is the <code>TempFactory</code> used by the tree's
171 duncan 1.1.2.12 * <code>Frame</code> to generate registers. Since these
172 duncan 1.1.2.12 * registers are assumed to be immutable, no temps from that
173 duncan 1.1.2.12 * temp factory will be cloned by this method. All other temps
174 cananian 1.1.2.28 * will be cloned using a new <code>CloningTempMap</code>.
175 duncan 1.1.2.6 */
176 cananian 1.1.2.28 public static Tree clone(TreeFactory ntf, Tree root, CloneCallback cb) {
177 duncan 1.1.2.6 if (root==null) return null;
178 cananian 1.1.2.28 if (cb==null) cb = nullCallback;
179 cananian 1.1.2.30 final RegFileInfo rfi = root.tf.getFrame().getRegFileInfo();
180 cananian 1.1.2.30 CloningTempMap ctm = (ntf==root.tf) ? null :
181 cananian 1.1.2.30 new CloningTempMap(root.tf.tempFactory(), ntf.tempFactory()) {
182 cananian 1.1.2.30 public Temp tempMap(Temp t) { // don't clone registers!
183 cananian 1.1.2.30 return rfi.isRegister(t) ? t : super.tempMap(t);
184 cananian 1.1.2.30 }
185 cananian 1.1.2.30 };
186 cananian 1.1.2.28 return root.rename(ntf, ctm, cb);
187 cananian 1.1.2.28 }
188 cananian 1.1.2.28 /** Clone a subtree. This is a *deep* copy -- ie, this node and
189 cananian 1.1.2.28 * nodes rooted here are copied, all the way down to the leaves.
190 cananian 1.1.2.28 * The cloned subtree will have the same tree factory as
191 cananian 1.1.2.28 * <code>this</code>. */
192 cananian 1.3.2.2 public final Tree clone() { return rename(null); }
193 cananian 1.1.2.28 /** Rename while cloning a subtree. This node and all child nodes
194 cananian 1.1.2.28 * are cloned; the 'temp' information of all <code>TEMP</code> nodes
195 cananian 1.1.2.28 * are renamed according to the supplied <code>TempMap</code>.
196 cananian 1.1.2.28 * Note that <code>Temp</code>s not belonging to
197 cananian 1.1.2.28 * <code>this.getFactory().tempFactory()</code> are not affected. */
198 cananian 1.1.2.28 public final Tree rename(TempMap tm) {
199 cananian 1.1.2.28 return rename(this.tf, tm, nullCallback);
200 cananian 1.1.2.28 }
201 cananian 1.1.2.28 /** Rename while cloning a subtree. This node and all child nodes
202 cananian 1.1.2.28 * are cloned; the 'temp' information of all <code>TEMP</code> nodes
203 cananian 1.1.2.28 * are renamed according to the supplied <code>TempMap</code>.
204 cananian 1.1.2.28 * Note that <code>Temp</code>s not belonging to
205 cananian 1.1.2.28 * <code>this.getFactory().tempFactory()</code> are not affected.
206 cananian 1.1.2.28 * The <code>callback()</code> method of the supplied
207 cananian 1.1.2.28 * <code>CloneCallback</code> is invoked once on each subtree cloned,
208 cananian 1.1.2.28 * starting from the leaves and working back to the root in a
209 cananian 1.1.2.28 * post-order depth-first manner. */
210 cananian 1.1.2.28 // --- this is what each tree subclass must implement ---
211 cananian 1.1.2.28 public abstract Tree rename(TreeFactory tf, TempMap tm, CloneCallback cb);
212 cananian 1.1.2.28
213 cananian 1.1.2.28 /** Callback interface to tree cloning code to allow you to update
214 cananian 1.1.2.28 * type and other annotations as the tree is cloned. */
215 cananian 1.1.2.28 public interface CloneCallback {
216 cananian 1.1.2.28 /** This method will be called once for every cloned/renamed subtree.
217 cananian 1.1.2.28 * The original tree will be passed in as <code>oldTree</code> and
218 cananian 1.1.2.28 * the new, cloned/renamed tree will be passed in as
219 cananian 1.1.2.28 * <code>newTree</code>. The return value of this function will
220 cananian 1.1.2.28 * be linked in to the cloned parent, so substitutions on the
221 cananian 1.1.2.28 * cloned-tree-in-progress can be made by returning something
222 cananian 1.1.2.28 * other than <code>newTree</code>. In normal use, however,
223 cananian 1.1.2.29 * <code>newTree</code> should always be returned.
224 cananian 1.1.2.29 * <p>The supplied <code>TempMap</code> specifies the
225 cananian 1.1.2.29 * <code>Temp</code> mapping in effect for the cloning
226 cananian 1.1.2.29 * operation. This allows you to update tree information
227 cananian 1.1.2.29 * which is tied to <code>Temp</code>s. */
228 cananian 1.1.2.29 public Tree callback(Tree oldTree, Tree newTree, TempMap tm);
229 cananian 1.1.2.28 }
230 cananian 1.1.2.28 /** A do-nothing callback. Comes in handy sometimes. */
231 cananian 1.1.2.28 private static final CloneCallback nullCallback = new CloneCallback() {
232 cananian 1.1.2.29 public Tree callback(Tree o, Tree n, TempMap tm) { return n; }
233 cananian 1.1.2.28 };
234 duncan 1.1.2.2
235 duncan 1.1.2.20 /** Return a list of subexpressions of this <code>Tree</code>. */
236 cananian 1.1.2.26 public ExpList kids() { // by default, make kids list from all children.
237 cananian 1.1.2.26 ExpList r=null;
238 cananian 1.1.2.26 for (int i=child.length-1; i>=0; i--)
239 cananian 1.1.2.26 r = new ExpList((Exp)child[i], r);
240 cananian 1.1.2.26 return r;
241 duncan 1.1.2.5 }
242 cananian 1.1.2.1 }
243 duncan 1.1.2.20
244 duncan 1.1.2.6
245 duncan 1.1.2.6
246 duncan 1.1.2.6
247 duncan 1.1.2.6
248 duncan 1.1.2.6
249 duncan 1.1.2.6
250 duncan 1.1.2.6
251 duncan 1.1.2.6
252 duncan 1.1.2.6
253 duncan 1.1.2.4
254 duncan 1.1.2.4
255 cananian 1.2