Re: [PATCH v2] ifcvt: Handle multiple rewired regs and refactor noce_convert_multiple_sets

[Manolis Tsamis <manolis.tsamis@vrull.eu>]

I have bootstrapped and checked for no testsuite regressions on x86 and aarch64.

Thanks,
Manolis

On Tue, Nov 21, 2023 at 8:00 PM Manolis Tsamis <manolis.tsamis@vrull.eu> wrote:
>
> The existing implementation of need_cmov_or_rewire and
> noce_convert_multiple_sets_1 assumes that sets are either REG or SUBREG.
> This commit enchances them so they can handle/rewire arbitrary set statements.
>
> To do that a new helper struct noce_multiple_sets_info is introduced which is
> used by noce_convert_multiple_sets and its helper functions. This results in
> cleaner function signatures, improved efficientcy (a number of vecs and hash
> set/map are replaced with a single vec of struct) and simplicity.
>
> gcc/ChangeLog:
>
>         * ifcvt.cc (need_cmov_or_rewire): Renamed init_noce_multiple_sets_info.
>         (init_noce_multiple_sets_info): Initialize noce_multiple_sets_info.
>         (noce_convert_multiple_sets_1): Use noce_multiple_sets_info and handle
>         rewiring of multiple registers.
>         (noce_convert_multiple_sets): Updated to use noce_multiple_sets_info.
>         * ifcvt.h (struct noce_multiple_sets_info): Introduce new struct
>         noce_multiple_sets_info to store info for noce_convert_multiple_sets.
>
> Signed-off-by: Manolis Tsamis <manolis.tsamis@vrull.eu>
> ---
>
> Changes in v2:
>         - Made standalone patch.
>         - Better comments, some more checks.
>
>  gcc/ifcvt.cc | 252 +++++++++++++++++++++++----------------------------
>  gcc/ifcvt.h  |  16 ++++
>  2 files changed, 129 insertions(+), 139 deletions(-)
>
> diff --git a/gcc/ifcvt.cc b/gcc/ifcvt.cc
> index a0af553b9ff..9486d54de34 100644
> --- a/gcc/ifcvt.cc
> +++ b/gcc/ifcvt.cc
> @@ -98,14 +98,10 @@ static bool dead_or_predicable (basic_block, basic_block, basic_block,
>                                 edge, bool);
>  static void noce_emit_move_insn (rtx, rtx);
>  static rtx_insn *block_has_only_trap (basic_block);
> -static void need_cmov_or_rewire (basic_block, hash_set<rtx_insn *> *,
> -                                hash_map<rtx_insn *, int> *);
> +static void init_noce_multiple_sets_info (basic_block,
> +  auto_delete_vec<noce_multiple_sets_info> &);
>  static bool noce_convert_multiple_sets_1 (struct noce_if_info *,
> -                                         hash_set<rtx_insn *> *,
> -                                         hash_map<rtx_insn *, int> *,
> -                                         auto_vec<rtx> *,
> -                                         auto_vec<rtx> *,
> -                                         auto_vec<rtx_insn *> *, int *);
> +  auto_delete_vec<noce_multiple_sets_info> &, int *);
>
>  /* Count the number of non-jump active insns in BB.  */
>
> @@ -3270,24 +3266,13 @@ noce_convert_multiple_sets (struct noce_if_info *if_info)
>    rtx x = XEXP (cond, 0);
>    rtx y = XEXP (cond, 1);
>
> -  /* The true targets for a conditional move.  */
> -  auto_vec<rtx> targets;
> -  /* The temporaries introduced to allow us to not consider register
> -     overlap.  */
> -  auto_vec<rtx> temporaries;
> -  /* The insns we've emitted.  */
> -  auto_vec<rtx_insn *> unmodified_insns;
> -
> -  hash_set<rtx_insn *> need_no_cmov;
> -  hash_map<rtx_insn *, int> rewired_src;
> -
> -  need_cmov_or_rewire (then_bb, &need_no_cmov, &rewired_src);
> +  auto_delete_vec<noce_multiple_sets_info> insn_info;
> +  init_noce_multiple_sets_info (then_bb, insn_info);
>
>    int last_needs_comparison = -1;
>
>    bool ok = noce_convert_multiple_sets_1
> -    (if_info, &need_no_cmov, &rewired_src, &targets, &temporaries,
> -     &unmodified_insns, &last_needs_comparison);
> +    (if_info, insn_info, &last_needs_comparison);
>    if (!ok)
>        return false;
>
> @@ -3302,8 +3287,7 @@ noce_convert_multiple_sets (struct noce_if_info *if_info)
>        end_sequence ();
>        start_sequence ();
>        ok = noce_convert_multiple_sets_1
> -       (if_info, &need_no_cmov, &rewired_src, &targets, &temporaries,
> -        &unmodified_insns, &last_needs_comparison);
> +       (if_info, insn_info, &last_needs_comparison);
>        /* Actually we should not fail anymore if we reached here,
>          but better still check.  */
>        if (!ok)
> @@ -3312,12 +3296,12 @@ noce_convert_multiple_sets (struct noce_if_info *if_info)
>
>    /* We must have seen some sort of insn to insert, otherwise we were
>       given an empty BB to convert, and we can't handle that.  */
> -  gcc_assert (!unmodified_insns.is_empty ());
> +  gcc_assert (!insn_info.is_empty ());
>
>    /* Now fixup the assignments.  */
> -  for (unsigned i = 0; i < targets.length (); i++)
> -    if (targets[i] != temporaries[i])
> -      noce_emit_move_insn (targets[i], temporaries[i]);
> +  for (unsigned i = 0; i < insn_info.length (); i++)
> +    if (insn_info[i]->target != insn_info[i]->temporary)
> +      noce_emit_move_insn (insn_info[i]->target, insn_info[i]->temporary);
>
>    /* Actually emit the sequence if it isn't too expensive.  */
>    rtx_insn *seq = get_insns ();
> @@ -3332,10 +3316,10 @@ noce_convert_multiple_sets (struct noce_if_info *if_info)
>      set_used_flags (insn);
>
>    /* Mark all our temporaries and targets as used.  */
> -  for (unsigned i = 0; i < targets.length (); i++)
> +  for (unsigned i = 0; i < insn_info.length (); i++)
>      {
> -      set_used_flags (temporaries[i]);
> -      set_used_flags (targets[i]);
> +      set_used_flags (insn_info[i]->temporary);
> +      set_used_flags (insn_info[i]->target);
>      }
>
>    set_used_flags (cond);
> @@ -3354,7 +3338,7 @@ noce_convert_multiple_sets (struct noce_if_info *if_info)
>        return false;
>
>    emit_insn_before_setloc (seq, if_info->jump,
> -                          INSN_LOCATION (unmodified_insns.last ()));
> +                          INSN_LOCATION (insn_info.last ()->unmodified_insn));
>
>    /* Clean up THEN_BB and the edges in and out of it.  */
>    remove_edge (find_edge (test_bb, join_bb));
> @@ -3389,21 +3373,13 @@ check_for_cc_cmp_clobbers (rtx dest, const_rtx, void *p0)
>      p[0] = NULL_RTX;
>  }
>
> -/* This goes through all relevant insns of IF_INFO->then_bb and tries to
> -   create conditional moves.  In case a simple move sufficis the insn
> -   should be listed in NEED_NO_CMOV.  The rewired-src cases should be
> -   specified via REWIRED_SRC.  TARGETS, TEMPORARIES and UNMODIFIED_INSNS
> -   are specified and used in noce_convert_multiple_sets and should be passed
> -   to this function..  */
> +/* This goes through all relevant insns of IF_INFO->then_bb and tries to create
> +   conditional moves.  Information for the insns is kept in INSN_INFO.  */
>
>  static bool
>  noce_convert_multiple_sets_1 (struct noce_if_info *if_info,
> -                             hash_set<rtx_insn *> *need_no_cmov,
> -                             hash_map<rtx_insn *, int> *rewired_src,
> -                             auto_vec<rtx> *targets,
> -                             auto_vec<rtx> *temporaries,
> -                             auto_vec<rtx_insn *> *unmodified_insns,
> -                             int *last_needs_comparison)
> +                       auto_delete_vec<noce_multiple_sets_info> &insn_info,
> +                       int *last_needs_comparison)
>  {
>    basic_block then_bb = if_info->then_bb;
>    rtx_insn *jump = if_info->jump;
> @@ -3421,11 +3397,6 @@ noce_convert_multiple_sets_1 (struct noce_if_info *if_info,
>
>    rtx_insn *insn;
>    int count = 0;
> -
> -  targets->truncate (0);
> -  temporaries->truncate (0);
> -  unmodified_insns->truncate (0);
> -
>    bool second_try = *last_needs_comparison != -1;
>
>    FOR_BB_INSNS (then_bb, insn)
> @@ -3434,6 +3405,8 @@ noce_convert_multiple_sets_1 (struct noce_if_info *if_info,
>        if (!active_insn_p (insn))
>         continue;
>
> +      noce_multiple_sets_info *info = insn_info[count];
> +
>        rtx set = single_set (insn);
>        gcc_checking_assert (set);
>
> @@ -3441,9 +3414,12 @@ noce_convert_multiple_sets_1 (struct noce_if_info *if_info,
>        rtx temp;
>
>        rtx new_val = SET_SRC (set);
> -      if (int *ii = rewired_src->get (insn))
> -       new_val = simplify_replace_rtx (new_val, (*targets)[*ii],
> -                                       (*temporaries)[*ii]);
> +
> +      int i, ii;
> +      FOR_EACH_VEC_ELT (info->rewired_src, i, ii)
> +       new_val = simplify_replace_rtx (new_val, insn_info[ii]->target,
> +                                       insn_info[ii]->temporary);
> +
>        rtx old_val = target;
>
>        /* As we are transforming
> @@ -3484,7 +3460,7 @@ noce_convert_multiple_sets_1 (struct noce_if_info *if_info,
>        /* We have identified swap-style idioms before.  A normal
>          set will need to be a cmov while the first instruction of a swap-style
>          idiom can be a regular move.  This helps with costing.  */
> -      bool need_cmov = !need_no_cmov->contains (insn);
> +      bool need_cmov = info->need_cmov;
>
>        /* If we had a non-canonical conditional jump (i.e. one where
>          the fallthrough is to the "else" case) we need to reverse
> @@ -3632,21 +3608,102 @@ noce_convert_multiple_sets_1 (struct noce_if_info *if_info,
>
>        /* Bookkeeping.  */
>        count++;
> -      targets->safe_push (target);
> -      temporaries->safe_push (temp_dest);
> -      unmodified_insns->safe_push (insn);
> +
> +      info->target = target;
> +      info->temporary = temp_dest;
> +      info->unmodified_insn = insn;
>      }
>
> +  /* The number of processed insns must match init_noce_multiple_sets_info.  */
> +  gcc_assert (count == (int) insn_info.length ());
> +
>    /* Even if we did not actually need the comparison, we want to make sure
>       to try a second time in order to get rid of the temporaries.  */
>    if (*last_needs_comparison == -1)
>      *last_needs_comparison = 0;
>
> -
>    return true;
>  }
>
> +/* Find local swap-style idioms in BB and mark the first insn (1)
> +   that is only a temporary as not needing a conditional move as
> +   it is going to be dead afterwards anyway.
> +
> +     (1) int tmp = a;
> +        a = b;
> +        b = tmp;
> +
> +        ifcvt
> +        -->
> +
> +        tmp = a;
> +        a = cond ? b : a_old;
> +        b = cond ? tmp : b_old;
> +
> +    Additionally, store the index of insns like (2) when a subsequent
> +    SET reads from their destination.
>
> +    (2) int c = a;
> +       int d = c;
> +
> +       ifcvt
> +       -->
> +
> +       c = cond ? a : c_old;
> +       d = cond ? d : c;     // Need to use c rather than c_old here.
> +*/
> +
> +static void
> +init_noce_multiple_sets_info (basic_block bb,
> +                    auto_delete_vec<noce_multiple_sets_info> &insn_info)
> +{
> +  rtx_insn *insn;
> +  int count = 0;
> +  auto_vec<rtx> dests;
> +
> +  /* Iterate over all SETs, storing the destinations
> +     in DEST.
> +     - If we hit a SET that reads from a destination
> +       that we have seen before and the corresponding register
> +       is dead afterwards, the register does not need to be
> +       moved conditionally.
> +     - If we encounter a previously changed register,
> +       rewire the read to the original source.  */
> +  FOR_BB_INSNS (bb, insn)
> +    {
> +      if (!active_insn_p (insn))
> +       continue;
> +
> +      noce_multiple_sets_info *info = new noce_multiple_sets_info;
> +      info->target = NULL_RTX;
> +      info->temporary = NULL_RTX;
> +      info->unmodified_insn = NULL;
> +      info->need_cmov = true;
> +      insn_info.safe_push (info);
> +
> +      rtx set = single_set (insn);
> +      gcc_checking_assert (set);
> +
> +      rtx src = SET_SRC (set);
> +      rtx dest = SET_DEST (set);
> +
> +      /* Check if the current SET's source is the same
> +        as any previously seen destination.
> +        This is quadratic but the number of insns in BB
> +        is bounded by PARAM_MAX_RTL_IF_CONVERSION_INSNS.  */
> +      for (int i = count - 1; i >= 0; --i)
> +       if (reg_mentioned_p (dests[i], src))
> +         {
> +           if (find_reg_note (insn, REG_DEAD, src) != NULL_RTX)
> +             insn_info[i]->need_cmov = false;
> +           else
> +             insn_info[count]->rewired_src.safe_push (i);
> +         }
> +
> +      dests.safe_push (dest);
> +      count++;
> +    }
> +}
>
>  /* Return true iff basic block TEST_BB is comprised of only
>     (SET (REG) (REG)) insns suitable for conversion to a series
> @@ -4121,89 +4178,6 @@ check_cond_move_block (basic_block bb,
>    return true;
>  }
>
> -/* Find local swap-style idioms in BB and mark the first insn (1)
> -   that is only a temporary as not needing a conditional move as
> -   it is going to be dead afterwards anyway.
> -
> -     (1) int tmp = a;
> -        a = b;
> -        b = tmp;
> -
> -        ifcvt
> -        -->
> -
> -        tmp = a;
> -        a = cond ? b : a_old;
> -        b = cond ? tmp : b_old;
> -
> -    Additionally, store the index of insns like (2) when a subsequent
> -    SET reads from their destination.
> -
> -    (2) int c = a;
> -       int d = c;
> -
> -       ifcvt
> -       -->
> -
> -       c = cond ? a : c_old;
> -       d = cond ? d : c;     // Need to use c rather than c_old here.
> -*/
> -
> -static void
> -need_cmov_or_rewire (basic_block bb,
> -                    hash_set<rtx_insn *> *need_no_cmov,
> -                    hash_map<rtx_insn *, int> *rewired_src)
> -{
> -  rtx_insn *insn;
> -  int count = 0;
> -  auto_vec<rtx_insn *> insns;
> -  auto_vec<rtx> dests;
> -
> -  /* Iterate over all SETs, storing the destinations
> -     in DEST.
> -     - If we hit a SET that reads from a destination
> -       that we have seen before and the corresponding register
> -       is dead afterwards, the register does not need to be
> -       moved conditionally.
> -     - If we encounter a previously changed register,
> -       rewire the read to the original source.  */
> -  FOR_BB_INSNS (bb, insn)
> -    {
> -      rtx set, src, dest;
> -
> -      if (!active_insn_p (insn))
> -       continue;
> -
> -      set = single_set (insn);
> -      if (set == NULL_RTX)
> -       continue;
> -
> -      src = SET_SRC (set);
> -      if (SUBREG_P (src))
> -       src = SUBREG_REG (src);
> -      dest = SET_DEST (set);
> -
> -      /* Check if the current SET's source is the same
> -        as any previously seen destination.
> -        This is quadratic but the number of insns in BB
> -        is bounded by PARAM_MAX_RTL_IF_CONVERSION_INSNS.  */
> -      if (REG_P (src))
> -       for (int i = count - 1; i >= 0; --i)
> -         if (reg_overlap_mentioned_p (src, dests[i]))
> -           {
> -             if (find_reg_note (insn, REG_DEAD, src) != NULL_RTX)
> -               need_no_cmov->add (insns[i]);
> -             else
> -               rewired_src->put (insn, i);
> -           }
> -
> -      insns.safe_push (insn);
> -      dests.safe_push (dest);
> -
> -      count++;
> -    }
> -}
> -
>  /* Given a basic block BB suitable for conditional move conversion,
>     a condition COND, and pointer maps THEN_VALS and ELSE_VALS containing
>     the register values depending on COND, emit the insns in the block as
> diff --git a/gcc/ifcvt.h b/gcc/ifcvt.h
> index be1385aabe4..83420fe1207 100644
> --- a/gcc/ifcvt.h
> +++ b/gcc/ifcvt.h
> @@ -40,6 +40,22 @@ struct ce_if_block
>    int pass;                            /* Pass number.  */
>  };
>
> +struct noce_multiple_sets_info
> +{
> +  /* A list of indices to instructions that we need to rewire into this
> +     instruction when we replace them with temporary conditional moves.  */
> +  auto_vec<int> rewired_src;
> +  /* The true targets for a conditional move.  */
> +  rtx target;
> +  /* The temporary introduced for this conditional move.  */
> +  rtx temporary;
> +  /* The original instruction that we're replacing.  */
> +  rtx_insn *unmodified_insn;
> +  /* True if a conditional move is needed.
> +     False if a simple move can be used instead.  */
> +  bool need_cmov;
> +};
> +
>  /* Used by noce_process_if_block to communicate with its subroutines.
>
>     The subroutines know that A and B may be evaluated freely.  They
> --
> 2.34.1
>