Guided linking: Dynamic linking without the costs

Sean Bartell, Will Dietz, Vikram S. Adve

Research output: Contribution to journalArticlepeer-review

Abstract

Dynamic linking is extremely common in modern software systems, thanks to the flexibility and space savings it offers. However, this flexibility comes at a cost: it's impossible to perform interprocedural optimizations that involve calls to a dynamic library. The basic problem is that the run-time behavior of the dynamic linker can't be predicted at compile time, so the compiler can make no assumptions about how such calls will behave. This paper introduces guided linking, a technique for optimizing dynamically linked software when some information about the dynamic linker's behavior is known in advance. The developer provides an arbitrary set of programs, libraries, and plugins to our tool, along with constraints that limit the possible dynamic linking behavior of the software. By taking advantage of the constraints, our tool enables any existing optimization to be applied across dynamic linking boundaries. For example, the NoOverride constraint can be applied to a function when the developer knows it will never be overridden with a different definition at run time; guided linking then enables the function to be inlined into its callers in other libraries. We also introduce a novel code size optimization that deduplicates identical functions even across different parts of the software set. By applying guided linking to the Python interpreter and its dynamically loaded modules, supplying the constraint that no other programs or modules will be used, we increase speed by an average of 9%. By applying guided linking to a dynamically linked distribution of Clang and LLVM, and using the constraint that no other software will use the LLVM libraries, we can increase speed by 5% and reduce file size by 13%. If we relax the constraint to allow other software to use the LLVM libraries, we can still increase speed by 5% and reduce file size by 5%. If we use guided linking to combine 11 different versions of the Boost library, using minimal constraints, we can reduce the total library size by 57%.

Original languageEnglish (US)
Article number145
JournalProceedings of the ACM on Programming Languages
Volume4
Issue numberOOPSLA
Early online dateNov 13 2020
DOIs
StatePublished - Nov 13 2020

Keywords

  • Code deduplication
  • Dynamic Linking
  • IR
  • LLVM
  • LTO
  • Link-Time Optimization
  • Plugins
  • Shared Libraries

ASJC Scopus subject areas

  • Software
  • Safety, Risk, Reliability and Quality

Fingerprint

Dive into the research topics of 'Guided linking: Dynamic linking without the costs'. Together they form a unique fingerprint.

Cite this