1 cananian 1.1.2.24 // Code.java, created Mon Feb 8 16:55:15 1999 by duncan
2 cananian 1.1.2.23 // Copyright (C) 1998 Duncan Bryce <duncan@lcs.mit.edu>
3 cananian 1.1.2.23 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 duncan 1.1.2.1 package harpoon.IR.Tree;
5 duncan 1.1.2.1
6 cananian 1.1.2.41 import harpoon.Analysis.Maps.Derivation;
7 cananian 1.1.2.41 import harpoon.Analysis.Maps.Derivation.DList;
8 duncan 1.1.2.2 import harpoon.Analysis.Maps.TypeMap;
9 duncan 1.1.2.1 import harpoon.Backend.Generic.Frame;
10 duncan 1.1.2.2 import harpoon.ClassFile.HClass;
11 duncan 1.1.2.1 import harpoon.ClassFile.HCode;
12 cananian 1.1.2.51 import harpoon.ClassFile.HCodeAndMaps;
13 duncan 1.1.2.1 import harpoon.ClassFile.HCodeElement;
14 duncan 1.1.2.1 import harpoon.ClassFile.HMethod;
15 duncan 1.1.2.38 import harpoon.IR.Properties.CFGrapher;
16 cananian 1.1.2.46 import harpoon.IR.Properties.UseDefer;
17 duncan 1.1.2.1 import harpoon.Util.ArrayFactory;
18 duncan 1.1.2.12 import harpoon.Util.Util;
19 duncan 1.1.2.12 import harpoon.Temp.LabelList;
20 duncan 1.1.2.1 import harpoon.Temp.Temp;
21 duncan 1.1.2.1 import harpoon.Temp.TempFactory;
22 cananian 1.1.2.51 import harpoon.Temp.TempMap;
23 cananian 1.9 import net.cscott.jutil.UnmodifiableIterator;
24 duncan 1.1.2.1
25 duncan 1.1.2.19 import java.util.ArrayList;
26 cananian 1.1.2.51 import java.util.Collections;
27 cananian 1.6 import java.util.ConcurrentModificationException;
28 duncan 1.1.2.19 import java.util.HashMap;
29 duncan 1.1.2.19 import java.util.HashSet;
30 duncan 1.1.2.19 import java.util.Iterator;
31 duncan 1.1.2.19 import java.util.List;
32 duncan 1.1.2.19 import java.util.Map;
33 duncan 1.1.2.1 import java.util.NoSuchElementException;
34 duncan 1.1.2.19 import java.util.Set;
35 duncan 1.1.2.1 import java.util.Stack;
36 duncan 1.1.2.1
37 duncan 1.1.2.19 /**
38 duncan 1.1.2.19 * <code>Tree.Code</code> is an abstract superclass of codeviews
39 duncan 1.1.2.19 * using the components in <code>IR.Tree</code>. It implements
40 duncan 1.1.2.19 * shared methods for the various codeviews using <code>Tree</code>s.
41 duncan 1.1.2.19 *
42 duncan 1.1.2.19 * @author Duncan Bryce <duncan@lcs.mit.edu>
43 cananian 1.9 * @version $Id: Code.java,v 1.9 2004/02/08 01:55:51 cananian Exp $
44 duncan 1.1.2.19 */
45 cananian 1.3.2.2 public abstract class Code extends HCode<Tree> {
46 duncan 1.1.2.11 /** The Tree Objects composing this code view. */
47 duncan 1.1.2.11 protected Tree tree;
48 pnkfelix 1.1.2.17
49 pnkfelix 1.1.2.17 /** The Frame containing machine-specific information*/
50 andyb 1.1.2.16 protected /* final */ Frame frame;
51 pnkfelix 1.1.2.17
52 duncan 1.1.2.11 /** Tree factory. */
53 andyb 1.1.2.16 protected /* final */ TreeFactory tf;
54 pnkfelix 1.1.2.17
55 duncan 1.1.2.11 /** The method that this code view represents. */
56 andyb 1.1.2.16 protected /* final */ HMethod parent;
57 duncan 1.1.2.1
58 cananian 1.6 /** Keep track of modifications to this <code>Code</code> so that the
59 cananian 1.6 * <code>getElementsI()</code> <code>Iterator</code> can fail-fast. */
60 cananian 1.6 private int modCount=0;
61 cananian 1.6
62 duncan 1.1.2.15 /** Create a proper TreeFactory. */
63 cananian 1.1.2.30 public class TreeFactory extends harpoon.IR.Tree.TreeFactory {
64 cananian 1.1.2.30 private int id=0;
65 cananian 1.1.2.31 private final TempFactory tempf;
66 cananian 1.1.2.31 TreeFactory(String scope) { this.tempf = Temp.tempFactory(scope); }
67 cananian 1.1.2.31 public TempFactory tempFactory() { return tempf; }
68 cananian 1.1.2.30 /** Returns the <code>HCode</code> to which all <code>Exp</code>s and
69 cananian 1.1.2.30 * <code>Stm</code>s generated by this factory belong. */
70 cananian 1.1.2.30 public Code getParent() { return Code.this; }
71 cananian 1.6 /** Indicate that the parent has changed, so that its
72 cananian 1.6 * fail-fast iterators will work correctly. */
73 cananian 1.6 void incModCount() { Code.this.modCount++; }
74 cananian 1.1.2.30 /** Returns the <code>HMethod</code> to which all <code>Exp</code>s and
75 cananian 1.1.2.30 * <code>Stm</code>s generated by this factory belong. */
76 cananian 1.1.2.30 public HMethod getMethod() { return Code.this.getMethod(); }
77 cananian 1.1.2.30 public Frame getFrame() { return Code.this.frame; }
78 cananian 1.1.2.30 synchronized int getUniqueID() { return id++; }
79 cananian 1.1.2.30 public String toString() {
80 cananian 1.1.2.30 return "Code.TreeFactory["+getParent().toString()+"]";
81 cananian 1.1.2.30 }
82 cananian 1.1.2.30 public int hashCode() { return Code.this.hashCode(); }
83 duncan 1.1.2.1 }
84 duncan 1.1.2.1
85 duncan 1.1.2.11 /** constructor. */
86 duncan 1.1.2.11 protected Code(final HMethod parent, final Tree tree,
87 cananian 1.1.2.31 final Frame frame) {
88 duncan 1.1.2.11 final String scope = parent.getDeclaringClass().getName() + "." +
89 duncan 1.1.2.11 parent.getName() + parent.getDescriptor() + "/" + getName();
90 pnkfelix 1.1.2.49
91 duncan 1.1.2.11 this.parent = parent;
92 duncan 1.1.2.11 this.tree = tree;
93 cananian 1.1.2.31 this.frame = frame;
94 cananian 1.1.2.31 this.tf = new TreeFactory(scope);
95 duncan 1.1.2.1 }
96 duncan 1.1.2.1
97 duncan 1.1.2.11 /** Clone this code representation. The clone has its own copy
98 duncan 1.1.2.19 * of the Tree */
99 cananian 1.7 public abstract HCodeAndMaps<Tree> clone(HMethod newMethod, Frame frame);
100 cananian 1.1.2.51 /** Helps to create a proper <code>HCodeAndMaps</code> during cloning */
101 cananian 1.7 protected final HCodeAndMaps<Tree> cloneHelper(final Code tc,
102 cananian 1.1.2.51 final DerivationGenerator dg) {
103 cananian 1.1.2.51 final Tree.CloneCallback ccb =
104 cananian 1.1.2.51 (dg==null) ? null : dg.cloneCallback(getTreeDerivation());
105 cananian 1.7 final Map<Tree,Tree>
106 cananian 1.7 o2nTree = new HashMap<Tree,Tree>(),
107 cananian 1.7 n2oTree = new HashMap<Tree,Tree>();
108 cananian 1.7 final Map<Temp,Temp>
109 cananian 1.7 o2nTemp = new HashMap<Temp,Temp>(),
110 cananian 1.7 n2oTemp = new HashMap<Temp,Temp>();
111 cananian 1.1.2.51 tc.tree = Tree.clone(tc.tf, tree, new Tree.CloneCallback() {
112 cananian 1.1.2.51 public Tree callback(Tree o, Tree n, TempMap tm) {
113 cananian 1.1.2.51 if (ccb!=null) n = ccb.callback(o, n, tm);
114 cananian 1.1.2.51 o2nTree.put(o, n); n2oTree.put(n, o);
115 cananian 1.1.2.51 if (n instanceof TEMP) {
116 cananian 1.1.2.51 Temp oT = ((TEMP)o).temp, nT = ((TEMP)n).temp;
117 cananian 1.1.2.51 o2nTemp.put(oT, nT); n2oTemp.put(nT, oT);
118 cananian 1.1.2.51 }
119 cananian 1.1.2.51 return n;
120 cananian 1.1.2.51 }
121 cananian 1.1.2.51 });
122 cananian 1.1.2.52 class MapTempMap implements TempMap {
123 cananian 1.7 private final Map<Temp,Temp> m;
124 cananian 1.7 MapTempMap(Map<Temp,Temp> m) { this.m = m; }
125 cananian 1.7 public Temp tempMap(Temp t) { return m.get(t); }
126 cananian 1.1.2.52 }
127 cananian 1.7 return new HCodeAndMaps<Tree>(tc,
128 cananian 1.1.2.52 Collections.unmodifiableMap(o2nTree),
129 cananian 1.1.2.52 new MapTempMap(o2nTemp),
130 cananian 1.1.2.52 this,
131 cananian 1.1.2.52 Collections.unmodifiableMap(n2oTree),
132 cananian 1.1.2.52 new MapTempMap(n2oTemp));
133 cananian 1.1.2.51 }
134 cananian 1.1.2.45 /** Clone this code representation. The clone has its own copy
135 cananian 1.1.2.45 * of the Tree */
136 cananian 1.7 public final HCodeAndMaps<Tree> clone(HMethod newMethod) {
137 cananian 1.1.2.45 return clone(newMethod, frame);
138 cananian 1.1.2.45 }
139 duncan 1.1.2.38
140 duncan 1.1.2.38 /** Returns a means to externally associate control flow with this
141 duncan 1.1.2.38 * tree code. If this tree code is modified subsequent to a call
142 duncan 1.1.2.38 * to <code>getGrapher()</code>, the grapher is invalid, this method
143 duncan 1.1.2.38 * should be re-invoked to acquire a new grapher.
144 duncan 1.1.2.38 */
145 cananian 1.3.2.3 public CFGrapher<Tree> getGrapher() { return new TreeGrapher(this); }
146 cananian 1.1.2.46 /** Returns a means to externally associate use/def information with
147 cananian 1.1.2.46 * this tree code. MOVE(TEMP(t), ...) and CALL/NATIVECALLs are treated
148 cananian 1.1.2.46 * as defs; all instances of TEMP in any of the subtrees returned
149 cananian 1.1.2.46 * by the <code>kids()</code> method are considered uses. Not
150 cananian 1.1.2.46 * valid for non-canonical forms. */
151 cananian 1.3.2.3 public UseDefer<Tree> getUseDefer() { return new TreeUseDefer(this); }
152 duncan 1.1.2.38
153 duncan 1.1.2.11 /** Return the name of this code view. */
154 duncan 1.1.2.11 public abstract String getName();
155 duncan 1.1.2.19
156 duncan 1.1.2.11 /** Return the <code>HMethod</code> this codeview
157 duncan 1.1.2.19 * belongs to. */
158 duncan 1.1.2.11 public HMethod getMethod() { return this.parent; }
159 duncan 1.1.2.1
160 duncan 1.1.2.11 public Frame getFrame() { return this.frame; }
161 andyb 1.1.2.9
162 cananian 1.1.2.42 public abstract TreeDerivation getTreeDerivation();
163 cananian 1.1.2.42
164 duncan 1.1.2.11 /** Returns the root of the Tree */
165 cananian 1.3.2.2 public Tree getRootElement() {
166 duncan 1.1.2.21 // Ensures that the root is a SEQ, and the first instruction is
167 duncan 1.1.2.21 // a SEGMENT.
168 duncan 1.1.2.27 Tree first = (SEQ)this.tree;
169 duncan 1.1.2.39 while(first.kind()==TreeKind.SEQ) first = ((SEQ)first).getLeft();
170 cananian 1.3.2.1 assert first.kind()==TreeKind.SEGMENT;
171 duncan 1.1.2.21 return this.tree;
172 duncan 1.1.2.21 }
173 duncan 1.1.2.1
174 duncan 1.1.2.11 /** Returns the leaves of the Tree */
175 cananian 1.3.2.2 public Tree[] getLeafElements() {
176 cananian 1.1.2.44 // what exactly does 'leaf elements' *mean* in this context?
177 cananian 1.1.2.44 return new Tree[0];
178 duncan 1.1.2.1 }
179 duncan 1.1.2.1
180 duncan 1.1.2.11 /**
181 duncan 1.1.2.19 * Returns an ordered list of the <code>Tree</code> Objects
182 duncan 1.1.2.19 * making up this code view. The root of the tree
183 duncan 1.1.2.19 * is in element 0 of the array.
184 cananian 1.8 * @deprecated
185 duncan 1.1.2.19 */
186 cananian 1.3.2.2 public Tree[] getElements() {
187 duncan 1.1.2.19 return super.getElements();
188 duncan 1.1.2.1 }
189 duncan 1.1.2.1
190 duncan 1.1.2.19 /**
191 duncan 1.1.2.19 * Returns an <code>Iterator</code> of the <code>Tree</code> Objects
192 duncan 1.1.2.19 * making up this code view. The root of the tree is the first element
193 cananian 1.1.2.48 * of the Iterator. Returns the elements of the tree in depth-first
194 cananian 1.1.2.48 * pre-order.
195 duncan 1.1.2.19 */
196 cananian 1.3.2.2 public Iterator<Tree> getElementsI() {
197 cananian 1.3.2.2 return new UnmodifiableIterator<Tree>() {
198 cananian 1.6 // record # of modifications to enable fail-fast.
199 cananian 1.6 int modCount = Code.this.modCount;
200 cananian 1.6 // set up worklists.
201 cananian 1.3.2.2 Stack<Tree> stack = new Stack<Tree>(), aux = new Stack<Tree>();
202 cananian 1.1.2.44 { // initialize stack/set
203 cananian 1.1.2.48 stack.push(getRootElement());
204 duncan 1.1.2.11 }
205 cananian 1.1.2.44 public boolean hasNext() { return !stack.isEmpty(); }
206 cananian 1.3.2.2 public Tree next() {
207 cananian 1.6 if (modCount != Code.this.modCount)
208 cananian 1.6 throw new ConcurrentModificationException();
209 duncan 1.1.2.11 if (stack.isEmpty()) throw new NoSuchElementException();
210 cananian 1.3.2.2 Tree t = stack.pop();
211 cananian 1.1.2.44 // Push successors on stack before returning
212 cananian 1.1.2.44 // (reverse the order twice to get things right)
213 cananian 1.1.2.44 for (Tree tp = t.getFirstChild(); tp!=null; tp=tp.getSibling())
214 cananian 1.1.2.48 aux.push(tp);
215 cananian 1.1.2.44 while (!aux.isEmpty())
216 cananian 1.1.2.44 stack.push(aux.pop()); //LIFO twice.
217 duncan 1.1.2.11 return t;
218 duncan 1.1.2.1 }
219 duncan 1.1.2.11 };
220 duncan 1.1.2.1 }
221 duncan 1.1.2.1
222 duncan 1.1.2.11 // implement elementArrayFactory which returns Tree[]s.
223 cananian 1.3.2.2 public ArrayFactory<Tree> elementArrayFactory() {
224 cananian 1.3.2.2 return Tree.arrayFactory;
225 cananian 1.3.2.2 }
226 andyb 1.1.2.6
227 cananian 1.3.2.2 public void print(java.io.PrintWriter pw, PrintCallback<Tree> callback) {
228 cananian 1.1.2.53 Print.print(pw, this, callback);
229 duncan 1.1.2.11 }
230 andyb 1.1.2.7
231 duncan 1.1.2.19 /**
232 duncan 1.1.2.19 * Returns true if this codeview is a canonical representation
233 duncan 1.1.2.19 */
234 duncan 1.1.2.19 public abstract boolean isCanonical();
235 duncan 1.1.2.12
236 duncan 1.1.2.40 /**
237 duncan 1.1.2.40 * Removes the specified <code>Stm</code> from the tree in which it
238 duncan 1.1.2.40 * resides.
239 duncan 1.1.2.40 *
240 duncan 1.1.2.40 * <br><b>Requires:</b>
241 duncan 1.1.2.40 * <ol>
242 duncan 1.1.2.40 * <li><code>stm</code> is not of type <code>SEQ</code>.
243 duncan 1.1.2.40 * <li><code>stm.getParent()</code> must be of type <code>SEQ</code>.
244 duncan 1.1.2.40 * <li><code>stm</code> is an element of this codeview.
245 duncan 1.1.2.40 * <li><code>stm</code> is not the root element of this codeview.
246 duncan 1.1.2.40 * </ol>
247 duncan 1.1.2.40 * <br><b>Effects:</b>
248 duncan 1.1.2.40 * Removes <code>stm</code> from this tree.
249 duncan 1.1.2.40 */
250 duncan 1.1.2.40 public void remove(Stm stm) {
251 cananian 1.3.2.1 assert stm.kind() != TreeKind.SEQ;
252 cananian 1.3.2.1 assert stm.getFactory() == this.tf;
253 cananian 1.3.2.1 assert this.tf.getParent() == this;
254 duncan 1.1.2.40
255 duncan 1.1.2.40 // All predecessors in canonical tree form must be SEQs
256 duncan 1.1.2.40 SEQ pred = (SEQ)stm.getParent();
257 duncan 1.1.2.40 Stm newPred;
258 duncan 1.1.2.40
259 duncan 1.1.2.40 if (pred.getLeft()==stm) { newPred = pred.getRight(); }
260 duncan 1.1.2.40 else if (pred.getRight()==stm) { newPred = pred.getLeft(); }
261 duncan 1.1.2.40 else { throw new Error("Invalid tree form!"); }
262 duncan 1.1.2.40
263 duncan 1.1.2.40 if (pred.getParent() == null) {
264 duncan 1.1.2.40 // Pred has no parents, it must be the root of the tree.
265 cananian 1.3.2.1 assert pred == this.tree;
266 duncan 1.1.2.40 this.tree = newPred;
267 cananian 1.1.2.43 this.tree.unlink();
268 duncan 1.1.2.40 }
269 duncan 1.1.2.40 else {
270 cananian 1.1.2.44 pred.replace(newPred);
271 duncan 1.1.2.40 }
272 duncan 1.1.2.40 }
273 duncan 1.1.2.1 }
274 duncan 1.1.2.40
275 cananian 1.2