326 lines
12 KiB
C++
326 lines
12 KiB
C++
//===- 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 <unsigned NumBits> struct WaymarkingTraits {
|
|
enum : unsigned {
|
|
// The number of bits of a Waymarking Tag.
|
|
NUM_BITS = NumBits,
|
|
|
|
// A Tag is composed from a Mark and a Stop mask.
|
|
MARK_SIZE = NUM_BITS - 1,
|
|
STOP_MASK = (1 << MARK_SIZE),
|
|
MARK_MASK = (STOP_MASK - 1),
|
|
TAG_MASK = (MARK_MASK | STOP_MASK),
|
|
|
|
// The number of pre-computed tags (for fast fill).
|
|
NUM_STATIC_TAGS = 32
|
|
};
|
|
|
|
private:
|
|
// Add a new tag, calculated from Count and Stop, to the Vals pack, while
|
|
// continuing recursively to decrease Len down to 0.
|
|
template <unsigned Len, bool Stop, unsigned Count, uint8_t... Vals>
|
|
struct AddTag;
|
|
|
|
// Delegate to the specialized AddTag according to the need of a Stop mask.
|
|
template <unsigned Len, unsigned Count, uint8_t... Vals> struct GenTag {
|
|
typedef
|
|
typename AddTag<Len, (Count <= MARK_MASK), Count, Vals...>::Xdata Xdata;
|
|
};
|
|
|
|
// Start adding tags while calculating the next Count, which is actually the
|
|
// number of already calculated tags (equivalent to the position in the
|
|
// array).
|
|
template <unsigned Len, uint8_t... Vals> struct GenOffset {
|
|
typedef typename GenTag<Len, sizeof...(Vals), Vals...>::Xdata Xdata;
|
|
};
|
|
|
|
// Add the tag and remove it from Count.
|
|
template <unsigned Len, unsigned Count, uint8_t... Vals>
|
|
struct AddTag<Len, false, Count, Vals...> {
|
|
typedef typename GenTag<Len - 1, (Count >> MARK_SIZE), Vals...,
|
|
Count & MARK_MASK>::Xdata Xdata;
|
|
};
|
|
|
|
// We have reached the end of this Count, so start with a new Count.
|
|
template <unsigned Len, unsigned Count, uint8_t... Vals>
|
|
struct AddTag<Len, true, Count, Vals...> {
|
|
typedef typename GenOffset<Len - 1, Vals...,
|
|
(Count & MARK_MASK) | STOP_MASK>::Xdata Xdata;
|
|
};
|
|
|
|
template <unsigned Count, uint8_t... Vals> struct TagsData {
|
|
// The remaining number for calculating the next tag, following the last one
|
|
// in Values.
|
|
static const unsigned Remain = Count;
|
|
|
|
// The array of ordered pre-computed Tags.
|
|
static const uint8_t Values[sizeof...(Vals)];
|
|
};
|
|
|
|
// Specialize the case when Len equals 0, as the recursion stop condition.
|
|
template <unsigned Count, uint8_t... Vals>
|
|
struct AddTag<0, false, Count, Vals...> {
|
|
typedef TagsData<Count, Vals...> Xdata;
|
|
};
|
|
|
|
template <unsigned Count, uint8_t... Vals>
|
|
struct AddTag<0, true, Count, Vals...> {
|
|
typedef TagsData<Count, Vals...> Xdata;
|
|
};
|
|
|
|
public:
|
|
typedef typename GenOffset<NUM_STATIC_TAGS>::Xdata Tags;
|
|
};
|
|
|
|
template <unsigned NumBits>
|
|
template <unsigned Count, uint8_t... Vals>
|
|
const uint8_t WaymarkingTraits<NumBits>::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 <class T, class WTraits = detail::WaymarkingTraits<
|
|
PointerLikeTypeTraits<T>::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 <class T, class WTraits> struct Waymarker<T *, WTraits> {
|
|
using Traits = WTraits;
|
|
static void setWaymark(T *&N, unsigned Tag) {
|
|
reinterpret_cast<uintptr_t &>(N) |= static_cast<uintptr_t>(Tag);
|
|
}
|
|
static unsigned getWaymark(const T *N) {
|
|
return static_cast<unsigned>(reinterpret_cast<uintptr_t>(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 <class TIter, class Marker = Waymarker<
|
|
typename std::iterator_traits<TIter>::value_type>>
|
|
void fillWaymarks(TIter Begin, TIter End, size_t Offset = 0) {
|
|
if (Begin == End)
|
|
return;
|
|
|
|
size_t Count = Marker::Traits::Tags::Remain;
|
|
if (Offset <= Marker::Traits::NUM_STATIC_TAGS) {
|
|
// Start by filling the pre-calculated tags, starting from the given offset.
|
|
while (Offset != Marker::Traits::NUM_STATIC_TAGS) {
|
|
Marker::setWaymark(*Begin, Marker::Traits::Tags::Values[Offset]);
|
|
|
|
++Offset;
|
|
++Begin;
|
|
|
|
if (Begin == End)
|
|
return;
|
|
}
|
|
} else {
|
|
// The given offset is larger than the number of pre-computed tags, so we
|
|
// must do it the hard way.
|
|
// Calculate the next remaining Count, as if we have filled the tags up to
|
|
// the given offset.
|
|
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);
|
|
}
|
|
|
|
// By now, we have the matching remaining Count for the current 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 <typename R, class Marker = Waymarker<typename std::remove_reference<
|
|
decltype(*std::begin(std::declval<R &>()))>::type>>
|
|
void fillWaymarks(R &&Range, size_t Offset = 0) {
|
|
return fillWaymarks<decltype(std::begin(std::declval<R &>())), 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 <class TIter, class Marker = Waymarker<
|
|
typename std::iterator_traits<TIter>::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
|