9.3 hello.c end to end: -O0, -O2 and the cycle count

The same C, twice

hello.c is small. It prints a string, then i * i and a newline for i from 0 to 4. Here it is beside its two compilations. Click a C line to see what each compiler made of it.

main of hello.c at -O0 (33 words) and at -O2 (30 words)

carolyne_ref/programs/hello.c; hello_o0.dump bfc0018c–bfc0020c; hello_o2.dump bfc000b0–bfc00124

hello.c

1int main(void) {
2  print_str("hello from carolyne\n");
3  for (i = 0;
4       i < 5;
5       i++) {
6    print_int(i * i);
7    print_char('\n');
8  }
9  return 0;
10}

-O0

bfc0018caddiu sp,sp,-32
bfc00190sw    ra,28(sp)
bfc00194sw    s8,24(sp)
bfc00198move  s8,sp
bfc0019clui   v0,0x1000
bfc001a0addiu a0,v0,0
bfc001a4jal   bfc00124 <print_str>
bfc001a8nop
bfc001acsw    zero,16(s8)
bfc001b0b     bfc001e4 <main+0x58>
bfc001b4nop
bfc001b8lw    v0,16(s8)
bfc001bcmul   v0,v0,v0
bfc001c0move  a0,v0
bfc001c4jal   bfc000ec <print_int>
bfc001c8nop
bfc001ccli    a0,10
bfc001d0jal   bfc000b0 <print_char>
bfc001d4nop
bfc001d8lw    v0,16(s8)
bfc001dcaddiu v0,v0,1
bfc001e0sw    v0,16(s8)
bfc001e4lw    v0,16(s8)
bfc001e8slti  v0,v0,5
bfc001ecbnez  v0,bfc001b8 <main+0x2c>
bfc001f0nop
bfc001f4move  v0,zero
bfc001f8move  sp,s8
bfc001fclw    ra,28(sp)
bfc00200lw    s8,24(sp)
bfc00204addiu sp,sp,32
bfc00208jr    ra
bfc0020cnop

-O2

bfc000b0lui   v1,0x1000
bfc000b4li    v0,104
bfc000b8addiu v1,v1,0
bfc000bclui   a0,0x1000
bfc000c0addiu v1,v1,1
bfc000c4andi  v0,v0,0xff
bfc000c8sw    v0,16368(a0)
bfc000ccaddiu a1,a0,16368
bfc000d0lb    v0,0(v1)
bfc000d4bnez  v0,bfc000c0 <main+0x10>
bfc000d8nop
bfc000dclui   a0,0x1000
bfc000e0li    v1,10
bfc000e4li    v0,1
bfc000e8li    a2,4
bfc000ecsw    zero,16372(a0)
bfc000f0sw    v1,0(a1)
bfc000f4sw    v0,16372(a0)
bfc000f8move  v0,zero
bfc000fcsw    v1,0(a1)
bfc00100sw    a2,16372(a0)
bfc00104li    a2,9
bfc00108sw    v1,0(a1)
bfc0010csw    a2,16372(a0)
bfc00110li    a2,16
bfc00114sw    v1,0(a1)
bfc00118sw    a2,16372(a0)
bfc0011csw    v1,0(a1)
bfc00120jr    ra
bfc00124nop

Click any highlighted line to see it light up in the other listing, and read what it does.

What to notice

At -O0, i is read from the stack three times per round and i * i is a real mul. Each print is a jal to a real function. At -O2 there is no mul, no jal, no frame and no i. The string loop is the only loop left, and even its first character was loaded at compile time.

What the optimiser did, in four words

The is a promise about how much the compiler may rearrange. At -O0 it keeps the shape of your C, statement by statement. At -O2 it keeps only the meaning. Four changes did most of the work here.

removed the three calls. print_char became one sw to the putchar door. print_str became the six-instruction loop. Because no call remained, main became a leaf, and a leaf needs no frame (§6.2).

removed the for. The compiler knew the loop runs exactly five times, so it wrote the body five times. No i, no slti, no bnez.

