tree-ssa-propagate.c [plain text]
#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 "expr.h"
#include "function.h"
#include "diagnostic.h"
#include "timevar.h"
#include "tree-dump.h"
#include "tree-flow.h"
#include "tree-pass.h"
#include "tree-ssa-propagate.h"
#include "langhooks.h"
#include "varray.h"
#include "vec.h"
static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt;
static ssa_prop_visit_phi_fn ssa_prop_visit_phi;
#define STMT_IN_SSA_EDGE_WORKLIST(T) TREE_DEPRECATED (T)
static sbitmap executable_blocks;
static VEC(basic_block,heap) *cfg_blocks;
static unsigned int cfg_blocks_num = 0;
static int cfg_blocks_tail;
static int cfg_blocks_head;
static sbitmap bb_in_list;
static GTY(()) VEC(tree,gc) *interesting_ssa_edges;
static GTY(()) VEC(tree,gc) *varying_ssa_edges;
static inline bool
cfg_blocks_empty_p (void)
{
return (cfg_blocks_num == 0);
}
static void
cfg_blocks_add (basic_block bb)
{
bool head = false;
gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR);
gcc_assert (!TEST_BIT (bb_in_list, bb->index));
if (cfg_blocks_empty_p ())
{
cfg_blocks_tail = cfg_blocks_head = 0;
cfg_blocks_num = 1;
}
else
{
cfg_blocks_num++;
if (cfg_blocks_num > VEC_length (basic_block, cfg_blocks))
{
cfg_blocks_tail = VEC_length (basic_block, cfg_blocks);
cfg_blocks_head = 0;
VEC_safe_grow (basic_block, heap, cfg_blocks, 2 * cfg_blocks_tail);
}
else if (EDGE_COUNT (bb->preds)
>= EDGE_COUNT (VEC_index (basic_block, cfg_blocks,
cfg_blocks_head)->preds))
cfg_blocks_tail = ((cfg_blocks_tail + 1)
% VEC_length (basic_block, cfg_blocks));
else
{
if (cfg_blocks_head == 0)
cfg_blocks_head = VEC_length (basic_block, cfg_blocks);
--cfg_blocks_head;
head = true;
}
}
VEC_replace (basic_block, cfg_blocks,
head ? cfg_blocks_head : cfg_blocks_tail,
bb);
SET_BIT (bb_in_list, bb->index);
}
static basic_block
cfg_blocks_get (void)
{
basic_block bb;
bb = VEC_index (basic_block, cfg_blocks, cfg_blocks_head);
gcc_assert (!cfg_blocks_empty_p ());
gcc_assert (bb);
cfg_blocks_head = ((cfg_blocks_head + 1)
% VEC_length (basic_block, cfg_blocks));
--cfg_blocks_num;
RESET_BIT (bb_in_list, bb->index);
return bb;
}
static void
add_ssa_edge (tree var, bool is_varying)
{
imm_use_iterator iter;
use_operand_p use_p;
FOR_EACH_IMM_USE_FAST (use_p, iter, var)
{
tree use_stmt = USE_STMT (use_p);
if (!DONT_SIMULATE_AGAIN (use_stmt)
&& !STMT_IN_SSA_EDGE_WORKLIST (use_stmt))
{
STMT_IN_SSA_EDGE_WORKLIST (use_stmt) = 1;
if (is_varying)
VEC_safe_push (tree, gc, varying_ssa_edges, use_stmt);
else
VEC_safe_push (tree, gc, interesting_ssa_edges, use_stmt);
}
}
}
static void
add_control_edge (edge e)
{
basic_block bb = e->dest;
if (bb == EXIT_BLOCK_PTR)
return;
if (e->flags & EDGE_EXECUTABLE)
return;
e->flags |= EDGE_EXECUTABLE;
if (TEST_BIT (bb_in_list, bb->index))
return;
cfg_blocks_add (bb);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n",
e->src->index, e->dest->index);
}
static void
simulate_stmt (tree stmt)
{
enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING;
edge taken_edge = NULL;
tree output_name = NULL_TREE;
if (DONT_SIMULATE_AGAIN (stmt))
return;
if (TREE_CODE (stmt) == PHI_NODE)
{
val = ssa_prop_visit_phi (stmt);
output_name = PHI_RESULT (stmt);
}
else
val = ssa_prop_visit_stmt (stmt, &taken_edge, &output_name);
if (val == SSA_PROP_VARYING)
{
DONT_SIMULATE_AGAIN (stmt) = 1;
if (output_name)
add_ssa_edge (output_name, true);
if (stmt_ends_bb_p (stmt))
{
edge e;
edge_iterator ei;
basic_block bb = bb_for_stmt (stmt);
FOR_EACH_EDGE (e, ei, bb->succs)
add_control_edge (e);
}
}
else if (val == SSA_PROP_INTERESTING)
{
if (output_name)
add_ssa_edge (output_name, false);
if (taken_edge)
add_control_edge (taken_edge);
}
}
static void
process_ssa_edge_worklist (VEC(tree,gc) **worklist)
{
while (VEC_length (tree, *worklist) > 0)
{
basic_block bb;
tree stmt = VEC_pop (tree, *worklist);
if (!STMT_IN_SSA_EDGE_WORKLIST (stmt))
continue;
STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
print_generic_stmt (dump_file, stmt, dump_flags);
}
bb = bb_for_stmt (stmt);
if (TREE_CODE (stmt) == PHI_NODE
|| TEST_BIT (executable_blocks, bb->index))
simulate_stmt (stmt);
}
}
static void
simulate_block (basic_block block)
{
tree phi;
if (block == EXIT_BLOCK_PTR)
return;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nSimulating block %d\n", block->index);
for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
simulate_stmt (phi);
if (!TEST_BIT (executable_blocks, block->index))
{
block_stmt_iterator j;
unsigned int normal_edge_count;
edge e, normal_edge;
edge_iterator ei;
SET_BIT (executable_blocks, block->index);
for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j))
{
tree stmt = bsi_stmt (j);
if (STMT_IN_SSA_EDGE_WORKLIST (stmt))
STMT_IN_SSA_EDGE_WORKLIST (stmt) = 0;
simulate_stmt (stmt);
}
normal_edge_count = 0;
normal_edge = NULL;
FOR_EACH_EDGE (e, ei, block->succs)
{
if (e->flags & EDGE_ABNORMAL)
add_control_edge (e);
else
{
normal_edge_count++;
normal_edge = e;
}
}
if (normal_edge_count == 1)
add_control_edge (normal_edge);
}
}
static void
ssa_prop_init (void)
{
edge e;
edge_iterator ei;
basic_block bb;
size_t i;
interesting_ssa_edges = VEC_alloc (tree, gc, 20);
varying_ssa_edges = VEC_alloc (tree, gc, 20);
executable_blocks = sbitmap_alloc (last_basic_block);
sbitmap_zero (executable_blocks);
bb_in_list = sbitmap_alloc (last_basic_block);
sbitmap_zero (bb_in_list);
if (dump_file && (dump_flags & TDF_DETAILS))
dump_immediate_uses (dump_file);
cfg_blocks = VEC_alloc (basic_block, heap, 20);
VEC_safe_grow (basic_block, heap, cfg_blocks, 20);
for (i = 1; i < num_ssa_names; i++)
if (ssa_name (i))
SSA_NAME_VALUE (ssa_name (i)) = NULL_TREE;
FOR_ALL_BB (bb)
{
block_stmt_iterator si;
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si)) = 0;
FOR_EACH_EDGE (e, ei, bb->succs)
e->flags &= ~EDGE_EXECUTABLE;
}
FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
add_control_edge (e);
}
static void
ssa_prop_fini (void)
{
VEC_free (tree, gc, interesting_ssa_edges);
VEC_free (tree, gc, varying_ssa_edges);
VEC_free (basic_block, heap, cfg_blocks);
cfg_blocks = NULL;
sbitmap_free (bb_in_list);
sbitmap_free (executable_blocks);
}
tree
get_rhs (tree stmt)
{
enum tree_code code = TREE_CODE (stmt);
switch (code)
{
case RETURN_EXPR:
stmt = TREE_OPERAND (stmt, 0);
if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR)
return stmt;
case MODIFY_EXPR:
stmt = TREE_OPERAND (stmt, 1);
if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
return TREE_OPERAND (stmt, 0);
else
return stmt;
case COND_EXPR:
return COND_EXPR_COND (stmt);
case SWITCH_EXPR:
return SWITCH_COND (stmt);
case GOTO_EXPR:
return GOTO_DESTINATION (stmt);
case LABEL_EXPR:
return LABEL_EXPR_LABEL (stmt);
default:
return stmt;
}
}
bool
set_rhs (tree *stmt_p, tree expr)
{
tree stmt = *stmt_p, op;
enum tree_code code = TREE_CODE (expr);
stmt_ann_t ann;
tree var;
ssa_op_iter iter;
if (TREE_CODE_CLASS (code) == tcc_binary)
{
if (!is_gimple_val (TREE_OPERAND (expr, 0))
|| !is_gimple_val (TREE_OPERAND (expr, 1)))
return false;
}
else if (TREE_CODE_CLASS (code) == tcc_unary)
{
if (!is_gimple_val (TREE_OPERAND (expr, 0)))
return false;
}
else if (code == ADDR_EXPR)
{
if (TREE_CODE (TREE_OPERAND (expr, 0)) == ARRAY_REF
&& !is_gimple_val (TREE_OPERAND (TREE_OPERAND (expr, 0), 1)))
return false;
}
else if (code == COMPOUND_EXPR
|| code == MODIFY_EXPR)
return false;
if (EXPR_HAS_LOCATION (stmt)
&& EXPR_P (expr)
&& ! EXPR_HAS_LOCATION (expr)
&& TREE_SIDE_EFFECTS (expr)
&& TREE_CODE (expr) != LABEL_EXPR)
SET_EXPR_LOCATION (expr, EXPR_LOCATION (stmt));
switch (TREE_CODE (stmt))
{
case RETURN_EXPR:
op = TREE_OPERAND (stmt, 0);
if (TREE_CODE (op) != MODIFY_EXPR)
{
TREE_OPERAND (stmt, 0) = expr;
break;
}
stmt = op;
case MODIFY_EXPR:
op = TREE_OPERAND (stmt, 1);
if (TREE_CODE (op) == WITH_SIZE_EXPR)
stmt = op;
TREE_OPERAND (stmt, 1) = expr;
break;
case COND_EXPR:
if (!is_gimple_condexpr (expr))
return false;
COND_EXPR_COND (stmt) = expr;
break;
case SWITCH_EXPR:
SWITCH_COND (stmt) = expr;
break;
case GOTO_EXPR:
GOTO_DESTINATION (stmt) = expr;
break;
case LABEL_EXPR:
LABEL_EXPR_LABEL (stmt) = expr;
break;
default:
ann = stmt_ann (stmt);
*stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt ();
(*stmt_p)->common.ann = (tree_ann_t) ann;
if (in_ssa_p
&& TREE_SIDE_EFFECTS (expr))
{
FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_DEFS)
{
if (TREE_CODE (var) == SSA_NAME)
SSA_NAME_DEF_STMT (var) = *stmt_p;
}
}
break;
}
return true;
}
void
ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt,
ssa_prop_visit_phi_fn visit_phi)
{
ssa_prop_visit_stmt = visit_stmt;
ssa_prop_visit_phi = visit_phi;
ssa_prop_init ();
while (!cfg_blocks_empty_p ()
|| VEC_length (tree, interesting_ssa_edges) > 0
|| VEC_length (tree, varying_ssa_edges) > 0)
{
if (!cfg_blocks_empty_p ())
{
basic_block dest_block = cfg_blocks_get ();
simulate_block (dest_block);
}
process_ssa_edge_worklist (&varying_ssa_edges);
process_ssa_edge_worklist (&interesting_ssa_edges);
}
ssa_prop_fini ();
}
tree
first_vdef (tree stmt)
{
ssa_op_iter iter;
tree op;
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
return (op);
gcc_unreachable ();
}
bool
stmt_makes_single_load (tree stmt)
{
tree rhs;
if (TREE_CODE (stmt) != MODIFY_EXPR)
return false;
if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VUSE))
return false;
rhs = TREE_OPERAND (stmt, 1);
STRIP_NOPS (rhs);
return (!TREE_THIS_VOLATILE (rhs)
&& (DECL_P (rhs)
|| REFERENCE_CLASS_P (rhs)));
}
bool
stmt_makes_single_store (tree stmt)
{
tree lhs;
if (TREE_CODE (stmt) != MODIFY_EXPR)
return false;
if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF))
return false;
lhs = TREE_OPERAND (stmt, 0);
STRIP_NOPS (lhs);
return (!TREE_THIS_VOLATILE (lhs)
&& (DECL_P (lhs)
|| REFERENCE_CLASS_P (lhs)));
}
prop_value_t *
get_value_loaded_by (tree stmt, prop_value_t *values)
{
ssa_op_iter i;
tree vuse;
prop_value_t *prev_val = NULL;
prop_value_t *val = NULL;
FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES)
{
val = &values[SSA_NAME_VERSION (vuse)];
if (prev_val && prev_val->value != val->value)
return NULL;
prev_val = val;
}
return val;
}
struct prop_stats_d
{
long num_const_prop;
long num_copy_prop;
long num_pred_folded;
};
static struct prop_stats_d prop_stats;
bool
replace_uses_in (tree stmt, bool *replaced_addresses_p,
prop_value_t *prop_value)
{
bool replaced = false;
use_operand_p use;
ssa_op_iter iter;
FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
{
tree tuse = USE_FROM_PTR (use);
tree val = prop_value[SSA_NAME_VERSION (tuse)].value;
if (val == tuse || val == NULL_TREE)
continue;
if (TREE_CODE (stmt) == ASM_EXPR
&& !may_propagate_copy_into_asm (tuse))
continue;
if (!may_propagate_copy (tuse, val))
continue;
if (TREE_CODE (val) != SSA_NAME)
prop_stats.num_const_prop++;
else
prop_stats.num_copy_prop++;
propagate_value (use, val);
replaced = true;
if (POINTER_TYPE_P (TREE_TYPE (tuse)) && replaced_addresses_p)
*replaced_addresses_p = true;
}
return replaced;
}
static bool
replace_vuses_in (tree stmt, bool *replaced_addresses_p,
prop_value_t *prop_value)
{
bool replaced = false;
ssa_op_iter iter;
use_operand_p vuse;
if (stmt_makes_single_load (stmt))
{
prop_value_t *val = get_value_loaded_by (stmt, prop_value);
tree rhs = TREE_OPERAND (stmt, 1);
if (val
&& val->value
&& (is_gimple_reg (val->value)
|| is_gimple_min_invariant (val->value))
&& simple_cst_equal (rhs, val->mem_ref) == 1)
{
if (TREE_CODE (val->value) != SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1)))
&& replaced_addresses_p)
*replaced_addresses_p = true;
TREE_OPERAND (stmt, 1) = val->value;
if (TREE_CODE (val->value) != SSA_NAME)
prop_stats.num_const_prop++;
else
prop_stats.num_copy_prop++;
return true;
}
}
FOR_EACH_SSA_USE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES)
{
tree var = USE_FROM_PTR (vuse);
tree val = prop_value[SSA_NAME_VERSION (var)].value;
if (val == NULL_TREE || var == val)
continue;
if (is_gimple_min_invariant (val) || is_gimple_reg (val))
continue;
propagate_value (vuse, val);
prop_stats.num_copy_prop++;
replaced = true;
}
return replaced;
}
static void
replace_phi_args_in (tree phi, prop_value_t *prop_value)
{
int i;
bool replaced = false;
tree prev_phi = NULL;
if (dump_file && (dump_flags & TDF_DETAILS))
prev_phi = unshare_expr (phi);
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
tree arg = PHI_ARG_DEF (phi, i);
if (TREE_CODE (arg) == SSA_NAME)
{
tree val = prop_value[SSA_NAME_VERSION (arg)].value;
if (val && val != arg && may_propagate_copy (arg, val))
{
if (TREE_CODE (val) != SSA_NAME)
prop_stats.num_const_prop++;
else
prop_stats.num_copy_prop++;
propagate_value (PHI_ARG_DEF_PTR (phi, i), val);
replaced = true;
if (TREE_CODE (val) == SSA_NAME
&& PHI_ARG_EDGE (phi, i)->flags & EDGE_ABNORMAL)
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
}
}
}
if (replaced && dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Folded PHI node: ");
print_generic_stmt (dump_file, prev_phi, TDF_SLIM);
fprintf (dump_file, " into: ");
print_generic_stmt (dump_file, phi, TDF_SLIM);
fprintf (dump_file, "\n");
}
}
static bool
fold_predicate_in (tree stmt)
{
tree *pred_p = NULL;
bool modify_expr_p = false;
tree val;
if (TREE_CODE (stmt) == MODIFY_EXPR
&& COMPARISON_CLASS_P (TREE_OPERAND (stmt, 1)))
{
modify_expr_p = true;
pred_p = &TREE_OPERAND (stmt, 1);
}
else if (TREE_CODE (stmt) == COND_EXPR)
pred_p = &COND_EXPR_COND (stmt);
else
return false;
val = vrp_evaluate_conditional (*pred_p, stmt);
if (val)
{
if (modify_expr_p)
val = fold_convert (TREE_TYPE (*pred_p), val);
if (dump_file)
{
fprintf (dump_file, "Folding predicate ");
print_generic_expr (dump_file, *pred_p, 0);
fprintf (dump_file, " to ");
print_generic_expr (dump_file, val, 0);
fprintf (dump_file, "\n");
}
prop_stats.num_pred_folded++;
*pred_p = val;
return true;
}
return false;
}
void
substitute_and_fold (prop_value_t *prop_value, bool use_ranges_p)
{
basic_block bb;
if (prop_value == NULL && !use_ranges_p)
return;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nSubstituing values and folding statements\n\n");
memset (&prop_stats, 0, sizeof (prop_stats));
FOR_EACH_BB (bb)
{
block_stmt_iterator i;
tree phi;
if (prop_value)
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
replace_phi_args_in (phi, prop_value);
for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
{
bool replaced_address, did_replace;
tree prev_stmt = NULL;
tree stmt = bsi_stmt (i);
if (TREE_CODE (stmt) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
continue;
did_replace = false;
replaced_address = false;
if (dump_file && (dump_flags & TDF_DETAILS))
prev_stmt = unshare_expr (stmt);
if (use_ranges_p)
did_replace = fold_predicate_in (stmt);
if (prop_value)
{
if (!did_replace)
did_replace |= replace_uses_in (stmt, &replaced_address,
prop_value);
did_replace |= replace_vuses_in (stmt, &replaced_address,
prop_value);
}
if (did_replace)
{
tree old_stmt = stmt;
tree rhs;
fold_stmt (bsi_stmt_ptr (i));
stmt = bsi_stmt (i);
mark_new_vars_to_rename (stmt);
if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
tree_purge_dead_eh_edges (bb);
rhs = get_rhs (stmt);
if (TREE_CODE (rhs) == ADDR_EXPR)
recompute_tree_invariant_for_addr_expr (rhs);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Folded statement: ");
print_generic_stmt (dump_file, prev_stmt, TDF_SLIM);
fprintf (dump_file, " into: ");
print_generic_stmt (dump_file, stmt, TDF_SLIM);
fprintf (dump_file, "\n");
}
}
if (use_ranges_p)
simplify_stmt_using_ranges (stmt);
}
}
if (dump_file && (dump_flags & TDF_STATS))
{
fprintf (dump_file, "Constants propagated: %6ld\n",
prop_stats.num_const_prop);
fprintf (dump_file, "Copies propagated: %6ld\n",
prop_stats.num_copy_prop);
fprintf (dump_file, "Predicates folded: %6ld\n",
prop_stats.num_pred_folded);
}
}
#include "gt-tree-ssa-propagate.h"