1 /* 2 * Copyright (C) 2007 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.dx.ssa; 18 19 import java.util.ArrayList; 20 import java.util.BitSet; 21 import java.util.HashSet; 22 23 /** 24 * This class computes dominator and post-dominator information using the 25 * Lengauer-Tarjan method. 26 * 27 * See A Fast Algorithm for Finding Dominators in a Flowgraph 28 * T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. 29 * 30 * This implementation runs in time O(n log n). The time bound 31 * could be changed to O(n * ack(n)) with a small change to the link and eval, 32 * and an addition of a child field to the DFS info. In reality, the constant 33 * overheads are high enough that the current method is faster in all but the 34 * strangest artificially constructed examples. 35 * 36 * The basic idea behind this algorithm is to perform a DFS walk, keeping track 37 * of various info about parents. We then use this info to calculate the 38 * dominators, using union-find structures to link together the DFS info, 39 * then finally evaluate the union-find results to get the dominators. 40 * This implementation is m log n because it does not perform union by 41 * rank to keep the union-find tree balanced. 42 */ 43 public final class Dominators { 44 /* postdom is true if we want post dominators */ 45 private final boolean postdom; 46 47 /* {@code non-null;} method being processed */ 48 private final SsaMethod meth; 49 50 /* Method's basic blocks. */ 51 private final ArrayList<SsaBasicBlock> blocks; 52 53 /** indexed by basic block index */ 54 private final DFSInfo[] info; 55 56 private final ArrayList<SsaBasicBlock> vertex; 57 58 /** {@code non-null;} the raw dominator info */ 59 private final DomFront.DomInfo domInfos[]; 60 61 /** 62 * Constructs an instance. 63 * 64 * @param meth {@code non-null;} method to process 65 * @param domInfos {@code non-null;} the raw dominator info 66 * @param postdom true for postdom information, false for normal dom info 67 */ 68 private Dominators(SsaMethod meth, DomFront.DomInfo[] domInfos, 69 boolean postdom) { 70 this.meth = meth; 71 this.domInfos = domInfos; 72 this.postdom = postdom; 73 this.blocks = meth.getBlocks(); 74 this.info = new DFSInfo[blocks.size() + 2]; 75 this.vertex = new ArrayList<SsaBasicBlock>(); 76 } 77 78 /** 79 * Constructs a fully-initialized instance. (This method exists so as 80 * to avoid calling a large amount of code in the constructor.) 81 * 82 * @param meth {@code non-null;} method to process 83 * @param domInfos {@code non-null;} the raw dominator info 84 * @param postdom true for postdom information, false for normal dom info 85 */ 86 public static Dominators make(SsaMethod meth, DomFront.DomInfo[] domInfos, 87 boolean postdom) { 88 Dominators result = new Dominators(meth, domInfos, postdom); 89 90 result.run(); 91 return result; 92 } 93 94 private BitSet getSuccs(SsaBasicBlock block) { 95 if (postdom) { 96 return block.getPredecessors(); 97 } else { 98 return block.getSuccessors(); 99 } 100 } 101 102 private BitSet getPreds(SsaBasicBlock block) { 103 if (postdom) { 104 return block.getSuccessors(); 105 } else { 106 return block.getPredecessors(); 107 } 108 } 109 110 /** 111 * Performs path compress on the DFS info. 112 * 113 * @param in Basic block whose DFS info we are path compressing. 114 */ 115 private void compress(SsaBasicBlock in) { 116 DFSInfo bbInfo = info[in.getIndex()]; 117 DFSInfo ancestorbbInfo = info[bbInfo.ancestor.getIndex()]; 118 119 if (ancestorbbInfo.ancestor != null) { 120 ArrayList<SsaBasicBlock> worklist = new ArrayList<SsaBasicBlock>(); 121 HashSet<SsaBasicBlock> visited = new HashSet<SsaBasicBlock>(); 122 worklist.add(in); 123 124 while (!worklist.isEmpty()) { 125 int wsize = worklist.size(); 126 SsaBasicBlock v = worklist.get(wsize - 1); 127 DFSInfo vbbInfo = info[v.getIndex()]; 128 SsaBasicBlock vAncestor = vbbInfo.ancestor; 129 DFSInfo vabbInfo = info[vAncestor.getIndex()]; 130 131 // Make sure we process our ancestor before ourselves. 132 if (visited.add(vAncestor) && vabbInfo.ancestor != null) { 133 worklist.add(vAncestor); 134 continue; 135 } 136 worklist.remove(wsize - 1); 137 138 // Update based on ancestor info. 139 if (vabbInfo.ancestor == null) { 140 continue; 141 } 142 SsaBasicBlock vAncestorRep = vabbInfo.rep; 143 SsaBasicBlock vRep = vbbInfo.rep; 144 if (info[vAncestorRep.getIndex()].semidom 145 < info[vRep.getIndex()].semidom) { 146 vbbInfo.rep = vAncestorRep; 147 } 148 vbbInfo.ancestor = vabbInfo.ancestor; 149 } 150 } 151 } 152 153 private SsaBasicBlock eval(SsaBasicBlock v) { 154 DFSInfo bbInfo = info[v.getIndex()]; 155 156 if (bbInfo.ancestor == null) { 157 return v; 158 } 159 160 compress(v); 161 return bbInfo.rep; 162 } 163 164 /** 165 * Performs dominator/post-dominator calculation for the control 166 * flow graph. 167 * 168 * @param meth {@code non-null;} method to analyze 169 */ 170 private void run() { 171 SsaBasicBlock root = postdom 172 ? meth.getExitBlock() : meth.getEntryBlock(); 173 174 if (root != null) { 175 vertex.add(root); 176 domInfos[root.getIndex()].idom = root.getIndex(); 177 } 178 179 /* 180 * First we perform a DFS numbering of the blocks, by 181 * numbering the dfs tree roots. 182 */ 183 184 DfsWalker walker = new DfsWalker(); 185 meth.forEachBlockDepthFirst(postdom, walker); 186 187 // the largest semidom number assigned 188 int dfsMax = vertex.size() - 1; 189 190 // Now calculate semidominators. 191 for (int i = dfsMax; i >= 2; --i) { 192 SsaBasicBlock w = vertex.get(i); 193 DFSInfo wInfo = info[w.getIndex()]; 194 195 BitSet preds = getPreds(w); 196 for (int j = preds.nextSetBit(0); 197 j >= 0; 198 j = preds.nextSetBit(j + 1)) { 199 SsaBasicBlock predBlock = blocks.get(j); 200 DFSInfo predInfo = info[predBlock.getIndex()]; 201 202 /* 203 * PredInfo may not exist in case the predecessor is 204 * not reachable. 205 */ 206 if (predInfo != null) { 207 int predSemidom = info[eval(predBlock).getIndex()].semidom; 208 if (predSemidom < wInfo.semidom) { 209 wInfo.semidom = predSemidom; 210 } 211 } 212 } 213 info[vertex.get(wInfo.semidom).getIndex()].bucket.add(w); 214 215 /* 216 * Normally we would call link here, but in our O(m log n) 217 * implementation this is equivalent to the following 218 * single line. 219 */ 220 wInfo.ancestor = wInfo.parent; 221 222 // Implicity define idom for each vertex. 223 ArrayList<SsaBasicBlock> wParentBucket; 224 wParentBucket = info[wInfo.parent.getIndex()].bucket; 225 226 while (!wParentBucket.isEmpty()) { 227 int lastItem = wParentBucket.size() - 1; 228 SsaBasicBlock last = wParentBucket.remove(lastItem); 229 SsaBasicBlock U = eval(last); 230 if (info[U.getIndex()].semidom 231 < info[last.getIndex()].semidom) { 232 domInfos[last.getIndex()].idom = U.getIndex(); 233 } else { 234 domInfos[last.getIndex()].idom = wInfo.parent.getIndex(); 235 } 236 } 237 } 238 239 // Now explicitly define the immediate dominator of each vertex 240 for (int i = 2; i <= dfsMax; ++i) { 241 SsaBasicBlock w = vertex.get(i); 242 if (domInfos[w.getIndex()].idom 243 != vertex.get(info[w.getIndex()].semidom).getIndex()) { 244 domInfos[w.getIndex()].idom 245 = domInfos[domInfos[w.getIndex()].idom].idom; 246 } 247 } 248 } 249 250 /** 251 * Callback for depth-first walk through control flow graph (either 252 * from the entry block or the exit block). Records the traversal order 253 * in the {@code info}list. 254 */ 255 private class DfsWalker implements SsaBasicBlock.Visitor { 256 private int dfsNum = 0; 257 258 @Override 259 public void visitBlock(SsaBasicBlock v, SsaBasicBlock parent) { 260 DFSInfo bbInfo = new DFSInfo(); 261 bbInfo.semidom = ++dfsNum; 262 bbInfo.rep = v; 263 bbInfo.parent = parent; 264 vertex.add(v); 265 info[v.getIndex()] = bbInfo; 266 } 267 } 268 269 private static final class DFSInfo { 270 public int semidom; 271 public SsaBasicBlock parent; 272 273 /** 274 * rep(resentative) is known as "label" in the paper. It is the node 275 * that our block's DFS info has been unioned to. 276 */ 277 public SsaBasicBlock rep; 278 279 public SsaBasicBlock ancestor; 280 public ArrayList<SsaBasicBlock> bucket; 281 282 public DFSInfo() { 283 bucket = new ArrayList<SsaBasicBlock>(); 284 } 285 } 286 } 287
