[TTI] Unify FavorPostInc and FavorBackedgeIndex into getAddressingMode

[SjoerdMeijer]

Summary

This refactors shouldFavorPostInc() and shouldFavorBackedgeIndex() into getAddressingMode() so that we have one interface to steer LSR in generating the preferred addressing mode.

[samparker]

Shouldn't this be an NFC..? Looks like we should be favouring post-incs for MVE, even at optsize.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

1263

else if

[SjoerdMeijer]

Yeah, it should be NFC, but there's some interaction with OptSize that makes this behave slightly different.
Now returning PostIndexed for OptSize, which shows some codegen differences, but they seem to be the right changes.

[samparker]

But why not just order the logic so that it is an NFC?

[SjoerdMeijer]

Now NFC.

[dmgreen]

llvm/include/llvm/Analysis/TargetTransformInfo.h

648

I feel like the name is too general, and should be most specific to this favoring one mode or the other in LSR. Maybe just adding Preferred or Favor to it would be enough.

llvm/lib/Target/ARM/ARMTargetTransformInfo.cpp

108

Is this not still different for optsize?

108–116

I don't think this should be needed?

110

Doesn't need the else after a return.

[SjoerdMeijer]

Thanks, renamed it to getPreferredAddressingMode and simplified the logic in the ARM implementation.

[dmgreen]

LGTM, unless Sam has any other comments.

llvm/lib/Target/ARM/ARMTargetTransformInfo.cpp

112

This needn't check hasMVEIntegerOps, if it's returning PostIndexed above.

[samparker]

Nothing else from me.

[SjoerdMeijer]

Thanks guys, I have added ScalarEvolution *SE to the interface to make it a bit more general (so implementation can e.g. query getInductionVariable)

[dmgreen]

That sounds OK. Like I said if you want to do any amount of processing in getPreferredAddressingMode then it probably needs to be caching the result. Cost::RateRegister is called a lot of times for some loops.

[SjoerdMeijer]

Thanks Dave, I will keep that in mind and will look into it when I'll get to it. My first thought would not to call it inside RateRegister, that seems unnecessary, so yes, either that or some caching.

llvm/include/llvm/Analysis/TargetTransformInfo.h

public:
   bool canMacroFuseCmp() const;
 
   /// Return true if the target can save a compare for loop count, for example
   /// hardware loop saves a compare.
   bool canSaveCmp(Loop *L, BranchInst **BI, ScalarEvolution *SE, LoopInfo *LI,
                   DominatorTree *DT, AssumptionCache *AC,
                   TargetLibraryInfo *LibInfo) const;
 
-  /// \return True is LSR should make efforts to create/preserve post-inc
-  /// addressing mode expressions.
-  bool shouldFavorPostInc() const;
-
-  /// Return true if LSR should make efforts to generate indexed addressing
-  /// modes that operate across loop iterations.
-  bool shouldFavorBackedgeIndex(const Loop *L) const;
+  enum AddressingModeKind {
+    AMK_PreIndexed,
+    AMK_PostIndexed,
+    AMK_None
+  };
+
+  /// Return the preferred addressing mode LSR should make efforts to generate.
+  AddressingModeKind getPreferredAddressingMode(const Loop *L,
+                                                ScalarEvolution *SE) const;
 
   /// Return true if the target supports masked store.
   bool isLegalMaskedStore(Type *DataType, Align Alignment) const;
   /// Return true if the target supports masked load.
   bool isLegalMaskedLoad(Type *DataType, Align Alignment) const;
 
   /// Return true if the target supports nontemporal store.
   bool isLegalNTStore(Type *DataType, Align Alignment) const;
public:
   virtual bool isLSRCostLess(TargetTransformInfo::LSRCost &C1,
                              TargetTransformInfo::LSRCost &C2) = 0;
   virtual bool isNumRegsMajorCostOfLSR() = 0;
   virtual bool isProfitableLSRChainElement(Instruction *I) = 0;
   virtual bool canMacroFuseCmp() = 0;
   virtual bool canSaveCmp(Loop *L, BranchInst **BI, ScalarEvolution *SE,
                           LoopInfo *LI, DominatorTree *DT, AssumptionCache *AC,
                           TargetLibraryInfo *LibInfo) = 0;
