Generation of Executable Code from Source Program Files

Source Program Files

The form that this textual description takes depends upon the specific "language" being used. In general such "languages" can be divided into two major catagories: "high-level" languages and "low-level" (or "assembler") languages. In either case, the textual description must be converted, from text (characters), into the binary patterns actually used by the computer's internal circuits to specify and control the activities required. A "compiler" is a program which translates "high-level" source program files into these binary patterns (often called "machine-level" code; a "compiler" translates single "high-level" statements into several (often, many) "machine-level" instructions. An "assembler" is a similar, but much simpler, translating program which translates each "low-level" instruction into a single "machine-level" instruction; each "machine-level" action is represented by a single, simple "low-level" textual code, called a "mnemonic" code. Mnemonic coding provides a reasonable way of controlling the computer at the machine level, although it would be a tedious method for developing very large programs or systems.

Understanding the "assembler" process is necessary as a starting point for understanding the translation process of higher level languages (using "compilers") into instructions the computer can process,

In addition to the use of mnemonic codes to represent machine-level actions, assembler (or mnemonic) coding typically uses symbolic labels to represent addresses (including data addresses) which at the machine-level are identified as (numeric) bit patterns. 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.

Translation of "mnemonic code" using symbolic addresses into machine-level instruction requires that the mnemonic (source) code file be read twice:
- once to determine the memory address to associate with each symbolic reference, and
- a second time to replace sybolic references with the associated addresses (and translate operation codes)

Steps in Assembler to Machine Language Translation

• Determining symbolic-actual address pairs - read the code in a "first pass" determining the memory location for each instruction and data item; specifically, the memory addresses of any symbolic labels should be recorded
• Translation - read through the code again (the "second pass"); for each instruction, replace any symbolic address with its memory location as determined during the first pass, then translate the mnemonic operation and its address into a machine level instruction (using a table of mnemonic-to-machine codes)

Modularization of Program Development

Most programs are developed in a "modular" fashion and are composed of routines (or "subroutines") which have been assembled or compiled into (separate) independent "object" files. Some of these subroutine object files may have been developed as integral components of the specific program being developed, but others may be "general purpose" routines (prehaps even supplied with the "assembler" or "compiler") which may be stored in composite library file or object subroutines.

All these files need to be combined into one complete program. Addresses will not match where they were assumed to belong by the "assembler" (or "compiler") since there would be no way for these programs to tell the size of other routines which would need to appear in memory locations ahead of any specific subroutine. All such addresses, therefore, will need to be modified to compensate for where the routines have actually been loaded into real memory.

In order to more fully explore this process, we will first need to consider how the "Little Man" Computer could be expanded to permit handling of "subroutines".

Subroutine Management

