[Bug tree-optimization/16656] New: [lno] huge amounts of time spent in find_best_candidate

[Bug tree-optimization/16656] New: [lno] huge amounts of time spent in find_best_candidate

[falk at debian dot org]

3.5-tree-ssa-lno 20040719 (merged 20040718)

The attached 297k c++ source takes at least 90 minutes to compile on my system
at -O, apparently it triggers an infinite loop or at least really bad worst case
time complexity. g++ 3.5.0 20040627 takes "only" about two minutes at -O.

According to oprofile, 99.9403% of the time is spent in find_best_candidate.

-- 
           Summary: [lno] huge amounts of time spent in find_best_candidate
           Product: gcc
           Version: lno
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: falk at debian dot org
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: alphaev68-unknown-linux-gnu
  GCC host triplet: alphaev68-unknown-linux-gnu
GCC target triplet: alphaev68-unknown-linux-gnu


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

[Bug tree-optimization/16656] [lno] huge amounts of time spent in find_best_candidate

[falk at debian dot org]

------- Additional Comments From falk at debian dot org  2004-07-21 11:39 -------
Created an attachment (id=6792)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=6792&action=view)
Test case


-- 


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

[Bug tree-optimization/16656] [lno] huge amounts of time spent in find_best_candidate

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |critical
   Target Milestone|---                         |lno


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

[Bug tree-optimization/16656] [lno] huge amounts of time spent in find_best_candidate

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2004-07-22 03:30 -------
The function apparently contains a loop with some 1500 memory references whose 
addresses are givs... ooops...

Just giving up on such a beast seems a sane choice to me.  I will send patch 
soon.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-07-22 03:30:01
               date|                            |


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

[Bug tree-optimization/16656] [lno] huge amounts of time spent in find_best_candidate

[giovannibajo at libero dot it]

------- Additional Comments From giovannibajo at libero dot it  2004-07-22 13:42 -------
(In reply to comment #2)

> Just giving up on such a beast seems a sane choice to me.  I will send patch 
> soon.

Mention the PR number in a comment. Maybe, if one day the algorithm is 
improved, we can test it again with this degenerated case.

-- 


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

[Bug tree-optimization/16656] [lno] huge amounts of time spent in find_best_candidate

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2004-07-23 14:03 -------
Subject: Bug 16656

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	lno-branch
Changes by:	rakdver@gcc.gnu.org	2004-07-23 14:03:25

Modified files:
	gcc            : ChangeLog.lno tree-ssa-loop-ivopts.c 

Log message:
	PR tree-optimization/16656
	* tree-ssa-loop-ivopts.c (CONSIDER_ALL_CANDIDATES_BOUND): Increase
	to 30.
	(MAX_CONSIDERED_USES): New.
	(set_cost_up_to, try_add_cand_for): New functions.
	(set_cost): Use set_cost_up_to.
	(find_best_candidate, get_initial_solution): Improve efficiency.
	(tree_ssa_iv_optimize_loop): Fail if there are more than
	MAX_CONSIDERED_USES iv uses in the loop.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.lno.diff?cvsroot=gcc&only_with_tag=lno-branch&r1=1.1.2.232&r2=1.1.2.233
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-loop-ivopts.c.diff?cvsroot=gcc&only_with_tag=lno-branch&r1=1.1.2.47&r2=1.1.2.48



-- 


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

[Bug tree-optimization/16656] [lno] huge amounts of time spent in find_best_candidate

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2004-07-23 14:11 -------
Fixed.

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


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