[llvm-dev] Reaching definitions on Machine IR post register allocation

Mon Oct 30 02:13:01 PDT 2017

Hi Krzysztof,

I am returning to this thread after a gap in time. I took some time to study the code in RDFGraph.cpp in the Hexagon directory.

I have a few questions. I hope you will not find it too much of a bother to answer them.

1) Does use node only support a single reaching def? If the RDF graph is constructed post-RA, the code is no longer in SSA form and is it not possible that multiple reaching defs reach a use node? For example, the same physical register RAX may be defined in the if branch and the else branch and can reach a common use node resulting in multiple reaching defs for a use node. How is this handled?
2) I am unable to locate the code that handles re-definition of the same register. I though "clobber" refers to such situations but the isClobbering() function which controls the setting of the "Clobbering" attribute seems to mainly handle function calls and not the re-definitions of registers through other types of instructions. How are such re-definitions handled?
3) My mental picture of reaching definitions analysis is the classical iterative data flow analysis approach which involves using the union operator as the join operator for the data flow information, but I do not see anything in the code that corresponds to such a notion. I am obviously way off the mark here, so, can you briefly explain the idea behind the reaching definitions analysis in the RDF code?
4) Assuming I have somehow fixed the register units issue for x86 (which you mentioned in a previous reply)  in the TableGen code by adding extra register units for x86, I am not sure how the preservation of the previous defined value through a partial over-write by a sub-register definition is handled in the RDF code. I looked at the isPreserving() function but that function seems to check whether the instruction is predicated or not which is a little confusing to me since the x86 case can create preservation of bits through non-predicated partial over-writes. So, how is the x86 situation handled?

I realize that I have asked too many questions, but, I hope you can briefly provide me some clarifications.

Thanks.

Regards,
Venugopal Raghavan.

-----Original Message-----
From: qcolombet at apple.com [mailto:qcolombet at apple.com] 
Sent: Tuesday, September 12, 2017 11:31 PM
To: Raghavan, Venugopal <Venugopal.Raghavan at amd.com>
Cc: llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] Reaching definitions on Machine IR post register allocation

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