Fix PR85475

Message ID alpine.LSU.2.20.1804201102350.31014@zhemvz.fhfr.qr
State New
Headers show
Series
  • Fix PR85475
Related show

Commit Message

Richard Biener April 20, 2018, 9:05 a.m.
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 <rguenther@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.

Patch

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;
+}