[LVI] Teach LVI to see through x.with.overflow calls

[regehr]

Summary

If we're going to use LVI as a remover for overflow checks, then it should be able to see through calls to x.with.overflow intrinsics. This patch does that.

I'm not too happy with the code copied from solveBlockValueBinaryOp() and would be happy for suggestions for how to factor this better.

[reames]

lib/Analysis/LazyValueInfo.cpp

654

minor: place this below the PHI and select handling please. Those two are mildly special in the current structure. Also, this should be below the pointer bail.

824

Prefer early exit please.

826

I think this should be:
if (EV->getNumIndices() != 1 && *EV->idx_begin() != 0)

832

Hm, semantics question. Is the first value of sadd.with.overflow result well defined if the second is true? (i.e. overflow did occur?)

I had thought the answer to this was "no". I suspect you're trying to use the result of this to prove the no-overflow on the intrinsic via CVP and I'm not sure that's safe.

874

You can separate out this bit into a helper of the form:
CR transfer(OpCode, CR, CR)

and share it with the current binaryoperator handling.

[regehr]

lib/Analysis/LazyValueInfo.cpp

832

My read of the langref is that the first and second values are independently valid, but I'll double-check on the mailing list.

[regehr]

lib/Analysis/LazyValueInfo.cpp

874

Just to be clear-- do the intrinsicIDs and regular opcodes live in different parts of the namespace? Can I safely mix them in a switch? I had been wondering about this but didn't find the thing I wanted to know in the documentation.

[regehr]

Address Philip's feedback and rebase. Thanks for the comments!

[regehr]

I have a small, well-defined program that gets compiled into a crash by clang -O2 -fsanitize=signed-integer-overflow -fsanitize-trap=signed-integer-overflow. So either there's a bug in this patch or else teaching LLVM to see through overflow intrinsics is exposing a bug elsewhere. I'll narrow it down.

This is the program.

int a;
int fn1(p1) { return 1 - p1 + 1; }
int main() {
  int b = 0;
  if (fn1(0))
    a = b = 1;
  fn1(b);
  return 0;
}

[regehr]

Oops-- instead of

(EV->getNumIndices() != 1 && *EV->idx_begin() != 0)

we wanted

(EV->getNumIndices() != 1 || *EV->idx_begin() != 0)

luckily Csmith caught this since I didn't.

[regehr]

rebase and bump

[reames]

Sorry for letting this lie for so long. If you separate out the two helper functions and rebase, I think this is very close to going in. You can land the refactorings suggested without further review for them.

lib/Analysis/LazyValueInfo.cpp

681

Please update with full context.

819

Separating out this transfer function is a useful cleanup for the code as is. Please separate, commit, then rebase. (LGTM for that only)

864

Shifting this below the next check would make the code easier to read (at least for me) as it groups related checks.

874

I believe there are different namespaces.

891

extracting out a helper function getRangeForOperand(...) would greatly simplify this code.

894

The patch needs rebased.

[lebedev.ri]

@regehr reverse-ping? :)

[nikic]

@lebedev.ri I believe I implemented something equivalent in the meantime, see https://github.com/llvm/llvm-project/blob/688183ec54482666e4faa6b6e1a83fe3ccc9372d/llvm/lib/Analysis/LazyValueInfo.cpp#L1099-L1105.

[lebedev.ri]

In D19867#1652174, @nikic wrote:

@lebedev.ri I believe I implemented something equivalent in the meantime, see https://github.com/llvm/llvm-project/blob/688183ec54482666e4faa6b6e1a83fe3ccc9372d/llvm/lib/Analysis/LazyValueInfo.cpp#L1099-L1105.

I briefly thought so too, but the tests here still don't get folded: https://godbolt.org/z/AvKbzY
So this is still applicable in some capacity.

[nikic]

@lebedev.ri Thanks! The problem here is that for these test cases CVP will convert the with.overflow intrinsic to a simple add/sub/mul together with insertvalue instructions. LVI can't see through extractvalue of insertvalue, which is why the followup optimization on the condition does not trigger (it would only happen on the next run). I'll look into fixing this.

[lebedev.ri]

@regehr abandon please

lib/Analysis/LazyValueInfo.cpp

class LazyValueInfoCache {
     bool hasBlockValue(Value *Val, BasicBlock *BB);
 
