x86 Programming III CSE 351 Autumn 2016
Aside: Registers are Inside the Processor
Processor
Control
Datapath
PC
Registers
Arithmetic & Logic Unit
(ALU)
Memory
Input
Output
Bytes
Enable?
Read/Write
Address
Write Data
Read Data
Processor-Memory Interface
I/O-Memory Interfaces
Program
Data
1
CMPT 295
L06 – RISC V – I
RISC V Integer Registers – 32 bits wide
2
CMPT 295
L06 – RISC V – I
Names are largely arbitrary, reasons behind them are not super relevant to us
But there are conventions about how they are used
One is particularly important to not misuse: %sp
Stack pointer; we’ll get to this when we talk about procedures
Each is 4-bytes wide
RISCV Instructions (1/2)
Instruction Syntax is rigid:
op dst, src1, src2
1 operator, 3 operands
op = operation name (“operator”)
dst = register getting result (“destination”)
src1 = first register for operation (“source 1”)
src2 = second register for operation (“source 2”)
Keep hardware simple via regularity
3
CMPT 295
L06 – RISC V – I
RISCV Instructions Example
Your very first instructions!
(assume here that the variables a, b, and c are assigned to registers s1, s2, and s3, respectively)
Integer Addition (add)
C: a = b + c
RISCV: add s1, s2, s3
Integer Subtraction (sub)
C: a = b – c
RISCV: sub s1, s2, s3
4
CMPT 295
L06 – RISC V – I
RISCV Instructions Example
5
Ordering of instructions matters (must follow order of operations)
Utilize temporary registers
Suppose a → s0,b → s1,c → s2,d → s3 and e → s4. Convert the following C statement to RISCV:
a = (b + c) – (d + e);
add t1, s3, s4
add t2, s1, s2
sub s0, t2, t1
CMPT 295
L06 – RISC V – I
add s0, s1, s2
add t0, s3, s4
sub s0, s0, t0
Suppose a -> s0, b->s1, c-> s2, d->s3 and e->s4. Convert the following C statement to RISCV:
a = (b + c) – (d + e);
add t1, s3, s4
add t2, s1, s2
sub s0, t2, t1
5
Three Basic Kinds of Instructions
Transfer data between memory and register
Load data from memory into register
%reg = Mem[address]
Store register data into memory
Mem[address] = %reg
Perform arithmetic operation on register or memory data
c = a + b; z = x << y; i = h & g;
Control flow: what instruction to execute next
Unconditional jumps to/from procedures
Conditional branches
6
Remember: Memory is indexed just like an array of bytes!
CMPT 295
L06 – RISC V - I
Immediates
Numerical constants are called immediates
Separate instruction syntax for immediates:
opi dst, src, imm
Operation names end with ‘i’, replace 2nd source register with an immediate
Example Uses:
addi s1, s2, 5 # a=b+5
addi s3, s3, 1 # c++
Why no subi instruction?
7
CMPT 295
L06 – RISC V - I
Goal of RISC is to minimize instruction set. subi dst, src, imm = addi dst, src, -imm.
7
Load from Memory to Register
C code
int A[100];
g = h + A[3];
Using Load Word (lw) in RISC-V:
lw x10,12(x15) # Reg x10 gets A[3]
add x11,x12,x10 # g = h + A[3]
Note: x15 – base register (pointer to A[0])
12 – offset in bytes
Offset must be a constant known at assembly time
Data flow
8
CMPT 295
L06 – RISC V - I
8
Store from Register to Memory
C code
int A[100];
A[10] = h + A[3];
Using Store Word (sw) in RISC-V:
lw x10,12(x15) # Temp reg x10 gets A[3]
add x10,x12,x10 # Temp reg x10 gets h + A[3]
sw x10,40(x15) # A[10] = h + A[3]
Note: x15 – base register (pointer)
12,40 – offsets in bytes
x15+12 and x15+40 must be multiples of 4
Data flow
9
CMPT 295
L06 – RISC V - I
80 – 5 (Clicker) – 3 (News/Administrativia) = 72 (36 slides max)
Clicker at 20 (half+)
9
Decision Making Instructions
Branch If Equal (beq)
beq reg1,reg2,label
If value in reg1 = value in reg2, go to label
Branch If Not Equal (bne)
bne reg1,reg2,label
If value in reg1 ≠ value in reg2, go to label
Jump (j)
j label
Unconditional jump to label
10
CMPT 295
L06 – RISC V - I
Branching on Conditions other than (Not) Equal
Set Less Than (slt)
slt dst, reg1,reg2
If value in reg1 < value in reg2, dst = 1, else 0
Set Less Than Immediate (slti)
slti dst, reg1,imm
If value in reg1 < imm, dst = 1, else 0
11
CMPT 295
L06 – RISC V - I
11
Branching on Conditions other than (Not) Equal
Branch Less Than (blt)
blt reg1,reg2, label
If value in reg1 < value in reg2, go to label
Branch Greater Than or Equal (bge)
bge reg1,reg2, label
If value in reg1 >= value in reg2, go to label
12
CMPT 295
L06 – RISC V – I
12
“And in Conclusion…”
Memory is byte-addressable, but lw and sw access one word at a time.
A pointer (used by lw and sw) is just a memory address, we can add to it or subtract from it (using offset).
A Decision allows us to decide what to execute at run-time rather than compile-time.
C Decisions are made using conditional statements within if, while, do while, for.
RISC-V Decision making instructions are the conditional branches: beq and bne.
New Instructions:
lw, sw, lb, sb, lbu, beq, bne, blt, bltu, bge, j
13
CMPT 295
L06 – RISC V – I
Breaking Down the If Else
C Code:
if(i
15
CMPT 295
L06 – RISC V – I
15
Breaking Down the If Else
C Code:
if(i
18
# t0 = *p
# *q = t0
# p = p + 1
# q = q + 1
# if *p==0, go to Exit
# go to Loop
CMPT 295
L06 – RISC V – I
C to RISCV Practice
Fill in lines:
# copy String p to q
# p→s0, q→s1 (pointers)
Loop: lb $t0,0($s0) # t0 = *p
sb $t0,0($s1) # *q = t0
addi $s0,$s0,1 # p = p + 1
addi $s1,$s1,1 # q = q + 1
beq $t0,$0,Exit # if *p==0, go to Exit
j Loop # go to Loop
Exit: # N chars in p => N*6 instructions
19
lb t0,0(s0)
sb t0,0(s1)
addi s0,s0,1
addi s1,s1,1
beq t0,0,Exit
CMPT 295
L06 – RISC V – I
C to RISCV Practice
Finished code:
# copy String p to q
# p→$s0, q→$s1 (pointers)
Loop: lb t0,0(s0) # t0 = *p
sb t0,0(s1) # *q = t0
addi s0,s0,1 # p = p + 1
addi s1,s1,1 # q = q + 1
beq t0,x0,Exit # if *p==0, go to Exit
j Loop # go to Loop
Exit: # N chars in p => N*6 instructions
20
CMPT 295
L06 – RISC V – I
Is this the only way to write out this function? Of course not.
20
C to RISCV Practice
Alternate code using bne:
# copy String p to q
# p→s0, q→s1 (pointers)
Loop: lb t0,0(s0) # t0 = *p
sb t0,0(s1) # *q = t0
addi s0,s0,1 # p = p + 1
addi s1,s1,1 # q = q + 1
bne t0,x0,Loop # if *p!=0, go to Loop
# N chars in p => N*5 instructions
21
CMPT 295
L06 – RISC V – I
Used fewer instructions!
Instead of “exit when equal to zero”, we are now using “loop when not equal to zero.”
21
RISCV Bitwise Instructions
Note: a→s1, b→s2, c→s3
22
Instruction C RISCV
And a = b & c; and s1,s2,s3
And Immediate a = b & 0x1; andi s1,s2,0x1
Or a = b | c; or s1,s2,s3
Or Immediate a = b | 0x5; ori s1,s2,0x5
Exclusive Or a = b ^ c; xor s1,s2,s3
Exclusive Or Immediate a = b ^ 0xF; xori s1,s2,0xF
CMPT 295
L06 – RISC V – I
Shifting Instructions
23
Instruction Name RISCV
Shift Left Logical sll s1,s2,s3
Shift Left Logical Imm slli s1,s2,imm
Shift Right Logical srl s1,s2,s3
Shift Right Logical Imm srli s1,s2,imm
Shift Right Arithmetic sra s1,s2,s3
Shift Right Arithmetic Imm srai s1,s2,imm
When using immediate, only values 0-31 are practical
When using variable, only lowest 5 bits are used (read as unsigned)
CMPT 295
L06 – RISC V – I
Shifting Instructions
Example 1:
# lb using lw: lb s1,1(s0)
lw s1,0(s0) # get word
andi s1,s1,0xFF00 # get 2nd byte
srli s1,s1,8 # shift into lowest
24
CMPT 295
L06 – RISC V – I
Shifting Instructions
Example 2:
# sb using sw: sb s1,3(s0)
lw t0,0(s0) # get current word
andi t0,t0,0xFFFFFF # zero top byte
slli t1,s1,24 # shift into highest
or t0,t0,t1 # combine
sw t0,0(s0) # store back
25
CMPT 295
L06 – RISC V – I
Switch Statement Example
Multiple case labels
Here: 5 & 6
Fall through cases
Here: 2
Missing cases
Here: 4
Implemented with:
Jump table
Indirect jump instruction
26
long switch_ex
(long x, long y, long z)
{
long w = 1;
switch (x) {
case 1:
w = y*z;
break;
case 2:
w = y/z;
/* Fall Through */
case 3:
w += z;
break;
case 5:
case 6:
w -= z;
break;
default:
w = 2;
}
return w;
}
CMPT 295
L06 – RISC V – I
Jump Table Structure
27
Code
Block 0
Targ0:
Code
Block 1
Targ1:
Code
Block 2
Targ2:
Code
Block n–1
Targn-1:
•
•
•
Targ0
Targ1
Targ2
Targn-1
•
•
•
JTab:
target = JTab[x];
goto target;
switch (x) {
case val_0:
Block 0
case val_1:
Block 1
• • •
case val_n-1:
Block n–1
}
Switch Form
Approximate Translation
Jump Table
Jump Targets
CMPT 295
L06 – RISC V – I
Jump Table Structure
28
switch (x) {
case 1:
break;
case 2:
case 3:
break;
case 5:
case 6:
break;
default:
}
Code
Blocks
Memory
Use the jump table when x 6:
if (x <= 6)
target = JTab[x];
goto target;
else
goto default;
C code:
0
1
2
3
4
5
6
Jump
Table
CMPT 295
L06 – RISC V - I
.section .rodata
.align 8
.L4:
.quad .L8 # x = 0
.quad .L3 # x = 1
.quad .L5 # x = 2
.quad .L9 # x = 3
.quad .L8 # x = 4
.quad .L7 # x = 5
.quad .L7 # x = 6
Jump Table
29
Jump table
switch(x) {
case 1: // .L3
w = y*z;
break;
case 2: // .L5
w = y/z;
/* Fall Through */
case 3: // .L9
w += z;
break;
case 5:
case 6: // .L7
w -= z;
break;
default: // .L8
w = 2;
}
declaring data, not instructions
8-byte memory alignment
this data is 64-bits wide
CMPT 295
L06 – RISC V - I
.rodata – read-only data section
Handling Fall-Through
30
long w = 1;
. . .
switch (x) {
. . .
case 2: // .L5
w = y/z;
/* Fall Through */
case 3: // .L9
w += z;
break;
. . .
}
case 3:
w = 1;
case 2:
w = y/z;
goto merge;
merge:
w += z;
More complicated choice than “just fall-through” forced by “migration” of w = 1;
Example compilation trade-off
CMPT 295
L06 – RISC V - I