Re: [PATCH] New hook adjust_iv_update_pos

[Xionghu Luo <luoxhu@linux.ibm.com>]

On 2021/7/7 21:20, Richard Biener wrote:
> On Tue, Jun 29, 2021 at 11:19 AM Xionghu Luo <luoxhu@linux.ibm.com> wrote:
>>
>>
>>
>> On 2021/6/28 16:25, Richard Biener wrote:
>>> On Mon, Jun 28, 2021 at 10:07 AM Xionghu Luo <luoxhu@linux.ibm.com> wrote:
>>>>
>>>>
>>>>
>>>> On 2021/6/25 18:02, Richard Biener wrote:
>>>>> On Fri, Jun 25, 2021 at 11:41 AM Xionghu Luo <luoxhu@linux.ibm.com> wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>> On 2021/6/25 16:54, Richard Biener wrote:
>>>>>>> On Fri, Jun 25, 2021 at 10:34 AM Xionghu Luo via Gcc-patches
>>>>>>> <gcc-patches@gcc.gnu.org> wrote:
>>>>>>>>
>>>>>>>> From: Xiong Hu Luo <luoxhu@linux.ibm.com>
>>>>>>>>
>>>>>>>> adjust_iv_update_pos in tree-ssa-loop-ivopts doesn't help performance
>>>>>>>> on Power.  For example, it generates mismatched address offset after
>>>>>>>> adjust iv update statement position:
>>>>>>>>
>>>>>>>> <bb 32> [local count: 70988443]:
>>>>>>>> _84 = MEM[(uint8_t *)ip_229 + ivtmp.30_414 * 1];
>>>>>>>> ivtmp.30_415 = ivtmp.30_414 + 1;
>>>>>>>> _34 = ref_180 + 18446744073709551615;
>>>>>>>> _86 = MEM[(uint8_t *)_34 + ivtmp.30_415 * 1];
>>>>>>>> if (_84 == _86)
>>>>>>>>       goto <bb 56>; [94.50%]
>>>>>>>>       else
>>>>>>>>       goto <bb 87>; [5.50%]
>>>>>>>>
>>>>>>>> Disable it will produce:
>>>>>>>>
>>>>>>>> <bb 32> [local count: 70988443]:
>>>>>>>> _84 = MEM[(uint8_t *)ip_229 + ivtmp.30_414 * 1];
>>>>>>>> _86 = MEM[(uint8_t *)ref_180 + ivtmp.30_414 * 1];
>>>>>>>> ivtmp.30_415 = ivtmp.30_414 + 1;
>>>>>>>> if (_84 == _86)
>>>>>>>>       goto <bb 56>; [94.50%]
>>>>>>>>       else
>>>>>>>>       goto <bb 87>; [5.50%]
>>>>>>>>
>>>>>>>> Then later pass loop unroll could benefit from same address offset
>>>>>>>> with different base address and reduces register dependency.
>>>>>>>> This patch could improve performance by 10% for typical case on Power,
>>>>>>>> no performance change observed for X86 or Aarch64 due to small loops
>>>>>>>> not unrolled on these platforms.  Any comments?
>>>>>>>
>>>>>>> The case you quote is special in that if we hoisted the IV update before
>>>>>>> the other MEM _also_ used in the condition it would be fine again.
>>>>>>
>>>>>> Thanks.  I tried to hoist the IV update statement before the first MEM (Fix 2), it
>>>>>> shows even worse performance due to not unroll(two more "base-1" is generated in gimple,
>>>>>> then loop->ninsns is 11 so small loops is not unrolled), change the threshold from
>>>>>> 10 to 12 in rs6000_loop_unroll_adjust would make it also unroll 2 times, the
>>>>>> performance is SAME to the one that IV update statement in the *MIDDLE* (trunk).
>>>>>>    From the ASM, we can see the index register %r4 is used in two iterations which
>>>>>> maybe a bottle neck for hiding instruction latency?
>>>>>>
>>>>>> Then it seems reasonable the performance would be better if keep the IV update
>>>>>> statement at *LAST* (Fix 1).
>>>>>>
>>>>>> (Fix 2):
>>>>>>      <bb 32> [local count: 70988443]:
>>>>>>      ivtmp.30_415 = ivtmp.30_414 + 1;
>>>>>>      _34 = ip_229 + 18446744073709551615;
>>>>>>      _84 = MEM[(uint8_t *)_34 + ivtmp.30_415 * 1];
>>>>>>      _33 = ref_180 + 18446744073709551615;
>>>>>>      _86 = MEM[(uint8_t *)_33 + ivtmp.30_415 * 1];
>>>>>>      if (_84 == _86)
>>>>>>        goto <bb 56>; [94.50%]
>>>>>>      else
>>>>>>        goto <bb 87>; [5.50%]
>>>>>>
>>>>>>
>>>>>> .L67:
>>>>>>            lbzx %r12,%r24,%r4
>>>>>>            lbzx %r25,%r7,%r4
>>>>>>            cmpw %cr0,%r12,%r25
>>>>>>            bne %cr0,.L11
>>>>>>            mr %r26,%r4
>>>>>>            addi %r4,%r4,1
>>>>>>            lbzx %r12,%r24,%r4
>>>>>>            lbzx %r25,%r7,%r4
>>>>>>            mr %r6,%r26
>>>>>>            cmpw %cr0,%r12,%r25
>>>>>>            bne %cr0,.L11
>>>>>>            mr %r26,%r4
>>>>>> .L12:
>>>>>>            cmpdi %cr0,%r10,1
>>>>>>            addi %r4,%r26,1
>>>>>>            mr %r6,%r26
>>>>>>            addi %r10,%r10,-1
>>>>>>            bne %cr0,.L67
>>>>>>
>>>>>>>
>>>>>>> Now, adjust_iv_update_pos doesn't seem to check that the
>>>>>>> condition actually uses the IV use stmt def, so it likely applies to
>>>>>>> too many cases.
>>>>>>>
>>>>>>> Unfortunately the introducing rev didn't come with a testcase,
>>>>>>> but still I think fixing up adjust_iv_update_pos is better than
>>>>>>> introducing a way to short-cut it per target decision.
>>>>>>>
>>>>>>> One "fix" might be to add a check that either the condition
>>>>>>> lhs or rhs is the def of the IV use and the other operand
>>>>>>> is invariant.  Or if it's of similar structure hoist across the
>>>>>>> other iv-use as well.  Not that I understand the argument
>>>>>>> about the overlapping life-range.
>>>>>>>
>>>>>>> You also don't provide a complete testcase ...
>>>>>>>
>>>>>>
>>>>>> Attached the test code, will also add it it patch in future version.
>>>>>> The issue comes from a very small hot loop:
>>>>>>
>>>>>>            do {
>>>>>>              len++;
>>>>>>            } while(len < maxlen && ip[len] == ref[len]);
>>>>>
>>>>> unsigned int foo (unsigned char *ip, unsigned char *ref, unsigned int maxlen)
>>>>> {
>>>>>      unsigned int len = 2;
>>>>>      do {
>>>>>          len++;
>>>>>      }while(len < maxlen && ip[len] == ref[len]);
>>>>>      return len;
>>>>> }
>>>>>
>>>>> I can see the effect on this loop on x86_64 as well, we end up with
>>>>>
>>>>> .L6:
>>>>>            movzbl  (%rdi,%rax), %ecx
>>>>>            addq    $1, %rax
>>>>>            cmpb    -1(%rsi,%rax), %cl
>>>>>            jne     .L1
>>>>> .L3:
>>>>>            movl    %eax, %r8d
>>>>>            cmpl    %edx, %eax
>>>>>            jb      .L6
>>>>>
>>>>> but without the trick it is
>>>>>
>>>>> .L6:
>>>>>            movzbl  (%rdi,%rax), %r8d
>>>>>            movzbl  (%rsi,%rax), %ecx
>>>>>            addq    $1, %rax
>>>>>            cmpb    %cl, %r8b
>>>>>            jne     .L1
>>>>> .L3:
>>>>>            movl    %eax, %r9d
>>>>>            cmpl    %edx, %eax
>>>>>            jb      .L6
>>>>
>>>> Verified this small piece of code on X86, there is no performance
>>>> change with or without adjust_iv_update_pos (I've checked the ASM
>>>> exactly same with yours):
>>>>
>>>> luoxhu@gcc14:~/workspace/lzf_compress_testcase$ gcc -O2 test.c
>>>> luoxhu@gcc14:~/workspace/lzf_compress_testcase$ time ./a.out  1
>>>>
>>>> real    0m7.003s
>>>> user    0m6.996s
>>>> sys     0m0.000s
>>>> luoxhu@gcc14:~/workspace/lzf_compress_testcase$ /home/luoxhu/workspace/build/gcc/xgcc -B/home/luoxhu/workspace/build/g
>>>> cc/ -O2 test.c
>>>> luoxhu@gcc14:~/workspace/lzf_compress_testcase$ time ./a.out  1
>>>>
>>>> real    0m7.070s
>>>> user    0m7.068s
>>>> sys     0m0.000s
>>>>
>>>>
>>>> But for AArch64, current GCC code also generates similar code with
>>>> or without adjust_iv_update_pos, the runtime is 10.705s for them.
>>>>
>>>> L6:
>>>>           ldrb    w4, [x6, x3]
>>>>           add     x3, x3, 1
>>>>           ldrb    w5, [x1, x3]
>>>>           cmp     w5, w4
>>>>           bne     .L1
>>>> .L3:
>>>>           mov     w0, w3
>>>>           cmp     w2, w3
>>>>           bhi     .L6
>>>>
>>>> No adjust_iv_update_pos:
>>>>
>>>> .L6:
>>>>           ldrb    w5, [x6, x3]
>>>>           ldrb    w4, [x1, x3]
>>>>           add     x3, x3, 1
>>>>           cmp     w5, w4
>>>>           bne     .L1
>>>> .L3:
>>>>           mov     w0, w3
>>>>           cmp     w2, w3
>>>>           bhi     .L6
>>>>
>>>>
>>>> While built with old GCC(gcc version 7.4.1 20190424), it generates
>>>> worse code and runtime is 11.664s:
>>>>
>>>> .L6:
>>>>           ldrb    w4, [x6, x3]
>>>>           add     x3, x3, 1
>>>>           add     x5, x1, x3
>>>>           ldrb    w5, [x5, -1]
>>>>           cmp     w5, w4
>>>>           bne     .L1
>>>> .L3:
>>>>           cmp     w3, w2
>>>>           mov     w0, w3
>>>>           bcc     .L6
>>>>
>>>>
>>>> In general, only Power shows negative performance with adjust_iv_update_pos,
>>>> that's why I tried to add target hook for it, is this reasonable?  Or we should
>>>> just remove adjust_iv_update_pos since it doesn't help performance for X86 or
>>>> other targets?
>>>
>>> It was Bin who added the functionality - maybe he can remember the cases
>>> he saw improvements for.
>>>
>>> I think we should instead try to change the code that it doesn't apply to
>>> CONDs where both operands are defined by stmts using the IV?
>>> And this time add a testcase ;)
>>
>> Thanks. I am not sure whether should check both cond_lhs and cond_rhs or just
>> cond_lhs is enough if COND expr's LHS is always processed first?
>>
>> For example, adjust_iv_update_pos will be called twice for this case,
>> after the first call, the gimple will be updated to:
>>
>> <bb 4> [local count: 1014686026]:
>> _1 = (sizetype) len_8;
>> _2 = ip_10(D) + _1;
>> _3 = MEM[(unsigned char *)ip_10(D) + ivtmp.15_15 * 1];
>> _5 = ref_12(D) + _1;
>> _6 = *_5;
>> ivtmp.15_16 = ivtmp.15_15 + 1;
>> if (_3 == _6)
>>    goto <bb 6>; [94.50%]
>> else
>>    goto <bb 10>; [5.50%]
>>
>>
>> At this moment, use->stmt is "_6 = *_5;", it is not using IV directly?
> 
> So looking around I think you want to pass down the IV group from
> rewrite_groups to rewrite_use_address and then see whether the
> definition of the RHS is one of the IV USE stmts that are going to be
> expressed using the same candidate.  In fact, I guess (to avoid
> linear searching the group), we likely might want to restrict considering
> adjust_iv_update_pos for IV candidates with a single [address] use?
> That would be more restrictive of course (OTOH the list shouldn't be
> too big - hopefully).  In case the other side of the conditional is
> a memory using a different IV the replacement should still be OK.
> 
> Richard.

Thanks, however those methods would still break the X86 optimization
with worse ASM(one more movzbl) though no performance change observed.
CCed X86 maintainers to see which one they prefer, and whether target
hook is a better solution?


GCC trunk:

.L6:
          movzbl  (%rdi,%rax), %ecx
          addq    $1, %rax
          cmpb    -1(%rsi,%rax), %cl
          jne     .L1
.L3:
          movl    %eax, %r8d
          cmpl    %edx, %eax
          jb      .L6

Disable adjust_iv_update_pos:

.L6:
          movzbl  (%rdi,%rax), %r8d
          movzbl  (%rsi,%rax), %ecx
          addq    $1, %rax
          cmpb    %cl, %r8b
          jne     .L1
.L3:
          movl    %eax, %r9d
          cmpl    %edx, %eax
          jb      .L6



-- 
Thanks,
Xionghu