#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 "cfgloop.h"
#include "output.h"
#include "expr.h"
#include "function.h"
#include "diagnostic.h"
#include "timevar.h"
#include "tree-dump.h"
#include "tree-flow.h"
#include "domwalk.h"
#include "real.h"
#include "tree-pass.h"
#include "tree-ssa-propagate.h"
#include "langhooks.h"
#include "params.h"
struct edge_info
{
tree lhs;
tree rhs;
tree *cond_equivalences;
unsigned int max_cond_equivalences;
};
static htab_t avail_exprs;
static VEC(tree,heap) *avail_exprs_stack;
static VEC(tree,heap) *stmts_to_rescan;
struct expr_hash_elt
{
tree lhs;
tree rhs;
tree stmt;
hashval_t hash;
};
static VEC(tree,heap) *const_and_copies_stack;
static bool cfg_altered;
static bitmap need_eh_cleanup;
struct opt_stats_d
{
long num_stmts;
long num_exprs_considered;
long num_re;
long num_const_prop;
long num_copy_prop;
};
static struct opt_stats_d opt_stats;
struct eq_expr_value
{
tree src;
tree dst;
};
static void optimize_stmt (struct dom_walk_data *,
basic_block bb,
block_stmt_iterator);
static tree lookup_avail_expr (tree, bool);
static hashval_t avail_expr_hash (const void *);
static hashval_t real_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);
static void record_const_or_copy (tree, tree);
static void record_equality (tree, tree);
static void record_equivalences_from_phis (basic_block);
static void record_equivalences_from_incoming_edge (basic_block);
static bool eliminate_redundant_computations (tree);
static void record_equivalences_from_stmt (tree, int, stmt_ann_t);
static void dom_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 (struct dom_walk_data *, basic_block);
static void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block);
static void remove_local_expressions_from_table (void);
static void restore_vars_to_original_value (void);
static edge single_incoming_edge_ignoring_loop_edges (basic_block);
static struct edge_info *
allocate_edge_info (edge e)
{
struct edge_info *edge_info;
edge_info = XCNEW (struct edge_info);
e->aux = edge_info;
return edge_info;
}
static void
free_all_edge_infos (void)
{
basic_block bb;
edge_iterator ei;
edge e;
FOR_EACH_BB (bb)
{
FOR_EACH_EDGE (e, ei, bb->preds)
{
struct edge_info *edge_info = (struct edge_info *) e->aux;
if (edge_info)
{
if (edge_info->cond_equivalences)
free (edge_info->cond_equivalences);
free (edge_info);
e->aux = NULL;
}
}
}
}
static unsigned int
tree_ssa_dominator_optimize (void)
{
struct dom_walk_data walk_data;
unsigned int i;
struct loops loops_info;
memset (&opt_stats, 0, sizeof (opt_stats));
avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free);
avail_exprs_stack = VEC_alloc (tree, heap, 20);
const_and_copies_stack = VEC_alloc (tree, heap, 20);
stmts_to_rescan = VEC_alloc (tree, heap, 20);
need_eh_cleanup = BITMAP_ALLOC (NULL);
walk_data.walk_stmts_backward = false;
walk_data.dom_direction = CDI_DOMINATORS;
walk_data.initialize_block_local_data = NULL;
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 = propagate_to_outgoing_edges;
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 = 0;
walk_data.interesting_blocks = NULL;
init_walk_dominator_tree (&walk_data);
calculate_dominance_info (CDI_DOMINATORS);
flow_loops_find (&loops_info);
mark_loop_exit_edges (&loops_info);
flow_loops_free (&loops_info);
cleanup_tree_cfg ();
calculate_dominance_info (CDI_DOMINATORS);
mark_dfs_back_edges ();
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
{
block_stmt_iterator bsi;
basic_block bb;
FOR_EACH_BB (bb)
{
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
update_stmt_if_modified (bsi_stmt (bsi));
}
}
update_ssa (TODO_update_ssa);
free_all_edge_infos ();
cfg_altered |= thread_through_all_blocks ();
if (!bitmap_empty_p (need_eh_cleanup))
{
cfg_altered |= tree_purge_all_dead_eh_edges (need_eh_cleanup);
bitmap_zero (need_eh_cleanup);
}
if (cfg_altered)
free_dominance_info (CDI_DOMINATORS);
for (i = 0; i < num_ssa_names; i++)
{
tree name = ssa_name (i);
tree value;
if (!name)
continue;
value = SSA_NAME_VALUE (name);
if (value && !is_gimple_min_invariant (value))
SSA_NAME_VALUE (name) = 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_FREE (need_eh_cleanup);
VEC_free (tree, heap, avail_exprs_stack);
VEC_free (tree, heap, const_and_copies_stack);
VEC_free (tree, heap, stmts_to_rescan);
return 0;
}
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 | PROP_alias,
0,
PROP_smt_usage,
0,
TODO_dump_func
| TODO_update_ssa
| TODO_cleanup_cfg
| TODO_verify_ssa
| TODO_update_smt_usage,
0
};
static void
canonicalize_comparison (tree condstmt)
{
tree cond = COND_EXPR_COND (condstmt);
tree op0;
tree op1;
enum tree_code code = TREE_CODE (cond);
if (!COMPARISON_CLASS_P (cond))
return;
op0 = TREE_OPERAND (cond, 0);
op1 = TREE_OPERAND (cond, 1);
if (tree_swap_operands_p (op0, op1, false))
{
if (code == LT_EXPR
|| code == GT_EXPR
|| code == LE_EXPR
|| code == GE_EXPR)
{
TREE_SET_CODE (cond, swap_tree_comparison (code));
swap_tree_operands (condstmt,
&TREE_OPERAND (cond, 0),
&TREE_OPERAND (cond, 1));
if (TREE_CODE_CLASS (TREE_CODE (op0))
!= TREE_CODE_CLASS (TREE_CODE (op1)))
update_stmt (condstmt);
}
}
}
static void
dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
VEC_safe_push (tree, heap, avail_exprs_stack, NULL_TREE);
VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
record_equivalences_from_incoming_edge (bb);
record_equivalences_from_phis (bb);
}
static void
initialize_hash_element (tree expr, tree lhs, struct expr_hash_elt *element)
{
if (COMPARISON_CLASS_P (expr) || TREE_CODE (expr) == TRUTH_NOT_EXPR)
{
element->stmt = NULL;
element->rhs = expr;
}
else if (TREE_CODE (expr) == COND_EXPR)
{
element->stmt = expr;
element->rhs = COND_EXPR_COND (expr);
}
else if (TREE_CODE (expr) == SWITCH_EXPR)
{
element->stmt = expr;
element->rhs = SWITCH_COND (expr);
}
else if (TREE_CODE (expr) == RETURN_EXPR && TREE_OPERAND (expr, 0))
{
element->stmt = expr;
element->rhs = TREE_OPERAND (TREE_OPERAND (expr, 0), 1);
}
else if (TREE_CODE (expr) == GOTO_EXPR)
{
element->stmt = expr;
element->rhs = GOTO_DESTINATION (expr);
}
else
{
element->stmt = expr;
element->rhs = TREE_OPERAND (expr, 1);
}
element->lhs = lhs;
element->hash = avail_expr_hash (element);
}
static void
remove_local_expressions_from_table (void)
{
while (VEC_length (tree, avail_exprs_stack) > 0)
{
struct expr_hash_elt element;
tree expr = VEC_pop (tree, avail_exprs_stack);
if (expr == NULL_TREE)
break;
initialize_hash_element (expr, NULL, &element);
htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
}
}
static void
restore_vars_to_original_value (void)
{
while (VEC_length (tree, const_and_copies_stack) > 0)
{
tree prev_value, dest;
dest = VEC_pop (tree, const_and_copies_stack);
if (dest == NULL)
break;
prev_value = VEC_pop (tree, const_and_copies_stack);
SSA_NAME_VALUE (dest) = prev_value;
}
}
static tree
simplify_stmt_for_jump_threading (tree stmt, tree within_stmt ATTRIBUTE_UNUSED)
{
return lookup_avail_expr (stmt, false);
}
static void
dom_thread_across_edge (struct dom_walk_data *walk_data, edge e)
{
if (! walk_data->global_data)
{
tree dummy_cond = build2 (NE_EXPR, boolean_type_node,
integer_zero_node, integer_zero_node);
dummy_cond = build3 (COND_EXPR, void_type_node, dummy_cond, NULL, NULL);
walk_data->global_data = dummy_cond;
}
thread_across_edge (walk_data->global_data, e, false,
&const_and_copies_stack,
simplify_stmt_for_jump_threading);
}
static void
dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
{
tree last;
if (single_succ_p (bb)
&& (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
&& potentially_threadable_block (single_succ (bb)))
{
dom_thread_across_edge (walk_data, single_succ_edge (bb));
}
else if ((last = last_stmt (bb))
&& TREE_CODE (last) == COND_EXPR
&& (COMPARISON_CLASS_P (COND_EXPR_COND (last))
|| TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME)
&& EDGE_COUNT (bb->succs) == 2
&& (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
&& (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)
{
edge true_edge, false_edge;
extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
if (potentially_threadable_block (true_edge->dest))
{
struct edge_info *edge_info;
unsigned int i;
VEC_safe_push (tree, heap, avail_exprs_stack, NULL_TREE);
VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
edge_info = (struct edge_info *) true_edge->aux;
if (edge_info)
{
tree *cond_equivalences = edge_info->cond_equivalences;
tree lhs = edge_info->lhs;
tree rhs = edge_info->rhs;
if (lhs && TREE_CODE (lhs) == SSA_NAME)
record_const_or_copy (lhs, rhs);
if (cond_equivalences)
for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
{
tree expr = cond_equivalences[i];
tree value = cond_equivalences[i + 1];
record_cond (expr, value);
}
}
dom_thread_across_edge (walk_data, true_edge);
remove_local_expressions_from_table ();
}
if (potentially_threadable_block (false_edge->dest))
{
struct edge_info *edge_info;
unsigned int i;
VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
edge_info = (struct edge_info *) false_edge->aux;
if (edge_info)
{
tree *cond_equivalences = edge_info->cond_equivalences;
tree lhs = edge_info->lhs;
tree rhs = edge_info->rhs;
if (lhs && TREE_CODE (lhs) == SSA_NAME)
record_const_or_copy (lhs, rhs);
if (cond_equivalences)
for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
{
tree expr = cond_equivalences[i];
tree value = cond_equivalences[i + 1];
record_cond (expr, value);
}
}
dom_thread_across_edge (walk_data, false_edge);
}
}
remove_local_expressions_from_table ();
restore_vars_to_original_value ();
while (VEC_length (tree, stmts_to_rescan) > 0)
{
tree stmt = VEC_last (tree, stmts_to_rescan);
basic_block stmt_bb = bb_for_stmt (stmt);
if (stmt_bb != bb)
break;
VEC_pop (tree, stmts_to_rescan);
mark_new_vars_to_rename (stmt);
}
}
static void
record_equivalences_from_phis (basic_block bb)
{
tree phi;
for (phi = phi_nodes (bb); phi; phi = PHI_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 (lhs == t)
continue;
if (rhs == NULL)
rhs = t;
else if (! operand_equal_for_phi_arg_p (rhs, t))
break;
}
if (!rhs)
rhs = lhs;
if (i == PHI_NUM_ARGS (phi)
&& may_propagate_copy (lhs, rhs))
SSA_NAME_VALUE (lhs) = rhs;
}
}
static edge
single_incoming_edge_ignoring_loop_edges (basic_block bb)
{
edge retval = NULL;
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
continue;
if (retval)
return NULL;
retval = e;
}
return retval;
}
static void
record_equivalences_from_incoming_edge (basic_block bb)
{
edge e;
basic_block parent;
struct edge_info *edge_info;
parent = get_immediate_dominator (CDI_DOMINATORS, bb);
e = single_incoming_edge_ignoring_loop_edges (bb);
if (e && e->src == parent)
{
unsigned int i;
edge_info = (struct edge_info *) e->aux;
if (edge_info)
{
tree lhs = edge_info->lhs;
tree rhs = edge_info->rhs;
tree *cond_equivalences = edge_info->cond_equivalences;
if (lhs)
record_equality (lhs, rhs);
if (cond_equivalences)
{
for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
{
tree expr = cond_equivalences[i];
tree value = cond_equivalences[i + 1];
record_cond (expr, value);
}
}
}
}
}
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, " Constants propagated: %6ld\n",
opt_stats.num_const_prop);
fprintf (file, " Copies propagated: %6ld\n",
opt_stats.num_copy_prop);
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_cond (tree cond, tree value)
{
struct expr_hash_elt *element = XCNEW (struct expr_hash_elt);
void **slot;
initialize_hash_element (cond, value, element);
slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
element->hash, INSERT);
if (*slot == NULL)
{
*slot = (void *) element;
VEC_safe_push (tree, heap, avail_exprs_stack, cond);
}
else
free (element);
}
static void
build_and_record_new_cond (enum tree_code new_code, tree op0, tree op1, tree *p)
{
*p = build2 (new_code, boolean_type_node, op0, op1);
p++;
*p = boolean_true_node;
}
static void
record_conditions (struct edge_info *edge_info, tree cond, tree inverted)
{
tree op0, op1;
if (!COMPARISON_CLASS_P (cond))
return;
op0 = TREE_OPERAND (cond, 0);
op1 = TREE_OPERAND (cond, 1);
switch (TREE_CODE (cond))
{
case LT_EXPR:
case GT_EXPR:
if (FLOAT_TYPE_P (TREE_TYPE (op0)))
{
edge_info->max_cond_equivalences = 12;
edge_info->cond_equivalences = XNEWVEC (tree, 12);
build_and_record_new_cond (ORDERED_EXPR, op0, op1,
&edge_info->cond_equivalences[8]);
build_and_record_new_cond (LTGT_EXPR, op0, op1,
&edge_info->cond_equivalences[10]);
}
else
{
edge_info->max_cond_equivalences = 8;
edge_info->cond_equivalences = XNEWVEC (tree, 8);
}
build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
? LE_EXPR : GE_EXPR),
op0, op1, &edge_info->cond_equivalences[4]);
build_and_record_new_cond (NE_EXPR, op0, op1,
&edge_info->cond_equivalences[6]);
break;
case GE_EXPR:
case LE_EXPR:
if (FLOAT_TYPE_P (TREE_TYPE (op0)))
{
edge_info->max_cond_equivalences = 6;
edge_info->cond_equivalences = XNEWVEC (tree, 6);
build_and_record_new_cond (ORDERED_EXPR, op0, op1,
&edge_info->cond_equivalences[4]);
}
else
{
edge_info->max_cond_equivalences = 4;
edge_info->cond_equivalences = XNEWVEC (tree, 4);
}
break;
case EQ_EXPR:
if (FLOAT_TYPE_P (TREE_TYPE (op0)))
{
edge_info->max_cond_equivalences = 10;
edge_info->cond_equivalences = XNEWVEC (tree, 10);
build_and_record_new_cond (ORDERED_EXPR, op0, op1,
&edge_info->cond_equivalences[8]);
}
else
{
edge_info->max_cond_equivalences = 8;
edge_info->cond_equivalences = XNEWVEC (tree, 8);
}
build_and_record_new_cond (LE_EXPR, op0, op1,
&edge_info->cond_equivalences[4]);
build_and_record_new_cond (GE_EXPR, op0, op1,
&edge_info->cond_equivalences[6]);
break;
case UNORDERED_EXPR:
edge_info->max_cond_equivalences = 16;
edge_info->cond_equivalences = XNEWVEC (tree, 16);
build_and_record_new_cond (NE_EXPR, op0, op1,
&edge_info->cond_equivalences[4]);
build_and_record_new_cond (UNLE_EXPR, op0, op1,
&edge_info->cond_equivalences[6]);
build_and_record_new_cond (UNGE_EXPR, op0, op1,
&edge_info->cond_equivalences[8]);
build_and_record_new_cond (UNEQ_EXPR, op0, op1,
&edge_info->cond_equivalences[10]);
build_and_record_new_cond (UNLT_EXPR, op0, op1,
&edge_info->cond_equivalences[12]);
build_and_record_new_cond (UNGT_EXPR, op0, op1,
&edge_info->cond_equivalences[14]);
break;
case UNLT_EXPR:
case UNGT_EXPR:
edge_info->max_cond_equivalences = 8;
edge_info->cond_equivalences = XNEWVEC (tree, 8);
build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
? UNLE_EXPR : UNGE_EXPR),
op0, op1, &edge_info->cond_equivalences[4]);
build_and_record_new_cond (NE_EXPR, op0, op1,
&edge_info->cond_equivalences[6]);
break;
case UNEQ_EXPR:
edge_info->max_cond_equivalences = 8;
edge_info->cond_equivalences = XNEWVEC (tree, 8);
build_and_record_new_cond (UNLE_EXPR, op0, op1,
&edge_info->cond_equivalences[4]);
build_and_record_new_cond (UNGE_EXPR, op0, op1,
&edge_info->cond_equivalences[6]);
break;
case LTGT_EXPR:
edge_info->max_cond_equivalences = 8;
edge_info->cond_equivalences = XNEWVEC (tree, 8);
build_and_record_new_cond (NE_EXPR, op0, op1,
&edge_info->cond_equivalences[4]);
build_and_record_new_cond (ORDERED_EXPR, op0, op1,
&edge_info->cond_equivalences[6]);
break;
default:
edge_info->max_cond_equivalences = 4;
edge_info->cond_equivalences = XNEWVEC (tree, 4);
break;
}
edge_info->cond_equivalences[0] = cond;
edge_info->cond_equivalences[1] = boolean_true_node;
edge_info->cond_equivalences[2] = inverted;
edge_info->cond_equivalences[3] = boolean_false_node;
}
static void
record_const_or_copy_1 (tree x, tree y, tree prev_x)
{
SSA_NAME_VALUE (x) = y;
VEC_reserve (tree, heap, const_and_copies_stack, 2);
VEC_quick_push (tree, const_and_copies_stack, prev_x);
VEC_quick_push (tree, const_and_copies_stack, x);
}
int
loop_depth_of_name (tree x)
{
tree defstmt;
basic_block defbb;
if (TREE_CODE (x) != SSA_NAME)
return 0;
defstmt = SSA_NAME_DEF_STMT (x);
defbb = bb_for_stmt (defstmt);
if (!defbb)
return 0;
return defbb->loop_depth;
}
static void
record_const_or_copy (tree x, tree y)
{
tree prev_x = SSA_NAME_VALUE (x);
if (TREE_CODE (y) == SSA_NAME)
{
tree tmp = SSA_NAME_VALUE (y);
if (tmp)
y = tmp;
}
record_const_or_copy_1 (x, y, prev_x);
}
static void
record_equality (tree x, tree y)
{
tree prev_x = NULL, prev_y = NULL;
if (TREE_CODE (x) == SSA_NAME)
prev_x = SSA_NAME_VALUE (x);
if (TREE_CODE (y) == SSA_NAME)
prev_y = SSA_NAME_VALUE (y);
if (TREE_INVARIANT (y))
;
else if (TREE_INVARIANT (x) || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
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 && TREE_CODE (prev_y) != VALUE_HANDLE)
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);
}
static bool
simple_iv_increment_p (tree stmt)
{
tree lhs, rhs, preinc, phi;
unsigned i;
if (TREE_CODE (stmt) != MODIFY_EXPR)
return false;
lhs = TREE_OPERAND (stmt, 0);
if (TREE_CODE (lhs) != SSA_NAME)
return false;
rhs = TREE_OPERAND (stmt, 1);
if (TREE_CODE (rhs) != PLUS_EXPR
&& TREE_CODE (rhs) != MINUS_EXPR)
return false;
preinc = TREE_OPERAND (rhs, 0);
if (TREE_CODE (preinc) != SSA_NAME)
return false;
phi = SSA_NAME_DEF_STMT (preinc);
if (TREE_CODE (phi) != PHI_NODE)
return false;
for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
if (PHI_ARG_DEF (phi, i) == lhs)
return true;
return false;
}
static void
cprop_into_successor_phis (basic_block bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
{
tree phi;
int indx;
if (e->flags & EDGE_ABNORMAL)
continue;
phi = phi_nodes (e->dest);
if (! phi)
continue;
indx = e->dest_idx;
for ( ; phi; phi = PHI_CHAIN (phi))
{
tree new;
use_operand_p orig_p;
tree orig;
orig_p = PHI_ARG_DEF_PTR (phi, indx);
orig = USE_FROM_PTR (orig_p);
if (TREE_CODE (orig) != SSA_NAME)
continue;
new = SSA_NAME_VALUE (orig);
if (new
&& new != orig
&& (TREE_CODE (new) == SSA_NAME
|| is_gimple_min_invariant (new))
&& may_propagate_copy (orig, new))
propagate_value (orig_p, new);
}
}
}
static void
record_edge_info (basic_block bb)
{
block_stmt_iterator bsi = bsi_last (bb);
struct edge_info *edge_info;
if (! bsi_end_p (bsi))
{
tree stmt = bsi_stmt (bsi);
if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
{
tree cond = SWITCH_COND (stmt);
if (TREE_CODE (cond) == SSA_NAME)
{
tree labels = SWITCH_LABELS (stmt);
int i, n_labels = TREE_VEC_LENGTH (labels);
tree *info = XCNEWVEC (tree, last_basic_block);
edge e;
edge_iterator ei;
for (i = 0; i < n_labels; i++)
{
tree label = TREE_VEC_ELT (labels, i);
basic_block target_bb = label_to_block (CASE_LABEL (label));
if (CASE_HIGH (label)
|| !CASE_LOW (label)
|| info[target_bb->index])
info[target_bb->index] = error_mark_node;
else
info[target_bb->index] = label;
}
FOR_EACH_EDGE (e, ei, bb->succs)
{
basic_block target_bb = e->dest;
tree node = info[target_bb->index];
if (node != NULL && node != error_mark_node)
{
tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
edge_info = allocate_edge_info (e);
edge_info->lhs = cond;
edge_info->rhs = x;
}
}
free (info);
}
}
if (stmt && TREE_CODE (stmt) == COND_EXPR)
{
tree cond = COND_EXPR_COND (stmt);
edge true_edge;
edge false_edge;
extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
if (SSA_VAR_P (cond))
{
struct edge_info *edge_info;
edge_info = allocate_edge_info (true_edge);
edge_info->lhs = cond;
edge_info->rhs = constant_boolean_node (1, TREE_TYPE (cond));
edge_info = allocate_edge_info (false_edge);
edge_info->lhs = cond;
edge_info->rhs = constant_boolean_node (0, TREE_TYPE (cond));
}
else if (COMPARISON_CLASS_P (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)
{
edge_info = allocate_edge_info (true_edge);
edge_info->lhs = op0;
edge_info->rhs = (integer_zerop (op1)
? boolean_false_node
: boolean_true_node);
edge_info = allocate_edge_info (false_edge);
edge_info->lhs = op0;
edge_info->rhs = (integer_zerop (op1)
? boolean_true_node
: boolean_false_node);
}
else
{
edge_info = allocate_edge_info (true_edge);
edge_info->lhs = op0;
edge_info->rhs = (integer_zerop (op1)
? boolean_true_node
: boolean_false_node);
edge_info = allocate_edge_info (false_edge);
edge_info->lhs = op0;
edge_info->rhs = (integer_zerop (op1)
? boolean_false_node
: boolean_true_node);
}
}
else if (is_gimple_min_invariant (op0)
&& (TREE_CODE (op1) == SSA_NAME
|| is_gimple_min_invariant (op1)))
{
tree inverted = invert_truthvalue (cond);
struct edge_info *edge_info;
edge_info = allocate_edge_info (true_edge);
record_conditions (edge_info, cond, inverted);
if (TREE_CODE (cond) == EQ_EXPR)
{
edge_info->lhs = op1;
edge_info->rhs = op0;
}
edge_info = allocate_edge_info (false_edge);
record_conditions (edge_info, inverted, cond);
if (TREE_CODE (cond) == NE_EXPR)
{
edge_info->lhs = op1;
edge_info->rhs = op0;
}
}
else if (TREE_CODE (op0) == SSA_NAME
&& (is_gimple_min_invariant (op1)
|| TREE_CODE (op1) == SSA_NAME))
{
tree inverted = invert_truthvalue (cond);
struct edge_info *edge_info;
edge_info = allocate_edge_info (true_edge);
record_conditions (edge_info, cond, inverted);
if (TREE_CODE (cond) == EQ_EXPR)
{
edge_info->lhs = op0;
edge_info->rhs = op1;
}
edge_info = allocate_edge_info (false_edge);
record_conditions (edge_info, inverted, cond);
if (TREE_CODE (cond) == NE_EXPR)
{
edge_info->lhs = op0;
edge_info->rhs = op1;
}
}
}
}
}
}
static void
propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb)
{
record_edge_info (bb);
cprop_into_successor_phis (bb);
}
static bool
eliminate_redundant_computations (tree stmt)
{
tree *expr_p, def = NULL_TREE;
bool insert = true;
tree cached_lhs;
bool retval = false;
bool modify_expr_p = false;
if (TREE_CODE (stmt) == MODIFY_EXPR)
def = TREE_OPERAND (stmt, 0);
if (! def
|| TREE_CODE (def) != SSA_NAME
|| SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
|| !ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF)
|| simple_iv_increment_p (stmt))
insert = false;
cached_lhs = lookup_avail_expr (stmt, 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);
modify_expr_p = true;
}
else
{
expr_p = &TREE_OPERAND (stmt, 1);
modify_expr_p = true;
}
if (cached_lhs
&& ((TREE_CODE (cached_lhs) != SSA_NAME
&& (modify_expr_p
|| tree_ssa_useless_type_conversion_1 (TREE_TYPE (*expr_p),
TREE_TYPE (cached_lhs))))
|| may_propagate_copy (*expr_p, cached_lhs)))
{
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
gcc_assert (TREE_CODE (cached_lhs) == SSA_NAME
|| is_gimple_min_invariant (cached_lhs));
#endif
if (TREE_CODE (cached_lhs) == ADDR_EXPR
|| (POINTER_TYPE_P (TREE_TYPE (*expr_p))
&& is_gimple_min_invariant (cached_lhs)))
retval = true;
if (modify_expr_p
&& !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*expr_p),
TREE_TYPE (cached_lhs)))
cached_lhs = fold_convert (TREE_TYPE (*expr_p), cached_lhs);
propagate_tree_value (expr_p, cached_lhs);
mark_stmt_modified (stmt);
}
return retval;
}
static void
record_equivalences_from_stmt (tree stmt,
int may_optimize_p,
stmt_ann_t ann)
{
tree lhs = TREE_OPERAND (stmt, 0);
enum tree_code lhs_code = TREE_CODE (lhs);
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)))
SSA_NAME_VALUE (lhs) = rhs;
}
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;
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)
{
new = build2 (MODIFY_EXPR, TREE_TYPE (stmt), rhs, lhs);
create_ssa_artficial_load_stmt (new, stmt);
lookup_avail_expr (new, true);
}
}
}
static bool
cprop_operand (tree stmt, use_operand_p op_p)
{
bool may_have_exposed_new_symbols = false;
tree val;
tree op = USE_FROM_PTR (op_p);
val = SSA_NAME_VALUE (op);
if (val && val != op && TREE_CODE (val) != VALUE_HANDLE)
{
tree op_type, val_type;
if (!is_gimple_reg (op)
&& (TREE_CODE (val) != SSA_NAME
|| is_gimple_reg (val)
|| get_virtual_var (val) != get_virtual_var (op)))
return false;
if (TREE_CODE (stmt) == ASM_EXPR
&& !may_propagate_copy_into_asm (op))
return false;
op_type = TREE_TYPE (op);
val_type = TREE_TYPE (val);
while (POINTER_TYPE_P (op_type) && POINTER_TYPE_P (val_type))
{
op_type = TREE_TYPE (op_type);
val_type = TREE_TYPE (val_type);
}
if (TREE_CODE (val) != SSA_NAME)
{
if (!lang_hooks.types_compatible_p (op_type, val_type))
{
val = fold_convert (TREE_TYPE (op), val);
if (!is_gimple_min_invariant (val))
return false;
}
}
else if (!may_propagate_copy (op, val))
return false;
if (loop_depth_of_name (val) > loop_depth_of_name (op))
return false;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " Replaced '");
print_generic_expr (dump_file, op, dump_flags);
fprintf (dump_file, "' with %s '",
(TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
print_generic_expr (dump_file, val, dump_flags);
fprintf (dump_file, "'\n");
}
if (TREE_CODE (val) == ADDR_EXPR
|| (POINTER_TYPE_P (TREE_TYPE (op))
&& is_gimple_min_invariant (val)))
may_have_exposed_new_symbols = true;
if (TREE_CODE (val) != SSA_NAME)
opt_stats.num_const_prop++;
else
opt_stats.num_copy_prop++;
propagate_value (op_p, val);
mark_stmt_modified (stmt);
}
return may_have_exposed_new_symbols;
}
static bool
cprop_into_stmt (tree stmt)
{
bool may_have_exposed_new_symbols = false;
use_operand_p op_p;
ssa_op_iter iter;
FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
{
if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
may_have_exposed_new_symbols |= cprop_operand (stmt, op_p);
}
return may_have_exposed_new_symbols;
}
static void
optimize_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb, block_stmt_iterator si)
{
stmt_ann_t ann;
tree stmt, old_stmt;
bool may_optimize_p;
bool may_have_exposed_new_symbols = false;
old_stmt = stmt = bsi_stmt (si);
if (TREE_CODE (stmt) == COND_EXPR)
canonicalize_comparison (stmt);
update_stmt_if_modified (stmt);
ann = stmt_ann (stmt);
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);
if (ann->modified)
{
tree rhs;
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);
}
}
rhs = get_rhs (stmt);
if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
recompute_tree_invariant_for_addr_expr (rhs);
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 (stmt);
if (TREE_CODE (stmt) == MODIFY_EXPR)
record_equivalences_from_stmt (stmt,
may_optimize_p,
ann);
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, val))
cfg_altered = true;
if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
{
bitmap_set_bit (need_eh_cleanup, bb->index);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " Flagged to clear EH edges.\n");
}
}
if (may_have_exposed_new_symbols)
VEC_safe_push (tree, heap, stmts_to_rescan, bsi_stmt (si));
}
static tree
lookup_avail_expr (tree stmt, bool insert)
{
void **slot;
tree lhs;
tree temp;
struct expr_hash_elt *element = XNEW (struct expr_hash_elt);
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;
}
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;
VEC_safe_push (tree, heap, avail_exprs_stack,
stmt ? stmt : element->rhs);
return NULL_TREE;
}
lhs = ((struct expr_hash_elt *)*slot)->lhs;
if (TREE_CODE (lhs) == SSA_NAME)
{
temp = SSA_NAME_VALUE (lhs);
if (temp && TREE_CODE (temp) != VALUE_HANDLE)
lhs = temp;
}
free (element);
return lhs;
}
static hashval_t
avail_expr_hash (const void *p)
{
tree stmt = ((struct expr_hash_elt *)p)->stmt;
tree rhs = ((struct expr_hash_elt *)p)->rhs;
tree vuse;
ssa_op_iter iter;
hashval_t val = 0;
val = iterative_hash_expr (rhs, val);
if (!stmt || !stmt_ann (stmt))
return val;
FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
val = iterative_hash_expr (vuse, val);
return val;
}
static hashval_t
real_avail_expr_hash (const void *p)
{
return ((const struct expr_hash_elt *)p)->hash;
}
static int
avail_expr_eq (const void *p1, const void *p2)
{
tree stmt1 = ((struct expr_hash_elt *)p1)->stmt;
tree rhs1 = ((struct expr_hash_elt *)p1)->rhs;
tree stmt2 = ((struct expr_hash_elt *)p2)->stmt;
tree rhs2 = ((struct expr_hash_elt *)p2)->rhs;
if (rhs1 == rhs2 && stmt1 == stmt2)
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))
{
bool ret = compare_ssa_operands_equal (stmt1, stmt2, SSA_OP_VUSE);
gcc_assert (!ret || ((struct expr_hash_elt *)p1)->hash
== ((struct expr_hash_elt *)p2)->hash);
return ret;
}
return false;
}
static tree
degenerate_phi_result (tree phi)
{
tree lhs = PHI_RESULT (phi);
tree val = NULL;
int i;
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
tree arg = PHI_ARG_DEF (phi, i);
if (arg == lhs)
continue;
else if (!val)
val = arg;
else if (!operand_equal_p (arg, val, 0))
break;
}
return (i == PHI_NUM_ARGS (phi) ? val : NULL);
}
static void
remove_stmt_or_phi (tree t)
{
if (TREE_CODE (t) == PHI_NODE)
remove_phi_node (t, NULL);
else
{
block_stmt_iterator bsi = bsi_for_stmt (t);
bsi_remove (&bsi, true);
}
}
static tree
get_rhs_or_phi_arg (tree t)
{
if (TREE_CODE (t) == PHI_NODE)
return degenerate_phi_result (t);
else if (TREE_CODE (t) == MODIFY_EXPR)
return TREE_OPERAND (t, 1);
gcc_unreachable ();
}
static tree
get_lhs_or_phi_result (tree t)
{
if (TREE_CODE (t) == PHI_NODE)
return PHI_RESULT (t);
else if (TREE_CODE (t) == MODIFY_EXPR)
return TREE_OPERAND (t, 0);
gcc_unreachable ();
}
static void
propagate_rhs_into_lhs (tree stmt, tree lhs, tree rhs, bitmap interesting_names)
{
if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
&& (TREE_CODE (rhs) != SSA_NAME
|| ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
&& may_propagate_copy (lhs, rhs)
&& loop_depth_of_name (lhs) >= loop_depth_of_name (rhs))
{
use_operand_p use_p;
imm_use_iterator iter;
tree use_stmt;
bool all = true;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " Replacing '");
print_generic_expr (dump_file, lhs, dump_flags);
fprintf (dump_file, "' with %s '",
(TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable"));
print_generic_expr (dump_file, rhs, dump_flags);
fprintf (dump_file, "'\n");
}
FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
{
if (TREE_CODE (use_stmt) == ASM_EXPR
&& ! may_propagate_copy_into_asm (lhs))
{
all = false;
continue;
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " Original statement:");
print_generic_expr (dump_file, use_stmt, dump_flags);
fprintf (dump_file, "\n");
}
FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
propagate_value (use_p, rhs);
if (TREE_CODE (use_stmt) == PHI_NODE
|| (! is_gimple_reg (lhs)
&& TREE_CODE (rhs) == SSA_NAME
&& SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs)))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " Updated statement:");
print_generic_expr (dump_file, use_stmt, dump_flags);
fprintf (dump_file, "\n");
}
if (TREE_CODE (use_stmt) == PHI_NODE)
{
tree result = get_lhs_or_phi_result (use_stmt);
bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
}
continue;
}
fold_stmt_inplace (use_stmt);
mark_new_vars_to_rename (use_stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " Updated statement:");
print_generic_expr (dump_file, use_stmt, dump_flags);
fprintf (dump_file, "\n");
}
if (TREE_CODE (use_stmt) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (use_stmt, 1)) == ADDR_EXPR)
recompute_tree_invariant_for_addr_expr (TREE_OPERAND (use_stmt, 1));
if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
{
bitmap_set_bit (need_eh_cleanup, bb_for_stmt (use_stmt)->index);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " Flagged to clear EH edges.\n");
}
if (TREE_CODE (use_stmt) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (use_stmt, 0)) == SSA_NAME
&& (TREE_CODE (TREE_OPERAND (use_stmt, 1)) == SSA_NAME
|| is_gimple_min_invariant (TREE_OPERAND (use_stmt, 1))))
{
tree result = get_lhs_or_phi_result (use_stmt);
bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
}
else if (TREE_CODE (use_stmt) == COND_EXPR
|| TREE_CODE (use_stmt) == SWITCH_EXPR
|| TREE_CODE (use_stmt) == GOTO_EXPR)
{
tree val;
if (TREE_CODE (use_stmt) == COND_EXPR)
val = COND_EXPR_COND (use_stmt);
else if (TREE_CODE (use_stmt) == SWITCH_EXPR)
val = SWITCH_COND (use_stmt);
else
val = GOTO_DESTINATION (use_stmt);
if (is_gimple_min_invariant (val))
{
basic_block bb = bb_for_stmt (use_stmt);
edge te = find_taken_edge (bb, val);
edge_iterator ei;
edge e;
block_stmt_iterator bsi;
for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
{
if (e != te)
{
tree phi;
for (phi = phi_nodes (e->dest);
phi;
phi = PHI_CHAIN (phi))
{
tree result = PHI_RESULT (phi);
int version = SSA_NAME_VERSION (result);
bitmap_set_bit (interesting_names, version);
}
te->probability += e->probability;
te->count += e->count;
remove_edge (e);
cfg_altered = 1;
}
else
ei_next (&ei);
}
bsi = bsi_last (bb_for_stmt (use_stmt));
bsi_remove (&bsi, true);
te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
te->flags &= ~EDGE_ABNORMAL;
te->flags |= EDGE_FALLTHRU;
if (te->probability > REG_BR_PROB_BASE)
te->probability = REG_BR_PROB_BASE;
}
}
}
gcc_assert (!all || has_zero_uses (lhs));
if (all)
remove_stmt_or_phi (stmt);
}
}
static void
eliminate_const_or_copy (tree t, bitmap interesting_names)
{
tree lhs = get_lhs_or_phi_result (t);
tree rhs;
int version = SSA_NAME_VERSION (lhs);
if (has_zero_uses (lhs))
{
bitmap_clear_bit (interesting_names, version);
remove_stmt_or_phi (t);
return;
}
rhs = get_rhs_or_phi_arg (t);
if (!rhs)
{
bitmap_clear_bit (interesting_names, version);
return;
}
propagate_rhs_into_lhs (t, lhs, rhs, interesting_names);
bitmap_clear_bit (interesting_names, version);
}
static void
eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names)
{
tree phi, next;
basic_block son;
for (phi = phi_nodes (bb); phi; phi = next)
{
next = PHI_CHAIN (phi);
eliminate_const_or_copy (phi, interesting_names);
}
for (son = first_dom_son (CDI_DOMINATORS, bb);
son;
son = next_dom_son (CDI_DOMINATORS, son))
eliminate_degenerate_phis_1 (son, interesting_names);
}
static unsigned int
eliminate_degenerate_phis (void)
{
bitmap interesting_names;
bitmap interesting_names1;
need_eh_cleanup = BITMAP_ALLOC (NULL);
interesting_names = BITMAP_ALLOC (NULL);
interesting_names1 = BITMAP_ALLOC (NULL);
calculate_dominance_info (CDI_DOMINATORS);
eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names);
while (!bitmap_empty_p (interesting_names))
{
unsigned int i;
bitmap_iterator bi;
bitmap_copy (interesting_names1, interesting_names);
EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
{
tree name = ssa_name (i);
if (name)
eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)),
interesting_names);
}
}
if (!bitmap_empty_p (need_eh_cleanup))
{
cfg_altered |= tree_purge_all_dead_eh_edges (need_eh_cleanup);
BITMAP_FREE (need_eh_cleanup);
}
BITMAP_FREE (interesting_names);
BITMAP_FREE (interesting_names1);
if (cfg_altered)
free_dominance_info (CDI_DOMINATORS);
return 0;
}
struct tree_opt_pass pass_phi_only_cprop =
{
"phicprop",
gate_dominator,
eliminate_degenerate_phis,
NULL,
NULL,
0,
TV_TREE_PHI_CPROP,
PROP_cfg | PROP_ssa | PROP_alias,
0,
PROP_smt_usage,
0,
TODO_cleanup_cfg | TODO_dump_func
| TODO_ggc_collect | TODO_verify_ssa
| TODO_verify_stmts | TODO_update_smt_usage
| TODO_update_ssa,
0
};