CIS 240 / CIT 593

Introduction to
Computer Systems
University of Pennsylvania
School of Engineering and Applied Science
Computer and Information Systems Department
Dr. Thomas Farmer

MODULE 7: Programming with LC-4 Assembly Language

Overview of Module #7

Background
• We now know the LC-4 ISA well, so let’s use it!#
• We’ll use groups of instructions to solve problems (programming!)
Section 1: Programming 101
• The basic constructs of all programming
Section 2: Assembly Programming Example #1: Loops
• Using a COMPARE/BRANCH/JUMP/LABELS to make a loop on the LC4
• In the process we’ll see while & if statements are related
Section 3: Assembly Programming Example #2: Subroutines
• What is a subroutine
• How to call it using: JSR/RET/FALIGN
Section 4: Assembly Programming Example #3: Working with Data Memory
• When the register file isn’t big enough
• LDR/STR instructions – How they work – What is a pointer?!
• For loops

Property of Penn Engineering 2

SECTION 1:

PROGRAMMING 101

Property of Penn Engineering 3

Basic Overview of Programming
What is Programming?
• Process of designing/writing/testing/debugging/maintaining the “source code” of computer programs

• Basically taking the 29 assembly instructions in the ISA and solving problems with them!

The 29 Instructions of ISA are like words in the English Language

• We can author great literature, or misuse them all together

• That’s up to us!

We now “know” the language of the LC-4: the LC4 ISA instruction set
• We must learn to use the language to have the CPU do useful things for us

• In the same way that AND/OR/NOT gave rise to a CPU…

• …29 simple instructions give rise to programs that can solve complicated problems!
Property of Penn Engineering 4
Programming Constructs
Variables – As in algebra, place to “store” information
• Ex: 5+6=11, OR Let A=5, B=6, then A+B=C
• Variables give us freedom to change our programs

Loops – A way to “repeat” a portion of a program over and over again

Let X=name
Loop Begin {
Print Paycheck for Bob
Print Paycheck for X
Print Paycheck for Cindy
Update X
Print Paycheck for John
All done? Yes->exit loop
} Loop End
Conditional Control – A way for our program to change natural flow of program based on a condition

if (today is end of month) {

• normally programs execute line after line print paychecks
} else {
order paper
}
Property of Penn Engineering 5
ISA, Machine Language, and Assembly Language
Machine language
• Bit patterns that are directly executable by computer
• Assembled into files called objects, binaries, executables
• Looks like gibberish to humans, but it’s the binary encoded instructions the CPU understands
• May also contain data, in addition to instructions

Assembly language (Symbolic representation of machine language)

• Instructions as mnemonic ASCII strings, e.g., ADD R2,R6,R2
• Can’t run, but mostly human readable
• Can be hand written or produced by a compiler from source
• In this module we’ll also see Assembly files can contain ASCII labels, e.g., BRnzp LOOP

Assembler: produces object file from assembly file

• Assembler directives: non-instructions tell assembler what to do

Property of Penn Engineering 6

The “Assembler”
– Bridge Between Assembly & Machine Code

ASSEMBLY Program
Text File (.asm)

Assembler
Translates input Assembly
program to Machine
Code

Machine Code
Binary File (.obj)
Can be loaded into
memory and executed
Property of Penn Engineering 7
SECTION 2: Assembly Programming Example #1: Multiplication

LOOPS / IF-ELSE IN ASSEMBLY

Property of Penn Engineering 8

Multiplication Program in LC-4 Assembly (no loop)
Implements C=A*B Register allocation: R0=A, R1=B, R2=C
Pseudocode of Algorithm: Assembly Program:
A = 2 Storing
CONST R0, #2
Variables
B = 3 CONST R1, #3 A, B, C
In Register
C = 0 CONST R2, #0 File

; we add A to itself 3 times

C=C+A ADD R2, R0, R2

C=C+A ADD R2, R0, R2 The Program

C=C+A ADD R2, R0, R2

Property of Penn Engineering 9

