1 of 58

CS61C: Great Ideas in Computer Architecture (aka Machine Structures)

Lecture 10: RISC-V Part 3: Control Flow, Bitwise Ops

Instructors: Lisa Yan, Justin Yokota

CS 61C

Spring 2024

2 of 58

Agenda

C Control Flow and goto
Reducing C with goto
RISC-V Control Flow
RISC-V Bitwise Operations

CS 61C

Spring 2024

3 of 58

Agenda

C Control Flow and goto
Reducing C with goto
RISC-V Control Flow
RISC-V Bitwise Operations

CS 61C

Spring 2024

4 of 58

RISC-V Guiding Philosophy

Goal of assembly: Create a set of instructions such that:

Each instruction represents a single computation or "step"

Ex. add adds two registers together, addi adds a register and an immediate

Every C program can be broken down into instructions

Ex. a = b+c+d; -> a = b+c; -> add x5 x6 x7� a = a+d; add x5 x5 x8

Each instruction works in isolation without depending on context

A program's behavior should depend only on memory, registers, and the current line being run

RISC: There should be as few unique instructions as possible

CS 61C

Spring 2024

5 of 58

Control Flow in C

In C, we run code one line at a time.
Most of the time, when we run a line of code, the next line that we will run is the line immediately afterwards
A few lines make it so that the next line isn't the line immediately afterwards, but somewhere else (we "jump" to another line of code).

int x = 5;�int y = 10;�int z = x+y;

Current Line

Next Line

CS 61C

Spring 2024

6 of 58

Control Flow in C

Lines in C that affect program flow:

If statements

if(cond) {� line;�}

line;

Current Line

Next Line if cond

Next Line if !cond

CS 61C

Spring 2024

7 of 58

Control Flow in C

Lines in C that affect program flow:

If statements

If-else statements

if(cond) {� line;�}�else {� line;�}�line;

Current Line

Next Line if cond

Next Line if !cond

CS 61C

Spring 2024

8 of 58

Control Flow in C

Lines in C that affect program flow:

If statements
While Loops

while(cond) {� line;� line;�}

Current Line

Next Line

CS 61C

Spring 2024

9 of 58

Control Flow in C

Lines in C that affect program flow:

If statements
While Loops

Do-While Loops

do {� line;� line;�} while(cond);�line;

Current Line

Next Line if cond

Next Line if !cond

CS 61C

Spring 2024

10 of 58

Control Flow in C

Lines in C that affect program flow:

If statements
While Loops
For Loops

for(line;cond;line) {� line;� line;�}�line;

Current Line (cond)

Next Line if !cond

Next Line if cond

CS 61C

Spring 2024

11 of 58

Control Flow in C

Lines in C that affect program flow:

If statements
While Loops
For Loops
Break/Continue

while(true) {� line;� break;�}�line;

Current Line

Next Line

CS 61C

Spring 2024

12 of 58

Control Flow in C

Lines in C that affect program flow:

If statements
While Loops
For Loops
Break/Continue
Function Calls

int foo(n) {� int a = 5;� return a+n;�}�...�line;�foo(5);�line;

Current Line

Next Line

CS 61C

Spring 2024

13 of 58

Control Flow in C

Lines in C that affect program flow:

If statements
While Loops
For Loops
Break/Continue
Function Calls

Both the function call, and the return!
Return line depends on which line called foo.
More on this Friday

int foo(n) {� int a = 5;� return a+n;�}�...�line;�foo(5);�line;�foo(5);�line;

Current Line

Next Line?

CS 61C

Spring 2024

14 of 58

New C operator: goto and Labels

A label is an identifier to a particular line of code

Doesn't count as a line of code itself; merely "points out" a particular line
Each label must have a unique name (like variable names)

The goto statement changes the next line to be run to the labelled line

The label can be either before or after the goto statement.

Target: line;� line;� line;� goto Target;� line;

Current Line

Next Line

CS 61C

Spring 2024

15 of 58

goto Example: Handling Mallocs

int* a = malloc(sizeof(int)*1000);

int* b = malloc(sizeof(int)*1000000);

int* c = malloc(sizeof(int)*1000000000);

FILE* d = fopen(filename);

CS 61C

Spring 2024

16 of 58

goto Example: Handling Mallocs

int* a = malloc(sizeof(int)*1000);

int* b = malloc(sizeof(int)*1000000);

int* c = malloc(sizeof(int)*1000000000);

FILE* d = fopen(filename);

Bad code: malloc can fail (returning NULL), and we should catch that before it causes a segfault

CS 61C

Spring 2024

17 of 58

goto Example: Handling Mallocs

int* a = malloc(sizeof(int)*1000);

if(a == NULL) allocation_failed();

