[DataLayout] Introduce DataLayout::getPointerIntegralSize(AS)

[arichardson]

Summary

This function can be used to retrieve the number of bits that can be used
for arithmetic in a given address space (i.e. the range of the address
space). For most (all?) in-tree targets this should not make any difference,
but differentiating between the size of a pointer in bits and the address
range is extremely important e.g. for CHERI-enabled targets, where pointers
carry additional metadata such as bounds and permissions and only a subset
of the pointer bits is used as the address. This could also benefit other
users of non-integral pointers but I am not familiar with any of those
backends. In the out-of-tree CHERI target, we use the index width of the
datalayout to identify the address range (and I believe this was also
the intent when the index type was introduced in D42123).
This commit is just a clarification of the LangRef as well as
the introduction of new functions that more clearly explain the
intended usage. In the future, if we end up supporting a target
with index width != integral range, we could add a new datalayout
component.

I am not sure if getPointerIntegralSize() is the best name for this
accessor, I also considered names such as getPointerArithmenticRange or
getPointerAddressRange().

[nikic]

I don't really understand what the distinction between the index size and the integral size is supposed to be. Can you please give some examples where these two quantities would differ?

I would be extremely vary of adding a third dimension to pointer sizes. The index size is already enough of a burden to deal with, and we've only recently approached something resembling correct use of index sizes.

[arichardson]

In D135158#3833549, @nikic wrote:

I don't really understand what the distinction between the index size and the integral size is supposed to be. Can you please give some examples where these two quantities would differ?

I would be extremely vary of adding a third dimension to pointer sizes. The index size is already enough of a burden to deal with, and we've only recently approached something resembling correct use of index sizes.

Ah, in that case I would be more than happy to drop this distinction and just clarify the datalayout that the index size is the size of the address (which is what we do for CHERI already).
I added this new type based on your comment in D99660:

The index type is used for GEP index and casting a pointer to the index type doesn't make a whole lot of sense to me. Do you have any LangRef wording or other usages that would show that this is a sensible thing to do?

Would a clarification to the LangRef be sufficient?

[arichardson]

Basically, the problem I'm trying to solve here is that code introducing ptr2int right now uses DL.getPointerSize() to obtain the integer, but for us we want this to be the address size (i.e. 64 for ELFCLASS64).
We don't want ptr2int to give us i128 types since only 64 of those bits are meaningful (but using ptrtoint is perfectly fine, so the current non-integral constraints are too restrictive)

[arichardson]

Avoid adding a new datalayout component and only add the function

[arsenm]

But I thought we banned ptrtoint for nonintegral pointers

[jrtc27]

CHERI capabilities aren't non-integral. Converting a capability to an integer gives you the address, discarding the metadata (which is also stable*), which is as well-defined as it is on normal architectures. Non-integral pointers are weird unstable things where ptrtoint on the same thing can give different results and so you can't introduce new instructions during optimisation (but so long as you know what you're doing it's fine to create them in the first place in the frontend).

• Technically not true when revocation is involved if you inspect the metadata of a capability referring to an object past the end of its lifetime, but that is highly UB and constrained in terms of what you can observe

[nikic]

Is this needed for anything but the one usage in D99660? We could just stop using ptrtoint there and just explicitly check for the nullptr and inttoptr cases, which is all this handles in practice. This overly general constant expression based code has already caused enough complications in the past, so I'm happy to drop it.

I don't think producing a ptr2int out of thin air (without a known result type) is common, and should probably be avoided in general. The main case where we currently introduce ptr2int is when type punning through memory, and in that case the load/store type determines the used type.

[arichardson]

In D135158#3834627, @nikic wrote:

Is this needed for anything but the one usage in D99660? We could just stop using ptrtoint there and just explicitly check for the nullptr and inttoptr cases, which is all this handles in practice. This overly general constant expression based code has already caused enough complications in the past, so I'm happy to drop it.

I don't think producing a ptr2int out of thin air (without a known result type) is common, and should probably be avoided in general. The main case where we currently introduce ptr2int is when type punning through memory, and in that case the load/store type determines the used type.

There are also a few other cases where code wants needs the address range instead of the pointer size but that does not matter for most targets. I'll upload a few more patches that show where this function is needed for CHERI.

[theraven]

CHERI capabilities aren't non-integral. Converting a capability to an integer gives you the address, discarding the metadata (which is also stable*), which is as well-defined as it is on normal architectures.

Note that this is purely for historical reasons: Non-integral pointers were not available when we started. I worked with the folks pushing NI pointers to make sure that they'd work with CHERI and the plan was always to move over to NI at some point.