Multiplication Program in LC-4 Assembly (loop)
Implements C=A*B Register allocation: R0=A, R1=B, R2=C
Pseudocode of Algorithm: Assembly Program:
A = 2 Storing
CONST R0, #2
Variables
B = 3 CONST R1, #3 A, B, C
In Register
C = 0 CONST R2, #0 File

while (B > 0)
CMPI R1, #0 ; sets NZP
{
BRnz #3 ; tests NZP

C = C + A; ADD R2, R2, R0 ; C=C+A

B = B – 1; ADD R1, R1, #-1 ; B=B-1
} BRnzp #-5

Property of Penn Engineering 10

Multiplication Program in LC-4 Assembly (loop + labels)
Implements C=A*B Register allocation: R0=A, R1=B, R2=C
Pseudocode of Algorithm: Assembly Program:
A = 2 Storing
CONST R0, #2
Variables
B = 3 CONST R1, #3 A, B, C
In Register
C = 0 CONST R2, #0 File

LOOP Label
while (B > 0)
CMPI R1, #0 ; sets NZP
{
BRnz END ; tests NZP

C = C + A; ADD R2, R2, R0 ; C=C+A

B = B – 1; ADD R1, R1, #-1 ; B=B-1
} BRnzp LOOP
Offsets are calculated for
you by assembler END Label
Property of Penn Engineering 11
Multiplication Program in LC-4 Assembly (loop + labels)
Implements C=A*B Register allocation: R0=A, R1=B, R2=C
Pseudocode of Algorithm: Assembly Program:
A = 2 Storing
CONST R0, #2
Variables
B = 3 CONST R1, #3 A, B, C
In Register
C = 0 CONST R2, #0 File

LOOP Label SUB instead?

while (B > 0)
CMPI R1, #0 ; sets NZP
{
BRnz END ; tests NZP

C = C + A; ADD R2, R2, R0 ; C=C+A

B = B – 1; ADD R1, R1, #-1 ; B=B-1
} JMP LOOP ; same idea
Offsets are calculated for
you by assembler END Label
Property of Penn Engineering 12
LC-4 Assembly Constants

• For “immediate” instructions (CONST, HICONST, ADDI, etc)…

• Immediate data can be specified in the assembly code in two ways:
• Hexadecimal constants

➢ 0x4EEE, xAF

• Decimal constants

➢ #200, #-96

• Notice: x (for Hex), and # (for decimal)

Property of Penn Engineering 13

What Happens Next?
Assembly Program (.ASM): Machine Code (.OBJ):
CONST R0, #2 1001000000000010 ; CONST
CONST R1, #3 1001001000000011 ; CONST
CONST R2, #0 1001010000000000 ; CONST
LOOP
CMPI R1, #0 ; sets NZP 0010001100000000 ; CMPI
BRnz #3
END ; tests NZP 0000110000000011 ; BRnz
ADD R2, R2, R0 ; C=C+A 0001010010000000 ; ADD
ADD R1, R1, #-1
#-1; B=B-1 0001001001111111 ; ADDI
BRnzp #-5
LOOP5 0000111111111011 ; BRnzp
END

An “Assembler” Program is used to translate Assembly Programs (.ASM) into Machine Code (.OBJ)
Operates in two phases:
First phase (1st pass), converts labels into offsets, removes comments
Second phase (2nd pass), converts assembly code into machine code
Uses the ISA to do this, saves in a .OBJ file (object file)

After “Assembler” finishes…a “loader” program loads it into CPU’s program memory Property of Penn Engineering 14
PENNSIM DEMO

Property of Penn Engineering 15

SECTION 3: Assembly Programming Example #2

SUBROUTINES IN ASSEMBLY

Property of Penn Engineering 18

