[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 ↗

(On Diff #52330)

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 ↗

(On Diff #52330)

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 ↗

(On Diff #53157)

would something isOverflowGuard() work better?

[sanjoy]

include/llvm/Analysis/ValueTracking.h

332 ↗

(On Diff #53157)

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.

llvm/trunk/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

llvm/trunk/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.
 
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->isInterposable() ? 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);

llvm/trunk/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);
 }

llvm/trunk/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