#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "flags.h"
#include "basic-block.h"
#include "function.h"
#include "diagnostic.h"
#include "bitmap.h"
#include "tree-flow.h"
#include "tree-gimple.h"
#include "tree-inline.h"
#include "varray.h"
#include "timevar.h"
#include "hashtab.h"
#include "tree-dump.h"
#include "tree-ssa-live.h"
#include "errors.h"
static void live_worklist (tree_live_info_p, varray_type, int);
static tree_live_info_p new_tree_live_info (var_map);
static inline void set_if_valid (var_map, bitmap, tree);
static inline void add_livein_if_notdef (tree_live_info_p, bitmap,
tree, basic_block);
static inline void register_ssa_partition (var_map, tree, bool);
static inline void add_conflicts_if_valid (tpa_p, conflict_graph,
var_map, bitmap, tree);
static partition_pair_p find_partition_pair (coalesce_list_p, int, int, bool);
var_map
init_var_map (int size)
{
var_map map;
map = (var_map) xmalloc (sizeof (struct _var_map));
map->var_partition = partition_new (size);
map->partition_to_var
= (tree *)xmalloc (size * sizeof (tree));
memset (map->partition_to_var, 0, size * sizeof (tree));
map->partition_to_compact = NULL;
map->compact_to_partition = NULL;
map->num_partitions = size;
map->partition_size = size;
map->ref_count = NULL;
return map;
}
void
delete_var_map (var_map map)
{
free (map->partition_to_var);
partition_delete (map->var_partition);
if (map->partition_to_compact)
free (map->partition_to_compact);
if (map->compact_to_partition)
free (map->compact_to_partition);
if (map->ref_count)
free (map->ref_count);
free (map);
}
int
var_union (var_map map, tree var1, tree var2)
{
int p1, p2, p3;
tree root_var = NULL_TREE;
tree other_var = NULL_TREE;
if (TREE_CODE (var1) == SSA_NAME)
p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
else
{
p1 = var_to_partition (map, var1);
if (map->compact_to_partition)
p1 = map->compact_to_partition[p1];
root_var = var1;
}
if (TREE_CODE (var2) == SSA_NAME)
p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
else
{
p2 = var_to_partition (map, var2);
if (map->compact_to_partition)
p2 = map->compact_to_partition[p2];
if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var)))
{
other_var = root_var;
root_var = var2;
}
else
other_var = var2;
}
gcc_assert (p1 != NO_PARTITION);
gcc_assert (p2 != NO_PARTITION);
if (p1 == p2)
p3 = p1;
else
p3 = partition_union (map->var_partition, p1, p2);
if (map->partition_to_compact)
p3 = map->partition_to_compact[p3];
if (root_var)
change_partition_var (map, root_var, p3);
if (other_var)
change_partition_var (map, other_var, p3);
return p3;
}
void
compact_var_map (var_map map, int flags)
{
sbitmap used;
int x, limit, count, tmp, root, root_i;
tree var;
root_var_p rv = NULL;
limit = map->partition_size;
used = sbitmap_alloc (limit);
sbitmap_zero (used);
if (map->partition_to_compact)
{
free (map->partition_to_compact);
map->partition_to_compact = NULL;
}
if (map->compact_to_partition)
{
free (map->compact_to_partition);
map->compact_to_partition = NULL;
}
map->num_partitions = map->partition_size;
if (flags & VARMAP_NO_SINGLE_DEFS)
rv = root_var_init (map);
map->partition_to_compact = (int *)xmalloc (limit * sizeof (int));
memset (map->partition_to_compact, 0xff, (limit * sizeof (int)));
count = 0;
for (x = 0; x < limit; x++)
{
tmp = partition_find (map->var_partition, x);
if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE)
{
if (rv)
{
root = root_var_find (rv, tmp);
root_i = root_var_first_partition (rv, root);
if (root_var_next_partition (rv, root_i) == ROOT_VAR_NONE)
continue;
}
SET_BIT (used, tmp);
count++;
}
}
if (count != limit)
{
map->compact_to_partition = (int *)xmalloc (count * sizeof (int));
count = 0;
EXECUTE_IF_SET_IN_SBITMAP (used, 1, x,
{
map->partition_to_compact[x] = count;
map->compact_to_partition[count] = x;
var = map->partition_to_var[x];
if (TREE_CODE (var) != SSA_NAME)
change_partition_var (map, var, count);
count++;
});
}
else
{
free (map->partition_to_compact);
map->partition_to_compact = NULL;
}
map->num_partitions = count;
if (rv)
root_var_delete (rv);
sbitmap_free (used);
}
void
change_partition_var (var_map map, tree var, int part)
{
var_ann_t ann;
gcc_assert (TREE_CODE (var) != SSA_NAME);
ann = var_ann (var);
ann->out_of_ssa_tag = 1;
VAR_ANN_PARTITION (ann) = part;
if (map->compact_to_partition)
map->partition_to_var[map->compact_to_partition[part]] = var;
}
static tree
mark_all_vars_used_1 (tree *tp, int *walk_subtrees,
void *data ATTRIBUTE_UNUSED)
{
tree t = *tp;
if (TREE_CODE (t) == VAR_DECL)
set_is_used (t);
if (IS_TYPE_OR_DECL_P (t))
*walk_subtrees = 0;
return NULL;
}
static inline void
mark_all_vars_used (tree *expr_p)
{
walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
}
var_map
create_ssa_var_map (int flags)
{
block_stmt_iterator bsi;
basic_block bb;
tree dest, use;
tree stmt;
stmt_ann_t ann;
var_map map;
ssa_op_iter iter;
#ifdef ENABLE_CHECKING
sbitmap used_in_real_ops;
sbitmap used_in_virtual_ops;
#endif
map = init_var_map (num_ssa_names + 1);
#ifdef ENABLE_CHECKING
used_in_real_ops = sbitmap_alloc (num_referenced_vars);
sbitmap_zero (used_in_real_ops);
used_in_virtual_ops = sbitmap_alloc (num_referenced_vars);
sbitmap_zero (used_in_virtual_ops);
#endif
if (flags & SSA_VAR_MAP_REF_COUNT)
{
map->ref_count
= (int *)xmalloc (((num_ssa_names + 1) * sizeof (int)));
memset (map->ref_count, 0, (num_ssa_names + 1) * sizeof (int));
}
FOR_EACH_BB (bb)
{
tree phi, arg;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
int i;
register_ssa_partition (map, PHI_RESULT (phi), false);
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
arg = PHI_ARG_DEF (phi, i);
if (TREE_CODE (arg) == SSA_NAME)
register_ssa_partition (map, arg, true);
mark_all_vars_used (&PHI_ARG_DEF_TREE (phi, i));
}
}
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
stmt = bsi_stmt (bsi);
get_stmt_operands (stmt);
ann = stmt_ann (stmt);
FOR_EACH_SSA_TREE_OPERAND (use , stmt, iter, SSA_OP_USE)
{
register_ssa_partition (map, use, true);
#ifdef ENABLE_CHECKING
SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (use))->uid);
#endif
}
FOR_EACH_SSA_TREE_OPERAND (dest, stmt, iter, SSA_OP_DEF)
{
register_ssa_partition (map, dest, false);
#ifdef ENABLE_CHECKING
SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (dest))->uid);
#endif
}
#ifdef ENABLE_CHECKING
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter,
SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF)
{
SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (use))->uid);
}
#endif
mark_all_vars_used (bsi_stmt_ptr (bsi));
}
}
#if defined ENABLE_CHECKING
{
unsigned i;
sbitmap both = sbitmap_alloc (num_referenced_vars);
sbitmap_a_and_b (both, used_in_real_ops, used_in_virtual_ops);
if (sbitmap_first_set_bit (both) >= 0)
{
EXECUTE_IF_SET_IN_SBITMAP (both, 0, i,
fprintf (stderr, "Variable %s used in real and virtual operands\n",
get_name (referenced_var (i))));
internal_error ("SSA corruption");
}
sbitmap_free (used_in_real_ops);
sbitmap_free (used_in_virtual_ops);
sbitmap_free (both);
}
#endif
return map;
}
static tree_live_info_p
new_tree_live_info (var_map map)
{
tree_live_info_p live;
unsigned x;
live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
live->map = map;
live->num_blocks = last_basic_block;
live->global = BITMAP_ALLOC (NULL);
live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap));
for (x = 0; x < num_var_partitions (map); x++)
live->livein[x] = BITMAP_ALLOC (NULL);
live->liveout = NULL;
return live;
}
void
delete_tree_live_info (tree_live_info_p live)
{
int x;
if (live->liveout)
{
for (x = live->num_blocks - 1; x >= 0; x--)
BITMAP_FREE (live->liveout[x]);
free (live->liveout);
}
if (live->livein)
{
for (x = num_var_partitions (live->map) - 1; x >= 0; x--)
BITMAP_FREE (live->livein[x]);
free (live->livein);
}
if (live->global)
BITMAP_FREE (live->global);
free (live);
}
static void
live_worklist (tree_live_info_p live, varray_type stack, int i)
{
unsigned b;
tree var;
basic_block def_bb = NULL;
edge e;
var_map map = live->map;
edge_iterator ei;
bitmap_iterator bi;
var = partition_to_var (map, i);
if (SSA_NAME_DEF_STMT (var))
def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi)
{
VARRAY_PUSH_INT (stack, b);
}
while (VARRAY_ACTIVE_SIZE (stack) > 0)
{
b = VARRAY_TOP_INT (stack);
VARRAY_POP (stack);
FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
if (e->src != ENTRY_BLOCK_PTR)
{
if (e->src == def_bb)
continue;
if (!bitmap_bit_p (live->livein[i], e->src->index))
{
bitmap_set_bit (live->livein[i], e->src->index);
VARRAY_PUSH_INT (stack, e->src->index);
}
}
}
}
static inline void
set_if_valid (var_map map, bitmap vec, tree var)
{
int p = var_to_partition (map, var);
if (p != NO_PARTITION)
bitmap_set_bit (vec, p);
}
static inline void
add_livein_if_notdef (tree_live_info_p live, bitmap def_vec,
tree var, basic_block bb)
{
int p = var_to_partition (live->map, var);
if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR)
return;
if (!bitmap_bit_p (def_vec, p))
{
bitmap_set_bit (live->livein[p], bb->index);
bitmap_set_bit (live->global, p);
}
}
tree_live_info_p
calculate_live_on_entry (var_map map)
{
tree_live_info_p live;
unsigned i;
basic_block bb;
bitmap saw_def;
tree phi, var, stmt;
tree op;
edge e;
varray_type stack;
block_stmt_iterator bsi;
stmt_ann_t ann;
ssa_op_iter iter;
bitmap_iterator bi;
#ifdef ENABLE_CHECKING
int num;
edge_iterator ei;
#endif
saw_def = BITMAP_ALLOC (NULL);
live = new_tree_live_info (map);
FOR_EACH_BB (bb)
{
bitmap_clear (saw_def);
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
{
var = PHI_ARG_DEF (phi, i);
if (!phi_ssa_name_p (var))
continue;
stmt = SSA_NAME_DEF_STMT (var);
e = EDGE_PRED (bb, i);
if (!stmt || e->src != bb_for_stmt (stmt))
add_livein_if_notdef (live, saw_def, var, e->src);
}
}
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
var = PHI_RESULT (phi);
set_if_valid (map, saw_def, var);
}
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
stmt = bsi_stmt (bsi);
get_stmt_operands (stmt);
ann = stmt_ann (stmt);
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
{
add_livein_if_notdef (live, saw_def, op, bb);
}
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
{
set_if_valid (map, saw_def, op);
}
}
}
VARRAY_INT_INIT (stack, last_basic_block, "stack");
EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi)
{
live_worklist (live, stack, i);
}
#ifdef ENABLE_CHECKING
bb = ENTRY_BLOCK_PTR;
num = 0;
FOR_EACH_EDGE (e, ei, bb->succs)
{
int entry_block = e->dest->index;
if (e->dest == EXIT_BLOCK_PTR)
continue;
for (i = 0; i < (unsigned)num_var_partitions (map); i++)
{
basic_block tmp;
tree d;
var = partition_to_var (map, i);
stmt = SSA_NAME_DEF_STMT (var);
tmp = bb_for_stmt (stmt);
d = default_def (SSA_NAME_VAR (var));
if (bitmap_bit_p (live_entry_blocks (live, i), entry_block))
{
if (!IS_EMPTY_STMT (stmt))
{
num++;
print_generic_expr (stderr, var, TDF_SLIM);
fprintf (stderr, " is defined ");
if (tmp)
fprintf (stderr, " in BB%d, ", tmp->index);
fprintf (stderr, "by:\n");
print_generic_expr (stderr, stmt, TDF_SLIM);
fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
entry_block);
fprintf (stderr, " So it appears to have multiple defs.\n");
}
else
{
if (d != var)
{
num++;
print_generic_expr (stderr, var, TDF_SLIM);
fprintf (stderr, " is live-on-entry to BB%d ",entry_block);
if (d)
{
fprintf (stderr, " but is not the default def of ");
print_generic_expr (stderr, d, TDF_SLIM);
fprintf (stderr, "\n");
}
else
fprintf (stderr, " and there is no default def.\n");
}
}
}
else
if (d == var)
{
int z, ok = 0;
for (phi = phi_nodes (e->dest);
phi && !ok;
phi = PHI_CHAIN (phi))
{
for (z = 0; z < PHI_NUM_ARGS (phi); z++)
if (var == PHI_ARG_DEF (phi, z))
{
ok = 1;
break;
}
}
if (ok)
continue;
num++;
print_generic_expr (stderr, var, TDF_SLIM);
fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
entry_block);
fprintf (stderr, "but it is a default def so it should be.\n");
}
}
}
gcc_assert (num <= 0);
#endif
BITMAP_FREE (saw_def);
return live;
}
void
calculate_live_on_exit (tree_live_info_p liveinfo)
{
unsigned b;
unsigned i, x;
bitmap *on_exit;
basic_block bb;
edge e;
tree t, phi;
bitmap on_entry;
var_map map = liveinfo->map;
on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
for (x = 0; x < (unsigned)last_basic_block; x++)
on_exit[x] = BITMAP_ALLOC (NULL);
FOR_EACH_BB (bb)
{
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
{
t = PHI_ARG_DEF (phi, i);
e = PHI_ARG_EDGE (phi, i);
if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR)
continue;
set_if_valid (map, on_exit[e->src->index], t);
}
}
for (i = 0; i < num_var_partitions (map); i++)
{
bitmap_iterator bi;
on_entry = live_entry_blocks (liveinfo, i);
EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi)
{
edge_iterator ei;
FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
if (e->src != ENTRY_BLOCK_PTR)
bitmap_set_bit (on_exit[e->src->index], i);
}
}
liveinfo->liveout = on_exit;
}
static tpa_p
tpa_init (var_map map)
{
tpa_p tpa;
int num_partitions = num_var_partitions (map);
int x;
if (num_partitions == 0)
return NULL;
tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d));
tpa->num_trees = 0;
tpa->uncompressed_num = -1;
tpa->map = map;
tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int));
memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int));
tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int));
memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int));
x = MAX (40, (num_partitions / 20));
VARRAY_TREE_INIT (tpa->trees, x, "trees");
VARRAY_INT_INIT (tpa->first_partition, x, "first_partition");
return tpa;
}
void
tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index)
{
int i;
i = tpa_first_partition (tpa, tree_index);
if (i == partition_index)
{
VARRAY_INT (tpa->first_partition, tree_index) = tpa->next_partition[i];
}
else
{
for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i))
{
if (tpa->next_partition[i] == partition_index)
{
tpa->next_partition[i] = tpa->next_partition[partition_index];
break;
}
}
}
}
void
tpa_delete (tpa_p tpa)
{
if (!tpa)
return;
free (tpa->partition_to_tree_map);
free (tpa->next_partition);
free (tpa);
}
int
tpa_compact (tpa_p tpa)
{
int last, x, y, first, swap_i;
tree swap_t;
for (last = tpa->num_trees - 1; last > 0; last--)
{
first = tpa_first_partition (tpa, last);
if (tpa_next_partition (tpa, first) != NO_PARTITION)
break;
}
x = 0;
while (x < last)
{
first = tpa_first_partition (tpa, x);
if (tpa_next_partition (tpa, first) == NO_PARTITION)
{
swap_t = VARRAY_TREE (tpa->trees, last);
swap_i = VARRAY_INT (tpa->first_partition, last);
VARRAY_TREE (tpa->trees, last) = VARRAY_TREE (tpa->trees, x);
VARRAY_INT (tpa->first_partition, last)
= VARRAY_INT (tpa->first_partition, x);
tpa->partition_to_tree_map[tpa_first_partition (tpa, last)] = last;
VARRAY_TREE (tpa->trees, x) = swap_t;
VARRAY_INT (tpa->first_partition, x) = swap_i;
for (y = tpa_first_partition (tpa, x);
y != NO_PARTITION;
y = tpa_next_partition (tpa, y))
tpa->partition_to_tree_map[y] = x;
last--;
for (; last > x; last--)
{
first = tpa_first_partition (tpa, last);
if (tpa_next_partition (tpa, first) != NO_PARTITION)
break;
}
}
x++;
}
first = tpa_first_partition (tpa, x);
if (tpa_next_partition (tpa, first) != NO_PARTITION)
x++;
tpa->uncompressed_num = tpa->num_trees;
tpa->num_trees = x;
return last;
}
root_var_p
root_var_init (var_map map)
{
root_var_p rv;
int num_partitions = num_var_partitions (map);
int x, p;
tree t;
var_ann_t ann;
sbitmap seen;
rv = tpa_init (map);
if (!rv)
return NULL;
seen = sbitmap_alloc (num_partitions);
sbitmap_zero (seen);
for (x = num_partitions - 1; x >= 0; x--)
{
t = partition_to_var (map, x);
if (!t)
continue;
p = var_to_partition (map, t);
gcc_assert (p != NO_PARTITION);
if (TEST_BIT (seen, p))
continue;
SET_BIT (seen, p);
if (TREE_CODE (t) == SSA_NAME)
t = SSA_NAME_VAR (t);
ann = var_ann (t);
if (ann->root_var_processed)
{
rv->next_partition[p] = VARRAY_INT (rv->first_partition,
VAR_ANN_ROOT_INDEX (ann));
VARRAY_INT (rv->first_partition, VAR_ANN_ROOT_INDEX (ann)) = p;
}
else
{
ann->root_var_processed = 1;
VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++;
VARRAY_PUSH_TREE (rv->trees, t);
VARRAY_PUSH_INT (rv->first_partition, p);
}
rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann);
}
for (x = 0; x < rv->num_trees; x++)
{
t = VARRAY_TREE (rv->trees, x);
var_ann (t)->root_var_processed = 0;
}
sbitmap_free (seen);
return rv;
}
type_var_p
type_var_init (var_map map)
{
type_var_p tv;
int x, y, p;
int num_partitions = num_var_partitions (map);
tree t;
sbitmap seen;
seen = sbitmap_alloc (num_partitions);
sbitmap_zero (seen);
tv = tpa_init (map);
if (!tv)
return NULL;
for (x = num_partitions - 1; x >= 0; x--)
{
t = partition_to_var (map, x);
if (!t
|| TREE_THIS_VOLATILE (t)
|| TREE_CODE (t) == RESULT_DECL
|| TREE_CODE (t) == PARM_DECL
|| (DECL_P (t)
&& (DECL_REGISTER (t)
|| !DECL_IGNORED_P (t)
|| DECL_RTL_SET_P (t))))
continue;
p = var_to_partition (map, t);
gcc_assert (p != NO_PARTITION);
if (TEST_BIT (seen, p))
continue;
SET_BIT (seen, p);
t = TREE_TYPE (t);
for (y = 0; y < tv->num_trees; y++)
if (t == VARRAY_TREE (tv->trees, y))
break;
if (y == tv->num_trees)
{
tv->num_trees++;
VARRAY_PUSH_TREE (tv->trees, t);
VARRAY_PUSH_INT (tv->first_partition, p);
}
else
{
tv->next_partition[p] = VARRAY_INT (tv->first_partition, y);
VARRAY_INT (tv->first_partition, y) = p;
}
tv->partition_to_tree_map[p] = y;
}
sbitmap_free (seen);
return tv;
}
coalesce_list_p
create_coalesce_list (var_map map)
{
coalesce_list_p list;
list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
list->map = map;
list->add_mode = true;
list->list = (partition_pair_p *) xcalloc (num_var_partitions (map),
sizeof (struct partition_pair_d));
return list;
}
void
delete_coalesce_list (coalesce_list_p cl)
{
free (cl->list);
free (cl);
}
static partition_pair_p
find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create)
{
partition_pair_p node, tmp;
int s;
if (p2 < p1)
{
s = p1;
p1 = p2;
p2 = s;
}
tmp = NULL;
for (node = cl->list[p1]; node; node = node->next)
{
if (node->second_partition == p2)
return node;
else
if (node->second_partition > p2)
break;
tmp = node;
}
if (!create)
return NULL;
node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d));
node->first_partition = p1;
node->second_partition = p2;
node->cost = 0;
if (tmp != NULL)
{
node->next = tmp->next;
tmp->next = node;
}
else
{
node->next = cl->list[p1];
cl->list[p1] = node;
}
return node;
}
void
add_coalesce (coalesce_list_p cl, int p1, int p2, int value)
{
partition_pair_p node;
gcc_assert (cl->add_mode);
if (p1 == p2)
return;
node = find_partition_pair (cl, p1, p2, true);
node->cost += value;
}
static
int compare_pairs (const void *p1, const void *p2)
{
return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost;
}
void
sort_coalesce_list (coalesce_list_p cl)
{
unsigned x, num, count;
partition_pair_p chain, p;
partition_pair_p *list;
gcc_assert (cl->add_mode);
cl->add_mode = false;
num = 0;
chain = NULL;
for (x = 0; x < num_var_partitions (cl->map); x++)
if (cl->list[x] != NULL)
{
for (p = cl->list[x]; p->next != NULL; p = p->next)
num++;
num++;
p->next = chain;
chain = cl->list[x];
cl->list[x] = NULL;
}
if (num > 2)
{
list = xmalloc (sizeof (partition_pair_p) * num);
count = 0;
for (p = chain; p != NULL; p = p->next)
list[count++] = p;
gcc_assert (count == num);
qsort (list, count, sizeof (partition_pair_p), compare_pairs);
p = list[0];
for (x = 1; x < num; x++)
{
p->next = list[x];
p = list[x];
}
p->next = NULL;
cl->list[0] = list[0];
free (list);
}
else
{
cl->list[0] = chain;
if (num == 2)
{
if (chain->cost < chain->next->cost)
{
cl->list[0] = chain->next;
cl->list[0]->next = chain;
chain->next = NULL;
}
}
}
}
static int
pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
{
partition_pair_p node;
int ret;
gcc_assert (!cl->add_mode);
node = cl->list[0];
if (!node)
return NO_BEST_COALESCE;
cl->list[0] = node->next;
*p1 = node->first_partition;
*p2 = node->second_partition;
ret = node->cost;
free (node);
return ret;
}
static inline void
add_conflicts_if_valid (tpa_p tpa, conflict_graph graph,
var_map map, bitmap vec, tree var)
{
int p, y, first;
p = var_to_partition (map, var);
if (p != NO_PARTITION)
{
bitmap_clear_bit (vec, p);
first = tpa_find_tree (tpa, p);
if (first == TPA_NONE)
return;
for (y = tpa_first_partition (tpa, first);
y != TPA_NONE;
y = tpa_next_partition (tpa, y))
{
if (bitmap_bit_p (vec, y))
conflict_graph_add (graph, p, y);
}
}
}
conflict_graph
build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa,
coalesce_list_p cl)
{
conflict_graph graph;
var_map map;
bitmap live;
unsigned x, y, i;
basic_block bb;
varray_type partition_link, tpa_to_clear, tpa_nodes;
unsigned l;
ssa_op_iter iter;
bitmap_iterator bi;
map = live_var_map (liveinfo);
graph = conflict_graph_new (num_var_partitions (map));
if (tpa_num_trees (tpa) == 0)
return graph;
live = BITMAP_ALLOC (NULL);
VARRAY_INT_INIT (partition_link, num_var_partitions (map) + 1, "part_link");
VARRAY_INT_INIT (tpa_nodes, tpa_num_trees (tpa), "tpa nodes");
VARRAY_INT_INIT (tpa_to_clear, 50, "tpa to clear");
FOR_EACH_BB (bb)
{
block_stmt_iterator bsi;
tree phi;
bitmap_copy (live, live_on_exit (liveinfo, bb));
for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
{
bool is_a_copy = false;
tree stmt = bsi_stmt (bsi);
stmt_ann_t ann;
get_stmt_operands (stmt);
ann = stmt_ann (stmt);
if (TREE_CODE (stmt) == MODIFY_EXPR)
{
tree lhs = TREE_OPERAND (stmt, 0);
tree rhs = TREE_OPERAND (stmt, 1);
int p1, p2;
int bit;
if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME)
p1 = var_to_partition (map, lhs);
else
p1 = NO_PARTITION;
if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME)
p2 = var_to_partition (map, rhs);
else
p2 = NO_PARTITION;
if (p1 != NO_PARTITION && p2 != NO_PARTITION)
{
is_a_copy = true;
bit = bitmap_bit_p (live, p2);
if (bit)
bitmap_clear_bit (live, p2);
add_conflicts_if_valid (tpa, graph, map, live, lhs);
if (bit)
bitmap_set_bit (live, p2);
if (cl)
add_coalesce (cl, p1, p2, 1);
set_if_valid (map, live, rhs);
}
}
if (!is_a_copy)
{
tree var;
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
{
add_conflicts_if_valid (tpa, graph, map, live, var);
}
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
{
set_if_valid (map, live, var);
}
}
}
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree result = PHI_RESULT (phi);
int p = var_to_partition (map, result);
if (p != NO_PARTITION && ! bitmap_bit_p (live, p))
add_conflicts_if_valid (tpa, graph, map, live, result);
}
EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi)
{
i = tpa_find_tree (tpa, x);
if (i != (unsigned)TPA_NONE)
{
int start = VARRAY_INT (tpa_nodes, i);
if (!start)
VARRAY_PUSH_INT (tpa_to_clear, i);
for (y = start; y != 0; y = VARRAY_INT (partition_link, y))
conflict_graph_add (graph, x, y - 1);
VARRAY_INT (tpa_nodes, i) = x + 1;
VARRAY_INT (partition_link, x + 1) = start;
}
}
for (l = 0; l < VARRAY_ACTIVE_SIZE (tpa_to_clear); l++)
VARRAY_INT (tpa_nodes, VARRAY_INT (tpa_to_clear, l)) = 0;
VARRAY_POP_ALL (tpa_to_clear);
}
BITMAP_FREE (live);
return graph;
}
void
coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
coalesce_list_p cl, FILE *debug)
{
int x, y, z, w;
tree var, tmp;
if (cl)
{
while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE)
{
if (debug)
{
fprintf (debug, "Coalesce list: (%d)", x);
print_generic_expr (debug, partition_to_var (map, x), TDF_SLIM);
fprintf (debug, " & (%d)", y);
print_generic_expr (debug, partition_to_var (map, y), TDF_SLIM);
}
w = tpa_find_tree (tpa, x);
z = tpa_find_tree (tpa, y);
if (w != z || w == TPA_NONE || z == TPA_NONE)
{
if (debug)
{
if (w != z)
fprintf (debug, ": Fail, Non-matching TPA's\n");
if (w == TPA_NONE)
fprintf (debug, ": Fail %d non TPA.\n", x);
else
fprintf (debug, ": Fail %d non TPA.\n", y);
}
continue;
}
var = partition_to_var (map, x);
tmp = partition_to_var (map, y);
x = var_to_partition (map, var);
y = var_to_partition (map, tmp);
if (debug)
fprintf (debug, " [map: %d, %d] ", x, y);
if (x == y)
{
if (debug)
fprintf (debug, ": Already Coalesced.\n");
continue;
}
if (!conflict_graph_conflict_p (graph, x, y))
{
z = var_union (map, var, tmp);
if (z == NO_PARTITION)
{
if (debug)
fprintf (debug, ": Unable to perform partition union.\n");
continue;
}
if (z == x)
{
conflict_graph_merge_regs (graph, x, y);
w = tpa_find_tree (tpa, y);
tpa_remove_partition (tpa, w, y);
}
else
{
conflict_graph_merge_regs (graph, y, x);
w = tpa_find_tree (tpa, x);
tpa_remove_partition (tpa, w, x);
}
if (debug)
fprintf (debug, ": Success -> %d\n", z);
}
else
if (debug)
fprintf (debug, ": Fail due to conflict\n");
}
return;
}
for (x = 0; x < tpa_num_trees (tpa); x++)
{
while (tpa_first_partition (tpa, x) != TPA_NONE)
{
int p1, p2;
y = tpa_first_partition (tpa, x);
tpa_remove_partition (tpa, x, y);
var = partition_to_var (map, y);
p1 = var_to_partition (map, var);
for (z = tpa_next_partition (tpa, y);
z != TPA_NONE;
z = tpa_next_partition (tpa, z))
{
tmp = partition_to_var (map, z);
p2 = var_to_partition (map, tmp);
if (debug)
{
fprintf (debug, "Coalesce : ");
print_generic_expr (debug, var, TDF_SLIM);
fprintf (debug, " &");
print_generic_expr (debug, tmp, TDF_SLIM);
fprintf (debug, " (%d ,%d)", p1, p2);
}
if (tmp == var)
{
tpa_remove_partition (tpa, x, z);
if (debug)
fprintf (debug, ": Already coalesced\n");
}
else
if (!conflict_graph_conflict_p (graph, p1, p2))
{
int v;
if (tpa_find_tree (tpa, y) == TPA_NONE
|| tpa_find_tree (tpa, z) == TPA_NONE)
{
if (debug)
fprintf (debug, ": Fail non-TPA member\n");
continue;
}
if ((v = var_union (map, var, tmp)) == NO_PARTITION)
{
if (debug)
fprintf (debug, ": Fail cannot combine partitions\n");
continue;
}
tpa_remove_partition (tpa, x, z);
if (v == p1)
conflict_graph_merge_regs (graph, v, z);
else
{
conflict_graph_merge_regs (graph, v, y);
p1 = v;
}
var = partition_to_var (map, p1);
if (debug)
fprintf (debug, ": Success -> %d\n", v);
}
else
if (debug)
fprintf (debug, ": Fail, Conflict\n");
}
}
}
}
void
dump_coalesce_list (FILE *f, coalesce_list_p cl)
{
partition_pair_p node;
int x, num;
tree var;
if (cl->add_mode)
{
fprintf (f, "Coalesce List:\n");
num = num_var_partitions (cl->map);
for (x = 0; x < num; x++)
{
node = cl->list[x];
if (node)
{
fprintf (f, "[");
print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM);
fprintf (f, "] - ");
for ( ; node; node = node->next)
{
var = partition_to_var (cl->map, node->second_partition);
print_generic_expr (f, var, TDF_SLIM);
fprintf (f, "(%1d), ", node->cost);
}
fprintf (f, "\n");
}
}
}
else
{
fprintf (f, "Sorted Coalesce list:\n");
for (node = cl->list[0]; node; node = node->next)
{
fprintf (f, "(%d) ", node->cost);
var = partition_to_var (cl->map, node->first_partition);
print_generic_expr (f, var, TDF_SLIM);
fprintf (f, " : ");
var = partition_to_var (cl->map, node->second_partition);
print_generic_expr (f, var, TDF_SLIM);
fprintf (f, "\n");
}
}
}
void
tpa_dump (FILE *f, tpa_p tpa)
{
int x, i;
if (!tpa)
return;
for (x = 0; x < tpa_num_trees (tpa); x++)
{
print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM);
fprintf (f, " : (");
for (i = tpa_first_partition (tpa, x);
i != TPA_NONE;
i = tpa_next_partition (tpa, i))
{
fprintf (f, "(%d)",i);
print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM);
fprintf (f, " ");
#ifdef ENABLE_CHECKING
if (tpa_find_tree (tpa, i) != x)
fprintf (f, "**find tree incorrectly set** ");
#endif
}
fprintf (f, ")\n");
}
fflush (f);
}
void
dump_var_map (FILE *f, var_map map)
{
int t;
unsigned x, y;
int p;
fprintf (f, "\nPartition map \n\n");
for (x = 0; x < map->num_partitions; x++)
{
if (map->compact_to_partition != NULL)
p = map->compact_to_partition[x];
else
p = x;
if (map->partition_to_var[p] == NULL_TREE)
continue;
t = 0;
for (y = 1; y < num_ssa_names; y++)
{
p = partition_find (map->var_partition, y);
if (map->partition_to_compact)
p = map->partition_to_compact[p];
if (p == (int)x)
{
if (t++ == 0)
{
fprintf(f, "Partition %d (", x);
print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
fprintf (f, " - ");
}
fprintf (f, "%d ", y);
}
}
if (t != 0)
fprintf (f, ")\n");
}
fprintf (f, "\n");
}
void
dump_live_info (FILE *f, tree_live_info_p live, int flag)
{
basic_block bb;
unsigned i;
var_map map = live->map;
bitmap_iterator bi;
if ((flag & LIVEDUMP_ENTRY) && live->livein)
{
FOR_EACH_BB (bb)
{
fprintf (f, "\nLive on entry to BB%d : ", bb->index);
for (i = 0; i < num_var_partitions (map); i++)
{
if (bitmap_bit_p (live_entry_blocks (live, i), bb->index))
{
print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
fprintf (f, " ");
}
}
fprintf (f, "\n");
}
}
if ((flag & LIVEDUMP_EXIT) && live->liveout)
{
FOR_EACH_BB (bb)
{
fprintf (f, "\nLive on exit from BB%d : ", bb->index);
EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
{
print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
fprintf (f, " ");
}
fprintf (f, "\n");
}
}
}
#ifdef ENABLE_CHECKING
void
register_ssa_partition_check (tree ssa_var)
{
gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
{
fprintf (stderr, "Illegally registering a virtual SSA name :");
print_generic_expr (stderr, ssa_var, TDF_SLIM);
fprintf (stderr, " in the SSA->Normal phase.\n");
internal_error ("SSA corruption");
}
}
#endif