#include "tree.h"
#include "stor-layout.h"
#include "flags.h"
+#include "predict.h"
+#include "vec.h"
+#include "hashtab.h"
+#include "hash-set.h"
+#include "machmode.h"
+#include "hard-reg-set.h"
+#include "input.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
#include "basic-block.h"
#include "gimple-pretty-print.h"
#include "tree-ssa-alias.h"
#include "tree-pass.h"
#include "dbgcnt.h"
#include "expr.h"
+#include "insn-codes.h"
#include "optabs.h"
/* List of basic blocks in if-conversion-suitable order. */
}
/* Add condition NC to the predicate list of basic block BB. LOOP is
- the loop to be if-converted. */
+ the loop to be if-converted. Use predicate of cd-equivalent block
+ for join bb if it exists: we call basic blocks bb1 and bb2
+ cd-equivalent if they are executed under the same condition. */
static inline void
add_to_predicate_list (struct loop *loop, basic_block bb, tree nc)
{
tree bc, *tp;
+ basic_block dom_bb;
if (is_true_predicate (nc))
return;
- if (!is_predicated (bb))
- {
- /* If dominance tells us this basic block is always executed, don't
- record any predicates for it. */
- if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
- return;
+ /* If dominance tells us this basic block is always executed,
+ don't record any predicates for it. */
+ if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
+ return;
- bc = nc;
+ dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
+ /* We use notion of cd equivalence to get simpler predicate for
+ join block, e.g. if join block has 2 predecessors with predicates
+ p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
+ p1 & p2 | p1 & !p2. */
+ if (dom_bb != loop->header
+ && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb)
+ {
+ gcc_assert (flow_bb_inside_loop_p (loop, dom_bb));
+ bc = bb_predicate (dom_bb);
+ gcc_assert (!is_true_predicate (bc));
+ set_bb_predicate (bb, bc);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n",
+ dom_bb->index, bb->index);
+ return;
}
+
+ if (!is_predicated (bb))
+ bc = nc;
else
{
bc = bb_predicate (bb);
ifcvt_can_use_mask_load_store (gimple stmt)
{
tree lhs, ref;
- enum machine_mode mode;
+ machine_mode mode;
basic_block bb = gimple_bb (stmt);
bool is_load;
- if (!(flag_tree_loop_vectorize || bb->loop_father->force_vect)
+ if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize)
|| bb->loop_father->dont_vectorize
|| !gimple_assign_single_p (stmt)
|| gimple_has_volatile_ops (stmt))
return false;
calculate_dominance_info (CDI_DOMINATORS);
+ calculate_dominance_info (CDI_POST_DOMINATORS);
/* Allow statements that can be handled during if-conversion. */
ifc_bbs = get_loop_body_in_if_conv_order (loop);
return first_edge->src;
}
+/* Returns true if def-stmt for phi argument ARG is simple increment/decrement
+ which is in predicated basic block.
+ In fact, the following PHI pattern is searching:
+ loop-header:
+ reduc_1 = PHI <..., reduc_2>
+ ...
+ if (...)
+ reduc_3 = ...
+ reduc_2 = PHI <reduc_1, reduc_3>
+
+ REDUC, OP0 and OP1 contain reduction stmt and its operands. */
+
+static bool
+is_cond_scalar_reduction (gimple phi, gimple *reduc,
+ tree *op0, tree *op1)
+{
+ tree lhs, r_op1, r_op2;
+ tree arg_0, arg_1;
+ gimple stmt;
+ gimple header_phi = NULL;
+ enum tree_code reduction_op;
+ basic_block bb = gimple_bb (phi);
+ struct loop *loop = bb->loop_father;
+ edge latch_e = loop_latch_edge (loop);
+ imm_use_iterator imm_iter;
+ use_operand_p use_p;
+
+ arg_0 = PHI_ARG_DEF (phi, 0);
+ arg_1 = PHI_ARG_DEF (phi, 1);
+ if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME)
+ return false;
+
+ if (gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI)
+ {
+ lhs = arg_1;
+ header_phi = SSA_NAME_DEF_STMT (arg_0);
+ stmt = SSA_NAME_DEF_STMT (arg_1);
+ }
+ else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI)
+ {
+ lhs = arg_0;
+ header_phi = SSA_NAME_DEF_STMT (arg_1);
+ stmt = SSA_NAME_DEF_STMT (arg_0);
+ }
+ else
+ return false;
+ if (gimple_bb (header_phi) != loop->header)
+ return false;
+
+ if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi))
+ return false;
+
+ if (gimple_code (stmt) != GIMPLE_ASSIGN
+ || gimple_has_volatile_ops (stmt))
+ return false;
+
+ if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
+ return false;
+
+ if (!is_predicated (gimple_bb (stmt)))
+ return false;
+
+ /* Check that stmt-block is predecessor of phi-block. */
+ if (EDGE_PRED (bb, 0)->src != gimple_bb (stmt)
+ && EDGE_PRED (bb, 1)->src != gimple_bb (stmt))
+ return false;
+
+ if (!has_single_use (lhs))
+ return false;
+
+ reduction_op = gimple_assign_rhs_code (stmt);
+ if (reduction_op != PLUS_EXPR && reduction_op != MINUS_EXPR)
+ return false;
+ r_op1 = gimple_assign_rhs1 (stmt);
+ r_op2 = gimple_assign_rhs2 (stmt);
+
+ /* Make R_OP1 to hold reduction variable. */
+ if (r_op2 == PHI_RESULT (header_phi)
+ && reduction_op == PLUS_EXPR)
+ {
+ tree tmp = r_op1;
+ r_op1 = r_op2;
+ r_op2 = tmp;
+ }
+ else if (r_op1 != PHI_RESULT (header_phi))
+ return false;
+
+ /* Check that R_OP1 is used in reduction stmt or in PHI only. */
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1)
+ {
+ gimple use_stmt = USE_STMT (use_p);
+ if (is_gimple_debug (use_stmt))
+ continue;
+ if (use_stmt == stmt)
+ continue;
+ if (gimple_code (use_stmt) != GIMPLE_PHI)
+ return false;
+ }
+
+ *op0 = r_op1; *op1 = r_op2;
+ *reduc = stmt;
+ return true;
+}
+
+/* Converts conditional scalar reduction into unconditional form, e.g.
+ bb_4
+ if (_5 != 0) goto bb_5 else goto bb_6
+ end_bb_4
+ bb_5
+ res_6 = res_13 + 1;
+ end_bb_5
+ bb_6
+ # res_2 = PHI <res_13(4), res_6(5)>
+ end_bb_6
+
+ will be converted into sequence
+ _ifc__1 = _5 != 0 ? 1 : 0;
+ res_2 = res_13 + _ifc__1;
+ Argument SWAP tells that arguments of conditional expression should be
+ swapped.
+ Returns rhs of resulting PHI assignment. */
+
+static tree
+convert_scalar_cond_reduction (gimple reduc, gimple_stmt_iterator *gsi,
+ tree cond, tree op0, tree op1, bool swap)
+{
+ gimple_stmt_iterator stmt_it;
+ gimple new_assign;
+ tree rhs;
+ tree rhs1 = gimple_assign_rhs1 (reduc);
+ tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
+ tree c;
+ tree zero = build_zero_cst (TREE_TYPE (rhs1));
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Found cond scalar reduction.\n");
+ print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
+ }
+
+ /* Build cond expression using COND and constant operand
+ of reduction rhs. */
+ c = fold_build_cond_expr (TREE_TYPE (rhs1),
+ unshare_expr (cond),
+ swap ? zero : op1,
+ swap ? op1 : zero);
+
+ /* Create assignment stmt and insert it at GSI. */
+ new_assign = gimple_build_assign (tmp, c);
+ gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
+ /* Build rhs for unconditional increment/decrement. */
+ rhs = fold_build2 (gimple_assign_rhs_code (reduc),
+ TREE_TYPE (rhs1), op0, tmp);
+
+ /* Delete original reduction stmt. */
+ stmt_it = gsi_for_stmt (reduc);
+ gsi_remove (&stmt_it, true);
+ release_defs (reduc);
+ return rhs;
+}
+
/* Replace a scalar PHI node with a COND_EXPR using COND as condition.
This routine does not handle PHI nodes with more than two
arguments.
else
{
tree arg_0, arg_1;
+ tree op0, op1;
+ gimple reduc;
+
/* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
if (EDGE_PRED (bb, 1)->src == true_bb)
{
arg_0 = gimple_phi_arg_def (phi, 0);
arg_1 = gimple_phi_arg_def (phi, 1);
}
-
- /* Build new RHS using selected condition and arguments. */
- rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
- arg_0, arg_1);
+ if (is_cond_scalar_reduction (phi, &reduc, &op0, &op1))
+ /* Convert reduction stmt into vectorizable form. */
+ rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
+ true_bb != gimple_bb (reduc));
+ else
+ /* Build new RHS using selected condition and arguments. */
+ rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
+ arg_0, arg_1);
}
new_stmt = gimple_build_assign (res, rhs);
if (new_loop == NULL)
return false;
new_loop->dont_vectorize = true;
- new_loop->force_vect = false;
+ new_loop->force_vectorize = false;
gsi = gsi_last_bb (cond_bb);
gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num));
gsi_insert_before (&gsi, g, GSI_SAME_STMT);
goto cleanup;
if (any_mask_load_store
- && ((!flag_tree_loop_vectorize && !loop->force_vect)
+ && ((!flag_tree_loop_vectorize && !loop->force_vectorize)
|| loop->dont_vectorize))
goto cleanup;
free (ifc_bbs);
ifc_bbs = NULL;
}
+ free_dominance_info (CDI_POST_DOMINATORS);
return todo;
}
/* Tree if-conversion pass management. */
-static unsigned int
-main_tree_if_conversion (void)
-{
- struct loop *loop;
- unsigned todo = 0;
-
- if (number_of_loops (cfun) <= 1)
- return 0;
-
- FOR_EACH_LOOP (loop, 0)
- if (flag_tree_loop_if_convert == 1
- || flag_tree_loop_if_convert_stores == 1
- || ((flag_tree_loop_vectorize || loop->force_vect)
- && !loop->dont_vectorize))
- todo |= tree_if_conversion (loop);
-
-#ifdef ENABLE_CHECKING
- {
- basic_block bb;
- FOR_EACH_BB_FN (bb, cfun)
- gcc_assert (!bb->aux);
- }
-#endif
-
- return todo;
-}
-
-/* Returns true when the if-conversion pass is enabled. */
-
-static bool
-gate_tree_if_conversion (void)
-{
- return (((flag_tree_loop_vectorize || cfun->has_force_vect_loops)
- && flag_tree_loop_if_convert != 0)
- || flag_tree_loop_if_convert == 1
- || flag_tree_loop_if_convert_stores == 1);
-}
-
namespace {
const pass_data pass_data_if_conversion =
GIMPLE_PASS, /* type */
"ifcvt", /* name */
OPTGROUP_NONE, /* optinfo_flags */
- true, /* has_gate */
- true, /* has_execute */
TV_NONE, /* tv_id */
( PROP_cfg | PROP_ssa ), /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- ( TODO_verify_stmts | TODO_verify_flow
- | TODO_verify_ssa ), /* todo_flags_finish */
+ 0, /* todo_flags_finish */
};
class pass_if_conversion : public gimple_opt_pass
{}
/* opt_pass methods: */
- bool gate () { return gate_tree_if_conversion (); }
- unsigned int execute () { return main_tree_if_conversion (); }
+ virtual bool gate (function *);
+ virtual unsigned int execute (function *);
}; // class pass_if_conversion
+bool
+pass_if_conversion::gate (function *fun)
+{
+ return (((flag_tree_loop_vectorize || fun->has_force_vectorize_loops)
+ && flag_tree_loop_if_convert != 0)
+ || flag_tree_loop_if_convert == 1
+ || flag_tree_loop_if_convert_stores == 1);
+}
+
+unsigned int
+pass_if_conversion::execute (function *fun)
+{
+ struct loop *loop;
+ unsigned todo = 0;
+
+ if (number_of_loops (fun) <= 1)
+ return 0;
+
+ FOR_EACH_LOOP (loop, 0)
+ if (flag_tree_loop_if_convert == 1
+ || flag_tree_loop_if_convert_stores == 1
+ || ((flag_tree_loop_vectorize || loop->force_vectorize)
+ && !loop->dont_vectorize))
+ todo |= tree_if_conversion (loop);
+
+#ifdef ENABLE_CHECKING
+ {
+ basic_block bb;
+ FOR_EACH_BB_FN (bb, fun)
+ gcc_assert (!bb->aux);
+ }
+#endif
+
+ return todo;
+}
+
} // anon namespace
gimple_opt_pass *
projects / gcc.git / blobdiff