3 ms·

Imagine if x86 had POPCNT since the beginning, implemented in microcode at first, and optimised it over time to be faster and use more available hardware. There

Imagine if x86 had POPCNT since the beginning, implemented in microcode at first, and optimised it over time to be faster and use more available hardware. There would be no need for this sort of "decompiler" in a compiler nor would software need recompilation for each CPU model.

pizlonator 2y ago
Meh? There will always be new CPU instructions that weren’t already part of whatever language you’re using, that corresponded to a pattern of code that people are already writing in that language. And the pattern matching isn’t rocket science. I wouldn’t characterize it as “decompilation”; that makes it seem more magical than it really is. Popcnt may be a particularly amusing example but it’s far from the only one. A modern C compiler has countless patterns it recognizes, sometimes to match them to instructions, other times just to aid the compiler’s understanding of what’s going on. Usually the latter.
lmm 2y ago
If they somehow magically knew the future of the whole industry decades in advance, and were able to design the perfect ISA based on that, sure. But that's not how things go in practice. If they'd put in all the opcodes that they thought would be important in the future back in the '80s and implemented them in microcode, I guarantee that we'd be a whole lot worse off now, with loads of pointless opcodes for 5GL and semantic networks and all the other dead ends of the era, and no space for things that turned out to be important like POPCNT.
- adrian_b 2y ago
  POPCNT was not from the future, it was from the past. The Intel designers only assumed that this belongs to the operations that would not be frequently used in the applications expected for their processors. This was caused in part because they were not personally familiar with such applications. Even if POPCNT actually has a very wide area of applicability, during the seventies of the 20th century the only people who were concerned with the speed of executing POPCNT were some who worked at cryptographic applications and at that time almost all such work was classified. However, with such operations there is always a chicken and egg problem. When they are not implemented in hardware, the programmers and the compiler writers avoid expressing algorithms with them and use various workarounds to implement in a different way the algorithms that would benefit from them. This leads to a low frequency of use of such operations, which is then used to justify that it is not necessary to implement them in hardware. The correct analysis whether such operations would be worthwhile when implemented in hardware requires much more work in writing alternative versions of various algorithms, to be run in simulated hardware, and this is almost never done.
  - sumtechguy 2y ago
    There are also a few different algorithms to handle it https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive https://graphics.stanford.edu/~seander/bithacks.html#CountBi... x86 started as basically a calculator chip. Not a lot of need in that particular space/usecase for it, and more importantly silicon space for it. However, what is interesting is how long it took to add it to the x86 set of instructions. But at least we have it now.
gizmo686 2y ago
C predates x86, and was written with the specific intent of being independent of the particular CPU architecture being compiled for. At any point, the C standard could have introduced a standard POPCNT function that compilers could easily compile in whatever platform relevant way they want; but such has never happened.
akira2501 2y ago
POPCNT really doesn't have a place on a 16bit processor. Particularly one which can split the 16bit register into two 8bit pairs.
- adrian_b 2y ago
  POPCNT might have not been very useful in the initial 8086 ISA of 1978, but it would have been at home in the NPX extension of the Intel ISA from 1980 (Numeric Procesor Extension, i.e. the instruction set of Intel 8087), which had operations with 64-bit integers and 64-bit significands of 80-bit floating-point numbers.
