From 8591640379ac9175a8a8493126ecf0b44e3bb4af Mon Sep 17 00:00:00 2001
From: Sanjay Patel <spatel@rotateright.com>
Date: Mon, 14 Jun 2021 12:10:48 -0400
Subject: [PATCH] [InstCombine] add DeMorgan folds for logical ops in select
 form

We canonicalized to these select patterns (poison-safe logic)
with D101191, so we need to reduce 'not' ops when possible
as we would with 'and'/'or' instructions.

This is shown in a secondary example in:
https://llvm.org/PR50389

https://alive2.llvm.org/ce/z/BvsESh
---
 .../Transforms/InstCombine/InstCombineSelect.cpp   | 13 +++++++++
 llvm/test/Transforms/InstCombine/select-and-or.ll  | 34 +++++++++++++---------
 2 files changed, 33 insertions(+), 14 deletions(-)

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
index f48cc90..2308cdfe 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
@@ -2705,6 +2705,19 @@ Instruction *InstCombinerImpl::visitSelectInst(SelectInst &SI) {
       return SelectInst::Create(FalseVal, One, TrueVal);
 
     Value *A, *B;
+
+    // DeMorgan in select form: !a && !b --> !(a || b)
+    // select !a, !b, false --> not (select a, true, b)
+    if (match(&SI, m_LogicalAnd(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
+        (CondVal->hasOneUse() || TrueVal->hasOneUse()))
+      return BinaryOperator::CreateNot(Builder.CreateSelect(A, One, B));
+
+    // DeMorgan in select form: !a || !b --> !(a && b)
+    // select !a, true, !b --> not (select a, b, false)
+    if (match(&SI, m_LogicalOr(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
+        (CondVal->hasOneUse() || FalseVal->hasOneUse()))
+      return BinaryOperator::CreateNot(Builder.CreateSelect(A, B, Zero));
+
     // select (select a, true, b), true, b -> select a, true, b
     if (match(CondVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&
         match(TrueVal, m_One()) && match(FalseVal, m_Specific(B)))
diff --git a/llvm/test/Transforms/InstCombine/select-and-or.ll b/llvm/test/Transforms/InstCombine/select-and-or.ll
index 9146f12..5d6352e 100644
--- a/llvm/test/Transforms/InstCombine/select-and-or.ll
+++ b/llvm/test/Transforms/InstCombine/select-and-or.ll
@@ -179,6 +179,8 @@ define i1 @logical_and_noundef_b(i1 %a, i1 noundef %b) {
   ret i1 %res
 }
 
+; (!x && !y) || x --> x || !y
+
 define i1 @not_not_true(i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_not_true(
 ; CHECK-NEXT:    [[NOTY:%.*]] = xor i1 [[Y:%.*]], true
@@ -191,11 +193,12 @@ define i1 @not_not_true(i1 %x, i1 %y) {
   ret i1 %r
 }
 
+; (!x && !y) --> !(x || y)
+
 define i1 @not_not_false(i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_not_false(
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i1 [[X:%.*]], true
-; CHECK-NEXT:    [[NOTY:%.*]] = xor i1 [[Y:%.*]], true
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[NOTX]], i1 [[NOTY]], i1 false
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = xor i1 [[TMP1]], true
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %notx = xor i1 %x, true
@@ -204,11 +207,12 @@ define i1 @not_not_false(i1 %x, i1 %y) {
   ret i1 %r
 }
 
+; (!x || !y) --> !(x && y)
+
 define i1 @not_true_not(i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_true_not(
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i1 [[X:%.*]], true
-; CHECK-NEXT:    [[NOTY:%.*]] = xor i1 [[Y:%.*]], true
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[NOTX]], i1 true, i1 [[NOTY]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 false
+; CHECK-NEXT:    [[R:%.*]] = xor i1 [[TMP1]], true
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %notx = xor i1 %x, true
@@ -217,6 +221,8 @@ define i1 @not_true_not(i1 %x, i1 %y) {
   ret i1 %r
 }
 
+; (!!x && !y) --> x && !y
+
 define i1 @not_false_not(i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_false_not(
 ; CHECK-NEXT:    [[NOTY:%.*]] = xor i1 [[Y:%.*]], true
@@ -248,8 +254,8 @@ define i1 @not_not_false_use1(i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_not_false_use1(
 ; CHECK-NEXT:    [[NOTX:%.*]] = xor i1 [[X:%.*]], true
 ; CHECK-NEXT:    call void @use(i1 [[NOTX]])
-; CHECK-NEXT:    [[NOTY:%.*]] = xor i1 [[Y:%.*]], true
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[NOTX]], i1 [[NOTY]], i1 false
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X]], i1 true, i1 [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = xor i1 [[TMP1]], true
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %notx = xor i1 %x, true
@@ -263,8 +269,8 @@ define i1 @not_true_not_use1(i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_true_not_use1(
 ; CHECK-NEXT:    [[NOTX:%.*]] = xor i1 [[X:%.*]], true
 ; CHECK-NEXT:    call void @use(i1 [[NOTX]])
-; CHECK-NEXT:    [[NOTY:%.*]] = xor i1 [[Y:%.*]], true
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[NOTX]], i1 true, i1 [[NOTY]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X]], i1 [[Y:%.*]], i1 false
+; CHECK-NEXT:    [[R:%.*]] = xor i1 [[TMP1]], true
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %notx = xor i1 %x, true
@@ -305,10 +311,10 @@ define i1 @not_not_true_use2(i1 %x, i1 %y) {
 
 define i1 @not_not_false_use2(i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_not_false_use2(
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i1 [[X:%.*]], true
 ; CHECK-NEXT:    [[NOTY:%.*]] = xor i1 [[Y:%.*]], true
 ; CHECK-NEXT:    call void @use(i1 [[NOTY]])
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[NOTX]], i1 [[NOTY]], i1 false
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y]]
+; CHECK-NEXT:    [[R:%.*]] = xor i1 [[TMP1]], true
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %notx = xor i1 %x, true
@@ -320,10 +326,10 @@ define i1 @not_not_false_use2(i1 %x, i1 %y) {
 
 define i1 @not_true_not_use2(i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_true_not_use2(
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i1 [[X:%.*]], true
 ; CHECK-NEXT:    [[NOTY:%.*]] = xor i1 [[Y:%.*]], true
 ; CHECK-NEXT:    call void @use(i1 [[NOTY]])
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[NOTX]], i1 true, i1 [[NOTY]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X:%.*]], i1 [[Y]], i1 false
+; CHECK-NEXT:    [[R:%.*]] = xor i1 [[TMP1]], true
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %notx = xor i1 %x, true
-- 
2.7.4