Transcript Chapter 5 The LC-3 - Pages - University of Wisconsin–Madison

Adapted from slides provided by McGraw-Hill Companies Inc., modified by professors at University of Wisconsin-Madison
Why machine language?
+ The closest language to H/W. Allows us
to control exactly what the processor does.
- Too tedious to write and debug. 0’s and
1’s make our head spin!
Assembly Language

Human readable Machine language
 Instruction pneumonic instead of opcode

Some added functionality
 Labels to refer to memory locations

Assembler: A program which converts
the human readable form to machine
instructions.
Assembly language syntax
Each line of an assembly program may be
 Instruction
 LC-3 instruction
 An assembler directive (pseudo-operation)

A comment
(Blank lines are ignored)
(Whitespaces and case are ignored)
(Comments are ignored)
Instruction
LABEL OPCODE OPERANDS ; COMMENTS
optional
mandatory
LC-3 Opcodes

Reserved symbols/names to represent
the LC-3 instruction type

Whatever we used to call them in
Chapter 5!

Example: ADD, BR, LD, STR, …
Operands

Registers: Rn where n is register
number

Numbers: decimal(#50) or hex (x32)

Labels: Symbolic name for memory
location
Multiple Operands

Separate multiple operands by comma

Same order as in the binary instruction

For example:
0001 001 010 0 00 101
ADD
R1
R2
R5
ADD R1, R2, R5
Labels
Placed at the beginning of a line
 Symbolic name for the memory address
corresponding to that line.
 For example:

LOOP ADD R1, R1, #-1
BRp LOOP

Used to replace PCOffset in LC-3
instructions (LD, ST, LDI, STI,
BR, JSR)
Labels (restrictions)

Can be any alpha-numeric string
 Can include underscore ‘_’ in PennSim

Should start with an alphabet
 Unenforced in PennSim

1 - 20 characters long

Cannot be any of the reserved symbols of
LC-3 (like ADD, .ORIG, 19, xA3 etc.)
Comments

Anything after the semicolon ‘;’

Ignored by the assembler.

Can be used by the programmer to
 Document code
 Separate pieces of the program
Assembler directives

Pseudo operations

Not an instruction executed by the
program, but used by the assembler

Opcode with a dot ‘.’
Assembler directives
Opcode
Operand
Meaning
.ORIG
address
starting address of program
.END
end of program
.FILL
n
allocate one word, initialize with
value ‘n’
.BLKW
n
allocate ‘n’ words of storage
.STRINGZ
n-character
string
allocate n+1 locations,
initialize w/characters and null
terminator
Pseudo-Instructions
Names for various TRAP codes so that you don’t
need to remember them!
Code
Equivalent
Description
HALT
TRAP x25
Halt execution and print message to
console.
IN
TRAP x23
Print prompt on console,
read (and echo) one character from keybd.
Character stored in R0[7:0].
OUT
TRAP x21
Write one character (in R0[7:0]) to console.
GETC
TRAP x20
Read one character from keyboard.
Character stored in R0[7:0].
PUTS
TRAP x22
Write null-terminated string to console.
Address of string is in R0.
A full program
;
; Program to multiply a number by the constant 6
;
.ORIG x3050
LD
R1, SIX
LD
R2, NUMBER
AND
R3, R3, #0
; Clear R3. It will
; contain the product.
; The inner loop
;
AGAIN
ADD
R3, R3, R2
ADD
R1, R1, #-1
; R1 keeps track of
BRp
AGAIN
; the iteration.
;
HALT
;
NUMBER .BLKW 1
SIX
.FILL x0006
;
.END
Pseudo-code to Assembly
R1 <- R2 + R3
ADD R1, R2, R3
R1 <- R1 AND 10
AND R1, R1, #10
OR
AND R1, R1, xA
Pseudo-code to Assembly
R5 = M[M[x3020]]
(address x3020 has a label “NUMBER”)
LDI R5, NUMBER
BR on Z or P to x3030
(address x3030 has a label “LOOP”)
BRzp LOOP
Pseudo-code to Assembly
R6 = M[R2+5]
LDR R6, R2, #5
BR unconditionally to x301E
(address x301E has a label “NEXT”)
BRnzp NEXT
OR
BR NEXT
Pseudo-code to Assembly
Write data x5000 to memory
(add a label “ADDR” to that mem loc)
ADDR .FILL x5000
Store a string “Hi” to memory
(add a label “STR” to that mem loc)
STR .STRINGZ “Hi”
Writing an Assembly Program
Count the number of occurrences of a
character in a string.
[OR]
Set the value of x4000 to the count of
occurrences of a character, stored at
x4001, in a null-terminated string, starting
at x4002
Assembler

Program which converts an assembly
language program into machine code.

In programming terms, converts your
assembly language file (.asm/.txt) into
an executable (.obj) file.

We will use the inbuilt assembler in
PennSim
Assembly process

Two pass process
Assembly Process: 1st Pass

Scan the program file and create a
“Symbol Table”

Symbol Table: A table which contains
the addresses of all the labels in your
assembly language program.
1st Pass: Steps
1.
Find the .ORIG statement,
which tells us the address of the first instruction.

2.
Initialize location counter (LC), which keeps track of the
current instruction.
For each non-empty line in the program:


If line contains a label, add label and LC to symbol
table.
Increment LC.
Note: If statement is .BLKW or .STRINGZ, increment LC
by the number of words allocated.
3.
Stop when .END statement is reached.
Note: A line that contains only a comment is considered an empty line.
1st Pass: Practice
;
; Program to multiply a number by the constant 6
;
.ORIG x3050
LD
R1, SIX
LD
R2, NUMBER
AND
R3, R3, #0
; Clear R3. It will
; contain the product.
; The inner loop
AGAIN
ADD
R3, R3, R2
ADD
R1, R1, #-1
; R1 keeps track of
BRp
AGAIN
; the iteration.
;
END
HALT
;
RAND
.FILL x41FF
GREET
.STRINGZ “252!”
NUMBER .BLKW 2
SIX
.FILL x0006
.END
1st Pass: Practice
Symbol
Address
AGAIN
x3053
END
x3056
RAND
x3057
GREET
x3058
NUMBER
x305D
SIX
x305F
Assembly Process: 2nd Pass

Generate machine code for each line of
assembly statement

Use the symbol table to get the
addresses of the labels, so as to
calculate the PCOffset
Assembly Process: 2nd Pass

Errors identified in this pass
 Improper number or type of arguments
○ ex: NOT R1,#7
ADD R1,R2
ADD R3,R3,NUMBER
 Immediate argument too large
○ ex: ADD R1,R2,#1023
 Address (associated with label) more than
“specifiable by offset” from instruction
2nd Pass: Practice
For the previous example, generate
machine code for instructions at address:
x3050:
 x3055:

2nd Pass: Practice
For the previous example, generate
machine code for instructions at address:
x3050: 0010 001 000001110
 x3055: 0000 001 111111101

Issues

Assembly done. Great! How to execute
the code?

How to write code in a team? Many
people writing many assembly files?

How to use vendor defined libraries?
Loading

Process of copying an executable (.obj)
into memory.

We can load multiple .obj files, each
starting at a desired address.

User code: x3000 - xFDFF

Careful! Do not overlap the object files
Linking

Process of resolving symbols between
independent object files
 Suppose we want to use a symbol (label)
defined in a different .obj file
 some notation, such as .EXTERNAL, is used
to tell assembler that a symbol is defined in
another module
 linker will search symbol tables of other
modules to resolve symbols and complete
code generation before loading
Subroutines (Section 9.2)

Very similar to “functions” in High Level
Languages
Arguments
foo()
{
...
c = a + b
d = bar(c, a)
e = d + 3
...
}
Caller
Function
Return Value
bar(x, y)
{
z = x * y
return z
}
Callee/Called
Function
Subroutines

A program fragment the performs a well
defined task

Invoked (or called) by a user program

Returns control when the called program
has finished
Arguments & Return Values

Arguments
 The value(s) passed into a subroutine

Return Values
 The value(s) passed out of a subroutine
Why subroutines?

Reuse useful and debugged code,
rather than redoing work

Divide task among multiple
programmers

Use vendor supplied library of routines
How to call a subroutine?

Use assembly instructions: JSR or JSRR

Jumps to a location, like BR, but
unconditionally

Before jumping, copies (saves) PC into R7

Can use this “saved PC” to return to the
caller program
JSR & JSRR

Even though two assembly instructions,
same OPCODE in binary

Differ in bit 11 of the instruction
Instruction
JSR
Bit 11
1
Target Address
PC’ + PCOffset11
JSRR
0
Base Register
JSR (PC-Relative)
15
14
13
12
11
0
1
0
0
1
10
9
8
7
6
5
4
PCoffset11
3
2
1
0
JSRR (Register)
15
14
13
12
11
10
9
8
7
6
0
1
0
0
0
0
0
Base Reg
5
4
3
2
1
0
0
0
0
0
0
0
JSR & JSRR
What is the advantage of JSRR over JSR?
How to return to the caller?

Using the RET assembly instruction

Alias (pseudo-instruction) for JMP R7
JMP
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
1
1
0
0
0
0
0
Base Reg
0
0
0
0
0
0
Fix Base Register as R7
RET
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
1
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
Arguments and Return Values

Normally registers are used to
 Pass arguments from caller to callee
 Return value from callee to caller

Registers being used to pass arguments
and return values should be explicitly
stated when writing a subroutine
Example
; value is R0 is negated and
; Argument: R0 ; Return: R0
2sComp
NOT
R0, R0
ADD
R0, R0, #1
RET
returned
; flip bits
; add one
; return to caller
Note: Call must be from within 1024 memory locations!
...
; need to compute
ADD
JSR
ADD
...
R4 = R1 - R3
R0, R3, #0
; copy R3 to R0
2sComp
; negate
R4, R1, R0
; add to R1
Other Issues

The caller and the callee use the same 8
General Purpose Registers (R0-R7)

What if the callee modifies registers
which are being used by the caller?

Let us revisit our example and modify
the subroutine:
Example
R1 modified!
; value is R0 is negated and
; Argument: R0 ; Return: R0
2sComp
NOT
R0, R0
R1,
ADD
R0, R1,
R0, #1
RET
returned
; flip bits
; add one
; return to caller
Note: Call must be from within 1024 memory locations!
...
; need to compute
ADD
JSR
ADD
...
R1’s value has changed!
R4 = R1 - R3
R0, R3, #0
; copy R3 to R0
2sComp
; negate
R4, R1, R0
; add to R1
Two solutions!

Caller-save
 [problem solved by the caller]

Callee-save
 [problem solved by the callee]
Caller-save

Caller knows which registers are
modified by the callee

Caller saves those registers before the
call and restores them after the call

Generally, modified registers are not
known
 Solution: Save all registers
Example
; value is R0 is negated and
; Argument: R0 ; Return: R0
2sComp
NOT
R1, R0
ADD
R0, R1, #1
RET
returned
; flip bits
; add one
; return to caller
...
; need to compute R4 = R1 - R3
ADD
R0, R3, #0
JSR
ST
2sComp
R1,
SAVE_R1
ADD
JSR
R4, R1, R0
2sComp
...
LD
R1, SAVE_R1
ADD
R4, R1, R0
...
SAVE_R1 .BLKW 1
;
;
;
;
;
copy R3 to R0
negate
Save
R1
add to R1
negate
Restore R1
add to R1
Callee-save

Callee saves the registers which it will
modify at the beginning of the
subroutine

Restore the values before RET
Example
; value is R0 is negated and returned
; Argument: R0 ; Return: R0
2sComp
NOT
ST
R1, SAVE_R1;
R0
; Save
flip bits
R1
ADD
R0,
one
NOT
R1, R1,
R0 #1 ;
; add
flip bits
RET
to caller
ADD
R0, R1, #1 ;
; return
add one
LD
R1, SAVE_R1; Restore R1
RET
; return to caller
SAVE_R1 .BLKW 1
...
; need to compute
ADD
JSR
ADD
...
R4 = R1 - R3
R0, R3, #0
; copy R3 to R0
2sComp
; negate
R4, R1, R0
; add to R1
Notes

If the caller is a subroutine, it should
save R7.

Even if using callee-save, value of R7
has to be saved and restored by the
caller.
Assembly Instruction
LABEL OPCODE OPERANDS ; COMMENTS
optional
mandatory
Various parts of the instruction
Label
Symbolic name for the memory
address of the instruction
Opcode
• LC-3 instruction opcode
• Assembler directive
Operands
• Register: R0-R7
• Numbers: decimal (#10) or
hexadecimal (xA)
• Labels
Comments
• Ignored by the assembler
• Used by programmers for
documentation
Assembler Directives
.ORIG x3050
.FILL x35
.BLKW #3
.STRINGZ “Hi!”
.FILL #25
.END
Address
Value
x3050
x0035
x3051
x0000
x3052
x0000
x3053
x0000
x3054
x0048
x3055
x0069
x3056
x0021
x3057
x0000
x3058
x0019
Assembly Process

2 Pass Process

1st Pass
 Generate the symbol table
 [Symbol Table: Mapping of label to address]

2nd Pass
 Generate machine code
 Use symbol table to change labels to PCOffset
Loading and Linking

Loading
 Process of loading an executable to memory
 Multiple executable can be loaded into
memory at the same time

Linking
 Process of resolving symbols defined in a
different assembly file
Subroutines

Calling
 JSR or JSRR
 Save PC to R7

Returning
 RET or JMP R7

Arguments and Return values
 Using registers (need to be stated explicitly)
Saving and Restoring

Caller-save and Callee save

Caller save advantage
+ knows which registers it needs after the call
- doesn’t know which registers are modified by the
callee.

Callee save
+ knows which registers it is going to modify
- doesn’t know which registers caller needs.
Problem 1
.ORIG x3000
XAF ADD R0, R0, x1F
LOOP BRnz NEXT
BRp ZERO
LDR R1, Zero
NOT R3, #5
OR R1, R2, R1
HALT
Zero .FILL 0
LOOP .BLKW 2
CHAR .ASCII ‘a’
STR .STRINGZ “Time”
.END
Find the assembly
errors in the program.
Solution
.ORIG x3000
XAF ADD R0, R0, x1F
LOOP BRnz NEXT
BRp ZERO
LDR R1, Zero
NOT R3, #5
OR R1, R2, R1
HALT
Zero .FILL 0
LOOP .BLKW 2
CHAR .ASCII ‘a’
STR .STRINGZ “Time”
.END
Problem 2
.ORIG x3800
LEA R3, INPUT
LD R1, SIZE
ADD R3, R3, R1
LOOP
LDR R0, R3, 0
TRAP x21
ADD R3, R3, -1
ADD R1, R1, -1
BRp LOOP
HALT
INPUT .STRINGZ "RtbY"
STRING .BLKW #3
SIZE .FILL #3
TWO
.FILL #2
.END
(a) Generate the symbol table for the
above code.
(b) What are the values in memory (in
hex) at the following memory addresses:
x3800
x3807
x380B
x3811
Solution
Label
Address
-----------------INPUT
x3809
LOOP
x3803
SIZE
x3811
STRING
x380E
TWO
x3812
Address
Value
-----------------x3800
xE608
x3807
x03FB
x380B
x0062
x3811
x0003
Problem 3
.ORIG X3100
LEA R0, TRS
LD R1, SUM
LOOP LDR R2, R0, #0
BRz END
ADD R2, R2, R1
STR R2, R0, #0
ADD R0, R0, #2
BR LOOP
END HALT
SUM .FILL x20
TRS .STRINGZ "BYEBYE"
.END
What does this
program do?
Solution
Changes the string stored at TRS from
“BYEBYE”
to
“bYeByE”
Problem 4
SUB1
SUB2
.ORIG x3000
ST R0, SAVER0
ST R1, SAVER1
JSR SUB1
LD R0, SAVER0
LD R1, SAVER1
HALT
ADD R0, R1, R1
JSR SUB2
AND R2, R1, R0
RET
ST R3, SAVER3
AND R3, R0, R0
NOT R0, R3
LD R3, SAVER3
RET
.END
(a) Is there is a problem with the above
assembly language program? How will
you fix it?
(b) Is SUB1 caller-save or callee-save? Is
SUB2 caller-save or callee-save?
Solution

R7 has to be saved before call from
SUB1 to SUB2
SUB1: Caller-save
 SUB2: Callee-save

Problem 5

What single instruction is equivalent to the
following two LC-3 instructions?
LEA R7, #1
JMP R2, #0

RET instruction is executed at address x1234.
What is the range of possible values of PC
after this instruction executes?

Which assembler directive(s) can be used only
once in an assembly language program?
Solution

JSRR R2

0x0000 – 0xFFFF
 RET is “JMP R7”

.ORIG and .END