[ARM] Optimize compare against smin/umin

[ARM] Optimize compare against smin/umin

[Michael Collison]

This patch is designed to optimize constructs such as:

#define min(x, y) ((x) <= (y)) ? (x) : (y)

unsignedint  foo (unsignedint  i, unsignedint  x ,unsignedint  y)
{
   return  i < (min (x, y));
}

int  bar (int  i,int  x,int  y)
{
   return  i < (min (x, y));
}

Patch was tested on arm-linux-gnueabi, arm-linux-gnueabihf, 
armeb-linux-gnueabihf. Okay for trunk?


2015-06-24  Michael Collison  <michael.collison@linaro.org

     2012-05-01  Ramana Radhakrishnan <ramana.radhakrishnan@linaro.org>

     * gcc/config/arm/arm.md (*arm_smin_cmp): New pattern.
     (*arm_umin_cmp): Likewise.

diff --git a/gcc/config/arm/arm.md b/gcc/config/arm/arm.md
index 1ac8af0..994c95f 100644
--- a/gcc/config/arm/arm.md
+++ b/gcc/config/arm/arm.md
@@ -3455,6 +3455,28 @@
     (set_attr "type" "multiple,multiple")]
  )

+;; t = (s/u)min (x, y)
+;; cc = cmp (t, z)
+;; is the same as
+;; cmp x, z
+;; cmpge(u) y, z
+
+(define_insn_and_split "*arm_smin_cmp"
+  [(set (reg:CC CC_REGNUM)
+    (compare:CC
+     (smin:SI (match_operand:SI 0 "s_register_operand" "r")
+          (match_operand:SI 1 "s_register_operand" "r"))
+     (match_operand:SI 2 "s_register_operand" "r")))]
+  "TARGET_32BIT"
+  "#"
+  ""
+  [(set (reg:CC CC_REGNUM)
+    (compare:CC (match_dup 0) (match_dup 2)))
+   (cond_exec (ge:CC (reg:CC CC_REGNUM) (const_int 0))
+          (set (reg:CC CC_REGNUM)
+           (compare:CC (match_dup 1) (match_dup 2))))]
+)
+
  (define_expand "umaxsi3"
    [(parallel [
      (set (match_operand:SI 0 "s_register_operand" "")
@@ -3521,6 +3543,22 @@
     (set_attr "type" "store1")]
  )

+(define_insn_and_split "*arm_umin_cmp"
+  [(set (reg:CC CC_REGNUM)
+    (compare:CC
+     (umin:SI (match_operand:SI 0 "s_register_operand" "r")
+          (match_operand:SI 1 "s_register_operand" "r"))
+     (match_operand:SI 2 "s_register_operand" "r")))]
+  "TARGET_32BIT"
+  "#"
+  ""
+  [(set (reg:CC CC_REGNUM)
+    (compare:CC (match_dup 0) (match_dup 2)))
+   (cond_exec (geu:CC (reg:CC CC_REGNUM) (const_int 0))
+          (set (reg:CC CC_REGNUM)
+           (compare:CC (match_dup 1) (match_dup 2))))]
+)
+
  (define_insn "*store_minmaxsi"
    [(set (match_operand:SI 0 "memory_operand" "=m")
      (match_operator:SI 3 "minmax_operator"

-- 
Michael Collison
Linaro Toolchain Working Group
michael.collison@linaro.org

Re: [ARM] Optimize compare against smin/umin

[Ramana Radhakrishnan]

On Thu, Jun 25, 2015 at 6:08 PM, Michael Collison
<michael.collison@linaro.org> wrote:
>
> This patch is designed to optimize constructs such as:
>
> #define min(x, y) ((x) <= (y)) ? (x) : (y)
>
> unsignedint  foo (unsignedint  i, unsignedint  x ,unsignedint  y)
> {
>   return  i < (min (x, y));
> }
>
> int  bar (int  i,int  x,int  y)
> {
>   return  i < (min (x, y));
> }
>
> Patch was tested on arm-linux-gnueabi, arm-linux-gnueabihf,
> armeb-linux-gnueabihf. Okay for trunk?

Sorry about the slow review and I wanted someone else to look at it
given I had a hand in writing this patch up.

Please add a testcase.

>
>
> 2015-06-24  Michael Collison  <michael.collison@linaro.org
>
>     2012-05-01  Ramana Radhakrishnan <ramana.radhakrishnan@linaro.org>

Please fix the Changelog formatting here.

>
>     * gcc/config/arm/arm.md (*arm_smin_cmp): New pattern.
>     (*arm_umin_cmp): Likewise.
>
> diff --git a/gcc/config/arm/arm.md b/gcc/config/arm/arm.md
> index 1ac8af0..994c95f 100644
> --- a/gcc/config/arm/arm.md
> +++ b/gcc/config/arm/arm.md
> @@ -3455,6 +3455,28 @@
>     (set_attr "type" "multiple,multiple")]
>  )
>
> +;; t = (s/u)min (x, y)
> +;; cc = cmp (t, z)
> +;; is the same as
> +;; cmp x, z
> +;; cmpge(u) y, z
> +
> +(define_insn_and_split "*arm_smin_cmp"
> +  [(set (reg:CC CC_REGNUM)
> +    (compare:CC
> +     (smin:SI (match_operand:SI 0 "s_register_operand" "r")
> +          (match_operand:SI 1 "s_register_operand" "r"))
> +     (match_operand:SI 2 "s_register_operand" "r")))]
> +  "TARGET_32BIT"
> +  "#"
> +  ""
> +  [(set (reg:CC CC_REGNUM)
> +    (compare:CC (match_dup 0) (match_dup 2)))
> +   (cond_exec (ge:CC (reg:CC CC_REGNUM) (const_int 0))
> +          (set (reg:CC CC_REGNUM)
> +           (compare:CC (match_dup 1) (match_dup 2))))]
> +)


IIUC it's not entirely safe to have cond_execs in the instruction
stream prior to reload - I think the consensus was that spilling and
filling with cond-exec style instructions could end up with
non-cond-exec style spills thus destroying registers in the non
cond-exec cases. so, lets just add a reload_completed to be safe here.

See https://patches.linaro.org/6469/ for more on this topic.

> +
>  (define_expand "umaxsi3"
>    [(parallel [
>      (set (match_operand:SI 0 "s_register_operand" "")
> @@ -3521,6 +3543,22 @@
>     (set_attr "type" "store1")]
>  )
>
> +(define_insn_and_split "*arm_umin_cmp"
> +  [(set (reg:CC CC_REGNUM)
> +    (compare:CC
> +     (umin:SI (match_operand:SI 0 "s_register_operand" "r")
> +          (match_operand:SI 1 "s_register_operand" "r"))
> +     (match_operand:SI 2 "s_register_operand" "r")))]
> +  "TARGET_32BIT"
> +  "#"
> +  ""
> +  [(set (reg:CC CC_REGNUM)
> +    (compare:CC (match_dup 0) (match_dup 2)))
> +   (cond_exec (geu:CC (reg:CC CC_REGNUM) (const_int 0))
> +          (set (reg:CC CC_REGNUM)
> +           (compare:CC (match_dup 1) (match_dup 2))))]
> +)
> +

Please move this below the other pattern.

>  (define_insn "*store_minmaxsi"
>    [(set (match_operand:SI 0 "memory_operand" "=m")
>      (match_operator:SI 3 "minmax_operator"
>
> --
> Michael Collison
> Linaro Toolchain Working Group
> michael.collison@linaro.org
>


Please repost after testing those changes and then I think this is OK to go in.

regards
Ramana

Re: [ARM] Optimize compare against smin/umin

[Michael Collison]

Here is an updated patch that addresses the issues you mentioned:

2015-07-24  Michael Collison  <michael.collison@linaro.org
                     Ramana Radhakrishnan <ramana.radhakrishnan@arm.com>

               * gcc/config/arm/arm.md (*arm_smin_cmp): New pattern.
               (*arm_umin_cmp): Likewise.
               * gcc.target/arm/mincmp.c: Test min compare idiom.

diff --git a/gcc/config/arm/arm.md b/gcc/config/arm/arm.md
index 0be70a8..361c292 100644
--- a/gcc/config/arm/arm.md
+++ b/gcc/config/arm/arm.md
@@ -3455,6 +3455,44 @@
     (set_attr "type" "multiple,multiple")]
  )

+;; t = (s/u)min (x, y)
+;; cc = cmp (t, z)
+;; is the same as
+;; cmp x, z
+;; cmpge(u) y, z
+
+(define_insn_and_split "*arm_smin_cmp"
+  [(set (reg:CC CC_REGNUM)
+    (compare:CC
+     (smin:SI (match_operand:SI 0 "s_register_operand" "r")
+          (match_operand:SI 1 "s_register_operand" "r"))
+     (match_operand:SI 2 "s_register_operand" "r")))]
+  "TARGET_32BIT"
+  "#"
+  "&& reload_completed"
+  [(set (reg:CC CC_REGNUM)
+    (compare:CC (match_dup 0) (match_dup 2)))
+   (cond_exec (ge:CC (reg:CC CC_REGNUM) (const_int 0))
+          (set (reg:CC CC_REGNUM)
+           (compare:CC (match_dup 1) (match_dup 2))))]
+)
+
+(define_insn_and_split "*arm_umin_cmp"
+  [(set (reg:CC CC_REGNUM)
+    (compare:CC
+     (umin:SI (match_operand:SI 0 "s_register_operand" "r")
+          (match_operand:SI 1 "s_register_operand" "r"))
+     (match_operand:SI 2 "s_register_operand" "r")))]
+  "TARGET_32BIT"
+  "#"
+  "&& reload_completed"
+  [(set (reg:CC CC_REGNUM)
+    (compare:CC (match_dup 0) (match_dup 2)))
+   (cond_exec (geu:CC (reg:CC CC_REGNUM) (const_int 0))
+          (set (reg:CC CC_REGNUM)
+           (compare:CC (match_dup 1) (match_dup 2))))]
+)
+
  (define_expand "umaxsi3"
    [(parallel [
      (set (match_operand:SI 0 "s_register_operand" "")
diff --git a/gcc/testsuite/gcc.target/arm/mincmp.c 
b/gcc/testsuite/gcc.target/arm/mincmp.c
new file mode 100644
index 0000000..2a55c6d
--- /dev/null
+++ b/gcc/testsuite/gcc.target/arm/mincmp.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+/* { dg-require-effective-target arm32 } */
+
+#define min(x, y) ((x) <= (y)) ? (x) : (y)
+
+unsigned int foo (unsigned int i, unsigned int x ,unsigned int y)
+{
+  return i < (min (x, y));
+}
+
+int bar (int i, int x, int y)
+{
+  return i < (min (x, y));
+}
+
+/* { dg-final { scan-assembler "cmpcs" } } */
+/* { dg-final { scan-assembler "cmpge" } } */
-- 
1.9.1
On 07/13/2015 04:27 AM, Ramana Radhakrishnan wrote:
> On Thu, Jun 25, 2015 at 6:08 PM, Michael Collison
> <michael.collison@linaro.org> wrote:
>> This patch is designed to optimize constructs such as:
>>
>> #define min(x, y) ((x) <= (y)) ? (x) : (y)
>>
>> unsignedint  foo (unsignedint  i, unsignedint  x ,unsignedint  y)
>> {
>>    return  i < (min (x, y));
>> }
>>
>> int  bar (int  i,int  x,int  y)
>> {
>>    return  i < (min (x, y));
>> }
>>
>> Patch was tested on arm-linux-gnueabi, arm-linux-gnueabihf,
>> armeb-linux-gnueabihf. Okay for trunk?
> Sorry about the slow review and I wanted someone else to look at it
> given I had a hand in writing this patch up.
>
> Please add a testcase.
>
>>
>> 2015-06-24  Michael Collison  <michael.collison@linaro.org
>>
>>      2012-05-01  Ramana Radhakrishnan <ramana.radhakrishnan@linaro.org>
> Please fix the Changelog formatting here.
>
>>      * gcc/config/arm/arm.md (*arm_smin_cmp): New pattern.
>>      (*arm_umin_cmp): Likewise.
>>
>> diff --git a/gcc/config/arm/arm.md b/gcc/config/arm/arm.md
>> index 1ac8af0..994c95f 100644
>> --- a/gcc/config/arm/arm.md
>> +++ b/gcc/config/arm/arm.md
>> @@ -3455,6 +3455,28 @@
>>      (set_attr "type" "multiple,multiple")]
>>   )
>>
>> +;; t = (s/u)min (x, y)
>> +;; cc = cmp (t, z)
>> +;; is the same as
>> +;; cmp x, z
>> +;; cmpge(u) y, z
>> +
>> +(define_insn_and_split "*arm_smin_cmp"
>> +  [(set (reg:CC CC_REGNUM)
>> +    (compare:CC
>> +     (smin:SI (match_operand:SI 0 "s_register_operand" "r")
>> +          (match_operand:SI 1 "s_register_operand" "r"))
>> +     (match_operand:SI 2 "s_register_operand" "r")))]
>> +  "TARGET_32BIT"
>> +  "#"
>> +  ""
>> +  [(set (reg:CC CC_REGNUM)
>> +    (compare:CC (match_dup 0) (match_dup 2)))
>> +   (cond_exec (ge:CC (reg:CC CC_REGNUM) (const_int 0))
>> +          (set (reg:CC CC_REGNUM)
>> +           (compare:CC (match_dup 1) (match_dup 2))))]
>> +)
>
> IIUC it's not entirely safe to have cond_execs in the instruction
> stream prior to reload - I think the consensus was that spilling and
> filling with cond-exec style instructions could end up with
> non-cond-exec style spills thus destroying registers in the non
> cond-exec cases. so, lets just add a reload_completed to be safe here.
>
> See https://patches.linaro.org/6469/ for more on this topic.
>
>> +
>>   (define_expand "umaxsi3"
>>     [(parallel [
>>       (set (match_operand:SI 0 "s_register_operand" "")
>> @@ -3521,6 +3543,22 @@
>>      (set_attr "type" "store1")]
>>   )
>>
>> +(define_insn_and_split "*arm_umin_cmp"
>> +  [(set (reg:CC CC_REGNUM)
>> +    (compare:CC
>> +     (umin:SI (match_operand:SI 0 "s_register_operand" "r")
>> +          (match_operand:SI 1 "s_register_operand" "r"))
>> +     (match_operand:SI 2 "s_register_operand" "r")))]
>> +  "TARGET_32BIT"
>> +  "#"
>> +  ""
>> +  [(set (reg:CC CC_REGNUM)
>> +    (compare:CC (match_dup 0) (match_dup 2)))
>> +   (cond_exec (geu:CC (reg:CC CC_REGNUM) (const_int 0))
>> +          (set (reg:CC CC_REGNUM)
>> +           (compare:CC (match_dup 1) (match_dup 2))))]
>> +)
>> +
> Please move this below the other pattern.
>
>>   (define_insn "*store_minmaxsi"
>>     [(set (match_operand:SI 0 "memory_operand" "=m")
>>       (match_operator:SI 3 "minmax_operator"
>>
>> --
>> Michael Collison
>> Linaro Toolchain Working Group
>> michael.collison@linaro.org
>>
>
> Please repost after testing those changes and then I think this is OK to go in.
>
> regards
> Ramana

-- 
Michael Collison
Linaro Toolchain Working Group
michael.collison@linaro.org

Re: [ARM] Optimize compare against smin/umin

[Kyrill Tkachov]

Hi Michael,

On 26/07/15 23:54, Michael Collison wrote:
> Here is an updated patch that addresses the issues you mentioned:
>
> 2015-07-24  Michael Collison  <michael.collison@linaro.org
>                       Ramana Radhakrishnan <ramana.radhakrishnan@arm.com>
>
>                 * gcc/config/arm/arm.md (*arm_smin_cmp): New pattern.
>                 (*arm_umin_cmp): Likewise.
>                 * gcc.target/arm/mincmp.c: Test min compare idiom.

Just "New test." would be a better ChangeLog entry for this.

>
> diff --git a/gcc/config/arm/arm.md b/gcc/config/arm/arm.md
> index 0be70a8..361c292 100644
> --- a/gcc/config/arm/arm.md
> +++ b/gcc/config/arm/arm.md
> @@ -3455,6 +3455,44 @@
>       (set_attr "type" "multiple,multiple")]
>    )
>
> +;; t = (s/u)min (x, y)
> +;; cc = cmp (t, z)
> +;; is the same as
> +;; cmp x, z
> +;; cmpge(u) y, z
> +
> +(define_insn_and_split "*arm_smin_cmp"
> +  [(set (reg:CC CC_REGNUM)
> +    (compare:CC
> +     (smin:SI (match_operand:SI 0 "s_register_operand" "r")
> +          (match_operand:SI 1 "s_register_operand" "r"))
> +     (match_operand:SI 2 "s_register_operand" "r")))]
> +  "TARGET_32BIT"
> +  "#"
> +  "&& reload_completed"
> +  [(set (reg:CC CC_REGNUM)
> +    (compare:CC (match_dup 0) (match_dup 2)))
> +   (cond_exec (ge:CC (reg:CC CC_REGNUM) (const_int 0))
> +          (set (reg:CC CC_REGNUM)
> +           (compare:CC (match_dup 1) (match_dup 2))))]
> +)
> +
> +(define_insn_and_split "*arm_umin_cmp"
> +  [(set (reg:CC CC_REGNUM)
> +    (compare:CC
> +     (umin:SI (match_operand:SI 0 "s_register_operand" "r")
> +          (match_operand:SI 1 "s_register_operand" "r"))
> +     (match_operand:SI 2 "s_register_operand" "r")))]
> +  "TARGET_32BIT"
> +  "#"
> +  "&& reload_completed"
> +  [(set (reg:CC CC_REGNUM)
> +    (compare:CC (match_dup 0) (match_dup 2)))
> +   (cond_exec (geu:CC (reg:CC CC_REGNUM) (const_int 0))
> +          (set (reg:CC CC_REGNUM)
> +           (compare:CC (match_dup 1) (match_dup 2))))]
> +)
> +
>    (define_expand "umaxsi3"
>      [(parallel [
>        (set (match_operand:SI 0 "s_register_operand" "")
> diff --git a/gcc/testsuite/gcc.target/arm/mincmp.c
> b/gcc/testsuite/gcc.target/arm/mincmp.c
> new file mode 100644
> index 0000000..2a55c6d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/arm/mincmp.c
> @@ -0,0 +1,18 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2" } */
> +/* { dg-require-effective-target arm32 } */
> +
> +#define min(x, y) ((x) <= (y)) ? (x) : (y)
> +
> +unsigned int foo (unsigned int i, unsigned int x ,unsigned int y)

Comma after "unsigned int x" in the wrong place.

> +{
> +  return i < (min (x, y));
> +}
> +
> +int bar (int i, int x, int y)
> +{
> +  return i < (min (x, y));
> +}

Can you please use GNU style for the testcase.
New line after return type, function name an arguments on their own line.

Ok with these changes.

Thanks,
Kyrill

Re: [ARM] Optimize compare against smin/umin

[Christophe Lyon]

Hi Michael,

It looks like this patch introduces regressions on armeb in:
gcc.dg/vect/vect-reduc-7.c
gcc.dg/vect/vect-reduc-8.c
gcc.dg/vect/vect-reduc-9.c

See http://people.linaro.org/~christophe.lyon/cross-validation/gcc/trunk/226476/report-build-info.html
for a bit more details.

Can you have a look?

Thanks,

Christophe.


On 27 July 2015 at 10:17, Kyrill Tkachov <kyrylo.tkachov@arm.com> wrote:
> Hi Michael,
>
> On 26/07/15 23:54, Michael Collison wrote:
>>
>> Here is an updated patch that addresses the issues you mentioned:
>>
>> 2015-07-24  Michael Collison  <michael.collison@linaro.org
>>                       Ramana Radhakrishnan <ramana.radhakrishnan@arm.com>
>>
>>                 * gcc/config/arm/arm.md (*arm_smin_cmp): New pattern.
>>                 (*arm_umin_cmp): Likewise.
>>                 * gcc.target/arm/mincmp.c: Test min compare idiom.
>
>
> Just "New test." would be a better ChangeLog entry for this.
>
>
>>
>> diff --git a/gcc/config/arm/arm.md b/gcc/config/arm/arm.md
>> index 0be70a8..361c292 100644
>> --- a/gcc/config/arm/arm.md
>> +++ b/gcc/config/arm/arm.md
>> @@ -3455,6 +3455,44 @@
>>       (set_attr "type" "multiple,multiple")]
>>    )
>>
>> +;; t = (s/u)min (x, y)
>> +;; cc = cmp (t, z)
>> +;; is the same as
>> +;; cmp x, z
>> +;; cmpge(u) y, z
>> +
>> +(define_insn_and_split "*arm_smin_cmp"
>> +  [(set (reg:CC CC_REGNUM)
>> +    (compare:CC
>> +     (smin:SI (match_operand:SI 0 "s_register_operand" "r")
>> +          (match_operand:SI 1 "s_register_operand" "r"))
>> +     (match_operand:SI 2 "s_register_operand" "r")))]
>> +  "TARGET_32BIT"
>> +  "#"
>> +  "&& reload_completed"
>> +  [(set (reg:CC CC_REGNUM)
>> +    (compare:CC (match_dup 0) (match_dup 2)))
>> +   (cond_exec (ge:CC (reg:CC CC_REGNUM) (const_int 0))
>> +          (set (reg:CC CC_REGNUM)
>> +           (compare:CC (match_dup 1) (match_dup 2))))]
>> +)
>> +
>> +(define_insn_and_split "*arm_umin_cmp"
>> +  [(set (reg:CC CC_REGNUM)
>> +    (compare:CC
>> +     (umin:SI (match_operand:SI 0 "s_register_operand" "r")
>> +          (match_operand:SI 1 "s_register_operand" "r"))
>> +     (match_operand:SI 2 "s_register_operand" "r")))]
>> +  "TARGET_32BIT"
>> +  "#"
>> +  "&& reload_completed"
>> +  [(set (reg:CC CC_REGNUM)
>> +    (compare:CC (match_dup 0) (match_dup 2)))
>> +   (cond_exec (geu:CC (reg:CC CC_REGNUM) (const_int 0))
>> +          (set (reg:CC CC_REGNUM)
>> +           (compare:CC (match_dup 1) (match_dup 2))))]
>> +)
>> +
>>    (define_expand "umaxsi3"
>>      [(parallel [
>>        (set (match_operand:SI 0 "s_register_operand" "")
>> diff --git a/gcc/testsuite/gcc.target/arm/mincmp.c
>> b/gcc/testsuite/gcc.target/arm/mincmp.c
>> new file mode 100644
>> index 0000000..2a55c6d
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.target/arm/mincmp.c
>> @@ -0,0 +1,18 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2" } */
>> +/* { dg-require-effective-target arm32 } */
>> +
>> +#define min(x, y) ((x) <= (y)) ? (x) : (y)
>> +
>> +unsigned int foo (unsigned int i, unsigned int x ,unsigned int y)
>
>
> Comma after "unsigned int x" in the wrong place.
>
>> +{
>> +  return i < (min (x, y));
>> +}
>> +
>> +int bar (int i, int x, int y)
>> +{
>> +  return i < (min (x, y));
>> +}
>
>
> Can you please use GNU style for the testcase.
> New line after return type, function name an arguments on their own line.
>
> Ok with these changes.
>
> Thanks,
> Kyrill
>