[LoopIdiom] 'left-shift until bittest' idiom: support canonical sign bit mask

[lebedev.ri]

Summary

If the bitmask is for sign bit, instcombine would have canonicalized
the pattern into a proper sign bit check. Supporting that is still
simple, but requires a bit of a roundtrip - we first have to use
decomposeBitTestICmp(), and the rest again just works.

[craig.topper]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

2034

At least for MatchVariableBitMask and MatchConstantBitMask isn't this doing duplicate work finding the ICmp and looking through the phi? And only then checking the differing part of the pattern?

[lebedev.ri]

Do recurrence analysis afterwards, not when matching backedge condition.

[lebedev.ri]

Rebased, NFC.

[lebedev.ri]

Rebased, NFC.

[lebedev.ri]

Rebased, NFC.

[craig.topper]

LGTM

[lebedev.ri]

In D91726#2470215, @craig.topper wrote:

LGTM

Thank you for the review!

[lebedev.ri]

Rebased, NFC.

[pcc]

It looks like this patch caused an assertion failure:

$ cat test.ii
# 1 "" 3
typedef int a;
typedef unsigned b;
struct c {
  template <typename d> c(d e) : f(e) {}
  int f;
};
struct g {
  template <typename h, typename ad> g(h e, ad) : ae(e), af(0) {}
  c ae;
  c af;
};
template <typename ag, typename i> auto ah(ag e, i) { return g(e, 0); }
class j {
public:
  void k();
};
class l;
class m {
public:
  m(int, l, int);
};
class l {
public:
  l(int, int);
};
class n {
  bool o();
  int ax;
};
template <typename> using ay = m;
template <typename, typename> using bc = l;
class p {
public:
  int *m_fn3();
  a q();
};
class r {
public:
  r(int)
      : bh(0, bc<int, int>(int(), bi), bi), bj(int(), bi), bk(int(), bi),
        bl(int(), bi) {
    p bn;
    int *base = bn.m_fn3();
    a bo = base == nullptr ?: bn.q();
    if (bo)
      for (auto bp = ah(bo, 0); __builtin_expect(bp.ae.f >= bp.af.f, false);)
        j().k();
  }
  int bi;
  ay<bc<int, int>> bh;
  bc<int, int> bj;
  bc<b, bool> bk;
  bc<b, int> bl;
};
bool n::o() { r bq(ax); }
$ ~/l2/ra/bin/clang -O2 test.ii
clang: ../llvm/include/llvm/IR/Instructions.h:2767: llvm::Value *llvm::PHINode::getIncomingValueForBlock(const llvm::BasicBlock *) const: Assertion `Idx >= 0 && "Invalid basic block argument!"' failed.

[lebedev.ri]

In D91726#2474387, @pcc wrote:

It looks like this patch caused an assertion failure:

$ cat test.ii
# 1 "" 3
typedef int a;
typedef unsigned b;
struct c {
  template <typename d> c(d e) : f(e) {}
  int f;
};
struct g {
  template <typename h, typename ad> g(h e, ad) : ae(e), af(0) {}
  c ae;
  c af;
};
template <typename ag, typename i> auto ah(ag e, i) { return g(e, 0); }
class j {
public:
  void k();
};
class l;
class m {
public:
  m(int, l, int);
};
class l {
public:
  l(int, int);
};
class n {
  bool o();
  int ax;
};
template <typename> using ay = m;
template <typename, typename> using bc = l;
class p {
public:
  int *m_fn3();
  a q();
};
class r {
public:
  r(int)
      : bh(0, bc<int, int>(int(), bi), bi), bj(int(), bi), bk(int(), bi),
        bl(int(), bi) {
    p bn;
    int *base = bn.m_fn3();
    a bo = base == nullptr ?: bn.q();
    if (bo)
      for (auto bp = ah(bo, 0); __builtin_expect(bp.ae.f >= bp.af.f, false);)
        j().k();
  }
  int bi;
  ay<bc<int, int>> bh;
  bc<int, int> bj;
  bc<b, bool> bk;
  bc<b, int> bl;
};
bool n::o() { r bq(ax); }
$ ~/l2/ra/bin/clang -O2 test.ii
clang: ../llvm/include/llvm/IR/Instructions.h:2767: llvm::Value *llvm::PHINode::getIncomingValueForBlock(const llvm::BasicBlock *) const: Assertion `Idx >= 0 && "Invalid basic block argument!"' failed.

Thank you for the reproducer, i'll take a look.

[lebedev.ri]

In D91726#2474793, @lebedev.ri wrote:

In D91726#2474387, @pcc wrote:

It looks like this patch caused an assertion failure:

$ cat test.ii
# 1 "" 3
typedef int a;
typedef unsigned b;
struct c {
  template <typename d> c(d e) : f(e) {}
  int f;
};
struct g {
  template <typename h, typename ad> g(h e, ad) : ae(e), af(0) {}
  c ae;
  c af;
};
template <typename ag, typename i> auto ah(ag e, i) { return g(e, 0); }
class j {
public:
  void k();
};
class l;
class m {
public:
  m(int, l, int);
};
class l {
public:
  l(int, int);
};
class n {
  bool o();
  int ax;
};
template <typename> using ay = m;
template <typename, typename> using bc = l;
class p {
public:
  int *m_fn3();
  a q();
};
class r {
public:
  r(int)
      : bh(0, bc<int, int>(int(), bi), bi), bj(int(), bi), bk(int(), bi),
        bl(int(), bi) {
    p bn;
    int *base = bn.m_fn3();
    a bo = base == nullptr ?: bn.q();
    if (bo)
      for (auto bp = ah(bo, 0); __builtin_expect(bp.ae.f >= bp.af.f, false);)
        j().k();
  }
  int bi;
  ay<bc<int, int>> bh;
  bc<int, int> bj;
  bc<b, bool> bk;
  bc<b, int> bl;
};
bool n::o() { r bq(ax); }
$ ~/l2/ra/bin/clang -O2 test.ii
clang: ../llvm/include/llvm/IR/Instructions.h:2767: llvm::Value *llvm::PHINode::getIncomingValueForBlock(const llvm::BasicBlock *) const: Assertion `Idx >= 0 && "Invalid basic block argument!"' failed.

Thank you for the reproducer, i'll take a look.

And, that is not a sufficient information for me to reproduce :/
Can you please just give me the IR produced by clang (i.e. -O2 -S -emit-llvm -Xclang -disable-llvm-optzns)?

[pcc]

Sure, here is the .ll file.

test2.ll11 KBDownload

Reproduces with opt -O2 -S test2.ll.

[lebedev.ri]

In D91726#2475301, @pcc wrote:

Sure, here is the .ll file.

test2.ll11 KBDownload

Reproduces with opt -O2 -S test2.ll.

Thank you, i can reproduce now.
This appears to be a very dumb mistake of forgetting to check the basic block of the PHI node, will fixup in a moment.

[lebedev.ri]

In D91726#2475308, @lebedev.ri wrote:

In D91726#2475301, @pcc wrote:

Sure, here is the .ll file.

test2.ll11 KBDownload

Reproduces with opt -O2 -S test2.ll.

Thank you, i can reproduce now.
This appears to be a very dumb mistake of forgetting to check the basic block of the PHI node, will fixup in a moment.

Fixed in 51879a525649c8151f7e841b66a5cea0e1c8e74e, thank you for the reproducer!

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/CmpInstAnalysis.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"

 ///
 ///   end:
 ///     %x.curr.res = phi i32 [ %x.curr, %loop ] <...>
 ///     %x.next.res = phi i32 [ %x.next, %loop ] <...>
 ///     <...>
 /// \endcode
 static bool detectShiftUntilBitTestIdiom(Loop *CurLoop, Value *&BaseX,
                                          Value *&BitMask, Value *&BitPos,
-                                         Value *&CurrX, Value *&NextX) {
+                                         Value *&CurrX, Value *&NextX,
+                                         size_t &CanonicalHeaderSize) {
   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;
   }
if (!match(LoopHeaderBB->getTerminator(),
                   m_BasicBlock(TrueBB), m_BasicBlock(FalseBB)))) {
     LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad backedge structure.\n");
     return false;
   }
 
   // Step 2: Check if the backedge's condition is in desirable form.
 
   auto MatchVariableBitMask = [&]() {
+    CanonicalHeaderSize = 5;
     return ICmpInst::isEquality(Pred) && match(CmpRHS, m_Zero()) &&
            match(CmpLHS,
                  m_c_And(m_Value(CurrX),
                          m_CombineAnd(
                              m_Value(BitMask),
                              m_LoopInvariant(m_Shl(m_One(), m_Value(BitPos)),
                                              CurLoop))));
   };
   auto MatchConstantBitMask = [&]() {
+    CanonicalHeaderSize = 5;
     return ICmpInst::isEquality(Pred) && match(CmpRHS, m_Zero()) &&
            match(CmpLHS, m_And(m_Value(CurrX),
                                m_CombineAnd(m_Value(BitMask), m_Power2()))) &&
            (BitPos = ConstantExpr::getExactLogBase2(cast<Constant>(BitMask)));
   };
+  auto MatchDecomposableConstantBitMask = [&]() {
+    CanonicalHeaderSize = 4;
 
-  if (!MatchVariableBitMask() && !MatchConstantBitMask()) {
-    // FIXME: support sign bit test (use llvm::decomposeBitTestICmp()).
+    APInt Mask;
+    return llvm::decomposeBitTestICmp(CmpLHS, CmpRHS, Pred, CurrX, Mask) &&
+           ICmpInst::isEquality(Pred) && Mask.isPowerOf2() &&
+           (BitMask = ConstantInt::get(CurrX->getType(), Mask)) &&
+           (BitPos = ConstantInt::get(CurrX->getType(), Mask.logBase2()));
+  };
+
+  if (!MatchVariableBitMask() && !MatchConstantBitMask() &&
+      !MatchDecomposableConstantBitMask()) {
     LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad backedge comparison.\n");
     return false;
   }
 
   // Step 3: Check if the recurrence is in desirable form.
   auto *CurrXPN = dyn_cast<PHINode>(CurrX);
   if (!CurrXPN) {
     LLVM_DEBUG(dbgs() << DEBUG_TYPE " Not a PHI node.\n");
     return false;
   }
 
   BaseX = CurrXPN->getIncomingValueForBlock(LoopPreheaderBB);
   NextX = CurrXPN->getIncomingValueForBlock(LoopHeaderBB);
 
   if (!match(NextX, m_Shl(m_Specific(CurrX), m_One()))) {
     // FIXME: support right-shift?
     LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad recurrence.\n");
     return false;

 ///     %x.curr.res = phi i32 [ %x.curr, %loop ] <...>
 ///     %x.next.res = phi i32 [ %x.next, %loop ] <...>
 ///     <...>
 /// \endcode
 bool LoopIdiomRecognize::recognizeShiftUntilBitTest() {
   bool MadeChange = false;
 
   Value *X, *BitMask, *BitPos, *XCurr, *XNext;
-  if (!detectShiftUntilBitTestIdiom(CurLoop, X, BitMask, BitPos, XCurr,
-                                    XNext)) {
+  size_t CanonicalHeaderSize;
+  if (!detectShiftUntilBitTestIdiom(CurLoop, X, BitMask, BitPos, XCurr, XNext,
+                                    CanonicalHeaderSize)) {
     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) {

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

loop:
   %x.next = shl i32 %x.curr, 1
   br i1 %x.curr.isbitunset, label %loop, label %end
 
 end:
   ret i32 %x.curr
 }
 
 define i32 @p7_constant_mask_signbit_canonical(i32 %x) {
-; ALL-LABEL: @p7_constant_mask_signbit_canonical(
-; ALL-NEXT:  entry:
-; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG116:!dbg !.*]]
-; ALL:       loop:
-; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG117:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META113:metadata !.*]], metadata !DIExpression()), [[DBG117]]
-; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp sgt i32 [[X_CURR]], -1, [[DBG118:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META114:metadata !.*]], metadata !DIExpression()), [[DBG118]]
-; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG119:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META115:metadata !.*]], metadata !DIExpression()), [[DBG119]]
-; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG120:!dbg !.*]]
-; ALL:       end:
-; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG117]]
-; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG121:!dbg !.*]]
+; LZCNT-LABEL: @p7_constant_mask_signbit_canonical(
+; LZCNT-NEXT:  entry:
+; LZCNT-NEXT:    [[X_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X:%.*]], i1 true), [[DBG116:!dbg !.*]]
+; LZCNT-NEXT:    [[X_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_NUMLEADINGZEROS]], [[DBG116]]
+; LZCNT-NEXT:    [[X_LEADINGONEPOS:%.*]] = add i32 [[X_NUMACTIVEBITS]], -1, [[DBG116]]
+; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 31, [[X_LEADINGONEPOS]], [[DBG116]]
+; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG116]]
+; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG116]]
+; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG116]]
+; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG117:!dbg !.*]]
+; LZCNT:       loop:
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT]], [[LOOP]] ], [[DBG116]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META113:metadata !.*]], metadata !DIExpression()), [[DBG116]]
+; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp sgt i32 [[X_CURR]], -1, [[DBG118:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META114:metadata !.*]], metadata !DIExpression()), [[DBG118]]
+; LZCNT-NEXT:    [[TMP1:%.*]] = shl i32 [[X_CURR]], 1, [[DBG119:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META115:metadata !.*]], metadata !DIExpression()), [[DBG119]]
+; LZCNT-NEXT:    br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG120:!dbg !.*]]
+; LZCNT:       end:
+; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG116]]
+; LZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG121:!dbg !.*]]
+;
+; NOLZCNT-LABEL: @p7_constant_mask_signbit_canonical(
+; NOLZCNT-NEXT:  entry:
+; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG116:!dbg !.*]]
+; NOLZCNT:       loop:
+; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG117:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META113:metadata !.*]], metadata !DIExpression()), [[DBG117]]
+; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp sgt i32 [[X_CURR]], -1, [[DBG118:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META114:metadata !.*]], metadata !DIExpression()), [[DBG118]]
+; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG119:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META115:metadata !.*]], metadata !DIExpression()), [[DBG119]]
+; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG120:!dbg !.*]]
+; NOLZCNT:       end:
+; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG117]]
+; NOLZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG121:!dbg !.*]]
 ;
 entry:
   br label %loop
 
 loop:
   %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
   %x.curr.isbitunset = icmp sgt i32 %x.curr, -1
   %x.next = shl i32 %x.curr, 1
loop:
   br i1 %x.curr.isbitunset, label %loop, label %end
 
 end:
   ret i32 %x.curr
 }
 
 ; ICmp-Br are commutative
 define i32 @p11(i32 %x) {
-; ALL-LABEL: @p11(
-; ALL-NEXT:  entry:
-; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG172:!dbg !.*]]
-; ALL:       loop:
-; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG173:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META169:metadata !.*]], metadata !DIExpression()), [[DBG173]]
-; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp slt i32 [[X_CURR]], 0, [[DBG174:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META170:metadata !.*]], metadata !DIExpression()), [[DBG174]]
-; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG175:!dbg !.*]]
-; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META171:metadata !.*]], metadata !DIExpression()), [[DBG175]]
-; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[END:%.*]], label [[LOOP]], [[DBG176:!dbg !.*]]
-; ALL:       end:
-; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG173]]
-; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG177:!dbg !.*]]
+; LZCNT-LABEL: @p11(
+; LZCNT-NEXT:  entry:
+; LZCNT-NEXT:    [[X_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X:%.*]], i1 true), [[DBG172:!dbg !.*]]
+; LZCNT-NEXT:    [[X_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_NUMLEADINGZEROS]], [[DBG172]]
+; LZCNT-NEXT:    [[X_LEADINGONEPOS:%.*]] = add i32 [[X_NUMACTIVEBITS]], -1, [[DBG172]]
+; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 31, [[X_LEADINGONEPOS]], [[DBG172]]
+; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG172]]
+; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG172]]
+; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG172]]
+; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG173:!dbg !.*]]
+; LZCNT:       loop:
+; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ [[X_NEXT]], [[LOOP]] ], [[DBG172]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META169:metadata !.*]], metadata !DIExpression()), [[DBG172]]
+; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp slt i32 [[X_CURR]], 0, [[DBG174:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META170:metadata !.*]], metadata !DIExpression()), [[DBG174]]
+; LZCNT-NEXT:    [[TMP1:%.*]] = shl i32 [[X_CURR]], 1, [[DBG175:!dbg !.*]]
+; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META171:metadata !.*]], metadata !DIExpression()), [[DBG175]]
+; LZCNT-NEXT:    br i1 true, label [[END:%.*]], label [[LOOP]], [[DBG176:!dbg !.*]]
+; LZCNT:       end:
+; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG172]]
+; LZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG177:!dbg !.*]]
+;
+; NOLZCNT-LABEL: @p11(
+; NOLZCNT-NEXT:  entry:
+; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG172:!dbg !.*]]
+; NOLZCNT:       loop:
+; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG173:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META169:metadata !.*]], metadata !DIExpression()), [[DBG173]]
+; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp slt i32 [[X_CURR]], 0, [[DBG174:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META170:metadata !.*]], metadata !DIExpression()), [[DBG174]]
+; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG175:!dbg !.*]]
+; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META171:metadata !.*]], metadata !DIExpression()), [[DBG175]]
+; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[END:%.*]], label [[LOOP]], [[DBG176:!dbg !.*]]
+; NOLZCNT:       end:
+; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG173]]
+; NOLZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG177:!dbg !.*]]
 ;
 entry:
   br label %loop
 
 loop:
   %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
   %x.curr.isbitunset = icmp slt i32 %x.curr, 0
   %x.next = shl i32 %x.curr, 1