removed the mul. With the loop unrolled, every i * i had known operands. So the program contains 0, 1, 4, 9 and 16 as li constants.

The fourth is smaller. The compiler noticed that both doors sit within 16 bits of 0x10000000. One lui a0,0x1000 serves every print, and each door is a base plus offset: 16368(a0) and 16372(a0).

Watch the -O2 main run

hello.c at -O2: the whole program is one leaf main

What does the optimised main actually do, instruction by instruction?

program (address · word · instruction)

PC →	0xbfc000b0	0x3c031000	main:lui $v1,0x1000
	0xbfc000b4	0x24020068	li $v0,104
	0xbfc000b8	0x24630000	addiu $v1,$v1,0
	0xbfc000bc	0x3c041000	lui $a0,0x1000
	0xbfc000c0	0x24630001	loop:addiu $v1,$v1,1
	0xbfc000c4	0x304200ff	andi $v0,$v0,0xff
	0xbfc000c8	0xac823ff0	sw $v0,16368($a0)
	0xbfc000cc	0x24853ff0	addiu $a1,$a0,16368
	0xbfc000d0	0x80620000	lb $v0,0($v1)
	0xbfc000d4	0x1440fffa	bnez $v0,0xbfc000c0
	0xbfc000d8	0x00000000	nop
	0xbfc000dc	0x3c041000	lui $a0,0x1000
	0xbfc000e0	0x2403000a	li $v1,10
	0xbfc000e4	0x24020001	li $v0,1
	0xbfc000e8	0x24060004	li $a2,4
	0xbfc000ec	0xac803ff4	sw $zero,16372($a0)
	0xbfc000f0	0xaca30000	sw $v1,0($a1)
	0xbfc000f4	0xac823ff4	sw $v0,16372($a0)
	0xbfc000f8	0x00001025	move $v0,$zero
	0xbfc000fc	0xaca30000	sw $v1,0($a1)
	0xbfc00100	0xac863ff4	sw $a2,16372($a0)
	0xbfc00104	0x24060009	li $a2,9
	0xbfc00108	0xaca30000	sw $v1,0($a1)
	0xbfc0010c	0xac863ff4	sw $a2,16372($a0)
	0xbfc00110	0x24060010	li $a2,16
	0xbfc00114	0xaca30000	sw $v1,0($a1)
	0xbfc00118	0xac863ff4	sw $a2,16372($a0)
	0xbfc0011c	0xaca30000	sw $v1,0($a1)
	0xbfc00120	0x03e00008	jr $ra
	0xbfc00124	0x00000000	nop
	0xbfc00128	0x3c081000	lui $t0,0x1000
	0xbfc0012c	0x25083ff8	addiu $t0,$t0,16376
	0xbfc00130	0xad020000	sw $v0,0($t0)

registers — read · written this tick

HI 0x00000000LO 0x00000000PC 0xbfc000b0

console (what the doors printed)

▮

cycle 0/1661 tick = 1 instruction (not a cycle)

tick 0 of 166

Nothing has run yet. The PC (program counter) points at the first instruction.

No frame is built: nothing is saved, nothing is called. The string loop prints one character per round and loads the next; 'h' was known at compile time. After the loop, ten stores print 0, 1, 4, 9, 16 with newlines. No mul runs: the squares are constants. jr $ra returns to crt0's tail, which stores 0 to the exit door.

What to notice

The string loop runs twenty rounds of seven instructions and prints one character per round. After it, every number and newline is one store. No mul ever runs. jr $ra returns to crt0’s tail, and the exit store ends the run with code 0. The console is the one the real core produced.

Before reading on, decide:

hello.c multiplies i * i, and §7.2 said your core runs mul on the muldiv station. At -O2, no mul appears anywhere. Where did the multiplications go?

Words, instructions, cycles

Three different counts hide behind “how big is the program”. The words are what the dump lists. The instructions executed are what the core actually ran, and a loop multiplies them. The add the machine’s own behaviour on top.

Seven programs, both optimisation levels: words in the dump and cycles on the core

