llvm dev - Jul 2017 - Tail merging "undef" with a defined register: wrong code

Yes, immediately after branch folding the code would still behave the 
same as the original.  At the same time, any subsequent optimization may 
"exploit" the incorrect liveness information to do something bad.  If 
you add -run-pass if-converter, you'll get:

# After If Converter
# Machine code for function fred: IsSSA, NoPHIs, TracksLiveness, NoVRegs

BB#0:
         %R0<def> = L2_ploadruhf_io %P0<undef>, %R0<undef>, 0,
%R0<imp-use>
         PS_storerhabs 0, %R0
         PS_jmpret %R31<kill>, %PC<imp-def>

# End machine code for function fred.

*** Bad machine code: Using an undefined physical register ***
- function:    fred
- basic block: BB#0  (0x411e8e8)
- instruction: %R0<def> = L2_ploadruhf_io
- operand 4:   %R0<imp-use>
LLVM ERROR: Found 1 machine code errors.

-Krzysztof


On 7/27/2017 1:47 PM, Quentin Colombet wrote:
> Why do you say the code is wrong?
> 
> I can see why the MachineVerifier would complain, but the code seems to do
the same thing as it was doing before the transformation, isn’t it?
> 
>> On Jul 27, 2017, at 11:40 AM, Krzysztof Parzyszek via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>>
>> The comment in test/CodeGen/X86/branchfolding-undef.mir states that
such merging is legal, however doing so can actually generate wrong code:
>>
>> Consider this (valid code):
>>
>> ---
>> name: fred
>> tracksRegLiveness: true
>>
>> body: |
>>   bb.0:
>>     successors: %bb.1, %bb.2
>>       J2_jumpt undef %p0, %bb.2, implicit-def %pc
>>       J2_jump %bb.1, implicit-def %pc
>>
>>   bb.1:
>>     successors: %bb.3
>>       %r0 = L2_loadruh_io undef %r0, 0
>>       PS_storerhabs 0, killed %r0
>>       J2_jump %bb.3, implicit-def %pc
>>
>>   bb.2:
>>     successors: %bb.3
>>       PS_storerhabs 0, undef %r0
>>       J2_jump %bb.3, implicit-def %pc
>>
>>   bb.3:
>>       PS_jmpret killed %r31, implicit-def %pc
>> ...
>>
>>
>> Run:
>> llc -march=hexagon -run-pass branch-folder test.mir -o -
>>
>>
>> We get an invalid code:
>>
>> body: |
>>   bb.0:
>>     successors: %bb.1(0x40000000), %bb.2(0x40000000)
>>     J2_jumpt undef %p0, %bb.2, implicit-def %pc
>>
>>   bb.1:
>>     successors: %bb.2(0x80000000)
>>     %r0 = L2_loadruh_io undef %r0, 0
>>
>>   bb.2:
>>     liveins: %r0       ; Invalid: r0 is not live out of bb.0
>>     PS_storerhabs 0, %r0
>>     PS_jmpret killed %r31, implicit-def %pc
>> ...
>>
>>
>> Should we disallow merging undef with non-undef?
>>
>> -Krzysztof
>>
>>
>> -- 
>> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
hosted by The Linux Foundation
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> 
-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

