use zeroinitializer for (trailing zero portion of) large array initializers more reliably

[rsmith]

Summary

Clang has two different ways it emits array constants (from InitListExprs and from APValues), and both had some ability to emit zeroinitializer, but neither was able to catch all cases where we could use zeroinitializer reliably. In particular, emitting from an APValue would fail to notice if all the explicit array elements happened to be zero. In addition, for large arrays where only an initial portion has an explicit initializer, we would emit the complete initializer (which could be huge) rather than emitting only the non-zero portion. With this change, when the element would have a suffix of more than 8 zero elements, we emit the array constant as a packed struct of its initial portion followed by a zeroinitializer constant for the trailing zero portion.

In passing, I found a bug where SemaInit would sometimes walk the entire array when checking an initializer that only covers the first few elements; that's fixed here to unblock testing of the rest.

[sepavloff]

Now I understand your idea about moving the logic to tryEmitPrivateForMemory. Indeed it is more general and consistent solution.
Thank you.

lib/CodeGen/CGExprConstant.cpp

643

s/Figre/Figure/ ?

903

The check for fillC != nullptr here is redundant, it was checked few lines above.

test/CodeGenCXX/cxx11-initializer-aggregate.cpp

83

Array definitions:

char data_8[1000 * 1000 * 1000] = {};
int (&&data_9)[1000 * 1000 * 1000] = {0};

also compile successfully with this patch and hang compiler without it.

[rjmccall]

I like this approach a lot.

lib/CodeGen/CGExprConstant.cpp

675

Why std::vector?

[rsmith]

lib/CodeGen/CGExprConstant.cpp

675

Only because this was extracted from the old version of the code. Switched to a SmallVector.

test/CodeGenCXX/cxx11-initializer-aggregate.cpp

83

I added these test cases, thanks!

[rjmccall]

LGTM, thanks!

lib/CodeGen/CGExprConstant.cpp

auto GV = new llvm::GlobalVariable(CGM.getModule(), C->getType(),
                                      llvm::GlobalVariable::NotThreadLocal,
                     CGM.getContext().getTargetAddressSpace(addressSpace));
   emitter.finalize(GV);
   GV->setAlignment(Align.getQuantity());
   CGM.setAddrOfConstantCompoundLiteral(E, GV);
   return ConstantAddress(GV, Align);
 }
 
