Seems like saturating arithmetic is a thing, apparently with
integers. I can see that for applications that interface with
the real world with limited-range sensors or actuators (no sense
in trying to put more than 20 mA on a 4-20 mA current loop).

And floating point (usually?) does not need it.

What's the best way of encoding this in an ISA? To cover the
range of 8,16,32,64 bit calculations would need two bits. Or,
if somebody has, let's say, a 12-bit sensor, intermediate lengths
might also come in handy to clip results to between -2048..2047.

Or is it just not worth the bother? Maybe people who have
experience with embedded CPUs can say something about this.

On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:
> Seems like saturating arithmetic is a thing, apparently with
> integers. I can see that for applications that interface with
> the real world with limited-range sensors or actuators (no sense
> in trying to put more than 20 mA on a 4-20 mA current loop).
>
> And floating point (usually?) does not need it.
>
> What's the best way of encoding this in an ISA? To cover the
> range of 8,16,32,64 bit calculations would need two bits. Or,
> if somebody has, let's say, a 12-bit sensor, intermediate lengths
> might also come in handy to clip results to between -2048..2047.
>
> Or is it just not worth the bother? Maybe people who have
> experience with embedded CPUs can say something about this.

IIRC, saturating adds & subtracts are used for things like JPEG & MPEG encoding/decoding.
For 12 bit, you could do 16 bit and then have ceiling/floor operations to "clip" the result.

- Tim

On Thursday, November 17, 2022 at 9:36:22 AM UTC-6, timca...@aol.com wrote:
> On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:
> > Seems like saturating arithmetic is a thing, apparently with
> > integers. I can see that for applications that interface with
> > the real world with limited-range sensors or actuators (no sense
> > in trying to put more than 20 mA on a 4-20 mA current loop).
> >
> > And floating point (usually?) does not need it.
> >
> > What's the best way of encoding this in an ISA? To cover the
> > range of 8,16,32,64 bit calculations would need two bits. Or,
> > if somebody has, let's say, a 12-bit sensor, intermediate lengths
> > might also come in handy to clip results to between -2048..2047.
> >
> > Or is it just not worth the bother? Maybe people who have
> > experience with embedded CPUs can say something about this.
<
> IIRC, saturating adds & subtracts are used for things like JPEG & MPEG encoding/decoding.
> For 12 bit, you could do 16 bit and then have ceiling/floor operations to "clip" the result.
<
For ADA: one would want to saturate at particular end-of-range which
may not be power of 2.
Do most of the rest: one would saturate to the size of a container which
may not be a power of 2.
<
If one can avoid integer overflow in the actual calculation, one can
have an extract instruction (or a saturate instruction) that provides
the necessary bounds (operands) and an instruction that does::
<
if( x < lbounds ) r = lbounds;
else if( x > ubounds ) r = ubounds;
else r = x;
>
> - Tim

On 11/17/2022 11:36 AM, MitchAlsup wrote:
> On Thursday, November 17, 2022 at 9:36:22 AM UTC-6, timca...@aol.com wrote:
>> On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:
>>> Seems like saturating arithmetic is a thing, apparently with
>>> integers. I can see that for applications that interface with
>>> the real world with limited-range sensors or actuators (no sense
>>> in trying to put more than 20 mA on a 4-20 mA current loop).
>>>
>>> And floating point (usually?) does not need it.
>>>
>>> What's the best way of encoding this in an ISA? To cover the
>>> range of 8,16,32,64 bit calculations would need two bits. Or,
>>> if somebody has, let's say, a 12-bit sensor, intermediate lengths
>>> might also come in handy to clip results to between -2048..2047.
>>>
>>> Or is it just not worth the bother? Maybe people who have
>>> experience with embedded CPUs can say something about this.
> <
>> IIRC, saturating adds & subtracts are used for things like JPEG & MPEG encoding/decoding.
>> For 12 bit, you could do 16 bit and then have ceiling/floor operations to "clip" the result.
> <
> For ADA: one would want to saturate at particular end-of-range which
> may not be power of 2.
> Do most of the rest: one would saturate to the size of a container which
> may not be a power of 2.
> <
> If one can avoid integer overflow in the actual calculation, one can
> have an extract instruction (or a saturate instruction) that provides
> the necessary bounds (operands) and an instruction that does::
> <
> if( x < lbounds ) r = lbounds;
> else if( x > ubounds ) r = ubounds;
> else r = x;

A few comments.

1. I think that saturating arithmetic is a pretty big thing in DSPs. If
that is so, then perhaps someone who is familiar with the usage patterns
there can chime in.

2. I recall that the Mill will offer saturating arithmetic. Perhaps
Ivan can provide more information.

3. There is a fundamental question of whether to include the saturation
in the arithmetic instructions or as a separate instruction after the
arithmetic instruction. There are arguments on both sides.

4. Your example requires a three operand instruction. This is
frequently overkill, as for example, if the arithmetic operation was an
unsigned add, there is no need to test the lower bounds, and a simple,
two operand MAX instruction would be sufficient.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>On 11/17/2022 11:36 AM, MitchAlsup wrote:
>> On Thursday, November 17, 2022 at 9:36:22 AM UTC-6, timca...@aol.com wrote:
>>> On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:
>>>> Seems like saturating arithmetic is a thing, apparently with
>>>> integers. I can see that for applications that interface with
>>>> the real world with limited-range sensors or actuators (no sense
>>>> in trying to put more than 20 mA on a 4-20 mA current loop).
>>>>
>>>> And floating point (usually?) does not need it.
>>>>
>>>> What's the best way of encoding this in an ISA? To cover the
>>>> range of 8,16,32,64 bit calculations would need two bits. Or,
>>>> if somebody has, let's say, a 12-bit sensor, intermediate lengths
>>>> might also come in handy to clip results to between -2048..2047.
>>>>
>>>> Or is it just not worth the bother? Maybe people who have
>>>> experience with embedded CPUs can say something about this.
>> <
>>> IIRC, saturating adds & subtracts are used for things like JPEG & MPEG encoding/decoding.
>>> For 12 bit, you could do 16 bit and then have ceiling/floor operations to "clip" the result.
>> <
>> For ADA: one would want to saturate at particular end-of-range which
>> may not be power of 2.
>> Do most of the rest: one would saturate to the size of a container which
>> may not be a power of 2.
>> <
>> If one can avoid integer overflow in the actual calculation, one can
>> have an extract instruction (or a saturate instruction) that provides
>> the necessary bounds (operands) and an instruction that does::
>> <
>> if( x < lbounds ) r = lbounds;
>> else if( x > ubounds ) r = ubounds;
>> else r = x;
>
>A few comments.
>
>1. I think that saturating arithmetic is a pretty big thing in DSPs. If
>that is so, then perhaps someone who is familiar with the usage patterns
>there can chime in.

ARMv8 Neon (SIMD) instructions include saturating variants for most
of the arithmetic operations signed and unsigned including addition,
subtraction, multiplication, bit shift and rounding operations.

