llvm dev - Sep 2017 - Reaching definitions on Machine IR post register allocation

Hi,

Just to clarify I am looking for a whole machine function analysis not just
something restricted to within a machine basic block.

Thanks.

Regards,
Venu.

From: Raghavan, Venugopal
Sent: Saturday, September 02, 2017 12:56 PM
To: llvm-dev at lists.llvm.org
Subject: Reaching definitions on Machine IR post register allocation

Hi,

Given a definition of a register by a machine instruction in the Machine IR post
register allocation, I would like to compute the set of uses of this register
reached by this definition.
Does LLVM already have this kind of analysis I can use? Otherwise, I will have
to implement a reaching definitions analysis which would be a little involved
since it would need to work on a non-SSA IR form.

If something already exists that would be very helpful for me.

Thanks.

Regards,
Venugopal Raghavan.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170904/788a1c07/attachment.html>

Hexagon has RDF that does exactly that.  At the moment it's under 
lib/Target/Hexagon, but it meant to be target-independent.  It won't 
work with X86 due to a known issue related to register units, but it 
should work fine for other targets.  See https://reviews.llvm.org/D29295 
about moving it to lib/CodeGen.

-Krzysztof

On 9/4/2017 9:00 AM, Raghavan, Venugopal via llvm-dev
wrote:
> Hi,
> 
> Just to clarify I am looking for a whole machine function analysis not 
> just something restricted to within a machine basic block.
> 
> Thanks.
> 
> Regards,
> 
> Venu.
> 
> *From:* Raghavan, Venugopal
> *Sent:* Saturday, September 02, 2017 12:56 PM
> *To:* llvm-dev at lists.llvm.org
> *Subject:* Reaching definitions on Machine IR post register allocation
> 
> Hi,
> 
> Given a definition of a register by a machine instruction in the Machine 
> IR post register allocation, I would like to compute the set of uses of 
> this register reached by this definition.
> 
> Does LLVM already have this kind of analysis I can use? Otherwise, I 
> will have to implement a reaching definitions analysis which would be a 
> little involved since it would need to work on a non-SSA IR form.
> 
> If something already exists that would be very helpful for me.
> 
> Thanks.
> 
> Regards,
> 
> Venugopal Raghavan.
> 
> 
> 
> _______________________________________________
> 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

Hi Krzysztof,

I did look at the other link you have mentioned in your reply but did not quite
understand the register units issue. If it is not too difficult, can you briefly
summarize what the issue was?

Thanks.

Regards,
Venu.


-----Original Message-----
From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
Krzysztof Parzyszek via llvm-dev
Sent: Tuesday, September 5, 2017 7:44 PM
To: llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] Reaching definitions on Machine IR post register
allocation

Hexagon has RDF that does exactly that.  At the moment it's under
lib/Target/Hexagon, but it meant to be target-independent.  It won't work
with X86 due to a known issue related to register units, but it should work fine
for other targets.  See https://reviews.llvm.org/D29295 about moving it to
lib/CodeGen.

-Krzysztof

On 9/4/2017 9:00 AM, Raghavan, Venugopal via llvm-dev
wrote:
> Hi,
> 
> Just to clarify I am looking for a whole machine function analysis not 
> just something restricted to within a machine basic block.
> 
> Thanks.
> 
> Regards,
> 
> Venu.
> 
> *From:* Raghavan, Venugopal
> *Sent:* Saturday, September 02, 2017 12:56 PM
> *To:* llvm-dev at lists.llvm.org
> *Subject:* Reaching definitions on Machine IR post register allocation
> 
> Hi,
> 
> Given a definition of a register by a machine instruction in the 
> Machine IR post register allocation, I would like to compute the set 
> of uses of this register reached by this definition.
> 
> Does LLVM already have this kind of analysis I can use? Otherwise, I 
> will have to implement a reaching definitions analysis which would be 
> a little involved since it would need to work on a non-SSA IR form.
> 
> If something already exists that would be very helpful for me.
> 
> Thanks.
> 
> Regards,
> 
> Venugopal Raghavan.
> 
> 
> 
> _______________________________________________
> 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 _______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

