[ConstraintElimination] Make decompose() infallible

[nikic]

Summary

decompose() currently returns a mix of {} and 0 + 1*V on failure. I don't really follow why we use one over the other in some cases. It seems like it would be better to make decompose() infallible and always return 0 + 1*V is we can't decompose the value further.

[nikic]

Remove one more check.

[fhahn]

LGTM, thanks!

IIRC the main reason was that {} originally was more compact. With respect to correctness, always returning 0 + V is fine and in combination with the constructors from D137848 the code will end up still compact.

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

 
 static SmallVector<DecompEntry, 4>
 decomposeGEP(GetElementPtrInst &GEP,
              SmallVector<PreconditionTy, 4> &Preconditions, bool IsSigned,
              const DataLayout &DL) {
   // Do not reason about pointers where the index size is larger than 64 bits,
   // as the coefficients used to encode constraints are 64 bit integers.
   if (DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()) > 64)
-    return {};
+    return {{0, nullptr}, {1, &GEP}};
 
   if (!GEP.isInBounds())
     return {{0, nullptr}, {1, &GEP}};
 
   // Handle the (gep (gep ....), C) case by incrementing the constant
   // coefficient of the inner GEP, if C is a constant.
   auto *InnerGEP = dyn_cast<GetElementPtrInst>(GEP.getPointerOperand());
   if (InnerGEP && GEP.getNumOperands() == 2 &&
       isa<ConstantInt>(GEP.getOperand(1))) {
     APInt Offset = cast<ConstantInt>(GEP.getOperand(1))->getValue();
     auto Result = decompose(InnerGEP, Preconditions, IsSigned, DL);
 
     auto GTI = gep_type_begin(GEP);
     // Bail out for scalable vectors for now.
     if (isa<ScalableVectorType>(GTI.getIndexedType()))
-      return {};
+      return {{0, nullptr}, {1, &GEP}};
     int64_t Scale = static_cast<int64_t>(
         DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize());
 
     Result[0].Coefficient =
         addWithOverflow(Result[0].Coefficient,
                         multiplyWithOverflow(Scale, Offset.getSExtValue()));
     if (Offset.isNegative()) {
       // Add pre-condition ensuring the GEP is increasing monotonically and
SmallVector<DecompEntry, 4> Result = {{0, nullptr},
                                         {1, GEP.getPointerOperand()}};
   gep_type_iterator GTI = gep_type_begin(GEP);
   for (User::const_op_iterator I = GEP.op_begin() + 1, E = GEP.op_end(); I != E;
        ++I, ++GTI) {
     Value *Index = *I;
 
     // Bail out for scalable vectors for now.
     if (isa<ScalableVectorType>(GTI.getIndexedType()))
-      return {};
+      return {{0, nullptr}, {1, &GEP}};
 
     // Struct indices must be constants (and reference an existing field). Add
     // them to the constant factor.
     if (StructType *STy = GTI.getStructTypeOrNull()) {
       // For a struct, add the member offset.
       unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
       if (FieldNo == 0)
         continue;
 
       // Add offset to constant factor.
       Result[0].Coefficient = addWithOverflow(
           Result[0].Coefficient,
           int64_t(DL.getStructLayout(STy)->getElementOffset(FieldNo)));
       continue;
     }
 
     // For an array/pointer, add the element offset, explicitly scaled.
     unsigned Scale = DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize();
 
     auto IdxResult = decompose(Index, Preconditions, IsSigned, DL);
-    if (IdxResult.empty()) {
-      Result.emplace_back(Scale, Index);
-    } else {
-      for (auto &KV : IdxResult)
-        KV.Coefficient = multiplyWithOverflow(KV.Coefficient, Scale);
-      Result[0].Coefficient += IdxResult[0].Coefficient;
-      append_range(Result, ArrayRef<DecompEntry>(IdxResult).drop_front());
-    }
+
     // If Op0 is signed non-negative, the GEP is increasing monotonically and
     // can be de-composed.
     if (!isKnownNonNegative(Index, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))
       Preconditions.emplace_back(CmpInst::ICMP_SGE, Index,
                                  ConstantInt::get(Index->getType(), 0));
   }
   return Result;
 }
 
 // Decomposes \p V into a vector of entries of the form { Coefficient, Variable
 // } where Coefficient * Variable. The sum of the pairs equals \p V.  The first
 // pair is the constant-factor and X must be nullptr. If the expression cannot
 // be decomposed, returns an empty vector.
 static SmallVector<DecompEntry, 4>
 decompose(Value *V, SmallVector<PreconditionTy, 4> &Preconditions,
           bool IsSigned, const DataLayout &DL) {
 
   auto MergeResults = [&Preconditions, IsSigned,
                        &DL](Value *A, Value *B,
                             bool IsSignedB) -> SmallVector<DecompEntry, 4> {
     auto ResA = decompose(A, Preconditions, IsSigned, DL);
     auto ResB = decompose(B, Preconditions, IsSignedB, DL);
-    if (ResA.empty() || ResB.empty())
-      return {};
     ResA[0].Coefficient += ResB[0].Coefficient;
     append_range(ResA, drop_begin(ResB));
     return ResA;
   };
 
   // Decompose \p V used with a signed predicate.
   if (IsSigned) {
     if (auto *CI = dyn_cast<ConstantInt>(V)) {
       if (canUseSExt(CI))
         return {{CI->getSExtValue(), nullptr}};
     }
     Value *Op0;
     Value *Op1;
     if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1))))
       return MergeResults(Op0, Op1, IsSigned);
 
     return {{0, nullptr}, {1, V}};
   }
 
   if (auto *CI = dyn_cast<ConstantInt>(V)) {
     if (CI->uge(MaxConstraintValue))
-      return {};
+      return {{0, nullptr}, {1, V}};
     return {{int64_t(CI->getZExtValue()), nullptr}};
   }
 
   if (auto *GEP = dyn_cast<GetElementPtrInst>(V))
     return decomposeGEP(*GEP, Preconditions, IsSigned, DL);
 
   Value *Op0;
   bool IsKnownPositive = false;
