-/* Rtl-level loop invariant motion.
- Copyright (C) 2004 Free Software Foundation, Inc.
-
+/* RTL-level loop invariant motion.
+ Copyright (C) 2004, 2005 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 version.
-
+
GCC is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
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, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
/* 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
+ (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.
-
+
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
and create a dependency graph on insns (saying "to move this insn, you must
We then need to determine what to move. We estimate the number of registers
used and move as many invariants as possible while we still have enough free
registers. We prefer the expensive invariants.
-
+
Then we move the selected invariants out of the loop, creating a new
temporaries for them if necessary. */
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
+#include "tm_p.h"
#include "hard-reg-set.h"
+#include "obstack.h"
#include "basic-block.h"
#include "cfgloop.h"
#include "expr.h"
/* Whether to move the invariant. */
bool move;
- /* Cost if the invariant. */
+ /* Cost of the invariant. */
unsigned cost;
/* The invariants it depends on. */
static unsigned actual_stamp;
+typedef struct invariant *invariant_p;
+
+DEF_VEC_P(invariant_p);
+DEF_VEC_ALLOC_P(invariant_p, heap);
+
/* The invariants. */
-static varray_type invariants;
+static VEC(invariant_p,heap) *invariants;
+
+/* The dataflow object. */
+
+static struct df *df;
/* Test for possibility of invariantness of X. */
/* Just handle the most trivial case where we load from an unchanging
location (most importantly, pic tables). */
- if (RTX_UNCHANGING_P (x))
+ if (MEM_READONLY_P (x))
break;
return false;
bitmap may_exit, bitmap has_exit)
{
unsigned i;
+ edge_iterator ei;
edge e;
struct loop *outermost_exit = loop, *aexit;
bool has_call = false;
}
}
- for (e = body[i]->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, body[i]->succs)
{
if (flow_bb_inside_loop_p (loop, e->dest))
continue;
}
continue;
}
-
+
/* Use the data stored for the subloop to decide whether we may exit
through it. It is sufficient to do this for header of the loop,
as other basic blocks inside it must be dominated by it. */
static bool
may_assign_reg_p (rtx x)
{
- return can_copy_p (GET_MODE (x));
+ return (can_copy_p (GET_MODE (x))
+ && (!REG_P (x)
+ || !HARD_REGISTER_P (x)
+ || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
}
-/* Finds definitions that may correspond to invariants in LOOP with body BODY.
- DF is the dataflow object. */
+/* Finds definitions that may correspond to invariants in LOOP with body
+ BODY. */
static void
-find_defs (struct loop *loop, basic_block *body, struct df *df)
+find_defs (struct loop *loop, basic_block *body)
{
unsigned i;
- bitmap blocks = BITMAP_XMALLOC ();
+ bitmap blocks = BITMAP_ALLOC (NULL);
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);
- BITMAP_XFREE (blocks);
+ BITMAP_FREE (blocks);
}
/* Creates a new invariant for definition DEF in INSN, depending on invariants
inv->stamp = 0;
inv->insn = insn;
- inv->invno = VARRAY_ACTIVE_SIZE (invariants);
+ inv->invno = VEC_length (invariant_p, invariants);
if (def)
def->invno = inv->invno;
- VARRAY_PUSH_GENERIC_PTR_NOGC (invariants, inv);
+ VEC_safe_push (invariant_p, heap, invariants, inv);
if (dump_file)
{
if (GET_CODE (*use) == SUBREG)
use = &SUBREG_REG (*use);
- if (!REG_P (*use))
- abort ();
+ gcc_assert (REG_P (*use));
u->pos = use;
u->insn = insn;
}
/* Finds the invariants INSN depends on and store them to the DEPENDS_ON
- bitmap. DF is the dataflow object. */
+ bitmap. */
static bool
-check_dependencies (rtx insn, struct df *df, bitmap depends_on)
+check_dependencies (rtx insn, bitmap depends_on)
{
struct df_link *uses, *defs;
struct ref *use, *def;
/* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
executed. ALWAYS_EXECUTED is true if the insn is always executed,
- unless the program ends due to a function call. DF is the dataflow
- object. */
+ unless the program ends due to a function call. */
static void
-find_invariant_insn (rtx insn, bool always_reached, bool always_executed,
- struct df *df)
+find_invariant_insn (rtx insn, bool always_reached, bool always_executed)
{
struct ref *ref;
struct def *def;
|| find_reg_note (insn, REG_LIBCALL, NULL_RTX)
|| find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX))
return;
-
+
set = single_set (insn);
if (!set)
return;
dest = SET_DEST (set);
- if (GET_CODE (dest) != REG
+ if (!REG_P (dest)
|| HARD_REGISTER_P (dest))
simple = false;
- if (!check_maybe_invariant (SET_SRC (set))
- || !may_assign_reg_p (SET_DEST (set)))
+ if (!may_assign_reg_p (SET_DEST (set))
+ || !check_maybe_invariant (SET_SRC (set)))
return;
if (may_trap_p (PATTERN (insn)))
return;
}
- depends_on = BITMAP_XMALLOC ();
- if (!check_dependencies (insn, df, depends_on))
+ depends_on = BITMAP_ALLOC (NULL);
+ if (!check_dependencies (insn, depends_on))
{
- BITMAP_XFREE (depends_on);
+ BITMAP_FREE (depends_on);
return;
}
create_new_invariant (def, insn, depends_on, always_executed);
}
-/* Record registers used in INSN that have an unique invariant definition.
- DF is the dataflow object. */
+/* Record registers used in INSN that have a unique invariant definition. */
static void
-record_uses (rtx insn, struct df *df)
+record_uses (rtx insn)
{
struct df_link *uses, *defs;
struct ref *use, *def;
/* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
executed. ALWAYS_EXECUTED is true if the insn is always executed,
- unless the program ends due to a function call. DF is the dataflow
- object. */
+ unless the program ends due to a function call. */
static void
-find_invariants_insn (rtx insn, bool always_reached, bool always_executed,
- struct df *df)
+find_invariants_insn (rtx insn, bool always_reached, bool always_executed)
{
- find_invariant_insn (insn, always_reached, always_executed, df);
- record_uses (insn, df);
+ find_invariant_insn (insn, always_reached, always_executed);
+ record_uses (insn);
}
/* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
basic block is always executed. ALWAYS_EXECUTED is true if the basic
block is always executed, unless the program ends due to a function
- call. DF is the dataflow object. */
+ call. */
static void
-find_invariants_bb (basic_block bb, bool always_reached, bool always_executed,
- struct df *df)
+find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
{
rtx insn;
if (!INSN_P (insn))
continue;
- find_invariants_insn (insn, always_reached, always_executed, df);
+ find_invariants_insn (insn, always_reached, always_executed);
if (always_reached
&& CALL_P (insn)
/* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
bitmap of basic blocks in BODY that are always executed unless the program
- ends due to a function call. DF is the dataflow object. */
+ ends due to a function call. */
static void
find_invariants_body (struct loop *loop, basic_block *body,
- bitmap always_reached, bitmap always_executed,
- struct df *df)
+ bitmap always_reached, bitmap always_executed)
{
unsigned i;
for (i = 0; i < loop->num_nodes; i++)
find_invariants_bb (body[i],
bitmap_bit_p (always_reached, i),
- bitmap_bit_p (always_executed, i),
- df);
+ bitmap_bit_p (always_executed, i));
}
-/* Finds invariants in LOOP. DF is the dataflow object. */
+/* Finds invariants in LOOP. */
static void
-find_invariants (struct loop *loop, struct df *df)
+find_invariants (struct loop *loop)
{
- bitmap may_exit = BITMAP_XMALLOC ();
- bitmap always_reached = BITMAP_XMALLOC ();
- bitmap has_exit = BITMAP_XMALLOC ();
- bitmap always_executed = BITMAP_XMALLOC ();
+ bitmap may_exit = BITMAP_ALLOC (NULL);
+ bitmap always_reached = BITMAP_ALLOC (NULL);
+ bitmap has_exit = BITMAP_ALLOC (NULL);
+ bitmap always_executed = BITMAP_ALLOC (NULL);
basic_block *body = get_loop_body_in_dom_order (loop);
find_exits (loop, body, may_exit, has_exit);
compute_always_reached (loop, body, may_exit, always_reached);
compute_always_reached (loop, body, has_exit, always_executed);
- find_defs (loop, body, df);
- find_invariants_body (loop, body, always_reached, always_executed, df);
+ find_defs (loop, body);
+ find_invariants_body (loop, body, always_reached, always_executed);
- BITMAP_XFREE (always_reached);
- BITMAP_XFREE (always_executed);
- BITMAP_XFREE (may_exit);
- BITMAP_XFREE (has_exit);
+ BITMAP_FREE (always_reached);
+ BITMAP_FREE (always_executed);
+ BITMAP_FREE (may_exit);
+ BITMAP_FREE (has_exit);
free (body);
}
unsigned aregs_needed;
unsigned depno;
struct invariant *dep;
+ bitmap_iterator bi;
*comp_cost = 0;
*regs_needed = 0;
(*regs_needed)++;
(*comp_cost) += inv->cost;
- EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno,
+ EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
{
- dep = VARRAY_GENERIC_PTR_NOGC (invariants, depno);
+ dep = VEC_index (invariant_p, invariants, depno);
get_inv_cost (dep, &acomp_cost, &aregs_needed);
(*regs_needed) += aregs_needed;
(*comp_cost) += acomp_cost;
- });
+ }
}
/* Calculates gain for eliminating invariant INV. REGS_USED is the number
int gain = 0, again;
unsigned aregs_needed, invno;
- for (invno = 0; invno < VARRAY_ACTIVE_SIZE (invariants); invno++)
+ for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++)
{
- inv = VARRAY_GENERIC_PTR_NOGC (invariants, invno);
if (inv->move)
continue;
static void
set_move_mark (unsigned invno)
{
- struct invariant *inv = VARRAY_GENERIC_PTR_NOGC (invariants, invno);
+ struct invariant *inv = VEC_index (invariant_p, invariants, invno);
+ bitmap_iterator bi;
if (inv->move)
return;
if (dump_file)
fprintf (dump_file, "Decided to move invariant %d\n", invno);
- EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, set_move_mark (invno));
+ EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
+ {
+ set_move_mark (invno);
+ }
}
-/* Determines which invariants to move. DF is the dataflow object. */
+/* Determines which invariants to move. */
static void
-find_invariants_to_move (struct df *df)
+find_invariants_to_move (void)
{
unsigned i, regs_used, n_inv_uses, regs_needed = 0, new_regs;
struct invariant *inv = NULL;
- if (flag_move_all_movables)
- {
- /* This is easy & stupid. */
- for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
- {
- inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
- inv->move = true;
- }
- return;
- }
-
- if (!VARRAY_ACTIVE_SIZE (invariants))
+ if (!VEC_length (invariant_p, invariants))
return;
/* Now something slightly more involved. First estimate the number of used
}
}
- for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
+ for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
{
- inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
if (inv->def)
n_inv_uses += inv->def->n_uses;
}
}
}
-/* Move invariant INVNO out of the LOOP. DF is the dataflow object. */
+/* Move invariant INVNO out of the LOOP. */
static void
-move_invariant_reg (struct loop *loop, unsigned invno, struct df *df)
+move_invariant_reg (struct loop *loop, unsigned invno)
{
- struct invariant *inv = VARRAY_GENERIC_PTR_NOGC (invariants, invno);
+ struct invariant *inv = VEC_index (invariant_p, invariants, invno);
unsigned i;
basic_block preheader = loop_preheader_edge (loop)->src;
rtx reg, set;
struct use *use;
+ bitmap_iterator bi;
if (inv->processed)
return;
if (inv->depends_on)
{
- EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i,
+ EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
{
- move_invariant_reg (loop, i, df);
- });
+ move_invariant_reg (loop, i);
+ }
}
/* Move the set out of the loop. If the set is always executed (we could
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);
- SET_DEST (set) = reg;
- reorder_insns (inv->insn, inv->insn, BB_END (preheader));
- df_insn_modify (df, preheader, 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);
+ }
/* Replace the uses we know to be dominated. It saves work for copy
propagation, and also it is necessary so that dependent invariants
}
/* Move selected invariant out of the LOOP. Newly created regs are marked
- in TEMPORARY_REGS. DF is the dataflow object. */
+ in TEMPORARY_REGS. */
static void
-move_invariants (struct loop *loop, struct df *df)
+move_invariants (struct loop *loop)
{
struct invariant *inv;
unsigned i;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
+ for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
{
- inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
if (inv->move)
- move_invariant_reg (loop, i, df);
+ move_invariant_reg (loop, i);
}
}
{
actual_stamp = 1;
- if (!invariants)
- VARRAY_GENERIC_PTR_NOGC_INIT (invariants, 100, "invariants");
+ invariants = VEC_alloc (invariant_p, heap, 100);
}
-/* Frees the data allocated by invariant motion. DF is the dataflow
- object. */
+/* Frees the data allocated by invariant motion. */
static void
-free_inv_motion_data (struct df *df)
+free_inv_motion_data (void)
{
unsigned i;
struct def *def;
DF_REF_DATA (df->defs[i]) = NULL;
}
- for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
+ for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
{
- inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
- BITMAP_XFREE (inv->depends_on);
+ BITMAP_FREE (inv->depends_on);
free (inv);
}
- VARRAY_POP_ALL (invariants);
+ VEC_free (invariant_p, heap, invariants);
}
-/* Move the invariants out of the LOOP. DF is the dataflow object. */
+/* Move the invariants out of the LOOP. */
static void
-move_single_loop_invariants (struct loop *loop, struct df *df)
+move_single_loop_invariants (struct loop *loop)
{
init_inv_motion_data ();
- find_invariants (loop, df);
- find_invariants_to_move (df);
- move_invariants (loop, df);
+ find_invariants (loop);
+ find_invariants_to_move ();
+ move_invariants (loop);
- free_inv_motion_data (df);
+ free_inv_motion_data ();
}
/* Releases the auxiliary data for LOOP. */
{
struct loop *loop;
unsigned i;
- struct df *df = df_init ();
+
+ df = df_init ();
/* Process the loops, innermost first. */
loop = loops->tree_root;
while (loop != loops->tree_root)
{
- move_single_loop_invariants (loop, df);
+ move_single_loop_invariants (loop);
if (loop->next)
{
free_loop_data (loops->parray[i]);
df_finish (df);
+ df = NULL;
+
+#ifdef ENABLE_CHECKING
+ verify_flow_info ();
+#endif
}
OSDN Git Service
