@@ -81,6 +81,8 @@ extern void bitmap_union_of_preds (sbitmap, sbitmap *, basic_block);
extern basic_block * single_pred_before_succ_order (void);
extern edge single_incoming_edge_ignoring_loop_edges (basic_block, bool);
extern edge single_pred_edge_ignoring_loop_edges (basic_block, bool);
+extern bool can_remove_breaks (class loop *, unsigned int, basic_block *,
+ edge *, vec<edge> *);
#endif /* GCC_CFGANAL_H */
@@ -268,6 +268,11 @@ public:
the basic-block from being collected but its index can still be
reused. */
basic_block former_header;
+
+ /* Used for loops that used to contain breaks. After removing of breaks this
+ tree is set to a variable that is true if we during the current iteration
+ we would have exited the loop due to the break condition. */
+ tree early_break_cond;
};
/* Set if the loop is known to be infinite. */
@@ -876,4 +881,17 @@ gcov_type_to_wide_int (gcov_type val)
return widest_int::from_array (a, 2);
}
+
+/* Function bb_in_loop_p
+
+ Used as predicate for dfs order traversal of the loop bbs. */
+
+inline bool
+bb_in_loop_p (const_basic_block bb, const void *data)
+{
+ const class loop *const loop = (const class loop *)data;
+ if (flow_bb_inside_loop_p (loop, bb))
+ return true;
+ return false;
+}
#endif /* GCC_CFGLOOP_H */
@@ -99,6 +99,7 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-fold.h"
#include "gimplify.h"
#include "gimple-iterator.h"
+#include "gimple-walk.h"
#include "gimplify-me.h"
#include "tree-cfg.h"
#include "tree-into-ssa.h"
@@ -2727,7 +2728,8 @@ combine_blocks (class loop *loop)
consistent after the condition is folded in the vectorizer. */
static class loop *
-version_loop_for_if_conversion (class loop *loop, vec<gimple *> *preds)
+version_loop_for_if_conversion (class loop *loop, vec<gimple *> *preds,
+ bool save_preds = true)
{
basic_block cond_bb;
tree cond = make_ssa_name (boolean_type_node);
@@ -2741,11 +2743,15 @@ version_loop_for_if_conversion (class loop *loop, vec<gimple *> *preds)
integer_zero_node);
gimple_call_set_lhs (g, cond);
- /* Save BB->aux around loop_version as that uses the same field. */
- save_length = loop->inner ? loop->inner->num_nodes : loop->num_nodes;
- void **saved_preds = XALLOCAVEC (void *, save_length);
- for (unsigned i = 0; i < save_length; i++)
- saved_preds[i] = ifc_bbs[i]->aux;
+ void **saved_preds;
+ if (save_preds)
+ {
+ /* Save BB->aux around loop_version as that uses the same field. */
+ save_length = loop->inner ? loop->inner->num_nodes : loop->num_nodes;
+ saved_preds = XALLOCAVEC (void *, save_length);
+ for (unsigned i = 0; i < save_length; i++)
+ saved_preds[i] = ifc_bbs[i]->aux;
+ }
initialize_original_copy_tables ();
/* At this point we invalidate porfile confistency until IFN_LOOP_VECTORIZED
@@ -2757,8 +2763,11 @@ version_loop_for_if_conversion (class loop *loop, vec<gimple *> *preds)
profile_probability::always (), true);
free_original_copy_tables ();
- for (unsigned i = 0; i < save_length; i++)
- ifc_bbs[i]->aux = saved_preds[i];
+ if (save_preds)
+ {
+ for (unsigned i = 0; i < save_length; i++)
+ ifc_bbs[i]->aux = saved_preds[i];
+ }
if (new_loop == NULL)
return NULL;
@@ -2813,6 +2822,404 @@ versionable_outer_loop_p (class loop *loop)
return true;
}
+bool
+mem_ref_maybe_out_of_bounds (tree ref)
+{
+ tree arg = TREE_OPERAND (ref, 0);
+ /* The constant and variable offset of the reference. */
+ tree cstoff = TREE_OPERAND (ref, 1);
+ tree varoff = NULL_TREE;
+
+ const offset_int maxobjsize = tree_to_shwi (max_object_size ());
+
+ /* The array or string constant bounds in bytes. Initially set
+ to [-MAXOBJSIZE - 1, MAXOBJSIZE] until a tighter bound is
+ determined. */
+ offset_int arrbounds[2] = { -maxobjsize - 1, maxobjsize };
+
+ offset_int ioff = wi::to_offset (fold_convert (ptrdiff_type_node, cstoff));
+
+ /* The range of the byte offset into the reference. */
+ offset_int offrange[2] = { 0, 0 };
+
+ /* Determine the offsets and increment OFFRANGE for the bounds of each.
+ The loop computes the range of the final offset for expressions such
+ as (A + i0 + ... + iN)[CSTOFF] where i0 through iN are SSA_NAMEs in
+ some range. */
+ const unsigned limit = 10;
+ for (unsigned n = 0; TREE_CODE (arg) == SSA_NAME && n < limit; ++n)
+ {
+ gimple *def = SSA_NAME_DEF_STMT (arg);
+ if (!is_gimple_assign (def))
+ break;
+
+ tree_code code = gimple_assign_rhs_code (def);
+ if (code == POINTER_PLUS_EXPR)
+ {
+ arg = gimple_assign_rhs1 (def);
+ varoff = gimple_assign_rhs2 (def);
+ }
+ else if (code == ASSERT_EXPR)
+ {
+ arg = TREE_OPERAND (gimple_assign_rhs1 (def), 0);
+ continue;
+ }
+ else
+ return true;
+
+ /* VAROFF should always be a SSA_NAME here (and not even
+ INTEGER_CST) but there's no point in taking chances. */
+ if (TREE_CODE (varoff) != SSA_NAME)
+ return true;
+
+ wide_int min_wi, max_wi;
+
+ enum value_range_kind range_type
+ = determine_value_range (varoff, &min_wi, &max_wi);
+
+ if (range_type != VR_RANGE)
+ return true;
+
+ offset_int min
+ = wi::to_offset (wide_int_to_tree (ptrdiff_type_node, min_wi));
+ offset_int max
+ = wi::to_offset (wide_int_to_tree (ptrdiff_type_node, max_wi));
+ if (min < max)
+ {
+ offrange[0] += min;
+ offrange[1] += max;
+ }
+ else
+ {
+ /* When MIN >= MAX, the offset is effectively in a union
+ of two ranges: [-MAXOBJSIZE -1, MAX] and [MIN, MAXOBJSIZE].
+ Since there is no way to represent such a range across
+ additions, conservatively add [-MAXOBJSIZE -1, MAXOBJSIZE]
+ to OFFRANGE. */
+ offrange[0] += arrbounds[0];
+ offrange[1] += arrbounds[1];
+ }
+
+ if (offrange[0] < arrbounds[0])
+ offrange[0] = arrbounds[0];
+
+ if (offrange[1] > arrbounds[1])
+ offrange[1] = arrbounds[1];
+ }
+
+ if (TREE_CODE (arg) == ADDR_EXPR)
+ {
+ arg = TREE_OPERAND (arg, 0);
+ if (TREE_CODE (arg) != STRING_CST
+ && TREE_CODE (arg) != PARM_DECL
+ && TREE_CODE (arg) != VAR_DECL)
+ return true;
+ }
+ else if (TREE_CODE (arg) == SSA_NAME)
+ {
+ gimple *def = SSA_NAME_DEF_STMT (arg);
+ tree pointer = TREE_TYPE (arg);
+ if (def != NULL && gimple_code (def) == GIMPLE_NOP
+ && POINTER_TYPE_P (pointer)
+ && RECORD_OR_UNION_TYPE_P (TREE_TYPE (pointer))
+ && TYPE_CXX_ODR_P (TREE_TYPE (pointer)))
+ /* We are dealing with a global object of sorts, always OK to access
+ it. */
+ return false;
+ else
+ return true;
+ }
+ else
+ return true;
+
+ /* The type of the object being referred to. It can be an array,
+ string literal, or a non-array type when the MEM_REF represents
+ a reference/subscript via a pointer to an object that is not
+ an element of an array. Incomplete types are excluded as well
+ because their size is not known. */
+ tree reftype = TREE_TYPE (arg);
+ if (POINTER_TYPE_P (reftype)
+ || !COMPLETE_TYPE_P (reftype)
+ || TREE_CODE (TYPE_SIZE_UNIT (reftype)) != INTEGER_CST)
+ return true;
+
+ /* Except in declared objects, references to trailing array members
+ of structs and union objects are excluded because MEM_REF doesn't
+ make it possible to identify the member where the reference
+ originated. */
+ if (RECORD_OR_UNION_TYPE_P (reftype)
+ && (!VAR_P (arg)
+ || (DECL_EXTERNAL (arg) && array_at_struct_end_p (ref))))
+ return true;
+
+ arrbounds[0] = 0;
+
+ offset_int eltsize;
+ if (TREE_CODE (reftype) == ARRAY_TYPE)
+ {
+ eltsize = wi::to_offset (TYPE_SIZE_UNIT (TREE_TYPE (reftype)));
+ if (tree dom = TYPE_DOMAIN (reftype))
+ {
+ tree bnds[] = { TYPE_MIN_VALUE (dom), TYPE_MAX_VALUE (dom) };
+ if (TREE_CODE (arg) == COMPONENT_REF)
+ {
+ offset_int size = maxobjsize;
+ if (tree fldsize = component_ref_size (arg))
+ size = wi::to_offset (fldsize);
+ arrbounds[1] = wi::lrshift (size, wi::floor_log2 (eltsize));
+ }
+ else if (array_at_struct_end_p (arg) || !bnds[0] || !bnds[1])
+ arrbounds[1] = wi::lrshift (maxobjsize, wi::floor_log2 (eltsize));
+ else
+ arrbounds[1] = (wi::to_offset (bnds[1]) - wi::to_offset (bnds[0])) * eltsize;
+ }
+ else
+ arrbounds[1] = wi::lrshift (maxobjsize, wi::floor_log2 (eltsize));
+
+ if (TREE_CODE (ref) == MEM_REF)
+ {
+ /* For MEM_REF determine a tighter bound of the non-array
+ element type. */
+ tree eltype = TREE_TYPE (reftype);
+ while (TREE_CODE (eltype) == ARRAY_TYPE)
+ eltype = TREE_TYPE (eltype);
+ eltsize = wi::to_offset (TYPE_SIZE_UNIT (eltype));
+ }
+ }
+ else
+ {
+ eltsize = 1;
+ tree size = TYPE_SIZE_UNIT (reftype);
+ if (VAR_P (arg))
+ if (tree initsize = DECL_SIZE_UNIT (arg))
+ if (tree_int_cst_lt (size, initsize))
+ size = initsize;
+
+ arrbounds[1] = wi::to_offset (size);
+ }
+
+ offrange[0] += ioff;
+ offrange[1] += ioff;
+
+ if (arrbounds[0] == arrbounds[1]
+ || offrange[0] >= arrbounds[1]
+ || offrange[1] < arrbounds[0])
+ return true;
+
+ return !(offrange[0] >= arrbounds[0] && offrange[1] <= arrbounds[1]);
+}
+
+bool
+array_ref_maybe_out_of_bounds (tree ref)
+{
+ tree low_sub = TREE_OPERAND (ref, 1);
+ tree up_sub = low_sub;
+ tree up_bound = array_ref_up_bound (ref);
+
+ tree up_bound_p1;
+
+ if (!up_bound
+ || TREE_CODE (up_bound) != INTEGER_CST)
+ return true;
+
+
+ up_bound_p1 = int_const_binop (PLUS_EXPR, up_bound,
+ build_int_cst (TREE_TYPE (up_bound), 1));
+
+ tree low_bound = array_ref_low_bound (ref);
+
+ /* Empty array. */
+ if (tree_int_cst_equal (low_bound, up_bound_p1))
+ return true;
+
+
+ enum value_range_kind range_type = VR_UNDEFINED;
+ if (TREE_CODE (low_sub) == SSA_NAME)
+ {
+ wide_int min_wi, max_wi;
+ range_type = determine_value_range (low_sub, &min_wi, &max_wi);
+
+ if (range_type != VR_UNDEFINED && range_type != VR_VARYING)
+ {
+ tree min = wide_int_to_tree (TREE_TYPE (low_sub), min_wi);
+ tree max = wide_int_to_tree (TREE_TYPE (low_sub), max_wi);
+ low_sub = range_type == VR_RANGE ? max : min;
+ up_sub = range_type == VR_RANGE ? min : max;
+ }
+ }
+
+ if (range_type == VR_ANTI_RANGE)
+ {
+ if (up_bound
+ && TREE_CODE (up_sub) == INTEGER_CST
+ && tree_int_cst_le (up_bound, up_sub)
+ && TREE_CODE (low_sub) == INTEGER_CST
+ && tree_int_cst_le (low_sub, low_bound))
+ return true;
+ }
+ else if (up_bound
+ && TREE_CODE (up_sub) == INTEGER_CST
+ && !tree_int_cst_le (up_sub, up_bound))
+ return true;
+ else if (TREE_CODE (low_sub) == INTEGER_CST
+ && tree_int_cst_lt (low_sub, low_bound))
+ return true;
+
+ return false;
+}
+
+static tree
+check_array_bounds (tree *tp, int *walk_subtree, void *data)
+{
+ tree t = *tp;
+ struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
+ bool *maybe_out_of_bounds = (bool*) wi->info;
+
+ if (*maybe_out_of_bounds)
+ {
+ *walk_subtree = FALSE;
+ return NULL_TREE;
+ }
+
+ *walk_subtree = TRUE;
+
+ if (TREE_CODE (t) == ARRAY_REF)
+ *maybe_out_of_bounds = array_ref_maybe_out_of_bounds (t);
+ else if (TREE_CODE (t) == MEM_REF)
+ *maybe_out_of_bounds = mem_ref_maybe_out_of_bounds (t);
+
+ return NULL_TREE;
+}
+
+
+bool
+can_remove_breaks (class loop *loop, unsigned int nbbs, basic_block *bbs,
+ edge *natural_loop_exit_p, vec<edge> *breaks)
+{
+ if (loop->num_nodes <= 2 || loop->inner || single_exit (loop))
+ return false;
+
+ for (unsigned int i = 0; i < nbbs; ++i)
+ {
+ basic_block bb = bbs[i];
+
+ for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gimple *stmt = gsi_stmt (gsi);
+ struct walk_stmt_info wi;
+
+ switch (gimple_code (stmt))
+ {
+ case GIMPLE_ASSIGN:
+ if (TREE_CODE (gimple_assign_lhs (stmt)) == MEM_REF)
+ return false;
+ break;
+ /* Do not remove breaks in loops with calls or inline
+ assembly. */
+ case GIMPLE_ASM:
+ case GIMPLE_CALL:
+ return false;
+ default:
+ break;
+ }
+
+ if (is_gimple_debug (stmt))
+ continue;
+
+ bool maybe_out_of_bounds = false;
+ memset (&wi, 0, sizeof (wi));
+ wi.info = &maybe_out_of_bounds;
+ walk_gimple_op (stmt, check_array_bounds, &wi);
+ if (maybe_out_of_bounds)
+ return false;
+ }
+ }
+
+ /* TODO: enable cases with if (cond) { break; } else { something else; } */
+ if (!single_pred_p (loop->latch))
+ return false;
+
+ /* Find the early exit and the condition for it. */
+ basic_block bb_with_latch_cond = single_pred (loop->latch);
+ if (!bb_with_latch_cond)
+ return false;
+
+ gimple *latch_condition = gsi_stmt (gsi_last_bb (bb_with_latch_cond));
+
+ if (gimple_code (latch_condition) != GIMPLE_COND)
+ return false;
+
+ /* The latch should only have one predecessor. */
+ edge latch_pred_e = single_pred_edge (loop->latch);
+ if (latch_pred_e == NULL)
+ return false;
+
+ /* Look for the natural loop exit, this should be the non-latch successor edge
+ of the latch's predecessor. */
+ edge e;
+ edge_iterator ei;
+ edge natural_loop_exit = NULL;
+ FOR_EACH_EDGE (e, ei, latch_pred_e->src->succs)
+ {
+ if (e != latch_pred_e)
+ natural_loop_exit = e;
+ }
+
+ if (natural_loop_exit == NULL)
+ return false;
+
+ vec<edge> exits = get_loop_exit_edges (loop);
+ for(unsigned int i = 0; i < exits.length (); ++i)
+ {
+ if (exits[i] != natural_loop_exit)
+ {
+ breaks->safe_push (exits[i]);
+ /* TODO: Support breaks with same destination as natural exit.
+ Shouldn't be too difficult, I believe adding an extra basic block
+ with a conditional jump would work. */
+ if (exits[i]->dest == natural_loop_exit->dest)
+ return false;
+
+ gimple *break_stmt = gsi_stmt (gsi_last_bb (exits[0]->src));
+ tree_code code = gimple_cond_code (break_stmt);
+ tree lhs = gimple_cond_lhs (break_stmt);
+ bool use_min_for_eq = ((code == EQ_EXPR || code == NE_EXPR)
+ && TREE_CODE (TREE_TYPE (lhs)) == INTEGER_TYPE);
+ /* Only support cases that we can transform into a MIN expr. */
+ if (!use_min_for_eq)
+ return false;
+ }
+
+ /* For a loop that is in loop closed SSA form any values escaping the
+ loop must do so via a PHI-node in an exit BB. Use this property to
+ verify that there is no such value escaping the loop. */
+ for (gphi_iterator si = gsi_start_phis (exits[i]->dest); !gsi_end_p (si);
+ gsi_next (&si))
+ {
+ gphi *phi = si.phi ();
+ for (unsigned int j = 0; j < gimple_phi_num_args (phi); ++j)
+ {
+ tree arg = gimple_phi_arg_def (phi, j);
+ if (TREE_CODE (arg) == SSA_NAME
+ && SSA_NAME_DEF_STMT (arg)->bb != NULL
+ && flow_bb_inside_loop_p (loop, SSA_NAME_DEF_STMT (arg)->bb))
+ return false;
+ }
+ }
+ }
+
+ /* TODO: Support multiple break stmts. */
+ if (breaks->length () > 1)
+ return false;
+
+ if (natural_loop_exit_p)
+ *natural_loop_exit_p = natural_loop_exit;
+
+ need_to_predicate = true;
+ return true;
+}
+
/* Performs splitting of critical edges. Skip splitting and return false
if LOOP will not be converted because:
@@ -2834,7 +3241,7 @@ ifcvt_split_critical_edges (class loop *loop, bool aggressive_if_conv)
auto_vec<edge> critical_edges;
/* Loop is not well formed. */
- if (num <= 2 || loop->inner || !single_exit (loop))
+ if (num > 2 || loop->inner || !single_exit (loop))
return false;
body = get_loop_body (loop);
@@ -3004,6 +3411,207 @@ ifcvt_local_dce (class loop *loop)
}
}
+static unsigned int
+simplify_loop_control_flow (class loop *loop, edge natural_loop_exit,
+ vec<edge> breaks)
+{
+ unsigned int todo = 0;
+
+ /* Add PHI-node to keep track of new break condition. */
+ basic_block break_src = breaks[0]->src;
+
+ gimple *break_stmt = gsi_stmt (gsi_last_bb (breaks[0]->src));
+ gcc_assert (gimple_code (break_stmt) == GIMPLE_COND);
+ bool negate = breaks[0]->flags & EDGE_FALSE_VALUE;
+
+ tree_code code = gimple_cond_code (break_stmt);
+ tree lhs = gimple_cond_lhs (break_stmt);
+ tree rhs = gimple_cond_rhs (break_stmt);
+
+ bool use_min_for_eq = ((code == EQ_EXPR || code == NE_EXPR)
+ && TREE_CODE (TREE_TYPE (lhs)) == INTEGER_TYPE);
+
+ tree cond_var = make_temp_ssa_name (use_min_for_eq
+ ? unsigned_type_for (TREE_TYPE (lhs))
+ : boolean_type_node, NULL, "break_cond");
+
+ gphi *break_phi = create_phi_node (cond_var, loop->header);
+ add_phi_arg (break_phi, use_min_for_eq
+ ? build_one_cst (TREE_TYPE (cond_var))
+ : build_zero_cst (boolean_type_node),
+ loop_preheader_edge (loop), UNKNOWN_LOCATION);
+
+ /* Construct break condition variable from original break stmt. */
+ tree phi_arg;
+
+ if (use_min_for_eq)
+ {
+ phi_arg = fold_build2 (MINUS_EXPR, TREE_TYPE (lhs), lhs, rhs);
+ phi_arg = fold_build1 (NOP_EXPR, TREE_TYPE (cond_var), phi_arg);
+ if (code == NE_EXPR)
+ phi_arg = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond_var), phi_arg);
+ phi_arg = fold_build2 (MIN_EXPR, TREE_TYPE (cond_var), phi_arg,
+ gimple_phi_result (break_phi));
+ }
+ else
+ {
+ phi_arg = build2 (gimple_cond_code (break_stmt), boolean_type_node,
+ gimple_cond_lhs (break_stmt),
+ gimple_cond_rhs (break_stmt));
+ if (negate)
+ phi_arg = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, phi_arg);
+
+ phi_arg = fold_build3 (COND_EXPR, boolean_type_node, phi_arg,
+ build_one_cst (boolean_type_node),
+ gimple_phi_result (break_phi));
+
+ }
+
+ /* Save break target's BB and remove break edge. */
+ gimple_stmt_iterator gsi = gsi_last_bb (break_src);
+ gsi_remove (&gsi, true);
+ basic_block break_target = breaks[0]->dest;
+ auto_vec<std::pair<gphi*, tree> > to_copy_phis;
+
+ for (gphi_iterator itr = gsi_start_phis (breaks[0]->dest);
+ !gsi_end_p(itr); gsi_next (&itr))
+ {
+ gphi *phi = itr.phi ();
+ tree var = gimple_phi_arg_def (phi, breaks[0]->dest_idx);
+ to_copy_phis.safe_push (std::make_pair (phi, var));
+ }
+
+ remove_edge (breaks[0]);
+
+ /* Make sure the other edge is now a FALLTHRU edge. */
+ edge fallthru_e = single_succ_edge (break_src);
+ gcc_assert (fallthru_e);
+ fallthru_e->flags &= ~(negate ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE);
+ fallthru_e->flags |= EDGE_FALLTHRU;
+
+ /* Update break condition. */
+ gimple_seq stmts;
+ phi_arg = force_gimple_operand (phi_arg, &stmts, true, NULL);
+ gsi = gsi_last_bb (break_src);
+ gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
+
+ /* If the basic block where the break condition is computed does not dominate
+ the natural loop exit block, then we must add a PHI-node this to block to
+ ensure correct def-use. */
+ if (!dominated_by_p (CDI_DOMINATORS, natural_loop_exit->src, break_src))
+ {
+ edge e;
+ edge_iterator ei;
+ cond_var = make_temp_ssa_name (TREE_TYPE (phi_arg), NULL, "break_cond");
+ gphi *new_phi = create_phi_node (cond_var, natural_loop_exit->src);
+
+ FOR_EACH_EDGE (e, ei, natural_loop_exit->src->preds)
+ {
+ if (dominated_by_p (CDI_DOMINATORS, e->src, break_src))
+ add_phi_arg (new_phi, phi_arg, e, UNKNOWN_LOCATION);
+ else
+ add_phi_arg (new_phi, gimple_phi_result (break_phi), e,
+ UNKNOWN_LOCATION);
+ }
+
+ phi_arg = gimple_phi_result (new_phi);
+ }
+
+ /* Add updated condition to PHI-node. */
+ add_phi_arg (break_phi, phi_arg, loop_latch_edge (loop), UNKNOWN_LOCATION);
+
+ loop->early_break_cond = phi_arg;
+
+ /* Construct new block with the new break condition. */
+ basic_block new_bb = split_edge (natural_loop_exit);
+
+ /* Put the result in a single option PHI-node to make sure
+ loop_closed_ssa_def check doesn't fail. */
+ cond_var = make_temp_ssa_name (TREE_TYPE (phi_arg), NULL, "break_cond");
+ break_phi = create_phi_node (cond_var, new_bb);
+ add_phi_arg (break_phi, phi_arg, single_pred_edge (new_bb),
+ UNKNOWN_LOCATION);
+
+ if (use_min_for_eq && ((code == EQ_EXPR) ^ negate))
+ {
+ cond_var = fold_build2 (EQ_EXPR, boolean_type_node, cond_var,
+ build_zero_cst (TREE_TYPE (cond_var)));
+ }
+
+ gimple *cond_stmt = gimple_build_cond_from_tree (cond_var, NULL_TREE,
+ NULL_TREE);
+ gsi = gsi_last_bb (new_bb);
+ gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
+
+ /* Fix up edges of new block. */
+ edge false_e = single_succ_edge (new_bb);
+ edge true_e = NULL;
+
+ /* TODO: set probabilities! */
+ if (false_e->dest == break_target)
+ {
+ true_e = false_e;
+ false_e = make_edge (new_bb, natural_loop_exit->dest, EDGE_FALSE_VALUE);
+ true_e->flags &= ~EDGE_FALLTHRU;
+ true_e->flags = EDGE_TRUE_VALUE;
+ }
+ else
+ {
+ false_e->flags &= ~EDGE_FALLTHRU;
+ false_e->flags |= EDGE_FALSE_VALUE;
+ true_e = make_edge (new_bb, break_target, EDGE_TRUE_VALUE);
+ }
+
+ std::pair<gphi*, tree> *el;
+ unsigned int ix;
+ FOR_EACH_VEC_ELT (to_copy_phis, ix, el)
+ {
+ add_phi_arg (el->first, el->second, true_e, UNKNOWN_LOCATION);
+ if (virtual_operand_p (el->second))
+ {
+ mark_virtual_operand_for_renaming (el->second);
+ todo |= TODO_update_ssa_only_virtuals;
+ }
+ }
+
+ return todo;
+}
+
+static bool
+version_loop (class loop *loop, class loop **rloop, vec<gimple *> *preds,
+ bool save_preds)
+{
+ class loop *vloop
+ = (versionable_outer_loop_p (loop_outer (loop))
+ ? loop_outer (loop) : loop);
+ class loop *nloop = version_loop_for_if_conversion (vloop, preds, save_preds);
+ if (nloop == NULL)
+ return false;
+ if (vloop != loop)
+ {
+ /* If versionable_outer_loop_p decided to version the
+ outer loop, version also the inner loop of the non-vectorized
+ loop copy. So we transform:
+ loop1
+ loop2
+ into:
+ if (LOOP_VECTORIZED (1, 3))
+ {
+ loop1
+ loop2
+ }
+ else
+ loop3 (copy of loop1)
+ if (LOOP_VECTORIZED (4, 5))
+ loop4 (copy of loop2)
+ else
+ loop5 (copy of loop4) */
+ gcc_assert (nloop->inner && nloop->inner->next == NULL);
+ *rloop = nloop->inner;
+ }
+ 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. */
@@ -3015,6 +3623,8 @@ tree_if_conversion (class loop *loop, vec<gimple *> *preds)
bool aggressive_if_conv;
class loop *rloop;
bitmap exit_bbs;
+ auto_vec<edge> breaks;
+ edge natural_loop_exit;
again:
rloop = NULL;
@@ -3033,14 +3643,20 @@ tree_if_conversion (class loop *loop, vec<gimple *> *preds)
aggressive_if_conv = true;
}
- if (!ifcvt_split_critical_edges (loop, aggressive_if_conv))
+ basic_block *bbs = XCNEWVEC (basic_block, loop->num_nodes);
+
+ unsigned int nbbs = dfs_enumerate_from (loop->header, 0, bb_in_loop_p, bbs,
+ loop->num_nodes, loop);
+
+ if (!ifcvt_split_critical_edges (loop, aggressive_if_conv)
+ && !can_remove_breaks (loop, nbbs, bbs, &natural_loop_exit, &breaks))
goto cleanup;
- if (!if_convertible_loop_p (loop)
+ if (!(if_convertible_loop_p (loop) || !breaks.is_empty ())
|| !dbg_cnt (if_conversion_tree))
goto cleanup;
- if ((need_to_predicate || any_complicated_phi)
+ if ((need_to_predicate || any_complicated_phi || !breaks.is_empty ())
&& ((!flag_tree_loop_vectorize && !loop->force_vectorize)
|| loop->dont_vectorize))
goto cleanup;
@@ -3049,39 +3665,18 @@ tree_if_conversion (class loop *loop, vec<gimple *> *preds)
specified -ftree-loop-if-convert or unless versioning is required.
Either version this loop, or if the pattern is right for outer-loop
vectorization, version the outer loop. In the latter case we will
- still if-convert the original inner loop. */
- if (need_to_predicate
- || any_complicated_phi
- || flag_tree_loop_if_convert != 1)
- {
- class loop *vloop
- = (versionable_outer_loop_p (loop_outer (loop))
- ? loop_outer (loop) : loop);
- class loop *nloop = version_loop_for_if_conversion (vloop, preds);
- if (nloop == NULL)
- goto cleanup;
- if (vloop != loop)
- {
- /* If versionable_outer_loop_p decided to version the
- outer loop, version also the inner loop of the non-vectorized
- loop copy. So we transform:
- loop1
- loop2
- into:
- if (LOOP_VECTORIZED (1, 3))
- {
- loop1
- loop2
- }
- else
- loop3 (copy of loop1)
- if (LOOP_VECTORIZED (4, 5))
- loop4 (copy of loop2)
- else
- loop5 (copy of loop4) */
- gcc_assert (nloop->inner && nloop->inner->next == NULL);
- rloop = nloop->inner;
- }
+ still if-convert the original inner loop. Only do this though if we are
+ certain we will run the vectorizer. */
+ if (flag_tree_loop_if_convert != 1
+ && !version_loop (loop, &rloop, preds, breaks.is_empty ()))
+ goto cleanup;
+
+ if (!breaks.is_empty ())
+ {
+ todo |= simplify_loop_control_flow (loop, natural_loop_exit, breaks);
+ breaks.block_remove (0, breaks.length ());
+ todo |= TODO_cleanup_cfg;
+ goto cleanup;
}
/* Now all statements are if-convertible. Combine all the basic
@@ -57,6 +57,7 @@ along with GCC; see the file COPYING3. If not see
#include "tree-ssa-loop.h"
#include "tree-into-ssa.h"
#include "cfgloop.h"
+#include "cfganal.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.h"
#include "tree-inline.h"
@@ -1340,6 +1341,14 @@ tree_unroll_loops_completely_1 (bool may_increase_size, bool unroll_outer,
class loop *inner;
enum unroll_level ul;
unsigned num = number_of_loops (cfun);
+ basic_block *bbs = XCNEWVEC (basic_block, loop->num_nodes);
+ unsigned int nbbs = dfs_enumerate_from (loop->header, 0, bb_in_loop_p, bbs,
+ loop->num_nodes, loop);
+ auto_vec<edge> breaks;
+ edge loop_exit;
+
+ if (can_remove_breaks (loop, nbbs, bbs, &loop_exit, &breaks))
+ return false;
/* Process inner loops first. Don't walk loops added by the recursive
calls because SSA form is not up-to-date. They can be handled in the
@@ -854,8 +854,26 @@ vect_set_loop_condition_unmasked (class loop *loop, tree niters,
limit = force_gimple_operand_gsi (&loop_cond_gsi, limit, true, NULL_TREE,
true, GSI_SAME_STMT);
- cond_stmt = gimple_build_cond (code, indx_after_incr, limit, NULL_TREE,
- NULL_TREE);
+ if (loop->early_break_cond)
+ {
+ bool exit_on_true = exit_edge->flags & EDGE_TRUE_VALUE;
+ /* EARLY_BREAK_COND is 0 if we can break. */
+ tree early_break
+ = fold_build2 (exit_on_true ? EQ_EXPR : NE_EXPR, boolean_type_node,
+ loop->early_break_cond,
+ build_zero_cst (TREE_TYPE (loop->early_break_cond)));
+ tree cond = build2 (code, boolean_type_node, indx_after_incr, limit);
+ cond = fold_build2 (exit_on_true ? TRUTH_OR_EXPR : TRUTH_AND_EXPR,
+ boolean_type_node, cond, early_break);
+ cond = force_gimple_operand_gsi (&loop_cond_gsi, cond, true, NULL_TREE,
+ true, GSI_SAME_STMT);
+ cond_stmt = gimple_build_cond (NE_EXPR, cond,
+ build_zero_cst (boolean_type_node),
+ NULL_TREE, NULL_TREE);
+ }
+ else
+ cond_stmt = gimple_build_cond (code, indx_after_incr, limit, NULL_TREE,
+ NULL_TREE);
gsi_insert_before (&loop_cond_gsi, cond_stmt, GSI_SAME_STMT);
@@ -1043,9 +1061,10 @@ slpeel_tree_duplicate_loop_to_edge_cfg (class loop *loop,
bbs[0] = preheader;
new_bbs = XNEWVEC (basic_block, scalar_loop->num_nodes + 1);
- exit = single_exit (scalar_loop);
+ edge scalar_exit = single_exit (scalar_loop);
+
copy_bbs (bbs, scalar_loop->num_nodes + 1, new_bbs,
- &exit, 1, &new_exit, NULL,
+ &scalar_exit, 1, &new_exit, NULL,
at_exit ? loop->latch : e->src, true);
exit = single_exit (loop);
basic_block new_preheader = new_bbs[0];
@@ -1059,8 +1078,7 @@ slpeel_tree_duplicate_loop_to_edge_cfg (class loop *loop,
but LOOP will not. slpeel_update_phi_nodes_for_guard{1,2} expects
the LOOP SSA_NAMEs (on the exit edge and edge from latch to
header) to have current_def set, so copy them over. */
- slpeel_duplicate_current_defs_from_edges (single_exit (scalar_loop),
- exit);
+ slpeel_duplicate_current_defs_from_edges (scalar_exit, exit);
slpeel_duplicate_current_defs_from_edges (EDGE_SUCC (scalar_loop->latch,
0),
EDGE_SUCC (loop->latch, 0));
@@ -2133,7 +2151,8 @@ slpeel_update_phi_nodes_for_loops (loop_vec_info loop_vinfo,
for correct vectorization of live stmts. */
if (loop == first)
{
- basic_block orig_exit = single_exit (second)->dest;
+
+ basic_block orig_exit = find_natural_loop_exit (second)->dest;
for (gsi_orig = gsi_start_phis (orig_exit);
!gsi_end_p (gsi_orig); gsi_next (&gsi_orig))
{
@@ -769,19 +769,6 @@ vect_get_loop_niters (class loop *loop, tree *assumptions,
return cond;
}
-/* Function bb_in_loop_p
-
- Used as predicate for dfs order traversal of the loop bbs. */
-
-static bool
-bb_in_loop_p (const_basic_block bb, const void *data)
-{
- const class loop *const loop = (const class loop *)data;
- if (flow_bb_inside_loop_p (loop, bb))
- return true;
- return false;
-}
-
/* Create and initialize a new loop_vec_info struct for LOOP_IN, as well as
stmt_vec_info structs for all the stmts in LOOP_IN. */
@@ -2450,7 +2437,8 @@ vect_joust_loop_vinfos (loop_vec_info new_loop_vinfo,
for it. The different analyses will record information in the
loop_vec_info struct. */
opt_loop_vec_info
-vect_analyze_loop (class loop *loop, vec_info_shared *shared)
+vect_analyze_loop (class loop *loop, vec_info_shared *shared,
+ bool loop_with_breaks)
{
auto_vector_modes vector_modes;
@@ -2562,6 +2550,33 @@ vect_analyze_loop (class loop *loop, vec_info_shared *shared)
mode_i += 1;
}
+ if (res && loop_with_breaks)
+ {
+ if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
+ res = opt_result::failure_at (vect_location,
+ "Can not vectorize loop with break"
+ "statements if the number of"
+ " iterations is not constant.\n");
+ else if (!multiple_p (LOOP_VINFO_INT_NITERS (loop_vinfo),
+ LOOP_VINFO_VECT_FACTOR (loop_vinfo)))
+ res = opt_result::failure_at (vect_location,
+ "Can not vectorize loop with break"
+ "statements if the number of"
+ " iterations is not a multiple of"
+ " VF.\n");
+ else if (LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo)
+ || LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo)
+ || LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo))
+ res = opt_result::failure_at (vect_location,
+ "Can not vectorize loop with break"
+ "statements if peeling is"
+ " required.\n");
+ if (res)
+ {
+ gcc_assert (LOOP_VINFO_INT_NITERS (loop_vinfo) > 0);
+ }
+ }
+
if (res)
{
LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;
@@ -8487,6 +8502,31 @@ update_epilogue_loop_vinfo (class loop *epilogue, tree advance)
epilogue_vinfo->shared->save_datarefs ();
}
+edge
+find_natural_loop_exit (class loop *loop)
+{
+ edge natural_exit = single_exit (loop);
+ if (!natural_exit)
+ {
+ /* Look for the natural loop exit, this should be the non-latch successor
+ edge of the latch's predecessor. */
+ edge e;
+ edge_iterator ei;
+ edge latch_pred_e = single_pred_edge (loop->latch);
+ gcc_assert (latch_pred_e);
+
+ FOR_EACH_EDGE (e, ei, latch_pred_e->src->succs)
+ {
+ if (e != latch_pred_e)
+ natural_exit = e;
+ }
+ gcc_assert (natural_exit);
+ }
+
+ return natural_exit;
+}
+
+
/* Function vect_transform_loop.
The analysis phase has determined that the loop is vectorizable.
@@ -8558,7 +8598,7 @@ vect_transform_loop (loop_vec_info loop_vinfo, gimple *loop_vectorized_call)
loop closed PHI nodes on the exit. */
if (LOOP_VINFO_SCALAR_LOOP (loop_vinfo))
{
- e = single_exit (LOOP_VINFO_SCALAR_LOOP (loop_vinfo));
+ e = find_natural_loop_exit (LOOP_VINFO_SCALAR_LOOP (loop_vinfo));
if (! single_pred_p (e->dest))
{
split_loop_exit_edge (e, true);
@@ -1801,6 +1801,7 @@ extern tree vect_create_addr_base_for_vector_ref (stmt_vec_info, gimple_seq *,
/* In tree-vect-loop.c. */
extern widest_int vect_iv_limit_for_full_masking (loop_vec_info loop_vinfo);
+extern edge find_natural_loop_exit (class loop *);
/* Used in tree-vect-loop-manip.c */
extern void determine_peel_for_niter (loop_vec_info);
/* Used in gimple-loop-interchange.c and tree-parloops.c. */
@@ -1808,7 +1809,7 @@ extern bool check_reduction_path (dump_user_location_t, loop_p, gphi *, tree,
enum tree_code);
extern bool needs_fold_left_reduction_p (tree, tree_code);
/* Drive for loop analysis stage. */
-extern opt_loop_vec_info vect_analyze_loop (class loop *, vec_info_shared *);
+extern opt_loop_vec_info vect_analyze_loop (class loop *, vec_info_shared *, bool);
extern tree vect_build_loop_niters (loop_vec_info, bool * = NULL);
extern void vect_gen_vector_loop_niters (loop_vec_info, tree, tree *,
tree *, bool);
@@ -873,6 +873,7 @@ try_vectorize_loop_1 (hash_table<simduid_to_vf> *&simduid_to_vf_htab,
vec_info_shared shared;
auto_purge_vect_location sentinel;
vect_location = find_loop_location (loop);
+ bool loop_with_breaks = false;
if (LOCATION_LOCUS (vect_location.get_location_t ()) != UNKNOWN_LOCATION
&& dump_enabled_p ())
@@ -888,8 +889,14 @@ try_vectorize_loop_1 (hash_table<simduid_to_vf> *&simduid_to_vf_htab,
loop_vinfo = opt_loop_vec_info::success (vinfo);
else
{
+ if (loop_vectorized_call)
+ {
+ tree arg = gimple_call_arg (loop_vectorized_call, 1);
+ loop_with_breaks
+ = !single_exit (get_loop (cfun, tree_to_shwi (arg)));
+ }
/* Try to analyze the loop, retaining an opt_problem if dump_enabled_p. */
- loop_vinfo = vect_analyze_loop (loop, &shared);
+ loop_vinfo = vect_analyze_loop (loop, &shared, loop_with_breaks);
loop->aux = loop_vinfo;
}