Subroutines in Assembly – Overview
• A subroutine is similar to a “function” in a high level language
• To enable, call, and return from subroutines in assembly, use the following outline:
1) Give the subroutine a unique name using a LABEL
2) Ensure subroutine is loaded at memory address that is multiple of 16 (How?? Our first directive: .FALIGN)
3) Pass it arguments by using the register file: R0->R6
4) Call the subroutine using ISA instruction: JSR
JSR = Jump to Subroutine
Mnemonic: JSR IMM11 <LABEL> ; converts label into IMM11
Semantics: R7 = PC + 1 ; stores PC value in R7
PC = (PC & 0x8000) | (IMM11 << 4) ; sets PC = IMM11 << 4
(IMM11 << 4) makes IMM11 a multiple of 16! Extends range of JSR
5) Return data using the register file: R0-R6
6) Return from the subroutine using ISA pseudo-instruction: RET
RET = Return from Subroutine (but its actually a JMPR)
Semantics: JMPR R7 ; PC = R7
Property of Penn Engineering 19
Subroutines in Assembly – Example: Multiply
Let’s take our “multiply” algorithm & make it a subroutine!
SUBROUTINE_MULTIPLY (A, B)
A=2
{
B=3
C=0 while (B > 0)
{
while (B > 0) C = C + A;
{ B = B – 1;
}
C = C + A; return C ;
B = B – 1; }
}
MAIN
c=SUBROUTINE_MULTIPLY (4, 5) ;

Surprisingly things won’t change much, we will mostly play with labels, JSR, RET instruction
Property of Penn Engineering 20
Subroutines in Assembly – Example: Multiply
0: CONST R0, #2 ; SETUP ARGUMENTS: A=2
1: CONST R1, #3 ; B=3
2: CONST R2, #0 ; C=0
3: JSR SUB_MULT ; CALL TO SUBROUTINE: C=A*B
4: CONST R0, #4 ; SETUP ARGUMENTS: A=4
5: CONST R1, #5 ; B=5
6: CONST R2, #0 ; C=0
7: JSR SUB_MULT ; CALL TO SUBROUTINE: C=A*B
8: JMP END ; jumps over subroutine
LINE #s In Hex

9: .FALIGN ; aligns the subroutine

A: SUB_MULT ; ARGS: R0(A), R1(B), RET: R2(C)
B: CMPI R1, #0 ; while loop
C: BRnz END_MULT JSR does the following:
D: ADD R2, R2, R0 ; C=C+A 1) R7=PC+1, so R7=3+1 = 4
E: ADD R1, R1, #-1 ; B=B-1 2) PC=<label> << 4, hence .FALIGN
F: BRnzp SUB_MULT ; end loop
10: END_MULT
11: RET ; end subroutine
12: END ; end program

Property of Penn Engineering 21

Subroutines in Assembly
– Effect of .FALIGN

JSR can only advance

PC to a multiple of 16
This gives JSR a
bigger range, since
It can only take an 11-bit
argument

Effect of .FALIGN
-placed “SUB_MULT”
at a multiple of 16
(x0010 is 16 in decimal)
Property of Penn Engineering 22
Arguments to Subroutines

For our subroutines, we’ll use the register file will hold:
Arguments

Return Values

Arguments:

Whatever is in the register file when we call our subroutine is considered an argument!
Return Values:

Whatever is in the register file when we return from our subroutine is considered a return value

Just remember not to use “R7” when authoring your subroutines!

Property of Penn Engineering 23

SECTION 4: Assembly Programming Example #3

WORKING WITH DATA MEMORY - THE BASICS

Property of Penn Engineering 24

Working with DATA Memory in LC-4 Assembly

ALU can only operate on #’s in the register File

• LC-4 Register File holds only 8 Numbers (in R0->R7)

How could we work with more than 8 numbers at a time?

• For example…what if we wanted to ADD up 10 numbers?
• We could use DATA memory to hold the extra #s
➢ One difficulty: ALU can only add #s in the register file
➢ Must get #s out of DATA memory into register file
– Just not all at once!
• How do we get numbers from DATA memory to register file?
➢ The LOAD Register instruction (LDR in ISA)

Property of Penn Engineering 25

LC-4 Memory Map
16-bit contents

