[clang] Short-circuit trivial constexpr array constructors

[tbaeder]

Summary

As discussed in https://github.com/llvm/llvm-project/issues/56774

[aaron.ballman]

Thank you for working on this! This should also include test coverage (hmmm, we don't have a reasonable way to lit test performance regressions though.... so perhaps we just need to ensure there's at least one test that would normally have been unreasonably slow?) and a release note.

clang/lib/AST/ExprConstant.cpp

10836–10838

The big question this raises for me is: will this cause constexpr to fail because of the note diagnostics when the type does not have a trivial default constructor? Or does this just bump the failure up a bit so that we fail before we start walking over the array elements?

[dblaikie]

Thank you for working on this! This should also include test coverage (hmmm, we don't have a reasonable way to lit test performance regressions though.... so perhaps we just need to ensure there's at least one test that would normally have been unreasonably slow?) and a release note.

I think generally for pure-perf fixes we don't include any testing. (like switching a container type, adding caching, etc) But may be worth double-checking that there's reasonable test coverage for the feature.

also: What about zero length arrays? (which are supported as an extension) - this change would cause failures that wouldn't be emitted in the old code?

[tbaeder]

In D130791#3692071, @dblaikie wrote:

also: What about zero length arrays? (which are supported as an extension) - this change would cause failures that wouldn't be emitted in the old code?

There's a if (FinalSize == 0) return true; case above, so this code will never be reached for zero-length arrays. That loop here is pretty confusing... OldElts is either zero (for the first iteration), or one (for the second iteration, where N == FinalSize). I tried to untangle this, but it doesn't work very well since the APValue we pass to VisitCXXConstructExpr() must be in an array APValue...

As for testing: I didn't include a test because of what you two mentioned, I can't really test that a test case finished in under X seconds...

clang/lib/AST/ExprConstant.cpp

10836–10838

I can't come up with an example that would make this fail, or fail differently than it did before. For a constructor that is not marked constexpr and where CheckTrivialDefaultConstructor returns false, the first VisitCXXConstructExpr will return false and no diagnostic will be emitted. In the cases I tried, Info.EvalStatus.Diag is nullptr anyway, so yeah. If it did emit a diagnostic, I would assume that the failure just happens a little early, yes.

The alternative would be to try to integrate the CheckTrivialDefaultConstructor call into the loop, but I'm not a fan of that loop anyway :)

[aaron.ballman]

LGTM! I agree that test coverage for the performance issue is basically impossible with our testing system. I was thinking "well good, add a test with a huge initializer to make sure it doesn't crash" but then I realized that will slow down running the tests significantly and will always be susceptible to a slightly larger array than the test uses being a problem. So I think it's fine to land this without tests.

clang/docs/ReleaseNotes.rst

 
 Bug Fixes
 ---------
 - Fixes an accepts-invalid bug in C when using a ``_Noreturn`` function
   specifier on something other than a function declaration. This fixes
   `Issue 56800 <https://github.com/llvm/llvm-project/issues/56800>`_.
 - Fix `#56772 <https://github.com/llvm/llvm-project/issues/56772>`_ - invalid
   destructor names were incorrectly accepted on template classes.
+- Improve compile-times with large dynamic array allocations with trivial
+  constructors. This fixes
+  `Issue 56774<https://github.com/llvm/llvm-project/issues/56774>`_.
 
 Improvements to Clang's diagnostics
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 - Clang will now correctly diagnose as ill-formed a constant expression where an
   enum without a fixed underlying type is set to a value outside the range of
   the enumeration's values. Fixes
   `Issue 50055: <https://github.com/llvm/llvm-project/issues/50055>`_.
 

clang/lib/AST/ExprConstant.cpp

if (const ConstantArrayType *CAT = Info.Ctx.getAsConstantArrayType(Type)) {
     APValue Filler =
       HadZeroInit && Value->hasArrayFiller() ? Value->getArrayFiller()
                                              : APValue();
 
     *Value = APValue(APValue::UninitArray(), 0, FinalSize);
     if (FinalSize == 0)
       return true;
 
+    bool HasTrivialConstructor = CheckTrivialDefaultConstructor(
+        Info, E->getExprLoc(), E->getConstructor(),
+        E->requiresZeroInitialization());
     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 = OldElts; I < N; ++I)
           Value->getArrayInitializedElt(I) = Filler;
 
-      // Initialize the elements.
+      if (HasTrivialConstructor && N == FinalSize) {
+        // If we have a trivial constructor, only evaluate it once and copy
+        // the result into all the array elements.
+        APValue &FirstResult = Value->getArrayInitializedElt(0);
+        for (unsigned I = OldElts; I < FinalSize; ++I)
+          Value->getArrayInitializedElt(I) = FirstResult;
+      } else {
         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;
           // When checking for const initilization any diagnostic is considered
           // an error.
           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)