[ValueTracking] computeOverflowForSignedAdd and isKnownNonNegative

[jingyue]

Summary

Refactor, NFC

Extracts computeOverflowForSignedAdd and isKnownNonNegative from NaryReassociate to ValueTracking in case
others need it.

[jingyue]

extract isKnownNonNegative

[reames]

include/llvm/Analysis/ValueTracking.h

297–302

I'm not thrilled with the inconsistent interface with the ones above, but given the extra power, it's worth it.

You might separate this into two versions:

1. which takes only LHS, RHS
2. which takes only the add and extracts LHS, RHS

1 is useful for analysing llvm.sadd.with.overflow in instcombine.
2 is useful in your original case

Having them share an implementation is reasonable.

lib/Analysis/ValueTracking.cpp

3349

The comment here is stale. What you appear to be actually checking is that the sign of the Add is the same as at least one of the operands. That appears sufficient, but the comment is misleading.

[jingyue]

two versions of computeOverflowForSignedAdd

[reames]

LGTM w/minor comments addressed. No further review needed.

include/llvm/Analysis/ValueTracking.h

302

/// doxygen comment please.

305

AC, CtxI, and DT need to be optional and defaulted to nullptr.

lib/Analysis/ValueTracking.cpp

3343

Use an early return to reduce nesting please.

3344

operands

lib/Transforms/Scalar/NaryReassociate.cpp

354

Doesn't need to be in this change, but this should be pushed inside the ValueTracking call and the wrapper function can probably completely disappear.

[majnemer]

lib/Analysis/ValueTracking.cpp

3327

This seems to overlap with InstCombiner::WillNotOverflowSignedAdd, would it make sense to consolidate this with that?

[reames]

lib/Analysis/ValueTracking.cpp

3327

Didn't know we had that one. Yes, a follow up patch to consolidate would make great sense.

[jingyue]

rebase to master

[jingyue]

All comments addressed. Thanks Philip and David!

lib/Analysis/ValueTracking.cpp

3327

ACK. Will address this in a follow-up diff.

lib/Transforms/Scalar/NaryReassociate.cpp

354

Done in this patch.

include/llvm/Analysis/ValueTracking.h

namespace llvm {
   /// when defined.  For vectors return true if every element is known to be
   /// non-zero when defined.  Supports values with integer or pointer type and
   /// vectors of integers.
   bool isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth = 0,
                       AssumptionCache *AC = nullptr,
                       const Instruction *CxtI = nullptr,
                       const DominatorTree *DT = nullptr);
 
+  /// Returns true if the give value is known to be non-negative.
+  bool isKnownNonNegative(Value *V, const DataLayout &DL, unsigned Depth = 0,
+                          AssumptionCache *AC = nullptr,
+                          const Instruction *CxtI = nullptr,
+                          const DominatorTree *DT = nullptr);
+
   /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
   /// this predicate to simplify operations downstream.  Mask is known to be
   /// zero for bits that V cannot have.
   ///
   /// This function is defined on values with integer type, values with pointer
   /// type, and vectors of integers.  In the case
   /// where V is a vector, the mask, known zero, and known one values are the
   /// same width as the vector element, and the bit is set only if it is true
OverflowResult computeOverflowForUnsignedMul(Value *LHS, Value *RHS,
                                                AssumptionCache *AC,
                                                const Instruction *CxtI,
                                                const DominatorTree *DT);
   OverflowResult computeOverflowForUnsignedAdd(Value *LHS, Value *RHS,
                                                const DataLayout &DL,
                                                AssumptionCache *AC,
                                                const Instruction *CxtI,
                                                const DominatorTree *DT);
-  
+  OverflowResult computeOverflowForSignedAdd(Value *Add, Value *LHS, Value *RHS,
+                                             const DataLayout &DL,
+                                             AssumptionCache *AC,
+                                             const Instruction *CxtI,
+                                             const DominatorTree *DT);
   /// \brief Specific patterns of select instructions we can match.
   enum SelectPatternFlavor {
     SPF_UNKNOWN = 0,
     SPF_SMIN,                   // Signed minimum
     SPF_UMIN,                   // Unsigned minimum
     SPF_SMAX,                   // Signed maximum
     SPF_UMAX,                   // Unsigned maximum
     SPF_ABS,                    // Absolute value
     SPF_NABS                    // Negated absolute value
   };
   /// Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind

