• ASM Optimized routines 5 1

Author Topic: ASM Optimized routines  (Read 104172 times)

0 Members and 1 Guest are viewing this topic.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: ASM Optimized routines
« Reply #105 on: June 18, 2021, 06:35:59 pm »
Wow, that's really neat. I don't have a use for that at the moment but I bet I can find one in some old, slow code.

How did you go about making the routine generator? I assume there are some simple rules it follows.
It looks through all the numbers 1-65535 to find some good code.
If the number is even, it essentially uses the code for n/2, but with an `add hl,hl` tacked on to the end. Otherwise it is odd and it first tries a shift-and-add algorithm (basically the classic, generic multiplication, but unrolled and with branches removed as we know which path it takes in advance). It registers whatever code it came up with, then it checks if it is faster or smaller to multiply by the factors (for example, it is faster to multiply by 27 by doing *3*9 or *9*3), so it finds all of the factors and checks for anything more efficient.

There are other tricks, too, like checking if it is faster to "negate" (i.e., *65535 is the same as *-1), and if there is a *(2^k-1) with k>3, it uses a subtraction. And it collapse things like 8 `add hl,hl` into `ld h,l \ ld l,0`, and has some pre-populated routines in the table.

It doesn't really know anything about the instruction set, so it can't do any fancy optimizations :(