We describe a compiler strategy we call “Software Multiplexing” that achieves the best of both statically linked and dynamically linked libraries, and adds some additional advantages. Specifically, it achieves the code size benefits of dynamically linked libraries while eliminating the major disadvantages: unexpected failures due to missing dependences, slow startup times, reduced execution performance due to indirect references to globals, and perhaps most importantly, the potential for security vulnerabilities. We design Software Multiplexing so that it works even in the common case where application build systems support only dynamic and not static linking; we have automatically built thousands of Linux software packages in this way. Software Multiplexing combines two key (and relatively simple) ideas: Automatic Multicall, i.e., where multiple independent programs are automatically merged into a single executable, and Static Linking of Shared Libraries, which works by linking an IR-level version of application code and all its libraries, even if the libraries are normally compiled as shared, before native code generation. The benefits are achieved essentially through deduplication of libraries across the multiplexed programs, while using static linking. We have implemented Software Multiplexing in a tool called allmux, part of the open-source ALLVM project. Compared with equivalent dynamically linked programs, allmux-optimized programs have significantly smaller startup times, and even have slightly lower memory usage and total disk size. Compared with equivalent statically linked programs, allmux-optimized programs are much smaller in both aggregate size and memory usage, and have very similar startup times and execution performance.