int* b = malloc(sizeof(int)*1000000);

if(b == NULL) allocation_failed();

int* c = malloc(sizeof(int)*1000000000);

if(c == NULL) allocation_failed();

FILE* d = fopen(filename);

if(d == NULL) allocation_failed();

CS 61C

Spring 2024

18 of 58

goto Example: Handling Mallocs

int* a = malloc(sizeof(int)*1000);

if(a == NULL) allocation_failed();

int* b = malloc(sizeof(int)*1000000);

if(b == NULL) allocation_failed();

int* c = malloc(sizeof(int)*1000000000);

if(c == NULL) allocation_failed();

FILE* d = fopen(filename);

if(d == NULL) allocation_failed();

Bad code: leaks memory since a gets allocated but never freed.

CS 61C

Spring 2024

19 of 58

goto Example: Handling Mallocs

int* a = malloc(sizeof(int)*1000);

if(a == NULL) allocation_failed();

int* b = malloc(sizeof(int)*1000000);

if(b == NULL) {

free(a);

allocation_failed();

}

int* c = malloc(sizeof(int)*1000000000);

if(c == NULL) {

free(b);

free(a);

allocation_failed();

}

FILE* d = fopen(filename);

if(d == NULL) {

free(c);

free(b);

free(a);

allocation_failed();

}

CS 61C

Spring 2024

20 of 58

goto Example: Handling Mallocs

int* a = malloc(sizeof(int)*1000);

if(a == NULL) goto ErrorA;

int* b = malloc(sizeof(int)*1000000);

if(b == NULL) goto ErrorB;

int* c = malloc(sizeof(int)*1000000000);

if(c == NULL) goto ErrorC;

FILE* d = fopen(filename);

if(d == NULL) {

free(c);

ErrorC: free(b);

ErrorB: free(a);

ErrorA: allocation_failed();

}

CS 61C

Spring 2024

21 of 58

NEVER USE goto!!!!

goto has a tendency to create completely illegible code
Generally considered bad practice, except in very specific situations

Error handling
Jumping out of nested loops

Even with the above, there are other approaches that don't use goto
Nevertheless, goto is useful in that we can create any other control flow statements with just goto and conditional goto statements

CS 61C

Spring 2024

22 of 58

Agenda

C Control Flow and goto
Reducing C with goto
RISC-V Control Flow
RISC-V Bitwise Operations

line;

AfterIf: line;

CS 61C

Spring 2024

Reducing C with goto: For

startline;

while(cond) {

line;

incline;

}

line;

CS 61C

Spring 2024

34 of 58

Reducing C with goto: For

startline;

Loop: if(cond) goto AfterLoop

line;

incline;

goto Loop

AfterLoop: line;

CS 61C

Spring 2024

35 of 58

Agenda

C Control Flow and goto
Reducing C with goto
RISC-V Control Flow
RISC-V Bitwise Operations

CS 61C

Spring 2024

36 of 58

RISC-V Control Flow Operations

Like in C, RISC-V allows you to write labels to signify particular lines of code
RISC-V has instructions for both conditional and unconditional jumps:

j Label

Jumps to the specified label
Technically a pseudoinstruction; more on this Friday

Branch instructions:

General format: bxx rs1 rs2 Label
Jumps to the specified Label if the condition is met
If the condition is not met, just moves to the next line

CS 61C

Spring 2024

37 of 58

RISC-V Control Flow Operations

List of branch instructions:

beq rs1 rs2 Label: Branch if EQual
bne rs1 rs2 Label: Branch if Not Equal
blt rs1 rs2 Label: Branch if Less Than (signed) (rs1 < rs2)
bge rs1 rs2 Label: Branch if Greater or Equal (signed)
bltu rs1 rs2 Label: Branch if Less Than (unsigned)
bgeu rs1 rs2 Label: Branch if Greater or Equal (unsigned)
Note that bgt, bgtu, ble, and bleu are pseudoinstructions (can make them by reversing inputs of existing instructions)

CS 61C

Spring 2024

38 of 58

RISC-V Control Flow Operations: Example

int a = 0;

for(int i = 0; i < 10; i++) {

if(i == 7) {

break;

}

a = a + i;

}

a = a + 50;

CS 61C

Spring 2024

39 of 58

RISC-V Control Flow Operations: Example

int a = 0;

for(int i = 0; i < 10; i++) {

if(i == 7) goto End;

a = a + i;

}

End: a = a + 50;

CS 61C

Spring 2024

40 of 58

RISC-V Control Flow Operations: Example

int a = 0;

int i = 0;

Loop: if(i >= 10) goto End;

if(i == 7) goto End;

a = a + i;

i = i + 1;

goto Loop;

End: a = a + 50;

