[Bug tree-optimization/23942] New: loop problem / testcase takes very long time to compile

[Bug tree-optimization/23942] New: loop problem / testcase takes very long time to compile

[marcus at jet dot franken dot de]

the following testcase (extracted from xaos) takes very long time to compile,  
  
a shorter version (just remove some tmp1 = .... lines) takes:  
  
 tree loop bounds      :  40.23 (100%) usr   0.02 (67%) sys  40.87 (100%) wall       
28 kB ( 1%) ggc

-- 
           Summary: loop problem / testcase takes very long time to compile
           Product: gcc
           Version: 4.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: marcus at jet dot franken dot de
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: x86_64-unknown-linux-gnu
  GCC host triplet: x86_64-unknown-linux-gnu
GCC target triplet: x86_64-unknown-linux-gnu


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

[Bug tree-optimization/23942] loop problem / testcase takes very long time to compile

[marcus at jet dot franken dot de]

------- Additional Comments From marcus at jet dot franken dot de  2005-09-18 11:08 -------
Created an attachment (id=9758)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=9758&action=view)
formulas.i

gcc -c -O2 formulas.i

-- 


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

[marcus at jet dot franken dot de]

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

[Bug tree-optimization/23942] [4.1 Regression] loop problem / testcase takes very long time to compile

[rguenth at gcc dot gnu dot org]

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

[pinskia at gcc dot gnu dot org]

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

[pinskia at gcc dot gnu dot org]

------- 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|0000-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

[rakdver at gcc dot gnu dot org]

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

[sebastian dot pop at cri dot ensmp dot fr]

------- 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 -0000	1.1541
+++ Makefile.in	21 Sep 2005 16:51:48 -0000
@@ -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 -0000	2.38
+++ tree-scalar-evolution.c	21 Sep 2005 16:51:48 -0000
@@ -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
 \f
 /* 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 (type_rhs, *evolution_of_loop,
@@ -1124,7 +1122,7 @@ follow_ssa_edge_in_rhs (struct loop *loo
 	     "a = ... + c".  */
 	  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 
 	      (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
@@ -1152,7 +1150,7 @@ follow_ssa_edge_in_rhs (struct loop *loo
 	  /* Match an assignment under the form: 
 	     "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 (type_rhs, *evolution_of_loop,
@@ -1182,7 +1180,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 = chrec_dont_know;
@@ -1191,7 +1189,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 = chrec_dont_know;
@@ -1204,7 +1202,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 = chrec_dont_know;
 	    }
@@ -1216,7 +1214,7 @@ follow_ssa_edge_in_rhs (struct loop *loo
 	     "a = ... * c".  */
 	  res = follow_ssa_edge 
 	    (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 
-	     evolution_of_loop);
+	     evolution_of_loop, limit);
 	  if (res)
 	    *evolution_of_loop = chrec_dont_know;
 	}
@@ -1236,7 +1234,7 @@ follow_ssa_edge_in_rhs (struct loop *loo
 	tree op0 = ASSERT_EXPR_VAR (rhs);
 	if (TREE_CODE (op0) == SSA_NAME)
 	  res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
-				 halting_phi, evolution_of_loop);
+				 halting_phi, evolution_of_loop, limit);
 	else
 	  res = false;
 	break;
@@ -1277,7 +1275,7 @@ follow_ssa_edge_in_condition_phi_branch 
 					 tree condition_phi, 
 					 tree halting_phi,
 					 tree *evolution_of_branch,
