Changed basic cost of Store operation on X86.

[delena]

Summary

Store operation takes 2 UOps on X86 processors. The exact cost calculation affects several optimization passes including loop unroling.
This change compensates performance degradation caused by https://reviews.llvm.org/D34458 and shows improvements on some benchmarks.

[zvi]

Elena, can you please add a test-case? Maybe a loop that this patch will prevent from being unrolled?

[eastig]

Hi Elena,

There is already

/// \return The cost of Load and Store instructions.
int TargetTransformInfo::getMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
                    unsigned AddressSpace, const Instruction *I = nullptr) const;

Maybe it should be updated and used?

[delena]

In D35888#821581, @eastig wrote:

Hi Elena,

There is already

/// \return The cost of Load and Store instructions.
int TargetTransformInfo::getMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
                    unsigned AddressSpace, const Instruction *I = nullptr) const;

Maybe it should be updated and used?

We have 2 sets of cost functions in TTI. One set is used by vectorizer in order to compare same operations with different vector types. Vectorizer does not estimate num of UOps, it mostly counts instructions. The second set is getOperationCost() returns TCC_Free/Basic/Expensive and used by Unroller, Inliner and, I think, CFG-simplifiy pass. These 2 sets are not mixed AFAIK.

[delena]

Added a test case.

[ashutosh.nema]

Is store is always 2 UOps on x86, independent of the type and register(xmm/ymm) ?

Thanks,
Ashutosh

[eastig]

In D35888#821885, @delena wrote:

We have 2 sets of cost functions in TTI. One set is used by vectorizer in order to compare same operations with different vector types. Vectorizer does not estimate num of UOps, it mostly counts instructions. The second set is getOperationCost() returns TCC_Free/Basic/Expensive and used by Unroller, Inliner and, I think, CFG-simplifiy pass. These 2 sets are not mixed AFAIK.

Thank you for clarification. I didn't know about this. It is not clear from the documentation. IMHO these specifics should be reflected at the language level not at the doc level.
What about having getLoadCost? I think there will be a reasonable question why there is getStoreCost but no getLoadCost.
Or can we have the overloaded version of TargetTransformInfo::getMemoryOpCost:

int TargetTransformInfo::getMemoryOpCost(const Instruction *I)

[delena]

In D35888#822536, @ashutosh.nema wrote:

Is store is always 2 UOps on x86, independent of the type and register(xmm/ymm) ?

Thanks,
Ashutosh

Yes, if the address has index and scale. If the address is simple, IACA shows "micro fusion".
IACA is publicly available tool that shows number of UOPS and ports per instruction for Intel processors.
https://software.intel.com/en-us/articles/intel-architecture-code-analyzer

[delena]

What about having getLoadCost? I think there will be a reasonable question why there is getStoreCost but no getLoadCost.
Or can we have the overloaded version of TargetTransformInfo::getMemoryOpCost:

int TargetTransformInfo::getMemoryOpCost(const Instruction *I)

I don't think that we want to extend interface without any special need. Load is 1 Uop on X86, and, probably, on other targets, so everyone is happy with the common getOperatopnCost().

[eastig]

In D35888#822557, @delena wrote:

What about having getLoadCost? I think there will be a reasonable question why there is getStoreCost but no getLoadCost.
Or can we have the overloaded version of TargetTransformInfo::getMemoryOpCost:

int TargetTransformInfo::getMemoryOpCost(const Instruction *I)

I don't think that we want to extend interface without any special need. Load is 1 Uop on X86, and, probably, on other targets, so everyone is happy with the common getOperatopnCost().

Maybe I am wrong but the instruction cost is the cost relative to the cost of a typical instruction. TTI does not operates in terms of microarchitecture: u-ops etc. Why do we need a general function which is only for X86? How will other architectures need it? If everyone is happy with getOperationCost why X86 is not? Is it possible to have this functionality in X86TTI without changing general TTI?

BTW ARM has LDM/STM (load and store multiple instructions) which can be quite heavy comparing to a typical instruction.

[delena]

Maybe I am wrong but the instruction cost is the cost relative to the cost of a typical instruction. TTI does not operates in terms of microarchitecture: u-ops etc. Why do we need a general function which is only for X86? How will other architectures need it? If everyone is happy with getOperationCost why X86 is not? Is it possible to have this functionality in X86TTI without changing general TTI?

The second option is to customize the getOperationCost() for X86. Agree, it is also a way to provide target specific cost. Is that what you suggest?

BTW ARM has LDM/STM (load and store multiple instructions) which can be quite heavy comparing to a typical instruction.

