/* Convert a program in SSA form into Normal form.
- Copyright (C) 2004 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005 Free Software Foundation, Inc.
Contributed by Andrew Macleod <amacleod@redhat.com>
This file is part of GCC.
static inline int elim_graph_remove_succ_edge (elim_graph, int);
static inline void eliminate_name (elim_graph, tree);
-static void eliminate_build (elim_graph, basic_block, int);
+static void eliminate_build (elim_graph, basic_block);
static void elim_forward (elim_graph, int);
static int elim_unvisited_predecessor (elim_graph, int);
static void elim_backward (elim_graph, int);
static void elim_create (elim_graph, int);
-static void eliminate_phi (edge, int, elim_graph);
+static void eliminate_phi (edge, elim_graph);
static tree_live_info_p coalesce_ssa_name (var_map, int);
static void assign_vars (var_map);
static bool replace_use_variable (var_map, use_operand_p, tree *);
if (name == NULL)
name = "temp";
tmp = create_tmp_var (type, name);
+
+ if (DECL_DEBUG_EXPR (t) && DECL_DEBUG_EXPR_IS_FROM (t))
+ {
+ DECL_DEBUG_EXPR (tmp) = DECL_DEBUG_EXPR (t);
+ DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
+ }
+ else if (!DECL_IGNORED_P (t))
+ {
+ DECL_DEBUG_EXPR (tmp) = t;
+ DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
+ }
DECL_ARTIFICIAL (tmp) = DECL_ARTIFICIAL (t);
+ DECL_IGNORED_P (tmp) = DECL_IGNORED_P (t);
add_referenced_tmp_var (tmp);
/* add_referenced_tmp_var will create the annotation and set up some
}
-/* Build elimination graph G for basic block BB on incoming PHI edge I. */
+/* Build elimination graph G for basic block BB on incoming PHI edge
+ G->e. */
static void
-eliminate_build (elim_graph g, basic_block B, int i)
+eliminate_build (elim_graph g, basic_block B)
{
tree phi;
tree T0, Ti;
if (T0 == NULL_TREE)
continue;
- if (PHI_ARG_EDGE (phi, i) == g->e)
- Ti = PHI_ARG_DEF (phi, i);
- else
- {
- /* On rare occasions, a PHI node may not have the arguments
- in the same order as all of the other PHI nodes. If they don't
- match, find the appropriate index here. */
- pi = phi_arg_from_edge (phi, g->e);
- gcc_assert (pi != -1);
- Ti = PHI_ARG_DEF (phi, pi);
- }
+ Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
/* If this argument is a constant, or a SSA_NAME which is being
left in SSA form, just queue a copy to be emitted on this
}
-/* Eliminate all the phi nodes on edge E in graph G. I is the usual PHI
- index that edge E's values are found on. */
+/* Eliminate all the phi nodes on edge E in graph G. */
static void
-eliminate_phi (edge e, int i, elim_graph g)
+eliminate_phi (edge e, elim_graph g)
{
int num_nodes = 0;
int x;
basic_block B = e->dest;
- gcc_assert (i != -1);
gcc_assert (VARRAY_ACTIVE_SIZE (g->const_copies) == 0);
/* Abnormal edges already have everything coalesced, or the coalescer
num_nodes = num_var_partitions (g->map);
g->e = e;
- eliminate_build (g, B, i);
+ eliminate_build (g, B);
if (elim_graph_size (g) != 0)
{
basic_block bb;
edge e;
tree phi, var, tmp;
- int x, y;
+ int x, y, z;
edge_iterator ei;
/* Code cannot be inserted on abnormal edges. Look for all abnormal
if (x == NO_PARTITION)
continue;
- y = phi_arg_from_edge (phi, e);
- gcc_assert (y != -1);
-
- tmp = PHI_ARG_DEF (phi, y);
+ tmp = PHI_ARG_DEF (phi, e->dest_idx);
#ifdef ENABLE_CHECKING
if (!phi_ssa_name_p (tmp))
{
"ABNORMAL: Coalescing ",
var, " and ", tmp);
}
+ z = var_union (map, var, tmp);
#ifdef ENABLE_CHECKING
- if (var_union (map, var, tmp) == NO_PARTITION)
+ if (z == NO_PARTITION)
{
print_exprs_edge (stderr, e, "\nUnable to coalesce",
partition_to_var (map, x), " and ",
internal_error ("SSA corruption");
}
#else
- gcc_assert (var_union (map, var, tmp) != NO_PARTITION);
+ gcc_assert (z != NO_PARTITION);
#endif
- conflict_graph_merge_regs (graph, x, y);
+ gcc_assert (z == x || z == y);
+ if (z == x)
+ conflict_graph_merge_regs (graph, x, y);
+ else
+ conflict_graph_merge_regs (graph, y, x);
}
}
}
static tree_live_info_p
coalesce_ssa_name (var_map map, int flags)
{
- int num, x, i;
+ unsigned num, x, i;
sbitmap live;
tree var, phi;
root_var_p rv;
int p = var_to_partition (map, res);
if (p == NO_PARTITION)
continue;
- for (x = 0; x < PHI_NUM_ARGS (phi); x++)
+ for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++)
{
tree arg = PHI_ARG_DEF (phi, x);
int p2;
basic_block bb;
type_var_p tv;
tree var;
- int x, p, p2;
+ unsigned x, p, p2;
coalesce_list_p cl;
conflict_graph graph;
FOR_EACH_BB (bb)
{
tree phi, arg;
- int p;
+ unsigned p;
+
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
p = var_to_partition (map, PHI_RESULT (phi));
/* Skip virtual PHI nodes. */
- if (p == NO_PARTITION)
+ if (p == (unsigned)NO_PARTITION)
continue;
make_live_on_entry (liveinfo, bb, p);
/* Each argument is a potential copy operation. Add any arguments
which are not coalesced to the result to the coalesce list. */
- for (x = 0; x < PHI_NUM_ARGS (phi); x++)
+ for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++)
{
arg = PHI_ARG_DEF (phi, x);
if (!phi_ssa_name_p (arg))
continue;
p2 = var_to_partition (map, arg);
- if (p2 == NO_PARTITION)
+ if (p2 == (unsigned)NO_PARTITION)
continue;
if (p != p2)
add_coalesce (cl, p, p2, 1);
tree *ret = NULL;
#ifdef ENABLE_CHECKING
- int x;
+ unsigned x;
for (x = 0; x <= num_var_partitions (t->map); x++)
gcc_assert (!t->partition_dep_list[x]);
#endif
}
-/* Find VALUE if its in LIST. Return a pointer to the list object if found,
+/* Find VALUE if it's in LIST. Return a pointer to the list object if found,
else return NULL. If LAST_PTR is provided, it will point to the previous
item upon return, or NULL if this is the first item in the list. */
int num_use_ops, version;
var_map map = tab->map;
ssa_op_iter iter;
+ tree call_expr;
if (TREE_CODE (stmt) != MODIFY_EXPR)
return false;
if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
return false;
+ /* Calls to functions with side-effects cannot be replaced. */
+ if ((call_expr = get_call_expr_in (stmt)) != NULL_TREE)
+ {
+ int call_flags = call_expr_flags (call_expr);
+ if (TREE_SIDE_EFFECTS (call_expr)
+ && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN)))
+ return false;
+ }
+
uses = USE_OPS (ann);
num_use_ops = NUM_USES (uses);
vuseops = VUSE_OPS (ann);
find_replaceable_exprs (var_map map)
{
basic_block bb;
- int i;
+ unsigned i;
temp_expr_table_p table;
tree *ret;
{
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->preds)
- eliminate_phi (e, phi_arg_from_edge (phi, e), g);
+ eliminate_phi (e, g);
}
}
bool is_label;
count = 0;
+
+ /* Blocks which contain at least one abnormal edge cannot use
+ make_forwarder_block. Look for these blocks, and commit any PENDING_STMTs
+ found on edges in these block. */
+ have_opportunity = true;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (e->flags & EDGE_ABNORMAL)
+ {
+ have_opportunity = false;
+ break;
+ }
+
+ if (!have_opportunity)
+ {
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (PENDING_STMT (e))
+ bsi_commit_one_edge_insert (e, NULL);
+ return false;
+ }
/* Find out how many edges there are with interesting pending stmts on them.
Commit the stmts on edges we are not interested in. */
FOR_EACH_EDGE (e, ei, bb->preds)
#ifdef ENABLE_CHECKING
gcc_assert (VARRAY_ACTIVE_SIZE (edge_leader) == 0);
gcc_assert (VARRAY_ACTIVE_SIZE (stmt_list) == 0);
- gcc_assert (bitmap_first_set_bit (leader_has_match) == -1);
+ gcc_assert (bitmap_empty_p (leader_has_match));
#endif
}
/* Clear out any tables which were created. */
edge_leader = NULL;
- if (leader_has_match != NULL)
- {
- free (leader_has_match);
- leader_has_match = NULL;
- }
+ BITMAP_XFREE (leader_has_match);
if (changed)
{
dump_file = save;
}
+/* Search every PHI node for arguments associated with backedges which
+ we can trivially determine will need a copy (the argument is either
+ not an SSA_NAME or the argument has a different underlying variable
+ than the PHI result).
+
+ Insert a copy from the PHI argument to a new destination at the
+ end of the block with the backedge to the top of the loop. Update
+ the PHI argument to reference this new destination. */
+
+static void
+insert_backedge_copies (void)
+{
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
+ {
+ tree phi;
+
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ tree result = PHI_RESULT (phi);
+ tree result_var;
+ int i;
+
+ if (!is_gimple_reg (result))
+ continue;
+
+ result_var = SSA_NAME_VAR (result);
+ for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ {
+ tree arg = PHI_ARG_DEF (phi, i);
+ edge e = PHI_ARG_EDGE (phi, i);
+
+ /* If the argument is not an SSA_NAME, then we will
+ need a constant initialization. If the argument is
+ an SSA_NAME with a different underlying variable and
+ we are not combining temporaries, then we will
+ need a copy statement. */
+ if ((e->flags & EDGE_DFS_BACK)
+ && (TREE_CODE (arg) != SSA_NAME
+ || (!flag_tree_combine_temps
+ && SSA_NAME_VAR (arg) != result_var)))
+ {
+ tree stmt, name, last = NULL;
+ block_stmt_iterator bsi;
+
+ bsi = bsi_last (PHI_ARG_EDGE (phi, i)->src);
+ if (!bsi_end_p (bsi))
+ last = bsi_stmt (bsi);
+
+ /* In theory the only way we ought to get back to the
+ start of a loop should be with a COND_EXPR or GOTO_EXPR.
+ However, better safe than sorry.
+
+ If the block ends with a control statement or
+ something that might throw, then we have to
+ insert this assignment before the last
+ statement. Else insert it after the last statement. */
+ if (last && stmt_ends_bb_p (last))
+ {
+ /* If the last statement in the block is the definition
+ site of the PHI argument, then we can't insert
+ anything after it. */
+ if (TREE_CODE (arg) == SSA_NAME
+ && SSA_NAME_DEF_STMT (arg) == last)
+ continue;
+ }
+
+ /* Create a new instance of the underlying
+ variable of the PHI result. */
+ stmt = build (MODIFY_EXPR, TREE_TYPE (result_var),
+ NULL, PHI_ARG_DEF (phi, i));
+ name = make_ssa_name (result_var, stmt);
+ TREE_OPERAND (stmt, 0) = name;
+
+ /* Insert the new statement into the block and update
+ the PHI node. */
+ if (last && stmt_ends_bb_p (last))
+ bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
+ else
+ bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
+ modify_stmt (stmt);
+ SET_PHI_ARG_DEF (phi, i, name);
+ }
+ }
+ }
+ }
+}
+
/* Take the current function out of SSA form, as described in
R. Morgan, ``Building an Optimizing Compiler'',
Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
int var_flags = 0;
int ssa_flags = (SSANORM_REMOVE_ALL_PHIS | SSANORM_USE_COALESCE_LIST);
+ /* If elimination of a PHI requires inserting a copy on a backedge,
+ then we will have to split the backedge which has numerous
+ undesirable performance effects.
+
+ A significant number of such cases can be handled here by inserting
+ copies into the loop itself. */
+ insert_backedge_copies ();
+
if (!flag_tree_live_range_split)
ssa_flags |= SSANORM_COALESCE_PARTITIONS;
OSDN Git Service
