On Fri, Nov 13, 2026 at 6:44 AM <[email protected]> wrote:
>
> 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.
First, this seems like it should be part of ivcanon pass rather than
ifcombine. Is there a reason why you can't move it to there?
Or maybe even loopinit ?
I can't tell if it reuses anything from ifcombine at all even so I
question why it is even part of this pass in the first place. Why not
its own or part of a loop one?
Thanks,
Andrea
>
> 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
Watch out for missing newline at EOF.
> 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
>
