InductiveRangeCheckElimination.cpp File Reference

#include "llvm/Transforms/Scalar/InductiveRangeCheckElimination.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/PriorityWorklist.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <limits>
#include <optional>
#include <utility>
#include <vector>

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "irce"

Functions
	INITIALIZE_PASS_BEGIN (IRCELegacyPass, "irce", "Inductive range check elimination", false, false) INITIALIZE_PASS_END(IRCELegacyPass
static void	DisableAllLoopOptsOnLoop (Loop &L)
static bool	isSafeDecreasingBound (const SCEV *Start, const SCEV *BoundSCEV, const SCEV *Step, ICmpInst::Predicate Pred, unsigned LatchBrExitIdx, Loop *L, ScalarEvolution &SE)
	Given a loop with an deccreasing induction variable, is it possible to safely calculate the bounds of a new loop using the given Predicate.
static bool	isSafeIncreasingBound (const SCEV *Start, const SCEV *BoundSCEV, const SCEV *Step, ICmpInst::Predicate Pred, unsigned LatchBrExitIdx, Loop *L, ScalarEvolution &SE)
	Given a loop with an increasing induction variable, is it possible to safely calculate the bounds of a new loop using the given Predicate.
static const SCEV *	NoopOrExtend (const SCEV *S, Type *Ty, ScalarEvolution &SE, bool Signed)
	If the type of S matches with Ty, return S.
static std::optional< InductiveRangeCheck::Range >	IntersectSignedRange (ScalarEvolution &SE, const std::optional< InductiveRangeCheck::Range > &R1, const InductiveRangeCheck::Range &R2)
static std::optional< InductiveRangeCheck::Range >	IntersectUnsignedRange (ScalarEvolution &SE, const std::optional< InductiveRangeCheck::Range > &R1, const InductiveRangeCheck::Range &R2)

Variables
static cl::opt< unsigned >	LoopSizeCutoff ("irce-loop-size-cutoff", cl::Hidden, cl::init(64))
static cl::opt< bool >	PrintChangedLoops ("irce-print-changed-loops", cl::Hidden, cl::init(false))
static cl::opt< bool >	PrintRangeChecks ("irce-print-range-checks", cl::Hidden, cl::init(false))
static cl::opt< bool >	SkipProfitabilityChecks ("irce-skip-profitability-checks", cl::Hidden, cl::init(false))
static cl::opt< unsigned >	MinRuntimeIterations ("irce-min-runtime-iterations", cl::Hidden, cl::init(10))
static cl::opt< bool >	AllowUnsignedLatchCondition ("irce-allow-unsigned-latch", cl::Hidden, cl::init(true))
static cl::opt< bool >	AllowNarrowLatchCondition ("irce-allow-narrow-latch", cl::Hidden, cl::init(true), cl::desc("If set to true, IRCE may eliminate wide range checks in loops " "with narrow latch condition."))
static const char *	ClonedLoopTag = "irce.loop.clone"
	irce
Inductive range check	elimination
Inductive range check	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "irce"

Definition at line 126 of file InductiveRangeCheckElimination.cpp.

Function Documentation

DisableAllLoopOptsOnLoop()

static void DisableAllLoopOptsOnLoop ( Loop &  L )

static

Definition at line 425 of file InductiveRangeCheckElimination.cpp.

References Context, llvm::ConstantAsMetadata::get(), llvm::MDNode::get(), llvm::MDString::get(), llvm::ConstantInt::get(), llvm::Type::getInt1Ty(), and llvm::MDNode::replaceOperandWith().

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	IRCELegacyPass	,
		"irce"	,
		"Inductive range check elimination"	,
		false	,
		false
	)

IntersectSignedRange()

static std::optional< InductiveRangeCheck::Range > IntersectSignedRange ( ScalarEvolution &  SE, const std::optional< InductiveRangeCheck::Range > &  R1, const InductiveRangeCheck::Range &  R2  )

static

Definition at line 1711 of file InductiveRangeCheckElimination.cpp.

References assert(), llvm::ScalarEvolution::getSMaxExpr(), llvm::ScalarEvolution::getSMinExpr(), and R2.

IntersectUnsignedRange()

static std::optional< InductiveRangeCheck::Range > IntersectUnsignedRange ( ScalarEvolution &  SE, const std::optional< InductiveRangeCheck::Range > &  R1, const InductiveRangeCheck::Range &  R2  )

static

Definition at line 1740 of file InductiveRangeCheckElimination.cpp.

References assert(), llvm::ScalarEvolution::getUMaxExpr(), llvm::ScalarEvolution::getUMinExpr(), and R2.

isSafeDecreasingBound()

