Reassociate takes forever on a long chain of operations.

[Quuxplusone]

Bugzilla Link	PR13021
Status	CONFIRMED
Importance	P normal
Reported by	Antoine Balestrat (antoine.balestrat@gmail.com)
Reported on	2012-06-04 03:14:12 -0700
Last modified on	2018-02-17 09:32:13 -0800
Version	trunk
Hardware	PC Linux
CC	anton@korobeynikov.info, baldrick@free.fr, ditaliano@apple.com, geek4civic@gmail.com, llvm-bugs@lists.llvm.org, willdtz@gmail.com
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also

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:
0.  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
1.  <eof> parser at end of file
2.  Per-module optimization passes
3.  Running pass 'CallGraph Pass Manager' on module 'file.c'.
4.  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

[Quuxplusone]

Maybe due to reassociate bug

[Quuxplusone]

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.

[Quuxplusone]

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.

[Quuxplusone]

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
}