Add PointerType analysis for DirectX backend

[beanz]

Summary

As implemented this patch assumes that Typed pointer support remains in
the llvm::PointerType class, however this could be modified to use a
different subclass of llvm::Type that could be disallowed from use in
other contexts.

This does not rely on inserting typed pointers into the Module, it just
uses the llvm::PointerType class to track and unique types.

[python3kgae]

llvm/lib/Target/DirectX/PointerTypeAnalysis.cpp

29

Why not use V->users() when all the access of Use are Use.getUser()?

37

Could a ptr used by AllocaInst?

41

In what case NewPointeeTy will be opaque?

51

In what case the pointee type cannot be determined?

[beanz]

Moving to using dxil::TypedPointerType instead of llvm::PointerType.

Also addressed a few bugs and fleshed out support for function types.

[kuhar]

llvm/lib/Target/DirectX/PointerTypeAnalysis.cpp

62

nit: prefer early exits

97–100

Does this handle global aliases?

llvm/unittests/Target/DirectX/PointerTypeAnalysisTests.cpp

26

nit: Why 8? If the exact small size is not that important or know, I think it's better to use the default one: SmallVector<Type *> Types;

30–35

Is this the same as is_permutation(Types, Expected)?

57–58

I think it might be more helpful to first extract values from the map and then check, something like:

EXPECT_THAT(Ex, UnorderedElementsAreArray(make_second_range(Extracted)));

