Lowering `~x | (x - 1)` to `~blsi(x)` by user1342234 · Pull Request #186722 · llvm/llvm-project

user1342234 · 2026-03-16T01:49:40Z

Alive2 proof:
https://alive2.llvm.org/ce/z/bK93Cn

I've implemented a fold in InstCombineAndOrXor.cpp to canonicalize ~x | (x - 1) to ~(x & -x) which enables the CodeGen to emit the blsi instruction.

I've also added a test in CodeGen/X86 though I'm not sure if it's required or not.

Fixes #184055

github-actions · 2026-03-16T01:49:59Z

Thank you for submitting a Pull Request (PR) to the LLVM Project!

This PR will be automatically labeled and the relevant teams will be notified.

If you wish to, you can add reviewers by using the "Reviewers" section on this page.

If this is not working for you, it is probably because you do not have write permissions for the repository. In which case you can instead tag reviewers by name in a comment by using @ followed by their GitHub username.

If you have received no comments on your PR for a week, you can request a review by "ping"ing the PR by adding a comment “Ping”. The common courtesy "ping" rate is once a week. Please remember that you are asking for valuable time from other developers.

If you have further questions, they may be answered by the LLVM GitHub User Guide.

You can also ask questions in a comment on this PR, on the LLVM Discord or on the forums.

llvmbot · 2026-03-16T01:50:32Z

@llvm/pr-subscribers-llvm-transforms

Author: Abu (user1342234)

Changes

Alive2 proof:
https://alive2.llvm.org/ce/z/bK93Cn

I've implemented a fold in InstCombineAndOrXor.cpp to canonicalize ~x | (x - 1) to (x & -x) which enables the CodeGen to emit the blsi instruction.

I've also added a test in CodeGen/X86 though I'm not sure if it's required or not.

Fixes #184055

Full diff: https://github.com/llvm/llvm-project/pull/186722.diff

3 Files Affected:

(modified) llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp (+10)
(added) llvm/test/CodeGen/X86/fold-bmi.ll (+14)
(added) llvm/test/Transforms/InstCombine/fold-bmi.ll (+66)

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
index 4c8c708fba986..97f1558a29f3e 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -4208,6 +4208,16 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) {
     return BinaryOperator::CreateMul(X, IncrementY);
   }
 
+  // Canonicalization to achieve lowering to Bit Manipulation Instructions (BMI)
+  // ~X | (X-1) => (X & -X)
+  Value *Op;
+  if (match(&I, m_c_Or(m_OneUse(m_Not(m_Value(Op))),
+                       m_OneUse(m_Add(m_Deferred(Op), m_AllOnes()))))) {
+    Value *NegX = Builder.CreateNeg(Op);
+    Value *And = Builder.CreateAnd(Op, NegX);
+    return BinaryOperator::CreateNot(And);
+  }
+
   // (C && A) || (C && B) => select C, A, B (and similar cases)
   //
   // Note: This is the same transformation used in `foldSelectOfBools`,
