[IR] Introduce a non-integral pointer type

[sanjoy]

Summary

This change adds a ni:<addrspace> specifier in the datalayout string to
denote pointers in the given address space as "non-integral", and adds some
typing rules these special pointers.

[sanjoy]

This probably does not need saying, but this is just the very first step in the plan mentioned in http://lists.llvm.org/pipermail/llvm-dev/2016-July/102466.html, other steps will follow once this lands.

For people seeing this for the first time, the design discussion starts at http://lists.llvm.org/pipermail/llvm-dev/2016-July/102161.html

[sanjoy]

• review

[sanjoy]

Also ping!

(I've changed the specification to not be tied to GC semantics as discussed on the llvm-dev thread)

[arsenm]

lib/IR/Verifier.cpp

2413–2415 ↗

(On Diff #64613)

What about vector of pointers?

2442–2444 ↗

(On Diff #64613)

Ditto

[sanjoy]

lib/IR/Verifier.cpp

2413–2415 ↗

(On Diff #64613)

Won't getScalarType take care of that? I'll add a test case.

2442–2444 ↗

(On Diff #64613)

Won't getScalarType take care of that? I'll add a test case.

[sanjoy]

• review
• move test case
• review

[arsenm]

docs/LangRef.rst

559–561 ↗

(On Diff #65125)

What consequence does the changing pointer value have on the optimizer? I'm interested in this for fat pointers which will not change value during runtime

[sanjoy]

docs/LangRef.rst

559–561 ↗

(On Diff #65125)

That is the justification for disallowing integer <-> pointer conversions (directly via cast instructions or via memory). If fat pointers have a stable bitwise representation, then why not represent them as normal pointers?

[arsenm]

docs/LangRef.rst

559–561 ↗

(On Diff #65125)

The pointer arithmetic does not behave exactly like a 128-bit integer. Doing pointer arithmetic such as a 128-bit add would be incorrect, and we don't want CodeGenPrepare etc. to be allowed to decompose it into integer operations.

The high 64-bits are constant "metadata" bits for the memory operation. The low 64-bits behave like a pointer. I think what we need is something that would only ever have the pointer manipulated through GEP, and then special addressing mode matching in the backend (since the fat pointer should almost always be treated as a constant with a separate index operand)

[sanjoy]

docs/LangRef.rst

559–561 ↗

(On Diff #65125)

Okay, that sounds reasonable. We have a similar restriction, in that GEPs have to stay GEPs and can't be decomposed into integer arithmetic. However, we also want to allow things like alignment, which only really make sense if the pointer has an integral representation. What do you think of changing the language to say "does not have a useful integral representation"? "useful" is deliberately vague here, with the understanding that we disallow some integer-like operations / properties, but allow others.

[sanjoy]

docs/LangRef.rst

559–561 ↗

(On Diff #65125)

we also want to allow things like alignment

Just to be explicit: I meant we also want to allow specifying things like alignment on these non-integral pointers

[arsenm]

docs/LangRef.rst

559–561 ↗

(On Diff #65125)

That seems ok. The low bits are pointer like, so alignment still would make sense for our case

[arsenm]

docs/LangRef.rst

559–561 ↗

(On Diff #65125)

Maybe better would be a target dependent representation? Saying not useful seems restrictive to backend code that wants to rely on target specific assumptions

[sanjoy]

• update docs as per dicussion with @arsenm

[arsenm]

docs/LangRef.rst

1854–1855 ↗

(On Diff #65580)

Maybe mention this isn't allowed for AS 0?

include/llvm/IR/DataLayout.h

206 ↗

(On Diff #65580)

Only one non-integral is supported? I would expect it to support specifying any address space (like the pointer bit widths). I'm not sure we really need more than one, but 2 or 3 seems likely.

[arsenm]

include/llvm/IR/DataLayout.h

206 ↗

(On Diff #65580)

If the one restriction remains it at least needs a mention in the langref

[sanjoy]

address review

[sanjoy]

Addressed review

[arsenm]

include/llvm/IR/DataLayout.h

150 ↗

(On Diff #65978)

Seems like it should be a SmallSet?

[sanjoy]

include/llvm/IR/DataLayout.h

150 ↗

(On Diff #65978)

Since this isn't going to change after creation, how about a sorted SmallVector? That way we'll avoid the isSmall check in isNonIntegralPointerType and will also be able to use a binary search instead of a linear search.

[arsenm]

include/llvm/IR/DataLayout.h

150 ↗

(On Diff #65978)

I don't forsee this ever being larger than 3 or 4, so the linear search a SmallSet does for the small case is probably better

[sanjoy]

include/llvm/IR/DataLayout.h

150 ↗

(On Diff #65978)

I don't forsee this ever being larger than 3 or 4, so the linear search a SmallSet does for the small case is probably better

Then why bother with a SmallSet at all? If you're worried about worst-case situations where we have millions of non-integral address spaces, then a sorted vector seems better than a SmallSet.

[arsenm]

include/llvm/IR/DataLayout.h

150 ↗

(On Diff #65978)

I suppose there's not much difference

[sanjoy]

• bump the small vector size, as discussed with @arsenm on IRC

[arsenm]

LGTM

llvm/trunk/docs/LangRef.rst

 
 .. code-block:: llvm
 
     %mytype = type { %mytype*, i32 }
 
 Prior to the LLVM 3.0 release, identified types were structurally uniqued. Only
 literal types are uniqued in recent versions of LLVM.
 
+.. _nointptrtype:
+
+Non-Integral Pointer Type
+-------------------------
+
+Note: non-integral pointer types are a work in progress, and they should be
+considered experimental at this time.
+
+LLVM IR optionally allows the frontend to denote pointers in certain address
+spaces as "non-integral" via the :ref:```datalayout``
+string<langref_datalayout>`.  Non-integral pointer types represent pointers that
+have an *unspecified* bitwise representation; that is, the integral
+representation may be target dependent or unstable (not backed by a fixed
+integer).
+
+``inttoptr`` instructions converting integers to non-integral pointer types are
+ill-typed, and so are ``ptrtoint`` instructions converting values of
+non-integral pointer types to integers.  Vector versions of said instructions
+are ill-typed as well.
+
 .. _globalvars:
 
 Global Variables
 ----------------
 
 Global variables define regions of memory allocated at compilation time
 instead of run-time.
 
``m:<mangling>``
     * ``x``: Windows x86 COFF prefix:  Similar to Windows COFF, but use a ``_``
       prefix for ``__cdecl`` functions.
 ``n<size1>:<size2>:<size3>...``
     This specifies a set of native integer widths for the target CPU in
     bits. For example, it might contain ``n32`` for 32-bit PowerPC,
     ``n32:64`` for PowerPC 64, or ``n8:16:32:64`` for X86-64. Elements of
     this set are considered to support most general arithmetic operations
     efficiently.
+``ni:<address space0>:<address space1>:<address space2>...``
+    This specifies pointer types with the specified address spaces
+    as :ref:`Non-Integral Pointer Type <nointptrtype>` s.  The ``0``
+    address space cannot be specified as non-integral.
 
 On every specification that takes a ``<abi>:<pref>``, specifying the
 ``<pref>`` alignment is optional. If omitted, the preceding ``:``
 should be omitted too and ``<pref>`` will be equal to ``<abi>``.
 
 When constructing the data layout for a given target, LLVM starts with a
 default set of specifications which are then (possibly) overridden by
 the specifications in the ``datalayout`` keyword. The default

llvm/trunk/include/llvm/IR/DataLayout.h

 // require modification to the object.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_DATALAYOUT_H
 #define LLVM_IR_DATALAYOUT_H
 
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/DataTypes.h"
 
 // This needs to be outside of the namespace, to avoid conflict with llvm-c
 // decl.
 typedef struct LLVMOpaqueTargetData *LLVMTargetDataRef;
private:
 
   /// This member is a signal that a requested pointer type and bit width were
   /// not found in the DenseSet.
   static const PointerAlignElem InvalidPointerElem;
 
   // The StructType -> StructLayout map.
   mutable void *LayoutMap;
 
+  /// Pointers in these address spaces are non-integral, and don't have a
+  /// well-defined bitwise representation.
+  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);
 
   /// Internal helper method that returns requested alignment for type.
DataLayout &operator=(const DataLayout &DL) {
     clear();
     StringRepresentation = DL.StringRepresentation;
     BigEndian = DL.isBigEndian();
     StackNaturalAlign = DL.StackNaturalAlign;
     ManglingMode = DL.ManglingMode;
     LegalIntWidths = DL.LegalIntWidths;
     Alignments = DL.Alignments;
     Pointers = DL.Pointers;
+    NonIntegralAddressSpaces = DL.NonIntegralAddressSpaces;
     return *this;
   }
 
   bool operator==(const DataLayout &Other) const;
   bool operator!=(const DataLayout &Other) const { return !(*this == Other); }
 
   ~DataLayout(); // Not virtual, do not subclass this class
 
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 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;
+  }
+
+  bool isNonIntegralPointerType(PointerType *PT) const {
+    ArrayRef<unsigned> NonIntegralSpaces = getNonIntegralAddressSpaces();
+    return find(NonIntegralSpaces, PT->getAddressSpace()) !=
+           NonIntegralSpaces.end();
+  }
+
   /// 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 getPointerSize(AS) * 8;
   }
 
   /// Layout pointer size, in bits, based on the type.  If this function is

llvm/trunk/lib/IR/DataLayout.cpp

 
 void DataLayout::reset(StringRef Desc) {
   clear();
 
   LayoutMap = nullptr;
   BigEndian = false;
   StackNaturalAlign = 0;
   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);
 
while (!Desc.empty()) {
 
     // Split at ':'.
     Split = split(Split.first, ':');
 
     // Aliases used below.
     StringRef &Tok  = Split.first;  // Current token.
     StringRef &Rest = Split.second; // The rest of the string.
 
+    if (Tok == "ni") {
+      do {
+        Split = split(Rest, ':');
+        Rest = Split.second;
+        unsigned AS = getInt(Split.first);
+        if (AS == 0)
+          report_fatal_error("Address space 0 can never be non-integral");
+        NonIntegralAddressSpaces.push_back(AS);
+      } while (!Rest.empty());
+
+      continue;
+    }
+
     char Specifier = Tok.front();
     Tok = Tok.substr(1);
 
     switch (Specifier) {
     case 's':
       // Ignored for backward compatibility.
       // FIXME: remove this on LLVM 4.0.
       break;

llvm/trunk/lib/IR/Verifier.cpp

 
 void Verifier::visitPtrToIntInst(PtrToIntInst &I) {
   // Get the source and destination types
   Type *SrcTy = I.getOperand(0)->getType();
   Type *DestTy = I.getType();
 
   Assert(SrcTy->getScalarType()->isPointerTy(),
          "PtrToInt source must be pointer", &I);
+
+  if (auto *PTy = dyn_cast<PointerType>(SrcTy->getScalarType()))
+    Assert(!M->getDataLayout().isNonIntegralPointerType(PTy),
+           "ptrtoint not supported for non-integral pointers");
+
   Assert(DestTy->getScalarType()->isIntegerTy(),
          "PtrToInt result must be integral", &I);
   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(), "PtrToInt type mismatch",
          &I);
 
   if (SrcTy->isVectorTy()) {
     VectorType *VSrc = dyn_cast<VectorType>(SrcTy);
     VectorType *VDest = dyn_cast<VectorType>(DestTy);
     Assert(VSrc->getNumElements() == VDest->getNumElements(),
            "PtrToInt Vector width mismatch", &I);
   }
 
   visitInstruction(I);
 }
 
 void Verifier::visitIntToPtrInst(IntToPtrInst &I) {
   // Get the source and destination types
   Type *SrcTy = I.getOperand(0)->getType();
   Type *DestTy = I.getType();
 
   Assert(SrcTy->getScalarType()->isIntegerTy(),
          "IntToPtr source must be an integral", &I);
   Assert(DestTy->getScalarType()->isPointerTy(),
          "IntToPtr result must be a pointer", &I);
+
+  if (auto *PTy = dyn_cast<PointerType>(DestTy->getScalarType()))
+    Assert(!M->getDataLayout().isNonIntegralPointerType(PTy),
+           "inttoptr not supported for non-integral pointers");
+
   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(), "IntToPtr type mismatch",
          &I);
   if (SrcTy->isVectorTy()) {
     VectorType *VSrc = dyn_cast<VectorType>(SrcTy);
     VectorType *VDest = dyn_cast<VectorType>(DestTy);
     Assert(VSrc->getNumElements() == VDest->getNumElements(),
            "IntToPtr Vector width mismatch", &I);
   }

llvm/trunk/test/Verifier/non-integral-pointers.ll

+; RUN: not opt -verify < %s 2>&1 | FileCheck %s
+
+target datalayout = "e-ni:4:6"
+
+define i64 @f_0(i8 addrspace(4)* %ptr) {
+; CHECK: ptrtoint not supported for non-integral pointers
+  %val = ptrtoint i8 addrspace(4)* %ptr to i64
+  ret i64 %val
+}
+
+define <4 x i64> @f_1(<4 x i8 addrspace(4)*> %ptr) {
+; CHECK: ptrtoint not supported for non-integral pointers
+  %val = ptrtoint <4 x i8 addrspace(4)*> %ptr to <4 x i64>
+  ret <4 x i64> %val
+}
+
+define i64 @f_2(i8 addrspace(3)* %ptr) {
+; Negative test
+  %val = ptrtoint i8 addrspace(3)* %ptr to i64
+  ret i64 %val
+}
+
+define i8 addrspace(4)* @f_3(i64 %integer) {
+; CHECK: inttoptr not supported for non-integral pointers
+  %val = inttoptr i64 %integer to i8 addrspace(4)*
+  ret i8 addrspace(4)* %val
+}
+
+define <4 x i8 addrspace(4)*> @f_4(<4 x i64> %integer) {
+; CHECK: inttoptr not supported for non-integral pointers
+  %val = inttoptr <4 x i64> %integer to <4 x i8 addrspace(4)*>
+  ret <4 x i8 addrspace(4)*> %val
+}
+
+define i8 addrspace(3)* @f_5(i64 %integer) {
+; Negative test
+  %val = inttoptr i64 %integer to i8 addrspace(3)*
+  ret i8 addrspace(3)* %val
+}
+
+define i64 @f_6(i8 addrspace(6)* %ptr) {
+; CHECK: ptrtoint not supported for non-integral pointers
+  %val = ptrtoint i8 addrspace(6)* %ptr to i64
+  ret i64 %val
+}