[Bug tree-optimization/20742] New: [4.0/4.1 Regression] Hang in tree_ssa_iv_optimize_loop

[Bug tree-optimization/20742] New: [4.0/4.1 Regression] Hang in tree_ssa_iv_optimize_loop

[jakub at gcc dot gnu dot org]

The following testcase (simplified from lmbench) causes major compile time
regression in tree_ssa_iv_optimize_loop.
Without -DHANG (and with -O2), HEAD gcc needs 0m34.176s, while with GCC 3.4.x
0m0.035s.  On 4.0 branch it even takes substantially longer.
lmbench has 100 such lines, which would take longer than anybody could wait.

-- 
           Summary: [4.0/4.1 Regression] Hang in tree_ssa_iv_optimize_loop
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Severity: critical
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: jakub at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org,rakdver at gcc dot gnu
                    dot org,sebastian dot pop at cri dot ensmp dot fr


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20742

[Bug tree-optimization/20742] [4.0/4.1 Regression] Hang in tree_ssa_iv_optimize_loop

[jakub at gcc dot gnu dot org]

------- Additional Comments From jakub at gcc dot gnu dot org  2005-04-04 11:38 -------
Created an attachment (id=8526)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=8526&action=view)
Testcase


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20742

[Bug tree-optimization/20742] [4.0/4.1 Regression] Hang in tree_ssa_iv_optimize_loop

[jakub at gcc dot gnu dot org]

------- Additional Comments From jakub at gcc dot gnu dot org  2005-04-04 11:40 -------
Oops, attached older version of the testcase.  The latest one had:
#ifdef HANG
#define TEN(x) x x x x x x x x x x
      TEN (TEN (a += b; b -= a;))
#endif
in the loop as well.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20742

[Bug tree-optimization/20742] [4.0/4.1 Regression] Hang in tree_ssa_iv_optimize_loop

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|critical                    |normal
           Keywords|                            |compile-time-hog
   Target Milestone|---                         |4.0.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20742

[Bug tree-optimization/20742] [4.0/4.1 Regression] Hang in tree_ssa_iv_optimize_loop

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2005-04-04 14:03 -------
This is scev analysis problem.  On this testcase, it produces exponentially
large expressions (of form a_5 + b_6 + b_6 - a_5 + b_6 + b_6 - a_5 + b_6 - a_5 ...).

As for possible solutions: more clever folding that would transform this to
c1 * a_5 + c2 * b_6 would help in this particular case, but the possibility that
an exponentially large expression that will not be possible to fold will be produced
by scev would still exist.

Scev probably should keep track of how large expressions it produces, and just give
up if it grows beyond some limit.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20742

[Bug tree-optimization/20742] [4.0/4.1 Regression] Hang in tree_ssa_iv_optimize_loop

[sebastian dot pop at cri dot ensmp dot fr]

------- Additional Comments From sebastian dot pop at cri dot ensmp dot fr  2005-04-04 14:50 -------
Subject: Re:  [4.0/4.1 Regression] Hang in tree_ssa_iv_optimize_loop

rakdver at gcc dot gnu dot org wrote:
> 
> Scev probably should keep track of how large expressions it produces, and just give
> up if it grows beyond some limit.
> 

Okay.  What about putting this limit in chrec_fold_plus_1 and
chrec_fold_multiply?  I think that this will minimize the size of the
patch for fixing this problem.



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20742

[Bug tree-optimization/20742] [4.0/4.1 Regression] Hang in tree_ssa_iv_optimize_loop

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-04-05 01:36:28
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20742

[Bug tree-optimization/20742] [4.0/4.1 Regression] Hang in tree_ssa_iv_optimize_loop

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-04-07 06:21 -------
*** Bug 20803 has been marked as a duplicate of this bug. ***

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dalej at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20742

[Bug tree-optimization/20742] [4.0/4.1 Regression] Hang in tree_ssa_iv_optimize_loop

