From d1de0ec2f6c424f50791fde5fb338a168d32a633 Mon Sep 17 00:00:00 2001 From: spop Date: Mon, 26 Sep 2005 18:44:16 +0000 Subject: [PATCH] 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. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@104653 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 15 ++++ gcc/Makefile.in | 2 +- gcc/tree-scalar-evolution.c | 187 +++++++++++++++++++++++++------------------- 3 files changed, 122 insertions(+), 82 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 2d94072..8499938 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,18 @@ +2005-09-26 Sebastian Pop + + 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. + 2005-09-26 Uros Bizjak PR middle-end/23831 diff --git a/gcc/Makefile.in b/gcc/Makefile.in index fded53d..33056ee 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -767,7 +767,7 @@ TREE_SSA_LIVE_H = tree-ssa-live.h $(PARTITION_H) 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) diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 82f814e..b13cac1 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -251,6 +251,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #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,19 +1023,23 @@ select_loops_exit_conditions (struct loops *loops, /* Depth first search algorithm. */ -static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *); +typedef enum t_bool { + t_false, + t_true, + t_dont_know +} t_bool; + + +static t_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) +static t_bool +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; + t_bool res = t_false; tree rhs0, rhs1; tree type_rhs = TREE_TYPE (rhs); @@ -1050,20 +1055,20 @@ follow_ssa_edge_in_rhs (struct loop *loop, 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; case INTEGER_CST: /* This assignment is under the form "a_1 = 7". */ - res = false; + res = t_false; break; 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,26 +1086,32 @@ follow_ssa_edge_in_rhs (struct loop *loop, "a = b + c". */ res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, - evolution_of_loop); + evolution_of_loop, limit); - if (res) + if (res == t_true) *evolution_of_loop = add_to_evolution (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt), PLUS_EXPR, rhs1); - else + else if (res == t_false) { res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, - evolution_of_loop); + evolution_of_loop, limit); - if (res) + if (res == t_true) *evolution_of_loop = add_to_evolution (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt), PLUS_EXPR, rhs0); + + else if (res == t_dont_know) + *evolution_of_loop = chrec_dont_know; } + + else if (res == t_dont_know) + *evolution_of_loop = chrec_dont_know; } else @@ -1109,12 +1120,15 @@ follow_ssa_edge_in_rhs (struct loop *loop, "a = b + ...". */ res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, - evolution_of_loop); - if (res) + evolution_of_loop, limit); + if (res == t_true) *evolution_of_loop = add_to_evolution (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt), PLUS_EXPR, rhs1); + + else if (res == t_dont_know) + *evolution_of_loop = chrec_dont_know; } } @@ -1124,19 +1138,22 @@ follow_ssa_edge_in_rhs (struct loop *loop, "a = ... + c". */ res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, - evolution_of_loop); - if (res) + evolution_of_loop, limit); + if (res == t_true) *evolution_of_loop = add_to_evolution (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt), PLUS_EXPR, rhs0); + + else if (res == t_dont_know) + *evolution_of_loop = chrec_dont_know; } else /* Otherwise, match an assignment under the form: "a = ... + ...". */ /* And there is nothing to do. */ - res = false; + res = t_false; break; @@ -1152,18 +1169,20 @@ follow_ssa_edge_in_rhs (struct loop *loop, /* Match an assignment under the form: "a = b - ...". */ res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, - evolution_of_loop); - if (res) + evolution_of_loop, limit); + if (res == t_true) *evolution_of_loop = add_to_evolution - (loop->num, chrec_convert (type_rhs, *evolution_of_loop, - at_stmt), - MINUS_EXPR, rhs1); + (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt), + MINUS_EXPR, rhs1); + + else if (res == t_dont_know) + *evolution_of_loop = chrec_dont_know; } else /* Otherwise, match an assignment under the form: "a = ... - ...". */ /* And there is nothing to do. */ - res = false; + res = t_false; break; @@ -1182,18 +1201,18 @@ follow_ssa_edge_in_rhs (struct loop *loop, "a = b * c". */ res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, - evolution_of_loop); + evolution_of_loop, limit); - if (res) + if (res == t_true || res == t_dont_know) *evolution_of_loop = chrec_dont_know; - else + else if (res == t_false) { res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, - evolution_of_loop); + evolution_of_loop, limit); - if (res) + if (res == t_true || res == t_dont_know) *evolution_of_loop = chrec_dont_know; } } @@ -1204,8 +1223,8 @@ follow_ssa_edge_in_rhs (struct loop *loop, "a = b * ...". */ res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, - evolution_of_loop); - if (res) + evolution_of_loop, limit); + if (res == t_true || res == t_dont_know) *evolution_of_loop = chrec_dont_know; } } @@ -1216,8 +1235,8 @@ follow_ssa_edge_in_rhs (struct loop *loop, "a = ... * c". */ res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, - evolution_of_loop); - if (res) + evolution_of_loop, limit); + if (res == t_true || res == t_dont_know) *evolution_of_loop = chrec_dont_know; } @@ -1225,7 +1244,7 @@ follow_ssa_edge_in_rhs (struct loop *loop, /* Otherwise, match an assignment under the form: "a = ... * ...". */ /* And there is nothing to do. */ - res = false; + res = t_false; break; @@ -1236,15 +1255,15 @@ follow_ssa_edge_in_rhs (struct loop *loop, 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; + res = t_false; break; } default: - res = false; + res = t_false; break; } @@ -1271,13 +1290,13 @@ backedge_phi_arg_p (tree phi, int i) true if the strongly connected component has been found following this path. */ -static inline bool +static inline t_bool follow_ssa_edge_in_condition_phi_branch (int i, struct loop *loop, 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; @@ -1285,13 +1304,13 @@ follow_ssa_edge_in_condition_phi_branch (int i, /* Do not follow back edges (they must belong to an irreducible loop, which we really do not want to worry about). */ if (backedge_phi_arg_p (condition_phi, i)) - return false; + return t_false; if (TREE_CODE (branch) == SSA_NAME) { *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 @@ -1301,27 +1320,28 @@ follow_ssa_edge_in_condition_phi_branch (int i, FIXME: This case have to be refined correctly: in some cases it is possible to say something better than chrec_dont_know, for example using a wrap-around notation. */ - return false; + return t_false; } /* This function merges the branches of a condition-phi-node in a loop. */ -static bool +static t_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; tree evolution_of_branch; + t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi, + halting_phi, + &evolution_of_branch, + init, limit); + if (res == t_false || res == t_dont_know) + return res; - if (!follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi, - halting_phi, - &evolution_of_branch, - init)) - return false; *evolution_of_loop = evolution_of_branch; for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++) @@ -1329,19 +1349,20 @@ follow_ssa_edge_in_condition_phi (struct loop *loop, /* Quickly give up when the evolution of one of the branches is not known. */ if (*evolution_of_loop == chrec_dont_know) - return true; + return t_true; - if (!follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi, - halting_phi, - &evolution_of_branch, - init)) - return false; + res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi, + halting_phi, + &evolution_of_branch, + init, limit); + if (res == t_false || res == t_dont_know) + return res; *evolution_of_loop = chrec_merge (*evolution_of_loop, evolution_of_branch); } - return true; + return t_true; } /* Follow an SSA edge in an inner loop. It computes the overall @@ -1349,11 +1370,11 @@ follow_ssa_edge_in_condition_phi (struct loop *loop, it follows the edges in the parent loop. The inner loop is considered as a single statement. */ -static bool +static t_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)); @@ -1362,7 +1383,7 @@ follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, result of the analysis is a symbolic parameter. */ if (ev == PHI_RESULT (loop_phi_node)) { - bool res = false; + t_bool res = t_false; int i; for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++) @@ -1373,13 +1394,15 @@ follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, /* Follow the edges that exit the inner loop. */ bb = PHI_ARG_EDGE (loop_phi_node, i)->src; 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); + res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, + arg, halting_phi, + evolution_of_loop, limit); + if (res == t_true) + break; } /* If the path crosses this loop-phi, give up. */ - if (res == true) + if (res == t_true) *evolution_of_loop = chrec_dont_know; return res; @@ -1388,22 +1411,24 @@ follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, /* 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) +static t_bool +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) - return false; + return t_false; + + /* Give up if the path is longer than the MAX that we allow. */ + if (limit++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) + return t_dont_know; def_loop = loop_containing_stmt (def); @@ -1416,39 +1441,39 @@ 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 the halting_phi to itself in the loop. */ if (def == halting_phi) - return true; + return t_true; /* Otherwise, the evolution of the HALTING_PHI depends on the evolution of another loop-phi-node, i.e. the evolution function is a higher degree polynomial. */ if (def_loop == loop) - return false; + return t_false; /* 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; + return t_false; case MODIFY_EXPR: 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 of MODIFY_EXPRs and PHI_NODEs. In principle there is no other node to be handled. */ - return false; + return t_false; } } @@ -1491,7 +1516,7 @@ analyze_evolution_in_loop (tree loop_phi_node, /* 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; -- 2.7.4