#include "mlir/Dialect/SCF/Utils/Utils.h"
#include "mlir/Analysis/SliceAnalysis.h"
#include "mlir/Dialect/Affine/IR/AffineOps.h"
#include "mlir/Dialect/Arith/IR/Arith.h"
#include "mlir/Dialect/Arith/Utils/Utils.h"
#include "mlir/Dialect/Func/IR/FuncOps.h"
#include "mlir/Dialect/SCF/IR/SCF.h"
#include "mlir/IR/BuiltinOps.h"
#include "mlir/IR/IRMapping.h"
#include "mlir/IR/OpDefinition.h"
#include "mlir/IR/PatternMatch.h"
#include "mlir/Interfaces/SideEffectInterfaces.h"
#include "mlir/Transforms/RegionUtils.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include <cstdint>

Macros
#define	DEBUG_TYPE "scf-utils"

#define	DBGS() (llvm::dbgs() << '[' << DEBUG_TYPE << "] ")

#define	LDBG(X) LLVM_DEBUG(DBGS() << X << "\n")

Functions
static Value	ceilDivPositive (OpBuilder &builder, Location loc, Value dividend, int64_t divisor)

static Value	ceilDivPositive (OpBuilder &builder, Location loc, Value dividend, Value divisor)

static std::optional< int64_t >	getConstantTripCount (scf::ForOp forOp)
	Returns the trip count of `forOp` if its' low bound, high bound and step are constants, or optional otherwise. More...

static void	generateUnrolledLoop (Block loopBodyBlock, Value forOpIV, uint64_t unrollFactor, function_ref< Value(unsigned, Value, OpBuilder)> ivRemapFn, function_ref< void(unsigned, Operation , OpBuilder)> annotateFn, ValueRange iterArgs, ValueRange yieldedValues)
	Generates unrolled copies of scf::ForOp 'loopBodyBlock', with associated 'forOpIV' by 'unrollFactor', calling 'ivRemapFn' to remap 'forOpIV' for each unrolled body. More...

static bool	areInnerBoundsInvariant (scf::ForOp forOp)
	Check if bounds of all inner loops are defined outside of `forOp` and return false if not. More...

Range	emitNormalizedLoopBoundsForIndexType (RewriterBase &rewriter, Location loc, OpFoldResult lb, OpFoldResult ub, OpFoldResult step)

static void	denormalizeInductionVariableForIndexType (RewriterBase &rewriter, Location loc, Value normalizedIv, OpFoldResult origLb, OpFoldResult origStep)

static OpFoldResult	getProductOfIndexes (RewriterBase &rewriter, Location loc, ArrayRef< OpFoldResult > values)

static Value	getProductOfIntsOrIndexes (RewriterBase &rewriter, Location loc, ArrayRef< Value > values)
	Helper function to multiply a sequence of values. More...

static std::pair< SmallVector< Value >, SmallPtrSet< Operation *, 2 > >	delinearizeInductionVariable (RewriterBase &rewriter, Location loc, Value linearizedIv, ArrayRef< Value > ubs)
	For each original loop, the value of the induction variable can be obtained by dividing the induction variable of the linearized loop by the total number of iterations of the loops nested in it modulo the number of iterations in this loop (remove the values related to the outer loops): iv_i = floordiv(iv_linear, product-of-loop-ranges-until-i) mod range_i. More...

static LogicalResult	hoistOpsBetween (scf::ForOp outer, scf::ForOp inner)

static LogicalResult	tryIsolateBands (const TileLoops &tileLoops)

template<typename T >
static void	getPerfectlyNestedLoopsImpl (SmallVectorImpl< T > &forOps, T rootForOp, unsigned maxLoops=std::numeric_limits< unsigned >::max())
	Collect perfectly nested loops starting from `rootForOps`. More...

static Loops	stripmineSink (scf::ForOp forOp, Value factor, ArrayRef< scf::ForOp > targets)

template<typename SizeType >
static scf::ForOp	stripmineSink (scf::ForOp forOp, SizeType factor, scf::ForOp target)

Macro Definition Documentation

◆ DBGS

#define DBGS ( ) (llvm::dbgs() << '[' << DEBUG_TYPE << "] ")

Definition at line 37 of file Utils.cpp.

◆ DEBUG_TYPE

#define DEBUG_TYPE "scf-utils"

Definition at line 36 of file Utils.cpp.

◆ LDBG

#define LDBG ( X ) LLVM_DEBUG(DBGS() << X << "\n")

Definition at line 38 of file Utils.cpp.

Function Documentation

◆ areInnerBoundsInvariant()

static bool areInnerBoundsInvariant ( scf::ForOp forOp )

static

Check if bounds of all inner loops are defined outside of forOp and return false if not.

Definition at line 502 of file Utils.cpp.

References mlir::WalkResult::advance(), and mlir::WalkResult::interrupt().

Referenced by mlir::loopUnrollJamByFactor().

◆ ceilDivPositive() [1/2]

static Value ceilDivPositive	(	OpBuilder &	builder,
		Location	loc,
		Value	dividend,
		int64_t	divisor
	)

static

Definition at line 271 of file Utils.cpp.

