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

234

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

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

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

 not exist in the symbol table.
 
 Symbol tables support iteration over the values in the symbol table with
 ``begin/end/iterator`` and supports querying to see if a specific name is in the
 symbol table (with ``lookup``).  The ``ValueSymbolTable`` class exposes no
 public mutator methods, instead, simply call ``setName`` on a value, which will
 autoinsert it into the appropriate symbol table.
 
-.. _UserLayout:
+.. _Waymarking:
 
-The ``User`` and owned ``Use`` classes' memory layout
------------------------------------------------------
+The Waymarking algorithm
+------------------------
 
-The ``User`` (`doxygen <http://llvm.org/doxygen/classllvm_1_1User.html>`__)
-class provides a basis for expressing the ownership of ``User`` towards other
-`Value instance <http://llvm.org/doxygen/classllvm_1_1Value.html>`_\ s.  The
-``Use`` (`doxygen <http://llvm.org/doxygen/classllvm_1_1Use.html>`__) helper
-class is employed to do the bookkeeping and to facilitate *O(1)* addition and
-removal.
+``#include "llvm/ADT/Waymarking.h"``
 
-.. _Use2User:
+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.
 
-Interaction and relationship between ``User`` and ``Use`` objects
-^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+A Tag of n-bits (in size) is composed as follows:
 
-A subclass of ``User`` can choose between incorporating its ``Use`` objects or
-refer to them out-of-line by means of a pointer.  A mixed variant (some ``Use``
-s inline others hung off) is impractical and breaks the invariant that the
-``Use`` objects belonging to the same ``User`` form a contiguous array.
+.. code-block:: none
 
-We have 2 different layouts in the ``User`` (sub)classes:
+  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.
 
-* Layout a)
+A special case - if we first encounter a Tag with a Stop and a zero digit,
+then this is already the head.
 
-  The ``Use`` object(s) are inside (resp. at fixed offset) of the ``User``
-  object and there are a fixed number of them.
+.. _Example2Bits:
 
-* Layout b)
+Example of 2 bits tag
+^^^^^^^^^^^^^^^^^^^^^
 
-  The ``Use`` object(s) are referenced by a pointer to an array from the
-  ``User`` object and there may be a variable number of them.
+Tags:
 
-As of v2.4 each layout still possesses a direct pointer to the start of the
-array of ``Use``\ s.  Though not mandatory for layout a), we stick to this
-redundancy for the sake of simplicity.  The ``User`` object also stores the
-number of ``Use`` objects it has. (Theoretically this information can also be
-calculated given the scheme presented below.)
+* ``x0`` --- binary digit 0
 
-Special forms of allocation operators (``operator new``) enforce the following
-memory layouts:
+* ``x1`` --- binary digit 1
 
-* Layout a) is modelled by prepending the ``User`` object by the ``Use[]``
-  array.
+* ``1x`` --- stop and calculate (s)
 
-  .. code-block:: none
 
-    ...---.---.---.---.-------...
-      | P | P | P | P | User
-    '''---'---'---'---'-------'''
-
-* Layout b) is modelled by pointing at the ``Use[]`` array.
+Array:
 
-  .. code-block:: none
 
