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 com.android.dx.util.IntSet; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.BitIntSet; 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.ListIntSet; 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.ArrayList; 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.Arrays; 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.BitSet; 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Calculates the dominance-frontiers of a methot's basic blocks. 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Algorithm from "A Simple, Fast Dominance Algorithm" by Cooper, 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Harvey, and Kennedy; transliterated to Java. 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic class DomFront { 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** local debug flag */ 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static boolean DEBUG = false; 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} method being processed */ 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final SsaMethod meth; 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final ArrayList<SsaBasicBlock> nodes; 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final DomInfo[] domInfos; 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Dominance-frontier information for a single basic block. 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static class DomInfo { 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@code null-ok;} the dominance frontier set indexed by 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * block index 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public IntSet dominanceFrontiers; 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code >= 0 after run();} the index of the immediate dominator */ 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int idom = -1; 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs instance. Call {@link DomFront#run} to process. 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param meth {@code non-null;} method to process 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public DomFront(SsaMethod meth) { 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.meth = meth; 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson nodes = meth.getBlocks(); 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int szNodes = nodes.size(); 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson domInfos = new DomInfo[szNodes]; 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < szNodes; i++) { 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson domInfos[i] = new DomInfo(); 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Calculates the dominance frontier information for the method. 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} an array of DomInfo structures 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public DomInfo[] run() { 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int szNodes = nodes.size(); 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (DEBUG) { 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < szNodes; i++) { 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock node = nodes.get(i); 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson System.out.println("pred[" + i + "]: " 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson + node.getPredecessors()); 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Dominators methDom = Dominators.make(meth, domInfos, false); 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (DEBUG) { 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < szNodes; i++) { 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DomInfo info = domInfos[i]; 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson System.out.println("idom[" + i + "]: " 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson + info.idom); 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson buildDomTree(); 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (DEBUG) { 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson debugPrintDomChildren(); 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < szNodes; i++) { 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson domInfos[i].dominanceFrontiers 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson = SetFactory.makeDomFrontSet(szNodes); 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson calcDomFronts(); 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (DEBUG) { 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < szNodes; i++) { 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson System.out.println("df[" + i + "]: " 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson + domInfos[i].dominanceFrontiers); 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return domInfos; 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void debugPrintDomChildren() { 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int szNodes = nodes.size(); 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < szNodes; i++) { 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock node = nodes.get(i); 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson StringBuffer sb = new StringBuffer(); 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append('{'); 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean comma = false; 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (SsaBasicBlock child : node.getDomChildren()) { 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (comma) { 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(','); 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(child); 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson comma = true; 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append('}'); 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson System.out.println("domChildren[" + node + "]: " 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson + sb); 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * The dominators algorithm leaves us knowing who the immediate dominator 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * is for each node. This sweeps the node list and builds the proper 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * dominance tree. 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void buildDomTree() { 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int szNodes = nodes.size(); 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < szNodes; i++) { 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DomInfo info = domInfos[i]; 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (info.idom == -1) continue; 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock domParent = nodes.get(info.idom); 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson domParent.addDomChild(nodes.get(i)); 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 163579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 164579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 165579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Calculates the dominance-frontier set. 166579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * from "A Simple, Fast Dominance Algorithm" by Cooper, 167579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Harvey, and Kennedy; transliterated to Java. 168579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 169579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void calcDomFronts() { 170579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int szNodes = nodes.size(); 171579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 172579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int b = 0; b < szNodes; b++) { 173579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson SsaBasicBlock nb = nodes.get(b); 174579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DomInfo nbInfo = domInfos[b]; 175579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BitSet pred = nb.getPredecessors(); 176579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 177579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (pred.cardinality() > 1) { 178579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = pred.nextSetBit(0); i >= 0; 179579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson i = pred.nextSetBit(i + 1)) { 180579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 181579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int runnerIndex = i; 182579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson runnerIndex != nbInfo.idom; /* empty */) { 183579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 184579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * We can stop if we hit a block we already 185579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * added label to, since we must be at a part 186579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * of the dom tree we have seen before. 187579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 188579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (runnerIndex == -1) break; 189579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 190579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson DomInfo runnerInfo = domInfos[runnerIndex]; 191579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 192579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (runnerInfo.dominanceFrontiers.has(b)) { 193579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson break; 194579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 195579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 196579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Add b to runner's dominance frontier set. 197579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson runnerInfo.dominanceFrontiers.add(b); 198579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson runnerIndex = runnerInfo.idom; 199579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 200579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 201579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 202579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 203579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 204579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 205