[NFC] Improve performances of Value::getSingleUndroppableUse

[Tyker]

Summary

since f1a9efabcb9bc37b663b0e03ed3d5a5aa7cc055e,
Value::getSingleUndroppableUse is used in the hot path of InstCombine.

[Tyker]

i was not able to get reliable time measurement for a whole compiler run.
but in a profiler this patched replaced a +0.16% cycles in Use::getUser() and +0.08% time in getSingleUndroppableUse for a +0.06% cycles in InstCombiner::run.

[jdoerfert]

llvm/include/llvm/IR/Use.h

152

There is a comment needed here explaining what this encodes.

[nikic]

I'm seeing a 0.1-0.2% regression with this change. Probably the added cost of the pointer tagging outweighs the benefit we see for the single user of getSingleUndroppableUse() right now. If this API is going to be used more heavily in the future, the picture will of course change. Hard for me to say whether it makes sense to make this change at this time.

I do wonder whether there's a middle ground here: Rather than adding a tag to Use, we could use a bit of subclass data on CallInst to indicate whether the call is droppable. That would reduce User->isDroppable() to a compare and mask check, and we could at least inline it.

llvm/include/llvm/IR/User.h

227

This sentence is cut off.

[jdoerfert]

I'm also not sure about changing Use, @nikic suggestion with marking it in the callinst sounds interesting.

[Tyker]

In D76923#1946433, @nikic wrote:

I do wonder whether there's a middle ground here: Rather than adding a tag to Use, we could use a bit of subclass data on CallInst to indicate whether the call is droppable. That would reduce User->isDroppable() to a compare and mask check, and we could at least inline it.

from profiling i saw that most of the cost of getSingleUndroppableUse comes from Use::getUser (+0.16%) and not from User::isDroppable (+0.05%). so i don't think this would make the difference we want.

with this revision i moved the tag to the Prev pointer because it is accessed much less than Val and it already has a tag so i just added a bit to the tag.
maybe this revision has less overhead.

by the way the compiler seems to be consistantly spending more than 1% of its cycle in Use::getUser. and i am wondering if way-marking is worth the memory saving.

[nikic]

In D76923#1947854, @Tyker wrote:

In D76923#1946433, @nikic wrote:

I do wonder whether there's a middle ground here: Rather than adding a tag to Use, we could use a bit of subclass data on CallInst to indicate whether the call is droppable. That would reduce User->isDroppable() to a compare and mask check, and we could at least inline it.

from profiling i saw that most of the cost of getSingleUndroppableUse comes from Use::getUser (+0.16%) and not from User::isDroppable (+0.05%). so i don't think this would make the difference we want.

with this revision i moved the tag to the Prev pointer because it is accessed much less than Val and it already has a tag so i just added a bit to the tag.
maybe this revision has less overhead.

Indeed, I'm seeing a 0.1% improvement with this version, which is about the size of the original regression.

It's not clear to me that this is actually safe though. On 32-bit platforms, wouldn't Use only be 4-aligned? Or does LLVM use a special allocator that provides stronger alignment guarantees?

[Tyker]

In D76923#1947948, @nikic wrote:

In D76923#1947854, @Tyker wrote:

In D76923#1946433, @nikic wrote:

I do wonder whether there's a middle ground here: Rather than adding a tag to Use, we could use a bit of subclass data on CallInst to indicate whether the call is droppable. That would reduce User->isDroppable() to a compare and mask check, and we could at least inline it.

from profiling i saw that most of the cost of getSingleUndroppableUse comes from Use::getUser (+0.16%) and not from User::isDroppable (+0.05%). so i don't think this would make the difference we want.

with this revision i moved the tag to the Prev pointer because it is accessed much less than Val and it already has a tag so i just added a bit to the tag.
maybe this revision has less overhead.

Indeed, I'm seeing a 0.1% improvement with this version, which is about the size of the original regression.

It's not clear to me that this is actually safe though. On 32-bit platforms, wouldn't Use only be 4-aligned? Or does LLVM use a special allocator that provides stronger alignment guarantees?

i don't think its safe either for 32-bits systems. we could over align Use to 8 to fix this for 32-bit without affecting 64-bit ?

[Tyker]

overalined the 2 fields the Use::Prev can point to.

[Tyker]

since D77144 has landed i don't think this is needed anymore

llvm/include/llvm/IR/Use.h

struct PrevPointerTraits {
     }
 
     static constexpr int NumLowBitsAvailable = 2;
   };
 
 private:
   /// Destructor - Only for zap()
   ~Use() {
-    if (Val)
+    if (Val.getPointer())
       removeFromList();
   }
 
   enum PrevPtrTag { zeroDigitTag, oneDigitTag, stopTag, fullStopTag };
 
   /// Constructor
   Use(PrevPtrTag tag) { Prev.setInt(tag); }
 
