Linking SMIR JSON data from different crates

[jberthold]

Linking several SMIR JSON files together

SMIR JSON is emitted per crate.
For a multi-crate program, this means we get several *.smir.json files.
Each of these files has its own independent set of internalised Ty IDs
to refer to functions and types (same for adt_def IDs).

In order to call a function in another crate, the functions table contains
entries which do not have a corresponding item in the items. Instead, the
called code resides in the other crate and its item is another SMIR JSON file.

Within a single crate, all functions and types are referred to by their
crate-local interned ID Ty. These references occur in various SMIR statements
and terminators. Also, the type metadata contains Tys for structured types such
as tuples, arrays, and structs.

We can link together a number of SMIR JSON files (each one for a named crate) by
applying a positive per-crate offset to all Ty IDs in the SMIR JSON.

The chosen offset value must be large enough to avoid any collisions between Tys from different crates.
A suitable value may be obtained by computing the max of all Ty IDs for each crate.
Traversing items is not necessary for this because all Tys are present in the functions or types tables.

TODO is this true for the types, or are we skipping some?
All Tys should be present in types (except the function ones, of course), and if an item contains a Ty not present in types or functions, we aren't using it!

This approach will lead to duplicates in the types, several (offset-equipped)
Tys will point to the same actual type (primitive or structured). This is harmless
in most cases, but the Tys cannot be used for type checking at runtime.

Algorithm to link several SMIR JSON crate files together:

• Determine the maximum Ty used in each SMIR JSON (functions, types);
• Assign a suitable offset to each crate (in alphabetical order of crate names?);
• traverse all items of each crate, adding the offset of the current crate to each Ty contained within;
• traverse all types in each crate, adding the offset of the current crate to all Ty keys and each Ty contained within;
• add the offset of the crate to each Ty key of the functions in each crate
• concatenate types, functions, items

In the concatenated SMIR JSON, there should be no TerminatorKindCall with a
Ty that is absent from the functions table. Again, we may have duplicate references to
(multiple offset-equipped Tys referring to) the same function (when the calls come from
different crates) but all call targets are known in the functions table.
The fully-qualified name is then looked up in the items and should be present because
all items have been concatenated.

TODO Can there be multiple items which are in fact the same?
(Same qualified name, items coming from different crates)
AFAICT this is possible for monomorphic instances of polymorphic functions (stdlib, specifically).
However, the items would in fact be identical , it would not matter which one to use.

MIR's visitors cannot be used for this, since they are not able to mutate the data they traverse.

TODO we have to read / deserialise SMIR JSON, which is a problem for types that come directly from rustc.

• Workaround: write the impls by hand (the code that would be derived)
• Future work: submit a PR to rustc to add #[derive(Deserialize)] where required
  This will hopefully only be necessary for stable_mir types (not rustc_middle ones).

Eliminating dead code from SMIR JSON

Given a particular start symbol, we want to eliminate all items from items that
aren't executed (transitively) by running the item referred to by the start_symbol.
The functions and types tables can remain unmodified, they only cause minor
overhead in lookups in K during execution.

To compute the required items:

• Traverse each item's terminators to determine which functions are called.
  • Resolve the Ty IDs of called functions using the functions table.
  • These are the edges of a graph of items, keyed by symbol_name.
• Compute the transitive closure of the start_symbol's item in this graph.
  • A simple graph walk starting at start_symbol can be used.
  • This is the set of required items for execution of start_symbol.

[ehildenb]

• Assign a suitable offset to each crate (in alphabetical order of crate names?);

Could we try to use the same crate resolution order that cargo would use? Are we able to ask cargo to do the crate resolution order for us?

[ehildenb]

TODO we have to read / deserialise SMIR JSON, which is a problem for types that come directly from rustc.

• Workaround: write the impls by hand (the code that would be derived)
• Future work: submit a PR to rustc to add #[derive(Deserialize)] where required
  This will hopefully only be necessary for stable_mir types (not rustc_middle ones).

Didn't we open a PR adding serde derivations to many different types of MIR before? @sskeirik worked on this I believe. Perhaps we should follow the same pattern, is there any benefit to adding Deserialize without Serialize?

[jberthold]

TODO we have to read / deserialise SMIR JSON, which is a problem for types that come directly from rustc.

