[clang] Fix some clang->llvm type cache invalidation issues

[aeubanks]

Summary

Take the following as an example

struct z {
  z (*p)();
};

z f();

When we attempt to get the LLVM type of f, we recurse into z. z itself
has a function pointer with the same type as f. Given the recursion,
Clang simply treats z::p as a pointer to an empty struct {}*. The
LLVM type of f is as expected. So we have two different potential
LLVM types for a given Clang type. If we store one of those into the
cache, when we access the cache with a different context (e.g. we
are/aren't recursing on z) we may get an incorrect result. There is some
attempt to clear the cache in these cases, but it doesn't seem to handle
all cases.

This change makes it so we only use the cache when we are not in any
sort of function context, i.e. `noRecordsBeingLaidOut() &&
FunctionsBeingProcessed.empty()`, which are the cases where we may
decide to choose a different LLVM type for a given Clang type. LLVM
types for builtin types are never recursive so they're always ok.

This allows us to clear the type cache less often (as seen with the
removal of one of the calls to TypeCache.clear()). We
still need to clear it when we use a placeholder type then replace it
later with the final type and other dependent types need to be
recalculated.

I've added a check that the cached type matches what we compute. It
triggered in this test case without the fix. It's currently not
check-clang clean so it's not on by default for something like expensive
checks builds.

This change uncovered another issue where the LLVM types for an argument
and its local temporary don't match. For example in type-cache-3, when
expanding z::dc's argument into a temporary alloca, we ConvertType() the
type of z::p which is void ({}*)*, which doesn't match the alloca GEP
type of {}*.

No noticeable compile time changes:
https://llvm-compile-time-tracker.com/compare.php?from=3918dd6b8acf8c5886b9921138312d1c638b2937&to=50bdec9836ed40e38ece0657f3058e730adffc4c&stat=instructions

Fixes #53465.

[aeubanks]

update

[aeubanks]

I'm seeing a similar crash with

struct z {
  static z dc(z);
  z (*di)(z);
};
z bar = z::dc({});

going to try to fix that here as well

[aeubanks]

fix more issues, ready to review
I've split the OpenCL change out into D119011, will rebase once that's submitted

[aeubanks]

rebase

[rnk]

This seems unfortunately complex, but I think we can live with it for a year or two.

Is it possible to use the compile time tracker to benchmark if this clang->LLVM type cache actually saves compile time? This change disables the cache pretty often, and I'm wondering if "pretty often" is close enough to "all the time" to let us remove the cache altogether.

---

Since the LLVM type for z::p can't reference z, Clang simply treats z::p as a pointer to an empty struct {}*.

I don't think this is strictly true. LLVM IR struct types can effectively be forward declared when building IR, using the two-phase StructType::create/setBody APIs. Consider the usual linked list example:

struct z { z *next; };
z head;

-->

%struct.z = type { %struct.z* }
@"?head@@3Uz@@A" = dso_local local_unnamed_addr global %struct.z zeroinitializer, align 4, !dbg !0

The IR for function prototypes can work similarly, we could produce this IR struct type:

%struct.z = type { (%struct.z (%struct.z))* }

Maybe that's hard to do today in clang, and ultimately it's probably not worth investing in generating pretty (function) pointer types given the impending transition to opaque pointers.

clang/lib/CodeGen/CodeGenTypes.cpp

34

This cl::opt seems reasonable if we don't expect it to live very long.

[aeubanks]

In D118744#3301977, @rnk wrote:

This seems unfortunately complex, but I think we can live with it for a year or two.

Is it possible to use the compile time tracker to benchmark if this clang->LLVM type cache actually saves compile time? This change disables the cache pretty often, and I'm wondering if "pretty often" is close enough to "all the time" to let us remove the cache altogether.

Yeah I measured disabling the cache and saw some slight regressions.

---

Since the LLVM type for z::p can't reference z, Clang simply treats z::p as a pointer to an empty struct {}*.

I don't think this is strictly true. LLVM IR struct types can effectively be forward declared when building IR, using the two-phase StructType::create/setBody APIs. Consider the usual linked list example:

struct z { z *next; };
z head;

-->

%struct.z = type { %struct.z* }
@"?head@@3Uz@@A" = dso_local local_unnamed_addr global %struct.z zeroinitializer, align 4, !dbg !0

Ah you're right, I'll update the description

The IR for function prototypes can work similarly, we could produce this IR struct type:

%struct.z = type { (%struct.z (%struct.z))* }

Maybe that's hard to do today in clang, and ultimately it's probably not worth investing in generating pretty (function) pointer types given the impending transition to opaque pointers.

There's a lot of code around choosing proper types (it's not as simple as mapping a C++ struct z to LLVM %struct.z), as you said it would take some time and it's probably not worth it given opaque pointers.

