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.controlflow;
014
015 import java.util.Enumeration;
016
017 import org.jikesrvm.VM;
018 import org.jikesrvm.compilers.opt.OperationNotImplementedException;
019 import org.jikesrvm.compilers.opt.ir.BasicBlock;
020 import org.jikesrvm.compilers.opt.ir.ControlFlowGraph;
021 import org.jikesrvm.compilers.opt.ir.IR;
022 import org.jikesrvm.compilers.opt.util.Stack;
023
024 /**
025 * Calculate dominators using Langauer and Tarjan's fastest algorithm.
026 * TOPLAS 1(1), July 1979. This implementation uses path compression and
027 * results in a O(e * alpha(e,n)) complexity, where e is the number of
028 * edges in the CFG and n is the number of nodes.
029 * <p>
030 * Sources: TOPLAS article, Muchnick book
031 * <p>
032 * The current implementation (4/25/00) does not include the EXIT node
033 * in any solution despite the fact that it is part of the CFG (it has
034 * incoming edges). This is to be compatible with the old code.
035 */
036 public class LTDominators extends Stack<BasicBlock> {
037 static final boolean DEBUG = false;
038
039 /**
040 * Indicates whether we perform the algorithm over the CFG or
041 * the reverse CFG, i.e., whether we are computing dominators or
042 * post-dominators.
043 */
044 private final boolean forward;
045
046 /**
047 * a counter for assigning DFS numbers
048 */
049 protected int DFSCounter;
050
051 /**
052 * a mapping from DFS number to their basic blocks
053 */
054 private BasicBlock[] vertex;
055
056 /**
057 * a convenient place to locate the cfg to avoid passing it internally
058 */
059 private final ControlFlowGraph cfg;
060
061 /**
062 * The constructor, called by the perform method
063 * @param ir
064 * @param forward Should we compute regular dominators, or post-dominators?
065 */
066 LTDominators(IR ir, boolean forward) {
067 cfg = ir.cfg; // save the cfg for easy access
068 this.forward = forward; // save the forward flag
069 }
070
071 /**
072 * The entry point for this phase
073 * @param ir the IR
074 * @param forward Should we compute regular dominators, or post-dominators?
075 * @param unfactor Should we unfactor the CFG?
076 */
077 public static void perform(IR ir, boolean forward, boolean unfactor) {
078 if (ir.hasReachableExceptionHandlers()) {
079 if (unfactor) {
080 ir.unfactor();
081 } else {
082 throw new OperationNotImplementedException("IR with exception handlers");
083 }
084 }
085 LTDominators dom = new LTDominators(ir, forward);
086 dom.analyze(ir);
087 }
088
089 /**
090 * Compute approximate dominator/post dominator without unfactoring
091 * exception handlers. Can only be used if what the client wants is
092 * approximate domination (ie, if it doesn't actually have to be correct...)
093 * @param ir the IR
094 * @param forward Should we compute regular dominators, or post-dominators?
095 */
096 public static void approximate(IR ir, boolean forward) {
097 LTDominators dom = new LTDominators(ir, forward);
098 dom.analyze(ir);
099 }
100
101 /**
102 * analyze dominators
103 */
104 protected void analyze(IR ir) {
105 if (DEBUG) {
106 System.out.println(" Here's the CFG for method: " + ir.method.getName() + "\n" + ir.cfg);
107 }
108
109 // Step 1: Perform a DFS numbering
110 step1();
111
112 // Check to make sure all nodes were reached
113 checkReachability(ir);
114
115 // Step 2: the heart of the algorithm
116 step2();
117
118 // Step 3: adjust immediate dominators of nodes whoe current version of
119 // the immediate dominators differs from the nodes with the depth-first
120 // number of the node's semidominator.
121 step3();
122
123 if (DEBUG) {
124 printResults(ir);
125 }
126 }
127
128 /**
129 * Check to make sure all nodes were reached
130 */
131 private void checkReachability(IR ir) {
132 if (!forward) {
133 if (DFSCounter != cfg.numberOfNodes()) {
134 VM.sysWrite(" *** Warning ***\n CFG for method " +
135 ir.method.getName() +
136 " in class " +
137 ir.method.getDeclaringClass() +
138 " has unreachable nodes.\n");
139 VM.sysWrite(" Assuming pessimistic results in dominators computation\n" + " for unreachable nodes.\n");
140 }
141 }
142 }
143
144 /**
145 * The goal of this step is to perform a DFS numbering on the CFG,
146 * starting at the root. The exit node is not included.
147 */
148 private void step1() {
149 // allocate the vertex array, one element for each basic block, starting
150 // at 1
151 vertex = new BasicBlock[cfg.numberOfNodes() + 1];
152 DFSCounter = 0;
153 if (DEBUG) { System.out.println("Initializing blocks:"); }
154
155 // Initialize each block with an empty set of predecessors and
156 // a 0 for a semidominator
157 for (Enumeration<BasicBlock> bbEnum = cfg.basicBlocks(); bbEnum.hasMoreElements();) {
158 BasicBlock block = bbEnum.nextElement();
159 // We don't compute a result for the exit node in the forward direction
160 if (!forward || !block.isExit()) {
161 block.scratchObject = new LTDominatorInfo(block);
162 if (DEBUG) {
163 printNextNodes(block);
164 }
165 }
166 }
167
168 DFS();
169
170 if (DEBUG) {
171 System.out.println("DFSCounter: " + DFSCounter + ", CFG Nodes: " + cfg.numberOfNodes());
172 printDFSNumbers();
173 }
174 }
175
176 private void DFS() { DFS(getFirstNode()); }
177
178 /**
179 * Get the first node, either entry or exit
180 * depending on which way we are viewing the graph
181 * @return the entry node or exit node
182 */
183 private BasicBlock getFirstNode() {
184 if (forward) {
185 return cfg.entry();
186 } else {
187 return cfg.exit();
188 }
189 }
190
191 /**
192 * Print the "next" nodes (either out or in) for the passed block
193 * depending on which way we are viewing the graph
194 * @param block the basic block of interest
195 */
196 private void printNextNodes(BasicBlock block) {
197 if (forward) {
198 System.out.print(block + " Succs:");
199 } else {
200 System.out.print(block + " Preds:");
201 }
202 Enumeration<BasicBlock> e = getNextNodes(block);
203 while (e.hasMoreElements()) {
204 System.out.print(" ");
205 System.out.print(e.nextElement());
206 }
207 System.out.println();
208 }
209
210 /**
211 * Returns an enumeration of the "next" nodes (either out or in) for the
212 * passed block depending on which way we are viewing the graph
213 * @param block the basic block of interest
214 */
215 private Enumeration<BasicBlock> getNextNodes(BasicBlock block) {
216 Enumeration<BasicBlock> bbEnum;
217 if (forward) {
218 bbEnum = block.getOut();
219 } else {
220 bbEnum = block.getIn();
221 }
222 return bbEnum;
223 }
224
225 /**
226 * Returns an enumeration of the "prev" nodes (either in or out) for the
227 * passed block depending on which way we are viewing the graph
228 * @param block the basic block of interest
229 */
230 private Enumeration<BasicBlock> getPrevNodes(BasicBlock block) {
231 Enumeration<BasicBlock> bbEnum;
232 if (forward) {
233 bbEnum = block.getIn();
234 } else {
235 bbEnum = block.getOut();
236 }
237 return bbEnum;
238 }
239
240 /**
241 * The non-recursive depth-first numbering code called from Step 1.
242 * The recursive version was too costly on the toba benchmark on Linux/IA32.
243 * @param block the basic block to process
244 */
245 protected void DFS(BasicBlock block) {
246
247 // push node on to the emulated activation stack
248 push(block);
249
250 recurse:
251 while (!empty()) {
252
253 block = peek();
254 if (DEBUG) { System.out.println(" Processing (peek)" + block); }
255
256 if (block == null) {
257 if (DEBUG) { System.out.println(" Popping"); }
258 pop(); // return
259 continue;
260 }
261
262 // The current Dominance Frontier and SSA code assumes the exit
263 // node will not be part of the (regular) dominator solution.
264 // To avoid this from happening we screen it out here for forward CFG
265 //
266 // However, it really shouldn't be in the CFG, if it isn't a node!
267 if (forward && block == cfg.exit()) {
268 if (DEBUG) { System.out.println(" Popping"); }
269 pop(); // return
270 continue;
271 }
272
273 Enumeration<BasicBlock> e;
274 e = LTDominatorInfo.getInfo(block).getEnum();
275
276 if (e == null) {
277 if (DEBUG) { System.out.println(" Initial processing of " + block); }
278
279 DFSCounter++;
280 LTDominatorInfo.getInfo(block).setSemiDominator(DFSCounter);
281 vertex[DFSCounter] = block;
282 e = getNextNodes(block);
283 } else {
284 if (DEBUG) { System.out.println(" Resuming processing of " + block); }
285 }
286
287 while (e.hasMoreElements()) {
288 BasicBlock next = e.nextElement();
289
290 if (DEBUG) { System.out.println(" Inspecting next node: " + next); }
291
292 // We treat the exit node as not being in the CFG for forward direction
293 if (forward && next.isExit()) {
294 continue; // inner loop
295 }
296 if (getSemi(next) == 0) {
297 LTDominatorInfo.getInfo(next).setParent(block);
298
299 // simulate a recursive call
300 // save the enumeration state for resumption later
301 LTDominatorInfo.getInfo(block).setEnum(e);
302
303 if (DEBUG) { System.out.println(" Pushing" + next); }
304 push(next);
305 continue recurse;
306 }
307 } // while more nexts
308 // "Pop" from the emulated activiation stack
309 if (DEBUG) { System.out.println(" Popping"); }
310 pop();
311 } // while stack not empty loop
312 }
313
314 /**
315 * This is the heart of the algorithm. See sources for details.
316 */
317 private void step2() {
318 if (DEBUG) { System.out.println(" ******* Beginning STEP 2 *******\n"); }
319
320 // Visit each node in reverse DFS order, except for the root, which
321 // has number 1
322 // for i=n downto 2
323 for (int i = DFSCounter; i > 1; i--) {
324 // block = vertex[i]
325 BasicBlock block = vertex[i];
326 LTDominatorInfo blockInfo = LTDominatorInfo.getInfo(block);
327
328 if (DEBUG) { System.out.println(" Processing: " + block + "\n"); }
329
330 // visit each predecessor
331 Enumeration<BasicBlock> e = getPrevNodes(block);
332 while (e.hasMoreElements()) {
333 BasicBlock prev = e.nextElement();
334 if (DEBUG) { System.out.println(" Inspecting prev: " + prev); }
335 BasicBlock u = EVAL(prev);
336 // if semi(u) < semi(block) then semi(block) = semi(u)
337 // u may be part of infinite loop and thus, is unreachable from the exit node.
338 // In this case, it will have a semi value of 0. Thus, we screen for it here
339 if (getSemi(u) != 0 && getSemi(u) < getSemi(block)) {
340 blockInfo.setSemiDominator(getSemi(u));
341 }
342 } // while prev
343
344 // add "block" to bucket(vertex(semi(block)));
345 LTDominatorInfo.getInfo(vertex[blockInfo.getSemiDominator()]).
346 addToBucket(block);
347
348 // LINK(parent(block), block)
349 LINK(blockInfo.getParent(), block);
350
351 // foreach block2 in bucket(parent(block)) do
352 java.util.Iterator<BasicBlock> bucketEnum = LTDominatorInfo.getInfo(getParent(block)).getBucketIterator();
353 while (bucketEnum.hasNext()) {
354 BasicBlock block2 = bucketEnum.next();
355
356 // u = EVAL(block2)
357 BasicBlock u = EVAL(block2);
358
359 // if semi(u) < semi(block2) then
360 // dom(block2) = u
361 // else
362 // dom(block2) = parent(block)
363 if (getSemi(u) < getSemi(block2)) {
364 LTDominatorInfo.getInfo(block2).setDominator(u);
365 } else {
366 LTDominatorInfo.getInfo(block2).setDominator(getParent(block));
367 }
368 } // while bucket has more elements
369 } // for DFSCounter .. 1
370 } // method
371
372 /**
373 * This method inspects the passed block and returns the following:
374 * <ul>
375 * <li>block, if block is a root of a tree in the forest
376 * <li>any vertex, u != r such that r is the root of the tree
377 * containing block and semi(u) is minimum on the path r -> v,
378 * otherwise
379 * </ul>
380 * <p>
381 *
382 * See TOPLAS 1(1), July 1979, p 128 for details.
383 *
384 * @param block the block to evaluate
385 * @return the block as described above
386 */
387 private BasicBlock EVAL(BasicBlock block) {
388 if (DEBUG) {
389 System.out.println(" Evaling " + block);
390 }
391 if (getAncestor(block) == null) {
392 return getLabel(block);
393 } else {
394 compress(block);
395 if (getSemi(getLabel(getAncestor(block))) >= getSemi(getLabel(block))) {
396 return getLabel(block);
397 } else {
398 return getLabel(getAncestor(block));
399 }
400 }
401 }
402
403 /**
404 * This recursive method performs the path compression
405 * @param block the block of interest
406 */
407 private void compress(BasicBlock block) {
408 if (getAncestor(getAncestor(block)) != null) {
409 compress(getAncestor(block));
410 LTDominatorInfo blockInfo = LTDominatorInfo.getInfo(block);
411 if (getSemi(getLabel(getAncestor(block))) < getSemi(getLabel(block))) {
412 blockInfo.setLabel(getLabel(getAncestor(block)));
413 }
414 blockInfo.setAncestor(getAncestor(getAncestor(block)));
415 }
416 }
417
418 /**
419 * Adds edge (block1, block2) to the forest maintained as an auxiliary
420 * data structure. This implementation uses path compression and
421 * results in a O(e * alpha(e,n)) complexity, where e is the number of
422 * edges in the CFG and n is the number of nodes.
423 *
424 * @param block1 a basic block corresponding to the source of the new edge
425 * @param block2 a basic block corresponding to the source of the new edge
426 */
427 private void LINK(BasicBlock block1, BasicBlock block2) {
428 if (DEBUG) {
429 System.out.println(" Linking " + block1 + " with " + block2);
430 }
431 BasicBlock s = block2;
432 while (getSemi(getLabel(block2)) < getSemi(getLabel(getChild(s)))) {
433 if (getSize(s) + getSize(getChild(getChild(s))) >= 2 * getSize(getChild(s))) {
434 LTDominatorInfo.getInfo(getChild(s)).setAncestor(s);
435 LTDominatorInfo.getInfo(s).setChild(getChild(getChild(s)));
436 } else {
437 LTDominatorInfo.getInfo(getChild(s)).setSize(getSize(s));
438 LTDominatorInfo.getInfo(s).setAncestor(getChild(s));
439 s = getChild(s);
440 }
441 }
442 LTDominatorInfo.getInfo(s).setLabel(getLabel(block2));
443 LTDominatorInfo.getInfo(block1).setSize(getSize(block1) + getSize(block2));
444 if (getSize(block1) < 2 * getSize(block2)) {
445 BasicBlock tmp = s;
446 s = getChild(block1);
447 LTDominatorInfo.getInfo(block1).setChild(tmp);
448 }
449 while (s != null) {
450 LTDominatorInfo.getInfo(s).setAncestor(block1);
451 s = getChild(s);
452 }
453 if (DEBUG) {
454 System.out.println(" .... done");
455 }
456 }
457
458 /**
459 * This final step sets the final dominator information.
460 */
461 private void step3() {
462 // Visit each node in DFS order, except for the root, which has number 1
463 for (int i = 2; i <= DFSCounter; i++) {
464 BasicBlock block = vertex[i];
465 // if dom(block) != vertex[semi(block)]
466 if (getDom(block) != vertex[getSemi(block)]) {
467 // dom(block) = dom(dom(block))
468 LTDominatorInfo.getInfo(block).setDominator(getDom(getDom(block)));
469 }
470 }
471 }
472
473 //
474 // The following methods are simple helper methods to increase the
475 // readability of the code.
476 //
477
478 /**
479 * Returns the current dominator for the passed block
480 * @param block
481 * @return the domiator for the passed block
482 */
483 private BasicBlock getDom(BasicBlock block) {
484 return LTDominatorInfo.getInfo(block).getDominator();
485 }
486
487 /**
488 * Returns the parent for the passed block
489 * @param block
490 * @return the parent for the passed block
491 */
492 private BasicBlock getParent(BasicBlock block) {
493 return LTDominatorInfo.getInfo(block).getParent();
494 }
495
496 /**
497 * Returns the ancestor for the passed block
498 * @param block
499 * @return the ancestor for the passed block
500 */
501 private BasicBlock getAncestor(BasicBlock block) {
502 return LTDominatorInfo.getInfo(block).getAncestor();
503 }
504
505 /**
506 * returns the label for the passed block or null if the block is null
507 * @param block
508 * @return the label for the passed block or null if the block is null
509 */
510 private BasicBlock getLabel(BasicBlock block) {
511 if (block == null) {
512 return null;
513 }
514 return LTDominatorInfo.getInfo(block).getLabel();
515 }
516
517 /**
518 * Returns the current semidominator for the passed block
519 * @param block
520 * @return the semidominator for the passed block
521 */
522 private int getSemi(BasicBlock block) {
523 if (block == null) {
524 return 0;
525 }
526 return LTDominatorInfo.getInfo(block).getSemiDominator();
527 }
528
529 /**
530 * returns the size associated with the block
531 * @param block
532 * @return the size of the block or 0 if the block is null
533 */
534 private int getSize(BasicBlock block) {
535 if (block == null) {
536 return 0;
537 }
538 return LTDominatorInfo.getInfo(block).getSize();
539 }
540
541 /**
542 * Get the child node for this block
543 * @param block
544 * @return the child node
545 */
546 private BasicBlock getChild(BasicBlock block) {
547 return LTDominatorInfo.getInfo(block).getChild();
548 }
549
550 /**
551 * Print the nodes that dominate each basic block
552 * @param ir the IR
553 */
554 private void printResults(IR ir) {
555 if (forward) {
556 System.out.println("Results of dominators computation for method " + ir.method.getName() + "\n");
557 System.out.println(" Here's the CFG:");
558 System.out.println(ir.cfg);
559 System.out.println("\n\n Here's the Dominator Info:");
560 } else {
561 System.out.println("Results of Post-Dominators computation for method " + ir.method.getName() + "\n");
562 System.out.println(" Here's the CFG:");
563 System.out.println(ir.cfg);
564 System.out.println("\n\n Here's the Post-Dominator Info:");
565 }
566
567 for (Enumeration<BasicBlock> bbEnum = cfg.basicBlocks(); bbEnum.hasMoreElements();) {
568 BasicBlock block = bbEnum.nextElement();
569 // We don't compute a result for the exit node for forward direction
570 if (!forward || !block.isExit()) {
571 System.out.println("Dominators of " + block + ":" + LTDominatorInfo.getInfo(block).dominators(block, ir));
572 }
573 }
574 System.out.println("\n");
575 }
576
577 /**
578 * Print the result of the DFS numbering performed in Step 1
579 */
580 private void printDFSNumbers() {
581 for (Enumeration<BasicBlock> bbEnum = cfg.basicBlocks(); bbEnum.hasMoreElements();) {
582 BasicBlock block = bbEnum.nextElement();
583 // We don't compute a result for the exit node for forward direction
584 if (forward && block.isExit()) {
585 continue;
586 }
587 LTDominatorInfo info = (LTDominatorInfo) block.scratchObject;
588 System.out.println(" " + block + " " + info);
589 }
590 // Visit each node in reverse DFS order, except for the root, which
591 // has number 1
592 for (int i = 1; i <= DFSCounter; i++) {
593 System.out.println(" Vertex: " + i + " " + vertex[i]);
594 }
595 }
596 }