1 # Compilation Pipeline
   2 
   3 For a simple single-file program, the compilation process has a dependency
   4 graph that looks like this:
   5 ```
   6   +----------+  transpile   +------------+  generate arg parser   
   7   | foo.tm.h | <----------- |   foo.tm   | -------------
   8   +----------+              +------------+              |
   9     |    |                    | transpile               |
  10     |    |                    v                         |
  11     |    |                  +------------+              |
  12     |    |                  |  foo.tm.c  |         +--------------------+
  13     |    |                  +------------+         | main() entry point |
  14     |    |                    |                    +--------------------+
  15     |    |          compile   v                         |
  16     |    |                  +------------+              |
  17     |    +----------------->|  foo.tm.o  |              |
  18     |                       +------------+              |
  19     |                         | link                    |
  20     |                         v                         |
  21     |          compile      +------------+  compile     |
  22     +---------------------> |    foo     | <------------+
  23                             +------------+
  24 ```
  25 
  26 For a more complicated example, imagine `foo.tm` imports `baz.tm` and both are
  27 being compiled into a shared library, `libfoo.so` (or `libfoo.dylib` on Mac):
  28 
  29 ```
  30         +---------------------------------------+
  31         |                                       |
  32       +----------+  transpile   +------------+  |
  33    +- | baz.tm.h | <----------- |   baz.tm   | -+-------------------------+
  34    |  +----------+              +------------+  |                         |
  35    |    |                         |             |                         |
  36    |    |                         | transpile   |                         |
  37    |    |                         v             |                         |
  38    |    |                       +------------+  |                         |
  39    |    |                       |  baz.tm.c  |  |                         |
  40    |    |                       +------------+  |                         |
  41    |    |                         |             |                         |
  42    |    |                         | compile     |                         |
  43    |    |                         v             |                         |
  44    |    |          compile      +------------+  |                         |
  45    |    +---------------------> |  baz.tm.o  |  |                         |
  46    |                            +------------+  |                         |
  47    |                              |             |                         |
  48    |                              | link        | compile                 |
  49    |                              v             v                         |
  50    |               compile      +--------------------------------------+  |
  51    |    +---------------------> |              libfoo.so               |  |
  52    |    |                       +--------------------------------------+  |
  53    |    |                                       ^                         |
  54    |    |                                       | link                    |
  55    |    |                                       |                         |
  56    |  +----------+  transpile   +------------+  |                         |
  57    |  | foo.tm.h | <----------- |   foo.tm   |  |                         |
  58    |  +----------+              +------------+  |                         |
  59    |    |                         |             |                         |
  60    |    |                         | transpile   |                         |
  61    |    |                         v             |                         |
  62    |    |                       +------------+  |          type info      |
  63    |    |                       |  foo.tm.c  | <+-------------------------+
  64    |    |                       +------------+  |
  65    |    |                         |             |
  66    |    |                         | compile     |
  67    |    |                         v             |
  68    |    |          compile      +------------+  |
  69    +----+---------------------> |  foo.tm.o  | -+
  70         |                       +------------+
  71         |          compile        ^
  72         +-------------------------+ 
  73 ```
  74 
  75 These dependency graphs are relatively complicated-looking, but here are some
  76 rough takeaways:
  77 
  78  1) Header files are a dependency for many parts of the process, so it's
  79     good to transpile them as early as possible.
  80  2) Once all the header files are available, 
  81     compiled into their object files in parallel. This is by far the
  82     slowest part of compilation (invoking the C compiler), so it benefits
  83     the most from parallelization.
  84  3) After all object files are compiled, the last step is to link them
  85     all together (fast and simple).
  86 
  87 To sastisfy these requirements as efficiently as possible, the approach taken
  88 below is to first transpile all header files sequentially (this could be
  89 parallelized, but is probably faster than the overhead of forking new
  90 processes), then fork a new process for each dependency to transpile and
  91 compile it to an object file. Then, wait for all child processes to finish and
  92 link the resulting object files together.
  93 
  94 ## Phase 1 (sequential transpilation):
  95 
  96 ```
  97           +--------+       +--------+
  98           | foo.tm |       | baz.tm |
  99           +--------+       +--------+
 100               |              |   | 
 101               +--------------+   |
 102               |                  |
 103               v                  v
 104          +----------+      +----------+
 105          | foo.tm.h |      | baz.tm.h |
 106          +----------+      +----------+
 107 ```
 108 
 109 ## Phase 2 (parallel transpilation/compilation):
 110 
 111 ```
 112  ################################    ################################
 113  #           Process 1          #    #           Process 2          #
 114  #   +--------+   +----------+  #    #  +----------+   +--------+   #
 115  #   | foo.tm |   | foo.tm.h |  #    #  | baz.tm.h |   | baz.tm |   #
 116  #   +--------+   | baz.tm.h |  #    #  +----------+   +--------+   #
 117  #       |        +----+-----+  #    #         |           |        #
 118  #       v             |        #    #         |           v        #
 119  #  +----------+       |        #    #         |      +----------+  #
 120  #  | foo.tm.c |       |        #    #         |      | baz.tm.c |  #
 121  #  +----------+       |        #    #         |      +----------+  #
 122  #       |             |        #    #         |        |           #
 123  #       +------+------+        #    #         +--------+           #
 124  #              |               #    #                  |           #
 125  #              v               #    #                  v           #
 126  #        +----------+          #    #            +----------+      #
 127  #        | foo.tm.o |          #    #            | baz.tm.o |      #
 128  #        +----------+          #    #            +----------+      #
 129  ################################    ################################
 130 ```
 131 
 132 ## Phase 3 (linking a shared object file library):
 133 
 134 ```
 135    +----------+      +----------+
 136    | foo.tm.o |      | baz.tm.o |
 137    +----------+      +----------+
 138         |                 |
 139         +--------+--------+
 140                  |
 141                  v
 142            +-----------+
 143            | libfoo.so |
 144            +-----------+
 145 ```
 146 
 147 ## Phase 3 (linking an executable):
 148 
 149 ```
 150    +----------+      +----------+   +--------+  +--------+
 151    | foo.tm.o |      | baz.tm.o |   | foo.tm |  | baz.tm |
 152    +----------+      +----------+   +--------+  +--------+
 153         |                 |              |          |
 154         +--------+--------+              +----+-----+
 155                  | link                       | Figure out command line args
 156                  v                            v
 157               +-----+    compile   +-------------------------+
 158               | foo |<-------------| main() function for exe |
 159               +-----+              +----------+--------------+
 160                                    | foo.tm.h |
 161                                    +----------+
 162                                    | baz.tm.h |
 163                                    +----------+
 164 ```