Implement the Waymarking as an independent utility

[ekatz]

Summary

This is an implementation that I am using for quite some time, for a personal project. Its need came from the requirement to use the algorithm for other purposes than the "Use" class.
I thought it could benefit others as well.
In any case, such a general algorithm deserves to be in the ADT library and not embedded into a specific usage. This way we also separate those logics from the Use class.

• This is an improved version of the waymarking algorithm currently present - which combines the STOP flag with the Offset's digits. Further explanation available in the header file.

[ekatz]

Ping

[craig.topper]

http://llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm would need to be updated too.

[ekatz]

In D69332#1732725, @craig.topper wrote:

http://llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm would need to be updated too.

Yes. Not sure how do I do that.
Is it enough to change "llvm/docs/ProgrammersManual.rst"?

[craig.topper]

In D69332#1732766, @ekatz wrote:

In D69332#1732725, @craig.topper wrote:

http://llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm would need to be updated too.

Yes. Not sure how do I do that.
Is it enough to change "llvm/docs/ProgrammersManual.rst"?

That should do it.

[mehdi_amini]

llvm/include/llvm/ADT/Waymarking.h

233

Can you improve the documentation of every public API in the file? If possible including usage example when appropriate. Thanks!

[ekatz]

• Improved documentation.
• Fixed Programmer's Manual.
• Added unit tests.

[ekatz]

Ping

[craig.topper]

Improving the algorithm and separating the algorithm from Use should probably be two different patches.

[ekatz]

In D69332#1752868, @craig.topper wrote:

Improving the algorithm and separating the algorithm from Use should probably be two different patches.

The improved algorithm is embedded in the solution of repurposing the waymarking algorithm into an independent utility. There is no middle stage, where I separate the old algorithm from Use.

[foad]

I agree with @craig.topper that improving the algorithm and separating the algorithm from Use should be two different patches. Personally I am much more interested in the former than the latter.

Have you seen bug 6809 and read this thread: http://lists.llvm.org/pipermail/llvm-dev/2014-April/072326.html ?

Have you done any kind of profiling or measurement of your improved algorithm?

llvm/docs/ProgrammersManual.rst

3157 ↗

