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 17package com.android.dx.ssa; 18 19import com.android.dx.util.IntSet; 20import com.android.dx.util.BitIntSet; 21import com.android.dx.util.ListIntSet; 22 23import java.util.ArrayList; 24import java.util.Arrays; 25import java.util.BitSet; 26 27/** 28 * Calculates the dominance-frontiers of a methot's basic blocks. 29 * Algorithm from "A Simple, Fast Dominance Algorithm" by Cooper, 30 * Harvey, and Kennedy; transliterated to Java. 31 */ 32public class DomFront { 33 /** local debug flag */ 34 private static boolean DEBUG = false; 35 36 /** {@code non-null;} method being processed */ 37 private final SsaMethod meth; 38 39 private final ArrayList<SsaBasicBlock> nodes; 40 41 private final DomInfo[] domInfos; 42 43 /** 44 * Dominance-frontier information for a single basic block. 45 */ 46 public static class DomInfo { 47 /** 48 * {@code null-ok;} the dominance frontier set indexed by 49 * block index 50 */ 51 public IntSet dominanceFrontiers; 52 53 /** {@code >= 0 after run();} the index of the immediate dominator */ 54 public int idom = -1; 55 } 56 57 /** 58 * Constructs instance. Call {@link DomFront#run} to process. 59 * 60 * @param meth {@code non-null;} method to process 61 */ 62 public DomFront(SsaMethod meth) { 63 this.meth = meth; 64 nodes = meth.getBlocks(); 65 66 int szNodes = nodes.size(); 67 domInfos = new DomInfo[szNodes]; 68 69 for (int i = 0; i < szNodes; i++) { 70 domInfos[i] = new DomInfo(); 71 } 72 } 73 74 /** 75 * Calculates the dominance frontier information for the method. 76 * 77 * @return {@code non-null;} an array of DomInfo structures 78 */ 79 public DomInfo[] run() { 80 int szNodes = nodes.size(); 81 82 if (DEBUG) { 83 for (int i = 0; i < szNodes; i++) { 84 SsaBasicBlock node = nodes.get(i); 85 System.out.println("pred[" + i + "]: " 86 + node.getPredecessors()); 87 } 88 } 89 90 Dominators methDom = Dominators.make(meth, domInfos, false); 91 92 if (DEBUG) { 93 for (int i = 0; i < szNodes; i++) { 94 DomInfo info = domInfos[i]; 95 System.out.println("idom[" + i + "]: " 96 + info.idom); 97 } 98 } 99 100 buildDomTree(); 101 102 if (DEBUG) { 103 debugPrintDomChildren(); 104 } 105 106 for (int i = 0; i < szNodes; i++) { 107 domInfos[i].dominanceFrontiers 108 = SetFactory.makeDomFrontSet(szNodes); 109 } 110 111 calcDomFronts(); 112 113 if (DEBUG) { 114 for (int i = 0; i < szNodes; i++) { 115 System.out.println("df[" + i + "]: " 116 + domInfos[i].dominanceFrontiers); 117 } 118 } 119 120 return domInfos; 121 } 122 123 private void debugPrintDomChildren() { 124 int szNodes = nodes.size(); 125 126 for (int i = 0; i < szNodes; i++) { 127 SsaBasicBlock node = nodes.get(i); 128 StringBuffer sb = new StringBuffer(); 129 130 sb.append('{'); 131 boolean comma = false; 132 for (SsaBasicBlock child : node.getDomChildren()) { 133 if (comma) { 134 sb.append(','); 135 } 136 sb.append(child); 137 comma = true; 138 } 139 sb.append('}'); 140 141 System.out.println("domChildren[" + node + "]: " 142 + sb); 143 } 144 } 145 146 /** 147 * The dominators algorithm leaves us knowing who the immediate dominator 148 * is for each node. This sweeps the node list and builds the proper 149 * dominance tree. 150 */ 151 private void buildDomTree() { 152 int szNodes = nodes.size(); 153 154 for (int i = 0; i < szNodes; i++) { 155 DomInfo info = domInfos[i]; 156 157 if (info.idom == -1) continue; 158 159 SsaBasicBlock domParent = nodes.get(info.idom); 160 domParent.addDomChild(nodes.get(i)); 161 } 162 } 163 164 /** 165 * Calculates the dominance-frontier set. 166 * from "A Simple, Fast Dominance Algorithm" by Cooper, 167 * Harvey, and Kennedy; transliterated to Java. 168 */ 169 private void calcDomFronts() { 170 int szNodes = nodes.size(); 171 172 for (int b = 0; b < szNodes; b++) { 173 SsaBasicBlock nb = nodes.get(b); 174 DomInfo nbInfo = domInfos[b]; 175 BitSet pred = nb.getPredecessors(); 176 177 if (pred.cardinality() > 1) { 178 for (int i = pred.nextSetBit(0); i >= 0; 179 i = pred.nextSetBit(i + 1)) { 180 181 for (int runnerIndex = i; 182 runnerIndex != nbInfo.idom; /* empty */) { 183 /* 184 * We can stop if we hit a block we already 185 * added label to, since we must be at a part 186 * of the dom tree we have seen before. 187 */ 188 if (runnerIndex == -1) break; 189 190 DomInfo runnerInfo = domInfos[runnerIndex]; 191 192 if (runnerInfo.dominanceFrontiers.has(b)) { 193 break; 194 } 195 196 // Add b to runner's dominance frontier set. 197 runnerInfo.dominanceFrontiers.add(b); 198 runnerIndex = runnerInfo.idom; 199 } 200 } 201 } 202 } 203 } 204} 205