0x0000
In the LC-4 Architecture Block Diagram:
Program
User Code Memory
• Program and Data Memory are separate
0x1FFF
Actually, there is only 1 memory:
0x2000
• The separation of Program & Data Mem
Data
➢ is purely logical for the ISA User Data Memory
• We partition it even further into 2 regions:
0x7FFF
➢ User region
0x8000
➢ Operating System Region
Program
User Region OS Code Memory
• Programs run by users (MS Word for ex) 0x9FFF
• Processes run in user mode with PSR[15]=0 are not 0xA000
allowed to access OS locations in the memory.
OS Data Data
Operating System Region + Device Memory Memory

• Processes run in OS mode with PSR[15]=1 0xFFFF

• Note: address x8200, first address of your OS

16-bit addresses Property of Penn Engineering 26

Working with DATA Memory in LC-4 Assembly
How do we add up more than 8 numbers?
Step 1: Load R0 with address x4000
Address Contents
CONST R0 x00 ; Load low byte
HICONST R0 x40 ; Load high byte x4000 1
x4001 2
R0 0
x4002 3
R1 0
x4003 4
R2 0
x4004 5
R3 0
x4005 6
R4 0
x4006 7
R5 0
x4007 8
R6 0
x4008 9
R7 0
x4009 10
Register File
DATA Memory
Property of Penn Engineering 27
Working with DATA Memory in LC-4 Assembly
How do we add up more than 8 numbers?
Step 1: Load R0 with address x4000
Address Contents
CONST R0 x00 ; Load low byte
HICONST R0 x40 ; Load high byte x4000 1
x4001 2
R0 x4000
x4002 3
R1 0
x4003 4
R2 0
x4004 5
R3 0
x4005 6
R0 – hold current R4 0
x4006 7
DATA Memory R5 0
Address (a pointer) x4007 8
R6 0
x4008 9
R7 0
x4009 10
Register File
DATA Memory
Property of Penn Engineering 28
Working with DATA Memory in LC-4 Assembly
How do we add up more than 8 numbers?
Step 2: Load R3 with DATA from x4000
Address Contents
LDR R3, R0, #0 ; offset 0
x4000 1
x4001 2
R0 x4000
x4002 3
R1 0
x4003 4
R2 0
x4004 5
R3 0
x4005 6
R0 – hold current R4 0
x4006 7
DATA Memory R5 0
Address (a pointer) x4007 8
R6 0
x4008 9
R7 0
x4009 10
Register File
DATA Memory
Property of Penn Engineering 29
Working with DATA Memory in LC-4 Assembly
How do we add up more than 8 numbers?
Step 2: Load R3 with DATA from x4000
Address Contents
LDR R3, R0, #0 ; offset 0
x4000 1
x4001 2
R0 x4000
x4002 3
R1 0
x4003 4
R2 0
x4004 5
R3 1
x4005 6
R0 – hold current R4 0
x4006 7
DATA Memory R5 0
Address (a pointer) x4007 8
R6 0
x4008 9
R3 – hold contents R7 0
x4009 10
of address pointed
to by R0
Register File
DATA Memory
Property of Penn Engineering 30
Working with DATA Memory in LC-4 Assembly
How do we add up more than 8 numbers?
Step 3: Use ALU to add 1st # to total
Address Contents
ADD R1, R1, R3 ; store total in R1
x4000 1
x4001 2
R0 x4000
x4002 3
R1 0
x4003 4
R1 R2 0
=1 x4004 5
R3 1
x4005 6
R4 0
ALU x4006 7
R5 0
x4007 8
R6 0
x4008 9
R1 – hold the R7 0
x4009 10
“running total”
Register File
DATA Memory
Property of Penn Engineering 31
Working with DATA Memory in LC-4 Assembly
How do we add up more than 8 numbers?
Step 4: Use ALU to increment REG holding
Address Contents
DATA Address
x4000 1
ADD R0, R0, #1
x4001 2
R0 x4000
x4002 3
R0 R1 1
= x4003 4
x4001 #1
R2 0
x4004 5
R3 1
ALU x4005 6
R4 0
x4006 7
R5 0
x4007 8
R6 0
x4008 9
R7 0
x4009 10
Register File
DATA Memory
Property of Penn Engineering 32
Working with DATA Memory in LC-4 Assembly
How do we add up more than 8 numbers?
Step 4: Use ALU to increment REG holding
Address Contents
DATA Address
x4000 1
ADD R0, R0, #1
x4001 2
R0 x4001
x4002 3
R0 R1 1
= x4003 4
x4001 #1
R2 0
x4004 5
R3 1
ALU x4005 6
R4 0
x4006 7
R5 0
x4007 8
R6 0
x4008 9
R7 0
x4009 10
Register File
DATA Memory
Property of Penn Engineering 33
Working with DATA Memory in LC-4 Assembly
How do we add up more than 8 numbers?
Repeat Step 2: Load R3 with DATA from x4001
Address Contents
LDR R3, R0, #0 ; offset 0
x4000 1
x4001 2
R0 x4001
x4002 3
R1 1
x4003 4
R2 0
x4004 5
R3 1
x4005 6
R4 0
x4006 7
R5 0
x4007 8
R6 0
x4008 9
R7 0
x4009 10
Register File
DATA Memory
Property of Penn Engineering 34
Working with DATA Memory in LC-4 Assembly
How do we add up more than 8 numbers?
Repeat Step 3: Use ALU to add 1st # to total
Address Contents
ADD R1, R1, R3 ; offset 0
x4000 1
x4001 2
R0 x4001
x4002 3
R1 1
x4003 4
R1 R2 0
=3 x4004 5
R3 2
x4005 6
R4 0
x4006 7
R5 0
x4007 8
R6 0
x4008 9
R7 0
x4009 10
Register File
DATA Memory
Property of Penn Engineering 35
Working with DATA Memory in LC-4 Assembly
How do we add up more than 8 numbers?
Repeat Step 4: Use ALU to increment REG
Address Contents
holding DATA Address
ADD R0, R0, #1 ; offset 0 And keep on going! x4000 1
x4001 2
R0 x4001
x4002 3
R0 R1 3
= x4003 4
x4002 #1
R2 0
x4004 5
R3 2
ALU x4005 6
R4 0
x4006 7
R5 0
x4007 8
R6 0
x4008 9
R7 0
x4009 10
Register File
DATA Memory
Property of Penn Engineering 36
A Word on “Pointers”
• This process of storing the address of a memory location in a variable (in this case a register) and then
using that address to access the memory location is very common in assembly

