Specialized integer allocator, more speed

6 files changed, 122 insertions, 47 deletions

diff --git a/compiler/elymasAsm.ey b/compiler/elymasAsm.ey
index 760fdcf..c101280 100644
--- a/compiler/elymasAsm.ey
+++ b/compiler/elymasAsm.ey
@@ -415,6 +415,29 @@
     } each
   } /defAsmBtq deff
 
+  { ==opcode2 ==opcode1 ==mnemonic
+    { ==reg1 ==reg2
+      reg2 bit64assert
+      reg1 bit64assert
+
+      1 reg1 /none reg2 rex
+      opcode1
+      opcode2
+      reg1 reg2 modrm11
+    } mnemonic /qRegReg defOp
+
+    memoryAddressingVariants keys { ==variant memoryAddressingVariants variant . =*parse
+      { ==reg parse ==mem
+        reg bit64assert
+
+        1 reg mem .idx mem .base rex
+        opcode1
+        opcode2
+        reg mem .encode
+      } mnemonic /qReg variant cat defOp
+    } each
+  } /defAsmBsfq deff
+
   { ==modrmOpcode ==opcode2 ==opcode1 ==mnemonic
     { ==reg ==i
       reg bit64assert
@@ -450,6 +473,14 @@
   /bt %0F %A3 defAsmBtq
   /bt %0F %BA /four defAsmBtqImm
 
+  /btr %0F %B3 defAsmBtq
+  /btr %0F %BA /six defAsmBtqImm
+
+  /bts %0F %AB defAsmBtq
+  /bts %0F %BA /five defAsmBtqImm
+
+  /bsf %0F %BC defAsmBsfq
+
   { ==off
     %E8
     off imm32
diff --git a/compiler/elymasAsmLib.ey b/compiler/elymasAsmLib.ey
index 0996f41..1c04d4e 100644
--- a/compiler/elymasAsmLib.ey
+++ b/compiler/elymasAsmLib.ey
@@ -198,8 +198,8 @@
       # run through block bitmap until sufficiently many zeroes are found
       # if yes, allocate block
       @searchForFreeBlock
-      # rdi == size of chunk in bytes
-      # rax == address of allocated chunk or zero if no free block was found
+      # rdi -> size of chunk in bytes
+      # rax <- address of allocated chunk or zero if no free block was found
 
       /rax :movqImmOOBReg HEAPBASE
       heapEnd /rbp :movqImmReg
@@ -271,8 +271,7 @@
 
       6 /rbp :shlqImm8Reg
       6 /rax :shlqImm8Reg
-      /rcx /rax :addqRegReg
-      /rax /rbx :movqRegReg
+      /rcx /rax /rbx :leaqMemIndexReg
 
       # rdi == size of block to allocate
       # rbx == last cell of free block of sufficient size
@@ -859,6 +858,73 @@
 
   # TODO: link internal functions statically with relative calls
   <
+    # allocate int
+    # rax <- address of allocated integer
+    #        chunk will have GC length header initialized correctly
+    [[
+      heapEnd /rbp :movqImmReg
+      unusedHeapStart /rcx :movqImmReg
+      /rdx :movqImmOOBReg HEAPBASE
+      0 /rbp /rbp :movqMemDisp8Reg
+      /rcx /rcx :movqMemReg
+      /rdi :movqImmOOBReg BLOCKBASE
+      /rsi :movqImmOOBReg MARKBASE
+      /rdx /rbp :subqRegReg
+      # rbp now holds number of bytes in heap
+      6 /rcx :shrqImm8Reg # extract quadword
+      10 /rbp :shrqImm8Reg
+      # rbp now holds number of quad-words in bitmaps
+
+      @testBlockBitLoop
+      /rcx /rbp :cmpqRegReg
+      /noFreeBlockAvailable :jbeLbl32
+      8 /rcx /rdi /rax :movqMemIndexScaleReg
+      /rax :notqReg
+      8 /rcx /rsi /rax :andqMemIndexScaleReg
+      /rax /rax :bsfqRegReg # find bit with !block & mark -> free
+      /continueTestBlockBitLoop :jzLbl8
+
+      /rax 8 /rcx /rdi :btsqRegMemIndexScale # set block bit of new block
+      /rax 8 /rcx /rsi :btrqRegMemIndexScale # reset mark bit of new block
+
+      # split block if necessary
+      /rax :incqReg
+      6 /rax :btqImm8Reg
+      0 /rcx :adcqImm8Reg
+      %3F /rax :andqImm8Reg
+      /rcx /rbp :cmpqRegReg
+      /dontSplit :jbeLbl8 # next cell outside of heap
+      /rax 8 /rcx /rdi :btqRegMemIndexScale
+      /dontSplit :jcLbl8 # next cell already allocated
+      /rax 8 /rcx /rsi :btsqRegMemIndexScale # set mark bit
+
+      @dontSplit
+      6 /rcx :shlqImm8Reg
+      /rax /rcx :addqRegReg
+      # rcx == cell index of cell after allocated int
+      unusedHeapStart /rax :movqImmReg
+      /rcx /rax :movqRegMem
+
+      /rcx :decqReg
+      # rcx == cell index of allocated int
+      4 /rcx :shlqImm8Reg
+      # rcx == offset of allocated int
+      /rdx /rcx /rax :leaqMemIndexReg
+
+      /rcx :movqImmOOBReg %10 %00 %00 %00 %00 %00 %00 %08 # -> light grep
+      /rcx /rax :movqRegMem # initialize GC header
+      :retn
+
+      @continueTestBlockBitLoop
+      /rcx :incqReg
+      /testBlockBitLoop :jmpLbl8
+
+      @noFreeBlockAvailable
+      10 /rdi :movqImmReg
+      internalAllocate /rax :movqImmReg
+      /rax :jmpqReg
+    ]] /internalAllocateInteger defv
+
     # allocate scope, expecting rdi entries
     # rdi -> expected number of entries
     # rsi -> parent scope
diff --git a/compiler/elymasGlobal.ey b/compiler/elymasGlobal.ey
index f44c86a..9a91aa1 100644
--- a/compiler/elymasGlobal.ey
+++ b/compiler/elymasGlobal.ey
@@ -24,13 +24,10 @@
     [
       /rbx :popqReg
 
-      # allocate result int
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      # allocate result
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
 
-      # type zero does not need to be changed
-
       # actual calculation
       /rcx :popqReg
       8 /rcx /rcx :movqMemDisp8Reg
@@ -534,8 +531,7 @@
       # rdx == correct string index
       24 1 /rdx /rsi /rbx :movzxMem8IndexScaleDisp8Reg64 # use some of the CISC goodness
 
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
       /rax :pushqReg # push integer on the stack
       
@@ -687,8 +683,7 @@
       16 /rax /rbx :movqMemDisp8Reg
 
       @done
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
       /rax :pushqReg # push integer on the stack
       
@@ -882,8 +877,7 @@
       /rax :pushqReg
       /rdi :pushqReg
       # create int
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
       /rbx 8 /rax :movqRegMemDisp8 # store value
       /rdi :popqReg
@@ -960,8 +954,7 @@
       /rbx :popqReg
 
       # allocate result int
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
       # and push to stack
       /rax :pushqReg
@@ -1690,8 +1683,7 @@
         8 /r15 :subqImm8Reg
         /r15 :popqMem
 
-        16 /rdi :movqImmReg
-        ::internalAllocate /rax :movqImmReg
+        ::internalAllocateInteger /rax :movqImmReg
         /rax :callqReg
         /rax :pushqReg
         activation /rdx :movqImmReg
@@ -2141,8 +2133,7 @@
 
       /rdi :pushqReg
       /rcx :pushqReg
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
       /rcx :popqReg
       /rdi :popqReg
@@ -2516,8 +2507,7 @@
       /rbx :popqReg
 
       # allocate result int
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
 
       /rdx :popqReg
@@ -2557,8 +2547,7 @@
       /rbx :popqReg
 
       # allocate result int
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
 
       # type zero does not need to be changed
@@ -2581,8 +2570,7 @@
       /rbx :popqReg
 
       # allocate result int
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
 
       # type zero does not need to be changed
@@ -2605,8 +2593,7 @@
       /rbx :popqReg
 
       # allocate result int
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
 
       # type zero does not need to be changed
diff --git a/compiler/elymasGlobalSysAsm.ey b/compiler/elymasGlobalSysAsm.ey
index e93cd1f..425bada 100644
--- a/compiler/elymasGlobalSysAsm.ey
+++ b/compiler/elymasGlobalSysAsm.ey
@@ -6,8 +6,7 @@
     [[
       /rbx :popqReg
 
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
 
       /rcx :popqReg
@@ -65,8 +64,7 @@
       /r15 :popqMem
 
       2 {
-        16 /rdi :movqImmReg
-        ::internalAllocate /rax :movqImmReg
+        ::internalAllocateInteger /rax :movqImmReg
         /rax :callqReg
 
         8 /r15 :subqImm8Reg
@@ -116,8 +114,7 @@
     [[
       /rbx :popqReg
       # allocate return integer
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
       /rax :pushqReg
 
@@ -139,8 +136,7 @@
       /rbx :popqReg
 
       # allocate return integer
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
 
       /rcx :popqReg
@@ -167,8 +163,7 @@
       /rbx :popqReg
 
       # allocate return integer
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
 
       /rcx :popqReg
@@ -195,8 +190,7 @@
       /rbx :popqReg
 
       # allocate return integer
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
 
       /rdx :popqReg
@@ -269,8 +263,7 @@
       /rdx :pushqReg # store allocation count for later return value
       /rdx 101 /rax :movqRegMemDisp8
 
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
       # type zero does not need to be changed
       /rdx :popqReg
diff --git a/compiler/elymasGlobalSysTyped.ey b/compiler/elymasGlobalSysTyped.ey
index bdc88d0..298dba8 100644
--- a/compiler/elymasGlobalSysTyped.ey
+++ b/compiler/elymasGlobalSysTyped.ey
@@ -45,8 +45,7 @@
     [[
       /rbx :popqReg
 
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
 
       /rdx :popqReg
diff --git a/compiler/elymasLexer.ey b/compiler/elymasLexer.ey
index 77ae81b..1ca264b 100644
--- a/compiler/elymasLexer.ey
+++ b/compiler/elymasLexer.ey
@@ -7,8 +7,7 @@
   { .value elymas .base10decode ==v
     [
       # allocate int
-      16 /rdi :movqImmReg
-      ::internalAllocate /rax :movqImmReg
+      ::internalAllocateInteger /rax :movqImmReg
       /rax :callqReg
 
       # push int address on program stack