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

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

[Manolis Tsamis]

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 *);
 \f
 /* 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

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

[Manolis Tsamis]

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
>

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

[Richard Sandiford]

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:

>
> 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 *);
>  \f
>  /* 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


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

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

[Manolis Tsamis]

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

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

[Richard Sandiford]

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.

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

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

[Manolis Tsamis]

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

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

[Manolis Tsamis]

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:
>
> >
> > 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.
>

Something else that I noticed about the current code is that the condition below

             if (find_reg_note (insn, REG_DEAD, src) != NULL_RTX)
               need_no_cmov->add (insns[i]);
             else
               rewired_src->put (insn, i);

considers rewiring and no_cmov exclusive, but they are not since the
same register can appear in SRC and as a REG_DEAD note in a single
instruction.
For example if we had something like

 (insn 1 (set (reg:SI 107) (reg:SI 105)))
 (insn 2 (set (reg:SI 102) (reg:SI 107))
    (expr_list:REG_DEAD (reg:SI 107))

Then the existing code would not rewrite insn 2 because reg 107 is
also dead at insn 2.

But although we have identified these issues I haven't been able to
trigger them in either x86 or aarch64.
One reason looks to be that although there is coded support for SUBREG
in noce_convert_multiple_sets, which would make it possible to write
some more complicated testcases, it does not trigger.
On aarch64 (and (reg X) (const_int 0xfff...)) is used and on x86 the
SUBREG is nested within zero_extend or sign_extend so SUBREG_P is
false in both cases. So we're left with only simple register moves
which look to work fine (there may be related issues in other targets
though).

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

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

[Manolis Tsamis]

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