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

[Jeroen Dobbelaere via 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