compiler

Unnamed Compiled Systems Language Project
git clone http://frotz.net/git/compiler.git
Log | Files | Refs

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