RDF needs to know when an assignment to a register is overwritten by 
another assignment, or by a sequence of assignments.  This is needed to 
determine whether the original assignment is still live or not. RDF uses 
register units to represent the building blocks of registers, and 
assumes that if all units of a register are overwritten, then the 
original value of that register is completely overwritten. This 
assumption is true for all targets (that I have tested it with) except 
X86. On X86, registers AX and EAX both have only one register unit, but 
when you assign a value to AX, the upper half of EAX is preserved (that 
is, the original value of EAX is not completely overwritten).

-Krzysztof

On 9/6/2017 6:42 AM, Raghavan, Venugopal via llvm-dev
wrote:
> Hi Krzysztof,
> 
> I did look at the other link you have mentioned in your reply but did not
quite understand the register units issue. If it is not too difficult, can you
briefly summarize what the issue was?
> 
> Thanks.
> 
> Regards,
> Venu.
> 
> 
> -----Original Message-----
> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
Krzysztof Parzyszek via llvm-dev
> Sent: Tuesday, September 5, 2017 7:44 PM
> To: llvm-dev at lists.llvm.org
> Subject: Re: [llvm-dev] Reaching definitions on Machine IR post register
allocation
> 
> Hexagon has RDF that does exactly that.  At the moment it's under
lib/Target/Hexagon, but it meant to be target-independent.  It won't work
with X86 due to a known issue related to register units, but it should work fine
for other targets.  See https://reviews.llvm.org/D29295 about moving it to
lib/CodeGen.
> 
> -Krzysztof
> 
> On 9/4/2017 9:00 AM, Raghavan, Venugopal via llvm-dev wrote:
>> Hi,
>>
>> Just to clarify I am looking for a whole machine function analysis not
>> just something restricted to within a machine basic block.
>>
>> Thanks.
>>
>> Regards,
>>
>> Venu.
>>
>> *From:* Raghavan, Venugopal
>> *Sent:* Saturday, September 02, 2017 12:56 PM
>> *To:* llvm-dev at lists.llvm.org
>> *Subject:* Reaching definitions on Machine IR post register allocation
>>
>> Hi,
>>
>> Given a definition of a register by a machine instruction in the
>> Machine IR post register allocation, I would like to compute the set
>> of uses of this register reached by this definition.
>>
>> Does LLVM already have this kind of analysis I can use? Otherwise, I
>> will have to implement a reaching definitions analysis which would be
>> a little involved since it would need to work on a non-SSA IR form.
>>
>> If something already exists that would be very helpful for me.
>>
>> Thanks.
>>
>> Regards,
>>
>> Venugopal Raghavan.
>>
>>
>>
>> _______________________________________________
>> 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 _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> _______________________________________________
> 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

Hi Krzysztof,

Thanks for your explanation - I think I understand the issue now.

I do know if this is a hack, but, in reaching definitions, when we check if a
definition of AX kills a previous definition of EAX, can we not check the actual
physical register? In this case since EAX and AX are different (although I
understand AX is a sub-register of EAX), can we not conclude that the definition
of AX does not kill EAX? Since, in reaching definitions, it is conservative if
we over-estimate the set of reaching definitions (but not unsafe), should not
this strategy be adequate to avoid incorrect optimizations?

Or, is there an optimization that can behave incorrectly with an overestimated
set of reaching definitions?

Regards,
Venu.

-----Original Message-----
From: Nema, Ashutosh 
Sent: Friday, September 08, 2017 12:00 PM
To: Raghavan, Venugopal <Venugopal.Raghavan at amd.com>
Subject: FW: [llvm-dev] Reaching definitions on Machine IR post register
allocation



-----Original Message-----
From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
Krzysztof Parzyszek via llvm-dev
Sent: Wednesday, September 6, 2017 6:10 PM
To: llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] Reaching definitions on Machine IR post register
allocation