adrian_b 2y ago
Which is not at all unrealistic, because POPCNT had been recognized as useful and it had already been implemented in some of the earliest computers with vacuum tubes (at the suggestion of Alan Turing). Those early computers, like the Ferranti Mark 1, were much simpler than Intel 8086. The name "population count" had been introduced for this instruction by Cray 1, a couple of years before the launch of Intel 8086.
JoshTriplett 2y ago
That doesn't allow for the possibility of hardware and software co-evolving. In particular, that doesn't allow hardware to get better by providing ways to run common software operations faster.
derdi 2y ago
You got this backwards. If x86 had had POPCNT from the beginning but C did not have a standard popcount function, you would still need to express the popcount in source as in this question, so the compiler would still need to recognize the idiom. There would be no need for this sort of pattern matching if C had had a standard popcount function from the beginning, regardless of widespread hardware support.
dzaima 2y ago
"implemented in microcode at first" has massive downsides if the microcode isn't particularly fast. e.g. AMD Zen 1 and Zen 2 support BMI2 and thus pdep & pext, but they're microcoded, so up to hundreds of times slower than on Zen 3 or Intel; so much so that they're a good amount slower than some 90-instruction manual bitwise implementation (potentially doing 4 at a time via SIMD, at least; so even an equivalent microcoded version might be slower as the pdep/pext instructions are scalar), and completely utterly brokenly slow if you want to use it for something like a byte compress. Similarly, using a microcoded POPCNT on just, say, integers in the range 0..15, would be pretty inefficient, while it's by far the best option on a properly implemented one. All to say, yeah, it would mean that you wouldn't strictly need recompilation for each CPU model, but it would still be plenty beneficial. And, honestly, "compile for the absolute minimum x86-64 while still tuning for recent CPUs" is just extremely horrible - yes, old hardware will technically run it, but that's the hardware that needs the extra perf tuning the most but ends up getting the least.
- kragen 2y ago
  probably 'a properly implemented one' would be using combinational logic that can calculate popcnt in a single cycle, or maybe a two-cycle pipelined implementation, which is not the same thing as a microcoded popcnt here's a simple combinational 8-bit popcnt circuit i just simulated, just using ripple carry. unfortunately i think falstad's circuit.js doesn't have a way to simulate propagation delays; i think the point where you start wanting lookahead carry instead of ripple carry is when you're doing a 16-bit popcnt, because a 64-bit ripple-carry popcnt would have three more full adders of propagation delay over this one https://www.falstad.com/circuit/circuitjs.html?ctz=CQAgjCAMB0l3BWcMBMcUHYMGZIA4UA2ATmIxAUgpABZsKBTAWjDACgxjCRCaQvwKPP25pK4NgBkQLDNzDcmaYQqhqAZgEMANgGcG1SFJlg5tYUvzm1ELXoNIj02fMJVLKtzZB39h4y6CFspB3r4OUBzESIGqLGAo4NxGnDGm8kImCaEp0TLYiaoFSZEA7jJ4VHHFqkblTJUi+YkCdc1NTMU0wm0NVAJ9OWz1jQpUvElUvY3dMhOzvfMWEwk9w3N8qzybmW1L201GALIguJvcCNm1ICjQCGwnNHAHl4kTVLf3jwJbrzk3d3WE0wbz4BSm6yYE2wCFBp1hZQ2NwwiShYIR0w+KKRIMRg2weD40MJeMa4IqVBhiV6xXJnUSuMxpzQ7XJTJQT3aHIhqS5nOK3MivMCVKyiVFuTSZkF8QZnKcJjMoo88Op4B8Oj8jgC6VOJJVBL4VQ19n8zl1uJVjPV4TNitEnKt8ptmoiuW40JZW3JYiqUSQIVUuNq60DHvOiJCsxCgraMc5wPlUW4ZwO2EIwmBkHE7HKqZ+Xla61T3sgYJZbVT5LGzJ5AieVUyNBWmV9EnKNZrDcmiNTs1T73W3c4iW7hsRY5JNfHx1oP2IiT+I7UnzYQA https://www.falstad.com/circuit/circuitjs.html?ctz=CQAgjCAMB... if you have a lot of popcnts to do, you can productively bitslice them so they're fast even without hardware support

pizlonator 2y ago

Meh? There will always be new CPU instructions that weren’t already part of whatever language you’re using, that corresponded to a pattern of code that people are already writing in that language. And the pattern matching isn’t rocket science. I wouldn’t characterize it as “decompilation”; that makes it seem more magical than it really is. Popcnt may be a particularly amusing example but it’s far from the only one. A modern C compiler has countless patterns it recognizes, sometimes to match them to instructions, other times just to aid the compiler’s understanding of what’s going on. Usually the latter.

lmm 2y ago

If they somehow magically knew the future of the whole industry decades in advance, and were able to design the perfect ISA based on that, sure. But that's not how things go in practice. If they'd put in all the opcodes that they thought would be important in the future back in the '80s and implemented them in microcode, I guarantee that we'd be a whole lot worse off now, with loads of pointless opcodes for 5GL and semantic networks and all the other dead ends of the era, and no space for things that turned out to be important like POPCNT.

adrian_b 2y ago
POPCNT was not from the future, it was from the past. The Intel designers only assumed that this belongs to the operations that would not be frequently used in the applications expected for their processors. This was caused in part because they were not personally familiar with such applications. Even if POPCNT actually has a very wide area of applicability, during the seventies of the 20th century the only people who were concerned with the speed of executing POPCNT were some who worked at cryptographic applications and at that time almost all such work was classified. However, with such operations there is always a chicken and egg problem. When they are not implemented in hardware, the programmers and the compiler writers avoid expressing algorithms with them and use various workarounds to implement in a different way the algorithms that would benefit from them. This leads to a low frequency of use of such operations, which is then used to justify that it is not necessary to implement them in hardware. The correct analysis whether such operations would be worthwhile when implemented in hardware requires much more work in writing alternative versions of various algorithms, to be run in simulated hardware, and this is almost never done.
- sumtechguy 2y ago
  There are also a few different algorithms to handle it https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive https://graphics.stanford.edu/~seander/bithacks.html#CountBi... x86 started as basically a calculator chip. Not a lot of need in that particular space/usecase for it, and more importantly silicon space for it. However, what is interesting is how long it took to add it to the x86 set of instructions. But at least we have it now.

gizmo686 2y ago