May be ARM should also customize load/store? I don't know. X86 hits performance regression due to wrong estimation of unroll factor against LSD.

[eastig]

In D35888#822634, @delena wrote:

Maybe I am wrong but the instruction cost is the cost relative to the cost of a typical instruction. TTI does not operates in terms of microarchitecture: u-ops etc. Why do we need a general function which is only for X86? How will other architectures need it? If everyone is happy with getOperationCost why X86 is not? Is it possible to have this functionality in X86TTI without changing general TTI?

The second option is to customize the getOperationCost() for X86. Agree, it is also a way to provide target specific cost. Is that what you suggest?

Yes, some kind of this. getOperationCost or getUserCost can be customized. For example, X86TTIImpl can override getUserCost in the following way:

unsigned X86TIImpl::getUserCost(const User *U,                                 
                                 ArrayRef<const Value *> Operands) {            
  if (isa<StoreInst>(U))
      return getStoreCost(cast<Instruction>(U));
  return BaseT::getUserCost(U, Operands);                                       
}

[delena]

I updated the patch according to Evgeny's comments.
(Sorry for the delay, I was on vacation)

[eastig]

Just back from vacation.
LGTM.
Thank you, Elena.

include/llvm/Analysis/TargetTransformInfo.h

public:
 
   /// \brief Estimate the cost of a EXT operation when lowered.
   ///
   /// The contract for this function is the same as \c getOperationCost except
   /// that it supports an interface that provides extra information specific to
   /// the EXT operation.
   int getExtCost(const Instruction *I, const Value *Src) const;
 
+  /// \brief Estimate the cost of Store operation when lowered
+  ///
+  /// The contract for this function is the same as \c getOperationCost.
+  /// This is the basic query to estimate the cost of Store operation in terms
+  /// of \c TargetCostConstants.
+  int getStoreCost(const Instruction *I) const;
+
   /// \brief Estimate the cost of a function call when lowered.
   ///
   /// The contract for this is the same as \c getOperationCost except that it
   /// supports an interface that provides extra information specific to call
   /// instructions.
   ///
   /// This is the most basic query for estimating call cost: it only knows the
   /// function type and (potentially) the number of arguments at the call site.

 class TargetTransformInfo::Concept {
 public:
   virtual ~Concept() = 0;
   virtual const DataLayout &getDataLayout() const = 0;
   virtual int getOperationCost(unsigned Opcode, Type *Ty, Type *OpTy) = 0;
   virtual int getGEPCost(Type *PointeeType, const Value *Ptr,
                          ArrayRef<const Value *> Operands) = 0;
   virtual int getExtCost(const Instruction *I, const Value *Src) = 0;
+  virtual int getStoreCost(const Instruction *I) = 0;
   virtual int getCallCost(FunctionType *FTy, int NumArgs) = 0;
   virtual int getCallCost(const Function *F, int NumArgs) = 0;
   virtual int getCallCost(const Function *F,
                           ArrayRef<const Value *> Arguments) = 0;
   virtual unsigned getInliningThresholdMultiplier() = 0;
   virtual int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                                ArrayRef<Type *> ParamTys) = 0;
   virtual int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
public:
   }
   int getGEPCost(Type *PointeeType, const Value *Ptr,
                  ArrayRef<const Value *> Operands) override {
     return Impl.getGEPCost(PointeeType, Ptr, Operands);
   }
   int getExtCost(const Instruction *I, const Value *Src) override {
     return Impl.getExtCost(I, Src);
   }
+  int getStoreCost(const Instruction *I) override {
+    return Impl.getStoreCost(I);
+  }
   int getCallCost(FunctionType *FTy, int NumArgs) override {
     return Impl.getCallCost(FTy, NumArgs);
   }
   int getCallCost(const Function *F, int NumArgs) override {
     return Impl.getCallCost(F, NumArgs);
   }
   int getCallCost(const Function *F,
                   ArrayRef<const Value *> Arguments) override {

include/llvm/Analysis/TargetTransformInfoImpl.h

unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
     // certain intrinsics based on constants used as arguments.
     SmallVector<Type *, 8> ParamTys;
     ParamTys.reserve(Arguments.size());
     for (unsigned Idx = 0, Size = Arguments.size(); Idx != Size; ++Idx)
       ParamTys.push_back(Arguments[Idx]->getType());
     return static_cast<T *>(this)->getIntrinsicCost(IID, RetTy, ParamTys);
   }
 
