constexpr pointer tagging

This paper proposes a new library non-owning pointer and value pair which has ability to store small amount of information in a tag in alignment low-bits. This functionality is also usable in constexpr environment so. It's meant to be a building tool to build more advanced data-structures and also last requirement for atomic<std::shared_ptr<T>> to be constexpr.

Revision history

• R2 → R3: polishing design and added wording
• R1 → R2: simplifying design by removing schemas and the heavy interface, massive simplification as discussed in SG1 (pointer_tag_pair, required sizeof(pointer_tag_pair) == sizeof(T*))
• R0 → R1: proposing and explaining design based on existing implementation

Introduction and motivation

Pointer tagging is widely known and used technique (Glasgow Haskell Compiler, LLVM's PointerIntPair, PointerUnion, CPython's garbage collector, Objective C / Swift, Chrome's V8 JavaScript engine, GAP, OCaml, PBRT). All major CPU vendors provides mechanism for pointer tagging (Intel's LAM linear address masking, AMD's Upper Address Ignore, ARM's TBI top byte ignore and MTE memory tagging extension). All widely used 64 bit platforms are not using more than 48 or 49 bits of the pointers.

This functionality widely supported can't be expressed in a standard conforming way.

Rust, Dlang, or Zig has an interface for pointer tagging. This is demonstrating demand for the feature and C++ should have it too and it should also work in constexpr.

Generally programmer can consider low-bits used for alignment to be safely used for storing an information. Upper bits are available on different platforms under different conditions (runtime processor setting, CPU generation, ...). This proposal only proposes interface to accessing low bits for storing // reading a tag value, not observing bits of a pointer.

This proposal doesn't propose accessing any other bits other than low-bits which are known to be zero due alignment. SG1 doesn't want to standardize access to high-bits as it's considered dangerous and non-portable. And can limit future development of security features in OS and CPUs for which high-bits are used.

Use cases

There are three basic use-cases of pointer tagging:

• marking pointer with an information (in allocators, used as a tiny refcount, or marking source of the pointer)
• pointee polymorphism (usually in data structures, eg. in trees: next node can be an internal node or a leaf)
• in-place polymorphism (similarly as variant, some bits stores an information about rest of payload, it can be a pointer, a number, a float, a small string, ...)

This paper aims to solve only first two use-cases.

Safety

Pointer tagging can be currently implemented in C++ only with reinterpret_cast and bit manipulating with shifts / bitand / bitor and this approach is prone to be unsafe and hard to debug as it's not expressed clearly in code what is the right intention, so compiler can't even diagnose incompatibility between encode/decode. By giving a name to this tool it allows programmer to express intent clearly and compiler to optimize and diagnose problems properly.

Preconditions and mandates of proposed std::pointer_tag_pair makes it unlike to use it unsafely as potentially dangerous operations (std::pointer_tag_pair<Pointee, Tag, Bits>::from_tagged(pointer) and std::pointer_tag_pair<Pointee, Tag, Bits>::template from_overaligned<PromisedAlignment>(pointer)) are verbose and visible.

Unsafe operations

Two mentioned functions are provided so user can explicitly provide over-aligned pointer which would otherwise won't be compatible with number of requested bits or interact with existing functionality for pointer tagging (which will allow gradual adoption of the feature and replace old code).

Examples

HAMT early leaves

Following example is a recursive search implementation for a HAMT (hash-array-mapped-trie) data structure. Where a tag value indicates leaf node.

// requesting only 1 bit of information
using hamt_node_pointer = std::pointer_tag_pair<const void, bool, 1>;
static_assert(sizeof(hamt_node_pointer) == sizeof(void *));

constexpr const T * find_value_in_hamt(hamt_node_pointer tptr, uint32_t hash) {
	if (tptr == nullptr) // checks only pointer part
		return nullptr;
	
	if (tptr.tag()) // we found leaf node, tag is boolean as specified
		return *static_cast<const T *>(tptr.pointer());
	
	const auto * node = static_cast<const internal_node *>(tptr.pointer());
	const auto next_node = node[hash & 0b1111u];
	
	return find_value_in_hamt(next_node, hash >> 4); // recursive descend
}

Smart (non-)owning pointer

This example shows maybe_owning_ptr type which can be both a reference or an owner:

template <typename T> class maybe_owning_ptr {
  enum class ownership: unsigned {
    reference,
    owning,
  };
  
  std::pointer_tag_pair<T, ownership, 1> _ptr;
public:
  constexpr maybe_owning_ptr(T* && pointer) noexcept: _ptr{pointer, ownership::owning} { }
  constexpr maybe_owning_ptr(T & ref) noexcept: _ptr{&ref, ownership::reference} { }
  
  constexpr decltype(auto) operator*() const noexcept {
    return *_ptr.pointer();
  }
  
  constexpr T * operator->() const noexcept {
    return _ptr.pointer();
  }
  
  constexpr ~maybe_owning_ptr() noexcept {
    if (_ptr.tag() == ownership::owning) {
      delete _ptr.pointer();
    }
  }
};

static_assert(sizeof(maybe_owning_ptr<int>) == sizeof(int *));

LLVM's L-value

Following code is simplification of LLVM's representation of pointer/reference type which is implemented with LLVM's PointerIntPair and is inside constant evaluator. This type holds subnodes of different kind: pointer to local/static variable, dynamic allocation, type info pointer, result of temporary.

struct LValueBase {
	using PtrTy = llvm::PointerUnion<const ValueDecl *, 
                                    const Expr *,
                                    TypeInfoLValue,
                                    DynamicAllocLValue>;

	struct PathEntry {
		uint64_t value;
	};
	
	using PathTy = std::vector<PathEntry>;
	
	PtrTy Location;
	PathEntry SubObjectPath;
};

APValue DereferencePointer(EvalInfo & Context, const LValueBase & Base) {
	auto & object = Context.Visit(Base.Location);
	return object.NavigateToSuboject(Base.SubObjectPath);
}

Implementation experience

Old version of this proposal has been implemented within libc++ & clang and it is accessible on github and compiler explorer. This functionality can't be implemented as a pure library (reinterpret_cast is not allowed during constant evaluation) and needs compiler support in some form.

Implementation in the library

Library is providing a special pair-like type containing pointer and small tag type, and user requested number of bits. The number of bits is by default deduced by default alignment of requested pointee type. Requesting more bits than alignment will disable normal constructor, and force user to use ::from_overaligned function as overalignment is not part of C++'s type system.

In terms of library design there is nothing surprising, and it's pretty straightforward wrapper which encode and decode tagged pointer on its boundaries and provides basic pointer functionality.

Accessing raw tagged pointers

The pointer int pair has support to access raw tagged pointer. Which is a pointer which can't be dereferenced or otherwise manipulated with, it's an opaque value usable only with legacy tagging interface or it can be used to construct pointer_tag_pair back from it. Existence of this interface allows ability to store such pointers in existing interfaces (atomic, other smart pointers). Question is if it should be uintptr_t or void*. I prefer void* as roundtriping thru an integer looses information about provenance and can disable some optimization.

Implementation in the compiler

The implementation is providing builtins to manipulating raw pointers and isn't meant to be used by end-users, only to allow this library functionality.

Compiler builtins

Implementation needs to manipulate pointers without casting them to integers and back. To do so the provided set of builtins is designed to store/load a value (with size of few bits) into/from unimportant/unused bits of a pointer without observing actual pointer representation.

Constant evaluation

With these builtins it's trivial to implement semantically identical behaviour for the constant evaluation. In case of my implementation, pointers in clang are not represented as addresses but as symbols (original AST variable, allocation, static object + path to subobject, its provenance) and there is no address to manipulate. Actual tag value in such "pointer" is then stored in a metadata of the pointer itself and builtins only provide access to it. Technically such storage can provide more bits than pointer "size", but there are internal checks which make sure it allows only bits which would be accessible in runtime based on alignment of individual pointer.

Any attempt to deference or otherwise manipulate such pointer, which would be unsafe in runtime, is detected and reported by the interpreter. Only the provided builtins can recover original pointer and tag value.

Pointer provenance and optimization

Easiest way to implement builtins for pointer tagging is to do the same thing reinterpret_cast is doing, which was my first implementation approach. But this approach leads to loosing pointer's provenance and compiler loosing information which otherwise should be accessible for optimizer to use.

For unmasking there is already ptr.mask LLVM's builtin, but there is no similar intrinsic to do the tagging. Hence the builtins needs to interact with backend and be implemented with a low level backend intrinsic to do the right thing. This shows how actually unimplementable pointer tagging is in existing language.

Alternative constexpr compatible implementation

