/* RTL-level loop invariant motion.
- Copyright (C) 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
This file is part of GCC.
#include "flags.h"
#include "df.h"
#include "hashtab.h"
+#include "except.h"
/* The data stored for the loop. */
/* The dataflow object. */
-static struct df *df;
+static struct df *df = NULL;
/* Test for possibility of invariantness of 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;
+ struct df_ref *def;
basic_block bb = BLOCK_FOR_INSN (use->insn), def_bb;
+ if (use->flags & DF_REF_READ_WRITE)
+ return NULL;
+
defs = DF_REF_CHAIN (use);
if (!defs || defs->next)
return NULL;
const char *fmt;
hashval_t val = code;
int do_not_record_p;
- struct ref *use;
+ struct df_ref *use;
struct invariant *inv;
switch (code)
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;
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;
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;
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;
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);
}
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));
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_set_blocks (df, blocks);
+ df_analyze (df);
BITMAP_FREE (blocks);
}
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;
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);
}
/* Finds the invariants INSN depends on and store them to the DEPENDS_ON
- bitmap. */
+ bitmap. Returns true if all dependencies of INSN are known to be
+ loop invariants, false otherwise. */
static bool
check_dependencies (rtx insn, bitmap depends_on)
{
- struct df_link *uses, *defs;
- struct ref *use, *def;
+ 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;
- for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
+ for (use = DF_INSN_GET (df, insn)->uses; use; use = use->next_ref)
{
- use = uses->ref;
+ if (use->flags & DF_REF_READ_WRITE)
+ return false;
defs = DF_REF_CHAIN (use);
if (!defs)
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;
|| 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;
+#endif
+
set = single_set (insn);
if (!set)
return;
|| !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))
}
if (simple)
- def = xcalloc (1, sizeof (struct def));
+ def = XCNEW (struct def);
else
def = NULL;
static void
record_uses (rtx insn)
{
- struct df_link *uses;
- struct ref *use;
+ struct df_ref *use;
struct invariant *inv;
- for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
+ for (use = DF_INSN_GET (df, insn)->uses; use; use = use->next_ref)
{
- use = uses->ref;
inv = invariant_for_use (use);
if (inv)
record_use (inv->def, DF_REF_LOC (use), DF_REF_INSN (use));
(*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);
{
unsigned i, regs_used, n_inv_uses, regs_needed = 0, new_regs;
struct invariant *inv = NULL;
+ unsigned int n_regs = DF_REG_SIZE (df);
if (!VEC_length (invariant_p, invariants))
return;
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))
{
}
}
-/* Move invariant INVNO out of the LOOP. */
+/* Returns true if all insns in SEQ are valid. */
-static void
+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. */
+
+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, seq, op;
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
{
EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
{
- move_invariant_reg (loop, i);
+ if (!move_invariant_reg (loop, i))
+ goto fail;
}
}
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);
+ dest = SET_DEST (set);
+ reg = gen_reg_rtx (GET_MODE (dest));
- /* If the SET_DEST of the invariant insn is a reg, we can just move
+ /* 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 (SET_DEST (set)))
+ 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));
- 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);
+ 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);
}
}
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;
if (inv->def)
{
for (use = inv->def->uses; use; use = use->next)
- {
- *use->pos = reg;
- df_insn_modify (df, BLOCK_FOR_INSN (use->insn), use->insn);
- }
+ *use->pos = reg;
}
+
+ 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
struct def *def;
struct invariant *inv;
- for (i = 0; i < df->n_defs; i++)
+ for (i = 0; i < DF_DEFS_SIZE (df); i++)
{
- if (!df->defs[i])
+ struct df_ref * ref = DF_DEFS_GET (df, i);
+ if (!ref)
continue;
- inv = DF_REF_DATA (df->defs[i]);
+ 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 (df->defs[i]) = NULL;
+ DF_REF_DATA (ref) = NULL;
}
for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
struct loop *loop;
unsigned i;
- df = df_init ();
-
+ df = df_init (DF_HARD_REGS | DF_EQUIV_NOTES);
+ df_chain_add_problem (df, DF_UD_CHAIN);
+
/* Process the loops, innermost first. */
loop = loops->tree_root;
while (loop->inner)
OSDN Git Service
