GCC won`t emit my instriction

GCC won`t emit my instriction

[Alex Hill via gcc-help]

I need to reduce amount of branches in code. There is exist benchmark called median it have some code like:
    if ( A < B )
            return A = foo[i];
        else
            return B = foo[i];
I wrote a pattern in machine description file *.md to avoid branches:
    (define_insn "smin<GPR:mode>3"
      [
        (set 
          (match_operand:GPR 0 "register_operand" "=r")
            (if_then_else:GPR
          (lt:GPR 
            (match_operand:GPR 1 "register_operand" " r")
            (match_operand:GPR 2 "register_operand" " r"))
        (match_dup 1)
        (match_dup 2)))
      ]
      ""
      "min\t%0,%1,%2"
      [(set_attr "type" "move")
       (set_attr "mode" "<MODE>")]) 
It works in case of simple comparison:
    if ( A < B )
            return A ;
        else
            return B;
GCC emit:
    min a0,a0,a1    # 9 smindi3 [length = 4]
    ret # 21    simple_return   [length = 4]
But if i try same, but with indexed variable( array ): it won`t works:
    if ( A < B )
            return A = foo[i];
        else
            return B = foo[i];
GCC emit:
    blt a0,a1,.L5   # 11    *branch_orderdi [length = 4]
    sd  a1,8(a2)    # 18    *movdi_64bit/4  [length = 4]
    mv  a0,a1   # 8 *movdi_64bit/1  [length = 4]
    ret # 34    simple_return   [length = 4]
    .L5:
    sd  a0,8(a2)    # 13    *movdi_64bit/4  [length = 4]
    ret # 28    simple_return   [length = 4]
I need to GCC emit something like this:
    min a0,a0,a1    # 9 smindi3 [length = 4]
    sd  a0,8(a2)    # 18    *movdi_64bit/4  [length = 4]
    ret # 34    simple_return   [length = 4]
I appreciate any help, and i desperate to find a desicion, i tried to look into GIMPLE to change conditions of MIN_EXPR, but there is no(almost) any documentation, and sources are VERY puzzling((


Kind regards Alex Hill.

Re: GCC won`t emit my instriction

[Jeff Law]

On 6/6/19 10:42 PM, Alex Hill via gcc-help wrote:
> 
> I need to reduce amount of branches in code. There is exist benchmark called median it have some code like:
>     if ( A < B )
>             return A = foo[i];
>         else
>             return B = foo[i];
> I wrote a pattern in machine description file *.md to avoid branches:
>     (define_insn "smin<GPR:mode>3"
>       [
>         (set 
>           (match_operand:GPR 0 "register_operand" "=r")
>             (if_then_else:GPR
>           (lt:GPR 
>             (match_operand:GPR 1 "register_operand" " r")
>             (match_operand:GPR 2 "register_operand" " r"))
>         (match_dup 1)
>         (match_dup 2)))
>       ]
>       ""
>       "min\t%0,%1,%2"
>       [(set_attr "type" "move")
>        (set_attr "mode" "<MODE>")]) 
> It works in case of simple comparison:
>     if ( A < B )
>             return A ;
>         else
>             return B;
> GCC emit:
>     min a0,a0,a1    # 9 smindi3 [length = 4]
>     ret # 21    simple_return   [length = 4]
> But if i try same, but with indexed variable( array ): it won`t works:
>     if ( A < B )
>             return A = foo[i];
>         else
>             return B = foo[i];
> GCC emit:
>     blt a0,a1,.L5   # 11    *branch_orderdi [length = 4]
>     sd  a1,8(a2)    # 18    *movdi_64bit/4  [length = 4]
>     mv  a0,a1   # 8 *movdi_64bit/1  [length = 4]
>     ret # 34    simple_return   [length = 4]
>     .L5:
>     sd  a0,8(a2)    # 13    *movdi_64bit/4  [length = 4]
>     ret # 28    simple_return   [length = 4]
> I need to GCC emit something like this:
>     min a0,a0,a1    # 9 smindi3 [length = 4]
>     sd  a0,8(a2)    # 18    *movdi_64bit/4  [length = 4]
>     ret # 34    simple_return   [length = 4]
> I appreciate any help, and i desperate to find a desicion, i tried to look into GIMPLE to change conditions of MIN_EXPR, but there is no(almost) any documentation, and sources are VERY puzzling((
Rather than using a match_dup which requires the exact same register
throughout the RTL pipeline, you might consider using a matching constraint.

    (define_insn "smin<GPR:mode>3"
      [
        (set
          (match_operand:GPR 0 "register_operand" "=r")
            (if_then_else:GPR
          (lt:GPR
            (match_operand:GPR 1 "register_operand" " r")
            (match_operand:GPR 2 "register_operand" " r"))
        (match_operand:GPR 3 "register_operand" "1")
        (match_operand:GPR 4 "register_operand" "2")))

I would also strongly recommnend reviewing the various dump files to see
if you're getting min/max as you leave gimple and if they're carried
through the RTL pipeline.

jeff

Re[2]: GCC won`t emit my instriction

