Teach InlineCost about address spaces

[arsenm]

Summary

Depends on

http://llvm-reviews.chandlerc.com/D1114
and
http://llvm-reviews.chandlerc.com/D1250

[bjope]

Does anyone remember why this has been "abandoned" (still not finished after four years being in need for review)?

I found some problem that seems to go away if we teach InlineCost about address spaces.

If we add the following test to test/Transforms/Inline/ptr-diff.ll then I see asserts like this:
opt: ../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.
#0 0x0000000001d7f4c4 PrintStackTraceSignalHandler(void*) (../master/build-all/bin/opt+0x1d7f4c4)
#1 0x0000000001d7fc36 SignalHandler(int) (../master/build-all/bin/opt+0x1d7fc36)
#2 0x00007f7b0a120810 restore_rt (/lib64/libpthread.so.0+0xf810)
#3 0x00007f7b092cb875 GI_raise (/lib64/libc.so.6+0x32875)
#4 0x00007f7b092cce51 GI_abort (/lib64/libc.so.6+0x33e51)
#5 0x00007f7b092c4740 GI___assert_fail (/lib64/libc.so.6+0x2b740)
#6 0x00000000017d098a llvm::ConstantExpr::getCompare(unsigned short, llvm::Constant*, llvm::Constant*, bool) (../master/build-all/bin/opt+0x17d098a)
#7 0x000000000133bb8f (anonymous namespace)::CallAnalyzer::visitCmpInst(llvm::CmpInst&) (../master/build-all/bin/opt+0x133bb8f)
#8 0x000000000133662b llvm::InstVisitor<(anonymous namespace)::CallAnalyzer, bool>::visit(llvm::Instruction&) (../master/build-all/bin/opt+0x133662b)
#9 0x0000000001334fc4 (anonymous namespace)::CallAnalyzer::analyzeCall(llvm::CallSite) (../master/build-all/bin/opt+0x1334fc4)
#10 0x0000000001333848 llvm::getInlineCost(llvm::CallSite, llvm::Function*, llvm::InlineParams const&, llvm::TargetTransformInfo&, std::function<llvm::AssumptionCache& (llvm::Function&)>&, llvm::Optional<llvm::function_ref<llvm::BlockFrequencyInfo& (llvm::Function&)> >, llvm::ProfileSummaryInfo*, llvm::OptimizationRemarkEmitter*) (../master/build-all/bin/opt+0x1333848)
#11 0x000000000133345a llvm::getInlineCost(llvm::CallSite, llvm::InlineParams const&, llvm::TargetTransformInfo&, std::function<llvm::AssumptionCache& (llvm::Function&)>&, llvm::Optional<llvm::function_ref<llvm::BlockFrequencyInfo& (llvm::Function&)> >, llvm::ProfileSummaryInfo*, llvm::OptimizationRemarkEmitter*) (../master/build-all/bin/opt+0x133345a)
#12 0x0000000001939c3f (anonymous namespace)::SimpleInliner::getInlineCost(llvm::CallSite) (../master/build-all/bin/opt+0x1939c3f)
#13 0x000000000194065e shouldInline(llvm::CallSite, llvm::function_ref<llvm::InlineCost (llvm::CallSite)>, llvm::OptimizationRemarkEmitter&) (../master/build-all/bin/opt+0x194065e)
#14 0x000000000193af98 inlineCallsImpl(llvm::CallGraphSCC&, llvm::CallGraph&, std::function<llvm::AssumptionCache& (llvm::Function&)>, llvm::ProfileSummaryInfo*, llvm::TargetLibraryInfo&, bool, llvm::function_ref<llvm::InlineCost (llvm::CallSite)>, llvm::function_ref<llvm::AAResults& (llvm::Function&)>, llvm::ImportedFunctionsInliningStatistics&) (../master/build-all/bin/opt+0x193af98)
#15 0x000000000193a23a llvm::LegacyInlinerBase::inlineCalls(llvm::CallGraphSCC&) (../master/build-all/bin/opt+0x193a23a)
#16 0x000000000193a002 llvm::LegacyInlinerBase::runOnSCC(llvm::CallGraphSCC&) (../master/build-all/bin/opt+0x193a002)
#17 0x00000000012e330b (anonymous namespace)::CGPassManager::runOnModule(llvm::Module&) (../master/build-all/bin/opt+0x12e330b)
#18 0x000000000187f8e8 llvm::legacy::PassManagerImpl::run(llvm::Module&) (../master/build-all/bin/opt+0x187f8e8)
#19 0x000000000070411f main (../master/build-all/bin/opt+0x70411f)

