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 <rguent...@suse.de> 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; +}