• Workaround: write the impls by hand (the code that would be derived)
• Future work: submit a PR to rustc to add #[derive(Deserialize)] where required
  This will hopefully only be necessary for stable_mir types (not rustc_middle ones).

Didn't we open a PR adding serde derivations to many different types of MIR before? @sskeirik worked on this I believe. Perhaps we should follow the same pattern, is there any benefit to adding Deserialize without Serialize?

Yes, our PR with #[derive(Serialize)] is in rustc main line We would need a few Deserialize additions.
In our own code there are some struct components skipped when serialising, that obviously has to change . Other than that, I expect the changes to follow the old PR.

[dkcumming]

I think this solution is good, I am sure there are other ways to go about doing the same thing of course, but I don't have a problem with this. I think it might be nice to choose an offset that is greater than the Tys and is rounded up to the next increase in the base10 radix so the numbers for the Tys are the same if we have to debug bad to the source (hopefully we don't). E.g. M=77 is the max Ty, we choose O=100 to be the offset so that M+O=177 and the last two digits are the same.

I can't remember if there was a problem with Deserialize being tricky, or if we didn't think we needed it so we didn't add something we weren't sure we would need into the compiler. I think it was actually a combination of both that stopped Stephen including it. I think Jost mentions the only work around that isn't adding it into the compiler, but the duplication is unfortunate.

TODO Can there be multiple items which are in fact the same?
(Same qualified name, items coming from different crates)
AFAICT this is possible for monomorphic instances of polymorphic functions (stdlib, specifically).

Do we have an example or psuedo-code example? Because I am not sure how you could define a function with the same name in the same crate twice... And MonoFn of resolved generics will then change to the explicit types so each would be a different name no? But, I do feel like we saw some functions 2 bodies at one point. However, I think this was long ago and we haven't seen this since. I can't remember the how it came about right now, but it might just be when we were incorrectly mixing up MIR from different part of the compiler and accessing prior versions of promoteds that were already allocated.

[jberthold]

I can't remember if there was a problem with Deserialize being tricky, or if we didn't think we needed it so we didn't add something we weren't sure we would need into the compiler. I think it was actually a combination of both that stopped Stephen including it. I think Jost mentions the only work around that isn't adding it into the compiler, but the duplication is unfortunate.

The missing Deserialize is not the only issue. I started on the Rust code for traversing the AST to update the Ty with offsets, and found that we cannot easily mutate the AST to update the Ty fields, because

1. the provided MirVisitor or Visitor cannot mutate the structure they traverse
2. a few fields are private (for no particular good reason)
   We will have to construct a complete copy during the traversal.

I have started writing a Python prototype which will be a lot faster to finish.

I think this solution is good, I am sure there are other ways to go about doing the same thing of course, but I don't have a problem with this. I think it might be nice to choose an offset that is greater than the Tys and is rounded up to the next increase in the base10 radix so the numbers for the Tys are the same if we have to debug bad to the source (hopefully we don't). E.g. M=77 is the max Ty, we choose O=100 to be the offset so that M+O=177 and the last two digits are the same.

Excellent thinking! I have implemented that very thing 😄 in the prototype.

TODO Can there be multiple items which are in fact the same?
(Same qualified name, items coming from different crates)
AFAICT this is possible for monomorphic instances of polymorphic functions (stdlib, specifically).

Do we have an example or psuedo-code example? Because I am not sure how you could define a function with the same name in the same crate twice...

What I thought of was use sites for a polymorphic function in two different crates, at the same type instance. IIUC both crates' SMIR JSON files will include an item for the same monomorphic instance, and we join the items. But the code should be identical. I will make a few examples for testing anyway, will try to make one for this.

[jberthold]

TODO Can there be multiple items which are in fact the same?
(Same qualified name, items coming from different crates)
AFAICT this is possible for monomorphic instances of polymorphic functions (stdlib, specifically).

Do we have an example or psuedo-code example? Because I am not sure how you could define a function with the same name in the same crate twice...

What I thought of was use sites for a polymorphic function in two different crates, at the same type instance. IIUC both crates' SMIR JSON files will include an item for the same monomorphic instance, and we join the items. But the code should be identical. I will make a few examples for testing anyway, will try to make one for this.

I set up a 2-crate example where both crates used unwrap_or at the same (user-defined) type. Interestingly, in crate2 (which imports the other) the function is not present as an item, the copy from crate1 is used. So there is no problem at all with duplicated function instances.