SemIR representation for dynamic class information (vtable, etc)

[dwblaikie]

After doing some relatively simple work on the vtable pointer in class layout (vptr member, vtable_ptr instruction).

But I'm reaching the point where a larger discussion about the internal representation might be suitable.

The initial question is: How/where is the vtable layout computed and that computation reused (it /could/ be done in lowering, walking the class's block to find virtual functions, etc - but that might be inefficient (walking the whole class potentially multiple times - to emit the vtable, and then looking that up/matching things up when making virtual calls))

Also, possibly computing some of this earlier (during checking, perhaps at the end of the class) might allow for better diagnostics/a good place to group a bunch of checking (eg: #4648 feels a bit awkward - perhaps we could implement the constraint that /all/ dynamic functions (virtual, impl, abstract) appear after the base decl, in which case we'd need to test that at the end of the class, or at least only once we discover the base decl - and having a list of the dynamic functions isolated from the rest of the class contents may be faster than walking the whole pending class block)

@chandlerc suggested this might be a question for @jonmeow and @zygoloid - but his thoughts were that maybe we have another side table (SemIR::Context::dynamic_class_info()?) that is associated with classes (a map keyed by ClassId? an extra field in ClassId that's populated for dynamic classes?). Would that be reasonable? What would we want in there, how should this be rendered to textual SemIR? Oh, right, @chandlerc was suggesting this might possibly be some constant instruction block that computes things like the vtable layout? (I wasn't sure how much the vtable would be explicitly rendered in SemIR, or only a lowering artifact - the impression I got from previous discussions with @zygoloid was that it might be more opaque/an artifact of lowering to some degree, though having a list of virtual functions, and maybe some association between impl and base virtual functions would be helpful)

Open to suggestions, widening or narrowing of the scope we should be considering at this point, etc.

[zygoloid]

Where is the vtable represented?

I have two contrasting thoughts here:

1. Constant evaluation of (eventual) compile-time virtual functions will be simpler if we have the vtable data formed by check, and present and explicitly represented in SemIR. This also seems to align well with the idea that SemIR describes the operational semantics of the program.
2. The exact layout used by the vtable is part of the ABI, and while we don't guarantee ABI stability within Carbon code, we do need to have consistent rules. Moreover, for C++ interop scenarios we need to make a layout decision that's compatible with C++, including the need to include things like a type_info field and an offset-to-most-derived field. This somewhat suggests that the final decision should be made by lowering.

I think I'm leaning towards a slightly hybrid approach: that SemIR contains something like a vtable instruction that takes a list of functions that go in the vtable, the check layer builds that list and builds vtable access instructions that index into it, and the lower layer is ultimately responsible for building a corresponding LLVM IR constant that contains extra fields as necessary, and for transforming the vtable access indexes into GEP indexes.

How is the vtable represented?

Perhaps something like: a VTable instruction that has a TypeId field naming the class type and an InstBlockId field containing a list IDs of FunctionDecls or (for the case of a generic class) SpecificFunctions. And we add an InstId field to the Class object to denote that VTable instruction.

When is the vtable representation built?

I think building the vtable as part of completing the class definition is probably reasonable. Prior to that point, we could track information in a side-table incrementally as we process the class, or we could do an additional pass through the class to find virtual functions and assign them to vtable slots; either approach seems feasible to me, though I think I'm inclined to prefer temporarily storing extra data to avoid rescanning the class.

[dwblaikie]

Thanks for the thoughts - I think I'm up for most/all of that. So (some of this is verbatim, excuse the copy/paste, trying to process/make sure I've absorbed the bits written, to frame any further questions)

• SemIR textual format would have a vtable instruction would appear inside the body of the class (towards/at the end)
• the vtable instruction would appear in the list of instructions in the SemIR in-memory data structure
• the Carbon::SemIR::Class would also have an explicit/named member that referenced the instruction
• the instruction would have:
  • a TypeId field naming the class type
  • an InstBlockId field to a block containing a list of IDs for FunctionDecls (I might set aside the generic case for now, but I'll keep in mind the direction you mentioned)
• the current vtable_ptr instruction, I had been planning to add either an TypeId, InstId, or ClassId (currently got a simple prototype for the latter) to chain back to something useful for building the vtable
• add a new dynamic_class_info stack to the SemIR Context to keep track of virtual functions as we go (no need to track the base class? because that's tracked on the class itself anyway) - use that to add errors for base-after-virtual (check if the top of the dynamic_class_info stack applies to the current class when we see a base decl, if it does, that means we already saw virtual things before the base decl)

OK, think that mostly covers it in my mind. Some questions intermingled ^, and one here:

• Why add the TypeId to the vtable instruction, if it's always within the class it applies to/could be determined from context?
• Why TypeId rather than InstId or ClassId, for instance?
• Should the vtable_ptr instruction use TypeId too, rather than ClassId?

This is enough to work with for now - but broader/thinking about, how would this then be used for virtual function calls/how should those be repersented in the SemIR? Do you expect/want explicit instructions to represent this sort of thing - or lower existing call SemIR into virtual dispatch? (I think there's enough info to do the latter, maybe in simple direct-call cases at least, is there any cases of more indirect calls, where the name_ref instruction might be separated from the call instruction?)

[dwblaikie]

Managed to get some of this going: #4732

But I'm struggling with importing - the list of virtual functions gets imported incorrectly (looks like the list of virtual functions ends up referring to the same elements as the list of the types of the virtual functions maybe?). I've got a hack-around at the moment that makes derived vtables the concatenation of the base vtable followed by any virtual functions in the derived class - which shows this broken vtable in an example like this:

package Modifiers;
base class B1 { virtual fn H(); }

import Modifiers;
class D1 { extend base: Modifiers.B1; }
base class B2 { virtual fn H(); }
class D2 { extend base: B2; }

where D2 has the correct vtable:

 %H.decl: %H.type.2 = fn_decl @H.2
 ...
 %.loc4_29: <vtable> = vtable (@B2.%H.decl) 

but D1 has this weird vtable:

 %H.1: %H.type.1 = struct_value ()
 ...
 %.loc2_39: <vtable> = vtable (constants.%H.1)

I've poked around in the import code, done my best to try things similar to what I've seen - but can't seem to figure out the issue as yet...

[danakj]

I've poked around in the import code, done my best to try things similar to what I've seen - but can't seem to figure out the issue as yet...

I tried to figure it out as well, left a guess at what went wrong on the PR