diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/compilation.md | 164 |
1 files changed, 164 insertions, 0 deletions
diff --git a/docs/compilation.md b/docs/compilation.md new file mode 100644 index 00000000..27161115 --- /dev/null +++ b/docs/compilation.md @@ -0,0 +1,164 @@ +# Compilation Pipeline + +For a simple single-file program, the compilation process has a dependency +graph that looks like this: +``` + +----------+ transpile +------------+ generate arg parser + | foo.tm.h | <----------- | foo.tm | ------------- + +----------+ +------------+ | + | | | transpile | + | | v | + | | +------------+ | + | | | foo.tm.c | +--------------------+ + | | +------------+ | main() entry point | + | | | +--------------------+ + | | compile v | + | | +------------+ | + | +----------------->| foo.tm.o | | + | +------------+ | + | | link | + | v | + | compile +------------+ compile | + +---------------------> | foo | <------------+ + +------------+ +``` + +For a more complicated example, imagine `foo.tm` imports `baz.tm` and both are +being compiled into a shared library, `libfoo.so`: + +``` + +---------------------------------------+ + | | + +----------+ transpile +------------+ | + +- | baz.tm.h | <----------- | baz.tm | -+-------------------------+ + | +----------+ +------------+ | | + | | | | | + | | | transpile | | + | | v | | + | | +------------+ | | + | | | baz.tm.c | | | + | | +------------+ | | + | | | | | + | | | compile | | + | | v | | + | | compile +------------+ | | + | +---------------------> | baz.tm.o | | | + | +------------+ | | + | | | | + | | link | compile | + | v v | + | compile +--------------------------------------+ | + | +---------------------> | libfoo.so | | + | | +--------------------------------------+ | + | | ^ | + | | | link | + | | | | + | +----------+ transpile +------------+ | | + | | foo.tm.h | <----------- | foo.tm | | | + | +----------+ +------------+ | | + | | | | | + | | | transpile | | + | | v | | + | | +------------+ | type info | + | | | foo.tm.c | <+-------------------------+ + | | +------------+ | + | | | | + | | | compile | + | | v | + | | compile +------------+ | + +----+---------------------> | foo.tm.o | -+ + | +------------+ + | compile ^ + +-------------------------+ +``` + +These dependency graphs are relatively complicated-looking, but here are some +rough takeaways: + + 1) Header files are a dependency for many parts of the process, so it's + good to transpile them as early as possible. + 2) Once all the header files are available, + compiled into their object files in parallel. This is by far the + slowest part of compilation (invoking the C compiler), so it benefits + the most from parallelization. + 3) After all object files are compiled, the last step is to link them + all together (fast and simple). + +To sastisfy these requirements as efficiently as possible, the approach taken +below is to first transpile all header files sequentially (this could be +parallelized, but is probably faster than the overhead of forking new +processes), then fork a new process for each dependency to transpile and +compile it to an object file. Then, wait for all child processes to finish and +link the resulting object files together. + +## Phase 1 (sequential transpilation): + +``` + +--------+ +--------+ + | foo.tm | | baz.tm | + +--------+ +--------+ + | | | + +--------------+ | + | | + v v + +----------+ +----------+ + | foo.tm.h | | baz.tm.h | + +----------+ +----------+ +``` + +## Phase 2 (parallel transpilation/compilation): + +``` + ################################ ################################ + # Process 1 # # Process 2 # + # +--------+ +----------+ # # +----------+ +--------+ # + # | foo.tm | | foo.tm.h | # # | baz.tm.h | | baz.tm | # + # +--------+ | baz.tm.h | # # +----------+ +--------+ # + # | +----+-----+ # # | | # + # v | # # | v # + # +----------+ | # # | +----------+ # + # | foo.tm.c | | # # | | baz.tm.c | # + # +----------+ | # # | +----------+ # + # | | # # | | # + # +------+------+ # # +--------+ # + # | # # | # + # v # # v # + # +----------+ # # +----------+ # + # | foo.tm.o | # # | baz.tm.o | # + # +----------+ # # +----------+ # + ################################ ################################ +``` + +## Phase 3 (linking a shared object file library): + +``` + +----------+ +----------+ + | foo.tm.o | | baz.tm.o | + +----------+ +----------+ + | | + +--------+--------+ + | + v + +-----------+ + | libfoo.so | + +-----------+ +``` + +## Phase 3 (linking an executable): + +``` + +----------+ +----------+ +--------+ +--------+ + | foo.tm.o | | baz.tm.o | | foo.tm | | baz.tm | + +----------+ +----------+ +--------+ +--------+ + | | | | + +--------+--------+ +----+-----+ + | link | Figure out command line args + v v + +-----+ compile +-------------------------+ + | foo |<-------------| main() function for exe | + +-----+ +----------+--------------+ + | foo.tm.h | + +----------+ + | baz.tm.h | + +----------+ +``` |