[llvm-dev] SimplifyCFG, llvm.loop and latch blocks

[Johannes Doerfert via llvm-dev]

On 4/13/21 11:06 AM, Jeroen Dobbelaere wrote:
> Hi Johannes et al,
>
>> -----Original Message-----
>> From: Johannes Doerfert
>> Sent: Monday, April 12, 2021 00:05
>>
>> I follow the part about simplify CFG dropping information but I don't
>> see how loop-simplify moves
>> things to the wrong loop, not to say it couldn't, latches are associated
>> with loops but we annotat
>> e branches which are not :(
>>
>>   From what I can see, the loops, identified by their headers, have the
>> following annotations before
>> and after those two passes
>> (https://www.godbolt.org/z/xMn8K8a6G ).
>> What
>> am I missing here, do I need
>> more intermediate transformations?
>>
>> loop            | before                   | after
>> do.cond         | unroll count 2           | none
>> for.cond        | mustprogress, no-unroll  | mustprogress, no-unroll
>> for.cond1       | mustprogress             | mustprogress
>>
> An example of pass order (deduced from -O2) that shows the problem:
> --simplifycfg --sroa --simplifycfg  --instcombine --licm --simplifycfg --loop-simplify --loop-rotate --licm --simplifycfg --loop-simplify -loops -enable-new-pm=0
>
> See https://www.godbolt.org/z/EW95YjW8h
>
> It has following panes:
> - on the left: the source code
> - top right: the loop info after the passes mentioned above, except for the last '--loop-simplify'.
>    This shows that %for.cond.cleanup3 serves as a latch for two loops. (outer and middle)
> - middle right: same info, now with the last '--loop-simplify'. It states that '%do.body.loopexit' is
>    the latch for the outer loop.
> - bottom right: resulting code, corresponding to the 'middle right' pane. There you can see that
>    the '%do.body.loopexit' contains a branch with an annotation that was originally on the middle loop.
>    This annotation also states 'llvm.loop.mustprogress'.
>    The branch in the latch block for the middle loop (%for.cond.cleanup3) does not contain a loop annotation
>    any more.
>
Right. That shows the problem nicely. As mentioned before, latches are 
not tied to loops, which
is the core issue here.


>>> Questions:
>>> - The branch in 'do.cond' is simplified, but I have the impression that at
>> the same time, the loop annotation is omitted.
>>>     This sounds like a bug ?
>> It is a "usability bug" in simplify CFG. If the surviving edge of a
>> branch is the latch we could keep the annotation.
>> With the existing problem that latches are not tied to loops but
>> branches are not.
>>
>>
>>> - Is it a correct assumption that we should not merge blocks if both have a
>> branch instruction with a !llvm.loop annotation set ?
>>
>> I doubt this is a viable option, too many places to check a non-trivial
>> condition that is control flow dependent.
>
> I tried this out and, while fixing the observed loop annotation jumping issue, it has a severe impact on resulting code quality.
> One of the reasons being that almost every loop that clang produces has a loop annotation attached...

I don't believe this is a viable option anyway, too many places to keep 
track of this.


>
>
>> Instead, I think we might want to rethink the entire latch association
>> concept. Headers are unique, they have unique
>> terminators, maybe we should use those to avoid the situation in which
>> one branch defines two latches. That said, I'd
> Can metadata be attached to a basic block ?

I doubt it, but that is not a conceptual issue. I haven't checked the
current code but I took a trip down memory lane instead:

https://reviews.llvm.org/D19597


> Can loop headers end up being merged in some way ?

Loop headers are tied to loops, so sharing a header means it's the
same loop. Loop fusion exists but intuitively I'd say that it can handle 
mismatches in
annotations easily. I think the next step is to determine why latches were
chosen over headers, maybe we are overlooking something here.


>
>> need to go back to the original introduction of the metadata to
>> determine why latches were chosen over "headers".
>>
>> ~ Johannes
>>
> Thanks,
>
> Jeroen Dobbelaere
>