[CodeGen] Recognize more cases of zero initialization

[sepavloff]

Summary

If a variable has initializer, codegen tries to build its value. It
causes strange behavior from user viewpoint: compilation of huge zero
initialized arrays like:

int char data_1[2147483648u] = { 0 };

consumes enormous amount of time and memory.

With this change compiler recognizes more patterns when variable is
initialized with zeros and elementwise treatment can be avoided.

[rjmccall]

lib/CodeGen/CGExprConstant.cpp

1395

You should have a comment here clarifying that this is checking whether the initializer is equivalent to a C++ zero initialization, not checking whether the initializer produces a zero bit-pattern.

1414

You should check the array fill expression here; for now, the test case would be something like StructWithNonTrivialDefaultInit sArr[10] = {};.

1415

I would suggest doing your primary switch over the form of Init instead of its type, and you can just have an isIntegerConstantExpr check at the end.

You should also check for a null pointer expression.

[sepavloff]

Addressed review notes.

[sepavloff]

lib/CodeGen/CGExprConstant.cpp

1414

Indeed, this is the missing case. Thank you!

[rjmccall]

lib/CodeGen/CGExprConstant.cpp

1403

Do you actually care if it's an array initialization instead of a struct/enum initialization?

1413

Aren't the null-pointer and integer-constant-expression checks below already checking this? Also, isEvaluatable actually computes the full value internally (as an APValue), so if you're worried about the memory and compile-time effects of producing such a value, you really shouldn't call it.

You could reasonably move this entire function to be a method on Expr that takes an ASTContext.

1417

There's a isNullPointerConstant method (you should use NPC_NeverValueDependent).

[sepavloff]

Small simplification

[sepavloff]

lib/CodeGen/CGExprConstant.cpp

1403

If this code is enabled for for records too, some tests start to fail. For instance, the code:

union { int i; double f; } u2 = { };

produces output:

%union.anon = type { double }
@u2 = global %union.anon zeroinitializer, align 4

while previously it produced:

@u2 = global { i32, [4 x i8] } { i32 0, [4 x i8] undef }, align 4

The latter looks more correct.

1413

Comment for EvaluateAsRValue says that it tries calculate expression agressively. Indeed, for the code:

decltype(nullptr) null();
int *p = null();

compiler ignores potential side effect of null() and removes the call, leaving only zero initialization. isNullPointerConstant behaves similarly.

1417

It make code more readable. Thank you!

[rsmith]

lib/CodeGen/CGExprConstant.cpp

1413

Nonetheless, it looks like this function could evaluate Init up to three times, which seems unreasonable. Instead of the checks based on trying to evaluate the initializer (isNullPointerConstant + isIntegerConstantExpr), how about calling VarDecl::evaluateValue() (which will return a potentially pre-computed and cached initializer value) and checking if the result is a zero constant?

In fact, tryEmitPrivateForVarInit already does most of that for you, and the right place to make this change is probably in tryEmitPrivateForMemory, where you can test to see if the APValue is zero-initialized and produce a zeroinitializer if so. As a side-benefit, putting the change there will mean we'll also start using zeroinitializer for zero-initialized subobjects of objects that have non-zero pieces.

[sepavloff]

Avoid redundant initializer calculation

[sepavloff]

lib/CodeGen/CGExprConstant.cpp

1413

An important point in this patch is that CodeGen tries to find out, if the initializer can be replaced with zeroinitializer, *prior* to the evaluation of it. For huge arrays the evaluation consumes huge amount of memory and time and it must be avoided.

With this patch CodeGen may evaluate parts of the initializer, if it is represented by InitListExpr. It may cause redundant calculation, for instance if the check for zero initialization failed but the initializer is constant. To avoid this redundancy we could cache result of evaluation in instances of Expr and then use the partial values in the evaluation of the initializer. The simple use case solved by this patch probably is not a sufficient justification for such redesign.

[rjmccall]

lib/CodeGen/CGExprConstant.cpp

1403

Hmm. In C++, a static object which isn't constant-initialized is zero-initialized, which is required to set any padding bits to zero (N4640 [dcl.init]p6) in both structs and unions. In C, a static object which doesn't have an initializer also has all any padding bits set to zero (N1548 6.7.9p10). Now, this object has an initializer (that acts as a constant-initializer in C++), so those rules don't directly apply; but I would argue that the intent of the standards is not that padding bits become undefined when you happen to have an initializer. So I actually think the zeroinitializer emission is more correct.

