#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "ggc.h"
#include "tree.h"
#include "rtl.h"
#include "flags.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"
#include "langhooks.h"
static unsigned int tree_ssa_phiopt (void);
static bool conditional_replacement (basic_block, basic_block,
edge, edge, tree, tree, tree);
static bool value_replacement (basic_block, basic_block,
edge, edge, tree, tree, tree);
static bool minmax_replacement (basic_block, basic_block,
edge, edge, tree, tree, tree);
static bool abs_replacement (basic_block, basic_block,
edge, edge, tree, tree, tree);
static void replace_phi_edge_with_variable (basic_block, edge, tree, tree);
static basic_block *blocks_in_phiopt_order (void);
static unsigned int
tree_ssa_phiopt (void)
{
basic_block bb;
basic_block *bb_order;
unsigned n, i;
bool cfgchanged = false;
bb_order = blocks_in_phiopt_order ();
n = n_basic_blocks - NUM_FIXED_BLOCKS;
for (i = 0; i < n; i++)
{
tree cond_expr;
tree phi;
basic_block bb1, bb2;
edge e1, e2;
tree arg0, arg1;
bb = bb_order[i];
cond_expr = last_stmt (bb);
if (!cond_expr
|| TREE_CODE (cond_expr) != COND_EXPR)
continue;
e1 = EDGE_SUCC (bb, 0);
bb1 = e1->dest;
e2 = EDGE_SUCC (bb, 1);
bb2 = e2->dest;
if ((e1->flags & EDGE_ABNORMAL) != 0
|| (e2->flags & EDGE_ABNORMAL) != 0)
continue;
if (EDGE_COUNT (bb1->succs) == 0
|| bb2 == NULL
|| EDGE_COUNT (bb2->succs) == 0)
continue;
if (EDGE_SUCC (bb1, 0)->dest == bb2)
;
else if (EDGE_SUCC (bb2, 0)->dest == bb1)
{
basic_block bb_tmp = bb1;
edge e_tmp = e1;
bb1 = bb2;
bb2 = bb_tmp;
e1 = e2;
e2 = e_tmp;
}
else
continue;
e1 = EDGE_SUCC (bb1, 0);
if (!single_succ_p (bb1)
|| (e1->flags & EDGE_FALLTHRU) == 0)
continue;
if (!single_pred_p (bb1)
|| single_pred (bb1) != bb)
continue;
phi = phi_nodes (bb2);
if (!phi || PHI_CHAIN (phi) != NULL)
continue;
arg0 = PHI_ARG_DEF_TREE (phi, e1->dest_idx);
arg1 = PHI_ARG_DEF_TREE (phi, e2->dest_idx);
gcc_assert (arg0 != NULL && arg1 != NULL);
if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
cfgchanged = true;
else if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
cfgchanged = true;
else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
cfgchanged = true;
else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
cfgchanged = true;
}
free (bb_order);
return cfgchanged ? TODO_cleanup_cfg : 0;
}
static basic_block *
blocks_in_phiopt_order (void)
{
basic_block x, y;
basic_block *order = XNEWVEC (basic_block, n_basic_blocks);
unsigned n = n_basic_blocks - NUM_FIXED_BLOCKS;
unsigned np, i;
sbitmap visited = sbitmap_alloc (last_basic_block);
#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
sbitmap_zero (visited);
MARK_VISITED (ENTRY_BLOCK_PTR);
FOR_EACH_BB (x)
{
if (VISITED_P (x))
continue;
for (y = x, np = 1;
single_pred_p (y) && !VISITED_P (single_pred (y));
y = single_pred (y))
np++;
for (y = x, i = n - np;
single_pred_p (y) && !VISITED_P (single_pred (y));
y = single_pred (y), i++)
{
order[i] = y;
MARK_VISITED (y);
}
order[i] = y;
MARK_VISITED (y);
gcc_assert (i == n - 1);
n -= np;
}
sbitmap_free (visited);
gcc_assert (n == 0);
return order;
#undef MARK_VISITED
#undef VISITED_P
}
bool
empty_block_p (basic_block bb)
{
block_stmt_iterator bsi;
bsi = bsi_start (bb);
while (!bsi_end_p (bsi)
&& (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR
|| IS_EMPTY_STMT (bsi_stmt (bsi))))
bsi_next (&bsi);
if (!bsi_end_p (bsi))
return false;
return true;
}
static void
replace_phi_edge_with_variable (basic_block cond_block,
edge e, tree phi, tree new)
{
basic_block bb = bb_for_stmt (phi);
basic_block block_to_remove;
block_stmt_iterator bsi;
SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new);
if (EDGE_SUCC (cond_block, 0)->dest == bb)
{
EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU;
EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
EDGE_SUCC (cond_block, 0)->probability = REG_BR_PROB_BASE;
EDGE_SUCC (cond_block, 0)->count += EDGE_SUCC (cond_block, 1)->count;
block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
}
else
{
EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
EDGE_SUCC (cond_block, 1)->flags
&= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
EDGE_SUCC (cond_block, 1)->probability = REG_BR_PROB_BASE;
EDGE_SUCC (cond_block, 1)->count += EDGE_SUCC (cond_block, 0)->count;
block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
}
delete_basic_block (block_to_remove);
bsi = bsi_last (cond_block);
bsi_remove (&bsi, true);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
"COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
cond_block->index,
bb->index);
}
static bool
conditional_replacement (basic_block cond_bb, basic_block middle_bb,
edge e0, edge e1, tree phi,
tree arg0, tree arg1)
{
tree result;
tree old_result = NULL;
tree new, cond;
block_stmt_iterator bsi;
edge true_edge, false_edge;
tree new_var = NULL;
tree new_var1;
if ((integer_zerop (arg0) && integer_onep (arg1))
|| (integer_zerop (arg1) && integer_onep (arg0)))
;
else
return false;
if (!empty_block_p (middle_bb))
return false;
cond = COND_EXPR_COND (last_stmt (cond_bb));
result = PHI_RESULT (phi);
if (TREE_CODE (cond) != SSA_NAME
&& !lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
{
tree tmp;
if (!COMPARISON_CLASS_P (cond))
return false;
tmp = create_tmp_var (TREE_TYPE (cond), NULL);
add_referenced_var (tmp);
new_var = make_ssa_name (tmp, NULL);
old_result = cond;
cond = new_var;
}
if (!lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
cond = fold_convert (TREE_TYPE (result), cond);
extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
bsi = bsi_last (cond_bb);
bsi_insert_before (&bsi, build_empty_stmt (), BSI_NEW_STMT);
if (old_result)
{
tree new1;
new1 = build2 (TREE_CODE (old_result), TREE_TYPE (old_result),
TREE_OPERAND (old_result, 0),
TREE_OPERAND (old_result, 1));
new1 = build2 (MODIFY_EXPR, TREE_TYPE (old_result), new_var, new1);
SSA_NAME_DEF_STMT (new_var) = new1;
bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
}
new_var1 = duplicate_ssa_name (PHI_RESULT (phi), NULL);
if ((e0 == true_edge && integer_onep (arg0))
|| (e0 == false_edge && integer_zerop (arg0))
|| (e1 == true_edge && integer_onep (arg1))
|| (e1 == false_edge && integer_zerop (arg1)))
{
new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
}
else
{
tree cond1 = invert_truthvalue (cond);
cond = cond1;
if (TREE_CODE (cond) == COND_EXPR)
{
release_ssa_name (new_var1);
return false;
}
if (is_gimple_cast (cond))
cond1 = TREE_OPERAND (cond, 0);
if (TREE_CODE (cond1) == TRUTH_NOT_EXPR
&& !is_gimple_val (TREE_OPERAND (cond1, 0)))
{
release_ssa_name (new_var1);
return false;
}
if (is_gimple_cast (cond)
&& !is_gimple_val (TREE_OPERAND (cond, 0)))
{
tree op0, tmp, cond_tmp;
gcc_assert (TREE_CODE (cond) == NOP_EXPR
|| TREE_CODE (cond) == CONVERT_EXPR);
op0 = TREE_OPERAND (cond, 0);
tmp = create_tmp_var (TREE_TYPE (op0), NULL);
add_referenced_var (tmp);
cond_tmp = make_ssa_name (tmp, NULL);
new = build2 (MODIFY_EXPR, TREE_TYPE (cond_tmp), cond_tmp, op0);
SSA_NAME_DEF_STMT (cond_tmp) = new;
bsi_insert_after (&bsi, new, BSI_NEW_STMT);
cond = fold_convert (TREE_TYPE (result), cond_tmp);
}
new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
}
bsi_insert_after (&bsi, new, BSI_NEW_STMT);
SSA_NAME_DEF_STMT (new_var1) = new;
replace_phi_edge_with_variable (cond_bb, e1, phi, new_var1);
return true;
}
static bool
value_replacement (basic_block cond_bb, basic_block middle_bb,
edge e0, edge e1, tree phi,
tree arg0, tree arg1)
{
tree cond;
edge true_edge, false_edge;
if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
return false;
if (!empty_block_p (middle_bb))
return false;
cond = COND_EXPR_COND (last_stmt (cond_bb));
if (TREE_CODE (cond) != NE_EXPR && TREE_CODE (cond) != EQ_EXPR)
return false;
extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
if ((operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 0))
&& operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 1)))
|| (operand_equal_for_phi_arg_p (arg1, TREE_OPERAND (cond, 0))
&& operand_equal_for_phi_arg_p (arg0, TREE_OPERAND (cond, 1))))
{
edge e;
tree arg;
e = (TREE_CODE (cond) == NE_EXPR ? true_edge : false_edge);
if (e->dest == middle_bb)
e = single_succ_edge (e->dest);
if (e0 == e)
arg = arg0;
else
arg = arg1;
replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
return true;
}
return false;
}
static bool
minmax_replacement (basic_block cond_bb, basic_block middle_bb,
edge e0, edge e1, tree phi,
tree arg0, tree arg1)
{
tree result, type;
tree cond, new;
edge true_edge, false_edge;
enum tree_code cmp, minmax, ass_code;
tree smaller, larger, arg_true, arg_false;
block_stmt_iterator bsi, bsi_from;
type = TREE_TYPE (PHI_RESULT (phi));
if (HONOR_NANS (TYPE_MODE (type)))
return false;
cond = COND_EXPR_COND (last_stmt (cond_bb));
cmp = TREE_CODE (cond);
result = PHI_RESULT (phi);
if (cmp == LT_EXPR || cmp == LE_EXPR)
{
smaller = TREE_OPERAND (cond, 0);
larger = TREE_OPERAND (cond, 1);
}
else if (cmp == GT_EXPR || cmp == GE_EXPR)
{
smaller = TREE_OPERAND (cond, 1);
larger = TREE_OPERAND (cond, 0);
}
else
return false;
extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
if (true_edge->dest == middle_bb)
true_edge = EDGE_SUCC (true_edge->dest, 0);
if (false_edge->dest == middle_bb)
false_edge = EDGE_SUCC (false_edge->dest, 0);
if (true_edge == e0)
{
gcc_assert (false_edge == e1);
arg_true = arg0;
arg_false = arg1;
}
else
{
gcc_assert (false_edge == e0);
gcc_assert (true_edge == e1);
arg_true = arg1;
arg_false = arg0;
}
if (empty_block_p (middle_bb))
{
if (operand_equal_for_phi_arg_p (arg_true, smaller)
&& operand_equal_for_phi_arg_p (arg_false, larger))
{
minmax = MIN_EXPR;
}
else if (operand_equal_for_phi_arg_p (arg_false, smaller)
&& operand_equal_for_phi_arg_p (arg_true, larger))
minmax = MAX_EXPR;
else
return false;
}
else
{
tree assign = last_and_only_stmt (middle_bb);
tree lhs, rhs, op0, op1, bound;
if (!assign
|| TREE_CODE (assign) != MODIFY_EXPR)
return false;
lhs = TREE_OPERAND (assign, 0);
rhs = TREE_OPERAND (assign, 1);
ass_code = TREE_CODE (rhs);
if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
return false;
op0 = TREE_OPERAND (rhs, 0);
op1 = TREE_OPERAND (rhs, 1);
if (true_edge->src == middle_bb)
{
if (!operand_equal_for_phi_arg_p (lhs, arg_true))
return false;
if (operand_equal_for_phi_arg_p (arg_false, larger))
{
if (ass_code != MAX_EXPR)
return false;
minmax = MIN_EXPR;
if (operand_equal_for_phi_arg_p (op0, smaller))
bound = op1;
else if (operand_equal_for_phi_arg_p (op1, smaller))
bound = op0;
else
return false;
if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
bound, larger)))
return false;
}
else if (operand_equal_for_phi_arg_p (arg_false, smaller))
{
if (ass_code != MIN_EXPR)
return false;
minmax = MAX_EXPR;
if (operand_equal_for_phi_arg_p (op0, larger))
bound = op1;
else if (operand_equal_for_phi_arg_p (op1, larger))
bound = op0;
else
return false;
if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
bound, smaller)))
return false;
}
else
return false;
}
else
{
if (!operand_equal_for_phi_arg_p (lhs, arg_false))
return false;
if (operand_equal_for_phi_arg_p (arg_true, larger))
{
if (ass_code != MIN_EXPR)
return false;
minmax = MAX_EXPR;
if (operand_equal_for_phi_arg_p (op0, smaller))
bound = op1;
else if (operand_equal_for_phi_arg_p (op1, smaller))
bound = op0;
else
return false;
if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
bound, larger)))
return false;
}
else if (operand_equal_for_phi_arg_p (arg_true, smaller))
{
if (ass_code != MAX_EXPR)
return false;
minmax = MIN_EXPR;
if (operand_equal_for_phi_arg_p (op0, larger))
bound = op1;
else if (operand_equal_for_phi_arg_p (op1, larger))
bound = op0;
else
return false;
if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
bound, smaller)))
return false;
}
else
return false;
}
bsi = bsi_last (cond_bb);
bsi_from = bsi_last (middle_bb);
bsi_move_before (&bsi_from, &bsi);
}
result = duplicate_ssa_name (PHI_RESULT (phi), NULL);
new = build2 (MODIFY_EXPR, type, result,
build2 (minmax, type, arg0, arg1));
SSA_NAME_DEF_STMT (result) = new;
bsi = bsi_last (cond_bb);
bsi_insert_before (&bsi, new, BSI_NEW_STMT);
replace_phi_edge_with_variable (cond_bb, e1, phi, result);
return true;
}
static bool
abs_replacement (basic_block cond_bb, basic_block middle_bb,
edge e0 ATTRIBUTE_UNUSED, edge e1,
tree phi, tree arg0, tree arg1)
{
tree result;
tree new, cond;
block_stmt_iterator bsi;
edge true_edge, false_edge;
tree assign;
edge e;
tree rhs, lhs;
bool negate;
enum tree_code cond_code;
if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
return false;
assign = last_and_only_stmt (middle_bb);
if (assign == NULL)
return false;
if (TREE_CODE (assign) != MODIFY_EXPR)
return false;
lhs = TREE_OPERAND (assign, 0);
rhs = TREE_OPERAND (assign, 1);
if (TREE_CODE (rhs) != NEGATE_EXPR)
return false;
rhs = TREE_OPERAND (rhs, 0);
if (!(lhs == arg0 && rhs == arg1)
&& !(lhs == arg1 && rhs == arg0))
return false;
cond = COND_EXPR_COND (last_stmt (cond_bb));
result = PHI_RESULT (phi);
cond_code = TREE_CODE (cond);
if (cond_code != GT_EXPR && cond_code != GE_EXPR
&& cond_code != LT_EXPR && cond_code != LE_EXPR)
return false;
if (TREE_OPERAND (cond, 0) != rhs)
return false;
if (FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))
? real_zerop (TREE_OPERAND (cond, 1))
: integer_zerop (TREE_OPERAND (cond, 1)))
;
else
return false;
extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
if (cond_code == GT_EXPR || cond_code == GE_EXPR)
e = true_edge;
else
e = false_edge;
if (e->dest == middle_bb)
negate = true;
else
negate = false;
result = duplicate_ssa_name (result, NULL);
if (negate)
{
tree tmp = create_tmp_var (TREE_TYPE (result), NULL);
add_referenced_var (tmp);
lhs = make_ssa_name (tmp, NULL);
}
else
lhs = result;
new = build2 (MODIFY_EXPR, TREE_TYPE (lhs),
lhs, build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
SSA_NAME_DEF_STMT (lhs) = new;
bsi = bsi_last (cond_bb);
bsi_insert_before (&bsi, new, BSI_NEW_STMT);
if (negate)
{
new = build2 (MODIFY_EXPR, TREE_TYPE (result),
result, build1 (NEGATE_EXPR, TREE_TYPE (lhs), lhs));
SSA_NAME_DEF_STMT (result) = new;
bsi_insert_after (&bsi, new, BSI_NEW_STMT);
}
replace_phi_edge_with_variable (cond_bb, e1, phi, result);
return true;
}
static bool
gate_phiopt (void)
{
return 1;
}
struct tree_opt_pass pass_phiopt =
{
"phiopt",
gate_phiopt,
tree_ssa_phiopt,
NULL,
NULL,
0,
TV_TREE_PHIOPT,
PROP_cfg | PROP_ssa | PROP_alias,
0,
0,
0,
TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
| TODO_verify_flow
| TODO_verify_stmts,
0
};