17. Multiple Translation Units#

A translation unit is a set of source files translated as a unit, comprising a primary source file and all of the source files included by that file. Sometimes, the front end has to deal with more than one translation unit at a time:

When exported templates are used, the source file in which a template is defined may be different than the one in which is it used. The front end has to read in a translation unit for the defining source file while retaining the translation unit for the referencing source file, and then perform the instantiation in a merged context that includes both translation units. Additional translation units may be read in for instantiations of other templates.
When COMPILE_MULTIPLE_TRANSLATION_UNITS is TRUE, multiple files can be specified on the command line for the front end. Each file is read in turn as the primary file of a translation unit.

In both these cases, the first translation unit read is called the primary translation unit, and any translation units read after the first are called secondary translation units. The translation units are kept separate within the front end. They have separate intermediate language (IL) trees and conceptually separate symbol tables. After all translation units have been processed, the IL for each secondary translation unit is merged into the IL for the primary translation unit. Duplicate copies of entities that appear in more than one translation unit are eliminated during the merge, and errors are issued for conflicts between entities that have incompatible definitions in different translation units. The final merged primary IL tree is then passed to a back end, looking much like an IL tree from a simple one-translation-unit compilation.

The process of translating a primary translation unit and zero or more secondary translation units into an IL tree is called a compilation.

Note that when COMPILE_MULTIPLE_SOURCE_FILES [1] is TRUE and the front end is given several source file names on the command line, each translation unit is treated as a separate compilation. It is read separately and its IL tree is written to a separate IL file. No merging is done on the translation unit IL trees, and no checking for matching between translation units. There are no secondary translation units in this mode (except those that might be brought in for exported templates).

The principal source files of the front end involved in multiple-translation-unit processing are trans_unit.c, trans_unit.h, trans_corresp.c, trans_corresp.h, trans_copy.c, and trans_copy.h.

17.1. Initialization, Termination, and Keeping Translation Units Separate#

By and large, the code in the front end is written as if there is only one translation unit. Global variables and tables indicate the state at the current point in the input, which is a particular point within a single translation unit. For the handling of multiple translation units, this global state must be carefully managed, and updated when one switches between translation units.

The process of initialization in the front end is broken down into three parts:

Initialization that is done only once in the entire front end invocation. Initialization routines in this class have names that have the suffix “_one_time_init”.
Initialization that is redone for each compilation. Initialization routines in this class have names that have the suffix “_init”.
Initialization that is redone for each translation unit. Initialization routines in this class have names that have the suffix “_trans_unit_init”.

It can be seen that in COMPILE_MULTIPLE_TRANSLATION_UNITS mode, the front end does one-time initialization, compilation initialization, and then, for each source file specified on the command line, translation unit initialization. In COMPILE_MULTIPLE_SOURCE_FILES mode, on the other hand, the front end does one-time initialization and then, for each source file specified on the command line, compilation initialization and then translation-unit initialization. See the top-level routines in fe_init.c.

Similarly, termination is done in several parts:

pop_scope for the file scope does necessary processing at the end of the file scope for a translation unit.
translation_unit_wrapup does necessary processing at the end of a translation unit.
fe_wrapup does necessary processing at the end of a compilation. This includes calling template_and_inline_function_wrapup, which does most template instantiation.
wrap_up_file_scopes finishes up each translation unit and merges the IL.

The instantiation process (during the third step above) can bring in additional secondary translation units for exported templates, which go through their own initialization, reading/parsing, and termination phases. Eventually, all necessary templates have been instantiated, which means all necessary translation units have been created and processed, and wrap_up_file_scopes is called.

The source code for a secondary translation unit is read, and the corresponding IL is generated, all at one time. There is no switching between translation units while the source code is being read. Once a secondary translation unit has been read, additional processing may be done in that translation unit that will add more IL to it, but that is done through template instantiations, and never by going back and reading more source code. Likewise, instantiations can add additional IL to the primary translation unit, but no additional source code will be read into it.

A structure of type a_translation_unit contains information about a single translation unit within a compilation, and the global variable curr_translation_unit points to the entry for the translation unit that is currently active. By calling switch_translation_unit, one can switch to a different translation unit, i.e., make another translation unit the “active” one. This is a relatively expensive process that changes the values of many global variables to match the new translation unit.

