Analysis and Critique of RemoveRedundantCallsToStaticInitializersPhase

This document combines a walkthrough of the RemoveRedundantCallsToStaticInitializersPhase with a critique of its algorithmic approach, discussing potential performance implications and alternatives.

Part 1: Walkthrough and Subdependencies

This section provides a walkthrough of the phase definition and its core subdependencies in the Kotlin/Native compiler, based on the source code in LTO.kt.

Walkthrough of Phase Definition

The phase is defined in LTO.kt.

internal val RemoveRedundantCallsToStaticInitializersPhase = createSimpleNamedCompilerPhase<NativeGenerationState, RedundantCallsInput>(
        name = "RemoveRedundantCallsToStaticInitializersPhase",
        preactions = getDefaultIrActions(),
        postactions = getDefaultIrActions(),
        op = { generationState, input ->
            val context = generationState.context
            val moduleDFG = input.moduleDFG

            val callGraph = CallGraphBuilder(
                    context,
                    input.irModule,
                    moduleDFG,
                    devirtualizedCallSitesUnfoldFactor = Int.MAX_VALUE,
                    nonDevirtualizedCallSitesUnfoldFactor = Int.MAX_VALUE
            ).build()

            val rootSet = DevirtualizationAnalysis.computeRootSet(context, input.irModule, moduleDFG)
                    .mapNotNull { it.irFunction }
                    .toSet()

            StaticInitializersOptimization.removeRedundantCalls(generationState, input.irModule, moduleDFG, callGraph, rootSet)
        }
)

Key Steps:

  1. Call Graph Construction: The phase builds a call graph using CallGraphBuilder. It sets both devirtualizedCallSitesUnfoldFactor and nonDevirtualizedCallSitesUnfoldFactor to Int.MAX_VALUE. This ensures that the analysis aggressively unfolds all possible targets of virtual calls, providing a very precise (but potentially large) call graph.
  2. Root Set Computation: It computes the set of entry points or roots for the analysis using DevirtualizationAnalysis.computeRootSet. This includes the program entry point, exported functions, and initializers.
  3. Optimization Execution: It calls StaticInitializersOptimization.removeRedundantCalls to perform the actual analysis and transformation.

Subdependencies

A. CallGraphBuilder.build()

Located in CallGraphBuilder.kt.

This method builds the call graph by tracing reachability from the root set. Because the unfold factors are set to Int.MAX_VALUE, it will resolve virtual calls to all possible overriding methods based on the type hierarchy, leading to a more complete graph.

B. DevirtualizationAnalysis.computeRootSet()

Located in DevirtualizationAnalysis.kt.

This method identifies all entry points into the module, such as the main function, public or exported functions, static field initializers, and functions leaking through raw references.

C. StaticInitializersOptimization.removeRedundantCalls()

Located in StaticInitializersOptimization.kt.

This is the core of the optimization. It performs a 3-phase interprocedural data flow analysis:

  1. Phase 1: Computes which files are initialized after returning from a function.
  2. Phase 2: Computes which files are initialized before executing a function.
  3. Phase 3: Collects call sites where initializer calls can be extracted.

Finally, it modifies the IR to remove redundant calls or move them to call sites where they are actually needed.

Part 2: Algorithmic Critique vs. Micro-Optimization

During the discussion, we identified that focusing solely on profiling for micro-optimizations might be premature if the underlying algorithm is fundamentally too aggressive or flawed for scale.

1. Aggressive Call Graph Unfolding

The phase uses Int.MAX_VALUE for both devirtualizedCallSitesUnfoldFactor and nonDevirtualizedCallSitesUnfoldFactor.

  • The Issue: This forces the compiler to resolve every virtual call to all possible overrides, creating a massive call graph in large projects with deep hierarchies or many implementations of an interface. This can cause exponential explosion in edges, leading to high memory and CPU usage.
  • Potential Solution: Limiting this factor to a small number (e.g., 5) or using a simpler heuristic would make the call graph smaller and the analysis faster, likely with minimal loss in optimization precision.

2. Multi-Phase Iterative Analysis

The analysis runs in 3 phases and iterates to find a fixed point (fixed-point iteration over strongly connected components).

  • The Issue: This can be slow if call graph components are large and deep, leading to many iterations.
  • Potential Solution: Simplifying the analysis to be more local or conservative, or combining it with other analysis passes that build similar graphs, could reduce redundant work.

Conclusion

Profiling is still useful to diagnose the algorithm (e.g., to prove that graph construction dominates the time), but the solution to performance issues may lie in changing the algorithm parameters (like the unfold factors) rather than optimizing the code implementation itself.