Dominance.cpp File Reference

#include "mlir/IR/Dominance.h"
#include "mlir/IR/Operation.h"
#include "mlir/IR/RegionKindInterface.h"
#include "llvm/Support/GenericDomTreeConstruction.h"

Go to the source code of this file.

Functions
static Block *	getAncestorBlock (Block *block)
	Return the ancestor block enclosing the specified block.
template<typename FuncT>
static Block *	traverseAncestors (Block *block, const FuncT &func)
	Walks up the list of containers of the given block and calls the user-defined traversal function for every pair of a region and block that could be found during traversal.
static bool	tryGetBlocksInSameRegion (Block *&a, Block *&b)
	Tries to update the given block references to live in the same region by exploring the relationship of both blocks with respect to their regions.
static std::pair< Block *, Block::iterator >	findAncestorIteratorInRegion (Region *r, Block *b, Block::iterator it)
	Returns the given block iterator if it lies within the region region.

Variables
	true
	Given two iterators into the same block, return "true" if a is before `b.

Function Documentation

findAncestorIteratorInRegion()

std::pair< Block *, Block::iterator > findAncestorIteratorInRegion ( Region * r, Block * b, Block::iterator it )

static

Returns the given block iterator if it lies within the region region.

Otherwise, otherwise finds the ancestor of the given block iterator that lies within the given region. Returns and "empty" iterator if the latter fails.

Note: This is a variant of Region::findAncestorOpInRegion that operates on block iterators instead of ops.

Definition at line 223 of file Dominance.cpp.

References b, mlir::Region::findAncestorOpInRegion(), and mlir::Operation::getBlock().

getAncestorBlock()

Block * getAncestorBlock ( Block * block )

static

Return the ancestor block enclosing the specified block.

This returns null if we reach the top of the hierarchy.

Definition at line 103 of file Dominance.cpp.

References mlir::Block::getParentOp().

Referenced by traverseAncestors(), and tryGetBlocksInSameRegion().

traverseAncestors()

template<typename FuncT>

Block * traverseAncestors ( Block * block, const FuncT & func )

static

Walks up the list of containers of the given block and calls the user-defined traversal function for every pair of a region and block that could be found during traversal.

If the user-defined function returns true for a given pair, traverseAncestors will return the current block. Nullptr otherwise.

Definition at line 115 of file Dominance.cpp.

References getAncestorBlock().

Referenced by tryGetBlocksInSameRegion().

tryGetBlocksInSameRegion()

bool tryGetBlocksInSameRegion ( Block *& a, Block *& b )

static

Tries to update the given block references to live in the same region by exploring the relationship of both blocks with respect to their regions.

Definition at line 126 of file Dominance.cpp.

References b, getAncestorBlock(), mlir::Block::getParent(), and traverseAncestors().

Referenced by mlir::detail::DominanceInfoBase< IsPostDom >::findNearestCommonDominator().

Variable Documentation

true

true

Given two iterators into the same block, return "true" if a is before `b.

/ Note: This is a variant of Operation::isBeforeInBlock that operates on / block iterators instead of ops. static bool isBeforeInBlock(Block *block, Block::iterator a, Block::iterator b) { if (a == b) return false; if (a == block->end()) return false; if (b == block->end()) return true; return a->isBeforeInBlock(&*b); }

template <bool IsPostDom> bool DominanceInfoBase<IsPostDom>::properlyDominatesImpl( Block *aBlock, Block::iterator aIt, Block *bBlock, Block::iterator bIt, bool enclosingOk) const { assert(aBlock && bBlock && "expected non-null blocks");

A block iterator (post)dominates, but does not properly (post)dominate, itself unless this is a graph region. if (aBlock == bBlock && aIt == bIt) return !hasSSADominance(aBlock);

If the iterators are in different regions, then normalize one into the other. Region *aRegion = aBlock->getParent(); if (aRegion != bBlock->getParent()) { Scoot up b's region tree until we find a location in A's region that encloses it. If this fails, then we know there is no (post)dom relation. if (!aRegion) { bBlock = nullptr; bIt = Block::iterator(); } else { std::tie(bBlock, bIt) = findAncestorIteratorInRegion(aRegion, bBlock, bIt); } if (!bBlock) return false; assert(bBlock->getParent() == aRegion && "expected block in regionA");

If 'a' encloses 'b', then we consider it to (post)dominate. if (aBlock == bBlock && aIt == bIt && enclosingOk) return true; }

Ok, they are in the same region now. if (aBlock == bBlock) { Dominance changes based on the region type. In a region with SSA dominance, uses inside the same block must follow defs. In other regions kinds, uses and defs can come in any order inside a block. if (!hasSSADominance(aBlock)) return true; if constexpr (IsPostDom) { return isBeforeInBlock(aBlock, bIt, aIt); } else { return isBeforeInBlock(aBlock, aIt, bIt); } }

If the blocks are different, use DomTree to resolve the query. return getDomTree(aRegion).properlyDominates(aBlock, bBlock); }

/ Return true if the specified block is reachable from the entry block of / its region. template <bool IsPostDom> bool DominanceInfoBase<IsPostDom>::isReachableFromEntry(Block *a) const { If this is the first block in its region, then it is obviously reachable. Region *region = a->getParent(); if (&region->front() == a) return true;

Otherwise this is some block in a multi-block region. Check DomTree. return getDomTree(region).isReachableFromEntry(a); }

template class detail::DominanceInfoBase</*IsPostDom=

Definition at line 316 of file Dominance.cpp.

Referenced by mlir::tracing::Breakpoint::Breakpoint(), mlir::transform::BuildOnly< DerivedTy >::BuildOnly(), mlir::detail::CallbackOstream::CallbackOstream(), mlir::detail::ElementsAttrIndexer::ElementsAttrIndexer(), mlir::transform::gpu::GpuLaneIdBuilder::GpuLaneIdBuilder(), mlir::presburger::LexSimplexBase::LexSimplexBase(), mlir::presburger::LexSimplexBase::LexSimplexBase(), mlir::PassManager::PassManager(), mlir::PassManager::PassManager(), mlir::PassNameCLParser::PassNameCLParser(), mlir::python::PyShapedTypeComponents::PyShapedTypeComponents(), mlir::python::PyShapedTypeComponents::PyShapedTypeComponents(), mlir::vector::ScalableValueBoundsConstraintSet::ScalableValueBoundsConstraintSet(), mlir::ShapedTypeComponents::ShapedTypeComponents(), mlir::ShapedTypeComponents::ShapedTypeComponents(), mlir::sparse_tensor::SparseTensorCOO< V >::SparseTensorCOO(), and mlir::SparsificationOptions::SparsificationOptions().