[InstCombine] Handle known shl nsw sign bit in SimplifyDemanded

[nikic]

Summary

Ideally SimplifyDemanded should compute the same known bits as computeKnownBits(). This addresses one discrepancy, where ValueTracking is more powerful: If we have a shl nsw shift, we know that the sign bit of the input and output must be the same. If this results in a conflict, the result is poison.

This is implemented in https://github.com/llvm-mirror/llvm/blob/2c4ca6832fa6b306ee6a7010bfb80a3f2596f824/lib/Analysis/ValueTracking.cpp#L1175-L1179 and https://github.com/llvm-mirror/llvm/blob/2c4ca6832fa6b306ee6a7010bfb80a3f2596f824/lib/Analysis/ValueTracking.cpp#L904-L908.

This implements the same basic logic in SimplifyDemanded. It's slightly stronger, because I return undef instead of zero for the poison case (which is not an option inside ValueTracking).

As mentioned in https://reviews.llvm.org/D75801#inline-698484, we could detect undef in more cases, this just establishes parity with the existing logic.

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

if (match(I->getOperand(1), m_APInt(SA))) {
       if (IOp->hasNoSignedWrap())
         DemandedMaskIn.setHighBits(ShiftAmt+1);
       else if (IOp->hasNoUnsignedWrap())
         DemandedMaskIn.setHighBits(ShiftAmt);
 
       if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
         return I;
       assert(!Known.hasConflict() && "Bits known to be one AND zero?");
+
+      bool SignBitZero = Known.Zero.isSignBitSet();
+      bool SignBitOne = Known.One.isSignBitSet();
       Known.Zero <<= ShiftAmt;
       Known.One  <<= ShiftAmt;
       // low bits known zero.
       if (ShiftAmt)
         Known.Zero.setLowBits(ShiftAmt);
+
+      // If this shift has "nsw" keyword, then the result is either a poison
+      // value or has the same sign bit as the first operand.
+      if (IOp->hasNoSignedWrap()) {
+        if (SignBitZero)
+          Known.Zero.setSignBit();
+        else if (SignBitOne)
+          Known.One.setSignBit();
+        if (Known.hasConflict())
+          return UndefValue::get(I->getType());
+      }
     } else {
       computeKnownBits(I, Known, Depth, CxtI);
     }
     break;
   }
   case Instruction::LShr: {
     const APInt *SA;
     if (match(I->getOperand(1), m_APInt(SA))) {

llvm/test/Transforms/InstCombine/known-signbit-shift.ll

;
   %cmp = icmp slt i32 %shift, 0
   ret i1 %cmp
 }
 
 ; If sign bit is a known zero, it cannot be a known one.
 ; This test should not crash opt. The shift produces poison.
 define i32 @test_no_sign_bit_conflict1(i1 %b) {
 ; EXPENSIVE-OFF-LABEL: @test_no_sign_bit_conflict1(
-; EXPENSIVE-OFF-NEXT:    [[SEL:%.*]] = select i1 [[B:%.*]], i32 -2147221504, i32 -2147483648
-; EXPENSIVE-OFF-NEXT:    ret i32 [[SEL]]
+; EXPENSIVE-OFF-NEXT:    ret i32 undef
 ;
 ; EXPENSIVE-ON-LABEL: @test_no_sign_bit_conflict1(
 ; EXPENSIVE-ON-NEXT:    ret i32 0
 ;
   %sel = select i1 %b, i32 8193, i32 8192
   %mul = shl nsw i32 %sel, 18
   ret i32 %mul
 }
 
 ; If sign bit is a known one, it cannot be a known zero.
 ; This test should not crash opt. The shift produces poison.
 define i32 @test_no_sign_bit_conflict2(i1 %b) {
 ; EXPENSIVE-OFF-LABEL: @test_no_sign_bit_conflict2(
-; EXPENSIVE-OFF-NEXT:    [[SEL:%.*]] = select i1 [[B:%.*]], i32 2147221504, i32 2146959360
-; EXPENSIVE-OFF-NEXT:    ret i32 [[SEL]]
+; EXPENSIVE-OFF-NEXT:    ret i32 undef
 ;
 ; EXPENSIVE-ON-LABEL: @test_no_sign_bit_conflict2(
 ; EXPENSIVE-ON-NEXT:    ret i32 0
 ;
   %sel = select i1 %b, i32 -8193, i32 -8194
   %mul = shl nsw i32 %sel, 18
   ret i32 %mul
 }