[PATCH 0/2] ifcvt: Allow if conversion of arithmetic in basic blocks with multiple sets

[PATCH 0/2] ifcvt: Allow if conversion of arithmetic in basic blocks with multiple sets

[Manolis Tsamis]

noce_convert_multiple_sets has been introduced and extended over time to handle
if conversion for blocks with multiple sets. Currently this is focused on
register moves and rejects any sort of arithmetic operations.

This series is an extension to allow more sequences to take part in if
conversion. The first patch is a required change to emit correct code and the
second patch whitelists a larger number of operations through
bb_ok_for_noce_convert_multiple_sets.

For targets that have a rich selection of conditional instructions,
like aarch64, I have seen an ~5x increase of profitable if conversions for
multiple set blocks in SPEC benchmarks. Also tested with a wide variety of
benchmarks and I have not seen performance regressions on either x64 / aarch64.

Some samples that previously resulted in a branch but now better use these
instructions can be seen in the provided test case.

Tested on aarch64 and x64; On x64 some tests that use __builtin_rint are
failing with an ICE but I believe that it's not an issue of this change.
force_operand crashes when (and:DF (not:DF (reg:DF 88)) (reg/v:DF 83 [ x ]))
is provided through emit_conditional_move.



Manolis Tsamis (2):
  ifcvt: handle sequences that clobber flags in
    noce_convert_multiple_sets
  ifcvt: Allow more operations in multiple set if conversion

 gcc/ifcvt.cc                                  | 109 ++++++++++--------
 .../aarch64/ifcvt_multiple_sets_arithm.c      |  67 +++++++++++
 2 files changed, 127 insertions(+), 49 deletions(-)
 create mode 100644 gcc/testsuite/gcc.target/aarch64/ifcvt_multiple_sets_arithm.c

-- 
2.34.1

[PATCH 1/2] ifcvt: handle sequences that clobber flags in noce_convert_multiple_sets

[Manolis Tsamis]

This is an extension of what was done in PR106590.

Currently if a sequence generated in noce_convert_multiple_sets clobbers the
condition rtx (cc_cmp or rev_cc_cmp) then only seq1 is used afterwards
(sequences that emit the comparison itself). Since this applies only from the
next iteration it assumes that the sequences generated (in particular seq2)
doesn't clobber the condition rtx itself before using it in the if_then_else,
which is only true in specific cases (currently only register/subregister moves
are allowed).

This patch changes this so it also tests if seq2 clobbers cc_cmp/rev_cc_cmp in
the current iteration. This makes it possible to include arithmetic operations
in noce_convert_multiple_sets.

gcc/ChangeLog:

	* ifcvt.cc (check_for_cc_cmp_clobbers): Use modified_in_p instead.
	(noce_convert_multiple_sets_1): Don't use seq2 if it clobbers cc_cmp.

Signed-off-by: Manolis Tsamis <manolis.tsamis@vrull.eu>
---

 gcc/ifcvt.cc | 49 +++++++++++++++++++------------------------------
 1 file changed, 19 insertions(+), 30 deletions(-)

diff --git a/gcc/ifcvt.cc b/gcc/ifcvt.cc
index 0b180b4568f..fd1ce8a1049 100644
--- a/gcc/ifcvt.cc
+++ b/gcc/ifcvt.cc
@@ -3373,20 +3373,6 @@ noce_convert_multiple_sets (struct noce_if_info *if_info)
   return TRUE;
 }
 
