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.TreeNode;
020 import org.jikesrvm.util.BitVector;
021
022 /**
023 * This class implements a node in the dominator tree.
024 *
025 * <p> TODO: we do not support IRs with exception handlers!!
026 */
027 public class DominatorTreeNode extends TreeNode {
028
029 /**
030 * the basic block this node represents
031 */
032 private final BasicBlock block;
033
034 /**
035 * distance from the root of the dominator tree, lazily initialized (-1 => not
036 * initialized)
037 */
038 private int depth = -1;
039
040 /**
041 * representation of the dominance frontier for this node
042 */
043 private BitVector dominanceFrontier;
044
045 /**
046 * the cache to hold the set of nodes that dominate this one. This is
047 * computed on demand by walking up the tree.
048 */
049 BitVector dominators;
050
051 /**
052 * lower bound of dominated nodes range
053 */
054 private int low = 0;
055
056 /**
057 * upper bound of dominated nodes range
058 */
059 private int high = 0;
060
061 /**
062 * Construct a dominator tree node for a given basic block.
063 * @param block the basic block
064 */
065 DominatorTreeNode(BasicBlock block) {
066 this.block = block;
067 }
068
069 /**
070 * Get the basic block for this dominator tree node
071 * @return the basic block
072 */
073 public BasicBlock getBlock() {
074 return block;
075 }
076
077 /**
078 * Return the distance of this node from the root of the dominator tree.
079 * @return the distance of this node from the root of the dominator tree.
080 */
081 int getDepth() {
082 if (depth == -1) {
083 DominatorTreeNode dad = (DominatorTreeNode) getParent();
084 if (dad == null) {
085 depth = 0;
086 } else {
087 depth = dad.getDepth() + 1;
088 }
089 }
090 return depth;
091 }
092
093 /**
094 * Return a bit set representing the dominance frontier for this node
095 * @return a bit set representing the dominance frontier for this node
096 */
097 BitVector getDominanceFrontier() {
098 return dominanceFrontier;
099 }
100
101 /**
102 * Set a bit set representing the dominance frontier for this node
103 * @param set the bit set
104 */
105 void setDominanceFrontier(BitVector set) {
106 dominanceFrontier = set;
107 }
108
109 /**
110 * Return a string representation of the dominance frontier for this
111 * node.
112 * @return a string representation of the dominance frontier for this
113 * node
114 */
115 String dominanceFrontierString() {
116 return dominanceFrontier.toString();
117 }
118
119 /**
120 * This method returns the set of blocks that dominates the passed
121 * block, i.e., it answers the question "Who dominates me?"
122 *
123 * @param ir the governing IR
124 * @return a BitVector containing those blocks that dominate me
125 */
126 BitVector dominators(IR ir) {
127 // Currently, this set is computed on demand,
128 // but we cache it for the next time.
129 if (dominators == null) {
130 dominators = new BitVector(ir.getMaxBasicBlockNumber() + 1);
131 dominators.set(block.getNumber());
132 DominatorTreeNode node = this;
133 while ((node = (DominatorTreeNode) getParent()) != null) {
134 dominators.set(node.getBlock().getNumber());
135 }
136 }
137 return dominators;
138 }
139
140 /**
141 * This method returns true if the passed node dominates this node
142 * @param master the proposed dominating node
143 * @return whether the passed node dominates me
144 */
145 boolean _isDominatedBy(DominatorTreeNode master) {
146 DominatorTreeNode node = this;
147 while ((node != null) && (node != master)) {
148 node = (DominatorTreeNode) node.getParent();
149 }
150 return node == master;
151 }
152
153 /**
154 * This method returns true if the passed node dominates this node
155 * @param master the proposed dominating node
156 * @return whether the passed node dominates me
157 */
158 boolean isDominatedBy(DominatorTreeNode master) {
159 if (low == 0) initializeRanges();
160 return master.low <= low && master.high >= high;
161 }
162
163 private void initializeRanges() {
164 DominatorTreeNode node = this;
165 DominatorTreeNode parent = (DominatorTreeNode) getParent();
166 while (parent != null) {
167 node = parent;
168 parent = (DominatorTreeNode) node.getParent();
169 }
170 node.initializeRanges(0);
171 }
172
173 private int initializeRanges(int i) {
174 low = ++i;
175 Enumeration<TreeNode> childEnum = getChildren();
176 while (childEnum.hasMoreElements()) {
177 DominatorTreeNode child = (DominatorTreeNode) childEnum.nextElement();
178 i = child.initializeRanges(i);
179 }
180 high = ++i;
181 return i;
182 }
183
184 /**
185 * Enumerate the basic blocks in the dominance frontier for this node.
186 * @param ir the governing IR
187 * @return an enumeration of the basic blocks in the dominance frontier
188 * for this node.
189 */
190 Enumeration<BasicBlock> domFrontierEnumerator(IR ir) {
191 return ir.getBasicBlocks(dominanceFrontier);
192 }
193
194 /**
195 * String-i-fies the node
196 * @return the node as a string
197 */
198 @Override
199 public final String toString() {
200 StringBuilder sb = new StringBuilder();
201 sb.append(block);
202 sb.append(" (").append(low).append(", ").append(high).append(")");
203 return sb.toString();
204 }
205 }
206
207
208