     // These methods process one work item and may add more. A false value
     // returned means that the work item was not completely processed and must
     // be revisited after going through the new items.
     bool solveBlockValue(Value *Val, BasicBlock *BB);
     bool solveBlockValueNonLocal(LVILatticeVal &BBLV,
                                  Value *Val, BasicBlock *BB);
+    bool solveBlockValueExtractValue(LVILatticeVal &BBLV,
+                                     ExtractValueInst *EV, BasicBlock *BB);
     bool solveBlockValuePHINode(LVILatticeVal &BBLV,
                                 PHINode *PN, BasicBlock *BB);
     bool solveBlockValueSelect(LVILatticeVal &BBLV,
                                SelectInst *S, BasicBlock *BB); 
     bool solveBlockValueBinaryOp(LVILatticeVal &BBLV,
                               Instruction *BBI, BasicBlock *BB);
     bool solveBlockValueCast(LVILatticeVal &BBLV,
                              Instruction *BBI, BasicBlock *BB);
bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
   Instruction *BBI = dyn_cast<Instruction>(Val);
   if (!BBI || BBI->getParent() != BB) {
     if (!solveBlockValueNonLocal(Res, Val, BB))
       return false;
    insertResult(Val, BB, Res);
    return true;
   }
 
+  if (auto *EV = dyn_cast<ExtractValueInst>(BBI)) {
+    if (!solveBlockValueExtractValue(Res, EV, BB))
+      return false;
+    insertResult(Val, BB, Res);
+    return true;
+  }
+
   if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
     if (!solveBlockValuePHINode(Res, PN, BB))
       return false;
     insertResult(Val, BB, Res);
     return true;
   }
 
   if (auto *SI = dyn_cast<SelectInst>(BBI)) {
     if (!solveBlockValueSelect(Res, SI, BB))
       return false;
     insertResult(Val, BB, Res);
     return true;
   }
 
   // If this value is a nonnull pointer, record it's range and bailout.  Note
   // that for all other pointer typed values, we terminate the search at the
   // definition.  We could easily extend this to look through geps, bitcasts,
   // and the like to prove non-nullness, but it's not clear that's worth it
   // compile time wise.  The context-insensative value walk done inside
   // isKnownNonNull gets most of the profitable cases at much less expense.
   // This does mean that we have a sensativity to where the defining
   // instruction is placed, even if it could legally be hoisted much higher.
   // That is unfortunate.
   PointerType *PT = dyn_cast<PointerType>(BBI->getType());
   if (PT && isKnownNonNull(BBI)) {
     Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT));
     insertResult(Val, BB, Res);
     return true;
   }
bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV,
   if (EdgesMissing)
     return false;
 
   // Return the merged value, which is more precise than 'overdefined'.
   assert(!Result.isOverdefined());
   BBLV = Result;
   return true;
 }
 
