This file contains an overview of the design of the compiler.

See also overall_design.html for an overview of how the different sub-systems (compiler, library, runtime, etc.) fit together.


The main job of the compiler is to translate Mercury into C, although it can also translate (subsets of) Mercury to some other languages: Mercury bytecode (for a planned bytecode interpreter), C#, Java and Erlang.

The top-level of the compiler is in the file mercury_compiler.m. This forwards all of the work to the file mercury_compiler_main.m which is a sub-module of the top_level.m package. The basic design is that compilation is broken into the following stages:

Note that in reality the separation is not quite as simple as that. Although parsing is listed as step 1 and semantic analysis is listed as step 2, the last stage of parsing actually includes some semantic checks. And although optimization is listed as steps 3 and 5, it also occurs in steps 2, 4, and 6. For example, elimination of assignments to dead variables is done in mode analysis; middle-recursion optimization and the use of static constants for ground terms is done during code generation; and a few low-level optimizations are done in llds_out.m as we are spitting out the C code.

In addition, the compiler is actually a multi-targeted compiler with several different back-ends.

mercury_compile.m itself supervises the parsing (step 1), but it subcontracts the supervision of the later steps to other modules. Semantic analysis (step 2) is looked after by mercury_compile_front_end.m; high level transformations (step 3) by mercury_compile_middle_passes.m; and code generation, optimization and output (steps 4, 5 and 6) by mercury_compile_llds_backend.m, mercury_compile_mlds_backend.m and mercury_compile_erl_backend.m for the LLDS, MLDS and Erlang backends respectively.

The modules in the compiler are structured by being grouped into "packages". A "package" is just a meta-module, i.e. a module that contains other modules as sub-modules. (The sub-modules are almost always stored in separate files, which are named only for their final module name.) We have a package for the top-level, a package for each main pass, and finally there are also some packages for library modules that are used by more than one pass.

Taking all this into account, the structure looks like this:

In addition to the packages mentioned above, there are also packages for the build system: make.m contains the support for the `--make' option, and recompilation.m contains the support for the `--smart-recompilation' option.


This section describes the role of each module in the compiler. For more information about the design of a particular module, see the documentation at the start of that module's source code.