RDF needs to know when an assignment to a register is overwritten by another
assignment, or by a sequence of assignments.  This is needed to determine
whether the original assignment is still live or not. RDF uses register units to
represent the building blocks of registers, and assumes that if all units of a
register are overwritten, then the original value of that register is completely
overwritten. This assumption is true for all targets (that I have tested it
with) except X86. On X86, registers AX and EAX both have only one register unit,
but when you assign a value to AX, the upper half of EAX is preserved (that is,
the original value of EAX is not completely overwritten).

-Krzysztof

On 9/6/2017 6:42 AM, Raghavan, Venugopal via llvm-dev
wrote:
> Hi Krzysztof,
> 
> I did look at the other link you have mentioned in your reply but did not
quite understand the register units issue. If it is not too difficult, can you
briefly summarize what the issue was?
> 
> Thanks.
> 
> Regards,
> Venu.
> 
> 
> -----Original Message-----
> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of 
> Krzysztof Parzyszek via llvm-dev
> Sent: Tuesday, September 5, 2017 7:44 PM
> To: llvm-dev at lists.llvm.org
> Subject: Re: [llvm-dev] Reaching definitions on Machine IR post 
> register allocation
> 
> Hexagon has RDF that does exactly that.  At the moment it's under
lib/Target/Hexagon, but it meant to be target-independent.  It won't work
with X86 due to a known issue related to register units, but it should work fine
for other targets.  See https://reviews.llvm.org/D29295 about moving it to
lib/CodeGen.
> 
> -Krzysztof
> 
> On 9/4/2017 9:00 AM, Raghavan, Venugopal via llvm-dev wrote:
>> Hi,
>>
>> Just to clarify I am looking for a whole machine function analysis 
>> not just something restricted to within a machine basic block.
>>
>> Thanks.
>>
>> Regards,
>>
>> Venu.
>>
>> *From:* Raghavan, Venugopal
>> *Sent:* Saturday, September 02, 2017 12:56 PM
>> *To:* llvm-dev at lists.llvm.org
>> *Subject:* Reaching definitions on Machine IR post register 
>> allocation
>>
>> Hi,
>>
>> Given a definition of a register by a machine instruction in the 
>> Machine IR post register allocation, I would like to compute the set 
>> of uses of this register reached by this definition.
>>
>> Does LLVM already have this kind of analysis I can use? Otherwise, I 
>> will have to implement a reaching definitions analysis which would be 
>> a little involved since it would need to work on a non-SSA IR form.
>>
>> If something already exists that would be very helpful for me.
>>
>> Thanks.
>>
>> Regards,
>>
>> Venugopal Raghavan.
>>
>>
>>
>> _______________________________________________
>> 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 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> _______________________________________________
> 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 _______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

It would be much easier to add extra reg units to EAX, EBX, etc. to 
represent the upper half of the register. That would fix the issue the 
right way (and would actually make sense without the context of RDF).

Regarding the sub-register check---consider this case:

   AX = ...
   ...
   AL = ...  // AX partially overwritten
   AH = ...  // AX completely overwritten

Each of the assignments to AL/AH does not overwrite AX by itself, but 
together they do. This would be very difficult to detect if we added 
such special treatment of sub-registers that you propose.

I could try to make a case for the extra register units to get them added.

-Krzysztof


