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

  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(-)
  

On Thu, Nov 23, 2023 at 11:01 PM Richard Sandiford
<richard.sandiford@arm.com> wrote:
>
> Manolis Tsamis <manolis.tsamis@vrull.eu> writes:
> > 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>
> > ---
>
> Thanks, this looks like a really nice clean-up.  One comment below:
>
Thanks!

> >
> > 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)
>
> This is pre-existing, but is a REG_DEAD note enough?  I think we also
> need to check that the register isn't live on exit from the condition
> block (or, alternatively, isn't live on entry to the join block).
>
> E.g. for:
>
>   if (cond)
>     {
>       tmp = a;
>       a = b;
>       b = tmp;
>       tmp = ...;
>     }
>   ...tmp...;
>
> we need to preserve the original value of tmp when !cond, even though
> tmp is temporarily dead in the "then" block.
>
> Thanks,
> Richard
>
Good question. I played around with some tests and looked at the
original code again and I believe it's fine.
In your example, when insn is at `b = tmp;` then `tmp = a;` will be
marked as need_no_cmov because tmp will have a REG_DEAD at insn. `tmp
= ...;` will be emitted as a conditional set and the use outside the
conditional will be just fine. I don't see any issue.

But it made me realize that my updated code doesn't really make sense
on that part. Since I allow src to be an arbitrary expression and not
a single reg, the code

  if (find_reg_note (insn, REG_DEAD, src) != NULL_RTX)

is nonsensical. Apart from the fact that the check is loop invariant
it also doesn't properly handle src anyway. I'll have to think again
about how to refactor this check now that src is not just a reg.

Thanks,
Manolis

>
> > +           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