Timothy McCaffrey <timcaffrey@aol.com> schrieb:
> On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:
>> Seems like saturating arithmetic is a thing, apparently with
>> integers. I can see that for applications that interface with
>> the real world with limited-range sensors or actuators (no sense
>> in trying to put more than 20 mA on a 4-20 mA current loop).
>>
>> And floating point (usually?) does not need it.
>>
>> What's the best way of encoding this in an ISA? To cover the
>> range of 8,16,32,64 bit calculations would need two bits. Or,
>> if somebody has, let's say, a 12-bit sensor, intermediate lengths
>> might also come in handy to clip results to between -2048..2047.
>>
>> Or is it just not worth the bother? Maybe people who have
>> experience with embedded CPUs can say something about this.
>
> IIRC, saturating adds & subtracts are used for things like JPEG & MPEG encoding/decoding.
> For 12 bit, you could do 16 bit and then have ceiling/floor operations to "clip" the result.

I just looked a bit at what different compilers / ISAs did for a
saturating results after a calculation, in two versions:

#define MIN(a,b) ((a)<(b)? (a) : (b))
#define MAX(a,b) ((a)>(b)? (a) : (b))

int saturate(int a)
{ int ret;
ret = MAX(a,-2048);
ret = MIN(ret,2047);
return ret;
}

and

int saturate(int a)
{ int ret;
if (a < -2048)
ret = -2048;
else if (a > 2047)
ret = 2047;
else
ret = a;

return ret;
}

ARM 64/gcc was (for both versions)

ssat r0, #12, r0
bx lr

so somebody must have done their pattern matching homework there.
Other code was a variant of (like ARM 64/clang)

mov w8, #-2048
cmn w0, #2048
csel w8, w0, w8, gt
mov w9, #2047
cmp w8, #2047
csel w0, w8, w9, lt
ret

For My 66000, the versions were actually different. The first
one gave the elegant

maxs r1,#-2048,r1
mins r1,#2047,r1
ret

the second code with a branch:

cmp r2,r1,#-2048
bge r2,.LBB0_1
; %bb.2: ; %return
mov r1,#-2048
ret
..LBB0_1: ; %if.else
mins r1,#2047,r1
ret

This would be another reason for putting in MAX and MIN instrucions
(and teaching the compiler how to use them).

Thomas Koenig <tkoenig@netcologne.de> writes:
>Timothy McCaffrey <timcaffrey@aol.com> schrieb:
>> On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:

>I just looked a bit at what different compilers / ISAs did for a
>saturating results after a calculation, in two versions:
>
>#define MIN(a,b) ((a)<(b)? (a) : (b))
>#define MAX(a,b) ((a)>(b)? (a) : (b))
>
>int saturate(int a)
>{
> int ret;
> ret = MAX(a,-2048);
> ret = MIN(ret,2047);
> return ret;
>}
>
>and
>
>int saturate(int a)
>{
> int ret;
> if (a < -2048)
> ret = -2048;
> else if (a > 2047)
> ret = 2047;
> else
> ret = a;
>
> return ret;
>}
>
>ARM 64/gcc was (for both versions)
>
> ssat r0, #12, r0
> bx lr
>

Those are ARMv7 (A32) instructions. ARMv8 (64-bit) doesn't have an integer
saturation instruction.

On Thursday, November 17, 2022 at 2:20:08 PM UTC-6, Stephen Fuld wrote:
> On 11/17/2022 11:36 AM, MitchAlsup wrote:

> > If one can avoid integer overflow in the actual calculation, one can
> > have an extract instruction (or a saturate instruction) that provides
> > the necessary bounds (operands) and an instruction that does::
> > <
> > if( x < lbounds ) r = lbounds;
> > else if( x > ubounds ) r = ubounds;
> > else r = x;
> A few comments.
>
> 1. I think that saturating arithmetic is a pretty big thing in DSPs. If
> that is so, then perhaps someone who is familiar with the usage patterns
> there can chime in.
<
Many DSPs only have arithmetic containers barely able to hold the
calculation itself, and in this realm, saturation is important. Imagine
8-bit DSP without saturation ?!?
>
> 2. I recall that the Mill will offer saturating arithmetic. Perhaps
> Ivan can provide more information.
<
OpenGL has saturation in integer and in FP.
FP saturates at [+0.0...+1.0]
>
> 3. There is a fundamental question of whether to include the saturation
> in the arithmetic instructions or as a separate instruction after the
> arithmetic instruction. There are arguments on both sides.
>
In the general purpose world, we can't even get people to check for
overflow ?!? what chance does saturation have ???
>
> 4. Your example requires a three operand instruction. This is
> frequently overkill, as for example, if the arithmetic operation was an
> unsigned add, there is no need to test the lower bounds, and a simple,
> two operand MAX instruction would be sufficient.
<
MIN(ubound,MAX(lbound,result))
<
If you prefer.
>
>
>
> --
> - Stephen Fuld
> (e-mail address disguised to prevent spam)

On 11/17/2022 12:20 PM, Stephen Fuld wrote:
> On 11/17/2022 11:36 AM, MitchAlsup wrote:
>> On Thursday, November 17, 2022 at 9:36:22 AM UTC-6, timca...@aol.com
>> wrote:
>>> On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:
>>>> Seems like saturating arithmetic is a thing, apparently with
>>>> integers. I can see that for applications that interface with
>>>> the real world with limited-range sensors or actuators (no sense
>>>> in trying to put more than 20 mA on a 4-20 mA current loop).
>>>>
>>>> And floating point (usually?) does not need it.
>>>>
>>>> What's the best way of encoding this in an ISA? To cover the
>>>> range of 8,16,32,64 bit calculations would need two bits. Or,
>>>> if somebody has, let's say, a 12-bit sensor, intermediate lengths
>>>> might also come in handy to clip results to between -2048..2047.
>>>>
>>>> Or is it just not worth the bother? Maybe people who have
>>>> experience with embedded CPUs can say something about this.
>> <
>>> IIRC, saturating adds & subtracts are used for things like JPEG &
>>> MPEG encoding/decoding.
>>> For 12 bit, you could do 16 bit and then have ceiling/floor
>>> operations to "clip" the result.
>> <
>> For ADA: one would want to saturate at particular end-of-range which
>> may not be power of 2.
>> Do most of the rest: one would saturate to the size of a container which
>> may not be a power of 2.
>> <
>> If one can avoid integer overflow in the actual calculation, one can
>> have an extract instruction (or a saturate instruction) that provides
>> the necessary bounds (operands) and an instruction that does::
>> <
>>            if(         x < lbounds   ) r = lbounds;
>>            else if( x > ubounds ) r = ubounds;
>>            else                              r = x;
>
> A few comments.
>
> 1.    I think that saturating arithmetic is a pretty big thing in DSPs.
> If that is so, then perhaps someone who is familiar with the usage
> patterns there can chime in.
>
> 2.    I recall that the Mill will offer saturating arithmetic.  Perhaps
> Ivan can provide more information.

Every operation that can overflow has saturation as one of the overflow
behaviors (the others are wrap, fault, and double-wide result).

The reason for hardware saturation is not bound checking, it's
intra-expression overflow. If the expression is "a = b +b" then you can
check the condition codes (the groan you hear is Mitch turning over in
his grave) with a conditional branch (plugging up the predictor) or a
special op. If the expression is a = b+c*d-e" then checking gets out of
hand.