(I haven't tried to compile it, you may need to tweak this a bit.)

The main difference is that gmock macros explain what went wrong when check fail, e.g., which array elements were different.

62–75

Consider creating a test class that takes care of assembling input IR, creating a context, and running the analysis.

[kuhar]

llvm/unittests/Target/DirectX/PointerTypeAnalysisTests.cpp

57–58

correction, more like: EXPECT_THAT(make_second_range(Map), UnorderedElementsAre(I8Ptr, FnTy));

[beanz]

Use llvm::Any instead of OpaqueDataStore.

[nikic]

llvm/include/llvm/IR/LLVMContext.h

328

The addition of this API should be separated into a separate review (with a unit test).

llvm/include/llvm/IR/Type.h

78

Hrm, it's unfortunate that this need to be exposed here.

llvm/lib/Target/DirectX/DXILPointerType.cpp

36

Why does this need shared_ptr?

nit: Drop braces for single-line if.

llvm/lib/Target/DirectX/DXILPointerType.h

3

File name out of sync, also in the header guard.

47

Do you actually need these helpers? The TODO certainly doesn't make sense...

llvm/lib/Target/DirectX/PointerTypeAnalysis.cpp

34

Are instructions like atomicrmw or cmpxchg relevant here?

44

Why does this one return directly rather than assigning NewPointeeTy?

58

Unnecessary llvm prefix.

90

Does not preserve variadic function type?

91

Spurious semicolon.

llvm/lib/Target/DirectX/PointerTypeAnalysis.h

17

Include doesn't look necessary.

31

Last two lines are outdated.

llvm/unittests/Target/DirectX/PointerTypeAnalysisTests.cpp

21

static and unnecessary llvm prefix.

25

But this doesn't check that the type is actually assigned to the correct value, right? Just that the type is present somewhere?

47

Comment doesn't make sense?

[beanz]

llvm/include/llvm/IR/Type.h

78

Sadly yes. That could be changed, but since we do this for X86 types too it is the current pattern.

llvm/lib/Target/DirectX/DXILPointerType.cpp

36

llvm::Any (and std::any) data types must be copyable, and it returns copies, not the original object. Since I don't want the underlying DenseMaps to be copied around a million times, needs to be a pointer, and unique_ptr isn't copyable.

llvm/lib/Target/DirectX/PointerTypeAnalysis.cpp

34

We don't support those instructions in DXIL. We're not yet handling them in DXILPrepare either, but they'll translate into intrinsics, and we'll need to expand type analysis to cover our intrinsics as they get added.

44

It is returning with a recursive call in the argument. This follows LLVM convention for early returns since the subsequent code isn't applicable.

90

We don't support variadic functions in the source language, so they shouldn't be showing up in the IR. I can add an assert to hard fail that case.

llvm/unittests/Target/DirectX/PointerTypeAnalysisTests.cpp

25

That's a fair observation. I can update the test to be more robust.

[beanz]

Updating based on review feedback.

I should write a printer for the pointer type analysis to aid in debugging and testing, but unless others feel differently I'd like to hold that off to a future patch.

The rewritten test cases are a bit more verbose, but they are more strictly verifying the results.

[nhaehnle]

This seems mostly reasonable. I'd point out that if you had an analysis printer, then test cases could be written much more conveniently as lit tests.

llvm/lib/Target/DirectX/PointerTypeAnalysis.cpp

48

I imagine this should be a TypedPointerType?

llvm/lib/Target/DirectX/PointerTypeAnalysis.h

2

Typo: Analysis

32

Should the namespace be DxilPointerTypeAnalysis since it's target-specific? Also, given that a namespace is used, should the using declaration above be part of the namespace? I don't feel particularly strongly on either point.

[beanz]

llvm/lib/Target/DirectX/PointerTypeAnalysis.cpp

48

It is meant to be the pointee type. In cases where the analysis detects more than one element type it falls back to an i8*, and relies on bitcasts being inserted.

[beanz]

llvm/lib/Target/DirectX/PointerTypeAnalysis.h

32

I put TypedPointerType in the dxil namespace, maybe that makes sense here too.

[beanz]

Updates based on review feedback.

[nhaehnle]

llvm/lib/Target/DirectX/PointerTypeAnalysis.cpp

48

Gotcha, thanks.

llvm/lib/Target/DirectX/PointerTypeAnalysis.h

32

Yeah, that would make sense.

[kuhar]

llvm/lib/IR/AsmWriter.cpp

616

This prints dixl-ptr (0x...) instead of the element type. Is this intentional? Could we have a test for this?

llvm/lib/Target/DirectX/DXILPointerType.h

40

nit: do we need inline here?

llvm/lib/Target/DirectX/PointerTypeAnalysis.cpp

26

Make this a nested if instead. We don't need an else because PointeeTy is already initialized to nullptr above.

32

nit: const auto *User

43

What's the worst case for the number of recursive calls? Could a pathological shader cause a stack overflow?

97–100

ping

103

I find it a bit confusing that we have a helper function handleFunction yet still have to iterate over the function instructions here. Can you add a comment describing what handleFunction does? Or alternatively, could we move this for loop into handleFunction?

llvm/unittests/Target/DirectX/PointerTypeAnalysisTests.cpp

43

IMO it would be more readable/idiomatic to use gmock matchers here, e.g.:

#include "gmock/gmock.h"

using ::testing::Contains;
using ::testing::Pair;

template <typename T> struct IsA {
  friend bool operator==(const Value *V, const IsA &) { return isa<T>(V); }
};

// ...
  ASSERT_EQ(Map.size(), 2u);
  Type *I8Ptr = TypedPointerType::get(Type::getInt8Ty(Context), 0);
  Type *FnTy = FunctionType::get(Type::getInt64Ty(Context), {I8Ptr}, false);
  EXPECT_THAT(Map, Contains(Pair(IsA<Function>(), FnTy)));
  EXPECT_THAT(Map, Contains(Pair(IsA<ReturnInst>(), I8Ptr)))

Or if you would like something with descriptive failure messages:

template <typename T> bool HasType(const Value *V) { return isa<T>(V); }

MATCHER_P2(HasOneEntry, key_predicate, value_type, "") {
  bool Found = false;
  for (auto &KV : arg) {
    if (key_predicate(KV.first)) {
      if (Found) {
        *result_listener << "where duplicate keys were found";
        return false;
      }
      if (KV.second != value_type) {
        *result_listener << "where the key was found but value did not match";
        return false;
      }
      Found = true;
    }
  }

  if (!Found) {
    *result_listener << "where the key is missing";
    return false;
  }
  return true;
}

// ...

  EXPECT_THAT(Map, HasOneEntry(HasType<ReturnInst>, I8Ptr));

209

Could we have a new test case that deals with globals?

[beanz]

Comments below. Updated patch coming shortly.

llvm/lib/IR/AsmWriter.cpp

616

Yea, I did this intentionally so that the llvm::Type class doesn't need to preserve interfaces for typed pointers, and so that the impact of DXILPointerType outside the backend is kept at a minimum.

llvm/lib/Target/DirectX/PointerTypeAnalysis.cpp

43

Since the source language doesn't support pointers, we should rarely see more than two levels of indirection.

97–100

Not yet. I'm not yet handling any globals.

103

The poorly named handleFunction helper just generates the function type. The loop for instructions inside only runs if the return type is an opaque pointer to collect the possible return types. I'll add some comments explaining and rename the function more appropriately.

[beanz]

Updates based on review feedback. Thanks @kuhar!

[kuhar]

llvm/lib/IR/AsmWriter.cpp

616

This is surprising to me, I'd expect types to produce the same strings across multiple runs. Could ignore the addresses altogether, use some stable ID, or add a comment explaining this choice here?

[kuhar]

llvm/lib/Target/DirectX/PointerTypeAnalysis.cpp

43

OK, that makes sense to me. Could you add this as a comment?

[beanz]

Ugh... please hold off reviewing. I somehow messed up the commit update and got a lot of noisy diffs.

[kuhar]

llvm/unittests/Target/DirectX/PointerTypeAnalysisTests.cpp

185–186

nit: I think the convention is that we either have all if/else bodies in a chain with or without braces. So

if (...)
  ...;
else
  ...;

and

if (...) {
  ...
} else {
  ...;
}

are fine, but:

if (...) {
  ...;
} else
  ...;

is not.

[beanz]

This should fix the patch upload, also added in some more of @kuhar's suggestions :).

[kuhar]

LGTM modulo nits. Thanks for the fixes!

llvm/lib/IR/AsmWriter.cpp

616

also this

llvm/lib/Target/DirectX/PointerTypeAnalysis.cpp

22

nit: s/classify/Classifies

43

also this

[beanz]

llvm/lib/IR/AsmWriter.cpp

616

Yea. This is an odd case. I'll add a comment. This isn't the only case where we print the type pointer's address in the dump method. It also happens for StructTypes in some cases.

llvm/include/llvm/IR/LLVMContext.h

 #include "llvm/IR/DiagnosticHandler.h"
 #include "llvm/Support/CBindingWrapping.h"
 #include <cstdint>
 #include <memory>
 #include <string>
 
 namespace llvm {
 
+class Any;
 class DiagnosticInfo;
 enum DiagnosticSeverity : char;
 class Function;
 class Instruction;
 class LLVMContextImpl;
 class Module;
 class OptPassGate;
 template <typename T> class SmallVectorImpl;
#undef LLVM_FIXED_MD_KIND
   /// times, but only with the same value. Note that creating a pointer type or
   /// otherwise querying the opaque pointer mode performs an implicit set to
   /// the default value.
   void setOpaquePointers(bool Enable) const;
 
   /// Whether typed pointers are supported. If false, all pointers are opaque.
   bool supportsTypedPointers() const;
 
+  /// Optionally target-spcific data can be attached to the context for lifetime
+  /// management and bypassing layering restrictions.
+  llvm::Any &getTargetData() const;
+
 private:
   // Module needs access to the add/removeModule methods.
   friend class Module;
 
   /// addModule - Register a module as being instantiated in this context.  If
   /// the context is deleted, the module will be deleted as well.
   void addModule(Module*);
 

llvm/include/llvm/IR/Type.h

enum TypeID {
     VoidTyID,      ///< type with no size
     LabelTyID,     ///< Labels
     MetadataTyID,  ///< Metadata
     X86_MMXTyID,   ///< MMX vectors (64 bits, X86 specific)
     X86_AMXTyID,   ///< AMX vectors (8192 bits, X86 specific)
     TokenTyID,     ///< Tokens
 
     // Derived types... see DerivedTypes.h file.
-    IntegerTyID,       ///< Arbitrary bit width integers
-    FunctionTyID,      ///< Functions
-    PointerTyID,       ///< Pointers
-    StructTyID,        ///< Structures
-    ArrayTyID,         ///< Arrays
-    FixedVectorTyID,   ///< Fixed width SIMD vector type
-    ScalableVectorTyID ///< Scalable SIMD vector type
+    IntegerTyID,        ///< Arbitrary bit width integers
+    FunctionTyID,       ///< Functions
+    PointerTyID,        ///< Pointers
+    StructTyID,         ///< Structures
+    ArrayTyID,          ///< Arrays
+    FixedVectorTyID,    ///< Fixed width SIMD vector type
+    ScalableVectorTyID, ///< Scalable SIMD vector type
+    DXILPointerTyID,    ///< DXIL typed pointer used by DirectX target
   };
 
 private:
   /// This refers to the LLVMContext in which this type was uniqued.
   LLVMContext &Context;
 
   TypeID   ID : 8;            // The current base type of this type.
   unsigned SubclassData : 24; // Space for subclasses to store data.

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

case Type::ScalableVectorTyID: {
       //        [numelts, eltty, scalable]
       Code = bitc::TYPE_CODE_VECTOR;
       TypeVals.push_back(VT->getElementCount().getKnownMinValue());
       TypeVals.push_back(VE.getTypeID(VT->getElementType()));
       if (isa<ScalableVectorType>(VT))
         TypeVals.push_back(true);
       break;
     }
+    case Type::DXILPointerTyID:
+      llvm_unreachable("DXIL pointers cannot be added to IR modules");
     }
 
     // Emit the finished record.
     Stream.EmitRecord(Code, TypeVals, AbbrevToUse);
     TypeVals.clear();
   }
 
   Stream.ExitBlock();

