Why does combine turn zero_extract into lshiftrf?

Why does combine turn zero_extract into lshiftrf?

[H.J. Lu]

On Tue, Jun 22, 2010 at 11:05 AM, Uros Bizjak <ubizjak@gmail.com> wrote:
> On Mon, 2010-06-21 at 12:33 -0700, H.J. Lu wrote:
>> Hi,
>>
>> This patch adds 8bit divmov pattern for x86. X86 8bit divide
>> instructions return result in AX with
>>
>> AL <- Quotient
>> AH <- Remainder
>>
>> This patch models it and properly extends quotient. Tested
>> on Intel64 with -m64 and -m32.  There are no regressions.
>> OK for trunk?
>>
>> BTW, there is only one divb used in subreg_get_info in
>> gcc compilers. The old code is
>>
>>         movzbl  mode_size(%r13), %edi
>>         movzbl  mode_size(%r14), %esi
>>         xorl    %edx, %edx
>>         movl    %edi, %eax
>>         divw    %si
>>         testw   %dx, %dx
>>         jne     .L1194
>>
>> The new one is
>>
>>         movzbl  mode_size(%r13), %edi
>>         movl    %edi, %eax
>>         divb    mode_size(%r14)
>>         movzbl  %ah, %eax
>>         testb   %al, %al
>>         jne     .L1194
>>
>
> Hm, something is not combined correctly, I'd say "testb %ah, %ah" is
> optimal in the second case.
>
> Uros.
>
>

For some reason, combine tries to turn

(insn 11 10 13 2 umod-6.c:4 (set (reg:QI 67)
        (subreg:QI (zero_extract:SI (reg:HI 69)
                (const_int 8 [0x8])
                (const_int 8 [0x8])) 0)) 91 {*movqi_extzv_2_rex64}
(expr_list:REG_DEAD (reg:HI 69)
        (nil)))

(insn 13 11 14 2 umod-6.c:4 (set (reg:CCZ 17 flags)
        (compare:CCZ (reg:QI 67)
            (const_int 0 [0]))) 0 {*cmpqi_ccno_1} (expr_list:REG_DEAD
(reg:QI 67)
        (nil)))

into

(set (reg:CCZ 17 flags)
    (compare:CCZ (subreg:QI (lshiftrt:SI (subreg:SI (reg:HI 69) 0)
                (const_int 8 [0x8])) 0)
        (const_int 0 [0])))


i386.md doesn't have such pattern..

-- 
H.J.

Re: Why does combine turn zero_extract into lshiftrf?

[Jeff Law]

On 06/23/10 16:44, H.J. Lu wrote:
> On Tue, Jun 22, 2010 at 11:05 AM, Uros Bizjak<ubizjak@gmail.com>  wrote:
>    
>> On Mon, 2010-06-21 at 12:33 -0700, H.J. Lu wrote:
>>      
>>> Hi,
>>>
>>> This patch adds 8bit divmov pattern for x86. X86 8bit divide
>>> instructions return result in AX with
>>>
>>> AL<- Quotient
>>> AH<- Remainder
>>>
>>> This patch models it and properly extends quotient. Tested
>>> on Intel64 with -m64 and -m32.  There are no regressions.
>>> OK for trunk?
>>>
>>> BTW, there is only one divb used in subreg_get_info in
>>> gcc compilers. The old code is
>>>
>>>          movzbl  mode_size(%r13), %edi
>>>          movzbl  mode_size(%r14), %esi
>>>          xorl    %edx, %edx
>>>          movl    %edi, %eax
>>>          divw    %si
>>>          testw   %dx, %dx
>>>          jne     .L1194
>>>
>>> The new one is
>>>
>>>          movzbl  mode_size(%r13), %edi
>>>          movl    %edi, %eax
>>>          divb    mode_size(%r14)
>>>          movzbl  %ah, %eax
>>>          testb   %al, %al
>>>          jne     .L1194
>>>
>>>        
>> Hm, something is not combined correctly, I'd say "testb %ah, %ah" is
>> optimal in the second case.
>>
>> Uros.
>>
>>
>>      
> For some reason, combine tries to turn
>
> (insn 11 10 13 2 umod-6.c:4 (set (reg:QI 67)
>          (subreg:QI (zero_extract:SI (reg:HI 69)
>                  (const_int 8 [0x8])
>                  (const_int 8 [0x8])) 0)) 91 {*movqi_extzv_2_rex64}
> (expr_list:REG_DEAD (reg:HI 69)
>          (nil)))
>
> (insn 13 11 14 2 umod-6.c:4 (set (reg:CCZ 17 flags)
>          (compare:CCZ (reg:QI 67)
>              (const_int 0 [0]))) 0 {*cmpqi_ccno_1} (expr_list:REG_DEAD
> (reg:QI 67)
>          (nil)))
>
> into
>
> (set (reg:CCZ 17 flags)
>      (compare:CCZ (subreg:QI (lshiftrt:SI (subreg:SI (reg:HI 69) 0)
>                  (const_int 8 [0x8])) 0)
>          (const_int 0 [0])))
>    
I believe that's standard form within combine.c

