/* RTL-level loop invariant motion.
- Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
+ 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
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
+<http://www.gnu.org/licenses/>. */
/* 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
#include "df.h"
#include "hashtab.h"
#include "except.h"
+#include "params.h"
/* The data stored for the loop. */
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
static VEC(invariant_p,heap) *invariants;
-/* The dataflow object. */
+/* Check the size of the invariant table and realloc if necessary. */
-static struct df *df = NULL;
+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. */
{
case CONST_INT:
case CONST_DOUBLE:
+ case CONST_FIXED:
case SYMBOL_REF:
case CONST:
case LABEL_REF:
/* 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;
invariant. */
static struct invariant *
-invariant_for_use (struct df_ref *use)
+invariant_for_use (df_ref use)
{
struct df_link *defs;
- struct df_ref *def;
- basic_block bb = BLOCK_FOR_INSN (use->insn), def_bb;
+ df_ref def;
+ basic_block bb = DF_REF_BB (use), def_bb;
- if (use->flags & DF_REF_READ_WRITE)
+ if (DF_REF_FLAGS (use) & 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. */
const char *fmt;
hashval_t val = code;
int do_not_record_p;
- struct df_ref *use;
+ 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);
enum rtx_code code = GET_CODE (e1);
int i, j;
const char *fmt;
- struct df_ref *use1, *use2;
+ df_ref use1, use2;
struct invariant *inv1 = NULL, *inv2 = NULL;
rtx sub1, sub2;
{
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)
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;
}
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;
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;
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);
for (i = 0; i < loop->num_nodes; i++)
bitmap_set_bit (blocks, body[i]->index);
- df_set_blocks (df, blocks);
- df_analyze (df);
+ 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);
}
{
struct invariant *inv = XNEW (struct invariant);
rtx set = single_set (insn);
+ bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
inv->def = def;
inv->always_executed = always_executed;
/* If the set is simple, usually by moving it we move the whole store out of
the loop. Otherwise we save only cost of the computation. */
if (def)
- inv->cost = rtx_cost (set, SET);
+ inv->cost = rtx_cost (set, SET, speed);
else
- inv->cost = rtx_cost (SET_SRC (set), SET);
+ inv->cost = rtx_cost (SET_SRC (set), SET, speed);
inv->move = false;
inv->reg = NULL_RTX;
{
struct use *u = XNEW (struct use);
- if (GET_CODE (*use) == SUBREG)
- use = &SUBREG_REG (*use);
gcc_assert (REG_P (*use));
u->pos = use;
def->n_uses++;
}
-/* 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
+/* 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, df_ref use, bitmap depends_on)
{
+ df_ref def;
+ basic_block def_bb;
struct df_link *defs;
- struct df_ref *use, *def;
- basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
struct def *def_data;
struct invariant *inv;
+
+ if (DF_REF_FLAGS (use) & 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 (use = DF_INSN_GET (df, insn)->uses; use; use = use->next_ref)
- {
- if (use->flags & DF_REF_READ_WRITE)
- return false;
-
- 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);
+ 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;
}
static void
find_invariant_insn (rtx insn, bool always_reached, bool always_executed)
{
- struct df_ref *ref;
+ 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))
- return;
-
#ifdef HAVE_cc0
/* We can't move a CC0 setter without the user. */
if (sets_cc0_p (insn))
return;
/* We cannot make trapping insn executed, unless it was executed before. */
- if (may_trap_after_code_motion_p (PATTERN (insn)) && !always_reached)
+ if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached)
return;
depends_on = BITMAP_ALLOC (NULL);
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;
}
}
static void
record_uses (rtx insn)
{
- struct df_ref *use;
+ struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
+ df_ref *use_rec;
struct invariant *inv;
- for (use = DF_INSN_GET (df, insn)->uses; use; use = use->next_ref)
+ for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
+ {
+ 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));
+ }
+ for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
{
+ 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));
}
}
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;
}
}
static int
gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
- unsigned new_regs, unsigned regs_used)
+ unsigned new_regs, unsigned regs_used, bool speed)
{
int comp_cost, size_cost;
get_inv_cost (inv, &comp_cost, regs_needed);
actual_stamp++;
- size_cost = (estimate_reg_pressure_cost (new_regs + *regs_needed, regs_used)
- - estimate_reg_pressure_cost (new_regs, regs_used));
+ size_cost = (estimate_reg_pressure_cost (new_regs + *regs_needed, regs_used, speed)
+ - estimate_reg_pressure_cost (new_regs, regs_used, speed));
return comp_cost - size_cost;
}
static int
best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
- unsigned new_regs, unsigned regs_used)
+ unsigned new_regs, unsigned regs_used, bool speed)
{
struct invariant *inv;
int gain = 0, again;
if (inv->eqto != inv->invno)
continue;
- again = gain_for_invariant (inv, &aregs_needed, new_regs, regs_used);
+ again = gain_for_invariant (inv, &aregs_needed, new_regs, regs_used,
+ speed);
if (again > gain)
{
gain = again;
/* Determines which invariants to move. */
static void
-find_invariants_to_move (void)
+find_invariants_to_move (bool speed)
{
unsigned i, regs_used, regs_needed = 0, new_regs;
struct invariant *inv = NULL;
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++;
}
new_regs = 0;
- while (best_gain_for_invariant (&inv, ®s_needed, new_regs, regs_used) > 0)
+ while (best_gain_for_invariant (&inv, ®s_needed, new_regs, regs_used, speed) > 0)
{
set_move_mark (inv->invno);
new_regs += regs_needed;
}
}
-/* Returns true if all insns in SEQ are valid. */
-
-static bool
-seq_insns_valid_p (rtx seq)
-{
- rtx x;
-
- for (x = seq; x; x = NEXT_INSN (x))
- if (insn_invalid_p (x))
- return false;
-
- return true;
-}
-
/* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
otherwise. */
struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto);
unsigned i;
basic_block preheader = loop_preheader_edge (loop)->src;
- rtx reg, set, dest, seq, op;
+ rtx reg, set, dest, note;
struct use *use;
bitmap_iterator bi;
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. */
need to create a temporary register. */
set = single_set (inv->insn);
dest = SET_DEST (set);
- reg = gen_reg_rtx (GET_MODE (dest));
+ reg = gen_reg_rtx_and_attrs (dest);
- /* If the SET_DEST of the invariant insn is a pseudo, 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 (dest) && !HARD_REGISTER_P (dest))
- {
- emit_insn_after (gen_move_insn (dest, reg), inv->insn);
- SET_DEST (set) = reg;
- reorder_insns (inv->insn, inv->insn, BB_END (preheader));
- }
- else
- {
- start_sequence ();
- op = force_operand (SET_SRC (set), reg);
- if (!op)
- {
- end_sequence ();
- goto fail;
- }
- if (op != reg)
- emit_move_insn (reg, op);
- seq = get_insns ();
- end_sequence ();
-
- if (!seq_insns_valid_p (seq))
- goto fail;
- emit_insn_after (seq, BB_END (preheader));
-
- emit_insn_after (gen_move_insn (dest, reg), inv->insn);
- delete_insn (inv->insn);
- }
+ /* 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
{
delete_insn (inv->insn);
}
+
inv->reg = reg;
/* Replace the uses we know to be dominated. It saves work for copy
if (inv->def)
{
for (use = inv->def->uses; use; use = use->next)
- *use->pos = reg;
+ {
+ *use->pos = reg;
+ df_insn_rescan (use->insn);
+ }
}
return true;
fprintf (dump_file, "Failed to move invariant %d\n", invno);
inv->move = false;
inv->reg = NULL_RTX;
+
return false;
}
struct def *def;
struct invariant *inv;
- for (i = 0; i < DF_DEFS_SIZE (df); i++)
+ check_invariant_table_size ();
+ for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
{
- struct df_ref * ref = DF_DEFS_GET (df, i);
- if (!ref)
- continue;
-
- inv = DF_REF_DATA (ref);
- if (!inv)
- continue;
-
- def = inv->def;
- gcc_assert (def != NULL);
-
- free_use_list (def->uses);
- free (def);
- DF_REF_DATA (ref) = 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++)
init_inv_motion_data ();
find_invariants (loop);
- find_invariants_to_move ();
+ find_invariants_to_move (optimize_loop_for_speed_p (loop));
move_invariants (loop);
free_inv_motion_data ();
struct loop *loop;
loop_iterator li;
- df = df_init (DF_HARD_REGS | DF_EQUIV_NOTES);
- df_chain_add_problem (df, DF_UD_CHAIN);
-
+ df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
/* Process the loops, innermost first. */
FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
{
- move_single_loop_invariants (loop);
+ /* move_single_loop_invariants for very large loops
+ is time consuming and might need a lot of memory. */
+ if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP)
+ move_single_loop_invariants (loop);
}
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 ();
OSDN Git Service
