#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 "errors.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"
#define SSANORM_PERFORM_TER 0x1
#define SSANORM_COMBINE_TEMPS 0x2
#define SSANORM_REMOVE_ALL_PHIS 0x4
#define SSANORM_COALESCE_PARTITIONS 0x8
#define SSANORM_USE_COALESCE_LIST 0x10
typedef struct _elim_graph {
int size;
varray_type nodes;
varray_type edge_list;
sbitmap visited;
varray_type stack;
var_map map;
edge e;
varray_type 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, int);
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 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);
DECL_ARTIFICIAL (tmp) = DECL_ARTIFICIAL (t);
add_referenced_tmp_var (tmp);
var_ann (tmp)->type_mem_tag = var_ann (t)->type_mem_tag;
if (is_call_clobbered (t))
mark_call_clobbered (tmp);
return tmp;
}
static void
insert_copy_on_edge (edge e, tree dest, tree src)
{
tree copy;
copy = build (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));
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->visited = sbitmap_alloc (size);
return g;
}
static inline void
clear_elim_graph (elim_graph g)
{
VARRAY_POP_ALL (g->nodes);
VARRAY_POP_ALL (g->edge_list);
}
static inline void
delete_elim_graph (elim_graph g)
{
sbitmap_free (g->visited);
free (g);
}
static inline int
elim_graph_size (elim_graph g)
{
return VARRAY_ACTIVE_SIZE (g->nodes);
}
static inline void
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)
return;
VARRAY_PUSH_TREE (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);
}
static inline int
elim_graph_remove_succ_edge (elim_graph g, int node)
{
int y;
unsigned x;
for (x = 0; x < VARRAY_ACTIVE_SIZE (g->edge_list); x += 2)
if (VARRAY_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;
return y;
}
return -1;
}
#define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE) \
do { \
unsigned x_; \
int y_; \
for (x_ = 0; x_ < VARRAY_ACTIVE_SIZE ((GRAPH)->edge_list); x_ += 2) \
{ \
y_ = VARRAY_INT ((GRAPH)->edge_list, x_); \
if (y_ != (NODE)) \
continue; \
(VAR) = VARRAY_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_ < VARRAY_ACTIVE_SIZE ((GRAPH)->edge_list); x_ += 2) \
{ \
y_ = VARRAY_INT ((GRAPH)->edge_list, x_ + 1); \
if (y_ != (NODE)) \
continue; \
(VAR) = VARRAY_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, int i)
{
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;
if (PHI_ARG_EDGE (phi, i) == g->e)
Ti = PHI_ARG_DEF (phi, i);
else
{
pi = phi_arg_from_edge (phi, g->e);
gcc_assert (pi != -1);
Ti = PHI_ARG_DEF (phi, pi);
}
if (!phi_ssa_name_p (Ti)
|| (TREE_CODE (Ti) == SSA_NAME
&& var_to_partition (g->map, Ti) == NO_PARTITION))
{
VARRAY_PUSH_TREE (g->const_copies, T0);
VARRAY_PUSH_TREE (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);
});
VARRAY_PUSH_INT (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, int i, elim_graph g)
{
int num_nodes = 0;
int x;
basic_block B = e->dest;
gcc_assert (i != -1);
gcc_assert (VARRAY_ACTIVE_SIZE (g->const_copies) == 0);
if (e->flags & EDGE_ABNORMAL)
return;
num_nodes = num_var_partitions (g->map);
g->e = e;
eliminate_build (g, B, i);
if (elim_graph_size (g) != 0)
{
sbitmap_zero (g->visited);
VARRAY_POP_ALL (g->stack);
for (x = 0; x < elim_graph_size (g); 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)
{
x = VARRAY_TOP_INT (g->stack);
VARRAY_POP (g->stack);
if (!TEST_BIT (g->visited, x))
elim_create (g, x);
}
}
while (VARRAY_ACTIVE_SIZE (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);
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;
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;
y = phi_arg_from_edge (phi, e);
gcc_assert (y != -1);
tmp = PHI_ARG_DEF (phi, y);
#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);
}
#ifdef ENABLE_CHECKING
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));
internal_error ("SSA corruption");
}
#else
gcc_assert (var_union (map, var, tmp) != NO_PARTITION);
#endif
conflict_graph_merge_regs (graph, x, y);
}
}
}
static tree_live_info_p
coalesce_ssa_name (var_map map, int flags)
{
int num, x, i;
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;
if (num_var_partitions (map) <= 1)
return NULL;
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);
root_var_compact (rv);
if (flags & SSANORM_USE_COALESCE_LIST)
{
cl = create_coalesce_list (map);
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);
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);
}
}
}
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);
}
}
}
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);
live = sbitmap_alloc (num_var_partitions (map));
sbitmap_zero (live);
num = num_var_partitions (map);
for (x = 0 ; x < num; x++)
{
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,
{
var = root_var (rv, root_var_find (rv, x));
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);
if (flags & SSANORM_USE_COALESCE_LIST)
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, bb);
}
}
}
}
static void
coalesce_vars (var_map map, tree_live_info_p liveinfo)
{
basic_block bb;
type_var_p tv;
tree var;
int 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;
int p;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
p = var_to_partition (map, PHI_RESULT (phi));
if (p == NO_PARTITION)
continue;
make_live_on_entry (liveinfo, bb, p);
for (x = 0; x < 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)
continue;
if (p != p2)
add_coalesce (cl, p, p2, 1);
}
}
}
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;
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_dependance (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 = (temp_expr_table_p) xmalloc (sizeof (struct temp_expr_table_d));
t->map = map;
t->version_info = xcalloc (num_ssa_names + 1, sizeof (void *));
t->partition_dep_list = xcalloc (num_var_partitions (map) + 1,
sizeof (value_expr_p));
t->replaceable = BITMAP_XMALLOC ();
t->partition_in_use = BITMAP_XMALLOC ();
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;
#ifdef ENABLE_CHECKING
int 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_XFREE (t->partition_in_use);
BITMAP_XFREE (t->replaceable);
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_dependance (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)
{
stmt_ann_t ann;
vuse_optype vuseops;
def_optype defs;
use_optype uses;
tree var, def;
int num_use_ops, version;
var_map map = tab->map;
ssa_op_iter iter;
if (TREE_CODE (stmt) != MODIFY_EXPR)
return false;
ann = stmt_ann (stmt);
defs = DEF_OPS (ann);
if (NUM_DEFS (defs) != 1)
return false;
def = DEF_OP (defs, 0);
if (version_ref_count (map, def) != 1)
return false;
if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) != 0)
return false;
if (NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) != 0)
return false;
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);
if (num_use_ops == 0 && NUM_VUSES (vuseops) == 0)
return false;
version = SSA_NAME_VERSION (def);
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
{
add_dependance (tab, version, var);
}
if (NUM_VUSES (vuseops) != 0)
{
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;
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 (def, stmt, iter, SSA_OP_USE)
{
if (tab->version_info[SSA_NAME_VERSION (def)])
{
if (!ann->has_volatile_ops)
mark_replaceable (tab, def);
else
finish_expr (tab, SSA_NAME_VERSION (def), 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 (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0)
kill_virtual_exprs (tab, true);
if (NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0)
kill_virtual_exprs (tab, true);
}
}
static tree *
find_replaceable_exprs (var_map map)
{
basic_block bb;
int 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 = DEF_OP (STMT_DEF_OPS (stmt), 0);
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 tree
discover_nonconstant_array_refs_r (tree * tp, int *walk_subtrees,
void *data ATTRIBUTE_UNUSED)
{
tree t = *tp;
if (IS_TYPE_OR_DECL_P (t))
*walk_subtrees = 0;
else if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
{
while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
&& is_gimple_min_invariant (TREE_OPERAND (t, 1))
&& (!TREE_OPERAND (t, 2)
|| is_gimple_min_invariant (TREE_OPERAND (t, 2))))
|| (TREE_CODE (t) == COMPONENT_REF
&& (!TREE_OPERAND (t,2)
|| is_gimple_min_invariant (TREE_OPERAND (t, 2))))
|| TREE_CODE (t) == BIT_FIELD_REF
|| TREE_CODE (t) == REALPART_EXPR
|| TREE_CODE (t) == IMAGPART_EXPR
|| TREE_CODE (t) == VIEW_CONVERT_EXPR
|| TREE_CODE (t) == NOP_EXPR
|| TREE_CODE (t) == CONVERT_EXPR)
t = TREE_OPERAND (t, 0);
if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
{
t = get_base_address (t);
if (t && DECL_P (t))
TREE_ADDRESSABLE (t) = 1;
}
*walk_subtrees = 0;
}
return NULL_TREE;
}
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);
}
}
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); )
{
size_t num_uses, num_defs;
use_optype uses;
def_optype defs;
tree stmt = bsi_stmt (si);
use_operand_p use_p;
def_operand_p def_p;
int remove = 0, is_copy = 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;
uses = USE_OPS (ann);
num_uses = NUM_USES (uses);
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
{
if (replace_use_variable (map, use_p, values))
changed = true;
}
defs = DEF_OPS (ann);
num_defs = NUM_DEFS (defs);
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)
{
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
{
if (replace_def_variable (map, def_p, NULL))
changed = true;
if (is_copy
&& num_uses == 1
&& (DEF_FROM_PTR (def_p) == USE_OP (uses, 0)))
remove = 1;
}
if (changed & !remove)
modify_stmt (stmt);
}
if (remove)
bsi_remove (&si);
else
bsi_next (&si);
}
phi = phi_nodes (bb);
if (phi)
{
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->preds)
eliminate_phi (e, phi_arg_from_edge (phi, e), g);
}
}
delete_elim_graph (g);
bsi_commit_edge_inserts (NULL);
}
static void
remove_ssa_form (FILE *dump, 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 ((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);
if ((flags & SSANORM_REMOVE_ALL_PHIS)
|| var_to_partition (map, PHI_RESULT (phi)) != NO_PARTITION)
remove_phi_node (phi, NULL_TREE, bb);
}
}
dump_file = save;
}
static void
rewrite_out_of_ssa (void)
{
var_map map;
int var_flags = 0;
int ssa_flags = (SSANORM_REMOVE_ALL_PHIS | SSANORM_USE_COALESCE_LIST);
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 (dump_file, map, ssa_flags);
if (dump_file && (dump_flags & TDF_DETAILS))
dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
cfg_remove_useless_stmts ();
delete_var_map (map);
discover_nonconstant_array_refs ();
}
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,
0
};