364 lines · cpp
1//===- Dominance.cpp - Dominator analysis for CFGs ------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Implementation of dominance related classes and instantiations of extern10// templates.11//12//===----------------------------------------------------------------------===//13 14#include "mlir/IR/Dominance.h"15#include "mlir/IR/Operation.h"16#include "mlir/IR/RegionKindInterface.h"17#include "llvm/Support/GenericDomTreeConstruction.h"18 19using namespace mlir;20using namespace mlir::detail;21 22template class llvm::DominatorTreeBase<Block, /*IsPostDom=*/false>;23template class llvm::DominatorTreeBase<Block, /*IsPostDom=*/true>;24template class llvm::DomTreeNodeBase<Block>;25 26//===----------------------------------------------------------------------===//27// DominanceInfoBase28//===----------------------------------------------------------------------===//29 30template <bool IsPostDom>31DominanceInfoBase<IsPostDom>::~DominanceInfoBase() {32 for (auto entry : dominanceInfos)33 delete entry.second.getPointer();34}35 36template <bool IsPostDom>37void DominanceInfoBase<IsPostDom>::invalidate() {38 for (auto entry : dominanceInfos)39 delete entry.second.getPointer();40 dominanceInfos.clear();41}42 43template <bool IsPostDom>44void DominanceInfoBase<IsPostDom>::invalidate(Region *region) {45 auto it = dominanceInfos.find(region);46 if (it != dominanceInfos.end()) {47 delete it->second.getPointer();48 dominanceInfos.erase(it);49 }50}51 52/// Return the dom tree and "hasSSADominance" bit for the given region. The53/// DomTree will be null for single-block regions. This lazily constructs the54/// DomTree on demand when needsDomTree=true.55template <bool IsPostDom>56auto DominanceInfoBase<IsPostDom>::getDominanceInfo(Region *region,57 bool needsDomTree) const58 -> llvm::PointerIntPair<DomTree *, 1, bool> {59 // Check to see if we already have this information.60 auto itAndInserted = dominanceInfos.insert({region, {nullptr, true}});61 auto &entry = itAndInserted.first->second;62 63 // This method builds on knowledge that multi-block regions always have64 // SSADominance. Graph regions are only allowed to be single-block regions,65 // but of course single-block regions may also have SSA dominance.66 if (!itAndInserted.second) {67 // We do have it, so we know the 'hasSSADominance' bit is correct, but we68 // may not have constructed a DominatorTree yet. If we need it, build it.69 if (needsDomTree && !entry.getPointer() && !region->hasOneBlock()) {70 auto *domTree = new DomTree();71 domTree->recalculate(*region);72 entry.setPointer(domTree);73 }74 return entry;75 }76 77 // Nope, lazily construct it. Create a DomTree if this is a multi-block78 // region.79 if (!region->hasOneBlock()) {80 auto *domTree = new DomTree();81 domTree->recalculate(*region);82 entry.setPointer(domTree);83 // Multiblock regions always have SSA dominance, leave `second` set to true.84 return entry;85 }86 87 // Single block regions have a more complicated predicate.88 if (Operation *parentOp = region->getParentOp()) {89 if (!parentOp->isRegistered()) { // We don't know about unregistered ops.90 entry.setInt(false);91 } else if (auto regionKindItf = dyn_cast<RegionKindInterface>(parentOp)) {92 // Registered ops can opt-out of SSA dominance with93 // RegionKindInterface.94 entry.setInt(regionKindItf.hasSSADominance(region->getRegionNumber()));95 }96 }97 98 return entry;99}100 101/// Return the ancestor block enclosing the specified block. This returns null102/// if we reach the top of the hierarchy.103static Block *getAncestorBlock(Block *block) {104 if (Operation *ancestorOp = block->getParentOp())105 return ancestorOp->getBlock();106 return nullptr;107}108 109/// Walks up the list of containers of the given block and calls the110/// user-defined traversal function for every pair of a region and block that111/// could be found during traversal. If the user-defined function returns true112/// for a given pair, traverseAncestors will return the current block. Nullptr113/// otherwise.114template <typename FuncT>115static Block *traverseAncestors(Block *block, const FuncT &func) {116 do {117 // Invoke the user-defined traversal function for each block.118 if (func(block))119 return block;120 } while ((block = getAncestorBlock(block)));121 return nullptr;122}123 124/// Tries to update the given block references to live in the same region by125/// exploring the relationship of both blocks with respect to their regions.126static bool tryGetBlocksInSameRegion(Block *&a, Block *&b) {127 // If both block do not live in the same region, we will have to check their128 // parent operations.129 Region *aRegion = a->getParent();130 Region *bRegion = b->getParent();131 if (aRegion == bRegion)132 return true;133 134 // Iterate over all ancestors of `a`, counting the depth of `a`. If one of135 // `a`s ancestors are in the same region as `b`, then we stop early because we136 // found our NCA.137 size_t aRegionDepth = 0;138 if (Block *aResult = traverseAncestors(a, [&](Block *block) {139 ++aRegionDepth;140 return block->getParent() == bRegion;141 })) {142 a = aResult;143 return true;144 }145 146 // Iterate over all ancestors of `b`, counting the depth of `b`. If one of147 // `b`s ancestors are in the same region as `a`, then we stop early because148 // we found our NCA.149 size_t bRegionDepth = 0;150 if (Block *bResult = traverseAncestors(b, [&](Block *block) {151 ++bRegionDepth;152 return block->getParent() == aRegion;153 })) {154 b = bResult;155 return true;156 }157 158 // Otherwise we found two blocks that are siblings at some level. Walk the159 // deepest one up until we reach the top or find an NCA.160 while (true) {161 if (aRegionDepth > bRegionDepth) {162 a = getAncestorBlock(a);163 --aRegionDepth;164 } else if (aRegionDepth < bRegionDepth) {165 b = getAncestorBlock(b);166 --bRegionDepth;167 } else {168 break;169 }170 }171 172 // If we found something with the same level, then we can march both up at the173 // same time from here on out.174 while (a) {175 // If they are at the same level, and have the same parent region then we176 // succeeded.177 if (a->getParent() == b->getParent())178 return true;179 180 a = getAncestorBlock(a);181 b = getAncestorBlock(b);182 }183 184 // They don't share an NCA, perhaps they are in different modules or185 // something.186 return false;187}188 189template <bool IsPostDom>190Block *191DominanceInfoBase<IsPostDom>::findNearestCommonDominator(Block *a,192 Block *b) const {193 // If either a or b are null, then conservatively return nullptr.194 if (!a || !b)195 return nullptr;196 197 // If they are the same block, then we are done.198 if (a == b)199 return a;200 201 // Try to find blocks that are in the same region.202 if (!tryGetBlocksInSameRegion(a, b))203 return nullptr;204 205 // If the common ancestor in a common region is the same block, then return206 // it.207 if (a == b)208 return a;209 210 // Otherwise, there must be multiple blocks in the region, check the211 // DomTree.212 return getDomTree(a->getParent()).findNearestCommonDominator(a, b);213}214 215/// Returns the given block iterator if it lies within the region region.216/// Otherwise, otherwise finds the ancestor of the given block iterator that217/// lies within the given region. Returns and "empty" iterator if the latter218/// fails.219///220/// Note: This is a variant of Region::findAncestorOpInRegion that operates on221/// block iterators instead of ops.222static std::pair<Block *, Block::iterator>223findAncestorIteratorInRegion(Region *r, Block *b, Block::iterator it) {224 // Case 1: The iterator lies within the region region.225 if (b->getParent() == r)226 return std::make_pair(b, it);227 228 // Otherwise: Find ancestor iterator. Bail if we run out of parent ops.229 Operation *parentOp = b->getParentOp();230 if (!parentOp)231 return std::make_pair(static_cast<Block *>(nullptr), Block::iterator());232 Operation *op = r->findAncestorOpInRegion(*parentOp);233 if (!op)234 return std::make_pair(static_cast<Block *>(nullptr), Block::iterator());235 return std::make_pair(op->getBlock(), op->getIterator());236}237 238/// Given two iterators into the same block, return "true" if `a` is before `b.239/// Note: This is a variant of Operation::isBeforeInBlock that operates on240/// block iterators instead of ops.241static bool isBeforeInBlock(Block *block, Block::iterator a,242 Block::iterator b) {243 if (a == b)244 return false;245 if (a == block->end())246 return false;247 if (b == block->end())248 return true;249 return a->isBeforeInBlock(&*b);250}251 252template <bool IsPostDom>253bool DominanceInfoBase<IsPostDom>::properlyDominatesImpl(254 Block *aBlock, Block::iterator aIt, Block *bBlock, Block::iterator bIt,255 bool enclosingOk) const {256 assert(aBlock && bBlock && "expected non-null blocks");257 258 // A block iterator (post)dominates, but does not properly (post)dominate,259 // itself unless this is a graph region.260 if (aBlock == bBlock && aIt == bIt)261 return !hasSSADominance(aBlock);262 263 // If the iterators are in different regions, then normalize one into the264 // other.265 Region *aRegion = aBlock->getParent();266 if (aRegion != bBlock->getParent()) {267 // Scoot up b's region tree until we find a location in A's region that268 // encloses it. If this fails, then we know there is no (post)dom relation.269 if (!aRegion) {270 bBlock = nullptr;271 bIt = Block::iterator();272 } else {273 std::tie(bBlock, bIt) =274 findAncestorIteratorInRegion(aRegion, bBlock, bIt);275 }276 if (!bBlock)277 return false;278 assert(bBlock->getParent() == aRegion && "expected block in regionA");279 280 // If 'a' encloses 'b', then we consider it to (post)dominate.281 if (aBlock == bBlock && aIt == bIt && enclosingOk)282 return true;283 }284 285 // Ok, they are in the same region now.286 if (aBlock == bBlock) {287 // Dominance changes based on the region type. In a region with SSA288 // dominance, uses inside the same block must follow defs. In other289 // regions kinds, uses and defs can come in any order inside a block.290 if (!hasSSADominance(aBlock))291 return true;292 if constexpr (IsPostDom) {293 return isBeforeInBlock(aBlock, bIt, aIt);294 } else {295 return isBeforeInBlock(aBlock, aIt, bIt);296 }297 }298 299 // If the blocks are different, use DomTree to resolve the query.300 return getDomTree(aRegion).properlyDominates(aBlock, bBlock);301}302 303/// Return true if the specified block is reachable from the entry block of304/// its region.305template <bool IsPostDom>306bool DominanceInfoBase<IsPostDom>::isReachableFromEntry(Block *a) const {307 // If this is the first block in its region, then it is obviously reachable.308 Region *region = a->getParent();309 if (®ion->front() == a)310 return true;311 312 // Otherwise this is some block in a multi-block region. Check DomTree.313 return getDomTree(region).isReachableFromEntry(a);314}315 316template class detail::DominanceInfoBase</*IsPostDom=*/true>;317template class detail::DominanceInfoBase</*IsPostDom=*/false>;318 319//===----------------------------------------------------------------------===//320// DominanceInfo321//===----------------------------------------------------------------------===//322 323bool DominanceInfo::properlyDominates(Operation *a, Operation *b,324 bool enclosingOpOk) const {325 return super::properlyDominatesImpl(a->getBlock(), a->getIterator(),326 b->getBlock(), b->getIterator(),327 enclosingOpOk);328}329 330bool DominanceInfo::properlyDominates(Block *a, Block *b) const {331 return super::properlyDominatesImpl(a, a->begin(), b, b->begin(),332 /*enclosingOk=*/true);333}334 335/// Return true if the `a` value properly dominates operation `b`, i.e if the336/// operation that defines `a` properlyDominates `b` and the operation that337/// defines `a` does not contain `b`.338bool DominanceInfo::properlyDominates(Value a, Operation *b) const {339 // block arguments properly dominate all operations in their own block, so340 // we use a dominates check here, not a properlyDominates check.341 if (auto blockArg = dyn_cast<BlockArgument>(a))342 return dominates(blockArg.getOwner(), b->getBlock());343 344 // `a` properlyDominates `b` if the operation defining `a` properlyDominates345 // `b`, but `a` does not itself enclose `b` in one of its regions.346 return properlyDominates(a.getDefiningOp(), b, /*enclosingOpOk=*/false);347}348 349//===----------------------------------------------------------------------===//350// PostDominanceInfo351//===----------------------------------------------------------------------===//352 353bool PostDominanceInfo::properlyPostDominates(Operation *a, Operation *b,354 bool enclosingOpOk) const {355 return super::properlyDominatesImpl(a->getBlock(), a->getIterator(),356 b->getBlock(), b->getIterator(),357 enclosingOpOk);358}359 360bool PostDominanceInfo::properlyPostDominates(Block *a, Block *b) const {361 return super::properlyDominatesImpl(a, a->end(), b, b->end(),362 /*enclosingOk=*/true);363}364