TY - JOUR
T1 - Guided linking
T2 - Dynamic linking without the costs
AU - Bartell, Sean
AU - Dietz, Will
AU - Adve, Vikram S.
N1 - Funding Information:
This material is based upon work supported by the National Science Foundation under Grant No. 1564274, and by the Office of Naval Research under Grant No. N00014-17-1-2996. We thank Hashim Sharif, Abdul Rafae Noor, Sibin Mohan, and the anonymous reviewers for their feedback.
Publisher Copyright:
© 2020 Owner/Author.
PY - 2020/11/13
Y1 - 2020/11/13
N2 - 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%.
AB - 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%.
KW - Code deduplication
KW - Dynamic Linking
KW - IR
KW - LLVM
KW - LTO
KW - Link-Time Optimization
KW - Plugins
KW - Shared Libraries
UR - http://www.scopus.com/inward/record.url?scp=85097583430&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85097583430&partnerID=8YFLogxK
U2 - 10.1145/3428213
DO - 10.1145/3428213
M3 - Article
AN - SCOPUS:85097583430
SN - 2475-1421
VL - 4
JO - Proceedings of the ACM on Programming Languages
JF - Proceedings of the ACM on Programming Languages
IS - OOPSLA
M1 - 145
ER -