Princeton University
COS 217: Introduction to Programming System

Precept 18: Assembler Assignment Pass 1

Purpose

Describe pass 1 of the assembler

The Forward Reference Problem

Example:

        ba label1
        ...
label1:
Assembler must generate machine code for "ba label1", but where is label1???

Solution to the forward reference problem:

Assembler performs two passes

Pass 1 creates symbol table defining locations of labels (which section, what offset within the section)

Pass 2 uses symbol table to generate machine code

The Symbol Table

Consists of bindings -- one binding for each label used in the assembly language program

Better name: label table

Key: a label name (string)

Value: a pointer to an Elf32_Sym structure:

(1) Section (data, bss, text, or undefined)
(2) Offset within section (0 if undefined)
(3) Global/local
(4) Sequence number (unique across all sections)

Implemented using Hanson's Table ADT

Stage 1: Pass 1

See the Assembler Assignment: Development Stages summary sheet

Objective: Fill out symbol table

Put one binding into symbol table for each unique label in the assembly language program

[Show conceptual symbol table on board]

| Label | Section | Offset | Local/Global | Seq# |

Must maintain three location counters

One for each section

Initialized to 0

[Show location counters on board]

iDataLc, iBssLc, iTextLc

Must keep track of which section (data, bss, or text) is "active"

[Show star on board next to appropriate location counter]

Example: 01section.s -- with labels added at every possible point

Handouts showing testing program 01section.s and the symbol table that it generates, as printed by print_passes()

.section ".data"
	Make the data section the current one
label0:
	Add a binding to the symbol table (label0, data, 0, local, 0)
.ascii "hello\t", "cs217\n"
	Increment the data section location counter by 6 (to 6)
	Increment the data section location counter by 6 (to 12)
label1:
	Add a binding to the symbol table (label1, data, 12, local, 1)
.asciz "assignment5\n"
	Increment the data section location counter by 13 (to 25)
label2:
	Add a binding to the symbol table (label2, data, 25, local, 2)
.skip 1
	Increment the data section location counter by 1 (to 26)
label3:
	Add a binding to the symbol table (label3, data, 26, local, 3)

.section ".bss"
	Make the bss section the current one
label4:
	Add a binding to the symbol table (label4, bss, 0, local, 4)
.skip 1
	Increment the bss section location counter by 1
label5:
	Add a binding to the symbol table (label5, bss, 1, local, 5)

.section ".text"
	Make the text section the current one
label6:
	Add a binding to the symbol table (label6, text, 0, local, 6)
add %r1, %r2, %r3
	Increment the text section location counter by 4
label7:
	Add a binding to the symbol table (label7, text, 4, local, 7)

.section ".data"
	Make the data section the current one (again)
label8:
	Add a binding to the symbol table (label8, data, 26, local, 8)
.byte 1, 2, 3
	Increment the data section location counter by 1 (27)
	Increment the data section location counter by 1 (28)
	Increment the data section location counter by 1 (29)
label9:
	Add a binding to the symbol table (label9, data, 29, local, 9)
.align 2
	Increment the data section location counter until it is evenly divisible by 2 (30)
label10:
	Add a binding to the symbol table (label10, data, 30, local, 10)
.half 4, 5
	Increment the data section location counter by 2 (32)
	Increment the data section location counter by 2 (34)
label11:
	Add a binding to the symbol table (label11, data, 34, local, 11)
.align 4
	Increment the data section location counter until it is evenly divisible by 4 (36)
label12:
	Add a binding to the symbol table (label12, data, 36, local, 12)
.word 6
	Increment the data section location counter by 4 (40)
label13:
	Add a binding to the symbol table (label13, data, 40, local, 13)

.section ".bss"
	Make the bss section the current one
label14:
	Add a binding to the symbol table (label14, bss, 1, local, 14)
.align 2
	Increment the data section location counter until it is evenly divisible by 2 (2)
label15:
	Add a binding to the symbol table (label15, bss, 2, local, 15)

.section ".text"
	Make the text section the current one
label16:
	Add a binding to the symbol table (label16, text, 4, local, 16)
add %r1, %r2, %r3
	Increment the text section location counter by 4 (8)
label17:
	Add a binding to the symbol table (label17, text, 8, local, 17)

Verify using the output of print_passes()

Example: 02symbol.s

Give handouts showing testing program 02symbol.s and the symbol table that it generates, as printed by print_passes()

.section ".data"
	Make the data section the current one
label0:
	label0 is not in the symbol table, so...
	Add a binding to the symbol table (label0, data, 0, local, 0)
.byte 0
	Increment the data section location counter by 1 (1)
.align 2
	Increment the data section location counter until it is evenly divisible by 2 (2)
.global label1
	label1 is not in the symbol table, so...
	Add a binding to the symbol table (label1, unknown, unknown, global, 1) 
label1:
	label1 is in the symbol table, so...
	Edit its binding in the symbol table (label1, data, 2, global, 1) 
.half 0
	Increment the data section location counter by 2 (4)

.section ".text"
	Make the text section the current one
label2:
	Add a binding to the symbol table (label2, text, 0, local, 2) 
add %r1, %r2, %r3
	Increment the text section location counter by 4 (4)
.global label2
	label2 is in the symbol table, so...
	Edit its binding in the symbol table (label2, text, 0, global, 2) 
.global label3
	label3 is not in the symbol table, so...
	Add a binding to the symbol table (label3, unknown, unknown, global, 3)