How does switch_translation_unit know what to update? It updates the variables recorded by calling register_trans_unit_variable during one-time initialization. Variables registered in that way are known as trans unit variables, and their per-translation-unit values are recorded in a data structure associated with the a_translation_unit structure: They are saved when the translation unit becomes inactive, and restored when the translation unit is reactivated. Certain values that need to be accessed efficiently even when the corresponding translation unit is not the active one are stored directly in the a_translation_unit structure (e.g., file_scope_pointers_block), or are pointed to by fields in that structure (e.g., module_id_ptr; variables of this kind are registered via register_trans_unit_variable_with_field).

process_translation_unit is the driver for the reading/parsing of a single translation unit.

Some data structures and numbering sequences are deliberately shared across multiple translation units. The source file data structure and source line sequence numbers, for example, are shared, so that a source position consisting of a sequence number and column number is unique across the entire compilation. Likewise, the symbol table and scope number sequence is shared, which ensures that scopes always have unique numbers, and therefore that one can do a lookup in the symbol table by scope number and find only entities from a single scope from a single translation unit.

17.2. Memory Regions and Intermediate Language#

Each secondary translation unit has its own set of IL memory regions, one for its file scope and one for each top-level function definition. The global variable file_scope_region_number indicates the region number of the file scope of the current translation unit, whether it is a primary or secondary translation unit.

The function alloc_primary_file_scope_il allocates space in the primary translation unit IL even if the current translation unit is a secondary translation unit.

The macro is_secondary_trans_unit returns true for an IL entry allocated in a memory region that is part of a secondary translation unit. The global array trans_unit_for_scope maps a scope number back to a pointer to the translation unit that contains that scope. Note that when IL is moved from secondary translation units to the primary IL at the end of the compilation, the value of is_secondary_trans_unit will change, but that of trans_unit_for_scope stays as it was.

The front end memory region is shared across all translation units.

17.3. Translation Unit Correspondences#

Each IL entry with external linkage is assigned to a correspondence set containing all of the related IL entries from different translation units, i.e., all the entries that represent the same entity. So, for example, all external global variables called “i” will be in one correspondence set.

A correspondence set is represented by an entry of type a_trans_unit_corresp, which is allocated in front end memory (so it is not really part of the IL). Each entry that is a member of the correspondence set points to the appropriate a_trans_unit_corresp entry via the trans_unit_corresp pointer in its source_corresp field. These pointers are set when secondary translation units are processed, and therefore in a compilation consisting only of a single translation unit the pointers will be NULL and the correspondence-set entries will not be allocated. [2] For entries without linkage, or with internal linkage, the trans_unit_corresp pointer is always NULL.

IL entries of type a_base_class are also matched up in correspondence sets and therefore contain a trans_unit_corresp pointer (though it is not part of a source_corresp field in that case).

17.4. Canonical Entries#

In each correspondence set, one entry is chosen as the canonical entry, and the canonical field in the a_trans_unit_corresp points to it. The entry chosen as the canonical entry is an instance that contains the most detailed information available about the entity: one with a definition if a definition is available, and a specialization if both specialized and unspecialized versions of a template instance are available. All other things being e qual, an entry in the primary IL is chosen over one in a secondary translation unit, because that means less copying later.

The canonical entry chosen can change as the compilation progresses. The first instance seen will generally be chosen as the canonical entry, but it may be replaced afterwards by a better choice from some other secondary translation unit scanned later.

Note that it is possible for a class or namespace not to be the canonical entry in its correspondence set while at the same time some of its members are the canonical entries in their sets.

The macro canonical_il_entry_of can be used to fetch the address of the canonical entry corresponding to a given entry. For an entry without linkage, the entry itself is returned.

17.5. The Copy Address Pointer#

All IL entries have a prefix that contains various flags and numbers. IL entries in the file scope of a secondary translation unit have, in addition, a copy address pointer, which is set during the copy process to indicate the address in the primary IL to which the entry should be copied or remapped.

For entries in correspondence sets, generally the canonical entry will be copied to the primary IL and its copy address pointer will be set to the address of the copy. The other members of the correspondence set will not be copied, but their copy address pointers will be set to the same copy address so that references to them can be remapped to the unique copy in the primary IL.

For entries not in correspondence sets, including non-declarative entries like statement and expression nodes, no copy address is pre-assigned. When the entry is encountered during the copy process, it is copied to the primary IL and the copy address pointer is set to the address of the copy. All references to the entry encountered thereafter are remapped to the established copy address.

