7 ms·

Reverse-engineering the division microcode in the Intel 8086 processor

127 points by picture 4y ago

kens 4y ago
Author here. Hopefully you're not all tired of the 8086 by now :-)
- LanternLight83 4y ago
  Can't speak for everyone, but I'm lovin' it, thanks!
- deleted 4y ago
  [deleted]
- jacquesm 4y ago
  Never! I really should get that other chip to you...
- kergonath 4y ago
  Absolutely not! I can’t say I understand everything but I love reading your work.
- rwmj 4y ago
  Are there any physical indications of the order in which instructions were added? I mean to say: Is there any indication that (for example) they added DIV last, perhaps because it's complicated and they didn't know if they could fit that in.
  - kens 4y ago
    Andrew Jenner pointed out that the microcode for the string (block move) operations doesn't exactly match the flowchart in the documentation, and the micro-instructions are kind of scattered around. So it's likely that the string operations were modified late in the process. As far as the other instructions, I haven't seen any particular indication of the order.
- userbinator 4y ago
  Do you think the 8086/8088 were well-optimised/efficient in general? In other words, had they spent some more effort, could they have reduced the transistor count and reduced the number of cycles the instructions take without changing the functionality?
  - kens 4y ago
    The 8086/8088 look pretty well-optimized in many ways: the design of the instruction set, the architecture, the microcode, and the silicon layout. Studying it closely, I've seen multiple things that are more clever than I expected, and haven't seen anything that makes me shake my head in dismay.
- bonzini 4y ago
  Just a note that, just like AAD is a multiplication (and add) in disguise, AAM is an 8-bit unsigned division in disguise and also uses the CORD subroutine.
CalmStorm 4y ago
For modern CPU, is microcode still used for division or there are better and faster alternatives?
- rep_lodsb 4y ago
  The 80186 already implemented the loop for multiplication and (unsigned) division in dedicated logic that could do 1 bit per cycle. The microcode only had to set up the registers, test for overflow, and undo the final subtraction if it underflowed (since it now used a non-restoring algorithm). Starting with the 486 there is likely no longer any microcode involved, and newer chips can handle multiple bits per step. See end of article, the first algorithm to do this comes from 1957!
- bri3d 4y ago
  It's way more complex than this on modern CPUs, so it's harder to explain. > is microcode still used for division? Yes, almost everything on a modern CPU uses "microcode" of some kind, although the term gets kind of hazy, since everything is out-of-order and a lot of instructions are issued in parallel. In a typical modern CPU, the "frontend" will decompose instructions into uOps, which then get pushed into a "reservation station" / "scheduler." The scheduler queues and reorders various uOps in various surprising and complicated ways to try to account for interdependencies and memory latency. Eventually, a uOp is issued into to an "execution port," which is connected to a fixed-function piece of logic that actually performs part or all of an operation (for example, an Arithmetic Unit / ALU). But, while microcode will be _involved_ still, most modern CPUs will have fixed-function hardware for the meaty parts of the division instruction - they generally speaking won't implement division _purely_ using microcode like the algorithm documented in the article. > are there better and faster alternatives? They're not "alternatives" per se, but there are a _lot_ of ways to implement division algorithmically, and a _lot_ of ways to trade size for speed. Improving integer division performance has been a fairly big focus in newer CPU microarchitectures, with major improvements arriving in the latest Intel, AMD, and Apple Silicon architectures. https://uops.info/table.html https://uops.info/table.html will show how many uOps a given x86 instruction decomposes to, what ports it uses, and rough latency estimates for the instruction's execution. Here's some reading I found, with a lot of references: * A discussion of various modern division implementations: https://stackoverflow.com/questions/71420116/why-is-there-only-little-difference-in-integer-division-throughput-with-larger-v https://stackoverflow.com/questions/71420116/why-is-there-on... * Performance comparison of integer division in modern architecutures with some implementation speculation: https://news.ycombinator.com/item?id=27133804 https://news.ycombinator.com/item?id=27133804 * An in-depth look at the division unit in mid-old Intel CPUs (Penryn), look for "Radix-16" : https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=16afaef17dfbcf074abd76ebe05f4707ae758f57 https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...