• This address variable is referred to as a pointer and we will see the concept reappear in C

• A pointer is a ‘variable’ that holds a memory address

• EX: R0=x4000 (R0 holds an address in data memory)

• R0 “points” to an address in data memory

• The act of using a pointer value to read or write a memory location

• Referred to as dereferencing the pointer

• EX: LDR R3, R0, #0

➢ Loads DATA from address pointed to by R0, into R3

➢ R0 will still hold address x4000
➢ Now R3 holds the “dereferenced data” pointed to by R0 x4000
Property of Penn Engineering 37
SECTION 4: Assembly Programming Example #3

WORKING WITH DATA MEMORY –

SETTING UP AN ARRAY

Property of Penn Engineering 38

Working with DATA Memory in LC-4 Assembly
Some outstanding questions in our Adding Program:
• How do we initially load DATA into DATA Memory?
• We’ll use three assembly “directives” (not instructions): .DATA .ADDR and .FILL
➢ Assembly Directives provide an indication to the assembler of where it should place various blocks of code or data

Assembly: Address Contents

.DATA x4000 1
.ADDR x4000 x4001 2
.FILL #1 x4002 3
.FILL #2
x4003 4
.FILL #3
.FILL #4 x4004 5
.FILL #5 … …
Property of Penn Engineering 39
LC-4 Assembly Directives

