#include "mlir/Transforms/RegionUtils.h"
#include "mlir/Analysis/SliceAnalysis.h"
#include "mlir/Analysis/TopologicalSortUtils.h"
#include "mlir/IR/Block.h"
#include "mlir/IR/Dominance.h"
#include "mlir/IR/IRMapping.h"
#include "mlir/IR/Operation.h"
#include "mlir/IR/PatternMatch.h"
#include "mlir/IR/Value.h"
#include "mlir/Interfaces/ControlFlowInterfaces.h"
#include "mlir/Interfaces/SideEffectInterfaces.h"
#include "mlir/Support/LogicalResult.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVectorExtras.h"
#include "llvm/Support/DebugLog.h"
#include <deque>
#include <iterator>

Macros
#define	DEBUG_TYPE "region-utils"

Functions
static bool	isUseSpeciallyKnownDead (OpOperand &use, LiveMap &liveMap)
static void	processValue (Value value, LiveMap &liveMap)
static void	propagateLiveness (Region &region, LiveMap &liveMap)
static void	propagateTerminatorLiveness (Operation *op, LiveMap &liveMap)
static void	propagateLiveness (Operation *op, LiveMap &liveMap)
static void	eraseTerminatorSuccessorOperands (Operation *terminator, LiveMap &liveMap)
static LogicalResult	deleteDeadness (RewriterBase &rewriter, MutableArrayRef< Region > regions, LiveMap &liveMap)
static bool	ableToUpdatePredOperands (Block *block)
	Returns true if the predecessor terminators of the given block can not have their operands updated.
static SmallVector< SmallVector< Value, 8 >, 2 >	pruneRedundantArguments (const SmallVector< SmallVector< Value, 8 >, 2 > &newArguments, RewriterBase &rewriter, unsigned numOldArguments, Block *block)
	Prunes the redundant list of new arguments.
static LogicalResult	mergeIdenticalBlocks (RewriterBase &rewriter, Region &region)
	Identify identical blocks within the given region and merge them, inserting new block arguments as necessary.
static LogicalResult	mergeIdenticalBlocks (RewriterBase &rewriter, MutableArrayRef< Region > regions)
	Identify identical blocks within the given regions and merge them, inserting new block arguments as necessary.
static LogicalResult	dropRedundantArguments (RewriterBase &rewriter, Block &block)
	If a block's argument is always the same across different invocations, then drop the argument and use the value directly inside the block.
static LogicalResult	dropRedundantArguments (RewriterBase &rewriter, MutableArrayRef< Region > regions)
	This optimization drops redundant argument to blocks.
static bool	blockArgsDominateInsertionPoint (const llvm::SetVector< Operation * > &slice, Operation insertionPoint, DominanceInfo &dominance, Operation *failingOp=nullptr)
	Check if moving operations in the slice before insertionPoint would break dominance due to block argument operands.
static bool	hasIsolatedRegionBetween (Operation op, Block ancestorBlock)
	Check if any region between an operation and an ancestor block is isolated from above.

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "region-utils"

Definition at line 34 of file RegionUtils.cpp.

Function Documentation

◆ ableToUpdatePredOperands()

bool ableToUpdatePredOperands ( Block * block )

static

Returns true if the predecessor terminators of the given block can not have their operands updated.

Definition at line 836 of file RegionUtils.cpp.

References mlir::Block::pred_begin(), and mlir::Block::pred_end().

◆ blockArgsDominateInsertionPoint()

bool blockArgsDominateInsertionPoint	(	const llvm::SetVector< Operation * > &	slice,
		Operation *	insertionPoint,
		DominanceInfo &	dominance,
		Operation **	failingOp = nullptr )

static

Check if moving operations in the slice before insertionPoint would break dominance due to block argument operands.

Returns true if all block args dominate the insertion point (no issue), false otherwise. If failingOp is provided, it will be set to the first problematic op.

For operands defined by ops: either the defining op is in the slice (so dominance preserved), or it already dominates insertionPoint (otherwise it would be in the slice). So we only need to check block argument operands, both as direct operands and as values captured inside regions.

Definition at line 1243 of file RegionUtils.cpp.