> 3.    There is a fundamental question of whether to include the
> saturation in the arithmetic instructions or as a separate instruction
> after the arithmetic instruction.  There are arguments on both sides.

Per-instruction saturation is needed for intra-expression overflow. A
separate op, in addition to per-instruction saturation, is needed to
bound to non-datasize bounds, as needed for Ada and in practice needed
for many DSP algorithms regardless of the language.

> 4.    Your example requires a three operand instruction.  This is
> frequently overkill, as for example, if the arithmetic operation was an
> unsigned add, there is no need to test the lower bounds, and a simple,
> two operand MAX instruction would be sufficient.

Consider adding years to a calendar date constrained to be AD. There is
no year zero.

Fortunately, the great majority of constraints are statically known to
the compiler, so if your design has a convenient way to put constants in
the code stream (ahem - Mitch, Mill) you don't need more reg ports, and
for the rare dynamic cases you can use two ops, one for lower and one
for upper bound.

On Thursday, November 17, 2022 at 8:43:45 PM UTC-6, Ivan Godard wrote:
> On 11/17/2022 12:20 PM, Stephen Fuld wrote:
> > On 11/17/2022 11:36 AM, MitchAlsup wrote:
> >> On Thursday, November 17, 2022 at 9:36:22 AM UTC-6, timca...@aol.com
> >> wrote:
> >>> On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:
> >>>> Seems like saturating arithmetic is a thing, apparently with
> >>>> integers. I can see that for applications that interface with
> >>>> the real world with limited-range sensors or actuators (no sense
> >>>> in trying to put more than 20 mA on a 4-20 mA current loop).
> >>>>
> >>>> And floating point (usually?) does not need it.
> >>>>
> >>>> What's the best way of encoding this in an ISA? To cover the
> >>>> range of 8,16,32,64 bit calculations would need two bits. Or,
> >>>> if somebody has, let's say, a 12-bit sensor, intermediate lengths
> >>>> might also come in handy to clip results to between -2048..2047.
> >>>>
> >>>> Or is it just not worth the bother? Maybe people who have
> >>>> experience with embedded CPUs can say something about this.
> >> <
> >>> IIRC, saturating adds & subtracts are used for things like JPEG &
> >>> MPEG encoding/decoding.
> >>> For 12 bit, you could do 16 bit and then have ceiling/floor
> >>> operations to "clip" the result.
> >> <
> >> For ADA: one would want to saturate at particular end-of-range which
> >> may not be power of 2.
> >> Do most of the rest: one would saturate to the size of a container which
> >> may not be a power of 2.
> >> <
> >> If one can avoid integer overflow in the actual calculation, one can
> >> have an extract instruction (or a saturate instruction) that provides
> >> the necessary bounds (operands) and an instruction that does::
> >> <
> >> if( x < lbounds ) r = lbounds;
> >> else if( x > ubounds ) r = ubounds;
> >> else r = x;
> >
> > A few comments.
> >
> > 1. I think that saturating arithmetic is a pretty big thing in DSPs.
> > If that is so, then perhaps someone who is familiar with the usage
> > patterns there can chime in.
> >
> > 2. I recall that the Mill will offer saturating arithmetic. Perhaps
> > Ivan can provide more information.
> Every operation that can overflow has saturation as one of the overflow
> behaviors (the others are wrap, fault, and double-wide result).
>
> The reason for hardware saturation is not bound checking, it's
> intra-expression overflow. If the expression is "a = b +b" then you can
> check the condition codes (the groan you hear is Mitch turning over in
> his grave)
<
The contrapositive is much more likely. I an neither in my grave, nor
turning over.
<
> with a conditional branch (plugging up the predictor) or a
> special op. If the expression is a = b+c*d-e" then checking gets out of
> hand.
<
If you do it with predication you don't <necessarily>plug up[ the branch
predictor.
<
Which leads to the question: does one use the same predictor for
branches and for predication ??? Hmmmmm.........
<
> > 3. There is a fundamental question of whether to include the
> > saturation in the arithmetic instructions or as a separate instruction
> > after the arithmetic instruction. There are arguments on both sides.
> Per-instruction saturation is needed for intra-expression overflow. A
> separate op, in addition to per-instruction saturation, is needed to
> bound to non-datasize bounds, as needed for Ada and in practice needed
> for many DSP algorithms regardless of the language.
> > 4. Your example requires a three operand instruction. This is
> > frequently overkill, as for example, if the arithmetic operation was an
> > unsigned add, there is no need to test the lower bounds, and a simple,
> > two operand MAX instruction would be sufficient.
> Consider adding years to a calendar date constrained to be AD. There is
> no year zero.
<
There are all sorts of maladies in the calander no zero is but a sampling;
there are no leap year in years divisible by 100 except those divisible by 400;
Thursday 4 October 1582 was followed by Friday 15 October 1582, and so
on.
>
> Fortunately, the great majority of constraints are statically known to
> the compiler, so if your design has a convenient way to put constants in
> the code stream (ahem - Mitch, Mill) you don't need more reg ports, and
> for the rare dynamic cases you can use two ops, one for lower and one
> for upper bound.
<
As I am fond of stating: There is no cheaper way to deliver an operand to
a calculation unit that as a constant.

On 11/17/2022 6:53 PM, MitchAlsup wrote:
> On Thursday, November 17, 2022 at 8:43:45 PM UTC-6, Ivan Godard wrote:
>> On 11/17/2022 12:20 PM, Stephen Fuld wrote:
>>> On 11/17/2022 11:36 AM, MitchAlsup wrote:
>>>> On Thursday, November 17, 2022 at 9:36:22 AM UTC-6, timca...@aol.com
>>>> wrote:
>>>>> On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:
>>>>>> Seems like saturating arithmetic is a thing, apparently with
>>>>>> integers. I can see that for applications that interface with
>>>>>> the real world with limited-range sensors or actuators (no sense
>>>>>> in trying to put more than 20 mA on a 4-20 mA current loop).
>>>>>>
>>>>>> And floating point (usually?) does not need it.
>>>>>>
>>>>>> What's the best way of encoding this in an ISA? To cover the
>>>>>> range of 8,16,32,64 bit calculations would need two bits. Or,
>>>>>> if somebody has, let's say, a 12-bit sensor, intermediate lengths
>>>>>> might also come in handy to clip results to between -2048..2047.
>>>>>>
>>>>>> Or is it just not worth the bother? Maybe people who have
>>>>>> experience with embedded CPUs can say something about this.
>>>> <
>>>>> IIRC, saturating adds & subtracts are used for things like JPEG &
>>>>> MPEG encoding/decoding.
>>>>> For 12 bit, you could do 16 bit and then have ceiling/floor
>>>>> operations to "clip" the result.
>>>> <
>>>> For ADA: one would want to saturate at particular end-of-range which
>>>> may not be power of 2.
>>>> Do most of the rest: one would saturate to the size of a container which
>>>> may not be a power of 2.
>>>> <
>>>> If one can avoid integer overflow in the actual calculation, one can
>>>> have an extract instruction (or a saturate instruction) that provides
>>>> the necessary bounds (operands) and an instruction that does::
>>>> <
>>>> if( x < lbounds ) r = lbounds;
>>>> else if( x > ubounds ) r = ubounds;
>>>> else r = x;
>>>
>>> A few comments.
>>>
>>> 1. I think that saturating arithmetic is a pretty big thing in DSPs.
>>> If that is so, then perhaps someone who is familiar with the usage
>>> patterns there can chime in.
>>>
>>> 2. I recall that the Mill will offer saturating arithmetic. Perhaps
>>> Ivan can provide more information.
>> Every operation that can overflow has saturation as one of the overflow
>> behaviors (the others are wrap, fault, and double-wide result).
>>
>> The reason for hardware saturation is not bound checking, it's
>> intra-expression overflow. If the expression is "a = b +b" then you can
>> check the condition codes (the groan you hear is Mitch turning over in
>> his grave)
> <
> The contrapositive is much more likely. I an neither in my grave, nor
> turning over.
> <
>> with a conditional branch (plugging up the predictor) or a
>> special op. If the expression is a = b+c*d-e" then checking gets out of
>> hand.
> <
> If you do it with predication you don't <necessarily>plug up[ the branch
> predictor.
> <
> Which leads to the question: does one use the same predictor for
> branches and for predication ??? Hmmmmm.........

