DomFront.java revision 4b4413ab3d8de5805276cfcde3d7f535d9f64e85
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 SsaBasicBlock domParent = nodes.get(info.idom); 157 domParent.addDomChild(nodes.get(i)); 158 } 159 } 160 161 /** 162 * Calculates the dominance-frontier set. 163 * from "A Simple, Fast Dominance Algorithm" by Cooper, 164 * Harvey, and Kennedy; transliterated to Java. 165 */ 166 private void calcDomFronts() { 167 int szNodes = nodes.size(); 168 169 for (int b = 0; b < szNodes; b++) { 170 SsaBasicBlock nb = nodes.get(b); 171 DomInfo nbInfo = domInfos[b]; 172 BitSet pred = nb.getPredecessors(); 173 174 if (pred.cardinality() > 1) { 175 for (int i = pred.nextSetBit(0); i >= 0; 176 i = pred.nextSetBit(i + 1)) { 177 178 for (int runnerIndex = i; 179 runnerIndex != nbInfo.idom; /* empty */) { 180 /* 181 * We can stop if we hit a block we already 182 * added label to, since we must be at a part 183 * of the dom tree we have seen before. 184 */ 185 DomInfo runnerInfo = domInfos[runnerIndex]; 186 187 if (runnerInfo.dominanceFrontiers.has(b)) { 188 break; 189 } 190 191 // Add b to runner's dominance frontier set. 192 runnerInfo.dominanceFrontiers.add(b); 193 runnerIndex = runnerInfo.idom; 194 } 195 } 196 } 197 } 198 } 199} 200