[IR] Introduce the opaque pointer type

[aeubanks]

Summary

The opaque pointer type is essentially just a normal pointer type with a
null pointee type.

This also adds support for the opaque pointer type to the bitcode
reader/writer, as well as to textual IR.

To avoid confusion with existing pointer types, we disallow creating a
pointer to an opaque pointer.

Opaque pointer types should not be widely used at this point since many
parts of LLVM still do not support them. The next steps are to add some
very simple use cases of opaque pointers to make sure they work, then
start pretending that all pointers are opaque pointers and see what
breaks.

https://lists.llvm.org/pipermail/llvm-dev/2021-May/150359.html

[aeubanks]

(RFC incoming)

[aeubanks]

tighten check on num records

[aeubanks]

(feel free to add any other reviewers)

[dblaikie]

To avoid confusion with existing pointer types, we disallow creating a pointer to an opaque pointer.

Is there some test coverage for this? (I guess some invalid textual and/or bitcode IR that demonstrates how this is checked/failed)

[arsenm]

llvm/docs/LangRef.rst

3335

in address space 0

llvm/include/llvm/IR/DerivedTypes.h

658

LLVM does not have a generic address space concept. This is the default address space

[aeubanks]

rebase
add test for pointer to opaque pointer
s/generic address space/default address space

[dblaikie]

Looks good to me - though might be worth waiting at least a few days to check if anyone else has feedback. (my approval isn't intended to stifle feedback - folks feel free to chime in!)

[dexonsmith]

The code LGTM too, just a couple of nits on docs and tests. Not sure if @t.p.northover has time to look right now, but I added him in case he does. I'm excited to see this moving along!

What's missing for me is where we are in the high-level arc. Why land this now? What's left to do after this lands? What should LLVM developers (and clients) be using the opaque type for once this patch lands (as opposed to the fullness of time)? What should they use typed pointers for?

IMO, adding some of that context to the commit message is important, even if it's light on details / high-level. It might also be useful (not sure...) to expand on it slightly in LangRef as well (some sort of guidance on when opaque vs. typed pointers are appropriate, which can be updated when the guidance changes / as typed pointers get eliminated).

It'd also be nice to have a clear message targeted at LLVM clients added to llvm/docs/ReleaseNotes.rst (which can be updated as guidance changes).

On a related note, plucked from the RFC thread:

Somebody pointed out to me that there's very little actual documentation on opaque pointer types. I'll try to write up some documentation so that the motivation and tradeoffs can be better discussed.

Were you planning to do that in this patch, or as a follow up? (Personally, I don't think it's necessary as a blocker for landing this patch; although pointing to it from the commit message / from the opaque pointer description in LangRef could be a tidy way to resolve my concerns about missing context / high-level arc / etc.)

llvm/docs/LangRef.rst

3312

Is the word "typically" needed here?

3319–3320

Please add another line:

ptr

llvm/test/Assembler/opaque-ptr.ll

2

It'd be nice to make this a double-round trip (pass it through as and dis again before heading to FileCheck), confirming that the textual IR generated by llvm-dis can also be assembled.

Also, at some point I added a RUN line calling verify-uselistorder to all tests in this directory; that's probably bit-rotted (I bet this wouldn't be the only one missing that line) but perhaps you can add one here.

[pcc]

This looks like a reasonable starting point for switching to opaque pointers in LLVM.

I think the most intuitive next step would be to get things working end-to-end with opaque pointers, starting with simple programs and going from there. As a side effect of that process we will no doubt cause some of the lit tests to start passing with opaque pointers -- as we do so, they can be converted incrementally to use opaque pointers.

Specifically what I would suggest is:

1. Add a command line flag that makes it so that PointerType::get(Type *, unsigned) always returns an opaque pointer type.

2. Turn it on and compile hello world with clang -O0. At this point this will almost certainly fail. Fix any issues found that way until hello world compiles and runs.

3. Repeat for hello world at -O2.

