1579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/* 2579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Copyright (C) 2007 The Android Open Source Project 3579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 4579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * you may not use this file except in compliance with the License. 6579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * You may obtain a copy of the License at 7579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 8579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 10579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See the License for the specific language governing permissions and 14579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * limitations under the License. 15579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 16579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 17579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpackage com.android.dx.ssa; 18579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 19579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.ArrayList; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.BitSet; 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.HashSet; 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * This class computes dominator and post-dominator information using the 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Lengauer-Tarjan method. 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See A Fast Algorithm for Finding Dominators in a Flowgraph 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * This implementation runs in time O(n log n). The time bound 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * could be changed to O(n * ack(n)) with a small change to the link and eval, 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * and an addition of a child field to the DFS info. In reality, the constant 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * overheads are high enough that the current method is faster in all but the 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * strangest artificially constructed examples. 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * The basic idea behind this algorithm is to perform a DFS walk, keeping track 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * of various info about parents. We then use this info to calculate the 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * dominators, using union-find structures to link together the DFS info, 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * then finally evaluate the union-find results to get the dominators. 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * This implementation is m log n because it does not perform union by 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * rank to keep the union-find tree balanced. 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic final class Dominators { 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* postdom is true if we want post dominators */ 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final boolean postdom; 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* {@code non-null;} method being processed */ 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final SsaMethod meth; 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* Method's basic blocks. */ 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final ArrayList<SsaBasicBlock> blocks; 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** indexed by basic block index */ 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final DFSInfo[] info; 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final ArrayList<SsaBasicBlock> vertex; 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} the raw dominator info */ 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final DomFront.DomInfo domInfos[]; 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs an instance. 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param meth {@code non-null;} method to process 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param domInfos {@code non-null;} the raw dominator info 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param postdom true for postdom information, false for normal dom info 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private Dominators(SsaMethod meth, DomFront.DomInfo[] domInfos, 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean postdom) { 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.meth = meth; 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.domInfos = domInfos; 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.postdom = postdom; 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.blocks = meth.getBlocks(); 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.info = new DFSInfo[blocks.size() + 2]; 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.vertex = new ArrayList<SsaBasicBlock>(); 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs a fully-initialized instance. (This method exists so as 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * to avoid calling a large amount of code in the constructor.) 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param meth {@code non-null;} method to process 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param domInfos {@code non-null;} the raw dominator info 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param postdom true for postdom information, false for normal dom info 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static Dominators make(SsaMethod meth, DomFront.DomInfo[] domInfos, 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean postdom) { 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Dominators result = new Dominators(meth, domInfos, postdom); 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.run(); 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private BitSet getSuccs(SsaBasicBlock block) { 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (postdom) { 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return block.getPredecessors(); 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return block.getSuccessors(); 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private BitSet getPreds(SsaBasicBlock block) { 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (postdom) { 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return block.getSuccessors(); 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return block.getPredecessors(); 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Performs path compress on the DFS info. 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param in Basic block whose DFS info we are path compressing. 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void compress(SsaBasicBlock in) { 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DFSInfo bbInfo = info[in.getIndex()]; 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DFSInfo ancestorbbInfo = info[bbInfo.ancestor.getIndex()]; 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (ancestorbbInfo.ancestor != null) { 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<SsaBasicBlock> worklist = new ArrayList<SsaBasicBlock>(); 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson HashSet<SsaBasicBlock> visited = new HashSet<SsaBasicBlock>(); 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson worklist.add(in); 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson while (!worklist.isEmpty()) { 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int wsize = worklist.size(); 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock v = worklist.get(wsize - 1); 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DFSInfo vbbInfo = info[v.getIndex()]; 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock vAncestor = vbbInfo.ancestor; 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DFSInfo vabbInfo = info[vAncestor.getIndex()]; 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Make sure we process our ancestor before ourselves. 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (visited.add(vAncestor) && vabbInfo.ancestor != null) { 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson worklist.add(vAncestor); 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson continue; 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson worklist.remove(wsize - 1); 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Update based on ancestor info. 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (vabbInfo.ancestor == null) { 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson continue; 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock vAncestorRep = vabbInfo.rep; 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock vRep = vbbInfo.rep; 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (info[vAncestorRep.getIndex()].semidom 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson < info[vRep.getIndex()].semidom) { 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson vbbInfo.rep = vAncestorRep; 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson vbbInfo.ancestor = vabbInfo.ancestor; 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private SsaBasicBlock eval(SsaBasicBlock v) { 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DFSInfo bbInfo = info[v.getIndex()]; 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (bbInfo.ancestor == null) { 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return v; 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson compress(v); 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return bbInfo.rep; 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 163579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 164579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 165579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Performs dominator/post-dominator calculation for the control 166579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * flow graph. 167579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 168579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param meth {@code non-null;} method to analyze 169579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 170579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void run() { 171579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock root = postdom 172579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ? meth.getExitBlock() : meth.getEntryBlock(); 173579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 174579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (root != null) { 175579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson vertex.add(root); 176579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson domInfos[root.getIndex()].idom = root.getIndex(); 177579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 178579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 179579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 180579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * First we perform a DFS numbering of the blocks, by 181579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * numbering the dfs tree roots. 182579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 183579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 184579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DfsWalker walker = new DfsWalker(); 185579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson meth.forEachBlockDepthFirst(postdom, walker); 186579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 187579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // the largest semidom number assigned 188579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int dfsMax = vertex.size() - 1; 189579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 190579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Now calculate semidominators. 191579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = dfsMax; i >= 2; --i) { 192579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock w = vertex.get(i); 193579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DFSInfo wInfo = info[w.getIndex()]; 194579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 195579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BitSet preds = getPreds(w); 196579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int j = preds.nextSetBit(0); 197579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson j >= 0; 198579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson j = preds.nextSetBit(j + 1)) { 199579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock predBlock = blocks.get(j); 200579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DFSInfo predInfo = info[predBlock.getIndex()]; 201579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 202579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 203579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * PredInfo may not exist in case the predecessor is 204579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * not reachable. 205579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 206579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (predInfo != null) { 207579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int predSemidom = info[eval(predBlock).getIndex()].semidom; 208579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (predSemidom < wInfo.semidom) { 209579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson wInfo.semidom = predSemidom; 210579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 211579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 212579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 213579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson info[vertex.get(wInfo.semidom).getIndex()].bucket.add(w); 214579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 215579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 216579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Normally we would call link here, but in our O(m log n) 217579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * implementation this is equivalent to the following 218579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * single line. 219579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 220579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson wInfo.ancestor = wInfo.parent; 221579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 222579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Implicity define idom for each vertex. 223579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ArrayList<SsaBasicBlock> wParentBucket; 224579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson wParentBucket = info[wInfo.parent.getIndex()].bucket; 225579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 226579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson while (!wParentBucket.isEmpty()) { 227579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int lastItem = wParentBucket.size() - 1; 228579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock last = wParentBucket.remove(lastItem); 229579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock U = eval(last); 230579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (info[U.getIndex()].semidom 231579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson < info[last.getIndex()].semidom) { 232579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson domInfos[last.getIndex()].idom = U.getIndex(); 233579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 234579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson domInfos[last.getIndex()].idom = wInfo.parent.getIndex(); 235579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 236579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 237579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 238579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 239579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Now explicitly define the immediate dominator of each vertex 240579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 2; i <= dfsMax; ++i) { 241579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock w = vertex.get(i); 242579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (domInfos[w.getIndex()].idom 243579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson != vertex.get(info[w.getIndex()].semidom).getIndex()) { 244579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson domInfos[w.getIndex()].idom 245579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson = domInfos[domInfos[w.getIndex()].idom].idom; 246579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 247579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 248579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 249579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 250579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 251579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Callback for depth-first walk through control flow graph (either 252579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * from the entry block or the exit block). Records the traversal order 253579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * in the {@code info}list. 254579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 255579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private class DfsWalker implements SsaBasicBlock.Visitor { 256579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private int dfsNum = 0; 257579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 258579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void visitBlock(SsaBasicBlock v, SsaBasicBlock parent) { 259579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DFSInfo bbInfo = new DFSInfo(); 260579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson bbInfo.semidom = ++dfsNum; 261579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson bbInfo.rep = v; 262579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson bbInfo.parent = parent; 263579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson vertex.add(v); 264579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson info[v.getIndex()] = bbInfo; 265579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 266579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 267579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 268579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static final class DFSInfo { 269579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int semidom; 270579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public SsaBasicBlock parent; 271579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 272579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 273579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * rep(resentative) is known as "label" in the paper. It is the node 274579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * that our block's DFS info has been unioned to. 275579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 276579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public SsaBasicBlock rep; 277579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 278579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public SsaBasicBlock ancestor; 279579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public ArrayList<SsaBasicBlock> bucket; 280579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 281579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public DFSInfo() { 282579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson bucket = new ArrayList<SsaBasicBlock>(); 283579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 284579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 285579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 286