[LoopIdiom] Introduce 'left-shift until bittest' idiom

[lebedev.ri]

Summary

The motivation here is the following inner loop in fp16/fp24 -> fp32 expander,
that runs as part of the floating-point DNG decompression in RawSpeed library:
https://github.com/darktable-org/rawspeed/blob/cd380bb9a209bd2e7a0e7022b0cab04528d151e7/src/librawspeed/decompressors/DeflateDecompressor.cpp#L112-L115

while (!(fp32_fraction & (1 << 23))) {
  fp32_exponent -= 1;
  fp32_fraction <<= 1;
}

(https://godbolt.org/z/r13YMh)
As one might notice, that loop is currently uncountable, and that whole code stays scalar.
Yet, it is rather trivial to make that loop countable:
https://godbolt.org/z/do8WMz
and we can prove that via alive2:
https://alive2.llvm.org/ce/z/7vQnji (ha nice, isn't it?)
... and that allow for the whole fp16->fp32 code to vectorize:
https://godbolt.org/z/7hYr13

Now, while i'd love to get there, i feel like i should take it in steps.

For now, this introduces support for the most basic case,
where the bit position is known as a variable,
and the loop *will* go away (has no live-outs other than the recurrence,
no extra instructions in the loop).

I have added sufficient (i believe) test coverage,
and alive2 is happy with those transforms.

Thoughts?

[jdoerfert]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

2081

Drive by: Should we move this "early exit" before step 2?

[lebedev.ri]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

2081

We can't do that, because we can't do this check before we've canonicalized the comparison predicate
(see previous if), which we can't do until after we've matched the bit-mask
(because in next patches said matching will result in other predicate changes)

[lebedev.ri]

Note that i'm mostly fine with doing this in post-commit-review mode,
i'm reasonably confident with the base change itself,
i'm mostly only looking for the high-level review.

[lebedev.ri]

ping

[lebedev.ri]

Rebase, NFC.

[lebedev.ri]

Do recurrence analysis afterwards, not when matching backedge condition.

[craig.topper]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

2059

Why are we adding a whole new matcher infrastructure for phis? Why can't we use getIncomingValueForBlock?

[lebedev.ri]

(This is in a need of a bit of rebase once i'm ready to post the final patch to actually rewrite the loop into countable.)

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

2059

There is no particular reason other than that
m_c_And(m_Value(), m_Constant())
is preferred to
I.getOpcode() == Instruction::And && (isa<Constant>I.getOperand(0) || isa<Constant>I.getOperand(1)),
because it's just that much more readable.
Of course, i can use old good methodology..

[lebedev.ri]

Rebased. Small tidyups.

Originally, i allowed the wrong instruction to liveout - in my motivational example
i need %x.next to liveout, but i allowed only %x.curr.
So let's just allow both of them to liveout.

[lebedev.ri]

@craig.topper thank you for taking a look!
Dropping PHI abstraction - on a second look it's more decent that i remember.

[craig.topper]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

2070

Should this be add -1 to match the code?

2167

This is called ".leadingonepos" in the comment block.

[lebedev.ri]

Fixup values names / comments, NFC otherwise.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

2059

On a second look, let's drop it for now.

2167

Argh, i was sure i fixed that already :)

[craig.topper]

LGTM

[lebedev.ri]

In D91038#2463821, @craig.topper wrote:

LGTM

Thank you for the review!
Note that there are 3 essential followups here, don't bother with D91725/D91726, but it would be good to get an agreement on D92754.

[lebedev.ri]

Rebased, NFC.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #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"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"

 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-idiom"
 
 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<bool, true>
     DisableLIRPAll("disable-" DEBUG_TYPE "-all",
                    cl::desc("Options to disable Loop Idiom Recognize Pass."),
                    cl::location(DisableLIRP::All), cl::init(false),
                    cl::ReallyHidden);
 
void transformLoopToPopcount(BasicBlock *PreCondBB, Instruction *CntInst,
                                PHINode *CntPhi, Value *Var);
   bool recognizeAndInsertFFS();  /// Find First Set: ctlz or cttz
   void transformLoopToCountable(Intrinsic::ID IntrinID, BasicBlock *PreCondBB,
                                 Instruction *CntInst, PHINode *CntPhi,
                                 Value *Var, Instruction *DefX,
                                 const DebugLoc &DL, bool ZeroCheck,
                                 bool IsCntPhiUsedOutsideLoop);
 
+  bool recognizeShiftUntilBitTest();
+
   /// @}
 };
 
 class LoopIdiomRecognizeLegacyPass : public LoopPass {
 public:
   static char ID;
 
   explicit LoopIdiomRecognizeLegacyPass() : LoopPass(ID) {

 }
 
 bool LoopIdiomRecognize::runOnNoncountableLoop() {
   LLVM_DEBUG(dbgs() << DEBUG_TYPE " Scanning: F["
                     << CurLoop->getHeader()->getParent()->getName()
                     << "] 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
 /// a variable and zero, and if the variable is non-zero or zero (JmpOnZero is
 /// true), the control yields to the loop entry. If the branch matches the
 /// behavior, the variable involved in the comparison is returned. This function
 /// will be called to see if the precondition and postcondition of the loop are
 /// in desirable form.
void LoopIdiomRecognize::transformLoopToPopcount(BasicBlock *PreCondBB,
   //  the loop are replaced with the NewCount -- the value returned from
   //  __builtin_ctpop().
   CntInst->replaceUsesOutsideBlock(NewCount, Body);
 
   // 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);
 }
+
+/// Match loop-invariant value.
+template <typename SubPattern_t> struct match_LoopInvariant {
+  SubPattern_t SubPattern;
+  const Loop *L;
+
+  match_LoopInvariant(const SubPattern_t &SP, const Loop *L)
+      : SubPattern(SP), L(L) {}
+
+  template <typename ITy> bool match(ITy *V) {
+    return L->isLoopInvariant(V) && SubPattern.match(V);
+  }
+};
+
+/// Matches if the value is loop-invariant.
+template <typename Ty>
+inline match_LoopInvariant<Ty> m_LoopInvariant(const Ty &M, const Loop *L) {
+  return match_LoopInvariant<Ty>(M, L);
+}
+
+/// Match PHI incoming block/value pair
+template <typename BlockSubPattern_t, typename ValueSubPattern_t>
+struct match_Incoming {
+  BlockSubPattern_t BlockSubPattern;
+  ValueSubPattern_t ValueSubPattern;
+
+  match_Incoming(BlockSubPattern_t BSP, ValueSubPattern_t VSP)
+      : BlockSubPattern(BSP), ValueSubPattern(VSP) {}
+
+  template <typename ITy> bool match(ITy *V, int IncomingIdx) {
+    auto *PHI = dyn_cast<PHINode>(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 <typename BTy, typename VTy>
+inline match_Incoming<BTy, VTy> m_Incoming(const BTy &BM, const VTy &VM) {
+  return match_Incoming<BTy, VTy>(BM, VM);
+}
+
+/// Match PHI node.
+/// FIXME: generalize to the variadic number of incomings.
+template <typename FirstIncomingTy, typename SecondIncomingTy>
+struct match_PHI {
+  FirstIncomingTy FirstSubPattern;
+  SecondIncomingTy SecondSubPattern;
+
+  match_PHI(FirstIncomingTy FirstSubPattern, SecondIncomingTy SecondSubPattern)
+      : FirstSubPattern(FirstSubPattern), SecondSubPattern(SecondSubPattern) {}
+
+  template <typename ITy> bool match(ITy *V) {
+    auto *PHI = dyn_cast<PHINode>(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 <typename FirstIncomingTy, typename SecondIncomingTy>
+inline match_PHI<FirstIncomingTy, SecondIncomingTy>
+m_PHI(FirstIncomingTy FirstSubPattern, SecondIncomingTy SecondSubPattern) {
+  return match_PHI<FirstIncomingTy, SecondIncomingTy>(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;
+  }
+
+  // Step 2: Check if the recurrence is in desirable form.
+  // We'll do that as a part of matching the backedge condition,
+  // so just record the matcher.
+
+  auto MatchRecurrence = 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?
+
+  // Step 3: 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(MatchRecurrence,
+                         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 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<Instruction>(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;
+}

llvm/test/Transforms/LoopIdiom/X86/left-shift-until-bittest.ll

 ; The patterns here are all have the same base form:
 ;   while (!(x & (1U << bit)))
 ;     x <<= 1;
 ; .. which is an uncountable loop.
 ; We should transform it into it's countable form.
 
 ; 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
   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:
   ret i32 %x.curr
 }
 
 ; 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
   br label %loop
 
 loop:
   %x.curr = phi i16 [ %x, %entry ], [ %x.next, %loop ]
   %x.curr.bitmasked = and i16 %x.curr, %bitmask
loop:
   br i1 %x.curr.isbitunset, label %loop, label %end
 
 end:
   ret i32 %x.curr
 }
 
 ; 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
   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 ne i32 %x.curr.bitmasked, 0 ; swapped predicate
   %x.next = shl i32 %x.curr, 1
   br i1 %x.curr.isbitunset, label %end, label %loop ; swapped dests
 
 end:
   ret i32 %x.curr
 }
 
 ; `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
   br label %loop
 
 loop:
   %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
   %x.curr.bitmasked = and i32 %bitmask, %x.curr ; swapped
   %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:
   ret i32 %x.curr
 }
 
 ; 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
   br label %loop
 
 loop:
   %x.curr = phi i32 [ %x.next, %loop ], [ %x, %entry ]
   %x.curr.bitmasked = and i32 %x.curr, %bitmask