logoalt Hacker News

CaliforniaKarlyesterday at 9:19 PM3 repliesview on HN

I wonder, if C used Reverse-Polish notation for math operations, would compilers have been able to target the 8087 better than they did?


Replies

ack_completetoday at 3:56 AM

Nah. As others have said, translating infix to RPN is pretty easy to do. The nasty part was keeping values within registers on the stack, especially within loops. The 8087 couldn't do binary ops between two arbitrary locations on the stack, one had to be the top of stack. This meant that if you need to add two non-top locations, for example, you had to exchange (FXCH) one of them to the top of the stack first. This meant that optimized x87 code tended to be a mess of FXCH instructions.

Complicating this further, doing this in a loop requires that the stack state match between the start and end of the loop. This can be challenging to do with minimal FXCH instructions. I've seen compilers emit 3+ FXCH instructions in a row at the end of a loop to match the stack state, where with some hairy rearrangement it was possible to get it down to 2 or 1.

Finally, the performance characteristics of different x87 implementations varied in annoying ways. The Intel Pentium, for instance, required very heavy use of FXCH to keep the add and multiply pipelines busy. Other x87 FPUs at the time, however, were non-pipelined, some taking 4 cycles for an FADD and another 4 cycles for FXCH. This meant that rearranging x87 code for Pentium could _halve_ the speed on other CPUs.

show 1 reply
kensyesterday at 9:41 PM

My compiler knowledge is limited, but I think that you end up with the same parse tree at a very early level of processing, whether you use Reverse-Polish notation or inline notation. So I don't think a language change would make a difference.

bonziniyesterday at 11:36 PM

Converting to RPN is, roughly speaking, the easiest way to generate code for either register or stack architectures.

Once you have a parse tree, visiting it in post order (left tree, right tree, operation) produces the RPN.