In some cases, entries in the secondary IL are “merged” into the primary IL. This is necessary, for example, if the canonical entry for a correspondence set is in a secondary translation unit but there is also a member of that correspondence set in the primary IL. The address in the primary IL must be preserved (because there are references to it from elsewhere in the primary IL, which will not be rewritten), so the canonical entity must be copied on top of the existing primary IL entry. In such cases, the copy address pointer is used to form a two-element list: The copy address pointer of the entry in the secondary translation unit points to allocated space for a copy (also in the secondary translation unit IL), and the copy address pointer of that copy entry points in turn to the address of the existing entry in the primary IL. The copy process copies the original entry to the intermediate copy, with pointer remapping, and then later overwrites the primary IL entry, carefully preserving certain information (e.g., next-on-list pointers).

The macro trans_unit_copy_address_of gives access to the correspondence pointer of an IL entry (for both fetching and setting). The macro checked_trans_unit_copy_address_of does the same thing, but also checks that the entry pointer provided is actually in the file scope of a secondary translation unit.

17.6. Correspondence Checking#

The code in trans_corresp.c establishes correspondences between entities in a secondary translation unit and similar entities in the primary translation unit and in other secondary translation units. It sets the correspondence pointer of IL entries to indicate the correspondences found. While establishing these correspondences, it checks that linked entities are in fact compatible, and issues errors when they are not. The entities that have correspondences set in this way are types, routines, variables, fields, namespaces, base classes (i.e., a_base_class entries), using-declarations appearing in class scopes, and templates (including template instances).

Correspondence checking can occur in three stages of the compilation:

Built-in types have their correspondences set by record_builtin_type as soon as they are created.
When a translation unit has been processed, set_trans_unit_correspondences is called from translation_unit_wrapup to establish correspondences for the entities that were created in that translation unit. The global variable correspondence_checking_underway is TRUE during this stage (and only during this stage); after that correspondence_checking_done is TRUE.
The correspondence checking process is notified of every template instantiation by calls to record_instantiation. When this occurs in a translation unit after its translation_unit_wrapup call, the correspondence pointer is established for the new instantiation. The instantiation process also notifies the correspondence checking process of template instantiations being completed, through calls to establish_class_instantiation_corresp, establish_function_instantiation_corresp, establish_variable_instantiation_corresp, establish_block_extern_function_correspondence, establish_block_extern_variable_correspondence and establish_friend_type_correspondence.

17.6.1. Finding Corresponding Pairs#

Several different mechanisms are used to find an entity in another translation unit that corresponds to a given entity:

For named entities in namespace scope, the symbol table is used. The search process simply traverses the list of symbols attached to the symbol header of the entity for which a correspondence is being searched. This is done in functions with the prefix find_ (e.g., find_type_correspondence).
For class members, we can rely on the fact that the lists of IL entities representing the members should have their elements correspond on a one-to-one basis. Hence no search is needed, although care must be taken with compiler-generated members that may not appear in every translation unit. This principle is implemented by establish_trans_unit_correspondences_for_class. A similar process can be used for enumeration constants.
Correspondences for instantiations of templates are usually established after the templates from which they are generated have been matched up. To support the search for a matching instantiation, a field all_instantiations was added to a_template_symbol_supplement. This field is set only in the supplement for the canonical template entry and points to a list of all the instantiation symbols for the template, including those for corresponding templates in other translation units. Some of the key functions manipulating this list are add_instantiation, find_class_template_instantiation and find_function_template_instantiation.
Correspondences are also sometimes established between unnamed types. This happens when matching up declarations of entities with linkage involving unnamed types. For example:
```
struct { float a, b; } *p, q; // Could appear in two translation units
```
In such cases, the correspondence is first established for the entities with linkage (variables or routines), and the correspondence between the types is sought by comparing the two types using f_types_are_compatible with the option TCF_SEEK_CORRESP.

17.6.2. Ordering Dependencies#

Determining whether two entities from different translation units correspond may require that other correspondences are known. For example, suppose we have two namespace scope functions f that are declared as

extern R N::f();

then the two must correspond if the entities denoted by N correspond, and if that is the case the entities denoted by R must correspond too. The ordering of corresponding checks must therefore be managed carefully.

