[SCEV] See through op.with.overflow intrinsics

[sanjoy]

Summary

This change teaches SCEV to see reduce `(extractvalue
0 (op.with.overflow X Y)) into op X Y` (with a no-wrap tag if
possible).

[regehr]

Sanjoy do you mind exposing IsResultNoOverflow() in such a way that it can be used by other passes? I was going to implement this myself (it's what I was asking about on twitter last night) but of course would rather just use yours.

[regehr]

lib/Analysis/ScalarEvolution.cpp

3841

I'm a little confused about this loop-- since we're looking for one branch, why do we want the loop here instead of just returning false if the CallInst has more than one user?

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

3841

We're also accumulating the result projections into AddVals (which in retrospect should be called something else, since they're not just additions -- I'll fix that).

[sanjoy]

Address review:

• Export isOverflowIntrinsicNoWrap to ValueTracking
• Generalize the logic a bit and add more tests to demonstrate

I couldn't find a better name than isOverflowIntrinsicNoWrap that
isn't also terribly verbose. Suggestions welcome!

[atrick]

This looks great. It seems like it will work well for createAddRecFromPHI.

I think we're still missing intrinsic support in getNoWrapFlagsFromUB.

[regehr]

Looks great.

include/llvm/Analysis/ValueTracking.h

332

would something isOverflowGuard() work better?

[sanjoy]

include/llvm/Analysis/ValueTracking.h

332

I'd say that would be misleading since we're not checking if the arithmetic operation can overflow, but that the "arithmetic result" projection of the intrinsic can be treated as no-wrap. So, as an example, the routine can (and will, in most cases) return true for an overflow intrinsic for which the "arithmetic result" projection is unused.

include/llvm/Analysis/ValueTracking.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_VALUETRACKING_H
 #define LLVM_ANALYSIS_VALUETRACKING_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Instruction.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Support/DataTypes.h"
 
 namespace llvm {
   class APInt;
   class AddOperator;
   class AssumptionCache;
   class DataLayout;
   class DominatorTree;
OverflowResult computeOverflowForSignedAdd(Value *LHS, Value *RHS,
                                              const DominatorTree *DT = nullptr);
   /// This version also leverages the sign bit of Add if known.
   OverflowResult computeOverflowForSignedAdd(AddOperator *Add,
                                              const DataLayout &DL,
                                              AssumptionCache *AC = nullptr,
                                              const Instruction *CxtI = nullptr,
                                              const DominatorTree *DT = nullptr);
 
+  /// 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(IntrinsicInst *II, DominatorTree &DT);
+
   /// 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
   /// captured in the CFG nor in the sequence of instructions within a basic

lib/Analysis/ScalarEvolution.cpp

explicit BinaryOp(unsigned Opcode, Value *LHS, Value *RHS, bool IsNSW = false,
                     bool IsNUW = false)
       : Opcode(Opcode), LHS(LHS), RHS(RHS), IsNSW(IsNSW), IsNUW(IsNUW),
         Op(nullptr) {}
 };
 }
 
 
 /// Try to map \p V into a BinaryOp, and return \c None on failure.