Why predict predication? Just be wide enough that you don't care that
some are nooped.

Scott Lurndal <scott@slp53.sl.home> schrieb:
> Thomas Koenig <tkoenig@netcologne.de> writes:
[...]
>>ARM 64/gcc was (for both versions)
>>
>> ssat r0, #12, r0
>> bx lr
>>
>
> Those are ARMv7 (A32) instructions. ARMv8 (64-bit) doesn't have an integer
> saturation instruction.

Correct, I selected the wrong compiler on godbolt.

On 17/11/2022 07:25, Thomas Koenig wrote:
> Seems like saturating arithmetic is a thing, apparently with
> integers. I can see that for applications that interface with
> the real world with limited-range sensors or actuators (no sense
> in trying to put more than 20 mA on a 4-20 mA current loop).
>
> And floating point (usually?) does not need it.
>
> What's the best way of encoding this in an ISA? To cover the
> range of 8,16,32,64 bit calculations would need two bits. Or,
> if somebody has, let's say, a 12-bit sensor, intermediate lengths
> might also come in handy to clip results to between -2048..2047.
>
> Or is it just not worth the bother? Maybe people who have
> experience with embedded CPUs can say something about this.

As you say, it is found in some embedded systems (and that includes
floating point saturation as well as integer saturation, though integer
saturation is more important). It is particularly popular in DSPs and
DSP algorithms.

You can google for the saturating arithmetic functions in ARM Cortex-M
processors. They are considered part of the "DSP functions", along with
multiply-accumulate instructions and the like. They are used in some
code, usually using intrinsics or even inline assembly to get the peak
efficiency.

There is also a somewhat outdated proposed C extension, "Extensions to
support embedded processors"
<https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf>. The whole
TR is, IMHO, a flop, and has not really done much. It included support
for saturated types, and there is limited support for them in gcc
<https://gcc.gnu.org/onlinedocs/gcc/Fixed-Point.html>. However, they
are pretty useless in practice - if you need to use saturated types, you
need to know the exact size - types like "_Sat unsigned long _Fract" are
pointless.

I believe Ada has saturating types as part of the language, making them
a lot more convenient than in C - maybe an expert in that language can
say how useful they are.

On Friday, November 18, 2022 at 4:43:45 AM UTC+2, Ivan Godard wrote:
> On 11/17/2022 12:20 PM, Stephen Fuld wrote:
> > On 11/17/2022 11:36 AM, MitchAlsup wrote:
> >> On Thursday, November 17, 2022 at 9:36:22 AM UTC-6, timca...@aol.com
> >> wrote:
> >>> On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:
> >>>> Seems like saturating arithmetic is a thing, apparently with
> >>>> integers. I can see that for applications that interface with
> >>>> the real world with limited-range sensors or actuators (no sense
> >>>> in trying to put more than 20 mA on a 4-20 mA current loop).
> >>>>
> >>>> And floating point (usually?) does not need it.
> >>>>
> >>>> What's the best way of encoding this in an ISA? To cover the
> >>>> range of 8,16,32,64 bit calculations would need two bits. Or,
> >>>> if somebody has, let's say, a 12-bit sensor, intermediate lengths
> >>>> might also come in handy to clip results to between -2048..2047.
> >>>>
> >>>> Or is it just not worth the bother? Maybe people who have
> >>>> experience with embedded CPUs can say something about this.
> >> <
> >>> IIRC, saturating adds & subtracts are used for things like JPEG &
> >>> MPEG encoding/decoding.
> >>> For 12 bit, you could do 16 bit and then have ceiling/floor
> >>> operations to "clip" the result.
> >> <
> >> For ADA: one would want to saturate at particular end-of-range which
> >> may not be power of 2.
> >> Do most of the rest: one would saturate to the size of a container which
> >> may not be a power of 2.
> >> <
> >> If one can avoid integer overflow in the actual calculation, one can
> >> have an extract instruction (or a saturate instruction) that provides
> >> the necessary bounds (operands) and an instruction that does::
> >> <
> >> if( x < lbounds ) r = lbounds;
> >> else if( x > ubounds ) r = ubounds;
> >> else r = x;
> >
> > A few comments.
> >
> > 1. I think that saturating arithmetic is a pretty big thing in DSPs.
> > If that is so, then perhaps someone who is familiar with the usage
> > patterns there can chime in.
> >
> > 2. I recall that the Mill will offer saturating arithmetic. Perhaps
> > Ivan can provide more information.
> Every operation that can overflow has saturation as one of the overflow
> behaviors (the others are wrap, fault, and double-wide result).
>
> The reason for hardware saturation is not bound checking, it's
> intra-expression overflow. If the expression is "a = b +b" then you can
> check the condition codes (the groan you hear is Mitch turning over in
> his grave) with a conditional branch (plugging up the predictor) or a
> special op. If the expression is a = b+c*d-e" then checking gets out of
> hand.

Sound like an argument for sticky overflow flag rather than saturation.

> > 3. There is a fundamental question of whether to include the
> > saturation in the arithmetic instructions or as a separate instruction
> > after the arithmetic instruction. There are arguments on both sides.
> Per-instruction saturation is needed for intra-expression overflow. A
> separate op, in addition to per-instruction saturation, is needed to
> bound to non-datasize bounds, as needed for Ada

Where is it needed in Ada?
According to my (incomplete, but not too incomplete) knowledge,
there are know situation where saturation arithmetic could help
in implementing compilers for Ada-83 or 95.
Is different in newer standards or am I missing something about
old ones?

> and in practice needed
> for many DSP algorithms regardless of the language.

'many' is a too strong word. 'occasionally' is closer to reality.
On traditional DSPs most often you want to saturate accumulator,
which is most typically 40-bit wide (sometimes 36 bit) into signed
32-bit lower part of the same accumulator.
40->16 and 32->16 also happens, but relatively rarer and not always
justifies separate instruction.
On the other hand, 32->16 saturation combined with packing is very
common on SIMD processors, both DSPs and general-purpose.
Also, 16->8 saturation with packing is commonly provided, but
I am not sure that it is still commonly used. The sorts of processing
that utilized 16->8 either became trivial in multi-GHz era (still image
processing) or migrated to specialized engines.

