CS152 Lab 1 - HackMD

# CS152 Lab 1 ## Open-ended Portion - Mix Manufacturing ### Note Due to some misunderstanding on the calculation of branch/non-branch inst ratio, we initially aimed at maximizing br/non-br ratio in executed code. ### Attempt 1 During our experiment on compiler codegen, we discovered that `goto` would be a convenient choice for redirecting program execution flow. (At this point, we were still maximizing the *runtime* branch/nonbranch ratio, so the longer the execution flow the better.) Our first attempt was this: ```c int a; int main () { tag: if (a == 1) { goto tag; } else if (a == 2) { goto tag; } else if (a == 3) { goto tag; } else if (a == 4) { goto tag; } else if (a == 5) { goto tag; } else if (a == 6) { goto tag; } return 0; } ``` ```assembly Disassembly of section .text: 80001048 <main>: 80001048: ff010113 addi sp,sp,-16 8000104c: 00812623 sw s0,12(sp) 80001050: 01010413 addi s0,sp,16 80001054: 00000797 auipc a5,0x0 80001058: 0a478793 addi a5,a5,164 # 800010f8 <a> 8000105c: 0007a703 lw a4,0(a5) 80001060: 00100793 li a5,1 80001064: 00f71463 bne a4,a5,8000106c <main+0x24> 80001068: fedff06f j 80001054 <main+0xc> 8000106c: 00000797 auipc a5,0x0 80001070: 08c78793 addi a5,a5,140 # 800010f8 <a> 80001074: 0007a703 lw a4,0(a5) 80001078: 00200793 li a5,2 8000107c: 00f71463 bne a4,a5,80001084 <main+0x3c> 80001080: fd5ff06f j 80001054 <main+0xc> 80001084: 00000797 auipc a5,0x0 80001088: 07478793 addi a5,a5,116 # 800010f8 <a> 8000108c: 0007a703 lw a4,0(a5) 80001090: 00300793 li a5,3 80001094: 00f71463 bne a4,a5,8000109c <main+0x54> 80001098: fbdff06f j 80001054 <main+0xc> 8000109c: 00000797 auipc a5,0x0 800010a0: 05c78793 addi a5,a5,92 # 800010f8 <a> 800010a4: 0007a703 lw a4,0(a5) 800010a8: 00400793 li a5,4 800010ac: 00f71463 bne a4,a5,800010b4 <main+0x6c> 800010b0: fa5ff06f j 80001054 <main+0xc> 800010b4: 00000797 auipc a5,0x0 800010b8: 04478793 addi a5,a5,68 # 800010f8 <a> 800010bc: 0007a703 lw a4,0(a5) 800010c0: 00500793 li a5,5 800010c4: 00f71463 bne a4,a5,800010cc <main+0x84> 800010c8: f8dff06f j 80001054 <main+0xc> 800010cc: 00000797 auipc a5,0x0 800010d0: 02c78793 addi a5,a5,44 # 800010f8 <a> 800010d4: 0007a703 lw a4,0(a5) 800010d8: 00600793 li a5,6 800010dc: 00f71463 bne a4,a5,800010e4 <main+0x9c> 800010e0: f75ff06f j 80001054 <main+0xc> 800010e4: 00000793 li a5,0 800010e8: 00078513 mv a0,a5 800010ec: 00c12403 lw s0,12(sp) 800010f0: 01010113 addi sp,sp,16 800010f4: 00008067 ret ``` As demonstrated above, every `if` statement generates one branch instruction, which is as expected. Most other instructions were loading immediates, saving register to be used, maintaining stack, etc. Obviously we can do better. **Ratio of branch to non-branch instructions, static: 6/44 = 13.64% (O0)** **Ratio of branch to non-branch instructions, runtime: 5% (O0)** **CPI: 1.328 (O0)** ### Attempt 2 Instead of redirecting execution using `goto`, we decided to try out recursive strategy in this round for comparison. At this stage we were aiming at increasing the branch density of the original C code, so our next step is to find something more efficient than `if`. `switch` came into mind (as we can fit `case` and its body on the same line). Meanwhile we also tried using ternary operators (equivalent to 1 or 2 branch(es)) to increase numbers of branch instructions. As a sidenote, we discovered that under some certain circumstances, using optimization would compress arithmetic instructions without influencing jump/branching instructions as much, so we opted in compiler optimization. (We used a gcc attribute to turn on "-O3" for this function only, as follows:) ```c volatile int test = 0; __attribute__((optimize("O3"))) int main(void) { switch (test == 0 ? 0 : test) { case 0: test = 0x1; main() == 0 ? 0 : main(); case 1: test == 0 ? test = 0 : (test = 0x2); main(); case 2: test == 0 ? test = 0 : (test = 0x3); main(); case 3: test == 0 ? test = 0 : (test = 0x4); main(); if ((test == 0) ? 0 : (test == 4)) { test == 0 ? test = 0 : (test = 0x5); main(); } else if ((test == 0) ? 0 : (test == 5)) { test == 0 ? test = 0 : (test = 0x6); main(); } else { main() == 0 ? 0 : main(); } } return 0; } ``` ```assembly Disassembly of section .text.startup: 80001048 <main>: 80001048: ff010113 addi sp,sp,-16 8000104c: 00812423 sw s0,8(sp) 80001050: 00000417 auipc s0,0x0 80001054: 14840413 addi s0,s0,328 # 80001198 <test> 80001058: 00042783 lw a5,0(s0) 8000105c: 00112623 sw ra,12(sp) 80001060: 08078063 beqz a5,800010e0 <main+0x98> 80001064: 00042783 lw a5,0(s0) 80001068: 00100713 li a4,1 8000106c: 08e78463 beq a5,a4,800010f4 <main+0xac> 80001070: 06f75663 ble a5,a4,800010dc <main+0x94> 80001074: 00200713 li a4,2 80001078: 08e78863 beq a5,a4,80001108 <main+0xc0> 8000107c: 00300713 li a4,3 80001080: 04e79463 bne a5,a4,800010c8 <main+0x80> 80001084: 00042783 lw a5,0(s0) 80001088: 08079c63 bnez a5,80001120 <main+0xd8> 8000108c: 00000797 auipc a5,0x0 80001090: 1007a623 sw zero,268(a5) # 80001198 <test> 80001094: fb5ff0ef jal ra,80001048 <main> 80001098: 00042783 lw a5,0(s0) 8000109c: 00078863 beqz a5,800010ac <main+0x64> 800010a0: 00042703 lw a4,0(s0) 800010a4: 00400793 li a5,4 800010a8: 08f70463 beq a4,a5,80001130 <main+0xe8> 800010ac: 00042783 lw a5,0(s0) 800010b0: 00078863 beqz a5,800010c0 <main+0x78> 800010b4: 00042703 lw a4,0(s0) 800010b8: 00500793 li a5,5 800010bc: 0af70863 beq a4,a5,8000116c <main+0x124> 800010c0: f89ff0ef jal ra,80001048 <main> 800010c4: 08051063 bnez a0,80001144 <main+0xfc> 800010c8: 00c12083 lw ra,12(sp) 800010cc: 00812403 lw s0,8(sp) 800010d0: 00000513 li a0,0 800010d4: 01010113 addi sp,sp,16 800010d8: 00008067 ret 800010dc: fe0796e3 bnez a5,800010c8 <main+0x80> 800010e0: 00100793 li a5,1 800010e4: 00000717 auipc a4,0x0 800010e8: 0af72a23 sw a5,180(a4) # 80001198 <test> 800010ec: f5dff0ef jal ra,80001048 <main> 800010f0: 0a051063 bnez a0,80001190 <main+0x148> 800010f4: 00042783 lw a5,0(s0) 800010f8: 06079263 bnez a5,8000115c <main+0x114> 800010fc: 00000797 auipc a5,0x0 80001100: 0807ae23 sw zero,156(a5) # 80001198 <test> 80001104: f45ff0ef jal ra,80001048 <main> 80001108: 00042783 lw a5,0(s0) 8000110c: 04079063 bnez a5,8000114c <main+0x104> 80001110: 00000797 auipc a5,0x0 80001114: 0807a423 sw zero,136(a5) # 80001198 <test> 80001118: f31ff0ef jal ra,80001048 <main> 8000111c: f69ff06f j 80001084 <main+0x3c> 80001120: 00400793 li a5,4 80001124: 00000717 auipc a4,0x0 80001128: 06f72a23 sw a5,116(a4) # 80001198 <test> 8000112c: f69ff06f j 80001094 <main+0x4c> 80001130: 00042783 lw a5,0(s0) 80001134: 04078063 beqz a5,80001174 <main+0x12c> 80001138: 00500793 li a5,5 8000113c: 00000717 auipc a4,0x0 80001140: 04f72e23 sw a5,92(a4) # 80001198 <test> 80001144: f05ff0ef jal ra,80001048 <main> 80001148: f81ff06f j 800010c8 <main+0x80> 8000114c: 00300793 li a5,3 80001150: 00000717 auipc a4,0x0 80001154: 04f72423 sw a5,72(a4) # 80001198 <test> 80001158: fc1ff06f j 80001118 <main+0xd0> 8000115c: 00200793 li a5,2 80001160: 00000717 auipc a4,0x0 80001164: 02f72c23 sw a5,56(a4) # 80001198 <test> 80001168: f9dff06f j 80001104 <main+0xbc> 8000116c: 00042783 lw a5,0(s0) 80001170: 00079863 bnez a5,80001180 <main+0x138> 80001174: 00000797 auipc a5,0x0 80001178: 0207a223 sw zero,36(a5) # 80001198 <test> 8000117c: fc9ff06f j 80001144 <main+0xfc> 80001180: 00600793 li a5,6 80001184: 00000717 auipc a4,0x0 80001188: 00f72a23 sw a5,20(a4) # 80001198 <test> 8000118c: fb9ff06f j 80001144 <main+0xfc> 80001190: eb9ff0ef jal ra,80001048 <main> 80001194: f61ff06f j 800010f4 <main+0xac> ``` As we can see, branch instruction density had a significant increase comparing to previous attempt. However, the increase of branch instructions brought more increase of immediate loading/memory access, which is not ideal for branch density. Asssuming the increasing of branch instructions leads to increased amount of stall, our observation matches our theory (that more branches will lead to increasing CPI). **Ratio of branch to non-branch instructions, static: 17/84 = 20.24% (O3)** **Ratio of branch to non-branch instructions, runtime: 20% (O3)** **CPI: 1.384 (O3)** ### Attempt 3 At this point, we read on Piazza that we should maximize the number of branch instructions in the generated static code instead of the number of branch instructions dispatched at runtime. Therefore, we started over and started to experiment with different constructs that could generate a bunch of branches. For example, we tried to write a nested if expression with a tenary expression in the condition field to maximize the number of branches generated per line. ```c volatile int test, test2 = 0; __attribute__((optimize("O3"))) int main() { test2 = 2; if (test ? 1 : test2) { if (test ? test2 : 1) { if (test ? 1 : test2) { if (test ? 1 : test2) { if (test ? 1 : test2) { if (test ? 1 : test2) { if (test ? 1 : test2) { if (test ? 1 : test2) { if (test ? 1 : test2) { if (test ? 1 : test2) { if (test ? 1 : test2) { test2 = test ? 1 : test2; }}}}}}}}}}} } ``` ```assembly Disassembly of section .text.startup: 80001048 <main>: 80001048: 00200793 li a5,2 8000104c: 00000717 auipc a4,0x0 80001050: 10f72423 sw a5,264(a4) # 80001154 <test2> 80001054: 00000797 auipc a5,0x0 80001058: 0fc78793 addi a5,a5,252 # 80001150 <test> 8000105c: 0007a683 lw a3,0(a5) 80001060: 00000717 auipc a4,0x0 80001064: 0f470713 addi a4,a4,244 # 80001154 <test2> 80001068: 00069663 bnez a3,80001074 <main+0x2c> 8000106c: 00072683 lw a3,0(a4) 80001070: 08068263 beqz a3,800010f4 <main+0xac> 80001074: 0007a683 lw a3,0(a5) 80001078: 08069263 bnez a3,800010fc <main+0xb4> 8000107c: 0007a683 lw a3,0(a5) 80001080: 08068463 beqz a3,80001108 <main+0xc0> 80001084: 0007a683 lw a3,0(a5) 80001088: 00069663 bnez a3,80001094 <main+0x4c> 8000108c: 00072683 lw a3,0(a4) 80001090: 06068263 beqz a3,800010f4 <main+0xac> 80001094: 0007a683 lw a3,0(a5) 80001098: 06068e63 beqz a3,80001114 <main+0xcc> 8000109c: 0007a683 lw a3,0(a5) 800010a0: 08068063 beqz a3,80001120 <main+0xd8> 800010a4: 0007a683 lw a3,0(a5) 800010a8: 08068263 beqz a3,8000112c <main+0xe4> 800010ac: 0007a683 lw a3,0(a5) 800010b0: 00069663 bnez a3,800010bc <main+0x74> 800010b4: 00072683 lw a3,0(a4) 800010b8: 02068e63 beqz a3,800010f4 <main+0xac> 800010bc: 0007a683 lw a3,0(a5) 800010c0: 00069663 bnez a3,800010cc <main+0x84> 800010c4: 00072683 lw a3,0(a4) 800010c8: 02068663 beqz a3,800010f4 <main+0xac> 800010cc: 0007a683 lw a3,0(a5) 800010d0: 06068463 beqz a3,80001138 <main+0xf0> 800010d4: 0007a683 lw a3,0(a5) 800010d8: 06068663 beqz a3,80001144 <main+0xfc> 800010dc: 0007a683 lw a3,0(a5) 800010e0: 00100793 li a5,1 800010e4: 00069463 bnez a3,800010ec <main+0xa4> 800010e8: 00072783 lw a5,0(a4) 800010ec: 00000717 auipc a4,0x0 800010f0: 06f72423 sw a5,104(a4) # 80001154 <test2> 800010f4: 00000513 li a0,0 800010f8: 00008067 ret 800010fc: 00072683 lw a3,0(a4) 80001100: f6069ee3 bnez a3,8000107c <main+0x34> 80001104: ff1ff06f j 800010f4 <main+0xac> 80001108: 00072683 lw a3,0(a4) 8000110c: f6069ce3 bnez a3,80001084 <main+0x3c> 80001110: fe5ff06f j 800010f4 <main+0xac> 80001114: 00072683 lw a3,0(a4) 80001118: f80692e3 bnez a3,8000109c <main+0x54> 8000111c: fd9ff06f j 800010f4 <main+0xac> 80001120: 00072683 lw a3,0(a4) 80001124: f80690e3 bnez a3,800010a4 <main+0x5c> 80001128: fcdff06f j 800010f4 <main+0xac> 8000112c: 00072683 lw a3,0(a4) 80001130: f6069ee3 bnez a3,800010ac <main+0x64> 80001134: fc1ff06f j 800010f4 <main+0xac> 80001138: 00072683 lw a3,0(a4) 8000113c: f8069ce3 bnez a3,800010d4 <main+0x8c> 80001140: fb5ff06f j 800010f4 <main+0xac> 80001144: 00072683 lw a3,0(a4) 80001148: f8069ae3 bnez a3,800010dc <main+0x94> 8000114c: fa9ff06f j 800010f4 <main+0xac> ``` **Ratio of branch to non-branch instructions, static: 23/66 = 35% (O3)** **Ratio of branch to non-branch instructions, runtime: 14% (O3)** **CPI: 1.521 (O3)** This approach turned out to be a bit more effective at generating branch instructions than our previous attempts, giving us a static ratio of 35%. We are using "O3" here because it gets rid of some of the prologue/epilogue/misc. code that do not contribute to the branch instruction ratio. The CPI also increased from 1.328 from 1.521, likely due to the increased ratio of branch instructions and the existance of many lw instructions (potentially because of memory latency).  ### Attempt 4 Looking at our previous attempts, it seems that a large portion of our instructions were load word or load immediate instructions besides our branches, typically at a one-to-one ratio. This meant that our final branch instruction ration could not exceed 50%. Is there way to not generate instructions that access the memory? Browsing Piazza once again, we received the helpful hint that we are allowed to use the register keyword to hint to the compiler that a particular variable should be stored in a register. The result is the code below: ```c __attribute__((optimize("O3"))) int main() { volatile register int r asm ("a0"); volatile register int a asm ("x5"); volatile register int b asm ("x6"); volatile register int c asm ("x7"); volatile register int d asm ("x28"); tag: if (a == b) { goto tag; } else if (a == c) { goto tag; } else if (a == d) { goto tag; } else if (a == 0) { goto tag; } return r; } ``` ```assembly Disassembly of section .text.startup: 80001048 <main>: 80001048: 00628063 beq t0,t1,80001048 <main> 8000104c: fe728ee3 beq t0,t2,80001048 <main> 80001050: ffc28ce3 beq t0,t3,80001048 <main> 80001054: fe028ae3 beqz t0,80001048 <main> 80001058: 00008067 ret ``` **Ratio of branch to non-branch instructions, static: 4/5 = 80%** **Ratio of branch to non-branch instructions, runtime: 4%** **CPI: 1.413** Here, we are able to drastically increase the ratio of branch to non-branch instructions to 80% by avoiding lw instructions. However, both our runtime branch to non-branch ratio and CPI has dropped, likely because the CPU no longer needs to wait for the data memory to respond. ### Attempt 5 Can we make the ratio higher? The answer is yes. Basically, now our goal is to generate as many branch instructions as possible so that the single `ret` instruction at the end takes up a smaller portion of the code. We noticed that all the variable declartions in our program take up multiple lines - lines that could've been taken up by if expressions, so we put all variable declartions on one line. ```c __attribute__((optimize("O3"))) int main() { volatile register int r asm ("a0"), a asm ("x5"), b asm ("x6"), c asm ("x7"), d asm ("x28"), e asm ("x29"), f asm ("x30"); tag: if (a == b) { goto tag; } else if (a == c) { goto tag; } else if (a == d) { goto tag; } else if (a == 0) { goto tag; } else if (a == e) { goto tag; } else if (a == f) { goto tag; } return r; } ``` ```assembly Disassembly of section .text.startup: 80001048 <main>: 80001048: 00628063 beq t0,t1,80001048 <main> 8000104c: fe728ee3 beq t0,t2,80001048 <main> 80001050: ffc28ce3 beq t0,t3,80001048 <main> 80001054: fe028ae3 beqz t0,80001048 <main> 80001058: ffd288e3 beq t0,t4,80001048 <main> 8000105c: ffe286e3 beq t0,t5,80001048 <main> 80001060: 00008067 ret ``` **Ratio of branch to non-branch instructions, static: 6/7 = 85.7% (O3)** **Ratio of branch to non-branch instructions, runtime: 5.6% (O3)** **CPI: 1.392 (O3)** As a result, our static branch to non-branch instructioin ratio increased from 80% to 85.7%. Curiously, our runtime ratio increased slightly while our CPI decreased slightly compared to the previous attempt. We suspect this is the case because our code became slightly longer, thus making the instruction cache a bit more effective. ### Attempt 6 However, we are not satified with our program because we still haven't had to use macros yet :) In our final attempt, we use a macro that generates two if expressions in just a single line (though the macro definition itself does take 4 lines). ```c #define foo(x, y) if (a == x) { \ goto tag; \ } if (a == y) { \ goto tag; \ } __attribute__((optimize("O3"))) int main() { volatile register int r asm ("a0"), a asm ("x5"), b asm ("x6"), c asm ("x7"), d asm ("x28"), e asm ("x29"), f asm ("x30"), g asm ("x31"), i asm ("x11"), j asm ("x12"), k asm ("x13"); tag: foo(b, c); foo(0, e); foo(e, f); foo(g, i); foo(j, k); foo(j, k); foo(j, k); return r; } ``` ```assembly Disassembly of section .text.startup: 80001048 <main>: 80001048: 00628063 beq t0,t1,80001048 <main> 8000104c: fe728ee3 beq t0,t2,80001048 <main> 80001050: fe028ce3 beqz t0,80001048 <main> 80001054: ffd28ae3 beq t0,t4,80001048 <main> 80001058: ffe288e3 beq t0,t5,80001048 <main> 8000105c: fff286e3 beq t0,t6,80001048 <main> 80001060: feb284e3 beq t0,a1,80001048 <main> 80001064: fec282e3 beq t0,a2,80001048 <main> 80001068: fed280e3 beq t0,a3,80001048 <main> 8000106c: fcc28ee3 beq t0,a2,80001048 <main> 80001070: fcd28ce3 beq t0,a3,80001048 <main> 80001074: fcc28ae3 beq t0,a2,80001048 <main> 80001078: fcd288e3 beq t0,a3,80001048 <main> 8000107c: 00008067 ret ``` **Ratio of branch to non-branch instructions, static: 13/14 = 92.9% (O3)** **Ratio of branch to non-branch instructions, runtime: 11.1% (O3)** **CPI: 1.349 (O3)** This gives us a static branch to non-branch instruction ratio of 92.9%. As observed before, there is again a slight increase of the runtime branch to non-branch instruction ratio and a slight decrease of CPI, likely due to cost of filling the instruction cache being amortized over the longer program.

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.