pm215 4y ago
Everybody loves division :-) The footnote that says "most ARM processors still don't have integer division" seems a little out of date to me -- all 64-bit Arm cores do, of course, and on the 32-bit side anything since v7VE (Cortex-A15 was the first of these, released 2011) does, and all the M-profile microcontroller cores have it. It's a bit unfortunate it didn't make it into v7, since that's a pretty popular 32-bit compilation target, but the runtime libs should use it even if the compiler can't opencode a division insn.
- andoma 4y ago
  Pretty sure some of the low-end Cortex-M cores (M0 and M1) lacks instructions for division.
  - pm215 4y ago
    Good point, it's not in v6M, though it is in v8M baseline, which is the v8 equivalent. So M0, M0+ and M1 don't have it but I think everything else M-profile should.
    - colejohnson66 4y ago
      Given that Ken said most ARM processors, the nerd sniping becomes: what percentage of all ARM cores are M0/M0+/M1. I'd guess a lot (maybe not half though). Don't all micro SD cards have a processor inside them? They're probably almost all ARM...
jiggawatts 4y ago
For comparison, a modern CPU architecture such as the Zen 4 can perform a 64-bit integer division in 10-18 clock cycles, which means it is processing 3.5 to 6.5 bits per clock. Ref: https://www.agner.org/optimize/instruction_tables.pdf https://www.agner.org/optimize/instruction_tables.pdf
powerpiglet 4y ago
> Signed multiplication and division use an internal flag called F1 to keep track of the sign. The F1 flag is toggled by microcode through the CF1 (Complement F1) micro-instruction. The F1 flag is implemented with a flip-flop, along with a multiplexer to select the value. It is cleared when a new instruction starts, set by a REP prefix, and toggled by the CF1 micro-instruction. Does this mean that one can run 'REP DIV' and get a negated quotient?
- kens 4y ago
  Yes, REP IDIV will negate the quotient. Andrew Jenner discusses that: https://www.reenigne.org/blog/8086-microcode-disassembled/ https://www.reenigne.org/blog/8086-microcode-disassembled/
  - powerpiglet 4y ago
    That's fascinating. Thanks for the pointer.

127 points by picture 4y ago

kens 4y ago

Author here. Hopefully you're not all tired of the 8086 by now :-)

LanternLight83 4y ago
Can't speak for everyone, but I'm lovin' it, thanks!
deleted 4y ago
[deleted]
jacquesm 4y ago
Never! I really should get that other chip to you...
kergonath 4y ago
Absolutely not! I can’t say I understand everything but I love reading your work.
rwmj 4y ago
Are there any physical indications of the order in which instructions were added? I mean to say: Is there any indication that (for example) they added DIV last, perhaps because it's complicated and they didn't know if they could fit that in.
- kens 4y ago
  Andrew Jenner pointed out that the microcode for the string (block move) operations doesn't exactly match the flowchart in the documentation, and the micro-instructions are kind of scattered around. So it's likely that the string operations were modified late in the process. As far as the other instructions, I haven't seen any particular indication of the order.
userbinator 4y ago
Do you think the 8086/8088 were well-optimised/efficient in general? In other words, had they spent some more effort, could they have reduced the transistor count and reduced the number of cycles the instructions take without changing the functionality?
- kens 4y ago
  The 8086/8088 look pretty well-optimized in many ways: the design of the instruction set, the architecture, the microcode, and the silicon layout. Studying it closely, I've seen multiple things that are more clever than I expected, and haven't seen anything that makes me shake my head in dismay.
bonzini 4y ago
Just a note that, just like AAD is a multiplication (and add) in disguise, AAM is an 8-bit unsigned division in disguise and also uses the CORD subroutine.

CalmStorm 4y ago

For modern CPU, is microcode still used for division or there are better and faster alternatives?