> > 4. Your example requires a three operand instruction. This is
> > frequently overkill, as for example, if the arithmetic operation was an
> > unsigned add, there is no need to test the lower bounds, and a simple,
> > two operand MAX instruction would be sufficient.
> Consider adding years to a calendar date constrained to be AD. There is
> no year zero.
>
> Fortunately, the great majority of constraints are statically known to
> the compiler, so if your design has a convenient way to put constants in
> the code stream (ahem - Mitch, Mill) you don't need more reg ports, and
> for the rare dynamic cases you can use two ops, one for lower and one
> for upper bound.

MitchAlsup wrote:
> On Thursday, November 17, 2022 at 9:36:22 AM UTC-6, timca...@aol.com wrote:
>> On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:
>>> Seems like saturating arithmetic is a thing, apparently with
>>> integers. I can see that for applications that interface with
>>> the real world with limited-range sensors or actuators (no sense
>>> in trying to put more than 20 mA on a 4-20 mA current loop).
>>>
>>> And floating point (usually?) does not need it.
>>>
>>> What's the best way of encoding this in an ISA? To cover the
>>> range of 8,16,32,64 bit calculations would need two bits. Or,
>>> if somebody has, let's say, a 12-bit sensor, intermediate lengths
>>> might also come in handy to clip results to between -2048..2047.
>>>
>>> Or is it just not worth the bother? Maybe people who have
>>> experience with embedded CPUs can say something about this.
> <
>> IIRC, saturating adds & subtracts are used for things like JPEG & MPEG encoding/decoding.
>> For 12 bit, you could do 16 bit and then have ceiling/floor operations to "clip" the result.
> <
> For ADA: one would want to saturate at particular end-of-range which
> may not be power of 2.
> Do most of the rest: one would saturate to the size of a container which
> may not be a power of 2.
> <
> If one can avoid integer overflow in the actual calculation, one can
> have an extract instruction (or a saturate instruction) that provides
> the necessary bounds (operands) and an instruction that does::
> <
> if( x < lbounds ) r = lbounds;
> else if( x > ubounds ) r = ubounds;
> else r = x;

The best I've been able to come up with, in the time before CMOV, was to
subtract the lower bound, propagate any carry to save it, then compare
the result with the range: Any carry from that comparison would indicate
the need for saturation, with the type determined by the initial
carry/non-carry.

It only works when you have least one spare bit though, i.e. the input
range needs to allow the subtraction to never cause an overflow.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Thomas Koenig wrote:
> Timothy McCaffrey <timcaffrey@aol.com> schrieb:
>> On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:
>>> Seems like saturating arithmetic is a thing, apparently with
>>> integers. I can see that for applications that interface with
>>> the real world with limited-range sensors or actuators (no sense
>>> in trying to put more than 20 mA on a 4-20 mA current loop).
>>>
>>> And floating point (usually?) does not need it.
>>>
>>> What's the best way of encoding this in an ISA? To cover the
>>> range of 8,16,32,64 bit calculations would need two bits. Or,
>>> if somebody has, let's say, a 12-bit sensor, intermediate lengths
>>> might also come in handy to clip results to between -2048..2047.
>>>
>>> Or is it just not worth the bother? Maybe people who have
>>> experience with embedded CPUs can say something about this.
>>
>> IIRC, saturating adds & subtracts are used for things like JPEG & MPEG encoding/decoding.
>> For 12 bit, you could do 16 bit and then have ceiling/floor operations to "clip" the result.
>
> I just looked a bit at what different compilers / ISAs did for a
> saturating results after a calculation, in two versions:
>
> #define MIN(a,b) ((a)<(b)? (a) : (b))
> #define MAX(a,b) ((a)>(b)? (a) : (b))
>
> int saturate(int a)
> {
> int ret;
> ret = MAX(a,-2048);
> ret = MIN(ret,2047);
> return ret;
> }
>
> and
>
> int saturate(int a)
> {
> int ret;
> if (a < -2048)
> ret = -2048;
> else if (a > 2047)
> ret = 2047;
> else
> ret = a;
>
> return ret;
> }
>
> ARM 64/gcc was (for both versions)
>
> ssat r0, #12, r0
> bx lr
>
> so somebody must have done their pattern matching homework there.
> Other code was a variant of (like ARM 64/clang)
>
> mov w8, #-2048
> cmn w0, #2048
> csel w8, w0, w8, gt
> mov w9, #2047
> cmp w8, #2047
> csel w0, w8, w9, lt
> ret
>
> For My 66000, the versions were actually different. The first
> one gave the elegant
>
> maxs r1,#-2048,r1
> mins r1,#2047,r1
> ret
>
> the second code with a branch:
>
> cmp r2,r1,#-2048
> bge r2,.LBB0_1
> ; %bb.2: ; %return
> mov r1,#-2048
> ret
> .LBB0_1: ; %if.else
> mins r1,#2047,r1
> ret
>
> This would be another reason for putting in MAX and MIN instrucions
> (and teaching the compiler how to use them).

Yeah!

Doing saturation at a binary power of two is of course easier than to
handle arbitrary limits, where upper, lower and range (upper-lower+1)
are all non-power of two.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

MitchAlsup wrote:
> On Thursday, November 17, 2022 at 8:43:45 PM UTC-6, Ivan Godard wrote:
>> On 11/17/2022 12:20 PM, Stephen Fuld wrote:
>>> On 11/17/2022 11:36 AM, MitchAlsup wrote:
>>>> On Thursday, November 17, 2022 at 9:36:22 AM UTC-6, timca...@aol.com
>>>> wrote:
>>>>> On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:
>>>>>> Seems like saturating arithmetic is a thing, apparently with
>>>>>> integers. I can see that for applications that interface with
>>>>>> the real world with limited-range sensors or actuators (no sense
>>>>>> in trying to put more than 20 mA on a 4-20 mA current loop).
>>>>>>
>>>>>> And floating point (usually?) does not need it.
>>>>>>
>>>>>> What's the best way of encoding this in an ISA? To cover the
>>>>>> range of 8,16,32,64 bit calculations would need two bits. Or,
>>>>>> if somebody has, let's say, a 12-bit sensor, intermediate lengths
>>>>>> might also come in handy to clip results to between -2048..2047.
>>>>>>
>>>>>> Or is it just not worth the bother? Maybe people who have
>>>>>> experience with embedded CPUs can say something about this.
>>>> <
>>>>> IIRC, saturating adds & subtracts are used for things like JPEG &
>>>>> MPEG encoding/decoding.
>>>>> For 12 bit, you could do 16 bit and then have ceiling/floor
>>>>> operations to "clip" the result.
>>>> <
>>>> For ADA: one would want to saturate at particular end-of-range which
>>>> may not be power of 2.
>>>> Do most of the rest: one would saturate to the size of a container which
>>>> may not be a power of 2.
>>>> <
>>>> If one can avoid integer overflow in the actual calculation, one can
>>>> have an extract instruction (or a saturate instruction) that provides
>>>> the necessary bounds (operands) and an instruction that does::
>>>> <
>>>> if( x < lbounds ) r = lbounds;
>>>> else if( x > ubounds ) r = ubounds;
>>>> else r = x;
>>>
>>> A few comments.
>>>
>>> 1. I think that saturating arithmetic is a pretty big thing in DSPs.
>>> If that is so, then perhaps someone who is familiar with the usage
>>> patterns there can chime in.
>>>
>>> 2. I recall that the Mill will offer saturating arithmetic. Perhaps
>>> Ivan can provide more information.
>> Every operation that can overflow has saturation as one of the overflow
>> behaviors (the others are wrap, fault, and double-wide result).
>>
>> The reason for hardware saturation is not bound checking, it's
>> intra-expression overflow. If the expression is "a = b +b" then you can
>> check the condition codes (the groan you hear is Mitch turning over in
>> his grave)
> <
> The contrapositive is much more likely. I an neither in my grave, nor
> turning over.
> <
>> with a conditional branch (plugging up the predictor) or a
>> special op. If the expression is a = b+c*d-e" then checking gets out of
>> hand.
> <
> If you do it with predication you don't <necessarily>plug up[ the branch
> predictor.
> <
> Which leads to the question: does one use the same predictor for
> branches and for predication ??? Hmmmmm.........
> <
>>> 3. There is a fundamental question of whether to include the
>>> saturation in the arithmetic instructions or as a separate instruction
>>> after the arithmetic instruction. There are arguments on both sides.
>> Per-instruction saturation is needed for intra-expression overflow. A
>> separate op, in addition to per-instruction saturation, is needed to
>> bound to non-datasize bounds, as needed for Ada and in practice needed
>> for many DSP algorithms regardless of the language.
>>> 4. Your example requires a three operand instruction. This is
>>> frequently overkill, as for example, if the arithmetic operation was an
>>> unsigned add, there is no need to test the lower bounds, and a simple,
>>> two operand MAX instruction would be sufficient.
>> Consider adding years to a calendar date constrained to be AD. There is
>> no year zero.
> <
> There are all sorts of maladies in the calander no zero is but a sampling;
> there are no leap year in years divisible by 100 except those divisible by 400;
> Thursday 4 October 1582 was followed by Friday 15 October 1582, and so
> on.

