Add CIL instructions to detect arithmetic overflows without raising an exception

[RobertBouillon]

The current implementation of the CIL ISA runs counter to the design guidelines for .NET exception handling with respect to overflow handling. The only way to check for an overflow is to raise an exception, however overflows can occur as a normal condition; there is no way to check for an overflow without raising an exception.

The workaround is expensive arithmetic checking which involves up-casting the types or operation-specific legacy c-style checks. Both have their drawbacks and are pretty expensive, especially when you're checking for overflows in 64-bit integers.

It's pretty silly to have to jump through such elaborate hoops to determine if you've overflowed to avoid excessive exceptions when there's likely an overflow flag tripped somewhere on the hardware already to which we simply don't have access.

Since there are already instructions that have to check for an overflow (e.g. add.ovf), I think all that really needs to be done as far as implementation is to find the best way in the IL and languages to expose an overflow flag without raising an exception. The instruction (something like add.sovf for silent) could simply push a second value to the stack indicating whether or not the operation overflowed. Language support might be a bit trickier, but the IL instruction would be a great start since we could, at very least, emit it in code. Ultimately, I'd love to see support all the way through to expressions (e.g. Expression.AddSilentChecked).

Since this is really meant to address performance, I'd also like to make another suggestion. Typically, overflow flags are set after each operation. Checking this flag after every arithmetic operation essentially doubles the CPU work (best case) and can make for ugly (hard to maintain) code. Practically speaking, overflow checking doesn't NEED to occur after every arithmetic operation, and in my experience, rarely does. Typically, it only needs to be checked after a batch or an equation involving multiple operands (Think a SUM or FMA). A latch rather than a flag would be far more useful, since it can be cleared at the start of the operation and checked at the end of it, rather than after each instruction. That's O+2 rather than O2. AFAIK the VM doesn't have any persistent flags, but I think a latch and / or a flag would be better than putting the overflow result on the stack.

category:proposal
theme:msil
skill-level:expert
cost:extra-large

[RobertBouillon]

A suggestion for C#:

UPDATE: See new suggestion below.

//Traditional checking
checked(a + b); 

//Non-exception overflow check
var overflow = checked(a + b); 

//But it can get tricky. Would this work?
int[] numbers = new[]{1,2,3,4};
var overflow = checked {
  var sum = numbers.Sum();
}

[mikedn]

Ultimately, I'd love to see support all the way through to expressions (e.g. Expression.AddSilentChecked).

What uses cases are there that would justify the enormous amount of work required for this kind of "all the way" support? Aren't perhaps a few ADD/SUB/MUL with overflow intrinsics sufficient?

Since this is really meant to address performance, I'd also like to make another suggestion. Typically, overflow flags are set after each operation. Checking this flag after every arithmetic operation essentially doubles the CPU work (best case) and can make for ugly (hard to maintain) code. Practically speaking, overflow checking doesn't NEED to occur after every arithmetic operation, and in my experience, rarely does. Typically, it only needs to be checked after a batch or an equation involving multiple operands

It's not clear how such a thing would be implemented efficiently. CPU's don't have direct support for this.

[RobertBouillon]

Aren't perhaps a few ADD/SUB/MUL with overflow intrinsics sufficient?

I think a few ADD/SUB/MUL with overflow intrinsics would be a good start, and hopefully of small enough scope to be done soon ;) Maybe this should be broken into two different issues?

What uses cases are there that would justify the enormous amount of work required for this kind of "all the way" support?

Expressions are a LINQ feature. LINQ providers exist as a way to execute LINQ expression trees on non-native platforms (Such as SQL). Requiring that an exception be raised by a LINQ provider creates a .NET-specific dependency on LINQ providers which are, inherently, not .NET. In my use-case, specifically, I have LINQ providers that compile down to CUDA, OpenCL, OpenMP, etc. The LINQ expressions are processed on vectors rather than distinct values, making it impossible implement the Checked variant of arithmetic operations. I still check for overflows, but only as part of the batch and the feature is outside of the LINQ framework. An Expression.CheckedBlock that mimics the example above would be ideal.

It's not clear how such a thing would be implemented efficiently. CPU's don't have direct support for this.

