Acknowledgement

I want to thank to everyone who helped me by reviewing this paper. I want to thank especially Tomasz Kamińsky who made the wording actually make sense.

Revision history

• R5 → R6: added section discussiong tptr.tagged_pointer() and pointer_tag_pair::from_tagged(...) impact of invalid pointers on portability and existing architectures, and how it is mitigated. Added support for nullptr in wording. Added precondition against pointers pointing past the end of an object. Constructors are now limiting what pointer types can be used (avoiding non-first base class and virtual inheritance). Added remark to max_pointer_bits_available what non-zero value means for the implementation. During review of draft of this R6 the function pointer_bits_available was added and removed quarantee of min 1 bit available for tagging (always). Changed order of template arguments to pointer_tag_pair<class PtrT, unsigned BitsRequested, typename TagT> (previously pointer_tag_pair<PtrT, TagT, BitsRequested>). Added exposition only concepts, functions, and constants to make specification simpler. Added section discussing comparing tags.Added section explaining why BitsRequested and not Bits. Added section explaining the necessity of all static checks and preconditions. Comparison operators are now conditionaly present. Fix mistake about CHERI pointers and casting to/from uintptr_t. Added information what it would take to allow past-the-end-of-an-object pointer values.
• R4 → R5: updated rest of paper to reflect changes of wording in R4 (changing pointee to pointer), reintroduce design section which was basically example implementation, this time updated with current wording, add subsection about having pointee or pointer, which LEWG should decide, wording uses pointer instead of pointee.
• R3 → R4: changes requested by LEWG (removed nullptr_t constructor, added support for void *, first template argument is now pointer and not pointee, added pointer_tag_trait to inspect available bits inside pointers, added tuple_size, tuple_element, and get<N>(pointer_tag_ptr))
• 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<T *, n, tag_t>) == 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.

// requesting only 1 bit of information
using hamt_node_pointer = std::pointer_tag_pair<const void *, 1, bool>;
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
}

template <typename T> class maybe_owning_ptr {
  enum class ownership: unsigned {
    reference,
    owning,
  };
  
  std::pointer_tag_pair<T *, 1, ownership> _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 *));

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);
}

Invalid pointers

Jens had concerns about fact that function .tagged_pointer() returns technically almost always an invalid pointer value [basic.compound]. In order to understand why this can feel concerning, one must understand what it means to have an invalid pointer value according C++. So to reiterate that, an invalid pointer value:

• can't be dereferenced or deallocated, as both these operations results in explicit undefined behaviour [basic.compound],
• all other operations including the l-value to r-value conversion is implementation defined [conv.lval] and on some architectures can result in a page-fault as stated in a note in [basic.types].

Obviously the pointer resulting from .tagged_pointer() is not meant to be dereferenced or deallocated. It's there only to be able to be passed thru C and legacy interfaces (without depending on reinterpret_cast). And only safe usage for it is to be passed into ::from_tagged(...) for us to reconstruct original pointer_tag_pair and then with .pointer() access the original pointer.

	auto tptr = std::pointer_tag_pair<T *, 1, bool>{&object, true};
	void * opaque = tptr.tagged_pointer(); // you got an invalid pointer value, and it's fine
	
	// example of problems:
	*opaque; // you can't dereference `void *` anyway
	*static_cast<T *>(opaque); // UB, dereferencing invalid pointer value, 
	                           // it may not point to a valid object due tagging, obviously
	
	// example why `void *` is needed
	curl_easy_setopt(handle, CURLOPT_PRIVATE, opaque); // implementation-defined lvalue-to-rvalue conversion
	
	// later...
	
	char * ptr;
	curl_easy_getinfo(handle, CURLINFO_PRIVATE, &ptr); // CURL uses char** for internal reasons
	// ptr is now invalid pointer value too, 
	// any manipulation with it is an implementation-defined behavior
	
	// following function takes always `void *` so it is converted implicitly from char *
	auto tptr2 = std::pointer_tag_pair<void *, 1, bool>::from_tagged(ptr); // implementation-defined lvalue-to-rvalue conversion
	
	// if the implementation pass value
	// identical `ptr` then `tptr2.pointer()` will yield valid pointer
	assert(tptr2.pointer() == object);
	assert(tptr2.tag() == true);
	

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.

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.

