llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT-->
@llvm/pr-subscribers-clang
Author: Kamil Jakubus (jkbz64)
<details>
<summary>Changes</summary>
## Problem
Consider a row in a generated lookup table:
```c
static const unsigned short table[10000] = {
[100] = 1,
[5000] = 2,
};
```
Although only two entries are explicitly initialized, the semantic initializer
list needs slots for the intervening elements. Repeating this pattern across
many rows amplifies two allocation costs:
- Verification can construct a temporary structured initializer list before the
performing pass constructs the final list.
- Incremental growth of a structured initializer list allocates replacement
buffers. The AST arena retains the old buffers, increasing peak memory.
The goal is to avoid this redundant allocation while preserving initialization
checks, diagnostics, and the final semantic representation.
## Motivation
This change is helpful in the [tree-sitter
ecosystem](https://github.com/tree-sitter/tree-sitter), where generated C
parsers contain large sparse lookup tables. Reducing Clang’s temporary
allocations lowers the peak memory needed to build these parsers without
changing their generated source. See [#<!--
-->5974](https://github.com/tree-sitter/tree-sitter/issues/5974).
The same optimization may benefit other projects that generate C code
programmatically, particularly those emitting large sparse arrays with
designated initializers. The applicability depends on the generated initializer
structure; benefits outside the measured workloads have not been established.
## C Changes
For fixed-size C integer arrays, verification skips constructing the temporary
structured list. Omitted integer elements can be zero-initialized, and
overlapping designators do not affect initialization viability. The performing
pass still constructs the semantic list and diagnoses overrides.
For fixed-size scalar arrays whose initializer entries each contain a single
array designator, a preliminary scan determines the required extent and calls
the existing `reserveInits` helper once. The scan uses `llvm::all_of` and falls
back to the existing allocation behavior for unsupported forms, dependent
indices, or invalid bounds.
The example above reserves 5,001 slots, leaving the trailing zeros implicit.
The patch does not allocate storage for the entire declared bound.
## C++ Changes
C++ verification retains the existing behavior. The reservation optimization
can also apply to qualifying scalar arrays where Clang accepts array
designators as a C++ extension.
## Measured impact
These measurements compare agains unpatched Clang
(`b7458ff8580ffc6844b3e4f5035e7f3b2a212816`). Both compile the same `parser.c`
files generated by upstream Tree-sitter 0.27.0.
| Parser | Compile before | Compile after | Time reduction | Peak memory before
| Peak memory after | Memory reduction |
|---|---:|---:|---:|---:|---:|---:|
| [ABL](https://github.com/usagi-coffee/tree-sitter-abl) | 8.24 s | 8.02 s |
2.7% | 2,705.88 MiB | 1,287.22 MiB | 52.4% |
| [Swift](https://github.com/alex-pinkus/tree-sitter-swift) | 1.12 s | 1.10 s |
1.8% | 300.98 MiB | 253.27 MiB | 15.9% |
| [F#](https://github.com/ionide/tree-sitter-fsharp) | 2.49 s | 2.43 s | 2.4% |
829.72 MiB | 573.72 MiB | 30.9% |
| [Scala](https://github.com/tree-sitter/tree-sitter-scala) | 1.29 s | 1.27 s |
1.6% | 383.72 MiB | 320.61 MiB | 16.4% |
| [Kotlin](https://github.com/tree-sitter-grammars/tree-sitter-kotlin) | 1.04 s
| 1.02 s | 1.9% | 308.56 MiB | 265.20 MiB | 14.1% |
| [Julia](https://github.com/tree-sitter/tree-sitter-julia) | 0.94 s | 0.94 s |
0.0% | 294.41 MiB | 252.64 MiB | 14.2% |
| [C#](https://github.com/tree-sitter/tree-sitter-c-sharp) | 1.33 s | 1.30 s |
2.3% | 457.17 MiB | 329.64 MiB | 27.9% |
| [C++](https://github.com/tree-sitter/tree-sitter-cpp) | 1.18 s | 1.17 s |
0.8% | 356.69 MiB | 293.69 MiB | 17.7% |
| [Vim](https://github.com/tree-sitter-grammars/tree-sitter-vim) | 0.72 s |
0.72 s | 0.0% | 207.27 MiB | 207.25 MiB | 0.0% |
```sh
clang --gcc-triple=aarch64-redhat-linux -std=c11 -O0 \
-fPIC -ffunction-sections -fdata-sections \
-I src -c src/parser.c -o parser.o
```
The main result is reduced compiler memory. Avoiding repeated allocations and
copying may also reduce compile time, but the measured timing differences are
too small to establish a consistent speedup.
Assisted-by: OpenAI Codex
---
Full diff: https://github.com/llvm/llvm-project/pull/227592.diff
2 Files Affected:
- (modified) clang/lib/Sema/SemaInit.cpp (+45-1)
- (modified) clang/test/Sema/designated-initializers.c (+11)
``````````diff
diff --git a/clang/lib/Sema/SemaInit.cpp b/clang/lib/Sema/SemaInit.cpp
index 3f30e94aa8976..b9828b61c28b2 100644
--- a/clang/lib/Sema/SemaInit.cpp
+++ b/clang/lib/Sema/SemaInit.cpp
@@ -33,11 +33,13 @@
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
+#include <limits>
using namespace clang;
@@ -1087,7 +1089,16 @@ InitListChecker::InitListChecker(
TreatUnavailableAsInvalid(TreatUnavailableAsInvalid),
InOverloadResolution(InOverloadResolution),
AggrDeductionCandidateParamTypes(AggrDeductionCandidateParamTypes) {
- if (!VerifyOnly || hasAnyDesignatedInits(IL)) {
+ // In C, omitted integer array elements can always be zero-initialized and
+ // overlapping designators do not affect initialization viability. There is
+ // no need to build a dense semantic list merely to verify such an array.
+ // The performing pass still builds the list and diagnoses overrides. Keep
+ // the existing C++ path, where overrides can affect overload resolution.
+ bool NeedsStructuredList = true;
+ if (VerifyOnly && !SemaRef.getLangOpts().CPlusPlus)
+ if (const auto *CAT = SemaRef.Context.getAsConstantArrayType(T))
+ NeedsStructuredList = !CAT->getElementType()->isIntegerType();
+ if (!VerifyOnly || (NeedsStructuredList && hasAnyDesignatedInits(IL))) {
FullyStructuredList = createInitListExpr(
T, IL->getSourceRange(), IL->getNumInits(), IL->isExplicit());
@@ -2156,6 +2167,39 @@ void InitListChecker::CheckArrayType(const
InitializedEntity &Entity,
IList->setInit(0, Embed->getDataStringLiteral());
}
+ // A sparse list of array designators can touch most of an array even when
+ // it contains few explicit initializers. Growing its semantic initializer
+ // incrementally retains every old buffer in the AST arena. Reserve the
+ // required extent once, without allocating space for trailing zeroes.
+ if (StructuredList && Index == 0 && StructuredIndex == 0 &&
+ IList->getNumInits() > 1 && arrayType->getElementType()->isScalarType())
{
+ if (const auto *CAT = dyn_cast<ConstantArrayType>(arrayType)) {
+ uint64_t Extent = 0;
+ const uint64_t Bound = CAT->getZExtSize();
+ if (llvm::all_of(IList->inits(), [&](const Expr *Init) {
+ const auto *DIE = dyn_cast<DesignatedInitExpr>(Init);
+ if (!DIE || DIE->size() != 1 ||
+ !DIE->getDesignator(0)->isArrayDesignator())
+ return false;
+ const Expr *IndexExpr = DIE->getArrayIndex(*DIE->getDesignator(0));
+ if (IndexExpr->isValueDependent())
+ return false;
+ // Sema has already checked that this is a nonnegative integer
+ // constant expression. Leave invalid bounds to the usual path.
+ uint64_t ArrayIndex =
+ IndexExpr->EvaluateKnownConstInt(SemaRef.Context)
+ .getLimitedValue();
+ if (ArrayIndex >= Bound ||
+ ArrayIndex >= std::numeric_limits<unsigned>::max())
+ return false;
+ Extent = std::max(Extent, ArrayIndex + 1);
+ return true;
+ }))
+ StructuredList->reserveInits(SemaRef.Context,
+ static_cast<unsigned>(Extent));
+ }
+ }
+
// Check for the special-case of initializing an array with a string.
if (Index < IList->getNumInits()) {
if (IsStringInit(IList->getInit(Index), arrayType, SemaRef.Context) ==
diff --git a/clang/test/Sema/designated-initializers.c
b/clang/test/Sema/designated-initializers.c
index 11dc3a2308dee..999757bb3a909 100644
--- a/clang/test/Sema/designated-initializers.c
+++ b/clang/test/Sema/designated-initializers.c
@@ -375,3 +375,14 @@ void gh154046(void) {
[1] = "" // expected-error {{incompatible pointer to integer conversion
initializing 'const char' with an expression of type 'char[1]'}}
}[1];
}
+
+// Nested fixed-size integer arrays exercise verification without a temporary
+// structured list and reservation for out-of-order array designators.
+unsigned short sparse_rows[2][8] = {
+ [1] = {[7] = 0xffff, [1] = 42},
+ [0] = {[6] = 7, [2] = 3},
+};
+unsigned short sparse_duplicate[1][8] = {
+ {[3] = 1, // expected-note {{previous initialization is here}}
+ [3] = 2} // expected-warning {{initializer overrides prior initialization
of this subobject}}
+};
``````````
</details>
https://github.com/llvm/llvm-project/pull/227592
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
