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