#include "config.h"
#include "system.h"
#include "rtl.h"
#include "expr.h"
#include "varray.h"
#include "partition.h"
#include "sbitmap.h"
#include "hashtab.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "flags.h"
#include "function.h"
#include "real.h"
#include "insn-config.h"
#include "recog.h"
#include "basic-block.h"
#include "output.h"
#include "ssa.h"
static int conservative_reg_partition;
int in_ssa_form = 0;
varray_type ssa_definition;
varray_type ssa_rename_from;
htab_t ssa_rename_from_ht;
static rtx *ssa_rename_to_pseudo;
static rtx ssa_rename_to_hard[FIRST_PSEUDO_REGISTER][NUM_MACHINE_MODES];
typedef struct {
unsigned int reg;
rtx original;
} ssa_rename_from_pair;
struct ssa_rename_from_hash_table_data {
sbitmap canonical_elements;
partition reg_partition;
};
static rtx gen_sequence
PARAMS ((void));
static void ssa_rename_from_initialize
PARAMS ((void));
static rtx ssa_rename_from_lookup
PARAMS ((int reg));
static unsigned int original_register
PARAMS ((unsigned int regno));
static void ssa_rename_from_insert
PARAMS ((unsigned int reg, rtx r));
static void ssa_rename_from_free
PARAMS ((void));
typedef int (*srf_trav) PARAMS ((int regno, rtx r, sbitmap canonical_elements, partition reg_partition));
static void ssa_rename_from_traverse
PARAMS ((htab_trav callback_function, sbitmap canonical_elements, partition reg_partition));
void ssa_rename_from_print
PARAMS ((void));
static int ssa_rename_from_print_1
PARAMS ((void **slot, void *data));
static hashval_t ssa_rename_from_hash_function
PARAMS ((const void * srfp));
static int ssa_rename_from_equal
PARAMS ((const void *srfp1, const void *srfp2));
static void ssa_rename_from_delete
PARAMS ((void *srfp));
static rtx ssa_rename_to_lookup
PARAMS ((rtx reg));
static void ssa_rename_to_insert
PARAMS ((rtx reg, rtx r));
static unsigned int ssa_max_reg_num;
struct rename_context;
static inline rtx * phi_alternative
PARAMS ((rtx, int));
static void compute_dominance_frontiers_1
PARAMS ((sbitmap *frontiers, dominance_info idom, int bb, sbitmap done));
static void find_evaluations_1
PARAMS ((rtx dest, rtx set, void *data));
static void find_evaluations
PARAMS ((sbitmap *evals, int nregs));
static void compute_iterated_dominance_frontiers
PARAMS ((sbitmap *idfs, sbitmap *frontiers, sbitmap *evals, int nregs));
static void insert_phi_node
PARAMS ((int regno, int b));
static void insert_phi_nodes
PARAMS ((sbitmap *idfs, sbitmap *evals, int nregs));
static void create_delayed_rename
PARAMS ((struct rename_context *, rtx *));
static void apply_delayed_renames
PARAMS ((struct rename_context *));
static int rename_insn_1
PARAMS ((rtx *ptr, void *data));
static void rename_block
PARAMS ((int b, dominance_info dom));
static void rename_registers
PARAMS ((int nregs, dominance_info idom));
static inline int ephi_add_node
PARAMS ((rtx reg, rtx *nodes, int *n_nodes));
static int * ephi_forward
PARAMS ((int t, sbitmap visited, sbitmap *succ, int *tstack));
static void ephi_backward
PARAMS ((int t, sbitmap visited, sbitmap *pred, rtx *nodes));
static void ephi_create
PARAMS ((int t, sbitmap visited, sbitmap *pred, sbitmap *succ, rtx *nodes));
static void eliminate_phi
PARAMS ((edge e, partition reg_partition));
static int make_regs_equivalent_over_bad_edges
PARAMS ((int bb, partition reg_partition));
static int make_equivalent_phi_alternatives_equivalent
PARAMS ((int bb, partition reg_partition));
static partition compute_conservative_reg_partition
PARAMS ((void));
static int record_canonical_element_1
PARAMS ((void **srfp, void *data));
static int check_hard_regs_in_partition
PARAMS ((partition reg_partition));
static int rename_equivalent_regs_in_insn
PARAMS ((rtx *ptr, void *data));
static int coalesce_if_unconflicting
PARAMS ((partition p, conflict_graph conflicts, int reg1, int reg2));
static int coalesce_regs_in_copies
PARAMS ((basic_block bb, partition p, conflict_graph conflicts));
static int coalesce_reg_in_phi
PARAMS ((rtx, int dest_regno, int src_regno, void *data));
static int coalesce_regs_in_successor_phi_nodes
PARAMS ((basic_block bb, partition p, conflict_graph conflicts));
static partition compute_coalesced_reg_partition
PARAMS ((void));
static int mark_reg_in_phi
PARAMS ((rtx *ptr, void *data));
static void mark_phi_and_copy_regs
PARAMS ((regset phi_set));
static int rename_equivalent_regs_in_insn
PARAMS ((rtx *ptr, void *data));
static void rename_equivalent_regs
PARAMS ((partition reg_partition));
static int conflicting_hard_regs_p
PARAMS ((int reg1, int reg2));
static rtx
ssa_rename_to_lookup (reg)
rtx reg;
{
if (!HARD_REGISTER_P (reg))
return ssa_rename_to_pseudo[REGNO (reg) - FIRST_PSEUDO_REGISTER];
else
return ssa_rename_to_hard[REGNO (reg)][GET_MODE (reg)];
}
static void
ssa_rename_to_insert(reg, r)
rtx reg;
rtx r;
{
if (!HARD_REGISTER_P (reg))
ssa_rename_to_pseudo[REGNO (reg) - FIRST_PSEUDO_REGISTER] = r;
else
ssa_rename_to_hard[REGNO (reg)][GET_MODE (reg)] = r;
}
static void
ssa_rename_from_initialize ()
{
ssa_rename_from_ht = htab_create (64,
&ssa_rename_from_hash_function,
&ssa_rename_from_equal,
&ssa_rename_from_delete);
}
static rtx
ssa_rename_from_lookup (reg)
int reg;
{
ssa_rename_from_pair srfp;
ssa_rename_from_pair *answer;
srfp.reg = reg;
srfp.original = NULL_RTX;
answer = (ssa_rename_from_pair *)
htab_find_with_hash (ssa_rename_from_ht, (void *) &srfp, reg);
return (answer == 0 ? NULL_RTX : answer->original);
}
static unsigned int
original_register (regno)
unsigned int regno;
{
rtx original_rtx = ssa_rename_from_lookup (regno);
return original_rtx != NULL_RTX ? REGNO (original_rtx) : regno;
}
static void
ssa_rename_from_insert (reg, r)
unsigned int reg;
rtx r;
{
void **slot;
ssa_rename_from_pair *srfp = xmalloc (sizeof (ssa_rename_from_pair));
srfp->reg = reg;
srfp->original = r;
slot = htab_find_slot_with_hash (ssa_rename_from_ht, (const void *) srfp,
reg, INSERT);
if (*slot != 0)
free ((void *) *slot);
*slot = srfp;
}
static void
ssa_rename_from_traverse (callback_function,
canonical_elements, reg_partition)
htab_trav callback_function;
sbitmap canonical_elements;
partition reg_partition;
{
struct ssa_rename_from_hash_table_data srfhd;
srfhd.canonical_elements = canonical_elements;
srfhd.reg_partition = reg_partition;
htab_traverse (ssa_rename_from_ht, callback_function, (void *) &srfhd);
}
static void
ssa_rename_from_free ()
{
htab_delete (ssa_rename_from_ht);
}
void
ssa_rename_from_print ()
{
printf ("ssa_rename_from's hash table contents:\n");
htab_traverse (ssa_rename_from_ht, &ssa_rename_from_print_1, NULL);
}
static int
ssa_rename_from_print_1 (slot, data)
void **slot;
void *data ATTRIBUTE_UNUSED;
{
ssa_rename_from_pair * p = *slot;
printf ("ssa_rename_from maps pseudo %i to original %i.\n",
p->reg, REGNO (p->original));
return 1;
}
static hashval_t
ssa_rename_from_hash_function (srfp)
const void *srfp;
{
return ((const ssa_rename_from_pair *) srfp)->reg;
}
static int
ssa_rename_from_equal (srfp1, srfp2)
const void *srfp1;
const void *srfp2;
{
return ssa_rename_from_hash_function (srfp1) ==
ssa_rename_from_hash_function (srfp2);
}
static void
ssa_rename_from_delete (srfp)
void *srfp;
{
free (srfp);
}
static inline rtx *
phi_alternative (set, c)
rtx set;
int c;
{
rtvec phi_vec = XVEC (SET_SRC (set), 0);
int v;
for (v = GET_NUM_ELEM (phi_vec) - 2; v >= 0; v -= 2)
if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c)
return &RTVEC_ELT (phi_vec, v);
return NULL;
}
int
remove_phi_alternative (set, block)
rtx set;
basic_block block;
{
rtvec phi_vec = XVEC (SET_SRC (set), 0);
int num_elem = GET_NUM_ELEM (phi_vec);
int v, c;
c = block->index;
for (v = num_elem - 2; v >= 0; v -= 2)
if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c)
{
if (v < num_elem - 2)
{
RTVEC_ELT (phi_vec, v) = RTVEC_ELT (phi_vec, num_elem - 2);
RTVEC_ELT (phi_vec, v + 1) = RTVEC_ELT (phi_vec, num_elem - 1);
}
PUT_NUM_ELEM (phi_vec, num_elem - 2);
return 1;
}
return 0;
}
static sbitmap *fe_evals;
static int fe_current_bb;
static void
find_evaluations_1 (dest, set, data)
rtx dest;
rtx set ATTRIBUTE_UNUSED;
void *data ATTRIBUTE_UNUSED;
{
if (GET_CODE (dest) == REG
&& CONVERT_REGISTER_TO_SSA_P (REGNO (dest)))
SET_BIT (fe_evals[REGNO (dest)], fe_current_bb);
}
static void
find_evaluations (evals, nregs)
sbitmap *evals;
int nregs;
{
basic_block bb;
sbitmap_vector_zero (evals, nregs);
fe_evals = evals;
FOR_EACH_BB_REVERSE (bb)
{
rtx p, last;
fe_current_bb = bb->index;
p = bb->head;
last = bb->end;
while (1)
{
if (INSN_P (p))
note_stores (PATTERN (p), find_evaluations_1, NULL);
if (p == last)
break;
p = NEXT_INSN (p);
}
}
}
static void
compute_dominance_frontiers_1 (frontiers, idom, bb, done)
sbitmap *frontiers;
dominance_info idom;
int bb;
sbitmap done;
{
basic_block b = BASIC_BLOCK (bb);
edge e;
basic_block c;
SET_BIT (done, bb);
sbitmap_zero (frontiers[bb]);
FOR_EACH_BB (c)
if (get_immediate_dominator (idom, c)->index == bb
&& ! TEST_BIT (done, c->index))
compute_dominance_frontiers_1 (frontiers, idom, c->index, done);
for (e = b->succ; e; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR)
continue;
if (get_immediate_dominator (idom, e->dest)->index != bb)
SET_BIT (frontiers[bb], e->dest->index);
}
FOR_EACH_BB (c)
if (get_immediate_dominator (idom, c)->index == bb)
{
int x;
EXECUTE_IF_SET_IN_SBITMAP (frontiers[c->index], 0, x,
{
if (get_immediate_dominator (idom, BASIC_BLOCK (x))->index != bb)
SET_BIT (frontiers[bb], x);
});
}
}
void
compute_dominance_frontiers (frontiers, idom)
sbitmap *frontiers;
dominance_info idom;
{
sbitmap done = sbitmap_alloc (last_basic_block);
sbitmap_zero (done);
compute_dominance_frontiers_1 (frontiers, idom, 0, done);
sbitmap_free (done);
}
static void
compute_iterated_dominance_frontiers (idfs, frontiers, evals, nregs)
sbitmap *idfs;
sbitmap *frontiers;
sbitmap *evals;
int nregs;
{
sbitmap worklist;
int reg, passes = 0;
worklist = sbitmap_alloc (last_basic_block);
for (reg = 0; reg < nregs; ++reg)
{
sbitmap idf = idfs[reg];
int b, changed;
sbitmap_copy (worklist, evals[reg]);
sbitmap_zero (idf);
do
{
changed = 0;
passes++;
EXECUTE_IF_SET_IN_SBITMAP (worklist, 0, b,
{
RESET_BIT (worklist, b);
sbitmap_union_of_diff (worklist, worklist, frontiers[b], idf);
sbitmap_a_or_b (idf, idf, frontiers[b]);
changed = 1;
});
}
while (changed);
}
sbitmap_free (worklist);
if (rtl_dump_file)
{
fprintf (rtl_dump_file,
"Iterated dominance frontier: %d passes on %d regs.\n",
passes, nregs);
}
}
static void
insert_phi_node (regno, bb)
int regno, bb;
{
basic_block b = BASIC_BLOCK (bb);
edge e;
int npred, i;
rtvec vec;
rtx phi, reg;
rtx insn;
int end_p;
for (e = b->pred, npred = 0; e; e = e->pred_next)
if (e->src != ENTRY_BLOCK_PTR)
npred++;
if (npred == 0)
return;
reg = regno_reg_rtx[regno];
vec = rtvec_alloc (npred * 2);
for (e = b->pred, i = 0; e ; e = e->pred_next, i += 2)
if (e->src != ENTRY_BLOCK_PTR)
{
RTVEC_ELT (vec, i + 0) = pc_rtx;
RTVEC_ELT (vec, i + 1) = GEN_INT (e->src->index);
}
phi = gen_rtx_PHI (VOIDmode, vec);
phi = gen_rtx_SET (VOIDmode, reg, phi);
insn = first_insn_after_basic_block_note (b);
end_p = PREV_INSN (insn) == b->end;
emit_insn_before (phi, insn);
if (end_p)
b->end = PREV_INSN (insn);
}
static void
insert_phi_nodes (idfs, evals, nregs)
sbitmap *idfs;
sbitmap *evals ATTRIBUTE_UNUSED;
int nregs;
{
int reg;
for (reg = 0; reg < nregs; ++reg)
if (CONVERT_REGISTER_TO_SSA_P (reg))
{
int b;
EXECUTE_IF_SET_IN_SBITMAP (idfs[reg], 0, b,
{
if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, reg))
insert_phi_node (reg, b);
});
}
}
struct rename_set_data
{
struct rename_set_data *next;
rtx *reg_loc;
rtx old_reg;
rtx new_reg;
rtx prev_reg;
rtx set_insn;
};
struct rename_context
{
struct rename_set_data *new_renames;
struct rename_set_data *done_renames;
rtx current_insn;
};
static void
create_delayed_rename (c, reg_loc)
struct rename_context *c;
rtx *reg_loc;
{
struct rename_set_data *r;
r = (struct rename_set_data *) xmalloc (sizeof(*r));
if (GET_CODE (*reg_loc) != REG
|| !CONVERT_REGISTER_TO_SSA_P (REGNO (*reg_loc)))
abort ();
r->reg_loc = reg_loc;
r->old_reg = *reg_loc;
r->prev_reg = ssa_rename_to_lookup(r->old_reg);
r->set_insn = c->current_insn;
r->next = c->new_renames;
c->new_renames = r;
}
#define RENAME_NO_RTX pc_rtx
static void
apply_delayed_renames (c)
struct rename_context *c;
{
struct rename_set_data *r;
struct rename_set_data *last_r = NULL;
for (r = c->new_renames; r != NULL; r = r->next)
{
int new_regno;
if (ssa_rename_to_lookup (r->old_reg) != r->prev_reg)
abort ();
if (r->prev_reg == NULL_RTX && !HARD_REGISTER_P (r->old_reg))
{
r->new_reg = r->old_reg;
r->prev_reg = RENAME_NO_RTX;
}
else
r->new_reg = gen_reg_rtx (GET_MODE (r->old_reg));
new_regno = REGNO (r->new_reg);
ssa_rename_to_insert (r->old_reg, r->new_reg);
if (new_regno >= (int) ssa_definition->num_elements)
{
int new_limit = new_regno * 5 / 4;
VARRAY_GROW (ssa_definition, new_limit);
}
VARRAY_RTX (ssa_definition, new_regno) = r->set_insn;
ssa_rename_from_insert (new_regno, r->old_reg);
last_r = r;
}
if (last_r != NULL)
{
last_r->next = c->done_renames;
c->done_renames = c->new_renames;
c->new_renames = NULL;
}
}
static int
rename_insn_1 (ptr, data)
rtx *ptr;
void *data;
{
rtx x = *ptr;
struct rename_context *context = data;
if (x == NULL_RTX)
return 0;
switch (GET_CODE (x))
{
case SET:
{
rtx *destp = &SET_DEST (x);
rtx dest = SET_DEST (x);
if (GET_CODE (dest) == SUBREG
&& (GET_MODE_SIZE (GET_MODE (dest))
> GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
&& GET_CODE (SUBREG_REG (dest)) == REG
&& CONVERT_REGISTER_TO_SSA_P (REGNO (SUBREG_REG (dest))))
{
destp = &XEXP (dest, 0);
dest = XEXP (dest, 0);
}
if (GET_CODE (dest) == STRICT_LOW_PART
|| GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == SIGN_EXTRACT
|| GET_CODE (dest) == ZERO_EXTRACT)
{
rtx i, reg;
reg = dest;
while (GET_CODE (reg) == STRICT_LOW_PART
|| GET_CODE (reg) == SUBREG
|| GET_CODE (reg) == SIGN_EXTRACT
|| GET_CODE (reg) == ZERO_EXTRACT)
reg = XEXP (reg, 0);
if (GET_CODE (reg) == REG
&& CONVERT_REGISTER_TO_SSA_P (REGNO (reg)))
{
struct rename_set_data *saved_new_renames;
saved_new_renames = context->new_renames;
context->new_renames = NULL;
i = emit_insn (gen_rtx_SET (VOIDmode, reg, reg));
for_each_rtx (&i, rename_insn_1, data);
apply_delayed_renames (context);
context->new_renames = saved_new_renames;
}
}
else if (GET_CODE (dest) == REG
&& CONVERT_REGISTER_TO_SSA_P (REGNO (dest)))
{
create_delayed_rename (context, destp);
if (GET_CODE (x) == SET)
for_each_rtx (&SET_SRC (x), rename_insn_1, data);
return -1;
}
return 0;
}
case REG:
if (CONVERT_REGISTER_TO_SSA_P (REGNO (x))
&& REGNO (x) < ssa_max_reg_num)
{
rtx new_reg = ssa_rename_to_lookup (x);
if (new_reg != RENAME_NO_RTX && new_reg != NULL_RTX)
{
if (GET_MODE (x) != GET_MODE (new_reg))
abort ();
*ptr = new_reg;
}
else
{
*ptr = gen_reg_rtx (GET_MODE (x));
}
}
return -1;
case CLOBBER:
{
rtx dest = XCEXP (x, 0, CLOBBER);
if (REG_P (dest))
{
if (CONVERT_REGISTER_TO_SSA_P (REGNO (dest))
&& REGNO (dest) < ssa_max_reg_num)
{
rtx new_reg = ssa_rename_to_lookup (dest);
if (new_reg != NULL_RTX && new_reg != RENAME_NO_RTX)
XCEXP (x, 0, CLOBBER) = new_reg;
}
return -1;
}
else
return 0;
}
case PHI:
return -1;
default:
return 0;
}
}
static rtx
gen_sequence ()
{
rtx first_insn = get_insns ();
rtx result;
rtx tem;
int i;
int len;
len = 0;
for (tem = first_insn; tem; tem = NEXT_INSN (tem))
len++;
result = gen_rtx_SEQUENCE (VOIDmode, rtvec_alloc (len));
for (i = 0, tem = first_insn; tem; tem = NEXT_INSN (tem), i++)
XVECEXP (result, 0, i) = tem;
return result;
}
static void
rename_block (bb, idom)
int bb;
dominance_info idom;
{
basic_block b = BASIC_BLOCK (bb);
edge e;
rtx insn, next, last;
struct rename_set_data *set_data = NULL;
basic_block c;
next = b->head;
last = b->end;
do
{
insn = next;
if (INSN_P (insn))
{
struct rename_context context;
context.done_renames = set_data;
context.new_renames = NULL;
context.current_insn = insn;
start_sequence ();
for_each_rtx (&PATTERN (insn), rename_insn_1, &context);
for_each_rtx (®_NOTES (insn), rename_insn_1, &context);
if (get_insns () != NULL_RTX)
{
rtx seq;
int i;
emit (PATTERN (insn));
seq = gen_sequence ();
for (i = 0; i < XVECLEN (seq, 0); i++)
XVECEXP (seq, 0, i) = PATTERN (XVECEXP (seq, 0, i));
PATTERN (insn) = seq;
}
end_sequence ();
apply_delayed_renames (&context);
set_data = context.done_renames;
}
next = NEXT_INSN (insn);
}
while (insn != last);
for (e = b->succ; e; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR)
continue;
insn = first_insn_after_basic_block_note (e->dest);
while (PHI_NODE_P (insn))
{
rtx phi = PATTERN (insn);
rtx reg;
reg = SET_DEST (phi);
if (REGNO (reg) >= ssa_max_reg_num)
reg = ssa_rename_from_lookup (REGNO (reg));
if (reg == NULL_RTX)
abort ();
reg = ssa_rename_to_lookup (reg);
if (reg == NULL || reg == RENAME_NO_RTX)
{
if (! remove_phi_alternative (phi, b))
abort ();
}
else
{
if (GET_MODE (SET_DEST (phi)) == VOIDmode)
PUT_MODE (SET_DEST (phi), GET_MODE (reg));
else if (GET_MODE (SET_DEST (phi)) != GET_MODE (reg))
abort ();
*phi_alternative (phi, bb) = reg;
}
insn = NEXT_INSN (insn);
}
}
FOR_EACH_BB (c)
if (get_immediate_dominator (idom, c)->index == bb)
rename_block (c->index, idom);
while (set_data)
{
struct rename_set_data *next;
rtx old_reg = *set_data->reg_loc;
if (*set_data->reg_loc != set_data->old_reg)
abort ();
*set_data->reg_loc = set_data->new_reg;
ssa_rename_to_insert (old_reg, set_data->prev_reg);
next = set_data->next;
free (set_data);
set_data = next;
}
}
static void
rename_registers (nregs, idom)
int nregs;
dominance_info idom;
{
VARRAY_RTX_INIT (ssa_definition, nregs * 3, "ssa_definition");
ssa_rename_from_initialize ();
ssa_rename_to_pseudo = (rtx *) alloca (nregs * sizeof(rtx));
memset ((char *) ssa_rename_to_pseudo, 0, nregs * sizeof(rtx));
memset ((char *) ssa_rename_to_hard, 0,
FIRST_PSEUDO_REGISTER * NUM_MACHINE_MODES * sizeof (rtx));
rename_block (0, idom);
ssa_rename_to_pseudo = NULL;
}
void
convert_to_ssa ()
{
sbitmap *evals;
sbitmap *dfs;
sbitmap *idfs;
dominance_info idom;
int nregs;
basic_block bb;
if (in_ssa_form)
abort ();
life_analysis (get_insns (), NULL, 0);
idom = calculate_dominance_info (CDI_DOMINATORS);
if (rtl_dump_file)
{
fputs (";; Immediate Dominators:\n", rtl_dump_file);
FOR_EACH_BB (bb)
fprintf (rtl_dump_file, ";\t%3d = %3d\n", bb->index,
get_immediate_dominator (idom, bb)->index);
fflush (rtl_dump_file);
}
dfs = sbitmap_vector_alloc (last_basic_block, last_basic_block);
compute_dominance_frontiers (dfs, idom);
if (rtl_dump_file)
{
dump_sbitmap_vector (rtl_dump_file, ";; Dominance Frontiers:",
"; Basic Block", dfs, last_basic_block);
fflush (rtl_dump_file);
}
ssa_max_reg_num = max_reg_num ();
nregs = ssa_max_reg_num;
evals = sbitmap_vector_alloc (nregs, last_basic_block);
find_evaluations (evals, nregs);
idfs = sbitmap_vector_alloc (nregs, last_basic_block);
compute_iterated_dominance_frontiers (idfs, dfs, evals, nregs);
if (rtl_dump_file)
{
dump_sbitmap_vector (rtl_dump_file, ";; Iterated Dominance Frontiers:",
"; Register", idfs, nregs);
fflush (rtl_dump_file);
}
insert_phi_nodes (idfs, evals, nregs);
rename_registers (nregs, idom);
sbitmap_vector_free (dfs);
sbitmap_vector_free (evals);
sbitmap_vector_free (idfs);
in_ssa_form = 1;
reg_scan (get_insns (), max_reg_num (), 1);
free_dominance_info (idom);
}
static inline int
ephi_add_node (reg, nodes, n_nodes)
rtx reg, *nodes;
int *n_nodes;
{
int i;
for (i = *n_nodes - 1; i >= 0; --i)
if (REGNO (reg) == REGNO (nodes[i]))
return i;
nodes[i = (*n_nodes)++] = reg;
return i;
}
static int *
ephi_forward (t, visited, succ, tstack)
int t;
sbitmap visited;
sbitmap *succ;
int *tstack;
{
int s;
SET_BIT (visited, t);
EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s,
{
if (! TEST_BIT (visited, s))
tstack = ephi_forward (s, visited, succ, tstack);
});
*tstack++ = t;
return tstack;
}
static void
ephi_backward (t, visited, pred, nodes)
int t;
sbitmap visited, *pred;
rtx *nodes;
{
int p;
SET_BIT (visited, t);
EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
{
if (! TEST_BIT (visited, p))
{
ephi_backward (p, visited, pred, nodes);
emit_move_insn (nodes[p], nodes[t]);
}
});
}
static void
ephi_create (t, visited, pred, succ, nodes)
int t;
sbitmap visited, *pred, *succ;
rtx *nodes;
{
rtx reg_u = NULL_RTX;
int unvisited_predecessors = 0;
int p;
EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
{
if (! TEST_BIT (visited, p))
unvisited_predecessors = 1;
else if (!reg_u)
reg_u = nodes[p];
});
if (unvisited_predecessors)
{
if (!reg_u)
{
reg_u = gen_reg_rtx (GET_MODE (nodes[t]));
emit_move_insn (reg_u, nodes[t]);
}
EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
{
if (! TEST_BIT (visited, p))
{
ephi_backward (p, visited, pred, nodes);
emit_move_insn (nodes[p], reg_u);
}
});
}
else
{
int s;
EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s,
{
SET_BIT (visited, t);
emit_move_insn (nodes[t], nodes[s]);
return;
});
}
}
static void
eliminate_phi (e, reg_partition)
edge e;
partition reg_partition;
{
int n_nodes;
sbitmap *pred, *succ;
sbitmap visited;
rtx *nodes;
int *stack, *tstack;
rtx insn;
int i;
insn = first_insn_after_basic_block_note (e->dest);
n_nodes = 0;
while (PHI_NODE_P (insn))
{
insn = next_nonnote_insn (insn);
n_nodes += 2;
}
if (n_nodes == 0)
return;
nodes = (rtx *) alloca (n_nodes * sizeof(rtx));
pred = sbitmap_vector_alloc (n_nodes, n_nodes);
succ = sbitmap_vector_alloc (n_nodes, n_nodes);
sbitmap_vector_zero (pred, n_nodes);
sbitmap_vector_zero (succ, n_nodes);
insn = first_insn_after_basic_block_note (e->dest);
n_nodes = 0;
for (; PHI_NODE_P (insn); insn = next_nonnote_insn (insn))
{
rtx* preg = phi_alternative (PATTERN (insn), e->src->index);
rtx tgt = SET_DEST (PATTERN (insn));
rtx reg;
if (preg == NULL)
continue;
reg = *preg;
if (GET_CODE (reg) != REG || GET_CODE (tgt) != REG)
abort ();
reg = regno_reg_rtx[partition_find (reg_partition, REGNO (reg))];
tgt = regno_reg_rtx[partition_find (reg_partition, REGNO (tgt))];
if (reg != tgt)
{
int ireg, itgt;
ireg = ephi_add_node (reg, nodes, &n_nodes);
itgt = ephi_add_node (tgt, nodes, &n_nodes);
SET_BIT (pred[ireg], itgt);
SET_BIT (succ[itgt], ireg);
}
}
if (n_nodes == 0)
goto out;
visited = sbitmap_alloc (n_nodes);
sbitmap_zero (visited);
tstack = stack = (int *) alloca (n_nodes * sizeof (int));
for (i = 0; i < n_nodes; ++i)
if (! TEST_BIT (visited, i))
tstack = ephi_forward (i, visited, succ, tstack);
sbitmap_zero (visited);
start_sequence ();
while (tstack != stack)
{
i = *--tstack;
if (! TEST_BIT (visited, i))
ephi_create (i, visited, pred, succ, nodes);
}
insn = get_insns ();
end_sequence ();
insert_insn_on_edge (insn, e);
if (rtl_dump_file)
fprintf (rtl_dump_file, "Emitting copy on edge (%d,%d)\n",
e->src->index, e->dest->index);
sbitmap_free (visited);
out:
sbitmap_vector_free (pred);
sbitmap_vector_free (succ);
}
static int
make_regs_equivalent_over_bad_edges (bb, reg_partition)
int bb;
partition reg_partition;
{
int changed = 0;
basic_block b = BASIC_BLOCK (bb);
rtx phi;
phi = first_insn_after_basic_block_note (b);
for (;
PHI_NODE_P (phi);
phi = next_nonnote_insn (phi))
{
edge e;
int tgt_regno;
rtx set = PATTERN (phi);
rtx tgt = SET_DEST (set);
if (GET_CODE (tgt) != REG
|| !CONVERT_REGISTER_TO_SSA_P (REGNO (tgt)))
abort ();
tgt_regno = REGNO (tgt);
for (e = b->pred; e; e = e->pred_next)
if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
{
rtx *alt = phi_alternative (set, e->src->index);
int alt_regno;
if (alt == 0)
continue;
if (GET_CODE (*alt) != REG
|| !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt)))
abort ();
alt_regno = REGNO (*alt);
if (partition_find (reg_partition, tgt_regno)
!= partition_find (reg_partition, alt_regno))
{
if (conflicting_hard_regs_p (tgt_regno, alt_regno))
abort ();
partition_union (reg_partition,
tgt_regno, alt_regno);
++changed;
}
}
}
return changed;
}
static int
make_equivalent_phi_alternatives_equivalent (bb, reg_partition)
int bb;
partition reg_partition;
{
int changed = 0;
basic_block b = BASIC_BLOCK (bb);
rtx phi;
phi = first_insn_after_basic_block_note (b);
for (;
PHI_NODE_P (phi);
phi = next_nonnote_insn (phi))
{
rtx set = PATTERN (phi);
int tgt_regno = REGNO (SET_DEST (PATTERN (phi)));
rtx phi2 = next_nonnote_insn (phi);
for (;
PHI_NODE_P (phi2);
phi2 = next_nonnote_insn (phi2))
{
rtx set2 = PATTERN (phi2);
int tgt2_regno = REGNO (SET_DEST (set2));
if (partition_find (reg_partition, tgt_regno) ==
partition_find (reg_partition, tgt2_regno))
{
edge e;
for (e = b->pred; e; e = e->pred_next)
{
int pred_block = e->src->index;
rtx *alt = phi_alternative (set, pred_block);
rtx *alt2 = phi_alternative (set2, pred_block);
if (alt == 0 || alt2 == 0)
continue;
if (GET_CODE (*alt) != REG
|| !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt)))
abort ();
if (GET_CODE (*alt2) != REG
|| !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt2)))
abort ();
if (partition_find (reg_partition, REGNO (*alt))
!= partition_find (reg_partition, REGNO (*alt2)))
{
if (conflicting_hard_regs_p (REGNO (*alt), REGNO (*alt2)))
abort ();
partition_union (reg_partition,
REGNO (*alt), REGNO (*alt2));
++changed;
}
}
}
}
}
return changed;
}
static partition
compute_conservative_reg_partition ()
{
basic_block bb;
int changed = 0;
partition p =
partition_new (ssa_definition->num_elements);
FOR_EACH_BB_REVERSE (bb)
changed += make_regs_equivalent_over_bad_edges (bb->index, p);
while (changed > 0)
{
changed = 0;
FOR_EACH_BB_REVERSE (bb)
changed += make_equivalent_phi_alternatives_equivalent (bb->index, p);
}
return p;
}
static int
coalesce_if_unconflicting (p, conflicts, reg1, reg2)
partition p;
conflict_graph conflicts;
int reg1;
int reg2;
{
int reg;
if (!CONVERT_REGISTER_TO_SSA_P (reg1) || !CONVERT_REGISTER_TO_SSA_P (reg2))
return 0;
reg1 = partition_find (p, reg1);
reg2 = partition_find (p, reg2);
if (reg1 == reg2)
return 0;
if (conflicting_hard_regs_p (reg1, reg2) ||
conflict_graph_conflict_p (conflicts, reg1, reg2))
return 0;
partition_union (p, reg1, reg2);
reg = partition_find (p, reg1);
conflict_graph_merge_regs (conflicts, reg, reg1);
conflict_graph_merge_regs (conflicts, reg, reg2);
return 1;
}
static int
coalesce_regs_in_copies (bb, p, conflicts)
basic_block bb;
partition p;
conflict_graph conflicts;
{
int changed = 0;
rtx insn;
rtx end = bb->end;
for (insn = bb->head; insn != end; insn = NEXT_INSN (insn))
{
rtx pattern;
rtx src;
rtx dest;
if (GET_CODE (insn) != INSN)
continue;
pattern = PATTERN (insn);
if (GET_CODE (pattern) != SET)
continue;
src = SET_SRC (pattern);
dest = SET_DEST (pattern);
if (GET_CODE (src) != REG || GET_CODE (dest) != REG)
continue;
if (GET_MODE (src) != GET_MODE (dest))
continue;
changed += coalesce_if_unconflicting (p, conflicts,
REGNO (src), REGNO (dest));
}
return changed;
}
struct phi_coalesce_context
{
partition p;
conflict_graph conflicts;
int changed;
};
static int
coalesce_reg_in_phi (insn, dest_regno, src_regno, data)
rtx insn ATTRIBUTE_UNUSED;
int dest_regno;
int src_regno;
void *data;
{
struct phi_coalesce_context *context =
(struct phi_coalesce_context *) data;
context->changed
+= coalesce_if_unconflicting (context->p, context->conflicts,
dest_regno, src_regno);
return 0;
}
static int
coalesce_regs_in_successor_phi_nodes (bb, p, conflicts)
basic_block bb;
partition p;
conflict_graph conflicts;
{
struct phi_coalesce_context context;
context.p = p;
context.conflicts = conflicts;
context.changed = 0;
for_each_successor_phi (bb, &coalesce_reg_in_phi, &context);
return context.changed;
}
static partition
compute_coalesced_reg_partition ()
{
basic_block bb;
int changed = 0;
regset_head phi_set_head;
regset phi_set = &phi_set_head;
partition p =
partition_new (ssa_definition->num_elements);
FOR_EACH_BB_REVERSE (bb)
make_regs_equivalent_over_bad_edges (bb->index, p);
INIT_REG_SET (phi_set);
do
{
conflict_graph conflicts;
changed = 0;
CLEAR_REG_SET (phi_set);
mark_phi_and_copy_regs (phi_set);
conflicts = conflict_graph_compute (phi_set, p);
FOR_EACH_BB_REVERSE (bb)
{
changed += coalesce_regs_in_copies (bb, p, conflicts);
changed +=
coalesce_regs_in_successor_phi_nodes (bb, p, conflicts);
}
conflict_graph_delete (conflicts);
}
while (changed > 0);
FREE_REG_SET (phi_set);
return p;
}
static int
mark_reg_in_phi (ptr, data)
rtx *ptr;
void *data;
{
rtx expr = *ptr;
regset set = (regset) data;
switch (GET_CODE (expr))
{
case REG:
SET_REGNO_REG_SET (set, REGNO (expr));
case CONST_INT:
case PHI:
return 0;
default:
abort ();
}
}
static void
mark_phi_and_copy_regs (phi_set)
regset phi_set;
{
unsigned int reg;
for (reg = 0; reg < VARRAY_SIZE (ssa_definition); ++reg)
if (CONVERT_REGISTER_TO_SSA_P (reg))
{
rtx insn = VARRAY_RTX (ssa_definition, reg);
rtx pattern;
rtx src;
if (insn == NULL
|| (GET_CODE (insn) == NOTE
&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED))
continue;
pattern = PATTERN (insn);
if (GET_CODE (pattern) != SET)
continue;
src = SET_SRC (pattern);
if (GET_CODE (src) == REG)
{
SET_REGNO_REG_SET (phi_set, reg);
SET_REGNO_REG_SET (phi_set, REGNO (src));
}
else if (GET_CODE (src) == PHI)
{
SET_REGNO_REG_SET (phi_set, reg);
for_each_rtx (&src, mark_reg_in_phi, phi_set);
}
}
}
static int
rename_equivalent_regs_in_insn (ptr, data)
rtx *ptr;
void* data;
{
rtx x = *ptr;
partition reg_partition = (partition) data;
if (x == NULL_RTX)
return 0;
switch (GET_CODE (x))
{
case REG:
if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)))
{
unsigned int regno = REGNO (x);
unsigned int new_regno = partition_find (reg_partition, regno);
rtx canonical_element_rtx = ssa_rename_from_lookup (new_regno);
if (canonical_element_rtx != NULL_RTX &&
HARD_REGISTER_P (canonical_element_rtx))
{
if (REGNO (canonical_element_rtx) != regno)
*ptr = canonical_element_rtx;
}
else if (regno != new_regno)
{
rtx new_reg = regno_reg_rtx[new_regno];
if (GET_MODE (x) != GET_MODE (new_reg))
abort ();
*ptr = new_reg;
}
}
return -1;
case PHI:
return -1;
default:
return 0;
}
}
static int
record_canonical_element_1 (srfp, data)
void **srfp;
void *data;
{
unsigned int reg = ((ssa_rename_from_pair *) *srfp)->reg;
sbitmap canonical_elements =
((struct ssa_rename_from_hash_table_data *) data)->canonical_elements;
partition reg_partition =
((struct ssa_rename_from_hash_table_data *) data)->reg_partition;
SET_BIT (canonical_elements, partition_find (reg_partition, reg));
return 1;
}
static int
check_hard_regs_in_partition (reg_partition)
partition reg_partition;
{
sbitmap canonical_elements;
int element_index;
int already_seen[FIRST_PSEUDO_REGISTER][NUM_MACHINE_MODES];
int reg;
int mach_mode;
canonical_elements = sbitmap_alloc (max_reg_num ());
sbitmap_zero (canonical_elements);
ssa_rename_from_traverse (&record_canonical_element_1,
canonical_elements, reg_partition);
for (reg = 0; reg < FIRST_PSEUDO_REGISTER; ++reg)
for (mach_mode = 0; mach_mode < NUM_MACHINE_MODES; ++mach_mode)
already_seen[reg][mach_mode] = 0;
EXECUTE_IF_SET_IN_SBITMAP (canonical_elements, 0, element_index,
{
rtx hard_reg_rtx = ssa_rename_from_lookup (element_index);
if (hard_reg_rtx != NULL_RTX &&
HARD_REGISTER_P (hard_reg_rtx) &&
already_seen[REGNO (hard_reg_rtx)][GET_MODE (hard_reg_rtx)] != 0)
return 0;
});
sbitmap_free (canonical_elements);
return 1;
}
static void
rename_equivalent_regs (reg_partition)
partition reg_partition;
{
basic_block b;
FOR_EACH_BB_REVERSE (b)
{
rtx next = b->head;
rtx last = b->end;
rtx insn;
do
{
insn = next;
if (INSN_P (insn))
{
for_each_rtx (&PATTERN (insn),
rename_equivalent_regs_in_insn,
reg_partition);
for_each_rtx (®_NOTES (insn),
rename_equivalent_regs_in_insn,
reg_partition);
if (GET_CODE (PATTERN (insn)) == SEQUENCE)
{
rtx s = PATTERN (insn);
int slen = XVECLEN (s, 0);
int i;
if (slen <= 1)
abort ();
PATTERN (insn) = XVECEXP (s, 0, slen-1);
for (i = 0; i < slen - 1; i++)
emit_insn_before (XVECEXP (s, 0, i), insn);
}
}
next = NEXT_INSN (insn);
}
while (insn != last);
}
}
void
convert_from_ssa ()
{
basic_block b, bb;
partition reg_partition;
rtx insns = get_insns ();
life_analysis (insns, NULL, PROP_DEATH_NOTES);
if (conservative_reg_partition)
reg_partition = compute_conservative_reg_partition ();
else
reg_partition = compute_coalesced_reg_partition ();
if (!check_hard_regs_in_partition (reg_partition))
abort ();
rename_equivalent_regs (reg_partition);
FOR_EACH_BB_REVERSE (b)
{
edge e;
for (e = b->pred; e; e = e->pred_next)
if (e->src != ENTRY_BLOCK_PTR)
eliminate_phi (e, reg_partition);
}
partition_delete (reg_partition);
FOR_EACH_BB_REVERSE (bb)
{
rtx insn = bb->head;
while (1)
{
if (PHI_NODE_P (insn))
{
if (insn == bb->end)
bb->end = PREV_INSN (insn);
insn = delete_insn (insn);
}
else if (INSN_P (insn))
break;
else if (insn == bb->end)
break;
else
insn = NEXT_INSN (insn);
}
}
commit_edge_insertions ();
in_ssa_form = 0;
count_or_remove_death_notes (NULL, 1);
ssa_definition = 0;
ssa_rename_from_free ();
}
int
for_each_successor_phi (bb, fn, data)
basic_block bb;
successor_phi_fn fn;
void *data;
{
edge e;
if (bb == EXIT_BLOCK_PTR)
return 0;
for (e = bb->succ; e != NULL; e = e->succ_next)
{
rtx insn;
basic_block successor = e->dest;
if (successor == ENTRY_BLOCK_PTR
|| successor == EXIT_BLOCK_PTR)
continue;
insn = first_insn_after_basic_block_note (successor);
if (insn == NULL)
continue;
for ( ; PHI_NODE_P (insn); insn = NEXT_INSN (insn))
{
int result;
rtx phi_set = PATTERN (insn);
rtx *alternative = phi_alternative (phi_set, bb->index);
rtx phi_src;
if (alternative == NULL)
continue;
phi_src = *alternative;
result = (*fn) (insn, REGNO (SET_DEST (phi_set)),
REGNO (phi_src), data);
if (result != 0)
return result;
}
}
return 0;
}
static int
conflicting_hard_regs_p (reg1, reg2)
int reg1;
int reg2;
{
int orig_reg1 = original_register (reg1);
int orig_reg2 = original_register (reg2);
if (HARD_REGISTER_NUM_P (orig_reg1) && HARD_REGISTER_NUM_P (orig_reg2)
&& orig_reg1 != orig_reg2)
return 1;
if (HARD_REGISTER_NUM_P (orig_reg1) && !HARD_REGISTER_NUM_P (orig_reg2))
return 1;
if (!HARD_REGISTER_NUM_P (orig_reg1) && HARD_REGISTER_NUM_P (orig_reg2))
return 1;
return 0;
}