[rnk]

lgtm

clang/lib/CodeGen/CGBuilder.h

 //===-- CGBuilder.h - Choose IRBuilder implementation  ----------*- C++ -*-===//
 //
 // 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_CLANG_LIB_CODEGEN_CGBUILDER_H
 #define LLVM_CLANG_LIB_CODEGEN_CGBUILDER_H
 
-#include "llvm/IR/DataLayout.h"
-#include "llvm/IR/IRBuilder.h"
 #include "Address.h"
 #include "CodeGenTypeCache.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Type.h"
 
 namespace clang {
 namespace CodeGen {
 
 class CodeGenFunction;
 
 /// This is an IRBuilder insertion helper that forwards to
 /// CodeGenFunction::InsertHelper, which adds necessary metadata to

clang/lib/CodeGen/CGCall.cpp

 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Assumptions.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/Type.h"
 #include "llvm/Transforms/Utils/Local.h"
 using namespace clang;
 using namespace CodeGen;
 
 /***/
 
 unsigned CodeGenTypes::ClangCallConvToLLVMCallConv(CallingConv CC) {
   switch (CC) {
void CodeGenFunction::ExpandTypeFromArgs(QualType Ty, LValue LV,
   } else if (isa<ComplexExpansion>(Exp.get())) {
     auto realValue = &*AI++;
     auto imagValue = &*AI++;
     EmitStoreOfComplex(ComplexPairTy(realValue, imagValue), LV, /*init*/ true);
   } else {
     // Call EmitStoreOfScalar except when the lvalue is a bitfield to emit a
     // primitive store.
     assert(isa<NoExpansion>(Exp.get()));
-    if (LV.isBitField())
-      EmitStoreThroughLValue(RValue::get(&*AI++), LV);
-    else
-      EmitStoreOfScalar(&*AI++, LV);
+    llvm::Value *Arg = &*AI++;
+    if (LV.isBitField()) {
+      EmitStoreThroughLValue(RValue::get(Arg), LV);
+    } else {
+      // TODO: currently there are some places are inconsistent in what LLVM
+      // pointer type they use (see D118744). Once clang uses opaque pointers
+      // all LLVM pointer types will be the same and we can remove this check.
+      if (Arg->getType()->isPointerTy()) {
+        Address Addr = LV.getAddress(*this);
+        Arg = Builder.CreateBitCast(Arg, Addr.getElementType());
+      }
+      EmitStoreOfScalar(Arg, LV);
+    }
   }
 }
 
 void CodeGenFunction::ExpandTypeToArgs(
     QualType Ty, CallArg Arg, llvm::FunctionType *IRFuncTy,
     SmallVectorImpl<llvm::Value *> &IRCallArgs, unsigned &IRCallArgPos) {
   auto Exp = getTypeExpansion(Ty, getContext());
   if (auto CAExp = dyn_cast<ConstantArrayExpansion>(Exp.get())) {

clang/lib/CodeGen/CodeGenTypes.cpp

 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/RecordLayout.h"
 #include "clang/CodeGen/CGFunctionInfo.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Module.h"
+
 using namespace clang;
 using namespace CodeGen;
 
+#ifndef NDEBUG
+#include "llvm/Support/CommandLine.h"
+// TODO: turn on by default when defined(EXPENSIVE_CHECKS) once check-clang is
+// -verify-type-cache clean.
+static llvm::cl::opt<bool> VerifyTypeCache(
+    "verify-type-cache",
+    llvm::cl::desc("Verify that the type cache matches the computed type"),
+    llvm::cl::init(false), llvm::cl::Hidden);
+#endif
+
 CodeGenTypes::CodeGenTypes(CodeGenModule &cgm)
   : CGM(cgm), Context(cgm.getContext()), TheModule(cgm.getModule()),
     Target(cgm.getTarget()), TheCXXABI(cgm.getCXXABI()),
     TheABIInfo(cgm.getTargetCodeGenInfo().getABIInfo()) {
   SkippedLayout = false;
 }
 
 CodeGenTypes::~CodeGenTypes() {
llvm::Type *CodeGenTypes::ConvertFunctionTypeInternal(QualType QFT) {
   } else {
 
     // Otherwise, we're good to go, go ahead and convert it.
     ResultType = GetFunctionType(*FI);
   }
 
   RecordsBeingLaidOut.erase(Ty);
 
-  if (SkippedLayout)
-    TypeCache.clear();
-
   if (RecordsBeingLaidOut.empty())
     while (!DeferredRecords.empty())
       ConvertRecordDeclType(DeferredRecords.pop_back_val());
   return ResultType;
 }
 
 /// ConvertType - Convert the specified type to its LLVM form.
 llvm::Type *CodeGenTypes::ConvertType(QualType T) {
if (T->isCUDADeviceBuiltinSurfaceType()) {
         return Ty;
     }
   }
 
   // RecordTypes are cached and processed specially.
   if (const RecordType *RT = dyn_cast<RecordType>(Ty))
     return ConvertRecordDeclType(RT->getDecl());
 
-  // See if type is already cached.
-  llvm::DenseMap<const Type *, llvm::Type *>::iterator TCI = TypeCache.find(Ty);
-  // If type is found in map then use it. Otherwise, convert type T.
+  // The LLVM type we return for a given Clang type may not always be the same,
+  // most notably when dealing with recursive structs. We mark these potential
+  // cases with ShouldUseCache below. Builtin types cannot be recursive.
+  // TODO: when clang uses LLVM opaque pointers we won't be able to represent
+  // recursive types with LLVM types, making this logic much simpler.
+  llvm::Type *CachedType = nullptr;
+  bool ShouldUseCache =
+      Ty->isBuiltinType() ||
+      (noRecordsBeingLaidOut() && FunctionsBeingProcessed.empty());
+  if (ShouldUseCache) {
+    llvm::DenseMap<const Type *, llvm::Type *>::iterator TCI =
+        TypeCache.find(Ty);
     if (TCI != TypeCache.end())
-    return TCI->second;
+      CachedType = TCI->second;
+    if (CachedType) {
+#ifndef NDEBUG
+      if (!VerifyTypeCache)
+        return CachedType;
+#else
+      return CachedType;
+#endif
+    }
+  }
 
   // If we don't have it in the cache, convert it now.
   llvm::Type *ResultType = nullptr;
   switch (Ty->getTypeClass()) {
   case Type::Record: // Handled above.
 #define TYPE(Class, Base)
 #define ABSTRACT_TYPE(Class, Base)
 #define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
case Type::BitInt: {
     const auto &EIT = cast<BitIntType>(Ty);
     ResultType = llvm::Type::getIntNTy(getLLVMContext(), EIT->getNumBits());
     break;
   }
   }
 
   assert(ResultType && "Didn't convert a type?");
 
+#ifndef NDEBUG
+  if (CachedType) {
+    assert(CachedType == ResultType &&
+           "Cached type doesn't match computed type");
+  }
+#endif
+
+  if (ShouldUseCache)
     TypeCache[Ty] = ResultType;
   return ResultType;
 }
 
 bool CodeGenModule::isPaddedAtomicType(QualType type) {
   return isPaddedAtomicType(type->castAs<AtomicType>());
 }
 
 bool CodeGenModule::isPaddedAtomicType(const AtomicType *type) {

clang/test/CodeGenCXX/type-cache-2.cpp

+// RUN: %clang_cc1 -mllvm -verify-type-cache -emit-llvm %s -o - -triple i386-pc-windows-msvc19.16.0 | FileCheck %s
+// REQUIRES: asserts, x86-registered-target
+
+// CHECK: call void @"?dc@z@@SAXU1@@Z"
+struct z {
+  static void dc(z);
+  void (*p)(z);
+};
+
+void f() {
+  z::dc({});
+}

clang/test/CodeGenCXX/type-cache-3.cpp

+// RUN: %clang_cc1 -mllvm -verify-type-cache -emit-llvm %s -o - -triple i386-pc-windows-msvc19.16.0 | FileCheck %s
+// REQUIRES: asserts, x86-registered-target
+
+// CHECK-LABEL: define {{.*}}@"?f@@YAXXZ"(
+// CHECK: call void @"?dc@z@@SAXU1@@Z"
+
+// CHECK-LABEL: define {{.*}}@"?dc@z@@SAXU1@@Z"(
+// CHECK: store void ({}*)* %{{.*}}, void ({}*)** %{{.*}}
+struct z {
+  static void dc(z) {}
+  void (*p)(z);
+};
+
+void f() {
+  z::dc({});
+}

clang/test/CodeGenCXX/type-cache.cpp

+// RUN: %clang_cc1 -mllvm -verify-type-cache -emit-llvm %s -o - -triple i386-pc-windows-msvc19.16.0 | FileCheck %s
+// REQUIRES: asserts, x86-registered-target
+
+// CHECK: call {}* @"?f@@YA?AUz@@XZ"()
+
+struct z {
+  z (*p)();
+};
+
+z f();
+
+void g() {
+  f();
+}