[Bug target/63949] New: Aarch64 instruction combiner does not optimize subsi_sxth function as expected

[Bug target/63949] New: Aarch64 instruction combiner does not optimize subsi_sxth function as expected

[vekumar at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63949

            Bug ID: 63949
           Summary: Aarch64 instruction combiner does not optimize
                    subsi_sxth function as expected
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: target
          Assignee: unassigned at gcc dot gnu.org
          Reporter: vekumar at gcc dot gnu.org

Reference: https://bugs.linaro.org/show_bug.cgi?id=863

Test case 

int   subsi_sxth (int a, short  i)
{
  /* { dg-final { scan-assembler "sub\tw\[0-9\]+,.*sxth #?1" } } */
  return a - ((int)i << 1);
}

Assembly generated with GCC 5.0.0 20141114

subsi_sxth:
        sbfiz   w1, w1, 1, 16
        sub     w0, w0, w1
        ret

Expected 
       subw    w0,w0,w1,sxth 1


Combiner Says Failed to mismatch 

set (reg/i:SI 0 x0)
    (minus:SI (reg:SI 0 x0 [ a ])
        (subreg:SI (sign_extract:DI (mult:DI (reg:DI 1 x1 [ i ])
                    (const_int 2 [0x2]))
                (const_int 17 [0x11])
                (const_int 0 [0])) 0)))

We have a pattern that would match in aarch64.md file, but it is not
recognized.

(define_insn "*sub_<optab><mode>_multp2"
   [(set (match_operand:GPI 0 "register_operand" "=rk")
         (minus:GPI (match_operand:GPI 4 "register_operand" "r")
                    (ANY_EXTRACT:GPI
                     (mult:GPI (match_operand:GPI 1 "register_operand" "r")
                               (match_operand 2 "aarch64_pwr_imm3" "Up3"))
                     (match_operand 3 "const_int_operand" "n")
                     (const_int 0))))]
   "aarch64_is_extend_from_extract (<MODE>mode, operands[2], operands[3])"
   "sub\\t%<w>0, %<w>4, %<w>1, <su>xt%e3 %p2"
   [(set_attr "type" "alu_ext")]
 )

[Bug target/63949] Aarch64 instruction combiner does not optimize subsi_sxth function as expected

