When we set out to design the Firefly compiler for the Fidelity Framework, one of our core goals was to produce truly minimal native executables. In the world of traditional .NET development, your “Hello World” application carries the weight of the entire runtime and referenced assemblies, resulting in deployments measured in megabytes. For embedded systems, high-frequency trading platforms, or any scenario where every byte matters, this overhead is unacceptable. Our solution involves a revolutionary approach: type-aware tree shaking that operates directly on the F# Compiler Services AST, preserving rich type information to guide precise dead code elimination.

Tree Shaking Through Type-Preserving Analysis

Tree shaking is a form of dead code elimination that removes unused code from your final executable. The name comes from the mental model of shaking a tree to make dead branches fall off, leaving only the living, connected parts. What makes Firefly’s approach unique is how we leverage F#’s rich type system throughout the reachability analysis, enabling optimizations impossible with traditional approaches.

Consider how our type-aware analysis surpasses traditional dead code elimination:

// Type with complex generic constraints
type IProcessor<'T when 'T :> IComparable<'T> and 'T : struct> =
    abstract Process : 'T -> 'T

// Multiple implementations
type IntProcessor() =
    interface IProcessor<int> with
        member _.Process x = x * 2

type FloatProcessor() =
    interface IProcessor<float> with
        member _.Process x = x * 1.5

type DateProcessor() =
    interface IProcessor<DateTime> with
        member _.Process x = x.AddDays(1.0)

// Your application only uses int processing
let result = IntProcessor().Process(42)

Traditional tree shaking might struggle to determine which processor implementations are actually used. Firefly’s type-preserving analysis traces the exact type instantiations through your program, determining that only IProcessor<int> and IntProcessor are needed. The FloatProcessor and DateProcessor, along with their associated type specializations, are eliminated entirely.

Consider a typical F# utility library with generic functions and type specializations:

module Collections =
    // Generic tree structure with many operations
    type Tree<'T> =
        | Leaf of 'T
        | Node of Tree<'T> * 'T * Tree<'T>
    
    let rec map f tree = // ... implementation
    let rec fold f acc tree = // ... implementation
    let rec filter pred tree = // ... implementation
    let rec height tree = // ... 15 lines
    let rec balance tree = // ... 30 lines
    let rec traverse order tree = // ... 25 lines
    // ... 20 more tree operations

module Algorithms =
    // Specialized implementations for different types
    let inline sort< ^T when ^T : comparison> (items: ^T list) = 
        // ... 40 lines of optimized sorting
    
    let sortInts = sort<int>  // Specialized for integers
    let sortFloats = sort<float>  // Specialized for floats
    let sortStrings = sort<string>  // Specialized for strings
    // ... more specializations

// Your application
open Collections
let myTree = Node(Leaf 1, 2, Leaf 3)
let doubled = map ((*) 2) myTree

With Firefly’s type-aware tree shaking, we analyze not just function calls but type instantiations. We determine that:

• Only Tree<int> is used, not Tree<'T> for other types
• Only map is called on trees; fold, filter, balance, etc. are eliminated
• The generic sort function is never instantiated, so all specializations are removed

Early prototypes show 70-90% size reductions for generic-heavy libraries, far exceeding what traditional tree shaking achieves.

Direct FCS Analysis: Preserving What Matters

The Firefly compiler now operates directly on the F# Compiler Services AST, eliminating intermediate representations that lose crucial type information. This positioning enables unprecedented optimization opportunities by maintaining complete type context throughout the analysis.

The key insight is that FCS provides rich type information that traditional AST representations discard. By preserving this information, we can make intelligent decisions about what code is truly necessary:

1. Type Specialization Tracking: We trace which generic instantiations are actually used
2. Interface Implementation Analysis: We determine which interface methods are called
3. Discriminated Union Usage: We identify which union cases appear in pattern matches
4. Static Member Resolution: We track which static members and type extensions are referenced

This direct analysis enables cross-cutting optimizations. When we determine a type is unused, we can eliminate:

• The type definition itself
• All methods and properties on that type
• Any type extensions defined for it
• Generic specializations involving that type
• Pattern match cases for that type’s constructors

Type-Directed Reachability Analysis

The heart of effective tree shaking lies in precise reachability analysis. Our type-preserving approach goes beyond simple function-call tracking to understand the rich relationships in F# code:

// Type-aware reachability using enhanced FCS analysis
type ReachabilityContext = {
    TypeInstantiations: Map<TypeDefinition, Set<Type list>>
    UsedUnionCases: Map<UnionType, Set<UnionCase>>
    CalledInterfaceMethods: Map<InterfaceType, Set<MethodSignature>>
    ReachableFunctions: Set<FunctionDefinition>
    MemoryLayouts: Map<Type, MemoryLayout>
}

