From: Richard Ball <[email protected]>
The loop
void add(int N, int *__restrict a, int *__restrict b, int *__restrict c) {
for (int i = 0; i < N; i++) {
c[i] = a[i] + b[i];
if (i > 1000) {
break;
}
}
}
is an example of a loop that we have started vectorizing using early break
vectorization. However the given loop is not actually an early break loop as
the condition on the exit introduces a MAX bound on N.
This patch teaches ifcombine to identify such cases and rewrite the latch
condition from i < N to i < MIN (N, C) where C is a constant.
gcc/ChangeLog:
PR tree-optimization/113134
* tree-ssa-ifcombine.cc
(struct ifcombine_exit_info): New struct.
(ifcombine_exit_niter): New function.
(ifcombine_reaches_header_via_latch_p): Likewise
(ifcombine_removable_exit_p): Likewise.
(ifcombine_collect_exit_bounds): Likewise.
(ifcombine_rewrite_loop_exits): Likewise.
(ifcombine_find_latch_exit): Likewise.
(ifcombine_aggregate_safe_p): Likewise.
(ifcombine_loop_exits): Likewise.
(ifcombine_loop_exits_in_function): Likewise.
(ifcombine_loop_exit_bounds): Likewise.
(pass_tree_ifcombine::execute): Add call for new functions.
gcc/testsuite/ChangeLog:
PR tree-optimization/113134
* gcc.dg/ifcombine-pr113134.c: New test.
---
gcc/testsuite/gcc.dg/ifcombine-pr113134.c | 13 +
gcc/tree-ssa-ifcombine.cc | 300 +++++++++++++++++++++-
2 files changed, 312 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/gcc.dg/ifcombine-pr113134.c
diff --git a/gcc/testsuite/gcc.dg/ifcombine-pr113134.c
b/gcc/testsuite/gcc.dg/ifcombine-pr113134.c
new file mode 100644
index 00000000000..7a8d7c1e98b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ifcombine-pr113134.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-ifcombine-details -save-temps" } */
+
+void add(int N, int *__restrict a, int *__restrict b, int *__restrict c) {
+ for (int i = 0; i < N; i++) {
+ c[i] = a[i] + b[i];
+ if (i > 1000) {
+ break;
+ }
+ }
+}
+
+/* { dg-final { scan-tree-dump "ifcombine: aggregated loop" "ifcombine" } } */
\ No newline at end of file
diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc
index d5e3d91e9b5..ad190427947 100644
--- a/gcc/tree-ssa-ifcombine.cc
+++ b/gcc/tree-ssa-ifcombine.cc
@@ -45,6 +45,11 @@ along with GCC; see the file COPYING3. If not see
#include "asan.h"
#include "bitmap.h"
#include "cfgloop.h"
+#include "tree-ssa-loop.h"
+#include "tree-ssa-loop-niter.h"
+#include "tree-ssa-loop-ivopts.h"
+#include "tree-scalar-evolution.h"
+#include "tree-chrec.h"
#ifndef LOGICAL_OP_NON_SHORT_CIRCUIT
#define LOGICAL_OP_NON_SHORT_CIRCUIT \
@@ -523,6 +528,295 @@ ifcombine_rewrite_to_defined_overflow
(gimple_stmt_iterator gsi)
rewrite_to_defined_unconditional (&gsi);
}
+/* Information retained for each exit incorporated in the aggregate. */
+struct ifcombine_exit_info
+{
+ edge exit;
+ tree niter;
+};
+
+/* Return the exit iteration count, accounting for an immediate exit. */
+static tree
+ifcombine_exit_niter (class loop *loop, edge exit)
+{
+ tree_niter_desc desc;
+
+ if (!number_of_iterations_exit (loop, exit, &desc, false))
+ return NULL_TREE;
+
+ tree niter = desc.niter;
+ if (!niter || chrec_contains_undetermined (niter))
+ return NULL_TREE;
+
+ if (integer_nonzerop (desc.may_be_zero))
+ return build_zero_cst (TREE_TYPE (niter));
+
+ if (!integer_zerop (desc.may_be_zero))
+ niter = fold_build3 (COND_EXPR, TREE_TYPE (niter),
+ desc.may_be_zero,
+ build_zero_cst (TREE_TYPE (niter)), niter);
+
+ return niter;
+}
+
+/* Require the non-exiting edge of E to reach the controlling header
+ via the loop latch. */
+static bool
+ifcombine_reaches_header_via_latch_p (class loop *loop,
+ edge e, edge controlling_exit)
+{
+ if (EDGE_COUNT (e->src->succs) != 2)
+ return false;
+
+ edge nonexit = EDGE_SUCC (e->src, 0);
+ if (nonexit == e)
+ nonexit = EDGE_SUCC (e->src, 1);
+
+ basic_block bb = nonexit->dest;
+ return (bb == loop->latch
+ && single_pred_p (bb)
+ && single_pred_edge (bb) == nonexit
+ && single_succ_p (bb)
+ && single_succ (bb) == controlling_exit->src
+ && controlling_exit->src == loop->header);
+}
+
+/* Check a candidate early exit's CFG shape and scalar exit PHIs.
+ Virtual PHIs are not compared; */
+static bool
+ifcombine_removable_exit_p (class loop *loop, edge e,
+ edge controlling_exit)
+{
+ if (e == controlling_exit
+ || !just_once_each_iteration_p (loop, e->src)
+ || !dominated_by_p (CDI_DOMINATORS,
+ e->src, controlling_exit->src)
+ || e->dest != controlling_exit->dest
+ || EDGE_COUNT (e->src->succs) != 2
+ || !ifcombine_reaches_header_via_latch_p (loop, e,
+ controlling_exit))
+ return false;
+
+ for (gphi_iterator gpi = gsi_start_phis (e->dest);
+ !gsi_end_p (gpi); gsi_next (&gpi))
+ {
+ gphi *phi = gpi.phi ();
+ if (virtual_operand_p (gimple_phi_result (phi)))
+ continue;
+
+ tree early_arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ tree control_arg = PHI_ARG_DEF_FROM_EDGE (phi, controlling_exit);
+ if (!operand_equal_for_phi_arg_p (early_arg, control_arg))
+ return false;
+ }
+
+ return true;
+}
+
+/* Find eligible exits and form the minimum controlling bound. */
+static bool
+ifcombine_collect_exit_bounds (class loop *loop,
+ edge controlling_exit,
+ tree *aggregate_niter,
+ auto_vec<ifcombine_exit_info> &candidates)
+{
+ tree controlling_niter = ifcombine_exit_niter (loop, controlling_exit);
+ if (!controlling_niter)
+ return false;
+
+ tree niter = controlling_niter;
+ auto_vec<edge> exits = get_loop_exit_edges (loop);
+
+ for (edge e : exits)
+ {
+ if (e == controlling_exit
+ || !just_once_each_iteration_p (loop, e->src)
+ || !dominated_by_p (CDI_DOMINATORS,
+ e->src, controlling_exit->src))
+ continue;
+
+ tree exit_niter = ifcombine_exit_niter (loop, e);
+ if (!exit_niter
+ || TREE_TYPE (exit_niter) != TREE_TYPE (controlling_niter)
+ || !ifcombine_removable_exit_p (loop, e, controlling_exit))
+ continue;
+
+ tree type = TREE_TYPE (controlling_niter);
+ if (!TYPE_UNSIGNED (type)
+ || TREE_CODE (exit_niter) != INTEGER_CST)
+ continue;
+
+ wide_int value = wi::to_wide (exit_niter);
+ if (wi::lts_p (value, 0)
+ || wi::geu_p (wi::to_wide (exit_niter),
+ wi::to_wide (TYPE_MAX_VALUE (type))))
+ continue;
+
+ tree adjusted_niter = fold_convert (type, exit_niter);
+ adjusted_niter = int_const_binop (PLUS_EXPR, adjusted_niter,
+ build_int_cst (type, 1));
+
+ ifcombine_exit_info info = { e, exit_niter };
+ candidates.safe_push (info);
+ niter = fold_build2 (MIN_EXPR, type, niter, adjusted_niter);
+ }
+
+ if (candidates.is_empty ())
+ return false;
+
+ *aggregate_niter = niter;
+ return true;
+}
+
+/* Replace the controlling exit with a canonical IV test, then
+ make the selected early exit conditions always take the non-exit
+ path. */
+static bool
+ifcombine_rewrite_loop_exits (class loop *loop, edge controlling_exit,
+ tree aggregate_niter,
+ auto_vec<ifcombine_exit_info> &candidates)
+{
+ create_canonical_iv (loop, controlling_exit, aggregate_niter);
+
+ for (unsigned i = 0; i < candidates.length (); ++i)
+ {
+ edge e = candidates[i].exit;
+ gcond *cond = as_a<gcond *> (*gsi_last_nondebug_bb (e->src));
+
+ if (e->flags & EDGE_TRUE_VALUE)
+ gimple_cond_make_false (cond);
+ else
+ gimple_cond_make_true (cond);
+
+ update_stmt (cond);
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "ifcombine: aggregated loop %d exits\n",
+ loop->num);
+
+ return true;
+}
+
+/* Locate a conditional loop-header exit. */
+static edge
+ifcombine_find_latch_exit (class loop *loop)
+{
+ basic_block header = loop->header;
+ if (EDGE_COUNT (header->succs) != 2)
+ return NULL;
+
+ gimple_stmt_iterator gsi = gsi_last_nondebug_bb (header);
+ if (gsi_end_p (gsi)
+ || gimple_code (gsi_stmt (gsi)) != GIMPLE_COND)
+ return NULL;
+
+ edge e0 = EDGE_SUCC (header, 0);
+ edge e1 = EDGE_SUCC (header, 1);
+
+ if (loop_exit_edge_p (loop, e0)
+ && flow_bb_inside_loop_p (loop, e1->dest))
+ return e0;
+ if (loop_exit_edge_p (loop, e1)
+ && flow_bb_inside_loop_p (loop, e0->dest))
+ return e1;
+
+ return NULL;
+}
+
+/* Check aggregate structural constraints. */
+static bool
+ifcombine_aggregate_safe_p (class loop *loop, edge controlling_exit,
+ tree aggregate_niter,
+ auto_vec<ifcombine_exit_info> &candidates)
+{
+ if (!aggregate_niter
+ || chrec_contains_undetermined (aggregate_niter)
+ || candidates.is_empty ()
+ || !loop_preheader_edge (loop)
+ || controlling_exit->src != loop->header
+ || !TYPE_UNSIGNED (TREE_TYPE (aggregate_niter)))
+ return false;
+
+ for (unsigned i = 0; i < candidates.length (); ++i)
+ {
+ edge e = candidates[i].exit;
+ if (e == controlling_exit
+ || e->dest != controlling_exit->dest
+ || !ifcombine_reaches_header_via_latch_p (loop, e,
+ controlling_exit))
+ return false;
+ }
+
+ return true;
+}
+
+/* Analyze and, if eligible, transform one loop. */
+static bool
+ifcombine_loop_exits (class loop *loop)
+{
+ edge controlling_exit = ifcombine_find_latch_exit (loop);
+ if (!controlling_exit)
+ return false;
+
+ tree aggregate_niter = NULL_TREE;
+ auto_vec<ifcombine_exit_info> candidates;
+
+ if (!ifcombine_collect_exit_bounds (loop, controlling_exit,
+ &aggregate_niter, candidates)
+ || !ifcombine_aggregate_safe_p (loop, controlling_exit,
+ aggregate_niter, candidates))
+ return false;
+
+ return ifcombine_rewrite_loop_exits (loop, controlling_exit,
+ aggregate_niter, candidates);
+}
+
+/* Process loops from the innermost out, invalidating SCEV after
+ each successful rewrite. */
+static bool
+ifcombine_loop_exits_in_function (function *fun)
+{
+ bool changed = false;
+ for (auto loop : loops_list (fun, LI_FROM_INNERMOST))
+ {
+ if (loop->num == 0)
+ continue;
+
+ if (ifcombine_loop_exits (loop))
+ {
+ changed = true;
+ scev_reset ();
+ }
+ }
+
+ return changed;
+}
+
+/* Set up SCEV infrastructure if necessary, process loops, and
+ restore the analysis state. */
+static bool
+ifcombine_loop_exit_bounds (function *fun)
+{
+ bool in_loop_pipeline = scev_initialized_p ();
+ if (!in_loop_pipeline)
+ {
+ loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
+ scev_initialize ();
+ }
+
+ bool changed = false;
+ if (number_of_loops (fun) > 1)
+ changed = ifcombine_loop_exits_in_function (fun);
+
+ if (!in_loop_pipeline)
+ {
+ scev_finalize ();
+ loop_optimizer_finalize ();
+ }
+
+ return changed;
+}
/* Replace the conditions in INNER_COND and OUTER_COND with COND and COND2.
COND and COND2 are computed for insertion at INNER_COND, with OUTER_COND
@@ -1556,7 +1850,11 @@ pass_tree_ifcombine::execute (function *fun)
free (bbs);
- return cfg_changed ? TODO_cleanup_cfg : 0;
+ /* Combine loop exits with compatible iteration bounds. */
+ bool loop_changed = ifcombine_loop_exit_bounds (fun);
+
+ return (cfg_changed || loop_changed)
+ ? TODO_cleanup_cfg : 0;
}
} // anon namespace
--
2.34.1