[sepavloff]

Added treatment of structures/unions

[sepavloff]

Hmm. In C++, a static object which isn't constant-initialized is zero-initialized, which is required to set any padding bits to zero (N4640 [dcl.init]p6) in both structs and unions. In C, a static object which doesn't have an initializer also has all any padding bits set to zero (N1548 6.7.9p10). Now, this object has an initializer (that acts as a constant-initializer in C++), so those rules don't directly apply; but I would argue that the intent of the standards is not that padding bits become undefined when you happen to have an initializer. So I actually think the zeroinitializer emission is more correct.

Using undefined values instead of zero initialization was implemented in https://reviews.llvm.org/rL101535. There is no much info about the reason of the implementation. Clang uses undefined values for padding bits, in particular in unions, when the first member is not widest. The code:

    union C1 {
	  char sel;
	  double dval;
	};
	union C1 val_1 = { 0 };

produces:

@val_1 = dso_local global { i8, [7 x i8] } { i8 0, [7 x i8] undef }, align 8

Another case is unnamed bit fields.

	struct C2 {
	  int : 4;
	  int x;
	};
	struct C2 val_2 = { 0 };

produces:

@val_2 = dso_local global { [4 x i8], i32 } { [4 x i8] undef, i32 0 }, align 4

Strictly speaking, this IR does not mean violation of the standard, but it can modify code generation in some cases. If we decided to use zeroinitializer in this case, we probably would need to revise using undefined values in initializers, otherwise similar declarations like:

	union C1 val_1a = { 0 };
	union C1 val_1b = { 1 };

would produce different IR representations, with and without undefined values.

The test SemaCXX/large-array-init.cpp is removed in this change. This test was added in https://reviews.llvm.org/rL325120 to solve https://bugs.llvm.org/show_bug.cgi?id=18978, which describes the same problem, as solved by this patch. This patch presents more efficient solution, with it the tests compiles 50 time faster. If r325120 does not solve additional problems, it can be reverted.

[rjmccall]

lib/CodeGen/CGExprConstant.cpp

1413

I really think you should have some sort of type restriction in front of this so that you don't end up creating a huge APValue only to throw it away because it's not an int or a pointer. It's quite possible to have something like an array initializer in a nested position that's not within an InitListExpr , e.g. due to compound literals or std::initializer_list.

[sepavloff]

Updated patch

Try evaluating initializer value only if the initializer type is
integral or pointer. It avoids calculation of large value, which
then is discarded.

[rjmccall]

Thanks, LGTM.

[rsmith]

lib/CodeGen/CGExprConstant.cpp

1414–1415

Please call D.evaluateValue() here rather than inventing your own evaluation scheme. That way, we'll cache the evaluated initializer on the variable for other uses or reuse the value if we've already evaluated it, and you don't need to worry about the corner cases involved in getting the evaluation right. (As it happens, you're getting some minor details wrong because evaluating an initializer is not quite the same as evaluating an rvalue, but in practice it's not a big deal here.)

[sepavloff]

lib/CodeGen/CGExprConstant.cpp

1414–1415

Call of D.evaluateValue() may result in substantial memory and time consumption if the variable value is huge, like in:

int char data_1[2147483648u] = { 0 };

The idea of this patch is to recognize some cases of zero initialization prior to the evaluation of variable initializer. In the example above, value would be evaluated only for part of the initializer, namely 0, which does not have an associated variable, so call of D.evaluateValue() is not possible.

[sepavloff]

@rsmith Do yo think this patch is OK to apply?

[rsmith]

lib/CodeGen/CGExprConstant.cpp

1414–1415

As noted, EvaluateAsRValue gets some of the details here wrong. I reverted this in r332886 because of a miscompile due to this fact.

[rsmith]

I've done some more investigation, and I now think this patch is merely working around deficiencies elsewhere. See https://reviews.llvm.org/D47166, which aims to fix those deficiencies more directly.

include/clang/AST/Expr.h

public:
 
   /// isConstantInitializer - Returns true if this expression can be emitted to
   /// IR as a constant, and thus can be used as a constant initializer in C.
   /// If this expression is not constant and Culprit is non-null,
   /// it is used to store the address of first non constant expr.
   bool isConstantInitializer(ASTContext &Ctx, bool ForRef,
                              const Expr **Culprit = nullptr) const;
 
