From a410d81f64a89ec2a0d43773b326d2b820ac0357 Mon Sep 17 00:00:00 2001 From: Artur Pilipenko Date: Tue, 9 Aug 2016 09:41:34 +0000 Subject: [PATCH] Teach CorrelatedValuePropagation to mark adds as no wrap Use LVI to prove that adds do not wrap. The change is motivated by https://llvm.org/bugs/show_bug.cgi?id=28620 bug and it's the first step to fix that problem. Reviewed By: sanjoy Differential Revision: http://reviews.llvm.org/D23059 llvm-svn: 278107 --- llvm/lib/Analysis/LazyValueInfo.cpp | 52 ++++++---- .../Transforms/CorrelatedValuePropagation/range.ll | 112 +++++++++++++++++++++ 2 files changed, 145 insertions(+), 19 deletions(-) diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp index 2728687..e6c375a 100644 --- a/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/llvm/lib/Analysis/LazyValueInfo.cpp @@ -1197,30 +1197,44 @@ bool getValueFromCondition(Value *Val, Value *Cond, LVILatticeVal &Result, Result = LVILatticeVal::getNot(cast(RHS)); return true; } + } - // Recognize the range checking idiom that InstCombine produces. - // (X+C1) u< C2 --> [-C1, C2-C1) - ConstantInt *Offset = nullptr; - if (Predicate == ICmpInst::ICMP_ULT) - match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset))); + // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible + // range of Val guaranteed by the condition. Recognize comparisons in the from + // of: + // icmp Val, ... + // icmp ult (add Val, Offset), ... + // The latter is the range checking idiom that InstCombine produces. Subtract + // the offset from the allowed range for RHS in this case. + + // Val or (add Val, Offset) can be on either hand of the comparison + if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) { + std::swap(LHS, RHS); + Predicate = CmpInst::getSwappedPredicate(Predicate); + } - ConstantInt *CI = dyn_cast(RHS); - if (CI && (LHS == Val || Offset)) { - // Calculate the range of values that are allowed by the comparison - ConstantRange CmpRange(CI->getValue()); + ConstantInt *Offset = nullptr; + if (Predicate == ICmpInst::ICMP_ULT) + match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset))); - // If we're interested in the false dest, invert the condition - CmpInst::Predicate Pred = - isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate); - ConstantRange TrueValues = - ConstantRange::makeAllowedICmpRegion(Pred, CmpRange); + if (LHS == Val || Offset) { + // Calculate the range of values that are allowed by the comparison + ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(), + /*isFullSet=*/true); + if (ConstantInt *CI = dyn_cast(RHS)) + RHSRange = ConstantRange(CI->getValue()); - if (Offset) // Apply the offset from above. - TrueValues = TrueValues.subtract(Offset->getValue()); + // If we're interested in the false dest, invert the condition + CmpInst::Predicate Pred = + isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate); + ConstantRange TrueValues = + ConstantRange::makeAllowedICmpRegion(Pred, RHSRange); - Result = LVILatticeVal::getRange(std::move(TrueValues)); - return true; - } + if (Offset) // Apply the offset from above. + TrueValues = TrueValues.subtract(Offset->getValue()); + + Result = LVILatticeVal::getRange(std::move(TrueValues)); + return true; } return false; diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/range.ll b/llvm/test/Transforms/CorrelatedValuePropagation/range.ll index 8ca171a..f8ad6bd 100644 --- a/llvm/test/Transforms/CorrelatedValuePropagation/range.ll +++ b/llvm/test/Transforms/CorrelatedValuePropagation/range.ll @@ -203,3 +203,115 @@ define i1 @test11() { next: ret i1 %test } + +define i32 @test12(i32 %a, i32 %b) { +; CHECK-LABEL: @test12( +; CHECK: then: +; CHECK-NEXT: br i1 false, label %end, label %else + %cmp = icmp ult i32 %a, %b + br i1 %cmp, label %then, label %else + +then: + %dead = icmp eq i32 %a, -1 + br i1 %dead, label %end, label %else + +else: + ret i32 1 + +end: + ret i32 2 +} + +define i32 @test12_swap(i32 %a, i32 %b) { +; CHECK-LABEL: @test12_swap( +; CHECK: then: +; CHECK-NEXT: br i1 false, label %end, label %else + %cmp = icmp ugt i32 %b, %a + br i1 %cmp, label %then, label %else + +then: + %dead = icmp eq i32 %a, -1 + br i1 %dead, label %end, label %else + +else: + ret i32 1 + +end: + ret i32 2 +} + +define i32 @test12_neg(i32 %a, i32 %b) { +; The same as @test12 but the second check is on the false path +; CHECK-LABEL: @test12_neg( +; CHECK: else: +; CHECK-NEXT: %alive = icmp eq i32 %a, -1 + %cmp = icmp ult i32 %a, %b + br i1 %cmp, label %then, label %else + +else: + %alive = icmp eq i32 %a, -1 + br i1 %alive, label %end, label %then + +then: + ret i32 1 + +end: + ret i32 2 +} + +define i32 @test12_signed(i32 %a, i32 %b) { +; The same as @test12 but with signed comparison +; CHECK-LABEL: @test12_signed( +; CHECK: then: +; CHECK-NEXT: br i1 false, label %end, label %else + %cmp = icmp slt i32 %a, %b + br i1 %cmp, label %then, label %else + +then: + %dead = icmp eq i32 %a, 2147483647 + br i1 %dead, label %end, label %else + +else: + ret i32 1 + +end: + ret i32 2 +} + +define i32 @test13(i32 %a, i32 %b) { +; CHECK-LABEL: @test13( +; CHECK: then: +; CHECK-NEXT: br i1 false, label %end, label %else + %a.off = add i32 %a, -8 + %cmp = icmp ult i32 %a.off, %b + br i1 %cmp, label %then, label %else + +then: + %dead = icmp eq i32 %a, 7 + br i1 %dead, label %end, label %else + +else: + ret i32 1 + +end: + ret i32 2 +} + +define i32 @test13_swap(i32 %a, i32 %b) { +; CHECK-LABEL: @test13_swap( +; CHECK: then: +; CHECK-NEXT: br i1 false, label %end, label %else + %a.off = add i32 %a, -8 + %cmp = icmp ugt i32 %b, %a.off + br i1 %cmp, label %then, label %else + +then: + %dead = icmp eq i32 %a, 7 + br i1 %dead, label %end, label %else + +else: + ret i32 1 + +end: + ret i32 2 +} -- 2.7.4