[Bitcode, Type] Assign deterministic IDs to unnamed types at creation time.

[fhahn]

Summary

Currently unnamed types cause problems for overloaded intrinsics like
ssa_copy, because different unnamed types get mangled to the same
string.

This patch introduces an additional map to LLVMContextImpl, which keeps
track of IDs to use when mangling for unnamed types. The IDs are
assigned at type creation time. For textual IR, those types are created
by order of appearance in the LL file. This change also changes the
bitcode writer to write unnamed types in the order they were created,
before other types. This ensures IDs are assigned in the same fashion in
both cases.

[efriedma]

Please add a testcase to make sure we can correctly serialize/deserialize IR containing calls to ssa_copy. I don't think your current approach will work in that case; assigning the identifiers on demand means we won't choose the same identifiers the next time the IR is loaded.

[fhahn]

Thanks Eli! If we serialize a declaration generated in such a way and then de-serialize it again a different pass might generate names in a different order, causing problems. I'll try to address that tomorrow.

[fhahn]

Hm when serializing to bitcode, the order the types are written is based on their uses in functions. That means when reading a bitcode file, the type objects may get created in a different order than defined in the LL file and this is a problem for generating IDs deterministically "on the side".

Currently I am not sure what a good approach/solution would be. Any thoughts/suggestions would be greatly appreciated!

[efriedma]

Maybe we could set names for the types in question? It's kind of awkward, but it should work, I think...

Alternatively, you could avoid generating ssa_copy calls which require mangling non-literal structs; assuming you don't need to ssa_copy first-class aggregates, struct types only show up in pointers, and you can always bitcast pointers to i8*.

[fhahn]

In D48541#1145433, @efriedma wrote:

Maybe we could set names for the types in question? It's kind of awkward, but it should work, I think...

Alternatively, you could avoid generating ssa_copy calls which require mangling non-literal structs; assuming you don't need to ssa_copy first-class aggregates, struct types only show up in pointers, and you can always bitcast pointers to i8*.

Thanks! I think I'll try to go with that approach for now, as it seems to have a much smaller impact. "All" that should be needed is teaching PredicateInfo's users to look through bitcasts in such cases I think.

[fhahn]

I've updated the patch to generate the IDs for unnamed types at creation time and also updated the bitcode writer to write the unamed types first, in the order they were created. This way, the IDs matche between serializing and de-serializing.

This change changes the order types are written to the bytecode file, but that should be a backwards compatible change, because the order only affects mangling with this patch.

[efriedma]

lib/Bitcode/Writer/ValueEnumerator.cpp

330

Changing the order we emit the types should be fine. I'm a little concerned this will make us emit unused types in bitcode.

[fhahn]

lib/Bitcode/Writer/ValueEnumerator.cpp

330

Ah yes, thanks! I'll update the patch, I am just looking for the best way to order the unnamed types as needed while also preserving the required order for type references, which seems slightly tricky.

[chandlerc]

I think this approach is fundamentally flawed. It doesn't achieve its stated goal in full generality.

If I load two modules into the same context and write them to bitcode, this will produce different bitcode than if each module were loaded into a fresh context and written to bitcode. I don't think we want that.

I actually think the whole idea of *any* of the canonical storage for this coming from the context is fundamentally and deeply flawed.

Either the order in which types are created *must not* be observable (IE, we should make it a hard error to mangle them into a function type, which would have prevented the issue that led to this patch in the first place) or we must move the types to be owned by the *module*, not the context. While I'm actually a fan of this (I really dislike the context owning *anything* serialized and deserialized in bitcode) I think it is pretty disruptive change. I think it would be much simpler to just firmly block this from mattering.

[fhahn]

Thanks @chandlerc, I think it is too fragile and I want to avoid unnecessary changes here. To get PredicateInfo working with unnamed types, it is probably easier to use a custom mangling for ssa_copy there; we can rely on the order we create ssa_copy calls and clean up all declarations we created after the predicateinfo is destroyed.

[fhahn]

I have created D49126 to deal with this problem locally in PredicateInfo, which seems the only place where this is currently causing any problems. It is easier to do there, as we can clean up any ssa_copy calls and declarations when destroying PredicateInfo. I also raised https://bugs.llvm.org/show_bug.cgi?id=38117 for a general solution.

include/llvm/IR/Type.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_TYPE_H
 #define LLVM_IR_TYPE_H
 
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/CBindingWrapping.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <cassert>
 #include <cstdint>
 #include <iterator>
