1 cananian 1.1.2.1 // Code.java, created Fri Aug 7 13:45:29 1998 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1998 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.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.20 import harpoon.Analysis.AllocationInformationMap;
7 cananian 1.1.2.15 import harpoon.Analysis.Maps.AllocationInformation;
8 cananian 1.1.2.16 import harpoon.Analysis.Maps.Derivation;
9 cananian 1.1.2.6 import harpoon.ClassFile.HCode;
10 cananian 1.1.2.18 import harpoon.ClassFile.HCodeAndMaps;
11 cananian 1.1.2.6 import harpoon.ClassFile.HCodeElement;
12 cananian 1.1.2.6 import harpoon.ClassFile.HMethod;
13 cananian 1.1.2.4 import harpoon.Temp.Temp;
14 cananian 1.1.2.18 import harpoon.Temp.TempMap;
15 cananian 1.1.2.4 import harpoon.Temp.TempFactory;
16 cananian 1.1.2.1 import harpoon.Util.ArrayFactory;
17 cananian 1.13 import harpoon.Util.Collections.Graph;
18 cananian 1.14 import net.cscott.jutil.UnmodifiableIterator;
19 cananian 1.1.2.10 import harpoon.Util.Util;
20 cananian 1.1.2.1
21 cananian 1.13 import java.util.AbstractSet;
22 cananian 1.13 import java.util.ArrayList;
23 cananian 1.7 import java.util.ConcurrentModificationException;
24 cananian 1.1.2.9 import java.util.HashSet;
25 cananian 1.1.2.9 import java.util.Iterator;
26 cananian 1.13 import java.util.List;
27 cananian 1.1.2.18 import java.util.Map;
28 cananian 1.1.2.1 import java.util.NoSuchElementException;
29 cananian 1.1.2.9 import java.util.Set;
30 cananian 1.1.2.1 import java.util.Stack;
31 cananian 1.1.2.1
32 cananian 1.1.2.1 /**
33 cananian 1.1.2.1 * <code>Quads.Code</code> is an abstract superclass of codeviews
34 cananian 1.1.2.1 * using the components in <code>IR.Quads</code>. It implements
35 cananian 1.1.2.1 * shared methods for the various codeviews using <code>Quad</code>s.
36 cananian 1.1.2.1 *
37 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
38 cananian 1.14 * @version $Id: Code.java,v 1.14 2004/02/08 01:55:25 cananian Exp $
39 cananian 1.1.2.1 */
40 cananian 1.3.2.2 public abstract class Code extends HCode<Quad>
41 cananian 1.13 implements java.io.Serializable, Graph<Quad,Edge> {
42 cananian 1.1.2.1 /** The method that this code view represents. */
43 cananian 1.1.2.6 protected final HMethod parent;
44 cananian 1.1.2.1 /** The quadruples composing this code view. */
45 cananian 1.1.2.6 protected Quad quads;
46 cananian 1.1.2.4 /** Quad factory. */
47 cananian 1.1.2.6 protected final QuadFactory qf;
48 cananian 1.1.2.15 /** <code>AllocationInformation</code> for this <code>HCode</code>. */
49 cananian 1.14 protected AllocationInformation<Quad> ai = null;
50 cananian 1.7 /** Keep track of modifications to this <code>Code</code> so that the
51 cananian 1.7 * <code>getElementsI()</code> <code>Iterator</code> can fail-fast. */
52 cananian 1.7 int modCount=0;
53 cananian 1.1.2.1
54 cananian 1.1.2.6 /** Create a proper QuadFactory. */
55 cananian 1.1.2.6 protected QuadFactory newQF(final HMethod parent) {
56 cananian 1.1.2.4 final String scope = parent.getDeclaringClass().getName() + "." +
57 cananian 1.1.2.4 parent.getName() + parent.getDescriptor() + "/" + getName();
58 cananian 1.1.2.14 abstract class SerializableQuadFactory extends QuadFactory
59 cananian 1.1.2.14 implements java.io.Serializable { /* only declare inheritance */ }
60 cananian 1.1.2.14 return new SerializableQuadFactory() {
61 cananian 1.1.2.4 private final TempFactory tf = Temp.tempFactory(scope);
62 cananian 1.1.2.4 private int id=0;
63 cananian 1.1.2.4 public TempFactory tempFactory() { return tf; }
64 cananian 1.1.2.4 public Code getParent() { return Code.this; }
65 cananian 1.1.2.6 public synchronized int getUniqueID() { return id++; }
66 cananian 1.1.2.4 };
67 cananian 1.1.2.6 }
68 cananian 1.1.2.6 /** constructor. */
69 cananian 1.1.2.6 protected Code(final HMethod parent, final Quad quads) {
70 cananian 1.1.2.6 this.parent = parent; this.quads = quads;
71 cananian 1.1.2.6 this.qf = newQF(parent);
72 cananian 1.1.2.1 }
73 cananian 1.1.2.1
74 cananian 1.1.2.1 /** Clone this code representation. The clone has its own
75 cananian 1.1.2.1 * copy of the quad graph. */
76 cananian 1.8 public abstract HCodeAndMaps<Quad> clone(HMethod newMethod);
77 cananian 1.1.2.18 /** Helper for clone */
78 cananian 1.8 protected final HCodeAndMaps<Quad> cloneHelper(final Code qc) {
79 cananian 1.1.2.19 return cloneHelper(this, qc);
80 cananian 1.1.2.19 }
81 cananian 1.1.2.19 /** Helper for clone */
82 cananian 1.8 protected HCodeAndMaps<Quad> cloneHelper(Code _this, Code qc) {
83 cananian 1.8 HCodeAndMaps<Quad> hcam = Quad.cloneWithMaps(qc.qf, _this.quads);
84 cananian 1.1.2.21 // fill in the missing info in the hcam.
85 cananian 1.8 hcam = new HCodeAndMaps<Quad>(qc,
86 cananian 1.3.2.2 hcam.elementMap(), hcam.tempMap(),
87 cananian 1.3.2.3 _this,
88 cananian 1.3.2.2 hcam.ancestorElementMap(),
89 cananian 1.1.2.21 hcam.ancestorTempMap());
90 cananian 1.1.2.21 // finish setting up qc.
91 cananian 1.1.2.19 qc.quads = (HEADER) hcam.elementMap().get(_this.quads);
92 cananian 1.1.2.20 // clone allocation information.
93 cananian 1.1.2.20 if (_this.getAllocationInformation()!=null)
94 cananian 1.1.2.20 qc.setAllocationInformation(cloneAllocationInformation(hcam));
95 cananian 1.1.2.20 // derivation is cloned in LowQuad.cloneHelper()
96 cananian 1.1.2.21 return hcam;
97 cananian 1.1.2.20 }
98 cananian 1.14 private static AllocationInformation<Quad> cloneAllocationInformation
99 cananian 1.14 (HCodeAndMaps<Quad> hcam) {
100 cananian 1.1.2.20 Code ocode = (Code) hcam.ancestorHCode();
101 cananian 1.14 AllocationInformation<Quad> oaim = ocode.getAllocationInformation();
102 cananian 1.1.2.20 AllocationInformationMap naim = new AllocationInformationMap();
103 cananian 1.14 for (Iterator<Quad> it=ocode.getElementsI(); it.hasNext(); ) {
104 cananian 1.14 Quad ohce = it.next();
105 cananian 1.14 Quad nhce = hcam.elementMap().get(ohce);
106 cananian 1.1.2.20 if (ohce instanceof ANEW || ohce instanceof NEW)
107 cananian 1.1.2.20 naim.transfer(nhce, ohce, hcam.tempMap(), oaim);
108 cananian 1.1.2.20 }
109 cananian 1.1.2.20 return naim;
110 cananian 1.1.2.18 }
111 cananian 1.1.2.18
112 cananian 1.1.2.1 /**
113 cananian 1.1.2.1 * Return the name of this code view.
114 cananian 1.1.2.1 */
115 cananian 1.1.2.1 public abstract String getName();
116 cananian 1.1.2.1
117 cananian 1.1.2.1 /**
118 cananian 1.1.2.1 * Return the <code>HMethod</code> this codeview
119 cananian 1.1.2.1 * belongs to.
120 cananian 1.1.2.1 */
121 cananian 1.1.2.1 public HMethod getMethod() { return parent; }
122 cananian 1.1.2.15
123 cananian 1.1.2.15 /**
124 cananian 1.1.2.15 * Return the <code>AllocationInformation</code> for this codeview.
125 cananian 1.1.2.15 */
126 cananian 1.14 public AllocationInformation<Quad> getAllocationInformation() { return ai; }
127 cananian 1.1.2.15 /**
128 cananian 1.1.2.15 * Set an <code>AllocationInformation</code> for this codeview.
129 cananian 1.1.2.15 */
130 cananian 1.14 public void setAllocationInformation(AllocationInformation<Quad> ai) {
131 cananian 1.1.2.15 this.ai = ai;
132 cananian 1.1.2.15 }
133 cananian 1.1.2.16 /**
134 cananian 1.1.2.16 * Return a <code>Derivation</code> for this codeview.
135 cananian 1.1.2.16 * @return <code>null</code>, always.
136 cananian 1.1.2.16 */
137 cananian 1.12 public Derivation<Quad> getDerivation() { return null; }
138 cananian 1.1.2.1
139 cananian 1.1.2.1 /** Returns the root of the control flow graph. */
140 cananian 1.3.2.2 public HEADER getRootElement() { return (HEADER) quads; }
141 cananian 1.1.2.1 /** Returns the leaves of the control flow graph. */
142 cananian 1.3.2.2 public Quad[] getLeafElements() {
143 cananian 1.1.2.1 HEADER h = (HEADER) getRootElement();
144 cananian 1.1.2.2 return new Quad[] { h.footer() };
145 cananian 1.1.2.1 }
146 cananian 1.1.2.1
147 cananian 1.1.2.1 /**
148 cananian 1.1.2.1 * Returns an ordered list of the <code>Quad</code>s
149 cananian 1.1.2.1 * making up this code view. The root of the graph
150 cananian 1.1.2.1 * is in element 0 of the array.
151 cananian 1.9 * @deprecated
152 cananian 1.1.2.1 */
153 cananian 1.3.2.2 public Quad[] getElements() { return super.getElements(); }
154 cananian 1.1.2.1
155 cananian 1.1.2.9 /** Returns an iterator over the <code>Quad</code>s making up
156 cananian 1.1.2.1 * this code view. The root of the graph is the first element
157 cananian 1.1.2.9 * in the iteration. */
158 cananian 1.3.2.2 public Iterator<Quad> getElementsI() {
159 cananian 1.3.2.2 return new UnmodifiableIterator<Quad>() {
160 cananian 1.7 // record # of modifications to enable fail-fast.
161 cananian 1.7 int modCount = Code.this.modCount;
162 cananian 1.7 // set up visited set and to-do stack.
163 cananian 1.3.2.2 Set<Quad> visited = new HashSet<Quad>();
164 cananian 1.3.2.2 Stack<Quad> s = new Stack<Quad>();
165 cananian 1.1.2.1 { // initialize stack/set.
166 cananian 1.1.2.9 s.push(getLeafElements()[0]); visited.add(s.peek());
167 cananian 1.1.2.9 s.push(getRootElement()); visited.add(s.peek());
168 cananian 1.1.2.1 }
169 cananian 1.1.2.9 public boolean hasNext() { return !s.isEmpty(); }
170 cananian 1.3.2.2 public Quad next() {
171 cananian 1.7 if (modCount != Code.this.modCount)
172 cananian 1.7 throw new ConcurrentModificationException();
173 cananian 1.1.2.1 if (s.empty()) throw new NoSuchElementException();
174 cananian 1.3.2.2 Quad q = s.pop();
175 cananian 1.1.2.24 boolean forwards = false;
176 cananian 1.1.2.24 // prettiness hack! try to order elements in original source
177 cananian 1.1.2.24 // order. =)
178 cananian 1.1.2.24 if (q.nextLength()==2 &&
179 cananian 1.1.2.24 q.next(1).getLineNumber() < q.next(0).getLineNumber())
180 cananian 1.1.2.24 forwards = true;
181 cananian 1.1.2.1 // push successors on stack before returning.
182 cananian 1.1.2.24 for (int i= forwards ? 0 : (q.nextLength()-1);
183 cananian 1.1.2.24 forwards ? (i<q.nextLength()) : (i>=0);
184 cananian 1.1.2.24 i = forwards ? (i+1) : (i-1)) {
185 cananian 1.3.2.1 assert q.nextEdge(i)!=null : q;
186 cananian 1.1.2.12 if (!visited.contains(q.next(i))) {
187 cananian 1.1.2.12 s.push(q.next(i));
188 cananian 1.1.2.12 visited.add(q.next(i));
189 cananian 1.1.2.1 }
190 cananian 1.1.2.17 }
191 cananian 1.1.2.17 // let's validate q quickly here.
192 cananian 1.1.2.17 for (int i=q.prevLength()-1; i>=0; i--)
193 cananian 1.3.2.1 assert q.prevEdge(i)!=null : q;
194 cananian 1.1.2.1 // okay.
195 cananian 1.1.2.1 return q;
196 cananian 1.1.2.1 }
197 cananian 1.1.2.1 };
198 cananian 1.1.2.1 }
199 cananian 1.1.2.1 // implement elementArrayFactory which returns Quad[]s.
200 cananian 1.3.2.2 public ArrayFactory<Quad> elementArrayFactory() {
201 cananian 1.3.2.2 return Quad.arrayFactory;
202 cananian 1.13 }
203 cananian 1.13 // Graph interface
204 cananian 1.13 public Set<Quad> nodes() {
205 cananian 1.13 final List<Quad> l = getElementsL();
206 cananian 1.13 return new AbstractSet<Quad>() {
207 cananian 1.13 public Iterator<Quad> iterator() { return l.iterator(); }
208 cananian 1.13 public int size() { return l.size(); }
209 cananian 1.13 };
210 cananian 1.3.2.2 }
211 cananian 1.1.2.3
212 cananian 1.1.2.3 // print this Code.
213 cananian 1.3.2.2 public void print(java.io.PrintWriter pw, PrintCallback<Quad> callback) {
214 cananian 1.1.2.23 Print.print(pw, this, callback);
215 cananian 1.1.2.3 }
216 salcianu 1.5
217 salcianu 1.5 /** Returns the list of all quads <code>q</code> from
218 salcianu 1.5 <code>this</code> code for which <code>q.accept(v)</code> is
219 salcianu 1.5 <code>true</code>. */
220 salcianu 1.5 public List<Quad> selectQuads(QuadValueVisitor<Boolean> v) {
221 salcianu 1.5 final List<Quad> l = new ArrayList<Quad>();
222 salcianu 1.5
223 salcianu 1.5 for(Iterator<Quad> it = getElementsI(); it.hasNext(); ) {
224 salcianu 1.5 Quad q = it.next();
225 salcianu 1.5 if (q.accept(v).booleanValue()) l.add(q);
226 salcianu 1.5 }
227 salcianu 1.5
228 salcianu 1.5 return l;
229 salcianu 1.5 }
230 salcianu 1.5
231 salcianu 1.5
232 salcianu 1.5 /** Returns the list of all <code>CALL</code> quads from
233 salcianu 1.5 <code>this</code> code. */
234 salcianu 1.5 public List<Quad> selectCALLs() {
235 salcianu 1.5 return selectQuads(call_visitor);
236 salcianu 1.5 }
237 salcianu 1.5 private static QuadValueVisitor<Boolean> call_visitor =
238 salcianu 1.5 new QuadValueVisitor<Boolean>() {
239 salcianu 1.5 public Boolean visit(CALL q) {
240 salcianu 1.5 return Boolean.TRUE;
241 salcianu 1.5 }
242 salcianu 1.5 public Boolean visit(Quad q) {
243 salcianu 1.5 return Boolean.FALSE;
244 salcianu 1.5 }
245 salcianu 1.5 };
246 salcianu 1.5
247 salcianu 1.5
248 salcianu 1.5 /** Returns the list of all allocation sites (ie, <code>NEW</code>
249 salcianu 1.5 and <code>ANEW</code> quads) from <code>this</code> code. */
250 salcianu 1.5 public List<Quad> selectAllocations() {
251 salcianu 1.5 return selectQuads(allocation_visitor);
252 salcianu 1.5 }
253 salcianu 1.5 private static QuadValueVisitor<Boolean> allocation_visitor =
254 salcianu 1.5 new QuadValueVisitor<Boolean>() {
255 salcianu 1.5 public Boolean visit(NEW q) {
256 salcianu 1.5 return Boolean.TRUE;
257 salcianu 1.5 }
258 salcianu 1.5 public Boolean visit(ANEW q) {
259 salcianu 1.5 return Boolean.TRUE;
260 salcianu 1.5 }
261 salcianu 1.5 public Boolean visit(Quad q) {
262 salcianu 1.5 return Boolean.FALSE;
263 salcianu 1.5 }
264 salcianu 1.5 };
265 salcianu 1.5
266 salcianu 1.10 /** Subclasses of <code>Code</code> that want to be notified when
267 salcianu 1.10 some optimization replace one of their quads with some other
268 salcianu 1.10 quad can override this method. This can be useful for
269 salcianu 1.10 updating mappings that attach information to quads (i.e.,
270 salcianu 1.10 allocation policies, QuadNoSSA to QuadSSI mappings etc.). See
271 salcianu 1.10 the code of DeadCode.replace for an example.
272 salcianu 1.10
273 salcianu 1.11 @param oldquad quad that is being replaced
274 salcianu 1.11 @param newquad new quad that replaces <code>oldquad</code>
275 salcianu 1.11 @param tm maps old temps to new temps */
276 salcianu 1.11 public void notifyReplace(Quad oldquad, Quad newquad, TempMap tm) { }
277 cananian 1.2 }