#include "mlir/Transforms/CFGToSCF.h"
#include "mlir/IR/RegionGraphTraits.h"
#include "mlir/Interfaces/ControlFlowInterfaces.h"
#include "mlir/Interfaces/SideEffectInterfaces.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"

Functions
static MutableOperandRange	getMutableSuccessorOperands (Block *block, unsigned successorIndex)
	Returns the mutable operand range used to transfer operands from `block` to its successor with the given index. More...

static OperandRange	getSuccessorOperands (Block *block, unsigned successorIndex)
	Return the operand range used to transfer operands from `block` to its successor with the given index. More...

static void	addBlockArgumentsFromOther (Block block, Block other)
	Appends all the block arguments from `other` to the block arguments of `block`, copying their types and locations. More...

static auto	successorEdges (Block *block)
	Returns a range of all edges from `block` to each of its successors. More...

static CycleEdges	calculateCycleEdges (const llvm::SmallSetVector< Block *, 4 > &cycles)
	Calculates entry, exit and back edges of the given cycle. More...

static EdgeMultiplexer	createSingleEntryBlock (Location loc, ArrayRef< Edge > entryEdges, function_ref< Value(unsigned)> getSwitchValue, function_ref< Value(Type)> getUndefValue, CFGToSCFInterface &interface)
	Creates a single entry block out of multiple entry edges using an edge multiplexer and returns it. More...

static FailureOr< StructuredLoopProperties >	createSingleExitingLatch (Location loc, ArrayRef< Edge > backEdges, ArrayRef< Edge > exitEdges, function_ref< Value(unsigned)> getSwitchValue, function_ref< Value(Type)> getUndefValue, CFGToSCFInterface &interface, ReturnLikeExitCombiner &exitCombiner)
	Transforms a loop into a structured loop with only a single back edge and exiting edge, originating from the same block. More...

static SmallVector< Value >	transformToReduceLoop (Block loopHeader, Block exitBlock, const llvm::SmallSetVector< Block *, 4 > &loopBlocks, function_ref< Value(Type)> getUndefValue, DominanceInfo &dominanceInfo)
	Transforms a structured loop into a loop in reduce form. More...

static FailureOr< SmallVector< Block * > >	transformCyclesToSCFLoops (Block *regionEntry, function_ref< Value(unsigned)> getSwitchValue, function_ref< Value(Type)> getUndefValue, CFGToSCFInterface &interface, DominanceInfo &dominanceInfo, ReturnLikeExitCombiner &exitCombiner)
	Transforms all outer-most cycles in the region with the region entry `regionEntry` into structured loops. More...

static void	createSingleExitBranchRegion (ArrayRef< Block * > branchRegion, Block continuation, SmallVectorImpl< std::pair< Block , SmallVector< Value >>> &createdEmptyBlocks, Region &conditionalRegion)
	Makes sure the branch region only has a single exit. More...

static bool	isRegionExitBlock (Block *block)
	Returns true if this block is an exit block of the region. More...

static FailureOr< SmallVector< Block * > >	transformToStructuredCFBranches (Block *regionEntry, function_ref< Value(unsigned)> getSwitchValue, function_ref< Value(Type)> getUndefValue, CFGToSCFInterface &interface, DominanceInfo &dominanceInfo)
	Transforms the first occurrence of conditional control flow in `regionEntry` into conditionally executed regions. More...

static ReturnLikeExitCombiner	createSingleExitBlocksForReturnLike (Region &region, function_ref< Value(unsigned)> getSwitchValue, CFGToSCFInterface &interface)
	Transforms the region to only have a single block for every kind of return-like operation that all previous occurrences of the return-like op branch to. More...

static LogicalResult	checkTransformationPreconditions (Region &region)
	Checks all preconditions of the transformation prior to any transformations. More...

Function Documentation

◆ addBlockArgumentsFromOther()

static void addBlockArgumentsFromOther	(	Block *	block,
		Block *	other
	)

static

Appends all the block arguments from other to the block arguments of block, copying their types and locations.

Definition at line 149 of file CFGToSCF.cpp.