I overloaded the semantics of ptrtoint as get-address as a quick hack to make things work but it's definitely not the right thing to do and we spent several years working with other folks with similar requirements to upstream features that would let us move away from this. The behaviour of CHERI's ptrtoint is confusing to optimisers. I believe that the correct solution (which, I vaguely recall, I wrote in a roadmap doc before I left the CL) is:

1. Make CHERI use NI pointers.
2. Make clang generate get-address intrinsics instead of ptrtoint.
3. Help fix any optimisations that try to introduce ptrtoint for NI pointers.
4. Make the CHERI back ends reject PTRTOINT DAG nodes.

CHERI LLVM IR should only ever have get-address and set-address intrinsics, no inttoptr and ptrtoint instructions. This should improve optimisations for things that round-trip addresses through pointers because ptrtoint is treated as an escape for alias analysis, whereas get-address is not and set-address is explicitly a provenance-carrying operation that works directly with alias analysis. This structure is also desirable for Rust's Strict Provenance model, even with non-CHERI targets.

This is also the approach that I've recommended to the embecosm folks working on preparing CHERI LLVM for upstreaming. It would be great if more people could join those calls.

[jrtc27]

Except then you can't do unsigned long x = (unsigned long)&y as intrinsics are not constant expressions. Non-integral pointers are too strict for CHERI as things stand, we want a subset of their behaviour.

[theraven]

In D135158#3836839, @jrtc27 wrote:

Except then you can't do unsigned long x = (unsigned long)&y as intrinsics are not constant expressions. Non-integral pointers are too strict for CHERI as things stand, we want a subset of their behaviour.

You can; however, do it as a constant address-space cast, followed by a ptrtoint, which would make lowering easier in the back end because a constant address space cast of a global should give a non-capability relocation.

[mkazantsev]

Not sure I can give any useful feedback here.

llvm/docs/LangRef.rst

``G<address space>``
     address space 0.
     Note: variable declarations without an address space are always created in
     address space 0, this property only affects the default value to be used
     when creating globals without additional contextual information (e.g. in
     LLVM passes).
 ``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>][:<integral>]``
     This specifies the *size* of a pointer and its ``<abi>`` and
     ``<pref>``\erred alignments for address space ``n``. ``<pref>`` is optional
     and defaults to ``<abi>``. The fourth parameter ``<idx>`` is the size of the
-    index that used for address calculation. If not
-    specified, the default index size is equal to the pointer size. All sizes
+    index that used for address calculation. If not specified, the default index
+    size is equal to the pointer size. For targets that include additional
+    non-integral bits in the pointer representation (e.g. fat pointer metadata),
+    ``<integral>`` specifies the number of integral bits, i.e. the address space
+    range. If not specified, ``<integral>`` defaults to ``<idx>``. All sizes
     are in bits. 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).
     ``<pref>`` is optional and defaults to ``<abi>``.
 ``v<size>:<abi>[:<pref>]``

llvm/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 {
   Align ABIAlign;
   Align PrefAlign;
   uint32_t TypeBitWidth;
   uint32_t AddressSpace;
   uint32_t IndexBitWidth;
+  uint32_t IntegralBitWidth;
 
   /// Initializer
   static PointerAlignElem getInBits(uint32_t AddressSpace, Align ABIAlign,
                                     Align PrefAlign, uint32_t TypeBitWidth,
-                                    uint32_t IndexBitWidth);
+                                    uint32_t IndexBitWidth,
+                                    uint32_t IntegralBitWidth);
 
   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:
   /// description on failure.
   Error setAlignment(AlignTypeEnum align_type, Align abi_align,
                      Align pref_align, uint32_t bit_width);
 
   /// Attempts to set the alignment of a pointer in the given address space.
   /// Returns an error description on failure.
   Error setPointerAlignmentInBits(uint32_t AddrSpace, Align ABIAlign,
                                   Align PrefAlign, uint32_t TypeBitWidth,
-                                  uint32_t IndexBitWidth);
+                                  uint32_t IndexBitWidth,
+                                  uint32_t IntegralBitWidth);
 
   /// Internal helper to get alignment for integer of given bitwidth.
   Align getIntegerAlignment(uint32_t BitWidth, bool abi_or_pref) const;
 
   /// Internal helper method that returns requested alignment for type.
   Align getAlignment(Type *Ty, bool abi_or_pref) const;
 
   /// Attempts to parse a target data specification string and reports an error
public:
   /// Layout pointer alignment
   Align getPointerABIAlignment(unsigned AS) const;
 
   /// Return target's alignment for stack-based pointers
   /// FIXME: The defaults need to be removed once all of
   /// the backends/clients are updated.
   Align getPointerPrefAlignment(unsigned AS = 0) const;
 
