Change ty::Const to a "value tree" representation

[oli-obk]

Proposal

Currently ty::Const has multiple ways of representing the same value, which by itself isn't bad, but we actually do represent the same value in different ways. This breaks the invariant in the compiler that if interned things are equal, their interned address is the same. This is very visible when you have two constants representing a pointer value. Const generic functions that are generic over pointer values can arbitrarily cause linker errors, because code defining the generic function may compute a different symbol than the code calling the generic function.

ty::Const's val field is of type ConstKind, whose Value variant contains a ConstValue. This ConstValue will be replaced by

enum ConstValue<'tcx> {
    Leaf(u128),
    Node {
        variant: Option<VariantIdx>,
        elements: &'tcx [ConstValue<'tcx>],
    }
}

This change will shrink the size of ConstValue from its current 32 bytes to 24 bytes.
A value of struct, tuple or array type will be represented as a Node, where all the fields or elements are again encoded as ConstValue. Only integers, bools and char are allowed as Leaf values.
A value of enum type will be represented as a Node where the variant field is set to the active enum variant's index and the enum variant's fields are encoded just like struct fields.
A pointer is represented as a Node with a single child, so (42,) and &42 are represented exactly the same, only the type at the ty::Const level will differ. While we could have a separate Pointer(&'tcx ConstValue<'tcx>) variant, there's little use in making this explicit and not having it will reduce code duplication everwhere where the difference is not relevant without affecting the places where the difference is relevant.

A lossy conversion from mir::Const to ty::Const will be introduced. It will be used for pretty printing mir::Const during mir dumps. This way we only have to support pretty printing ty::Const, which is trivial to pretty print.

mir::Const will be changed to just become the old ConstValue::ByRef representation in case of ConstKind::Value. We can likely also remove other variants from the new mir::ConstKind - I belive Infer, Bound and PlaceHolder are only used in typeck and irrelevant for MIR.

Extensions and alternative designs are elaborated in https://hackmd.io/YmDjIsUsRrC6SiQzkl3Gew

Mentors or Reviewers

• @eddyb already talked with me about this

Process

The main points of the Major Change Process is as follows:

• File an issue describing the proposal.
• A compiler team member or contributor who is knowledgeable in the area can second by writing @rustbot second.
  • Finding a "second" suffices for internal changes. If however you are proposing a new public-facing feature, such as a -C flag, then full team check-off is required.
  • Compiler team members can initiate a check-off via @rfcbot fcp merge on either the MCP or the PR.
• Once an MCP is seconded, the Final Comment Period begins. If no objections are raised after 10 days, the MCP is considered approved.

You can read more about Major Change Proposals on forge.

Comments

This issue is not meant to be used for technical discussion. There is a Zulip stream for that. Use this issue to leave procedural comments, such as volunteering to review, indicating that you second the proposal (or third, etc), or raising a concern that you would like to be addressed.

[rustbot]

This issue is not meant to be used for technical discussion. There is a Zulip stream for that. Use this issue to leave procedural comments, such as volunteering to review, indicating that you second the proposal (or third, etc), or raising a concern that you would like to be addressed.

[eddyb]

I've previously talked about how this is the interpretation const generics want, and I'm now conceding that making it explicit in the representation (as opposed to lazily decoding it from the miri representation) is a good way to sidestep accidentally ending up with not-typesystem-friendly constants in types, even if other uses of ty::Const (i.e. MIR) may incur additional complexity.

We also probably want to also have some compact encoding for [u8] and str (as they have literals), but that's orthogonal.

@rustbot second