The core.checkedint module isn't meant to be used directly like this, it has the bricks to build partially library-defined safe integral types:


void main(in string[] args) {
    import std.stdio, std.conv, core.checkedint;

    assert(args.length == 3);
    immutable xy = args[1 .. $].to!(int[2]);

    bool overflow = false;
    immutable result = muls(xy[0], xy[1], overflow);
    assert(!overflow);
    writeln("Product: ", result);
}


Calls to core.checkedint functions are eventually meant to be replaced by faster compiler intrisics in all D compiler, that use the carry and overflow bits present in most CPUs.

But to be more useful, the compiler should replace safe integral operations with regular (faster) integral operations where it statically knows they can't overflow/underflow. In D there is value range propagation (that probably will be improved in future) that can be used for this. If the compiler replaces the calls to core.checkedint functions with intrinsics, it can also replace some calls with regular operations where it sees the value range makes an overflow impossible. This is a naive example:


void main() {
    import std.stdio, core.checkedint;
	
	ubyte x = 100;
	ubyte y = 200;	

    bool overflow = false;
    immutable result = muls(x, y, overflow);
    assert(!overflow);
    writeln("Product: ", result);
}


With a library-defined type the first program could look:


void main(in string[] args) {
    import std.stdio, std.conv, std.safeintegral;

    assert(args.length == 3);
    SInt x = args[1].to!int;
    SInt y = args[2].to!int;

    immutable result = x * y;
    assert(!result.overflow);
    writeln("Product: ", result);
}


where the operator "*" of SInt calls muls().


But while operations with ubyte and int values are able to use the range of values (to avoid casts), a library-defined type like SInt that calls muls() currently loses the knowledge of the range of the operands. How do you solve this problem? If you solve this problem for SInt, you can solve it for lot of other library-defined types.

A possible piece of the solution is the recently suggested __trait(valueRange, exp), but alone that's not enough.

Bye,
bearophile

On 7/27/2014 6:52 AM, bearophile wrote:
> A possible piece of the solution is the recently suggested __trait(valueRange,
> exp), but alone that's not enough.

Instead of adding more language features, purpose existing ones:

    assert(exp >= min && exp <= max);

Walter Bright:

> Instead of adding more language features, purpose existing ones:
>
>     assert(exp >= min && exp <= max);

I don't see how this can solve the problem I have discussed. Please explain better.

Bye,
bearophile

On Sunday, 27 July 2014 at 20:20:54 UTC, Walter Bright wrote:
> On 7/27/2014 6:52 AM, bearophile wrote:
>> A possible piece of the solution is the recently suggested __trait(valueRange,
>> exp), but alone that's not enough.
>
> Instead of adding more language features, purpose existing ones:
>
>     assert(exp >= min && exp <= max);

That's great for communicating bounds from code to the compiler, but what bearophile is talking about is accessing the compiler's value rage propagation information in code. The other way around.

On 7/27/2014 1:54 PM, bearophile wrote:
> Walter Bright:
>
>> Instead of adding more language features, purpose existing ones:
>>
>>     assert(exp >= min && exp <= max);
>
> I don't see how this can solve the problem I have discussed. Please explain better.

That tells the compiler that the exp is within min and max after that point.

On Monday, 28 July 2014 at 04:44:04 UTC, Walter Bright wrote:
> On 7/27/2014 1:54 PM, bearophile wrote:
>> Walter Bright:
>>
>>> Instead of adding more language features, purpose existing ones:
>>>
>>>    assert(exp >= min && exp <= max);
>>
>> I don't see how this can solve the problem I have discussed. Please explain better.
>
> That tells the compiler that the exp is within min and max after that point.

Conflating run time debug checks with programmer provided guarantees sounds dangerous. Call it "assume" not "assert" then.

Walter:

>Instead of adding more language features,<

Perhaps you can't solve this problem in a sufficiently clean way without adding language features (and a assume() is not the solution, see below).

---------------------

Ola Fosheim:

> Conflating run time debug checks with programmer provided guarantees sounds dangerous. Call it "assume" not "assert" then.

But this still missed the point. I am not interested in annotations, in this thread I am not asking for a built-in assume() (or for some weird kind kind of assert() that is much worse).

Let's go back to the second example I've shown:

void main() {
    import std.stdio, core.checkedint;
	
    ubyte x = 100;
    ubyte y = 200;	

    bool overflow = false;
    immutable result = muls(x, y, overflow);
    assert(!overflow);
    writeln("Product: ", result);
}


Here I am not willing to add an assume(). Here at the call point of muls() x and y have a full range of ubytes, so the range analysis tell the compiler their product will not overflow, so it can replace the muls() with a regular product and leave overflow untouched. This is faster.

The same kind of optimization is desired for a SInt or other library-defined types. So the point of this discussion is how to do this. The problem is that the compiler has some static information about ranges, but to optimize away user-defined types such information needs to be read and given to "static ifs" to replace the calls to muls() to calls to regular operations.

Bye,
bearophile

On Monday, 28 July 2014 at 08:42:16 UTC, bearophile wrote:
>
> The same kind of optimization is desired for a SInt or other library-defined types. So the point of this discussion is how to do this. The problem is that the compiler has some static information about ranges, but to optimize away user-defined types such information needs to be read and given to "static ifs" to replace the calls to muls() to calls to regular operations.

Not sure if this is the right way to do carry/overflow optimization, but I can see the value of having range information when doing CTFE for building minimal lookup tables/perfect hashing etc.

IMO muls should yield 2N bits of output for N bits input, then the compiler should do strength reduction.

Adds should be done on N+1 bits types, using 33 bit output for 32 bits input, then strength reduce it to >=32 bit output if both operands are 31 bits or less?

Ola Fosheim Grøstad:

> IMO muls should yield 2N bits of output for N bits input, then the compiler should do strength reduction.
>
> Adds should be done on N+1 bits types, using 33 bit output for 32 bits input, then strength reduce it to >=32 bit output if both operands are 31 bits or less?

I copy here a comment I've written here:
https://github.com/D-Programming-Language/phobos/pull/1866#issuecomment-50216839

A core.checkedint function like muls() accepts two ints or two longs. What if you have a uint and int? An example:

void main() {
    import std.stdio, core.checkedint;
    int x = -1;
    uint y = 3_000_000_000;
    writeln(x, " ", y);
    writeln(x * y);
    bool overflow = false;
    immutable r1 = muls(x, y, overflow);
    writeln(r1, " ", overflow);
    overflow = false;
    immutable r2 = mulu(x, y, overflow);
    writeln(r2, " ", overflow);
}

It outputs:

-1 3000000000
1294967296
1294967296 false
1294967296 true

Here the overflow boolean from the muls() is false, but the result is wrong (it's -3_000_000_000 that is not representable by both ints and uints).

Bye,
bearophile

On Sunday, 27 July 2014 at 20:20:54 UTC, Walter Bright wrote:
> On 7/27/2014 6:52 AM, bearophile wrote:
>> A possible piece of the solution is the recently suggested __trait(valueRange,
>> exp), but alone that's not enough.
>
> Instead of adding more language features, purpose existing ones:
>
>     assert(exp >= min && exp <= max);

To what extent can a compiler use assertions? Can it work backwards from an assert to affect previous code?

void foo(int a)
{
    enforce(a & 1);
    assert(a & 1);
}

void bar()
{
    assert(a & 1);
    enforce(a & 1);
}

Which, if either, of those calls to enforce can be removed?