-static Optional<BinaryOp> MatchBinaryOp(Value *V) {
+static Optional<BinaryOp> MatchBinaryOp(Value *V, DominatorTree &DT) {
   auto *Op = dyn_cast<Operator>(V);
   if (!Op)
     return None;
 
   // Implementation detail: all the cleverness here should happen without
   // creating new SCEV expressions -- our caller knowns tricks to avoid creating
   // SCEV expressions when possible, and we should not break that.
 
   switch (Op->getOpcode()) {
   case Instruction::Add:
   case Instruction::Sub:
   case Instruction::Mul:
   case Instruction::UDiv:
   case Instruction::And:
   case Instruction::Or:
if (ConstantInt *SA = dyn_cast<ConstantInt>(Op->getOperand(1))) {
         Constant *X =
             ConstantInt::get(SA->getContext(),
                              APInt::getOneBitSet(BitWidth, SA->getZExtValue()));
         return BinaryOp(Instruction::UDiv, Op->getOperand(0), X);
       }
     }
     return BinaryOp(Op);
 
+  case Instruction::ExtractValue: {
+    auto *EVI = cast<ExtractValueInst>(Op);
+    if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
+      break;
+
+    auto *CI = dyn_cast<CallInst>(EVI->getAggregateOperand());
+    if (!CI)
+      break;
+
+    if (auto *F = CI->getCalledFunction())
+      switch (F->getIntrinsicID()) {
+      case Intrinsic::sadd_with_overflow:
+      case Intrinsic::uadd_with_overflow: {
+        if (!isOverflowIntrinsicNoWrap(cast<IntrinsicInst>(CI), DT))
+          return BinaryOp(Instruction::Add, CI->getArgOperand(0),
+                          CI->getArgOperand(1));
+
+        // Now that we know that all uses of the arithmetic-result component of
+        // CI are guarded by the overflow check, we can go ahead and pretend
+        // that the arithmetic is non-overflowing.
+        if (F->getIntrinsicID() == Intrinsic::sadd_with_overflow)
+          return BinaryOp(Instruction::Add, CI->getArgOperand(0),
+                          CI->getArgOperand(1), /* IsNSW = */ true,
+                          /* IsNUW = */ false);
+        else
+          return BinaryOp(Instruction::Add, CI->getArgOperand(0),
+                          CI->getArgOperand(1), /* IsNSW = */ false,
+                          /* IsNUW*/ true);
+      }
+
+      case Intrinsic::ssub_with_overflow:
+      case Intrinsic::usub_with_overflow:
+        return BinaryOp(Instruction::Sub, CI->getArgOperand(0),
+                        CI->getArgOperand(1));
+
+      case Intrinsic::smul_with_overflow:
+      case Intrinsic::umul_with_overflow:
+        return BinaryOp(Instruction::Mul, CI->getArgOperand(0),
+                        CI->getArgOperand(1));
+      default:
+        break;
+      }
+  }
+
   default:
     break;
   }
 
   return None;
 }
 
 const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) {
if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
         // loop iteration, but is not itself an addrec in this loop.
         if (isLoopInvariant(Accum, L) ||
             (isa<SCEVAddRecExpr>(Accum) &&
              cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
 
           // If the increment doesn't overflow, then neither the addrec nor
           // the post-increment will overflow.
-          if (auto BO = MatchBinaryOp(BEValueV)) {
+          if (auto BO = MatchBinaryOp(BEValueV, DT)) {
             if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
               if (BO->IsNUW)
                 Flags = setFlags(Flags, SCEV::FlagNUW);
               if (BO->IsNSW)
                 Flags = setFlags(Flags, SCEV::FlagNSW);
             }
           } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(BEValueV)) {
             // If the increment is an inbounds GEP, then we know the address
const SCEV *ScalarEvolution::createSCEV(Value *V) {
   else if (isa<ConstantPointerNull>(V))
     return getZero(V->getType());
   else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
     return GA->mayBeOverridden() ? getUnknown(V) : getSCEV(GA->getAliasee());
   else if (!isa<ConstantExpr>(V))
     return getUnknown(V);
 
   Operator *U = cast<Operator>(V);
-  if (auto BO = MatchBinaryOp(U)) {
+  if (auto BO = MatchBinaryOp(U, DT)) {
     switch (BO->Opcode) {
     case Instruction::Add: {
       // The simple thing to do would be to just call getSCEV on both operands
       // and call getAddExpr with the result. However if we're looking at a
       // bunch of things all added together, this can be quite inefficient,
       // because it leads to N-1 getAddExpr calls for N ultimate operands.
       // Instead, gather up all the operands and make a single getAddExpr call.
       // LLVM IR canonical form means we need only traverse the left operands.
case Instruction::Add: {
           }
         }
 
         if (BO->Opcode == Instruction::Sub)
           AddOps.push_back(getNegativeSCEV(getSCEV(BO->RHS)));
         else
           AddOps.push_back(getSCEV(BO->RHS));
 
-        auto NewBO = MatchBinaryOp(BO->LHS);
+        auto NewBO = MatchBinaryOp(BO->LHS, DT);
         if (!NewBO || (NewBO->Opcode != Instruction::Add &&
                        NewBO->Opcode != Instruction::Sub)) {
           AddOps.push_back(getSCEV(BO->LHS));
           break;
         }
         BO = NewBO;
       } while (true);
 
case Instruction::Mul: {
           if (Flags != SCEV::FlagAnyWrap) {
             MulOps.push_back(
                 getMulExpr(getSCEV(BO->LHS), getSCEV(BO->RHS), Flags));
             break;
           }
         }
 
         MulOps.push_back(getSCEV(BO->RHS));
-        auto NewBO = MatchBinaryOp(BO->LHS);
+        auto NewBO = MatchBinaryOp(BO->LHS, DT);
         if (!NewBO || NewBO->Opcode != Instruction::Mul) {
           MulOps.push_back(getSCEV(BO->LHS));
           break;
         }
   BO = NewBO;
       } while (true);
 
       return getMulExpr(MulOps);

lib/Analysis/ValueTracking.cpp

if ((AddKnownNonNegative && LHSOrRHSKnownNonNegative) ||
         (AddKnownNegative && LHSOrRHSKnownNegative)) {
       return OverflowResult::NeverOverflows;
     }
   }
 
   return OverflowResult::MayOverflow;
 }
 
+bool llvm::isOverflowIntrinsicNoWrap(IntrinsicInst *II, DominatorTree &DT) {
+#ifndef NDEBUG
+  auto IID = II->getIntrinsicID();
+  assert((IID == Intrinsic::sadd_with_overflow ||
+          IID == Intrinsic::uadd_with_overflow ||
+          IID == Intrinsic::ssub_with_overflow ||
+          IID == Intrinsic::usub_with_overflow ||
+          IID == Intrinsic::smul_with_overflow ||
+          IID == Intrinsic::umul_with_overflow) &&
+         "Not an overflow intrinsic!");
+#endif
+
+  SmallVector<BranchInst *, 2> GuardingBranches;
+  SmallVector<ExtractValueInst *, 2> Results;
+
+  for (User *U : II->users()) {
+    if (auto *EVI = dyn_cast<ExtractValueInst>(U)) {
+      assert(EVI->getNumIndices() == 1 && "Obvious from CI's type");
+
+      if (EVI->getIndices()[0] == 0)
+        Results.push_back(EVI);
+      else {
+        assert(EVI->getIndices()[0] == 1 && "Obvious from CI's type");
+
+        for (auto *U : EVI->users())
+          if (auto *B = dyn_cast<BranchInst>(U)) {
+            assert(B->isConditional() && "How else is it using an i1?");
+            GuardingBranches.push_back(B);
+          }
+      }
+    } else {
+      // We are using the aggregate directly in a way we don't want to analyze
+      // here (storing it to a global, say).
+      return false;
+    }
+  }
+
+  auto AllUsesGuardedByBranch = [&](BranchInst *BI) {
+    BasicBlockEdge NoWrapEdge(BI->getParent(), BI->getSuccessor(1));
+    if (!NoWrapEdge.isSingleEdge())
+      return false;
+
+    // Check if all users of the add are provably no-wrap.
+    for (auto *Result : Results) {
+      // If the extractvalue itself is not executed on overflow, the we don't
+      // need to check each use separately, since domination is transitive.
+      if (DT.dominates(NoWrapEdge, Result->getParent()))
+        continue;
+
+      for (auto &RU : Result->uses())
+        if (!DT.dominates(NoWrapEdge, RU))
+          return false;
+    }
+
+    return true;
+  };
+
+  return any_of(GuardingBranches, AllUsesGuardedByBranch);
+}
+
+
 OverflowResult llvm::computeOverflowForSignedAdd(AddOperator *Add,
                                                  const DataLayout &DL,
                                                  AssumptionCache *AC,
                                                  const Instruction *CxtI,
                                                  const DominatorTree *DT) {
   return ::computeOverflowForSignedAdd(Add->getOperand(0), Add->getOperand(1),
                                        Add, DL, AC, CxtI, DT);
 }

test/Analysis/ScalarEvolution/overflow-intrinsics.ll

+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @f_sadd_0(i8* %a) {
+; CHECK-LABEL: Classifying expressions for: @f_sadd_0
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %cont
+  ret void
+
+for.body:                                         ; preds = %entry, %cont
+; CHECK:  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
+; CHECK-NEXT:  -->  {0,+,1}<nuw><nsw><%for.body> U: [0,16) S: [0,16)
+
+  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
+  %idxprom = sext i32 %i.04 to i64
+  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
+  store i8 0, i8* %arrayidx, align 1
+  %tmp0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %i.04, i32 1)
+  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
+  br i1 %tmp1, label %trap, label %cont, !nosanitize !{}
+
+trap:                                             ; preds = %for.body
+  tail call void @llvm.trap() #2, !nosanitize !{}
+  unreachable, !nosanitize !{}
+
+cont:                                             ; preds = %for.body
+  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
+  %cmp = icmp slt i32 %tmp2, 16
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+; CHECK: Loop %for.body: max backedge-taken count is 15
+}
+
+define void @f_sadd_1(i8* %a) {
+; CHECK-LABEL: Classifying expressions for: @f_sadd_1
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %cont
+  ret void
+
+for.body:                                         ; preds = %entry, %cont
+; CHECK:  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
+; CHECK-NEXT:  -->  {0,+,1}<%for.body> U: [0,16) S: [0,16)
+
+; SCEV can prove <nsw> for the above induction variable; but it does
+; not bother so before it sees the sext below since it is not a 100%
+; obvious.
+
+  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
+  %idxprom = sext i32 %i.04 to i64
+  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
+  store i8 0, i8* %arrayidx, align 1
+  %tmp0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %i.04, i32 1)
+  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
+  br i1 %tmp1, label %trap, label %cont, !nosanitize !{}
+
+trap:                                             ; preds = %for.body
+
+  br label %cont
+
+cont:                                             ; preds = %for.body
+  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
+  %cmp = icmp slt i32 %tmp2, 16
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+; CHECK: Loop %for.body: max backedge-taken count is 15
+}
+
+define void @f_sadd_2(i8* %a, i1* %c) {
+; CHECK-LABEL: Classifying expressions for: @f_sadd_2
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %cont
+  ret void
+
+for.body:                                         ; preds = %entry, %cont
+; CHECK:  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
+; CHECK-NEXT:  -->  {0,+,1}<%for.body>
+
+  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
+  %idxprom = sext i32 %i.04 to i64
+  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
+  store i8 0, i8* %arrayidx, align 1
+  %tmp0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %i.04, i32 1)
+  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
+  br i1 %tmp1, label %trap, label %cont, !nosanitize !{}
+
+trap:                                             ; preds = %for.body
+
+  br label %cont
+
+cont:                                             ; preds = %for.body
+  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
+  %cond = load volatile i1, i1* %c
+  br i1 %cond, label %for.body, label %for.cond.cleanup
+}
+
+define void @f_sadd_3(i8* %a, i1* %c) {
+; CHECK-LABEL: Classifying expressions for: @f_sadd_3
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %cont
+  ret void
+
+for.body:                                         ; preds = %entry, %cont
+; CHECK:  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %for.body ]
+; CHECK-NEXT:  -->  {0,+,1}<nuw><nsw><%for.body>
+
+  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %for.body ]
+  %idxprom = sext i32 %i.04 to i64
+  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
+  store i8 0, i8* %arrayidx, align 1
+  %tmp0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %i.04, i32 1)
+  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
+  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
+  br i1 %tmp1, label %trap, label %for.body, !nosanitize !{}
+
+trap:                                             ; preds = %for.body
+  tail call void @llvm.trap() #2, !nosanitize !{}
+  unreachable, !nosanitize !{}
+}
+
+define void @f_sadd_4(i8* %a, i1* %c) {
+; CHECK-LABEL: Classifying expressions for: @f_sadd_4
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %cont
+  ret void
+
+for.body:                                         ; preds = %entry, %cont
+; CHECK:  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %merge ]
+; CHECK-NEXT:  -->  {0,+,1}<nuw><nsw><%for.body>
+
+  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %merge ]
+  %idxprom = sext i32 %i.04 to i64
+  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
+  store i8 0, i8* %arrayidx, align 1
+  %tmp0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %i.04, i32 1)
+  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
+  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
+  br i1 %tmp1, label %notrap, label %merge
+
+notrap:
+  br label %merge
+
+merge:
+  %tmp3 = extractvalue { i32, i1 } %tmp0, 1
+  br i1 %tmp3, label %trap, label %for.body, !nosanitize !{}
+
+trap:                                             ; preds = %for.body
+  tail call void @llvm.trap() #2, !nosanitize !{}
+  unreachable, !nosanitize !{}
+}
+
+define void @f_sadd_may_overflow(i8* %a, i1* %c) {
+; CHECK-LABEL: Classifying expressions for: @f_sadd_may_overflow
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %cont
+  ret void
+
+for.body:                                         ; preds = %entry, %cont
+; CHECK:  %i.04 = phi i32 [ 0, %entry ], [ %tmp1, %cont ]
+; CHECK-NEXT:  -->  {0,+,1}<%for.body> U: full-set S: full-set
+
+  %i.04 = phi i32 [ 0, %entry ], [ %tmp1, %cont ]
+  %idxprom = sext i32 %i.04 to i64
+  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
+  store i8 0, i8* %arrayidx, align 1
+  %tmp0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %i.04, i32 1)
+  %cond1 = load volatile i1, i1* %c
+  br i1 %cond1, label %trap, label %cont, !nosanitize !{}
+
+trap:                                             ; preds = %for.body
+  tail call void @llvm.trap() #2, !nosanitize !{}
+  unreachable, !nosanitize !{}
+
+cont:                                             ; preds = %for.body
+  %tmp1 = extractvalue { i32, i1 } %tmp0, 0
+  %cond = load volatile i1, i1* %c
+  br i1 %cond, label %for.body, label %for.cond.cleanup
+}
+
+define void @f_uadd(i8* %a) {
+; CHECK-LABEL: Classifying expressions for: @f_uadd
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %cont
+  ret void
+
+for.body:                                         ; preds = %entry, %cont
+; CHECK:  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
+; CHECK-NEXT:  -->  {0,+,1}<nuw><%for.body> U: [0,16) S: [0,16)
+
+  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
+  %idxprom = sext i32 %i.04 to i64
+  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
+  store i8 0, i8* %arrayidx, align 1
+  %tmp0 = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %i.04, i32 1)
+  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
+  br i1 %tmp1, label %trap, label %cont, !nosanitize !{}
+
+trap:                                             ; preds = %for.body
+  tail call void @llvm.trap(), !nosanitize !{}
+  unreachable, !nosanitize !{}
+
+cont:                                             ; preds = %for.body
+  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
+  %cmp = icmp slt i32 %tmp2, 16
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+; CHECK: Loop %for.body: max backedge-taken count is 15
+}
+
+define void @f_ssub(i8* nocapture %a) {
+; CHECK-LABEL: Classifying expressions for: @f_ssub
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %cont
+  ret void
+
+for.body:                                         ; preds = %entry, %cont
+; CHECK:  %i.04 = phi i32 [ 15, %entry ], [ %tmp2, %cont ]
+; CHECK-NEXT:  -->  {15,+,-1}<%for.body> U: [0,16) S: [0,16)
+
+  %i.04 = phi i32 [ 15, %entry ], [ %tmp2, %cont ]
+  %idxprom = sext i32 %i.04 to i64
+  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
+  store i8 0, i8* %arrayidx, align 1
+  %tmp0 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %i.04, i32 1)
+  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
+  br i1 %tmp1, label %trap, label %cont, !nosanitize !{}
+
+trap:                                             ; preds = %for.body
+  tail call void @llvm.trap(), !nosanitize !{}
+  unreachable, !nosanitize !{}
+
+cont:                                             ; preds = %for.body
+  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
+  %cmp = icmp sgt i32 %tmp2, -1
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+; CHECK: Loop %for.body: max backedge-taken count is 15
+}
+
+define void @f_usub(i8* nocapture %a) {
+; CHECK-LABEL: Classifying expressions for: @f_usub
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %cont
+  ret void
+
+for.body:                                         ; preds = %entry, %cont
+; CHECK:  %i.04 = phi i32 [ 15, %entry ], [ %tmp2, %cont ]
+; CHECK-NEXT:  -->  {15,+,-1}<%for.body> U: [0,16) S: [0,16)
+
+  %i.04 = phi i32 [ 15, %entry ], [ %tmp2, %cont ]
+  %idxprom = sext i32 %i.04 to i64
+  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
+  store i8 0, i8* %arrayidx, align 1
+  %tmp0 = tail call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %i.04, i32 1)
+  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
+  br i1 %tmp1, label %trap, label %cont, !nosanitize !{}
+
+trap:                                             ; preds = %for.body
+  tail call void @llvm.trap(), !nosanitize !{}
+  unreachable, !nosanitize !{}
+
+cont:                                             ; preds = %for.body
+  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
+  %cmp = icmp sgt i32 %tmp2, -1
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+; CHECK: Loop %for.body: max backedge-taken count is 15
+}
+
+define i32 @f_smul(i32 %val_a, i32 %val_b) {
+; CHECK-LABEL: Classifying expressions for: @f_smul
+  %agg = tail call { i32, i1 } @llvm.smul.with.overflow.i32(i32 %val_a, i32 %val_b)
+; CHECK:   %mul = extractvalue { i32, i1 } %agg, 0
+; CHECK-NEXT:  -->  (%val_a * %val_b) U: full-set S: full-set
+  %mul = extractvalue { i32, i1 } %agg, 0
+  ret i32 %mul
+}
+
+define i32 @f_umul(i32 %val_a, i32 %val_b) {
+; CHECK-LABEL: Classifying expressions for: @f_umul
+  %agg = tail call { i32, i1 } @llvm.umul.with.overflow.i32(i32 %val_a, i32 %val_b)
+; CHECK:   %mul = extractvalue { i32, i1 } %agg, 0
+; CHECK-NEXT:  -->  (%val_a * %val_b) U: full-set S: full-set
+  %mul = extractvalue { i32, i1 } %agg, 0
+  ret i32 %mul
+}
+
+declare { i32, i1 } @llvm.sadd.with.overflow.i32(i32, i32) nounwind readnone
+declare { i32, i1 } @llvm.uadd.with.overflow.i32(i32, i32) nounwind readnone
+declare { i32, i1 } @llvm.ssub.with.overflow.i32(i32, i32) nounwind readnone
+declare { i32, i1 } @llvm.usub.with.overflow.i32(i32, i32) nounwind readnone
+declare { i32, i1 } @llvm.smul.with.overflow.i32(i32, i32) nounwind readnone
+declare { i32, i1 } @llvm.umul.with.overflow.i32(i32, i32) nounwind readnone
+
+declare void @llvm.trap() #2