InductiveRangeCheckElimination.cpp File Reference

#include "llvm/Transforms/Scalar/InductiveRangeCheckElimination.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpander.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/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/ValueMapper.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <limits>
#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. More...
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. More...
static Optional< InductiveRangeCheck::Range >	IntersectSignedRange (ScalarEvolution &SE, const Optional< InductiveRangeCheck::Range > &R1, const InductiveRangeCheck::Range &R2)
static Optional< InductiveRangeCheck::Range >	IntersectUnsignedRange (ScalarEvolution &SE, const 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< int >	MaxExitProbReciprocal ("irce-max-exit-prob-reciprocal", cl::Hidden, cl::init(10))
static cl::opt< bool >	SkipProfitabilityChecks ("irce-skip-profitability-checks", cl::Hidden, cl::init(false))
static cl::opt< bool >	AllowUnsignedLatchCondition ("irce-allow-unsigned-latch", cl::Hidden, cl::init(true))
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 121 of file InductiveRangeCheckElimination.cpp.

Function Documentation

DisableAllLoopOptsOnLoop()

static void DisableAllLoopOptsOnLoop ( Loop &  L )

static

Definition at line 406 of file InductiveRangeCheckElimination.cpp.

References Context, llvm::NVPTXISD::Dummy, F(), llvm::ConstantInt::get(), llvm::ConstantAsMetadata::get(), llvm::MDString::get(), llvm::MDNode::get(), llvm::BasicBlock::getContext(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingBlock(), llvm::Type::getInt1Ty(), llvm::PHINode::getNumIncomingValues(), llvm::BasicBlock::getParent(), llvm::AArch64CC::LS, llvm::max(), llvm::MDNode::replaceOperandWith(), llvm::PHINode::setIncomingBlock(), and llvm::Loop::setLoopID().

INITIALIZE_PASS_BEGIN()

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

IntersectSignedRange()

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

static

Definition at line 1675 of file InductiveRangeCheckElimination.cpp.

References assert(), llvm::ScalarEvolution::getSMaxExpr(), llvm::ScalarEvolution::getSMinExpr(), llvm::Optional< T >::getValue(), llvm::Optional< T >::hasValue(), llvm::None, and llvm::MipsISD::Ret.

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

IntersectUnsignedRange()

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

static

Definition at line 1704 of file InductiveRangeCheckElimination.cpp.

References assert(), llvm::ScalarEvolution::getUMaxExpr(), llvm::ScalarEvolution::getUMinExpr(), llvm::Optional< T >::getValue(), llvm::Optional< T >::hasValue(), llvm::None, and llvm::MipsISD::Ret.

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

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

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

Variable Documentation

AllowUnsignedLatchCondition

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

static

ClonedLoopTag

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

static

Definition at line 119 of file InductiveRangeCheckElimination.cpp.

elimination

Inductive range check elimination

Definition at line 264 of file InductiveRangeCheckElimination.cpp.

false

Inductive range check false

Definition at line 264 of file InductiveRangeCheckElimination.cpp.

irce

irce

Definition at line 264 of file InductiveRangeCheckElimination.cpp.

LoopSizeCutoff

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

static

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

MaxExitProbReciprocal

cl::opt<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal", cl::Hidden, cl::init(10))

static

PrintChangedLoops

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

static

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

PrintRangeChecks

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

static

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

SkipProfitabilityChecks

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

static