#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "flags.h"
#include "rtl.h"
#include "tm_p.h"
#include "ggc.h"
#include "langhooks.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "output.h"
#include "expr.h"
#include "function.h"
#include "diagnostic.h"
#include "bitmap.h"
#include "tree-flow.h"
#include "tree-gimple.h"
#include "tree-inline.h"
#include "varray.h"
#include "timevar.h"
#include "hashtab.h"
#include "tree-dump.h"
#include "tree-ssa-live.h"
#include "tree-pass.h"
#include "toplev.h"
#include "vecprim.h"
#define SSANORM_PERFORM_TER 0x1
#define SSANORM_COMBINE_TEMPS 0x2
#define SSANORM_COALESCE_PARTITIONS 0x4
typedef struct _elim_graph {
int size;
VEC(tree,heap) *nodes;
VEC(int,heap) *edge_list;
sbitmap visited;
VEC(int,heap) *stack;
var_map map;
edge e;
VEC(tree,heap) *const_copies;
} *elim_graph;
static tree create_temp (tree);
static void insert_copy_on_edge (edge, tree, tree);
static elim_graph new_elim_graph (int);
static inline void delete_elim_graph (elim_graph);
static inline void clear_elim_graph (elim_graph);
static inline int elim_graph_size (elim_graph);
static inline void elim_graph_add_node (elim_graph, tree);
static inline void elim_graph_add_edge (elim_graph, int, int);
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);
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, 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 *);
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,
const char *);
static void print_exprs_edge (FILE *, edge, const char *, tree, const char *,
tree);
static tree
create_temp (tree t)
{
tree tmp;
const char *name = NULL;
tree type;
if (TREE_CODE (t) == SSA_NAME)
t = SSA_NAME_VAR (t);
gcc_assert (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == PARM_DECL);
type = TREE_TYPE (t);
tmp = DECL_NAME (t);
if (tmp)
name = IDENTIFIER_POINTER (tmp);
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_var (tmp);
var_ann (tmp)->symbol_mem_tag = var_ann (t)->symbol_mem_tag;
if (is_call_clobbered (t))
mark_call_clobbered (tmp, var_ann (t)->escape_mask);
return tmp;
}
static void
insert_copy_on_edge (edge e, tree dest, tree src)
{
tree copy;
copy = build2 (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
set_is_used (dest);
if (TREE_CODE (src) == ADDR_EXPR)
src = TREE_OPERAND (src, 0);
if (TREE_CODE (src) == VAR_DECL || TREE_CODE (src) == PARM_DECL)
set_is_used (src);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file,
"Inserting a copy on edge BB%d->BB%d :",
e->src->index,
e->dest->index);
print_generic_expr (dump_file, copy, dump_flags);
fprintf (dump_file, "\n");
}
bsi_insert_on_edge (e, copy);
}
static elim_graph
new_elim_graph (int size)
{
elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
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);
return g;
}
static inline void
clear_elim_graph (elim_graph g)
{
VEC_truncate (tree, g->nodes, 0);
VEC_truncate (int, g->edge_list, 0);
}
static inline void
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 VEC_length (tree, g->nodes);
}
static inline void
elim_graph_add_node (elim_graph g, tree node)
{
int x;
tree t;
for (x = 0; VEC_iterate (tree, g->nodes, x, t); x++)
if (t == node)
return;
VEC_safe_push (tree, heap, g->nodes, node);
}
static inline void
elim_graph_add_edge (elim_graph g, int pred, int succ)
{
VEC_safe_push (int, heap, g->edge_list, pred);
VEC_safe_push (int, heap, g->edge_list, succ);
}
static inline int
elim_graph_remove_succ_edge (elim_graph g, int node)
{
int y;
unsigned x;
for (x = 0; x < VEC_length (int, g->edge_list); x += 2)
if (VEC_index (int, g->edge_list, x) == node)
{
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;
}
#define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE) \
do { \
unsigned x_; \
int y_; \
for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
{ \
y_ = VEC_index (int, (GRAPH)->edge_list, x_); \
if (y_ != (NODE)) \
continue; \
(VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
CODE; \
} \
} while (0)
#define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE) \
do { \
unsigned x_; \
int y_; \
for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \
{ \
y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \
if (y_ != (NODE)) \
continue; \
(VAR) = VEC_index (int, (GRAPH)->edge_list, x_); \
CODE; \
} \
} while (0)
static inline void
eliminate_name (elim_graph g, tree T)
{
elim_graph_add_node (g, T);
}
static void
eliminate_build (elim_graph g, basic_block B)
{
tree phi;
tree T0, Ti;
int p0, pi;
clear_elim_graph (g);
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;
Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
if (!phi_ssa_name_p (Ti)
|| (TREE_CODE (Ti) == SSA_NAME
&& var_to_partition (g->map, Ti) == NO_PARTITION))
{
VEC_safe_push (tree, heap, g->const_copies, T0);
VEC_safe_push (tree, heap, g->const_copies, Ti);
}
else
{
Ti = var_to_partition_to_var (g->map, Ti);
if (T0 != Ti)
{
eliminate_name (g, T0);
eliminate_name (g, Ti);
p0 = var_to_partition (g->map, T0);
pi = var_to_partition (g->map, Ti);
elim_graph_add_edge (g, p0, pi);
}
}
}
}
static void
elim_forward (elim_graph g, int T)
{
int S;
SET_BIT (g->visited, T);
FOR_EACH_ELIM_GRAPH_SUCC (g, T, S,
{
if (!TEST_BIT (g->visited, S))
elim_forward (g, S);
});
VEC_safe_push (int, heap, g->stack, T);
}
static int
elim_unvisited_predecessor (elim_graph g, int T)
{
int P;
FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
{
if (!TEST_BIT (g->visited, P))
return 1;
});
return 0;
}
static void
elim_backward (elim_graph g, int T)
{
int P;
SET_BIT (g->visited, T);
FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
{
if (!TEST_BIT (g->visited, P))
{
elim_backward (g, P);
insert_copy_on_edge (g->e,
partition_to_var (g->map, P),
partition_to_var (g->map, T));
}
});
}
static void
elim_create (elim_graph g, int T)
{
tree U;
int P, S;
if (elim_unvisited_predecessor (g, T))
{
U = create_temp (partition_to_var (g->map, T));
insert_copy_on_edge (g->e, U, partition_to_var (g->map, T));
FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
{
if (!TEST_BIT (g->visited, P))
{
elim_backward (g, P);
insert_copy_on_edge (g->e, partition_to_var (g->map, P), U);
}
});
}
else
{
S = elim_graph_remove_succ_edge (g, T);
if (S != -1)
{
SET_BIT (g->visited, T);
insert_copy_on_edge (g->e,
partition_to_var (g->map, T),
partition_to_var (g->map, S));
}
}
}
static void
eliminate_phi (edge e, elim_graph g)
{
int x;
basic_block B = e->dest;
gcc_assert (VEC_length (tree, g->const_copies) == 0);
if (e->flags & EDGE_ABNORMAL)
return;
g->e = e;
eliminate_build (g, B);
if (elim_graph_size (g) != 0)
{
tree var;
sbitmap_zero (g->visited);
VEC_truncate (int, g->stack, 0);
for (x = 0; VEC_iterate (tree, g->nodes, x, var); x++)
{
int p = var_to_partition (g->map, var);
if (!TEST_BIT (g->visited, p))
elim_forward (g, p);
}
sbitmap_zero (g->visited);
while (VEC_length (int, g->stack) > 0)
{
x = VEC_pop (int, g->stack);
if (!TEST_BIT (g->visited, x))
elim_create (g, x);
}
}
while (VEC_length (tree, g->const_copies) > 0)
{
tree src, dest;
src = VEC_pop (tree, g->const_copies);
dest = VEC_pop (tree, g->const_copies);
insert_copy_on_edge (e, dest, src);
}
}
static void
print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
tree expr2, const char *str3)
{
fprintf (f, "%s", str1);
print_generic_expr (f, expr1, TDF_SLIM);
fprintf (f, "%s", str2);
print_generic_expr (f, expr2, TDF_SLIM);
fprintf (f, "%s", str3);
}
static void
print_exprs_edge (FILE *f, edge e, const char *str1, tree expr1,
const char *str2, tree expr2)
{
print_exprs (f, str1, expr1, str2, expr2, " across an abnormal edge");
fprintf (f, " from BB%d->BB%d\n", e->src->index,
e->dest->index);
}
static void
coalesce_abnormal_edges (var_map map, conflict_graph graph, root_var_p rv)
{
basic_block bb;
edge e;
tree phi, var, tmp;
int x, y, z;
edge_iterator ei;
FOR_EACH_BB (bb)
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 = PHI_CHAIN (phi))
{
var = PHI_RESULT (phi);
x = var_to_partition (map, var);
if (x == NO_PARTITION)
continue;
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);
internal_error ("SSA corruption");
}
#else
gcc_assert (phi_ssa_name_p (tmp));
#endif
y = var_to_partition (map, tmp);
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)));
internal_error ("SSA corruption");
}
#else
gcc_assert (root_var_find (rv, x) == root_var_find (rv, y));
#endif
if (x != y)
{
#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));
internal_error ("SSA corruption");
}
#else
gcc_assert (!conflict_graph_conflict_p (graph, x, y));
#endif
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);
}
}
}
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)));
}
}
}
}
}
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));
}
}
}
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));
}
}
}
}
static tree_live_info_p
coalesce_ssa_name (var_map map, int flags)
{
unsigned num, x;
sbitmap live;
root_var_p rv;
tree_live_info_p liveinfo;
conflict_graph graph;
coalesce_list_p cl = NULL;
sbitmap_iterator sbi;
if (num_var_partitions (map) <= 1)
return NULL;
liveinfo = calculate_live_on_entry (map);
calculate_live_on_exit (liveinfo);
rv = root_var_init (map);
root_var_compact (rv);
cl = create_coalesce_list (map);
coalesce_phi_operands (map, cl);
coalesce_result_decls (map, cl);
coalesce_asm_operands (map, cl);
graph = build_tree_conflict_graph (liveinfo, rv, cl);
if (cl)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Before sorting:\n");
dump_coalesce_list (dump_file, cl);
}
sort_coalesce_list (cl);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nAfter sorting:\n");
dump_coalesce_list (dump_file, cl);
}
}
root_var_decompact (rv);
num = num_var_partitions (map);
live = sbitmap_alloc (num);
sbitmap_zero (live);
for (x = 0 ; x < num; x++)
{
tree var = partition_to_var (map, x);
if (default_def (SSA_NAME_VAR (var)) == var)
SET_BIT (live, x);
}
if ((flags & SSANORM_COMBINE_TEMPS) == 0)
{
delete_tree_live_info (liveinfo);
liveinfo = NULL;
}
EXECUTE_IF_SET_IN_SBITMAP (live, 0, x, sbi)
{
tree var = root_var (rv, root_var_find (rv, x));
var_ann_t ann = var_ann (var);
if (partition_to_var (map, x) != var)
{
gcc_assert (!ann->out_of_ssa_tag);
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_exprs (dump_file, "Must coalesce ",
partition_to_var (map, x),
" with the root variable ", var, ".\n");
}
change_partition_var (map, var, x);
}
}
sbitmap_free (live);
coalesce_abnormal_edges (map, graph, rv);
if (dump_file && (dump_flags & TDF_DETAILS))
dump_var_map (dump_file, map);
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));
if (cl)
delete_coalesce_list (cl);
root_var_delete (rv);
conflict_graph_delete (graph);
return liveinfo;
}
static void
assign_vars (var_map map)
{
int x, i, num, rep;
tree t, var;
var_ann_t ann;
root_var_p rv;
rv = root_var_init (map);
if (!rv)
return;
num = num_var_partitions (map);
for (x = 0; x < num; x++)
{
var = partition_to_var (map, x);
if (TREE_CODE (var) != SSA_NAME)
{
ann = var_ann (var);
ann->out_of_ssa_tag = 1;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "partition %d has variable ", x);
print_generic_expr (dump_file, var, TDF_SLIM);
fprintf (dump_file, " assigned to it.\n");
}
}
}
num = root_var_num (rv);
for (x = 0; x < num; x++)
{
var = root_var (rv, x);
ann = var_ann (var);
for (i = root_var_first_partition (rv, x);
i != ROOT_VAR_NONE;
i = root_var_next_partition (rv, i))
{
t = partition_to_var (map, i);
if (t == var || TREE_CODE (t) != SSA_NAME)
continue;
rep = var_to_partition (map, t);
if (!ann->out_of_ssa_tag)
{
if (dump_file && (dump_flags & TDF_DETAILS))
print_exprs (dump_file, "", t, " --> ", var, "\n");
change_partition_var (map, var, rep);
continue;
}
if (dump_file && (dump_flags & TDF_DETAILS))
print_exprs (dump_file, "", t, " not coalesced with ", var,
"");
var = create_temp (t);
change_partition_var (map, var, rep);
ann = var_ann (var);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " --> New temp: '");
print_generic_expr (dump_file, var, TDF_SLIM);
fprintf (dump_file, "'\n");
}
}
}
root_var_delete (rv);
}
static inline bool
replace_use_variable (var_map map, use_operand_p p, tree *expr)
{
tree new_var;
tree var = USE_FROM_PTR (p);
if (expr)
{
int version = SSA_NAME_VERSION (var);
if (expr[version])
{
tree new_expr = TREE_OPERAND (expr[version], 1);
SET_USE (p, new_expr);
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;
}
static inline bool
replace_def_variable (var_map map, def_operand_p def_p, tree *expr)
{
tree new_var;
tree var = DEF_FROM_PTR (def_p);
if (expr)
{
int version = SSA_NAME_VERSION (var);
if (expr[version])
{
tree new_expr = TREE_OPERAND (expr[version], 1);
SET_DEF (def_p, new_expr);
TREE_OPERAND (expr[version], 1) = NULL_TREE;
return true;
}
}
new_var = var_to_partition_to_var (map, var);
if (new_var)
{
SET_DEF (def_p, new_var);
set_is_used (new_var);
return true;
}
return false;
}
static void
eliminate_virtual_phis (void)
{
basic_block bb;
tree phi, next;
FOR_EACH_BB (bb)
{
for (phi = phi_nodes (bb); phi; phi = next)
{
next = PHI_CHAIN (phi);
if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
{
#ifdef ENABLE_CHECKING
int i;
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
tree arg = PHI_ARG_DEF (phi, i);
if (TREE_CODE (arg) == SSA_NAME
&& is_gimple_reg (SSA_NAME_VAR (arg)))
{
fprintf (stderr, "Argument of PHI is not virtual (");
print_generic_expr (stderr, arg, TDF_SLIM);
fprintf (stderr, "), but the result is :");
print_generic_stmt (stderr, phi, TDF_SLIM);
internal_error ("SSA corruption");
}
}
#endif
remove_phi_node (phi, NULL_TREE);
}
}
}
}
static void
coalesce_vars (var_map map, tree_live_info_p liveinfo)
{
basic_block bb;
type_var_p tv;
tree var;
unsigned x, p, p2;
coalesce_list_p cl;
conflict_graph graph;
cl = create_coalesce_list (map);
for (x = 0; x < num_var_partitions (map); x++)
{
var = partition_to_var (map, x);
p = var_to_partition (map, var);
if (p != x)
live_merge_and_clear (liveinfo, p, x);
}
FOR_EACH_BB (bb)
{
tree phi, arg;
unsigned p;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
p = var_to_partition (map, PHI_RESULT (phi));
if (p == (unsigned)NO_PARTITION)
continue;
make_live_on_entry (liveinfo, bb, p);
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 == (unsigned)NO_PARTITION)
continue;
if (p != p2)
{
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)));
}
}
}
}
calculate_live_on_exit (liveinfo);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Live range info for variable memory coalescing.\n");
dump_live_info (dump_file, liveinfo, LIVEDUMP_ALL);
fprintf (dump_file, "Coalesce list from phi nodes:\n");
dump_coalesce_list (dump_file, cl);
}
tv = type_var_init (map);
if (dump_file)
type_var_dump (dump_file, tv);
type_var_compact (tv);
if (dump_file)
type_var_dump (dump_file, tv);
graph = build_tree_conflict_graph (liveinfo, tv, cl);
type_var_decompact (tv);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "type var list now looks like:n");
type_var_dump (dump_file, tv);
fprintf (dump_file, "Coalesce list after conflict graph build:\n");
dump_coalesce_list (dump_file, cl);
}
sort_coalesce_list (cl);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Coalesce list after sorting:\n");
dump_coalesce_list (dump_file, cl);
}
coalesce_tpa_members (tv, graph, map, cl,
((dump_flags & TDF_DETAILS) ? dump_file : NULL));
type_var_delete (tv);
delete_coalesce_list (cl);
}
typedef struct value_expr_d
{
int value;
struct value_expr_d *next;
} *value_expr_p;
typedef struct temp_expr_table_d
{
var_map map;
void **version_info;
bitmap *expr_vars;
value_expr_p *partition_dep_list;
bitmap replaceable;
bool saw_replaceable;
int virtual_partition;
bitmap partition_in_use;
value_expr_p free_list;
value_expr_p pending_dependence;
} *temp_expr_table_p;
#define VIRTUAL_PARTITION(table) (table->virtual_partition)
static temp_expr_table_p new_temp_expr_table (var_map);
static tree *free_temp_expr_table (temp_expr_table_p);
static inline value_expr_p new_value_expr (temp_expr_table_p);
static inline void free_value_expr (temp_expr_table_p, value_expr_p);
static inline value_expr_p find_value_in_list (value_expr_p, int,
value_expr_p *);
static inline void add_value_to_list (temp_expr_table_p, value_expr_p *, int);
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_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);
static inline void kill_expr (temp_expr_table_p, int, bool);
static inline void kill_virtual_exprs (temp_expr_table_p, bool);
static void find_replaceable_in_bb (temp_expr_table_p, basic_block);
static tree *find_replaceable_exprs (var_map);
static void dump_replaceable_exprs (FILE *, tree *);
static temp_expr_table_p
new_temp_expr_table (var_map map)
{
temp_expr_table_p t;
t = XNEW (struct temp_expr_table_d);
t->map = map;
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_ALLOC (NULL);
t->partition_in_use = BITMAP_ALLOC (NULL);
t->saw_replaceable = false;
t->virtual_partition = num_var_partitions (map);
t->free_list = NULL;
t->pending_dependence = NULL;
return t;
}
static tree *
free_temp_expr_table (temp_expr_table_p t)
{
value_expr_p p;
tree *ret = NULL;
unsigned i;
#ifdef ENABLE_CHECKING
unsigned x;
for (x = 0; x <= num_var_partitions (t->map); x++)
gcc_assert (!t->partition_dep_list[x]);
#endif
while ((p = t->free_list))
{
t->free_list = p->next;
free (p);
}
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)
ret = (tree *)t->version_info;
else
free (t->version_info);
free (t);
return ret;
}
static inline value_expr_p
new_value_expr (temp_expr_table_p table)
{
value_expr_p p;
if (table->free_list)
{
p = table->free_list;
table->free_list = p->next;
}
else
p = (value_expr_p) xmalloc (sizeof (struct value_expr_d));
return p;
}
static inline void
free_value_expr (temp_expr_table_p table, value_expr_p p)
{
p->next = table->free_list;
table->free_list = p;
}
static inline value_expr_p
find_value_in_list (value_expr_p list, int value, value_expr_p *last_ptr)
{
value_expr_p curr;
value_expr_p last = NULL;
for (curr = list; curr; last = curr, curr = curr->next)
{
if (curr->value == value)
break;
}
if (last_ptr)
*last_ptr = last;
return curr;
}
static inline void
add_value_to_list (temp_expr_table_p tab, value_expr_p *list, int value)
{
value_expr_p info;
if (!find_value_in_list (*list, value, NULL))
{
info = new_value_expr (tab);
info->value = value;
info->next = *list;
*list = info;
}
}
static inline void
add_info_to_list (temp_expr_table_p tab, value_expr_p *list, value_expr_p info)
{
if (find_value_in_list (*list, info->value, NULL))
free_value_expr (tab, info);
else
{
info->next = *list;
*list = info;
}
}
static value_expr_p
remove_value_from_list (value_expr_p *list, int value)
{
value_expr_p info, last;
info = find_value_in_list (*list, value, &last);
if (!info)
return NULL;
if (!last)
*list = info->next;
else
last->next = info->next;
return info;
}
static void
add_dependence (temp_expr_table_p tab, int version, tree var)
{
int i, x;
value_expr_p info;
i = SSA_NAME_VERSION (var);
if (bitmap_bit_p (tab->replaceable, i))
{
while ((info = tab->pending_dependence))
{
tab->pending_dependence = info->next;
x = info->value;
info->value = version;
add_info_to_list (tab, &(tab->partition_dep_list[x]), info);
add_value_to_list (tab,
(value_expr_p *)&(tab->version_info[version]), x);
bitmap_set_bit (tab->partition_in_use, x);
}
}
else
{
i = var_to_partition (tab->map, var);
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);
bitmap_set_bit (tab->partition_in_use, i);
}
}
static bool
check_replaceable (temp_expr_table_p tab, tree stmt)
{
tree var, def, basevar;
int version;
var_map map = tab->map;
ssa_op_iter iter;
tree call_expr;
bitmap def_vars, use_vars;
if (TREE_CODE (stmt) != MODIFY_EXPR)
return false;
def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
if (!def)
return false;
if (version_ref_count (map, def) != 1)
return false;
if (!(ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF))))
return false;
if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
return false;
if (TREE_CODE (TREE_OPERAND (stmt, 1)) == VAR_DECL
&& DECL_HARD_REGISTER (TREE_OPERAND (stmt, 1)))
return false;
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);
def_vars = BITMAP_ALLOC (NULL);
bitmap_set_bit (def_vars, DECL_UID (basevar));
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
{
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 (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
{
add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]),
VIRTUAL_PARTITION (tab));
add_value_to_list (tab,
&(tab->partition_dep_list[VIRTUAL_PARTITION (tab)]),
version);
bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab));
}
return true;
}
static void
finish_expr (temp_expr_table_p tab, int version, bool replace)
{
value_expr_p info, tmp;
int partition;
for (info = (value_expr_p) tab->version_info[version]; info; info = tmp)
{
partition = info->value;
gcc_assert (tab->partition_dep_list[partition]);
tmp = remove_value_from_list (&(tab->partition_dep_list[partition]),
version);
gcc_assert (tmp);
free_value_expr (tab, tmp);
if (!(tab->partition_dep_list[partition]) && replace)
bitmap_clear_bit (tab->partition_in_use, partition);
tmp = info->next;
if (!replace)
free_value_expr (tab, info);
}
if (replace)
{
tab->saw_replaceable = true;
bitmap_set_bit (tab->replaceable, version);
}
else
{
gcc_assert (!bitmap_bit_p (tab->replaceable, version));
tab->version_info[version] = NULL;
}
}
static void
mark_replaceable (temp_expr_table_p tab, tree var)
{
value_expr_p info;
int version = SSA_NAME_VERSION (var);
finish_expr (tab, version, true);
if (tab->version_info[version])
{
info = (value_expr_p) tab->version_info[version];
for ( ; info->next; info = info->next)
continue;
info->next = tab->pending_dependence;
tab->pending_dependence = (value_expr_p)tab->version_info[version];
}
tab->version_info[version] = SSA_NAME_DEF_STMT (var);
}
static inline void
kill_expr (temp_expr_table_p tab, int partition, bool clear_bit)
{
value_expr_p ptr;
while ((ptr = tab->partition_dep_list[partition]) != NULL)
finish_expr (tab, ptr->value, false);
if (clear_bit)
bitmap_clear_bit (tab->partition_in_use, partition);
}
static inline void
kill_virtual_exprs (temp_expr_table_p tab, bool clear_bit)
{
kill_expr (tab, VIRTUAL_PARTITION (tab), clear_bit);
}
static void
find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
{
block_stmt_iterator bsi;
tree stmt, def, use;
stmt_ann_t ann;
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))
{
stmt = bsi_stmt (bsi);
ann = stmt_ann (stmt);
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
{
unsigned ver = SSA_NAME_VERSION (use);
if (tab->version_info[ver])
{
bool same_root_var = false;
ssa_op_iter iter2;
bitmap vars = tab->expr_vars[ver];
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;
}
}
if (!ann->has_volatile_ops && !same_root_var)
mark_replaceable (tab, use);
else
finish_expr (tab, ver, false);
}
}
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
{
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);
while ((p = tab->pending_dependence))
{
tab->pending_dependence = p->next;
free_value_expr (tab, p);
}
if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
kill_virtual_exprs (tab, true);
}
}
static tree *
find_replaceable_exprs (var_map map)
{
basic_block bb;
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, bi)
{
kill_expr (table, i, false);
}
}
ret = free_temp_expr_table (table);
return ret;
}
static void
dump_replaceable_exprs (FILE *f, tree *expr)
{
tree stmt, var;
int x;
fprintf (f, "\nReplacing Expressions\n");
for (x = 0; x < (int)num_ssa_names + 1; x++)
if (expr[x])
{
stmt = expr[x];
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);
fprintf (f, "\n");
}
fprintf (f, "\n");
}
static void
rewrite_trees (var_map map, tree *values)
{
elim_graph g;
basic_block bb;
block_stmt_iterator si;
edge e;
tree phi;
bool changed;
#ifdef ENABLE_CHECKING
FOR_EACH_BB (bb)
{
tree phi;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi));
if (T0 == NULL_TREE)
{
int i;
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
tree arg = PHI_ARG_DEF (phi, i);
if (TREE_CODE (arg) == SSA_NAME
&& var_to_partition (map, arg) != NO_PARTITION)
{
fprintf (stderr, "Argument of PHI is in a partition :(");
print_generic_expr (stderr, arg, TDF_SLIM);
fprintf (stderr, "), but the result is not :");
print_generic_stmt (stderr, phi, TDF_SLIM);
internal_error ("SSA corruption");
}
}
}
}
}
#endif
g = new_elim_graph (map->num_partitions);
g->map = map;
FOR_EACH_BB (bb)
{
for (si = bsi_start (bb); !bsi_end_p (si); )
{
tree stmt = bsi_stmt (si);
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;
ann = stmt_ann (stmt);
changed = false;
if (TREE_CODE (stmt) == MODIFY_EXPR
&& (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME))
is_copy = true;
copy_use_p = NULL_USE_OPERAND_P;
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
{
if (replace_use_variable (map, use_p, values))
changed = true;
copy_use_p = use_p;
num_uses++;
}
if (num_uses != 1)
is_copy = false;
def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
if (def_p != NULL)
{
if (values && values[SSA_NAME_VERSION (DEF_FROM_PTR (def_p))])
remove = true;
else
{
if (replace_def_variable (map, def_p, NULL))
changed = true;
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;
}
}
}
else
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
if (replace_def_variable (map, def_p, NULL))
changed = true;
if (remove)
bsi_remove (&si, true);
else
bsi_next (&si);
}
phi = phi_nodes (bb);
if (phi)
{
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->preds)
eliminate_phi (e, g);
}
}
delete_elim_graph (g);
}
DEF_VEC_ALLOC_P(edge,heap);
static VEC(edge,heap) *edge_leader;
static VEC(tree,heap) *stmt_list;
static bitmap leader_has_match = NULL;
static edge leader_match = NULL;
static bool
same_stmt_list_p (edge e)
{
return (e->aux == (PTR) leader_match) ? true : false;
}
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;
}
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;
}
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);
}
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);
}
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;
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;
}
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);
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 (count < 2)
{
if (single_edge)
bsi_commit_one_edge_insert (single_edge, NULL);
return;
}
#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
have_opportunity = false;
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (PENDING_STMT (e))
{
bool found = false;
for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
{
if (identical_stmt_lists_p (leader, e))
{
PENDING_STMT (e) = NULL;
e->aux = leader;
bitmap_set_bit (leader_has_match, x);
have_opportunity = found = true;
break;
}
}
if (!found)
{
VEC_safe_push (edge, heap, edge_leader, e);
VEC_safe_push (tree, heap, stmt_list, PENDING_STMT (e));
}
}
}
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 (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;
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;
}
else
{
PENDING_STMT (leader) = VEC_index (tree, stmt_list, 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);
}
static void
perform_edge_inserts (void)
{
basic_block bb;
if (dump_file)
fprintf(dump_file, "Analyzing Edge Insertions.\n");
free_dominance_info (CDI_DOMINATORS);
free_dominance_info (CDI_POST_DOMINATORS);
init_analyze_edges_for_bb ();
FOR_EACH_BB (bb)
analyze_edges_for_bb (bb);
analyze_edges_for_bb (EXIT_BLOCK_PTR);
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
}
static void
remove_ssa_form (var_map map, int flags)
{
tree_live_info_p liveinfo;
basic_block bb;
tree phi, next;
tree *values = NULL;
if ((flags & SSANORM_COMBINE_TEMPS) == 0)
compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
else
compact_var_map (map, VARMAP_NORMAL);
if (dump_file && (dump_flags & TDF_DETAILS))
dump_var_map (dump_file, map);
liveinfo = coalesce_ssa_name (map, flags);
if ((flags & SSANORM_COMBINE_TEMPS) == 0)
compact_var_map (map, VARMAP_NORMAL);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "After Coalescing:\n");
dump_var_map (dump_file, map);
}
if (flags & SSANORM_PERFORM_TER)
{
values = find_replaceable_exprs (map);
if (values && dump_file && (dump_flags & TDF_DETAILS))
dump_replaceable_exprs (dump_file, values);
}
assign_vars (map);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "After Root variable replacement:\n");
dump_var_map (dump_file, map);
}
if ((flags & SSANORM_COMBINE_TEMPS) && liveinfo)
{
coalesce_vars (map, liveinfo);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "After variable memory coalescing:\n");
dump_var_map (dump_file, map);
}
}
if (liveinfo)
delete_tree_live_info (liveinfo);
rewrite_trees (map, values);
if (values)
free (values);
FOR_EACH_BB (bb)
{
for (phi = phi_nodes (bb); phi; phi = next)
{
next = PHI_CHAIN (phi);
remove_phi_node (phi, NULL_TREE);
}
}
fini_ssa_operands ();
perform_edge_inserts ();
}
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 ((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);
if (last && stmt_ends_bb_p (last))
{
if (TREE_CODE (arg) == SSA_NAME
&& SSA_NAME_DEF_STMT (arg) == last)
continue;
}
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;
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);
}
}
}
}
}
static unsigned int
rewrite_out_of_ssa (void)
{
var_map map;
int var_flags = 0;
int ssa_flags = 0;
insert_backedge_copies ();
if (!flag_tree_live_range_split)
ssa_flags |= SSANORM_COALESCE_PARTITIONS;
eliminate_virtual_phis ();
if (dump_file && (dump_flags & TDF_DETAILS))
dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
if (flag_tree_ter && !flag_mudflap)
var_flags = SSA_VAR_MAP_REF_COUNT;
map = create_ssa_var_map (var_flags);
if (flag_tree_combine_temps)
ssa_flags |= SSANORM_COMBINE_TEMPS;
if (flag_tree_ter && !flag_mudflap)
ssa_flags |= SSANORM_PERFORM_TER;
remove_ssa_form (map, ssa_flags);
if (dump_file && (dump_flags & TDF_DETAILS))
dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
delete_var_map (map);
in_ssa_p = false;
return 0;
}
struct tree_opt_pass pass_del_ssa =
{
"optimized",
NULL,
rewrite_out_of_ssa,
NULL,
NULL,
0,
TV_TREE_SSA_TO_NORMAL,
PROP_cfg | PROP_ssa | PROP_alias,
0,
PROP_ssa,
TODO_verify_ssa | TODO_verify_flow
| TODO_verify_stmts,
TODO_dump_func
| TODO_ggc_collect
| TODO_remove_unused_locals,
0
};