diff options
| -rw-r--r-- | gcc/ChangeLog | 23 | ||||
| -rw-r--r-- | gcc/Makefile.in | 2 | ||||
| -rw-r--r-- | gcc/cfgloop.h | 128 | ||||
| -rw-r--r-- | gcc/doc/loop.texi | 15 | ||||
| -rw-r--r-- | gcc/loop-unswitch.c | 2 | ||||
| -rw-r--r-- | gcc/modulo-sched.c | 2 | ||||
| -rw-r--r-- | gcc/tree-chrec.c | 59 | ||||
| -rw-r--r-- | gcc/tree-scalar-evolution.c | 15 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-unswitch.c | 2 | ||||
| -rw-r--r-- | gcc/tree-vectorizer.c | 2 |
10 files changed, 178 insertions, 72 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 3433a8d1406..78f2b6e8413 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,26 @@ +2007-01-31 Zdenek Dvorak <dvorakz@suse.cz> + + * cfgloop.h: Include vec-prim.h. + (enum li_flags): Remove LI_ONLY_OLD. + (loop_iterator): Changed. + (fel_next, fel_init): Iterate over loop tree. + (FOR_EACH_LOOP_BREAK): New macro. + * loop-unswitch.c (unswitch_loops): Do not pass LI_ONLY_OLD to + FOR_EACH_LOOP. + * tree-ssa-loop-unswitch.c (tree_ssa_unswitch_loops): Ditto. + * modulo-sched.c (sms_schedule): Ditto. + * tree-vectorizer.c (vectorize_loops): Ditto. + * doc/loop.texi: Update information on loop numbering and behavior of + FOR_EACH_LOOP wrto new loops. + * tree-scalar-evolution.c (compute_overall_effect_of_inner_loop, + add_to_evolution_1): Test nestedness of loops instead of comparing + their numbers. + * tree-chrec.c (chrec_fold_plus_poly_poly, + chrec_fold_multiply_poly_poly, chrec_evaluate, + hide_evolution_in_other_loops_than_loop, chrec_component_in_loop_num, + reset_evolution_in_loop): Ditto. + * Makefile.in (CFGLOOP_H): Add vecprim.h dependency. + 2007-01-31 Dirk Mueller <dmueller@suse.de> * c-common.c (warn_about_parentheses): Separate warning about diff --git a/gcc/Makefile.in b/gcc/Makefile.in index b569b36dc00..f5cc3a8f590 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -749,7 +749,7 @@ RESOURCE_H = resource.h hard-reg-set.h SCHED_INT_H = sched-int.h $(INSN_ATTR_H) $(BASIC_BLOCK_H) $(RTL_H) INTEGRATE_H = integrate.h $(VARRAY_H) CFGLAYOUT_H = cfglayout.h $(BASIC_BLOCK_H) -CFGLOOP_H = cfgloop.h $(BASIC_BLOCK_H) $(RTL_H) +CFGLOOP_H = cfgloop.h $(BASIC_BLOCK_H) $(RTL_H) vecprim.h IPA_UTILS_H = ipa-utils.h $(TREE_H) $(CGRAPH_H) IPA_REFERENCE_H = ipa-reference.h bitmap.h $(TREE_H) IPA_TYPE_ESCAPE_H = ipa-type-escape.h $(TREE_H) diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index 0e1b13a94f4..4223a39c45f 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -25,6 +25,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "basic-block.h" /* For rtx_code. */ #include "rtl.h" +#include "vecprim.h" /* Structure to hold decision about unrolling/peeling. */ enum lpt_dec @@ -425,84 +426,127 @@ number_of_loops (void) enum li_flags { - LI_INCLUDE_ROOT = 1, /* Include the fake root of the loop tree. */ - LI_FROM_INNERMOST = 2,/* Iterate over the loops in the reverse order, - starting from innermost ones. */ - LI_ONLY_INNERMOST = 4,/* Iterate only over innermost loops. */ - LI_ONLY_OLD = 8 /* Do not traverse the loops created during the - traversal (this is the default behavior with - LI_FROM_INNERMOST). */ + LI_INCLUDE_ROOT = 1, /* Include the fake root of the loop tree. */ + LI_FROM_INNERMOST = 2, /* Iterate over the loops in the reverse order, + starting from innermost ones. */ + LI_ONLY_INNERMOST = 4 /* Iterate only over innermost loops. */ }; /* The iterator for loops. */ typedef struct { - int idx; /* Index of the actual loop. */ - int end; /* Only loops before end should be traversed. */ + /* The list of loops to visit. */ + VEC(int,heap) *to_visit; + + /* The index of the actual loop. */ + unsigned idx; } loop_iterator; static inline void -fel_next (loop_iterator *li, loop_p *loop, unsigned flags) +fel_next (loop_iterator *li, loop_p *loop) { - if (flags & LI_FROM_INNERMOST) - { - li->idx--; - for (; li->idx > li->end; li->idx--) - { - *loop = VEC_index (loop_p, current_loops->larray, li->idx); - if (*loop - && (!(flags & LI_ONLY_INNERMOST) - || (*loop)->inner == NULL)) - return; - } - } - else + int anum; + + while (VEC_iterate (int, li->to_visit, li->idx, anum)) { - if (!(flags & LI_ONLY_OLD)) - li->end = number_of_loops (); li->idx++; - for (; li->idx < li->end; li->idx++) - { - *loop = VEC_index (loop_p, current_loops->larray, li->idx); - if (*loop - && (!(flags & LI_ONLY_INNERMOST) - || (*loop)->inner == NULL)) - return; - } + *loop = get_loop (anum); + if (*loop) + return; } + VEC_free (int, heap, li->to_visit); *loop = NULL; } static inline void fel_init (loop_iterator *li, loop_p *loop, unsigned flags) { + struct loop *aloop; + unsigned i; + int mn; + + li->idx = 0; if (!current_loops) { - li->idx = 0; - li->end = 0; + li->to_visit = NULL; *loop = NULL; return; } - if (flags & LI_FROM_INNERMOST) + li->to_visit = VEC_alloc (int, heap, number_of_loops ()); + mn = (flags & LI_INCLUDE_ROOT) ? 0 : 1; + + if (flags & LI_ONLY_INNERMOST) + { + for (i = 0; VEC_iterate (loop_p, current_loops->larray, i, aloop); i++) + if (aloop != NULL + && aloop->inner == NULL + && aloop->num >= mn) + VEC_quick_push (int, li->to_visit, aloop->num); + } + else if (flags & LI_FROM_INNERMOST) { - li->idx = number_of_loops (); - li->end = (flags & LI_INCLUDE_ROOT) ? -1 : 0; + /* Push the loops to LI->TO_VISIT in postorder. */ + for (aloop = current_loops->tree_root; + aloop->inner != NULL; + aloop = aloop->inner) + continue; + + while (1) + { + if (aloop->num >= mn) + VEC_quick_push (int, li->to_visit, aloop->num); + + if (aloop->next) + { + for (aloop = aloop->next; + aloop->inner != NULL; + aloop = aloop->inner) + continue; + } + else if (!aloop->outer) + break; + else + aloop = aloop->outer; + } } else { - li->idx = (flags & LI_INCLUDE_ROOT) ? -1 : 0; - li->end = number_of_loops (); + /* Push the loops to LI->TO_VISIT in preorder. */ + aloop = current_loops->tree_root; + while (1) + { + if (aloop->num >= mn) + VEC_quick_push (int, li->to_visit, aloop->num); + + if (aloop->inner != NULL) + aloop = aloop->inner; + else + { + while (aloop != NULL && aloop->next == NULL) + aloop = aloop->outer; + if (aloop == NULL) + break; + aloop = aloop->next; + } + } } - fel_next (li, loop, flags); + + fel_next (li, loop); } #define FOR_EACH_LOOP(LI, LOOP, FLAGS) \ for (fel_init (&(LI), &(LOOP), FLAGS); \ (LOOP); \ - fel_next (&(LI), &(LOOP), FLAGS)) + fel_next (&(LI), &(LOOP))) + +#define FOR_EACH_LOOP_BREAK(LI) \ + { \ + VEC_free (int, heap, (LI)->to_visit); \ + break; \ + } /* The properties of the target. */ diff --git a/gcc/doc/loop.texi b/gcc/doc/loop.texi index fade89d32e8..e486b0c5d10 100644 --- a/gcc/doc/loop.texi +++ b/gcc/doc/loop.texi @@ -64,17 +64,24 @@ function. Each of the loops is represented in a @code{struct loop} structure. Each loop is assigned an index (@code{num} field of the @code{struct loop} structure), and the pointer to the loop is stored in the corresponding field of the @code{larray} vector in the loops -structure. Index of a sub-loop is always greater than the index of its -super-loop. The indices do not have to be continuous, there may be +structure. The indices do not have to be continuous, there may be empty (@code{NULL}) entries in the @code{larray} created by deleting -loops. The index of a loop never changes. +loops. Also, there is no guarantee on the relative order of a loop +and its subloops in the numbering. The index of a loop never changes. The entries of the @code{larray} field should not be accessed directly. The function @code{get_loop} returns the loop description for a loop with the given index. @code{number_of_loops} function returns number of loops in the function. To traverse all loops, use @code{FOR_EACH_LOOP} macro. The @code{flags} argument of the macro is used to determine -the direction of traversal and the set of loops visited. +the direction of traversal and the set of loops visited. Each loop is +guaranteed to be visited exactly once, regardless of the changes to the +loop tree, and the loops may be removed during the traversal. The newly +created loops are never traversed, if they need to be visited, this +must be done separately after their creation. The @code{FOR_EACH_LOOP} +macro allocates temporary variables. If the @code{FOR_EACH_LOOP} loop +were ended using break or goto, they would not be released; +@code{FOR_EACH_LOOP_BREAK} macro must be used instead. Each basic block contains the reference to the innermost loop it belongs to (@code{loop_father}). For this reason, it is only possible to have diff --git a/gcc/loop-unswitch.c b/gcc/loop-unswitch.c index 05530adcfaf..8eb21d6ec2b 100644 --- a/gcc/loop-unswitch.c +++ b/gcc/loop-unswitch.c @@ -143,7 +143,7 @@ unswitch_loops (void) /* Go through inner loops (only original ones). */ - FOR_EACH_LOOP (li, loop, LI_ONLY_OLD | LI_ONLY_INNERMOST) + FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) { unswitch_single_loop (loop, NULL_RTX, 0); #ifdef ENABLE_CHECKING diff --git a/gcc/modulo-sched.c b/gcc/modulo-sched.c index 1b6f7eec13c..228c3f985cc 100644 --- a/gcc/modulo-sched.c +++ b/gcc/modulo-sched.c @@ -1028,7 +1028,7 @@ sms_schedule (void) df = NULL; /* We don't want to perform SMS on new loops - created by versioning. */ - FOR_EACH_LOOP (li, loop, LI_ONLY_OLD) + FOR_EACH_LOOP (li, loop, 0) { rtx head, tail; rtx count_reg, count_init; diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c index 66738d35d09..ae95fc8c496 100644 --- a/gcc/tree-chrec.c +++ b/gcc/tree-chrec.c @@ -99,6 +99,8 @@ chrec_fold_plus_poly_poly (enum tree_code code, tree poly1) { tree left, right; + struct loop *loop0 = get_chrec_loop (poly0); + struct loop *loop1 = get_chrec_loop (poly1); gcc_assert (poly0); gcc_assert (poly1); @@ -111,7 +113,7 @@ chrec_fold_plus_poly_poly (enum tree_code code, {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2, {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2, {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */ - if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1)) + if (flow_loop_nested_p (loop0, loop1)) { if (code == PLUS_EXPR) return build_polynomial_chrec @@ -128,7 +130,7 @@ chrec_fold_plus_poly_poly (enum tree_code code, : build_int_cst_type (type, -1))); } - if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (poly1)) + if (flow_loop_nested_p (loop1, loop0)) { if (code == PLUS_EXPR) return build_polynomial_chrec @@ -141,7 +143,11 @@ chrec_fold_plus_poly_poly (enum tree_code code, chrec_fold_minus (type, CHREC_LEFT (poly0), poly1), CHREC_RIGHT (poly0)); } - + + /* This function should never be called for chrecs of loops that + do not belong to the same loop nest. */ + gcc_assert (loop0 == loop1); + if (code == PLUS_EXPR) { left = chrec_fold_plus @@ -175,6 +181,8 @@ chrec_fold_multiply_poly_poly (tree type, { tree t0, t1, t2; int var; + struct loop *loop0 = get_chrec_loop (poly0); + struct loop *loop1 = get_chrec_loop (poly1); gcc_assert (poly0); gcc_assert (poly1); @@ -186,20 +194,22 @@ chrec_fold_multiply_poly_poly (tree type, /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2, {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2, {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ - if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1)) + if (flow_loop_nested_p (loop0, loop1)) /* poly0 is a constant wrt. poly1. */ return build_polynomial_chrec (CHREC_VARIABLE (poly1), chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0), CHREC_RIGHT (poly1)); - if (CHREC_VARIABLE (poly1) < CHREC_VARIABLE (poly0)) + if (flow_loop_nested_p (loop1, loop0)) /* poly1 is a constant wrt. poly0. */ return build_polynomial_chrec (CHREC_VARIABLE (poly0), chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1), CHREC_RIGHT (poly0)); - + + gcc_assert (loop0 == loop1); + /* poly0 and poly1 are two polynomials in the same variable, {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ @@ -492,9 +502,10 @@ chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k) { tree arg0, arg1, binomial_n_k; tree type = TREE_TYPE (chrec); + struct loop *var_loop = get_loop (var); while (TREE_CODE (chrec) == POLYNOMIAL_CHREC - && CHREC_VARIABLE (chrec) > var) + && flow_loop_nested_p (var_loop, get_chrec_loop (chrec))) chrec = CHREC_LEFT (chrec); if (TREE_CODE (chrec) == POLYNOMIAL_CHREC @@ -631,26 +642,32 @@ tree hide_evolution_in_other_loops_than_loop (tree chrec, unsigned loop_num) { + struct loop *loop = get_loop (loop_num), *chloop; if (automatically_generated_chrec_p (chrec)) return chrec; switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: - if (CHREC_VARIABLE (chrec) == loop_num) + chloop = get_chrec_loop (chrec); + + if (chloop == loop) return build_polynomial_chrec (loop_num, hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), loop_num), CHREC_RIGHT (chrec)); - else if (CHREC_VARIABLE (chrec) < loop_num) + else if (flow_loop_nested_p (chloop, loop)) /* There is no evolution in this loop. */ return initial_condition (chrec); else - return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), - loop_num); + { + gcc_assert (flow_loop_nested_p (loop, chloop)); + return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), + loop_num); + } default: return chrec; @@ -666,6 +683,7 @@ chrec_component_in_loop_num (tree chrec, bool right) { tree component; + struct loop *loop = get_loop (loop_num), *chloop; if (automatically_generated_chrec_p (chrec)) return chrec; @@ -673,7 +691,9 @@ chrec_component_in_loop_num (tree chrec, switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: - if (CHREC_VARIABLE (chrec) == loop_num) + chloop = get_chrec_loop (chrec); + + if (chloop == loop) { if (right) component = CHREC_RIGHT (chrec); @@ -693,14 +713,17 @@ chrec_component_in_loop_num (tree chrec, component); } - else if (CHREC_VARIABLE (chrec) < loop_num) + else if (flow_loop_nested_p (chloop, loop)) /* There is no evolution part in this loop. */ return NULL_TREE; else - return chrec_component_in_loop_num (CHREC_LEFT (chrec), - loop_num, - right); + { + gcc_assert (flow_loop_nested_p (loop, chloop)); + return chrec_component_in_loop_num (CHREC_LEFT (chrec), + loop_num, + right); + } default: if (right) @@ -742,10 +765,12 @@ reset_evolution_in_loop (unsigned loop_num, tree chrec, tree new_evol) { + struct loop *loop = get_loop (loop_num); + gcc_assert (chrec_type (chrec) == chrec_type (new_evol)); if (TREE_CODE (chrec) == POLYNOMIAL_CHREC - && CHREC_VARIABLE (chrec) > loop_num) + && flow_loop_nested_p (loop, get_chrec_loop (chrec))) { tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), new_evol); diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index a1fe07a9dc8..43a5e27ddba 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -465,9 +465,11 @@ compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC) { - if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num) + struct loop *inner_loop = get_chrec_loop (evolution_fn); + + if (inner_loop == loop + || flow_loop_nested_p (loop, inner_loop)) { - struct loop *inner_loop = get_chrec_loop (evolution_fn); tree nb_iter = number_of_latch_executions (inner_loop); if (nb_iter == chrec_dont_know) @@ -646,18 +648,21 @@ add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, tree at_stmt) { tree type, left, right; + struct loop *loop = get_loop (loop_nb), *chloop; switch (TREE_CODE (chrec_before)) { case POLYNOMIAL_CHREC: - if (CHREC_VARIABLE (chrec_before) <= loop_nb) + chloop = get_chrec_loop (chrec_before); + if (chloop == loop + || flow_loop_nested_p (chloop, loop)) { unsigned var; type = chrec_type (chrec_before); /* When there is no evolution part in this loop, build it. */ - if (CHREC_VARIABLE (chrec_before) < loop_nb) + if (chloop != loop) { var = loop_nb; left = chrec_before; @@ -679,6 +684,8 @@ add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, } else { + gcc_assert (flow_loop_nested_p (loop, chloop)); + /* Search the evolution in LOOP_NB. */ left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_add, at_stmt); diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c index c646ef395c7..b9bd3724ba9 100644 --- a/gcc/tree-ssa-loop-unswitch.c +++ b/gcc/tree-ssa-loop-unswitch.c @@ -88,7 +88,7 @@ tree_ssa_unswitch_loops (void) bool changed = false; /* Go through inner loops (only original ones). */ - FOR_EACH_LOOP (li, loop, LI_ONLY_OLD | LI_ONLY_INNERMOST) + FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) { changed |= tree_unswitch_single_loop (loop, 0); } diff --git a/gcc/tree-vectorizer.c b/gcc/tree-vectorizer.c index ef805955efc..870163df754 100644 --- a/gcc/tree-vectorizer.c +++ b/gcc/tree-vectorizer.c @@ -2175,7 +2175,7 @@ vectorize_loops (void) than all previously defined loops. This fact allows us to run only over initial loops skipping newly generated ones. */ vect_loops_num = number_of_loops (); - FOR_EACH_LOOP (li, loop, LI_ONLY_OLD) + FOR_EACH_LOOP (li, loop, 0) { loop_vec_info loop_vinfo; |