[InstCombine] Missed optimization for the pattern ((a << 1) + b) - ((a+b) & a)

[XChy]

((a << 1) + b) - ((a + b) & a) can be folded to (a + b) | a.
Missed example: https://godbolt.org/z/boz84e85j
Alive2 Proof: https://alive2.llvm.org/ce/z/j_lETs
Let me know if you think it's an optimization opportunity, please.

[dtcxzyw]

What is your motivation for this pattern? Does it come from a real-world application?

[XChy]

What is your motivation for this pattern? Does it come from a real-world application?

No real-world motivation now. Actually, we are developing something like https://github.com/google/souper, and perform initial trials on peephole optimization. This issue is one of the results. Your feedback about what can be defined as missed optimization opportunity is important to me. Thanks.

[nikic]

The most reliable way to find "interesting" patterns is probably to start with real-world IR and find unoptimized patterns in it, rather than the other way around (i.e. generating patterns and then trying to determine whether they are interesting). That way you have positive proof that the pattern will improve at least one piece of real code...

But assuming we don't have any knowledge of real-world relevance, I think one criterion to look at is pattern complexity vs specificity. The pattern here is a complex one (involving five binary operators with exact operand requirements) and one that, as far as I can tell, doesn't really generalize to anything. That's the kind of pattern we usually do not want.

Compare this for example to #71789, which also has a very specific pattern that probably doesn't generalize, but it's also a very simple one.

Or compare it to #71533. The specific pattern there wouldn't be acceptable, but if you see this generalized to "KnownBits information implied by select used to simplify select arms", then that becomes a reasonable pattern to handle (though probably also technically also quite challenging).

[XChy]

@nikic @dtcxzyw, thanks for your feedback and explanation! It really helps with improving our work and methods. I will consider more about real-world application, complexity and specificity in future.