-  /// Layout pointer size in bytes, rounded up to a whole
-  /// number of bytes.
+  /// Layout pointer size in bytes, rounded up to a whole number of bytes. The
+  /// difference between this function and getPointerIntegralSize() is this one
+  /// returns the size of the entire pointer type (this includes metadata bits
+  /// for fat pointers) and the latter only returns the number of address bits.
+  /// \sa DataLayout::getPointerIntegralSize
   /// FIXME: The defaults need to be removed once all of
   /// the backends/clients are updated.
   unsigned getPointerSize(unsigned AS = 0) const;
 
+  /// Returns the integral size of a pointer in a given address space in bytes.
+  /// For targets that store bits in pointers that are not part of the address,
+  /// this returns the number of bits that can be manipulated using operations
+  /// that change the address (e.g. addition/subtraction).
+  /// For example, a 64-bit CHERI-enabled target has 128-bit pointers of which
+  /// only 64 are used to represent the address and the remaining ones are used
+  /// for metadata such as bounds and access permissions. In this case
+  /// getPointerSize() returns 16, but getPointerIntegralSize() returns 8.
+  /// \sa DataLayout::getPointerSize
+  unsigned getPointerIntegralSize(unsigned AS) const;
+
   /// Returns the maximum index size over all address spaces.
   unsigned getMaxIndexSize() const;
 
   // Index size in bytes used for address calculation,
   /// rounded up to a whole number of bytes.
   unsigned getIndexSize(unsigned AS) const;
 
   /// Return the address spaces containing non-integral pointers.  Pointers in
public:
 
   /// Layout pointer size, in bits
   /// FIXME: The defaults need to be removed once all of
   /// the backends/clients are updated.
   unsigned getPointerSizeInBits(unsigned AS = 0) const {
     return getPointerAlignElem(AS).TypeBitWidth;
   }
 
