[#6/7] ifcombine across noncontiguous blocks (was: Re: [PATCH] fold fold_truth_andor field merging into ifcombine)

Rework ifcombine to support merging conditions from noncontiguous
blocks.  This depends on earlier preparation changes.

The function that attempted to ifcombine a block with its immediate
predecessor, tree_ssa_ifcombine_bb, now loops over dominating blocks
eligible for ifcombine, attempting to combine with them.

The function that actually drives the combination of a pair of blocks,
tree_ssa_ifcombine_bb_1, now takes an additional parameter: the
successor of outer that leads to inner.

The function that recognizes if_then_else patterns is modified to
enable testing without distinguishing between then and else, or to
require nondegenerate conditions, that aren't worth combining with.


for  gcc/ChangeLog

	* tree-ssa-ifcombine.cc (recognize_if_then_else): Support
	relaxed then/else testing; require nondegenerate condition
	otherwise.
	(tree_ssa_ifcombine_bb_1): Add outer_succ_bb parm, use it
	instead of inner_cond_bb.  Adjust callers.
	(tree_ssa_ifcombine_bb): Loop over dominating outer blocks
	eligible for ifcombine.
	(pass_tree_ifcombine::execute): Noted potential need for
	changes to the post-combine logic.
---
 gcc/tree-ssa-ifcombine.cc |  152 ++++++++++++++++++++++++++++++++++++---------
 1 file changed, 123 insertions(+), 29 deletions(-)

On Fri, Oct 25, 2024 at 4:39 PM Alexandre Oliva <oliva@adacore.com> wrote:
>
>
> Rework ifcombine to support merging conditions from noncontiguous
> blocks.  This depends on earlier preparation changes.
>
> The function that attempted to ifcombine a block with its immediate
> predecessor, tree_ssa_ifcombine_bb, now loops over dominating blocks
> eligible for ifcombine, attempting to combine with them.
>
> The function that actually drives the combination of a pair of blocks,
> tree_ssa_ifcombine_bb_1, now takes an additional parameter: the
> successor of outer that leads to inner.
>
> The function that recognizes if_then_else patterns is modified to
> enable testing without distinguishing between then and else, or to
> require nondegenerate conditions, that aren't worth combining with.
>
>
> for  gcc/ChangeLog
>
>         * tree-ssa-ifcombine.cc (recognize_if_then_else): Support
>         relaxed then/else testing; require nondegenerate condition
>         otherwise.
>         (tree_ssa_ifcombine_bb_1): Add outer_succ_bb parm, use it
>         instead of inner_cond_bb.  Adjust callers.
>         (tree_ssa_ifcombine_bb): Loop over dominating outer blocks
>         eligible for ifcombine.
>         (pass_tree_ifcombine::execute): Noted potential need for
>         changes to the post-combine logic.
> ---
>  gcc/tree-ssa-ifcombine.cc |  152 ++++++++++++++++++++++++++++++++++++---------
>  1 file changed, 123 insertions(+), 29 deletions(-)
>
> diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc
> index 71c7c9074e94a..817c95b20252e 100644
> --- a/gcc/tree-ssa-ifcombine.cc
> +++ b/gcc/tree-ssa-ifcombine.cc
> @@ -85,25 +85,34 @@ known_succ_p (basic_block cond_bb)
>     is left to CFG cleanup and DCE.  */
>
>
> -/* Recognize a if-then-else CFG pattern starting to match with the
> -   COND_BB basic-block containing the COND_EXPR.  The recognized
> -   then end else blocks are stored to *THEN_BB and *ELSE_BB.  If
> -   *THEN_BB and/or *ELSE_BB are already set, they are required to
> -   match the then and else basic-blocks to make the pattern match.
> -   Returns true if the pattern matched, false otherwise.  */
> +/* Recognize a if-then-else CFG pattern starting to match with the COND_BB
> +   basic-block containing the COND_EXPR.  If !SUCCS_ANY, the condition must not
> +   resolve to a constant for a match.  Returns true if the pattern matched,
> +   false otherwise.  In case of a !SUCCS_ANY match, the recognized then end
> +   else blocks are stored to *THEN_BB and *ELSE_BB.  If *THEN_BB and/or
> +   *ELSE_BB are already set, they are required to match the then and else
> +   basic-blocks to make the pattern match.  If SUCCS_ANY, *THEN_BB and *ELSE_BB
> +   will not be filled in, and they will be found to match even if reversed.  */
>
>  static bool
>  recognize_if_then_else (basic_block cond_bb,
> -                       basic_block *then_bb, basic_block *else_bb)
> +                       basic_block *then_bb, basic_block *else_bb,
> +                       bool succs_any = false)
>  {
>    edge t, e;
>
> -  if (EDGE_COUNT (cond_bb->succs) != 2)
> +  if (EDGE_COUNT (cond_bb->succs) != 2
> +      || (!succs_any && known_succ_p (cond_bb)))
>      return false;
>
>    /* Find the then/else edges.  */
>    t = EDGE_SUCC (cond_bb, 0);
>    e = EDGE_SUCC (cond_bb, 1);
> +
> +  if (succs_any)
> +    return ((t->dest == *then_bb && e->dest == *else_bb)
> +           || (t->dest == *else_bb && e->dest == *then_bb));
> +
>    if (!(t->flags & EDGE_TRUE_VALUE))
>      std::swap (t, e);
>    if (!(t->flags & EDGE_TRUE_VALUE)
> @@ -886,19 +895,21 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
>  /* Helper function for tree_ssa_ifcombine_bb.  Recognize a CFG pattern and
>     dispatch to the appropriate if-conversion helper for a particular
>     set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
> -   PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB.  */
> +   PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB.
> +   OUTER_SUCC_BB is the successor of OUTER_COND_BB on the path towards
> +   INNER_COND_BB.  */
>
>  static bool
>  tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
>                          basic_block then_bb, basic_block else_bb,
> -                        basic_block phi_pred_bb)
> +                        basic_block phi_pred_bb, basic_block outer_succ_bb)
>  {
>    /* The && form is characterized by a common else_bb with
>       the two edges leading to it mergable.  The latter is
>       guaranteed by matching PHI arguments in the else_bb and
>       the inner cond_bb having no side-effects.  */
>    if (phi_pred_bb != else_bb
> -      && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
> +      && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &else_bb)
>        && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
>      {
>        /* We have
> @@ -915,7 +926,7 @@ tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
>
>    /* And a version where the outer condition is negated.  */
>    if (phi_pred_bb != else_bb
> -      && recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb)
> +      && recognize_if_then_else (outer_cond_bb, &else_bb, &outer_succ_bb)
>        && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
>      {
>        /* We have
> @@ -935,7 +946,7 @@ tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
>       by matching PHI arguments in the then_bb and the inner cond_bb
>       having no side-effects.  */
>    if (phi_pred_bb != then_bb
> -      && recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
> +      && recognize_if_then_else (outer_cond_bb, &then_bb, &outer_succ_bb)
>        && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
>      {
>        /* We have
> @@ -951,7 +962,7 @@ tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
>
>    /* And a version where the outer condition is negated.  */
>    if (phi_pred_bb != then_bb
> -      && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb)
> +      && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &then_bb)
>        && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
>      {
>        /* We have
> @@ -975,10 +986,11 @@ tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
>  static bool
>  tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
>  {
> +  bool ret = false;
>    basic_block then_bb = NULL, else_bb = NULL;
>
>    if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
> -    return false;
> +    return ret;
>
>    /* Recognize && and || of two conditions with a common
>       then/else block which entry edges we can merge.  That is:
> @@ -987,17 +999,62 @@ tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
>       and
>         if (a && b)
>          ;
> -     This requires a single predecessor of the inner cond_bb.  */
> -  if (single_pred_p (inner_cond_bb)
> -      && bb_no_side_effects_p (inner_cond_bb))
> +     This requires a single predecessor of the inner cond_bb.
> +
> +     Look for an OUTER_COND_BBs to combine with INNER_COND_BB.  They need not
> +     be contiguous, as long as inner and intervening blocks have no side
> +     effects, and are either single-entry-single-exit or conditionals choosing
> +     between the same EXIT_BB with the same PHI args, and the path leading to
> +     INNER_COND_BB.  ??? We could potentially handle multi-block
> +     single-entry-single-exit regions, but the loop below only deals with
> +     single-entry-single-exit individual intervening blocks.  Larger regions
> +     without side effects are presumably rare, so it's probably not worth the
> +     effort.  */
> +  for (basic_block bb = inner_cond_bb, outer_cond_bb, exit_bb = NULL;
> +       single_pred_p (bb) && bb_no_side_effects_p (bb);
> +       bb = outer_cond_bb)
>      {
> -      basic_block outer_cond_bb = single_pred (inner_cond_bb);
> +      bool changed = false;
>
> -      if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
> -                                  then_bb, else_bb, inner_cond_bb))
> -       return true;
> +      outer_cond_bb = single_pred (bb);
>
> -      if (forwarder_block_to (else_bb, then_bb))
> +      /* Skip blocks without conditions.  */
> +      if (single_succ_p (outer_cond_bb))
> +       continue;
> +
> +      /* When considering noncontiguous conditions, make sure that all
> +        non-final conditions lead to the same successor of the final
> +        condition, when not taking the path to inner_bb, so that we can
> +        combine C into A, both in A && (B && C), and in A || (B || C), but
> +        neither in A && (B || C), nor A || (B && C).  Say, if C goes to
> +        THEN_BB or ELSE_BB, then B must go to either of these, say X, besides
> +        C (whether C is then or else), and A must go to X and B (whether then
> +        or else).
> +
> +        We test for this, while allowing intervening nonconditional blocks, by
> +        first taking note of which of the successors of the inner conditional
> +        block is the exit path taken by the first considered outer conditional
> +        block.
> +
> +        Having identified and saved the exit block in EXIT_BB at the end of
> +        the loop, here we test that subsequent conditional blocks under
> +        consideration also use the exit block as a successor, besides the
> +        block that leads to inner_cond_bb, and that the edges to exit share
> +        the same phi values.  */
> +      if (exit_bb
> +         && !recognize_if_then_else (outer_cond_bb, &bb, &exit_bb, true))
> +       break;
> +
> +      /* After checking dests and phi args, we can also skip blocks whose
> +        conditions have been optimized down to a constant, without trying to
> +        combine them, but we must not skip the computation of EXIT_BB and the
> +        checking of same phi args.  */
> +      if (known_succ_p (outer_cond_bb))
> +       changed = false;
> +      else if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
> +                                       then_bb, else_bb, inner_cond_bb, bb))
> +       changed = true;
> +      else if (forwarder_block_to (else_bb, then_bb))
>         {
>           /* Other possibilities for the && form, if else_bb is
>              empty forwarder block to then_bb.  Compared to the above simpler
> @@ -1006,8 +1063,8 @@ tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
>              For same_phi_args_p we look at equality of arguments between
>              edge from outer_cond_bb and the forwarder block.  */
>           if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
> -                                      then_bb, else_bb))
> -           return true;
> +                                      then_bb, else_bb, bb))
> +           changed = true;
>         }
>        else if (forwarder_block_to (then_bb, else_bb))
>         {
> @@ -1018,12 +1075,46 @@ tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
>              For same_phi_args_p we look at equality of arguments between
>              edge from outer_cond_bb and the forwarder block.  */
>           if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
> -                                      then_bb, then_bb))
> -           return true;
> +                                      then_bb, then_bb, bb))
> +           changed = true;
>         }
> +
> +      if (changed)
> +       ret = changed;
> +
> +      /* If the inner condition is gone, there's no point in attempting to
> +        combine it any further.  */
> +      if (changed && known_succ_p (inner_cond_bb))
> +       break;
> +
> +      /* Record the exit path taken by the outer condition.  */
> +      if (!exit_bb)
> +       {
> +         if (recognize_if_then_else (outer_cond_bb, &then_bb, &bb, true))
> +           exit_bb = then_bb;
> +         else if (recognize_if_then_else (outer_cond_bb, &bb, &else_bb, true))
> +           exit_bb = else_bb;
> +         else
> +           break;
> +       }
> +
> +      /* Before trying an earlier block, make sure INNER_COND_BB and the
> +        current OUTER_COND_BB share the same PHI args at EXIT_BB.  We don't
> +        need to check if the latest attempt at combining succeeded, because
> +        that means we'll have already checked.  But we can't only check outer
> +        and inner, we have to check that all intervening blocks also get to
> +        exit with the same result, otherwise the transformation may change the
> +        final result.  Consider (a ? 0 : b ? 1 : c ? 0 : -1).  If we combine
> +        (a | c), yielding ((a | c) ? 0 : b ? 1 : [0 ? 0 :] -1), we'd get 0
> +        rather than 1 when (!a&&b).  And if we were to replace inner instead
> +        of outer, we'd get ([1 ? 0 :] b ? 1 : (a | c) ? 0 : -1), which would
> +        yield 1 rather than 0 when (a).  */
> +      if (!changed
> +         && !same_phi_args_p (outer_cond_bb, inner_cond_bb, exit_bb))
> +       break;
>      }
>
> -  return false;
> +  return ret;
>  }
>
>  /* Main entry for the tree if-conversion pass.  */
> @@ -1082,7 +1173,10 @@ pass_tree_ifcombine::execute (function *fun)
>         if (tree_ssa_ifcombine_bb (bb))
>           {
>             /* Clear range info from all stmts in BB which is now executed
> -              conditional on a always true/false condition.  */
> +              conditional on a always true/false condition.  ??? When we
> +              combine noncontiguous blocks, do we need to adjust the
> +              intervening blocks as well?  If we leave outer conditions
> +              nonconstant, do we still need to modify them?  */

I think since you make the outer condition the short-circuiting one what's in
the inner block isn't executed when it wasn't before the transform?  So in
fact you shouldn't need to process stmts in BB even?  Only when the
outer condition is now unconditional.

But I think you need to reset flow sensitive info on all statements you move
as part of the inner condition computation in the earlier patch.

I think with the restructuring this code resetting flow sensitive info should
move to where we make the outer condition always true and it gated BB.

>             reset_flow_sensitive_info_in_bb (bb);
>             for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
>                  gsi_next (&gsi))
>
> --
> Alexandre Oliva, happy hacker            https://FSFLA.org/blogs/lxo/
>    Free Software Activist                   GNU Toolchain Engineer
> More tolerance and less prejudice are key for inclusion and diversity
> Excluding neuro-others for not behaving ""normal"" is *not* inclusive

