[Pre-RFC] Flow-Directed Monomorphization Collection in MIR

Summary

This RFC proposes an experimental MIR-level analysis for flow-directed monomorphization , based on the technique described in The Simple Essence of Monomorphization. The paper shows that monomorphization can be formulated as a type-flow analysis: collect constraints, solve them, and specialize the finite set of required instantiations. It further shows that higher-rank type polymorphism and existential types are not inherent obstacles to monomorphization; the real obstruction is cyclic type flow that requires infinitely many specializations.

The proposal has three goals:

1. make monomorphization collection explicit as a type-flow problem;
2. provide compiler infrastructure for future closed-world monomorphization of higher-rank, existential, and opaque-type flows;
3. detect infinite monomorphization structurally, before recursive expansion can cause excessive compile time, memory exhaustion, or compiler hangs.

This RFC does not propose any immediate surface-language change.

Motivation

Rust already monomorphizes generic functions and types. However, the current mechanism is primarily operational: rustc discovers reachable mono items and recursively expands the required instances.

This is sufficient for ordinary generics, but it leaves two issues.

First, the compiler lacks a uniform representation for type instantiation flow through more advanced forms of abstraction, including:

generic functions
generic methods
opaque return types
async fn futures
return-position impl Trait
trait-associated opaque types
future existential-like encodings
future closed-world generic dyn methods

Second, recursive monomorphization is currently treated as an expansion problem. For example:

fn f<T>(x: T) {
    f(Some(x));
}

fn main() {
    f(0_i32);
}

requires:

f::<i32>
f::<Option<i32>>
f::<Option<Option<i32>>>
...

The underlying cause is not recursion alone, but growing type flow :

i32       ⊑ T
Option<T> ⊑ T

This proposal makes that structure explicit. The compiler can reject the growing cycle before generating the infinite sequence.

Guide-level explanation

The compiler builds a type-flow graph during MIR monomorphization collection.

A constraint has the form:

τ ⊑ α

where τ is a lifetime-erased, codegen-relevant type expression and α is a generic parameter. The constraint means:

type τ flows into parameter α

For example:

fn id<T>(x: T) -> T {
    x
}

fn main() {
    id(1_i32);
    id(String::from("x"));
}

produces:

i32    ⊑ T
String ⊑ T

The solution is:

T ↦ { i32, String }

so the required instances are:

id::<i32>
id::<String>

Forwarding is represented by parameter-to-parameter flow:

fn g<U>(x: U) {
    h::<U>(x);
}

fn h<T>(x: T) {}

produces:

U ⊑ T

Recursive growth is represented by constructor-labeled flow:

fn f<T>(x: T) {
    f::<Option<T>>(Some(x));
}

produces:

Option<T> ⊑ T

which forms the growing cycle:

T --Option--> T

The cycle is rejected because it denotes infinitely many required instances.

Reference-level explanation

Position in the compiler

The analysis runs during MIR monomorphization collection.

It operates after type checking and borrow checking, on normalized codegen-relevant types.

Regions are erased before constructing monomorphization keys. Type parameters and const parameters remain specialization dimensions.

For example:

fn id_ref<'a>(x: &'a i32) -> &'a i32 {
    x
}

does not produce lifetime-indexed instances. The analysis sees:

&i32

not:

&'a i32
&'static i32

Constraint collection

At each generic instantiation site, rustc emits a constraint from the actual argument to the callee parameter.

fn f<T>(x: T) {}

fn main() {
    f::<i32>(0);
}

emits:

i32 ⊑ T

Generic forwarding emits parameter flow:

fn g<U>(x: U) {
    f::<U>(x);
}

emits:

U ⊑ T

Constructed instantiation emits structured flow:

fn g<U>(x: U) {
    f::<Option<U>>(Some(x));
}

emits:

Option<U> ⊑ T

Solving

The solver computes a finite mapping:

S(α) = { ρ1, ρ2, ... }

where each ρ is a lifetime-erased concrete type.

A cycle is rejected when returning to the same parameter adds a non-empty type constructor stack.

Rejected:

T --Option--> T

because it denotes:

T = i32
T = Option<i32>
T = Option<Option<i32>>
...

Allowed:

T ⊑ U
U ⊑ T

because it does not itself grow the type.

Opaque types and impl Trait

The analysis must explicitly represent Rust opaque types.

Argument-position impl Trait is treated as an anonymous generic parameter:

fn f(x: impl Clone) {}

is modeled like:

fn f<T: Clone>(x: T) {}

Return-position impl Trait is treated as an opaque but concrete type:

fn once<T>(x: T) -> impl Iterator<Item = T> {
    std::iter::once(x)
}

Conceptually, the flow graph records:

T       ⊑ once::T
Once<T> ⊑ once::ReturnOpaque<T>

After calls at i32 and String, the opaque instances are:

once::ReturnOpaque<i32>
once::ReturnOpaque<String>

async fn is handled similarly, since it returns an opaque future type.

This RFC does not change the semantics of impl Trait. It only requires the flow graph to account for opaque types already present in Rust’s type system.

Higher-rank and existential flow

The analysis is intended to support future closed-world monomorphization of type flow through higher-rank and existential structures.

For higher-rank type-polymorphic methods, method-level type parameters are flow targets:

i32  ⊑ A
bool ⊑ A

A closed-world lowering may then generate:

method_i32
method_bool

For existential packaging, construction flows into the hidden type parameter, and unpacking propagates it onward:

i32    ⊑ A
String ⊑ A
A      ⊑ B

Rust does not currently expose general existential packages in this form. Existing impl Trait is opaque rather than runtime-unpacked existential packaging. Nevertheless, both require tracking hidden concrete types through generic instantiation.

Proposed implementation

Stage 1: graph construction

Add an internal flow graph builder behind:

-Z flow-directed-mono

This stage mirrors existing monomorphization collection and does not affect code generation.

Stage 2: growing-cycle detection

Detect growing cycles before recursive mono-item expansion.

This is the primary robustness benefit: infinite monomorphization becomes a structural compiler error, not an operational failure mode.

Stage 3: diagnostics

Use the graph to report the type-growth path.

Example diagnostic:

error: generic instantiation grows without bound
 --> src/main.rs:2:5
  |
2 |     f(Some(x));
  |     ^^^^^^^^^^ recursively instantiates `f` with `Option<T>`

note: type-flow cycle detected:
      T --Option--> T

note: starting from `i32`, this requires:
      f::<i32>
      f::<Option<i32>>
      f::<Option<Option<i32>>>
      ...

Stage 4: validation

Compare the flow-derived mono item set against rustc’s existing collector under a debug flag.

The new analysis should initially be used for validation and diagnostics, not as the codegen driver.

Stage 5: optional integration

After validation, rustc may use the solver for selected parts of monomorphization collection.

Drawbacks

This adds compiler complexity.

The analysis must interact with MIR, trait selection, opaque types, associated types, codegen units, incremental compilation, drop glue, closures, generators, async lowering, vtables, and shims.

The analysis may over-approximate. Over-approximation is acceptable for diagnostics, but not for direct code generation unless validated.

Rationale and alternatives

Keep the existing collector unchanged

This avoids implementation cost but leaves infinite monomorphization as a recursive expansion failure.

Add ad hoc recursion diagnostics

This may improve individual errors, but it does not provide a general model for generic, higher-rank, existential, and opaque type flow.

Use backend-level analysis

LLVM-level analysis is too late. Rust generics have already been monomorphized before LLVM IR generation.

Prior art

The primary prior art is The Simple Essence of Monomorphization , which presents monomorphization as flow-directed constraint solving, supports higher-rank and existential polymorphism, and characterizes non-monomorphizable programs as growing cycles in type flow.

Rust’s existing MIR monomorphization machinery remains the implementation baseline.

Unresolved questions

• What is the graph node identity?

  • DefId + GenericParamIndex
  • InstanceDef + GenericArgIndex
  • MonoItem + GenericArgIndex

• Should the graph be built per item, per crate, per codegen unit, or per compilation session?

• How should opaque types be represented?

  • by opaque DefId;
  • by defining use;
  • by hidden type;
  • by opaque identity plus captured arguments?

• When should hidden types for impl Trait be revealed to the solver?

• How should RPITIT be represented?

  • as associated type projection flow;
  • as opaque type flow;
  • or both before and after normalization?

• How should const generics appear in the graph?

• How should compiler-generated items appear?

  • drop glue;
  • closures;
  • async futures;
  • generators;
  • vtable shims.

• Should growing cycles be rejected before the existing recursion limit is reached?

• Can upstream crates expose compact type-flow metadata?

Future possibilities

This infrastructure may support future closed-world experiments with generic methods behind dynamic dispatch.

For example:

trait Choose {
    fn choose<T>(&self, a: T, b: T) -> T;
}

could, in a closed-world setting, be lowered into:

choose_i32
choose_bool
choose_String

when flow analysis proves that these are the only required instantiations.

This RFC does not propose that language feature. It proposes the MIR-level analysis needed to make such features technically tractable.