constexpr unsigned max_pointer_bits_available = std::countr_zero(4096u); // tagging must never overflow page alignment

constexpr unsigned pointer_bits_available(size_t alignment) noexcept {
	assert(std::popcount(alignment) == 1);
	return std::min(std::countr_zero(alignment), max_pointer_bits_available);
}

// helper
template <typename T> struct copy_cv {
	template <typename Y> using result_t = Y;
};

template <typename T> struct copy_cv<const T> {
	template <typename Y> using result_t = const Y;
};

template <typename T> struct copy_cv<volatile T> {
	template <typename Y> using result_t = volatile Y;
};

template <typename T, typename Y> using copy_cv_t = copy_cv<T>::template result_t<Y>; 

template &lt;typename Ptr, typename TagT, unsigned BitsRequested = pointer_bits_available(alignof(std::pointer_traits<Ptr>::element_type))&gt;
class pointer_tag_pair {
	static_assert(std::is_same_v&lt;remove_cvref_t&lt;Ptr&gt;, Ptr&gt;);
	static_assert(std::is_same_v&lt;remove_cvref_t&lt;TagT&gt;, TagT&gt;);
	static_assert(std::is_pointer_v&lt;Ptr&gt;);
	static_assert(!std::is_function_v&lt;remove_pointer_t&lt;Ptr&gt;&gt;);
	using UT = std::conditional_t&lt;std::is_enum_v&lt;TagT&gt;, std::underlying_type_t&lt;TagT&gt;, T&gt;;
	static_assert(std::is_unsigned_t&lt;UT&gt;);
	static_assert(sizeof(TagT) &lt;= sizeof(void*));
	static_assert(BitsRequested <= max_pointer_bits_available);
	
public:
	using pointer_type				= Ptr;
	using tagged_pointer_type = copy_cv_t<Ptr, void *>; // I prefer `void *` to avoid loosing provenance
	using tag_type						= TagT;
	static constexpr unsigned bits_requested = BitsRequested;

private:
	static constexpr uintptr_t tag_mask = (uintptr_t{1} &lt;&lt; bits_requested) - 1u;
	static constexpr uintptr_t pointer_mask = ~tag_mask;

	Pointer internal_pointer;

public:
	constexpr pointer_tag_pair() noexcept {
		internal_pointer = nullptr;
	}
	pointer_tag_pair(const pointer_tag_pair&amp;) = default;
	pointer_tag_pair(pointer_tag_pair&amp;&amp;) = default;
	pointer_tag_pair&amp; operator=(const pointer_tag_pair&amp;) = default;
	pointer_tag_pair&amp; operator=(pointer_tag_pair&amp;&amp;) = default;
	~pointer_tag_pair() = default;

	constexpr pointer_tag_pair(nullptr_t, tag_type tag) 
	{
		assert(bit_width(tag) &lt;= bits_requested);
		__builtin_tag_pointer_mask_or(nullptr, static_cast&lt;uintptr_t&gt;(tag), tag_mask)
	}

	template &lt;typename U&gt;
	constexpr pointer_tag_pair(U * ptr, tag_type tag)
		requires(std::convertible_to&lt;U*, pointer_type&gt; &amp;&amp; pointer_bits_available(alignof(U)) &gt;= bits_requested): internal_pointer{
			__builtin_tag_pointer_mask_or(ptr, static_cast&lt;uintptr_t&gt;(tag), tag_mask)
		} {
			assert(bit_width(tag) &lt;= bits_requested);
		}