-/* Helper function for noce_convert_multiple_sets_1.  If store to
-   DEST can affect P[0] or P[1], clear P[0].  Called via note_stores.  */
-
-static void
-check_for_cc_cmp_clobbers (rtx dest, const_rtx, void *p0)
-{
-  rtx *p = (rtx *) p0;
-  if (p[0] == NULL_RTX)
-    return;
-  if (reg_overlap_mentioned_p (dest, p[0])
-      || (p[1] && reg_overlap_mentioned_p (dest, p[1])))
-    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
@@ -3550,9 +3536,17 @@ noce_convert_multiple_sets_1 (struct noce_if_info *if_info,
 	 creating an additional compare for each.  If successful, costing
 	 is easier and this sequence is usually preferred.  */
       if (cc_cmp)
-	seq2 = try_emit_cmove_seq (if_info, temp, cond,
-				   new_val, old_val, need_cmov,
-				   &cost2, &temp_dest2, cc_cmp, rev_cc_cmp);
+	{
+	  seq2 = try_emit_cmove_seq (if_info, temp, cond,
+				     new_val, old_val, need_cmov,
+				     &cost2, &temp_dest2, cc_cmp, rev_cc_cmp);
+
+	  /* The if_then_else in SEQ2 may be affected when cc_cmp/rev_cc_cmp is
+	     clobbered.  We can't safely use the sequence in this case.  */
+	  if (seq2 && (modified_in_p (cc_cmp, seq2)
+	      || (rev_cc_cmp && modified_in_p (rev_cc_cmp, seq2))))
+	    seq2 = NULL;
+	}
 
       /* The backend might have created a sequence that uses the
 	 condition.  Check this.  */
@@ -3607,21 +3601,16 @@ noce_convert_multiple_sets_1 (struct noce_if_info *if_info,
 	  return FALSE;
 	}
 
-      if (cc_cmp)
+      if (cc_cmp && seq == seq1)
 	{
-	  /* Check if SEQ can clobber registers mentioned in
-	     cc_cmp and/or rev_cc_cmp.  If yes, we need to use
-	     only seq1 from that point on.  */
-	  rtx cc_cmp_pair[2] = { cc_cmp, rev_cc_cmp };
-	  for (walk = seq; walk; walk = NEXT_INSN (walk))
+	  /* Check if SEQ can clobber registers mentioned in cc_cmp/rev_cc_cmp.
+	     If yes, we need to use only seq1 from that point on.
+	     Only check when we use seq1 since we have already tested seq2.  */
+	  if (modified_in_p (cc_cmp, seq)
+	      || (rev_cc_cmp && modified_in_p (rev_cc_cmp, seq)))
 	    {
-	      note_stores (walk, check_for_cc_cmp_clobbers, cc_cmp_pair);
-	      if (cc_cmp_pair[0] == NULL_RTX)
-		{
-		  cc_cmp = NULL_RTX;
-		  rev_cc_cmp = NULL_RTX;
-		  break;
-		}
+	      cc_cmp = NULL_RTX;
+	      rev_cc_cmp = NULL_RTX;
 	    }
 	}
 
-- 
2.34.1

[PATCH 2/2] ifcvt: Allow more operations in multiple set if conversion

[Manolis Tsamis]

Currently the operations allowed for if conversion of a basic block with
multiple sets are few, namely REG, SUBREG and CONST_INT (as controlled by
bb_ok_for_noce_convert_multiple_sets).

This commit allows more operations (arithmetic, compare, etc) to participate
in if conversion. The target's profitability hook and ifcvt's costing is
expected to reject sequences that are unprofitable.

This is especially useful for targets which provide a rich selection of
conditional instructions (like aarch64 which has cinc, csneg, csinv, ccmp, ...)
which are currently not used in basic blocks with more than a single set.

gcc/ChangeLog:

	* ifcvt.cc (try_emit_cmove_seq): Modify comments.
	(noce_convert_multiple_sets_1): Modify comments.
	(bb_ok_for_noce_convert_multiple_sets): Allow more operations.

gcc/testsuite/ChangeLog:

	* gcc.target/aarch64/ifcvt_multiple_sets_arithm.c: New test.

Signed-off-by: Manolis Tsamis <manolis.tsamis@vrull.eu>
---

 gcc/ifcvt.cc                                  | 60 +++++++++++------
 .../aarch64/ifcvt_multiple_sets_arithm.c      | 67 +++++++++++++++++++
 2 files changed, 108 insertions(+), 19 deletions(-)
 create mode 100644 gcc/testsuite/gcc.target/aarch64/ifcvt_multiple_sets_arithm.c

diff --git a/gcc/ifcvt.cc b/gcc/ifcvt.cc
index fd1ce8a1049..a9e5352a0a0 100644
--- a/gcc/ifcvt.cc
+++ b/gcc/ifcvt.cc
@@ -3213,13 +3213,13 @@ try_emit_cmove_seq (struct noce_if_info *if_info, rtx temp,
 /* We have something like:
 
      if (x > y)
-       { i = a; j = b; k = c; }
+       { i = EXPR_A; j = EXPR_B; k = EXPR_C; }
 
    Make it:
 
-     tmp_i = (x > y) ? a : i;
-     tmp_j = (x > y) ? b : j;
-     tmp_k = (x > y) ? c : k;
+     tmp_i = (x > y) ? EXPR_A : i;
+     tmp_j = (x > y) ? EXPR_B : j;
+     tmp_k = (x > y) ? EXPR_C : k;
      i = tmp_i;
      j = tmp_j;
      k = tmp_k;
@@ -3635,11 +3635,10 @@ noce_convert_multiple_sets_1 (struct noce_if_info *if_info,
 
 
 
-/* Return true iff basic block TEST_BB is comprised of only
-   (SET (REG) (REG)) insns suitable for conversion to a series
-   of conditional moves.  Also check that we have more than one set
-   (other routines can handle a single set better than we would), and
-   fewer than PARAM_MAX_RTL_IF_CONVERSION_INSNS sets.  While going
+/* Return true iff basic block TEST_BB is suitable for conversion to a
+   series of conditional moves.  Also check that we have more than one
+   set (other routines can handle a single set better than we would),
+   and fewer than PARAM_MAX_RTL_IF_CONVERSION_INSNS sets.  While going
    through the insns store the sum of their potential costs in COST.  */
 
 static bool
@@ -3665,20 +3664,43 @@ bb_ok_for_noce_convert_multiple_sets (basic_block test_bb, unsigned *cost)
       rtx dest = SET_DEST (set);
       rtx src = SET_SRC (set);
 
-      /* We can possibly relax this, but for now only handle REG to REG
-	 (including subreg) moves.  This avoids any issues that might come
-	 from introducing loads/stores that might violate data-race-freedom
-	 guarantees.  */
-      if (!REG_P (dest))
+      /* Do not handle anything involving memory loads/stores since it might
+	 violate data-race-freedom guarantees.  */
+      if (!REG_P (dest) || contains_mem_rtx_p (src))
 	return false;
 
-      if (!((REG_P (src) || CONSTANT_P (src))
-	    || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
-	      && subreg_lowpart_p (src))))
+      /* Allow a wide range of operations and let the costing function decide
+	 if the conversion is worth it later.  */
+      enum rtx_code code = GET_CODE (src);
+      if (!(CONSTANT_P (src)
+	    || code == REG
+	    || code == SUBREG
+	    || code == ZERO_EXTEND
+	    || code == SIGN_EXTEND
+	    || code == NOT
+	    || code == NEG
+	    || code == PLUS
+	    || code == MINUS
+	    || code == AND
+	    || code == IOR
+	    || code == MULT
+	    || code == ASHIFT
+	    || code == ASHIFTRT
+	    || code == NE
+	    || code == EQ
+	    || code == GE
+	    || code == GT
+	    || code == LE
+	    || code == LT
+	    || code == GEU
+	    || code == GTU
+	    || code == LEU
+	    || code == LTU
+	    || code == COMPARE))
 	return false;
 
-      /* Destination must be appropriate for a conditional write.  */
-      if (!noce_operand_ok (dest))
+      /* Destination and source must be appropriate.  */
+      if (!noce_operand_ok (dest) || !noce_operand_ok (src))
 	return false;
 
       /* We must be able to conditionally move in this mode.  */
diff --git a/gcc/testsuite/gcc.target/aarch64/ifcvt_multiple_sets_arithm.c b/gcc/testsuite/gcc.target/aarch64/ifcvt_multiple_sets_arithm.c
new file mode 100644
index 00000000000..f29cc72263a
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/ifcvt_multiple_sets_arithm.c
@@ -0,0 +1,67 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-rtl-ce1" } */
+
+void sink2(int, int);
+void sink3(int, int, int);
+
+void cond_1(int cond, int x, int y) {
+    if (cond) {
+        x = x << 4;
+        y = 1;
+    }
+
+    sink2(x, y);
+}
+
+void cond_2(int cond, int x, int y) {
+    if (cond) {
+        x++;
+        y++;
+    }
+
+    sink2(x, y);
+}
+
+void cond_3(int cond, int x1, int x2, int x3) {
+    if (cond) {
+        x1++;
+        x2++;
+        x3++;
+    }
+
+    sink3(x1, x2, x3);
+}
+
+void cond_4(int cond, int x, int y) {
+    if (cond) {
+        x += 2;
+        y += 3;
+    }
+
+    sink2(x, y);
+}
+
+void cond_5(int cond, int x, int y, int r1, int r2) {
+    if (cond) {
+        x = r1 + 2;
+        y = r2 - 34;
+    }
+
+    sink2(x, y);
+}
+
+void cond_6(int cond, int x, int y) {
+    if (cond) {
+        x = -x;
+        y = ~y;
+    }
+
+    sink2(x, y);
+}
+
+/* { dg-final { scan-assembler-times "cinc\t" 5 } } */
+/* { dg-final { scan-assembler-times "csneg\t" 1 } } */
+/* { dg-final { scan-assembler-times "csinv\t" 1 } } */
+/* { dg-final { scan-assembler "csel\t" 1 } } */
+
+/* { dg-final { scan-rtl-dump-times "if-conversion succeeded through noce_convert_multiple_sets" 6 "ce1" } } */
\ No newline at end of file
-- 
2.34.1

Re: [PATCH 2/2] ifcvt: Allow more operations in multiple set if conversion

[Robin Dapp]

Hi Manolis,

that looks like a nice enhancement of what's already possible.  The concern
I had some years back already was that this function would eventually
grow and cannibalize on some of what the other functions in ifcvt already
do :)  At some point we really should unify but that's not within the
scope of this patch.

IMHO we're already pretty far towards general "conditional execution"
with conditional increments, selects and so on (and the function is still
called "_noce") and historically the cond_exec functions would have
taken care of that.  To my knowledge though, none of the major backends
implements anything like (cond_exec ...) anymore and relies on bit-twiddling
tricks to generate the conditional instructions.

Have you checked whether cond_exec and others could be adjusted to
handle the conditional instructions you want to see?  They don't perform
full cost comparison though but just count.

I would expect a bit of discussion around that but from a first look
I don't have major concerns.

> -/* Return true iff basic block TEST_BB is comprised of only
> -   (SET (REG) (REG)) insns suitable for conversion to a series
> -   of conditional moves.  Also check that we have more than one set
> -   (other routines can handle a single set better than we would), and
> -   fewer than PARAM_MAX_RTL_IF_CONVERSION_INSNS sets.  While going
> +/* Return true iff basic block TEST_BB is suitable for conversion to a
> +   series of conditional moves.  Also check that we have more than one

Might want to change the "conditional moves" while you're at it.

>  
> -      if (!((REG_P (src) || CONSTANT_P (src))
> -	    || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
> -	      && subreg_lowpart_p (src))))
> +      /* Allow a wide range of operations and let the costing function decide
> +	 if the conversion is worth it later.  */
> +      enum rtx_code code = GET_CODE (src);
> +      if (!(CONSTANT_P (src)
> +	    || code == REG
> +	    || code == SUBREG
> +	    || code == ZERO_EXTEND
> +	    || code == SIGN_EXTEND
> +	    || code == NOT
> +	    || code == NEG
> +	    || code == PLUS
> +	    || code == MINUS
> +	    || code == AND
> +	    || code == IOR
> +	    || code == MULT
> +	    || code == ASHIFT
> +	    || code == ASHIFTRT
> +	    || code == NE
> +	    || code == EQ
> +	    || code == GE
> +	    || code == GT
> +	    || code == LE
> +	    || code == LT
> +	    || code == GEU
> +	    || code == GTU
> +	    || code == LEU
> +	    || code == LTU
> +	    || code == COMPARE))

We're potentially checking many more patterns than before.  Maybe it
would make sense to ask the backend whether it has a pattern for
the respective code?

Regards
 Robin

Re: [PATCH 2/2] ifcvt: Allow more operations in multiple set if conversion

[Manolis Tsamis]

On Mon, Jul 3, 2023 at 12:12 PM Robin Dapp <rdapp.gcc@gmail.com> wrote:
>
> Hi Manolis,
>
> that looks like a nice enhancement of what's already possible.  The concern
> I had some years back already was that this function would eventually
> grow and cannibalize on some of what the other functions in ifcvt already
> do :)  At some point we really should unify but that's not within the
> scope of this patch.
>

