Basis of dropping uses in llvm.assume.

[Tyker]

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.

[jdoerfert]

We need to split this patch. The droppable logic can be applied to regular assumes already so we can separate this from the operand bundle stuff at first. That should make the patches significantly smaller. You also need to separate D73404 out.

llvm/lib/IR/Value.cpp

181

We have to make sure we handle "incomplete" operand bundles properly. I guess if we always go through KnowledgeRetention we can make sure of that.

[Tyker]

i splited the patch.

[lebedev.ri]

I'm not sure i'm fully onboard with using generic 'droppable' term for these uses.
Can we be somehow more specific, since those are really only ever about assumes?

llvm/include/llvm/ADT/STLExtras.h

1534

These changes can be separated into another review

[Tyker]

In D73404#1883378, @lebedev.ri wrote:

I'm not sure i'm fully onboard with using generic 'droppable' term for these uses.
Can we be somehow more specific, since those are really only ever about assumes?

i don't know if it can be useful in other situations than for uses in assume.
if you think it probably won't we can just call then use in assume.

[Tyker]

splitted the patch as requested.

[jdoerfert]

There might be other operand bundle and metadata uses we want to drop later. Unclear. We could also rename it to "drop assume uses"

[jdoerfert]

I think this makes sense, especially since lifetime markers will soon join assume as droppable users. That said, we need to improve the nullptr replacement for assume. I made some suggestions here https://reviews.llvm.org/D73832#1902199

llvm/include/llvm/IR/User.h

224

We should list what those uses are, later maybe define an enum to restrict the selection.

[Tyker]

Changes:

• Dropped uses in assume are represented the tag ignore and the values are replaced with undef.
• this broke the ordering invariance that hasAttributeInAssume was depending upon so i changed the implementation to a more naive linear search.
• changed the test in KnowledgeRetentionTest.cpp to make them easier to write.
• adapted the LangRef and verifier to the new "ignore" tag.

an assume containg a dropped use now looks like

call void @llvm.assume(i1 true) [ "ignore"(i32* undef, i64 8) ]

[Tyker]

rebased

[lebedev.ri]

Yes, i suppose given that we now have a second user (lifetime), droppable isn't the worst choice.

[jdoerfert]

llvm/lib/IR/KnowledgeRetention.cpp

220 ↗

(On Diff #248999)

Can we give it a more descriptive name than Loop.

[jdoerfert]

LGTM. One comment though (see Loop)

[Tyker]

This patch depends on D74967 which is not yet accepted.

llvm/include/llvm/ADT/STLExtras.h

 /// tuple variadically to f as if by calling f(a1, a2, ..., an) and
 /// return the result.
 template <typename F, typename Tuple>
 auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
     std::forward<F>(f), std::forward<Tuple>(t),
     std::make_index_sequence<
         std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
   using Indices = std::make_index_sequence<
       std::tuple_size<typename std::decay<Tuple>::type>::value>;
 
   return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
                                   Indices{});
 }
 
 /// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N)
 /// time. Not meant for use with random-access iterators.
-template <typename IterTy>
+/// Can optionally take a predicate to filter lazily some items.
+template <typename IterTy,
+          typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
 bool hasNItems(
     IterTy &&Begin, IterTy &&End, unsigned N,
+    Pred &&ShouldBeCounted =
+        [](const decltype(*std::declval<IterTy>()) &) { return true; },
     typename std::enable_if<
         !std::is_same<
             typename std::iterator_traits<typename std::remove_reference<
                 decltype(Begin)>::type>::iterator_category,
             std::random_access_iterator_tag>::value,
         void>::type * = nullptr) {
-  for (; N; --N, ++Begin)
+  for (; N; ++Begin) {
     if (Begin == End)
       return false; // Too few.
+    N -= ShouldBeCounted(*Begin);
+  }
   return Begin == End;
 }
 
 /// Return true if the sequence [Begin, End) has N or more items. Runs in O(N)
 /// time. Not meant for use with random-access iterators.
-template <typename IterTy>
+/// Can optionally take a predicate to filter lazily some items.
+template <typename IterTy,
+          typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
 bool hasNItemsOrMore(
     IterTy &&Begin, IterTy &&End, unsigned N,
+    Pred &&ShouldBeCounted =
+        [](const decltype(*std::declval<IterTy>()) &) { return true; },
     typename std::enable_if<
         !std::is_same<
             typename std::iterator_traits<typename std::remove_reference<
                 decltype(Begin)>::type>::iterator_category,
             std::random_access_iterator_tag>::value,
         void>::type * = nullptr) {
-  for (; N; --N, ++Begin)
+  for (; N; ++Begin) {
     if (Begin == End)
       return false; // Too few.
+    N -= ShouldBeCounted(*Begin);
+  }
   return true;
 }
 
 /// Returns a raw pointer that represents the same address as the argument.
 ///
 /// The late bound return should be removed once we move to C++14 to better
 /// align with the C++20 declaration. Also, this implementation can be removed
 /// once we move to C++20 where it's defined as std::to_addres()