[Alex Hill via gcc-help]

>Пятница,  7 июня 2019, 9:50 +05:00 от Jeff Law <law@redhat.com>:
>
>On 6/6/19 10:42 PM, Alex Hill via gcc-help wrote:
>> 
>> I need to reduce amount of branches in code. There is exist benchmark called median it have some code like:
>>     if ( A < B )
>>             return A = foo[i];
>>         else
>>             return B = foo[i];
>> I wrote a pattern in machine description file *.md to avoid branches:
>>     (define_insn "smin<GPR:mode>3"
>>       [
>>         (set 
>>           (match_operand:GPR 0 "register_operand" "=r")
>>             (if_then_else:GPR
>>           (lt:GPR 
>>             (match_operand:GPR 1 "register_operand" " r")
>>             (match_operand:GPR 2 "register_operand" " r"))
>>         (match_dup 1)
>>         (match_dup 2)))
>>       ]
>>       ""
>>       "min\t%0,%1,%2"
>>       [(set_attr "type" "move")
>>        (set_attr "mode" "<MODE>")]) 
>> It works in case of simple comparison:
>>     if ( A < B )
>>             return A ;
>>         else
>>             return B;
>> GCC emit:
>>     min a0,a0,a1    # 9 smindi3 [length = 4]
>>     ret # 21    simple_return   [length = 4]
>> But if i try same, but with indexed variable( array ): it won`t works:
>>     if ( A < B )
>>             return A = foo[i];
>>         else
>>             return B = foo[i];
>> GCC emit:
>>     blt a0,a1,.L5   # 11    *branch_orderdi [length = 4]
>>     sd  a1,8(a2)    # 18    *movdi_64bit/4  [length = 4]
>>     mv  a0,a1   # 8 *movdi_64bit/1  [length = 4]
>>     ret # 34    simple_return   [length = 4]
>>     .L5:
>>     sd  a0,8(a2)    # 13    *movdi_64bit/4  [length = 4]
>>     ret # 28    simple_return   [length = 4]
>> I need to GCC emit something like this:
>>     min a0,a0,a1    # 9 smindi3 [length = 4]
>>     sd  a0,8(a2)    # 18    *movdi_64bit/4  [length = 4]
>>     ret # 34    simple_return   [length = 4]
>> I appreciate any help, and i desperate to find a desicion, i tried to look into GIMPLE to change conditions of MIN_EXPR, but there is no(almost) any documentation, and sources are VERY puzzling((
>Rather than using a match_dup which requires the exact same register
>throughout the RTL pipeline, you might consider using a matching constraint.
>
>    (define_insn "smin<GPR:mode>3"
>      [
>        (set
>          (match_operand:GPR 0 "register_operand" "=r")
>            (if_then_else:GPR
>          (lt:GPR
>            (match_operand:GPR 1 "register_operand" " r")
>            (match_operand:GPR 2 "register_operand" " r"))
>        (match_operand:GPR 3 "register_operand" "1")
>        (match_operand:GPR 4 "register_operand" "2")))
>
>I would also strongly recommnend reviewing the various dump files to see
>if you're getting min/max as you leave gimple and if they're carried
>through the RTL pipeline.
>
>jeff
It won`t help of course, in GIMPLE direct comparisen gets