-					 tree init_cond)
+					 tree init_cond, int limit)
 {
   tree branch = PHI_ARG_DEF (condition_phi, i);
   *evolution_of_branch = chrec_dont_know;
@@ -1291,7 +1289,7 @@ follow_ssa_edge_in_condition_phi_branch 
     {
       *evolution_of_branch = init_cond;
       return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi, 
-			      evolution_of_branch);
+			      evolution_of_branch, limit);
     }
 
   /* This case occurs when one of the condition branches sets 
@@ -1311,7 +1309,7 @@ static bool
 follow_ssa_edge_in_condition_phi (struct loop *loop,
 				  tree condition_phi, 
 				  tree halting_phi, 
-				  tree *evolution_of_loop)
+				  tree *evolution_of_loop, int limit)
 {
   int i;
   tree init = *evolution_of_loop;
@@ -1320,7 +1318,7 @@ follow_ssa_edge_in_condition_phi (struct
   if (!follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
 						halting_phi,
 						&evolution_of_branch,
-						init))
+						init, limit))
     return false;
   *evolution_of_loop = evolution_of_branch;
 
@@ -1334,7 +1332,7 @@ follow_ssa_edge_in_condition_phi (struct
       if (!follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
 						    halting_phi,
 						    &evolution_of_branch,
-						    init))
+						    init, limit))
 	return false;
 
       *evolution_of_loop = chrec_merge (*evolution_of_loop,
@@ -1353,7 +1351,7 @@ static bool
 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
 				tree loop_phi_node, 
 				tree halting_phi,
-				tree *evolution_of_loop)
+				tree *evolution_of_loop, int limit)
 {
   struct loop *loop = loop_containing_stmt (loop_phi_node);
   tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
@@ -1375,7 +1373,7 @@ follow_ssa_edge_inner_loop_phi (struct l
 	  if (!flow_bb_inside_loop_p (loop, bb))
 	    res = res || follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
 						 arg, halting_phi,
-						 evolution_of_loop);
+						 evolution_of_loop, limit);
 	}
 
       /* If the path crosses this loop-phi, give up.  */
@@ -1388,21 +1386,20 @@ follow_ssa_edge_inner_loop_phi (struct l
   /* Otherwise, compute the overall effect of the inner loop.  */
   ev = compute_overall_effect_of_inner_loop (loop, ev);
   return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
-				 evolution_of_loop);
+				 evolution_of_loop, limit);
 }
 
 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
    path that is analyzed on the return walk.  */
 
 static bool
-follow_ssa_edge (struct loop *loop, 
-		 tree def, 
-		 tree halting_phi,
-		 tree *evolution_of_loop)
+follow_ssa_edge (struct loop *loop, tree def, tree halting_phi,
+		 tree *evolution_of_loop, int limit)
 {
   struct loop *def_loop;
   
-  if (TREE_CODE (def) == NOP_EXPR)
+  if (limit++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)
+      || TREE_CODE (def) == NOP_EXPR)
     return false;
   
   def_loop = loop_containing_stmt (def);
@@ -1416,7 +1413,7 @@ follow_ssa_edge (struct loop *loop, 
 	   information and set the approximation to the main
 	   variable.  */
 	return follow_ssa_edge_in_condition_phi 
-	  (loop, def, halting_phi, evolution_of_loop);
+	  (loop, def, halting_phi, evolution_of_loop, limit);
 
       /* When the analyzed phi is the halting_phi, the
 	 depth-first search is over: we have found a path from
@@ -1433,7 +1430,7 @@ follow_ssa_edge (struct loop *loop, 
       /* Inner loop.  */
       if (flow_loop_nested_p (loop, def_loop))
 	return follow_ssa_edge_inner_loop_phi 
-	  (loop, def, halting_phi, evolution_of_loop);
+	  (loop, def, halting_phi, evolution_of_loop, limit);
 
       /* Outer loop.  */
       return false;
@@ -1442,7 +1439,7 @@ follow_ssa_edge (struct loop *loop, 
       return follow_ssa_edge_in_rhs (loop, def,
 				     TREE_OPERAND (def, 1), 
 				     halting_phi, 
-				     evolution_of_loop);
+				     evolution_of_loop, limit);
       
     default:
       /* At this level of abstraction, the program is just a set
@@ -1491,7 +1488,7 @@ analyze_evolution_in_loop (tree loop_phi
 
 	  /* Pass in the initial condition to the follow edge function.  */
 	  ev_fn = init_cond;
-	  res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn);
+	  res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
 	}
       else
 	res = false;


-- 


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

[cvs-commit at gcc dot gnu dot org]

------- 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:	spop@gcc.gnu.org	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

[cvs-commit at gcc dot gnu dot org]

------- 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:	spop@gcc.gnu.org	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

[pinskia at gcc dot gnu dot org]

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