#include "mlir/Dialect/SCF/Utils/Utils.h"
#include "mlir/Analysis/SliceAnalysis.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/PatternMatch.h"
#include "mlir/Interfaces/SideEffectInterfaces.h"
#include "mlir/Support/MathExtras.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"

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 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 LoopParams	emitNormalizedLoopBounds (RewriterBase &rewriter, Location loc, Value lb, Value ub, Value step)
	Transform a loop with a strictly positive step for i = lb to ub step s into a 0-based loop with step 1 for ii = 0 to ceildiv(ub - lb, s) step 1 { i = ii * s + lb Insert the induction variable remapping in the body of `inner`, which is expected to be either `loop` or another loop perfectly nested under `loop`. More...

static void	denormalizeInductionVariable (RewriterBase &rewriter, Location loc, Value normalizedIv, Value origLb, Value origStep)
	Get back the original induction variable values after loop normalization. More...

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)

Function Documentation

◆ ceilDivPositive() [1/2]

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

static

Definition at line 273 of file Utils.cpp.

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

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::Value::getType(), and mlir::Type::isIndex().

◆ 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 563 of file Utils.cpp.

References mlir::OpBuilder::create(), and mlir::Value::getDefiningOp().

Referenced by mlir::coalesceLoops().

◆ denormalizeInductionVariable()

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

static

Get back the original induction variable values after loop normalization.

Definition at line 521 of file Utils.cpp.

References mlir::OpBuilder::create(), mlir::Value::getDefiningOp(), mlir::isConstantIntValue(), and mlir::RewriterBase::replaceAllUsesExcept().

Referenced by mlir::coalesceLoops(), and mlir::collapseParallelLoops().

◆ emitNormalizedLoopBounds()

static LoopParams emitNormalizedLoopBounds	(	RewriterBase &	rewriter,
		Location	loc,
		Value	lb,
		Value	ub,
		Value	step
	)

static

Transform a loop with a strictly positive step for i = lb to ub step s into a 0-based loop with step 1 for ii = 0 to ceildiv(ub - lb, s) step 1 { i = ii * s + lb Insert the induction variable remapping in the body of inner, which is expected to be either loop or another loop perfectly nested under loop.

Insert the definition of new bounds immediate before outer, which is expected to be either loop or its parent in the loop nest.

Definition at line 485 of file Utils.cpp.

References mlir::OpBuilder::create(), mlir::getConstantIntValue(), mlir::Builder::getIntegerAttr(), mlir::Value::getType(), and mlir::Builder::getZeroAttr().

Referenced by mlir::coalesceLoops(), and mlir::collapseParallelLoops().

◆ 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 303 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().

◆ 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 891 of file Utils.cpp.

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

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