Use the basic cost if a GEP is not used as addressing mode

[junbuml]

Summary

Currently, getGEPCost() returns TCC_FREE whenever a GEP is a legal addressing mode in the target.
However, since it doesn't check its actual users, it will return FREE even in cases
where the GEP cannot be folded away as a part of actual addressing mode.
For example, if an user of the GEP is a call instruction taking the GEP as a parameter,
then the GEP may not be folded in isel.

[junbuml]

In my tests for spec2000/2006/2017 on aarch64 with -O3, I didn't see any significant performance regressions, and the code size change was minor.

test/Analysis/CostModel/X86/vector_gep.ll

11

With this patch, %B is changed to a non-free because it's used in %arrayidx (non-memory operation). It might be possible to continue checking users of the non-memory operation users, but doing this completely must be expensive to be done in getGEPCost. It might be possible to add some simple exceptions, but in this patch I didn't add such checks.

[efriedma]

test/Analysis/CostModel/X86/vector_gep.ll

11

Yes, it should be fine to avoid folding together GEPs in getUserCost(). (Arguably, you might want to, but it could get complicated, so okay to skip that for now.)

That said, there's something going wrong here. "gep %x, 0, 0" is free because it's just a type conversion. By the same reasoning, "gep %s, zeroinitializer, zeroinitializer" should also be free.

[hfinkel]

include/llvm/Analysis/TargetTransformInfo.h

255

This comment would need to be updated.

include/llvm/Analysis/TargetTransformInfoImpl.h

55

This needs to be updated, or...

At a high level, I'm not sure what we want to completely remove the version of the function that can be used without an existing function. Instead, we should add an overload, and then fall back to the existing code where relevant.

[junbuml]

include/llvm/Analysis/TargetTransformInfoImpl.h

55

I'm not perfectly clear about this.
Do you think we should keep the existing getGEPCost as it is :

int getGEPCost(Type *PointeeType, const Value *Ptr, ArrayRef<const Value *> Operands),

and add the new one :

int getGEPCost(const GEPOperator *GEP, ArrayRef<const Value *> Operands)

test/Analysis/CostModel/X86/vector_gep.ll

11

We might be able to handle zeroinlitializer in hasAllZeroIndices() for ArrayType. Then, I think it should be a separate patch.

[hfinkel]

include/llvm/Analysis/TargetTransformInfoImpl.h

55

Yes. Then implement this new function so that it calls the instruction-independent version to handle the non-user-based logic.

test/Analysis/CostModel/X86/vector_gep.ll

11

Why a separate patch? This patch is not overly complicated, and if there's a separate patch we'll have a regression in between.

If you want to separate the patches, we should have them both before either is committed. But it sounds like a couple lines of code and a few lines of code for some tests.

[junbuml]

Addressed comments from Hal and Eli.

[junbuml]

Kindly ping.

[hfinkel]

include/llvm/Analysis/TargetTransformInfoImpl.h

755

togetehr -> together

757

I don't understand this comment. If there's a sext/zext, then it would be an operand of the GEP, not the other way around, no?

[junbuml]

Address Hal's comment.

include/llvm/Analysis/TargetTransformInfoImpl.h

757

Yes, sext must be an operand of the GEP, not an user. Sorry for the confusion. Remove "sext" from the comment.

[hfinkel]

LGTM

[junbuml]

Minor change in spacing. Thanks for the review !

[alekseyshl]

Reverted as r314560, it crashes sanitizer bots.

[eastig]

Thank you, Jun, for fixing this.
There is PR33642 with a test case when TCC_FREE is returned for non-cost free GEPs.

[junbuml]

The buildbot failure happened when an user of GEPOperator (GEP ConstantExpr) is a constant. Now returns TCC_Basic for ConstantExpr as it require one or two instructions. For example in AArch64, adrp and add instruction is required. The test case added should show the case.

[efriedma]

Oh, I see, cast<Operator>(U) will crash in cases where the user is something else, like a global variable.

A ConstantExpr GEP could still be free in certain cases (e.g. on x86-64 a GEP of a global variable could get lowered to a RIP-relative load instruction), but maybe not worth worrying about.

[junbuml]

Recommitted in r314923. Thanks for the review.

[chandlerc]

This patch got reverted again, and I wanted to provide some insight as to why...