public:
   static PointerType *getX86_MMXPtrTy(LLVMContext &C, unsigned AS = 0);
   static PointerType *getIntNPtrTy(LLVMContext &C, unsigned N, unsigned AS = 0);
   static PointerType *getInt1PtrTy(LLVMContext &C, unsigned AS = 0);
   static PointerType *getInt8PtrTy(LLVMContext &C, unsigned AS = 0);
   static PointerType *getInt16PtrTy(LLVMContext &C, unsigned AS = 0);
   static PointerType *getInt32PtrTy(LLVMContext &C, unsigned AS = 0);
   static PointerType *getInt64PtrTy(LLVMContext &C, unsigned AS = 0);
 
+  /// Return a map containing identifiers for the created unnamed types.
+  static MapVector<Type *, unsigned> &getUnnamedTypes(LLVMContext &C);
+
   /// Return a pointer to the current type. This is equivalent to
   /// PointerType::get(Foo, AddrSpace).
   PointerType *getPointerTo(unsigned AddrSpace = 0) const;
 
 private:
   /// Derived types like structures and arrays are sized iff all of the members
   /// of the type are sized as well. Since asking for their size is relatively
   /// uncommon, move this operation out-of-line.

lib/Bitcode/Writer/ValueEnumerator.cpp

 }
 
 ValueEnumerator::ValueEnumerator(const Module &M,
                                  bool ShouldPreserveUseListOrder)
     : ShouldPreserveUseListOrder(ShouldPreserveUseListOrder) {
   if (ShouldPreserveUseListOrder)
     UseListOrders = predictUseListOrder(M);
 
+  // Enumerate unnamed types first, so they are created in a deterministic
+  // order.
+  for (auto &T : Type::getUnnamedTypes(M.getContext()))
+    EnumerateType(T.first);
+
   // Enumerate the global variables.
   for (const GlobalVariable &GV : M.globals())
     EnumerateValue(&GV);
 
   // Enumerate the functions.
   for (const Function & F : M) {
     EnumerateValue(&F);
     EnumerateAttributes(F.getAttributes());

lib/IR/Function.cpp

if (PointerType* PTyp = dyn_cast<PointerType>(Ty)) {
     Result += "p" + utostr(PTyp->getAddressSpace()) +
       getMangledTypeStr(PTyp->getElementType());
   } else if (ArrayType* ATyp = dyn_cast<ArrayType>(Ty)) {
     Result += "a" + utostr(ATyp->getNumElements()) +
       getMangledTypeStr(ATyp->getElementType());
   } else if (StructType *STyp = dyn_cast<StructType>(Ty)) {
     if (!STyp->isLiteral()) {
       Result += "s_";
+      if (STyp->hasName())
         Result += STyp->getName();
+      else {
+        // Different unnamed struct types should get mangled to different names,
+        // so we use the generated ID here.
+        auto &UnnamedIDs = Type::getUnnamedTypes(STyp->getContext());
+        Result += Twine(UnnamedIDs[STyp]).str();
+      }
     } else {
       Result += "sl_";
       for (auto Elem : STyp->elements())
         Result += getMangledTypeStr(Elem);
     }
     // Ensure nested structs are distinguishable.
     Result += "s";
   } else if (FunctionType *FT = dyn_cast<FunctionType>(Ty)) {

lib/IR/LLVMContextImpl.h

 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APInt.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/MapVector.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/BinaryFormat/Dwarf.h"
#include "llvm/IR/Metadata.def"
   DenseMap<unsigned, IntegerType*> IntegerTypes;
 
   using FunctionTypeSet = DenseSet<FunctionType *, FunctionTypeKeyInfo>;
   FunctionTypeSet FunctionTypes;
   using StructTypeSet = DenseSet<StructType *, AnonStructTypeKeyInfo>;
   StructTypeSet AnonStructTypes;
   StringMap<StructType*> NamedStructTypes;
   unsigned NamedStructTypesUniqueID = 0;
-    
+  /// Mapping from unnamed types to a deterministic ID for mangling.
+  /// It is populated at type creation time.
+  MapVector<Type *, unsigned> UnnamedTypeIDs;
+  unsigned UnnamedTypesUniqueID = 0;
+
   DenseMap<std::pair<Type *, uint64_t>, ArrayType*> ArrayTypes;
   DenseMap<std::pair<Type *, unsigned>, VectorType*> VectorTypes;
   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.

lib/IR/Type.cpp

 
 IntegerType *Type::getInt1Ty(LLVMContext &C) { return &C.pImpl->Int1Ty; }
 IntegerType *Type::getInt8Ty(LLVMContext &C) { return &C.pImpl->Int8Ty; }
 IntegerType *Type::getInt16Ty(LLVMContext &C) { return &C.pImpl->Int16Ty; }
 IntegerType *Type::getInt32Ty(LLVMContext &C) { return &C.pImpl->Int32Ty; }
 IntegerType *Type::getInt64Ty(LLVMContext &C) { return &C.pImpl->Int64Ty; }
 IntegerType *Type::getInt128Ty(LLVMContext &C) { return &C.pImpl->Int128Ty; }
 
+MapVector<Type *, unsigned> &Type::getUnnamedTypes(LLVMContext &C) {
+  return C.pImpl->UnnamedTypeIDs;
+}
+
 IntegerType *Type::getIntNTy(LLVMContext &C, unsigned N) {
   return IntegerType::get(C, N);
 }
 
 PointerType *Type::getHalfPtrTy(LLVMContext &C, unsigned AS) {
   return getHalfTy(C)->getPointerTo(AS);
 }
 

 
 //===----------------------------------------------------------------------===//
 // StructType Helper functions.
 
 StructType *StructType::create(LLVMContext &Context, StringRef Name) {
   StructType *ST = new (Context.pImpl->TypeAllocator) StructType(Context);
   if (!Name.empty())
     ST->setName(Name);
+  else {
+    auto *Impl = Context.pImpl;
+    auto I =
+        Type::getUnnamedTypes(Context).insert({ST, Impl->UnnamedTypesUniqueID});
+    if (I.second)
+      Impl->UnnamedTypesUniqueID++;
+  }
   return ST;
 }
 
 StructType *StructType::get(LLVMContext &Context, bool isPacked) {
   return get(Context, None, isPacked);
 }
 
 StructType *StructType::create(LLVMContext &Context, ArrayRef<Type*> Elements,

test/Bitcode/intrinsics-with-unnamed-types.ll

+; RUN: llvm-as -o - %s | llvm-dis -o - 2>&1 | FileCheck %s
+
+; Make sure we can assemble and disassemble IR containing intrinsics with
+; unnamed types.
+
+%1 = type opaque
+%0 = type opaque
+
+; CHECK-LABEL: @f0(
+; CHECK: %c1 = call %0* @llvm.ssa.copy.p0s_1s(%0* %arg)
+; CHECK: %c2 = call %1* @llvm.ssa.copy.p0s_0s(%1* %tmp)
+
+define void @f0(%0* %arg, %1* %tmp) {
+bb:
+  %cmp1 = icmp ne %0* %arg, null
+  %c1 = call %0* @llvm.ssa.copy.p0s_1s(%0* %arg)
+  %c2 = call %1* @llvm.ssa.copy.p0s_0s(%1* %tmp)
+  ret void
+}
+
+declare %0* @llvm.ssa.copy.p0s_1s(%0* returned)
+
+declare %1* @llvm.ssa.copy.p0s_0s(%1* returned)

test/Transforms/Util/PredicateInfo/unnamed-types.ll

+; RUN: opt < %s -print-predicateinfo 2>&1 | FileCheck %s
+
+%1 = type opaque
+%0 = type opaque
+
+; Check we can use ssa.copy with unnamed types.
+
+; CHECK-LABEL: bb:
+; CHECK: Has predicate info
+; CHECK: branch predicate info { TrueEdge: 1 Comparison:  %cmp1 = icmp ne %0* %arg, null Edge: [label %bb,label %bb1] }
+; CHECK-NEXT:  %arg.0 = call %0* @llvm.ssa.copy.p0s_1s(%0* %arg)
+
+; CHECK-LABEL: bb1:
+; CHECK: Has predicate info
+; CHECK-NEXT: branch predicate info { TrueEdge: 0 Comparison:  %cmp2 = icmp ne %1* null, %tmp Edge: [label %bb1,label %bb3] }
+; CHECK-NAME: %tmp.0 = call %1* @llvm.ssa.copy.p0s_0s(%1* %tmp)
+
+define void @f0(%0* %arg, %1* %tmp) {
+bb:
+  %cmp1 = icmp ne %0* %arg, null
+  br i1 %cmp1, label %bb1, label %bb2
+
+bb1:                                              ; preds = %bb
+  %cmp2 = icmp ne %1* null, %tmp
+  br i1 %cmp2, label %bb2, label %bb3
+
+bb2:                                              ; preds = %bb
+  ret void
+
+bb3:                                              ; preds = %bb
+  %u1 = call i8* @fun(%1* %tmp)
+  %tmp2 = bitcast %0* %arg to i8*
+  ret void
+}
+
+declare %0* @llvm.ssa.copy.p0s_1s(%0* returned)
+
+declare %1* @llvm.ssa.copy.p0s_0s(%1* returned)
+
+declare i8* @fun(%1*)