lib/Analysis/ValueTracking.cpp

static bool isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth,
                            const Query &Q);
 
 bool llvm::isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth,
                           AssumptionCache *AC, const Instruction *CxtI,
                           const DominatorTree *DT) {
   return ::isKnownNonZero(V, DL, Depth, Query(AC, safeCxtI(V, CxtI), DT));
 }
 
+bool llvm::isKnownNonNegative(Value *V, const DataLayout &DL, unsigned Depth,
+                              AssumptionCache *AC, const Instruction *CxtI,
+                              const DominatorTree *DT) {
+  bool NonNegative, Negative;
+  ComputeSignBit(V, NonNegative, Negative, DL, Depth, AC, CxtI, DT);
+  return NonNegative;
+}
+
 static bool MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout &DL,
                               unsigned Depth, const Query &Q);
 
 bool llvm::MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout &DL,
                              unsigned Depth, AssumptionCache *AC,
                              const Instruction *CxtI, const DominatorTree *DT) {
   return ::MaskedValueIsZero(V, Mask, DL, Depth,
                              Query(AC, safeCxtI(V, CxtI), DT));
if (LHSKnownNonNegative && RHSKnownNonNegative) {
       // Create a simple add instruction, and insert it into the struct.
       return OverflowResult::NeverOverflows;
     }
   }
 
   return OverflowResult::MayOverflow;
 }
 
