Skip to content

[InstSimpify] Simplifying (xor (sub C_Mask, X), C_Mask) -> X #122552

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 3 commits into from
Jan 11, 2025
Merged

[InstSimpify] Simplifying (xor (sub C_Mask, X), C_Mask) -> X #122552

merged 3 commits into from
Jan 11, 2025

Conversation

@goldsteinn
Copy link
Contributor

@goldsteinn goldsteinn commented Jan 10, 2025 •
edited
Loading

  • [InstSimpify] Add tests for simplifying (xor (sub C_Mask, X), C_Mask); NFC
  • [InstSimpify] Simplifying (xor (sub C_Mask, X), C_Mask) -> X

Helps address regressions with folding clz(Pow2).

Proof: https://alive2.llvm.org/ce/z/zGwUBp

@goldsteinn goldsteinn requested a review from nikic as a code owner January 10, 2025 23:50
@goldsteinn goldsteinn requested a review from dtcxzyw January 10, 2025 23:50
@llvmbot llvmbot added llvm:instcombine Covers the InstCombine, InstSimplify and AggressiveInstCombine passes llvm:analysis Includes value tracking, cost tables and constant folding llvm:transforms labels Jan 10, 2025
@goldsteinn goldsteinn changed the title goldsteinn/subnuw xor simp [InstSimpify] Simplifying (xor (sub C_Mask, X), C_Mask) -> X Jan 10, 2025
@llvmbot
Copy link
Member

llvmbot commented Jan 10, 2025

@llvm/pr-subscribers-llvm-transforms

Author: None (goldsteinn)

Changes
  • [InstSimpify] Add tests for simplifying (xor (sub C_Mask, X), C_Mask); NFC
  • [InstSimpify] Simplifying (xor (sub C_Mask, X), C_Mask) -> X

Helps address regressions with folding clz(Pow2).

Proof: https://alive2.llvm.org/ce/z/zGwUBp

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

2 Files Affected:

  • (modified) llvm/lib/Analysis/InstructionSimplify.cpp (+16)
  • (added) llvm/test/Transforms/InstSimplify/subnuw-with-xor.ll (+118)
diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp
index 999386c0a04917..ef9454fd9c9ab2 100644
--- a/llvm/lib/Analysis/InstructionSimplify.cpp
+++ b/llvm/lib/Analysis/InstructionSimplify.cpp
@@ -871,6 +871,14 @@ static Value *simplifySubInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW,
   if (Value *V = simplifyByDomEq(Instruction::Sub, Op0, Op1, Q, MaxRecurse))
     return V;
 
+  // (sub nuw C_Mask, (xor X, C_Mask)) -> X
+  if (IsNUW) {
+    Value *X;
+    if (match(Op1, m_Xor(m_Value(X), m_Specific(Op0))) &&
+        match(Op0, m_CheckedInt([](const APInt &C) { return C.isMask(); })))
+      return X;
+  }
+
   return nullptr;
 }
 
@@ -2540,6 +2548,14 @@ static Value *simplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
   if (Value *V = simplifyByDomEq(Instruction::Xor, Op0, Op1, Q, MaxRecurse))
     return V;
 
+  // (xor (sub nuw C_Mask, X), C_Mask) -> X
+  {
+    Value *X;
+    if (match(Op0, m_NUWSub(m_Specific(Op1), m_Value(X))) &&
+        match(Op1, m_CheckedInt([](const APInt &C) { return C.isMask(); })))
+      return X;
+  }
+
   return nullptr;
 }
 