IMO we don't have hardware support because of inadequate language / runtime support. CPU manufacturers bake in new instructions and features because it makes software better. I don't know of any language that has first-class support for overflow checks after batch operations. We don't even have the ability to check for overflows without choking the runtime with exceptions.

Databases, financial systems, and most data systems that care about data accuracy have to check for overflows. I think we're all used to hacking it - you either check EVERY operation, or allocate the largest possible data size, and both solutions cost you performance. (Or you just don't even consider overflows and wait until exceptions are thrown). That doesn't mean it's the right way or that we can't improve it. If I had an overflow latch I could check, a lot of code I've written would be faster & leaner.

With CPU support, this latch could be set in the same cycle as the arithmetic operation. Since most CPUs have an overflow flag, a latch doesn't seem like a stretch. Without CPU support, we could easily mimic this with an Or-Assign of the overflow flag to a value on the stack.

If an overflow latch is something we need, and I think it is, I think we should drive it.

[Suchiman]

//Non-exception overflow check
var overflow = checked(a + b); 

this is valid code today, the overflow variable contains the result of the expression in checked(expression).

[RobertBouillon]

this is valid code today, the overflow variable contains the result of the expression in checked(expression).

Not sure how I overlooked that... how else would you get the result? Thank you.

The checked block (check-defined scope) doesn't return anything, so maybe we could use that.

I also thought that adding a new keyword might work, but after playing with it (see below), I don't think it does, because for a single expression you're going to want the result AND the overflow flag, and the syntax just doesn't work out for returning two values. I thought a TryX pattern might work since we we could replace the function with some compiler magic, but I don't think a TryX pattern works, either, because you can't efficiently aggregate the results. So far, I think returning an overflow value from a checked block works the best at the C# level.

For me, the problem still comes down to the IL. Without support for overflow checking that doesn't raise an exception, anything we build on top of the CLR is going to be a hack. It looks like most hardware supports saturation arithmetic, but practically speaking, I can't really use this because Primitive.MinValue and Primitive.MaxValue become ambiguous with overflows. It's not really a solution because I still have to add additional application logic to disambiguate legitimate Min/Max values from overflows. All I really want to know is if I've overflowed during a vector operation without having to jump through hoops.

//Traditional checking
var c = checked(a + b); 
checked
{
  var c = a + b; 
}

//Non-exception overflow check
var overflow = checked
{
  var c = a + b; 
}

//But it can get tricky. Would this work?
int[] numbers = new[]{1,2,3,4};
var overflow = checked {
  var sum = numbers.Sum();
}

//A new keyword lacks that ability to return both the result AND the overflow
var overflowed = overflow(a + b, out var result); //Brutally ugly. Feels like a function, but it's a keyword.
var overflowed = overflow
{
  var c = a + b;  //If we do this, we may as well reuse the checked keyword.
}

//Intrinsics wouldn't really solve the problem. You'd need too many overloads, it's awful to code, and
//you still have to aggregate the result. We really need compiler support, here. At least from a C#
//Perspective.
//bool TryAdd(int a, int b, out int result) {...}
var x = a + (b * c); //Prototype
var overflow = !Int32.TryMultiply(b, c, out var mul_b_c);
overflow |= !Int32.TryAdd(mul_b_c, a, out var result);

//Inversed Try. Return result and out the overflow
//int TryAdd(int a, int b, out bool overflow) {...}
var x = a + (b * c); //Prototype
var x = Int32.TryAdd(Int32.TryMultiply(b, c, out var mul_overflow), out var add_overflow);
var overflow = mul_overflow | add_overflow;

[mikedn]

Expressions are a LINQ feature.

I wasn't talking specifically about the LINQ part but the whole IL & C# support. That's a rather costly endeavor and it's not even clear how/if it can be implemented efficiently (e.g. the push a second value onto the stack is unlikely to be practical).

In my use-case, specifically, I have LINQ providers that compile down to CUDA, OpenCL, OpenMP. The LINQ expressions are processed on vectors rather than distinct values, making it impossible implement the Checked variant of arithmetic operations.

And how would those handle overflow checking?

Since most CPUs have an overflow flag, a latch doesn't seem like a stretch.

Actually it's likely to be a stretch. Even the current overflow flag can be problematic for compilers, it's an extra value that some instructions produce in a specific register that can't be manipulated like other registers. A latch is likely to be worse because the compiler will have to be careful not to mix instructions coming from different checked/unchecked contexts or the CPU will need to provide multiple such flags and the instructions will need to be able to select the destination flag.