// Analyze type-directed dispatch
let analyzeMethodCall (ctx: ReachabilityContext) (callSite: FCSCallExpression) =
    match callSite with
    | InterfaceCall(interfaceType, methodSig, actualType) ->
        // Track both the interface method and concrete implementation
        ctx
        |> markInterfaceMethodUsed interfaceType methodSig
        |> markConcreteTypeUsed actualType
        |> traceImplementation actualType interfaceType methodSig
    
    | GenericCall(genericFunc, typeArgs) ->
        // Track specific generic instantiation
        ctx
        |> markGenericInstantiation genericFunc typeArgs
        |> analyzeSpecializedBody genericFunc typeArgs

This sophisticated analysis handles F#’s advanced type system features:

Discriminated Union Optimization

When analyzing discriminated unions, we track not just type usage but individual case usage:

type Command =
    | Start of ProcessInfo          // Used in pattern matches
    | Stop of ProcessId             // Used in pattern matches  
    | Pause of ProcessId * Duration // Never constructed or matched
    | Resume of ProcessId           // Never constructed or matched
    | Status of ProcessId           // Used only in construction, never matched
    | Restart of ProcessInfo        // Never used at all

// Analysis determines:
// - Pause, Resume, Restart can be eliminated entirely
// - Status needs constructor but not pattern match code
// - Only Start and Stop need full support

The memory layout analyzer integrates with tree shaking to optimize union storage based on actual usage patterns. If certain cases are eliminated, the union’s memory layout can be optimized accordingly.

Generic Specialization Tracking

F#’s inline functions and SRTP (Statically Resolved Type Parameters) create specialized code for each type instantiation. Our analysis tracks these precisely:

let inline sumBy< ^T, ^U when ^T : (member Length : int)
                          and ^U : (static member (+) : ^U * ^U -> ^U)
                          and ^U : (static member Zero : ^U)> 
    (projection: 'a -> ^U) (collection: ^T) = 
    // ... implementation

// Used with int arrays and float lists
let intSum = sumBy id [|1; 2; 3|]
let floatSum = sumBy (fun x -> x * 2.0) [1.0; 2.0; 3.0]

// Analysis generates exactly two specializations:
// sumBy<int[], int> and sumBy<float list, float>
// No generic version is retained

Integration with Memory Layout Analysis

One unique aspect of Firefly’s tree shaking is its deep integration with memory layout analysis. As we eliminate code, we simultaneously optimize memory layouts:

// Before tree shaking
type LargeRecord = {
    Field1: int          // Used
    Field2: string       // Never accessed
    Field3: DateTime     // Never accessed
    Field4: decimal      // Used
    Field5: int64        // Never accessed
    Nested: NestedType   // Never accessed
}

// After integrated analysis
// Memory layout optimized from 64 bytes to 16 bytes
// Only Field1 and Field4 remain, optimally packed

This integration enables sophisticated optimizations:

1. Field Elimination: Unused record fields are removed entirely
2. Layout Compaction: Remaining fields are reordered for optimal packing
3. Alignment Optimization: Alignment requirements are recalculated based on remaining fields
4. Inline Expansion: Small types may be inlined when usage patterns permit

Platform-Specific Tree Shaking

The Fidelity Framework’s multi-platform nature adds another dimension to tree shaking. Our analysis understands platform constraints and optimizes accordingly:

// Platform-aware analysis configuration
type TreeShakingConfig = {
    Platform: TargetPlatform
    MemoryConstraints: MemoryConstraints
    EnabledFeatures: Set<FeatureFlag>
    MaxStackDepth: int option
}

// Different platforms eliminate different code
[<PlatformSpecific>]
module Graphics =
    [<Desktop>] 
    let renderOpenGL() = // ... 500 lines
    
    [<Mobile>]
    let renderMetal() = // ... 400 lines
    
    [<Embedded>]
    let renderFramebuffer() = // ... 100 lines
    
    [<All>]
    let renderText(text: string) = // ... kept on all platforms

When compiling for an embedded target, the OpenGL and Metal renderers are eliminated before MLIR generation even begins. This platform-aware elimination combines with type analysis - if the embedded platform never uses certain types, their definitions and all associated code are removed.

Developer Experience: Understanding Elimination

The enhanced tree shaking provides rich diagnostics that include type information:

=== Firefly Type-Aware Tree Shaking Analysis ===
Source: HelloWorld.fs
Target: cortex-m4
Analysis: Type-preserving reachability from @main

Type Elimination Summary:
- Total type definitions: 89
- Used types: 23 (25.8%)
- Eliminated types: 66 (74.2%)
- Generic instantiations: 12 (from 47 possible)

Detailed Type Analysis:
  Collections.Tree<'T>:
    - Instantiated with: [int]
    - Methods retained: map, tryFind
    - Methods eliminated: fold, filter, balance, height (18 others)
    - Memory layout: 16 bytes (reduced from generic 24 bytes)
  
  IProcessor<'T>:
    - Instantiated with: [int; float32]
    - Implementations retained: IntProcessor, Float32Processor  
    - Implementations eliminated: FloatProcessor, DateProcessor, StringProcessor
    - Interface dispatch optimized to direct calls

Union Case Analysis:
  Command: 2 of 6 cases used (66.7% eliminated)
    - Memory layout optimized from 32 to 16 bytes
  Result<'T,'E>: Ok case only (Error case eliminated)
    - Converted to simple wrapper type

Memory Impact:
- Type definitions: 89KB → 18KB (79.8% reduction)
- Method tables: 134KB → 31KB (76.9% reduction)
- Generic specializations: 67KB → 14KB (79.1% reduction)
- Static data: 23KB → 8KB (65.2% reduction)

Largest Eliminated Types:
1. Graphics.RenderingEngine (4.2KB) - No usage on embedded platform
2. Collections.SortedMap<'K,'V> (3.8KB) - No instantiations found
3. Async.AsyncBuilder (3.1KB) - Async eliminated for embedded target

These diagnostics integrate with IDE support to provide real-time feedback. Developers can see which types and methods would be included in each platform target, enabling informed architectural decisions during development.

Advanced Optimization Through Type Information

The type-preserving pipeline enables sophisticated optimizations beyond simple elimination:

Devirtualization Through Type Analysis

When tree shaking determines that an interface has only one implementation in use, virtual calls become direct calls:

; Before: Virtual dispatch through interface
%vtable = load i8**, i8*** %obj
%method = getelementptr i8*, i8** %vtable, i32 3
%func = load i8*, i8** %method
call void %func(i8* %obj, i32 %arg)

; After: Direct call to known implementation
call void @IntProcessor.Process(i8* %obj, i32 %arg)

Memory Layout Specialization

Types used only in specific contexts can have their layouts optimized:

// Original generic type
type Option<'T> =
    | Some of 'T
    | None

// After analysis: Option<int> used only in non-null contexts
// Optimized to unwrapped int with sentinel value for None
// Reduces memory usage and eliminates pointer indirection

The Road Ahead

Tree shaking in the restructured Firefly compiler represents a fundamental shift in how we think about dead code elimination. By preserving type information throughout the compilation pipeline, we enable optimizations that were previously impossible:

1. Incremental Compilation: Type-aware dependency tracking enables precise incremental builds
2. Link-Time Type Optimization: Cross-module type specialization and elimination
3. Profile-Guided Type Specialization: Runtime profiling informs which generic instantiations to optimize
4. Formal Verification Integration: Eliminated code paths reduce the verification burden

The integration with our broader tooling ecosystem leverages this type information. The Fidelity VS Code extension will show not just which functions are included, but which types, which generic instantiations, and which pattern match cases made it into your binary. This visibility transforms tree shaking from a black-box optimization into a transparent, predictable process.

A New Paradigm for Functional Compilation

The journey from traditional tree shaking to type-aware elimination represents more than an incremental improvement; it’s a fundamental rethinking of how functional languages can be compiled. For years, the rich type systems that make languages like F# so expressive have been seen as a compile-time feature that largely disappears during code generation. Firefly’s approach inverts this, making types the central pillar of our optimization strategy.

What we’re building goes beyond eliminating unused functions. By tracking type instantiations, interface implementations, and union case usage, we can eliminate entire categories of code that traditional approaches must preserve “just in case.” When your embedded system uses only three cases of a twenty-case discriminated union, why should the binary include code for the other seventeen? When your application uses a generic collection only with integers, why preserve the infrastructure for arbitrary type parameters?

This transformation enables F# in domains where it was previously impractical. Embedded systems with kilobytes of flash storage become viable targets. High-frequency trading systems can eliminate every microsecond of virtual dispatch overhead. WebAssembly modules can achieve sizes competitive with hand-written JavaScript. The same F# code that expresses your domain elegantly can compile to binaries that meet the strictest size and performance requirements.

Type-Driven Future

Looking ahead, type-aware tree shaking is just the beginning of what’s possible when we preserve type information throughout compilation. The same infrastructure that enables precise dead code elimination can power:

• Type-Specialized Memory Pools: Allocators optimized for exactly the types your program uses
• Automatic Data Structure Selection: Choosing optimal collections based on usage patterns
• Cross-Language Type Optimization: Eliminating FFI overhead when types align perfectly
• Verification-Guided Elimination: Using formal proofs to enable more aggressive optimization

As we continue developing these capabilities, we’re guided by a simple principle: a language’s type system should be its greatest optimization asset, not a compile-time burden to be discarded. The Fidelity Framework, with Firefly at its heart, demonstrates that F#’s expressive types can drive unprecedented optimization while maintaining the safety and clarity that make functional programming so powerful.

The future we’re building is one where choosing F# means choosing both elegance and efficiency. Tree shaking exemplifies this vision - leveraging every bit of type information to produce binaries that are not just functional, but optimal. As we realize this vision of type-preserving compilation, we’re proving that functional programming’s abstractions can be truly zero-cost. The Fidelity Framework represents more than a new compiler; it’s a demonstration that type safety and raw performance are not opposing forces, but complementary aspects of a modern compilation strategy.