[Issue 9850] New: Compiler support to implement efficient safe integrals

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=9850

           Summary: Compiler support to implement efficient safe integrals
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: DMD
        AssignedTo: nobody at puremagic.com
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2013-03-31 15:02:18 PDT ---
The silent overflow of integers causes bugs in D programs. To solve similar
problems Ada language allows to perform safe operations, C# language allows to
write safe expressions and safe blocks of code, and Clang compiler has an
option to produce run-time overflow errors in C and C++ programs. D language
tries to remove bugs from programs where possible, and to be safer than C++.

In C programs sometimes the unsigned integers wrap around. In some cases this
is desired by programmer, but in other cases it is not desired, and it's
essentially a bug. The C language currently doesn't offer the programmer to
tell apart such two cases, that are very different.

(One example where the wrap-around of unsigned integers is expected by the
programmer is when you have to perform an exploration of a 2D grid. If you use
an unsigned X  coordinates, when your exploration leads you outside a row, both
below the zero X coordinate or over the maximum X coordinate, the wrap-around
of the unsigned value will produce a X larger than the grid width, so you need
a single test to see you are outside the row span. Doing the same for both
coordinates allows you to perform the out-of-grid test with just two
comparisons instead of four. This is shorter and more efficient.)

This topic was discussed several times in the D newsgroup, and one conclusion
seems to be that solutions like the C# or C++-Clang ones are not good enough
for D (for performance reasons, and because D programs contain legitimate cases
of unsigned wrap-around, that are not easy to tell apart from the not
legitimate ones, that are the bugs).

So the D solution to this problem seems to be the introduction of new integral
types that generate run-time errors in case of overflow or wrap around (so both
signed and unsigned overflows need to be found). Such two structs should go in
Phobos, to be available to all/most D programs/programmers (just like a future
decimal type).

D structs are able to emulate most of the capabilities of a built-in type.
Currently (dmd 2.063) there are few situations where you can't put a
library-defined struct where a number is expected. So you can't just a complex
numerical function templated on T=int, and replace it with T=SafeInt. Hopefully
in future such small limits will be removed, this is stuff for other
Enhancement Requests.

SafeInt should work on the full range of both signed and unsigned built-in
typed, like uint, long, ushort, wchar, etc. But in some cases you also want a
type that produces an overflow when it's outside a sub-range of the whole range
of a built-in type. Ada has built-in syntax for this:

alias MyMonth = SafeInt!(ubyte, 1, 12);


With the current semantics of D it's hard to create an efficient user-defined
integral typetype. Some of the things a safe integral struct is expected to do:

1) Read the CPU flags, to detect carry and overflows (when not run in CTFE
mode, a __ctfe guard is used);
2) Its member functions must be inlined, to avoid an excessive loss of
performance;
3) The compiler is supposed to perform the typical simplifications it usually
perform on integral values, on the base of the algebraic properties of
integers.

The requirements 1 and 2 are at odd, because in D currently functions that
contain asm (that's used to read the CPU flags).

The point 3 sometimes comes naturally from the point 2, because if the value is
store locally on the stack, and the member function (like a sum) is inlined,
the compiler is probably able to perform those simplifications.

Another way to solve the problem 3 is to introduce annotations like @symmetric,
@associative, but this is probably too much hard to do in D.

A solution to such problems is to introduce safeint and safeuint in the D
language itself. This has the disadvantage of introducing some complexity in
the compiler, and it probably doesn't allow simply to support the
SafeInt!(ubyte,1,12) use case.

So in the discussion threads it was proposed an intermediate solution: to
define the SafeInt in Phobos, but add it a special compiler support, allowing
its member functions to be inlined, and allow its operations to be natively
fast (when not performed a compile-time). Such compile support is probably two
(or few, like uint, int, ulong, long) bare-bones types defined by the compiler,
that SafeInt used internally. This is a solution similar to the one used to
bring SSE operations in D.

So this enhancement request asks for this basic compiler support, to later
allow the creation of efficient SafeInt for Phobos, able to replace as much
transparently as as possible the built-in integral types as int and ulong.

I think the built-in support will not help a lot to support the
SafeInt!(ubyte,1,12) use case, or even the SafeInt!short case. So this is
probably mostly done by the Phobos struct itself.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------