Here is the test to add to test/Transforms/Inline/ptr-diff.ll:

;-------------------------------------------------------------
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
}
;-------------------------------------------------------------

[bjope]

If nobody remembers why this very old patch never was landed, then I guess I'll make a new attempt as it would avoid the asserts that I've seen.
And it is also one step towards getting rid of the default arguments in DataLayout::getPointerSizeInBits(unsigned AS = 0) , marked as a FIXME in DataLayout.h.

[bjope]

I believe this review is superseded by https://reviews.llvm.org/rL321809, so it can probably be abandoned now.

lib/Analysis/IPA/InlineCost.cpp

 /// \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) {
   if (!TD)
     return false;
 
-  unsigned IntPtrWidth = TD->getPointerSizeInBits();
+  unsigned IntPtrWidth = TD->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::visitBitCast(BitCastInst &I) {
   if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
     SROAArgValues[&I] = SROAArg;
 
   // Bitcasts are always zero cost.
   return true;
 }
 
 bool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) {
+  Type *Ty = I.getType();
+  Value *Op = I.getOperand(0);
   // Propagate constants through ptrtoint.
-  Constant *COp = dyn_cast<Constant>(I.getOperand(0));
+  Constant *COp = dyn_cast<Constant>(Op);
   if (!COp)
-    COp = SimplifiedValues.lookup(I.getOperand(0));
+    COp = SimplifiedValues.lookup(Op);
   if (COp)
-    if (Constant *C = ConstantExpr::getPtrToInt(COp, I.getType())) {
+    if (Constant *C = ConstantExpr::getPtrToInt(COp, Ty)) {
       SimplifiedValues[&I] = C;
       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 (TD && IntegerSize == TD->getPointerSizeInBits()) {
-    std::pair<Value *, APInt> BaseAndOffset
-      = ConstantOffsetPtrs.lookup(I.getOperand(0));
-    if (BaseAndOffset.first)
+  unsigned IntegerSize = Ty->getScalarSizeInBits();
+  unsigned AS = Op->getType()->getPointerAddressSpace();
+  if (TD && IntegerSize == TD->getPointerSizeInBits(AS)) {
+    std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Op);
+    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
   // inlining, it will be nuked, and SROA should proceed. All of the uses which
   // would block SROA would also block SROA if applied directly to a pointer,
   // and so we can just add the integer in here. The only places where SROA is
   // preserved either cannot fire on an integer, or won't in-and-of themselves
   // disable SROA (ext) w/o some later use that we would see and disable.
   Value *SROAArg;
   DenseMap<Value *, int>::iterator CostIt;
-  if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
+  if (lookupSROAArgAndCost(Op, SROAArg, CostIt))
     SROAArgValues[&I] = SROAArg;
 
   return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
 }
 
 bool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) {
   // Propagate constants through ptrtoint.
   Constant *COp = dyn_cast<Constant>(I.getOperand(0));
   if (!COp)
     COp = SimplifiedValues.lookup(I.getOperand(0));
   if (COp)
     if (Constant *C = ConstantExpr::getIntToPtr(COp, I.getType())) {
       SimplifiedValues[&I] = C;
       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 (TD && IntegerSize == TD->getPointerSizeInBits()) {
+  if (TD && IntegerSize == TD->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 (!TD || !V->getType()->isPointerTy())
     return 0;
 
-  unsigned IntPtrWidth = TD->getPointerSizeInBits();
+  unsigned AS = V->getType()->getPointerAddressSpace();
+  unsigned IntPtrWidth = TD->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 0;
       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->mayBeOverridden())
         break;
       V = GA->getAliasee();
     } else {
       break;
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   } while (Visited.insert(V));
 
-  Type *IntPtrTy = TD->getIntPtrType(V->getContext());
+  Type *IntPtrTy = TD->getIntPtrType(V->getContext(), AS);
   return cast<ConstantInt>(ConstantInt::get(IntPtrTy, Offset));
 }
 
 /// \brief Analyze a call site for potential inlining.
 ///
 /// Returns true if inlining this call is viable, and false if it is not
 /// viable. It computes the cost and adjusts the threshold based on numerous
 /// factors and heuristics. If this method returns false but the computed cost
bool CallAnalyzer::analyzeCall(CallSite CS) {
   // Give out bonuses per argument, as the instructions setting them up will
   // be gone after inlining.
   for (unsigned I = 0, E = CS.arg_size(); I != E; ++I) {
     if (TD && 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 = TD->getTypeSizeInBits(PTy->getElementType());
-      unsigned PointerSize = TD->getPointerSizeInBits();
+      unsigned AS = PTy->getAddressSpace();
+      unsigned PointerSize = TD->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
for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
 
     // Handle the terminator cost here where we can track returns and other
     // function-wide constructs.
     TerminatorInst *TI = BB->getTerminator();
 
     // We never want to inline functions that contain an indirectbr.  This is
     // incorrect because all the blockaddress's (in static global initializers
     // for example) would be referring to the original function, and this
-    // indirect jump would jump from the inlined copy of the function into the 
+    // indirect jump would jump from the inlined copy of the function into the
     // original function which is extremely undefined behavior.
     // FIXME: This logic isn't really right; we can safely inline functions
     // with indirectbr's as long as no other function or global references the
     // blockaddress of a block within the current function.  And as a QOI issue,
     // if someone is using a blockaddress without an indirectbr, and that
     // reference somehow ends up in another function or global, we probably
     // don't want to inline this function.
     if (isa<IndirectBrInst>(TI))
for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
     // inlining.
     if (SingleBB && TI->getNumSuccessors() > 1) {
       // Take off the bonus we applied to the threshold.
       Threshold -= SingleBBBonus;
       SingleBB = false;
     }
   }
 
-  // If this is a noduplicate call, we can still inline as long as 
+  // If this is a noduplicate call, we can still inline as long as
   // inlining this would cause the removal of the caller (so the instruction
   // is not actually duplicated, just moved).
   if (!OnlyOneCallAndLocalLinkage && ContainsNoDuplicateCall)
     return false;
 
   Threshold += VectorBonus;
 
   return Cost < Threshold;

test/Transforms/Inline/ptr-diff.ll

 ; RUN: opt -inline < %s -S -o - -inline-threshold=10 | FileCheck %s
 
-target datalayout = "p:32:32"
+target datalayout = "p:32:32-p1:64:64-n32"
 
 define i32 @outer1() {
 ; CHECK-LABEL: @outer1(
 ; CHECK-NOT: call
 ; CHECK: ret i32
 
   %ptr = alloca i32
   %ptr1 = getelementptr inbounds i32* %ptr, i32 0

 then:
   ret i32 3
 
 else:
   %t = load i32* %begin
   ret i32 %t
 }
 
+define i32 @outer1_as1(i32 addrspace(1)* %ptr) {
+; CHECK-LABEL: @outer1_as1(
+; CHECK: call
+; CHECK: ret i32
+  %ptr1 = getelementptr inbounds i32 addrspace(1)* %ptr, i32 0
+  %ptr2 = getelementptr inbounds 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 addrspace(1)* %begin
+  ret i32 %t
+}
+
 ; Make sure that assertion isn't hit when ptrtoint is used with an
 ; integer size different from the pointer size
 define i32 @outer1_ptrtoint_larger() {
 ; CHECK: @outer1_ptrtoint_larger
 ; CHECK: ret i32
 
   %ptr = alloca i32
   %ptr1 = getelementptr inbounds i32* %ptr, i64 0