[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

                                 PHINode *PN, BasicBlock *BB);
     bool solveBlockValueSelect(LVILatticeVal &BBLV,
                                SelectInst *S, BasicBlock *BB); 
+    bool solveBlockValueExtractValue(LVILatticeVal &BBLV,
+                                     ExtractValueInst *EV, BasicBlock *BB);
     bool solveBlockValueBinaryOp(LVILatticeVal &BBLV,
                               Instruction *BBI, BasicBlock *BB);
     bool solveBlockValueCast(LVILatticeVal &BBLV,

     return true;
   }
   if (BBI->getType()->isIntegerTy()) {
+    if (auto *EV = dyn_cast<ExtractValueInst>(BBI)) {
+      if (!solveBlockValueExtractValue(Res, EV, BB))
+        return false;
+      insertResult(Val, BB, Res);
+      return true;
+    }
     if (isa<CastInst>(BBI)) {
       if (!solveBlockValueCast(Res, BBI, BB))
         return false;

   return true;
 }
 
+static ConstantRange transfer(unsigned Opcode, ConstantRange LHS,
+                              ConstantRange RHS) {
+  // NOTE: We're currently limited by the set of operations that ConstantRange
+  // can evaluate symbolically.  Enhancing that set will allow us to analyze
+  // more definitions.
+  switch (Opcode) {
+  case Instruction::Add:
+  case Intrinsic::sadd_with_overflow:
+  case Intrinsic::uadd_with_overflow:
+    return LHS.add(RHS);
+  case Instruction::Sub:
+  case Intrinsic::ssub_with_overflow:
+  case Intrinsic::usub_with_overflow:
+    return LHS.sub(RHS);
+  case Instruction::Mul:
+  case Intrinsic::smul_with_overflow:
+  case Intrinsic::umul_with_overflow:
+    return LHS.multiply(RHS);
+  case Instruction::UDiv:
+    return LHS.udiv(RHS);
+  case Instruction::Shl:
+    return LHS.shl(RHS);
+  case Instruction::LShr:
+    return LHS.lshr(RHS);
+  case Instruction::And:
+    return LHS.binaryAnd(RHS);
+  case Instruction::Or:
+    return LHS.binaryOr(RHS);
+  default:
+    llvm_unreachable("unsupported binop or intrinsic");
+    break;
+  }
+}
+
+bool LazyValueInfoCache::solveBlockValueExtractValue(LVILatticeVal &BBLV,
+                                                     ExtractValueInst *EV,
+                                                     BasicBlock *BB) {
+  // The only case we're handling is extracting the non-overflow result of an
+  // x.with.overflow intrinsic.
+  IntrinsicInst *II = dyn_cast<IntrinsicInst>(EV->getOperand(0));
+  if (!II) {
+    BBLV.markOverdefined();
+    return true;
+  }
+
+  // Bail early unless we're getting the zero-indexed output (the non-overflow
+  // result).
+  if (EV->getNumIndices() != 1 || *EV->idx_begin() != 0) {
+    BBLV.markOverdefined();
+    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.markOverdefined();
+    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();
+  }
+
+  BBLV.markConstantRange(transfer(II->getIntrinsicID(), LHSRange, RHSRange));
+  return true;
+}
+
 bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
                                                 PHINode *PN, BasicBlock *BB) {
   LVILatticeVal Result;  // Start Undefined.

   ConstantInt *RHS = cast<ConstantInt>(BBI->getOperand(1));
   ConstantRange RHSRange = ConstantRange(RHS->getValue());
 
-  // NOTE: We're currently limited by the set of operations that ConstantRange
-  // can evaluate symbolically.  Enhancing that set will allows us to analyze
-  // more definitions.
-  LVILatticeVal Result;
-  switch (BBI->getOpcode()) {
-  case Instruction::Add:
-    Result.markConstantRange(LHSRange.add(RHSRange));
-    break;
-  case Instruction::Sub:
-    Result.markConstantRange(LHSRange.sub(RHSRange));
-    break;
-  case Instruction::Mul:
-    Result.markConstantRange(LHSRange.multiply(RHSRange));
-    break;
-  case Instruction::UDiv:
-    Result.markConstantRange(LHSRange.udiv(RHSRange));
-    break;
-  case Instruction::Shl:
-    Result.markConstantRange(LHSRange.shl(RHSRange));
-    break;
-  case Instruction::LShr:
-    Result.markConstantRange(LHSRange.lshr(RHSRange));
-    break;
-  case Instruction::And:
-    Result.markConstantRange(LHSRange.binaryAnd(RHSRange));
-    break;
-  case Instruction::Or:
-    Result.markConstantRange(LHSRange.binaryOr(RHSRange));
-    break;
-  default:
-    // Should be dead if the code above is correct
-    llvm_unreachable("inconsistent with above");
-    break;
-  }
-
-  BBLV = Result;
+  BBLV.markConstantRange(transfer(BBI->getOpcode(), LHSRange, RHSRange));
   return true;
 }
 

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