#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"
bool
just_once_each_iteration_p (struct loop *loop, basic_block bb)
{
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
return false;
if (bb->loop_father != loop)
return false;
if (bb->flags & BB_IRREDUCIBLE_LOOP)
return false;
return true;
}
struct edge
{
int src, dest;
struct edge *pred_next, *succ_next;
void *data;
};
struct vertex
{
struct edge *pred, *succ;
int component;
int post;
};
struct graph
{
int n_vertices;
struct vertex *vertices;
};
extern void dump_graph (FILE *, struct graph *);
void dump_graph (FILE *f, struct graph *g)
{
int i;
struct edge *e;
for (i = 0; i < g->n_vertices; i++)
{
if (!g->vertices[i].pred
&& !g->vertices[i].succ)
continue;
fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
for (e = g->vertices[i].pred; e; e = e->pred_next)
fprintf (f, " %d", e->src);
fprintf (f, "\n");
fprintf (f, "\t->");
for (e = g->vertices[i].succ; e; e = e->succ_next)
fprintf (f, " %d", e->dest);
fprintf (f, "\n");
}
}
static struct graph *
new_graph (int n_vertices)
{
struct graph *g = xmalloc (sizeof (struct graph));
g->n_vertices = n_vertices;
g->vertices = xcalloc (n_vertices, sizeof (struct vertex));
return g;
}
static void
add_edge (struct graph *g, int f, int t, void *data)
{
struct edge *e = xmalloc (sizeof (struct edge));
e->src = f;
e->dest = t;
e->data = data;
e->pred_next = g->vertices[t].pred;
g->vertices[t].pred = e;
e->succ_next = g->vertices[f].succ;
g->vertices[f].succ = e;
}
static void
dfs (struct graph *g, int *qs, int nq, int *qt, bool forward)
{
int i, tick = 0, v, comp = 0, top;
struct edge *e;
struct edge **stack = xmalloc (sizeof (struct edge *) * g->n_vertices);
for (i = 0; i < g->n_vertices; i++)
{
g->vertices[i].component = -1;
g->vertices[i].post = -1;
}
#define FST_EDGE(V) (forward ? g->vertices[(V)].succ : g->vertices[(V)].pred)
#define NEXT_EDGE(E) (forward ? (E)->succ_next : (E)->pred_next)
#define EDGE_SRC(E) (forward ? (E)->src : (E)->dest)
#define EDGE_DEST(E) (forward ? (E)->dest : (E)->src)
for (i = 0; i < nq; i++)
{
v = qs[i];
if (g->vertices[v].post != -1)
continue;
g->vertices[v].component = comp++;
e = FST_EDGE (v);
top = 0;
while (1)
{
while (e && g->vertices[EDGE_DEST (e)].component != -1)
e = NEXT_EDGE (e);
if (!e)
{
if (qt)
qt[tick] = v;
g->vertices[v].post = tick++;
if (!top)
break;
e = stack[--top];
v = EDGE_SRC (e);
e = NEXT_EDGE (e);
continue;
}
stack[top++] = e;
v = EDGE_DEST (e);
e = FST_EDGE (v);
g->vertices[v].component = comp - 1;
}
}
free (stack);
}
static void
check_irred (struct graph *g, struct edge *e)
{
edge real = e->data;
gcc_assert (g->vertices[e->src].component >= g->vertices[e->dest].component);
if (g->vertices[e->src].component != g->vertices[e->dest].component)
return;
real->flags |= EDGE_IRREDUCIBLE_LOOP;
if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
real->src->flags |= BB_IRREDUCIBLE_LOOP;
}
static void
for_each_edge (struct graph *g,
void (callback) (struct graph *, struct edge *))
{
struct edge *e;
int i;
for (i = 0; i < g->n_vertices; i++)
for (e = g->vertices[i].succ; e; e = e->succ_next)
callback (g, e);
}
static void
free_graph (struct graph *g)
{
struct edge *e, *n;
int i;
for (i = 0; i < g->n_vertices; i++)
for (e = g->vertices[i].succ; e; e = n)
{
n = e->succ_next;
free (e);
}
free (g->vertices);
free (g);
}
#define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
#define BB_REPR(BB) ((BB)->index + 1)
void
mark_irreducible_loops (struct loops *loops)
{
basic_block act;
edge e;
edge_iterator ei;
int i, src, dest;
struct graph *g;
int *queue1 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
int *queue2 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
int nq, depth;
struct loop *cloop;
FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
{
act->flags &= ~BB_IRREDUCIBLE_LOOP;
FOR_EACH_EDGE (e, ei, act->succs)
e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
}
g = new_graph (last_basic_block + loops->num);
FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
FOR_EACH_EDGE (e, ei, act->succs)
{
if (e->dest == EXIT_BLOCK_PTR)
continue;
if (e->dest->loop_father->header == e->dest
&& e->dest->loop_father->latch == act)
continue;
src = BB_REPR (act);
dest = BB_REPR (e->dest);
if (e->dest->loop_father->header == e->dest)
dest = LOOP_REPR (e->dest->loop_father);
if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
{
depth = find_common_loop (act->loop_father,
e->dest->loop_father)->depth + 1;
if (depth == act->loop_father->depth)
cloop = act->loop_father;
else
cloop = act->loop_father->pred[depth];
src = LOOP_REPR (cloop);
}
add_edge (g, src, dest, e);
}
nq = 0;
FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
{
queue1[nq++] = BB_REPR (act);
}
for (i = 1; i < (int) loops->num; i++)
if (loops->parray[i])
queue1[nq++] = LOOP_REPR (loops->parray[i]);
dfs (g, queue1, nq, queue2, false);
for (i = 0; i < nq; i++)
queue1[i] = queue2[nq - i - 1];
dfs (g, queue1, nq, NULL, true);
for_each_edge (g, check_irred);
free_graph (g);
free (queue1);
free (queue2);
loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
}
int
num_loop_insns (struct loop *loop)
{
basic_block *bbs, bb;
unsigned i, ninsns = 0;
rtx insn;
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
{
bb = bbs[i];
ninsns++;
for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
if (INSN_P (insn))
ninsns++;
}
free(bbs);
return ninsns;
}
int
average_num_loop_insns (struct loop *loop)
{
basic_block *bbs, bb;
unsigned i, binsns, ninsns, ratio;
rtx insn;
ninsns = 0;
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
{
bb = bbs[i];
binsns = 1;
for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
if (INSN_P (insn))
binsns++;
ratio = loop->header->frequency == 0
? BB_FREQ_MAX
: (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
ninsns += binsns * ratio;
}
free(bbs);
ninsns /= BB_FREQ_MAX;
if (!ninsns)
ninsns = 1;
return ninsns;
}
unsigned
expected_loop_iterations (const struct loop *loop)
{
edge e;
edge_iterator ei;
if (loop->header->count)
{
gcov_type count_in, count_latch, expected;
count_in = 0;
count_latch = 0;
FOR_EACH_EDGE (e, ei, loop->header->preds)
if (e->src == loop->latch)
count_latch = e->count;
else
count_in += e->count;
if (count_in == 0)
expected = count_latch * 2;
else
expected = (count_latch + count_in - 1) / count_in;
return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
}
else
{
int freq_in, freq_latch;
freq_in = 0;
freq_latch = 0;
FOR_EACH_EDGE (e, ei, loop->header->preds)
if (e->src == loop->latch)
freq_latch = EDGE_FREQUENCY (e);
else
freq_in += EDGE_FREQUENCY (e);
if (freq_in == 0)
return freq_latch * 2;
return (freq_latch + freq_in - 1) / freq_in;
}
}
unsigned
get_loop_level (const struct loop *loop)
{
const struct loop *ploop;
unsigned mx = 0, l;
for (ploop = loop->inner; ploop; ploop = ploop->next)
{
l = get_loop_level (ploop);
if (l >= mx)
mx = l + 1;
}
return mx;
}
static unsigned
seq_cost (rtx seq)
{
unsigned cost = 0;
rtx set;
for (; seq; seq = NEXT_INSN (seq))
{
set = single_set (seq);
if (set)
cost += rtx_cost (set, SET);
else
cost++;
}
return cost;
}
unsigned target_avail_regs;
unsigned target_res_regs;
unsigned target_small_cost;
unsigned target_pres_cost;
unsigned target_spill_cost;
void
init_set_costs (void)
{
rtx seq;
rtx reg1 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER);
rtx reg2 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER + 1);
rtx addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 2);
rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
unsigned i;
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
&& !fixed_regs[i])
target_avail_regs++;
target_res_regs = 3;
start_sequence ();
emit_move_insn (reg1, reg2);
seq = get_insns ();
end_sequence ();
target_small_cost = seq_cost (seq);
#if defined(TARGET_ARM)
if (TARGET_ARM)
target_small_cost = seq_cost (seq) -1;
#endif
target_pres_cost = 2 * target_small_cost;
start_sequence ();
emit_move_insn (mem, reg1);
emit_move_insn (reg2, mem);
seq = get_insns ();
end_sequence ();
target_spill_cost = seq_cost (seq);
}
unsigned
global_cost_for_size (unsigned size, unsigned regs_used, unsigned n_uses)
{
unsigned regs_needed = regs_used + size;
unsigned cost = 0;
if (regs_needed + target_res_regs <= target_avail_regs)
cost += target_small_cost * size;
else if (regs_needed <= target_avail_regs)
cost += target_pres_cost * size;
else
{
cost += target_pres_cost * size;
cost += target_spill_cost * n_uses * (regs_needed - target_avail_regs) / regs_needed;
}
return cost;
}