Moving isComplex decision to TTI

[magabari]

Summary

Currently isLikelyComplexAddressComputation tries to figure out if the given stride seems to be "complex" and need some extra cost for address computation handling.

This code seems to be target dependent which may not be the same for all targets.
Passed the decision whether the given stride is complex or not to the target by proposing a new interface method in the TTI interface.

Specifically at X86 targets we dont see any significant address computation cost in case if the access is strided.

[mkuper]

I have some comments on the patch, but on a higher level, I'm not sure this is the right way to do this.
The only place that'll call this new TTI hook will be isLikelyComplexAddressComputation(), and the only thing we do with the result of isLikelyComplexAddressComputation() is feed it into a different TTI hook - TTI.getAddressComputationCost().

Perhaps we can enhance getAddressComputationCost() instead of adding another hook?

include/llvm/Analysis/TargetTransformInfo.h

210 ↗

(On Diff #80582)

Extra space.

211 ↗

(On Diff #80582)

Maybe "Expensive" makes more sense than "Complex" here?

lib/Target/X86/X86TargetTransformInfo.cpp

1480 ↗

(On Diff #80582)

What do you mean by "we don't see any significant address computation cost"? Can you give an example?

lib/Transforms/Vectorize/LoopVectorize.cpp

6618 ↗

(On Diff #80582)

NULL -> nullptr
Also, this looks a bit dirty. Maybe use Optional<>?

[Ayal]

In D27518#616355, @mkuper wrote:

I have some comments on the patch, but on a higher level, I'm not sure this is the right way to do this.
The only place that'll call this new TTI hook will be isLikelyComplexAddressComputation(), and the only thing we do with the result of isLikelyComplexAddressComputation() is feed it into a different TTI hook - TTI.getAddressComputationCost().

Perhaps we can enhance getAddressComputationCost() instead of adding another hook?

Yes we can, by passing it the (possibly Optional<>) APStrideVal instead of the current boolean "IsComplexComputation", and folding the "how expensive are certain stride values" logic from isLikelyComplexAddressComputation() down to getAddressComputationCost(). In any case this logic should best be target dependent, right?

[mkuper]

In D27518#618646, @Ayal wrote:

In D27518#616355, @mkuper wrote:

I have some comments on the patch, but on a higher level, I'm not sure this is the right way to do this.
The only place that'll call this new TTI hook will be isLikelyComplexAddressComputation(), and the only thing we do with the result of isLikelyComplexAddressComputation() is feed it into a different TTI hook - TTI.getAddressComputationCost().

Perhaps we can enhance getAddressComputationCost() instead of adding another hook?

Yes we can, by passing it the (possibly Optional<>) APStrideVal instead of the current boolean "IsComplexComputation", and folding the "how expensive are certain stride values" logic from isLikelyComplexAddressComputation() down to getAddressComputationCost().

Yes, I think that would be a better design. (Disagreement is welcome. :-) )

In any case this logic should best be target dependent, right?

I think so - I'm not familiar with addressing modes of other targets, but I think it makes a lot of sense for the logic to be target dependent.

[magabari]

updating patch following to Michael comments.

[magabari]

clarified comment of X86TTI::isExpensiveAddressComputation

[delena]

include/llvm/Analysis/TargetTransformInfo.h

606 ↗

(On Diff #81214)

Why do you need a struct? "Value *" will contain everything.

Value *Stride;

if (Stride == nullptr) - no stride,
dyn_cast<ConstantInt>(Stride) - answers the question isConstant()

[mkuper]

include/llvm/Analysis/TargetTransformInfo.h

606 ↗

(On Diff #81214)

IIUC, we don't necessarily have a Value* in hand, this originates from a SCEV, right?

lib/Target/X86/X86TargetTransformInfo.cpp

1482 ↗

(On Diff #81214)

nor -> not

lib/Transforms/Vectorize/LoopVectorize.cpp

6782 ↗

(On Diff #81214)

Extra spaces after the line.
(On the line below too.)

6782 ↗

(On Diff #81214)

You don't seem to initialize the fields.

7046 ↗

(On Diff #81214)

Please elaborate about what you actually get, rather than just "some info"
(this is really "Figure out whether the access is strided and what the stride is..." or something like that).

[delena]

include/llvm/Analysis/TargetTransformInfo.h

606 ↗

(On Diff #81214)

yes. We can use const SCEV*.

[mkuper]

include/llvm/Analysis/TargetTransformInfo.h

606 ↗

(On Diff #81214)

I'm not sure passing a SCEV* to TTI makes sense, in terms of layering.

[hfinkel]

include/llvm/Analysis/TargetTransformInfo.h

606 ↗

(On Diff #81214)

I don't see why that should be a problem. The backends already depend on SCEV (and the rest of analysis) because of IR-level passes. TTI should definitely use SCEV where appropriate.

[mkuper]

include/llvm/Analysis/TargetTransformInfo.h

606 ↗

(On Diff #81214)

Never mind me, then. SCEV it is.

[magabari]

fixed some comments.
In my opinion we should still keep TTI as a lightweight interface which is not depended on SCEV.
So i think that passing struct which can hold all the properties still can be better approach. Even for future enhancements for that function.
please tell me what do you think.

include/llvm/Analysis/TargetTransformInfo.h

606 ↗

(On Diff #81214)

passing only Value* has some cons and doesn't solve the general problem.

1. it depends on SCEV
2. currently we differentiate between strided and not strided access, but i think that there is more than those 2 cases so i thought creating some struct will be better approach

lib/Transforms/Vectorize/LoopVectorize.cpp

6782 ↗

(On Diff #81214)

add initialize for isConstant field too. last field is undefined in case it's not constant stride

7046 ↗

(On Diff #81214)

fixed

[hfinkel]

In D27518#623377, @magabari wrote:

fixed some comments.
In my opinion we should still keep TTI as a lightweight interface which is not depended on SCEV.
So i think that passing struct which can hold all the properties still can be better approach. Even for future enhancements for that function.
please tell me what do you think.

If all of the information that the backend might reasonably need can be summarized in a structure, then I agree with you that using a structure is preferred. TTI is already not necessarily a "lightweight" interface (to compute unrolling preferences, for example, we just hand the backend the loop itself because there's no reasonable way that we can summarize what the backend might need).

[mkuper]

include/llvm/Analysis/TargetTransformInfo.h

606 ↗

(On Diff #81214)

I agree a Value* is not appropriate.
I can live with either a struct or SCEV.

include/llvm/CodeGen/BasicTTIImpl.h

921 ↗

(On Diff #81550)

Assuming this stays a struct - could you change all the "Info" variables and arguments to "AddressInfo" or something else that's meaningful?

lib/Target/X86/X86TargetTransformInfo.cpp

1483 ↗

(On Diff #81550)

Maybe it would be better to have the options "0, 1, 10" instead of "0, 10, where the 0 case can hide an add that we ignore"?
I'm saying "maybe" because, as imprecise as this already is, fixing that may just be noise. On the other hand, I'm loathe to leave it as a TODO, because I think that'd require another API change.

lib/Transforms/Vectorize/LoopVectorize.cpp

6782 ↗

(On Diff #81214)

Please don't leave undefined fields.

[magabari]

fixed issues pointed by Michael

include/llvm/Analysis/TargetTransformInfo.h

606 ↗

(On Diff #81214)

SCEV can't replace the struct, since you still need more info.
nullptr -> means default behavior
struct->isStrided = false -> means after check it is not strided at all
struct->isStrided = true -> you can look on the stride info or SCEV
but SCEV can be part of the struct if needed.
So in case there is no objections I prefer to go with struct which will contain bool and SCEV.

include/llvm/CodeGen/BasicTTIImpl.h

921 ↗

(On Diff #81550)

fixed

lib/Target/X86/X86TargetTransformInfo.cpp

1483 ↗

(On Diff #81550)

fixed

lib/Transforms/Vectorize/LoopVectorize.cpp

6782 ↗

(On Diff #81214)

fixed

[delena]

include/llvm/Analysis/TargetTransformInfo.h

609 ↗

(On Diff #81921)

Please add a cosntructor here.

613 ↗

(On Diff #81921)

I suggest to shorten these 2 functions:
bool isConstantStridedAccess() const {

   return (!Strided || !dyn_cast<SCEVConstant>(Step));
}

bool isConstantStridedAccessLessThan(int64_t MergeDistance) const {

  if (!isConstantStridedAccess())
    return false;
  APInt StrideVal = cast<SCEVConstant>(C)->getAPInt();
  if (StrideVal.getBitWidth() > 64)
    return false;
  return StrideVal.getSExtValue() < MergeDistance;
}

lib/Transforms/Vectorize/LoopVectorize.cpp

6788 ↗

(On Diff #81921)

These 2 lines may be removed once you have a constructor.

[magabari]

fix Elena comments

[mkuper]

include/llvm/Analysis/TargetTransformInfo.h

606 ↗

(On Diff #81214)

But aren't you figuring isStrided out based on the SCEV?
That is, if you pass a SCEV* S, it can be:
nullptr -> default
!isa<SCEVAddRecExpr>(S) -> not strided
isa<SCEVAddRecExpr>(S) -> strided?

[delena]

include/llvm/Analysis/TargetTransformInfo.h

606 ↗

(On Diff #81214)

There are 4 cases that we want to handle

1. Default, when pointer to AddressInfo is null. This case is equal to the old variant when IsComplex was false;
2. The access is complex and we don't have info about the stride. In this case we put isStrided = false and do not check SCEV.
3. The access is strided (isStrided = true, SCEV is not null): (3.1) Stride is constant (SCEV is const int) (3.2) Stride is loop invariant unknown value (SCEV is not const int)

I agree that we can drop isStrided and say the following:

2. The access is complex and we don't have info about the stride. AddressInfo is not null, but SCEV inside is null
3. The access is strided - SCEV is not null

Is that what you mean? I just think that the situation when "AddressInfo is not null, but SCEV inside is null" looks strange from design point of view.

[magabari]

re-adding the test. some how it got missed in the last version

[magabari]

ping

[mkuper]

What I'm saying is that you have this code in getAddressAccessComplexity():

const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Ptr));
if (!AddRec)
  return AddressInfo;

AddressInfo.isStrided = true;

// Get Step Recurrence.
AddressInfo.Step = AddRec->getStepRecurrence(*SE);
return AddressInfo;

So, basically, the logic right now is:

1. If we don't have a SCEV for the pointer, or have a SCEV which isn't an AddRec, return a struct with isStrided == false.
2. If we have a SCEV, and it's an AddRec, return a struct with isStrided == true, and a Step.

What I'm saying is that you could replace this with "If we don't have a SCEVAddRecExpr for the pointer return null, otherwise return the SCEV", and pass the result of that into getAddressComputationCost(). Then, if getAddressComputationCost() doesn't get a SCEV, it knows the access isn't strided. If it does get a SCEV, it knows it's strided, and can call getStepRecurrence to get the Step.

Am I missing something?

[magabari]

So you are suggesting passing the SCEV of the ptr instead of the Step, right?

I am just trying to think if there is more interesting access patterns rather than strided access to care about,
which is already covered by passing the step and isStrided boolean.
Also in this case I need to pass the ScalarEvolution ptr in order to get the Step.

[mkuper]

In D27518#630346, @magabari wrote:

So you are suggesting passing the SCEV of the ptr instead of the Step, right?

Yes.

I am just trying to think if there is more interesting access patterns rather than strided access to care about,
which is already covered by passing the step and isStrided boolean.

Sure, but you're basically inventing a new struct to pass information that's already encapsulated in an existing one (the SCEV). This may be justified, I'm just trying to understand what's the advantage of not passing the ptr SCEV. It looks like the SCEV would be more flexible, and using it avoids introducing another way to describe the same information. I originally thought it may be problematic from the layering perspective, but Hal made me realize that's nonsense, so... :-)

[magabari]

following Michael comments.
removed AddressAccessInfo and passed ScalarEvolution and Ptr SCEV directly.

[mkuper]

include/llvm/Analysis/TargetTransformInfo.h

26 ↗

(On Diff #82590)

Why do you need the expander?

include/llvm/Analysis/TargetTransformInfoImpl.h

430 ↗

(On Diff #82590)

This dyn_cast<> should be isa<>.

432 ↗

(On Diff #82590)

Missing newline between functions.

435 ↗

(On Diff #82590)

This dyn_cast<> can be a cast<> since you already know it's a SCEVAddRecExpr.
In general, you should never use dyn_cast without checking if the result is null. If you already know the cast is going to succeed, use cast<>. If not, use dyn_cast<> and check the result.

437 ↗

(On Diff #82590)

Again, isa<>.

439 ↗

(On Diff #82590)

Another missing newline.

443 ↗

(On Diff #82590)

Again, cast.

444 ↗

(On Diff #82590)

Why not replace isConstantStridedAccess() with something that returns the step if it succeeds?

lib/Target/AArch64/AArch64TargetTransformInfo.cpp

429 ↗

(On Diff #82590)

clang-format?

lib/Target/ARM/ARMTargetTransformInfo.cpp

350 ↗

(On Diff #82590)

clang-format?

[magabari]

fixed all comments

[magabari]

fixed Michael comments.

[magabari]

adding back the test (dropped it by mistake in the prev. patch)

[mkuper]

include/llvm/Analysis/TargetTransformInfo.h

26 ↗

(On Diff #82590)

Sorry, I missed this on the previous pass - but why do you even need this include here at all?
Can you forward-declare what you need (SCEV, ScalarEvolution?) and actually include this where you need it (I guess TargetTransformInfoImpl.h and the relevant cpps)?

include/llvm/Analysis/TargetTransformInfoImpl.h

446 ↗

(On Diff #82665)

You could just return a SCEVConstant* from getConstantStrideStep()
E.g. something like:

const SCEVConstant *getConstantStrideStep(ScalarEvolution *SE, const SCEV *Ptr) {
  if (!isStridedAccess(Ptr))
    return nullptr;

  const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ptr);
  return dyn_cast<SCEVConstant>(AddRec->getStepRecurrence(*SE));
}

Then this code could be something like:

bool isConstantStridedAccessLessThan(ScalarEvolution *SE, const SCEV *Ptr,
                                     int64_t MergeDistance) {
  const SCEVConstant *Step = getConstantStrideStep(SE, Ptr);
  APInt StrideVal = Step->getAPInt();
  if (StrideVal.getBitWidth() > 64)
    return false;
  return StrideVal.getSExtValue() < MergeDistance;
}

[magabari]

fixed Michael comments.

[mkuper]

LGTM, except that I'm not sure I understand what's going on with negative strides in isConstantStridedAccessLessThan().

include/llvm/Analysis/TargetTransformInfoImpl.h

450 ↗

(On Diff #82797)

Can we get here with negative stride values?

If we can't, then I'm not sure why you get the sext value - and why MergeDistance is signed.
If we can, then you probably don't want to return true for any negative value.

(I realize this was the way in the original, but as long as you're touching the code...)

[magabari]

In D27518#634251, @mkuper wrote:

LGTM, except that I'm not sure I understand what's going on with negative strides in isConstantStridedAccessLessThan().

I think it's a bug in the original version which i tried not to change. I will fix it in a separate patch.

[mkuper]

Ok, please add a FIXME in this patch for the negative stride thing, otherwise LGTM.

llvm/trunk/include/llvm/Analysis/TargetTransformInfo.h

 #include "llvm/Support/DataTypes.h"
 #include <functional>
 
 namespace llvm {
 
 class Function;
 class GlobalValue;
 class Loop;
+class ScalarEvolution;
+class SCEV;
 class Type;
 class User;
 class Value;
 
 /// \brief Information about a load/store intrinsic defined by the target.
 struct MemIntrinsicInfo {
   MemIntrinsicInfo()
       : ReadMem(false), WriteMem(false), IsSimple(false), MatchingId(0),
public:
   /// \returns The number of pieces into which the provided type must be
   /// split during legalization. Zero is returned when the answer is unknown.
   unsigned getNumberOfParts(Type *Tp) const;
 
   /// \returns The cost of the address computation. For most targets this can be
   /// merged into the instruction indexing mode. Some targets might want to
   /// distinguish between address computation for memory operations on vector
   /// types and scalar types. Such targets should override this function.
-  /// The 'IsComplex' parameter is a hint that the address computation is likely
-  /// to involve multiple instructions and as such unlikely to be merged into
-  /// the address indexing mode.
-  int getAddressComputationCost(Type *Ty, bool IsComplex = false) const;
+  /// The 'SE' parameter holds pointer for the scalar evolution object which
+  /// is used in order to get the Ptr step value in case of constant stride.
+  /// The 'Ptr' parameter holds SCEV of the access pointer.
+  int getAddressComputationCost(Type *Ty, ScalarEvolution *SE = nullptr,
+                                const SCEV *Ptr = nullptr) const;
 
   /// \returns The cost, if any, of keeping values of the given types alive
   /// over a callsite.
   ///
   /// Some types may require the use of register classes that do not have
   /// any callee-saved registers, so would require a spill and fill.
   unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) const;
 
virtual int getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy,
                                     ArrayRef<Type *> Tys,
                                     FastMathFlags FMF) = 0;
   virtual int getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy,
                                     ArrayRef<Value *> Args,
                                     FastMathFlags FMF) = 0;
   virtual int getCallInstrCost(Function *F, Type *RetTy,
                                ArrayRef<Type *> Tys) = 0;
   virtual unsigned getNumberOfParts(Type *Tp) = 0;
-  virtual int getAddressComputationCost(Type *Ty, bool IsComplex) = 0;
+  virtual int getAddressComputationCost(Type *Ty, ScalarEvolution *SE,
+                                        const SCEV *Ptr) = 0;
   virtual unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) = 0;
   virtual bool getTgtMemIntrinsic(IntrinsicInst *Inst,
                                   MemIntrinsicInfo &Info) = 0;
   virtual Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst,
                                                    Type *ExpectedType) = 0;
   virtual bool areInlineCompatible(const Function *Caller,
                                    const Function *Callee) const = 0;
   virtual unsigned getLoadStoreVecRegBitWidth(unsigned AddrSpace) const = 0;
public:
   }
   int getCallInstrCost(Function *F, Type *RetTy,
                        ArrayRef<Type *> Tys) override {
     return Impl.getCallInstrCost(F, RetTy, Tys);
   }
   unsigned getNumberOfParts(Type *Tp) override {
     return Impl.getNumberOfParts(Tp);
   }
-  int getAddressComputationCost(Type *Ty, bool IsComplex) override {
-    return Impl.getAddressComputationCost(Ty, IsComplex);
+  int getAddressComputationCost(Type *Ty, ScalarEvolution *SE,
+                                const SCEV *Ptr) override {
+    return Impl.getAddressComputationCost(Ty, SE, Ptr);
   }
   unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) override {
     return Impl.getCostOfKeepingLiveOverCall(Tys);
   }
   bool getTgtMemIntrinsic(IntrinsicInst *Inst,
                           MemIntrinsicInfo &Info) override {
     return Impl.getTgtMemIntrinsic(Inst, Info);
   }

llvm/trunk/include/llvm/Analysis/TargetTransformInfoImpl.h

 /// This file provides helpers for the implementation of
 /// a TargetTransformInfo-conforming class.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_TARGETTRANSFORMINFOIMPL_H
 #define LLVM_ANALYSIS_TARGETTRANSFORMINFOIMPL_H
 
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Analysis/VectorUtils.h"
public:
   }
 
   unsigned getCallInstrCost(Function *F, Type *RetTy, ArrayRef<Type *> Tys) {
     return 1;
   }
 
   unsigned getNumberOfParts(Type *Tp) { return 0; }
 
-  unsigned getAddressComputationCost(Type *Tp, bool) { return 0; }
+  unsigned getAddressComputationCost(Type *Tp, ScalarEvolution *,
+                                     const SCEV *) {
+    return 0; 
+  }
 
   unsigned getReductionCost(unsigned, Type *, bool) { return 1; }
 
   unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) { return 0; }
 
   bool getTgtMemIntrinsic(IntrinsicInst *Inst, MemIntrinsicInfo &Info) {
     return false;
   }
unsigned getLoadVectorFactor(unsigned VF, unsigned LoadSize,
     return VF;
   }
 
   unsigned getStoreVectorFactor(unsigned VF, unsigned StoreSize,
                                 unsigned ChainSizeInBytes,
                                 VectorType *VecTy) const {
     return VF;
   }
+protected:
+  bool isStridedAccess(const SCEV *Ptr) {
+    return Ptr && isa<SCEVAddRecExpr>(Ptr);
+  }
+
+  const SCEVConstant *getConstantStrideStep(ScalarEvolution *SE,
+                                            const SCEV *Ptr) {
+    if (!isStridedAccess(Ptr))
+      return nullptr;
+    const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ptr);
+    return dyn_cast<SCEVConstant>(AddRec->getStepRecurrence(*SE));
+  }
+
+  bool isConstantStridedAccessLessThan(ScalarEvolution *SE, const SCEV *Ptr,
+                                       int64_t MergeDistance) {
+    const SCEVConstant *Step = getConstantStrideStep(SE, Ptr);
+    if (!Step)
+      return false;
+    APInt StrideVal = Step->getAPInt();
+    if (StrideVal.getBitWidth() > 64)
+      return false;
+    // FIXME: need to take absolute value for negtive stride case  
+    return StrideVal.getSExtValue() < MergeDistance;
+  }
 };
 
 /// \brief CRTP base class for use as a mix-in that aids implementing
 /// a TargetTransformInfo-compatible class.
 template <typename T>
 class TargetTransformInfoImplCRTPBase : public TargetTransformInfoImplBase {
 private:
   typedef TargetTransformInfoImplBase BaseT;

llvm/trunk/include/llvm/CodeGen/BasicTTIImpl.h

unsigned getCallInstrCost(Function *F, Type *RetTy, ArrayRef<Type *> Tys) {
     return 10;
   }
 
   unsigned getNumberOfParts(Type *Tp) {
     std::pair<unsigned, MVT> LT = getTLI()->getTypeLegalizationCost(DL, Tp);
     return LT.first;
   }
 
-  unsigned getAddressComputationCost(Type *Ty, bool IsComplex) { return 0; }
+  unsigned getAddressComputationCost(Type *Ty, ScalarEvolution *,
+                                     const SCEV *) {
+    return 0; 
+  }
 
   unsigned getReductionCost(unsigned Opcode, Type *Ty, bool IsPairwise) {
     assert(Ty->isVectorTy() && "Expect a vector type");
     Type *ScalarTy = Ty->getVectorElementType();
     unsigned NumVecElts = Ty->getVectorNumElements();
     unsigned NumReduxLevels = Log2_32(NumVecElts);
     // Try to calculate arithmetic and shuffle op costs for reduction operations.
     // We're assuming that reduction operation are performing the following way:

llvm/trunk/lib/Analysis/TargetTransformInfo.cpp

int TargetTransformInfo::getCallInstrCost(Function *F, Type *RetTy,
   return Cost;
 }
 
 unsigned TargetTransformInfo::getNumberOfParts(Type *Tp) const {
   return TTIImpl->getNumberOfParts(Tp);
 }
 
 int TargetTransformInfo::getAddressComputationCost(Type *Tp,
-                                                   bool IsComplex) const {
-  int Cost = TTIImpl->getAddressComputationCost(Tp, IsComplex);
+                                                   ScalarEvolution *SE,
+                                                   const SCEV *Ptr) const {
+  int Cost = TTIImpl->getAddressComputationCost(Tp, SE, Ptr);
   assert(Cost >= 0 && "TTI should not produce negative costs!");
   return Cost;
 }
 
 int TargetTransformInfo::getReductionCost(unsigned Opcode, Type *Ty,
                                           bool IsPairwiseForm) const {
   int Cost = TTIImpl->getReductionCost(Opcode, Ty, IsPairwiseForm);
   assert(Cost >= 0 && "TTI should not produce negative costs!");

llvm/trunk/lib/Target/AArch64/AArch64TargetTransformInfo.h

public:
 
   int getArithmeticInstrCost(
       unsigned Opcode, Type *Ty,
       TTI::OperandValueKind Opd1Info = TTI::OK_AnyValue,
       TTI::OperandValueKind Opd2Info = TTI::OK_AnyValue,
       TTI::OperandValueProperties Opd1PropInfo = TTI::OP_None,
       TTI::OperandValueProperties Opd2PropInfo = TTI::OP_None);
 
-  int getAddressComputationCost(Type *Ty, bool IsComplex);
+  int getAddressComputationCost(Type *Ty, ScalarEvolution *SE, const SCEV *Ptr);
 
   int getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy);
 
   int getMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
                       unsigned AddressSpace);
 
   int getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys);
 

llvm/trunk/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

int AArch64TTIImpl::getArithmeticInstrCost(
   case ISD::OR:
   case ISD::AND:
     // These nodes are marked as 'custom' for combining purposes only.
     // We know that they are legal. See LowerAdd in ISelLowering.
     return 1 * LT.first;
   }
 }
 
-int AArch64TTIImpl::getAddressComputationCost(Type *Ty, bool IsComplex) {
+int AArch64TTIImpl::getAddressComputationCost(Type *Ty, ScalarEvolution *SE,
+                                              const SCEV *Ptr) {
   // Address computations in vectorized code with non-consecutive addresses will
   // likely result in more instructions compared to scalar code where the
   // computation can more often be merged into the index mode. The resulting
   // extra micro-ops can significantly decrease throughput.
   unsigned NumVectorInstToHideOverhead = 10;
+  int MaxMergeDistance = 64;
 
-  if (Ty->isVectorTy() && IsComplex)
+  if (Ty->isVectorTy() && SE && 
+      !BaseT::isConstantStridedAccessLessThan(SE, Ptr, MaxMergeDistance + 1))
     return NumVectorInstToHideOverhead;
 
   // In many cases the address computation is not merged into the instruction
   // addressing mode.
   return 1;
 }
 
 int AArch64TTIImpl::getCmpSelInstrCost(unsigned Opcode, Type *ValTy,

llvm/trunk/lib/Target/ARM/ARMTargetTransformInfo.h

public:
   int getShuffleCost(TTI::ShuffleKind Kind, Type *Tp, int Index, Type *SubTp);
 
   int getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src);
 
   int getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy);
 
   int getVectorInstrCost(unsigned Opcode, Type *Val, unsigned Index);
 
-  int getAddressComputationCost(Type *Val, bool IsComplex);
+  int getAddressComputationCost(Type *Val, ScalarEvolution *SE, 
+                                const SCEV *Ptr);
 
   int getFPOpCost(Type *Ty);
 
   int getArithmeticInstrCost(
       unsigned Opcode, Type *Ty,
       TTI::OperandValueKind Op1Info = TTI::OK_AnyValue,
       TTI::OperandValueKind Op2Info = TTI::OK_AnyValue,
       TTI::OperandValueProperties Opd1PropInfo = TTI::OP_None,

llvm/trunk/lib/Target/ARM/ARMTargetTransformInfo.cpp

if (ST->hasNEON() && ValTy->isVectorTy() && ISD == ISD::SELECT) {
 
     std::pair<int, MVT> LT = TLI->getTypeLegalizationCost(DL, ValTy);
     return LT.first;
   }
 
   return BaseT::getCmpSelInstrCost(Opcode, ValTy, CondTy);
 }
 
-int ARMTTIImpl::getAddressComputationCost(Type *Ty, bool IsComplex) {
+int ARMTTIImpl::getAddressComputationCost(Type *Ty, ScalarEvolution *SE,
+                                          const SCEV *Ptr) {
   // Address computations in vectorized code with non-consecutive addresses will
   // likely result in more instructions compared to scalar code where the
   // computation can more often be merged into the index mode. The resulting
   // extra micro-ops can significantly decrease throughput.
   unsigned NumVectorInstToHideOverhead = 10;
+  int MaxMergeDistance = 64;
 
-  if (Ty->isVectorTy() && IsComplex)
+  if (Ty->isVectorTy() && SE && 
+      !BaseT::isConstantStridedAccessLessThan(SE, Ptr, MaxMergeDistance + 1))
     return NumVectorInstToHideOverhead;
 
   // In many cases the address computation is not merged into the instruction
   // addressing mode.
   return 1;
 }
 
 int ARMTTIImpl::getFPOpCost(Type *Ty) {

llvm/trunk/lib/Target/X86/X86TargetTransformInfo.h

public:
   int getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy);
   int getVectorInstrCost(unsigned Opcode, Type *Val, unsigned Index);
   int getMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
                       unsigned AddressSpace);
   int getMaskedMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
                             unsigned AddressSpace);
   int getGatherScatterOpCost(unsigned Opcode, Type *DataTy, Value *Ptr,
                              bool VariableMask, unsigned Alignment);
-  int getAddressComputationCost(Type *PtrTy, bool IsComplex);
+  int getAddressComputationCost(Type *PtrTy, ScalarEvolution *SE,
+                                const SCEV *Ptr);
 
   int getIntrinsicInstrCost(Intrinsic::ID IID, Type *RetTy,
                             ArrayRef<Type *> Tys, FastMathFlags FMF);
   int getIntrinsicInstrCost(Intrinsic::ID IID, Type *RetTy,
                             ArrayRef<Value *> Args, FastMathFlags FMF);
 
   int getReductionCost(unsigned Opcode, Type *Ty, bool IsPairwiseForm);
 

llvm/trunk/lib/Target/X86/X86TargetTransformInfo.cpp

int X86TTIImpl::getMaskedMemoryOpCost(unsigned Opcode, Type *SrcTy,
   }
   if (!ST->hasAVX512())
     return Cost + LT.first*4; // Each maskmov costs 4
 
   // AVX-512 masked load/store is cheapper
   return Cost+LT.first;
 }
 
-int X86TTIImpl::getAddressComputationCost(Type *Ty, bool IsComplex) {
+int X86TTIImpl::getAddressComputationCost(Type *Ty, ScalarEvolution *SE,
+                                          const SCEV *Ptr) {
   // Address computations in vectorized code with non-consecutive addresses will
   // likely result in more instructions compared to scalar code where the
   // computation can more often be merged into the index mode. The resulting
   // extra micro-ops can significantly decrease throughput.
   unsigned NumVectorInstToHideOverhead = 10;
 
-  if (Ty->isVectorTy() && IsComplex)
+  // Cost modeling of Strided Access Computation is hidden by the indexing
+  // modes of X86 regardless of the stride value. We dont believe that there
+  // is a difference between constant strided access in gerenal and constant
+  // strided value which is less than or equal to 64.
+  // Even in the case of (loop invariant) stride whose value is not known at
+  // compile time, the address computation will not incur more than one extra
+  // ADD instruction.
+  if (Ty->isVectorTy() && SE) {
+    if (!BaseT::isStridedAccess(Ptr))
       return NumVectorInstToHideOverhead;
+    if (!BaseT::getConstantStrideStep(SE, Ptr))
+      return 1;
+  }
 
-  return BaseT::getAddressComputationCost(Ty, IsComplex);
+  return BaseT::getAddressComputationCost(Ty, SE, Ptr);
 }
 
 int X86TTIImpl::getReductionCost(unsigned Opcode, Type *ValTy,
                                  bool IsPairwise) {
 
   std::pair<int, MVT> LT = TLI->getTypeLegalizationCost(DL, ValTy);
 
   MVT MTy = LT.second;

llvm/trunk/lib/Transforms/Vectorize/LoopVectorize.cpp

for (BasicBlock *BB : TheLoop->blocks()) {
 
     Cost.first += BlockCost.first;
     Cost.second |= BlockCost.second;
   }
 
   return Cost;
 }
 
-/// \brief Check whether the address computation for a non-consecutive memory
-/// access looks like an unlikely candidate for being merged into the indexing
-/// mode.
+/// \brief Gets Address Access SCEV after verifying that the access pattern
+/// is loop invariant except the induction variable dependence.
 ///
-/// We look for a GEP which has one index that is an induction variable and all
-/// other indices are loop invariant. If the stride of this access is also
-/// within a small bound we decide that this address computation can likely be
-/// merged into the addressing mode.
-/// In all other cases, we identify the address computation as complex.
-static bool isLikelyComplexAddressComputation(Value *Ptr,
-                                              LoopVectorizationLegality *Legal,
-                                              ScalarEvolution *SE,
-                                              const Loop *TheLoop) {
+/// This SCEV can be sent to the Target in order to estimate the address
+/// calculation cost.
+static const SCEV *getAddressAccessSCEV(
+              Value *Ptr,
   auto *Gep = dyn_cast<GetElementPtrInst>(Ptr);
   if (!Gep)
-    return true;
+    return nullptr;
 
   // We are looking for a gep with all loop invariant indices except for one
   // which should be an induction variable.
   unsigned NumOperands = Gep->getNumOperands();
   for (unsigned i = 1; i < NumOperands; ++i) {
     Value *Opd = Gep->getOperand(i);
     if (!SE->isLoopInvariant(SE->getSCEV(Opd), TheLoop) &&
         !Legal->isInductionVariable(Opd))
-      return true;
+      return nullptr;
   }
 
-  // Now we know we have a GEP ptr, %inv, %ind, %inv. Make sure that the step
-  // can likely be merged into the address computation.
-  unsigned MaxMergeDistance = 64;
-
-  const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Ptr));
-  if (!AddRec)
-    return true;
-
-  // Check the step is constant.
-  const SCEV *Step = AddRec->getStepRecurrence(*SE);
-  // Calculate the pointer stride and check if it is consecutive.
-  const auto *C = dyn_cast<SCEVConstant>(Step);
-  if (!C)
-    return true;
-
-  const APInt &APStepVal = C->getAPInt();
-
-  // Huge step value - give up.
-  if (APStepVal.getBitWidth() > 64)
-    return true;
-
-  int64_t StepVal = APStepVal.getSExtValue();
-
-  return StepVal > MaxMergeDistance;
+  // Now we know we have a GEP ptr, %inv, %ind, %inv. return the Ptr SCEV.
+  return SE->getSCEV(Ptr);
 }
 
 static bool isStrideMul(Instruction *I, LoopVectorizationLegality *Legal) {
   return Legal->hasStride(I->getOperand(0)) ||
          Legal->hasStride(I->getOperand(1));
 }
 
 LoopVectorizationCostModel::VectorizationCostTy
if (Legal->isAccessInterleaved(I)) {
       return Cost;
     }
 
     // Check if the memory instruction will be scalarized.
     if (Legal->memoryInstructionMustBeScalarized(I, VF)) {
       unsigned Cost = 0;
       Type *PtrTy = ToVectorTy(Ptr->getType(), VF);
 
-      // True if the memory instruction's address computation is complex.
-      bool IsComplexComputation =
-          isLikelyComplexAddressComputation(Ptr, Legal, SE, TheLoop);
+      // Figure out whether the access is strided and get the stride value
+      // if it's known in compile time
+      const SCEV *PtrSCEV = getAddressAccessSCEV(Ptr, Legal, SE, TheLoop); 
 
       // Get the cost of the scalar memory instruction and address computation.
-      Cost += VF * TTI.getAddressComputationCost(PtrTy, IsComplexComputation);
+      Cost += VF * TTI.getAddressComputationCost(PtrTy, SE, PtrSCEV);
       Cost += VF *
               TTI.getMemoryOpCost(I->getOpcode(), ValTy->getScalarType(),
                                   Alignment, AS);
 
       // Get the overhead of the extractelement and insertelement instructions
       // we might create due to scalarization.
       Cost += getScalarizationOverhead(I, VF, TTI);
 

llvm/trunk/test/Transforms/LoopVectorize/X86/strided_load_cost.ll

+; This test checks that the given loop still beneficial for vecotization
+; even if it contains scalarized load (gather on AVX2)
+;RUN: opt < %s -loop-vectorize -S -o - | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: norecurse nounwind readonly uwtable
+define i32 @matrix_row_col([100 x i32]* nocapture readonly %data, i32 %i, i32 %j) local_unnamed_addr #0 {
+entry:
+  %idxprom = sext i32 %i to i64
+  %idxprom5 = sext i32 %j to i64
+  br label %for.body
+
+  for.cond.cleanup:                                 ; preds = %for.body
+  ret i32 %add7
+
+  for.body:                                         ; preds = %for.body, %entry
+  ; the loop gets vectorized
+  ; first consecutive load as vector load
+  ; CHECK: %wide.load = load <8 x i32>
+  ; second strided load scalarized
+  ; CHECK: load i32
+  ; CHECK: load i32
+  ; CHECK: load i32
+  ; CHECK: load i32
+  ; CHECK: load i32
+  ; CHECK: load i32
+  ; CHECK: load i32
+  ; CHECK: load i32
+
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %sum.015 = phi i32 [ 0, %entry ], [ %add7, %for.body ]
+  %arrayidx2 = getelementptr inbounds [100 x i32], [100 x i32]* %data, i64 %idxprom, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx2, align 4, !tbaa !1
+  %arrayidx6 = getelementptr inbounds [100 x i32], [100 x i32]* %data, i64 %indvars.iv, i64 %idxprom5
+  %1 = load i32, i32* %arrayidx6, align 4, !tbaa !1
+  %mul = mul nsw i32 %1, %0
+  %add = add i32 %sum.015, 4
+  %add7 = add i32 %add, %mul
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 100
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+attributes #0 = { "target-cpu"="core-avx2" "target-features"="+avx,+avx2,+sse,+sse2,+sse3,+sse4.1,+sse4.2,+ssse3" }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 4.0.0 (cfe/trunk 284570)"}
+!1 = !{!2, !2, i64 0}
+!2 = !{!"int", !3, i64 0}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C/C++ TBAA"}