<table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Issue</th>
<td>
<a href=https://github.com/llvm/llvm-project/issues/54510>54510</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>
Regression in LLVM 13: Long code generation time with large-ish static arrays of std::string
</td>
</tr>
<tr>
<th>Labels</th>
<td>
new issue
</td>
</tr>
<tr>
<th>Assignees</th>
<td>
</td>
</tr>
<tr>
<th>Reporter</th>
<td>
tinloaf
</td>
</tr>
</table>
<pre>
I'm using clang 13.0.1:
```
❯ /usr/bin/clang++-13 --version
Ubuntu clang version 13.0.1-++20220120110924+75e33f71c2da-1~exp1~20220120231001.58
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin
```
I have a file (see attachment [bug.cpp.txt](https://github.com/llvm/llvm-project/files/8332455/bug.cpp.txt) - ignore the `.txt` extension, GitHub apparently does not allow to attach `.cpp` files) that contains a global `static` c-style array of 300 `std::string` objects. There is not much else going on, `main` just contains a loop over those 300 elements.
When I compile this with `/usr/bin/clang++-13 -O1 ./bug.cpp`, clang takes more than six minutes:
```
❯ time /usr/bin/clang++-13 -O1 ./bug.cpp
/usr/bin/clang++-13 -O1 ./bug.cpp 364.56s user 0.31s system 99% cpu 6:05.25 total
```
I also tried increasing the number of elements in the array to 500. I killed clang after ~35 minutes of compiling that file. This looks like some kind of exponential growth in compile time.
When I use `-O2`, `-O3` or `-O0`, the problem goes away:
```
❯ time /usr/bin/clang++-13 -O0 ./bug.cpp
/usr/bin/clang++-13 -O0 ./bug.cpp 0.27s user 0.16s system 78% cpu 0.540 total
❯ time /usr/bin/clang++-13 -O2 ./bug.cpp
/usr/bin/clang++-13 -O2 ./bug.cpp 1.81s user 0.19s system 98% cpu 2.031 total
❯ time /usr/bin/clang++-13 -O3 ./bug.cpp
/usr/bin/clang++-13 -O3 ./bug.cpp 1.78s user 0.19s system 98% cpu 1.990 total
```
Following the bug reporting guide, I have tried to break this down into the three steps bitcode generation / optimization / code generation, but each of those steps run individually seems to be fast:
```
❯ time /usr/bin/clang++-13 -emit-llvm -O1 -Xclang -disable-llvm-passes -c -o bug.bc bug.cpp
/usr/bin/clang++-13 -emit-llvm -O1 -Xclang -disable-llvm-passes -c -o bug.bc 0.19s user 0.11s system 100% cpu 0.297 total
❯ time /usr/bin/opt-13 -O1 bug.bc -disable-output
/usr/bin/opt-13 -O1 bug.bc -disable-output 0.34s user 0.03s system 99% cpu 0.375 total
❯ time /usr/bin/llc-13 -O1 -relocation-model=static bug.bc
/usr/bin/llc-13 -O1 -relocation-model=static bug.bc 0.19s user 0.03s system 97% cpu 0.225 total
❯ time /usr/bin/llc-13 -O1 -relocation-model=pic bug.bc
/usr/bin/llc-13 -O1 -relocation-model=pic bug.bc 0.19s user 0.02s system 90% cpu 0.226 total
❯ time /usr/bin/llc-13 -O1 bug.bc
/usr/bin/llc-13 -O1 bug.bc 0.16s user 0.05s system 92% cpu 0.219 total
```
I have created a [time report](https://github.com/llvm/llvm-project/files/8332447/clang13-time-report.txt) using `-ftime-report` (see link for full file), and this is what seems to be the core of the problem:
```
[…]
===-------------------------------------------------------------------------===
Instruction Selection and Scheduling
===-------------------------------------------------------------------------===
Total Execution Time: 364.1250 seconds (364.4754 wall clock)
---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---
363.9844 (100.0%) 0.1250 (100.0%) 364.1094 (100.0%) 364.4519 (100.0%) DAG Combining 1
[…]
===-------------------------------------------------------------------------===
... Pass execution timing report ...
===-------------------------------------------------------------------------===
Total Execution Time: 364.2969 seconds (364.6338 wall clock)
---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---
364.0156 (100.0%) 0.1250 ( 80.0%) 364.1406 (100.0%) 364.4800 (100.0%) X86 DAG->DAG Instruction Selection
[…]
```
The same bug seems not to be present in LLVM 10, 11 or 12:
```
❯ /usr/bin/clang++-12 --version
Ubuntu clang version 12.0.1-++20211029101322+fed41342a82f-1~exp1~20211029221816.4
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin
❯ /usr/bin/clang++-11 --version
Ubuntu clang version 11.0.0-2~ubuntu20.04.1
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin
❯ /usr/bin/clang++-10 --version
clang version 10.0.0-4ubuntu1
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin
❯ time /usr/bin/clang++-12 -O1 ./bug.cpp
/usr/bin/clang++-12 -O1 ./bug.cpp 0.48s user 0.14s system 98% cpu 0.637 total
❯ time /usr/bin/clang++-11 -O1 ./bug.cpp
/usr/bin/clang++-11 -O1 ./bug.cpp 0.42s user 0.22s system 99% cpu 0.646 total
❯ time /usr/bin/clang++-10 -O1 ./bug.cpp
/usr/bin/clang++-10 -O1 ./bug.cpp 0.45s user 0.16s system 95% cpu 0.640 total
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzNWNty2zYQ_Rr5BUMOLrw-6MGOkzQzadNpnCZvHZCEJMQUwSHA2O7XdxegLpYV20oyaTQaSsRlcXb37GKByjR38zcznq_JaHW3JHUr4clETGM2E-czejmj57OMTt_w-pLPysvZ-Ssy469GO8Cz0h08_eQZv4BvxASJoi9qsNp0YdqHauzcOK0w9UwrRWESp5xTBl9GS55AQ54qIRY5q3kjIzbLX6rbHn82A7lglLI4LcIKV3JYKgewyW2R_ZMlUV9Hre7G22jZjdOQ1aBkQ9amUS0O7I3Vt6HrTWedbFvVXOoBu-4pd9QOYRpZyS-KSLLQrYJJhVXw5pysV2vVOTJLL6pxGdd9H7tbN0svYcjKud6iefkr-C61W41VXJs1vLTtl81P1A_ms6odvKJsC7-FEDxJUwS1J5OXJCJ62ZlBEbcCEBn17Rkl6tapzvuAvyCvtfttrIjsezkAtPaONEZZ0hlHQHFzQ5yZkHsRIB5FTGuXIFo6UpvOSd1ZUHjZmkq2OBQM53SNg-vIujuwgxwGeUfMgghKw4gG9RXn1g3AMxxqKlTOxuRqpQC4DkDWI6yuWqvI0iAhA3IYv4ZVcdrn0d5D0RrTEwN8AnwGpuGCqlVoexvvO-rjSnXkDUxd9-gpt4IVb8D0KPwJIr9jJN7Z3I9_MRHZyWsw4TqYXnYE6ETWwDmn7NPx4_RaPRVEsPb-4mSScQpgQkSWxGlmIcjBTjQWzBJ7Z51ak7Kc8ZTU_UgywEvTGN6cgUA4Cv0NEMUaAj5UDdFdDcHk0wayrhvXFUgHn2_MDyN8TyADkCulNAYXXGsMs8mAcuFgFgS1SDeGQxnBTUE20A5JiEwBn4HDr-GprxWxBux3rbvGr3rbmw6W1cDJ5WBuwLOw_tbdYOpjdACLIAGid3xyq38RnqBDeKFTD6oCIVmBdkBOgClv5N0PcjK9R7BnuZjedzGNeb51MMu2Ds6LjYNpnCb0nnNPw8hPx8jvY2RxwXYYyx0Jtxh5TAX7DozidIziEGNePI6RxWVJHwmS8HxlMKVuggPEk0H1ZnDYshx1o5BS0-YR4gkCpIKAug6pqTE3HRAYGnG-g30L-O5Ub0mlXQ37F1mqTg2QeGEbBQWI6cFC-t9dw8EgXK8aHVGY3yFeQroMIocR12r0F92MsBXcEdjE1tYjUmQhrfsxNFdr7SLc2nyGij6FDBA12kqIqihsetJaiK2oJpFBs8VVTU7x57euQSZ3bzy_S5FQY-xCiJf5Pdc_wwrgmE1SntbaojGj60d3VK8nZyFgkWwBU3Ekp8OIPD0Vb9vWm5WjQbWm9vSJpprpMmz2E6ij0E8RcGD2fS3yPasf7Erfg7__LvD9V5HzHfJ9vvDsm5A_D-Eekt3uTtMdEr6HhJVPJq0pH-G-7iAjSaxePdCQu35E9Zrkm6BlIkLZUZC9qWTDOQQ33sVeL-7HU20NRcE1WcDmvBjb1hcGMA2Tm4Q6wKdOLOywaNhPYphEa6zSfObbbuRfzWvpBbqqoLPzDLUOjeIyfKMf9dlKDAuQox88mAxj7fP6e6itwj_U9n29Us2IVdJPA3iFDCIvb1U9ehhX4CM8LWGFyXhKwehQnDcWvYVtSZ4m5Ab2FCj3TH2NrtrjG2gHi3xA3qIg-O9b3gf2hibfgkMgw4eOqS36iGK38_DxhwSuIuxJushEXBZJgmggjccYmEgyHzGI9rDdq0HLhxO8LimE0GHH5flr8sKsITSRt-zXo08cx-RP2PCgQN44DQuFblOQ4IBfgj68zMpD-mRCFP8nfZKYsjR7jD6kOKRPQh9O8PQp6EPCfSoypBBY6iUy6WisP8apY1l8c9UB1R0qhLVnSIV4wA7psB-UxdsJOCG9ffv371DjYAZlDA89jH_fzQ9_3s0Pv3_zwxjlJaNMcNizLhaqSZhIuCz44uDmxw_knBUsi5OfdPHzLL3Z8_RmoDeNOCgz-n4Or8CaX0kTeqjJgQrUq5AE_D8L-annDf7g3ubJ48ODKRjoyd5xMDlyHKSQpPJvPLKy0zE-mOIx8i1Gzo-eA7LkhDr0kAynYnwwxWNMj11PlOk-xseO1WfNXDSlKOWZ065V87_UEpKYJ-Q2iwnkzluDF9kHJ2Svpr_ua5GokbYrMh1E_PWUv3Q6uKU8G4d2fnK1q60dfbmbQr1Az1ZzWeR1nlcLziRjZa5Es5AL2pRFXWf1okrOWlmp1s4xwXPeqRviRcB_SPNneu5vuwUXDDMfbEhclHmSiARyo6zKapZQtZa6jRFHbIbl2TD3kMD2FjpbbZ3ddUIloJedUn45kC9HtzLD3OmuNXJx5peee-j_Ab8L218">