On Oct 30, 2024, Richard Biener <richard.guenther@gmail.com> wrote:

> I think since you make the outer condition the short-circuiting one what's in
> the inner block isn't executed when it wasn't before the transform?  So in
> fact you shouldn't need to process stmts in BB even?  Only when the
> outer condition is now unconditional.

Aah, I think I get what the goal is now.

I suppose we could get away without resetting flow info, but even if
guarding conditions become stricter, resetting flow info makes sense so
that they're recomputed to reflect the guard changes.

But we need not worry about introducing undefined behavior in inner
blocks as long as we're making the outer condition that guards them
stricter.  There's a twist there when we get a compound cond and split
it across neighbor blocks, as in patch #7/7, because then we may be
making the outer condition laxer.

I'm testing an incremental patch that adds simple bounds to the amount
of stmt moving, and flow info resetting and UB avoiding for moved stmts,
and arranges to reset flow info and avoid UB in inner blocks when the
outer cond is relaxed.

On Sat, Nov 2, 2024 at 8:39 AM Alexandre Oliva <oliva@adacore.com> wrote:
>
> On Oct 30, 2024, Richard Biener <richard.guenther@gmail.com> wrote:
>
> > I think since you make the outer condition the short-circuiting one what's in
> > the inner block isn't executed when it wasn't before the transform?  So in
> > fact you shouldn't need to process stmts in BB even?  Only when the
> > outer condition is now unconditional.
>
> Aah, I think I get what the goal is now.
>
> I suppose we could get away without resetting flow info, but even if
> guarding conditions become stricter, resetting flow info makes sense so
> that they're recomputed to reflect the guard changes.

