From 96a3dfeb9303f2f2d26628bd08908554286895cf Mon Sep 17 00:00:00 2001
From: Simon Pilgrim <llvm-dev@redking.me.uk>
Date: Wed, 24 Feb 2021 18:03:05 +0000
Subject: [PATCH] Revert rGd65ddca83ff85c7345fe9a0f5a15750f01e38420 -
 "[ValueTracking] ComputeKnownBits - minimum leading/trailing zero bits in
 LSHR/SHL (PR44526)"

This is causing sanitizer test failures that I haven't been able to fix yet.
---
 llvm/lib/Analysis/ValueTracking.cpp                | 39 ++++++++++++++--------
 llvm/lib/Support/KnownBits.cpp                     | 19 -----------
 llvm/test/Transforms/InstSimplify/icmp-constant.ll |  2 +-
 3 files changed, 27 insertions(+), 33 deletions(-)

diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index 9e5c8b4..520c7f9 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -994,26 +994,30 @@ static void computeKnownBitsFromShiftOperator(
   bool ShiftAmtIsConstant = Known.isConstant();
   bool MaxShiftAmtIsOutOfRange = Known.getMaxValue().uge(BitWidth);
 
-  // Use the KF callback to get an initial knownbits approximation.
-  Known = KF(Known2, Known);
+  if (ShiftAmtIsConstant) {
+    Known = KF(Known2, Known);
 
-  // If the known bits conflict, this must be an overflowing left shift, so
-  // the shift result is poison.
-  if (Known.hasConflict()) {
-    Known.resetAll();
-    return;
-  }
+    // If the known bits conflict, this must be an overflowing left shift, so
+    // the shift result is poison. We can return anything we want. Choose 0 for
+    // the best folding opportunity.
+    if (Known.hasConflict())
+      Known.setAllZero();
 
-  // Constant shift amount - we're not going to improve on this.
-  if (ShiftAmtIsConstant)
     return;
+  }
 
   // If the shift amount could be greater than or equal to the bit-width of the
   // LHS, the value could be poison, but bail out because the check below is
   // expensive.
   // TODO: Should we just carry on?
-  if (MaxShiftAmtIsOutOfRange)
+  if (MaxShiftAmtIsOutOfRange) {
+    Known.resetAll();
     return;
+  }
+
+  // It would be more-clearly correct to use the two temporaries for this
+  // calculation. Reusing the APInts here to prevent unnecessary allocations.
+  Known.resetAll();
 
   // If we know the shifter operand is nonzero, we can sometimes infer more
   // known bits. However this is expensive to compute, so be lazy about it and
@@ -1053,9 +1057,10 @@ static void computeKnownBitsFromShiftOperator(
         Known, KF(Known2, KnownBits::makeConstant(APInt(32, ShiftAmt))));
   }
 
-  // If the known bits conflict, the result is poison.
+  // If the known bits conflict, the result is poison. Return a 0 and hope the
+  // caller can further optimize that.
   if (Known.hasConflict())
-    Known.resetAll();
+    Known.setAllZero();
 }
 
 static void computeKnownBitsFromOperator(const Operator *I,
@@ -1227,6 +1232,10 @@ static void computeKnownBitsFromOperator(const Operator *I,
     };
     computeKnownBitsFromShiftOperator(I, DemandedElts, Known, Known2, Depth, Q,
                                       KF);
+    // Trailing zeros of a right-shifted constant never decrease.
+    const APInt *C;
+    if (match(I->getOperand(0), m_APInt(C)))
+      Known.Zero.setLowBits(C->countTrailingZeros());
     break;
   }
   case Instruction::LShr: {
@@ -1235,6 +1244,10 @@ static void computeKnownBitsFromOperator(const Operator *I,
     };
     computeKnownBitsFromShiftOperator(I, DemandedElts, Known, Known2, Depth, Q,
                                       KF);
+    // Leading zeros of a left-shifted constant never decrease.
+    const APInt *C;
+    if (match(I->getOperand(0), m_APInt(C)))
+      Known.Zero.setHighBits(C->countLeadingZeros());
     break;
   }
   case Instruction::AShr: {
diff --git a/llvm/lib/Support/KnownBits.cpp b/llvm/lib/Support/KnownBits.cpp
index 0f87f22..d7265d0 100644
--- a/llvm/lib/Support/KnownBits.cpp
+++ b/llvm/lib/Support/KnownBits.cpp
@@ -187,25 +187,6 @@ KnownBits KnownBits::shl(const KnownBits &LHS, const KnownBits &RHS) {
     MinTrailingZeros = std::min(MinTrailingZeros, BitWidth);
   }
 
-  // If the maximum shift is in range, then find the common bits from all
-  // possible shifts.
-  APInt MaxShiftAmount = RHS.getMaxValue();
-  if (MaxShiftAmount.ult(BitWidth)) {
-    assert(MinShiftAmount.ult(MaxShiftAmount) && "Illegal shift range");
-    Known.Zero.setAllBits();
-    Known.One.setAllBits();
-    for (uint64_t ShiftAmt = MinShiftAmount.getZExtValue(),
-                  MaxShiftAmt = MaxShiftAmount.getZExtValue();
-         ShiftAmt <= MaxShiftAmt; ++ShiftAmt) {
-      KnownBits SpecificShift;
-      SpecificShift.Zero = LHS.Zero << ShiftAmt;
-      SpecificShift.One = LHS.One << ShiftAmt;
-      Known = KnownBits::commonBits(Known, SpecificShift);
-      if (Known.isUnknown())
-        break;
-    }
-  }
-
   Known.Zero.setLowBits(MinTrailingZeros);
   return Known;
 }
diff --git a/llvm/test/Transforms/InstSimplify/icmp-constant.ll b/llvm/test/Transforms/InstSimplify/icmp-constant.ll
index 9db63e6..f8d5bdc 100644
--- a/llvm/test/Transforms/InstSimplify/icmp-constant.ll
+++ b/llvm/test/Transforms/InstSimplify/icmp-constant.ll
@@ -799,7 +799,7 @@ define i1 @eq_shl_by_constant_produces_poison(i8 %x) {
 
 define i1 @eq_shl_by_variable_produces_poison(i8 %x) {
 ; CHECK-LABEL: @eq_shl_by_variable_produces_poison(
-; CHECK-NEXT:    ret i1 poison
+; CHECK-NEXT:    ret i1 false
 ;
   %clear_high_bit = and i8 %x, 127                 ; 0x7f
   %set_next_high_bits = or i8 %clear_high_bit, 112 ; 0x70
-- 
2.7.4