InductiveRangeCheckElimination.cpp [plain text]
#include "llvm/ADT/Optional.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/InstructionSimplify.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/Analysis/ValueTracking.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
#include <array>
using namespace llvm;
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));
#define DEBUG_TYPE "irce"
namespace {
class InductiveRangeCheck {
enum RangeCheckKind : unsigned {
RANGE_CHECK_LOWER = 1,
RANGE_CHECK_UPPER = 2,
RANGE_CHECK_BOTH = RANGE_CHECK_LOWER | RANGE_CHECK_UPPER,
RANGE_CHECK_UNKNOWN = (unsigned)-1
};
static const char *rangeCheckKindToStr(RangeCheckKind);
const SCEV *Offset;
const SCEV *Scale;
Value *Length;
BranchInst *Branch;
RangeCheckKind Kind;
static RangeCheckKind parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
ScalarEvolution &SE, Value *&Index,
Value *&Length);
static InductiveRangeCheck::RangeCheckKind
parseRangeCheck(Loop *L, ScalarEvolution &SE, Value *Condition,
const SCEV *&Index, Value *&UpperLimit);
InductiveRangeCheck() :
Offset(nullptr), Scale(nullptr), Length(nullptr), Branch(nullptr) { }
public:
const SCEV *getOffset() const { return Offset; }
const SCEV *getScale() const { return Scale; }
Value *getLength() const { return Length; }
void print(raw_ostream &OS) const {
OS << "InductiveRangeCheck:\n";
OS << " Kind: " << rangeCheckKindToStr(Kind) << "\n";
OS << " Offset: ";
Offset->print(OS);
OS << " Scale: ";
Scale->print(OS);
OS << " Length: ";
if (Length)
Length->print(OS);
else
OS << "(null)";
OS << "\n Branch: ";
getBranch()->print(OS);
OS << "\n";
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void dump() {
print(dbgs());
}
#endif
BranchInst *getBranch() const { return Branch; }
class Range {
const SCEV *Begin;
const SCEV *End;
public:
Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
assert(Begin->getType() == End->getType() && "ill-typed range!");
}
Type *getType() const { return Begin->getType(); }
const SCEV *getBegin() const { return Begin; }
const SCEV *getEnd() const { return End; }
};
typedef SpecificBumpPtrAllocator<InductiveRangeCheck> AllocatorTy;
bool getPassingDirection() { return true; }
Optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
const SCEVAddRecExpr *IndVar,
IRBuilder<> &B) const;
static InductiveRangeCheck *create(AllocatorTy &Alloc, BranchInst *BI,
Loop *L, ScalarEvolution &SE,
BranchProbabilityInfo &BPI);
};
class InductiveRangeCheckElimination : public LoopPass {
InductiveRangeCheck::AllocatorTy Allocator;
public:
static char ID;
InductiveRangeCheckElimination() : LoopPass(ID) {
initializeInductiveRangeCheckEliminationPass(
*PassRegistry::getPassRegistry());
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<LoopInfoWrapperPass>();
AU.addRequiredID(LoopSimplifyID);
AU.addRequiredID(LCSSAID);
AU.addRequired<ScalarEvolutionWrapperPass>();
AU.addRequired<BranchProbabilityInfoWrapperPass>();
}
bool runOnLoop(Loop *L, LPPassManager &LPM) override;
};
char InductiveRangeCheckElimination::ID = 0;
}
INITIALIZE_PASS_BEGIN(InductiveRangeCheckElimination, "irce",
"Inductive range check elimination", false, false)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
INITIALIZE_PASS_DEPENDENCY(LCSSA)
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
INITIALIZE_PASS_END(InductiveRangeCheckElimination, "irce",
"Inductive range check elimination", false, false)
const char *InductiveRangeCheck::rangeCheckKindToStr(
InductiveRangeCheck::RangeCheckKind RCK) {
switch (RCK) {
case InductiveRangeCheck::RANGE_CHECK_UNKNOWN:
return "RANGE_CHECK_UNKNOWN";
case InductiveRangeCheck::RANGE_CHECK_UPPER:
return "RANGE_CHECK_UPPER";
case InductiveRangeCheck::RANGE_CHECK_LOWER:
return "RANGE_CHECK_LOWER";
case InductiveRangeCheck::RANGE_CHECK_BOTH:
return "RANGE_CHECK_BOTH";
}
llvm_unreachable("unknown range check type!");
}
InductiveRangeCheck::RangeCheckKind
InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
ScalarEvolution &SE, Value *&Index,
Value *&Length) {
auto IsNonNegativeAndNotLoopVarying = [&SE, L](Value *V) {
const SCEV *S = SE.getSCEV(V);
if (isa<SCEVCouldNotCompute>(S))
return false;
return SE.getLoopDisposition(S, L) == ScalarEvolution::LoopInvariant &&
SE.isKnownNonNegative(S);
};
using namespace llvm::PatternMatch;
ICmpInst::Predicate Pred = ICI->getPredicate();
Value *LHS = ICI->getOperand(0);
Value *RHS = ICI->getOperand(1);
switch (Pred) {
default:
return RANGE_CHECK_UNKNOWN;
case ICmpInst::ICMP_SLE:
std::swap(LHS, RHS);
case ICmpInst::ICMP_SGE:
if (match(RHS, m_ConstantInt<0>())) {
Index = LHS;
return RANGE_CHECK_LOWER;
}
return RANGE_CHECK_UNKNOWN;
case ICmpInst::ICMP_SLT:
std::swap(LHS, RHS);
case ICmpInst::ICMP_SGT:
if (match(RHS, m_ConstantInt<-1>())) {
Index = LHS;
return RANGE_CHECK_LOWER;
}
if (IsNonNegativeAndNotLoopVarying(LHS)) {
Index = RHS;
Length = LHS;
return RANGE_CHECK_UPPER;
}
return RANGE_CHECK_UNKNOWN;
case ICmpInst::ICMP_ULT:
std::swap(LHS, RHS);
case ICmpInst::ICMP_UGT:
if (IsNonNegativeAndNotLoopVarying(LHS)) {
Index = RHS;
Length = LHS;
return RANGE_CHECK_BOTH;
}
return RANGE_CHECK_UNKNOWN;
}
llvm_unreachable("default clause returns!");
}
InductiveRangeCheck::RangeCheckKind
InductiveRangeCheck::parseRangeCheck(Loop *L, ScalarEvolution &SE,
Value *Condition, const SCEV *&Index,
Value *&Length) {
using namespace llvm::PatternMatch;
Value *A = nullptr;
Value *B = nullptr;
if (match(Condition, m_And(m_Value(A), m_Value(B)))) {
Value *IndexA = nullptr, *IndexB = nullptr;
Value *LengthA = nullptr, *LengthB = nullptr;
ICmpInst *ICmpA = dyn_cast<ICmpInst>(A), *ICmpB = dyn_cast<ICmpInst>(B);
if (!ICmpA || !ICmpB)
return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
auto RCKindA = parseRangeCheckICmp(L, ICmpA, SE, IndexA, LengthA);
auto RCKindB = parseRangeCheckICmp(L, ICmpB, SE, IndexB, LengthB);
if (RCKindA == InductiveRangeCheck::RANGE_CHECK_UNKNOWN ||
RCKindB == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
if (IndexA != IndexB)
return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
if (LengthA != nullptr && LengthB != nullptr && LengthA != LengthB)
return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
Index = SE.getSCEV(IndexA);
if (isa<SCEVCouldNotCompute>(Index))
return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
Length = LengthA == nullptr ? LengthB : LengthA;
return (InductiveRangeCheck::RangeCheckKind)(RCKindA | RCKindB);
}
if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
Value *IndexVal = nullptr;
auto RCKind = parseRangeCheckICmp(L, ICI, SE, IndexVal, Length);
if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
Index = SE.getSCEV(IndexVal);
if (isa<SCEVCouldNotCompute>(Index))
return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
return RCKind;
}
return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
}
InductiveRangeCheck *
InductiveRangeCheck::create(InductiveRangeCheck::AllocatorTy &A, BranchInst *BI,
Loop *L, ScalarEvolution &SE,
BranchProbabilityInfo &BPI) {
if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
return nullptr;
BranchProbability LikelyTaken(15, 16);
if (BPI.getEdgeProbability(BI->getParent(), (unsigned) 0) < LikelyTaken)
return nullptr;
Value *Length = nullptr;
const SCEV *IndexSCEV = nullptr;
auto RCKind = InductiveRangeCheck::parseRangeCheck(L, SE, BI->getCondition(),
IndexSCEV, Length);
if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
return nullptr;
assert(IndexSCEV && "contract with SplitRangeCheckCondition!");
assert((!(RCKind & InductiveRangeCheck::RANGE_CHECK_UPPER) || Length) &&
"contract with SplitRangeCheckCondition!");
const SCEVAddRecExpr *IndexAddRec = dyn_cast<SCEVAddRecExpr>(IndexSCEV);
bool IsAffineIndex =
IndexAddRec && (IndexAddRec->getLoop() == L) && IndexAddRec->isAffine();
if (!IsAffineIndex)
return nullptr;
InductiveRangeCheck *IRC = new (A.Allocate()) InductiveRangeCheck;
IRC->Length = Length;
IRC->Offset = IndexAddRec->getStart();
IRC->Scale = IndexAddRec->getStepRecurrence(SE);
IRC->Branch = BI;
IRC->Kind = RCKind;
return IRC;
}
namespace {
struct LoopStructure {
const char *Tag;
BasicBlock *Header;
BasicBlock *Latch;
BranchInst *LatchBr;
BasicBlock *LatchExit;
unsigned LatchBrExitIdx;
Value *IndVarNext;
Value *IndVarStart;
Value *LoopExitAt;
bool IndVarIncreasing;
LoopStructure()
: Tag(""), Header(nullptr), Latch(nullptr), LatchBr(nullptr),
LatchExit(nullptr), LatchBrExitIdx(-1), IndVarNext(nullptr),
IndVarStart(nullptr), LoopExitAt(nullptr), IndVarIncreasing(false) {}
template <typename M> LoopStructure map(M Map) const {
LoopStructure Result;
Result.Tag = Tag;
Result.Header = cast<BasicBlock>(Map(Header));
Result.Latch = cast<BasicBlock>(Map(Latch));
Result.LatchBr = cast<BranchInst>(Map(LatchBr));
Result.LatchExit = cast<BasicBlock>(Map(LatchExit));
Result.LatchBrExitIdx = LatchBrExitIdx;
Result.IndVarNext = Map(IndVarNext);
Result.IndVarStart = Map(IndVarStart);
Result.LoopExitAt = Map(LoopExitAt);
Result.IndVarIncreasing = IndVarIncreasing;
return Result;
}
static Optional<LoopStructure> parseLoopStructure(ScalarEvolution &,
BranchProbabilityInfo &BPI,
Loop &,
const char *&);
};
class LoopConstrainer {
struct ClonedLoop {
std::vector<BasicBlock *> Blocks;
ValueToValueMapTy Map;
LoopStructure Structure;
};
struct RewrittenRangeInfo {
BasicBlock *PseudoExit;
BasicBlock *ExitSelector;
std::vector<PHINode *> PHIValuesAtPseudoExit;
PHINode *IndVarEnd;
RewrittenRangeInfo()
: PseudoExit(nullptr), ExitSelector(nullptr), IndVarEnd(nullptr) {}
};
struct SubRanges {
Optional<const SCEV *> LowLimit;
Optional<const SCEV *> HighLimit;
};
static void replacePHIBlock(PHINode *PN, BasicBlock *Block,
BasicBlock *ReplaceBy);
Optional<SubRanges> calculateSubRanges() const;
void cloneLoop(ClonedLoop &CLResult, const char *Tag) const;
RewrittenRangeInfo
changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *Preheader,
Value *ExitLoopAt,
BasicBlock *ContinuationBlock) const;
BasicBlock *createPreheader(const LoopStructure &LS, BasicBlock *OldPreheader,
const char *Tag) const;
void rewriteIncomingValuesForPHIs(
LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader,
const LoopConstrainer::RewrittenRangeInfo &RRI) const;
void addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs);
Function &F;
LLVMContext &Ctx;
ScalarEvolution &SE;
Loop &OriginalLoop;
LoopInfo &OriginalLoopInfo;
const SCEV *LatchTakenCount;
BasicBlock *OriginalPreheader;
BasicBlock *MainLoopPreheader;
InductiveRangeCheck::Range Range;
LoopStructure MainLoopStructure;
public:
LoopConstrainer(Loop &L, LoopInfo &LI, const LoopStructure &LS,
ScalarEvolution &SE, InductiveRangeCheck::Range R)
: F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()),
SE(SE), OriginalLoop(L), OriginalLoopInfo(LI), LatchTakenCount(nullptr),
OriginalPreheader(nullptr), MainLoopPreheader(nullptr), Range(R),
MainLoopStructure(LS) {}
bool run();
};
}
void LoopConstrainer::replacePHIBlock(PHINode *PN, BasicBlock *Block,
BasicBlock *ReplaceBy) {
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
if (PN->getIncomingBlock(i) == Block)
PN->setIncomingBlock(i, ReplaceBy);
}
static bool CanBeSMax(ScalarEvolution &SE, const SCEV *S) {
APInt SMax =
APInt::getSignedMaxValue(cast<IntegerType>(S->getType())->getBitWidth());
return SE.getSignedRange(S).contains(SMax) &&
SE.getUnsignedRange(S).contains(SMax);
}
static bool CanBeSMin(ScalarEvolution &SE, const SCEV *S) {
APInt SMin =
APInt::getSignedMinValue(cast<IntegerType>(S->getType())->getBitWidth());
return SE.getSignedRange(S).contains(SMin) &&
SE.getUnsignedRange(S).contains(SMin);
}
Optional<LoopStructure>
LoopStructure::parseLoopStructure(ScalarEvolution &SE, BranchProbabilityInfo &BPI,
Loop &L, const char *&FailureReason) {
assert(L.isLoopSimplifyForm() && "should follow from addRequired<>");
BasicBlock *Latch = L.getLoopLatch();
if (!L.isLoopExiting(Latch)) {
FailureReason = "no loop latch";
return None;
}
BasicBlock *Header = L.getHeader();
BasicBlock *Preheader = L.getLoopPreheader();
if (!Preheader) {
FailureReason = "no preheader";
return None;
}
BranchInst *LatchBr = dyn_cast<BranchInst>(&*Latch->rbegin());
if (!LatchBr || LatchBr->isUnconditional()) {
FailureReason = "latch terminator not conditional branch";
return None;
}
unsigned LatchBrExitIdx = LatchBr->getSuccessor(0) == Header ? 1 : 0;
BranchProbability ExitProbability =
BPI.getEdgeProbability(LatchBr->getParent(), LatchBrExitIdx);
if (ExitProbability > BranchProbability(1, MaxExitProbReciprocal)) {
FailureReason = "short running loop, not profitable";
return None;
}
ICmpInst *ICI = dyn_cast<ICmpInst>(LatchBr->getCondition());
if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType())) {
FailureReason = "latch terminator branch not conditional on integral icmp";
return None;
}
const SCEV *LatchCount = SE.getExitCount(&L, Latch);
if (isa<SCEVCouldNotCompute>(LatchCount)) {
FailureReason = "could not compute latch count";
return None;
}
ICmpInst::Predicate Pred = ICI->getPredicate();
Value *LeftValue = ICI->getOperand(0);
const SCEV *LeftSCEV = SE.getSCEV(LeftValue);
IntegerType *IndVarTy = cast<IntegerType>(LeftValue->getType());
Value *RightValue = ICI->getOperand(1);
const SCEV *RightSCEV = SE.getSCEV(RightValue);
if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
if (isa<SCEVAddRecExpr>(RightSCEV)) {
std::swap(LeftSCEV, RightSCEV);
std::swap(LeftValue, RightValue);
Pred = ICmpInst::getSwappedPredicate(Pred);
} else {
FailureReason = "no add recurrences in the icmp";
return None;
}
}
auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {
if (AR->getNoWrapFlags(SCEV::FlagNSW))
return true;
IntegerType *Ty = cast<IntegerType>(AR->getType());
IntegerType *WideTy =
IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
const SCEVAddRecExpr *ExtendAfterOp =
dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));
if (ExtendAfterOp) {
const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);
const SCEV *ExtendedStep =
SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);
bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
if (NoSignedWrap)
return true;
}
return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap;
};
auto IsInductionVar = [&](const SCEVAddRecExpr *AR, bool &IsIncreasing) {
if (!AR->isAffine())
return false;
if (!HasNoSignedWrap(AR))
return false;
if (const SCEVConstant *StepExpr =
dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE))) {
ConstantInt *StepCI = StepExpr->getValue();
if (StepCI->isOne() || StepCI->isMinusOne()) {
IsIncreasing = StepCI->isOne();
return true;
}
}
return false;
};
const SCEVAddRecExpr *IndVarNext = cast<SCEVAddRecExpr>(LeftSCEV);
bool IsIncreasing = false;
if (!IsInductionVar(IndVarNext, IsIncreasing)) {
FailureReason = "LHS in icmp not induction variable";
return None;
}
ConstantInt *One = ConstantInt::get(IndVarTy, 1);
if (IsIncreasing) {
bool FoundExpectedPred =
(Pred == ICmpInst::ICMP_SLT && LatchBrExitIdx == 1) ||
(Pred == ICmpInst::ICMP_SGT && LatchBrExitIdx == 0);
if (!FoundExpectedPred) {
FailureReason = "expected icmp slt semantically, found something else";
return None;
}
if (LatchBrExitIdx == 0) {
if (CanBeSMax(SE, RightSCEV)) {
FailureReason = "limit may overflow when coercing sle to slt";
return None;
}
IRBuilder<> B(&*Preheader->rbegin());
RightValue = B.CreateAdd(RightValue, One);
}
} else {
bool FoundExpectedPred =
(Pred == ICmpInst::ICMP_SGT && LatchBrExitIdx == 1) ||
(Pred == ICmpInst::ICMP_SLT && LatchBrExitIdx == 0);
if (!FoundExpectedPred) {
FailureReason = "expected icmp sgt semantically, found something else";
return None;
}
if (LatchBrExitIdx == 0) {
if (CanBeSMin(SE, RightSCEV)) {
FailureReason = "limit may overflow when coercing sge to sgt";
return None;
}
IRBuilder<> B(&*Preheader->rbegin());
RightValue = B.CreateSub(RightValue, One);
}
}
const SCEV *StartNext = IndVarNext->getStart();
const SCEV *Addend = SE.getNegativeSCEV(IndVarNext->getStepRecurrence(SE));
const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx);
assert(SE.getLoopDisposition(LatchCount, &L) ==
ScalarEvolution::LoopInvariant &&
"loop variant exit count doesn't make sense!");
assert(!L.contains(LatchExit) && "expected an exit block!");
const DataLayout &DL = Preheader->getModule()->getDataLayout();
Value *IndVarStartV =
SCEVExpander(SE, DL, "irce")
.expandCodeFor(IndVarStart, IndVarTy, &*Preheader->rbegin());
IndVarStartV->setName("indvar.start");
LoopStructure Result;
Result.Tag = "main";
Result.Header = Header;
Result.Latch = Latch;
Result.LatchBr = LatchBr;
Result.LatchExit = LatchExit;
Result.LatchBrExitIdx = LatchBrExitIdx;
Result.IndVarStart = IndVarStartV;
Result.IndVarNext = LeftValue;
Result.IndVarIncreasing = IsIncreasing;
Result.LoopExitAt = RightValue;
FailureReason = nullptr;
return Result;
}
Optional<LoopConstrainer::SubRanges>
LoopConstrainer::calculateSubRanges() const {
IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType());
if (Range.getType() != Ty)
return None;
LoopConstrainer::SubRanges Result;
ConstantInt *One = ConstantInt::get(Ty, 1);
const SCEV *Start = SE.getSCEV(MainLoopStructure.IndVarStart);
const SCEV *End = SE.getSCEV(MainLoopStructure.LoopExitAt);
bool Increasing = MainLoopStructure.IndVarIncreasing;
const SCEV *Smallest = nullptr, *Greatest = nullptr;
if (Increasing) {
Smallest = Start;
Greatest = End;
} else {
Smallest = SE.getAddExpr(End, SE.getSCEV(One));
Greatest = SE.getAddExpr(Start, SE.getSCEV(One));
}
auto Clamp = [this, Smallest, Greatest](const SCEV *S) {
return SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S));
};
bool ProvablyNoPreloop =
SE.isKnownPredicate(ICmpInst::ICMP_SLE, Range.getBegin(), Smallest);
if (!ProvablyNoPreloop)
Result.LowLimit = Clamp(Range.getBegin());
bool ProvablyNoPostLoop =
SE.isKnownPredicate(ICmpInst::ICMP_SLE, Greatest, Range.getEnd());
if (!ProvablyNoPostLoop)
Result.HighLimit = Clamp(Range.getEnd());
return Result;
}
void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,
const char *Tag) const {
for (BasicBlock *BB : OriginalLoop.getBlocks()) {
BasicBlock *Clone = CloneBasicBlock(BB, Result.Map, Twine(".") + Tag, &F);
Result.Blocks.push_back(Clone);
Result.Map[BB] = Clone;
}
auto GetClonedValue = [&Result](Value *V) {
assert(V && "null values not in domain!");
auto It = Result.Map.find(V);
if (It == Result.Map.end())
return V;
return static_cast<Value *>(It->second);
};
Result.Structure = MainLoopStructure.map(GetClonedValue);
Result.Structure.Tag = Tag;
for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) {
BasicBlock *ClonedBB = Result.Blocks[i];
BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];
assert(Result.Map[OriginalBB] == ClonedBB && "invariant!");
for (Instruction &I : *ClonedBB)
RemapInstruction(&I, Result.Map,
RF_NoModuleLevelChanges | RF_IgnoreMissingEntries);
for (auto SBBI = succ_begin(OriginalBB), SBBE = succ_end(OriginalBB);
SBBI != SBBE; ++SBBI) {
if (OriginalLoop.contains(*SBBI))
continue;
for (Instruction &I : **SBBI) {
if (!isa<PHINode>(&I))
break;
PHINode *PN = cast<PHINode>(&I);
Value *OldIncoming = PN->getIncomingValueForBlock(OriginalBB);
PN->addIncoming(GetClonedValue(OldIncoming), ClonedBB);
}
}
}
}
LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
const LoopStructure &LS, BasicBlock *Preheader, Value *ExitSubloopAt,
BasicBlock *ContinuationBlock) const {
RewrittenRangeInfo RRI;
auto BBInsertLocation = std::next(Function::iterator(LS.Latch));
RRI.ExitSelector = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".exit.selector",
&F, &*BBInsertLocation);
RRI.PseudoExit = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".pseudo.exit", &F,
&*BBInsertLocation);
BranchInst *PreheaderJump = cast<BranchInst>(&*Preheader->rbegin());
bool Increasing = LS.IndVarIncreasing;
IRBuilder<> B(PreheaderJump);
Value *EnterLoopCond = Increasing
? B.CreateICmpSLT(LS.IndVarStart, ExitSubloopAt)
: B.CreateICmpSGT(LS.IndVarStart, ExitSubloopAt);
B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);
PreheaderJump->eraseFromParent();
LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);
B.SetInsertPoint(LS.LatchBr);
Value *TakeBackedgeLoopCond =
Increasing ? B.CreateICmpSLT(LS.IndVarNext, ExitSubloopAt)
: B.CreateICmpSGT(LS.IndVarNext, ExitSubloopAt);
Value *CondForBranch = LS.LatchBrExitIdx == 1
? TakeBackedgeLoopCond
: B.CreateNot(TakeBackedgeLoopCond);
LS.LatchBr->setCondition(CondForBranch);
B.SetInsertPoint(RRI.ExitSelector);
Value *IterationsLeft = Increasing
? B.CreateICmpSLT(LS.IndVarNext, LS.LoopExitAt)
: B.CreateICmpSGT(LS.IndVarNext, LS.LoopExitAt);
B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);
BranchInst *BranchToContinuation =
BranchInst::Create(ContinuationBlock, RRI.PseudoExit);
for (Instruction &I : *LS.Header) {
if (!isa<PHINode>(&I))
break;
PHINode *PN = cast<PHINode>(&I);
PHINode *NewPHI = PHINode::Create(PN->getType(), 2, PN->getName() + ".copy",
BranchToContinuation);
NewPHI->addIncoming(PN->getIncomingValueForBlock(Preheader), Preheader);
NewPHI->addIncoming(PN->getIncomingValueForBlock(LS.Latch),
RRI.ExitSelector);
RRI.PHIValuesAtPseudoExit.push_back(NewPHI);
}
RRI.IndVarEnd = PHINode::Create(LS.IndVarNext->getType(), 2, "indvar.end",
BranchToContinuation);
RRI.IndVarEnd->addIncoming(LS.IndVarStart, Preheader);
RRI.IndVarEnd->addIncoming(LS.IndVarNext, RRI.ExitSelector);
for (Instruction &I : *LS.LatchExit) {
if (PHINode *PN = dyn_cast<PHINode>(&I))
replacePHIBlock(PN, LS.Latch, RRI.ExitSelector);
else
break;
}
return RRI;
}
void LoopConstrainer::rewriteIncomingValuesForPHIs(
LoopStructure &LS, BasicBlock *ContinuationBlock,
const LoopConstrainer::RewrittenRangeInfo &RRI) const {
unsigned PHIIndex = 0;
for (Instruction &I : *LS.Header) {
if (!isa<PHINode>(&I))
break;
PHINode *PN = cast<PHINode>(&I);
for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
if (PN->getIncomingBlock(i) == ContinuationBlock)
PN->setIncomingValue(i, RRI.PHIValuesAtPseudoExit[PHIIndex++]);
}
LS.IndVarStart = RRI.IndVarEnd;
}
BasicBlock *LoopConstrainer::createPreheader(const LoopStructure &LS,
BasicBlock *OldPreheader,
const char *Tag) const {
BasicBlock *Preheader = BasicBlock::Create(Ctx, Tag, &F, LS.Header);
BranchInst::Create(LS.Header, Preheader);
for (Instruction &I : *LS.Header) {
if (!isa<PHINode>(&I))
break;
PHINode *PN = cast<PHINode>(&I);
for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
replacePHIBlock(PN, OldPreheader, Preheader);
}
return Preheader;
}
void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) {
Loop *ParentLoop = OriginalLoop.getParentLoop();
if (!ParentLoop)
return;
for (BasicBlock *BB : BBs)
ParentLoop->addBasicBlockToLoop(BB, OriginalLoopInfo);
}
bool LoopConstrainer::run() {
BasicBlock *Preheader = nullptr;
LatchTakenCount = SE.getExitCount(&OriginalLoop, MainLoopStructure.Latch);
Preheader = OriginalLoop.getLoopPreheader();
assert(!isa<SCEVCouldNotCompute>(LatchTakenCount) && Preheader != nullptr &&
"preconditions!");
OriginalPreheader = Preheader;
MainLoopPreheader = Preheader;
Optional<SubRanges> MaybeSR = calculateSubRanges();
if (!MaybeSR.hasValue()) {
DEBUG(dbgs() << "irce: could not compute subranges\n");
return false;
}
SubRanges SR = MaybeSR.getValue();
bool Increasing = MainLoopStructure.IndVarIncreasing;
IntegerType *IVTy =
cast<IntegerType>(MainLoopStructure.IndVarNext->getType());
SCEVExpander Expander(SE, F.getParent()->getDataLayout(), "irce");
Instruction *InsertPt = OriginalPreheader->getTerminator();
ClonedLoop PreLoop, PostLoop;
bool NeedsPreLoop =
Increasing ? SR.LowLimit.hasValue() : SR.HighLimit.hasValue();
bool NeedsPostLoop =
Increasing ? SR.HighLimit.hasValue() : SR.LowLimit.hasValue();
Value *ExitPreLoopAt = nullptr;
Value *ExitMainLoopAt = nullptr;
const SCEVConstant *MinusOneS =
cast<SCEVConstant>(SE.getConstant(IVTy, -1, true ));
if (NeedsPreLoop) {
const SCEV *ExitPreLoopAtSCEV = nullptr;
if (Increasing)
ExitPreLoopAtSCEV = *SR.LowLimit;
else {
if (CanBeSMin(SE, *SR.HighLimit)) {
DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
<< "preloop exit limit. HighLimit = " << *(*SR.HighLimit)
<< "\n");
return false;
}
ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
}
ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
ExitPreLoopAt->setName("exit.preloop.at");
}
if (NeedsPostLoop) {
const SCEV *ExitMainLoopAtSCEV = nullptr;
if (Increasing)
ExitMainLoopAtSCEV = *SR.HighLimit;
else {
if (CanBeSMin(SE, *SR.LowLimit)) {
DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
<< "mainloop exit limit. LowLimit = " << *(*SR.LowLimit)
<< "\n");
return false;
}
ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
}
ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);
ExitMainLoopAt->setName("exit.mainloop.at");
}
if (NeedsPreLoop)
cloneLoop(PreLoop, "preloop");
if (NeedsPostLoop)
cloneLoop(PostLoop, "postloop");
RewrittenRangeInfo PreLoopRRI;
if (NeedsPreLoop) {
Preheader->getTerminator()->replaceUsesOfWith(MainLoopStructure.Header,
PreLoop.Structure.Header);
MainLoopPreheader =
createPreheader(MainLoopStructure, Preheader, "mainloop");
PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader,
ExitPreLoopAt, MainLoopPreheader);
rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,
PreLoopRRI);
}
BasicBlock *PostLoopPreheader = nullptr;
RewrittenRangeInfo PostLoopRRI;
if (NeedsPostLoop) {
PostLoopPreheader =
createPreheader(PostLoop.Structure, Preheader, "postloop");
PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,
ExitMainLoopAt, PostLoopPreheader);
rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,
PostLoopRRI);
}
BasicBlock *NewMainLoopPreheader =
MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr;
BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit,
PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,
PostLoopRRI.ExitSelector, NewMainLoopPreheader};
auto NewBlocksEnd =
std::remove(std::begin(NewBlocks), std::end(NewBlocks), nullptr);
addToParentLoopIfNeeded(makeArrayRef(std::begin(NewBlocks), NewBlocksEnd));
addToParentLoopIfNeeded(PreLoop.Blocks);
addToParentLoopIfNeeded(PostLoop.Blocks);
return true;
}
Optional<InductiveRangeCheck::Range>
InductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE,
const SCEVAddRecExpr *IndVar,
IRBuilder<> &) const {
if (!IndVar->isAffine())
return None;
const SCEV *A = IndVar->getStart();
const SCEVConstant *B = dyn_cast<SCEVConstant>(IndVar->getStepRecurrence(SE));
if (!B)
return None;
const SCEV *C = getOffset();
const SCEVConstant *D = dyn_cast<SCEVConstant>(getScale());
if (D != B)
return None;
ConstantInt *ConstD = D->getValue();
if (!(ConstD->isMinusOne() || ConstD->isOne()))
return None;
const SCEV *M = SE.getMinusSCEV(C, A);
const SCEV *Begin = SE.getNegativeSCEV(M);
const SCEV *UpperLimit = nullptr;
if (Value *V = getLength()) {
UpperLimit = SE.getSCEV(V);
} else {
assert(Kind == InductiveRangeCheck::RANGE_CHECK_LOWER && "invariant!");
unsigned BitWidth = cast<IntegerType>(IndVar->getType())->getBitWidth();
UpperLimit = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
}
const SCEV *End = SE.getMinusSCEV(UpperLimit, M);
return InductiveRangeCheck::Range(Begin, End);
}
static Optional<InductiveRangeCheck::Range>
IntersectRange(ScalarEvolution &SE,
const Optional<InductiveRangeCheck::Range> &R1,
const InductiveRangeCheck::Range &R2, IRBuilder<> &B) {
if (!R1.hasValue())
return R2;
auto &R1Value = R1.getValue();
if (R1Value.getType() != R2.getType())
return None;
const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
return InductiveRangeCheck::Range(NewBegin, NewEnd);
}
bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
if (L->getBlocks().size() >= LoopSizeCutoff) {
DEBUG(dbgs() << "irce: giving up constraining loop, too large\n";);
return false;
}
BasicBlock *Preheader = L->getLoopPreheader();
if (!Preheader) {
DEBUG(dbgs() << "irce: loop has no preheader, leaving\n");
return false;
}
LLVMContext &Context = Preheader->getContext();
InductiveRangeCheck::AllocatorTy IRCAlloc;
SmallVector<InductiveRangeCheck *, 16> RangeChecks;
ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
BranchProbabilityInfo &BPI =
getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
for (auto BBI : L->getBlocks())
if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
if (InductiveRangeCheck *IRC =
InductiveRangeCheck::create(IRCAlloc, TBI, L, SE, BPI))
RangeChecks.push_back(IRC);
if (RangeChecks.empty())
return false;
auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) {
OS << "irce: looking at loop "; L->print(OS);
OS << "irce: loop has " << RangeChecks.size()
<< " inductive range checks: \n";
for (InductiveRangeCheck *IRC : RangeChecks)
IRC->print(OS);
};
DEBUG(PrintRecognizedRangeChecks(dbgs()));
if (PrintRangeChecks)
PrintRecognizedRangeChecks(errs());
const char *FailureReason = nullptr;
Optional<LoopStructure> MaybeLoopStructure =
LoopStructure::parseLoopStructure(SE, BPI, *L, FailureReason);
if (!MaybeLoopStructure.hasValue()) {
DEBUG(dbgs() << "irce: could not parse loop structure: " << FailureReason
<< "\n";);
return false;
}
LoopStructure LS = MaybeLoopStructure.getValue();
bool Increasing = LS.IndVarIncreasing;
const SCEV *MinusOne =
SE.getConstant(LS.IndVarNext->getType(), Increasing ? -1 : 1, true);
const SCEVAddRecExpr *IndVar =
cast<SCEVAddRecExpr>(SE.getAddExpr(SE.getSCEV(LS.IndVarNext), MinusOne));
Optional<InductiveRangeCheck::Range> SafeIterRange;
Instruction *ExprInsertPt = Preheader->getTerminator();
SmallVector<InductiveRangeCheck *, 4> RangeChecksToEliminate;
IRBuilder<> B(ExprInsertPt);
for (InductiveRangeCheck *IRC : RangeChecks) {
auto Result = IRC->computeSafeIterationSpace(SE, IndVar, B);
if (Result.hasValue()) {
auto MaybeSafeIterRange =
IntersectRange(SE, SafeIterRange, Result.getValue(), B);
if (MaybeSafeIterRange.hasValue()) {
RangeChecksToEliminate.push_back(IRC);
SafeIterRange = MaybeSafeIterRange.getValue();
}
}
}
if (!SafeIterRange.hasValue())
return false;
LoopConstrainer LC(*L, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), LS,
SE, SafeIterRange.getValue());
bool Changed = LC.run();
if (Changed) {
auto PrintConstrainedLoopInfo = [L]() {
dbgs() << "irce: in function ";
dbgs() << L->getHeader()->getParent()->getName() << ": ";
dbgs() << "constrained ";
L->print(dbgs());
};
DEBUG(PrintConstrainedLoopInfo());
if (PrintChangedLoops)
PrintConstrainedLoopInfo();
for (InductiveRangeCheck *IRC : RangeChecksToEliminate) {
ConstantInt *FoldedRangeCheck = IRC->getPassingDirection()
? ConstantInt::getTrue(Context)
: ConstantInt::getFalse(Context);
IRC->getBranch()->setCondition(FoldedRangeCheck);
}
}
return Changed;
}
Pass *llvm::createInductiveRangeCheckEliminationPass() {
return new InductiveRangeCheckElimination;
}