[IR] Put the Use list waymarking bits in the bit positions documentation says they are using

[craig.topper]

Summary

The documentation for the waymarking algorithm says that we use the lower 2 bits of Use::Prev to store the way marking bits. But because we use a PointerIntPair with the default PointerLikeTypeTraits, we're using bits 2:1 on 64-bit targets.

There's also a trick employed for distinguishing Users that have Uses stored with them and Users that have Uses stored in a separate array. The documentation says we use the LSB of the first byte of the real User object or the User* that occurs at the end of the Use array. But again due to the PointerLikeTypeTraits we're really using bit 2(64-bit) or bit 1(32-bit) and not the LSB. This is a little worrying because the first byte of the User object is the vtable ptr so we're assuming the vtable has 8 byte or 4 byte alignment where what is documented would only require 2 byte alignment.

This patch provides a custom traits override for these two cases to put the bits where the documentation says they are. It also has the side effect of removing some shifts from the waymarking traversal implementation.

[mehdi_amini]

include/llvm/IR/Use.h

64

I'd document the motivation for the traits (i.e. for using the LSB independently of the platform IIUC).

77

same here :)

[craig.topper]

Add additional comments.

[craig.topper]

Ping

[rnk]

lgtm

include/llvm/IR/Use.h

 class Use {
 public:
   Use(const Use &U) = delete;
 
   /// \brief Provide a fast substitute to std::swap<Use>
   /// that also works with less standard-compliant compilers
   void swap(Use &RHS);
 
+  /// Pointer traits for the UserRef PointerIntPair.
+  struct UserRefPointerTraits {
+    static inline void *getAsVoidPointer(User *P) { return P; }
+    static inline User *getFromVoidPointer(void *P) {
+      return (User *)P;
+    }
+    enum { NumLowBitsAvailable = 1 };
+  };
+
   // A type for the word following an array of hung-off Uses in memory, which is
   // a pointer back to their User with the bottom bit set.
-  typedef PointerIntPair<User *, 1, unsigned> UserRef;
+  typedef PointerIntPair<User *, 1, unsigned, UserRefPointerTraits> UserRef;
+
+  /// Pointer traits for the Prev PointerIntPair.
+  struct PrevPointerTraits {
+    static inline void *getAsVoidPointer(Use **P) { return P; }
+    static inline Use **getFromVoidPointer(void *P) {
+      return (Use **)P;
+    }
+    enum { NumLowBitsAvailable = 2 };
+  };
 
 private:
   /// Destructor - Only for zap()
   ~Use() {
     if (Val)
       removeFromList();
   }
 
public:
   /// a User changes.
   static void zap(Use *Start, const Use *Stop, bool del = false);
 
 private:
   const Use *getImpliedUser() const LLVM_READONLY;
 
   Value *Val;
   Use *Next;
-  PointerIntPair<Use **, 2, PrevPtrTag> Prev;
+  PointerIntPair<Use **, 2, PrevPtrTag, PrevPointerTraits> Prev;
 
   void setPrev(Use **NewPrev) { Prev.setPointer(NewPrev); }
 
   void addToList(Use **List) {
     Next = *List;
     if (Next)
       Next->setPrev(&Next);
     setPrev(List);