Hi Robin,

Indeed and it would be nice to extend the multi statement
implementation to the point that the others are not needed :)
I have some future plans to analyze cases where the multi-statement
performs worse and improve on that.

> IMHO we're already pretty far towards general "conditional execution"
> with conditional increments, selects and so on (and the function is still
> called "_noce") and historically the cond_exec functions would have
> taken care of that.  To my knowledge though, none of the major backends
> implements anything like (cond_exec ...) anymore and relies on bit-twiddling
> tricks to generate the conditional instructions.
>
> Have you checked whether cond_exec and others could be adjusted to
> handle the conditional instructions you want to see?  They don't perform
> full cost comparison though but just count.
>

Thanks for mentioning that, I was not really aware of cond_exec usage.
As you say, it looks like cond_exec isn't used very much on major backends.

Since noce_convert_multiple_sets_1 is just using the existing ifcvt
machinery (specifically noce_emit_cmove / try_emit_cmove_seq), is this
a question of whether we want to replace (if_then_else ...) with
(cond_exec ...) in general?
If that is beneficial then I could try to implement a change like
this, but that should probably be a separate effort from this
implementation.

> I would expect a bit of discussion around that but from a first look
> I don't have major concerns.
>
> > -/* Return true iff basic block TEST_BB is comprised of only
> > -   (SET (REG) (REG)) insns suitable for conversion to a series
> > -   of conditional moves.  Also check that we have more than one set
> > -   (other routines can handle a single set better than we would), and
> > -   fewer than PARAM_MAX_RTL_IF_CONVERSION_INSNS sets.  While going
> > +/* Return true iff basic block TEST_BB is suitable for conversion to a
> > +   series of conditional moves.  Also check that we have more than one
>
> Might want to change the "conditional moves" while you're at it.
>

Thanks for pointing out this comment, I missed it. I will rewrite the
relevant parts.

> >
> > -      if (!((REG_P (src) || CONSTANT_P (src))
> > -         || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
> > -           && subreg_lowpart_p (src))))
> > +      /* Allow a wide range of operations and let the costing function decide
> > +      if the conversion is worth it later.  */
> > +      enum rtx_code code = GET_CODE (src);
> > +      if (!(CONSTANT_P (src)
> > +         || code == REG
> > +         || code == SUBREG
> > +         || code == ZERO_EXTEND
> > +         || code == SIGN_EXTEND
> > +         || code == NOT
> > +         || code == NEG
> > +         || code == PLUS
> > +         || code == MINUS
> > +         || code == AND
> > +         || code == IOR
> > +         || code == MULT
> > +         || code == ASHIFT
> > +         || code == ASHIFTRT
> > +         || code == NE
> > +         || code == EQ
> > +         || code == GE
> > +         || code == GT
> > +         || code == LE
> > +         || code == LT
> > +         || code == GEU
> > +         || code == GTU
> > +         || code == LEU
> > +         || code == LTU
> > +         || code == COMPARE))
>
> We're potentially checking many more patterns than before.  Maybe it
> would make sense to ask the backend whether it has a pattern for
> the respective code?
>