-  virtual bool shouldFavorPostInc() const = 0;
-  virtual bool shouldFavorBackedgeIndex(const Loop *L) const = 0;
+  virtual AddressingModeKind
+    getPreferredAddressingMode(const Loop *L, ScalarEvolution *SE) const = 0;
   virtual bool isLegalMaskedStore(Type *DataType, Align Alignment) = 0;
   virtual bool isLegalMaskedLoad(Type *DataType, Align Alignment) = 0;
   virtual bool isLegalNTStore(Type *DataType, Align Alignment) = 0;
   virtual bool isLegalNTLoad(Type *DataType, Align Alignment) = 0;
   virtual bool isLegalMaskedScatter(Type *DataType, Align Alignment) = 0;
   virtual bool isLegalMaskedGather(Type *DataType, Align Alignment) = 0;
   virtual bool isLegalMaskedCompressStore(Type *DataType) = 0;
   virtual bool isLegalMaskedExpandLoad(Type *DataType) = 0;
bool isProfitableLSRChainElement(Instruction *I) override {
     return Impl.isProfitableLSRChainElement(I);
   }
   bool canMacroFuseCmp() override { return Impl.canMacroFuseCmp(); }
   bool canSaveCmp(Loop *L, BranchInst **BI, ScalarEvolution *SE, LoopInfo *LI,
                   DominatorTree *DT, AssumptionCache *AC,
                   TargetLibraryInfo *LibInfo) override {
     return Impl.canSaveCmp(L, BI, SE, LI, DT, AC, LibInfo);
   }
