Linking and Generation of Executable Code
from Source Program Files

Types of Source Program Files

Source program files contain text (characters) that describe the data elements and the processing required to perform some particular processing task.

The form that this textual description takes depends upon the specific language being used. In general, such languages can be divided into two major categories: high-level languages (e.g. Java) and low-level or assembler languages (e.g. Intel assembly language). In either case, the textual program must be converted from text (characters) into the stored-program binary machine code actually used to control the computer's internal circuits.

A compiler is a program that translates high-level source program files (e.g. C++) into binary machine code. A compiler translates high-level statements into machine-level instructions, often requiring many machine-level instructions to perform each high-level program statement. The high-level language is independent of the type of CPU or processor being used.

An assembler is a simpler translating program that translates low-level source program files for a specific CPU type into binary machine code. Each machine-level action of the CPU is represented by a single low-level mnemonic textual code. Assembly language coding provides a direct way of controlling the CPU at the machine-code level, without having to remember and write the machine code. The assembler program is specific to the type of CPU being used.

Understanding the assembly process is necessary to understand the translation process of higher level languages into machine code. In many cases, compilers can be told to produce assembly language as an intermediate output file.

In addition to the use of mnemonic codes to represent machine-level instructions, assembly language coding uses symbolic labels to represent memory addresses, rather than having to use actual numbers. When a specific memory location is required for use in an instruction, a symbolic reference to the corresponding label is used. A label can only correspond to a single (low-level) memory address, however, there may be many symbolic references to this label.

Two-pass Assembly to Machine Language Translation

The translation of assembly language into machine-code requires that the assembly language file be read twice in a "two-pass" process:

  1. Pass 1: Determining label address locations - read the assembly language code in a first pass, determining the memory location for each instruction and data item. Record the memory addresses of any symbolic labels used in a label table called a symbol table.

  2. Pass 2: Translation to Machine Code - read through the assembly language code a second time. For each instruction, replace any symbolic addresses with their actual memory locations as determined during the first pass, then translate the mnemonic operation and its address into a machine level instruction.

Modularization of Program Development

Even once source code has been translated into machine level instructions, there is generally a lot of work that may need to be done before we have a working program.

Most programs are developed in a modular fashion and are composed of separate pieces (files) of code that have been assembled or compiled separately into independent machine-code output files, called object files. Some of these object files may be part of the program being developed, and others may be available as external libraries of object code, e.g. various system libraries of object code.

All these separately-produced object files need to be combined into one complete machine-code executable program.

Separate Compilation - Linking Independent Object Files

For each independent object file, there is no way to know at compile/assembly time what memory locations are available to store the machine code or where the object file will be in memory with respect to all the other object files used to make up the program. Each object file of machine code is therefore independently produced on the assumption that it is the only code in memory and that it will be placed in memory starting at location zero.

When it comes time to place all the separate object files into memory to create the program, work has to be done to relocate each object file into its own memory region. Each object file except the very first one has to be moved and relocated into a new memory region different from the region in which it was originally compiled/assembled.

All the machine instructions that refer to memory locations as if the module were loaded at location zero will have to be adjusted to refer to memory locations in the region of memory where the object file is actually loaded.

Memory references between object modules have to be resolved: When one piece of code makes a function/subroutine call or memory reference to a location inside another object module, those references have to be resolved into the actual memory locations where the modules end up in memory.

The process of taking separate machine-code object modules and combining them all into a working program is called linking.

To explore the linking process, we will first consider how the Little Man Computer can be expanded to permit handling of functions and subroutines.

LMC Subroutines - The CALL instruction

A function/subroutine may be called from several different locations in a main program and the subroutine must be able to return to the instruction after whichever instruction called it. Coding a static JMP (jump) instruction in the subroutine does not work to return control from a subroutine back to the main program, since the jump could only return to one place. The jump provides no information as to from where the jump originated. Every call of a function/subroutine needs to record a different return address somewhere so that the subroutine can use the return address to return to the correct place in the calling program.