jeff

Re: Why does combine turn zero_extract into lshiftrf?

[H.J. Lu]

On Thu, Jun 24, 2010 at 10:28 AM, Jeff Law <law@redhat.com> wrote:
> On 06/23/10 16:44, H.J. Lu wrote:
>>
>> On Tue, Jun 22, 2010 at 11:05 AM, Uros Bizjak<ubizjak@gmail.com>  wrote:
>>
>>>
>>> On Mon, 2010-06-21 at 12:33 -0700, H.J. Lu wrote:
>>>
>>>>
>>>> Hi,
>>>>
>>>> This patch adds 8bit divmov pattern for x86. X86 8bit divide
>>>> instructions return result in AX with
>>>>
>>>> AL<- Quotient
>>>> AH<- Remainder
>>>>
>>>> This patch models it and properly extends quotient. Tested
>>>> on Intel64 with -m64 and -m32.  There are no regressions.
>>>> OK for trunk?
>>>>
>>>> BTW, there is only one divb used in subreg_get_info in
>>>> gcc compilers. The old code is
>>>>
>>>>         movzbl  mode_size(%r13), %edi
>>>>         movzbl  mode_size(%r14), %esi
>>>>         xorl    %edx, %edx
>>>>         movl    %edi, %eax
>>>>         divw    %si
>>>>         testw   %dx, %dx
>>>>         jne     .L1194
>>>>
>>>> The new one is
>>>>
>>>>         movzbl  mode_size(%r13), %edi
>>>>         movl    %edi, %eax
>>>>         divb    mode_size(%r14)
>>>>         movzbl  %ah, %eax
>>>>         testb   %al, %al
>>>>         jne     .L1194
>>>>
>>>>
>>>
>>> Hm, something is not combined correctly, I'd say "testb %ah, %ah" is
>>> optimal in the second case.
>>>
>>> Uros.
>>>
>>>
>>>
>>
>> For some reason, combine tries to turn
>>
>> (insn 11 10 13 2 umod-6.c:4 (set (reg:QI 67)
>>         (subreg:QI (zero_extract:SI (reg:HI 69)
>>                 (const_int 8 [0x8])
>>                 (const_int 8 [0x8])) 0)) 91 {*movqi_extzv_2_rex64}
>> (expr_list:REG_DEAD (reg:HI 69)
>>         (nil)))
>>
>> (insn 13 11 14 2 umod-6.c:4 (set (reg:CCZ 17 flags)
>>         (compare:CCZ (reg:QI 67)
>>             (const_int 0 [0]))) 0 {*cmpqi_ccno_1} (expr_list:REG_DEAD
>> (reg:QI 67)
>>         (nil)))
>>
>> into
>>
>> (set (reg:CCZ 17 flags)
>>     (compare:CCZ (subreg:QI (lshiftrt:SI (subreg:SI (reg:HI 69) 0)
>>                 (const_int 8 [0x8])) 0)
>>         (const_int 0 [0])))
>>
>
> I believe that's standard form within combine.c
>

