SimplifyCFG, llvm.loop and latch blocks

Project Infrastructure LLVM Dev List Archives
#1

Hi all,

LLVM Language Reference Manual — LLVM 16.0.0git documentation 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 Compiler Explorer 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.

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 ?
- Is it a correct assumption that we should not merge blocks if both have a branch instruction with a !llvm.loop annotation set ?

Thanks,

Jeroen Dobbelaere

#2

I think that metadata / annotation preservation isn’t perfect and is on a best-effort basis in general, unfortunately, as the IR spec may say that it’s okay to drop them. But contributions would be welcome to improve it.

#3

Hi Hiroshi,

thank you for the reply.

I am aware of the general rule that Metadata can be dropped.
I am wondering if that should still hold for (at least) some of the loop annotations.

In this particular case, there is also a 'real bug' where loop metadata indicating that a loop
that is 'progressing but should not be unrolled' is, after some transformations, suddenly attached to
a different, infinite loop (aka not progressing).

Greetings,

Jeroen Dobbelaere

#4

Yeah, certainly not ideal. Maybe worth filing a bug regardless?

#5

Preserving loop metadata like all metadata is only done on a
best-effort basis and there are several ways it can get disassociated
with the loop (see e.g. previous discussion
[llvm-dev] CFG manipulation and !llvm.loop metadata or
⚙ D95789 [SpeculateAroundPHIs] Avoid speculation on loop back edges). But that semantics, preservation is
just quality-of-implementation since we cannot make loop metadata
"more special" than other metadata. Which is unfortunate because some
loop properties can be seen as semantic requirement, such as the
vectorizer metadata that is emitted by `#pragma omp simd`. It should
not just be dropped without warning the user that the loop has not
been vectorized.

Michael

#6

Hi all,

LLVM Language Reference Manual — LLVM 16.0.0git documentation 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 Compiler Explorer 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 :frowning:

From what I can see, the loops, identified by their headers, have the following annotations before
and after those two passes (Compiler Explorer). 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

#7

Hi Johannes et al,

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 :frowning:

From what I can see, the loops, identified by their headers, have the
following annotations before
and after those two passes
(Compiler Explorer ).
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 Compiler Explorer

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

#8

Hi Johannes et al,

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 :frowning:

  From what I can see, the loops, identified by their headers, have the
following annotations before
and after those two passes
(Compiler Explorer ).
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 Compiler Explorer

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.

#9

I created 50060 – Loop latch info migrates to wrong loop. for this.

Thanks,

Jeroen Dobbelaere