On 9/8/2017 1:55 AM, Raghavan, Venugopal via llvm-dev
wrote:
> Hi Krzysztof,
> 
> Thanks for your explanation - I think I understand the issue now.
> 
> I do know if this is a hack, but, in reaching definitions, when we check if
a definition of AX kills a previous definition of EAX, can we not check the
actual physical register? In this case since EAX and AX are different (although
I understand AX is a sub-register of EAX), can we not conclude that the
definition of AX does not kill EAX? Since, in reaching definitions, it is
conservative if we over-estimate the set of reaching definitions (but not
unsafe), should not this strategy be adequate to avoid incorrect optimizations?
> 
> Or, is there an optimization that can behave incorrectly with an
overestimated set of reaching definitions?
> 
> Regards,
> Venu.
> 
> -----Original Message-----
> From: Nema, Ashutosh
> Sent: Friday, September 08, 2017 12:00 PM
> To: Raghavan, Venugopal <Venugopal.Raghavan at amd.com>
> Subject: FW: [llvm-dev] Reaching definitions on Machine IR post register
allocation
> 
> 
> 
> -----Original Message-----
> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
Krzysztof Parzyszek via llvm-dev
> Sent: Wednesday, September 6, 2017 6:10 PM
> To: llvm-dev at lists.llvm.org
> Subject: Re: [llvm-dev] Reaching definitions on Machine IR post register
allocation
> 
> RDF needs to know when an assignment to a register is overwritten by
another assignment, or by a sequence of assignments.  This is needed to
determine whether the original assignment is still live or not. RDF uses
register units to represent the building blocks of registers, and assumes that
if all units of a register are overwritten, then the original value of that
register is completely overwritten. This assumption is true for all targets
(that I have tested it with) except X86. On X86, registers AX and EAX both have
only one register unit, but when you assign a value to AX, the upper half of EAX
is preserved (that is, the original value of EAX is not completely overwritten).
> 
> -Krzysztof
> 
> On 9/6/2017 6:42 AM, Raghavan, Venugopal via llvm-dev wrote:
>> Hi Krzysztof,
>>
>> I did look at the other link you have mentioned in your reply but did
not quite understand the register units issue. If it is not too difficult, can
you briefly summarize what the issue was?
>>
>> Thanks.
>>
>> Regards,
>> Venu.
>>
>>
>> -----Original Message-----
>> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
>> Krzysztof Parzyszek via llvm-dev
>> Sent: Tuesday, September 5, 2017 7:44 PM
>> To: llvm-dev at lists.llvm.org
>> Subject: Re: [llvm-dev] Reaching definitions on Machine IR post
>> register allocation
>>
>> Hexagon has RDF that does exactly that.  At the moment it's under
lib/Target/Hexagon, but it meant to be target-independent.  It won't work
with X86 due to a known issue related to register units, but it should work fine
for other targets.  See https://reviews.llvm.org/D29295 about moving it to
lib/CodeGen.
>>
>> -Krzysztof
>>
>> On 9/4/2017 9:00 AM, Raghavan, Venugopal via llvm-dev wrote:
>>> Hi,
>>>
>>> Just to clarify I am looking for a whole machine function analysis
>>> not just something restricted to within a machine basic block.
>>>
>>> Thanks.
>>>
>>> Regards,
>>>
>>> Venu.
>>>
>>> *From:* Raghavan, Venugopal
>>> *Sent:* Saturday, September 02, 2017 12:56 PM
>>> *To:* llvm-dev at lists.llvm.org
>>> *Subject:* Reaching definitions on Machine IR post register
>>> allocation
>>>
>>> Hi,
>>>
>>> Given a definition of a register by a machine instruction in the
>>> Machine IR post register allocation, I would like to compute the
set
>>> of uses of this register reached by this definition.
>>>
>>> Does LLVM already have this kind of analysis I can use? Otherwise,
I
>>> will have to implement a reaching definitions analysis which would
be
>>> a little involved since it would need to work on a non-SSA IR form.
>>>
>>> If something already exists that would be very helpful for me.
>>>
>>> Thanks.
>>>
>>> Regards,
>>>
>>> Venugopal Raghavan.
>>>
>>>
>>>
>>> _______________________________________________
>>> 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
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>> _______________________________________________
>> 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 _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> _______________________________________________
> 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

Hi Krzysztof,

Thanks for your reply.

I agree that adding extra register units for x86 would be the right way to fix
this. Do you know if there is a plan to fix this?

The case that you have pointed out involving partial writes to a register
together completely killing a wider register is interesting and did not occur to
me. But, for reaching definitions, even if you do not detect this case,
shouldn't this be safe (although conservative) since you would only end up
over-estimating the set of reaching definitions at a point?