Assembly Directives provide an indication to the assembler of where it should place

various blocks of code or data
.DATA
• Next values are in DATA Memory
.ADDR
• Set current address to the specified value
.FILL IMM16
• Set value at the current address to the specified 16 bit value

Ultimately the assembly program gets assembled to an object file which is a specification
for how the machine memory should be set up

Property of Penn Engineering 40

Program to Add Up 10 Numbers (Assembly) – P1
.DATA ; lines below are DATA memory
.ADDR x4000 ; where to start in DATA memory

global_array ; label address x4000: global_array

.FILL #1 ; x4000
Address = 1 Data Mem Contents
.FILL #2 ; x4001 = 2
global_array 1
.FILL #3 ; x4002 = 3
x4001 2
.FILL #4 ; x4003 = 4
x4002 3
.FILL #5 ; x4004 = 5
.FILL #6 ; x4003 = 6
x4005 4
.FILL #7 ; x4004 = 7
x4006 5
.FILL #8 ; x4005 = 8
x4007 6
.FILL #9 ; x4006 = 9
x4008 7
.FILL #10 ; x4009
x4007 = 10 8
x4008 9
x4009 10
Property of Penn Engineering 41
SECTION 4: Assembly Programming Example #3

WORKING WITH DATA MEMORY –

USING A FOR LOOP

Property of Penn Engineering 42

Program to Add Up 10 Numbers (Flow Chart)
R0 = Starting
address where Set Running Total =0 Set Loop Counter =10
DATA is stored (R1=0) (R2=10)

T
Is Counter <= 0? END

F
Load # to add to total
R0 – holds current
(Load DATA from Address: R0
DATA Memory Address
into R3 )
R1 – hold running total
Update Running Total
R2 – # of items to add (Add R1 + R3, store in R1)

R3 – holds current Increment DATA address +1

DATA Memory Item (R0=R0+1)

Decrement Loop Counter -1

(R2=R2-1)
Property of Penn Engineering 43
What type of loop should we use?

What type of loop is best?

• We could use a while loop (we’ve done this already), but why not a for loop?
• We need a loop that repeats an exact # of times

➢ that’s exactly what a for loop is designed to do!

Initial value Condition What to do each

of counter to end loop time through loop

for (loop_count=10 ; loop_count>0 ; loop_count--) {

// load data from memory

// add loaded data to running total

// increment data memory address

Property of Penn Engineering 44

Program to Add Up 10 Numbers (Assembly) – P1
.DATA ; lines below are DATA memory
.ADDR x4000 ; where to start in DATA memory

global_array ; label address x4000: global_array

.FILL #1 ; x4000 = 1
.FILL #2 ; x4001 = 2
.FILL #3 ; x4002 = 3
.FILL #4 ; x4003 = 4
.FILL #5 ; x4004 = 5
.FILL #6 ; x4005 = 6
.FILL #7 ; x4006 = 7
.FILL #8 ; x4007 = 8
.FILL #9 ; x4008 = 9
.FILL #10 ; x4009 = 10

Property of Penn Engineering 45

Program to Add Up 10 Numbers (Assembly) – P2
.CODE ; lines below are Program Memory
.ADDR x0000 ; where to start in Program Memory

INIT
LEA R0, global_array ; load starting address of data to R0
; same as HICONST=x40, CONST=x00
CONST R1, #0 ; R1 = running total
CONST R2, #10 ; R2 = # of items to add (aka – loop counter)

FOR_LOOP
CMPI R2, #0 ; subtract 0 from the loop counter (R2), set NZP
BRnz END ; if R2 is <=0, done, jump to END
LDR R3, R0, #0 ; LOAD the data (at R0) into R3
ADD R1, R1, R3 ; update running total in R1
ADD R0, R0, #1 ; add 1 to address in R0
ADD R2, R2, #-1 ; reduce for loop counter by 1
JMP FOR_LOOP ; could also use: BRnzp FOR_LOOP
END

Property of Penn Engineering 46