So backend has to provide lshiftrt patterns for combiner.

Uros, i386.md has patterns like

(define_insn "*cmpqi_ext_1"
  [(set (reg FLAGS_REG)
        (compare
          (match_operand:QI 0 "general_operand" "Qm")
          (subreg:QI
            (zero_extract:SI
              (match_operand 1 "ext_register_operand" "Q")
              (const_int 8)
              (const_int 8)) 0)))]
  "!TARGET_64BIT && ix86_match_ccmode (insn, CCmode)"
  "cmp{b}\t{%h1, %0|%0, %h1}"
  [(set_attr "type" "icmp")
   (set_attr "mode" "QI")])

Combiner won't match them since they don't use lshiftrt.
What are they used for?


-- 
H.J.

Re: Why does combine turn zero_extract into lshiftrf?

[Jeff Law]

On 06/24/10 11:38, H.J. Lu wrote:
> On Thu, Jun 24, 2010 at 10:28 AM, Jeff Law<law@redhat.com>  wrote:
>    
>> On 06/23/10 16:44, H.J. Lu wrote:
>>      
>>> On Tue, Jun 22, 2010 at 11:05 AM, Uros Bizjak<ubizjak@gmail.com>    wrote:
>>>
>>>        
>>>> On Mon, 2010-06-21 at 12:33 -0700, H.J. Lu wrote:
>>>>
>>>>          
>>>>> Hi,
>>>>>
>>>>> This patch adds 8bit divmov pattern for x86. X86 8bit divide
>>>>> instructions return result in AX with
>>>>>
>>>>> AL<- Quotient
>>>>> AH<- Remainder
>>>>>
>>>>> This patch models it and properly extends quotient. Tested
>>>>> on Intel64 with -m64 and -m32.  There are no regressions.
>>>>> OK for trunk?
>>>>>
>>>>> BTW, there is only one divb used in subreg_get_info in
>>>>> gcc compilers. The old code is
>>>>>
>>>>>          movzbl  mode_size(%r13), %edi
>>>>>          movzbl  mode_size(%r14), %esi
>>>>>          xorl    %edx, %edx
>>>>>          movl    %edi, %eax
>>>>>          divw    %si
>>>>>          testw   %dx, %dx
>>>>>          jne     .L1194
>>>>>
>>>>> The new one is
>>>>>
>>>>>          movzbl  mode_size(%r13), %edi
>>>>>          movl    %edi, %eax
>>>>>          divb    mode_size(%r14)
>>>>>          movzbl  %ah, %eax
>>>>>          testb   %al, %al
>>>>>          jne     .L1194
>>>>>
>>>>>
>>>>>            
>>>> Hm, something is not combined correctly, I'd say "testb %ah, %ah" is
>>>> optimal in the second case.
>>>>
>>>> Uros.
>>>>
>>>>
>>>>
>>>>          
>>> For some reason, combine tries to turn
>>>
>>> (insn 11 10 13 2 umod-6.c:4 (set (reg:QI 67)
>>>          (subreg:QI (zero_extract:SI (reg:HI 69)
>>>                  (const_int 8 [0x8])
>>>                  (const_int 8 [0x8])) 0)) 91 {*movqi_extzv_2_rex64}
>>> (expr_list:REG_DEAD (reg:HI 69)
>>>          (nil)))
>>>
>>> (insn 13 11 14 2 umod-6.c:4 (set (reg:CCZ 17 flags)
>>>          (compare:CCZ (reg:QI 67)
>>>              (const_int 0 [0]))) 0 {*cmpqi_ccno_1} (expr_list:REG_DEAD
>>> (reg:QI 67)
>>>          (nil)))
>>>
>>> into
>>>
>>> (set (reg:CCZ 17 flags)
>>>      (compare:CCZ (subreg:QI (lshiftrt:SI (subreg:SI (reg:HI 69) 0)
>>>                  (const_int 8 [0x8])) 0)
>>>          (const_int 0 [0])))
>>>
>>>        
>> I believe that's standard form within combine.c
>>
>>      
> So backend has to provide lshiftrt patterns for combiner.
>    
Not necessarily.  It's an internal form to make the rest of combine 
simpler.  Combine generally knows how to move in/out of those canonical 
forms.

