wiki:Commentary/Pipeline

Version 3 (modified by duncan, 8 years ago) (diff)

fix missing }} baces

[ Up: Commentary ]

The compilation pipeline

When GHC compiles a module, it calls other programs, and generates a series of intermediate files. Here's a summary of the process.

We start with Foo.hs or Foo.lhs, the "l" specifing whether literate style is being used.

  • Run CPP (if -fcpp is specified), generating Foo.cpp or Foo.lpp respectively.
  • Run the unlit pre-processor, unlit, to remove the literate markup, generating ???. The unlit processor is a C program kept in utils/unlit.
  • Run the compiler itself. This does not start a separate process; it's just a call to a Haskell function. This step always generates an interface file Foo.hi, and depending on what flags you give, it also generates a compiled file:
    • Assembly code: flag -S, file Foo.s
    • C code: flag -fviaC, file Foo.hc
  • Run the C compiler or assembler, as appropriate, generating Foo.o

Interface files

An interface file supports separate compilation by recording the information gained by compiling M.hs in its interface file M.hi. Morally speaking, the interface file M.hi is part of the object file M.o; it's like a super symbol-table for M.o.

Interface files are kept in binary, GHC-specific format. The format of these files changes with each GHC release, but not with patch-level releases. You can see what's in an interface file (often very useful) thus:

  ghc --show-iface M.hi

Here are some of the things stored in an interface file M.hi

  • A list of what M exports.
  • The types of exported functions, definition of exported types, and so on.
  • Version information, used to drive the smart recompilation checker.
  • The strictness, arity, and unfolding of exported functions. This is crucial for cross-module optimisation; but it is only included when you compile with -O.

HC files

GHC uses gcc as a code generator, in a very stylised way:

  • Generate Foo.hc
  • Compile it with gcc, using register declarations to nail a bunch of things into registers (e.g. the allocation pointer)
  • Post-process the generated assembler code with the Evil Mangler

The Evil Mangler

The Evil Mangler (EM) is a Perl script invoked by the Glorious Driver after the C compiler (gcc) has translated the GHC-produced C code into assembly. Consequently, it is only of interest if -fvia-C is in effect (either explicitly or implicitly).

The EM reads the assembly produced by gcc and re-arranges code blocks as well as nukes instructions that it considers non-essential. It derives it evilness from its utterly ad hoc, machine, compiler, and whatnot dependent design and implementation. More precisely, the EM performs the following tasks:

  • The code executed when a closure is entered is moved adjacent to that closure's infotable. Moreover, the order of the info table entries is reversed. Also, SRT pointers are removed from closures that don't need them (non-FUN, RET and THUNK ones).
  • Function prologue and epilogue code is removed. (GHC generated code manages its own stack and uses the system stack only for return addresses and during calls to C code.)
  • Certain code patterns are replaced by simpler code (eg, loads of fast entry points followed by indirect jumps are replaced by direct jumps to the fast entry point).

Implementation of the Evil Mangler

The EM is located in the Perl script driver/mangler/ghc-asm.lprl. The script reads the .s file and chops it up into chunks (that's how they are actually called in the script) that roughly correspond to basic blocks. Each chunk is annotated with an educated guess about what kind of code it contains (e.g., infotable, fast entry point, slow entry point, etc.). The annotations also contain the symbol introducing the chunk of assembly and whether that chunk has already been processed or not.

The parsing of the input into chunks as well as recognising assembly instructions that are to be removed or altered is based on a large number of Perl regular expressions sprinkled over the whole code. These expressions are rather fragile as they heavily rely on the structure of the generated code - in fact, they even rely on the right amount of white space and thus on the formatting of the assembly.

Afterwards, the chunks are reordered, some of them purged, and some stripped of some useless instructions. Moreover, some instructions are manipulated (eg, loads of fast entry points followed by indirect jumps are replaced by direct jumps to the fast entry point).

The EM knows which part of the code belongs to function prologues and epilogues as STG C adds tags of the form --- BEGIN --- and --- END --- the assembler just before and after the code proper of a function starts. It adds these tags using gcc's __asm__ feature.

Update: Gcc 2.96 upwards performs more aggressive basic block re-ordering and dead code elimination. This seems to make the whole --- END --- tag business redundant -- in fact, if proper code is generated, no --- END --- tags survive gcc optimiser.