References mlir::DominanceInfo::dominates(), mlir::Operation::getBlock(), mlir::BlockArgument::getOwner(), and mlir::getUsedValuesDefinedAbove().

Referenced by mlir::moveOperationDependencies(), and mlir::moveValueDefinitions().

◆ deleteDeadness()

LogicalResult deleteDeadness	(	RewriterBase &	rewriter,
		MutableArrayRef< Region >	regions,
		LiveMap &	liveMap )

static

Definition at line 443 of file RegionUtils.cpp.

References deleteDeadness(), mlir::Region::empty(), mlir::RewriterBase::eraseOp(), eraseTerminatorSuccessorOperands(), mlir::Region::front(), mlir::Region::getBlocks(), mlir::Region::hasOneBlock(), and success().

Referenced by deleteDeadness(), and mlir::runRegionDCE().

◆ dropRedundantArguments() [1/2]

LogicalResult dropRedundantArguments	(	RewriterBase &	rewriter,
		Block &	block )

static

If a block's argument is always the same across different invocations, then drop the argument and use the value directly inside the block.

Definition at line 1092 of file RegionUtils.cpp.

References mlir::SuccessorOperands::erase(), mlir::Block::eraseArgument(), mlir::Block::getArguments(), mlir::SuccessorOperands::isOperandProduced(), mlir::Block::pred_begin(), mlir::Block::pred_end(), mlir::RewriterBase::replaceAllUsesWith(), and success().

Referenced by dropRedundantArguments(), and mlir::simplifyRegions().

◆ dropRedundantArguments() [2/2]

LogicalResult dropRedundantArguments	(	RewriterBase &	rewriter,
		MutableArrayRef< Region >	regions )

static

This optimization drops redundant argument to blocks.

I.e., if a given argument to a block receives the same value from each of the block predecessors, we can remove the argument from the block and use directly the original value. This is a simple example:

cond = llvm.call @rand() : () -> i1 val0 = llvm.mlir.constant(1 : i64) : i64 val1 = llvm.mlir.constant(2 : i64) : i64 val2 = llvm.mlir.constant(3 : i64) : i64 llvm.cond_br cond, ^bb1(val0 : i64, val1 : i64), ^bb2(val0 : i64, val2 : i64)

^bb1(arg0 : i64, arg1 : i64): llvm.call @foo(arg0, arg1)

The previous IR can be rewritten as: cond = llvm.call @rand() : () -> i1 val0 = llvm.mlir.constant(1 : i64) : i64 val1 = llvm.mlir.constant(2 : i64) : i64 val2 = llvm.mlir.constant(3 : i64) : i64 llvm.cond_br cond, ^bb1(val1 : i64), ^bb2(val2 : i64)

^bb1(arg0 : i64): llvm.call @foo(val0, arg0)

Definition at line 1184 of file RegionUtils.cpp.

References dropRedundantArguments(), and success().

◆ eraseTerminatorSuccessorOperands()

void eraseTerminatorSuccessorOperands	(	Operation *	terminator,
		LiveMap &	liveMap )

static

Definition at line 417 of file RegionUtils.cpp.

References mlir::SuccessorOperands::erase(), mlir::Block::getArgument(), mlir::Operation::getNumSuccessors(), mlir::Operation::getSuccessor(), and mlir::SuccessorOperands::size().

Referenced by deleteDeadness().

◆ hasIsolatedRegionBetween()

bool hasIsolatedRegionBetween	(	Operation *	op,
		Block *	ancestorBlock )

static

Check if any region between an operation and an ancestor block is isolated from above.

If so, moving the operation out would break the isolation semantics.

Definition at line 1289 of file RegionUtils.cpp.

References mlir::Block::getParent(), mlir::Region::getParentOp(), mlir::Operation::getParentRegion(), and mlir::Operation::hasTrait().

Referenced by mlir::moveOperationDependencies(), and mlir::moveValueDefinitions().

◆ isUseSpeciallyKnownDead()

bool isUseSpeciallyKnownDead	(	OpOperand &	use,
		LiveMap &	liveMap )

static

Definition at line 312 of file RegionUtils.cpp.

