[Bug tree-optimization/23942] [4.1 Regression] loop problem / testcase takes very long time to compile
--- Additional Comments From pinskia at gcc dot gnu dot org 2005-09-26 19:55 --- Fixed. -- What|Removed |Added Status|ASSIGNED|RESOLVED Resolution||FIXED http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23942
[Bug tree-optimization/23942] [4.1 Regression] loop problem / testcase takes very long time to compile
--- Additional Comments From cvs-commit at gcc dot gnu dot org 2005-09-26 18:44 --- Subject: Bug 23942 CVSROOT:/cvs/gcc Module name:gcc Changes by: [EMAIL PROTECTED] 2005-09-26 18:44:23 Modified files: gcc: Makefile.in Log message: PR tree-optimization/23942 * Makefile.in (SCEV_H): Depends on PARAMS_H. * tree-scalar-evolution.c: Include params.h. (t_bool): New enum. (follow_ssa_edge, follow_ssa_edge_in_rhs, follow_ssa_edge_in_condition_phi_branch, follow_ssa_edge_in_condition_phi, follow_ssa_edge_inner_loop_phi): Change return type to t_bool. Use a parameter to limit the size of trees that are walked before stopping (analyze_evolution_in_loop): Initialize the limit to 0. (follow_ssa_edge): Give up by returning t_dont_know if the limit exceeds PARAM_SCEV_MAX_EXPR_SIZE. Patches: http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/Makefile.in.diff?cvsroot=gcc&r1=1.1541&r2=1.1542 -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23942
[Bug tree-optimization/23942] [4.1 Regression] loop problem / testcase takes very long time to compile
--- Additional Comments From cvs-commit at gcc dot gnu dot org 2005-09-26 18:43 --- Subject: Bug 23942 CVSROOT:/cvs/gcc Module name:gcc Changes by: [EMAIL PROTECTED] 2005-09-26 18:43:09 Modified files: gcc: ChangeLog tree-scalar-evolution.c Log message: PR tree-optimization/23942 * Makefile.in (SCEV_H): Depends on PARAMS_H. * tree-scalar-evolution.c: Include params.h. (t_bool): New enum. (follow_ssa_edge, follow_ssa_edge_in_rhs, follow_ssa_edge_in_condition_phi_branch, follow_ssa_edge_in_condition_phi, follow_ssa_edge_inner_loop_phi): Change return type to t_bool. Use a parameter to limit the size of trees that are walked before stopping (analyze_evolution_in_loop): Initialize the limit to 0. (follow_ssa_edge): Give up by returning t_dont_know if the limit exceeds PARAM_SCEV_MAX_EXPR_SIZE. Patches: http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.10025&r2=2.10026 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-scalar-evolution.c.diff?cvsroot=gcc&r1=2.38&r2=2.39 -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23942
[Bug tree-optimization/23942] [4.1 Regression] loop problem / testcase takes very long time to compile
--- Additional Comments From sebastian dot pop at cri dot ensmp dot fr
2005-09-21 17:02 ---
Subject: Re: [4.1 Regression] loop problem / testcase takes very long time to
compile
> Random break stops things typically somewhere inside 140 nested calls in scev
> (follow_ssa_edge and friends). I seem to recall there is some backtracking
> involved, I will check.
>
A patch around these lines should fix the problem: it limits the
number of arcs that we walk before giving up. For the moment I'm
returning "didn't found a path from P to P", when we give up. We have
to handle a "don't know" symbol for this case.
I'll test a patch similar to the following tomorow.
Index: Makefile.in
===
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1541
diff -d -u -p -r1.1541 Makefile.in
--- Makefile.in 14 Sep 2005 09:26:41 - 1.1541
+++ Makefile.in 21 Sep 2005 16:51:48 -
@@ -767,7 +767,7 @@ TREE_SSA_LIVE_H = tree-ssa-live.h $(PART
PRETTY_PRINT_H = pretty-print.h input.h $(OBSTACK_H)
DIAGNOSTIC_H = diagnostic.h diagnostic.def $(PRETTY_PRINT_H)
C_PRETTY_PRINT_H = c-pretty-print.h $(PRETTY_PRINT_H) $(C_COMMON_H) $(TREE_H)
-SCEV_H = tree-scalar-evolution.h $(GGC_H) tree-chrec.h
+SCEV_H = tree-scalar-evolution.h $(GGC_H) tree-chrec.h $(PARAMS_H)
LAMBDA_H = lambda.h tree.h vec.h $(GGC_H)
TREE_DATA_REF_H = tree-data-ref.h $(LAMBDA_H)
VARRAY_H = varray.h $(MACHMODE_H) $(SYSTEM_H) coretypes.h $(TM_H)
Index: tree-scalar-evolution.c
===
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.38
diff -d -u -p -r2.38 tree-scalar-evolution.c
--- tree-scalar-evolution.c 20 Sep 2005 07:09:20 - 2.38
+++ tree-scalar-evolution.c 21 Sep 2005 16:51:48 -
@@ -251,6 +251,7 @@ Software Foundation, 51 Franklin Street,
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
#include "flags.h"
+#include "params.h"
static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
static tree resolve_mixers (struct loop *, tree);
@@ -1022,17 +1023,14 @@ select_loops_exit_conditions (struct loo
/* Depth first search algorithm. */
-static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *);
+static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int);
/* Follow the ssa edge into the right hand side RHS of an assignment.
Return true if the strongly connected component has been found. */
static bool
-follow_ssa_edge_in_rhs (struct loop *loop,
- tree at_stmt,
- tree rhs,
- tree halting_phi,
- tree *evolution_of_loop)
+follow_ssa_edge_in_rhs (struct loop *loop, tree at_stmt, tree rhs,
+ tree halting_phi, tree *evolution_of_loop, int limit)
{
bool res = false;
tree rhs0, rhs1;
@@ -1050,7 +1048,7 @@ follow_ssa_edge_in_rhs (struct loop *loo
case NOP_EXPR:
/* This assignment is under the form "a_1 = (cast) rhs. */
res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
- halting_phi, evolution_of_loop);
+ halting_phi, evolution_of_loop, limit);
*evolution_of_loop = chrec_convert (TREE_TYPE (rhs),
*evolution_of_loop, at_stmt);
break;
@@ -1063,7 +1061,7 @@ follow_ssa_edge_in_rhs (struct loop *loo
case SSA_NAME:
/* This assignment is under the form: "a_1 = b_2". */
res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop);
+ (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit);
break;
case PLUS_EXPR:
@@ -1081,7 +1079,7 @@ follow_ssa_edge_in_rhs (struct loop *loo
"a = b + c". */
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
-evolution_of_loop);
+evolution_of_loop, limit);
if (res)
*evolution_of_loop = add_to_evolution
@@ -1093,7 +1091,7 @@ follow_ssa_edge_in_rhs (struct loop *loo
{
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
-evolution_of_loop);
+evolution_of_loop, limit);
if (res)
*evolution_of_loop = add_to_evolution
@@ -1109,7 +1107,7 @@ follow_ssa_edge_in_rhs (struct loop *loo
"a = b + ...". */
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
-evolution_of_loop);
+evolution_of_loop, limit);
if (res)
*evolution_of_loop = add_to_evolution
(loop->num, chrec_convert
[Bug tree-optimization/23942] [4.1 Regression] loop problem / testcase takes very long time to compile
--- Additional Comments From rakdver at gcc dot gnu dot org 2005-09-20 14:56 --- Random break stops things typically somewhere inside 140 nested calls in scev (follow_ssa_edge and friends). I seem to recall there is some backtracking involved, I will check. -- What|Removed |Added AssignedTo|unassigned at gcc dot gnu |rakdver at gcc dot gnu dot |dot org |org Status|NEW |ASSIGNED http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23942
[Bug tree-optimization/23942] [4.1 Regression] loop problem / testcase takes very long time to compile
--- Additional Comments From pinskia at gcc dot gnu dot org 2005-09-18 17:10 --- Confirmed, this is a really bad compile time regression. -- What|Removed |Added Status|UNCONFIRMED |NEW Ever Confirmed||1 Known to work||4.0.0 3.4.0 Last reconfirmed|-00-00 00:00:00 |2005-09-18 17:10:56 date|| http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23942
[Bug tree-optimization/23942] [4.1 Regression] loop problem / testcase takes very long time to compile
-- What|Removed |Added CC||spop at gcc dot gnu dot org Keywords||compile-time-hog http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23942
[Bug tree-optimization/23942] [4.1 Regression] loop problem / testcase takes very long time to compile
-- What|Removed |Added Known to fail||4.1.0 Target Milestone|--- |4.1.0 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23942
[Bug tree-optimization/23942] [4.1 Regression] loop problem / testcase takes very long time to compile
-- What|Removed |Added Summary|loop problem / testcase |[4.1 Regression] loop |takes very long time to |problem / testcase takes |compile |very long time to compile http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23942
