[DataLayout] Add bit width of pointers to global values

[nhaehnle]

Summary

Together with leading known-zero bit tracking for getelementptr, this
recovers most of the code quality that was lost for AMDGPU's SI subtarget
with a previous commit.

AMDGPU has LDS (local) and GDS (region) address spaces that use 32 bit
pointers, even though the underlying memory is only 64 kiB, and therefore
pointers to global values always fit into 16 bits.

This recovers a lot of the code quality lost in "AMDGPU: Restrict DS
load/store vectorizing on SI".

Change-Id: Ic17f297b714039ea4988581b3abfafc57d11a6bd

[delena]

Can you use the "address space" to distinguish between global and local in Data Layout?

[bjope]

include/llvm/IR/DataLayout.h

340

Maybe remove the default here. There are comments about removing AS defaults for other methods here, and usually when someone does not provide the address space in the call it could be a hard to find fault.

[theraven]

include/llvm/IR/DataLayout.h

340

Agreed. The default value is useful for incrementally migrating consumers of APIs that didn't know about address spaces, but for a new API it doesn't make sense.

lib/Analysis/ValueTracking.cpp

1344

Does this correctly handle the case of invalid pointers being created as temporary values? In CHERI, we saw a few cases where, after reassociation, you ended up with IR that took a pointer out of bounds in one calculation and then brought it back in as a result of the next one before dereferencing. This should perhaps be restricted to inbounds GEPs (or is it already and I'm missing the check)?

lib/IR/DataLayout.cpp

311

Please can we have a comment that we're assuming 8-bit bytes here? A few out-of-tree targets are trying to make things work with different addressable sizes and it's polite to leave them a signpost that this is a thing that they'll need to change.

[nhaehnle]

• no default value for address space
• add comment about 8-bit bytes

[nhaehnle]

Thank you all for taking a look.

In D53162#1263094, @delena wrote:

Can you use the "address space" to distinguish between global and local in Data Layout?

We may be talking past each other. This is about GlobalValues (i.e. global variables, e.g. file-level variables in C/C++), not about global vs. local. Those could exist in any address space.

include/llvm/IR/DataLayout.h

340

That makes a lot of sense, thanks for the history lesson :)

lib/Analysis/ValueTracking.cpp

1344

The intention of this code is to just not care about the in- or out-of-boundedness of GEPs, so yes, it should handle temporary invalid pointers correctly (though maybe over-conservatively).

To think this through:

• GEP indices are always supposed to be treated as signed integers. If the index may be negative, setting LeadZ = 0 is conservatively correct: we make no claim about leading zeros at all anymore in this case.
• Zero indices don't actually change the pointer value, so need no change of LeadZ.
• Non-zero but positive indices change the pointer value by adding some offset. The intuition behind the code here is that the base pointer (or rather, the base pointer plus offsets from earlier GEP indices) fits into some number of bits, and the offset that we're adding in this GEP index fits into some number of bits, so their some fits into max(those numbers) + 1. Though the code itself is expressed in number of leading zeros as opposed to number of bits needed to represent the (unsigned) pointer value.

It seems like some tighter guarantees could be made for inbounds GEPs, but this code does not attempt that.

Does that make sense to you?

[theraven]

lib/Analysis/ValueTracking.cpp

1344

Sounds good, thanks for the clarification.

[efriedma]

I'm not sure it makes sense to put this information in the DataLayout.

The number of bits required to represent the address of a global isn't really a fundamental aspect of the target; it can vary based on the code generation options used. For example, on x86-64, non-position-independent code can assume the address of a global fits into 32 bits, but we don't want to change the datalayout based on whether the user passed -fPIC. And even if it is fundamental on some targets, it doesn't seem important enough to include in the datalayout; no target-independent transforms care about known bits for pointers beyond figuring out the alignment of a pointer.

[nhaehnle]

no target-independent transforms care about known bits for pointers beyond figuring out the alignment of a pointer.

