1 // Copyright (c) 2016, the R8 project authors. Please see the AUTHORS file 2 // for details. All rights reserved. Use of this source code is governed by a 3 // BSD-style license that can be found in the LICENSE file. 4 5 package com.android.tools.r8.ir.code; 6 7 import java.util.Collection; 8 import java.util.Collections; 9 import java.util.Iterator; 10 import java.util.List; 11 12 public class DominatorTree { 13 14 IRCode code; 15 private BasicBlock[] sorted; 16 private BasicBlock[] doms; 17 DominatorTree(IRCode code)18 public DominatorTree(IRCode code) { 19 this(code, Collections.emptyList()); 20 } 21 22 // TODO(sgjesse) Get rid of this constructor and blocksToIgnore. DominatorTree(IRCode code, List<BasicBlock> blocksToIgnore)23 DominatorTree(IRCode code, List<BasicBlock> blocksToIgnore) { 24 this.code = code; 25 this.sorted = code.topologicallySortedBlocks(blocksToIgnore); 26 numberBlocks(); 27 build(); 28 } 29 30 /** 31 * Get the immediate dominator block for a block. 32 */ immediateDominator(BasicBlock block)33 public BasicBlock immediateDominator(BasicBlock block) { 34 return doms[block.getNumber()]; 35 } 36 37 /** 38 * Check if one basic block is dominated by another basic block. 39 * 40 * @param subject subject to check for domination by {@code dominator} 41 * @param dominator dominator to check against 42 * @return wether {@code subject} is dominated by {@code dominator} 43 */ dominatedBy(BasicBlock subject, BasicBlock dominator)44 public boolean dominatedBy(BasicBlock subject, BasicBlock dominator) { 45 if (subject == dominator) { 46 return true; 47 } 48 return strictlyDominatedBy(subject, dominator); 49 } 50 51 /** 52 * Check if one basic block is strictly dominated by another basic block. 53 * 54 * @param subject subject to check for domination by {@code dominator} 55 * @param dominator dominator to check against 56 * @return wether {@code subject} is strictly dominated by {@code dominator} 57 */ strictlyDominatedBy(BasicBlock subject, BasicBlock dominator)58 public boolean strictlyDominatedBy(BasicBlock subject, BasicBlock dominator) { 59 if (subject.getNumber() == 0) { 60 return false; 61 } 62 while (true) { 63 BasicBlock idom = immediateDominator(subject); 64 if (idom.getNumber() < dominator.getNumber()) { 65 return false; 66 } 67 if (idom == dominator) { 68 return true; 69 } 70 subject = idom; 71 } 72 } 73 74 /** 75 * Use the dominator tree to find the dominating block that is closest to a set of blocks. 76 * 77 * @param blocks the block for which to find a dominator 78 * @return the closest dominator for the collection of blocks 79 */ closestDominator(Collection<BasicBlock> blocks)80 public BasicBlock closestDominator(Collection<BasicBlock> blocks) { 81 if (blocks.size() == 0) { 82 return null; 83 } 84 Iterator<BasicBlock> it = blocks.iterator(); 85 BasicBlock dominator = it.next(); 86 while (it.hasNext()) { 87 dominator = intersect(dominator, it.next()); 88 } 89 return dominator; 90 } 91 getSortedBlocks()92 public BasicBlock[] getSortedBlocks() { 93 return sorted; 94 } 95 numberBlocks()96 private void numberBlocks() { 97 for (int i = 0; i < sorted.length; i++) { 98 sorted[i].setNumber(i); 99 } 100 } 101 postorderCompareLess(BasicBlock b1, BasicBlock b2)102 private boolean postorderCompareLess(BasicBlock b1, BasicBlock b2) { 103 // The topological sort is reverse postorder. 104 return b1.getNumber() > b2.getNumber(); 105 } 106 107 // Build dominator tree based on the algorithm described in this paper: 108 // 109 // A Simple, Fast Dominance Algorithm 110 // Cooper, Keith D.; Harvey, Timothy J.; and Kennedy, Ken (2001). 111 // http://www.cs.rice.edu/~keith/EMBED/dom.pdf build()112 private void build() { 113 doms = new BasicBlock[sorted.length]; 114 doms[0] = sorted[0]; 115 boolean changed = true; 116 while (changed) { 117 changed = false; 118 // Run through all nodes in reverse postorder (except start node). 119 for (int i = 1; i < sorted.length; i++) { 120 BasicBlock b = sorted[i]; 121 // Pick one processed predecessor. 122 BasicBlock newIDom = null; 123 int picked = -1; 124 for (int j = 0; newIDom == null && j < b.getPredecessors().size(); j++) { 125 BasicBlock p = b.getPredecessors().get(j); 126 if (doms[p.getNumber()] != null) { 127 picked = j; 128 newIDom = p; 129 } 130 } 131 // Run through all other predecessors. 132 for (int j = 0; j < b.getPredecessors().size(); j++) { 133 BasicBlock p = b.getPredecessors().get(j); 134 if (j == picked) { 135 continue; 136 } 137 if (doms[p.getNumber()] != null) { 138 newIDom = intersect(p, newIDom); 139 } 140 } 141 if (doms[b.getNumber()] != newIDom) { 142 doms[b.getNumber()] = newIDom; 143 changed = true; 144 } 145 } 146 } 147 } 148 intersect(BasicBlock b1, BasicBlock b2)149 private BasicBlock intersect(BasicBlock b1, BasicBlock b2) { 150 BasicBlock finger1 = b1; 151 BasicBlock finger2 = b2; 152 while (finger1 != finger2) { 153 while (postorderCompareLess(finger1, finger2)) { 154 finger1 = doms[finger1.getNumber()]; 155 } 156 while (postorderCompareLess(finger2, finger1)) { 157 finger2 = doms[finger2.getNumber()]; 158 } 159 } 160 return finger1; 161 } 162 163 @Override toString()164 public String toString() { 165 StringBuilder builder = new StringBuilder(); 166 builder.append("Dominators\n"); 167 for (BasicBlock block : sorted) { 168 builder.append(block.getNumber()); 169 builder.append(": "); 170 builder.append(doms[block.getNumber()].getNumber()); 171 builder.append("\n"); 172 } 173 return builder.toString(); 174 } 175 } 176