diff --git a/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp b/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp --- a/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp +++ b/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp @@ -79,6 +79,7 @@ #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" +#include "llvm/IR/PatternMatch.h" #include "llvm/IR/Type.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" @@ -106,6 +107,9 @@ STATISTIC(NumMemSet, "Number of memset's formed from loop stores"); STATISTIC(NumMemCpy, "Number of memcpy's formed from loop load+stores"); +STATISTIC( + NumShiftUntilBitTest, + "Number of uncountable loops recognized as 'shift until bitttest' idiom"); bool DisableLIRP::All; static cl::opt @@ -227,6 +231,8 @@ const DebugLoc &DL, bool ZeroCheck, bool IsCntPhiUsedOutsideLoop); + bool recognizeShiftUntilBitTest(); + /// @} }; @@ -1228,7 +1234,8 @@ << "] Noncountable Loop %" << CurLoop->getHeader()->getName() << "\n"); - return recognizePopcount() || recognizeAndInsertFFS(); + return recognizePopcount() || recognizeAndInsertFFS() || + recognizeShiftUntilBitTest(); } /// Check if the given conditional branch is based on the comparison between @@ -1904,3 +1911,326 @@ // loop. The loop would otherwise not be deleted even if it becomes empty. SE->forgetLoop(CurLoop); } + +/// Match loop-invariant value. +template struct match_LoopInvariant { + SubPattern_t SubPattern; + const Loop *L; + + match_LoopInvariant(const SubPattern_t &SP, const Loop *L) + : SubPattern(SP), L(L) {} + + template bool match(ITy *V) { + return L->isLoopInvariant(V) && SubPattern.match(V); + } +}; + +/// Matches if the value is loop-invariant. +template +inline match_LoopInvariant m_LoopInvariant(const Ty &M, const Loop *L) { + return match_LoopInvariant(M, L); +} + +/// Match PHI incoming block/value pair +template +struct match_Incoming { + BlockSubPattern_t BlockSubPattern; + ValueSubPattern_t ValueSubPattern; + + match_Incoming(BlockSubPattern_t BSP, ValueSubPattern_t VSP) + : BlockSubPattern(BSP), ValueSubPattern(VSP) {} + + template bool match(ITy *V, int IncomingIdx) { + auto *PHI = dyn_cast(V); + if (!PHI) + return false; + return BlockSubPattern.match(PHI->getIncomingBlock(IncomingIdx)) && + ValueSubPattern.match(PHI->getIncomingValue(IncomingIdx)); + } +}; + +/// Matches if the PHI node has the following incoming block/value pair. +template +inline match_Incoming m_Incoming(const BTy &BM, const VTy &VM) { + return match_Incoming(BM, VM); +} + +/// Match PHI node. +/// FIXME: generalize to the variadic number of incomings. +template +struct match_PHI { + FirstIncomingTy FirstSubPattern; + SecondIncomingTy SecondSubPattern; + + match_PHI(FirstIncomingTy FirstSubPattern, SecondIncomingTy SecondSubPattern) + : FirstSubPattern(FirstSubPattern), SecondSubPattern(SecondSubPattern) {} + + template bool match(ITy *V) { + auto *PHI = dyn_cast(V); + if (!PHI || PHI->getNumOperands() != 2) + return false; + return (FirstSubPattern.match(PHI, 0) && SecondSubPattern.match(PHI, 1)) || + (FirstSubPattern.match(PHI, 1) && SecondSubPattern.match(PHI, 0)); + } +}; + +/// Matches if the value is a PHI. +template +inline match_PHI +m_PHI(FirstIncomingTy FirstSubPattern, SecondIncomingTy SecondSubPattern) { + return match_PHI(FirstSubPattern, + SecondSubPattern); +} + +/// Return true if the idiom is detected in the loop. +/// +/// The core idiom we are trying to detect is: +/// \code +/// entry: +/// <...> +/// %bitmask = shl i32 1, %bitpos +/// br label %loop +/// +/// loop: +/// %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] +/// %x.curr.bitmasked = and i32 %x.curr, %bitmask +/// %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 +/// %x.next = shl i32 %x.curr, 1 +/// br i1 %x.curr.isbitunset, label %loop, label %end +/// +/// end: +/// %x.res = phi i32 [ %x.curr, %loop ] <...> +/// <...> +/// \endcode +static bool detectShiftUntilBitTestIdiom(Loop *CurLoop, Value *&BaseX, + Value *&BitMask, Value *&BitPos, + Value *&CurrX) { + LLVM_DEBUG(dbgs() << DEBUG_TYPE + " Performing shift-until-bittest idiom detection.\n"); + + // Give up if the loop has multiple blocks or multiple backedges. + if (CurLoop->getNumBlocks() != 1 || CurLoop->getNumBackEdges() != 1) { + LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad block/backedge count.\n"); + return false; + } + + BasicBlock *LoopHeaderBB = CurLoop->getHeader(); + BasicBlock *LoopPreheaderBB = CurLoop->getLoopPreheader(); + assert(LoopPreheaderBB && "There is always a loop preheader."); + + using namespace PatternMatch; + + // Step 1: Check if the loop backedge is in desirable form. + + ICmpInst::Predicate Pred; + Value *CmpLHS, *CmpRHS; + BasicBlock *TrueBB, *FalseBB; + if (!match(LoopHeaderBB->getTerminator(), + m_Br(m_ICmp(Pred, m_Value(CmpLHS), m_Value(CmpRHS)), + m_BasicBlock(TrueBB), m_BasicBlock(FalseBB)))) { + LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad backedge structure.\n"); + return false; + } + + Value *Rec; + + // Step 2: Check if the backedge's condition is in desirable form. + + auto MatchVariableBitMask = [&]() { + return ICmpInst::isEquality(Pred) && match(CmpRHS, m_Zero()) && + match(CmpLHS, + m_c_And(m_Value(Rec), + m_CombineAnd( + m_Value(BitMask), + m_LoopInvariant(m_Shl(m_One(), m_Value(BitPos)), + CurLoop)))); + }; + + if (!MatchVariableBitMask()) { + // FIXME: support constant bit mask. + // FIXME: support sign bit test (use llvm::decomposeBitTestICmp()). + LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad backedge comparison.\n"); + return false; + } + + // Step 3: Check if the recurrence is in desirable form. + if (!match(Rec, m_CombineAnd( + m_Value(CurrX), + m_PHI(m_Incoming(m_SpecificBB(LoopPreheaderBB), + m_Value(BaseX)), + m_Incoming(m_SpecificBB(LoopHeaderBB), + m_Shl(m_Deferred(CurrX), m_One())))))) { + // FIXME: support right-shift? + LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad recurrence.\n"); + return false; + } + + // Step 4: Check if the backedge's destinations are in desirable form. + + assert(ICmpInst::isEquality(Pred) && + "Should only get equality predicates here."); + + // cmp-br is commutative, so canonicalize to a single variant. + if (Pred != ICmpInst::Predicate::ICMP_EQ) { + Pred = ICmpInst::getInversePredicate(Pred); + std::swap(TrueBB, FalseBB); + } + + // We expect to exit loop when comparison yields false, + // so when it yields true we should branch back to loop header. + if (TrueBB != LoopHeaderBB) { + LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad backedge flow.\n"); + return false; + } + + // Okay, idiom checks out. + return true; +} + +/// Look for the following loop: +/// \code +/// entry: +/// <...> +/// %bitmask = shl i32 1, %bitpos +/// br label %loop +/// +/// loop: +/// %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] +/// %x.curr.bitmasked = and i32 %x.curr, %bitmask +/// %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 +/// %x.next = shl i32 %x.curr, 1 +/// br i1 %x.curr.isbitunset, label %loop, label %end +/// +/// end: +/// %x.res = phi i32 [ %x.curr, %loop ] <...> +/// <...> +/// \endcode +/// +/// And transform it into: +/// \code +/// entry: +/// %bitmask = shl i32 1, %bitpos +/// %lowbitmask = add i32 %bitmask, -1 +/// %mask = or i32 %lowbitmask, %bitmask +/// %x.masked = and i32 %x, %mask +/// %x.masked.numleadingzeros = call i32 @llvm.ctlz.i32(i32 %x.masked, +/// i1 true) +/// %x.masked.numactivebits = sub i32 32, %x.masked.numleadingzeros +/// %x.masked.leadingonepos = sub i32 %x.masked.numactivebits, 1 +/// %shamt = sub i32 %bitpos, %x.masked.leadingonepos +/// %x.curr = shl i32 %x, %shamt +/// br label %end +/// +/// end: +/// %x.res = phi i32 [ %x.curr, %loop ] <...> +/// <...> +/// \endcode +bool LoopIdiomRecognize::recognizeShiftUntilBitTest() { + bool MadeChange = false; + + Value *X, *BitMask, *BitPos, *XCurr; + if (!detectShiftUntilBitTestIdiom(CurLoop, X, BitMask, BitPos, XCurr)) { + LLVM_DEBUG(dbgs() << DEBUG_TYPE + " shift-until-bittest idiom detection failed.\n"); + return MadeChange; + } + LLVM_DEBUG(dbgs() << DEBUG_TYPE " shift-until-bittest idiom detected!\n"); + + // Ok, it is the idiom we were looking for, we *could* transform this loop, + // but is it profitable to transform? + + BasicBlock *LoopHeaderBB = CurLoop->getHeader(); + BasicBlock *LoopPreheaderBB = CurLoop->getLoopPreheader(); + assert(LoopPreheaderBB && "There is always a loop preheader."); + + BasicBlock *SuccessorBB = CurLoop->getExitBlock(); + assert(LoopPreheaderBB && "There is only a single successor."); + + // The loop must not have any other instructions other than the idiom itself. + // FIXME: we could just rewrite the loop with countable trip count. + size_t HeaderSize = LoopHeaderBB->sizeWithoutDebug(); + constexpr size_t CanonicalHeaderSize = 5; + assert(HeaderSize >= CanonicalHeaderSize); + if (HeaderSize > CanonicalHeaderSize) { + LLVM_DEBUG(dbgs() << DEBUG_TYPE " Won't be able to delete loop!\n"); + return MadeChange; + } + + // Only the recurrence itself is allowed to have uses outside of the loop. + if (any_of(SuccessorBB->phis(), [&](PHINode &PN) { + Value *IV = PN.getIncomingValueForBlock(LoopHeaderBB); + return IV != XCurr && !CurLoop->isLoopInvariant(IV); + })) { + LLVM_DEBUG(dbgs() << DEBUG_TYPE " In-loop value is live-out!\n"); + return MadeChange; + } + // FIXME: we *could* allow this. + + IRBuilder<> Builder(LoopPreheaderBB->getTerminator()); + Builder.SetCurrentDebugLocation(cast(XCurr)->getDebugLoc()); + + Intrinsic::ID IntrID = Intrinsic::ctlz; + Type *Ty = X->getType(); + + // Also, the intrinsic we'll use must be cheap. + IntrinsicCostAttributes Attrs( + IntrID, Ty, {UndefValue::get(Ty), /*is_zero_undef=*/Builder.getTrue()}); + int Cost = TTI->getIntrinsicInstrCost( + Attrs, TargetTransformInfo::TCK_SizeAndLatency); + if (Cost > TargetTransformInfo::TCC_Basic) { + LLVM_DEBUG(dbgs() << DEBUG_TYPE + " Intrinsic is too costly, not beneficial\n"); + return MadeChange; + } + + // Ok, transform appears worthwhile. + MadeChange = true; + + // Step 1: Compute the loop trip count. + + Value *LowBitMask = + Builder.CreateAdd(BitMask, Constant::getAllOnesValue(BitMask->getType()), + BitPos->getName() + ".lowbitmask"); + Value *Mask = + Builder.CreateOr(LowBitMask, BitMask, BitPos->getName() + ".mask"); + Value *XMasked = Builder.CreateAnd(X, Mask, X->getName() + ".masked"); + CallInst *XMaskedNumLeadingZeros = Builder.CreateIntrinsic( + IntrID, Ty, {XMasked, /*is_zero_undef=*/Builder.getTrue()}, + /*FMFSource=*/nullptr, XMasked->getName() + ".numleadingzeros"); + Value *XMaskedNumActiveBits = Builder.CreateSub( + ConstantInt::get(X->getType(), X->getType()->getScalarSizeInBits()), + XMaskedNumLeadingZeros, XMasked->getName() + ".numactivebits"); + Value *XMaskedLeadingOnePos = Builder.CreateAdd( + XMaskedNumActiveBits, Constant::getAllOnesValue(BitMask->getType()), + XMasked->getName() + ".numleadingonepos"); + Value *LoopTripCount = Builder.CreateSub( + BitPos, XMaskedLeadingOnePos, XMasked->getName() + ".looptripcount"); + + // Step 2: Compute the recurrence's final value without a loop. + + Value *NewX = Builder.CreateShl(X, LoopTripCount); + NewX->takeName(XCurr); + + // Step 3: Replace all references to the recurrence with + // computed recurrence's final value. + + XCurr->replaceAllUsesWith(NewX); + + // Step 4: Fix the loop back-edge to always exit upon first iteration. + + Builder.SetInsertPoint(LoopHeaderBB->getTerminator()); + Builder.CreateCondBr(Builder.getTrue(), SuccessorBB, LoopHeaderBB); + LoopHeaderBB->getTerminator()->eraseFromParent(); + + // Step 5: Forget the "non-computable" trip-count SCEV associated with the + // loop. The loop would otherwise not be deleted even if it becomes empty. + + SE->forgetLoop(CurLoop); + + // Other passes will take care of actually deleting the loop. + + LLVM_DEBUG(dbgs() << DEBUG_TYPE " shift-until-bittest idiom optimized!\n"); + + ++NumShiftUntilBitTest; + return MadeChange; +} diff --git a/llvm/test/Transforms/LoopIdiom/X86/left-shift-until-bittest.ll b/llvm/test/Transforms/LoopIdiom/X86/left-shift-until-bittest.ll --- a/llvm/test/Transforms/LoopIdiom/X86/left-shift-until-bittest.ll +++ b/llvm/test/Transforms/LoopIdiom/X86/left-shift-until-bittest.ll @@ -15,25 +15,53 @@ ; Most basic example. define i32 @p0_i32(i32 %x, i32 %bit) { -; ALL-LABEL: @p0_i32( -; ALL-NEXT: entry: -; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG16:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META9:metadata !.*]], metadata !DIExpression()), [[DBG16]] -; ALL-NEXT: br label [[LOOP:%.*]], [[DBG17:!dbg !.*]] -; ALL: loop: -; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG18:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META11:metadata !.*]], metadata !DIExpression()), [[DBG18]] -; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG19:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META12:metadata !.*]], metadata !DIExpression()), [[DBG19]] -; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG20:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META13:metadata !.*]], metadata !DIExpression()), [[DBG20]] -; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG21:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META15:metadata !.*]], metadata !DIExpression()), [[DBG21]] -; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG22:!dbg !.*]] -; ALL: end: -; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG18]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META11]], metadata !DIExpression()), [[DBG18]] -; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG23:!dbg !.*]] +; LZCNT-LABEL: @p0_i32( +; LZCNT-NEXT: entry: +; LZCNT-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG16:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META9:metadata !.*]], metadata !DIExpression()), [[DBG16]] +; LZCNT-NEXT: [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG17:!dbg !.*]] +; LZCNT-NEXT: [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG17]] +; LZCNT-NEXT: [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG17]] +; LZCNT-NEXT: [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG17]] +; LZCNT-NEXT: [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG17]] +; LZCNT-NEXT: [[X_MASKED_NUMLEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG17]] +; LZCNT-NEXT: [[X_MASKED_LOOPTRIPCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_NUMLEADINGONEPOS]], [[DBG17]] +; LZCNT-NEXT: [[X_CURR:%.*]] = shl i32 [[X]], [[X_MASKED_LOOPTRIPCOUNT]], [[DBG17]] +; LZCNT-NEXT: br label [[LOOP:%.*]], [[DBG18:!dbg !.*]] +; LZCNT: loop: +; LZCNT-NEXT: [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG17]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META11:metadata !.*]], metadata !DIExpression()), [[DBG17]] +; LZCNT-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG19:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META12:metadata !.*]], metadata !DIExpression()), [[DBG19]] +; LZCNT-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG20:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META13:metadata !.*]], metadata !DIExpression()), [[DBG20]] +; LZCNT-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG21:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META15:metadata !.*]], metadata !DIExpression()), [[DBG21]] +; LZCNT-NEXT: br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG22:!dbg !.*]] +; LZCNT: end: +; LZCNT-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG17]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META11]], metadata !DIExpression()), [[DBG17]] +; LZCNT-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG23:!dbg !.*]] +; +; NOLZCNT-LABEL: @p0_i32( +; NOLZCNT-NEXT: entry: +; NOLZCNT-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG16:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META9:metadata !.*]], metadata !DIExpression()), [[DBG16]] +; NOLZCNT-NEXT: br label [[LOOP:%.*]], [[DBG17:!dbg !.*]] +; NOLZCNT: loop: +; NOLZCNT-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG18:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META11:metadata !.*]], metadata !DIExpression()), [[DBG18]] +; NOLZCNT-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG19:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META12:metadata !.*]], metadata !DIExpression()), [[DBG19]] +; NOLZCNT-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG20:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META13:metadata !.*]], metadata !DIExpression()), [[DBG20]] +; NOLZCNT-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG21:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META15:metadata !.*]], metadata !DIExpression()), [[DBG21]] +; NOLZCNT-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG22:!dbg !.*]] +; NOLZCNT: end: +; NOLZCNT-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG18]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META11]], metadata !DIExpression()), [[DBG18]] +; NOLZCNT-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG23:!dbg !.*]] ; entry: %bitmask = shl i32 1, %bit @@ -52,25 +80,53 @@ ; Same, but in some other bit width. define i16 @p1_i16(i16 %x, i16 %bit) { -; ALL-LABEL: @p1_i16( -; ALL-NEXT: entry: -; ALL-NEXT: [[BITMASK:%.*]] = shl i16 1, [[BIT:%.*]], [[DBG32:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i16 [[BITMASK]], [[META26:metadata !.*]], metadata !DIExpression()), [[DBG32]] -; ALL-NEXT: br label [[LOOP:%.*]], [[DBG33:!dbg !.*]] -; ALL: loop: -; ALL-NEXT: [[X_CURR:%.*]] = phi i16 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG34:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i16 [[X_CURR]], [[META28:metadata !.*]], metadata !DIExpression()), [[DBG34]] -; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i16 [[X_CURR]], [[BITMASK]], [[DBG35:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i16 [[X_CURR_BITMASKED]], [[META29:metadata !.*]], metadata !DIExpression()), [[DBG35]] -; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i16 [[X_CURR_BITMASKED]], 0, [[DBG36:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META30:metadata !.*]], metadata !DIExpression()), [[DBG36]] -; ALL-NEXT: [[X_NEXT]] = shl i16 [[X_CURR]], 1, [[DBG37:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i16 [[X_NEXT]], [[META31:metadata !.*]], metadata !DIExpression()), [[DBG37]] -; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG38:!dbg !.*]] -; ALL: end: -; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i16 [ [[X_CURR]], [[LOOP]] ], [[DBG34]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i16 [[X_CURR_LCSSA]], [[META28]], metadata !DIExpression()), [[DBG34]] -; ALL-NEXT: ret i16 [[X_CURR_LCSSA]], [[DBG39:!dbg !.*]] +; LZCNT-LABEL: @p1_i16( +; LZCNT-NEXT: entry: +; LZCNT-NEXT: [[BITMASK:%.*]] = shl i16 1, [[BIT:%.*]], [[DBG32:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i16 [[BITMASK]], [[META26:metadata !.*]], metadata !DIExpression()), [[DBG32]] +; LZCNT-NEXT: [[BIT_LOWBITMASK:%.*]] = add i16 [[BITMASK]], -1, [[DBG33:!dbg !.*]] +; LZCNT-NEXT: [[BIT_MASK:%.*]] = or i16 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG33]] +; LZCNT-NEXT: [[X_MASKED:%.*]] = and i16 [[X:%.*]], [[BIT_MASK]], [[DBG33]] +; LZCNT-NEXT: [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i16 @llvm.ctlz.i16(i16 [[X_MASKED]], i1 true), [[DBG33]] +; LZCNT-NEXT: [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i16 16, [[X_MASKED_NUMLEADINGZEROS]], [[DBG33]] +; LZCNT-NEXT: [[X_MASKED_NUMLEADINGONEPOS:%.*]] = add i16 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG33]] +; LZCNT-NEXT: [[X_MASKED_LOOPTRIPCOUNT:%.*]] = sub i16 [[BIT]], [[X_MASKED_NUMLEADINGONEPOS]], [[DBG33]] +; LZCNT-NEXT: [[X_CURR:%.*]] = shl i16 [[X]], [[X_MASKED_LOOPTRIPCOUNT]], [[DBG33]] +; LZCNT-NEXT: br label [[LOOP:%.*]], [[DBG34:!dbg !.*]] +; LZCNT: loop: +; LZCNT-NEXT: [[TMP0:%.*]] = phi i16 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG33]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i16 [[X_CURR]], [[META28:metadata !.*]], metadata !DIExpression()), [[DBG33]] +; LZCNT-NEXT: [[X_CURR_BITMASKED:%.*]] = and i16 [[X_CURR]], [[BITMASK]], [[DBG35:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i16 [[X_CURR_BITMASKED]], [[META29:metadata !.*]], metadata !DIExpression()), [[DBG35]] +; LZCNT-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i16 [[X_CURR_BITMASKED]], 0, [[DBG36:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META30:metadata !.*]], metadata !DIExpression()), [[DBG36]] +; LZCNT-NEXT: [[X_NEXT]] = shl i16 [[X_CURR]], 1, [[DBG37:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i16 [[X_NEXT]], [[META31:metadata !.*]], metadata !DIExpression()), [[DBG37]] +; LZCNT-NEXT: br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG38:!dbg !.*]] +; LZCNT: end: +; LZCNT-NEXT: [[X_CURR_LCSSA:%.*]] = phi i16 [ [[X_CURR]], [[LOOP]] ], [[DBG33]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i16 [[X_CURR_LCSSA]], [[META28]], metadata !DIExpression()), [[DBG33]] +; LZCNT-NEXT: ret i16 [[X_CURR_LCSSA]], [[DBG39:!dbg !.*]] +; +; NOLZCNT-LABEL: @p1_i16( +; NOLZCNT-NEXT: entry: +; NOLZCNT-NEXT: [[BITMASK:%.*]] = shl i16 1, [[BIT:%.*]], [[DBG32:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i16 [[BITMASK]], [[META26:metadata !.*]], metadata !DIExpression()), [[DBG32]] +; NOLZCNT-NEXT: br label [[LOOP:%.*]], [[DBG33:!dbg !.*]] +; NOLZCNT: loop: +; NOLZCNT-NEXT: [[X_CURR:%.*]] = phi i16 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG34:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i16 [[X_CURR]], [[META28:metadata !.*]], metadata !DIExpression()), [[DBG34]] +; NOLZCNT-NEXT: [[X_CURR_BITMASKED:%.*]] = and i16 [[X_CURR]], [[BITMASK]], [[DBG35:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i16 [[X_CURR_BITMASKED]], [[META29:metadata !.*]], metadata !DIExpression()), [[DBG35]] +; NOLZCNT-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i16 [[X_CURR_BITMASKED]], 0, [[DBG36:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META30:metadata !.*]], metadata !DIExpression()), [[DBG36]] +; NOLZCNT-NEXT: [[X_NEXT]] = shl i16 [[X_CURR]], 1, [[DBG37:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i16 [[X_NEXT]], [[META31:metadata !.*]], metadata !DIExpression()), [[DBG37]] +; NOLZCNT-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG38:!dbg !.*]] +; NOLZCNT: end: +; NOLZCNT-NEXT: [[X_CURR_LCSSA:%.*]] = phi i16 [ [[X_CURR]], [[LOOP]] ], [[DBG34]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i16 [[X_CURR_LCSSA]], [[META28]], metadata !DIExpression()), [[DBG34]] +; NOLZCNT-NEXT: ret i16 [[X_CURR_LCSSA]], [[DBG39:!dbg !.*]] ; entry: %bitmask = shl i16 1, %bit @@ -218,25 +274,53 @@ ; Check that loop backedge's cmp-br order is correctly handled define i32 @p6(i32 %x, i32 %bit) { -; ALL-LABEL: @p6( -; ALL-NEXT: entry: -; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG97:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META92:metadata !.*]], metadata !DIExpression()), [[DBG97]] -; ALL-NEXT: br label [[LOOP:%.*]], [[DBG98:!dbg !.*]] -; ALL: loop: -; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG99:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META93:metadata !.*]], metadata !DIExpression()), [[DBG99]] -; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG100:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META94:metadata !.*]], metadata !DIExpression()), [[DBG100]] -; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp ne i32 [[X_CURR_BITMASKED]], 0, [[DBG101:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META95:metadata !.*]], metadata !DIExpression()), [[DBG101]] -; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG102:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META96:metadata !.*]], metadata !DIExpression()), [[DBG102]] -; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[END:%.*]], label [[LOOP]], [[DBG103:!dbg !.*]] -; ALL: end: -; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG99]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META93]], metadata !DIExpression()), [[DBG99]] -; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG104:!dbg !.*]] +; LZCNT-LABEL: @p6( +; LZCNT-NEXT: entry: +; LZCNT-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG97:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META92:metadata !.*]], metadata !DIExpression()), [[DBG97]] +; LZCNT-NEXT: [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG98:!dbg !.*]] +; LZCNT-NEXT: [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG98]] +; LZCNT-NEXT: [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG98]] +; LZCNT-NEXT: [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG98]] +; LZCNT-NEXT: [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG98]] +; LZCNT-NEXT: [[X_MASKED_NUMLEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG98]] +; LZCNT-NEXT: [[X_MASKED_LOOPTRIPCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_NUMLEADINGONEPOS]], [[DBG98]] +; LZCNT-NEXT: [[X_CURR:%.*]] = shl i32 [[X]], [[X_MASKED_LOOPTRIPCOUNT]], [[DBG98]] +; LZCNT-NEXT: br label [[LOOP:%.*]], [[DBG99:!dbg !.*]] +; LZCNT: loop: +; LZCNT-NEXT: [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG98]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META93:metadata !.*]], metadata !DIExpression()), [[DBG98]] +; LZCNT-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG100:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META94:metadata !.*]], metadata !DIExpression()), [[DBG100]] +; LZCNT-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp ne i32 [[X_CURR_BITMASKED]], 0, [[DBG101:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META95:metadata !.*]], metadata !DIExpression()), [[DBG101]] +; LZCNT-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG102:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META96:metadata !.*]], metadata !DIExpression()), [[DBG102]] +; LZCNT-NEXT: br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG103:!dbg !.*]] +; LZCNT: end: +; LZCNT-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG98]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META93]], metadata !DIExpression()), [[DBG98]] +; LZCNT-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG104:!dbg !.*]] +; +; NOLZCNT-LABEL: @p6( +; NOLZCNT-NEXT: entry: +; NOLZCNT-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG97:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META92:metadata !.*]], metadata !DIExpression()), [[DBG97]] +; NOLZCNT-NEXT: br label [[LOOP:%.*]], [[DBG98:!dbg !.*]] +; NOLZCNT: loop: +; NOLZCNT-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG99:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META93:metadata !.*]], metadata !DIExpression()), [[DBG99]] +; NOLZCNT-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG100:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META94:metadata !.*]], metadata !DIExpression()), [[DBG100]] +; NOLZCNT-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp ne i32 [[X_CURR_BITMASKED]], 0, [[DBG101:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META95:metadata !.*]], metadata !DIExpression()), [[DBG101]] +; NOLZCNT-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG102:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META96:metadata !.*]], metadata !DIExpression()), [[DBG102]] +; NOLZCNT-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[END:%.*]], label [[LOOP]], [[DBG103:!dbg !.*]] +; NOLZCNT: end: +; NOLZCNT-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG99]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META93]], metadata !DIExpression()), [[DBG99]] +; NOLZCNT-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG104:!dbg !.*]] ; entry: %bitmask = shl i32 1, %bit @@ -255,25 +339,53 @@ ; `and` is commutative, so ensure that order is irrelevant define i32 @p7(i32 %x, i32 %bit) { -; ALL-LABEL: @p7( -; ALL-NEXT: entry: -; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG112:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META107:metadata !.*]], metadata !DIExpression()), [[DBG112]] -; ALL-NEXT: br label [[LOOP:%.*]], [[DBG113:!dbg !.*]] -; ALL: loop: -; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG114:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META108:metadata !.*]], metadata !DIExpression()), [[DBG114]] -; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[BITMASK]], [[X_CURR]], [[DBG115:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META109:metadata !.*]], metadata !DIExpression()), [[DBG115]] -; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG116:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META110:metadata !.*]], metadata !DIExpression()), [[DBG116]] -; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG117:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META111:metadata !.*]], metadata !DIExpression()), [[DBG117]] -; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG118:!dbg !.*]] -; ALL: end: -; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG114]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META108]], metadata !DIExpression()), [[DBG114]] -; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG119:!dbg !.*]] +; LZCNT-LABEL: @p7( +; LZCNT-NEXT: entry: +; LZCNT-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG112:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META107:metadata !.*]], metadata !DIExpression()), [[DBG112]] +; LZCNT-NEXT: [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG113:!dbg !.*]] +; LZCNT-NEXT: [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG113]] +; LZCNT-NEXT: [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG113]] +; LZCNT-NEXT: [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG113]] +; LZCNT-NEXT: [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG113]] +; LZCNT-NEXT: [[X_MASKED_NUMLEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG113]] +; LZCNT-NEXT: [[X_MASKED_LOOPTRIPCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_NUMLEADINGONEPOS]], [[DBG113]] +; LZCNT-NEXT: [[X_CURR:%.*]] = shl i32 [[X]], [[X_MASKED_LOOPTRIPCOUNT]], [[DBG113]] +; LZCNT-NEXT: br label [[LOOP:%.*]], [[DBG114:!dbg !.*]] +; LZCNT: loop: +; LZCNT-NEXT: [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG113]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META108:metadata !.*]], metadata !DIExpression()), [[DBG113]] +; LZCNT-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[BITMASK]], [[X_CURR]], [[DBG115:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META109:metadata !.*]], metadata !DIExpression()), [[DBG115]] +; LZCNT-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG116:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META110:metadata !.*]], metadata !DIExpression()), [[DBG116]] +; LZCNT-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG117:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META111:metadata !.*]], metadata !DIExpression()), [[DBG117]] +; LZCNT-NEXT: br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG118:!dbg !.*]] +; LZCNT: end: +; LZCNT-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG113]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META108]], metadata !DIExpression()), [[DBG113]] +; LZCNT-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG119:!dbg !.*]] +; +; NOLZCNT-LABEL: @p7( +; NOLZCNT-NEXT: entry: +; NOLZCNT-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG112:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META107:metadata !.*]], metadata !DIExpression()), [[DBG112]] +; NOLZCNT-NEXT: br label [[LOOP:%.*]], [[DBG113:!dbg !.*]] +; NOLZCNT: loop: +; NOLZCNT-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG114:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META108:metadata !.*]], metadata !DIExpression()), [[DBG114]] +; NOLZCNT-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[BITMASK]], [[X_CURR]], [[DBG115:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META109:metadata !.*]], metadata !DIExpression()), [[DBG115]] +; NOLZCNT-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG116:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META110:metadata !.*]], metadata !DIExpression()), [[DBG116]] +; NOLZCNT-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG117:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META111:metadata !.*]], metadata !DIExpression()), [[DBG117]] +; NOLZCNT-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG118:!dbg !.*]] +; NOLZCNT: end: +; NOLZCNT-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG114]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META108]], metadata !DIExpression()), [[DBG114]] +; NOLZCNT-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG119:!dbg !.*]] ; entry: %bitmask = shl i32 1, %bit @@ -293,25 +405,53 @@ ; PHI node does not have any particular order for it's incomings, ; but check that the other order still works. define i32 @p8(i32 %x, i32 %bit) { -; ALL-LABEL: @p8( -; ALL-NEXT: entry: -; ALL-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG127:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META122:metadata !.*]], metadata !DIExpression()), [[DBG127]] -; ALL-NEXT: br label [[LOOP:%.*]], [[DBG128:!dbg !.*]] -; ALL: loop: -; ALL-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X_NEXT:%.*]], [[LOOP]] ], [ [[X:%.*]], [[ENTRY:%.*]] ], [[DBG129:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META123:metadata !.*]], metadata !DIExpression()), [[DBG129]] -; ALL-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG130:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META124:metadata !.*]], metadata !DIExpression()), [[DBG130]] -; ALL-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG131:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META125:metadata !.*]], metadata !DIExpression()), [[DBG131]] -; ALL-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG132:!dbg !.*]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META126:metadata !.*]], metadata !DIExpression()), [[DBG132]] -; ALL-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG133:!dbg !.*]] -; ALL: end: -; ALL-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG129]] -; ALL-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META123]], metadata !DIExpression()), [[DBG129]] -; ALL-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG134:!dbg !.*]] +; LZCNT-LABEL: @p8( +; LZCNT-NEXT: entry: +; LZCNT-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG127:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META122:metadata !.*]], metadata !DIExpression()), [[DBG127]] +; LZCNT-NEXT: [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG128:!dbg !.*]] +; LZCNT-NEXT: [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG128]] +; LZCNT-NEXT: [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG128]] +; LZCNT-NEXT: [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG128]] +; LZCNT-NEXT: [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG128]] +; LZCNT-NEXT: [[X_MASKED_NUMLEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG128]] +; LZCNT-NEXT: [[X_MASKED_LOOPTRIPCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_NUMLEADINGONEPOS]], [[DBG128]] +; LZCNT-NEXT: [[X_CURR:%.*]] = shl i32 [[X]], [[X_MASKED_LOOPTRIPCOUNT]], [[DBG128]] +; LZCNT-NEXT: br label [[LOOP:%.*]], [[DBG129:!dbg !.*]] +; LZCNT: loop: +; LZCNT-NEXT: [[TMP0:%.*]] = phi i32 [ [[X_NEXT:%.*]], [[LOOP]] ], [ [[X]], [[ENTRY:%.*]] ], [[DBG128]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META123:metadata !.*]], metadata !DIExpression()), [[DBG128]] +; LZCNT-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG130:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META124:metadata !.*]], metadata !DIExpression()), [[DBG130]] +; LZCNT-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG131:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META125:metadata !.*]], metadata !DIExpression()), [[DBG131]] +; LZCNT-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG132:!dbg !.*]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META126:metadata !.*]], metadata !DIExpression()), [[DBG132]] +; LZCNT-NEXT: br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG133:!dbg !.*]] +; LZCNT: end: +; LZCNT-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG128]] +; LZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META123]], metadata !DIExpression()), [[DBG128]] +; LZCNT-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG134:!dbg !.*]] +; +; NOLZCNT-LABEL: @p8( +; NOLZCNT-NEXT: entry: +; NOLZCNT-NEXT: [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG127:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META122:metadata !.*]], metadata !DIExpression()), [[DBG127]] +; NOLZCNT-NEXT: br label [[LOOP:%.*]], [[DBG128:!dbg !.*]] +; NOLZCNT: loop: +; NOLZCNT-NEXT: [[X_CURR:%.*]] = phi i32 [ [[X_NEXT:%.*]], [[LOOP]] ], [ [[X:%.*]], [[ENTRY:%.*]] ], [[DBG129:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META123:metadata !.*]], metadata !DIExpression()), [[DBG129]] +; NOLZCNT-NEXT: [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG130:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META124:metadata !.*]], metadata !DIExpression()), [[DBG130]] +; NOLZCNT-NEXT: [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG131:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META125:metadata !.*]], metadata !DIExpression()), [[DBG131]] +; NOLZCNT-NEXT: [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG132:!dbg !.*]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META126:metadata !.*]], metadata !DIExpression()), [[DBG132]] +; NOLZCNT-NEXT: br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG133:!dbg !.*]] +; NOLZCNT: end: +; NOLZCNT-NEXT: [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG129]] +; NOLZCNT-NEXT: call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META123]], metadata !DIExpression()), [[DBG129]] +; NOLZCNT-NEXT: ret i32 [[X_CURR_LCSSA]], [[DBG134:!dbg !.*]] ; entry: %bitmask = shl i32 1, %bit