+bool LazyValueInfoCache::solveBlockValueExtractValue(LVILatticeVal &BBLV,
+                                                     ExtractValueInst *EV, BasicBlock *BB) {
+  LVILatticeVal Result;  // Start Undefined.
+
+  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(EV->getOperand(0))) {
+
+    // Bail early unless we're getting the zero-indexed output.
+    if (EV->getIndices()[0] != 0) {
+      BBLV = Result;
+      return true;
+    }
+
+    // And it's an overflow intrinsic.
+    switch (II->getIntrinsicID()) {
+    case Intrinsic::sadd_with_overflow:
+    case Intrinsic::uadd_with_overflow:
+    case Intrinsic::ssub_with_overflow:
+    case Intrinsic::usub_with_overflow:
+    case Intrinsic::smul_with_overflow:
+    case Intrinsic::umul_with_overflow:
+      break;
+    default:
+      BBLV = Result;
+      return true;
+    }
+
+    if (!hasBlockValue(II->getOperand(0), BB))
+      if (pushBlockValue(std::make_pair(BB, II->getOperand(0))))
+        // More work to do before applying this transfer rule.
+        return false;
+    const unsigned LHSBitWidth =
+      DL.getTypeSizeInBits(II->getOperand(0)->getType());
+    ConstantRange LHSRange = ConstantRange(LHSBitWidth);
+    if (hasBlockValue(II->getOperand(0), BB)) {
+      LVILatticeVal LHSVal = getBlockValue(II->getOperand(0), BB);
+      intersectAssumeBlockValueConstantRange(II->getOperand(0), LHSVal, II);
+      if (LHSVal.isConstantRange())
+        LHSRange = LHSVal.getConstantRange();
+    }
+
+    if (!hasBlockValue(II->getOperand(1), BB))
+      if (pushBlockValue(std::make_pair(BB, II->getOperand(1))))
+        // More work to do before applying this transfer rule.
+        return false;
+    const unsigned RHSBitWidth =
+      DL.getTypeSizeInBits(II->getOperand(1)->getType());
+    ConstantRange RHSRange = ConstantRange(RHSBitWidth);
+    if (hasBlockValue(II->getOperand(1), BB)) {
+      LVILatticeVal RHSVal = getBlockValue(II->getOperand(1), BB);
+      intersectAssumeBlockValueConstantRange(II->getOperand(1), RHSVal, II);
+      if (RHSVal.isConstantRange())
+        RHSRange = RHSVal.getConstantRange();
+    }
+
+    switch (II->getIntrinsicID()) {
+    case Intrinsic::sadd_with_overflow:
+    case Intrinsic::uadd_with_overflow:
+      Result.markConstantRange(LHSRange.add(RHSRange));
+      break;
+    case Intrinsic::ssub_with_overflow:
+    case Intrinsic::usub_with_overflow:
+      Result.markConstantRange(LHSRange.sub(RHSRange));
+      break;
+    case Intrinsic::smul_with_overflow:
+    case Intrinsic::umul_with_overflow:
+      Result.markConstantRange(LHSRange.multiply(RHSRange));
+      break;
+    default:
+      // Should be dead if the code above is correct
+      llvm_unreachable("inconsistent with above");
+      break;
+    }
+  }
+  BBLV = Result;
+  return true;
+}
+
 bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
                                                 PHINode *PN, BasicBlock *BB) {
   LVILatticeVal Result;  // Start Undefined.
 
   // Loop over all of our predecessors, merging what we know from them into
   // result.
   bool EdgesMissing = false;
   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {

test/Transforms/CorrelatedValuePropagation/overflow.ll

+; RUN: opt -correlated-propagation -S %s | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.10.0"
+
+; Make sure CVP (via LVI) can propagate values through sadd.with.overflow.
+; CHECK-LABEL: @sadd1
+define i1 @sadd1(i32 %x, i32 %y) #0 {
+entry:
+  %x.offset = add i32 %x, 9
+  %cmp1 = icmp ult i32 %x.offset, 19
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %y.offset = add i32 %y, 9
+  %cmp2 = icmp ult i32 %y.offset, 19
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  ; x = [-9,10), y = [-9,10)
+  %res = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %x, i32 %y)
+  %add = extractvalue { i32, i1 } %res, 0
+  br label %cont3
+
+cont3:
+  ; add = [-18,19)
+  %cmp3 = icmp slt i32 %add, 19
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK: ret i1 true
+  ret i1 %ret
+}
+
+; Negative version of previous test.
+; CHECK-LABEL: @sadd2
+define i1 @sadd2(i32 %x, i32 %y) #0 {
+entry:
+  %x.offset = add i32 %x, 9
+  %cmp1 = icmp ult i32 %x.offset, 19
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %y.offset = add i32 %y, 9
+  %cmp2 = icmp ult i32 %y.offset, 19
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  ; x = [-9,10), y = [-9,10)
+  %res = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %x, i32 %y)
+  %add = extractvalue { i32, i1 } %res, 0
+  br label %cont3
+
+cont3:
+  ; add = [-18,19)
+  %cmp3 = icmp slt i32 %add, 18
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK-NOT: ret i1 true
+  ret i1 %ret
+}
+
+; Make sure CVP (via LVI) can propagate values through uadd.with.overflow.
+; CHECK-LABEL: @uadd1
+define i1 @uadd1(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 10
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 10
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  %res = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %x, i32 %y)
+  %add = extractvalue { i32, i1 } %res, 0
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ult i32 %add, 19
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK: ret i1 true
+  ret i1 %ret
+}
+
+; Negative version of previous test.
+; CHECK-LABEL: @uadd2
+define i1 @uadd2(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 10
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 10
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  ; x = [0,10), y = [0,10)
+  %res = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %x, i32 %y)
+  %add = extractvalue { i32, i1 } %res, 0
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ult i32 %add, 18
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK-NOT: ret i1 true
+  ret i1 %ret
+}
+
+; Make sure CVP (via LVI) can propagate values through ssub.with.overflow.
+; CHECK-LABEL: @ssub1
+define i1 @ssub1(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 10
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 10
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  %offset = add i32 %x, 9
+  ; x = [0,10), y = [0,10), offset = [9,19)
+  %res = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %offset, i32 %y)
+  %sub = extractvalue { i32, i1 } %res, 0
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ult i32 %sub, 19
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK: ret i1 true
+  ret i1 %ret
+}
+
+; Negative version of previous test.
+; CHECK-LABEL: @ssub2
+define i1 @ssub2(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 10
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 10
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  %offset = add i32 %x, 8
+  ; x = [0,10), y = [0,10), offset = [8,18)
+  %res = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %offset, i32 %y)
+  %sub = extractvalue { i32, i1 } %res, 0
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ult i32 %sub, 19
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK-NOT: ret i1 true
+  ret i1 %ret
+}
+
+; Make sure CVP (via LVI) can propagate values through usub.with.overflow.
+; CHECK-LABEL: @usub1
+define i1 @usub1(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 10
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 10
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  %offset = add i32 %x, 9
+  ; x = [0,10), y = [0,10), offset = [9,19)
+  %res = tail call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %offset, i32 %y)
+  %sub = extractvalue { i32, i1 } %res, 0
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ult i32 %sub, 19
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK: ret i1 true
+  ret i1 %ret
+}
+
+; Negative version of previous test.
+; CHECK-LABEL: @usub2
+define i1 @usub2(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 10
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 10
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  %offset = add i32 %x, 9
+  ; x = [0,10), y = [0,10), offset = [9,19)
+  %res = tail call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %offset, i32 %y)
+  %sub = extractvalue { i32, i1 } %res, 0
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ult i32 %sub, 18
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK-NOT: ret i1 true
+  ret i1 %ret
+}
+
+; Make sure CVP (via LVI) can propagate values through smul.with.overflow.
+; CHECK-LABEL: @smul1
+define i1 @smul1(i32 %x, i32 %y) #0 {
+entry:
+  %x.offset = add i32 %x, 9
+  %cmp1 = icmp ult i32 %x.offset, 19
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %y.offset = add i32 %y, 9
+  %cmp2 = icmp ult i32 %y.offset, 19
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  ; x = [-9,10), y = [-9,10)
+  %res = tail call { i32, i1 } @llvm.smul.with.overflow.i32(i32 %x, i32 %y)
+  %mul = extractvalue { i32, i1 } %res, 0
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp sle i32 %mul, 81
+  %cmp4 = icmp sge i32 %mul, -81
+  %cmp5 = and i1 %cmp3, %cmp4
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp5, %cont3 ]
+; CHECK: ret i1 true
+  ret i1 %ret
+}
+
+; Negative version of previous test.
+; CHECK-LABEL: @smul2
+define i1 @smul2(i32 %x, i32 %y) #0 {
+entry:
+  %x.offset = add i32 %x, 9
+  %cmp1 = icmp ult i32 %x.offset, 19
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %y.offset = add i32 %y, 9
+  %cmp2 = icmp ult i32 %y.offset, 19
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  ; x = [-9,10), y = [-9,10)
+  %res = tail call { i32, i1 } @llvm.smul.with.overflow.i32(i32 %x, i32 %y)
+  %mul = extractvalue { i32, i1 } %res, 0
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp slt i32 %mul, 81
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK-NOT: ret i1 true
+  ret i1 %ret
+}
+
+; Make sure CVP (via LVI) can propagate values through umul.with.overflow.
+; CHECK-LABEL: @umul1
+define i1 @umul1(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 100
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 100
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  %res = tail call { i32, i1 } @llvm.umul.with.overflow.i32(i32 %x, i32 %y)
+  %mul = extractvalue { i32, i1 } %res, 0
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ule i32 %mul, 9801
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK: ret i1 true
+  ret i1 %ret
+}
+
+; Negative version of previous test.
+; CHECK-LABEL: @umul2
+define i1 @umul2(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 100
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 100
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  %res = tail call { i32, i1 } @llvm.umul.with.overflow.i32(i32 %x, i32 %y)
+  %mul = extractvalue { i32, i1 } %res, 0
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ult i32 %mul, 9801
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK-NOT: ret i1 true
+  ret i1 %ret
+}
+
+declare { i32, i1 } @llvm.sadd.with.overflow.i32(i32, i32) #1
+declare { i32, i1 } @llvm.uadd.with.overflow.i32(i32, i32) #1
+declare { i32, i1 } @llvm.ssub.with.overflow.i32(i32, i32) #1
+declare { i32, i1 } @llvm.usub.with.overflow.i32(i32, i32) #1
+declare { i32, i1 } @llvm.smul.with.overflow.i32(i32, i32) #1
+declare { i32, i1 } @llvm.umul.with.overflow.i32(i32, i32) #1