word counts from carolyne_ref/dumps; cycles from the MIPS sweep, generated/sim/run/*_mips32_o0 and _o2


riscv_temp	189	288	98	34	MORE words: its fib (compiled, never called) grows from 32 to 219 words, the recursion inlined into itself
hello	128	72	1023	264	every call inlined, the loop unrolled, the squares folded
m4	98	54	127	44	locals in registers instead of the stack
fwd	122	66	156	50	locals in registers; the calls inlined
subword	147	72	213	58	seb keeps the sign-extension of a byte in one word
rec	134	67	470	45	the recursion unrolled into straight code
fib	215	304	16077	3391	MORE words: fib grows from 32 to 217 words, the recursion inlined into itself; five times fewer cycles

What to notice

hello executes about 200 instructions at -O2, from 72 words: crt0’s 42 first, then the string loop twenty times. It takes 264 cycles. m4 has no loop and finishes 54 words in 44 cycles, fewer cycles than words. The core can retire two instructions in one cycle. And fib is the warning: -O2 made it bigger and five times faster at the same time.

Why does hello need more cycles than instructions? Every taken branch in the string loop redirects fetch and throws away its slot. Every store goes through the store buffer before it reaches a door. And at -O0 the same program touches the stack on nearly every instruction. That is 1023 cycles for what -O2 does in 264.

Go deeper: how the numbers were made

The word counts are lines of the dumps. Every line with an address and an 8-digit word counts, symbols excluded. The cycle counts are the sweep from the design log, python -m examples.sim.sweep --target mips32 --opt=-O0 --opt=-O2. That is one Verilator run per program. Each run is checked against a host build of the same C. Every -O0 run matched its host build too. So the two compilations print the same text and differ only in how they get there.

-fno-delayed-branch is in force at both levels. That is why the -O2 loop still ends in bnez + nop. GCC would otherwise have moved the addiu into the slot and saved one word per round.

Can you now explain it?

-O0 translates statement by statement with every variable in memory; -O2 inlines, unrolls, folds and shares, and keeps only the meaning. Words, instructions executed and cycles are three counts, and only the last is what the clock sees.

If you remember only three things

-O0 keeps the shape. Every C line has its own instructions, i lives on the stack, every print is a real jal with a frame around it.
-O2 keeps the meaning. Three calls inlined, the loop unrolled five times, i*i folded to constants, one base for both doors. No mul, no frame.
Cycles are the machine's number. 72 words, about 200 instructions executed, 264 cycles. Loops multiply instructions; branches, slots and stores multiply cycles.

Now try to explain this one yourself: fib at -O2 is 304 words, more than the 215 at -O0. Yet it runs in 3391 cycles instead of 16077. What did the compiler most likely do? Why does bigger code run faster here?

Go deeper: a model answer, once you have tried

fib is recursive, and -O2 inlined part of the recursion. A call to fib(n − 1) was replaced by a copy of fib’s body, several levels deep. The function grew from 32 words to 217. But each inlined level is a call that no longer happens. No jal, no frame, no $ra save and restore, no return. The original made thousands of calls. Removing most of them saves far more cycles than the extra words cost. Bigger and faster are not opposites; the cycle count is the one that matters to the clock.

Check your understanding

0/5 answered

1.main at -O2 begins with `lui v1,0x1000`, not with `addiu sp,sp,-32`. Why can it skip building a frame?
2.Before the string loop, -O2 wrote `li v0,104`. What is 104, and why is it a constant?
3.Why does `sw v0,16368(a0)` print a character?
4.hello at -O2 is 72 words but took 264 cycles on your core. Why not 72 cycles?
5.fib is 215 words at -O0 and 304 at -O2. Does -O2 always make a program smaller?

Next: §9.4 — MIPS as a description, and MIPS beside RISC-V.

hello.c end to end: -O0, -O2 and the cycle count

Before you start

By the end, you can

The same C, twice

What the optimiser did, in four words

Watch the -O2 main run

Words, instructions, cycles

Can you now explain it?

Check your understanding