IMO we don't have hardware support because of inadequate language / runtime support. CPU manufacturers bake in new instructions and features because it makes software better.

I don't know, it's likely the other way around. The difficulty in supporting this properly in both hardware and compilers prevented it from becoming a mainstream feature.

You can see this even in your attempt above - an non-throwing overflow checking expression has to produce 2 values, the actual numeric value and an overflow indicator. So what is the type of an expression like overflow(a + b)? Most likely it has to be a struct, something similar to Nullable<T>. And how do you implement that in hardware? I don't know, probably you need multiple registers to store such a value, it's not like they're going to add 33/65 bit registers to store the overflow flag. Or you need to invent a representation similar to the floating point representation that allows you to encode special values such as NaN.

[RobertBouillon]

So there are 3 layers here to talk about:

1. Hardware
2. IL
3. C# (And other high-level languages)

Strictly hardware, overflows in register-based architectures are typically stored in a SFR you can pull out with a bitmask. So adding a latch on top of that register bit and exposing the latch via another SFR bit is probably a trivial number of transistors. A latch would be set in the same cycle so there would be no performance cost. The latch would allow software to detect overflows without requiring the software to check the SFR for an overflow after every operation. Instead, overflows would be checked after a batch of operations.

From the perspective of C#, we already know that there are two common use-cases for checking for overflows - a single expression and a block of expressions, as supported by the checked keyword and block, respectively. The problem is that checked only throws exceptions and there's no way to change that behavior. I have a use-case that treats overflows as common and expected, and thus the design choice to only use exceptions to communicate overflows really hinders me.

What I'm proposing we change the behavior of the checked keyword to allow overflows to be identified and handled in pretty much the same way as they're being handled now, only without raising exceptions. To do this, we'd have to find a way to return a value indicating whether or not an overflow occurred. I don't know what the best way is to do this, but right now I like the idea of returning a bool from a checked block (var overflowed = checked { var c = a + b; }). The compiler can detect the assignment operator and change the IL generated accordingly.

I think both of the above solutions are reasonable and relatively simple. The tricky part is the IL - how we actually make it work, and without hardware support, how do we emulate an overflow latch without taking a performance hit? This is why I posted in CoreCLR.

The checked keyword already alters the compiled IL by replacing add with add.ovf, which throws an exception in the event of overflow. So if we wanted to detect an overflow without raising an exception, we'd need a new instruction, like add.sovf. If the checked block is assigned to a bool, then add.sovf is generated instead of add.ovf. add.sovf would emulate the latch, if required (which it would be, at first). The start of the checked block would clear the overflow latch, and the end of the block would push the value in the latch to the stack (and assign it to the variable). The checking and clearing of the latch could be handled by compiler-generated intrinsics which would map to a default implementation that emulates hardware latch functionality.

So after kicking the idea back and forth a bit, I don't think would be that much work. We'd need:

1. A new instruction add.sovf that works very much the add.ovf instruction. Without hardware support, the overflow value is or-assigned to a latch (a Boolean the stack?) instead of conditionally branching to an exception. With hardware support, this would act identically to add.
2. Two intrinsic functions to clear and to read the value of the overflow latch.
3. checked blocks would optionally emit add.sovf instead of add.ovf if the checked block is assigned to a Boolean. If add.sovf is used, then the behavior of the block changes from raising an exception to returning a Boolean.

[verelpode]

How about doing it via System.Runtime.Intrinsics.X86 instead of new CIL instructions? Although I very much like your idea of doing it via new CIL instructions, I'm also thinking about what would give the proposal the best chance of being accepted and implemented in the near future without long delays. Therefore, to get what we want without waiting 5-10 years for it to arrive, I suggest doing it via System.Runtime.Intrinsics.X86, and then we can build the rest of it ourselves to our own likings.

I had a quick look through System.Runtime.Intrinsics.X86 in NETFW 5.0. Currently I don't see anything that gives access to the carry and overflow flags, but maybe I missed it because my knowledge of Intel instructions is not great.

Anyway, if it's not already there, then the proposal can be to add something to System.Runtime.Intrinsics.X86 to give people access to the preexisting carry and/or overflow flags that the x86-32 and x86-64 processors already calculate.