MIN_EXPR()

but indexed storing gets

long int _1;
<bb 2> [100.00%]:
if (A_3(D) < B_4(D))
goto <bb 3>; [46.00%]
else
goto <bb 4>; [54.00%]
<bb 3> [46.00%]:
MEM[(long int *)kekeke_5(D) + 8B] = A_3(D);
goto <bb 5>; [100.00%]
<bb 4> [54.00%]:
MEM[(long int *)kekeke_5(D) + 8B] = B_4(D);
<bb 5> [100.00%]:
# _1 = PHI <A_3(D)(3), B_4(D)(4)>
return _1;


Kind regards Alex Hill.

Re: GCC won`t emit my instriction

[Segher Boessenkool]

Hi Alex,

On Fri, Jun 07, 2019 at 07:42:26AM +0300, Alex Hill via gcc-help wrote:
> I wrote a pattern in machine description file *.md to avoid branches:
>     (define_insn "smin<GPR:mode>3"
>       [
>         (set 
>           (match_operand:GPR 0 "register_operand" "=r")
>             (if_then_else:GPR
>           (lt:GPR 
>             (match_operand:GPR 1 "register_operand" " r")
>             (match_operand:GPR 2 "register_operand" " r"))
>         (match_dup 1)
>         (match_dup 2)))
>       ]
>       ""
>       "min\t%0,%1,%2"
>       [(set_attr "type" "move")
>        (set_attr "mode" "<MODE>")]) 

You could just do

(define_insn "smin<mode>3"
  [(set (match_operand:GPR 0 "register_operand" "=r")
        (smin:GPR (match_operand:GPR 1 "register_operand" "r")
                  (match_operand:GPR 2 "register_operand" "r")))]
  ""
  "min\t%0,%1,%2"
  [(set_attr "type" "move")
   (set_attr "mode" "<MODE>")])

Does that work better?


Segher

Re[2]: GCC won`t emit my instriction

[Alex Hill via gcc-help]

>Пятница,  7 июня 2019, 21:34 +05:00 от Segher Boessenkool <segher@kernel.crashing.org>:
>
>Hi Alex,
>
>On Fri, Jun 07, 2019 at 07:42:26AM +0300, Alex Hill via gcc-help wrote:
>> I wrote a pattern in machine description file *.md to avoid branches:
>>     (define_insn "smin<GPR:mode>3"
>>       [
>>         (set 
>>           (match_operand:GPR 0 "register_operand" "=r")
>>             (if_then_else:GPR
>>           (lt:GPR 
>>             (match_operand:GPR 1 "register_operand" " r")
>>             (match_operand:GPR 2 "register_operand" " r"))
>>         (match_dup 1)
>>         (match_dup 2)))
>>       ]
>>       ""
>>       "min\t%0,%1,%2"
>>       [(set_attr "type" "move")
>>        (set_attr "mode" "<MODE>")]) 
>
>You could just do
>
>(define_insn "smin<mode>3"
>  [(set (match_operand:GPR 0 "register_operand" "=r")
>        (smin:GPR (match_operand:GPR 1 "register_operand" "r")
>                  (match_operand:GPR 2 "register_operand" "r")))]
>  ""
>  "min\t%0,%1,%2"
>  [(set_attr "type" "move")
>   (set_attr "mode" "<MODE>")])
>
>Does that work better?
>
>
>Segher
Of course i tried this before, but its not work.

I found some decision, i used flags -fexceptions -fnon-call-exceptions and it emits max insn, now i try to understand why this happens.
Here is the max it emits:
(define_insn "smax<GPR:mode>3"
    [(set (match_operand:GPR 0 "register_operand" "=r")
        (smax:GPR (match_operand:GPR 1 "register_operand" " r")
        (match_operand:GPR 2 "register_operand" " r")))]
""
"max\t%0,%1,%2"
[(set_attr "type" "move")
(set_attr "mode" "<MODE>")])

