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 import java.util.HashSet;
017 import java.util.Iterator;
018 import org.jikesrvm.compilers.opt.ir.BasicBlock;
019 import org.jikesrvm.compilers.opt.ir.IR;
020 import org.jikesrvm.util.BitVector;
021
022 /**
023 * This class holds data associated with a basic block as computed by the
024 * Lengauer-Tarjan dominator calculation.
025 * @see LTDominators
026 */
027 class LTDominatorInfo {
028 static final boolean DEBUG = false;
029
030 private int semiDominator;
031 /** the immediate dominator */
032 private BasicBlock dominator;
033 private BasicBlock parent;
034 private final HashSet<BasicBlock> bucket;
035 private BasicBlock label;
036 private BasicBlock ancestor;
037 // Used to keep the trees balanced, during path compression
038 private int size;
039 private BasicBlock child;
040
041 // used to capture activation record state to avoid the use of recursion
042 // in Step 1 of the LT algorithm
043 // A null value will signal that we have not started to process this
044 // block, otherwise, we'll skip the (redundant)
045 // initialization step for the block
046 // See LTDominators.DFS() for details
047 private Enumeration<BasicBlock> bbEnum;
048
049 /**
050 * @param block the basic block this info is associated with
051 */
052 LTDominatorInfo(BasicBlock block) {
053 semiDominator = 0;
054 dominator = null;
055 parent = null;
056 bucket = new HashSet<BasicBlock>();
057 ancestor = null;
058 label = block;
059 size = 1;
060 child = null;
061 bbEnum = null;
062 }
063
064 /**
065 * This method returns the set of blocks that dominates the passed
066 * block, i.e., it answers the question "Who dominates me?"
067 *
068 * @param block the block of interest
069 * @param ir the governing ir
070 * @return a BitVector containing those blocks that dominate the passed one
071 */
072 public BitVector dominators(BasicBlock block, IR ir) {
073 // Currently this set is computed on demand. We may want to cache
074 // the result for reuse. The cost of computing is the height of the
075 // the dominator tree.
076 BitVector dominators = new BitVector(ir.getMaxBasicBlockNumber() + 1);
077 dominators.set(block.getNumber());
078 while ((block = getIdom(block)) != null) {
079 dominators.set(block.getNumber());
080 }
081 return dominators;
082 }
083
084 /**
085 * This method determines if the 1st parameter (block) is dominated by
086 * the 2nd parameter (master), i.e., must control pass through "master"
087 * before reaching "block"
088 *
089 * @param block the block we care about
090 * @param master the potential dominating block
091 * @return whether master dominates block
092 */
093 public static boolean isDominatedBy(BasicBlock block, BasicBlock master) {
094 if (block == master) {
095 return true;
096 }
097 // walk up the dominator tree looking for the passed block
098 block = getIdom(block);
099 while (block != null && block != master) {
100 block = getIdom(block);
101 }
102 // If we found the master, the condition is true
103 return block == master;
104 }
105
106 /**
107 * Sets the semidominator for this node
108 * @param value the new value
109 */
110 public void setSemiDominator(int value) {
111 semiDominator = value;
112 }
113
114 /**
115 * Returns the semidomintor for this node
116 * @return the semidomintor for this node
117 */
118 public int getSemiDominator() {
119 return semiDominator;
120 }
121
122 /**
123 * Sets the immediate dominator for this node
124 * @param value the value to set
125 */
126 public void setDominator(BasicBlock value) {
127 dominator = value;
128 }
129
130 /**
131 * Returns the immediate dominator for this node
132 * @return the immediate dominator for this node
133 */
134 public BasicBlock getDominator() {
135 return dominator;
136 }
137
138 /**
139 * Sets the parent of this block
140 * @param value the value
141 */
142 public void setParent(BasicBlock value) {
143 parent = value;
144 }
145
146 /**
147 * Returns the parent of this block
148 * @return the parent of this block
149 */
150 public BasicBlock getParent() {
151 return parent;
152 }
153
154 /**
155 * Returns an iterator over this block's bucket
156 * @return an iterator over this block's bucket
157 */
158 public Iterator<BasicBlock> getBucketIterator() {
159 return bucket.iterator();
160 }
161
162 /**
163 * Removes the passed block from the bucket for this node
164 * @param block the block to remove from the bucket
165 */
166 public void removeFromBucket(BasicBlock block) {
167 bucket.remove(block);
168 }
169
170 /**
171 * Adds the passed block from the bucket for this node
172 * @param block the block to add to our bucket
173 */
174 public void addToBucket(BasicBlock block) {
175 bucket.add(block);
176 }
177
178 /**
179 * Sets the ancestor for the value passed
180 * @param value the ancestor value
181 */
182 public void setAncestor(BasicBlock value) {
183 ancestor = value;
184 }
185
186 /**
187 * Returns the ancestor for this block
188 * @return the ancestor for this block
189 */
190 public BasicBlock getAncestor() {
191 return ancestor;
192 }
193
194 /**
195 * sets the label
196 * @param value the label
197 */
198 public void setLabel(BasicBlock value) {
199 label = value;
200 }
201
202 /**
203 * returns the label
204 * @return the label
205 */
206 public BasicBlock getLabel() {
207 return label;
208 }
209
210 /**
211 * sets the size
212 * @param value the size
213 */
214 public void setSize(int value) {
215 size = value;
216 }
217
218 /**
219 * returns the size
220 * @return the size
221 */
222 public int getSize() {
223 return size;
224 }
225
226 /**
227 * sets the child field
228 * @param value the child value
229 */
230 public void setChild(BasicBlock value) {
231 child = value;
232 }
233
234 /**
235 * returns the child
236 * @return the child
237 */
238 public BasicBlock getChild() {
239 return child;
240 }
241
242 /**
243 * Helper method to return the Info field associated with a block
244 * @return the basic block enumeration, could be null
245 */
246 public Enumeration<BasicBlock> getEnum() {
247 return bbEnum;
248 }
249
250 /**
251 * set the basic block enum field
252 * @param bbEnum basic block enum
253 */
254 public void setEnum(Enumeration<BasicBlock> bbEnum) {
255 this.bbEnum = bbEnum;
256 }
257
258 /**
259 * Helper method to return the Info field associated with a block
260 * @param block the block of interest
261 * @return the LTInfo info
262 */
263 public static LTDominatorInfo getInfo(BasicBlock block) {
264 return (LTDominatorInfo) block.scratchObject;
265 }
266
267 /**
268 * return the immediate dominator of a basic block.
269 * Note: the dominator info must be pre-calculated
270 * @param bb the basic block in question
271 * @return bb's immediate dominator
272 */
273 public static BasicBlock getIdom(BasicBlock bb) {
274 return getInfo(bb).dominator;
275 }
276
277 /**
278 * Prints a string version of objection
279 */
280 @Override
281 public String toString() {
282 return super.toString() + " [Parent: " + parent + " SDom: " + semiDominator + " Dom: " + dominator + "]";
283 }
284 }