Some optimizations to the allocator

2 files changed, 96 insertions, 25 deletions

diff --git a/compiler/elymasAsm.ey b/compiler/elymasAsm.ey
index 2d9f7b8..0148faa 100644
--- a/compiler/elymasAsm.ey
+++ b/compiler/elymasAsm.ey
@@ -392,6 +392,54 @@
     reg mem modrm00
   } /addlMemReg deff
 
+  { ==opcode2 ==opcode1 ==mnemonic
+    { ==reg2 ==reg1
+      reg2 bit64assert
+      reg1 bit64assert
+
+      1 reg1 /none reg2 rex
+      opcode1
+      opcode2
+      reg1 reg2 modrm11
+    } mnemonic /qRegReg defOp
+
+    memoryAddressingVariants keys { ==variant memoryAddressingVariants variant . =*parse
+      { parse ==mem ==reg
+        reg bit64assert
+
+        1 reg mem .idx mem .base rex
+        opcode1
+        opcode2
+        reg mem .encode
+      } mnemonic /qReg variant cat defOp
+    } each
+  } /defAsmBtq deff
+
+  { ==modrmOpcode ==opcode2 ==opcode1 ==mnemonic
+    { ==reg ==i
+      reg bit64assert
+
+      1 /none /none reg rex
+      opcode1
+      opcode2
+      modrmOpcode reg modrm11
+      i imm8
+    } mnemonic /qImm8Reg defOp
+
+    memoryAddressingVariants keys { ==variant memoryAddressingVariants variant . =*parse
+      { parse ==mem ==imm
+        1 /none mem .idx mem .base rex
+        opcode1
+        opcode2
+        modrmOpcode mem .encode
+        imm imm8
+      } mnemonic /qImm8 variant cat defOp
+    } each
+  } /defAsmBtqImm deff
+
+  /adc %11 defAsmAddq
+  /adc /two defAsmAddImm
+
   /add %01 defAsmAddq
   /add /zero defAsmAddImm
 
@@ -399,6 +447,9 @@
   /and %21 defAsmAddq
   /and /four defAsmAddImm
 
+  /bt %0F %A3 defAsmBtq
+  /bt %0F %BA /four defAsmBtqImm
+
   { ==off
     %E8
     off imm32
diff --git a/compiler/elymasAsmLib.ey b/compiler/elymasAsmLib.ey
index c8565ee..0e77994 100644
--- a/compiler/elymasAsmLib.ey
+++ b/compiler/elymasAsmLib.ey
@@ -212,49 +212,66 @@
       # /rbx /rbx :xorqRegReg
       # rbx == index of cell currently tested
 
-      @startFreeBlockScan
-      /rsi /rsi :xorqRegReg
-      # rsi > 0  =>  currently counting block extent of free block
+      /r8 :pushqReg
+      /r9 :pushqReg
+
+      /r8 :movqImmOOBReg BLOCKBASE
+      /r9 :movqImmOOBReg MARKBASE
 
-      @testBlockBitLoop
       /rbx /rbp :cmpqRegReg
       /noFreeBlockAvailable :jbeLbl32
 
       /rbx /rax :movqRegReg
-      3 /rax :shrqImm8Reg # extract byte
-      /rdx :movqImmOOBReg BLOCKBASE
-      /rdx /rax /al :movbMemIndexReg
       /rbx /rcx :movqRegReg
-      7 /cl :andbImmReg
-      /cl :incbReg
-      /rax :shrqClReg
+      %3F /rcx :andqImm8Reg # extract bit position in quadword
+      6 /rax :shrqImm8Reg # extract quadword
+      6 /rbp :shrqImm8Reg # extract one-after-last quadword
+
+      /rsi /rsi :xorqRegReg
+      # rsi > 0  =>  currently counting block extent of free block
+
+      @testBlockBitLoop
+      /rcx 8 /rax /r8 :btqRegMemIndexScale # test block bitmap
       /nonFreeBlock :jcLbl8 # block not free
       /rsi /rsi :andqRegReg
-      /currentlyCounting :jnzLbl8
-
-      /rbx /rax :movqRegReg
-      3 /rax :shrqImm8Reg # extract byte
-      /rdx :movqImmOOBReg MARKBASE
-      /rdx /rax /al :movbMemIndexReg
-      /rbx /rcx :movqRegReg
-      7 /cl :andbImmReg
-      /cl :incbReg
-      /rax :shrqClReg
-      /nonFreeBlock :jncLbl8 # block not marked, i.e. just block extent
+      /notCurrentlyCounting :jzLbl8
 
       @currentlyCounting
       16 /rsi :addqImm8Reg
       /rsi /rdi :cmpqRegReg
       /freeBlockFound :jbeLbl8
 
-      /rbx :incqReg
-      /testBlockBitLoop :jmpLbl8
+      /rcx :incqReg
+      6 /rcx :btqImm8Reg
+      0 /rax :adcqImm8Reg
+      %3F /rcx :andqImm8Reg
+      /rax /rbp :cmpqRegReg
+      /testBlockBitLoop :jaLbl8
+      /noFreeBlockAvailable :jmpLbl32
+
+      @notCurrentlyCounting
+      /rcx 8 /rax /r9 :btqRegMemIndexScale # test mark bitmap
+      /currentlyCounting :jcLbl8 # block marked, i.e. truly free block start
 
       @nonFreeBlock
-      /rbx :incqReg
-      /startFreeBlockScan :jmpLbl8
+      /rsi /rsi :xorqRegReg
+      /rcx :incqReg
+      6 /rcx :btqImm8Reg
+      0 /rax :adcqImm8Reg
+      %3F /rcx :andqImm8Reg
+      /rax /rbp :cmpqRegReg
+      /testBlockBitLoop :jaLbl8
+      /noFreeBlockAvailable :jmpLbl32
 
       @freeBlockFound
+      /r9 :popqReg
+      /r8 :popqReg
+
+      6 /rbp :shlqImm8Reg
+      6 /rax :shlqImm8Reg
+      /rcx /rax :addqRegReg
+      /rax /rbx :movqRegReg
+
       # rdi == size of block to allocate
       # rbx == last cell of free block of sufficient size
 
@@ -353,6 +370,9 @@
       :retn
 
       @noFreeBlockAvailable
+      /r9 :popqReg
+      /r8 :popqReg
+
       /rax /rax :xorqRegReg
       :retn