From 3cf03158599472b1f6713192d9fa2b120f9f209b Mon Sep 17 00:00:00 2001 From: Kartik Agaram Date: Sat, 7 Mar 2020 17:32:39 -0800 Subject: 6094 - new 'compute-offset' instruction If indexing into a type with power-of-2-sized elements we can access them in one instruction: x/reg1: (addr int) <- index A/reg2: (addr array int), idx/reg3: int This translates to a single instruction because x86 instructions support an addressing mode with left-shifts. For non-powers-of-2, however, we need a multiply. To keep things type-safe, it is performed like this: x/reg1: (offset T) <- compute-offset A: (addr array T), idx: int y/reg2: (addr T) <- index A, x An offset is just an int that is guaranteed to be a multiple of size-of(T). Offsets can only be used in index instructions, and the types will eventually be required to line up. In the process, I have to expand Input-size because mu.subx is growing big. --- apps/assort | Bin 40852 -> 40852 bytes apps/braces | Bin 42546 -> 42546 bytes apps/calls | Bin 47207 -> 47207 bytes apps/dquotes | Bin 44502 -> 44502 bytes apps/hex | Bin 43099 -> 43099 bytes apps/mu | Bin 177346 -> 180570 bytes apps/mu.subx | 186 ++++++++++++++++++++++++++++++++++++++++++++------ apps/pack | Bin 53244 -> 53244 bytes apps/sigils | Bin 54931 -> 54931 bytes apps/subx-params.subx | 2 +- apps/survey | Bin 50093 -> 50093 bytes apps/survey.subx | 2 +- apps/tests | Bin 39650 -> 39650 bytes mu_instructions | 14 +++- mu_summary | 11 ++- 15 files changed, 186 insertions(+), 29 deletions(-) diff --git a/apps/assort b/apps/assort index 92ac1ca1..980e294d 100755 Binary files a/apps/assort and b/apps/assort differ diff --git a/apps/braces b/apps/braces index fcda2022..1c4f8596 100755 Binary files a/apps/braces and b/apps/braces differ diff --git a/apps/calls b/apps/calls index c7e2b758..f22a1b2c 100755 Binary files a/apps/calls and b/apps/calls differ diff --git a/apps/dquotes b/apps/dquotes index 8f96f53b..fd1bae17 100755 Binary files a/apps/dquotes and b/apps/dquotes differ diff --git a/apps/hex b/apps/hex index 92241075..d91286e0 100755 Binary files a/apps/hex and b/apps/hex differ diff --git a/apps/mu b/apps/mu index aca16494..6820aa8d 100755 Binary files a/apps/mu and b/apps/mu differ diff --git a/apps/mu.subx b/apps/mu.subx index bf777231..89ee6af5 100644 --- a/apps/mu.subx +++ b/apps/mu.subx @@ -389,6 +389,7 @@ Type-id: # (stream (address array byte)) "handle"/imm32 # 4 "boolean"/imm32 # 5 "constant"/imm32 # 6: like a literal, but replaced with its value in Var-offset + "offset"/imm32 # 7: (offset T) is guaranteed to be a 32-bit multiple of size-of(T) 0/imm32 # 0x20 0/imm32 0/imm32 0/imm32 0/imm32 0/imm32 0/imm32 0/imm32 0/imm32 @@ -2311,6 +2312,58 @@ test-convert-index-into-array-with-literal: 5d/pop-to-ebp c3/return +test-convert-index-into-array-using-offset: + # . prologue + 55/push-ebp + 89/<- %ebp 4/r32/esp + # setup + (clear-stream _test-input-stream) + (clear-stream $_test-input-buffered-file->buffer) + (clear-stream _test-output-stream) + (clear-stream $_test-output-buffered-file->buffer) + c7 0/subop/copy *Next-block-index 1/imm32 + # + (write _test-input-stream "fn foo {\n") + (write _test-input-stream " var arr/eax: (addr array int) <- copy 0\n") + (write _test-input-stream " var idx/ecx: int <- copy 3\n") + (write _test-input-stream " var off/ecx: (offset int) <- compute-offset arr, idx\n") + (write _test-input-stream " var x/eax: (addr int) <- index arr, off\n") + (write _test-input-stream "}\n") + # convert + (convert-mu _test-input-buffered-file _test-output-buffered-file) + (flush _test-output-buffered-file) +#? # dump _test-output-stream {{{ +#? (write 2 "^") +#? (write-stream 2 _test-output-stream) +#? (write 2 "$\n") +#? (rewind-stream _test-output-stream) +#? # }}} + # check output + (check-next-stream-line-equal _test-output-stream "foo:" "F - test-convert-index-into-array-using-offset/0") + (check-next-stream-line-equal _test-output-stream " # . prologue" "F - test-convert-index-into-array-using-offset/1") + (check-next-stream-line-equal _test-output-stream " 55/push-ebp" "F - test-convert-index-into-array-using-offset/2") + (check-next-stream-line-equal _test-output-stream " 89/<- %ebp 4/r32/esp" "F - test-convert-index-into-array-using-offset/3") + (check-next-stream-line-equal _test-output-stream " {" "F - test-convert-index-into-array-using-offset/4") + (check-next-stream-line-equal _test-output-stream "$foo:0x00000001:loop:" "F - test-convert-index-into-array-using-offset/5") + (check-next-stream-line-equal _test-output-stream " ff 6/subop/push %eax" "F - test-convert-index-into-array-using-offset/6") + (check-next-stream-line-equal _test-output-stream " b8/copy-to-eax 0/imm32" "F - test-convert-index-into-array-using-offset/7") + (check-next-stream-line-equal _test-output-stream " ff 6/subop/push %ecx" "F - test-convert-index-into-array-using-offset/8") + (check-next-stream-line-equal _test-output-stream " b9/copy-to-ecx 3/imm32" "F - test-convert-index-into-array-using-offset/9") + (check-next-stream-line-equal _test-output-stream " 69/multiply 0x00000004/imm32 %ecx 0x00000001/r32" "F - test-convert-index-into-array-using-offset/10") + (check-next-stream-line-equal _test-output-stream " 8d/copy-address *(eax + ecx + 4) 0x00000000/r32" "F - test-convert-index-into-array-using-offset/11") + (check-next-stream-line-equal _test-output-stream " 8f 0/subop/pop %ecx" "F - test-convert-index-into-array-using-offset/12") + (check-next-stream-line-equal _test-output-stream " 8f 0/subop/pop %eax" "F - test-convert-index-into-array-using-offset/13") + (check-next-stream-line-equal _test-output-stream " }" "F - test-convert-index-into-array-using-offset/14") + (check-next-stream-line-equal _test-output-stream "$foo:0x00000001:break:" "F - test-convert-index-into-array-using-offset/15") + (check-next-stream-line-equal _test-output-stream " # . epilogue" "F - test-convert-index-into-array-using-offset/16") + (check-next-stream-line-equal _test-output-stream " 89/<- %esp 5/r32/ebp" "F - test-convert-index-into-array-using-offset/17") + (check-next-stream-line-equal _test-output-stream " 5d/pop-to-ebp" "F - test-convert-index-into-array-using-offset/18") + (check-next-stream-line-equal _test-output-stream " c3/return" "F - test-convert-index-into-array-using-offset/19") + # . epilogue + 89/<- %esp 5/r32/ebp + 5d/pop-to-ebp + c3/return + test-convert-function-and-type-definition: # . prologue 55/push-ebp @@ -6684,6 +6737,15 @@ emit-subx-stmt: # out: (addr buffered-file), stmt: (handle stmt), primitives: ( (translate-mu-index-stmt *(ebp+8) *(ebp+0xc)) e9/jump $emit-subx-stmt:end/disp32 } + # compute-offset for index into array + { + # if (!string-equal?(var->operation, "compute-offset")) break + (string-equal? *(ecx+4) "compute-offset") # Stmt1-operation => eax + 3d/compare-eax-and 0/imm32 + 0f 84/jump-if-= break/disp32 + (translate-mu-compute-index-stmt *(ebp+8) *(ebp+0xc)) + e9/jump $emit-subx-stmt:end/disp32 + } # get field from record { # if (!string-equal?(var->operation, "get")) break @@ -6788,23 +6850,46 @@ $translate-mu-index-stmt:emit-base: 81 7/subop/compare *(edx+0x10) 0/imm32 # Var-register { 0f 84/jump-if-= break/disp32 - # print inouts[1]->register "<<" log2(sizeof(element(inouts[0]->type))) " + 4) " $translate-mu-index-stmt:emit-register-index: - # . inouts[1]->register "<<" - (write-buffered *(ebp+8) *(edx+0x10)) # Var-register - (write-buffered *(ebp+8) "<<") - # . log2(sizeof(element(inouts[0]->type))) - # TODO: ensure size is a power of 2 - (array-element-type-id %ebx) # => eax - (size-of-type-id %eax) # => eax - (num-shift-rights %eax) # => eax - (print-int32-buffered *(ebp+8) %eax) - # . + # if inouts[1] is an int + (is-simple-mu-type? *(edx+4) 1) # Var-type, int => eax + 3d/compare-eax-and 0/imm32/false + { + 0f 84/jump-if-= break/disp32 +$translate-mu-index-stmt:emit-int-register-index: + # print inouts[1]->register "<<" log2(sizeof(element(inouts[0]->type))) " + 4) " + # . inouts[1]->register "<<" + (write-buffered *(ebp+8) *(edx+0x10)) # Var-register + (write-buffered *(ebp+8) "<<") + # . log2(sizeof(element(inouts[0]->type))) + # TODO: ensure size is a power of 2 + (array-element-type-id %ebx) # => eax + (size-of-type-id %eax) # => eax + (num-shift-rights %eax) # => eax + (print-int32-buffered *(ebp+8) %eax) + e9/jump $translate-mu-index-stmt:emit-register-index-done/disp32 + } + # if inouts[1]->type is any other atom, abort + 8b/-> *(edx+4) 0/r32/eax # Var-type + 8b/-> *eax 0/r32/eax # Tree-left or Atom-value + 3b/compare 0/r32/eax *Max-type-id + 0f 82/jump-if-addr< $translate-mu-index-stmt:error2/disp32 + # if inouts[1] is (offset ...) + (is-simple-mu-type? %eax 7) # offset => eax + 3d/compare-eax-and 0/imm32/false + { + 0f 84/jump-if-= break/disp32 + # print inouts[1]->register "<<" log2(sizeof(element(inouts[0]->type))) " + 4) " +$translate-mu-index-stmt:emit-offset-register-index: + # . inouts[1]->register + (write-buffered *(ebp+8) *(edx+0x10)) # Var-register + } +$translate-mu-index-stmt:emit-register-index-done: (write-buffered *(ebp+8) " + 4) ") e9/jump $translate-mu-index-stmt:emit-output/disp32 } # otherwise if inouts[1] is a literal - (is-literal-type? *(edx+4)) # Var-type => eax + (is-simple-mu-type? *(edx+4) 0) # Var-type => eax 3d/compare-eax-and 0/imm32/false { 0f 84/jump-if-= break/disp32 @@ -6825,7 +6910,7 @@ $translate-mu-index-stmt:emit-literal-index: e9/jump $translate-mu-index-stmt:emit-output/disp32 } # otherwise abort - e9/jump $translate-mu-index-stmt:abort/disp32 + e9/jump $translate-mu-index-stmt:error1/disp32 $translate-mu-index-stmt:emit-output: # outputs[0] "/r32" 8b/-> *(ecx+0xc) 0/r32/eax # Stmt1-outputs @@ -6844,7 +6929,7 @@ $translate-mu-index-stmt:end: 5d/pop-to-ebp c3/return -$translate-mu-index-stmt:abort: +$translate-mu-index-stmt:error1: (write-buffered Stderr "couldn't translate an index instruction. second (index) input must either lie in a register or be a literal\n") (flush Stderr) # . syscall(exit, 1) @@ -6853,6 +6938,60 @@ $translate-mu-index-stmt:abort: cd/syscall 0x80/imm8 # never gets here +$translate-mu-index-stmt:error2: + (write-buffered Stderr "couldn't translate an index instruction. second (index) input when in a register must be an int or offset\n") + (flush Stderr) + # . syscall(exit, 1) + bb/copy-to-ebx 1/imm32 + b8/copy-to-eax 1/imm32/exit + cd/syscall 0x80/imm8 + # never gets here + +translate-mu-compute-index-stmt: # out: (address buffered-file), stmt: (handle stmt) + # . prologue + 55/push-ebp + 89/<- %ebp 4/r32/esp + # . save registers + 50/push-eax + 51/push-ecx + 52/push-edx + 53/push-ebx + # + (emit-indent *(ebp+8) *Curr-block-depth) + (write-buffered *(ebp+8) "69/multiply ") +$translate-mu-compute-index-stmt:emit-elem-size: + # ecx = stmt + 8b/-> *(ebp+0xc) 1/r32/ecx + # var first-inout/edx: (handle stmt-var) = stmt->inouts[0] + 8b/-> *(ecx+8) 2/r32/edx # Stmt1-inouts + # var base/ebx: (handle var) + 8b/-> *edx 3/r32/ebx # Stmt-var-value + # print sizeof(element(base->type)) + (array-element-type-id %ebx) # => eax + (size-of-type-id %eax) # => eax + (print-int32-buffered *(ebp+8) %eax) + (write-buffered *(ebp+8) "/imm32") +$translate-mu-compute-index-stmt:emit-index: + (emit-subx-var-as-rm32 *(ebp+8) *(edx+4)) # Stmt-var-next + (write-buffered *(ebp+8) Space) +$translate-mu-compute-index-stmt:emit-output: + # outputs[0] "/r32" + 8b/-> *(ecx+0xc) 0/r32/eax # Stmt1-outputs + 8b/-> *eax 0/r32/eax # Stmt-var-value + (get Registers *(eax+0x10) 8 "Registers") # Var-register => eax + (print-int32-buffered *(ebp+8) *eax) + (write-buffered *(ebp+8) "/r32\n") +$translate-mu-compute-index-stmt:end: + # . restore registers + 5b/pop-to-ebx + 5a/pop-to-edx + 59/pop-to-ecx + 58/pop-to-eax + # . epilogue + 89/<- %esp 5/r32/ebp + 5d/pop-to-ebp + c3/return + translate-mu-get-stmt: # out: (address buffered-file), stmt: (handle stmt) # . prologue 55/push-ebp @@ -9114,10 +9253,10 @@ subx-type-equal?: # a: (handle tree type-id), b: (handle tree type-id) -> resul # . save registers 51/push-ecx # var alit/ecx: boolean = is-literal-type?(a) - (is-literal-type? *(ebp+8)) # => eax + (is-simple-mu-type? *(ebp+8) 0) # => eax 89/<- %ecx 0/r32/eax # var blit/eax: boolean = is-literal-type?(b) - (is-literal-type? *(ebp+0xc)) # => eax + (is-simple-mu-type? *(ebp+0xc) 0) # => eax # return alit == blit 39/compare %eax 1/r32/ecx 0f 94/set-if-= %eax @@ -9130,17 +9269,22 @@ $subx-type-equal?:end: 5d/pop-to-ebp c3/return -is-literal-type?: # a: (handle tree type-id) -> result/eax: boolean +is-simple-mu-type?: # a: (handle tree type-id), n: type-id -> result/eax: boolean # . prologue 55/push-ebp 89/<- %ebp 4/r32/esp - # + # . save registers + 51/push-ecx + # ecx = n + 8b/-> *(ebp+0xc) 1/r32/ecx + # return (a->value == n) 8b/-> *(ebp+8) 0/r32/eax - # return (*eax == 0) - 81 7/subop/compare *eax 0/imm32/literal-type-id # Atom-type + 39/compare *eax 1/r32/ecx # Atom-type 0f 94/set-if-= %eax 81 4/subop/and %eax 0xff/imm32 -$is-literal-type?:end: +$is-simple-mu-type?:end: + # . restore registers + 59/pop-to-ecx # . epilogue 89/<- %esp 5/r32/ebp 5d/pop-to-ebp diff --git a/apps/pack b/apps/pack index 8e60d188..ceeeb153 100755 Binary files a/apps/pack and b/apps/pack differ diff --git a/apps/sigils b/apps/sigils index 9dffa2a8..10877010 100755 Binary files a/apps/sigils and b/apps/sigils differ diff --git a/apps/subx-params.subx b/apps/subx-params.subx index 3bc02894..c3827ad7 100644 --- a/apps/subx-params.subx +++ b/apps/subx-params.subx @@ -8,7 +8,7 @@ Segment-size: # maximum size of input textual stream (spanning all segments) Input-size: - 0x180000/imm32/1.5MB + 0x200000/imm32/2MB # number of labels we can translate to addresses Max-labels: diff --git a/apps/survey b/apps/survey index 516ee21b..49905f1a 100755 Binary files a/apps/survey and b/apps/survey differ diff --git a/apps/survey.subx b/apps/survey.subx index fd7b212f..db8fb08c 100644 --- a/apps/survey.subx +++ b/apps/survey.subx @@ -115,7 +115,7 @@ $subx-survey-main:end: subx-survey: # infile: (addr buffered-file), out: (addr buffered-file) # pseudocode - # var in: (stream byte 4096) + # var in: (stream byte Input-size) # slurp(infile, in) # var segments: (stream segment-info) # var labels: (stream label-info Max-labels) diff --git a/apps/tests b/apps/tests index 9f0ea034..39c29b36 100755 Binary files a/apps/tests and b/apps/tests differ diff --git a/mu_instructions b/mu_instructions index 0b6da8b0..c8be987b 100644 --- a/mu_instructions +++ b/mu_instructions @@ -207,13 +207,21 @@ loop-if-addr>= label {.name="loop-if-addr>=", .inouts=[label], Array operations -var/reg <- length var2/reg2: (addr array T) +var/reg <- length arr/reg2: (addr array T) {.name="length", .inouts=[reg2], .outputs=[reg1], .subx-name="8b/copy-from", .rm32="*" inouts[0], .r32=outputs[0]} var/reg <- index arr/rega: (addr array T), idx/regi: int {.name="index", .inouts=[rega, regi], .outputs=[reg], .subx-name="8d/copy-address", .rm32="*(" inouts[0] "+" inouts[1] "<<2)", .r32=outputs[0]} var/reg <- index arr/rega: (addr array T), n -compare var, n {.name="compare", .inouts=[var, n], .subx-name="81 7/subop/compare", .rm32="*(ebp+" inouts[0].stack-offset ")", .imm32=inouts[1]} - {.name="index", .inouts=[rega, n], .outputs=[reg], .subx-name="8d/copy-address", .rm32="*(" inouts[0] "+" inouts[1] "<<2)", .r32=outputs[0]} + {.name="index", .inouts=[rega, n], .outputs=[reg], .subx-name="8d/copy-address", .rm32="*(" inouts[0] "+" inouts[1]*size(T) ")", .r32=outputs[0]} + +var/reg: (offset T) <- compute-offset arr: (addr array T), idx/regi: int # arr can be in reg or mem + {.name="compute-offset", .inouts=[arr, regi], .outputs=[reg], .subx-name="69/multiply", .rm32=inouts[1], .r32=outputs[0], .imm32=sizeof(T)} +var/reg: (offset T) <- compute-offset arr: (addr array T), idx: int # arr can be in reg or mem + {.name="compute-offset", .inouts=[arr, regi], .outputs=[reg], .subx-name="69/multiply", .rm32="*(ebp+" inouts[1].stack-offset ")", .r32=outputs[0], .imm32=sizeof(T)} +var: (offset T) <- compute-offset arr: (addr array T), n # arr can be in reg or mem + {.name="compute-offset", .inouts=[var, n], .outputs=[reg], .subx-name="c7 0/subop/copy", .rm32=outputs[0], .imm32=sizeof(T)*n} +var/reg <- index arr/rega: (addr array T), o/rego: offset + {.name="index", .inouts=[rega, rego], .outputs=[reg], .subx-name="8d/copy-address", .rm32="*(" inouts[0] "+" inouts[1] "+" "4)", .r32=outputs[0]} User-defined types diff --git a/mu_summary b/mu_summary index 179aa11f..e4e82905 100644 --- a/mu_summary +++ b/mu_summary @@ -197,9 +197,14 @@ Similarly, conditional loops: ## Array operations - var/reg: int <- length var: (addr array T) - var/reg: (addr T) <- index var: (addr array T), idx: int - var/reg: (addr T) <- index var: (addr array T), n + var/reg: int <- length arr/reg: (addr array T) + var/reg: (addr T) <- index arr/reg: (addr array T), idx/reg: int + var/reg: (addr T) <- index arr/reg: (addr array T), n + + var/reg: (offset T) <- compute-offset arr: (addr array T), idx/reg: int # arr can be in reg or mem + var/reg: (offset T) <- compute-offset arr: (addr array T), n # arr can be in reg or mem + var: (offset T) <- compute-offset arr: (addr array T), n # arr can be in reg or mem + var/reg: (addr T) <- index arr/reg: (addr array T), idx/reg: (offset T) ## User-defined types -- cgit 1.4.1-2-gfad0