[RFC] Pass return status

Hi folks,

Per the documentation[0], whenever an LLVM pass doesn't modify the IR it's run on, it
should return `false`--it's okay to return `true` if no change happen, just less
optimal. In the New PM area, this is generally translated into a `PreservedAnalyses::all()`.

https://reviews.llvm.org/D80916 provides an `EXPENSIVE_CHECK` that computes a
hash of the IR before and after the pass, and checks that any change is
correctly reported. The hash is currently incomplete (on purpose, let's start
small), but it turns out a dozen of passes do not satisfy that
requirement.

This could lead to various category of bugs (dangling references, inconsistent
state, etc). This affects both New and Legacy PM, as passes tend to wrap functions
that report their status.

I wrote a bunch of patches for all failure detected by this check, as I cannot land the
check now, it would break the buildbots :slight_smile: Any help to review the remaining
ones [1] is appreciated.

Once that check lands and we're relatively confident on the quality of the
return status, some more optimizations could be triggered, like
https://reviews.llvm.org/D80707.

[0] https://llvm.org/docs/WritingAnLLVMPass.html#the-runonmodule-method
[1] https://reviews.llvm.org/D81230
    https://reviews.llvm.org/D81236
    https://reviews.llvm.org/D81256
    https://reviews.llvm.org/D81238
    https://reviews.llvm.org/D81225

Hi,

I think this is a very useful addition.

Note that many passes using EXPENSIVE_CHECKS to verify themselves
still allow switching verification on using a command line option
(e.g. -verify-loop-info) where EXPENSIVE_CHECKS just controls the
default value. This is useful so it can be enabled explicitly e.g. in
regression tests for proper pass behavior.

Michael

Hi folks,

Per the documentation[0], whenever an LLVM pass doesn't modify the IR it's run on, it
should return `false`--it's okay to return `true` if no change happen, just less
optimal. In the New PM area, this is generally translated into a `PreservedAnalyses::all()`.

https://reviews.llvm.org/D80916 provides an `EXPENSIVE_CHECK` that computes a
hash of the IR before and after the pass, and checks that any change is
correctly reported. The hash is currently incomplete (on purpose, let's start
small), but it turns out a dozen of passes do not satisfy that
requirement.

This could lead to various category of bugs (dangling references, inconsistent
state, etc). This affects both New and Legacy PM, as passes tend to wrap functions
that report their status.

I wrote a bunch of patches for all failure detected by this check, as I cannot land the
check now, it would break the buildbots :slight_smile: Any help to review the remaining
ones [1] is appreciated.

Once that check lands and we're relatively confident on the quality of the
return status, some more optimizations could be triggered, like
https://reviews.llvm.org/D80707.

Wow, this is really cool. Thank you for working on this!

-Chris

Awesome feature! I am really fond of these pieces of infrastructure that can defend against human mistakes and save countless hours of debugging when subtle issues arise.

Thanks Serge,

Hi folks,

some more information on this feature - as a reminder I started one month ago to work on an expensive check that would verify that pass return status is correctly reported by passes, i.e. no pass return « IR not modified » while actually modifying it.
It took ~20 pass fixes to achieve that goal, as many passes were not respectful of that contract, but as of 3667d87a33d3c8d4072a41fd84bb880c59347dc0, https://reviews.llvm.org/D80916 has been merged in master and the check is active, which should prevent further regression on that topic.

Thanks a lot to @foad, @jdoerfert, @fhahn, @calixte (and others I’m sorry to forgot) for their help during the reviews.

some more information on this feature - as a reminder I started one month ago to work on an expensive check that would verify that pass return status is correctly reported by passes, i.e. no pass return « IR not modified » while actually modifying it.
It took ~20 pass fixes to achieve that goal, as many passes were not respectful of that contract, but as of 3667d87a33d3c8d4072a41fd84bb880c59347dc0, https://reviews.llvm.org/D80916 has been merged in master and the check is active, which should prevent further regression on that topic.

Awesome, thank you!

Cheers,
Nicolai

Hi folks,

some more information on this feature - as a reminder I started one month ago to work on an expensive check that would verify that pass return status is correctly reported by passes, i.e. no pass return « IR not modified » while actually modifying it.
It took ~20 pass fixes to achieve that goal, as many passes were not respectful of that contract, but as of 3667d87a33d3c8d4072a41fd84bb880c59347dc0, https://reviews.llvm.org/D80916 has been merged in master and the check is active, which should prevent further regression on that topic.

Thanks a lot to @foad, @jdoerfert, @fhahn, @calixte (and others I'm sorry to forgot) for their help during the reviews.

This is great news!

Some years ago, we did some experiments on whether we could develop more fixed-point optimization within LLVM's pipeline. This was not the only impediment we identified, but it was a major one.

Out of curiosity, does change here include changes to names, and other semantically-irrelevant changes (e.g., changing the order of operands in a PHI)?

-Hal

Out of curiosity, does change here include changes to names, and other semantically-irrelevant changes (e.g., changing the order of operands in a PHI)?

The hashing function used to detect changes is currently very simple: it only accounts for instruction opcode and order. So some semantically-irrelevant changes are ignored (as well as some relevant changes), and some are not.
Permuting two independant instructions is not ignored, while permuting the operands of a sub is ignored.

+1 This is definitely a useful feature.

Hashing functions would definitely get tricky over time. One way to encode it would be encoding CFG structure. Order of BBs in CFG coupled with order of instructions in each BB would be fairly fine, IMHO. Of course, such a hash function should be invoked when we want to preserve CFG. In addition to this, it could also be a post-order + pre-order traversal of DOM trees. However, more importantly, I think one hash function may not serve all the purpose. A hash function can be a part of AnalysisPass. Clients would invoke such a top-level wrapper to verify sanity of the analysis pass which in-turn calls pass specific hash function to do the job.

Hi folks,
Another follow-up on the pass return status checker started with https://reviews.llvm.org/D80916:

now that https://reviews.llvm.org/D86589 and https://reviews.llvm.org/D86442 have landed, Loop, Region and CallgraphSCC passes also have their return status checked.
This found a few extra ill-returned status, and thanks to skipping a few analyse recomputations, it also saves a CPU cycles.

I’ll take this as an opportunity to thank Johannes Doerfert, Jay Foad and Nikita Popov for their help on this work!