Index: llvm/docs/ProgrammersManual.rst =================================================================== --- llvm/docs/ProgrammersManual.rst +++ llvm/docs/ProgrammersManual.rst @@ -3103,119 +3103,127 @@ 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 `__) -class provides a basis for expressing the ownership of ``User`` towards other -`Value instance `_\ s. The -``Use`` (`doxygen `__) 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| + '---------'------------------------------------' -* Layout a) +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. - The ``Use`` object(s) are inside (resp. at fixed offset) of the ``User`` - object and there are a fixed number of them. +A special case - if we first encounter a Tag with a Stop and a zero digit, +then this is already the head. -* Layout b) +.. _Example2Bits: - 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. +Example of 2 bits tag +^^^^^^^^^^^^^^^^^^^^^ -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.) +Tags: -Special forms of allocation operators (``operator new``) enforce the following -memory layouts: +* ``x0`` --- binary digit 0 -* Layout a) is modelled by prepending the ``User`` object by the ``Use[]`` - array. +* ``x1`` --- binary digit 1 - .. code-block:: none +* ``1x`` --- stop and calculate (s) - ...---.---.---.---.-------... - | P | P | P | P | User - '''---'---'---'---'-------''' -* Layout b) is modelled by pointing at the ``Use[]`` array. +Array: - .. code-block:: none +.. 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: -A bit-encoding in the 2 LSBits (least significant bits) of the ``Use::Prev`` -allows to find the start of the ``User`` object: +* ``x00`` --- quaternary digit 0 -* ``00`` --- binary digit 0 +* ``x01`` --- quaternary digit 1 -* ``01`` --- binary digit 1 +* ``x10`` --- quaternary digit 2 -* ``10`` --- stop and calculate (``s``) +* ``x11`` --- quaternary digit 3 -* ``11`` --- full stop (``S``) +* ``1xy`` --- stop and calculate (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: -.. code-block:: none +Array: - .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---------------- - | 1 | s | 1 | 0 | 1 | 0 | s | 1 | 1 | 0 | s | 1 | 1 | s | 1 | S | User (or User*) - '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---------------- - |+15 |+10 |+6 |+3 |+1 - | | | | | __> - | | | | __________> - | | | ______________________> - | | ______________________________________> - | __________________________________________________________> +.. code-block:: none + .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---. + 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 @@ -3228,9 +3236,9 @@ > 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 @@ -3238,7 +3246,7 @@ > test = takeLast 40 $ dist 20 [] > -Printing gives: ``"1s100000s11010s10100s1111s1010s110s11s1S"`` +Printing gives: ``"1s00001s1100s0111s0010s110s010s11s00s0sS"`` The reverse algorithm computes the length of the string just by examining a certain prefix: @@ -3247,7 +3255,7 @@ > 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 @@ -3290,20 +3298,95 @@ *Main> deepCheck identityProp OK, passed 500 tests. +.. _UserLayout: + +The ``User`` and owned ``Use`` classes' memory layout +----------------------------------------------------- + +The ``User`` (`doxygen `__) +class provides a basis for expressing the ownership of ``User`` towards other +`Value instance `_\ s. The +``Use`` (`doxygen `__) 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 `. + .. _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: Index: llvm/include/llvm/ADT/Waymarking.h =================================================================== --- /dev/null +++ llvm/include/llvm/ADT/Waymarking.h @@ -0,0 +1,305 @@ +//===- 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 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 + struct AddTag; + + template struct GenTag { + typedef + typename AddTag::Xdata Xdata; + }; + + template struct GenOffset { + typedef typename GenTag::Xdata Xdata; + }; + + template + struct AddTag { + typedef typename GenTag> MARK_SIZE), Vals..., + Count & MARK_MASK>::Xdata Xdata; + }; + + template + struct AddTag { + typedef typename GenOffset::Xdata Xdata; + }; + + template struct TagsData { + static const unsigned Remain = Count; + static const uint8_t Values[sizeof...(Vals)]; + }; + + template + struct AddTag<0, false, Count, Vals...> { + typedef TagsData Xdata; + }; + + template + struct AddTag<0, true, Count, Vals...> { + typedef TagsData Xdata; + }; + +public: + typedef typename GenOffset::Xdata Tags; +}; + +template +template +const uint8_t WaymarkingTraits::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 ::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 struct Waymarker { + using Traits = WTraits; + static void setWaymark(T *&N, unsigned Tag) { + reinterpret_cast(N) |= static_cast(Tag); + } + static unsigned getWaymark(const T *N) { + return static_cast(reinterpret_cast(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 ::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 >> +void fillWaymarks(R &&Range, size_t Offset = 0) { + return fillWaymarks, 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 ::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 Index: llvm/include/llvm/IR/Use.h =================================================================== --- llvm/include/llvm/IR/Use.h +++ llvm/include/llvm/IR/Use.h @@ -26,6 +26,7 @@ #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" @@ -76,18 +77,6 @@ // a pointer back to their User with the bottom bit set. using UserRef = PointerIntPair; - /// 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() { @@ -95,10 +84,8 @@ removeFromList(); } - enum PrevPtrTag { zeroDigitTag, oneDigitTag, stopTag, fullStopTag }; - /// Constructor - Use(PrevPtrTag tag) { Prev.setInt(tag); } + Use(unsigned tag) { Prev.setInt(tag); } public: friend class Value; @@ -138,9 +125,17 @@ private: const Use *getImpliedUser() const LLVM_READONLY; + using Waymarker = + llvm::Waymarker::NumLowBitsAvailable>>; + friend Waymarker; + Value *Val = nullptr; Use *Next = nullptr; - PointerIntPair Prev; + PointerIntPair Prev; + + void setWaymark(unsigned Tag) { new (this) Use(Tag); } + unsigned getWaymark() const { return Prev.getInt(); } void setPrev(Use **NewPrev) { Prev.setPointer(NewPrev); } Index: llvm/lib/IR/Use.cpp =================================================================== --- llvm/lib/IR/Use.cpp +++ llvm/lib/IR/Use.cpp @@ -11,7 +11,7 @@ #include "llvm/IR/Value.h" #include -namespace llvm { +using namespace llvm; void Use::swap(Use &RHS) { if (Val == RHS.Val) @@ -48,38 +48,9 @@ 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 From(Stop), To(Start); + fillWaymarks(From, To); return Start; } @@ -90,37 +61,30 @@ ::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; - } - } - } - - case fullStopTag: - return Current; - } +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 -} // End llvm namespace +const Use *Use::getImpliedUser() const { + FollowWaymarksIterator It(this); + return &*followWaymarks(It) + 1; +} Index: llvm/unittests/ADT/CMakeLists.txt =================================================================== --- llvm/unittests/ADT/CMakeLists.txt +++ llvm/unittests/ADT/CMakeLists.txt @@ -72,6 +72,7 @@ TinyPtrVectorTest.cpp TripleTest.cpp TwineTest.cpp + WaymarkingTest.cpp ) target_link_libraries(ADTTests PRIVATE LLVMTestingSupport) Index: llvm/unittests/ADT/WaymarkingTest.cpp =================================================================== --- /dev/null +++ llvm/unittests/ADT/WaymarkingTest.cpp @@ -0,0 +1,152 @@ +//===- 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(reinterpret_cast(P) & + uintptr_t(alignof(int *) - 1)); +} + +int *ref(int *P) { + return reinterpret_cast(reinterpret_cast(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 Index: llvm/unittests/IR/CMakeLists.txt =================================================================== --- llvm/unittests/IR/CMakeLists.txt +++ llvm/unittests/IR/CMakeLists.txt @@ -39,7 +39,6 @@ ValueTest.cpp VectorTypesTest.cpp VerifierTest.cpp - WaymarkTest.cpp ) target_link_libraries(IRTests PRIVATE LLVMTestingSupport) Index: llvm/unittests/IR/UseTest.cpp =================================================================== --- llvm/unittests/IR/UseTest.cpp +++ llvm/unittests/IR/UseTest.cpp @@ -7,7 +7,9 @@ //===----------------------------------------------------------------------===// #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" @@ -107,4 +109,25 @@ 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 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 Index: llvm/unittests/IR/WaymarkTest.cpp =================================================================== --- llvm/unittests/IR/WaymarkTest.cpp +++ /dev/null @@ -1,55 +0,0 @@ -//===- 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 - -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 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(Ue + 1), U->getUser()); - } - free(many); -} - -} // end anonymous namespace -} // end namespace llvm