blob: d9832eeb0697e6ebf84399d3d0c61f8f8fcac130 [file] [log] [blame]
#include "llvm/Transforms/Utils/LoopConstrainer.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/Dominators.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"
using namespace llvm;
static const char *ClonedLoopTag = "loop_constrainer.loop.clone";
#define DEBUG_TYPE "loop-constrainer"
/// 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 isSafeDecreasingBound(const SCEV *Start, const SCEV *BoundSCEV,
const SCEV *Step, ICmpInst::Predicate Pred,
unsigned LatchBrExitIdx, Loop *L,
ScalarEvolution &SE) {
if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
return false;
if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))
return false;
assert(SE.isKnownNegative(Step) && "expecting negative step");
LLVM_DEBUG(dbgs() << "isSafeDecreasingBound with:\n");
LLVM_DEBUG(dbgs() << "Start: " << *Start << "\n");
LLVM_DEBUG(dbgs() << "Step: " << *Step << "\n");
LLVM_DEBUG(dbgs() << "BoundSCEV: " << *BoundSCEV << "\n");
LLVM_DEBUG(dbgs() << "Pred: " << Pred << "\n");
LLVM_DEBUG(dbgs() << "LatchExitBrIdx: " << LatchBrExitIdx << "\n");
bool IsSigned = ICmpInst::isSigned(Pred);
// The predicate that we need to check that the induction variable lies
// within bounds.
ICmpInst::Predicate BoundPred =
IsSigned ? CmpInst::ICMP_SGT : CmpInst::ICMP_UGT;
auto StartLG = SE.applyLoopGuards(Start, L);
auto BoundLG = SE.applyLoopGuards(BoundSCEV, L);
if (LatchBrExitIdx == 1)
return SE.isLoopEntryGuardedByCond(L, BoundPred, StartLG, BoundLG);
assert(LatchBrExitIdx == 0 && "LatchBrExitIdx should be either 0 or 1");
const SCEV *StepPlusOne = SE.getAddExpr(Step, SE.getOne(Step->getType()));
unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
APInt Min = IsSigned ? APInt::getSignedMinValue(BitWidth)
: APInt::getMinValue(BitWidth);
const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Min), StepPlusOne);
const SCEV *MinusOne =
SE.getMinusSCEV(BoundLG, SE.getOne(BoundLG->getType()));
return SE.isLoopEntryGuardedByCond(L, BoundPred, StartLG, MinusOne) &&
SE.isLoopEntryGuardedByCond(L, BoundPred, BoundLG, Limit);
}
/// 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 bool isSafeIncreasingBound(const SCEV *Start, const SCEV *BoundSCEV,
const SCEV *Step, ICmpInst::Predicate Pred,
unsigned LatchBrExitIdx, Loop *L,
ScalarEvolution &SE) {
if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
return false;
if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))
return false;
LLVM_DEBUG(dbgs() << "isSafeIncreasingBound with:\n");
LLVM_DEBUG(dbgs() << "Start: " << *Start << "\n");
LLVM_DEBUG(dbgs() << "Step: " << *Step << "\n");
LLVM_DEBUG(dbgs() << "BoundSCEV: " << *BoundSCEV << "\n");
LLVM_DEBUG(dbgs() << "Pred: " << Pred << "\n");
LLVM_DEBUG(dbgs() << "LatchExitBrIdx: " << LatchBrExitIdx << "\n");
bool IsSigned = ICmpInst::isSigned(Pred);
// The predicate that we need to check that the induction variable lies
// within bounds.
ICmpInst::Predicate BoundPred =
IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
auto StartLG = SE.applyLoopGuards(Start, L);
auto BoundLG = SE.applyLoopGuards(BoundSCEV, L);
if (LatchBrExitIdx == 1)
return SE.isLoopEntryGuardedByCond(L, BoundPred, StartLG, BoundLG);
assert(LatchBrExitIdx == 0 && "LatchBrExitIdx should be 0 or 1");
const SCEV *StepMinusOne = SE.getMinusSCEV(Step, SE.getOne(Step->getType()));
unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
APInt Max = IsSigned ? APInt::getSignedMaxValue(BitWidth)
: APInt::getMaxValue(BitWidth);
const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Max), StepMinusOne);
return (SE.isLoopEntryGuardedByCond(L, BoundPred, StartLG,
SE.getAddExpr(BoundLG, Step)) &&
SE.isLoopEntryGuardedByCond(L, BoundPred, BoundLG, Limit));
}
/// Returns estimate for max latch taken count of the loop of the narrowest
/// available type. If the latch block has such estimate, it is returned.
/// Otherwise, we use max exit count of whole loop (that is potentially of wider
/// type than latch check itself), which is still better than no estimate.
static const SCEV *getNarrowestLatchMaxTakenCountEstimate(ScalarEvolution &SE,
const Loop &L) {
const SCEV *FromBlock =
SE.getExitCount(&L, L.getLoopLatch(), ScalarEvolution::SymbolicMaximum);
if (isa<SCEVCouldNotCompute>(FromBlock))
return SE.getSymbolicMaxBackedgeTakenCount(&L);
return FromBlock;
}
std::optional<LoopStructure>
LoopStructure::parseLoopStructure(ScalarEvolution &SE, Loop &L,
bool AllowUnsignedLatchCond,
const char *&FailureReason) {
if (!L.isLoopSimplifyForm()) {
FailureReason = "loop not in LoopSimplify form";
return std::nullopt;
}
BasicBlock *Latch = L.getLoopLatch();
assert(Latch && "Simplified loops only have one latch!");
if (Latch->getTerminator()->getMetadata(ClonedLoopTag)) {
FailureReason = "loop has already been cloned";
return std::nullopt;
}
if (!L.isLoopExiting(Latch)) {
FailureReason = "no loop latch";
return std::nullopt;
}
BasicBlock *Header = L.getHeader();
BasicBlock *Preheader = L.getLoopPreheader();
if (!Preheader) {
FailureReason = "no preheader";
return std::nullopt;
}
BranchInst *LatchBr = dyn_cast<BranchInst>(Latch->getTerminator());
if (!LatchBr || LatchBr->isUnconditional()) {
FailureReason = "latch terminator not conditional branch";
return std::nullopt;
}
unsigned LatchBrExitIdx = LatchBr->getSuccessor(0) == Header ? 1 : 0;
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 std::nullopt;
}
const SCEV *MaxBETakenCount = getNarrowestLatchMaxTakenCountEstimate(SE, L);
if (isa<SCEVCouldNotCompute>(MaxBETakenCount)) {
FailureReason = "could not compute latch count";
return std::nullopt;
}
assert(SE.getLoopDisposition(MaxBETakenCount, &L) ==
ScalarEvolution::LoopInvariant &&
"loop variant exit count doesn't make sense!");
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);
// We canonicalize `ICI` such that `LeftSCEV` is an add recurrence.
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 std::nullopt;
}
}
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;
}
// We may have proved this when computing the sign extension above.
return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap;
};
// `ICI` is interpreted as taking the backedge if the *next* value of the
// induction variable satisfies some constraint.
const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(LeftSCEV);
if (IndVarBase->getLoop() != &L) {
FailureReason = "LHS in cmp is not an AddRec for this loop";
return std::nullopt;
}
if (!IndVarBase->isAffine()) {
FailureReason = "LHS in icmp not induction variable";
return std::nullopt;
}
const SCEV *StepRec = IndVarBase->getStepRecurrence(SE);
if (!isa<SCEVConstant>(StepRec)) {
FailureReason = "LHS in icmp not induction variable";
return std::nullopt;
}
ConstantInt *StepCI = cast<SCEVConstant>(StepRec)->getValue();
if (ICI->isEquality() && !HasNoSignedWrap(IndVarBase)) {
FailureReason = "LHS in icmp needs nsw for equality predicates";
return std::nullopt;
}
assert(!StepCI->isZero() && "Zero step?");
bool IsIncreasing = !StepCI->isNegative();
bool IsSignedPredicate;
const SCEV *StartNext = IndVarBase->getStart();
const SCEV *Addend = SE.getNegativeSCEV(IndVarBase->getStepRecurrence(SE));
const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
const SCEV *Step = SE.getSCEV(StepCI);
const SCEV *FixedRightSCEV = nullptr;
// If RightValue resides within loop (but still being loop invariant),
// regenerate it as preheader.
if (auto *I = dyn_cast<Instruction>(RightValue))
if (L.contains(I->getParent()))
FixedRightSCEV = RightSCEV;
if (IsIncreasing) {
bool DecreasedRightValueByOne = false;
if (StepCI->isOne()) {
// Try to turn eq/ne predicates to those we can work with.
if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
// while (++i != len) { while (++i < len) {
// ... ---> ...
// } }
// If both parts are known non-negative, it is profitable to use
// unsigned comparison in increasing loop. This allows us to make the
// comparison check against "RightSCEV + 1" more optimistic.
if (isKnownNonNegativeInLoop(IndVarStart, &L, SE) &&
isKnownNonNegativeInLoop(RightSCEV, &L, SE))
Pred = ICmpInst::ICMP_ULT;
else
Pred = ICmpInst::ICMP_SLT;
else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
// while (true) { while (true) {
// if (++i == len) ---> if (++i > len - 1)
// break; break;
// ... ...
// } }
if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
cannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/ false)) {
Pred = ICmpInst::ICMP_UGT;
RightSCEV =
SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType()));
DecreasedRightValueByOne = true;
} else if (cannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/ true)) {
Pred = ICmpInst::ICMP_SGT;
RightSCEV =
SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType()));
DecreasedRightValueByOne = true;
}
}
}
bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
bool FoundExpectedPred =
(LTPred && LatchBrExitIdx == 1) || (GTPred && LatchBrExitIdx == 0);
if (!FoundExpectedPred) {
FailureReason = "expected icmp slt semantically, found something else";
return std::nullopt;
}
IsSignedPredicate = ICmpInst::isSigned(Pred);
if (!IsSignedPredicate && !AllowUnsignedLatchCond) {
FailureReason = "unsigned latch conditions are explicitly prohibited";
return std::nullopt;
}
if (!isSafeIncreasingBound(IndVarStart, RightSCEV, Step, Pred,
LatchBrExitIdx, &L, SE)) {
FailureReason = "Unsafe loop bounds";
return std::nullopt;
}
if (LatchBrExitIdx == 0) {
// We need to increase the right value unless we have already decreased
// it virtually when we replaced EQ with SGT.
if (!DecreasedRightValueByOne)
FixedRightSCEV =
SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
} else {
assert(!DecreasedRightValueByOne &&
"Right value can be decreased only for LatchBrExitIdx == 0!");
}
} else {
bool IncreasedRightValueByOne = false;
if (StepCI->isMinusOne()) {
// Try to turn eq/ne predicates to those we can work with.
if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
// while (--i != len) { while (--i > len) {
// ... ---> ...
// } }
// We intentionally don't turn the predicate into UGT even if we know
// that both operands are non-negative, because it will only pessimize
// our check against "RightSCEV - 1".
Pred = ICmpInst::ICMP_SGT;
else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
// while (true) { while (true) {
// if (--i == len) ---> if (--i < len + 1)
// break; break;
// ... ...
// } }
if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
cannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ false)) {
Pred = ICmpInst::ICMP_ULT;
RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
IncreasedRightValueByOne = true;
} else if (cannotBeMaxInLoop(RightSCEV, &L, SE, /* Signed */ true)) {
Pred = ICmpInst::ICMP_SLT;
RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
IncreasedRightValueByOne = true;
}
}
}
bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
bool FoundExpectedPred =
(GTPred && LatchBrExitIdx == 1) || (LTPred && LatchBrExitIdx == 0);
if (!FoundExpectedPred) {
FailureReason = "expected icmp sgt semantically, found something else";
return std::nullopt;
}
IsSignedPredicate =
Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
if (!IsSignedPredicate && !AllowUnsignedLatchCond) {
FailureReason = "unsigned latch conditions are explicitly prohibited";
return std::nullopt;
}
if (!isSafeDecreasingBound(IndVarStart, RightSCEV, Step, Pred,
LatchBrExitIdx, &L, SE)) {
FailureReason = "Unsafe bounds";
return std::nullopt;
}
if (LatchBrExitIdx == 0) {
// We need to decrease the right value unless we have already increased
// it virtually when we replaced EQ with SLT.
if (!IncreasedRightValueByOne)
FixedRightSCEV =
SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType()));
} else {
assert(!IncreasedRightValueByOne &&
"Right value can be increased only for LatchBrExitIdx == 0!");
}
}
BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx);
assert(!L.contains(LatchExit) && "expected an exit block!");
const DataLayout &DL = Preheader->getModule()->getDataLayout();
SCEVExpander Expander(SE, DL, "loop-constrainer");
Instruction *Ins = Preheader->getTerminator();
if (FixedRightSCEV)
RightValue =
Expander.expandCodeFor(FixedRightSCEV, FixedRightSCEV->getType(), Ins);
Value *IndVarStartV = Expander.expandCodeFor(IndVarStart, IndVarTy, Ins);
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.IndVarStep = StepCI;
Result.IndVarBase = LeftValue;
Result.IndVarIncreasing = IsIncreasing;
Result.LoopExitAt = RightValue;
Result.IsSignedPredicate = IsSignedPredicate;
Result.ExitCountTy = cast<IntegerType>(MaxBETakenCount->getType());
FailureReason = nullptr;
return Result;
}
// Add metadata to the loop L to disable loop optimizations. Callers need to
// confirm that optimizing loop L is not beneficial.
static void DisableAllLoopOptsOnLoop(Loop &L) {
// We do not care about any existing loopID related metadata for L, since we
// are setting all loop metadata to false.
LLVMContext &Context = L.getHeader()->getContext();
// Reserve first location for self reference to the LoopID metadata node.
MDNode *Dummy = MDNode::get(Context, {});
MDNode *DisableUnroll = MDNode::get(
Context, {MDString::get(Context, "llvm.loop.unroll.disable")});
Metadata *FalseVal =
ConstantAsMetadata::get(ConstantInt::get(Type::getInt1Ty(Context), 0));
MDNode *DisableVectorize = MDNode::get(
Context,
{MDString::get(Context, "llvm.loop.vectorize.enable"), FalseVal});
MDNode *DisableLICMVersioning = MDNode::get(
Context, {MDString::get(Context, "llvm.loop.licm_versioning.disable")});
MDNode *DisableDistribution = MDNode::get(
Context,
{MDString::get(Context, "llvm.loop.distribute.enable"), FalseVal});
MDNode *NewLoopID =
MDNode::get(Context, {Dummy, DisableUnroll, DisableVectorize,
DisableLICMVersioning, DisableDistribution});
// Set operand 0 to refer to the loop id itself.
NewLoopID->replaceOperandWith(0, NewLoopID);
L.setLoopID(NewLoopID);
}
LoopConstrainer::LoopConstrainer(Loop &L, LoopInfo &LI,
function_ref<void(Loop *, bool)> LPMAddNewLoop,
const LoopStructure &LS, ScalarEvolution &SE,
DominatorTree &DT, Type *T, SubRanges SR)
: F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()), SE(SE),
DT(DT), LI(LI), LPMAddNewLoop(LPMAddNewLoop), OriginalLoop(L), RangeTy(T),
MainLoopStructure(LS), SR(SR) {}
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);
};
auto *ClonedLatch =
cast<BasicBlock>(GetClonedValue(OriginalLoop.getLoopLatch()));
ClonedLatch->getTerminator()->setMetadata(ClonedLoopTag,
MDNode::get(Ctx, {}));
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_IgnoreMissingLocals);
// Exit blocks will now have one more predecessor and their PHI nodes need
// to be edited to reflect that. No phi nodes need to be introduced because
// the loop is in LCSSA.
for (auto *SBB : successors(OriginalBB)) {
if (OriginalLoop.contains(SBB))
continue; // not an exit block
for (PHINode &PN : SBB->phis()) {
Value *OldIncoming = PN.getIncomingValueForBlock(OriginalBB);
PN.addIncoming(GetClonedValue(OldIncoming), ClonedBB);
SE.forgetValue(&PN);
}
}
}
}
LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
const LoopStructure &LS, BasicBlock *Preheader, Value *ExitSubloopAt,
BasicBlock *ContinuationBlock) const {
// We start with a loop with a single latch:
//
// +--------------------+
// | |
// | preheader |
// | |
// +--------+-----------+
// | ----------------\
// | / |
// +--------v----v------+ |
// | | |
// | header | |
// | | |
// +--------------------+ |
// |
// ..... |
// |
// +--------------------+ |
// | | |
// | latch >----------/
// | |
// +-------v------------+
// |
// |
// | +--------------------+
// | | |
// +---> original exit |
// | |
// +--------------------+
//
// We change the control flow to look like
//
//
// +--------------------+
// | |
// | preheader >-------------------------+
// | | |
// +--------v-----------+ |
// | /-------------+ |
// | / | |
// +--------v--v--------+ | |
// | | | |
// | header | | +--------+ |
// | | | | | |
// +--------------------+ | | +-----v-----v-----------+
// | | | |
// | | | .pseudo.exit |
// | | | |
// | | +-----------v-----------+
// | | |
// ..... | | |
// | | +--------v-------------+
// +--------------------+ | | | |
// | | | | | ContinuationBlock |
// | latch >------+ | | |
// | | | +----------------------+
// +---------v----------+ |
// | |
// | |
// | +---------------^-----+
// | | |
// +-----> .exit.selector |
// | |
// +----------v----------+
// |
// +--------------------+ |
// | | |
// | original exit <----+
// | |
// +--------------------+
RewrittenRangeInfo RRI;
BasicBlock *BBInsertLocation = LS.Latch->getNextNode();
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->getTerminator());
bool Increasing = LS.IndVarIncreasing;
bool IsSignedPredicate = LS.IsSignedPredicate;
IRBuilder<> B(PreheaderJump);
auto NoopOrExt = [&](Value *V) {
if (V->getType() == RangeTy)
return V;
return IsSignedPredicate ? B.CreateSExt(V, RangeTy, "wide." + V->getName())
: B.CreateZExt(V, RangeTy, "wide." + V->getName());
};
// EnterLoopCond - is it okay to start executing this `LS'?
Value *EnterLoopCond = nullptr;
auto Pred =
Increasing
? (IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT)
: (IsSignedPredicate ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT);
Value *IndVarStart = NoopOrExt(LS.IndVarStart);
EnterLoopCond = B.CreateICmp(Pred, IndVarStart, ExitSubloopAt);
B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);
PreheaderJump->eraseFromParent();
LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);
B.SetInsertPoint(LS.LatchBr);
Value *IndVarBase = NoopOrExt(LS.IndVarBase);
Value *TakeBackedgeLoopCond = B.CreateICmp(Pred, IndVarBase, ExitSubloopAt);
Value *CondForBranch = LS.LatchBrExitIdx == 1
? TakeBackedgeLoopCond
: B.CreateNot(TakeBackedgeLoopCond);
LS.LatchBr->setCondition(CondForBranch);
B.SetInsertPoint(RRI.ExitSelector);
// IterationsLeft - are there any more iterations left, given the original
// upper bound on the induction variable? If not, we branch to the "real"
// exit.
Value *LoopExitAt = NoopOrExt(LS.LoopExitAt);
Value *IterationsLeft = B.CreateICmp(Pred, IndVarBase, LoopExitAt);
B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);
BranchInst *BranchToContinuation =
BranchInst::Create(ContinuationBlock, RRI.PseudoExit);
// We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of
// each of the PHI nodes in the loop header. This feeds into the initial
// value of the same PHI nodes if/when we continue execution.
for (PHINode &PN : LS.Header->phis()) {
PHINode *NewPHI = PHINode::Create(PN.getType(), 2, PN.getName() + ".copy",
BranchToContinuation->getIterator());
NewPHI->addIncoming(PN.getIncomingValueForBlock(Preheader), Preheader);
NewPHI->addIncoming(PN.getIncomingValueForBlock(LS.Latch),
RRI.ExitSelector);
RRI.PHIValuesAtPseudoExit.push_back(NewPHI);
}
RRI.IndVarEnd = PHINode::Create(IndVarBase->getType(), 2, "indvar.end",
BranchToContinuation->getIterator());
RRI.IndVarEnd->addIncoming(IndVarStart, Preheader);
RRI.IndVarEnd->addIncoming(IndVarBase, RRI.ExitSelector);
// The latch exit now has a branch from `RRI.ExitSelector' instead of
// `LS.Latch'. The PHI nodes need to be updated to reflect that.
LS.LatchExit->replacePhiUsesWith(LS.Latch, RRI.ExitSelector);
return RRI;
}
void LoopConstrainer::rewriteIncomingValuesForPHIs(
LoopStructure &LS, BasicBlock *ContinuationBlock,
const LoopConstrainer::RewrittenRangeInfo &RRI) const {
unsigned PHIIndex = 0;
for (PHINode &PN : LS.Header->phis())
PN.setIncomingValueForBlock(ContinuationBlock,
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);
LS.Header->replacePhiUsesWith(OldPreheader, Preheader);
return Preheader;
}
void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) {
Loop *ParentLoop = OriginalLoop.getParentLoop();
if (!ParentLoop)
return;
for (BasicBlock *BB : BBs)
ParentLoop->addBasicBlockToLoop(BB, LI);
}
Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent,
ValueToValueMapTy &VM,
bool IsSubloop) {
Loop &New = *LI.AllocateLoop();
if (Parent)
Parent->addChildLoop(&New);
else
LI.addTopLevelLoop(&New);
LPMAddNewLoop(&New, IsSubloop);
// Add all of the blocks in Original to the new loop.
for (auto *BB : Original->blocks())
if (LI.getLoopFor(BB) == Original)
New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), LI);
// Add all of the subloops to the new loop.
for (Loop *SubLoop : *Original)
createClonedLoopStructure(SubLoop, &New, VM, /* IsSubloop */ true);
return &New;
}
bool LoopConstrainer::run() {
BasicBlock *Preheader = OriginalLoop.getLoopPreheader();
assert(Preheader != nullptr && "precondition!");
OriginalPreheader = Preheader;
MainLoopPreheader = Preheader;
bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
bool Increasing = MainLoopStructure.IndVarIncreasing;
IntegerType *IVTy = cast<IntegerType>(RangeTy);
SCEVExpander Expander(SE, F.getParent()->getDataLayout(), "loop-constrainer");
Instruction *InsertPt = OriginalPreheader->getTerminator();
// It would have been better to make `PreLoop' and `PostLoop'
// `std::optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy
// constructor.
ClonedLoop PreLoop, PostLoop;
bool NeedsPreLoop =
Increasing ? SR.LowLimit.has_value() : SR.HighLimit.has_value();
bool NeedsPostLoop =
Increasing ? SR.HighLimit.has_value() : SR.LowLimit.has_value();
Value *ExitPreLoopAt = nullptr;
Value *ExitMainLoopAt = nullptr;
const SCEVConstant *MinusOneS =
cast<SCEVConstant>(SE.getConstant(IVTy, -1, true /* isSigned */));
if (NeedsPreLoop) {
const SCEV *ExitPreLoopAtSCEV = nullptr;
if (Increasing)
ExitPreLoopAtSCEV = *SR.LowLimit;
else if (cannotBeMinInLoop(*SR.HighLimit, &OriginalLoop, SE,
IsSignedPredicate))
ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
else {
LLVM_DEBUG(dbgs() << "could not prove no-overflow when computing "
<< "preloop exit limit. HighLimit = "
<< *(*SR.HighLimit) << "\n");
return false;
}
if (!Expander.isSafeToExpandAt(ExitPreLoopAtSCEV, InsertPt)) {
LLVM_DEBUG(dbgs() << "could not prove that it is safe to expand the"
<< " preloop exit limit " << *ExitPreLoopAtSCEV
<< " at block " << InsertPt->getParent()->getName()
<< "\n");
return false;
}
ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
ExitPreLoopAt->setName("exit.preloop.at");
}
if (NeedsPostLoop) {
const SCEV *ExitMainLoopAtSCEV = nullptr;
if (Increasing)
ExitMainLoopAtSCEV = *SR.HighLimit;
else if (cannotBeMinInLoop(*SR.LowLimit, &OriginalLoop, SE,
IsSignedPredicate))
ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
else {
LLVM_DEBUG(dbgs() << "could not prove no-overflow when computing "
<< "mainloop exit limit. LowLimit = "
<< *(*SR.LowLimit) << "\n");
return false;
}
if (!Expander.isSafeToExpandAt(ExitMainLoopAtSCEV, InsertPt)) {
LLVM_DEBUG(dbgs() << "could not prove that it is safe to expand the"
<< " main loop exit limit " << *ExitMainLoopAtSCEV
<< " at block " << InsertPt->getParent()->getName()
<< "\n");
return false;
}
ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);
ExitMainLoopAt->setName("exit.mainloop.at");
}
// We clone these ahead of time so that we don't have to deal with changing
// and temporarily invalid IR as we transform the loops.
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};
// Some of the above may be nullptr, filter them out before passing to
// addToParentLoopIfNeeded.
auto NewBlocksEnd =
std::remove(std::begin(NewBlocks), std::end(NewBlocks), nullptr);
addToParentLoopIfNeeded(ArrayRef(std::begin(NewBlocks), NewBlocksEnd));
DT.recalculate(F);
// We need to first add all the pre and post loop blocks into the loop
// structures (as part of createClonedLoopStructure), and then update the
// LCSSA form and LoopSimplifyForm. This is necessary for correctly updating
// LI when LoopSimplifyForm is generated.
Loop *PreL = nullptr, *PostL = nullptr;
if (!PreLoop.Blocks.empty()) {
PreL = createClonedLoopStructure(&OriginalLoop,
OriginalLoop.getParentLoop(), PreLoop.Map,
/* IsSubLoop */ false);
}
if (!PostLoop.Blocks.empty()) {
PostL =
createClonedLoopStructure(&OriginalLoop, OriginalLoop.getParentLoop(),
PostLoop.Map, /* IsSubLoop */ false);
}
// This function canonicalizes the loop into Loop-Simplify and LCSSA forms.
auto CanonicalizeLoop = [&](Loop *L, bool IsOriginalLoop) {
formLCSSARecursively(*L, DT, &LI, &SE);
simplifyLoop(L, &DT, &LI, &SE, nullptr, nullptr, true);
// Pre/post loops are slow paths, we do not need to perform any loop
// optimizations on them.
if (!IsOriginalLoop)
DisableAllLoopOptsOnLoop(*L);
};
if (PreL)
CanonicalizeLoop(PreL, false);
if (PostL)
CanonicalizeLoop(PostL, false);
CanonicalizeLoop(&OriginalLoop, true);
/// At this point:
/// - We've broken a "main loop" out of the loop in a way that the "main loop"
/// runs with the induction variable in a subset of [Begin, End).
/// - There is no overflow when computing "main loop" exit limit.
/// - Max latch taken count of the loop is limited.
/// It guarantees that induction variable will not overflow iterating in the
/// "main loop".
if (isa<OverflowingBinaryOperator>(MainLoopStructure.IndVarBase))
if (IsSignedPredicate)
cast<BinaryOperator>(MainLoopStructure.IndVarBase)
->setHasNoSignedWrap(true);
/// TODO: support unsigned predicate.
/// To add NUW flag we need to prove that both operands of BO are
/// non-negative. E.g:
/// ...
/// %iv.next = add nsw i32 %iv, -1
/// %cmp = icmp ult i32 %iv.next, %n
/// br i1 %cmp, label %loopexit, label %loop
///
/// -1 is MAX_UINT in terms of unsigned int. Adding anything but zero will
/// overflow, therefore NUW flag is not legal here.
return true;
}