To reduce the magnitude of this issue, correspondences are determined in two steps. In the first step, correspondences are established: Only those components of the entity that uniquely identify it are compared (e.g., the entity’s name, its enclosing classes and namespaces, parameter types of functions, etc.) and if they match the correspondence pointer is set. Some diagnostics may be issued at this time. This process is mostly done in functions with the prefix establish_. In the second step, which starts after all the correspondences for the translation unit have been established, the correspondences are verified. This involves comparing the remaining relevant attributes of entities that were found to correspond after the first step; diagnostics are issued if the entities do not match. Most of the verification work is done in functions with the prefix verify_. This separation into two steps makes sure that in our example above the correspondence for R has been established by the time it is needed.

To deal with other ordering issues, such as the requirement that the correspondence of N be established in our example, the correspondence checking process may be stacked. For example, while searching for a correspondence for N::f above, another search for a correspondence for N may be initiated. This is driven by calls to functions named canonical_entity_entry_of where entity is one of namespace, type, field, routine, variable or template. If a correspondence was already established, these functions return the requested canonical entry; if not, they first determine the correspondence by calling determine_correspondence [3].

Other ordering issues sometimes arise because establishing a correspondence for a template instantiation seemingly leads to infinite recursion. Such situations are resolved in part by placing appropriate markers in the all_instantiations list and in part by as much as possible establishing the correspondences of all templates before attempting to match their instantiations. To that end, the front end maintains a list of instantiations whose correspondences are yet to be determined (the list is pointed to by instantiations_to_process). That list is processed at appropriate times (i.e., when the correspondences of the various templates have been found) by calls to process_pending_instantiations.

Finally, we should note that the verification process always compares an entity with its canonical counterpart. If a canonical entry (from an already processed translation unit) is replaced by a new entry (from the current translation unit) the former will need to be compared with the latter when all the correspondences have been established in the current translation unit. This is done in process_verification_list.

17.6.3. Debugging Facilities#

When the preprocessor symbol DEBUG is TRUE,a few facilities are provided by trans_corresp.c to help identify problems during correspondence checking. First, the command-line option “-d-trans_corresp” will cause a line of output to be produced for each correspondence pointer being set (or cleared), as well as for certain operations on the all_instantiations lists. Second, the function db_corresp can be called from a debugger to examine the correspondence of a given entity. Finally, the modification of a correspondence pointer for a specific entity can easily be intercepted in a debug environment where addresses are reproducible from run to run. To enable this, set breakpoints on main and on corresp_intercept. Rerun the front end and at the stop in main, set the static variable trace_corresp_ptr to the address of the entity whose correspondence value should be tracked: corresp_intercept will be called (triggering the breakpoint) when that value is modified.

17.7. Copying from Secondary Translation Units#

The code in trans_copy.c copies IL from a secondary translation unit to the primary translation unit IL. It is run after elimination of unneeded entries in the secondary translation unit, so it copies only entries that are actually “needed.” It also runs after correspondence checking has established the correspondences between externally-linked entities, so it does not copy entries for which there is already an instance in the primary translation unit IL; for such cases, all references to the entity are simply rewritten to point to the primary IL instance.

The secondary translation unit IL consists of a file scope memory region and zero or more function scope memory regions. The file scope memory region is actually copied into the primary IL, via a tree walk, with duplicates eliminated as indicated above. The function scope memory regions, on the other hand, are not copied. Instead, they are walked to update pointers appropriately, and then the memory region numbers are simply reassigned to the primary IL.

The copy process is handled by copy_secondary_trans_unit_IL_to_primary, which has five main phases:

prepare_for_trans_unit_copy walks through the declaration lists of the file scope of a secondary translation unit and its subscopes, and puts each entry into one of four categories: (a) entries that should be copied to the primary IL; (b) entries that should overwrite a corresponding entry in the primary IL (e.g., a function in the secondary translation unit that has a definition, where the corresponding function in the primary IL has only a declaration); (c) entries that are in a correspondence set but are not the canonical entry, which should be removed from the lists and discarded; and (d) entries in a correspondence set that provide additional (minor) information over what is present in the canonical entry, which should be merged into the corresponding entry.
copy_from_secondary_to_primary_IL uses the IL-walking routines to walk the IL tree, copy over entries that need to be copied, and update pointers so that the copied IL refers only to copies or to pre-existing entries in the primary IL.
copy_function_bodies_to_primary_IL processes the bodies of any functions that are to be moved over, by using the IL-walking routines to walk the IL tree and update pointers appropriately.
finish_trans_unit_copy walks through the declaration lists again, and links copied entries into the declaration lists of the primary IL. A struct type copied over, for example, would be linked into the types list of the primary scope of the primary IL. Variables, types, and routines that must be merged into the corresponding entries are also copied onto the corresponding entries at this point. This part of the processing runs while switched into the primary translation unit. See also finish_moved_entity_processing, which is similar but reaches all copied or merged entities, even those from non-merged scopes.
finish_processing_for_function_bodies calls finish_function_body_processing for each copied function scope memory region, and kicks off IL lowering for the function if it’s needed. This part of the processing runs while switched into the primary translation unit.