+OverflowResult llvm::computeOverflowForSignedAdd(
+    Value *Add, Value *LHS, Value *RHS, const DataLayout &DL,
+    AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT) {
+  bool LHSKnownNonNegative, LHSKnownNegative;
+  bool RHSKnownNonNegative, RHSKnownNegative;
+  ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, DL, /*Depth=*/0,
+                 AC, CxtI, DT);
+  ComputeSignBit(RHS, RHSKnownNonNegative, RHSKnownNegative, DL, /*Depth=*/0,
+                 AC, CxtI, DT);
+
+  if ((LHSKnownNonNegative && RHSKnownNegative) ||
+      (LHSKnownNegative && RHSKnownNonNegative)) {
+    // The sign bits are opposite: this CANNOT overflow.
+    return OverflowResult::NeverOverflows;
+  }
+
+  bool LHSOrRHSKnownNonNegative = (LHSKnownNonNegative || RHSKnownNonNegative);
+  bool LHSOrRHSKnownNegative = (LHSKnownNegative || RHSKnownNegative);
+  if (LHSOrRHSKnownNonNegative || LHSOrRHSKnownNegative) {
+    bool AddKnownNonNegative, AddKnownNegative;
+    ComputeSignBit(Add, AddKnownNonNegative, AddKnownNegative, DL, /*Depth=*/0,
+                   AC, CxtI, DT);
+    // If Add has the same sign as LHS/RHS, this add CANNOT overflow. This is
+    // particularly useful when the sum is @llvm.assume'ed non-negative rather
+    // than proved so from analyzing its operands.
+    if ((AddKnownNonNegative && LHSOrRHSKnownNonNegative) ||
+        (AddKnownNegative && LHSOrRHSKnownNegative)) {
+      return OverflowResult::NeverOverflows;
+    }
+  }
+
+  return OverflowResult::MayOverflow;
+}
+
 static SelectPatternFlavor matchSelectPattern(ICmpInst::Predicate Pred,
                                               Value *CmpLHS, Value *CmpRHS,
                                               Value *TrueVal, Value *FalseVal,
                                               Value *&LHS, Value *&RHS) {
   LHS = CmpLHS;
   RHS = CmpRHS;
 
   // (icmp X, Y) ? X : Y

lib/Transforms/Scalar/NaryReassociate.cpp

private:
   // \c CandidateExpr. Returns null if not found.
   Instruction *findClosestMatchingDominator(const SCEV *CandidateExpr,
                                             Instruction *Dominatee);
   // GetElementPtrInst implicitly sign-extends an index if the index is shorter
   // than the pointer size. This function returns whether Index is shorter than
   // GEP's pointer size, i.e., whether Index needs to be sign-extended in order
   // to be an index of GEP.
   bool requiresSignExtension(Value *Index, GetElementPtrInst *GEP);
-  // Returns whether V is known to be non-negative at context \c Ctxt.
-  bool isKnownNonNegative(Value *V, Instruction *Ctxt);
   // Returns whether AO may sign overflow at context \c Ctxt. It computes a
   // conservative result -- it answers true when not sure.
   bool maySignOverflow(AddOperator *AO, Instruction *Ctxt);
 
   AssumptionCache *AC;
   const DataLayout *DL;
   DominatorTree *DT;
   ScalarEvolution *SE;

 
 bool NaryReassociate::requiresSignExtension(Value *Index,
                                             GetElementPtrInst *GEP) {
   unsigned PointerSizeInBits =
       DL->getPointerSizeInBits(GEP->getType()->getPointerAddressSpace());
   return cast<IntegerType>(Index->getType())->getBitWidth() < PointerSizeInBits;
 }
 
-bool NaryReassociate::isKnownNonNegative(Value *V, Instruction *Ctxt) {
-  bool NonNegative, Negative;
-  // TODO: ComputeSignBits is expensive. Consider caching the results.
-  ComputeSignBit(V, NonNegative, Negative, *DL, 0, AC, Ctxt, DT);
-  return NonNegative;
-}
-
 bool NaryReassociate::maySignOverflow(AddOperator *AO, Instruction *Ctxt) {
   if (AO->hasNoSignedWrap())
     return false;
 
   Value *LHS = AO->getOperand(0), *RHS = AO->getOperand(1);
-  // If LHS or RHS has the same sign as the sum, AO doesn't sign overflow.
-  // TODO: handle the negative case as well.
-  if (isKnownNonNegative(AO, Ctxt) &&
-      (isKnownNonNegative(LHS, Ctxt) || isKnownNonNegative(RHS, Ctxt)))
-    return false;
-
-  return true;
+  return computeOverflowForSignedAdd(AO, LHS, RHS, *DL, AC, Ctxt, DT) !=
+         OverflowResult::NeverOverflows;
 }
 
 GetElementPtrInst *
 NaryReassociate::tryReassociateGEPAtIndex(GetElementPtrInst *GEP, unsigned I,
                                           Type *IndexedType) {
   Value *IndexToSplit = GEP->getOperand(I + 1);
   if (SExtInst *SExt = dyn_cast<SExtInst>(IndexToSplit)) {
     IndexToSplit = SExt->getOperand(0);
   } else if (ZExtInst *ZExt = dyn_cast<ZExtInst>(IndexToSplit)) {
     // zext can be treated as sext if the source is non-negative.
-    if (isKnownNonNegative(ZExt->getOperand(0), GEP))
+    if (isKnownNonNegative(ZExt->getOperand(0), *DL, 0, AC, GEP, DT))
       IndexToSplit = ZExt->getOperand(0);
   }
 
   if (AddOperator *AO = dyn_cast<AddOperator>(IndexToSplit)) {
     // If the I-th index needs sext and the underlying add is not equipped with
     // nsw, we cannot split the add because
     //   sext(LHS + RHS) != sext(LHS) + sext(RHS).
     if (requiresSignExtension(IndexToSplit, GEP) && maySignOverflow(AO, GEP))
GetElementPtrInst *NaryReassociate::tryReassociateGEPAtIndex(
     Type *IndexedType) {
   // Look for GEP's closest dominator that has the same SCEV as GEP except that
   // the I-th index is replaced with LHS.
   SmallVector<const SCEV *, 4> IndexExprs;
   for (auto Index = GEP->idx_begin(); Index != GEP->idx_end(); ++Index)
     IndexExprs.push_back(SE->getSCEV(*Index));
   // Replace the I-th index with LHS.
   IndexExprs[I] = SE->getSCEV(LHS);
-  if (isKnownNonNegative(LHS, GEP) &&
+  if (isKnownNonNegative(LHS, *DL, 0, AC, GEP, DT) &&
       DL->getTypeSizeInBits(LHS->getType()) <
           DL->getTypeSizeInBits(GEP->getOperand(I)->getType())) {
     // Zero-extend LHS if it is non-negative. InstCombine canonicalizes sext to
     // zext if the source operand is proved non-negative. We should do that
     // consistently so that CandidateExpr more likely appears before. See
     // @reassociate_gep_assume for an example of this canonicalization.
     IndexExprs[I] =
         SE->getZeroExtendExpr(IndexExprs[I], GEP->getOperand(I)->getType());