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.ir.BasicBlock;
018 import org.jikesrvm.compilers.opt.ir.IR;
019 import org.jikesrvm.compilers.opt.util.Tree;
020 import org.jikesrvm.compilers.opt.util.TreeNode;
021 import org.jikesrvm.util.BitVector;
022
023 /**
024 * This class provides the abstraction of a dominator tree
025 *
026 * <p>TODO: we do not support IRs with exception handlers.
027 */
028 public class DominatorTree extends Tree {
029 /**
030 * {@code true} if we are computing regular dominators, {@code false} for post-dominators
031 */
032 private final boolean forward;
033
034 /**
035 * The governing IR
036 */
037 private final IR ir;
038
039 /**
040 * A structure used to quickly index into the DominatorVertex tree
041 */
042 private DominatorTreeNode[] dominatorInfoMap;
043
044 /**
045 * Build a dominator tree from an IR. NOTE: the dominator
046 * information MUST be computed BEFORE calling this method!
047 * We assume the scratch object of each basic block contains
048 * the LTDominatorInfo object holding this information.
049 *
050 * @param ir the governing IR
051 * @param forward are we building regular dominators or post-dominators?
052 */
053 public static void perform(IR ir, boolean forward) {
054 // control for debugging messages.
055 final boolean DEBUG = false;
056
057 if (forward) {
058 ir.HIRInfo.dominatorTree = new DominatorTree(ir, forward);
059 if (ir.options.PRINT_DOMINATORS) {
060 if (DEBUG) {
061 System.out.println("Here is the CFG for method " + ir.method.getName() + "\n" + ir.cfg);
062 }
063 System.out.println("Here is the Dominator Tree for method " +
064 ir.method.getName() + "\n" +
065 ir.HIRInfo.dominatorTree);
066 }
067 } else {
068 ir.HIRInfo.postDominatorTree = new DominatorTree(ir, forward);
069 if (ir.options.PRINT_POST_DOMINATORS) {
070 if (DEBUG) {
071 System.out.println("Here is the CFG for method " + ir.method.getName() + "\n" + ir.cfg);
072 }
073 System.out.println("Here is the Post-Dominator Tree for method " +
074 ir.method.getName() + "\n" +
075 ir.HIRInfo.postDominatorTree);
076 }
077 }
078 }
079
080 /**
081 * Build a dominator tree from an IR. NOTE: the dominator
082 * information MUST be computed BEFORE calling this
083 * constructor!
084 *
085 * @param ir the governing IR
086 * @param forward are we building regular dominators or post-dominators?
087 */
088 public DominatorTree(IR ir, boolean forward) {
089 this.ir = ir;
090 this.forward = forward;
091
092 // The query methods of dominator information, such as
093 // getDominanceFrontier, dominates, and domFrontierEnumerator
094 // all use ir.getBasicBlock(int). This method relies on
095 // the basic block map being up to date. Here we ensure this
096 // property, even though it is needed for computing the dominator
097 // tree.
098 ir.resetBasicBlockMap();
099
100 // allocate the dominator vertex map
101 dominatorInfoMap = new DominatorTreeNode[ir.getMaxBasicBlockNumber() + 1];
102
103 // allocate the tree and root node
104 // Step 1: add all basic blocks to the tree as nodes
105 for (Enumeration<BasicBlock> bbEnum = ir.cfg.basicBlocks(); bbEnum.hasMoreElements();) {
106 BasicBlock block = bbEnum.nextElement();
107 // We treat the exit node as not being part of the CFG
108 if (!forward || !block.isExit()) {
109 addNode(block);
110 }
111 }
112
113 // Step 2: set the root value
114 setRoot(dominatorInfoMap[getFirstNode().getNumber()]);
115
116 // Step 3: Walk the nodes, for each node create link with parent
117 // Leaf nodes have no links to add
118 for (Enumeration<BasicBlock> bbEnum = ir.cfg.basicBlocks(); bbEnum.hasMoreElements();) {
119 BasicBlock block = bbEnum.nextElement();
120 // skip the exit node
121 if (forward && block.isExit()) {
122 continue;
123 }
124
125 // get the tree node corresponding to "block"
126 DominatorTreeNode blockNode = dominatorInfoMap[block.getNumber()];
127
128 // if parent = null, this is the root of the tree, nothing to do
129 if (LTDominatorInfo.getInfo(block) == null) {
130 System.out.println("info field is null for block: " + block);
131 }
132 BasicBlock parent = LTDominatorInfo.getInfo(block).getDominator();
133 if (parent != null) {
134 DominatorTreeNode parentNode = dominatorInfoMap[parent.getNumber()];
135
136 // tell the parent they have a child
137 parentNode.addChild(blockNode);
138 }
139 } // for loop
140 } // method
141
142 /**
143 * Get the first node, either entry or exit
144 * depending on which way we are viewing the graph
145 * @return the entry node or exit node
146 */
147 private BasicBlock getFirstNode() {
148 if (forward) {
149 return ir.cfg.entry();
150 } else {
151 return ir.cfg.exit();
152 }
153 }
154
155 /**
156 * Enumerate the children of the vertex corresponding to a basic
157 * block
158 *
159 * @param bb the basic block
160 * @return an Enumeration of bb's children
161 */
162 public Enumeration<TreeNode> getChildren(BasicBlock bb) {
163 DominatorTreeNode node = dominatorInfoMap[bb.getNumber()];
164 return node.getChildren();
165 }
166
167 /**
168 * Return the parent of the vertex corresponding to a basic
169 * block
170 *
171 * @param bb the basic block
172 * @return bb's parent
173 */
174 public BasicBlock getParent(BasicBlock bb) {
175 DominatorTreeNode node = dominatorInfoMap[bb.getNumber()];
176 return ((DominatorTreeNode) node.getParent()).getBlock();
177 }
178
179 /**
180 * Return the (already calculated) dominance frontier for
181 * a basic block
182 *
183 * @param bb the basic block
184 * @return a BitVector representing the dominance frontier
185 */
186 public BitVector getDominanceFrontier(BasicBlock bb) {
187 DominatorTreeNode info = dominatorInfoMap[bb.getNumber()];
188 return info.getDominanceFrontier();
189 }
190
191 /**
192 * Return the (already calculated) dominance frontier for
193 * a basic block
194 *
195 * @param number the number of the basic block
196 * @return a BitVector representing the dominance frontier
197 */
198 public BitVector getDominanceFrontier(int number) {
199 return getDominanceFrontier(ir.getBasicBlock(number));
200 }
201
202 /**
203 * Does basic block number b dominate all basic blocks in a set?
204 *
205 * @param b the number of the basic block to test
206 * @param bits BitVector representation of the set of basic blocks to test
207 * @return true or false
208 */
209 public boolean dominates(int b, BitVector bits) {
210 for (int i = 0; i < bits.length(); i++) {
211 if (!bits.get(i)) {
212 continue;
213 }
214 if (!dominates(b, i)) {
215 return false;
216 }
217 }
218 return true;
219 }
220
221 /**
222 * Does basic block number "master" dominate basic block number "slave"?
223 *
224 * @param master the number of the proposed "master" basic block
225 * @param slave the number of the proposed "slave block
226 * @return "master dominates slave"
227 */
228 public boolean dominates(int master, int slave) {
229 BasicBlock masterBlock = ir.getBasicBlock(master);
230 BasicBlock slaveBlock = ir.getBasicBlock(slave);
231 DominatorTreeNode masterNode = dominatorInfoMap[masterBlock.getNumber()];
232 DominatorTreeNode slaveNode = dominatorInfoMap[slaveBlock.getNumber()];
233 return slaveNode.isDominatedBy(masterNode);
234 }
235
236 /**
237 * Does basic block number "master" dominate basic block number "slave"?
238 *
239 * @param master the number of the proposed "master" basic block
240 * @param slave the number of the proposed "slave block
241 * @return "master dominates slave"
242 */
243 public boolean dominates(BasicBlock master, BasicBlock slave) {
244 DominatorTreeNode masterNode = dominatorInfoMap[master.getNumber()];
245 DominatorTreeNode slaveNode = dominatorInfoMap[slave.getNumber()];
246 return slaveNode.isDominatedBy(masterNode);
247 }
248
249 /**
250 * Creates dominator tree nodes for the passed block and adds them to the
251 * map.
252 * @param b the basic block
253 */
254 private void addNode(BasicBlock b) {
255 DominatorTreeNode node = new DominatorTreeNode(b);
256 dominatorInfoMap[b.getNumber()] = node;
257 }
258
259 /**
260 * Return the distance from the root of the dominator tree to a given
261 * basic block
262 *
263 * @param b the basic block in question
264 * @return <code>b</code>'s depth
265 */
266 public int depth(BasicBlock b) {
267 return dominatorInfoMap[b.getNumber()].getDepth();
268 }
269
270 /**
271 * Return the deepest common dominance ancestor of blocks <code>a</code> and <code>b</code>
272 *
273 * @param a The first basic block
274 * @param b The second basic block
275 * @return the deepest common dominance ancestor of blocks <code>a</code>
276 * and <code>b</code>
277 */
278 public BasicBlock deepestCommonAncestor(BasicBlock a, BasicBlock b) {
279 DominatorTreeNode n_a = dominatorInfoMap[a.getNumber()];
280 DominatorTreeNode n_b = dominatorInfoMap[b.getNumber()];
281 while (n_a != n_b) {
282 if (n_a.getDepth() > n_b.getDepth()) {
283 n_a = (DominatorTreeNode) n_a.getParent();
284 } else {
285 n_b = (DominatorTreeNode) n_b.getParent();
286 }
287 }
288 return n_a.getBlock();
289 }
290
291 }