The other patch in this stack (D53160) cares about it. And sure, that patch is target-dependent, but it's based on the target-independent computeKnownBits. The canonical way that this kind of information is passed into computeKnownBits is via the DataLayout. The alternative would be to start passing some separate target-info into computeKnownBits, which seems way uglier to me.

So yeah, I hear your complaint, but unless you can come up with a constructive alternative, this patch is the way to go.

[arsenm]

I also think this is pretty weird for the datalayout. An optional TTI parameter that improves computeKnownBits seems natural to me? We could also handle target intrinsics more easily with that

[nhaehnle]

I'm dropping this change. We don't need it anymore, given changes to the parent revision.

docs/LangRef.rst

``P<address space>``
     Harvard architectures can use this to specify what space LLVM
     should place things such as functions into. If omitted, the
     program memory space defaults to the default address space of 0,
     which corresponds to a Von Neumann architecture that has code
     and data in the same space.
 ``A<address space>``
     Specifies the address space of objects created by '``alloca``'.
     Defaults to the default address space of 0.
-``p[n]:<size>:<abi>:<pref>:<idx>``
+``p[n]:<size>:<abi>[:<pref>[:<idx>[:<global>]]]``
     This specifies the *size* of a pointer and its ``<abi>`` and
     ``<pref>``\erred alignments for address space ``n``. The fourth parameter
     ``<idx>`` is a size of index that used for address calculation. If not
     specified, the default index size is equal to the pointer size. All sizes
-    are in bits. The address space, ``n``, is optional, and if not specified,
+    are in bits. ``<global>`` is the number of bits in addresses of global
+    values. The high bits are assumed to be 0. If not specified, this is equal
+    to pointer size.
+    The address space, ``n``, is optional, and if not specified,
     denotes the default address space 0. The value of ``n`` must be
     in the range [1,2^23).
 ``i<size>:<abi>:<pref>``
     This specifies the alignment for an integer type of a given bit
     ``<size>``. The value of ``<size>`` must be in the range [1,2^23).
 ``v<size>:<abi>:<pref>``
     This specifies the alignment for a vector type of a given bit
     ``<size>``.

include/llvm/IR/DataLayout.h

 /// \note The unusual order of elements in the structure attempts to reduce
 /// padding and make the structure slightly more cache friendly.
 struct PointerAlignElem {
   unsigned ABIAlign;
   unsigned PrefAlign;
   uint32_t TypeByteWidth;
   uint32_t AddressSpace;
   uint32_t IndexWidth;
+  uint32_t GlobalBitWidth;
 
   /// Initializer
   static PointerAlignElem get(uint32_t AddressSpace, unsigned ABIAlign,
                               unsigned PrefAlign, uint32_t TypeByteWidth,
-                              uint32_t IndexWidth);
+                              uint32_t IndexWidth, uint32_t GlobalBitWidth);
 
   bool operator==(const PointerAlignElem &rhs) const;
 };
 
 /// A parsed version of the target data layout string in and methods for
 /// querying it.
 ///
 /// The target data layout string is specified *by the target* - a frontend
private:
   SmallVector<unsigned, 8> NonIntegralAddressSpaces;
 
   void setAlignment(AlignTypeEnum align_type, unsigned abi_align,
                     unsigned pref_align, uint32_t bit_width);
   unsigned getAlignmentInfo(AlignTypeEnum align_type, uint32_t bit_width,
                             bool ABIAlign, Type *Ty) const;
   void setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
                            unsigned PrefAlign, uint32_t TypeByteWidth,
-                           uint32_t IndexWidth);
+                           uint32_t IndexWidth, uint32_t GlobalBitWidth);
 
   /// Internal helper method that returns requested alignment for type.
   unsigned getAlignment(Type *Ty, bool abi_or_pref) const;
 
   /// Parses a target data specification string. Assert if the string is
   /// malformed.
   void parseSpecifier(StringRef LayoutDescription);
 
