1 salcianu 1.1.2.1 // FCFGBasicBlock.java, created Fri Dec 14 11:03:15 2001 by salcianu
2 salcianu 1.1.2.1 // Copyright (C) 2000 Alexandru SALCIANU <salcianu@MIT.EDU>
3 salcianu 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 salcianu 1.1.2.1 package harpoon.Analysis;
5 salcianu 1.1.2.1
6 salcianu 1.1.2.1 import java.util.List;
7 salcianu 1.1.2.1 import java.util.Map;
8 salcianu 1.1.2.1 import java.util.HashMap;
9 salcianu 1.1.2.1 import java.util.Set;
10 salcianu 1.1.2.1 import java.util.HashSet;
11 salcianu 1.1.2.1 import java.util.LinkedList;
12 salcianu 1.1.2.1 import java.util.Enumeration;
13 salcianu 1.1.2.1 import java.util.NoSuchElementException;
14 salcianu 1.1.2.1 import java.util.ListIterator;
15 salcianu 1.1.2.1
16 salcianu 1.1.2.1 import harpoon.ClassFile.HCode;
17 salcianu 1.1.2.1 import harpoon.ClassFile.HCodeElement;
18 salcianu 1.1.2.1
19 cananian 1.5 import harpoon.IR.Quads.Code;
20 salcianu 1.1.2.1 import harpoon.IR.Quads.Quad;
21 salcianu 1.1.2.1 import harpoon.IR.Quads.METHOD;
22 salcianu 1.1.2.1 import harpoon.IR.Quads.HANDLER;
23 salcianu 1.1.2.1 import harpoon.IR.Quads.HEADER;
24 salcianu 1.1.2.1
25 cananian 1.7 import net.cscott.jutil.UnmodifiableListIterator;
26 cananian 1.6 import harpoon.Util.Collections.WorkSet;
27 salcianu 1.1.2.1 import harpoon.Util.Worklist;
28 salcianu 1.1.2.1
29 salcianu 1.1.2.1 import harpoon.Util.Util;
30 salcianu 1.1.2.1
31 salcianu 1.1.2.1 /**
32 salcianu 1.1.2.1 * <code>FCFGBasicBlock</code> is a basic block structure for the Factored
33 salcianu 1.1.2.1 Control Flow Graph (FCFG) representation. This representation is based on
34 salcianu 1.1.2.1 a factored and <i>implicit</i> representation of exceptions. It is described
35 salcianu 1.1.2.1 in detail in the paper
36 salcianu 1.1.2.1 <a href="http://www.research.ibm.com/jalapeno/pub/paste99.ps">Efficient and Precise Modeling of Exceptions for the Analysis of Java Programs</a>
37 salcianu 1.1.2.1 by Choi, Grove, Hind and Sarkar.
38 salcianu 1.1.2.1
39 salcianu 1.1.2.1 <p>
40 salcianu 1.1.2.1 Each <code>FCFGBasicBlock</code> corresponds to a list of
41 salcianu 1.1.2.1 consecutive instructions, such that:
42 salcianu 1.1.2.1 <ul>
43 salcianu 1.1.2.1 <li>the normal (that is, in the absence of exceptions) flow of execution
44 salcianu 1.1.2.1 through them is a straight line, and
45 salcianu 1.1.2.1 <li>all the instructions are protected by the same set of handlers.
46 salcianu 1.1.2.1 </ul>
47 salcianu 1.1.2.1
48 salcianu 1.1.2.1 Therefore, a <code>FCFGBasicBlock</code> has a single entry point, a
49 salcianu 1.1.2.1 single <i>normal</i> exit point and possibly many <i>lateral</i>
50 salcianu 1.1.2.1 exits due to exceptions. As all the instructions a
51 salcianu 1.1.2.1 <code>FCFGBasicBlock</code> are protected by the same set of handlers
52 salcianu 1.1.2.1 (in fact a list because the order the handlers are processed in is
53 salcianu 1.1.2.1 important), these lateral exits can be kept once for the entire basic
54 salcianu 1.1.2.1 block, hence the name <i>factored</i>.
55 salcianu 1.1.2.1
56 salcianu 1.1.2.1 <p>
57 cananian 1.4 Similar to <code>BasicBlock</code>s, the only way of producing
58 salcianu 1.1.2.1 <code>FCFGBasicBlock</code>s is by using
59 salcianu 1.1.2.1 <code>FCFGBasicBlock.Factory</code>.
60 salcianu 1.1.2.1
61 salcianu 1.1.2.1 *
62 salcianu 1.1.2.1 * @author Alexandru SALCIANU <salcianu@MIT.EDU>
63 cananian 1.7 * @version $Id: FCFGBasicBlock.java,v 1.7 2004/02/08 01:49:03 cananian Exp $
64 cananian 1.5 */
65 salcianu 1.1.2.1 public class FCFGBasicBlock implements BasicBlockInterf {
66 salcianu 1.1.2.1
67 salcianu 1.1.2.1 /** Creates a <code>FCFGBasicBlock</code>. This method is called
68 salcianu 1.1.2.1 only by the <code>FCFGBasicBlock.Factory</code>. */
69 salcianu 1.1.2.1 protected FCFGBasicBlock(Quad q, Factory f) {
70 salcianu 1.1.2.1 id = f.BBnum++;
71 salcianu 1.1.2.1 first = q;
72 salcianu 1.1.2.1 size = 1;
73 salcianu 1.1.2.1 next_bb = new HashSet();
74 salcianu 1.1.2.1 prev_bb = new HashSet();
75 salcianu 1.1.2.1 protected_bb = new HashSet();
76 salcianu 1.1.2.1 handler_bb = new LinkedList();
77 salcianu 1.1.2.1 }
78 salcianu 1.1.2.1
79 salcianu 1.1.2.1 protected int id;
80 salcianu 1.1.2.1
81 salcianu 1.1.2.1 /** Next BBs (according to the normal control flow). */
82 salcianu 1.1.2.1 protected Set next_bb;
83 salcianu 1.1.2.1 /** Previous BBs (according to the normal control flow). */
84 salcianu 1.1.2.1 protected Set prev_bb;
85 salcianu 1.1.2.1
86 salcianu 1.1.2.1 /** Predecessor BBs in the exceptional control flow. */
87 salcianu 1.1.2.1 protected Set protected_bb;
88 salcianu 1.1.2.1 /** Successor BBs in the exceptional control flow. */
89 salcianu 1.1.2.1 protected List handler_bb;
90 salcianu 1.1.2.1
91 salcianu 1.1.2.1 protected Quad first;
92 salcianu 1.1.2.1 protected Quad last;
93 salcianu 1.1.2.1
94 salcianu 1.1.2.1 // number of instructions in this basic block
95 salcianu 1.1.2.1 int size;
96 salcianu 1.1.2.1
97 salcianu 1.1.2.1 /** Returns the first instruction of <code>this</code> basic block. */
98 salcianu 1.1.2.1 public HCodeElement getFirst() {
99 salcianu 1.1.2.1 return first;
100 salcianu 1.1.2.1 }
101 salcianu 1.1.2.1
102 salcianu 1.1.2.1 /** Returns the last instruction of <code>this</code> basic block. */
103 salcianu 1.1.2.1 public HCodeElement getLast() {
104 salcianu 1.1.2.1 return last;
105 salcianu 1.1.2.1 }
106 salcianu 1.1.2.1
107 salcianu 1.1.2.1 /** Returns the set of predecessor BBs in the normal control
108 salcianu 1.1.2.1 flow. */
109 salcianu 1.1.2.1 public Set normalNextSet() {
110 salcianu 1.1.2.1 return next_bb;
111 salcianu 1.1.2.1 }
112 salcianu 1.1.2.1
113 salcianu 1.1.2.1 /** Returns the set of successor BBs in the normal control
114 salcianu 1.1.2.1 flow. */
115 salcianu 1.1.2.1 public Set normalPrevSet() {
116 salcianu 1.1.2.1 return prev_bb;
117 salcianu 1.1.2.1 }
118 salcianu 1.1.2.1
119 salcianu 1.1.2.1
120 salcianu 1.1.2.1 // add the normal control flow edge <from,to>
121 salcianu 1.1.2.1 protected static void addNormalEdge
122 salcianu 1.1.2.1 (FCFGBasicBlock from, FCFGBasicBlock to) {
123 salcianu 1.1.2.1 from.next_bb.add(to);
124 salcianu 1.1.2.1 to.prev_bb.add(from);
125 salcianu 1.1.2.1 }
126 salcianu 1.1.2.1
127 salcianu 1.1.2.1 /** Returns the set of predecessor BBs in the exceptional control
128 salcianu 1.1.2.1 flow. For a basic block that starts with a
129 salcianu 1.1.2.1 <code>HANDLER</code> instruction, this is the set of basic
130 salcianu 1.1.2.1 blocks whose instructions are protected by that
131 salcianu 1.1.2.1 handler. <code>FOOTER</code> is the default handler: the
132 salcianu 1.1.2.1 uncaught exceptions are sent to the caller. For any other
133 salcianu 1.1.2.1 basic block, this set is empty. */
134 salcianu 1.1.2.1 public Set protectedSet() {
135 salcianu 1.1.2.1 return protected_bb;
136 salcianu 1.1.2.1 }
137 salcianu 1.1.2.1
138 salcianu 1.1.2.1 /** Returns the list of successor BBs in the exceptional control
139 salcianu 1.1.2.1 flow. These are the handlers that protect the instructions
140 salcianu 1.1.2.1 from this basic block. <code>FOOTER</code> is the default
141 salcianu 1.1.2.1 handler: the uncaught exceptions are sent to the caller.
142 salcianu 1.1.2.1 The order of the handlers in the list is the order in which the
143 salcianu 1.1.2.1 JVM tries to find an appropriate handler. */
144 salcianu 1.1.2.1 public List handlerList() {
145 salcianu 1.1.2.1 return handler_bb;
146 salcianu 1.1.2.1 }
147 salcianu 1.1.2.1
148 salcianu 1.1.2.1 /** Returns <i>all</i> the predecessors of the basic block,
149 salcianu 1.1.2.1 according to the normal and the exceptional control flow. */
150 salcianu 1.1.2.1 public Set prevSet() {
151 salcianu 1.1.2.1 Set result = new HashSet();
152 salcianu 1.1.2.1 result.addAll(normalPrevSet());
153 salcianu 1.1.2.1 result.addAll(protectedSet());
154 salcianu 1.1.2.1 return result;
155 salcianu 1.1.2.1 }
156 salcianu 1.1.2.1
157 salcianu 1.1.2.1 /** Returns <i>all</i> the successors of the basic block,
158 salcianu 1.1.2.1 according to the normal and the exceptional control flow. */
159 salcianu 1.1.2.1 public Set nextSet() {
160 salcianu 1.1.2.1 Set result = new HashSet();
161 salcianu 1.1.2.1 result.addAll(normalNextSet());
162 salcianu 1.1.2.1 result.addAll(handlerList());
163 salcianu 1.1.2.1 return result;
164 salcianu 1.1.2.1 }
165 salcianu 1.1.2.1
166 salcianu 1.1.2.1 // record the fact that the instructions from the basic block
167 salcianu 1.1.2.1 // <code>from</code> are controlled by the handler <code>to</code>.
168 salcianu 1.1.2.1 protected static void addExcpEdge(FCFGBasicBlock from, FCFGBasicBlock to) {
169 salcianu 1.1.2.1 from.handler_bb.add(to);
170 salcianu 1.1.2.1 to.protected_bb.add(from);
171 salcianu 1.1.2.1 }
172 salcianu 1.1.2.1
173 salcianu 1.1.2.1
174 salcianu 1.1.2.1 private class InstructionListIterator extends UnmodifiableListIterator {
175 salcianu 1.1.2.1
176 salcianu 1.1.2.1 InstructionListIterator(Quad first_quad, int first_index) {
177 salcianu 1.1.2.1 next = first_quad;
178 salcianu 1.1.2.1 index = first_index;
179 salcianu 1.1.2.1 }
180 salcianu 1.1.2.1
181 salcianu 1.1.2.1 // element for next() to return
182 salcianu 1.1.2.1 Quad next;
183 salcianu 1.1.2.1
184 salcianu 1.1.2.1 // where currently pointing?
185 salcianu 1.1.2.1 // Invariant: 0 <= index /\ index <= size
186 salcianu 1.1.2.1 int index;
187 salcianu 1.1.2.1
188 salcianu 1.1.2.1 public boolean hasNext() {
189 salcianu 1.1.2.1 return index != size;
190 salcianu 1.1.2.1 }
191 salcianu 1.1.2.1
192 salcianu 1.1.2.1 public Object next() {
193 salcianu 1.1.2.1 if (index == size) {
194 salcianu 1.1.2.1 throw new NoSuchElementException();
195 salcianu 1.1.2.1 }
196 salcianu 1.1.2.1
197 salcianu 1.1.2.1 index++;
198 salcianu 1.1.2.1 Object ret = next;
199 salcianu 1.1.2.1
200 salcianu 1.1.2.1 if (index != size) {
201 salcianu 1.1.2.1 if(next instanceof HEADER)
202 salcianu 1.1.2.1 next = next.next(1);
203 salcianu 1.1.2.1 else
204 salcianu 1.1.2.1 next = next.next(0);
205 salcianu 1.1.2.1 } else {
206 salcianu 1.1.2.1 // keep 'next' the same, since previous()
207 salcianu 1.1.2.1 // needs to be able to return it
208 salcianu 1.1.2.1 }
209 salcianu 1.1.2.1
210 salcianu 1.1.2.1 return ret;
211 salcianu 1.1.2.1 }
212 salcianu 1.1.2.1
213 salcianu 1.1.2.1
214 salcianu 1.1.2.1 public boolean hasPrevious() {
215 salcianu 1.1.2.1 return index > 0;
216 salcianu 1.1.2.1 }
217 salcianu 1.1.2.1
218 salcianu 1.1.2.1 public Object previous() {
219 salcianu 1.1.2.1 if (index <= 0) {
220 salcianu 1.1.2.1 throw new NoSuchElementException();
221 salcianu 1.1.2.1 }
222 salcianu 1.1.2.1
223 salcianu 1.1.2.1 // special case: if index == size, then we just
224 salcianu 1.1.2.1 // return <next>
225 salcianu 1.1.2.1 if (index != size) {
226 salcianu 1.1.2.1 next = next.prev(0);
227 salcianu 1.1.2.1 }
228 salcianu 1.1.2.1 index--;
229 salcianu 1.1.2.1
230 salcianu 1.1.2.1 return next;
231 salcianu 1.1.2.1 }
232 salcianu 1.1.2.1
233 salcianu 1.1.2.1 public int nextIndex() {
234 salcianu 1.1.2.1 return index;
235 salcianu 1.1.2.1 }
236 salcianu 1.1.2.1 };
237 salcianu 1.1.2.1
238 salcianu 1.1.2.1
239 salcianu 1.1.2.1 public List statements() {
240 salcianu 1.1.2.1 return new java.util.AbstractSequentialList() {
241 salcianu 1.1.2.1 public int size() { return size; }
242 salcianu 1.1.2.1 public ListIterator listIterator(int index) {
243 salcianu 1.1.2.1 // check argument
244 salcianu 1.1.2.1 if (index < 0) {
245 salcianu 1.1.2.1 throw new IndexOutOfBoundsException(index + "< 0");
246 salcianu 1.1.2.1 } else if (index > size) {
247 salcianu 1.1.2.1 throw new
248 salcianu 1.1.2.1 IndexOutOfBoundsException(index + " > " + size);
249 salcianu 1.1.2.1 }
250 salcianu 1.1.2.1
251 salcianu 1.1.2.1 Quad first_quad = first;
252 salcianu 1.1.2.1 int bound = (index == size) ? index - 1 : index ;
253 salcianu 1.1.2.1 for(int i = 0; i < bound; i++)
254 salcianu 1.1.2.1 first_quad = first_quad.next(0);
255 salcianu 1.1.2.1
256 salcianu 1.1.2.1 return new InstructionListIterator(first_quad, index);
257 salcianu 1.1.2.1 }
258 salcianu 1.1.2.1 };
259 salcianu 1.1.2.1 }
260 salcianu 1.1.2.1
261 salcianu 1.1.2.1
262 salcianu 1.1.2.1 public void accept(BasicBlockInterfVisitor v) {
263 salcianu 1.1.2.1 v.visit(this);
264 salcianu 1.1.2.1 }
265 salcianu 1.1.2.1
266 salcianu 1.1.2.1 /** Returns a string identifying <code>this</code>
267 salcianu 1.1.2.1 <code>FCFGBasicBlock</code>. All the
268 salcianu 1.1.2.1 <code>FCFGBasicBlock</code>s generated for a given method have
269 salcianu 1.1.2.1 different string representations. */
270 salcianu 1.1.2.1 public String toString() {
271 salcianu 1.1.2.1 return "FCFG" + id;
272 salcianu 1.1.2.1 }
273 salcianu 1.1.2.1
274 salcianu 1.1.2.1 /** Factory structure for generating <code>FCFGBasicBlock</code>
275 salcianu 1.1.2.1 views of an <code>HCode</code>. */
276 salcianu 1.1.2.1 public static class Factory implements BasicBlockFactoryInterf {
277 salcianu 1.1.2.1
278 cananian 1.5 protected Code hcode;
279 salcianu 1.1.2.1 protected Set blocks;
280 salcianu 1.1.2.1 protected Set leaves;
281 salcianu 1.1.2.1 protected FCFGBasicBlock root;
282 salcianu 1.1.2.1 protected Map quadToBB;
283 salcianu 1.1.2.1
284 salcianu 1.1.2.1 int BBnum = 0;
285 salcianu 1.1.2.1
286 salcianu 1.1.2.1 /** Produces a <code>FCFGBasicBlock</code> view of
287 salcianu 1.1.2.1 <code>hcode</code> <code>hcode</code> must be in
288 salcianu 1.1.2.1 "quad-with-try" format. */
289 salcianu 1.1.2.1 public Factory(HCode hcode) {
290 cananian 1.3.2.1 assert hcode.getName().equals("quad-with-try") : "FCFG works only for quad-with-try";
291 salcianu 1.1.2.1
292 cananian 1.5 this.hcode = (Code) hcode;
293 salcianu 1.1.2.1
294 salcianu 1.1.2.1 quadToBB = new HashMap();
295 salcianu 1.1.2.1 leaves = new HashSet();
296 salcianu 1.1.2.1 blocks = new HashSet();
297 salcianu 1.1.2.1
298 cananian 1.5 METHOD method = this.hcode.getRootElement().method();
299 salcianu 1.1.2.1 Set[] controlled = get_controlled(method);
300 salcianu 1.1.2.1
301 salcianu 1.1.2.1 Worklist w = new WorkSet();
302 salcianu 1.1.2.1 HEADER header = (HEADER) hcode.getRootElement();
303 salcianu 1.1.2.1 root = new FCFGBasicBlock(header, this);
304 salcianu 1.1.2.1 blocks.add(root);
305 salcianu 1.1.2.1 quadToBB.put(header, root);
306 salcianu 1.1.2.1 w.push(root);
307 salcianu 1.1.2.1
308 salcianu 1.1.2.1 while(!w.isEmpty()) {
309 salcianu 1.1.2.1 FCFGBasicBlock current = (FCFGBasicBlock) w.pull();
310 salcianu 1.1.2.1
311 salcianu 1.1.2.1 // 'last' is our guess on which elem will be the last;
312 salcianu 1.1.2.1 // thus we start with the most conservative guess
313 salcianu 1.1.2.1 Quad last = (Quad) current.getFirst();
314 salcianu 1.1.2.1 boolean foundEnd = false;
315 salcianu 1.1.2.1
316 salcianu 1.1.2.1 while(!foundEnd) {
317 salcianu 1.1.2.1 Quad succs[] = last.next();
318 salcianu 1.1.2.1
319 salcianu 1.1.2.1 // for METHOD, eliminate the bogus edges toward HANDLERs
320 salcianu 1.1.2.1 if(last == method)
321 salcianu 1.1.2.1 succs = new Quad[]{succs[0]};
322 salcianu 1.1.2.1 // for HEADER eliminate the bogus edge toward FOOTER
323 salcianu 1.1.2.1 else if(last == header)
324 salcianu 1.1.2.1 succs = new Quad[]{succs[1]};
325 salcianu 1.1.2.1
326 salcianu 1.1.2.1 if((succs.length > 1) || // split point
327 salcianu 1.1.2.1 (succs.length == 0)) { // end of method code
328 salcianu 1.1.2.1 end_basic_block(current, last, succs, w);
329 salcianu 1.1.2.1 foundEnd = true;
330 salcianu 1.1.2.1 if(succs.length == 0)
331 salcianu 1.1.2.1 leaves.add(current);
332 salcianu 1.1.2.1 } else { // one successor
333 salcianu 1.1.2.1 Quad next = succs[0];
334 salcianu 1.1.2.1 if((next.prev().length > 1) || // join point
335 salcianu 1.1.2.1 different_handlers(last, next, controlled)) {
336 salcianu 1.1.2.1 end_basic_block(current, last, succs, w);
337 salcianu 1.1.2.1 foundEnd = true;
338 salcianu 1.1.2.1 } else {
339 salcianu 1.1.2.1 quadToBB.put(next, current);
340 salcianu 1.1.2.1 last = next;
341 salcianu 1.1.2.1 current.size++;
342 salcianu 1.1.2.1 }
343 salcianu 1.1.2.1 }
344 salcianu 1.1.2.1 }
345 salcianu 1.1.2.1
346 salcianu 1.1.2.1 current.last = last;
347 salcianu 1.1.2.1 }
348 salcianu 1.1.2.1 }
349 salcianu 1.1.2.1
350 salcianu 1.1.2.1 private Set[] get_controlled(METHOD method) {
351 salcianu 1.1.2.1 int nb_handlers = method.nextLength() - 1;
352 salcianu 1.1.2.1 Set[] controlled = new Set[nb_handlers];
353 salcianu 1.1.2.1 for(int i = 0; i < nb_handlers; i++)
354 salcianu 1.1.2.1 controlled[i] = ((HANDLER) method.next(i+1)).protectedSet();
355 salcianu 1.1.2.1 return controlled;
356 salcianu 1.1.2.1 }
357 salcianu 1.1.2.1
358 salcianu 1.1.2.1 // The basic block "current" ends at "last". We examine "last"'s
359 salcianu 1.1.2.1 // succesors (from succs[]) and, if necessary, create new
360 salcianu 1.1.2.1 // basic blocks for them. These new basic blocks are put into
361 salcianu 1.1.2.1 // the worklist w.
362 salcianu 1.1.2.1 private void end_basic_block
363 salcianu 1.1.2.1 (FCFGBasicBlock current, Quad last, Quad succs[], Worklist w) {
364 salcianu 1.1.2.1 // examine the normal successors
365 salcianu 1.1.2.1 for(int i = 0; i < succs.length; i++) {
366 salcianu 1.1.2.1 // the edges between METHOD and HANDLERs are bogus
367 salcianu 1.1.2.1 if(succs[i] instanceof HANDLER) continue;
368 salcianu 1.1.2.1 FCFGBasicBlock bb = get_bb(succs[i], w);
369 salcianu 1.1.2.1 FCFGBasicBlock.addNormalEdge(current, bb);
370 salcianu 1.1.2.1 }
371 salcianu 1.1.2.1
372 salcianu 1.1.2.1 // find the relevant handlers
373 cananian 1.5 METHOD method = hcode.getRootElement().method();
374 salcianu 1.1.2.1 Quad handlers[] = method.next();
375 salcianu 1.1.2.1 int nb_handlers = handlers.length - 1;
376 salcianu 1.1.2.1 for(int i = 0; i < nb_handlers; i++) {
377 salcianu 1.1.2.1 HANDLER handler = (HANDLER) handlers[i+1];
378 salcianu 1.1.2.1 if(handler.protectedSet().contains(last)) {
379 salcianu 1.1.2.1 FCFGBasicBlock bb = get_bb(handler, w);
380 salcianu 1.1.2.1 FCFGBasicBlock.addExcpEdge(current, bb);
381 salcianu 1.1.2.1 }
382 salcianu 1.1.2.1 }
383 salcianu 1.1.2.1 }
384 salcianu 1.1.2.1
385 salcianu 1.1.2.1 // Get the basic block that starts with the quad "succ". If
386 salcianu 1.1.2.1 // such a basic block does not exist yet, create a new one and
387 salcianu 1.1.2.1 // add it to the worklist w (in order for it to be processed
388 salcianu 1.1.2.1 // later).
389 salcianu 1.1.2.1 private FCFGBasicBlock get_bb(Quad succ, Worklist w) {
390 salcianu 1.1.2.1 FCFGBasicBlock bb = (FCFGBasicBlock) quadToBB.get(succ);
391 salcianu 1.1.2.1 if(bb == null) {
392 salcianu 1.1.2.1 // new basic block -> create it and put it into w
393 salcianu 1.1.2.1 bb = new FCFGBasicBlock(succ, this);
394 salcianu 1.1.2.1 blocks.add(bb);
395 salcianu 1.1.2.1 quadToBB.put(succ, bb);
396 salcianu 1.1.2.1 w.push(bb);
397 salcianu 1.1.2.1 }
398 salcianu 1.1.2.1 return bb;
399 salcianu 1.1.2.1 }
400 salcianu 1.1.2.1
401 salcianu 1.1.2.1 // checks whether a and b are protected by different sets of handlers
402 salcianu 1.1.2.1 // requires: controlled[i] = protectedSet() of the ith handler.
403 salcianu 1.1.2.1 private boolean different_handlers(Quad a, Quad b, Set[] controlled) {
404 salcianu 1.1.2.1 for(int i = 0; i < controlled.length; i++)
405 salcianu 1.1.2.1 if(controlled[i].contains(a) ^ controlled[i].contains(b))
406 salcianu 1.1.2.1 return true;
407 salcianu 1.1.2.1 return false;
408 salcianu 1.1.2.1 }
409 salcianu 1.1.2.1
410 salcianu 1.1.2.1 /** Returns the <code>HCode</code> that <code>this</code> factory
411 salcianu 1.1.2.1 produces FCFG basic blocks of. */
412 salcianu 1.1.2.1 public HCode getHCode() {
413 salcianu 1.1.2.1 return hcode;
414 salcianu 1.1.2.1 }
415 salcianu 1.1.2.1
416 salcianu 1.1.2.1 /** Returns the root <code>FCFGBasicBlock</code>.
417 salcianu 1.1.2.1 <BR> <B>effects:</B> returns the <code>FCFGBasicBlock</code>
418 salcianu 1.1.2.1 that is at the start of the set of
419 salcianu 1.1.2.1 <code>HCodeElement</code>s being analyzed.
420 salcianu 1.1.2.1 */
421 salcianu 1.1.2.1 public FCFGBasicBlock getRoot() {
422 salcianu 1.1.2.1 return root;
423 salcianu 1.1.2.1 }
424 salcianu 1.1.2.1
425 salcianu 1.1.2.1 /** Does the same thing as <code>getRoot</code>.
426 salcianu 1.1.2.1 Work around Java's weak typing system. */
427 salcianu 1.1.2.1 public BasicBlockInterf getRootBBInterf() {
428 salcianu 1.1.2.1 return getRoot();
429 salcianu 1.1.2.1 }
430 salcianu 1.1.2.1
431 salcianu 1.1.2.1 /** Returns the <code>FCFGBasicBlock</code>s constructed by
432 salcianu 1.1.2.1 <code>this</code> factory.
433 salcianu 1.1.2.1 */
434 salcianu 1.1.2.1 public Set blockSet() {
435 salcianu 1.1.2.1 return blocks;
436 salcianu 1.1.2.1 }
437 salcianu 1.1.2.1
438 salcianu 1.1.2.1 /** Returns the leaf <code>FCFGBasicBlock</code>s. <BR>
439 salcianu 1.1.2.1 <B>effects:</B> returns a <code>Set</code> of terminal
440 salcianu 1.1.2.1 <code>FCFGBasicBlock</code>s for the underlying
441 salcianu 1.1.2.1 <code>HCode</code>. Usually, this set will contain a
442 salcianu 1.1.2.1 single element, the <code>FCFGBasicBlock</code> for the
443 salcianu 1.1.2.1 <code>FOOTER</code>. */
444 salcianu 1.1.2.1 public Set getLeaves() {
445 salcianu 1.1.2.1 return leaves;
446 salcianu 1.1.2.1 }
447 salcianu 1.1.2.1
448 salcianu 1.1.2.1 /** Does the same thing as <code>getLeaves</code>.
449 salcianu 1.1.2.1 Work around Java's weak typing system. */
450 salcianu 1.1.2.1 public Set getLeavesBBInterf() {
451 salcianu 1.1.2.1 return getLeaves();
452 salcianu 1.1.2.1 }
453 salcianu 1.1.2.1
454 salcianu 1.1.2.1 /** Returns the <code>FCFGBasicBlock</code> containing
455 salcianu 1.1.2.1 <code>hce</code>.
456 salcianu 1.1.2.1 <BR> <B>requires:</B> hce is present in the code for
457 salcianu 1.1.2.1 <code>this</code>.
458 salcianu 1.1.2.1 <BR> <B>effects:</B> returns the basic block that contains
459 salcianu 1.1.2.1 <code>hce</code>, or <code>null</code> if
460 salcianu 1.1.2.1 <code>hce</code> is unreachable.
461 salcianu 1.1.2.1 */
462 salcianu 1.1.2.1 public FCFGBasicBlock getBlock(HCodeElement hce) {
463 salcianu 1.1.2.1 return (FCFGBasicBlock) quadToBB.get(hce);
464 salcianu 1.1.2.1 }
465 salcianu 1.1.2.1
466 salcianu 1.1.2.1 /** Does the same thing as <code>getBlock</code>.
467 salcianu 1.1.2.1 Work around Java's weak typing system. */
468 salcianu 1.1.2.1 public BasicBlockInterf getBBInterf(HCodeElement hce) {
469 salcianu 1.1.2.1 return getBlock(hce);
470 salcianu 1.1.2.1 }
471 salcianu 1.1.2.1
472 salcianu 1.1.2.1 };
473 salcianu 1.1.2.1
474 cananian 1.2 }