The back end upper half originated in the Yale FLINT project[12].
When the front end is done typechecking the code, it is handed over successively to the back end upper and lower halves
src/lib/compiler/back/top/
src/lib/compiler/back/low/
where the first does machine-independent stuff and the second does machine-dependent stuff.
From a control-flow point of view, the core back end upper half module is
src/lib/compiler/back/top/main/backend-tophalf-g.pkg
which schedules the various compiler passes in highly customizable form.
The front end gives us the code in the form of a deep syntax tree, defined in
src/lib/compiler/front/typer-stuff/deep-syntax/deep-syntax.api
The upper half module translates the deep syntax tree into three successive forms, each lower-level than the previous:
The lambdacode format is defined in
src/lib/compiler/back/top/lambdacode/lambdacode-form.api
It is an essentially language-neutral high-level representation, so translation into it from deep syntax requires removing all vestiges of Mythryl-specific source syntax. This translation is done by
src/lib/compiler/back/top/translate/translate-deep-syntax-to-lambdacode.pkg
In particular, this translation requires expanding all pattern-matching constructs into elementary function applications, a subtask handled by
src/lib/compiler/back/top/translate/translate-deep-syntax-pattern-to-lambdacode.pkg
The lambdacode representation is purely transitional; One constructed, it is immediately converted into A-Normal form.
A-Normal format is well documented in the literature.[2] It is a high-level, typed, optimization-oriented format in which the call hierarchy remains explicit. These characteristics make some sorts of optimizations easy (and others correspondingly hard). Our version is defined in
src/lib/compiler/back/top/anormcode/anormcode-form.api
(See the comments in that file for a list of the major transforms performed on A-Normal Form code, and the files implementing them.)
The translation from lambdacode to anormcode form is handled by
src/lib/compiler/back/top/lambdacode/translate-lambdacode-to-anormcode.pkg
While in A-Normal form, a number of optimizations are performed (or can be, per configuration options handed to backend-tophalf-g.pkg). Stefan Monnier’s 2003 PhD Thesis "Principled Compilation and Scavenging" provides a good overview. [3]
When we’ve done what we reasonably can in A-Normal form, we convert the code to FPS, "Fate-Passing Style". This is an untyped format in which code is represented essentially as a series of basic blocks linked by GOTOs, albeit in abstract, machine-independent form. In particular, the explicit function-call hierarchy is discarded, as is the implicit stack, replaced by fates passed as explicit arguments, hence the name.
Our definition of FPS is somewhat diffuse, and split into an externally visible API on the one hand, whose definition centers on
src/lib/compiler/back/top/highcode/highcode-form.api
src/lib/compiler/back/top/highcode/highcode-form.pkg
and a more complex internal package, whose definition centers on
src/lib/compiler/back/top/highcode/highcode-uniq-types.api
src/lib/compiler/back/top/highcode/highcode-uniq-types.pkg
Translation from A-Normal to FPS form is handled by
src/lib/compiler/back/top/nextcode/translate-anormcode-to-nextcode-g.pkg
Once in FPS form, a different set of optimizations become easy, and are applied. (The relative dis/advantages of A-Normal and FPS form are discussed in Stefan Monnier’s above-mentioned PhD thesis.)
See [14] and the comments in
src/lib/compiler/back/top/highcode/highcode-form.api
for discussion of the various FPS compiler passes.