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

185

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 ↗

(On Diff #241911)

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/docs/LangRef.rst

 to represent as a boolean argument of an :ref:`llvm.assume <int_assume>`.
 
 An assume operand bundle has the form:
 
 ::
 
       "<tag>"([ <holds for value> [, <attribute argument>] ])
 
-* The tag of the operand bundle is the name of attribute that can be assumed
-  to hold.
+* The tag of the operand bundle is usually the name of attribute that can be
+  assumed to hold. It can also be `ignore`, this tag doesn't contain any
+  information and should be ignored.
 * The first argument if present is the value for which the attribute hold.
 * The second argument if present is an argument of the attribute.
 
 If there are no arguments the attribute is a property of the call location.
 
 If the represented attribute expects a constant argument, the argument provided
 to the operand bundle should be a constant as well.
 

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/Analysis/KnowledgeRetention.cpp

bool llvm::hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn,
   assert(Attribute::isExistingAttribute(AttrName) &&
          "this attribute doesn't exist");
   assert((ArgVal == nullptr || Attribute::doesAttrKindHaveArgument(
                                    Attribute::getAttrKindFromName(AttrName))) &&
          "requested value for an attribute that has no argument");
   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);
-    }
-  }
-
-  if (Lookup->End - Lookup->Begin < BOIE_Argument)
-    return true;
-  if (ArgVal)
+  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, *Lookup, BOIE_Argument))
+                      getValueFromBundleOpInfo(Assume, BOI, BOIE_Argument))
                       ->getZExtValue();
+      }
       return true;
     }
+    return false;
+  };
+
+  if (AQR == AssumeQuery::Lowest)
+    return Loop(Assume.bundle_op_infos());
+  return Loop(reverse(Assume.bundle_op_infos()));
+}
 
 void llvm::fillMapFromAssume(CallInst &AssumeCI, RetainedKnowledgeMap &Result) {
   IntrinsicInst &Assume = cast<IntrinsicInst>(AssumeCI);
   assert(Assume.getIntrinsicID() == Intrinsic::assume &&
          "this function is intended to be used on llvm.assume");
   for (auto &Bundles : Assume.bundle_op_infos()) {
     std::pair<Value *, Attribute::AttrKind> Key{
         nullptr, Attribute::getAttrKindFromName(Bundles.Tag->getKey())};

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) {
+    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
   // 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();

llvm/lib/IR/Verifier.cpp

for (Value *V : Call.args())
     if (auto *MD = dyn_cast<MetadataAsValue>(V))
       visitMetadataAsValue(*MD, Call.getCaller());
 
   switch (ID) {
   default:
     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 =
           Attribute::getAttrKindFromName(Elem.Tag->getKey());
       if (Kind == Attribute::None)
         break;
       if (Attribute::doesAttrKindHaveArgument(Kind)) {
         Assert(Elem.End - Elem.Begin == 2,

llvm/unittests/Analysis/KnowledgeRetentionTest.cpp

 using namespace llvm;
 
 extern cl::opt<bool> ShouldPreserveAllAttributes;
 
 static void RunTest(
     StringRef Head, StringRef Tail,
     std::vector<std::pair<StringRef, llvm::function_ref<void(Instruction *)>>>
         &Tests) {
+  for (auto &Elem : Tests) {
     std::string IR;
     IR.append(Head.begin(), Head.end());
-  for (auto &Elem : Tests)
     IR.append(Elem.first.begin(), Elem.first.end());
     IR.append(Tail.begin(), Tail.end());
     LLVMContext C;
     SMDiagnostic Err;
     std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
     if (!Mod)
       Err.print("AssumeQueryAPI", errs());
-  unsigned Idx = 0;
-  for (Instruction &I : (*Mod->getFunction("test")->begin())) {
-    if (Idx < Tests.size())
-      Tests[Idx].second(&I);
-    Idx++;
+    Elem.second(&*(Mod->getFunction("test")->begin()->begin()));
   }
 }
 
 static void AssertMatchesExactlyAttributes(CallInst *Assume, Value *WasOn,
                                     StringRef AttrToMatch) {
   Regex Reg(AttrToMatch);
   SmallVector<StringRef, 1> Matches;
   for (StringRef Attr : {
Tests.push_back(std::make_pair(
         AssertHasTheRightValue(Assume, I->getOperand(2),
                                Attribute::AttrKind::Dereferenceable, 4, true);
         AssertHasTheRightValue(Assume, I->getOperand(3),
                                Attribute::AttrKind::Alignment, 16, true);
         AssertHasTheRightValue(Assume, I->getOperand(3),
                                Attribute::AttrKind::Dereferenceable, 12, true);
       }));
 
-  /// Keep this test last as it modifies the function.
+  Tests.push_back(std::make_pair(
+      "call void @func1(i32* readnone align 32 "
+      "dereferenceable(48) noalias %P, i32* "
+      "align 8 dereferenceable(28) %P1, i32* align 64 "
+      "dereferenceable(4) "
+      "%P2, i32* nonnull align 16 dereferenceable(12) %P3)\n",
+      [](Instruction *I) {
+        CallInst *Assume = BuildAssumeFromInst(I);
+        Assume->insertBefore(I);
+        I->getOperand(1)->dropDroppableUses();
+        I->getOperand(2)->dropDroppableUses();
+        I->getOperand(3)->dropDroppableUses();
+        AssertMatchesExactlyAttributes(
+            Assume, I->getOperand(0),
+            "(readnone|align|dereferenceable|noalias)");
+        AssertMatchesExactlyAttributes(Assume, I->getOperand(1),
+                                       "");
+        AssertMatchesExactlyAttributes(Assume, I->getOperand(2),
+                                       "");
+        AssertMatchesExactlyAttributes(Assume, I->getOperand(3),
+                                       "");
+        AssertHasTheRightValue(Assume, I->getOperand(0),
+                               Attribute::AttrKind::Alignment, 32, true);
+        AssertHasTheRightValue(Assume, I->getOperand(0),
+                               Attribute::AttrKind::Dereferenceable, 48, true);
+      }));
   Tests.push_back(std::make_pair(
       "call void @func(i32* nonnull align 4 dereferenceable(16) %P, i32* align "
       "8 noalias %P1)\n",
       [](Instruction *I) {
         CallInst *Assume = BuildAssumeFromInst(I);
         Assume->insertBefore(I);
         Value *New = I->getFunction()->getArg(3);
         Value *Old = I->getOperand(0);