llvm/lib/IR/AsmWriter.cpp

case Type::ScalableVectorTyID: {
     OS << "<";
     if (EC.isScalable())
       OS << "vscale x ";
     OS << EC.getKnownMinValue() << " x ";
     print(PTy->getElementType(), OS);
     OS << '>';
     return;
   }
+  case Type::DXILPointerTyID:
+    // DXIL pointer types are only handled by the DirectX backend. To avoid
+    // extra dependencies we just print the pointer's address here.
+    OS << "dxil-ptr (" << Ty << ")";
+    return;
   }
   llvm_unreachable("Invalid TypeID");
 }
 
 void TypePrinting::printStructBody(StructType *STy, raw_ostream &OS) {
   if (STy->isOpaque()) {
     OS << "opaque";
     return;

llvm/lib/IR/Core.cpp

LLVMTypeKind LLVMGetTypeKind(LLVMTypeRef Ty) {
   case Type::X86_MMXTyID:
     return LLVMX86_MMXTypeKind;
   case Type::X86_AMXTyID:
     return LLVMX86_AMXTypeKind;
   case Type::TokenTyID:
     return LLVMTokenTypeKind;
   case Type::ScalableVectorTyID:
     return LLVMScalableVectorTypeKind;
+  case Type::DXILPointerTyID:
+    llvm_unreachable("DXIL pointers are unsupported via the C API");
   }
   llvm_unreachable("Unhandled TypeID.");
 }
 
 LLVMBool LLVMTypeIsSized(LLVMTypeRef Ty)
 {
     return unwrap(Ty)->isSized();
 }

llvm/lib/IR/LLVMContext.cpp

 
 void LLVMContext::setOpaquePointers(bool Enable) const {
   pImpl->setOpaquePointers(Enable);
 }
 
 bool LLVMContext::supportsTypedPointers() const {
   return !pImpl->getOpaquePointers();
 }
+
+Any &LLVMContext::getTargetData() const {
+  return pImpl->TargetDataStorage;
+}

llvm/lib/IR/LLVMContextImpl.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_IR_LLVMCONTEXTIMPL_H
 #define LLVM_LIB_IR_LLVMCONTEXTIMPL_H
 
 #include "ConstantsContext.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APInt.h"
+#include "llvm/ADT/Any.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
#include "llvm/IR/Metadata.def"
   void setOptPassGate(OptPassGate &);
 
   // TODO: clean up the following after we no longer support non-opaque pointer
   // types.
   bool getOpaquePointers();
   bool hasOpaquePointersValue();
   void setOpaquePointers(bool OP);
 
+  llvm::Any TargetDataStorage;
+
 private:
   Optional<bool> OpaquePointers;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_IR_LLVMCONTEXTIMPL_H

llvm/lib/Target/DirectX/CMakeLists.txt

 add_llvm_component_group(DirectX)
 
 set(LLVM_TARGET_DEFINITIONS DirectX.td)
 
 tablegen(LLVM DirectXGenSubtargetInfo.inc -gen-subtarget)
 
 add_public_tablegen_target(DirectXCommonTableGen)
 
 add_llvm_target(DirectXCodeGen
   DirectXSubtarget.cpp
   DirectXTargetMachine.cpp
+  DXILPointerType.cpp
   DXILPrepare.cpp
+  PointerTypeAnalysis.cpp
 
   LINK_COMPONENTS
   Core
   Support
   DirectXInfo
   DXILBitWriter
 
   ADD_TO_COMPONENT
   DirectX
 )
 
 add_subdirectory(MCTargetDesc)
 add_subdirectory(TargetInfo)
 add_subdirectory(DXILWriter)

llvm/lib/Target/DirectX/DXILPointerType.h

+//===- Target/DirectX/DXILPointerType.h - DXIL Typed Pointer Type ---------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TARGET_DIRECTX_DXILPOINTERTYPE_H
+#define LLVM_TARGET_DIRECTX_DXILPOINTERTYPE_H
+
+#include "llvm/IR/Type.h"
+
+namespace llvm {
+namespace dxil {
+
+// DXIL has typed pointers, this pointer type abstraction is used for tracking
+// in PointerTypeAnalysis and for the bitcode ValueEnumerator
+class TypedPointerType : public Type {
+  explicit TypedPointerType(Type *ElType, unsigned AddrSpace);
+
+  Type *PointeeTy;
+
+public:
+  TypedPointerType(const TypedPointerType &) = delete;
+  TypedPointerType &operator=(const TypedPointerType &) = delete;
+
+  /// This constructs a pointer to an object of the specified type in a numbered
+  /// address space.
+  static TypedPointerType *get(Type *ElementType, unsigned AddressSpace);
+
+  /// Return true if the specified type is valid as a element type.
+  static bool isValidElementType(Type *ElemTy);
+
+  /// Return the address space of the Pointer type.
+  unsigned getAddressSpace() const { return getSubclassData(); }
+
+  Type *getElementType() const { return PointeeTy; }
+
+  /// Implement support type inquiry through isa, cast, and dyn_cast.
+  static bool classof(const Type *T) {
+    return T->getTypeID() == DXILPointerTyID;
+  }
+};
+
+} // namespace dxil
+} // namespace llvm
+
+#endif // LLVM_TARGET_DIRECTX_DXILPOINTERTYPE_H

llvm/lib/Target/DirectX/DXILPointerType.cpp

+//===- Target/DirectX/DXILTypedPointerType.cpp - DXIL Typed Pointer Type
+//-------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//
+//===----------------------------------------------------------------------===//
+
+#include "DXILPointerType.h"
+#include "llvm/ADT/Any.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/IR/LLVMContext.h"
+
+using namespace llvm;
+using namespace llvm::dxil;
+
+class TypedPointerTracking {
+public:
+  TypedPointerTracking() {}
+  DenseMap<Type *, std::unique_ptr<TypedPointerType>> PointerTypes;
+  DenseMap<std::pair<Type *, unsigned>, std::unique_ptr<TypedPointerType>>
+      ASPointerTypes;
+};
+
+TypedPointerType *TypedPointerType::get(Type *EltTy, unsigned AddressSpace) {
+  assert(EltTy && "Can't get a pointer to <null> type!");
+  assert(isValidElementType(EltTy) && "Invalid type for pointer element!");
+
+  llvm::Any &TargetData = EltTy->getContext().getTargetData();
+  if (!TargetData.hasValue())
+    TargetData = Any{std::make_shared<TypedPointerTracking>()};
+
+  assert(any_isa<std::shared_ptr<TypedPointerTracking>>(TargetData) &&
+         "Unexpected target data type");
+
+  std::shared_ptr<TypedPointerTracking> Tracking =
+      any_cast<std::shared_ptr<TypedPointerTracking>>(TargetData);
+
+  // Since AddressSpace #0 is the common case, we special case it.
+  std::unique_ptr<TypedPointerType> &Entry =
+      AddressSpace == 0
+          ? Tracking->PointerTypes[EltTy]
+          : Tracking->ASPointerTypes[std::make_pair(EltTy, AddressSpace)];
+
+  if (!Entry)
+    Entry = std::unique_ptr<TypedPointerType>(
+        new TypedPointerType(EltTy, AddressSpace));
+  return Entry.get();
+}
+
+TypedPointerType::TypedPointerType(Type *E, unsigned AddrSpace)
+    : Type(E->getContext(), DXILPointerTyID), PointeeTy(E) {
+  ContainedTys = &PointeeTy;
+  NumContainedTys = 1;
+  setSubclassData(AddrSpace);
+}
+
+bool TypedPointerType::isValidElementType(Type *ElemTy) {
+  return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() &&
+         !ElemTy->isMetadataTy() && !ElemTy->isTokenTy() &&
+         !ElemTy->isX86_AMXTy();
+}

llvm/lib/Target/DirectX/DXILWriter/DXILBitcodeWriter.cpp

void DXILBitcodeWriter::writeTypeTable() {
   for (Type *T : TypeList) {
     int AbbrevToUse = 0;
     unsigned Code = 0;
 
     switch (T->getTypeID()) {
     case Type::BFloatTyID:
     case Type::X86_AMXTyID:
     case Type::TokenTyID:
+    case Type::DXILPointerTyID:
       llvm_unreachable("These should never be used!!!");
       break;
     case Type::VoidTyID:
       Code = bitc::TYPE_CODE_VOID;
       break;
     case Type::HalfTyID:
       Code = bitc::TYPE_CODE_HALF;
       break;

llvm/lib/Target/DirectX/PointerTypeAnalysis.h

+//===- Target/DirectX/PointerTypeAnalysis.h - PointerType analysis --------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Analysis pass to assign types to opaque pointers.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TARGET_DIRECTX_POINTERTYPEANALYSIS_H
+#define LLVM_TARGET_DIRECTX_POINTERTYPEANALYSIS_H
+
+#include "DXILPointerType.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+namespace dxil {
+
+// Store the underlying type and the number of pointer indirections
+using PointerTypeMap = DenseMap<const Value *, Type *>;
+
+/// An analysis to compute the \c PointerTypes for pointers in a \c Module.
+/// Since this analysis is only run during codegen and the new pass manager
+/// doesn't support codegen passes, this is wrtten as a function in a namespace.
+/// It is very simple to transform it into a proper analysis pass.
+/// This code relies on typed pointers existing as LLVM types, but could be
+/// migrated to a custom Type if PointerType loses typed support.
+namespace PointerTypeAnalysis {
+
+/// Compute the \c PointerTypeMap for the module \c M.
+PointerTypeMap run(const Module &M);
+} // namespace PointerTypeAnalysis
+
+} // namespace dxil
+
+} // namespace llvm
+
+#endif // LLVM_TARGET_DIRECTX_POINTERTYPEANALYSIS_H

llvm/lib/Target/DirectX/PointerTypeAnalysis.cpp

+//===- Target/DirectX/PointerTypeAnalisis.cpp - PointerType analysis ------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Analysis pass to assign types to opaque pointers.
+//
+//===----------------------------------------------------------------------===//
+
+#include "PointerTypeAnalysis.h"
+#include "llvm/IR/Instructions.h"
+
+using namespace llvm;
+using namespace llvm::dxil;
+
+namespace {
+
+// Classifies the type of the value passed in by walking the value's users to
+// find a typed instruction to materialize a type from.
+TypedPointerType *classifyPointerType(const Value *V) {
+  assert(V->getType()->isOpaquePointerTy() &&
+         "classifyPointerType called with non-opaque pointer");
+  Type *PointeeTy = nullptr;
+  if (auto *Inst = dyn_cast<GetElementPtrInst>(V)) {
+    if (!Inst->getResultElementType()->isOpaquePointerTy())
+      PointeeTy = Inst->getResultElementType();
+  } else if (auto *Inst = dyn_cast<AllocaInst>(V)) {
+    PointeeTy = Inst->getAllocatedType();
+  }
+  for (const auto *User : V->users()) {
+    Type *NewPointeeTy = nullptr;
+    if (const auto *Inst = dyn_cast<LoadInst>(User)) {
+      NewPointeeTy = Inst->getType();
+    } else if (const auto *Inst = dyn_cast<StoreInst>(User)) {
+      NewPointeeTy = Inst->getValueOperand()->getType();
+    } else if (const auto *Inst = dyn_cast<GetElementPtrInst>(User)) {
+      NewPointeeTy = Inst->getSourceElementType();
+    }
+    if (NewPointeeTy) {
+      // HLSL doesn't support pointers, so it is unlikely to get more than one
+      // or two levels of indirection in the IR. Because of this, recursion is
+      // pretty safe.
+      if (NewPointeeTy->isOpaquePointerTy())
+        return TypedPointerType::get(classifyPointerType(User),
+                                     V->getType()->getPointerAddressSpace());
+      if (!PointeeTy)
+        PointeeTy = NewPointeeTy;
+      else if (PointeeTy != NewPointeeTy)
+        PointeeTy = Type::getInt8Ty(V->getContext());
+    }
+  }
+  // If we were unable to determine the pointee type, set to i8
+  if (!PointeeTy)
+    PointeeTy = Type::getInt8Ty(V->getContext());
+  return TypedPointerType::get(PointeeTy,
+                               V->getType()->getPointerAddressSpace());
+}
+
+// This function constructs a function type accepting typed pointers. It only
+// handles function arguments and return types, and assigns the function type to
+// the function's value in the type map.
+void classifyFunctionType(const Function &F, PointerTypeMap &Map) {
+  SmallVector<Type *, 8> NewArgs;
+  bool HasOpaqueTy = false;
+  Type *RetTy = F.getReturnType();
+  if (RetTy->isOpaquePointerTy()) {
+    RetTy = nullptr;
+    for (const auto &B : F) {
+      for (const auto &I : B) {
+        if (const auto *RetInst = dyn_cast_or_null<ReturnInst>(&I)) {
+          Type *NewRetTy = classifyPointerType(RetInst->getReturnValue());
+          if (!RetTy)
+            RetTy = NewRetTy;
+          else if (RetTy != NewRetTy)
+            RetTy = TypedPointerType::get(
+                Type::getInt8Ty(I.getContext()),
+                F.getReturnType()->getPointerAddressSpace());
+        }
+      }
+    }
+  }
+  for (auto &A : F.args()) {
+    Type *ArgTy = A.getType();
+    if (ArgTy->isOpaquePointerTy()) {
+      TypedPointerType *NewTy = classifyPointerType(&A);
+      Map[&A] = NewTy;
+      ArgTy = NewTy;
+      HasOpaqueTy = true;
+    }
+    NewArgs.push_back(ArgTy);
+  }
+  if (!HasOpaqueTy)
+    return;
+  Map[&F] = FunctionType::get(RetTy, NewArgs, false);
+}
+} // anonymous namespace
+
+PointerTypeMap PointerTypeAnalysis::run(const Module &M) {
+  PointerTypeMap Map;
+  for (auto &G : M.globals()) {
+    if (G.getType()->isOpaquePointerTy())
+      Map[&G] = classifyPointerType(&G);
+  }
+  for (auto &F : M) {
+    classifyFunctionType(F, Map);
+
+    for (const auto &B : F) {
+      for (const auto &I : B) {
+        if (I.getType()->isOpaquePointerTy())
+          Map[&I] = classifyPointerType(&I);
+      }
+    }
+  }
+
+  return Map;
+}

llvm/unittests/Target/DirectX/CMakeLists.txt

+include_directories(
+  ${LLVM_MAIN_SRC_DIR}/lib/Target/DirectX
+  ${LLVM_BINARY_DIR}/lib/Target/DirectX
+  )
+
+set(LLVM_LINK_COMPONENTS
+  AsmParser
+  Core
+  DirectXCodeGen
+  Support
+)
+
+add_llvm_target_unittest(DirectXTests
+  PointerTypeAnalysisTests.cpp
+  )

llvm/unittests/Target/DirectX/PointerTypeAnalysisTests.cpp

+//===- llvm/unittests/Target/DirectX/PointerTypeAnalysisTests.cpp ---------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "DXILPointerType.h"
+#include "PointerTypeAnalysis.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Type.h"
+#include "llvm/Support/SourceMgr.h"
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+using ::testing::Contains;
+using ::testing::Pair;
+
+using namespace llvm;
+using namespace llvm::dxil;
+
+template <typename T> struct IsA {
+  friend bool operator==(const Value *V, const IsA &) { return isa<T>(V); }
+};
+
+TEST(DXILPointerType, PrintTest) {
+  std::string Buffer;
+  LLVMContext Context;
+  raw_string_ostream OS(Buffer);
+
+  Type *I8Ptr = TypedPointerType::get(Type::getInt8Ty(Context), 0);
+  I8Ptr->print(OS);
+  EXPECT_TRUE(StringRef(Buffer).startswith("dxil-ptr ("));
+}
+
+TEST(PointerTypeAnalysis, DigressToi8) {
+  StringRef Assembly = R"(
+    define i64 @test(ptr %p) {
+      store i32 0, ptr %p
+      %v = load i64, ptr %p
+      ret i64 %v
+    }
+  )";
+
+  LLVMContext Context;
+  SMDiagnostic Error;
+  auto M = parseAssemblyString(Assembly, Error, Context);
+  ASSERT_TRUE(M) << "Bad assembly?";
+
+  PointerTypeMap Map = PointerTypeAnalysis::run(*M);
+  ASSERT_EQ(Map.size(), 2u);
+  Type *I8Ptr = TypedPointerType::get(Type::getInt8Ty(Context), 0);
+  Type *FnTy = FunctionType::get(Type::getInt64Ty(Context), {I8Ptr}, false);
+
+  EXPECT_THAT(Map, Contains(Pair(IsA<Function>(), FnTy)));
+  EXPECT_THAT(Map, Contains(Pair(IsA<Argument>(), I8Ptr)));  
+}
+
+TEST(PointerTypeAnalysis, DiscoverStore) {
+  StringRef Assembly = R"(
+    define i32 @test(ptr %p) {
+      store i32 0, ptr %p
+      ret i32 0
+    }
+  )";
+
+  LLVMContext Context;
+  SMDiagnostic Error;
+  auto M = parseAssemblyString(Assembly, Error, Context);
+  ASSERT_TRUE(M) << "Bad assembly?";
+
+  PointerTypeMap Map = PointerTypeAnalysis::run(*M);
+  ASSERT_EQ(Map.size(), 2u);
+  Type *I32Ptr = TypedPointerType::get(Type::getInt32Ty(Context), 0);
+  Type *FnTy = FunctionType::get(Type::getInt32Ty(Context), {I32Ptr}, false);
+
+  EXPECT_THAT(Map, Contains(Pair(IsA<Function>(), FnTy)));
+  EXPECT_THAT(Map, Contains(Pair(IsA<Argument>(), I32Ptr)));
+}
+
+TEST(PointerTypeAnalysis, DiscoverLoad) {
+  StringRef Assembly = R"(
+    define i32 @test(ptr %p) {
+      %v = load i32, ptr %p
+      ret i32 %v
+    }
+  )";
+
+  LLVMContext Context;
+  SMDiagnostic Error;
+  auto M = parseAssemblyString(Assembly, Error, Context);
+  ASSERT_TRUE(M) << "Bad assembly?";
+
+  PointerTypeMap Map = PointerTypeAnalysis::run(*M);
+  ASSERT_EQ(Map.size(), 2u);
+  Type *I32Ptr = TypedPointerType::get(Type::getInt32Ty(Context), 0);
+  Type *FnTy = FunctionType::get(Type::getInt32Ty(Context), {I32Ptr}, false);
+
+  EXPECT_THAT(Map, Contains(Pair(IsA<Function>(), FnTy)));
+  EXPECT_THAT(Map, Contains(Pair(IsA<Argument>(), I32Ptr)));
+}
+
+TEST(PointerTypeAnalysis, DiscoverGEP) {
+  StringRef Assembly = R"(
+    define ptr @test(ptr %p) {
+      %p2 = getelementptr i64, ptr %p, i64 1
+      ret ptr %p2
+    }
+  )";
+
+  LLVMContext Context;
+  SMDiagnostic Error;
+  auto M = parseAssemblyString(Assembly, Error, Context);
+  ASSERT_TRUE(M) << "Bad assembly?";
+
+  PointerTypeMap Map = PointerTypeAnalysis::run(*M);
+  ASSERT_EQ(Map.size(), 3u);
+
+  Type *I64Ptr = TypedPointerType::get(Type::getInt64Ty(Context), 0);
+  Type *FnTy = FunctionType::get(I64Ptr, {I64Ptr}, false);
+
+  EXPECT_THAT(Map, Contains(Pair(IsA<Function>(), FnTy)));
+  EXPECT_THAT(Map, Contains(Pair(IsA<Argument>(), I64Ptr)));
+  EXPECT_THAT(Map, Contains(Pair(IsA<GetElementPtrInst>(), I64Ptr)));
+}
+
+TEST(PointerTypeAnalysis, TraceIndirect) {
+  StringRef Assembly = R"(
+    define i64 @test(ptr %p) {
+      %p2 = load ptr, ptr %p
+      %v = load i64, ptr %p2
+      ret i64 %v
+    }
+  )";
+
+  LLVMContext Context;
+  SMDiagnostic Error;
+  auto M = parseAssemblyString(Assembly, Error, Context);
+  ASSERT_TRUE(M) << "Bad assembly?";
+
+  PointerTypeMap Map = PointerTypeAnalysis::run(*M);
+  ASSERT_EQ(Map.size(), 3u);
+
+  Type *I64Ptr = TypedPointerType::get(Type::getInt64Ty(Context), 0);
+  Type *I64PtrPtr = TypedPointerType::get(I64Ptr, 0);
+  Type *FnTy = FunctionType::get(Type::getInt64Ty(Context), {I64PtrPtr}, false);
+
+  EXPECT_THAT(Map, Contains(Pair(IsA<Function>(), FnTy)));
+  EXPECT_THAT(Map, Contains(Pair(IsA<Argument>(), I64PtrPtr)));
+  EXPECT_THAT(Map, Contains(Pair(IsA<LoadInst>(), I64Ptr)));
+}
+
+TEST(PointerTypeAnalysis, WithNoOpCasts) {
+  StringRef Assembly = R"(
+    define i64 @test(ptr %p) {
+      %1 = bitcast ptr %p to ptr
+      %2 = bitcast ptr %p to ptr
+      store i32 0, ptr %1, align 4
+      %3 = load i64, ptr %2, align 8
+      ret i64 %3
+    }
+  )";
+
+  LLVMContext Context;
+  SMDiagnostic Error;
+  auto M = parseAssemblyString(Assembly, Error, Context);
+  ASSERT_TRUE(M) << "Bad assembly?";
+
+  PointerTypeMap Map = PointerTypeAnalysis::run(*M);
+  ASSERT_EQ(Map.size(), 4u);
+
+  Type *I8Ptr = TypedPointerType::get(Type::getInt8Ty(Context), 0);
+  Type *I32Ptr = TypedPointerType::get(Type::getInt32Ty(Context), 0);
+  Type *I64Ptr = TypedPointerType::get(Type::getInt64Ty(Context), 0);
+  Type *FnTy = FunctionType::get(Type::getInt64Ty(Context), {I8Ptr}, false);
+
+  EXPECT_THAT(Map, Contains(Pair(IsA<Function>(), FnTy)));
+  EXPECT_THAT(Map, Contains(Pair(IsA<Argument>(), I8Ptr)));
+  EXPECT_THAT(Map, Contains(Pair(IsA<BitCastInst>(), I64Ptr)));
+  EXPECT_THAT(Map, Contains(Pair(IsA<BitCastInst>(), I32Ptr)));
+}