PointerUnion stores a fixed-width `ceil(log2(N))`-bit tag in the low
bits of the pointer. This works only when every member type provides at
least that many low bits — if the least-aligned type doesn't,
compilation fails, even though the higher-aligned types may have plenty
of spare bits going to waste.
Introduce a variable-length escape-encoded tag that exploits the extra
low bits of higher-aligned types, analogous to UTF-8: types are grouped
into tiers by NumLowBitsAvailable; each non-final tier reserves one code
as an escape prefix, and the next tier extends the tag into the newly
available bits. This allows PointerUnion to hold more type variants than
a fixed-width tag permits.
The fixed-width path is used when the minimum alignment already provides
enough bits (the common case); the variable-width path activates only
when it doesn't, and requires types to be listed in non-decreasing
NumLowBitsAvailable order.
I need this for https://github.com/llvm/llvm-project/pull/186923 which
requires a 6-member PointerUnion in MLIR TypeRange/ValueRange. On 32-bit
systems, some members only provide 2 low bits, insufficient for a 3-bit
fixed-width tag.
6e916d0598