llvm dev - Apr 2021 - SimplifyCFG, llvm.loop and latch blocks

On 4/7/21 12:17 PM, Jeroen Dobbelaere via llvm-dev
wrote:
> Hi all,
>
> https://llvm.org/docs/LangRef.html#llvm-loop  states that a llvm.loop is
put on the
> 'branch instruction of the loop's latch block'.
>
> With 'SimplifyCFG', I have come in a situation where a !llvm.loop
is associated to
> a basicblock that is found to be a latch block for two different loops.
>
> The original annotation of one of those loops disappeared in the process.
> (See  https://www.godbolt.org/z/5r1T5e9fs  and look for the disappearing
!llvm.loop !10  in BB 'do.cond')
>
>
> Then later on,  'Canonicalize natural loops' splits the latch block
up, so that it now is only
> the latch block for a single loop, but the original annotation is moved to
the wrong loop.
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

>
> 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.
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
need to go back to the original introduction of the metadata to 
determine why latches were chosen over "headers".

~ Johannes

> Thanks,
>
> Jeroen Dobbelaere
>   
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

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.

> 
> >
> > 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...

> 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 ?
Can loop headers end up being merged in some way ?
> need to go back to the original introduction of the metadata to
> determine why latches were chosen over "headers".
> 
> ~ Johannes
> 
Thanks,

Jeroen Dobbelaere