}
static BasicBlock::iterator findInsertPointAfter(Instruction *I,
- DominatorTree &DT,
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)) {
+ if (isa<FuncletPadInst>(IP) || isa<LandingPadInst>(IP)) {
++IP;
- } else if (auto *TPI = dyn_cast<TerminatePadInst>(IP)) {
- IP = TPI->getUnwindDest()->getFirstNonPHI();
- } else if (auto *CEPI = dyn_cast<CatchEndPadInst>(IP)) {
- IP = CEPI->getUnwindDest()->getFirstNonPHI();
- } else if (auto *CEPI = dyn_cast<CleanupEndPadInst>(IP)) {
- IP = CEPI->getUnwindDest()->getFirstNonPHI();
- } else if (auto *CPI = dyn_cast<CatchPadInst>(IP)) {
- BasicBlock *NormalDest = CPI->getNormalDest();
- if (NormalDest == MustDominate || DT.dominates(NormalDest, MustDominate))
- IP = NormalDest->getFirstNonPHI();
- else
- IP = CPI->getUnwindDest()->getFirstNonPHI();
+ } else if (isa<CatchSwitchInst>(IP)) {
+ IP = MustDominate->getFirstInsertionPt();
} else {
llvm_unreachable("unexpected eh pad!");
}
// Cast the instruction immediately after the instruction.
Instruction *I = cast<Instruction>(V);
- BasicBlock::iterator IP =
- findInsertPointAfter(I, SE.DT, Builder.GetInsertBlock());
+ BasicBlock::iterator IP = findInsertPointAfter(I, Builder.GetInsertBlock());
return ReuseOrCreateCast(I, Ty, Op, IP);
}
// Check for divisibility.
if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor)) {
ConstantInt *CI =
- ConstantInt::get(SE.getContext(),
- C->getValue()->getValue().sdiv(
- FC->getValue()->getValue()));
+ ConstantInt::get(SE.getContext(), C->getAPInt().sdiv(FC->getAPInt()));
// If the quotient is zero and the remainder is non-zero, reject
// the value at this scale. It will be considered for subsequent
// smaller scales.
if (!CI->isZero()) {
const SCEV *Div = SE.getConstant(CI);
S = Div;
- Remainder =
- SE.getAddExpr(Remainder,
- SE.getConstant(C->getValue()->getValue().srem(
- FC->getValue()->getValue())));
+ Remainder = SE.getAddExpr(
+ Remainder, SE.getConstant(C->getAPInt().srem(FC->getAPInt())));
return true;
}
}
// of the given factor. If so, we can factor it.
const SCEVConstant *FC = cast<SCEVConstant>(Factor);
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0)))
- if (!C->getValue()->getValue().srem(FC->getValue()->getValue())) {
+ if (!C->getAPInt().srem(FC->getAPInt())) {
SmallVector<const SCEV *, 4> NewMulOps(M->op_begin(), M->op_end());
- NewMulOps[0] = SE.getConstant(
- C->getValue()->getValue().sdiv(FC->getValue()->getValue()));
+ NewMulOps[0] = SE.getConstant(C->getAPInt().sdiv(FC->getAPInt()));
S = SE.getMulExpr(NewMulOps);
return true;
}
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.
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;
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;
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)) {
// 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) {
// 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; ++I) {
- 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);
Value *LHS = expandCodeFor(S->getLHS(), Ty);
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
- const APInt &RHS = SC->getValue()->getValue();
+ const APInt &RHS = SC->getAPInt();
if (RHS.isPowerOf2())
return InsertBinop(Instruction::LShr, LHS,
ConstantInt::get(Ty, RHS.logBase2()));
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)) {
!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.
SmallVector<Instruction*, 4> IVIncs;
for(;;) {
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;
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));
NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType());
Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
S->getNoWrapFlags(SCEV::FlagNW)));
- BasicBlock::iterator NewInsertPt = findInsertPointAfter(
- cast<Instruction>(V), SE.DT, Builder.GetInsertBlock());
+ BasicBlock::iterator NewInsertPt =
+ findInsertPointAfter(cast<Instruction>(V), Builder.GetInsertBlock());
V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,
&*NewInsertPt);
return V;
}
// 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;
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.
DenseMap<const SCEV *, PHINode *> ExprToIVMap;
// 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.emplace_back(Phi);
++NumElim;
// 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 (SC->getAPInt().isPowerOf2()) {
const DataLayout &DL =
L->getHeader()->getParent()->getParent()->getDataLayout();
unsigned Width = cast<IntegerType>(UDivExpr->getType())->getBitWidth();
// 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, At, 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