diff options
| -rw-r--r-- | TODO | 1 | ||||
| -rwxr-xr-x | compiler/elymas.ey | 3 | ||||
| -rw-r--r-- | compiler/elymasAsm.ey | 9 | ||||
| -rw-r--r-- | compiler/elymasAsmLib.ey | 533 | ||||
| -rw-r--r-- | compiler/elymasAsmOps.ey | 10 | ||||
| -rw-r--r-- | compiler/elymasGlobal.ey | 225 | ||||
| -rw-r--r-- | doc/notes | 62 |
7 files changed, 673 insertions, 170 deletions
@@ -1,4 +1,3 @@ -* hashed nametables * make '' applicable to arrays, too, i.e. save input type * utf8 * glob diff --git a/compiler/elymas.ey b/compiler/elymas.ey index fd0a3db..42cf217 100755 --- a/compiler/elymas.ey +++ b/compiler/elymas.ey @@ -1,6 +1,9 @@ #!/home/drahflow/elymas/interpreter/elymas "standard.ey" include + +1 ==ASSERTIONS + "elymasGlobal.ey" include "elymasTokenize.ey" include "elymasLexer.ey" include diff --git a/compiler/elymasAsm.ey b/compiler/elymasAsm.ey index ff57627..e792b21 100644 --- a/compiler/elymasAsm.ey +++ b/compiler/elymasAsm.ey @@ -6,12 +6,15 @@ 6148914691236517205 ==STACKBOTTOMMARKER 4 ==ERRORMARKER + 3 ==HASHPOSITIONS # number of positions to probe on collisions # hex decoding { - "(.)(.)" regex { } { "not a valid hex-string" die } ? * - { { eq }_ [ "0" "1" "2" "3" "4" "5" "6" "7" "8" "9" "A" "B" "C" "D" "E" "F" ] -01 index } - -20*10* 16 mul add + 0 -01 { "(.)(.*)" regex } { + { 16 mul } + { { eq }_ [ "0" "1" "2" "3" "4" "5" "6" "7" "8" "9" "A" "B" "C" "D" "E" "F" ] -01 index add } + -41*20*3 + } loop } "%" defq "elymasAsmOps.ey" include diff --git a/compiler/elymasAsmLib.ey b/compiler/elymasAsmLib.ey index 71763c6..b2a2e59 100644 --- a/compiler/elymasAsmLib.ey +++ b/compiler/elymasAsmLib.ey @@ -136,6 +136,7 @@ } /unboxInteger deff # internal functions, ABI follows SysV standards + # except that r8-r15 are also callee-saved < # dump string to stderr for internal error reporting @@ -149,24 +150,185 @@ :retn ] /internalDumpErrorString defv - # compare two strings - # rdi -> address of first string - # rsi -> address of second string - # rax <- 1 if both strings are equal, 0 otherwise - [ - /rax /rax :xorqRegReg - :cmpsq # ignore memory length header - :cmpsq # ignore hash - /rsi /rdx :movqMemReg # load exact length - :cmpsq # same exact length - /fail :jnzLbl8 - /rdx /rcx :movqRegReg - :repz :cmpsb - /fail :jnzLbl8 - /rax :incqReg - @fail + # rdi -> string to hash + # rax <- hash value + # This is (or should be) MurmurHash3_x64_128 + [[ + /rbx :pushqReg + /r8 :pushqReg + /r9 :pushqReg + /r10 :pushqReg + /r11 :pushqReg + /r12 :pushqReg + /r13 :pushqReg + + # const uint8_t * data = (const uint8_t*)key; + 24 /rdi /rsi :leaqMemDisp8Reg + + # uint64_t h1 = seed; + /r12 /r12 :xorqRegReg + # uint64_t h2 = seed; + /r13 /r13 :xorqRegReg + + # const uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5); + /r8 :movqImmOOBReg [ %87 %C3 %7B %91 %11 %42 %53 %D5 ] reverse 8 dearray + # const uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f); + /r9 :movqImmOOBReg [ %4C %F5 %AD %43 %27 %45 %93 %7F ] reverse 8 dearray + + # const int nblocks = len / 16; + 16 /rdi /rcx :movqMemDisp8Reg + 16 /rcx :subqImm8Reg + /blockLoopFinished :jbLbl8 + + # //---------- body + + # const uint64_t * blocks = (const uint64_t *)(data); + + # for(int i = 0; i < nblocks; i++) { + + @blockLoop + + /rsi /rax :movqMemReg # uint64_t k1 = getblock64(blocks,i*2+0); + /r8 :mulqReg # k1 *= c1; + 31 /rax :rolqImm8Reg # k1 = ROTL64(k1,31); + /r9 :mulqReg # k1 *= c2; + + /rax /r12 :xorqRegReg # h1 ^= k1; + 27 /r12 :rolqImm8Reg # h1 = ROTL64(h1,27); + /r13 /r12 :addqRegReg # h1 += h2; + %52DCE729 4 /r12 /r12 /r12 :leaqMemIndexScaleDisp32Reg # h1 = h1*5+0x52dce729; + + 8 /rsi /rax :movqMemDisp8Reg # uint64_t k2 = getblock64(blocks,i*2+1); + /r9 :mulqReg # k2 *= c2; + 33 /rax :rolqImm8Reg # k2 = ROTL64(k2,33); + /r8 :mulqReg # k2 *= c1; + /rax /r13 :xorqRegReg # h2 ^= k2; + + 31 /r13 :rolqImm8Reg # h2 = ROTL64(h2,31); + /r12 /r13 :addqRegReg # h2 += h1; + %38495AB5 4 /r13 /r13 /r13 :leaqMemIndexScaleDisp32Reg # h2 = h2*5+0x38495ab5; + + 16 /rsi :addqImm8Reg + 16 /rcx :subqImm8Reg + /blockLoop :jaeLbl8 + # } + + @blockLoopFinished + 16 /rcx :addqImm8Reg + /finalize :jzLbl8 + + # //---------- tail + + /rcx /rbp :movqRegReg + + # const uint8_t * tail = (const uint8_t*)(data + nblocks*16); + + # switch(len & 15) + # { + # case 8: k1 ^= ((uint64_t)tail[ 7]) << 56; + # case 7: k1 ^= ((uint64_t)tail[ 6]) << 48; + # case 6: k1 ^= ((uint64_t)tail[ 5]) << 40; + # case 5: k1 ^= ((uint64_t)tail[ 4]) << 32; + # case 4: k1 ^= ((uint64_t)tail[ 3]) << 24; + # case 3: k1 ^= ((uint64_t)tail[ 2]) << 16; + # case 2: k1 ^= ((uint64_t)tail[ 1]) << 8; + # case 1: k1 ^= ((uint64_t)tail[ 0]) << 0; + 1 /rax :movqImmReg + 2 /rcx :shlqImm8Reg + /rax :shlqClReg + /rax :shlqClReg # support 64bit shift + /rax :decqReg # rax == bitmask for selection + /rsi /rax :andqMemReg + + /r8 :mulqReg # k1 *= c1; + 31 /rax :rolqImm8Reg # k1 = ROTL64(k1,31); + /r9 :mulqReg # k1 *= c2; + /rax /r12 :xorqRegReg # h1 ^= k1; + + 8 /rbp :subqImm8Reg + /finalize :jbeLbl8 + 8 /rsi :addqImm8Reg + + # case 15: k2 ^= ((uint64_t)tail[14]) << 48; + # case 14: k2 ^= ((uint64_t)tail[13]) << 40; + # case 13: k2 ^= ((uint64_t)tail[12]) << 32; + # case 12: k2 ^= ((uint64_t)tail[11]) << 24; + # case 11: k2 ^= ((uint64_t)tail[10]) << 16; + # case 10: k2 ^= ((uint64_t)tail[ 9]) << 8; + # case 9: k2 ^= ((uint64_t)tail[ 8]) << 0; + /rbp /rcx :movqRegReg + 1 /rax :movqImmReg + 3 /rcx :shlqImm8Reg + /rax :shlqImm8Reg + /rax :decqReg # rax == bitmask for selection + /rsi /rax :andqMemReg + + /r9 :mulqReg # k2 *= c2; + 33 /rax :rolqImm8Reg # k2 = ROTL64(k2,33); + /r8 :mulqReg # k2 *= c1; + /rax /r13 :xorqRegReg # h2 ^= k2; + + # }; + + # //---------- finalization + @finalize + + 16 /rdi /r12 :xorqMemDisp8Reg # h1 ^= len; + 16 /rdi /r13 :xorqMemDisp8Reg # h2 ^= len; + + /r13 /r12 :addqRegReg # h1 += h2; + /r12 /r13 :addqRegReg # h2 += h1; + + %85EBCA6B /r8 :movqImmReg + %C2B2AE35 /r9 :movqImmReg + # h1 = fmix64(h1); + /r12 /rax :movqRegReg + 16 /r12 :shrqImm8Reg + /r12 /rax :xorqRegReg + # h ^= h >> 16; + /r8 :mulqReg # h *= 0x85ebca6b; + /rax /r12 :movqRegReg + 13 /r12 :shrqImm8Reg + /r12 /rax :xorqRegReg + # h ^= h >> 13; + /r9 :mulqReg # h *= 0xc2b2ae35; + /rax /r12 :movqRegReg + 16 /r12 :shrqImm8Reg + /rax /r12 :xorqRegReg + # h ^= h >> 16; + + # h2 = fmix64(h2); + /r13 /rax :movqRegReg + 16 /r13 :shrqImm8Reg + /r13 /rax :xorqRegReg + # h ^= h >> 16; + /r8 :mulqReg # h *= 0x85ebca6b; + /rax /r13 :movqRegReg + 13 /r13 :shrqImm8Reg + /r13 /rax :xorqRegReg + # h ^= h >> 13; + /r9 :mulqReg # h *= 0xc2b2ae35; + /rax /r13 :movqRegReg + 16 /r13 :shrqImm8Reg + /rax /r13 :xorqRegReg + # h ^= h >> 16; + + /r13 /r12 :addqRegReg # h1 += h2; + /r12 /r13 :addqRegReg # h2 += h1; + + # ((uint64_t*)out)[0] = h1; + /r12 /rax :movqRegReg + # ((uint64_t*)out)[1] = h2; + + /r13 :popqReg + /r12 :popqReg + /r11 :popqReg + /r10 :popqReg + /r9 :popqReg + /r8 :popqReg + /rbx :popqReg :retn - ] /internalStringEquals defv + ]] /internalHashString defv > { defv }' allocateOffsetStruct { ==str @@ -540,20 +702,24 @@ "unknown object type during mark phase" outputError :ud2 + 0 /rax :movqImmReg # dead code for disambiguation in debugging @markInteger # "integer marked\n" outputError :retn + 1 /rax :movqImmReg # dead code for disambiguation in debugging @markString # internalDumpErrorString /rax :movqImmReg # /rax :callqReg # " string marked\n" outputError :retn + 2 /rax :movqImmReg # dead code for disambiguation in debugging @markFloat # "float marked\n" outputError :retn + 4 /rax :movqImmReg # dead code for disambiguation in debugging @markExtensionArea # /rdi :pushqReg # "extension area marked\n" outputError @@ -573,6 +739,7 @@ /rcx :popqReg :retn + 5 /rax :movqImmReg # dead code for disambiguation in debugging @markFunction # /rdi :pushqReg # "function marked\n" outputError @@ -592,6 +759,7 @@ /rdi /rdi :movqMemReg /markObject :jmpLbl32 + 6 /rax :movqImmReg # dead code for disambiguation in debugging @markFunctionCode # /rdi :pushqReg # "function code marked\n" outputError @@ -636,6 +804,7 @@ 16 /rdi :subqImm8Reg /markObject :jmpLbl32 + 7 /rax :movqImmReg # dead code for disambiguation in debugging @markArray # /rdi :pushqReg # "array marked\n" outputError @@ -657,6 +826,7 @@ /rcx :popqReg :retn + 8 /rax :movqImmReg # dead code for disambiguation in debugging @markFunctionType # /rdi :pushqReg # "function type marked\n" outputError @@ -676,6 +846,7 @@ /rcx :popqReg :retn + 9 /rax :movqImmReg # dead code for disambiguation in debugging @markScope # /rdi :pushqReg # "scope marked\n" outputError @@ -695,6 +866,7 @@ /rcx :popqReg :retn + 10 /rax :movqImmReg # dead code for disambiguation in debugging @markNameTable # /rdi :pushqReg # "name table marked\n" outputError @@ -702,7 +874,7 @@ /rcx :pushqReg /rsi :pushqReg - 8 /rdi /ecx :movlMemDisp8Reg + /rdi /ecx :movlMemReg /rdi /rsi :movqRegReg 16 /rcx :subqImm8Reg /markNameTableEmpty :jzLbl8 @@ -716,6 +888,7 @@ /rcx :popqReg :retn + 11 /rax :movqImmReg # dead code for disambiguation in debugging @markStack # /rdi :pushqReg # "stack marked\n" outputError @@ -742,6 +915,7 @@ /rsi :popqReg :retn + 12 /rax :movqImmReg # dead code for disambiguation in debugging @markCoroutine # /rdi :pushqReg # "coroutine marked\n" outputError @@ -823,6 +997,62 @@ > { defv }' allocateOffsetStruct < + # rdi -> first string + # rsi -> second string + # rax <- 1 if both strings are equal, 0 otherwise + [[ + # compare lengths + 16 /rdi /rax :movqMemDisp8Reg + 16 /rsi /rax :cmpqMemDisp8Reg + /different :jnzLbl8 + + # compute hashes + 0 8 /rdi :cmpqImm8MemDisp8 + /firstStringHashed :jnzLbl8 + /rdi :pushqReg + /rsi :pushqReg + internalHashString /rax :movqImmReg + /rax :callqReg + /rsi :popqReg + /rdi :popqReg + + @firstStringHashed + + 0 8 /rsi :cmpqImm8MemDisp8 + /secondStringHashed :jnzLbl8 + /rdi :pushqReg + /rsi :pushqReg + /rsi /rdi :movqRegReg + internalHashString /rax :movqImmReg + /rax :callqReg + /rsi :popqReg + /rdi :popqReg + + @secondStringHashed + + # compare hashes + 8 /rdi /rax :movqMemDisp8Reg + 8 /rsi /rax :cmpqMemDisp8Reg + /different :jnzLbl8 + + # compare contents + 16 /rdi /rcx :movqMemDisp8Reg + 24 /rdi /rdi :leaqMemDisp8Reg + 24 /rsi /rsi :leaqMemDisp8Reg + + :repz :cmpsb + /different :jneLbl8 + + 1 /rax :movqImmReg + :retn + + @different + /rax /rax :xorqRegReg + :retn + ]] /internalCompareString defv + > { defv }' allocateOffsetStruct + + < # allocate a chunk of memory and zero it # rdi -> size of chunk in bytes # rax <- address of allocated chunk @@ -883,31 +1113,69 @@ @isScope # ENDCHECK + 8 /rsi /rcx :movqMemDisp8Reg + /rcx /rcx :testqRegReg + /hashComputed :jnzLbl8 + + /rsi /rdi :movqRegReg + internalHashString /rax :movqImmReg + /rax :callqReg + /rax /rcx :movqRegReg + + 0 /rsp /rsi :movqMemDisp8Reg + /rax 8 /rsi :movqRegMemDisp8 # cache hash value in string + 8 /rsp /rdi :movqMemDisp8Reg + + @hashComputed + 8 /rdi /rbp :movqMemDisp8Reg # load name table /rbp /rbp :testqRegReg - /end :jzLbl8 # no name table present - empty scope - - 16 /rbp /rdx :leaqMemDisp8Reg # rdx will iterate over entries - 8 /rbp /rbp :addqMemDisp8Reg # compute name table effective end - /rsi /rax :movqRegReg - - /rdx /rbp :cmpqRegReg - /end :jbeLbl8 - - @loop - /rdx /rdi :movqMemReg - 16 /rax /rcx :movqMemDisp8Reg # load exact length - 16 /rdi /rdi :leaqMemDisp8Reg - 16 /rax /rsi :leaqMemDisp8Reg - :cmpsq # same exact length - /fail :jnzLbl8 - :repz :cmpsb - /found :jzLbl8 - - @fail - 16 /rdx :addqImm8Reg - /rdx /rbp :cmpqRegReg - /loop :jaLbl8 + /end :jzLbl32 # no name table present - empty scope + + < + { + # rcx == hash value of key to resolve + # rbp == nametable to resolve in + # 0 /rsp == key to find + + /ecx /eax :movlRegReg + 0 /rbp /esi :movlMemDisp8Reg # load table length + 16 /rsi :subqImm8Reg # substract header length + 4 /rsi :shrqImm8Reg # divide by slot length + /rdx /rdx :xorqRegReg + /rsi :divqReg + + # rdx == remainder, i.e. slot index + 4 /rdx :shlqImm8Reg # multiply by slot length + 16 1 /rbp /rdx /rax :leaqMemIndexScaleDisp8Reg # load key from bucket + 0 /rax :cmpqImm8Mem + /end :jzLbl32 # empty slot found, key is not present + + 0 /rsp /rdi :movqMemDisp8Reg + /rax /rsi :movqMemReg + /rax :pushqReg + /rcx :pushqReg + /rbp :pushqReg + internalCompareString /rax :movqImmReg + /rax :callqReg + /rbp :popqReg + /rcx :popqReg + /rax /rax :testqRegReg + /found :jnzLbl32 + + /rax :popqReg + } /trySlot deff + + :HASHPOSITIONS 1 sub { + trySlot + + /rcx /rax :movqRegReg + 32 /rax :shrqImm8Reg + /rax /rcx :addqRegReg # derive a new hash value + } rep + + trySlot + > -- @end # not found at all, retry with parent @@ -922,7 +1190,7 @@ /rax :pushqReg /rdi :pushqReg /rsi :pushqReg - /retryWithParent :jnzLbl8 + /retryWithParent :jnzLbl32 @failed /rsi :popqReg @@ -933,16 +1201,16 @@ :retn @found + /rdx :popqReg # rdx == hash bucket where we found the key /rsi :popqReg # rsi == name to resolve /rdi :popqReg # rdi == scope we are resolving in - # top of stack -> number of parent pointers followed - 8 /rdx /rax :movqMemDisp8Reg # load default activation - 8 /rdi /rdx :subqMemDisp8Reg # substract name table start - 16 /rdx :subqImm8Reg # substract name table header size - /rdx :shrq1Reg # divide by 2 to get offset within scope + # 0 /rsp -> number of parent pointers followed + + 8 /rdx /eax :movlMemDisp8Reg # load default activation + 12 /rdx /ecx :movlMemDisp8Reg # load index in scope + 3 /rcx :shlqImm8Reg - /rdx /rcx :movqRegReg # rcx == entry index * 8 in scope # rax == entry default activation /rcx /rsi :movqRegReg # save into target register for return value @@ -1087,6 +1355,110 @@ :retn ] /internalAllocateScope defv + # allocate nametable + # rdi -> expected number of entries + # rax <- address of nametable on the heap + [ + 4 /rdi :shlqImm8Reg + 32 /rdi :addqImm8Reg + internalAllocateAndZero /rax :movqImmReg + /rax :callqReg + + # set type + %A0 7 /rax :orbImmMemDisp8 + :retn + ] /internalAllocateNametable defv + + # insert string into nametable + # rdi -> string to insert + # rsi -> nametable to insert within + # rax <- address of 16 byte hash slot, or zero if no free bucket was found + # rdx <- zero if new entry, one if same key was already present + [[ + /rdi :pushqReg + /rsi :pushqReg + + 8 /rdi /rcx :movqMemDisp8Reg # load cached hash value + /rcx /rcx :testqRegReg + /hashComputed :jnzLbl8 + + internalHashString /rax :movqImmReg + /rax :callqReg + /rax /rcx :movqRegReg + + 8 /rsp /rdi :movqMemDisp8Reg + /rax 8 /rdi :movqRegMemDisp8 # cache hash value in string + 0 /rsp /rsi :movqMemDisp8Reg + + @hashComputed + + < + { + # rcx == hash value + # rsi == nametable to insert into + # rdi == string to insert + + /ecx /eax :movlRegReg + /rsi /esi :movlMemReg # load table length + 16 /rsi :subqImm8Reg # substract header length + 4 /rsi :shrqImm8Reg # divide by slot length + /rdx /rdx :xorqRegReg + /rsi :divqReg + + # rdx == remainder of division + + 0 /rsp /rsi :movqMemDisp8Reg + 4 /rdx :shlqImm8Reg # multiply by slot length + 16 1 /rdx /rsi /rax :leaqMemIndexScaleDisp8Reg # rax == slot address + 0 /rax :cmpqImm8Mem + /emptySlotFound :jzLbl32 + + /rax /rsi :movqMemReg + /rax :pushqReg + /rcx :pushqReg + internalCompareString /rax :movqImmReg + /rax :callqReg + /rcx :popqReg + /rax /rax :testqRegReg + /equalSlotFound :jnzLbl32 + + /rax :popqReg + 8 /rsp /rdi :movqMemDisp8Reg + 0 /rsp /rsi :movqMemDisp8Reg + } /trySlot deff + + :HASHPOSITIONS 1 sub { + trySlot + + /rcx /rax :movqRegReg + 32 /rax :shrqImm8Reg + /rax /rcx :addqRegReg # derive a new hash value + } rep + + trySlot + > -- + + /rax /rax :xorqRegReg # no slot found + /rdx /rdx :xorqRegReg + 16 /rsp :addqImm8Reg + :retn + + @emptySlotFound + # rax == slot address + /rsi :popqReg + + /rax :popqMem # save string into slot + /rdx /rdx :xorqRegReg + :retn + + @equalSlotFound + /rax :popqReg + 16 /rsp :addqImm8Reg + + 1 /rdx :movqImmReg + :retn + ]] /internalInsertToNametable defv + # allocate function # rdi -> code pointer # rsi -> scope pointer @@ -1270,6 +1642,71 @@ :retn ]] /internalAllocateCodeFromEncodingBuffer defv + + # rdi -> nametable to enlarge + # rsi -> number of entries to have in the new hashtable + # rax <- new, larger nametable + [[ + /rdi :pushqReg + + @retry + + /rsi /rdi :movqRegReg + internalAllocateNametable /rax :movqImmReg + /rax :callqReg + /rax :pushqReg + + 8 /rsp /rsi :movqMemDisp8Reg + + 8 /rsi /rdx :movqMemDisp8Reg + /rdx 8 /rax :movqRegMemDisp8 # transfer entry count + + /rsi /ecx :movlMemReg + 16 /rcx :subqImm8Reg # substract header size + 4 /rcx :shrqImm8Reg # divide by 16 to get number of buckets + + # rcx == number of entries to rehash + + @rehashEntry + 16 /rsi :addqImm8Reg + + # rsi == hash bucket to rehash + + 0 /rsi :cmpqImm8Mem + /entryIsEmpty :jzLbl8 + + /rcx :pushqReg + /rsi :pushqReg + + /rsi /rdi :movqMemReg + 16 /rsp /rsi :movqMemDisp8Reg + internalInsertToNametable /rax :movqImmReg + /rax :callqReg + /rax /rax :testqRegReg + /rehashFailed :jzLbl8 + + /rsi :popqReg + /rcx :popqReg + + 8 /rsi /rdx :movqMemDisp8Reg + /rdx 8 /rax :movqRegMemDisp8 # transfer entry data + + @entryIsEmpty + + /rehashEntry :loopLbl8 + + /rax :popqReg + 8 /rsp :addqImm8Reg + :retn + + @rehashFailed + 16 /rsp :addqImm8Reg + /rax :popqReg + /rax /esi :movlMemReg + 3 /rsi :shrqImm8Reg + + /retry :jmpLbl8 + ]] /internalGrowNametable defv > { defv }' allocateOffsetStruct [ diff --git a/compiler/elymasAsmOps.ey b/compiler/elymasAsmOps.ey index 3adba21..3d30518 100644 --- a/compiler/elymasAsmOps.ey +++ b/compiler/elymasAsmOps.ey @@ -1294,6 +1294,16 @@ memoryAddressingVariants keys { ==variant memoryAddressingVariants variant . =*p /zero reg modrm11 } /rolqClReg deff +{ ==reg ==i + reg bit64assert + i 64 lt not { "Shift immediate too large" die } rep + + 1 /none /none reg rex + %C1 + /zero reg modrm11 + i imm8 +} /rolqImm8Reg deff + { %AE } /scasb deff diff --git a/compiler/elymasGlobal.ey b/compiler/elymasGlobal.ey index 805a3db..90fbfda 100644 --- a/compiler/elymasGlobal.ey +++ b/compiler/elymasGlobal.ey @@ -116,127 +116,93 @@ /r15 :popqMem 8 /r15 :subqImm8Reg - /r15 :popqMem # /r15 now points to activation + /r15 :popqMem - /rdi :popqReg + 8 /r15 :subqImm8Reg + /r15 :popqMem + # 8 /r15 now points to activation + # /r15 now points to key to define - /rax :popqReg # CHECK this is just sanity checking - /rax :pushqReg - /rax /rax :testqRegReg - /realObject :jnzLbl8 - "trying to store zero object address" ::outputError - :ud2 - @realObject # CHECK end of checking + ASSERTIONS { + /rax :popqReg + /rax :pushqReg + /rax /rax :testqRegReg + /realObject :jnzLbl8 + "trying to store zero object address" ::outputError + :ud2 + @realObject + + /r15 /rax :movqMemReg + 7 /rax /al :movbMemDisp8Reg + %f0 /al :andbImmReg + %10 /al :cmpbImmReg + /keyIsString :jzLbl8 + "tried to def to non-string key" ::outputError + :ud2 + @keyIsString + } rep # search for name in nametable /r14 /rbx :movqRegReg # rbx == start of scope in heap - 8 /rbx /rdx :movqMemDisp8Reg # rdx == start of nametable in heap - /rdx /rdx :testqRegReg - /createNameTable :jzLbl32 8 /rbx /rsi :movqMemDisp8Reg # rsi == start of nametable in heap - 8 /rsi /rsi :addqMemDisp8Reg # rsi == end of nametable in heap (according to fill) + /rsi /rsi :testqRegReg + /nameTableExists :jnzLbl32 - @nameSearch - 16 /rdx :addqImm8Reg - - # rsi: end of nametable - # rdx: current element of nametable + INITIALNAMETABLESIZE /rdi :movqImmReg + ::internalAllocateNametable /rax :movqImmReg + /rax :callqReg - /rdx /rsi :cmpqRegReg - /nameUndefined :jbeLbl8 + # rax == nametable + /rax 8 /rbx :movqRegMemDisp8 # save new nametable + /rax /rsi :movqRegReg - /rdx :pushqReg # TODO code does not seem optimal here - /rsi :pushqReg - /rdi :pushqReg - /rcx :pushqReg - /rdx /rsi :movqMemReg - /rax /rax :xorqRegReg - :cmpsq # ignore memory length header - :cmpsq # ignore hash - /rsi /rdx :movqMemReg # load exact length - :cmpsq # same exact length - /fail :jnzLbl8 - /rdx /rcx :movqRegReg - :repz :cmpsb - /fail :jnzLbl8 - /rax :incqReg - @fail - /rcx :popqReg - /rdi :popqReg - /rsi :popqReg - /rdx :popqReg - /rax /rax :testqRegReg - /nameOffsetKnown :jnzLbl32 - /nameSearch :jmpLbl8 + @nameTableExists + /r15 /rdi :movqMemReg - # if not exists, insert - @nameUndefined - 8 /rbx /rdx :movqMemDisp8Reg # rdx == start of nametable in heap - /rdx /eax :movlMemReg # add memory length to obtain memory end - /rax /rdx :addqRegReg + # rdi == string to insert + # rsi == nametable on heap - /rsi /rdx :cmpqRegReg - /enlargeNameTable :jbeLbl8 + ::internalInsertToNametable /rax :movqImmReg + /rax :callqReg - # insert into name table - @insertIntoNameTable - /rdi /rsi :movqRegMem - /r15 /rax :movqMemReg - /rax ::unboxInteger - /rax 8 /rsi :movqRegMemDisp8 # set default activation mode - 8 /rbx /rdx :movqMemDisp8Reg # rdx == start of nametable in heap - 16 8 /rdx :addqImm8MemDisp8 # increment fill - /rsi /rdx :movqRegReg - /nameOffsetKnown :jmpLbl32 + # rax == start of 16 byte slot (or zero if no slot was found) + /rax /rax :testqRegReg + /slotFound :jnzLbl8 - @enlargeNameTable - # if name table is already full, double size - 8 /rbx /rdx :movqMemDisp8Reg # rdx == start of nametable in heap - /rdi :pushqReg - /rdx :pushqReg - /rdx /edi :movlMemReg # load current length - /rdi /rdi :addqRegReg + 8 /rbx /rdi :movqMemDisp8Reg # rdi == start of nametable in heap + /rdi /esi :movlMemReg + 3 /rsi :shrqImm8Reg - ::internalAllocateAndZero /rax :movqImmReg + ::internalGrowNametable /rax :movqImmReg /rax :callqReg - %A0 7 /rax :orbImmMemDisp8 # set type - /rdx :popqReg - 8 /rdx /rcx :movqMemDisp8Reg - /rcx 8 /rax :movqRegMemDisp8 # copy fill + # rax == new, larger nametable + /rax 8 /rbx :movqRegMemDisp8 # store new nametable in scope + /rax /rsi :movqRegReg + /nameTableExists :jmpLbl8 - 16 /rdx /rsi :leaqMemDisp8Reg - 16 /rax /rdi :leaqMemDisp8Reg - 16 /rcx :subqImm8Reg - 3 /rcx :shrqImm8Reg - :reprcx :movsq # copy content - /insertIntoNewNameTable :jmpLbl8 + @slotFound + # rax == address of 16 byte slot in nametable + /rdx /rdx :testqRegReg + /nameExists :jnzLbl8 - @createNameTable - /rdi :pushqReg + 8 /r15 /esi :movlMemDisp8Reg + /esi 8 /rax :movlRegMemDisp8 # store execution mode - INITIALNAMETABLESIZE 16 mul 16 add /rdi :movqImmReg - ::internalAllocateAndZero /rax :movqImmReg - /rax :callqReg - %A0 7 /rax :orbImmMemDisp8 # set type - 16 8 /rax :orbImmMemDisp8 # set initial fill - 16 /rax /rdi :leaqMemDisp8Reg # load first entry address + 8 /rbx /rdi :movqMemDisp8Reg # rdi == start of nametable in heap + 8 /rdi /esi :movlMemDisp8Reg + /esi 12 /rax :movlRegMemDisp8 # store scope index # FIXME measure performance and consider orq-ing the two fields by hand + 1 8 /rdi :addqImm8MemDisp8 # increment number of assigned slots + + /rsi /rdx :movqRegReg + /nameInserted :jmpLbl8 - @insertIntoNewNameTable + @nameExists + 12 /rax /edx :movlMemDisp8Reg # load slot index from hash - # rax == enlarged or new name table on heap - # rdi == target address for name table entry - - /rax 8 /rbx :movqRegMemDisp8 # switch scope to new name table + @nameInserted + # rdx == slot index - # insert into name table - /rsi :popqReg - /rsi /rdi :xchgqRegReg - /insertIntoNameTable :jmpLbl32 - - @nameOffsetKnown - 8 /rbx /rdx :subqMemDisp8Reg # substract name table address - 16 /rdx :subqImm8Reg # substract name table header size - /rdx :shrq1Reg # divide by 2 to get offset within scope + 3 /rdx :shlqImm8Reg # multiply by 8 to get offset within scope # rdx == offset in scope # top of stack: the object to store @@ -308,7 +274,7 @@ /rax :popqReg /rax /rbx /rdx :movqRegMemIndex # save entry pointer - 8 /r15 :addqImm8Reg + 16 /r15 :addqImm8Reg /r15 :pushqMem 8 /r15 :addqImm8Reg :retn @@ -435,13 +401,18 @@ # rdx == array on heap /rbx :popqReg 63 /rbx :btrqImm8Reg - /arrayIntArgumentUnboxed :jcLbl8 + /arrayIntArgumentUnboxed :jcLbl32 7 /rbx /cl :movbMemDisp8Reg %F0 /cl :andbImmReg %00 /cl :cmpbImmReg /arrayIntArgumentBoxed :jeLbl8 + %01 /cl :cmpbImmReg + /arrayWrongScalarArgumentBoxed :jeLbl8 + %02 /cl :cmpbImmReg + /arrayWrongScalarArgumentBoxed :jeLbl8 + # escape this to compiled high-level code /rbx :pushqReg /rdx :pushqReg @@ -465,6 +436,10 @@ 8 /r15 :addqImm8Reg :retn + @arrayWrongScalarArgumentBoxed + "trying to execute array on string or float" ::outputError + :ud2 + @arrayIntArgumentBoxed 8 /rbx /rax :movqMemDisp8Reg # rax == requested index /arrayIntArgumentLoaded :jmpLbl8 @@ -1853,6 +1828,26 @@ 8 /r15 :popqMemDisp8 # output arguments /r15 :popqMem # input arguments + ASSERTIONS { + /r15 /rax :movqMemReg + 7 /rax /al :movbMemDisp8Reg + %f0 /al :andbImmReg + %70 /al :cmpbImmReg + /inputIsArray :jzLbl8 + "tried to '' for non-array input arguments" ::outputError + :ud2 + @inputIsArray + + 8 /r15 /rax :movqMemDisp8Reg + 7 /rax /al :movbMemDisp8Reg + %f0 /al :andbImmReg + %70 /al :cmpbImmReg + /outputIsArray :jzLbl8 + "tried to '' for non-array output arguments" ::outputError + :ud2 + @outputIsArray + } rep + /r15 /rdx :movqMemReg /rdx /edi :movlMemReg 8 /r15 /rdx :movqMemDisp8Reg @@ -2458,27 +2453,35 @@ /emptyScope :jzLbl8 16 /rax /rsi :leaqMemDisp8Reg - /rsi :pushqReg + /rsi :pushqReg # save start of bucket array + /rax /ecx :movlMemReg + 16 /rcx :subqImm8Reg # substract header size + 4 /rcx :shrqImm8Reg + /rcx :pushqReg # save bucket count 8 /rax /rdi :movqMemDisp8Reg - 16 /rdi :subqImm8Reg - /rdi :pushqReg - /rdi :shrq1Reg + 3 /rdi :shlqImm8Reg ::internalAllocateArray /rax :movqImmReg /rax :callqReg 8 /rax /rdi :leaqMemDisp8Reg /rcx :popqReg /rsi :popqReg - 4 /rcx :shrqImm8Reg + + /rax :pushqReg # save array on stack as result + + /rcx /rcx :testqRegReg /empty :jzLbl8 @loop - :movsq - 8 /rsi :addqImm8Reg + /rsi /rax :movqMemReg + /rax /rax :testqRegReg + /emptyBucket :jzLbl8 + 12 /rsi /edx :movlMemDisp8Reg # load entry index + /rax 8 /rdx /rdi :movqRegMemIndexScale # put into array + @emptyBucket + 16 /rsi :addqImm8Reg /loop :loopLbl8 @empty - /rax :pushqReg - /r15 :pushqMem 8 /r15 :addqImm8Reg :retn @@ -271,16 +271,17 @@ Overhead: 1/32. * data [ <reference> ]* -=== Name Table === -( TODO: create a hash-table based implementation here ) +=== Name Table (hashed implementation) === * Length in bytes (including header) bit 63-60: 1 0 1 0 bit 59: reserved for GC -* End of fill in bytes (i.e. if this field == length, table is full) -* data - [ <string reference>, <execution mode> ]* - ( TODO: Oh, the performance... ) - The 0th string maps to 0 and so on. +* Number of keys (also next scope entry index to assign) +* Hash buckets (16 bytes each) + [ + <string reference> (8 bytes) + <execution mode> (4 bytes) + <scope entry index> (4 bytes) + ]* === Stack === * Length in bytes (including header) @@ -397,6 +398,53 @@ eq [ sys .typed .SCALAR _ ] [ Int ] '' eq [ sys .typed .var _ ] [ Int ] '' { 1 eq } { "foo" eq } and # [ $X $Y ] [ Int ] # 1 eq -01 "foo" eq and +== Variant: Scalar Argument-Selector == + +=== Obvious Case 1 === +1 [ 1 2 3 ] add => [ 2 3 4 ] +[ 1 2 3 ] 1 add => [ 2 3 4 ] +Because: +[ 1 1 1 ] [ 1 2 3 ] add => [ 2 3 4 ] + +=== Obvious Case 2 === +If f, g unrelated: +|f |g h => { f ==x g ==y y x h } * + +|add |sub mul => { ==x ==y x y add x y sub mul } * + +WTF??? Hence: +Say f, g have a type which specifies which stack position they'd like to consume, like so: +|f type => [ 2 0 ] . [ 0 ] +|g type => [ 1 0 ] . [ 0 ] +then +|f |g h => { ==z ==y ==x y x g ==G z x f ==F F G h } * + +=== Obvious Case 3 === +{ -- { -- { 1 } } } =*f (i.e. the constant function from two arguments to 1) +|f |f add => { -- { -- { 2 } } } (i.e. the constant function from two arguments to 2) + +With the above: +|f type => [ 0 ] . [ [ 0 ] . 0 ] + +=== Case 4 === +{ _ } =*dup (clearly with type [ 0 ] . [ 0 0 ]) + +|dup |add ; => { _ add } +X |dup add => { ==y y dup ==D1 ==D2 X D2 add D1 } +|dup X add => { ==y y dup ==D1 ==D2 D2 X add D1 } + +=== Case 5 === + + + +f: A->B->X + | | + v v + a0 b0 + | + v + a1 + = Musings about function composition operator = Maybe ; should act differently when getting a string, or use another single char for category operations |