[mmitchel at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.0.0                       |4.0.1


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20742

[Bug tree-optimization/20742] [4.0 Regression] Hang in tree_ssa_iv_optimize_loop

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-04-21 20:57 -------
Subject: Bug 20742

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	apple-local-200502-branch
Changes by:	dalej@gcc.gnu.org	2005-04-21 20:57:24

Modified files:
	gcc            : ChangeLog params.def tree-chrec.c tree-chrec.h 
	                 tree-scalar-evolution.c 
	gcc/doc        : invoke.texi 

Log message:
	2005-04-20  Dale Johannesen  <dalej@apple.com>
	
	Radar 4080945
	PR 20742
	* params.def (PARAM_SCEV_MAX_EXPR_SIZE):  New.
	* tree-chrec.c (params.h):  New include.
	(chrec_fold_plus_1):  Avoid too deep recursion.
	(reset_evolution_in_loop):  Use build2 not build.
	(tree_contains_chrecs):  Add size argument.
	* tree-chrec.h (tree_constains_chrecs):  Add size argument.
	(tree_does_not_contain_chrecs):  Adjust call to it.
	* tree-scalar-evolution.c (simple_iv):  Ditto.
	* doc/invoke.texi (scev-max-expr-size):  Document.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&only_with_tag=apple-local-200502-branch&r1=2.7489.2.7&r2=2.7489.2.8
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/params.def.diff?cvsroot=gcc&only_with_tag=apple-local-200502-branch&r1=1.54.4.2&r2=1.54.4.3
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-chrec.c.diff?cvsroot=gcc&only_with_tag=apple-local-200502-branch&r1=2.12.8.2&r2=2.12.8.3
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-chrec.h.diff?cvsroot=gcc&only_with_tag=apple-local-200502-branch&r1=2.6&r2=2.6.10.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-scalar-evolution.c.diff?cvsroot=gcc&only_with_tag=apple-local-200502-branch&r1=2.16.6.1&r2=2.16.6.2
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/doc/invoke.texi.diff?cvsroot=gcc&only_with_tag=apple-local-200502-branch&r1=1.579.2.4&r2=1.579.2.5



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20742

[Bug tree-optimization/20742] [4.0 Regression] Hang in tree_ssa_iv_optimize_loop

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-05-03 23:05 -------
Subject: Bug 20742

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	gcc-4_0-rhl-branch
Changes by:	jakub@gcc.gnu.org	2005-05-03 23:05:32

Modified files:
	gcc            : ChangeLog Makefile.in params.def tree-chrec.c 
	                 tree-chrec.h tree-scalar-evolution.c 
	gcc/doc        : invoke.texi 
	gcc/testsuite  : ChangeLog 
Added files:
	gcc/testsuite/gcc.c-torture/compile: 20050423-1.c 

Log message:
	2005-05-04  Sebastian Pop  <sebastian.pop@cri.ensmp.fr>
	
	PR tree-optimization/20742
	* Makefile.in (tree-chrec.o): Depend on params.h.
	* params.def (PARAM_SCEV_MAX_EXPR_SIZE): New parameter with
	default value 20.
	* tree-chrec.c: Depend on params.h.  Replace build with buildN.
	(chrec_fold_plus_1): Fail with a chrec_don_know when the size of
	the expression exceeds PARAM_SCEV_MAX_EXPR_SIZE.
	(tree_contains_chrecs): Compute an estimation of the size of the
	given expression.
	* tree-chrec.h (tree_contains_chrecs): Modify its declaration.
	(tree_does_not_contain_chrecs): Update the use of tree_contains_chrecs.
	* tree-scalar-evolution.c (simple_iv): Ditto.
	* doc/invoke.texi (scev-max-expr-size): Documented.
	
	2005-05-04  Jakub Jelinek  <jakub@redhat.com>
	
	PR tree-optimization/20742
	* gcc.c-torture/compile/20050423-1.c: New test.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-rhl-branch&r1=2.7592.2.10.2.27&r2=2.7592.2.10.2.28
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/Makefile.in.diff?cvsroot=gcc&only_with_tag=gcc-4_0-rhl-branch&r1=1.1447.4.4&r2=1.1447.4.5
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/params.def.diff?cvsroot=gcc&only_with_tag=gcc-4_0-rhl-branch&r1=1.54.8.1&r2=1.54.8.2
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-chrec.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-rhl-branch&r1=2.12.14.2&r2=2.12.14.3
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-chrec.h.diff?cvsroot=gcc&only_with_tag=gcc-4_0-rhl-branch&r1=2.6&r2=2.6.16.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-scalar-evolution.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-rhl-branch&r1=2.17.6.1&r2=2.17.6.2
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/doc/invoke.texi.diff?cvsroot=gcc&only_with_tag=gcc-4_0-rhl-branch&r1=1.583.2.1.2.10&r2=1.583.2.1.2.11
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-rhl-branch&r1=1.5084.2.9.2.22&r2=1.5084.2.9.2.23
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.c-torture/compile/20050423-1.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-rhl-branch&r1=NONE&r2=1.1.2.1



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20742

[Bug tree-optimization/20742] [4.0 Regression] Hang in tree_ssa_iv_optimize_loop

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-06-06 12:13 -------
Subject: Bug 20742

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	gcc-4_0-branch
Changes by:	spop@gcc.gnu.org	2005-06-06 12:12:53

Modified files:
	gcc            : ChangeLog params.def tree-chrec.c tree-chrec.h 
	                 tree-scalar-evolution.c 
	gcc/doc        : invoke.texi 

Log message:
	PR tree-optimization/20742
	* params.def (PARAM_SCEV_MAX_EXPR_SIZE): New parameter with
	default value 20.
	* tree-chrec.c: Depend on params.h.  Replace build with buildN,
	and fold build with fold_buildN.
	(chrec_fold_plus_1): Fail with a chrec_don_know when the size of
	the expression exceeds PARAM_SCEV_MAX_EXPR_SIZE.
	(tree_contains_chrecs): Compute an estimation of the size of the
	given expression.
	* tree-chrec.h (tree_contains_chrecs): Modify its declaration.
	(tree_does_not_contain_chrecs): Update the use of tree_contains_chrecs.
	* tree-scalar-evolution.c (simple_iv): Ditto.
	* doc/invoke.texi (scev-max-expr-size): Documented.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=2.7592.2.279&r2=2.7592.2.280
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/params.def.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=1.54.6.1&r2=1.54.6.2
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-chrec.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=2.12.12.2&r2=2.12.12.3
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-chrec.h.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=2.6&r2=2.6.14.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-scalar-evolution.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=2.17.4.1&r2=2.17.4.2
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/doc/invoke.texi.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=1.583.2.18&r2=1.583.2.19



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20742

[Bug tree-optimization/20742] [4.0 Regression] Hang in tree_ssa_iv_optimize_loop

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-06-06 12:59 -------
Fixed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20742

[Bug tree-optimization/20742] [4.0 Regression] Hang in tree_ssa_iv_optimize_loop

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-06-07 19:54 -------
Subject: Bug 20742

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	spop@gcc.gnu.org	2005-06-07 19:54:23

Added files:
	gcc/testsuite/gcc.c-torture/compile: 20050423-1.c 

Log message:
	* 20050423-1.c: Testcase for PR tree-optimization/20742.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.c-torture/compile/20050423-1.c.diff?cvsroot=gcc&r1=1.1&r2=1.2



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20742