X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-scalar-evolution.c;h=b13cac134c0f3e8421d51a9c793b54d406d6f667;hb=347465629f7e2933e5a091261fdcffbecf9718f9;hp=1ffeb0bd6c12233b2dc4a91f960a7fe7448d264a;hpb=15a951ca6939db302ac188180743cc64651c449d;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 1ffeb0bd6c1..b13cac134c0 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -1,5 +1,5 @@ /* Scalar evolution detector. - Copyright (C) 2003, 2004 Free Software Foundation, Inc. + Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. Contributed by Sebastian Pop This file is part of GCC. @@ -16,8 +16,8 @@ for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ /* Description: @@ -235,9 +235,9 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "system.h" #include "coretypes.h" #include "tm.h" -#include "errors.h" #include "ggc.h" #include "tree.h" +#include "real.h" /* These RTL headers are needed for basic-block.h. */ #include "rtl.h" @@ -251,6 +251,7 @@ Software Foundation, 59 Temple Place - Suite 330, 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); @@ -350,33 +351,6 @@ find_var_scev_info (tree var) return &res->chrec; } -/* Tries to express CHREC in wider type TYPE. */ - -tree -count_ev_in_wider_type (tree type, tree chrec) -{ - tree base, step; - struct loop *loop; - - if (!evolution_function_is_affine_p (chrec)) - return fold_convert (type, chrec); - - base = CHREC_LEFT (chrec); - step = CHREC_RIGHT (chrec); - loop = current_loops->parray[CHREC_VARIABLE (chrec)]; - - /* TODO -- if we knew the statement at that the conversion occurs, - we could pass it to can_count_iv_in_wider_type and get a better - result. */ - step = can_count_iv_in_wider_type (loop, type, base, step, NULL_TREE); - if (!step) - return fold_convert (type, chrec); - base = chrec_convert (type, base); - - return build_polynomial_chrec (CHREC_VARIABLE (chrec), - base, step); -} - /* Return true when CHREC contains symbolic names defined in LOOP_NB. */ @@ -703,7 +677,9 @@ add_to_evolution_1 (unsigned loop_nb, { var = loop_nb; left = chrec_before; - right = build_int_cst (type, 0); + right = SCALAR_FLOAT_TYPE_P (type) + ? build_real (type, dconst0) + : build_int_cst (type, 0); } else { @@ -894,8 +870,9 @@ add_to_evolution (unsigned loop_nb, } if (code == MINUS_EXPR) - to_add = chrec_fold_multiply (type, to_add, - build_int_cst_type (type, -1)); + to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type) + ? build_real (type, dconstm1) + : build_int_cst_type (type, -1)); res = add_to_evolution_1 (loop_nb, chrec_before, to_add); @@ -922,8 +899,9 @@ set_nb_iterations_in_loop (struct loop *loop, count of the loop in order to be compatible with the other nb_iter computations in loop-iv. This also allows the representation of nb_iters that are equal to MAX_INT. */ - if ((TREE_CODE (res) == INTEGER_CST && TREE_INT_CST_LOW (res) == 0) - || TREE_OVERFLOW (res)) + if (TREE_CODE (res) == INTEGER_CST + && (TREE_INT_CST_LOW (res) == 0 + || TREE_OVERFLOW (res))) res = chrec_dont_know; if (dump_file && (dump_flags & TDF_DETAILS)) @@ -1012,7 +990,7 @@ get_loop_exit_condition (struct loop *loop) static void get_exit_conditions_rec (struct loop *loop, - varray_type *exit_conditions) + VEC(tree,heap) **exit_conditions) { if (!loop) return; @@ -1026,7 +1004,7 @@ get_exit_conditions_rec (struct loop *loop, tree loop_condition = get_loop_exit_condition (loop); if (loop_condition) - VARRAY_PUSH_TREE (*exit_conditions, loop_condition); + VEC_safe_push (tree, heap, *exit_conditions, loop_condition); } } @@ -1035,7 +1013,7 @@ get_exit_conditions_rec (struct loop *loop, static void select_loops_exit_conditions (struct loops *loops, - varray_type *exit_conditions) + VEC(tree,heap) **exit_conditions) { struct loop *function_body = loops->parray[0]; @@ -1045,18 +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 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); @@ -1065,26 +1048,27 @@ follow_ssa_edge_in_rhs (struct loop *loop, - an INTEGER_CST, - a PLUS_EXPR, - a MINUS_EXPR, - - other cases are not yet handled. - */ + - an ASSERT_EXPR, + - other cases are not yet handled. */ switch (TREE_CODE (rhs)) { case NOP_EXPR: /* This assignment is under the form "a_1 = (cast) rhs. */ - res = follow_ssa_edge_in_rhs (loop, TREE_OPERAND (rhs, 0), halting_phi, - evolution_of_loop); - *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), *evolution_of_loop); + res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0), + 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: @@ -1102,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), + 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), + 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 @@ -1130,11 +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), + (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; } } @@ -1144,18 +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), + (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; @@ -1171,17 +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), - 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; @@ -1200,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; } } @@ -1222,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; } } @@ -1234,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; } @@ -1243,12 +1244,26 @@ 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; + case ASSERT_EXPR: + { + /* This assignment is of the form: "a_1 = ASSERT_EXPR " + It must be handled as a copy assignment of the form a_1 = a_2. */ + 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, limit); + else + res = t_false; + break; + } + + default: - res = false; + res = t_false; break; } @@ -1275,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; @@ -1289,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 @@ -1305,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++) @@ -1333,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 @@ -1353,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)); @@ -1366,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++) @@ -1377,12 +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, 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; @@ -1390,23 +1410,25 @@ 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, ev, halting_phi, - evolution_of_loop); + return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi, + 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); @@ -1419,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, + 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; } } @@ -1494,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; @@ -1644,21 +1666,21 @@ interpret_condition_phi (struct loop *loop, tree condition_phi) } /* Interpret the right hand side of a modify_expr OPND1. If we didn't - analyzed this node before, follow the definitions until ending + analyze this node before, follow the definitions until ending either on an analyzed modify_expr, or on a loop-phi-node. On the return path, this function propagates evolutions (ala constant copy propagation). OPND1 is not a GIMPLE expression because we could analyze the effect of an inner loop: see interpret_loop_phi. */ static tree -interpret_rhs_modify_expr (struct loop *loop, +interpret_rhs_modify_expr (struct loop *loop, tree at_stmt, tree opnd1, tree type) { tree res, opnd10, opnd11, chrec10, chrec11; - + if (is_gimple_min_invariant (opnd1)) - return chrec_convert (type, opnd1); - + return chrec_convert (type, opnd1, at_stmt); + switch (TREE_CODE (opnd1)) { case PLUS_EXPR: @@ -1666,8 +1688,8 @@ interpret_rhs_modify_expr (struct loop *loop, opnd11 = TREE_OPERAND (opnd1, 1); chrec10 = analyze_scalar_evolution (loop, opnd10); chrec11 = analyze_scalar_evolution (loop, opnd11); - chrec10 = chrec_convert (type, chrec10); - chrec11 = chrec_convert (type, chrec11); + chrec10 = chrec_convert (type, chrec10, at_stmt); + chrec11 = chrec_convert (type, chrec11, at_stmt); res = chrec_fold_plus (type, chrec10, chrec11); break; @@ -1676,16 +1698,18 @@ interpret_rhs_modify_expr (struct loop *loop, opnd11 = TREE_OPERAND (opnd1, 1); chrec10 = analyze_scalar_evolution (loop, opnd10); chrec11 = analyze_scalar_evolution (loop, opnd11); - chrec10 = chrec_convert (type, chrec10); - chrec11 = chrec_convert (type, chrec11); + chrec10 = chrec_convert (type, chrec10, at_stmt); + chrec11 = chrec_convert (type, chrec11, at_stmt); res = chrec_fold_minus (type, chrec10, chrec11); break; case NEGATE_EXPR: opnd10 = TREE_OPERAND (opnd1, 0); chrec10 = analyze_scalar_evolution (loop, opnd10); - chrec10 = chrec_convert (type, chrec10); - res = chrec_fold_minus (type, build_int_cst (type, 0), chrec10); + chrec10 = chrec_convert (type, chrec10, at_stmt); + res = chrec_fold_multiply (type, chrec10, SCALAR_FLOAT_TYPE_P (type) + ? build_real (type, dconstm1) + : build_int_cst_type (type, -1)); break; case MULT_EXPR: @@ -1693,20 +1717,27 @@ interpret_rhs_modify_expr (struct loop *loop, opnd11 = TREE_OPERAND (opnd1, 1); chrec10 = analyze_scalar_evolution (loop, opnd10); chrec11 = analyze_scalar_evolution (loop, opnd11); - chrec10 = chrec_convert (type, chrec10); - chrec11 = chrec_convert (type, chrec11); + chrec10 = chrec_convert (type, chrec10, at_stmt); + chrec11 = chrec_convert (type, chrec11, at_stmt); res = chrec_fold_multiply (type, chrec10, chrec11); break; case SSA_NAME: - res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1)); + res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1), + at_stmt); + break; + + case ASSERT_EXPR: + opnd10 = ASSERT_EXPR_VAR (opnd1); + res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10), + at_stmt); break; case NOP_EXPR: case CONVERT_EXPR: opnd10 = TREE_OPERAND (opnd1, 0); chrec10 = analyze_scalar_evolution (loop, opnd10); - res = chrec_convert (type, chrec10); + res = chrec_convert (type, chrec10, at_stmt); break; default: @@ -1756,7 +1787,7 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) return chrec_dont_know; if (TREE_CODE (var) != SSA_NAME) - return interpret_rhs_modify_expr (loop, var, type); + return interpret_rhs_modify_expr (loop, NULL_TREE, var, type); def = SSA_NAME_DEF_STMT (var); bb = bb_for_stmt (def); @@ -1790,7 +1821,7 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) switch (TREE_CODE (def)) { case MODIFY_EXPR: - res = interpret_rhs_modify_expr (loop, TREE_OPERAND (def, 1), type); + res = interpret_rhs_modify_expr (loop, def, TREE_OPERAND (def, 1), type); break; case PHI_NODE: @@ -1922,26 +1953,56 @@ set_instantiated_value (htab_t cache, tree version, tree val) info->chrec = val; } +/* Return the closed_loop_phi node for VAR. If there is none, return + NULL_TREE. */ + +static tree +loop_closed_phi_def (tree var) +{ + struct loop *loop; + edge exit; + tree phi; + + if (var == NULL_TREE + || TREE_CODE (var) != SSA_NAME) + return NULL_TREE; + + loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var)); + exit = loop->single_exit; + if (!exit) + return NULL_TREE; + + for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi)) + if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var) + return PHI_RESULT (phi); + + return NULL_TREE; +} + /* Analyze all the parameters of the chrec that were left under a symbolic form, - with respect to LOOP. CHREC is the chrec to instantiate. If - ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with - outer loop chrecs is done. CACHE is the cache of already instantiated - values. */ + with respect to LOOP. CHREC is the chrec to instantiate. CACHE is the cache + of already instantiated values. FLAGS modify the way chrecs are + instantiated. */ +/* Values for FLAGS. */ +enum +{ + INSERT_SUPERLOOP_CHRECS = 1, /* Loop invariants are replaced with chrecs + in outer loops. */ + FOLD_CONVERSIONS = 2 /* The conversions that may wrap in + signed/pointer type are folded, as long as the + value of the chrec is preserved. */ +}; + static tree -instantiate_parameters_1 (struct loop *loop, tree chrec, - bool allow_superloop_chrecs, - htab_t cache) +instantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t cache) { tree res, op0, op1, op2; basic_block def_bb; struct loop *def_loop; - - if (chrec == NULL_TREE - || automatically_generated_chrec_p (chrec)) - return chrec; - - if (is_gimple_min_invariant (chrec)) + + if (automatically_generated_chrec_p (chrec) + || is_gimple_min_invariant (chrec)) return chrec; switch (TREE_CODE (chrec)) @@ -1952,7 +2013,7 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, /* A parameter (or loop invariant and we do not want to include evolutions in outer loops), nothing to do. */ if (!def_bb - || (!allow_superloop_chrecs + || (!(flags & INSERT_SUPERLOOP_CHRECS) && !flow_bb_inside_loop_p (loop, def_bb))) return chrec; @@ -1990,7 +2051,25 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, result again. */ bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec)); res = analyze_scalar_evolution (def_loop, chrec); - res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs, cache); + + /* Don't instantiate loop-closed-ssa phi nodes. */ + if (TREE_CODE (res) == SSA_NAME + && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL + || (loop_containing_stmt (SSA_NAME_DEF_STMT (res))->depth + > def_loop->depth))) + { + if (res == chrec) + res = loop_closed_phi_def (chrec); + else + res = chrec; + + if (res == NULL_TREE) + res = chrec_dont_know; + } + + else if (res != chrec_dont_know) + res = instantiate_parameters_1 (loop, res, flags, cache); + bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); /* Store the correct value to the cache. */ @@ -1999,9 +2078,15 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, case POLYNOMIAL_CHREC: op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec), - allow_superloop_chrecs, cache); + flags, cache); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec), - allow_superloop_chrecs, cache); + flags, cache); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (CHREC_LEFT (chrec) != op0 || CHREC_RIGHT (chrec) != op1) chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); @@ -2009,9 +2094,15 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, case PLUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), - allow_superloop_chrecs, cache); + flags, cache); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), - allow_superloop_chrecs, cache); + flags, cache); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1); @@ -2019,9 +2110,15 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, case MINUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), - allow_superloop_chrecs, cache); + flags, cache); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), - allow_superloop_chrecs, cache); + flags, cache); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1); @@ -2029,9 +2126,15 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, case MULT_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), - allow_superloop_chrecs, cache); + flags, cache); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), - allow_superloop_chrecs, cache); + flags, cache); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1); @@ -2041,14 +2144,21 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, case CONVERT_EXPR: case NON_LVALUE_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), - allow_superloop_chrecs, cache); + flags, cache); if (op0 == chrec_dont_know) return chrec_dont_know; + if (flags & FOLD_CONVERSIONS) + { + tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0); + if (tmp) + return tmp; + } + if (op0 == TREE_OPERAND (chrec, 0)) return chrec; - return chrec_convert (TREE_TYPE (chrec), op0); + return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE); case SCEV_NOT_KNOWN: return chrec_dont_know; @@ -2064,14 +2174,18 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, { case 3: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), - allow_superloop_chrecs, cache); + flags, cache); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), - allow_superloop_chrecs, cache); + flags, cache); + if (op1 == chrec_dont_know) + return chrec_dont_know; + op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2), - allow_superloop_chrecs, cache); - if (op0 == chrec_dont_know - || op1 == chrec_dont_know - || op2 == chrec_dont_know) + flags, cache); + if (op2 == chrec_dont_know) return chrec_dont_know; if (op0 == TREE_OPERAND (chrec, 0) @@ -2079,31 +2193,33 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, && op2 == TREE_OPERAND (chrec, 2)) return chrec; - return fold (build (TREE_CODE (chrec), - TREE_TYPE (chrec), op0, op1, op2)); + return fold_build3 (TREE_CODE (chrec), + TREE_TYPE (chrec), op0, op1, op2); case 2: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), - allow_superloop_chrecs, cache); + flags, cache); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), - allow_superloop_chrecs, cache); - if (op0 == chrec_dont_know - || op1 == chrec_dont_know) + flags, cache); + if (op1 == chrec_dont_know) return chrec_dont_know; if (op0 == TREE_OPERAND (chrec, 0) && op1 == TREE_OPERAND (chrec, 1)) return chrec; - return fold (build (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1)); + return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1); case 1: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), - allow_superloop_chrecs, cache); + flags, cache); if (op0 == chrec_dont_know) return chrec_dont_know; if (op0 == TREE_OPERAND (chrec, 0)) return chrec; - return fold (build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0)); + return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0); case 0: return chrec; @@ -2136,7 +2252,7 @@ instantiate_parameters (struct loop *loop, fprintf (dump_file, ")\n"); } - res = instantiate_parameters_1 (loop, chrec, true, cache); + res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -2151,13 +2267,15 @@ instantiate_parameters (struct loop *loop, } /* Similar to instantiate_parameters, but does not introduce the - evolutions in outer loops for LOOP invariants in CHREC. */ + evolutions in outer loops for LOOP invariants in CHREC, and does not + care about causing overflows, as long as they do not affect value + of an expression. */ static tree resolve_mixers (struct loop *loop, tree chrec) { htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); - tree ret = instantiate_parameters_1 (loop, chrec, false, cache); + tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache); htab_delete (cache); return ret; } @@ -2203,7 +2321,7 @@ number_of_iterations_in_loop (struct loop *loop) if (!exit) goto end; - if (!number_of_iterations_exit (loop, exit, &niter_desc)) + if (!number_of_iterations_exit (loop, exit, &niter_desc, false)) goto end; type = TREE_TYPE (niter_desc.niter); @@ -2223,16 +2341,16 @@ end: from the EXIT_CONDITIONS array. */ static void -number_of_iterations_for_all_loops (varray_type exit_conditions) +number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions) { unsigned int i; unsigned nb_chrec_dont_know_loops = 0; unsigned nb_static_loops = 0; + tree cond; - for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++) + for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++) { - tree res = number_of_iterations_in_loop - (loop_containing_stmt (VARRAY_TREE (exit_conditions, i))); + tree res = number_of_iterations_in_loop (loop_containing_stmt (cond)); if (chrec_contains_undetermined (res)) nb_chrec_dont_know_loops++; else @@ -2375,20 +2493,21 @@ gather_chrec_stats (tree chrec, struct chrec_stats *stats) index. This allows the parallelization of the loop. */ static void -analyze_scalar_evolution_for_all_loop_phi_nodes (varray_type exit_conditions) +analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions) { unsigned int i; struct chrec_stats stats; + tree cond; reset_chrecs_counters (&stats); - for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++) + for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++) { struct loop *loop; basic_block bb; tree phi, chrec; - loop = loop_containing_stmt (VARRAY_TREE (exit_conditions, i)); + loop = loop_containing_stmt (cond); bb = loop->header; for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) @@ -2451,8 +2570,8 @@ initialize_scalar_evolutions_analyzer (void) chrec_not_analyzed_yet = NULL_TREE; chrec_dont_know = make_node (SCEV_NOT_KNOWN); chrec_known = make_node (SCEV_KNOWN); - TREE_TYPE (chrec_dont_know) = NULL_TREE; - TREE_TYPE (chrec_known) = NULL_TREE; + TREE_TYPE (chrec_dont_know) = void_type_node; + TREE_TYPE (chrec_known) = void_type_node; } } @@ -2466,7 +2585,7 @@ scev_initialize (struct loops *loops) scalar_evolution_info = htab_create (100, hash_scev_info, eq_scev_info, del_scev_info); - already_instantiated = BITMAP_XMALLOC (); + already_instantiated = BITMAP_ALLOC (NULL); initialize_scalar_evolutions_analyzer (); @@ -2496,10 +2615,13 @@ scev_reset (void) } /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns - its BASE and STEP if possible. */ + its BASE and STEP if possible. If ALLOW_NONCONSTANT_STEP is true, we + want STEP to be invariant in LOOP. Otherwise we require it to be an + integer constant. */ bool -simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step) +simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step, + bool allow_nonconstant_step) { basic_block bb = bb_for_stmt (stmt); tree type, ev; @@ -2528,10 +2650,17 @@ simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step) return false; *step = CHREC_RIGHT (ev); - if (TREE_CODE (*step) != INTEGER_CST) + if (allow_nonconstant_step) + { + if (tree_contains_chrecs (*step, NULL) + || chrec_contains_symbols_defined_in_loop (*step, loop->num)) + return false; + } + else if (TREE_CODE (*step) != INTEGER_CST) return false; + *base = CHREC_LEFT (ev); - if (tree_contains_chrecs (*base) + if (tree_contains_chrecs (*base, NULL) || chrec_contains_symbols_defined_in_loop (*base, loop->num)) return false; @@ -2543,16 +2672,16 @@ simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step) void scev_analysis (void) { - varray_type exit_conditions; + VEC(tree,heap) *exit_conditions; - VARRAY_GENERIC_PTR_INIT (exit_conditions, 37, "exit_conditions"); + exit_conditions = VEC_alloc (tree, heap, 37); select_loops_exit_conditions (current_loops, &exit_conditions); if (dump_file && (dump_flags & TDF_STATS)) - analyze_scalar_evolution_for_all_loop_phi_nodes (exit_conditions); + analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions); - number_of_iterations_for_all_loops (exit_conditions); - VARRAY_CLEAR (exit_conditions); + number_of_iterations_for_all_loops (&exit_conditions); + VEC_free (tree, heap, exit_conditions); } /* Finalize the scalar evolution analysis. */ @@ -2561,6 +2690,136 @@ void scev_finalize (void) { htab_delete (scalar_evolution_info); - BITMAP_XFREE (already_instantiated); + BITMAP_FREE (already_instantiated); } +/* Replace ssa names for that scev can prove they are constant by the + appropriate constants. Also perform final value replacement in loops, + in case the replacement expressions are cheap. + + We only consider SSA names defined by phi nodes; rest is left to the + ordinary constant propagation pass. */ + +void +scev_const_prop (void) +{ + basic_block bb; + tree name, phi, next_phi, type, ev; + struct loop *loop, *ex_loop; + bitmap ssa_names_to_remove = NULL; + unsigned i; + + if (!current_loops) + return; + + FOR_EACH_BB (bb) + { + loop = bb->loop_father; + + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + { + name = PHI_RESULT (phi); + + if (!is_gimple_reg (name)) + continue; + + type = TREE_TYPE (name); + + if (!POINTER_TYPE_P (type) + && !INTEGRAL_TYPE_P (type)) + continue; + + ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name)); + if (!is_gimple_min_invariant (ev) + || !may_propagate_copy (name, ev)) + continue; + + /* Replace the uses of the name. */ + if (name != ev) + replace_uses_by (name, ev); + + if (!ssa_names_to_remove) + ssa_names_to_remove = BITMAP_ALLOC (NULL); + bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name)); + } + } + + /* Remove the ssa names that were replaced by constants. We do not remove them + directly in the previous cycle, since this invalidates scev cache. */ + if (ssa_names_to_remove) + { + bitmap_iterator bi; + unsigned i; + + EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi) + { + name = ssa_name (i); + phi = SSA_NAME_DEF_STMT (name); + + gcc_assert (TREE_CODE (phi) == PHI_NODE); + remove_phi_node (phi, NULL); + } + + BITMAP_FREE (ssa_names_to_remove); + scev_reset (); + } + + /* Now the regular final value replacement. */ + for (i = current_loops->num - 1; i > 0; i--) + { + edge exit; + tree def, stmts; + + loop = current_loops->parray[i]; + if (!loop) + continue; + + /* If we do not know exact number of iterations of the loop, we cannot + replace the final value. */ + exit = loop->single_exit; + if (!exit + || number_of_iterations_in_loop (loop) == chrec_dont_know) + continue; + ex_loop = exit->dest->loop_father; + + for (phi = phi_nodes (exit->dest); phi; phi = next_phi) + { + next_phi = PHI_CHAIN (phi); + def = PHI_ARG_DEF_FROM_EDGE (phi, exit); + if (!is_gimple_reg (def) + || expr_invariant_in_loop_p (loop, def)) + continue; + + if (!POINTER_TYPE_P (TREE_TYPE (def)) + && !INTEGRAL_TYPE_P (TREE_TYPE (def))) + continue; + + def = analyze_scalar_evolution_in_loop (ex_loop, ex_loop, def); + if (!tree_does_not_contain_chrecs (def) + || chrec_contains_symbols_defined_in_loop (def, loop->num) + || def == PHI_RESULT (phi) + || (TREE_CODE (def) == SSA_NAME + && loop_containing_stmt (SSA_NAME_DEF_STMT (def)) + && loop_containing_stmt (phi) + && loop_containing_stmt (SSA_NAME_DEF_STMT (def)) + == loop_containing_stmt (phi))) + continue; + + /* If computing the expression is expensive, let it remain in + loop. TODO -- we should take the cost of computing the expression + in loop into account. */ + if (force_expr_to_var_cost (def) >= target_spill_cost) + continue; + def = unshare_expr (def); + + if (is_gimple_val (def)) + stmts = NULL_TREE; + else + def = force_gimple_operand (def, &stmts, true, + SSA_NAME_VAR (PHI_RESULT (phi))); + SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, exit), def); + if (stmts) + compute_phi_arg_on_exit (exit, stmts, def); + } + } +}