This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Fix PR40062, exponential behavior in SCEV
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Cc: Sebastian Pop <sebpop at gmail dot com>
- Date: Fri, 8 May 2009 12:09:23 +0200 (CEST)
- Subject: [PATCH] Fix PR40062, exponential behavior in SCEV
This fixes PR40062, a case where SCEV at -O3 uses up all memory
in my machine (no idea what it would take if it would finish).
The issue is that while we limit recursion depth in walking
PHI nodes somewhat we do not effectively limit breath of the search
for a path through the loop. This effectively makes the
complexity exponential if you have, like in the testcase, several
non-loop PHI nodes with a large number of arguments.
The fix is to take this into account like for example with the following.
Bootstrap / regtest in progress. Sebastian - are you ok with that?
Thanks,
Richard.
2009-05-08 Richard Guenther <rguenther@suse.de>
PR tree-optimization/40062
* tree-scalar-evolution.c (follow_ssa_edge_in_condition_phi):
Avoid exponential behavior.
Index: gcc/tree-scalar-evolution.c
===================================================================
*** gcc/tree-scalar-evolution.c (revision 147237)
--- gcc/tree-scalar-evolution.c (working copy)
*************** follow_ssa_edge_in_condition_phi (struct
*** 1320,1330 ****
*evolution_of_loop = evolution_of_branch;
- /* If the phi node is just a copy, do not increase the limit. */
n = gimple_phi_num_args (condition_phi);
- if (n > 1)
- limit++;
-
for (i = 1; i < n; i++)
{
/* Quickly give up when the evolution of one of the branches is
--- 1320,1326 ----
*************** follow_ssa_edge_in_condition_phi (struct
*** 1332,1341 ****
if (*evolution_of_loop == chrec_dont_know)
return t_true;
res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
halting_phi,
&evolution_of_branch,
! init, limit);
if (res == t_false || res == t_dont_know)
return res;
--- 1328,1339 ----
if (*evolution_of_loop == chrec_dont_know)
return t_true;
+ /* Increase the limit by the PHI argument number to avoid exponential
+ time and memory complexity. */
res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
halting_phi,
&evolution_of_branch,
! init, limit + i);
if (res == t_false || res == t_dont_know)
return res;