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

Reply via email to