Compile packages independently

[aykevl]

Packages should be compiled independently and then linked together. This provides several advantages in the long term:

• Packages can be compiled in parallel so compile time can be shorter.
• Unchanged packages can be cached, further cutting down on compile time.
• We can optionally avoid LTO to make incremental (debug) builds much faster.

I would strive for the following architecture:

• Change the compiler package to compile just a single package (and not dependencies).
• Add a linker package that links several packages together and performs whole-program optimizations on them (LTO).
• Add a driver package (or repurpose the loader package?) that orchestrates all this work.
• Add some subcommands (go tool compile, go tool link) that call the compiler/linker directly. This can be useful for debugging.

I have taken a look at the Go build cache and I think I'd implement a similar system. Every package has a hash of the input (build tags, file list, hashes of files, output hashes of packages it depends on) and produces an output hash, which is a hash over all the artifacts that it builds (mostly the serialized exported types).

My thinking is that a cached package would be an uncompressed zip file stored in the cache directory, with the following contents as files:

• a list of packages it depends upon and their hashes (plain text)
• a list of files included in the build and their mtimes / hashes (plain text)
• a serialized form of the public API (some binary format, like this one)
• LLVM bytecode for this file (including C/C++ files, they are all linked together in one module / compile unit)

This is most likely too big to do at once, so I'd do it in multiple steps. But I'm creating this issue to give a high-level overview of what I would want to achieve at some point.

[aykevl]

Some statistics when building -target=circuitplay-express ./testdata/stdlib.go, one of the slowest compiles at the moment:

  load:    37.230169ms
  parse:   90.345719ms
  types:   211.548187ms
  dce:     11.11218ms
  irgen:   700.464742ms
compile: 1.214556923s
interp:  1.264428106s
opt:     4.707457718s
codegen: 475.201528ms
link:    65.829285ms
total:   8.211343631s

The entire compiler runs serially at the moment, while most of this could be parallelized and/or cached.

• the load step (which determines dependencies and to-be-compiled files) cannot be entirely parallelized, but dependencies can be loaded in parallel. However, there is not much to be gained here.
• parse can happen fully parallel per file. Dependencies do not have to be loaded yet, although we should probably start to parse leaf packages.
• typecheck can be done in parallel per package, after all dependent packages are typechecked. So it can start with leaf packages and move to the root.
• the dce step will probably be removed when building incrementally (it isn't very useful right now anyway except for speed)
• irgen can be done in parallel per package, after typecheck of that package is finished
• parts of interp can be parallelized per package, but not all of it. However, it may be possible to cache most of interp for (near)root packages which is a common case.
• opt can partially be done per package, or can be done entirely per package depending on whether LTO is used (there is no way to turn off LTO at the moment)
• codegen can be done per package if we skip LTO, or can perhaps be done efficiently using ThinLTO.
• link is already quite fast