#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "obstack.h"
#include "basic-block.h"
#include "cfgloop.h"
#include "expr.h"
#include "output.h"
#include "function.h"
#include "flags.h"
#include "df.h"
struct loop_data
{
struct loop *outermost_exit;
bool has_call;
};
#define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
struct use
{
rtx *pos;
rtx insn;
struct use *next;
};
struct def
{
struct use *uses;
unsigned n_uses;
unsigned invno;
};
struct invariant
{
unsigned invno;
bool processed;
struct def *def;
rtx insn;
bool always_executed;
bool move;
unsigned cost;
bitmap depends_on;
unsigned stamp;
};
static unsigned actual_stamp;
static varray_type invariants;
static bool
check_maybe_invariant (rtx x)
{
enum rtx_code code = GET_CODE (x);
int i, j;
const char *fmt;
switch (code)
{
case CONST_INT:
case CONST_DOUBLE:
case SYMBOL_REF:
case CONST:
case LABEL_REF:
return true;
case PC:
case CC0:
case UNSPEC_VOLATILE:
case CALL:
return false;
case REG:
return true;
case MEM:
if (MEM_READONLY_P (x))
break;
return false;
case ASM_OPERANDS:
if (MEM_VOLATILE_P (x))
return false;
break;
default:
break;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
{
if (!check_maybe_invariant (XEXP (x, i)))
return false;
}
else if (fmt[i] == 'E')
{
for (j = 0; j < XVECLEN (x, i); j++)
if (!check_maybe_invariant (XVECEXP (x, i, j)))
return false;
}
}
return true;
}
static void
compute_always_reached (struct loop *loop, basic_block *body,
bitmap may_exit, bitmap always_reached)
{
unsigned i;
for (i = 0; i < loop->num_nodes; i++)
{
if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
bitmap_set_bit (always_reached, i);
if (bitmap_bit_p (may_exit, i))
return;
}
}
static void
find_exits (struct loop *loop, basic_block *body,
bitmap may_exit, bitmap has_exit)
{
unsigned i;
edge_iterator ei;
edge e;
struct loop *outermost_exit = loop, *aexit;
bool has_call = false;
rtx insn;
for (i = 0; i < loop->num_nodes; i++)
{
if (body[i]->loop_father == loop)
{
FOR_BB_INSNS (body[i], insn)
{
if (CALL_P (insn)
&& !CONST_OR_PURE_CALL_P (insn))
{
has_call = true;
bitmap_set_bit (may_exit, i);
break;
}
}
FOR_EACH_EDGE (e, ei, body[i]->succs)
{
if (flow_bb_inside_loop_p (loop, e->dest))
continue;
bitmap_set_bit (may_exit, i);
bitmap_set_bit (has_exit, i);
outermost_exit = find_common_loop (outermost_exit,
e->dest->loop_father);
}
continue;
}
if (body[i]->loop_father->header != body[i])
continue;
if (LOOP_DATA (body[i]->loop_father)->has_call)
{
has_call = true;
bitmap_set_bit (may_exit, i);
}
aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
if (aexit != loop)
{
bitmap_set_bit (may_exit, i);
bitmap_set_bit (has_exit, i);
if (flow_loop_nested_p (aexit, outermost_exit))
outermost_exit = aexit;
}
}
loop->aux = xcalloc (1, sizeof (struct loop_data));
LOOP_DATA (loop)->outermost_exit = outermost_exit;
LOOP_DATA (loop)->has_call = has_call;
}
static bool
may_assign_reg_p (rtx x)
{
return can_copy_p (GET_MODE (x));
}
static void
find_defs (struct loop *loop, basic_block *body, struct df *df)
{
unsigned i;
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_FREE (blocks);
}
static void
create_new_invariant (struct def *def, rtx insn, bitmap depends_on,
bool always_executed)
{
struct invariant *inv = xmalloc (sizeof (struct invariant));
rtx set = single_set (insn);
inv->def = def;
inv->always_executed = always_executed;
inv->depends_on = depends_on;
if (def)
inv->cost = rtx_cost (set, SET);
else
inv->cost = rtx_cost (SET_SRC (set), SET);
inv->move = false;
inv->processed = false;
inv->stamp = 0;
inv->insn = insn;
inv->invno = VARRAY_ACTIVE_SIZE (invariants);
if (def)
def->invno = inv->invno;
VARRAY_PUSH_GENERIC_PTR_NOGC (invariants, inv);
if (dump_file)
{
fprintf (dump_file,
"Set in insn %d is invariant (%d), cost %d, depends on ",
INSN_UID (insn), inv->invno, inv->cost);
dump_bitmap (dump_file, inv->depends_on);
}
}
static void
record_use (struct def *def, rtx *use, rtx insn)
{
struct use *u = xmalloc (sizeof (struct use));
if (GET_CODE (*use) == SUBREG)
use = &SUBREG_REG (*use);
if (!REG_P (*use))
abort ();
u->pos = use;
u->insn = insn;
u->next = def->uses;
def->uses = u;
def->n_uses++;
}
static bool
check_dependencies (rtx insn, struct df *df, bitmap depends_on)
{
struct df_link *uses, *defs;
struct ref *use, *def;
basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
struct def *def_data;
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;
def_data = DF_REF_DATA (def);
if (!def_data)
return false;
def_bb = DF_REF_BB (def);
if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
return false;
bitmap_set_bit (depends_on, def_data->invno);
}
return true;
}
static void
find_invariant_insn (rtx insn, bool always_reached, bool always_executed,
struct df *df)
{
struct ref *ref;
struct def *def;
bitmap depends_on;
rtx set, dest;
bool simple = true;
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;
set = single_set (insn);
if (!set)
return;
dest = SET_DEST (set);
if (GET_CODE (dest) != REG
|| HARD_REGISTER_P (dest))
simple = false;
if (!check_maybe_invariant (SET_SRC (set))
|| !may_assign_reg_p (SET_DEST (set)))
return;
if (may_trap_p (PATTERN (insn)))
{
if (!always_reached)
return;
if (flag_non_call_exceptions)
return;
}
depends_on = BITMAP_ALLOC (NULL);
if (!check_dependencies (insn, df, depends_on))
{
BITMAP_FREE (depends_on);
return;
}
if (simple)
{
ref = df_find_def (df, insn, dest);
def = xcalloc (1, sizeof (struct def));
DF_REF_DATA (ref) = def;
}
else
def = NULL;
create_new_invariant (def, insn, depends_on, always_executed);
}
static void
record_uses (rtx insn, struct df *df)
{
struct df_link *uses, *defs;
struct ref *use, *def;
basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
{
use = uses->ref;
defs = DF_REF_CHAIN (use);
if (!defs || defs->next)
continue;
def = defs->ref;
if (!DF_REF_DATA (def))
continue;
def_bb = DF_REF_BB (def);
if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
continue;
record_use (DF_REF_DATA (def), DF_REF_LOC (use), DF_REF_INSN (use));
}
}
static void
find_invariants_insn (rtx insn, bool always_reached, bool always_executed,
struct df *df)
{
find_invariant_insn (insn, always_reached, always_executed, df);
record_uses (insn, df);
}
static void
find_invariants_bb (basic_block bb, bool always_reached, bool always_executed,
struct df *df)
{
rtx insn;
FOR_BB_INSNS (bb, insn)
{
if (!INSN_P (insn))
continue;
find_invariants_insn (insn, always_reached, always_executed, df);
if (always_reached
&& CALL_P (insn)
&& !CONST_OR_PURE_CALL_P (insn))
always_reached = false;
}
}
static void
find_invariants_body (struct loop *loop, basic_block *body,
bitmap always_reached, bitmap always_executed,
struct df *df)
{
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);
}
static void
find_invariants (struct loop *loop, struct df *df)
{
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);
BITMAP_FREE (always_reached);
BITMAP_FREE (always_executed);
BITMAP_FREE (may_exit);
BITMAP_FREE (has_exit);
free (body);
}
static void
free_use_list (struct use *use)
{
struct use *next;
for (; use; use = next)
{
next = use->next;
free (use);
}
}
static void
get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed)
{
int acomp_cost;
unsigned aregs_needed;
unsigned depno;
struct invariant *dep;
bitmap_iterator bi;
*comp_cost = 0;
*regs_needed = 0;
if (inv->move
|| inv->stamp == actual_stamp)
return;
inv->stamp = actual_stamp;
(*regs_needed)++;
(*comp_cost) += inv->cost;
EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
{
dep = VARRAY_GENERIC_PTR_NOGC (invariants, depno);
get_inv_cost (dep, &acomp_cost, &aregs_needed);
if (aregs_needed
&& dep->always_executed
&& !dep->def->uses->next)
{
aregs_needed--;
}
(*regs_needed) += aregs_needed;
(*comp_cost) += acomp_cost;
}
}
static int
gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
unsigned new_regs, unsigned regs_used, unsigned n_inv_uses)
{
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));
return comp_cost - size_cost;
}
static int
best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
unsigned new_regs, unsigned regs_used,
unsigned n_inv_uses)
{
struct invariant *inv;
int gain = 0, again;
unsigned aregs_needed, invno;
for (invno = 0; invno < VARRAY_ACTIVE_SIZE (invariants); invno++)
{
inv = VARRAY_GENERIC_PTR_NOGC (invariants, invno);
if (inv->move)
continue;
again = gain_for_invariant (inv, &aregs_needed,
new_regs, regs_used, n_inv_uses);
if (again > gain)
{
gain = again;
*best = inv;
*regs_needed = aregs_needed;
}
}
return gain;
}
static void
set_move_mark (unsigned invno)
{
struct invariant *inv = VARRAY_GENERIC_PTR_NOGC (invariants, invno);
bitmap_iterator bi;
if (inv->move)
return;
inv->move = true;
if (dump_file)
fprintf (dump_file, "Decided to move invariant %d\n", invno);
EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
{
set_move_mark (invno);
}
}
static void
find_invariants_to_move (struct df *df)
{
unsigned i, regs_used, n_inv_uses, regs_needed = 0, new_regs;
struct invariant *inv = NULL;
if (!VARRAY_ACTIVE_SIZE (invariants))
return;
n_inv_uses = 0;
regs_used = 2;
for (i = 0; i < df->n_regs; i++)
{
if (!DF_REGNO_FIRST_DEF (df, i) && DF_REGNO_LAST_USE (df, i))
{
regs_used++;
}
}
for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
{
inv = VARRAY_GENERIC_PTR_NOGC (invariants, 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)
{
set_move_mark (inv->invno);
new_regs += regs_needed;
}
}
static void
move_invariant_reg (struct loop *loop, unsigned invno, struct df *df)
{
struct invariant *inv = VARRAY_GENERIC_PTR_NOGC (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;
inv->processed = true;
if (inv->depends_on)
{
EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
{
move_invariant_reg (loop, i, df);
}
}
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);
SET_DEST (set) = reg;
reorder_insns (inv->insn, inv->insn, BB_END (preheader));
df_insn_modify (df, preheader, inv->insn);
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);
}
}
}
static void
move_invariants (struct loop *loop, struct df *df)
{
struct invariant *inv;
unsigned i;
for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
{
inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
if (inv->move)
move_invariant_reg (loop, i, df);
}
}
static void
init_inv_motion_data (void)
{
actual_stamp = 1;
if (!invariants)
VARRAY_GENERIC_PTR_NOGC_INIT (invariants, 100, "invariants");
}
static void
free_inv_motion_data (struct df *df)
{
unsigned i;
struct def *def;
struct invariant *inv;
for (i = 0; i < df->n_defs; i++)
{
if (!df->defs[i])
continue;
def = DF_REF_DATA (df->defs[i]);
if (!def)
continue;
free_use_list (def->uses);
free (def);
DF_REF_DATA (df->defs[i]) = NULL;
}
for (i = 0; i < VARRAY_ACTIVE_SIZE (invariants); i++)
{
inv = VARRAY_GENERIC_PTR_NOGC (invariants, i);
BITMAP_FREE (inv->depends_on);
free (inv);
}
VARRAY_POP_ALL (invariants);
}
static void
move_single_loop_invariants (struct loop *loop, struct df *df)
{
init_inv_motion_data ();
find_invariants (loop, df);
find_invariants_to_move (df);
move_invariants (loop, df);
free_inv_motion_data (df);
}
static void
free_loop_data (struct loop *loop)
{
struct loop_data *data = LOOP_DATA (loop);
free (data);
loop->aux = NULL;
}
void
move_loop_invariants (struct loops *loops)
{
struct loop *loop;
unsigned i;
struct df *df = df_init ();
loop = loops->tree_root;
while (loop->inner)
loop = loop->inner;
while (loop != loops->tree_root)
{
move_single_loop_invariants (loop, df);
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]);
df_finish (df);
}