ConstraintInfo::getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
 
   SmallVector<PreconditionTy, 4> Preconditions;
   bool IsSigned = CmpInst::isSigned(Pred);
   auto &Value2Index = getValue2Index(IsSigned);
   auto ADec = decompose(Op0->stripPointerCastsSameRepresentation(),
                         Preconditions, IsSigned, DL);
   auto BDec = decompose(Op1->stripPointerCastsSameRepresentation(),
                         Preconditions, IsSigned, DL);
-  // Skip if decomposing either of the values failed.
-  if (ADec.empty() || BDec.empty())
-    return {};
-
   int64_t Offset1 = ADec[0].Coefficient;
   int64_t Offset2 = BDec[0].Coefficient;
   Offset1 *= -1;
 
   // Create iterator ranges that skip the constant-factor.
   auto VariablesA = llvm::drop_begin(ADec);
   auto VariablesB = llvm::drop_begin(BDec);
 

llvm/test/Transforms/ConstraintElimination/large-constant-ints.ll

 ; CHECK-LABEL: @sub_decomp_i80(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nuw i80 [[A:%.*]], 1973801615886922022913
 ; CHECK-NEXT:    [[C:%.*]] = icmp ult i80 [[SUB]], 1346612317380797267967
 ; CHECK-NEXT:    br i1 [[C]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[SUB_1:%.*]] = sub nuw i80 [[A]], 1973801615886922022913
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ult i80 [[SUB_1]], 1346612317380797267967
-; CHECK-NEXT:    ret i1 [[C_1]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       else:
 ; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %sub = sub nuw i80 %a, 1973801615886922022913
   %c = icmp ult i80 %sub, 1346612317380797267967
   br i1 %c, label %then, label %else