1 //===- Waymarking.h - Array waymarking algorithm ----------------*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // Utility to backtrace an array's head, from a pointer into it. For the
10 // backtrace to work, we use "Waymarks", which are special tags embedded into
11 // the array's elements.
13 // A Tag of n-bits (in size) is composed as follows:
15 // bits: | n-1 | n-2 ... 0 |
16 // .---------.------------------------------------.
17 // |Stop Mask|(2^(n-1))-ary numeric system - digit|
18 // '---------'------------------------------------'
20 // Backtracing is done as follows:
21 // Walk back (starting from a given pointer to an element into the array), until
22 // a tag with a "Stop Mask" is reached. Then start calculating the "Offset" from
23 // the array's head, by picking up digits along the way, until another stop is
24 // reached. The "Offset" is then subtracted from the current pointer, and the
25 // result is the array's head.
26 // A special case - if we first encounter a Tag with a Stop and a zero digit,
27 // then this is already the head.
33 // x0 - binary digit 0
34 // x1 - binary digit 1
35 // 1x - stop and calculate (s)
38 // .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.
39 // head -> |s0 |s1 | 0 |s1 | 0 | 0 |s1 | 1 | 1 |s1 | 0 | 1 | 0 |s1 | 0 | 1 |
40 // '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'
41 // |-1 |-2 |-4 |-7 |-10 |-14
44 // <_____________ | | | |
45 // <_________________________ | | |
46 // <_____________________________________ | |
47 // <_____________________________________________________ |
53 // x00 - quaternary digit 0
54 // x01 - quaternary digit 1
55 // x10 - quaternary digit 2
56 // x11 - quaternary digit 3
57 // 1xy - stop and calculate (s)
60 // .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.
61 // head -> |s0 |s1 |s2 |s3 | 0 |s1 | 2 |s1 | 0 |s2 | 2 |s2 | 0 |s3 | 2 |s3 |
62 // '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'
63 // |-1 |-2 |-3 |-4 |-6 |-8 |-10 |-12 |-14 |-16
64 // <_ | | | | | | | | | |
65 // <_____ | | | | | | | | |
66 // <_________ | | | | | | | |
67 // <_____________ | | | | | | |
68 // <_____________________ | | | | | |
69 // <_____________________________ | | | | |
70 // <_____________________________________ | | | |
71 // <_____________________________________________ | | |
72 // <_____________________________________________________ | |
73 // <_____________________________________________________________ |
76 // The API introduce 2 functions:
83 // int **A = new int *[N + M]; // Define the array.
84 // for (int I = 0; I < N + M; ++I)
87 // fillWaymarks(A, A + N); // Set the waymarks for the first N elements
89 // // Note that it must be done AFTER we fill
90 // // the array's elements.
92 // ... // Elements which are not in the range
93 // // [A, A+N) will not be marked, and we won't
94 // // be able to call followWaymarks on them.
96 // ... // Elements which will be changed after the
97 // // call to fillWaymarks, will have to be
100 // fillWaymarks(A + N, A + N + M, N); // Set the waymarks of the remaining M
103 // int **It = A + N + 1;
104 // int **B = followWaymarks(It); // Find the head of the array containing It.
107 //===----------------------------------------------------------------------===//
109 #ifndef LLVM_ADT_WAYMARKING_H
110 #define LLVM_ADT_WAYMARKING_H
112 #include "llvm/ADT/STLExtras.h"
113 #include "llvm/Support/PointerLikeTypeTraits.h"
119 template <unsigned NumBits> struct WaymarkingTraits {
121 // The number of bits of a Waymarking Tag.
124 // A Tag is composed from a Mark and a Stop mask.
125 MARK_SIZE = NUM_BITS - 1,
126 STOP_MASK = (1 << MARK_SIZE),
127 MARK_MASK = (STOP_MASK - 1),
128 TAG_MASK = (MARK_MASK | STOP_MASK),
130 // The number of pre-computed tags (for fast fill).
135 // Add a new tag, calculated from Count and Stop, to the Vals pack, while
136 // continuing recursively to decrease Len down to 0.
137 template <unsigned Len, bool Stop, unsigned Count, uint8_t... Vals>
140 // Delegate to the specialized AddTag according to the need of a Stop mask.
141 template <unsigned Len, unsigned Count, uint8_t... Vals> struct GenTag {
143 typename AddTag<Len, (Count <= MARK_MASK), Count, Vals...>::Xdata Xdata;
146 // Start adding tags while calculating the next Count, which is actually the
147 // number of already calculated tags (equivalent to the position in the
149 template <unsigned Len, uint8_t... Vals> struct GenOffset {
150 typedef typename GenTag<Len, sizeof...(Vals), Vals...>::Xdata Xdata;
153 // Add the tag and remove it from Count.
154 template <unsigned Len, unsigned Count, uint8_t... Vals>
155 struct AddTag<Len, false, Count, Vals...> {
156 typedef typename GenTag<Len - 1, (Count >> MARK_SIZE), Vals...,
157 Count & MARK_MASK>::Xdata Xdata;
160 // We have reached the end of this Count, so start with a new Count.
161 template <unsigned Len, unsigned Count, uint8_t... Vals>
162 struct AddTag<Len, true, Count, Vals...> {
163 typedef typename GenOffset<Len - 1, Vals...,
164 (Count & MARK_MASK) | STOP_MASK>::Xdata Xdata;
167 template <unsigned Count, uint8_t... Vals> struct TagsData {
168 // The remaining number for calculating the next tag, following the last one
170 static const unsigned Remain = Count;
172 // The array of ordered pre-computed Tags.
173 static const uint8_t Values[sizeof...(Vals)];
176 // Specialize the case when Len equals 0, as the recursion stop condition.
177 template <unsigned Count, uint8_t... Vals>
178 struct AddTag<0, false, Count, Vals...> {
179 typedef TagsData<Count, Vals...> Xdata;
182 template <unsigned Count, uint8_t... Vals>
183 struct AddTag<0, true, Count, Vals...> {
184 typedef TagsData<Count, Vals...> Xdata;
188 typedef typename GenOffset<NUM_STATIC_TAGS>::Xdata Tags;
191 template <unsigned NumBits>
192 template <unsigned Count, uint8_t... Vals>
193 const uint8_t WaymarkingTraits<NumBits>::TagsData<
194 Count, Vals...>::Values[sizeof...(Vals)] = {Vals...};
196 } // end namespace detail
198 /// This class is responsible for tagging (and retrieving the tag of) a given
199 /// element of type T.
200 template <class T, class WTraits = detail::WaymarkingTraits<
201 PointerLikeTypeTraits<T>::NumLowBitsAvailable>>
203 using Traits = WTraits;
204 static void setWaymark(T &N, unsigned Tag) { N.setWaymark(Tag); }
205 static unsigned getWaymark(const T &N) { return N.getWaymark(); }
208 template <class T, class WTraits> struct Waymarker<T *, WTraits> {
209 using Traits = WTraits;
210 static void setWaymark(T *&N, unsigned Tag) {
211 reinterpret_cast<uintptr_t &>(N) |= static_cast<uintptr_t>(Tag);
213 static unsigned getWaymark(const T *N) {
214 return static_cast<unsigned>(reinterpret_cast<uintptr_t>(N)) &
219 /// Sets up the waymarking algorithm's tags for a given range [Begin, End).
221 /// \param Begin The beginning of the range to mark with tags (inclusive).
222 /// \param End The ending of the range to mark with tags (exclusive).
223 /// \param Offset The position in the supposed tags array from which to start
224 /// marking the given range.
225 template <class TIter, class Marker = Waymarker<
226 typename std::iterator_traits<TIter>::value_type>>
227 void fillWaymarks(TIter Begin, TIter End, size_t Offset = 0) {
231 size_t Count = Marker::Traits::Tags::Remain;
232 if (Offset <= Marker::Traits::NUM_STATIC_TAGS) {
233 // Start by filling the pre-calculated tags, starting from the given offset.
234 while (Offset != Marker::Traits::NUM_STATIC_TAGS) {
235 Marker::setWaymark(*Begin, Marker::Traits::Tags::Values[Offset]);
244 // The given offset is larger than the number of pre-computed tags, so we
245 // must do it the hard way.
246 // Calculate the next remaining Count, as if we have filled the tags up to
248 size_t Off = Marker::Traits::NUM_STATIC_TAGS;
252 unsigned Tag = Count & Marker::Traits::MARK_MASK;
254 // If the count can fit into the tag, then the counting must stop.
255 if (Count <= Marker::Traits::MARK_MASK) {
256 Tag |= Marker::Traits::STOP_MASK;
259 Count >>= Marker::Traits::MARK_SIZE;
260 } while (Off != Offset);
263 // By now, we have the matching remaining Count for the current offset.
267 unsigned Tag = Count & Marker::Traits::MARK_MASK;
269 // If the count can fit into the tag, then the counting must stop.
270 if (Count <= Marker::Traits::MARK_MASK) {
271 Tag |= Marker::Traits::STOP_MASK;
274 Count >>= Marker::Traits::MARK_SIZE;
276 Marker::setWaymark(*Begin, Tag);
278 } while (Begin != End);
281 /// Sets up the waymarking algorithm's tags for a given range.
283 /// \param Range The range to mark with tags.
284 /// \param Offset The position in the supposed tags array from which to start
285 /// marking the given range.
286 template <typename R, class Marker = Waymarker<typename std::remove_reference<
287 decltype(*std::begin(std::declval<R &>()))>::type>>
288 void fillWaymarks(R &&Range, size_t Offset = 0) {
289 return fillWaymarks<decltype(std::begin(std::declval<R &>())), Marker>(
290 adl_begin(Range), adl_end(Range), Offset);
293 /// Retrieves the element marked with tag of only STOP_MASK, by following the
294 /// waymarks. This is the first element in a range passed to a previous call to
295 /// \c fillWaymarks with \c Offset 0.
297 /// For the trivial usage of calling \c fillWaymarks(Array), and \I is an
298 /// iterator inside \c Array, this function retrieves the head of \c Array, by
299 /// following the waymarks.
301 /// \param I The iterator into an array which was marked by the waymarking tags
302 /// (by a previous call to \c fillWaymarks).
303 template <class TIter, class Marker = Waymarker<
304 typename std::iterator_traits<TIter>::value_type>>
305 TIter followWaymarks(TIter I) {
308 Tag = Marker::getWaymark(*I--);
309 while (!(Tag & Marker::Traits::STOP_MASK));
311 // Special case for the first Use.
312 if (Tag != Marker::Traits::STOP_MASK) {
313 ptrdiff_t Offset = Tag & Marker::Traits::MARK_MASK;
314 while (!((Tag = Marker::getWaymark(*I)) & Marker::Traits::STOP_MASK)) {
315 Offset = (Offset << Marker::Traits::MARK_SIZE) + Tag;
323 } // end namespace llvm
325 #endif // LLVM_ADT_WAYMARKING_H