[LSR] Cleanup of getPreferredAddresingMode. NFC.

[SjoerdMeijer]

Summary

This is a follow up D96600 and cleans up all calls to getPreferredAddresingMode. i.e., we really don't need to query the same things again and again, but get the preferred addressing mode once. So this should be a lot friendlier for compile times, especially if we start implementing getPreferredAddresingMode.

[dmgreen]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5565

Should the EnableBackedgeIndexing option override what the target defines? Or could it be removed, or replaced?

[SjoerdMeijer]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3810

Should the EnableBackedgeIndexing option override what the target defines? Or could it be removed, or replaced?

Good point. I think in general an option takes precedence, but that's not really happening here.

I think haIving an option for this would be good (I noticed it would at least be convenient for testing), which accepts values that match the values this hook returns: preindexed, postindexed, and none. I was thinking of doing that as a follow up of this NFC, so that would mean generalising and renaming this EnableBackedgeIndexing if that sounds like a good idea (so leave this as a NFC).

[samparker]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3810

I was also going to suggest, in the previous patch, to just remove the option. I just added it for testing and I don't think it's useful now.

[fhahn]

LGTM, the target's preferred addressing mode should be independent of the contents of the loop, which may change between the different calls in the original code.

Please resolve @dmgreen's comment before landing. For me, adjusting EnableBackedgeIndexing handling would be fine as a follow up.

[SjoerdMeijer]

Thanks guys.

I will commit this to get this NFC out of the way, and then follow up shortly to make some changes to options as I also found that's convenient to have for testing.
I will rename EnableBackedgeIndexing to PreferredAddressingMode, and let it accept the 3 values corresponding to the enum values of AddressingModeKind.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

 
 // Flag to narrow search space by filtering non-optimal formulae with
 // the same ScaledReg and Scale.
 static cl::opt<bool> FilterSameScaledReg(
     "lsr-filter-same-scaled-reg", cl::Hidden, cl::init(true),
     cl::desc("Narrow LSR search space by filtering non-optimal formulae"
              " with the same ScaledReg and Scale"));
 
