CALL

Steps in Compiling and Running a C Program

1. Compiler
   • C Program foo.c -> Assembly Program foo.s
   • gcc -S -O2 foo.c
2. Assembler
   • Assembly Program foo.s -> Object (Machine Language Module) foo.o
   • gcc -c foo.s
3. Linker
   • Object foo.o + lib.o -> Executable Machine Language Program a.out
   • gcc foo.o
4. Loader
   • Executable: a.out -> Memory
   • ./a.out

Compiler

• Input: High-level Langage Code
  • e.g., foo.c
• Output: Assembly Language Code
  • e.g., foo.s for RISC-V
  • May contain pseudoinstructions

Assembler

• Input: Assembly Language Code
  • e.g., foo.s for RISC-V
• Output: Machine Language Module, object file
  • e.g., foo.o for RISC-V
  • Object Code (machine code)
  • Information for linking and debugging
    • Symbol Table
    • Relocation Information
    • Data Segment
    • ...
• Reads and uses directives
• Replaces pseudoinstrutions with true assembly

Directives

• Directives give directions to the assembler
  • Often generated by the compiler
  • Directives do not perduce machine instructions, they inform how to build different parts of the object file
• Directives are ususally in static segment

Different directives

• .text Subsequent items put in user Text segment
  • (machine code)
• .data Subsequent items put in user Data segment
  • (source file data in binary)
• .globl sym Declares sym global and can be referenced from other files
• .string str Store the string str in memory and null-terminate it
• .word w1 ... wn Store the n 32-bit quantities in successive memory words

Object File Format

1. Object File Header: size and position of other pieces of the object file
2. Text Segment: machine code
3. Data Segment: binary representation of static data in the source file
4. Symbol Table: List of file's symbols, static data that can be referenced by other programs
5. Relocation Information: Lines of code to fix later (by Linker)
6. Debugging Information

Producing Machine Code

• Simple case
  • Arithmetic, Logical, Shifts, etc.
  • All necessary info is within the instruction already
• PC-Relative branches and jumps:
  • e.g., beq/bne, jal
  • Position-Independent Code (PIC):
    • Once pseudoinstructions are replaced with real ones, all PC-relative addressing can be computed
  • Determne the offset to encode by counting the number of half-word instructions between current instruction and the target instruction

Computing PC-Relative Address: Two-Passes

• Forward Reference problem, cannot compute all offsets in a single pass
• It takes two passes
  • Pass 1: Remember positions of labels (store in symbol table)
  • Pass 2: Use label positions to generate machine code

Other References

Not determined:

• References to other files
  • e.g., calling strlen from C string lib
• Reference to static data
  • e.g., la -> lui + addi
  • Require knowing the full 32-bit address of the data

Assembler join them down in two tables:

• Relocation Information
• Symbol Table

Symbol Table

• List of "items" in this file
• Instruction Labels
  • Used to compute machine code for PC-relative addressing in branches, function calling, etc.
  • .global directive: labels can be referenced by others
• Data: anything in the .data section
  • Global variables may be accessed/used by other files

Relocation Information

• List of "items" whose address this file needs
• Any external label jumped to (including lib files)
• Any piece of data in static section

Linker

A Linker edits all the "links" in jump-and-link instructions

• Input: Object files
  • e.g., foo.o, lib.o for RISC-V
  • Text/Data segments, Info Table per file
• Output: Executable machine code
  • e.g., a.out for RISC-V

The Linker enables separate compilation of files

• Changes to one file does not require recompilation of the entire program

Linking Procedure

1. Put together text segment from each .o file
2. Put together data segments from each .o file, then concatenate this onto the end of Step 1's segment
3. Resolve references
   • Go through Relocation Table and handle each entry, i.e., fill in all absolute addresses

file1.o     file2.o
|Text 1|    |Text 2| 
|Data 1|    |Data 2|
|Info 1|    |Info 2|
       V    V
       LINKER
         |
         V
       a.out
  |Relocated Text 1     |
  |Relocated Text 2     |
  |Relocated Data 1     |
  |Relocated Data 2     |
  |Aggregated Info 1 + 2|

Relocating Addresses

Never relocate:

• PC-Relative Addressing (Position-independent code)
  • beq, bne, jal, auipc/addi, etc

Always relocate:

• External Function Reference (Addresses were unknown at assembling)
  • usually jal or auipc/jalr
• Static Data Reference
  • lw, sw, lui/addi

Relocation Editing Instructions

• J-Format (jumping externally)
• Loads and stores using gp to access .data variables
  • Global pointer (gp) is a pointer to the data/static segment
• lui, addi; auipc/jalr (if jumping externally)

Resolving References

• For RV32, Linker assumes first text segment starts at address 0x10000
• Linker knows:
  • Length of each text/data segment
  • Ordering of text and segments
• Linker calculates:
  • Absolute address of each label to be jumped to and of each piece of data referenced
