From 0c89528a388ef823c58d5b44239696128f6e3d37 Mon Sep 17 00:00:00 2001 From: Kartik Agaram Date: Thu, 5 Mar 2020 18:01:59 -0800 Subject: 6079 - optimize register spills The second var to the same register in a block doesn't need to spill. We're never going to restore the var it's shadowing. --- apps/mu | Bin 163670 -> 165475 bytes apps/mu.subx | 234 +++++++++++++++++++++++++++++++++++++++++++++++++++++------ 2 files changed, 211 insertions(+), 23 deletions(-) diff --git a/apps/mu b/apps/mu index 9c61873b..ca2de6b0 100755 Binary files a/apps/mu and b/apps/mu differ diff --git a/apps/mu.subx b/apps/mu.subx index 57ae56bc..e8c1ebb5 100644 --- a/apps/mu.subx +++ b/apps/mu.subx @@ -961,6 +961,54 @@ test-convert-function-with-local-var-in-reg: 5d/pop-to-ebp c3/return +test-convert-function-with-second-local-var-in-same-reg: + # . 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 x/ecx: int <- copy 3\n") + (write _test-input-stream " var y/ecx: int <- copy 4\n") + (write _test-input-stream " y <- increment\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-function-with-second-local-var-in-same-reg/0") + (check-next-stream-line-equal _test-output-stream " # . prologue" "F - test-convert-function-with-second-local-var-in-same-reg/1") + (check-next-stream-line-equal _test-output-stream " 55/push-ebp" "F - test-convert-function-with-second-local-var-in-same-reg/2") + (check-next-stream-line-equal _test-output-stream " 89/<- %ebp 4/r32/esp" "F - test-convert-function-with-second-local-var-in-same-reg/3") + (check-next-stream-line-equal _test-output-stream " {" "F - test-convert-function-with-second-local-var-in-same-reg/4") + (check-next-stream-line-equal _test-output-stream "$foo:0x00000001:loop:" "F - test-convert-function-with-second-local-var-in-same-reg/5") + (check-next-stream-line-equal _test-output-stream " ff 6/subop/push %ecx" "F - test-convert-function-with-second-local-var-in-same-reg/6") + (check-next-stream-line-equal _test-output-stream " b9/copy-to-ecx 3/imm32" "F - test-convert-function-with-second-local-var-in-same-reg/7") + (check-next-stream-line-equal _test-output-stream " b9/copy-to-ecx 4/imm32" "F - test-convert-function-with-second-local-var-in-same-reg/8") + (check-next-stream-line-equal _test-output-stream " 41/increment-ecx" "F - test-convert-function-with-second-local-var-in-same-reg/9") + (check-next-stream-line-equal _test-output-stream " 8f 0/subop/pop %ecx" "F - test-convert-function-with-second-local-var-in-same-reg/10") + (check-next-stream-line-equal _test-output-stream " }" "F - test-convert-function-with-second-local-var-in-same-reg/11") + (check-next-stream-line-equal _test-output-stream "$foo:0x00000001:break:" "F - test-convert-function-with-second-local-var-in-same-reg/12") + (check-next-stream-line-equal _test-output-stream " # . epilogue" "F - test-convert-function-with-second-local-var-in-same-reg/13") + (check-next-stream-line-equal _test-output-stream " 89/<- %esp 5/r32/ebp" "F - test-convert-function-with-second-local-var-in-same-reg/14") + (check-next-stream-line-equal _test-output-stream " 5d/pop-to-ebp" "F - test-convert-function-with-second-local-var-in-same-reg/15") + (check-next-stream-line-equal _test-output-stream " c3/return" "F - test-convert-function-with-second-local-var-in-same-reg/16") + # . epilogue + 89/<- %esp 5/r32/ebp + 5d/pop-to-ebp + c3/return + test-convert-function-with-local-var-dereferenced: # . prologue 55/push-ebp @@ -1902,9 +1950,7 @@ test-convert-length-of-array: (check-next-stream-line-equal _test-output-stream "$foo:0x00000001:loop:" "F - test-convert-length-of-array/5") (check-next-stream-line-equal _test-output-stream " ff 6/subop/push %eax" "F - test-convert-length-of-array/6") (check-next-stream-line-equal _test-output-stream " 8b/copy-from *(ebp+0x00000008) 0x00000000/r32" "F - test-convert-length-of-array/7") - (check-next-stream-line-equal _test-output-stream " ff 6/subop/push %eax" "F - test-convert-length-of-array/8") (check-next-stream-line-equal _test-output-stream " 8b/copy-from *eax 0x00000000/r32" "F - test-convert-length-of-array/9") - (check-next-stream-line-equal _test-output-stream " 8f 0/subop/pop %eax" "F - test-convert-length-of-array/10") (check-next-stream-line-equal _test-output-stream " 8f 0/subop/pop %eax" "F - test-convert-length-of-array/11") (check-next-stream-line-equal _test-output-stream " }" "F - test-convert-length-of-array/12") (check-next-stream-line-equal _test-output-stream "$foo:0x00000001:break:" "F - test-convert-length-of-array/13") @@ -1953,9 +1999,7 @@ test-convert-index-into-array: (check-next-stream-line-equal _test-output-stream " b8/copy-to-eax 0/imm32" "F - test-convert-index-into-array/7") (check-next-stream-line-equal _test-output-stream " ff 6/subop/push %ecx" "F - test-convert-index-into-array/8") (check-next-stream-line-equal _test-output-stream " b9/copy-to-ecx 3/imm32" "F - test-convert-index-into-array/9") - (check-next-stream-line-equal _test-output-stream " ff 6/subop/push %eax" "F - test-convert-index-into-array/10") (check-next-stream-line-equal _test-output-stream " 8d/copy-address *(eax + ecx<<0x00000002 + 4) 0x00000000/r32" "F - test-convert-index-into-array/11") - (check-next-stream-line-equal _test-output-stream " 8f 0/subop/pop %eax" "F - test-convert-index-into-array/12") (check-next-stream-line-equal _test-output-stream " 8f 0/subop/pop %ecx" "F - test-convert-index-into-array/13") (check-next-stream-line-equal _test-output-stream " 8f 0/subop/pop %eax" "F - test-convert-index-into-array/14") (check-next-stream-line-equal _test-output-stream " }" "F - test-convert-index-into-array/15") @@ -2009,9 +2053,7 @@ test-convert-function-and-type-definition: (check-next-stream-line-equal _test-output-stream " 8b/copy-from *(ebp+0x00000008) 0x00000000/r32" "F - test-convert-function-and-type-definition/7") (check-next-stream-line-equal _test-output-stream " ff 6/subop/push %ecx" "F - test-convert-function-and-type-definition/8") (check-next-stream-line-equal _test-output-stream " 8d/copy-address *(eax + 0x00000000) 0x00000001/r32" "F - test-convert-function-and-type-definition/9") - (check-next-stream-line-equal _test-output-stream " ff 6/subop/push %ecx" "F - test-convert-function-and-type-definition/10") (check-next-stream-line-equal _test-output-stream " 8d/copy-address *(eax + 0x00000004) 0x00000001/r32" "F - test-convert-function-and-type-definition/11") - (check-next-stream-line-equal _test-output-stream " 8f 0/subop/pop %ecx" "F - test-convert-function-and-type-definition/12") (check-next-stream-line-equal _test-output-stream " 8f 0/subop/pop %ecx" "F - test-convert-function-and-type-definition/13") (check-next-stream-line-equal _test-output-stream " 8f 0/subop/pop %eax" "F - test-convert-function-and-type-definition/14") (check-next-stream-line-equal _test-output-stream " }" "F - test-convert-function-and-type-definition/15") @@ -2113,9 +2155,7 @@ test-convert-array-of-user-defined-types: (check-next-stream-line-equal _test-output-stream " b8/copy-to-eax 0/imm32" "F - test-convert-array-of-user-defined-types/7") (check-next-stream-line-equal _test-output-stream " ff 6/subop/push %ecx" "F - test-convert-array-of-user-defined-types/8") (check-next-stream-line-equal _test-output-stream " b9/copy-to-ecx 3/imm32" "F - test-convert-array-of-user-defined-types/9") - (check-next-stream-line-equal _test-output-stream " ff 6/subop/push %eax" "F - test-convert-array-of-user-defined-types/10") (check-next-stream-line-equal _test-output-stream " 8d/copy-address *(eax + ecx<<0x00000003 + 4) 0x00000000/r32" "F - test-convert-array-of-user-defined-types/11") - (check-next-stream-line-equal _test-output-stream " 8f 0/subop/pop %eax" "F - test-convert-array-of-user-defined-types/12") (check-next-stream-line-equal _test-output-stream " 8f 0/subop/pop %ecx" "F - test-convert-array-of-user-defined-types/13") (check-next-stream-line-equal _test-output-stream " 8f 0/subop/pop %eax" "F - test-convert-array-of-user-defined-types/14") (check-next-stream-line-equal _test-output-stream " }" "F - test-convert-array-of-user-defined-types/15") @@ -5685,7 +5725,7 @@ $emit-subx-stmt-list:check-for-reg-var-def: 0f 85/jump-if-!= break/disp32 $emit-subx-stmt-list:reg-var-def: # TODO: ensure that there's exactly one output - (compute-reg-and-maybe-emit-spill *(ebp+8) %ecx) + (compute-reg-and-maybe-emit-spill *(ebp+8) %ecx *(ebp+0x10)) # register variable definition (push *(ebp+0x10) %eax) # emit the instruction as usual @@ -5714,7 +5754,7 @@ $emit-subx-stmt-list:end: 5d/pop-to-ebp c3/return -compute-reg-and-maybe-emit-spill: # out: (addr buffered-file), stmt: (handle reg-var-def) -> result/eax: (handle var) +compute-reg-and-maybe-emit-spill: # out: (addr buffered-file), stmt: (handle reg-var-def), vars: (addr stack (handle var)) -> result/eax: (handle var) # . prologue 55/push-ebp 89/<- %ebp 4/r32/esp @@ -5729,14 +5769,18 @@ compute-reg-and-maybe-emit-spill: # out: (addr buffered-file), stmt: (handle re 8b/-> *(ecx+0x10) 0/r32/eax # Var-register # ensure that output is in a register 3d/compare-eax-and 0/imm32 - 0f 84/jump-if-= $compute-reg-and-maybe-emit-spill:abort-reg-var-def-without-register/disp32 + 0f 84/jump-if-= $compute-reg-and-maybe-emit-spill:abort/disp32 + # if already-spilled-this-block?(reg, vars) return + (already-spilled-this-block? %eax *(ebp+0x10)) # => eax + 3d/compare-eax-and 0/imm32/false + 75/jump-if-!= $compute-reg-and-maybe-emit-spill:end/disp8 # emit spill (emit-indent *(ebp+8) *Curr-block-depth) (write-buffered *(ebp+8) "ff 6/subop/push %") - (write-buffered *(ebp+8) %eax) + (write-buffered *(ebp+8) *(ecx+0x10)) # Var-register (write-buffered *(ebp+8) Newline) $compute-reg-and-maybe-emit-spill:end: - # return ecx + # return output 89/<- %eax 1/r32/ecx # . restore registers 59/pop-to-ecx @@ -5745,7 +5789,7 @@ $compute-reg-and-maybe-emit-spill:end: 5d/pop-to-ebp c3/return -$compute-reg-and-maybe-emit-spill:abort-reg-var-def-without-register: +$compute-reg-and-maybe-emit-spill:abort: # error("var '" var->name "' initialized from an instruction must live in a register\n") (write-buffered Stderr "var '") (write-buffered Stderr *eax) # Var-name @@ -5978,12 +6022,21 @@ $emit-cleanup-code-until-depth:loop: # if v is in a register 81 7/subop/compare *(ebx+0x10) 0/imm32 # Var-register { - 74/jump-if-= break/disp8 + 0f 84/jump-if-= break/disp32 + 50/push-eax + { +$emit-cleanup-code-until-depth:check-for-previous-spill: + (same-register-spilled-before? %ebx *(ebp+0xc)) # => eax + 3d/compare-eax-and 0/imm32/false + 0f 85/jump-if-!= break/disp32 $emit-cleanup-code-until-depth:reclaim-var-in-register: - (emit-indent *(ebp+8) *Curr-block-depth) - (write-buffered *(ebp+8) "8f 0/subop/pop %") - (write-buffered *(ebp+8) *(ebx+0x10)) - (write-buffered *(ebp+8) Newline) + (emit-indent *(ebp+8) *Curr-block-depth) + (write-buffered *(ebp+8) "8f 0/subop/pop %") + (write-buffered *(ebp+8) *(ebx+0x10)) + (write-buffered *(ebp+8) Newline) + } + 58/pop-to-eax + eb/jump $emit-cleanup-code-until-depth:continue/disp8 } # otherwise v is on the stack { @@ -6001,6 +6054,7 @@ $emit-cleanup-code-until-depth:reclaim-var-on-stack: (write-buffered *(ebp+8) "/imm32\n") 58/pop-to-eax } +$emit-cleanup-code-until-depth:continue: # curr -= 4 2d/subtract-from-eax 4/imm32 e9/jump loop/disp32 @@ -6051,11 +6105,20 @@ $emit-cleanup-code-until-target:loop: 81 7/subop/compare *(ebx+0x10) 0/imm32 # Var-register { 74/jump-if-= break/disp8 + 50/push-eax + { +$emit-cleanup-code-until-target:check-for-previous-spill: + (same-register-spilled-before? %ebx *(ebp+0xc) %edx) # => eax + 3d/compare-eax-and 0/imm32/false + 75/jump-if-!= break/disp8 $emit-cleanup-code-until-target:reclaim-var-in-register: - (emit-indent *(ebp+8) *Curr-block-depth) - (write-buffered *(ebp+8) "8f 0/subop/pop %") - (write-buffered *(ebp+8) *(ebx+0x10)) - (write-buffered *(ebp+8) Newline) + (emit-indent *(ebp+8) *Curr-block-depth) + (write-buffered *(ebp+8) "8f 0/subop/pop %") + (write-buffered *(ebp+8) *(ebx+0x10)) + (write-buffered *(ebp+8) Newline) + } + 58/pop-to-eax + eb/jump $emit-cleanup-code-until-target:continue/disp8 } # otherwise v is on the stack { @@ -6071,6 +6134,7 @@ $emit-cleanup-code-until-target:reclaim-var-on-stack: (print-int32-buffered *(ebp+8) %eax) (write-buffered *(ebp+8) "/imm32\n") } +$emit-cleanup-code-until-target:continue: # curr -= 4 81 5/subop/subtract %edx 4/imm32 e9/jump loop/disp32 @@ -6086,6 +6150,130 @@ $emit-cleanup-code-until-target:end: 5d/pop-to-ebp c3/return +# is there already a var with the same block-depth and register as 'v' on the 'vars' stack? +# v is guaranteed not to be within vars +already-spilled-this-block?: # v: (handle var), vars: (addr stack (handle var)) -> result/eax: boolean + # . prologue + 55/push-ebp + 89/<- %ebp 4/r32/esp + # . save registers + 51/push-ecx + 52/push-edx + 56/push-esi + 57/push-edi + # ecx = vars + 8b/-> *(ebp+0xc) 1/r32/ecx + # var eax: int = vars->top + 8b/-> *ecx 0/r32/eax + # var min/ecx: (address (handle var)) = vars->data + 81 0/subop/add %ecx 8/imm32 + # var curr/edx: (address (handle var)) = &vars->data[vars->top - 4] + 81 5/subop/subtract %eax 4/imm32 + 8d/copy-address *(ecx+eax) 2/r32/edx + # var needle/esi: (handle array byte) = v->register + 8b/-> *(ebp+8) 6/r32/esi + 8b/-> *(esi+0x10) 3/r32/esi # Var-register + { +$already-spilled-this-block?:loop: + # if (curr < min) break + 39/compare %edx 1/r32/ecx + 0f 82/jump-if-addr< break/disp32 + # var cand/edi: (handle var) = *curr + 8b/-> *edx 7/r32/edi + # var cand-reg/ebx: (handle array byte) = v->reg + 8b/-> *(edi+0x10) 7/r32/edi + # if (cand-reg == null) continue + { + 81 7/subop/compare %edi 0/imm32 + 74/jump-if-= break/disp8 + # if (cand-reg == needle) return true + (string-equal? %esi %edi) # => eax + 3d/compare-eax-and 0/imm32/false + 74/jump-if-= break/disp8 + b8/copy-to-eax 1/imm32/true + eb/jump $already-spilled-this-block?:end/disp8 + } +$already-spilled-this-block?:continue: + # curr -= 4 + 81 5/subop/subtract %edx 4/imm32 + e9/jump loop/disp32 + } + # return false + b8/copy-to-eax 0/imm32/false +$already-spilled-this-block?:end: + # . restore registers + 5f/pop-to-edi + 5e/pop-to-esi + 5a/pop-to-edx + 59/pop-to-ecx + # . epilogue + 89/<- %esp 5/r32/ebp + 5d/pop-to-ebp + c3/return + +# is there a var before 'v' with the same block-depth and register on the 'vars' stack? +# v is guaranteed to be within vars +# 'start' is provided as an optimization, a pointer within vars +# *start == v +same-register-spilled-before?: # v: (handle var), vars: (addr stack (handle var)), start: (addr (handle var)) -> result/eax: boolean + # . prologue + 55/push-ebp + 89/<- %ebp 4/r32/esp + # . save registers + 51/push-ecx + 52/push-edx + 53/push-ebx + 56/push-esi + 57/push-edi + # ecx = v + 8b/-> *(ebp+8) 1/r32/ecx + # var reg/edx: (handle array byte) = v->register + 8b/-> *(ecx+0x10) 2/r32/edx # Var-register + # var depth/ebx: int = v->block-depth + 8b/-> *(ecx+8) 3/r32/ebx # Var-block-depth + # var min/ecx: (address (handle var)) = vars->data + 8b/-> *(ebp+0xc) 1/r32/ecx + 81 0/subop/add %ecx 8/imm32 + # TODO: check that start >= min and start < &vars->data[top] + # TODO: check that *start == v + # var curr/esi: (address (handle var)) = start + 8b/-> *(ebp+0x10) 6/r32/esi + # curr -= 4 + 81 5/subop/subtract %esi 4/imm32 + { +$same-register-spilled-before?:loop: + # if (curr < min) break + 39/compare %esi 1/r32/ecx + 0f 82/jump-if-addr< break/disp32 +$same-register-spilled-before?:aa: + # var x/eax: (handle var) = *curr + 8b/-> *esi 0/r32/eax + # if (x->block-depth < depth) break + 39/compare *(eax+8) 3/r32/ebx # Var-block-depth + 0f 8c/jump-if-< break/disp32 +$same-register-spilled-before?:bb: + # if (x->register == reg) return true + (string-equal? *(eax+0x10) %edx) # Var-register => eax + 3d/compare-eax-and 0/imm32/false + 75/jump-if-!= $same-register-spilled-before?:end/disp8 + # curr -= 4 + 81 5/subop/subtract %esi 4/imm32 + e9/jump loop/disp32 + } +$same-register-spilled-before?:false: + b8/copy-to-eax 0/imm32/false +$same-register-spilled-before?:end: + # . restore registers + 5f/pop-to-edi + 5e/pop-to-esi + 5b/pop-to-ebx + 5a/pop-to-edx + 59/pop-to-ecx + # . epilogue + 89/<- %esp 5/r32/ebp + 5d/pop-to-ebp + c3/return + # clean up global state for 'vars' until some block depth clean-up-blocks: # vars: (addr stack (handle var)), until-block-depth: int # . prologue -- cgit 1.4.1-2-gfad0