From eaa67821647daeff7d98a79505318aceae250370 Mon Sep 17 00:00:00 2001 From: davidxl Date: Tue, 27 Jul 2010 18:18:25 +0000 Subject: [PATCH] Multiple exit loop handling in ivopts. Regression tested on x86-64/linux git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@162585 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 9 ++++ gcc/tree-ssa-loop-ivopts.c | 100 +++++++++++++++++++++++++++++++++------------ 2 files changed, 82 insertions(+), 27 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 043c4015134..e4435ba45ea 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,12 @@ +2010-07-27 Xinliang David Li + + * tree-ssa-loop-ivopts.c (niter_for_exit): New parameter. + (niter_for_single_dom_exit): Passes additional parameter. + (iv_period): Fix comments. + (may_eliminate_iv): Handles multiple exit loops properly. + (free_tree_niter_desc): New function. + (free_loop_data): Frees up loop iteration descriptors. + 2010-07-27 Jakub Jelinek PR target/44542 diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index c7d534b1f5f..30ddb75520d 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -718,9 +718,10 @@ contains_abnormal_ssa_name_p (tree expr) EXIT of DATA->current_loop, or NULL if something goes wrong. */ static tree -niter_for_exit (struct ivopts_data *data, edge exit) +niter_for_exit (struct ivopts_data *data, edge exit, + struct tree_niter_desc **desc_p) { - struct tree_niter_desc desc; + struct tree_niter_desc* desc = NULL; tree niter; void **slot; @@ -739,19 +740,24 @@ niter_for_exit (struct ivopts_data *data, edge exit) being zero). Also, we cannot safely work with ssa names that appear in phi nodes on abnormal edges, so that we do not create overlapping life ranges for them (PR 27283). */ + desc = XNEW (struct tree_niter_desc); if (number_of_iterations_exit (data->current_loop, - exit, &desc, true) - && integer_zerop (desc.may_be_zero) - && !contains_abnormal_ssa_name_p (desc.niter)) - niter = desc.niter; + exit, desc, true) + && integer_zerop (desc->may_be_zero) + && !contains_abnormal_ssa_name_p (desc->niter)) + niter = desc->niter; else niter = NULL_TREE; - *pointer_map_insert (data->niters, exit) = niter; + desc->niter = niter; + slot = pointer_map_insert (data->niters, exit); + *slot = desc; } else - niter = (tree) *slot; + niter = ((struct tree_niter_desc *) *slot)->niter; + if (desc_p) + *desc_p = (struct tree_niter_desc *) *slot; return niter; } @@ -767,7 +773,7 @@ niter_for_single_dom_exit (struct ivopts_data *data) if (!exit) return NULL; - return niter_for_exit (data, exit); + return niter_for_exit (data, exit, NULL); } /* Initializes data structures used by the iv optimization pass, stored @@ -4005,15 +4011,20 @@ iv_period (struct iv *iv) gcc_assert (step && TREE_CODE (step) == INTEGER_CST); - /* Period of the iv is gcd (step, type range). Since type range is power - of two, it suffices to determine the maximum power of two that divides - step. */ - pow2div = num_ending_zeros (step); type = unsigned_type_for (TREE_TYPE (step)); + /* Period of the iv is lcm (step, type_range)/step -1, + i.e., N*type_range/step - 1. Since type range is power + of two, N == (step >> num_of_ending_zeros_binary (step), + so the final result is + + (type_range >> num_of_ending_zeros_binary (step)) - 1 + + */ + pow2div = num_ending_zeros (step); period = build_low_bits_mask (type, - (TYPE_PRECISION (type) - - tree_low_cst (pow2div, 1))); + (TYPE_PRECISION (type) + - tree_low_cst (pow2div, 1))); return period; } @@ -4047,6 +4058,7 @@ may_eliminate_iv (struct ivopts_data *data, tree nit, period; struct loop *loop = data->current_loop; aff_tree bnd; + struct tree_niter_desc *desc = NULL; if (TREE_CODE (cand->iv->step) != INTEGER_CST) return false; @@ -4065,7 +4077,7 @@ may_eliminate_iv (struct ivopts_data *data, if (flow_bb_inside_loop_p (loop, exit->dest)) return false; - nit = niter_for_exit (data, exit); + nit = niter_for_exit (data, exit, &desc); if (!nit) return false; @@ -4077,27 +4089,46 @@ may_eliminate_iv (struct ivopts_data *data, /* If the number of iterations is constant, compare against it directly. */ if (TREE_CODE (nit) == INTEGER_CST) { - if (!tree_int_cst_lt (nit, period)) - return false; + /* See cand_value_at. */ + if (stmt_after_increment (loop, cand, use->stmt)) + { + if (!tree_int_cst_lt (nit, period)) + return false; + } + else + { + if (tree_int_cst_lt (period, nit)) + return false; + } } /* If not, and if this is the only possible exit of the loop, see whether we can get a conservative estimate on the number of iterations of the entire loop and compare against that instead. */ - else if (loop_only_exit_p (loop, exit)) + else { double_int period_value, max_niter; - if (!estimated_loop_iterations (loop, true, &max_niter)) - return false; + + max_niter = desc->max; + if (stmt_after_increment (loop, cand, use->stmt)) + max_niter = double_int_add (max_niter, double_int_one); period_value = tree_to_double_int (period); - if (double_int_ucmp (max_niter, period_value) >= 0) - return false; + if (double_int_ucmp (max_niter, period_value) > 0) + { + /* See if we can take advantage of infered loop bound information. */ + if (loop_only_exit_p (loop, exit)) + { + if (!estimated_loop_iterations (loop, true, &max_niter)) + return false; + /* The loop bound is already adjusted by adding 1. */ + if (double_int_ucmp (max_niter, period_value) > 0) + return false; + } + else + return false; + } } - /* Otherwise, punt. */ - else - return false; - cand_value_at (loop, cand, use->stmt, nit, &bnd); *bound = aff_combination_to_tree (&bnd); @@ -4108,6 +4139,7 @@ may_eliminate_iv (struct ivopts_data *data, return true; } + /* Determines cost of basing replacement of USE on CAND in a condition. */ static bool @@ -5779,6 +5811,19 @@ remove_unused_ivs (struct ivopts_data *data) BITMAP_FREE (toremove); } +/* Frees memory occupied by struct tree_niter_desc in *VALUE. Callback + for pointer_map_traverse. */ + +static bool +free_tree_niter_desc (const void *key ATTRIBUTE_UNUSED, void **value, + void *data ATTRIBUTE_UNUSED) +{ + struct tree_niter_desc *const niter = (struct tree_niter_desc *) *value; + + free (niter); + return true; +} + /* Frees data allocated by the optimization of a single loop. */ static void @@ -5790,6 +5835,7 @@ free_loop_data (struct ivopts_data *data) if (data->niters) { + pointer_map_traverse (data->niters, free_tree_niter_desc, NULL); pointer_map_destroy (data->niters); data->niters = NULL; } -- 2.11.4.GIT