Infinite loop in reassociate (with -ffast-math)

[llvmbot]

Bugzilla Link	34078
Resolution	FIXED
Resolved on	Sep 05, 2017 14:35
Version	4.0
OS	Linux
Blocks	#33196
Attachments	reduced .bc file from bugpoint, bugpoint output to terminal
Reporter	LLVM Bugzilla Contributor
CC	@zmodem,@hfinkel,@RKSimon,@rotateright
Fixed by commit(s)	311554, 311603

Extended Description

clang++ hangs indefinitely when compiling the following code with -O2 -ffast-math

#include
void f(double A) {
double B = 1. - A - pow(A, 2) / 2.;
std::complex C = B + B;
std::complex D = 1. / C;
}

or the following code with -O1 -ffast-math

#include
void f(double A) {
double B = 1. - A - pow(A, 2) / 2.;
std::complex C = B + B;
}

(I originally observed the bug while compiling https://github.com/laurentkneip/opengv/blob/master/src/math/roots.cpp, and reduced).

Bugpoint suggests it is the reassociate pass. Reduced output attached.

[llvmbot]

assigned to @zmodem

[llvmbot]

This might be the same as #31861

[llvmbot]

Yes, it's an infloop in reassociate.

define double @​patatino(double %A) {
%sub = fsub fast double 1.000000e+00, %A
%pow2 = fmul double %A, %A
%div = fmul fast double %pow2, 5.000000e-01
%sub1 = fsub fast double %sub, %div
%add = fadd fast double %sub1, %sub1
ret double %add
}

$ ./opt blah.ll -reassociate
^C

[llvmbot]

Tentatively marking this as release blocker, let's see where the thing goes.

[llvmbot]

When redoing instructions we get into a cycle like the following:

In0: C + (-0.000000e+00 - B5.0)
Rule: Replace (0 - X) with (X * -1).
Out0: (B-5.0) + C

In1: (B*-5.0) + C
Rule: Replace (X + (-Constant * Y)) with (X - (Constant * Y)).
Out1: C - B*5.0

In2: C - B5.0
Rule: Replace (X - Y) with (X + (0 - Y)).
Out2: C + (-0.000000e+00 - B5.0)

Cycle: Out2 == In1

FWIW, this has little if nothing to do with fast math being enabled (it is necessary to expose the issue in this example, but I can very easily see an integer equivalent running into the same problem).

[zmodem]

Reproduces with 5.0, 4.0, 3.9, 3.8 but not 3.7.

Since it's not a regression I won't block 5.0 on it.

Bisection points to
r253240 - Add intermediate subtract instructions to reassociation worklist

which was committed by Owen on behalf of Aditya (who I couldn't find a bugzilla account for).

[llvmbot]

FWIW, this has little if nothing to do with fast math being enabled (it is
necessary to expose the issue in this example, but I can very easily see an
integer equivalent running into the same problem).

Nevermind! This has everything to do with FP instructions. :)

Specifically, the cycle is being caused by the canonicalizeNegConstExpr() function, which only considers FMul and FDiv instructions.

This optimization says (X + Y*-Const) -> (X - Y*Const), but the BreakUpSubtract optimization does the exact opposite.

[llvmbot]

Should be fixed in r311554.

[llvmbot]

Marking this as a 5.0.0 blocker as I think it would be good to include. The change is targeted and shouldn't have any fallout besides what is intended. No code owner for reassociation that I know of, but Chris, Owen, and I are the top contributors (for better or worse ;)). AFAIC, this is fairly safe to cherry pick in after a little bake time on the bots.

[zmodem]

Marking this as a 5.0.0 blocker as I think it would be good to include. The
change is targeted and shouldn't have any fallout besides what is intended.
No code owner for reassociation that I know of, but Chris, Owen, and I are
the top contributors (for better or worse ;)). AFAIC, this is fairly safe
to cherry pick in after a little bake time on the bots.

Sounds good to me. Thanks for fixing!

[llvmbot]

Marking this as a 5.0.0 blocker as I think it would be good to include. The
change is targeted and shouldn't have any fallout besides what is intended.
No code owner for reassociation that I know of, but Chris, Owen, and I are
the top contributors (for better or worse ;)). AFAIC, this is fairly safe
to cherry pick in after a little bake time on the bots.

Sounds good to me. Thanks for fixing!

np!

[zmodem]

Merged in r311603.

[llvmbot]

Merged in r311603.

Thanks, Hans!