Intelligent Tree Shaking

When we set out to design the Composer compiler for the Fidelity Framework, one of our core goals was to produce minimal native executables. In traditional .NET development, a “Hello World” application carries the weight of the runtime and referenced assemblies, resulting in deployments measured in megabytes. For embedded systems, high-frequency trading platforms, or any scenario where every byte matters, that overhead is a real cost. Our design takes a principled approach: semantic reachability analysis that operates on the Program Semantic Graph (PSG), narrowing the compilation scope to only what’s actually needed while preserving the type information required by subsequent compiler phases.

Concrete Example: HelloWorld with CCS Intrinsics

Consider a simple Fidelity application using the native type system:

module Examples.HelloWorldDirect

[<EntryPoint>]
let main argv =
    Console.WriteStr "Hello, World!"
    Console.WriteStrLn ""
    0

The native type system contains thousands of functions across console I/O, memory management, UTF-8 text processing, buffer handling, and more. Yet tree shaking ensures this simple program includes only:

• Console.WriteStr and Console.WriteStrLn from Console
• The underlying system call wrappers these functions use
• NativeStr type definition (the native string representation)

Everything else in the native type system - the ReadLine functions, the stackBuffer allocator, the UTF-8 encoding utilities, the Result combinators - is eliminated because our semantic reachability analysis determines they’re never called from main.

Tree Shaking Through Type-Preserving Analysis

Tree shaking is a form of dead code elimination that removes unused code from the 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. Composer’s approach leverages Clef’s type system throughout the reachability analysis, which lets it act on information that call-graph-only dead code elimination does not carry.

Our type-aware analysis extends traditional dead code elimination in the following way:

// 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)

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

Call-graph-only tree shaking struggles to determine which processor implementations are actually used. Composer’s type-preserving analysis traces the type instantiations through the program, determining that only IProcessor<int> and IntProcessor are needed. The FloatProcessor and DateProcessor, along with their associated type specializations, are eliminated.

.NET’s Native AOT compilation reaches this precision less directly. Microsoft has made progress with ahead-of-time compilation across .NET 8 through 10, and the approach still contends with the runtime’s historical reliance on reflection and dynamic code generation. Generic type instantiation is a particular difficulty: the AOT compiler cannot always determine which ILogger<T> instantiations an application will request through dependency injection, which leads to either over-inclusion of code or runtime failures. Attributes like RequiresDynamicCodeAttribute and DynamicallyAccessedMembers let developers annotate their code for trimming compatibility, working around a system whose original design did not treat static analysis as a primary concern.

By building on Clef’s type system and its deterministic foundations, the compiler constructs a full dependency graph at compile time. There is no reflection to defeat tree shaking and no dynamic instantiation to second-guess, so the reachable set the analysis computes is exact rather than conservative.

Consider a typical Clef 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

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

Composer’s type-aware tree shaking analyzes function calls and type instantiations together. 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, exceeding what call-graph-only tree shaking achieves.

The precision comes from where the analysis sits in the pipeline. Composer analyzes Clef source through FCS before any lowering to intermediate representations, so it has access to the full semantic context: which generic instantiations are actually constructed, which type parameters flow through which call sites, and which paths through the code are reachable. The PSG captures these relationships directly rather than reconstructing them from assembly metadata, where a single generic definition and its instantiation sites are already separated. Because the reachable set is computed before any information is discarded, there are no trimming warnings to suppress and no runtime directive files to maintain.

Soft-Delete Reachability: The Nanopass Approach

