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

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

On Tue, Nov 28, 2023 at 12:12 PM Richard Sandiford
<richard.sandiford@arm.com> wrote:
>
> Manolis Tsamis <manolis.tsamis@vrull.eu> writes:
> > 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 I think we end up with:
>
>   tmp = a;
>   a = cond ? b : a;
>   b = cond ? tmp : b;
>   tmp = cond ? ... : tmp;
>
> So the net effect for !cond will be to set tmp to a, rather than
> preserve the original value of tmp.
>
Ok, I now see what you've meant. Then, indeed, it looks like a bug to
me (that fortunately didn't trigger?).
Since I'll have to refactor my change around REG_DEAD anyway, I can
make sure to fix this issue too.
I'll also re-try to create some test case that triggers this bug, if possible.

Thanks,
Manolis
> Thanks,
> Richard
>
> >
> > 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