1 pnkfelix 1.1.2.1 // BasicBlock.java, created Wed Mar 10 9:00:53 1999 by jwhaley
2 cananian 1.1.2.46 // Copyright (C) 1998 John Whaley <jwhaley@alum.mit.edu>
3 pnkfelix 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.1 package harpoon.Analysis;
5 pnkfelix 1.1.2.1
6 pnkfelix 1.1.2.1 import harpoon.Util.Util;
7 cananian 1.8 import net.cscott.jutil.IteratorEnumerator;
8 cananian 1.1.2.48 import harpoon.Util.Collections.WorkSet;
9 cananian 1.8 import net.cscott.jutil.LinearSet;
10 cananian 1.8 import net.cscott.jutil.UnmodifiableListIterator;
11 pnkfelix 1.1.2.1 import harpoon.Util.Worklist;
12 pnkfelix 1.1.2.4 import harpoon.ClassFile.HCodeElement;
13 pnkfelix 1.1.2.7 import harpoon.ClassFile.HCodeEdge;
14 cananian 1.1.2.23 import harpoon.ClassFile.HCode;
15 pnkfelix 1.1.2.9 import harpoon.IR.Properties.CFGrapher;
16 pnkfelix 1.1.2.1
17 pnkfelix 1.1.2.1 import harpoon.Analysis.DataFlow.ReversePostOrderEnumerator;
18 pnkfelix 1.1.2.1
19 pnkfelix 1.1.2.1 import java.util.Map;
20 pnkfelix 1.1.2.4 import java.util.HashMap;
21 pnkfelix 1.1.2.1 import java.util.Hashtable;
22 pnkfelix 1.1.2.1 import java.util.Enumeration;
23 pnkfelix 1.1.2.14 import java.util.List;
24 pnkfelix 1.1.2.35 import java.util.LinkedList;
25 pnkfelix 1.1.2.1 import java.util.ListIterator;
26 pnkfelix 1.1.2.3 import java.util.ArrayList;
27 pnkfelix 1.1.2.1 import java.util.NoSuchElementException;
28 pnkfelix 1.1.2.1 import java.util.Iterator;
29 pnkfelix 1.1.2.1 import java.util.Set;
30 pnkfelix 1.1.2.1 import java.util.HashSet;
31 pnkfelix 1.1.2.1 import java.util.Collections;
32 pnkfelix 1.1.2.26 import java.util.Collection;
33 pnkfelix 1.1.2.1
34 pnkfelix 1.1.2.1 /**
35 pnkfelix 1.1.2.27 BasicBlock collects a sequence of operations. It is designed to
36 pnkfelix 1.1.2.1 abstract away specific operation and allow the compiler to focus on
37 pnkfelix 1.1.2.1 control flow at a higher level. (It also allows for some analysis
38 pnkfelix 1.1.2.1 within the block to operate more efficiently by taking advantage of
39 pnkfelix 1.1.2.1 the fact that the elements of a BasicBlock have a total ordering of
40 pnkfelix 1.1.2.1 execution).
41 pnkfelix 1.1.2.27
42 pnkfelix 1.1.2.27 <P> Most BasicBlocks are a part of a larger piece of code, and thus
43 pnkfelix 1.1.2.27 a collection of BasicBlocks form a Control Flow Graph (where the
44 pnkfelix 1.1.2.27 nodes of the graph are the blocks and the directed edges of the
45 pnkfelix 1.1.2.27 graph indicate when one block is succeeded by another block).
46 pnkfelix 1.1.2.19
47 pnkfelix 1.1.2.19 <P> Make sure to look at <code>BasicBlock.Factory</code>, since it
48 pnkfelix 1.1.2.19 acts as the central core for creating and keeping track of the
49 pnkfelix 1.1.2.19 <code>BasicBlock</code>s for a given <code>HCode</code>.
50 pnkfelix 1.1.2.1
51 pnkfelix 1.1.2.19 <P> <B>NOTE:</B> right now <code>BasicBlock</code> only guarantees
52 pnkfelix 1.1.2.39 that it preserves the <i>Maximal Basic Block</i> property (where each
53 pnkfelix 1.1.2.39 block is the longest sequence of instructions such that only the
54 pnkfelix 1.1.2.39 first instruction may have more than one entry and only the last
55 pnkfelix 1.1.2.39 instruction may have more than one exit) if the graph of operations
56 pnkfelix 1.1.2.39 is not modified while the basic block is in use. For that matter,
57 pnkfelix 1.1.2.39 some methods of BasicBlock may implicitly rely on the intermediate
58 pnkfelix 1.1.2.39 representation not changing while the blocks are in use. However,
59 pnkfelix 1.1.2.39 most <b>but not all</b> Intermediate Representations in the Flex
60 pnkfelix 1.1.2.39 Compiler are immutable. Therefore compilation passes modifying the
61 pnkfelix 1.1.2.39 intermediate representation must reconstruct the BasicBlocks for
62 pnkfelix 1.1.2.39 that intermediate representation if they wish to perform a second
63 pnkfelix 1.1.2.39 analysis pass.
64 pnkfelix 1.1.2.1 *
65 cananian 1.1.2.46 * @author John Whaley <jwhaley@alum.mit.edu>
66 cananian 1.1.2.46 * @author Felix S. Klock II <pnkfelix@mit.edu>
67 cananian 1.8 * @version $Id: BasicBlock.java,v 1.8 2004/02/08 01:49:03 cananian Exp $ */
68 cananian 1.3.2.2 public class BasicBlock<HCE extends HCodeElement>
69 cananian 1.3.2.2 implements BasicBlockInterf<HCE,BasicBlock<HCE>>, java.io.Serializable {
70 pnkfelix 1.1.2.1
71 pnkfelix 1.1.2.14 static final boolean DEBUG = false;
72 pnkfelix 1.1.2.30 static final boolean TIME = false;
73 pnkfelix 1.1.2.31
74 pnkfelix 1.1.2.34 static boolean CHECK_INSTRS = false;
75 pnkfelix 1.1.2.1
76 cananian 1.3.2.2 private HCE first;
77 cananian 1.3.2.2 private HCE last;
78 pnkfelix 1.1.2.17
79 pnkfelix 1.1.2.27 // BasicBlocks preceding and succeeding this block (we store the
80 pnkfelix 1.1.2.27 // CFG implicityly in the basic block objects; if necessary this
81 pnkfelix 1.1.2.27 // information can be migrated to BasicBlock.Factory and
82 pnkfelix 1.1.2.27 // maintained there)
83 cananian 1.3.2.2 private Set<BasicBlock<HCE>> pred_bb;
84 cananian 1.3.2.2 private Set<BasicBlock<HCE>> succ_bb;
85 pnkfelix 1.1.2.1
86 pnkfelix 1.1.2.27 // unique id number for this basic block; used only for BasicBlock.toString()
87 pnkfelix 1.1.2.14 private int num;
88 pnkfelix 1.1.2.14
89 pnkfelix 1.1.2.14 // number of statements in this block
90 pnkfelix 1.1.2.14 private int size;
91 pnkfelix 1.1.2.1
92 pnkfelix 1.1.2.17 // factory that generated this block
93 cananian 1.3.2.2 private Factory<HCE> factory;
94 pnkfelix 1.1.2.4
95 pnkfelix 1.1.2.27 /** Returns the first <code>HCodeElement</code> in the sequence.
96 pnkfelix 1.1.2.27 @deprecated Use the standard List view provided by statements() instead
97 pnkfelix 1.1.2.27 @see BasicBlock#statements
98 pnkfelix 1.1.2.27 */
99 cananian 1.3.2.2 public HCE getFirst() { return first; }
100 pnkfelix 1.1.2.27
101 pnkfelix 1.1.2.27 /** Returns the last <code>HCodeElement</code> in the sequence.
102 pnkfelix 1.1.2.27 @deprecated Use the standard List view provided by statements() instead
103 pnkfelix 1.1.2.27 @see BasicBlock#statements
104 pnkfelix 1.1.2.27 */
105 cananian 1.3.2.2 public HCE getLast() { return last; }
106 pnkfelix 1.1.2.1
107 pnkfelix 1.1.2.27 /** Adds <code>bb</code> to the set of predecessor basic blocks
108 pnkfelix 1.1.2.27 for <code>this</code>. Meant to be used during construction.
109 pnkfelix 1.1.2.27 FSK: probably should take this out; it adds little to the
110 pnkfelix 1.1.2.27 class
111 pnkfelix 1.1.2.27 */
112 cananian 1.3.2.2 private void addPredecessor(BasicBlock<HCE> bb) { pred_bb.add(bb); }
113 pnkfelix 1.1.2.27
114 pnkfelix 1.1.2.27 /** Adds <code>bb</code> to the set of successor basic blocks for
115 pnkfelix 1.1.2.27 <code>this</code>. Meant to be used during construction.
116 pnkfelix 1.1.2.27 FSK: probably should take this out; it adds little to the
117 pnkfelix 1.1.2.27 class
118 pnkfelix 1.1.2.27 */
119 cananian 1.3.2.2 private void addSuccessor(BasicBlock<HCE> bb) { succ_bb.add(bb); }
120 pnkfelix 1.1.2.1
121 pnkfelix 1.1.2.27 /** Returns the number of basic blocks in the predecessor set for
122 pnkfelix 1.1.2.27 <code>this</code>.
123 pnkfelix 1.1.2.27 @deprecated Use prevSet() instead
124 pnkfelix 1.1.2.27 @see BasicBlock#prevSet
125 pnkfelix 1.1.2.27 */
126 pnkfelix 1.1.2.1 public int prevLength() { return pred_bb.size(); }
127 pnkfelix 1.1.2.27
128 pnkfelix 1.1.2.27 /** Returns the number of basic blocks in the successor set for
129 pnkfelix 1.1.2.27 <code>this</code>.
130 pnkfelix 1.1.2.27 @deprecated Use nextSet() instead
131 pnkfelix 1.1.2.27 @see BasicBlock#nextSet
132 pnkfelix 1.1.2.27 */
133 pnkfelix 1.1.2.1 public int nextLength() { return succ_bb.size(); }
134 pnkfelix 1.1.2.27
135 pnkfelix 1.1.2.27 /** Returns an Enumeration that iterates over the predecessors for
136 pnkfelix 1.1.2.27 <code>this</code>.
137 pnkfelix 1.1.2.27 @deprecated Use prevSet() instead
138 pnkfelix 1.1.2.27 @see BasicBlock#prevSet
139 pnkfelix 1.1.2.27 */
140 cananian 1.3.2.2 public Enumeration<BasicBlock<HCE>> prev() { return new IteratorEnumerator<BasicBlock<HCE>>(pred_bb.iterator()); }
141 pnkfelix 1.1.2.27
142 pnkfelix 1.1.2.27 /** Returns an Enumeration that iterates over the successors for
143 pnkfelix 1.1.2.27 <code>this</code>.
144 pnkfelix 1.1.2.27 @deprecated Use nextSet() instead
145 pnkfelix 1.1.2.27 @see BasicBlock#prevSet
146 pnkfelix 1.1.2.27 */
147 cananian 1.3.2.2 public Enumeration<BasicBlock<HCE>> next() { return new IteratorEnumerator<BasicBlock<HCE>>(succ_bb.iterator()); }
148 salcianu 1.1.2.12
149 pnkfelix 1.1.2.14 /** Returns all the predecessors of <code>this</code>.
150 pnkfelix 1.1.2.14 <BR> <B>effects:</B> returns a <code>Set</code> of
151 pnkfelix 1.1.2.14 <code>BasicBlock</code>s which precede
152 pnkfelix 1.1.2.14 <code>this</code>.
153 pnkfelix 1.1.2.14 */
154 cananian 1.3.2.2 public Set<BasicBlock<HCE>> prevSet() {
155 pnkfelix 1.1.2.14 return Collections.unmodifiableSet(pred_bb);
156 pnkfelix 1.1.2.14 }
157 pnkfelix 1.1.2.1
158 pnkfelix 1.1.2.14 /** Returns all the successors of <code>this</code>.
159 pnkfelix 1.1.2.14 <BR> <B>effects:</B> returns a <code>Set</code> of
160 pnkfelix 1.1.2.14 <code>BasicBlock</code>s which succeed
161 pnkfelix 1.1.2.14 <code>this</code>.
162 pnkfelix 1.1.2.14 */
163 cananian 1.3.2.2 public Set<BasicBlock<HCE>> nextSet() {
164 pnkfelix 1.1.2.14 return Collections.unmodifiableSet(succ_bb);
165 pnkfelix 1.1.2.1 }
166 pnkfelix 1.1.2.1
167 pnkfelix 1.1.2.14 /** Returns an unmodifiable <code>List</code> for the
168 pnkfelix 1.1.2.14 <code>HCodeElement</code>s within <code>this</code>.
169 pnkfelix 1.1.2.27
170 pnkfelix 1.1.2.14 <BR> <B>effects:</B> Generates a new <code>List</code> of
171 pnkfelix 1.1.2.14 <code>HCodeElement</code>s ordered according to the order
172 pnkfelix 1.1.2.14 mandated by the <code>CFGrapher</code> used in the call to
173 pnkfelix 1.1.2.14 <code>computeBasicBlocks</code> that generated
174 pnkfelix 1.1.2.14 <code>this</code>.
175 pnkfelix 1.1.2.2 */
176 cananian 1.3.2.2 public List<HCE> statements() {
177 pnkfelix 1.1.2.27
178 pnkfelix 1.1.2.27 // FSK: this is dumb; why not just return an empty list in
179 pnkfelix 1.1.2.27 // this case? I suspect this is an attempt to fail-fast, but
180 pnkfelix 1.1.2.27 // still...
181 cananian 1.3.2.1 assert size > 0 : "BasicBlock class breaks on empty BBs";
182 pnkfelix 1.1.2.27
183 cananian 1.3.2.2 return new java.util.AbstractSequentialList<HCE>() {
184 pnkfelix 1.1.2.14 public int size() { return size; }
185 cananian 1.3.2.2 public ListIterator<HCE> listIterator(int index) {
186 pnkfelix 1.1.2.14 // note that index *can* equal the size of the list,
187 pnkfelix 1.1.2.14 // in which case we start the iterator past the last
188 pnkfelix 1.1.2.14 // element of the list.
189 pnkfelix 1.1.2.14
190 pnkfelix 1.1.2.14 // check argument
191 pnkfelix 1.1.2.27 if (index < 0) {
192 pnkfelix 1.1.2.27 throw new IndexOutOfBoundsException(index +"< 0");
193 pnkfelix 1.1.2.27 } else if (index > size) {
194 pnkfelix 1.1.2.27 throw new IndexOutOfBoundsException(index+" > "+size);
195 pnkfelix 1.1.2.14 }
196 pnkfelix 1.1.2.14
197 pnkfelix 1.1.2.14 // iterate to correct starting point
198 cananian 1.3.2.2 HCE curr;
199 pnkfelix 1.1.2.15
200 pnkfelix 1.1.2.42 // FSK: put better code in here for choosing starting pt
201 pnkfelix 1.1.2.27 if (index < size) {
202 pnkfelix 1.1.2.27 curr = first;
203 pnkfelix 1.1.2.27 int bound = Math.min(index, size-1);
204 pnkfelix 1.1.2.27 for(int i=0; i < bound; i++) {
205 cananian 1.7 curr = factory.grapher.succC(curr).get(0).to();
206 pnkfelix 1.1.2.27 }
207 pnkfelix 1.1.2.27 } else {
208 pnkfelix 1.1.2.27 curr = last;
209 pnkfelix 1.1.2.14 }
210 pnkfelix 1.1.2.27
211 pnkfelix 1.1.2.14 // new final vars to be passed to ListIterator
212 cananian 1.3.2.2 final HCE fcurr = curr;
213 pnkfelix 1.1.2.16 final int fi = index;
214 pnkfelix 1.1.2.16
215 pnkfelix 1.1.2.16 if (false) System.out.println
216 pnkfelix 1.1.2.16 (" generating listIterator("+index+")"+
217 pnkfelix 1.1.2.16 " next: "+fcurr+
218 pnkfelix 1.1.2.16 " ind: "+fi);
219 pnkfelix 1.1.2.14
220 cananian 1.5 return new UnmodifiableListIterator<HCE>() {
221 pnkfelix 1.1.2.27 //elem for next() to return
222 cananian 1.3.2.2 HCE next = fcurr;
223 pnkfelix 1.1.2.27
224 pnkfelix 1.1.2.27 // where currently pointing?
225 pnkfelix 1.1.2.27 // Invariant: 0 <= ind /\ ind <= size
226 pnkfelix 1.1.2.27 int ind = fi;
227 pnkfelix 1.1.2.27
228 pnkfelix 1.1.2.29 // checks rep of `this' (for debugging)
229 pnkfelix 1.1.2.27 private void repOK() {
230 pnkfelix 1.1.2.27 repOK("");
231 pnkfelix 1.1.2.27 }
232 pnkfelix 1.1.2.27
233 pnkfelix 1.1.2.29 // checks rep of `this' (for debugging)
234 pnkfelix 1.1.2.27 private void repOK(String s) {
235 cananian 1.3.2.1 assert 0 <= ind : (s+" (0 <= ind), ind:"+ind);
236 cananian 1.3.2.1 assert ind <= size : (s+" (ind <= size), ind:"+ind+", size:"+size);
237 cananian 1.3.2.1 assert ((ind==0)?next==first:true) : (s+" (ind==0 => next==first), next:"+next+", first:"+first);
238 pnkfelix 1.1.2.27
239 cananian 1.3.2.1 assert ((ind==(size-1))?next==last:true) : (s+" (ind==(size-1) => next==last), next:"+next+", last:"+last);
240 pnkfelix 1.1.2.27
241 cananian 1.3.2.1 assert ((ind==size)?next==last:true) : (s+" (ind==size => next==last), next:"+next+", last:"+last);
242 pnkfelix 1.1.2.27 }
243 pnkfelix 1.1.2.14
244 pnkfelix 1.1.2.14 public boolean hasNext() {
245 pnkfelix 1.1.2.29 if (DEBUG) repOK();
246 pnkfelix 1.1.2.27 return ind != size;
247 pnkfelix 1.1.2.14 }
248 cananian 1.3.2.2 public HCE next() {
249 pnkfelix 1.1.2.29 if (DEBUG) repOK("beginning");
250 pnkfelix 1.1.2.27 if (ind == size) {
251 pnkfelix 1.1.2.14 throw new NoSuchElementException();
252 pnkfelix 1.1.2.6 }
253 pnkfelix 1.1.2.14 ind++;
254 cananian 1.3.2.2 HCE ret = next;
255 pnkfelix 1.1.2.14 if (ind != size) {
256 cananian 1.3.2.2 Collection<HCodeEdge<HCE>> succs = factory.grapher.succC(next);
257 cananian 1.3.2.1 assert succs.size() == 1 : (true)?" wrong succs:":
258 pnkfelix 1.1.2.47 next+" has wrong succs:" + succs
259 cananian 1.3.2.1 +" (ind:"+ind+", size:"+size+")";
260 cananian 1.3.2.2 next = succs.iterator().next().to();
261 pnkfelix 1.1.2.15
262 pnkfelix 1.1.2.15 } else {
263 pnkfelix 1.1.2.14 // keep 'next' the same, since previous()
264 pnkfelix 1.1.2.14 // needs to be able to return it
265 pnkfelix 1.1.2.6 }
266 pnkfelix 1.1.2.27
267 pnkfelix 1.1.2.29 if (DEBUG) repOK("end");
268 pnkfelix 1.1.2.14 return ret;
269 pnkfelix 1.1.2.14 }
270 pnkfelix 1.1.2.15
271 pnkfelix 1.1.2.15
272 pnkfelix 1.1.2.14 public boolean hasPrevious() {
273 pnkfelix 1.1.2.29 if (DEBUG) repOK();
274 pnkfelix 1.1.2.27 return ind > 0;
275 pnkfelix 1.1.2.27
276 pnkfelix 1.1.2.14 }
277 cananian 1.3.2.2 public HCE previous() {
278 pnkfelix 1.1.2.29 if (DEBUG) repOK();
279 pnkfelix 1.1.2.27
280 pnkfelix 1.1.2.27 if (ind <= 0) {
281 pnkfelix 1.1.2.14 throw new NoSuchElementException();
282 pnkfelix 1.1.2.14 }
283 pnkfelix 1.1.2.27
284 pnkfelix 1.1.2.27 // special case: if ind == size, then we just
285 pnkfelix 1.1.2.27 // return <next>
286 pnkfelix 1.1.2.14 if (ind != size) {
287 cananian 1.7 next = factory.grapher.predC(next).get(0).from();
288 pnkfelix 1.1.2.14 }
289 pnkfelix 1.1.2.14 ind--;
290 pnkfelix 1.1.2.27
291 pnkfelix 1.1.2.29 if (DEBUG) repOK();
292 pnkfelix 1.1.2.14 return next;
293 pnkfelix 1.1.2.14 }
294 pnkfelix 1.1.2.14 public int nextIndex() {
295 pnkfelix 1.1.2.29 if (DEBUG) repOK();
296 pnkfelix 1.1.2.14 return ind;
297 pnkfelix 1.1.2.14 }
298 pnkfelix 1.1.2.14 };
299 pnkfelix 1.1.2.1 }
300 pnkfelix 1.1.2.1 };
301 pnkfelix 1.1.2.1 }
302 pnkfelix 1.1.2.1
303 pnkfelix 1.1.2.27 /** Accept a visitor.
304 pnkfelix 1.1.2.27 FSK: is this really useful? John put this in with the thought
305 pnkfelix 1.1.2.27 that we'd have many different types of BasicBlocks, but I'm
306 pnkfelix 1.1.2.27 not sure about that actually being a useful set of subtypes
307 pnkfelix 1.1.2.27 */
308 salcianu 1.1.2.49 public void accept(BasicBlockInterfVisitor v) { v.visit(this); }
309 pnkfelix 1.1.2.1
310 pnkfelix 1.1.2.27 /** Constructs a new BasicBlock with <code>h</code> as its first
311 pnkfelix 1.1.2.27 element. Meant to be used only during construction.
312 pnkfelix 1.1.2.27 */
313 cananian 1.3.2.2 protected BasicBlock(HCE h, Factory f) {
314 cananian 1.3.2.1 assert h!=null;
315 pnkfelix 1.1.2.17 first = h;
316 pnkfelix 1.1.2.17 last = null; // note that this MUST be updated by 'f'
317 cananian 1.3.2.2 pred_bb = new HashSet<BasicBlock<HCE>>();
318 cananian 1.3.2.2 succ_bb = new HashSet<BasicBlock<HCE>>();
319 pnkfelix 1.1.2.15 size = 1;
320 pnkfelix 1.1.2.17 this.factory = f;
321 pnkfelix 1.1.2.17 num = factory.BBnum++;
322 pnkfelix 1.1.2.1 }
323 pnkfelix 1.1.2.1
324 pnkfelix 1.1.2.27 /** Constructs an edge from <code>from</code> to
325 pnkfelix 1.1.2.27 </code>to</code>.
326 pnkfelix 1.1.2.27 */
327 cananian 1.3.2.2 private static <HCE extends HCodeElement> void addEdge(BasicBlock<HCE> from, BasicBlock<HCE> to) {
328 pnkfelix 1.1.2.1 from.addSuccessor(to);
329 pnkfelix 1.1.2.1 to.addPredecessor(from);
330 pnkfelix 1.1.2.1 }
331 pnkfelix 1.1.2.1
332 pnkfelix 1.1.2.1 public String toString() {
333 pnkfelix 1.1.2.44 return "BB"+num+"{"+first+"}";
334 pnkfelix 1.1.2.1 }
335 pnkfelix 1.1.2.1
336 pnkfelix 1.1.2.27 /** Returns a String composed of the statements comprising
337 pnkfelix 1.1.2.27 <code>this</code>.
338 pnkfelix 1.1.2.27 */
339 pnkfelix 1.1.2.1 public String dumpElems() {
340 pnkfelix 1.1.2.37 List stms = statements();
341 pnkfelix 1.1.2.37 StringBuffer s = new StringBuffer(stms.size()*16);
342 pnkfelix 1.1.2.37 Iterator iter = stms.listIterator();
343 pnkfelix 1.1.2.1 while(iter.hasNext()) {
344 pnkfelix 1.1.2.1 s.append(iter.next() + "\n");
345 pnkfelix 1.1.2.1 }
346 pnkfelix 1.1.2.1 return s.toString();
347 pnkfelix 1.1.2.1 }
348 pnkfelix 1.1.2.1
349 pnkfelix 1.1.2.17 /** Factory structure for generating BasicBlock views of
350 pnkfelix 1.1.2.27 an <code>HCode</code>.
351 pnkfelix 1.1.2.17 */
352 cananian 1.3.2.2 public static class Factory<HCE extends HCodeElement>
353 cananian 1.3.2.2 implements BasicBlockFactoryInterf<HCE,BasicBlock<HCE>>,
354 cananian 1.3.2.2 java.io.Serializable {
355 salcianu 1.1.2.49
356 salcianu 1.1.2.25 // the underlying HCode
357 cananian 1.3.2.2 private final HCode<HCE> hcode;
358 salcianu 1.1.2.25
359 cananian 1.3.2.2 private final Map<HCE,BasicBlock<HCE>> hceToBB;
360 pnkfelix 1.1.2.19
361 cananian 1.3.2.2 private final CFGrapher<HCE> grapher;
362 cananian 1.3.2.2 private final BasicBlock<HCE> root;
363 cananian 1.3.2.2 private final Set<BasicBlock<HCE>> leaves;
364 cananian 1.3.2.2 private final Set<BasicBlock<HCE>> blocks;
365 pnkfelix 1.1.2.19
366 pnkfelix 1.1.2.17
367 pnkfelix 1.1.2.17 // tracks the current id number to assign to the next
368 pnkfelix 1.1.2.17 // generated basic block
369 pnkfelix 1.1.2.17 private int BBnum = 0;
370 pnkfelix 1.1.2.17
371 pnkfelix 1.1.2.17 /** Returns the root <code>BasicBlock</code>.
372 pnkfelix 1.1.2.17 <BR> <B>effects:</B> returns the <code>BasicBlock</code>
373 pnkfelix 1.1.2.17 that is at the start of the set of
374 pnkfelix 1.1.2.17 <code>HCodeElement</code>s being analyzed.
375 pnkfelix 1.1.2.17 */
376 cananian 1.3.2.2 public BasicBlock<HCE> getRoot() {
377 pnkfelix 1.1.2.17 return root;
378 pnkfelix 1.1.2.17 }
379 pnkfelix 1.1.2.17
380 salcianu 1.1.2.49 /** Does the same thing as <code>getRoot</code>.
381 salcianu 1.1.2.49 Work around Java's weak typing system. */
382 cananian 1.3.2.2 public BasicBlock<HCE> getRootBBInterf() {
383 salcianu 1.1.2.49 return getRoot();
384 salcianu 1.1.2.49 }
385 salcianu 1.1.2.49
386 pnkfelix 1.1.2.17 /** Returns the leaf <code>BasicBlock</code>s.
387 pnkfelix 1.1.2.17 <BR> <B>effects:</B> returns a <code>Set</code> of
388 pnkfelix 1.1.2.17 <code>BasicBlock</code>s that are at the ends of the
389 pnkfelix 1.1.2.17 <code>HCodeElement</code>s being analyzed.
390 pnkfelix 1.1.2.17 */
391 cananian 1.3.2.2 public Set<BasicBlock<HCE>> getLeaves() {
392 pnkfelix 1.1.2.19 return leaves;
393 pnkfelix 1.1.2.19 }
394 pnkfelix 1.1.2.19
395 salcianu 1.1.2.49 /** Does the same thing as <code>getLeaves</code>.
396 salcianu 1.1.2.49 Work around Java's weak typing system. */
397 cananian 1.3.2.2 public Set<BasicBlock<HCE>> getLeavesBBInterf() {
398 salcianu 1.1.2.49 return getLeaves();
399 salcianu 1.1.2.49 }
400 salcianu 1.1.2.49
401 salcianu 1.1.2.25 /** Returns the <code>HCode</code> that <code>this</code> factory
402 salcianu 1.1.2.25 produces basic blocks of. */
403 cananian 1.3.2.2 public HCode<HCE> getHCode(){
404 salcianu 1.1.2.25 return hcode;
405 salcianu 1.1.2.25 }
406 pnkfelix 1.1.2.19
407 pnkfelix 1.1.2.19 /** Returns the <code>BasicBlock</code>s constructed by
408 pnkfelix 1.1.2.19 <code>this</code>.
409 pnkfelix 1.1.2.19 */
410 cananian 1.3.2.2 public Set<BasicBlock<HCE>> blockSet() {
411 pnkfelix 1.1.2.19 return blocks;
412 pnkfelix 1.1.2.19 }
413 pnkfelix 1.1.2.19
414 cananian 1.1.2.22 /** Generates an <code>Iterator</code> that traverses over all
415 cananian 1.1.2.22 of the blocks generated by this <code>BasicBlock.Factory</code>.
416 cananian 1.1.2.22 */
417 cananian 1.3.2.2 public Iterator<BasicBlock<HCE>> blocksIterator() {
418 pnkfelix 1.1.2.35 return postorderBlocksIter();
419 cananian 1.1.2.22 }
420 cananian 1.1.2.22
421 pnkfelix 1.1.2.35 /** Generates an <code>Iterator</code> that traverses over all
422 pnkfelix 1.1.2.35 of the blocks generated by this
423 pnkfelix 1.1.2.44 <code>BasicBlock.Factory</code> in Preorder (root first,
424 pnkfelix 1.1.2.44 then subtrees).
425 pnkfelix 1.1.2.35 */
426 cananian 1.3.2.2 public Iterator<BasicBlock<HCE>> preorderBlocksIter() {
427 cananian 1.3.2.2 LinkedList<Iterator<BasicBlock<HCE>>> iters =
428 cananian 1.3.2.2 new LinkedList<Iterator<BasicBlock<HCE>>>();
429 cananian 1.3.2.2 LinkedList<BasicBlock<HCE>> bbs=new LinkedList<BasicBlock<HCE>>();
430 cananian 1.3.2.2 LinkedList<BasicBlock<HCE>> order=new LinkedList<BasicBlock<HCE>>();
431 cananian 1.3.2.2 Set<BasicBlock<HCE>> done = new HashSet<BasicBlock<HCE>>();
432 cananian 1.3.2.2 BasicBlock<HCE> start = getRoot();
433 pnkfelix 1.1.2.36 done.add(start);
434 pnkfelix 1.1.2.36 bbs.addLast(start);
435 pnkfelix 1.1.2.36 iters.addLast(start.nextSet().iterator());
436 pnkfelix 1.1.2.36 while(!bbs.isEmpty()) {
437 cananian 1.3.2.1 assert bbs.size() == iters.size();
438 cananian 1.3.2.2 for (Iterator<BasicBlock<HCE>> i = iters.removeLast();
439 pnkfelix 1.1.2.36 i.hasNext(); ) {
440 cananian 1.3.2.2 BasicBlock<HCE> bb2 = i.next();
441 pnkfelix 1.1.2.36 if (!done.contains(bb2)) {
442 pnkfelix 1.1.2.36 done.add(bb2);
443 pnkfelix 1.1.2.36 bbs.addFirst(bb2);
444 pnkfelix 1.1.2.36 iters.addLast(i);
445 pnkfelix 1.1.2.36 i = bb2.nextSet().iterator();
446 pnkfelix 1.1.2.36 }
447 pnkfelix 1.1.2.36 }
448 pnkfelix 1.1.2.36
449 pnkfelix 1.1.2.36 // reverses order
450 pnkfelix 1.1.2.36 order.addLast(bbs.removeLast());
451 pnkfelix 1.1.2.36 }
452 pnkfelix 1.1.2.36
453 pnkfelix 1.1.2.36 return order.iterator();
454 pnkfelix 1.1.2.35 }
455 pnkfelix 1.1.2.35
456 pnkfelix 1.1.2.35 /** Generates an <code>Iterator</code> that traverses over all
457 pnkfelix 1.1.2.35 of the blocks generated by this
458 pnkfelix 1.1.2.44 <code>BasicBlock.Factory</code> in Postorder (subtrees
459 pnkfelix 1.1.2.44 first, then root).
460 pnkfelix 1.1.2.35 */
461 cananian 1.3.2.2 public Iterator<BasicBlock<HCE>> postorderBlocksIter() {
462 cananian 1.3.2.2 LinkedList<Iterator<BasicBlock<HCE>>> iters =
463 cananian 1.3.2.2 new LinkedList<Iterator<BasicBlock<HCE>>>();
464 cananian 1.3.2.2 LinkedList<BasicBlock<HCE>> bbs=new LinkedList<BasicBlock<HCE>>();
465 cananian 1.3.2.2 LinkedList<BasicBlock<HCE>> order=new LinkedList<BasicBlock<HCE>>();
466 cananian 1.3.2.2 Set<BasicBlock<HCE>> done = new HashSet<BasicBlock<HCE>>();
467 cananian 1.3.2.2 BasicBlock<HCE> start = getRoot();
468 pnkfelix 1.1.2.35 done.add(start);
469 pnkfelix 1.1.2.36 bbs.addLast(start);
470 pnkfelix 1.1.2.36 iters.addLast(start.nextSet().iterator());
471 pnkfelix 1.1.2.35 while(!bbs.isEmpty()) {
472 cananian 1.3.2.1 assert bbs.size() == iters.size();
473 cananian 1.3.2.2 for (Iterator<BasicBlock<HCE>> i = iters.removeLast();
474 pnkfelix 1.1.2.35 i.hasNext(); ) {
475 cananian 1.3.2.2 BasicBlock<HCE> bb2 = i.next();
476 pnkfelix 1.1.2.35 if (!done.contains(bb2)) {
477 pnkfelix 1.1.2.35 done.add(bb2);
478 pnkfelix 1.1.2.36 bbs.addLast(bb2);
479 pnkfelix 1.1.2.36 iters.addLast(i);
480 pnkfelix 1.1.2.35 i = bb2.nextSet().iterator();
481 pnkfelix 1.1.2.35 }
482 pnkfelix 1.1.2.35 }
483 pnkfelix 1.1.2.36
484 pnkfelix 1.1.2.36 // reverses order
485 pnkfelix 1.1.2.35 order.addLast(bbs.removeLast());
486 pnkfelix 1.1.2.35 }
487 pnkfelix 1.1.2.35
488 pnkfelix 1.1.2.35 return order.iterator();
489 pnkfelix 1.1.2.35 }
490 pnkfelix 1.1.2.35
491 pnkfelix 1.1.2.19 /** Returns the <code>BasicBlock</code> containing
492 pnkfelix 1.1.2.19 <code>hce</code>.
493 pnkfelix 1.1.2.41 <BR> <B>requires:</B> hce is present in the code for
494 pnkfelix 1.1.2.41 <code>this</code>.
495 pnkfelix 1.1.2.43 <BR> <B>effects:</B> returns the BasicBlock that contains
496 pnkfelix 1.1.2.43 <code>hce</code>, or <code>null</code> if
497 pnkfelix 1.1.2.43 <code>hce</code> is unreachable.
498 pnkfelix 1.1.2.19 */
499 cananian 1.3.2.2 public BasicBlock<HCE> getBlock(HCE hce) {
500 cananian 1.3.2.2 return hceToBB.get(hce);
501 salcianu 1.1.2.49 }
502 salcianu 1.1.2.49
503 salcianu 1.1.2.49 /** Does the same thing as <code>getBlock</code>.
504 salcianu 1.1.2.49 Work around Java's weak typing system. */
505 cananian 1.3.2.2 public BasicBlock<HCE> getBBInterf(HCE hce) {
506 salcianu 1.1.2.49 return getBlock(hce);
507 pnkfelix 1.1.2.40 }
508 pnkfelix 1.1.2.40
509 pnkfelix 1.1.2.40 /** Constructs a <code>BasicBlock.Factory</code> using the
510 pnkfelix 1.1.2.40 implicit control flow provided by <code>code</code>.
511 pnkfelix 1.1.2.40 <BR> <B>requires:</B> elements of <code>code</code>
512 pnkfelix 1.1.2.40 implement <code>CFGraphable</code>.
513 pnkfelix 1.1.2.40 <BR> <B>effects:</B> constructs a
514 pnkfelix 1.1.2.40 <code>BasicBlock.Factory</code> using
515 pnkfelix 1.1.2.40 <code>this(code, CFGrapher.DEFAULT);</code>
516 pnkfelix 1.1.2.40 */
517 cananian 1.3.2.2 public Factory(HCode<HCE> code) {
518 cananian 1.8 this(code, (CFGrapher<HCE>) CFGrapher.DEFAULT);
519 pnkfelix 1.1.2.17 }
520 pnkfelix 1.1.2.17
521 pnkfelix 1.1.2.17 /** Constructs a <code>BasicBlock.Factory</code> and generates
522 pnkfelix 1.1.2.17 <code>BasicBlock</code>s for a given <code>HCode</code>.
523 pnkfelix 1.1.2.17 <BR> <B>requires:</B>
524 cananian 1.1.2.23 <code>grapher.getFirstElement(hcode)</code>
525 cananian 1.1.2.23 is an appropriate entry point for a
526 cananian 1.1.2.23 basic block.
527 pnkfelix 1.1.2.17 <BR> <B>effects:</B> Creates a set of
528 pnkfelix 1.1.2.17 <code>BasicBlock</code>s corresponding to the blocks
529 cananian 1.1.2.23 implicitly contained in
530 cananian 1.1.2.23 <code>grapher.getFirstElement(hcode)</code> and the
531 cananian 1.1.2.23 <code>HCodeElement</code> objects that this
532 cananian 1.1.2.23 points to, and returns the
533 cananian 1.1.2.23 <code>BasicBlock</code> that
534 cananian 1.1.2.23 <code>grapher.getFirstElement(hcode)</code> is an
535 pnkfelix 1.1.2.17 instruction in. The <code>BasicBlock</code> returned
536 pnkfelix 1.1.2.17 is considered to be the root (entry-point) of the set
537 pnkfelix 1.1.2.17 of <code>BasicBlock</code>s created.
538 pnkfelix 1.1.2.17 */
539 cananian 1.3.2.2 public Factory(HCode<HCE> hcode, final CFGrapher<HCE> grapher) {
540 pnkfelix 1.1.2.30 if (TIME) System.out.print("bldBB");
541 pnkfelix 1.1.2.30
542 pnkfelix 1.1.2.17 // maps HCodeElement 'e' -> BasicBlock 'b' starting with 'e'
543 cananian 1.3.2.2 Map<HCE,BasicBlock<HCE>> h = new HashMap<HCE,BasicBlock<HCE>>();
544 pnkfelix 1.1.2.17 // stores BasicBlocks to be processed
545 cananian 1.3.2.2 Worklist<BasicBlock<HCE>> w = new WorkSet<BasicBlock<HCE>>();
546 pnkfelix 1.1.2.17
547 cananian 1.3.2.2 HCE head = grapher.getFirstElement(hcode);
548 cananian 1.1.2.23 this.grapher = grapher;
549 salcianu 1.1.2.25 this.hcode = hcode;
550 pnkfelix 1.1.2.17
551 pnkfelix 1.1.2.19 // modifable util classes for construction use only
552 cananian 1.3.2.2 Set<BasicBlock<HCE>> myLeaves = new HashSet<BasicBlock<HCE>>();
553 cananian 1.3.2.2 Map<HCE,BasicBlock<HCE>> myHceToBB =
554 cananian 1.3.2.2 new HashMap<HCE,BasicBlock<HCE>>();
555 pnkfelix 1.1.2.19
556 cananian 1.3.2.2 BasicBlock<HCE> first = new BasicBlock<HCE>(head, this);
557 pnkfelix 1.1.2.17 h.put(head, first);
558 pnkfelix 1.1.2.19 myHceToBB.put(head, first);
559 pnkfelix 1.1.2.17 w.push(first);
560 pnkfelix 1.1.2.17
561 pnkfelix 1.1.2.17 root = first;
562 pnkfelix 1.1.2.19
563 pnkfelix 1.1.2.17 while(!w.isEmpty()) {
564 cananian 1.3.2.2 BasicBlock<HCE> current = w.pull();
565 pnkfelix 1.1.2.17
566 pnkfelix 1.1.2.17 // 'last' is our guess on which elem will be the last;
567 pnkfelix 1.1.2.17 // thus we start with the most conservative guess
568 cananian 1.3.2.2 HCE last = current.getFirst();
569 pnkfelix 1.1.2.17 boolean foundEnd = false;
570 pnkfelix 1.1.2.17 while(!foundEnd) {
571 cananian 1.1.2.23 int n = grapher.succC(last).size();
572 pnkfelix 1.1.2.17 if (n == 0) {
573 pnkfelix 1.1.2.17 if(DEBUG) System.out.println("found end: "+last);
574 pnkfelix 1.1.2.17
575 pnkfelix 1.1.2.17 foundEnd = true;
576 pnkfelix 1.1.2.19 myLeaves.add(current);
577 pnkfelix 1.1.2.17
578 pnkfelix 1.1.2.17 } else if (n > 1) { // control flow split
579 pnkfelix 1.1.2.17 if(DEBUG) System.out.println("found split: "+last);
580 pnkfelix 1.1.2.17
581 pnkfelix 1.1.2.17 for (int i=0; i<n; i++) {
582 cananian 1.7 HCE e_n = grapher.succC(last).get(i).to();
583 cananian 1.3.2.2 BasicBlock<HCE> bb = h.get(e_n);
584 pnkfelix 1.1.2.17 if (bb == null) {
585 cananian 1.3.2.2 h.put(e_n, bb=new BasicBlock<HCE>(e_n, this));
586 pnkfelix 1.1.2.19 myHceToBB.put(e_n, bb);
587 pnkfelix 1.1.2.17 w.push(bb);
588 pnkfelix 1.1.2.17 }
589 pnkfelix 1.1.2.17 BasicBlock.addEdge(current, bb);
590 pnkfelix 1.1.2.17 }
591 pnkfelix 1.1.2.17 foundEnd = true;
592 pnkfelix 1.1.2.17
593 pnkfelix 1.1.2.17 } else { // one successor
594 cananian 1.3.2.1 assert n == 1 : "must have one successor";
595 cananian 1.7 HCE next = grapher.succC(last).get(0).to();
596 cananian 1.1.2.23 int m = grapher.predC(next).size();
597 pnkfelix 1.1.2.17 if (m > 1) { // control flow join
598 pnkfelix 1.1.2.17 if(DEBUG) System.out.println("found join: "+next);
599 pnkfelix 1.1.2.17
600 cananian 1.3.2.2 BasicBlock<HCE> bb = h.get(next);
601 pnkfelix 1.1.2.17 if (bb == null) {
602 cananian 1.3.2.2 bb = new BasicBlock<HCE>(next, this);
603 pnkfelix 1.1.2.17 h.put(next, bb);
604 pnkfelix 1.1.2.19 myHceToBB.put(next, bb);
605 pnkfelix 1.1.2.17 w.push(bb);
606 pnkfelix 1.1.2.17 }
607 pnkfelix 1.1.2.17 BasicBlock.addEdge(current, bb);
608 pnkfelix 1.1.2.17 foundEnd = true;
609 pnkfelix 1.1.2.17
610 pnkfelix 1.1.2.17 } else { // no join; update our guess
611 pnkfelix 1.1.2.17 if(DEBUG) System.out.println("found line: "+
612 pnkfelix 1.1.2.17 last+", "+ next);
613 pnkfelix 1.1.2.17
614 pnkfelix 1.1.2.17 current.size++;
615 pnkfelix 1.1.2.19 myHceToBB.put(next, current);
616 pnkfelix 1.1.2.17 last = next;
617 pnkfelix 1.1.2.17 }
618 pnkfelix 1.1.2.17 }
619 pnkfelix 1.1.2.17 }
620 pnkfelix 1.1.2.20
621 pnkfelix 1.1.2.17 current.last = last;
622 pnkfelix 1.1.2.21
623 cananian 1.3.2.2 final HCE flast = last;
624 cananian 1.3.2.2 final BasicBlock<HCE> fcurr = current;
625 cananian 1.3.2.1 assert grapher.succC(last).size() != 1 ||
626 cananian 1.7 grapher.predC(grapher.succC(last).get(0).
627 cananian 1.3.2.1 to()).size() > 1 : "succC invariant broken";
628 pnkfelix 1.1.2.21
629 pnkfelix 1.1.2.17 }
630 pnkfelix 1.1.2.19
631 pnkfelix 1.1.2.27 // efficiency hacks: make various immutable Collections
632 pnkfelix 1.1.2.27 // array-backed sets, and make them unmodifiable at
633 pnkfelix 1.1.2.27 // construction time rather than at accessor time.
634 cananian 1.3.2.2 leaves = Collections.unmodifiableSet(new LinearSet<BasicBlock<HCE>>(myLeaves));
635 pnkfelix 1.1.2.19 hceToBB = Collections.unmodifiableMap(myHceToBB);
636 cananian 1.3.2.2 blocks = Collections.unmodifiableSet(new LinearSet<BasicBlock<HCE>>
637 cananian 1.3.2.2 (new HashSet<BasicBlock<HCE>>(hceToBB.values())));
638 cananian 1.3.2.2 Iterator<BasicBlock<HCE>> bbIter = blocks.iterator();
639 pnkfelix 1.1.2.27 while (bbIter.hasNext()) {
640 cananian 1.3.2.2 BasicBlock<HCE> bb = bbIter.next();
641 cananian 1.3.2.2 bb.pred_bb = new LinearSet<BasicBlock<HCE>>(bb.pred_bb);
642 cananian 1.3.2.2 bb.succ_bb = new LinearSet<BasicBlock<HCE>>(bb.succ_bb);
643 pnkfelix 1.1.2.27
644 pnkfelix 1.1.2.29 // FSK: debug checkBlock(bb);
645 pnkfelix 1.1.2.27 }
646 pnkfelix 1.1.2.31
647 pnkfelix 1.1.2.31 if (CHECK_INSTRS) {
648 pnkfelix 1.1.2.31 // check that all instrs map to SOME block
649 cananian 1.3.2.2 Iterator<HCE> hceIter = hcode.getElementsI();
650 pnkfelix 1.1.2.31 while(hceIter.hasNext()) {
651 cananian 1.3.2.2 HCE hce = hceIter.next();
652 pnkfelix 1.1.2.34 System.out.println("BB Check: "+hce);
653 pnkfelix 1.1.2.31 if (!(hce instanceof harpoon.IR.Assem.InstrLABEL) &&
654 pnkfelix 1.1.2.31 !(hce instanceof harpoon.IR.Assem.InstrDIRECTIVE)&&
655 pnkfelix 1.1.2.32 !(hce instanceof harpoon.IR.Assem.InstrJUMP) &&
656 pnkfelix 1.1.2.32
657 pnkfelix 1.1.2.32 (getBlock(hce) == null)) {
658 pnkfelix 1.1.2.32
659 cananian 1.3.2.2 Set<HCE> s = new HashSet<HCE>();
660 cananian 1.3.2.2 List<HCodeEdge<HCE>> t = new ArrayList<HCodeEdge<HCE>>();
661 pnkfelix 1.1.2.32 t.addAll(grapher.predC(hce));
662 pnkfelix 1.1.2.32 for(int i=0; i<t.size(); i++) {
663 cananian 1.3.2.2 HCE p = t.get(i).from();
664 pnkfelix 1.1.2.32 if(!s.contains(p)) {
665 pnkfelix 1.1.2.32 // System.out.println("visiting "+p);
666 pnkfelix 1.1.2.32 s.add(p);
667 pnkfelix 1.1.2.32 t.addAll(grapher.predC(p));
668 pnkfelix 1.1.2.32 if (grapher.predC(p).size() == 0) {
669 pnkfelix 1.1.2.32 System.out.println
670 pnkfelix 1.1.2.32 ("no preds for "+p);
671 pnkfelix 1.1.2.32 }
672 pnkfelix 1.1.2.32 if (getBlock(p) != null) {
673 pnkfelix 1.1.2.32 System.out.println
674 pnkfelix 1.1.2.32 ("there IS a BB for pred:"+p);
675 pnkfelix 1.1.2.32 }
676 pnkfelix 1.1.2.32 }
677 pnkfelix 1.1.2.32 }
678 pnkfelix 1.1.2.32 System.out.println("no BB for "+hce+"\n");
679 pnkfelix 1.1.2.32 }
680 pnkfelix 1.1.2.31 }
681 pnkfelix 1.1.2.31 }
682 pnkfelix 1.1.2.31
683 pnkfelix 1.1.2.30
684 pnkfelix 1.1.2.30 if (TIME) System.out.print("#");
685 pnkfelix 1.1.2.27 }
686 pnkfelix 1.1.2.27
687 cananian 1.3.2.2 private void checkBlock(BasicBlock<HCE> block) {
688 cananian 1.3.2.2 List<HCE> blockL = block.statements();
689 pnkfelix 1.1.2.27 int sz = blockL.size();
690 cananian 1.3.2.2 Iterator<HCE> iter = blockL.iterator();
691 cananian 1.3.2.2 HCE curr = null;
692 pnkfelix 1.1.2.27 while(iter.hasNext()) {
693 cananian 1.3.2.2 HCE h = iter.next();
694 pnkfelix 1.1.2.27 if (curr == null) {
695 cananian 1.3.2.1 assert h == block.first;
696 pnkfelix 1.1.2.27
697 pnkfelix 1.1.2.27 curr = h;
698 pnkfelix 1.1.2.27 } else {
699 cananian 1.3.2.1 assert grapher.succC(curr).size() == 1;
700 cananian 1.7 assert grapher.succC(curr).get(0).to() == h;
701 pnkfelix 1.1.2.27
702 pnkfelix 1.1.2.27 curr = h;
703 pnkfelix 1.1.2.27 }
704 pnkfelix 1.1.2.27 sz--;
705 pnkfelix 1.1.2.27 }
706 cananian 1.3.2.1 assert curr == block.last;
707 cananian 1.3.2.1 assert sz == 0;
708 pnkfelix 1.1.2.17 }
709 pnkfelix 1.1.2.45 public void dumpCFG() { dumpCFG(root); }
710 pnkfelix 1.1.2.47
711 pnkfelix 1.1.2.47 public String toString() { return "BasicBlock.Factory : \n"+getCFG(root); }
712 pnkfelix 1.1.2.17
713 pnkfelix 1.1.2.17 public static void dumpCFG(BasicBlock start) {
714 pnkfelix 1.1.2.17 Enumeration e = new ReversePostOrderEnumerator(start);
715 pnkfelix 1.1.2.17 while (e.hasMoreElements()) {
716 pnkfelix 1.1.2.17 BasicBlock bb = (BasicBlock)e.nextElement();
717 pnkfelix 1.1.2.17 System.out.println("Basic block "+bb + " size:"+ bb.size);
718 pnkfelix 1.1.2.17 System.out.println("BasicBlock in : "+bb.pred_bb);
719 pnkfelix 1.1.2.17 System.out.println("BasicBlock out: "+bb.succ_bb);
720 pnkfelix 1.1.2.17 System.out.println();
721 pnkfelix 1.1.2.17 }
722 pnkfelix 1.1.2.1 }
723 pnkfelix 1.1.2.47
724 pnkfelix 1.1.2.47 public static String getCFG(BasicBlock start) {
725 pnkfelix 1.1.2.47 Enumeration e = new ReversePostOrderEnumerator(start);
726 pnkfelix 1.1.2.47 StringBuffer sb = new StringBuffer();
727 pnkfelix 1.1.2.47 while (e.hasMoreElements()) {
728 pnkfelix 1.1.2.47 BasicBlock bb = (BasicBlock)e.nextElement();
729 pnkfelix 1.1.2.47 sb.append("Basic block "+bb + " size:"+ bb.size);
730 pnkfelix 1.1.2.47 sb.append("\n");
731 pnkfelix 1.1.2.47 sb.append("BasicBlock in : "+bb.pred_bb);
732 pnkfelix 1.1.2.47 sb.append("\n");
733 pnkfelix 1.1.2.47 sb.append("BasicBlock out: "+bb.succ_bb);
734 pnkfelix 1.1.2.47 sb.append("\n");
735 pnkfelix 1.1.2.47 }
736 pnkfelix 1.1.2.47 return sb.toString();
737 pnkfelix 1.1.2.47 }
738 pnkfelix 1.1.2.47
739 pnkfelix 1.1.2.1 }
740 cananian 1.2 }