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