1//===- Waymarking.h - Array waymarking algorithm ----------------*- C++ -*-===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
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.
12//
13// A Tag of n-bits (in size) is composed as follows:
14//
15// bits: | n-1 | n-2 ... 0 |
16// .---------.------------------------------------.
17// |Stop Mask|(2^(n-1))-ary numeric system - digit|
18// '---------'------------------------------------'
19//
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.
28//
29// For example:
30// In case of 2 bits:
31//
32// Tags:
33// x0 - binary digit 0
34// x1 - binary digit 1
35// 1x - stop and calculate (s)
36//
37// Array:
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
42// <_ | | | | | |
43// <_____ | | | | |
44// <_____________ | | | |
45// <_________________________ | | |
46// <_____________________________________ | |
47// <_____________________________________________________ |
48//
49//
50// In case of 3 bits:
51//
52// Tags:
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)
58//
59// Array:
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// <_____________________________________________________________ |
74//
75//
76// The API introduce 2 functions:
77// 1. fillWaymarks
78// 2. followWaymarks
79//
80// Example:
81// int N = 10;
82// int M = 5;
83// int **A = new int *[N + M]; // Define the array.
84// for (int I = 0; I < N + M; ++I)
85// A[I] = new int(I);
86//
87// fillWaymarks(A, A + N); // Set the waymarks for the first N elements
88// // of the array.
89// // Note that it must be done AFTER we fill
90// // the array's elements.
91//
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.
95//
96// ... // Elements which will be changed after the
97// // call to fillWaymarks, will have to be
98// // retagged.
99//
100// fillWaymarks(A + N, A + N + M, N); // Set the waymarks of the remaining M
101// // elements.
102// ...
103// int **It = A + N + 1;
104// int **B = followWaymarks(It); // Find the head of the array containing It.
105// assert(B == A);
106//
107//===----------------------------------------------------------------------===//
108
109#ifndef LLVM_ADT_WAYMARKING_H
110#define LLVM_ADT_WAYMARKING_H
111
112#include "llvm/ADT/STLExtras.h"
113#include "llvm/Support/PointerLikeTypeTraits.h"
114
115namespace llvm {
116
117namespace detail {
118
119template <unsigned NumBits> struct WaymarkingTraits {
120 enum : unsigned {
121 // The number of bits of a Waymarking Tag.
122 NUM_BITS = NumBits,
123
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),
129
130 // The number of pre-computed tags (for fast fill).
131 NUM_STATIC_TAGS = 32
132 };
133
134private:
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>
138 struct AddTag;
139
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 {
142 typedef
143 typename AddTag<Len, (Count <= MARK_MASK), Count, Vals...>::Xdata Xdata;
144 };
145
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
148 // array).
149 template <unsigned Len, uint8_t... Vals> struct GenOffset {
150 typedef typename GenTag<Len, sizeof...(Vals), Vals...>::Xdata Xdata;
151 };
152
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;
158 };
159
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;
165 };
166
167 template <unsigned Count, uint8_t... Vals> struct TagsData {
168 // The remaining number for calculating the next tag, following the last one
169 // in Values.
170 static const unsigned Remain = Count;
171
172 // The array of ordered pre-computed Tags.
173 static const uint8_t Values[sizeof...(Vals)];
174 };
175
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;
180 };
181
182 template <unsigned Count, uint8_t... Vals>
183 struct AddTag<0, true, Count, Vals...> {
184 typedef TagsData<Count, Vals...> Xdata;
185 };
186
187public:
188 typedef typename GenOffset<NUM_STATIC_TAGS>::Xdata Tags;
189};
190
191template <unsigned NumBits>
192template <unsigned Count, uint8_t... Vals>
193const uint8_t WaymarkingTraits<NumBits>::TagsData<
194 Count, Vals...>::Values[sizeof...(Vals)] = {Vals...};
195
196} // end namespace detail
197
198/// This class is responsible for tagging (and retrieving the tag of) a given
199/// element of type T.
200template <class T, class WTraits = detail::WaymarkingTraits<
201 PointerLikeTypeTraits<T>::NumLowBitsAvailable>>
202struct Waymarker {
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(); }
206};
207
208template <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);
212 }
213 static unsigned getWaymark(const T *N) {
214 return static_cast<unsigned>(reinterpret_cast<uintptr_t>(N)) &
215 Traits::TAG_MASK;
216 }
217};
218
219/// Sets up the waymarking algorithm's tags for a given range [Begin, End).
220///
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.
225template <class TIter, class Marker = Waymarker<
226 typename std::iterator_traits<TIter>::value_type>>
227void fillWaymarks(TIter Begin, TIter End, size_t Offset = 0) {
228 if (Begin == End)
229 return;
230
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]);
236
237 ++Offset;
238 ++Begin;
239
240 if (Begin == End)
241 return;
242 }
243 } else {
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
247 // the given offset.
248 size_t Off = Marker::Traits::NUM_STATIC_TAGS;
249 do {
250 ++Off;
251
252 unsigned Tag = Count & Marker::Traits::MARK_MASK;
253
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;
257 Count = Off;
258 } else
259 Count >>= Marker::Traits::MARK_SIZE;
260 } while (Off != Offset);
261 }
262
263 // By now, we have the matching remaining Count for the current offset.
264 do {
265 ++Offset;
266
267 unsigned Tag = Count & Marker::Traits::MARK_MASK;
268
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;
272 Count = Offset;
273 } else
274 Count >>= Marker::Traits::MARK_SIZE;
275
276 Marker::setWaymark(*Begin, Tag);
277 ++Begin;
278 } while (Begin != End);
279}
280
281/// Sets up the waymarking algorithm's tags for a given range.
282///
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.
286template <typename R, class Marker = Waymarker<typename std::remove_reference<
287 decltype(*std::begin(std::declval<R &>()))>::type>>
288void 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);
291}
292
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.
296///
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.
300///
301/// \param I The iterator into an array which was marked by the waymarking tags
302/// (by a previous call to \c fillWaymarks).
303template <class TIter, class Marker = Waymarker<
304 typename std::iterator_traits<TIter>::value_type>>
305TIter followWaymarks(TIter I) {
306 unsigned Tag;
307 do
308 Tag = Marker::getWaymark(*I--);
309 while (!(Tag & Marker::Traits::STOP_MASK));
310
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;
316 --I;
317 }
318 I -= Offset;
319 }
320 return ++I;
321}
322
323} // end namespace llvm
324
325#endif // LLVM_ADT_WAYMARKING_H
326