001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.compilers.opt.ir;
014
015 import java.util.Enumeration;
016
017 import org.jikesrvm.VM;
018 import org.jikesrvm.compilers.opt.util.SortedGraphNode;
019 import org.jikesrvm.compilers.opt.util.SpaceEffGraph;
020 import org.jikesrvm.compilers.opt.util.SpaceEffGraphNode;
021
022 /**
023 * The Factored Control Flow Graph (FCFG).
024 * <p>
025 * Like a standard control flow graph (CFG), the FCFG is composed
026 * of {@link BasicBlock basic blocks} which in turn contain
027 * {@link Instruction instructions}. The critical difference between
028 * a FCFG and a CFG is in the definition of basic blocks. In the FCFG,
029 * a Potentially Excepting Instruction (PEI) does not necessarily end its
030 * basic block. Therefore, although instructions within a FCFG basic block
031 * have the expected dominance relationships, they do <em>not</em> have the
032 * same post-dominance relationships as they would under the traditional
033 * basic block formulation used in a CFG.
034 * We chose to use an FCFG because doing so significantly reduces the
035 * number of basic blocks and control flow graph edges, thus reducing
036 * the time and space costs of representing the FCFG and also
037 * increasing the effectiveness of local (within a single basic block)
038 * analysis. However, using an FCFG does complicate flow-sensitive
039 * global analaysis. Many analyses can be easily extended to
040 * work on the FCFG. For those analyses that cannot, we provide utilities
041 * ({@link IR#unfactor()}, {@link BasicBlock#unfactor(IR)})
042 * to effectively convert the FCFG into a CFG.
043 * For a more detailed description of the FCFG and its implications for
044 * program analysis see the PASTE'99 paper by Choi et al.
045 * <a href="http://www.research.ibm.com/jalapeno/publication.html#paste99">
046 * Efficient and Precise Modeling of Exceptions for the Analysis of Java Programs </a>
047 * <p>
048 * The nodes in the FCFG are components in two distinct
049 * orderings, the "main" one is the control flow relationship
050 * in which edges represent flow of control.
051 * The secondary ordering is a linearization of the blocks
052 * which represents the ordering of instructions in the generated code.
053 * Both of these relationships are represented using the fields inherited
054 * from {@link SpaceEffGraphNode}.
055 * The control flow edges are the primary relationship and are encoded by
056 * <code>In</code> and <code>Out</code> relations of
057 * {@link SpaceEffGraphNode} and the {@link #entry()} and {@link #exit()}
058 * functions of <code>ControlFlowGraph</code>.
059 * The linear order is secondary and is represented by the order of the
060 * nodes in the doubly linked list ({@link SpaceEffGraphNode#next} and
061 * {@link SpaceEffGraphNode#prev}) and the functions
062 * ({@link #firstInCodeOrder()}, {@link #lastInCodeOrder()})
063 * of <code>ControlFlowGraph<code>.
064 * Utility functions are provided here and in {@link SpaceEffGraphNode}
065 * to manipulate these orderings.
066 *
067 * @see BasicBlock
068 * @see IR
069 */
070 public final class ControlFlowGraph extends SpaceEffGraph {
071
072 /**
073 * The distinguished exit node of the FCFG
074 */
075 private final BasicBlock _exitNode;
076
077 /**
078 * Return the entry node of the FCFG. All reachable nodes
079 * can be found by doing a forward traversal from this node.
080 *
081 * @return the entry node of the FCFG
082 */
083 public BasicBlock entry() {
084 return (BasicBlock) _firstNode;
085 }
086
087 /**
088 * Return the "exit" node of the FCFG. In a perfect world,
089 * we'd have the invariant that all nodes that are reachable in a
090 * forward traversal from cfgEntry() are exactly the same set of nodes
091 * as those that are reachable from cfgExit() via a reverse traversal,
092 * but that's currently not the case. Not all forward reachable nodes can
093 * be found by going backwards from exit. The issue is infinite loops
094 * (loops without normal exits).
095 *
096 * @return the exit node of the FCFG
097 */
098 public BasicBlock exit() {
099 return _exitNode;
100 }
101
102 /**
103 * Return the first basic block with respect to
104 * the current code linearization order.
105 *
106 * @return the first basic block in the code order
107 */
108 public BasicBlock firstInCodeOrder() {
109 return (BasicBlock) _firstNode;
110 }
111
112 /**
113 * Return the last basic block with respect to
114 * the current code linearization order.
115 *
116 * @return the last basic block in the code order
117 */
118 public BasicBlock lastInCodeOrder() {
119 return (BasicBlock) _lastNode;
120 }
121
122 /**
123 * Return the node to start with for a topological traversal
124 * of the FCFG.
125 * Override {@link SpaceEffGraph#startNode(boolean)}
126 * to use entry and exit; we want topological traversals to be with
127 * respect to FCFG edges not the code linearization order
128 *
129 * @param forward {@code true} for forward traversal, {@code false} for reverse
130 * @return the node to use as the start of a topological traversal
131 */
132 @Override
133 public SortedGraphNode startNode(boolean forward) {
134 if (forward) {
135 return entry();
136 } else {
137 return exit();
138 }
139 }
140
141 /**
142 * Densely number (0...n) all nodes in the FCFG.
143 * Override {@link SpaceEffGraph#compactNodeNumbering()} to also
144 * number the exit node.
145 */
146 @Override
147 public void compactNodeNumbering() {
148 super.compactNodeNumbering();
149 exit().setNumber(numberOfNodes++);
150 }
151
152 /**
153 * Builds the reverse topological order, i.e., the topsort order on the
154 * reverse graph. (This is not the same as reversing the topsort order
155 * of the forward graph.)
156 *
157 * @return the first node in the reverse topological ordering
158 */
159 @Override
160 public SortedGraphNode buildRevTopSort() {
161 SortedGraphNode firstNode = super.buildRevTopSort();
162 if (firstNode != null) {
163
164 // The CFG may have "end" nodes that are not reachable
165 // by all nodes. For example, a program with an infinite loop will not
166 // have a path from the loop to the exit node. Such nodes will not
167 // be in the reverseTopSort, but will be of interest. Thus, we now
168 // look for such nodes and add them to the revTopSort.
169
170 // We do this by visiting each basic block and checking to ensure
171 // that is marked with the sortMarker, if not we simply give it a
172 // number.
173
174 int sortMarker = firstNode.getSortMarker();
175 int sortNumber = firstNode.getBackwardSortNumber() - 1;
176 for (BasicBlock block = firstInCodeOrder(); block != null; block = block.nextBasicBlockInCodeOrder()) {
177
178 if (block.getSortMarker() != sortMarker) {
179 // found a block that wasn't on the Reverse Top List, add it.
180 // It is not clear where it should go, so since it is convenient
181 // to add at the front, we add it at the front!
182 block.setSortMarker(sortMarker);
183 block.setBackwardSortNumber(sortNumber--);
184
185 // put block at the beginning of the list
186 block.setSortedNext(firstNode, false);
187 firstNode = block;
188 }
189 }
190 }
191 return firstNode;
192 }
193
194 /**
195 * @param number starting value for assigning node numbers
196 */
197 public ControlFlowGraph(int number) {
198 _exitNode = BasicBlock.makeExit();
199 numberOfNodes = number;
200 }
201
202 /**
203 * Add an FCFG edge from the given basic block to the exit node.
204 *
205 * @param bb basic block to link to the exit
206 */
207 public void linkToExit(BasicBlock bb) {
208 bb.insertOut(exit());
209 }
210
211 /**
212 * Remove a basic block from both the CFG and code ordering
213 *
214 * @param bb the block to remove
215 */
216 public void removeFromCFGAndCodeOrder(BasicBlock bb) {
217 removeFromCFG(bb);
218 removeFromCodeOrder(bb);
219 }
220
221 /**
222 * Remove a basic block from the FCFG, leaving the code ordering unchanged.
223 *
224 * @param bb the block to remove
225 */
226 public void removeFromCFG(BasicBlock bb) {
227 bb.deleteIn();
228 bb.deleteOut();
229 }
230
231 /**
232 * Remove a basic block from the code ordering,
233 * leaving the FCFG unchanged.
234 *
235 * @param bb the block to remove
236 */
237 public void removeFromCodeOrder(BasicBlock bb) {
238 if (bb == _firstNode) {
239 _firstNode = bb.getNext();
240 }
241 if (bb == _lastNode) {
242 _lastNode = bb.getPrev();
243 }
244 bb.remove();
245 }
246
247 /**
248 * Insert a block 'toAdd' not currently in the code ordering after
249 * a block 'old' that is currently in the code ordering.
250 * If necessary, _lastNode is updated.
251 * No impact on FCFG edges.
252 *
253 * @param old a block currently in the code ordering
254 * @param toAdd a block to add after old in the code ordering
255 */
256 public void insertAfterInCodeOrder(BasicBlock old, BasicBlock toAdd) {
257 if (IR.SANITY_CHECK) VM._assert(toAdd.next == null);
258 if (IR.SANITY_CHECK) VM._assert(toAdd.prev == null);
259 SpaceEffGraphNode oldNext = old.next;
260 if (oldNext == null) {
261 if (IR.SANITY_CHECK) VM._assert(_lastNode == old);
262 old.append(toAdd);
263 _lastNode = toAdd;
264 } else {
265 old.append(toAdd);
266 toAdd.append(oldNext);
267 }
268 }
269
270 /**
271 * Insert a block 'toAdd' not currently in the code ordering before
272 * a block 'old' that is currently in the code ordering.
273 * If necessary, _firstNode is updated.
274 * No impact on FCFG edges.
275 *
276 * @param old a block currently in the code ordering
277 * @param toAdd a block to add before old in the code ordering
278 */
279 public void insertBeforeInCodeOrder(BasicBlock old, BasicBlock toAdd) {
280 if (IR.SANITY_CHECK) VM._assert(toAdd.next == null);
281 if (IR.SANITY_CHECK) VM._assert(toAdd.prev == null);
282 SpaceEffGraphNode oldPrev = old.prev;
283 if (oldPrev == null) {
284 if (IR.SANITY_CHECK) VM._assert(_firstNode == old);
285 _firstNode = toAdd;
286 toAdd.append(old);
287 } else {
288 oldPrev.append(toAdd);
289 toAdd.append(old);
290 }
291 }
292
293 /**
294 * Add a block not currently in the code ordering to the end of the
295 * code ordering.
296 * No impact on FCFG edges.
297 *
298 * @param bb the block to add to the end of the code ordering
299 */
300 public void addLastInCodeOrder(BasicBlock bb) {
301 if (IR.SANITY_CHECK) VM._assert(bb.next == null);
302 if (IR.SANITY_CHECK) VM._assert(bb.prev == null);
303 if (_firstNode == null) {
304 _firstNode = bb;
305 _lastNode = bb;
306 } else {
307 _lastNode.append(bb);
308 _lastNode = bb;
309 }
310 }
311
312 /**
313 * Make BB2 follow BB1 in the code ordering.
314 * If _lastNode == BB1, then update _lastNode appropriately
315 * No impact on FCFG edges.
316 *
317 * @param bb1 a basic block
318 * @param bb2 the basic block to follow bb1 in the code ordering
319 */
320 public void linkInCodeOrder(BasicBlock bb1, BasicBlock bb2) {
321 if (IR.SANITY_CHECK) VM._assert(bb1.next == null);
322 if (IR.SANITY_CHECK) VM._assert(bb2.prev == null);
323 bb1.append(bb2);
324 if (bb1 == _lastNode) {
325 _lastNode = bb2;
326 }
327 }
328
329 /**
330 * Create a break in the code order between bb1 and bb2
331 * (bb1 and bb2 must be currently adjacent in the code order).
332 * No impact on FCFG edges.
333 *
334 * @param bb1 the first block
335 * @param bb2 the second block
336 */
337 public void breakCodeOrder(BasicBlock bb1, BasicBlock bb2) {
338 if (IR.SANITY_CHECK) VM._assert(bb1.next == bb2);
339 if (IR.SANITY_CHECK) VM._assert(bb2.prev == bb1);
340 bb1.next = null;
341 bb2.prev = null;
342 }
343
344 /**
345 * Clear the code ordering information for the CFG.<p>
346 * NOTE: This method should only be called as part of a
347 * whole scale recomputation of the code order, for example
348 * by ReorderingPhase
349 */
350 public void clearCodeOrder() {
351 SpaceEffGraphNode cur = _firstNode;
352 if (cur == null) return;
353 while (true) {
354 SpaceEffGraphNode next = cur.next;
355 if (next == null) break;
356 cur.next = null;
357 next.prev = null;
358 cur = next;
359 }
360 _firstNode = null;
361 _lastNode = null;
362 }
363
364 // Enumerate the nodes in the CFG, casting them to whatever concrete type
365 // the caller wants.
366 private static final class NodeEnumeration<T> implements Enumeration<T> {
367 private SpaceEffGraphNode _node;
368 private SpaceEffGraphNode _end;
369
370 public NodeEnumeration(ControlFlowGraph cfg) {
371 _node = cfg.entry();
372 _end = cfg.exit();
373 }
374
375 @Override
376 public boolean hasMoreElements() { return _node != null; }
377
378 @Override
379 @SuppressWarnings("unchecked")
380 // We cast to whatever the concrete type of the graph is
381 public T nextElement() {
382 SpaceEffGraphNode n = _node;
383 _node = n.getNext();
384 if ((n != _end) && (_node == null)) {
385 _node = _end;
386 }
387 return (T) n;
388 }
389 }
390
391 public Enumeration<BasicBlock> basicBlocks() { return new NodeEnumeration<BasicBlock>(this); }
392 }