public:
   /// the backends/clients are updated.
   unsigned getPointerPrefAlignment(unsigned AS = 0) const;
 
   /// Layout pointer size
   /// FIXME: The defaults need to be removed once all of
   /// the backends/clients are updated.
   unsigned getPointerSize(unsigned AS = 0) const;
 
+  /// Return bit width of global value addresses. Higher bits can be assumed
+  /// to be 0.
+  unsigned getPointerGlobalBitWidth(unsigned AS) const;
+
   // Index size used for address calculation.
   unsigned getIndexSize(unsigned AS) const;
 
   /// Return the address spaces containing non-integral pointers.  Pointers in
   /// this address space don't have a well-defined bitwise representation.
   ArrayRef<unsigned> getNonIntegralAddressSpaces() const {
     return NonIntegralAddressSpaces;
   }

lib/Analysis/ValueTracking.cpp

case Instruction::Alloca: {
     break;
   }
   case Instruction::GetElementPtr: {
     // Analyze all of the subscripts of this getelementptr instruction
     // to determine if we can prove known low zero bits.
     KnownBits LocalKnown(BitWidth);
     computeKnownBits(I->getOperand(0), LocalKnown, Depth + 1, Q);
     unsigned TrailZ = LocalKnown.countMinTrailingZeros();
+    unsigned LeadZ = LocalKnown.countMinLeadingZeros();
 
+    uint64_t StructOffset = 0;
     gep_type_iterator GTI = gep_type_begin(I);
     for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) {
       Value *Index = I->getOperand(i);
       if (StructType *STy = GTI.getStructTypeOrNull()) {
         // Handle struct member offset arithmetic.
 
         // Handle case when index is vector zeroinitializer
         Constant *CIndex = cast<Constant>(Index);
         if (CIndex->isZeroValue())
           continue;
 
         if (CIndex->getType()->isVectorTy())
           Index = CIndex->getSplatValue();
 
         unsigned Idx = cast<ConstantInt>(Index)->getZExtValue();
         const StructLayout *SL = Q.DL.getStructLayout(STy);
-        uint64_t Offset = SL->getElementOffset(Idx);
-        TrailZ = std::min<unsigned>(TrailZ,
-                                    countTrailingZeros(Offset));
+        StructOffset += SL->getElementOffset(Idx);
       } else {
         // Handle array index arithmetic.
         Type *IndexedTy = GTI.getIndexedType();
         if (!IndexedTy->isSized()) {
           TrailZ = 0;
+          LeadZ = 0;
           break;
         }
         unsigned GEPOpiBits = Index->getType()->getScalarSizeInBits();
         uint64_t TypeSize = Q.DL.getTypeAllocSize(IndexedTy);
         LocalKnown.Zero = LocalKnown.One = APInt(GEPOpiBits, 0);
         computeKnownBits(Index, LocalKnown, Depth + 1, Q);
         TrailZ = std::min(TrailZ,
                           unsigned(countTrailingZeros(TypeSize) +
                                    LocalKnown.countMinTrailingZeros()));
+        if (!LocalKnown.isNonNegative()) {
+          LeadZ = 0;
+        } else if (!LocalKnown.isZero()) {
+          // Bit width for (Index * TypeSize).
+          //
+          // In the common case where TypeSize is a power-of-two this is just
+          // the bit width of Index + log2(TypeSize). Else it's bounded by the
+          // bit width of TypeSize + bit width of Index.
+          unsigned OffsetWidth = std::min<unsigned>(
+              BitWidth, GEPOpiBits - LocalKnown.countMinLeadingZeros() +
+                            Log2_64_Ceil(TypeSize));
+          LeadZ = std::min(LeadZ, BitWidth - OffsetWidth);
+          if (LeadZ > 0)
+            LeadZ--;
+        }
       }
     }
 
+    if (StructOffset) {
+      TrailZ = std::min<unsigned>(TrailZ, countTrailingZeros(StructOffset));
+      LeadZ = std::min<unsigned>(LeadZ, BitWidth - (Log2_64(StructOffset) + 1));
+      if (LeadZ > 0)
+        LeadZ--;
+    }
+
     Known.Zero.setLowBits(TrailZ);
