/* Liveness for SSA trees.
- Copyright (C) 2003 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
Contributed by Andrew MacLeod <amacleod@redhat.com>
This file is part of GCC.
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. */
+the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA. */
#include "config.h"
#include "system.h"
#include "tree-inline.h"
#include "varray.h"
#include "timevar.h"
-#include "tree-alias-common.h"
#include "hashtab.h"
#include "tree-dump.h"
#include "tree-ssa-live.h"
+#include "toplev.h"
-static void live_worklist (tree_live_info_p, varray_type, int);
+static void live_worklist (tree_live_info_p, int *, 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,
/* This function will combine the partitions in MAP for VAR1 and VAR2. It
Returns the partition which represents the new partition. If the two
- partitions cannot be combined, NO_PARTITION is returned. */
+ partitions cannot be combined, NO_PARTITION is returned. */
int
var_union (var_map map, tree var1, tree var2)
if (map->compact_to_partition)
p2 = map->compact_to_partition[p2];
- /* If there is no root_var set, or its not a user variable, set the
+ /* If there is no root_var set, or it's not a user variable, set the
root_var to this one. */
- if (!root_var || is_gimple_tmp_var (root_var))
+ if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var)))
{
other_var = root_var;
root_var = var2;
other_var = var2;
}
- if (p1 == NO_PARTITION || p2 == NO_PARTITION)
- abort ();
+ gcc_assert (p1 != NO_PARTITION);
+ gcc_assert (p2 != NO_PARTITION);
if (p1 == p2)
p3 = p1;
compact_var_map (var_map map, int flags)
{
sbitmap used;
- int x, limit, count, tmp, root, root_i;
+ int tmp, root, root_i;
+ unsigned int x, limit, count;
tree var;
root_var_p rv = NULL;
/* Build a compacted partitioning. */
if (count != limit)
{
+ sbitmap_iterator sbi;
+
map->compact_to_partition = (int *)xmalloc (count * sizeof (int));
count = 0;
/* SSA renaming begins at 1, so skip 0 when compacting. */
- EXECUTE_IF_SET_IN_SBITMAP (used, 1, x,
+ EXECUTE_IF_SET_IN_SBITMAP (used, 1, x, sbi)
{
map->partition_to_compact[x] = count;
map->compact_to_partition[count] = x;
if (TREE_CODE (var) != SSA_NAME)
change_partition_var (map, var, count);
count++;
- });
+ }
}
else
{
{
var_ann_t ann;
- if (TREE_CODE (var) == SSA_NAME)
- abort();
+ gcc_assert (TREE_CODE (var) != SSA_NAME);
ann = var_ann (var);
ann->out_of_ssa_tag = 1;
map->partition_to_var[map->compact_to_partition[part]] = var;
}
+static inline void mark_all_vars_used (tree *);
+
+/* Helper function for mark_all_vars_used, called via walk_tree. */
+
+static tree
+mark_all_vars_used_1 (tree *tp, int *walk_subtrees,
+ void *data ATTRIBUTE_UNUSED)
+{
+ tree t = *tp;
+
+ /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other
+ fields that do not contain vars. */
+ if (TREE_CODE (t) == TARGET_MEM_REF)
+ {
+ mark_all_vars_used (&TMR_SYMBOL (t));
+ mark_all_vars_used (&TMR_BASE (t));
+ mark_all_vars_used (&TMR_INDEX (t));
+ *walk_subtrees = 0;
+ return NULL;
+ }
+
+ /* Only need to mark VAR_DECLS; parameters and return results are not
+ eliminated as unused. */
+ if (TREE_CODE (t) == VAR_DECL)
+ set_is_used (t);
+
+ if (IS_TYPE_OR_DECL_P (t))
+ *walk_subtrees = 0;
+
+ return NULL;
+}
+
+/* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
+ eliminated during the tree->rtl conversion process. */
+
+static inline void
+mark_all_vars_used (tree *expr_p)
+{
+ walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
+}
/* This function looks through the program and uses FLAGS to determine what
SSA versioned variables are given entries in a new partition table. This
{
block_stmt_iterator bsi;
basic_block bb;
- tree *dest, *use;
+ tree dest, use;
tree stmt;
- stmt_ann_t ann;
- vuse_optype vuses;
- vdef_optype vdefs;
- use_optype uses;
- def_optype defs;
- unsigned x;
var_map map;
-#if defined ENABLE_CHECKING
- sbitmap used_in_real_ops;
- sbitmap used_in_virtual_ops;
+ ssa_op_iter iter;
+#ifdef ENABLE_CHECKING
+ bitmap used_in_real_ops;
+ bitmap used_in_virtual_ops;
#endif
- map = init_var_map (highest_ssa_version + 1);
-
-#if defined ENABLE_CHECKING
- used_in_real_ops = sbitmap_alloc (num_referenced_vars);
- sbitmap_zero (used_in_real_ops);
+ map = init_var_map (num_ssa_names + 1);
- used_in_virtual_ops = sbitmap_alloc (num_referenced_vars);
- sbitmap_zero (used_in_virtual_ops);
+#ifdef ENABLE_CHECKING
+ used_in_real_ops = BITMAP_ALLOC (NULL);
+ used_in_virtual_ops = BITMAP_ALLOC (NULL);
#endif
if (flags & SSA_VAR_MAP_REF_COUNT)
{
map->ref_count
- = (int *)xmalloc (((highest_ssa_version + 1) * sizeof (int)));
- memset (map->ref_count, 0, (highest_ssa_version + 1) * sizeof (int));
+ = (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 = TREE_CHAIN (phi))
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
int i;
register_ssa_partition (map, PHI_RESULT (phi), false);
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);
/* Register USE and DEF operands in each statement. */
- uses = USE_OPS (ann);
- for (x = 0; x < NUM_USES (uses); x++)
+ FOR_EACH_SSA_TREE_OPERAND (use , stmt, iter, SSA_OP_USE)
{
- use = USE_OP_PTR (uses, x);
- register_ssa_partition (map, *use, true);
+ register_ssa_partition (map, use, true);
-#if defined ENABLE_CHECKING
- SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (*use))->uid);
+#ifdef ENABLE_CHECKING
+ bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (use)));
#endif
}
- defs = DEF_OPS (ann);
- for (x = 0; x < NUM_DEFS (defs); x++)
+ FOR_EACH_SSA_TREE_OPERAND (dest, stmt, iter, SSA_OP_DEF)
{
- dest = DEF_OP_PTR (defs, x);
- register_ssa_partition (map, *dest, false);
+ register_ssa_partition (map, dest, false);
-#if defined ENABLE_CHECKING
- SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (*dest))->uid);
+#ifdef ENABLE_CHECKING
+ bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (dest)));
#endif
}
- /* While we do not care about virtual operands for
- out of SSA, we do need to look at them to make sure
- we mark all the variables which are used. */
- vuses = VUSE_OPS (ann);
- for (x = 0; x < NUM_VUSES (vuses); x++)
+#ifdef ENABLE_CHECKING
+ /* Validate that virtual ops don't get used in funny ways. */
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter,
+ SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF)
{
- tree var = VUSE_OP (vuses, x);
- set_is_used (var);
-
-#if defined ENABLE_CHECKING
- SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (var))->uid);
-#endif
+ bitmap_set_bit (used_in_virtual_ops,
+ DECL_UID (SSA_NAME_VAR (use)));
}
- vdefs = VDEF_OPS (ann);
- for (x = 0; x < NUM_VDEFS (vdefs); x++)
- {
- tree var = VDEF_OP (vdefs, x);
- set_is_used (var);
+#endif /* ENABLE_CHECKING */
-#if defined ENABLE_CHECKING
- SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (var))->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)
+ bitmap both = BITMAP_ALLOC (NULL);
+ bitmap_and (both, used_in_real_ops, used_in_virtual_ops);
+ if (!bitmap_empty_p (both))
{
- EXECUTE_IF_SET_IN_SBITMAP (both, 0, i,
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi)
fprintf (stderr, "Variable %s used in real and virtual operands\n",
- get_name (referenced_var (i))));
- abort ();
+ get_name (referenced_var (i)));
+ internal_error ("SSA corruption");
}
- sbitmap_free (used_in_real_ops);
- sbitmap_free (used_in_virtual_ops);
- sbitmap_free (both);
+ BITMAP_FREE (used_in_real_ops);
+ BITMAP_FREE (used_in_virtual_ops);
+ BITMAP_FREE (both);
}
#endif
new_tree_live_info (var_map map)
{
tree_live_info_p live;
- int x;
+ 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_XMALLOC ();
+ 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_XMALLOC ();
+ live->livein[x] = BITMAP_ALLOC (NULL);
/* liveout is deferred until it is actually requested. */
live->liveout = NULL;
if (live->liveout)
{
for (x = live->num_blocks - 1; x >= 0; x--)
- BITMAP_XFREE (live->liveout[x]);
+ BITMAP_FREE (live->liveout[x]);
free (live->liveout);
}
if (live->livein)
{
for (x = num_var_partitions (live->map) - 1; x >= 0; x--)
- BITMAP_XFREE (live->livein[x]);
+ BITMAP_FREE (live->livein[x]);
free (live->livein);
}
if (live->global)
- BITMAP_XFREE (live->global);
+ BITMAP_FREE (live->global);
free (live);
}
passed in rather than being allocated on every call. */
static void
-live_worklist (tree_live_info_p live, varray_type stack, int i)
+live_worklist (tree_live_info_p live, int *stack, int i)
{
- int b;
+ unsigned b;
tree var;
basic_block def_bb = NULL;
edge e;
var_map map = live->map;
+ edge_iterator ei;
+ bitmap_iterator bi;
+ int *tos = stack;
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,
+ EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi)
{
- VARRAY_PUSH_INT (stack, b);
- });
+ *tos++ = b;
+ }
- while (VARRAY_ACTIVE_SIZE (stack) > 0)
+ while (tos != stack)
{
- b = VARRAY_TOP_INT (stack);
- VARRAY_POP (stack);
+ b = *--tos;
- for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next)
- if (e->src != ENTRY_BLOCK_PTR)
+ FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds)
+ if (e->src != ENTRY_BLOCK_PTR)
{
/* Its not live on entry to the block its defined in. */
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);
+ bitmap_set_bit (live->livein[i], e->src->index);
+ *tos++ = e->src->index;
}
}
}
calculate_live_on_entry (var_map map)
{
tree_live_info_p live;
- int num, i;
+ unsigned i;
basic_block bb;
bitmap saw_def;
tree phi, var, stmt;
tree op;
edge e;
- varray_type stack;
+ int *stack;
block_stmt_iterator bsi;
- use_optype uses;
- def_optype defs;
- stmt_ann_t ann;
+ ssa_op_iter iter;
+ bitmap_iterator bi;
+#ifdef ENABLE_CHECKING
+ int num;
+ edge_iterator ei;
+#endif
- saw_def = BITMAP_XMALLOC ();
+ saw_def = BITMAP_ALLOC (NULL);
live = new_tree_live_info (map);
{
bitmap_clear (saw_def);
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
- for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ 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 = PHI_ARG_EDGE (phi, i);
+ e = EDGE_PRED (bb, i);
/* Any uses in PHIs which either don't have def's or are not
defined in the block from which the def comes, will be live
The a_3 referred to in b_3's PHI node is the one incoming on the
edge, *not* the PHI node just seen. */
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ 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);
- uses = USE_OPS (ann);
- num = NUM_USES (uses);
- for (i = 0; i < num; i++)
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
{
- op = USE_OP (uses, i);
add_livein_if_notdef (live, saw_def, op, bb);
}
- defs = DEF_OPS (ann);
- num = NUM_DEFS (defs);
- for (i = 0; i < num; i++)
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
{
- op = DEF_OP (defs, i);
set_if_valid (map, saw_def, op);
}
}
}
- VARRAY_INT_INIT (stack, last_basic_block, "stack");
- EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i,
+ stack = xmalloc (sizeof (int) * last_basic_block);
+ EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi)
{
live_worklist (live, stack, i);
- });
+ }
+ free (stack);
#ifdef ENABLE_CHECKING
/* Check for live on entry partitions and report those with a DEF in
bb = ENTRY_BLOCK_PTR;
num = 0;
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
{
int entry_block = e->dest->index;
if (e->dest == EXIT_BLOCK_PTR)
continue;
- for (i = 0; i < num_var_partitions (map); i++)
+ for (i = 0; i < (unsigned)num_var_partitions (map); i++)
{
basic_block tmp;
tree d;
int z, ok = 0;
for (phi = phi_nodes (e->dest);
phi && !ok;
- phi = TREE_CHAIN (phi))
+ phi = PHI_CHAIN (phi))
{
for (z = 0; z < PHI_NUM_ARGS (phi); z++)
if (var == PHI_ARG_DEF (phi, z))
}
}
}
- if (num > 0)
- abort ();
+ gcc_assert (num <= 0);
#endif
- BITMAP_XFREE (saw_def);
+ BITMAP_FREE (saw_def);
return live;
}
calculate_live_on_exit (tree_live_info_p liveinfo)
{
unsigned b;
- int i, x;
+ unsigned i, x;
bitmap *on_exit;
basic_block bb;
edge e;
var_map map = liveinfo->map;
on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
- for (x = 0; x < last_basic_block; x++)
- on_exit[x] = BITMAP_XMALLOC ();
+ for (x = 0; x < (unsigned)last_basic_block; x++)
+ on_exit[x] = BITMAP_ALLOC (NULL);
/* Set all the live-on-exit bits for uses in PHIs. */
FOR_EACH_BB (bb)
{
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
- for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ 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);
/* Set live on exit for all predecessors of live on entry's. */
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,
+ EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi)
{
- for (e = BASIC_BLOCK(b)->pred; e; e = e->pred_next)
+ 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;
/* Initialize a tree_partition_associator object using MAP. */
-tpa_p
+static tpa_p
tpa_init (var_map map)
{
tpa_p tpa;
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");
+ tpa->trees = VEC_alloc (tree, heap, x);
VARRAY_INT_INIT (tpa->first_partition, x, "first_partition");
return tpa;
if (!tpa)
return;
+ VEC_free (tree, heap, tpa->trees);
free (tpa->partition_to_tree_map);
free (tpa->next_partition);
free (tpa);
of the tree list. */
if (tpa_next_partition (tpa, first) == NO_PARTITION)
{
- swap_t = VARRAY_TREE (tpa->trees, last);
+ swap_t = VEC_index (tree, tpa->trees, last);
swap_i = VARRAY_INT (tpa->first_partition, last);
/* Update the last entry. Since it is known to only have one
partition, there is nothing else to update. */
- VARRAY_TREE (tpa->trees, last) = VARRAY_TREE (tpa->trees, x);
+ VEC_replace (tree, tpa->trees, last,
+ VEC_index (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;
/* Since this list is known to have more than one partition, update
the list owner entries. */
- VARRAY_TREE (tpa->trees, x) = swap_t;
+ VEC_replace (tree, tpa->trees, x, swap_t);
VARRAY_INT (tpa->first_partition, x) = swap_i;
for (y = tpa_first_partition (tpa, x);
y != NO_PARTITION;
p = var_to_partition (map, t);
-#ifdef ENABLE_CHECKING
- if (p == NO_PARTITION)
- abort ();
-#endif
+ gcc_assert (p != NO_PARTITION);
/* Make sure we only put coalesced partitions into the list once. */
if (TEST_BIT (seen, p))
{
ann->root_var_processed = 1;
VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++;
- VARRAY_PUSH_TREE (rv->trees, t);
+ VEC_safe_push (tree, heap, rv->trees, t);
VARRAY_PUSH_INT (rv->first_partition, p);
}
rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann);
/* Reset the out_of_ssa_tag flag on each variable for later use. */
for (x = 0; x < rv->num_trees; x++)
{
- t = VARRAY_TREE (rv->trees, x);
+ t = VEC_index (tree, rv->trees, x);
var_ann (t)->root_var_processed = 0;
}
|| TREE_CODE (t) == PARM_DECL
|| (DECL_P (t)
&& (DECL_REGISTER (t)
- || !DECL_ARTIFICIAL (t)
+ || !DECL_IGNORED_P (t)
|| DECL_RTL_SET_P (t))))
continue;
p = var_to_partition (map, t);
-#ifdef ENABLE_CHECKING
- if (p == NO_PARTITION)
- abort ();
-#endif
+ gcc_assert (p != NO_PARTITION);
/* If partitions have been coalesced, only add the representative
for the partition to the list once. */
/* Find the list for this type. */
for (y = 0; y < tv->num_trees; y++)
- if (t == VARRAY_TREE (tv->trees, y))
+ if (t == VEC_index (tree, tv->trees, y))
break;
if (y == tv->num_trees)
{
tv->num_trees++;
- VARRAY_PUSH_TREE (tv->trees, t);
+ VEC_safe_push (tree, heap, tv->trees, t);
VARRAY_PUSH_INT (tv->first_partition, p);
}
else
return node;
}
+/* Return cost of execution of copy instruction with FREQUENCY
+ possibly on CRITICAL edge and in HOT basic block. */
+int
+coalesce_cost (int frequency, bool hot, bool critical)
+{
+ /* Base costs on BB frequencies bounded by 1. */
+ int cost = frequency;
+
+ if (!cost)
+ cost = 1;
+ if (optimize_size || hot)
+ cost = 1;
+ /* Inserting copy on critical edge costs more
+ than inserting it elsewhere. */
+ if (critical)
+ cost *= 2;
+ return cost;
+}
/* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */
void
-add_coalesce (coalesce_list_p cl, int p1, int p2, int value)
+add_coalesce (coalesce_list_p cl, int p1, int p2,
+ int value)
{
partition_pair_p node;
-#ifdef ENABLE_CHECKING
- if (!cl->add_mode)
- abort();
-#endif
+ gcc_assert (cl->add_mode);
if (p1 == p2)
return;
void
sort_coalesce_list (coalesce_list_p cl)
{
- int x, num, count;
+ unsigned x, num, count;
partition_pair_p chain, p;
partition_pair_p *list;
- if (!cl->add_mode)
- abort();
+ gcc_assert (cl->add_mode);
cl->add_mode = false;
for (p = chain; p != NULL; p = p->next)
list[count++] = p;
-#ifdef ENABLE_CHECKING
- if (count != num)
- abort ();
-#endif
+ gcc_assert (count == num);
qsort (list, count, sizeof (partition_pair_p), compare_pairs);
partitions via P1 and P2. Their calculated cost is returned by the function.
NO_BEST_COALESCE is returned if the coalesce list is empty. */
-int
+static int
pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
{
partition_pair_p node;
int ret;
- if (cl->add_mode)
- abort();
+ gcc_assert (!cl->add_mode);
node = cl->list[0];
if (!node)
}
}
+DEF_VEC_I(int);
+DEF_VEC_ALLOC_I(int,heap);
/* Return a conflict graph for the information contained in LIVE_INFO. Only
conflicts between items in the same TPA list are added. If optional
conflict_graph graph;
var_map map;
bitmap live;
- int num, x, y, i;
+ unsigned x, y, i;
basic_block bb;
- varray_type partition_link, tpa_to_clear, tpa_nodes;
- def_optype defs;
- use_optype uses;
+ int *partition_link, *tpa_nodes;
+ VEC(int,heap) *tpa_to_clear;
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_XMALLOC ();
+ 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");
+ partition_link = xcalloc (num_var_partitions (map) + 1, sizeof (int));
+ tpa_nodes = xcalloc (tpa_num_trees (tpa), sizeof (int));
+ tpa_to_clear = VEC_alloc (int, heap, 50);
FOR_EACH_BB (bb)
{
block_stmt_iterator bsi;
tree phi;
+ int idx;
/* Start with live on exit temporaries. */
bitmap_copy (live, live_on_exit (liveinfo, bb));
{
bool is_a_copy = false;
tree stmt = bsi_stmt (bsi);
- stmt_ann_t ann;
-
- get_stmt_operands (stmt);
- ann = stmt_ann (stmt);
/* A copy between 2 partitions does not introduce an interference
by itself. If they did, you would never be able to coalesce
This is handled specially here since we may also be interested
in copies between real variables and SSA_NAME variables. We may
be interested in trying to coalesce SSA_NAME variables with
- root variables in some cases. */
+ root variables in some cases. */
if (TREE_CODE (stmt) == MODIFY_EXPR)
{
if (bit)
bitmap_set_bit (live, p2);
if (cl)
- add_coalesce (cl, p1, p2, 1);
+ add_coalesce (cl, p1, p2,
+ coalesce_cost (bb->frequency,
+ maybe_hot_bb_p (bb), false));
set_if_valid (map, live, rhs);
}
}
if (!is_a_copy)
{
- tree *var_p;
-
- defs = DEF_OPS (ann);
- num = NUM_DEFS (defs);
- for (x = 0; x < num; x++)
+ tree var;
+ FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
{
- var_p = DEF_OP_PTR (defs, x);
- add_conflicts_if_valid (tpa, graph, map, live, *var_p);
+ add_conflicts_if_valid (tpa, graph, map, live, var);
}
- uses = USE_OPS (ann);
- num = NUM_USES (uses);
- for (x = 0; x < num; x++)
+ FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
{
- var_p = USE_OP_PTR (uses, x);
- set_if_valid (map, live, *var_p);
+ set_if_valid (map, live, var);
}
}
}
going to be translated out of SSA form we must record a conflict
between the result of the PHI and any variables with are live.
Otherwise the out-of-ssa translation may create incorrect code. */
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree result = PHI_RESULT (phi);
int p = var_to_partition (map, result);
tpa_clear contains all the tpa_roots processed, and these are the only
entries which need to be zero'd out for a clean restart. */
- EXECUTE_IF_SET_IN_BITMAP (live, 0, x,
+ EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi)
{
i = tpa_find_tree (tpa, x);
- if (i != TPA_NONE)
+ if (i != (unsigned)TPA_NONE)
{
- int start = VARRAY_INT (tpa_nodes, i);
+ int start = tpa_nodes[i];
/* If start is 0, a new root reference list is being started.
Register it to be cleared. */
if (!start)
- VARRAY_PUSH_INT (tpa_to_clear, i);
+ VEC_safe_push (int, heap, tpa_to_clear, i);
/* Add interferences to other tpa members seen. */
- for (y = start; y != 0; y = VARRAY_INT (partition_link, y))
+ for (y = start; y != 0; y = partition_link[y])
conflict_graph_add (graph, x, y - 1);
- VARRAY_INT (tpa_nodes, i) = x + 1;
- VARRAY_INT (partition_link, x + 1) = start;
+ tpa_nodes[i] = x + 1;
+ partition_link[x + 1] = start;
}
- });
+ }
/* Now clear the used tpa root references. */
- 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);
+ for (l = 0; VEC_iterate (int, tpa_to_clear, l, idx); l++)
+ tpa_nodes[idx] = 0;
+ VEC_truncate (int, tpa_to_clear, 0);
}
- BITMAP_XFREE (live);
+ free (tpa_nodes);
+ free (partition_link);
+ VEC_free (int, heap, tpa_to_clear);
+ BITMAP_FREE (live);
return graph;
}
continue;
t = 0;
- for (y = 1; y < highest_ssa_version; y++)
+ for (y = 1; y < num_ssa_names; y++)
{
p = partition_find (map->var_partition, y);
if (map->partition_to_compact)
dump_live_info (FILE *f, tree_live_info_p live, int flag)
{
basic_block bb;
- int i;
+ unsigned i;
var_map map = live->map;
+ bitmap_iterator bi;
if ((flag & LIVEDUMP_ENTRY) && live->livein)
{
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,
+ 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");
}
}
}
-/* Register partitions in MAP so that we can take VARS out of SSA form.
- This requires a walk over all the PHI nodes and all the statements. */
-
+#ifdef ENABLE_CHECKING
void
-register_ssa_partitions_for_vars (bitmap vars, var_map map)
+register_ssa_partition_check (tree ssa_var)
{
- basic_block bb;
-
- if (bitmap_first_set_bit (vars) >= 0)
+ gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
+ if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
{
-
- /* Find every instance (SSA_NAME) of variables in VARs and
- register a new partition for them. This requires examining
- every statement and every PHI node once. */
- FOR_EACH_BB (bb)
- {
- block_stmt_iterator bsi;
- tree next;
- tree phi;
-
- /* Register partitions for SSA_NAMEs appearing in the PHI
- nodes in this basic block.
-
- Note we delete PHI nodes in this loop if they are
- associated with virtual vars which are going to be
- renamed. */
- for (phi = phi_nodes (bb); phi; phi = next)
- {
- tree result = SSA_NAME_VAR (PHI_RESULT (phi));
-
- next = TREE_CHAIN (phi);
- if (bitmap_bit_p (vars, var_ann (result)->uid))
- {
- if (! is_gimple_reg (result))
- remove_phi_node (phi, NULL_TREE, bb);
- else
- {
- int i;
-
- /* Register a partition for the result. */
- register_ssa_partition (map, PHI_RESULT (phi), 0);
-
- /* Register a partition for each argument as needed. */
- for (i = 0; i < PHI_NUM_ARGS (phi); i++)
- {
- tree arg = PHI_ARG_DEF (phi, i);
-
- if (TREE_CODE (arg) != SSA_NAME)
- continue;
- if (!bitmap_bit_p (vars,
- var_ann (SSA_NAME_VAR (arg))->uid))
- continue;
-
- register_ssa_partition (map, arg, 1);
- }
- }
- }
- }
-
- /* Now register partitions for SSA_NAMEs appearing in each
- statement in this block. */
- for (bsi = bsi_start (bb); ! bsi_end_p (bsi); bsi_next (&bsi))
- {
- stmt_ann_t ann = stmt_ann (bsi_stmt (bsi));
- use_optype uses = USE_OPS (ann);
- def_optype defs = DEF_OPS (ann);
- unsigned int i;
-
- for (i = 0; i < NUM_USES (uses); i++)
- {
- tree op = USE_OP (uses, i);
-
- if (TREE_CODE (op) == SSA_NAME
- && bitmap_bit_p (vars, var_ann (SSA_NAME_VAR (op))->uid))
- register_ssa_partition (map, op, 1);
- }
-
- for (i = 0; i < NUM_DEFS (defs); i++)
- {
- tree op = DEF_OP (defs, i);
-
- if (TREE_CODE (op) == SSA_NAME
- && bitmap_bit_p (vars,
- var_ann (SSA_NAME_VAR (op))->uid))
- register_ssa_partition (map, op, 0);
- }
- }
- }
+ 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
OSDN Git Service
