Excessive compile time spent in DAGCombiner::mergeConsecutiveStores (Clang stalls when compiling with O1 optimisation level)

[ArashPartow]

This issue is related to the following version circa 20220214 ( 4ee240b ):

clang version 15.0.0 (https://github.com/llvm/llvm-project.git 4ee240b86085ef90d20ce731a434287805d119ea)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /usr/local/bin

When compiling the following code with O1, clang does not return and continuously consumes up an entire core:

https://partow.net/clang/clang_O1_bug_20220214.zip

I have let clang run for about nine hours before having to break. The expected compile/link time for the example code is about roughly one minute.

user@machine ~/workspace/clang_O1_bug_20220214 $ time make exprtk_real_test
clang++ -pedantic-errors -Wall -Wextra -Werror -std=c++11 -O1 -o exprtk_real_test exprtk_real_test.cpp -L/usr/lib -lstdc++ -lm
^Cmake: [Makefile:34: exprtk_real_test] Interrupt (ignored)

real    547m54.763s
user    0m0.004s
sys     0m0.015s

Note: During the run time I did not observe any changes in the amount of memory being consumed by the clang process.

---

The code compiles and links error and warning free on ALL other optimisation levels (O0, O2, O3) for the above denoted version of clang.

Furthermore the code compiles and links error and warning free on ALL optimisation levels for the following compilers and versions:

• g++ 4.3 .. 11
• clang++ 10, 13

[fhahn]

I tried to reproduce the issue with the provided file but for me compilation completes within a few minutes. Could you double check if it still hangs on aa recent build of LLVM's main branch?

If it does, please re-open the issue and provide the pre-processed source file to reproduce (passing -E to clang).

[ArashPartow]

@fhahn: It is still the case as of 38e8880.

How do I go about opening this issue? or should I create a new issue?

---

I've attached the output using the -E command line parameter

clang++ -pedantic-errors -Wall -Wextra -Werror -Wno-long-long -std=c++11 -O1 -E exprtk_real_test.cpp -o exprtk_real_test.out

exprtk_real_test.zip

---

clang++:

clang++ --version
clang version 15.0.0 (https://github.com/llvm/llvm-project.git 38e8880e931293dab8e90cac731e4bda2306836d)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /usr/local/bin

Git log (02:40 Monday, 21 March 2022 (GMT-5)):

commit 38e8880e931293dab8e90cac731e4bda2306836d (HEAD -> main, origin/main, origin/HEAD)
Author: Andrew Litteken <andrew.litteken@gmail.com>
Date:   Sun Mar 13 23:34:30 2022 -0500

    [IROutliner] Do not outlined from functions with optnone

    Since the IROutliner is performing an optimization, it should not outline from functions explicitly marked with optnone. This adds an extra check and test to make sure this does not occur.

    Reviewers: paquette

    Differential Revision: https://reviews.llvm.org/D121567

---

#!/usr/bin/env bash

if cd llvm-project; then
   git fetch --all;
   git fetch --tags;
   git pull;
   git submodule update --init --recursive;
   cd ..;
else
   echo "cloning fresh copy of llvm-project...."
   git clone https://github.com/llvm/llvm-project.git --recurse-submodules;
   cd llvm-project;
   git submodule update --init --recursive;
   cd ..;
   echo "completed cloning fresh copy of llvm-project"
fi

mkdir -p build
cd build

cmake \
    -DCMAKE_CXX_COMPILER_LAUNCHER=ccache \
    -DCMAKE_CXX_COMPILER:FILEPATH=clang++ \
    -DCMAKE_C_COMPILER:FILEPATH=clang \
    -DLLVM_ENABLE_PROJECTS="clang;clang-tools-extra;lld;lldb;compiler-rt" \
    -DCMAKE_BUILD_TYPE=Release \
    ../llvm-project/llvm

make all -j 128
sudo make install -j 6

[fhahn]

@ArashPartow thanks for the update! I am able to reproduce it and will upload a reduced reproducer soon.

[ArashPartow]

@fhahn thanks for the quick feedback 👍 If there's anything I can help with please do let me know.

[fhahn]

Looks like this is hitting non-linear behaviour in DAGCombiner::mergeConsecutiveStores(llvm::StoreSDNode*).

The attached reduced input has ~1500 lines of IR and llc takes ~80s on my system with 86% of the time spent in mergeConsecutiveStores.

slow_dagcombine_visit_store.bc.zip

[fhahn]

FWIW DAGCombiner::mergeConsecutiveStores and co are known to have various scalability issues.