Further possibilities for mir::Constant cleanup

[RalfJung]

Our mir::Constant/ty::Const story has come a long way. I like that we have two distinct types that each have an eval function that returns an appropriate "evaluated" form (mir::interpret::ConstValue/ty::Valtree). Generally I think this is fairly clean now. :)

However, there are still some subtle invariants and sharp corners:

• Round-trips from an interpreter result (something that originally came out of eval_to_allocation_raw) to a ConstValue and back to an interpreter OpTy should ideally not alter the value (failing to do that leads to surprises like slice::from_raw_parts returns a different address in const context for u8 #105536).
• We have to carefully think about two kinds of efficient representations (in ConstValue and in Valtree) and how to convert between them.
• I started looking at pattern matching and it seems like const_to_pat is only ever called with a Valtree or ConstValue, and furthermore it relies on the caller "normalizing" to a valtree if possible. The logic of "try valtree first, fall back to general ConstValue" exists multiple times (here and here). str patterns must be turned into valtrees which is a very inefficient representation, despite them having a nice efficient representation as ConstValue.

So... I am wondering if we can have a world where there is only one efficient representation, and it's Valtree. I want to kill ConstValue entirely. The things that need to be represented efficiently are:

• Scalars: for primitive types, valtrees are already efficient. ConstValue is additionally efficient for newtype wrappers around primitive types. I don't know if these matter, but if they do we can always declare that for any type with Scalar ABI, the valtree is a leaf -- we can optimize away all the branches. Or we declare that for any repr(transparent) type, valtrees skip the branch and just represent the one non-1-ZST field (and use an empty branch for 1-ZST types). We have options, and we can hide this behind general functions that are given a type and know how to construct/destruct a valtree of that type.
• ZST: I don't know how relevant that is. But it's easy to say that the valtree for a ZST is always a branch with no children (i.e., optimize away all the nested eventually-empty branches in types like [(), 1024]).
• &str and &[u8]/&[u8; N]: currently not very efficient as valtrees. For patterns I think we already turn all strings into valtrees, but we don't currently do that for all literals, and that would be silly to do. So we'd definitely want a more efficient representation. And we have a lot of constraints here -- I think we want this to be both "not any more expensive to construct than the current ConstValue" (since otherwise we will regress MIR building), and we want it to be reasonably efficient to turn into an interpreter OpTy (so that uses of the constants in const-eval are efficient). Codegen also needs to be able to efficiently consume them.

Efficient representation of str and byte literals

So for that last point about slices, currently "efficient consumption in const-eval and codegen" is achieved by sharing the codepath with handling arbitrary results of const-evaluation (both are represented as a ConstAllocation). const-eval needs to generate a fresh AllocId but at least it doesn't have to copy the data. MIR building right now isn't actually that efficient since a new ConstAllocation needs to be created.

It's hard to be efficient on all sides. I see two options here:

• Prioritize MIR building: have a valtree variant that can hold a [u8], suitably interned. (Maybe even push this all the way to LitKind::ByteStr/CStr? And maybe even LitKind::Str, which currently stores a Symbol but that's actually not that great for us since we can't get an &'tcx [u8] out of that.) Codegen backends should learn how to directly turn that into a suitable constant in their target representation. The const-eval interpreter needs to either make a full copy (boooh) or we alter interpret::Allocation to store the bytes in something like a Cow<'tcx, [u8]> -- that is still a bit less efficient than today's literal-to-OpTy path but at least it doesn't copy the string contents. (It needs to create a new Allocation though which we can currently avoid.)
• Prioritize consumption: ConstAllocation is a type that the interpreter can handle very efficiently, and also codegen backends know very well how to turn this into their appropriate backend types. So we could use ConstAllocation as "an efficiently stored str/[u8]/[u8; N]". It's kind of dicey to put a ConstAllocation into a valtree though, since the entire point of valtrees is to not be able to represent arbitrary interpreter data. We'd have tight constraints: only for valtrees of type str/[u8]/[u8; N]; no provenance; everything initialized (in InitMaskBlocks::Lazy mode); alignment 1; not mutable. I think this is coherent (equal data implies equal representation), and it's a lot less churn for the rest of the compiler than the previous alternative, but I can see how it could make someone feel uneasy.

Valtrees as the only efficient representation

On the other hand, I think we could get a nice payoff from making valtrees the only efficient representation: ConstValue disappears! mir::ConstantKind::Value becomes just a ConstAlloc (we might have to add an offset if we still want to support projection for try_destructure_mir_constant_for_diagnostics). EvalToConstValueResult would have an Either<ValTree, AllocId> value, and it would pick Left exactly and only for scalar types, to make these easily accessible in the rest of the compiler without accessing Allocations. (It might as well be Either<Scalar, AllocId>.) Turning that into a mir::ConstantKind will use mir::ConstantKind::Ty when encountering a Left -- basically, everything that today is mir::ConstantKind::Value(_) except ConstValue::Indirect becomes mir::ConstantKind::Ty(ty::ConstKind::Value(_)). We remap the "efficiently represented" mir::ConstantKind::Value to be valtrees instead.

We'd avoid the ambiguity of representing something as a mir::ConstantKind::Value(ConstValue::Scalar(s)) vs mir::ConstantKind::Ty(ty::ConstKind::Value(ValTree::Leaf(s))). We'd reduce the number of possible representations of a compile-time known value down to two: "efficient and abstract" vs "low-level". Generally values of any type can appear in either representation (if they can be valtree'd), except pretty much everyone will assume that scalars are represented efficiently. Pattern matching could much more directly use Either<ValTree, AllocId>, and its use of valtrees for str wouldn't be a performance hazard any more.

Maybe we'll want to give Either<ValTree, AllocId> a name, and maybe that name is mir::ConstantValue -- but that would still be quite different from the current ConstValue type. If the type exists it can have methods like "normalize to valtree if possible" (that's what pattern matching would want), "normalize to valtree if cheap" (i.e., only for scalars; that's what most consumers would want), "normalize to AllocId unless valtree is trivial" (that's what the interpreter / codegen would want -- a "trivial" valtree is a leaf, empty branch, or the efficient str/byte representation; crucially for "valtree if cheap"-normalized constants this is a NOP).

@rust-lang/wg-const-eval please let me know if this makes any sense. :)

[RalfJung]

I tried some refactoring in PatKind to make it more clear which constants are opaque and which are transparent for exhaustiveness checking, but currently that is rather awkward -- while some code really benefits from separate PatKind variants that carry a ValTree/ConstValue, respectively, a lot of other code likes to treat them the same, and converting from ValTree/ConstValue back to ConstantKind quickly becomes cumbersome.

I think if we do the refactor proposed above, and we have a new ConstValue type that's either ValTree or AllocId, this might be easier.

---

There is an interesting interaction of two aspects I hadn't considered yet: we might want to guarantee that valtrees can only be constructed for StructuralEq types. This means under this proposal, non-structural-eq types cannot get the optimized representation. This loses the optimized representation for (some) scalar newtypes. But I think we long as we keep the optimized representations for literals (which have primitive types and hence are structural eq), this should be fine.

[cjgillot]

There is one footgun I'd like to treat around constants too: cloning a ConstOperand may create a distinct AllocId.
For instance, if you have a ConstValue::Slice, the first occurrence will create some AllocId from the data.
The second times the same ConstValue::Slice appears, does it yield the same AllocId or a different one?
What about codegen?

The same question can be asked for a valtree that represents a reference.

[RalfJung]

Under my proposal Valtree-representing-reference would be the only non-AllocId representation of a reference.

And for a valtree I would say this is entirely intentional: if such a valtree is used multiple times, we don't guarantee that you get the same address on each use at runtime. It will be a new AllocId each time. Codegen might be able to deduplicate identical ConstAllocations (though it shouldn't do that for statics), but this is an optimization, not a guarantee.

[RalfJung]

So, regarding the MIR opt concern discussed here -- to me that sounds like you'd want constants that are valtrees only for non-pointer scalar types (to keep an efficient representation for integers). So inside the optimization you'd want a normalization pass that turns all constants that contain pointers into ConstAlloc and thus ensures they are perfectly identical. OTOH, we effectively tried doing that when I tried to use AllocId in ConstValue::Scalar, and it caused a perf regression, so I don't think we can force a ConstAlloc for all str/byte literals.

I don't think we want general clonability of all ConstOperand; we have so far quite deliberately avoided making any guarantees about pointer identity when the same constant is used multiple times. When there are multiple codegen units, guaranteeing deduplication becomes tricky.

We also need a better name for ConstAlloc... RawConstValue?