-  bool shouldFavorPostInc() const override { return Impl.shouldFavorPostInc(); }
-  bool shouldFavorBackedgeIndex(const Loop *L) const override {
-    return Impl.shouldFavorBackedgeIndex(L);
+  AddressingModeKind
+    getPreferredAddressingMode(const Loop *L,
+                               ScalarEvolution *SE) const override {
+    return Impl.getPreferredAddressingMode(L, SE);
   }
   bool isLegalMaskedStore(Type *DataType, Align Alignment) override {
     return Impl.isLegalMaskedStore(DataType, Alignment);
   }
   bool isLegalMaskedLoad(Type *DataType, Align Alignment) override {
     return Impl.isLegalMaskedLoad(DataType, Alignment);
   }
   bool isLegalNTStore(Type *DataType, Align Alignment) override {

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

public:
   bool canMacroFuseCmp() const { return false; }
 
   bool canSaveCmp(Loop *L, BranchInst **BI, ScalarEvolution *SE, LoopInfo *LI,
                   DominatorTree *DT, AssumptionCache *AC,
                   TargetLibraryInfo *LibInfo) const {
     return false;
   }
 
-  bool shouldFavorPostInc() const { return false; }
-
-  bool shouldFavorBackedgeIndex(const Loop *L) const { return false; }
+  TTI::AddressingModeKind
+    getPreferredAddressingMode(const Loop *L, ScalarEvolution *SE) const {
+    return TTI::AMK_None;
+  }
 
   bool isLegalMaskedStore(Type *DataType, Align Alignment) const {
     return false;
   }
 
   bool isLegalMaskedLoad(Type *DataType, Align Alignment) const {
     return false;
   }

llvm/lib/Analysis/TargetTransformInfo.cpp

 
 bool TargetTransformInfo::canSaveCmp(Loop *L, BranchInst **BI,
                                      ScalarEvolution *SE, LoopInfo *LI,
                                      DominatorTree *DT, AssumptionCache *AC,
                                      TargetLibraryInfo *LibInfo) const {
   return TTIImpl->canSaveCmp(L, BI, SE, LI, DT, AC, LibInfo);
 }
 
-bool TargetTransformInfo::shouldFavorPostInc() const {
-  return TTIImpl->shouldFavorPostInc();
-}
-
-bool TargetTransformInfo::shouldFavorBackedgeIndex(const Loop *L) const {
-  return TTIImpl->shouldFavorBackedgeIndex(L);
+TTI::AddressingModeKind
+TargetTransformInfo::getPreferredAddressingMode(const Loop *L,
+                                                ScalarEvolution *SE) const {
+  return TTIImpl->getPreferredAddressingMode(L, SE);
 }
 
 bool TargetTransformInfo::isLegalMaskedStore(Type *DataType,
                                              Align Alignment) const {
   return TTIImpl->isLegalMaskedStore(DataType, Alignment);
 }
 
 bool TargetTransformInfo::isLegalMaskedLoad(Type *DataType,

llvm/lib/Target/ARM/ARMTargetTransformInfo.h

explicit ARMTTIImpl(const ARMBaseTargetMachine *TM, const Function &F)
       : BaseT(TM, F.getParent()->getDataLayout()), ST(TM->getSubtargetImpl(F)),
         TLI(ST->getTargetLowering()) {}
 
   bool areInlineCompatible(const Function *Caller,
                            const Function *Callee) const;
 
   bool enableInterleavedAccessVectorization() { return true; }
 
-  bool shouldFavorBackedgeIndex(const Loop *L) const;
-  bool shouldFavorPostInc() const;
+  TTI::AddressingModeKind
+    getPreferredAddressingMode(const Loop *L, ScalarEvolution *SE) const;
 
   /// Floating-point computation using ARMv8 AArch32 Advanced
   /// SIMD instructions remains unchanged from ARMv7. Only AArch64 SIMD
   /// and Arm MVE are IEEE-754 compliant.
   bool isFPVectorizationPotentiallyUnsafe() {
     return !ST->isTargetDarwin() && !ST->hasMVEFloatOps();
   }
 

llvm/lib/Target/ARM/ARMTargetTransformInfo.cpp

bool MatchExact = (CallerBits & ~InlineFeaturesAllowed) ==
                     (CalleeBits & ~InlineFeaturesAllowed);
   // For features in the allowed list, the callee's features must be a subset of
   // the callers'.
   bool MatchSubset = ((CallerBits & CalleeBits) & InlineFeaturesAllowed) ==
                      (CalleeBits & InlineFeaturesAllowed);
   return MatchExact && MatchSubset;
 }
 
-bool ARMTTIImpl::shouldFavorBackedgeIndex(const Loop *L) const {
-  if (L->getHeader()->getParent()->hasOptSize())
-    return false;
+TTI::AddressingModeKind
+ARMTTIImpl::getPreferredAddressingMode(const Loop *L,
+                                       ScalarEvolution *SE) const {
   if (ST->hasMVEIntegerOps())
-    return false;
-  return ST->isMClass() && ST->isThumb2() && L->getNumBlocks() == 1;
-}
+    return TTI::AMK_PostIndexed;
 
-bool ARMTTIImpl::shouldFavorPostInc() const {
-  if (ST->hasMVEIntegerOps())
-    return true;
-  return false;
+  if (L->getHeader()->getParent()->hasOptSize())
+    return TTI::AMK_None;
+
+  if (ST->isMClass() && ST->isThumb2() &&
+      L->getNumBlocks() == 1)
+    return TTI::AMK_PreIndexed;
+
+  return TTI::AMK_None;
 }
 
 Optional<Instruction *>
 ARMTTIImpl::instCombineIntrinsic(InstCombiner &IC, IntrinsicInst &II) const {
   using namespace PatternMatch;
   Intrinsic::ID IID = II.getIntrinsicID();
   switch (IID) {
   default:

llvm/lib/Target/Hexagon/HexagonTargetTransformInfo.h

public:
   // The Hexagon target can unroll loops with run-time trip counts.
   void getUnrollingPreferences(Loop *L, ScalarEvolution &SE,
                                TTI::UnrollingPreferences &UP);
 
   void getPeelingPreferences(Loop *L, ScalarEvolution &SE,
                              TTI::PeelingPreferences &PP);
 
   /// Bias LSR towards creating post-increment opportunities.
-  bool shouldFavorPostInc() const;
+  AddressingModeKind getPreferredAddressingMode(const Loop *L,
+                                                ScalarEvolution *SE) const;
 
   // L1 cache prefetch.
   unsigned getPrefetchDistance() const override;
   unsigned getCacheLineSize() const override;
 
   /// @}
 
   /// \name Vector TTI Implementations

llvm/lib/Target/Hexagon/HexagonTargetTransformInfo.cpp

void HexagonTTIImpl::getPeelingPreferences(Loop *L, ScalarEvolution &SE,
   if (L && L->isInnermost() && canPeel(L) &&
       SE.getSmallConstantTripCount(L) == 0 &&
       SE.getSmallConstantMaxTripCount(L) > 0 &&
       SE.getSmallConstantMaxTripCount(L) <= 5) {
     PP.PeelCount = 2;
   }
 }
 
-bool HexagonTTIImpl::shouldFavorPostInc() const {
-  return true;
+AddressingModeKind::getPreferredAddressingMode(const Loop *L,
+                                               ScalarEvolution *SE) const {
+  return AMK_PostIndexed;
 }
 
 /// --- Vector TTI begin ---
 
 unsigned HexagonTTIImpl::getNumberOfRegisters(bool Vector) const {
   if (Vector)
     return useHVX() ? 32 : 0;
   return 32;

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

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) && !TTI->shouldFavorPostInc())
+      if (isExistingPhi(AR, *SE) && AMK != TTI::AMK_PostIndexed)
         return;
 
       // It is bad to allow LSR for current loop to add induction variables
       // for its sibling loops.
       if (!AR->getLoop()->contains(L)) {
         Lose();
         return;
       }
 
       // Otherwise, it will be an invariant with respect to Loop L.
       ++C.NumRegs;
       return;
     }
 
     unsigned LoopCost = 1;
     if (TTI->isIndexedLoadLegal(TTI->MIM_PostInc, AR->getType()) ||
         TTI->isIndexedStoreLegal(TTI->MIM_PostInc, AR->getType())) {
 
       // If the step size matches the base offset, we could use pre-indexed
       // addressing.
-      if (TTI->shouldFavorBackedgeIndex(L)) {
+      if (AMK == TTI::AMK_PreIndexed) {
         if (auto *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE)))
           if (Step->getAPInt() == F.BaseOffset)
             LoopCost = 0;
-      }
-
-      if (TTI->shouldFavorPostInc()) {
+      } else if (AMK == TTI::AMK_PostIndexed) {
         const SCEV *LoopStep = AR->getStepRecurrence(*SE);
         if (isa<SCEVConstant>(LoopStep)) {
           const SCEV *LoopStart = AR->getStart();
           if (!isa<SCEVConstant>(LoopStart) &&
               SE->isLoopInvariant(LoopStart, L))
             LoopCost = 0;
         }
       }
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.
-  if (TTI.shouldFavorPostInc() && mayUsePostIncMode(TTI, LU, BaseReg, L, SE))
+  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)
     return;
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.shouldFavorPostInc() &&
+            if (TTI.getPreferredAddressingMode(this->L, &SE) ==
+                    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);
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.shouldFavorPostInc())
+  if (TTI.getPreferredAddressingMode(L, &SE) != 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,
   Cost NewCost(L, SE, TTI);
   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.shouldFavorPostInc() || LU.Kind != LSRUse::Address) {
+    if (TTI.getPreferredAddressingMode(L, &SE) != 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;
         }

 }
 
 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.shouldFavorBackedgeIndex(L)) {
+                                       TTI.getPreferredAddressingMode(L, &SE) ==
+                                           TTI::AMK_PreIndexed) {
   // 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