/* 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"
+#include "vecprim.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,
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. */
{
tree t = *tp;
+ if (TREE_CODE (t) == SSA_NAME)
+ t = SSA_NAME_VAR (t);
+
+ /* 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 (DECL_P (t) || TYPE_P (t))
+ if (IS_TYPE_OR_DECL_P (t))
*walk_subtrees = 0;
return NULL;
walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
}
+
+/* Remove local variables that are not referenced in the IL. */
+
+void
+remove_unused_locals (void)
+{
+ basic_block bb;
+ tree t, *cell;
+
+ /* Assume all locals are unused. */
+ for (t = cfun->unexpanded_var_list; t; t = TREE_CHAIN (t))
+ {
+ tree var = TREE_VALUE (t);
+ if (TREE_CODE (var) != FUNCTION_DECL
+ && var_ann (var))
+ var_ann (var)->used = false;
+ }
+
+ /* Walk the CFG marking all referenced symbols. */
+ FOR_EACH_BB (bb)
+ {
+ block_stmt_iterator bsi;
+ tree phi, def;
+
+ /* Walk the statements. */
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ mark_all_vars_used (bsi_stmt_ptr (bsi));
+
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ use_operand_p arg_p;
+ ssa_op_iter i;
+
+ /* No point processing globals. */
+ if (is_global_var (SSA_NAME_VAR (PHI_RESULT (phi))))
+ continue;
+
+ def = PHI_RESULT (phi);
+ mark_all_vars_used (&def);
+
+ FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
+ {
+ tree arg = USE_FROM_PTR (arg_p);
+ mark_all_vars_used (&arg);
+ }
+ }
+ }
+
+ /* Remove unmarked vars and clear used flag. */
+ for (cell = &cfun->unexpanded_var_list; *cell; )
+ {
+ tree var = TREE_VALUE (*cell);
+ var_ann_t ann;
+
+ if (TREE_CODE (var) != FUNCTION_DECL
+ && (!(ann = var_ann (var))
+ || !ann->used))
+ {
+ *cell = TREE_CHAIN (*cell);
+ continue;
+ }
+
+ cell = &TREE_CHAIN (*cell);
+ }
+}
+
/* This function looks through the program and uses FLAGS to determine what
SSA versioned variables are given entries in a new partition table. This
new partition map is returned. */
basic_block bb;
tree dest, use;
tree stmt;
- stmt_ann_t ann;
- use_optype uses;
- def_optype defs;
- unsigned x;
var_map map;
+ ssa_op_iter iter;
#ifdef ENABLE_CHECKING
- sbitmap used_in_real_ops;
- sbitmap used_in_virtual_ops;
- vuse_optype vuses;
- v_may_def_optype v_may_defs;
- v_must_def_optype v_must_defs;
+ bitmap used_in_real_ops;
+ bitmap 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);
+ used_in_real_ops = BITMAP_ALLOC (NULL);
+ used_in_virtual_ops = BITMAP_ALLOC (NULL);
#endif
if (flags & SSA_VAR_MAP_REF_COUNT)
FOR_EACH_BB (bb)
{
tree phi, arg;
+
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
int 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 (uses, x);
register_ssa_partition (map, use, true);
#ifdef ENABLE_CHECKING
- SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (use))->uid);
+ 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 (defs, x);
register_ssa_partition (map, dest, false);
#ifdef ENABLE_CHECKING
- SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (dest))->uid);
+ bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (dest)));
#endif
}
#ifdef ENABLE_CHECKING
/* Validate that virtual ops don't get used in funny ways. */
- vuses = VUSE_OPS (ann);
- for (x = 0; x < NUM_VUSES (vuses); x++)
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter,
+ SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF)
{
- tree var = VUSE_OP (vuses, x);
- SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (var))->uid);
+ bitmap_set_bit (used_in_virtual_ops,
+ DECL_UID (SSA_NAME_VAR (use)));
}
- v_may_defs = V_MAY_DEF_OPS (ann);
- for (x = 0; x < NUM_V_MAY_DEFS (v_may_defs); x++)
- {
- tree var = V_MAY_DEF_OP (v_may_defs, x);
- SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (var))->uid);
- }
-
- v_must_defs = V_MUST_DEF_OPS (ann);
- for (x = 0; x < NUM_V_MUST_DEFS (v_must_defs); x++)
- {
- tree var = V_MUST_DEF_OP (v_must_defs, x);
- SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (var))->uid);
- }
#endif /* ENABLE_CHECKING */
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);
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
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 = XNEWVEC (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;
}
}
}
- 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 = PHI_CHAIN (phi))
- for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ 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");
- VARRAY_INT_INIT (tpa->first_partition, x, "first_partition");
+ tpa->trees = VEC_alloc (tree, heap, x);
+ tpa->first_partition = VEC_alloc (int, heap, x);
return tpa;
i = tpa_first_partition (tpa, tree_index);
if (i == partition_index)
{
- VARRAY_INT (tpa->first_partition, tree_index) = tpa->next_partition[i];
+ VEC_replace (int, tpa->first_partition, tree_index,
+ tpa->next_partition[i]);
}
else
{
if (!tpa)
return;
+ VEC_free (tree, heap, tpa->trees);
+ VEC_free (int, heap, tpa->first_partition);
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_i = VARRAY_INT (tpa->first_partition, last);
+ swap_t = VEC_index (tree, tpa->trees, last);
+ swap_i = VEC_index (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);
- VARRAY_INT (tpa->first_partition, last)
- = VARRAY_INT (tpa->first_partition, x);
+ VEC_replace (tree, tpa->trees, last,
+ VEC_index (tree, tpa->trees, x));
+ VEC_replace (int, tpa->first_partition, last,
+ VEC_index (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;
- VARRAY_INT (tpa->first_partition, x) = swap_i;
+ VEC_replace (tree, tpa->trees, x, swap_t);
+ VEC_replace (int, tpa->first_partition, x, swap_i);
for (y = tpa_first_partition (tpa, x);
y != NO_PARTITION;
y = tpa_next_partition (tpa, y))
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 = 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;
+ rv->next_partition[p] = VEC_index (int, rv->first_partition,
+ VAR_ANN_ROOT_INDEX (ann));
+ VEC_replace (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);
+ VEC_safe_push (tree, heap, rv->trees, t);
+ VEC_safe_push (int, heap, 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 t;
sbitmap seen;
- seen = sbitmap_alloc (num_partitions);
- sbitmap_zero (seen);
-
tv = tpa_init (map);
if (!tv)
return NULL;
+ seen = sbitmap_alloc (num_partitions);
+ sbitmap_zero (seen);
+
for (x = num_partitions - 1; x >= 0; x--)
{
t = partition_to_var (map, x);
|| 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);
- VARRAY_PUSH_INT (tv->first_partition, p);
+ VEC_safe_push (tree, heap, tv->trees, t);
+ VEC_safe_push (int, heap, tv->first_partition, p);
}
else
{
- tv->next_partition[p] = VARRAY_INT (tv->first_partition, y);
- VARRAY_INT (tv->first_partition, y) = p;
+ tv->next_partition[p] = VEC_index (int, tv->first_partition, y);
+ VEC_replace (int, tv->first_partition, y, p);
}
tv->partition_to_tree_map[p] = y;
}
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;
/* Only call qsort if there are more than 2 items. */
if (num > 2)
{
- list = xmalloc (sizeof (partition_pair_p) * num);
+ list = XNEWVEC (partition_pair_p, num);
count = 0;
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)
}
}
-
/* Return a conflict graph for the information contained in LIVE_INFO. Only
conflicts between items in the same TPA list are added. If optional
coalesce list CL is passed in, any copies encountered are added. */
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 = XCNEWVEC (int, num_var_partitions (map) + 1);
+ tpa_nodes = XCNEWVEC (int, tpa_num_trees (tpa));
+ 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
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;
-
- defs = DEF_OPS (ann);
- num = NUM_DEFS (defs);
- for (x = 0; x < num; x++)
+ FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
{
- var = DEF_OP (defs, x);
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 = USE_OP (uses, x);
set_if_valid (map, live, var);
}
}
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;
}
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 = PHI_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
