Basis of dropping uses in llvm.assume.

Summary: This patch adds the basic utilities to deal with dropable uses. dropable uses are uses that we rather drop than prevent transformations, for now they are limited to uses in llvm.assume.

Reviewers: jdoerfert, sstefan1

Reviewed By: jdoerfert

Subscribers: uenoku, lebedev.ri, mgorny, hiraditya, dexonsmith, llvm-commits

Tags: #llvm

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

4 files changed, 73 insertions, 44 deletions

diff --git a/llvm/lib/IR/KnowledgeRetention.cpp b/llvm/lib/IR/KnowledgeRetention.cpp
index fa21450..e877911 100644
--- a/llvm/lib/IR/KnowledgeRetention.cpp
+++ b/llvm/lib/IR/KnowledgeRetention.cpp
@@ -197,51 +197,27 @@ bool llvm::hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn,
   if (Assume.bundle_op_infos().empty())
     return false;
 
-  CallInst::bundle_op_iterator Lookup;
-
-  /// The right attribute can be found by binary search. After this finding the
-  /// right WasOn needs to be done via linear search.
-  /// Element have been ordered by argument value so the first we find is the
-  /// one we need.
-  if (AQR == AssumeQuery::Lowest)
-    Lookup =
-        llvm::lower_bound(Assume.bundle_op_infos(), AttrName,
-                          [](const CallBase::BundleOpInfo &BOI, StringRef RHS) {
-                            return BOI.Tag->getKey() < RHS;
-                          });
-  else
-    Lookup = std::prev(
-        llvm::upper_bound(Assume.bundle_op_infos(), AttrName,
-                          [](StringRef LHS, const CallBase::BundleOpInfo &BOI) {
-                            return LHS < BOI.Tag->getKey();
-                          }));
-
-  if (Lookup == Assume.bundle_op_info_end() ||
-      Lookup->Tag->getKey() != AttrName)
-    return false;
-  if (IsOn) {
-    assert((Lookup->End - Lookup->Begin > BOIE_WasOn) &&
-           "missing argument of attribute");
-    while (true) {
-      if (Lookup == Assume.bundle_op_info_end() ||
-          Lookup->Tag->getKey() != AttrName)
-        return false;
-      if (getValueFromBundleOpInfo(Assume, *Lookup, BOIE_WasOn) == IsOn)
-        break;
-      if (AQR == AssumeQuery::Highest &&
-          Lookup == Assume.bundle_op_info_begin())
-        return false;
-      Lookup = Lookup + (AQR == AssumeQuery::Lowest ? 1 : -1);
+  auto Loop = [&](auto &&Range) {
+    for (auto &BOI : Range) {
+      if (BOI.Tag->getKey() != AttrName)
+        continue;
+      if (IsOn && (BOI.End - BOI.Begin <= BOIE_WasOn ||
+                   IsOn != getValueFromBundleOpInfo(Assume, BOI, BOIE_WasOn)))
+        continue;
+      if (ArgVal) {
+        assert(BOI.End - BOI.Begin > BOIE_Argument);
+        *ArgVal = cast<ConstantInt>(
+                      getValueFromBundleOpInfo(Assume, BOI, BOIE_Argument))
+                      ->getZExtValue();
+      }
+      return true;
     }
-  }
+    return false;
+  };
 
-  if (Lookup->End - Lookup->Begin < BOIE_Argument)
-    return true;
-  if (ArgVal)
-    *ArgVal = cast<ConstantInt>(
-                  getValueFromBundleOpInfo(Assume, *Lookup, BOIE_Argument))
-                  ->getZExtValue();
-  return true;
+  if (AQR == AssumeQuery::Lowest)
+    return Loop(Assume.bundle_op_infos());
+  return Loop(reverse(Assume.bundle_op_infos()));
 }
 
 void llvm::fillMapFromAssume(CallInst &AssumeCI, RetainedKnowledgeMap &Result) {
diff --git a/llvm/lib/IR/User.cpp b/llvm/lib/IR/User.cpp
index 4a3eba9..3097916 100644
--- a/llvm/lib/IR/User.cpp
+++ b/llvm/lib/IR/User.cpp
@@ -9,6 +9,7 @@
 #include "llvm/IR/User.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/GlobalValue.h"
+#include "llvm/IR/IntrinsicInst.h"
 
 namespace llvm {
 class BasicBlock;
@@ -105,6 +106,12 @@ MutableArrayRef<uint8_t> User::getDescriptor() {
       reinterpret_cast<uint8_t *>(DI) - DI->SizeInBytes, DI->SizeInBytes);
 }
 
+bool User::isDroppable() const {
+  if (const auto *Intr = dyn_cast<IntrinsicInst>(this))
+    return Intr->getIntrinsicID() == Intrinsic::assume;
+  return false;
+}
+
 //===----------------------------------------------------------------------===//
 //                         User operator new Implementations
 //===----------------------------------------------------------------------===//
diff --git a/llvm/lib/IR/Value.cpp b/llvm/lib/IR/Value.cpp
index beb3989..8cd58975 100644
--- a/llvm/lib/IR/Value.cpp
+++ b/llvm/lib/IR/Value.cpp
@@ -141,6 +141,51 @@ bool Value::hasNUsesOrMore(unsigned N) const {
   return hasNItemsOrMore(use_begin(), use_end(), N);
 }
 
+static bool isUnDroppableUser(const User *U) { return !U->isDroppable(); }
+
+Use *Value::getSingleUndroppableUse() {
+  Use *Result = nullptr;
+  for (Use &U : uses()) {
+    if (!U.getUser()->isDroppable()) {
+      if (Result)
+        return nullptr;
+      Result = &U;
+    }
+  }
+  return Result;
+}
+
+bool Value::hasNUndroppableUses(unsigned int N) const {
+  return hasNItems(user_begin(), user_end(), N, isUnDroppableUser);
+}
+
+bool Value::hasNUndroppableUsesOrMore(unsigned int N) const {
+  return hasNItemsOrMore(user_begin(), user_end(), N, isUnDroppableUser);
+}
+
+void Value::dropDroppableUses(
+    llvm::function_ref<bool(const Use *)> ShouldDrop) {
+  SmallVector<Use *, 8> ToBeEdited;
+  for (Use &U : uses())
+    if (U.getUser()->isDroppable() && ShouldDrop(&U))
+      ToBeEdited.push_back(&U);
+  for (Use *U : ToBeEdited) {
+    U->removeFromList();
+    if (auto *Assume = dyn_cast<IntrinsicInst>(U->getUser())) {
+      assert(Assume->getIntrinsicID() == Intrinsic::assume);
+      unsigned OpNo = U->getOperandNo();
+      if (OpNo == 0)
+        Assume->setOperand(0, ConstantInt::getTrue(Assume->getContext()));
+      else {
+        Assume->setOperand(OpNo, UndefValue::get(U->get()->getType()));
+        CallInst::BundleOpInfo &BOI = Assume->getBundleOpInfoForOperand(OpNo);
+        BOI.Tag = getContext().pImpl->getOrInsertBundleTag("ignore");
+      }
+    } else
+      llvm_unreachable("unkown droppable use");
+  }
+}
+
 bool Value::isUsedInBasicBlock(const BasicBlock *BB) const {
   // This can be computed either by scanning the instructions in BB, or by
   // scanning the use list of this Value. Both lists can be very long, but
diff --git a/llvm/lib/IR/Verifier.cpp b/llvm/lib/IR/Verifier.cpp
index abd7a00..676f98d 100644
--- a/llvm/lib/IR/Verifier.cpp
+++ b/llvm/lib/IR/Verifier.cpp
@@ -4322,7 +4322,8 @@ void Verifier::visitIntrinsicCall(Intrinsic::ID ID, CallBase &Call) {
     break;
   case Intrinsic::assume: {
     for (auto &Elem : Call.bundle_op_infos()) {
-      Assert(Attribute::isExistingAttribute(Elem.Tag->getKey()),
+      Assert(Elem.Tag->getKey() == "ignore" ||
+                 Attribute::isExistingAttribute(Elem.Tag->getKey()),
              "tags must be valid attribute names");
       Assert(Elem.End - Elem.Begin <= 2, "to many arguments");
       Attribute::AttrKind Kind =