chibinz
commented
2 years ago Similar to the idea of parse-generator, could we come up with some sort of algorithms that take bit patterns (00101...1 where ... means dont care) as input, and automatically generate a optimal decoder table?
Potential issue that I could think of right now:
- How do we define "optimal"? Usually the shallower the decode tree, the less time spent on decoding. We could pattern match on the entire 32-bit instruction, but the table would overflow the cpu cache and penalize performance severely. On the other hand we could do bit by bit decoding, but that is also very slow. There seems to be space-time trade off that is quite subtle to handle... We could also take into consideration the frequency of instructions executed...
- How much time is actually spent on decoding / dispatch / execution individually? Intuitively, execution is the most expensive. But decoding with const generics actually monophormizes functions, eliminating branches at compile time. Branch misprediction seems to be a major overhead when executing complicated instructions. Yes, I am looking at you ARM Data processing, LDM/STM...
Currently the dispatch is written manually, first bits 27 - 25, then bit 24 -21, and optionally bits 7 - 4 for arm mode, and bits 15 - 11 for thumb mode. While the cpu is really not the bottle neck, other emulator writers seemed to agreed upon using 12 bits for arm opcode dispatching. Const generics are useful eliminating branches at compile time. Right now it's only available in rust nightly, and is scheduled to stablize in version 1.51, March 25. I feel a bit reluctant to switch tool chain.