Much worse: The jumps from Julian to Gregorian leap year handling
happened over a long time range, so various countries did it much later
than others.

In my own code I internally use 1600-03-01 as day zero and then pretend
negative day numbers are valid.

I'm still proud of the algorithm I came up with ~30 years ago which
converts a day number into year-month-day in less time than a single DIV
opcode: The textbook algorithms had a bunch of those div/mod operations.

Easter is similar, but I haven't bothered trying to make that one really
fast.
>>
>> Fortunately, the great majority of constraints are statically known to
>> the compiler, so if your design has a convenient way to put constants in
>> the code stream (ahem - Mitch, Mill) you don't need more reg ports, and
>> for the rare dynamic cases you can use two ops, one for lower and one
>> for upper bound.
> <
> As I am fond of stating: There is no cheaper way to deliver an operand to
> a calculation unit that as a constant.

Amen!

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On Thursday, November 17, 2022 at 9:01:32 PM UTC-6, Ivan Godard wrote:
> On 11/17/2022 6:53 PM, MitchAlsup wrote:
> > On Thursday, November 17, 2022 at 8:43:45 PM UTC-6, Ivan Godard wrote:
> >> On 11/17/2022 12:20 PM, Stephen Fuld wrote:
> >>> On 11/17/2022 11:36 AM, MitchAlsup wrote:
> >>>> On Thursday, November 17, 2022 at 9:36:22 AM UTC-6, timca...@aol.com
> >>>> wrote:
> >>>>> On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:
> >>>>>> Seems like saturating arithmetic is a thing, apparently with
> >>>>>> integers. I can see that for applications that interface with
> >>>>>> the real world with limited-range sensors or actuators (no sense
> >>>>>> in trying to put more than 20 mA on a 4-20 mA current loop).
> >>>>>>
> >>>>>> And floating point (usually?) does not need it.
> >>>>>>
> >>>>>> What's the best way of encoding this in an ISA? To cover the
> >>>>>> range of 8,16,32,64 bit calculations would need two bits. Or,
> >>>>>> if somebody has, let's say, a 12-bit sensor, intermediate lengths
> >>>>>> might also come in handy to clip results to between -2048..2047.
> >>>>>>
> >>>>>> Or is it just not worth the bother? Maybe people who have
> >>>>>> experience with embedded CPUs can say something about this.
> >>>> <
> >>>>> IIRC, saturating adds & subtracts are used for things like JPEG &
> >>>>> MPEG encoding/decoding.
> >>>>> For 12 bit, you could do 16 bit and then have ceiling/floor
> >>>>> operations to "clip" the result.
> >>>> <
> >>>> For ADA: one would want to saturate at particular end-of-range which
> >>>> may not be power of 2.
> >>>> Do most of the rest: one would saturate to the size of a container which
> >>>> may not be a power of 2.
> >>>> <
> >>>> If one can avoid integer overflow in the actual calculation, one can
> >>>> have an extract instruction (or a saturate instruction) that provides
> >>>> the necessary bounds (operands) and an instruction that does::
> >>>> <
> >>>> if( x < lbounds ) r = lbounds;
> >>>> else if( x > ubounds ) r = ubounds;
> >>>> else r = x;
> >>>
> >>> A few comments.
> >>>
> >>> 1. I think that saturating arithmetic is a pretty big thing in DSPs.
> >>> If that is so, then perhaps someone who is familiar with the usage
> >>> patterns there can chime in.
> >>>
> >>> 2. I recall that the Mill will offer saturating arithmetic. Perhaps
> >>> Ivan can provide more information.
> >> Every operation that can overflow has saturation as one of the overflow
> >> behaviors (the others are wrap, fault, and double-wide result).
> >>
> >> The reason for hardware saturation is not bound checking, it's
> >> intra-expression overflow. If the expression is "a = b +b" then you can
> >> check the condition codes (the groan you hear is Mitch turning over in
> >> his grave)
> > <
> > The contrapositive is much more likely. I an neither in my grave, nor
> > turning over.
> > <
> >> with a conditional branch (plugging up the predictor) or a
> >> special op. If the expression is a = b+c*d-e" then checking gets out of
> >> hand.
> > <
> > If you do it with predication you don't <necessarily>plug up[ the branch
> > predictor.
> > <
> > Which leads to the question: does one use the same predictor for
> > branches and for predication ??? Hmmmmm.........
<
> Why predict predication? Just be wide enough that you don't care that
> some are nooped.
<
I just wanted to stir the pot and illustrate why using branches as your
only means to control which instructions execute is very sub-optimal.

