Index: llvm/include/llvm/ADT/Waymarking.h
===================================================================
--- /dev/null
+++ llvm/include/llvm/ADT/Waymarking.h
@@ -0,0 +1,233 @@
+//===- 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|
+// <_ | | | | | | | | | |
+// <_____ | | | | | | | | |
+// <_________ | | | | | | | |
+// <_____________ | | | | | | |
+// <_____________________ | | | | | |
+// <_____________________________ | | | | |
+// <_____________________________________ | | | |
+// <_____________________________________________ | | |
+// <_____________________________________________________ | |
+// <_____________________________________________________________ |
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_WAYMARKING_H
+#define LLVM_ADT_WAYMARKING_H
+
+#include "llvm/ADT/STLExtras.h"
+
+namespace llvm {
+
+namespace detail {
+
+template <unsigned NumBits> struct WaymarkingTraits {
+ enum : unsigned {
+ NUM_BITS = NumBits,
+
+ MARK_SIZE = NUM_BITS - 1,
+ STOP_MASK = (1 << MARK_SIZE),
+ MARK_MASK = (STOP_MASK - 1),
+ TAG_MASK = (MARK_MASK | STOP_MASK),
+
+ NUM_STATIC_TAGS = 32
+ };
+
+private:
+ template <unsigned Len, bool Stop, unsigned Count, uint8_t... Vals>
+ struct AddTag;
+
+ template <unsigned Len, unsigned Count, uint8_t... Vals> struct GenTag {
+ typedef
+ typename AddTag<Len, (Count <= MARK_MASK), Count, Vals...>::Xdata Xdata;
+ };
+
+ template <unsigned Len, uint8_t... Vals> struct GenOffset {
+ typedef typename GenTag<Len, sizeof...(Vals), Vals...>::Xdata Xdata;
+ };
+
+ 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;
+ };
+
+ 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 {
+ static const unsigned Remain = Count;
+ static const uint8_t Values[sizeof...(Vals)];
+ };
+
+ template <unsigned Count, uint8_t... Vals>
+ struct AddTag<0, false, Count, Vals...> {
+ typedef typename TagsData<Count, Vals...> Xdata;
+ };
+
+ template <unsigned Count, uint8_t... Vals>
+ struct AddTag<0, true, Count, Vals...> {
+ typedef typename 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
+
+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.
+template <class TIter, class Marker = Waymarker<
+ typename std::iterator_traits<TIter>::value_type>>
+void fillWaymarks(TIter Begin, TIter End, size_t Offset = 0) {
+ assert(Offset <= Marker::Traits::NUM_STATIC_TAGS);
+
+ while (true) {
+ if (!(Begin < End))
+ return;
+
+ if (Offset >= Marker::Traits::NUM_STATIC_TAGS)
+ break;
+
+ Marker::setWaymark(*Begin, Marker::Traits::Tags::Values[Offset++]);
+ ++Begin;
+ }
+
+ size_t Count = Marker::Traits::Tags::Remain;
+ 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.
+template <typename R, class Marker = Waymarker<detail::ValueOfRange<R>>>
+void fillWaymarks(R &&Range, size_t Offset = 0) {
+ return fillWaymarks<detail::IterOfRange<R>, Marker>(adl_begin(Range),
+ adl_end(Range), Offset);
+}
+
+/// Retrieves the owning array's head, by following the waymarks.
+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
Index: llvm/include/llvm/IR/Use.h
===================================================================
--- llvm/include/llvm/IR/Use.h
+++ llvm/include/llvm/IR/Use.h
@@ -26,6 +26,7 @@
#include "llvm-c/Types.h"
#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/Waymarking.h"
#include "llvm/Support/CBindingWrapping.h"
#include "llvm/Support/Compiler.h"
@@ -76,18 +77,6 @@
// a pointer back to their User with the bottom bit set.
using UserRef = PointerIntPair<User *, 1, unsigned, UserRefPointerTraits>;
- /// Pointer traits for the Prev PointerIntPair. This ensures we always use
- /// the two LSBs regardless of pointer alignment on different targets.
- struct PrevPointerTraits {
- static inline void *getAsVoidPointer(Use **P) { return P; }
-
- static inline Use **getFromVoidPointer(void *P) {
- return (Use **)P;
- }
-
- enum { NumLowBitsAvailable = 2 };
- };
-
private:
/// Destructor - Only for zap()
~Use() {
@@ -95,10 +84,8 @@
removeFromList();
}
- enum PrevPtrTag { zeroDigitTag, oneDigitTag, stopTag, fullStopTag };
-
/// Constructor
- Use(PrevPtrTag tag) { Prev.setInt(tag); }
+ Use(unsigned tag) { Prev.setInt(tag); }
public:
friend class Value;
@@ -138,9 +125,17 @@
private:
const Use *getImpliedUser() const LLVM_READONLY;
+ using Waymarker =
+ llvm::Waymarker<Use, detail::WaymarkingTraits<PointerLikeTypeTraits<
+ Use **>::NumLowBitsAvailable>>;
+ friend Waymarker;
+
Value *Val = nullptr;
Use *Next = nullptr;
- PointerIntPair<Use **, 2, PrevPtrTag, PrevPointerTraits> Prev;
+ PointerIntPair<Use **, Waymarker::Traits::NUM_BITS, unsigned> Prev;
+
+ void setWaymark(unsigned Tag) { new (this) Use(Tag); }
+ unsigned getWaymark() const { return Prev.getInt(); }
void setPrev(Use **NewPrev) { Prev.setPointer(NewPrev); }
Index: llvm/lib/IR/Use.cpp
===================================================================
--- llvm/lib/IR/Use.cpp
+++ llvm/lib/IR/Use.cpp
@@ -48,38 +48,9 @@
return this - getUser()->op_begin();
}
-// Sets up the waymarking algorithm's tags for a series of Uses. See the
-// algorithm details here:
-//
-// http://www.llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm
-//
Use *Use::initTags(Use *const Start, Use *Stop) {
- ptrdiff_t Done = 0;
- while (Done < 20) {
- if (Start == Stop--)
- return Start;
- static const PrevPtrTag tags[20] = {
- fullStopTag, oneDigitTag, stopTag, oneDigitTag, oneDigitTag,
- stopTag, zeroDigitTag, oneDigitTag, oneDigitTag, stopTag,
- zeroDigitTag, oneDigitTag, zeroDigitTag, oneDigitTag, stopTag,
- oneDigitTag, oneDigitTag, oneDigitTag, oneDigitTag, stopTag};
- new (Stop) Use(tags[Done++]);
- }
-
- ptrdiff_t Count = Done;
- while (Start != Stop) {
- --Stop;
- if (!Count) {
- new (Stop) Use(stopTag);
- ++Done;
- Count = Done;
- } else {
- new (Stop) Use(PrevPtrTag(Count & 1));
- Count >>= 1;
- ++Done;
- }
- }
-
+ std::reverse_iterator<Use *> From(Stop), To(Start);
+ fillWaymarks<decltype(To), Waymarker>(From, To);
return Start;
}
@@ -90,37 +61,30 @@
::operator delete(Start);
}
-const Use *Use::getImpliedUser() const {
- const Use *Current = this;
-
- while (true) {
- unsigned Tag = (Current++)->Prev.getInt();
- switch (Tag) {
- case zeroDigitTag:
- case oneDigitTag:
- continue;
-
- case stopTag: {
- ++Current;
- ptrdiff_t Offset = 1;
- while (true) {
- unsigned Tag = Current->Prev.getInt();
- switch (Tag) {
- case zeroDigitTag:
- case oneDigitTag:
- ++Current;
- Offset = (Offset << 1) + Tag;
- continue;
- default:
- return Current + Offset;
- }
- }
- }
-
- case fullStopTag:
- return Current;
- }
+namespace {
+struct FollowWaymarksIterator {
+ const Use *U;
+ FollowWaymarksIterator(const Use *U) : U(U) {}
+ const Use &operator*() const { return *U; }
+ FollowWaymarksIterator &operator++() {
+ --U;
+ return *this;
+ }
+ FollowWaymarksIterator &operator--() {
+ ++U;
+ return *this;
}
+ FollowWaymarksIterator operator--(int) { return U++; }
+ FollowWaymarksIterator &operator-=(const ptrdiff_t Offset) {
+ U += Offset;
+ return *this;
+ }
+};
+} // end anonymous namespace
+
+const Use *Use::getImpliedUser() const {
+ FollowWaymarksIterator It(this);
+ return &*followWaymarks<decltype(It), Waymarker>(It) + 1;
}
-} // End llvm namespace
+} // end namespace llvm