1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project 3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you may not use this file except in compliance with the License. 6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * You may obtain a copy of the License at 7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See the License for the specific language governing permissions and 14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * limitations under the License. 15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpackage com.android.dx.ssa; 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.ArrayList; 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.BitSet; 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.HashSet; 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This class computes dominator and post-dominator information using the 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Lengauer-Tarjan method. 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See A Fast Algorithm for Finding Dominators in a Flowgraph 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This implementation runs in time O(n log n). The time bound 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * could be changed to O(n * ack(n)) with a small change to the link and eval, 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and an addition of a child field to the DFS info. In reality, the constant 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * overheads are high enough that the current method is faster in all but the 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * strangest artificially constructed examples. 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The basic idea behind this algorithm is to perform a DFS walk, keeping track 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * of various info about parents. We then use this info to calculate the 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * dominators, using union-find structures to link together the DFS info, 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * then finally evaluate the union-find results to get the dominators. 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This implementation is m log n because it does not perform union by 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * rank to keep the union-find tree balanced. 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic final class Dominators { 4499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /* postdom is true if we want post dominators */ 4599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final boolean postdom; 4699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 4799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /* {@code non-null;} method being processed */ 4899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final SsaMethod meth; 4999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* Method's basic blocks. */ 5199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final ArrayList<SsaBasicBlock> blocks; 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 5399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** indexed by basic block index */ 5499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final DFSInfo[] info; 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 5699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final ArrayList<SsaBasicBlock> vertex; 5799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 5899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} the raw dominator info */ 5999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final DomFront.DomInfo domInfos[]; 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 6199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** 6299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Constructs an instance. 63de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 6499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param meth {@code non-null;} method to process 6599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param domInfos {@code non-null;} the raw dominator info 6699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param postdom true for postdom information, false for normal dom info 6799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 6899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private Dominators(SsaMethod meth, DomFront.DomInfo[] domInfos, 6999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project boolean postdom) { 7099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project this.meth = meth; 7199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project this.domInfos = domInfos; 7299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project this.postdom = postdom; 7399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project this.blocks = meth.getBlocks(); 7499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project this.info = new DFSInfo[blocks.size() + 2]; 7599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project this.vertex = new ArrayList<SsaBasicBlock>(); 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 7899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** 7999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Constructs a fully-initialized instance. (This method exists so as 8099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * to avoid calling a large amount of code in the constructor.) 81de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 8299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param meth {@code non-null;} method to process 8399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param domInfos {@code non-null;} the raw dominator info 8499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param postdom true for postdom information, false for normal dom info 8599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 8699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project public static Dominators make(SsaMethod meth, DomFront.DomInfo[] domInfos, 8799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project boolean postdom) { 8899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project Dominators result = new Dominators(meth, domInfos, postdom); 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 9099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project result.run(); 9199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project return result; 9299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project } 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private BitSet getSuccs(SsaBasicBlock block) { 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (postdom) { 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return block.getPredecessors(); 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return block.getSuccessors(); 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private BitSet getPreds(SsaBasicBlock block) { 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (postdom) { 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return block.getSuccessors(); 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return block.getPredecessors(); 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Performs path compress on the DFS info. 112de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param in Basic block whose DFS info we are path compressing. 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void compress(SsaBasicBlock in) { 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DFSInfo bbInfo = info[in.getIndex()]; 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DFSInfo ancestorbbInfo = info[bbInfo.ancestor.getIndex()]; 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ancestorbbInfo.ancestor != null) { 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<SsaBasicBlock> worklist = new ArrayList<SsaBasicBlock>(); 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashSet<SsaBasicBlock> visited = new HashSet<SsaBasicBlock>(); 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project worklist.add(in); 123de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (!worklist.isEmpty()) { 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int wsize = worklist.size(); 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock v = worklist.get(wsize - 1); 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DFSInfo vbbInfo = info[v.getIndex()]; 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock vAncestor = vbbInfo.ancestor; 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DFSInfo vabbInfo = info[vAncestor.getIndex()]; 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Make sure we process our ancestor before ourselves. 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (visited.add(vAncestor) && vabbInfo.ancestor != null) { 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project worklist.add(vAncestor); 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project worklist.remove(wsize - 1); 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 13899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Update based on ancestor info. 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (vabbInfo.ancestor == null) { 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock vAncestorRep = vabbInfo.rep; 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock vRep = vbbInfo.rep; 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (info[vAncestorRep.getIndex()].semidom 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project < info[vRep.getIndex()].semidom) { 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project vbbInfo.rep = vAncestorRep; 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project vbbInfo.ancestor = vabbInfo.ancestor; 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 15299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private SsaBasicBlock eval(SsaBasicBlock v) { 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DFSInfo bbInfo = info[v.getIndex()]; 15599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (bbInfo.ancestor == null) { 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return v; 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 15999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project compress(v); 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return bbInfo.rep; 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 16599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Performs dominator/post-dominator calculation for the control 16699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * flow graph. 167de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 16899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param meth {@code non-null;} method to analyze 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 17099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private void run() { 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock root = postdom 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ? meth.getExitBlock() : meth.getEntryBlock(); 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (root != null) { 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project vertex.add(root); 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project domInfos[root.getIndex()].idom = root.getIndex(); 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 178de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 17999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /* 18099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * First we perform a DFS numbering of the blocks, by 18199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * numbering the dfs tree roots. 18299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DfsWalker walker = new DfsWalker(); 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project meth.forEachBlockDepthFirst(postdom, walker); 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // the largest semidom number assigned 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int dfsMax = vertex.size() - 1; 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Now calculate semidominators. 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = dfsMax; i >= 2; --i) { 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock w = vertex.get(i); 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DFSInfo wInfo = info[w.getIndex()]; 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet preds = getPreds(w); 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int j = preds.nextSetBit(0); 19799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project j >= 0; 19899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project j = preds.nextSetBit(j + 1)) { 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock predBlock = blocks.get(j); 200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DFSInfo predInfo = info[predBlock.getIndex()]; 20199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 20299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /* 20399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * PredInfo may not exist in case the predecessor is 20499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * not reachable. 20599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (predInfo != null) { 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int predSemidom = info[eval(predBlock).getIndex()].semidom; 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (predSemidom < wInfo.semidom) { 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project wInfo.semidom = predSemidom; 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project info[vertex.get(wInfo.semidom).getIndex()].bucket.add(w); 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 21599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /* 21699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Normally we would call link here, but in our O(m log n) 21799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * implementation this is equivalent to the following 21899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * single line. 21999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project wInfo.ancestor = wInfo.parent; 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 22299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project // Implicity define idom for each vertex. 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<SsaBasicBlock> wParentBucket; 224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project wParentBucket = info[wInfo.parent.getIndex()].bucket; 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (!wParentBucket.isEmpty()) { 227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int lastItem = wParentBucket.size() - 1; 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock last = wParentBucket.remove(lastItem); 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock U = eval(last); 230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (info[U.getIndex()].semidom 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project < info[last.getIndex()].semidom) { 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project domInfos[last.getIndex()].idom = U.getIndex(); 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project domInfos[last.getIndex()].idom = wInfo.parent.getIndex(); 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 23899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Now explicitly define the immediate dominator of each vertex 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 2; i <= dfsMax; ++i) { 241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SsaBasicBlock w = vertex.get(i); 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (domInfos[w.getIndex()].idom 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project != vertex.get(info[w.getIndex()].semidom).getIndex()) { 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project domInfos[w.getIndex()].idom 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project = domInfos[domInfos[w.getIndex()].idom].idom; 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 25199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Callback for depth-first walk through control flow graph (either 25299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * from the entry block or the exit block). Records the traversal order 25399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * in the {@code info}list. 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 25599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private class DfsWalker implements SsaBasicBlock.Visitor { 25699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private int dfsNum = 0; 25799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 25899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project public void visitBlock(SsaBasicBlock v, SsaBasicBlock parent) { 25999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project DFSInfo bbInfo = new DFSInfo(); 26099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project bbInfo.semidom = ++dfsNum; 26199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project bbInfo.rep = v; 26299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project bbInfo.parent = parent; 26399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project vertex.add(v); 26499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project info[v.getIndex()] = bbInfo; 26599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project } 26699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project } 26799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 26899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private static final class DFSInfo { 26999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project public int semidom; 27099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project public SsaBasicBlock parent; 27199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 27299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** 27399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * rep(resentative) is known as "label" in the paper. It is the node 27499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * that our block's DFS info has been unioned to. 27599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 27699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project public SsaBasicBlock rep; 27799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 27899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project public SsaBasicBlock ancestor; 27999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project public ArrayList<SsaBasicBlock> bucket; 28099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 28199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project public DFSInfo() { 28299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project bucket = new ArrayList<SsaBasicBlock>(); 28399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project } 284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 286