[ValueTracking] Take signedness into account for and/or ranges

[nikic]

Summary

While trying to extend D59386 to signed add/sub I ran into quite a few issues ... unfortunately our range handling is quite biased in favor of unsigned ranges right now and it'll be necessary to thread preferred signedness through various APIs to get reasonable results.

This is the first step in this direction. computeConstantRange() gets a preferred signedness flag, which is respected for and/or range calculations. InstSimplify calls computeConstantRange() with the signedness of the predicate. This allows us to simplify signed icmps of and/or in InstSimplify.

[lebedev.ri]

Ok, i have to ask.
Is there some alternative way that does not require passing ForSigned all the way?

• Operate on a single range, and reinterpret it somehow when we know the sign matters?
• Always track two ranges, and use the one we need?

[nikic]

In D59668#1440521, @lebedev.ri wrote:

Ok, i have to ask.
Is there some alternative way that does not require passing ForSigned all the way?

• Operate on a single range, and reinterpret it somehow when we know the sign matters?
• Always track two ranges, and use the one we need?

Good question! Let me start with what we can't do: It's not possible to have a single range and reinterpret it for signed and unsigned purposes. Taking the example of known bits 0b..00, we can either interpret this is an unsigned range [0b0000, 0b1100] or a signed range [0b1000, 0b0100]. Here is a drawing of the unsigned (u) and signed (s) ranges, as well as the values (x) which are actually possible:

0b0000  u s x
0b0001  u s
0b0010  u s
0b0011  u s
0b0100  u s x
0b0101  u
0b0110  u
0b0111  u
0b1000  u s x
0b1001  u s
0b1010  u s
0b1011  u s
0b1100  u s x
0b1101    s
0b1110    s
0b1111    s

As you can see, both ranges cover all the x's, but in different ways: One without wrapping the unsigned domain, the other without wrapping the signed domain. Once we've arrived at this representation, we can no longer switch between them, because we have lost the information that the sign bit can be arbitrary.

There are a couple of different ways we can deal with this:

1. As you have already suggested, we can store both signed and unsigned ranges and just use whichever will be more convenient in the end. This would work, but it has rather high costs. We'd have to store two ranges everywhere and perform all calculations on two ranges. In many cases both ranges would end up being the same -- while you can interpret a known bits result without fixed sign bit in two ways, there's no two ways to interpret a urem result.

2. Pass a preferred signedness flag, which is what is done here. This is already common practice in some other parts of the codebase that deal with ranges, e.g. SCEV passes a SignHint through the range-based functionality. A flag allows us to choose an appropriate range when beneficial, but all calculations are still performed on only one range. (As a sidenote: While SCEV just passes this flag through, for recursive operations you don't necessarily want to do that. If you are computing a umax range for a signed context, you will still want to compute the ranges of the umax operands as unsigned. This is something that has to be decided per-operation, there is no general signedness context for the whole calculation.)

3. Some kind of hybrid representation that is not based on pure ranges. For example, we could store that the first N bits are undetermined and only store the range for the lower BW-N bits. If N>0 this would allow recovering both the signed and unsigned ranges for the case above. I'm not sure how general this would be, as it wouldn't be able to handle cases where the signed and unsigned ranges are not the same after truncation. Of course, this would also require rewriting the entire ConstantRange machinery from scratch :)

[lebedev.ri]

llvm/test/Transforms/InstSimplify/icmp-constant.ll

495–503

This is a miscompile, i believe.
https://rise4fun.com/Alive/R6k

----------------------------------------
Optimization: 1

ERROR: Mismatch in values of i1 %z

Example:
%x i8 = 0x80 (128, -128)
%y i8 = 0x80 (128, -128)
Source value: 0x0 (0)
Target value: 0x1 (1, -1)

[nikic]

llvm/test/Transforms/InstSimplify/icmp-constant.ll

495–503

Wow, thanks for catching that! What I did with the lower bound for and here doesn't make sense, it should just be SignedMin, independent of the constant.

I'm wondering if I should maybe move these calculations to ConstantRange, so they can be independently (and exhaustively) tested. The calculations here are quite specific though, in that they compute the range when combining a full range and a single constant. Something like ConstantRange::forBinaryAndWithConst() and friends?