Alternative way to implement constexpr support (for compiler which don't have heavy pointer representation in their interprets) is inserting a hidden intermediate object holding the metadata and pointer to original object. This allows exactly same semantic as the metadata approach, and can be completely implemented in library using if consteval, but it will need allocation during constant evaluation.

Design

The std::pointer_int_pair is simple pair-like template providing only necessory interface and is not meant to provide heavy interface as it's preferable to not hide pointer tagging / untagging from users. This is mean to be a low-level facility. Main requirement on the type is it must be always same size as stored pointer and not more.

template <typename PointeeT, typename TagT, unsigned BitsRequested = std::countr_zero(alignof(PointeeT))>
	requires(std::is_object_v<PointeeT> && std::is_unsigned_v<_underlying_type_or_identity_t<TagT>> &&
					 std::is_same_v<TagT, std::remove_cvref_t<TagT>> && (BitsRequested < sizeof(PointeeT*) * CHAR_BIT))
struct pointer_tag_pair {
public:
	using element_type				= PointeeT;
	using pointer_type				= element_type*;
	using tagged_pointer_type = void*; // I prefer `void *` to avoid loosing provenance
	using tag_type						= TagT;

private:
	// exposition only
	static constexpr unsigned alignment-needed = (1u << BitsRequested);
	static constexpr /* unsigned-integer */ tag-mask = (alignment-needed - 1u);
	static constexpr /* unsigned-integer */ pointer-mask = ~tag-mask;
	using numeric-tag = _underlying_type_or_identity_t<tag_type>;

	// conversion to numeric tags
	static constexpr numeric-tag to-numeric-tag(tag_type) noexcept;
	static constexpr tag_type from-numeric-tag(numeric-tag) noexcept;

	// required to have size same as sizeof(Pointee *)
	unspecified-pointer-like-type internal-pointer = nullptr; 

	// internal constructor for `from_overaligned` and `from_tagged` functions
	explicit constexpr pointer_tag_pair(unspecified-pointer-like-type ptr) noexcept : internal-pointer{ptr} {}


public:
	pointer_tag_pair() = default;
	pointer_tag_pair(nullptr_t) = default;
	pointer_tag_pair(const pointer_tag_pair&) = default;
	pointer_tag_pair(pointer_tag_pair&&) = default;
	pointer_tag_pair& operator=(const pointer_tag_pair&) = default;
	pointer_tag_pair& operator=(pointer_tag_pair&&) = default;
	~pointer_tag_pair() = default;

	// Precondition: alignment of `ptr` >= `alignment-needed`
	// Precondition: `tag` value is representable in its underlying type within bit field 
	//   of size `BitsRequested` bits or value of `tag` is equal to zero
	constexpr pointer_tag_pair(pointer_type ptr, tag_type tag)
		requires(alignof(element_type) >= alignment-needed): internal-pointer{
			__builtin_tag_pointer_mask_or(ptr, to-numeric-tag(tag), tag-mask)
		} { }

	// Precondition: alignment of `ptr` >= `PromisedAlignment`
	// Precondition: `tag` value is representable in its underlying type within bit field
	//   of size `BitsRequested` bits or value of `tag` is equal to zero
	template <unsigned PromisedAlignment>
	static constexpr pointer_tag_pair from_overaligned(pointer_type ptr, tag_type tag)
		requires(PromisedAlignment >= alignment-needed)
	{
		return pointer_tag_pair{static_cast<unspecified-pointer-like-type>(
			__builtin_tag_pointer_mask_or(ptr, to-numeric-tag(tag), tag-mask)
		)};
	}

	// Precondition: valid pointer if untagged
	static pointer_tag_pair from_tagged(tagged_pointer_type ptr) { // no-constexpr
		return pointer_tag_pair{reinterpret_cast<unspecified-pointer-like-type>(ptr)};
	}

	// access tagged pointer (for interaction with existing tagging mechanisms)
	tagged_pointer_type tagged_pointer() const noexcept { 
		return reinterpret_cast<tagged_pointer_type>(internal-pointer);
	}
	
	// access untagged pointer
	constexpr pointer_type pointer() const noexcept {
		return static_cast<pointer_type>(__builtin_tag_pointer_mask(internal-pointer, pointer-mask));
	}
	
	// access tag value
	constexpr tag_type tag() const noexcept {
		return _from_bitfield_tag(__builtin_tag_pointer_mask_as_int(internal-pointer, tag-mask));
	}

	// swap
	friend constexpr void swap(pointer_tag_pair& lhs, pointer_tag_pair& rhs) noexcept { std::swap(lhs.internal-pointer, rhs.internal-pointer); }

	// comparing {pointer(), tag()} <=> {pointer(), tag()} for consistency
	friend constexpr auto operator<=>(pointer_tag_pair lhs, pointer_tag_pair rhs) noexcept {
		return std::tuple(lhs.pointer(), lhs.tag()) <=> std::tuple(rhs.pointer(), rhs.tag());
	}

	friend bool operator==(pointer_tag_pair, pointer_tag_pair) = default;
};

Preconditions and eligibility of constructors

Constructor taking a pointer and tag value is only available if alignment of the pointee type is enough to store requested number of bits.

Both the constructor and ::from_overaligned function have preconditions checking if pointer is aligned enough as expected (in the constructor) or promised overaligned (in the ::from_overaligned function). In addition to this there is a precondition to make sure value of tag type is representible with RequestedBits.

Representation of tag value

Tag value can only be unsigned integral type or an enum type with underlying unsigned integral type. The value is converted to the underlying or kepy original unsigned integral type and then it is bit masked with mask based on BitsRequested bits (1u << BitsRequested - 1u).

It's precondition failure for the value after this conversion different than original value. An attempt was made to support signed type, but unfortunetely storing unrepresentable value into a bitfield is implementation specific. And this can be added later as extension to current design.

Converting to bit representation

template <typename T> struct underlying_type_or_identity {
  using type = T;
};

template <typename T> requires(std::is_enum_v<T>) struct underlying_type_or_identity<T> {
  using type = std::underlying_type_t<T>;
};

static constexpr auto to-bitfield-tag(tag_type _tag) {
  using underlying_type = underlying_type_or_identity<tag_type>::type;
  
  if constexpr (Bits == 0) {
    PRECONDITION-CHECK(0 == (static_cast<underlying_type>(_tag)), "Only zero is representable with Bits == 0");
    return underlying_type{0};
  } else {
    struct {
      underlying_type _value : Bits;
    } _helper{._value = static_cast<underlying_type>(_tag)};
    
    PRECONDITION-CHECK(_helper._value == (static_cast<underlying_type>(_tag)), "Value is not representable in requested amount of Bits.");
    
    return _helper._value;
  }
}

static constexpr auto from-bitfield-tag(std::size_t _tag) -> tag_type {
  using underlying_type = underlying_type_or_identity<tag_type>::type;

  if constexpr (Bits == 0) {
    return tag_type{0};
  } else {
    struct {
      underlying_type _value : Bits;
    } _helper{._value = static_cast<underlying_type>(_tag)};

   return tag_type{_helper._value};
  }
}

Tuple protocol

pointer_tag_pair supports being destructured, but it doesn't model tuple-like (as it would open whole can of worms, as told by STL). But following code should work:

auto [ptr, tag] = a_pointer_tag_pair;

template <typename Pointee, typename Tag, unsigned BitsRequested>
struct tuple_size<pointer_tag_pair<Pointee, Tag, BitsRequested>> : std::integral_constant<std::size_t, 2> {};

template <typename Pointee, typename Tag, unsigned BitsRequested>
struct tuple_element<0, pointer_tag_pair<Pointee, Tag, BitsRequested>> {
  using type = Pointee*;
};

template <typename Pointee, typename Tag, unsigned BitsRequested>
struct tuple_element<1, pointer_tag_pair<Pointee, Tag, BitsRequested>> {
  using type = Tag;
};

template <typename Pointee, typename Tag, unsigned BitsRequested>
struct tuple_element<0, const pointer_tag_pair<Pointee, Tag, BitsRequested>> {
  using type = Pointee*;
};

template <typename Pointee, typename Tag, unsigned BitsRequested>
struct tuple_element<1, const pointer_tag_pair<Pointee, Tag, BitsRequested>> {
  using type = Tag;
};

template <size_t I, typename Pointee, typename Tag, unsigned BitsRequested>
constexpr auto get(pointer_tag_pair<Pointee, Tag, BitsRequested> pair) noexcept
    -> tuple_element<I, pointer_tag_pair<Pointee, Tag, BitsRequested>>::type {
  if constexpr (I == 0) {
    return pair.pointer();
  } else {
    static_assert(I == 1);
    return pair.tag();
  }
}

Things it's not doing and why

• modeling pointer — this is not a pointer type, access to the pointer should be explicitly visible,
• convertible to bool — it's not sure if it means .pointer() == nullptr or also .tag() == 0,
• manage lifetime — this is not a owning pointer, it's a tool to build one,
• using other than non-alignment bits — these are not portable and are subject of being enabled/disabled as an OS setting, this would create at best ABI problems,
• changing size based on bits requested — intention of this type to be same size of pointer, not be generic pair of pointer and any value,
• supporting function pointers — these doesn't need to be real pointer, but handlers, and can even have bigger size than normal pointer.
• supporting signed tag types — it's tricky and using bitfield is implementation specific.

Impact on existing code

None, this is purely an API extension. It allows to express semantic clearly for a compiler instead of using an unsafe reinterpret_cast based techniques. Integral part of the proposed design is ability to interact with such existing code and migrate away from it.

Proposed changes to wording

This is probably really incorrect, follow the design, sorry.

namespace std {
  template <typename T> struct underlying-or-identity; // exposition only
  
  template <typename T> requires (is_enum_v<T>) struct underlying-or-identity<T> {
    using type = underlying_t<T>;
  }
  
  template <typename T> requires (is_integral_v<T>) struct underlying-or-identity<T> {
    using type = T;
  }
  
  template <unsigned Bits, typename T> constexpr auto pass-thru-mask(T value) noexcept { // exposition only
    return static_cast<underlying-or-identity<T>>(value) & ((1u << Bits) - 1u);
  }
  
  template <typename PointeeT, typename TagT, unsigned BitsRequested = countr_zero(alignof(PointeeT))>
    requires(is_object_v<PointeeT> && is_unsigned_v<underlying-or-identity<TagT>::type &&
             is_same_v<TagT, remove_cvref_t<TagT>> && (BitsRequested < sizeof(PointeeT*) * CHAR_BIT))
  struct pointer_tag_pair {   // freestanding
  public:
    using element_type        = PointeeT;
    using pointer_type        = element_type*;
    using tagged_pointer_type = void*;
    using tag_type            = TagT;

  private:
    // exposition only
    static constexpr unsigned alignment-needed = (1u << BitsRequested);
    
    static constexpr see below tag-mask = (alignment-needed - 1u);
    static constexpr see below pointer-mask = ~tag-mask;
    
    using numeric-tag = underlying-or-identity<tag_type>;
    
    static constexpr numeric-tag to-numeric-tag(tag_type) noexcept;
    static constexpr tag_type from-numeric-tag(numeric-tag) noexcept;

    see below pointer_ = nullptr; 
    
  public:
    // Constructors and assignment
    pointer_tag_pair() = default;
    pointer_tag_pair(nullptr_t) = default;
    pointer_tag_pair(const pointer_tag_pair&) = default;
    pointer_tag_pair(pointer_tag_pair&&) = default;
    pointer_tag_pair& operator=(const pointer_tag_pair&) = default;
    pointer_tag_pair& operator=(pointer_tag_pair&&) = default;
    
    constexpr pointer_tag_pair(pointer_type ptr, tag_type tag)
      requires(alignof(element_type) >= alignment-needed);

    // Special construction helpers
    template <unsigned PromisedAlignment>
    static constexpr pointer_tag_pair from_overaligned(pointer_type ptr, tag_type tag)
      requires(PromisedAlignment >= alignment-needed);

    static pointer_tag_pair from_tagged(tagged_pointer_type ptr);
    
    // Destructor
    ~pointer_tag_pair() = default;

    // Accessors
    tagged_pointer_type tagged_pointer() const noexcept;
    constexpr pointer_type pointer() const noexcept;
    constexpr tag_type tag() const noexcept;

    // Swap
    friend constexpr void swap(pointer_tag_pair& lhs, pointer_tag_pair& rhs) noexcept;

    // Comparisons
    friend constexpr see below operator<=>(pointer_tag_pair lhs, pointer_tag_pair rhs) noexcept;
    friend bool operator==(pointer_tag_pair, pointer_tag_pair) = default;
  };
}

constexpr pointer_tag_pair() noexcept = default;

constexpr pointer_tag_pair(nullptr_t) noexcept;

constexpr pointer_tag_pair(const pointer_tag_pair& other) noexcept = default;

constexpr pointer_tag_pair(pointer_tag_pair&& other) noexcept = default;

constexpr pointer_tag_pair(pointer_type p, tag_type t)

constexpr pointer_tag_pair& operator=(const pointer_tag_pair& other) noexcept = default

constexpr pointer_tag_pair& operator=(pointer_tag_pair&& other) noexcept = default

template <unsigned PromisedAlignment> constexpr pointer_tag_pair from_overaligned(pointer_type p, tag_type t);

pointer_tag_pair from_tagged(tagged_pointer_type p);

~pointer_tag_pair() = default;

constexpr tag_type tag() const noexcept;

constexpr pointer_type pointer() const noexcept;

tagged_pointer_type tagged_pointer() const noexcept;

friend constexpr void swap(pointer_tag_pair lhs, pointer_tag_pair rhs) noexcept;

friend constexpr auto operator<=>(pointer_tag_pair lhs, pointer_tag_pair rhs) noexcept;

friend constexpr bool operator==(pointer_tag_pair lhs, pointer_tag_pair rhs) noexcept;

Feature test macro