Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

We Need Hardware Traps for Integer Overflow

blog.regehr.org

Post reply on HN
Print view View original

31–40 of 112 posts

Re: We Need Hardware Traps for Integer Overflow

#31

Post by willvarfar »

(Mill team)

With apologies to those tired of hearing about the new Mill CPU let me explain how the Mill traps on integer overflow:

For overflow-able arithmetic operations, we support four modes:

* truncate

* except

* saturate

* double-width

With excepting overflow, the result is marked as invalid (we term it "Not-a-Result (NaR)").

As these invalid results are used in further computation, the NaR propagates.

When you finally use the result in non-speculatively e.g. store it or branch on it then the hardware faults.

NaRs have lots of other uses.

This is described in the Metadata talk http://millcomputing.com/topic/metadata/

And http://millcomputing.com/topic/introduction-to-the-mill-cpu-... for a broader overview.

Re: We Need Hardware Traps for Integer Overflow

#32

Post by userbinator »

It's a little amusing that x86 has the INTO instruction, a single byte opcode at position CEh, that was designed specifically for this purpose and was there since the 8086, but when AMD designed their 64-bit extensions, it turned into an invalid instruction (and Intel was forced to go along, presumably for compatibility.) A rather shortsighted move, I think; instead of having a possibly useful (but not previously often-used) instruction, that single-byte opcode becomes wasted in 64-bit mode. With it, adding overflow-trapping arithemtic support to a compiler would be trivial and only add 1 extra byte to each arithmetic operation that needs it.

Ditto for BOUND, which is useful for automatic array bounds-checking - it performs both lower and upper bounds checks.

Also, I don't really get why integers wrapping around should be "unexpected". It is only to those who don't understand how integers work. The saying "know your limit, play within it" comes to mind.

Re: We Need Hardware Traps for Integer Overflow

#35

Post by danbruc »

perlgeek wrote: post #33

My assembler is very rusty, couldn't compilers check the carry flag on i386 after a math operation that could potentially overflow, and handle the trapping in software?

Of course and this is what actually happens if you enable overflow checking but it comes at a price - if your code is correct you will never need the checks but you will execute them every time.

Re: We Need Hardware Traps for Integer Overflow

#36

Post by al2o3cr »

maggit wrote: post #11
sounds wrote: post #9

Modern CPUs don't like traps ("exceptions"). The exception causes a pipeline flush which kills performance for math-intensive code. For example, detecting integer overflow on x86 and x86_64 CPUs is easy: check the overflow flag after every arithmetic operation. It would only be slightly more difficult to detect overflow for SSE (vector) operations, which would require doing some bit masking and shifting. For a langua…

The entire premise of the linked article is that doing it the way you suggest is too expensive for the common case, where no overflow happens. Further, it implicitly asserts that the cost of a hardware trap/exception, while great, will be offset by the savings from the common case. Now, it doesn't back these assertions with much data, but neither do you :)

The problem is that potentially-overflowing integer instructions make a real mess out of things like out-of-order execution and speculative execution.

For data to back this, see your favorite computer architecture reference, particularly anything that discusses the consequences of highly-complex instructions in things like the VAX.

Re: We Need Hardware Traps for Integer Overflow

#37

Post by stormbrew »

zvrba wrote: post #26

Or you could have a "sticky" overflow flag, so that you could check for overflow after each complete expression instead of after every single math operation. This needs one new flag and one new conditional instruction. (Plus compiler modifications.)

I don't know if this solves all the associated problems. If part of the chain of operations isn't side-effect-free, eg. function call, you'll still have to check more than once for the whole chain. And if you want to do more than throw an error/exception you may need to re-run the operations on a slow path to get the correct result.

But I like it a lot even so. For a general case it seems like it would help.

Re: We Need Hardware Traps for Integer Overflow

#39

Post by JoshTriplett »

jjoonathan wrote: post #16
JoshTriplett wrote: post #7

Personally, I'd like to see more programming done in languages that simply don't allow integer overflow in the first place. Most current languages have arbitrary-precision integers; well-implemented arbitrary-precision integers are quite efficient when they fit in a machine word, and as efficient as possible when larger. Sure, you'll lose a bit of performance due to checks for overflow, but those checks need to exist…

Checks are the smallest cost of bignums. Dynamic allocation isn't free, it's terribly expensive. Dereferencing pointers isn't free, it's terribly expensive. It's one thing for a scripting language (where people expect poor, inconsistent performance) to have automatic bignums but it's quite another for a language in which people will be writing performant code to have automatic bignums. They introduce a thousand diffi…

> Dynamic allocation isn't free, it's terribly expensive. Dereferencing pointers isn't free, it's terribly expensive.

So don't do either of those things until your arithmetic overflows the size of a word; until then, you can keep numbers in a register.

Re: We Need Hardware Traps for Integer Overflow

#40

Post by JoshTriplett »

userbinator wrote: post #32

It's a little amusing that x86 has the INTO instruction, a single byte opcode at position CEh, that was designed specifically for this purpose and was there since the 8086, but when AMD designed their 64-bit extensions, it turned into an invalid instruction (and Intel was forced to go along, presumably for compatibility.) A rather shortsighted move, I think; instead of having a possibly useful (but not previously oft…

Those instructions generate an interrupt; you'd have to define the OS ABI to make those instructions trap back to the application in a catchable way.
Post reply on HN