A function/subroutine call operation must somehow save the memory address of the instruction that occurs immediately after the call. Usually, a special "Subroutine Return" instruction is used to retrieve this saved address and use it to return to from where the subroutine was called. In designing the new LMC CALL instruction, we considered that the return address might be saved in one of several ways:

Support for the use of functions and subroutines necessitated the creation of a new LMC instruction named CALL, used to call functions/subroutines and allow the subroutines to return to the code that placed the CALL.

The original Little Man Computer posed some significant restrictions in implementing an extension that would permit management of subroutines. Specifically:

LMC Subroutine Implementation Method:

The method selected for the extended LMC (called the "sonOfLMC") is to use the unused numeric code 0xy as the CALL xy instruction in a method very similar to the use of 9xy as the JMP xy instruction.

The difference between the CALL xy and JMP xy is that the CALL xy first stores a "return address" trick in the memory location that immediately precedes the location being CALL'ed, i.e. at memory location xy - 1. That "trick" being stored is a JMP instruction that returns to the location physically after the CALL. In other words, the JMP being stored uses the address currently in the Counter when the CALL is being executed.

For CALL xy to work, each subroutine must be coded with a mailbox that is left unused, located immediately before the instruction that is being CALL'd in the subroutine. This unused mailbox will receive the JMP trick put there by the CALL instruction.

When a subroutine has completed its task and wishes to return to the "calling" routine, it must JMP to this trick location (that is to the mailbox containing the JMP put there by the CALL that entered the subroutine). The JMP to the JMP will cause control to return to the statement physically following the original CALL.

Parameter passing and value return for subroutines

Passing argument values to a subroutine and retrieving them in the subroutine as parameters involves some of the same memory location problems as maintaining the subroutine return address. Where do you put the arguments before calling a subroutine? Where do you put the return value(s) before returning from a subroutine? The actual method used depends upon the use of a protocol agreed to by both the calling and the called routines.

The method for passing parameter values to a subroutine is left unspecified by the structure of this extended version of the LMC. Parameter passing is a protocol to be decided upon between the two routines involved, but, in general, information sharing (passing argument values to the subroutine and returning result values to the calling routine) is normally achieved either through single values passed in the LMC calculator, or through the use of global labelled memory locations.

