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/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/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopConstrainer.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
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< LoopConstrainer::SubRanges >	calculateSubRanges (ScalarEvolution &SE, const Loop &L, InductiveRangeCheck::Range &Range, const LoopStructure &MainLoopStructure)
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 cl::opt< unsigned >	MaxTypeSizeForOverflowCheck ("irce-max-type-size-for-overflow-check", cl::Hidden, cl::init(32), cl::desc("Maximum size of range check type for which can be produced runtime " "overflow check of its limit's computation"))
static cl::opt< bool >	PrintScaledBoundaryRangeChecks ("irce-print-scaled-boundary-range-checks", cl::Hidden, cl::init(false))

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "irce"

Definition at line 133 of file InductiveRangeCheckElimination.cpp.

Function Documentation

calculateSubRanges()

static std::optional< LoopConstrainer::SubRanges > calculateSubRanges ( ScalarEvolution &  SE, const Loop &  L, InductiveRangeCheck::Range &  Range, const LoopStructure &  MainLoopStructure  )

static

Definition at line 565 of file InductiveRangeCheckElimination.cpp.

References AllowNarrowLatchCondition, End, llvm::LoopStructure::ExitCountTy, llvm::ScalarEvolution::getAddExpr(), llvm::IntegerType::getBitWidth(), llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getOne(), llvm::ScalarEvolution::getSCEV(), llvm::ScalarEvolution::getSMaxExpr(), llvm::ScalarEvolution::getSMinExpr(), llvm::ScalarEvolution::getUMaxExpr(), llvm::ScalarEvolution::getUMinExpr(), llvm::LoopStructure::IndVarIncreasing, llvm::LoopStructure::IndVarStart, llvm::ScalarEvolution::isKnownPredicate(), llvm::LoopStructure::IsSignedPredicate, llvm::LoopStructure::LoopExitAt, and NoopOrExtend().

IntersectSignedRange()

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

static

Definition at line 827 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 856 of file InductiveRangeCheckElimination.cpp.

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

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 556 of file InductiveRangeCheckElimination.cpp.

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

Referenced by calculateSubRanges().

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

Referenced by calculateSubRanges().

AllowUnsignedLatchCondition

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

static

LoopSizeCutoff

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

static

MaxTypeSizeForOverflowCheck

cl::opt< unsigned > MaxTypeSizeForOverflowCheck("irce-max-type-size-for-overflow-check", cl::Hidden, cl::init(32), cl::desc( "Maximum size of range check type for which can be produced runtime " "overflow check of its limit's computation")) ( "irce-max-type-size-for-overflow-check"  , cl::Hidden  , cl::init(32)  , cl::desc( "Maximum size of range check type for which can be produced runtime " "overflow check of its limit's computation")    )

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

PrintScaledBoundaryRangeChecks

cl::opt< bool > PrintScaledBoundaryRangeChecks("irce-print-scaled-boundary-range-checks", cl::Hidden, cl::init(false)) ( "irce-print-scaled-boundary-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().