An architectural element that differentiates Composer from traditional compilation approaches is soft-delete reachability rather than hard deletion. When we determine a node is unreachable, we don’t remove it from the Program Semantic Graph - we mark it with IsReachable = false. This preserves structural integrity for Baker’s two-tree zipper traversal, where unreachable nodes still provide traversal context that keeps analysis aligned during PSG construction. Without this context, the zipper’s simultaneous traversal of the AST and typed tree could lose synchronization when encountering nodes that exist in one tree but not the other.

  graph TB
    FS[Clef Source] --> FCS[F# Compiler Services]
    FCS --> P1[Phase 1: Structural Construction]
    P1 --> P2[Phase 2: Symbol Correlation]
    P2 --> P3[Phase 3: Semantic Reachability]
    P3 --> P4["Phase 4: Type Resolution (Baker)"]
    P4 --> ENRICH[Enrichment Nanopasses]
    ENRICH --> ALEX["Code Generation (Alex)"]
    ALEX --> MLIR[MLIR → LLVM IR]
    MLIR --> BIN[Native Binary]

The critical boundary is Phase 3 - reachability analysis. Everything before Phase 3 operates on the full library graph (including all CCS intrinsics, FSharp.Core, and user code). Everything from Phase 3 onward operates on the narrowed graph - only the code actually reachable from entry points. This scope narrowing is what makes expensive operations like SRTP resolution and type overlay practical.

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

Precise reachability analysis carries the weight of effective tree shaking. Our type-preserving approach goes past function-call tracking to reach the type relationships in Clef code:

// Semantic reachability context - tracks what's actually used
type SemanticReachabilityContext = {
    ReachableFunctions: Set<string>
    TypeInstantiations: Map<string, Set<string>>
    UsedUnionCases: Map<string, Set<string>>
    CalledInterfaceMethods: Map<string, Set<string>>
    EntryPoints: FSharpSymbol list
}

// Two-level reachability: symbol-level and node-level
let analyzeReachability (psg: ProgramSemanticGraph) (entryPoints: FSharpSymbol list) =
    // Phase 1: Symbol-level reachability - which functions are called?
    let reachableSymbols =
        entryPoints
        |> List.fold (fun acc entry ->
            transitiveClosureFrom entry psg.CallGraph
            |> Set.union acc) Set.empty

    // Phase 2: Node-level reachability - mark all nodes in reachable functions
    psg.Nodes
    |> Seq.iter (fun node ->
        let isReachable =
            reachableSymbols.Contains(node.ContainingSymbol.FullName)
        node.IsReachable <- isReachable)

    { ReachableFunctions = reachableSymbols
      TypeInstantiations = collectTypeInstantiations psg reachableSymbols
      UsedUnionCases = collectUnionCaseUsage psg reachableSymbols
      CalledInterfaceMethods = collectInterfaceCalls psg reachableSymbols
      EntryPoints = entryPoints }

The analysis covers Clef’s advanced type system features:

Discriminated Union Optimization

When analyzing discriminated unions, we track usage down to the individual case, one level finer than whole-type tracking:

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

Clef’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
 

Library Boundary Classification

Composer’s reachability analysis understands the layered architecture of a Fidelity application. Code is classified into distinct library boundaries:

type LibraryCategory =
    | UserCode        // Application code - most aggressive elimination
    | CCSIntrinsics   // Fidelity native type system
    | FSharpCore      // F# runtime support
    | Other of string // Third-party libraries
 

This classification enables targeted optimization strategies. User code receives the most aggressive pruning since we have complete visibility. CCS intrinsic functions can be eliminated with confidence because we understand their semantic contracts. FSharp.Core functions require more conservative analysis due to their foundational role in Clef semantics.

The result is a library-aware pruning analysis:

type LibraryAwareReachability = {
    BasicResult: ReachabilityResult
    LibraryCategories: Map<string, LibraryCategory>
    PruningStatistics: PruningStatistics
    MarkedPSG: ProgramSemanticGraph
}

Integration with Memory Layout Analysis

One unique aspect of Composer’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. Getting the artifact small enough to flash is what makes the pure-Clef microcontroller unikernel fit.

Developer Experience: Understanding Elimination

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

=== Composer Semantic Reachability Analysis ===
Source: HelloWorldDirect.fs
Target: cortex-m4
Entry point: Examples.HelloWorldDirect.main

Pruning Statistics:
  Total symbols:      1,247
  Reachable symbols:    23
  Eliminated symbols: 1,224 (98.2%)
  Computation time:     12ms

Library Breakdown:
  UserCode:     3 reachable /    3 total (100.0%)
  CCSIntrinsics: 8 reachable /  412 total (  1.9%)
  FSharpCore:  12 reachable /  832 total (  1.4%)

Reachable Symbol Summary:
  User code:
    - Examples.HelloWorldDirect.main
    - <Module>.main$cont@7

  Console:
    - WriteStr
    - WriteStrLn
    - writeToStdout (internal)

  NativeTypes:
    - NativeStr (type definition)
    - toByteSpan

Type Analysis:
  Generic instantiations used: 2 (from 156 possible)
  Union cases reachable: 0 (Result<_,_> eliminated entirely)
  Interface dispatch sites: 0 (no virtual calls)

PSG Nodes:
  Total:     4,892
  Marked reachable: 156
  Elimination rate: 96.8%

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 can be devirtualized. At the MLIR level, Composer emits interface dispatch operations that mlir-opt and LLVM optimize into direct calls:

// Before devirtualization: Interface dispatch in MLIR
%obj_ref = memref.alloca() : memref<1x!processor.interface>
%arg = arith.constant 42 : i32
func.call @IProcessor.Process(%obj_ref, %arg) : (memref<1x!processor.interface>, i32) -> ()

// After tree-shaking analysis determines single implementation:
// LLVM backend generates direct call (no vtable lookup)
// call void @IntProcessor.Process(ptr %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 Composer 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 which functions are included, and then go finer: 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 Concurrent 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 concurrent functional languages can be compiled. For years, the rich type systems that make languages like Clef so expressive have been seen as a compile-time feature that largely disappears during code generation. Composer’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 Clef 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 Clef 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 Composer at its heart, demonstrates that Clef’s expressive types can drive unprecedented optimization while maintaining the safety and clarity that make concurrent functional programming so powerful.

The future we’re building is one where choosing Clef means choosing both elegance and efficiency. Tree shaking exemplifies this vision, leveraging every bit of type information to produce binaries that stay correct while running at the optimum. 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 reinforce each other within a modern compilation strategy, each strengthening what the other can deliver.

Cross-References:

• Baker: Saturation Engine - Type resolution and the zipper-based correlation pipeline
• Absorbing Alloy - The native standard library absorbed into CCS
• Hello World Goes Native - Sample programs demonstrating native compilation
• Why Clef Fits MLIR - The theoretical foundation connecting functional programming to modern compilation
• Nanopass Navigation - The compilation phase architecture