Teach InlineCost about address spaces

[bjope]

Summary

I basically copied this patch from here: https://reviews.llvm.org/D1251
But I skipped some of the refactoring to make the patch more clean.

The new outer3/inner3 test case in ptr-diff.ll triggers the following assert without this patch:
lib/IR/Constants.cpp:1834: static llvm::Constant *llvm::ConstantExpr::getCompare(unsigned short, llvm::Constant *, llvm::Constant *, bool): Assertion `C1->getType() == C2->getType() && "Op types should be identical!"' failed.

The other new test cases makes sure that there is code coverage for all modifications in InlineCost.cpp (getting different values due to not fetching sizes for address space zero). I only guarantee code coverage for those tests. The tests are not written in a way that they would break if not having the corrections in InlineCost.cpp. I found it quite hard to fine tune the tests into getting different results based on the pointer sizes (except for the test case where we hit an assert if not teaching InlineCost about address spaces).

[arsenm]

LGTM

[arsenm]

Actually the test seems to just cover the ptrtoint case. Need some for the GEP cases as well

[bjope]

Added some more tests.

[bjope]

In D40455#936215, @arsenm wrote:

Actually the test seems to just cover the ptrtoint case. Need some for the GEP cases as well

So, are the new test cases enough?

[bjope]

ping

[arsenm]

LGTM

[skatkov]

Dear Bjorn, your added test in byvall.ll expose the problem in inliner causing an assert.

Specifically if I excerpt you test in separate file and run:
$ opt -S -inline -instcombine test.ll
I've got a
opt: ../../lib/Analysis/ValueTracking.cpp:1551: void computeKnownBits(const llvm::Value*, llvm::KnownBits&, unsigned int, const {anonymous}::Query&): Assertion `Q.DL.getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth && "V and Known should have same BitWidth"' failed.

The reason of this is that %p is substituted with
%d = alloca %struct.S1, align 8
which is from addrspace(0) and has a different pointer size than %p.

I'm far from thinking that your patch is causing this issue but probably it is long standing issue in inliner. But it causes the crash in our custom pipeline.
I do not want to revert your patch if you can quickly update the test or simply revert the test itself.

A separate bug against inliner can be filed...

Does it make sense to you?

[bjope]

In D40455#971926, @skatkov wrote:

Dear Bjorn, your added test in byvall.ll expose the problem in inliner causing an assert.

Specifically if I excerpt you test in separate file and run:
$ opt -S -inline -instcombine test.ll
I've got a
opt: ../../lib/Analysis/ValueTracking.cpp:1551: void computeKnownBits(const llvm::Value*, llvm::KnownBits&, unsigned int, const {anonymous}::Query&): Assertion `Q.DL.getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth && "V and Known should have same BitWidth"' failed.

The reason of this is that %p is substituted with
%d = alloca %struct.S1, align 8
which is from addrspace(0) and has a different pointer size than %p.

I'm far from thinking that your patch is causing this issue but probably it is long standing issue in inliner. But it causes the crash in our custom pipeline.
I do not want to revert your patch if you can quickly update the test or simply revert the test itself.

A separate bug against inliner can be filed...

Does it make sense to you?

Ok. I'll take a look at it.

[skatkov]

Thank you very much!

[bjope]

In D40455#971944, @bjope wrote:

In D40455#971926, @skatkov wrote:

Dear Bjorn, your added test in byvall.ll expose the problem in inliner causing an assert.

Specifically if I excerpt you test in separate file and run:
$ opt -S -inline -instcombine test.ll
I've got a
opt: ../../lib/Analysis/ValueTracking.cpp:1551: void computeKnownBits(const llvm::Value*, llvm::KnownBits&, unsigned int, const {anonymous}::Query&): Assertion `Q.DL.getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth && "V and Known should have same BitWidth"' failed.

The reason of this is that %p is substituted with
%d = alloca %struct.S1, align 8
which is from addrspace(0) and has a different pointer size than %p.

I'm far from thinking that your patch is causing this issue but probably it is long standing issue in inliner. But it causes the crash in our custom pipeline.
I do not want to revert your patch if you can quickly update the test or simply revert the test itself.

A separate bug against inliner can be filed...

Does it make sense to you?

Ok. I'll take a look at it.

Here is an attempt to workaround the problem: https://reviews.llvm.org/D41898

llvm/trunk/lib/Analysis/InlineCost.cpp