[ktkachov at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63949

ktkachov at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
             Target|                            |aarch64*
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-11-19
                 CC|                            |ktkachov at gcc dot gnu.org
     Ever confirmed|0                           |1
      Known to fail|                            |4.8.4, 4.9.2, 5.0

--- Comment #1 from ktkachov at gcc dot gnu.org ---
Confirmed. Also, I see it failing on 4.9.2 and 4.8.4 as well. Has this ever
worked?

[Bug target/63949] Aarch64 instruction combiner does not optimize subsi_sxth function as expected

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63949

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to ktkachov from comment #1)
> Confirmed. Also, I see it failing on 4.9.2 and 4.8.4 as well. Has this ever
> worked?

No I have never seen it work.

[Bug target/63949] Aarch64 instruction combiner does not optimize subsi_sxth function as expected (gcc.target/aarch64/extend.c fails)

[rearnsha at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63949

--- Comment #3 from Richard Earnshaw <rearnsha at gcc dot gnu.org> ---
make_extraction is unable to generate bit-field extractions in more than one
mode.  This causes the extractions that it does generate to be wrapped in
subregs when SImode results are wanted.

Ideally, we should teach make_extraction to be more sensible, but I'm not sure
what the impact of that would be on other ports that really can only support
one mode for bit-field extracts.

[Bug target/63949] Aarch64 instruction combiner does not optimize subsi_sxth function as expected (gcc.target/aarch64/extend.c fails)

[vekumar at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63949

--- Comment #4 from vekumar at gcc dot gnu.org ---
(In reply to Richard Earnshaw from comment #3)
> make_extraction is unable to generate bit-field extractions in more than one
> mode.  This causes the extractions that it does generate to be wrapped in
> subregs when SImode results are wanted.
> 
> Ideally, we should teach make_extraction to be more sensible, but I'm not
> sure what the impact of that would be on other ports that really can only
> support one mode for bit-field extracts.

Yes, make_extraction converts mult to sign extract RTL.

RTL from (mult: SI (reg: SI 1 x1 [i])
              ( constant_int 2 [0x2]))

to 

(subreg: SI (sign_extract: DI (ashift: DI (reg DI 1 x1 [i]) 
                                      (constant_int 1 [0x1]))
                              (constant_int 17 [0x11]))
            (constant_int 0 [0x0]))

[Bug target/63949] Aarch64 instruction combiner does not optimize subsi_sxth function as expected (gcc.target/aarch64/extend.c fails)

[vekumar at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63949

--- Comment #5 from vekumar at gcc dot gnu.org ---
Richard, what the function get_best_reg_extraction_insn is supposed to do in
make_extraction ?

[Bug target/63949] Aarch64 instruction combiner does not optimize subsi_sxth function as expected (gcc.target/aarch64/extend.c fails)

[vekumar at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63949

--- Comment #6 from vekumar at gcc dot gnu.org ---
In the function make_compound_operation, there a check 

      /* See if we have operations between an ASHIFTRT and an ASHIFT.
         If so, try to merge the shifts into a SIGN_EXTEND.  We could
         also do this for some cases of SIGN_EXTRACT, but it doesn't
         seem worth the effort; the case checked for occurs on Alpha.          
*/

if (!OBJECT_P (lhs)
          && ! (GET_CODE (lhs) == SUBREG
                && (OBJECT_P (SUBREG_REG (lhs))))
          && CONST_INT_P (rhs)
          && INTVAL (rhs) < HOST_BITS_PER_WIDE_INT
          && INTVAL (rhs) < mode_width
          && (new_rtx = extract_left_shift (lhs, INTVAL (rhs))) != 0)
        new_rtx = make_extraction (mode, make_compound_operation (new_rtx,
next_code),
                               0, NULL_RTX, mode_width - INTVAL (rhs),
                               code == LSHIFTRT, 0, in_code == COMPARE);

      break;



Our input RTL actually matches this case. 

For (int)i << 1  we are getting incomming RTX as 

(ashiftrt:SI (ashift:SI (reg:SI 1 x1 [ i ])
        (const_int 16 [0x10]))
    (const_int 15 [0xf]))


LHS is ashift:SI (reg:SI 1 x1 [ i ])
        (const_int 16 [0x10]) 

RHS is ashiftrt with a value of 15.

So bacially we get (i<<16)>>15, we can merge these shifts to sign_extends.

With extract_left_shift we get 

(ashift:SI (reg:SI 1 x1 [ i ])
    (const_int 1 [0x1]))

or x1<<1

When we do make_extraction with this shift pattern we get 

    (ashift:SI (sign_extend:SI (reg:HI 1 x1 [ i ]))
        (const_int 1 [0x1])))


But instead this we are the shift RTX, we are actually passing MULT RTX to
make_extraction via another make_compound_operation.

p make_compound_operation(new_rtx,MEM)
$3 = (rtx_def *) 0x7ffff77fd420
(gdb) pr
(mult:SI (reg:SI 1 x1 [ i ])
    (const_int 2 [0x2]))

Which results in 

 (subreg:SI (sign_extract:DI (mult:DI (reg:DI 1 x1 [ i ])
                (const_int 2 [0x2]))
            (const_int 17 [0x11])
            (const_int 0 [0])) 0)

When I changed the original check to

--- a/gcc/combine.c
+++ b/gcc/combine.c
@@ -7896,7 +7896,7 @@ make_compound_operation (rtx x, enum rtx_code in_code)
          && INTVAL (rhs) < HOST_BITS_PER_WIDE_INT
          && INTVAL (rhs) < mode_width
          && (new_rtx = extract_left_shift (lhs, INTVAL (rhs))) != 0)
-       new_rtx = make_extraction (mode, make_compound_operation (new_rtx,
next_
+       new_rtx = make_extraction (mode, new_rtx,
                               0, NULL_RTX, mode_width - INTVAL (rhs),
                               code == LSHIFTRT, 0, in_code == COMPARE)

Combiner was able to match the pattern successfully.

Trying 8 -> 13:
Successfully matched this instruction:
(set (reg/i:SI 0 x0)
    (minus:SI (reg:SI 0 x0 [ a ])
        (ashift:SI (sign_extend:SI (reg:HI 1 x1 [ i ]))
            (const_int 1 [0x1]))))
(minus:SI (reg:SI 0 x0 [ a ])
    (ashift:SI (sign_extend:SI (reg:HI 1 x1 [ i ]))

Any comments about this change?
        (const_int 1 [0x1])))

[Bug target/63949] Aarch64 instruction combiner does not optimize subsi_sxth function as expected (gcc.target/aarch64/extend.c fails)

[vekumar at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63949

--- Comment #7 from vekumar at gcc dot gnu.org ---
I ran GCC tests against the patch found one failure. 

int
adds_shift_ext ( long long a, int b, int c)
{
 long long  d = (a + ((long long)b << 3));

  if (d == 0)
    return a + c;
  else
    return b + d + c;
}


The test expects adds generation and before my fix it is generated .
adds_shift_ext:
        adds    x3, x0, x1, sxtw 3      // 11   *adds_extvdi_multp2     [length
= 4]
        beq     .L5     // 12   *condjump       [length = 4]

But now I am generating sign extends with shifts instead of sign extends with
mul in my patch.

adds_shift_ext:
        add     x3, x0, x1, sxtw 3      // 10   *add_extendsi_shft_di   [length
= 4]
        cbz     x3, .L5 // 12   *cbeqdi1        [length = 4]

We don't have *adds_extendsi_shft_di pattern. We have patterns for
adds_extvdi_multp2 that extends an operation over mult.

Adding one will help optimize this case. But my concern is what if other
targets  hits the same issue?

[Bug target/63949] Aarch64 instruction combiner does not optimize subsi_sxth function as expected (gcc.target/aarch64/extend.c fails)

[vekumar at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63949

--- Comment #8 from vekumar at gcc dot gnu.org ---
This is complete patch for the first approach that I took (comment 6). This
patch fixes issues I faced while testing. But I have added extra patterns to
cater the sign extended operands with left shifts. This might impact other
targets as well :( 

Now I am also exploring other possibilities instead of writing extra patterns. 


diff --git a/gcc/combine.c b/gcc/combine.c
index ee7b3f9..80b345d 100644
--- a/gcc/combine.c
+++ b/gcc/combine.c
@@ -7896,7 +7896,7 @@ make_compound_operation (rtx x, enum rtx_code in_code)
          && INTVAL (rhs) < HOST_BITS_PER_WIDE_INT
          && INTVAL (rhs) < mode_width
          && (new_rtx = extract_left_shift (lhs, INTVAL (rhs))) != 0)
-       new_rtx = make_extraction (mode, make_compound_operation (new_rtx,
next_
+       new_rtx = make_extraction (mode, new_rtx,
                               0, NULL_RTX, mode_width - INTVAL (rhs),
                               code == LSHIFTRT, 0, in_code == COMPARE);

diff --git a/gcc/config/aarch64/aarch64.md b/gcc/config/aarch64/aarch64.md
index 97d7009..f0b9240 100644
--- a/gcc/config/aarch64/aarch64.md
+++ b/gcc/config/aarch64/aarch64.md
@@ -1570,26 +1570,62 @@
   [(set_attr "type" "alus_ext")]
 )

-(define_insn "*adds_<optab><mode>_multp2"
+(define_insn "*adds_<optab><mode>_extend_ashift"
   [(set (reg:CC_NZ CC_REGNUM)
        (compare:CC_NZ
-        (plus:GPI (ANY_EXTRACT:GPI
-                   (mult:GPI (match_operand:GPI 1 "register_operand" "r")
-                             (match_operand 2 "aarch64_pwr_imm3" "Up3"))
-                   (match_operand 3 "const_int_operand" "n")
-                   (const_int 0))
-                  (match_operand:GPI 4 "register_operand" "r"))
+        (plus:GPI (match_operand:GPI 1 "register_operand" "r")
+                  (ashift:GPI (ANY_EXTEND:GPI
+                                (match_operand:ALLX 2 "register_operand" "r"))
+                               (match_operand 3 "aarch64_imm3" "Ui3")))
        (const_int 0)))
    (set (match_operand:GPI 0 "register_operand" "=r")
-       (plus:GPI (ANY_EXTRACT:GPI (mult:GPI (match_dup 1) (match_dup 2))
-                                  (match_dup 3)
-                                  (const_int 0))
-                 (match_dup 4)))]
+       (plus:GPI  (match_dup 1) 
+                   (ashift:GPI (ANY_EXTEND:GPI (match_dup 2))
+                               (match_dup 3))))]
+  ""
+  "adds\\t%<w>0, %<w>1, %<w>2, <su>xt %3"
+  [(set_attr "type" "alus_ext")]
+)
+
+(define_insn "*subs_<optab><mode>_extend_ashift"
+  [(set (reg:CC_NZ CC_REGNUM)
+        (compare:CC_NZ
+         (minus:GPI (match_operand:GPI 1 "register_operand" "r")
+                    (ashift:GPI (ANY_EXTEND:GPI
+                                  (match_operand:ALLX 2 "register_operand"
"r")
+                                 (match_operand 3 "aarch64_imm3" "Ui3")))
+        (const_int 0)))
+   (set (match_operand:GPI 0 "register_operand" "=r")
+        (minus:GPI (match_dup 1)
+                   (ashift:GPI (ANY_EXTEND:GPI (match_dup 2))
+                                (match_dup 3))))]
+  ""
+  "subs\\t%<w>0, %<w>1, %<w>2, <su>xt %3"
+  [(set_attr "type" "alus_ext")]
+)
+
+
+(define_insn "*adds_<optab><mode>_multp2"
+  [(set (reg:CC_NZ CC_REGNUM)
+        (compare:CC_NZ
+         (plus:GPI (ANY_EXTRACT:GPI
+                    (mult:GPI (match_operand:GPI 1 "register_operand" "r")
+                              (match_operand 2 "aarch64_pwr_imm3" "Up3"))
+                    (match_operand 3 "const_int_operand" "n")
+                    (const_int 0))
+                   (match_operand:GPI 4 "register_operand" "r"))
+        (const_int 0)))
+   (set (match_operand:GPI 0 "register_operand" "=r")
+        (plus:GPI (ANY_EXTRACT:GPI (mult:GPI (match_dup 1) (match_dup 2))
+                                   (match_dup 3)
+                                   (const_int 0))
+                  (match_dup 4)))]
   "aarch64_is_extend_from_extract (<MODE>mode, operands[2], operands[3])"
   "adds\\t%<w>0, %<w>4, %<w>1, <su>xt%e3 %p2"
   [(set_attr "type" "alus_ext")]
 )

+
 (define_insn "*subs_<optab><mode>_multp2"
   [(set (reg:CC_NZ CC_REGNUM)
        (compare:CC_NZ

[Bug target/63949] Aarch64 instruction combiner does not optimize subsi_sxth function as expected (gcc.target/aarch64/extend.c fails)

[segher at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63949

Segher Boessenkool <segher at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |segher at gcc dot gnu.org

--- Comment #9 from Segher Boessenkool <segher at gcc dot gnu.org> ---
A MULT by a constant power of 2 is not canonical RTL (well, not what
simplify_rtx would give you); combine shouldn't generate this.

[Bug target/63949] Aarch64 instruction combiner does not optimize subsi_sxth function as expected (gcc.target/aarch64/extend.c fails)

[ramana at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63949

Ramana Radhakrishnan <ramana at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |ramana at gcc dot gnu.org

[Bug target/63949] Aarch64 instruction combiner does not optimize subsi_sxth function as expected (gcc.target/aarch64/extend.c fails)

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63949

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
https://gcc.gnu.org/ml/gcc-patches/2015-01/msg01020.html

[Bug target/63949] Aarch64 instruction combiner does not optimize subsi_sxth function as expected (gcc.target/aarch64/extend.c fails)

[vekumar at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63949

vekumar at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #12 from vekumar at gcc dot gnu.org ---
Fixed at r222874

 https://gcc.gnu.org/viewcvs/gcc?view=revision&revision=222874

2015-05-07  Venkataramanan Kumar  <venkataramanan.kumar@amd.com>

        * combine.c (make_compound_operation): Remove checks for PLUS/MINUS
        rtx type.