tree-ssa-forwprop.c [plain text]
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "errors.h"
#include "ggc.h"
#include "tree.h"
#include "rtl.h"
#include "tm_p.h"
#include "basic-block.h"
#include "timevar.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "tree-pass.h"
#include "tree-dump.h"
static bitmap vars;
static bool need_imm_uses_for (tree);
static void tree_ssa_forward_propagate_single_use_vars (void);
static void record_single_argument_cond_exprs (varray_type,
varray_type *,
bitmap);
static void substitute_single_use_vars (varray_type *, varray_type);
static bool
need_imm_uses_for (tree var)
{
return bitmap_bit_p (vars, SSA_NAME_VERSION (var));
}
static void
record_single_argument_cond_exprs (varray_type cond_worklist,
varray_type *vars_worklist,
bitmap vars)
{
while (VARRAY_ACTIVE_SIZE (cond_worklist) > 0)
{
tree last = VARRAY_TOP_TREE (cond_worklist);
VARRAY_POP (cond_worklist);
if (last && TREE_CODE (last) == COND_EXPR)
{
tree cond = COND_EXPR_COND (last);
enum tree_code cond_code = TREE_CODE (cond);
if (cond_code == SSA_NAME
|| ((cond_code == EQ_EXPR || cond_code == NE_EXPR)
&& TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
&& CONSTANT_CLASS_P (TREE_OPERAND (cond, 1))
&& INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
{
tree def;
tree test_var;
if (cond_code == SSA_NAME)
test_var = cond;
else
test_var = TREE_OPERAND (cond, 0);
if (bitmap_bit_p (vars, SSA_NAME_VERSION (test_var)))
continue;
def = SSA_NAME_DEF_STMT (test_var);
if (TREE_CODE (def) == MODIFY_EXPR)
{
tree def_rhs = TREE_OPERAND (def, 1);
if (TREE_CODE (def_rhs) == PLUS_EXPR
|| TREE_CODE (def_rhs) == MINUS_EXPR)
{
tree op0 = TREE_OPERAND (def_rhs, 0);
tree op1 = TREE_OPERAND (def_rhs, 1);
if (TREE_CODE (op0) != SSA_NAME
|| !CONSTANT_CLASS_P (op1)
|| !INTEGRAL_TYPE_P (TREE_TYPE (op1)))
continue;
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
continue;
}
else if (TREE_CODE (cond) == SSA_NAME
|| integer_zerop (TREE_OPERAND (cond, 1))
|| integer_onep (TREE_OPERAND (cond, 1)))
{
if (COMPARISON_CLASS_P (def_rhs))
{
tree op0 = TREE_OPERAND (def_rhs, 0);
tree op1 = TREE_OPERAND (def_rhs, 1);
if ((TREE_CODE (op0) != SSA_NAME
&& !is_gimple_min_invariant (op0))
|| (TREE_CODE (op1) != SSA_NAME
&& !is_gimple_min_invariant (op1)))
continue;
if (TREE_CODE (op0) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
continue;
if (TREE_CODE (op1) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))
continue;
}
else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
{
def_rhs = TREE_OPERAND (def_rhs, 0);
if (TREE_CODE (def_rhs) != SSA_NAME
&& !is_gimple_min_invariant (def_rhs))
continue;
if (TREE_CODE (def_rhs) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs))
continue;
}
else if (TREE_CODE (def_rhs) == NOP_EXPR
|| TREE_CODE (def_rhs) == CONVERT_EXPR)
{
tree outer_type;
tree inner_type;
outer_type = TREE_TYPE (def_rhs);
inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0));
if ((TREE_CODE (outer_type) == BOOLEAN_TYPE
&& INTEGRAL_TYPE_P (inner_type))
|| (TREE_CODE (inner_type) == BOOLEAN_TYPE
&& INTEGRAL_TYPE_P (outer_type)))
;
else
continue;
if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND
(def_rhs, 0)))
continue;
}
else
continue;
}
else
continue;
VARRAY_PUSH_TREE (*vars_worklist, test_var);
bitmap_set_bit (vars, SSA_NAME_VERSION (test_var));
}
}
}
}
}
static void
substitute_single_use_vars (varray_type *cond_worklist,
varray_type vars_worklist)
{
while (VARRAY_ACTIVE_SIZE (vars_worklist) > 0)
{
tree test_var = VARRAY_TOP_TREE (vars_worklist);
tree def = SSA_NAME_DEF_STMT (test_var);
dataflow_t df;
int j, num_uses, propagated_uses;
block_stmt_iterator bsi;
VARRAY_POP (vars_worklist);
df = get_immediate_uses (def);
num_uses = num_immediate_uses (df);
propagated_uses = 0;
if (num_uses == 1
|| (TREE_CODE (TREE_TYPE (test_var)) == BOOLEAN_TYPE
&& TREE_CODE (TREE_OPERAND (def, 1)) == TRUTH_NOT_EXPR
&& (TREE_CODE (TREE_OPERAND (TREE_OPERAND (def, 1), 0))
== SSA_NAME)))
;
else
continue;
for (j = 0; j < num_uses; j++)
{
tree cond_stmt;
tree cond;
enum tree_code cond_code;
tree def_rhs;
enum tree_code def_rhs_code;
tree new_cond;
cond_stmt = immediate_use (df, j);
if (TREE_CODE (cond_stmt) != COND_EXPR)
continue;
cond = COND_EXPR_COND (cond_stmt);
cond_code = TREE_CODE (cond);
def_rhs = TREE_OPERAND (def, 1);
def_rhs_code = TREE_CODE (def_rhs);
if (def_rhs_code == PLUS_EXPR || def_rhs_code == MINUS_EXPR)
{
tree op0 = TREE_OPERAND (def_rhs, 0);
tree op1 = TREE_OPERAND (def_rhs, 1);
enum tree_code new_code;
tree t;
new_code = def_rhs_code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR;
t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
if (!is_gimple_val (t))
continue;
new_cond = build (cond_code, boolean_type_node, op0, t);
}
else if (TREE_CODE_CLASS (def_rhs_code) == tcc_comparison)
{
tree op0 = TREE_OPERAND (def_rhs, 0);
tree op1 = TREE_OPERAND (def_rhs, 1);
new_cond = build (def_rhs_code, boolean_type_node, op0, op1);
if ((cond_code == EQ_EXPR
&& integer_zerop (TREE_OPERAND (cond, 1)))
|| (cond_code == NE_EXPR
&& integer_onep (TREE_OPERAND (cond, 1))))
{
new_cond = invert_truthvalue (new_cond);
if (!COMPARISON_CLASS_P (new_cond)
&& TREE_CODE (new_cond) != SSA_NAME)
continue;
}
}
else
{
bool invert = false;
enum tree_code new_code;
tree new_arg;
if (def_rhs_code == TRUTH_NOT_EXPR)
invert = true;
if (cond_code == SSA_NAME
|| (cond_code == NE_EXPR
&& integer_zerop (TREE_OPERAND (cond, 1)))
|| (cond_code == EQ_EXPR
&& integer_onep (TREE_OPERAND (cond, 1))))
new_code = NE_EXPR;
else
new_code = EQ_EXPR;
if (invert)
new_code = (new_code == EQ_EXPR ? NE_EXPR : EQ_EXPR);
new_arg = TREE_OPERAND (def_rhs, 0);
new_cond = build2 (new_code, boolean_type_node, new_arg,
fold_convert (TREE_TYPE (new_arg),
integer_zero_node));
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " Replaced '");
print_generic_expr (dump_file, cond, dump_flags);
fprintf (dump_file, "' with '");
print_generic_expr (dump_file, new_cond, dump_flags);
fprintf (dump_file, "'\n");
}
COND_EXPR_COND (cond_stmt) = new_cond;
modify_stmt (cond_stmt);
propagated_uses++;
VARRAY_PUSH_TREE (*cond_worklist, cond_stmt);
}
if (num_uses && num_uses == propagated_uses)
for (bsi = bsi_start (bb_for_stmt (def));
!bsi_end_p (bsi);
bsi_next (&bsi))
{
if (def == bsi_stmt (bsi))
{
bsi_remove (&bsi);
break;
}
}
}
}
static bool cast_conversion_assignment_p (tree stmt)
{
tree lhs, rhs;
gcc_assert (stmt);
if (TREE_CODE (stmt) != MODIFY_EXPR)
return false;
lhs = TREE_OPERAND (stmt, 0);
rhs = TREE_OPERAND (stmt, 1);
if ((TREE_CODE (rhs) == NOP_EXPR
|| TREE_CODE (rhs) == CONVERT_EXPR)
&& TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
&& TREE_CODE (lhs) == SSA_NAME)
return true;
return false;
}
static bool
replacable_use_in_cond_expr (tree stmt, tree def_stmt, tree *new_stmt)
{
tree op0, op1, candidate_op, other_op, temp, def_rhs, def_rhs_inner_type;
gcc_assert (stmt);
gcc_assert (def_stmt);
gcc_assert (COMPARISON_CLASS_P (stmt));
gcc_assert (TREE_CODE (def_stmt) == MODIFY_EXPR);
candidate_op = NULL_TREE;
other_op = NULL_TREE;
op0 = TREE_OPERAND (stmt, 0);
op1 = TREE_OPERAND (stmt, 1);
if (TREE_CODE (op0) == SSA_NAME
&& SSA_NAME_DEF_STMT (op0) == def_stmt
&& is_gimple_min_invariant (op1))
{
candidate_op = op0;
other_op = op1;
}
else if (TREE_CODE (op1) == SSA_NAME
&& SSA_NAME_DEF_STMT (op1) == def_stmt
&& is_gimple_min_invariant (op0))
{
candidate_op = op1;
other_op = op0;
}
else
return false;
if (!cast_conversion_assignment_p (def_stmt))
return false;
def_rhs = TREE_OPERAND (def_stmt, 1);
def_rhs_inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0));
temp = build1 (TREE_CODE (def_rhs), def_rhs_inner_type, other_op);
temp = fold (temp);
if (is_gimple_val (temp) && tree_int_cst_equal (temp, other_op))
{
if (new_stmt)
*new_stmt = build (TREE_CODE (stmt), TREE_TYPE (stmt),
TREE_OPERAND (def_rhs, 0), temp);
return true;
}
return false;
}
static bool
all_uses_are_replacable (tree stmt, bool replace)
{
dataflow_t df;
int j, num_uses;
bool replacable = true;
df = get_immediate_uses (stmt);
num_uses = num_immediate_uses (df);
for (j = 0; j < num_uses && replacable; j++)
{
tree use = immediate_use (df, j);
if (replace && dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " Removing casts");
print_generic_expr (dump_file, use, dump_flags);
fprintf (dump_file, "\n");
}
if (TREE_CODE (use) == MODIFY_EXPR)
{
replacable = cast_conversion_assignment_p (use);
if (replace)
{
tree def_rhs = TREE_OPERAND (stmt, 1);
tree def_rhs_inner = TREE_OPERAND (def_rhs, 0);
tree use_lhs = TREE_OPERAND (use, 0);
tree def_rhs_inner_type = TREE_TYPE (def_rhs_inner);
tree use_lhs_type = TREE_TYPE (use_lhs);
if ((TYPE_PRECISION (def_rhs_inner_type)
== TYPE_PRECISION (use_lhs_type))
&& (TYPE_MAIN_VARIANT (def_rhs_inner_type)
== TYPE_MAIN_VARIANT (use_lhs_type)))
{
TREE_OPERAND (use, 1) = TREE_OPERAND (def_rhs, 0);
modify_stmt (use);
}
}
}
else if (TREE_CODE (use) == COND_EXPR
&& COMPARISON_CLASS_P (COND_EXPR_COND (use)))
{
if (replace)
{
tree new_cond = NULL_TREE;
replacable = replacable_use_in_cond_expr (COND_EXPR_COND (use),
stmt, &new_cond);
if (new_cond)
{
COND_EXPR_COND (use) = new_cond;
modify_stmt (use);
}
else
abort ();
}
else
replacable = replacable_use_in_cond_expr (COND_EXPR_COND (use),
stmt, NULL);
}
else
replacable = false;
}
return replacable;
}
static void
eliminate_unnecessary_casts (void)
{
basic_block bb;
block_stmt_iterator bsi;
varray_type worklist;
vars = BITMAP_XMALLOC ();
VARRAY_TREE_INIT (worklist, 10, "worklist");
FOR_EACH_BB (bb)
{
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
if (cast_conversion_assignment_p (stmt))
{
tree lhs = TREE_OPERAND (stmt, 0);
tree rhs = TREE_OPERAND (stmt, 1);
tree rhs_inner = TREE_OPERAND (rhs, 0);
tree rhs_type = TREE_TYPE (rhs);
tree rhs_inner_type = TREE_TYPE (rhs_inner);
if ((TYPE_PRECISION (rhs_inner_type) <= TYPE_PRECISION (rhs_type))
&& (TYPE_UNSIGNED (rhs_inner_type) == TYPE_UNSIGNED (rhs_type)))
{
bitmap_set_bit (vars, SSA_NAME_VERSION (lhs));
VARRAY_PUSH_TREE (worklist, stmt);
}
}
}
}
compute_immediate_uses (TDFA_USE_OPS, need_imm_uses_for);
while (VARRAY_ACTIVE_SIZE (worklist) > 0)
{
tree stmt = VARRAY_TOP_TREE (worklist);
VARRAY_POP (worklist);
if (all_uses_are_replacable (stmt, false ))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file,"File name = %s\n", __FILE__);
fprintf (dump_file,"Input name = %s\n", main_input_filename);
}
all_uses_are_replacable (stmt, true );
}
}
free_df ();
BITMAP_XFREE (vars);
}
static void
tree_ssa_forward_propagate_single_use_vars (void)
{
basic_block bb;
varray_type vars_worklist, cond_worklist;
eliminate_unnecessary_casts ();
vars = BITMAP_XMALLOC ();
VARRAY_TREE_INIT (vars_worklist, 10, "VARS worklist");
VARRAY_TREE_INIT (cond_worklist, 10, "COND worklist");
FOR_EACH_BB (bb)
{
tree last = last_stmt (bb);
if (last && TREE_CODE (last) == COND_EXPR)
VARRAY_PUSH_TREE (cond_worklist, last);
}
while (VARRAY_ACTIVE_SIZE (cond_worklist) > 0)
{
record_single_argument_cond_exprs (cond_worklist, &vars_worklist, vars);
if (VARRAY_ACTIVE_SIZE (vars_worklist) > 0)
{
compute_immediate_uses (TDFA_USE_OPS, need_imm_uses_for);
bitmap_clear (vars);
substitute_single_use_vars (&cond_worklist, vars_worklist);
free_df ();
}
}
BITMAP_XFREE (vars);
}
static bool
gate_forwprop (void)
{
return 1;
}
struct tree_opt_pass pass_forwprop = {
"forwprop",
gate_forwprop,
tree_ssa_forward_propagate_single_use_vars,
NULL,
NULL,
0,
TV_TREE_FORWPROP,
PROP_cfg | PROP_ssa
| PROP_alias,
0,
0,
0,
TODO_dump_func | TODO_ggc_collect
| TODO_verify_ssa,
0
};