In one of the classes similar to System.Runtime.Intrinsics.X86.Bmi2 or rather whichever of those classes is most suitable, new methods could be added like this:

public static uint Add(uint left, uint right, out bool carry);
public static ulong Add(ulong left, ulong right, out bool carry);
public static ulong Multiply(ulong left, ulong right, out bool overflow);

Anyway then we'd be able to use it to write overflow-reporting methods like this:

public static uint? TryMultiply(uint a, uint b)
{
	if (System.Runtime.Intrinsics.X86.Bmi2.X64.IsSupported)
	{
		bool overflow;
		uint result = System.Runtime.Intrinsics.X86.Bmi2.X64.Multiply(a, b, out overflow);
		if (overflow) return null;
		return result;
	}
	//... else perform slower software-fallback here....
}

Note the preexisting method Bmi2.X64.MultiplyNoFlags(ulong, ulong, ulong*); produces a 128-bit product from two 64-bit parameters, thus it can already be used to detect multiplication overflows, but using it for this purpose seems like a bit of a hack. I wonder if the proper way would be to stay with a 64-bit product and just output the overflow flag, not calculate the full 128-bit product, but this depends on processor details that I'm not so familiar with.

Maybe the preexisting method Bmi2.X64.MultiplyNoFlags is already the best way overall ? Someone with more instruction knowledge could answer this.

Although I'm no expert in this particular area, it seems like it'd probably be a minimal amount of work to add the necessary methods to System.Runtime.Intrinsics.X86. This isn't some complex vector-acceleration topic. In this overflow-checking case, the applicable instructions are merely the normal basic addition, subtraction, multiplication instructions, but with access to read the carry and/or overflow flags. Likewise the carry flag is something preexisting and long-standing, so I don't see any big difficulties with doing this.

In contrast, if the proposal is to create new CIL instructions, then it's much more work than adding methods to System.Runtime.Intrinsics. Sure I like the idea of new CIL instructions, and yes new CIL instructions would be better than what I suggested with System.Runtime.Intrinsics, but people also need to consider what can be done in the short-term. Some additions to System.Runtime.Intrinsics are far more likely to be implemented in the short-term than any new CIL instructions.

Note:
Because of Intel x86 quirks, it's possible that the best way is already supported. Possibly the best way to check for addition overflow isn't to use the carry flag, and instead to use the less-than operator. And possibly the best way to check for multiplication overflow is the Bmi2.X64.MultiplyNoFlags that is already supported in NETFW 5.0. Someone with more in-detail CPU knowledge could answer this.

[RobertBouillon]

I'm not a huge fan of managed intrinsics, personally. I guess there's a demand for it, since it's out there, but I don't like the pattern. I wouldn't use them.

If talking about a short-term workaround, I'd prefer something more abstract & complete, perhaps in a NuGet:

abstract class StatefulArithmetic
{
  //Create instance based on the current platform. Return software implementation if platform is not supported.
  public static StatefulArithmetic Create() { }

  //Latch that stays true if any operation has overflowed unless manually set to false
  public abstract bool Overflowed { get; set; }

  public abstract long Multiply(long a, long b);
}

class Foo
{
  static void Bar()
  {
    var arith = StatefulArithmetic.Create();
    long l = 0;
    for(int i = 0; i < 10; i++)
      l = arith.Multiply(l,2);
    if(arith.Overflowed)
      HandleOverflowScenario();
  }
}

I prefer this approach because:

1. Create can return a software "fallback" if hardware is not supported.
2. Platform check is only run once. Platform check is abstracted from the user.
3. Pattern overtly supports a latch, allowing checks to be deferred to the end of a batch.
4. Is probably the same amount of work as intrinsics, with better future-proofing and a friendlier API.

This is, of course, in-lieu of first-class BCL methods, like Int32.TryAdd, which would be preferred. If any effort goes into putting it into the BCL, though, it should be aligned with some sort of INumeric interface for the sake of arithmetic support in generic operations.

[Alxandr]

There's a guy working on a rust to CIL compiler. He details in this blog post how the lack of an exception-less checked add is one of the issues he had to deal with and how he's doing checks using less than manually before operations to be able to know if the operation overflowed.

I figured this usecase at least warranted documentation on this issue.