Index: llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp =================================================================== --- llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -64,7 +64,7 @@ STATISTIC(NumSRems, "Number of srem converted to urem"); STATISTIC(NumOverflows, "Number of overflow checks removed"); -static cl::opt DontProcessAdds("cvp-dont-process-adds", cl::init(true)); +static cl::opt DontProcessAddNSubs("cvp-dont-process-addnsubs", cl::init(true)); namespace { @@ -626,53 +626,53 @@ return true; } -static bool processAdd(BinaryOperator *AddOp, LazyValueInfo *LVI) { +static bool processAddSub(BinaryOperator *AddSubOp, LazyValueInfo *LVI) { using OBO = OverflowingBinaryOperator; - if (DontProcessAdds) + if (DontProcessAddNSubs) return false; - if (AddOp->getType()->isVectorTy()) + if (AddSubOp->getType()->isVectorTy()) return false; - bool NSW = AddOp->hasNoSignedWrap(); - bool NUW = AddOp->hasNoUnsignedWrap(); + bool NSW = AddSubOp->hasNoSignedWrap(); + bool NUW = AddSubOp->hasNoUnsignedWrap(); if (NSW && NUW) return false; - BasicBlock *BB = AddOp->getParent(); + BasicBlock *BB = AddSubOp->getParent(); - Value *LHS = AddOp->getOperand(0); - Value *RHS = AddOp->getOperand(1); + Value *LHS = AddSubOp->getOperand(0); + Value *RHS = AddSubOp->getOperand(1); - ConstantRange LRange = LVI->getConstantRange(LHS, BB, AddOp); + ConstantRange RRange = LVI->getConstantRange(RHS, BB, AddSubOp); - // Initialize RRange only if we need it. If we know that guaranteed no wrap - // range for the given LHS range is empty don't spend time calculating the - // range for the RHS. - Optional RRange; - auto LazyRRange = [&] () { - if (!RRange) - RRange = LVI->getConstantRange(RHS, BB, AddOp); - return RRange.getValue(); + // Initialize LRange only if we need it. If we know that guaranteed no wrap + // range for the given RHS range is empty don't spend time calculating the + // range for the LHS. + Optional LRange; + auto LazyLRange = [&] () { + if (!LRange) + LRange = LVI->getConstantRange(LHS, BB, AddSubOp); + return LRange.getValue(); }; bool Changed = false; if (!NUW) { ConstantRange NUWRange = ConstantRange::makeGuaranteedNoWrapRegion( - BinaryOperator::Add, LRange, OBO::NoUnsignedWrap); + AddSubOp->getOpcode(), RRange, OBO::NoUnsignedWrap); if (!NUWRange.isEmptySet()) { - bool NewNUW = NUWRange.contains(LazyRRange()); - AddOp->setHasNoUnsignedWrap(NewNUW); + bool NewNUW = NUWRange.contains(LazyLRange()); + AddSubOp->setHasNoUnsignedWrap(NewNUW); Changed |= NewNUW; } } if (!NSW) { ConstantRange NSWRange = ConstantRange::makeGuaranteedNoWrapRegion( - BinaryOperator::Add, LRange, OBO::NoSignedWrap); + AddSubOp->getOpcode(), RRange, OBO::NoSignedWrap); if (!NSWRange.isEmptySet()) { - bool NewNSW = NSWRange.contains(LazyRRange()); - AddOp->setHasNoSignedWrap(NewNSW); + bool NewNSW = NSWRange.contains(LazyLRange()); + AddSubOp->setHasNoSignedWrap(NewNSW); Changed |= NewNSW; } } @@ -748,7 +748,8 @@ BBChanged |= processAShr(cast(II), LVI); break; case Instruction::Add: - BBChanged |= processAdd(cast(II), LVI); + case Instruction::Sub: + BBChanged |= processAddSub(cast(II), LVI); break; } } Index: llvm/test/Transforms/CorrelatedValuePropagation/add.ll =================================================================== --- llvm/test/Transforms/CorrelatedValuePropagation/add.ll +++ llvm/test/Transforms/CorrelatedValuePropagation/add.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -correlated-propagation -cvp-dont-process-adds=false -S | FileCheck %s +; RUN: opt < %s -correlated-propagation -cvp-dont-process-addnsubs=false -S | FileCheck %s ; CHECK-LABEL: @test0( define void @test0(i32 %a) { Index: llvm/test/Transforms/CorrelatedValuePropagation/sub.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/CorrelatedValuePropagation/sub.ll @@ -0,0 +1,392 @@ +; RUN: opt < %s -correlated-propagation -cvp-dont-process-addnsubs=false -S | FileCheck %s + +; CHECK-LABEL: @test0( +define void @test0(i32 %a) { +entry: + %cmp = icmp sgt i32 %a, 100 + br i1 %cmp, label %bb, label %exit + +bb: +; CHECK: %sub = sub nuw nsw i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +; CHECK-LABEL: @test1( +define void @test1(i32 %a) { +entry: + %cmp = icmp ugt i32 %a, 100 + br i1 %cmp, label %bb, label %exit + +bb: +; CHECK: %sub = sub nuw i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +; CHECK-LABEL: @test2( +define void @test2(i32 %a) { +entry: + %cmp = icmp ugt i32 %a, -1 + br i1 %cmp, label %bb, label %exit + +bb: +; CHECK: %sub = sub i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +; CHECK-LABEL: @test3( +define void @test3(i32 %a) { +entry: + %cmp = icmp sgt i32 %a, -1 + br i1 %cmp, label %bb, label %exit + +bb: +; CHECK: %sub = sub nsw i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +; CHECK-LABEL: @test4( +define void @test4(i32 %a) { +entry: + %cmp = icmp ugt i32 %a, 2147483647 + br i1 %cmp, label %bb, label %exit + +bb: +; CHECK: %sub = sub nuw i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +; CHECK-LABEL: @test5( +define void @test5(i32 %a) { +entry: + %cmp = icmp sle i32 %a, 2147483647 + br i1 %cmp, label %bb, label %exit + +bb: +; CHECK: %sub = sub i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +; Check for a corner case where an integer value is represented with a constant +; LVILatticeValue instead of constantrange. Check that we don't fail with an +; assertion in this case. +@b = global i32 0, align 4 +define void @test6(i32 %a) { +bb: + %sub = sub i32 %a, ptrtoint (i32* @b to i32) + ret void +} + +; Check that we can gather information for conditions in the form of +; and ( i s< 100, Unknown ) +; CHECK-LABEL: @test7( +define void @test7(i32 %a, i1 %flag) { +entry: + %cmp.1 = icmp ugt i32 %a, 100 + %cmp = and i1 %cmp.1, %flag + br i1 %cmp, label %bb, label %exit + +bb: +; CHECK: %sub = sub nuw i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +; Check that we can gather information for conditions in the form of +; and ( i s< 100, i s> 0 ) +; CHECK-LABEL: @test8( +define void @test8(i32 %a) { +entry: + %cmp.1 = icmp slt i32 %a, 100 + %cmp.2 = icmp sgt i32 %a, 0 + %cmp = and i1 %cmp.1, %cmp.2 + br i1 %cmp, label %bb, label %exit + +bb: +; CHECK: %sub = sub nuw nsw i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +; Check that for conditions in the form of cond1 && cond2 we don't mistakenly +; assume that !cond1 && !cond2 holds down to false path. +; CHECK-LABEL: @test8_neg( +define void @test8_neg(i32 %a) { +entry: + %cmp.1 = icmp sge i32 %a, 100 + %cmp.2 = icmp sle i32 %a, 0 + %cmp = and i1 %cmp.1, %cmp.2 + br i1 %cmp, label %exit, label %bb + +bb: +; CHECK: %sub = sub i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +; Check that we can gather information for conditions in the form of +; and ( i s< 100, and (i s> 0, Unknown ) +; CHECK-LABEL: @test9( +define void @test9(i32 %a, i1 %flag) { +entry: + %cmp.1 = icmp slt i32 %a, 100 + %cmp.2 = icmp sgt i32 %a, 0 + %cmp.3 = and i1 %cmp.2, %flag + %cmp = and i1 %cmp.1, %cmp.3 + br i1 %cmp, label %bb, label %exit + +bb: +; CHECK: %sub = sub nuw nsw i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +; Check that we can gather information for conditions in the form of +; and ( i s> Unknown, ... ) +; CHECK-LABEL: @test10( +define void @test10(i32 %a, i32 %b, i1 %flag) { +entry: + %cmp.1 = icmp sgt i32 %a, %b + %cmp = and i1 %cmp.1, %flag + br i1 %cmp, label %bb, label %exit + +bb: +; CHECK: %sub = sub nsw i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +@limit = external global i32 +; CHECK-LABEL: @test11( +define i32 @test11(i32* %p, i32 %i) { + %limit = load i32, i32* %p, !range !{i32 0, i32 2147483647} + %within.1 = icmp slt i32 %limit, %i + %i.minus.7 = add i32 %i, -7 + %within.2 = icmp slt i32 %limit, %i.minus.7 + %within = and i1 %within.1, %within.2 + br i1 %within, label %then, label %else + +then: +; CHECK: %i.minus.6 = sub nuw nsw i32 %i, 6 + %i.minus.6 = sub i32 %i, 6 + ret i32 %i.minus.6 + +else: + ret i32 0 +} + +; Check that we can gather information for conditions is the form of +; or ( i s<= -100, Unknown ) +; CHECK-LABEL: @test12( +define void @test12(i32 %a, i1 %flag) { +entry: + %cmp.1 = icmp sle i32 %a, -100 + %cmp = or i1 %cmp.1, %flag + br i1 %cmp, label %exit, label %bb + +bb: +; CHECK: %sub = sub nsw i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +; Check that we can gather information for conditions is the form of +; or ( i s>= 100, i s<= 0 ) +; CHECK-LABEL: @test13( +define void @test13(i32 %a) { +entry: + %cmp.1 = icmp sge i32 %a, 100 + %cmp.2 = icmp sle i32 %a, 0 + %cmp = or i1 %cmp.1, %cmp.2 + br i1 %cmp, label %exit, label %bb + +bb: +; CHECK: %sub = sub nuw nsw i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +; Check that for conditions is the form of cond1 || cond2 we don't mistakenly +; assume that cond1 || cond2 holds down to true path. +; CHECK-LABEL: @test13_neg( +define void @test13_neg(i32 %a) { +entry: + %cmp.1 = icmp slt i32 %a, 100 + %cmp.2 = icmp sgt i32 %a, 0 + %cmp = or i1 %cmp.1, %cmp.2 + br i1 %cmp, label %bb, label %exit + +bb: +; CHECK: %sub = sub i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +; Check that we can gather information for conditions is the form of +; or ( i s>=100, or (i s<= 0, Unknown ) +; CHECK-LABEL: @test14( +define void @test14(i32 %a, i1 %flag) { +entry: + %cmp.1 = icmp sge i32 %a, 100 + %cmp.2 = icmp sle i32 %a, 0 + %cmp.3 = or i1 %cmp.2, %flag + %cmp = or i1 %cmp.1, %cmp.3 + br i1 %cmp, label %exit, label %bb + +bb: +; CHECK: %sub = sub nuw nsw i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +; Check that we can gather information for conditions is the form of +; or ( i s<= Unknown, ... ) +; CHECK-LABEL: @test15( +define void @test15(i32 %a, i32 %b, i1 %flag) { +entry: + %cmp.1 = icmp sle i32 %a, %b + %cmp = or i1 %cmp.1, %flag + br i1 %cmp, label %exit, label %bb + +bb: +; CHECK: %sub = sub nsw i32 %a, 1 + %sub = sub i32 %a, 1 + br label %exit + +exit: + ret void +} + +; single basic block loop +; because the loop exit condition is SLT, we can supplement the iv sub +; (iv.next def) with an nsw. +; CHECK-LABEL: @test16( +define i32 @test16(i32* %n, i32* %a) { +preheader: + br label %loop + +loop: +; CHECK: %iv.next = sub nsw i32 %iv, -1 + %iv = phi i32 [ 0, %preheader ], [ %iv.next, %loop ] + %acc = phi i32 [ 0, %preheader ], [ %acc.curr, %loop ] + %x = load atomic i32, i32* %a unordered, align 8 + fence acquire + %acc.curr = sub i32 %acc, %x + %iv.next = sub i32 %iv, -1 + %nval = load atomic i32, i32* %n unordered, align 8 + %cmp = icmp slt i32 %iv.next, %nval + br i1 %cmp, label %loop, label %exit + +exit: + ret i32 %acc.curr +} + +; CHECK-LABEL: @test17( +define void @test17(i32 %a) { +entry: + %cmp = icmp sgt i32 %a, 100 + br i1 %cmp, label %bb, label %exit + +bb: +; CHECK: %sub = sub nsw i32 1, %a + %sub = sub i32 1, %a + br label %exit + +exit: + ret void +} + +; CHECK-LABEL: @test18( +define void @test18(i32 %a) { +entry: + %cmp = icmp sgt i32 %a, 10000 + br i1 %cmp, label %bb, label %exit + +bb: +; CHECK: %sub = sub nuw i32 -2, %a + %sub = sub i32 -2, %a + br label %exit + +exit: + ret void +} + +; CHECK-LABEL: @test19( +define void @test19(i32 %a) { +entry: + %cmp = icmp ult i32 %a, 100 + br i1 %cmp, label %bb, label %exit + +bb: +; CHECK: %sub = sub nuw nsw i32 -1, %a + %sub = sub i32 -1, %a + br label %exit + +exit: + ret void +} + +; CHECK-LABEL: @test20( +define void @test20(i32 %a) { +entry: + %cmp = icmp ugt i32 %a, 2147483647 + br i1 %cmp, label %bb, label %exit + +bb: +; CHECK: %sub = sub i32 0, %a + %sub = sub i32 0, %a + br label %exit + +exit: + ret void +} \ No newline at end of file