Kind regards Alex Hill.

Re: Re[2]: GCC won`t emit my instriction

[Jim Wilson]

On Sun, Jun 9, 2019 at 11:15 PM Alex Hill via gcc-help
<gcc-help@gcc.gnu.org> wrote:
> I found some decision, i used flags -fexceptions -fnon-call-exceptions and it emits max insn, now i try to understand why this happens.
> Here is the max it emits:
> (define_insn "smax<GPR:mode>3"
>     [(set (match_operand:GPR 0 "register_operand" "=r")
>         (smax:GPR (match_operand:GPR 1 "register_operand" " r")
>         (match_operand:GPR 2 "register_operand" " r")))]
> ""
> "max\t%0,%1,%2"
> [(set_attr "type" "move")
> (set_attr "mode" "<MODE>")])

There is some code in noce_try_minmax in ifcvt.c that will try to
recognize an if statement in RTL that performs min/max and try to
convert it to a direct min/max operation.  However, in general, you
are more likely to get a min/max operation if you recognize it when
parsing, and then carry it all of the way through the optimizer.  To
make that work, you need min/max named patterns, that emit min/max
operations in RTL.  Like what you have immediately above.  If trying
to understand how this works, look at the debugging dumps you can get
with -fdump-tree-all and -fdump-rtl-all when compiling a trivial
testcase.  And maybe compare with another CPU target that already has
working min/max support.

Jim

Re[4]: GCC won`t emit my instriction

[Alex Hill via gcc-help]

>Вторник, 11 июня 2019, 3:20 +05:00 от Jim Wilson <jimw@sifive.com>:
>
>On Sun, Jun 9, 2019 at 11:15 PM Alex Hill via gcc-help
>< gcc-help@gcc.gnu.org > wrote:
>> I found some decision, i used flags -fexceptions -fnon-call-exceptions and it emits max insn, now i try to understand why this happens.
>> Here is the max it emits:
>> (define_insn "smax<GPR:mode>3"
>>     [(set (match_operand:GPR 0 "register_operand" "=r")
>>         (smax:GPR (match_operand:GPR 1 "register_operand" " r")
>>         (match_operand:GPR 2 "register_operand" " r")))]
>> ""
>> "max\t%0,%1,%2"
>> [(set_attr "type" "move")
>> (set_attr "mode" "<MODE>")])
>
>There is some code in noce_try_minmax in ifcvt.c that will try to
>recognize an if statement in RTL that performs min/max and try to
>convert it to a direct min/max operation.  However, in general, you
>are more likely to get a min/max operation if you recognize it when
>parsing, and then carry it all of the way through the optimizer.  To
>make that work, you need min/max named patterns, that emit min/max
>operations in RTL.  Like what you have immediately above.  If trying
>to understand how this works, look at the debugging dumps you can get
>with -fdump-tree-all and -fdump-rtl-all when compiling a trivial
>testcase.  And maybe compare with another CPU target that already has
>working min/max support.
>
>Jim
What have i done for this moment:
I create some pattern:

(define_insn "<code><GPR:mode>3"
[(set (match_operand:GPR 0 "register_operand" "=r")
(any_maxmin:GPR (match_operand:GPR 1 "register_operand" " r")
(match_operand:GPR 2 "register_operand" " r")))]
""
"<maxmin>\t%0,%1,%2"
[(set_attr "type" "move")
(set_attr "mode" "<MODE>")])
It emit in case of indexed variables:

if ( A < C )
results[i] = A;
else if ( C < B )
results[i] = B;
else
results[i] = C; an assembler code:

.L15:
blt a4,a1,.L22
max 0(a2),a5,a1
ret
.L22:
sd a4,0(a2)
ret
.L21:
sd a5,0(a2)
ret