static bool isSafeDecreasingBound ( const SCEV *  Start, const SCEV *  BoundSCEV, const SCEV *  Step, ICmpInst::Predicate  Pred, unsigned  LatchBrExitIdx, Loop *  L, ScalarEvolution &  SE  )

static

Given a loop with an deccreasing induction variable, is it possible to safely calculate the bounds of a new loop using the given Predicate.

Definition at line 656 of file InductiveRangeCheckElimination.cpp.

References assert(), llvm::BitWidth, llvm::dbgs(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getMinusSCEV(), llvm::APInt::getMinValue(), llvm::ScalarEvolution::getOne(), llvm::APInt::getSignedMinValue(), llvm::SCEV::getType(), llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_UGT, llvm::ScalarEvolution::isAvailableAtLoopEntry(), llvm::ScalarEvolution::isKnownNegative(), llvm::ScalarEvolution::isLoopEntryGuardedByCond(), and LLVM_DEBUG.

isSafeIncreasingBound()

static bool isSafeIncreasingBound ( const SCEV *  Start, const SCEV *  BoundSCEV, const SCEV *  Step, ICmpInst::Predicate  Pred, unsigned  LatchBrExitIdx, Loop *  L, ScalarEvolution &  SE  )

static

Given a loop with an increasing induction variable, is it possible to safely calculate the bounds of a new loop using the given Predicate.

Definition at line 705 of file InductiveRangeCheckElimination.cpp.

References assert(), llvm::BitWidth, llvm::dbgs(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getConstant(), llvm::APInt::getMaxValue(), llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getOne(), llvm::APInt::getSignedMaxValue(), llvm::SCEV::getType(), llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_ULT, llvm::ScalarEvolution::isAvailableAtLoopEntry(), llvm::ScalarEvolution::isLoopEntryGuardedByCond(), and LLVM_DEBUG.

NoopOrExtend()

static const SCEV * NoopOrExtend ( const SCEV *  S, Type *  Ty, ScalarEvolution &  SE, bool  Signed  )

static

If the type of S matches with Ty, return S.

Otherwise, return signed or unsigned extension of S to type Ty.

Definition at line 1056 of file InductiveRangeCheckElimination.cpp.

References llvm::ScalarEvolution::getNoopOrSignExtend(), llvm::ScalarEvolution::getNoopOrZeroExtend(), and Signed.

Variable Documentation

AllowNarrowLatchCondition

cl::opt< bool > AllowNarrowLatchCondition("irce-allow-narrow-latch", cl::Hidden, cl::init(true), cl::desc("If set to true, IRCE may eliminate wide range checks in loops " "with narrow latch condition.")) ( "irce-allow-narrow-latch"  , cl::Hidden  , cl::init(true)  , cl::desc("If set to true, IRCE may eliminate wide range checks in loops " "with narrow latch condition.")    )

static

AllowUnsignedLatchCondition

cl::opt< bool > AllowUnsignedLatchCondition("irce-allow-unsigned-latch", cl::Hidden, cl::init(true)) ( "irce-allow-unsigned-latch"  , cl::Hidden  , cl::init(true)    )

static

ClonedLoopTag

const char* ClonedLoopTag = "irce.loop.clone"

static

Definition at line 124 of file InductiveRangeCheckElimination.cpp.

elimination

Inductive range check elimination

Definition at line 284 of file InductiveRangeCheckElimination.cpp.

false

Inductive range check false

Definition at line 285 of file InductiveRangeCheckElimination.cpp.

irce

irce

Definition at line 284 of file InductiveRangeCheckElimination.cpp.

LoopSizeCutoff

cl::opt< unsigned > LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden, cl::init(64)) ( "irce-loop-size-cutoff"  , cl::Hidden  , cl::init(64)    )

static

MinRuntimeIterations

cl::opt< unsigned > MinRuntimeIterations("irce-min-runtime-iterations", cl::Hidden, cl::init(10)) ( "irce-min-runtime-iterations"  , cl::Hidden  , cl::init(10)    )

static

PrintChangedLoops

cl::opt< bool > PrintChangedLoops("irce-print-changed-loops", cl::Hidden, cl::init(false)) ( "irce-print-changed-loops"  , cl::Hidden  , cl::init(false)    )

static

PrintRangeChecks

cl::opt< bool > PrintRangeChecks("irce-print-range-checks", cl::Hidden, cl::init(false)) ( "irce-print-range-checks"  , cl::Hidden  , cl::init(false)    )

static

SkipProfitabilityChecks

cl::opt< bool > SkipProfitabilityChecks("irce-skip-profitability-checks", cl::Hidden, cl::init(false)) ( "irce-skip-profitability-checks"  , cl::Hidden  , cl::init(false)    )

static

Referenced by llvm::IRCEPass::run().