LLVM  10.0.0svn
Macros | Functions | Variables
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 const SCEVNoopOrExtend (const SCEV *S, Type *Ty, ScalarEvolution &SE, bool Signed)
 If the type of S matches with Ty, return S. 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< unsignedLoopSizeCutoff ("irce-loop-size-cutoff", cl::Hidden, cl::init(64))
 
static cl::opt< boolPrintChangedLoops ("irce-print-changed-loops", cl::Hidden, cl::init(false))
 
static cl::opt< boolPrintRangeChecks ("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< boolSkipProfitabilityChecks ("irce-skip-profitability-checks", cl::Hidden, cl::init(false))
 
static cl::opt< boolAllowUnsignedLatchCondition ("irce-allow-unsigned-latch", cl::Hidden, cl::init(true))
 
static cl::opt< boolAllowNarrowLatchCondition ("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 charClonedLoopTag = "irce.loop.clone"
 
 irce
 
Inductive range check elimination
 
Inductive range check false
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "irce"

Definition at line 125 of file InductiveRangeCheckElimination.cpp.

Function Documentation

◆ DisableAllLoopOptsOnLoop()

static void DisableAllLoopOptsOnLoop ( Loop L)
static

◆ 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

◆ IntersectUnsignedRange()

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

◆ 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 642 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 692 of file InductiveRangeCheckElimination.cpp.

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

References AllowNarrowLatchCondition, llvm::IntegerType::getBitWidth(), llvm::ScalarEvolution::getNoopOrSignExtend(), llvm::ScalarEvolution::getNoopOrZeroExtend(), and llvm::None.

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."))
static

Referenced by NoopOrExtend().

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

◆ elimination

Inductive range check elimination

Definition at line 268 of file InductiveRangeCheckElimination.cpp.

◆ false

Inductive range check false

Definition at line 268 of file InductiveRangeCheckElimination.cpp.

◆ irce

irce

Definition at line 268 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