[InstCombine] Optimize and of icmps with power-of-2 and contiguous masks

[jmciver]

Summary

Add an instance combine optimization for expressions of the form:

(%arg u< C1) & ((%arg & C2) != C2) -> %arg u< C2

Where C1 is a power-of-2 and C2 is a contiguous mask starting 1 bit below C1.

This commit resolves GitHub missed-optimization issue #54856.

[jmciver]

All six reported failing tests (due to timeouts) are passing locally in my build/test environment.

[jmciver]

Fix capitzalation of function names containing ICMP

[jmciver]

Based on functionality of the optimization I believe foldLogOpOfMaskedICmps to be a reasonable location. However, it maybe better to create a new function and call it from InstCombinerImpl::foldAndOrOfICmps based on the following.

The placement of the call to foldLogOpOfMaskedICmps_AllZeros_BMask_NotMixed_and_NotAllOnes in the function foldLogOpOfMaskedICmps breaks the consistency of the conditional testing based on the conjunction of left and right mask (see variable Mask line 586). It is possible to place calls to foldLogOpOfMaskedICmps_AllZeros_BMask_NotMixed_and_NotAllOnes in two locations in foldLogOpOfMaskedICmps:

• In function foldLogOpOfMaskedIcmpsAsymmetric called from conditional block Mask == 0 (line 593)
• In conditional block Mask & (Mask_NotAllZeros | BMask_NotAllOnes (line 655)

I opted against this due to readability.

Thanks in advance for any feedback!

[jmciver]

To reduce performance impact I am thinking that the call to foldLogOpOfMaskedICmps_AllZeros_BMask_NotMixed_and_NotAllOnes should be moved into a new function, foldPowerOf2AndWithLesserContinuous, and then call this function from foldAndOrOfICmps. This will help to keep the purpose of foldLogOpOfMaskedICmps clear and reduce the overhead by not testing for a less probable optimization early.

[RKSimon]

Please can you add vector test coverage - uniform / non-uniform cases and cases containing undef / poison elements

[jmciver]

Thanks @RKSimon! I will work on adding the additional tests.

[jmciver]

As per @RKSimon's feedback I have discovered a number of vector deficiencies in my implementation.

From reading https://developers.redhat.com/articles/2022/12/20/how-contribute-llvm# (which is excellent) I have a better understanding of how to structure this patch. I am currently working on further vector test case generation and will post it as a parent to this patch in the next day or so.