/* If-conversion for vectorizer.
- Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
- Free Software Foundation, Inc.
+ Copyright (C) 2004-2014 Free Software Foundation, Inc.
Contributed by Devang Patel <dpatel@apple.com>
This file is part of GCC.
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
+#include "stor-layout.h"
#include "flags.h"
-#include "timevar.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 "tree-pretty-print.h"
#include "gimple-pretty-print.h"
-#include "tree-flow.h"
-#include "tree-dump.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-fold.h"
+#include "gimple-expr.h"
+#include "is-a.h"
+#include "gimple.h"
+#include "gimplify.h"
+#include "gimple-iterator.h"
+#include "gimplify-me.h"
+#include "gimple-ssa.h"
+#include "tree-cfg.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "stringpool.h"
+#include "tree-ssanames.h"
+#include "tree-into-ssa.h"
+#include "tree-ssa.h"
#include "cfgloop.h"
#include "tree-chrec.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
+#include "tree-ssa-loop-ivopts.h"
+#include "tree-ssa-address.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. */
static basic_block *ifc_bbs;
static inline void
set_bb_predicate (basic_block bb, tree cond)
{
+ gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR
+ && is_gimple_condexpr (TREE_OPERAND (cond, 0)))
+ || is_gimple_condexpr (cond));
((bb_predicate_p) bb->aux)->predicate = cond;
}
{
bb->aux = XNEW (struct bb_predicate_s);
set_bb_predicate_gimplified_stmts (bb, NULL);
- set_bb_predicate (bb, NULL_TREE);
+ set_bb_predicate (bb, boolean_true_node);
}
-/* Free the predicate of basic block BB. */
+/* Release the SSA_NAMEs associated with the predicate of basic block BB,
+ but don't actually free it. */
static inline void
-free_bb_predicate (basic_block bb)
+release_bb_predicate (basic_block bb)
{
- gimple_seq stmts;
-
- if (!bb_has_predicate (bb))
- return;
-
- /* Release the SSA_NAMEs created for the gimplification of the
- predicate. */
- stmts = bb_predicate_gimplified_stmts (bb);
+ gimple_seq stmts = bb_predicate_gimplified_stmts (bb);
if (stmts)
{
gimple_stmt_iterator i;
for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i))
- free_stmt_operands (gsi_stmt (i));
+ free_stmt_operands (cfun, gsi_stmt (i));
+ set_bb_predicate_gimplified_stmts (bb, NULL);
}
+}
+
+/* Free the predicate of basic block BB. */
+
+static inline void
+free_bb_predicate (basic_block bb)
+{
+ if (!bb_has_predicate (bb))
+ return;
+ release_bb_predicate (bb);
free (bb->aux);
bb->aux = NULL;
}
-/* Create a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP
- to the new variable. */
+/* Reinitialize predicate of BB with the true predicate. */
-static gimple
-ifc_temp_var (tree type, tree exp)
+static inline void
+reset_bb_predicate (basic_block bb)
{
- const char *name = "_ifc_";
- tree var, new_name;
- gimple stmt;
-
- /* Create new temporary variable. */
- var = create_tmp_var (type, name);
- add_referenced_var (var);
-
- /* Build new statement to assign EXP to new variable. */
- stmt = gimple_build_assign (var, exp);
+ if (!bb_has_predicate (bb))
+ init_bb_predicate (bb);
+ else
+ {
+ release_bb_predicate (bb);
+ set_bb_predicate (bb, boolean_true_node);
+ }
+}
- /* Get SSA name for the new variable and set make new statement
- its definition statement. */
- new_name = make_ssa_name (var, stmt);
- gimple_assign_set_lhs (stmt, new_name);
- SSA_NAME_DEF_STMT (new_name) = stmt;
- update_stmt (stmt);
+/* Returns a new SSA_NAME of type TYPE that is assigned the value of
+ the expression EXPR. Inserts the statement created for this
+ computation before GSI and leaves the iterator GSI at the same
+ statement. */
- return stmt;
+static tree
+ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi)
+{
+ tree new_name = make_temp_ssa_name (type, NULL, "_ifc_");
+ gimple stmt = gimple_build_assign (new_name, expr);
+ gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
+ return new_name;
}
/* Return true when COND is a true predicate. */
return !is_true_predicate (bb_predicate (bb));
}
-/* Add condition NEW_COND to the predicate list of basic block BB. */
+/* Parses the predicate COND and returns its comparison code and
+ operands OP0 and OP1. */
+
+static enum tree_code
+parse_predicate (tree cond, tree *op0, tree *op1)
+{
+ gimple s;
+
+ if (TREE_CODE (cond) == SSA_NAME
+ && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond)))
+ {
+ if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
+ {
+ *op0 = gimple_assign_rhs1 (s);
+ *op1 = gimple_assign_rhs2 (s);
+ return gimple_assign_rhs_code (s);
+ }
+
+ else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR)
+ {
+ tree op = gimple_assign_rhs1 (s);
+ tree type = TREE_TYPE (op);
+ enum tree_code code = parse_predicate (op, op0, op1);
+
+ return code == ERROR_MARK ? ERROR_MARK
+ : invert_tree_comparison (code, HONOR_NANS (TYPE_MODE (type)));
+ }
+
+ return ERROR_MARK;
+ }
+
+ if (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison)
+ {
+ *op0 = TREE_OPERAND (cond, 0);
+ *op1 = TREE_OPERAND (cond, 1);
+ return TREE_CODE (cond);
+ }
+
+ return ERROR_MARK;
+}
+
+/* Returns the fold of predicate C1 OR C2 at location LOC. */
+
+static tree
+fold_or_predicates (location_t loc, tree c1, tree c2)
+{
+ tree op1a, op1b, op2a, op2b;
+ enum tree_code code1 = parse_predicate (c1, &op1a, &op1b);
+ enum tree_code code2 = parse_predicate (c2, &op2a, &op2b);
+
+ if (code1 != ERROR_MARK && code2 != ERROR_MARK)
+ {
+ tree t = maybe_fold_or_comparisons (code1, op1a, op1b,
+ code2, op2a, op2b);
+ if (t)
+ return t;
+ }
+
+ return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2);
+}
+
+/* Returns true if N is either a constant or a SSA_NAME. */
+
+static bool
+constant_or_ssa_name (tree n)
+{
+ switch (TREE_CODE (n))
+ {
+ case SSA_NAME:
+ case INTEGER_CST:
+ case REAL_CST:
+ case COMPLEX_CST:
+ case VECTOR_CST:
+ return true;
+ default:
+ return false;
+ }
+}
+
+/* Returns either a COND_EXPR or the folded expression if the folded
+ expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
+ a constant or a SSA_NAME. */
+
+static tree
+fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs)
+{
+ tree rhs1, lhs1, cond_expr;
+ cond_expr = fold_ternary (COND_EXPR, type, cond,
+ rhs, lhs);
+
+ if (cond_expr == NULL_TREE)
+ return build3 (COND_EXPR, type, cond, rhs, lhs);
+
+ STRIP_USELESS_TYPE_CONVERSION (cond_expr);
+
+ if (constant_or_ssa_name (cond_expr))
+ return cond_expr;
+
+ if (TREE_CODE (cond_expr) == ABS_EXPR)
+ {
+ rhs1 = TREE_OPERAND (cond_expr, 1);
+ STRIP_USELESS_TYPE_CONVERSION (rhs1);
+ if (constant_or_ssa_name (rhs1))
+ return build1 (ABS_EXPR, type, rhs1);
+ }
+
+ if (TREE_CODE (cond_expr) == MIN_EXPR
+ || TREE_CODE (cond_expr) == MAX_EXPR)
+ {
+ lhs1 = TREE_OPERAND (cond_expr, 0);
+ STRIP_USELESS_TYPE_CONVERSION (lhs1);
+ rhs1 = TREE_OPERAND (cond_expr, 1);
+ STRIP_USELESS_TYPE_CONVERSION (rhs1);
+ if (constant_or_ssa_name (rhs1)
+ && constant_or_ssa_name (lhs1))
+ return build2 (TREE_CODE (cond_expr), type, lhs1, rhs1);
+ }
+ return build3 (COND_EXPR, type, cond, rhs, lhs);
+}
+
+/* Add condition NC to the predicate list of basic block BB. LOOP is
+ 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 (basic_block bb, tree new_cond)
+add_to_predicate_list (struct loop *loop, basic_block bb, tree nc)
{
- tree cond = bb_predicate (bb);
+ tree bc, *tp;
+ basic_block dom_bb;
+
+ if (is_true_predicate (nc))
+ 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;
+
+ 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);
+ bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc);
+ if (is_true_predicate (bc))
+ {
+ reset_bb_predicate (bb);
+ return;
+ }
+ }
- set_bb_predicate (bb, is_true_predicate (cond) ? new_cond :
- fold_build2_loc (EXPR_LOCATION (cond),
- TRUTH_OR_EXPR, boolean_type_node,
- cond, new_cond));
+ /* Allow a TRUTH_NOT_EXPR around the main predicate. */
+ if (TREE_CODE (bc) == TRUTH_NOT_EXPR)
+ tp = &TREE_OPERAND (bc, 0);
+ else
+ tp = &bc;
+ if (!is_gimple_condexpr (*tp))
+ {
+ gimple_seq stmts;
+ *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE);
+ add_bb_predicate_gimplified_stmts (bb, stmts);
+ }
+ set_bb_predicate (bb, bc);
}
/* Add the condition COND to the previous condition PREV_COND, and add
cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
prev_cond, cond);
- add_to_predicate_list (e->dest, cond);
+ add_to_predicate_list (loop, e->dest, cond);
}
/* Return true if one of the successor edges of BB exits LOOP. */
and it belongs to basic block BB.
PHI is not if-convertible if:
- - it has more than 2 arguments,
- - virtual PHI is immediately used in another PHI node,
- - virtual PHI on BB other than header. */
+ - it has more than 2 arguments.
+
+ When the flag_tree_loop_if_convert_stores is not set, PHI is not
+ if-convertible if:
+ - a virtual PHI is immediately used in another PHI node,
+ - there is a virtual PHI in a BB other than the loop->header. */
static bool
-if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
+if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi,
+ bool any_mask_load_store)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
return false;
}
- if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi))))
+ if (flag_tree_loop_if_convert_stores || any_mask_load_store)
+ return true;
+
+ /* When the flag_tree_loop_if_convert_stores is not set, check
+ that there are no memory writes in the branches of the loop to be
+ if-converted. */
+ if (virtual_operand_p (gimple_phi_result (phi)))
{
imm_use_iterator imm_iter;
use_operand_p use_p;
if (bb != loop->header)
{
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Virtual phi not on loop header.\n");
+ fprintf (dump_file, "Virtual phi not on loop->header.\n");
return false;
}
+
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi))
{
if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI)
return true;
}
+/* Records the status of a data reference. This struct is attached to
+ each DR->aux field. */
+
+struct ifc_dr {
+ /* -1 when not initialized, 0 when false, 1 when true. */
+ int written_at_least_once;
+
+ /* -1 when not initialized, 0 when false, 1 when true. */
+ int rw_unconditionally;
+};
+
+#define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
+#define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
+#define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
+
+/* Returns true when the memory references of STMT are read or written
+ unconditionally. In other words, this function returns true when
+ for every data reference A in STMT there exist other accesses to
+ a data reference with the same base with predicates that add up (OR-up) to
+ the true predicate: this ensures that the data reference A is touched
+ (read or written) on every iteration of the if-converted loop. */
+
+static bool
+memrefs_read_or_written_unconditionally (gimple stmt,
+ vec<data_reference_p> drs)
+{
+ int i, j;
+ data_reference_p a, b;
+ tree ca = bb_predicate (gimple_bb (stmt));
+
+ for (i = 0; drs.iterate (i, &a); i++)
+ if (DR_STMT (a) == stmt)
+ {
+ bool found = false;
+ int x = DR_RW_UNCONDITIONALLY (a);
+
+ if (x == 0)
+ return false;
+
+ if (x == 1)
+ continue;
+
+ for (j = 0; drs.iterate (j, &b); j++)
+ {
+ tree ref_base_a = DR_REF (a);
+ tree ref_base_b = DR_REF (b);
+
+ if (DR_STMT (b) == stmt)
+ continue;
+
+ while (TREE_CODE (ref_base_a) == COMPONENT_REF
+ || TREE_CODE (ref_base_a) == IMAGPART_EXPR
+ || TREE_CODE (ref_base_a) == REALPART_EXPR)
+ ref_base_a = TREE_OPERAND (ref_base_a, 0);
+
+ while (TREE_CODE (ref_base_b) == COMPONENT_REF
+ || TREE_CODE (ref_base_b) == IMAGPART_EXPR
+ || TREE_CODE (ref_base_b) == REALPART_EXPR)
+ ref_base_b = TREE_OPERAND (ref_base_b, 0);
+
+ if (!operand_equal_p (ref_base_a, ref_base_b, 0))
+ {
+ tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
+
+ if (DR_RW_UNCONDITIONALLY (b) == 1
+ || is_true_predicate (cb)
+ || is_true_predicate (ca
+ = fold_or_predicates (EXPR_LOCATION (cb), ca, cb)))
+ {
+ DR_RW_UNCONDITIONALLY (a) = 1;
+ DR_RW_UNCONDITIONALLY (b) = 1;
+ found = true;
+ break;
+ }
+ }
+ }
+
+ if (!found)
+ {
+ DR_RW_UNCONDITIONALLY (a) = 0;
+ return false;
+ }
+ }
+
+ return true;
+}
+
+/* Returns true when the memory references of STMT are unconditionally
+ written. In other words, this function returns true when for every
+ data reference A written in STMT, there exist other writes to the
+ same data reference with predicates that add up (OR-up) to the true
+ predicate: this ensures that the data reference A is written on
+ every iteration of the if-converted loop. */
+
+static bool
+write_memrefs_written_at_least_once (gimple stmt,
+ vec<data_reference_p> drs)
+{
+ int i, j;
+ data_reference_p a, b;
+ tree ca = bb_predicate (gimple_bb (stmt));
+
+ for (i = 0; drs.iterate (i, &a); i++)
+ if (DR_STMT (a) == stmt
+ && DR_IS_WRITE (a))
+ {
+ bool found = false;
+ int x = DR_WRITTEN_AT_LEAST_ONCE (a);
+
+ if (x == 0)
+ return false;
+
+ if (x == 1)
+ continue;
+
+ for (j = 0; drs.iterate (j, &b); j++)
+ if (DR_STMT (b) != stmt
+ && DR_IS_WRITE (b)
+ && same_data_refs_base_objects (a, b))
+ {
+ tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
+
+ if (DR_WRITTEN_AT_LEAST_ONCE (b) == 1
+ || is_true_predicate (cb)
+ || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb),
+ ca, cb)))
+ {
+ DR_WRITTEN_AT_LEAST_ONCE (a) = 1;
+ DR_WRITTEN_AT_LEAST_ONCE (b) = 1;
+ found = true;
+ break;
+ }
+ }
+
+ if (!found)
+ {
+ DR_WRITTEN_AT_LEAST_ONCE (a) = 0;
+ return false;
+ }
+ }
+
+ return true;
+}
+
+/* Return true when the memory references of STMT won't trap in the
+ if-converted code. There are two things that we have to check for:
+
+ - writes to memory occur to writable memory: if-conversion of
+ memory writes transforms the conditional memory writes into
+ unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
+ into "A[i] = cond ? foo : A[i]", and as the write to memory may not
+ be executed at all in the original code, it may be a readonly
+ memory. To check that A is not const-qualified, we check that
+ there exists at least an unconditional write to A in the current
+ function.
+
+ - reads or writes to memory are valid memory accesses for every
+ iteration. To check that the memory accesses are correctly formed
+ and that we are allowed to read and write in these locations, we
+ check that the memory accesses to be if-converted occur at every
+ iteration unconditionally. */
+
+static bool
+ifcvt_memrefs_wont_trap (gimple stmt, vec<data_reference_p> refs)
+{
+ return write_memrefs_written_at_least_once (stmt, refs)
+ && memrefs_read_or_written_unconditionally (stmt, refs);
+}
+
+/* Wrapper around gimple_could_trap_p refined for the needs of the
+ if-conversion. Try to prove that the memory accesses of STMT could
+ not trap in the innermost loop containing STMT. */
+
+static bool
+ifcvt_could_trap_p (gimple stmt, vec<data_reference_p> refs)
+{
+ if (gimple_vuse (stmt)
+ && !gimple_could_trap_p_1 (stmt, false, false)
+ && ifcvt_memrefs_wont_trap (stmt, refs))
+ return false;
+
+ return gimple_could_trap_p (stmt);
+}
+
+/* Return true if STMT could be converted into a masked load or store
+ (conditional load or store based on a mask computed from bb predicate). */
+
+static bool
+ifcvt_can_use_mask_load_store (gimple stmt)
+{
+ tree lhs, ref;
+ machine_mode mode;
+ basic_block bb = gimple_bb (stmt);
+ bool is_load;
+
+ 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;
+
+ /* Check whether this is a load or store. */
+ lhs = gimple_assign_lhs (stmt);
+ if (gimple_store_p (stmt))
+ {
+ if (!is_gimple_val (gimple_assign_rhs1 (stmt)))
+ return false;
+ is_load = false;
+ ref = lhs;
+ }
+ else if (gimple_assign_load_p (stmt))
+ {
+ is_load = true;
+ ref = gimple_assign_rhs1 (stmt);
+ }
+ else
+ return false;
+
+ if (may_be_nonaddressable_p (ref))
+ return false;
+
+ /* Mask should be integer mode of the same size as the load/store
+ mode. */
+ mode = TYPE_MODE (TREE_TYPE (lhs));
+ if (int_mode_for_mode (mode) == BLKmode
+ || VECTOR_MODE_P (mode))
+ return false;
+
+ if (can_vec_mask_load_store_p (mode, is_load))
+ return true;
+
+ return false;
+}
+
/* Return true when STMT is if-convertible.
GIMPLE_ASSIGN statement is not if-convertible if,
- it is not movable,
- it could trap,
- - LHS is not var decl.
-
- GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP. */
+ - LHS is not var decl. */
static bool
-if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb,
- gimple stmt)
+if_convertible_gimple_assign_stmt_p (gimple stmt,
+ vec<data_reference_p> refs,
+ bool *any_mask_load_store)
{
tree lhs = gimple_assign_lhs (stmt);
+ basic_block bb;
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
+ if (!is_gimple_reg_type (TREE_TYPE (lhs)))
+ return false;
+
/* Some of these constrains might be too conservative. */
if (stmt_ends_bb_p (stmt)
|| gimple_has_volatile_ops (stmt)
return false;
}
+ /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
+ in between if_convertible_loop_p and combine_blocks
+ we can perform loop versioning. */
+ gimple_set_plf (stmt, GF_PLF_2, false);
+
+ if (flag_tree_loop_if_convert_stores)
+ {
+ if (ifcvt_could_trap_p (stmt, refs))
+ {
+ if (ifcvt_can_use_mask_load_store (stmt))
+ {
+ gimple_set_plf (stmt, GF_PLF_2, true);
+ *any_mask_load_store = true;
+ return true;
+ }
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "tree could trap...\n");
+ return false;
+ }
+ return true;
+ }
+
if (gimple_assign_rhs_could_trap_p (stmt))
{
+ if (ifcvt_can_use_mask_load_store (stmt))
+ {
+ gimple_set_plf (stmt, GF_PLF_2, true);
+ *any_mask_load_store = true;
+ return true;
+ }
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "tree could trap...\n");
return false;
}
+ bb = gimple_bb (stmt);
+
if (TREE_CODE (lhs) != SSA_NAME
- && bb != loop->header
- && !bb_with_exit_edge_p (loop, bb))
+ && bb != bb->loop_father->header
+ && !bb_with_exit_edge_p (bb->loop_father, bb))
{
+ if (ifcvt_can_use_mask_load_store (stmt))
+ {
+ gimple_set_plf (stmt, GF_PLF_2, true);
+ *any_mask_load_store = true;
+ return true;
+ }
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "LHS is not var\n");
/* Return true when STMT is if-convertible.
A statement is if-convertible if:
- - it is an if-convertible GIMPLE_ASSGIN,
- - it is a GIMPLE_LABEL or a GIMPLE_COND.
-
- STMT is inside BB, which is inside loop LOOP. */
+ - it is an if-convertible GIMPLE_ASSIGN,
+ - it is a GIMPLE_LABEL or a GIMPLE_COND. */
static bool
-if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
+if_convertible_stmt_p (gimple stmt, vec<data_reference_p> refs,
+ bool *any_mask_load_store)
{
switch (gimple_code (stmt))
{
return true;
case GIMPLE_ASSIGN:
- return if_convertible_gimple_assign_stmt_p (loop, bb, stmt);
+ return if_convertible_gimple_assign_stmt_p (stmt, refs,
+ any_mask_load_store);
+
+ case GIMPLE_CALL:
+ {
+ tree fndecl = gimple_call_fndecl (stmt);
+ if (fndecl)
+ {
+ int flags = gimple_call_flags (stmt);
+ if ((flags & ECF_CONST)
+ && !(flags & ECF_LOOPING_CONST_OR_PURE)
+ /* We can only vectorize some builtins at the moment,
+ so restrict if-conversion to those. */
+ && DECL_BUILT_IN (fndecl))
+ return true;
+ }
+ return false;
+ }
default:
/* Don't know what to do with 'em so don't do anything. */
/* Be less adventurous and handle only normal edges. */
FOR_EACH_EDGE (e, ei, bb->succs)
- if (e->flags &
- (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
+ if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Difficult to handle edges\n");
return false;
}
+ /* At least one incoming edge has to be non-critical as otherwise edge
+ predicates are not equal to basic-block predicates of the edge
+ source. */
+ if (EDGE_COUNT (bb->preds) > 1
+ && bb != loop->header)
+ {
+ bool found = false;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (EDGE_COUNT (e->src->succs) == 1)
+ found = true;
+ if (!found)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "only critical predecessors\n");
+ return false;
+ }
+ }
+
return true;
}
unsigned int visited_count = 0;
gcc_assert (loop->num_nodes);
- gcc_assert (loop->latch != EXIT_BLOCK_PTR);
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
blocks = XCNEWVEC (basic_block, loop->num_nodes);
visited = BITMAP_ALLOC (NULL);
S1 will be predicated with "x", and
S2 will be predicated with "!x". */
-static bool
+static void
predicate_bbs (loop_p loop)
{
unsigned int i;
{
basic_block bb = ifc_bbs[i];
tree cond;
- gimple_stmt_iterator itr;
+ gimple stmt;
/* The loop latch is always executed and has no extra conditions
to be processed: skip it. */
if (bb == loop->latch)
{
- set_bb_predicate (loop->latch, boolean_true_node);
- set_bb_predicate_gimplified_stmts (loop->latch, NULL);
+ reset_bb_predicate (loop->latch);
continue;
}
cond = bb_predicate (bb);
- if (cond
- && bb != loop->header)
+ stmt = last_stmt (bb);
+ if (stmt && gimple_code (stmt) == GIMPLE_COND)
{
- gimple_seq stmts;
-
- cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
- add_bb_predicate_gimplified_stmts (bb, stmts);
- }
-
- for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
- {
- gimple stmt = gsi_stmt (itr);
-
- switch (gimple_code (stmt))
- {
- case GIMPLE_LABEL:
- case GIMPLE_ASSIGN:
- case GIMPLE_CALL:
- case GIMPLE_DEBUG:
- break;
-
- case GIMPLE_COND:
- {
- tree c2;
- edge true_edge, false_edge;
- location_t loc = gimple_location (stmt);
- tree c = fold_build2_loc (loc, gimple_cond_code (stmt),
- boolean_type_node,
- gimple_cond_lhs (stmt),
- gimple_cond_rhs (stmt));
-
- /* Add new condition into destination's predicate list. */
- extract_true_false_edges_from_block (gimple_bb (stmt),
- &true_edge, &false_edge);
-
- /* If C is true, then TRUE_EDGE is taken. */
- add_to_dst_predicate_list (loop, true_edge, cond, c);
-
- /* If C is false, then FALSE_EDGE is taken. */
- c2 = invert_truthvalue_loc (loc, unshare_expr (c));
- add_to_dst_predicate_list (loop, false_edge, cond, c2);
-
- cond = NULL_TREE;
- break;
- }
-
- default:
- /* Not handled yet in if-conversion. */
- return false;
- }
+ tree c2;
+ edge true_edge, false_edge;
+ location_t loc = gimple_location (stmt);
+ tree c = fold_build2_loc (loc, gimple_cond_code (stmt),
+ boolean_type_node,
+ gimple_cond_lhs (stmt),
+ gimple_cond_rhs (stmt));
+
+ /* Add new condition into destination's predicate list. */
+ extract_true_false_edges_from_block (gimple_bb (stmt),
+ &true_edge, &false_edge);
+
+ /* If C is true, then TRUE_EDGE is taken. */
+ add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond),
+ unshare_expr (c));
+
+ /* If C is false, then FALSE_EDGE is taken. */
+ c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node,
+ unshare_expr (c));
+ add_to_dst_predicate_list (loop, false_edge,
+ unshare_expr (cond), c2);
+
+ cond = NULL_TREE;
}
/* If current bb has only one successor, then consider it as an
if (cond == NULL_TREE)
cond = boolean_true_node;
- add_to_predicate_list (bb_n, cond);
+ add_to_predicate_list (loop, bb_n, cond);
}
}
/* The loop header is always executed. */
- set_bb_predicate (loop->header, boolean_true_node);
+ reset_bb_predicate (loop->header);
gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
&& bb_predicate_gimplified_stmts (loop->latch) == NULL);
+}
+
+/* Return true when LOOP is if-convertible. This is a helper function
+ for if_convertible_loop_p. REFS and DDRS are initialized and freed
+ in if_convertible_loop_p. */
+
+static bool
+if_convertible_loop_p_1 (struct loop *loop,
+ vec<loop_p> *loop_nest,
+ vec<data_reference_p> *refs,
+ vec<ddr_p> *ddrs, bool *any_mask_load_store)
+{
+ bool res;
+ unsigned int i;
+ basic_block exit_bb = NULL;
+
+ /* Don't if-convert the loop when the data dependences cannot be
+ computed: the loop won't be vectorized in that case. */
+ res = compute_data_dependences_for_loop (loop, true, loop_nest, refs, ddrs);
+ if (!res)
+ 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);
+ if (!ifc_bbs)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Irreducible loop\n");
+ return false;
+ }
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ basic_block bb = ifc_bbs[i];
+
+ if (!if_convertible_bb_p (loop, bb, exit_bb))
+ return false;
+
+ if (bb_with_exit_edge_p (loop, bb))
+ exit_bb = bb;
+ }
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ basic_block bb = ifc_bbs[i];
+ gimple_stmt_iterator gsi;
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ switch (gimple_code (gsi_stmt (gsi)))
+ {
+ case GIMPLE_LABEL:
+ case GIMPLE_ASSIGN:
+ case GIMPLE_CALL:
+ case GIMPLE_DEBUG:
+ case GIMPLE_COND:
+ break;
+ default:
+ return false;
+ }
+ }
+
+ if (flag_tree_loop_if_convert_stores)
+ {
+ data_reference_p dr;
+
+ for (i = 0; refs->iterate (i, &dr); i++)
+ {
+ dr->aux = XNEW (struct ifc_dr);
+ DR_WRITTEN_AT_LEAST_ONCE (dr) = -1;
+ DR_RW_UNCONDITIONALLY (dr) = -1;
+ }
+ predicate_bbs (loop);
+ }
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ basic_block bb = ifc_bbs[i];
+ gimple_stmt_iterator itr;
+
+ /* Check the if-convertibility of statements in predicated BBs. */
+ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
+ for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
+ if (!if_convertible_stmt_p (gsi_stmt (itr), *refs,
+ any_mask_load_store))
+ return false;
+ }
+
+ if (flag_tree_loop_if_convert_stores)
+ for (i = 0; i < loop->num_nodes; i++)
+ free_bb_predicate (ifc_bbs[i]);
+
+ /* Checking PHIs needs to be done after stmts, as the fact whether there
+ are any masked loads or stores affects the tests. */
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ basic_block bb = ifc_bbs[i];
+ gimple_stmt_iterator itr;
+
+ for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
+ if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr),
+ *any_mask_load_store))
+ return false;
+ }
+
+ if (dump_file)
+ fprintf (dump_file, "Applying if-conversion\n");
return true;
}
- if its basic blocks and phi nodes are if convertible. */
static bool
-if_convertible_loop_p (struct loop *loop)
+if_convertible_loop_p (struct loop *loop, bool *any_mask_load_store)
{
- unsigned int i;
edge e;
edge_iterator ei;
- basic_block exit_bb = NULL;
+ bool res = false;
+ vec<data_reference_p> refs;
+ vec<ddr_p> ddrs;
/* Handle only innermost loop. */
if (!loop || loop->inner)
return false;
}
- /* ??? Check target's vector conditional operation support for vectorizer. */
-
- /* If one of the loop header's edge is exit edge then do not apply
- if-conversion. */
+ /* If one of the loop header's edge is an exit edge then do not
+ apply if-conversion. */
FOR_EACH_EDGE (e, ei, loop->header->succs)
- {
- if (loop_exit_edge_p (loop, e))
- return false;
- }
-
- /* Don't if-convert the loop when the data dependences cannot be
- computed: the loop won't be vectorized in that case. */
- {
- VEC (data_reference_p, heap) *refs = VEC_alloc (data_reference_p, heap, 5);
- VEC (ddr_p, heap) *ddrs = VEC_alloc (ddr_p, heap, 25);
- bool res = compute_data_dependences_for_loop (loop, true, &refs, &ddrs);
-
- free_data_refs (refs);
- free_dependence_relations (ddrs);
-
- if (!res)
+ if (loop_exit_edge_p (loop, e))
return false;
- }
- calculate_dominance_info (CDI_DOMINATORS);
-
- /* Allow statements that can be handled during if-conversion. */
- ifc_bbs = get_loop_body_in_if_conv_order (loop);
- if (!ifc_bbs)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Irreducible loop\n");
- return false;
- }
+ refs.create (5);
+ ddrs.create (25);
+ auto_vec<loop_p, 3> loop_nest;
+ res = if_convertible_loop_p_1 (loop, &loop_nest, &refs, &ddrs,
+ any_mask_load_store);
- for (i = 0; i < loop->num_nodes; i++)
+ if (flag_tree_loop_if_convert_stores)
{
- basic_block bb = ifc_bbs[i];
-
- if (!if_convertible_bb_p (loop, bb, exit_bb))
- return false;
-
- if (bb_with_exit_edge_p (loop, bb))
- exit_bb = bb;
- }
-
- if (!predicate_bbs (loop))
- return false;
-
- for (i = 0; i < loop->num_nodes; i++)
- {
- basic_block bb = ifc_bbs[i];
- gimple_stmt_iterator itr;
-
- for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
- if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
- return false;
-
- /* For non predicated BBs, don't check their statements. */
- if (!is_predicated (bb))
- continue;
+ data_reference_p dr;
+ unsigned int i;
- for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
- if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr)))
- return false;
+ for (i = 0; refs.iterate (i, &dr); i++)
+ free (dr->aux);
}
- if (dump_file)
- fprintf (dump_file, "Applying if-conversion\n");
-
- return true;
+ free_data_refs (refs);
+ free_dependence_relations (ddrs);
+ return res;
}
/* Basic block BB has two predecessors. Using predecessor's bb
if-conversion. */
static basic_block
-find_phi_replacement_condition (struct loop *loop,
- basic_block bb, tree *cond,
- gimple_stmt_iterator *gsi)
+find_phi_replacement_condition (basic_block bb, tree *cond,
+ gimple_stmt_iterator *gsi)
{
edge first_edge, second_edge;
tree tmp_cond;
first_edge = EDGE_PRED (bb, 0);
second_edge = EDGE_PRED (bb, 1);
- /* Use condition based on following criteria:
- 1)
- S1: x = !c ? a : b;
-
- S2: x = c ? b : a;
-
- S2 is preferred over S1. Make 'b' first_bb and use its condition.
-
- 2) Do not make loop header first_bb.
-
- 3)
- S1: x = !(c == d)? a : b;
-
- S21: t1 = c == d;
- S22: x = t1 ? b : a;
-
- S3: x = (c == d) ? b : a;
-
- S3 is preferred over S1 and S2*, Make 'b' first_bb and use
- its condition.
-
- 4) If pred B is dominated by pred A then use pred B's condition.
- See PR23115. */
-
- /* Select condition that is not TRUTH_NOT_EXPR. */
+ /* Prefer an edge with a not negated predicate.
+ ??? That's a very weak cost model. */
tmp_cond = bb_predicate (first_edge->src);
gcc_assert (tmp_cond);
-
if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
{
edge tmp_edge;
second_edge = tmp_edge;
}
- /* Check if FIRST_BB is loop header or not and make sure that
- FIRST_BB does not dominate SECOND_BB. */
- if (first_edge->src == loop->header
- || dominated_by_p (CDI_DOMINATORS,
- second_edge->src, first_edge->src))
+ /* Check if the edge we take the condition from is not critical.
+ We know that at least one non-critical edge exists. */
+ if (EDGE_COUNT (first_edge->src->succs) > 1)
{
*cond = bb_predicate (second_edge->src);
if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
- *cond = invert_truthvalue (*cond);
+ *cond = TREE_OPERAND (*cond, 0);
else
/* Select non loop header bb. */
first_edge = second_edge;
else
*cond = bb_predicate (first_edge->src);
- /* Gimplify the condition: the vectorizer prefers to have gimple
- values as conditions. Various targets use different means to
- communicate conditions in vector compare operations. Using a
- gimple value allows the compiler to emit vector compare and
- select RTL without exposing compare's result. */
- *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond),
- false, NULL_TREE,
- true, GSI_SAME_STMT);
- if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
+ /* Gimplify the condition to a valid cond-expr conditonal operand. */
+ *cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (*cond),
+ is_gimple_condexpr, NULL_TREE,
+ true, GSI_SAME_STMT);
+
+ 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)
{
- gimple new_stmt;
+ 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);
- new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
- gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
- *cond = gimple_assign_lhs (new_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;
- gcc_assert (*cond);
+ /* 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;
+ }
- return first_edge->src;
+ *op0 = r_op1; *op1 = r_op2;
+ *reduc = stmt;
+ return true;
}
-/* Replace PHI node with conditional modify expr using COND. This
- routine does not handle PHI nodes with more than two arguments.
+/* 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.
For example,
- S1: A = PHI <x1(1), x2(5)
+ S1: A = PHI <x1(1), x2(5)>
is converted into,
S2: A = cond ? x1 : x2;
TRUE_BB is selected. */
static void
-replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
- basic_block true_bb,
- gimple_stmt_iterator *gsi)
+predicate_scalar_phi (gimple phi, tree cond,
+ basic_block true_bb,
+ gimple_stmt_iterator *gsi)
{
gimple new_stmt;
basic_block bb;
- tree rhs;
- tree arg;
+ tree rhs, res, arg, scev;
gcc_assert (gimple_code (phi) == GIMPLE_PHI
&& gimple_phi_num_args (phi) == 2);
+ res = gimple_phi_result (phi);
+ /* Do not handle virtual phi nodes. */
+ if (virtual_operand_p (res))
+ return;
+
bb = gimple_bb (phi);
- arg = degenerate_phi_result (phi);
- if (arg)
+ if ((arg = degenerate_phi_result (phi))
+ || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
+ res))
+ && !chrec_contains_undetermined (scev)
+ && scev != res
+ && (arg = gimple_phi_arg_def (phi, 0))))
rhs = arg;
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 = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
- 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 (PHI_RESULT (phi), rhs);
- SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
+ new_stmt = gimple_build_assign (res, rhs);
gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
update_stmt (new_stmt);
}
}
-/* Replaces in LOOP all the phi nodes other than those in the
+/* Replaces in LOOP all the scalar phi nodes other than those in the
LOOP->header block with conditional modify expressions. */
static void
-ifconvert_phi_nodes (struct loop *loop)
+predicate_all_scalar_phis (struct loop *loop)
{
basic_block bb;
unsigned int orig_loop_num_nodes = loop->num_nodes;
/* BB has two predecessors. Using predecessor's aux field, set
appropriate condition for the PHI node replacement. */
gsi = gsi_after_labels (bb);
- true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
+ true_bb = find_phi_replacement_condition (bb, &cond, &gsi);
while (!gsi_end_p (phi_gsi))
{
phi = gsi_stmt (phi_gsi);
- replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi);
+ predicate_scalar_phi (phi, cond, true_bb, &gsi);
release_phi_node (phi);
gsi_next (&phi_gsi);
}
gimplification of the predicates. */
static void
-insert_gimplified_predicates (loop_p loop)
+insert_gimplified_predicates (loop_p loop, bool any_mask_load_store)
{
unsigned int i;
for (i = 0; i < loop->num_nodes; i++)
{
basic_block bb = ifc_bbs[i];
- gimple_seq stmts = bb_predicate_gimplified_stmts (bb);
+ gimple_seq stmts;
- if (stmts)
+ if (!is_predicated (bb))
{
- gimple_stmt_iterator gsi = gsi_last_bb (bb);
+ /* Do not insert statements for a basic block that is not
+ predicated. Also make sure that the predicate of the
+ basic block is set to true. */
+ reset_bb_predicate (bb);
+ continue;
+ }
- if (gsi_end_p (gsi)
- || gimple_code (gsi_stmt (gsi)) == GIMPLE_COND)
- gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
+ stmts = bb_predicate_gimplified_stmts (bb);
+ if (stmts)
+ {
+ if (flag_tree_loop_if_convert_stores
+ || any_mask_load_store)
+ {
+ /* Insert the predicate of the BB just after the label,
+ as the if-conversion of memory writes will use this
+ predicate. */
+ gimple_stmt_iterator gsi = gsi_after_labels (bb);
+ gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
+ }
else
- gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
+ {
+ /* Insert the predicate of the BB at the end of the BB
+ as this would reduce the register pressure: the only
+ use of this predicate will be in successor BBs. */
+ gimple_stmt_iterator gsi = gsi_last_bb (bb);
+
+ if (gsi_end_p (gsi)
+ || stmt_ends_bb_p (gsi_stmt (gsi)))
+ gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
+ else
+ gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
+ }
/* Once the sequence is code generated, set it to NULL. */
set_bb_predicate_gimplified_stmts (bb, NULL);
}
}
+/* Predicate each write to memory in LOOP.
+
+ This function transforms control flow constructs containing memory
+ writes of the form:
+
+ | for (i = 0; i < N; i++)
+ | if (cond)
+ | A[i] = expr;
+
+ into the following form that does not contain control flow:
+
+ | for (i = 0; i < N; i++)
+ | A[i] = cond ? expr : A[i];
+
+ The original CFG looks like this:
+
+ | bb_0
+ | i = 0
+ | end_bb_0
+ |
+ | bb_1
+ | if (i < N) goto bb_5 else goto bb_2
+ | end_bb_1
+ |
+ | bb_2
+ | cond = some_computation;
+ | if (cond) goto bb_3 else goto bb_4
+ | end_bb_2
+ |
+ | bb_3
+ | A[i] = expr;
+ | goto bb_4
+ | end_bb_3
+ |
+ | bb_4
+ | goto bb_1
+ | end_bb_4
+
+ insert_gimplified_predicates inserts the computation of the COND
+ expression at the beginning of the destination basic block:
+
+ | bb_0
+ | i = 0
+ | end_bb_0
+ |
+ | bb_1
+ | if (i < N) goto bb_5 else goto bb_2
+ | end_bb_1
+ |
+ | bb_2
+ | cond = some_computation;
+ | if (cond) goto bb_3 else goto bb_4
+ | end_bb_2
+ |
+ | bb_3
+ | cond = some_computation;
+ | A[i] = expr;
+ | goto bb_4
+ | end_bb_3
+ |
+ | bb_4
+ | goto bb_1
+ | end_bb_4
+
+ predicate_mem_writes is then predicating the memory write as follows:
+
+ | bb_0
+ | i = 0
+ | end_bb_0
+ |
+ | bb_1
+ | if (i < N) goto bb_5 else goto bb_2
+ | end_bb_1
+ |
+ | bb_2
+ | if (cond) goto bb_3 else goto bb_4
+ | end_bb_2
+ |
+ | bb_3
+ | cond = some_computation;
+ | A[i] = cond ? expr : A[i];
+ | goto bb_4
+ | end_bb_3
+ |
+ | bb_4
+ | goto bb_1
+ | end_bb_4
+
+ and finally combine_blocks removes the basic block boundaries making
+ the loop vectorizable:
+
+ | bb_0
+ | i = 0
+ | if (i < N) goto bb_5 else goto bb_1
+ | end_bb_0
+ |
+ | bb_1
+ | cond = some_computation;
+ | A[i] = cond ? expr : A[i];
+ | if (i < N) goto bb_5 else goto bb_4
+ | end_bb_1
+ |
+ | bb_4
+ | goto bb_1
+ | end_bb_4
+*/
+
+static void
+predicate_mem_writes (loop_p loop)
+{
+ unsigned int i, orig_loop_num_nodes = loop->num_nodes;
+
+ for (i = 1; i < orig_loop_num_nodes; i++)
+ {
+ gimple_stmt_iterator gsi;
+ basic_block bb = ifc_bbs[i];
+ tree cond = bb_predicate (bb);
+ bool swap;
+ gimple stmt;
+
+ if (is_true_predicate (cond))
+ continue;
+
+ swap = false;
+ if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
+ {
+ swap = true;
+ cond = TREE_OPERAND (cond, 0);
+ }
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ if (!gimple_assign_single_p (stmt = gsi_stmt (gsi)))
+ continue;
+ else if (gimple_plf (stmt, GF_PLF_2))
+ {
+ tree lhs = gimple_assign_lhs (stmt);
+ tree rhs = gimple_assign_rhs1 (stmt);
+ tree ref, addr, ptr, masktype, mask_op0, mask_op1, mask;
+ gimple new_stmt;
+ int bitsize = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs)));
+
+ masktype = build_nonstandard_integer_type (bitsize, 1);
+ mask_op0 = build_int_cst (masktype, swap ? 0 : -1);
+ mask_op1 = build_int_cst (masktype, swap ? -1 : 0);
+ ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs;
+ mark_addressable (ref);
+ addr = force_gimple_operand_gsi (&gsi, build_fold_addr_expr (ref),
+ true, NULL_TREE, true,
+ GSI_SAME_STMT);
+ cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
+ is_gimple_condexpr, NULL_TREE,
+ true, GSI_SAME_STMT);
+ mask = fold_build_cond_expr (masktype, unshare_expr (cond),
+ mask_op0, mask_op1);
+ mask = ifc_temp_var (masktype, mask, &gsi);
+ ptr = build_int_cst (reference_alias_ptr_type (ref), 0);
+ /* Copy points-to info if possible. */
+ if (TREE_CODE (addr) == SSA_NAME && !SSA_NAME_PTR_INFO (addr))
+ copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr),
+ ref);
+ if (TREE_CODE (lhs) == SSA_NAME)
+ {
+ new_stmt
+ = gimple_build_call_internal (IFN_MASK_LOAD, 3, addr,
+ ptr, mask);
+ gimple_call_set_lhs (new_stmt, lhs);
+ }
+ else
+ new_stmt
+ = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr,
+ mask, rhs);
+ gsi_replace (&gsi, new_stmt, true);
+ }
+ else if (gimple_vdef (stmt))
+ {
+ tree lhs = gimple_assign_lhs (stmt);
+ tree rhs = gimple_assign_rhs1 (stmt);
+ tree type = TREE_TYPE (lhs);
+
+ lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
+ rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
+ if (swap)
+ {
+ tree tem = lhs;
+ lhs = rhs;
+ rhs = tem;
+ }
+ cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
+ is_gimple_condexpr, NULL_TREE,
+ true, GSI_SAME_STMT);
+ rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs);
+ gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
+ update_stmt (stmt);
+ }
+ }
+}
+
/* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
other than the exit and latch of the LOOP. Also resets the
GIMPLE_DEBUG information. */
blocks. Replace PHI nodes with conditional modify expressions. */
static void
-combine_blocks (struct loop *loop)
+combine_blocks (struct loop *loop, bool any_mask_load_store)
{
basic_block bb, exit_bb, merge_target_bb;
unsigned int orig_loop_num_nodes = loop->num_nodes;
edge e;
edge_iterator ei;
+ predicate_bbs (loop);
remove_conditions_and_labels (loop);
- insert_gimplified_predicates (loop);
- ifconvert_phi_nodes (loop);
+ insert_gimplified_predicates (loop, any_mask_load_store);
+ predicate_all_scalar_phis (loop);
+
+ if (flag_tree_loop_if_convert_stores || any_mask_load_store)
+ predicate_mem_writes (loop);
/* Merge basic blocks: first remove all the edges in the loop,
except for those from the exit block. */
for (i = 0; i < orig_loop_num_nodes; i++)
{
bb = ifc_bbs[i];
+ free_bb_predicate (bb);
if (bb_with_exit_edge_p (loop, bb))
{
+ gcc_assert (exit_bb == NULL);
exit_bb = bb;
- break;
}
}
gcc_assert (exit_bb != loop->latch);
&& exit_bb != loop->header
&& can_merge_blocks_p (loop->header, exit_bb))
merge_blocks (loop->header, exit_bb);
+
+ free (ifc_bbs);
+ ifc_bbs = NULL;
}
-/* If-convert LOOP when it is legal. For the moment this pass has no
- profitability analysis. Returns true when something changed. */
+/* Version LOOP before if-converting it, the original loop
+ will be then if-converted, the new copy of the loop will not,
+ and the LOOP_VECTORIZED internal call will be guarding which
+ loop to execute. The vectorizer pass will fold this
+ internal call into either true or false. */
static bool
+version_loop_for_if_conversion (struct loop *loop)
+{
+ basic_block cond_bb;
+ tree cond = make_ssa_name (boolean_type_node, NULL);
+ struct loop *new_loop;
+ gimple g;
+ gimple_stmt_iterator gsi;
+
+ g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2,
+ build_int_cst (integer_type_node, loop->num),
+ integer_zero_node);
+ gimple_call_set_lhs (g, cond);
+
+ initialize_original_copy_tables ();
+ new_loop = loop_version (loop, cond, &cond_bb,
+ REG_BR_PROB_BASE, REG_BR_PROB_BASE,
+ REG_BR_PROB_BASE, true);
+ free_original_copy_tables ();
+ if (new_loop == NULL)
+ return false;
+ new_loop->dont_vectorize = true;
+ 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);
+ update_ssa (TODO_update_ssa);
+ return true;
+}
+
+/* If-convert LOOP when it is legal. For the moment this pass has no
+ profitability analysis. Returns non-zero todo flags when something
+ changed. */
+
+static unsigned int
tree_if_conversion (struct loop *loop)
{
- bool changed = false;
+ unsigned int todo = 0;
ifc_bbs = NULL;
+ bool any_mask_load_store = false;
- if (!if_convertible_loop_p (loop)
+ if (!if_convertible_loop_p (loop, &any_mask_load_store)
|| !dbg_cnt (if_conversion_tree))
goto cleanup;
+ if (any_mask_load_store
+ && ((!flag_tree_loop_vectorize && !loop->force_vectorize)
+ || loop->dont_vectorize))
+ goto cleanup;
+
+ if (any_mask_load_store && !version_loop_for_if_conversion (loop))
+ goto cleanup;
+
/* Now all statements are if-convertible. Combine all the basic
blocks into one huge basic block doing the if-conversion
on-the-fly. */
- combine_blocks (loop);
- changed = true;
+ combine_blocks (loop, any_mask_load_store);
+
+ todo |= TODO_cleanup_cfg;
+ if (flag_tree_loop_if_convert_stores || any_mask_load_store)
+ {
+ mark_virtual_operands_for_renaming (cfun);
+ todo |= TODO_update_ssa_only_virtuals;
+ }
cleanup:
if (ifc_bbs)
free (ifc_bbs);
ifc_bbs = NULL;
}
+ free_dominance_info (CDI_POST_DOMINATORS);
- return changed;
+ return todo;
}
/* Tree if-conversion pass management. */
-static unsigned int
-main_tree_if_conversion (void)
+namespace {
+
+const pass_data pass_data_if_conversion =
{
- loop_iterator li;
- struct loop *loop;
- bool changed = false;
+ GIMPLE_PASS, /* type */
+ "ifcvt", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_NONE, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
- if (number_of_loops () <= 1)
- return 0;
+class pass_if_conversion : public gimple_opt_pass
+{
+public:
+ pass_if_conversion (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_if_conversion, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *);
+ virtual unsigned int execute (function *);
- FOR_EACH_LOOP (li, loop, 0)
- changed |= tree_if_conversion (loop);
+}; // class pass_if_conversion
- return changed ? TODO_cleanup_cfg : 0;
+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);
}
-static bool
-gate_tree_if_conversion (void)
+unsigned int
+pass_if_conversion::execute (function *fun)
{
- return flag_tree_vectorize != 0;
+ 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;
}
-struct gimple_opt_pass pass_if_conversion =
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_if_conversion (gcc::context *ctxt)
{
- {
- GIMPLE_PASS,
- "ifcvt", /* name */
- gate_tree_if_conversion, /* gate */
- main_tree_if_conversion, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_NONE, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_dump_func | TODO_verify_stmts | TODO_verify_flow
- /* todo_flags_finish */
- }
-};
+ return new pass_if_conversion (ctxt);
+}