But for other scenarios such as copy propagation, you may need to detect this
scenario because otherwise you could assume that a copy reaches a use point
(when it actually does not) and you may end up propagating the copy when it is
incorrect to do so.

Regards,
Venu.


-----Original Message-----
From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
Krzysztof Parzyszek via llvm-dev
Sent: Friday, September 8, 2017 7:10 PM
To: llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] Reaching definitions on Machine IR post register
allocation

It would be much easier to add extra reg units to EAX, EBX, etc. to represent
the upper half of the register. That would fix the issue the right way (and
would actually make sense without the context of RDF).

Regarding the sub-register check---consider this case:

   AX = ...
   ...
   AL = ...  // AX partially overwritten
   AH = ...  // AX completely overwritten

Each of the assignments to AL/AH does not overwrite AX by itself, but together
they do. This would be very difficult to detect if we added such special
treatment of sub-registers that you propose.

I could try to make a case for the extra register units to get them added.

-Krzysztof


On 9/8/2017 1:55 AM, Raghavan, Venugopal via llvm-dev
wrote:
> Hi Krzysztof,
> 
> Thanks for your explanation - I think I understand the issue now.
> 
> I do know if this is a hack, but, in reaching definitions, when we check if
a definition of AX kills a previous definition of EAX, can we not check the
actual physical register? In this case since EAX and AX are different (although
I understand AX is a sub-register of EAX), can we not conclude that the
definition of AX does not kill EAX? Since, in reaching definitions, it is
conservative if we over-estimate the set of reaching definitions (but not
unsafe), should not this strategy be adequate to avoid incorrect optimizations?
> 
> Or, is there an optimization that can behave incorrectly with an
overestimated set of reaching definitions?
> 
> Regards,
> Venu.
> 
> -----Original Message-----
> From: Nema, Ashutosh
> Sent: Friday, September 08, 2017 12:00 PM
> To: Raghavan, Venugopal <Venugopal.Raghavan at amd.com>
> Subject: FW: [llvm-dev] Reaching definitions on Machine IR post 
> register allocation
> 
> 
> 
> -----Original Message-----
> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of 
> Krzysztof Parzyszek via llvm-dev
> Sent: Wednesday, September 6, 2017 6:10 PM
> To: llvm-dev at lists.llvm.org
> Subject: Re: [llvm-dev] Reaching definitions on Machine IR post 
> register allocation
> 
> RDF needs to know when an assignment to a register is overwritten by
another assignment, or by a sequence of assignments.  This is needed to
determine whether the original assignment is still live or not. RDF uses
register units to represent the building blocks of registers, and assumes that
if all units of a register are overwritten, then the original value of that
register is completely overwritten. This assumption is true for all targets
(that I have tested it with) except X86. On X86, registers AX and EAX both have
only one register unit, but when you assign a value to AX, the upper half of EAX
is preserved (that is, the original value of EAX is not completely overwritten).
> 
> -Krzysztof
> 
> On 9/6/2017 6:42 AM, Raghavan, Venugopal via llvm-dev wrote:
>> Hi Krzysztof,
>>
>> I did look at the other link you have mentioned in your reply but did
not quite understand the register units issue. If it is not too difficult, can
you briefly summarize what the issue was?
>>
>> Thanks.
>>
>> Regards,
>> Venu.
>>
>>
>> -----Original Message-----
>> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
>> Krzysztof Parzyszek via llvm-dev
>> Sent: Tuesday, September 5, 2017 7:44 PM
>> To: llvm-dev at lists.llvm.org
>> Subject: Re: [llvm-dev] Reaching definitions on Machine IR post 
>> register allocation
>>
>> Hexagon has RDF that does exactly that.  At the moment it's under
lib/Target/Hexagon, but it meant to be target-independent.  It won't work
with X86 due to a known issue related to register units, but it should work fine
for other targets.  See https://reviews.llvm.org/D29295 about moving it to
lib/CodeGen.
>>
>> -Krzysztof
>>
>> On 9/4/2017 9:00 AM, Raghavan, Venugopal via llvm-dev wrote:
>>> Hi,
>>>
>>> Just to clarify I am looking for a whole machine function analysis 
>>> not just something restricted to within a machine basic block.
>>>
>>> Thanks.
>>>
>>> Regards,
>>>
>>> Venu.
>>>
>>> *From:* Raghavan, Venugopal
>>> *Sent:* Saturday, September 02, 2017 12:56 PM
>>> *To:* llvm-dev at lists.llvm.org
>>> *Subject:* Reaching definitions on Machine IR post register 
>>> allocation
>>>
>>> Hi,
>>>
>>> Given a definition of a register by a machine instruction in the 
>>> Machine IR post register allocation, I would like to compute the
set
>>> of uses of this register reached by this definition.
>>>
>>> Does LLVM already have this kind of analysis I can use? Otherwise,
I
>>> will have to implement a reaching definitions analysis which would 
>>> be a little involved since it would need to work on a non-SSA IR
form.
>>>
>>> If something already exists that would be very helpful for me.
>>>
>>> Thanks.
>>>
>>> Regards,
>>>
>>> Venugopal Raghavan.
>>>
>>>
>>>
>>> _______________________________________________
>>> 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 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>> _______________________________________________
>> 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 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> _______________________________________________
> 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 _______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Hi Venu,
> On Sep 11, 2017, at 11:00 PM, Raghavan, Venugopal via llvm-dev <llvm-dev
at lists.llvm.org> wrote:
> 
> Hi Krzysztof,
> 
> Thanks for your reply.
> 
> I agree that adding extra register units for x86 would be the right way to
fix this. Do you know if there is a plan to fix this?
No concrete plan, no. We've been thinking about for quite some time now, but
never got at it.