We saw a pretty dramatic and immediate regression in benchmarks due to failed inlining. One of the benchmarks is open source (Gipfeli) but it can be hard or impossible to reproduce the benchmark rigging that shows the clear issue. But looking at just one benchmark doesn't seem very informative...

The issue is that we saw significant increases in inline cost. This very likely isn't just in one place but is true across the board, and I think I can explain some of why....

I think the real problem here is that we simply can't determine "what will fold" into an addressing mode this early in the pipeline. Looking at users I think is the wrong model, because those users are extremely likely to change as a result of inlining and the rest of the optimization pipeline. While it may be somewhat counter-intuitive that we get better results by *assuming* that a GEP will fold at some point into an addressing mode, currently that seems to be a better assumption than that the users seen when querying the cost are actually the correct users to analyze.

[junbuml]

I'm okay reverting this change if the regression caused by this change is significant and prevent many people from testing their compiler. As we go back to the original cost model, we optimistically assume that a GEP will fold into addressing mode later in the pipeline. In other words, the Free from getUserCost for a GEP is "expected to be cheap", not really free. So, don't we need to change the name from "Free" to "Cheap"?

[eastig]

The patch has caused a few regressions on Arm too. They are within 5%. We investigated some of them. For example, the unrolling is not applied. However the unrolling could figure out that some non-free GEPs are removed during optimisation. Maybe other passes have the similar problem. We currently need more precise cost model for inlining at Oz. However we started looking at the recently introduced TTI code size cost if we can use it.
At which optimisation level is the inlining affected? Could we fix the issues by updating the heuristics?

[apilipenko]

We also observed regressions caused by this change. In our case the change increases the perceived cost of a loop which in turn reduced the unrolling factor. Let me know if you need further details about the regressions.

include/llvm/Analysis/TargetTransformInfo.h

public:
   /// comments for a detailed explanation of the cost values.
   int getOperationCost(unsigned Opcode, Type *Ty, Type *OpTy = nullptr) const;
 
   /// \brief Estimate the cost of a GEP 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 GEP operation.
-  int getGEPCost(Type *PointeeType, const Value *Ptr,
+  int getGEPCost(const GEPOperator *GEP,
                  ArrayRef<const Value *> Operands) const;
 
   /// \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;
public:
   /// table.
   unsigned getEstimatedNumberOfCaseClusters(const SwitchInst &SI,
                                             unsigned &JTSize) const;
 
   /// \brief Estimate the cost of a given IR user when lowered.
   ///
   /// This can estimate the cost of either a ConstantExpr or Instruction when
   /// lowered. It has two primary advantages over the \c getOperationCost and
   /// \c getGEPCost above, and one significant disadvantage: it can only be
   /// used when the IR construct has already been formed.
   ///
   /// The advantages are that it can inspect the SSA use graph to reason more
   /// accurately about the cost. For example, all-constant-GEPs can often be
   /// folded into a load or other instruction, but if they are used in some
   /// other context they may not be folded. This routine can distinguish such
   /// cases.
   ///
private:
   std::unique_ptr<Concept> TTIImpl;
 };
 
 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,
+  virtual int getGEPCost(const GEPOperator *GEP,
                          ArrayRef<const Value *> Operands) = 0;
   virtual int getExtCost(const Instruction *I, const Value *Src) = 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,
public:
 
   const DataLayout &getDataLayout() const override {
     return Impl.getDataLayout();
   }
 
   int getOperationCost(unsigned Opcode, Type *Ty, Type *OpTy) override {
     return Impl.getOperationCost(Opcode, Ty, OpTy);
   }
