/* Coalesce SSA_NAMES together for the out-of-ssa pass.
- Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
+ Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
Free Software Foundation, Inc.
Contributed by Andrew MacLeod <amacleod@redhat.com>
#include "tm.h"
#include "tree.h"
#include "flags.h"
-#include "diagnostic.h"
+#include "tree-pretty-print.h"
#include "bitmap.h"
#include "tree-flow.h"
#include "hashtab.h"
#include "tree-dump.h"
#include "tree-ssa-live.h"
-#include "toplev.h"
+#include "diagnostic-core.h"
/* This set of routines implements a coalesce_list. This is an object which
is used to track pairs of ssa_names which are desirable to coalesce
- together to avoid copies. Costs are associated with each pair, and when
- all desired information has been collected, the object can be used to
+ together to avoid copies. Costs are associated with each pair, and when
+ all desired information has been collected, the object can be used to
order the pairs for processing. */
/* This structure defines a pair entry. */
/* This structure maintains the list of coalesce pairs. */
-typedef struct coalesce_list_d
+typedef struct coalesce_list_d
{
htab_t list; /* Hash table. */
coalesce_pair_p *sorted; /* List when sorted. */
#define MUST_COALESCE_COST INT_MAX
-/* Return cost of execution of copy instruction with FREQUENCY
- possibly on CRITICAL edge and in HOT basic block. */
+/* Return cost of execution of copy instruction with FREQUENCY. */
static inline int
-coalesce_cost (int frequency, bool optimize_for_size, bool critical)
+coalesce_cost (int frequency, bool optimize_for_size)
{
/* Base costs on BB frequencies bounded by 1. */
int cost = frequency;
if (optimize_for_size)
cost = 1;
- /* Inserting copy on critical edge costs more than inserting it elsewhere. */
- if (critical)
- cost *= 2;
return cost;
}
/* Return the cost of executing a copy instruction in basic block BB. */
-static inline int
+static inline int
coalesce_cost_bb (basic_block bb)
{
- return coalesce_cost (bb->frequency, optimize_bb_for_size_p (bb), false);
+ return coalesce_cost (bb->frequency, optimize_bb_for_size_p (bb));
}
/* Return the cost of executing a copy instruction on edge E. */
-static inline int
+static inline int
coalesce_cost_edge (edge e)
{
+ int mult = 1;
+
+ /* Inserting copy on critical edge costs more than inserting it elsewhere. */
+ if (EDGE_CRITICAL_P (e))
+ mult = 2;
if (e->flags & EDGE_ABNORMAL)
return MUST_COALESCE_COST;
+ if (e->flags & EDGE_EH)
+ {
+ edge e2;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e2, ei, e->dest->preds)
+ if (e2 != e)
+ {
+ /* Putting code on EH edge that leads to BB
+ with multiple predecestors imply splitting of
+ edge too. */
+ if (mult < 2)
+ mult = 2;
+ /* If there are multiple EH predecestors, we
+ also copy EH regions and produce separate
+ landing pad. This is expensive. */
+ if (e2->flags & EDGE_EH)
+ {
+ mult = 5;
+ break;
+ }
+ }
+ }
- return coalesce_cost (EDGE_FREQUENCY (e),
- optimize_edge_for_size_p (e),
- EDGE_CRITICAL_P (e));
+ return coalesce_cost (EDGE_FREQUENCY (e),
+ optimize_edge_for_size_p (e)) * mult;
}
-/* Retrieve a pair to coalesce from the cost_one_list in CL. Returns the
+/* Retrieve a pair to coalesce from the cost_one_list in CL. Returns the
2 elements via P1 and P2. 1 is returned by the function if there is a pair,
NO_BEST_COALESCE is returned if there aren't any. */
return 1;
}
-/* Retrieve the most expensive remaining pair to coalesce from CL. Returns the
+/* Retrieve the most expensive remaining pair to coalesce from CL. Returns the
2 elements via P1 and P2. Their calculated cost is returned by the function.
NO_BEST_COALESCE is returned if the coalesce list is empty. */
/* Hash function for coalesce list. Calculate hash for PAIR. */
-static unsigned int
+static unsigned int
coalesce_pair_map_hash (const void *pair)
{
hashval_t a = (hashval_t)(((const_coalesce_pair_p)pair)->first_element);
/* Equality function for coalesce list hash table. Compare PAIR1 and PAIR2,
returning TRUE if the two pairs are equivalent. */
-static int
+static int
coalesce_pair_map_eq (const void *pair1, const void *pair2)
{
const_coalesce_pair_p const p1 = (const_coalesce_pair_p) pair1;
/* Create a new empty coalesce list object and return it. */
-static inline coalesce_list_p
+static inline coalesce_list_p
create_coalesce_list (void)
{
coalesce_list_p list;
unsigned size = num_ssa_names * 3;
- if (size < 40)
+ if (size < 40)
size = 40;
list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
/* Delete coalesce list CL. */
-static inline void
+static inline void
delete_coalesce_list (coalesce_list_p cl)
{
gcc_assert (cl->cost_one_list == NULL);
htab_delete (cl->list);
- if (cl->sorted)
- free (cl->sorted);
+ free (cl->sorted);
gcc_assert (cl->num_sorted == 0);
free (cl);
}
-/* Find a matching coalesce pair object in CL for the pair P1 and P2. If
- one isn't found, return NULL if CREATE is false, otherwise create a new
+/* Find a matching coalesce pair object in CL for the pair P1 and P2. If
+ one isn't found, return NULL if CREATE is false, otherwise create a new
coalesce pair object and return it. */
static coalesce_pair_p
find_coalesce_pair (coalesce_list_p cl, int p1, int p2, bool create)
{
- struct coalesce_pair p, *pair;
+ struct coalesce_pair p;
void **slot;
unsigned int hash;
-
+
/* Normalize so that p1 is the smaller value. */
if (p2 < p1)
{
p.first_element = p1;
p.second_element = p2;
}
-
-
+
hash = coalesce_pair_map_hash (&p);
- pair = (struct coalesce_pair *) htab_find_with_hash (cl->list, &p, hash);
+ slot = htab_find_slot_with_hash (cl->list, &p, hash,
+ create ? INSERT : NO_INSERT);
+ if (!slot)
+ return NULL;
- if (create && !pair)
+ if (!*slot)
{
+ struct coalesce_pair * pair = XNEW (struct coalesce_pair);
gcc_assert (cl->sorted == NULL);
- pair = XNEW (struct coalesce_pair);
pair->first_element = p.first_element;
pair->second_element = p.second_element;
pair->cost = 0;
- slot = htab_find_slot_with_hash (cl->list, pair, hash, INSERT);
- *(struct coalesce_pair **)slot = pair;
+ *slot = (void *)pair;
}
- return pair;
+ return (struct coalesce_pair *) *slot;
}
static inline void
/* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */
-static inline void
+static inline void
add_coalesce (coalesce_list_p cl, int p1, int p2, int value)
{
coalesce_pair_p node;
/* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */
-static int
+static int
compare_pairs (const void *p1, const void *p2)
{
const_coalesce_pair_p const *const pp1 = (const_coalesce_pair_p const *) p1;
const_coalesce_pair_p const *const pp2 = (const_coalesce_pair_p const *) p2;
int result;
- result = (* pp2)->cost - (* pp1)->cost;
+ result = (* pp1)->cost - (* pp2)->cost;
/* Since qsort does not guarantee stability we use the elements
as a secondary key. This provides us with independence from
the host's implementation of the sorting algorithm. */
/* Send debug info for coalesce list CL to file F. */
-static void
+static void
dump_coalesce_list (FILE *f, coalesce_list_p cl)
{
coalesce_pair_p node;
}
-/* This represents a conflict graph. Implemented as an array of bitmaps.
+/* This represents a conflict graph. Implemented as an array of bitmaps.
A full matrix is used for conflicts rather than just upper triangular form.
this make sit much simpler and faster to perform conflict merges. */
{
bitmap b;
-#ifdef ENABLE_CHECKING
- gcc_assert (x < ptr->size);
- gcc_assert (y < ptr->size);
- gcc_assert (x != y);
-#endif
+ gcc_checking_assert (x < ptr->size);
+ gcc_checking_assert (y < ptr->size);
+ gcc_checking_assert (x != y);
b = ptr->conflicts[x];
if (b)
static inline void
ssa_conflicts_add (ssa_conflicts_p ptr, unsigned x, unsigned y)
{
-#ifdef ENABLE_CHECKING
- gcc_assert (x < ptr->size);
- gcc_assert (y < ptr->size);
- gcc_assert (x != y);
-#endif
+ gcc_checking_assert (x < ptr->size);
+ gcc_checking_assert (y < ptr->size);
+ gcc_checking_assert (x != y);
ssa_conflicts_add_one (ptr, x, y);
ssa_conflicts_add_one (ptr, y, x);
}
}
-/* This structure is used to efficiently record the current status of live
- SSA_NAMES when building a conflict graph.
+/* This structure is used to efficiently record the current status of live
+ SSA_NAMES when building a conflict graph.
LIVE_BASE_VAR has a bit set for each base variable which has at least one
ssa version live.
- LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an
- index, and is used to track what partitions of each base variable are
- live. This makes it easy to add conflicts between just live partitions
- with the same base variable.
- The values in LIVE_BASE_PARTITIONS are only valid if the base variable is
+ LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an
+ index, and is used to track what partitions of each base variable are
+ live. This makes it easy to add conflicts between just live partitions
+ with the same base variable.
+ The values in LIVE_BASE_PARTITIONS are only valid if the base variable is
marked as being live. This delays clearing of these bitmaps until
they are actually needed again. */
int root;
root = basevar_index (ptr->map, partition);
- /* If this base var wasn't live before, it is now. Clear the element list
+ /* If this base var wasn't live before, it is now. Clear the element list
since it was delayed until needed. */
- if (!bitmap_bit_p (ptr->live_base_var, root))
- {
- bitmap_set_bit (ptr->live_base_var, root);
- bitmap_clear (ptr->live_base_partitions[root]);
- }
+ if (bitmap_set_bit (ptr->live_base_var, root))
+ bitmap_clear (ptr->live_base_partitions[root]);
bitmap_set_bit (ptr->live_base_partitions[root], partition);
-
+
}
}
-/* This routine will add USE to PTR. USE will be marked as live in both the
+/* This routine will add USE to PTR. USE will be marked as live in both the
ssa live map and the live bitmap for the root of USE. */
static inline void
/* This routine will process a DEF in PTR. DEF will be removed from the live
- lists, and if there are any other live partitions with the same base
+ lists, and if there are any other live partitions with the same base
variable, conflicts will be added to GRAPH. */
static inline void
/* Build a conflict graph based on LIVEINFO. Any partitions which are in the
- partition view of the var_map liveinfo is based on get entries in the
- conflict graph. Only conflicts between ssa_name partitions with the same
+ partition view of the var_map liveinfo is based on get entries in the
+ conflict graph. Only conflicts between ssa_name partitions with the same
base variable are added. */
static ssa_conflicts_p
tree var;
gimple stmt = gsi_stmt (gsi);
- /* A copy between 2 partitions does not introduce an interference
- by itself. If they did, you would never be able to coalesce
- two things which are copied. If the two variables really do
- conflict, they will conflict elsewhere in the program.
-
- This is handled by simply removing the SRC of the copy from the
+ /* A copy between 2 partitions does not introduce an interference
+ by itself. If they did, you would never be able to coalesce
+ two things which are copied. If the two variables really do
+ conflict, they will conflict elsewhere in the program.
+
+ This is handled by simply removing the SRC of the copy from the
live list, and processing the stmt normally. */
if (is_gimple_assign (stmt))
{
&& TREE_CODE (rhs1) == SSA_NAME)
live_track_clear_var (live, rhs1);
}
+ else if (is_gimple_debug (stmt))
+ continue;
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
live_track_process_def (live, var, graph);
live_track_process_use (live, var);
}
- /* If result of a PHI is unused, looping over the statements will not
+ /* If result of a PHI is unused, looping over the statements will not
record any conflicts since the def was never live. Since the PHI node
is going to be translated out of SSA form, it will insert a copy.
- There must be a conflict recorded between the result of the PHI and
- any variables that are live. Otherwise the out-of-ssa translation
+ There must be a conflict recorded between the result of the PHI and
+ any variables that are live. Otherwise the out-of-ssa translation
may create incorrect code. */
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
/* Called if a coalesce across and abnormal edge cannot be performed. PHI is
- the phi node at fault, I is the argument index at fault. A message is
+ the phi node at fault, I is the argument index at fault. A message is
printed and compilation is then terminated. */
static inline void
used_in_virtual_ops = BITMAP_ALLOC (NULL);
#endif
- map = init_var_map (num_ssa_names + 1);
+ map = init_var_map (num_ssa_names);
FOR_EACH_BB (bb)
{
ver = SSA_NAME_VERSION (res);
register_ssa_partition (map, res);
- /* Register ssa_names and coalesces between the args and the result
+ /* Register ssa_names and coalesces between the args and the result
of all PHI. */
for (i = 0; i < gimple_phi_num_args (phi); i++)
{
arg = PHI_ARG_DEF (phi, i);
if (TREE_CODE (arg) == SSA_NAME)
register_ssa_partition (map, arg);
- if (TREE_CODE (arg) == SSA_NAME
+ if (TREE_CODE (arg) == SSA_NAME
&& SSA_NAME_VAR (arg) == SSA_NAME_VAR (res))
{
saw_copy = true;
{
stmt = gsi_stmt (gsi);
+ if (is_gimple_debug (stmt))
+ continue;
+
/* Register USE and DEF operands in each statement. */
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
register_ssa_partition (map, var);
if (SSA_NAME_VAR (outputs[match]) == SSA_NAME_VAR (input))
{
- cost = coalesce_cost (REG_BR_PROB_BASE,
- optimize_bb_for_size_p (bb),
- false);
+ cost = coalesce_cost (REG_BR_PROB_BASE,
+ optimize_bb_for_size_p (bb));
add_coalesce (cl, v1, v2, cost);
bitmap_set_bit (used_in_copy, v1);
bitmap_set_bit (used_in_copy, v2);
default:
break;
}
-
+
#ifdef ENABLE_CHECKING
/* Mark real uses and defs. */
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
/* Validate that virtual ops don't get used in funny ways. */
if (gimple_vuse (stmt))
- bitmap_set_bit (used_in_virtual_ops,
+ bitmap_set_bit (used_in_virtual_ops,
DECL_UID (SSA_NAME_VAR (gimple_vuse (stmt))));
#endif /* ENABLE_CHECKING */
}
first = NULL_TREE;
for (i = 1; i < num_ssa_names; i++)
{
- var = map->partition_to_var[i];
- if (var != NULL_TREE)
+ var = ssa_name (i);
+ if (var != NULL_TREE && is_gimple_reg (var))
{
/* Add coalesces between all the result decls. */
if (TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
/* Mark any default_def variables as being in the coalesce list
since they will have to be coalesced with the base variable. If
not marked as present, they won't be in the coalesce view. */
- if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var)
+ if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var
+ && !has_zero_uses (var))
bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
}
}
print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM);
}
- if (p1 == p2)
+ if (p1 == p2)
{
if (debug)
fprintf (debug, ": Already Coalesced.\n");
return false;
}
- /* z is the new combined partition. Remove the other partition from
+ /* z is the new combined partition. Remove the other partition from
the list, and merge the conflicts. */
if (z == p1)
ssa_conflicts_merge (graph, p1, p2);
}
-/* Attempt to Coalesce partitions in MAP which occur in the list CL using
+/* Attempt to Coalesce partitions in MAP which occur in the list CL using
GRAPH. Debug output is sent to DEBUG if it is non-NULL. */
static void
-coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
+coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
FILE *debug)
{
int x = 0, y = 0;
edge_iterator ei;
/* First, coalesce all the copies across abnormal edges. These are not placed
- in the coalesce list because they do not need to be sorted, and simply
+ in the coalesce list because they do not need to be sorted, and simply
consume extra memory/compilation time in large programs. */
FOR_EACH_BB (bb)
extern var_map
coalesce_ssa_name (void)
{
- unsigned num, x;
tree_live_info_p liveinfo;
ssa_conflicts_p graph;
coalesce_list_p cl;
{
tree a = ssa_name (i);
- if (a && SSA_NAME_VAR (a) && !DECL_ARTIFICIAL (SSA_NAME_VAR (a)))
+ if (a
+ && SSA_NAME_VAR (a)
+ && !DECL_IGNORED_P (SSA_NAME_VAR (a))
+ && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)))
{
tree *slot = (tree *) htab_find_slot (ssa_name_hash, a, INSERT);
dump_coalesce_list (dump_file, cl);
}
- /* First, coalesce all live on entry variables to their base variable.
+ /* First, coalesce all live on entry variables to their base variable.
This will ensure the first use is coming from the correct location. */
- num = num_var_partitions (map);
- for (x = 0 ; x < num; x++)
- {
- tree var = partition_to_var (map, x);
- tree root;
-
- if (TREE_CODE (var) != SSA_NAME)
- continue;
-
- root = SSA_NAME_VAR (var);
- if (gimple_default_def (cfun, root) == var)
- {
- /* This root variable should have not already been assigned
- to another partition which is not coalesced with this one. */
- gcc_assert (!var_ann (root)->out_of_ssa_tag);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- print_exprs (dump_file, "Must coalesce ", var,
- " with the root variable ", root, ".\n");
- }
- change_partition_var (map, root, x);
- }
- }
-
if (dump_file && (dump_flags & TDF_DETAILS))
dump_var_map (dump_file, map);
/* Now coalesce everything in the list. */
- coalesce_partitions (map, graph, cl,
+ coalesce_partitions (map, graph, cl,
((dump_flags & TDF_DETAILS) ? dump_file
: NULL));
OSDN Git Service