	template &lt;unsigned PromisedAlignment, typename U&gt;
		requires(std::convertible_to&lt;U*, pointer_type&gt; &amp;&amp; pointer_bits_available(PromisedAlignment) &gt;= bits_requested)
	    static constexpr pointer_tag_pair from_overaligned(P ptr, tag_type t) {
		assert(ptr == null || std::is_sufficiently_aligned&lt;PromisedAlignment&gt;(ptr));
		assert(bit_width(t) &lt;= bits_requested);
		
		auto out = pointer_tag_pair{};
		out.internal_pointer = __builtin_tag_pointer_mask_or(ptr, static_cast&lt;uintptr_t&gt;(tag), tag_mask);
		return out;
	}

	template &lt;unsigned PromisedAlignment&gt;
	static constexpr pointer_tag_pair from_overaligned(pointer_type ptr, tag_type tag)
		requires(pointer_bits_available(PromisedAlignment) &gt;= bits_requested)
	{
		auto out = pointer_tag_pair{};
		out.internal_pointer = __builtin_tag_pointer_mask_or(ptr, static_cast&lt;uintptr_t&gt;(tag), tag_mask);
	}

	// Precondition: valid pointer if untagged
	static pointer_tag_pair from_tagged(tagged_pointer_type ptr) { // no-constexpr
		auto out = pointer_tag_pair{};
		out.internal_pointer = ptr;
		return out;
	}

	// access tagged pointer (for interaction with existing tagging mechanisms)
	tagged_pointer_type tagged_pointer() const noexcept { 
		return reinterpret_cast&lt;tagged_pointer_type&gt;(internal_pointer);
	}
	
	// access untagged pointer
	constexpr pointer_type pointer() const noexcept {
		return static_cast&lt;pointer_type&gt;(__builtin_tag_pointer_mask(internal_pointer, pointer_mask));
	}
	
	// access tag value
	constexpr tag_type tag() const noexcept {
		return static_cast&lt;tag_type&gt;(__builtin_tag_pointer_mask_as_int(internal_pointer, tag_mask));
	}

	// swap
	constexpr void swap(pointer_tag_pair&amp; lhs) noexcept {
		std::swap(internal_pointer, rhs.internal_pointer);
	}

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

	friend bool operator==(pointer_tag_pair lhs, pointer_tag_pair rhs) noexcept {
		return lhs.pointer() == rhs.pointer() &amp;&amp; lhs.tag() == rhs.tag();
	}
};