+#ifndef NDEBUG
+  bool checkDroppable() const;
+#endif
+  void setDroppable(bool NewVal = true) { Val.setInt(NewVal); }
+
 public:
   friend class Value;
+  friend class User;
+
+  bool isDroppable() const {
+    assert(checkDroppable() && "the use should be marked droppable");
+    return Val.getInt();
+  }
 
-  operator Value *() const { return Val; }
-  Value *get() const { return Val; }
+  operator Value *() const { return Val.getPointer(); }
+  Value *get() const { return Val.getPointer(); }
 
   /// Returns the User that contains this Use.
   ///
   /// For an instruction operand, for example, this will return the
   /// instruction.
   User *getUser() const LLVM_READONLY;
 
   inline void set(Value *Val);
 
   inline Value *operator=(Value *RHS);
   inline const Use &operator=(const Use &RHS);
 
-  Value *operator->() { return Val; }
-  const Value *operator->() const { return Val; }
+  Value *operator->() { return Val.getPointer(); }
+  const Value *operator->() const { return Val.getPointer(); }
 
   Use *getNext() const { return Next; }
 
   /// Return the operand # of this use in its User.
   unsigned getOperandNo() const;
 
   /// Initializes the waymarking tags on an array of Uses.
   ///
   /// This sets up the array of Uses such that getUser() can find the User from
   /// any of those Uses.
   static Use *initTags(Use *Start, Use *Stop);
 
   /// Destroys Use operands when the number of operands of
   /// a User changes.
   static void zap(Use *Start, const Use *Stop, bool del = false);
 
 private:
   const Use *getImpliedUser() const LLVM_READONLY;
 