diff --git a/llvm/test/Transforms/InstSimplify/subnuw-with-xor.ll b/llvm/test/Transforms/InstSimplify/subnuw-with-xor.ll
new file mode 100644
index 00000000000000..a990e2f2ae394e
--- /dev/null
+++ b/llvm/test/Transforms/InstSimplify/subnuw-with-xor.ll
@@ -0,0 +1,118 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5
+; RUN: opt < %s -passes=instsimplify -S | FileCheck %s
+
+define i8 @xor_w_sub_fail_missing_nuw(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @xor_w_sub_fail_missing_nuw(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X]], 15
+; CHECK-NEXT:    [[R:%.*]] = sub nsw i8 15, [[XOR]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %xor = xor i8 %x, 15
+  %r = sub nsw i8 15, %xor
+  ret i8 %r
+}
+
+define i8 @xor_w_sub_fail_diff_values(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @xor_w_sub_fail_diff_values(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X]], 15
+; CHECK-NEXT:    [[R:%.*]] = sub nuw nsw i8 31, [[XOR]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %xor = xor i8 %x, 15
+  %r = sub nsw nuw i8 31, %xor
+  ret i8 %r
+}
+
+define i8 @xor_w_sub_fail_diff_values2(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @xor_w_sub_fail_diff_values2(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X]], 31
+; CHECK-NEXT:    [[R:%.*]] = sub nuw nsw i8 15, [[XOR]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %xor = xor i8 %x, 31
+  %r = sub nsw nuw i8 15, %xor
+  ret i8 %r
+}
+
+define i8 @xor_w_sub_fail_not_mask(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @xor_w_sub_fail_not_mask(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X]], 30
+; CHECK-NEXT:    [[R:%.*]] = sub nuw nsw i8 30, [[XOR]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %xor = xor i8 %x, 30
+  %r = sub nsw nuw i8 30, %xor
+  ret i8 %r
+}
+
+define i8 @xor_w_sub_okay(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @xor_w_sub_okay(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    ret i8 [[X]]
+;
+  %xor = xor i8 %x, 31
+  %r = sub nsw nuw i8 31, %xor
+  ret i8 %r
+}
+
+define i8 @sub_w_xor_fail_missing_nuw(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @sub_w_xor_fail_missing_nuw(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i8 15, [[X]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[SUB]], 15
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %sub = sub nsw i8 15, %x
+  %r = xor i8 %sub, 15
+  ret i8 %r
+}
+
+define i8 @sub_w_xor_fail_diff_values(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @sub_w_xor_fail_diff_values(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[SUB:%.*]] = sub nuw nsw i8 15, [[X]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[SUB]], 31
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %sub = sub nsw nuw i8 15, %x
+  %r = xor i8 %sub, 31
+  ret i8 %r
+}
+
+define i8 @sub_w_sub_fail_diff_values2(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @sub_w_sub_fail_diff_values2(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[SUB:%.*]] = sub nuw nsw i8 31, [[X]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[SUB]], 15
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %sub = sub nsw nuw i8 31, %x
+  %r = xor i8 %sub, 15
+  ret i8 %r
+}
+
+define i8 @sub_w_sub_fail_not_mask(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @sub_w_sub_fail_not_mask(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[SUB:%.*]] = sub nuw nsw i8 30, [[X]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[SUB]], 30
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %sub = sub nsw nuw i8 30, %x
+  %r = xor i8 %sub, 30
+  ret i8 %r
+}
+
+define i8 @sub_w_sub_okay(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @sub_w_sub_okay(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    ret i8 [[X]]
+;
+  %sub = sub nsw nuw i8 31, %x
+  %r = xor i8 %sub, 31
+  ret i8 %r
+}

@llvmbot
Copy link
Member

llvmbot commented Jan 10, 2025

@llvm/pr-subscribers-llvm-analysis

Author: None (goldsteinn)

Changes
  • [InstSimpify] Add tests for simplifying (xor (sub C_Mask, X), C_Mask); NFC
  • [InstSimpify] Simplifying (xor (sub C_Mask, X), C_Mask) -> X

Helps address regressions with folding clz(Pow2).

Proof: https://alive2.llvm.org/ce/z/zGwUBp

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

2 Files Affected:

  • (modified) llvm/lib/Analysis/InstructionSimplify.cpp (+16)
  • (added) llvm/test/Transforms/InstSimplify/subnuw-with-xor.ll (+118)
diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp
index 999386c0a04917..ef9454fd9c9ab2 100644
--- a/llvm/lib/Analysis/InstructionSimplify.cpp
+++ b/llvm/lib/Analysis/InstructionSimplify.cpp
@@ -871,6 +871,14 @@ static Value *simplifySubInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW,
   if (Value *V = simplifyByDomEq(Instruction::Sub, Op0, Op1, Q, MaxRecurse))
     return V;
 
+  // (sub nuw C_Mask, (xor X, C_Mask)) -> X
+  if (IsNUW) {
+    Value *X;
+    if (match(Op1, m_Xor(m_Value(X), m_Specific(Op0))) &&
+        match(Op0, m_CheckedInt([](const APInt &C) { return C.isMask(); })))
+      return X;
+  }
+
   return nullptr;
 }
 
@@ -2540,6 +2548,14 @@ static Value *simplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
   if (Value *V = simplifyByDomEq(Instruction::Xor, Op0, Op1, Q, MaxRecurse))
     return V;
 
+  // (xor (sub nuw C_Mask, X), C_Mask) -> X
+  {
+    Value *X;
+    if (match(Op0, m_NUWSub(m_Specific(Op1), m_Value(X))) &&
+        match(Op1, m_CheckedInt([](const APInt &C) { return C.isMask(); })))
+      return X;
+  }
+
   return nullptr;
 }
 
diff --git a/llvm/test/Transforms/InstSimplify/subnuw-with-xor.ll b/llvm/test/Transforms/InstSimplify/subnuw-with-xor.ll
new file mode 100644
index 00000000000000..a990e2f2ae394e
--- /dev/null
+++ b/llvm/test/Transforms/InstSimplify/subnuw-with-xor.ll
@@ -0,0 +1,118 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5
+; RUN: opt < %s -passes=instsimplify -S | FileCheck %s
+
+define i8 @xor_w_sub_fail_missing_nuw(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @xor_w_sub_fail_missing_nuw(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X]], 15
+; CHECK-NEXT:    [[R:%.*]] = sub nsw i8 15, [[XOR]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %xor = xor i8 %x, 15
+  %r = sub nsw i8 15, %xor
+  ret i8 %r
+}
+
+define i8 @xor_w_sub_fail_diff_values(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @xor_w_sub_fail_diff_values(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X]], 15
+; CHECK-NEXT:    [[R:%.*]] = sub nuw nsw i8 31, [[XOR]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %xor = xor i8 %x, 15
+  %r = sub nsw nuw i8 31, %xor
+  ret i8 %r
+}
+
+define i8 @xor_w_sub_fail_diff_values2(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @xor_w_sub_fail_diff_values2(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X]], 31
+; CHECK-NEXT:    [[R:%.*]] = sub nuw nsw i8 15, [[XOR]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %xor = xor i8 %x, 31
+  %r = sub nsw nuw i8 15, %xor
+  ret i8 %r
+}
+
+define i8 @xor_w_sub_fail_not_mask(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @xor_w_sub_fail_not_mask(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X]], 30
+; CHECK-NEXT:    [[R:%.*]] = sub nuw nsw i8 30, [[XOR]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %xor = xor i8 %x, 30
+  %r = sub nsw nuw i8 30, %xor
+  ret i8 %r
+}
+
+define i8 @xor_w_sub_okay(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @xor_w_sub_okay(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    ret i8 [[X]]
+;
+  %xor = xor i8 %x, 31
+  %r = sub nsw nuw i8 31, %xor
+  ret i8 %r
+}
+
+define i8 @sub_w_xor_fail_missing_nuw(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @sub_w_xor_fail_missing_nuw(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i8 15, [[X]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[SUB]], 15
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %sub = sub nsw i8 15, %x
+  %r = xor i8 %sub, 15
+  ret i8 %r
+}
+
+define i8 @sub_w_xor_fail_diff_values(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @sub_w_xor_fail_diff_values(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[SUB:%.*]] = sub nuw nsw i8 15, [[X]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[SUB]], 31
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %sub = sub nsw nuw i8 15, %x
+  %r = xor i8 %sub, 31
+  ret i8 %r
+}
+
+define i8 @sub_w_sub_fail_diff_values2(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @sub_w_sub_fail_diff_values2(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[SUB:%.*]] = sub nuw nsw i8 31, [[X]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[SUB]], 15
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %sub = sub nsw nuw i8 31, %x
+  %r = xor i8 %sub, 15
+  ret i8 %r
+}
+
+define i8 @sub_w_sub_fail_not_mask(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @sub_w_sub_fail_not_mask(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    [[SUB:%.*]] = sub nuw nsw i8 30, [[X]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[SUB]], 30
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %sub = sub nsw nuw i8 30, %x
+  %r = xor i8 %sub, 30
+  ret i8 %r
+}
+
+define i8 @sub_w_sub_okay(i8 range(i8 0, 16) %x) {
+; CHECK-LABEL: define i8 @sub_w_sub_okay(
+; CHECK-SAME: i8 range(i8 0, 16) [[X:%.*]]) {
+; CHECK-NEXT:    ret i8 [[X]]
+;
+  %sub = sub nsw nuw i8 31, %x
+  %r = xor i8 %sub, 31
+  ret i8 %r
+}

This was referenced Jan 11, 2025
Open
Closed
Closed
dtcxzyw
dtcxzyw approved these changes Jan 11, 2025
View reviewed changes
Copy link
Member

@dtcxzyw dtcxzyw left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM.

nikic
nikic approved these changes Jan 11, 2025
View reviewed changes
llvm/lib/Analysis/InstructionSimplify.cpp Outdated
if (IsNUW) {
Value *X;
if (match(Op1, m_Xor(m_Value(X), m_Specific(Op0))) &&
match(Op0, m_CheckedInt([](const APInt &C) { return C.isMask(); })))
Copy link
Contributor

@nikic nikic Jan 11, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
match(Op0, m_CheckedInt([](const APInt &C) { return C.isMask(); })))
match(Op0, m_LowBitMask())

llvm/lib/Analysis/InstructionSimplify.cpp Outdated
{
Value *X;
if (match(Op0, m_NUWSub(m_Specific(Op1), m_Value(X))) &&
match(Op1, m_CheckedInt([](const APInt &C) { return C.isMask(); })))
Copy link
Contributor

@nikic nikic Jan 11, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
match(Op1, m_CheckedInt([](const APInt &C) { return C.isMask(); })))
match(Op1, m_LowBitMask())

@goldsteinn goldsteinn merged commit cc995ad into llvm:main Jan 11, 2025
8 checks passed
BaiXilin pushed a commit to BaiXilin/llvm-project that referenced this pull request Jan 12, 2025
@goldsteinn @BaiXilin
[InstSimpify] Simplifying (xor (sub C_Mask, X), C_Mask) -> X (llv…
5d62fde 
…m#122552)

- **[InstSimpify] Add tests for simplifying `(xor (sub C_Mask, X),
C_Mask)`; NFC**
- **[InstSimpify] Simplifying `(xor (sub C_Mask, X), C_Mask)` -> `X`**

Helps address regressions with folding `clz(Pow2)`.

Proof: https://alive2.llvm.org/ce/z/zGwUBp
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@nikic nikic nikic approved these changes

@dtcxzyw dtcxzyw dtcxzyw approved these changes

Assignees

No one assigned

Labels

llvm:analysis Includes value tracking, cost tables and constant folding llvm:instcombine Covers the InstCombine, InstSimplify and AggressiveInstCombine passes llvm:transforms

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@goldsteinn @llvmbot @nikic @dtcxzyw