The action is co-ordinated from mercury_compile.m or make.m (if `--make' was specified on the command line).

Option handling

Option handling is part of the libs.m package.

The command-line options are defined in the module options.m. mercury_compile.m calls library/getopt_io.m, passing the predicates defined in options.m as arguments, to parse them. It then invokes handle_options.m (and indirectly, op_mode.m and compute_grade.m) to postprocess the option set. The results are represented using the type globals, defined in globals.m. The globals structure is available in the HLDS representation, but it is passed around as a separate argument both before the HLDS is built and after it is no longer needed.

Build system

Support for `--make' is in the make.m package, which contains the following modules:

Categorizes targets passed on the command line and passes them to the appropriate module to be built.
Handles whole program `mmc --make' targets, including executables, libraries and cleanup.
Handles targets built by a compilation action associated with a single module, for example making interface files.
Compute dependencies between targets and between modules.
Record the dependency information for each module between compilations.
Utility predicates.
Read the options files specified by the `--options-file' option. Also used by mercury_compile.m to collect the value of DEFAULT_MCFLAGS, which contains the auto-configured flags passed to the compiler.
The build process also invokes routines in compile_target_code.m, which is part of the backend_libs.m package (see below).


1. Parsing

The parse_tree.m package

The first part of parsing is in the parse_tree.m package, which contains the modules listed below (except for the library/*.m modules, which are in the standard library). This part produces the parse_tree.m data structure, which is intended to match up as closely as possible with the source code, so that it is suitable for tasks such as pretty-printing.

That is all the modules in the parse_tree.m package.

The hlds.m package

Once the stages listed above are complete, we then convert from the parse_tree data structure to a simplified data structure, which no longer attempts to maintain a one-to-one correspondence with the source code. This simplified data structure is called the High Level Data Structure (HLDS), which is defined in the hlds.m package.

The last stage of parsing is this conversion to HLDS, which is done mostly by the following submodules of the make_hlds module in the hlds package.

This submodule calls the others to perform the conversion.
This submodule separates out the different kinds of items, so that when make_hlds_passes.m adds one kind of item (e.g. clauses) to the HLDS, it can rely on the fact that all items of another kind (e.g. predicate declarations) have already been processed.
Performs the conversion of unifications into superhomogeneous form.
Expands away state variable syntax.
Expands away field access syntax.
Converts clauses from parse_tree format to hlds format. Eliminates universal quantification (using `all [Vs] G' ===> `not (some [Vs] (not G))') and implication (using `A => B' ===> `not(A, not B)').
Oversees the conversion of clauses from parse_tree format to hlds format. Handles their addition to procedures, which is nontrivial in the presence of mode-specific clauses.
Handles type and mode declarations for predicates. (Actually in the hlds package because it is called by add_special_pred.m, but does most of its work for the other modules in the make_hlds package.)
If a function has no declared mode, this module adds to it the standard default mode.
Handles the declarations of types.
Handles the declarations of insts and modes, including checking for circular insts and modes.
Adds to the HLDS the casting predicates needed by solver types.
Adds to the HLDS the auxiliary predicates (init, get, set, lock, unlock) needed by mutables.
Handles typeclass and instance declarations.
Handles the abstract data types used for module qualification.
Looks for constructs that merit warnings, such as singleton variables and variables with overlapping scopes.
Error messages used by more than one submodule of make_hlds.m. (Actually, make_hlds_error.m is in the hlds package, because it is needed by some other modules that have been moved from the make_hlds package to hlds.)
Adds foreign procs (Mercury predicates defined using foreign language code) to the HLDS.
Adds foreign enums (Mercury enum types linked to foreign language equivalents) to the HLDS.
Adds everything needed to implement tabling pragmas to the HLDS.
Adds everything needed to implement type specialization pragmas to the HLDS.
Adds the easiest-to-implement kinds of pragmas to the HLDS, i.e. those that don't need their own module.
Fact table pragmas are handled by fact_table.m (which is part of the ll_backend.m package). That module also reads the facts from the declared file and compiles them into a separate C file used by the foreign_proc body of the relevant predicate.

The HLDS data structure itself is spread over the following modules:

  1. hlds_args.m defines the parts of the HLDS concerned with predicate and function argument lists.
  2. hlds_data.m defines the parts of the HLDS concerned with data types, and the representation of values of various types;
  3. hlds_cons.m defines the parts of the HLDS concerned with function symbols.
  4. hlds_inst_mode.m defines the parts of the HLDS concerned with instantiation states and modes.
  5. hlds_class.m defines the parts of the HLDS concerned with type classes and type class constraints.
  6. hlds_goal.m defines the part of the HLDS concerned with the structure of goals, including the annotations on goals.
  7. hlds_clauses.m defines the part of the HLDS concerning clauses.
  8. hlds_rtti.m defines the part of the HLDS concerning RTTI.
  9. const_struct.m defines the part of the HLDS concerning constant structures.
  10. hlds_pred.m defines the part of the HLDS concerning predicates and procedures;
  11. pred_table.m defines the tables that index predicates and functions on various combinations of (qualified and unqualified) names and arity.
  12. hlds_promise.m defines the parts of the HLDS concerned with recording promises made by the programmer about the properties of predicates and functions.
  13. hlds_module.m defines the top-level parts of the HLDS, including the type module_info.
  14. status.m defines the type that record the import/export status of entities such as types, insts, modes, and predicates.
  15. vartypes.m defines the data structure that maps variables to their types.
Some modules implement a pass that decides the representation of every type used by the module being compiled:
Decides how values of discriminated union types are laid out in memory. The two main issues it handles are floats (which can be a problem on platforms where they don't fit in words) and the packing of data structures as densely as possible. Once the representations of all types are known, this module invokes add_special_pred.m to declare, and if need be, define the unify and compare predicate of each type.
Adds unify, compare, and (if the compare predicate needs it) index predicates to the HLDS.

The module hlds_out.m contains predicates to dump the HLDS to a file. These predicates print all the information the compiler has about each part of the HLDS. The module hlds_desc.m, by contrast contains predicates that describe some parts of the HLDS (e.g. goals) with brief strings, suitable for use in progress messages used for debugging.

The module hlds_defns.m contains code to print the set of definitions in the HLDS to a file. When dividing a module into two or more submodules, one can use the information thus generated to check whether the new modules include every type, inst, mode, predicate and function definition in the original module exactly once. (The other sorts of definitions, e.g. typeclass definitions, are typically so few in number that one can keep track of them in one's head.)

The hlds.m package also contains some utility modules that contain various library routines which are used by other modules that manipulate the HLDS:

Marks directly tail recursive calls as such, and marks procedures containing directly tail recursive calls as such.
Utility routines for use during HLDS generation.
Contains predicates for determining whether HLDS goals match various criteria.
Contains various miscellaneous utility predicates for manipulating HLDS goals, such as attaching features to goals.
Contains predicates for creating new HLDS goals.
Contains code to write progress messages, and higher-order code to traverse all the predicates defined in the current module and do something with each one.
Utility routines for printing nicely formatted error messages for symptoms involving HLDS data structures. For symptoms involving only structures defined in prog_data, use parse_tree.error_util.
Utility routines for printing insts and modes in nicely formatted error messages.
Defines a type for classifying determinisms in ways useful to the various backends, and utility predicates on that type.
Utility routines that the various backends use to analyze procedures' argument lists and decide on parameter passing conventions.
Facilities for translating the bodies of predicates to hyperhomogeneous form, for constraint based mode analysis.
Defines the inst_graph data type, which describes the structures of insts for constraint based mode analysis, as well as predicates operating on that type.
Contains types and predicates for operating on from_ground_term scopes and their contents.

2. Semantic analysis and error checking

This is the check_hlds.m package, with support from the mode_robdd.m package for constraint based mode analysis.

Any pass which can report errors or warnings must be part of this stage, so that the compiler does the right thing for options such as `--halt-at-warn' (which turns warnings into errors) and `--error-check-only' (which makes the compiler only compile up to this stage).

implicit quantification
quantification.m handles implicit quantification and computes the set of non-local variables for each sub-goal. It also expands away bi-implication (unlike the expansion of implication and universal quantification, this expansion cannot be done until after quantification). This module is part of the hlds.m package rather than the check_hlds.m package, partly because it is rerun by several passes after semantic analysis to update nonlocal sets after changes to procedure bodies. The first invocation of quantification may be preceded by a pre-quantification pass (in pre_quantification.m), which can insert implicit existential quantifiers into trace goals to implement a scope rule about such goals that people tend to intuitively expect.

checking typeclass instances (check_typeclass.m)
check_typeclass.m both checks that instance declarations satisfy all the appropriate superclass constraints (including functional dependencies) and performs a source-to-source transformation on the methods from the instance declarations. The transformed code is checked for type, mode, uniqueness, purity and determinism correctness by the later passes, which has the effect of checking the correctness of the instance methods themselves (ie. that the instance methods match those expected by the typeclass declaration). During the transformation, pred_ids and proc_ids are assigned to the methods for each instance.

While checking that the superclasses of a class are satisfied by the instance declaration, a set of constraint_proofs are built up for the superclass constraints. These are used by polymorphism.m when generating the base_typeclass_info for the instance.

This module also checks that there are no ambiguous pred/func declarations (that is, it checks that all type variables in constraints are determined by type variables in arguments), checks that there are no cycles in the typeclass hierarchy, and checks that each abstract instance has a corresponding typeclass instance.

check user defined insts for consistency with types
inst_check.m checks that all user defined bound insts are consistent with at least one type in scope (i.e. that the set of function symbols in the bound list for the inst are a subset of the allowed function symbols for at least one type in scope).

The compiler generates a warning if it finds any user defined bound insts that are not consistent with any types in scope.

pretest user defined insts
inst_user.m performs on user defined bound insts the tests whose results the compiler needs, and records the results in the insts themselves. This is faster than having the compiler perform those tests repeatedly each time it needs the results of those tests.
improving the names of head variables
headvar_names.m tries to replace names of the form HeadVar__n with actual names given by the programmer.

For efficiency, this phase not a standalone pass, but is instead invoked by pre_typecheck.m.

type checking

old_type_constraints.m contains an old (2008-2009) attempt by a summer student at a constraint based type analysis algorithm, which covers only a subset of Mercury.

type_constraints.m contains a (start on) another constraint based type analysis algorithm, which is intended to cover all of Mercury.

assertion.m (XXX in the hlds.m package) is the abstract interface to the assertion table. Currently all the compiler does is type check the assertions and record for each predicate that is used in an assertion, which assertion it is used in. The set up of the assertion table occurs in post_typecheck.finish_assertion.

purity analysis
purity.m is responsible for purity checking, as well as defining the purity type and a few public operations on it. It also does some tasks that are logically part of typechecking but which cannot be done until after the main part typechecking is complete. (This is separate from the work done by post_typecheck.m.) purity.m also does two other miscellaneous tasks. The first is the elimination of double negations; that needs to be done after quantification but before mode analysis. The other is converting calls to `private_builtin.unsafe_type_cast/2' into `generic_call(unsafe_cast, ...)' goals.

check_promise.m records each promise in the appropriate table (the assertion table or the promise_ex table), and removes them from further processing as predicates.
implementation-defined literals
implementation_defined_literals.m replaces unifications of the form Var = $name by unifications to string or integer constants.

polymorphism transformation
polymorphism.m handles introduction of type_info arguments for polymorphic predicates and introduction of typeclass_info arguments for typeclass-constrained predicates. This phase needs to come before mode analysis so that mode analysis can properly reorder code involving existential types. (It also needs to come before simplification so that simplify.m's optimization of goals with no output variables doesn't do the wrong thing for goals whose only output is the type_info for an existentially quantified type parameter.)

polymorphism.m subcontracts parts of its job to introduce_exists_casts.m, which sometimes is also invoked from modes.m.

This phase also converts higher-order predicate terms into lambda expressions, and copies the clauses to the proc_infos in preparation for mode analysis.

The polymorphism.m module also exports some utility routines that are used by other modules. These include some routines for generating code to create type_infos, which are used by simplify.m and magic.m when those modules introduce new calls to polymorphic procedures.

When it has finished, polymorphism.m calls clause_to_proc.m to make duplicate copies of the clauses for each different mode of a predicate; all later stages work on procedures, not predicates.

mode analysis

constraint based mode analysis
This was an experimental alternative to the usual mode analysis algorithm. It worked by building a system of boolean constraints about where (parts of) variables can be bound, and then solving those constraints using reduced ordered binary decision diagrams (robdds). It has been abandoned in favor of the propagation based constraint solver, for two main reasons. First, its performance was far too dependent on finding a good ordering of variables for the robdds, and we found no heuristics that could ensure such an ordering. And second, even with the best orderings, the performance left a lot to be desired.

constraint based mode analysis propagation solver
This is a new alternative for the constraint based mode analysis algorithm. It will perform conjunct reordering for mercury programs of a limited syntax (it calls error if it encounters higher order code or a parallel conjunction, or is asked to infer modes).

indexing and determinism analysis

checking of unique modes (unique_modes.m)
unique_modes.m checks that non-backtrackable unique modes were not used in a context which might require backtracking. Note that what unique_modes.m does is quite similar to what modes.m does, and unique_modes calls lots of predicates defined in modes.m to do it.

stratification checking
The module stratify.m implements the `--warn-non-stratification' warning, which is an optional warning that checks for loops through negation.

oisu pragma checking
Check whether the predicates mentioned in any pragmas about order independent state update obey the requirements placed on them by those pragmas.

try goal expansion
try_expand.m expands `try' goals into calls to predicates in the `exception' module instead.

simplification (simplify.m and its submodules)
Simplification finds and exploits opportunities for simplifying the internal form of the program, both to optimize the code and to massage the code into a form the code generator will accept. It also warns the programmer about any constructs that are so simple that they should not have been included in the program in the first place. (That's why this pass needs to be part of semantic analysis: because it can report warnings.)

simplify.m is a package of submodules.

  1. simplify_goal.m handles simplifications that involve the interaction of a goal with its environment, and then invokes one of the goal-type-specific submodules for further processing.
  2. simplify_goal_call.m handles calls (plain, generic and foreign code). Using const_prop.m in the transform_hlds.m package, it attempts to partially evaluate calls to builtin procedures if the inputs are all constants.
  3. simplify_goal_unify.m handles unifications. Amongst other things, it converts complicated unifications into procedure calls.
  4. simplify_goal_conj.m handles conjunctions. It inlines nested conjunctions, eliminates unreachable code, and eliminates assign unification conjuncts (replacing the assigned-to variable with the assigned-from variable in the rest of the conjunction) if this is possible.
  5. simplify_goal_disj.m handles disjunctions (and atomic goals). It eliminates unnecessary disjunction wrappers, and transforms semidet disjunctions into if-then-elses if this possible.
  6. simplify_goal_ite.m handles if-then-elses (and negations). It warns about if-then-elses in which either the then-part or the else-part is unreachable, and about if-then-elses that should be replaced by switches.
  7. simplify_goal_switch.m handles switches. It eliminates switch arms that cannot fail, and switches with no arms left.
  8. simplify_goal_scope.m handles scope goals. It eliminates unnecessary nested scopes, replaces from_ground_term_construct scopes with a single assignment unifications referencing a constant structure in a constant structure database (to eliminate the need for any later passes to traverse the scope), and evaluates compile-time conditions on trace goals, eliminating either the compile-time condition wrapper on the trace goal (if the condition is true) or the trace goal scope altogether (if the condition is false).
  9. common.m looks for (a) construction unifications that construct a term that is the same as one that already exists, or (b) repeated calls to a predicate with the same inputs. It replaces both with assignment unifications. It is invoked by the goal-type-specific submodules above.
  10. format_call.m looks for calls to predicates such as string.format and io.format. It reports calls in which the types of the values to be printed disagree with the format string, and/or calls in which the agreement cannot be established. It also attempts to partially evaluate the correct calls, essentially interpreting the format string at compile time, not runtime.
  11. simplify_proc.m handles the top-level processing of procedures and their bodies.
  12. simplify_info.m defines the data structure that is threaded through the code of the submodules above, containing the information those submodules need.
  13. simplify_tasks.m defines the type that identifies the tasks that the simplification package may be asked to do. Simplification can be invoked at several different points in the compilation process; different invocations need to perform different subsets of the tasks that simplification is capable of.

unused imports (unused_imports.m)
unused_imports.m determines which imports of the module are not required for the module to compile. It also identifies which imports of a module can be moved from the interface to the implementation.

style checks (style_checks.m)
style_checks.m generates warnings if a predicate or function declaration is not followed immediately by all the mode declarations of that predicate or function, and for module bodies in which either the exported or nonexported predicates and functions have one order for their declarations and a different order for their definitions.

xml documentation (xml_documentation.m)
xml_documentation.m outputs a XML representation of all the declarations in the module. This XML representation is designed to be transformed via XSL into more human readable documentation.

3. High-level transformations

This is the transform_hlds.m package.

The first pass of this stage does tabling transformations (table_gen.m). This involves the insertion of several calls to tabling predicates defined in mercury_builtin.m and the addition of some scaffolding structure. Note that this pass can change the evaluation methods of some procedures to eval_table_io, so it should come before any passes that require definitive evaluation methods (e.g. inlining).

The next pass of this stage is a code simplification, namely removal of lambda expressions (lambda.m):

(Is there any good reason why lambda.m comes after table_gen.m?)

The next pass also simplifies the HLDS by expanding out the atomic goals implementing Software Transactional Memory (stm_expand.m).

Expansion of equivalence types (equiv_type_hlds.m)

Exception analysis. (exception_analysis.m)

The next pass is termination analysis. The compiler contains two separate termination analysis systems, which are based on different principles. The modules involved in the first system are:

The modules involved in the second system are:

Trail usage analysis. (trailing_analysis.m)

Minimal model tabling analysis. (tabling_analysis.m)

The results of these program analyses are written out to `.trans_opt' files by intermod.m. intermod.m is also responsible for creating `.opt' files. Besides containing some analysis results, `.opt' files may also contain contains clauses for predicates (exported or local), if these clauses are suitable for other optimizations such as inlining or higher-order specialization.

Most of the remaining HLDS-to-HLDS transformations are optimizations:

The module transform.m contains stuff that is supposed to be useful for high-level optimizations (but which is not yet used).

The last three HLDS-to-HLDS transformations implement term size profiling (size_prof.m and complexity.m) and deep profiling (deep_profiling.m, in the ll_backend.m package). Both passes insert into procedure bodies, among other things, calls to procedures (some of which are impure) that record profiling information.

4. Intermodule analysis framework

This is the analysis.m package.

The framework can be used by a few analyses in the transform_hlds.m package. It is documented in the analysis/README file.


This is the ll_backend.m package.

3a. LLDS-specific HLDS -> HLDS transformations

Before LLDS code generation, there are a few more passes which annotate the HLDS with information used for LLDS code generation, or perform LLDS-specific transformations on the HLDS:
reducing the number of variables that have to be saved across procedure calls (saved_vars.m)
We do this by putting the code that generates the value of a variable just before the use of that variable, duplicating the variable and the code that produces it if necessary, provided the cost of doing so is smaller than the cost of saving and restoring the variable would be.
transforming procedure definitions to reduce the number of variables that need their own stack slots (stack_opt.m)
The main algorithm in stack_opt.m figures out when variable A can be reached from a cell pointed to by variable B, so that storing variable B on the stack obviates the need to store variable A on the stack as well. This algorithm relies on an implementation of the maximal matching algorithm in matching.m.
migration of builtins following branched structures (follow_code.m)
This transformation improves the results of follow_vars.m (see below)
simplification again (simplify.m, in the check_hlds.m package)
We run this pass a second time in case the intervening transformations have created new opportunities for simplification. It needs to be run immediately before code generation, because it enforces some invariants that the LLDS code generator relies on.
annotation of goals with liveness information (liveness.m)
This records the birth and death of each variable in the HLDS goal_info.
allocation of stack slots
This is done by stack_alloc.m, with the assistance of the following modules:
allocating the follow vars (follow_vars.m)
Traverses backwards over the HLDS, annotating some goals with information about what locations variables will be needed in next. This allows us to generate more efficient code by putting variables in the right spot directly. This module is not called from mercury_compile_llds_back_end.m; it is called from store_alloc.m.
allocating the store map (store_alloc.m)
Annotates each branched goal with variable location information so that we can generate correct code by putting variables in the same spot at the end of each branch.
computing goal paths (goal_path.m in the check_hlds.m package)
The goal path of a goal defines its position in the procedure body. This transformation attaches its goal path to every goal, for use by the debugger.

4a. Code generation.

code generation
Code generation converts HLDS into LLDS. For the LLDS back-end, this is also the point at which we insert code to handle debugging and trailing, and to do heap reclamation on failure. The top level code generation module is proc_gen.m, which looks after the generation of code for procedures (including prologues and epilogues). The predicate for generating code for arbitrary goals is in code_gen.m, but that module handles only sequential conjunctions; it calls other modules to handle other kinds of goals:

The code generator also calls middle_rec.m to do middle recursion optimization, which is implemented during code generation.

The code generation modules make use of

The persistent part of the code generator state.
The location-dependent part of the code generator state.
This defines the var_locn type, which is a sub-component of the code_info data structure; it keeps track of the values and locations of variables. It implements eager code generation.
Various utility predicates.
Some miscellaneous preds used for code generation.
Some miscellaneous preds used for lookup switch (and lookup disjunction) generation.
For accurate garbage collection, collects information about each live value after calls, and saves information about procedures.
Inserts calls to the runtime debugger.
trace_params.m (in the libs.m package, since it is considered part of option handling)
Holds the parameter settings controlling the handling of execution tracing.
code generation for `pragma export' declarations (export.m)
This is handled separately from the other parts of code generation. mercury_compile*.m calls `export.produce_header_file' to produce C code fragments which declare/define the C functions which are the interface stubs for procedures exported to C.
generation of constants for RTTI data structures
This could also be considered a part of code generation, but for the LLDS back-end this is currently done as part of the output phase (see below).

The result of code generation is the Low Level Data Structure (llds.m), which may also contains some data structures whose types are defined in rtti.m. The code for each procedure is generated as a tree of code fragments which is then flattened.

5a. Low-level optimization (LLDS).

Most of the various LLDS-to-LLDS optimizations are invoked from optimize.m. They are:

In addition, stdlabel.m performs standardization of labels. This is not an optimization itself, but it allows other optimizations to be evaluated more easily.

The module opt_debug.m contains utility routines used for debugging these LLDS-to-LLDS optimizations.

Several of these optimizations (frameopt and use_local_vars) also use livemap.m, a module that finds the set of locations live at each label.

Use_local_vars numbering also introduces references to temporary variables in extended basic blocks in the LLDS representation of the C code. The transformation to insert the block scopes and declare the temporary variables is performed by wrap_blocks.m.

Depending on which optimization flags are enabled, optimize.m may invoke many of these passes multiple times.

Some of the low-level optimization passes use basic_block.m, which defines predicates for converting sequences of instructions to basic block format and back, as well as opt_util.m, which contains miscellaneous predicates for LLDS-to-LLDS optimization.

6a. Output C code


This is the ml_backend.m package.

The original LLDS code generator generates very low-level code, since the LLDS was designed to map easily to RISC architectures. We have developed a new back-end that generates much higher-level code, suitable for generating Java, high-level C, etc. This back-end uses the Medium Level Data Structure (mlds.m) as its intermediate representation.

3b. pre-passes to annotate/transform the HLDS

Before code generation there is a pass which annotates the HLDS with information used for code generation:

For the MLDS back-end, we have tried to keep the code generator simple. So we prefer to do things as HLDS to HLDS transformations where possible, rather than complicating the HLDS to MLDS code generator. Thus we have a pass which transforms the HLDS to handle trailing:

4b. MLDS code generation

5b. MLDS transformations

6b. MLDS output

There are currently three backends that generate code from MLDS: one generates C/C++ code, one generates Java, and one generates C#. There is also a module, mlds_dump.m, that dumps out the MLDS in format designed specifically for debugging.

The various mlds_to_c_*.m modules together convert MLDS to C/C++ code, the various mlds_to_cs_*.m modules together convert it to C# code, while the various mlds_to_java_*.m modules together convert it to Java code.

Generated C or C# code is intended to be given to a C or C# compiler to turn the .c file into a .o file, or the .cs file into a .dll or .exe. Generated Java code is intended to be given to a Java compiler (normally javac) to turn the .java file into a .class file containing Java bytecodes.

The mlds_to_target_util.m module contains types, functions and predicates that are needed by more than one of these MLDS backends.


This is the bytecode_backend.m package.

The Mercury compiler can translate Mercury programs into bytecode for interpretation by a bytecode interpreter. The intent of this is to achieve faster turn-around time during development. However, the bytecode interpreter has not yet been written.


This is the erl_backend.m package.

The Mercury compiler can translate Mercury programs into Erlang. The intent of this is to take advantage of the features of the Erlang implementation (concurrency, fault tolerance, etc.) However, the backend is still incomplete. This back-end uses the Erlang Data Structure (elds.m) as its intermediate representation.

4d. ELDS code generation

6d. ELDS output


This is the recompilation.m package.

The Mercury compiler can record program dependency information to avoid unnecessary recompilations when an imported module's interface changes in a way which does not invalidate previously compiled code.


The modules special_pred.m (in the hlds.m package) and unify_proc.m (in the check_hlds.m package) contain stuff for handling the special compiler-generated predicates which are generated for each type: unify/2, compare/3, and index/1 (used in the implementation of compare/3).

This module is part of the transform_hlds.m package.

This contains predicates to compute the call graph for a module, and to print it out to a file. (The call graph file is used by the profiler.) The call graph may eventually also be used by det_analysis.m, inlining.m, and other parts of the compiler which could benefit from traversing the predicates in a module in a bottom-up or top-down fashion with respect to the call graph.

The following modules are part of the backend_libs.m package.

This module defines the types unary_op and binary_op which are used by several of the different back-ends: bytecode.m, llds.m, and mlds.m.
This module defines utility routines useful for generating C code. It is used by both llds_out.m and mlds_to_c.m.
This module defines utility routines useful for mangling names to forms acceptable as identifiers in target languages.
Invoke C, C#, Java, etc. compilers and linkers to compile and link the generated code.
This module defines utility routines to do with string encodings.

The following modules are part of the libs.m package.

Predicates to deal with files, such as searching for a file in a list of directories.
Predicates to deal with process creation and signal handling. This module is mainly used by make.m and its sub-modules.
Contains an ADT representing timestamps used by smart recompilation and `mmc --make'.
Graph colouring.
This is used by the LLDS back-end for register allocation
Emulate `int' operations for a given number of bits per int.
Implements the linear programming algorithm for optimizing a set of linear constraints on floats with respect to a linear cost function. This is used by the first termination analyser, whose top level is in termination.m.
Implements the linear programming algorithm for optimizing a set of linear constraints on rational numbers with respect to a linear cost function. This is used by the second, convex-constraint-based termination analyser, whose top level is in term_constr_main.m.
Implements operations on convex polyhedra. This is used by the second, convex-constraint-based termination analyser, whose top level is in term_constr_main.m.
Implements rational numbers.
Generic utility predicates, mainly for error handling.
A representation for mmakefiles and mmakefile fragments, and predicates for printing them.



atsort.m (in the libs.m package)
Approximate topological sort. This was once used for traversing the call graph, but nowadays we use relation.atsort from library/relation.m.