[lebedev.ri]

llvm/test/Transforms/InstSimplify/icmp-constant.ll

495–503

I'm not quite sure how to best expose that (ConstantRange::forBinaryAndWithConst()
is a reasonable intermediate solution), but i *really* *really* like the idea of
separating them into small functions with exhaustive test coverage.

[nikic]

I'm going to drop this for now -- the original motivation here went away with the signed intersection support. These changes still make sense to improve icmp instsimplify, but are also not super valuable in that instcombine can handle it.

llvm/include/llvm/Analysis/ValueTracking.h

class Value;
   /// Returns true if the arithmetic part of the \p II 's result is
   /// used only along the paths control dependent on the computation
   /// not overflowing, \p II being an <op>.with.overflow intrinsic.
   bool isOverflowIntrinsicNoWrap(const IntrinsicInst *II,
                                  const DominatorTree &DT);
 
 
   /// Determine the possible constant range of an integer or vector of integer
-  /// value. This is intended as a cheap, non-recursive check.
-  ConstantRange computeConstantRange(const Value *V, bool UseInstrInfo = true);
+  /// value. The ForSigned flag determines whether ranges that do not wrap in
+  /// the signed or unsigned domains are preferred. This is intended as a
+  /// cheap, non-recursive check.
+  ConstantRange computeConstantRange(const Value *V, bool ForSigned,
+                                     bool UseInstrInfo = true);
 
   /// Return true if this function can prove that the instruction I will
   /// always transfer execution to one of its successors (including the next
   /// instruction that follows within a basic block). E.g. this is not
   /// guaranteed for function calls that could loop infinitely.
   ///
   /// In other words, this function returns false for instructions that may
   /// transfer execution or fail to transfer execution in a way that is not

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *simplifyICmpWithConstant(CmpInst::Predicate Pred, Value *LHS,
 
   // Rule out tautological comparisons (eg., ult 0 or uge 0).
   ConstantRange RHS_CR = ConstantRange::makeExactICmpRegion(Pred, *C);
   if (RHS_CR.isEmptySet())
     return ConstantInt::getFalse(ITy);
   if (RHS_CR.isFullSet())
     return ConstantInt::getTrue(ITy);
 
-  ConstantRange LHS_CR = computeConstantRange(LHS, IIQ.UseInstrInfo);
+  ConstantRange LHS_CR = computeConstantRange(
+      LHS, CmpInst::isSigned(Pred), IIQ.UseInstrInfo);
   if (!LHS_CR.isFullSet()) {
     if (RHS_CR.contains(LHS_CR))
       return ConstantInt::getTrue(ITy);
     if (RHS_CR.inverse().contains(LHS_CR))
       return ConstantInt::getFalse(ITy);
   }
 
   return nullptr;

llvm/lib/Analysis/ValueTracking.cpp

 
 /// Combine constant ranges from computeConstantRange() and computeKnownBits().
 static ConstantRange computeConstantRangeIncludingKnownBits(
     const Value *V, bool ForSigned, const DataLayout &DL, unsigned Depth,
     AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT,
     OptimizationRemarkEmitter *ORE = nullptr, bool UseInstrInfo = true) {
   KnownBits Known = computeKnownBits(
       V, DL, Depth, AC, CxtI, DT, ORE, UseInstrInfo);
-  ConstantRange CR = computeConstantRange(V, UseInstrInfo);
+  ConstantRange CR = computeConstantRange(V, ForSigned, UseInstrInfo);
   return ConstantRange::fromKnownBits(Known, ForSigned).intersectWith(CR);
 }
 
 OverflowResult llvm::computeOverflowForUnsignedAdd(
     const Value *LHS, const Value *RHS, const DataLayout &DL,
     AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT,
     bool UseInstrInfo) {
   ConstantRange LHSRange = computeConstantRangeIncludingKnownBits(
assert((TrueBB == ContextBB || FalseBB == ContextBB) &&
          "Predecessor block does not point to successor?");
 
   // Is this condition implied by the predecessor condition?
   bool CondIsTrue = TrueBB == ContextBB;
   return isImpliedCondition(PredCond, Cond, DL, CondIsTrue);
 }
 
 static void setLimitsForBinOp(const BinaryOperator &BO, APInt &Lower,
-                              APInt &Upper, const InstrInfoQuery &IIQ) {
+                              APInt &Upper, bool ForSigned,
+                              const InstrInfoQuery &IIQ) {
   unsigned Width = Lower.getBitWidth();
   const APInt *C;
   switch (BO.getOpcode()) {
   case Instruction::Add:
     if (match(BO.getOperand(1), m_APInt(C)) && !C->isNullValue()) {
       // FIXME: If we have both nuw and nsw, we should reduce the range further.
       if (IIQ.hasNoUnsignedWrap(cast<OverflowingBinaryOperator>(&BO))) {
         // 'add nuw x, C' produces [C, UINT_MAX].
         Lower = *C;
       } else if (IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(&BO))) {
         if (C->isNegative()) {
           // 'add nsw x, -C' produces [SINT_MIN, SINT_MAX - C].
           Lower = APInt::getSignedMinValue(Width);
           Upper = APInt::getSignedMaxValue(Width) + *C + 1;
         } else {
           // 'add nsw x, +C' produces [SINT_MIN + C, SINT_MAX].
           Lower = APInt::getSignedMinValue(Width) + *C;
           Upper = APInt::getSignedMaxValue(Width) + 1;
         }
       }
     }
     break;
 
   case Instruction::And:
-    if (match(BO.getOperand(1), m_APInt(C)))
-      // 'and x, C' produces [0, C].
+    if (match(BO.getOperand(1), m_APInt(C))) {
+      // 'and x, C' produces [0, C] in the unsigned domain
+      // or [C, C & SINT_MAX] in the signed domain if C has a sign bit.
+      if (ForSigned && C->isSignBitSet()) {
+        Lower = *C;
+        Upper = *C;
+        Upper.clearSignBit();
+        ++Upper;
+      } else {
         Upper = *C + 1;
+      }
+    }
     break;
 
   case Instruction::Or:
-    if (match(BO.getOperand(1), m_APInt(C)))
-      // 'or x, C' produces [C, UINT_MAX].
+    if (match(BO.getOperand(1), m_APInt(C))) {
+      // 'or x, C' produces [C, UINT_MAX] in the unsigned domain
+      // or [C | SINT_MIN, SINT_MAX] in the signed domain if C has no sign bit.
       Lower = *C;
+      if (ForSigned && C->isSignBitClear()) {
+        Lower.setSignBit();
+        Upper = APInt::getSignedMaxValue(Width) + 1;
+      }
+    }
     break;
 
   case Instruction::AShr:
     if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) {
       // 'ashr x, C' produces [INT_MIN >> C, INT_MAX >> C].
       Lower = APInt::getSignedMinValue(Width).ashr(*C);
       Upper = APInt::getSignedMaxValue(Width).ashr(*C) + 1;
     } else if (match(BO.getOperand(0), m_APInt(C))) {
if (R.Flavor == SelectPatternFlavor::SPF_NABS) {
     Lower = APInt::getSignedMinValue(BitWidth);
     Upper = APInt(BitWidth, 1);
     return;
   }
 
   // TODO Handle min/max flavors.
 }
 
-ConstantRange llvm::computeConstantRange(const Value *V, bool UseInstrInfo) {
+ConstantRange llvm::computeConstantRange(const Value *V, bool ForSigned,
+                                         bool UseInstrInfo) {
   assert(V->getType()->isIntOrIntVectorTy() && "Expected integer instruction");
 
   const APInt *C;
   if (match(V, m_APInt(C)))
     return ConstantRange(*C);
 
   InstrInfoQuery IIQ(UseInstrInfo);
   unsigned BitWidth = V->getType()->getScalarSizeInBits();
   APInt Lower = APInt(BitWidth, 0);
   APInt Upper = APInt(BitWidth, 0);
   if (auto *BO = dyn_cast<BinaryOperator>(V))
-    setLimitsForBinOp(*BO, Lower, Upper, IIQ);
+    setLimitsForBinOp(*BO, Lower, Upper, ForSigned, IIQ);
   else if (auto *II = dyn_cast<IntrinsicInst>(V))
     setLimitsForIntrinsic(*II, Lower, Upper);
   else if (auto *SI = dyn_cast<SelectInst>(V))
     setLimitsForSelectPattern(*SI, Lower, Upper);
 
   ConstantRange CR = Lower != Upper ? ConstantRange(Lower, Upper)
                                     : ConstantRange(BitWidth, true);
 
   if (auto *I = dyn_cast<Instruction>(V))
     if (auto *Range = IIQ.getMetadata(I, LLVMContext::MD_range))
       CR = CR.intersectWith(getConstantRangeFromMetadata(*Range));
 
   return CR;
 }

llvm/test/Transforms/InstSimplify/icmp-constant.ll

;
   %A = or <2 x i32> %X, <i32 62, i32 62>
   %B = icmp ult <2 x i32> %A, <i32 50, i32 50>
   ret <2 x i1> %B
 }
 
 ; Single bit OR.
 define i1 @or2_true(i8 %x) {
 ; CHECK-LABEL: @or2_true(
-; CHECK-NEXT:    [[Y:%.*]] = or i8 [[X:%.*]], 64
-; CHECK-NEXT:    [[Z:%.*]] = icmp sge i8 [[Y]], -64
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 true
 ;
   %y = or i8 %x, 64
   %z = icmp sge i8 %y, -64
   ret i1 %z
 }
 
 define i1 @or2_unknown(i8 %x) {
 ; CHECK-LABEL: @or2_unknown(
 ; CHECK-NEXT:    [[Y:%.*]] = or i8 [[X:%.*]], 64
 ; CHECK-NEXT:    [[Z:%.*]] = icmp sgt i8 [[Y]], -64
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %y = or i8 %x, 64
   %z = icmp sgt i8 %y, -64
   ret i1 %z
 }
 
 ; Multi bit OR.
 ; 78 = 0b01001110; -50 = 0b11001110
 define i1 @or3_true(i8 %x) {
 ; CHECK-LABEL: @or3_true(
-; CHECK-NEXT:    [[Y:%.*]] = or i8 [[X:%.*]], 78
-; CHECK-NEXT:    [[Z:%.*]] = icmp sge i8 [[Y]], -50
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 true
 ;
   %y = or i8 %x, 78
   %z = icmp sge i8 %y, -50
   ret i1 %z
 }
 
 define i1 @or3_unknown(i8 %x) {
 ; CHECK-LABEL: @or3_unknown(

 ; CHECK-LABEL: @and2(
 ; CHECK-NEXT:    ret i1 false
 ;
   %A = and i32 %X, 62
   %B = icmp sgt i32 %A, 70
   ret i1 %B
 }
 
 ; -75 = 0b10110101, 53 = 0b00110101
 define i1 @and3_true1(i8 %x) {
 ; CHECK-LABEL: @and3_true1(
-; CHECK-NEXT:    [[Y:%.*]] = and i8 [[X:%.*]], -75
-; CHECK-NEXT:    [[Z:%.*]] = icmp sge i8 [[Y]], -75
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 true
 ;
   %y = and i8 %x, -75
   %z = icmp sge i8 %y, -75
   ret i1 %z
 }
 
 define i1 @and3_unknown1(i8 %x) {
 ; CHECK-LABEL: @and3_unknown1(
 ; CHECK-NEXT:    [[Y:%.*]] = and i8 [[X:%.*]], -75
 ; CHECK-NEXT:    [[Z:%.*]] = icmp sgt i8 [[Y]], -75
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %y = and i8 %x, -75
   %z = icmp sgt i8 %y, -75
   ret i1 %z
 }
 
 define i1 @and3_true2(i8 %x) {
 ; CHECK-LABEL: @and3_true2(
-; CHECK-NEXT:    [[Y:%.*]] = and i8 [[X:%.*]], -75
-; CHECK-NEXT:    [[Z:%.*]] = icmp sle i8 [[Y]], 53
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 true
 ;
   %y = and i8 %x, -75
   %z = icmp sle i8 %y, 53
   ret i1 %z
 }
 
 define i1 @and3_unknown2(i8 %x) {
 ; CHECK-LABEL: @and3_unknown2(