-  int getGEPCost(Type *PointeeType, const Value *Ptr,
+  int getGEPCost(const GEPOperator *GEP,
                  ArrayRef<const Value *> Operands) override {
-    return Impl.getGEPCost(PointeeType, Ptr, Operands);
+    return Impl.getGEPCost(GEP, Operands);
   }
   int getExtCost(const Instruction *I, const Value *Src) override {
     return Impl.getExtCost(I, Src);
   }
   int getCallCost(FunctionType *FTy, int NumArgs) override {
     return Impl.getCallCost(FTy, NumArgs);
   }
   int getCallCost(const Function *F, int NumArgs) override {

include/llvm/Analysis/TargetTransformInfoImpl.h

public:
 
   unsigned getOperationCost(unsigned Opcode, Type *Ty, Type *OpTy) {
     switch (Opcode) {
     default:
       // By default, just classify everything as 'basic'.
       return TTI::TCC_Basic;
 
     case Instruction::GetElementPtr:
       llvm_unreachable("Use getGEPCost for GEP operations!");
 
     case Instruction::BitCast:
       assert(OpTy && "Cast instructions must provide the operand type");
       if (Ty == OpTy || (Ty->isPointerTy() && OpTy->isPointerTy()))
         // Identity and pointer-to-pointer casts are free.
         return TTI::TCC_Free;
 
       // Otherwise, the default basic cost is used.
case Instruction::Trunc:
       // shift-right of the same width).
       if (DL.isLegalInteger(DL.getTypeSizeInBits(Ty)))
         return TTI::TCC_Free;
 
       return TTI::TCC_Basic;
     }
   }
 
-  int getGEPCost(Type *PointeeType, const Value *Ptr,
-                 ArrayRef<const Value *> Operands) {
+  int getGEPCost(const GEPOperator *GEP, ArrayRef<const Value *> Operands) {
     // In the basic model, we just assume that all-constant GEPs will be folded
     // into their uses via addressing modes.
     for (unsigned Idx = 0, Size = Operands.size(); Idx != Size; ++Idx)
       if (!isa<Constant>(Operands[Idx]))
         return TTI::TCC_Basic;
 
     return TTI::TCC_Free;
   }
unsigned getCallCost(const Function *F, ArrayRef<const Value *> Arguments) {
     // Simply delegate to generic handling of the call.
     // FIXME: We should use instsimplify or something else to catch calls which
     // will constant fold with these arguments.
     return static_cast<T *>(this)->getCallCost(F, Arguments.size());
   }
 
   using BaseT::getGEPCost;
 
-  int getGEPCost(Type *PointeeType, const Value *Ptr,
-                 ArrayRef<const Value *> Operands) {
+  int getGEPCost(const GEPOperator *GEP, ArrayRef<const Value *> Operands) {
+    Type *PointeeType = GEP->getSourceElementType();
+    const Value *Ptr = GEP->getPointerOperand();
+
     const GlobalValue *BaseGV = nullptr;
     if (Ptr != nullptr) {
       // TODO: will remove this when pointers have an opaque type.
       assert(Ptr->getType()->getScalarType()->getPointerElementType() ==
                  PointeeType &&
              "explicit pointee type doesn't match operand's pointee type");
       BaseGV = dyn_cast<GlobalValue>(Ptr->stripPointerCasts());
     }
for (auto I = Operands.begin(); I != Operands.end(); ++I, ++GTI) {
       }
     }
 
     // Assumes the address space is 0 when Ptr is nullptr.
     unsigned AS =
         (Ptr == nullptr ? 0 : Ptr->getType()->getPointerAddressSpace());
     if (static_cast<T *>(this)->isLegalAddressingMode(
             TargetType, const_cast<GlobalValue *>(BaseGV), BaseOffset,
-            HasBaseReg, Scale, AS))
+            HasBaseReg, Scale, AS)) {
+      // Should check if the GEP is actually used in load / store instructions.
+      // For simplicity, we check only direct users of the GEP.
+      //
+      // FIXME: GEPs could also be folded away as a part of addressing mode in
+      // load/store instructions togetehr with other instructions (e.g., sext or
+      // other GEPs). Handling all such cases must be expensive to be performed
+      // in this function, so we stay conservative for now.
+      for (const User *U : GEP->users()) {
+        const Operator *UOP = cast<Operator>(U);
+        const Value *PointerOperand = nullptr;
+        if (auto *LI = dyn_cast<LoadInst>(UOP))
+          PointerOperand = LI->getPointerOperand();
+        else if (auto *SI = dyn_cast<StoreInst>(UOP))
+          PointerOperand = SI->getPointerOperand();
+
+        if ((!PointerOperand || PointerOperand != GEP) &&
+            !GEP->hasAllZeroIndices())
+          return TTI::TCC_Basic;
+      }
       return TTI::TCC_Free;
+    }
     return TTI::TCC_Basic;
   }
 
   using BaseT::getIntrinsicCost;
 
   unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                             ArrayRef<const Value *> Arguments) {
     // Delegate to the generic intrinsic handling code. This mostly provides an
     // opportunity for targets to (for example) special case the cost of
     // 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 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(),
+    if (const GEPOperator *GEP = dyn_cast<GEPOperator>(U))
+      return static_cast<T *>(this)->getGEPCost(GEP,
                                                 Operands.drop_front());
-    }
 
     if (auto CS = ImmutableCallSite(U)) {
       const Function *F = CS.getCalledFunction();
       if (!F) {
         // Just use the called value type.
         Type *FTy = CS.getCalledValue()->getType()->getPointerElementType();
         return static_cast<T *>(this)
             ->getCallCost(cast<FunctionType>(FTy), CS.arg_size());

include/llvm/CodeGen/BasicTTIImpl.h

bool isProfitableToHoist(Instruction *I) {
     return getTLI()->isProfitableToHoist(I);
   }
 
   bool isTypeLegal(Type *Ty) {
     EVT VT = getTLI()->getValueType(DL, Ty);
     return getTLI()->isTypeLegal(VT);
   }
 
-  int getGEPCost(Type *PointeeType, const Value *Ptr,
+  int getGEPCost(const GEPOperator *GEP,
                  ArrayRef<const Value *> Operands) {
-    return BaseT::getGEPCost(PointeeType, Ptr, Operands);
+    return BaseT::getGEPCost(GEP, Operands);
   }
 
   int getExtCost(const Instruction *I, const Value *Src) {
     if (getTLI()->isExtFree(I))
       return TargetTransformInfo::TCC_Free;
 
     if (isa<ZExtInst>(I) || isa<SExtInst>(I))
       if (const LoadInst *LI = dyn_cast<LoadInst>(Src))

lib/Analysis/TargetTransformInfo.cpp

int TargetTransformInfo::getCallCost(const Function *F,
   assert(Cost >= 0 && "TTI should not produce negative costs!");
   return Cost;
 }
 
 unsigned TargetTransformInfo::getInliningThresholdMultiplier() const {
   return TTIImpl->getInliningThresholdMultiplier();
 }
 
-int TargetTransformInfo::getGEPCost(Type *PointeeType, const Value *Ptr,
+int TargetTransformInfo::getGEPCost(const GEPOperator *GEP,
                                     ArrayRef<const Value *> Operands) const {
-  return TTIImpl->getGEPCost(PointeeType, Ptr, Operands);
+  return TTIImpl->getGEPCost(GEP, Operands);
 }
 
 int TargetTransformInfo::getExtCost(const Instruction *I,
                                     const Value *Src) const {
   return TTIImpl->getExtCost(I, Src);
 }
 
 int TargetTransformInfo::getIntrinsicCost(

lib/Transforms/Scalar/NaryReassociate.cpp

Instruction *NaryReassociatePass::tryReassociate(Instruction *I) {
   }
 }
 
 static bool isGEPFoldable(GetElementPtrInst *GEP,
                           const TargetTransformInfo *TTI) {
   SmallVector<const Value*, 4> Indices;
   for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I)
     Indices.push_back(*I);
-  return TTI->getGEPCost(GEP->getSourceElementType(), GEP->getPointerOperand(),
+  return TTI->getGEPCost(cast<GEPOperator>(GEP),
                          Indices) == TargetTransformInfo::TCC_Free;
 }
 
 Instruction *NaryReassociatePass::tryReassociateGEP(GetElementPtrInst *GEP) {
   // Not worth reassociating GEP if it is foldable.
   if (isGEPFoldable(GEP, TTI))
     return nullptr;
 

lib/Transforms/Scalar/StraightLineStrengthReduce.cpp

return (Basis.Ins != C.Ins && // skip the same instruction
           Basis.CandidateKind == C.CandidateKind);
 }
 
 static bool isGEPFoldable(GetElementPtrInst *GEP,
                           const TargetTransformInfo *TTI) {
   SmallVector<const Value*, 4> Indices;
   for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I)
     Indices.push_back(*I);
-  return TTI->getGEPCost(GEP->getSourceElementType(), GEP->getPointerOperand(),
+  return TTI->getGEPCost(cast<GEPOperator>(GEP),
                          Indices) == TargetTransformInfo::TCC_Free;
 }
 
 // Returns whether (Base + Index * Stride) can be folded to an addressing mode.
 static bool isAddFoldable(const SCEV *Base, ConstantInt *Index, Value *Stride,
                           TargetTransformInfo *TTI) {
   // Index->getSExtValue() may crash if Index is wider than 64-bit.
   return Index->getBitWidth() <= 64 &&

test/Analysis/CostModel/AArch64/gep.ll

 
 define i64 @test36(i64* %p) {
 ; CHECK-LABEL: test36
 ; CHECK: cost of 1 for instruction: {{.*}} getelementptr inbounds i64, i64*
   %a = getelementptr inbounds i64, i64* %p, i32 -512
   %v = load i64, i64* %a
   ret i64 %v
 }
+
+; CHECK-LABEL: test37
+; CHECK: cost of 1 for instruction:  {{.*}} = getelementptr inbounds i8*, i8**
+define i8 @test37(i64 %j, i8** readonly %P) {
+entry:
+  %arrayidx0 = getelementptr inbounds i8*, i8** %P, i64 %j
+  %l1 = call i8* @func(i8** %arrayidx0)
+  ret i8 0
+}
+
+; CHECK-LABEL: test38
+; CHECK: cost of 1 for instruction: {{.*}} = getelementptr inbounds i8*, i8**
+define i8 @test38(i8** readonly %P) {
+entry:
+  %arrayidx0 = getelementptr inbounds i8*, i8** %P, i64 10
+  %l1 = call i8* @func(i8** %arrayidx0)
+  ret i8 0
+}
+
+; CHECK-LABEL:test39
+; CHECK: cost of 0 for instruction: {{.*}} = getelementptr inbounds i8*, i8**
+define i8 @test39(i8** readonly %P) {
+entry:
+  %arrayidx0 = getelementptr inbounds i8*, i8** %P, i64 0
+  %l1 = call i8* @func(i8** %arrayidx0)
+  ret i8 0
+}
+
+; CHECK-LABEL:test40
+; CHECK: cost of 1 for instruction: {{.*}} = getelementptr inbounds i8*, i8**
+define i8** @test40(i8** readonly %P) {
+entry:
+  %arrayidx0 = getelementptr inbounds i8*, i8** %P, i64 10
+  ret i8** %arrayidx0
+}
+
+; CHECK-LABEL:test41
+; CHECK: cost of 1 for instruction: {{.*}} = getelementptr inbounds i8, i8*
+define i8 @test41(i8* %V, i8** readonly %P) {
+entry:
+  %arrayidx0 = getelementptr inbounds i8, i8* %V, i64 10
+  store i8* %arrayidx0, i8** %P
+  ret i8 0
+}
+
+declare i8* @func(i8**)

test/Analysis/CostModel/X86/vector_gep.ll

 ; RUN: opt < %s  -cost-model -analyze -mtriple=x86_64-linux-unknown-unknown -mattr=+avx512f | FileCheck %s
 
 %struct.S = type { [1000 x i32] }
 
 
 declare <4 x i32> @llvm.masked.gather.v4i32.v4p0i32(<4 x i32*>, i32, <4 x i1>, <4 x i32>)
 
 define <4 x i32> @foov(<4 x %struct.S*> %s, i64 %base){
   %temp = insertelement <4 x i64> undef, i64 %base, i32 0
   %vector = shufflevector <4 x i64> %temp, <4 x i64> undef, <4 x i32> zeroinitializer
-;CHECK: cost of 0 for instruction: {{.*}} getelementptr inbounds %struct.S
+;CHECK: cost of 1 for instruction: {{.*}} getelementptr inbounds %struct.S
   %B = getelementptr inbounds %struct.S, <4 x %struct.S*> %s, <4 x i32> zeroinitializer, <4 x i32> zeroinitializer
-;CHECK: cost of 0 for instruction: {{.*}} getelementptr inbounds [1000 x i32]
+;CHECK: cost of 1 for instruction: {{.*}} getelementptr inbounds [1000 x i32]
   %arrayidx = getelementptr inbounds [1000 x i32], <4 x [1000 x i32]*> %B, <4 x i64> zeroinitializer, <4 x i64> %vector
   %res = call <4 x i32> @llvm.masked.gather.v4i32.v4p0i32(<4 x i32*> %arrayidx, i32 4, <4 x i1> <i1 true, i1 true, i1 true, i1 true>, <4 x i32> undef)
   ret <4 x i32> %res
 }