notebook.md (9975B)
1 # Notebook 2 3 A place to jot down ideas and/or commentary about the work in progress. 4 5 ### 2021 Nov 30 - Going backward to go forward. 6 7 The single pass straight code generation from parsing approach was working 8 but feeling increasingly brittle in the face of trying to get basic 9 optimizations going, etc. Decided to pause that and shift to compiler2.c 10 to start fresh with the existing lexer and rebuilding the parser to 11 generate an Abstract Syntax Tree instead. 12 13 This allows for multiple passes, simplifies some optimizations, and 14 paves the way for generating three-argument IR, SSA, etc. 15 16 ``` 17 FUNCDEF 'fib' 18 PARAM 'n' i32 19 RETURNS i32 20 BLOCK 21 IF 22 BINOP < 23 NAME 'n' 24 U32 0x2 25 BLOCK 26 RETURN 27 NAME 'n' 28 ``` 29 30 The new compiler can parse all the existing test and demo code, but does 31 not yet do any codegen. 32 33 ### 2021 May 24 - Where was I? 34 35 Implemented basic global scope enum support and changed remaining #defines 36 in compiler.c to enums. 37 38 Yanked out the lexer and built up rewriter.c that does a pretty limit 39 C to whatever language this is transform by mostly passing code through 40 but rewriting simple patterns like: 41 42 - void name(at an, bt bn) { -> func name(an at, bn bt) { 43 - type name = ... -> var name types = ... 44 - struct name { ... -> type name struct { ... 45 46 Discovered that demo/life.src bitrotted. Git bisect identifies the guilty 47 commit as cfe2d815bea0dd47d0ebeae933d673f4bf16cd6d "compiler: logical and/or 48 improvements. 49 50 Also d30153ccc6a1f5e61d13094999e703504153aa94 "copmiler: scanner fetches input 51 data in chunks" seems to have broken the correct printing of error lines. 52 53 Considering replacing varargs error io... error("file %s has %u typos",fn,n) 54 em("file "); es(fn); es(" has "); eu(n); ee(" typos"); kinda gross. 55 56 ### 2020 Mar 15 - Non-optimal codegen 57 58 1030-flow-control shows inefficient branch patterns around if-x-continue usage: 59 60 ```text 61 000000ac: 88e00004 ldw r8, [sp, 4] 62 000000b0: 48840001 and r8, r8, 1 63 000000b4: 49000001 mov r9, 1 64 000000b8: 08890009 sub r8, r8, r9 65 000000bc: e9000002 bne 0xc8 66 67 if ((n & 1) == 1) { 68 69 000000c0: e7fffff3 b 0x90 70 71 continue; 72 } 73 74 000000c4: e7000000 b 0xc8 75 ``` 76 77 This also gets me thinking that adopting the C convention that integer types 78 are treated as bools (0 = false, othewise true) would be more efficent in a 79 number of places, 80 81 ### 2020 Mar 14 - More questionable codegen 82 83 All of these from `demo/life.src` 84 85 What's up with this mov'ing the constant to r9 instead of just `sub r8, r8, 5`? 86 87 ```text 88 00000098: f7ffffdb bl 0x8 89 0000009c: 08000000 mov r8, r0 90 000000a0: 4884000f and r8, r8, 15 91 000000a4: 49000005 mov r9, 5 92 000000a8: 08890009 sub r8, r8, r9 93 000000ac: ed00000a bge 0xd8 94 95 if ((xorshift32() & 15) < 5) { 96 ``` 97 98 Hmm... 99 100 ```text 101 gen_load_reg 0x8, <Reg: r=0,a=8,b=0,t=int32> 102 gen_code '0000009c: 08000000 mov r8, r0' 103 gen_load_reg<<< <Reg: r=8,a=0,b=0,t=int32> 104 gen_mul_op 0x3, <Reg: r=8,a=0,b=0,t=int32>, <Const: r=0,a=15,b=0,t=int32> 105 gen_code '000000a0: 4884000f and r8, r8, 15' 106 gen_rel_op 0x2, <Reg: r=8,a=0,b=0,t=int32>, <Const: r=0,a=5,b=0,t=int32> 107 gen_load_reg 0x9, <Const: r=0,a=5,b=0,t=int32> 108 gen_code '000000a4: 49000005 mov r9, 5' 109 gen_load_reg<<< <Reg: r=9,a=0,b=0,t=int32> 110 gen_branch_cond 0x0, <Comp: r=2,a=8,b=9,t=int32> 111 gen_code '000000a8: 08890009 sub r8, r8, r9' 112 gen_code '000000ac: ed000000 bge 0xb0' 113 ``` 114 115 Hm. RHS of the rel-op is insufficiently lazy, it looks. 116 It loads 5 into a register ahead of `gen_branch_cond` 117 118 And the `add r8, r8, 4` at 0xc0 looks fishy too... 119 120 ```text 121 000000b0: 48d80004 add r8, sb, 4 122 000000b4: 89e00018 ldw r9, [sp, 24] 123 000000b8: 499a0050 mul r9, r9, 80 124 000000bc: 08880009 add r8, r8, r9 125 000000c0: 48880004 add r8, r8, 4 126 000000c4: 89e00014 ldw r9, [sp, 20] 127 000000c8: 08880009 add r8, r8, r9 128 000000cc: 49000001 mov r9, 1 129 000000d0: b9800004 stb r9, [r8, 4] 130 131 grid[y][x] = 1; 132 ``` 133 134 ```text 135 gen_item_from_obj<<< <RegInd: r=13,a=4,b=0,t=[25][80]byte> 136 gen_item_from_obj<<< <RegInd: r=14,a=24,b=0,t=int32> 137 gen_index <RegInd: r=13,a=4,b=0,t=[25][80]byte>, <RegInd: r=14,a=24,b=0,t=int32> 138 gen_address_reg 0x8, <RegInd: r=13,a=4,b=0,t=[25][80]byte> 139 gen_code '000000b0: 48d80004 add r8, sb, 4' 140 gen_load_reg 0x9, <RegInd: r=14,a=24,b=0,t=int32> 141 gen_code '000000b4: 89e00018 ldw r9, [sp, 24]' 142 gen_load_reg<<< <Reg: r=9,a=0,b=0,t=int32> 143 gen_code '000000b8: 499a0050 mul r9, r9, 80' 144 gen_code '000000bc: 08880009 add r8, r8, r9' 145 gen_index<<< <RegInd: r=8,a=4,b=0,t=[80]byte> 146 gen_item_from_obj<<< <RegInd: r=14,a=20,b=0,t=int32> 147 gen_index <RegInd: r=8,a=4,b=0,t=[80]byte>, <RegInd: r=14,a=20,b=0,t=int32> 148 gen_address_reg 0x8, <RegInd: r=8,a=4,b=0,t=[80]byte> 149 gen_code '000000c0: 48880004 add r8, r8, 4' 150 gen_load_reg 0x9, <RegInd: r=14,a=20,b=0,t=int32> 151 gen_code '000000c4: 89e00014 ldw r9, [sp, 20]' 152 gen_load_reg<<< <Reg: r=9,a=0,b=0,t=int32> 153 gen_code '000000c8: 08880009 add r8, r8, r9' 154 gen_index<<< <RegInd: r=8,a=4,b=0,t=byte> 155 gen_gen_store <Const: r=0,a=1,b=0,t=int32>, <RegInd: r=8,a=4,b=0,t=byte> 156 gen_load_reg 0x9, <Const: r=0,a=1,b=0,t=int32> 157 gen_code '000000cc: 49000001 mov r9, 1' 158 gen_load_reg<<< <Reg: r=9,a=0,b=0,t=int32> 159 gen_code '000000d0: b9800004 stb r9, [r8, 4]' 160 ``` 161 162 ### 2020 Mar 14 - stdlib deps 163 164 Quick check to see how much libc the compiler is depending on... 165 166 Not too bad. 167 168 unistd/syscall: open close read write exit\ 169 buffered: fopen fclose fgets fputs fwrite 170 formatted: printf fprintf vfprintf\ 171 memory: malloc memcmp memcpy memset strlen\ 172 misc: putchar puts exit abort\ 173 174 175 ### 2020 Mar 10 - Non-optimal codegen 176 177 When a break / continue / return takes control out of a scope, we're 178 not smart enough to discard stuff like the jump-around-else emitted 179 at the end of an if block, resulting in a dead branch op: 180 181 ```text 182 if (n < 2) { 183 return n; 184 185 00000020: 80e00004 ldw r0, [sp, 4] 186 00000024: e700000d b 0x5c 187 00000028: e700000c b 0x5c 188 ``` 189 190 We move return values from r0 to a temp register to cover cases where 191 we may immediately need r0 again (another call, etc) but that means 192 extra instructions and copies in other cases like `return fib(n - 1) + fib(n - 2);` 193 194 ```text 195 0000002c: 88e00004 ldw r8, [sp, 4] # get n 196 00000030: 40890001 sub r0, r8, 1 # r0 = n - 1 197 00000034: f7fffff3 bl 0x4 # r0 = fib(r0) 198 00000038: 08000000 mov r8, r0 # r0 -> tmp0 199 0000003c: 89e00004 ldw r9, [sp, 4] # get n 200 00000040: 40990002 sub r0, r9, 2 # r0 = n - 2 201 00000044: a8e00008 stw r8, [sp, 8] # save tmp0 202 00000048: f7ffffee bl 0x4 # r0 = fib(r0) 203 0000004c: 88e00008 ldw r8, [sp, 8] # restore tmp0 204 00000050: 09000000 mov r9, r0 # r0 -> tmp1 205 00000054: 00880009 add r0, r8, r9 # r0 = tmp0 + tmp1 206 00000058: e7000000 b 0x5c # jump to epilogue (return) 207 ``` 208 209 ### 2020 Mar 09 - Simplifying the Code 210 211 Up til now I had been passing around a "compiler context" pointer, so 212 almost every method looked like `parse_xyz(Ctx ctx, ...)` with a sort of 213 explicit this pointer as the first argument. 214 215 This caused a lot of clutter, and it will not help performance in any 216 useful way once it's self-hosting (since globals are loaded relative 217 to a global pointer register, whereas pointers first have to be grabbed 218 relative to sp and then further dereferenced). 219 220 It is useful from a namespace clutter standpoint to keep the struct 221 rather than 20-some stray globals. 222 223 See: [commit 1086c2aa1](https://github.com/swetland/compiler/commit/1086c2aa1133ed44b462b9a360f180ef9f0a851e) 224 225 ### 2020 Mar 09 - Path to Self-Hosting 226 227 As a big goal of the project is for the compiler to be self-hosted, able 228 to compile itself, and the bigger and more complex it and the language 229 gets the more work converting the source base over is likely to be, I've 230 been thinking about the simplest path to a MVP self-hosting compiler. 231 232 Expressions and simple flow control (if/else, while, break, return) 233 will be nearly identical to C. Basic function and structure declarations 234 will be very similar (mostly flipping the name/type order and some slight 235 punctuation changes). 236 237 My thinking is by writing the compiler in a strict subset of C that is 238 very regular it should be pretty simple to mechanically translate the 239 compiler with a script. Ideally entirely by script so I could maintain 240 the compiler in both languages long enough to do some "co-simulation" 241 style testing to ensure I'm getting identical compilation from both. 242 243 The remaining pieces needed to hit the MVP target are, I believe: 244 245 - [ ] finish if/while flow control 246 - [ ] support for enums, or convert enums to consts 247 - [ ] support for structs 248 - [ ] support for arrays 249 - [ ] support for pointers 250 - [ ] support for globals, init'ing gp 251 - [ ] support for open/close/read/write "syscalls" 252 - [ ] mini std library (malloc-analogue, alloc-only heap, string utils) 253 - [ ] rewrite lexer to use if/else instead of case 254 - [ ] emulator support for commandline args passing 255 256 Okay, that's still a decent chunk of work. But most of it is straight 257 forward for a base implementation. 258 259 We can survive for a while without floating point, structure extension, 260 whatever case/match mechanism ends up looking like, etc, etc. Data 261 structures are all about dumb, single-linked lists for now. Hashtables 262 or Trees can come much later in the process. 263 264 I need to make some decisions on pointers vs references. 265 266 I should just make ctx global -- passing it like a this pointer clutters 267 up the code and doesn't buy much. And it'll be slower for quite a while, 268 since for now param -> ldw -> pointer-in-reg -> ldw -> value in struct is 269 more work than just loading relative to the global pointer. 270 271