/* 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.
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 "hard-reg-set.h"
#include "basic-block.h"
#include "output.h"
-#include "errors.h"
#include "expr.h"
#include "function.h"
#include "diagnostic.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 "tree-pass.h"
+#include "toplev.h"
+#include "vecprim.h"
+
+/* Flags to pass to remove_ssa_form. */
+
+#define SSANORM_PERFORM_TER 0x1
+#define SSANORM_COMBINE_TEMPS 0x2
+#define SSANORM_COALESCE_PARTITIONS 0x4
/* Used to hold all the components required to do SSA PHI elimination.
The node and pred/succ list is a simple linear list of nodes and
int size;
/* List of nodes in the elimination graph. */
- varray_type nodes;
+ VEC(tree,heap) *nodes;
/* The predecessor and successor edge list. */
- varray_type edge_list;
+ VEC(int,heap) *edge_list;
/* Visited vector. */
sbitmap visited;
/* Stack for visited nodes. */
- varray_type stack;
+ VEC(int,heap) *stack;
/* The variable partition map. */
var_map map;
edge e;
/* List of constant copies to emit. These are pushed on in pairs. */
- varray_type const_copies;
+ VEC(tree,heap) *const_copies;
} *elim_graph;
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_variable (var_map, tree *, tree *);
+static bool replace_use_variable (var_map, use_operand_p, tree *);
+static bool replace_def_variable (var_map, def_operand_p, tree *);
static void eliminate_virtual_phis (void);
static void coalesce_abnormal_edges (var_map, conflict_graph, root_var_p);
static void print_exprs (FILE *, const char *, tree, const char *, tree,
if (TREE_CODE (t) == SSA_NAME)
t = SSA_NAME_VAR (t);
-
- if (TREE_CODE (t) != VAR_DECL
- && TREE_CODE (t) != PARM_DECL)
- abort ();
+
+ gcc_assert (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == PARM_DECL);
type = TREE_TYPE (t);
tmp = DECL_NAME (t);
if (name == NULL)
name = "temp";
tmp = create_tmp_var (type, name);
+
+ if (DECL_DEBUG_EXPR_IS_FROM (t) && DECL_DEBUG_EXPR (t))
+ {
+ SET_DECL_DEBUG_EXPR (tmp, DECL_DEBUG_EXPR (t));
+ DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
+ }
+ else if (!DECL_IGNORED_P (t))
+ {
+ SET_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
of the flags in the annotation. However, some flags we need to
inherit from our original variable. */
- var_ann (tmp)->type_mem_tag = var_ann (t)->type_mem_tag;
+ var_ann (tmp)->symbol_mem_tag = var_ann (t)->symbol_mem_tag;
if (is_call_clobbered (t))
- mark_call_clobbered (tmp);
+ mark_call_clobbered (tmp, var_ann (t)->escape_mask);
return tmp;
}
{
tree copy;
- copy = build (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
+ copy = build2 (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
set_is_used (dest);
if (TREE_CODE (src) == ADDR_EXPR)
{
elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
- VARRAY_TREE_INIT (g->nodes, 30, "Elimination Node List");
- VARRAY_TREE_INIT (g->const_copies, 20, "Elimination Constant Copies");
- VARRAY_INT_INIT (g->edge_list, 20, "Elimination Edge List");
- VARRAY_INT_INIT (g->stack, 30, " Elimination Stack");
+ g->nodes = VEC_alloc (tree, heap, 30);
+ g->const_copies = VEC_alloc (tree, heap, 20);
+ g->edge_list = VEC_alloc (int, heap, 20);
+ g->stack = VEC_alloc (int, heap, 30);
g->visited = sbitmap_alloc (size);
static inline void
clear_elim_graph (elim_graph g)
{
- VARRAY_POP_ALL (g->nodes);
- VARRAY_POP_ALL (g->edge_list);
+ VEC_truncate (tree, g->nodes, 0);
+ VEC_truncate (int, g->edge_list, 0);
}
delete_elim_graph (elim_graph g)
{
sbitmap_free (g->visited);
+ VEC_free (int, heap, g->stack);
+ VEC_free (int, heap, g->edge_list);
+ VEC_free (tree, heap, g->const_copies);
+ VEC_free (tree, heap, g->nodes);
free (g);
}
static inline int
elim_graph_size (elim_graph g)
{
- return VARRAY_ACTIVE_SIZE (g->nodes);
+ return VEC_length (tree, g->nodes);
}
elim_graph_add_node (elim_graph g, tree node)
{
int x;
- for (x = 0; x < elim_graph_size (g); x++)
- if (VARRAY_TREE (g->nodes, x) == node)
+ tree t;
+
+ for (x = 0; VEC_iterate (tree, g->nodes, x, t); x++)
+ if (t == node)
return;
- VARRAY_PUSH_TREE (g->nodes, node);
+ VEC_safe_push (tree, heap, g->nodes, node);
}
static inline void
elim_graph_add_edge (elim_graph g, int pred, int succ)
{
- VARRAY_PUSH_INT (g->edge_list, pred);
- VARRAY_PUSH_INT (g->edge_list, succ);
+ VEC_safe_push (int, heap, g->edge_list, pred);
+ VEC_safe_push (int, heap, g->edge_list, succ);
}
{
int y;
unsigned x;
- for (x = 0; x < VARRAY_ACTIVE_SIZE (g->edge_list); x += 2)
- if (VARRAY_INT (g->edge_list, x) == node)
+ for (x = 0; x < VEC_length (int, g->edge_list); x += 2)
+ if (VEC_index (int, g->edge_list, x) == node)
{
- VARRAY_INT (g->edge_list, x) = -1;
- y = VARRAY_INT (g->edge_list, x + 1);
- VARRAY_INT (g->edge_list, x + 1) = -1;
+ VEC_replace (int, g->edge_list, x, -1);
+ y = VEC_index (int, g->edge_list, x + 1);
+ VEC_replace (int, g->edge_list, x + 1, -1);
return y;
}
return -1;
do { \
unsigned x_; \
int y_; \
- for (x_ = 0; x_ < VARRAY_ACTIVE_SIZE ((GRAPH)->edge_list); x_ += 2) \
+ for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
{ \
- y_ = VARRAY_INT ((GRAPH)->edge_list, x_); \
+ y_ = VEC_index (int, (GRAPH)->edge_list, x_); \
if (y_ != (NODE)) \
continue; \
- (VAR) = VARRAY_INT ((GRAPH)->edge_list, x_ + 1); \
+ (VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
CODE; \
} \
} while (0)
do { \
unsigned x_; \
int y_; \
- for (x_ = 0; x_ < VARRAY_ACTIVE_SIZE ((GRAPH)->edge_list); x_ += 2) \
+ for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
{ \
- y_ = VARRAY_INT ((GRAPH)->edge_list, x_ + 1); \
+ y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
if (y_ != (NODE)) \
continue; \
- (VAR) = VARRAY_INT ((GRAPH)->edge_list, x_); \
+ (VAR) = VEC_index (int, (GRAPH)->edge_list, x_); \
CODE; \
} \
} while (0)
}
-/* 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;
clear_elim_graph (g);
- for (phi = phi_nodes (B); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (B); phi; phi = PHI_CHAIN (phi))
{
T0 = var_to_partition_to_var (g->map, PHI_RESULT (phi));
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);
- if (pi == -1)
- abort();
- 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
{
/* Save constant copies until all other copies have been emitted
on this edge. */
- VARRAY_PUSH_TREE (g->const_copies, T0);
- VARRAY_PUSH_TREE (g->const_copies, Ti);
+ VEC_safe_push (tree, heap, g->const_copies, T0);
+ VEC_safe_push (tree, heap, g->const_copies, Ti);
}
else
{
if (!TEST_BIT (g->visited, S))
elim_forward (g, S);
});
- VARRAY_PUSH_INT (g->stack, T);
+ VEC_safe_push (int, heap, g->stack, T);
}
}
-/* 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;
-#if defined ENABLE_CHECKING
- if (i == -1)
- abort ();
- if (VARRAY_ACTIVE_SIZE (g->const_copies) != 0)
- abort ();
-#endif
+ gcc_assert (VEC_length (tree, g->const_copies) == 0);
- /* Abnormal edges already have everything coalesced, or the coalescer
- would have aborted. */
+ /* Abnormal edges already have everything coalesced. */
if (e->flags & EDGE_ABNORMAL)
return;
- 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)
{
+ tree var;
+
sbitmap_zero (g->visited);
- VARRAY_POP_ALL (g->stack);
+ VEC_truncate (int, g->stack, 0);
- for (x = 0; x < elim_graph_size (g); x++)
+ for (x = 0; VEC_iterate (tree, g->nodes, x, var); x++)
{
- tree var = VARRAY_TREE (g->nodes, x);
int p = var_to_partition (g->map, var);
if (!TEST_BIT (g->visited, p))
elim_forward (g, p);
}
sbitmap_zero (g->visited);
- while (VARRAY_ACTIVE_SIZE (g->stack) > 0)
+ while (VEC_length (int, g->stack) > 0)
{
- x = VARRAY_TOP_INT (g->stack);
- VARRAY_POP (g->stack);
+ x = VEC_pop (int, g->stack);
if (!TEST_BIT (g->visited, x))
elim_create (g, x);
}
}
/* If there are any pending constant copies, issue them now. */
- while (VARRAY_ACTIVE_SIZE (g->const_copies) > 0)
+ while (VEC_length (tree, g->const_copies) > 0)
{
tree src, dest;
- src = VARRAY_TOP_TREE (g->const_copies);
- VARRAY_POP (g->const_copies);
- dest = VARRAY_TOP_TREE (g->const_copies);
- VARRAY_POP (g->const_copies);
+ src = VEC_pop (tree, g->const_copies);
+ dest = VEC_pop (tree, g->const_copies);
insert_copy_on_edge (e, dest, src);
}
}
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
edges, and coalesce any PHI results with their arguments across
that edge. */
FOR_EACH_BB (bb)
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
if (e->dest != EXIT_BLOCK_PTR && e->flags & EDGE_ABNORMAL)
- for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
{
/* Visit each PHI on the destination side of this abnormal
edge, and attempt to coalesce the argument with the result. */
if (x == NO_PARTITION)
continue;
- y = phi_arg_from_edge (phi, e);
- if (y == -1)
- abort ();
-
- tmp = PHI_ARG_DEF (phi, y);
+ tmp = PHI_ARG_DEF (phi, e->dest_idx);
+#ifdef ENABLE_CHECKING
if (!phi_ssa_name_p (tmp))
{
print_exprs_edge (stderr, e,
"\nConstant argument in PHI. Can't insert :",
var, " = ", tmp);
- abort ();
+ internal_error ("SSA corruption");
}
+#else
+ gcc_assert (phi_ssa_name_p (tmp));
+#endif
y = var_to_partition (map, tmp);
- if (x == NO_PARTITION || y == NO_PARTITION)
- abort ();
+ gcc_assert (x != NO_PARTITION);
+ gcc_assert (y != NO_PARTITION);
+#ifdef ENABLE_CHECKING
if (root_var_find (rv, x) != root_var_find (rv, y))
{
print_exprs_edge (stderr, e, "\nDifferent root vars: ",
root_var (rv, root_var_find (rv, x)),
" and ",
root_var (rv, root_var_find (rv, y)));
- abort ();
+ internal_error ("SSA corruption");
}
+#else
+ gcc_assert (root_var_find (rv, x) == root_var_find (rv, y));
+#endif
if (x != y)
{
- if (!conflict_graph_conflict_p (graph, x, y))
- {
- /* Now map the partitions back to their real variables. */
- var = partition_to_var (map, x);
- tmp = partition_to_var (map, y);
- if (dump_file
- && (dump_flags & TDF_DETAILS))
- {
- print_exprs_edge (dump_file, e,
- "ABNORMAL: Coalescing ",
- var, " and ", tmp);
- }
- if (var_union (map, var, tmp) == NO_PARTITION)
- {
- print_exprs_edge (stderr, e, "\nUnable to coalesce",
- partition_to_var (map, x), " and ",
- partition_to_var (map, y));
- abort ();
- }
- conflict_graph_merge_regs (graph, x, y);
- }
- else
+#ifdef ENABLE_CHECKING
+ if (conflict_graph_conflict_p (graph, x, y))
{
print_exprs_edge (stderr, e, "\n Conflict ",
partition_to_var (map, x),
" and ", partition_to_var (map, y));
- abort ();
+ internal_error ("SSA corruption");
}
+#else
+ gcc_assert (!conflict_graph_conflict_p (graph, x, y));
+#endif
+
+ /* Now map the partitions back to their real variables. */
+ var = partition_to_var (map, x);
+ tmp = partition_to_var (map, y);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ print_exprs_edge (dump_file, e,
+ "ABNORMAL: Coalescing ",
+ var, " and ", tmp);
+ }
+ z = var_union (map, var, tmp);
+#ifdef ENABLE_CHECKING
+ if (z == NO_PARTITION)
+ {
+ print_exprs_edge (stderr, e, "\nUnable to coalesce",
+ partition_to_var (map, x), " and ",
+ partition_to_var (map, y));
+ internal_error ("SSA corruption");
+ }
+#else
+ gcc_assert (z != NO_PARTITION);
+#endif
+ gcc_assert (z == x || z == y);
+ if (z == x)
+ conflict_graph_merge_regs (graph, x, y);
+ else
+ conflict_graph_merge_regs (graph, y, x);
}
}
}
+/* Coalesce potential copies via PHI arguments. */
+
+static void
+coalesce_phi_operands (var_map map, coalesce_list_p cl)
+{
+ basic_block bb;
+ tree phi;
+
+ FOR_EACH_BB (bb)
+ {
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ tree res = PHI_RESULT (phi);
+ int p = var_to_partition (map, res);
+ int x;
+
+ if (p == NO_PARTITION)
+ continue;
+
+ for (x = 0; x < PHI_NUM_ARGS (phi); x++)
+ {
+ tree arg = PHI_ARG_DEF (phi, x);
+ int p2;
+
+ if (TREE_CODE (arg) != SSA_NAME)
+ continue;
+ if (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg))
+ continue;
+ p2 = var_to_partition (map, PHI_ARG_DEF (phi, x));
+ if (p2 != NO_PARTITION)
+ {
+ edge e = PHI_ARG_EDGE (phi, x);
+ add_coalesce (cl, p, p2,
+ coalesce_cost (EDGE_FREQUENCY (e),
+ maybe_hot_bb_p (bb),
+ EDGE_CRITICAL_P (e)));
+ }
+ }
+ }
+ }
+}
+
+/* Coalesce all the result decls together. */
+
+static void
+coalesce_result_decls (var_map map, coalesce_list_p cl)
+{
+ unsigned int i, x;
+ tree var = NULL;
+
+ for (i = x = 0; x < num_var_partitions (map); x++)
+ {
+ tree p = partition_to_var (map, x);
+ if (TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL)
+ {
+ if (var == NULL_TREE)
+ {
+ var = p;
+ i = x;
+ }
+ else
+ add_coalesce (cl, i, x,
+ coalesce_cost (EXIT_BLOCK_PTR->frequency,
+ maybe_hot_bb_p (EXIT_BLOCK_PTR),
+ false));
+ }
+ }
+}
+
+/* Coalesce matching constraints in asms. */
+
+static void
+coalesce_asm_operands (var_map map, coalesce_list_p cl)
+{
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
+ {
+ block_stmt_iterator bsi;
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+ unsigned long noutputs, i;
+ tree *outputs, link;
+
+ if (TREE_CODE (stmt) != ASM_EXPR)
+ continue;
+
+ noutputs = list_length (ASM_OUTPUTS (stmt));
+ outputs = (tree *) alloca (noutputs * sizeof (tree));
+ for (i = 0, link = ASM_OUTPUTS (stmt); link;
+ ++i, link = TREE_CHAIN (link))
+ outputs[i] = TREE_VALUE (link);
+
+ for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
+ {
+ const char *constraint
+ = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
+ tree input = TREE_VALUE (link);
+ char *end;
+ unsigned long match;
+ int p1, p2;
+
+ if (TREE_CODE (input) != SSA_NAME && !DECL_P (input))
+ continue;
+
+ match = strtoul (constraint, &end, 10);
+ if (match >= noutputs || end == constraint)
+ continue;
+
+ if (TREE_CODE (outputs[match]) != SSA_NAME
+ && !DECL_P (outputs[match]))
+ continue;
+
+ p1 = var_to_partition (map, outputs[match]);
+ if (p1 == NO_PARTITION)
+ continue;
+ p2 = var_to_partition (map, input);
+ if (p2 == NO_PARTITION)
+ continue;
+
+ add_coalesce (cl, p1, p2, coalesce_cost (REG_BR_PROB_BASE,
+ maybe_hot_bb_p (bb),
+ false));
+ }
+ }
+ }
+}
/* Reduce the number of live ranges in MAP. Live range information is
returned if FLAGS indicates that we are combining temporaries, otherwise
static tree_live_info_p
coalesce_ssa_name (var_map map, int flags)
{
- int num, x, i;
+ unsigned num, x;
sbitmap live;
- tree var, phi;
root_var_p rv;
tree_live_info_p liveinfo;
- var_ann_t ann;
conflict_graph graph;
- basic_block bb;
coalesce_list_p cl = NULL;
+ sbitmap_iterator sbi;
if (num_var_partitions (map) <= 1)
return NULL;
- /* If no preference given, use cheap coalescing of all partitions. */
- if ((flags & (SSANORM_COALESCE_PARTITIONS | SSANORM_USE_COALESCE_LIST)) == 0)
- flags |= SSANORM_COALESCE_PARTITIONS;
-
liveinfo = calculate_live_on_entry (map);
calculate_live_on_exit (liveinfo);
rv = root_var_init (map);
/* Remove single element variable from the list. */
root_var_compact (rv);
- if (flags & SSANORM_USE_COALESCE_LIST)
- {
- cl = create_coalesce_list (map);
-
- /* Add all potential copies via PHI arguments to the list. */
- FOR_EACH_BB (bb)
- {
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
- {
- tree res = PHI_RESULT (phi);
- int p = var_to_partition (map, res);
- if (p == NO_PARTITION)
- continue;
- for (x = 0; x < PHI_NUM_ARGS (phi); x++)
- {
- tree arg = PHI_ARG_DEF (phi, x);
- int p2;
-
- if (TREE_CODE (arg) != SSA_NAME)
- continue;
- if (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg))
- continue;
- p2 = var_to_partition (map, PHI_ARG_DEF (phi, x));
- if (p2 != NO_PARTITION)
- add_coalesce (cl, p, p2, 1);
- }
- }
- }
+ cl = create_coalesce_list (map);
- /* Coalesce all the result decls together. */
- var = NULL_TREE;
- i = 0;
- for (x = 0; x < num_var_partitions (map); x++)
- {
- tree p = partition_to_var (map, x);
- if (TREE_CODE (SSA_NAME_VAR(p)) == RESULT_DECL)
- {
- if (var == NULL_TREE)
- {
- var = p;
- i = x;
- }
- else
- add_coalesce (cl, i, x, 1);
- }
- }
- }
+ coalesce_phi_operands (map, cl);
+ coalesce_result_decls (map, cl);
+ coalesce_asm_operands (map, cl);
/* Build a conflict graph. */
graph = build_tree_conflict_graph (liveinfo, rv, cl);
/* First, coalesce all live on entry variables to their root variable.
This will ensure the first use is coming from the correct location. */
- live = sbitmap_alloc (num_var_partitions (map));
+ num = num_var_partitions (map);
+ live = sbitmap_alloc (num);
sbitmap_zero (live);
/* Set 'live' vector to indicate live on entry partitions. */
- num = num_var_partitions (map);
for (x = 0 ; x < num; x++)
{
- var = partition_to_var (map, x);
+ tree var = partition_to_var (map, x);
if (default_def (SSA_NAME_VAR (var)) == var)
SET_BIT (live, x);
}
/* Assign root variable as partition representative for each live on entry
partition. */
- EXECUTE_IF_SET_IN_SBITMAP (live, 0, x,
+ EXECUTE_IF_SET_IN_SBITMAP (live, 0, x, sbi)
{
- var = root_var (rv, root_var_find (rv, x));
- ann = var_ann (var);
+ tree var = root_var (rv, root_var_find (rv, x));
+ var_ann_t ann = var_ann (var);
/* If these aren't already coalesced... */
if (partition_to_var (map, x) != var)
{
- if (ann->out_of_ssa_tag)
- {
- /* This root variable has already been assigned to another
- partition which is not coalesced with this one. */
- abort ();
- }
+ /* This root variable should have not already been assigned
+ to another partition which is not coalesced with this one. */
+ gcc_assert (!ann->out_of_ssa_tag);
if (dump_file && (dump_flags & TDF_DETAILS))
{
change_partition_var (map, var, x);
}
- });
+ }
sbitmap_free (live);
dump_var_map (dump_file, map);
/* Coalesce partitions. */
- if (flags & SSANORM_USE_COALESCE_LIST)
- coalesce_tpa_members (rv, graph, map, cl,
- ((dump_flags & TDF_DETAILS) ? dump_file
- : NULL));
+ coalesce_tpa_members (rv, graph, map, cl,
+ ((dump_flags & TDF_DETAILS) ? dump_file
+ : NULL));
-
if (flags & SSANORM_COALESCE_PARTITIONS)
- coalesce_tpa_members (rv, graph, map, NULL,
- ((dump_flags & TDF_DETAILS) ? dump_file
- : NULL));
+ coalesce_tpa_members (rv, graph, map, NULL,
+ ((dump_flags & TDF_DETAILS) ? dump_file
+ : NULL));
if (cl)
delete_coalesce_list (cl);
root_var_delete (rv);
}
-/* Replace *P with whatever variable it has been rewritten to based on the
- partitions in MAP. EXPR is an optional expression vector over SSA versions
- which is used to replace *P with an expression instead of a variable.
+/* Replace use operand P with whatever variable it has been rewritten to based
+ on the partitions in MAP. EXPR is an optional expression vector over SSA
+ versions which is used to replace P with an expression instead of a variable.
If the stmt is changed, return true. */
static inline bool
-replace_variable (var_map map, tree *p, tree *expr)
+replace_use_variable (var_map map, use_operand_p p, tree *expr)
+{
+ tree new_var;
+ tree var = USE_FROM_PTR (p);
+
+ /* Check if we are replacing this variable with an expression. */
+ if (expr)
+ {
+ int version = SSA_NAME_VERSION (var);
+ if (expr[version])
+ {
+ tree new_expr = TREE_OPERAND (expr[version], 1);
+ SET_USE (p, new_expr);
+ /* Clear the stmt's RHS, or GC might bite us. */
+ TREE_OPERAND (expr[version], 1) = NULL_TREE;
+ return true;
+ }
+ }
+
+ new_var = var_to_partition_to_var (map, var);
+ if (new_var)
+ {
+ SET_USE (p, new_var);
+ set_is_used (new_var);
+ return true;
+ }
+ return false;
+}
+
+
+/* Replace def operand DEF_P with whatever variable it has been rewritten to
+ based on the partitions in MAP. EXPR is an optional expression vector over
+ SSA versions which is used to replace DEF_P with an expression instead of a
+ variable. If the stmt is changed, return true. */
+
+static inline bool
+replace_def_variable (var_map map, def_operand_p def_p, tree *expr)
{
tree new_var;
- tree var = *p;
+ tree var = DEF_FROM_PTR (def_p);
/* Check if we are replacing this variable with an expression. */
if (expr)
{
- int version = SSA_NAME_VERSION (*p);
+ int version = SSA_NAME_VERSION (var);
if (expr[version])
{
tree new_expr = TREE_OPERAND (expr[version], 1);
- *p = new_expr;
+ SET_DEF (def_p, new_expr);
/* Clear the stmt's RHS, or GC might bite us. */
TREE_OPERAND (expr[version], 1) = NULL_TREE;
return true;
new_var = var_to_partition_to_var (map, var);
if (new_var)
{
- *p = new_var;
+ SET_DEF (def_p, new_var);
set_is_used (new_var);
return true;
}
{
for (phi = phi_nodes (bb); phi; phi = next)
{
- next = TREE_CHAIN (phi);
+ next = PHI_CHAIN (phi);
if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
{
#ifdef ENABLE_CHECKING
print_generic_expr (stderr, arg, TDF_SLIM);
fprintf (stderr, "), but the result is :");
print_generic_stmt (stderr, phi, TDF_SLIM);
- abort();
+ internal_error ("SSA corruption");
}
}
#endif
- remove_phi_node (phi, NULL_TREE, bb);
+ remove_phi_node (phi, NULL_TREE);
}
}
}
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;
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ 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);
+ {
+ edge e = PHI_ARG_EDGE (phi, x);
+
+ add_coalesce (cl, p, p2,
+ coalesce_cost (EDGE_FREQUENCY (e),
+ maybe_hot_bb_p (bb),
+ EDGE_CRITICAL_P (e)));
+ }
}
}
}
dependent on any virtual variable (via a VUSE) has a dependence added
to the special partition defined by VIRTUAL_PARTITION.
- Whenever a VDEF is seen, all expressions dependent this VIRTUAL_PARTITION
- are removed from consideration.
+ Whenever a V_MAY_DEF is seen, all expressions dependent this
+ VIRTUAL_PARTITION are removed from consideration.
At the end of a basic block, all expression are removed from consideration
in preparation for the next block.
it is replaced with the RHS of the defining expression. */
-/* Dependancy list element. This can contain either a partition index or a
+/* Dependency list element. This can contain either a partition index or a
version number, depending on which list it is in. */
typedef struct value_expr_d
typedef struct temp_expr_table_d
{
var_map map;
- void **version_info;
+ void **version_info;
+ bitmap *expr_vars;
value_expr_p *partition_dep_list;
bitmap replaceable;
bool saw_replaceable;
value_expr_p pending_dependence;
} *temp_expr_table_p;
-/* Used to indicate a dependancy on VDEFs. */
+/* Used to indicate a dependency on V_MAY_DEFs. */
#define VIRTUAL_PARTITION(table) (table->virtual_partition)
static temp_expr_table_p new_temp_expr_table (var_map);
static inline void add_info_to_list (temp_expr_table_p, value_expr_p *,
value_expr_p);
static value_expr_p remove_value_from_list (value_expr_p *, int);
-static void add_dependance (temp_expr_table_p, int, tree);
+static void add_dependence (temp_expr_table_p, int, tree);
static bool check_replaceable (temp_expr_table_p, tree);
static void finish_expr (temp_expr_table_p, int, bool);
static void mark_replaceable (temp_expr_table_p, tree);
{
temp_expr_table_p t;
- t = (temp_expr_table_p) xmalloc (sizeof (struct temp_expr_table_d));
+ t = XNEW (struct temp_expr_table_d);
t->map = map;
- t->version_info = xcalloc (highest_ssa_version + 1, sizeof (void *));
- t->partition_dep_list = xcalloc (num_var_partitions (map) + 1,
- sizeof (value_expr_p));
+ t->version_info = XCNEWVEC (void *, num_ssa_names + 1);
+ t->expr_vars = XCNEWVEC (bitmap, num_ssa_names + 1);
+ t->partition_dep_list = XCNEWVEC (value_expr_p,
+ num_var_partitions (map) + 1);
- t->replaceable = BITMAP_XMALLOC ();
- t->partition_in_use = BITMAP_XMALLOC ();
+ t->replaceable = BITMAP_ALLOC (NULL);
+ t->partition_in_use = BITMAP_ALLOC (NULL);
t->saw_replaceable = false;
t->virtual_partition = num_var_partitions (map);
{
value_expr_p p;
tree *ret = NULL;
+ unsigned i;
#ifdef ENABLE_CHECKING
- int x;
+ unsigned x;
for (x = 0; x <= num_var_partitions (t->map); x++)
- if (t->partition_dep_list[x] != NULL)
- abort();
+ gcc_assert (!t->partition_dep_list[x]);
#endif
while ((p = t->free_list))
free (p);
}
- BITMAP_XFREE (t->partition_in_use);
- BITMAP_XFREE (t->replaceable);
+ BITMAP_FREE (t->partition_in_use);
+ BITMAP_FREE (t->replaceable);
+
+ for (i = 0; i <= num_ssa_names; i++)
+ if (t->expr_vars[i])
+ BITMAP_FREE (t->expr_vars[i]);
+ free (t->expr_vars);
free (t->partition_dep_list);
if (t->saw_replaceable)
}
-/* 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. */
}
-/* Add a dependancy between the def of ssa VERSION and VAR. if VAR is
- replaceable by an expression, add a dependance each of the elements of the
+/* Add a dependency between the def of ssa VERSION and VAR. If VAR is
+ replaceable by an expression, add a dependence each of the elements of the
expression. These are contained in the pending list. TAB is the
expression table. */
static void
-add_dependance (temp_expr_table_p tab, int version, tree var)
+add_dependence (temp_expr_table_p tab, int version, tree var)
{
int i, x;
value_expr_p info;
else
{
i = var_to_partition (tab->map, var);
-#ifdef ENABLE_CHECKING
- if (i== NO_PARTITION)
- abort ();
-#endif
+ gcc_assert (i != NO_PARTITION);
add_value_to_list (tab, &(tab->partition_dep_list[i]), version);
add_value_to_list (tab,
(value_expr_p *)&(tab->version_info[version]), i);
static bool
check_replaceable (temp_expr_table_p tab, tree stmt)
{
- stmt_ann_t ann;
- vuse_optype vuseops;
- def_optype defs;
- use_optype uses;
- tree var, def;
- int num_use_ops, version, i;
+ tree var, def, basevar;
+ int version;
var_map map = tab->map;
+ ssa_op_iter iter;
+ tree call_expr;
+ bitmap def_vars = BITMAP_ALLOC (NULL), use_vars;
if (TREE_CODE (stmt) != MODIFY_EXPR)
return false;
- ann = stmt_ann (stmt);
- defs = DEF_OPS (ann);
-
/* Punt if there is more than 1 def, or more than 1 use. */
- if (NUM_DEFS (defs) != 1)
- return false;
- def = DEF_OP (defs, 0);
- if (version_ref_count (map, def) != 1)
+ def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
+ if (!def)
return false;
- /* Assignments to variables assigned to hard registers are not
- replaceable. */
- if (DECL_HARD_REGISTER (SSA_NAME_VAR (def)))
+ if (version_ref_count (map, def) != 1)
return false;
- /* There must be no VDEFS. */
- if (NUM_VDEFS (VDEF_OPS (ann)) != 0)
+ /* There must be no V_MAY_DEFS or V_MUST_DEFS. */
+ if (!(ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF))))
return false;
/* Float expressions must go through memory if float-store is on. */
if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
return false;
- uses = USE_OPS (ann);
- num_use_ops = NUM_USES (uses);
- vuseops = VUSE_OPS (ann);
-
- /* Any expression which has no virtual operands and no real operands
- should have been propagated if it's possible to do anything with them.
- If this happens here, it probably exists that way for a reason, so we
- won't touch it. An example is:
- b_4 = &tab
- There are no virtual uses nor any real uses, so we just leave this
- alone to be safe. */
-
- if (num_use_ops == 0 && NUM_VUSES (vuseops) == 0)
- 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;
+ }
version = SSA_NAME_VERSION (def);
+ basevar = SSA_NAME_VAR (def);
+ bitmap_set_bit (def_vars, DECL_UID (basevar));
- /* Add this expression to the dependancy list for each use partition. */
- for (i = 0; i < num_use_ops; i++)
+ /* Add this expression to the dependency list for each use partition. */
+ FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
{
- var = USE_OP (uses, i);
- add_dependance (tab, version, var);
+ add_dependence (tab, version, var);
+
+ use_vars = tab->expr_vars[SSA_NAME_VERSION (var)];
+ if (use_vars)
+ bitmap_ior_into (def_vars, use_vars);
}
+ tab->expr_vars[version] = def_vars;
/* If there are VUSES, add a dependence on virtual defs. */
- if (NUM_VUSES (vuseops) != 0)
+ if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
{
add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]),
VIRTUAL_PARTITION (tab));
value_expr_p info, tmp;
int partition;
- /* Remove this expression from its dependent lists. The partition dependance
+ /* Remove this expression from its dependent lists. The partition dependence
list is retained and transfered later to whomever uses this version. */
for (info = (value_expr_p) tab->version_info[version]; info; info = tmp)
{
partition = info->value;
-#ifdef ENABLE_CHECKING
- if (tab->partition_dep_list[partition] == NULL)
- abort ();
-#endif
+ gcc_assert (tab->partition_dep_list[partition]);
tmp = remove_value_from_list (&(tab->partition_dep_list[partition]),
version);
-#ifdef ENABLE_CHECKING
- if (!tmp)
- abort ();
-#endif
+ gcc_assert (tmp);
free_value_expr (tab, tmp);
- /* Only clear the bit when the dependancy list is emptied via
+ /* Only clear the bit when the dependency list is emptied via
a replacement. Otherwise kill_expr will take care of it. */
if (!(tab->partition_dep_list[partition]) && replace)
bitmap_clear_bit (tab->partition_in_use, partition);
}
else
{
-#ifdef ENABLE_CHECKING
- if (bitmap_bit_p (tab->replaceable, version))
- abort ();
-#endif
+ gcc_assert (!bitmap_bit_p (tab->replaceable, version));
tab->version_info[version] = NULL;
}
}
{
value_expr_p ptr;
- /* Mark every active expr dependant on this var as not replaceable. */
+ /* Mark every active expr dependent on this var as not replaceable. */
while ((ptr = tab->partition_dep_list[partition]) != NULL)
finish_expr (tab, ptr->value, false);
}
-/* This function kills all expressions in TAB which are dependant on virtual
+/* This function kills all expressions in TAB which are dependent on virtual
DEFs. CLEAR_BIT determines whether partition_in_use gets cleared. */
static inline void
find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
{
block_stmt_iterator bsi;
- tree stmt, def;
+ tree stmt, def, use;
stmt_ann_t ann;
- int partition, num, i;
- use_optype uses;
- def_optype defs;
+ int partition;
var_map map = tab->map;
value_expr_p p;
+ ssa_op_iter iter;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
ann = stmt_ann (stmt);
/* Determine if this stmt finishes an existing expression. */
- uses = USE_OPS (ann);
- num = NUM_USES (uses);
- for (i = 0; i < num; i++)
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
{
- def = USE_OP (uses, i);
- if (tab->version_info[SSA_NAME_VERSION (def)])
+ unsigned ver = SSA_NAME_VERSION (use);
+
+ if (tab->version_info[ver])
{
- /* Mark expression as replaceable unless stmt is volatile. */
- if (!ann->has_volatile_ops)
- mark_replaceable (tab, def);
+ bool same_root_var = false;
+ ssa_op_iter iter2;
+ bitmap vars = tab->expr_vars[ver];
+
+ /* See if the root variables are the same. If they are, we
+ do not want to do the replacement to avoid problems with
+ code size, see PR tree-optimization/17549. */
+ FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF)
+ {
+ if (bitmap_bit_p (vars, DECL_UID (SSA_NAME_VAR (def))))
+ {
+ same_root_var = true;
+ break;
+ }
+ }
+
+ /* Mark expression as replaceable unless stmt is volatile
+ or DEF sets the same root variable as STMT. */
+ if (!ann->has_volatile_ops && !same_root_var)
+ mark_replaceable (tab, use);
else
- finish_expr (tab, SSA_NAME_VERSION (def), false);
+ finish_expr (tab, ver, false);
}
}
/* Next, see if this stmt kills off an active expression. */
- defs = DEF_OPS (ann);
- num = NUM_DEFS (defs);
- for (i = 0; i < num; i++)
+ FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
{
- def = DEF_OP (defs, i);
partition = var_to_partition (map, def);
if (partition != NO_PARTITION && tab->partition_dep_list[partition])
kill_expr (tab, partition, true);
if (!ann->has_volatile_ops)
check_replaceable (tab, stmt);
- /* Free any unused dependancy lists. */
+ /* Free any unused dependency lists. */
while ((p = tab->pending_dependence))
{
tab->pending_dependence = p->next;
free_value_expr (tab, p);
}
- /* A VDEF kills any expression using a virtual operand. */
- if (NUM_VDEFS (VDEF_OPS (ann)) > 0)
+ /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand. */
+ if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
kill_virtual_exprs (tab, true);
}
}
find_replaceable_exprs (var_map map)
{
basic_block bb;
- int i;
+ unsigned i;
temp_expr_table_p table;
tree *ret;
table = new_temp_expr_table (map);
FOR_EACH_BB (bb)
{
+ bitmap_iterator bi;
+
find_replaceable_in_bb (table, bb);
- EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i,
+ EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi)
{
kill_expr (table, i, false);
- });
+ }
}
ret = free_temp_expr_table (table);
tree stmt, var;
int x;
fprintf (f, "\nReplacing Expressions\n");
- for (x = 0; x < (int)highest_ssa_version + 1; x++)
+ for (x = 0; x < (int)num_ssa_names + 1; x++)
if (expr[x])
{
stmt = expr[x];
- var = DEF_OP (STMT_DEF_OPS (stmt), 0);
+ var = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
+ gcc_assert (var != NULL_TREE);
print_generic_expr (f, var, TDF_SLIM);
fprintf (f, " replace with --> ");
print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM);
}
-/* Helper function for discover_nonconstant_array_refs.
- Look for ARRAY_REF nodes with non-constant indexes and mark them
- addressable. */
-
-static tree
-discover_nonconstant_array_refs_r (tree * tp, int *walk_subtrees,
- void *data ATTRIBUTE_UNUSED)
-{
- tree t = *tp;
-
- if (TYPE_P (t) || DECL_P (t))
- *walk_subtrees = 0;
- else if (TREE_CODE (t) == ARRAY_REF)
- {
- while ((TREE_CODE (t) == ARRAY_REF
- && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
- || (TREE_CODE (t) == COMPONENT_REF
- || TREE_CODE (t) == BIT_FIELD_REF
- || TREE_CODE (t) == REALPART_EXPR
- || TREE_CODE (t) == IMAGPART_EXPR))
- t = TREE_OPERAND (t, 0);
-
- if (TREE_CODE (t) == ARRAY_REF)
- {
- t = get_base_address (t);
- if (t && DECL_P (t))
- TREE_ADDRESSABLE (t) = 1;
- }
-
- *walk_subtrees = 0;
- }
-
- return NULL_TREE;
-}
-
-
-/* RTL expansion is not able to compile array references with variable
- offsets for arrays stored in single register. Discover such
- expressions and mark variables as addressable to avoid this
- scenario. */
-
-static void
-discover_nonconstant_array_refs (void)
-{
- basic_block bb;
- block_stmt_iterator bsi;
-
- FOR_EACH_BB (bb)
- {
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- walk_tree (bsi_stmt_ptr (bsi), discover_nonconstant_array_refs_r,
- NULL , NULL);
- }
-}
-
-
/* This function will rewrite the current program using the variable mapping
found in MAP. If the replacement vector VALUES is provided, any
occurrences of partitions with non-null entries in the vector will be
{
tree phi;
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi));
print_generic_expr (stderr, arg, TDF_SLIM);
fprintf (stderr, "), but the result is not :");
print_generic_stmt (stderr, phi, TDF_SLIM);
- abort();
+ internal_error ("SSA corruption");
}
}
}
{
for (si = bsi_start (bb); !bsi_end_p (si); )
{
- size_t i, num_uses, num_defs;
- use_optype uses;
- def_optype defs;
tree stmt = bsi_stmt (si);
- tree *use_p = NULL;
- int remove = 0, is_copy = 0;
+ use_operand_p use_p, copy_use_p;
+ def_operand_p def_p;
+ bool remove = false, is_copy = false;
+ int num_uses = 0;
stmt_ann_t ann;
+ ssa_op_iter iter;
- get_stmt_operands (stmt);
ann = stmt_ann (stmt);
changed = false;
if (TREE_CODE (stmt) == MODIFY_EXPR
&& (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME))
- is_copy = 1;
+ is_copy = true;
- uses = USE_OPS (ann);
- num_uses = NUM_USES (uses);
-
- for (i = 0; i < num_uses; i++)
+ copy_use_p = NULL_USE_OPERAND_P;
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
{
- use_p = USE_OP_PTR (uses, i);
- if (replace_variable (map, use_p, values))
- changed = true;
+ if (replace_use_variable (map, use_p, values))
+ changed = true;
+ copy_use_p = use_p;
+ num_uses++;
}
- defs = DEF_OPS (ann);
- num_defs = NUM_DEFS (defs);
+ if (num_uses != 1)
+ is_copy = false;
- /* Mark this stmt for removal if it is the list of replaceable
- expressions. */
- if (values && num_defs == 1)
- {
- tree def = DEF_OP (defs, 0);
- tree val;
- val = values[SSA_NAME_VERSION (def)];
- if (val)
- remove = 1;
- }
- if (!remove)
+ def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
+
+ if (def_p != NULL)
{
- for (i = 0; i < num_defs; i++)
+ /* Mark this stmt for removal if it is the list of replaceable
+ expressions. */
+ if (values && values[SSA_NAME_VERSION (DEF_FROM_PTR (def_p))])
+ remove = true;
+ else
{
- tree *def_p = DEF_OP_PTR (defs, i);
-
- if (replace_variable (map, def_p, NULL))
+ if (replace_def_variable (map, def_p, NULL))
changed = true;
-
/* If both SSA_NAMEs coalesce to the same variable,
mark the now redundant copy for removal. */
- if (is_copy
- && num_uses == 1
- && use_p
- && def_p
- && (*def_p == *use_p))
- remove = 1;
+ if (is_copy)
+ {
+ gcc_assert (copy_use_p != NULL_USE_OPERAND_P);
+ if (DEF_FROM_PTR (def_p) == USE_FROM_PTR (copy_use_p))
+ remove = true;
+ }
}
- if (changed)
- modify_stmt (stmt);
}
+ else
+ FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
+ if (replace_def_variable (map, def_p, NULL))
+ changed = true;
/* Remove any stmts marked for removal. */
if (remove)
- bsi_remove (&si);
+ bsi_remove (&si, true);
else
bsi_next (&si);
}
phi = phi_nodes (bb);
if (phi)
{
- for (e = bb->pred; e; e = e->pred_next)
- eliminate_phi (e, phi_arg_from_edge (phi, e), g);
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ eliminate_phi (e, g);
}
}
delete_elim_graph (g);
+}
+
+
+DEF_VEC_ALLOC_P(edge,heap);
+
+/* These are the local work structures used to determine the best place to
+ insert the copies that were placed on edges by the SSA->normal pass.. */
+static VEC(edge,heap) *edge_leader;
+static VEC(tree,heap) *stmt_list;
+static bitmap leader_has_match = NULL;
+static edge leader_match = NULL;
+
+
+/* Pass this function to make_forwarder_block so that all the edges with
+ matching PENDING_STMT lists to 'curr_stmt_list' get redirected. */
+static bool
+same_stmt_list_p (edge e)
+{
+ return (e->aux == (PTR) leader_match) ? true : false;
+}
+
+
+/* Return TRUE if S1 and S2 are equivalent copies. */
+static inline bool
+identical_copies_p (tree s1, tree s2)
+{
+#ifdef ENABLE_CHECKING
+ gcc_assert (TREE_CODE (s1) == MODIFY_EXPR);
+ gcc_assert (TREE_CODE (s2) == MODIFY_EXPR);
+ gcc_assert (DECL_P (TREE_OPERAND (s1, 0)));
+ gcc_assert (DECL_P (TREE_OPERAND (s2, 0)));
+#endif
+
+ if (TREE_OPERAND (s1, 0) != TREE_OPERAND (s2, 0))
+ return false;
+
+ s1 = TREE_OPERAND (s1, 1);
+ s2 = TREE_OPERAND (s2, 1);
+
+ if (s1 != s2)
+ return false;
+
+ return true;
+}
+
+
+/* Compare the PENDING_STMT list for two edges, and return true if the lists
+ contain the same sequence of copies. */
+
+static inline bool
+identical_stmt_lists_p (edge e1, edge e2)
+{
+ tree t1 = PENDING_STMT (e1);
+ tree t2 = PENDING_STMT (e2);
+ tree_stmt_iterator tsi1, tsi2;
+
+ gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
+ gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
+
+ for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
+ !tsi_end_p (tsi1) && !tsi_end_p (tsi2);
+ tsi_next (&tsi1), tsi_next (&tsi2))
+ {
+ if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
+ break;
+ }
+
+ if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
+ return false;
+
+ return true;
+}
+
+
+/* Allocate data structures used in analyze_edges_for_bb. */
+
+static void
+init_analyze_edges_for_bb (void)
+{
+ edge_leader = VEC_alloc (edge, heap, 25);
+ stmt_list = VEC_alloc (tree, heap, 25);
+ leader_has_match = BITMAP_ALLOC (NULL);
+}
+
+
+/* Free data structures used in analyze_edges_for_bb. */
+
+static void
+fini_analyze_edges_for_bb (void)
+{
+ VEC_free (edge, heap, edge_leader);
+ VEC_free (tree, heap, stmt_list);
+ BITMAP_FREE (leader_has_match);
+}
+
+
+/* Look at all the incoming edges to block BB, and decide where the best place
+ to insert the stmts on each edge are, and perform those insertions. */
+
+static void
+analyze_edges_for_bb (basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+ int count;
+ unsigned int x;
+ bool have_opportunity;
+ block_stmt_iterator bsi;
+ tree stmt;
+ edge single_edge = NULL;
+ bool is_label;
+ edge leader;
+
+ 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;
+ }
+ /* 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)
+ {
+ if (PENDING_STMT (e))
+ {
+ gcc_assert (!(e->flags & EDGE_ABNORMAL));
+ if (e->flags & EDGE_FALLTHRU)
+ {
+ bsi = bsi_start (e->src);
+ if (!bsi_end_p (bsi))
+ {
+ stmt = bsi_stmt (bsi);
+ bsi_next (&bsi);
+ gcc_assert (stmt != NULL_TREE);
+ is_label = (TREE_CODE (stmt) == LABEL_EXPR);
+ /* Punt if it has non-label stmts, or isn't local. */
+ if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0))
+ || !bsi_end_p (bsi))
+ {
+ bsi_commit_one_edge_insert (e, NULL);
+ continue;
+ }
+ }
+ }
+ single_edge = e;
+ count++;
+ }
+ }
- /* If any copies were inserted on edges, actually insert them now. */
- bsi_commit_edge_inserts (NULL);
+ /* If there aren't at least 2 edges, no sharing will happen. */
+ if (count < 2)
+ {
+ if (single_edge)
+ bsi_commit_one_edge_insert (single_edge, NULL);
+ return;
+ }
+
+ /* Ensure that we have empty worklists. */
+#ifdef ENABLE_CHECKING
+ gcc_assert (VEC_length (edge, edge_leader) == 0);
+ gcc_assert (VEC_length (tree, stmt_list) == 0);
+ gcc_assert (bitmap_empty_p (leader_has_match));
+#endif
+
+ /* Find the "leader" block for each set of unique stmt lists. Preference is
+ given to FALLTHRU blocks since they would need a GOTO to arrive at another
+ block. The leader edge destination is the block which all the other edges
+ with the same stmt list will be redirected to. */
+ have_opportunity = false;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ if (PENDING_STMT (e))
+ {
+ bool found = false;
+
+ /* Look for the same stmt list in edge leaders list. */
+ for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
+ {
+ if (identical_stmt_lists_p (leader, e))
+ {
+ /* Give this edge the same stmt list pointer. */
+ PENDING_STMT (e) = NULL;
+ e->aux = leader;
+ bitmap_set_bit (leader_has_match, x);
+ have_opportunity = found = true;
+ break;
+ }
+ }
+
+ /* If no similar stmt list, add this edge to the leader list. */
+ if (!found)
+ {
+ VEC_safe_push (edge, heap, edge_leader, e);
+ VEC_safe_push (tree, heap, stmt_list, PENDING_STMT (e));
+ }
+ }
+ }
+
+ /* If there are no similar lists, just issue the stmts. */
+ if (!have_opportunity)
+ {
+ for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
+ bsi_commit_one_edge_insert (leader, NULL);
+ VEC_truncate (edge, edge_leader, 0);
+ VEC_truncate (tree, stmt_list, 0);
+ bitmap_clear (leader_has_match);
+ return;
+ }
+
+
+ if (dump_file)
+ fprintf (dump_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
+ bb->index);
+
+
+ /* For each common list, create a forwarding block and issue the stmt's
+ in that block. */
+ for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
+ if (bitmap_bit_p (leader_has_match, x))
+ {
+ edge new_edge;
+ block_stmt_iterator bsi;
+ tree curr_stmt_list;
+
+ leader_match = leader;
+
+ /* The tree_* cfg manipulation routines use the PENDING_EDGE field
+ for various PHI manipulations, so it gets cleared whhen calls are
+ made to make_forwarder_block(). So make sure the edge is clear,
+ and use the saved stmt list. */
+ PENDING_STMT (leader) = NULL;
+ leader->aux = leader;
+ curr_stmt_list = VEC_index (tree, stmt_list, x);
+
+ new_edge = make_forwarder_block (leader->dest, same_stmt_list_p,
+ NULL);
+ bb = new_edge->dest;
+ if (dump_file)
+ {
+ fprintf (dump_file, "Splitting BB %d for Common stmt list. ",
+ leader->dest->index);
+ fprintf (dump_file, "Original block is now BB%d.\n", bb->index);
+ print_generic_stmt (dump_file, curr_stmt_list, TDF_VOPS);
+ }
+
+ FOR_EACH_EDGE (e, ei, new_edge->src->preds)
+ {
+ e->aux = NULL;
+ if (dump_file)
+ fprintf (dump_file, " Edge (%d->%d) lands here.\n",
+ e->src->index, e->dest->index);
+ }
+
+ bsi = bsi_last (leader->dest);
+ bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
+
+ leader_match = NULL;
+ /* We should never get a new block now. */
+ }
+ else
+ {
+ PENDING_STMT (leader) = VEC_index (tree, stmt_list, x);
+ bsi_commit_one_edge_insert (leader, NULL);
+ }
+
+
+ /* Clear the working data structures. */
+ VEC_truncate (edge, edge_leader, 0);
+ VEC_truncate (tree, stmt_list, 0);
+ bitmap_clear (leader_has_match);
+}
+
+
+/* This function will analyze the insertions which were performed on edges,
+ and decide whether they should be left on that edge, or whether it is more
+ efficient to emit some subset of them in a single block. All stmts are
+ inserted somewhere. */
+
+static void
+perform_edge_inserts (void)
+{
+ basic_block bb;
+
+ if (dump_file)
+ fprintf(dump_file, "Analyzing Edge Insertions.\n");
+
+ /* analyze_edges_for_bb calls make_forwarder_block, which tries to
+ incrementally update the dominator information. Since we don't
+ need dominator information after this pass, go ahead and free the
+ dominator information. */
+ free_dominance_info (CDI_DOMINATORS);
+ free_dominance_info (CDI_POST_DOMINATORS);
+
+ /* Allocate data structures used in analyze_edges_for_bb. */
+ init_analyze_edges_for_bb ();
+
+ FOR_EACH_BB (bb)
+ analyze_edges_for_bb (bb);
+
+ analyze_edges_for_bb (EXIT_BLOCK_PTR);
+
+ /* Free data structures used in analyze_edges_for_bb. */
+ fini_analyze_edges_for_bb ();
+
+#ifdef ENABLE_CHECKING
+ {
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_BB (bb)
+ {
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ if (PENDING_STMT (e))
+ error (" Pending stmts not issued on PRED edge (%d, %d)\n",
+ e->src->index, e->dest->index);
+ }
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ if (PENDING_STMT (e))
+ error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
+ e->src->index, e->dest->index);
+ }
+ }
+ FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
+ {
+ if (PENDING_STMT (e))
+ error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
+ e->src->index, e->dest->index);
+ }
+ FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
+ {
+ if (PENDING_STMT (e))
+ error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
+ e->src->index, e->dest->index);
+ }
+ }
+#endif
}
-/* Remove the variables specified in MAP from SSA form. Any debug information
- is sent to DUMP. FLAGS indicate what options should be used. */
+/* Remove the variables specified in MAP from SSA form. FLAGS indicate what
+ options should be used. */
-void
-remove_ssa_form (FILE *dump, var_map map, int flags)
+static void
+remove_ssa_form (var_map map, int flags)
{
tree_live_info_p liveinfo;
basic_block bb;
tree phi, next;
- FILE *save;
tree *values = NULL;
- save = dump_file;
- dump_file = dump;
-
/* If we are not combining temps, don't calculate live ranges for variables
with only one SSA version. */
if ((flags & SSANORM_COMBINE_TEMPS) == 0)
{
for (phi = phi_nodes (bb); phi; phi = next)
{
- next = TREE_CHAIN (phi);
- if ((flags & SSANORM_REMOVE_ALL_PHIS)
- || var_to_partition (map, PHI_RESULT (phi)) != NO_PARTITION)
- remove_phi_node (phi, NULL_TREE, bb);
+ next = PHI_CHAIN (phi);
+ remove_phi_node (phi, NULL_TREE);
}
}
- dump_file = save;
+ /* we no longer maintain the SSA operand cache at this point. */
+ fini_ssa_operands ();
+
+ /* If any copies were inserted on edges, analyze and insert them now. */
+ perform_edge_inserts ();
}
+/* 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).
-/* Take a subset of the variables VARS in the current function out of SSA
- form. */
+ 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. */
-void
-rewrite_vars_out_of_ssa (bitmap vars)
+static void
+insert_backedge_copies (void)
{
- if (bitmap_first_set_bit (vars) >= 0)
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
{
- var_map map;
- basic_block bb;
tree phi;
- int i;
- int ssa_flags;
-
- /* Search for PHIs in which one of the PHI arguments is marked for
- translation out of SSA form, but for which the PHI result is not
- marked for translation out of SSA form.
-
- Our per-variable out of SSA translation can not handle that case;
- however we can easily handle it here by creating a new instance
- of the PHI result's underlying variable and initializing it to
- the offending PHI argument on the edge associated with the
- PHI argument. We then change the PHI argument to use our new
- instead of the PHI's underlying variable.
-
- You might think we could register partitions for the out-of-ssa
- translation here and avoid a second walk of the PHI nodes. No
- such luck since the size of the var map will change if we have
- to manually take variables out of SSA form here. */
- FOR_EACH_BB (bb)
+
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
- {
- tree result = SSA_NAME_VAR (PHI_RESULT (phi));
+ tree result = PHI_RESULT (phi);
+ tree result_var;
+ int i;
- /* If the definition is marked for renaming, then we need
- to do nothing more for this PHI node. */
- if (bitmap_bit_p (vars, var_ann (result)->uid))
- continue;
+ if (!is_gimple_reg (result))
+ continue;
- /* Look at all the arguments and see if any of them are
- marked for renaming. If so, we need to handle them
- specially. */
- for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ 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 arg = PHI_ARG_DEF (phi, i);
-
- /* If the argument is not an SSA_NAME, then we can ignore
- this argument. */
- if (TREE_CODE (arg) != SSA_NAME)
- continue;
-
- /* If this argument is marked for renaming, then we need
- to undo the copy propagation so that we can take
- the argument out of SSA form without taking the
- result out of SSA form. */
- arg = SSA_NAME_VAR (arg);
- if (bitmap_bit_p (vars, var_ann (arg)->uid))
+ 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))
{
- tree new_name, copy;
-
- /* Get a new SSA_NAME for the copy, it is based on
- the result, not the argument! We use the PHI
- as the definition since we haven't created the
- definition statement yet. */
- new_name = make_ssa_name (result, phi);
-
- /* Now create the copy statement. */
- copy = build (MODIFY_EXPR, TREE_TYPE (arg),
- new_name, PHI_ARG_DEF (phi, i));
-
- /* Now update SSA_NAME_DEF_STMT to point to the
- newly created statement. */
- SSA_NAME_DEF_STMT (new_name) = copy;
-
- /* Now make the argument reference our new SSA_NAME. */
- PHI_ARG_DEF (phi, i) = new_name;
-
- /* Queue the statement for insertion. */
- bsi_insert_on_edge (PHI_ARG_EDGE (phi, i), copy);
- modify_stmt (copy);
+ /* 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 = build2 (MODIFY_EXPR, TREE_TYPE (result_var),
+ NULL_TREE, 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);
+ SET_PHI_ARG_DEF (phi, i, name);
}
}
}
-
- /* If any copies were inserted on edges, actually insert them now. */
- bsi_commit_edge_inserts (NULL);
-
- /* Now register partitions for all instances of the variables we
- are taking out of SSA form. */
- map = init_var_map (highest_ssa_version + 1);
- register_ssa_partitions_for_vars (vars, map);
-
- /* Now that we have all the partitions registered, translate the
- appropriate variables out of SSA form. */
- ssa_flags = SSANORM_COALESCE_PARTITIONS;
- if (flag_tree_combine_temps)
- ssa_flags |= SSANORM_COMBINE_TEMPS;
- remove_ssa_form (dump_file, map, ssa_flags);
-
- /* And finally, reset the out_of_ssa flag for each of the vars
- we just took out of SSA form. */
- EXECUTE_IF_SET_IN_BITMAP (vars, 0, i,
- {
- var_ann (referenced_var (i))->out_of_ssa_tag = 0;
- });
-
- /* Free the map as we are done with it. */
- delete_var_map (map);
-
}
}
-
/* 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. */
-static void
+static unsigned int
rewrite_out_of_ssa (void)
{
var_map map;
int var_flags = 0;
- int ssa_flags = (SSANORM_REMOVE_ALL_PHIS | SSANORM_USE_COALESCE_LIST);
+ int ssa_flags = 0;
+
+ /* 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;
if (flag_tree_ter && !flag_mudflap)
ssa_flags |= SSANORM_PERFORM_TER;
- remove_ssa_form (dump_file, map, ssa_flags);
+ remove_ssa_form (map, ssa_flags);
if (dump_file && (dump_flags & TDF_DETAILS))
dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
- /* Do some cleanups which reduce the amount of data the
- tree->rtl expanders deal with. */
- cfg_remove_useless_stmts ();
-
/* Flush out flow graph and SSA data. */
delete_var_map (map);
- /* Mark arrays indexed with non-constant indices with TREE_ADDRESSABLE. */
- discover_nonconstant_array_refs ();
+ in_ssa_p = false;
+ return 0;
}
NULL, /* next */
0, /* static_pass_number */
TV_TREE_SSA_TO_NORMAL, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
+ PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
0, /* properties_provided */
/* ??? If TER is enabled, we also kill gimple. */
PROP_ssa, /* properties_destroyed */
TODO_verify_ssa | TODO_verify_flow
| TODO_verify_stmts, /* todo_flags_start */
- TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */
+ TODO_dump_func
+ | TODO_ggc_collect
+ | TODO_remove_unused_locals, /* todo_flags_finish */
+ 0 /* letter */
};
OSDN Git Service