References mlir::OpOperand::getOperandNumber(), mlir::detail::IROperandBase::getOwner(), and mlir::Operation::hasTrait().

◆ mergeIdenticalBlocks() [1/2]

LogicalResult mergeIdenticalBlocks	(	RewriterBase &	rewriter,
		MutableArrayRef< Region >	regions )

static

Identify identical blocks within the given regions and merge them, inserting new block arguments as necessary.

Definition at line 1067 of file RegionUtils.cpp.

References mergeIdenticalBlocks(), and success().

◆ mergeIdenticalBlocks() [2/2]

LogicalResult mergeIdenticalBlocks	(	RewriterBase &	rewriter,
		Region &	region )

static

Identify identical blocks within the given region and merge them, inserting new block arguments as necessary.

Returns success if any blocks were merged, failure otherwise.

Definition at line 1011 of file RegionUtils.cpp.

References mlir::Region::empty(), mlir::Block::getArguments(), mlir::Operation::getRegions(), mlir::Block::getSuccessors(), mlir::Region::hasOneBlock(), and success().

Referenced by mergeIdenticalBlocks(), and mlir::simplifyRegions().

◆ processValue()

void processValue	(	Value	value,
		LiveMap &	liveMap )

static

Definition at line 335 of file RegionUtils.cpp.

References mlir::Value::getUses().

Referenced by getBackwardSliceImpl(), propagateLiveness(), and propagateLiveness().

◆ propagateLiveness() [1/2]

void propagateLiveness	(	Operation *	op,
		LiveMap &	liveMap )

static

Definition at line 371 of file RegionUtils.cpp.

References mlir::Operation::getRegions(), mlir::Operation::getResults(), mlir::Operation::hasTrait(), processValue(), propagateLiveness(), propagateTerminatorLiveness(), and mlir::wouldOpBeTriviallyDead().

◆ propagateLiveness() [2/2]

void propagateLiveness	(	Region &	region,
		LiveMap &	liveMap )

static

Definition at line 393 of file RegionUtils.cpp.

References mlir::Region::empty(), mlir::Region::front(), processValue(), and propagateLiveness().

Referenced by propagateLiveness(), propagateLiveness(), and mlir::runRegionDCE().

◆ propagateTerminatorLiveness()

void propagateTerminatorLiveness	(	Operation *	op,
		LiveMap &	liveMap )

static

Definition at line 347 of file RegionUtils.cpp.

References mlir::Block::getArgument(), mlir::Operation::getNumSuccessors(), mlir::SuccessorOperands::getProducedOperandCount(), mlir::Operation::getSuccessor(), and mlir::Operation::getSuccessors().

Referenced by propagateLiveness().

◆ pruneRedundantArguments()

SmallVector< SmallVector< Value, 8 >, 2 > pruneRedundantArguments	(	const SmallVector< SmallVector< Value, 8 >, 2 > &	newArguments,
		RewriterBase &	rewriter,
		unsigned	numOldArguments,
		Block *	block )

static

Prunes the redundant list of new arguments.

E.g., if we are passing an argument list like [x, y, z, x] this would return [x, y, z] and it would update the block (to whom the argument are passed to) accordingly. The new arguments are passed as arguments at the back of the block, hence we need to know how many numOldArguments were before, in order to correctly replace the new arguments in the block

Definition at line 850 of file RegionUtils.cpp.

References mlir::Block::eraseArgument(), mlir::Block::getArgument(), mlir::Block::getArguments(), mlir::RewriterBase::replaceAllUsesWith(), and replacement().

Macros

Functions

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ ableToUpdatePredOperands()

◆ blockArgsDominateInsertionPoint()

◆ deleteDeadness()

◆ dropRedundantArguments() [1/2]

◆ dropRedundantArguments() [2/2]

◆ eraseTerminatorSuccessorOperands()

◆ hasIsolatedRegionBetween()

◆ isUseSpeciallyKnownDead()

◆ mergeIdenticalBlocks() [1/2]

◆ mergeIdenticalBlocks() [2/2]

◆ processValue()

◆ propagateLiveness() [1/2]

◆ propagateLiveness() [2/2]

◆ propagateTerminatorLiveness()

◆ pruneRedundantArguments()