The main routine will typically copy subroutine argument values into global variables in the subroutine before calling the subroutine, and the subroutine will store return values in the same (or other) global variables before returning. This method assumes that, if separately assembled (or compiled modules are used, there will be some method for identifying these shared, labelled memory locations.

Separate Module Assembly (to Object Files)

As has been already noted, modules (or "subroutines") are generally assembled (or compiled) from source files into separate object files. This results in three major problems:

  1. Lost Public Labels - As a source file is translated into binary machine code by the assembler program, all the label address information is lost. Machine code has no label information. Object files containing machine code must therefore keep a separate table of Public Labels for use by the linker in identifying important address locations inside the module. Not all labels in the source code may be public. Local variable labels do not need to be preserved in the Public Label table. The label that is the start of a subroutine must be put in the Public Label table so that other programs can call the subroutine.

  2. Calls to External Routines - Calls to routines not included with the source can not have their actual memory addresses filled in to the machine code, since those addresses are not known at the time the source translation is done. The object file must keep a list of these "unresolved external references" for later resolution by the linker program when the linker knows where in memory these external routines have been placed. The object file must include the name of the called external routine and the location within the calling routine where the external routine is called, so that the linker knows what memory locations to fix when the actual memory addresses are known.

  3. Relocatable Address References - Instructions or data that were translated to machine code based on the assumption that the routine would be loaded starting at a specific address, usually zero, need to be modified if the routine is loaded at a different address. Not all machine code needs to be modified, only instructions or data that refer to addresses inside the routine need to be adjusted. The object file must contain a table of all locations containing addresses that must be relocated to reflect the actual load address used for the routine.

Object File Format

As a result of the above three problems, object files typically contain three tables to accompany the machine code. This means an object file contains four parts: machine code plus three tables:

  1. a Public Label table containing a list of all Public Labels defined within the module, and their corresponding mailbox (memory) addresses. "Public" labels are labels that should be made available to other modules. All other labels are private, local labels that are not visible to other modules. (Private labels may or may not be saved inside the object module. Some object modules only save private label information if you specifically ask for it for debugging purposes.)

  2. an External Reference table containing a list of all mailbox addresses that make references to public labels defined in other modules, plus the name of the actual label being referenced.

  3. a Relocation Address table containing a list of all the addresses containing instructions that include address references to addresses within the module (based on the false assumption that the module would be loaded starting at address 00). All relocatable memory address references will need to be adjusted to reflect the true memory address values once the true starting address of the module has been established by the linker.

All the addresses in the above three tables are themselves subject to relocation if the subroutine is loaded at a non-zero address.

LMC Relocation and Linking Example

Suppose we want a simple program that outputs pairs of numbers: the first number of each pair output will be a count value starting at 000 and stopping before reaching a MAX of 010; the second number of each pair will be double the value of the first number. In order to allow the user time to read the numbers output, the program will pause after each output for a certain amount of time (performing some time wasting loop). (Note that the program stops before reaching the MAX value; the MAX value is not output.)

We will code this as 3 separate source files: a MAIN program and two subroutines Pause() and Dble(). Here is the pseudocode for the three modules:

        // *** MAIN program ***
        int count = 1
        int max = 10
        do {
           output count
           call Pause()
           call Dble(count)
           count += 1
        } while ( count < max );

        // *** PAUSE subroutine ***
        subroutine Pause() {
           int count = 0
           do {
              count -= 1
           } while ( count != 0 );

        // *** DBLE subroutine ***
        subroutine Dble(arg) {
           output arg+arg
           call Pause()

Here are the three modules, translated in to LMC assembly language and then assembled into three object files:

MAIN program
MAIN Mnemonic Source Code MAIN Object File - machine code and tables
Repeat  LDA Count   ; output count
        CALL Pause
        LDA  Count
        STO  Arg    ; store subroutine argument
        CALL Dble
        LDA  Count  ; count += 1
        ADD  One
        STO  Count
        SUB  Max    ; while ( count < max )
        JMP  Repeat
Count   DAT  000   ; local symbol (not Public)
One     DAT  001   ; local symbol (not Public)
Max     DAT  010   ; local symbol (not Public)
        PUB  MAIN  ; MAIN is a Public Label
Pause   EXT        ; Pause is an External Ref.
Arg     EXT        ; Arg is an External Ref.
Dble    EXT        ; Dble is an External Ref.
00: 113
01: 600
02: 000
03: 113
04: 200
05: 000
06: 113
07: 314
08: 213
09: 415
10: 802
11: 900
12: 700
13: 000
14: 001
15: 010
Public Label Location
External Reference Location
Pause 02
Arg 04
Dble 05
Relocatable Address Locations
00, 03, 06, 07, 08, 09, 11
Pause Subroutine
Pause Mnemonic Source Code Pause Object File - machine code and tables
        DAT        ; CALL return address
Pause   LDA  Count ; start of subroutine
        SUB  One
        STO  Count
        SKZ        ; while ( count != 0 )
        JMP  Pause
        JMP  Pause-1
Count   DAT  000   ; local symbol (not Public)
One     DAT  001   ; local symbol (not Public)
        PUB  Pause ; Pause is a Public Label
00: 000
01: 107
02: 408
03: 207
04: 801
05: 901
06: 900
07: 000
08: 001
Public Label Location
Pause 01
External Reference Location
Relocatable Address Locations
01, 02, 03, 05, 06
Dble Subroutine
Dble Mnemonic Source Code Dble Object File - machine code and tables
Arg     DAT        ; input argument to Dble
        DAT        ; CALL return address
Dble    LDA  Arg   ; start of subroutine
        ADD  Arg   ; double the input value
        CALL Pause
        JMP  Dble-1
        PUB  Arg   ; Arg  is a Public Label
        PUB  Dble  ; Dble is a Public Label
Pause   EXT        ; Pause is an External Ref.
00: 000
01: 000
02: 100
03: 300
04: 600
05: 000
06: 901
Public Label Location
Arg 00
Dble 02
External Reference Location
Pause 05
Relocatable Address Locations
02, 03, 06

As is always the case with separately created modules, the main program and each subroutine have been assembled into object modules and machine code as if none of the other code existed:

If we collect all the Public Labels from all modules, we have Public Labels for MAIN, Pause, Arg, and Dble. If we collect all the External References from all modules, we have External References for Pause, Arg, and Dble. Every External Reference can be matched with a Public Label, which means all the modules are present.

Link-Edit Processing or "Linking"

Combining multiple object files together to form a single executable program (often stored as a file) is the job of a program called a link-editor, or "Linker". The link process can be viewed as a sequence of five steps:

  1. Copy the numeric codes from all object files into sequentially contiguous locations, keeping track of the address used for each routine's new memory start address. Typically the first object file is loaded starting at address zero and the other object files go at higher memory locations.

  2. The tables in each object file were built assuming the object file was loaded at location zero. Since we have just loaded many subroutines at non-zero start addresses, we have to fix the addresses in the tables for each routine to reflect the new location of the subroutine in memory. Adjust the memory location specifications in the Public Label, External Reference, and Relocatable Address Location tables in each object file by adding the new memory load address of the subroutine to each location specification in each table.

  3. Having loaded all the subroutines into memory, we now know exactly where in memory each public symbol resides and we can go back and fix up the external reference information in all the loaded routines. Adjust all external reference memory locations by adding the actual public address of the externally referenced public symbol to the address portion of instruction at that location.

  4. The code in each object file was built assuming that the object file was loaded at location zero. Since we have just loaded many subroutines at non-zero start addresses, we have to fix each relocatable instruction in each subroutine to account for the move to a new location. Using the relocatable address locations table in each object file, adjust all relocatable address locations in each subroutine by adding the new memory address of the corresponding routine to the address operand at each relocatable location.

  5. The program is now "linked" and ready to execute as a unit. Save the modified numeric code to an executable file.

We will expand each of the above five steps by running through this process with the previously generated object files:

  1. The Linker copies the numeric instruction codes from each of the object files into contiguous (mailbox) memory locations. The order that the modules are placed in memory is not usually under the control of the programmer - the linker chooses. We choose to load Main followed by Pause followed by Dble (with a small line showing the boundary between each):
    00: 113
    01: 600
    02: 000
    03: 113
    04: 200
    05: 000
    06: 113
    07: 314
    08: 213
    09: 415
    10: 802
    11: 900
    12: 700
    13: 000
    14: 001
    15: 010
    16: 000
    17: 107
    18: 408
    19: 207
    20: 801
    21: 901
    22: 900
    23: 000
    24: 001
    25: 000
    26: 000
    27: 100
    28: 300
    29: 600
    30: 000
    31: 901

    The main program loaded at zero; Pause loaded starting at memory address 16; Dble loaded starting at memory address 25. The linker builds a table indicating the actual location where each subroutine was loaded in memory:

    Routine Assembled to load at: Actually Loaded At:
    main routine 00 00
    Pause subroutine 00 16
    Dble subroutine 00 25

    The linker will use these new memory locations to "relocate" addresses inside each subroutine, below.

  2. We have put subroutines into memory at non-zero starting addresses, and we now have to fix the addresses in the object file tables to reflect the new memory location of each subroutine. We have three tables to fix in each of the object files: the Public Label table, the External Reference table, and the Relocatable Address Locations table.
  3. Having loaded all the subroutines into memory, we now know exactly where in memory each public symbol resides and we can go back and fix up the unresolved external reference information in all the loaded routines:

    All external references have now been updated to refer to their correct memory locations.

  4. Finally, the instructions at the locations identified by the (modified) relocatable address locations table inside each object file must be adjusted by the actual location where that specific subroutine was loaded. The contents of memory at the addresses specified in the (modified) relocation address locations table must be modified to compensate for the actual load address of the subroutine:

    This completes the relocation of all the instructions in all the subroutines.

The linker has resolved all external references and relocated all relocatable code. At this point all address operands should be correct and the combined block of code properly executable. The code is output to an executable file, ready for loading and execution by the system.

Link Process Summary

Load and Execute Operating System Functions