On Friday, November 18, 2022 at 3:54:22 AM UTC-6, David Brown wrote:
> On 17/11/2022 07:25, Thomas Koenig wrote:
> > Seems like saturating arithmetic is a thing, apparently with
> > integers. I can see that for applications that interface with
> > the real world with limited-range sensors or actuators (no sense
> > in trying to put more than 20 mA on a 4-20 mA current loop).
> >
> > And floating point (usually?) does not need it.
> >
> > What's the best way of encoding this in an ISA? To cover the
> > range of 8,16,32,64 bit calculations would need two bits. Or,
> > if somebody has, let's say, a 12-bit sensor, intermediate lengths
> > might also come in handy to clip results to between -2048..2047.
> >
> > Or is it just not worth the bother? Maybe people who have
> > experience with embedded CPUs can say something about this.
> As you say, it is found in some embedded systems (and that includes
> floating point saturation as well as integer saturation, though integer
> saturation is more important). It is particularly popular in DSPs and
> DSP algorithms.
>
> You can google for the saturating arithmetic functions in ARM Cortex-M
> processors. They are considered part of the "DSP functions", along with
> multiply-accumulate instructions and the like. They are used in some
> code, usually using intrinsics or even inline assembly to get the peak
> efficiency.
>
> There is also a somewhat outdated proposed C extension, "Extensions to
> support embedded processors"
> <https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf>. The whole
> TR is, IMHO, a flop, and has not really done much. It included support
> for saturated types, and there is limited support for them in gcc
> <https://gcc.gnu.org/onlinedocs/gcc/Fixed-Point.html>. However, they
> are pretty useless in practice - if you need to use saturated types, you
> need to know the exact size - types like "_Sat unsigned long _Fract" are
> pointless.
>
>
> I believe Ada has saturating types as part of the language, making them
> a lot more convenient than in C - maybe an expert in that language can
> say how useful they are.
<
Yes, but ADA saturates to the range of the variable, not its container size.
{Which was my point above.}

On Thursday, November 17, 2022 at 9:01:32 PM UTC-6, Ivan Godard wrote:
> On 11/17/2022 6:53 PM, MitchAlsup wrote:
> > On Thursday, November 17, 2022 at 8:43:45 PM UTC-6, Ivan Godard wrote:
> >> On 11/17/2022 12:20 PM, Stephen Fuld wrote:
> >>> On 11/17/2022 11:36 AM, MitchAlsup wrote:
> >>>> On Thursday, November 17, 2022 at 9:36:22 AM UTC-6, timca...@aol.com
> >>>> wrote:
> >>>>> On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:
> >>>>>> Seems like saturating arithmetic is a thing, apparently with
> >>>>>> integers. I can see that for applications that interface with
> >>>>>> the real world with limited-range sensors or actuators (no sense
> >>>>>> in trying to put more than 20 mA on a 4-20 mA current loop).
> >>>>>>
> >>>>>> And floating point (usually?) does not need it.
> >>>>>>
> >>>>>> What's the best way of encoding this in an ISA? To cover the
> >>>>>> range of 8,16,32,64 bit calculations would need two bits. Or,
> >>>>>> if somebody has, let's say, a 12-bit sensor, intermediate lengths
> >>>>>> might also come in handy to clip results to between -2048..2047.
> >>>>>>
> >>>>>> Or is it just not worth the bother? Maybe people who have
> >>>>>> experience with embedded CPUs can say something about this.
> >>>> <
> >>>>> IIRC, saturating adds & subtracts are used for things like JPEG &
> >>>>> MPEG encoding/decoding.
> >>>>> For 12 bit, you could do 16 bit and then have ceiling/floor
> >>>>> operations to "clip" the result.
> >>>> <
> >>>> For ADA: one would want to saturate at particular end-of-range which
> >>>> may not be power of 2.
> >>>> Do most of the rest: one would saturate to the size of a container which
> >>>> may not be a power of 2.
> >>>> <
> >>>> If one can avoid integer overflow in the actual calculation, one can
> >>>> have an extract instruction (or a saturate instruction) that provides
> >>>> the necessary bounds (operands) and an instruction that does::
> >>>> <
> >>>> if( x < lbounds ) r = lbounds;
> >>>> else if( x > ubounds ) r = ubounds;
> >>>> else r = x;
> >>>
> >>> A few comments.
> >>>
> >>> 1. I think that saturating arithmetic is a pretty big thing in DSPs.
> >>> If that is so, then perhaps someone who is familiar with the usage
> >>> patterns there can chime in.
> >>>
> >>> 2. I recall that the Mill will offer saturating arithmetic. Perhaps
> >>> Ivan can provide more information.
> >> Every operation that can overflow has saturation as one of the overflow
> >> behaviors (the others are wrap, fault, and double-wide result).
> >>
> >> The reason for hardware saturation is not bound checking, it's
> >> intra-expression overflow. If the expression is "a = b +b" then you can
> >> check the condition codes (the groan you hear is Mitch turning over in
> >> his grave)
> > <
> > The contrapositive is much more likely. I an neither in my grave, nor
> > turning over.
> > <
> >> with a conditional branch (plugging up the predictor) or a
> >> special op. If the expression is a = b+c*d-e" then checking gets out of
> >> hand.
> > <
> > If you do it with predication you don't <necessarily>plug up[ the branch
> > predictor.
> > <
> > Which leads to the question: does one use the same predictor for
> > branches and for predication ??? Hmmmmm.........
<
> Why predict predication? Just be wide enough that you don't care that
> some are nooped.
<
My compiler uses predication indiscriminately--it predicates anything
and everything that fits under an 8 instruction shadow--without thinking
about whether the control flow is predictable or not.
<
But the execution model does not use the predictor associated with
branches either.
<
The thought train is that one sues predication when the join point of
flow control will already have been fetched by the time the flow control
becomes manifest. And for the vast majority of predications, the join
point has already arrived by the time the PRED instruction is ready to
execute. Thus, there is no reason to alter the fetch point, and it is
easier to skip instructions.

On 2022-11-18 11:54, David Brown wrote:

> I believe Ada has saturating types as part of the language,

Nope (or not yet). Ada provides range-constrained types (integer and
floating), and wrap-around types (unsigned integer only), but not
saturating types. Exceeding a range constraint raises an exception.

Of course one can program saturating types, and overload the ordinary
operators, as in many other languages.

> making them a lot more convenient than in C - maybe an expert in that
> language can say how useful they are.

I've never missed saturating types in my Ada programs. Saturation is
typically needed for commands to actuators, or at a few other points in
servo-control loops, but the upper and lower bounds are seldom powers of
two, and I don't see why one would want saturation on all operators --
more often, only the final result of a computation needs saturation.

On 2022-11-18 15:08, Michael S wrote:
> On Friday, November 18, 2022 at 4:43:45 AM UTC+2, Ivan Godard wrote
[snip]

>> Per-instruction saturation is needed for intra-expression overflow.
>> A separate op, in addition to per-instruction saturation, is needed
>> to bound to non-datasize bounds, as needed for Ada
>
> Where is it needed in Ada? According to my (incomplete, but not too
> incomplete) knowledge, there are know situation where saturation
> arithmetic could help in implementing compilers for Ada-83 or 95. Is
> different in newer standards or am I missing something about old
> ones?

I agree that saturating arithmetic is mostly not useful for implementing
Ada semantics. The only case I can think of, where it might be used, is
to implement a case statement with an "others" clause, for example:

type Count is range 1 .. 9;
C1, C2 : Count;
...
case C1 + C2 is
when 1 => ...;
when 2 => ...;
when 3 => ...;
when others => ...;
end case;

If the compiler decides to implement this 4-branch statement with a jump
table indexed from 0 to 3, it could perform the addition C1+C2 with
saturation to that range, thus routing all values except 1, 2, 3 to the
"others" branch. Of course any language with a similar "others" or
"default" branch could do that too.

