X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Floop-invariant.c;h=40e70ba18c04bec9ed7e51ef186f50728f74edc3;hp=8c3f2d23512d90bb2d04eb0f58f7bbacc3472c59;hb=94c13a9e836cf6486786673c9ba448fdeb815cd8;hpb=3d6b8be710445a7a01af0b657ea2e47c6a3c6670 diff --git a/gcc/loop-invariant.c b/gcc/loop-invariant.c index 8c3f2d23512..40e70ba18c0 100644 --- a/gcc/loop-invariant.c +++ b/gcc/loop-invariant.c @@ -1,11 +1,11 @@ /* RTL-level loop invariant motion. - Copyright (C) 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 2004, 2005, 2006, 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 +Free 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 @@ -14,14 +14,13 @@ 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 +. */ /* This implements the loop invariant motion pass. It is very simple - (no calls, libcalls, etc.). This should be sufficient to cleanup things - like address arithmetics -- other more complicated invariants should be - eliminated on tree level either in tree-ssa-loop-im.c or in tree-ssa-pre.c. + (no calls, no loads/stores, etc.). This should be sufficient to cleanup + things like address arithmetics -- other more complicated invariants should + be eliminated on GIMPLE either in tree-ssa-loop-im.c or in tree-ssa-pre.c. We proceed loop by loop -- it is simpler than trying to handle things globally and should not lose much. First we inspect all sets inside loop @@ -52,6 +51,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "flags.h" #include "df.h" #include "hashtab.h" +#include "except.h" /* The data stored for the loop. */ @@ -120,6 +120,11 @@ struct invariant unsigned stamp; }; +/* Table of invariants indexed by the df_ref uid field. */ + +static unsigned int invariant_table_size = 0; +static struct invariant ** invariant_table; + /* Entry for hash table of invariant expressions. */ struct invariant_expr_entry @@ -151,9 +156,20 @@ DEF_VEC_ALLOC_P(invariant_p, heap); static VEC(invariant_p,heap) *invariants; -/* The dataflow object. */ +/* Check the size of the invariant table and realloc if necessary. */ -static struct df *df; +static void +check_invariant_table_size (void) +{ + if (invariant_table_size < DF_DEFS_TABLE_SIZE()) + { + unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4); + invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size); + memset (&invariant_table[invariant_table_size], 0, + (new_size - invariant_table_size) * sizeof (struct rtx_iv *)); + invariant_table_size = new_size; + } +} /* Test for possibility of invariantness of X. */ @@ -168,6 +184,7 @@ check_maybe_invariant (rtx x) { case CONST_INT: case CONST_DOUBLE: + case CONST_FIXED: case SYMBOL_REF: case CONST: case LABEL_REF: @@ -188,7 +205,7 @@ check_maybe_invariant (rtx x) /* Just handle the most trivial case where we load from an unchanging location (most importantly, pic tables). */ - if (MEM_READONLY_P (x)) + if (MEM_READONLY_P (x) && !MEM_VOLATILE_P (x)) break; return false; @@ -226,23 +243,27 @@ check_maybe_invariant (rtx x) invariant. */ static struct invariant * -invariant_for_use (struct ref *use) +invariant_for_use (struct df_ref *use) { struct df_link *defs; - struct ref *def; - basic_block bb = BLOCK_FOR_INSN (use->insn), def_bb; + struct df_ref *def; + basic_block bb = DF_REF_BB (use), def_bb; + + if (use->flags & DF_REF_READ_WRITE) + return NULL; defs = DF_REF_CHAIN (use); if (!defs || defs->next) return NULL; def = defs->ref; - if (!DF_REF_DATA (def)) + check_invariant_table_size (); + if (!invariant_table[DF_REF_ID(def)]) return NULL; def_bb = DF_REF_BB (def); if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb)) return NULL; - return DF_REF_DATA (def); + return invariant_table[DF_REF_ID(def)]; } /* Computes hash value for invariant expression X in INSN. */ @@ -255,20 +276,21 @@ hash_invariant_expr_1 (rtx insn, rtx x) const char *fmt; hashval_t val = code; int do_not_record_p; - struct ref *use; + struct df_ref *use; struct invariant *inv; switch (code) { case CONST_INT: case CONST_DOUBLE: + case CONST_FIXED: case SYMBOL_REF: case CONST: case LABEL_REF: return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false); case REG: - use = df_find_use (df, insn, x); + use = df_find_use (insn, x); if (!use) return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false); inv = invariant_for_use (use); @@ -292,6 +314,8 @@ hash_invariant_expr_1 (rtx insn, rtx x) for (j = 0; j < XVECLEN (x, i); j++) val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j)); } + else if (fmt[i] == 'i' || fmt[i] == 'n') + val ^= XINT (x, i); } return val; @@ -306,7 +330,7 @@ invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2) enum rtx_code code = GET_CODE (e1); int i, j; const char *fmt; - struct ref *use1, *use2; + struct df_ref *use1, *use2; struct invariant *inv1 = NULL, *inv2 = NULL; rtx sub1, sub2; @@ -320,14 +344,15 @@ invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2) { case CONST_INT: case CONST_DOUBLE: + case CONST_FIXED: case SYMBOL_REF: case CONST: case LABEL_REF: return rtx_equal_p (e1, e2); case REG: - use1 = df_find_use (df, insn1, e1); - use2 = df_find_use (df, insn2, e2); + use1 = df_find_use (insn1, e1); + use2 = df_find_use (insn2, e2); if (use1) inv1 = invariant_for_use (use1); if (use2) @@ -373,6 +398,14 @@ invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2) return false; } } + else if (fmt[i] == 'i' || fmt[i] == 'n') + { + if (XINT (e1, i) != XINT (e2, i)) + return false; + } + /* Unhandled type of subexpression, we fail conservatively. */ + else + return false; } return true; @@ -383,7 +416,8 @@ invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2) static hashval_t hash_invariant_expr (const void *e) { - const struct invariant_expr_entry *entry = e; + const struct invariant_expr_entry *const entry = + (const struct invariant_expr_entry *) e; return entry->hash; } @@ -393,8 +427,10 @@ hash_invariant_expr (const void *e) static int eq_invariant_expr (const void *e1, const void *e2) { - const struct invariant_expr_entry *entry1 = e1; - const struct invariant_expr_entry *entry2 = e2; + const struct invariant_expr_entry *const entry1 = + (const struct invariant_expr_entry *) e1; + const struct invariant_expr_entry *const entry2 = + (const struct invariant_expr_entry *) e2; if (entry1->mode != entry2->mode) return 0; @@ -420,12 +456,12 @@ find_or_insert_inv (htab_t eq, rtx expr, enum machine_mode mode, pentry.inv = inv; pentry.mode = mode; slot = htab_find_slot_with_hash (eq, &pentry, hash, INSERT); - entry = *slot; + entry = (struct invariant_expr_entry *) *slot; if (entry) return entry->inv; - entry = xmalloc (sizeof (struct invariant_expr_entry)); + entry = XNEW (struct invariant_expr_entry); entry->inv = inv; entry->expr = expr; entry->mode = mode; @@ -465,7 +501,7 @@ find_identical_invariants (htab_t eq, struct invariant *inv) if (dump_file && inv->eqto != inv->invno) fprintf (dump_file, - "Invariant %d is equivalent to invariant %d.\n ", + "Invariant %d is equivalent to invariant %d.\n", inv->invno, inv->eqto); } @@ -529,7 +565,8 @@ find_exits (struct loop *loop, basic_block *body, FOR_BB_INSNS (body[i], insn) { if (CALL_P (insn) - && !CONST_OR_PURE_CALL_P (insn)) + && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn) + || !RTL_CONST_OR_PURE_CALL_P (insn))) { has_call = true; bitmap_set_bit (may_exit, i); @@ -582,7 +619,9 @@ find_exits (struct loop *loop, basic_block *body, static bool may_assign_reg_p (rtx x) { - return (can_copy_p (GET_MODE (x)) + return (GET_MODE (x) != VOIDmode + && GET_MODE (x) != BLKmode + && can_copy_p (GET_MODE (x)) && (!REG_P (x) || !HARD_REGISTER_P (x) || REGNO_REG_CLASS (REGNO (x)) != NO_REGS)); @@ -600,7 +639,21 @@ find_defs (struct loop *loop, basic_block *body) for (i = 0; i < loop->num_nodes; i++) bitmap_set_bit (blocks, body[i]->index); - df_analyze_subcfg (df, blocks, DF_UD_CHAIN | DF_HARD_REGS | DF_EQUIV_NOTES); + df_remove_problem (df_chain); + df_process_deferred_rescans (); + df_chain_add_problem (DF_UD_CHAIN); + df_set_blocks (blocks); + df_analyze (); + + if (dump_file) + { + df_dump_region (dump_file); + fprintf (dump_file, "*****starting processing of loop ******\n"); + print_rtl_with_bb (dump_file, get_insns ()); + fprintf (dump_file, "*****ending processing of loop ******\n"); + } + check_invariant_table_size (); + BITMAP_FREE (blocks); } @@ -613,7 +666,7 @@ static struct invariant * create_new_invariant (struct def *def, rtx insn, bitmap depends_on, bool always_executed) { - struct invariant *inv = xmalloc (sizeof (struct invariant)); + struct invariant *inv = XNEW (struct invariant); rtx set = single_set (insn); inv->def = def; @@ -654,10 +707,8 @@ create_new_invariant (struct def *def, rtx insn, bitmap depends_on, static void record_use (struct def *def, rtx *use, rtx insn) { - struct use *u = xmalloc (sizeof (struct use)); + struct use *u = XNEW (struct use); - if (GET_CODE (*use) == SUBREG) - use = &SUBREG_REG (*use); gcc_assert (REG_P (*use)); u->pos = use; @@ -667,47 +718,69 @@ record_use (struct def *def, rtx *use, rtx insn) def->n_uses++; } -/* Finds the invariants INSN depends on and store them to the DEPENDS_ON - bitmap. */ +/* Finds the invariants USE depends on and store them to the DEPENDS_ON + bitmap. Returns true if all dependencies of USE are known to be + loop invariants, false otherwise. */ static bool -check_dependencies (rtx insn, bitmap depends_on) +check_dependency (basic_block bb, struct df_ref *use, bitmap depends_on) { - struct df_link *uses, *defs; - struct ref *use, *def; - basic_block bb = BLOCK_FOR_INSN (insn), def_bb; + struct df_ref *def; + basic_block def_bb; + struct df_link *defs; struct def *def_data; struct invariant *inv; + + if (use->flags & DF_REF_READ_WRITE) + return false; + + defs = DF_REF_CHAIN (use); + if (!defs) + return true; + + if (defs->next) + return false; + + def = defs->ref; + check_invariant_table_size (); + inv = invariant_table[DF_REF_ID(def)]; + if (!inv) + return false; + + def_data = inv->def; + gcc_assert (def_data != NULL); + + def_bb = DF_REF_BB (def); + /* Note that in case bb == def_bb, we know that the definition + dominates insn, because def has invariant_table[DF_REF_ID(def)] + defined and we process the insns in the basic block bb + sequentially. */ + if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb)) + return false; + + bitmap_set_bit (depends_on, def_data->invno); + return true; +} - for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next) - { - use = uses->ref; - - defs = DF_REF_CHAIN (use); - if (!defs) - continue; - - if (defs->next) - return false; - - def = defs->ref; - inv = DF_REF_DATA (def); - if (!inv) - return false; - - def_data = inv->def; - gcc_assert (def_data != NULL); - def_bb = DF_REF_BB (def); - /* Note that in case bb == def_bb, we know that the definition dominates - insn, because def has DF_REF_DATA defined and we process the insns - in the basic block bb sequentially. */ - if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb)) - return false; +/* Finds the invariants INSN depends on and store them to the DEPENDS_ON + bitmap. Returns true if all dependencies of INSN are known to be + loop invariants, false otherwise. */ - bitmap_set_bit (depends_on, def_data->invno); - } +static bool +check_dependencies (rtx insn, bitmap depends_on) +{ + struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); + struct df_ref **use_rec; + basic_block bb = BLOCK_FOR_INSN (insn); + for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++) + if (!check_dependency (bb, *use_rec, depends_on)) + return false; + for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++) + if (!check_dependency (bb, *use_rec, depends_on)) + return false; + return true; } @@ -718,18 +791,18 @@ check_dependencies (rtx insn, bitmap depends_on) static void find_invariant_insn (rtx insn, bool always_reached, bool always_executed) { - struct ref *ref; + struct df_ref *ref; struct def *def; bitmap depends_on; rtx set, dest; bool simple = true; struct invariant *inv; - /* Until we get rid of LIBCALLS. */ - if (find_reg_note (insn, REG_RETVAL, NULL_RTX) - || find_reg_note (insn, REG_LIBCALL, NULL_RTX) - || find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX)) +#ifdef HAVE_cc0 + /* We can't move a CC0 setter without the user. */ + if (sets_cc0_p (insn)) return; +#endif set = single_set (insn); if (!set) @@ -744,16 +817,14 @@ find_invariant_insn (rtx insn, bool always_reached, bool always_executed) || !check_maybe_invariant (SET_SRC (set))) return; - if (may_trap_p (PATTERN (insn))) - { - if (!always_reached) - return; + /* If the insn can throw exception, we cannot move it at all without changing + cfg. */ + if (can_throw_internal (insn)) + return; - /* Unless the exceptions are handled, the behavior is undefined - if the trap occurs. */ - if (flag_non_call_exceptions) - return; - } + /* We cannot make trapping insn executed, unless it was executed before. */ + if (may_trap_after_code_motion_p (PATTERN (insn)) && !always_reached) + return; depends_on = BITMAP_ALLOC (NULL); if (!check_dependencies (insn, depends_on)) @@ -763,7 +834,7 @@ find_invariant_insn (rtx insn, bool always_reached, bool always_executed) } if (simple) - def = xcalloc (1, sizeof (struct def)); + def = XCNEW (struct def); else def = NULL; @@ -771,8 +842,9 @@ find_invariant_insn (rtx insn, bool always_reached, bool always_executed) if (simple) { - ref = df_find_def (df, insn, dest); - DF_REF_DATA (ref) = inv; + ref = df_find_def (insn, dest); + check_invariant_table_size (); + invariant_table[DF_REF_ID(ref)] = inv; } } @@ -781,16 +853,23 @@ find_invariant_insn (rtx insn, bool always_reached, bool always_executed) static void record_uses (rtx insn) { - struct df_link *uses; - struct ref *use; + struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); + struct df_ref **use_rec; struct invariant *inv; - for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next) + for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++) { - use = uses->ref; + struct df_ref *use = *use_rec; inv = invariant_for_use (use); if (inv) - record_use (inv->def, DF_REF_LOC (use), DF_REF_INSN (use)); + record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use)); + } + for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++) + { + struct df_ref *use = *use_rec; + inv = invariant_for_use (use); + if (inv) + record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use)); } } @@ -824,7 +903,8 @@ find_invariants_bb (basic_block bb, bool always_reached, bool always_executed) if (always_reached && CALL_P (insn) - && !CONST_OR_PURE_CALL_P (insn)) + && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn) + || ! RTL_CONST_OR_PURE_CALL_P (insn))) always_reached = false; } } @@ -911,6 +991,32 @@ get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed) (*regs_needed)++; (*comp_cost) += inv->cost; +#ifdef STACK_REGS + { + /* Hoisting constant pool constants into stack regs may cost more than + just single register. On x87, the balance is affected both by the + small number of FP registers, and by its register stack organization, + that forces us to add compensation code in and around the loop to + shuffle the operands to the top of stack before use, and pop them + from the stack after the loop finishes. + + To model this effect, we increase the number of registers needed for + stack registers by two: one register push, and one register pop. + This usually has the effect that FP constant loads from the constant + pool are not moved out of the loop. + + Note that this also means that dependent invariants can not be moved. + However, the primary purpose of this pass is to move loop invariant + address arithmetic out of loops, and address arithmetic that depends + on floating point constants is unlikely to ever occur. */ + rtx set = single_set (inv->insn); + if (set + && IS_STACK_MODE (GET_MODE (SET_SRC (set))) + && constant_pool_constant_p (SET_SRC (set))) + (*regs_needed) += 2; + } +#endif + EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi) { dep = VEC_index (invariant_p, invariants, depno); @@ -936,37 +1042,34 @@ get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed) } /* Calculates gain for eliminating invariant INV. REGS_USED is the number - of registers used in the loop, N_INV_USES is the number of uses of - invariants, NEW_REGS is the number of new variables already added due to - the invariant motion. The number of registers needed for it is stored in - *REGS_NEEDED. */ + of registers used in the loop, NEW_REGS is the number of new variables + already added due to the invariant motion. The number of registers needed + for it is stored in *REGS_NEEDED. */ static int gain_for_invariant (struct invariant *inv, unsigned *regs_needed, - unsigned new_regs, unsigned regs_used, unsigned n_inv_uses) + unsigned new_regs, unsigned regs_used) { int comp_cost, size_cost; get_inv_cost (inv, &comp_cost, regs_needed); actual_stamp++; - size_cost = (global_cost_for_size (new_regs + *regs_needed, - regs_used, n_inv_uses) - - global_cost_for_size (new_regs, regs_used, n_inv_uses)); + size_cost = (estimate_reg_pressure_cost (new_regs + *regs_needed, regs_used) + - estimate_reg_pressure_cost (new_regs, regs_used)); return comp_cost - size_cost; } /* Finds invariant with best gain for moving. Returns the gain, stores the invariant in *BEST and number of registers needed for it to - *REGS_NEEDED. REGS_USED is the number of registers used in - the loop, N_INV_USES is the number of uses of invariants. NEW_REGS - is the number of new variables already added due to invariant motion. */ + *REGS_NEEDED. REGS_USED is the number of registers used in the loop. + NEW_REGS is the number of new variables already added due to invariant + motion. */ static int best_gain_for_invariant (struct invariant **best, unsigned *regs_needed, - unsigned new_regs, unsigned regs_used, - unsigned n_inv_uses) + unsigned new_regs, unsigned regs_used) { struct invariant *inv; int gain = 0, again; @@ -981,8 +1084,7 @@ best_gain_for_invariant (struct invariant **best, unsigned *regs_needed, if (inv->eqto != inv->invno) continue; - again = gain_for_invariant (inv, &aregs_needed, - new_regs, regs_used, n_inv_uses); + again = gain_for_invariant (inv, &aregs_needed, new_regs, regs_used); if (again > gain) { gain = again; @@ -1023,61 +1125,53 @@ set_move_mark (unsigned invno) static void find_invariants_to_move (void) { - unsigned i, regs_used, n_inv_uses, regs_needed = 0, new_regs; + unsigned i, regs_used, regs_needed = 0, new_regs; struct invariant *inv = NULL; + unsigned int n_regs = DF_REG_SIZE (df); if (!VEC_length (invariant_p, invariants)) return; - /* Now something slightly more involved. First estimate the number of used - registers. */ - n_inv_uses = 0; - - /* We do not really do a good job in this estimation; put some initial bound - here to stand for induction variables etc. that we do not detect. */ + /* We do not really do a good job in estimating number of registers used; + we put some initial bound here to stand for induction variables etc. + that we do not detect. */ regs_used = 2; - for (i = 0; i < df->n_regs; i++) + for (i = 0; i < n_regs; i++) { - if (!DF_REGNO_FIRST_DEF (df, i) && DF_REGNO_LAST_USE (df, i)) + if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i)) { /* This is a value that is used but not changed inside loop. */ regs_used++; } } - for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++) - { - if (inv->def) - n_inv_uses += inv->def->n_uses; - } - new_regs = 0; - while (best_gain_for_invariant (&inv, ®s_needed, - new_regs, regs_used, n_inv_uses) > 0) + while (best_gain_for_invariant (&inv, ®s_needed, new_regs, regs_used) > 0) { set_move_mark (inv->invno); new_regs += regs_needed; } } -/* Move invariant INVNO out of the LOOP. */ +/* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false + otherwise. */ -static void +static bool move_invariant_reg (struct loop *loop, unsigned invno) { struct invariant *inv = VEC_index (invariant_p, invariants, invno); struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto); unsigned i; basic_block preheader = loop_preheader_edge (loop)->src; - rtx reg, set; + rtx reg, set, dest, note; struct use *use; bitmap_iterator bi; - if (inv->reg - || !repr->move) - return; - + if (inv->reg) + return true; + if (!repr->move) + return false; /* If this is a representative of the class of equivalent invariants, really move the invariant. Otherwise just replace its use with the register used for the representative. */ @@ -1087,7 +1181,8 @@ move_invariant_reg (struct loop *loop, unsigned invno) { EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi) { - move_invariant_reg (loop, i); + if (!move_invariant_reg (loop, i)) + goto fail; } } @@ -1097,36 +1192,38 @@ move_invariant_reg (struct loop *loop, unsigned invno) would not be dominated by it, we may just move it (TODO). Otherwise we need to create a temporary register. */ set = single_set (inv->insn); - reg = gen_reg_rtx (GET_MODE (SET_DEST (set))); - df_pattern_emit_after (df, gen_move_insn (SET_DEST (set), reg), - BLOCK_FOR_INSN (inv->insn), inv->insn); - - /* If the SET_DEST of the invariant insn is a reg, we can just move - the insn out of the loop. Otherwise, we have to use gen_move_insn - to let emit_move_insn produce a valid instruction stream. */ - if (REG_P (SET_DEST (set))) - { - SET_DEST (set) = reg; - reorder_insns (inv->insn, inv->insn, BB_END (preheader)); - df_insn_modify (df, preheader, inv->insn); - } - else - { - df_pattern_emit_after (df, gen_move_insn (reg, SET_SRC (set)), - preheader, BB_END (preheader)); - df_insn_delete (df, BLOCK_FOR_INSN (inv->insn), inv->insn); - } + dest = SET_DEST (set); + reg = gen_reg_rtx_and_attrs (dest); + + /* Try replacing the destination by a new pseudoregister. */ + if (!validate_change (inv->insn, &SET_DEST (set), reg, false)) + goto fail; + df_insn_rescan (inv->insn); + + emit_insn_after (gen_move_insn (dest, reg), inv->insn); + reorder_insns (inv->insn, inv->insn, BB_END (preheader)); + + /* If there is a REG_EQUAL note on the insn we just moved, and + insn is in a basic block that is not always executed, the note + may no longer be valid after we move the insn. + Note that uses in REG_EQUAL notes are taken into account in + the computation of invariants. Hence it is safe to retain the + note even if the note contains register references. */ + if (! inv->always_executed + && (note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX))) + remove_note (inv->insn, note); } else { - move_invariant_reg (loop, repr->invno); + if (!move_invariant_reg (loop, repr->invno)) + goto fail; reg = repr->reg; set = single_set (inv->insn); - df_pattern_emit_after (df, gen_move_insn (SET_DEST (set), reg), - BLOCK_FOR_INSN (inv->insn), inv->insn); - df_insn_delete (df, BLOCK_FOR_INSN (inv->insn), inv->insn); + emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn); + delete_insn (inv->insn); } + inv->reg = reg; /* Replace the uses we know to be dominated. It saves work for copy @@ -1137,9 +1234,21 @@ move_invariant_reg (struct loop *loop, unsigned invno) for (use = inv->def->uses; use; use = use->next) { *use->pos = reg; - df_insn_modify (df, BLOCK_FOR_INSN (use->insn), use->insn); - } + df_insn_rescan (use->insn); + } } + + return true; + +fail: + /* If we failed, clear move flag, so that we do not try to move inv + again. */ + if (dump_file) + fprintf (dump_file, "Failed to move invariant %d\n", invno); + inv->move = false; + inv->reg = NULL_RTX; + + return false; } /* Move selected invariant out of the LOOP. Newly created regs are marked @@ -1174,20 +1283,19 @@ free_inv_motion_data (void) struct def *def; struct invariant *inv; - for (i = 0; i < df->n_defs; i++) + check_invariant_table_size (); + for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++) { - if (!df->defs[i]) - continue; - - inv = DF_REF_DATA (df->defs[i]); - if (!inv) - continue; - def = inv->def; - gcc_assert (def != NULL); - - free_use_list (def->uses); - free (def); - DF_REF_DATA (df->defs[i]) = NULL; + inv = invariant_table[i]; + if (inv) + { + def = inv->def; + gcc_assert (def != NULL); + + free_use_list (def->uses); + free (def); + invariant_table[i] = NULL; + } } for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++) @@ -1223,41 +1331,29 @@ free_loop_data (struct loop *loop) loop->aux = NULL; } -/* Move the invariants out of the LOOPS. */ +/* Move the invariants out of the loops. */ void -move_loop_invariants (struct loops *loops) +move_loop_invariants (void) { struct loop *loop; - unsigned i; - - df = df_init (); + loop_iterator li; + df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN); /* Process the loops, innermost first. */ - loop = loops->tree_root; - while (loop->inner) - loop = loop->inner; - - while (loop != loops->tree_root) + FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) { move_single_loop_invariants (loop); - - if (loop->next) - { - loop = loop->next; - while (loop->inner) - loop = loop->inner; - } - else - loop = loop->outer; } - for (i = 1; i < loops->num; i++) - if (loops->parray[i]) - free_loop_data (loops->parray[i]); + FOR_EACH_LOOP (li, loop, 0) + { + free_loop_data (loop); + } - df_finish (df); - df = NULL; + free (invariant_table); + invariant_table = NULL; + invariant_table_size = 0; #ifdef ENABLE_CHECKING verify_flow_info ();