Index: include/llvm/Analysis/LazyValueInfo.h =================================================================== --- include/llvm/Analysis/LazyValueInfo.h +++ include/llvm/Analysis/LazyValueInfo.h @@ -93,6 +93,13 @@ Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI = nullptr); + /// Return the ConstantRage constraint that is known to hold for the + /// specified value on the specified edge. This may be only be called + /// on integer-typed Values. + ConstantRange getConstantRangeOnEdge(Value *V, BasicBlock *FromBB, + BasicBlock *ToBB, + Instruction *CxtI = nullptr); + /// Inform the analysis cache that we have threaded an edge from /// PredBB to OldSucc to be from PredBB to NewSucc instead. void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc); Index: lib/Analysis/LazyValueInfo.cpp =================================================================== --- lib/Analysis/LazyValueInfo.cpp +++ lib/Analysis/LazyValueInfo.cpp @@ -1660,6 +1660,26 @@ return nullptr; } +ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V, + BasicBlock *FromBB, + BasicBlock *ToBB, + Instruction *CxtI) { + unsigned Width = V->getType()->getIntegerBitWidth(); + const DataLayout &DL = FromBB->getModule()->getDataLayout(); + LVILatticeVal Result = + getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); + + if (Result.isUndefined()) + return ConstantRange(Width, /*isFullSet=*/false); + if (Result.isConstantRange()) + return Result.getConstantRange(); + // We represent ConstantInt constants as constant ranges but other kinds + // of integer constants, i.e. ConstantExpr will be tagged as constants + assert(!(Result.isConstant() && isa(Result.getConstant())) && + "ConstantInt value must be represented as constantrange"); + return ConstantRange(Width, /*isFullSet=*/true); +} + static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C, LVILatticeVal &Result, const DataLayout &DL, Index: lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- lib/Transforms/Scalar/JumpThreading.cpp +++ lib/Transforms/Scalar/JumpThreading.cpp @@ -25,6 +25,7 @@ #include "llvm/Analysis/Loads.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/ConstantRange.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/LLVMContext.h" @@ -630,6 +631,44 @@ 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 (isa(CmpConst) && + 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 ConstantRange in + // a predecessor, use that information to try to thread this + // block. + ConstantRange CR = LVI->getConstantRangeOnEdge( + CmpIn->getOperand(0), P, BB, CxtI ? CxtI : CmpIn); + // Propagate the range through the addition. + CR = CR.add(ConstantRange(AddC->getValue())); + + // Get the range where the compare returns true. + ConstantRange CmpRange = ConstantRange::makeExactICmpRegion( + Cmp->getPredicate(), cast(CmpConst)->getValue()); + + Constant *ResC; + if (CmpRange.contains(CR)) + ResC = ConstantInt::getTrue(Cmp->getType()); + else if (CmpRange.inverse().contains(CR)) + ResC = ConstantInt::getFalse(Cmp->getType()); + else + continue; + + 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,125 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +;RUN: opt < %s -jump-threading -S | FileCheck %s + + +declare void @bar(...) +declare void @baz(...) + +; Make sure we thread the end of the bar block to the end of the function. +define void @test1(i32 %x) { +; CHECK-LABEL: @test1( +; 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 sgt i32 %x, 9 + 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 + %x.off = add i32 %x, -3 + %0 = icmp ult i32 %x.off, 5 + br i1 %0, label %if.then3, label %if.end4 + +if.then3: ; preds = %if.end + call void (...) @baz() + br label %if.end4 + +if.end4: ; preds = %if.then3, %if.end + ret void +} + +; Make sure we thread the false side of the first if to the end of the function. +define void @test2(i32 %x) { +; CHECK-LABEL: @test2( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 9 +; CHECK-NEXT: br i1 [[CMP]], label [[IF_END:%.*]], label [[IF_END4:%.*]] +; CHECK: if.end: +; CHECK-NEXT: call void (...) @bar() +; 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 slt i32 %x, 9 + 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 + %x.off = add i32 %x, -3 + %0 = icmp ult i32 %x.off, 5 + br i1 %0, label %if.then3, label %if.end4 + +if.then3: ; preds = %if.end + call void (...) @baz() + br label %if.end4 + +if.end4: ; preds = %if.then3, %if.end + ret void +} + +; Negative test to make sure we don't thread when the ranges overlap. +define void @test3(i32 %x) { +; CHECK-LABEL: @test3( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i32 [[X:%.*]], 6 +; CHECK-NEXT: br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]] +; CHECK: if.then: +; CHECK-NEXT: call void (...) @bar() +; CHECK-NEXT: br label [[IF_END]] +; 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 sgt i32 %x, 6 + 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 + %x.off = add i32 %x, -3 + %0 = icmp ult i32 %x.off, 5 + br i1 %0, label %if.then3, label %if.end4 + +if.then3: ; preds = %if.end + call void (...) @baz() + br label %if.end4 + +if.end4: ; preds = %if.then3, %if.end + ret void +} +