BUT! In case we using IF loop GCC wont emit minmax AGAIN!
for ( i = 1; i < (n-1); i++ ) {
A = input[i-1];
B = input[i];
C = input[i+1];
if ( A < B ) {
if ( B < C )
results[i] = B;
else if ( C < A )
results[i] = A;
else
results[i] = C;
}
else {
if ( A < C )
results[i] = A;
else if ( C < B )
results[i] = B;
else
results[i] = C;
}
}

Asembler code:

L3:
blt a4,a3,.L12
bgt a5,a3,.L11                 //instead of max
.L8:
sd a3,0(a2)
j .L5
.L11:
sd a5,0(a2)
j .L5 I supposed it happens because of this part:

(jump_insn 77 76 78 13 (set (pc)
(if_then_else (le (reg/v:DI 104 [ B ])
(reg/v:DI 105 [ C ]))
(label_ref 82)
(pc))) "./median/median1.c":58 -1
(int_list:REG_BR_PROB 5000 (nil))
-> 82)
(note 78 77 79 14 [bb 14] NOTE_INSN_BASIC_BLOCK)
(insn 79 78 80 14 (set (mem:DI (reg:DI 113 [ ivtmp.29 ]) [1 MEM[base: _39, offset: 0B]+0 S8 A64])       <----this part
(reg/v:DI 104 [ B ])) "./median/median1.c":59 -1
(nil))

what`s the difference between  

(reg:DI 113 [ ivtmp.29 ]) [1 MEM[base: _39, offset: 0B]+0 S8 A64])  

and (reg/f:DI 89 [ _48 ]) [1 *_48+0 S8 A64])

I can`t find meaning of ivtmp and MEM[base:_39,offset:0B]
Of course meaning in this case, i understand what mean "MEM" or "offset" or pointer.
In second string, same pointer + offset '*_48+0' statement.
Does anyone have any thoughts on this?

Sorry for my Engrish


Kind regards Alex Hill.

Re: Re[4]: GCC won`t emit my instriction

[Jim Wilson]

On Tue, Jun 11, 2019 at 1:32 AM Alex Hill <hardest2005@mail.ru> wrote:
> BUT! In case we using IF loop GCC wont emit minmax AGAIN!

It looks like the memory accesses are the problem, not the control
flow.  However, the control flow may be affecting exactly how the
compiler optimizes the memory references.  If you create a temporary
variable, store the result in the temporary variable, and then write
the temporary variable to memory at the end, it should be optimized
regardless of control flow.

> what`s the difference between
> (reg:DI 113 [ ivtmp.29 ]) [1 MEM[base: _39, offset: 0B]+0 S8 A64])
> and
> (reg/f:DI 89 [ _48 ]) [1 *_48+0 S8 A64])

_ivtmp.29 and _48 are variable names.  In both cases, these are
variable names created by high level optimization passes.  See the
-fdump-tree-all output, and look at the last one before the conversion
to RTL.

The MEM is giving alias analysis info.  A is the alignment, S is the
size.  The first number is the alias set, where alias set 0 aliases
everything, and other numbers only alias values in the same alias set.
The MEM is the original base and offset for this address, where _39 is
again a compiler generated variable.  You can find the code that
prints this stuff in print-rtl.c, and then you probably need to look
at the alias analysis code if you want to know more.

See also the noce_try_minmax function I pointed at earlier, to see why
it works in one case but not in another case.

Jim