4. Once hello world is working, move on to larger programs, e.g. the LLVM test suite. As programs start working, have the test suite pass the flag for those programs to prevent backsliding.

5. In parallel with 2-4, gradually convert the lit tests to use opaque pointers.

[aeubanks]

update test
add to ReleaseNotes
mention that opaque pointer types aren't ready for general use yet

[dexonsmith]

In D101704#2751664, @aeubanks wrote:

update test
add to ReleaseNotes
mention that opaque pointer types aren't ready for general use yet

LGTM!

In D101704#2749822, @pcc wrote:

I think the most intuitive next step would be to get things working end-to-end with opaque pointers, starting with simple programs and going from there. As a side effect of that process we will no doubt cause some of the lit tests to start passing with opaque pointers -- as we do so, they can be converted incrementally to use opaque pointers.

Yeah, this approach sounds pretty reasonable.

I'm curious, have we exhausted what we can do statically? I wonder if refactoring to remove all callers of PointerType::getElementType() (and deleting the API) would be possible as an initial step. Might be simplify the problem in some ways.

[aeubanks]

I was in the process of auditing callers of PointerType::getElementType() and Type::getPointerElementType() to try and fix them up. That would be a good step.

[aeubanks]

As for documentation, I'm currently writing that up separately. I'll hopefully have something fairly soon.

[aeubanks]

https://reviews.llvm.org/D102292 for documentation

[fhahn]

In D101704#2752554, @aeubanks wrote:

https://reviews.llvm.org/D102292 for documentation

It looks like the assert(!isOpaque()) assertion in getElementType triggers when parsing certain bitcode with sret types: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=35708

[aeubanks]

In D101704#2852369, @fhahn wrote:

It looks like the assert(!isOpaque()) assertion in getElementType triggers when parsing certain bitcode with sret types: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=35708

If I had to guess, the fuzzer is creating an opaque pointer with a sret attribute but without the sret type, which should never be emitted. https://reviews.llvm.org/D105138 should have fixed these sorts of issues for opaque pointers with a proper sret attribute with the sret type.

llvm/docs/LangRef.rst

 Pointer types may have an optional address space attribute defining the
 numbered address space where the pointed-to object resides. The default
 address space is number zero. The semantics of non-zero address spaces
 are target-specific.
 
 Note that LLVM does not permit pointers to void (``void*``) nor does it
 permit pointers to labels (``label*``). Use ``i8*`` instead.
 
+LLVM is in the process of transitioning to opaque pointers. Opaque pointers do
+not have a pointee type. Rather, instructions interacting through pointers
+specify the type of the underlying memory they are interacting with. Opaque
+pointers are still in the process of being worked on and are not complete.
+
 :Syntax:
 
 ::
 
       <type> *
+      ptr
 
 :Examples:
 
 +-------------------------+--------------------------------------------------------------------------------------------------------------+
 | ``[4 x i32]*``          | A :ref:`pointer <t_pointer>` to :ref:`array <t_array>` of four ``i32`` values.                               |
 +-------------------------+--------------------------------------------------------------------------------------------------------------+
 | ``i32 (i32*) *``        | A :ref:`pointer <t_pointer>` to a :ref:`function <t_function>` that takes an ``i32*``, returning an ``i32``. |
 +-------------------------+--------------------------------------------------------------------------------------------------------------+
