[TTI] getMemcpyCost

[SjoerdMeijer]

Summary

This adds new function getMemcpyCost to TTI so that the cost of a memcpy can be
modeled and queried.

[t.p.northover]

include/llvm/Analysis/TargetTransformInfoImpl.h

144 ↗

(On Diff #190249)

That seems optimistic, even as a default. I'd probably bump it to TCC_Expensive if just one load/store is needed, and a size-based estimate would be even better (is there a DataLayout handy to calculate length in terms of pointer-words?)

[SjoerdMeijer]

include/llvm/Analysis/TargetTransformInfoImpl.h

144 ↗

(On Diff #190249)

Thanks for looking into this. Agreed that TCC_Basic doesn't make much sense.

As a default size based estimate, I am thinking of this default:

(2 * TCC_Basic)  * (memcpy-count / pointer-size)

where:
(2 * TCC_Basic) is a load/store pair, and
(memcpy-count / pointer-size) models the number of load/stores needed

Since this will change behaviour, I probably need a test somewhere. :-)

[arsenm]

include/llvm/Analysis/TargetTransformInfoImpl.h

144 ↗

(On Diff #190249)

A pointer size isn't relevant. We already have things like getMemcpyLoopLoweringType for when memcpy is expanded. The cost should also be much higher for unknown amounts

[SjoerdMeijer]

In my previous comment, I commented on a possible default cost calculation for a memcpy, which approximated the cost by calculating the number of load/stores pairs. I probably could see this working as a default estimation, because I think when this would be used, the result will be that memcpy's are considered expensive relative to other instructions, which is probably correct. However, I appreciate that this is an approximation, and that there are many things missing here, like source/destination alignment, available load/store instruction, etc., which really shows this is a target dependent decision. So, I've changed getMemcpyCost to just simply return TCC_Expensive, so that target can override this method and implement their decision making there, like is done for many/most functions here in TTI.

I've added a regression test.

[SjoerdMeijer]

Apologies for already asking, but I was curious if @t.p.northover or @arsenm had more feedback/concerns or if this looks somewhat reasonable.

[samparker]

LGTM. I think returning Expensive is the only reasonable thing we can do for a default implementation. It's more realistic than Basic and for anything else more complicated, it should be up to a target to override.

[SjoerdMeijer]

Thanks for looking Sam!
I will wait a day with committing this, just in case there are more comments.

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

public:
 
   /// Estimate the cost of an intrinsic when lowered.
   ///
   /// Mirrors the \c getCallCost method but uses an intrinsic identifier.
   int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                        ArrayRef<const Value *> Arguments,
                        const User *U = nullptr) const;
 
+  /// \Return the expected cost of a memcpy, which could e.g. depend on the
+  /// source/destination type and alignment and the number of bytes copied.
+  int getMemcpyCost(const Instruction *I) const;
+
   /// \return The estimated number of case clusters when lowering \p 'SI'.
   /// \p JTSize Set a jump table size only when \p SI is suitable for a jump
   /// table.
   unsigned getEstimatedNumberOfCaseClusters(const SwitchInst &SI,
                                             unsigned &JTSize) const;
 
   /// Estimate the cost of a given IR user when lowered.
   ///
public:
   virtual int getCallCost(const Function *F,
                           ArrayRef<const Value *> Arguments, const User *U) = 0;
   virtual unsigned getInliningThresholdMultiplier() = 0;
   virtual int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                                ArrayRef<Type *> ParamTys, const User *U) = 0;
   virtual int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                                ArrayRef<const Value *> Arguments,
                                const User *U) = 0;
+  virtual int getMemcpyCost(const Instruction *I) = 0;
   virtual unsigned getEstimatedNumberOfCaseClusters(const SwitchInst &SI,
                                                     unsigned &JTSize) = 0;
   virtual int
   getUserCost(const User *U, ArrayRef<const Value *> Operands) = 0;
   virtual bool hasBranchDivergence() = 0;
   virtual bool isSourceOfDivergence(const Value *V) = 0;
   virtual bool isAlwaysUniform(const Value *V) = 0;
   virtual unsigned getFlatAddressSpace() = 0;
int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                        ArrayRef<Type *> ParamTys, const User *U = nullptr) override {
     return Impl.getIntrinsicCost(IID, RetTy, ParamTys, U);
   }
   int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                        ArrayRef<const Value *> Arguments,
                        const User *U = nullptr) override {
     return Impl.getIntrinsicCost(IID, RetTy, Arguments, U);
   }
+  int getMemcpyCost(const Instruction *I) {
+    return Impl.getMemcpyCost(I);
+  }
   int getUserCost(const User *U, ArrayRef<const Value *> Operands) override {
     return Impl.getUserCost(U, Operands);
   }
   bool hasBranchDivergence() override { return Impl.hasBranchDivergence(); }
   bool isSourceOfDivergence(const Value *V) override {
     return Impl.isSourceOfDivergence(V);
   }
 

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

if (NumArgs < 0)
       // function.
       NumArgs = FTy->getNumParams();
 
     return TTI::TCC_Basic * (NumArgs + 1);
   }
 
   unsigned getInliningThresholdMultiplier() { return 1; }
 
+  unsigned getMemcpyCost(const Instruction *I) {
+    return TTI::TCC_Expensive;
+  }
+
   unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                             ArrayRef<Type *> ParamTys, const User *U) {
     switch (IID) {
     default:
       // Intrinsics rarely (if ever) have normal argument setup constraints.
       // Model them as having a basic instruction cost.
-      // FIXME: This is wrong for libc intrinsics.
       return TTI::TCC_Basic;
 
+    // TODO: other libc intrinsics.
+    case Intrinsic::memcpy:
+      return getMemcpyCost(dyn_cast<Instruction>(U));
+
     case Intrinsic::annotation:
     case Intrinsic::assume:
     case Intrinsic::sideeffect:
     case Intrinsic::dbg_declare:
     case Intrinsic::dbg_value:
     case Intrinsic::dbg_label:
     case Intrinsic::invariant_start:
     case Intrinsic::invariant_end:

llvm/trunk/test/Analysis/CostModel/ARM/memcpy.ll

+; RUN: opt < %s  -cost-model -analyze -cost-kind=code-size | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "thumbv7m-arm-unknown-eabi"
+
+define void @memcpy(i8* %d, i8* %s, i32 %N) {
+entry:
+; CHECK: cost of 4 for instruction: call void @llvm.memcpy.p0i8.p0i8.i32
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* align 1 %d, i8* align 1 %s, i32 36, i1 false)
+  ret void
+}
+
+declare void @llvm.memcpy.p0i8.p0i8.i32(i8* nocapture writeonly, i8* nocapture readonly, i32, i1) #1