<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">Hi, all. David Ungar and Graydon Hoare have been doing compiler performance investigations, and in particular are interested in the cases where WMO-with-Onone builds are faster than the multi-file -Onone builds. By now this is out there as a hackaround for build time on targets with many files because the compiler spends too much time doing repeated work, and whatever work is saved by -incremental isn't worth it. -incremental is still very conservative and we could probably do better there, but meanwhile there's something to this: could we save on work in non-WMO mode by processing multiple "primary files" in one frontend invocation?<div class=""><br class=""></div><div class="">(This email is a bit of a brain dump on some of the past discussions on this, because David's fairly new to the Apple side of the compiler project, and even Graydon hasn't been here for all of it. I also realized partway through writing it that I already said a lot of this in&nbsp;<a href="https://github.com/apple/swift/blob/master/docs/Driver.md" class="">docs/Driver.md</a>, but that's more for outside people.&nbsp;<a href="https://github.com/apple/swift/blob/master/docs/DependencyAnalysis.rst" class="">docs/DependenciesAnalysis.rst</a>&nbsp;may also be relevant.)</div><div class=""><br class=""></div><div class="">First, some background:</div><div class=""><br class=""></div><div class=""><b class="">WMO mode</b></div><div class="">- one frontend process</div><div class="">- parses, resolves imports, and type-checks all files</div><div class="">- generates SIL for all files in a single SILModule</div><div class="">- usually generates N LLVM modules, which turn into N .o files in parallel</div><div class="">- does not support incremental builds, even under -Onone (one reason: it isn't guaranteed which content goes into which .o)</div><div class=""><br class=""></div><div class="">(There's also a fully single-threaded WMO mode which outputs a single .o file. This allows slightly more LLVM optimization at the cost of, well, being single-threaded. For historical reasons this is the default WMO mode on the command line, but isn't used by Xcode or SwiftPM.)</div><div class=""><br class=""></div><div class=""><b class="">Non-WMO mode</b></div><div class="">- a.k.a. "multi-file mode", "multi-frontend mode", "primary file mode", or "incremental mode" – there isn't really a standard name for this</div><div class="">- parses and resolves imports in all files, type-checks just the "primary file" (specified on command line)</div><div class="">- …but type-checking one file can sometimes require partially type-checking others (e.g. because you inherit from a class in another file). You pretty much always get to skip function bodies, though.</div><div class="">- generates SIL for the primary file in a SILModule</div><div class="">- generates 1&nbsp;<a href="http://llvm.org/docs/LangRef.html#module-structure" class="">LLVM module</a>, which results in one .o file</div><div class="">- very conservative incremental builds (as in, "err on the side of rebuilding")</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">So of course there's repeated work in the non-WMO mode. Parsing all files is something that we <i class="">don't</i>&nbsp;consider expensive because it's a relatively small part of the total compile time, though I can't remember if we're smart enough to delay parsing of function bodies in other files. However, it turns out even the cost of <i class="">opening</i>&nbsp;the files can matter. Beyond that, there are a number of other pieces of potentially repeated work:</div><div class=""><br class=""></div><div class="">- anything brought in through the Clang importer</div><div class="">- anything deserialized from a Swift module (usually the standard library)</div><div class="">- <i class="">searching</i>&nbsp;for modules on disk (both Clang modules and Swift modules)</div><div class="">- the "partial type-checking" I alluded to above</div><div class="">- synthesizing helper functions for things imported from Clang (for example, memberwise initializers for structs)</div><div class=""><br class=""></div><div class="">David suggested today the idea of a "multiple primary file" mode to speed up compiles (prompting this email), which isn't a bad idea. However, we definitely want to be sure we don't break incremental builds. That means a few restrictions:</div><div class=""><br class=""></div><div class="">- We still want to generate one object file per source file.</div><div class="">- This object file has to be self-contained, in case we don't rebuild it next time, or <i class="">do</i>&nbsp;rebuild something it depends on.</div><div class="">- The easiest way to guarantee one self-contained object file is to have one LLVM module.</div><div class="">- But we probably also want one <i class="">SIL</i>&nbsp;module per source file, since SILModule has a field that controls what scope we can assume perfect information for, and it wouldn't be self-contained to have that cross source file boundaries. (I don't trust us to only use this during optimization, either.)</div><div class="">- The Swift AST and ASTContext are not thread-safe, so we can't process multiple SILModules in different threads today.</div><div class="">- When we <i class="">do</i>&nbsp;synthesize helper functions that aren't associated with a source file, we probably need to put them in <i class="">every</i>&nbsp;object file.</div><div class=""><br class=""></div><div class="">So, the least intrusive approach here that still supports incremental builds would be to type-check multiple files, but then serially process a separate SILModule for each "primary file". (We might want to call them something more like "active files".) This is (probably) what David was getting at.</div><div class=""><br class=""></div><div class="">However…</div><div class=""><br class=""></div><div class="">…there's something more interesting.</div><div class=""><br class=""></div><div class=""><b class="">Pipelining</b></div><div class=""><b class=""><br class=""></b></div><div class="">Currently, the way we incrementally build a project is by passing all input files to the Swift driver, which decides which files need to be rebuilt and then spawns a bunch of "frontend jobs", one per primary file that needs to be rebuilt. (It's actually a little worse than this because we may&nbsp;<a href="https://github.com/apple/swift/blob/master/docs/Driver.md#incremental-builds" class=""><a href="https://github.com/apple/swift/blob/master/docs/Driver.md#incremental-builds" class="">discover that a file needs to be rebuilt</a>&nbsp;only after doing some of the work</a>.) The "least intrusive" approach I described above would partition up the files we <i class="">know</i>&nbsp;we need to rebuild ahead of time, but it would still end up spawning new jobs for those "late-discovered" files. It could also end up accidentally putting five long files on one job and five short files on another, which isn't a great use of resources.</div><div class=""><br class=""></div><div class="">An alternate approach would be what Daniel Dunbar has called <i class="">pipelining:</i>&nbsp;when a particular frontend job is done, the parent process should be able to send it another file to work on, starting from the type-checking phase.</div><div class=""><br class=""></div><div class="">There are some downsides to pipelining:</div><div class="">- Even less deterministic than a normal parallel build (if "less deterministic" can be considered a thing)</div><div class="">- Harder to test – we'd have to make the "multiple primary file" mode anyway just to ensure the same series of processing.</div><div class="">- Unbounded growth – we'd probably want to start from scratch at some point if memory usage exceeded some threshold.</div><div class=""><br class=""></div><div class="">But overall I think this fits our model better, and if we can figure out a good way to communicate between the frontend and driver this is the way to go.</div><div class=""><br class=""></div><div class="">(Since David recently pushed through a nice refactoring of CompilerInstance::performSema, we know there's an additional complication around targets that have a main.swift—today we type-check that file piecemeal instead of parsing it all at once. We'd probably either subset main.swift out from this optimization, or figure out if we can drop the weird special-case type-checking.)</div><div class=""><br class=""></div><div class=""><b class="">Faster Optimized Builds?</b></div><div class=""><b class=""><br class=""></b></div><div class="">Also important! But since we expect most optimized builds these days are WMO builds, this sort of approach is <i class="">less</i>&nbsp;important than it might otherwise be.</div><div class=""><br class=""></div><div class=""><b class="">Incremental Optimized Builds?</b></div><div class=""><b class=""><br class=""></b></div><div class="">Unlikely for WMO, although there's already a small optimization where if a particular LLVM module's contents are exactly the same as the last build, we won't bother re-optimizing at the LLVM level. For non-WMO, naively extending the current model would require that we were sure that the current dependency tracking mechanism included all information that the optimizer uses, which I'm not confident about. However, we've talked (idly) about doing incremental processing up to the "mandatory optimizations" in SIL, i.e. up until we've produced canonical SIL and emitted flow-sensitive diagnostics. We would then write this to disk (we call these "SIB" files, for "Swift Intermediate Binary file") and then do a non-incremental stage turning this into object files. We could even do cross-file WMO-like optimization this way, either by using a single process that merged in all the SIB information, or by loading all N files into multiple processes, each responsible for one or more object files.</div><div class=""><br class=""></div><div class="">But of course, within most optimized builds, type-checking and SILGen is at most a third of the build time, usually less. So it's unclear whether this would be a net win given all the extra overhead.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">That's probably all the relevant information I have right now, but it seems like quite enough.</div><div class=""><br class=""></div><div class="">Jordan</div></body></html>