Jeff

Re: Why does combine turn zero_extract into lshiftrf?

[H.J. Lu]

On Thu, Jun 24, 2010 at 10:42 AM, Jeff Law <law@redhat.com> wrote:
> On 06/24/10 11:38, H.J. Lu wrote:
>>
>> On Thu, Jun 24, 2010 at 10:28 AM, Jeff Law<law@redhat.com>  wrote:
>>
>>>
>>> On 06/23/10 16:44, H.J. Lu wrote:
>>>
>>>>
>>>> On Tue, Jun 22, 2010 at 11:05 AM, Uros Bizjak<ubizjak@gmail.com>
>>>>  wrote:
>>>>
>>>>
>>>>>
>>>>> On Mon, 2010-06-21 at 12:33 -0700, H.J. Lu wrote:
>>>>>
>>>>>
>>>>>>
>>>>>> Hi,
>>>>>>
>>>>>> This patch adds 8bit divmov pattern for x86. X86 8bit divide
>>>>>> instructions return result in AX with
>>>>>>
>>>>>> AL<- Quotient
>>>>>> AH<- Remainder
>>>>>>
>>>>>> This patch models it and properly extends quotient. Tested
>>>>>> on Intel64 with -m64 and -m32.  There are no regressions.
>>>>>> OK for trunk?
>>>>>>
>>>>>> BTW, there is only one divb used in subreg_get_info in
>>>>>> gcc compilers. The old code is
>>>>>>
>>>>>>         movzbl  mode_size(%r13), %edi
>>>>>>         movzbl  mode_size(%r14), %esi
>>>>>>         xorl    %edx, %edx
>>>>>>         movl    %edi, %eax
>>>>>>         divw    %si
>>>>>>         testw   %dx, %dx
>>>>>>         jne     .L1194
>>>>>>
>>>>>> The new one is
>>>>>>
>>>>>>         movzbl  mode_size(%r13), %edi
>>>>>>         movl    %edi, %eax
>>>>>>         divb    mode_size(%r14)
>>>>>>         movzbl  %ah, %eax
>>>>>>         testb   %al, %al
>>>>>>         jne     .L1194
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>> Hm, something is not combined correctly, I'd say "testb %ah, %ah" is
>>>>> optimal in the second case.
>>>>>
>>>>> Uros.
>>>>>
>>>>>
>>>>>
>>>>>
>>>>
>>>> For some reason, combine tries to turn
>>>>
>>>> (insn 11 10 13 2 umod-6.c:4 (set (reg:QI 67)
>>>>         (subreg:QI (zero_extract:SI (reg:HI 69)
>>>>                 (const_int 8 [0x8])
>>>>                 (const_int 8 [0x8])) 0)) 91 {*movqi_extzv_2_rex64}
>>>> (expr_list:REG_DEAD (reg:HI 69)
>>>>         (nil)))
>>>>
>>>> (insn 13 11 14 2 umod-6.c:4 (set (reg:CCZ 17 flags)
>>>>         (compare:CCZ (reg:QI 67)
>>>>             (const_int 0 [0]))) 0 {*cmpqi_ccno_1} (expr_list:REG_DEAD
>>>> (reg:QI 67)
>>>>         (nil)))
>>>>
>>>> into
>>>>
>>>> (set (reg:CCZ 17 flags)
>>>>     (compare:CCZ (subreg:QI (lshiftrt:SI (subreg:SI (reg:HI 69) 0)
>>>>                 (const_int 8 [0x8])) 0)
>>>>         (const_int 0 [0])))
>>>>
>>>>
>>>
>>> I believe that's standard form within combine.c
>>>
>>>
>>
>> So backend has to provide lshiftrt patterns for combiner.
>>
>
> Not necessarily.  It's an internal form to make the rest of combine simpler.
>  Combine generally knows how to move in/out of those canonical forms.
>
> Jeff
>
>

