constexpr pointer tagging

This paper proposes a new library non-owning pointer and value pair which has ability to store small amount of information 'tag' in a pointer bits in an unspecified-way. This functionality must be usable in constexpr environment.

Revision history

• 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

TL;DR

This paper proposes simple type for which user request n-bits of storage inside a pointer value in an unspecified way. Construction of the type should fail in case when no such storage is available.

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 is trying to make a design which will allow vendors to provide their own extension to access this functionality while allowing interop with standard code.

These extensions brings a major adventage as they allow to dereferencing a tagged pointer without any actual unmasking. This approach has performance advantage, but the major usage for pointer tagging is memory size / throughput limitations, not CPU performance. Interface of this proposal has a such fast-path provided.

Use-cases

There are three basic use-cases:

• 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 small string, ...)

This paper aims to solve first two use-cases and give tools to build the third use-case safely to users.

Safety

Pointer tagging is currently implementable only with reinterpret_cast bit manipulating pointers and is prone to be unsafe and hard to debug as it's not expressed clearly in code what is the intention. By giving a name to the tool it allows programmer to express intent clearly and compiler to diagnose better.

Any unsafe operation like accessing raw tagged pointer or not unmasked but valid pointer must be clearly visible in the code, this proposal is trying to keep these points visible.

Examples

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
}

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 {
    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 *));

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 and needs compiler support in some form.

Updated version is strictly subset of of the old version.

Implementation in the library

Library is providing a special pair-lie type containing pointer and small tag type, and user requested number of bits.

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

Library has support to access dirty. Dirty pointer 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).

Implementation in the compiler

The implementation is providing C-like builtins to manipulating raw pointers and isn't mean to be used by end-users, only to allow 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 revealing actual pointer representation.

Constexpr support

These builints are trivial to implement semanticaly identical behaviour for the constant evaluation. Pointers in clang are not represented as addresses but as symbols (original AST variable, allocation, static object + path to subobject, its provenance), there is no address to manipulate. Actual tag value in "pointer" is stored in a metadata of the pointer itself and builtins only provide access to it.

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 access original pointer and tag value.

Provenance

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 approach

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.

Design of the proposed functionality

Simple pointer like pair storing information in "free" bits in a pointer, the storage is done in an unspecified way, but implementations are required to keep size of the object same as the underlying pointer type.

template <typename Pointee, typename TagType, unsigned Bits> class pointer_tag_pair {
public:
	using clean_pointer = Pointee *;
	using dirty_pointer = void *;
	using tag_type = TagType;
	
private:
	/* unspecified */ _pointer{nullptr}; // required to have size same as sizeof(Pointee *)

public:
	// constructors
	pointer_tag_pair() = default;
	constexpr pointer_tag_pair(nullptr_t) noexcept;
	pointer_tag_pair(const pointer_tag_pair &) = default;
	pointer_tag_pair(pointer_tag_pair &&) = default;
	
	// to construct from already tagged pointer from external facility
	pointer_tag_pair(std::already_tagged_t, dirty_pointer ptr) noexcept; // no constexpr
	
	// to store and tag pointer (only if eligible)
	constexpr pointer_tag_pair(clean_pointer ptr, tag_type tag) noexcept;
	
	// to store and tag pointer for over-aligned pointers which wouldn't be eligible otherwise
	template <size_t Alignment> constexpr pointer_tag_pair(std::overaligned_pointer_t<Alignment>, clean_pointer ptr, tag_type tag) noexcept;
	
	// destructor
	~pointer_tag_pair() = default;
	
	// accessors
	dirty_pointer unsafe_tagged_pointer() const noexcept; // no constexpr
	constexpr clean_pointer pointer() const noexcept;
	constexpr tag_type tag() const noexcept;
	
	// support for tuple protocol to access [pointer(), tag()]
	template <size_t I> friend constexpr decltype(auto) get(pointer_tag_pair _pair) noexcept; 
	
	// swap
	friend constexpr void swap(pointer_tag_pair & lhs, pointer_tag_pair & rhs) noexcept;
	
	// comparing {pointer(), tag()} <=> {pointer(), tag()} for consistency
	friend constexpr auto operator<=>(pointer_tag_pair lhs, pointer_tag_pair rhs) noexcept {
		// comparison equivalent to (but not actually needing tuple)
		return std::tuple{lhs.pointer(), lhs.tag()} <=> std::tuple{rhs.pointer(), rhs.tag()};
	}
	friend bool operator==(pointer_tag_pair, pointer_tag_pair) = default;
};

struct already_tagged_t { };
constexpr auto already_tagged = already_tagged_t{};

template <unsigned Alignment> struct overaligned_pointer_t { };
template <unsigned Alignment> constexpr auto overaligned_pointer = overaligned_pointer_t<Alignment>{};

Preconditions and eligibility of constructors

In addition to static safety checks, constructors will have preconditions requiring the original pointer to be recoverable with call of .pointer() and tag of identical value to be recoverable with call of .tag()

tuple protocol

// support for tuple protocol so we can split tagged pointer to structured bindings:
// auto [ptr, tag] = pointer_tag_pair;
template <typename _T, typename _Tag, unsigned _Bits>
struct tuple_size<pointer_tag_pair<_T, _Tag, _Bits>>: std::integral_constant<std::size_t, 2> {};

template <std::size_t I, typename _T, typename _Tag, unsigned _Bits>
struct tuple_element<I, pointer_tag_pair<_T, _Tag, _Bits>> {
  using _pair_type = pointer_tag_pair<_T, _Tag, _Bits>;
  using type = std::conditional_t<I == 0, typename _pair_type::clean_pointer, typename _pair_type::tag_type>;
};

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

TBD after design review.

Feature test macro