From 485c4b552b71aff21fc27ce958c2d8ea4cebba99 Mon Sep 17 00:00:00 2001
From: Roman Lebedev <lebedev.ri@gmail.com>
Date: Tue, 2 Feb 2021 16:59:47 +0300
Subject: [PATCH] [InstCombine] Host inversion out of ashr's value operand
 (PR48995)

This is a yet another hint that we will eventually need InstCombineInverter,
which would consistently sink inversions, but but for that we'll need
to consistently hoist inversions where possible, so let's do that here.

Example of a proof: https://alive2.llvm.org/ce/z/78SbDq

See https://bugs.llvm.org/show_bug.cgi?id=48995
---
 llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp    |  9 +++++++++
 .../InstCombine/hoist-not-from-ashr-operand.ll           | 16 ++++++++--------
 2 files changed, 17 insertions(+), 8 deletions(-)

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp b/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
index 7295369..c444873 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
@@ -1320,5 +1320,14 @@ Instruction *InstCombinerImpl::visitAShr(BinaryOperator &I) {
   if (MaskedValueIsZero(Op0, APInt::getSignMask(BitWidth), 0, &I))
     return BinaryOperator::CreateLShr(Op0, Op1);
 
+  // ashr (xor %x, -1), %y  -->  xor (ashr %x, %y), -1
+  Value *X;
+  if (match(Op0, m_OneUse(m_Not(m_Value(X))))) {
+    // Note that we must drop 'exact'-ness of the shift!
+    // Note that we can't keep undef's in -1 vector constant!
+    auto *NewAShr = Builder.CreateAShr(X, Op1, Op0->getName() + ".not");
+    return BinaryOperator::CreateNot(NewAShr);
+  }
+
   return nullptr;
 }
diff --git a/llvm/test/Transforms/InstCombine/hoist-not-from-ashr-operand.ll b/llvm/test/Transforms/InstCombine/hoist-not-from-ashr-operand.ll
index 2504800..b14c4c2 100644
--- a/llvm/test/Transforms/InstCombine/hoist-not-from-ashr-operand.ll
+++ b/llvm/test/Transforms/InstCombine/hoist-not-from-ashr-operand.ll
@@ -11,8 +11,8 @@ declare void @use8(i8)
 ; Most basic positive test
 define i8 @t0(i8 %x, i8 %y) {
 ; CHECK-LABEL: @t0(
-; CHECK-NEXT:    [[NOT_X:%.*]] = xor i8 [[X:%.*]], -1
-; CHECK-NEXT:    [[ASHR:%.*]] = ashr i8 [[NOT_X]], [[Y:%.*]]
+; CHECK-NEXT:    [[NOT_X_NOT:%.*]] = ashr i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[ASHR:%.*]] = xor i8 [[NOT_X_NOT]], -1
 ; CHECK-NEXT:    ret i8 [[ASHR]]
 ;
   %not_x = xor i8 %x, -1
@@ -22,8 +22,8 @@ define i8 @t0(i8 %x, i8 %y) {
 ; 'exact'-ness isn't preserved!
 define i8 @t1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @t1(
-; CHECK-NEXT:    [[NOT_X:%.*]] = xor i8 [[X:%.*]], -1
-; CHECK-NEXT:    [[ASHR:%.*]] = ashr exact i8 [[NOT_X]], [[Y:%.*]]
+; CHECK-NEXT:    [[NOT_X_NOT:%.*]] = ashr i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[ASHR:%.*]] = xor i8 [[NOT_X_NOT]], -1
 ; CHECK-NEXT:    ret i8 [[ASHR]]
 ;
   %not_x = xor i8 %x, -1
@@ -33,8 +33,8 @@ define i8 @t1(i8 %x, i8 %y) {
 ; Basic vector test
 define <2 x i8> @t2_vec(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @t2_vec(
-; CHECK-NEXT:    [[NOT_X:%.*]] = xor <2 x i8> [[X:%.*]], <i8 -1, i8 -1>
-; CHECK-NEXT:    [[ASHR:%.*]] = ashr <2 x i8> [[NOT_X]], [[Y:%.*]]
+; CHECK-NEXT:    [[NOT_X_NOT:%.*]] = ashr <2 x i8> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[ASHR:%.*]] = xor <2 x i8> [[NOT_X_NOT]], <i8 -1, i8 -1>
 ; CHECK-NEXT:    ret <2 x i8> [[ASHR]]
 ;
   %not_x = xor <2 x i8> %x, <i8 -1, i8 -1>
@@ -44,8 +44,8 @@ define <2 x i8> @t2_vec(<2 x i8> %x, <2 x i8> %y) {
 ; Note that we must sanitize undef elts of -1 constant to -1 or 0.
 define <2 x i8> @t3_vec_undef(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @t3_vec_undef(
-; CHECK-NEXT:    [[NOT_X:%.*]] = xor <2 x i8> [[X:%.*]], <i8 -1, i8 undef>
-; CHECK-NEXT:    [[ASHR:%.*]] = ashr <2 x i8> [[NOT_X]], [[Y:%.*]]
+; CHECK-NEXT:    [[NOT_X_NOT:%.*]] = ashr <2 x i8> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[ASHR:%.*]] = xor <2 x i8> [[NOT_X_NOT]], <i8 -1, i8 -1>
 ; CHECK-NEXT:    ret <2 x i8> [[ASHR]]
 ;
   %not_x = xor <2 x i8> %x, <i8 -1, i8 undef>
-- 
2.7.4