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 115 namespace llvm { 116 117 namespace detail { 118 119 template <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 134 private: 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 187 public: 188 typedef typename GenOffset<NUM_STATIC_TAGS>::Xdata Tags; 189 }; 190 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...}; 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. 200 template <class T, class WTraits = detail::WaymarkingTraits< 201 PointerLikeTypeTraits<T>::NumLowBitsAvailable>> 202 struct 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 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); 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. 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) { 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. 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); 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). 303 template <class TIter, class Marker = Waymarker< 304 typename std::iterator_traits<TIter>::value_type>> 305 TIter 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