This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[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;
  


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]