References mlir::Block::addArgument(), and mlir::Block::getArguments().

Referenced by createSingleExitBranchRegion(), and transformCyclesToSCFLoops().

◆ calculateCycleEdges()

static CycleEdges calculateCycleEdges ( const llvm::SmallSetVector< Block *, 4 > & cycles )

static

Calculates entry, exit and back edges of the given cycle.

Definition at line 480 of file CFGToSCF.cpp.

References mlir::detail::enumerate(), mlir::Block::getSuccessors(), mlir::Block::pred_begin(), and mlir::Block::pred_end().

Referenced by transformCyclesToSCFLoops().

◆ checkTransformationPreconditions()

static LogicalResult checkTransformationPreconditions ( Region & region )

static

Checks all preconditions of the transformation prior to any transformations.

Returns failure if any precondition is violated.

Definition at line 1229 of file CFGToSCF.cpp.

References mlir::WalkResult::advance(), mlir::Operation::emitOpError(), mlir::failure(), mlir::Block::front(), mlir::Region::getBlocks(), mlir::Operation::getNumSuccessors(), mlir::SuccessorOperands::getProducedOperandCount(), mlir::Block::hasNoPredecessors(), mlir::WalkResult::interrupt(), mlir::Block::isEntryBlock(), mlir::isMemoryEffectFree(), mlir::Region::walk(), and mlir::WalkResult::wasInterrupted().

Referenced by mlir::transformCFGToSCF().

◆ createSingleEntryBlock()

static EdgeMultiplexer createSingleEntryBlock	(	Location	loc,
		ArrayRef< Edge >	entryEdges,
		function_ref< Value(unsigned)>	getSwitchValue,
		function_ref< Value(Type)>	getUndefValue,
		CFGToSCFInterface &	interface
	)

static

Creates a single entry block out of multiple entry edges using an edge multiplexer and returns it.

Definition at line 519 of file CFGToSCF.cpp.

References mlir::OpBuilder::atBlockBegin().

Referenced by transformCyclesToSCFLoops(), and transformToStructuredCFBranches().

◆ createSingleExitBlocksForReturnLike()

static ReturnLikeExitCombiner createSingleExitBlocksForReturnLike	(	Region &	region,
		function_ref< Value(unsigned)>	getSwitchValue,
		CFGToSCFInterface &	interface
	)

static

Transforms the region to only have a single block for every kind of return-like operation that all previous occurrences of the return-like op branch to.

If the region only contains a single kind of return-like operation, it creates a single-entry and single-exit region.

Definition at line 1213 of file CFGToSCF.cpp.

References mlir::Region::getBlocks(), mlir::Block::getNumSuccessors(), and mlir::Block::getTerminator().

Referenced by mlir::transformCFGToSCF().

◆ createSingleExitBranchRegion()

static void createSingleExitBranchRegion	(	ArrayRef< Block * >	branchRegion,
		Block *	continuation,
		SmallVectorImpl< std::pair< Block *, SmallVector< Value >>> &	createdEmptyBlocks,
		Region &	conditionalRegion
	)

static

Makes sure the branch region only has a single exit.

This is required by the recursive part of the algorithm, as it expects the CFG to be single-entry and single-exit. This is done by simply creating an empty block if there is more than one block with an edge to the continuation block. All blocks with edges to the continuation are then redirected to this block. A region terminator is later placed into the block.

Definition at line 904 of file CFGToSCF.cpp.

References addBlockArgumentsFromOther(), mlir::Block::getArguments(), mlir::Region::push_back(), and successorEdges().

Referenced by transformToStructuredCFBranches().

◆ createSingleExitingLatch()

static FailureOr<StructuredLoopProperties> createSingleExitingLatch	(	Location	loc,
		ArrayRef< Edge >	backEdges,
		ArrayRef< Edge >	exitEdges,
		function_ref< Value(unsigned)>	getSwitchValue,
		function_ref< Value(Type)>	getUndefValue,
		CFGToSCFInterface &	interface,
		ReturnLikeExitCombiner &	exitCombiner
	)