-    .-------...
-    | User
-    '-------'''
-        |
-        v
-        .---.---.---.---...
-        | P | P | P | P |
-        '---'---'---'---'''
+          .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.
+  head -> |s0 |s1 | 0 |s1 | 0 | 0 |s1 | 1 | 1 |s1 | 0 | 1 | 0 |s1 | 0 | 1 |
+          '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'
+            -1| -2|     -4|         -7|        -10|                -14|
+           <_ |   |       |           |           |                   |
+           <_____ |       |           |           |                   |
+           <_____________ |           |           |                   |
+           <_________________________ |           |                   |
+           <_____________________________________ |                   |
+           <_________________________________________________________ |
 
-*(In the above figures* '``P``' *stands for the* ``Use**`` *that is stored in
-each* ``Use`` *object in the member* ``Use::Prev`` *)*
+Only the significant number of bits need to be stored between the stops, so that
+the *worst case is 19 memory accesses* for an array of size 1000.
 
-.. _Waymarking:
+.. _Example3Bits:
 
-The waymarking algorithm
-^^^^^^^^^^^^^^^^^^^^^^^^
+Example of 3 bits tag
+^^^^^^^^^^^^^^^^^^^^^
 
-Since the ``Use`` objects are deprived of the direct (back)pointer to their
-``User`` objects, there must be a fast and exact method to recover it.  This is
-accomplished by the following scheme:
+Tags:
+
+* ``x00`` --- quaternary digit 0
 
-A bit-encoding in the 2 LSBits (least significant bits) of the ``Use::Prev``
-allows to find the start of the ``User`` object:
+* ``x01`` --- quaternary digit 1
 
-* ``00`` --- binary digit 0
+* ``x10`` --- quaternary digit 2
 
-* ``01`` --- binary digit 1
+* ``x11`` --- quaternary digit 3
 
-* ``10`` --- stop and calculate (``s``)
+* ``1xy`` --- stop and calculate (s)
 
-* ``11`` --- full stop (``S``)
 
-Given a ``Use*``, all we have to do is to walk till we get a stop and we either
-have a ``User`` immediately behind or we have to walk to the next stop picking
-up digits and calculating the offset:
+Array:
 
 .. code-block:: none
 
-  .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.----------------
-  | 1 | s | 1 | 0 | 1 | 0 | s | 1 | 1 | 0 | s | 1 | 1 | s | 1 | S | User (or User*)
-  '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'----------------
-      |+15                |+10            |+6         |+3     |+1
-      |                   |               |           |       | __>
-      |                   |               |           | __________>
-      |                   |               | ______________________>
-      |                   | ______________________________________>
-      | __________________________________________________________>
+          .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.
+  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|
+           <_ |   |   |   |       |       |       |       |       |       |
+           <_____ |   |   |       |       |       |       |       |       |
+           <_________ |   |       |       |       |       |       |       |
+           <_____________ |       |       |       |       |       |       |
+           <_____________________ |       |       |       |       |       |
+           <_____________________________ |       |       |       |       |
+           <_____________________________________ |       |       |       |
+           <_____________________________________________ |       |       |
+           <_____________________________________________________ |       |
+           <_____________________________________________________________ |
        
 Only the significant number of bits need to be stored between the stops, so that
-the *worst case is 20 memory accesses* when there are 1000 ``Use`` objects
-associated with a ``User``.
+the *worst case is 10 memory accesses* for an array of size 1000.
 
 .. _ReferenceImpl:
 
 Reference implementation
 ^^^^^^^^^^^^^^^^^^^^^^^^
 
+It is clearer to look at the array of tags in reverse order, and perform the
+waymarking following by moving forward (instead of the default backward).
+
+To represent each 2 bits tag using a single character, we define the following
+analogy:
+
+* ``00`` = ``'0'``
+
+* ``01`` = ``'1'``
+
+* ``10`` = ``'S'``
+
+* ``11`` = ``'s'``
+
 The following literate Haskell fragment demonstrates the concept:
 
 .. code-block:: haskell
 
   > import Test.QuickCheck
   >
   > digits :: Int -> [Char] -> [Char]
   > digits 0 acc = '0' : acc
   > digits 1 acc = '1' : acc
   > digits n acc = digits (n `div` 2) $ digits (n `mod` 2) acc
   >
   > dist :: Int -> [Char] -> [Char]
-  > dist 0 [] = ['S']
   > dist 0 acc = acc
-  > dist 1 acc = let r = dist 0 acc in 's' : digits (length r) r
+  > dist 1 [] = ['S']
+  > dist 1 acc = 's' : drop 1 (digits (length acc) acc)
   > dist n acc = dist (n - 1) $ dist 1 acc
   >
   > takeLast n ss = reverse $ take n $ reverse ss
   >
   > test = takeLast 40 $ dist 20 []
   >
 
-Printing <test> gives: ``"1s100000s11010s10100s1111s1010s110s11s1S"``
+Printing <test> gives: ``"1s00001s1100s0111s0010s110s010s11s00s0sS"``
 
 The reverse algorithm computes the length of the string just by examining a
 certain prefix:
 
 .. code-block:: haskell
 
   > pref :: [Char] -> Int
   > pref "S" = 1
-  > pref ('s':'1':rest) = decode 2 1 rest
+  > pref ('s':rest) = decode 1 1 rest
   > pref (_:rest) = 1 + pref rest
   >
   > decode walk acc ('0':rest) = decode (walk + 1) (acc * 2) rest
   > decode walk acc ('1':rest) = decode (walk + 1) (acc * 2 + 1) rest
   > decode walk acc _ = walk + acc
   >
 
 Now, as expected, printing <pref test> gives ``40``.

 
 And here is the result of <deepCheck identityProp>:
 
 ::
 
   *Main> deepCheck identityProp
   OK, passed 500 tests.
 
+.. _UserLayout:
+
+The ``User`` and owned ``Use`` classes' memory layout
+-----------------------------------------------------
+
+The ``User`` (`doxygen <http://llvm.org/doxygen/classllvm_1_1User.html>`__)
+class provides a basis for expressing the ownership of ``User`` towards other
+`Value instance <http://llvm.org/doxygen/classllvm_1_1Value.html>`_\ s.  The
+``Use`` (`doxygen <http://llvm.org/doxygen/classllvm_1_1Use.html>`__) helper
+class is employed to do the bookkeeping and to facilitate *O(1)* addition and
+removal.
+
+.. _Use2User:
+
+Interaction and relationship between ``User`` and ``Use`` objects
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+A subclass of ``User`` can choose between incorporating its ``Use`` objects or
+refer to them out-of-line by means of a pointer.  A mixed variant (some ``Use``
+s inline others hung off) is impractical and breaks the invariant that the
+``Use`` objects belonging to the same ``User`` form a contiguous array.
+
+We have 2 different layouts in the ``User`` (sub)classes:
+
+* Layout a)
+
+  The ``Use`` object(s) are inside (resp. at fixed offset) of the ``User``
+  object and there are a fixed number of them.
+
+* Layout b)
+
+  The ``Use`` object(s) are referenced by a pointer to an array from the
+  ``User`` object and there may be a variable number of them.
+
+As of v2.4 each layout still possesses a direct pointer to the start of the
+array of ``Use``\ s.  Though not mandatory for layout a), we stick to this
+redundancy for the sake of simplicity.  The ``User`` object also stores the
+number of ``Use`` objects it has. (Theoretically this information can also be
+calculated given the scheme presented below.)
+
+Special forms of allocation operators (``operator new``) enforce the following
+memory layouts:
+
+* Layout a) is modelled by prepending the ``User`` object by the ``Use[]``
+  array.
+
+  .. code-block:: none
+
+    ...---.---.---.---.-------...
+      | P | P | P | P | User
+    '''---'---'---'---'-------'''
+
+* Layout b) is modelled by pointing at the ``Use[]`` array.
+
+  .. code-block:: none
+
+    .-------...
+    | User
+    '-------'''
+        |
+        v
+        .---.---.---.---...
+        | P | P | P | P |
+        '---'---'---'---'''
+
+*(In the above figures* '``P``' *stands for the* ``Use**`` *that is stored in
+each* ``Use`` *object in the member* ``Use::Prev`` *)*
+
+Since the ``Use`` objects are deprived of the direct (back)pointer to their
+``User`` objects, there must be a fast and exact method to recover it.  This is
+accomplished by using :ref:`The Waymarking algorithm <Waymarking>`.
+
 .. _Tagging:
 
 Tagging considerations
 ^^^^^^^^^^^^^^^^^^^^^^
 
-To maintain the invariant that the 2 LSBits of each ``Use**`` in ``Use`` never
-change after being set up, setters of ``Use::Prev`` must re-tag the new
+The waymarking tags are stored in the free-LSBits (least significant bits that
+are always zero according to pointer alignment) of the ``Use::Prev``.
+
+To maintain the invariant that the free-LSBits of each ``Use**`` in ``Use``
+never change after being set up, setters of ``Use::Prev`` must re-tag the new
 ``Use**`` on every modification.  Accordingly getters must strip the tag bits.
 
 For layout b) instead of the ``User`` we find a pointer (``User*`` with LSBit
-set).  Following this pointer brings us to the ``User``.  A portable trick
-ensures that the first bytes of ``User`` (if interpreted as a pointer) never has
-the LSBit set. (Portability is relying on the fact that all known compilers
-place the ``vptr`` in the first word of the instances.)
+set).  Following this pointer brings us to the ``User``.  To distinguish between
+the layouts, we must ensure that the LSBit of ``User`` is always clear.  As
+``User`` derived from ``Value``, we keep the ``Type``'s pointer as the first
+field of ``Value`` (pointer alignment takes care of the rest).
 
 .. _polymorphism:
 
 Designing Type Hiercharies and Polymorphic Interfaces
 -----------------------------------------------------
 
 There are two different design patterns that tend to result in the use of
 virtual dispatch for methods in a type hierarchy in C++ programs. The first is

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|
+//          <_ |   |   |   |       |       |       |       |       |       |
+//          <_____ |   |   |       |       |       |       |       |       |
+//          <_________ |   |       |       |       |       |       |       |
+//          <_____________ |       |       |       |       |       |       |
+//          <_____________________ |       |       |       |       |       |
+//          <_____________________________ |       |       |       |       |
+//          <_____________________________________ |       |       |       |
+//          <_____________________________________________ |       |       |
+//          <_____________________________________________________ |       |
+//          <_____________________________________________________________ |
+//
+//
+// The API introduce 2 functions:
+// 1. fillWaymarks
+// 2. followWaymarks
+//
+// Example:
+//   int N = 10;
+//   int M = 5;
+//   int **A = new int *[N + M];   // Define the array.
+//   for (int I = 0; I < N + M; ++I)
+//     A[I] = new int(I);
+//
+//   fillWaymarks(A, A + N);       // Set the waymarks for the first N elements
+//                                 // of the array.
+//                                 // Note that it must be done AFTER we fill
+//                                 // the array's elements.
+//
+//   ...                           // Elements which are not in the range
+//                                 // [A, A+N) will not be marked, and we won't
+//                                 // be able to call followWaymarks on them.
+//
+//   ...                           // Elements which will be changed after the
+//                                 // call to fillWaymarks, will have to be
+//                                 // retagged.
+//
+//   fillWaymarks(A + N, A + N + M, N); // Set the waymarks of the remaining M
+//                                      // elements.
+//   ...
+//   int **It = A + N + 1;
+//   int **B = followWaymarks(It); // Find the head of the array containing It.
+//   assert(B == A);
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_WAYMARKING_H
+#define LLVM_ADT_WAYMARKING_H
+
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/PointerLikeTypeTraits.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 TagsData<Count, Vals...> Xdata;
+  };
+
+  template <unsigned Count, uint8_t... Vals>
+  struct AddTag<0, true, Count, Vals...> {
+    typedef 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
+
+/// This class is responsible for tagging (and retrieving the tag of) a given
+/// element of type T.
+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 [Begin, End).
+///
+/// \param Begin The beginning of the range to mark with tags (inclusive).
+/// \param End The ending of the range to mark with tags (exclusive).
+/// \param Offset The position in the supposed tags array from which to start
+/// marking the 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) {
+  if (!(Begin < End))
+    return;
+
+  size_t Count;
+  if (Offset <= Marker::Traits::NUM_STATIC_TAGS) {
+    while (Offset != Marker::Traits::NUM_STATIC_TAGS) {
+      Marker::setWaymark(*Begin, Marker::Traits::Tags::Values[Offset]);
+
+      ++Offset;
+      ++Begin;
+
+      if (!(Begin < End))
+        return;
+    }
+
+    Count = Marker::Traits::Tags::Remain;
+  } else {
+    Count = Marker::Traits::Tags::Remain;
+    size_t Off = Marker::Traits::NUM_STATIC_TAGS;
+    do {
+      ++Off;
+
+      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 = Off;
+      } else
+        Count >>= Marker::Traits::MARK_SIZE;
+    } while (Off != Offset);
+  }
+
+  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.
+///
+/// \param Range The range to mark with tags.
+/// \param Offset The position in the supposed tags array from which to start
+/// marking the 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 element marked with tag of only STOP_MASK, by following the
+/// waymarks. This is the first element in a range passed to a previous call to
+/// \c fillWaymarks with \c Offset 0.
+///
+/// For the trivial usage of calling \c fillWaymarks(Array), and \I is an
+/// iterator inside \c Array, this function retrieves the head of \c Array, by
+/// following the waymarks.
+///
+/// \param I The iterator into an array which was marked by the waymarking tags
+/// (by a previous call to \c fillWaymarks).
+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

 //===-- Use.cpp - Implement the Use 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/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include <new>
 
-namespace llvm {
+using namespace llvm;
 
 void Use::swap(Use &RHS) {
   if (Val == RHS.Val)
     return;
 
   if (Val)
     removeFromList();
 
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 {
+// This iterator yields better code and simpler to use, than
+// std::reverse_iterator.
+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

llvm/unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   StringExtrasTest.cpp
   StringMapTest.cpp
   StringRefTest.cpp
   StringSetTest.cpp
   StringSwitchTest.cpp
   TinyPtrVectorTest.cpp
   TripleTest.cpp
   TwineTest.cpp
+  WaymarkingTest.cpp
   )
 
 target_link_libraries(ADTTests PRIVATE LLVMTestingSupport)
 
 add_dependencies(ADTTests intrinsics_gen)

llvm/unittests/ADT/WaymarkingTest.cpp

+//===- llvm/unittest/IR/WaymarkTest.cpp - getUser() unit tests ------------===//
+//
+// 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/ADT/Waymarking.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+const int N = 100;
+
+int tag(int *P) {
+  return static_cast<int>(reinterpret_cast<uintptr_t>(P) &
+                          uintptr_t(alignof(int *) - 1));
+}
+
+int *ref(int *P) {
+  return reinterpret_cast<int *>(reinterpret_cast<uintptr_t>(P) &
+                                 ~uintptr_t(alignof(int *) - 1));
+}
+
+int deref(int *P) { return *ref(P); }
+
+int **createArray(int Len) {
+  int **A = new int *[Len];
+  for (int I = 0; I < Len; ++I)
+    A[I] = new int(I);
+  return A;
+}
+
+void freeArray(int **A, int Len) {
+  for (int I = 0; I < Len; ++I)
+    delete ref(A[I]);
+  delete[] A;
+}
+
+TEST(WaymarkingTest, SingleHead) {
+  const int N2 = 2 * N;
+  int **A = createArray(N2);
+
+  // Fill the first half of the array with waymarkings.
+  fillWaymarks(A, A + N, 0);
+
+  // Verify the values stored in the array are as expected, while we can deduce
+  // the array's head from them.
+  for (int I = 0; I < N; ++I) {
+    int **P = followWaymarks(A + I);
+    EXPECT_EQ(A, P);
+    EXPECT_EQ(I, deref(A[I]));
+  }
+
+  // Fill the rest of the waymarkings (continuing from where we stopped).
+  fillWaymarks(A + N, A + N2, N);
+
+  // Verify the values stored in the array are as expected, while we can deduce
+  // the array's head from them.
+  for (int I = 0; I < N2; ++I) {
+    int **P = followWaymarks(A + I);
+    EXPECT_EQ(A, P);
+    EXPECT_EQ(I, deref(A[I]));
+  }
+
+  freeArray(A, N2);
+}
+
+TEST(WaymarkingTest, MultiHead) {
+  const int N2 = 2 * N;
+  const int N3 = 3 * N;
+  int **A = createArray(N3);
+
+  // Seperate the array into 3 sections, of waymarkings.
+  fillWaymarks(A, A + N, 0);
+  fillWaymarks(A + N, A + N2, 0);
+  fillWaymarks(A + N2, A + N3, 0);
+
+  // Verify the values stored in the array are as expected, while we can deduce
+  // the array section's head from them.
+  for (int I = 0; I < N; ++I) {
+    int **P = followWaymarks(A + I);
+    EXPECT_EQ(A, P);
+    EXPECT_EQ(I, deref(A[I]));
+  }
+  for (int I = N; I < N2; ++I) {
+    int **P = followWaymarks(A + I);
+    EXPECT_EQ(A + N, P);
+    EXPECT_EQ(I, deref(A[I]));
+  }
+  for (int I = N2; I < N3; ++I) {
+    int **P = followWaymarks(A + I);
+    EXPECT_EQ(A + N2, P);
+    EXPECT_EQ(I, deref(A[I]));
+  }
+
+  freeArray(A, N3);
+}
+
+TEST(WaymarkingTest, Reset) {
+  int **A = createArray(N);
+
+  fillWaymarks(A, A + N, 0);
+
+  const int N2 = N / 2;
+  const int N3 = N / 3;
+  const int N4 = N / 4;
+
+  // Reset specific elements and check that the tag remains the same.
+  int T2 = tag(A[N2]);
+  delete ref(A[N2]);
+  A[N2] = new int(-1);
+  fillWaymarks(A + N2, A + N2 + 1, N2);
+  EXPECT_EQ(T2, tag(A[N2]));
+
+  int T3 = tag(A[N3]);
+  delete ref(A[N3]);
+  A[N3] = new int(-1);
+  fillWaymarks(A + N3, A + N3 + 1, N3);
+  EXPECT_EQ(T3, tag(A[N3]));
+
+  int T4 = tag(A[N4]);
+  delete ref(A[N4]);
+  A[N4] = new int(-1);
+  fillWaymarks(A + N4, A + N4 + 1, N4);
+  EXPECT_EQ(T4, tag(A[N4]));
+
+  // Verify the values stored in the array are as expected, while we can deduce
+  // the array's head from them.
+  for (int I = 0; I < N; ++I) {
+    int **P = followWaymarks(A + I);
+    EXPECT_EQ(A, P);
+    switch (I) {
+    case N2:
+    case N3:
+    case N4:
+      EXPECT_EQ(-1, deref(A[I]));
+      break;
+
+    default:
+      EXPECT_EQ(I, deref(A[I]));
+      break;
+    }
+  }
+
+  freeArray(A, N);
+}
+
+} // end anonymous namespace

llvm/unittests/IR/CMakeLists.txt

add_llvm_unittest(IRTests
   TypesTest.cpp
   UseTest.cpp
   UserTest.cpp
   ValueHandleTest.cpp
   ValueMapTest.cpp
   ValueTest.cpp
   VectorTypesTest.cpp
   VerifierTest.cpp
-  WaymarkTest.cpp
   )
 
 target_link_libraries(IRTests PRIVATE LLVMTestingSupport)

llvm/unittests/IR/UseTest.cpp

 //===- llvm/unittest/IR/UseTest.cpp - Use unit tests ----------------------===//
 //
 // 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/AsmParser/Parser.h"
+#include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/User.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
TEST(UseTest, reverse) {
   I = 0;
   for (User *U : X.users()) {
     format("v%u", (7 - I++)).snprint(vnbuf, sizeof(vnbuf));
     EXPECT_EQ(vnbuf, U->getName());
   }
   ASSERT_EQ(8u, I);
 }
 
+TEST(UseTest, waymarking) {
+  LLVMContext Context;
+  static uint8_t tail[22] = "s02s33s30y2y0s1x0syxS";
+  Value *values[22];
+  std::transform(tail, tail + 22, values, [&](char c) {
+    return ConstantInt::get(Type::getInt8Ty(Context), c);
+  });
+  FunctionType *FT = FunctionType::get(Type::getVoidTy(Context), true);
+  std::unique_ptr<Function> F(
+      Function::Create(FT, GlobalValue::ExternalLinkage));
+  const CallInst *A = CallInst::Create(F.get(), makeArrayRef(values));
+  ASSERT_NE(A, (const CallInst *)nullptr);
+  ASSERT_EQ(1U + 22, A->getNumOperands());
+  const Use *U = &A->getOperandUse(0);
+  const Use *Ue = &A->getOperandUse(22);
+  for (; U != Ue; ++U) {
+    EXPECT_EQ(A, U->getUser());
+  }
+  delete A;
+}
+
 } // end anonymous namespace

llvm/unittests/IR/WaymarkTest.cpp

-//===- llvm/unittest/IR/WaymarkTest.cpp - getUser() unit tests ------------===//
-//
-// 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
-//
-//===----------------------------------------------------------------------===//
-
-// we perform white-box tests
-//
-#include "llvm/IR/Constants.h"
-#include "llvm/IR/Function.h"
-#include "llvm/IR/Instructions.h"
-#include "llvm/IR/LLVMContext.h"
-#include "gtest/gtest.h"
-#include <algorithm>
-
-namespace llvm {
-namespace {
-
-TEST(WaymarkTest, NativeArray) {
-  LLVMContext Context;
-  static uint8_t tail[22] = "s02s33s30y2y0s1x0syxS";
-  Value * values[22];
-  std::transform(tail, tail + 22, values, [&](char c) {
-    return ConstantInt::get(Type::getInt8Ty(Context), c);
-  });
-  FunctionType *FT = FunctionType::get(Type::getVoidTy(Context), true);
-  std::unique_ptr<Function> F(
-      Function::Create(FT, GlobalValue::ExternalLinkage));
-  const CallInst *A = CallInst::Create(F.get(), makeArrayRef(values));
-  ASSERT_NE(A, (const CallInst*)nullptr);
-  ASSERT_EQ(1U + 22, A->getNumOperands());
-  const Use *U = &A->getOperandUse(0);
-  const Use *Ue = &A->getOperandUse(22);
-  for (; U != Ue; ++U)
-  {
-    EXPECT_EQ(A, U->getUser());
-  }
-  delete A;
-}
-
-TEST(WaymarkTest, TwoBit) {
-  Use* many = (Use*)calloc(sizeof(Use), 8212 + 1);
-  ASSERT_TRUE(many);
-  Use::initTags(many, many + 8212);
-  for (Use *U = many, *Ue = many + 8212 - 1; U != Ue; ++U)
-  {
-    EXPECT_EQ(reinterpret_cast<User *>(Ue + 1), U->getUser());
-  }
-  free(many);
-}
-
-}  // end anonymous namespace
-}  // end namespace llvm