[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

156

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

public:
   /// the two LSBs regardless of pointer alignment on different targets.
   struct PrevPointerTraits {
     static inline void *getAsVoidPointer(Use **P) { return P; }
 
     static inline Use **getFromVoidPointer(void *P) {
       return (Use **)P;
     }
 
-    static constexpr int NumLowBitsAvailable = 2;
+    static constexpr int NumLowBitsAvailable = 3;
   };
 
 private:
   /// Destructor - Only for zap()
   ~Use() {
     if (Val)
       removeFromList();
   }
 
   enum PrevPtrTag { zeroDigitTag, oneDigitTag, stopTag, fullStopTag };
 
   /// Constructor
   Use(PrevPtrTag tag) { Prev.setInt(tag); }
 
+  static constexpr unsigned isDroppableMask = 1 << 2;
+
+#ifndef NDEBUG
+  bool checkDroppable() const;
+#endif
+  void setDroppable() {
+    Prev.setInt(Prev.getInt() | isDroppableMask);
+  }
+
 public:
   friend class Value;
+  friend class User;
+
+  bool isDroppable() const {
+    assert(checkDroppable() && "the use should be marked droppable");
+    return Prev.getInt() & isDroppableMask;
+  }
 
   operator Value *() const { return Val; }
   Value *get() const { return Val; }
 
   /// Returns the User that contains this Use.
   ///
   /// For an instruction operand, for example, this will return the
   /// instruction.
public:
 
   /// 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;
-  Use *Next = nullptr;
-  PointerIntPair<Use **, 2, PrevPtrTag, PrevPointerTraits> Prev;
+  /// This is aligned on 8 so that it allways have the 3 bottom bits
+  /// available.
+  alignas(8) Use *Next = nullptr;
+
+  /// The pointer point to the Use::Next of the previous node or the
+  /// Value::UseList of the associated value. *Prev.getPointer() is always the
+  /// a pointer to the use itself.
+  /// In the Int the 2 lowest bits are the Tag used for waymarking.
+  /// The third lowest bit is wether the use is droppable or not.
+  PointerIntPair<Use **, 3, unsigned, PrevPointerTraits> Prev;
 
   void setPrev(Use **NewPrev) { Prev.setPointer(NewPrev); }
+  PrevPtrTag getTag() const LLVM_READONLY {
+    return static_cast<PrevPtrTag>(Prev.getInt() & ~isDroppableMask);
+  }
 
   void addToList(Use **List) {
     Next = *List;
     if (Next)
       Next->setPrev(&Next);
     setPrev(List);
     *List = this;
   }

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

 /// Every value has a "use list" that keeps track of which other Values are
 /// using this Value.  A Value can also have an arbitrary number of ValueHandle
 /// objects that watch it and listen to RAUW and Destroy events.  See
 /// llvm/IR/ValueHandle.h for details.
 class Value {
   // The least-significant bit of the first word of Value *must* be zero:
   //   http://www.llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm
   Type *VTy;
-  Use *UseList;
+  /// This is aligned on 8 so that it allways have the 3 bottom bits
+  /// available.
+  alignas(8) Use *UseList;
 
   friend class ValueAsMetadata; // Allow access to IsUsedByMD.
   friend class ValueHandleBase;
 
   const unsigned char SubclassID;   // Subclass identifier (for isa/dyn_cast)
   unsigned char HasValueHandle : 1; // Has a ValueHandle pointing to this?
 
 protected:
#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.

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

User *Use::getUser() const {
   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 static_cast<bool>(Prev.getInt() & isDroppableMask) ==
+         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) {
void Use::zap(Use *Start, const Use *Stop, bool del) {
   if (del)
     ::operator delete(Start);
 }
 
 const Use *Use::getImpliedUser() const {
   const Use *Current = this;
 
   while (true) {
-    unsigned Tag = (Current++)->Prev.getInt();
+    unsigned Tag = (Current++)->getTag();
     switch (Tag) {
     case zeroDigitTag:
     case oneDigitTag:
       continue;
 
     case stopTag: {
       ++Current;
       ptrdiff_t Offset = 1;
       while (true) {
-        unsigned Tag = Current->Prev.getInt();
+        unsigned Tag = Current->getTag();
         switch (Tag) {
         case zeroDigitTag:
         case oneDigitTag:
           ++Current;
           Offset = (Offset << 1) + Tag;
           continue;
         default:
           return Current + Offset;

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)