rep_lodsb 4y ago
The 80186 already implemented the loop for multiplication and (unsigned) division in dedicated logic that could do 1 bit per cycle. The microcode only had to set up the registers, test for overflow, and undo the final subtraction if it underflowed (since it now used a non-restoring algorithm). Starting with the 486 there is likely no longer any microcode involved, and newer chips can handle multiple bits per step. See end of article, the first algorithm to do this comes from 1957!
bri3d 4y ago
It's way more complex than this on modern CPUs, so it's harder to explain. > is microcode still used for division? Yes, almost everything on a modern CPU uses "microcode" of some kind, although the term gets kind of hazy, since everything is out-of-order and a lot of instructions are issued in parallel. In a typical modern CPU, the "frontend" will decompose instructions into uOps, which then get pushed into a "reservation station" / "scheduler." The scheduler queues and reorders various uOps in various surprising and complicated ways to try to account for interdependencies and memory latency. Eventually, a uOp is issued into to an "execution port," which is connected to a fixed-function piece of logic that actually performs part or all of an operation (for example, an Arithmetic Unit / ALU). But, while microcode will be _involved_ still, most modern CPUs will have fixed-function hardware for the meaty parts of the division instruction - they generally speaking won't implement division _purely_ using microcode like the algorithm documented in the article. > are there better and faster alternatives? They're not "alternatives" per se, but there are a _lot_ of ways to implement division algorithmically, and a _lot_ of ways to trade size for speed. Improving integer division performance has been a fairly big focus in newer CPU microarchitectures, with major improvements arriving in the latest Intel, AMD, and Apple Silicon architectures. https://uops.info/table.html https://uops.info/table.html will show how many uOps a given x86 instruction decomposes to, what ports it uses, and rough latency estimates for the instruction's execution. Here's some reading I found, with a lot of references: * A discussion of various modern division implementations: https://stackoverflow.com/questions/71420116/why-is-there-only-little-difference-in-integer-division-throughput-with-larger-v https://stackoverflow.com/questions/71420116/why-is-there-on... * Performance comparison of integer division in modern architecutures with some implementation speculation: https://news.ycombinator.com/item?id=27133804 https://news.ycombinator.com/item?id=27133804 * An in-depth look at the division unit in mid-old Intel CPUs (Penryn), look for "Radix-16" : https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=16afaef17dfbcf074abd76ebe05f4707ae758f57 https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...

pm215 4y ago

Everybody loves division :-) The footnote that says "most ARM processors still don't have integer division" seems a little out of date to me -- all 64-bit Arm cores do, of course, and on the 32-bit side anything since v7VE (Cortex-A15 was the first of these, released 2011) does, and all the M-profile microcontroller cores have it. It's a bit unfortunate it didn't make it into v7, since that's a pretty popular 32-bit compilation target, but the runtime libs should use it even if the compiler can't opencode a division insn.

andoma 4y ago
Pretty sure some of the low-end Cortex-M cores (M0 and M1) lacks instructions for division.
- pm215 4y ago
  Good point, it's not in v6M, though it is in v8M baseline, which is the v8 equivalent. So M0, M0+ and M1 don't have it but I think everything else M-profile should.
  - colejohnson66 4y ago
    Given that Ken said most ARM processors, the nerd sniping becomes: what percentage of all ARM cores are M0/M0+/M1. I'd guess a lot (maybe not half though). Don't all micro SD cards have a processor inside them? They're probably almost all ARM...

jiggawatts 4y ago

For comparison, a modern CPU architecture such as the Zen 4 can perform a 64-bit integer division in 10-18 clock cycles, which means it is processing 3.5 to 6.5 bits per clock. Ref: https://www.agner.org/optimize/instruction_tables.pdf https://www.agner.org/optimize/instruction_tables.pdf

powerpiglet 4y ago

> Signed multiplication and division use an internal flag called F1 to keep track of the sign. The F1 flag is toggled by microcode through the CF1 (Complement F1) micro-instruction. The F1 flag is implemented with a flip-flop, along with a multiplexer to select the value. It is cleared when a new instruction starts, set by a REP prefix, and toggled by the CF1 micro-instruction. Does this mean that one can run 'REP DIV' and get a negated quotient?

kens 4y ago
Yes, REP IDIV will negate the quotient. Andrew Jenner discusses that: https://www.reenigne.org/blog/8086-microcode-disassembled/ https://www.reenigne.org/blog/8086-microcode-disassembled/
- powerpiglet 4y ago
  That's fascinating. Thanks for the pointer.