#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 "basic-block.h"
#include "output.h"
#include "errors.h"
#include "expr.h"
#include "function.h"
#include "diagnostic.h"
#include "timevar.h"
#include "cfgloop.h"
#include "tree-dump.h"
#include "tree-flow.h"
#include "domwalk.h"
#include "real.h"
#include "tree-pass.h"
#include "langhooks.h"
static htab_t avail_exprs;
struct expr_hash_elt
{
tree lhs;
tree rhs;
stmt_ann_t ann;
hashval_t hash;
};
static varray_type const_and_copies;
static bitmap nonzero_vars;
static bool cfg_altered;
struct opt_stats_d
{
long num_stmts;
long num_exprs_considered;
long num_re;
};
struct vrp_element
{
tree low;
tree high;
tree cond;
basic_block bb;
};
static struct opt_stats_d opt_stats;
static GTY(()) varray_type redirection_edges;
static varray_type vrp_data;
struct dom_walk_block_data
{
varray_type avail_exprs;
varray_type const_and_copies;
varray_type nonzero_vars;
varray_type stmts_to_rescan;
varray_type vrp_variables;
varray_type block_defs;
};
struct eq_expr_value
{
tree src;
tree dst;
};
static void optimize_stmt (struct dom_walk_data *,
basic_block bb,
block_stmt_iterator);
static inline tree get_value_for (tree, varray_type table);
static inline void set_value_for (tree, tree, varray_type table);
static tree lookup_avail_expr (tree, varray_type *, bool);
static struct eq_expr_value get_eq_expr_value (tree, int, varray_type *,
basic_block, varray_type *);
static hashval_t avail_expr_hash (const void *);
static int avail_expr_eq (const void *, const void *);
static void htab_statistics (FILE *, htab_t);
static void record_cond (tree, tree, varray_type *);
static void record_const_or_copy (tree, tree, varray_type *);
static void record_equality (tree, tree, varray_type *);
static tree update_rhs_and_lookup_avail_expr (tree, tree, varray_type *,
stmt_ann_t, bool);
static tree simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *,
tree, stmt_ann_t, int);
static tree simplify_cond_and_lookup_avail_expr (tree, varray_type *,
stmt_ann_t, int);
static tree simplify_switch_and_lookup_avail_expr (tree, varray_type *,
stmt_ann_t, int);
static tree find_equivalent_equality_comparison (tree);
static void record_range (tree, basic_block, varray_type *);
static bool extract_range_from_cond (tree, tree *, tree *, int *);
static void record_equivalences_from_phis (struct dom_walk_data *, basic_block);
static void record_equivalences_from_incoming_edge (struct dom_walk_data *,
basic_block);
static bool eliminate_redundant_computations (struct dom_walk_data *,
tree, stmt_ann_t);
static void record_equivalences_from_stmt (tree, varray_type *, varray_type *,
int, stmt_ann_t);
static void thread_across_edge (struct dom_walk_data *, edge);
static void dom_opt_finalize_block (struct dom_walk_data *, basic_block);
static void dom_opt_initialize_block_local_data (struct dom_walk_data *,
basic_block, bool);
static void dom_opt_initialize_block (struct dom_walk_data *, basic_block);
static void cprop_into_phis (struct dom_walk_data *, basic_block);
static void remove_local_expressions_from_table (varray_type locals,
unsigned limit,
htab_t table);
static void restore_vars_to_original_value (varray_type locals,
unsigned limit,
varray_type table);
static void restore_currdefs_to_original_value (varray_type locals,
unsigned limit);
static void register_definitions_for_stmt (stmt_ann_t, varray_type *);
static void redirect_edges_and_update_ssa_graph (varray_type);
static tree
local_fold (tree t)
{
t = fold (t);
STRIP_MAIN_TYPE_NOPS (t);
STRIP_USELESS_TYPE_CONVERSION (t);
return t;
}
static inline tree
get_value_for (tree var, varray_type table)
{
return VARRAY_TREE (table, SSA_NAME_VERSION (var));
}
static inline void
set_value_for (tree var, tree value, varray_type table)
{
VARRAY_TREE (table, SSA_NAME_VERSION (var)) = value;
}
static void
redirect_edges_and_update_ssa_graph (varray_type redirection_edges)
{
basic_block tgt, bb;
tree phi;
unsigned int i;
size_t old_num_referenced_vars = num_referenced_vars;
bitmap virtuals_to_rename = BITMAP_XMALLOC ();
for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
{
block_stmt_iterator bsi;
edge e;
basic_block tgt;
tree phi;
e = VARRAY_EDGE (redirection_edges, i);
tgt = VARRAY_EDGE (redirection_edges, i + 1)->dest;
for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
{
tree result = SSA_NAME_VAR (PHI_RESULT (phi));
if (is_gimple_reg (PHI_RESULT (phi)))
bitmap_set_bit (vars_to_rename, var_ann (result)->uid);
else
bitmap_set_bit (virtuals_to_rename, var_ann (result)->uid);
}
for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
{
unsigned int j;
def_optype defs;
vdef_optype vdefs;
tree stmt = bsi_stmt (bsi);
stmt_ann_t ann = stmt_ann (stmt);
if (TREE_CODE (stmt) == COND_EXPR)
break;
get_stmt_operands (stmt);
defs = DEF_OPS (ann);
for (j = 0; j < NUM_DEFS (defs); j++)
{
tree op = SSA_NAME_VAR (DEF_OP (defs, j));
bitmap_set_bit (vars_to_rename, var_ann (op)->uid);
}
vdefs = VDEF_OPS (ann);
for (j = 0; j < NUM_VDEFS (vdefs); j++)
{
tree op = VDEF_RESULT (vdefs, j);
bitmap_set_bit (virtuals_to_rename, var_ann (op)->uid);
}
}
for (phi = phi_nodes (tgt); phi; phi = TREE_CHAIN (phi))
{
tree result = SSA_NAME_VAR (PHI_RESULT (phi));
if (is_gimple_reg (PHI_RESULT (phi)))
bitmap_set_bit (vars_to_rename, var_ann (result)->uid);
else
bitmap_set_bit (virtuals_to_rename, var_ann (result)->uid);
}
}
if (bitmap_first_set_bit (vars_to_rename) >= 0)
rewrite_vars_out_of_ssa (vars_to_rename);
for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
{
edge e = VARRAY_EDGE (redirection_edges, i);
tree last = last_stmt (e->dest);
if (last
&& TREE_CODE (last) != COND_EXPR
&& TREE_CODE (last) != SWITCH_EXPR)
{
e = e->dest->succ;
#ifdef ENABLE_CHECKING
if (e->succ_next)
abort ();
#endif
VARRAY_EDGE (redirection_edges, i) = e;
}
}
if (num_referenced_vars != old_num_referenced_vars)
{
for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
{
block_stmt_iterator bsi;
edge e;
e = VARRAY_EDGE (redirection_edges, i);
for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
if (IS_EMPTY_STMT (stmt)
|| TREE_CODE (stmt) == LABEL_EXPR)
continue;
if (TREE_CODE (stmt) == COND_EXPR)
break;
VARRAY_EDGE (redirection_edges, i) = NULL;
VARRAY_EDGE (redirection_edges, i + 1) = NULL;
break;
}
}
}
for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
{
basic_block src;
edge e;
e = VARRAY_EDGE (redirection_edges, i);
if (!e)
continue;
tgt = VARRAY_EDGE (redirection_edges, i + 1)->dest;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
e->src->index, e->dest->index, tgt->index);
src = e->src;
e = redirect_edge_and_branch (e, tgt);
PENDING_STMT (e) = NULL_TREE;
free_dominance_info (CDI_DOMINATORS);
if ((dump_file && (dump_flags & TDF_DETAILS))
&& e->src != src)
fprintf (dump_file, " basic block %d created\n",
e->src->index);
cfg_altered = true;
}
VARRAY_CLEAR (redirection_edges);
for (i = old_num_referenced_vars; i < num_referenced_vars; i++)
{
bitmap_set_bit (vars_to_rename, i);
var_ann (referenced_var (i))->out_of_ssa_tag = 0;
}
bitmap_a_or_b (vars_to_rename, vars_to_rename, virtuals_to_rename);
FOR_EACH_BB (bb)
{
tree next;
for (phi = phi_nodes (bb); phi; phi = next)
{
tree result = PHI_RESULT (phi);
next = TREE_CHAIN (phi);
if (bitmap_bit_p (virtuals_to_rename,
var_ann (SSA_NAME_VAR (result))->uid))
remove_phi_node (phi, NULL, bb);
}
}
BITMAP_XFREE (virtuals_to_rename);
}
static void
tree_ssa_dominator_optimize (void)
{
basic_block bb;
struct dom_walk_data walk_data;
struct loops *loops;
unsigned int i;
loops = loop_optimizer_init (NULL);
for (i = 0; i < num_referenced_vars; i++)
var_ann (referenced_var (i))->current_def = NULL;
mark_dfs_back_edges ();
avail_exprs = htab_create (1024, avail_expr_hash, avail_expr_eq, free);
VARRAY_TREE_INIT (const_and_copies, highest_ssa_version, "const_and_copies");
nonzero_vars = BITMAP_XMALLOC ();
VARRAY_EDGE_INIT (redirection_edges, 20, "redirection_edges");
VARRAY_GENERIC_PTR_INIT (vrp_data, highest_ssa_version, "vrp_data");
walk_data.walk_stmts_backward = false;
walk_data.dom_direction = CDI_DOMINATORS;
walk_data.initialize_block_local_data = dom_opt_initialize_block_local_data;
walk_data.before_dom_children_before_stmts = dom_opt_initialize_block;
walk_data.before_dom_children_walk_stmts = optimize_stmt;
walk_data.before_dom_children_after_stmts = cprop_into_phis;
walk_data.after_dom_children_before_stmts = NULL;
walk_data.after_dom_children_walk_stmts = NULL;
walk_data.after_dom_children_after_stmts = dom_opt_finalize_block;
walk_data.global_data = NULL;
walk_data.block_local_data_size = sizeof (struct dom_walk_block_data);
init_walk_dominator_tree (&walk_data);
FOR_EACH_BB (bb)
bb_ann (bb)->forwardable = 1;
calculate_dominance_info (CDI_DOMINATORS);
do
{
cfg_altered = false;
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
if (VARRAY_ACTIVE_SIZE (redirection_edges) > 0)
redirect_edges_and_update_ssa_graph (redirection_edges);
cfg_altered |= delete_unreachable_blocks ();
if (cfg_altered)
{
cleanup_tree_cfg ();
calculate_dominance_info (CDI_DOMINATORS);
}
if (cfg_altered
&& bitmap_first_set_bit (vars_to_rename) >= 0)
{
rewrite_into_ssa (false);
bitmap_clear (vars_to_rename);
VARRAY_GROW (const_and_copies, highest_ssa_version);
VARRAY_GROW (vrp_data, highest_ssa_version);
}
bitmap_clear (nonzero_vars);
htab_empty (avail_exprs);
VARRAY_CLEAR (const_and_copies);
VARRAY_CLEAR (vrp_data);
for (i = 0; i < num_referenced_vars; i++)
var_ann (referenced_var (i))->current_def = NULL;
}
while (cfg_altered);
cleanup_tree_cfg ();
loop_optimizer_finalize (loops, NULL);
if (dump_file && (dump_flags & TDF_STATS))
dump_dominator_optimization_stats (dump_file);
htab_delete (avail_exprs);
fini_walk_dominator_tree (&walk_data);
BITMAP_XFREE (nonzero_vars);
}
static bool
gate_dominator (void)
{
return flag_tree_dom != 0;
}
struct tree_opt_pass pass_dominator =
{
"dom",
gate_dominator,
tree_ssa_dominator_optimize,
NULL,
NULL,
0,
TV_TREE_SSA_DOMINATOR_OPTS,
PROP_cfg | PROP_ssa,
0,
0,
0,
TODO_dump_func | TODO_rename_vars
| TODO_verify_ssa
};
static void
thread_across_edge (struct dom_walk_data *walk_data, edge e)
{
struct dom_walk_block_data *bd
= VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
block_stmt_iterator bsi;
tree stmt = NULL;
tree phi;
for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
{
tree src = PHI_ARG_DEF (phi, phi_arg_from_edge (phi, e));
tree dst = PHI_RESULT (phi);
record_const_or_copy (dst, src, &bd->const_and_copies);
register_new_def (dst, &bd->block_defs);
}
for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
{
tree lhs, cached_lhs;
stmt = bsi_stmt (bsi);
if (IS_EMPTY_STMT (stmt) || TREE_CODE (stmt) == LABEL_EXPR)
continue;
if (TREE_CODE (stmt) != MODIFY_EXPR
|| TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
break;
if (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
cached_lhs = TREE_OPERAND (stmt, 1);
else
cached_lhs = lookup_avail_expr (stmt, NULL, false);
lhs = TREE_OPERAND (stmt, 0);
if (lhs == cached_lhs)
break;
if (!cached_lhs)
{
stmt_ann_t ann = stmt_ann (stmt);
use_optype uses = USE_OPS (ann);
vuse_optype vuses = VUSE_OPS (ann);
tree *uses_copy = xcalloc (NUM_USES (uses), sizeof (tree));
tree *vuses_copy = xcalloc (NUM_VUSES (vuses), sizeof (tree));
unsigned int i;
for (i = 0; i < NUM_USES (uses); i++)
{
tree tmp = NULL;
uses_copy[i] = USE_OP (uses, i);
if (TREE_CODE (USE_OP (uses, i)) == SSA_NAME)
tmp = get_value_for (USE_OP (uses, i), const_and_copies);
if (tmp)
*USE_OP_PTR (uses, i) = tmp;
}
for (i = 0; i < NUM_VUSES (vuses); i++)
{
tree tmp = NULL;
vuses_copy[i] = VUSE_OP (vuses, i);
if (TREE_CODE (VUSE_OP (vuses, i)) == SSA_NAME)
tmp = get_value_for (VUSE_OP (vuses, i), const_and_copies);
if (tmp)
VUSE_OP (vuses, i) = tmp;
}
cached_lhs = lookup_avail_expr (stmt, NULL, false);
for (i = 0; i < NUM_USES (uses); i++)
*USE_OP_PTR (uses, i) = uses_copy[i];
for (i = 0; i < NUM_VUSES (vuses); i++)
VUSE_OP (vuses, i) = vuses_copy[i];
free (uses_copy);
free (vuses_copy);
if (! cached_lhs)
break;
}
if (TREE_CODE (cached_lhs) != SSA_NAME)
break;
if (SSA_NAME_VAR (cached_lhs) != SSA_NAME_VAR (lhs))
break;
if (var_ann (SSA_NAME_VAR (lhs))->current_def != cached_lhs)
break;
record_const_or_copy (lhs, cached_lhs, &bd->const_and_copies);
register_new_def (lhs, &bd->block_defs);
}
if (stmt
&& (TREE_CODE (stmt) == COND_EXPR
|| TREE_CODE (stmt) == SWITCH_EXPR))
{
tree cond, cached_lhs;
edge e1;
if (!e->flags & EDGE_DFS_BACK)
{
for (e1 = e->dest->pred; e; e = e->pred_next)
if (e1->flags & EDGE_DFS_BACK)
break;
if (e1)
return;
}
if (TREE_CODE (stmt) == COND_EXPR)
cond = COND_EXPR_COND (stmt);
else
cond = SWITCH_COND (stmt);
if (TREE_CODE_CLASS (TREE_CODE (cond)) == '<')
{
tree dummy_cond, op0, op1;
enum tree_code cond_code;
op0 = TREE_OPERAND (cond, 0);
op1 = TREE_OPERAND (cond, 1);
cond_code = TREE_CODE (cond);
if (TREE_CODE (op0) == SSA_NAME)
{
tree tmp = get_value_for (op0, const_and_copies);
if (tmp)
op0 = tmp;
}
if (TREE_CODE (op1) == SSA_NAME)
{
tree tmp = get_value_for (op1, const_and_copies);
if (tmp)
op1 = tmp;
}
dummy_cond = walk_data->global_data;
if (! dummy_cond)
{
dummy_cond = build (cond_code, boolean_type_node, op0, op1);
dummy_cond = build (COND_EXPR, void_type_node,
dummy_cond, NULL, NULL);
walk_data->global_data = dummy_cond;
}
else
{
TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), cond_code);
TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op0;
TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1) = op1;
}
cached_lhs = local_fold (COND_EXPR_COND (dummy_cond));
if (! is_gimple_min_invariant (cached_lhs))
cached_lhs = lookup_avail_expr (dummy_cond, NULL, false);
if (!cached_lhs || ! is_gimple_min_invariant (cached_lhs))
{
stmt_ann_t ann = get_stmt_ann (dummy_cond);
cached_lhs = simplify_cond_and_lookup_avail_expr (dummy_cond,
NULL,
ann,
false);
}
}
else if (TREE_CODE (cond) == SSA_NAME)
{
cached_lhs = cond;
cached_lhs = get_value_for (cached_lhs, const_and_copies);
if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
cached_lhs = 0;
}
else
cached_lhs = lookup_avail_expr (stmt, NULL, false);
if (cached_lhs)
{
edge taken_edge = find_taken_edge (e->dest, cached_lhs);
basic_block dest = (taken_edge ? taken_edge->dest : NULL);
if (dest == e->src)
return;
if (dest)
{
int saved_forwardable = bb_ann (e->src)->forwardable;
edge tmp_edge;
bb_ann (e->src)->forwardable = 0;
tmp_edge = tree_block_forwards_to (dest);
taken_edge = (tmp_edge ? tmp_edge : taken_edge);
bb_ann (e->src)->forwardable = saved_forwardable;
VARRAY_PUSH_EDGE (redirection_edges, e);
VARRAY_PUSH_EDGE (redirection_edges, taken_edge);
}
}
}
}
static void
dom_opt_initialize_block_local_data (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb ATTRIBUTE_UNUSED,
bool recycled ATTRIBUTE_UNUSED)
{
#ifdef ENABLE_CHECKING
struct dom_walk_block_data *bd
= (struct dom_walk_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
if (recycled)
{
if (bd->avail_exprs && VARRAY_ACTIVE_SIZE (bd->avail_exprs) > 0)
abort ();
if (bd->const_and_copies && VARRAY_ACTIVE_SIZE (bd->const_and_copies) > 0)
abort ();
if (bd->nonzero_vars && VARRAY_ACTIVE_SIZE (bd->nonzero_vars) > 0)
abort ();
if (bd->stmts_to_rescan && VARRAY_ACTIVE_SIZE (bd->stmts_to_rescan) > 0)
abort ();
if (bd->vrp_variables && VARRAY_ACTIVE_SIZE (bd->vrp_variables) > 0)
abort ();
if (bd->block_defs && VARRAY_ACTIVE_SIZE (bd->block_defs) > 0)
abort ();
}
#endif
}
static void
dom_opt_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
record_equivalences_from_incoming_edge (walk_data, bb);
record_equivalences_from_phis (walk_data, bb);
}
static void
initialize_hash_element (tree expr, tree lhs, struct expr_hash_elt *element)
{
if (TREE_CODE_CLASS (TREE_CODE (expr)) == '<'
|| TREE_CODE (expr) == TRUTH_NOT_EXPR)
{
element->ann = NULL;
element->rhs = expr;
}
else if (TREE_CODE (expr) == COND_EXPR)
{
element->ann = stmt_ann (expr);
element->rhs = COND_EXPR_COND (expr);
}
else if (TREE_CODE (expr) == SWITCH_EXPR)
{
element->ann = stmt_ann (expr);
element->rhs = SWITCH_COND (expr);
}
else if (TREE_CODE (expr) == RETURN_EXPR && TREE_OPERAND (expr, 0))
{
element->ann = stmt_ann (expr);
element->rhs = TREE_OPERAND (TREE_OPERAND (expr, 0), 1);
}
else
{
element->ann = stmt_ann (expr);
element->rhs = TREE_OPERAND (expr, 1);
}
element->lhs = lhs;
element->hash = avail_expr_hash (element);
}
static void
remove_local_expressions_from_table (varray_type locals,
unsigned limit,
htab_t table)
{
if (! locals)
return;
while (VARRAY_ACTIVE_SIZE (locals) > limit)
{
struct expr_hash_elt element;
tree expr = VARRAY_TOP_TREE (locals);
VARRAY_POP (locals);
initialize_hash_element (expr, NULL, &element);
htab_remove_elt_with_hash (table, &element, element.hash);
}
}
static void
restore_nonzero_vars_to_original_value (varray_type locals,
unsigned limit,
bitmap table)
{
if (!locals)
return;
while (VARRAY_ACTIVE_SIZE (locals) > limit)
{
tree name = VARRAY_TOP_TREE (locals);
VARRAY_POP (locals);
bitmap_clear_bit (table, SSA_NAME_VERSION (name));
}
}
static void
restore_vars_to_original_value (varray_type locals,
unsigned limit,
varray_type table)
{
if (! locals)
return;
while (VARRAY_ACTIVE_SIZE (locals) > limit)
{
tree prev_value, dest;
prev_value = VARRAY_TOP_TREE (locals);
VARRAY_POP (locals);
dest = VARRAY_TOP_TREE (locals);
VARRAY_POP (locals);
set_value_for (dest, prev_value, table);
}
}
static void
restore_currdefs_to_original_value (varray_type locals, unsigned limit)
{
if (!locals)
return;
while (VARRAY_ACTIVE_SIZE (locals) > limit)
{
tree tmp = VARRAY_TOP_TREE (locals);
tree saved_def, var;
VARRAY_POP (locals);
if (TREE_CODE (tmp) == SSA_NAME)
{
saved_def = tmp;
var = SSA_NAME_VAR (saved_def);
}
else
{
saved_def = NULL;
var = tmp;
}
var_ann (var)->current_def = saved_def;
}
}
static void
dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
{
struct dom_walk_block_data *bd
= VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
tree last;
if (bb->succ
&& ! bb->succ->succ_next
&& (bb->succ->flags & EDGE_ABNORMAL) == 0
&& (get_immediate_dominator (CDI_DOMINATORS, bb->succ->dest) != bb
|| phi_nodes (bb->succ->dest)))
{
thread_across_edge (walk_data, bb->succ);
}
else if ((last = last_stmt (bb))
&& TREE_CODE (last) == COND_EXPR
&& (TREE_CODE_CLASS (TREE_CODE (COND_EXPR_COND (last))) == '<'
|| TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME)
&& bb->succ
&& (bb->succ->flags & EDGE_ABNORMAL) == 0
&& bb->succ->succ_next
&& (bb->succ->succ_next->flags & EDGE_ABNORMAL) == 0
&& ! bb->succ->succ_next->succ_next)
{
edge true_edge, false_edge;
tree cond, inverted = NULL;
enum tree_code cond_code;
extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
cond = COND_EXPR_COND (last);
cond_code = TREE_CODE (cond);
if (TREE_CODE_CLASS (cond_code) == '<')
inverted = invert_truthvalue (cond);
if (get_immediate_dominator (CDI_DOMINATORS, true_edge->dest) != bb
|| phi_nodes (true_edge->dest))
{
unsigned avail_expr_limit;
unsigned const_and_copies_limit;
unsigned currdefs_limit;
avail_expr_limit
= bd->avail_exprs ? VARRAY_ACTIVE_SIZE (bd->avail_exprs) : 0;
const_and_copies_limit
= bd->const_and_copies ? VARRAY_ACTIVE_SIZE (bd->const_and_copies)
: 0;
currdefs_limit
= bd->block_defs ? VARRAY_ACTIVE_SIZE (bd->block_defs) : 0;
if (TREE_CODE_CLASS (cond_code) == '<')
{
record_cond (cond, boolean_true_node, &bd->avail_exprs);
record_cond (inverted, boolean_false_node, &bd->avail_exprs);
}
else if (cond_code == SSA_NAME)
record_const_or_copy (cond, boolean_true_node,
&bd->const_and_copies);
thread_across_edge (walk_data, true_edge);
remove_local_expressions_from_table (bd->avail_exprs,
avail_expr_limit,
avail_exprs);
restore_vars_to_original_value (bd->const_and_copies,
const_and_copies_limit,
const_and_copies);
restore_currdefs_to_original_value (bd->block_defs, currdefs_limit);
}
if (get_immediate_dominator (CDI_DOMINATORS, false_edge->dest) != bb
|| phi_nodes (false_edge->dest))
{
if (TREE_CODE_CLASS (cond_code) == '<')
{
record_cond (cond, boolean_false_node, &bd->avail_exprs);
record_cond (inverted, boolean_true_node, &bd->avail_exprs);
}
else if (cond_code == SSA_NAME)
record_const_or_copy (cond, boolean_false_node,
&bd->const_and_copies);
thread_across_edge (walk_data, false_edge);
}
}
remove_local_expressions_from_table (bd->avail_exprs, 0, avail_exprs);
restore_nonzero_vars_to_original_value (bd->nonzero_vars, 0, nonzero_vars);
restore_vars_to_original_value (bd->const_and_copies, 0, const_and_copies);
restore_currdefs_to_original_value (bd->block_defs, 0);
while (bd->vrp_variables && VARRAY_ACTIVE_SIZE (bd->vrp_variables) > 0)
{
tree var = VARRAY_TOP_TREE (bd->vrp_variables);
varray_type var_vrp_records = VARRAY_GENERIC_PTR (vrp_data,
SSA_NAME_VERSION (var));
while (VARRAY_ACTIVE_SIZE (var_vrp_records) > 0)
{
struct vrp_element *element
= (struct vrp_element *)VARRAY_TOP_GENERIC_PTR (var_vrp_records);
if (element->bb != bb)
break;
VARRAY_POP (var_vrp_records);
}
VARRAY_POP (bd->vrp_variables);
}
while (bd->stmts_to_rescan && VARRAY_ACTIVE_SIZE (bd->stmts_to_rescan) > 0)
{
tree stmt = VARRAY_TOP_TREE (bd->stmts_to_rescan);
VARRAY_POP (bd->stmts_to_rescan);
mark_new_vars_to_rename (stmt, vars_to_rename);
}
}
static void
record_equivalences_from_phis (struct dom_walk_data *walk_data, basic_block bb)
{
struct dom_walk_block_data *bd
= VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
tree phi;
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
{
tree lhs = PHI_RESULT (phi);
tree rhs = NULL;
int i;
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
tree t = PHI_ARG_DEF (phi, i);
if (TREE_CODE (t) == SSA_NAME || is_gimple_min_invariant (t))
{
if (operand_equal_p (lhs, t, 0))
continue;
if (rhs == NULL)
rhs = t;
else if (! operand_equal_p (rhs, t, 0))
break;
}
else
break;
}
if (!rhs)
rhs = lhs;
if (i == PHI_NUM_ARGS (phi)
&& may_propagate_copy (lhs, rhs))
set_value_for (lhs, rhs, const_and_copies);
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
if (!PHI_ARG_NONZERO (phi, i))
break;
}
if (i == PHI_NUM_ARGS (phi))
bitmap_set_bit (nonzero_vars, SSA_NAME_VERSION (PHI_RESULT (phi)));
register_new_def (lhs, &bd->block_defs);
}
}
static void
record_equivalences_from_incoming_edge (struct dom_walk_data *walk_data,
basic_block bb)
{
int edge_flags;
basic_block parent;
struct eq_expr_value eq_expr_value;
tree parent_block_last_stmt = NULL;
struct dom_walk_block_data *bd
= VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
parent = get_immediate_dominator (CDI_DOMINATORS, bb);
if (parent)
{
parent_block_last_stmt = last_stmt (parent);
if (parent_block_last_stmt && !is_ctrl_stmt (parent_block_last_stmt))
parent_block_last_stmt = NULL;
}
eq_expr_value.src = NULL;
eq_expr_value.dst = NULL;
if (bb->pred
&& ! bb->pred->pred_next
&& parent_block_last_stmt
&& bb_for_stmt (parent_block_last_stmt) == bb->pred->src)
{
edge_flags = bb->pred->flags;
}
else
{
edge_flags = 0;
parent_block_last_stmt = NULL;
}
if (parent_block_last_stmt
&& bb->pred->pred_next == NULL
&& TREE_CODE (parent_block_last_stmt) == COND_EXPR
&& (edge_flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
eq_expr_value = get_eq_expr_value (parent_block_last_stmt,
(edge_flags & EDGE_TRUE_VALUE) != 0,
&bd->avail_exprs,
bb,
&bd->vrp_variables);
else if (parent_block_last_stmt
&& bb->pred->pred_next == NULL
&& TREE_CODE (parent_block_last_stmt) == SWITCH_EXPR)
{
tree switch_cond = SWITCH_COND (parent_block_last_stmt);
if (TREE_CODE (switch_cond) == SSA_NAME)
{
tree switch_vec = SWITCH_LABELS (parent_block_last_stmt);
size_t i, n = TREE_VEC_LENGTH (switch_vec);
int case_count = 0;
tree match_case = NULL_TREE;
for (i = 0; i < n; ++i)
{
tree elt = TREE_VEC_ELT (switch_vec, i);
if (label_to_block (CASE_LABEL (elt)) == bb)
{
if (++case_count > 1)
break;
match_case = elt;
}
}
if (case_count == 1
&& CASE_LOW (match_case)
&& !CASE_HIGH (match_case))
{
eq_expr_value.dst = switch_cond;
eq_expr_value.src = CASE_LOW (match_case);
}
}
}
if (eq_expr_value.src && eq_expr_value.dst)
record_equality (eq_expr_value.dst, eq_expr_value.src,
&bd->const_and_copies);
}
void
dump_dominator_optimization_stats (FILE *file)
{
long n_exprs;
fprintf (file, "Total number of statements: %6ld\n\n",
opt_stats.num_stmts);
fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
opt_stats.num_exprs_considered);
n_exprs = opt_stats.num_exprs_considered;
if (n_exprs == 0)
n_exprs = 1;
fprintf (file, " Redundant expressions eliminated: %6ld (%.0f%%)\n",
opt_stats.num_re, PERCENT (opt_stats.num_re,
n_exprs));
fprintf (file, "\nHash table statistics:\n");
fprintf (file, " avail_exprs: ");
htab_statistics (file, avail_exprs);
}
void
debug_dominator_optimization_stats (void)
{
dump_dominator_optimization_stats (stderr);
}
static void
htab_statistics (FILE *file, htab_t htab)
{
fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
(long) htab_size (htab),
(long) htab_elements (htab),
htab_collisions (htab));
}
static void
record_var_is_nonzero (tree var, varray_type *block_nonzero_vars_p)
{
int indx = SSA_NAME_VERSION (var);
if (bitmap_bit_p (nonzero_vars, indx))
return;
bitmap_set_bit (nonzero_vars, indx);
if (! *block_nonzero_vars_p)
VARRAY_TREE_INIT (*block_nonzero_vars_p, 2, "block_nonzero_vars");
VARRAY_PUSH_TREE (*block_nonzero_vars_p, var);
}
static void
record_cond (tree cond, tree value, varray_type *block_avail_exprs_p)
{
struct expr_hash_elt *element = xmalloc (sizeof (struct expr_hash_elt));
void **slot;
initialize_hash_element (cond, value, element);
slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
element->hash, true);
if (*slot == NULL)
{
*slot = (void *) element;
if (! *block_avail_exprs_p)
VARRAY_TREE_INIT (*block_avail_exprs_p, 20, "block_avail_exprs");
VARRAY_PUSH_TREE (*block_avail_exprs_p, cond);
}
else
free (element);
}
static void
record_const_or_copy_1 (tree x, tree y, tree prev_x,
varray_type *block_const_and_copies_p)
{
set_value_for (x, y, const_and_copies);
if (!*block_const_and_copies_p)
VARRAY_TREE_INIT (*block_const_and_copies_p, 2, "block_const_and_copies");
VARRAY_PUSH_TREE (*block_const_and_copies_p, x);
VARRAY_PUSH_TREE (*block_const_and_copies_p, prev_x);
}
static void
record_const_or_copy (tree x, tree y, varray_type *block_const_and_copies_p)
{
tree prev_x = get_value_for (x, const_and_copies);
if (TREE_CODE (y) == SSA_NAME)
{
tree tmp = get_value_for (y, const_and_copies);
if (tmp)
y = tmp;
}
record_const_or_copy_1 (x, y, prev_x, block_const_and_copies_p);
}
static void
record_equality (tree x, tree y, varray_type *block_const_and_copies_p)
{
tree prev_x = NULL, prev_y = NULL;
if (TREE_CODE (x) == SSA_NAME)
prev_x = get_value_for (x, const_and_copies);
if (TREE_CODE (y) == SSA_NAME)
prev_y = get_value_for (y, const_and_copies);
if (TREE_INVARIANT (y))
;
else if (TREE_INVARIANT (x))
prev_x = x, x = y, y = prev_x, prev_x = prev_y;
else if (prev_x && TREE_INVARIANT (prev_x))
x = y, y = prev_x, prev_x = prev_y;
else if (prev_y)
y = prev_y;
if (TREE_CODE (x) != SSA_NAME)
return;
if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x)))
&& (TREE_CODE (y) != REAL_CST
|| REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y))))
return;
record_const_or_copy_1 (x, y, prev_x, block_const_and_copies_p);
}
static tree
simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *walk_data,
tree stmt,
stmt_ann_t ann,
int insert)
{
tree rhs = TREE_OPERAND (stmt, 1);
enum tree_code rhs_code = TREE_CODE (rhs);
tree result = NULL;
struct dom_walk_block_data *bd
= VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
if ((rhs_code == BIT_NOT_EXPR || rhs_code == NEGATE_EXPR)
&& TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
{
tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
if (TREE_CODE (rhs_def_stmt) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (rhs_def_stmt, 1)) == rhs_code
&& loop_of_stmt (rhs_def_stmt) == loop_of_stmt (stmt))
{
tree rhs_def_operand;
rhs_def_operand = TREE_OPERAND (TREE_OPERAND (rhs_def_stmt, 1), 0);
if (TREE_CODE (rhs_def_operand) == SSA_NAME
&& ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
result = update_rhs_and_lookup_avail_expr (stmt,
rhs_def_operand,
&bd->avail_exprs,
ann,
insert);
}
}
if ((associative_tree_code (rhs_code) || rhs_code == MINUS_EXPR)
&& TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
&& is_gimple_min_invariant (TREE_OPERAND (rhs, 1)))
{
tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
if (TREE_CODE (rhs_def_stmt) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (rhs_def_stmt, 1)) == rhs_code
&& loop_of_stmt (rhs_def_stmt) == loop_of_stmt (stmt))
{
tree rhs_def_rhs = TREE_OPERAND (rhs_def_stmt, 1);
enum tree_code rhs_def_code = TREE_CODE (rhs_def_rhs);
if (rhs_code == rhs_def_code
|| (rhs_code == PLUS_EXPR && rhs_def_code == MINUS_EXPR)
|| (rhs_code == MINUS_EXPR && rhs_def_code == PLUS_EXPR))
{
tree def_stmt_op0 = TREE_OPERAND (rhs_def_rhs, 0);
tree def_stmt_op1 = TREE_OPERAND (rhs_def_rhs, 1);
if (TREE_CODE (def_stmt_op0) == SSA_NAME
&& ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_stmt_op0)
&& is_gimple_min_invariant (def_stmt_op1))
{
tree outer_const = TREE_OPERAND (rhs, 1);
tree type = TREE_TYPE (TREE_OPERAND (stmt, 0));
tree t;
if (rhs_def_code != rhs_code)
{
if (rhs_def_code == MINUS_EXPR)
t = build (MINUS_EXPR, type, outer_const, def_stmt_op1);
else
t = build (MINUS_EXPR, type, def_stmt_op1, outer_const);
rhs_code = PLUS_EXPR;
}
else if (rhs_def_code == MINUS_EXPR)
t = build (PLUS_EXPR, type, def_stmt_op1, outer_const);
else
t = build (rhs_def_code, type, def_stmt_op1, outer_const);
t = local_fold (t);
t = build (rhs_code, type, def_stmt_op0, t);
t = local_fold (t);
if (TREE_CODE (t) == SSA_NAME
|| (TREE_CODE_CLASS (TREE_CODE (t)) == '1'
&& TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
|| ((TREE_CODE_CLASS (TREE_CODE (t)) == '2'
|| TREE_CODE_CLASS (TREE_CODE (t)) == '<')
&& TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
&& is_gimple_val (TREE_OPERAND (t, 1))))
result = update_rhs_and_lookup_avail_expr
(stmt, t, &bd->avail_exprs, ann, insert);
}
}
}
}
if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
&& INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
&& integer_pow2p (TREE_OPERAND (rhs, 1)))
{
tree val;
tree op = TREE_OPERAND (rhs, 0);
if (TYPE_UNSIGNED (TREE_TYPE (op)))
{
val = integer_one_node;
}
else
{
tree dummy_cond = walk_data->global_data;
if (! dummy_cond)
{
dummy_cond = build (GT_EXPR, boolean_type_node,
op, integer_zero_node);
dummy_cond = build (COND_EXPR, void_type_node,
dummy_cond, NULL, NULL);
walk_data->global_data = dummy_cond;
}
else
{
TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), GT_EXPR);
TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op;
TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1)
= integer_zero_node;
}
val = simplify_cond_and_lookup_avail_expr (dummy_cond,
&bd->avail_exprs,
NULL, false);
}
if (val && integer_onep (val))
{
tree t;
tree op0 = TREE_OPERAND (rhs, 0);
tree op1 = TREE_OPERAND (rhs, 1);
if (rhs_code == TRUNC_DIV_EXPR)
t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0,
build_int_2 (tree_log2 (op1), 0));
else
t = build (BIT_AND_EXPR, TREE_TYPE (op0), op0,
local_fold (build (MINUS_EXPR, TREE_TYPE (op1),
op1, integer_one_node)));
result = update_rhs_and_lookup_avail_expr (stmt, t,
&bd->avail_exprs,
ann, insert);
}
}
if (rhs_code == ABS_EXPR
&& INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
{
tree val;
tree op = TREE_OPERAND (rhs, 0);
tree type = TREE_TYPE (op);
if (TYPE_UNSIGNED (type))
{
val = integer_zero_node;
}
else
{
tree dummy_cond = walk_data->global_data;
if (! dummy_cond)
{
dummy_cond = build (LE_EXPR, boolean_type_node,
op, integer_zero_node);
dummy_cond = build (COND_EXPR, void_type_node,
dummy_cond, NULL, NULL);
walk_data->global_data = dummy_cond;
}
else
{
TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), LE_EXPR);
TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op;
TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1)
= convert (type, integer_zero_node);
}
val = simplify_cond_and_lookup_avail_expr (dummy_cond,
&bd->avail_exprs,
NULL, false);
if (!val)
{
TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), GE_EXPR);
TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op;
TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1)
= convert (type, integer_zero_node);
val = simplify_cond_and_lookup_avail_expr (dummy_cond,
&bd->avail_exprs,
NULL, false);
if (val)
{
if (integer_zerop (val))
val = integer_one_node;
else if (integer_onep (val))
val = integer_zero_node;
}
}
}
if (val
&& (integer_onep (val) || integer_zerop (val)))
{
tree t;
if (integer_onep (val))
t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
else
t = op;
result = update_rhs_and_lookup_avail_expr (stmt, t,
&bd->avail_exprs,
ann, insert);
}
}
if (TREE_CODE (rhs) == INDIRECT_REF || TREE_CODE (rhs) == ARRAY_REF)
{
tree t = fold_read_from_constant_string (rhs);
if (t)
result = update_rhs_and_lookup_avail_expr (stmt, t,
&bd->avail_exprs,
ann, insert);
}
return result;
}
static tree
find_equivalent_equality_comparison (tree cond)
{
tree op0 = TREE_OPERAND (cond, 0);
tree op1 = TREE_OPERAND (cond, 1);
tree def_stmt = SSA_NAME_DEF_STMT (op0);
if (def_stmt && TREE_CODE (def_stmt) == MODIFY_EXPR)
{
tree def_rhs = TREE_OPERAND (def_stmt, 1);
if ((TREE_CODE (def_rhs) == NOP_EXPR
|| TREE_CODE (def_rhs) == CONVERT_EXPR)
&& TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME)
{
tree def_rhs_inner = TREE_OPERAND (def_rhs, 0);
tree def_rhs_inner_type = TREE_TYPE (def_rhs_inner);
tree new;
if (TYPE_PRECISION (def_rhs_inner_type)
> TYPE_PRECISION (TREE_TYPE (def_rhs)))
return NULL;
new = build1 (TREE_CODE (def_rhs), def_rhs_inner_type, op1);
new = local_fold (new);
if (is_gimple_val (new) && tree_int_cst_equal (new, op1))
return build (TREE_CODE (cond), TREE_TYPE (cond),
def_rhs_inner, new);
}
}
return NULL;
}
static tree
simplify_cond_and_lookup_avail_expr (tree stmt,
varray_type *block_avail_exprs_p,
stmt_ann_t ann,
int insert)
{
tree cond = COND_EXPR_COND (stmt);
if (TREE_CODE_CLASS (TREE_CODE (cond)) == '<')
{
tree op0 = TREE_OPERAND (cond, 0);
tree op1 = TREE_OPERAND (cond, 1);
if (TREE_CODE (op0) == SSA_NAME && is_gimple_min_invariant (op1))
{
int limit;
tree low, high, cond_low, cond_high;
int lowequal, highequal, swapped, no_overlap, subset, cond_inverted;
varray_type vrp_records;
struct vrp_element *element;
if (TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
{
tree new_cond = find_equivalent_equality_comparison (cond);
if (new_cond)
{
COND_EXPR_COND (stmt) = new_cond;
ann->modified = 1;
new_cond = lookup_avail_expr (stmt, block_avail_exprs_p,
insert);
if (new_cond)
return new_cond;
op0 = TREE_OPERAND (cond, 0);
op1 = TREE_OPERAND (cond, 1);
}
}
vrp_records = VARRAY_GENERIC_PTR (vrp_data, SSA_NAME_VERSION (op0));
if (vrp_records == NULL)
return NULL;
limit = VARRAY_ACTIVE_SIZE (vrp_records);
if (limit == 0
|| ! extract_range_from_cond (cond, &cond_high,
&cond_low, &cond_inverted))
return NULL;
element
= (struct vrp_element *)VARRAY_GENERIC_PTR (vrp_records, limit - 1);
if (element->high && element->low)
{
low = element->low;
high = element->high;
}
else
{
tree tmp_high, tmp_low;
int dummy;
extract_range_from_cond (element->cond, &tmp_high,
&tmp_low, &dummy);
if (limit == 1)
{
low = tmp_low;
high = tmp_high;
}
else
{
struct vrp_element *prev
= (struct vrp_element *)VARRAY_GENERIC_PTR (vrp_records,
limit - 2);
low = prev->low;
high = prev->high;
low = (tree_int_cst_compare (low, tmp_low) == 1
? low : tmp_low);
high = (tree_int_cst_compare (high, tmp_high) == -1
? high : tmp_high);
}
element->low = low;
element->high = high;
}
lowequal = tree_int_cst_equal (low, cond_low);
highequal = tree_int_cst_equal (high, cond_high);
if (lowequal && highequal)
return (cond_inverted ? boolean_false_node : boolean_true_node);
swapped = 0;
if (tree_int_cst_compare (low, cond_low) == 1
|| (lowequal
&& tree_int_cst_compare (cond_high, high) == 1))
{
tree temp;
swapped = 1;
temp = low;
low = cond_low;
cond_low = temp;
temp = high;
high = cond_high;
cond_high = temp;
}
no_overlap = tree_int_cst_lt (high, cond_low);
subset = tree_int_cst_compare (cond_high, high) != 1;
if (no_overlap)
return (cond_inverted ? boolean_true_node : boolean_false_node);
if (subset && swapped)
return (cond_inverted ? boolean_false_node : boolean_true_node);
low = tree_int_cst_compare (low, cond_low) == 1 ? low : cond_low;
high = tree_int_cst_compare (high, cond_high) == -1 ? high : cond_high;
if (TREE_CODE (cond) != EQ_EXPR
&& TREE_CODE (cond) != NE_EXPR
&& tree_int_cst_equal (low, high))
{
TREE_SET_CODE (cond, EQ_EXPR);
TREE_OPERAND (cond, 1) = high;
}
}
}
return 0;
}
static tree
simplify_switch_and_lookup_avail_expr (tree stmt,
varray_type *block_avail_exprs_p,
stmt_ann_t ann,
int insert)
{
tree cond = SWITCH_COND (stmt);
tree def, to, ti;
if (TREE_CODE (cond) == SSA_NAME)
{
def = SSA_NAME_DEF_STMT (cond);
if (TREE_CODE (def) == MODIFY_EXPR)
{
def = TREE_OPERAND (def, 1);
if (TREE_CODE (def) == NOP_EXPR)
{
def = TREE_OPERAND (def, 0);
to = TREE_TYPE (cond);
ti = TREE_TYPE (def);
if (TYPE_UNSIGNED (to) == TYPE_UNSIGNED (ti)
&& TYPE_PRECISION (to) >= TYPE_PRECISION (ti)
&& is_gimple_val (def))
{
SWITCH_COND (stmt) = def;
ann->modified = 1;
return lookup_avail_expr (stmt, block_avail_exprs_p, insert);
}
}
}
}
return 0;
}
static void
cprop_into_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb)
{
cprop_into_successor_phis (bb, const_and_copies, nonzero_vars);
}
static bool
eliminate_redundant_computations (struct dom_walk_data *walk_data,
tree stmt, stmt_ann_t ann)
{
vdef_optype vdefs = VDEF_OPS (ann);
tree *expr_p, def = NULL_TREE;
bool insert = true;
tree cached_lhs;
bool retval = false;
struct dom_walk_block_data *bd
= VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
if (TREE_CODE (stmt) == MODIFY_EXPR)
def = TREE_OPERAND (stmt, 0);
if (ann->makes_aliased_stores
|| ! def
|| TREE_CODE (def) != SSA_NAME
|| SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
|| NUM_VDEFS (vdefs) != 0)
insert = false;
cached_lhs = lookup_avail_expr (stmt, &bd->avail_exprs, insert);
if (! cached_lhs && TREE_CODE (stmt) == MODIFY_EXPR)
cached_lhs = simplify_rhs_and_lookup_avail_expr (walk_data,
stmt,
ann,
insert);
else if (! cached_lhs && TREE_CODE (stmt) == COND_EXPR)
cached_lhs = simplify_cond_and_lookup_avail_expr (stmt,
&bd->avail_exprs,
ann,
insert);
else if (!cached_lhs && TREE_CODE (stmt) == SWITCH_EXPR)
cached_lhs = simplify_switch_and_lookup_avail_expr (stmt,
&bd->avail_exprs,
ann,
insert);
opt_stats.num_exprs_considered++;
if (TREE_CODE (stmt) == COND_EXPR)
expr_p = &COND_EXPR_COND (stmt);
else if (TREE_CODE (stmt) == SWITCH_EXPR)
expr_p = &SWITCH_COND (stmt);
else if (TREE_CODE (stmt) == RETURN_EXPR && TREE_OPERAND (stmt, 0))
expr_p = &TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
else
expr_p = &TREE_OPERAND (stmt, 1);
if (cached_lhs
&& (TREE_CODE (cached_lhs) != SSA_NAME
|| may_propagate_copy (cached_lhs, *expr_p)))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " Replaced redundant expr '");
print_generic_expr (dump_file, *expr_p, dump_flags);
fprintf (dump_file, "' with '");
print_generic_expr (dump_file, cached_lhs, dump_flags);
fprintf (dump_file, "'\n");
}
opt_stats.num_re++;
#if defined ENABLE_CHECKING
if (TREE_CODE (cached_lhs) != SSA_NAME
&& !is_gimple_min_invariant (cached_lhs))
abort ();
#endif
if (TREE_CODE (cached_lhs) == ADDR_EXPR
|| (POINTER_TYPE_P (TREE_TYPE (*expr_p))
&& is_gimple_min_invariant (cached_lhs)))
retval = true;
propagate_value (expr_p, cached_lhs);
ann->modified = 1;
}
return retval;
}
static void
record_equivalences_from_stmt (tree stmt,
varray_type *block_avail_exprs_p,
varray_type *block_nonzero_vars_p,
int may_optimize_p,
stmt_ann_t ann)
{
tree lhs = TREE_OPERAND (stmt, 0);
enum tree_code lhs_code = TREE_CODE (lhs);
int i;
if (lhs_code == SSA_NAME)
{
tree rhs = TREE_OPERAND (stmt, 1);
STRIP_USELESS_TYPE_CONVERSION (rhs);
if (may_optimize_p
&& (TREE_CODE (rhs) == SSA_NAME
|| is_gimple_min_invariant (rhs)))
set_value_for (lhs, rhs, const_and_copies);
while (TREE_CODE (rhs) == NOP_EXPR
|| TREE_CODE (rhs) == CONVERT_EXPR)
rhs = TREE_OPERAND (rhs, 0);
if (alloca_call_p (rhs)
|| (TREE_CODE (rhs) == ADDR_EXPR
&& DECL_P (TREE_OPERAND (rhs, 0))
&& ! DECL_WEAK (TREE_OPERAND (rhs, 0))))
record_var_is_nonzero (lhs, block_nonzero_vars_p);
if (TREE_CODE (rhs) == BIT_IOR_EXPR
&& integer_nonzerop (TREE_OPERAND (rhs, 1)))
record_var_is_nonzero (lhs, block_nonzero_vars_p);
}
if (flag_delete_null_pointer_checks)
for (i = 0; i < 2; i++)
{
tree t = TREE_OPERAND (stmt, i);
while (TREE_CODE (t) == COMPONENT_REF)
t = TREE_OPERAND (t, 0);
if (TREE_CODE (t) == INDIRECT_REF)
{
tree op = TREE_OPERAND (t, 0);
while (TREE_CODE (op) == SSA_NAME)
{
tree def = SSA_NAME_DEF_STMT (op);
record_var_is_nonzero (op, block_nonzero_vars_p);
if (def
&& TREE_CODE (def) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (def, 1)) == NOP_EXPR)
op = TREE_OPERAND (TREE_OPERAND (def, 1), 0);
else
break;
}
}
}
if (!ann->has_volatile_ops
&& (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME
|| is_gimple_min_invariant (TREE_OPERAND (stmt, 1)))
&& !is_gimple_reg (lhs))
{
tree rhs = TREE_OPERAND (stmt, 1);
tree new;
size_t j;
if (lhs_code == COMPONENT_REF
&& DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
{
if (TREE_CONSTANT (rhs))
rhs = widen_bitfield (rhs, TREE_OPERAND (lhs, 1), lhs);
else
rhs = NULL;
if (rhs && ! is_gimple_min_invariant (rhs))
rhs = NULL;
}
if (rhs)
{
vdef_optype vdefs = VDEF_OPS (ann);
new = build (MODIFY_EXPR, TREE_TYPE (stmt), rhs, lhs);
get_stmt_ann (new);
get_stmt_operands (new);
remove_vuses (new);
remove_vdefs (new);
start_ssa_stmt_operands (new);
for (j = 0; j < NUM_VDEFS (vdefs); j++)
{
tree op = VDEF_RESULT (vdefs, j);
add_vuse (op, new);
}
finalize_ssa_stmt_operands (new);
lookup_avail_expr (new, block_avail_exprs_p, true);
}
}
}
static void
optimize_stmt (struct dom_walk_data *walk_data,
basic_block bb ATTRIBUTE_UNUSED,
block_stmt_iterator si)
{
stmt_ann_t ann;
tree stmt;
vdef_optype vdefs;
bool may_optimize_p;
bool may_have_exposed_new_symbols = false;
struct dom_walk_block_data *bd
= VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
stmt = bsi_stmt (si);
get_stmt_operands (stmt);
ann = stmt_ann (stmt);
vdefs = VDEF_OPS (ann);
opt_stats.num_stmts++;
may_have_exposed_new_symbols = false;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Optimizing statement ");
print_generic_stmt (dump_file, stmt, TDF_SLIM);
}
may_have_exposed_new_symbols = cprop_into_stmt (stmt, const_and_copies);
if (ann->modified)
{
if (fold_stmt (bsi_stmt_ptr (si)))
{
stmt = bsi_stmt (si);
ann = stmt_ann (stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " Folded to: ");
print_generic_stmt (dump_file, stmt, TDF_SLIM);
}
}
may_have_exposed_new_symbols = true;
}
may_optimize_p = (!ann->has_volatile_ops
&& ((TREE_CODE (stmt) == RETURN_EXPR
&& TREE_OPERAND (stmt, 0)
&& TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR
&& ! (TREE_SIDE_EFFECTS
(TREE_OPERAND (TREE_OPERAND (stmt, 0), 1))))
|| (TREE_CODE (stmt) == MODIFY_EXPR
&& ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt, 1)))
|| TREE_CODE (stmt) == COND_EXPR
|| TREE_CODE (stmt) == SWITCH_EXPR));
if (may_optimize_p)
may_have_exposed_new_symbols
|= eliminate_redundant_computations (walk_data, stmt, ann);
if (TREE_CODE (stmt) == MODIFY_EXPR)
record_equivalences_from_stmt (stmt,
&bd->avail_exprs,
&bd->nonzero_vars,
may_optimize_p,
ann);
register_definitions_for_stmt (ann, &bd->block_defs);
if (ann->modified)
{
tree val = NULL;
if (TREE_CODE (stmt) == COND_EXPR)
val = COND_EXPR_COND (stmt);
else if (TREE_CODE (stmt) == SWITCH_EXPR)
val = SWITCH_COND (stmt);
if (val && TREE_CODE (val) == INTEGER_CST
&& find_taken_edge (bb_for_stmt (stmt), val))
cfg_altered = true;
}
if (may_have_exposed_new_symbols)
{
if (! bd->stmts_to_rescan)
VARRAY_TREE_INIT (bd->stmts_to_rescan, 20, "stmts_to_rescan");
VARRAY_PUSH_TREE (bd->stmts_to_rescan, bsi_stmt (si));
}
}
static tree
update_rhs_and_lookup_avail_expr (tree stmt, tree new_rhs,
varray_type *block_avail_exprs_p,
stmt_ann_t ann,
bool insert)
{
tree cached_lhs = NULL;
if (insert)
{
struct expr_hash_elt element;
initialize_hash_element (stmt, NULL, &element);
htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
}
TREE_OPERAND (stmt, 1) = new_rhs;
cached_lhs = lookup_avail_expr (stmt, block_avail_exprs_p, insert);
if (insert)
VARRAY_POP (*block_avail_exprs_p);
ann->modified = 1;
return cached_lhs;
}
static tree
lookup_avail_expr (tree stmt, varray_type *block_avail_exprs_p, bool insert)
{
void **slot;
tree lhs;
tree temp;
struct expr_hash_elt *element = xcalloc (sizeof (struct expr_hash_elt), 1);
lhs = TREE_CODE (stmt) == MODIFY_EXPR ? TREE_OPERAND (stmt, 0) : NULL;
initialize_hash_element (stmt, lhs, element);
if (TREE_CODE (element->rhs) == SSA_NAME
|| is_gimple_min_invariant (element->rhs))
{
free (element);
return NULL_TREE;
}
if ((TREE_CODE (element->rhs) == EQ_EXPR
|| TREE_CODE (element->rhs) == NE_EXPR)
&& TREE_CODE (TREE_OPERAND (element->rhs, 0)) == SSA_NAME
&& integer_zerop (TREE_OPERAND (element->rhs, 1)))
{
int indx = SSA_NAME_VERSION (TREE_OPERAND (element->rhs, 0));
if (bitmap_bit_p (nonzero_vars, indx))
{
tree t = element->rhs;
free (element);
if (TREE_CODE (t) == EQ_EXPR)
return boolean_false_node;
else
return boolean_true_node;
}
}
slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
(insert ? INSERT : NO_INSERT));
if (slot == NULL)
{
free (element);
return NULL_TREE;
}
if (*slot == NULL)
{
*slot = (void *) element;
if (! *block_avail_exprs_p)
VARRAY_TREE_INIT (*block_avail_exprs_p, 20, "block_avail_exprs");
VARRAY_PUSH_TREE (*block_avail_exprs_p, stmt ? stmt : element->rhs);
return NULL_TREE;
}
lhs = ((struct expr_hash_elt *)*slot)->lhs;
if (TREE_CODE (lhs) == SSA_NAME)
{
temp = get_value_for (lhs, const_and_copies);
if (temp)
lhs = temp;
}
free (element);
return lhs;
}
static bool
extract_range_from_cond (tree cond, tree *hi_p, tree *lo_p, int *inverted_p)
{
tree op1 = TREE_OPERAND (cond, 1);
tree high, low, type;
int inverted;
if (TREE_CODE (TREE_TYPE (op1)) != INTEGER_TYPE)
return 0;
type = TREE_TYPE (op1);
switch (TREE_CODE (cond))
{
case EQ_EXPR:
high = low = op1;
inverted = 0;
break;
case NE_EXPR:
high = low = op1;
inverted = 1;
break;
case GE_EXPR:
low = op1;
high = TYPE_MAX_VALUE (type);
inverted = 0;
break;
case GT_EXPR:
low = int_const_binop (PLUS_EXPR, op1, integer_one_node, 1);
high = TYPE_MAX_VALUE (type);
inverted = 0;
break;
case LE_EXPR:
high = op1;
low = TYPE_MIN_VALUE (type);
inverted = 0;
break;
case LT_EXPR:
high = int_const_binop (MINUS_EXPR, op1, integer_one_node, 1);
low = TYPE_MIN_VALUE (type);
inverted = 0;
break;
default:
return 0;
}
*hi_p = high;
*lo_p = low;
*inverted_p = inverted;
return 1;
}
static void
record_range (tree cond, basic_block bb, varray_type *vrp_variables_p)
{
if (TREE_CODE_CLASS (TREE_CODE (cond)) == '<'
&& TREE_CODE (cond) != NE_EXPR
&& TREE_CODE (TREE_TYPE (TREE_OPERAND (cond, 1))) == INTEGER_TYPE)
{
struct vrp_element *element = ggc_alloc (sizeof (struct vrp_element));
int ssa_version = SSA_NAME_VERSION (TREE_OPERAND (cond, 0));
varray_type *vrp_records_p
= (varray_type *)&VARRAY_GENERIC_PTR (vrp_data, ssa_version);
element->low = NULL;
element->high = NULL;
element->cond = cond;
element->bb = bb;
if (*vrp_records_p == NULL)
{
VARRAY_GENERIC_PTR_INIT (*vrp_records_p, 2, "vrp records");
VARRAY_GENERIC_PTR (vrp_data, ssa_version) = *vrp_records_p;
}
VARRAY_PUSH_GENERIC_PTR (*vrp_records_p, element);
if (! *vrp_variables_p)
VARRAY_TREE_INIT (*vrp_variables_p, 2, "vrp_variables");
VARRAY_PUSH_TREE (*vrp_variables_p, TREE_OPERAND (cond, 0));
}
}
static struct eq_expr_value
get_eq_expr_value (tree if_stmt,
int true_arm,
varray_type *block_avail_exprs_p,
basic_block bb,
varray_type *vrp_variables_p)
{
tree cond;
struct eq_expr_value retval;
cond = COND_EXPR_COND (if_stmt);
retval.src = NULL;
retval.dst = NULL;
if (TREE_CODE (cond) == SSA_NAME)
{
retval.dst = cond;
retval.src = (true_arm ? integer_one_node : integer_zero_node);
return retval;
}
if (TREE_CODE_CLASS (TREE_CODE (cond)) == '<')
{
tree op0 = TREE_OPERAND (cond, 0);
tree op1 = TREE_OPERAND (cond, 1);
if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
&& TREE_CODE (op0) == SSA_NAME
&& TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
&& is_gimple_min_invariant (op1))
{
if ((TREE_CODE (cond) == EQ_EXPR && true_arm)
|| (TREE_CODE (cond) == NE_EXPR && ! true_arm))
{
retval.src = op1;
}
else
{
if (integer_zerop (op1))
retval.src = boolean_true_node;
else
retval.src = boolean_false_node;
}
retval.dst = op0;
return retval;
}
if (TREE_CODE (op0) == SSA_NAME
&& (is_gimple_min_invariant (op1) || TREE_CODE (op1) == SSA_NAME))
{
tree inverted = invert_truthvalue (cond);
if (true_arm)
{
record_cond (cond, boolean_true_node, block_avail_exprs_p);
record_cond (inverted, boolean_false_node, block_avail_exprs_p);
if (TREE_CONSTANT (op1))
record_range (cond, bb, vrp_variables_p);
if (TREE_CODE (cond) == EQ_EXPR)
{
retval.dst = op0;
retval.src = op1;
return retval;
}
}
else
{
record_cond (inverted, boolean_true_node, block_avail_exprs_p);
record_cond (cond, boolean_false_node, block_avail_exprs_p);
if (TREE_CONSTANT (op1))
record_range (inverted, bb, vrp_variables_p);
if (TREE_CODE (cond) == NE_EXPR)
{
retval.dst = op0;
retval.src = op1;
return retval;
}
}
}
}
return retval;
}
static hashval_t
avail_expr_hash (const void *p)
{
stmt_ann_t ann = ((struct expr_hash_elt *)p)->ann;
tree rhs = ((struct expr_hash_elt *)p)->rhs;
hashval_t val = 0;
size_t i;
vuse_optype vuses;
val = iterative_hash_expr (rhs, val);
if (!ann)
return val;
vuses = VUSE_OPS (ann);
for (i = 0; i < NUM_VUSES (vuses); i++)
val = iterative_hash_expr (VUSE_OP (vuses, i), val);
return val;
}
static int
avail_expr_eq (const void *p1, const void *p2)
{
stmt_ann_t ann1 = ((struct expr_hash_elt *)p1)->ann;
tree rhs1 = ((struct expr_hash_elt *)p1)->rhs;
stmt_ann_t ann2 = ((struct expr_hash_elt *)p2)->ann;
tree rhs2 = ((struct expr_hash_elt *)p2)->rhs;
if (rhs1 == rhs2 && ann1 == ann2)
return true;
if (TREE_CODE (rhs1) != TREE_CODE (rhs2))
return false;
if ((TREE_TYPE (rhs1) == TREE_TYPE (rhs2)
|| lang_hooks.types_compatible_p (TREE_TYPE (rhs1), TREE_TYPE (rhs2)))
&& operand_equal_p (rhs1, rhs2, OEP_PURE_SAME))
{
vuse_optype ops1 = NULL;
vuse_optype ops2 = NULL;
size_t num_ops1 = 0;
size_t num_ops2 = 0;
size_t i;
if (ann1)
{
ops1 = VUSE_OPS (ann1);
num_ops1 = NUM_VUSES (ops1);
}
if (ann2)
{
ops2 = VUSE_OPS (ann2);
num_ops2 = NUM_VUSES (ops2);
}
if (num_ops1 != num_ops2)
return false;
for (i = 0; i < num_ops1; i++)
if (VUSE_OP (ops1, i) != VUSE_OP (ops2, i))
return false;
#ifdef ENABLE_CHECKING
if (((struct expr_hash_elt *)p1)->hash
!= ((struct expr_hash_elt *)p2)->hash)
abort ();
#endif
return true;
}
return false;
}
static void
register_definitions_for_stmt (stmt_ann_t ann, varray_type *block_defs_p)
{
def_optype defs;
vdef_optype vdefs;
unsigned int i;
defs = DEF_OPS (ann);
for (i = 0; i < NUM_DEFS (defs); i++)
{
tree def = DEF_OP (defs, i);
register_new_def (def, block_defs_p);
}
vdefs = VDEF_OPS (ann);
for (i = 0; i < NUM_VDEFS (vdefs); i++)
{
register_new_def (VDEF_RESULT (vdefs, i), block_defs_p);
}
}