Yeah, that’s want I was expecting from the verifier.
I’d say we should add an implicit_def (assuming it gets kill at code emission)
in the part where it is undef.
> On Jul 27, 2017, at 11:52 AM, Krzysztof Parzyszek <kparzysz at
codeaurora.org> wrote:
> 
> Yes, immediately after branch folding the code would still behave the same
as the original.  At the same time, any subsequent optimization may
"exploit" the incorrect liveness information to do something bad.  If
you add -run-pass if-converter, you'll get:
> 
> # After If Converter
> # Machine code for function fred: IsSSA, NoPHIs, TracksLiveness, NoVRegs
> 
> BB#0:
>        %R0<def> = L2_ploadruhf_io %P0<undef>, %R0<undef>,
0, %R0<imp-use>
>        PS_storerhabs 0, %R0
>        PS_jmpret %R31<kill>, %PC<imp-def>
> 
> # End machine code for function fred.
> 
> *** Bad machine code: Using an undefined physical register ***
> - function:    fred
> - basic block: BB#0  (0x411e8e8)
> - instruction: %R0<def> = L2_ploadruhf_io
> - operand 4:   %R0<imp-use>
> LLVM ERROR: Found 1 machine code errors.
> 
> -Krzysztof
> 
> 
> On 7/27/2017 1:47 PM, Quentin Colombet wrote:
>> Why do you say the code is wrong?
>> I can see why the MachineVerifier would complain, but the code seems to
do the same thing as it was doing before the transformation, isn’t it?
>>> On Jul 27, 2017, at 11:40 AM, Krzysztof Parzyszek via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>>> 
>>> The comment in test/CodeGen/X86/branchfolding-undef.mir states that
such merging is legal, however doing so can actually generate wrong code:
>>> 
>>> Consider this (valid code):
>>> 
>>> ---
>>> name: fred
>>> tracksRegLiveness: true
>>> 
>>> body: |
>>>  bb.0:
>>>    successors: %bb.1, %bb.2
>>>      J2_jumpt undef %p0, %bb.2, implicit-def %pc
>>>      J2_jump %bb.1, implicit-def %pc
>>> 
>>>  bb.1:
>>>    successors: %bb.3
>>>      %r0 = L2_loadruh_io undef %r0, 0
>>>      PS_storerhabs 0, killed %r0
>>>      J2_jump %bb.3, implicit-def %pc
>>> 
>>>  bb.2:
>>>    successors: %bb.3
>>>      PS_storerhabs 0, undef %r0
>>>      J2_jump %bb.3, implicit-def %pc
>>> 
>>>  bb.3:
>>>      PS_jmpret killed %r31, implicit-def %pc
>>> ...
>>> 
>>> 
>>> Run:
>>> llc -march=hexagon -run-pass branch-folder test.mir -o -
>>> 
>>> 
>>> We get an invalid code:
>>> 
>>> body: |
>>>  bb.0:
>>>    successors: %bb.1(0x40000000), %bb.2(0x40000000)
>>>    J2_jumpt undef %p0, %bb.2, implicit-def %pc
>>> 
>>>  bb.1:
>>>    successors: %bb.2(0x80000000)
>>>    %r0 = L2_loadruh_io undef %r0, 0
>>> 
>>>  bb.2:
>>>    liveins: %r0       ; Invalid: r0 is not live out of bb.0
>>>    PS_storerhabs 0, %r0
>>>    PS_jmpret killed %r31, implicit-def %pc
>>> ...
>>> 
>>> 
>>> Should we disallow merging undef with non-undef?
>>> 
>>> -Krzysztof
>>> 
>>> 
>>> -- 
>>> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
hosted by The Linux Foundation
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> 
> -- 
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted
by The Linux Foundation

I've looked into that and it's not going to be simple, unfortunately.

Here's the original example again:

---
name: fred
tracksRegLiveness: true

body: |
   bb.0:
     successors: %bb.1, %bb.2
       J2_jumpt undef %p0, %bb.2, implicit-def %pc
       J2_jump %bb.1, implicit-def %pc

   bb.1:
     successors: %bb.3
       %r0 = L2_loadruh_io undef %r0, 0
       PS_storerhabs 0, killed %r0
       J2_jump %bb.3, implicit-def %pc

   bb.2:
     successors: %bb.3
       PS_storerhabs 0, undef %r0
       J2_jump %bb.3, implicit-def %pc

   bb.3:
       PS_jmpret killed %r31, implicit-def %pc
...


If the merging process produced this intermediate code (I stripped some 
unimportant pieces):

   bb.1:
       %r0 = L2_loadruh_io undef %r0, 0
       J2_jump %bb.tail

   bb.2:
       J2_jump %bb.tail

   bb.tail:
     liveins: %r0
       PS_storerhabs 0, killed %r0
       J2_jump %bb.3, implicit-def %pc

Then we could insert IMPLICIT_DEF into bb.2 and everything would be 
fine. This is not what happens, though. In this case, the entire bb.2 
will be used as the new tail leaving us without a good point to put the 
implicit def at.