+  enum SideEffectsKind {
+    SE_NoSideEffects,          ///< Strictly evaluate the expression.
+    SE_AllowUndefinedBehavior, ///< Allow UB that we can give a value, but not
+                               ///< arbitrary unmodeled side effects.
+    SE_AllowSideEffects        ///< Allow any unmodeled side effect.
+  };
+
   /// EvalStatus is a struct with detailed info about an evaluation in progress.
   struct EvalStatus {
     /// \brief Whether the evaluated expression has side effects.
     /// For example, (f() && 0) can be folded, but it still has side effects.
     bool HasSideEffects;
 
     /// \brief Whether the evaluation hit undefined behavior.
     /// For example, 1.0 / 0.0 can be folded to Inf, but has undefined behavior.
struct EvalStatus {
     EvalStatus()
         : HasSideEffects(false), HasUndefinedBehavior(false), Diag(nullptr) {}
 
     // hasSideEffects - Return true if the evaluated expression has
     // side effects.
     bool hasSideEffects() const {
       return HasSideEffects;
     }
+
+    bool hasUnacceptableSideEffect(SideEffectsKind SEK) {
+      return (SEK < SE_AllowSideEffects && HasSideEffects) ||
+             (SEK < SE_AllowUndefinedBehavior && HasUndefinedBehavior);
+    }
   };
 
   /// EvalResult is a struct with detailed info about an evaluated expression.
   struct EvalResult : EvalStatus {
     /// Val - This is the value the expression can be folded to.
     APValue Val;
 
     // isGlobalLValue - Return true if the evaluated lvalue expression
public:
   bool EvaluateAsRValue(EvalResult &Result, const ASTContext &Ctx) const;
 
   /// EvaluateAsBooleanCondition - Return true if this is a constant
   /// which we can fold and convert to a boolean condition using
   /// any crazy technique that we want to, even if the expression has
   /// side-effects.
   bool EvaluateAsBooleanCondition(bool &Result, const ASTContext &Ctx) const;
 
-  enum SideEffectsKind {
-    SE_NoSideEffects,          ///< Strictly evaluate the expression.
-    SE_AllowUndefinedBehavior, ///< Allow UB that we can give a value, but not
-                               ///< arbitrary unmodeled side effects.
-    SE_AllowSideEffects        ///< Allow any unmodeled side effect.
-  };
-
   /// EvaluateAsInt - Return true if this is a constant which we can fold and
   /// convert to an integer, using any crazy technique that we want to.
   bool EvaluateAsInt(llvm::APSInt &Result, const ASTContext &Ctx,
                      SideEffectsKind AllowSideEffects = SE_NoSideEffects) const;
 
   /// EvaluateAsFloat - Return true if this is a constant which we can fold and
   /// convert to a floating point value, using any crazy technique that we
   /// want to.

lib/AST/ExprConstant.cpp

 
 bool Expr::EvaluateAsBooleanCondition(bool &Result,
                                       const ASTContext &Ctx) const {
   EvalResult Scratch;
   return EvaluateAsRValue(Scratch, Ctx) &&
          HandleConversionToBool(Scratch.Val, Result);
 }
 
-static bool hasUnacceptableSideEffect(Expr::EvalStatus &Result,
-                                      Expr::SideEffectsKind SEK) {
-  return (SEK < Expr::SE_AllowSideEffects && Result.HasSideEffects) ||
-         (SEK < Expr::SE_AllowUndefinedBehavior && Result.HasUndefinedBehavior);
-}
-
 bool Expr::EvaluateAsInt(APSInt &Result, const ASTContext &Ctx,
                          SideEffectsKind AllowSideEffects) const {
   if (!getType()->isIntegralOrEnumerationType())
     return false;
 
   EvalResult ExprResult;
   if (!EvaluateAsRValue(ExprResult, Ctx) || !ExprResult.Val.isInt() ||
-      hasUnacceptableSideEffect(ExprResult, AllowSideEffects))
+      ExprResult.hasUnacceptableSideEffect(AllowSideEffects))
     return false;
 
   Result = ExprResult.Val.getInt();
   return true;
 }
 
 bool Expr::EvaluateAsFloat(APFloat &Result, const ASTContext &Ctx,
                            SideEffectsKind AllowSideEffects) const {
   if (!getType()->isRealFloatingType())
     return false;
 
   EvalResult ExprResult;
   if (!EvaluateAsRValue(ExprResult, Ctx) || !ExprResult.Val.isFloat() ||
-      hasUnacceptableSideEffect(ExprResult, AllowSideEffects))
+      ExprResult.hasUnacceptableSideEffect(AllowSideEffects))
     return false;
 
   Result = ExprResult.Val.getFloat();
   return true;
 }
 
 bool Expr::EvaluateAsLValue(EvalResult &Result, const ASTContext &Ctx) const {
   EvalInfo Info(Ctx, Result, EvalInfo::EM_ConstantFold);
return CheckConstantExpression(InitInfo, VD->getLocation(), VD->getType(),
                                  Value);
 }
 
 /// isEvaluatable - Call EvaluateAsRValue to see if this expression can be
 /// constant folded, but discard the result.
 bool Expr::isEvaluatable(const ASTContext &Ctx, SideEffectsKind SEK) const {
   EvalResult Result;
   return EvaluateAsRValue(Result, Ctx) &&
-         !hasUnacceptableSideEffect(Result, SEK);
+         !Result.hasUnacceptableSideEffect(SEK);
 }
 
 APSInt Expr::EvaluateKnownConstInt(const ASTContext &Ctx,
                     SmallVectorImpl<PartialDiagnosticAt> *Diag) const {
   EvalResult EvalResult;
   EvalResult.Diag = Diag;
   bool Result = EvaluateAsRValue(EvalResult, Ctx);
   (void)Result;

lib/CodeGen/CGExprConstant.cpp

 static QualType getNonMemoryType(CodeGenModule &CGM, QualType type) {
   if (auto AT = type->getAs<AtomicType>()) {
     return CGM.getContext().getQualifiedType(AT->getValueType(),
                                              type.getQualifiers());
   }
   return type;
 }
 
+/// Checks if the specified initializer is equivalent to zero initialization.
+static bool isZeroInitializer(ConstantEmitter &CE, const Expr *Init) {
+  QualType InitTy = Init->getType().getCanonicalType();
+  if (auto *E = dyn_cast_or_null<CXXConstructExpr>(Init)) {
+    CXXConstructorDecl *CD = E->getConstructor();
+    return CD->isDefaultConstructor() && CD->isTrivial();
+  }
+  if (auto *IL = dyn_cast_or_null<InitListExpr>(Init)) {
+    if (InitTy->isConstantArrayType()) {
+      for (auto I : IL->inits())
+        if (!isZeroInitializer(CE, I))
+          return false;
+      if (const Expr *Filler = IL->getArrayFiller()) {
+        return isZeroInitializer(CE, Filler);
+      }
+      return true;
+    }
+  } else {
+    Expr::EvalResult Result;
+    if (Init->EvaluateAsRValue(Result, CE.CGM.getContext()) &&
+        !Result.hasUnacceptableSideEffect(Expr::SE_NoSideEffects))
+      return (Result.Val.isInt() && Result.Val.getInt().isNullValue()) ||
+             (Result.Val.isLValue() && Result.Val.isNullPointer());
+  }
+
+  return false;
+}
+
 llvm::Constant *ConstantEmitter::tryEmitPrivateForVarInit(const VarDecl &D) {
   // Make a quick check if variable can be default NULL initialized
   // and avoid going through rest of code which may do, for c++11,
   // initialization of memory to all NULLs.
-  if (!D.hasLocalStorage()) {
-    QualType Ty = CGM.getContext().getBaseElementType(D.getType());
-    if (Ty->isRecordType())
-      if (const CXXConstructExpr *E =
-          dyn_cast_or_null<CXXConstructExpr>(D.getInit())) {
-        const CXXConstructorDecl *CD = E->getConstructor();
-        if (CD->isTrivial() && CD->isDefaultConstructor())
-          return CGM.EmitNullConstant(D.getType());
-      }
-  }
+  if (!D.hasLocalStorage() && isZeroInitializer(*this, D.getInit()))
 
   QualType destType = D.getType();
 
   // Try to emit the initializer.  Note that this can allow some things that
   // are not allowed by tryEmitPrivateForMemory alone.
   if (auto value = D.evaluateValue()) {
     return tryEmitPrivateForMemory(*value, destType);
   }

test/CodeGenCXX/cxx11-initializer-aggregate.cpp

 // 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();
+  };
+
+  // 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() };
+
+
+  // This variable must be initialized elementwise.
+  Filler data_e1[1024] = {};
+  // CHECK: getelementptr inbounds {{.*}} @_ZN8ZeroInit7data_e1E
+}