(On Diff #228958)

These diagrams are always confusing to read. I think it would be better to put numbers like -7 to the right of the vertical line instead of to the left; at the moment "-7" is underneath the binary encoding for 4, which is confusing. Also I think the vertical line for -14 is too far to the right.

[ekatz]

llvm/docs/ProgrammersManual.rst

3157 ↗

(On Diff #228958)

I see what you mean. I'll change them, and fix -14.

[ekatz]

In D69332#1753407, @foad wrote:

I agree with @craig.topper that improving the algorithm and separating the algorithm from Use should be two different patches. Personally I am much more interested in the former than the latter.

Have you seen bug 6809 and read this thread: http://lists.llvm.org/pipermail/llvm-dev/2014-April/072326.html ?

Have you done any kind of profiling or measurement of your improved algorithm?

How do you and @craig.topper suggest I should separate it into 2 patches?
As I've explained, I can't separate the improvement of the algorithm from the one in the patch. I would have to re-design, re-write, re-test everything.
The only thing I can think of, is separate it into 2 patches: 1 for the utility, and 1 for changing Use, to use the utility. I can do that, but, correct me if I'm wrong, that is not what you suggested.

Regarding PR6809, I've seen it, and read everything regarding all the suggestions (including others) for improving the Waymarking algorithm.
I am not certain that my algorithm is better than the ones suggested (although it may be, or even about the same). What drove me into my improvement is just the dangling bit of the STOP tag, which could be used with the bits data, and not have to be alone (seemed like a waste).
Regarding the improvement of the number of bits used (for 64-bit), that was actually asked for a very long time, but in any case I wanted to generalize it (using templates) for any number of bits, and any location they may be in any type of data (not only pointer).

I do not think we get much (if any) REAL performance improvement (I tested), but only THEORETICAL improvement; but as explained above, this is not the reason for change. At least we don't get a slow down. ;)

The solution I propose is the one I am using on my personal project. I work with it for more than a year, now. Just thought to share it (plus - I added tests and updated the docs as needed).

[foad]

In D69332#1753682, @ekatz wrote:

How do you and @craig.topper suggest I should separate it into 2 patches?
As I've explained, I can't separate the improvement of the algorithm from the one in the patch. I would have to re-design, re-write, re-test everything.

Yes I am suggesting (not insisting) that you re-write and re-test the patch. Sorry if that seems like a lot of work, but I don't think it's unreasonable. As the contributing guide says: Independent changes should be submitted as separate patches as this makes reviewing easier.

The solution I propose is the one I am using on my personal project. I work with it for more than a year, now. Just thought to share it (plus - I added tests and updated the docs as needed).

I appreciate that.

[ekatz]

I see why you suggest it, but what are the options available? Should I do this large change or drop it?
@lattner, may I have a second opinion? I know MLIR and SWIFT may benefit from it too, if they decide to use the utility.

[ekatz]

Separate into 2 different patches.

llvm/include/llvm/ADT/Waymarking.h

+//===- Waymarking.h - Array waymarking algorithm ----------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Utility to backtrace an array's head, from a pointer into it. For the
+// backtrace to work, we use "Waymarks", which are special tags embedded into
+// the array's elements.
+//
+// A Tag of n-bits (in size) is composed as follows:
+//
+// bits: |   n-1   |             n-2 ... 0              |
+//       .---------.------------------------------------.
+//       |Stop Mask|(2^(n-1))-ary numeric system - digit|
+//       '---------'------------------------------------'
+//
+// Backtracing is done as follows:
+// Walk back (starting from a given pointer to an element into the array), until
+// a tag with a "Stop Mask" is reached. Then start calculating the "Offset" from
+// the array's head, by picking up digits along the way, until another stop is
+// reached. The "Offset" is then subtracted from the current pointer, and the
+// result is the array's head.
+// A special case - if we first encounter a Tag with a Stop and a zero digit,
+// then this is already the head.
+//
+// For example:
+// In case of 2 bits:
+//
+// Tags:
+// x0 - binary digit 0
+// x1 - binary digit 1
+// 1x - stop and calculate (s)
+//
+// Array:
+//         .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.
+// head -> |s0 |s1 | 0 |s1 | 0 | 0 |s1 | 1 | 1 |s1 | 0 | 1 | 0 |s1 | 0 | 1 |
+//         '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'
+//           -1| -2|     -4|         -7|        -10|                -14|
+//          <_ |   |       |           |           |                   |
+//          <_____ |       |           |           |                   |
+//          <_____________ |           |           |                   |
+//          <_________________________ |           |                   |
+//          <_____________________________________ |                   |
+//          <_________________________________________________________ |
+//
+//
+// In case of 3 bits:
+//
+// Tags:
+// x00 - quaternary digit 0
+// x01 - quaternary digit 1
+// x10 - quaternary digit 2
+// x11 - quaternary digit 3
+// 1xy - stop and calculate (s)
+//
+// Array:
+//         .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.
+// head -> |s0 |s1 |s2 |s3 | 0 |s1 | 2 |s1 | 0 |s2 | 2 |s2 | 0 |s3 | 2 |s3 |
+//         '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'
+//           -1| -2| -3| -4|     -6|     -8|    -10|    -12|    -14|    -16|
+//          <_ |   |   |   |       |       |       |       |       |       |
+//          <_____ |   |   |       |       |       |       |       |       |
+//          <_________ |   |       |       |       |       |       |       |
+//          <_____________ |       |       |       |       |       |       |
+//          <_____________________ |       |       |       |       |       |
+//          <_____________________________ |       |       |       |       |
+//          <_____________________________________ |       |       |       |
+//          <_____________________________________________ |       |       |
+//          <_____________________________________________________ |       |
+//          <_____________________________________________________________ |
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_WAYMARKING_H
+#define LLVM_ADT_WAYMARKING_H
+
+#include "llvm/ADT/STLExtras.h"
+
+namespace llvm {
+
+namespace detail {
+
+template <unsigned NumBits> struct WaymarkingTraits {
+  enum : unsigned {
+    NUM_BITS = NumBits,
+
+    MARK_SIZE = NUM_BITS - 1,
+    STOP_MASK = (1 << MARK_SIZE),
+    MARK_MASK = (STOP_MASK - 1),
+    TAG_MASK = (MARK_MASK | STOP_MASK),
+
+    NUM_STATIC_TAGS = 32
+  };
+
+private:
+  template <unsigned Len, bool Stop, unsigned Count, uint8_t... Vals>
+  struct AddTag;
+
+  template <unsigned Len, unsigned Count, uint8_t... Vals> struct GenTag {
+    typedef
+        typename AddTag<Len, (Count <= MARK_MASK), Count, Vals...>::Xdata Xdata;
+  };
+
+  template <unsigned Len, uint8_t... Vals> struct GenOffset {
+    typedef typename GenTag<Len, sizeof...(Vals), Vals...>::Xdata Xdata;
+  };
+
+  template <unsigned Len, unsigned Count, uint8_t... Vals>
+  struct AddTag<Len, false, Count, Vals...> {
+    typedef typename GenTag<Len - 1, (Count >> MARK_SIZE), Vals...,
+                            Count & MARK_MASK>::Xdata Xdata;
+  };
+
+  template <unsigned Len, unsigned Count, uint8_t... Vals>
+  struct AddTag<Len, true, Count, Vals...> {
+    typedef typename GenOffset<Len - 1, Vals...,
+                               (Count & MARK_MASK) | STOP_MASK>::Xdata Xdata;
+  };
+
+  template <unsigned Count, uint8_t... Vals> struct TagsData {
+    static const unsigned Remain = Count;
+    static const uint8_t Values[sizeof...(Vals)];
+  };
+
+  template <unsigned Count, uint8_t... Vals>
+  struct AddTag<0, false, Count, Vals...> {
+    typedef typename TagsData<Count, Vals...> Xdata;
+  };
+
+  template <unsigned Count, uint8_t... Vals>
+  struct AddTag<0, true, Count, Vals...> {
+    typedef typename TagsData<Count, Vals...> Xdata;
+  };
+
+public:
+  typedef typename GenOffset<NUM_STATIC_TAGS>::Xdata Tags;
+};
+
+template <unsigned NumBits>
+template <unsigned Count, uint8_t... Vals>
+const uint8_t WaymarkingTraits<NumBits>::TagsData<
+    Count, Vals...>::Values[sizeof...(Vals)] = {Vals...};
+
+} // end namespace detail
+
+template <class T, class WTraits = detail::WaymarkingTraits<
+                       PointerLikeTypeTraits<T>::NumLowBitsAvailable>>
+struct Waymarker {
+  using Traits = WTraits;
+  static void setWaymark(T &N, unsigned Tag) { N.setWaymark(Tag); }
+  static unsigned getWaymark(const T &N) { return N.getWaymark(); }
+};
+
+template <class T, class WTraits> struct Waymarker<T *, WTraits> {
+  using Traits = WTraits;
+  static void setWaymark(T *&N, unsigned Tag) {
+    reinterpret_cast<uintptr_t &>(N) |= static_cast<uintptr_t>(Tag);
+  }
+  static unsigned getWaymark(const T *N) {
+    return static_cast<unsigned>(reinterpret_cast<uintptr_t>(N)) &
+           Traits::TAG_MASK;
+  }
+};
+
+/// Sets up the waymarking algorithm's tags for a given range.
+template <class TIter, class Marker = Waymarker<
+                           typename std::iterator_traits<TIter>::value_type>>
+void fillWaymarks(TIter Begin, TIter End, size_t Offset = 0) {
+  assert(Offset <= Marker::Traits::NUM_STATIC_TAGS);
+
+  while (true) {
+    if (!(Begin < End))
+      return;
+
+    if (Offset >= Marker::Traits::NUM_STATIC_TAGS)
+      break;
+
+    Marker::setWaymark(*Begin, Marker::Traits::Tags::Values[Offset++]);
+    ++Begin;
+  }
+
+  size_t Count = Marker::Traits::Tags::Remain;
+  do {
+    ++Offset;
+
+    unsigned Tag = Count & Marker::Traits::MARK_MASK;
+
+    // If the count can fit into the tag, then the counting must stop.
+    if (Count <= Marker::Traits::MARK_MASK) {
+      Tag |= Marker::Traits::STOP_MASK;
+      Count = Offset;
+    } else
+      Count >>= Marker::Traits::MARK_SIZE;
+
+    Marker::setWaymark(*Begin, Tag);
+    ++Begin;
+  } while (Begin < End);
+}
+
+/// Sets up the waymarking algorithm's tags for a given range.
+template <typename R, class Marker = Waymarker<detail::ValueOfRange<R>>>
+void fillWaymarks(R &&Range, size_t Offset = 0) {
+  return fillWaymarks<detail::IterOfRange<R>, Marker>(adl_begin(Range),
+                                                      adl_end(Range), Offset);
+}
+
+/// Retrieves the owning array's head, by following the waymarks.
+template <class TIter, class Marker = Waymarker<
+                           typename std::iterator_traits<TIter>::value_type>>
+TIter followWaymarks(TIter I) {
+  unsigned Tag;
+  do
+    Tag = Marker::getWaymark(*I--);
+  while (!(Tag & Marker::Traits::STOP_MASK));
+
+  // Special case for the first Use.
+  if (Tag != Marker::Traits::STOP_MASK) {
+    ptrdiff_t Offset = Tag & Marker::Traits::MARK_MASK;
+    while (!((Tag = Marker::getWaymark(*I)) & Marker::Traits::STOP_MASK)) {
+      Offset = (Offset << Marker::Traits::MARK_SIZE) + Tag;
+      --I;
+    }
+    I -= Offset;
+  }
+  return ++I;
+}
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_WAYMARKING_H

llvm/include/llvm/IR/Use.h

 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_USE_H
 #define LLVM_IR_USE_H
 
 #include "llvm-c/Types.h"
 #include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/Waymarking.h"
 #include "llvm/Support/CBindingWrapping.h"
 #include "llvm/Support/Compiler.h"
 
 namespace llvm {
 
 template <typename> struct simplify_type;
 class User;
 class Value;
struct UserRefPointerTraits {
 
     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.
   using UserRef = PointerIntPair<User *, 1, unsigned, UserRefPointerTraits>;
 
-  /// Pointer traits for the Prev PointerIntPair. This ensures we always use
-  /// 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;
-    }
-
-    enum { NumLowBitsAvailable = 2 };
-  };
-
 private:
   /// Destructor - Only for zap()
   ~Use() {
     if (Val)
       removeFromList();
   }
 
-  enum PrevPtrTag { zeroDigitTag, oneDigitTag, stopTag, fullStopTag };
-
   /// Constructor
-  Use(PrevPtrTag tag) { Prev.setInt(tag); }
+  Use(unsigned tag) { Prev.setInt(tag); }
 
 public:
   friend class Value;
 
   operator Value *() const { return Val; }
   Value *get() const { return Val; }
 
   /// Returns the User that contains this Use.
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;
 
+  using Waymarker =
+      llvm::Waymarker<Use, detail::WaymarkingTraits<PointerLikeTypeTraits<
+                               Use **>::NumLowBitsAvailable>>;
+  friend Waymarker;
+
   Value *Val = nullptr;
   Use *Next = nullptr;
-  PointerIntPair<Use **, 2, PrevPtrTag, PrevPointerTraits> Prev;
+  PointerIntPair<Use **, Waymarker::Traits::NUM_BITS, unsigned> Prev;
+
+  void setWaymark(unsigned Tag) { new (this) Use(Tag); }
+  unsigned getWaymark() const { return Prev.getInt(); }
 
   void setPrev(Use **NewPrev) { Prev.setPointer(NewPrev); }
 
   void addToList(Use **List) {
     Next = *List;
     if (Next)
       Next->setPrev(&Next);
     setPrev(List);

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();
 }
 
-// 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) {
-    if (Start == Stop--)
-      return Start;
-    static const PrevPtrTag tags[20] = {
-        fullStopTag,  oneDigitTag,  stopTag,      oneDigitTag, oneDigitTag,
-        stopTag,      zeroDigitTag, oneDigitTag,  oneDigitTag, stopTag,
-        zeroDigitTag, oneDigitTag,  zeroDigitTag, oneDigitTag, stopTag,
-        oneDigitTag,  oneDigitTag,  oneDigitTag,  oneDigitTag, stopTag};
-    new (Stop) Use(tags[Done++]);
-  }
-
-  ptrdiff_t Count = Done;
-  while (Start != Stop) {
-    --Stop;
-    if (!Count) {
-      new (Stop) Use(stopTag);
-      ++Done;
-      Count = Done;
-    } else {
-      new (Stop) Use(PrevPtrTag(Count & 1));
-      Count >>= 1;
-      ++Done;
-    }
-  }
-
+  std::reverse_iterator<Use *> From(Stop), To(Start);
+  fillWaymarks<decltype(To), Waymarker>(From, To);
   return Start;
 }
 
 void Use::zap(Use *Start, const Use *Stop, bool del) {
   while (Start != Stop)
     (--Stop)->~Use();
   if (del)
     ::operator delete(Start);
 }
 
-const Use *Use::getImpliedUser() const {
-  const Use *Current = this;
-
-  while (true) {
-    unsigned Tag = (Current++)->Prev.getInt();
-    switch (Tag) {
-    case zeroDigitTag:
-    case oneDigitTag:
-      continue;
-
-    case stopTag: {
-      ++Current;
-      ptrdiff_t Offset = 1;
-      while (true) {
-        unsigned Tag = Current->Prev.getInt();
-        switch (Tag) {
-        case zeroDigitTag:
-        case oneDigitTag:
-          ++Current;
-          Offset = (Offset << 1) + Tag;
-          continue;
-        default:
-          return Current + Offset;
-        }
-      }
-    }
+namespace {
+struct FollowWaymarksIterator {
+  const Use *U;
+  FollowWaymarksIterator(const Use *U) : U(U) {}
+  const Use &operator*() const { return *U; }
+  FollowWaymarksIterator &operator++() {
+    --U;
+    return *this;
+  }
+  FollowWaymarksIterator &operator--() {
+    ++U;
+    return *this;
+  }
+  FollowWaymarksIterator operator--(int) { return U++; }
+  FollowWaymarksIterator &operator-=(const ptrdiff_t Offset) {
+    U += Offset;
+    return *this;
+};
+} // end anonymous namespace
 
-    case fullStopTag:
-      return Current;
-    }
-  }
+const Use *Use::getImpliedUser() const {
+  FollowWaymarksIterator It(this);
+  return &*followWaymarks<decltype(It), Waymarker>(It) + 1;
 }
 
-} // End llvm namespace
+} // end namespace llvm