Index: include/llvm/Analysis/LazyValueInfo.h =================================================================== --- include/llvm/Analysis/LazyValueInfo.h +++ include/llvm/Analysis/LazyValueInfo.h @@ -21,6 +21,7 @@ namespace llvm { class AssumptionCache; class Constant; + class ConstantInt; class ConstantRange; class DataLayout; class DominatorTree; @@ -73,6 +74,11 @@ BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI = nullptr); + Tristate getPredicateOnEdgeAfterAdd(unsigned Pred, Value *V, Constant *C, + ConstantInt *Addend, + BasicBlock *FromBB, BasicBlock *ToBB, + Instruction *CxtI = nullptr); + /// Determine whether the specified value comparison with a constant is known /// to be true or false at the specified instruction /// (from an assume intrinsic). Pred is a CmpInst predicate. Index: lib/Analysis/LazyValueInfo.cpp =================================================================== --- lib/Analysis/LazyValueInfo.cpp +++ lib/Analysis/LazyValueInfo.cpp @@ -1693,6 +1693,36 @@ return nullptr; } +static LazyValueInfo::Tristate +getPredicateResultForRange(unsigned Pred, Constant *C, + const ConstantRange &CR) { + ConstantInt *CI = dyn_cast(C); + if (!CI) return LazyValueInfo::Unknown; + + if (Pred == ICmpInst::ICMP_EQ) { + if (!CR.contains(CI->getValue())) + return LazyValueInfo::False; + + if (CR.isSingleElement() && CR.contains(CI->getValue())) + return LazyValueInfo::True; + } else if (Pred == ICmpInst::ICMP_NE) { + if (!CR.contains(CI->getValue())) + return LazyValueInfo::True; + + if (CR.isSingleElement() && CR.contains(CI->getValue())) + return LazyValueInfo::False; + } + + // Handle more complex predicates. + const ConstantRange &TrueValues = ConstantRange::makeExactICmpRegion( + (ICmpInst::Predicate)Pred, CI->getValue()); + if (TrueValues.contains(CR)) + return LazyValueInfo::True; + if (TrueValues.inverse().contains(CR)) + return LazyValueInfo::False; + return LazyValueInfo::Unknown; +} + static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C, LVILatticeVal &Result, const DataLayout &DL, @@ -1708,34 +1738,8 @@ return LazyValueInfo::Unknown; } - if (Result.isConstantRange()) { - ConstantInt *CI = dyn_cast(C); - if (!CI) return LazyValueInfo::Unknown; - - const ConstantRange &CR = Result.getConstantRange(); - if (Pred == ICmpInst::ICMP_EQ) { - if (!CR.contains(CI->getValue())) - return LazyValueInfo::False; - - if (CR.isSingleElement() && CR.contains(CI->getValue())) - return LazyValueInfo::True; - } else if (Pred == ICmpInst::ICMP_NE) { - if (!CR.contains(CI->getValue())) - return LazyValueInfo::True; - - if (CR.isSingleElement() && CR.contains(CI->getValue())) - return LazyValueInfo::False; - } - - // Handle more complex predicates. - ConstantRange TrueValues = ConstantRange::makeExactICmpRegion( - (ICmpInst::Predicate)Pred, CI->getValue()); - if (TrueValues.contains(CR)) - return LazyValueInfo::True; - if (TrueValues.inverse().contains(CR)) - return LazyValueInfo::False; - return LazyValueInfo::Unknown; - } + if (Result.isConstantRange()) + return getPredicateResultForRange(Pred, C, Result.getConstantRange()); if (Result.isNotConstant()) { // If this is an equality comparison, we can try to fold it knowing that @@ -1774,6 +1778,27 @@ return getPredicateResult(Pred, C, Result, DL, TLI); } +/// Determine whether the specified value comparison with a constant is known to +/// be true or false on the specified CFG edge. Pred is a CmpInst predicate. +LazyValueInfo::Tristate +LazyValueInfo::getPredicateOnEdgeAfterAdd(unsigned Pred, Value *V, Constant *C, + ConstantInt *Addend, + BasicBlock *FromBB, BasicBlock *ToBB, + Instruction *CxtI) { + const DataLayout &DL = FromBB->getModule()->getDataLayout(); + LVILatticeVal Result = + getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); + // Only handle ConstantRanges. + if (!Result.isConstantRange()) + return LazyValueInfo::Unknown; + + ConstantRange CR = Result.getConstantRange(); + // Adjust the range by the Addend. + CR = CR.add(ConstantRange(Addend->getValue())); + + return getPredicateResultForRange(Pred, C, CR); +} + LazyValueInfo::Tristate LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI) { Index: lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- lib/Transforms/Scalar/JumpThreading.cpp +++ lib/Transforms/Scalar/JumpThreading.cpp @@ -601,6 +601,34 @@ return !Result.empty(); } + // InstCombine can fold some forms of constant range checks into + // (icmp (add (x, C1)), C2). See if we have we have such a thing with + // x as a live-in. + Instruction *CmpIn = cast(Cmp->getOperand(0)); + if (CmpIn->getOpcode() == Instruction::Add) { + if (!isa(CmpIn->getOperand(0)) || + cast(CmpIn->getOperand(0))->getParent() != BB) { + if (auto *AddC = dyn_cast(CmpIn->getOperand(1))) { + for (BasicBlock *P : predecessors(BB)) { + // If the value is known by LazyValueInfo to be a constant in a + // predecessor, use that information to try to thread this block. + LazyValueInfo::Tristate Res = + LVI->getPredicateOnEdgeAfterAdd(Cmp->getPredicate(), + CmpIn->getOperand(0), CmpConst, + AddC, P, BB, + CxtI ? CxtI : CmpIn); + if (Res == LazyValueInfo::Unknown) + continue; + + Constant *ResC = ConstantInt::get(Cmp->getType(), Res); + Result.push_back(std::make_pair(ResC, P)); + } + + return !Result.empty(); + } + } + } + // Try to find a constant value for the LHS of a comparison, // and evaluate it statically if we can. PredValueInfoTy LHSVals; Index: test/Transforms/JumpThreading/range-compare.ll =================================================================== --- /dev/null +++ test/Transforms/JumpThreading/range-compare.ll @@ -0,0 +1,49 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -simplifycfg -instcombine -jump-threading -S | FileCheck %s + +; The important bit here is that after calling bar we should jump directly to the ret. +define void @foo(i32 %x) { +; CHECK-LABEL: @foo( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i32 [[X:%.*]], 9 +; CHECK-NEXT: br i1 [[CMP]], label %if.end.thread, label %if.end +; CHECK: if.end.thread: +; CHECK-NEXT: call void (...) @bar() +; CHECK-NEXT: br label %if.end4 +; CHECK: if.end: +; CHECK-NEXT: [[X_OFF:%.*]] = add i32 [[X]], -3 +; CHECK-NEXT: [[TMP0:%.*]] = icmp ult i32 [[X_OFF]], 5 +; CHECK-NEXT: br i1 [[TMP0]], label %if.then3, label %if.end4 +; CHECK: if.then3: +; CHECK-NEXT: call void (...) @baz() +; CHECK-NEXT: br label %if.end4 +; CHECK: if.end4: +; CHECK-NEXT: ret void +; +entry: + %cmp = icmp sge i32 %x, 10 + br i1 %cmp, label %if.then, label %if.end + +if.then: ; preds = %entry + call void (...) @bar() + br label %if.end + +if.end: ; preds = %if.then, %entry + %cmp1 = icmp sge i32 %x, 3 + br i1 %cmp1, label %land.lhs.true, label %if.end4 + +land.lhs.true: ; preds = %if.end + %cmp2 = icmp slt i32 %x, 8 + br i1 %cmp2, label %if.then3, label %if.end4 + +if.then3: ; preds = %land.lhs.true + call void (...) @baz() + br label %if.end4 + +if.end4: ; preds = %if.then3, %land.lhs.true, %if.end + ret void +} + +declare void @bar(...) + +declare void @baz(...)