Chapter 5
The LC-3
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Instruction Set Architecture
ISA = All of the programmer-visible components and operations of the computer
• memory organization
address space — how may locations can be addressed? addressibility — how many bits per location?
• register set
how many? what size? how are they used?
• instruction set opcodes
data types
addressing modes
ISA provides all information needed for someone that wants to write a program in machine language
(or translate from a high-level language to machine language).
5-2
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
LC-3 Overview: Memory and Registers
Memory
• address space: 216 locations (16-bit addresses) • addressability: 16 bits
Registers
• temporary storage, accessed in a single machine cycle accessing memory generally takes longer than a single cycle
• eight general-purpose registers: R0 – R7
each 16 bits wide
how many bits to uniquely identify a register?
• other registers
not directly addressible, but used by (and affected by)
instructions
PC (program counter), condition codes
5-3
Opcodes
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
LC-3 Overview: Instruction Set
• 15 opcodes
• Operate instructions: ADD, AND, NOT
• Data movement instructions: LD, LDI, LDR, LEA, ST, STR, STI • Control instructions: BR, JSR/JSRR, JMP, RTI, TRAP
• some opcodes set/clear condition codes, based on result:
N = negative, Z = zero, P = positive (> 0) Data Types
• 16-bit 2’s complement integer
Addressing Modes
• How is the location of an operand specified?
• non-memory addresses: immediate, register
• memory addresses: PC-relative, indirect, base+offset
5-4
Operate Instructions
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Only three operations: ADD, AND, NOT
Source and destination operands are registers
• These instructions do not reference memory.
• ADD and AND can use “immediate” mode,
where one operand is hard-wired into the instruction.
Will show dataflow diagram with each instruction.
• illustrates when and where data moves to accomplish the desired operation
5-5
NOT (Register)
Note: Src and Dst
could be the same register.
5-6
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
NOT Dst, Src
ADD/AND (Register)
this zero means “register mode”
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
ADD Dst, Src1, Src2 AND Dst, Src1, Src2
5-7
ADD/AND (Immediate)
this one means “immediate mode”
Note: Immediate field is sign-extended.
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
ADD Dst, Src1, Imm5 AND Dst, Src1, Imm5
Immediate Values -> x12 for Hex values, decimal values #12
5-8
LC-3 Data Path Revisited
Filled arrow
= info to be processed.
Unfilled arrow
= control signal.
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
5-9
With only ADD, AND, NOT… • How do we subtract?
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Using Operate Instructions
• HowdoweOR?
• How do we copy from one register to another? • How do we initialize a register to zero?
5-10
Control Instructions
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Used to alter the sequence of instructions (by changing the Program Counter)
Conditional Branch
• branch is taken if a specified condition is true signed offset is added to PC to yield new PC
• else, the branch is not taken
PC is not changed, points to the next sequential instruction
Unconditional Branch (or Jump)
• always changes the PC
TRAP
• changes PC to the address of an OS “service routine”
• routine will return control to the next instruction (after TRAP)
5-11
Condition Codes
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
LC-3 has three condition code registers: N — negative
Z — zero
P — positive (greater than zero)
Set by any instruction that writes a value to a register (ADD, AND, NOT, LD, LDR, LDI, LEA)
Exactly one will be set at all times
• Based on the last instruction that altered a register
5-12
Branch Instruction
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Branch specifies one or more condition codes. If the set bit is specified, the branch is taken.
• PC-relative addressing:
target address is made by adding signed offset (IR[8:0]) to current PC.
• Note: PC has already been incremented by FETCH stage. • Note: Target must be within 256 words of BR instruction.
If the branch is not taken,
the next sequential instruction is executed.
5-13
BR (PC-Relative)
What happens if bits [11:9] are all zero? All one?
5-14
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
BRx LABEL (PCoffset9)
LC-3 Data Path Revisited
Filled arrow
= info to be processed.
Unfilled arrow
= control signal.
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
5-15
Two basic constructs: • Conditional (If, If-Else)
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
How are Branches Used?
Alter the flow of the program,
based on some programmer-specified condition, evaluated at execution time.
choose whether or not to execute instruction sequence • Iterative (Loops)
execute instruction sequence multiple times
5-16
Conditional
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
If If-Else
“hammock” “diamond”
5-17
Code for Conditional
True Test Condition
False
Subtask 1
Subtask 2
B0000? C Subtask 1
Next Subtask
Unconditional branch to Next Subtask
D Next Subtask
PC offset to address D
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Assumes all addresses are close enough that PC-relative branch can be used.
6-18
Exact bits depend on condition being tested
Instruction
PC offset to address C
A
Generate Condition
C
0000 111 D
Subtask 2
Iterative
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
While Loop Do-While Loop
5-19
Code for Iteration
Test Condition
False
Subtask
Subtask
Next Subtask
Unconditional branch to retest condition
PC offset to address A
True
B
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Exact bits depend on condition being tested
Instruction
PC offset to address C
Assumes all addresses are close enough that PC-relative branch can be used.
6-20
A
Generate Condition
C
Next Subtask
0000 ? C
0000 111 A
JMP (Register)
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Jump is an unconditional branch — always taken. • Target address is the contents of a register.
• Allows any target address.
JMP Rbase
5-21
TRAP
TRAP trapvect8
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Calls a service routine, identified by 8-bit “trap vector.”
vector routine
x23 x21 x25
input a character from the keyboard (IN) output a character to the monitor (OUT) halt the program (HALT)
When routine is done,
PC is set to the instruction following TRAP.
(We’ll talk about how this works later.) Warning: TRAP changes R7.
5-22
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Data Movement Instructions
Load — read data from memory to register • LD: PC-relative mode
• LDR: base+offset mode
• LDI: indirect mode
Store — write data from register to memory • ST: PC-relative mode
• STR: base+offset mode
• STI: indirect mode
Load effective address — compute address, save in register
• LEA: immediate mode
• does not access memory
5-23
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
PC-Relative Addressing Mode
Want to specify address directly in the instruction
• But an address is 16 bits, and so is an instruction!
• After subtracting 4 bits for opcode
and 3 bits for register, we have 9 bits available for address.
Solution:
• Use the 9 bits as a signed offset from the current PC.
9 bits: 256 offset 255 CanformanyaddressX,suchthat: PC256XPC255
Remember that PC is incremented as part of the FETCH phase; This is done before the EVALUATE ADDRESS stage.
5-24
LD (PC-Relative)
LD Dst, LABEL (PCoffset9)
Note: The ALU is shown performing the add, but there may be a separate adder for address generation.
5-25
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
ST (PC-Relative)
ST Src, LABEL (PCoffset9)
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
5-26
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Base + Offset Addressing Mode
With PC-relative mode, can only address data within 256 words of the instruction.
• What about the rest of memory? Solution #1:
• Use the value in a register to generate a full 16-bit address.
4 bits for opcode, 3 for src/dest register,
3 bits for base register — remaining 6 bits are used as a signed offset.
• Offset is sign-extended before adding to base register.
5-27
LDR (Base+Offset)
LDR Dst, BaseR LABEL (offset6)
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
5-28
STR (Base+Offset)
STR Src, BaseR LABEL (offset6)
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
5-29
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Indirect Addressing Mode
With PC-relative mode, can only address data within 256 words of the instruction.
• What about the rest of memory? Solution #3:
• Read address from memory location, then load/store to that address.
First address is generated from PC and IR
(just like PC-relative addressing), then
content of that address is used as target for load/store.
5-30
LDI (Indirect)
LDI Dst, LABEL (PCoffset9)
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
5-31
STI (Indirect)
STI Src, LABEL (PCoffset9)
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
5-32
Load Effective Address
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Computes address like PC-relative (PC plus signed offset) and stores the result into a register.
Note: The address is stored in the register, not the contents of the memory location.
5-33
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
LEA (Immediate) LEA Dst LABEL (PCoffset9)
5-34
LC-3 Data Path Revisited
Filled arrow
= info to be processed.
Unfilled arrow
= control signal.
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
5-35
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Using Branch and Load Instructions
Compute sum of 12 integers.
Numbers start at location x3100. Program starts at location x3000.
R1 x3100 R3 0 R2 12
R2=0?
R4 M[R1] R3 R3+R4 R1 R1+1 R2 R2-1
NO YES
5-36
Sample Program
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Address Instruction
Comments
x3000 1110001011111111 x3001 0101011011100000 x3002 0101010010100000 x3003 0001010010101100 x3004 0000010000000101 x3005 0110100001000000 x3006 0001011011000001 x3007 0001001001100001 X3008 0001010010111111 x3009 0000111111111010
R1x3100(PC+0xFF) R3 0
R2 0
R2 12 IfZ,gotox300A(PC+5) LoadnextvaluetoR4 Add to R3 IncrementR1(pointer) DecrementR2(counter) Goto x3004 (PC-6)
5-37
Another Example
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Count the occurrences of a character in a memory region
• Program begins at location x3000
• Read character from keyboard
• Load each character from a “file”
File is a sequence of memory locations
Starting address of file is stored in the memory location immediately after the program
• If file character equals input character, increment counter
• End of file is indicated by a special ASCII value: EOT (x04)
• At the end, print the number of characters and halt (assume there will be less than 10 occurrences of the character)
A special character used to indicate the end of a sequence is often called a sentinel.
• Usefulwhenyoudon’tknowaheadoftimehowmanytimes to execute a loop.
5-38
Flow Chart
Count = 0
Convert count to ASCII character
(R2 = 0)
YES (R1 ?= EOT)
Ptr = 1st file character
NO
(R3 = M[x3012])
Input char from keybd
(TRAP x23)
Load char from file
(R2 = R2 + 1)
(R1 = M[R3])
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
YES
Match? NO (R1 ?= R0)
(TRAP x21)
Incr Count
(TRAP x25)
Done?
Load next char from file
(R3 = R3 + 1, R1 = M[R3])
(R0 = x30, R0 = R2 + R0)
Print count
HALT
5-39
Program (1 of 2)
Address
Instruction
Comments
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
x3000 0101010010100000
x3001 0010011000010000
x3002 1111000000100011
x3003 0110001011000000
x3004 0001100001111100
x3005 0000010000001000
x3006 1001001001111111
x3007 0001001001100001
X3008 0001001001000000 x3009 0000101000000001
R2 0 (counter) R3 M[x3102] (ptr) Input to R0 (TRAP x23) R1 M[R3]
R4 R1 – 4 (EOT) If Z, goto x300E
R1 NOT R1
R1 R1 + 1
R1 R1 + R0
If N or P, goto x300B
5-40
Program (2 of 2)
Address
Instruction
Comments
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
x300A 0001010010100001
x300B 0001011011100001
x300C 0110001011000000
x300D 0000111111110110
x300E 0010000000000100
x300F 0001000000000010
x3010 1111000000100001
x3011 1111000000100101
X3012 Starting Address of File x3013 0000000000110000
R2 R2 + 1
R3 R3 + 1
R1 M[R3] Goto x3004
R0 M[x3013] R0 R0 + R2 Print R0 (TRAP x21) HALT (TRAP x25)
ASCII x30 (‘0’)
5-41