static

Transforms a loop into a structured loop with only a single back edge and exiting edge, originating from the same block.

Definition at line 555 of file CFGToSCF.cpp.

References mlir::OpBuilder::atBlockBegin(), mlir::CFGToSCFInterface::createConditionalBranch(), mlir::CFGToSCFInterface::createUnreachableTerminator(), mlir::failed(), mlir::failure(), mlir::Block::getArguments(), mlir::Block::getNumArguments(), and mlir::Block::insertAfter().

Referenced by transformCyclesToSCFLoops().

◆ getMutableSuccessorOperands()

static MutableOperandRange getMutableSuccessorOperands	(	Block *	block,
		unsigned	successorIndex
	)

static

Returns the mutable operand range used to transfer operands from block to its successor with the given index.

The returned range being mutable allows us to modify the operands being transferred.

Definition at line 133 of file CFGToSCF.cpp.

References mlir::SuccessorOperands::getMutableForwardedOperands(), and mlir::Block::getTerminator().

Referenced by getSuccessorOperands(), transformToReduceLoop(), and transformToStructuredCFBranches().

◆ getSuccessorOperands()

static OperandRange getSuccessorOperands	(	Block *	block,
		unsigned	successorIndex
	)

static

Return the operand range used to transfer operands from block to its successor with the given index.

Definition at line 142 of file CFGToSCF.cpp.

References getMutableSuccessorOperands().

Referenced by transformToReduceLoop(), and transformToStructuredCFBranches().

◆ isRegionExitBlock()

static bool isRegionExitBlock ( Block * block )

static

Returns true if this block is an exit block of the region.

Definition at line 943 of file CFGToSCF.cpp.

References mlir::Block::getNumSuccessors().

Referenced by transformToStructuredCFBranches().

◆ successorEdges()

static auto successorEdges ( Block * block )

static

Returns a range of all edges from block to each of its successors.

Definition at line 473 of file CFGToSCF.cpp.

References mlir::Block::getNumSuccessors().

Referenced by createSingleExitBranchRegion(), transformToReduceLoop(), and transformToStructuredCFBranches().

◆ transformCyclesToSCFLoops()

static FailureOr<SmallVector<Block *> > transformCyclesToSCFLoops	(	Block *	regionEntry,
		function_ref< Value(unsigned)>	getSwitchValue,
		function_ref< Value(Type)>	getUndefValue,
		CFGToSCFInterface &	interface,
		DominanceInfo &	dominanceInfo,
		ReturnLikeExitCombiner &	exitCombiner
	)

static

Transforms all outer-most cycles in the region with the region entry regionEntry into structured loops.

Returns the entry blocks of any newly created regions potentially requiring further transformations.

Definition at line 803 of file CFGToSCF.cpp.

References addBlockArgumentsFromOther(), mlir::OpBuilder::atBlockBegin(), calculateCycleEdges(), createSingleEntryBlock(), createSingleExitingLatch(), mlir::CFGToSCFInterface::createStructuredDoWhileLoopOp(), mlir::Block::erase(), mlir::Operation::erase(), mlir::failed(), mlir::failure(), mlir::Block::front(), mlir::Block::getArguments(), mlir::Region::getBlocks(), mlir::Operation::getLoc(), mlir::Block::getOperations(), mlir::Block::getParent(), mlir::Operation::getSuccessor(), mlir::Block::getTerminator(), mlir::Block::insertBefore(), mlir::Region::push_back(), mlir::Operation::remove(), mlir::IRObjectWithUseList< OperandType >::replaceAllUsesWith(), and transformToReduceLoop().

Referenced by mlir::transformCFGToSCF().

◆ transformToReduceLoop()

static SmallVector<Value> transformToReduceLoop	(	Block *	loopHeader,
		Block *	exitBlock,
		const llvm::SmallSetVector< Block *, 4 > &	loopBlocks,
		function_ref< Value(Type)>	getUndefValue,
		DominanceInfo &	dominanceInfo
	)

static

Transforms a structured loop into a loop in reduce form.

