Index: llvm/include/llvm/Analysis/LazyValueInfo.h =================================================================== --- llvm/include/llvm/Analysis/LazyValueInfo.h +++ llvm/include/llvm/Analysis/LazyValueInfo.h @@ -74,11 +74,23 @@ 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. + /// to be true or false at the specified instruction Pred is a CmpInst + /// predicate. + /// + /// Because this function does not take a basic block, it generally only looks + /// at assume intrinsics and range metadata. This makes it significantly less + /// powerful than getConstantRange or getPredicateAtBlock. Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI); + /// Like getPredicateAt, tries to determine whether the V C is true. + /// This version evaluates V at the end of BB. + /// + /// This is more powerful than getPredicateAt; it doesn't just look at assume + /// intrinsics and range metadata. + Tristate getPredicateInBlock(unsigned Pred, Value *V, Constant *C, + BasicBlock *BB, Instruction *CxtI = nullptr); + /// Determine whether the specified value is known to be a /// constant at the end of the specified block. Return null if not. Constant *getConstant(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr); Index: llvm/lib/Analysis/LazyValueInfo.cpp =================================================================== --- llvm/lib/Analysis/LazyValueInfo.cpp +++ llvm/lib/Analysis/LazyValueInfo.cpp @@ -1686,14 +1686,13 @@ return getPredicateResult(Pred, C, Result, DL, TLI); } -LazyValueInfo::Tristate -LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C, - Instruction *CxtI) { - // Is or is not NonNull are common predicates being queried. If - // isKnownNonZero can tell us the result of the predicate, we can - // return it quickly. But this is only a fastpath, and falling - // through would still be correct. - const DataLayout &DL = CxtI->getModule()->getDataLayout(); +// If Pred and C are a null or not-null check, quickly checks whether V is known +// null/not-null. +// +// This is a fast approximation, used because these checks are common. +static LazyValueInfo::Tristate fastCheckIsOrIsNotNull(unsigned Pred, Value *V, + Constant *C, + const DataLayout &DL) { if (V->getType()->isPointerTy() && C->isNullValue() && isKnownNonZero(V->stripPointerCasts(), DL)) { if (Pred == ICmpInst::ICMP_EQ) @@ -1701,33 +1700,43 @@ else if (Pred == ICmpInst::ICMP_NE) return LazyValueInfo::True; } - ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI); - Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI); - if (Ret != Unknown) - return Ret; + return LazyValueInfo::Unknown; +} + +// Tries to determine the value of the given predicate by walking the CFG +// backwards. +// +// The approach here is somewhat distinct from the rest of LVI. LVI as a whole +// tries to compute a lattice value which is conservatively correct at a given +// location, but in this case, we have a predicate which we weren't able to +// prove about the merged result, and we're pushing that predicate back along +// each incoming edge to see if we can prove it separately for each input. +// +// As a motivating example, consider: +// +// bb1: +// %v1 = ... ; constantrange<1, 5> +// br label %merge +// bb2: +// %v2 = ... ; constantrange<10, 20> +// br label %merge +// merge: +// %phi = phi [%v1, %v2] ; constantrange<1,20> +// %pred = icmp eq i32 %phi, 8 +// +// We can't tell from the lattice value for '%phi' that '%pred' is false along +// each path, but by checking the predicate over each input separately, we can. +// +// We limit the search to one step backwards from the current BB and value. We +// could consider extending this to search further backwards through the CFG +// and/or value graph, but there are non-obvious compile time vs quality +// tradeoffs. +static LazyValueInfo::Tristate +getPredicateFromEdges(unsigned Pred, Value *V, Constant *C, BasicBlock *BB, + Instruction *CxtI, LazyValueInfo *LVI) { + using Tristate = LazyValueInfo::Tristate; + constexpr auto Unknown = LazyValueInfo::Unknown; - // Note: The following bit of code is somewhat distinct from the rest of LVI; - // LVI as a whole tries to compute a lattice value which is conservatively - // correct at a given location. In this case, we have a predicate which we - // weren't able to prove about the merged result, and we're pushing that - // predicate back along each incoming edge to see if we can prove it - // separately for each input. As a motivating example, consider: - // bb1: - // %v1 = ... ; constantrange<1, 5> - // br label %merge - // bb2: - // %v2 = ... ; constantrange<10, 20> - // br label %merge - // merge: - // %phi = phi [%v1, %v2] ; constantrange<1,20> - // %pred = icmp eq i32 %phi, 8 - // We can't tell from the lattice value for '%phi' that '%pred' is false - // along each path, but by checking the predicate over each input separately, - // we can. - // We limit the search to one step backwards from the current BB and value. - // We could consider extending this to search further backwards through the - // CFG and/or value graph, but there are non-obvious compile time vs quality - // tradeoffs. if (CxtI) { BasicBlock *BB = CxtI->getParent(); @@ -1748,8 +1757,8 @@ Value *Incoming = PHI->getIncomingValue(i); BasicBlock *PredBB = PHI->getIncomingBlock(i); // Note that PredBB may be BB itself. - Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB, - CxtI); + Tristate Result = + LVI->getPredicateOnEdge(Pred, Incoming, C, PredBB, BB, CxtI); // Keep going as long as we've seen a consistent known result for // all inputs. @@ -1770,11 +1779,11 @@ // For predecessor edge, determine if the comparison is true or false // on that edge. If they're all true or all false, we can conclude // the value of the comparison in this block. - Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI); + Tristate Baseline = LVI->getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI); if (Baseline != Unknown) { // Check that all remaining incoming values match the first one. while (++PI != PE) { - Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI); + Tristate Ret = LVI->getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI); if (Ret != Baseline) break; } // If we terminated early, then one of the values didn't match. @@ -1787,6 +1796,39 @@ return Unknown; } +LazyValueInfo::Tristate LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, + Constant *C, + Instruction *CxtI) { + const DataLayout &DL = CxtI->getModule()->getDataLayout(); + Tristate Ret = fastCheckIsOrIsNotNull(Pred, V, C, DL); + if (Ret != Unknown) + return Ret; + + Ret = getPredicateResult( + Pred, C, getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI), DL, TLI); + if (Ret != Unknown) + return Ret; + + return getPredicateFromEdges(Pred, V, C, /*BB=*/nullptr, CxtI, this); +} + +LazyValueInfo::Tristate +LazyValueInfo::getPredicateInBlock(unsigned Pred, Value *V, Constant *C, + BasicBlock *BB, Instruction *CxtI) { + const DataLayout &DL = CxtI->getModule()->getDataLayout(); + Tristate Ret = fastCheckIsOrIsNotNull(Pred, V, C, DL); + if (Ret != Unknown) + return Ret; + + Ret = getPredicateResult( + Pred, C, getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI), DL, + TLI); + if (Ret != Unknown) + return Ret; + + return getPredicateFromEdges(Pred, V, C, /*BB=*/nullptr, CxtI, this); +} + void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc) { if (PImpl) { Index: llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp =================================================================== --- llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -226,7 +226,7 @@ return false; LazyValueInfo::Tristate Result = - LVI->getPredicateAt(C->getPredicate(), Op0, Op1, C); + LVI->getPredicateInBlock(C->getPredicate(), Op0, Op1, C->getParent(), C); if (Result == LazyValueInfo::Unknown) return false; ++NumCmps; @@ -401,10 +401,10 @@ // relatively expensive analysis for constants which are obviously either // null or non-null to start with. if (Type && !CS.paramHasAttr(ArgNo, Attribute::NonNull) && - !isa(V) && - LVI->getPredicateAt(ICmpInst::ICMP_EQ, V, - ConstantPointerNull::get(Type), - CS.getInstruction()) == LazyValueInfo::False) + !isa(V) && + LVI->getPredicateInBlock(ICmpInst::ICMP_EQ, V, + ConstantPointerNull::get(Type), CS.getParent(), + CS.getInstruction()) == LazyValueInfo::False) ArgNos.push_back(ArgNo); ArgNo++; } @@ -426,7 +426,8 @@ static bool hasPositiveOperands(BinaryOperator *SDI, LazyValueInfo *LVI) { Constant *Zero = ConstantInt::get(SDI->getType(), 0); for (Value *O : SDI->operands()) { - auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, O, Zero, SDI); + auto Result = LVI->getPredicateInBlock(ICmpInst::ICMP_SGE, O, Zero, + SDI->getParent(), SDI); if (Result != LazyValueInfo::True) return false; } @@ -518,8 +519,8 @@ return false; Constant *Zero = ConstantInt::get(SDI->getType(), 0); - if (LVI->getPredicateAt(ICmpInst::ICMP_SGE, SDI->getOperand(0), Zero, SDI) != - LazyValueInfo::True) + if (LVI->getPredicateInBlock(ICmpInst::ICMP_SGE, SDI->getOperand(0), Zero, + SDI->getParent(), SDI) != LazyValueInfo::True) return false; ++NumAShrs; @@ -598,9 +599,9 @@ Value *Op0 = C->getOperand(0); Constant *Op1 = dyn_cast(C->getOperand(1)); if (!Op1) return nullptr; - - LazyValueInfo::Tristate Result = - LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At); + + LazyValueInfo::Tristate Result = LVI->getPredicateInBlock( + C->getPredicate(), Op0, Op1, At->getParent(), At); if (Result == LazyValueInfo::Unknown) return nullptr; Index: llvm/test/Transforms/CorrelatedValuePropagation/ashr.ll =================================================================== --- llvm/test/Transforms/CorrelatedValuePropagation/ashr.ll +++ llvm/test/Transforms/CorrelatedValuePropagation/ashr.ll @@ -97,3 +97,11 @@ exit: ret void } + +; CHECK-LABEL: @mask +define void @mask(i8 %n) { + %m = and i8 %n, 31 +; CHECK: lshr i8 %m, 1 + %shr = ashr i8 %m, 1 + ret void +} Index: llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll =================================================================== --- llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll +++ llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll @@ -61,4 +61,12 @@ unreachable } +; CHECK-LABEL: @mask +define i1 @mask(i8 %val) { + %v = and i8 %val, 31 + %pred = icmp sle i8 %v, 31 +; CHECK: ret i1 true + ret i1 %pred +} + attributes #4 = { noreturn } Index: llvm/test/Transforms/CorrelatedValuePropagation/non-null.ll =================================================================== --- llvm/test/Transforms/CorrelatedValuePropagation/non-null.ll +++ llvm/test/Transforms/CorrelatedValuePropagation/non-null.ll @@ -161,3 +161,14 @@ ; CHECK: call void @test12_helper(i8* nonnull %merged_arg) ret void } + +declare void @test_bittwiddle_helper(i8* %arg) +define void @test_bittwiddle(i8* %arg) { +; CHECK-LABEL: @test_bittwiddle + %raw_ptr = ptrtoint i8* %arg to i64 + %twiddled = or i64 %raw_ptr, 1 + %twiddled_ptr = inttoptr i64 %twiddled to i8* +; CHECK: call void @test_bittwiddle_helper(i8* nonnull %twiddled_ptr) + call void @test_bittwiddle_helper(i8* %twiddled_ptr) + ret void +} Index: llvm/test/Transforms/CorrelatedValuePropagation/sdiv.ll =================================================================== --- llvm/test/Transforms/CorrelatedValuePropagation/sdiv.ll +++ llvm/test/Transforms/CorrelatedValuePropagation/sdiv.ll @@ -95,3 +95,11 @@ exit: ret void } + +; CHECK-LABEL: @mask +define void @mask(i8 %n) { + %m = and i8 %n, 31 +; CHECK: udiv i8 %m, 42 + %div = sdiv i8 %m, 42 + ret void +} Index: llvm/test/Transforms/CorrelatedValuePropagation/srem.ll =================================================================== --- llvm/test/Transforms/CorrelatedValuePropagation/srem.ll +++ llvm/test/Transforms/CorrelatedValuePropagation/srem.ll @@ -42,3 +42,11 @@ exit: ret void } + +; CHECK-LABEL: @mask +define void @mask(i8 %n) { + %m = and i8 %n, 31 +; CHECK: urem i8 %m, 42 + %rem = srem i8 %m, 42 + ret void +}