1 cananian 1.1.2.1 // CFGrapher.java, created Mon Nov 29 23:32:45 1999 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1999 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.Properties;
5 cananian 1.1.2.1
6 cananian 1.1.2.3 import harpoon.ClassFile.HCode;
7 cananian 1.1.2.1 import harpoon.ClassFile.HCodeEdge;
8 cananian 1.1.2.1 import harpoon.ClassFile.HCodeElement;
9 cananian 1.1.2.10 import harpoon.Util.ArrayIterator;
10 cananian 1.6 import net.cscott.jutil.CombineIterator;
11 cananian 1.6 import net.cscott.jutil.FilterIterator;
12 cananian 1.6 import net.cscott.jutil.UnmodifiableIterator;
13 cananian 1.1.2.1
14 cananian 1.1.2.10 import java.util.AbstractCollection;
15 cananian 1.1.2.10 import java.util.AbstractSet;
16 cananian 1.5 import java.util.ArrayList;
17 cananian 1.1.2.6 import java.util.Arrays;
18 cananian 1.1.2.1 import java.util.Collection;
19 cananian 1.5 import java.util.Collections;
20 cananian 1.1.2.10 import java.util.HashSet;
21 cananian 1.1.2.6 import java.util.Iterator;
22 cananian 1.5 import java.util.List;
23 cananian 1.1.2.10 import java.util.NoSuchElementException;
24 cananian 1.1.2.10 import java.util.Set;
25 cananian 1.1.2.10 import java.util.Stack;
26 cananian 1.1.2.1 /**
27 cananian 1.1.2.1 * <code>CFGrapher</code> provides a means to externally associate
28 cananian 1.1.2.1 * control-flow graph information with elements of an intermediate
29 cananian 1.1.2.1 * representation.
30 cananian 1.1.2.1 *
31 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
32 cananian 1.6 * @version $Id: CFGrapher.java,v 1.6 2004/02/08 01:55:20 cananian Exp $
33 cananian 1.1.2.7 * @see harpoon.IR.Properties.CFGraphable
34 cananian 1.1.2.1 */
35 cananian 1.2.2.1 public abstract class CFGrapher<HCE extends HCodeElement> {
36 cananian 1.1.2.8 /** Returns the first <code>HCodeElement</code>s to be executed; that is,
37 cananian 1.1.2.8 * the roots of the control-flow graph. */
38 cananian 1.2.2.1 public HCE[] getFirstElements(HCode<HCE> hcode) {
39 cananian 1.2.2.1 HCE[] r = hcode.elementArrayFactory().newArray(1);
40 cananian 1.1.2.8 r[0] = getFirstElement(hcode);
41 cananian 1.1.2.8 return r;
42 cananian 1.1.2.8 }
43 cananian 1.1.2.8 /** Returns the last <code>HCodeElement</code>s to be executed; that is,
44 cananian 1.1.2.8 * the leaves of the control-flow graph. */
45 cananian 1.2.2.1 public abstract HCE[] getLastElements(HCode<HCE> hcode);
46 cananian 1.1.2.8 /** This method is present for compatibility only.
47 cananian 1.1.2.8 * @deprecated Use getFirstElements() instead. */
48 cananian 1.2.2.1 public abstract HCE getFirstElement(HCode<HCE> hcode);
49 cananian 1.1.2.3
50 cananian 1.1.2.1 // JDK 1.2 collections API: [CSA, 15-Jun-1999]
51 cananian 1.5 /** Returns a <code>List</code> of all the edges to and from
52 cananian 1.1.2.1 * this <code>HCodeElement</code>. */
53 cananian 1.5 public List<HCodeEdge<HCE>> edgeC(HCE hc) {
54 cananian 1.2.2.1 Collection<HCodeEdge<HCE>> p = predC(hc), s = succC(hc);
55 cananian 1.5 List<HCodeEdge<HCE>> ea = new ArrayList(p.size()+s.size());
56 cananian 1.5 ea.addAll(p); ea.addAll(s);
57 cananian 1.5 return Collections.unmodifiableList(ea);
58 cananian 1.1.2.6 }
59 cananian 1.5 /** Returns a <code>List</code> of all the edges to
60 cananian 1.1.2.1 this <code>HCodeElement</code>.
61 cananian 1.1.2.1 Each <code>HCodeEdge</code> returned is guaranteed to return
62 cananian 1.1.2.1 <code>hc</code> in response to a call to <code>to()</code>;
63 cananian 1.1.2.1 the actual predecessor will be returned from
64 cananian 1.1.2.1 <code>from()</code>.
65 cananian 1.1.2.1 */
66 cananian 1.5 public abstract List<HCodeEdge<HCE>> predC(HCE hc);
67 cananian 1.5 /** Returns a <code>List</code> of all the edges from
68 cananian 1.1.2.1 this <code>HCodeElement</code>.
69 cananian 1.1.2.1 Each <code>HCodeEdge</code> returned is guaranteed to return
70 cananian 1.1.2.1 <code>hc</code> in response to a call to
71 cananian 1.1.2.1 <code>from()</code>; the actual successor to <code>this</code>
72 cananian 1.1.2.1 will be returned from <code>to()</code>.
73 cananian 1.1.2.1 */
74 cananian 1.5 public abstract List<HCodeEdge<HCE>> succC(HCE hc);
75 pnkfelix 1.1.2.9
76 pnkfelix 1.1.2.9 /** Returns a <code>Collection</code> of all the
77 pnkfelix 1.1.2.9 <code>HCodeElement</code>s preceeding <code>hc</code>.
78 pnkfelix 1.1.2.9 */
79 cananian 1.2.2.1 public Collection<HCE> predElemC(HCE hc) {
80 cananian 1.2.2.1 final Collection<HCodeEdge<HCE>> predEdges = this.predC(hc);
81 cananian 1.2.2.1 return new AbstractCollection<HCE>() {
82 pnkfelix 1.1.2.9 public int size() { return predEdges.size(); }
83 cananian 1.2.2.1 public Iterator<HCE> iterator() {
84 cananian 1.2.2.1 return new FilterIterator<HCodeEdge<HCE>,HCE>
85 pnkfelix 1.1.2.9 (predEdges.iterator(),
86 cananian 1.2.2.1 new FilterIterator.Filter<HCodeEdge<HCE>,HCE>() {
87 cananian 1.2.2.1 public HCE map(HCodeEdge<HCE> o)
88 cananian 1.2.2.1 { return o.from(); }
89 cananian 1.1.2.10 });
90 pnkfelix 1.1.2.9 }
91 pnkfelix 1.1.2.9 };
92 pnkfelix 1.1.2.9 }
93 pnkfelix 1.1.2.9
94 pnkfelix 1.1.2.9 /** Returns a <code>Collection</code> of all the
95 pnkfelix 1.1.2.9 <code>HCodeElement</code> succeeding <code>hc</code>.
96 pnkfelix 1.1.2.9 */
97 cananian 1.2.2.1 public Collection<HCE> succElemC(HCE hc) {
98 cananian 1.2.2.1 final Collection<HCodeEdge<HCE>> succEdges = this.succC(hc);
99 cananian 1.2.2.1 return new AbstractCollection<HCE>() {
100 pnkfelix 1.1.2.9 public int size() { return succEdges.size(); }
101 cananian 1.2.2.1 public Iterator<HCE> iterator() {
102 cananian 1.2.2.1 return new FilterIterator<HCodeEdge<HCE>,HCE>
103 pnkfelix 1.1.2.9 (succEdges.iterator(),
104 cananian 1.2.2.1 new FilterIterator.Filter<HCodeEdge<HCE>,HCE>() {
105 cananian 1.2.2.1 public HCE map(HCodeEdge<HCE> o)
106 cananian 1.2.2.1 { return o.to(); }
107 cananian 1.1.2.10 });
108 pnkfelix 1.1.2.9 }
109 pnkfelix 1.1.2.9 };
110 cananian 1.1.2.10 }
111 cananian 1.1.2.10
112 cananian 1.2.2.1 public Set<HCE> getElements(final HCode<HCE> code) {
113 cananian 1.2.2.1 return new AbstractSet<HCE>() {
114 cananian 1.1.2.10 public int size() {
115 cananian 1.1.2.10 int i=0;
116 cananian 1.2.2.1 for (Iterator<HCE> it=iterator(); it.hasNext(); it.next())
117 cananian 1.1.2.10 i++;
118 cananian 1.1.2.10 return i;
119 cananian 1.1.2.10 }
120 cananian 1.2.2.1 public Iterator<HCE> iterator() {
121 cananian 1.2.2.1 return new UnmodifiableIterator<HCE>() {
122 cananian 1.1.2.10 // implementation borrowed from IR/Quads/Code.
123 cananian 1.2.2.1 Set<HCE> visited = new HashSet<HCE>();
124 cananian 1.2.2.1 Stack<HCE> s = new Stack<HCE>();
125 cananian 1.1.2.10 { // initialize stack/set.
126 cananian 1.2.2.1 Iterator<HCE> it =
127 cananian 1.2.2.2 new ArrayIterator<HCE>(getFirstElements(code));
128 cananian 1.2.2.1 HCE[] leaves = getLastElements(code);
129 cananian 1.1.2.11 if (leaves!=null)
130 cananian 1.2.2.1 it = new CombineIterator<HCE>
131 cananian 1.2.2.1 (new ArrayIterator<HCE>(leaves), it);
132 cananian 1.1.2.10 while (it.hasNext()) {
133 cananian 1.2.2.1 HCE hce = it.next();
134 cananian 1.1.2.10 s.push(hce); visited.add(hce);
135 cananian 1.1.2.10 }
136 cananian 1.1.2.10 }
137 cananian 1.1.2.10 public boolean hasNext() { return !s.isEmpty(); }
138 cananian 1.2.2.1 public HCE next() {
139 cananian 1.1.2.10 if (s.empty()) throw new NoSuchElementException();
140 cananian 1.2.2.1 HCE hce = s.pop();
141 cananian 1.1.2.10 // push successors on stack before returning.
142 cananian 1.2.2.1 Iterator<HCE> it=succElemC(hce).iterator();
143 cananian 1.1.2.10 while (it.hasNext()) {
144 cananian 1.2.2.1 HCE nxt = it.next();
145 cananian 1.1.2.10 if (!visited.contains(nxt)) {
146 cananian 1.1.2.10 s.push(nxt); visited.add(nxt);
147 cananian 1.1.2.10 }
148 cananian 1.1.2.10 }
149 cananian 1.1.2.10 return hce;
150 cananian 1.1.2.10 }
151 cananian 1.1.2.10 };
152 cananian 1.1.2.10 }
153 cananian 1.1.2.10 };
154 pnkfelix 1.1.2.9 }
155 pnkfelix 1.1.2.9
156 cananian 1.1.2.8 /** Returns an edge-reversed grapher based on this one.
157 cananian 1.1.2.8 * Certain algorithms operate more naturally on this
158 cananian 1.1.2.8 * representation --- for example, the difference between a
159 cananian 1.1.2.8 * dominator tree and a post-dominator tree is now simply
160 cananian 1.1.2.8 * whether you use the <code>grapher</code> or
161 cananian 1.1.2.8 * <code>grapher.edgeReversed()</code>. */
162 cananian 1.2.2.1 public CFGrapher<HCE> edgeReversed() {
163 cananian 1.2.2.1 if (reversed==null)
164 cananian 1.2.2.1 reversed=new ReverseGrapher<HCE>(this);
165 cananian 1.2.2.1 return reversed;
166 cananian 1.2.2.1 }
167 cananian 1.2.2.1 private CFGrapher<HCE> reversed = null;
168 cananian 1.2.2.1 private static class ReverseGrapher<HCE extends HCodeElement>
169 cananian 1.2.2.1 extends SerializableGrapher<HCE> {
170 cananian 1.2.2.1 private final CFGrapher<HCE> grapher;
171 cananian 1.2.2.1 ReverseGrapher(CFGrapher<HCE> grapher) { this.grapher = grapher; }
172 cananian 1.2.2.1 public HCE[] getFirstElements(HCode<HCE> hcode) {
173 cananian 1.1.2.8 return grapher.getLastElements(hcode);
174 cananian 1.1.2.8 }
175 cananian 1.2.2.1 public HCE getFirstElement(HCode<HCE> hcode) {
176 cananian 1.2.2.1 HCE[] r = getFirstElements(hcode);
177 cananian 1.1.2.8 if (r.length!=1)
178 cananian 1.1.2.8 throw new Error("Deprecated use of getFirstElement() not "+
179 cananian 1.1.2.8 "supported with edge-reversed graphers.");
180 cananian 1.1.2.8 return r[0];
181 cananian 1.1.2.8 }
182 cananian 1.2.2.1 public HCE[] getLastElements(HCode<HCE> hcode) {
183 cananian 1.1.2.8 return grapher.getFirstElements(hcode);
184 cananian 1.1.2.8 }
185 cananian 1.5 public List<HCodeEdge<HCE>> predC(HCE hc) {
186 cananian 1.1.2.8 return reverseEdges(grapher.succC(hc));
187 cananian 1.1.2.8 }
188 cananian 1.5 public List<HCodeEdge<HCE>> succC(HCE hc) {
189 cananian 1.1.2.8 return reverseEdges(grapher.predC(hc));
190 cananian 1.1.2.8 }
191 cananian 1.2.2.1 private static <HCE extends HCodeElement>
192 cananian 1.5 List<HCodeEdge<HCE>> reverseEdges(List<HCodeEdge<HCE>> edges) {
193 cananian 1.5 List<HCodeEdge<HCE>> ea =
194 cananian 1.5 new ArrayList<HCodeEdge<HCE>>(edges.size());
195 cananian 1.5 for (Iterator<HCodeEdge<HCE>> it=edges.iterator(); it.hasNext(); ){
196 cananian 1.2.2.1 final HCodeEdge<HCE> e = it.next();
197 cananian 1.5 ea.add(new HCodeEdge<HCE>() {
198 cananian 1.2.2.1 public HCE from() { return e.to(); }
199 cananian 1.2.2.1 public HCE to() { return e.from(); }
200 cananian 1.5 });
201 cananian 1.1.2.8 }
202 cananian 1.5 return Collections.unmodifiableList(ea);
203 cananian 1.1.2.8 }
204 cananian 1.2.2.1 public CFGrapher<HCE> edgeReversed() { return grapher; }
205 cananian 1.1.2.8 }
206 cananian 1.1.2.8
207 cananian 1.1.2.1 /** Default <code>CFGrapher</code> for <code>HCodeElement</code>s
208 cananian 1.1.2.1 * which implement <code>CFGraphable</code>. Does nothing
209 cananian 1.1.2.1 * but cast the supplied <code>HCodeElement</code> to a
210 cananian 1.1.2.1 * <code>CFGraphable</code> and invoke the appropriate
211 cananian 1.1.2.1 * corresponding method in the <code>CFGraphable</code>
212 cananian 1.1.2.3 * interface. The root of the control flow graph is
213 cananian 1.1.2.3 * assumed to be whatever <code>HCode.getRootElement</code>
214 cananian 1.1.2.3 * returns.
215 cananian 1.1.2.1 * @see java.util.Comparator
216 cananian 1.1.2.1 * @see java.lang.Comparable
217 cananian 1.6 * @see net.cscott.jutil.Default.comparator
218 cananian 1.1.2.1 */
219 cananian 1.2.2.1 // XXX in theory, we could use a type system to enforce the
220 cananian 1.2.2.1 // constraint that DEFAULT is a CFGrapher that only works
221 cananian 1.2.2.1 // for HCodeElements which are CFGraphable. but the GJ
222 cananian 1.2.2.1 // type system's not powerful enough.
223 cananian 1.1.2.5 public static final CFGrapher DEFAULT = new SerializableGrapher() {
224 cananian 1.1.2.3 public HCodeElement getFirstElement(HCode hcode) {
225 cananian 1.1.2.3 return hcode.getRootElement();
226 cananian 1.1.2.8 }
227 cananian 1.1.2.8 public HCodeElement[] getLastElements(HCode hcode) {
228 cananian 1.1.2.8 return hcode.getLeafElements();
229 cananian 1.1.2.3 }
230 cananian 1.1.2.1 public HCodeEdge[] edges(HCodeElement hc) {
231 cananian 1.1.2.1 return ((CFGraphable)hc).edges();
232 cananian 1.1.2.1 }
233 cananian 1.1.2.1 public HCodeEdge[] pred(HCodeElement hc) {
234 cananian 1.1.2.1 return ((CFGraphable)hc).pred();
235 cananian 1.1.2.1 }
236 cananian 1.1.2.1 public HCodeEdge[] succ(HCodeElement hc) {
237 cananian 1.1.2.1 return ((CFGraphable)hc).succ();
238 cananian 1.1.2.1 }
239 cananian 1.5 public List edgeC(HCodeElement hc) {
240 cananian 1.1.2.1 return ((CFGraphable)hc).edgeC();
241 cananian 1.1.2.1 }
242 cananian 1.5 public List predC(HCodeElement hc) {
243 cananian 1.1.2.1 return ((CFGraphable)hc).predC();
244 cananian 1.1.2.1 }
245 cananian 1.5 public List succC(HCodeElement hc) {
246 cananian 1.1.2.1 return ((CFGraphable)hc).succC();
247 cananian 1.1.2.1 }
248 cananian 1.1.2.1 };
249 cananian 1.2.2.1 private static abstract class SerializableGrapher<HCE extends HCodeElement>
250 cananian 1.2.2.1 extends CFGrapher<HCE>
251 cananian 1.1.2.5 implements java.io.Serializable { }
252 cananian 1.2 }