The following fixes exponential complexity with
/* Reassociate (X * CST) * Y to (X * Y) * CST. This does not introduce
signed overflow for CST != 0 && CST != -1. */
(simplify
(mult:c (mult:s @0 INTEGER_CST@1) @2)
(if (TREE_CODE (@2) != INTEGER_CST
&& !integer_zerop (@1) && !integer_minus_onep (@1))
(mult (mult @0 @2) @1)))
when the inner multiply is present multiple times in the expression.
:s doesn't protect us here because it fires too late.
Maybe already bootstrapped & tested but the machine died on me so,
re-bootstrapping and testing on x86_64-unknown-linux-gnu.
Richard.
2018-04-20 Richard Biener <[email protected]>
PR middle-end/85475
* match.pd ((X * CST) * Y -> (X * Y) * CST): Avoid exponential
complexity by forcing a single use of the multiply operand.
* gcc.dg/torture/pr85475.c: New testcase.
Index: gcc/match.pd
===================================================================
--- gcc/match.pd (revision 259515)
+++ gcc/match.pd (working copy)
@@ -2578,8 +2578,9 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
/* Reassociate (X * CST) * Y to (X * Y) * CST. This does not introduce
signed overflow for CST != 0 && CST != -1. */
(simplify
- (mult:c (mult:s @0 INTEGER_CST@1) @2)
+ (mult:c (mult:s@3 @0 INTEGER_CST@1) @2)
(if (TREE_CODE (@2) != INTEGER_CST
+ && single_use (@3)
&& !integer_zerop (@1) && !integer_minus_onep (@1))
(mult (mult @0 @2) @1)))
Index: gcc/testsuite/gcc.dg/torture/pr85475.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/pr85475.c (nonexistent)
+++ gcc/testsuite/gcc.dg/torture/pr85475.c (working copy)
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-fpeel-loops" } */
+
+int
+nj (int le)
+{
+ int zb;
+
+ for (zb = 0; zb < 16; ++zb)
+ le += le;
+
+ return le * le;
+}