Support for the use of subroutines requires additions to the basic LMC structure
• Maintaining a "return" address - A subroutine may be "called" from several different locations and must be able to return to the next instruction after whichever instruction "called" the routine; "jumping" to a routine provides no information as to where the "jump" originated from
• Call and Return operations - The "Call" operation must somehow save the address of the instruction which physically occurs immediately after the "Call"; a special "Return" instruction is normally employed to retrieve this "saved address" and set it up as the next instruction address
  The "return address" may be saved in:
  • a register (the calculator's "accumulator" in the LMC)
  • a fixed memory location
  • a memory location at a fixed "offset" from the "called" subroutine
  • a memory location which is part of a hardware maintained "stack"
• Argument-Parameter passing - 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"; generally, the same methods are available, but the actually method used depends less upon the hardware level of support and more upon the use of a "protocol" agreed to by both the "calling" and the "called" routines.

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

1. Only one decimal digit (0) was not used by the original "Little Man" as a machine-level "operation code". This meant that, while it was possible to add an new instruction to "call" a subroutine, there were no numeric code values left to add a "return" instruction.
2. Establishing a method for saving the "return address" (the location where control should resume after completion of the subroutine) is difficult. The "Little Man" Computer supplies only a single "working" register, the Accumulator, and no easy way to use the contents of this register as an address. Furthermore, if the Accumulator were used to hold the "return address" when a call were made to a subroutine, this would elimate the possibility of using the Accumulator to pass values to or return values from the subroutine.

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 through the use of "global" labelled memory locations. This "normal" method assumes that, if separately assembled (or compiled modules (routines) are used, there will be some method for identifying shared, labelled memory locations.

Separate Module Assembly (to Object Files)

1. Calls to External Routines - Calls to routines not included with the source can not have their actual memory addresses filled in since those addresses will not be known at the time the translation is done.
2. Variable Address References - Addresses of instructions or data which were translated based on the assumption that the routine would be loaded starting at a specific address, will be invalid (and will need to be modified) if the routine is loaded at a different address.
3. Modifications to Object File for Calling Modules - The "object" file for routines which call other (external) routines must include the name of the "called" routine and the location within the "calling" routine where the "called" routine is called.
4. Modifications to Object File for Called Modules - "Called" routines (as a result of not being the "main" routine) can not rely on any fixed address references as being valid; the "object" file must contain a table of all locations containing addresses that must be "reloacted" to reflect the actual load address used for the routine.

Suppose this has been coded as 3 separate "source" files (using mnemonic assembler code):

Mnemonic Code	Object Code
// main program Repeat LDA Count OUT CALL Pause LDA Count STA Arg CALL Dble LDA Count ADD One STA Count SUB Max SKP JMP Repeat HLT Count DAT 000 One DAT 001 Max DAT 010 Pause EXT Arg EXT Dble EXT	00: 113 01: 600 02: 000 03: 113 04: 201 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 (none)   external reference location Pause 02 Arg 04 Dble 05 relocatable address locations (none)

// Pause subroutine DAT Pause LDA Count SUB One STA Count SKZ JMP Pause JMP Pause-1 Count DAT 000 One DAT 001 PUB Pause

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 (none)   relocatable address locations 01, 02, 03, 05, 06

// Dble subroutine DAT Dble JMP overArg Arg DAT overArg LDA Arg ADD Arg OUT CALL Pause JMP Dble-1 PUB Dble PUB Arg Pause EXT

00: 000 01: 903 02: 000 03: 102 04: 302 05: 600 06: 000 07: 900

public label location Dble 01 Arg 02 external reference location Pause 06 relocatable address locations 01, 03, 04, 07

Link Processing

The link process can be viewed as a series of steps:
1. copy the numeric codes from all object files into sequentially contiguous locations, keeping track of the address used for each routine's "entry point".
2. adjust the location specifications in the "external reference" & "relocatable address locations" tables by adding the entry point address of the routine to each location specification.
3. adjust all external reference locations by adding the actual entry point address of the externally referenced routine to the address portion of instruction at that location.
4. adjust all relocatable address locations by adding the entry point of the corresponding routine (i.e. the routine containing the specific "relocatable address locations" table) to the address operand at each location.
5. copy the modified numeric code to an "executable" file.

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 and builds a table indicating the actual location where each subroutine was loaded, plus a table of public labels with their locations modified by the addition of the beginning load address of the subroutine which contains the definition of each public entry:

   00: 113 01: 600 02: 000 03: 113 04: 201 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: 903 27: 000 28: 102 29: 302

   30: 600 31: 000 32: 900

   routine loaded at: main routine 00 Pause subroutine 16 Dble subroutine 25

   public label location Pause 01 17 Dble 01 26 Arg 02 27 Dble 01 26

2. using the external reference table from the main object file:
   

   external reference	location
   Pause	02
   Arg	04
   Dble	05

   the instructions in (mailbox) addresses 02, 04, and 05 are changed by adding the location address from the (modified) public label table to the current contents:

   02: 000 017 03: 113 04: 200 227 05: 000 026

   CALL Pause LDA Count STO Arg CALL Dble

3. Since the Pause object file contains no external references, no modifications are required to this portion of the code to "fill in" the addresses for external references

4. Similarly the external reference table from the Dble object file is used to modify the contents of the location within the Dble subroutine which CALLs the Pause subroutine. Note that the locations in the external reference table must be modified (by the addition of the Dble subroutine's load address) before they (actually, in this case, "it") can be used.
   

   external reference	location
   Pause	06 31

   Since the (modified) public label table identifies mailbox address 17 as corresponding to the public label "Pause", then the contents of mailbox 31 (above) must be modified by the addition of 17.

   31: 000 017

   CALL Pause

5. Finally within the (mailbox) addresses for each subroutine, the instructions at the locations identified by the relocatable address locations table from each object file, must be adjusted by the actual location where that specific subroutine was loaded.
   Note that there are two address adjustments required for each subroutine:
   
   1. The relocatable address locations table must be adjusted to compensate for the actual load address of the subroutine:

      For the Pause subroutine (loaded starting at 16) relocatable address locations

      01 17,   02 18,   03 19,   05 21,   06 22

      For the Dble subroutine (loaded starting at 25) relocatable address locations

      01 26,   03 28,   04 29,   07 32

   2. 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:

      For the range of mailboxes of the Pause subroutine
      values from the Pause object file	modified instructions base on load at 16
      16: 000 17: 107 18: 408 19: 207 20: 801 21: 901 22: 900 23: 000 24: 001	16: 000 17: 123 18: 424 19: 223 20: 801 21: 917 22: 916 23: 000 24: 001

      and, similarly, the relocatable addresses within the Dble subroutine range will be updated.

      For the range of mailboxes of the Dble subroutine
      values from the Dble object file	modified instructions base on load at 25
      25: 000 26: 903 27: 000 28: 102 29: 302 30: 600 31: 000 32: 900	25: 000 26: 928 27: 000 28: 127 29: 327 30: 600 31: 000 32: 925

   At this point all address operands should be correct and the combined block of code properly executable.

Link Process Summary

Pre-compiled and pre-assembled routines are combined to form an executable program by a kind of program called a "Linker".
• Object File Reference Tables - As we have already seen, each object file must contain a table of all subroutines which it "calls" and for each a list of all "call" locations where the subroutine's address must be "filled in".
• Load Process and Load Module Reference Tables - Starting with a "main line" routine, the "Linker" copies the routine into memory and for each object subroutine referenced copies that routine into memory (with its sub-subroutine references). The actual address where each routine loaded must be maintained in a table (together with the name of the routine).
• Address Updating - The Linker must then go through the original object file reference tables and update "call" addresses with the locations where the routines were actually loaded. Internal addresses within each routine may need to be modified as well to reflect changes caused by loading the routines at addresses which were not known at translation time.
• Relative Addressing - The hardware in some computer processors provides a special "base address" register whose contents are automatically added to any address used to access memory. In this case, by loading the "base register" with the initial address of the "called" subroutine, all addresses that the subroutine uses can be "relative addresses" (that is the addresses are "offsets" or distances relative to the "base"/starting point of the routine).
• Executable Memory Image or Executable File - Once the Linker has completed "linking" object files, there are basically 2 options: the linked "image" can be executed immediately or (as is more common) the image can be written as an "executable" file to be loaded and run by the Operating System at a later time.

Load and Execute Operating System Functions

Assuming linked images are saved in files as "executable" programs, the Operating System must perform certain functions in order for the program to actually "be run".
• Loading Executable File - the first (obvious) requirement is that the Operating System must perform instructions which copy the executable file into memory.
• Further Address Relocation - unless the Operating System is designed so that programs are guaranteed to always be loaded into memory at some fixed address, the Operating System will need to establish a "base" register for automatic address relocation (this requires additional hardware support) or it must go through the entire program and adjust all address references.
• Giving Control to the Loaded Program - as a final act, the Operating System must reset the Program Instruction Counter to point to the first instruction of the program just loaded; note that at this point the Operating System effectively loses control of the computer.