[CVP] Simplify umulo and smulo that cannot overflow

[nikic]

Summary

If a umul.with.overflow or smul.with.overflow operation cannot overflow, simplify it to a simple mul nuw / mul nsw. After the refactoring in D60668 this is just a matter of removing an explicit check against multiplications.

[lebedev.ri]

LG, thank you.

[uabelho]

Hi,

I see crashed with this patch. E.g.

opt -S -o - cvp_crash.ll -correlated-propagation

on

define void @f() {
  %mul = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 1, i8 2)
  ret void
}

declare { i8, i1 } @llvm.umul.with.overflow.i8(i8, i8)

gives

opt: ../include/llvm/Support/Casting.h:264: typename cast_retty<X, Y *>::ret_type llvm::cast(Y *) [X = llvm::Instruction, Y = llvm::Value]: Assertion `isa<X>(Val) && "cast<Ty>() argument of incompatible type!"' failed.

Program received signal SIGABRT, Aborted.


(gdb) where
#0  0x00007ffff67bbc37 in __GI_raise (sig=sig@entry=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:56
#1  0x00007ffff67bf028 in __GI_abort () at abort.c:89
#2  0x00007ffff67b4bf6 in __assert_fail_base (fmt=0x7ffff6909058 "%s%s%s:%u: %s%sAssertion `%s' failed.\n%n", assertion=assertion@entry=0x448edf9 "isa<X>(Val) && \"cast<Ty>() argument of incompatible type!\"", file=file@entry=0x448ed5a "../include/llvm/Support/Casting.h", line=line@entry=264, function=function@entry=0x448fa5c "typename cast_retty<X, Y *>::ret_type llvm::cast(Y *) [X = llvm::Instruction, Y = llvm::Value]") at assert.c:92
#3  0x00007ffff67b4ca2 in __GI___assert_fail (assertion=0x448edf9 "isa<X>(Val) && \"cast<Ty>() argument of incompatible type!\"", file=0x448ed5a "../include/llvm/Support/Casting.h", line=264, function=0x448fa5c "typename cast_retty<X, Y *>::ret_type llvm::cast(Y *) [X = llvm::Instruction, Y = llvm::Value]") at assert.c:101
#4  0x0000000000d64129 in llvm::cast<llvm::Instruction, llvm::Value> (Val=0x6d8df00) at ../include/llvm/Support/Casting.h:264
#5  0x000000000348d282 in processOverflowIntrinsic (WO=0x6d8e188) at ../lib/Transforms/Scalar/CorrelatedValuePropagation.cpp:422
#6  0x000000000348b59f in processCallSite (CS=..., LVI=0x6d5c9d0) at ../lib/Transforms/Scalar/CorrelatedValuePropagation.cpp:438
#7  0x000000000348a9a9 in runImpl (F=..., LVI=0x6d5c9d0, DT=0x6d8e390, SQ=...) at ../lib/Transforms/Scalar/CorrelatedValuePropagation.cpp:713
#8  0x000000000348d874 in (anonymous namespace)::CorrelatedValuePropagation::runOnFunction (this=0x6d8d5b0, F=...) at ../lib/Transforms/Scalar/CorrelatedValuePropagation.cpp:768
#9  0x0000000002f26e48 in llvm::FPPassManager::runOnFunction (this=0x6d8b6c0, F=...) at ../lib/IR/LegacyPassManager.cpp:1648
#10 0x0000000002f272c5 in llvm::FPPassManager::runOnModule (this=0x6d8b6c0, M=...) at ../lib/IR/LegacyPassManager.cpp:1688
#11 0x0000000002f27a87 in (anonymous namespace)::MPPassManager::runOnModule (this=0x6d8b1c0, M=...) at ../lib/IR/LegacyPassManager.cpp:1755
#12 0x0000000002f2758d in llvm::legacy::PassManagerImpl::run (this=0x6d8ad20, M=...) at ../lib/IR/LegacyPassManager.cpp:1868
#13 0x0000000002f28041 in llvm::legacy::PassManager::run (this=0x7fffffffd4e8, M=...) at ../lib/IR/LegacyPassManager.cpp:1899
#14 0x0000000000da3a64 in main (argc=6, argv=0x7fffffffda88) at ../tools/opt/opt.cpp:901

Problem seems to be in processOverflowIntrinsic:

static void processOverflowIntrinsic(WithOverflowInst *WO) {
  IRBuilder<> B(WO);
  Value *NewOp = B.CreateBinOp(
      WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), WO->getName());
  if (WO->isSigned())
    cast<Instruction>(NewOp)->setHasNoSignedWrap();
  else
    cast<Instruction>(NewOp)->setHasNoUnsignedWrap();

when it crashes we have

$11 = void
(gdb) call WO->dump()
  %mul = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 1, i8 2)
(gdb) call NewOp->dump()
i8 2

So I suppose cases where NewOp is evaluated to a constant doesn't work since then the cast<Instruction> crashes.

[lebedev.ri]

Right. Sorry about that. I thought it can't happen and would have been cleaned up
by instsimplify already, but that clearly doesn't happen,
at least if we feed the pass that input directly.

[nikic]

Thanks @uabelho for the report and @lebedev.ri for fixing it!

llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

if (Changed)
     // by a branch then do so now.
     ConstantFoldTerminator(BB, /*DeleteDeadConditions = */ false,
                            /*TLI = */ nullptr, &DTU);
   return Changed;
 }
 
 // See if we can prove that the given overflow intrinsic will not overflow.
 static bool willNotOverflow(WithOverflowInst *WO, LazyValueInfo *LVI) {
-  // TODO: Also support multiplication.
-  Instruction::BinaryOps BinOp = WO->getBinaryOp();
-  if (BinOp == Instruction::Mul)
-    return false;
-
   Value *RHS = WO->getRHS();
   ConstantRange RRange = LVI->getConstantRange(RHS, WO->getParent(), WO);
   ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
-      BinOp, RRange, WO->getNoWrapKind());
+      WO->getBinaryOp(), RRange, WO->getNoWrapKind());
   // As an optimization, do not compute LRange if we do not need it.
   if (NWRegion.isEmptySet())
     return false;
   Value *LHS = WO->getLHS();
   ConstantRange LRange = LVI->getConstantRange(LHS, WO->getParent(), WO);
   return NWRegion.contains(LRange);
 }
 

llvm/trunk/test/Transforms/CorrelatedValuePropagation/overflows.ll

 }
 
 define i32 @unsigned_mul(i32 %x) {
 ; CHECK-LABEL: @unsigned_mul(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[X:%.*]], 10000
 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
 ; CHECK:       cond.false:
-; CHECK-NEXT:    [[MULO:%.*]] = tail call { i32, i1 } @llvm.umul.with.overflow.i32(i32 [[X]], i32 100)
-; CHECK-NEXT:    [[RES:%.*]] = extractvalue { i32, i1 } [[MULO]], 0
-; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i32, i1 } [[MULO]], 1
+; CHECK-NEXT:    [[MULO1:%.*]] = mul nuw i32 [[X]], 100
+; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } undef, i32 [[MULO1]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = insertvalue { i32, i1 } [[TMP0]], i1 false, 1
+; CHECK-NEXT:    [[RES:%.*]] = extractvalue { i32, i1 } [[TMP1]], 0
+; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i32, i1 } [[TMP1]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[TRAP:%.*]], label [[COND_END]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    tail call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[RES]], [[COND_FALSE]] ]
 ; CHECK-NEXT:    ret i32 [[COND]]
 ;

 define i32 @signed_mul(i32 %x) {
 ; CHECK-LABEL: @signed_mul(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i32 [[X:%.*]], 10000
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[X]], -10000
 ; CHECK-NEXT:    [[CMP3:%.*]] = or i1 [[CMP1]], [[CMP2]]
 ; CHECK-NEXT:    br i1 [[CMP3]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
 ; CHECK:       cond.false:
-; CHECK-NEXT:    [[MULO:%.*]] = tail call { i32, i1 } @llvm.smul.with.overflow.i32(i32 [[X]], i32 100)
-; CHECK-NEXT:    [[RES:%.*]] = extractvalue { i32, i1 } [[MULO]], 0
-; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i32, i1 } [[MULO]], 1
+; CHECK-NEXT:    [[MULO1:%.*]] = mul nsw i32 [[X]], 100
+; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } undef, i32 [[MULO1]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = insertvalue { i32, i1 } [[TMP0]], i1 false, 1
+; CHECK-NEXT:    [[RES:%.*]] = extractvalue { i32, i1 } [[TMP1]], 0
+; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i32, i1 } [[TMP1]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[TRAP:%.*]], label [[COND_END]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    tail call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[RES]], [[COND_FALSE]] ]
 ; CHECK-NEXT:    ret i32 [[COND]]
 ;