I still love the 33 instructions in the Microchip PIC instruction set.
How many x86 instructions are there? (2016)
71–80 of 92 posts
Re: How many x86 instructions are there? (2016)
#72Earlier quoted context omitted.
> you could burn the top 2b to mark Which seems reasonable.. but you just burned 3/4 of the single opcode instruction space, which may not be worth it for most general purpose loads.
Would you mind elaborating on the math of how the "top 2b" ends up burning 3/4 of the single opcode instruction space?
Each bit used halves the potential encoding space, e.g. 2^32 -> 2^31 possible instruction encodings.
For thumb, 32-bit instructions can be allocated up to 3/32 of the potential 32-bit space, and 16-bit instructions can use 29/32 of the 16-bit space (3 of the potential 5-bit opcodes denote a 32-bit instruction.) Which is probably a better ratio than 1/2 or 1/4 of each, for instance. Though I'm not sure how much of that encoding space is actually allocated or still reserved.
Related, I believe ARM has allocated about half of the 32-bit encoding space for current A64 instructions.
Re: How many x86 instructions are there? (2016)
#73An interesting (if horrifying) exercise:
$ ndisasm -b 64 /dev/urandom
Re: How many x86 instructions are there? (2016)
#74Earlier quoted context omitted.
Would you mind elaborating on the math of how the "top 2b" ends up burning 3/4 of the single opcode instruction space?
Each bit used halves the potential encoding space, e.g. 2^32 -> 2^31 possible instruction encodings. For thumb, 32-bit instructions can be allocated up to 3/32 of the potential 32-bit space, and 16-bit instructions can use 29/32 of the 16-bit space (3 of the potential 5-bit opcodes denote a 32-bit instruction.) Which is probably a better ratio than 1/2 or 1/4 of each, for instance. Though I'm not sure how much of tha…
Further, if you want single-byte opcodes, then you took that space from 256 opcodes down to 64. It cost you 192 single-byte opcodes to use a 2b marker. This wouldn't be possible with the current x86 encodings [1].
Re: How many x86 instructions are there? (2016)
#75Earlier quoted context omitted.
Which one?
_mm256_movemask_epi8, i.e., the "fast lexer" instruction. That instruction takes ~3c (depending on uarch), and the ARM equivalent (7-8 instructions) takes ~5-6c (depending on uarch). It's just annoying .
PMOVMSKB is a great instruction, and 3c understates how cheap it is - if you have a throughput problem (rather than a latency problem) it's even more efficient relative to the ARM equivalent.
I have a blog post about coping strategies for working around the absence of PMOVMSKB on NEON:
https://branchfree.org/2019/04/01/fitting-my-head-through-th...
We used these techniques in simdjson (which I presume still uses them; the code has changed considerably since I built this): https://github.com/simdjson/simdjson
The best techniques for mitigating the absence of PMOVMSKB require that you use LD4, which results in interleaved inputs. This can sometimes make things easier, sometimes harder for your underlying lexing algorithm - sadly, it's not a 1:1 transformation of the original x86 code.
Re: How many x86 instructions are there? (2016)
#76Past related threads:
How Many X86-64 Instructions Are There Anyway? - https://news.ycombinator.com/item?id=14233296 - April 2017 (133 comments)
How many x86 instructions are there? - https://news.ycombinator.com/item?id=12358050 - Aug 2016 (39 comments)
Does a compiler use all x86 instructions? (2010) - https://news.ycombinator.com/item?id=12352959 - Aug 2016 (189 comments)
How Many X86-64 Instructions Are There Anyway? - https://news.ycombinator.com/item?id=11535178 - April 2016 (1 comment)
Re: How many x86 instructions are there? (2016)
#77Earlier quoted context omitted.
I'd also be curious to discover how many distinct x86 instructions gcc can even emit? I expect the answer is "a lot less than all of them."
Probably a couple hundred at most, and for common programs several dozen.
Tried it out on Debian Bullseye x86_64:
$ objdump -w -j .text --no-show-raw-insn -d /usr/bin/emacs-gtk | egrep '^ *[0-9]+:' | awk '{print $2}' | sort | uniq | wc -l
130
$ objdump -w -j .text --no-show-raw-insn -d /bin/ls | egrep '^ *[0-9]+:' | awk '{print $2}' | sort | uniq | wc -l
97
$ objdump -w -j .text --no-show-raw-insn -d firefox-bin | egrep '^ *[0-9]+:' | awk '{print $2}' | sort | uniq | wc -l
136Re: How many x86 instructions are there? (2016)
#78Earlier quoted context omitted.
Would you mind elaborating on the math of how the "top 2b" ends up burning 3/4 of the single opcode instruction space?
Each bit used halves the potential encoding space, e.g. 2^32 -> 2^31 possible instruction encodings. For thumb, 32-bit instructions can be allocated up to 3/32 of the potential 32-bit space, and 16-bit instructions can use 29/32 of the 16-bit space (3 of the potential 5-bit opcodes denote a 32-bit instruction.) Which is probably a better ratio than 1/2 or 1/4 of each, for instance. Though I'm not sure how much of tha…
Ah OK, I think I understand now. You are specifically referring to the ARM Thumb instruction set as an example of this encoding scheme in both your comments?
Re: How many x86 instructions are there? (2016)
#79Earlier quoted context omitted.
Probably a couple hundred at most, and for common programs several dozen.
Tried it out on Debian Bullseye x86_64: $ objdump -w -j .text --no-show-raw-insn -d /usr/bin/emacs-gtk | egrep '^ *[0-9]+:' | awk '{print $2}' | sort | uniq | wc -l 130 $ objdump -w -j .text --no-show-raw-insn -d /bin/ls | egrep '^ *[0-9]+:' | awk '{print $2}' | sort | uniq | wc -l 97 $ objdump -w -j .text --no-show-raw-insn -d firefox-bin | egrep '^ *[0-9]+:' | awk '{print $2}' | sort | uniq | wc -l 136
[deleted]
Re: How many x86 instructions are there? (2016)
#80And by the way, I used x86 as an example here, but don’t believe for a second the same thing doesn’t apply to, say, the ARM chip in your phone. Modern ARM chips support multiple encodings and also rank over 1000 instructions if you count them at the same level of granularity as XEDs “iforms”.
Indeed, those who think x86 is complex should also take a detailed look at the ARM64 instruction set, particularly its instruction encoding. If you thought making sense of x86 instruction encoding was hard, and that a RISC might seem simpler, AArch64 will puzzle you even more.
To use the MOV example, the closest ARM equivalent might be the 40 variants of LD, which the reference manual (5000+ pages) enumerates as: LDAR, LDARB, LDARH, LDAXP, LDAXR, LDAXRB, LDAXRH, LDNP, LDP, LDPSW, LDR (immediate), LDR (literal), LDR (register), LDRB (immediate), LDRB (register), LDRH (immediate), LDRH (register), LDRSB (immediate), LDRSB (register), LDRSH (immediate), LDRSH (register), LDRSW (immediate), LDRSW (literal), LDRSW (register), LDTR, LDTRB, LDTRH, LDTRSB, LDTRSH, LDTRSW, LDUR, LDURB, LDURH, LDURSB, LDURSH, LDURSW, LDXP, LDXR, LDXRB, LDXRH. Some, like LDP, are then further split into different encodings depending on the addressing mode.
My suspicion is that to achieve acceptable code density with a fixed-length instruction encoding, they just made the individual instructions more complex. For example, the add instruction can also do a shift on one of its operands, which would require a second instruction on x86.