Cheers,
-Quentin
> 
> The case that you have pointed out involving partial writes to a register
together completely killing a wider register is interesting and did not occur to
me. But, for reaching definitions, even if you do not detect this case,
shouldn't this be safe (although conservative) since you would only end up
over-estimating the set of reaching definitions at a point?
> 
> But for other scenarios such as copy propagation, you may need to detect
this scenario because otherwise you could assume that a copy reaches a use point
(when it actually does not) and you may end up propagating the copy when it is
incorrect to do so.
> 
> Regards,
> Venu.
> 
> 
> -----Original Message-----
> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
Krzysztof Parzyszek via llvm-dev
> Sent: Friday, September 8, 2017 7:10 PM
> To: llvm-dev at lists.llvm.org
> Subject: Re: [llvm-dev] Reaching definitions on Machine IR post register
allocation
> 
> It would be much easier to add extra reg units to EAX, EBX, etc. to
represent the upper half of the register. That would fix the issue the right way
(and would actually make sense without the context of RDF).
> 
> Regarding the sub-register check---consider this case:
> 
>   AX = ...
>   ...
>   AL = ...  // AX partially overwritten
>   AH = ...  // AX completely overwritten
> 
> Each of the assignments to AL/AH does not overwrite AX by itself, but
together they do. This would be very difficult to detect if we added such
special treatment of sub-registers that you propose.
> 
> I could try to make a case for the extra register units to get them added.
> 
> -Krzysztof
> 
> 
> On 9/8/2017 1:55 AM, Raghavan, Venugopal via llvm-dev wrote:
>> Hi Krzysztof,
>> 
>> Thanks for your explanation - I think I understand the issue now.
>> 
>> I do know if this is a hack, but, in reaching definitions, when we
check if a definition of AX kills a previous definition of EAX, can we not check
the actual physical register? In this case since EAX and AX are different
(although I understand AX is a sub-register of EAX), can we not conclude that
the definition of AX does not kill EAX? Since, in reaching definitions, it is
conservative if we over-estimate the set of reaching definitions (but not
unsafe), should not this strategy be adequate to avoid incorrect optimizations?
>> 
>> Or, is there an optimization that can behave incorrectly with an
overestimated set of reaching definitions?
>> 
>> Regards,
>> Venu.
>> 
>> -----Original Message-----
>> From: Nema, Ashutosh
>> Sent: Friday, September 08, 2017 12:00 PM
>> To: Raghavan, Venugopal <Venugopal.Raghavan at amd.com>
>> Subject: FW: [llvm-dev] Reaching definitions on Machine IR post 
>> register allocation
>> 
>> 
>> 
>> -----Original Message-----
>> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
>> Krzysztof Parzyszek via llvm-dev
>> Sent: Wednesday, September 6, 2017 6:10 PM
>> To: llvm-dev at lists.llvm.org
>> Subject: Re: [llvm-dev] Reaching definitions on Machine IR post 
>> register allocation
>> 
>> RDF needs to know when an assignment to a register is overwritten by
another assignment, or by a sequence of assignments.  This is needed to
determine whether the original assignment is still live or not. RDF uses
register units to represent the building blocks of registers, and assumes that
if all units of a register are overwritten, then the original value of that
register is completely overwritten. This assumption is true for all targets
(that I have tested it with) except X86. On X86, registers AX and EAX both have
only one register unit, but when you assign a value to AX, the upper half of EAX
is preserved (that is, the original value of EAX is not completely overwritten).
>> 
>> -Krzysztof
>> 
>> On 9/6/2017 6:42 AM, Raghavan, Venugopal via llvm-dev wrote:
>>> Hi Krzysztof,
>>> 
>>> I did look at the other link you have mentioned in your reply but
did not quite understand the register units issue. If it is not too difficult,
can you briefly summarize what the issue was?
>>> 
>>> Thanks.
>>> 
>>> Regards,
>>> Venu.
>>> 
>>> 
>>> -----Original Message-----
>>> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On
Behalf Of
>>> Krzysztof Parzyszek via llvm-dev
>>> Sent: Tuesday, September 5, 2017 7:44 PM
>>> To: llvm-dev at lists.llvm.org
>>> Subject: Re: [llvm-dev] Reaching definitions on Machine IR post 
>>> register allocation
>>> 
>>> Hexagon has RDF that does exactly that.  At the moment it's
under lib/Target/Hexagon, but it meant to be target-independent.  It won't
work with X86 due to a known issue related to register units, but it should work
fine for other targets.  See https://reviews.llvm.org/D29295 about moving it to
lib/CodeGen.
>>> 
>>> -Krzysztof
>>> 
>>> On 9/4/2017 9:00 AM, Raghavan, Venugopal via llvm-dev wrote:
>>>> Hi,
>>>> 
>>>> Just to clarify I am looking for a whole machine function
analysis
>>>> not just something restricted to within a machine basic block.
>>>> 
>>>> Thanks.
>>>> 
>>>> Regards,
>>>> 
>>>> Venu.
>>>> 
>>>> *From:* Raghavan, Venugopal
>>>> *Sent:* Saturday, September 02, 2017 12:56 PM
>>>> *To:* llvm-dev at lists.llvm.org
>>>> *Subject:* Reaching definitions on Machine IR post register 
>>>> allocation
>>>> 
>>>> Hi,
>>>> 
>>>> Given a definition of a register by a machine instruction in
the
>>>> Machine IR post register allocation, I would like to compute
the set
>>>> of uses of this register reached by this definition.
>>>> 
>>>> Does LLVM already have this kind of analysis I can use?
Otherwise, I
>>>> will have to implement a reaching definitions analysis which
would
>>>> be a little involved since it would need to work on a non-SSA
IR form.
>>>> 
>>>> If something already exists that would be very helpful for me.
>>>> 
>>>> Thanks.
>>>> 
>>>> Regards,
>>>> 
>>>> Venugopal Raghavan.
>>>> 
>>>> 
>>>> 
>>>> _______________________________________________
>>>> 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 
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>> _______________________________________________
>>> 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 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>> _______________________________________________
>> 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 _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev