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
1. parsing (source files -> HLDS)
2. semantic analysis and error checking (HLDS -> annotated HLDS)
3. high-level transformations (annotated HLDS -> annotated HLDS)
4. code generation (annotated HLDS -> target representation)
5. low-level optimizations
(target representation -> target representation)
6. output code (target representation -> target code)
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
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:
At the top of the dependency graph is the top_level.m package,
which currently contains only the mercury_compile*.m modules,
which invoke all the different passes in the compiler.
The next level down is all of the different passes of the compiler.
In general, we try to stick by the principle that later passes can
depend on data structures defined in earlier passes, but not vice versa.
1. parsing (source files -> HLDS)
Packages: parse_tree.m and hlds.m
2. semantic analysis and error checking (HLDS -> annotated HLDS)
3. high-level transformations (annotated HLDS -> annotated HLDS)
Packages: transform_hlds.m and analysis.m
a. LLDS back-end
3a. LLDS-back-end-specific HLDS->HLDS transformations
4a. code generation (annotated HLDS -> LLDS)
5a. low-level optimizations (LLDS -> LLDS)
6a. output code (LLDS -> C)
b. MLDS back-end
4b. code generation (annotated HLDS -> MLDS)
5b. MLDS transformations (MLDS -> MLDS)
6b. output code
(MLDS -> C or MLDS -> C# or MLDS -> Java, etc.)
c. bytecode back-end
4c. code generation (annotated HLDS -> bytecode)
d. Erlang back-end
4d. code generation (annotated HLDS -> ELDS)
6d. output code (ELDS -> Erlang)
There is also a package backend_libs.m which contains modules
which are shared between several different back-ends.
Finally, at the bottom of the dependency graph there is the package libs.m.
libs.m contains the option handling code, and also library modules
which are not sufficiently general or sufficiently useful to go
in the Mercury standard library.
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'
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 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.
Support for `--make' is in the make.m package,
which contains the following modules:
The build process also invokes routines in compile_target_code.m,
which is part of the backend_libs.m package (see below).
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.
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 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.
lexical analysis (library/lexer.m)
stage 1 parsing - convert strings to terms.
library/parser.m contains the code to do this, while
library/term.m and library/varset.m contain the term and varset
data structures that result, and predicates for manipulating them.
stage 2 parsing - convert terms to `items' (declarations, clauses, etc.)
The result of this stage is a parse tree
that has a close correspondence with the source code.
The parse tree data structure definition is in prog_data.m,
prog_data_event.m, prog_data_foreign.m, prog_data_pragma.m,
prog_data_used_modules.m, prog_item.m and file_kind.m,
while the code to create it is in the prog_io*.m modules:
prog_io.m handles the top level tasks of reading in
whole Mercury source files.
prog_io_find.m locates source files containing Mercury modules.
prog_io_item.m parses in the top level parts of items,
prog_io_dcg.m parses clauses using Definite Clause Grammar notation.
prog_io_goal.m parses goals.
prog_io_vars.m parses lists of variables.
prog_io_type_name.m parses type names, while
prog_io_inst_mode_name.m parses inst and mode names.
prog_io_type_defn.m parses type definitions, while
prog_io_inst_mode_defn.m parses inst and mode definitions.
prog_io_typeclass.m parses typeclass and instance declarations.
prog_io_pragma.m parses pragma declarations.
prog_io_mutable.m parses initialize, finalize and mutable declarations.
prog_io_sym_name.m parses symbol names and specifiers.
prog_io_error.m defines the types that represents the possible outcomes
of parsing a source file.
prog_io_util.m and prog_io_iom.m define some types and predicates
needed by the other prog_io*.m modules.
There are several modules whose collective job it is
to print (parts of) the parse tree.
The top levels of parse trees are output by parse_tree_out.m.
This module also outputs most kinds of items.
parse_tree_out_clause.m outputs clauses and goals.
parse_tree_out_pragma.m outputs pragmas.
parse_tree_out_pred_decl.m outputs (parts of) predicate, function
and mode declarations.
parse_tree_out_inst.m outputs insts and modes.
parse_tree_out_term.m outputs variables and terms.
parse_tree_out_info.m provides a common infrastructure
for the above modules, and for mercury_to_mercury.m.
The modules prog_out.m and mercury_to_mercury.m output
the lowest level, and smallest, parts of the parse tree.
There are several modules that provide utility predicates
that operate on (parts of) the parse tree.
builtin_lib_types.m contains definitions about types, type constructors
and function symbols that the Mercury implementation needs to know about.
prog_item_stats.m has facilities for gathering and printing statistics
about the parse tree.
prog_util.m contains some utility predicates
for manipulating the parse tree.
prog_detism.m contains utility predicates
for manipulating determinism and determinism components.
prog_mode.m contains utility predicates
for manipulating insts and modes.
prog_type.m contains utility predicates
for manipulating types.
prog_type_subst.m contains predicates
for performing type substitutions.
prog_rename.m contains predicates
for performing variable substitutions.
prog_foreign.m contains utility predicates
for manipulating foreign code.
prog_mutable.m contains utility predicates
for manipulating mutable variables.
prog_event.m contains utility predicates for working with events.
error_util.m contains predicates
for printing nicely formatted error messages.
maybe_error.m contains types that allow the representation
of computations that can either succeed or generate such error messages.
imports are handled at this point (modules.m)
read_module.m has code to read in modules in the form of .m,
.int, .opt etc files.
write_module_interface_files.m has the code to write out
`.int0', `.int', `.int2', and `.int3' files.
split_parse_tree_src.m splits up the parse tree of a source file
into a sequence of raw compilation units, one unit per module
contained in the source file.
comp_unit_interface.m separates the parts of a raw compilation unit
that belong in its .int file from those that don't.
modules.m figures out what interface files to read,
and also does a bunch of other semi-related things.
check_raw_comp_unit.m checks whether a compilation unit
generate_dep_d_files.m generates the information from which
write_deps_file.m writes out Makefile fragments.
module_imports.m contains the module_imports type and its access
get_dependencies.m contains predicates that compute various sorts of
direct dependencies (those caused by imports) between modules.
deps_map.m and module_deps_graph.m contain data structures
for recording indirect dependencies between modules,
and the predicates for creating and using them.
file_names.m does conversions between module names and file names.
It uses java_names.m, which contains predicates for dealing with names
of things in Java.
source_file_map.m contains code to read, write and search
the mapping between module names and file names.
module_cmds.m handles the commands for manipulating interface files of
item_util.m contains some utility predicates dealing with items.
module qualification of types, insts and modes
Adds module qualifiers to all types insts and modes,
checking that a given type, inst or mode exists and that
there is only possible match. This is done here because
it must be done before the `.int' and `.int2' interface files
are written. This also checks whether imports are really needed
in the interface.
module_qual.m does the above by coordinating the work of its four
collects information about what types, insts etc are defined
in which modules.
uses the collected information to module qualify items
and their components.
defines the data structure used by collect_mq_info and qualify_items
to do their job and communicate with each other
handles the errors that arise when an item refers to an entity
(type, or inst, or ...) that is either not defined anywhere,
or is defined in more than once module, and the reference
does not indicate which one is intended.
Notes on module qualification:
all types, typeclasses, insts and modes occurring in pred, func,
type, typeclass and mode declarations are module qualified by
module_qual.m and its submodules.
all types, insts and modes occurring in lambda expressions,
explicit type qualifications, and clause mode annotations
are module qualified in make_hlds.m.
constructors occurring in predicate and function mode declarations
are module qualified during type checking.
predicate and function calls and constructors within goals
are module qualified during mode analysis.
expansion of equivalence types (equiv_type.m)
`with_type` and `with_inst` annotations on predicate
and function type and mode declarations are also expanded.
Expansion of equivalence types is really part of type-checking,
but is done on the item_list rather than on the HLDS because it
turned out to be much easier to implement that way.
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.
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 conversion of the item list to HLDS also involves make_tags.m,
which chooses the data representation for each discriminated union type
by assigning tags to each functor.
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.
Handles the declarations of types.
Handles the declarations of insts and modes,
including checking for circular insts and modes.
Adds unify, compare, and (if needed) index and init predicates
to the HLDS as necessary.
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.
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 enums.
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.
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.
The HLDS data structure itself is spread over the following modules:
hlds_args.m defines the parts of the HLDS concerned with predicate
and function argument lists.
hlds_data.m defines the parts of the HLDS concerned with
function symbols, types, insts, modes and determinisms;
hlds_goal.m defines the part of the HLDS concerned with the
structure of goals, including the annotations on goals.
hlds_clauses.m defines the part of the HLDS concerning clauses.
hlds_rtti.m defines the part of the HLDS concerning RTTI.
const_struct.m defines the part of the HLDS concerning constant structures.
hlds_pred.m defines the part of the HLDS concerning
predicates and procedures;
pred_table.m defines the tables that index predicates and functions
on various combinations of (qualified and unqualified) names and arity.
hlds_module.m defines the top-level parts of the HLDS,
including the type module_info.
status.m defines the type that record the import/export status
of entities such as types, insts, modes, and predicates.
vartypes.m defines the data structure that maps variables to their types.
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
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,
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 (XXX which for some reason is part of the hlds.m
package rather than the check_hlds.m package)
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 pass is called from the `transform' predicate in make_hlds.m.
- 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
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
- 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 the typechecker.
- type checking
typecheck.m handles type checking, overloading resolution &
module name resolution, and almost fully qualifies all predicate
and functor names. It sets the map(var, type) field in the
pred_info. However, typecheck.m doesn't figure out the pred_id
for function calls or calls to overloaded predicates. That can't
be done in a single pass of typechecking, and so it is done
later on (in purity.m for overloaded predicate calls, and in
resolve_unify_functor.m for function calls)
type_assign.m and typecheck_info.m define
the main data structures used by typechecking.
typecheck_errors.m handles outputting of type errors.
typeclasses.m checks typeclass constraints, and
any redundant constraints that are eliminated are recorded (as
constraint_proofs) in the pred_info for future reference.
type_util.m contains utility predicates dealing with types
that are used in a variety of different places within the compiler
post_typecheck.m may also be considered to logically be a part
of typechecking, although it also prepares for mode analysis.
It contains tests for errors such as unbound type and inst variables,
unsatisfied type class constraints, and indistinguishable predicate
or function modes. These tests can't be done in the main type
checking pass, because they depend on type analysis being
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.
check_for_missing_type_defns.m checks for locally defined types
that have an abstract definition but no corresponding
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
- purity analysis
purity.m is responsible for purity checking, as well as
purity type and a few public
operations on it. It also calls post_typecheck.m to
complete the handling of predicate
overloading for cases which typecheck.m is unable to handle,
and to check for unbound type variables.
Elimination of double negation is also done here; that needs to
be done after quantification analysis and before mode analysis.
Calls to `private_builtin.unsafe_type_cast/2' are converted
into `generic_call(unsafe_cast, ...)' goals here.
- 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.)
This phase also
converts higher-order predicate terms into lambda expressions,
and copies the clauses to the proc_infos in preparation for
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 is an experimental alternative to the usual mode analysis algorithm.
It works by building a system of boolean constraints about where
(parts of) variables can be bound, and then solving those constraints.
mode_constraints.m is the module that finds the constraints
and adds them to the constraint store.
mode_ordering.m is the module that uses solutions of the
constraint system to find an ordering for the goals in conjunctions.
mode_constraint_robdd.m is the interface to the modules
that perform constraint solving using reduced ordered binary decision
We have several implementations of solvers using robdds.
Each solver is in a module named mode_robdd.X.m, and they all belong
to the top-level mode_robdd.m.
- 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).
prop_mode_constraints.m is the interface to the old mode_constraints.m.
It builds constraints for an SCC.
build_mode_constraints.m is the module that traverses a predicate
to build constraints for it.
abstract_mode_constraints.m describes data structures for the
ordering_mode_constraints.m solves constraints to determine
the producing and consuming goals for program variables, and
performs conjunct reordering based on the result.
mcsolver.m contains the constraint solver used by
- indexing and determinism analysis
switch_detection.m transforms into switches those disjunctions
in which several disjuncts test the same variable against different
cse_detection.m looks for disjunctions in which each disjunct tests
the same variable against the same function symbols, and hoists any
such unifications out of the disjunction.
If cse_detection.m modifies the code,
it will re-run mode analysis and switch detection.
det_analysis.m annotates each goal with its determinism;
it inserts cuts in the form of "some" goals wherever the determinisms
and delta instantiations of the goals involved make it necessary.
Any errors found during determinism analysis are reported by
det_util.m contains utility predicates used in several modules.
- 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.
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.
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.
simplify_goal_unify.m handles unifications.
Amongst other things, it converts complicated unifications
into procedure calls.
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.
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.
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.
simplify_goal_switch.m handles switches.
It eliminates switch arms that cannot fail, and switches
with no arms left.
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).
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.
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,
simplify_proc.m handles the top-level processing of procedures
and their bodies.
simplify_info.m defines the data structure
that is threaded through the code of the submodules above,
containing the information those submodules need.
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
- 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?)
lambda.m converts lambda expressions into higher-order predicate terms
referring to freshly introduced separate predicates.
This pass needs to come after unique_modes.m to ensure that
the modes we give to the introduced predicates are correct.
It also needs to come after polymorphism.m since polymorphism.m
doesn't handle higher-order predicate constants.
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)
This pass annotates each module with information about whether
the procedures in the module may throw an exception or not.
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:
termination.m is the control module. It sets the argument size and
termination properties of builtin and compiler generated procedures,
invokes term_pass1.m and term_pass2.m
and writes .trans_opt files and error messages as appropriate.
term_pass1.m analyzes the argument size properties
of user-defined procedures,
term_pass2.m analyzes the termination properties
of user-defined procedures.
term_traversal.m contains code common to the two passes.
term_errors.m defines the various kinds of termination errors
and prints the messages appropriate for each.
term_util.m defines the main types used in termination analysis
and contains utility predicates.
post_term_analysis.m contains error checking routines and optimizations
that depend upon the information obtained by termination analysis.
term_constr_main.m is the control module; it invokes the others as needed.
term_constr_initial.m sets up the initial state of the analysis,
based on things such as user-provided annotations.
term_constr_build.m builds an abstract representation
of the procedures to be analyzed.
term_constr_fixpoint.m uses that abstract representation
to derive information about the relationships
among the sizes of the arguments of each analyzed procedure.
term_constr_pass2.m uses this information about argument size relationships
to attempt to prove whether the analyzed procedures terminate.
term_constr_main_types.m defines the types that represent the result
of the analysis.
term_constr_data.m defines types needed during the analysis.
term_constr_errors.m generates error messages for termination problems.
Trail usage analysis. (trailing_analysis.m)
This pass annotates each module with information about whether
the procedures in the module modify the trail or not. This
information can be used to avoid redundant trailing operations.
Minimal model tabling analysis. (tabling_analysis.m)
This pass annotates each goal in a module with information about
whether the goal calls procedures that are evaluated using
minimal model tabling. This information can be used to reduce
the overhead of minimal model tabling.
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.
a. LLDS BACK-END
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:
live_vars.m works out which variables need
to be saved on the stack when.
graph_colour.m (in the libs.m package) contains the algorithm
that stack_alloc.m calls to convert sets of variables
that must be saved on the stack at the same time
to an assignment of a stack slot to each such variable.
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
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:
call_gen.m (predicate calls and also calls to out-of-line
par_conj_gen.m (parallel conjunctions)
switch_gen.m (switches), which has sub-modules
switch_util.m -- this is in the backend_libs.m
package, since it is also used by MLDS back-end
pragma_c_gen.m (embedded C code)
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.
In addition, stdlabel.m performs standardization of labels.
This is not an optimization itself,
but it allows other optimizations to be evaluated more easily.
optimization of jumps to jumps (jumpopt.m)
elimination of duplicate code sequences within procedures (dupelim.m)
elimination of duplicate procedure bodies (dupproc.m,
invoked directly from mercury_compile_llds_back_end.m)
optimization of stack frame allocation/deallocation (frameopt.m)
filling branch delay slots (delay_slot.m)
dead code and dead label removal (labelopt.m)
peephole optimization (peephole.m)
introduction of local C variables (use_local_vars.m)
removal of redundant assignments, i.e. assignments that assign a value
that the target location already holds (reassign.m)
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
b. MLDS BACK-END
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
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:
mark_static_terms.m (in the hlds.m package) marks
construction unifications which can be implemented using static constants
rather than heap allocation.
For the MLDS back-end, we've 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:
add_trail_ops.m inserts code to manipulate the trail,
in particular ensuring that we apply the appropriate
trail operations before each choice point, when execution
resumes after backtracking, and whenever we do a commit.
The trail operations are represented as (and implemented as)
calls to impure procedures defined in library/private_builtin.m.
add_heap_ops.m is very similar to add_trail_ops.m;
it inserts code to do heap reclamation on backtracking.
4b. MLDS code generation
ml_proc_gen.m is the top module of the package that converts HLDS code
to MLDS. Its main submodule is ml_code_gen.m, which handles the tasks
common to all kinds of goals, as well as the tasks specific to some
goals (conjunctions, if-then-elses, negations). For other kinds of goals,
ml_code_gen.m invokes some other submodules:
The main data structure used by the MLDS code generator is defined
in ml_gen_info.m, while global data structures (those created at
module scope) are handled in ml_global_data.m.
The module ml_accurate_gc.m handles provisions for accurate garbage
collection, while the modules ml_code_util.m, ml_target_util.m and
ml_util.m provide some general utility routines.
ml_switch_gen.m, which calls upon:
switch_util.m (in the backend_libs.m package,
since it is also used by LLDS back-end)
ml_type_gen.m converts HLDS types to MLDS.
type_ctor_info.m and base_typeclass_info.m generate
the RTTI data structures defined in rtti.m and pseudo_type_info.m
(those four modules are in the backend_libs.m package, since they
are shared with the LLDS back-end)
and then rtti_to_mlds.m converts these to MLDS.
5b. MLDS transformations
ml_tailcall.m annotates the MLDS with information about tailcalls.
It also has a pass to implement the `--warn-non-tail-recursion' option.
ml_optimize.m does MLDS->MLDS optimizations
ml_elim_nested.m does two MLDS transformations that happen
to have a lot in common: (1) eliminating nested functions
and (2) adding code to handle accurate garbage collection.
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#.
mlds_to_c.m converts MLDS to C/C++ code.
The MLDS->Java backend is broken into two submodules.
After the Java code has been emitted, a Java compiler (normally javac)
is invoked to turn the .java file into a .class file containing Java bytecodes.
- mlds_to_java.m converts MLDS to Java and writes it to a .java file.
After the C# code has been emitted, a C# compiler is invoked to turn the .cs
file into a .dll or .exe.
- mlds_to_cs.m converts MLDS to C# code.
c. BYTECODE BACK-END
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.
bytecode.m defines the internal representation of bytecodes, and contains
the predicates to emit them in two forms. The raw bytecode form is emitted
into <filename>.bytecode for interpretation, while a human-readable
form is emitted into <filename>.bytedebug for visual inspection.
bytecode_gen.m contains the predicates that translate HLDS into bytecode.
bytecode_data.m contains the predicates that translate ints, strings
and floats into bytecode.
d. ERLANG BACK-END
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
4d. ELDS code generation
erl_code_gen.m converts HLDS code to ELDS.
The following sub-modules are used to handle different constructs:
The module erl_code_util.m provides utility routines
for ELDS code generation.
erl_rtti.m converts RTTI data structures defined in rtti.m into
ELDS functions which return the same information when called.
6d. ELDS output
elds_to_erlang.m converts ELDS to Erlang code.
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
recompilation.m contains types used by the other smart
recompilation_version.m generates version numbers for program items
in interface files.
recompilation_usage.m works out which program items were used
during a compilation.
recompilation_check.m is called before recompiling a module.
It uses the information written by recompilation_version.m and
recompilation_usage.m to work out whether the recompilation is
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 utility routines to do with argument
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'.
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
whose top level is in term_constr_main.m.
Implements operations on convex polyhedra.
This is used by the second, convex-constraint-based
whose top level is in term_constr_main.m.
Implements rational numbers.
Generic utility predicates, mainly for error handling.
- 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.