#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
+#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
+using namespace PatternMatch;
/// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP,
/// reusing an existing cast if a suitable one exists, moving an existing
// Create a new cast, and leave the old cast in place in case
// it is being used as an insert point. Clear its operand
// so that it doesn't hold anything live.
- Ret = CastInst::Create(Op, V, Ty, "", IP);
+ Ret = CastInst::Create(Op, V, Ty, "", &*IP);
Ret->takeName(CI);
CI->replaceAllUsesWith(Ret);
CI->setOperand(0, UndefValue::get(V->getType()));
// Create a new cast.
if (!Ret)
- Ret = CastInst::Create(Op, V, Ty, V->getName(), IP);
+ Ret = CastInst::Create(Op, V, Ty, V->getName(), &*IP);
// We assert at the end of the function since IP might point to an
// instruction with different dominance properties than a cast
// (an invoke for example) and not dominate BIP (but the cast does).
- assert(SE.DT->dominates(Ret, BIP));
+ assert(SE.DT.dominates(Ret, &*BIP));
rememberInstruction(Ret);
return Ret;
}
+static BasicBlock::iterator findInsertPointAfter(Instruction *I,
+ BasicBlock *MustDominate) {
+ BasicBlock::iterator IP = ++I->getIterator();
+ if (auto *II = dyn_cast<InvokeInst>(I))
+ IP = II->getNormalDest()->begin();
+
+ while (isa<PHINode>(IP))
+ ++IP;
+
+ while (IP->isEHPad()) {
+ if (isa<FuncletPadInst>(IP) || isa<LandingPadInst>(IP)) {
+ ++IP;
+ } else if (auto *TPI = dyn_cast<TerminatePadInst>(IP)) {
+ IP = TPI->getUnwindDest()->getFirstNonPHI()->getIterator();
+ } else if (isa<CatchSwitchInst>(IP)) {
+ IP = MustDominate->getFirstInsertionPt();
+ } else {
+ llvm_unreachable("unexpected eh pad!");
+ }
+ }
+
+ return IP;
+}
+
/// InsertNoopCastOfTo - Insert a cast of V to the specified type,
/// which must be possible with a noop cast, doing what we can to share
/// the casts.
while ((isa<BitCastInst>(IP) &&
isa<Argument>(cast<BitCastInst>(IP)->getOperand(0)) &&
cast<BitCastInst>(IP)->getOperand(0) != A) ||
- isa<DbgInfoIntrinsic>(IP) ||
- isa<LandingPadInst>(IP))
+ isa<DbgInfoIntrinsic>(IP))
++IP;
return ReuseOrCreateCast(A, Ty, Op, IP);
}
// Cast the instruction immediately after the instruction.
Instruction *I = cast<Instruction>(V);
- BasicBlock::iterator IP = I; ++IP;
- if (InvokeInst *II = dyn_cast<InvokeInst>(I))
- IP = II->getNormalDest()->begin();
- while (isa<PHINode>(IP) || isa<LandingPadInst>(IP))
- ++IP;
+ BasicBlock::iterator IP = findInsertPointAfter(I, Builder.GetInsertBlock());
return ReuseOrCreateCast(I, Ty, Op, IP);
}
ScanLimit++;
if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS &&
IP->getOperand(1) == RHS)
- return IP;
+ return &*IP;
if (IP == BlockBegin) break;
}
}
BuilderType::InsertPointGuard Guard(Builder);
// Move the insertion point out of as many loops as we can.
- while (const Loop *L = SE.LI->getLoopFor(Builder.GetInsertBlock())) {
+ while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break;
BasicBlock *Preheader = L->getLoopPreheader();
if (!Preheader) break;
// Ok, move up a level.
- Builder.SetInsertPoint(Preheader, Preheader->getTerminator());
+ Builder.SetInsertPoint(Preheader->getTerminator());
}
// If we haven't found this binop, insert it.
const SCEV *ElSize = SE.getSizeOfExpr(IntPtrTy, ElTy);
if (!ElSize->isZero()) {
SmallVector<const SCEV *, 8> NewOps;
- for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
- const SCEV *Op = Ops[i];
+ for (const SCEV *Op : Ops) {
const SCEV *Remainder = SE.getConstant(Ty, 0);
if (FactorOutConstant(Op, Remainder, ElSize, SE, DL)) {
// Op now has ElSize factored out.
} else {
// The operand was not divisible, so add it to the list of operands
// we'll scan next iteration.
- NewOps.push_back(Ops[i]);
+ NewOps.push_back(Op);
}
}
// If we made any changes, update Ops.
Type::getInt8PtrTy(Ty->getContext(), PTy->getAddressSpace()));
assert(!isa<Instruction>(V) ||
- SE.DT->dominates(cast<Instruction>(V), Builder.GetInsertPoint()));
+ SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint()));
// Expand the operands for a plain byte offset.
Value *Idx = expandCodeFor(SE.getAddExpr(Ops), Ty);
ScanLimit++;
if (IP->getOpcode() == Instruction::GetElementPtr &&
IP->getOperand(0) == V && IP->getOperand(1) == Idx)
- return IP;
+ return &*IP;
if (IP == BlockBegin) break;
}
}
BuilderType::InsertPointGuard Guard(Builder);
// Move the insertion point out of as many loops as we can.
- while (const Loop *L = SE.LI->getLoopFor(Builder.GetInsertBlock())) {
+ while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
if (!L->isLoopInvariant(V) || !L->isLoopInvariant(Idx)) break;
BasicBlock *Preheader = L->getLoopPreheader();
if (!Preheader) break;
// Ok, move up a level.
- Builder.SetInsertPoint(Preheader, Preheader->getTerminator());
+ Builder.SetInsertPoint(Preheader->getTerminator());
}
// Emit a GEP.
BuilderType::InsertPoint SaveInsertPt = Builder.saveIP();
// Move the insertion point out of as many loops as we can.
- while (const Loop *L = SE.LI->getLoopFor(Builder.GetInsertBlock())) {
+ while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
if (!L->isLoopInvariant(V)) break;
- bool AnyIndexNotLoopInvariant = false;
- for (SmallVectorImpl<Value *>::const_iterator I = GepIndices.begin(),
- E = GepIndices.end(); I != E; ++I)
- if (!L->isLoopInvariant(*I)) {
- AnyIndexNotLoopInvariant = true;
- break;
- }
+ bool AnyIndexNotLoopInvariant =
+ std::any_of(GepIndices.begin(), GepIndices.end(),
+ [L](Value *Op) { return !L->isLoopInvariant(Op); });
+
if (AnyIndexNotLoopInvariant)
break;
if (!Preheader) break;
// Ok, move up a level.
- Builder.SetInsertPoint(Preheader, Preheader->getTerminator());
+ Builder.SetInsertPoint(Preheader->getTerminator());
}
// Insert a pretty getelementptr. Note that this GEP is not marked inbounds,
Value *Casted = V;
if (V->getType() != PTy)
Casted = InsertNoopCastOfTo(Casted, PTy);
- Value *GEP = Builder.CreateGEP(OriginalElTy, Casted,
- GepIndices,
- "scevgep");
+ Value *GEP = Builder.CreateGEP(OriginalElTy, Casted, GepIndices, "scevgep");
Ops.push_back(SE.getUnknown(GEP));
rememberInstruction(GEP);
/// expression, according to PickMostRelevantLoop.
const Loop *SCEVExpander::getRelevantLoop(const SCEV *S) {
// Test whether we've already computed the most relevant loop for this SCEV.
- std::pair<DenseMap<const SCEV *, const Loop *>::iterator, bool> Pair =
- RelevantLoops.insert(std::make_pair(S, nullptr));
+ auto Pair = RelevantLoops.insert(std::make_pair(S, nullptr));
if (!Pair.second)
return Pair.first->second;
return nullptr;
if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
if (const Instruction *I = dyn_cast<Instruction>(U->getValue()))
- return Pair.first->second = SE.LI->getLoopFor(I->getParent());
+ return Pair.first->second = SE.LI.getLoopFor(I->getParent());
// A non-instruction has no relevant loops.
return nullptr;
}
const Loop *L = nullptr;
if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
L = AR->getLoop();
- for (SCEVNAryExpr::op_iterator I = N->op_begin(), E = N->op_end();
- I != E; ++I)
- L = PickMostRelevantLoop(L, getRelevantLoop(*I), *SE.DT);
+ for (const SCEV *Op : N->operands())
+ L = PickMostRelevantLoop(L, getRelevantLoop(Op), SE.DT);
return RelevantLoops[N] = L;
}
if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) {
return RelevantLoops[C] = Result;
}
if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
- const Loop *Result =
- PickMostRelevantLoop(getRelevantLoop(D->getLHS()),
- getRelevantLoop(D->getRHS()),
- *SE.DT);
+ const Loop *Result = PickMostRelevantLoop(
+ getRelevantLoop(D->getLHS()), getRelevantLoop(D->getRHS()), SE.DT);
return RelevantLoops[D] = Result;
}
llvm_unreachable("Unexpected SCEV type!");
// Sort by loop. Use a stable sort so that constants follow non-constants and
// pointer operands precede non-pointer operands.
- std::stable_sort(OpsAndLoops.begin(), OpsAndLoops.end(), LoopCompare(*SE.DT));
+ std::stable_sort(OpsAndLoops.begin(), OpsAndLoops.end(), LoopCompare(SE.DT));
// Emit instructions to add all the operands. Hoist as much as possible
// out of loops, and form meaningful getelementptrs where possible.
Value *Sum = nullptr;
- for (SmallVectorImpl<std::pair<const Loop *, const SCEV *> >::iterator
- I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E; ) {
+ for (auto I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E;) {
const Loop *CurLoop = I->first;
const SCEV *Op = I->second;
if (!Sum) {
OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
// Sort by loop. Use a stable sort so that constants follow non-constants.
- std::stable_sort(OpsAndLoops.begin(), OpsAndLoops.end(), LoopCompare(*SE.DT));
+ std::stable_sort(OpsAndLoops.begin(), OpsAndLoops.end(), LoopCompare(SE.DT));
// Emit instructions to mul all the operands. Hoist as much as possible
// out of loops.
Value *Prod = nullptr;
- for (SmallVectorImpl<std::pair<const Loop *, const SCEV *> >::iterator
- I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E; ) {
- const SCEV *Op = I->second;
+ for (const auto &I : OpsAndLoops) {
+ const SCEV *Op = I.second;
if (!Prod) {
// This is the first operand. Just expand it.
Prod = expand(Op);
- ++I;
} else if (Op->isAllOnesValue()) {
// Instead of doing a multiply by negative one, just do a negate.
Prod = InsertNoopCastOfTo(Prod, Ty);
Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod);
- ++I;
} else {
// A simple mul.
Value *W = expandCodeFor(Op, Ty);
Prod = InsertNoopCastOfTo(Prod, Ty);
// Canonicalize a constant to the RHS.
if (isa<Constant>(Prod)) std::swap(Prod, W);
- Prod = InsertBinop(Instruction::Mul, Prod, W);
- ++I;
+ const APInt *RHS;
+ if (match(W, m_Power2(RHS))) {
+ // Canonicalize Prod*(1<<C) to Prod<<C.
+ assert(!Ty->isVectorTy() && "vector types are not SCEVable");
+ Prod = InsertBinop(Instruction::Shl, Prod,
+ ConstantInt::get(Ty, RHS->logBase2()));
+ } else {
+ Prod = InsertBinop(Instruction::Mul, Prod, W);
+ }
}
}
for (User::op_iterator OI = IncV->op_begin()+1,
OE = IncV->op_end(); OI != OE; ++OI)
if (Instruction *OInst = dyn_cast<Instruction>(OI))
- if (!SE.DT->dominates(OInst, IVIncInsertPos))
+ if (!SE.DT.dominates(OInst, IVIncInsertPos))
return false;
}
// Advance to the next instruction.
case Instruction::Add:
case Instruction::Sub: {
Instruction *OInst = dyn_cast<Instruction>(IncV->getOperand(1));
- if (!OInst || SE.DT->dominates(OInst, InsertPos))
+ if (!OInst || SE.DT.dominates(OInst, InsertPos))
return dyn_cast<Instruction>(IncV->getOperand(0));
return nullptr;
}
case Instruction::BitCast:
return dyn_cast<Instruction>(IncV->getOperand(0));
case Instruction::GetElementPtr:
- for (Instruction::op_iterator I = IncV->op_begin()+1, E = IncV->op_end();
- I != E; ++I) {
+ for (auto I = IncV->op_begin() + 1, E = IncV->op_end(); I != E; ++I) {
if (isa<Constant>(*I))
continue;
if (Instruction *OInst = dyn_cast<Instruction>(*I)) {
- if (!SE.DT->dominates(OInst, InsertPos))
+ if (!SE.DT.dominates(OInst, InsertPos))
return nullptr;
}
if (allowScale) {
/// it available to other uses in this loop. Recursively hoist any operands,
/// until we reach a value that dominates InsertPos.
bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) {
- if (SE.DT->dominates(IncV, InsertPos))
+ if (SE.DT.dominates(IncV, InsertPos))
return true;
// InsertPos must itself dominate IncV so that IncV's new position satisfies
// its existing users.
- if (isa<PHINode>(InsertPos)
- || !SE.DT->dominates(InsertPos->getParent(), IncV->getParent()))
+ if (isa<PHINode>(InsertPos) ||
+ !SE.DT.dominates(InsertPos->getParent(), IncV->getParent()))
+ return false;
+
+ if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos))
return false;
// Check that the chain of IV operands leading back to Phi can be hoisted.
// IncV is safe to hoist.
IVIncs.push_back(IncV);
IncV = Oper;
- if (SE.DT->dominates(IncV, InsertPos))
+ if (SE.DT.dominates(IncV, InsertPos))
break;
}
- for (SmallVectorImpl<Instruction*>::reverse_iterator I = IVIncs.rbegin(),
- E = IVIncs.rend(); I != E; ++I) {
+ for (auto I = IVIncs.rbegin(), E = IVIncs.rend(); I != E; ++I) {
(*I)->moveBefore(InsertPos);
}
return true;
}
/// \brief Check whether we can cheaply express the requested SCEV in terms of
-/// the available PHI SCEV by truncation and/or invertion of the step.
+/// the available PHI SCEV by truncation and/or inversion of the step.
static bool canBeCheaplyTransformed(ScalarEvolution &SE,
const SCEVAddRecExpr *Phi,
const SCEVAddRecExpr *Requested,
// Only try partially matching scevs that need truncation and/or
// step-inversion if we know this loop is outside the current loop.
- bool TryNonMatchingSCEV = IVIncInsertLoop &&
- SE.DT->properlyDominates(LatchBlock, IVIncInsertLoop->getHeader());
+ bool TryNonMatchingSCEV =
+ IVIncInsertLoop &&
+ SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader());
- for (BasicBlock::iterator I = L->getHeader()->begin();
- PHINode *PN = dyn_cast<PHINode>(I); ++I) {
- if (!SE.isSCEVable(PN->getType()))
+ for (auto &I : *L->getHeader()) {
+ auto *PN = dyn_cast<PHINode>(&I);
+ if (!PN || !SE.isSCEVable(PN->getType()))
continue;
const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(PN));
// Potentially, move the increment. We have made sure in
// isExpandedAddRecExprPHI or hoistIVInc that this is possible.
if (L == IVIncInsertLoop)
- hoistBeforePos(SE.DT, IncV, IVIncInsertPos, AddRecPhiMatch);
+ hoistBeforePos(&SE.DT, IncV, IVIncInsertPos, AddRecPhiMatch);
// Ok, the add recurrence looks usable.
// Remember this PHI, even in post-inc mode.
PostIncLoops.clear();
// Expand code for the start value.
- Value *StartV = expandCodeFor(Normalized->getStart(), ExpandTy,
- L->getHeader()->begin());
+ Value *StartV =
+ expandCodeFor(Normalized->getStart(), ExpandTy, &L->getHeader()->front());
// StartV must be hoisted into L's preheader to dominate the new phi.
assert(!isa<Instruction>(StartV) ||
- SE.DT->properlyDominates(cast<Instruction>(StartV)->getParent(),
- L->getHeader()));
+ SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(),
+ L->getHeader()));
// Expand code for the step value. Do this before creating the PHI so that PHI
// reuse code doesn't see an incomplete PHI.
if (useSubtract)
Step = SE.getNegativeSCEV(Step);
// Expand the step somewhere that dominates the loop header.
- Value *StepV = expandCodeFor(Step, IntTy, L->getHeader()->begin());
+ Value *StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front());
// The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if
// we actually do emit an addition. It does not apply if we emit a
if (PostIncLoops.count(L)) {
PostIncLoopSet Loops;
Loops.insert(L);
- Normalized =
- cast<SCEVAddRecExpr>(TransformForPostIncUse(Normalize, S, nullptr,
- nullptr, Loops, SE, *SE.DT));
+ Normalized = cast<SCEVAddRecExpr>(TransformForPostIncUse(
+ Normalize, S, nullptr, nullptr, Loops, SE, SE.DT));
}
// Strip off any non-loop-dominating component from the addrec start.
// For an expansion to use the postinc form, the client must call
// expandCodeFor with an InsertPoint that is either outside the PostIncLoop
// or dominated by IVIncInsertPos.
- if (isa<Instruction>(Result)
- && !SE.DT->dominates(cast<Instruction>(Result),
- Builder.GetInsertPoint())) {
+ if (isa<Instruction>(Result) &&
+ !SE.DT.dominates(cast<Instruction>(Result),
+ &*Builder.GetInsertPoint())) {
// The induction variable's postinc expansion does not dominate this use.
// IVUsers tries to prevent this case, so it is rare. However, it can
// happen when an IVUser outside the loop is not dominated by the latch
{
// Expand the step somewhere that dominates the loop header.
BuilderType::InsertPointGuard Guard(Builder);
- StepV = expandCodeFor(Step, IntTy, L->getHeader()->begin());
+ StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front());
}
Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
}
Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
S->getNoWrapFlags(SCEV::FlagNW)));
BasicBlock::iterator NewInsertPt =
- std::next(BasicBlock::iterator(cast<Instruction>(V)));
- BuilderType::InsertPointGuard Guard(Builder);
- while (isa<PHINode>(NewInsertPt) || isa<DbgInfoIntrinsic>(NewInsertPt) ||
- isa<LandingPadInst>(NewInsertPt))
- ++NewInsertPt;
+ findInsertPointAfter(cast<Instruction>(V), Builder.GetInsertBlock());
V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,
- NewInsertPt);
+ &*NewInsertPt);
return V;
}
BasicBlock *Header = L->getHeader();
pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
CanonicalIV = PHINode::Create(Ty, std::distance(HPB, HPE), "indvar",
- Header->begin());
+ &Header->front());
rememberInstruction(CanonicalIV);
SmallSet<BasicBlock *, 4> PredSeen;
Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty,
Instruction *IP) {
- Builder.SetInsertPoint(IP->getParent(), IP);
+ assert(IP);
+ Builder.SetInsertPoint(IP);
return expandCodeFor(SH, Ty);
}
Value *SCEVExpander::expand(const SCEV *S) {
// Compute an insertion point for this SCEV object. Hoist the instructions
// as far out in the loop nest as possible.
- Instruction *InsertPt = Builder.GetInsertPoint();
- for (Loop *L = SE.LI->getLoopFor(Builder.GetInsertBlock()); ;
+ Instruction *InsertPt = &*Builder.GetInsertPoint();
+ for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;
L = L->getParentLoop())
if (SE.isLoopInvariant(S, L)) {
if (!L) break;
// LSR sets the insertion point for AddRec start/step values to the
// block start to simplify value reuse, even though it's an invalid
// position. SCEVExpander must correct for this in all cases.
- InsertPt = L->getHeader()->getFirstInsertionPt();
+ InsertPt = &*L->getHeader()->getFirstInsertionPt();
}
} else {
// If the SCEV is computable at this level, insert it into the header
// after the PHIs (and after any other instructions that we've inserted
// there) so that it is guaranteed to dominate any user inside the loop.
if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L))
- InsertPt = L->getHeader()->getFirstInsertionPt();
+ InsertPt = &*L->getHeader()->getFirstInsertionPt();
while (InsertPt != Builder.GetInsertPoint()
&& (isInsertedInstruction(InsertPt)
|| isa<DbgInfoIntrinsic>(InsertPt))) {
- InsertPt = std::next(BasicBlock::iterator(InsertPt));
+ InsertPt = &*std::next(InsertPt->getIterator());
}
break;
}
// Check to see if we already expanded this here.
- std::map<std::pair<const SCEV *, Instruction *>, TrackingVH<Value> >::iterator
- I = InsertedExpressions.find(std::make_pair(S, InsertPt));
+ auto I = InsertedExpressions.find(std::make_pair(S, InsertPt));
if (I != InsertedExpressions.end())
return I->second;
BuilderType::InsertPointGuard Guard(Builder);
- Builder.SetInsertPoint(InsertPt->getParent(), InsertPt);
+ Builder.SetInsertPoint(InsertPt);
// Expand the expression into instructions.
Value *V = visit(S);
// Emit code for it.
BuilderType::InsertPointGuard Guard(Builder);
- PHINode *V = cast<PHINode>(expandCodeFor(H, nullptr,
- L->getHeader()->begin()));
+ PHINode *V =
+ cast<PHINode>(expandCodeFor(H, nullptr, &L->getHeader()->front()));
return V;
}
const TargetTransformInfo *TTI) {
// Find integer phis in order of increasing width.
SmallVector<PHINode*, 8> Phis;
- for (BasicBlock::iterator I = L->getHeader()->begin();
- PHINode *Phi = dyn_cast<PHINode>(I); ++I) {
- Phis.push_back(Phi);
+ for (auto &I : *L->getHeader()) {
+ if (auto *PN = dyn_cast<PHINode>(&I))
+ Phis.push_back(PN);
+ else
+ break;
}
+
if (TTI)
std::sort(Phis.begin(), Phis.end(), [](Value *LHS, Value *RHS) {
// Put pointers at the back and make sure pointer < pointer = false.
unsigned NumElim = 0;
DenseMap<const SCEV *, PHINode *> ExprToIVMap;
- // Process phis from wide to narrow. Mapping wide phis to the their truncation
+ // Process phis from wide to narrow. Map wide phis to their truncation
// so narrow phis can reuse them.
- for (SmallVectorImpl<PHINode*>::const_iterator PIter = Phis.begin(),
- PEnd = Phis.end(); PIter != PEnd; ++PIter) {
- PHINode *Phi = *PIter;
+ for (PHINode *Phi : Phis) {
+ auto SimplifyPHINode = [&](PHINode *PN) -> Value * {
+ if (Value *V = SimplifyInstruction(PN, DL, &SE.TLI, &SE.DT, &SE.AC))
+ return V;
+ if (!SE.isSCEVable(PN->getType()))
+ return nullptr;
+ auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(PN));
+ if (!Const)
+ return nullptr;
+ return Const->getValue();
+ };
// Fold constant phis. They may be congruent to other constant phis and
// would confuse the logic below that expects proper IVs.
- if (Value *V = SimplifyInstruction(Phi, DL, SE.TLI, SE.DT, SE.AC)) {
+ if (Value *V = SimplifyPHINode(Phi)) {
+ if (V->getType() != Phi->getType())
+ continue;
Phi->replaceAllUsesWith(V);
- DeadInsts.push_back(Phi);
+ DeadInsts.emplace_back(Phi);
++NumElim;
DEBUG_WITH_TYPE(DebugType, dbgs()
<< "INDVARS: Eliminated constant iv: " << *Phi << '\n');
if (OrigInc->getType() != IsomorphicInc->getType()) {
Instruction *IP = nullptr;
if (PHINode *PN = dyn_cast<PHINode>(OrigInc))
- IP = PN->getParent()->getFirstInsertionPt();
+ IP = &*PN->getParent()->getFirstInsertionPt();
else
IP = OrigInc->getNextNode();
CreateTruncOrBitCast(OrigInc, IsomorphicInc->getType(), IVName);
}
IsomorphicInc->replaceAllUsesWith(NewInc);
- DeadInsts.push_back(IsomorphicInc);
+ DeadInsts.emplace_back(IsomorphicInc);
}
}
DEBUG_WITH_TYPE(DebugType, dbgs()
++NumElim;
Value *NewIV = OrigPhiRef;
if (OrigPhiRef->getType() != Phi->getType()) {
- IRBuilder<> Builder(L->getHeader()->getFirstInsertionPt());
+ IRBuilder<> Builder(&*L->getHeader()->getFirstInsertionPt());
Builder.SetCurrentDebugLocation(Phi->getDebugLoc());
NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName);
}
Phi->replaceAllUsesWith(NewIV);
- DeadInsts.push_back(Phi);
+ DeadInsts.emplace_back(Phi);
}
return NumElim;
}
+Value *SCEVExpander::findExistingExpansion(const SCEV *S,
+ const Instruction *At, Loop *L) {
+ using namespace llvm::PatternMatch;
+
+ SmallVector<BasicBlock *, 4> ExitingBlocks;
+ L->getExitingBlocks(ExitingBlocks);
+
+ // Look for suitable value in simple conditions at the loop exits.
+ for (BasicBlock *BB : ExitingBlocks) {
+ ICmpInst::Predicate Pred;
+ Instruction *LHS, *RHS;
+ BasicBlock *TrueBB, *FalseBB;
+
+ if (!match(BB->getTerminator(),
+ m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)),
+ TrueBB, FalseBB)))
+ continue;
+
+ if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))
+ return LHS;
+
+ if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At))
+ return RHS;
+ }
+
+ // There is potential to make this significantly smarter, but this simple
+ // heuristic already gets some interesting cases.
+
+ // Can not find suitable value.
+ return nullptr;
+}
+
bool SCEVExpander::isHighCostExpansionHelper(
- const SCEV *S, Loop *L, SmallPtrSetImpl<const SCEV *> &Processed) {
+ const SCEV *S, Loop *L, const Instruction *At,
+ SmallPtrSetImpl<const SCEV *> &Processed) {
+
+ // If we can find an existing value for this scev avaliable at the point "At"
+ // then consider the expression cheap.
+ if (At && findExistingExpansion(S, At, L) != nullptr)
+ return false;
// Zero/One operand expressions
switch (S->getSCEVType()) {
case scConstant:
return false;
case scTruncate:
- return isHighCostExpansionHelper(cast<SCEVTruncateExpr>(S)->getOperand(), L,
- Processed);
+ return isHighCostExpansionHelper(cast<SCEVTruncateExpr>(S)->getOperand(),
+ L, At, Processed);
case scZeroExtend:
return isHighCostExpansionHelper(cast<SCEVZeroExtendExpr>(S)->getOperand(),
- L, Processed);
+ L, At, Processed);
case scSignExtend:
return isHighCostExpansionHelper(cast<SCEVSignExtendExpr>(S)->getOperand(),
- L, Processed);
+ L, At, Processed);
}
if (!Processed.insert(S).second)
if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) {
// If the divisor is a power of two and the SCEV type fits in a native
- // integer, consider the divison cheap irrespective of whether it occurs in
+ // integer, consider the division cheap irrespective of whether it occurs in
// the user code since it can be lowered into a right shift.
if (auto *SC = dyn_cast<SCEVConstant>(UDivExpr->getRHS()))
if (SC->getValue()->getValue().isPowerOf2()) {
if (!ExitingBB)
return true;
- BranchInst *ExitingBI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
- if (!ExitingBI || !ExitingBI->isConditional())
- return true;
-
- ICmpInst *OrigCond = dyn_cast<ICmpInst>(ExitingBI->getCondition());
- if (!OrigCond)
+ // At the beginning of this function we already tried to find existing value
+ // for plain 'S'. Now try to lookup 'S + 1' since it is common pattern
+ // involving division. This is just a simple search heuristic.
+ if (!At)
+ At = &ExitingBB->back();
+ if (!findExistingExpansion(
+ SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), At, L))
return true;
-
- const SCEV *RHS = SE.getSCEV(OrigCond->getOperand(1));
- RHS = SE.getMinusSCEV(RHS, SE.getConstant(RHS->getType(), 1));
- if (RHS != S) {
- const SCEV *LHS = SE.getSCEV(OrigCond->getOperand(0));
- LHS = SE.getMinusSCEV(LHS, SE.getConstant(LHS->getType(), 1));
- if (LHS != S)
- return true;
- }
}
// HowManyLessThans uses a Max expression whenever the loop is not guarded by
// BackedgeTakenCount. They may already exist in program code, and if not,
// they are not too expensive rematerialize.
if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(S)) {
- for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
- I != E; ++I) {
- if (isHighCostExpansionHelper(*I, L, Processed))
+ for (auto *Op : NAry->operands())
+ if (isHighCostExpansionHelper(Op, L, At, Processed))
return true;
- }
}
// If we haven't recognized an expensive SCEV pattern, assume it's an
return false;
}
+Value *SCEVExpander::expandCodeForPredicate(const SCEVPredicate *Pred,
+ Instruction *IP) {
+ assert(IP);
+ switch (Pred->getKind()) {
+ case SCEVPredicate::P_Union:
+ return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred), IP);
+ case SCEVPredicate::P_Equal:
+ return expandEqualPredicate(cast<SCEVEqualPredicate>(Pred), IP);
+ }
+ llvm_unreachable("Unknown SCEV predicate type");
+}
+
+Value *SCEVExpander::expandEqualPredicate(const SCEVEqualPredicate *Pred,
+ Instruction *IP) {
+ Value *Expr0 = expandCodeFor(Pred->getLHS(), Pred->getLHS()->getType(), IP);
+ Value *Expr1 = expandCodeFor(Pred->getRHS(), Pred->getRHS()->getType(), IP);
+
+ Builder.SetInsertPoint(IP);
+ auto *I = Builder.CreateICmpNE(Expr0, Expr1, "ident.check");
+ return I;
+}
+
+Value *SCEVExpander::expandUnionPredicate(const SCEVUnionPredicate *Union,
+ Instruction *IP) {
+ auto *BoolType = IntegerType::get(IP->getContext(), 1);
+ Value *Check = ConstantInt::getNullValue(BoolType);
+
+ // Loop over all checks in this set.
+ for (auto Pred : Union->getPredicates()) {
+ auto *NextCheck = expandCodeForPredicate(Pred, IP);
+ Builder.SetInsertPoint(IP);
+ Check = Builder.CreateOr(Check, NextCheck);
+ }
+
+ return Check;
+}
+
namespace {
// Search for a SCEV subexpression that is not safe to expand. Any expression
// that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely
projects / oota-llvm.git / blobdiff