Low-level cross-language post-link optimisation

Abstract

A Foreign Function Interface (FFI) is a powerful tool that allows a method in one language to invoke another method from a distinct language. Unlike calls within the bounds of the same language, invocations through the FFI crossing a language barrier incur a significant overhead, due to both missed optimisation opportunities and the required glue code or trampolines. Since the redundancies are exposed only at link time when the modules of the participating languages are merged together to form the final program, ameliorating the overhead of FFI calls falls within the scope of link-time or post-link optimisers. Presently, such optimisers lack the required specialised transformations to fully exploit the optimisation opportunities exposed by the cross-language context and rely on representations that are either more abstract than some of the participating languages or unreasonably difficult to analyse as they discard all relevant structure. This thesis tackles the problem of cross-language optimisation by introducing the Duplo framework and its associated analyses and transformations. Duplo is built around the Low-Level Intermediate Representation (LLIR), capable of representing both high-level and low-level languages, such as OCaml, Rust and C. The representation is generated through custom compiler backends and assembled into modules carrying whole program information through a specialised toolchain, before optimisations are applied and executable machine code is emitted. Most importantly, LLIR enables inlining across FFI calls, creating opportunities for other improvements. In addition to applying a series of well-established inter-procedural analyses and transformations adapted to the cross-language context, the framework includes novel algorithms designed to operate specifically on global representations, aimed at simplifying the startup path and extracting type information compatible with all source languages for use in further optimisation passes. The Duplo framework and its associated cross-language and inter-procedural optimisations yield substantial benefits in excess of existing tools, improving both the code-size and performance. Results are demonstrated on a diverse range of macro- and micro-benchmarks testing widely used functionality, along with real-world applications.