C predates x86, and was written with the specific intent of being independent of the particular CPU architecture being compiled for. At any point, the C standard could have introduced a standard POPCNT function that compilers could easily compile in whatever platform relevant way they want; but such has never happened.

akira2501 2y ago

POPCNT really doesn't have a place on a 16bit processor. Particularly one which can split the 16bit register into two 8bit pairs.

adrian_b 2y ago
POPCNT might have not been very useful in the initial 8086 ISA of 1978, but it would have been at home in the NPX extension of the Intel ISA from 1980 (Numeric Procesor Extension, i.e. the instruction set of Intel 8087), which had operations with 64-bit integers and 64-bit significands of 80-bit floating-point numbers.

adrian_b 2y ago

Which is not at all unrealistic, because POPCNT had been recognized as useful and it had already been implemented in some of the earliest computers with vacuum tubes (at the suggestion of Alan Turing). Those early computers, like the Ferranti Mark 1, were much simpler than Intel 8086. The name "population count" had been introduced for this instruction by Cray 1, a couple of years before the launch of Intel 8086.

JoshTriplett 2y ago

That doesn't allow for the possibility of hardware and software co-evolving. In particular, that doesn't allow hardware to get better by providing ways to run common software operations faster.

derdi 2y ago

You got this backwards. If x86 had had POPCNT from the beginning but C did not have a standard popcount function, you would still need to express the popcount in source as in this question, so the compiler would still need to recognize the idiom. There would be no need for this sort of pattern matching if C had had a standard popcount function from the beginning, regardless of widespread hardware support.

dzaima 2y ago

"implemented in microcode at first" has massive downsides if the microcode isn't particularly fast. e.g. AMD Zen 1 and Zen 2 support BMI2 and thus pdep & pext, but they're microcoded, so up to hundreds of times slower than on Zen 3 or Intel; so much so that they're a good amount slower than some 90-instruction manual bitwise implementation (potentially doing 4 at a time via SIMD, at least; so even an equivalent microcoded version might be slower as the pdep/pext instructions are scalar), and completely utterly brokenly slow if you want to use it for something like a byte compress. Similarly, using a microcoded POPCNT on just, say, integers in the range 0..15, would be pretty inefficient, while it's by far the best option on a properly implemented one. All to say, yeah, it would mean that you wouldn't strictly need recompilation for each CPU model, but it would still be plenty beneficial. And, honestly, "compile for the absolute minimum x86-64 while still tuning for recent CPUs" is just extremely horrible - yes, old hardware will technically run it, but that's the hardware that needs the extra perf tuning the most but ends up getting the least.

kragen 2y ago
probably 'a properly implemented one' would be using combinational logic that can calculate popcnt in a single cycle, or maybe a two-cycle pipelined implementation, which is not the same thing as a microcoded popcnt here's a simple combinational 8-bit popcnt circuit i just simulated, just using ripple carry. unfortunately i think falstad's circuit.js doesn't have a way to simulate propagation delays; i think the point where you start wanting lookahead carry instead of ripple carry is when you're doing a 16-bit popcnt, because a 64-bit ripple-carry popcnt would have three more full adders of propagation delay over this one https://www.falstad.com/circuit/circuitjs.html?ctz=CQAgjCAMB0l3BWcMBMcUHYMGZIA4UA2ATmIxAUgpABZsKBTAWjDACgxjCRCaQvwKPP25pK4NgBkQLDNzDcmaYQqhqAZgEMANgGcG1SFJlg5tYUvzm1ELXoNIj02fMJVLKtzZB39h4y6CFspB3r4OUBzESIGqLGAo4NxGnDGm8kImCaEp0TLYiaoFSZEA7jJ4VHHFqkblTJUi+YkCdc1NTMU0wm0NVAJ9OWz1jQpUvElUvY3dMhOzvfMWEwk9w3N8qzybmW1L201GALIguJvcCNm1ICjQCGwnNHAHl4kTVLf3jwJbrzk3d3WE0wbz4BSm6yYE2wCFBp1hZQ2NwwiShYIR0w+KKRIMRg2weD40MJeMa4IqVBhiV6xXJnUSuMxpzQ7XJTJQT3aHIhqS5nOK3MivMCVKyiVFuTSZkF8QZnKcJjMoo88Op4B8Oj8jgC6VOJJVBL4VQ19n8zl1uJVjPV4TNitEnKt8ptmoiuW40JZW3JYiqUSQIVUuNq60DHvOiJCsxCgraMc5wPlUW4ZwO2EIwmBkHE7HKqZ+Xla61T3sgYJZbVT5LGzJ5AieVUyNBWmV9EnKNZrDcmiNTs1T73W3c4iW7hsRY5JNfHx1oP2IiT+I7UnzYQA https://www.falstad.com/circuit/circuitjs.html?ctz=CQAgjCAMB... if you have a lot of popcnts to do, you can productively bitslice them so they're fast even without hardware support