From 524bc988650339de8fd137ac20c74423e7d7e1bb Mon Sep 17 00:00:00 2001 From: spop Date: Fri, 31 Jul 2009 02:28:50 +0000 Subject: 2009-07-30 Sebastian Pop * tree-scalar-evolution.c (compute_overall_effect_of_inner_loop): Not static anymore. Instantiate the symbols that may have been introduced by chrec_apply. * tree-scalar-evolution.h (compute_overall_effect_of_inner_loop): Declared. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@150289 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index bac6e594d8f..e817ffe64c3 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -466,7 +466,7 @@ loop_phi_node_p (gimple phi) EVOLUTION_FN = {i_0, +, 2}_1. */ -static tree +tree compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) { bool val = false; @@ -492,7 +492,10 @@ compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) /* evolution_fn is the evolution function in LOOP. Get its value in the nb_iter-th iteration. */ res = chrec_apply (inner_loop->num, evolution_fn, nb_iter); - + + if (chrec_contains_symbols_defined_in_loop (res, loop->num)) + res = instantiate_parameters (loop, res); + /* Continue the computation until ending on a parent of LOOP. */ return compute_overall_effect_of_inner_loop (loop, res); } -- cgit v1.2.1 From 8b7d09b4add9aa2ede6e915a029b523a5ab94529 Mon Sep 17 00:00:00 2001 From: spop Date: Fri, 31 Jul 2009 02:30:03 +0000 Subject: Return unknow from scev instantiation if the result is not above instantiate_below. 2009-07-30 Sebastian Pop * tree-scalar-evolution.c: Fix comment. (instantiate_scev_1): Return unknow from scev instantiation if the result is not above instantiate_below. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@150290 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index e817ffe64c3..02a4eed646e 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -1893,18 +1893,16 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) return res; } -/* Entry point for the scalar evolution analyzer. - Analyzes and returns the scalar evolution of the ssa_name VAR. - LOOP_NB is the identifier number of the loop in which the variable - is used. +/* Analyzes and returns the scalar evolution of the ssa_name VAR in + LOOP. LOOP is the loop in which the variable is used. Example of use: having a pointer VAR to a SSA_NAME node, STMT a pointer to the statement that uses this variable, in order to determine the evolution function of the variable, use the following calls: - unsigned loop_nb = loop_containing_stmt (stmt)->num; - tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var); + loop_p loop = loop_containing_stmt (stmt); + tree chrec_with_symbols = analyze_scalar_evolution (loop, var); tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols); */ @@ -2177,7 +2175,9 @@ instantiate_scev_1 (basic_block instantiate_below, else res = chrec; - if (res == NULL_TREE) + if (res == NULL_TREE + || !dominated_by_p (CDI_DOMINATORS, instantiate_below, + gimple_bb (SSA_NAME_DEF_STMT (res)))) res = chrec_dont_know; } -- cgit v1.2.1 From 8da11536673aba7617a056943f17b857808c32de Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 21 Oct 2009 23:05:39 +0000 Subject: PR tree-optimization/41497 * tree-scalar-evolution.c (analyze_evolution_in_loop): Return chrec_dont_know if the evolution function returned by follow_ssa_edge is constant in the analyzed loop and is not compatible with the initial value before the loop. * tree-chrec.h (no_evolution_in_loop_p): Call STRIP_NOPS. * gcc.dg/tree-ssa/pr41497.c: New. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@153441 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 15 +++++++++++++-- 1 file changed, 13 insertions(+), 2 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 02a4eed646e..70af0fda610 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -1492,18 +1492,29 @@ analyze_evolution_in_loop (gimple loop_phi_node, bb = gimple_phi_arg_edge (loop_phi_node, i)->src; if (!flow_bb_inside_loop_p (loop, bb)) continue; - + if (TREE_CODE (arg) == SSA_NAME) { + bool val = false; + ssa_chain = SSA_NAME_DEF_STMT (arg); /* 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, 0); + + /* If ev_fn has no evolution in the inner loop, and the + init_cond is not equal to ev_fn, then we have an + ambiguity between two possible values, as we cannot know + the number of iterations at this point. */ + if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC + && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val + && !operand_equal_p (init_cond, ev_fn, 0)) + ev_fn = chrec_dont_know; } else res = t_false; - + /* When it is impossible to go back on the same loop_phi_node by following the ssa edges, the evolution is represented by a peeled chrec, i.e. the -- cgit v1.2.1 From 0731d86936901cecedd4c2e879cfac3405b0e66e Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 25 Nov 2009 04:28:15 +0000 Subject: 2009-09-01 Sebastian Pop * tree-scalar-evolution.c (instantiate_scev_name): New. (instantiate_scev_1): Move code in instantiate_scev_name. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154532 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 143 ++++++++++++++++++++++++++------------------ 1 file changed, 85 insertions(+), 58 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 70af0fda610..8214c4aa237 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -2109,6 +2109,88 @@ loop_closed_phi_def (tree var) return NULL_TREE; } +static tree instantiate_scev_1 (basic_block, struct loop *, tree, bool, + htab_t, int); + +/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW + and EVOLUTION_LOOP, that were left under a symbolic form. + + CHREC is an SSA_NAME to be instantiated. + + CACHE is the cache of already instantiated values. + + FOLD_CONVERSIONS should be set to true when the conversions that + may wrap in signed/pointer type are folded, as long as the value of + the chrec is preserved. + + SIZE_EXPR is used for computing the size of the expression to be + instantiated, and to stop if it exceeds some limit. */ + +static tree +instantiate_scev_name (basic_block instantiate_below, + struct loop *evolution_loop, tree chrec, + bool fold_conversions, htab_t cache, int size_expr) +{ + tree res; + struct loop *def_loop; + basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec)); + + /* A parameter (or loop invariant and we do not want to include + evolutions in outer loops), nothing to do. */ + if (!def_bb + || loop_depth (def_bb->loop_father) == 0 + || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb)) + return chrec; + + /* We cache the value of instantiated variable to avoid exponential + time complexity due to reevaluations. We also store the convenient + value in the cache in order to prevent infinite recursion -- we do + not want to instantiate the SSA_NAME if it is in a mixer + structure. This is used for avoiding the instantiation of + recursively defined functions, such as: + + | a_2 -> {0, +, 1, +, a_2}_1 */ + + res = get_instantiated_value (cache, instantiate_below, chrec); + if (res) + return res; + + res = chrec_dont_know; + set_instantiated_value (cache, instantiate_below, chrec, res); + + def_loop = find_common_loop (evolution_loop, def_bb->loop_father); + + /* If the analysis yields a parametric chrec, instantiate the + result again. */ + res = analyze_scalar_evolution (def_loop, chrec); + + /* Don't instantiate loop-closed-ssa phi nodes. */ + if (TREE_CODE (res) == SSA_NAME + && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL + || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res))) + > loop_depth (def_loop)))) + { + if (res == chrec) + res = loop_closed_phi_def (chrec); + else + res = chrec; + + if (res == NULL_TREE + || !dominated_by_p (CDI_DOMINATORS, instantiate_below, + gimple_bb (SSA_NAME_DEF_STMT (res)))) + res = chrec_dont_know; + } + + else if (res != chrec_dont_know) + res = instantiate_scev_1 (instantiate_below, evolution_loop, res, + fold_conversions, cache, size_expr); + + /* Store the correct value to the cache. */ + set_instantiated_value (cache, instantiate_below, chrec, res); + return res; + +} + /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. @@ -2128,9 +2210,7 @@ instantiate_scev_1 (basic_block instantiate_below, struct loop *evolution_loop, tree chrec, bool fold_conversions, htab_t cache, int size_expr) { - tree res, op0, op1, op2; - basic_block def_bb; - struct loop *def_loop; + tree op0, op1, op2; tree type = chrec_type (chrec); /* Give up if the expression is larger than the MAX that we allow. */ @@ -2144,61 +2224,8 @@ instantiate_scev_1 (basic_block instantiate_below, switch (TREE_CODE (chrec)) { case SSA_NAME: - def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec)); - - /* A parameter (or loop invariant and we do not want to include - evolutions in outer loops), nothing to do. */ - if (!def_bb - || loop_depth (def_bb->loop_father) == 0 - || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb)) - return chrec; - - /* We cache the value of instantiated variable to avoid exponential - time complexity due to reevaluations. We also store the convenient - value in the cache in order to prevent infinite recursion -- we do - not want to instantiate the SSA_NAME if it is in a mixer - structure. This is used for avoiding the instantiation of - recursively defined functions, such as: - - | a_2 -> {0, +, 1, +, a_2}_1 */ - - res = get_instantiated_value (cache, instantiate_below, chrec); - if (res) - return res; - - res = chrec_dont_know; - set_instantiated_value (cache, instantiate_below, chrec, res); - - def_loop = find_common_loop (evolution_loop, def_bb->loop_father); - - /* If the analysis yields a parametric chrec, instantiate the - result again. */ - res = analyze_scalar_evolution (def_loop, chrec); - - /* Don't instantiate loop-closed-ssa phi nodes. */ - if (TREE_CODE (res) == SSA_NAME - && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL - || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res))) - > loop_depth (def_loop)))) - { - if (res == chrec) - res = loop_closed_phi_def (chrec); - else - res = chrec; - - if (res == NULL_TREE - || !dominated_by_p (CDI_DOMINATORS, instantiate_below, - gimple_bb (SSA_NAME_DEF_STMT (res)))) - res = chrec_dont_know; - } - - else if (res != chrec_dont_know) - res = instantiate_scev_1 (instantiate_below, evolution_loop, res, - fold_conversions, cache, size_expr); - - /* Store the correct value to the cache. */ - set_instantiated_value (cache, instantiate_below, chrec, res); - return res; + return instantiate_scev_name (instantiate_below, evolution_loop, chrec, + fold_conversions, cache, size_expr); case POLYNOMIAL_CHREC: op0 = instantiate_scev_1 (instantiate_below, evolution_loop, -- cgit v1.2.1 From 5a10dfbafec838c5ea351b49614a12b486a69503 Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 25 Nov 2009 04:28:44 +0000 Subject: 2009-09-01 Sebastian Pop * tree-scalar-evolution.c (instantiate_scev_binary): New. (instantiate_scev_1): Move code in instantiate_scev_binary. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154533 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 126 ++++++++++++++++++++++---------------------- 1 file changed, 63 insertions(+), 63 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 8214c4aa237..219ef5cd1b7 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -2191,6 +2191,66 @@ instantiate_scev_name (basic_block instantiate_below, } +/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW + and EVOLUTION_LOOP, that were left under a symbolic form. + + CHREC is a binary expression to be instantiated. + + CACHE is the cache of already instantiated values. + + FOLD_CONVERSIONS should be set to true when the conversions that + may wrap in signed/pointer type are folded, as long as the value of + the chrec is preserved. + + SIZE_EXPR is used for computing the size of the expression to be + instantiated, and to stop if it exceeds some limit. */ + +static tree +instantiate_scev_binary (basic_block instantiate_below, + struct loop *evolution_loop, tree chrec, + bool fold_conversions, htab_t cache, int size_expr) +{ + tree op1; + tree op0 = instantiate_scev_1 (instantiate_below, evolution_loop, + TREE_OPERAND (chrec, 0), fold_conversions, cache, + size_expr); + if (op0 == chrec_dont_know) + return chrec_dont_know; + + op1 = instantiate_scev_1 (instantiate_below, evolution_loop, + TREE_OPERAND (chrec, 1), fold_conversions, cache, + size_expr); + if (op1 == chrec_dont_know) + return chrec_dont_know; + + if (TREE_OPERAND (chrec, 0) != op0 + || TREE_OPERAND (chrec, 1) != op1) + { + tree type = chrec_type (chrec); + + op0 = chrec_convert (type, op0, NULL); + op1 = chrec_convert_rhs (type, op1, NULL); + + switch (TREE_CODE (chrec)) + { + case POINTER_PLUS_EXPR: + case PLUS_EXPR: + return chrec_fold_plus (type, op0, op1); + + case MINUS_EXPR: + return chrec_fold_minus (type, op0, op1); + + case MULT_EXPR: + return chrec_fold_multiply (type, op0, op1); + + default: + gcc_unreachable (); + } + } + + return chrec; +} + /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. @@ -2250,70 +2310,10 @@ instantiate_scev_1 (basic_block instantiate_below, case POINTER_PLUS_EXPR: case PLUS_EXPR: - op0 = instantiate_scev_1 (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 0), fold_conversions, cache, - size_expr); - if (op0 == chrec_dont_know) - return chrec_dont_know; - - op1 = instantiate_scev_1 (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 1), fold_conversions, cache, - size_expr); - if (op1 == chrec_dont_know) - return chrec_dont_know; - - if (TREE_OPERAND (chrec, 0) != op0 - || TREE_OPERAND (chrec, 1) != op1) - { - op0 = chrec_convert (type, op0, NULL); - op1 = chrec_convert_rhs (type, op1, NULL); - chrec = chrec_fold_plus (type, op0, op1); - } - return chrec; - case MINUS_EXPR: - op0 = instantiate_scev_1 (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 0), fold_conversions, cache, - size_expr); - if (op0 == chrec_dont_know) - return chrec_dont_know; - - op1 = instantiate_scev_1 (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 1), - fold_conversions, cache, size_expr); - if (op1 == chrec_dont_know) - return chrec_dont_know; - - if (TREE_OPERAND (chrec, 0) != op0 - || TREE_OPERAND (chrec, 1) != op1) - { - op0 = chrec_convert (type, op0, NULL); - op1 = chrec_convert (type, op1, NULL); - chrec = chrec_fold_minus (type, op0, op1); - } - return chrec; - case MULT_EXPR: - op0 = instantiate_scev_1 (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 0), - fold_conversions, cache, size_expr); - if (op0 == chrec_dont_know) - return chrec_dont_know; - - op1 = instantiate_scev_1 (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 1), - fold_conversions, cache, size_expr); - if (op1 == chrec_dont_know) - return chrec_dont_know; - - if (TREE_OPERAND (chrec, 0) != op0 - || TREE_OPERAND (chrec, 1) != op1) - { - op0 = chrec_convert (type, op0, NULL); - op1 = chrec_convert (type, op1, NULL); - chrec = chrec_fold_multiply (type, op0, op1); - } - return chrec; + return instantiate_scev_binary (instantiate_below, evolution_loop, chrec, + fold_conversions, cache, size_expr); CASE_CONVERT: op0 = instantiate_scev_1 (instantiate_below, evolution_loop, @@ -2363,7 +2363,7 @@ instantiate_scev_1 (basic_block instantiate_below, case SCEV_KNOWN: return chrec_known; - + default: break; } -- cgit v1.2.1 From 7723692aa4b28d48c3b8f0bac2a5c8d0fbafc0a4 Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 25 Nov 2009 04:29:12 +0000 Subject: 2009-09-01 Sebastian Pop * tree-scalar-evolution.c (instantiate_scev_convert): New. (instantiate_scev_1): Move code in instantiate_scev_convert. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154534 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 76 ++++++++++++++++++++++++++++++--------------- 1 file changed, 51 insertions(+), 25 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 219ef5cd1b7..3a50f1e499d 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -2252,7 +2252,53 @@ instantiate_scev_binary (basic_block instantiate_below, } /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW - and EVOLUTION_LOOP, that were left under a symbolic form. + and EVOLUTION_LOOP, that were left under a symbolic form. + + "CHREC" that stands for a convert expression "(TYPE) OP" is to be + instantiated. + + CACHE is the cache of already instantiated values. + + FOLD_CONVERSIONS should be set to true when the conversions that + may wrap in signed/pointer type are folded, as long as the value of + the chrec is preserved. + + SIZE_EXPR is used for computing the size of the expression to be + instantiated, and to stop if it exceeds some limit. */ + +static tree +instantiate_scev_convert (basic_block instantiate_below, + struct loop *evolution_loop, tree chrec, + tree type, tree op, + bool fold_conversions, htab_t cache, int size_expr) +{ + tree op0 = instantiate_scev_1 (instantiate_below, evolution_loop, op, + fold_conversions, cache, size_expr); + + if (op0 == chrec_dont_know) + return chrec_dont_know; + + if (fold_conversions) + { + tree tmp = chrec_convert_aggressive (type, op0); + if (tmp) + return tmp; + } + + if (chrec && op0 == op) + return chrec; + + /* If we used chrec_convert_aggressive, we can no longer assume that + signed chrecs do not overflow, as chrec_convert does, so avoid + calling it in that case. */ + if (fold_conversions) + return fold_convert (type, op0); + + return chrec_convert (type, op0, NULL); +} + +/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW + and EVOLUTION_LOOP, that were left under a symbolic form. CHREC is the scalar evolution to instantiate. @@ -2264,7 +2310,7 @@ instantiate_scev_binary (basic_block instantiate_below, SIZE_EXPR is used for computing the size of the expression to be instantiated, and to stop if it exceeds some limit. */ - + static tree instantiate_scev_1 (basic_block instantiate_below, struct loop *evolution_loop, tree chrec, @@ -2316,29 +2362,9 @@ instantiate_scev_1 (basic_block instantiate_below, fold_conversions, cache, size_expr); CASE_CONVERT: - op0 = instantiate_scev_1 (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 0), - fold_conversions, cache, size_expr); - if (op0 == chrec_dont_know) - return chrec_dont_know; - - if (fold_conversions) - { - tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0); - if (tmp) - return tmp; - } - - if (op0 == TREE_OPERAND (chrec, 0)) - return chrec; - - /* If we used chrec_convert_aggressive, we can no longer assume that - signed chrecs do not overflow, as chrec_convert does, so avoid - calling it in that case. */ - if (fold_conversions) - return fold_convert (TREE_TYPE (chrec), op0); - - return chrec_convert (TREE_TYPE (chrec), op0, NULL); + return instantiate_scev_convert (instantiate_below, evolution_loop, chrec, + TREE_TYPE (chrec), TREE_OPERAND (chrec, 0), + fold_conversions, cache, size_expr); case BIT_NOT_EXPR: /* Handle ~X as -1 - X. */ -- cgit v1.2.1 From 39251a91ba8ab1630133682e6d17a8d192ea4674 Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 25 Nov 2009 04:29:43 +0000 Subject: 2009-09-01 Sebastian Pop * tree-scalar-evolution.c (instantiate_scev_bitnot): New. (instantiate_scev_1): Move code in instantiate_scev_bitnot. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154535 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 59 +++++++++++++++++++++++++++++++-------------- 1 file changed, 41 insertions(+), 18 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 3a50f1e499d..6d8bf26c64c 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -2297,6 +2297,44 @@ instantiate_scev_convert (basic_block instantiate_below, return chrec_convert (type, op0, NULL); } +/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW + and EVOLUTION_LOOP, that were left under a symbolic form. + + CHREC is a BIT_NOT_EXPR expression to be instantiated. + Handle ~X as -1 - X. + + CACHE is the cache of already instantiated values. + + FOLD_CONVERSIONS should be set to true when the conversions that + may wrap in signed/pointer type are folded, as long as the value of + the chrec is preserved. + + SIZE_EXPR is used for computing the size of the expression to be + instantiated, and to stop if it exceeds some limit. */ + +static tree +instantiate_scev_bitnot (basic_block instantiate_below, + struct loop *evolution_loop, tree chrec, + bool fold_conversions, htab_t cache, int size_expr) +{ + tree type = chrec_type (chrec); + tree op0 = instantiate_scev_1 (instantiate_below, evolution_loop, + TREE_OPERAND (chrec, 0), + fold_conversions, cache, size_expr); + if (op0 == chrec_dont_know) + return chrec_dont_know; + + if (TREE_OPERAND (chrec, 0) != op0) + { + op0 = chrec_convert (type, op0, NULL); + chrec = chrec_fold_minus (type, + fold_convert (type, + integer_minus_one_node), + op0); + } + return chrec; +} + /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. @@ -2317,7 +2355,6 @@ instantiate_scev_1 (basic_block instantiate_below, bool fold_conversions, htab_t cache, int size_expr) { tree op0, op1, op2; - tree type = chrec_type (chrec); /* Give up if the expression is larger than the MAX that we allow. */ if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) @@ -2367,22 +2404,8 @@ instantiate_scev_1 (basic_block instantiate_below, fold_conversions, cache, size_expr); case BIT_NOT_EXPR: - /* Handle ~X as -1 - X. */ - op0 = instantiate_scev_1 (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 0), - fold_conversions, cache, size_expr); - if (op0 == chrec_dont_know) - return chrec_dont_know; - - if (TREE_OPERAND (chrec, 0) != op0) - { - op0 = chrec_convert (type, op0, NULL); - chrec = chrec_fold_minus (type, - fold_convert (type, - integer_minus_one_node), - op0); - } - return chrec; + return instantiate_scev_bitnot (instantiate_below, evolution_loop, chrec, + fold_conversions, cache, size_expr); case SCEV_NOT_KNOWN: return chrec_dont_know; @@ -2443,7 +2466,7 @@ instantiate_scev_1 (basic_block instantiate_below, && op1 == TREE_OPERAND (chrec, 1)) return chrec; return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1); - + case 1: op0 = instantiate_scev_1 (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 0), -- cgit v1.2.1 From a819f8453a109032106be130ecaad17a81859569 Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 25 Nov 2009 04:30:10 +0000 Subject: 2009-09-01 Sebastian Pop * tree-scalar-evolution.c (instantiate_scev_poly): New. (instantiate_scev_1): Move code in instantiate_scev_poly. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154536 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 62 +++++++++++++++++++++++++++++++-------------- 1 file changed, 43 insertions(+), 19 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 6d8bf26c64c..6c9e09193c7 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -2191,6 +2191,47 @@ instantiate_scev_name (basic_block instantiate_below, } +/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW + and EVOLUTION_LOOP, that were left under a symbolic form. + + CHREC is a polynomial chain of recurrence to be instantiated. + + CACHE is the cache of already instantiated values. + + FOLD_CONVERSIONS should be set to true when the conversions that + may wrap in signed/pointer type are folded, as long as the value of + the chrec is preserved. + + SIZE_EXPR is used for computing the size of the expression to be + instantiated, and to stop if it exceeds some limit. */ + +static tree +instantiate_scev_poly (basic_block instantiate_below, + struct loop *evolution_loop, tree chrec, + bool fold_conversions, htab_t cache, int size_expr) +{ + tree op1; + tree op0 = instantiate_scev_1 (instantiate_below, evolution_loop, + CHREC_LEFT (chrec), fold_conversions, cache, + size_expr); + if (op0 == chrec_dont_know) + return chrec_dont_know; + + op1 = instantiate_scev_1 (instantiate_below, evolution_loop, + CHREC_RIGHT (chrec), fold_conversions, cache, + size_expr); + if (op1 == chrec_dont_know) + return chrec_dont_know; + + if (CHREC_LEFT (chrec) != op0 + || CHREC_RIGHT (chrec) != op1) + { + op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL); + chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); + } + return chrec; +} + /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. @@ -2371,25 +2412,8 @@ instantiate_scev_1 (basic_block instantiate_below, fold_conversions, cache, size_expr); case POLYNOMIAL_CHREC: - op0 = instantiate_scev_1 (instantiate_below, evolution_loop, - CHREC_LEFT (chrec), fold_conversions, cache, - size_expr); - if (op0 == chrec_dont_know) - return chrec_dont_know; - - op1 = instantiate_scev_1 (instantiate_below, evolution_loop, - CHREC_RIGHT (chrec), fold_conversions, cache, - size_expr); - if (op1 == chrec_dont_know) - return chrec_dont_know; - - if (CHREC_LEFT (chrec) != op0 - || CHREC_RIGHT (chrec) != op1) - { - op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL); - chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); - } - return chrec; + return instantiate_scev_poly (instantiate_below, evolution_loop, chrec, + fold_conversions, cache, size_expr); case POINTER_PLUS_EXPR: case PLUS_EXPR: -- cgit v1.2.1 From 378a662614f973d8f75e8f732c3bbac0e5298f7d Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 25 Nov 2009 04:30:41 +0000 Subject: 2009-09-01 Sebastian Pop * tree-scalar-evolution.c (instantiate_scev_3): New. (instantiate_scev_1): Move code in instantiate_scev_3. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154537 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 76 +++++++++++++++++++++++++++++---------------- 1 file changed, 50 insertions(+), 26 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 6c9e09193c7..11a9bf6c349 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -2376,6 +2376,53 @@ instantiate_scev_bitnot (basic_block instantiate_below, return chrec; } +/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW + and EVOLUTION_LOOP, that were left under a symbolic form. + + CHREC is an expression with 3 operands to be instantiated. + + CACHE is the cache of already instantiated values. + + FOLD_CONVERSIONS should be set to true when the conversions that + may wrap in signed/pointer type are folded, as long as the value of + the chrec is preserved. + + SIZE_EXPR is used for computing the size of the expression to be + instantiated, and to stop if it exceeds some limit. */ + +static tree +instantiate_scev_3 (basic_block instantiate_below, + struct loop *evolution_loop, tree chrec, + bool fold_conversions, htab_t cache, int size_expr) +{ + tree op1, op2; + tree op0 = instantiate_scev_1 (instantiate_below, evolution_loop, + TREE_OPERAND (chrec, 0), + fold_conversions, cache, size_expr); + if (op0 == chrec_dont_know) + return chrec_dont_know; + + op1 = instantiate_scev_1 (instantiate_below, evolution_loop, + TREE_OPERAND (chrec, 1), + fold_conversions, cache, size_expr); + if (op1 == chrec_dont_know) + return chrec_dont_know; + + op2 = instantiate_scev_1 (instantiate_below, evolution_loop, + TREE_OPERAND (chrec, 2), + fold_conversions, cache, size_expr); + if (op2 == chrec_dont_know) + return chrec_dont_know; + + if (op0 == TREE_OPERAND (chrec, 0) + && op1 == TREE_OPERAND (chrec, 1) + && op2 == TREE_OPERAND (chrec, 2)) + return chrec; + + return fold_build3 (TREE_CODE (chrec), + TREE_TYPE (chrec), op0, op1, op2); +} + /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. @@ -2395,7 +2442,7 @@ instantiate_scev_1 (basic_block instantiate_below, struct loop *evolution_loop, tree chrec, bool fold_conversions, htab_t cache, int size_expr) { - tree op0, op1, op2; + tree op0, op1; /* Give up if the expression is larger than the MAX that we allow. */ if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) @@ -2447,31 +2494,8 @@ instantiate_scev_1 (basic_block instantiate_below, switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) { case 3: - op0 = instantiate_scev_1 (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 0), - fold_conversions, cache, size_expr); - if (op0 == chrec_dont_know) - return chrec_dont_know; - - op1 = instantiate_scev_1 (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 1), - fold_conversions, cache, size_expr); - if (op1 == chrec_dont_know) - return chrec_dont_know; - - op2 = instantiate_scev_1 (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 2), - fold_conversions, cache, size_expr); - if (op2 == chrec_dont_know) - return chrec_dont_know; - - if (op0 == TREE_OPERAND (chrec, 0) - && op1 == TREE_OPERAND (chrec, 1) - && op2 == TREE_OPERAND (chrec, 2)) - return chrec; - - return fold_build3 (TREE_CODE (chrec), - TREE_TYPE (chrec), op0, op1, op2); + return instantiate_scev_3 (instantiate_below, evolution_loop, chrec, + fold_conversions, cache, size_expr); case 2: op0 = instantiate_scev_1 (instantiate_below, evolution_loop, -- cgit v1.2.1 From d91a99f1ad2eaf906907a64facdc54a879efeffa Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 25 Nov 2009 04:31:10 +0000 Subject: 2009-09-01 Sebastian Pop * tree-scalar-evolution.c (instantiate_scev_1): Renamed instantiate_scev_r. (instantiate_scev_r): Move code in instantiate_scev_2 and instantiate_scev_1. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154538 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 127 ++++++++++++++++++++++++++++++-------------- 1 file changed, 88 insertions(+), 39 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 11a9bf6c349..368cd28530f 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -2109,7 +2109,7 @@ loop_closed_phi_def (tree var) return NULL_TREE; } -static tree instantiate_scev_1 (basic_block, struct loop *, tree, bool, +static tree instantiate_scev_r (basic_block, struct loop *, tree, bool, htab_t, int); /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW @@ -2182,7 +2182,7 @@ instantiate_scev_name (basic_block instantiate_below, } else if (res != chrec_dont_know) - res = instantiate_scev_1 (instantiate_below, evolution_loop, res, + res = instantiate_scev_r (instantiate_below, evolution_loop, res, fold_conversions, cache, size_expr); /* Store the correct value to the cache. */ @@ -2211,13 +2211,13 @@ instantiate_scev_poly (basic_block instantiate_below, bool fold_conversions, htab_t cache, int size_expr) { tree op1; - tree op0 = instantiate_scev_1 (instantiate_below, evolution_loop, + tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, CHREC_LEFT (chrec), fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; - op1 = instantiate_scev_1 (instantiate_below, evolution_loop, + op1 = instantiate_scev_r (instantiate_below, evolution_loop, CHREC_RIGHT (chrec), fold_conversions, cache, size_expr); if (op1 == chrec_dont_know) @@ -2252,13 +2252,13 @@ instantiate_scev_binary (basic_block instantiate_below, bool fold_conversions, htab_t cache, int size_expr) { tree op1; - tree op0 = instantiate_scev_1 (instantiate_below, evolution_loop, + tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 0), fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; - op1 = instantiate_scev_1 (instantiate_below, evolution_loop, + op1 = instantiate_scev_r (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 1), fold_conversions, cache, size_expr); if (op1 == chrec_dont_know) @@ -2313,7 +2313,7 @@ instantiate_scev_convert (basic_block instantiate_below, tree type, tree op, bool fold_conversions, htab_t cache, int size_expr) { - tree op0 = instantiate_scev_1 (instantiate_below, evolution_loop, op, + tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op, fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) @@ -2359,7 +2359,7 @@ instantiate_scev_bitnot (basic_block instantiate_below, bool fold_conversions, htab_t cache, int size_expr) { tree type = chrec_type (chrec); - tree op0 = instantiate_scev_1 (instantiate_below, evolution_loop, + tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 0), fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) @@ -2396,19 +2396,19 @@ instantiate_scev_3 (basic_block instantiate_below, bool fold_conversions, htab_t cache, int size_expr) { tree op1, op2; - tree op0 = instantiate_scev_1 (instantiate_below, evolution_loop, + tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 0), fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; - op1 = instantiate_scev_1 (instantiate_below, evolution_loop, + op1 = instantiate_scev_r (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 1), fold_conversions, cache, size_expr); if (op1 == chrec_dont_know) return chrec_dont_know; - op2 = instantiate_scev_1 (instantiate_below, evolution_loop, + op2 = instantiate_scev_r (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 2), fold_conversions, cache, size_expr); if (op2 == chrec_dont_know) @@ -2426,7 +2426,46 @@ instantiate_scev_3 (basic_block instantiate_below, /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. - CHREC is the scalar evolution to instantiate. + CHREC is an expression with 2 operands to be instantiated. + + CACHE is the cache of already instantiated values. + + FOLD_CONVERSIONS should be set to true when the conversions that + may wrap in signed/pointer type are folded, as long as the value of + the chrec is preserved. + + SIZE_EXPR is used for computing the size of the expression to be + instantiated, and to stop if it exceeds some limit. */ + +static tree +instantiate_scev_2 (basic_block instantiate_below, + struct loop *evolution_loop, tree chrec, + bool fold_conversions, htab_t cache, int size_expr) +{ + tree op1; + tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, + TREE_OPERAND (chrec, 0), + fold_conversions, cache, size_expr); + if (op0 == chrec_dont_know) + return chrec_dont_know; + + op1 = instantiate_scev_r (instantiate_below, evolution_loop, + TREE_OPERAND (chrec, 1), + fold_conversions, cache, size_expr); + if (op1 == chrec_dont_know) + return chrec_dont_know; + + if (op0 == TREE_OPERAND (chrec, 0) + && op1 == TREE_OPERAND (chrec, 1)) + return chrec; + + return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1); +} + +/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW + and EVOLUTION_LOOP, that were left under a symbolic form. + + CHREC is an expression with 2 operands to be instantiated. CACHE is the cache of already instantiated values. @@ -2442,8 +2481,38 @@ instantiate_scev_1 (basic_block instantiate_below, struct loop *evolution_loop, tree chrec, bool fold_conversions, htab_t cache, int size_expr) { - tree op0, op1; + tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, + TREE_OPERAND (chrec, 0), + fold_conversions, cache, size_expr); + + 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); +} + +/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW + and EVOLUTION_LOOP, that were left under a symbolic form. + + CHREC is the scalar evolution to instantiate. + + CACHE is the cache of already instantiated values. + FOLD_CONVERSIONS should be set to true when the conversions that + may wrap in signed/pointer type are folded, as long as the value of + the chrec is preserved. + + SIZE_EXPR is used for computing the size of the expression to be + instantiated, and to stop if it exceeds some limit. */ + +static tree +instantiate_scev_r (basic_block instantiate_below, + struct loop *evolution_loop, tree chrec, + bool fold_conversions, htab_t cache, int size_expr) +{ /* Give up if the expression is larger than the MAX that we allow. */ if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) return chrec_dont_know; @@ -2498,32 +2567,12 @@ instantiate_scev_1 (basic_block instantiate_below, fold_conversions, cache, size_expr); case 2: - op0 = instantiate_scev_1 (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 0), - fold_conversions, cache, size_expr); - if (op0 == chrec_dont_know) - return chrec_dont_know; - - op1 = instantiate_scev_1 (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 1), - fold_conversions, cache, size_expr); - if (op1 == chrec_dont_know) - return chrec_dont_know; - - if (op0 == TREE_OPERAND (chrec, 0) - && op1 == TREE_OPERAND (chrec, 1)) - return chrec; - return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1); + return instantiate_scev_2 (instantiate_below, evolution_loop, chrec, + fold_conversions, cache, size_expr); case 1: - op0 = instantiate_scev_1 (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 0), - fold_conversions, cache, size_expr); - 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 instantiate_scev_1 (instantiate_below, evolution_loop, chrec, + fold_conversions, cache, size_expr); case 0: return chrec; @@ -2559,7 +2608,7 @@ instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop, fprintf (dump_file, ")\n"); } - res = instantiate_scev_1 (instantiate_below, evolution_loop, chrec, false, + res = instantiate_scev_r (instantiate_below, evolution_loop, chrec, false, cache, 0); if (dump_file && (dump_flags & TDF_DETAILS)) @@ -2583,7 +2632,7 @@ 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_scev_1 (block_before_loop (loop), loop, chrec, true, + tree ret = instantiate_scev_r (block_before_loop (loop), loop, chrec, true, cache, 0); htab_delete (cache); return ret; -- cgit v1.2.1 From 9d206f16271e7ec399edbfdd12bde37de9a6ae29 Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 25 Nov 2009 04:31:40 +0000 Subject: 2009-09-01 Sebastian Pop * tree-scalar-evolution.c (instantiate_scev_bitnot): Renamed instantiate_scev_not. Handle NEGATE_EXPR. (instantiate_scev_r): Handle NEGATE_EXPR. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154539 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 33 +++++++++++++++++++++++---------- 1 file changed, 23 insertions(+), 10 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 368cd28530f..41944972cb8 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -2341,8 +2341,9 @@ instantiate_scev_convert (basic_block instantiate_below, /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. - CHREC is a BIT_NOT_EXPR expression to be instantiated. + CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated. Handle ~X as -1 - X. + Handle -X as -1 * X. CACHE is the cache of already instantiated values. @@ -2354,9 +2355,9 @@ instantiate_scev_convert (basic_block instantiate_below, instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_scev_bitnot (basic_block instantiate_below, - struct loop *evolution_loop, tree chrec, - bool fold_conversions, htab_t cache, int size_expr) +instantiate_scev_not (basic_block instantiate_below, + struct loop *evolution_loop, tree chrec, + bool fold_conversions, htab_t cache, int size_expr) { tree type = chrec_type (chrec); tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, @@ -2368,11 +2369,22 @@ instantiate_scev_bitnot (basic_block instantiate_below, if (TREE_OPERAND (chrec, 0) != op0) { op0 = chrec_convert (type, op0, NULL); - chrec = chrec_fold_minus (type, - fold_convert (type, - integer_minus_one_node), - op0); + + switch (TREE_CODE (chrec)) + { + case BIT_NOT_EXPR: + return chrec_fold_minus + (type, fold_convert (type, integer_minus_one_node), op0); + + case NEGATE_EXPR: + return chrec_fold_multiply + (type, fold_convert (type, integer_minus_one_node), op0); + + default: + gcc_unreachable (); + } } + return chrec; } @@ -2543,9 +2555,10 @@ instantiate_scev_r (basic_block instantiate_below, TREE_TYPE (chrec), TREE_OPERAND (chrec, 0), fold_conversions, cache, size_expr); + case NEGATE_EXPR: case BIT_NOT_EXPR: - return instantiate_scev_bitnot (instantiate_below, evolution_loop, chrec, - fold_conversions, cache, size_expr); + return instantiate_scev_not (instantiate_below, evolution_loop, chrec, + fold_conversions, cache, size_expr); case SCEV_NOT_KNOWN: return chrec_dont_know; -- cgit v1.2.1 From 9e9aa0c6b103af51f292baa804390fbd7d613ae2 Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 25 Nov 2009 04:32:07 +0000 Subject: 2009-09-01 Sebastian Pop * tree-scalar-evolution.c (instantiate_scev_binary): Adapted to pass as parameters the operands of the binary expression. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154540 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 22 ++++++++++++---------- 1 file changed, 12 insertions(+), 10 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 41944972cb8..a6b3e77a08e 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -2235,7 +2235,7 @@ instantiate_scev_poly (basic_block instantiate_below, /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. - CHREC is a binary expression to be instantiated. + "C0 CODE C1" is a binary expression of type TYPE to be instantiated. CACHE is the cache of already instantiated values. @@ -2248,31 +2248,30 @@ instantiate_scev_poly (basic_block instantiate_below, static tree instantiate_scev_binary (basic_block instantiate_below, - struct loop *evolution_loop, tree chrec, + struct loop *evolution_loop, tree chrec, enum tree_code code, + tree type, tree c0, tree c1, bool fold_conversions, htab_t cache, int size_expr) { tree op1; tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 0), fold_conversions, cache, + c0, fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; op1 = instantiate_scev_r (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 1), fold_conversions, cache, + c1, fold_conversions, cache, size_expr); if (op1 == chrec_dont_know) return chrec_dont_know; - if (TREE_OPERAND (chrec, 0) != op0 - || TREE_OPERAND (chrec, 1) != op1) + if (c0 != op0 + || c1 != op1) { - tree type = chrec_type (chrec); - op0 = chrec_convert (type, op0, NULL); op1 = chrec_convert_rhs (type, op1, NULL); - switch (TREE_CODE (chrec)) + switch (code) { case POINTER_PLUS_EXPR: case PLUS_EXPR: @@ -2289,7 +2288,7 @@ instantiate_scev_binary (basic_block instantiate_below, } } - return chrec; + return chrec ? chrec : fold_build2 (code, type, c0, c1); } /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW @@ -2548,6 +2547,9 @@ instantiate_scev_r (basic_block instantiate_below, case MINUS_EXPR: case MULT_EXPR: return instantiate_scev_binary (instantiate_below, evolution_loop, chrec, + TREE_CODE (chrec), chrec_type (chrec), + TREE_OPERAND (chrec, 0), + TREE_OPERAND (chrec, 1), fold_conversions, cache, size_expr); CASE_CONVERT: -- cgit v1.2.1 From c43f1e90c227c56517f9ea4a40377f38a8970ff8 Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 25 Nov 2009 04:32:35 +0000 Subject: 2009-09-01 Sebastian Pop * tree-scalar-evolution.c (instantiate_scev_assign): New. Do not call analyze_scalar_evolution on assignments. (instantiate_scev_phi): Call analyze_scalar_evolution. (instantiate_scev_name): Call instantiate_scev_assign and instantiate_scev_phi. (instantiate_scev_not): Adapted to pass as parameters the operands of the not expression. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154541 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 182 ++++++++++++++++++++++++++++++++++++-------- 1 file changed, 150 insertions(+), 32 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index a6b3e77a08e..41e95b48917 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -2109,13 +2109,21 @@ loop_closed_phi_def (tree var) return NULL_TREE; } +static tree instantiate_scev_binary (basic_block, struct loop *, tree, + enum tree_code, tree, tree, tree, + bool, htab_t, int); +static tree instantiate_scev_convert (basic_block, struct loop *, tree, tree, + tree, bool, htab_t, int); +static tree instantiate_scev_not (basic_block, struct loop *, tree, + enum tree_code, tree, tree, + bool, htab_t, int); static tree instantiate_scev_r (basic_block, struct loop *, tree, bool, htab_t, int); /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. - CHREC is an SSA_NAME to be instantiated. + STMT is a GIMPLE assignment to be instantiated. CACHE is the cache of already instantiated values. @@ -2127,38 +2135,90 @@ static tree instantiate_scev_r (basic_block, struct loop *, tree, bool, instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_scev_name (basic_block instantiate_below, - struct loop *evolution_loop, tree chrec, - bool fold_conversions, htab_t cache, int size_expr) +instantiate_scev_assign (basic_block instantiate_below, + struct loop *evolution_loop, gimple stmt, + bool fold_conversions, htab_t cache, int size_expr) { - tree res; - struct loop *def_loop; - basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec)); + tree type = TREE_TYPE (gimple_assign_lhs (stmt)); + tree rhs1 = gimple_assign_rhs1 (stmt); + tree rhs2 = gimple_assign_rhs2 (stmt); + enum tree_code code = gimple_assign_rhs_code (stmt); - /* A parameter (or loop invariant and we do not want to include - evolutions in outer loops), nothing to do. */ - if (!def_bb - || loop_depth (def_bb->loop_father) == 0 - || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb)) - return chrec; + if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS) + { + if (is_gimple_min_invariant (rhs1)) + return chrec_convert (type, rhs1, stmt); - /* We cache the value of instantiated variable to avoid exponential - time complexity due to reevaluations. We also store the convenient - value in the cache in order to prevent infinite recursion -- we do - not want to instantiate the SSA_NAME if it is in a mixer - structure. This is used for avoiding the instantiation of - recursively defined functions, such as: + if (code == SSA_NAME) + { + rhs1 = instantiate_scev_r (instantiate_below, evolution_loop, rhs1, + fold_conversions, cache, size_expr); + return chrec_convert (type, rhs1, stmt); + } - | a_2 -> {0, +, 1, +, a_2}_1 */ + if (code == ASSERT_EXPR) + { + rhs1 = ASSERT_EXPR_VAR (rhs1); + rhs1 = instantiate_scev_r (instantiate_below, evolution_loop, rhs1, + fold_conversions, cache, size_expr); + return chrec_convert (type, rhs1, stmt); + } - res = get_instantiated_value (cache, instantiate_below, chrec); - if (res) - return res; + return chrec_dont_know; + } - res = chrec_dont_know; - set_instantiated_value (cache, instantiate_below, chrec, res); + switch (code) + { + case POINTER_PLUS_EXPR: + case PLUS_EXPR: + case MINUS_EXPR: + case MULT_EXPR: + return instantiate_scev_binary (instantiate_below, evolution_loop, + NULL_TREE, code, type, rhs1, rhs2, + fold_conversions, cache, size_expr); - def_loop = find_common_loop (evolution_loop, def_bb->loop_father); + case NEGATE_EXPR: + case BIT_NOT_EXPR: + return instantiate_scev_not (instantiate_below, evolution_loop, + NULL_TREE, code, type, rhs1, + fold_conversions, cache, size_expr); + + CASE_CONVERT: + return instantiate_scev_convert (instantiate_below, evolution_loop, + NULL_TREE, type, rhs1, + fold_conversions, cache, size_expr); + default: + return chrec_dont_know; + } +} + +/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW + and EVOLUTION_LOOP, that were left under a symbolic form. + + CHREC is an SSA_NAME defined by a GIMPLE PHI node. As the PHI node + belongs to the region to be instantiated, it is fully analyzed and + transformed into a chain of recurrence. + + CACHE is the cache of already instantiated values. + + FOLD_CONVERSIONS should be set to true when the conversions that + may wrap in signed/pointer type are folded, as long as the value of + the chrec is preserved. + + SIZE_EXPR is used for computing the size of the expression to be + instantiated, and to stop if it exceeds some limit. */ + +static tree +instantiate_scev_phi (basic_block instantiate_below, + struct loop *evolution_loop, tree chrec, + bool fold_conversions, htab_t cache, int size_expr) +{ + tree res = chrec_dont_know; + gimple def = SSA_NAME_DEF_STMT (chrec); + basic_block def_bb = gimple_bb (def); + loop_p def_loop = find_common_loop (evolution_loop, def_bb->loop_father); + + set_instantiated_value (cache, instantiate_below, chrec, res); /* If the analysis yields a parametric chrec, instantiate the result again. */ @@ -2188,7 +2248,63 @@ instantiate_scev_name (basic_block instantiate_below, /* Store the correct value to the cache. */ set_instantiated_value (cache, instantiate_below, chrec, res); return res; +} + +/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW + and EVOLUTION_LOOP, that were left under a symbolic form. + + CHREC is an SSA_NAME to be instantiated. + + CACHE is the cache of already instantiated values. + + FOLD_CONVERSIONS should be set to true when the conversions that + may wrap in signed/pointer type are folded, as long as the value of + the chrec is preserved. + + SIZE_EXPR is used for computing the size of the expression to be + instantiated, and to stop if it exceeds some limit. */ + +static tree +instantiate_scev_name (basic_block instantiate_below, + struct loop *evolution_loop, tree chrec, + bool fold_conversions, htab_t cache, int size_expr) +{ + tree res; + gimple def = SSA_NAME_DEF_STMT (chrec); + basic_block def_bb = gimple_bb (def); + + /* A parameter (or loop invariant and we do not want to include + evolutions in outer loops), nothing to do. */ + if (!def_bb + || loop_depth (def_bb->loop_father) == 0 + || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb)) + return chrec; + /* We cache the value of instantiated variable to avoid exponential + time complexity due to reevaluations. We also store the convenient + value in the cache in order to prevent infinite recursion -- we do + not want to instantiate the SSA_NAME if it is in a mixer + structure. This is used for avoiding the instantiation of + recursively defined functions, such as: + + | a_2 -> {0, +, 1, +, a_2}_1 */ + + res = get_instantiated_value (cache, instantiate_below, chrec); + if (res) + return res; + + /* Return the RHS */ + switch (gimple_code (def)) + { + case GIMPLE_ASSIGN: + return instantiate_scev_assign (instantiate_below, evolution_loop, def, + fold_conversions, cache, size_expr); + case GIMPLE_PHI: + return instantiate_scev_phi (instantiate_below, evolution_loop, chrec, + fold_conversions, cache, size_expr); + default: + return chrec_dont_know; + } } /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW @@ -2356,20 +2472,20 @@ instantiate_scev_convert (basic_block instantiate_below, static tree instantiate_scev_not (basic_block instantiate_below, struct loop *evolution_loop, tree chrec, + enum tree_code code, tree type, tree op, bool fold_conversions, htab_t cache, int size_expr) { - tree type = chrec_type (chrec); - tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 0), + tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op, fold_conversions, cache, size_expr); + if (op0 == chrec_dont_know) return chrec_dont_know; - if (TREE_OPERAND (chrec, 0) != op0) + if (op != op0) { op0 = chrec_convert (type, op0, NULL); - switch (TREE_CODE (chrec)) + switch (code) { case BIT_NOT_EXPR: return chrec_fold_minus @@ -2384,7 +2500,7 @@ instantiate_scev_not (basic_block instantiate_below, } } - return chrec; + return chrec ? chrec : fold_build1 (code, type, op0); } /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW @@ -2560,6 +2676,8 @@ instantiate_scev_r (basic_block instantiate_below, case NEGATE_EXPR: case BIT_NOT_EXPR: return instantiate_scev_not (instantiate_below, evolution_loop, chrec, + TREE_CODE (chrec), TREE_TYPE (chrec), + TREE_OPERAND (chrec, 0), fold_conversions, cache, size_expr); case SCEV_NOT_KNOWN: -- cgit v1.2.1 From 5e803fbe4ef0f368b8e24a6516ff2e1f5344a3c0 Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 25 Nov 2009 04:33:03 +0000 Subject: 2009-09-02 Sebastian Pop Partially revert the previous patch, except the following. * tree-scalar-evolution.c (instantiate_scev_not): Adapted to pass as parameters the operands of the not expression. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154542 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 168 +++++++------------------------------------- 1 file changed, 26 insertions(+), 142 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 41e95b48917..e3f33e2ef96 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -2109,21 +2109,13 @@ loop_closed_phi_def (tree var) return NULL_TREE; } -static tree instantiate_scev_binary (basic_block, struct loop *, tree, - enum tree_code, tree, tree, tree, - bool, htab_t, int); -static tree instantiate_scev_convert (basic_block, struct loop *, tree, tree, - tree, bool, htab_t, int); -static tree instantiate_scev_not (basic_block, struct loop *, tree, - enum tree_code, tree, tree, - bool, htab_t, int); static tree instantiate_scev_r (basic_block, struct loop *, tree, bool, htab_t, int); /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. - STMT is a GIMPLE assignment to be instantiated. + CHREC is an SSA_NAME to be instantiated. CACHE is the cache of already instantiated values. @@ -2135,91 +2127,39 @@ static tree instantiate_scev_r (basic_block, struct loop *, tree, bool, instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_scev_assign (basic_block instantiate_below, - struct loop *evolution_loop, gimple stmt, - bool fold_conversions, htab_t cache, int size_expr) +instantiate_scev_name (basic_block instantiate_below, + struct loop *evolution_loop, tree chrec, + bool fold_conversions, htab_t cache, int size_expr) { - tree type = TREE_TYPE (gimple_assign_lhs (stmt)); - tree rhs1 = gimple_assign_rhs1 (stmt); - tree rhs2 = gimple_assign_rhs2 (stmt); - enum tree_code code = gimple_assign_rhs_code (stmt); - - if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS) - { - if (is_gimple_min_invariant (rhs1)) - return chrec_convert (type, rhs1, stmt); - - if (code == SSA_NAME) - { - rhs1 = instantiate_scev_r (instantiate_below, evolution_loop, rhs1, - fold_conversions, cache, size_expr); - return chrec_convert (type, rhs1, stmt); - } - - if (code == ASSERT_EXPR) - { - rhs1 = ASSERT_EXPR_VAR (rhs1); - rhs1 = instantiate_scev_r (instantiate_below, evolution_loop, rhs1, - fold_conversions, cache, size_expr); - return chrec_convert (type, rhs1, stmt); - } - - return chrec_dont_know; - } - - switch (code) - { - case POINTER_PLUS_EXPR: - case PLUS_EXPR: - case MINUS_EXPR: - case MULT_EXPR: - return instantiate_scev_binary (instantiate_below, evolution_loop, - NULL_TREE, code, type, rhs1, rhs2, - fold_conversions, cache, size_expr); - - case NEGATE_EXPR: - case BIT_NOT_EXPR: - return instantiate_scev_not (instantiate_below, evolution_loop, - NULL_TREE, code, type, rhs1, - fold_conversions, cache, size_expr); - - CASE_CONVERT: - return instantiate_scev_convert (instantiate_below, evolution_loop, - NULL_TREE, type, rhs1, - fold_conversions, cache, size_expr); - default: - return chrec_dont_know; - } -} - -/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW - and EVOLUTION_LOOP, that were left under a symbolic form. - - CHREC is an SSA_NAME defined by a GIMPLE PHI node. As the PHI node - belongs to the region to be instantiated, it is fully analyzed and - transformed into a chain of recurrence. + tree res; + struct loop *def_loop; + basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec)); - CACHE is the cache of already instantiated values. + /* A parameter (or loop invariant and we do not want to include + evolutions in outer loops), nothing to do. */ + if (!def_bb + || loop_depth (def_bb->loop_father) == 0 + || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb)) + return chrec; - FOLD_CONVERSIONS should be set to true when the conversions that - may wrap in signed/pointer type are folded, as long as the value of - the chrec is preserved. + /* We cache the value of instantiated variable to avoid exponential + time complexity due to reevaluations. We also store the convenient + value in the cache in order to prevent infinite recursion -- we do + not want to instantiate the SSA_NAME if it is in a mixer + structure. This is used for avoiding the instantiation of + recursively defined functions, such as: - SIZE_EXPR is used for computing the size of the expression to be - instantiated, and to stop if it exceeds some limit. */ + | a_2 -> {0, +, 1, +, a_2}_1 */ -static tree -instantiate_scev_phi (basic_block instantiate_below, - struct loop *evolution_loop, tree chrec, - bool fold_conversions, htab_t cache, int size_expr) -{ - tree res = chrec_dont_know; - gimple def = SSA_NAME_DEF_STMT (chrec); - basic_block def_bb = gimple_bb (def); - loop_p def_loop = find_common_loop (evolution_loop, def_bb->loop_father); + res = get_instantiated_value (cache, instantiate_below, chrec); + if (res) + return res; + res = chrec_dont_know; set_instantiated_value (cache, instantiate_below, chrec, res); + def_loop = find_common_loop (evolution_loop, def_bb->loop_father); + /* If the analysis yields a parametric chrec, instantiate the result again. */ res = analyze_scalar_evolution (def_loop, chrec); @@ -2248,63 +2188,7 @@ instantiate_scev_phi (basic_block instantiate_below, /* Store the correct value to the cache. */ set_instantiated_value (cache, instantiate_below, chrec, res); return res; -} - -/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW - and EVOLUTION_LOOP, that were left under a symbolic form. - CHREC is an SSA_NAME to be instantiated. - - CACHE is the cache of already instantiated values. - - FOLD_CONVERSIONS should be set to true when the conversions that - may wrap in signed/pointer type are folded, as long as the value of - the chrec is preserved. - - SIZE_EXPR is used for computing the size of the expression to be - instantiated, and to stop if it exceeds some limit. */ - -static tree -instantiate_scev_name (basic_block instantiate_below, - struct loop *evolution_loop, tree chrec, - bool fold_conversions, htab_t cache, int size_expr) -{ - tree res; - gimple def = SSA_NAME_DEF_STMT (chrec); - basic_block def_bb = gimple_bb (def); - - /* A parameter (or loop invariant and we do not want to include - evolutions in outer loops), nothing to do. */ - if (!def_bb - || loop_depth (def_bb->loop_father) == 0 - || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb)) - return chrec; - - /* We cache the value of instantiated variable to avoid exponential - time complexity due to reevaluations. We also store the convenient - value in the cache in order to prevent infinite recursion -- we do - not want to instantiate the SSA_NAME if it is in a mixer - structure. This is used for avoiding the instantiation of - recursively defined functions, such as: - - | a_2 -> {0, +, 1, +, a_2}_1 */ - - res = get_instantiated_value (cache, instantiate_below, chrec); - if (res) - return res; - - /* Return the RHS */ - switch (gimple_code (def)) - { - case GIMPLE_ASSIGN: - return instantiate_scev_assign (instantiate_below, evolution_loop, def, - fold_conversions, cache, size_expr); - case GIMPLE_PHI: - return instantiate_scev_phi (instantiate_below, evolution_loop, chrec, - fold_conversions, cache, size_expr); - default: - return chrec_dont_know; - } } /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW -- cgit v1.2.1 From 1d4dd1ed696e4c78d2608195368e6be22e98e676 Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 25 Nov 2009 05:35:58 +0000 Subject: 2009-11-18 Sebastian Pop PR middle-end/40281 * testsuite/gcc.dg/graphite/pr40281.c: New. * tree-scalar-evolution.c (instantiate_scev_poly): Base and stride evolutions should not variate in inner loops. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154641 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 14 +++++++++++++- 1 file changed, 13 insertions(+), 1 deletion(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index e3f33e2ef96..2cae2ceff45 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -2226,9 +2226,21 @@ instantiate_scev_poly (basic_block instantiate_below, if (CHREC_LEFT (chrec) != op0 || CHREC_RIGHT (chrec) != op1) { + unsigned var = CHREC_VARIABLE (chrec); + + /* When the instantiated stride or base has an evolution in an + innermost loop, return chrec_dont_know, as this is not a + valid SCEV representation. In the reduced testcase for + PR40281 we would have {0, +, {1, +, 1}_2}_1 that has no + meaning. */ + if ((tree_is_chrec (op0) && CHREC_VARIABLE (op0) > var) + || (tree_is_chrec (op1) && CHREC_VARIABLE (op1) > var)) + return chrec_dont_know; + op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL); - chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); + chrec = build_polynomial_chrec (var, op0, op1); } + return chrec; } -- cgit v1.2.1 From 48e1416a24d50cacbb2a5e06a9ee61dd8cbee313 Mon Sep 17 00:00:00 2001 From: hjl Date: Wed, 25 Nov 2009 10:55:54 +0000 Subject: Remove trailing white spaces. 2009-11-25 H.J. Lu * alias.c: Remove trailing white spaces. * alloc-pool.c: Likewise. * alloc-pool.h: Likewise. * attribs.c: Likewise. * auto-inc-dec.c: Likewise. * basic-block.h: Likewise. * bb-reorder.c: Likewise. * bt-load.c: Likewise. * builtins.c: Likewise. * builtins.def: Likewise. * c-common.c: Likewise. * c-common.h: Likewise. * c-cppbuiltin.c: Likewise. * c-decl.c: Likewise. * c-format.c: Likewise. * c-lex.c: Likewise. * c-omp.c: Likewise. * c-opts.c: Likewise. * c-parser.c: Likewise. * c-pretty-print.c: Likewise. * c-tree.h: Likewise. * c-typeck.c: Likewise. * caller-save.c: Likewise. * calls.c: Likewise. * cfg.c: Likewise. * cfganal.c: Likewise. * cfgexpand.c: Likewise. * cfghooks.c: Likewise. * cfghooks.h: Likewise. * cfglayout.c: Likewise. * cfgloop.c: Likewise. * cfgloop.h: Likewise. * cfgloopmanip.c: Likewise. * cfgrtl.c: Likewise. * cgraph.c: Likewise. * cgraph.h: Likewise. * cgraphbuild.c: Likewise. * cgraphunit.c: Likewise. * cif-code.def: Likewise. * collect2.c: Likewise. * combine.c: Likewise. * convert.c: Likewise. * coverage.c: Likewise. * crtstuff.c: Likewise. * cse.c: Likewise. * cselib.c: Likewise. * dbgcnt.c: Likewise. * dbgcnt.def: Likewise. * dbgcnt.h: Likewise. * dbxout.c: Likewise. * dce.c: Likewise. * ddg.c: Likewise. * ddg.h: Likewise. * defaults.h: Likewise. * df-byte-scan.c: Likewise. * df-core.c: Likewise. * df-problems.c: Likewise. * df-scan.c: Likewise. * df.h: Likewise. * dfp.c: Likewise. * diagnostic.c: Likewise. * diagnostic.h: Likewise. * dominance.c: Likewise. * domwalk.c: Likewise. * double-int.c: Likewise. * double-int.h: Likewise. * dse.c: Likewise. * dwarf2asm.c: Likewise. * dwarf2asm.h: Likewise. * dwarf2out.c: Likewise. * ebitmap.c: Likewise. * ebitmap.h: Likewise. * emit-rtl.c: Likewise. * et-forest.c: Likewise. * except.c: Likewise. * except.h: Likewise. * expmed.c: Likewise. * expr.c: Likewise. * expr.h: Likewise. * final.c: Likewise. * flags.h: Likewise. * fold-const.c: Likewise. * function.c: Likewise. * function.h: Likewise. * fwprop.c: Likewise. * gcc.c: Likewise. * gcov-dump.c: Likewise. * gcov-io.c: Likewise. * gcov-io.h: Likewise. * gcov.c: Likewise. * gcse.c: Likewise. * genattr.c: Likewise. * genattrtab.c: Likewise. * genautomata.c: Likewise. * genchecksum.c: Likewise. * genconfig.c: Likewise. * genflags.c: Likewise. * gengtype-parse.c: Likewise. * gengtype.c: Likewise. * gengtype.h: Likewise. * genmddeps.c: Likewise. * genmodes.c: Likewise. * genopinit.c: Likewise. * genpreds.c: Likewise. * gensupport.c: Likewise. * ggc-common.c: Likewise. * ggc-page.c: Likewise. * ggc-zone.c: Likewise. * ggc.h: Likewise. * gimple-iterator.c: Likewise. * gimple-low.c: Likewise. * gimple-pretty-print.c: Likewise. * gimple.c: Likewise. * gimple.def: Likewise. * gimple.h: Likewise. * gimplify.c: Likewise. * graphds.c: Likewise. * graphite-clast-to-gimple.c: Likewise. * gthr-nks.h: Likewise. * gthr-posix.c: Likewise. * gthr-posix.h: Likewise. * gthr-posix95.h: Likewise. * gthr-single.h: Likewise. * gthr-tpf.h: Likewise. * gthr-vxworks.h: Likewise. * gthr.h: Likewise. * haifa-sched.c: Likewise. * hard-reg-set.h: Likewise. * hooks.c: Likewise. * hooks.h: Likewise. * hosthooks.h: Likewise. * hwint.h: Likewise. * ifcvt.c: Likewise. * incpath.c: Likewise. * init-regs.c: Likewise. * integrate.c: Likewise. * ipa-cp.c: Likewise. * ipa-inline.c: Likewise. * ipa-prop.c: Likewise. * ipa-pure-const.c: Likewise. * ipa-reference.c: Likewise. * ipa-struct-reorg.c: Likewise. * ipa-struct-reorg.h: Likewise. * ipa-type-escape.c: Likewise. * ipa-type-escape.h: Likewise. * ipa-utils.c: Likewise. * ipa-utils.h: Likewise. * ipa.c: Likewise. * ira-build.c: Likewise. * ira-color.c: Likewise. * ira-conflicts.c: Likewise. * ira-costs.c: Likewise. * ira-emit.c: Likewise. * ira-int.h: Likewise. * ira-lives.c: Likewise. * ira.c: Likewise. * jump.c: Likewise. * lambda-code.c: Likewise. * lambda-mat.c: Likewise. * lambda-trans.c: Likewise. * lambda.h: Likewise. * langhooks.c: Likewise. * lcm.c: Likewise. * libgcov.c: Likewise. * lists.c: Likewise. * loop-doloop.c: Likewise. * loop-init.c: Likewise. * loop-invariant.c: Likewise. * loop-iv.c: Likewise. * loop-unroll.c: Likewise. * lower-subreg.c: Likewise. * lto-cgraph.c: Likewise. * lto-compress.c: Likewise. * lto-opts.c: Likewise. * lto-section-in.c: Likewise. * lto-section-out.c: Likewise. * lto-streamer-in.c: Likewise. * lto-streamer-out.c: Likewise. * lto-streamer.c: Likewise. * lto-streamer.h: Likewise. * lto-symtab.c: Likewise. * lto-wpa-fixup.c: Likewise. * matrix-reorg.c: Likewise. * mcf.c: Likewise. * mode-switching.c: Likewise. * modulo-sched.c: Likewise. * omega.c: Likewise. * omega.h: Likewise. * omp-low.c: Likewise. * optabs.c: Likewise. * optabs.h: Likewise. * opts-common.c: Likewise. * opts.c: Likewise. * params.def: Likewise. * params.h: Likewise. * passes.c: Likewise. * plugin.c: Likewise. * postreload-gcse.c: Likewise. * postreload.c: Likewise. * predict.c: Likewise. * predict.def: Likewise. * pretty-print.c: Likewise. * pretty-print.h: Likewise. * print-rtl.c: Likewise. * print-tree.c: Likewise. * profile.c: Likewise. * read-rtl.c: Likewise. * real.c: Likewise. * recog.c: Likewise. * reg-stack.c: Likewise. * regcprop.c: Likewise. * reginfo.c: Likewise. * regmove.c: Likewise. * regrename.c: Likewise. * regs.h: Likewise. * regstat.c: Likewise. * reload.c: Likewise. * reload1.c: Likewise. * resource.c: Likewise. * rtl.c: Likewise. * rtl.def: Likewise. * rtl.h: Likewise. * rtlanal.c: Likewise. * sbitmap.c: Likewise. * sched-deps.c: Likewise. * sched-ebb.c: Likewise. * sched-int.h: Likewise. * sched-rgn.c: Likewise. * sched-vis.c: Likewise. * sdbout.c: Likewise. * sel-sched-dump.c: Likewise. * sel-sched-dump.h: Likewise. * sel-sched-ir.c: Likewise. * sel-sched-ir.h: Likewise. * sel-sched.c: Likewise. * sel-sched.h: Likewise. * sese.c: Likewise. * sese.h: Likewise. * simplify-rtx.c: Likewise. * stack-ptr-mod.c: Likewise. * stmt.c: Likewise. * stor-layout.c: Likewise. * store-motion.c: Likewise. * stringpool.c: Likewise. * stub-objc.c: Likewise. * sync-builtins.def: Likewise. * target-def.h: Likewise. * target.h: Likewise. * targhooks.c: Likewise. * targhooks.h: Likewise. * timevar.c: Likewise. * tlink.c: Likewise. * toplev.c: Likewise. * toplev.h: Likewise. * tracer.c: Likewise. * tree-affine.c: Likewise. * tree-affine.h: Likewise. * tree-browser.def: Likewise. * tree-call-cdce.c: Likewise. * tree-cfg.c: Likewise. * tree-cfgcleanup.c: Likewise. * tree-chrec.c: Likewise. * tree-chrec.h: Likewise. * tree-complex.c: Likewise. * tree-data-ref.c: Likewise. * tree-data-ref.h: Likewise. * tree-dfa.c: Likewise. * tree-dump.c: Likewise. * tree-dump.h: Likewise. * tree-eh.c: Likewise. * tree-flow-inline.h: Likewise. * tree-flow.h: Likewise. * tree-if-conv.c: Likewise. * tree-inline.c: Likewise. * tree-into-ssa.c: Likewise. * tree-loop-distribution.c: Likewise. * tree-loop-linear.c: Likewise. * tree-mudflap.c: Likewise. * tree-nested.c: Likewise. * tree-nomudflap.c: Likewise. * tree-nrv.c: Likewise. * tree-object-size.c: Likewise. * tree-optimize.c: Likewise. * tree-outof-ssa.c: Likewise. * tree-parloops.c: Likewise. * tree-pass.h: Likewise. * tree-phinodes.c: Likewise. * tree-predcom.c: Likewise. * tree-pretty-print.c: Likewise. * tree-profile.c: Likewise. * tree-scalar-evolution.c: Likewise. * tree-ssa-address.c: Likewise. * tree-ssa-alias.c: Likewise. * tree-ssa-ccp.c: Likewise. * tree-ssa-coalesce.c: Likewise. * tree-ssa-copy.c: Likewise. * tree-ssa-copyrename.c: Likewise. * tree-ssa-dce.c: Likewise. * tree-ssa-dom.c: Likewise. * tree-ssa-dse.c: Likewise. * tree-ssa-forwprop.c: Likewise. * tree-ssa-ifcombine.c: Likewise. * tree-ssa-live.c: Likewise. * tree-ssa-live.h: Likewise. * tree-ssa-loop-ch.c: Likewise. * tree-ssa-loop-im.c: Likewise. * tree-ssa-loop-ivcanon.c: Likewise. * tree-ssa-loop-ivopts.c: Likewise. * tree-ssa-loop-manip.c: Likewise. * tree-ssa-loop-niter.c: Likewise. * tree-ssa-loop-prefetch.c: Likewise. * tree-ssa-loop-unswitch.c: Likewise. * tree-ssa-loop.c: Likewise. * tree-ssa-math-opts.c: Likewise. * tree-ssa-operands.c: Likewise. * tree-ssa-operands.h: Likewise. * tree-ssa-phiopt.c: Likewise. * tree-ssa-phiprop.c: Likewise. * tree-ssa-pre.c: Likewise. * tree-ssa-propagate.c: Likewise. * tree-ssa-reassoc.c: Likewise. * tree-ssa-sccvn.c: Likewise. * tree-ssa-sink.c: Likewise. * tree-ssa-structalias.c: Likewise. * tree-ssa-ter.c: Likewise. * tree-ssa-threadedge.c: Likewise. * tree-ssa-threadupdate.c: Likewise. * tree-ssa-uncprop.c: Likewise. * tree-ssa.c: Likewise. * tree-ssanames.c: Likewise. * tree-switch-conversion.c: Likewise. * tree-tailcall.c: Likewise. * tree-vect-data-refs.c: Likewise. * tree-vect-generic.c: Likewise. * tree-vect-loop-manip.c: Likewise. * tree-vect-loop.c: Likewise. * tree-vect-patterns.c: Likewise. * tree-vect-slp.c: Likewise. * tree-vect-stmts.c: Likewise. * tree-vectorizer.c: Likewise. * tree-vectorizer.h: Likewise. * tree-vrp.c: Likewise. * tree.c: Likewise. * tree.def: Likewise. * tree.h: Likewise. * treestruct.def: Likewise. * unwind-compat.c: Likewise. * unwind-dw2-fde-glibc.c: Likewise. * unwind-dw2.c: Likewise. * value-prof.c: Likewise. * value-prof.h: Likewise. * var-tracking.c: Likewise. * varasm.c: Likewise. * varpool.c: Likewise. * vec.c: Likewise. * vec.h: Likewise. * vmsdbgout.c: Likewise. * web.c: Likewise. * xcoffout.c: Likewise. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154645 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 576 ++++++++++++++++++++++---------------------- 1 file changed, 288 insertions(+), 288 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 2cae2ceff45..087ba798830 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -19,9 +19,9 @@ You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see . */ -/* - Description: - +/* + Description: + This pass analyzes the evolution of scalar variables in loop structures. The algorithm is based on the SSA representation, and on the loop hierarchy tree. This algorithm is not based on @@ -42,15 +42,15 @@ along with GCC; see the file COPYING3. If not see are fully instantiated before their use because symbolic names can hide some difficult cases such as self-references described later (see the Fibonacci example). - + A short sketch of the algorithm is: - + Given a scalar variable to be analyzed, follow the SSA edge to its definition: - + - When the definition is a GIMPLE_ASSIGN: if the right hand side (RHS) of the definition cannot be statically analyzed, the answer - of the analyzer is: "don't know". + of the analyzer is: "don't know". Otherwise, for all the variables that are not yet analyzed in the RHS, try to determine their evolution, and finally try to evaluate the operation of the RHS that gives the evolution @@ -72,16 +72,16 @@ along with GCC; see the file COPYING3. If not see symbolic chrec {initial_condition, +, symbolic_stride}_loop. Examples: - + Example 1: Illustration of the basic algorithm. - + | a = 3 | loop_1 | b = phi (a, c) | c = b + 1 | if (c > 10) exit_loop | endloop - + Suppose that we want to know the number of iterations of the loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We ask the scalar evolution analyzer two questions: what's the @@ -112,22 +112,22 @@ along with GCC; see the file COPYING3. If not see created a variable that is implicitly defined, "x" or just "_1", and all the other analyzed scalars of the loop are defined in function of this variable: - + a -> 3 b -> {3, +, 1}_1 c -> {4, +, 1}_1 - - or in terms of a C program: - + + or in terms of a C program: + | a = 3 | for (x = 0; x <= 7; x++) | { | b = x + 3 | c = x + 4 | } - + Example 2a: Illustration of the algorithm on nested loops. - + | loop_1 | a = phi (1, b) | c = a + 2 @@ -136,22 +136,22 @@ along with GCC; see the file COPYING3. If not see | d = b + 3 | endloop | endloop - + For analyzing the scalar evolution of "a", the algorithm follows the SSA edge into the loop's body: "a -> b". "b" is an inner - loop-phi-node, and its analysis as in Example 1, gives: - + loop-phi-node, and its analysis as in Example 1, gives: + b -> {c, +, 3}_2 d -> {c + 3, +, 3}_2 - + Following the SSA edge for the initial condition, we end on "c = a + 2", and then on the starting loop-phi-node "a". From this point, the loop stride is computed: back on "c = a + 2" we get a "+2" in the loop_1, then on the loop-phi-node "b" we compute the overall effect of the inner loop that is "b = c + 30", and we get a "+30" in the loop_1. That means that the overall stride in loop_1 is - equal to "+32", and the result is: - + equal to "+32", and the result is: + a -> {1, +, 32}_1 c -> {3, +, 32}_1 @@ -179,65 +179,65 @@ along with GCC; see the file COPYING3. If not see The result of this call is {{0, +, 1}_1, +, 1}_2. Example 3: Higher degree polynomials. - + | loop_1 | a = phi (2, b) | c = phi (5, d) | b = a + 1 | d = c + a | endloop - + a -> {2, +, 1}_1 b -> {3, +, 1}_1 c -> {5, +, a}_1 d -> {5 + a, +, a}_1 - + instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1 instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1 - + Example 4: Lucas, Fibonacci, or mixers in general. - + | loop_1 | a = phi (1, b) | c = phi (3, d) | b = c | d = c + a | endloop - + a -> (1, c)_1 c -> {3, +, a}_1 - + The syntax "(1, c)_1" stands for a PEELED_CHREC that has the following semantics: during the first iteration of the loop_1, the variable contains the value 1, and then it contains the value "c". Note that this syntax is close to the syntax of the loop-phi-node: "a -> (1, c)_1" vs. "a = phi (1, c)". - + The symbolic chrec representation contains all the semantics of the original code. What is more difficult is to use this information. - + Example 5: Flip-flops, or exchangers. - + | loop_1 | a = phi (1, b) | c = phi (3, d) | b = c | d = a | endloop - + a -> (1, c)_1 c -> (3, a)_1 - + Based on these symbolic chrecs, it is possible to refine this - information into the more precise PERIODIC_CHRECs: - + information into the more precise PERIODIC_CHRECs: + a -> |1, 3|_1 c -> |3, 1|_1 - + This transformation is not yet implemented. - + Further readings: - + You can find a more detailed description of the algorithm in: http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that @@ -245,7 +245,7 @@ along with GCC; see the file COPYING3. If not see algorithm have changed. I'm working on a research report that updates the description of the algorithms to reflect the design choices used in this implementation. - + A set of slides show a high level overview of the algorithm and run an example through the scalar evolution analyzer: http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf @@ -316,7 +316,7 @@ static inline struct scev_info_str * new_scev_info_str (basic_block instantiated_below, tree var) { struct scev_info_str *res; - + res = GGC_NEW (struct scev_info_str); res->var = var; res->chrec = chrec_not_analyzed_yet; @@ -377,7 +377,7 @@ find_var_scev_info (basic_block instantiated_below, tree var) /* Return true when CHREC contains symbolic names defined in LOOP_NB. */ -bool +bool chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb) { int i, n; @@ -413,7 +413,7 @@ chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb) n = TREE_OPERAND_LENGTH (chrec); for (i = 0; i < n; i++) - if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i), + if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i), loop_nb)) return true; return false; @@ -435,37 +435,37 @@ loop_phi_node_p (gimple phi) In general, in the case of multivariate evolutions we want to get the evolution in different loops. LOOP specifies the level for which to get the evolution. - + Example: - + | for (j = 0; j < 100; j++) | { | for (k = 0; k < 100; k++) | { - | i = k + j; - Here the value of i is a function of j, k. + | i = k + j; - Here the value of i is a function of j, k. | } - | ... = i - Here the value of i is a function of j. + | ... = i - Here the value of i is a function of j. | } - | ... = i - Here the value of i is a scalar. - - Example: - + | ... = i - Here the value of i is a scalar. + + Example: + | i_0 = ... | loop_1 10 times | i_1 = phi (i_0, i_2) | i_2 = i_1 + 2 | endloop - + This loop has the same effect as: LOOP_1 has the same effect as: - + | i_1 = i_0 + 20 - - The overall effect of the loop, "i_0 + 20" in the previous example, - is obtained by passing in the parameters: LOOP = 1, + + The overall effect of the loop, "i_0 + 20" in the previous example, + is obtained by passing in the parameters: LOOP = 1, EVOLUTION_FN = {i_0, +, 2}_1. */ - + tree compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) { @@ -503,11 +503,11 @@ compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) else return evolution_fn; } - + /* If the evolution function is an invariant, there is nothing to do. */ else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val) return evolution_fn; - + else return chrec_dont_know; } @@ -521,14 +521,14 @@ chrec_is_positive (tree chrec, bool *value) { bool value0, value1, value2; tree end_value, nb_iter; - + switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: if (!chrec_is_positive (CHREC_LEFT (chrec), &value0) || !chrec_is_positive (CHREC_RIGHT (chrec), &value1)) return false; - + /* FIXME -- overflows. */ if (value0 == value1) { @@ -555,17 +555,17 @@ chrec_is_positive (tree chrec, bool *value) #endif end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter); - + if (!chrec_is_positive (end_value, &value2)) return false; - + *value = value0; return value0 == value1; - + case INTEGER_CST: *value = (tree_int_cst_sgn (chrec) == 1); return true; - + default: return false; } @@ -577,12 +577,12 @@ static void set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec) { tree *scalar_info; - + if (TREE_CODE (scalar) != SSA_NAME) return; scalar_info = find_var_scev_info (instantiated_below, scalar); - + if (dump_file) { if (dump_flags & TDF_DETAILS) @@ -599,7 +599,7 @@ set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec) if (dump_flags & TDF_STATS) nb_set_scev++; } - + *scalar_info = chrec; } @@ -610,7 +610,7 @@ static tree get_scalar_evolution (basic_block instantiated_below, tree scalar) { tree res; - + if (dump_file) { if (dump_flags & TDF_DETAILS) @@ -623,7 +623,7 @@ get_scalar_evolution (basic_block instantiated_below, tree scalar) if (dump_flags & TDF_STATS) nb_get_scev++; } - + switch (TREE_CODE (scalar)) { case SSA_NAME: @@ -640,14 +640,14 @@ get_scalar_evolution (basic_block instantiated_below, tree scalar) res = chrec_not_analyzed_yet; break; } - + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, " (scalar_evolution = "); print_generic_expr (dump_file, res, 0); fprintf (dump_file, "))\n"); } - + return res; } @@ -655,8 +655,8 @@ get_scalar_evolution (basic_block instantiated_below, tree scalar) function for an assignment of the form "a = b + c", where "a" and "b" are on the strongly connected component. CHREC_BEFORE is the information that we already have collected up to this point. - TO_ADD is the evolution of "c". - + TO_ADD is the evolution of "c". + When CHREC_BEFORE has an evolution part in LOOP_NB, add to this evolution the expression TO_ADD, otherwise construct an evolution part for this loop. */ @@ -678,7 +678,7 @@ add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, unsigned var; type = chrec_type (chrec_before); - + /* When there is no evolution part in this loop, build it. */ if (chloop != loop) { @@ -712,7 +712,7 @@ add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, return build_polynomial_chrec (CHREC_VARIABLE (chrec_before), left, right); } - + default: /* These nodes do not depend on a loop. */ if (chrec_before == chrec_dont_know) @@ -725,155 +725,155 @@ add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, } /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension - of LOOP_NB. - + of LOOP_NB. + Description (provided for completeness, for those who read code in a plane, and for my poor 62 bytes brain that would have forgotten all this in the next two or three months): - + The algorithm of translation of programs from the SSA representation into the chrecs syntax is based on a pattern matching. After having reconstructed the overall tree expression for a loop, there are only two cases that can arise: - + 1. a = loop-phi (init, a + expr) 2. a = loop-phi (init, expr) - + where EXPR is either a scalar constant with respect to the analyzed loop (this is a degree 0 polynomial), or an expression containing other loop-phi definitions (these are higher degree polynomials). - + Examples: - - 1. + + 1. | init = ... | loop_1 | a = phi (init, a + 5) | endloop - - 2. + + 2. | inita = ... | initb = ... | loop_1 | a = phi (inita, 2 * b + 3) | b = phi (initb, b + 1) | endloop - - For the first case, the semantics of the SSA representation is: - + + For the first case, the semantics of the SSA representation is: + | a (x) = init + \sum_{j = 0}^{x - 1} expr (j) - + that is, there is a loop index "x" that determines the scalar value of the variable during the loop execution. During the first iteration, the value is that of the initial condition INIT, while during the subsequent iterations, it is the sum of the initial condition with the sum of all the values of EXPR from the initial - iteration to the before last considered iteration. - + iteration to the before last considered iteration. + For the second case, the semantics of the SSA program is: - + | a (x) = init, if x = 0; | expr (x - 1), otherwise. - + The second case corresponds to the PEELED_CHREC, whose syntax is - close to the syntax of a loop-phi-node: - + close to the syntax of a loop-phi-node: + | phi (init, expr) vs. (init, expr)_x - + The proof of the translation algorithm for the first case is a - proof by structural induction based on the degree of EXPR. - + proof by structural induction based on the degree of EXPR. + Degree 0: When EXPR is a constant with respect to the analyzed loop, or in other words when EXPR is a polynomial of degree 0, the evolution of the variable A in the loop is an affine function with an initial condition INIT, and a step EXPR. In order to show this, we start from the semantics of the SSA representation: - + f (x) = init + \sum_{j = 0}^{x - 1} expr (j) - + and since "expr (j)" is a constant with respect to "j", - - f (x) = init + x * expr - + + f (x) = init + x * expr + Finally, based on the semantics of the pure sum chrecs, by identification we get the corresponding chrecs syntax: - - f (x) = init * \binom{x}{0} + expr * \binom{x}{1} + + f (x) = init * \binom{x}{0} + expr * \binom{x}{1} f (x) -> {init, +, expr}_x - + Higher degree: Suppose that EXPR is a polynomial of degree N with respect to the analyzed loop_x for which we have already determined that it is written under the chrecs syntax: - + | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x) - + We start from the semantics of the SSA program: - + | f (x) = init + \sum_{j = 0}^{x - 1} expr (j) | - | f (x) = init + \sum_{j = 0}^{x - 1} + | f (x) = init + \sum_{j = 0}^{x - 1} | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1}) | - | f (x) = init + \sum_{j = 0}^{x - 1} - | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k}) + | f (x) = init + \sum_{j = 0}^{x - 1} + | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k}) | - | f (x) = init + \sum_{k = 0}^{n - 1} - | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k}) + | f (x) = init + \sum_{k = 0}^{n - 1} + | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k}) | - | f (x) = init + \sum_{k = 0}^{n - 1} - | (b_k * \binom{x}{k + 1}) + | f (x) = init + \sum_{k = 0}^{n - 1} + | (b_k * \binom{x}{k + 1}) | - | f (x) = init + b_0 * \binom{x}{1} + ... - | + b_{n-1} * \binom{x}{n} + | f (x) = init + b_0 * \binom{x}{1} + ... + | + b_{n-1} * \binom{x}{n} | - | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ... - | + b_{n-1} * \binom{x}{n} + | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ... + | + b_{n-1} * \binom{x}{n} | - + And finally from the definition of the chrecs syntax, we identify: - | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x - + | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x + This shows the mechanism that stands behind the add_to_evolution function. An important point is that the use of symbolic parameters avoids the need of an analysis schedule. - + Example: - + | inita = ... | initb = ... - | loop_1 + | loop_1 | a = phi (inita, a + 2 + b) | b = phi (initb, b + 1) | endloop - + When analyzing "a", the algorithm keeps "b" symbolically: - + | a -> {inita, +, 2 + b}_1 - + Then, after instantiation, the analyzer ends on the evolution: - + | a -> {inita, +, 2 + initb, +, 1}_1 */ -static tree +static tree add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, tree to_add, gimple at_stmt) { tree type = chrec_type (to_add); tree res = NULL_TREE; - + if (to_add == NULL_TREE) return chrec_before; - + /* TO_ADD is either a scalar, or a parameter. TO_ADD is not instantiated at this point. */ if (TREE_CODE (to_add) == POLYNOMIAL_CHREC) /* This should not happen. */ return chrec_dont_know; - + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "(add_to_evolution \n"); @@ -905,7 +905,7 @@ add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, /* Helper function. */ static inline tree -set_nb_iterations_in_loop (struct loop *loop, +set_nb_iterations_in_loop (struct loop *loop, tree res) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -914,7 +914,7 @@ set_nb_iterations_in_loop (struct loop *loop, print_generic_expr (dump_file, res, 0); fprintf (dump_file, "))\n"); } - + loop->nb_iterations = res; return res; } @@ -929,50 +929,50 @@ set_nb_iterations_in_loop (struct loop *loop, guards the exit edge. If the expression is too difficult to analyze, then give up. */ -gimple +gimple get_loop_exit_condition (const struct loop *loop) { gimple res = NULL; edge exit_edge = single_exit (loop); - + if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "(get_loop_exit_condition \n "); - + if (exit_edge) { gimple stmt; - + stmt = last_stmt (exit_edge->src); if (gimple_code (stmt) == GIMPLE_COND) res = stmt; } - + if (dump_file && (dump_flags & TDF_DETAILS)) { print_gimple_stmt (dump_file, res, 0, 0); fprintf (dump_file, ")\n"); } - + return res; } /* Recursively determine and enqueue the exit conditions for a loop. */ -static void -get_exit_conditions_rec (struct loop *loop, +static void +get_exit_conditions_rec (struct loop *loop, VEC(gimple,heap) **exit_conditions) { if (!loop) return; - + /* Recurse on the inner loops, then on the next (sibling) loops. */ get_exit_conditions_rec (loop->inner, exit_conditions); get_exit_conditions_rec (loop->next, exit_conditions); - + if (single_exit (loop)) { gimple loop_condition = get_loop_exit_condition (loop); - + if (loop_condition) VEC_safe_push (gimple, heap, *exit_conditions, loop_condition); } @@ -985,7 +985,7 @@ static void select_loops_exit_conditions (VEC(gimple,heap) **exit_conditions) { struct loop *function_body = current_loops->tree_root; - + get_exit_conditions_rec (function_body->inner, exit_conditions); } @@ -1020,34 +1020,34 @@ follow_ssa_edge_binary (struct loop *loop, gimple at_stmt, { if (TREE_CODE (rhs1) == SSA_NAME) { - /* Match an assignment under the form: + /* Match an assignment under the form: "a = b + c". */ - + /* We want only assignments of form "name + name" contribute to LIMIT, as the other cases do not necessarily contribute to the complexity of the expression. */ limit++; evol = *evolution_of_loop; - res = follow_ssa_edge + res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit); - + if (res == t_true) - *evolution_of_loop = add_to_evolution - (loop->num, - chrec_convert (type, evol, at_stmt), + *evolution_of_loop = add_to_evolution + (loop->num, + chrec_convert (type, evol, at_stmt), code, rhs1, at_stmt); - + else if (res == t_false) { - res = follow_ssa_edge - (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, evolution_of_loop, limit); - + if (res == t_true) - *evolution_of_loop = add_to_evolution - (loop->num, - chrec_convert (type, *evolution_of_loop, at_stmt), + *evolution_of_loop = add_to_evolution + (loop->num, + chrec_convert (type, *evolution_of_loop, at_stmt), code, rhs0, at_stmt); else if (res == t_dont_know) @@ -1057,16 +1057,16 @@ follow_ssa_edge_binary (struct loop *loop, gimple at_stmt, else if (res == t_dont_know) *evolution_of_loop = chrec_dont_know; } - + else { - /* Match an assignment under the form: + /* Match an assignment under the form: "a = b + ...". */ - res = follow_ssa_edge - (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, evolution_of_loop, limit); if (res == t_true) - *evolution_of_loop = add_to_evolution + *evolution_of_loop = add_to_evolution (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt), code, rhs1, at_stmt); @@ -1075,16 +1075,16 @@ follow_ssa_edge_binary (struct loop *loop, gimple at_stmt, *evolution_of_loop = chrec_dont_know; } } - + else if (TREE_CODE (rhs1) == SSA_NAME) { - /* Match an assignment under the form: + /* Match an assignment under the form: "a = ... + c". */ - res = follow_ssa_edge - (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, evolution_of_loop, limit); if (res == t_true) - *evolution_of_loop = add_to_evolution + *evolution_of_loop = add_to_evolution (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt), code, rhs0, at_stmt); @@ -1094,17 +1094,17 @@ follow_ssa_edge_binary (struct loop *loop, gimple at_stmt, } else - /* Otherwise, match an assignment under the form: + /* Otherwise, match an assignment under the form: "a = ... + ...". */ /* And there is nothing to do. */ res = t_false; break; - + case MINUS_EXPR: /* This case is under the form "opnd0 = rhs0 - rhs1". */ if (TREE_CODE (rhs0) == SSA_NAME) { - /* Match an assignment under the form: + /* Match an assignment under the form: "a = b - ...". */ /* We want only assignments of form "name - name" contribute to @@ -1113,10 +1113,10 @@ follow_ssa_edge_binary (struct loop *loop, gimple at_stmt, if (TREE_CODE (rhs1) == SSA_NAME) limit++; - res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, + res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, evolution_of_loop, limit); if (res == t_true) - *evolution_of_loop = add_to_evolution + *evolution_of_loop = add_to_evolution (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt), MINUS_EXPR, rhs1, at_stmt); @@ -1124,7 +1124,7 @@ follow_ssa_edge_binary (struct loop *loop, gimple at_stmt, *evolution_of_loop = chrec_dont_know; } else - /* Otherwise, match an assignment under the form: + /* Otherwise, match an assignment under the form: "a = ... - ...". */ /* And there is nothing to do. */ res = t_false; @@ -1136,12 +1136,12 @@ follow_ssa_edge_binary (struct loop *loop, gimple at_stmt, return res; } - + /* Follow the ssa edge into the expression EXPR. Return true if the strongly connected component has been found. */ static t_bool -follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr, +follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr, gimple halting_phi, tree *evolution_of_loop, int limit) { enum tree_code code = TREE_CODE (expr); @@ -1149,10 +1149,10 @@ follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr, t_bool res; /* The EXPR is one of the following cases: - - an SSA_NAME, + - an SSA_NAME, - an INTEGER_CST, - - a PLUS_EXPR, - - a POINTER_PLUS_EXPR, + - a PLUS_EXPR, + - a POINTER_PLUS_EXPR, - a MINUS_EXPR, - an ASSERT_EXPR, - other cases are not yet handled. */ @@ -1173,7 +1173,7 @@ follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr, case SSA_NAME: /* This assignment is under the form: "a_1 = b_2". */ - res = follow_ssa_edge + res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit); break; @@ -1273,8 +1273,8 @@ backedge_phi_arg_p (gimple phi, int i) static inline t_bool follow_ssa_edge_in_condition_phi_branch (int i, - struct loop *loop, - gimple condition_phi, + struct loop *loop, + gimple condition_phi, gimple halting_phi, tree *evolution_of_branch, tree init_cond, int limit) @@ -1290,15 +1290,15 @@ follow_ssa_edge_in_condition_phi_branch (int i, if (TREE_CODE (branch) == SSA_NAME) { *evolution_of_branch = init_cond; - return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi, + return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi, evolution_of_branch, limit); } - /* This case occurs when one of the condition branches sets + /* This case occurs when one of the condition branches sets the variable to a constant: i.e. a phi-node like - "a_2 = PHI ;". - - FIXME: This case have to be refined correctly: + "a_2 = PHI ;". + + 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 t_false; @@ -1309,8 +1309,8 @@ follow_ssa_edge_in_condition_phi_branch (int i, static t_bool follow_ssa_edge_in_condition_phi (struct loop *loop, - gimple condition_phi, - gimple halting_phi, + gimple condition_phi, + gimple halting_phi, tree *evolution_of_loop, int limit) { int i, n; @@ -1345,7 +1345,7 @@ follow_ssa_edge_in_condition_phi (struct loop *loop, *evolution_of_loop = chrec_merge (*evolution_of_loop, evolution_of_branch); } - + return t_true; } @@ -1356,7 +1356,7 @@ follow_ssa_edge_in_condition_phi (struct loop *loop, static t_bool follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, - gimple loop_phi_node, + gimple loop_phi_node, gimple halting_phi, tree *evolution_of_loop, int limit) { @@ -1406,16 +1406,16 @@ follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi, tree *evolution_of_loop, int limit) { struct loop *def_loop; - + if (gimple_nop_p (def)) 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); - + switch (gimple_code (def)) { case GIMPLE_PHI: @@ -1424,7 +1424,7 @@ follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi, record their evolutions. Finally, merge the collected information and set the approximation to the main variable. */ - return follow_ssa_edge_in_condition_phi + return follow_ssa_edge_in_condition_phi (loop, def, halting_phi, evolution_of_loop, limit); /* When the analyzed phi is the halting_phi, the @@ -1432,25 +1432,25 @@ follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi, the halting_phi to itself in the loop. */ if (def == halting_phi) 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 t_false; - + /* Inner loop. */ if (flow_loop_nested_p (loop, def_loop)) - return follow_ssa_edge_inner_loop_phi + return follow_ssa_edge_inner_loop_phi (loop, def, halting_phi, evolution_of_loop, limit + 1); /* Outer loop. */ return t_false; case GIMPLE_ASSIGN: - return follow_ssa_edge_in_rhs (loop, def, halting_phi, + return follow_ssa_edge_in_rhs (loop, def, halting_phi, evolution_of_loop, limit); - + default: /* At this level of abstraction, the program is just a set of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no @@ -1465,14 +1465,14 @@ follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi, function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */ static tree -analyze_evolution_in_loop (gimple loop_phi_node, +analyze_evolution_in_loop (gimple loop_phi_node, tree init_cond) { int i, n = gimple_phi_num_args (loop_phi_node); tree evolution_function = chrec_not_analyzed_yet; struct loop *loop = loop_containing_stmt (loop_phi_node); basic_block bb; - + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "(analyze_evolution_in_loop \n"); @@ -1480,7 +1480,7 @@ analyze_evolution_in_loop (gimple loop_phi_node, print_gimple_stmt (dump_file, loop_phi_node, 0, 0); fprintf (dump_file, ")\n"); } - + for (i = 0; i < n; i++) { tree arg = PHI_ARG_DEF (loop_phi_node, i); @@ -1519,23 +1519,23 @@ analyze_evolution_in_loop (gimple loop_phi_node, loop_phi_node by following the ssa edges, the evolution is represented by a peeled chrec, i.e. the first iteration, EV_FN has the value INIT_COND, then - all the other iterations it has the value of ARG. + all the other iterations it has the value of ARG. For the moment, PEELED_CHREC nodes are not built. */ if (res != t_true) ev_fn = chrec_dont_know; - + /* When there are multiple back edges of the loop (which in fact never happens currently, but nevertheless), merge their evolutions. */ evolution_function = chrec_merge (evolution_function, ev_fn); } - + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, " (evolution_function = "); print_generic_expr (dump_file, evolution_function, 0); fprintf (dump_file, "))\n"); } - + return evolution_function; } @@ -1546,13 +1546,13 @@ analyze_evolution_in_loop (gimple loop_phi_node, This analyzer does not analyze the evolution outside the current loop, and leaves this task to the on-demand tree reconstructor. */ -static tree +static tree analyze_initial_condition (gimple loop_phi_node) { int i, n; tree init_cond = chrec_not_analyzed_yet; struct loop *loop = loop_containing_stmt (loop_phi_node); - + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "(analyze_initial_condition \n"); @@ -1560,13 +1560,13 @@ analyze_initial_condition (gimple loop_phi_node) print_gimple_stmt (dump_file, loop_phi_node, 0, 0); fprintf (dump_file, ")\n"); } - + n = gimple_phi_num_args (loop_phi_node); for (i = 0; i < n; i++) { tree branch = PHI_ARG_DEF (loop_phi_node, i); basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src; - + /* When the branch is oriented to the loop's body, it does not contribute to the initial condition. */ if (flow_bb_inside_loop_p (loop, bb)) @@ -1611,19 +1611,19 @@ analyze_initial_condition (gimple loop_phi_node) print_generic_expr (dump_file, init_cond, 0); fprintf (dump_file, "))\n"); } - + return init_cond; } /* Analyze the scalar evolution for LOOP_PHI_NODE. */ -static tree +static tree interpret_loop_phi (struct loop *loop, gimple loop_phi_node) { tree res; struct loop *phi_loop = loop_containing_stmt (loop_phi_node); tree init_cond; - + if (phi_loop != loop) { struct loop *subloop; @@ -1654,11 +1654,11 @@ interpret_condition_phi (struct loop *loop, gimple condition_phi) { int i, n = gimple_phi_num_args (condition_phi); tree res = chrec_not_analyzed_yet; - + for (i = 0; i < n; i++) { tree branch_chrec; - + if (backedge_phi_arg_p (condition_phi, i)) { res = chrec_dont_know; @@ -1667,7 +1667,7 @@ interpret_condition_phi (struct loop *loop, gimple condition_phi) branch_chrec = analyze_scalar_evolution (loop, PHI_ARG_DEF (condition_phi, i)); - + res = chrec_merge (res, branch_chrec); } @@ -1723,7 +1723,7 @@ interpret_rhs_expr (struct loop *loop, gimple at_stmt, chrec2 = chrec_convert (type, chrec2, at_stmt); res = chrec_fold_plus (type, chrec1, chrec2); break; - + case MINUS_EXPR: chrec1 = analyze_scalar_evolution (loop, rhs1); chrec2 = analyze_scalar_evolution (loop, rhs2); @@ -1756,17 +1756,17 @@ interpret_rhs_expr (struct loop *loop, gimple at_stmt, chrec2 = chrec_convert (type, chrec2, at_stmt); res = chrec_fold_multiply (type, chrec1, chrec2); break; - + CASE_CONVERT: chrec1 = analyze_scalar_evolution (loop, rhs1); res = chrec_convert (type, chrec1, at_stmt); break; - + default: res = chrec_dont_know; break; } - + return res; } @@ -1805,7 +1805,7 @@ interpret_gimple_assign (struct loop *loop, gimple stmt) -/* This section contains all the entry points: +/* This section contains all the entry points: - number_of_iterations_in_loop, - analyze_scalar_evolution, - instantiate_parameters. @@ -1814,9 +1814,9 @@ interpret_gimple_assign (struct loop *loop, gimple stmt) /* Compute and return the evolution function in WRTO_LOOP, the nearest common ancestor of DEF_LOOP and USE_LOOP. */ -static tree -compute_scalar_evolution_in_loop (struct loop *wrto_loop, - struct loop *def_loop, +static tree +compute_scalar_evolution_in_loop (struct loop *wrto_loop, + struct loop *def_loop, tree ev) { tree res; @@ -1860,7 +1860,7 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) if (res != chrec_not_analyzed_yet) { if (loop != bb->loop_father) - res = compute_scalar_evolution_in_loop + res = compute_scalar_evolution_in_loop (find_common_loop (loop, bb->loop_father), bb->loop_father, res); goto set_and_end; @@ -1906,18 +1906,18 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) /* Analyzes and returns the scalar evolution of the ssa_name VAR in LOOP. LOOP is the loop in which the variable is used. - + Example of use: having a pointer VAR to a SSA_NAME node, STMT a pointer to the statement that uses this variable, in order to determine the evolution function of the variable, use the following calls: - + loop_p loop = loop_containing_stmt (stmt); tree chrec_with_symbols = analyze_scalar_evolution (loop, var); tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols); */ -tree +tree analyze_scalar_evolution (struct loop *loop, tree var) { tree res; @@ -1945,8 +1945,8 @@ analyze_scalar_evolution (struct loop *loop, tree var) FOLDED_CASTS is set to true if resolve_mixers used chrec_convert_aggressive (TODO -- not really, we are way too conservative - at the moment in order to keep things simple). - + at the moment in order to keep things simple). + To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following example: @@ -1997,7 +1997,7 @@ analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop, bool val = false; tree ev = version, tmp; - /* We cannot just do + /* We cannot just do tmp = analyze_scalar_evolution (use_loop, version); ev = resolve_mixers (wrto_loop, tmp); @@ -2048,7 +2048,7 @@ get_instantiated_value (htab_t cache, basic_block instantiated_below, tree version) { struct scev_info_str *info, pattern; - + pattern.var = version; pattern.instantiated_below = instantiated_below; info = (struct scev_info_str *) htab_find (cache, &pattern); @@ -2068,7 +2068,7 @@ set_instantiated_value (htab_t cache, basic_block instantiated_below, { struct scev_info_str *info, pattern; PTR *slot; - + pattern.var = version; pattern.instantiated_below = instantiated_below; slot = htab_find_slot (cache, &pattern, INSERT); @@ -2636,7 +2636,7 @@ instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop, print_generic_expr (dump_file, chrec, 0); fprintf (dump_file, ")\n"); } - + res = instantiate_scev_r (instantiate_below, evolution_loop, chrec, false, cache, 0); @@ -2648,7 +2648,7 @@ instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop, } htab_delete (cache); - + return res; } @@ -2667,27 +2667,27 @@ resolve_mixers (struct loop *loop, tree chrec) return ret; } -/* Entry point for the analysis of the number of iterations pass. +/* Entry point for the analysis of the number of iterations pass. This function tries to safely approximate the number of iterations the loop will run. When this property is not decidable at compile time, the result is chrec_dont_know. Otherwise the result is a scalar or a symbolic parameter. - + Example of analysis: suppose that the loop has an exit condition: - + "if (b > 49) goto end_loop;" - + and that in a previous analysis we have determined that the variable 'b' has an evolution function: - - "EF = {23, +, 5}_2". - + + "EF = {23, +, 5}_2". + When we evaluate the function at the point 5, i.e. the value of the variable 'b' after 5 iterations in the loop, we have EF (5) = 48, and EF (6) = 53. In this case the value of 'b' on exit is '53' and the loop body has been executed 6 times. */ -tree +tree number_of_latch_executions (struct loop *loop) { tree res, type; @@ -2703,7 +2703,7 @@ number_of_latch_executions (struct loop *loop) if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "(number_of_iterations_in_loop\n"); - + exit = single_exit (loop); if (!exit) goto end; @@ -2733,7 +2733,7 @@ end: expression, the caller is responsible for dealing with this the possible overflow. */ -tree +tree number_of_exit_cond_executions (struct loop *loop) { tree ret = number_of_latch_executions (loop); @@ -2754,14 +2754,14 @@ number_of_exit_cond_executions (struct loop *loop) This function computes the number of iterations for all the loops from the EXIT_CONDITIONS array. */ -static void +static void number_of_iterations_for_all_loops (VEC(gimple,heap) **exit_conditions) { unsigned int i; unsigned nb_chrec_dont_know_loops = 0; unsigned nb_static_loops = 0; gimple cond; - + for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++) { tree res = number_of_latch_executions (loop_containing_stmt (cond)); @@ -2770,7 +2770,7 @@ number_of_iterations_for_all_loops (VEC(gimple,heap) **exit_conditions) else nb_static_loops++; } - + if (dump_file) { fprintf (dump_file, "\n(\n"); @@ -2780,7 +2780,7 @@ number_of_iterations_for_all_loops (VEC(gimple,heap) **exit_conditions) fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ()); fprintf (dump_file, "-----------------------------------------\n"); fprintf (dump_file, ")\n\n"); - + print_loops (dump_file, 3); } } @@ -2789,7 +2789,7 @@ number_of_iterations_for_all_loops (VEC(gimple,heap) **exit_conditions) /* Counters for the stats. */ -struct chrec_stats +struct chrec_stats { unsigned nb_chrecs; unsigned nb_affine; @@ -2821,15 +2821,15 @@ dump_chrecs_stats (FILE *file, struct chrec_stats *stats) fprintf (file, "-----------------------------------------\n"); fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine); fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar); - fprintf (file, "%d\tdegree greater than 2 polynomials\n", + fprintf (file, "%d\tdegree greater than 2 polynomials\n", stats->nb_higher_poly); fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know); fprintf (file, "-----------------------------------------\n"); fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs); - fprintf (file, "%d\twith undetermined coefficients\n", + fprintf (file, "%d\twith undetermined coefficients\n", stats->nb_undetermined); fprintf (file, "-----------------------------------------\n"); - fprintf (file, "%d\tchrecs in the scev database\n", + fprintf (file, "%d\tchrecs in the scev database\n", (int) htab_elements (scalar_evolution_info)); fprintf (file, "%d\tsets in the scev database\n", nb_set_scev); fprintf (file, "%d\tgets in the scev database\n", nb_get_scev); @@ -2848,15 +2848,15 @@ gather_chrec_stats (tree chrec, struct chrec_stats *stats) print_generic_expr (dump_file, chrec, 0); fprintf (dump_file, "\n"); } - + stats->nb_chrecs++; - + if (chrec == NULL_TREE) { stats->nb_undetermined++; return; } - + switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: @@ -2878,20 +2878,20 @@ gather_chrec_stats (tree chrec, struct chrec_stats *stats) fprintf (dump_file, " higher_degree_polynomial\n"); stats->nb_higher_poly++; } - + break; default: break; } - + if (chrec_contains_undetermined (chrec)) { if (dump_file && (dump_flags & TDF_STATS)) fprintf (dump_file, " undetermined\n"); stats->nb_undetermined++; } - + if (dump_file && (dump_flags & TDF_STATS)) fprintf (dump_file, ")\n"); } @@ -2899,47 +2899,47 @@ gather_chrec_stats (tree chrec, struct chrec_stats *stats) /* One of the drivers for testing the scalar evolutions analysis. This function analyzes the scalar evolution of all the scalars defined as loop phi nodes in one of the loops from the - EXIT_CONDITIONS array. - + EXIT_CONDITIONS array. + TODO Optimization: A loop is in canonical form if it contains only a single scalar loop phi node. All the other scalars that have an evolution in the loop are rewritten in function of this single index. This allows the parallelization of the loop. */ -static void +static void analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple,heap) **exit_conditions) { unsigned int i; struct chrec_stats stats; gimple cond, phi; gimple_stmt_iterator psi; - + reset_chrecs_counters (&stats); - + for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++) { struct loop *loop; basic_block bb; tree chrec; - + loop = loop_containing_stmt (cond); bb = loop->header; - + for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) { phi = gsi_stmt (psi); if (is_gimple_reg (PHI_RESULT (phi))) { - chrec = instantiate_parameters - (loop, + chrec = instantiate_parameters + (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi))); - + if (dump_file && (dump_flags & TDF_STATS)) gather_chrec_stats (chrec, &stats); } } } - + if (dump_file && (dump_flags & TDF_STATS)) dump_chrecs_stats (dump_file, &stats); } @@ -2959,16 +2959,16 @@ gather_stats_on_scev_database_1 (void **slot, void *stats) /* Classify the chrecs of the whole database. */ -void +void gather_stats_on_scev_database (void) { struct chrec_stats stats; - + if (!dump_file) return; - + reset_chrecs_counters (&stats); - + htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1, &stats); @@ -3007,7 +3007,7 @@ scev_initialize (void) del_scev_info, ggc_calloc, ggc_free); - + initialize_scalar_evolutions_analyzer (); FOR_EACH_LOOP (li, loop, 0) @@ -3039,18 +3039,18 @@ scev_reset (void) (see analyze_scalar_evolution_in_loop for more details on USE_LOOP and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be invariant in LOOP. Otherwise we require it to be an integer constant. - + IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g. because it is computed in signed arithmetics). Consequently, adding an induction variable - + for (i = IV->base; ; i += IV->step) is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is false for the type of the induction variable, or you can prove that i does not wrap by some other argument. Otherwise, this might introduce undefined behavior, and - + for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step)) must be used instead. */ @@ -3109,13 +3109,13 @@ void scev_analysis (void) { VEC(gimple,heap) *exit_conditions; - + exit_conditions = VEC_alloc (gimple, heap, 37); select_loops_exit_conditions (&exit_conditions); if (dump_file && (dump_flags & TDF_STATS)) analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions); - + number_of_iterations_for_all_loops (&exit_conditions); VEC_free (gimple, heap, exit_conditions); } @@ -3178,7 +3178,7 @@ expression_expensive_p (tree expr) /* 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. */ -- cgit v1.2.1 From ce00c15086a5414a3b3b2d49a717f1ceb6945739 Mon Sep 17 00:00:00 2001 From: rguenth Date: Sat, 9 Jan 2010 12:04:17 +0000 Subject: 2010-01-09 Richard Guenther PR middle-end/42512 * tree-scalar-evolution.c (interpret_loop_phi): Make sure the evolution is compatible with the initial condition. * gcc.c-torture/execute/pr42512.c: New testcase. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@155757 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 087ba798830..3ebc54e8556 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -1642,6 +1642,23 @@ interpret_loop_phi (struct loop *loop, gimple loop_phi_node) init_cond = analyze_initial_condition (loop_phi_node); res = analyze_evolution_in_loop (loop_phi_node, init_cond); + /* Verify we maintained the correct initial condition throughout + possible conversions in the SSA chain. */ + if (res != chrec_dont_know) + { + tree new_init = res; + if (CONVERT_EXPR_P (res) + && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC) + new_init = fold_convert (TREE_TYPE (res), + CHREC_LEFT (TREE_OPERAND (res, 0))); + else if (TREE_CODE (res) == POLYNOMIAL_CHREC) + new_init = CHREC_LEFT (res); + STRIP_USELESS_TYPE_CONVERSION (new_init); + gcc_assert (TREE_CODE (new_init) != POLYNOMIAL_CHREC); + if (!operand_equal_p (init_cond, new_init, 0)) + return chrec_dont_know; + } + return res; } -- cgit v1.2.1 From efe339e3ce830410f033049845a704a8487820ef Mon Sep 17 00:00:00 2001 From: spop Date: Thu, 14 Jan 2010 07:38:15 +0000 Subject: Fix PR42732. 2010-01-14 Sebastian Pop PR middle-end/42732 * graphite-clast-to-gimple.c (gloog): Call scev_reset_htab and rename_nb_iterations. * sese.c (rename_variables_in_operand): New. (rename_variables_in_expr): New. (rename_nb_iterations): New. (sese_adjust_liveout_phis): Update the rename_map. * sese.h (rename_nb_iterations): Declared. * tree-scalar-evolution.c (scev_reset_htab): New. (scev_reset): Call scev_reset_htab. * tree-scalar-evolution.h (scev_reset_htab): Declared. * testsuite/gfortran.dg/graphite/pr42732.f: New. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@155881 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 20 +++++++++++++++++--- 1 file changed, 17 insertions(+), 3 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 3ebc54e8556..4d8f85e5047 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -3033,7 +3033,20 @@ scev_initialize (void) } } -/* Cleans up the information cached by the scalar evolutions analysis. */ +/* Cleans up the information cached by the scalar evolutions analysis + in the hash table. */ + +void +scev_reset_htab (void) +{ + if (!scalar_evolution_info) + return; + + htab_empty (scalar_evolution_info); +} + +/* Cleans up the information cached by the scalar evolutions analysis + in the hash table and in the loop->nb_iterations. */ void scev_reset (void) @@ -3041,10 +3054,11 @@ scev_reset (void) loop_iterator li; struct loop *loop; - if (!scalar_evolution_info || !current_loops) + scev_reset_htab (); + + if (!current_loops) return; - htab_empty (scalar_evolution_info); FOR_EACH_LOOP (li, loop, 0) { loop->nb_iterations = NULL_TREE; -- cgit v1.2.1 From 7cf0dbf3e5eee1286c76c26a836622c9c9974736 Mon Sep 17 00:00:00 2001 From: steven Date: Fri, 2 Apr 2010 19:54:46 +0000 Subject: * ada/gcc-interface/Make-lang.in, alias.c, attribs.c, auto-inc-dec.c, basic-block.h, bb-reorder.c, calls.c, c-common.c, cgraph.h, collect2.h, config/alpha/alpha.c, config/alpha/alpha.md, config/alpha/predicates.md, config/arm/arm.md, config/arm/lib1funcs.asm, config/arm/neon-schedgen.ml, config/avr/avr.c, config/avr/avr.md, config/bfin/bfin.c, config/darwin9.h, config/darwin.c, config/darwin.h, config/h8300/h8300.c, config/i386/cpuid.h, config/i386/cygming.h, config/i386/cygwin.h, config/i386/mingw32.h, config/i386/msformat-c.c, config/i386/sol2-10.h, config/i386/xopintrin.h, config/ia64/ia64.c, config/ia64/ia64.md, config/ia64/sync.md, config/mep/mep.c, config/mips/mips.md, config/mn10300/mn10300.c, config/mn10300/mn10300.h, config/pa/pa.c, config/pa/pa.md, config/rs6000/aix.h, config/rs6000/dfp.md, config/rs6000/rs6000-builtin.def, config/rs6000/rs6000-c.c, config/rs6000/vector.md, config/rtems.h, config/rx/rx.md, config/s390/s390.md, config/sol2-c.c, config/sparc/sol2-bi.h, config/sparc/sol2-gas.h, config/sparc/sparc.h, config/sparc/sparc.md, config/sparc/sparc-protos.h, config/spu/spu.c, config/spu/spu-c.c, config/t-darwin, convert.c, c.opt, c-opts.c, cp/Make-lang.in, c-pretty-print.c, c-typeck.c, df-core.c, df-scan.c, diagnostic.c, diagnostic.h, doc/cppopts.texi, doc/cpp.texi, doc/extend.texi, doc/gimple.texi, doc/languages.texi, doc/plugins.texi, doc/rtl.texi, doc/standards.texi, doc/tree-ssa.texi, doc/trouble.texi, dominance.c, fold-const.c, fortran/Make-lang.in, fwprop.c, gcc-plugin.h, gensupport.c, gimple.h, gimple-iterator.c, graphite.c, graphite-clast-to-gimple.c, graphite-clast-to-gimple.h, graphite-dependences.c, graphite-poly.c, graphite-poly.h, graphite-ppl.c, graphite-ppl.h, graphite-scop-detection.c, graphite-sese-to-poly.c, graphite-sese-to-poly.h, ifcvt.c, intl.c, intl.h, ipa.c, ipa-cp.c, ipa-inline.c, ipa-prop.c, ipa-prop.h, ipa-pure-const.c, ipa-reference.c, ipa-type-escape.c, ira-color.c, ira-conflicts.c, ira-lives.c, java/Make-lang.in, lambda-code.c, loop-invariant.c, lto/Make-lang.in, lto-streamer.h, lto-streamer-in.c, objc/Make-lang.in, objcp/Make-lang.in, omp-low.c, optc-gen.awk, opt-functions.awk, opth-gen.awk, params.def, passes.c, postreload-gcse.c, print-tree.c, recog.c, regrename.c, reload.h, rtl.def, sched-int.h, sched-rgn.c, sel-sched-dump.c, sese.c, sese.h, store-motion.c, stor-layout.c, tree-cfgcleanup.c, tree-chrec.c, tree-complex.c, tree-data-ref.c, tree.def, tree-eh.c, tree-flow.h, tree-flow-inline.h, tree.h, tree-loop-distribution.c, tree-outof-ssa.c, tree-parloops.c, tree-pass.h, tree-predcom.c, tree-profile.c, tree-scalar-evolution.c, tree-ssa-address.c, tree-ssa-alias.c, tree-ssa-coalesce.c, tree-ssa-copy.c, tree-ssa-dce.c, tree-ssa-dom.c, tree-ssa-dse.c, tree-ssa-loop-im.c, tree-ssa-loop-ivcanon.c, tree-ssa-loop-manip.c, tree-ssa-math-opts.c, tree-ssa-operands.c, tree-ssa-pre.c, tree-ssa-sccvn.c, tree-ssa-structalias.c, tree-ssa-uncprop.c, tree-tailcall.c, tree-vect-data-refs.c, tree-vect-loop.c, tree-vectorizer.h, tree-vect-slp.c, tree-vrp.c, unwind-dw2-fde-darwin.c, varpool.c: Update copyright years. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@157950 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 4d8f85e5047..054c6435c00 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -1,5 +1,5 @@ /* Scalar evolution detector. - Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 + Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. Contributed by Sebastian Pop -- cgit v1.2.1 From a7a4626828090600459358ca745c4482cf9551a1 Mon Sep 17 00:00:00 2001 From: steven Date: Fri, 21 May 2010 13:53:22 +0000 Subject: gcc/ChangeLog: * tree.h: Include real.h and fixed-value.h as basic datatypes. * dfp.c, convert.c, reload1.c, reginfo.c, tree-flow.h, tree-ssa-threadedge.c, tree-ssanames.c, tree-loop-linear.c, tree-into-ssa.c, tree-vect-generic.c, tree-ssa-structalias.c, tree-ssa-loop-im.c, tree-dump.c, tree-complex.c, tree-ssa-uninit.c, genrecog.c, tree-ssa-threadupdate.c, tree-ssa-loop-niter.c, tree-pretty-print.c, tree-loop-distribution.c, tree-ssa-loop-unswitch.c, c-lex.c, optabs.c, postreload-gcse.c, tree-ssa-loop-manip.c, postreload.c, tree-ssa-loop-ch.c, tree-tailcall.c, tree.c, reload.c, tree-scalar-evolution.c, rtlanal.c, tree-phinodes.c, builtins.c, final.c, genoutput.c, fold-const.c, tree-ssa-dse.c, genautomata.c, tree-ssa-uncprop.c, toplev.c, tree-chrec.c, genemit.c, c-cppbuiltin.c, tree-ssa-sccvn.c, tree-ssa-ccp.c, tree-ssa-loop-ivopts.c, mode-switching.c, tree-call-cdce.c, cse.c, genpeep.c, tree-ssa-math-opts.c, tree-ssa-dom.c, tree-nrv.c, tree-ssa-propagate.c, tree-ssa-alias.c, tree-ssa-sink.c, jump.c, ifcvt.c, dwarf2out.c, expr.c, genattrtab.c, genconditions.c, tree-ssa-loop-ivcanon.c, tree-ssa-loop.c, tree-parloops.c, recog.c, tree-ssa-address.c, lcm.c, tree-eh.c, gimple-pretty-print.c, c-pretty-print.c, print-rtl.c, gcse.c, tree-if-conv.c, tree-data-ref.c, tree-affine.c, gimplify.c, tree-ssa-phiopt.c, implicit-zee.c, expmed.c, tree-dfa.c, emit-rtl.c, store-motion.c, cselib.c, tree-cfgcleanup.c, simplify-rtx.c, tree-ssa-pre.c, genpreds.c, tree-mudflap.c, print-tree.c, tree-ssa-copy.c, tree-ssa-forwprop.c, tree-ssa-dce.c, varasm.c, tree-nested.c, tree-ssa.c, tree-ssa-loop-prefetch.c, rtl.c, tree-inline.c, integrate.c, tree-optimize.c, tree-ssa-phiprop.c, fixed-value.c, combine.c, tree-profile.c, c-common.c, sched-vis.c, tree-cfg.c, passes.c, tree-ssa-reassoc.c, config/alpha/alpha.c, config/frv/frv.c, config/s390/s390.c, config/m32c/m32c.c, config/spu/spu.c, config/sparc/sparc.c, config/mep/mep.c, config/m32r/m32r.c, config/rx/rx.c, config/i386/i386.c, config/sh/sh.c, config/pdp11/pdp11.c, config/avr/avr.c, config/crx/crx.c, config/xtensa/xtensa.c, config/stormy16/stormy16.c, config/fr30/fr30.c, config/lm32/lm32.c, config/moxie/moxie.c, config/m68hc11/m68hc11.c, config/cris/cris.c, config/iq2000/iq2000.c, config/mn10300/mn10300.c, config/ia64/ia64.c, config/m68k/m68k.c, config/rs6000/rs6000.c, config/picochip/picochip.c, config/darwin.c, config/arc/arc.c, config/mcore/mcore.c, config/score/score3.c, config/score/score7.c, config/score/score.c, config/arm/arm.c, config/pa/pa.c, config/mips/mips.c, config/vax/vax.c, config/h8300/h8300.c, config/v850/v850.c, config/mmix/mmix.c, config/bfin/bfin.c: Clean up redundant includes. * Makefile.in: Update accordingly. java/ChangeLog: * typeck.c, decl.c, jcf-parse.c, except.c, expr.c: cp/Changelog: * error.c, tree.c, typeck2.c, cxx-pretty-print.c, mangle.c: Clean up redundant includes. fortran/ChangeLog: * trans-const.c, trans-types.c, trans-intrinsic.c: Clean up redundant includes. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@159663 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 4 ---- 1 file changed, 4 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 054c6435c00..b924ef1a07c 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -260,10 +260,6 @@ along with GCC; see the file COPYING3. If not see #include "tm.h" #include "ggc.h" #include "tree.h" -#include "real.h" - -/* These RTL headers are needed for basic-block.h. */ -#include "rtl.h" #include "basic-block.h" #include "diagnostic.h" #include "tree-flow.h" -- cgit v1.2.1 From ce084dfc1cd60d867d38dbed86a914d82fa908d1 Mon Sep 17 00:00:00 2001 From: jsm28 Date: Fri, 21 May 2010 22:34:26 +0000 Subject: * diagnostic.c: Don't include tm.h, tree.h, tm_p.h, langhooks.h or langhooks-def.h. (diagnostic_initialize): Initialize x_data not last_function. (diagnostic_report_current_function): Move to tree-diagnostic.c. (default_diagnostic_starter): Call diagnostic_report_current_module not diagnostic_report_current_function. (diagnostic_report_diagnostic): Initialize x_data not abstract_origin. (verbatim): Likewise. * diagnostic.h (struct diagnostic_info): Change abstract_origin to x_data. (struct diagnostic_context): Change last_function to x_data. (diagnostic_auxiliary_data): Replace with diagnostic_context_auxiliary_data and diagnostic_info_auxiliary_data. (diagnostic_last_function_changed, diagnostic_set_last_function, diagnostic_report_current_function): Move to tree-diagnostic.h. (print_declaration, dump_generic_node, print_generic_stmt, print_generic_stmt_indented, print_generic_expr, print_generic_decl, debug_c_tree, dump_omp_clauses, print_call_name, debug_generic_expr, debug_generic_stmt, debug_tree_chain, default_tree_printer): Move to tree-pretty-print.h. (debug_gimple_stmt, debug_gimple_seq, print_gimple_seq, print_gimple_stmt, print_gimple_expr, dump_gimple_stmt): Move to gimple-pretty-print.h. * pretty-print.c: Don't include tree.h (pp_base_format): Don't handle %K here. (pp_base_tree_identifier): Move to tree-pretty-print.c. * pretty-print.h (text_info): Change abstract_origin to x_data. (pp_tree_identifier, pp_unsupported_tree, pp_base_tree_identifier): Move to tree-pretty-print.h. * gimple-pretty-print.h, tree-diagnostic.c, tree-diagnostic.h, tree-pretty-print.h: New files. * tree-pretty-print.c: Include tree-pretty-print.h. (percent_K_format): New. Moved from pretty-print.c. (pp_base_tree_identifier): Move from pretty-print.c. * c-objc-common.c: Include tree-pretty-print.h. (c_tree_printer): Handle %K here. * langhooks.c: Include tree-diagnostic.h. (lhd_print_error_function): Use diagnostic_abstract_origin macro. * toplev.c: Include tree-diagnostic.h and tree-pretty-print.h. (default_tree_printer): Handle %K using percent_K_format. (general_init): Use default_tree_diagnostic_starter. * tree.c: Include tree-diagnostic.h and tree-pretty-print.h. (free_lang_data): Use default_tree_diagnostic_starter. * c-pretty-print.c: Include tree-pretty-print.h. * cfgexpand.c: Include tree-pretty-print.h and gimple-pretty-print.h. * cgraphunit.c: Include tree-pretty-print.h and gimple-pretty-print.h. * dwarf2out.c: Include tree-pretty-print.h. * except.c: Include tree-pretty-print.h. * gimple-pretty-print.c: Include tree-pretty-print.h and gimple-pretty-print.h. * gimplify.c: Include tree-pretty-print.h. * graphite-poly.c: Include tree-pretty-print.h and gimple-pretty-print.h. * ipa-cp.c: Include tree-pretty-print.h. * ipa-inline.c: Include gimple-pretty-print.h. * ipa-prop.c: Include tree-pretty-print.h and gimple-pretty-print.h. * ipa-pure-const.c: Include gimple-pretty-print.h. * ipa-struct-reorg.c: Include tree-pretty-print.h and gimple-pretty-print.h. * ipa-type-escape.c: Include tree-pretty-print.h. * print-rtl.c: Include tree-pretty-print.h. * print-tree.c: Include gimple-pretty-print.h. * sese.c: Include tree-pretty-print.h. * tree-affine.c: Include tree-pretty-print.h. * tree-browser.c: Include tree-pretty-print.h. * tree-call-cdce.c: Include gimple-pretty-print.h. * tree-cfg.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-chrec.c: Include tree-pretty-print.h. * tree-data-ref.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-dfa.c: Include tree-pretty-print.h. * tree-if-conv.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-inline.c: Include tree-pretty-print.h. * tree-into-ssa.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-nrv.c: Include tree-pretty-print.h. * tree-object-size.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-outof-ssa.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-parloops.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-predcom.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-scalar-evolution.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-sra.c: Include tree-pretty-print.h. * tree-ssa-address.c: Include tree-pretty-print.h. * tree-ssa-alias.c: Include tree-pretty-print.h. * tree-ssa-ccp.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-ssa-coalesce.c: Include tree-pretty-print.h. * tree-ssa-copy.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-ssa-copyrename.c: Include tree-pretty-print.h. * tree-ssa-dce.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-ssa-dom.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-ssa-dse.c: Include gimple-pretty-print.h. * tree-ssa-forwprop.c: Include tree-pretty-print.h. * tree-ssa-ifcombine.c: Include tree-pretty-print.h. * tree-ssa-live.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-ssa-loop-im.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-ssa-loop-ivcanon.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-ssa-loop-ivopts.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-ssa-loop-niter.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-ssa-loop-prefetch.c: Include tree-pretty-print.h. * tree-ssa-math-opts.c: Include gimple-pretty-print.h. * tree-ssa-operands.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-ssa-phiprop.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-ssa-pre.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-ssa-propagate.c: Include gimple-pretty-print.h. * tree-ssa-reassoc.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-ssa-sccvn.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-ssa-sink.c: Include gimple-pretty-print.h. * tree-ssa-ter.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-ssa-uninit.c: Include gimple-pretty-print.h. * tree-ssa.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-stdarg.c: Include gimple-pretty-print.h. * tree-switch-conversion.c: Include gimple-pretty-print.h. * tree-tailcall.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-vect-data-refs.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-vect-loop-manip.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-vect-loop.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-vect-patterns.c: Include gimple-pretty-print.h. * tree-vect-slp.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-vect-stmts.c: Include tree-pretty-print.h and gimple-pretty-print.h. * tree-vectorizer.c: Include tree-pretty-print.h. * tree-vrp.c: Include tree-pretty-print.h and gimple-pretty-print.h. * value-prof.c: Include tree-pretty-print.h and gimple-pretty-print.h. * var-tracking.c: Include tree-pretty-print.h. * Makefile.in (OBJS-common): Add tree-diagnostic.o. (tree-diagnostic.o): New dependencies. (c-objc-common.o, c-pretty-print.o, langhooks.o, tree.o, tree-inline.o, print-tree.o, stor-layout.o, tree-ssa-uninit.o, tree-ssa.o, tree-into-ssa.o, tree-ssa-ter.o, tree-ssa-coalesce.o, tree-outof-ssa.o, tree-ssa-forwprop.o, tree-ssa-phiprop.o, tree-ssa-ifcombine.o, tree-nrv.o, tree-ssa-copy.o, tree-ssa-propagate.o, tree-ssa-dom.o, tree-ssa-uncprop.o, tree-ssa-live.o, tree-ssa-copyrename.o, tree-ssa-pre.o, tree-ssa-sccvn.o, tree-vrp.o, tree-cfg.o, tree-tailcall.o, tree-ssa-sink.o, tree-if-conv.o, tree-dfa.o, tree-ssa-operands.o, tree-ssa-address.o, tree-ssa-loop-niter.o, tree-ssa-loop-ivcanon.o, tree-ssa-loop-prefetch.o, tree-predcom.o, tree-ssa-loop-ivopts.o, tree-affine.o, tree-ssa-loop-im.o, tree-ssa-math-opts.o, tree-ssa-alias.o, tree-ssa-reassoc.o, gimplify.o, tree-browser.o, tree-chrec.o, tree-scalar-evolution.o, tree-data-ref.o, sese.o, graphite-poly.o, tree-vect-loop.o, tree-vect-loop-manip.o, tree-vect-patterns.o, tree-vect-slp.o, tree-vect-stmts.o, tree-vect-data-refs.o, tree-vectorizer.o, tree-parloops.o, tree-stdarg.o, tree-object-size.o, gimple-pretty-print.o, tree-pretty-print.o, diagnostic.o, toplev.o, print-rtl.o, except.o, dwarf2out.o, cgraphunit.o, ipa-prop.o, ipa-cp.o, ipa-inline.o, ipa-pure-const.o, ipa-type-escape.o, ipa-struct-reorg.o, tree-ssa-dce.o, tree-call-cdce.o, tree-ssa-ccp.o, tree-sra.o, tree-switch-conversion.o, var-tracking.o, value-prof.o, cfgexpand.o, pretty-print.o): Update dependencies. cp: * error.c: Include tree-diagnostic.h and tree-pretty-print.h. (cp_print_error_function): Use diagnostic_abstract_origin macro. (cp_printer): Handle %K here using percent_K_format. * cxx-pretty-print.c: Include tree-pretty-print.h. * Make-lang.in (cp/error.o, cp/cxx-pretty-print.o): Update dependencies. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@159685 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 2 ++ 1 file changed, 2 insertions(+) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index b924ef1a07c..e2ed1f59ee2 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -262,6 +262,8 @@ along with GCC; see the file COPYING3. If not see #include "tree.h" #include "basic-block.h" #include "diagnostic.h" +#include "tree-pretty-print.h" +#include "gimple-pretty-print.h" #include "tree-flow.h" #include "tree-dump.h" #include "timevar.h" -- cgit v1.2.1 From 134c053efb725c8dfa8238c3329ea0439f96df09 Mon Sep 17 00:00:00 2001 From: spop Date: Fri, 28 May 2010 18:42:15 +0000 Subject: When niter may be zero, return a COND_EXPR with the may_be_zero condition. 2010-05-28 Sebastian Pop * tree-scalar-evolution.c (set_nb_iterations_in_loop): Inlined in the only place it was called from. (number_of_latch_executions): Do not return chrec_dont_know when the may_be_zero is a runtime condition: instead, return a COND_EXPR including the may_be_zero condition. * cfgloop.h (struct loop): Add a note on COND_EXPRs to the comment of nb_iterations. * tree-ssa-loop-ivopts.c (contains_abnormal_ssa_name_p): Handle COND_EXPRs. * gcc.dg/vect/vect-outer-fir-lb.c: Un-XFAIL-ed. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@159992 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 70 +++++++++++++++++++++++---------------------- 1 file changed, 36 insertions(+), 34 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index e2ed1f59ee2..d50eac98339 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -900,23 +900,6 @@ add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, return res; } -/* Helper function. */ - -static inline tree -set_nb_iterations_in_loop (struct loop *loop, - tree res) -{ - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, " (set_nb_iterations_in_loop = "); - print_generic_expr (dump_file, res, 0); - fprintf (dump_file, "))\n"); - } - - loop->nb_iterations = res; - return res; -} - /* This section selects the loops that will be good candidates for the @@ -2685,8 +2668,11 @@ resolve_mixers (struct loop *loop, tree chrec) /* Entry point for the analysis of the number of iterations pass. This function tries to safely approximate the number of iterations the loop will run. When this property is not decidable at compile - time, the result is chrec_dont_know. Otherwise the result is - a scalar or a symbolic parameter. + time, the result is chrec_dont_know. Otherwise the result is a + scalar or a symbolic parameter. When the number of iterations may + be equal to zero and the property cannot be determined at compile + time, the result is a COND_EXPR that represents in a symbolic form + the conditions under which the number of iterations is not zero. Example of analysis: suppose that the loop has an exit condition: @@ -2705,37 +2691,53 @@ resolve_mixers (struct loop *loop, tree chrec) tree number_of_latch_executions (struct loop *loop) { - tree res, type; edge exit; struct tree_niter_desc niter_desc; + tree may_be_zero; + tree res; - /* Determine whether the number_of_iterations_in_loop has already + /* Determine whether the number of iterations in loop has already been computed. */ res = loop->nb_iterations; if (res) return res; - res = chrec_dont_know; + + may_be_zero = NULL_TREE; if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "(number_of_iterations_in_loop\n"); + fprintf (dump_file, "(number_of_iterations_in_loop = \n"); + res = chrec_dont_know; exit = single_exit (loop); - if (!exit) - goto end; - if (!number_of_iterations_exit (loop, exit, &niter_desc, false)) - goto end; + if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false)) + { + may_be_zero = niter_desc.may_be_zero; + res = niter_desc.niter; + } + + if (res == chrec_dont_know + || !may_be_zero + || integer_zerop (may_be_zero)) + ; + else if (integer_nonzerop (may_be_zero)) + res = build_int_cst (TREE_TYPE (res), 0); - type = TREE_TYPE (niter_desc.niter); - if (integer_nonzerop (niter_desc.may_be_zero)) - res = build_int_cst (type, 0); - else if (integer_zerop (niter_desc.may_be_zero)) - res = niter_desc.niter; + else if (COMPARISON_CLASS_P (may_be_zero)) + res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero, + build_int_cst (TREE_TYPE (res), 0), res); else res = chrec_dont_know; -end: - return set_nb_iterations_in_loop (loop, res); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " (set_nb_iterations_in_loop = "); + print_generic_expr (dump_file, res, 0); + fprintf (dump_file, "))\n"); + } + + loop->nb_iterations = res; + return res; } /* Returns the number of executions of the exit condition of LOOP, -- cgit v1.2.1 From 8e3cb73bc66100e137b20bcd98316bc415b6e53c Mon Sep 17 00:00:00 2001 From: steven Date: Tue, 1 Jun 2010 22:00:56 +0000 Subject: * gimplify.c: Do not include except.h and optabs.h. (gimplify_body): Do not initialize RTL profiling. * gimple-low.c: Do not include rtl.h, diagnostic.h, langhooks.h, langhooks-def.h, timevar.h, except.h, hashtab.h, and expr.h. * gimple-fold.c: Do not include rtl.h, tm_p.h, ggc.h, basic-block.h, output.h, expr.h, diagnostic.h, timevar.h, value-prof.h, and langhooks.h. * tree-pretty-print.h: Include pretty-print.h. * gimple-pretty-print.h: Include pretty-print.h. * tree-pretty-print.c: Do not include diagnostic.h. * tree-vrp.c: Likewise. * tree-tailcall.c: Likewise * tree-scalar-evolution.c: Likewise * tree-ssa-dse.c: Likewise * tree-chrec.c: Likewise * tree-ssa-sccvn.c: Likewise * tree-ssa-copyrename.c: Likewise * tree-nomudflap.c: Likewise * tree-call-cdce.c: Likewise * tree-stdarg.c: Likewise * tree-ssa-math-opts.c: Likewise * tree-nrv.c: Likewise * tree-ssa-sink.c: Likewise * tree-browser.c: Likewise * tree-ssa-loop-ivcanon.c: Likewise * tree-ssa-loop.c: Likewise * tree-parloops.c: Likewise * tree-ssa-address.c: Likewise * tree-ssa-ifcombine.c: Likewise * tree-if-conv.c: Likewise * tree-data-ref.c: Likewise * tree-affine.c: Likewise * tree-ssa-phiopt.c: Likewise * tree-ssa-coalesce.c: Likewise * tree-ssa-pre.c: Likewise * tree-ssa-live.c: Likewise * tree-predcom.c: Likewise * tree-ssa-forwprop.c: Likewise * tree-ssa-dce.c: Likewise * tree-ssa-ter.c: Likewise * tree-ssa-loop-prefetch.c: Likewise * tree-optimize.c: Likewise * tree-ssa-phiprop.c: Likewise * tree-object-size.c: Likewise * tree-outof-ssa.c: Likewise * tree-ssa-structalias.c: Likewise * tree-switch-conversion.c: Likewise * tree-ssa-reassoc.c: Likewise * tree-ssa-operands.c: Likewise * tree-vectorizer.c: Likewise * tree-vect-data-refs.c: Likewise * tree-vect-generic.c: Likewise * tree-vect-stmts.c: Likewise * tree-vect-patterns.c: Likewise * tree-vect-slp.c: Likewise * tree-vect-loop.c: Likewise * tree-ssa-loop-ivopts.c: Likewise * tree-ssa-loop-im.c: Likewise * tree-ssa-loop-niter.c: Likewise * tree-ssa-loop-unswitch.c: Likewise * tree-ssa-loop-manip.c: Likewise * tree-ssa-loop-ch.c: Likewise * tree-dump.c: Likewise * tree-complex.c: Likewise * tree-into-ssa.c: Do not include diagnostic.h and expr.h. * tree-ssa-uninit.c: Likewise * tree-ssa-threadupdate.c: Likewise * tree-ssa-uncprop.c: Likewise * tree-ssa-ccp.c: Likewise * tree-ssa-dom.c: Likewise * tree-ssa-propagate.c: Likewise * tree-ssa-alias.c: Likewise * tree-dfa.c: Likewise * tree-cfgcleanup.c: Likewise * tree-sra.c: Likewise * tree-ssa-copy.c: Likewise * tree-ssa.c: Likewise * tree-profile.c: Likewise * tree-cfg.c: Likewise * tree-ssa-threadedge.c: Likewise * tree-vect-loop-manip.c: Likewise * tree-inline.c: Do not include diagnostic.h and expr.h. Include rtl.h. (copy_decl_for_dup_finish): Do not use NULL_RTX. * tree-loop-linear.c: Do not include diagnostic.h, expr.h, and optabs.h. * tree-loop-distribution.c: Likewise. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@160125 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 1 - 1 file changed, 1 deletion(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index d50eac98339..bf564d8dab5 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -261,7 +261,6 @@ along with GCC; see the file COPYING3. If not see #include "ggc.h" #include "tree.h" #include "basic-block.h" -#include "diagnostic.h" #include "tree-pretty-print.h" #include "gimple-pretty-print.h" #include "tree-flow.h" -- cgit v1.2.1 From ba72912a012b97cad825eebee3f5f22253d0afe4 Mon Sep 17 00:00:00 2001 From: lauras Date: Tue, 8 Jun 2010 07:25:24 +0000 Subject: gcc/ada: 2010-06-08 Laurynas Biveinis * gcc-interface/utils.c (init_gnat_to_gnu): Use typed GC allocation. (init_dummy_type): Likewise. (gnat_pushlevel): Likewise. * gcc-interface/trans.c (Attribute_to_gnu): Likewise. (Subprogram_Body_to_gnu): Likewise. (Compilation_Unit_to_gnu): Likewise. (start_stmt_group): Likewise. (extract_encoding): Likewise. (decode_name): Likewise. * gcc-interface/misc.c (gnat_printable_name): Likewise. * gcc-interface/decl.c (annotate_value): Likewise. * gcc-interface/ada-tree.h (struct lang_type): Add variable_size GTY option. (struct lang_decl): Likewise. (SET_TYPE_LANG_SPECIFIC): Use typed GC allocation. (SET_DECL_LANG_SPECIFIC): Likewise. gcc/c-family: 2010-06-08 Laurynas Biveinis * c-pragma.c (push_alignment): Use typed GC allocation. (handle_pragma_push_options): Likewise. * c-common.c (parse_optimize_options): Likewise. * c-common.h (struct sorted_fields_type): Add variable_size GTY option. gcc/cp: 2010-06-08 Laurynas Biveinis * typeck2.c (abstract_virtuals_error): Likewise. * pt.c (maybe_process_partial_specialization): Likewise. (register_specialization): Likewise. (add_pending_template): Likewise. (lookup_template_class): Likewise. (push_tinst_level): Likewise. * parser.c (cp_lexer_new_main): Likewise. (cp_lexer_new_from_tokens): Likewise. (cp_token_cache_new): Likewise. (cp_parser_context_new): Likewise. (cp_parser_new): Likewise. (cp_parser_nested_name_specifier_opt): Likewise. (cp_parser_template_id): Likewise. * name-lookup.c (binding_entry_make): Likewise. (binding_table_construct): Likewise. (binding_table_new): Likewise. (cxx_binding_make): Likewise. (pushdecl_maybe_friend): Likewise. (begin_scope): Likewise. (push_to_top_level): Likewise. * lex.c (init_reswords): Likewise. (retrofit_lang_decl): Likewise. (cxx_dup_lang_specific_decl): Likewise. (copy_lang_type): Likewise. (cxx_make_type): Likewise. * decl.c (make_label_decl): Likewise. (check_goto): Likewise. (start_preparsed_function): Likewise. (save_function_data): Likewise. * cp-tree.h (TYPE_SET_PTRMEMFUNC_TYPE): Likewise. * cp-objcp-common.c (decl_shadowed_for_var_insert): Likewise. * class.c (finish_struct_1): Likewise. * cp-tree.h (struct lang_type): Add variable_size GTY option. (struct lang_decl): Likewise. * parser.c (cp_parser_new): Update comment to not reference ggc_alloc. gcc/fortran: 2010-06-08 Laurynas Biveinis * trans-types.c (gfc_get_nodesc_array_type): Use typed GC allocation. (gfc_get_array_type_bounds): Likewise. * trans-decl.c (gfc_allocate_lang_decl): Likewise. (gfc_find_module): Likewise. * f95-lang.c (pushlevel): Likewise. * trans.h (struct lang_type): Add variable_size GTY option. (struct lang_decl): Likewise. gcc/java: 2010-06-08 Laurynas Biveinis * jcf-reader.c (jcf_parse_constant_pool): Use typed GC allocation. * jcf-parse.c (java_parse_file): Likewise. (process_zip_dir): Likewise. * java-tree.h (MAYBE_CREATE_VAR_LANG_DECL_SPECIFIC): Likewise. (MAYBE_CREATE_TYPE_TYPE_LANG_SPECIFIC): Likewise. * expr.c (add_type_assertion): Likewise. * decl.c (make_binding_level): Likewise. (java_dup_lang_specific_decl): Likewise. * constants.c (set_constant_entry): Likewise. (cpool_for_class): Likewise. * class.c (add_method_1): Likewise. (java_treetreehash_new): Likewise. * java-tree.h (struct lang_type): Add variable_size GTY option. (struct lang_decl): Likewise. * jch.h (struct cpool_entry): Likewise. * java-tree.h (java_treetreehash_create): Remove parameter ggc. * except.c (prepare_eh_table_type): Update java_treetreehash_create call. * class.c (add_method_1): Update java_treetreehash_create call. (java_treetreehash_create): Remove parameter gc. Use htab_create_ggc. gcc/lto: 2010-06-08 Laurynas Biveinis * lto.c (lto_read_in_decl_state): Use typed GC allocation. (lto_file_read): Likewise. (new_partition): Likewise. (read_cgraph_and_symbols): Likewise. gcc/objc: 2010-06-08 Laurynas Biveinis * objc-act.h (ALLOC_OBJC_TYPE_LANG_SPECIFIC): Use typed GC allocation. * objc-act.c (objc_volatilize_decl): Likewise. (objc_build_string_object): Likewise. (hash_init): Likewise. (hash_enter): Likewise. (hash_add_attr): Likewise. (add_class): Likewise. (start_class): Likewise. gcc/objcp: 2010-06-08 Laurynas Biveinis * objcp-decl.h (ALLOC_OBJC_TYPE_LANG_SPECIFIC): Use typed GC allocation. gcc: 2010-06-08 Laurynas Biveinis * doc/tm.texi (Per-Function Data): Do not reference ggc_alloc. * doc/gty.texi (GTY Options): Document typed GC allocation and variable_size GTY option. * ggc-internal.h: New. * ggc.h: Update copyright year. (digit_string): Move to stringpool.c. (ggc_mark_stringpool, ggc_purge_stringpool, ggc_mark_roots) (gt_pch_save_stringpool, gt_pch_fixup_stringpool) (gt_pach_restore_stringpool, gt_pch_p_S, gt_pch_note_object) (init_ggc_pch, ggc_pch_count_object, ggc_pch_total_size) (ggc_pch_this_base, ggc_pch_alloc_object, ggc_pch_prepare_write) (ggc_pch_write_object, ggc_pch_finish, ggc_pch_read) (ggc_force_collect, ggc_get_size, ggc_statistics) (ggc_print_common_statistics): Move to ggc-internal.h. (digit_vector, new_ggc_zone, destroy_ggc_zone, ggc_alloc_stat) (ggc_alloc, ggc_alloc_cleared, ggc_realloc, ggc_calloc, GGC_NEW) (GGC_CNEW, GGC_NEWVEC, GGC_CNEWVEC, GGC_NEWVAR, ggc_alloc_rtvec) (ggc_alloc_tree, gt_pch_save, ggc_min_expand_heuristic) (ggc_min_heapsize_heuristic, ggc_alloc_zone) (ggc_alloc_zone_pass_stat): Remove. (ggc_internal_alloc_stat, ggc_internal_alloc) (ggc_internal_cleared_alloc_stat): New. (GGC_RESIZEVEC, GGC_RESIZEVAR): Redefine. (ggc_internal_vec_alloc_stat) (ggc_internal_cleared_vec_alloc_stat) (ggc_internal_vec_alloc_stat, ggc_internal_cleared_vec_alloc) (ggc_alloc_atomic_stat, ggc_alloc_atomic) (ggc_alloc_cleared_atomic, ggc_cleared_alloc_htab_ignore_args) (ggc_cleared_alloc_ptr_array_two_args): New. (htab_create_ggc, splay_tree_new_ggc): Redefine. (ggc_splay_alloc): Change the type of the first argument to enum gt_types_enum. (ggc_alloc_string): Make macro. (ggc_alloc_string_stat): New. (ggc_strdup): Redefine. (rtl_zone, tree_zone, tree_id_zone): Declare unconditionally. (ggc_alloc_rtvec_sized): New. (ggc_alloc_zone_stat): Rename to ggc_internal_alloc_zone_stat. (ggc_internal_alloc_zone_pass_stat, ggc_internal_alloc_zone_stat) (ggc_internal_cleared_alloc_zone_stat) (ggc_internal_zone_alloc_stat) (ggc_internal_zone_cleared_alloc_stat) (ggc_internal_zone_vec_alloc_stat) (ggc_alloc_zone_rtx_def_stat) (ggc_alloc_zone_tree_node_stat) (ggc_alloc_zone_cleared_tree_node_stat) (ggc_alloc_cleared_gimple_statement_d_stat): New. * ggc-common.c: Include ggc-internal.h. (ggc_internal_cleared_alloc_stat): Rename from ggc_alloc_cleared_stat. (ggc_realloc_stat): Use ggc_internal_alloc_stat. (ggc_calloc): Remove. (ggc_cleared_alloc_htab_ignore_args): New. (ggc_cleared_alloc_ptr_array_two_args): New. (ggc_splay_alloc): Add obj_type parameter. (init_ggc_heuristics): Formatting fixes. * ggc-none.c: Update copyright year. (ggc_alloc_stat): Rename to ggc_alloc_stat. (ggc_alloc_cleared_stat): Rename to ggc_internal_cleared_alloc_stat. (struct alloc_zone, rtl_zone, tree_zone, tree_id_zone): New. * ggc-page.c: Update copyright year. Include ggc-internal.h. Remove references to ggc_alloc in comments. (ggc_alloc_typed_stat): Call ggc_internal_alloc_stat. (ggc_alloc_stat): Rename to ggc_internal_alloc_stat. (new_ggc_zone, destroy_ggc_zone): Remove. (struct alloc_zone, rtl_zone, tree_zone, tree_id_zone): New. * ggc-zone.c: Include ggc-internal.h. Remove references to ggc_alloc in comments. (ggc_alloc_zone_stat): ggc_internal_alloc_zone_stat. (ggc_internal_alloc_zone_pass_stat): New. (ggc_internal_cleared_alloc_zone_stat): New. (ggc_alloc_typed_stat): Use ggc_internal_alloc_zone_pass_stat. (ggc_alloc_stat): Rename ggc_internal_alloc_stat. (new_ggc_zone, destroy_ggc_zone): Remove. * stringpool.c: Update copyright year. Include ggc-internal.h (digit_vector): Make static. (digit_string): Moved from ggc.h. (stringpool_ggc_alloc): Use ggc_alloc_atomic. (ggc_alloc_string): Rename to ggc_alloc_string_stat. * Makefile.in (GGC_INTERNAL_H): New. (ggc_common.o, ggc-page.o, ggc-zone.o, stringpool.o): Add $(GGC_INTERNAL_H) to dependencies. * gentype.c: Update copyright year. (walk_type): Accept variable_size GTY option. (USED_BY_TYPED_GC_P): New macro. (write_enum_defn): Use USED_BY_TYPED_GC_P. Do not output whitespace at the end of strings. (get_type_specifier, variable_size_p): New functions. (alloc_quantity, alloc_zone): New enums. (write_typed_alloc_def): New function. (write_typed_struct_alloc_def): Likewise. (write_typed_typed_typedef_alloc_def): Likewise. (write_typed_alloc_defns): Likewise. (output_typename, write_splay_tree_allocator_def): Likewise. (write_splay_tree_allocators): Likewise. (main): Call write_typed_alloc_defns and write_splay_tree_allocators. * lto-streamer.h (lto_file_decl_data_ptr): New. * passes.c (order): Define using cgraph_node_ptr. * strinpool.c (struct string_pool_data): Declare nested_ptr using ht_identifier_ptr. * gimple.h (union gimple_statement_d): Likewise. * rtl.h (struct rtx_def): Likewise. (struct rtvec_def): Likewise. * tree.h (union tree_node): Likewise. * tree-ssa-operands.h (struct ssa_operand_memory_d): Likewise. * cfgloop.c (record_loop_exits): Use htab_create_ggc. * tree-scalar-evolution.c (scev_initialize): Likewise. * alias.c (record_alias_subset): Update splay_tree_new_ggc call. * dwarf2asm.c (dw2_force_const_mem): Likewise. * omp-low.c (lower_omp_critical): Likewise. * bitmap.h (struct bitmap_head_def): Update comment to not reference ggc_alloc. * config/pa/pa.c (get_deferred_label): Use GGC_RESIZEVEC. * ira.c (fix_reg_equiv_init): Use GGC_RESIZEVEC. * ipa-prop.c (duplicate_ggc_array): Rename to duplicate_ipa_jump_func_array. Use typed GC allocation. (ipa_edge_duplication_hook): Call duplicate_ipa_jump_func_array. * gimple.c (gimple_alloc_stat): Use ggc_alloc_cleared_gimple_statement_d_stat. * varasm.c (create_block_symbol): Use ggc_alloc_zone_rtx_def. * tree.c (make_node_stat): Use ggc_alloc_zone_cleared_tree_node_stat. (make_tree_vec_stat): Likewise. (build_vl_exp_stat): Likewise. (copy_node_stat): Use ggc_alloc_zone_tree_node_stat. (make_tree_binfo_stat): Likewise. (tree_cons_stat): Likewise. * rtl.c (rtx_alloc_stat): Use ggc_alloc_zone_rtx_def_stat. (shallow_copy_rtx_stat): Likewise. (make_node_stat): Likewise. * lto-symtab.c: Fix comment. * tree-cfg.c (create_bb): Update comment to not reference ggc_alloc_cleared. * tree-ssa-structalias.c (struct heapvar_for_stmt): Fix param_is value. * varpool.c (varpool_node): Use typed GC allocation. (varpool_extra_name_alias): Likewise. * varasm.c (emutls_decl): Likewise. (get_unnamed_section): Likewise. (get_noswitch_section): Likewise. (get_section): Likewise. (get_block_for_section): Likewise. (build_constant_desc): Likewise. (create_constant_pool): Likewise. (force_const_mem): Likewise. * tree.c (build_vl_exp_stat): Likewise. (build_real): Likewise. (build_string): Likewise. (decl_debug_expr_insert): Likewise. (decl_value_expr_insert): Likewise. (type_hash_add): Likewise. (build_omp_clause): Likewise. * tree-ssanames.c (duplicate_ssa_name_ptr_info): Likewise. * tree-ssa.c (init_tree_ssa): Likewise. * tree-ssa-structalias.c (heapvar_insert): Likewise. * tree-ssa-operands.c (ssa_operand_alloc): Likewise. * tree-ssa-loop-niter.c (record_estimate): Likewise. * tree-ssa-alias.c (get_ptr_info): Likewise. * tree-scalar-evolution.c (new_scev_info_str): Likewise. * tree-phinodes.c (allocate_phi_node): Likewise. * tree-iterator.c (tsi_link_before): Likewise. (tsi_link_after): Likewise. * tree-eh.c (add_stmt_to_eh_lp_fn): Likewise. * tree-dfa.c (create_var_ann): Likewise. * tree-cfg.c (create_bb): Likewise. * toplev.c (alloc_for_identifier_to_locale): Likewise. (general_init): Likewise. * stringpool.c (stringpool_ggc_alloc): Likewise. (gt_pch_save_stringpool): Likewise. * sese.c (if_region_set_false_region): Likewise. * passes.c (do_per_function_toporder): Likewise. * optabs.c (set_optab_libfunc): Likewise. (set_conv_libfunc): Likewise. * lto-symtab.c (lto_symtab_register_decl): Likewise. * lto-streamer-in.c (lto_input_eh_catch_list): Likewise. (input_eh_region): Likewise. (input_eh_lp): Likewise. (make_new_block): Likewise. (unpack_ts_real_cst_value_fields): Likewise. * lto-section-in.c (lto_new_in_decl_state): Likewise. * lto-cgraph.c (input_node_opt_summary): Likewise. * loop-init.c (loop_optimizer_init): Likewise. * lambda.h (lambda_vector_new): Likewise. * lambda-code.c (replace_uses_equiv_to_x_with_y): Likewise. * ira.c (update_equiv_regs): Likewise. * ipa.c (cgraph_node_set_new): Likewise. (cgraph_node_set_add): Likewise. (varpool_node_set_new): Likewise. (varpool_node_set_add): Likewise. * ipa-prop.c (ipa_compute_jump_functions_for_edge): Likewise. (duplicate_ipa_jump_func_array): Likewise. (ipa_read_node_info): Likewise. * ipa-cp.c (ipcp_create_replace_map): Likewise. * integrate.c (get_hard_reg_initial_val): Likewise. * gimple.c (gimple_alloc_stat): Likewise. (gimple_build_omp_for): Likewise. (gimple_seq_alloc): Likewise. (gimple_copy): Likewise. * gimple-iterator.c (gsi_insert_before_without_update): Likewise. (gsi_insert_after_without_update): Likewise. * function.c (add_frame_space): Likewise. (insert_temp_slot_address): Likewise. (assign_stack_temp_for_type): Likewise. (allocate_struct_function): Likewise. (types_used_by_var_decl_insert): Likewise. * except.c (init_eh_for_function): Likewise. (gen_eh_region): Likewise. (gen_eh_region_catch): Likewise. (gen_eh_landing_pad): Likewise. (add_call_site): Likewise. * emit-rtl.c (get_mem_attrs): Likewise. (get_reg_attrs): Likewise. (start_sequence): Likewise. (init_emit): Likewise. * dwarf2out.c (new_cfi): Likewise. (queue_reg_save): Likewise. (dwarf2out_frame_init): Likewise. (new_loc_descr): Likewise. (find_AT_string): Likewise. (new_die): Likewise. (add_var_loc_to_decl): Likewise. (clone_die): Likewise. (clone_as_declaration): Likewise. (break_out_comdat_types): Likewise. (new_loc_list): Likewise. (loc_descriptor): Likewise. (add_loc_descr_to_each): Likewise. (add_const_value_attribute): Likewise. (tree_add_const_value_attribute): Likewise. (add_comp_dir_attribute): Likewise. (add_name_and_src_coords_attributes): Likewise. (lookup_filename): Likewise. (store_vcall_insn): Likewise. (dwarf2out_init): Likewise. * dbxout.c (dbxout_init): Likewise. * config/xtensa/xtensa.c (xtensa_init_machine_status): Likewise. * config/sparc/sparc.c (sparc_init_machine_status): Likewise. * config/score/score7.c (score7_output_external): Likewise. * config/score/score3.c (score3_output_external): Likewise. * config/s390/s390.c (s390_init_machine_status): Likewise. * config/rs6000/rs6000.c (builtin_function_type): Likewise. (rs6000_init_machine_status): Likewise. (output_toc): Likewise. * config/pa/pa.c (pa_init_machine_status): Likewise. (get_deferred_plabel): Likewise. * config/moxie/moxie.c (moxie_init_machine_status): Likewise. * config/mmix/mmix.c (mmix_init_machine_status): Likewise. * config/mips/mips.c (mflip_mips16_use_mips16_p): Likewise. * config/mep/mep.c (mep_init_machine_status): Likewise. (mep_note_pragma_flag): Likewise. * config/m32c/m32c.c (m32c_init_machine_status): Likewise. * config/iq2000/iq2000.c (iq2000_init_machine_status): Likewise. * config/ia64/ia64.c (ia64_init_machine_status): Likewise. * config/i386/winnt.c (i386_pe_record_external_function): Likewise. (i386_pe_maybe_record_exported_symbol): Likewise. * config/i386/i386.c (get_dllimport_decl): Likewise. (ix86_init_machine_status): Likewise. (assign_386_stack_local): Likewise. * config/frv/frv.c (frv_init_machine_status): Likewise. * config/darwin.c (machopic_indirection_name): Likewise. * config/cris/cris.c (cris_init_machine_status): Likewise. * config/bfin/bfin.c (bfin_init_machine_status): Likewise. * config/avr/avr.c (avr_init_machine_status): Likewise. * config/arm/arm.c (arm_init_machine_status): Likewise. * config/alpha/alpha.c (alpha_init_machine_status): Likewise. (alpha_need_linkage): Likewise. (alpha_use_linkage): Likewise. * cgraph.c (cgraph_allocate_node): Likewise. (cgraph_create_edge_1): Likewise. (cgraph_create_indirect_edge): Likewise. (cgraph_add_asm_node): Likewise. * cfgrtl.c (init_rtl_bb_info): Likewise. * cfgloop.c (alloc_loop): Likewise. (rescan_loop_exit): Likewise. * cfg.c (init_flow): Likewise. (alloc_block): Likewise. (unchecked_make_edge): Likewise. * c-parser.c (c_parse_init): Likewise. (c_parse_file): Likewise. * c-decl.c (bind): Likewise. (record_inline_static): Likewise. (push_scope): Likewise. (make_label): Likewise. (lookup_label_for_goto): Likewise. (finish_struct): Likewise. (finish_enum): Likewise. (c_push_function_context): Likewise. * bitmap.c (bitmap_element_allocate): Likewise. (bitmap_gc_alloc_stat): Likewise. * alias.c (record_alias_subset): Likewise. (init_alias_analysis): Likewise. include: 2010-06-08 Laurynas Biveinis * splay-tree.h: Update copyright years. (splay_tree_s): Document fields. (splay_tree_new_typed_alloc): New. * hashtab.h: Update copyright years. (htab_create_typed_alloc): New. libcpp: 2010-06-08 Laurynas Biveinis * include/symtab.h (ht_identifier_ptr): New. libiberty: 2010-06-08 Laurynas Biveinis * splay-tree.c: Update copyright years. (splay_tree_new_typed_alloc): New. (splay_tree_new_with_allocator): Use it. * hashtab.c: Update copyright years. (htab_create_typed_alloc): New. (htab_create_alloc): Use it. * functions.texi: Regenerate. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@160425 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 11 ++++------- 1 file changed, 4 insertions(+), 7 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index bf564d8dab5..5eb61740bee 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -314,7 +314,7 @@ new_scev_info_str (basic_block instantiated_below, tree var) { struct scev_info_str *res; - res = GGC_NEW (struct scev_info_str); + res = ggc_alloc_scev_info_str (); res->var = var; res->chrec = chrec_not_analyzed_yet; res->instantiated_below = instantiated_below; @@ -3017,12 +3017,9 @@ scev_initialize (void) loop_iterator li; struct loop *loop; - scalar_evolution_info = htab_create_alloc (100, - hash_scev_info, - eq_scev_info, - del_scev_info, - ggc_calloc, - ggc_free); + + scalar_evolution_info = htab_create_ggc (100, hash_scev_info, eq_scev_info, + del_scev_info); initialize_scalar_evolutions_analyzer (); -- cgit v1.2.1 From dfeb6545e649ba53adf17b8d77f6499b7cb02977 Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 9 Jun 2010 22:09:41 +0000 Subject: Call compute_overall_effect_of_inner_loop from instantiate_scev_name. 2010-06-09 Sebastian Pop * tree-scalar-evolution.c (instantiate_scev_name): Do not fail the scev analysis when the variable is not used outside the loop in a close phi node: call compute_overall_effect_of_inner_loop. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@160510 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 16 +++++++++++++--- 1 file changed, 13 insertions(+), 3 deletions(-) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 5eb61740bee..13d897fd5ce 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -2172,9 +2172,19 @@ instantiate_scev_name (basic_block instantiate_below, else res = chrec; - if (res == NULL_TREE - || !dominated_by_p (CDI_DOMINATORS, instantiate_below, - gimple_bb (SSA_NAME_DEF_STMT (res)))) + /* When there is no loop_closed_phi_def, it means that the + variable is not used after the loop: try to still compute the + value of the variable when exiting the loop. */ + if (res == NULL_TREE) + { + loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec)); + res = analyze_scalar_evolution (loop, chrec); + res = compute_overall_effect_of_inner_loop (loop, res); + res = instantiate_scev_r (instantiate_below, evolution_loop, res, + fold_conversions, cache, size_expr); + } + else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below, + gimple_bb (SSA_NAME_DEF_STMT (res)))) res = chrec_dont_know; } -- cgit v1.2.1 From 182cf5a9a415f31df0f9a10e46faed1221484a35 Mon Sep 17 00:00:00 2001 From: rguenth Date: Thu, 1 Jul 2010 08:49:19 +0000 Subject: 2010-07-01 Richard Guenther PR middle-end/42834 PR middle-end/44468 * doc/gimple.texi (is_gimple_mem_ref_addr): Document. * doc/generic.texi (References to storage): Document MEM_REF. * tree-pretty-print.c (dump_generic_node): Handle MEM_REF. (print_call_name): Likewise. * tree.c (recompute_tree_invariant_for_addr_expr): Handle MEM_REF. (build_simple_mem_ref_loc): New function. (mem_ref_offset): Likewise. * tree.h (build_simple_mem_ref_loc): Declare. (build_simple_mem_ref): Define. (mem_ref_offset): Declare. * fold-const.c: Include tree-flow.h. (operand_equal_p): Handle MEM_REF. (build_fold_addr_expr_with_type_loc): Likewise. (fold_comparison): Likewise. (fold_unary_loc): Fold VIEW_CONVERT_EXPR > to MEM_REF . (fold_binary_loc): Fold MEM[&MEM[p, CST1], CST2] to MEM[p, CST1 + CST2], fold MEM[&a.b, CST2] to MEM[&a, offsetof (a, b) + CST2]. * tree-ssa-alias.c (ptr_deref_may_alias_decl_p): Handle MEM_REF. (ptr_deref_may_alias_ref_p_1): Likewise. (ao_ref_base_alias_set): Properly differentiate base object for offset and TBAA. (ao_ref_init_from_ptr_and_size): Use MEM_REF. (indirect_ref_may_alias_decl_p): Handle MEM_REFs properly. (indirect_refs_may_alias_p): Likewise. (refs_may_alias_p_1): Likewise. Remove pointer SSA name def chasing code. (ref_maybe_used_by_call_p_1): Handle MEM_REF. (call_may_clobber_ref_p_1): Likewise. * dwarf2out.c (loc_list_from_tree): Handle MEM_REF. * expr.c (expand_assignment): Handle MEM_REF. (store_expr): Handle MEM_REFs from STRING_CSTs. (store_field): If expanding a MEM_REF of a non-addressable decl use bitfield operations. (get_inner_reference): Handle MEM_REF. (expand_expr_addr_expr_1): Likewise. (expand_expr_real_1): Likewise. * tree-eh.c (tree_could_trap_p): Handle MEM_REF. * alias.c (ao_ref_from_mem): Handle MEM_REF. (get_alias_set): Likewise. Properly handle VIEW_CONVERT_EXPRs. * tree-data-ref.c (dr_analyze_innermost): Handle MEM_REF. (dr_analyze_indices): Likewise. (dr_analyze_alias): Likewise. (object_address_invariant_in_loop_p): Likewise. * gimplify.c (mark_addressable): Handle MEM_REF. (gimplify_cond_expr): Build MEM_REFs. (gimplify_modify_expr_to_memcpy): Likewise. (gimplify_init_ctor_preeval_1): Handle MEM_REF. (gimple_fold_indirect_ref): Adjust. (gimplify_expr): Handle MEM_REF. Gimplify INDIRECT_REF to MEM_REF. * tree.def (MEM_REF): New tree code. * tree-dfa.c: Include toplev.h. (get_ref_base_and_extent): Handle MEM_REF. (get_addr_base_and_unit_offset): New function. * emit-rtl.c (set_mem_attributes_minus_bitpos): Handle MEM_REF. * gimple-fold.c (may_propagate_address_into_dereference): Handle MEM_REF. (maybe_fold_offset_to_array_ref): Allow possibly out-of bounds accesses if the array has just one dimension. Remove always true parameter. Do not require type compatibility here. (maybe_fold_offset_to_component_ref): Remove. (maybe_fold_stmt_indirect): Remove. (maybe_fold_reference): Remove INDIRECT_REF handling. Fold back to non-MEM_REF. (maybe_fold_offset_to_address): Simplify. Deal with type mismatches here. (maybe_fold_reference): Likewise. (maybe_fold_stmt_addition): Likewise. Also handle &ARRAY + I in addition to &ARRAY[0] + I. (fold_gimple_assign): Handle ADDR_EXPR of MEM_REFs. (gimple_get_relevant_ref_binfo): Handle MEM_REF. * cfgexpand.c (expand_debug_expr): Handle MEM_REF. * tree-ssa.c (useless_type_conversion_p): Make most pointer conversions useless. (warn_uninitialized_var): Handle MEM_REF. (maybe_rewrite_mem_ref_base): New function. (execute_update_addresses_taken): Implement re-writing of MEM_REFs to SSA form. * tree-inline.c (remap_gimple_op_r): Handle MEM_REF, remove INDIRECT_REF handling. (copy_tree_body_r): Handle MEM_REF. * gimple.c (is_gimple_addressable): Adjust. (is_gimple_address): Likewise. (is_gimple_invariant_address): ADDR_EXPRs of MEM_REFs with invariant base are invariant. (is_gimple_min_lval): Adjust. (is_gimple_mem_ref_addr): New function. (get_base_address): Handle MEM_REF. (count_ptr_derefs): Likewise. (get_base_loadstore): Likewise. * gimple.h (is_gimple_mem_ref_addr): Declare. (gimple_call_fndecl): Handle invariant MEM_REF addresses. * tree-cfg.c (verify_address): New function, split out from ... (verify_expr): ... here. Use for verifying ADDR_EXPRs and the address operand of MEM_REFs. Verify MEM_REFs. Reject INDIRECT_REFs. (verify_types_in_gimple_min_lval): Handle MEM_REF. Disallow INDIRECT_REF. Allow conversions. (verify_types_in_gimple_reference): Verify VIEW_CONVERT_EXPR of a register does not change its size. (verify_types_in_gimple_reference): Verify MEM_REF. (verify_gimple_assign_single): Disallow INDIRECT_REF. Handle MEM_REF. * tree-ssa-operands.c (opf_non_addressable, opf_not_non_addressable): New. (mark_address_taken): Handle MEM_REF. (get_indirect_ref_operands): Pass through opf_not_non_addressable. (get_asm_expr_operands): Pass opf_not_non_addressable. (get_expr_operands): Handle opf_[not_]non_addressable. Handle MEM_REF. Remove INDIRECT_REF handling. * tree-vrp.c: (check_array_ref): Handle MEM_REF. (search_for_addr_array): Likewise. (check_array_bounds): Likewise. (vrp_stmt_computes_nonzero): Adjust for MEM_REF. * tree-ssa-loop-im.c (for_each_index): Handle MEM_REF. (ref_always_accessed_p): Likewise. (gen_lsm_tmp_name): Likewise. Handle ADDR_EXPR. * tree-complex.c (extract_component): Do not handle INDIRECT_REF. Handle MEM_REF. * cgraphbuild.c (mark_load): Properly check for NULL result from get_base_address. (mark_store): Likewise. * tree-ssa-loop-niter.c (array_at_struct_end_p): Handle MEM_REF. * tree-loop-distribution.c (generate_builtin): Exchange INDIRECT_REF handling for MEM_REF. * tree-scalar-evolution.c (follow_ssa_edge_expr): Handle &MEM[ptr + CST] similar to POINTER_PLUS_EXPR. * builtins.c (stabilize_va_list_loc): Use the function ABI valist type if we couldn't canonicalize the argument type. Always dereference with the canonical va-list type. (maybe_emit_free_warning): Handle MEM_REF. (fold_builtin_memory_op): Simplify and handle MEM_REFs in folding memmove to memcpy. * builtins.c (fold_builtin_memory_op): Use ref-all types for all memcpy foldings. * omp-low.c (build_receiver_ref): Adjust for MEM_REF. (build_outer_var_ref): Likewise. (scan_omp_1_op): Likewise. (lower_rec_input_clauses): Likewise. (lower_lastprivate_clauses): Likewise. (lower_reduction_clauses): Likewise. (lower_copyprivate_clauses): Likewise. (expand_omp_atomic_pipeline): Likewise. (expand_omp_atomic_mutex): Likewise. (create_task_copyfn): Likewise. * tree-ssa-sccvn.c (copy_reference_ops_from_ref): Handle MEM_REF. Remove old union trick. Initialize constant offsets. (ao_ref_init_from_vn_reference): Likewise. Do not handle INDIRECT_REF. Init base_alias_set properly. (vn_reference_lookup_3): Replace INDIRECT_REF handling with MEM_REF. (vn_reference_fold_indirect): Adjust for MEM_REFs. (valueize_refs): Fold MEM_REFs. Re-evaluate constant offset for ARRAY_REFs. (may_insert): Remove. (visit_reference_op_load): Do not test may_insert. (run_scc_vn): Remove parameter, do not fiddle with may_insert. * tree-ssa-sccvn.h (struct vn_reference_op_struct): Add a field to store the constant offset this op applies. (run_scc_vn): Adjust prototype. * cgraphunit.c (thunk_adjust): Adjust for MEM_REF. * tree-ssa-ccp.c (ccp_fold): Replace INDIRECT_REF folding with MEM_REF. Propagate &foo + CST as &MEM[&foo, CST]. Do not bother about volatile qualifiers on pointers. (fold_const_aggregate_ref): Handle MEM_REF, do not handle INDIRECT_REF. * tree-ssa-loop-ivopts.c * tree-ssa-loop-ivopts.c (determine_base_object): Adjust for MEM_REF. (strip_offset_1): Likewise. (find_interesting_uses_address): Replace INDIRECT_REF handling with MEM_REF handling. (get_computation_cost_at): Likewise. * ipa-pure-const.c (check_op): Handle MEM_REF. * tree-stdarg.c (check_all_va_list_escapes): Adjust for MEM_REF. * tree-ssa-sink.c (is_hidden_global_store): Handle MEM_REF and constants. * ipa-inline.c (likely_eliminated_by_inlining_p): Handle MEM_REF. * tree-parloops.c (take_address_of): Adjust for MEM_REF. (eliminate_local_variables_1): Likewise. (create_call_for_reduction_1): Likewise. (create_loads_for_reductions): Likewise. (create_loads_and_stores_for_name): Likewise. * matrix-reorg.c (may_flatten_matrices_1): Sanitize. (ssa_accessed_in_tree): Handle MEM_REF. (ssa_accessed_in_assign_rhs): Likewise. (update_type_size): Likewise. (analyze_accesses_for_call_stmt): Likewise. (analyze_accesses_for_assign_stmt): Likewise. (transform_access_sites): Likewise. (transform_allocation_sites): Likewise. * tree-affine.c (tree_to_aff_combination): Handle MEM_REF. * tree-vect-data-refs.c (vect_create_addr_base_for_vector_ref): Do not handle INDIRECT_REF. * tree-ssa-phiopt.c (add_or_mark_expr): Handle MEM_REF. (cond_store_replacement): Likewise. * tree-ssa-pre.c (create_component_ref_by_pieces_1): Handle MEM_REF, no not handle INDIRECT_REFs. (insert_into_preds_of_block): Properly initialize avail. (phi_translate_1): Fold MEM_REFs. Re-evaluate constant offset for ARRAY_REFs. Properly handle reference lookups that require a bit re-interpretation. (can_PRE_operation): Do not handle INDIRECT_REF. Handle MEM_REF. * tree-sra.c * tree-sra.c (build_access_from_expr_1): Handle MEM_REF. (build_ref_for_offset_1): Remove. (build_ref_for_offset): Build MEM_REFs. (gate_intra_sra): Disable for now. (sra_ipa_modify_expr): Handle MEM_REF. (ipa_early_sra_gate): Disable for now. * tree-sra.c (create_access): Swap INDIRECT_REF handling for MEM_REF handling. (disqualify_base_of_expr): Likewise. (ptr_parm_has_direct_uses): Swap INDIRECT_REF handling for MEM_REF handling. (sra_ipa_modify_expr): Remove INDIRECT_REF handling. Use mem_ref_offset. Remove bogus folding. (build_access_from_expr_1): Properly handle MEM_REF for non IPA-SRA. (make_fancy_name_1): Add support for MEM_REF. * tree-predcom.c (ref_at_iteration): Handle MEM_REFs. * tree-mudflap.c (mf_xform_derefs_1): Adjust for MEM_REF. * ipa-prop.c (compute_complex_assign_jump_func): Handle MEM_REF. (compute_complex_ancestor_jump_func): Likewise. (ipa_analyze_virtual_call_uses): Likewise. * tree-ssa-forwprop.c (forward_propagate_addr_expr_1): Replace INDIRECT_REF folding with more generalized MEM_REF folding. (tree_ssa_forward_propagate_single_use_vars): Adjust accordingly. (forward_propagate_addr_into_variable_array_index): Also handle &ARRAY + I in addition to &ARRAY[0] + I. * tree-ssa-dce.c (ref_may_be_aliased): Handle MEM_REF. * tree-ssa-ter.c (find_replaceable_in_bb): Avoid TER if that creates assignments with overlap. * tree-nested.c (get_static_chain): Adjust for MEM_REF. (get_frame_field): Likewise. (get_nonlocal_debug_decl): Likewise. (convert_nonlocal_reference_op): Likewise. (struct nesting_info): Add mem_refs pointer-set. (create_nesting_tree): Allocate it. (convert_local_reference_op): Insert to be folded mem-refs. (fold_mem_refs): New function. (finalize_nesting_tree_1): Perform defered folding of mem-refs (free_nesting_tree): Free the pointer-set. * tree-vect-stmts.c (vectorizable_store): Adjust for MEM_REF. (vectorizable_load): Likewise. * tree-ssa-phiprop.c (phiprop_insert_phi): Adjust for MEM_REF. (propagate_with_phi): Likewise. * tree-object-size.c (addr_object_size): Handle MEM_REFs instead of INDIRECT_REFs. (compute_object_offset): Handle MEM_REF. (plus_stmt_object_size): Handle MEM_REF. (collect_object_sizes_for): Dispatch to plus_stmt_object_size for &MEM_REF. * tree-flow.h (get_addr_base_and_unit_offset): Declare. (symbol_marked_for_renaming): Likewise. * Makefile.in (tree-dfa.o): Add $(TOPLEV_H). (fold-const.o): Add $(TREE_FLOW_H). * tree-ssa-structalias.c (get_constraint_for_1): Handle MEM_REF. (find_func_clobbers): Likewise. * ipa-struct-reorg.c (decompose_indirect_ref_acc): Handle MEM_REF. (decompose_access): Likewise. (replace_field_acc): Likewise. (replace_field_access_stmt): Likewise. (insert_new_var_in_stmt): Likewise. (get_stmt_accesses): Likewise. (reorg_structs_drive): Disable. * config/i386/i386.c (ix86_va_start): Adjust for MEM_REF. (ix86_canonical_va_list_type): Likewise. cp/ * cp-gimplify.c (cp_gimplify_expr): Open-code the rhs predicate we are looking for, allow non-gimplified INDIRECT_REFs. testsuite/ * gcc.c-torture/execute/20100316-1.c: New testcase. * gcc.c-torture/execute/pr44468.c: Likewise. * gcc.c-torture/compile/20100609-1.c: Likewise. * gcc.dg/volatile2.c: Adjust. * gcc.dg/plugin/selfassign.c: Likewise. * gcc.dg/pr36902.c: Likewise. * gcc.dg/tree-ssa/foldaddr-2.c: Remove. * gcc.dg/tree-ssa/foldaddr-3.c: Likewise. * gcc.dg/tree-ssa/forwprop-8.c: Adjust. * gcc.dg/tree-ssa/pr17141-1.c: Likewise. * gcc.dg/tree-ssa/ssa-fre-13.c: Likewise. * gcc.dg/tree-ssa/ssa-fre-14.c: Likewise. * gcc.dg/tree-ssa/ssa-ccp-21.c: Likewise. * gcc.dg/tree-ssa/pta-ptrarith-1.c: Likewise. * gcc.dg/tree-ssa/20030807-7.c: Likewise. * gcc.dg/tree-ssa/forwprop-10.c: Likewise. * gcc.dg/tree-ssa/ssa-fre-1.c: Likewise. * gcc.dg/tree-ssa/pta-ptrarith-2.c: Likewise. * gcc.dg/tree-ssa/ssa-ccp-23.c: Likewise. * gcc.dg/tree-ssa/forwprop-1.c: Likewise. * gcc.dg/tree-ssa/forwprop-2.c: Likewise. * gcc.dg/tree-ssa/struct-aliasing-1.c: Likewise. * gcc.dg/tree-ssa/ssa-ccp-25.c: Likewise. * gcc.dg/tree-ssa/ssa-pre-26.c: Likewise. * gcc.dg/tree-ssa/struct-aliasing-2.c: Likewise. * gcc.dg/tree-ssa/ssa-ccp-26.c: Likewise. * gcc.dg/tree-ssa/ssa-sccvn-4.c: Likewise. * gcc.dg/tree-ssa/ssa-pre-7.c: Likewise. * gcc.dg/tree-ssa/forwprop-5.c: Likewise. * gcc.dg/struct/w_prof_two_strs.c: XFAIL. * gcc.dg/struct/wo_prof_escape_arg_to_local.c: Likewise. * gcc.dg/struct/wo_prof_global_var.c: Likewise. * gcc.dg/struct/wo_prof_malloc_size_var.c: Likewise. * gcc.dg/struct/w_prof_local_array.c: Likewise. * gcc.dg/struct/w_prof_single_str_global.c: Likewise. * gcc.dg/struct/wo_prof_escape_str_init.c: Likewise. * gcc.dg/struct/wo_prof_array_through_pointer.c: Likewise. * gcc.dg/struct/w_prof_global_array.c: Likewise. * gcc.dg/struct/wo_prof_array_field.c: Likewise. * gcc.dg/struct/wo_prof_single_str_local.c: Likewise. * gcc.dg/struct/w_prof_local_var.c: Likewise. * gcc.dg/struct/wo_prof_two_strs.c: Likewise. * gcc.dg/struct/wo_prof_empty_str.c: Likewise. * gcc.dg/struct/wo_prof_local_array.c: Likewise. * gcc.dg/struct/w_prof_global_var.c: Likewise. * gcc.dg/struct/wo_prof_single_str_global.c: Likewise. * gcc.dg/struct/wo_prof_escape_substr_value.c: Likewise. * gcc.dg/struct/wo_prof_global_array.c: Likewise. * gcc.dg/struct/wo_prof_escape_return.c: Likewise. * gcc.dg/struct/wo_prof_escape_substr_array.c: Likewise. * gcc.dg/struct/wo_prof_double_malloc.c: Likewise. * gcc.dg/struct/w_ratio_cold_str.c: Likewise. * gcc.dg/struct/wo_prof_escape_substr_pointer.c: Likewise. * gcc.dg/struct/wo_prof_local_var.c: Likewise. * gcc.dg/tree-prof/stringop-1.c: Adjust. * g++.dg/tree-ssa/pr31146.C: Likewise. * g++.dg/tree-ssa/copyprop-1.C: Likewise. * g++.dg/tree-ssa/pr33604.C: Likewise. * g++.dg/plugin/selfassign.c: Likewise. * gfortran.dg/array_memcpy_3.f90: Likewise. * gfortran.dg/array_memcpy_4.f90: Likewise. * c-c++-common/torture/pr42834.c: New testcase. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@161655 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/tree-scalar-evolution.c | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) (limited to 'gcc/tree-scalar-evolution.c') diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 13d897fd5ce..0e372567c89 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -1170,6 +1170,24 @@ follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr, halting_phi, evolution_of_loop, limit); break; + case ADDR_EXPR: + /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */ + if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF) + { + expr = TREE_OPERAND (expr, 0); + rhs0 = TREE_OPERAND (expr, 0); + rhs1 = TREE_OPERAND (expr, 1); + type = TREE_TYPE (rhs0); + STRIP_USELESS_TYPE_CONVERSION (rhs0); + STRIP_USELESS_TYPE_CONVERSION (rhs1); + res = follow_ssa_edge_binary (loop, at_stmt, type, + rhs0, POINTER_PLUS_EXPR, rhs1, + halting_phi, evolution_of_loop, limit); + } + else + 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. */ -- cgit v1.2.1