[LoopIdiomRecognize] Don't convert a do while loop to ctlz.
This commit suppresses turning loops like this into "(bitwidth - ctlz(input))".
unsigned foo(unsigned input) {
unsigned num = 0;
do {
++num;
input >>= 1;
} while (input != 0);
return num;
}
The loop version returns a value of 1 for both an input of 0 and an input of 1. Converting to a naive ctlz does not preserve that.
Theoretically we could do better if we checked isKnownNonZero or we could insert a select to handle the divergence. But until we have motivating cases for that, this is the easiest solution.
llvm-svn: 336864
diff --git a/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp b/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
index 3e9546f..d869219 100644
--- a/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
@@ -1405,16 +1405,21 @@
if (DefX->getOpcode() == Instruction::AShr && !isKnownNonNegative(InitX, *DL))
return false;
- // If we check X != 0 before entering the loop we don't need a zero
- // check in CTLZ intrinsic, but only if Cnt Phi is not used outside of the
- // loop (if it is used we count CTLZ(X >> 1)).
- if (!IsCntPhiUsedOutsideLoop)
- if (BasicBlock *PreCondBB = PH->getSinglePredecessor())
- if (BranchInst *PreCondBr =
- dyn_cast<BranchInst>(PreCondBB->getTerminator())) {
- if (matchCondition(PreCondBr, PH) == InitX)
- ZeroCheck = true;
- }
+ // If we are using the count instruction outside the loop, make sure we
+ // have a zero check as a precondition. Without the check the loop would run
+ // one iteration for before any check of the input value. This means 0 and 1
+ // would have identical behavior in the original loop and thus
+ if (!IsCntPhiUsedOutsideLoop) {
+ auto *PreCondBB = PH->getSinglePredecessor();
+ if (!PreCondBB)
+ return false;
+ auto *PreCondBI = dyn_cast<BranchInst>(PreCondBB->getTerminator());
+ if (!PreCondBI)
+ return false;
+ if (matchCondition(PreCondBI, PH) != InitX)
+ return false;
+ ZeroCheck = true;
+ }
// Check if CTLZ intrinsic is profitable. Assume it is always profitable
// if we delete the loop (the loop has only 6 instructions):