-  Value *Val = nullptr;
+  PointerIntPair<Value *, 1> Val = {nullptr, 0};
   Use *Next = nullptr;
   PointerIntPair<Use **, 2, PrevPtrTag, PrevPointerTraits> Prev;
 
   void setPrev(Use **NewPrev) { Prev.setPointer(NewPrev); }
 
   void addToList(Use **List) {
     Next = *List;
     if (Next)

llvm/include/llvm/IR/User.h

void setNumHungOffUseOperands(unsigned NumOps) {
     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;
 
+  /// This will mark every use as droppable if the user is droppable.
+  /// This should be called from 
+  void maybeMarkUsesAsDroppable();
+
   // ---------------------------------------------------------------------------
   // 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
   /// 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();
+  Use *getSingleUndroppableUse() {
+    Use *Result = nullptr;
+    for (Use &U : uses()) {
+      if (!U.isDroppable()) {
+        if (Result)
+          return nullptr;
+        Result = &U;
+      }
+    }
+    return Result;
+  }
 
   /// 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.

 using unique_value = std::unique_ptr<Value, ValueDeleter>;
 
 inline raw_ostream &operator<<(raw_ostream &OS, const Value &V) {
   V.print(OS);
   return OS;
 }
 
 void Use::set(Value *V) {
-  if (Val) removeFromList();
-  Val = V;
+  if (Val.getPointer())
+    removeFromList();
+  Val.setPointer(V);
   if (V) V->addUse(*this);
 }
 
 Value *Use::operator=(Value *RHS) {
   set(RHS);
   return RHS;
 }
 
 const Use &Use::operator=(const Use &RHS) {
-  set(RHS.Val);
+  set(RHS.Val.getPointer());
   return *this;
 }
 
 template <class Compare> void Value::sortUseList(Compare Cmp) {
   if (!UseList || !UseList->Next)
     // No need to sort 0 or 1 uses.
     return;
 

llvm/lib/IR/Instructions.cpp

#endif
 
   llvm::copy(Args, op_begin());
 
   auto It = populateBundleOperandInfos(Bundles, Args.size());
   (void)It;
   assert(It + 1 == op_end() && "Should add up!");
 
   setName(NameStr);
+  maybeMarkUsesAsDroppable();
 }
 
 void CallInst::init(FunctionType *FTy, Value *Func, const Twine &NameStr) {
   this->FTy = FTy;
   assert(getNumOperands() == 1 && "NumOperands not set up?");
   setCalledOperand(Func);
 
   assert(FTy->getNumParams() == 0 && "Calling a function with bad signature");
 
   setName(NameStr);
+  maybeMarkUsesAsDroppable();
 }
 
 CallInst::CallInst(FunctionType *Ty, Value *Func, const Twine &Name,
                    Instruction *InsertBefore)
     : CallBase(Ty->getReturnType(), Instruction::Call,
                OperandTraits<CallBase>::op_end(this) - 1, 1, InsertBefore) {
   init(Ty, Func, Name);
 }

llvm/lib/IR/Use.cpp

 #include <new>
 
 namespace llvm {
 
 void Use::swap(Use &RHS) {
   if (Val == RHS.Val)
     return;
 
-  if (Val)
+  if (Val.getPointer())
     removeFromList();
 
-  Value *OldVal = Val;
-  if (RHS.Val) {
+  Value *OldVal = Val.getPointer();
+  if (RHS.Val.getPointer()) {
     RHS.removeFromList();
-    Val = RHS.Val;
-    Val->addUse(*this);
+    Val.setPointer(RHS.Val.getPointer());
+    Val.getPointer()->addUse(*this);
   } else {
-    Val = nullptr;
+    Val.setPointer(nullptr);
   }
 
   if (OldVal) {
-    RHS.Val = OldVal;
-    RHS.Val->addUse(RHS);
+    RHS.Val.setPointer(OldVal);
+    RHS.Val.getPointer()->addUse(RHS);
   } else {
-    RHS.Val = nullptr;
+    RHS.Val.setPointer(nullptr);
   }
 }
 
 User *Use::getUser() const {
   const Use *End = getImpliedUser();
   const UserRef *ref = reinterpret_cast<const UserRef *>(End);
   return ref->getInt() ? ref->getPointer()
                        : reinterpret_cast<User *>(const_cast<Use *>(End));
 }
 
 unsigned Use::getOperandNo() const {
   return this - getUser()->op_begin();
 }
 
+#ifndef NDEBUG
+bool Use::checkDroppable() const {
+  return Val.getInt() == getUser()->isDroppable();
+}
+#endif
+
 // Sets up the waymarking algorithm's tags for a series of Uses. See the
 // algorithm details here:
 //
 //   http://www.llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm
 //
 Use *Use::initTags(Use *const Start, Use *Stop) {
   ptrdiff_t Done = 0;
   while (Done < 20) {

llvm/lib/IR/User.cpp

MutableArrayRef<uint8_t> User::getDescriptor() {
 
   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;
+  /// If you are changing this definition you may need to add calls to
+  /// maybeMarkUsesAsDroppable in some subclasses
   return false;
 }
 
+void User::maybeMarkUsesAsDroppable() {
+  if (!isDroppable())
+    return;
+  for (unsigned i = 0; i < getNumOperands(); i++)
+    getOperandUse(i).setDroppable();
+}
+
 //===----------------------------------------------------------------------===//
 //                         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;
-}
+static bool isUnDroppableUse(const Use& U) { return !U.isDroppable(); }
 
 bool Value::hasNUndroppableUses(unsigned int N) const {
-  return hasNItems(user_begin(), user_end(), N, isUnDroppableUser);
+  return hasNItems(use_begin(), use_end(), N, isUnDroppableUse);
 }
 
 bool Value::hasNUndroppableUsesOrMore(unsigned int N) const {
-  return hasNItemsOrMore(user_begin(), user_end(), N, isUnDroppableUser);
+  return hasNItemsOrMore(use_begin(), use_end(), N, isUnDroppableUse);
 }
 
 void Value::dropDroppableUses(
     llvm::function_ref<bool(const Use *)> ShouldDrop) {
   SmallVector<Use *, 8> ToBeEdited;
   for (Use &U : uses())
-    if (U.getUser()->isDroppable() && ShouldDrop(&U))
+    if (U.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()));

llvm/lib/Transforms/IPO/Attributor.cpp

struct AACaptureUseTracker final : public CaptureTracker {
   /// Register \p CS as potential copy of the value we are checking.
   void addPotentialCopy(CallSite CS) {
     PotentialCopies.push_back(CS.getInstruction());
   }
 
   /// See CaptureTracker::shouldExplore(...).
   bool shouldExplore(const Use *U) override {
     // Check liveness and ignore droppable users.
-    return !U->getUser()->isDroppable() &&
-           !A.isAssumedDead(*U, &NoCaptureAA, &IsDeadAA);
+    return !U->isDroppable() && !A.isAssumedDead(*U, &NoCaptureAA, &IsDeadAA);
   }
 
   /// Update the state according to \p CapturedInMem, \p CapturedInInt, and
   /// \p CapturedInRet, then return the appropriate value for use in the
   /// CaptureTracker::captured() interface.
   bool isCapturedIn(bool CapturedInMem, bool CapturedInInt,
                     bool CapturedInRet) {
     LLVM_DEBUG(dbgs() << " - captures [Mem " << CapturedInMem << "|Int "
if (!Visited.insert(U).second)
       continue;
     LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << **U << " in "
                       << *U->getUser() << "\n");
     if (isAssumedDead(*U, &QueryingAA, LivenessAA,
                       /* CheckBBLivenessOnly */ false, LivenessDepClass)) {
       LLVM_DEBUG(dbgs() << "[Attributor] Dead use, skip!\n");
       continue;
     }
-    if (U->getUser()->isDroppable()) {
+    if (U->isDroppable()) {
       LLVM_DEBUG(dbgs() << "[Attributor] Droppable user, skip!\n");
       continue;
     }
 
     bool Follow = false;
     if (!Pred(*U, Follow))
       return false;
     if (!Follow)