For entries that are being merged into the primary IL, the copy process sets the il_lowering flag in the IL entry prefix to indicate merging rather than copying. (The flag is available for this use because IL lowering is never done on secondary translation units.) For merged entries, the copy process uses an extra copy of the entity allocated in the secondary translation unit: The entity’s copy address pointer points to the copy, whose copy address pointer points to the corresponding entity in the primary IL. During the copy, the original entry is copied to the copy space, and its pointers are remapped there. This allows finish_trans_unit_copy later to have access to both the original entity in the primary IL and the entity from the secondary translation unit as updated for the copy. This is often important because some flags from the two entries need to be merged.

The bodies of functions not copied over are eliminated, and likewise for the initializers of variables. See clear_body_for_routine and clear_variable_definition. Non-template functions and variables in secondary translation units included only to get exported templates are turned into external declarations, because the definition of those entities is put out when the file is compiled as a primary translation unit.

The IL for secondary translation units can contain references to other translation units. In some ways, the IL trees for all secondary translation units have to be viewed as one big somewhat interconnected tree. For this reason, each of the processing phases described above is done for all secondary translation units before advancing to the next phase.

Part of the function of the copy process is to produce a primary IL tree that contains no references to IL entries in secondary translation units, and this is done by making sure that every entity copied over has only pointers that refer to the primary IL. Sometimes, however, the instantiation of a template that is defined in the primary translation unit introduces exactly the kind of mixed-translation-unit IL that we are trying to avoid. To eliminate such references, a pair of routines in trans_copy.c is called:

mark_secondary_trans_unit_IL_entities_used_from_primary_as_needed sweeps the primary translation unit IL and looks for references to secondary translation unit entries. When it finds them, it marks the secondary translation unit entries as needed so that they will be copied to the primary IL when the secondary translation unit is copied.
rewrite_secondary_trans_unit_IL_entity_pointers_used_in_primary sweeps the primary translation unit IL after the secondary translation units have been copied in, and looks for references to secondary translation unit entries. When it finds them, it rewrites them either as references to the corresponding entity in the primary translation unit (if there is one) or it copies them and rewrites the pointer to the copy.

In some (relatively rare) cases, the merged IL produced by the copy process has some type entries out of order on the type lists, where “out of order” is defined according to the peculiar ordering required by the C-generating back end so that it can generate compilable C code. fix_type_list_ordering_problems is called after IL lowering to examine the file-scope types list to look for ordering problems and to move types to fix those problems. If there are no ordering problems (which is almost always the case), the checking is done fairly quickly and efficiently.

17.8. Externalization of statics#

When a source file includes exported templates, it is possible that the exported templates will refer to static entities in the file. Because the template instances may be generated as part of the translation of other source files, and be included in the object code for those files, it may be necessary to refer to the static entities from another compilation. Therefore, the front end externalizes all statics when a compilation includes exported templates. This gives the static functions and variables external linkage and special mangled names. This has a number of consequences, such as that static inline functions become extern inline functions, which in some configurations makes them instantiatable. See externalize_statics_for_exported_templates.

17.9. One-instantiation-per-object mode#

In one-instantiation-per-object mode, each instantiated template is put into a separate “slice” of the IL, so that a back end can put out each instantiation in a separate object file. The slices are defined by having a separate “needed” flag for each slice (there’s an array of them attached to each IL entity), and setting the slice-specific needed flags so that each slice contains only the types, variables, etc. referenced by the template instantiation in that slice.

When there are multiple translation units, the per-instantiation needed flags are not maintained in the secondary translation unit IL. Once the IL is copied to the primary IL, the flags are built up and maintained appropriately there.