// with requirement of bits the following instantiation of type would fail
// instead we communicate "we take pointer to char, which has 2 bits of space"
using overaligned_char_tptr = pointer_tag_pair<char *, 2>; 

	using tptr_t = pointer_tag_pair<char *, 16>; // user naively ask for 16 bits
	alignas(16) char c = ...; // align 16, not 2^16
	
	// no failure on next line (if the static check is removed)
	auto x = tptr_t::from_overaligned<16>(&c, 0b1111'1111'1111'1111u);
	assert(x.pointer() != &c); // wrong pointer value
	assert(x.tag() != 0b1111'1111'1111'1111u); // wrong tag value

	using tptr_t = pointer_tag_pair<char *, 16>; // user naively ask for 16 bits
	char c = ...; 
	
	// no runtime failure on next line (user is lying!)
	auto x = tptr_t::from_overaligned<(2 << 16)>(&c, 0b1111'1111'1111'1111u); // works on my machine #YOLO
	assert(x.pointer() != &c);
	assert(x.tag() != 0b1111'1111'1111'1111u);

	using tptr_t = pointer_tag_pair<char *, 2>; // user wants this to work with any char
	alignas(4) char c = ...; 
	
	// no runtime failure on next line (pointer has enough alignment for what is requested)
	auto x = tptr_t(&c, 0x10u); // accidentally passing 0b1'0000 to space of two bits
	assert(x.pointer() != &c); // wrong pointer value
	assert(x.tag() != 0x10u); // wrong tag value

auto [ptr, tag] = a_pointer_tag_pair;

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-defined.

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

inline constexpr unsigned max_pointer_bits_available = see below;

constexpr unsigned pointer_bits_available(size_t alignment);

namespace std {   

  template <class U, class PtrT, unsigned BitsRequested, size_t Alignment = alignof(U)>
    concept tagging-compatible-pointee // exposition only
      = convertible_to<U*, PtrT> && pointer_bits_available(Alignment) >= BitsRequested 
        && (is_void_v<element-of<PtrT>> 
          || is_scalar_v<element-of<PtrT>> 
          || is_union_v<element-of<PtrT>> 
          || is_pointer_interconvertible_base_of_v<element-of<PtrT>, U>);

  template <class TagT> constexpr unsigned tag-bit-width(TagT value) noexcept; // exposition only


  template <class Ptr,
    unsigned BitsRequested = bits-available<element-of<Ptr>>,
    class TagT = unsigned>
  class pointer_tag_pair {   // freestanding
  public:
    using pointer_type        = Ptr;
    using element_type        = pointer_traits<Ptr>::element_type; 
    using tagged_pointer_type = see below;
    using tag_type            = TagT;
    static constexpr unsigned bits_requested = BitsRequested;

    // Constructors and assignment
    constexpr pointer_tag_pair() noexcept;

    template <tagging-compatible-pointee<pointer_type, bits_requested> U>
      constexpr pointer_tag_pair(U* p, tag_type t);
    constexpr pointer_tag_pair(nullptr_t p, tag_type t);

    // Special construction helpers
    template <size_t PromisedAlignment,
        tagging-compatible-pointee<pointer_type, bits_requested, PromisedAlignment> U>
      static constexpr pointer_tag_pair from_overaligned(U* p, tag_type t);

    static pointer_tag_pair from_tagged(tagged_pointer_type p) noexcept;

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

    // Swap
    constexpr void swap(pointer_tag_pair& o) noexcept;

    // Comparisons
    friend constexpr see-below operator<=>(pointer_tag_pair lhs, pointer_tag_pair rhs) noexcept requires three_way_comparable<tag_type>;
    friend constexpr bool operator==(pointer_tag_pair, pointer_tag_pair) noexcept requires equality_comparable<tag_type>;
  };


  template <class Ptr>
    pointer_tag_pair(Ptr *) -> pointer_tag_pair<Ptr *>;
  template <class Ptr, class TagT> 
    pointer_tag_pair(Ptr *, TagT tag) -> pointer_tag_pair<Ptr *, bits-available<element-of<Ptr>>, TagT>;
}

template <class T> constexpr unsigned tag-bit-width(T v) noexcept;

constexpr pointer_tag_pair() noexcept;

template <tagging-compatible-pointee<pointer_type, bits_requested> U>
  constexpr pointer_tag_pair(U* p, tag_type t);
constexpr pointer_tag_pair(nullptr_t p, tag_type t);

template <size_t PromisedAlignment,
    tagging-compatible-pointee<pointer_type, bits_requested, PromisedAlignment> U>
  static constexpr pointer_tag_pair from_overaligned(U* p, tag_type t);

using tagged_pointer_type = see below;

tagged_pointer_type tagged_pointer() const noexcept;

static pointer_tag_pair from_tagged(tagged_pointer_type p) noexcept;

constexpr pointer_type pointer() const noexcept;

constexpr tag_type tag() const noexcept;

constexpr void swap(pointer_tag_pair& o) noexcept;

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

return pair(lhs.pointer(), lhs.tag()) <=> pair(rhs.pointer(), rhs.tag());

friend constexpr bool operator==(pointer_tag_pair lhs, pointer_tag_pair rhs) noexcept requires equality_comparable<tag_type>;

return pair(lhs.pointer(), lhs.tag()) == pair(rhs.pointer(), rhs.tag());

template<class Ptr, unsigned BitsRequested, class TagT>
  constexpr tuple_element_t<I, pointer_tag_pair<Ptr, BitsRequested, TagT>>
    get(pointer_tag_pair<Ptr, BitsRequested, TagT> p) noexcept;