I opened:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44659

to track it.


-- 
H.J.

Re: Why does combine turn zero_extract into lshiftrf?

[Uros Bizjak]

On Thu, 2010-06-24 at 10:38 -0700, H.J. Lu wrote:

> >> For some reason, combine tries to turn
> >>
> >> (insn 11 10 13 2 umod-6.c:4 (set (reg:QI 67)
> >>         (subreg:QI (zero_extract:SI (reg:HI 69)
> >>                 (const_int 8 [0x8])
> >>                 (const_int 8 [0x8])) 0)) 91 {*movqi_extzv_2_rex64}
> >> (expr_list:REG_DEAD (reg:HI 69)
> >>         (nil)))
> >>
> >> (insn 13 11 14 2 umod-6.c:4 (set (reg:CCZ 17 flags)
> >>         (compare:CCZ (reg:QI 67)
> >>             (const_int 0 [0]))) 0 {*cmpqi_ccno_1} (expr_list:REG_DEAD
> >> (reg:QI 67)
> >>         (nil)))
> >>
> >> into
> >>
> >> (set (reg:CCZ 17 flags)
> >>     (compare:CCZ (subreg:QI (lshiftrt:SI (subreg:SI (reg:HI 69) 0)
> >>                 (const_int 8 [0x8])) 0)
> >>         (const_int 0 [0])))
> >>
> >
> > I believe that's standard form within combine.c
> >
> 
> So backend has to provide lshiftrt patterns for combiner.
> 
> Uros, i386.md has patterns like
> 
> (define_insn "*cmpqi_ext_1"
>   [(set (reg FLAGS_REG)
>         (compare
>           (match_operand:QI 0 "general_operand" "Qm")
>           (subreg:QI
>             (zero_extract:SI
>               (match_operand 1 "ext_register_operand" "Q")
>               (const_int 8)
>               (const_int 8)) 0)))]
>   "!TARGET_64BIT && ix86_match_ccmode (insn, CCmode)"
>   "cmp{b}\t{%h1, %0|%0, %h1}"
>   [(set_attr "type" "icmp")
>    (set_attr "mode" "QI")])
> 
> Combiner won't match them since they don't use lshiftrt.
> What are they used for?

This RTX predates my involvement with gcc, but perhaps it was useful
some time ago, before various RTX simplifications were introduced.
Anyway, looking into _.combine dump, you should be able to figure out
what is the canonical-form-of-the-moment RTX for various combined
patterns.  To complicate things a bit, there are several CC modes that
are compatible through ix86_match_ccmode checking, i.e. CCZmode with
CCNOmode.

Uros.

Re: Why does combine turn zero_extract into lshiftrf?

[H.J. Lu]

