X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Floop-unroll.c;h=8812e68805baab628640cd55345971c7afadaea8;hb=d3832055fda2ca4c70c534b5638eb8f018ea3225;hp=776b2e1f6b15f854d14cfb6364372129a9d2fcfc;hpb=7194de72e1651831d842524a0d0a01f64f8f98ed;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/loop-unroll.c b/gcc/loop-unroll.c index 776b2e1f6b1..8812e68805b 100644 --- a/gcc/loop-unroll.c +++ b/gcc/loop-unroll.c @@ -1,11 +1,12 @@ /* Loop unrolling and peeling. - Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008 + Free Software Foundation, Inc. This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free -Software Foundation; either version 2, or (at your option) any later +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -14,9 +15,8 @@ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA -02110-1301, USA. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" @@ -77,6 +77,7 @@ struct iv_to_split rtx base_var; /* The variable on that the values in the further iterations are based. */ rtx step; /* Step of the induction variable. */ + struct iv_to_split *next; /* Next entry in walking order. */ unsigned n_loc; unsigned loc[3]; /* Location where the definition of the induction variable occurs in the insn. For example if @@ -91,6 +92,7 @@ struct var_to_expand rtx insn; /* The insn in that the variable expansion occurs. */ rtx reg; /* The accumulator which is expanded. */ VEC(rtx,heap) *var_expansions; /* The copies of the accumulator which is expanded. */ + struct var_to_expand *next; /* Next entry in walking order. */ enum rtx_code op; /* The type of the accumulation - addition, subtraction or multiplication. */ int expansion_count; /* Count the number of expansions generated so far. */ @@ -98,6 +100,10 @@ struct var_to_expand the accumulator. If REUSE_EXPANSION is 0 reuse the original accumulator. Else use var_expansions[REUSE_EXPANSION - 1]. */ + unsigned accum_pos; /* The position in which the accumulator is placed in + the insn src. For example in x = x + something + accum_pos is 0 while in x = something + x accum_pos + is 1. */ }; /* Information about optimization applied in @@ -106,8 +112,12 @@ struct var_to_expand struct opt_info { htab_t insns_to_split; /* A hashtable of insns to split. */ + struct iv_to_split *iv_to_split_head; /* The first iv to split. */ + struct iv_to_split **iv_to_split_tail; /* Pointer to the tail of the list. */ htab_t insns_with_var_to_expand; /* A hashtable of insns with accumulators to expand. */ + struct var_to_expand *var_to_expand_head; /* The first var to expand. */ + struct var_to_expand **var_to_expand_tail; /* Pointer to the tail of the list. */ unsigned first_new_block; /* The first basic block that was duplicated. */ basic_block loop_exit; /* The loop exit basic block. */ @@ -135,17 +145,19 @@ static struct var_to_expand *analyze_insn_to_expand_var (struct loop*, rtx); static bool referenced_in_one_insn_in_loop_p (struct loop *, rtx); static struct iv_to_split *analyze_iv_to_split_insn (rtx); static void expand_var_during_unrolling (struct var_to_expand *, rtx); -static int insert_var_expansion_initialization (void **, void *); -static int combine_var_copies_in_loop_exit (void **, void *); -static int release_var_copies (void **, void *); +static void insert_var_expansion_initialization (struct var_to_expand *, + basic_block); +static void combine_var_copies_in_loop_exit (struct var_to_expand *, + basic_block); static rtx get_expansion (struct var_to_expand *); /* Unroll and/or peel (depending on FLAGS) LOOPS. */ void unroll_and_peel_loops (int flags) { - struct loop *loop, *next; + struct loop *loop; bool check; + loop_iterator li; /* First perform complete loop peeling (it is almost surely a win, and affects parameters for further decision a lot). */ @@ -154,22 +166,9 @@ unroll_and_peel_loops (int flags) /* Now decide rest of unrolling and peeling. */ decide_unrolling_and_peeling (flags); - loop = current_loops->tree_root; - while (loop->inner) - loop = loop->inner; - /* Scan the loops, inner ones first. */ - while (loop != current_loops->tree_root) + FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) { - if (loop->next) - { - next = loop->next; - while (next->inner) - next = next->inner; - } - else - next = loop->outer; - check = true; /* And perform the appropriate transformations. */ switch (loop->lpt_decision.decision) @@ -202,7 +201,6 @@ unroll_and_peel_loops (int flags) verify_loop_structure (); #endif } - loop = next; } iv_analysis_done (); @@ -234,15 +232,11 @@ static void peel_loops_completely (int flags) { struct loop *loop; - unsigned i; + loop_iterator li; /* Scan the loops, the inner ones first. */ - for (i = current_loops->num - 1; i > 0; i--) + FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) { - loop = current_loops->parray[i]; - if (!loop) - continue; - loop->lpt_decision.decision = LPT_NONE; if (dump_file) @@ -271,34 +265,22 @@ peel_loops_completely (int flags) static void decide_unrolling_and_peeling (int flags) { - struct loop *loop = current_loops->tree_root, *next; - - while (loop->inner) - loop = loop->inner; + struct loop *loop; + loop_iterator li; /* Scan the loops, inner ones first. */ - while (loop != current_loops->tree_root) + FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) { - if (loop->next) - { - next = loop->next; - while (next->inner) - next = next->inner; - } - else - next = loop->outer; - loop->lpt_decision.decision = LPT_NONE; if (dump_file) fprintf (dump_file, "\n;; *** Considering loop %d ***\n", loop->num); /* Do not peel cold areas. */ - if (!maybe_hot_bb_p (loop->header)) + if (optimize_loop_for_size_p (loop)) { if (dump_file) fprintf (dump_file, ";; Not considering loop, cold area\n"); - loop = next; continue; } @@ -308,7 +290,6 @@ decide_unrolling_and_peeling (int flags) if (dump_file) fprintf (dump_file, ";; Not considering loop, cannot duplicate\n"); - loop = next; continue; } @@ -317,7 +298,6 @@ decide_unrolling_and_peeling (int flags) { if (dump_file) fprintf (dump_file, ";; Not considering loop, is not innermost\n"); - loop = next; continue; } @@ -334,8 +314,6 @@ decide_unrolling_and_peeling (int flags) decide_unroll_stupid (loop, flags); if (loop->lpt_decision.decision == LPT_NONE) decide_peel_simple (loop, flags); - - loop = next; } } @@ -398,7 +376,7 @@ decide_peel_completely (struct loop *loop, int flags ATTRIBUTE_UNUSED) } /* Do not peel cold areas. */ - if (!maybe_hot_bb_p (loop->header)) + if (optimize_loop_for_size_p (loop)) { if (dump_file) fprintf (dump_file, ";; Not considering loop, cold area\n"); @@ -479,8 +457,9 @@ peel_loop_completely (struct loop *loop) { sbitmap wont_exit; unsigned HOST_WIDE_INT npeel; - unsigned n_remove_edges, i; - edge *remove_edges, ein; + unsigned i; + VEC (edge, heap) *remove_edges; + edge ein; struct niter_desc *desc = get_simple_loop_desc (loop); struct opt_info *opt_info = NULL; @@ -496,8 +475,7 @@ peel_loop_completely (struct loop *loop) if (desc->noloop_assumptions) RESET_BIT (wont_exit, 1); - remove_edges = XCNEWVEC (edge, npeel); - n_remove_edges = 0; + remove_edges = NULL; if (flag_split_ivs_in_unroller) opt_info = analyze_insns_in_loop (loop); @@ -506,7 +484,7 @@ peel_loop_completely (struct loop *loop) ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), npeel, wont_exit, desc->out_edge, - remove_edges, &n_remove_edges, + &remove_edges, DLTHE_FLAG_UPDATE_FREQ | DLTHE_FLAG_COMPLETTE_PEEL | (opt_info @@ -522,9 +500,9 @@ peel_loop_completely (struct loop *loop) } /* Remove the exit edges. */ - for (i = 0; i < n_remove_edges; i++) - remove_path (remove_edges[i]); - free (remove_edges); + for (i = 0; VEC_iterate (edge, remove_edges, i, ein); i++) + remove_path (ein); + VEC_free (edge, heap, remove_edges); } ein = desc->in_edge; @@ -663,8 +641,9 @@ unroll_loop_constant_iterations (struct loop *loop) unsigned HOST_WIDE_INT niter; unsigned exit_mod; sbitmap wont_exit; - unsigned n_remove_edges, i; - edge *remove_edges; + unsigned i; + VEC (edge, heap) *remove_edges; + edge e; unsigned max_unroll = loop->lpt_decision.times; struct niter_desc *desc = get_simple_loop_desc (loop); bool exit_at_end = loop_exit_at_end_p (loop); @@ -681,8 +660,7 @@ unroll_loop_constant_iterations (struct loop *loop) wont_exit = sbitmap_alloc (max_unroll + 1); sbitmap_ones (wont_exit); - remove_edges = XCNEWVEC (edge, max_unroll + exit_mod + 1); - n_remove_edges = 0; + remove_edges = NULL; if (flag_split_ivs_in_unroller || flag_variable_expansion_in_unroller) opt_info = analyze_insns_in_loop (loop); @@ -707,7 +685,7 @@ unroll_loop_constant_iterations (struct loop *loop) ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), exit_mod, wont_exit, desc->out_edge, - remove_edges, &n_remove_edges, + &remove_edges, DLTHE_FLAG_UPDATE_FREQ | (opt_info && exit_mod > 1 ? DLTHE_RECORD_COPY_NUMBER @@ -746,7 +724,7 @@ unroll_loop_constant_iterations (struct loop *loop) ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), exit_mod + 1, wont_exit, desc->out_edge, - remove_edges, &n_remove_edges, + &remove_edges, DLTHE_FLAG_UPDATE_FREQ | (opt_info && exit_mod > 0 ? DLTHE_RECORD_COPY_NUMBER @@ -773,7 +751,7 @@ unroll_loop_constant_iterations (struct loop *loop) ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop), max_unroll, wont_exit, desc->out_edge, - remove_edges, &n_remove_edges, + &remove_edges, DLTHE_FLAG_UPDATE_FREQ | (opt_info ? DLTHE_RECORD_COPY_NUMBER @@ -810,9 +788,9 @@ unroll_loop_constant_iterations (struct loop *loop) desc->niter_expr = GEN_INT (desc->niter); /* Remove the edges. */ - for (i = 0; i < n_remove_edges; i++) - remove_path (remove_edges[i]); - free (remove_edges); + for (i = 0; VEC_iterate (edge, remove_edges, i, e); i++) + remove_path (e); + VEC_free (edge, heap, remove_edges); if (dump_file) fprintf (dump_file, @@ -912,7 +890,37 @@ split_edge_and_insert (edge e, rtx insns) return NULL; bb = split_edge (e); emit_insn_after (insns, BB_END (bb)); - bb->flags |= BB_SUPERBLOCK; + + /* ??? We used to assume that INSNS can contain control flow insns, and + that we had to try to find sub basic blocks in BB to maintain a valid + CFG. For this purpose we used to set the BB_SUPERBLOCK flag on BB + and call break_superblocks when going out of cfglayout mode. But it + turns out that this never happens; and that if it does ever happen, + the verify_flow_info call in loop_optimizer_finalize would fail. + + There are two reasons why we expected we could have control flow insns + in INSNS. The first is when a comparison has to be done in parts, and + the second is when the number of iterations is computed for loops with + the number of iterations known at runtime. In both cases, test cases + to get control flow in INSNS appear to be impossible to construct: + + * If do_compare_rtx_and_jump needs several branches to do comparison + in a mode that needs comparison by parts, we cannot analyze the + number of iterations of the loop, and we never get to unrolling it. + + * The code in expand_divmod that was suspected to cause creation of + branching code seems to be only accessed for signed division. The + divisions used by # of iterations analysis are always unsigned. + Problems might arise on architectures that emits branching code + for some operations that may appear in the unroller (especially + for division), but we have no such architectures. + + Considering all this, it was decided that we should for now assume + that INSNS can in theory contain control flow insns, but in practice + it never does. So we don't handle the theoretical case, and should + a real failure ever show up, we have a pretty good clue for how to + fix it. */ + return bb; } @@ -952,12 +960,13 @@ unroll_loop_runtime_iterations (struct loop *loop) { rtx old_niter, niter, init_code, branch_code, tmp; unsigned i, j, p; - basic_block preheader, *body, *dom_bbs, swtch, ezc_swtch; - unsigned n_dom_bbs; + basic_block preheader, *body, swtch, ezc_swtch; + VEC (basic_block, heap) *dom_bbs; sbitmap wont_exit; int may_exit_copy; - unsigned n_peel, n_remove_edges; - edge *remove_edges, e; + unsigned n_peel; + VEC (edge, heap) *remove_edges; + edge e; bool extra_zero_check, last_may_exit; unsigned max_unroll = loop->lpt_decision.times; struct niter_desc *desc = get_simple_loop_desc (loop); @@ -970,21 +979,20 @@ unroll_loop_runtime_iterations (struct loop *loop) opt_info = analyze_insns_in_loop (loop); /* Remember blocks whose dominators will have to be updated. */ - dom_bbs = XCNEWVEC (basic_block, n_basic_blocks); - n_dom_bbs = 0; + dom_bbs = NULL; body = get_loop_body (loop); for (i = 0; i < loop->num_nodes; i++) { - unsigned nldom; - basic_block *ldom; + VEC (basic_block, heap) *ldom; + basic_block bb; - nldom = get_dominated_by (CDI_DOMINATORS, body[i], &ldom); - for (j = 0; j < nldom; j++) - if (!flow_bb_inside_loop_p (loop, ldom[j])) - dom_bbs[n_dom_bbs++] = ldom[j]; + ldom = get_dominated_by (CDI_DOMINATORS, body[i]); + for (j = 0; VEC_iterate (basic_block, ldom, j, bb); j++) + if (!flow_bb_inside_loop_p (loop, bb)) + VEC_safe_push (basic_block, heap, dom_bbs, bb); - free (ldom); + VEC_free (basic_block, heap, ldom); } free (body); @@ -1024,12 +1032,12 @@ unroll_loop_runtime_iterations (struct loop *loop) init_code = get_insns (); end_sequence (); + unshare_all_rtl_in_chain (init_code); /* Precondition the loop. */ split_edge_and_insert (loop_preheader_edge (loop), init_code); - remove_edges = XCNEWVEC (edge, max_unroll + n_peel + 1); - n_remove_edges = 0; + remove_edges = NULL; wont_exit = sbitmap_alloc (max_unroll + 2); @@ -1044,7 +1052,7 @@ unroll_loop_runtime_iterations (struct loop *loop) ezc_swtch = loop_preheader_edge (loop)->src; ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), 1, wont_exit, desc->out_edge, - remove_edges, &n_remove_edges, + &remove_edges, DLTHE_FLAG_UPDATE_FREQ); gcc_assert (ok); @@ -1059,7 +1067,7 @@ unroll_loop_runtime_iterations (struct loop *loop) SET_BIT (wont_exit, 1); ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), 1, wont_exit, desc->out_edge, - remove_edges, &n_remove_edges, + &remove_edges, DLTHE_FLAG_UPDATE_FREQ); gcc_assert (ok); @@ -1104,7 +1112,7 @@ unroll_loop_runtime_iterations (struct loop *loop) } /* Recount dominators for outer blocks. */ - iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs); + iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false); /* And unroll loop. */ @@ -1115,7 +1123,7 @@ unroll_loop_runtime_iterations (struct loop *loop) ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop), max_unroll, wont_exit, desc->out_edge, - remove_edges, &n_remove_edges, + &remove_edges, DLTHE_FLAG_UPDATE_FREQ | (opt_info ? DLTHE_RECORD_COPY_NUMBER @@ -1149,9 +1157,9 @@ unroll_loop_runtime_iterations (struct loop *loop) } /* Remove the edges. */ - for (i = 0; i < n_remove_edges; i++) - remove_path (remove_edges[i]); - free (remove_edges); + for (i = 0; VEC_iterate (edge, remove_edges, i, e); i++) + remove_path (e); + VEC_free (edge, heap, remove_edges); /* We must be careful when updating the number of iterations due to preconditioning and the fact that the value must be valid at entry @@ -1176,8 +1184,7 @@ unroll_loop_runtime_iterations (struct loop *loop) "in runtime, %i insns\n", max_unroll, num_loop_insns (loop)); - if (dom_bbs) - free (dom_bbs); + VEC_free (basic_block, heap, dom_bbs); } /* Decide whether to simply peel LOOP and how much. */ @@ -1297,8 +1304,7 @@ peel_loop_simple (struct loop *loop) opt_info_start_duplication (opt_info); ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), - npeel, wont_exit, - NULL, NULL, + npeel, wont_exit, NULL, NULL, DLTHE_FLAG_UPDATE_FREQ | (opt_info ? DLTHE_RECORD_COPY_NUMBER @@ -1449,7 +1455,7 @@ unroll_loop_stupid (struct loop *loop) ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop), nunroll, wont_exit, - NULL, NULL, NULL, + NULL, NULL, DLTHE_FLAG_UPDATE_FREQ | (opt_info ? DLTHE_RECORD_COPY_NUMBER @@ -1485,7 +1491,7 @@ unroll_loop_stupid (struct loop *loop) static hashval_t si_info_hash (const void *ivts) { - return (hashval_t) INSN_UID (((struct iv_to_split *) ivts)->insn); + return (hashval_t) INSN_UID (((const struct iv_to_split *) ivts)->insn); } /* An equality functions for information about insns to split. */ @@ -1493,8 +1499,8 @@ si_info_hash (const void *ivts) static int si_info_eq (const void *ivts1, const void *ivts2) { - const struct iv_to_split *i1 = ivts1; - const struct iv_to_split *i2 = ivts2; + const struct iv_to_split *const i1 = (const struct iv_to_split *) ivts1; + const struct iv_to_split *const i2 = (const struct iv_to_split *) ivts2; return i1->insn == i2->insn; } @@ -1504,7 +1510,7 @@ si_info_eq (const void *ivts1, const void *ivts2) static hashval_t ve_info_hash (const void *ves) { - return (hashval_t) INSN_UID (((struct var_to_expand *) ves)->insn); + return (hashval_t) INSN_UID (((const struct var_to_expand *) ves)->insn); } /* Return true if IVTS1 and IVTS2 (which are really both of type @@ -1513,8 +1519,8 @@ ve_info_hash (const void *ves) static int ve_info_eq (const void *ivts1, const void *ivts2) { - const struct var_to_expand *i1 = ivts1; - const struct var_to_expand *i2 = ivts2; + const struct var_to_expand *const i1 = (const struct var_to_expand *) ivts1; + const struct var_to_expand *const i2 = (const struct var_to_expand *) ivts2; return i1->insn == i2->insn; } @@ -1569,10 +1575,11 @@ referenced_in_one_insn_in_loop_p (struct loop *loop, rtx reg) static struct var_to_expand * analyze_insn_to_expand_var (struct loop *loop, rtx insn) { - rtx set, dest, src, op1; + rtx set, dest, src, op1, op2, something; struct var_to_expand *ves; enum machine_mode mode1, mode2; - + unsigned accum_pos; + set = single_set (insn); if (!set) return NULL; @@ -1597,40 +1604,62 @@ analyze_insn_to_expand_var (struct loop *loop, rtx insn) if (!have_insn_for (GET_CODE (src), GET_MODE (src))) return NULL; - if (!XEXP (src, 0)) - return NULL; - op1 = XEXP (src, 0); + op2 = XEXP (src, 1); if (!REG_P (dest) && !(GET_CODE (dest) == SUBREG && REG_P (SUBREG_REG (dest)))) return NULL; - if (!rtx_equal_p (dest, op1)) - return NULL; - + if (rtx_equal_p (dest, op1)) + accum_pos = 0; + else if (rtx_equal_p (dest, op2)) + accum_pos = 1; + else + return NULL; + + /* The method of expansion that we are using; which includes + the initialization of the expansions with zero and the summation of + the expansions at the end of the computation will yield wrong results + for (x = something - x) thus avoid using it in that case. */ + if (accum_pos == 1 + && GET_CODE (src) == MINUS) + return NULL; + + something = (accum_pos == 0)? op2 : op1; + if (!referenced_in_one_insn_in_loop_p (loop, dest)) return NULL; - if (rtx_referenced_p (dest, XEXP (src, 1))) + if (rtx_referenced_p (dest, something)) return NULL; mode1 = GET_MODE (dest); - mode2 = GET_MODE (XEXP (src, 1)); + mode2 = GET_MODE (something); if ((FLOAT_MODE_P (mode1) || FLOAT_MODE_P (mode2)) - && !flag_unsafe_math_optimizations) + && !flag_associative_math) return NULL; - + + if (dump_file) + { + fprintf (dump_file, + "\n;; Expanding Accumulator "); + print_rtl (dump_file, dest); + fprintf (dump_file, "\n"); + } + /* Record the accumulator to expand. */ ves = XNEW (struct var_to_expand); ves->insn = insn; - ves->var_expansions = VEC_alloc (rtx, heap, 1); ves->reg = copy_rtx (dest); + ves->var_expansions = VEC_alloc (rtx, heap, 1); + ves->next = NULL; ves->op = GET_CODE (src); ves->expansion_count = 0; ves->reuse_expansion = 0; + ves->accum_pos = accum_pos; return ves; } @@ -1702,6 +1731,7 @@ analyze_iv_to_split_insn (rtx insn) ivts->insn = insn; ivts->base_var = NULL_RTX; ivts->step = iv.step; + ivts->next = NULL; ivts->n_loc = 1; ivts->loc[0] = 1; @@ -1733,8 +1763,12 @@ analyze_insns_in_loop (struct loop *loop) body = get_loop_body (loop); if (flag_split_ivs_in_unroller) - opt_info->insns_to_split = htab_create (5 * loop->num_nodes, - si_info_hash, si_info_eq, free); + { + opt_info->insns_to_split = htab_create (5 * loop->num_nodes, + si_info_hash, si_info_eq, free); + opt_info->iv_to_split_head = NULL; + opt_info->iv_to_split_tail = &opt_info->iv_to_split_head; + } /* Record the loop exit bb and loop preheader before the unrolling. */ opt_info->loop_preheader = loop_preheader_edge (loop)->src; @@ -1751,8 +1785,13 @@ analyze_insns_in_loop (struct loop *loop) if (flag_variable_expansion_in_unroller && can_apply) - opt_info->insns_with_var_to_expand = htab_create (5 * loop->num_nodes, - ve_info_hash, ve_info_eq, free); + { + opt_info->insns_with_var_to_expand = htab_create (5 * loop->num_nodes, + ve_info_hash, + ve_info_eq, free); + opt_info->var_to_expand_head = NULL; + opt_info->var_to_expand_tail = &opt_info->var_to_expand_head; + } for (i = 0; i < loop->num_nodes; i++) { @@ -1771,7 +1810,10 @@ analyze_insns_in_loop (struct loop *loop) if (ivts) { slot1 = htab_find_slot (opt_info->insns_to_split, ivts, INSERT); + gcc_assert (*slot1 == NULL); *slot1 = ivts; + *opt_info->iv_to_split_tail = ivts; + opt_info->iv_to_split_tail = &ivts->next; continue; } @@ -1781,7 +1823,10 @@ analyze_insns_in_loop (struct loop *loop) if (ves) { slot2 = htab_find_slot (opt_info->insns_with_var_to_expand, ves, INSERT); + gcc_assert (*slot2 == NULL); *slot2 = ves; + *opt_info->var_to_expand_tail = ves; + opt_info->var_to_expand_tail = &ves->next; } } } @@ -1841,18 +1886,14 @@ get_ivts_expr (rtx expr, struct iv_to_split *ivts) return ret; } -/* Allocate basic variable for the induction variable chain. Callback for - htab_traverse. */ +/* Allocate basic variable for the induction variable chain. */ -static int -allocate_basic_variable (void **slot, void *data ATTRIBUTE_UNUSED) +static void +allocate_basic_variable (struct iv_to_split *ivts) { - struct iv_to_split *ivts = *slot; rtx expr = *get_ivts_expr (single_set (ivts->insn), ivts); ivts->base_var = gen_reg_rtx (GET_MODE (expr)); - - return 1; } /* Insert initialization of basic variable of IVTS before INSN, taking @@ -1979,7 +2020,7 @@ expand_var_during_unrolling (struct var_to_expand *ve, rtx insn) new_reg = get_expansion (ve); validate_change (insn, &SET_DEST (set), new_reg, 1); - validate_change (insn, &XEXP (SET_SRC (set), 0), new_reg, 1); + validate_change (insn, &XEXP (SET_SRC (set), ve->accum_pos), new_reg, 1); if (apply_change_group ()) if (really_new_expansion) @@ -1989,27 +2030,54 @@ expand_var_during_unrolling (struct var_to_expand *ve, rtx insn) } } -/* Initialize the variable expansions in loop preheader. - Callbacks for htab_traverse. PLACE_P is the loop-preheader - basic block where the initialization of the expansions - should take place. */ +/* Initialize the variable expansions in loop preheader. PLACE is the + loop-preheader basic block where the initialization of the + expansions should take place. The expansions are initialized with + (-0) when the operation is plus or minus to honor sign zero. This + way we can prevent cases where the sign of the final result is + effected by the sign of the expansion. Here is an example to + demonstrate this: + + for (i = 0 ; i < n; i++) + sum += something; -static int -insert_var_expansion_initialization (void **slot, void *place_p) + ==> + + sum += something + .... + i = i+1; + sum1 += something + .... + i = i+1 + sum2 += something; + .... + + When SUM is initialized with -zero and SOMETHING is also -zero; the + final result of sum should be -zero thus the expansions sum1 and sum2 + should be initialized with -zero as well (otherwise we will get +zero + as the final result). */ + +static void +insert_var_expansion_initialization (struct var_to_expand *ve, + basic_block place) { - struct var_to_expand *ve = *slot; - basic_block place = (basic_block)place_p; rtx seq, var, zero_init, insn; unsigned i; - + enum machine_mode mode = GET_MODE (ve->reg); + bool honor_signed_zero_p = HONOR_SIGNED_ZEROS (mode); + if (VEC_length (rtx, ve->var_expansions) == 0) - return 1; + return; start_sequence (); if (ve->op == PLUS || ve->op == MINUS) for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); i++) { - zero_init = CONST0_RTX (GET_MODE (var)); + if (honor_signed_zero_p) + zero_init = simplify_gen_unary (NEG, mode, CONST0_RTX (mode), mode); + else + zero_init = CONST0_RTX (mode); + emit_move_insn (var, zero_init); } else if (ve->op == MULT) @@ -2027,26 +2095,21 @@ insert_var_expansion_initialization (void **slot, void *place_p) insn = NEXT_INSN (insn); emit_insn_after (seq, insn); - /* Continue traversing the hash table. */ - return 1; } -/* Combine the variable expansions at the loop exit. - Callbacks for htab_traverse. PLACE_P is the loop exit - basic block where the summation of the expansions should - take place. */ +/* Combine the variable expansions at the loop exit. PLACE is the + loop exit basic block where the summation of the expansions should + take place. */ -static int -combine_var_copies_in_loop_exit (void **slot, void *place_p) +static void +combine_var_copies_in_loop_exit (struct var_to_expand *ve, basic_block place) { - struct var_to_expand *ve = *slot; - basic_block place = (basic_block)place_p; rtx sum = ve->reg; rtx expr, seq, var, insn; unsigned i; if (VEC_length (rtx, ve->var_expansions) == 0) - return 1; + return; start_sequence (); if (ve->op == PLUS || ve->op == MINUS) @@ -2073,9 +2136,6 @@ combine_var_copies_in_loop_exit (void **slot, void *place_p) insn = NEXT_INSN (insn); emit_insn_after (seq, insn); - - /* Continue traversing the hash table. */ - return 1; } /* Apply loop optimizations in loop copies using the @@ -2104,7 +2164,8 @@ apply_opt_in_copies (struct opt_info *opt_info, /* Allocate the basic variables (i0). */ if (opt_info->insns_to_split) - htab_traverse (opt_info->insns_to_split, allocate_basic_variable, NULL); + for (ivts = opt_info->iv_to_split_head; ivts; ivts = ivts->next) + allocate_basic_variable (ivts); for (i = opt_info->first_new_block; i < (unsigned) last_basic_block; i++) { @@ -2132,7 +2193,8 @@ apply_opt_in_copies (struct opt_info *opt_info, /* Apply splitting iv optimization. */ if (opt_info->insns_to_split) { - ivts = htab_find (opt_info->insns_to_split, &ivts_templ); + ivts = (struct iv_to_split *) + htab_find (opt_info->insns_to_split, &ivts_templ); if (ivts) { @@ -2147,7 +2209,8 @@ apply_opt_in_copies (struct opt_info *opt_info, /* Apply variable expansion optimization. */ if (unrolling && opt_info->insns_with_var_to_expand) { - ves = htab_find (opt_info->insns_with_var_to_expand, &ve_templ); + ves = (struct var_to_expand *) + htab_find (opt_info->insns_with_var_to_expand, &ve_templ); if (ves) { gcc_assert (GET_CODE (PATTERN (insn)) @@ -2166,12 +2229,10 @@ apply_opt_in_copies (struct opt_info *opt_info, and take care of combining them at the loop exit. */ if (opt_info->insns_with_var_to_expand) { - htab_traverse (opt_info->insns_with_var_to_expand, - insert_var_expansion_initialization, - opt_info->loop_preheader); - htab_traverse (opt_info->insns_with_var_to_expand, - combine_var_copies_in_loop_exit, - opt_info->loop_exit); + for (ves = opt_info->var_to_expand_head; ves; ves = ves->next) + insert_var_expansion_initialization (ves, opt_info->loop_preheader); + for (ves = opt_info->var_to_expand_head; ves; ves = ves->next) + combine_var_copies_in_loop_exit (ves, opt_info->loop_exit); } /* Rewrite also the original loop body. Find them as originals of the blocks @@ -2197,7 +2258,8 @@ apply_opt_in_copies (struct opt_info *opt_info, ivts_templ.insn = orig_insn; if (opt_info->insns_to_split) { - ivts = htab_find (opt_info->insns_to_split, &ivts_templ); + ivts = (struct iv_to_split *) + htab_find (opt_info->insns_to_split, &ivts_templ); if (ivts) { if (!delta) @@ -2211,20 +2273,6 @@ apply_opt_in_copies (struct opt_info *opt_info, } } -/* Release the data structures used for the variable expansion - optimization. Callbacks for htab_traverse. */ - -static int -release_var_copies (void **slot, void *data ATTRIBUTE_UNUSED) -{ - struct var_to_expand *ve = *slot; - - VEC_free (rtx, heap, ve->var_expansions); - - /* Continue traversing the hash table. */ - return 1; -} - /* Release OPT_INFO. */ static void @@ -2234,8 +2282,10 @@ free_opt_info (struct opt_info *opt_info) htab_delete (opt_info->insns_to_split); if (opt_info->insns_with_var_to_expand) { - htab_traverse (opt_info->insns_with_var_to_expand, - release_var_copies, NULL); + struct var_to_expand *ves; + + for (ves = opt_info->var_to_expand_head; ves; ves = ves->next) + VEC_free (rtx, heap, ves->var_expansions); htab_delete (opt_info->insns_with_var_to_expand); } free (opt_info);