Reduce form is defined as a structured loop where: (0) No values defined within the loop body are used outside the loop body. (1) The block arguments and successor operands of the exit block are equal to the block arguments of the loop header and the successor operands of the back edge.

This is required for many structured control flow ops as they tend to not have separate "loop result arguments" and "loop iteration arguments" at the end of the block. Rather, the "loop iteration arguments" from the last iteration are the result of the loop.

Note that the requirement of (0) is shared with LCSSA form in LLVM. However, due to this being a structured loop instead of a general loop, we do not require complicated dominance algorithms nor SSA updating making this implementation easier than creating a generic LCSSA transformation pass.

Definition at line 658 of file CFGToSCF.cpp.

References mlir::Block::addArgument(), mlir::MutableOperandRange::append(), mlir::DominanceInfo::dominates(), mlir::Block::getArguments(), mlir::Operation::getBlock(), getMutableSuccessorOperands(), mlir::Block::getNumArguments(), mlir::detail::IROperandBase::getOwner(), mlir::Block::getParent(), mlir::Block::getParentOp(), mlir::Block::getPredecessors(), mlir::Block::getSinglePredecessor(), mlir::Block::getSuccessor(), getSuccessorOperands(), mlir::Block::pred_begin(), mlir::Block::pred_end(), and successorEdges().

Referenced by transformCyclesToSCFLoops().

◆ transformToStructuredCFBranches()

static FailureOr<SmallVector<Block *> > transformToStructuredCFBranches	(	Block *	regionEntry,
		function_ref< Value(unsigned)>	getSwitchValue,
		function_ref< Value(Type)>	getUndefValue,
		CFGToSCFInterface &	interface,
		DominanceInfo &	dominanceInfo
	)

static

Transforms the first occurrence of conditional control flow in regionEntry into conditionally executed regions.

Returns the entry block of the created regions and the region after the conditional control flow.

Definition at line 950 of file CFGToSCF.cpp.

References mlir::OpBuilder::atBlockEnd(), mlir::OpBuilder::atBlockTerminator(), createSingleEntryBlock(), createSingleExitBranchRegion(), mlir::CFGToSCFInterface::createStructuredBranchRegionOp(), mlir::CFGToSCFInterface::createStructuredBranchRegionTerminatorOp(), mlir::Block::end(), mlir::Block::erase(), mlir::Operation::erase(), mlir::Block::eraseArguments(), mlir::failed(), mlir::failure(), mlir::Block::front(), mlir::Block::getArguments(), mlir::Block::getArgumentTypes(), mlir::MutableOperandRange::getAsOperandRange(), mlir::Operation::getLoc(), getMutableSuccessorOperands(), mlir::detail::DominanceInfoBase< IsPostDom >::getNode(), mlir::Block::getNumArguments(), mlir::Block::getNumSuccessors(), mlir::Block::getOperations(), mlir::Block::getParent(), mlir::Operation::getResults(), mlir::Block::getSuccessor(), getSuccessorOperands(), mlir::Block::getSuccessors(), mlir::Block::getTerminator(), mlir::IRObjectWithUseList< OperandType >::getUsers(), mlir::detail::DominanceInfoBase< IsPostDom >::invalidate(), isRegionExitBlock(), mlir::Block::pred_begin(), mlir::Block::pred_end(), mlir::Operation::replaceAllUsesWith(), mlir::IRObjectWithUseList< OperandType >::replaceAllUsesWith(), and successorEdges().

Referenced by mlir::transformCFGToSCF().

Functions

Function Documentation

◆ addBlockArgumentsFromOther()

◆ calculateCycleEdges()

◆ checkTransformationPreconditions()

◆ createSingleEntryBlock()

◆ createSingleExitBlocksForReturnLike()

◆ createSingleExitBranchRegion()

◆ createSingleExitingLatch()

◆ getMutableSuccessorOperands()

◆ getSuccessorOperands()

◆ isRegionExitBlock()

◆ successorEdges()

◆ transformCyclesToSCFLoops()

◆ transformToReduceLoop()

◆ transformToStructuredCFBranches()