On Thu, Nov 23, 2023 at 11:01 PM Richard Sandiford
<richard.sandif...@arm.com> wrote:
>
> Manolis Tsamis <manolis.tsa...@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.tsa...@vrull.eu>
> > ---
>
> Thanks, this looks like a really nice clean-up. One comment below:
>
> >
> > 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.
>
The new iteration of this just uses BB_LIVE_OUT to decide when to use
cmov: https://gcc.gnu.org/pipermail/gcc-patches/2024-April/649900.html
This simplifies the code and should handle some more cases (e.g.
having a temporary that is set twice in the THEN block). I think it's
true that we can emit a unconditional move iff the destination is not
live at BB out.
Thanks,
Manolis
> Thanks,
> Richard
>
>
> > + 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