+  unsigned getPointerIntegralSizeInBits(unsigned AS) const {
+    return getPointerAlignElem(AS).IntegralBitWidth;
+  }
+
   /// Returns the maximum index size over all address spaces.
   unsigned getMaxIndexSizeInBits() const {
     return getMaxIndexSize() * 8;
   }
 
   /// Size in bits of index used for address calculation in getelementptr.
   unsigned getIndexSizeInBits(unsigned AS) const {
     return getPointerAlignElem(AS).IndexBitWidth;

llvm/lib/IR/DataLayout.cpp

 
 //===----------------------------------------------------------------------===//
 // PointerAlignElem, PointerAlign support
 //===----------------------------------------------------------------------===//
 
 PointerAlignElem PointerAlignElem::getInBits(uint32_t AddressSpace,
                                              Align ABIAlign, Align PrefAlign,
                                              uint32_t TypeBitWidth,
-                                             uint32_t IndexBitWidth) {
+                                             uint32_t IndexBitWidth,
+                                             uint32_t IntegralBitWidth) {
   assert(ABIAlign <= PrefAlign && "Preferred alignment worse than ABI!");
   PointerAlignElem retval;
   retval.AddressSpace = AddressSpace;
   retval.ABIAlign = ABIAlign;
   retval.PrefAlign = PrefAlign;
   retval.TypeBitWidth = TypeBitWidth;
   retval.IndexBitWidth = IndexBitWidth;
+  retval.IntegralBitWidth = IntegralBitWidth;
   return retval;
 }
 
 bool
 PointerAlignElem::operator==(const PointerAlignElem &rhs) const {
   return (ABIAlign == rhs.ABIAlign && AddressSpace == rhs.AddressSpace &&
           PrefAlign == rhs.PrefAlign && TypeBitWidth == rhs.TypeBitWidth &&
           IndexBitWidth == rhs.IndexBitWidth);
void DataLayout::reset(StringRef Desc) {
   NonIntegralAddressSpaces.clear();
 
   // Default alignments
   for (const LayoutAlignElem &E : DefaultAlignments) {
     if (Error Err = setAlignment((AlignTypeEnum)E.AlignType, E.ABIAlign,
                                  E.PrefAlign, E.TypeBitWidth))
       return report_fatal_error(std::move(Err));
   }
-  if (Error Err = setPointerAlignmentInBits(0, Align(8), Align(8), 64, 64))
+  if (Error Err = setPointerAlignmentInBits(0, Align(8), Align(8), 64, 64, 64))
     return report_fatal_error(std::move(Err));
 
   if (Error Err = parseSpecifier(Desc))
     return report_fatal_error(std::move(Err));
 }
 
 Expected<DataLayout> DataLayout::parse(StringRef LayoutDescription) {
   DataLayout Layout("");
case 'p': {
       if (Error Err = getIntInBytes(Tok, PointerABIAlign))
         return Err;
       if (!isPowerOf2_64(PointerABIAlign))
         return reportError("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;
+      unsigned IntegralBits = IndexSize;
 
       // Preferred alignment.
       unsigned PointerPrefAlign = PointerABIAlign;
       if (!Rest.empty()) {
         if (Error Err = ::split(Rest, ':', Split))
           return Err;
         if (Error Err = getIntInBytes(Tok, PointerPrefAlign))
           return Err;
         if (!isPowerOf2_64(PointerPrefAlign))
           return reportError(
               "Pointer preferred alignment must be a power of 2");
 
         // Now read the index. It is the second optional parameter here.
         if (!Rest.empty()) {
           if (Error Err = ::split(Rest, ':', Split))
             return Err;
           if (Error Err = getInt(Tok, IndexSize))
             return Err;
           if (!IndexSize)
             return reportError("Invalid index size of 0 bytes");
         }
+        // Now read the integral range. It is the third optional parameter here.
+        IntegralBits = IndexSize;
+        if (!Rest.empty()) {
+          if (Error Err = ::split(Rest, ':', Split))
+            return Err;
+          if (Error Err = getInt(Tok, IntegralBits))
+            return Err;
+          if (!IntegralBits)
+            return reportError("Invalid integral size of 0 bytes");
+          if (IntegralBits > PointerMemSize)
+            return reportError("Pointer integral size cannot be larger than "
+                               "total pointer size");
+        }
         }
         if (Error Err = setPointerAlignmentInBits(
                 AddrSpace, assumeAligned(PointerABIAlign),
-              assumeAligned(PointerPrefAlign), PointerMemSize, IndexSize))
+                assumeAligned(PointerPrefAlign), PointerMemSize, IndexSize,
+                IntegralBits))
           return Err;
         break;
       }
     case 'i':
     case 'v':
     case 'f':
     case 'a': {
       AlignTypeEnum AlignType;
       switch (Specifier) {
       default: llvm_unreachable("Unexpected specifier!");
       case 'i': AlignType = INTEGER_ALIGN; break;
DataLayout::getPointerAlignElem(uint32_t AddressSpace) const {
 
   assert(Pointers[0].AddressSpace == 0);
   return Pointers[0];
 }
 
 Error DataLayout::setPointerAlignmentInBits(uint32_t AddrSpace, Align ABIAlign,
                                             Align PrefAlign,
                                             uint32_t TypeBitWidth,
-                                            uint32_t IndexBitWidth) {
+                                            uint32_t IndexBitWidth,
+                                            uint32_t IntegralBitWidth) {
   if (PrefAlign < ABIAlign)
     return reportError(
         "Preferred alignment cannot be less than the ABI alignment");
 
   auto I = lower_bound(Pointers, AddrSpace,
                        [](const PointerAlignElem &A, uint32_t AddressSpace) {
     return A.AddressSpace < AddressSpace;
   });
   if (I == Pointers.end() || I->AddressSpace != AddrSpace) {
-    Pointers.insert(I,
-                    PointerAlignElem::getInBits(AddrSpace, ABIAlign, PrefAlign,
-                                                TypeBitWidth, IndexBitWidth));
+    Pointers.insert(I, PointerAlignElem::getInBits(
+                           AddrSpace, ABIAlign, PrefAlign, TypeBitWidth,
+                           IndexBitWidth, IntegralBitWidth));
   } else {
     I->ABIAlign = ABIAlign;
     I->PrefAlign = PrefAlign;
     I->TypeBitWidth = TypeBitWidth;
     I->IndexBitWidth = IndexBitWidth;
   }
   return Error::success();
 }

 Align DataLayout::getPointerPrefAlignment(unsigned AS) const {
   return getPointerAlignElem(AS).PrefAlign;
 }
 
 unsigned DataLayout::getPointerSize(unsigned AS) const {
   return divideCeil(getPointerAlignElem(AS).TypeBitWidth, 8);
 }
 
+unsigned DataLayout::getPointerIntegralSize(unsigned AS) const {
+  return divideCeil(getPointerAlignElem(AS).IntegralBitWidth, 8);
+}
+
 unsigned DataLayout::getMaxIndexSize() const {
   unsigned MaxIndexSize = 0;
   for (auto &P : Pointers)
     MaxIndexSize =
         std::max(MaxIndexSize, (unsigned)divideCeil(P.TypeBitWidth, 8));
 
   return MaxIndexSize;
 }

llvm/test/Assembler/invalid-datalayout25.ll

+; RUN: not llvm-as < %s 2>&1 | FileCheck %s
+
+target datalayout = "p0:32:32:32:32:64"
+
+; CHECK: error: Pointer integral size cannot be larger than total pointer size
+

llvm/test/Assembler/invalid-datalayout26.ll

+; RUN: not llvm-as < %s 2>&1 | FileCheck %s
+
+target datalayout = "p0:32:32:32:32:0"
+
+; CHECK: error: Invalid integral size of 0 bytes
+