LLVM  14.0.0git
Waymarking.h
Go to the documentation of this file.
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"
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.
129 
130  // The number of pre-computed tags (for fast fill).
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>
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  // If the count can fit into the tag, then the counting must stop.
253  if (Count <= Marker::Traits::MARK_MASK) {
254  Count = Off;
255  } else
256  Count >>= Marker::Traits::MARK_SIZE;
257  } while (Off != Offset);
258  }
259 
260  // By now, we have the matching remaining Count for the current offset.
261  do {
262  ++Offset;
263 
264  unsigned Tag = Count & Marker::Traits::MARK_MASK;
265 
266  // If the count can fit into the tag, then the counting must stop.
267  if (Count <= Marker::Traits::MARK_MASK) {
268  Tag |= Marker::Traits::STOP_MASK;
269  Count = Offset;
270  } else
271  Count >>= Marker::Traits::MARK_SIZE;
272 
273  Marker::setWaymark(*Begin, Tag);
274  ++Begin;
275  } while (Begin != End);
276 }
277 
278 /// Sets up the waymarking algorithm's tags for a given range.
279 ///
280 /// \param Range The range to mark with tags.
281 /// \param Offset The position in the supposed tags array from which to start
282 /// marking the given range.
283 template <typename R, class Marker = Waymarker<typename std::remove_reference<
284  decltype(*std::begin(std::declval<R &>()))>::type>>
285 void fillWaymarks(R &&Range, size_t Offset = 0) {
286  return fillWaymarks<decltype(std::begin(std::declval<R &>())), Marker>(
287  adl_begin(Range), adl_end(Range), Offset);
288 }
289 
290 /// Retrieves the element marked with tag of only STOP_MASK, by following the
291 /// waymarks. This is the first element in a range passed to a previous call to
292 /// \c fillWaymarks with \c Offset 0.
293 ///
294 /// For the trivial usage of calling \c fillWaymarks(Array), and \I is an
295 /// iterator inside \c Array, this function retrieves the head of \c Array, by
296 /// following the waymarks.
297 ///
298 /// \param I The iterator into an array which was marked by the waymarking tags
299 /// (by a previous call to \c fillWaymarks).
300 template <class TIter, class Marker = Waymarker<
301  typename std::iterator_traits<TIter>::value_type>>
302 TIter followWaymarks(TIter I) {
303  unsigned Tag;
304  do
305  Tag = Marker::getWaymark(*I--);
306  while (!(Tag & Marker::Traits::STOP_MASK));
307 
308  // Special case for the first Use.
309  if (Tag != Marker::Traits::STOP_MASK) {
310  ptrdiff_t Offset = Tag & Marker::Traits::MARK_MASK;
311  while (!((Tag = Marker::getWaymark(*I)) & Marker::Traits::STOP_MASK)) {
312  Offset = (Offset << Marker::Traits::MARK_SIZE) + Tag;
313  --I;
314  }
315  I -= Offset;
316  }
317  return ++I;
318 }
319 
320 } // end namespace llvm
321 
322 #endif // LLVM_ADT_WAYMARKING_H
llvm::detail::WaymarkingTraits::STOP_MASK
@ STOP_MASK
Definition: Waymarking.h:126
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::followWaymarks
TIter followWaymarks(TIter I)
Retrieves the element marked with tag of only STOP_MASK, by following the waymarks.
Definition: Waymarking.h:302
llvm::detail::WaymarkingTraits::NUM_BITS
@ NUM_BITS
Definition: Waymarking.h:122
llvm::Waymarker::setWaymark
static void setWaymark(T &N, unsigned Tag)
Definition: Waymarking.h:204
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
llvm::detail::WaymarkingTraits
Definition: Waymarking.h:119
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::detail::WaymarkingTraits::Tags
GenOffset< NUM_STATIC_TAGS >::Xdata Tags
Definition: Waymarking.h:188
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
STLExtras.h
llvm::dwarf::Tag
Tag
Definition: Dwarf.h:104
llvm::Waymarker< T *, WTraits >::Traits
WTraits Traits
Definition: Waymarking.h:209
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:193
ptrdiff_t
llvm::adl_end
decltype(auto) adl_end(ContainerTy &&container)
Definition: STLExtras.h:242
llvm::fillWaymarks
void fillWaymarks(TIter Begin, TIter End, size_t Offset=0)
Sets up the waymarking algorithm's tags for a given range [Begin, End).
Definition: Waymarking.h:227
false
Definition: StackSlotColoring.cpp:142
llvm::detail::WaymarkingTraits::TAG_MASK
@ TAG_MASK
Definition: Waymarking.h:128
PointerLikeTypeTraits.h
llvm::detail::WaymarkingTraits::NUM_STATIC_TAGS
@ NUM_STATIC_TAGS
Definition: Waymarking.h:131
llvm::Waymarker::getWaymark
static unsigned getWaymark(const T &N)
Definition: Waymarking.h:205
type
AMD64 Optimization Manual has some nice information about optimizing integer multiplication by a constant How much of it applies to Intel s X86 implementation There are definite trade offs to xmm0 cvttss2siq rdx jb L3 subss xmm0 rax cvttss2siq rdx xorq rdx rax ret instead of xmm1 cvttss2siq rcx movaps xmm2 subss xmm2 cvttss2siq rax rdx xorq rax ucomiss xmm0 cmovb rax ret Seems like the jb branch has high likelihood of being taken It would have saved a few instructions It s not possible to reference and DH registers in an instruction requiring REX prefix divb and mulb both produce results in AH If isel emits a CopyFromReg which gets turned into a movb and that can be allocated a r8b r15b To get around isel emits a CopyFromReg from AX and then right shift it down by and truncate it It s not pretty but it works We need some register allocation magic to make the hack go which would often require a callee saved register Callees usually need to keep this value live for most of their body so it doesn t add a significant burden on them We currently implement this in however this is suboptimal because it means that it would be quite awkward to implement the optimization for callers A better implementation would be to relax the LLVM IR rules for sret arguments to allow a function with an sret argument to have a non void return type
Definition: README-X86-64.txt:70
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::Waymarker< T *, WTraits >::setWaymark
static void setWaymark(T *&N, unsigned Tag)
Definition: Waymarking.h:210
llvm::Waymarker
This class is responsible for tagging (and retrieving the tag of) a given element of type T.
Definition: Waymarking.h:202
llvm::detail::WaymarkingTraits::MARK_SIZE
@ MARK_SIZE
Definition: Waymarking.h:125
llvm::pdb::DbgHeaderType::Xdata
@ Xdata
llvm::adl_begin
decltype(auto) adl_begin(ContainerTy &&container)
Definition: STLExtras.h:237
llvm::detail::WaymarkingTraits::MARK_MASK
@ MARK_MASK
Definition: Waymarking.h:127
N
#define N
llvm::Waymarker::Traits
WTraits Traits
Definition: Waymarking.h:203
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1815
llvm::Waymarker< T *, WTraits >::getWaymark
static unsigned getWaymark(const T *N)
Definition: Waymarking.h:213