+  unsigned getStoreCost(const Instruction *I) {
+    return static_cast<T *>(this)
+        ->getOperationCost(Instruction::Store, I->getType(), 
+                           I->getOperand(0)->getType());
+  }
+
   unsigned getUserCost(const User *U, ArrayRef<const Value *> Operands) {
     if (isa<PHINode>(U))
       return TTI::TCC_Free; // Model all PHI nodes as free.
 
     if (const GEPOperator *GEP = dyn_cast<GEPOperator>(U)) {
       return static_cast<T *>(this)->getGEPCost(GEP->getSourceElementType(),
                                                 GEP->getPointerOperand(),
                                                 Operands.drop_front());
if (const CastInst *CI = dyn_cast<CastInst>(U)) {
       // cmp instructions, logical or return instructions). These are usually
       // nop on most sane targets.
       if (isa<CmpInst>(CI->getOperand(0)))
         return TTI::TCC_Free;
       if (isa<SExtInst>(CI) || isa<ZExtInst>(CI) || isa<FPExtInst>(CI))
         return static_cast<T *>(this)->getExtCost(CI, Operands.back());
     }
 
+    if (isa<StoreInst>(U))
+      return static_cast<T *>(this)->getStoreCost(cast<Instruction>(U));
+
     return static_cast<T *>(this)->getOperationCost(
         Operator::getOpcode(U), U->getType(),
         U->getNumOperands() == 1 ? U->getOperand(0)->getType() : nullptr);
   }
 };
 }
 
 #endif

lib/Analysis/TargetTransformInfo.cpp

int TargetTransformInfo::getGEPCost(Type *PointeeType, const Value *Ptr,
   return TTIImpl->getGEPCost(PointeeType, Ptr, Operands);
 }
 
 int TargetTransformInfo::getExtCost(const Instruction *I,
                                     const Value *Src) const {
   return TTIImpl->getExtCost(I, Src);
 }
 
+int TargetTransformInfo::getStoreCost(const Instruction *I) const {
+  return TTIImpl->getStoreCost(I);
+}
+
 int TargetTransformInfo::getIntrinsicCost(
     Intrinsic::ID IID, Type *RetTy, ArrayRef<const Value *> Arguments) const {
   int Cost = TTIImpl->getIntrinsicCost(IID, RetTy, Arguments);
   assert(Cost >= 0 && "TTI should not produce negative costs!");
   return Cost;
 }
 
 unsigned

lib/Target/X86/X86TargetTransformInfo.h

public:
   int getInterleavedMemoryOpCostAVX2(unsigned Opcode, Type *VecTy,
                                  unsigned Factor, ArrayRef<unsigned> Indices,
                                  unsigned Alignment, unsigned AddressSpace);
 
   int getIntImmCost(int64_t);
 
   int getIntImmCost(const APInt &Imm, Type *Ty);
 
+  int getStoreCost(const Instruction *I);
+
   int getIntImmCost(unsigned Opcode, unsigned Idx, const APInt &Imm, Type *Ty);
   int getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm,
                     Type *Ty);
   bool isLegalMaskedLoad(Type *DataType);
   bool isLegalMaskedStore(Type *DataType);
   bool isLegalMaskedGather(Type *DataType);
   bool isLegalMaskedScatter(Type *DataType);
   bool areInlineCompatible(const Function *Caller,

lib/Target/X86/X86TargetTransformInfo.cpp

int X86TTIImpl::getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm,
   case Intrinsic::experimental_patchpoint_i64:
     if ((Idx < 4) || (Imm.getBitWidth() <= 64 && isInt<64>(Imm.getSExtValue())))
       return TTI::TCC_Free;
     break;
   }
   return X86TTIImpl::getIntImmCost(Imm, Ty);
 }
 
+int X86TTIImpl::getStoreCost(const Instruction *I) {
+  assert(isa<StoreInst>(I) && "Expected Store Instruction in getStoreCost()");
+  Value *Ptr = I->getOperand(1);
+  // Store operation takes 2 UOps. If the address is simple, without scale*index
+  // arithmetics, address calculation goes to another port.
+  if (auto GEP = dyn_cast<GetElementPtrInst>(Ptr)) {
+    if (!all_of(GEP->indices(), [](Value *V) { return isa<Constant>(V); }))
+      return TTI::TCC_Basic * 2;
+  }
+  return TTI::TCC_Basic;
+}
+
 // Return an average cost of Gather / Scatter instruction, maybe improved later
 int X86TTIImpl::getGSVectorCost(unsigned Opcode, Type *SrcVTy, Value *Ptr,
                                 unsigned Alignment, unsigned AddressSpace) {
 
   assert(isa<VectorType>(SrcVTy) && "Unexpected type in getGSVectorCost");
   unsigned VF = SrcVTy->getVectorNumElements();
 
   // Try to reduce index size from 64 bit (default for GEP)