From 763c59dc9aa22f416bea70156dca89070936b2a2 Mon Sep 17 00:00:00 2001
From: Amaury Sechet <deadalnix@gmail.com>
Date: Thu, 18 Aug 2016 20:43:50 +0000
Subject: [PATCH] Make cltz and cttz zero undef when the operand cannot be zero
 in InstCombine

Summary: Also add popcount(n) == bitsize(n)  -> n == -1 transformation.

Reviewers: majnemer, spatel

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D23134

llvm-svn: 279141
---
 .../Transforms/InstCombine/InstCombineCalls.cpp    | 25 +++++++++++++++++-----
 llvm/test/Transforms/InstCombine/intrinsics.ll     | 20 +++++++++++++++++
 2 files changed, 40 insertions(+), 5 deletions(-)

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
index f00363e..00fdc46 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
@@ -1133,7 +1133,10 @@ static Instruction *simplifyMaskedScatter(IntrinsicInst &II, InstCombiner &IC) {
   return nullptr;
 }
 
-static Value *foldCttzCtlz(IntrinsicInst &II, InstCombiner &IC) {
+static Instruction *foldCttzCtlz(IntrinsicInst &II, InstCombiner &IC) {
+  assert((II.getIntrinsicID() == Intrinsic::cttz ||
+          II.getIntrinsicID() == Intrinsic::ctlz) &&
+         "Expected cttz or ctlz intrinsic");
   Value *Op0 = II.getArgOperand(0);
   // FIXME: Try to simplify vectors of integers.
   auto *IT = dyn_cast<IntegerType>(Op0->getType());
@@ -1156,8 +1159,20 @@ static Value *foldCttzCtlz(IntrinsicInst &II, InstCombiner &IC) {
   // zero, this value is constant.
   // FIXME: This should be in InstSimplify because we're replacing an
   // instruction with a constant.
-  if ((Mask & KnownZero) == Mask)
-    return ConstantInt::get(IT, APInt(BitWidth, NumMaskBits));
+  if ((Mask & KnownZero) == Mask) {
+    auto *C = ConstantInt::get(IT, APInt(BitWidth, NumMaskBits));
+    return IC.replaceInstUsesWith(II, C);
+  }
+
+  // If the input to cttz/ctlz is known to be non-zero,
+  // then change the 'ZeroIsUndef' parameter to 'true'
+  // because we know the zero behavior can't affect the result.
+  if (KnownOne != 0 || isKnownNonZero(Op0, IC.getDataLayout())) {
+    if (!match(II.getArgOperand(1), m_One())) {
+      II.setOperand(1, IC.Builder->getTrue());
+      return &II;
+    }
+  }
 
   return nullptr;
 }
@@ -1457,8 +1472,8 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) {
 
   case Intrinsic::cttz:
   case Intrinsic::ctlz:
-    if (Value *V = foldCttzCtlz(*II, *this))
-      return replaceInstUsesWith(*II, V);
+    if (auto *I = foldCttzCtlz(*II, *this))
+      return I;
     break;
 
   case Intrinsic::uadd_with_overflow:
diff --git a/llvm/test/Transforms/InstCombine/intrinsics.ll b/llvm/test/Transforms/InstCombine/intrinsics.ll
index 599cee0..858f9c0 100644
--- a/llvm/test/Transforms/InstCombine/intrinsics.ll
+++ b/llvm/test/Transforms/InstCombine/intrinsics.ll
@@ -380,6 +380,16 @@ define i32 @ctlz_undef(i32 %Value) nounwind {
 
 }
 
+define i32 @ctlz_make_undef(i32 %a) {
+  %or = or i32 %a, 8
+  %ctlz = tail call i32 @llvm.ctlz.i32(i32 %or, i1 false)
+  ret i32 %ctlz
+; CHECK-LABEL: @ctlz_make_undef(
+; CHECK-NEXT: %or = or i32 %a, 8
+; CHECK-NEXT: %ctlz = tail call i32 @llvm.ctlz.i32(i32 %or, i1 true)
+; CHECK-NEXT: ret i32 %ctlz
+}
+
 define i32 @cttz_undef(i32 %Value) nounwind {
 ; CHECK-LABEL: @cttz_undef(
 ; CHECK-NEXT:    ret i32 undef
@@ -389,6 +399,16 @@ define i32 @cttz_undef(i32 %Value) nounwind {
 
 }
 
+define i32 @cttz_make_undef(i32 %a) {
+  %or = or i32 %a, 8
+  %cttz = tail call i32 @llvm.cttz.i32(i32 %or, i1 false)
+  ret i32 %cttz
+; CHECK-LABEL: @cttz_make_undef(
+; CHECK-NEXT: %or = or i32 %a, 8
+; CHECK-NEXT: %cttz = tail call i32 @llvm.cttz.i32(i32 %or, i1 true)
+; CHECK-NEXT: ret i32 %cttz
+}
+
 define i32 @ctlz_select(i32 %Value) nounwind {
 ; CHECK-LABEL: @ctlz_select(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctlz.i32(i32 %Value, i1 false)
-- 
2.7.4