search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
27.52k stars 11.3k forks source link

Reassociate takes forever on a long chain of operations. #13393

Open llvmbot opened 12 years ago

llvmbot commented 12 years ago
Bugzilla Link 13021
Version trunk
OS Linux
Reporter LLVM Bugzilla Contributor
CC @asl

Extended Description

This testcase makes Clang as of r157903 go into what looks like an infinite loop, which causes very high memory consumption.

$ cat file.c unsigned char a, i;

void f1(void) { for(i = 0; i < 30; i++) a *= a; }

void f2(void) { f1(); }

$ ulimit -t 60

$ ~/clang/build/Release+Asserts/bin/clang -O3 -w file.c 0 clang 0x0000000001bb22af 1 clang 0x0000000001bb27c4 2 libpthread.so.0 0x00007f9488e04280 3 clang 0x00000000018ba2fb 4 clang 0x00000000018b9bf3 5 clang 0x00000000018b3d7b 6 clang 0x00000000018b305b 7 clang 0x0000000001b2036b llvm::FPPassManager::runOnFunction(llvm::Function&) + 443 8 clang 0x0000000001988225 9 clang 0x0000000001b20843 llvm::MPPassManager::runOnModule(llvm::Module&) + 419 10 clang 0x0000000001b20dc8 llvm::PassManagerImpl::run(llvm::Module&) + 408 11 clang 0x0000000001b20f2a llvm::PassManager::run(llvm::Module&) + 10 12 clang 0x0000000000786b20 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::Module, clang::BackendAction, llvm::raw_ostream) + 4976 13 clang 0x00000000007849ea 14 clang 0x00000000008add35 clang::ParseAST(clang::Sema&, bool, bool) + 389 15 clang 0x0000000000783a78 clang::CodeGenAction::ExecuteAction() + 184 16 clang 0x000000000065270d clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) + 973 17 clang 0x000000000063b0ab clang::ExecuteCompilerInvocation(clang::CompilerInstance) + 3307 18 clang 0x000000000063038b cc1_main(char const, char const, char const, void*) + 731 19 clang 0x000000000063772a main + 3482 20 libc.so.6 0x00007f948805d4bd __libc_start_main + 253 21 clang 0x000000000062ffed Stack dump:

  1. Program arguments: /home/merkil/git/clang/build/Release+Asserts/bin/clang -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -disable-free -main-file-name file.c -mrelocation-model static -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -target-linker-version 2.22 -momit-leaf-frame-pointer -resource-dir /home/merkil/git/clang/build/Release+Asserts/bin/../lib/clang/3.2 -fmodule-cache-path /var/tmp/clang-module-cache -internal-isystem /usr/local/include -internal-isystem /home/merkil/git/clang/build/Release+Asserts/bin/../lib/clang/3.2/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -w -fdebug-compilation-dir /home/merkil/garbage/creduce/creduce -ferror-limit 19 -fmessage-length 96 -mstackrealign -fgnu-runtime -fobjc-runtime-has-arc -fobjc-runtime-has-weak -fobjc-fragile-abi -fdiagnostics-show-option -fcolor-diagnostics -o /tmp/file-tIT535.o -x c file.c
  2. parser at end of file
  3. Per-module optimization passes
  4. Running pass 'CallGraph Pass Manager' on module 'file.c'.
  5. Running pass 'Reassociate expressions' on function '@f2' clang: error: unable to execute command: CPU time limit exceeded clang: error: clang frontend command failed due to signal (use -v to see invocation) clang: note: diagnostic msg: Please submit a bug report to http://llvm.org/bugs/ and include command line arguments and all diagnostic information. clang version 3.2 (trunk 157903) Target: x86_64-unknown-linux-gnu Thread model: posix clang: note: diagnostic msg: Preprocessed source(s) and associated run script(s) are located at: clang: note: diagnostic msg: /tmp/file-hnsPlF.i clang: note: diagnostic msg: /tmp/file-hnsPlF.sh
llvmbot commented 2 years ago

mentioned in issue llvm/llvm-bugzilla-archive#16067

llvmbot commented 7 years ago

Test where this still applies:

define float @​patatino(float %x) { %t0 = fmul fast float %x, %x %t1 = fmul fast float %t0, %t0 %t2 = fmul fast float %t1, %t1 %t3 = fmul fast float %t2, %t2 %t4 = fmul fast float %t3, %t3 %t5 = fmul fast float %t4, %t4 %t6 = fmul fast float %t5, %t5 %t7 = fmul fast float %t6, %t6 %t8 = fmul fast float %t7, %t7 %t9 = fmul fast float %t8, %t8 %t10 = fmul fast float %t9, %t9 %t11 = fmul fast float %t10, %t10 %t12 = fmul fast float %t11, %t11 %t13 = fmul fast float %t12, %t12 %t14 = fmul fast float %t13, %t13 %t15 = fmul fast float %t14, %t14 %t16 = fmul fast float %t15, %t15 %t17 = fmul fast float %t16, %t16 %t18 = fmul fast float %t17, %t17 %t19 = fmul fast float %t18, %t18 %t20 = fmul fast float %t19, %t19 %t21 = fmul fast float %t20, %t20 %t22 = fmul fast float %t21, %t21 %t23 = fmul fast float %t22, %t22 %t24 = fmul fast float %t23, %t23 %t25 = fmul fast float %t24, %t24 %t26 = fmul fast float %t25, %t25 %t27 = fmul fast float %t26, %t26 %t28 = fmul fast float %t27, %t27 ret float %t28 }

llvmbot commented 12 years ago

I've been working on this but haven't finished yet. I've disabled the transform at the origin of the problem for the moment.

llvmbot commented 12 years ago

Yes, it looks like this is me, and corresponds to this FIXME in reassociate:

// FIXME: Rather than repeating values Weight times, use a vector of // (ValueEntry, multiplicity) pairs.

It sees a multiply expression which is a**67108864, and in order to be compatible with the existing reassociate transforms, which expect this in the form "a list of copies of a", it pushes 67108864 copies of a into the vector.

asl commented 12 years ago

Maybe due to reassociate bug