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

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

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.

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.