+    Known.Zero.setHighBits(LeadZ);
     break;
   }
   case Instruction::PHI: {
     const PHINode *P = cast<PHINode>(I);
     // Handle the case of a simple two-predecessor recurrence PHI.
     // There's a lot more that could theoretically be done here, but
     // this is sufficient to catch some interesting cases.
     if (P->getNumIncomingValues() == 2) {
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth,
   if (const Operator *I = dyn_cast<Operator>(V))
     computeKnownBitsFromOperator(I, Known, Depth, Q);
 
   // Aligned pointers have trailing zeros - refine Known.Zero set
   if (V->getType()->isPointerTy()) {
     unsigned Align = V->getPointerAlignment(Q.DL);
     if (Align)
       Known.Zero.setLowBits(countTrailingZeros(Align));
+
+    if (isa<GlobalValue>(V)) {
+      unsigned AS = cast<PointerType>(V->getType())->getAddressSpace();
+      unsigned Bits = Q.DL.getPointerGlobalBitWidth(AS);
+      assert(Bits <= BitWidth);
+      Known.Zero.setBits(Bits, BitWidth);
+    }
   }
 
   // computeKnownBitsFromAssume strictly refines Known.
   // Therefore, we run them after computeKnownBitsFromOperator.
 
   // Check whether a nearby assume intrinsic can determine some known bits.
   computeKnownBitsFromAssume(V, Known, Depth, Q);
 

lib/IR/DataLayout.cpp

 
 //===----------------------------------------------------------------------===//
 // PointerAlignElem, PointerAlign support
 //===----------------------------------------------------------------------===//
 
 PointerAlignElem
 PointerAlignElem::get(uint32_t AddressSpace, unsigned ABIAlign,
                       unsigned PrefAlign, uint32_t TypeByteWidth,
-                      uint32_t IndexWidth) {
+                      uint32_t IndexWidth, uint32_t GlobalBitWidth) {
   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
   PointerAlignElem retval;
   retval.AddressSpace = AddressSpace;
   retval.ABIAlign = ABIAlign;
   retval.PrefAlign = PrefAlign;
   retval.TypeByteWidth = TypeByteWidth;
   retval.IndexWidth = IndexWidth;
+  retval.GlobalBitWidth = GlobalBitWidth;
   return retval;
 }
 
 bool
 PointerAlignElem::operator==(const PointerAlignElem &rhs) const {
   return (ABIAlign == rhs.ABIAlign
           && AddressSpace == rhs.AddressSpace
           && PrefAlign == rhs.PrefAlign
           && TypeByteWidth == rhs.TypeByteWidth
-          && IndexWidth == rhs.IndexWidth);
+          && IndexWidth == rhs.IndexWidth
+          && GlobalBitWidth == rhs.GlobalBitWidth);
 }
 
 //===----------------------------------------------------------------------===//
 //                       DataLayout Class Implementation
 //===----------------------------------------------------------------------===//
 
 const char *DataLayout::getManglingComponent(const Triple &T) {
   if (T.isOSBinFormatMachO())
void DataLayout::reset(StringRef Desc) {
   ManglingMode = MM_None;
   NonIntegralAddressSpaces.clear();
 
   // Default alignments
   for (const LayoutAlignElem &E : DefaultAlignments) {
     setAlignment((AlignTypeEnum)E.AlignType, E.ABIAlign, E.PrefAlign,
                  E.TypeBitWidth);
   }
-  setPointerAlignment(0, 8, 8, 8, 8);
+  setPointerAlignment(0, 8, 8, 8, 8, 64);
 
   parseSpecifier(Desc);
 }
 
 /// Checked version of split, to ensure mandatory subparts.
 static std::pair<StringRef, StringRef> split(StringRef Str, char Separator) {
   assert(!Str.empty() && "parse error, string can't be empty here");
   std::pair<StringRef, StringRef> Split = Str.split(Separator);
case 'p': {
             "Pointer ABI alignment must be a power of 2");
 
       // Size of index used in GEP for address calculation.
       // The parameter is optional. By default it is equal to size of pointer.
       unsigned IndexSize = PointerMemSize;
 
       // Preferred alignment.
       unsigned PointerPrefAlign = PointerABIAlign;
+
+      // Size of global value pointers. This default assumes 8-bit bytes.
+      unsigned GlobalBitWidth = 8 * PointerMemSize;
+
       if (!Rest.empty()) {
         Split = split(Rest, ':');
         PointerPrefAlign = inBytes(getInt(Tok));
         if (!isPowerOf2_64(PointerPrefAlign))
           report_fatal_error(
             "Pointer preferred alignment must be a power of 2");
 
         // Now read the index. It is the second optional parameter here.
         if (!Rest.empty()) {
           Split = split(Rest, ':');
           IndexSize = inBytes(getInt(Tok));
           if (!IndexSize)
             report_fatal_error("Invalid index size of 0 bytes");
+
+          if (!Rest.empty()) {
+            Split = split(Rest, ':');
+            GlobalBitWidth = getInt(Tok);
+            if (!GlobalBitWidth)
+              report_fatal_error("Invalid global bit width of 0 bits");
+          }
         }
       }
       setPointerAlignment(AddrSpace, PointerABIAlign, PointerPrefAlign,
-                          PointerMemSize, IndexSize);
+                          PointerMemSize, IndexSize, GlobalBitWidth);
       break;
     }
     case 'i':
     case 'v':
     case 'f':
     case 'a': {
       AlignTypeEnum AlignType;
       switch (Specifier) {
DataLayout::findPointerLowerBound(uint32_t AddressSpace) {
   return std::lower_bound(Pointers.begin(), Pointers.end(), AddressSpace,
                           [](const PointerAlignElem &A, uint32_t AddressSpace) {
     return A.AddressSpace < AddressSpace;
   });
 }
 
 void DataLayout::setPointerAlignment(uint32_t AddrSpace, unsigned ABIAlign,
                                      unsigned PrefAlign, uint32_t TypeByteWidth,
-                                     uint32_t IndexWidth) {
+                                     uint32_t IndexWidth,
+                                     uint32_t GlobalBitWidth) {
   if (PrefAlign < ABIAlign)
     report_fatal_error(
         "Preferred alignment cannot be less than the ABI alignment");
 
   PointersTy::iterator I = findPointerLowerBound(AddrSpace);
   if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
     Pointers.insert(I, PointerAlignElem::get(AddrSpace, ABIAlign, PrefAlign,
-                                             TypeByteWidth, IndexWidth));
+                                             TypeByteWidth, IndexWidth,
+                                             GlobalBitWidth));
   } else {
     I->ABIAlign = ABIAlign;
     I->PrefAlign = PrefAlign;
     I->TypeByteWidth = TypeByteWidth;
     I->IndexWidth = IndexWidth;
+    I->GlobalBitWidth = GlobalBitWidth;
   }
 }
 
 /// getAlignmentInfo - Return the alignment (either ABI if ABIInfo = true or
 /// preferred if ABIInfo = false) the layout wants for the specified datatype.
 unsigned DataLayout::getAlignmentInfo(AlignTypeEnum AlignType,
                                       uint32_t BitWidth, bool ABIInfo,
                                       Type *Ty) const {
unsigned DataLayout::getPointerSize(unsigned AS) const {
   PointersTy::const_iterator I = findPointerLowerBound(AS);
   if (I == Pointers.end() || I->AddressSpace != AS) {
     I = findPointerLowerBound(0);
     assert(I->AddressSpace == 0);
   }
   return I->TypeByteWidth;
 }
 
+unsigned DataLayout::getPointerGlobalBitWidth(unsigned AS) const {
+  PointersTy::const_iterator I = findPointerLowerBound(AS);
+  if (I == Pointers.end() || I->AddressSpace != AS) {
+    I = findPointerLowerBound(0);
+    assert(I->AddressSpace == 0);
+  }
+  return I->GlobalBitWidth;
+}
+
 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
   assert(Ty->isPtrOrPtrVectorTy() &&
          "This should only be called with a pointer or pointer vector type");
   Ty = Ty->getScalarType();
   return getPointerSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
 }
 
 unsigned DataLayout::getIndexSize(unsigned AS) const {

lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

static StringRef computeDataLayout(const Triple &TT) {
   if (TT.getArch() == Triple::r600) {
     // 32-bit pointers.
       return "e-p:32:32-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128"
              "-v192:256-v256:256-v512:512-v1024:1024-v2048:2048-n32:64-S32-A5";
   }
 
   // 32-bit private, local, and region pointers. 64-bit global, constant and
   // flat.
-    return "e-p:64:64-p1:64:64-p2:32:32-p3:32:32-p4:64:64-p5:32:32-p6:32:32"
+  return "e-p:64:64-p1:64:64-p2:32:32:32:32:16-p3:32:32:32:32:16"
+         "-p4:64:64-p5:32:32-p6:32:32"
          "-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128"
          "-v192:256-v256:256-v512:512-v1024:1024-v2048:2048-n32:64-S32-A5";
 }
 
 LLVM_READNONE
 static StringRef getGPUOrDefault(const Triple &TT, StringRef GPU) {
   if (!GPU.empty())
     return GPU;

test/Transforms/LoadStoreVectorizer/AMDGPU/ds-bounds.ll

entry:
 
   store i32 42, i32 addrspace(3)* %ptr, align 8
   store i32 43, i32 addrspace(3)* %ptr.gep.1
   ret void
 }
 
 
 ; ALL-LABEL: @store_global_const_idx(
-;
-; TODO: Addresses are known-positive, this could be merged!
-; SI: store i32
-; SI: store i32
-;
-; NONSI: store <2 x i32> <i32 42, i32 43>, <2 x i32> addrspace(3)* %0, align 4
+; ALL: store <2 x i32> <i32 42, i32 43>, <2 x i32> addrspace(3)* %0, align 4
 define amdgpu_cs void @store_global_const_idx() #0 {
 entry:
   %ptr.a = getelementptr [512 x i32], [512 x i32] addrspace(3)* @compute_lds, i32 0, i32 3
   %ptr.b = getelementptr [512 x i32], [512 x i32] addrspace(3)* @compute_lds, i32 0, i32 4
 
   store i32 42, i32 addrspace(3)* %ptr.a
   store i32 43, i32 addrspace(3)* %ptr.b
   ret void
entry:
 
   store i32 42, i32 addrspace(3)* %ptr.a
   store i32 43, i32 addrspace(3)* %ptr.b
   ret void
 }
 
 
 ; ALL-LABEL: @store_global_var_idx_case2(
-;
-; TODO: Addresses are known-positive, this could be merged!
-; SI: store i32
-; SI: store i32
-;
-; NONSI: store <2 x i32> <i32 42, i32 43>, <2 x i32> addrspace(3)* %0, align 4
+; ALL: store <2 x i32> <i32 42, i32 43>, <2 x i32> addrspace(3)* %0, align 4
 define amdgpu_cs void @store_global_var_idx_case2(i32 %idx) #0 {
 entry:
   %idx.and = and i32 %idx, 255
   %ptr.a = getelementptr [512 x i32], [512 x i32] addrspace(3)* @compute_lds, i32 0, i32 %idx.and
   %ptr.b = getelementptr i32, i32 addrspace(3)* %ptr.a, i32 1
 
   store i32 42, i32 addrspace(3)* %ptr.a
   store i32 43, i32 addrspace(3)* %ptr.b
   ret void
 }
 
 
 attributes #0 = { nounwind }