Jeroen Dobbelaere via llvm-dev
2021-Apr-13 16:06 UTC
[llvm-dev] SimplifyCFG, llvm.loop and latch blocks
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'dCan 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
Johannes Doerfert via llvm-dev
2021-Apr-13 18:34 UTC
[llvm-dev] SimplifyCFG, llvm.loop and latch blocks
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 >