// 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();
+ if (auto *CPI = dyn_cast<CatchPadInst>(I))
+ IP = CPI->getNormalDest()->begin();
+
+ while (isa<PHINode>(IP))
+ ++IP;
+
+ while (IP->isEHPad()) {
+ if (isa<LandingPadInst>(IP) || isa<CleanupPadInst>(IP)) {
+ ++IP;
+ } else if (auto *TPI = dyn_cast<TerminatePadInst>(IP)) {
+ IP = TPI->getUnwindDest()->getFirstNonPHI()->getIterator();
+ } else if (auto *CEPI = dyn_cast<CatchEndPadInst>(IP)) {
+ IP = CEPI->getUnwindDest()->getFirstNonPHI()->getIterator();
+ } else if (auto *CEPI = dyn_cast<CleanupEndPadInst>(IP)) {
+ IP = CEPI->getUnwindDest()->getFirstNonPHI()->getIterator();
+ } else if (isa<CatchPadInst>(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();
- if (CatchPadInst *CPI = dyn_cast<CatchPadInst>(I))
- IP = CPI->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;
}
}
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.
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;
}
}
if (!Preheader) break;
// Ok, move up a level.
- Builder.SetInsertPoint(Preheader, Preheader->getTerminator());
+ Builder.SetInsertPoint(Preheader->getTerminator());
}
// Emit a GEP.
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,
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) ||
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
// 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())) {
+ !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();
+ Instruction *InsertPt = &*Builder.GetInsertPoint();
for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;
L = L->getParentLoop())
if (SE.isLoopInvariant(S, L)) {
// 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;
}
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;
}
PEnd = Phis.end(); PIter != PEnd; ++PIter) {
PHINode *Phi = *PIter;
+ 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.emplace_back(Phi);
++NumElim;
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();
++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);
}
const Instruction *At, Loop *L) {
using namespace llvm::PatternMatch;
- SmallVector<BasicBlock *, 4> Latches;
- L->getLoopLatches(Latches);
+ SmallVector<BasicBlock *, 4> ExitingBlocks;
+ L->getExitingBlocks(ExitingBlocks);
- // Look for suitable value in simple conditions at the loop latches.
- for (BasicBlock *BB : Latches) {
+ // 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 (!ExitingBB)
return true;
- BranchInst *ExitingBI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
- if (!ExitingBI || !ExitingBI->isConditional())
+ // 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;
-
- ICmpInst *OrigCond = dyn_cast<ICmpInst>(ExitingBI->getCondition());
- if (!OrigCond)
- 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
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