CS 61C

Spring 2024

41 of 58

RISC-V Control Flow Operations: Example

int a = 0;

int i = 0;

Loop:

int j = 10;

if(i >= j) goto End;

j = 7;

if(i == j) goto End;

a = a + i;

i = i + 1;

goto Loop;

End: a = a + 50;

CS 61C

Spring 2024

42 of 58

RISC-V Control Flow Operations: Example

li x10 0 #int a = 0;

li x5 0 #int i = 0;

Loop:

li x6 10 #int j = 10;

bge x5 x6 End #if(i >= j) goto End;

li x6 7 #j = 7;

beq x5 x6 End #if(i == j) goto End;

add x10 x10 x5 #a = a + i;

addi x5 x5 1 #i = i + 1;

j Loop #goto Loop;

End: addi x10 x10 50 #a = a + 50;

CS 61C

Spring 2024

43 of 58

Agenda

C Control Flow and goto
Reducing C with goto
RISC-V Control Flow
RISC-V Bitwise Operations

CS 61C

Spring 2024

44 of 58

Review: Bitwise Operations in C

Bitwise AND, OR, XOR, and NOT

Perform the operation on the binary one bit at a time
Ex. 0b1001 | 0b0111 = 0b1111
Ex. 0b1001 & 0b0111 = 0b0001
Ex. 0b1001 ^ 0b0111 = 0b1110
Ex. ~0b1001 = 0b0110

Left and Right Shift

Shift the bits of the number left/right, then fill the remaining bits
Ex. 0b0001 << 3 = 0b1000 = 8
Ex. 0b1011 >> 2 = 0b0010 = 2

CS 61C

Spring 2024

45 of 58

Review: Bitwise Operations in C

Shifts have numerical equivalents in math

Left Shift by n -> Multiply by 2ⁿ
Right Shift by n -> (Floor) Divide by 2ⁿ

For left shifts, we always fill the new bits with 0s

For right shifts, dividing an unsigned number should fill the bits with 0s

But right-shifting a signed number shouldn't fill with 0s always

Ex. 0b1000 0010 = -126 in 8 bits. If we right-shift by 1 and fill with 0s, we get 0b0100 0001 = 65. But if we right-shift by 1 and fill with the sign bit, we get 0b1100 0001 = -63 = -126/2

CS 61C

Spring 2024

46 of 58

Review: Bitwise Operations in C

Logical Left Shift

Shift left, add zeros
Same as multiplication by a power of 2

Logical Right Shift

Shift right, zero-extend
Same as dividing an unsigned number by a power of 2

Arithmetic Right Shift

Shift right, sign-extend
NOT the same as dividing a signed number by a power of 2

C standard is to round towards zero, while right-shift always rounds down

CS 61C

Spring 2024

47 of 58

Arithmetic Operations in RISC-V

RISC-V has many arithmetic operations:

add rd rs1 rs2: Add
sub rd rs1 rs2: Subtract
and rd rs1 rs2: Bitwise AND
or rd rs1 rs2: Bitwise OR
xor rd rs1 rs2: Bitwise XOR
sll rd rs1 rs2: Shift Left Logical
srl rd rs1 rs2: Shift Right Logical
sra rd rs1 rs2: Shift Right Arithmetic

Each one has a corresponding immediate version (ex. xori rd rs1 imm runs a bitwise XOR on a register and immediate)

CS 61C

Spring 2024

48 of 58

Arithmetic Operations that AREN'T in RISC-V

There's a few notable omissions in this list:

Bitwise NOT

Exists as a pseudoinstruction; can be run by doing a bitwise XOR with 0xFFFF FFFF = -1

Multiplication, Division, Mod

Circuit is significantly more complicated than bitwise ops or addition.
Exists as an extension of RISC-V, but is not by itself in base RISC-V
For multiplying/dividing by powers of 2, we can use shifts instead

Float addition/subtraction/etc.

Much more complicated circuit, so also exists as an extension.

CS 61C

Spring 2024

49 of 58

Practice: Bitwise Operations

What is in register x12 after the following instructions?

li x10 0x34FF

slli x12 x10 0x10

srli x12 x12 0x08

and x12 x12 x10

CS 61C

Spring 2024

50 of 58

CS 61C

Spring 2024

51 of 58

srli x12 x12 0x08

and x12 x12 x10

Register	Value
x10	0x0000 34FF
x12	0x0000 3400

CS 61C

Spring 2024

58 of 58

Summary: RISC-V so far

Arithmetic

Immediate

addi
andi
ori
xori
slli
srli
srai
li (pseudo)

Loads/Stores

Branches/Jumps

beq
bne
bge
blt
bgeu
bltu
j (pseudo)

CS 61C

Spring 2024