+static llvm::Constant *
+EmitArrayConstant(llvm::ArrayType *PreferredArrayType,
+                  llvm::Type *CommonElementType, unsigned ArrayBound,
+                  SmallVectorImpl<llvm::Constant *> &Elements,
+                  llvm::Constant *Filler) {
+  // Figure out how long the initial prefix of non-zero elements is.
+  unsigned NonzeroLength = ArrayBound;
+  if (Elements.size() < NonzeroLength && Filler->isNullValue())
+    NonzeroLength = Elements.size();
+  if (NonzeroLength == Elements.size()) {
+    while (NonzeroLength > 0 && Elements[NonzeroLength - 1]->isNullValue())
+      --NonzeroLength;
+  }
+
+  if (NonzeroLength == 0)
+    return llvm::ConstantAggregateZero::get(PreferredArrayType);
+
+  // If there's not many trailing zero elements, just emit an array
+  // constant.
+  if (NonzeroLength + 8 >= ArrayBound && CommonElementType) {
+    Elements.resize(ArrayBound, Filler);
+    return llvm::ConstantArray::get(
+        llvm::ArrayType::get(CommonElementType, ArrayBound), Elements);
+  }
+
+  // Add a zeroinitializer array filler if we have trailing zeroes.
+  if (unsigned TrailingZeroes = ArrayBound - NonzeroLength) {
+    assert(Elements.size() >= NonzeroLength &&
+           "missing initializer for non-zero element");
+    Elements.resize(NonzeroLength + 1);
+    auto *FillerType = PreferredArrayType->getElementType();
+    if (TrailingZeroes > 1)
+      FillerType = llvm::ArrayType::get(FillerType, TrailingZeroes);
+    Elements.back() = llvm::ConstantAggregateZero::get(FillerType);
+  }
+
+  // We have mixed types. Use a packed struct.
+  llvm::SmallVector<llvm::Type *, 16> Types;
+  Types.reserve(Elements.size());
+  for (llvm::Constant *Elt : Elements)
+    Types.push_back(Elt->getType());
+  llvm::StructType *SType =
+      llvm::StructType::get(PreferredArrayType->getContext(), Types, true);
+  return llvm::ConstantStruct::get(SType, Elements);
+}
+
 /// This class only needs to handle two cases:
 /// 1) Literals (this is used by APValue emission to emit literals).
 /// 2) Arrays, structs and unions (outside C++11 mode, we don't currently
 ///    constant fold these types).
 class ConstExprEmitter :
   public StmtVisitor<ConstExprEmitter, llvm::Constant*, QualType> {
   CodeGenModule &CGM;
   ConstantEmitter &Emitter;
public:
   llvm::Constant *VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *E,
                                                 QualType T) {
     return Visit(E->GetTemporaryExpr(), T);
   }
 
   llvm::Constant *EmitArrayInitialization(InitListExpr *ILE, QualType T) {
     llvm::ArrayType *AType =
         cast<llvm::ArrayType>(ConvertType(ILE->getType()));
-    llvm::Type *ElemTy = AType->getElementType();
     unsigned NumInitElements = ILE->getNumInits();
     unsigned NumElements = AType->getNumElements();
 
     // Initialising an array requires us to automatically
     // initialise any elements that have not been initialised explicitly
     unsigned NumInitableElts = std::min(NumInitElements, NumElements);
 
     QualType EltType = CGM.getContext().getAsArrayType(T)->getElementType();
 
     // Initialize remaining array elements.
-    llvm::Constant *fillC;
-    if (Expr *filler = ILE->getArrayFiller())
+    llvm::Constant *fillC = nullptr;
+    if (Expr *filler = ILE->getArrayFiller()) {
       fillC = Emitter.tryEmitAbstractForMemory(filler, EltType);
-    else
-      fillC = Emitter.emitNullForMemory(EltType);
       if (!fillC)
         return nullptr;
-
-    // Try to use a ConstantAggregateZero if we can.
-    if (fillC->isNullValue() && !NumInitableElts)
-      return llvm::ConstantAggregateZero::get(AType);
+    }
 
     // Copy initializer elements.
     SmallVector<llvm::Constant*, 16> Elts;
-    Elts.reserve(std::max(NumInitableElts, NumElements));
+    if (fillC && fillC->isNullValue())
+      Elts.reserve(NumInitableElts + 1);
+    else
+      Elts.reserve(NumElements);
 
-    bool RewriteType = false;
-    bool AllNullValues = true;
+    llvm::Type *CommonElementType = nullptr;
     for (unsigned i = 0; i < NumInitableElts; ++i) {
       Expr *Init = ILE->getInit(i);
       llvm::Constant *C = Emitter.tryEmitPrivateForMemory(Init, EltType);
       if (!C)
         return nullptr;
-      RewriteType |= (C->getType() != ElemTy);
+      if (i == 0)
+        CommonElementType = C->getType();
+      else if (C->getType() != CommonElementType)
+        CommonElementType = nullptr;
       Elts.push_back(C);
-      if (AllNullValues && !C->isNullValue())
-        AllNullValues = false;
     }
 
-    // If all initializer elements are "zero," then avoid storing NumElements
-    // instances of the zero representation.
-    if (AllNullValues)
-      return llvm::ConstantAggregateZero::get(AType);
-
-    RewriteType |= (fillC->getType() != ElemTy);
-    Elts.resize(NumElements, fillC);
-
-    if (RewriteType) {
-      // FIXME: Try to avoid packing the array
-      std::vector<llvm::Type*> Types;
-      Types.reserve(Elts.size());
-      for (unsigned i = 0, e = Elts.size(); i < e; ++i)
-        Types.push_back(Elts[i]->getType());
-      llvm::StructType *SType = llvm::StructType::get(AType->getContext(),
-                                                            Types, true);
-      return llvm::ConstantStruct::get(SType, Elts);
-    }
-
-    return llvm::ConstantArray::get(AType, Elts);
+    return EmitArrayConstant(AType, CommonElementType, NumElements, Elts,
+                             fillC);
   }
 
   llvm::Constant *EmitRecordInitialization(InitListExpr *ILE, QualType T) {
     return ConstStructBuilder::BuildStruct(Emitter, ILE, T);
   }
 
   llvm::Constant *VisitImplicitValueInitExpr(ImplicitValueInitExpr* E,
                                              QualType T) {
case APValue::Union:
     return ConstStructBuilder::BuildStruct(*this, Value, DestType);
   case APValue::Array: {
     const ArrayType *CAT = CGM.getContext().getAsArrayType(DestType);
     unsigned NumElements = Value.getArraySize();
     unsigned NumInitElts = Value.getArrayInitializedElts();
 
     // Emit array filler, if there is one.
     llvm::Constant *Filler = nullptr;
-    if (Value.hasArrayFiller())
+    if (Value.hasArrayFiller()) {
       Filler = tryEmitAbstractForMemory(Value.getArrayFiller(),
                                         CAT->getElementType());
+      if (!Filler)
+        return nullptr;
+    }
 
     // Emit initializer elements.
     llvm::Type *CommonElementType =
         CGM.getTypes().ConvertType(CAT->getElementType());
-
-    // Try to use a ConstantAggregateZero if we can.
-    if (Filler && Filler->isNullValue() && !NumInitElts) {
-      llvm::ArrayType *AType =
-          llvm::ArrayType::get(CommonElementType, NumElements);
-      return llvm::ConstantAggregateZero::get(AType);
-    }
+    llvm::ArrayType *PreferredArrayType =
 
     SmallVector<llvm::Constant*, 16> Elts;
+    if (Filler && Filler->isNullValue())
+      Elts.reserve(NumInitElts + 1);
+    else
       Elts.reserve(NumElements);
-    for (unsigned I = 0; I < NumElements; ++I) {
-      llvm::Constant *C = Filler;
-      if (I < NumInitElts) {
-        C = tryEmitPrivateForMemory(Value.getArrayInitializedElt(I),
-                                    CAT->getElementType());
-      } else if (!Filler) {
-        assert(Value.hasArrayFiller() &&
-               "Missing filler for implicit elements of initializer");
-        C = tryEmitPrivateForMemory(Value.getArrayFiller(),
-                                    CAT->getElementType());
-      }
+
+    for (unsigned I = 0; I < NumInitElts; ++I) {
+      llvm::Constant *C = tryEmitPrivateForMemory(
+          Value.getArrayInitializedElt(I), CAT->getElementType());
       if (!C) return nullptr;
 
       if (I == 0)
         CommonElementType = C->getType();
       else if (C->getType() != CommonElementType)
         CommonElementType = nullptr;
       Elts.push_back(C);
     }
 
-    if (!CommonElementType) {
-      // FIXME: Try to avoid packing the array
-      std::vector<llvm::Type*> Types;
-      Types.reserve(NumElements);
-      for (unsigned i = 0, e = Elts.size(); i < e; ++i)
-        Types.push_back(Elts[i]->getType());
-      llvm::StructType *SType =
-        llvm::StructType::get(CGM.getLLVMContext(), Types, true);
-      return llvm::ConstantStruct::get(SType, Elts);
-    }
-
-    llvm::ArrayType *AType =
-      llvm::ArrayType::get(CommonElementType, NumElements);
-    return llvm::ConstantArray::get(AType, Elts);
+    return EmitArrayConstant(PreferredArrayType, CommonElementType, NumElements,
+                             Elts, Filler);
   }
   case APValue::MemberPointer:
     return CGM.getCXXABI().EmitMemberPointer(Value, DestType);
   }
   llvm_unreachable("Unknown APValue kind");
 }
 
 llvm::GlobalVariable *CodeGenModule::getAddrOfConstantCompoundLiteralIfEmitted(

lib/Sema/SemaInit.cpp

InitListChecker::FillInEmptyInitializations(const InitializedEntity &Entity,
   for (unsigned Init = 0; Init != NumElements; ++Init) {
     if (hadError)
       return;
 
     if (ElementEntity.getKind() == InitializedEntity::EK_ArrayElement ||
         ElementEntity.getKind() == InitializedEntity::EK_VectorElement)
       ElementEntity.setElementIndex(Init);
 
+    if (Init >= NumInits && ILE->hasArrayFiller())
+      return;
+
     Expr *InitExpr = (Init < NumInits ? ILE->getInit(Init) : nullptr);
     if (!InitExpr && Init < NumInits && ILE->hasArrayFiller())
       ILE->setInit(Init, ILE->getArrayFiller());
     else if (!InitExpr && !ILE->hasArrayFiller()) {
       Expr *Filler = nullptr;
 
       if (FillWithNoInit)
         Filler = new (SemaRef.Context) NoInitExpr(ElementType);

test/CodeGen/init.c

 struct a7 {
   int  b;
   char v[];
 };
 
 struct a7 test7 = { .b = 0, .v = "bar" };
 
 
+// CHECK-DAG: @huge_array = global {{.*}} <{ i32 1, i32 0, i32 2, i32 0, i32 3, [999999995 x i32] zeroinitializer }>
+int huge_array[1000000000] = {1, 0, 2, 0, 3, 0, 0, 0};
+
+// CHECK-DAG: @huge_struct = global {{.*}} { i32 1, <{ i32, [999999999 x i32] }> <{ i32 2, [999999999 x i32] zeroinitializer }> }
+struct Huge {
+  int a;
+  int arr[1000 * 1000 * 1000];
+} huge_struct = {1, {2, 0, 0, 0}};
+
+
 // PR279 comment #3
 char test8(int X) {
   char str[100000] = "abc"; // tail should be memset.
   return str[X];
 // CHECK: @test8(
 // CHECK: call void @llvm.memset
 // CHECK: store i8 97
 // CHECK: store i8 98

test/CodeGenCXX/cxx11-initializer-aggregate.cpp

 // RUN: %clang_cc1 -std=c++11 -S -emit-llvm -o - %s -triple x86_64-linux-gnu | FileCheck %s
 
 struct A { int a, b; int f(); };
 
 namespace NonAggregateCopyInAggregateInit { // PR32044
   struct A { constexpr A(int n) : x(n), y() {} int x, y; } extern a;
   // CHECK-DAG: @_ZN31NonAggregateCopyInAggregateInit1bE = global %{{.*}} { %[[A:.*]]* @_ZN31NonAggregateCopyInAggregateInit1aE }
   struct B { A &p; } b{{a}};
   // CHECK-DAG: @_ZGRN31NonAggregateCopyInAggregateInit1cE_ = internal global %[[A]] { i32 1, i32 0 }
   // CHECK-DAG: @_ZN31NonAggregateCopyInAggregateInit1cE = global %{{.*}} { %{{.*}}* @_ZGRN31NonAggregateCopyInAggregateInit1cE_ }
   struct C { A &&p; } c{{1}};
 }
 
+namespace NearlyZeroInit {
+  // CHECK-DAG: @_ZN14NearlyZeroInit1aE = global {{.*}} <{ i32 1, i32 2, i32 3, [120 x i32] zeroinitializer }>
+  int a[123] = {1, 2, 3};
+  // CHECK-DAG: @_ZN14NearlyZeroInit1bE = global {{.*}} { i32 1, <{ i32, [2147483647 x i32] }> <{ i32 2, [2147483647 x i32] zeroinitializer }> }
+  struct B { int n; int arr[1024 * 1024 * 1024 * 2u]; } b = {1, {2}};
+}
+
 // CHECK-LABEL: define {{.*}}@_Z3fn1i(
 int fn1(int x) {
   // CHECK: %[[INITLIST:.*]] = alloca %struct.A
   // CHECK: %[[A:.*]] = getelementptr inbounds %struct.A, %struct.A* %[[INITLIST]], i32 0, i32 0
   // CHECK: store i32 %{{.*}}, i32* %[[A]], align 4
   // CHECK: %[[B:.*]] = getelementptr inbounds %struct.A, %struct.A* %[[INITLIST]], i32 0, i32 1
   // CHECK: store i32 5, i32* %[[B]], align 4
   // CHECK: call i32 @_ZN1A1fEv(%struct.A* %[[INITLIST]])

 // CHECK: call i32 @__cxa_atexit(
 namespace NonTrivialInit {
   struct A { A(); A(const A&) = delete; ~A(); };
   struct B { A a[20]; };
   // NB, this must be large enough to be worth memsetting for this test to be
   // meaningful.
   B b[30] = {};
 }
+
+namespace ZeroInit {
+  enum { Zero, One };
+  constexpr int zero() { return 0; }
+  constexpr int *null() { return nullptr; }
+  struct Filler {
+    int x;
+    Filler();
+  };
+  struct S1 {
+    int x;
+  };
+
+  // These declarations, if implemented elementwise, require huge
+  // amout of memory and compiler time.
+  unsigned char data_1[1024 * 1024 * 1024 * 2u] = { 0 };
+  unsigned char data_2[1024 * 1024 * 1024 * 2u] = { Zero };
+  unsigned char data_3[1024][1024][1024] = {{{0}}};
+  unsigned char data_4[1024 * 1024 * 1024 * 2u] = { zero() };
+  int *data_5[1024 * 1024 * 512] = { nullptr };
+  int *data_6[1024 * 1024 * 512] = { null() };
+  struct S1 data_7[1024 * 1024 * 512] = {{0}};
+  char data_8[1000 * 1000 * 1000] = {};
+  int (&&data_9)[1000 * 1000 * 1000] = {0};
+  unsigned char data_10[1024 * 1024 * 1024 * 2u] = { 1 };
+  unsigned char data_11[1024 * 1024 * 1024 * 2u] = { One };
+  unsigned char data_12[1024][1024][1024] = {{{1}}};
+
+  // This variable must be initialized elementwise.
+  Filler data_e1[1024] = {};
+  // CHECK: getelementptr inbounds {{.*}} @_ZN8ZeroInit7data_e1E
+}

test/SemaCXX/aggregate-initialization.cpp

#if __cplusplus >= 201703L
   // pattern becomes idiomatic, it would be reasonable to suppress the
   // warning here too.
   template<typename T, int N> struct JustABaseClass : StdArray<T, N> {};
   JustABaseClass<int, 3> w = {1, 2, 3}; // expected-warning {{suggest braces}}
 #endif
 
 #pragma clang diagnostic pop
 }
+
+namespace HugeArraysUseArrayFiller {
+  // All we're checking here is that initialization completes in a reasonable
+  // amount of time.
+  struct A { int n; int arr[1000 * 1000 * 1000]; } a = {1, {2}};
+}