Is it an issue if the backend doesn't have a pattern for a respective code?

My goal here is to not limit if conversion for sequences based on the
code but rather let ifcvt / the backedn decide based on costing.
That's because from what I've seen, conditional set instructions can
be beneficial even when the backend doesn't have a specific
instruction for that code.

Best,
Manolis

> Regards
>  Robin
>

Re: [PATCH 2/2] ifcvt: Allow more operations in multiple set if conversion

[Manolis Tsamis]

I resent this with just the change in the comment.
OK to merge?

Manolis

On Tue, Jul 4, 2023 at 5:32 PM Manolis Tsamis <manolis.tsamis@vrull.eu> wrote:
>
> On Mon, Jul 3, 2023 at 12:12 PM Robin Dapp <rdapp.gcc@gmail.com> wrote:
> >
> > Hi Manolis,
> >
> > that looks like a nice enhancement of what's already possible.  The concern
> > I had some years back already was that this function would eventually
> > grow and cannibalize on some of what the other functions in ifcvt already
> > do :)  At some point we really should unify but that's not within the
> > scope of this patch.
> >
>
> Hi Robin,
>
> Indeed and it would be nice to extend the multi statement
> implementation to the point that the others are not needed :)
> I have some future plans to analyze cases where the multi-statement
> performs worse and improve on that.
>
> > IMHO we're already pretty far towards general "conditional execution"
> > with conditional increments, selects and so on (and the function is still
> > called "_noce") and historically the cond_exec functions would have
> > taken care of that.  To my knowledge though, none of the major backends
> > implements anything like (cond_exec ...) anymore and relies on bit-twiddling
> > tricks to generate the conditional instructions.
> >
> > Have you checked whether cond_exec and others could be adjusted to
> > handle the conditional instructions you want to see?  They don't perform
> > full cost comparison though but just count.
> >
>
> Thanks for mentioning that, I was not really aware of cond_exec usage.
> As you say, it looks like cond_exec isn't used very much on major backends.
>
> Since noce_convert_multiple_sets_1 is just using the existing ifcvt
> machinery (specifically noce_emit_cmove / try_emit_cmove_seq), is this
> a question of whether we want to replace (if_then_else ...) with
> (cond_exec ...) in general?
> If that is beneficial then I could try to implement a change like
> this, but that should probably be a separate effort from this
> implementation.
>
> > I would expect a bit of discussion around that but from a first look
> > I don't have major concerns.
> >
> > > -/* Return true iff basic block TEST_BB is comprised of only
> > > -   (SET (REG) (REG)) insns suitable for conversion to a series
> > > -   of conditional moves.  Also check that we have more than one set
> > > -   (other routines can handle a single set better than we would), and
> > > -   fewer than PARAM_MAX_RTL_IF_CONVERSION_INSNS sets.  While going
> > > +/* Return true iff basic block TEST_BB is suitable for conversion to a
> > > +   series of conditional moves.  Also check that we have more than one
> >
> > Might want to change the "conditional moves" while you're at it.
> >
>
> Thanks for pointing out this comment, I missed it. I will rewrite the
> relevant parts.
>
> > >
> > > -      if (!((REG_P (src) || CONSTANT_P (src))
> > > -         || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
> > > -           && subreg_lowpart_p (src))))
> > > +      /* Allow a wide range of operations and let the costing function decide
> > > +      if the conversion is worth it later.  */
> > > +      enum rtx_code code = GET_CODE (src);
> > > +      if (!(CONSTANT_P (src)
> > > +         || code == REG
> > > +         || code == SUBREG
> > > +         || code == ZERO_EXTEND
> > > +         || code == SIGN_EXTEND
> > > +         || code == NOT
> > > +         || code == NEG
> > > +         || code == PLUS
> > > +         || code == MINUS
> > > +         || code == AND
> > > +         || code == IOR
> > > +         || code == MULT
> > > +         || code == ASHIFT
> > > +         || code == ASHIFTRT
> > > +         || code == NE
> > > +         || code == EQ
> > > +         || code == GE
> > > +         || code == GT
> > > +         || code == LE
> > > +         || code == LT
> > > +         || code == GEU
> > > +         || code == GTU
> > > +         || code == LEU
> > > +         || code == LTU
> > > +         || code == COMPARE))
> >
> > We're potentially checking many more patterns than before.  Maybe it
> > would make sense to ask the backend whether it has a pattern for
> > the respective code?
> >
>
> Is it an issue if the backend doesn't have a pattern for a respective code?
>
> My goal here is to not limit if conversion for sequences based on the
> code but rather let ifcvt / the backedn decide based on costing.
> That's because from what I've seen, conditional set instructions can
> be beneficial even when the backend doesn't have a specific
> instruction for that code.
>
> Best,
> Manolis
>
> > Regards
> >  Robin
> >