On 2022-11-18 16:53, MitchAlsup wrote:
> On Friday, November 18, 2022 at 3:54:22 AM UTC-6, David Brown wrote:

[...]

>> I believe Ada has saturating types as part of the language, making them
>> a lot more convenient than in C - maybe an expert in that language can
>> say how useful they are.
> <
> Yes, but ADA saturates to the range of the variable, not its container size.
> {Which was my point above.}

As I wrote in an earlier reply to David Brown, Ada does not provide
saturating arithmetic, neither to natural power-of-two sizes nor to
programmer-defined ranges.

However, instructions that check a value against a range would be useful
in Ada code. The range would sometimes be static (compile-time constant)
but also sometimes dynamic, for example when indexing an array that is a
parameter to a routine and of a type that has an unconstrained index range.

MitchAlsup wrote:
> On Thursday, November 17, 2022 at 8:43:45 PM UTC-6, Ivan Godard wrote:
> <
>> with a conditional branch (plugging up the predictor) or a
>> special op. If the expression is a = b+c*d-e" then checking gets out of
>> hand.
> <
> If you do it with predication you don't <necessarily>plug up[ the branch
> predictor.
> <
> Which leads to the question: does one use the same predictor for
> branches and for predication ??? Hmmmmm.........

There are a bunch of papers from back around Itanium days on
predicate prediction. (I suspect some changed the term "predication"
to "guarded execution" because "predicate prediction" winds up with too
many pred's in sentences, plus one might spit in peoples faces a lot.)

It seems that guarded execution (predication) can both positively and
negatively impact branch prediction by skewing the stats that BP sees.
This led some to propose GE and combined GE+BP predictors.

On 11/18/2022 7:05 AM, MitchAlsup wrote:
> On Thursday, November 17, 2022 at 9:01:32 PM UTC-6, Ivan Godard wrote:
>> On 11/17/2022 6:53 PM, MitchAlsup wrote:
>>> On Thursday, November 17, 2022 at 8:43:45 PM UTC-6, Ivan Godard wrote:
>>>> On 11/17/2022 12:20 PM, Stephen Fuld wrote:
>>>>> On 11/17/2022 11:36 AM, MitchAlsup wrote:
>>>>>> On Thursday, November 17, 2022 at 9:36:22 AM UTC-6, timca...@aol.com
>>>>>> wrote:
>>>>>>> On Thursday, November 17, 2022 at 1:25:42 AM UTC-5, Thomas Koenig wrote:
>>>>>>>> Seems like saturating arithmetic is a thing, apparently with
>>>>>>>> integers. I can see that for applications that interface with
>>>>>>>> the real world with limited-range sensors or actuators (no sense
>>>>>>>> in trying to put more than 20 mA on a 4-20 mA current loop).
>>>>>>>>
>>>>>>>> And floating point (usually?) does not need it.
>>>>>>>>
>>>>>>>> What's the best way of encoding this in an ISA? To cover the
>>>>>>>> range of 8,16,32,64 bit calculations would need two bits. Or,
>>>>>>>> if somebody has, let's say, a 12-bit sensor, intermediate lengths
>>>>>>>> might also come in handy to clip results to between -2048..2047.
>>>>>>>>
>>>>>>>> Or is it just not worth the bother? Maybe people who have
>>>>>>>> experience with embedded CPUs can say something about this.
>>>>>> <
>>>>>>> IIRC, saturating adds & subtracts are used for things like JPEG &
>>>>>>> MPEG encoding/decoding.
>>>>>>> For 12 bit, you could do 16 bit and then have ceiling/floor
>>>>>>> operations to "clip" the result.
>>>>>> <
>>>>>> For ADA: one would want to saturate at particular end-of-range which
>>>>>> may not be power of 2.
>>>>>> Do most of the rest: one would saturate to the size of a container which
>>>>>> may not be a power of 2.
>>>>>> <
>>>>>> If one can avoid integer overflow in the actual calculation, one can
>>>>>> have an extract instruction (or a saturate instruction) that provides
>>>>>> the necessary bounds (operands) and an instruction that does::
>>>>>> <
>>>>>> if( x < lbounds ) r = lbounds;
>>>>>> else if( x > ubounds ) r = ubounds;
>>>>>> else r = x;
>>>>>
>>>>> A few comments.
>>>>>
>>>>> 1. I think that saturating arithmetic is a pretty big thing in DSPs.
>>>>> If that is so, then perhaps someone who is familiar with the usage
>>>>> patterns there can chime in.
>>>>>
>>>>> 2. I recall that the Mill will offer saturating arithmetic. Perhaps
>>>>> Ivan can provide more information.
>>>> Every operation that can overflow has saturation as one of the overflow
>>>> behaviors (the others are wrap, fault, and double-wide result).
>>>>
>>>> The reason for hardware saturation is not bound checking, it's
>>>> intra-expression overflow. If the expression is "a = b +b" then you can
>>>> check the condition codes (the groan you hear is Mitch turning over in
>>>> his grave)
>>> <
>>> The contrapositive is much more likely. I an neither in my grave, nor
>>> turning over.
>>> <
>>>> with a conditional branch (plugging up the predictor) or a
>>>> special op. If the expression is a = b+c*d-e" then checking gets out of
>>>> hand.
>>> <
>>> If you do it with predication you don't <necessarily>plug up[ the branch
>>> predictor.
>>> <
>>> Which leads to the question: does one use the same predictor for
>>> branches and for predication ??? Hmmmmm.........
> <
>> Why predict predication? Just be wide enough that you don't care that
>> some are nooped.
> <
> My compiler uses predication indiscriminately--it predicates anything
> and everything that fits under an 8 instruction shadow--without thinking
> about whether the control flow is predictable or not.
> <
> But the execution model does not use the predictor associated with
> branches either.
> <
> The thought train is that one sues predication when the join point of
> flow control will already have been fetched by the time the flow control
> becomes manifest. And for the vast majority of predications, the join
> point has already arrived by the time the PRED instruction is ready to
> execute. Thus, there is no reason to alter the fetch point, and it is
> easier to skip instructions.

You need a good lawyer if you sue predication.

Seems that you condition predication on the encoding artifact that is
used to express it. A better choice is: use predication if the resources
used by all-path predication are less than the resources used by
branching as weighted by the path probability, including the cost of
misprediction. This leads to balancing resource criticality, width, and
miss cost and probability.

For a throughput design like Mill the resource is execution speed, the
width is family-member dependent, and miss is usually frequent enough to
dominate costs. Internally the code generator uses a tunable cost
function to decide on predication.

On 17/11/2022 22:49, MitchAlsup wrote:
> On Thursday, November 17, 2022 at 2:20:08 PM UTC-6, Stephen Fuld wrote:
>> On 11/17/2022 11:36 AM, MitchAlsup wrote:
>

>>
>> 4. Your example requires a three operand instruction. This is
>> frequently overkill, as for example, if the arithmetic operation was an
>> unsigned add, there is no need to test the lower bounds, and a simple,
>> two operand MAX instruction would be sufficient.
> <
> MIN(ubound,MAX(lbound,result))
> <
> If you prefer.

Usually, lbound is either 0, or -ubound. It's rare that you need two
independent bounds.