MLIR  19.0.0git
Functions
CFGToSCF.cpp File Reference
#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"

Go to the source code of this file.

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< ValuetransformToReduceLoop (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

◆ 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::Block::getArguments(), mlir::Block::getNumArguments(), mlir::getType(), 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

◆ 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