llvm/include/llvm/IR/User.h

public:
   /// themselves.  In these instances, the operand count isn't used to find the
   /// OperandList, so there's no issue in having the operand count change.
   void setNumHungOffUseOperands(unsigned NumOps) {
     assert(HasHungOffUses && "Must have hung off uses to use this method");
     assert(NumOps < (1u << NumUserOperandsBits) && "Too many operands");
     NumUserOperands = NumOps;
   }
 
+  /// A droppable user is a user for which uses can be dropped without affecting
+  /// correctness and should be dropped rather than preventing a transformation
+  /// from happening.
+  bool isDroppable() const;
+
   // ---------------------------------------------------------------------------
   // Operand Iterator interface...
   //
   using op_iterator = Use*;
   using const_op_iterator = const Use*;
   using op_range = iterator_range<op_iterator>;
   using const_op_range = iterator_range<const_op_iterator>;
 

llvm/include/llvm/IR/Value.h

#endif
   /// Return true if this Value has exactly N users.
   bool hasNUses(unsigned N) const;
 
   /// Return true if this value has N users or more.
   ///
   /// This is logically equivalent to getNumUses() >= N.
   bool hasNUsesOrMore(unsigned N) const;
 
+  /// Return true if there is exactly one user of this value that cannot be
+  /// dropped.
+  ///
+  /// This is specialized because it is a common request and does not require
+  /// traversing the whole use list.
+  Use *getSingleUndroppableUse();
+
+  /// Return true if there this value.
+  ///
+  /// This is specialized because it is a common request and does not require
+  /// traversing the whole use list.
+  bool hasNUndroppableUses(unsigned N) const;
+
+  /// Return true if this value has N users or more.
+  ///
+  /// This is logically equivalent to getNumUses() >= N.
+  bool hasNUndroppableUsesOrMore(unsigned N) const;
+
+  /// Remove every uses that can safely be removed.
+  ///
+  /// This will remove for example uses in llvm.assume.
+  /// This should be used when performing want to perform a tranformation but
+  /// some Droppable uses pervent it.
+  /// This function optionally takes a filter to only remove some droppable
+  /// uses.
+  void dropDroppableUses(llvm::function_ref<bool(const Use *)> ShouldDrop =
+                             [](const Use *) { return true; });
+
   /// Check if this value is used in the specified basic block.
   bool isUsedInBasicBlock(const BasicBlock *BB) const;
 
   /// This method computes the number of uses of this Value.
   ///
   /// This is a linear time operation.  Use hasOneUse, hasNUses, or
   /// hasNUsesOrMore to check for specific values.
   unsigned getNumUses() const;

llvm/lib/IR/User.cpp

 //===-- User.cpp - Implement the User class -------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/User.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/GlobalValue.h"
+#include "llvm/IR/IntrinsicInst.h"
 
 namespace llvm {
 class BasicBlock;
 
 //===----------------------------------------------------------------------===//
 //                                 User Class
 //===----------------------------------------------------------------------===//
 
MutableArrayRef<uint8_t> User::getDescriptor() {
 
   auto *DI = reinterpret_cast<DescriptorInfo *>(getIntrusiveOperands()) - 1;
   assert(DI->SizeInBytes != 0 && "Should not have had a descriptor otherwise!");
 
   return MutableArrayRef<uint8_t>(
       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
 //===----------------------------------------------------------------------===//
 
 void *User::allocateFixedOperandUser(size_t Size, unsigned Us,
                                      unsigned DescBytes) {
   assert(Us < (1u << NumUserOperandsBits) && "Too many operands");
 

llvm/lib/IR/Value.cpp

 bool Value::hasNUses(unsigned N) const {
   return hasNItems(use_begin(), use_end(), N);
 }
 
 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) {
+    Value *V = U->get();
+    (void)V;
+    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, nullptr);
+    } else
+      llvm_unreachable("add special handeling here");
+    assert(V != U->get() && "the value should have been changed");
+    U->removeFromList();
+  }
+}
+
 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
   // usually one is quite short.
   //
   // Scan both lists simultaneously until one is exhausted. This limits the
   // search to the shorter list.
   BasicBlock::const_iterator BI = BB->begin(), BE = BB->end();