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.compilers.opt.OperationNotImplementedException;
018 import org.jikesrvm.compilers.opt.dfsolver.DF_LatticeCell;
019 import org.jikesrvm.compilers.opt.dfsolver.DF_Solution;
020 import org.jikesrvm.compilers.opt.ir.BasicBlock;
021 import org.jikesrvm.compilers.opt.ir.IR;
022
023 /**
024 * Calculate dominators for basic blocks.
025 * <p> Uses the algorithm contained in Dragon book, pg. 670-1.
026 * <pre>
027 * D(n0) := { n0 }
028 * for n in N - { n0 } do D(n) := N;
029 * while changes to any D(n) occur do
030 * for n in N - {n0} do
031 * D(n) := {n} U (intersect of D(p) over all predecessors p of n)
032 * </pre>
033 * <p> TODO: we do not support IRs with exception handlers!!
034 */
035 public class Dominators {
036 /**
037 * Control for debug output
038 */
039 static final boolean DEBUG = false;
040 /**
041 * Should we compute post-dominators instead of dominators? This is
042 * false by default.
043 */
044 static boolean COMPUTE_POST_DOMINATORS = false;
045
046 /**
047 * Calculate the dominators for an IR.
048 * <p> After this pass, each basic block's scrach field points to
049 * an <code> DominatorInfo </code> object, which holds the dominators
050 * of the basic block.
051 *
052 * @param ir the IR in question
053 */
054 public static void perform(IR ir) {
055 if (ir.hasReachableExceptionHandlers()) {
056 throw new OperationNotImplementedException("IR with exception handlers");
057 }
058 DominatorSystem system = new DominatorSystem(ir);
059 if (DEBUG) {
060 System.out.print("Solving...");
061 }
062 if (DEBUG) {
063 System.out.println(system);
064 }
065 system.solve();
066 if (DEBUG) {
067 System.out.println("done");
068 }
069 DF_Solution solution = system.getSolution();
070 if (DEBUG) {
071 System.out.println("Dominator Solution :" + solution);
072 }
073 if (DEBUG) {
074 System.out.print("Updating blocks ...");
075 }
076 updateBlocks(solution);
077 if (DEBUG) {
078 System.out.println("done.");
079 }
080 if (ir.options.PRINT_DOMINATORS) {
081 printDominators(ir);
082 }
083 }
084
085 /**
086 * Calculate the "approximate" dominators for an IR i.e., the
087 * dominators in the factored CFG rather than the normal CFG.
088 * <p> (No exception is thrown if the input IR has handler blocks.)
089 *
090 * <p> After this pass, each basic block's scratch field points to
091 * an DominatorInfo object, which holds the dominators
092 * of the basic block.
093 *
094 * @param ir the IR in question
095 */
096 public static void computeApproxDominators(IR ir) {
097 DominatorSystem system = new DominatorSystem(ir);
098 if (DEBUG) {
099 System.out.print("Solving...");
100 }
101 if (DEBUG) {
102 System.out.println(system);
103 }
104 system.solve();
105 if (DEBUG) {
106 System.out.println("done");
107 }
108 DF_Solution solution = system.getSolution();
109 if (DEBUG) {
110 System.out.println("Dominator Solution :" + solution);
111 }
112 if (DEBUG) {
113 System.out.print("Updating blocks ...");
114 }
115 updateBlocks(solution);
116 if (DEBUG) {
117 System.out.println("done.");
118 }
119 if (ir.options.PRINT_DOMINATORS) {
120 printDominators(ir);
121 }
122 }
123
124 /**
125 * Calculate the postdominators for an IR.
126 * <p> After this pass, each basic block's scrach field points to
127 * an DominatorInfo object, which holds the postdominators
128 * of the basic block.
129 *
130 * @param ir the IR in question
131 */
132 public static void computeApproxPostdominators(IR ir) {
133 Dominators.COMPUTE_POST_DOMINATORS = true;
134 DominatorSystem system = new DominatorSystem(ir);
135 if (DEBUG) {
136 System.out.print("Solving...");
137 }
138 if (DEBUG) {
139 System.out.println(system);
140 }
141 system.solve();
142 if (DEBUG) {
143 System.out.println("done");
144 }
145 DF_Solution solution = system.getSolution();
146 if (DEBUG) {
147 System.out.println("Postdominator Solution :" + solution);
148 }
149 if (DEBUG) {
150 System.out.print("Updating blocks ...");
151 }
152 updateBlocks(solution);
153 if (DEBUG) {
154 System.out.println("done.");
155 }
156 if (ir.options.PRINT_DOMINATORS) {
157 printDominators(ir);
158 }
159 Dominators.COMPUTE_POST_DOMINATORS = false;
160 }
161
162 /**
163 * For each basic block in the data flow system solution,
164 * create an <code> DominatorInfo </code> and store it in the basic
165 * blocks scratchObject
166 *
167 * @param solution the solution to the Dominators equations
168 */
169 public static void updateBlocks(DF_Solution solution) {
170 for (final DF_LatticeCell latticeCell : solution.values()) {
171 DominatorCell cell = (DominatorCell) latticeCell;
172 BasicBlock b = cell.block;
173 b.scratchObject = new DominatorInfo(cell.dominators);
174 if (DEBUG) {
175 System.out.println("Dominators of " + b + ":" + cell.dominators);
176 }
177 }
178 }
179
180 /**
181 * Print the (already calculated) dominators.
182 * @param ir the IR
183 */
184 public static void printDominators(IR ir) {
185 for (Enumeration<BasicBlock> e = ir.getBasicBlocks(); e.hasMoreElements();) {
186 BasicBlock b = e.nextElement();
187 DominatorInfo i = (DominatorInfo) b.scratchObject;
188 System.out.println("Dominators of " + b + ":" + i.dominators);
189 }
190 }
191 }