On Thu, Jun 24, 2010 at 10:42 AM, Jeff Law <law@redhat.com> wrote:
> On 06/24/10 11:38, H.J. Lu wrote:
>>
>> On Thu, Jun 24, 2010 at 10:28 AM, Jeff Law<law@redhat.com>  wrote:
>>
>>>
>>> On 06/23/10 16:44, H.J. Lu wrote:
>>>
>>>>
>>>> On Tue, Jun 22, 2010 at 11:05 AM, Uros Bizjak<ubizjak@gmail.com>
>>>>  wrote:
>>>>
>>>>
>>>>>
>>>>> On Mon, 2010-06-21 at 12:33 -0700, H.J. Lu wrote:
>>>>>
>>>>>
>>>>>>
>>>>>> Hi,
>>>>>>
>>>>>> This patch adds 8bit divmov pattern for x86. X86 8bit divide
>>>>>> instructions return result in AX with
>>>>>>
>>>>>> AL<- Quotient
>>>>>> AH<- Remainder
>>>>>>
>>>>>> This patch models it and properly extends quotient. Tested
>>>>>> on Intel64 with -m64 and -m32.  There are no regressions.
>>>>>> OK for trunk?
>>>>>>
>>>>>> BTW, there is only one divb used in subreg_get_info in
>>>>>> gcc compilers. The old code is
>>>>>>
>>>>>>         movzbl  mode_size(%r13), %edi
>>>>>>         movzbl  mode_size(%r14), %esi
>>>>>>         xorl    %edx, %edx
>>>>>>         movl    %edi, %eax
>>>>>>         divw    %si
>>>>>>         testw   %dx, %dx
>>>>>>         jne     .L1194
>>>>>>
>>>>>> The new one is
>>>>>>
>>>>>>         movzbl  mode_size(%r13), %edi
>>>>>>         movl    %edi, %eax
>>>>>>         divb    mode_size(%r14)
>>>>>>         movzbl  %ah, %eax
>>>>>>         testb   %al, %al
>>>>>>         jne     .L1194
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>> Hm, something is not combined correctly, I'd say "testb %ah, %ah" is
>>>>> optimal in the second case.
>>>>>
>>>>> Uros.
>>>>>
>>>>>
>>>>>
>>>>>
>>>>
>>>> For some reason, combine tries to turn
>>>>
>>>> (insn 11 10 13 2 umod-6.c:4 (set (reg:QI 67)
>>>>         (subreg:QI (zero_extract:SI (reg:HI 69)
>>>>                 (const_int 8 [0x8])
>>>>                 (const_int 8 [0x8])) 0)) 91 {*movqi_extzv_2_rex64}
>>>> (expr_list:REG_DEAD (reg:HI 69)
>>>>         (nil)))
>>>>
>>>> (insn 13 11 14 2 umod-6.c:4 (set (reg:CCZ 17 flags)
>>>>         (compare:CCZ (reg:QI 67)
>>>>             (const_int 0 [0]))) 0 {*cmpqi_ccno_1} (expr_list:REG_DEAD
>>>> (reg:QI 67)
>>>>         (nil)))
>>>>
>>>> into
>>>>
>>>> (set (reg:CCZ 17 flags)
>>>>     (compare:CCZ (subreg:QI (lshiftrt:SI (subreg:SI (reg:HI 69) 0)
>>>>                 (const_int 8 [0x8])) 0)
>>>>         (const_int 0 [0])))
>>>>
>>>>
>>>
>>> I believe that's standard form within combine.c
>>>
>>>
>>
>> So backend has to provide lshiftrt patterns for combiner.
>>
>
> Not necessarily.  It's an internal form to make the rest of combine simpler.
>  Combine generally knows how to move in/out of those canonical forms.
>

Apparently not. Combiner never tries zero_extract for the testcase
in

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44659

Also lshiftrt can't replace zero_extract on destination. Is
that possible for combiner to try zero_extract on

(insn 11 10 13 2 umod-4.c:4 (set (reg:QI 67)
        (subreg:QI (zero_extract:SI (reg:HI 69)
                (const_int 8 [0x8])
                (const_int 8 [0x8])) 0)) 90 {*movqi_extzv_2_rex64}
(expr_list:REG_DEAD (reg:HI 69)
        (expr_list:REG_EQUAL (umod:QI (reg/v:QI 61 [ x ])
                (reg/v:QI 63 [ y ]))
            (nil))))

(insn 13 11 14 2 umod-4.c:4 (set (reg:CCZ 17 flags)
        (compare:CCZ (reg:QI 67)
            (const_int 0 [0]))) 0 {*cmpqi_ccno_1} (expr_list:REG_DEAD (reg:QI
67)
        (nil)))


-- 
H.J.