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.OptOptions;
018 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
019 import org.jikesrvm.compilers.opt.ir.BasicBlock;
020 import org.jikesrvm.compilers.opt.ir.IR;
021 import org.jikesrvm.compilers.opt.util.TreeNode;
022 import org.jikesrvm.util.BitVector;
023
024 /**
025 * Calculate dominance frontier for a set of basic blocks.
026 *
027 * <p> Uses the algorithm of Cytron et al., TOPLAS Oct. 91:
028 *
029 * <pre>
030 * for each X in a bottom-up traversal of the dominator tree do
031 *
032 * DF(X) < - null
033 * for each Y in Succ(X) do
034 * if (idom(Y)!=X) then DF(X) <- DF(X) U Y
035 * end
036 * for each Z in {idom(z) = X} do
037 * for each Y in DF(Z) do
038 * if (idom(Y)!=X) then DF(X) <- DF(X) U Y
039 * end
040 * end
041 * </pre>
042 *
043 * <p> TODO: we do not support IRs with exception handlers!!
044 */
045 public class DominanceFrontier extends CompilerPhase {
046 /**
047 * Should this phase be performed? This is a member of a composite
048 * phase, so always return {@code true}. The parent composite phase will
049 * dictate.
050 * @param options controlling compiler options
051 * @return {@code true}
052 */
053 @Override
054 public final boolean shouldPerform(OptOptions options) {
055 return true;
056 }
057
058 /**
059 * Return this instance of this phase. This phase contains no
060 * per-compilation instance fields.
061 * @param ir not used
062 * @return this
063 */
064 @Override
065 public CompilerPhase newExecution(IR ir) {
066 return this;
067 }
068
069 /**
070 * Return a String representation for this phase
071 * @return a String representation for this phase
072 */
073 @Override
074 public final String getName() {
075 return "Dominance Frontier";
076 }
077
078 /**
079 * Should the IR be printed either before or after performing this phase?
080 *
081 * @param options controlling compiler options
082 * @param before {@code true} iff querying before the phase
083 * @return {@code false}
084 */
085 @Override
086 public final boolean printingEnabled(OptOptions options, boolean before) {
087 return false;
088 }
089
090 /**
091 * Calculate the dominance frontier for each basic block in the
092 * CFG. Stores the result in the DominatorTree for the governing
093 * IR.
094 *
095 * <p> NOTE: The dominator tree MUST be calculated BEFORE calling this
096 * routine.
097 *
098 * @param ir the governing IR
099 */
100 @Override
101 public void perform(IR ir) {
102 final boolean DEBUG = false;
103 // make sure the dominator computation completed successfully
104 if (!ir.HIRInfo.dominatorsAreComputed) {
105 return;
106 }
107 // make sure dominator tree is computed
108 if (ir.HIRInfo.dominatorTree == null) {
109 return;
110 }
111 // for each X in a bottom-up traversal of the dominator tree do
112 DominatorTree tree = ir.HIRInfo.dominatorTree;
113 for (Enumeration<TreeNode> x = tree.getBottomUpEnumerator(); x.hasMoreElements();) {
114 DominatorTreeNode v = (DominatorTreeNode) x.nextElement();
115 BasicBlock X = v.getBlock();
116 if (DEBUG) {
117 System.out.println("Computing frontier for node " + X);
118 }
119 BitVector DF = new BitVector(ir.getMaxBasicBlockNumber() + 1);
120 v.setDominanceFrontier(DF);
121 // for each Y in Succ(X) do
122 for (Enumeration<BasicBlock> y = X.getOut(); y.hasMoreElements();) {
123 BasicBlock Y = y.nextElement();
124 // skip EXIT node
125 if (Y.isExit()) {
126 continue;
127 }
128 // if (idom(Y)!=X) then DF(X) <- DF(X) U Y
129 if (LTDominatorInfo.getIdom(Y) != X) {
130 DF.set(Y.getNumber());
131 }
132 }
133 if (DEBUG) {
134 System.out.println("After local " + DF);
135 }
136 // for each Z in {idom(z) = X} do
137 for (Enumeration<TreeNode> z = tree.getChildren(X); z.hasMoreElements();) {
138 DominatorTreeNode zVertex = (DominatorTreeNode) z.nextElement();
139 BasicBlock Z = zVertex.getBlock();
140 if (DEBUG) {
141 System.out.println("Processing Z = " + Z);
142 }
143 // for each Y in DF(Z) do
144 for (Enumeration<BasicBlock> y = zVertex.domFrontierEnumerator(ir); y.hasMoreElements();) {
145 BasicBlock Y = y.nextElement();
146 // if (idom(Y)!=X) then DF(X) <- DF(X) U Y
147 if (LTDominatorInfo.getIdom(Y) != X) {
148 DF.set(Y.getNumber());
149 }
150 }
151 }
152 if (DEBUG) {
153 System.out.println("After up " + DF);
154 }
155 }
156 if (DEBUG) {
157 for (Enumeration<BasicBlock> bbEnum = ir.cfg.basicBlocks(); bbEnum.hasMoreElements();) {
158 BasicBlock block = bbEnum.nextElement();
159 if (block.isExit()) {
160 continue;
161 }
162 System.out.println(block + " DF: " + tree.getDominanceFrontier(block));
163 }
164 }
165 }
166
167 /**
168 * Calculate the dominance frontier for the set of basic blocks
169 * represented by a BitVector.
170 *
171 * <p> NOTE: The dominance frontiers for the IR MUST be calculated
172 * BEFORE calling this routine.
173 *
174 * @param ir the governing IR
175 * @param bits the BitVector representing the set of basic blocks
176 * @return a BitVector representing the dominance frontier for the set
177 */
178 public static BitVector getDominanceFrontier(IR ir, BitVector bits) {
179 BitVector result = new BitVector(ir.getMaxBasicBlockNumber() + 1);
180 DominatorTree dTree = ir.HIRInfo.dominatorTree;
181 for (int i = 0; i < bits.length(); i++) {
182 if (bits.get(i)) {
183 result.or(dTree.getDominanceFrontier(i));
184 }
185 }
186 return result;
187 }
188
189 /**
190 * Calculate the iterated dominance frontier for a set of basic blocks
191 * represented by a BitVector.
192 *
193 * <p> NOTE: The dominance frontiers for the IR MUST be calculated
194 * BEFORE calling this routine.
195 *
196 * @param ir The governing IR
197 * @param S The {@link BitVector} representing the set of basic blocks
198 * @return an {@link BitVector} representing the dominance frontier for
199 * the set
200 */
201 public static BitVector getIteratedDominanceFrontier(IR ir, BitVector S) {
202 BitVector DFi = getDominanceFrontier(ir, S);
203 while (true) {
204 BitVector DFiplus1 = getDominanceFrontier(ir, DFi);
205 DFiplus1.or(DFi);
206 if (DFi.equals(DFiplus1)) {
207 break;
208 }
209 DFi = DFiplus1;
210 }
211 return DFi;
212 }
213 }
214
215
216