-| ``i32 addrspace(5)*``   | A :ref:`pointer <t_pointer>` to an ``i32`` value that resides in address space #5.                           |
+| ``i32 addrspace(5)*``   | A :ref:`pointer <t_pointer>` to an ``i32`` value that resides in address space 5.                            |
++-------------------------+--------------------------------------------------------------------------------------------------------------+
+| ``ptr``                 | An opaque pointer type to a value that resides in address space 0.                                           |
++-------------------------+--------------------------------------------------------------------------------------------------------------+
+| ``ptr addrspace(5)``    | An opaque pointer type to a value that resides in address space 5.                                           |
 +-------------------------+--------------------------------------------------------------------------------------------------------------+
 
 .. _t_vector:
 
 Vector Type
 """""""""""
 
 :Overview:
 
 A vector type is a simple derived type that represents a vector of

llvm/docs/ReleaseNotes.rst

* Windows Control-flow Enforcement Technology: the ``-ehcontguard`` option now
   set during exception handling.
 
 Changes to the LLVM IR
 ----------------------
 
 * The ``inalloca`` attribute now has a mandatory type field, similar
   to ``byval`` and ``sret``.
 
+* The opaque pointer type ``ptr`` has been introduced. It is still in the
+  process of being worked on and should not be used yet.
+
 Changes to building LLVM
 ------------------------
 
 * The build system now supports building multiple distributions, so that you can
   e.g. have one distribution containing just tools and another for libraries (to
   enable development). See :ref:`Multi-distribution configurations` for details.
 
 Changes to TableGen

llvm/include/llvm/Bitcode/LLVMBitCodes.h

enum TypeCodes {
   TYPE_CODE_STRUCT_ANON = 18,  // STRUCT_ANON: [ispacked, eltty x N]
   TYPE_CODE_STRUCT_NAME = 19,  // STRUCT_NAME: [strchr x N]
   TYPE_CODE_STRUCT_NAMED = 20, // STRUCT_NAMED: [ispacked, eltty x N]
 
   TYPE_CODE_FUNCTION = 21, // FUNCTION: [vararg, retty, paramty x N]
 
   TYPE_CODE_TOKEN = 22, // TOKEN
 
-  TYPE_CODE_BFLOAT = 23, // BRAIN FLOATING POINT
-  TYPE_CODE_X86_AMX = 24 // X86 AMX
+  TYPE_CODE_BFLOAT = 23,  // BRAIN FLOATING POINT
+  TYPE_CODE_X86_AMX = 24, // X86 AMX
+
+  TYPE_CODE_OPAQUE_POINTER = 25, // OPAQUE_POINTER: [addrspace]
 };
 
 enum OperandBundleTagCode {
   OPERAND_BUNDLE_TAG = 1, // TAG: [strchr x N]
 };
 
 enum SyncScopeNameCode {
   SYNC_SCOPE_NAME = 1,

llvm/include/llvm/IR/DerivedTypes.h

 
 inline ElementCount VectorType::getElementCount() const {
   return ElementCount::get(ElementQuantity, isa<ScalableVectorType>(this));
 }
 
 /// Class to represent pointers.
 class PointerType : public Type {
   explicit PointerType(Type *ElType, unsigned AddrSpace);
+  explicit PointerType(LLVMContext &C, unsigned AddrSpace);
 
   Type *PointeeTy;
 
 public:
   PointerType(const PointerType &) = delete;
   PointerType &operator=(const PointerType &) = delete;
 
   /// This constructs a pointer to an object of the specified type in a numbered
   /// address space.
   static PointerType *get(Type *ElementType, unsigned AddressSpace);
+  /// This constructs an opaque pointer to an object in a numbered address
+  /// space.
+  static PointerType *get(LLVMContext &C, unsigned AddressSpace);
 
   /// This constructs a pointer to an object of the specified type in the
-  /// generic address space (address space zero).
+  /// default address space (address space zero).
   static PointerType *getUnqual(Type *ElementType) {
     return PointerType::get(ElementType, 0);
   }
 
-  Type *getElementType() const { return PointeeTy; }
+  /// This constructs an opaque pointer to an object in the
+  /// default address space (address space zero).
+  static PointerType *getUnqual(LLVMContext &C) {
+    return PointerType::get(C, 0);
+  }
+
+  Type *getElementType() const {
+    assert(!isOpaque() && "Attempting to get element type of opaque pointer");
+    return PointeeTy;
+  }
+
+  bool isOpaque() const { return !PointeeTy; }
 
   /// Return true if the specified type is valid as a element type.
   static bool isValidElementType(Type *ElemTy);
 
   /// Return true if we can load or store from a pointer to this type.
   static bool isLoadableOrStorableType(Type *ElemTy);
 
   /// Return the address space of the Pointer type.

llvm/lib/AsmParser/LLLexer.cpp

#define TYPEKEYWORD(STR, LLVMTY)                                               \
   TYPEKEYWORD("x86_fp80",  Type::getX86_FP80Ty(Context));
   TYPEKEYWORD("fp128",     Type::getFP128Ty(Context));
   TYPEKEYWORD("ppc_fp128", Type::getPPC_FP128Ty(Context));
   TYPEKEYWORD("label",     Type::getLabelTy(Context));
   TYPEKEYWORD("metadata",  Type::getMetadataTy(Context));
   TYPEKEYWORD("x86_mmx",   Type::getX86_MMXTy(Context));
   TYPEKEYWORD("x86_amx",   Type::getX86_AMXTy(Context));
   TYPEKEYWORD("token",     Type::getTokenTy(Context));
+  TYPEKEYWORD("ptr", PointerType::getUnqual(Context));
 
 #undef TYPEKEYWORD
 
   // Keywords for instructions.
 #define INSTKEYWORD(STR, Enum)                                                 \
   do {                                                                         \
     if (Keyword == #STR) {                                                     \
       UIntVal = Instruction::Enum;                                             \

llvm/lib/AsmParser/LLParser.cpp

if (!Entry.first) {
       Entry.second = Lex.getLoc();
     }
     Result = Entry.first;
     Lex.Lex();
     break;
   }
   }
 
+  if (Result->isPointerTy() && cast<PointerType>(Result)->isOpaque()) {
+    unsigned AddrSpace;
+    if (parseOptionalAddrSpace(AddrSpace))
+      return true;
+    Result = PointerType::get(getContext(), AddrSpace);
+  }
+
   // parse the type suffixes.
   while (true) {
     switch (Lex.getKind()) {
     // End of type.
     default:
       if (!AllowVoid && Result->isVoidTy())
         return error(TypeLoc, "void type only allowed for function results");
       return false;

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

case bitc::TYPE_CODE_POINTER: { // POINTER: [pointee type] or
         AddressSpace = Record[1];
       ResultTy = getTypeByID(Record[0]);
       if (!ResultTy ||
           !PointerType::isValidElementType(ResultTy))
         return error("Invalid type");
       ResultTy = PointerType::get(ResultTy, AddressSpace);
       break;
     }
+    case bitc::TYPE_CODE_OPAQUE_POINTER: { // OPAQUE_POINTER: [addrspace]
+      if (Record.size() != 1)
+        return error("Invalid record");
+      unsigned AddressSpace = Record[0];
+      ResultTy = PointerType::get(Context, AddressSpace);
+      break;
+    }
     case bitc::TYPE_CODE_FUNCTION_OLD: {
       // Deprecated, but still needed to read old bitcode files.
       // FUNCTION: [vararg, attrid, retty, paramty x N]
       if (Record.size() < 3)
         return error("Invalid record");
       SmallVector<Type*, 8> ArgTys;
       for (unsigned i = 3, e = Record.size(); i != e; ++i) {
         if (Type *T = getTypeByID(Record[i]))

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

void ModuleBitcodeWriter::writeTypeTable() {
 
   // Abbrev for TYPE_CODE_POINTER.
   auto Abbv = std::make_shared<BitCodeAbbrev>();
   Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_POINTER));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
   Abbv->Add(BitCodeAbbrevOp(0));  // Addrspace = 0
   unsigned PtrAbbrev = Stream.EmitAbbrev(std::move(Abbv));
 
+  // Abbrev for TYPE_CODE_OPAQUE_POINTER.
+  Abbv = std::make_shared<BitCodeAbbrev>();
+  Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_OPAQUE_POINTER));
+  Abbv->Add(BitCodeAbbrevOp(0)); // Addrspace = 0
+  unsigned OpaquePtrAbbrev = Stream.EmitAbbrev(std::move(Abbv));
+
   // Abbrev for TYPE_CODE_FUNCTION.
   Abbv = std::make_shared<BitCodeAbbrev>();
   Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_FUNCTION));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));  // isvararg
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
   unsigned FunctionAbbrev = Stream.EmitAbbrev(std::move(Abbv));
 
for (unsigned i = 0, e = TypeList.size(); i != e; ++i) {
     case Type::TokenTyID:     Code = bitc::TYPE_CODE_TOKEN;     break;
     case Type::IntegerTyID:
       // INTEGER: [width]
       Code = bitc::TYPE_CODE_INTEGER;
       TypeVals.push_back(cast<IntegerType>(T)->getBitWidth());
       break;
     case Type::PointerTyID: {
       PointerType *PTy = cast<PointerType>(T);
+      unsigned AddressSpace = PTy->getAddressSpace();
+      if (PTy->isOpaque()) {
+        // OPAQUE_POINTER: [address space]
+        Code = bitc::TYPE_CODE_OPAQUE_POINTER;
+        TypeVals.push_back(AddressSpace);
+        if (AddressSpace == 0)
+          AbbrevToUse = OpaquePtrAbbrev;
+      } else {
         // POINTER: [pointee type, address space]
         Code = bitc::TYPE_CODE_POINTER;
         TypeVals.push_back(VE.getTypeID(PTy->getElementType()));
-      unsigned AddressSpace = PTy->getAddressSpace();
         TypeVals.push_back(AddressSpace);
-      if (AddressSpace == 0) AbbrevToUse = PtrAbbrev;
+        if (AddressSpace == 0)
+          AbbrevToUse = PtrAbbrev;
+      }
       break;
     }
     case Type::FunctionTyID: {
       FunctionType *FT = cast<FunctionType>(T);
       // FUNCTION: [isvararg, retty, paramty x N]
       Code = bitc::TYPE_CODE_FUNCTION;
       TypeVals.push_back(FT->isVarArg());
       TypeVals.push_back(VE.getTypeID(FT->getReturnType()));

llvm/lib/IR/AsmWriter.cpp

case Type::StructTyID: {
     if (I != Type2Number.end())
       OS << '%' << I->second;
     else  // Not enumerated, print the hex address.
       OS << "%\"type " << STy << '\"';
     return;
   }
   case Type::PointerTyID: {
     PointerType *PTy = cast<PointerType>(Ty);
+    if (PTy->isOpaque()) {
+      OS << "ptr";
+      if (unsigned AddressSpace = PTy->getAddressSpace())
+        OS << " addrspace(" << AddressSpace << ')';
+      return;
+    }
     print(PTy->getElementType(), OS);
     if (unsigned AddressSpace = PTy->getAddressSpace())
       OS << " addrspace(" << AddressSpace << ')';
     OS << '*';
     return;
   }
   case Type::ArrayTyID: {
     ArrayType *ATy = cast<ArrayType>(Ty);

llvm/lib/IR/LLVMContextImpl.h

#include "llvm/IR/Metadata.def"
   FunctionTypeSet FunctionTypes;
   using StructTypeSet = DenseSet<StructType *, AnonStructTypeKeyInfo>;
   StructTypeSet AnonStructTypes;
   StringMap<StructType*> NamedStructTypes;
   unsigned NamedStructTypesUniqueID = 0;
 
   DenseMap<std::pair<Type *, uint64_t>, ArrayType*> ArrayTypes;
   DenseMap<std::pair<Type *, ElementCount>, VectorType*> VectorTypes;
+  // TODO: clean up the following after we no longer support non-opaque pointer
+  // types.
   DenseMap<Type*, PointerType*> PointerTypes;  // Pointers in AddrSpace = 0
   DenseMap<std::pair<Type*, unsigned>, PointerType*> ASPointerTypes;
 
   /// ValueHandles - This map keeps track of all of the value handles that are
   /// watching a Value*.  The Value::HasValueHandle bit is used to know
   /// whether or not a value has an entry in this map.
   using ValueHandlesTy = DenseMap<Value *, ValueHandleBase *>;
   ValueHandlesTy ValueHandles;

llvm/lib/IR/Type.cpp

PointerType *PointerType::get(Type *EltTy, unsigned AddressSpace) {
   PointerType *&Entry = AddressSpace == 0 ? CImpl->PointerTypes[EltTy]
      : CImpl->ASPointerTypes[std::make_pair(EltTy, AddressSpace)];
 
   if (!Entry)
     Entry = new (CImpl->Alloc) PointerType(EltTy, AddressSpace);
   return Entry;
 }
 
+PointerType *PointerType::get(LLVMContext &C, unsigned AddressSpace) {
+  LLVMContextImpl *CImpl = C.pImpl;
+
+  // Since AddressSpace #0 is the common case, we special case it.
+  PointerType *&Entry =
+      AddressSpace == 0
+          ? CImpl->PointerTypes[nullptr]
+          : CImpl->ASPointerTypes[std::make_pair(nullptr, AddressSpace)];
+
+  if (!Entry)
+    Entry = new (CImpl->Alloc) PointerType(C, AddressSpace);
+  return Entry;
+}
+
 PointerType::PointerType(Type *E, unsigned AddrSpace)
   : Type(E->getContext(), PointerTyID), PointeeTy(E) {
   ContainedTys = &PointeeTy;
   NumContainedTys = 1;
   setSubclassData(AddrSpace);
 }
 
+PointerType::PointerType(LLVMContext &C, unsigned AddrSpace)
+    : Type(C, PointerTyID), PointeeTy(nullptr) {
+  setSubclassData(AddrSpace);
+}
+
 PointerType *Type::getPointerTo(unsigned addrs) const {
   return PointerType::get(const_cast<Type*>(this), addrs);
 }
 
 bool PointerType::isValidElementType(Type *ElemTy) {
   return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() &&
          !ElemTy->isMetadataTy() && !ElemTy->isTokenTy() &&
-         !ElemTy->isX86_AMXTy();
+         !ElemTy->isX86_AMXTy() &&
+         !(ElemTy->isPointerTy() && cast<PointerType>(ElemTy)->isOpaque());
 }
 
 bool PointerType::isLoadableOrStorableType(Type *ElemTy) {
   return isValidElementType(ElemTy) && !ElemTy->isFunctionTy();
 }

llvm/test/Assembler/invalid-opaque-ptr.ll

+; RUN: not llvm-as < %s -disable-output 2>&1 | FileCheck %s
+
+; CHECK: pointer to this type is invalid
+define void @f(ptr %a) {
+    %b = bitcast ptr %a to ptr*
+    ret void
+}

llvm/test/Assembler/opaque-ptr.ll

+; RUN: llvm-as < %s | llvm-dis | llvm-as | llvm-dis | FileCheck %s
+; RUN: verify-uselistorder %s
+
+; CHECK: define ptr @f(ptr %a) {
+; CHECK:     %b = bitcast ptr %a to ptr
+; CHECK:     ret ptr %b
+define ptr @f(ptr %a) {
+    %b = bitcast ptr %a to ptr
+    ret ptr %b
+}
+
+; CHECK: define ptr @g(ptr addrspace(2) %a) {
+; CHECK:     %b = addrspacecast ptr addrspace(2) %a to ptr
+; CHECK:     ret ptr %b
+define ptr @g(ptr addrspace(2) %a) {
+    %b = addrspacecast ptr addrspace(2) %a to ptr addrspace(0)
+    ret ptr addrspace(0) %b
+}
+
+; CHECK: define ptr addrspace(2) @g2(ptr %a) {
+; CHECK:     %b = addrspacecast ptr %a to ptr addrspace(2)
+; CHECK:     ret ptr addrspace(2) %b
+define ptr addrspace(2) @g2(ptr addrspace(0) %a) {
+    %b = addrspacecast ptr addrspace(0) %a to ptr addrspace(2)
+    ret ptr addrspace(2) %b
+}