References mlir::OpBuilder::create(), mlir::Builder::getIntegerAttr(), mlir::Value::getType(), and mlir::Type::isIntOrIndex().

Referenced by mlir::extractFixedOuterLoops(), and mlir::loopUnrollByFactor().

◆ ceilDivPositive() [2/2]

static Value ceilDivPositive	(	OpBuilder &	builder,
		Location	loc,
		Value	dividend,
		Value	divisor
	)

static

Definition at line 289 of file Utils.cpp.

References mlir::OpBuilder::create(), mlir::Builder::getOneAttr(), mlir::Value::getType(), and mlir::Type::isIntOrIndex().

◆ delinearizeInductionVariable()

static std::pair<SmallVector<Value>, SmallPtrSet<Operation *, 2> > delinearizeInductionVariable	(	RewriterBase &	rewriter,
		Location	loc,
		Value	linearizedIv,
		ArrayRef< Value >	ubs
	)

static

For each original loop, the value of the induction variable can be obtained by dividing the induction variable of the linearized loop by the total number of iterations of the loops nested in it modulo the number of iterations in this loop (remove the values related to the outer loops): iv_i = floordiv(iv_linear, product-of-loop-ranges-until-i) mod range_i.

Compute these iteratively from the innermost loop by creating a "running quotient" of division by the range.

Definition at line 845 of file Utils.cpp.

References mlir::OpBuilder::create(), mlir::Operation::getResults(), mlir::Value::getType(), and mlir::Type::isIndex().

Referenced by mlir::coalesceLoops().

◆ denormalizeInductionVariableForIndexType()

static void denormalizeInductionVariableForIndexType	(	RewriterBase &	rewriter,
		Location	loc,
		Value	normalizedIv,
		OpFoldResult	origLb,
		OpFoldResult	origStep
	)

static

Definition at line 739 of file Utils.cpp.

References mlir::bindDims(), mlir::bindSymbols(), mlir::Builder::getContext(), mlir::getValueOrCreateConstantIndexOp(), mlir::isConstantIntValue(), mlir::affine::makeComposedFoldedAffineApply(), and mlir::RewriterBase::replaceAllUsesExcept().

Referenced by mlir::denormalizeInductionVariable().

◆ emitNormalizedLoopBoundsForIndexType()

Range emitNormalizedLoopBoundsForIndexType	(	RewriterBase &	rewriter,
		Location	loc,
		OpFoldResult	lb,
		OpFoldResult	ub,
		OpFoldResult	step
	)

Definition at line 679 of file Utils.cpp.

References mlir::bindSymbols(), mlir::Builder::getContext(), mlir::Builder::getIndexAttr(), mlir::affine::makeComposedFoldedAffineApply(), mlir::Range::offset, mlir::Range::size, and mlir::Range::stride.

Referenced by mlir::emitNormalizedLoopBounds().

◆ generateUnrolledLoop()

static void generateUnrolledLoop	(	Block *	loopBodyBlock,
		Value	forOpIV,
		uint64_t	unrollFactor,
		function_ref< Value(unsigned, Value, OpBuilder)>	ivRemapFn,
		function_ref< void(unsigned, Operation *, OpBuilder)>	annotateFn,
		ValueRange	iterArgs,
		ValueRange	yieldedValues
	)

static

Generates unrolled copies of scf::ForOp 'loopBodyBlock', with associated 'forOpIV' by 'unrollFactor', calling 'ivRemapFn' to remap 'forOpIV' for each unrolled body.

If specified, annotates the Ops in each unrolled iteration using annotateFn.

Definition at line 323 of file Utils.cpp.

References mlir::OpBuilder::atBlockTerminator(), mlir::Block::begin(), mlir::Operation::clone(), mlir::Block::end(), mlir::Block::getTerminator(), mlir::IRMapping::lookup(), mlir::IRMapping::map(), mlir::Operation::setOperands(), and mlir::Value::use_empty().

Referenced by mlir::loopUnrollByFactor().

◆ getConstantTripCount()

static std::optional<int64_t> getConstantTripCount ( scf::ForOp forOp )

static

Returns the trip count of forOp if its' low bound, high bound and step are constants, or optional otherwise.

Trip count is computed as ceilDiv(highBound - lowBound, step).

Definition at line 303 of file Utils.cpp.

References mlir::getConstantIntValue().

Referenced by mlir::loopUnrollByFactor(), and mlir::loopUnrollJamByFactor().

◆ getPerfectlyNestedLoopsImpl()

template<typename T >

static void getPerfectlyNestedLoopsImpl	(	SmallVectorImpl< T > &	forOps,
		T	rootForOp,
		unsigned	maxLoops = `std::numeric_limits<unsigned>::max()`
	)

static

Collect perfectly nested loops starting from rootForOps.

Loops are perfectly nested if each loop is the first and only non-terminator operation in the parent loop. Collect at most maxLoops loops and append them to forOps.

Definition at line 1219 of file Utils.cpp.

References mlir::Block::begin(), mlir::Block::end(), and mlir::Block::front().

Referenced by mlir::extractFixedOuterLoops(), mlir::getPerfectlyNestedLoops(), and mlir::tilePerfectlyNested().