Index: llvm/trunk/lib/Analysis/LazyValueInfo.cpp =================================================================== --- llvm/trunk/lib/Analysis/LazyValueInfo.cpp +++ llvm/trunk/lib/Analysis/LazyValueInfo.cpp @@ -1197,30 +1197,47 @@ 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))); - - 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()); - - // 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 (!Val->getType()->isIntegerTy()) + return false; - if (Offset) // Apply the offset from above. - TrueValues = TrueValues.subtract(Offset->getValue()); + // 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 *Offset = nullptr; + if (Predicate == ICmpInst::ICMP_ULT) + match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset))); + + 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 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; Index: llvm/trunk/test/Transforms/CorrelatedValuePropagation/range.ll =================================================================== --- llvm/trunk/test/Transforms/CorrelatedValuePropagation/range.ll +++ llvm/trunk/test/Transforms/CorrelatedValuePropagation/range.ll @@ -203,3 +203,115 @@ 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 +}