diff --git a/llvm/test/CodeGen/X86/fold-bmi.ll b/llvm/test/CodeGen/X86/fold-bmi.ll
new file mode 100644
index 0000000000000..c4a4d1047f130
--- /dev/null
+++ b/llvm/test/CodeGen/X86/fold-bmi.ll
@@ -0,0 +1,14 @@
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py UTC_ARGS: --version 6
+; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+bmi -filetype=asm | FileCheck %s
+
+define i64 @foo(i64 %x) {
+; CHECK-LABEL: foo:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    blsiq %rdi, %rax
+; CHECK-NEXT:    notq %rax
+; CHECK-NEXT:    retq
+  %neg = sub i64 0, %x
+  %and = and i64 %x, %neg
+  %not = xor i64 %and, -1
+  ret i64 %not
+}
diff --git a/llvm/test/Transforms/InstCombine/fold-bmi.ll b/llvm/test/Transforms/InstCombine/fold-bmi.ll
new file mode 100644
index 0000000000000..ca07d45c65519
--- /dev/null
+++ b/llvm/test/Transforms/InstCombine/fold-bmi.ll
@@ -0,0 +1,66 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6
+; RUN: opt -passes=instcombine -S < %s | FileCheck %s
+
+define i64 @test(i64 %x) {
+; CHECK-LABEL: define i64 @foo(
+; CHECK-SAME: i64 [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 0, [[X]]
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[X]], [[TMP1]]
+; CHECK-NEXT:    [[NOT:%.*]] = xor i64 [[AND]], -1
+; CHECK-NEXT:    ret i64 [[NOT]]
+;
+  %xor = xor i64 %x, -1
+  %add = add i64 %x, -1
+  %or  = or i64 %xor, %add
+  ret i64 %or
+}
+
+define i64 @commutative(i64 %x) {
+; CHECK-LABEL: define i64 @commutative(
+; CHECK-SAME: i64 [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 0, [[X]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[X]], [[TMP1]]
+; CHECK-NEXT:    [[OR:%.*]] = xor i64 [[TMP2]], -1
+; CHECK-NEXT:    ret i64 [[OR]]
+;
+  %xor = xor i64 %x, -1
+  %add = add i64 %x, -1
+  %or  = or i64 %add, %xor
+  ret i64 %or
+}
+
+
+; NEGATIVE TEST: add has multiple uses
+define i64 @negative_multiuse_add(i64 %x, ptr %p) {
+; CHECK-LABEL: define i64 @negative_multiuse_add(
+; CHECK-SAME: i64 [[X:%.*]], ptr [[P:%.*]]) {
+; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[X]], -1
+; CHECK-NEXT:    [[ADD:%.*]] = add i64 [[X]], -1
+; CHECK-NEXT:    store i64 [[ADD]], ptr [[P]], align 4
+; CHECK-NEXT:    [[OR:%.*]] = or i64 [[ADD]], [[XOR]]
+; CHECK-NEXT:    ret i64 [[OR]]
+;
+  %xor = xor i64 %x, -1
+  %add = add i64 %x, -1
+  store i64 %add, ptr %p     ; second use of %add
+  %or  = or i64 %add, %xor
+  ret i64 %or
+}
+
+; NEGATIVE TEST: xor has multiple uses
+define i64 @negative_multiuse_xor(i64 %x, ptr %p) {
+; CHECK-LABEL: define i64 @negative_multiuse_xor(
+; CHECK-SAME: i64 [[X:%.*]], ptr [[P:%.*]]) {
+; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[X]], -1
+; CHECK-NEXT:    [[ADD:%.*]] = add i64 [[X]], -1
+; CHECK-NEXT:    store i64 [[XOR]], ptr [[P]], align 4
+; CHECK-NEXT:    [[OR:%.*]] = or i64 [[ADD]], [[XOR]]
+; CHECK-NEXT:    ret i64 [[OR]]
+;
+  %xor = xor i64 %x, -1
+  %add = add i64 %x, -1
+  store i64 %xor, ptr %p     ; second use of %xor
+  %or  = or i64 %add, %xor
+  ret i64 %or
+}
+

llvmbot · 2026-03-16T01:50:33Z

@llvm/pr-subscribers-backend-x86

Author: Abu (user1342234)

Changes

Alive2 proof:
https://alive2.llvm.org/ce/z/bK93Cn

I've implemented a fold in InstCombineAndOrXor.cpp to canonicalize ~x | (x - 1) to (x & -x) which enables the CodeGen to emit the blsi instruction.

I've also added a test in CodeGen/X86 though I'm not sure if it's required or not.

Fixes #184055

Full diff: https://github.com/llvm/llvm-project/pull/186722.diff

3 Files Affected:

(modified) llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp (+10)
(added) llvm/test/CodeGen/X86/fold-bmi.ll (+14)
(added) llvm/test/Transforms/InstCombine/fold-bmi.ll (+66)

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
index 4c8c708fba986..97f1558a29f3e 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -4208,6 +4208,16 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) {
     return BinaryOperator::CreateMul(X, IncrementY);
   }
 
+  // Canonicalization to achieve lowering to Bit Manipulation Instructions (BMI)
+  // ~X | (X-1) => (X & -X)
+  Value *Op;
+  if (match(&I, m_c_Or(m_OneUse(m_Not(m_Value(Op))),
+                       m_OneUse(m_Add(m_Deferred(Op), m_AllOnes()))))) {
+    Value *NegX = Builder.CreateNeg(Op);
+    Value *And = Builder.CreateAnd(Op, NegX);
+    return BinaryOperator::CreateNot(And);
+  }
+
   // (C && A) || (C && B) => select C, A, B (and similar cases)
   //
   // Note: This is the same transformation used in `foldSelectOfBools`,
diff --git a/llvm/test/CodeGen/X86/fold-bmi.ll b/llvm/test/CodeGen/X86/fold-bmi.ll
new file mode 100644
index 0000000000000..c4a4d1047f130
--- /dev/null
+++ b/llvm/test/CodeGen/X86/fold-bmi.ll
@@ -0,0 +1,14 @@
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py UTC_ARGS: --version 6
+; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+bmi -filetype=asm | FileCheck %s
+
+define i64 @foo(i64 %x) {
+; CHECK-LABEL: foo:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    blsiq %rdi, %rax
+; CHECK-NEXT:    notq %rax
+; CHECK-NEXT:    retq
+  %neg = sub i64 0, %x
+  %and = and i64 %x, %neg
+  %not = xor i64 %and, -1
+  ret i64 %not
+}
diff --git a/llvm/test/Transforms/InstCombine/fold-bmi.ll b/llvm/test/Transforms/InstCombine/fold-bmi.ll
new file mode 100644
index 0000000000000..ca07d45c65519
--- /dev/null
+++ b/llvm/test/Transforms/InstCombine/fold-bmi.ll
@@ -0,0 +1,66 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6
+; RUN: opt -passes=instcombine -S < %s | FileCheck %s
+
+define i64 @test(i64 %x) {
+; CHECK-LABEL: define i64 @foo(
+; CHECK-SAME: i64 [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 0, [[X]]
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[X]], [[TMP1]]
+; CHECK-NEXT:    [[NOT:%.*]] = xor i64 [[AND]], -1
+; CHECK-NEXT:    ret i64 [[NOT]]
+;
+  %xor = xor i64 %x, -1
+  %add = add i64 %x, -1
+  %or  = or i64 %xor, %add
+  ret i64 %or
+}
+
+define i64 @commutative(i64 %x) {
+; CHECK-LABEL: define i64 @commutative(
+; CHECK-SAME: i64 [[X:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 0, [[X]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[X]], [[TMP1]]
+; CHECK-NEXT:    [[OR:%.*]] = xor i64 [[TMP2]], -1
+; CHECK-NEXT:    ret i64 [[OR]]
+;
+  %xor = xor i64 %x, -1
+  %add = add i64 %x, -1
+  %or  = or i64 %add, %xor
+  ret i64 %or
+}
+
+
+; NEGATIVE TEST: add has multiple uses
+define i64 @negative_multiuse_add(i64 %x, ptr %p) {
+; CHECK-LABEL: define i64 @negative_multiuse_add(
+; CHECK-SAME: i64 [[X:%.*]], ptr [[P:%.*]]) {
+; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[X]], -1
+; CHECK-NEXT:    [[ADD:%.*]] = add i64 [[X]], -1
+; CHECK-NEXT:    store i64 [[ADD]], ptr [[P]], align 4
+; CHECK-NEXT:    [[OR:%.*]] = or i64 [[ADD]], [[XOR]]
+; CHECK-NEXT:    ret i64 [[OR]]
+;
+  %xor = xor i64 %x, -1
+  %add = add i64 %x, -1
+  store i64 %add, ptr %p     ; second use of %add
+  %or  = or i64 %add, %xor
+  ret i64 %or
+}
+
+; NEGATIVE TEST: xor has multiple uses
+define i64 @negative_multiuse_xor(i64 %x, ptr %p) {
+; CHECK-LABEL: define i64 @negative_multiuse_xor(
+; CHECK-SAME: i64 [[X:%.*]], ptr [[P:%.*]]) {
+; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[X]], -1
+; CHECK-NEXT:    [[ADD:%.*]] = add i64 [[X]], -1
+; CHECK-NEXT:    store i64 [[XOR]], ptr [[P]], align 4
+; CHECK-NEXT:    [[OR:%.*]] = or i64 [[ADD]], [[XOR]]
+; CHECK-NEXT:    ret i64 [[OR]]
+;
+  %xor = xor i64 %x, -1
+  %add = add i64 %x, -1
+  store i64 %xor, ptr %p     ; second use of %xor
+  %or  = or i64 %add, %xor
+  ret i64 %or
+}
+

github-actions · 2026-03-16T09:46:58Z

🪟 Windows x64 Test Results

132407 tests passed
3011 tests skipped

✅ The build succeeded and all tests passed.

github-actions · 2026-03-16T09:46:58Z

🐧 Linux x64 Test Results

192343 tests passed
4935 tests skipped

✅ The build succeeded and all tests passed.

RKSimon · 2026-03-16T10:10:20Z

+  %and = and i64 %x, %neg
+  %not = xor i64 %and, -1
+  ret i64 %not
+}


please can you put this inside bmi.ll instead (renamed blsi64_not()) and add a blsi32_not variant as well - keep it with the other the blsi patterns inside bmi.ll

Done, thanks

Co-authored-by: Tim Gymnich <[email protected]>

user1342234 · 2026-03-17T01:49:24Z

Pushed changes to fix failing test and moved fold-bmi.ll into bmi.ll.

RKSimon

a few minors

RKSimon

LGTM

@dtcxzyw are the instcombine changes OK?

dtcxzyw

LG

github-actions · 2026-03-19T12:46:18Z

@user1342234 Congratulations on having your first Pull Request (PR) merged into the LLVM Project!

Your changes will be combined with recent changes from other authors, then tested by our build bots. If there is a problem with a build, you may receive a report in an email or a comment on this PR.

Please check whether problems have been caused by your change specifically, as the builds can include changes from many authors. It is not uncommon for your change to be included in a build that fails due to someone else's changes, or infrastructure issues.

How to do this, and the rest of the post-merge process, is covered in detail here.

If your change does cause a problem, it may be reverted, or you can revert it yourself. This is a normal part of LLVM development. You can fix your changes and open a new PR to merge them again.

If you don't get any reports, no action is required from you. Your changes are working as expected, well done!

Lowering ~x | (x - 1)to ~blsi(x)`

92e4a56

user1342234 requested a review from nikic as a code owner March 16, 2026 01:49

llvmbot added backend:X86 llvm:instcombine Covers the InstCombine, InstSimplify and AggressiveInstCombine passes llvm:transforms labels Mar 16, 2026

tgymnich reviewed Mar 16, 2026

View reviewed changes

Comment thread llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp Outdated

RKSimon reviewed Mar 16, 2026

View reviewed changes

user1342234 and others added 2 commits March 16, 2026 18:33

Fix comment

9fc72e4

Co-authored-by: Tim Gymnich <[email protected]>

Fixed failing test and merged fold-bmi.ll into bmi.ll

0d84345

user1342234 requested a review from RKSimon March 17, 2026 08:10

RKSimon reviewed Mar 17, 2026

View reviewed changes

Comment thread llvm/test/CodeGen/X86/bmi.ll Outdated

Comment thread llvm/test/Transforms/InstCombine/fold-bmi.ll Outdated

Comment thread llvm/test/Transforms/InstCombine/fold-bmi.ll

Added suggestions

221b06d

user1342234 requested a review from RKSimon March 19, 2026 04:34

RKSimon approved these changes Mar 19, 2026

View reviewed changes

dtcxzyw approved these changes Mar 19, 2026

View reviewed changes

dtcxzyw merged commit 1078a1d into llvm:main Mar 19, 2026
10 checks passed

nikic mentioned this pull request Jul 15, 2026

[X86] InstCombine change breaks blsic matching #209718

Closed

Uh oh!

Conversation

user1342234 commented Mar 16, 2026 • edited by dtcxzyw Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

github-actions Bot commented Mar 16, 2026

Uh oh!

llvmbot commented Mar 16, 2026

Uh oh!

llvmbot commented Mar 16, 2026

Uh oh!

Uh oh!

github-actions Bot commented Mar 16, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

🪟 Windows x64 Test Results

Uh oh!

github-actions Bot commented Mar 16, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

🐧 Linux x64 Test Results

Uh oh!

RKSimon Mar 16, 2026

Choose a reason for hiding this comment

Uh oh!

user1342234 Mar 17, 2026

Choose a reason for hiding this comment

Uh oh!

user1342234 commented Mar 17, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

RKSimon left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

RKSimon left a comment

Choose a reason for hiding this comment

Uh oh!

dtcxzyw left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

github-actions Bot commented Mar 19, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

user1342234 commented Mar 16, 2026 •

edited by dtcxzyw

Loading

github-actions Bot commented Mar 16, 2026 •

edited

Loading

github-actions Bot commented Mar 16, 2026 •

edited

Loading

user1342234 commented Mar 17, 2026 •

edited

Loading