[InstCombine] Optimize and of icmps with power-of-2 and contiguous masks
authorJohn McIver <john.mciver.iii@gmail.com>
Fri, 9 Jun 2023 21:26:30 +0000 (15:26 -0600)
committerJohn McIver <john.mciver.iii@gmail.com>
Fri, 9 Jun 2023 22:07:01 +0000 (16:07 -0600)
commit1001f9031f3ed0ca2ff146889bf82c10cea149d5
tree32481d78842158ff9a1dab55e4044dda3b9b919c
parentea868d5748cef57aa88f4c96445a1fdfbdb3832d
[InstCombine] Optimize and of icmps with power-of-2 and contiguous masks

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.

Validation of scalar tests:
  - https://alive2.llvm.org/ce/z/JfKjiU
  - https://alive2.llvm.org/ce/z/AruHY_
  - https://alive2.llvm.org/ce/z/JAiR6t
  - https://alive2.llvm.org/ce/z/S2X2e5
  - https://alive2.llvm.org/ce/z/4cycdE
  - https://alive2.llvm.org/ce/z/NcDiLP

Validation of vector tests:
  - https://alive2.llvm.org/ce/z/ABY6tE
  - https://alive2.llvm.org/ce/z/BTJi3s
  - https://alive2.llvm.org/ce/z/3BKWpu
  - https://alive2.llvm.org/ce/z/RrAbkj
  - https://alive2.llvm.org/ce/z/nM6fsN

Reviewed By: goldstein.w.n

Differential Revision: https://reviews.llvm.org/D125717
llvm/include/llvm/IR/PatternMatch.h
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
llvm/test/Transforms/InstCombine/icmp-power2-and-icmp-shifted-mask.ll