-static cl::opt<bool> EnableBackedgeIndexing(
-  "lsr-backedge-indexing", cl::Hidden, cl::init(true),
-  cl::desc("Enable the generation of cross iteration indexed memops"));
-
 static cl::opt<unsigned> ComplexityLimit(
   "lsr-complexity-limit", cl::Hidden,
   cl::init(std::numeric_limits<uint16_t>::max()),
   cl::desc("LSR search space complexity limit"));
 
 static cl::opt<unsigned> SetupCostDepthLimit(
     "lsr-setupcost-depth-limit", cl::Hidden, cl::init(7),
     cl::desc("The limit on recursion depth for LSRs setup cost"));

 namespace {
 
 /// This class is used to measure and compare candidate formulae.
 class Cost {
   const Loop *L = nullptr;
   ScalarEvolution *SE = nullptr;
   const TargetTransformInfo *TTI = nullptr;
   TargetTransformInfo::LSRCost C;
+  TTI::AddressingModeKind AMK = TTI::AMK_None;
 
 public:
   Cost() = delete;
-  Cost(const Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI) :
-    L(L), SE(&SE), TTI(&TTI) {
+  Cost(const Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI,
+       TTI::AddressingModeKind AMK) :
+    L(L), SE(&SE), TTI(&TTI), AMK(AMK) {
     C.Insns = 0;
     C.NumRegs = 0;
     C.AddRecCost = 0;
     C.NumIVMuls = 0;
     C.NumBaseAdds = 0;
     C.ImmCost = 0;
     C.SetupCost = 0;
     C.ScaleCost = 0;
if (auto S = dyn_cast<SCEVUDivExpr>(Reg))
     return getSetupCost(S->getLHS(), Depth - 1) +
            getSetupCost(S->getRHS(), Depth - 1);
   return 0;
 }
 
 /// Tally up interesting quantities from the given register.
 void Cost::RateRegister(const Formula &F, const SCEV *Reg,
                         SmallPtrSetImpl<const SCEV *> &Regs) {
-  TTI::AddressingModeKind AMK = TTI->getPreferredAddressingMode(L, SE);
-
   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Reg)) {
     // If this is an addrec for another loop, it should be an invariant
     // with respect to L since L is the innermost loop (at least
     // for now LSR only handles innermost loops).
     if (AR->getLoop() != L) {
       // If the AddRec exists, consider it's register free and leave it alone.
       if (isExistingPhi(AR, *SE) && AMK != TTI::AMK_PostIndexed)
         return;
class LSRInstance {
   ScalarEvolution &SE;
   DominatorTree &DT;
   LoopInfo &LI;
   AssumptionCache &AC;
   TargetLibraryInfo &TLI;
   const TargetTransformInfo &TTI;
   Loop *const L;
   MemorySSAUpdater *MSSAU;
-  bool FavorBackedgeIndex = false;
+  TTI::AddressingModeKind AMK;
   bool Changed = false;
 
   /// This is the insert position that the current loop's induction variable
   /// increment should be placed. In simple loops, this is the latch block's
   /// terminator. But in more complicated cases, this is a position which will
   /// dominate all the in-loop post-increment users.
   Instruction *IVIncInsertPos = nullptr;
 
void LSRInstance::GenerateReassociationsImpl(LSRUse &LU, unsigned LUIdx,
                                              const Formula &Base,
                                              unsigned Depth, size_t Idx,
                                              bool IsScaledReg) {
   const SCEV *BaseReg = IsScaledReg ? Base.ScaledReg : Base.BaseRegs[Idx];
   // Don't generate reassociations for the base register of a value that
   // may generate a post-increment operator. The reason is that the
   // reassociations cause extra base+register formula to be created,
   // and possibly chosen, but the post-increment is more efficient.
-  TTI::AddressingModeKind AMK = TTI.getPreferredAddressingMode(L, &SE);
   if (AMK == TTI::AMK_PostIndexed && mayUsePostIncMode(TTI, LU, BaseReg, L, SE))
     return;
   SmallVector<const SCEV *, 8> AddOps;
   const SCEV *Remainder = CollectSubexprs(BaseReg, nullptr, AddOps, L, SE);
   if (Remainder)
     AddOps.push_back(Remainder);
 
   if (AddOps.size() == 1)
void LSRInstance::GenerateConstantOffsetsImpl(
   // With constant offsets and constant steps, we can generate pre-inc
   // accesses by having the offset equal the step. So, for access #0 with a
   // step of 8, we generate a G - 8 base which would require the first access
   // to be ((G - 8) + 8),+,8. The pre-indexed access then updates the pointer
   // for itself and hopefully becomes the base for other accesses. This means
   // means that a single pre-indexed access can be generated to become the new
   // base pointer for each iteration of the loop, resulting in no extra add/sub
   // instructions for pointer updating.
-  if (FavorBackedgeIndex && LU.Kind == LSRUse::Address) {
+  if (AMK == TTI::AMK_PreIndexed && LU.Kind == LSRUse::Address) {
     if (auto *GAR = dyn_cast<SCEVAddRecExpr>(G)) {
       if (auto *StepRec =
           dyn_cast<SCEVConstant>(GAR->getStepRecurrence(SE))) {
         const APInt &StepInt = StepRec->getAPInt();
         int64_t Step = StepInt.isNegative() ?
           StepInt.getSExtValue() : StepInt.getZExtValue();
 
         for (int64_t Offset : Worklist) {
           Offset -= Step;
for (size_t L = 0, LE = LU.Formulae.size(); L != LE; ++L) {
         for (size_t N = 0, NE = F.BaseRegs.size(); N != NE; ++N) {
           const SCEV *BaseReg = F.BaseRegs[N];
           if (BaseReg != OrigReg)
             continue;
           Formula NewF = F;
           NewF.BaseOffset = (uint64_t)NewF.BaseOffset + Imm;
           if (!isLegalUse(TTI, LU.MinOffset, LU.MaxOffset,
                           LU.Kind, LU.AccessTy, NewF)) {
-            if (TTI.getPreferredAddressingMode(this->L, &SE) ==
-                    TTI::AMK_PostIndexed &&
+            if (AMK == TTI::AMK_PostIndexed &&
                 mayUsePostIncMode(TTI, LU, OrigReg, this->L, SE))
               continue;
             if (!TTI.isLegalAddImmediate((uint64_t)NewF.UnfoldedOffset + Imm))
               continue;
             NewF = F;
             NewF.UnfoldedOffset = (uint64_t)NewF.UnfoldedOffset + Imm;
           }
           NewF.BaseRegs[N] = SE.getAddExpr(NegImmS, BaseReg);
for (size_t FIdx = 0, NumForms = LU.Formulae.size();
 
       // Some formulas are instant losers. For example, they may depend on
       // nonexistent AddRecs from other loops. These need to be filtered
       // immediately, otherwise heuristics could choose them over others leading
       // to an unsatisfactory solution. Passing LoserRegs into RateFormula here
       // avoids the need to recompute this information across formulae using the
       // same bad AddRec. Passing LoserRegs is also essential unless we remove
       // the corresponding bad register from the Regs set.
-      Cost CostF(L, SE, TTI);
+      Cost CostF(L, SE, TTI, AMK);
       Regs.clear();
       CostF.RateFormula(F, Regs, VisitedRegs, LU, &LoserRegs);
       if (CostF.isLoser()) {
         // During initial formula generation, undesirable formulae are generated
         // by uses within other loops that have some non-trivial address mode or
         // use the postinc form of the IV. LSR needs to provide these formulae
         // as the basis of rediscovering the desired formula that uses an AddRec
         // corresponding to the existing phi. Once all formulae have been
for (size_t FIdx = 0, NumForms = LU.Formulae.size();
 
         std::pair<BestFormulaeTy::const_iterator, bool> P =
           BestFormulae.insert(std::make_pair(Key, FIdx));
         if (P.second)
           continue;
 
         Formula &Best = LU.Formulae[P.first->second];
 
-        Cost CostBest(L, SE, TTI);
+        Cost CostBest(L, SE, TTI, AMK);
         Regs.clear();
         CostBest.RateFormula(Best, Regs, VisitedRegs, LU);
         if (CostF.isLess(CostBest))
           std::swap(F, Best);
         LLVM_DEBUG(dbgs() << "  Filtering out formula "; F.print(dbgs());
                    dbgs() << "\n"
                              "    in favor of formula ";
                    Best.print(dbgs()); dbgs() << '\n');
auto IsBetterThan = [&](Formula &FA, Formula &FB) {
         const SmallBitVector &UsedByIndices = RegUses.getUsedByIndices(Reg);
         FBRegNum += (NumUses - UsedByIndices.count() + 1);
       }
       if (FARegNum != FBRegNum)
         return FARegNum < FBRegNum;
 
       // If the new register numbers are the same, choose the Formula with
       // less Cost.
-      Cost CostFA(L, SE, TTI);
-      Cost CostFB(L, SE, TTI);
+      Cost CostFA(L, SE, TTI, AMK);
+      Cost CostFB(L, SE, TTI, AMK);
       Regs.clear();
       CostFA.RateFormula(FA, Regs, VisitedRegs, LU);
       Regs.clear();
       CostFB.RateFormula(FB, Regs, VisitedRegs, LU);
       return CostFA.isLess(CostFB);
     };
 
     bool Any = false;
dbgs() << "\n"
               "After filtering out undesirable candidates:\n";
     print_uses(dbgs());
   });
 }
 
 /// If we are over the complexity limit, filter out any post-inc prefering
 /// variables to only post-inc values.
 void LSRInstance::NarrowSearchSpaceByFilterPostInc() {
-  if (TTI.getPreferredAddressingMode(L, &SE) != TTI::AMK_PostIndexed)
+  if (AMK != TTI::AMK_PostIndexed)
     return;
   if (EstimateSearchSpaceComplexity() < ComplexityLimit)
     return;
 
   LLVM_DEBUG(dbgs() << "The search space is too complex.\n"
                        "Narrowing the search space by choosing the lowest "
                        "register Formula for PostInc Uses.\n");
 
void LSRInstance::SolveRecurse(SmallVectorImpl<const Formula *> &Solution,
   // reference that register in order to be considered. This prunes out
   // unprofitable searching.
   SmallSetVector<const SCEV *, 4> ReqRegs;
   for (const SCEV *S : CurRegs)
     if (LU.Regs.count(S))
       ReqRegs.insert(S);
 
   SmallPtrSet<const SCEV *, 16> NewRegs;
-  Cost NewCost(L, SE, TTI);
+  Cost NewCost(L, SE, TTI, AMK);
   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.
     // This can sometimes (notably when trying to favour postinc) lead to
     // sub-optimial decisions. There it is best left to the cost modelling to
     // get correct.
-    if (TTI.getPreferredAddressingMode(L, &SE) != TTI::AMK_PostIndexed ||
-        LU.Kind != LSRUse::Address) {
+    if (AMK != TTI::AMK_PostIndexed || LU.Kind != LSRUse::Address) {
       int NumReqRegsToFind = std::min(F.getNumRegs(), ReqRegs.size());
       for (const SCEV *Reg : ReqRegs) {
         if ((F.ScaledReg && F.ScaledReg == Reg) ||
             is_contained(F.BaseRegs, Reg)) {
           --NumReqRegsToFind;
           if (NumReqRegsToFind == 0)
             break;
         }
for (const Formula &F : LU.Formulae) {
     }
   }
 }
 
 /// Choose one formula from each use. Return the results in the given Solution
 /// vector.
 void LSRInstance::Solve(SmallVectorImpl<const Formula *> &Solution) const {
   SmallVector<const Formula *, 8> Workspace;
-  Cost SolutionCost(L, SE, TTI);
+  Cost SolutionCost(L, SE, TTI, AMK);
   SolutionCost.Lose();
-  Cost CurCost(L, SE, TTI);
+  Cost CurCost(L, SE, TTI, AMK);
   SmallPtrSet<const SCEV *, 16> CurRegs;
   DenseSet<const SCEV *> VisitedRegs;
   Workspace.reserve(Uses.size());
 
   // SolveRecurse does all the work.
   SolveRecurse(Solution, SolutionCost, Workspace, CurCost,
                CurRegs, VisitedRegs);
   if (Solution.empty()) {
Changed |= RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts,
                                                                   &TLI, MSSAU);
 }
 
 LSRInstance::LSRInstance(Loop *L, IVUsers &IU, ScalarEvolution &SE,
                          DominatorTree &DT, LoopInfo &LI,
                          const TargetTransformInfo &TTI, AssumptionCache &AC,
                          TargetLibraryInfo &TLI, MemorySSAUpdater *MSSAU)
     : IU(IU), SE(SE), DT(DT), LI(LI), AC(AC), TLI(TLI), TTI(TTI), L(L),
-      MSSAU(MSSAU), FavorBackedgeIndex(EnableBackedgeIndexing &&
-                                       TTI.getPreferredAddressingMode(L, &SE) ==
-                                           TTI::AMK_PreIndexed) {
+      MSSAU(MSSAU), AMK(TTI.getPreferredAddressingMode(L, &SE)) {
   // If LoopSimplify form is not available, stay out of trouble.
   if (!L->isLoopSimplifyForm())
     return;
 
   // If there's no interesting work to be done, bail early.
   if (IU.empty()) return;
 
   // If there's too much analysis to be done, bail early. We won't be able to