diff options
Diffstat (limited to 'contrib/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp')
| -rw-r--r-- | contrib/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp | 389 |
1 files changed, 152 insertions, 237 deletions
diff --git a/contrib/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/contrib/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp index 7b60373..4b59f3d 100644 --- a/contrib/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/contrib/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -28,7 +28,7 @@ // // The SCEV for %i is {0,+,1}<%L>. The SCEV for %i.next is {1,+,1}<%L>, however // it's useful to think about these as the same register, with some uses using -// the value of the register before the add and some using // it after. In this +// the value of the register before the add and some using it after. In this // example, the icmp is a post-increment user, since it uses %i.next, which is // the value of the induction variable after the increment. The other common // case of post-increment users is users outside the loop. @@ -68,6 +68,7 @@ #include "llvm/IR/Dominators.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Module.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" @@ -111,8 +112,6 @@ public: /// a particular register. SmallBitVector UsedByIndices; - RegSortData() {} - void print(raw_ostream &OS) const; void dump() const; }; @@ -186,9 +185,8 @@ RegUseTracker::SwapAndDropUse(size_t LUIdx, size_t LastLUIdx) { // Update RegUses. The data structure is not optimized for this purpose; // we must iterate through it and update each of the bit vectors. - for (RegUsesTy::iterator I = RegUsesMap.begin(), E = RegUsesMap.end(); - I != E; ++I) { - SmallBitVector &UsedByIndices = I->second.UsedByIndices; + for (auto &Pair : RegUsesMap) { + SmallBitVector &UsedByIndices = Pair.second.UsedByIndices; if (LUIdx < UsedByIndices.size()) UsedByIndices[LUIdx] = LastLUIdx < UsedByIndices.size() ? UsedByIndices[LastLUIdx] : 0; @@ -298,9 +296,8 @@ static void DoInitialMatch(const SCEV *S, Loop *L, // Look at add operands. if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { - for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); - I != E; ++I) - DoInitialMatch(*I, L, Good, Bad, SE); + for (const SCEV *S : Add->operands()) + DoInitialMatch(S, L, Good, Bad, SE); return; } @@ -327,12 +324,10 @@ static void DoInitialMatch(const SCEV *S, Loop *L, DoInitialMatch(NewMul, L, MyGood, MyBad, SE); const SCEV *NegOne = SE.getSCEV(ConstantInt::getAllOnesValue( SE.getEffectiveSCEVType(NewMul->getType()))); - for (SmallVectorImpl<const SCEV *>::const_iterator I = MyGood.begin(), - E = MyGood.end(); I != E; ++I) - Good.push_back(SE.getMulExpr(NegOne, *I)); - for (SmallVectorImpl<const SCEV *>::const_iterator I = MyBad.begin(), - E = MyBad.end(); I != E; ++I) - Bad.push_back(SE.getMulExpr(NegOne, *I)); + for (const SCEV *S : MyGood) + Good.push_back(SE.getMulExpr(NegOne, S)); + for (const SCEV *S : MyBad) + Bad.push_back(SE.getMulExpr(NegOne, S)); return; } @@ -444,9 +439,8 @@ bool Formula::hasRegsUsedByUsesOtherThan(size_t LUIdx, if (ScaledReg) if (RegUses.isRegUsedByUsesOtherThan(ScaledReg, LUIdx)) return true; - for (SmallVectorImpl<const SCEV *>::const_iterator I = BaseRegs.begin(), - E = BaseRegs.end(); I != E; ++I) - if (RegUses.isRegUsedByUsesOtherThan(*I, LUIdx)) + for (const SCEV *BaseReg : BaseRegs) + if (RegUses.isRegUsedByUsesOtherThan(BaseReg, LUIdx)) return true; return false; } @@ -461,10 +455,9 @@ void Formula::print(raw_ostream &OS) const { if (!First) OS << " + "; else First = false; OS << BaseOffset; } - for (SmallVectorImpl<const SCEV *>::const_iterator I = BaseRegs.begin(), - E = BaseRegs.end(); I != E; ++I) { + for (const SCEV *BaseReg : BaseRegs) { if (!First) OS << " + "; else First = false; - OS << "reg(" << **I << ')'; + OS << "reg(" << *BaseReg << ')'; } if (HasBaseReg && BaseRegs.empty()) { if (!First) OS << " + "; else First = false; @@ -577,10 +570,8 @@ static const SCEV *getExactSDiv(const SCEV *LHS, const SCEV *RHS, if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(LHS)) { if (IgnoreSignificantBits || isAddSExtable(Add, SE)) { SmallVector<const SCEV *, 8> Ops; - for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); - I != E; ++I) { - const SCEV *Op = getExactSDiv(*I, RHS, SE, - IgnoreSignificantBits); + for (const SCEV *S : Add->operands()) { + const SCEV *Op = getExactSDiv(S, RHS, SE, IgnoreSignificantBits); if (!Op) return nullptr; Ops.push_back(Op); } @@ -594,9 +585,7 @@ static const SCEV *getExactSDiv(const SCEV *LHS, const SCEV *RHS, if (IgnoreSignificantBits || isMulSExtable(Mul, SE)) { SmallVector<const SCEV *, 4> Ops; bool Found = false; - for (SCEVMulExpr::op_iterator I = Mul->op_begin(), E = Mul->op_end(); - I != E; ++I) { - const SCEV *S = *I; + for (const SCEV *S : Mul->operands()) { if (!Found) if (const SCEV *Q = getExactSDiv(S, RHS, SE, IgnoreSignificantBits)) { @@ -766,9 +755,8 @@ static bool isHighCostExpansion(const SCEV *S, return false; if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { - for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); - I != E; ++I) { - if (isHighCostExpansion(*I, Processed, SE)) + for (const SCEV *S : Add->operands()) { + if (isHighCostExpansion(S, Processed, SE)) return true; } return false; @@ -819,11 +807,11 @@ DeleteTriviallyDeadInstructions(SmallVectorImpl<WeakVH> &DeadInsts) { if (!I || !isInstructionTriviallyDead(I)) continue; - for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) - if (Instruction *U = dyn_cast<Instruction>(*OI)) { - *OI = nullptr; + for (Use &O : I->operands()) + if (Instruction *U = dyn_cast<Instruction>(O)) { + O = nullptr; if (U->use_empty()) - DeadInsts.push_back(U); + DeadInsts.emplace_back(U); } I->eraseFromParent(); @@ -1002,9 +990,7 @@ void Cost::RateFormula(const TargetTransformInfo &TTI, if (isLoser()) return; } - for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(), - E = F.BaseRegs.end(); I != E; ++I) { - const SCEV *BaseReg = *I; + for (const SCEV *BaseReg : F.BaseRegs) { if (VisitedRegs.count(BaseReg)) { Lose(); return; @@ -1027,9 +1013,8 @@ void Cost::RateFormula(const TargetTransformInfo &TTI, ScaleCost += getScalingFactorCost(TTI, LU, F); // Tally up the non-zero immediates. - for (SmallVectorImpl<int64_t>::const_iterator I = Offsets.begin(), - E = Offsets.end(); I != E; ++I) { - int64_t Offset = (uint64_t)*I + F.BaseOffset; + for (int64_t O : Offsets) { + int64_t Offset = (uint64_t)O + F.BaseOffset; if (F.BaseGV) ImmCost += 64; // Handle symbolic values conservatively. // TODO: This should probably be the pointer size. @@ -1152,10 +1137,9 @@ void LSRFixup::print(raw_ostream &OS) const { OS << ", OperandValToReplace="; OperandValToReplace->printAsOperand(OS, /*PrintType=*/false); - for (PostIncLoopSet::const_iterator I = PostIncLoops.begin(), - E = PostIncLoops.end(); I != E; ++I) { + for (const Loop *PIL : PostIncLoops) { OS << ", PostIncLoop="; - (*I)->getHeader()->printAsOperand(OS, /*PrintType=*/false); + PIL->getHeader()->printAsOperand(OS, /*PrintType=*/false); } if (LUIdx != ~size_t(0)) @@ -1301,9 +1285,8 @@ bool LSRUse::InsertFormula(const Formula &F) { assert((!F.ScaledReg || !F.ScaledReg->isZero()) && "Zero allocated in a scaled register!"); #ifndef NDEBUG - for (SmallVectorImpl<const SCEV *>::const_iterator I = - F.BaseRegs.begin(), E = F.BaseRegs.end(); I != E; ++I) - assert(!(*I)->isZero() && "Zero allocated in a base register!"); + for (const SCEV *BaseReg : F.BaseRegs) + assert(!BaseReg->isZero() && "Zero allocated in a base register!"); #endif // Add the formula to the list. @@ -1327,11 +1310,9 @@ void LSRUse::DeleteFormula(Formula &F) { /// RecomputeRegs - Recompute the Regs field, and update RegUses. void LSRUse::RecomputeRegs(size_t LUIdx, RegUseTracker &RegUses) { // Now that we've filtered out some formulae, recompute the Regs set. - SmallPtrSet<const SCEV *, 4> OldRegs = Regs; + SmallPtrSet<const SCEV *, 4> OldRegs = std::move(Regs); Regs.clear(); - for (SmallVectorImpl<Formula>::const_iterator I = Formulae.begin(), - E = Formulae.end(); I != E; ++I) { - const Formula &F = *I; + for (const Formula &F : Formulae) { if (F.ScaledReg) Regs.insert(F.ScaledReg); Regs.insert(F.BaseRegs.begin(), F.BaseRegs.end()); } @@ -1357,11 +1338,11 @@ void LSRUse::print(raw_ostream &OS) const { } OS << ", Offsets={"; - for (SmallVectorImpl<int64_t>::const_iterator I = Offsets.begin(), - E = Offsets.end(); I != E; ++I) { - OS << *I; - if (std::next(I) != E) - OS << ','; + bool NeedComma = false; + for (int64_t O : Offsets) { + if (NeedComma) OS << ','; + OS << O; + NeedComma = true; } OS << '}'; @@ -1386,9 +1367,6 @@ static bool isAMCompletelyFolded(const TargetTransformInfo &TTI, case LSRUse::Address: return TTI.isLegalAddressingMode(AccessTy, BaseGV, BaseOffset, HasBaseReg, Scale); - // Otherwise, just guess that reg+reg addressing is legal. - //return ; - case LSRUse::ICmpZero: // There's not even a target hook for querying whether it would be legal to // fold a GV into an ICmp. @@ -1928,12 +1906,12 @@ void LSRInstance::OptimizeShadowIV() { /// set the IV user and stride information and return true, otherwise return /// false. bool LSRInstance::FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse) { - for (IVUsers::iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) - if (UI->getUser() == Cond) { + for (IVStrideUse &U : IU) + if (U.getUser() == Cond) { // NOTE: we could handle setcc instructions with multiple uses here, but // InstCombine does it as well for simple uses, it's not clear that it // occurs enough in real life to handle. - CondUse = UI; + CondUse = &U; return true; } return false; @@ -2108,8 +2086,7 @@ LSRInstance::OptimizeLoopTermCond() { SmallVector<BasicBlock*, 8> ExitingBlocks; L->getExitingBlocks(ExitingBlocks); - for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { - BasicBlock *ExitingBlock = ExitingBlocks[i]; + for (BasicBlock *ExitingBlock : ExitingBlocks) { // Get the terminating condition for the loop if possible. If we // can, we want to change it to use a post-incremented version of its @@ -2352,9 +2329,7 @@ LSRInstance::FindUseWithSimilarFormula(const Formula &OrigF, LU.WidestFixupType == OrigLU.WidestFixupType && LU.HasFormulaWithSameRegs(OrigF)) { // Scan through this use's formulae. - for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(), - E = LU.Formulae.end(); I != E; ++I) { - const Formula &F = *I; + for (const Formula &F : LU.Formulae) { // Check to see if this formula has the same registers and symbols // as OrigF. if (F.BaseRegs == OrigF.BaseRegs && @@ -2382,8 +2357,8 @@ void LSRInstance::CollectInterestingTypesAndFactors() { // Collect interesting types and strides. SmallVector<const SCEV *, 4> Worklist; - for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) { - const SCEV *Expr = IU.getExpr(*UI); + for (const IVStrideUse &U : IU) { + const SCEV *Expr = IU.getExpr(U); // Collect interesting types. Types.insert(SE.getEffectiveSCEVType(Expr->getType())); @@ -2586,25 +2561,23 @@ isProfitableChain(IVChain &Chain, SmallPtrSetImpl<Instruction*> &Users, unsigned NumConstIncrements = 0; unsigned NumVarIncrements = 0; unsigned NumReusedIncrements = 0; - for (IVChain::const_iterator I = Chain.begin(), E = Chain.end(); - I != E; ++I) { - - if (I->IncExpr->isZero()) + for (const IVInc &Inc : Chain) { + if (Inc.IncExpr->isZero()) continue; // Incrementing by zero or some constant is neutral. We assume constants can // be folded into an addressing mode or an add's immediate operand. - if (isa<SCEVConstant>(I->IncExpr)) { + if (isa<SCEVConstant>(Inc.IncExpr)) { ++NumConstIncrements; continue; } - if (I->IncExpr == LastIncExpr) + if (Inc.IncExpr == LastIncExpr) ++NumReusedIncrements; else ++NumVarIncrements; - LastIncExpr = I->IncExpr; + LastIncExpr = Inc.IncExpr; } // An IV chain with a single increment is handled by LSR's postinc // uses. However, a chain with multiple increments requires keeping the IV's @@ -2839,12 +2812,11 @@ void LSRInstance::FinalizeChain(IVChain &Chain) { assert(!Chain.Incs.empty() && "empty IV chains are not allowed"); DEBUG(dbgs() << "Final Chain: " << *Chain.Incs[0].UserInst << "\n"); - for (IVChain::const_iterator I = Chain.begin(), E = Chain.end(); - I != E; ++I) { - DEBUG(dbgs() << " Inc: " << *I->UserInst << "\n"); - User::op_iterator UseI = - std::find(I->UserInst->op_begin(), I->UserInst->op_end(), I->IVOperand); - assert(UseI != I->UserInst->op_end() && "cannot find IV operand"); + for (const IVInc &Inc : Chain) { + DEBUG(dbgs() << " Inc: " << Inc.UserInst << "\n"); + auto UseI = std::find(Inc.UserInst->op_begin(), Inc.UserInst->op_end(), + Inc.IVOperand); + assert(UseI != Inc.UserInst->op_end() && "cannot find IV operand"); IVIncSet.insert(UseI); } } @@ -2907,20 +2879,18 @@ void LSRInstance::GenerateIVChain(const IVChain &Chain, SCEVExpander &Rewriter, Type *IVTy = IVSrc->getType(); Type *IntTy = SE.getEffectiveSCEVType(IVTy); const SCEV *LeftOverExpr = nullptr; - for (IVChain::const_iterator IncI = Chain.begin(), - IncE = Chain.end(); IncI != IncE; ++IncI) { - - Instruction *InsertPt = IncI->UserInst; + for (const IVInc &Inc : Chain) { + Instruction *InsertPt = Inc.UserInst; if (isa<PHINode>(InsertPt)) InsertPt = L->getLoopLatch()->getTerminator(); // IVOper will replace the current IV User's operand. IVSrc is the IV // value currently held in a register. Value *IVOper = IVSrc; - if (!IncI->IncExpr->isZero()) { + if (!Inc.IncExpr->isZero()) { // IncExpr was the result of subtraction of two narrow values, so must // be signed. - const SCEV *IncExpr = SE.getNoopOrSignExtend(IncI->IncExpr, IntTy); + const SCEV *IncExpr = SE.getNoopOrSignExtend(Inc.IncExpr, IntTy); LeftOverExpr = LeftOverExpr ? SE.getAddExpr(LeftOverExpr, IncExpr) : IncExpr; } @@ -2933,22 +2903,21 @@ void LSRInstance::GenerateIVChain(const IVChain &Chain, SCEVExpander &Rewriter, IVOper = Rewriter.expandCodeFor(IVOperExpr, IVTy, InsertPt); // If an IV increment can't be folded, use it as the next IV value. - if (!canFoldIVIncExpr(LeftOverExpr, IncI->UserInst, IncI->IVOperand, - TTI)) { + if (!canFoldIVIncExpr(LeftOverExpr, Inc.UserInst, Inc.IVOperand, TTI)) { assert(IVTy == IVOper->getType() && "inconsistent IV increment type"); IVSrc = IVOper; LeftOverExpr = nullptr; } } - Type *OperTy = IncI->IVOperand->getType(); + Type *OperTy = Inc.IVOperand->getType(); if (IVTy != OperTy) { assert(SE.getTypeSizeInBits(IVTy) >= SE.getTypeSizeInBits(OperTy) && "cannot extend a chained IV"); IRBuilder<> Builder(InsertPt); IVOper = Builder.CreateTruncOrBitCast(IVOper, OperTy, "lsr.chain"); } - IncI->UserInst->replaceUsesOfWith(IncI->IVOperand, IVOper); - DeadInsts.push_back(IncI->IVOperand); + Inc.UserInst->replaceUsesOfWith(Inc.IVOperand, IVOper); + DeadInsts.emplace_back(Inc.IVOperand); } // If LSR created a new, wider phi, we may also replace its postinc. We only // do this if we also found a wide value for the head of the chain. @@ -2970,17 +2939,17 @@ void LSRInstance::GenerateIVChain(const IVChain &Chain, SCEVExpander &Rewriter, IVOper = Builder.CreatePointerCast(IVSrc, PostIncTy, "lsr.chain"); } Phi->replaceUsesOfWith(PostIncV, IVOper); - DeadInsts.push_back(PostIncV); + DeadInsts.emplace_back(PostIncV); } } } void LSRInstance::CollectFixupsAndInitialFormulae() { - for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) { - Instruction *UserInst = UI->getUser(); + for (const IVStrideUse &U : IU) { + Instruction *UserInst = U.getUser(); // Skip IV users that are part of profitable IV Chains. User::op_iterator UseI = std::find(UserInst->op_begin(), UserInst->op_end(), - UI->getOperandValToReplace()); + U.getOperandValToReplace()); assert(UseI != UserInst->op_end() && "cannot find IV operand"); if (IVIncSet.count(UseI)) continue; @@ -2988,8 +2957,8 @@ void LSRInstance::CollectFixupsAndInitialFormulae() { // Record the uses. LSRFixup &LF = getNewFixup(); LF.UserInst = UserInst; - LF.OperandValToReplace = UI->getOperandValToReplace(); - LF.PostIncLoops = UI->getPostIncLoops(); + LF.OperandValToReplace = U.getOperandValToReplace(); + LF.PostIncLoops = U.getPostIncLoops(); LSRUse::KindType Kind = LSRUse::Basic; Type *AccessTy = nullptr; @@ -2998,7 +2967,7 @@ void LSRInstance::CollectFixupsAndInitialFormulae() { AccessTy = getAccessType(LF.UserInst); } - const SCEV *S = IU.getExpr(*UI); + const SCEV *S = IU.getExpr(U); // Equality (== and !=) ICmps are special. We can rewrite (i == N) as // (N - i == 0), and this allows (N - i) to be the expression that we work @@ -3090,9 +3059,8 @@ LSRInstance::InsertSupplementalFormula(const SCEV *S, void LSRInstance::CountRegisters(const Formula &F, size_t LUIdx) { if (F.ScaledReg) RegUses.CountRegister(F.ScaledReg, LUIdx); - for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(), - E = F.BaseRegs.end(); I != E; ++I) - RegUses.CountRegister(*I, LUIdx); + for (const SCEV *BaseReg : F.BaseRegs) + RegUses.CountRegister(BaseReg, LUIdx); } /// InsertFormula - If the given formula has not yet been inserted, add it to @@ -3213,9 +3181,8 @@ static const SCEV *CollectSubexprs(const SCEV *S, const SCEVConstant *C, if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { // Break out add operands. - for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); - I != E; ++I) { - const SCEV *Remainder = CollectSubexprs(*I, C, Ops, L, SE, Depth+1); + for (const SCEV *S : Add->operands()) { + const SCEV *Remainder = CollectSubexprs(S, C, Ops, L, SE, Depth+1); if (Remainder) Ops.push_back(C ? SE.getMulExpr(C, Remainder) : Remainder); } @@ -3373,9 +3340,7 @@ void LSRInstance::GenerateCombinations(LSRUse &LU, unsigned LUIdx, Formula F = Base; F.BaseRegs.clear(); SmallVector<const SCEV *, 4> Ops; - for (SmallVectorImpl<const SCEV *>::const_iterator - I = Base.BaseRegs.begin(), E = Base.BaseRegs.end(); I != E; ++I) { - const SCEV *BaseReg = *I; + for (const SCEV *BaseReg : Base.BaseRegs) { if (SE.properlyDominates(BaseReg, L->getHeader()) && !SE.hasComputableLoopEvolution(BaseReg, L)) Ops.push_back(BaseReg); @@ -3432,15 +3397,13 @@ void LSRInstance::GenerateConstantOffsetsImpl( LSRUse &LU, unsigned LUIdx, const Formula &Base, const SmallVectorImpl<int64_t> &Worklist, size_t Idx, bool IsScaledReg) { const SCEV *G = IsScaledReg ? Base.ScaledReg : Base.BaseRegs[Idx]; - for (SmallVectorImpl<int64_t>::const_iterator I = Worklist.begin(), - E = Worklist.end(); - I != E; ++I) { + for (int64_t Offset : Worklist) { Formula F = Base; - F.BaseOffset = (uint64_t)Base.BaseOffset - *I; - if (isLegalUse(TTI, LU.MinOffset - *I, LU.MaxOffset - *I, LU.Kind, + F.BaseOffset = (uint64_t)Base.BaseOffset - Offset; + if (isLegalUse(TTI, LU.MinOffset - Offset, LU.MaxOffset - Offset, LU.Kind, LU.AccessTy, F)) { // Add the offset to the base register. - const SCEV *NewG = SE.getAddExpr(SE.getConstant(G->getType(), *I), G); + const SCEV *NewG = SE.getAddExpr(SE.getConstant(G->getType(), Offset), G); // If it cancelled out, drop the base register, otherwise update it. if (NewG->isZero()) { if (IsScaledReg) { @@ -3506,10 +3469,7 @@ void LSRInstance::GenerateICmpZeroScales(LSRUse &LU, unsigned LUIdx, assert(!Base.BaseGV && "ICmpZero use is not legal!"); // Check each interesting stride. - for (SmallSetVector<int64_t, 8>::const_iterator - I = Factors.begin(), E = Factors.end(); I != E; ++I) { - int64_t Factor = *I; - + for (int64_t Factor : Factors) { // Check that the multiplication doesn't overflow. if (Base.BaseOffset == INT64_MIN && Factor == -1) continue; @@ -3593,10 +3553,7 @@ void LSRInstance::GenerateScales(LSRUse &LU, unsigned LUIdx, Formula Base) { assert(Base.Scale == 0 && "Unscale did not did its job!"); // Check each interesting stride. - for (SmallSetVector<int64_t, 8>::const_iterator - I = Factors.begin(), E = Factors.end(); I != E; ++I) { - int64_t Factor = *I; - + for (int64_t Factor : Factors) { Base.Scale = Factor; Base.HasBaseReg = Base.BaseRegs.size() > 1; // Check whether this scale is going to be legal. @@ -3652,16 +3609,13 @@ void LSRInstance::GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base) { if (!DstTy) return; DstTy = SE.getEffectiveSCEVType(DstTy); - for (SmallSetVector<Type *, 4>::const_iterator - I = Types.begin(), E = Types.end(); I != E; ++I) { - Type *SrcTy = *I; + for (Type *SrcTy : Types) { if (SrcTy != DstTy && TTI.isTruncateFree(SrcTy, DstTy)) { Formula F = Base; - if (F.ScaledReg) F.ScaledReg = SE.getAnyExtendExpr(F.ScaledReg, *I); - for (SmallVectorImpl<const SCEV *>::iterator J = F.BaseRegs.begin(), - JE = F.BaseRegs.end(); J != JE; ++J) - *J = SE.getAnyExtendExpr(*J, SrcTy); + if (F.ScaledReg) F.ScaledReg = SE.getAnyExtendExpr(F.ScaledReg, SrcTy); + for (const SCEV *&BaseReg : F.BaseRegs) + BaseReg = SE.getAnyExtendExpr(BaseReg, SrcTy); // TODO: This assumes we've done basic processing on all uses and // have an idea what the register usage is. @@ -3708,20 +3662,17 @@ void WorkItem::dump() const { void LSRInstance::GenerateCrossUseConstantOffsets() { // Group the registers by their value without any added constant offset. typedef std::map<int64_t, const SCEV *> ImmMapTy; - typedef DenseMap<const SCEV *, ImmMapTy> RegMapTy; - RegMapTy Map; + DenseMap<const SCEV *, ImmMapTy> Map; DenseMap<const SCEV *, SmallBitVector> UsedByIndicesMap; SmallVector<const SCEV *, 8> Sequence; - for (RegUseTracker::const_iterator I = RegUses.begin(), E = RegUses.end(); - I != E; ++I) { - const SCEV *Reg = *I; + for (const SCEV *Use : RegUses) { + const SCEV *Reg = Use; // Make a copy for ExtractImmediate to modify. int64_t Imm = ExtractImmediate(Reg, SE); - std::pair<RegMapTy::iterator, bool> Pair = - Map.insert(std::make_pair(Reg, ImmMapTy())); + auto Pair = Map.insert(std::make_pair(Reg, ImmMapTy())); if (Pair.second) Sequence.push_back(Reg); - Pair.first->second.insert(std::make_pair(Imm, *I)); - UsedByIndicesMap[Reg] |= RegUses.getUsedByIndices(*I); + Pair.first->second.insert(std::make_pair(Imm, Use)); + UsedByIndicesMap[Reg] |= RegUses.getUsedByIndices(Use); } // Now examine each set of registers with the same base value. Build up @@ -3729,9 +3680,7 @@ void LSRInstance::GenerateCrossUseConstantOffsets() { // not adding formulae and register counts while we're searching. SmallVector<WorkItem, 32> WorkItems; SmallSet<std::pair<size_t, int64_t>, 32> UniqueItems; - for (SmallVectorImpl<const SCEV *>::const_iterator I = Sequence.begin(), - E = Sequence.end(); I != E; ++I) { - const SCEV *Reg = *I; + for (const SCEV *Reg : Sequence) { const ImmMapTy &Imms = Map.find(Reg)->second; // It's not worthwhile looking for reuse if there's only one offset. @@ -3739,9 +3688,8 @@ void LSRInstance::GenerateCrossUseConstantOffsets() { continue; DEBUG(dbgs() << "Generating cross-use offsets for " << *Reg << ':'; - for (ImmMapTy::const_iterator J = Imms.begin(), JE = Imms.end(); - J != JE; ++J) - dbgs() << ' ' << J->first; + for (const auto &Entry : Imms) + dbgs() << ' ' << Entry.first; dbgs() << '\n'); // Examine each offset. @@ -3786,9 +3734,7 @@ void LSRInstance::GenerateCrossUseConstantOffsets() { UniqueItems.clear(); // Now iterate through the worklist and add new formulae. - for (SmallVectorImpl<WorkItem>::const_iterator I = WorkItems.begin(), - E = WorkItems.end(); I != E; ++I) { - const WorkItem &WI = *I; + for (const WorkItem &WI : WorkItems) { size_t LUIdx = WI.LUIdx; LSRUse &LU = Uses[LUIdx]; int64_t Imm = WI.Imm; @@ -3827,7 +3773,7 @@ void LSRInstance::GenerateCrossUseConstantOffsets() { if (C->getValue()->isNegative() != (NewF.BaseOffset < 0) && (C->getValue()->getValue().abs() * APInt(BitWidth, F.Scale)) - .ule(abs64(NewF.BaseOffset))) + .ule(std::abs(NewF.BaseOffset))) continue; // OK, looks good. @@ -3853,12 +3799,10 @@ void LSRInstance::GenerateCrossUseConstantOffsets() { // If the new formula has a constant in a register, and adding the // constant value to the immediate would produce a value closer to // zero than the immediate itself, then the formula isn't worthwhile. - for (SmallVectorImpl<const SCEV *>::const_iterator - J = NewF.BaseRegs.begin(), JE = NewF.BaseRegs.end(); - J != JE; ++J) - if (const SCEVConstant *C = dyn_cast<SCEVConstant>(*J)) + for (const SCEV *NewReg : NewF.BaseRegs) + if (const SCEVConstant *C = dyn_cast<SCEVConstant>(NewReg)) if ((C->getValue()->getValue() + NewF.BaseOffset).abs().slt( - abs64(NewF.BaseOffset)) && + std::abs(NewF.BaseOffset)) && (C->getValue()->getValue() + NewF.BaseOffset).countTrailingZeros() >= countTrailingZeros<uint64_t>(NewF.BaseOffset)) @@ -3959,9 +3903,7 @@ void LSRInstance::FilterOutUndesirableDedicatedRegisters() { } else { SmallVector<const SCEV *, 4> Key; - for (SmallVectorImpl<const SCEV *>::const_iterator J = F.BaseRegs.begin(), - JE = F.BaseRegs.end(); J != JE; ++J) { - const SCEV *Reg = *J; + for (const SCEV *Reg : F.BaseRegs) { if (RegUses.isRegUsedByUsesOtherThan(Reg, LUIdx)) Key.push_back(Reg); } @@ -4023,9 +3965,8 @@ static const size_t ComplexityLimit = UINT16_MAX; /// isn't always sufficient. size_t LSRInstance::EstimateSearchSpaceComplexity() const { size_t Power = 1; - for (SmallVectorImpl<LSRUse>::const_iterator I = Uses.begin(), - E = Uses.end(); I != E; ++I) { - size_t FSize = I->Formulae.size(); + for (const LSRUse &LU : Uses) { + size_t FSize = LU.Formulae.size(); if (FSize >= ComplexityLimit) { Power = ComplexityLimit; break; @@ -4116,9 +4057,7 @@ void LSRInstance::NarrowSearchSpaceByCollapsingUnrolledCode() { for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { LSRUse &LU = Uses[LUIdx]; - for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(), - E = LU.Formulae.end(); I != E; ++I) { - const Formula &F = *I; + for (const Formula &F : LU.Formulae) { if (F.BaseOffset == 0 || (F.Scale != 0 && F.Scale != 1)) continue; @@ -4135,9 +4074,7 @@ void LSRInstance::NarrowSearchSpaceByCollapsingUnrolledCode() { LUThatHas->AllFixupsOutsideLoop &= LU.AllFixupsOutsideLoop; // Update the relocs to reference the new use. - for (SmallVectorImpl<LSRFixup>::iterator I = Fixups.begin(), - E = Fixups.end(); I != E; ++I) { - LSRFixup &Fixup = *I; + for (LSRFixup &Fixup : Fixups) { if (Fixup.LUIdx == LUIdx) { Fixup.LUIdx = LUThatHas - &Uses.front(); Fixup.Offset += F.BaseOffset; @@ -4218,9 +4155,7 @@ void LSRInstance::NarrowSearchSpaceByPickingWinnerRegs() { // to be a good reuse register candidate. const SCEV *Best = nullptr; unsigned BestNum = 0; - for (RegUseTracker::const_iterator I = RegUses.begin(), E = RegUses.end(); - I != E; ++I) { - const SCEV *Reg = *I; + for (const SCEV *Reg : RegUses) { if (Taken.count(Reg)) continue; if (!Best) @@ -4308,17 +4243,12 @@ void LSRInstance::SolveRecurse(SmallVectorImpl<const Formula *> &Solution, SmallPtrSet<const SCEV *, 16> NewRegs; Cost NewCost; - for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(), - E = LU.Formulae.end(); I != E; ++I) { - const Formula &F = *I; - + for (const Formula &F : LU.Formulae) { // Ignore formulae which may not be ideal in terms of register reuse of // ReqRegs. The formula should use all required registers before // introducing new ones. int NumReqRegsToFind = std::min(F.getNumRegs(), ReqRegs.size()); - for (SmallSetVector<const SCEV *, 4>::const_iterator J = ReqRegs.begin(), - JE = ReqRegs.end(); J != JE; ++J) { - const SCEV *Reg = *J; + for (const SCEV *Reg : ReqRegs) { if ((F.ScaledReg && F.ScaledReg == Reg) || std::find(F.BaseRegs.begin(), F.BaseRegs.end(), Reg) != F.BaseRegs.end()) { @@ -4426,9 +4356,7 @@ LSRInstance::HoistInsertPosition(BasicBlock::iterator IP, bool AllDominate = true; Instruction *BetterPos = nullptr; Instruction *Tentative = IDom->getTerminator(); - for (SmallVectorImpl<Instruction *>::const_iterator I = Inputs.begin(), - E = Inputs.end(); I != E; ++I) { - Instruction *Inst = *I; + for (Instruction *Inst : Inputs) { if (Inst == Tentative || !DT.dominates(Inst, Tentative)) { AllDominate = false; break; @@ -4475,9 +4403,7 @@ LSRInstance::AdjustInsertPositionForExpand(BasicBlock::iterator LowestIP, } // The expansion must also be dominated by the increment positions of any // loops it for which it is using post-inc mode. - for (PostIncLoopSet::const_iterator I = LF.PostIncLoops.begin(), - E = LF.PostIncLoops.end(); I != E; ++I) { - const Loop *PIL = *I; + for (const Loop *PIL : LF.PostIncLoops) { if (PIL == L) continue; // Be dominated by the loop exit. @@ -4552,9 +4478,7 @@ Value *LSRInstance::Expand(const LSRFixup &LF, SmallVector<const SCEV *, 8> Ops; // Expand the BaseRegs portion. - for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(), - E = F.BaseRegs.end(); I != E; ++I) { - const SCEV *Reg = *I; + for (const SCEV *Reg : F.BaseRegs) { assert(!Reg->isZero() && "Zero allocated in a base register!"); // If we're expanding for a post-inc user, make the post-inc adjustment. @@ -4670,7 +4594,7 @@ Value *LSRInstance::Expand(const LSRFixup &LF, // form, update the ICmp's other operand. if (LU.Kind == LSRUse::ICmpZero) { ICmpInst *CI = cast<ICmpInst>(LF.UserInst); - DeadInsts.push_back(CI->getOperand(1)); + DeadInsts.emplace_back(CI->getOperand(1)); assert(!F.BaseGV && "ICmp does not support folding a global value and " "a scale at the same time!"); if (F.Scale == -1) { @@ -4728,12 +4652,14 @@ void LSRInstance::RewriteForPHI(PHINode *PN, // Split the critical edge. BasicBlock *NewBB = nullptr; if (!Parent->isLandingPad()) { - NewBB = SplitCriticalEdge(BB, Parent, P, - /*MergeIdenticalEdges=*/true, - /*DontDeleteUselessPhis=*/true); + NewBB = SplitCriticalEdge(BB, Parent, + CriticalEdgeSplittingOptions(&DT, &LI) + .setMergeIdenticalEdges() + .setDontDeleteUselessPHIs()); } else { SmallVector<BasicBlock*, 2> NewBBs; - SplitLandingPadPredecessors(Parent, BB, "", "", P, NewBBs); + SplitLandingPadPredecessors(Parent, BB, "", "", NewBBs, + /*AliasAnalysis*/ nullptr, &DT, &LI); NewBB = NewBBs[0]; } // If NewBB==NULL, then SplitCriticalEdge refused to split because all @@ -4811,7 +4737,7 @@ void LSRInstance::Rewrite(const LSRFixup &LF, LF.UserInst->replaceUsesOfWith(LF.OperandValToReplace, FullV); } - DeadInsts.push_back(LF.OperandValToReplace); + DeadInsts.emplace_back(LF.OperandValToReplace); } /// ImplementSolution - Rewrite all the fixup locations with new values, @@ -4823,7 +4749,8 @@ LSRInstance::ImplementSolution(const SmallVectorImpl<const Formula *> &Solution, // we can remove them after we are done working. SmallVector<WeakVH, 16> DeadInsts; - SCEVExpander Rewriter(SE, "lsr"); + SCEVExpander Rewriter(SE, L->getHeader()->getModule()->getDataLayout(), + "lsr"); #ifndef NDEBUG Rewriter.setDebugType(DEBUG_TYPE); #endif @@ -4832,25 +4759,20 @@ LSRInstance::ImplementSolution(const SmallVectorImpl<const Formula *> &Solution, Rewriter.setIVIncInsertPos(L, IVIncInsertPos); // Mark phi nodes that terminate chains so the expander tries to reuse them. - for (SmallVectorImpl<IVChain>::const_iterator ChainI = IVChainVec.begin(), - ChainE = IVChainVec.end(); ChainI != ChainE; ++ChainI) { - if (PHINode *PN = dyn_cast<PHINode>(ChainI->tailUserInst())) + for (const IVChain &Chain : IVChainVec) { + if (PHINode *PN = dyn_cast<PHINode>(Chain.tailUserInst())) Rewriter.setChainedPhi(PN); } // Expand the new value definitions and update the users. - for (SmallVectorImpl<LSRFixup>::const_iterator I = Fixups.begin(), - E = Fixups.end(); I != E; ++I) { - const LSRFixup &Fixup = *I; - + for (const LSRFixup &Fixup : Fixups) { Rewrite(Fixup, *Solution[Fixup.LUIdx], Rewriter, DeadInsts, P); Changed = true; } - for (SmallVectorImpl<IVChain>::const_iterator ChainI = IVChainVec.begin(), - ChainE = IVChainVec.end(); ChainI != ChainE; ++ChainI) { - GenerateIVChain(*ChainI, Rewriter, DeadInsts); + for (const IVChain &Chain : IVChainVec) { + GenerateIVChain(Chain, Rewriter, DeadInsts); Changed = true; } // Clean up after ourselves. This must be done before deleting any @@ -4863,9 +4785,10 @@ LSRInstance::ImplementSolution(const SmallVectorImpl<const Formula *> &Solution, LSRInstance::LSRInstance(Loop *L, Pass *P) : IU(P->getAnalysis<IVUsers>()), SE(P->getAnalysis<ScalarEvolution>()), DT(P->getAnalysis<DominatorTreeWrapperPass>().getDomTree()), - LI(P->getAnalysis<LoopInfo>()), - TTI(P->getAnalysis<TargetTransformInfo>()), L(L), Changed(false), - IVIncInsertPos(nullptr) { + LI(P->getAnalysis<LoopInfoWrapperPass>().getLoopInfo()), + TTI(P->getAnalysis<TargetTransformInfoWrapperPass>().getTTI( + *L->getHeader()->getParent())), + L(L), Changed(false), IVIncInsertPos(nullptr) { // If LoopSimplify form is not available, stay out of trouble. if (!L->isLoopSimplifyForm()) return; @@ -4876,10 +4799,10 @@ LSRInstance::LSRInstance(Loop *L, Pass *P) // If there's too much analysis to be done, bail early. We won't be able to // model the problem anyway. unsigned NumUsers = 0; - for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) { + for (const IVStrideUse &U : IU) { if (++NumUsers > MaxIVUsers) { - DEBUG(dbgs() << "LSR skipping loop, too many IV Users in " << *L - << "\n"); + (void)U; + DEBUG(dbgs() << "LSR skipping loop, too many IV Users in " << U << "\n"); return; } } @@ -4948,14 +4871,10 @@ LSRInstance::LSRInstance(Loop *L, Pass *P) #ifndef NDEBUG // Formulae should be legal. - for (SmallVectorImpl<LSRUse>::const_iterator I = Uses.begin(), E = Uses.end(); - I != E; ++I) { - const LSRUse &LU = *I; - for (SmallVectorImpl<Formula>::const_iterator J = LU.Formulae.begin(), - JE = LU.Formulae.end(); - J != JE; ++J) + for (const LSRUse &LU : Uses) { + for (const Formula &F : LU.Formulae) assert(isLegalUse(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy, - *J) && "Illegal formula generated!"); + F) && "Illegal formula generated!"); }; #endif @@ -4969,44 +4888,38 @@ void LSRInstance::print_factors_and_types(raw_ostream &OS) const { OS << "LSR has identified the following interesting factors and types: "; bool First = true; - for (SmallSetVector<int64_t, 8>::const_iterator - I = Factors.begin(), E = Factors.end(); I != E; ++I) { + for (int64_t Factor : Factors) { if (!First) OS << ", "; First = false; - OS << '*' << *I; + OS << '*' << Factor; } - for (SmallSetVector<Type *, 4>::const_iterator - I = Types.begin(), E = Types.end(); I != E; ++I) { + for (Type *Ty : Types) { if (!First) OS << ", "; First = false; - OS << '(' << **I << ')'; + OS << '(' << *Ty << ')'; } OS << '\n'; } void LSRInstance::print_fixups(raw_ostream &OS) const { OS << "LSR is examining the following fixup sites:\n"; - for (SmallVectorImpl<LSRFixup>::const_iterator I = Fixups.begin(), - E = Fixups.end(); I != E; ++I) { + for (const LSRFixup &LF : Fixups) { dbgs() << " "; - I->print(OS); + LF.print(OS); OS << '\n'; } } void LSRInstance::print_uses(raw_ostream &OS) const { OS << "LSR is examining the following uses:\n"; - for (SmallVectorImpl<LSRUse>::const_iterator I = Uses.begin(), - E = Uses.end(); I != E; ++I) { - const LSRUse &LU = *I; + for (const LSRUse &LU : Uses) { dbgs() << " "; LU.print(OS); OS << '\n'; - for (SmallVectorImpl<Formula>::const_iterator J = LU.Formulae.begin(), - JE = LU.Formulae.end(); J != JE; ++J) { + for (const Formula &F : LU.Formulae) { OS << " "; - J->print(OS); + F.print(OS); OS << '\n'; } } @@ -5041,11 +4954,11 @@ private: char LoopStrengthReduce::ID = 0; INITIALIZE_PASS_BEGIN(LoopStrengthReduce, "loop-reduce", "Loop Strength Reduction", false, false) -INITIALIZE_AG_DEPENDENCY(TargetTransformInfo) +INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) INITIALIZE_PASS_DEPENDENCY(IVUsers) -INITIALIZE_PASS_DEPENDENCY(LoopInfo) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) INITIALIZE_PASS_END(LoopStrengthReduce, "loop-reduce", "Loop Strength Reduction", false, false) @@ -5064,8 +4977,8 @@ void LoopStrengthReduce::getAnalysisUsage(AnalysisUsage &AU) const { // many analyses if they are around. AU.addPreservedID(LoopSimplifyID); - AU.addRequired<LoopInfo>(); - AU.addPreserved<LoopInfo>(); + AU.addRequired<LoopInfoWrapperPass>(); + AU.addPreserved<LoopInfoWrapperPass>(); AU.addRequiredID(LoopSimplifyID); AU.addRequired<DominatorTreeWrapperPass>(); AU.addPreserved<DominatorTreeWrapperPass>(); @@ -5076,7 +4989,7 @@ void LoopStrengthReduce::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequiredID(LoopSimplifyID); AU.addRequired<IVUsers>(); AU.addPreserved<IVUsers>(); - AU.addRequired<TargetTransformInfo>(); + AU.addRequired<TargetTransformInfoWrapperPass>(); } bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager & /*LPM*/) { @@ -5092,13 +5005,15 @@ bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager & /*LPM*/) { Changed |= DeleteDeadPHIs(L->getHeader()); if (EnablePhiElim && L->isLoopSimplifyForm()) { SmallVector<WeakVH, 16> DeadInsts; - SCEVExpander Rewriter(getAnalysis<ScalarEvolution>(), "lsr"); + const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); + SCEVExpander Rewriter(getAnalysis<ScalarEvolution>(), DL, "lsr"); #ifndef NDEBUG Rewriter.setDebugType(DEBUG_TYPE); #endif unsigned numFolded = Rewriter.replaceCongruentIVs( L, &getAnalysis<DominatorTreeWrapperPass>().getDomTree(), DeadInsts, - &getAnalysis<TargetTransformInfo>()); + &getAnalysis<TargetTransformInfoWrapperPass>().getTTI( + *L->getHeader()->getParent())); if (numFolded) { Changed = true; DeleteTriviallyDeadInstructions(DeadInsts); |
