[clang] Add early exit when checking for const init of arrays.

[adamcz]

Summary

Before this commit, on code like:

struct S { ... };
S arr[10000000];

while checking if arr is constexpr, clang would reserve memory for
arr before running constructor for S. If S turned out to not have a
valid constexpr c-tor, clang would still try to initialize each element
(and, in case the c-tor was trivial, even skipping the constexpr step
limit), only to discard that whole APValue later, since the first
element generated a diagnostic.

With this change, we start by allocating just 1 element in the array to
try out the c-tor and take an early exit if any diagnostics are
generated, avoiding possibly large memory allocation and a lot of work
initializing to-be-discarded APValues.

Fixes 51712 and 51843.

In the future we may want to be smarter about large possibly-constexrp
arrays and maybe make the allocation lazy.

[adamcz]

Hey Kadir. This is my naive approach at solving that large memory usage issue you reported. It works, although I wish this was more generic. I'm not an expert on this piece of code, so I tried to keep things similar to how they worked previously. Let me know what you think.

[kadircet]

thanks this looks amazing! i am also not an expert in these parts of the code but AFAICT the proposed behavior is in line with the contract. i am a little worried about the cost of extra copy (especially when there are only a handful of elements), but it should be probably fine.

clang/lib/AST/ExprConstant.cpp

10617

maybe unroll the loop with a helper like checkConstantInitialization and just call it for a single element first and perform copy & call again for the whole thing ?

that way we can migrate performance issues later on (e.g. put a threshold on FinalSize, don't perform the small step check if it's less than 100, since copying might introduce a significant extra latency in such cases).

WDYT?

10641

i am a little worried about having "non fatal/error" diagnostics here. But looking at the documentation of the field, intention seems to be making this empty iff evaluation succeeded so far. so it's probably fine, but might be worth introducing in a separate patch to make the revert easy, in case it breaks things (+ this seems to be an orthogonal change to the rest)

clang/test/SemaCXX/PR51712-large-array-constexpr-check-oom.cpp

2

maybe test with ulimit and ~1 GB of memory? (you might need Requires: shell and unsupported: windows.)

[adamcz]

review comments

clang/lib/AST/ExprConstant.cpp

10617

I thought of that and decided against it. I think the for loop gives us the same ability to change the steps - we can just replace {1u, FinalSize} with a vector that could have only one element if FinalSize is below some threshold.

Something like:
std::vector<unsigned> steps;
if (FinalSize < 100) steps = {FinalSize};
else steps = {1u, FinalSize};
for (const unsigned N : steps) {
[...]

The problem with helper is that it need sooo many arguments:
N, E, ArrayElt, CAT, Filler, HadZeroInit, Value and "this" (assuming it's free function). Seems like it would hurt readability quite a bit.

If you still think it should be a helper, let me know and I won't argue further - when it comes to readability the reviewer always knows better :-)

10641

Added a short comment.

I don't think splitting this into separate change makes sense. I'd rather just revert this one. Without this check the whole two-step process is mostly useless, so it's not a state we should be in - either revert the whole thing, or keep it.

[kadircet]

thanks, lgtm!

clang/lib/AST/ExprConstant.cpp

10617

sorry I was actually implying a lambda with the "helper" (should've been more explicit && at least use the correct style :D), to prevent the plumbing massacre.

having an earlier logic to decide on the steps if need be also sounds like a good approach though. so feel free to ignore.

[thakis]

The test is failing on non-arm macs: http://45.33.8.238/mac/38601/step_7.txt

Please take a look and revert for now if it takes a while to fix.

[adamcz]

Sorry for trouble, I will revert this for now.

It's only the test that's causing the problem, the fix is fine, as far as I can tell. Still, better revert the whole thing for now.

clang/lib/AST/ExprConstant.cpp

 
 bool ArrayExprEvaluator::VisitCXXConstructExpr(const CXXConstructExpr *E,
                                                const LValue &Subobject,
                                                APValue *Value,
                                                QualType Type) {
   bool HadZeroInit = Value->hasValue();
 
   if (const ConstantArrayType *CAT = Info.Ctx.getAsConstantArrayType(Type)) {
-    unsigned N = CAT->getSize().getZExtValue();
+    unsigned FinalSize = CAT->getSize().getZExtValue();
 
     // Preserve the array filler if we had prior zero-initialization.
     APValue Filler =
       HadZeroInit && Value->hasArrayFiller() ? Value->getArrayFiller()
                                              : APValue();
 
-    *Value = APValue(APValue::UninitArray(), N, N);
+    *Value = APValue(APValue::UninitArray(), 0, FinalSize);
+    if (FinalSize == 0)
+      return true;
+
+    LValue ArrayElt = Subobject;
+    ArrayElt.addArray(Info, E, CAT);
+    // We do the whole initialization in two passes, first for just one element,
+    // then for the whole array. It's possible we may find out we can't do const
+    // init in the first pass, in which case we avoid allocating a potentially
+    // large array. We don't do more passes because expanding array requires
+    // copying the data, which is wasteful.
+    for (const unsigned N : {1u, FinalSize}) {
+      unsigned OldElts = Value->getArrayInitializedElts();
+      if (OldElts == N)
+        break;
+
+      // Expand the array to appropriate size.
+      APValue NewValue(APValue::UninitArray(), N, FinalSize);
+      for (unsigned I = 0; I < OldElts; ++I)
+        NewValue.getArrayInitializedElt(I).swap(
+            Value->getArrayInitializedElt(I));
+      Value->swap(NewValue);
 
       if (HadZeroInit)
-      for (unsigned I = 0; I != N; ++I)
+        for (unsigned I = OldElts; I < N; ++I)
           Value->getArrayInitializedElt(I) = Filler;
 
       // Initialize the elements.
-    LValue ArrayElt = Subobject;
-    ArrayElt.addArray(Info, E, CAT);
-    for (unsigned I = 0; I != N; ++I)
-      if (!VisitCXXConstructExpr(E, ArrayElt, &Value->getArrayInitializedElt(I),
+      for (unsigned I = OldElts; I < N; ++I) {
+        if (!VisitCXXConstructExpr(E, ArrayElt,
+                                   &Value->getArrayInitializedElt(I),
                                    CAT->getElementType()) ||
             !HandleLValueArrayAdjustment(Info, E, ArrayElt,
                                          CAT->getElementType(), 1))
           return false;
+        if (Info.EvalStatus.Diag && !Info.EvalStatus.Diag->empty() &&
+            !Info.keepEvaluatingAfterFailure())
+          return false;
+      }
+    }
 
     return true;
   }
 
   if (!Type->isRecordType())
     return Error(E);
 
   return RecordExprEvaluator(Info, Subobject, *Value)

clang/test/SemaCXX/PR51712-large-array-constexpr-check-oom.cpp

+// RUN: %clang_cc1 -std=c++11 -fsyntax-only -verify %s
+// expected-no-diagnostics
+
+// This used to require too much memory and crash with OOM.
+struct {
+  int a, b, c, d;
+} arr[1<<30];
+