Program Relocation

The squares prgram in the previous section contains four labels. The addresses of these labels are shown in the symbol table below:

These addresses are used to construct the constants contained in the branch and jump instructions. The address constants stored in the instructions have two possible interpretations:

1. The actual address of a memory location, also called an absolute address;
2. The offset to a memory location relative to a second known location.

Branch instructions use PC-relative addresses, while jump instructions use absolute addresses. Relative addresses allow a program module to be loaded at any address in memory without changing the addresses stored in the instructions. If all addresses in a module are relative, the module is relocatable.

The instruction

        bgtz    $3, end

in the squares example assembles to the machine code 0x1C600005. The immediate constant 5 appears in the address field of the machine code because the bgtz is located at address 0x0040 0018 and the address of end is 0x0040 0030. The difference between the addresses of the branch and the target is 0x18 bytes, or 6 words. Since the PC has advanced to the instruction following the branch when the branch is executed, the PC-relative offset stored in the branch instruction is 5 words.

The relative address which appears in a TAL branch instruction is given in bytes. The byte offset for the previous branch instruction is 20 bytes.

The general form of the branch offset in the machine code is:

The offset gives the address of the target instruction relative to the branch instruction. When the branch and target are relocated together, the constant remains unchanged.

The j while instruction employs an absolute address. The immediate field in the machine instruction contains 0x10 0005, which is 0x0040 0014, the address of the while label, divided by 4. If the code is relocated to another position in memory, the address stored in the jump instruction must be modified to reflect the new location of the while label.

The assembler maintains a list of all instructions containing absolute addresses as part of the symbol table. When a program module is assigned an actual address in memory, the loader phase of the assembler modifies any absolute addresses to produce the correct result.

By saving the address of the first instruction in a module as the base address for the module, the absolute addresses can be modified by the difference between the base address and the assigned address when a module is relocated in memory.