In this particular testcase, the implicit def could go in bb.0 (which 
was not involved in the tail merging at all), but in general that may 
not be an option.

-Krzysztof



On 7/27/2017 2:20 PM, Quentin Colombet wrote:
> Yeah, that’s want I was expecting from the verifier.
> I’d say we should add an implicit_def (assuming it gets kill at code
emission) in the part where it is undef.
> 
>> On Jul 27, 2017, at 11:52 AM, Krzysztof Parzyszek <kparzysz at
codeaurora.org> wrote:
>>
>> Yes, immediately after branch folding the code would still behave the
same as the original.  At the same time, any subsequent optimization may
"exploit" the incorrect liveness information to do something bad.  If
you add -run-pass if-converter, you'll get:
>>
>> # After If Converter
>> # Machine code for function fred: IsSSA, NoPHIs, TracksLiveness,
NoVRegs
>>
>> BB#0:
>>         %R0<def> = L2_ploadruhf_io %P0<undef>,
%R0<undef>, 0, %R0<imp-use>
>>         PS_storerhabs 0, %R0
>>         PS_jmpret %R31<kill>, %PC<imp-def>
>>
>> # End machine code for function fred.
>>
>> *** Bad machine code: Using an undefined physical register ***
>> - function:    fred
>> - basic block: BB#0  (0x411e8e8)
>> - instruction: %R0<def> = L2_ploadruhf_io
>> - operand 4:   %R0<imp-use>
>> LLVM ERROR: Found 1 machine code errors.
>>
>> -Krzysztof
>>
>>
>> On 7/27/2017 1:47 PM, Quentin Colombet wrote:
>>> Why do you say the code is wrong?
>>> I can see why the MachineVerifier would complain, but the code
seems to do the same thing as it was doing before the transformation, isn’t it?
>>>> On Jul 27, 2017, at 11:40 AM, Krzysztof Parzyszek via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>>>>
>>>> The comment in test/CodeGen/X86/branchfolding-undef.mir states
that such merging is legal, however doing so can actually generate wrong code:
>>>>
>>>> Consider this (valid code):
>>>>
>>>> ---
>>>> name: fred
>>>> tracksRegLiveness: true
>>>>
>>>> body: |
>>>>   bb.0:
>>>>     successors: %bb.1, %bb.2
>>>>       J2_jumpt undef %p0, %bb.2, implicit-def %pc
>>>>       J2_jump %bb.1, implicit-def %pc
>>>>
>>>>   bb.1:
>>>>     successors: %bb.3
>>>>       %r0 = L2_loadruh_io undef %r0, 0
>>>>       PS_storerhabs 0, killed %r0
>>>>       J2_jump %bb.3, implicit-def %pc
>>>>
>>>>   bb.2:
>>>>     successors: %bb.3
>>>>       PS_storerhabs 0, undef %r0
>>>>       J2_jump %bb.3, implicit-def %pc
>>>>
>>>>   bb.3:
>>>>       PS_jmpret killed %r31, implicit-def %pc
>>>> ...
>>>>
>>>>
>>>> Run:
>>>> llc -march=hexagon -run-pass branch-folder test.mir -o -
>>>>
>>>>
>>>> We get an invalid code:
>>>>
>>>> body: |
>>>>   bb.0:
>>>>     successors: %bb.1(0x40000000), %bb.2(0x40000000)
>>>>     J2_jumpt undef %p0, %bb.2, implicit-def %pc
>>>>
>>>>   bb.1:
>>>>     successors: %bb.2(0x80000000)
>>>>     %r0 = L2_loadruh_io undef %r0, 0
>>>>
>>>>   bb.2:
>>>>     liveins: %r0       ; Invalid: r0 is not live out of bb.0
>>>>     PS_storerhabs 0, %r0
>>>>     PS_jmpret killed %r31, implicit-def %pc
>>>> ...
>>>>
>>>>
>>>> Should we disallow merging undef with non-undef?
>>>>
>>>> -Krzysztof
>>>>
>>>>
>>>> -- 
>>>> Qualcomm Innovation Center, Inc. is a member of Code Aurora
Forum, hosted by The Linux Foundation
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org
>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>> -- 
>> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
hosted by The Linux Foundation
> 
-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation