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.

2 files changed, 211 insertions, 23 deletions

diff --git a/apps/mu b/apps/mu
index 9c61873b..ca2de6b0 100755
--- a/apps/mu
+++ b/apps/mu
Binary files differdiff --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