Re[6]: GCC won`t emit my instriction

[Alex Hill via gcc-help]

>Среда, 12 июня 2019, 1:54 +05:00 от Jim Wilson <jimw@sifive.com>:
>
>On Tue, Jun 11, 2019 at 1:32 AM Alex Hill < hardest2005@mail.ru > wrote:
>> BUT! In case we using IF loop GCC wont emit minmax AGAIN!
>It looks like the memory accesses are the problem, not the control
>flow.  However, the control flow may be affecting exactly how the
>compiler optimizes the memory references.  If you create a temporary
>variable, store the result in the temporary variable, and then write
>the temporary variable to memory at the end, it should be optimized
>regardless of control flow.
>
>> what`s the difference between
>> (reg:DI 113 [ ivtmp.29 ]) [1 MEM[base: _39, offset: 0B]+0 S8 A64])
>> and
>> (reg/f:DI 89 [ _48 ]) [1 *_48+0 S8 A64])
>
>_ivtmp.29 and _48 are variable names.  In both cases, these are
>variable names created by high level optimization passes.  See the
>-fdump-tree-all output, and look at the last one before the conversion
>to RTL.
>
>The MEM is giving alias analysis info.  A is the alignment, S is the
>size.  The first number is the alias set, where alias set 0 aliases
>everything, and other numbers only alias values in the same alias set.
>The MEM is the original base and offset for this address, where _39 is
>again a compiler generated variable.  You can find the code that
>prints this stuff in print-rtl.c, and then you probably need to look
>at the alias analysis code if you want to know more.
>
>See also the noce_try_minmax function I pointed at earlier, to see why
>it works in one case but not in another case.
>
>Jim
I`m still looking for the way to emit minmax, now i`m try to find solution in
ifcvt.c, is there exist a way to dump conditional execution step by step, 
i`m interesting in functions:
df_analyze in df-core.c
noce_process_if_block in ifcvt.c
noce_try_minmax in ifcvt.c

I read more than thousand pages from documents from gnu.gcc.org, try to find in internet but i can`t find how to dump
every step of rtl passes, for example 243.r.ce1, there is only general info in dumps receivced by fdump-rtl-all.
In 243.r.ce1 just told "df_analyze called" and nothing else.

Sorry for my Engrish
Kind regards Alex Hill.

Re: Re[6]: GCC won`t emit my instriction

[Jim Wilson]

On Mon, Jun 17, 2019 at 4:34 AM Alex Hill <hardest2005@mail.ru> wrote:
> I`m still looking for the way to emit minmax, now i`m try to find solution in
> ifcvt.c, is there exist a way to dump conditional execution step by step,
>
> I read more than thousand pages from documents from gnu.gcc.org, try to find in internet but i can`t find how to dump
> every step of rtl passes, for example 243.r.ce1, there is only general info in dumps receivced by fdump-rtl-all.
> In 243.r.ce1 just told "df_analyze called" and nothing else.

You can append a -all to get more info, e.g. -fdump-rtl-ce1-all will
emit more info than -fdump-rtl-ce1.  This will only emit info where
the optimization pass has hooks to dump debugging info.  If you need
more info than that, you should be stepping through the code in gdb
We have gdb macros in the .gdbinit file that you can use to pretty
print rtl, etc.  The pr macro will pretty print an rtl pointer.

Jim

Re[8]: GCC won`t emit my instriction

[Alex Hill via gcc-help]

>Вторник, 18 июня 2019, 3:02 +05:00 от Jim Wilson <jimw@sifive.com>:
>
>On Mon, Jun 17, 2019 at 4:34 AM Alex Hill < hardest2005@mail.ru > wrote:
>> I`m still looking for the way to emit minmax, now i`m try to find solution in
>> ifcvt.c, is there exist a way to dump conditional execution step by step,
>>
>> I read more than thousand pages from documents from gnu.gcc.org, try to find in internet but i can`t find how to dump
>> every step of rtl passes, for example 243.r.ce1, there is only general info in dumps receivced by fdump-rtl-all.
>> In 243.r.ce1 just told "df_analyze called" and nothing else.
>
>You can append a -all to get more info, e.g. -fdump-rtl-ce1-all will
>emit more info than -fdump-rtl-ce1.  This will only emit info where
>the optimization pass has hooks to dump debugging info.  If you need
>more info than that, you should be stepping through the code in gdb
>We have gdb macros in the .gdbinit file that you can use to pretty
>print rtl, etc.  The pr macro will pretty print an rtl pointer.
>
>Jim
i`am using key -da it gives the same result as -all-all or -ce1-all, i`m trying to understand what he is writes to me in dumps, but there is lack of info, except comments in sources, i can`t find any books or electronic resource with infos. Its looks for me as some research in depths of sources of GCC, but i will find the way to emit my instruction no matter what costs!!!!


Sorry for my Engrish
Kind regards Alex Hill.