• Linker resolves references:
  • Search for reference (data or label) in all "user" symbol tables
  • If not found, search library files (e.g., for `printf)
  • Once absolute address determined, fill in machine code appropriately
• Linker output:
  • Executable containing text and data (+ header, debugging info)

Static and Dynamic Linking

• Statically-linked libraries
  • Library is part of the executable. If library updates, need to recompile the user program
  • The executable includes the entire library, even if not all of it is used
  • Pro: The executable is self-contained
• Dynamically-linked libraries (DLL)
  • Library linked at runtime
  • Space vs. Time
    • Storing a program requires less disk space
    • Executing two programs requires less memory (if they share a library)
    • Con: Runtime overhead - extra time to link
  • Reasonable handling of upgrades
    • Replacing libXYZ.so upgrades every program using library XYZ
    • Con: Need to have DLL file other than executable
  • Prevailing approach to DLL uses machine code as the "lowest common denominator"
    • "Linking at the machine code level", i.e., linker does not know what compiler / what language compiled from

Loader

Loader is the operating system

• Input: Executable Code
• Output: (program is run)
• Executable files are stored on disk
• When an executable is run, loader loads it into memory and start it running

A loader:

• Load program into a newly created address space
  • Reads executable file’s header to determine size of text and data segments
  • Creates new address space for program large enough to hold text and data segments, along with a stack segment
    • Copy instructions, data from executable file into new address space
    • Copy argumnets passed to the program on the stack
• Initialize machine registers
  • Most registers cleared; stack pointer assigned address of 1st free stack location
• Jumps to start-up routine
  • Copy program arguments from stack to registers, set PC, and call main
  • If main routine returns, terminates program with exit system call

Example: Hello World

Compile: hello.c -> hello.s

#include <stdio.h>
int main() {
  printf("Hello, %s!\n", "world");
  return 0;
}

.text                # Directive: Enter text section
  .align 2           # Directive: Align code to 2^2 bytes
  .globl main        # Directive: Declare global symbol `main`
main:                # Label for start of `main`
  addi sp, sp, -4
  sw   ra, 0(sp)
  la   a0, str1      # Load addresses of str1, str2
  la   a1, str2
  call printf        # Call function `printf`
  lw   ra, 0(sp)
  addi sp, sp, 4
  li   a0, 0         # Return with value 0
  ret
.section .rodata     # Directive: Enter **read-only data** section
  .balign 4          # Directive: Align data section to 4 bytes
str1:                # Label for `str1`
  .string "Hello, %s!\n" # Directive: null-terminated string
str2:
  .string "world"

Assemble: hello.s -> hello.o

Text segment

00000000 <main>:
0:  ff010113 addi sp, sp, -16
4:  00112623 sw   ra, 12(sp)
8:  00000537 lui  a0, 0x0        # la, call
c:  00050513 addi a0, a0, 0      # pseudo-instructions
10: 000005b7 lui  a1, 0x0        # replaced
14: 00058593 addi a1, a1, 0
18: 00000097 auipc ra, 0x0       # 0, 0x0
1c: 000080e7 jalr ra, 0          # address placeholders
20: 00c12083 lw   ra, 12(sp)
24: 01010113 addi sp, sp, 16
28: 00000513 addi a0, a0, 0
2c: 00008067 jalr ra

Symbol Table

Label	Address (in module)	Type
main:	0x00000000	global text
str1:	0x00000000	local data
str2:	0x0000000c	local data

Relocation Information

Address	Type	Dependency
0x00000008	lui	%hi(str1)
0x0000000c	addi	%low(str1)
0x00000010	lui	%hi(str2)
...	...	...

Link: hello.o -> a.out

000101b0 <main>:
101b0: ff010113 addi sp, sp, -16
101b4: 00112623 sw   ra, 12(sp)
101b8: *00021* 537 lui  a0, 0x21
101bc: *a10* 50513 addi a0, a0, -1520  # 20a10 <str1>
101c0: *00021* 5b7 lui  a1, 0x21
101c4: *a1c* 58593 addi a1, a1, -1508  # 20a1c <str2>
101c8: *28800* 097 auipc ra, 0x0       # <printf> 28800
101cc: 000080e7 jalr ra, 0          
101d0: 00c12083 lw   ra, 12(sp)
101d4: 01010113 addi sp, sp, 16
101d8: 00000513 addi a0, a0, 0
101dc: 00008067 jalr ra

lui/addi Address Calculation

Target address of <str1> is 0x00020A10

>>>> lui  0x00020
>>>> addi 0xA10
Wrong result because 0xA10 is negative
0x00020 000 + 0xFFFFF A10 = 0x0001F A10
(off by 0x00001 000)

Correct version:
(0x00020 000 + 0x00001 000) + 0xFFFFF A10
= 0x00020 A10
- Two's complement of 0xFFFFF A10 = 0x00000 5EF + 1 = 1520
- 0xFFFFF A10 = -1520

>>>> lui  0x00021
>>>> addi -1520
0x00020 A10