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