Cache and reuse object files and/or LLVM bitcode when compiling to LLVM

yorickpeterse commented 1 year ago

Description

https://github.com/inko-lang/inko/pull/508 introduces a native code compiler uses LLVM, replacing the bytecode interpreter. The compiler compiles everything from scratch every time. While our own parts of the compiler (e.g. generating MIR) are plenty fast, LLVM is quite slow, and easily takes up over 90% of the compilation time.

One way we can improve this is by caching object files, and only lowering MIR modules to LLVM IR if they have changed compared to the cached files. I briefly experimented with this, and in the best case it can drastically cut down the compile times.

A challenge here is that I'm not sure if LLVM can optimise across the LLVM module boundary. If so, then caching the modules may hinder optimisations, because LLVM wouldn't be aware of them. If LLVM only optimises on a per-module basis, then we can cache the modules.

I did also experiment with caching/loading LLVM bitcode, but this doesn't seem to improve compile times much, as most of the time is spent generating the object files; not generating and optimising the LLVM IR.

The object cache would be applied in addition to any other future caching/incremental compilation techniques, should there be a need for them in the future.

Tasks

[ ] Move LLVM optimisation code from llvm::passes::Compile::run_all into a separate function
[ ] Move object generation code from llvm::passes::Compile::run_all into a separate function
[ ] Add ModuleId::modified_at so we can fetch the last modification time, if any
[ ] For each MIR module, record the modules that depend on it directly through an import
[ ] For each MIR module, check if its object file exists. If so, check if the MIR module has been modified since the object file was created. If so, or if the object file doesn't exist, set a "update" flag for the MIR module
[ ] Iterate over each MIR module. If the "update" flag is set, recursively set the flag for any modules that depend on it, unless the flag is already set
[ ] Iterate over each MIR module. If "update" is set, lower the module to LLVM IR and schedule it for object file generation
[ ] Optimise and generate the object files for each scheduled module
[ ] Return a list of paths that includes the updated object files and the cached ones

Related issues

https://github.com/inko-lang/inko/issues/674

yorickpeterse commented 8 months ago

I've been looking into this starting this week.

To effectively cache LLVM object files, we need to change how we generate symbol names. Specifically, we have to stop using type IDs and instead use the type shapes to generate unique names for specialized methods and types. This way it doesn't matter in which order the object files are generated, as the symbol X always refers to the same thing.

Specialization makes things tricky: consider modules A, B, and C. We store specialized types/methods in the module the generic base type/method originated from. Let's say this is A. If B creates a new specialization but A itself didn't change, and B did, we have to somehow flag A as "changed" such that we generate the new object code for it. This requires that we can somehow track if specialized types are new compared to the last run, or if they're the same. We can't just blindly flag A as changed if B changed, because that could result in unnecessary cache invalidations of A.

Further, if/when we swap out LLVM with a different backend, code generation may become fast enough to warrant a caching strategy that we can scale to different compiler stages (e.g. caching MIR). I'm also not yet sure how to approach that.

Given the goal is to make compilation faster, and Cranelift is becoming more mature, perhaps I should first take another look at using Cranelift instead of LLVM.

yorickpeterse commented 8 months ago

83713aa9 decouples the symbol names from the type IDs, meaning the order in which modules are processed is no longer relevant when generating object files.

inko-lang / inko