[LLVMdev] Separating loop nests based on profile information?

[Philip Reames]

On 01/12/2015 10:35 AM, Mehdi Amini wrote:
>
>> On Jan 12, 2015, at 10:08 AM, Philip Reames 
>> <listmail at philipreames.com <mailto:listmail at philipreames.com>> wrote:
>>
>>
>> On 01/11/2015 10:35 PM, Daniel Berlin wrote:
>>>
>>>
>>>     Looking at what LLVM does, the failing on the PRE side is that
>>>     our PRE/GVN models are not strong enough to handle this. I'm not
>>>     sure at all why we think anything else is necessary.
>>>
>>>
>>> By this i mean we don't actually perform real PRE for loads. It's a 
>>> known deficiency and one that does not require any duplicate 
>>> heuristics to solve.
>>> Right now we perform some availability based removal that happens be 
>>> willing to do an insertion here or there to try to move a load in 
>>> some cases (it will only do a single insertion).  It's not also 
>>> based on real availability, but on finding nearest dependencies of 
>>> loads and squinting at them (which is not even really the same as 
>>> finding where a load stops being available) funny.
>>>
>>> It's also not real PRE, just some code that is willing to insert one 
>>> load to move a load.
>> Er, I think we have a terminology problem here.  From what I can 
>> gather, our current implementation *is* an implementation of classic 
>> PRE.  It's more or less directly organized around the classic 
>> "available" and "anticipated" concepts from the literature.  The 
>> *implementation* has some limitations, but the conceptual framework 
>> is there*. One of the key invariants in classic PRE is that you do 
>> not change program behaviour on any path.  As a result, moving (or at 
>> most duplicating) loads is pretty much all that happens.
>>
>> * It took me a few hours of squinting at the code to recognize that 
>> weird backwards walk as being an implementation of "anctipated", but 
>> it is.
>
> Did you add some comments? It may save a few hours of squinting to 
> someone else in the future :)
Not yet, but yes, I plan to.

Having said that, part of my trouble was that I didn't have the 
background to understand what I was seeing at first.  I had to go do 
some literature search and then things made (slightly) more sense.
>
> Mehdi
>
>
>
>> The "available" part comes from MemoryDependenceAnalysis and the 
>> forward dataflow algorithm based on those inputs.
>>
>> If you want to start inserting loads on paths which didn't previously 
>> have them - for example the loop preheader in your example in the 
>> previous email - this is not classic PRE as I'm familiar with it.  It 
>> can be very profitable and worthwhile, but is not classic PRE.   I'm 
>> not sure what this variant is known as in the literature.
>>
>> (If I'm being overly pedantic here, or just flat out wrong, please 
>> say so.  I'm still exploring related material and am trying to 
>> categorize things in my own head.)
>>
>> I think we actually in reasonable agreement that we do need to move 
>> beyond 'classic PRE' as I called it above. If you have specific 
>> suggestions, positive or negative examples, or other thoughts to 
>> share, I'd very much value the input.
>>>
>>> If you want this case to work, what you need is a real Load PRE 
>>> implementation, not one based on simple memdep based load moving.
>>>
>>> Trying to hack this one up with profile guided code duplication, 
>>> etc, to get it to kinda sorta work seems to me to be a bad idea.
>> Not sure I really agree here, but I'm open to pushing as far as we 
>> can with static heuristics first.  I suspect that's likely to be more 
>> stable w.r.t. optimization effect and applicable to more cases.
>>>
>>>     It's certainly not requiring special code duplication
>>>     heuristics, etc.
>>>
>>>     So either you are thinking of a case that is different from the
>>>     above, or I am seriously confused :)
>>>
>>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu> http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150112/78258703/attachment.html>