Note they are "recomputed" whether or not we reset them here when
the next VRP pass comes around.  We need to reset the info for correctness
reasons so passes between now and the next re-compute doesn't end up
with invalid data.

> But we need not worry about introducing undefined behavior in inner
> blocks as long as we're making the outer condition that guards them
> stricter.  There's a twist there when we get a compound cond and split
> it across neighbor blocks, as in patch #7/7, because then we may be
> making the outer condition laxer.
>
> I'm testing an incremental patch that adds simple bounds to the amount
> of stmt moving, and flow info resetting and UB avoiding for moved stmts,
> and arranges to reset flow info and avoid UB in inner blocks when the
> outer cond is relaxed.

Thanks,
Richard.

>
> --
> Alexandre Oliva, happy hacker            https://FSFLA.org/blogs/lxo/
>    Free Software Activist                   GNU Toolchain Engineer
> More tolerance and less prejudice are key for inclusion and diversity
> Excluding neuro-others for not behaving ""normal"" is *not* inclusive

On Nov  3, 2024, Richard Biener <richard.guenther@gmail.com> wrote:

> On Sat, Nov 2, 2024 at 8:39 AM Alexandre Oliva <oliva@adacore.com> wrote:

>> I suppose we could get away without resetting flow info, but even if
>> guarding conditions become stricter, resetting flow info makes sense so
>> that they're recomputed to reflect the guard changes.

> Note they are "recomputed" whether or not we reset them here when
> the next VRP pass comes around.

Aah, I was hoping for some dynamic incremental recomputation upon
query.  Wishful thinking much? :-)


I see you've reviewed and approved #8 (thanks), where I implemented the
changed prompted by your feedback to this (#6), so now this (#6) is the
only patch in the reduced series that's still pending approval (or
further changes?)