void CallAnalyzer::disableLoadElimination() {
   }
 }
 
 /// \brief Accumulate a constant GEP offset into an APInt if possible.
 ///
 /// Returns false if unable to compute the offset for any reason. Respects any
 /// simplified values known during the analysis of this callsite.
 bool CallAnalyzer::accumulateGEPOffset(GEPOperator &GEP, APInt &Offset) {
-  unsigned IntPtrWidth = DL.getPointerSizeInBits();
+  unsigned IntPtrWidth = DL.getPointerTypeSizeInBits(GEP.getType());
   assert(IntPtrWidth == Offset.getBitWidth());
 
   for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
        GTI != GTE; ++GTI) {
     ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand());
     if (!OpC)
       if (Constant *SimpleOp = SimplifiedValues.lookup(GTI.getOperand()))
         OpC = dyn_cast<ConstantInt>(SimpleOp);

 }
 
 bool CallAnalyzer::visitPHI(PHINode &I) {
   // FIXME: We need to propagate SROA *disabling* through phi nodes, even
   // though we don't want to propagate it's bonuses. The idea is to disable
   // SROA if it *might* be used in an inappropriate manner.
 
   // Phi nodes are always zero-cost.
-
-  APInt ZeroOffset = APInt::getNullValue(DL.getPointerSizeInBits());
+  // FIXME: Pointer sizes may differ between different address spaces, so do we
+  // need to use correct address space in the call to getPointerSizeInBits here?
+  // Or could we skip the getPointerSizeInBits call completely? As far as I can
+  // see the ZeroOffset is used as a dummy value, so we can probably use any
+  // bit width for the ZeroOffset?
+  APInt ZeroOffset = APInt::getNullValue(DL.getPointerSizeInBits(0));
   bool CheckSROA = I.getType()->isPointerTy();
 
   // Track the constant or pointer with constant offset we've seen so far.
   Constant *FirstC = nullptr;
   std::pair<Value *, APInt> FirstBaseAndOffset = {nullptr, ZeroOffset};
   Value *FirstV = nullptr;
 
   for (unsigned i = 0, e = I.getNumIncomingValues(); i != e; ++i) {
bool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) {
   if (simplifyInstruction(I, [&](SmallVectorImpl<Constant *> &COps) {
         return ConstantExpr::getPtrToInt(COps[0], I.getType());
       }))
     return true;
 
   // Track base/offset pairs when converted to a plain integer provided the
   // integer is large enough to represent the pointer.
   unsigned IntegerSize = I.getType()->getScalarSizeInBits();
-  if (IntegerSize >= DL.getPointerSizeInBits()) {
+  unsigned AS = I.getOperand(0)->getType()->getPointerAddressSpace();
+  if (IntegerSize >= DL.getPointerSizeInBits(AS)) {
     std::pair<Value *, APInt> BaseAndOffset =
         ConstantOffsetPtrs.lookup(I.getOperand(0));
     if (BaseAndOffset.first)
       ConstantOffsetPtrs[&I] = BaseAndOffset;
   }
 
   // This is really weird. Technically, ptrtoint will disable SROA. However,
   // unless that ptrtoint is *used* somewhere in the live basic blocks after
if (simplifyInstruction(I, [&](SmallVectorImpl<Constant *> &COps) {
         return ConstantExpr::getIntToPtr(COps[0], I.getType());
       }))
     return true;
 
   // Track base/offset pairs when round-tripped through a pointer without
   // modifications provided the integer is not too large.
   Value *Op = I.getOperand(0);
   unsigned IntegerSize = Op->getType()->getScalarSizeInBits();
-  if (IntegerSize <= DL.getPointerSizeInBits()) {
+  if (IntegerSize <= DL.getPointerTypeSizeInBits(I.getType())) {
     std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Op);
     if (BaseAndOffset.first)
       ConstantOffsetPtrs[&I] = BaseAndOffset;
   }
 
   // "Propagate" SROA here in the same manner as we do for ptrtoint above.
   Value *SROAArg;
   DenseMap<Value *, int>::iterator CostIt;

 /// This strips all constant offsets off of V, leaving it the base pointer, and
 /// accumulates the total constant offset applied in the returned constant. It
 /// returns 0 if V is not a pointer, and returns the constant '0' if there are
 /// no constant offsets applied.
 ConstantInt *CallAnalyzer::stripAndComputeInBoundsConstantOffsets(Value *&V) {
   if (!V->getType()->isPointerTy())
     return nullptr;
 
-  unsigned IntPtrWidth = DL.getPointerSizeInBits();
+  unsigned AS = V->getType()->getPointerAddressSpace();
+  unsigned IntPtrWidth = DL.getPointerSizeInBits(AS);
   APInt Offset = APInt::getNullValue(IntPtrWidth);
 
   // Even though we don't look through PHI nodes, we could be called on an
   // instruction in an unreachable block, which may be on a cycle.
   SmallPtrSet<Value *, 4> Visited;
   Visited.insert(V);
   do {
     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
       if (!GEP->isInBounds() || !accumulateGEPOffset(*GEP, Offset))
         return nullptr;
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast) {
       V = cast<Operator>(V)->getOperand(0);
     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
       if (GA->isInterposable())
         break;
       V = GA->getAliasee();
     } else {
       break;
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   } while (Visited.insert(V).second);
 
-  Type *IntPtrTy = DL.getIntPtrType(V->getContext());
+  Type *IntPtrTy = DL.getIntPtrType(V->getContext(), AS);
   return cast<ConstantInt>(ConstantInt::get(IntPtrTy, Offset));
 }
 
 /// \brief Find dead blocks due to deleted CFG edges during inlining.
 ///
 /// If we know the successor of the current block, \p CurrBB, has to be \p
 /// NextBB, the other successors of \p CurrBB are dead if these successors have
 /// no live incoming CFG edges.  If one block is found to be dead, we can

 int llvm::getCallsiteCost(CallSite CS, const DataLayout &DL) {
   int Cost = 0;
   for (unsigned I = 0, E = CS.arg_size(); I != E; ++I) {
     if (CS.isByValArgument(I)) {
       // We approximate the number of loads and stores needed by dividing the
       // size of the byval type by the target's pointer size.
       PointerType *PTy = cast<PointerType>(CS.getArgument(I)->getType());
       unsigned TypeSize = DL.getTypeSizeInBits(PTy->getElementType());
-      unsigned PointerSize = DL.getPointerSizeInBits();
+      unsigned AS = PTy->getAddressSpace();
+      unsigned PointerSize = DL.getPointerSizeInBits(AS);
       // Ceiling division.
       unsigned NumStores = (TypeSize + PointerSize - 1) / PointerSize;
 
       // If it generates more than 8 stores it is likely to be expanded as an
       // inline memcpy so we take that as an upper bound. Otherwise we assume
       // one load and one store per word copied.
       // FIXME: The maxStoresPerMemcpy setting from the target should be used
       // here instead of a magic number of 8, but it's not available via

llvm/trunk/test/Transforms/Inline/byval.ll

 ; RUN: opt < %s -inline -S | FileCheck %s
 ; RUN: opt < %s -passes='cgscc(inline)' -S | FileCheck %s
 
+target datalayout = "p:32:32-p1:64:64-p2:16:16-n16:32:64"
+
 ; Inlining a byval struct should cause an explicit copy into an alloca.
 
   %struct.ss = type { i32, i64 }
 @.str = internal constant [10 x i8] c"%d, %lld\0A\00"    ; <[10 x i8]*> [#uses=1]
 
 define internal void @f(%struct.ss* byval  %b) nounwind  {
 entry:
   %tmp = getelementptr %struct.ss, %struct.ss* %b, i32 0, i32 0    ; <i32*> [#uses=2]

 entry:
   tail call void @f5(%struct.S0* byval align 4 @b)
   %0 = load i32, i32* @a, align 4
   ret i32 %0
 ; CHECK: @test5()
 ; CHECK: store i32 0, i32* getelementptr inbounds (%struct.S0, %struct.S0* @b, i64 0, i32 0), align 4
 ; CHECK-NOT: load i32, i32* getelementptr inbounds (%struct.S0, %struct.S0* @b, i64 0, i32 0), align 4
 }
+
+%struct.S1 = type { i32 }
+
+@d = addrspace(1) global %struct.S1 { i32 1 }, align 4
+@c = common addrspace(1) global i32 0, align 4
+
+define internal void @f5_as1(%struct.S1 addrspace(1)* byval nocapture readonly align 4 %p) {
+entry:
+  store i32 0, i32 addrspace(1)* getelementptr inbounds (%struct.S1, %struct.S1 addrspace(1)* @d, i64 0, i32 0), align 4
+  %f2 = getelementptr inbounds %struct.S1, %struct.S1 addrspace(1)* %p, i64 0, i32 0
+  %0 = load i32, i32 addrspace(1)* %f2, align 4
+  store i32 %0, i32 addrspace(1)* @c, align 4
+  ret void
+}
+
+define i32 @test5_as1() {
+entry:
+  tail call void @f5_as1(%struct.S1 addrspace(1)* byval align 4 @d)
+  %0 = load i32, i32 addrspace(1)* @c, align 4
+  ret i32 %0
+; CHECK: @test5_as1()
+; CHECK: store i32 0, i32 addrspace(1)* getelementptr inbounds (%struct.S1, %struct.S1 addrspace(1)* @d, i64 0, i32 0), align 4
+; CHECK-NOT: load i32, i32 addrspace(1)* getelementptr inbounds (%struct.S1, %struct.S1 addrspace(1)* @d, i64 0, i32 0), align 4
+}

llvm/trunk/test/Transforms/Inline/ptr-diff.ll

 then:
   ret i32 3
 
 else:
   %t = load i32, i32* %begin
   ret i32 %t
 }
 
+define i32 @outer1_as1(i32 addrspace(1)* %ptr) {
+; CHECK-LABEL: @outer1_as1(
+; CHECK-NOT: call
+; CHECK: ret i32
+  %ptr1 = getelementptr inbounds i32, i32 addrspace(1)* %ptr, i32 0
+  %ptr2 = getelementptr inbounds i32, i32 addrspace(1)* %ptr, i32 42
+  %result = call i32 @inner1_as1(i32 addrspace(1)* %ptr1, i32 addrspace(1)* %ptr2)
+  ret i32 %result
+}
+
+; Make sure that the address space's larger size makes the ptrtoints
+; not no-ops preventing inlining
+define i32 @inner1_as1(i32 addrspace(1)* %begin, i32 addrspace(1)* %end) {
+  %begin.i = ptrtoint i32 addrspace(1)* %begin to i32
+  %end.i = ptrtoint i32 addrspace(1)* %end to i32
+  %distance = sub i32 %end.i, %begin.i
+  %icmp = icmp sle i32 %distance, 42
+  br i1 %icmp, label %then, label %else
+
+then:
+  ret i32 3
+
+else:
+  %t = load i32, i32 addrspace(1)* %begin
+  ret i32 %t
+}
+
 define i32 @outer2(i32* %ptr) {
 ; Test that an inbounds GEP disables this -- it isn't safe in general as
 ; wrapping changes the behavior of lessthan and greaterthan comparisons.
 ; CHECK-LABEL: @outer2(
 ; CHECK: call i32 @inner2
 ; CHECK: ret i32
 
   %ptr1 = getelementptr i32, i32* %ptr, i32 0

 then:
   ret i32 3
 
 else:
   %t = load i32, i32* %begin
   ret i32 %t
 }
 
+define i32 @outer3(i16* addrspace(1)* %ptr) {
+; CHECK-LABEL: @outer3(
+; CHECK-NOT: call i32
+; CHECK: ret i32 3
+; CHECK-LABEL: @inner3(
+  %result = call i32 @inner3(i16* addrspace(1)* %ptr)
+  ret i32 %result
+}
+
+define i32 @inner3(i16* addrspace(1)* %ptr) {
+  call void @extern()
+  %ptr.i = ptrtoint i16* addrspace(1)* %ptr to i64
+  %distance = sub i64 %ptr.i, %ptr.i
+  %icmp = icmp eq i64 %distance, 0
+  br i1 %icmp, label %then, label %else
+
+then:
+  ret i32 3
+
+else:
+  ret i32 5
+}
+
+
 ; The inttoptrs are free since it is a smaller integer to a larger
 ; pointer size
 define i32 @inttoptr_free_cost(i32 %a, i32 %b, i32 %c) {
   call void @extern()
   %p1 = inttoptr i32 %a to i32 addrspace(1)*
   %p2 = inttoptr i32 %b to i32 addrspace(1)*
   %p3 = inttoptr i32 %c to i32 addrspace(1)*
   %t1 = load i32, i32 addrspace(1)* %p1

 define i32 @inttoptr_cost_smaller_ptr_user(i32 %begin, i32 %end) {
 ; CHECK-LABEL: @inttoptr_cost_smaller_ptr_user(
 ; CHECK: call i32
   %x = call i32 @inttoptr_cost_smaller_ptr(i32 %begin, i32 %end, i32 9)
   ret i32 %x
 }
 
 declare void @extern()
 No newline at end of file