EricP <ThatWouldBeTelling@thevillage.com> schrieb:
> MitchAlsup wrote:
>> On Wednesday, May 19, 2021 at 7:23:04 AM UTC-5, Anton Ertl wrote:
>>> Thomas Koenig <tko...@netcologne.de> writes:
>>>> Anton Ertl <an...@mips.complang.tuwien.ac.at> schrieb:
>>>>> Thomas Koenig <tko...@netcologne.de> writes:
>>>>>> Unsigned loops can cause a headache, because it is often
>>>>>> not possible to prove they actually terminate...
>>>>> And the difference to signed loops is? Note that you wrote
>>>>> "actually", so pretending that signed overflow does not happen does
>>>>> not count.
>>>> According to many language definitions, it does indeed not
>>>> count.
>>> This sentence makes no sense.
>> <
>> How about this::
>> <
>> Languages, that want to be ported across multiple architectures, and
>> have high performing implementations, cannot specify that signed integers
>> overflow.
>> <
>
> The language spec should:
> - allow the programmer to choose between bounds-range checked,
> unchecked, modulo, or saturating data types

That is not going to fly for an established, general-purpose
language. Languages have traditionally tried to stay away from
this kind of thing because of the very many different implementations
there are.

Fortran is a bit of an exception in that it supports IEEE floating
point via intrinsic modules.

And face it - a numeric type that is not supported by hardware is
going to suck rocks through a straw, performance-wise. Think about
the floating-point performance in the Intel days before the numeric
coprocessors.

But you can, of course, write everything in C++ and then
overload everything in sight.

> - specify that range and array bounds checks can be enabled or disabled
> at compile time by command line options or inline pragmas,
> for blocks of code, individual data types, or individual objects.

If you want to do that, your best bet is probably to use
manual checks.

> So that it is up to the software product developers to make any
> cost-performance tradoff, not the language or HW designers.

You left out the compiler writers... somebody would have to
implement all that.

Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
> Thomas Koenig <tkoenig@netcologne.de> writes:
>>Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>>> Thomas Koenig <tkoenig@netcologne.de> writes:
>>>>Unsigned loops can cause a headache, because it is often
>>>>not possible to prove they actually terminate...
>>>
>>> And the difference to signed loops is? Note that you wrote
>>> "actually", so pretending that signed overflow does not happen does
>>> not count.
>>
>>According to many language definitions, it does indeed not
>>count.
>
> This sentence makes no sense.
>
>>I could quote you chapter and verse from the Fortran standard, but
>>I hope you'll take my word for it.
>
> What do "many language definitions" and "the Fortran standard" have to
> do with proving what *actually* happens?

I am not sure that I follow.

Language standards usually describe the behavior of a program at an
abstract level. They specify rules for programs. Compilers ( or
interpreters, or... ) may or may not be required to catch violations
of said rules, depending on the specific rule. As an example, the
Fortran standard has "constraints" which a compiler must issue a
diagnostic for, or it's a bug in the compiler. Those are usually
things that are fairly easy to find at compile-time.

Are we agreed on that?

If a program violates a rule that a compiler does not need to
catch, it may still issue a diagnostic, either at compile-time
or at run-time. For example, the code

real :: a(10)
do i=1,11
a(i) = 42.
end do
end

will issue the warning

2 | do i=1,11
| 2
3 | a(i) = 42.
| 1
Warning: Array reference at (1) out of bounds (11 > 10)
in loop beginning at (2)

if you use gfortran, and if you specify bounds checking,
running it will result in

At line 3 of file a.f90
Fortran runtime error: Index '11' of dimension 1 of array 'a'
above upper bound of 10

Are we still agreed on that?

So, what happens if a program violates the rules, and the compiler
is not required to find that particular bug?

If you want to impose a requirement on that, there is
required behavior, and we are back to one of the previous cases.

If you do _not_ want to impose a requirement on that, what
should the behavior be?

This is unspecified, anything can happen.

Let's look at

void foo (int *a, int from, int to)
{ for (i=from; i<to; i++)
a[i] = 0;
}

Should the compiler be allowed to conclude that this loop
terminates? The write to a[i] could clobber the memory location of
i, and this could go into an endless loop. At higher optimization
level, i could be kept in a register, and the loop could terminate.

[...]

> but my experience is that gcc tends towards "optimizing"
> intended-to-be-bounded loops into endless loops, not the reverse.

Do you have an example for that?

On Wednesday, May 19, 2021 at 11:32:29 AM UTC-5, Thomas Koenig wrote:
> EricP <ThatWould...@thevillage.com> schrieb:
> > MitchAlsup wrote:
> >> On Wednesday, May 19, 2021 at 7:23:04 AM UTC-5, Anton Ertl wrote:
> >>> Thomas Koenig <tko...@netcologne.de> writes:
> >>>> Anton Ertl <an...@mips.complang.tuwien.ac.at> schrieb:
> >>>>> Thomas Koenig <tko...@netcologne.de> writes:
> >>>>>> Unsigned loops can cause a headache, because it is often
> >>>>>> not possible to prove they actually terminate...
> >>>>> And the difference to signed loops is? Note that you wrote
> >>>>> "actually", so pretending that signed overflow does not happen does
> >>>>> not count.
> >>>> According to many language definitions, it does indeed not
> >>>> count.
> >>> This sentence makes no sense.
> >> <
> >> How about this::
> >> <
> >> Languages, that want to be ported across multiple architectures, and
> >> have high performing implementations, cannot specify that signed integers
> >> overflow.
> >> <
> >
> > The language spec should:
> > - allow the programmer to choose between bounds-range checked,
> > unchecked, modulo, or saturating data types
<
> That is not going to fly for an established, general-purpose
> language. Languages have traditionally tried to stay away from
> this kind of thing because of the very many different implementations
> there are.
>
> Fortran is a bit of an exception in that it supports IEEE floating
> point via intrinsic modules.
>
> And face it - a numeric type that is not supported by hardware is
> going to suck rocks through a straw, performance-wise.
<
I do not think you are thinking about {in my best Monty Python voice}
"little bitty rocks" but the typical pick up and throw rocks.......
<
> Think about
> the floating-point performance in the Intel days before the numeric
> coprocessors.
>
> But you can, of course, write everything in C++ and then
> overload everything in sight.
> > - specify that range and array bounds checks can be enabled or disabled
> > at compile time by command line options or inline pragmas,
> > for blocks of code, individual data types, or individual objects.
> If you want to do that, your best bet is probably to use
> manual checks.
> > So that it is up to the software product developers to make any
> > cost-performance tradoff, not the language or HW designers.
> You left out the compiler writers... somebody would have to
> implement all that.

On Wednesday, May 19, 2021 at 12:13:58 PM UTC-5, Thomas Koenig wrote:
> Anton Ertl <an...@mips.complang.tuwien.ac.at> schrieb:
> > Thomas Koenig <tko...@netcologne.de> writes:
> >>Anton Ertl <an...@mips.complang.tuwien.ac.at> schrieb:
>
> This is unspecified, anything can happen.
>
> Let's look at
>
> void foo (int *a, int from, int to)
> {
> for (i=from; i<to; i++)
> a[i] = 0;
> }
>
> Should the compiler be allowed to conclude that this loop
> terminates? The write to a[i] could clobber the memory location of
> i, and this could go into an endless loop. At higher optimization
> level, i could be kept in a register, and the loop could terminate.
<
If the subroutine and the caller were written in FORTRAN, instead
of passing of a pointer to a[] one passes a dope vector to a[1..10]
and then the run time can check that 'to' is within [1..10] and you
get safe and fast code, rather than unsafe and fast code.
>
> [...]
> > but my experience is that gcc tends towards "optimizing"
> > intended-to-be-bounded loops into endless loops, not the reverse.
> Do you have an example for that?

Thomas Koenig wrote:
> EricP <ThatWouldBeTelling@thevillage.com> schrieb:
>> MitchAlsup wrote:
>>> On Wednesday, May 19, 2021 at 7:23:04 AM UTC-5, Anton Ertl wrote:
>>>> Thomas Koenig <tko...@netcologne.de> writes:
>>>>> Anton Ertl <an...@mips.complang.tuwien.ac.at> schrieb:
>>>>>> Thomas Koenig <tko...@netcologne.de> writes:
>>>>>>> Unsigned loops can cause a headache, because it is often
>>>>>>> not possible to prove they actually terminate...
>>>>>> And the difference to signed loops is? Note that you wrote
>>>>>> "actually", so pretending that signed overflow does not happen does
>>>>>> not count.
>>>>> According to many language definitions, it does indeed not
>>>>> count.
>>>> This sentence makes no sense.
>>> <
>>> How about this::
>>> <
>>> Languages, that want to be ported across multiple architectures, and
>>> have high performing implementations, cannot specify that signed integers
>>> overflow.
>>> <
>> The language spec should:
>> - allow the programmer to choose between bounds-range checked,
>> unchecked, modulo, or saturating data types
>
> That is not going to fly for an established, general-purpose
> language. Languages have traditionally tried to stay away from
> this kind of thing because of the very many different implementations
> there are.

I didn't say an established language.
I have no illusions that C is fixable.

> Fortran is a bit of an exception in that it supports IEEE floating
> point via intrinsic modules.
>
> And face it - a numeric type that is not supported by hardware is
> going to suck rocks through a straw, performance-wise. Think about
> the floating-point performance in the Intel days before the numeric
> coprocessors.

Checked or saturating integer operations are not remotely
comparable to floating point.

For example, on x64 signed and unsigned overflow check
are a "jo" or "jc" instruction.

Saturating unsigned and signed add on x64:

// rsi+rdi->rax
sat_addu64b:
add %rsi, %rdi
sbb %rax, %rax
or %rdi, %rax

long_max:
.quad 0x7fffffffffffffff
long_min:
.quad 0x8000000000000000

// rsi+rdi->rax
sat_adds64b:
mov %rdi, %rax
shr $0x3f, %rdi
add long_max(%rip), %rdi
add %rsi, %rax
cmovo %rdi, %rax

> But you can, of course, write everything in C++ and then
> overload everything in sight.

Those are the implementations that suck,
both in terms of functionality and performance.

And the language semantics are still C++'s with all its flaws.

>> - specify that range and array bounds checks can be enabled or disabled
>> at compile time by command line options or inline pragmas,
>> for blocks of code, individual data types, or individual objects.
>
> If you want to do that, your best bet is probably to use
> manual checks.

That is what is done now. That is why code is riddled with bugs.

>> So that it is up to the software product developers to make any
>> cost-performance tradoff, not the language or HW designers.
>
> You left out the compiler writers... somebody would have to
> implement all that.

It need be no more complicated than a Pascal front end.
Certainly nothing like a C++ compiler.
Back end is the same as many other languages.

MitchAlsup <MitchAlsup@aol.com> writes:
>On Wednesday, May 19, 2021 at 7:23:04 AM UTC-5, Anton Ertl wrote:
>> Thomas Koenig <tko...@netcologne.de> writes:
>> >Anton Ertl <an...@mips.complang.tuwien.ac.at> schrieb:
>> >> Thomas Koenig <tko...@netcologne.de> writes:
>> >>>Unsigned loops can cause a headache, because it is often
>> >>>not possible to prove they actually terminate...
>> >>
>> >> And the difference to signed loops is? Note that you wrote
>> >> "actually", so pretending that signed overflow does not happen does
>> >> not count.
>> >
>> >According to many language definitions, it does indeed not
>> >count.
>> This sentence makes no sense.
><
>How about this::
><
>Languages, that want to be ported across multiple architectures, and
>have high performing implementations, cannot specify that signed integers
>overflow.

Which proves that truth does not matter, repetition does. Fans of
undefined behaviour (and exploiting it in miscompilers) have repeated
the fairy tale that undefining signed overflow is important for
performance so often that you fell for it. And the cool thing is that
they invariably don't present any numbers to back it up. The one time
I saw numbers gcc people were citing an unnamed source who used an IBM
AIX compiler.

Wang et al. [wang+12] actually measured the effect of -wrapv (with
both gcc and clang on AMD64) on SPECint, and they found that in all of
SPECint, there was exactly one place where it made a significant
performance difference. It -wrapv introduced a sign-extension
instruction in one place in one benchmark (out of ~12 or so),
resulting in ~10% speed difference for that benchmark (this was a hot
loop), <1% for the suite. This could be fixed by making the loop
variable long instead of int.

So a language just has to avoid the mistake that C made when they went
I32LP64, and defining signed overflow is not even a minor performance
problem. BTW, Java defines signed overflow; not sure if you count it
in the class of programming languages mentioned above.

@InProceedings{wang+12,
author = {Xi Wang and Haogang Chen and Alvin Cheung and Zhihao Jia and Nickolai Zeldovich and M. Frans Kaashoek},
title = {Undefined Behavior: What Happened to My Code?},
booktitle = {Asia-Pacific Workshop on Systems (APSYS'12)},
OPTpages = {},
year = {2012},
url1 = {http://homes.cs.washington.edu/~akcheung/getFile.php?file=apsys12.pdf},
url2 = {http://people.csail.mit.edu/nickolai/papers/wang-undef-2012-08-21.pdf},
OPTannote = {}
}

>> >I could quote you chapter and verse from the Fortran standard, but
>> >I hope you'll take my word for it.
><
>> What do "many language definitions" and "the Fortran standard" have to
>> do with proving what *actually* happens?
><
>Many architectures do not have signed overflow.

This does not answer the question. And I really doubt that there is
even a single architecture with unbounded signed numbers.

>> Sure, a C compiler might "prove" that, under the assumption that no
>> undefined behaviour happens
>>
>> int i;
>> for (i=0; ;i++)
>> printf("%d\n",i);
>>
>> terminates: In general, ex falso quodlibet; in this case, the proof
>> could be as follows: you know that i is bounded, and you know that i
>> increases in every iteration, so the number of iterations is bounded
>> and the loop terminates.
....
>> The compiler cannot prove that if i is changed to unsigned. This does
>> not change the fact that this loop *actually* does not terminate in
>> either case;
><
>What logic does the compiler use to decide that the int version terminates

I wrote it above:

|you know that i is bounded, and you know that i
|increases in every iteration, so the number of iterations is bounded
|and the loop terminates.

Yes, it reaches a wrong conclusion. That's because it starts with a
wrong premise. That was my point.

>and the unsigned version does not.

In the unsigned version i++ can also decrease i.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:

> The major downside is that the world has adapted to the unwise
> decision to go I32LP64 for ~30 years, so any change now incurs
> significant switching cost.

You don't care about cache or memory bandwidth, then?

EricP <ThatWouldBeTelling@thevillage.com> schrieb:

Coming back.
> The language spec should:
> - allow the programmer to choose between bounds-range checked,
> unchecked, modulo, or saturating data types

That would be an interesting language design...

Using Fortran's attribute syntax here, because it
could easily be extended:

integer, unchecked :: i
integer, modulo :: j
integer, saturating :: n

Just a few question about this...

Should integer constants also have these properties? What about
named constants (parameters in Fortran parlance)? What about mixed
expressions, how would they work (or not)? What about expressions
using different integer sizes? What about calling a procedure with
a saturating argument, should it also require a saturating argument
as actual argument or should that be rejected or warned about?

Or do you want to make the these attributes a function
of the operators? Have a signed addition, a modulo
addition, a saturating addition operator in the language?

None of these questions are unsolvable (obviously), but you need
to think carefully about what the answer should be.

Language design is _hard_, and there are many traps for the unwary,
as evidenced by the many warts and quirks of existing languages.

Thomas Koenig <tkoenig@netcologne.de> writes:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>> Thomas Koenig <tkoenig@netcologne.de> writes:
>>>Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>>>> Thomas Koenig <tkoenig@netcologne.de> writes:
>>>>>Unsigned loops can cause a headache, because it is often
>>>>>not possible to prove they actually terminate...
>>>>
>>>> And the difference to signed loops is? Note that you wrote
>>>> "actually", so pretending that signed overflow does not happen does
>>>> not count.
>>>
>>>According to many language definitions, it does indeed not
>>>count.
>>
>> This sentence makes no sense.
>>
>>>I could quote you chapter and verse from the Fortran standard, but
>>>I hope you'll take my word for it.
>>
>> What do "many language definitions" and "the Fortran standard" have to
>> do with proving what *actually* happens?
>
>I am not sure that I follow.
>
>Language standards usually describe the behavior of a program at an
>abstract level. They specify rules for programs. Compilers ( or
>interpreters, or... ) may or may not be required to catch violations
>of said rules, depending on the specific rule.

And if they don't, the language standard does not say what *actually*
happens. And therefore a standard for a language like C and Fortran
that includes undefined behaviour cannot be used to prove what
*actually* happens in a program.

>Let's look at
>
>void foo (int *a, int from, int to)
>{
> for (i=from; i<to; i++)
> a[i] = 0;
>}
>
>Should the compiler be allowed to conclude that this loop
>terminates? The write to a[i] could clobber the memory location of
>i, and this could go into an endless loop. At higher optimization
>level, i could be kept in a register, and the loop could terminate.

Which does not support your claim that you can prove whether a program
actually terminates by looking at the language standard. It also does
not support your claim that proving termination is harder for unsigned
numbers.

>> but my experience is that gcc tends towards "optimizing"
>> intended-to-be-bounded loops into endless loops, not the reverse.
>
>Do you have an example for that?

void foo(int *a)
{ int i;
for (i=0; i<i+1; i++)
a[i&256]=0;
}

gcc-4.9.2 -O3 -S compiles foo into:

without -fwrapv: with -fwrapv:
foo: foo:
..LFB0: .LFB0:
.cfi_startproc .cfi_startproc
xorl %edx, %edx movl $1, %edx
.p2align 4,,10 jmp .L2
.p2align 3 .p2align 4,,10
..L2: .p2align 3
movl %edx, %eax .L3:
addl $1, %edx movl %eax, %edx
andl $256, %eax .L2:
cltq leal -1(%rdx), %eax
movl $0, (%rdi,%rax,4) andl $256, %eax
jmp .L2 cltq
movl $0, (%rdi,%rax,4)
leal 1(%rdx), %eax
cmpl %edx, %eax
jg .L3
rep ret

So without -fwrapv gcc optimizes the loop into an endless loop. The
reason is that gcc "proves" (without -fwrapv) that i<i+1 can never be
false, and "optimizes" the termination condition away.

The superfluous sign extension (cltq) is a nice comment on the origin
of this subthread. Note that the undefined overflow on the left side
does not protect you from that.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Thomas Koenig <tkoenig@netcologne.de> writes:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>
>> The major downside is that the world has adapted to the unwise
>> decision to go I32LP64 for ~30 years, so any change now incurs
>> significant switching cost.
>
>You don't care about cache or memory bandwidth, then?

When that plays a role, I use the appropriate in-memory
representation. No need to have e.g., 32-bit loop counters and
sign-extend them all the time for array access, though. Or to add
warts like the Aarch64 sign- and zero-extending addressing modes:

ldr W1, [X2, W3, sxtw] // W1 ← *(X2 + ExtendSigned32To64(W3))
ldr W1, [X2, W3, uxtw] // W1 ← *(X2 + ExtendUnsigned32To64(W3))

At least they would be unnecessary, if the I32LP64 mistake had not
been made. Speaking of which, given that Aarch64 has 32-bit
instructions that zero-extend their result, is uxtw really necessary?

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On 19/05/2021 21:48, Anton Ertl wrote:
> Thomas Koenig <tkoenig@netcologne.de> writes:
>> Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>>> Thomas Koenig <tkoenig@netcologne.de> writes:
>>>> Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
>>>>> Thomas Koenig <tkoenig@netcologne.de> writes:
>>>>>> Unsigned loops can cause a headache, because it is often
>>>>>> not possible to prove they actually terminate...
>>>>>
>>>>> And the difference to signed loops is? Note that you wrote
>>>>> "actually", so pretending that signed overflow does not happen does
>>>>> not count.
>>>>
>>>> According to many language definitions, it does indeed not
>>>> count.
>>>
>>> This sentence makes no sense.
>>>
>>>> I could quote you chapter and verse from the Fortran standard, but
>>>> I hope you'll take my word for it.
>>>
>>> What do "many language definitions" and "the Fortran standard" have to
>>> do with proving what *actually* happens?
>>
>> I am not sure that I follow.
>>
>> Language standards usually describe the behavior of a program at an
>> abstract level. They specify rules for programs. Compilers ( or
>> interpreters, or... ) may or may not be required to catch violations
>> of said rules, depending on the specific rule.
>
> And if they don't, the language standard does not say what *actually*
> happens. And therefore a standard for a language like C and Fortran
> that includes undefined behaviour cannot be used to prove what
> *actually* happens in a program.
>
>> Let's look at
>>
>> void foo (int *a, int from, int to)
>> {
>> for (i=from; i<to; i++)
>> a[i] = 0;
>> }
>>
>> Should the compiler be allowed to conclude that this loop
>> terminates? The write to a[i] could clobber the memory location of
>> i, and this could go into an endless loop. At higher optimization
>> level, i could be kept in a register, and the loop could terminate.
>
> Which does not support your claim that you can prove whether a program
> actually terminates by looking at the language standard. It also does
> not support your claim that proving termination is harder for unsigned
> numbers.
>
>>> but my experience is that gcc tends towards "optimizing"
>>> intended-to-be-bounded loops into endless loops, not the reverse.
>>
>> Do you have an example for that?

Do you have an example of sensible code where this happens, rather than
something that would be rejected by any code review as clearly wrong?

"int" in C models mathematical integers, with size limitations. Any
mathematician will tell you "i < i + 1" is obviously true, regardless of
the value of "i".

I really cannot see the problem with gcc's code here. But I would
greatly prefer a warning about the code - not even "-Wstrict-overflow=5"
gives a warning, which I find disappointing.

(gcc 10 does not have the unnecessary "cltq" instruction, unlike gcc 9
and below.)

>
> void foo(int *a)
> {
> int i;
> for (i=0; i<i+1; i++)
> a[i&256]=0;
> }
>
> gcc-4.9.2 -O3 -S compiles foo into:
>
> without -fwrapv: with -fwrapv:
> foo: foo:
> .LFB0: .LFB0:
> .cfi_startproc .cfi_startproc
> xorl %edx, %edx movl $1, %edx
> .p2align 4,,10 jmp .L2
> .p2align 3 .p2align 4,,10
> .L2: .p2align 3
> movl %edx, %eax .L3:
> addl $1, %edx movl %eax, %edx
> andl $256, %eax .L2:
> cltq leal -1(%rdx), %eax
> movl $0, (%rdi,%rax,4) andl $256, %eax
> jmp .L2 cltq
> movl $0, (%rdi,%rax,4)
> leal 1(%rdx), %eax
> cmpl %edx, %eax
> jg .L3
> rep ret
>
> So without -fwrapv gcc optimizes the loop into an endless loop. The
> reason is that gcc "proves" (without -fwrapv) that i<i+1 can never be
> false, and "optimizes" the termination condition away.
>
> The superfluous sign extension (cltq) is a nice comment on the origin
> of this subthread. Note that the undefined overflow on the left side
> does not protect you from that.
>
> - anton
>

On Wednesday, May 19, 2021 at 4:49:03 PM UTC-5, David Brown wrote:
> On 19/05/2021 21:48, Anton Ertl wrote:
> > Thomas Koenig <tko...@netcologne.de> writes:

> >>> but my experience is that gcc tends towards "optimizing"
> >>> intended-to-be-bounded loops into endless loops, not the reverse.
> >>
> >> Do you have an example for that?
> Do you have an example of sensible code where this happens, rather than
> something that would be rejected by any code review as clearly wrong?
<
How about something nefarious like::
<
unsigned char i;
// way farther down in the code
for( i = 0; i < 256; i++ )
<blah>
<
if the char part if 'i' is not on the same page as the for loop, it is easy for
the code reviewers to see the for loop as "reasonable".
<
>
> "int" in C models mathematical integers, with size limitations. Any
> mathematician will tell you "i < i + 1" is obviously true, regardless of
> the value of "i".
<
But notice that i < i+1 is NOT obviously true in floating point !
So if you don't have the type handy, the code reviewer is blind sided.
>

David Brown <david.brown@hesbynett.no> writes:
["optimize" bounded loop into an endless loop]
>Do you have an example of sensible code where this happens, rather than
>something that would be rejected by any code review as clearly wrong?

The classical example is the SATD function, which was "optimized" into
an endless loop by a prerelease of gcc-4.8; but the final version and
later versions of gcc do not perform this "optimization", a fact that
supposedly has nothing to do with SATD being in SPEC.

int d[16];

int SATD (void)
{

int satd = 0, dd, k;
for (dd=d[k=0]; k<16; dd=d[++k]) {

satd += (dd < 0 ? -dd : dd);
}
return satd;
}

Another example is a loop for filling an array with bit patterns,
something similar to

int a[16];

void bar()
{ int i;
int *p=a;
for (i=0; i!=-1; i+=0x11111111)
*p++=i;
}

gcc-4.9.2 -Os produces a warning:

xxx.c: In function ‘bar’:
xxx.c:7:21: warning: iteration 7u invokes undefined behavior [-Waggressive-loop-optimizations]
for (i=0; i!=-1; i+=0x11111111)
^
xxx.c:7:3: note: containing loop
for (i=0; i!=-1; i+=0x11111111)
^

and the following "optimized" endless loop:

..L4:
addq $4, %rdx
movl %eax, -4(%rdx)
addl $286331153, %eax
jmp .L4

Well, at least it warns.

>"int" in C models mathematical integers, with size limitations. Any
>mathematician will tell you "i < i + 1" is obviously true, regardless of
>the value of "i".

Any mathematician will tell you that mathematical integers have no
size limitations. And that the fact that for mathematical integers
i<i+1 hold regardless of the value of i depends on that property.

As soon as you have some limit, it's no longer the mathematical
integers, and i<i+1 does not hold for all of them; in particular, it
does not hold for i=int_max. And that's independent of whether you
use 2s-complement, 1s-complement, or sign-magnitude representation for
negative integers, and whether you handle overflow by modulo
arithmetic, by saturation, by trapping, or anything else.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On 20/05/2021 00:11, Anton Ertl wrote:
> David Brown <david.brown@hesbynett.no> writes:
> ["optimize" bounded loop into an endless loop]
>> Do you have an example of sensible code where this happens, rather than
>> something that would be rejected by any code review as clearly wrong?
>
> The classical example is the SATD function, which was "optimized" into
> an endless loop by a prerelease of gcc-4.8; but the final version and
> later versions of gcc do not perform this "optimization", a fact that
> supposedly has nothing to do with SATD being in SPEC.
>

When people say "I know this code is bad, but it's a common structure
and it worked before" then gcc developers give it due consideration. It
doesn't matter if it is from SPEC, the Linux kernel, or anything else.

And note that there is a reason there are pre-release versions made
available - they are for testing, aiming to find bugs or complicating
issues before a full release. (For this sort of situation, gcc issues a
warning, which is nice.)

The SPEC code here is bad C code - it always has been bad, but no one
noticed before. Mistakes happen, and even the best programmers get
things wrong at times - but you can't blame the compiler for finding
errors in your code.

> int d[16];
>
> int SATD (void)
> {
>
> int satd = 0, dd, k;
> for (dd=d[k=0]; k<16; dd=d[++k]) {
>
> satd += (dd < 0 ? -dd : dd);
> }
> return satd;
> }
>
> Another example is a loop for filling an array with bit patterns,
> something similar to
>
> int a[16];
>
> void bar()
> {
> int i;
> int *p=a;
> for (i=0; i!=-1; i+=0x11111111)
> *p++=i;
> }
>
> gcc-4.9.2 -Os produces a warning:
>
> xxx.c: In function ‘bar’:
> xxx.c:7:21: warning: iteration 7u invokes undefined behavior [-Waggressive-loop-optimizations]
> for (i=0; i!=-1; i+=0x11111111)
> ^
> xxx.c:7:3: note: containing loop
> for (i=0; i!=-1; i+=0x11111111)
> ^
>
> and the following "optimized" endless loop:
>
> .L4:
> addq $4, %rdx
> movl %eax, -4(%rdx)
> addl $286331153, %eax
> jmp .L4
>
> Well, at least it warns.

Warning is good.

Perhaps it should also give the suggestion "you should be using unsigned
types for this kind of thing". As a general rule, anything involving
bit patterns should be unsigned types - signed types are for abstract
numbers only.

>
>> "int" in C models mathematical integers, with size limitations. Any
>> mathematician will tell you "i < i + 1" is obviously true, regardless of
>> the value of "i".
>
> Any mathematician will tell you that mathematical integers have no
> size limitations. And that the fact that for mathematical integers
> i<i+1 hold regardless of the value of i depends on that property.

No, the fact that "i + 1" is defined for all mathematical integers
depends on the unlimited size. When there is a size limit (as in C),
the expression "i + 1" is a partial function, only defined for some
values of "i". (Partial functions are common in mathematics too -
"log(0)" is undefined, just like in C.) So more accurately, "i < i + 1"
is always true for any "i" for which the expression makes sense. In
particular, that also means it is never false.

>
> As soon as you have some limit, it's no longer the mathematical
> integers, and i<i+1 does not hold for all of them; in particular, it
> does not hold for i=int_max.

However, you never have a value "i" for which "i < i + 1" is false.

> And that's independent of whether you
> use 2s-complement, 1s-complement, or sign-magnitude representation for
> negative integers, and whether you handle overflow by modulo
> arithmetic, by saturation, by trapping, or anything else.
>

True - but the difference is that when the overflow is not defined, you
have a third option for the result of the expression. It can be true,
false, or not defined - a nonsensical expression (like 1/0, log(0),
etc., in normal maths). A compiler only needs to obey code that makes
sense. (Though I am all in favour of as many warnings as possible when
the compiler can see that the code doesn't make sense - and there is
always scope for improvement in that area.)

On 20/05/2021 00:30, MitchAlsup wrote:
> On Wednesday, May 19, 2021 at 4:49:03 PM UTC-5, David Brown wrote:
>> On 19/05/2021 21:48, Anton Ertl wrote:
>>> Thomas Koenig <tko...@netcologne.de> writes:
>
>>>>> but my experience is that gcc tends towards "optimizing"
>>>>> intended-to-be-bounded loops into endless loops, not the reverse.
>>>>
>>>> Do you have an example for that?
>> Do you have an example of sensible code where this happens, rather than
>> something that would be rejected by any code review as clearly wrong?
> <
> How about something nefarious like::
> <
> unsigned char i;
> // way farther down in the code
> for( i = 0; i < 256; i++ )
> <blah>

That /is/ an infinite loop (for 8-bit char). How could a compiler read
the programmer's mind and guess what was meant? We are not talking
about simple mistakes in the code here - we are talking about more
subtle mistakes made by people who think C should mean something it doesn't.

The way to avoid this sort of thing is to keep the scope of your local
variables tight:

for (unsigned char i = 0; i < 256; i++) {
...
}

Then it is a lot clearer. C99 has been around for quite a while now.
It is also a good idea to use a compiler (or other tool) that can do
static error checking - we all get things wrong sometimes.

> <
> if the char part if 'i' is not on the same page as the for loop, it is easy for
> the code reviewers to see the for loop as "reasonable".
> <

As a code reviewer, I would not find that loop remotely reasonable if I
could not immediately see the definition of "i". Even if it was defined
just above the loop, I would question why it is not defined within the
"for" statement.

>>
>> "int" in C models mathematical integers, with size limitations. Any
>> mathematician will tell you "i < i + 1" is obviously true, regardless of
>> the value of "i".
> <
> But notice that i < i+1 is NOT obviously true in floating point !

C floating point has different rules from mathematical real numbers.
There is a rough similarity, but noticeable differences.

> So if you don't have the type handy, the code reviewer is blind sided.

And thus the code should be rejected by the reviewer.

One of the purposes of code review is to be sure the code is correct (or
at least, increase the chances of spotting errors). If the reviewer is
blind-sided, and cannot see that it is correct, the code should be rejected.

On Wednesday, May 19, 2021 at 6:25:20 PM UTC-5, David Brown wrote:
> On 20/05/2021 00:11, Anton Ertl wrote:
> > David Brown <david...@hesbynett.no> writes:
> > ["optimize" bounded loop into an endless loop]
> >> Do you have an example of sensible code where this happens, rather than
> >> something that would be rejected by any code review as clearly wrong?
> >
> > The classical example is the SATD function, which was "optimized" into
> > an endless loop by a prerelease of gcc-4.8; but the final version and
> > later versions of gcc do not perform this "optimization", a fact that
> > supposedly has nothing to do with SATD being in SPEC.
> >
> When people say "I know this code is bad, but it's a common structure
> and it worked before" then gcc developers give it due consideration. It
> doesn't matter if it is from SPEC, the Linux kernel, or anything else.
>
> And note that there is a reason there are pre-release versions made
> available - they are for testing, aiming to find bugs or complicating
> issues before a full release. (For this sort of situation, gcc issues a
> warning, which is nice.)
>
> The SPEC code here is bad C code - it always has been bad, but no one
> noticed before. Mistakes happen, and even the best programmers get
> things wrong at times - but you can't blame the compiler for finding
> errors in your code.
> > int d[16];
> >
> > int SATD (void)
> > {
> >
> > int satd = 0, dd, k;
> > for (dd=d[k=0]; k<16; dd=d[++k]) {
> >
> > satd += (dd < 0 ? -dd : dd);
> > }
> > return satd;
> > }
> >
> > Another example is a loop for filling an array with bit patterns,
> > something similar to
> >
> > int a[16];
> >
> > void bar()
> > {
> > int i;
> > int *p=a;
> > for (i=0; i!=-1; i+=0x11111111)
> > *p++=i;
> > }
> >
> > gcc-4.9.2 -Os produces a warning:
> >
> > xxx.c: In function ‘bar’:
> > xxx.c:7:21: warning: iteration 7u invokes undefined behavior [-Waggressive-loop-optimizations]
> > for (i=0; i!=-1; i+=0x11111111)
> > ^
> > xxx.c:7:3: note: containing loop
> > for (i=0; i!=-1; i+=0x11111111)
> > ^
> >
> > and the following "optimized" endless loop:
> >
> > .L4:
> > addq $4, %rdx
> > movl %eax, -4(%rdx)
> > addl $286331153, %eax
> > jmp .L4
> >
> > Well, at least it warns.
> Warning is good.
>
> Perhaps it should also give the suggestion "you should be using unsigned
> types for this kind of thing". As a general rule, anything involving
> bit patterns should be unsigned types - signed types are for abstract
> numbers only.
<
All integral container that do not explicitly need to contain negative
numbers should be unsigned.
> >
> >> "int" in C models mathematical integers, with size limitations. Any
> >> mathematician will tell you "i < i + 1" is obviously true, regardless of
> >> the value of "i".
> >
> > Any mathematician will tell you that mathematical integers have no
> > size limitations. And that the fact that for mathematical integers
> > i<i+1 hold regardless of the value of i depends on that property.
<
> No, the fact that "i + 1" is defined for all mathematical integers
> depends on the unlimited size. When there is a size limit (as in C),
> the expression "i + 1" is a partial function, only defined for some
> values of "i". (Partial functions are common in mathematics too -
> "log(0)" is undefined, just like in C.)
<
Not quite::
<
log(+0) is defined to be -INFINITY
log(-0) is undefined (NaN)
<
And has been so defined since at least 754-2008 maybe since 85.
Any machine claiming to be IEEE compliance needs to have this property.
Any compiler compiling to a target claiming 754 compliance should
have this property.
<
> So more accurately, "i < i + 1"
> is always true for any "i" for which the expression makes sense. In
> particular, that also means it is never false.
> >
> > As soon as you have some limit, it's no longer the mathematical
> > integers, and i<i+1 does not hold for all of them; in particular, it
> > does not hold for i=int_max.
> However, you never have a value "i" for which "i < i + 1" is false.
<
when i=POSMAX and you are running in a saturated integer machine
it is.
<
> > And that's independent of whether you
> > use 2s-complement, 1s-complement, or sign-magnitude representation for
> > negative integers, and whether you handle overflow by modulo
> > arithmetic, by saturation, by trapping, or anything else.
> >
> True - but the difference is that when the overflow is not defined, you
> have a third option for the result of the expression. It can be true,
> false, or not defined - a nonsensical expression (like 1/0, log(0),
> etc., in normal maths). A compiler only needs to obey code that makes
> sense. (Though I am all in favour of as many warnings as possible when
> the compiler can see that the code doesn't make sense - and there is
> always scope for improvement in that area.)

On 5/19/2021 4:54 PM, MitchAlsup wrote:
> On Wednesday, May 19, 2021 at 6:25:20 PM UTC-5, David Brown wrote:
>> On 20/05/2021 00:11, Anton Ertl wrote:
>>> David Brown <david...@hesbynett.no> writes:
>>> ["optimize" bounded loop into an endless loop]
>>>> Do you have an example of sensible code where this happens, rather than
>>>> something that would be rejected by any code review as clearly wrong?
>>>
>>> The classical example is the SATD function, which was "optimized" into
>>> an endless loop by a prerelease of gcc-4.8; but the final version and
>>> later versions of gcc do not perform this "optimization", a fact that
>>> supposedly has nothing to do with SATD being in SPEC.
>>>
>> When people say "I know this code is bad, but it's a common structure
>> and it worked before" then gcc developers give it due consideration. It
>> doesn't matter if it is from SPEC, the Linux kernel, or anything else.
>>
>> And note that there is a reason there are pre-release versions made
>> available - they are for testing, aiming to find bugs or complicating
>> issues before a full release. (For this sort of situation, gcc issues a
>> warning, which is nice.)
>>
>> The SPEC code here is bad C code - it always has been bad, but no one
>> noticed before. Mistakes happen, and even the best programmers get
>> things wrong at times - but you can't blame the compiler for finding
>> errors in your code.
>>> int d[16];
>>>
>>> int SATD (void)
>>> {
>>>
>>> int satd = 0, dd, k;
>>> for (dd=d[k=0]; k<16; dd=d[++k]) {
>>>
>>> satd += (dd < 0 ? -dd : dd);
>>> }
>>> return satd;
>>> }
>>>
>>> Another example is a loop for filling an array with bit patterns,
>>> something similar to
>>>
>>> int a[16];
>>>
>>> void bar()
>>> {
>>> int i;
>>> int *p=a;
>>> for (i=0; i!=-1; i+=0x11111111)
>>> *p++=i;
>>> }
>>>
>>> gcc-4.9.2 -Os produces a warning:
>>>
>>> xxx.c: In function ‘bar’:
>>> xxx.c:7:21: warning: iteration 7u invokes undefined behavior [-Waggressive-loop-optimizations]
>>> for (i=0; i!=-1; i+=0x11111111)
>>> ^
>>> xxx.c:7:3: note: containing loop
>>> for (i=0; i!=-1; i+=0x11111111)
>>> ^
>>>
>>> and the following "optimized" endless loop:
>>>
>>> .L4:
>>> addq $4, %rdx
>>> movl %eax, -4(%rdx)
>>> addl $286331153, %eax
>>> jmp .L4
>>>
>>> Well, at least it warns.
>> Warning is good.
>>
>> Perhaps it should also give the suggestion "you should be using unsigned
>> types for this kind of thing". As a general rule, anything involving
>> bit patterns should be unsigned types - signed types are for abstract
>> numbers only.
> <
> All integral container that do not explicitly need to contain negative
> numbers should be unsigned.

True for whichever "integral containers" actually model subranges of
integers; those should not wrap. Unfortunately, among other problems C
conflates those with "logical containers" that model subranges of bool
arrays. For those both LSL and ROTL are meaningful, and should be
distinct operations.

On 20/05/2021 01:54, MitchAlsup wrote:
> On Wednesday, May 19, 2021 at 6:25:20 PM UTC-5, David Brown wrote:
>> On 20/05/2021 00:11, Anton Ertl wrote:
>>> David Brown <david...@hesbynett.no> writes:

>>
>> Perhaps it should also give the suggestion "you should be using unsigned
>> types for this kind of thing". As a general rule, anything involving
>> bit patterns should be unsigned types - signed types are for abstract
>> numbers only.
> <
> All integral container that do not explicitly need to contain negative
> numbers should be unsigned.

That also works.

But if you are saying this because overflow is defined for unsigned
types in C, then I would disagree with the point - as overflow is
generally (but not always) a mistake, whether signed or unsigned, and
should not occur in normal code.

>>>
>>>> "int" in C models mathematical integers, with size limitations. Any
>>>> mathematician will tell you "i < i + 1" is obviously true, regardless of
>>>> the value of "i".
>>>
>>> Any mathematician will tell you that mathematical integers have no
>>> size limitations. And that the fact that for mathematical integers
>>> i<i+1 hold regardless of the value of i depends on that property.
> <
>> No, the fact that "i + 1" is defined for all mathematical integers
>> depends on the unlimited size. When there is a size limit (as in C),
>> the expression "i + 1" is a partial function, only defined for some
>> values of "i". (Partial functions are common in mathematics too -
>> "log(0)" is undefined, just like in C.)
> <
> Not quite::
> <
> log(+0) is defined to be -INFINITY
> log(-0) is undefined (NaN)
> <
> And has been so defined since at least 754-2008 maybe since 85.
> Any machine claiming to be IEEE compliance needs to have this property.
> Any compiler compiling to a target claiming 754 compliance should
> have this property.
> <

Actually, in C log(0) is not fully defined - a "pole error" may occur,
giving an implementation-defined result. (This is very different from
being "undefined".) C implementations don't have to support IEEE
standards, though they usually do.

(I have never been fussed about this sort of thing - I haven't needed
to, for the code I write.)

>> So more accurately, "i < i + 1"
>> is always true for any "i" for which the expression makes sense. In
>> particular, that also means it is never false.
>>>
>>> As soon as you have some limit, it's no longer the mathematical
>>> integers, and i<i+1 does not hold for all of them; in particular, it
>>> does not hold for i=int_max.
>> However, you never have a value "i" for which "i < i + 1" is false.
> <
> when i=POSMAX and you are running in a saturated integer machine
> it is.
> <

The C standards leave INT_MAX + 1 undefined, and an implementation that
does not add additional semantics giving it a definition can assume "i <
i + 1" is never false, regardless of the value of "i".

Particular implementations (or flags, options, etc.) can define INT_MAX
+ 1, and thereby have different rules in cases where C does not define
the results.

On 5/19/2021 8:47 AM, EricP wrote:
> MitchAlsup wrote:
>> On Wednesday, May 19, 2021 at 7:23:04 AM UTC-5, Anton Ertl wrote:
>>> Thomas Koenig <tko...@netcologne.de> writes:
>>>> Anton Ertl <an...@mips.complang.tuwien.ac.at> schrieb:
>>>>> Thomas Koenig <tko...@netcologne.de> writes:
>>>>>> Unsigned loops can cause a headache, because it is often not
>>>>>> possible to prove they actually terminate...
>>>>> And the difference to signed loops is? Note that you wrote
>>>>> "actually", so pretending that signed overflow does not happen does
>>>>> not count.
>>>> According to many language definitions, it does indeed not count.
>>> This sentence makes no sense.
>> <
>> How about this::
>> <
>> Languages, that want to be ported across multiple architectures, and
>> have high performing implementations, cannot specify that signed
>> integers overflow.
>> <
>
> The language spec should:
> - allow the programmer to choose between bounds-range checked,
>   unchecked, modulo, or saturating data types

Ada allows range checked, i.e. Range 20-100, unchecked, at least within
the limits of the size, and Modulo variables. I suspect adding
saturated wouldn't be a big stretch if it were popular enough.
Saturating would be pretty inexpensive to check, especially if you have
something like a CMOV instruction.

> - specify that range and array bounds checks can be enabled or disabled
>   at compile time by command line options or inline pragmas,
>   for blocks of code, individual data types, or individual objects.

Since Ada supports Range attributes, and you can use a range restricted
variable as a subscript or loop limit, I think you can do all of that.

But Nick Holsti is the Ada expert around here, so perhaps he will chime in.

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

On Wednesday, May 19, 2021 at 7:37:33 PM UTC-5, David Brown wrote:
> On 20/05/2021 01:54, MitchAlsup wrote:
> > On Wednesday, May 19, 2021 at 6:25:20 PM UTC-5, David Brown wrote:
> >> On 20/05/2021 00:11, Anton Ertl wrote:
> >>> David Brown <david...@hesbynett.no> writes:
>
> >>
> >> Perhaps it should also give the suggestion "you should be using unsigned
> >> types for this kind of thing". As a general rule, anything involving
> >> bit patterns should be unsigned types - signed types are for abstract
> >> numbers only.
> > <
> > All integral container that do not explicitly need to contain negative
> > numbers should be unsigned.
> That also works.
>
> But if you are saying this because overflow is defined for unsigned
> types in C, then I would disagree with the point - as overflow is
> generally (but not always) a mistake, whether signed or unsigned, and
> should not occur in normal code.
<
I am saying this because; unsigned arithmetic is much better defined
than signed arithmetic in C. The surprise coefficient is way lower.
<
> >>>
> >>>> "int" in C models mathematical integers, with size limitations. Any
> >>>> mathematician will tell you "i < i + 1" is obviously true, regardless of
> >>>> the value of "i".
> >>>
> >>> Any mathematician will tell you that mathematical integers have no
> >>> size limitations. And that the fact that for mathematical integers
> >>> i<i+1 hold regardless of the value of i depends on that property.
> > <
> >> No, the fact that "i + 1" is defined for all mathematical integers
> >> depends on the unlimited size. When there is a size limit (as in C),
> >> the expression "i + 1" is a partial function, only defined for some
> >> values of "i". (Partial functions are common in mathematics too -
> >> "log(0)" is undefined, just like in C.)
> > <
> > Not quite::
> > <
> > log(+0) is defined to be -INFINITY
> > log(-0) is undefined (NaN)
> > <
> > And has been so defined since at least 754-2008 maybe since 85.
> > Any machine claiming to be IEEE compliance needs to have this property.
> > Any compiler compiling to a target claiming 754 compliance should
> > have this property.
> > <
> Actually, in C log(0) is not fully defined - a "pole error" may occur,
> giving an implementation-defined result. (This is very different from
> being "undefined".) C implementations don't have to support IEEE
> standards, though they usually do.
>
> (I have never been fussed about this sort of thing - I haven't needed
> to, for the code I write.)
> >> So more accurately, "i < i + 1"
> >> is always true for any "i" for which the expression makes sense. In
> >> particular, that also means it is never false.
> >>>
> >>> As soon as you have some limit, it's no longer the mathematical
> >>> integers, and i<i+1 does not hold for all of them; in particular, it
> >>> does not hold for i=int_max.
> >> However, you never have a value "i" for which "i < i + 1" is false.
> > <
> > when i=POSMAX and you are running in a saturated integer machine
> > it is.
> > <
> The C standards leave INT_MAX + 1 undefined, and an implementation that
> does not add additional semantics giving it a definition can assume "i <
> i + 1" is never false, regardless of the value of "i".
>
> Particular implementations (or flags, options, etc.) can define INT_MAX
> + 1, and thereby have different rules in cases where C does not define
> the results.

On 5/19/2021 9:32 AM, Thomas Koenig wrote:
> EricP <ThatWouldBeTelling@thevillage.com> schrieb:
>> MitchAlsup wrote:
>>> On Wednesday, May 19, 2021 at 7:23:04 AM UTC-5, Anton Ertl wrote:
>>>> Thomas Koenig <tko...@netcologne.de> writes:
>>>>> Anton Ertl <an...@mips.complang.tuwien.ac.at> schrieb:
>>>>>> Thomas Koenig <tko...@netcologne.de> writes:
>>>>>>> Unsigned loops can cause a headache, because it is often
>>>>>>> not possible to prove they actually terminate...
>>>>>> And the difference to signed loops is? Note that you wrote
>>>>>> "actually", so pretending that signed overflow does not happen does
>>>>>> not count.
>>>>> According to many language definitions, it does indeed not
>>>>> count.
>>>> This sentence makes no sense.
>>> <
>>> How about this::
>>> <
>>> Languages, that want to be ported across multiple architectures, and
>>> have high performing implementations, cannot specify that signed integers
>>> overflow.
>>> <
>>
>> The language spec should:
>> - allow the programmer to choose between bounds-range checked,
>> unchecked, modulo, or saturating data types
>
> That is not going to fly for an established, general-purpose
> language.

A counter example is Ada, which implements most of those things.

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

On 5/19/2021 11:42 AM, Thomas Koenig wrote:
> EricP <ThatWouldBeTelling@thevillage.com> schrieb:
>
> Coming back.
>> The language spec should:
>> - allow the programmer to choose between bounds-range checked,
>> unchecked, modulo, or saturating data types
>
> That would be an interesting language design...
>
> Using Fortran's attribute syntax here, because it
> could easily be extended:
>
> integer, unchecked :: i
> integer, modulo :: j
> integer, saturating :: n
>
> Just a few question about this...
>
> Should integer constants also have these properties?

I don't see why they should. Most of these properties are only useful
if the item is the target of an assign statement, which obviously, a
constant can't be.

> What about
> named constants (parameters in Fortran parlance)?

Same arguments as above.

> What about mixed
> expressions, how would they work (or not)?

If you disallow side effects in expressions, then no need to. You can
effect some of what you might need with various simple functions that
could probably be inlined.

> What about expressions
> using different integer sizes? What about calling a procedure with
> a saturating argument, should it also require a saturating argument
> as actual argument or should that be rejected or warned about?

I think it should be required, unless you have some extra syntax saying
"I know this is unusual, but I know what I am doing, so trust me."

> Or do you want to make the these attributes a function
> of the operators?

You could make simple functions to accomplish at least some of these, so
I tentatively would not try to have multiple e.g. addition types. I
know the Mill supports at least some of these, so I am open to having my
mind changed.

Have a signed addition, a modulo
> addition, a saturating addition operator in the language?
>
> None of these questions are unsolvable (obviously), but you need
> to think carefully about what the answer should be.

Yup. I expect the people who defined some of them in Ada did just that!
:-)

>
> Language design is _hard_, and there are many traps for the unwary,
> as evidenced by the many warts and quirks of existing languages.

You got that right!

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

MitchAlsup <MitchAlsup@aol.com> schrieb:
> On Wednesday, May 19, 2021 at 4:49:03 PM UTC-5, David Brown wrote:
>> On 19/05/2021 21:48, Anton Ertl wrote:
>> > Thomas Koenig <tko...@netcologne.de> writes:
>
>> >>> but my experience is that gcc tends towards "optimizing"
>> >>> intended-to-be-bounded loops into endless loops, not the reverse.
>> >>
>> >> Do you have an example for that?
>> Do you have an example of sensible code where this happens, rather than
>> something that would be rejected by any code review as clearly wrong?
><
> How about something nefarious like::
><
> unsigned char i;
> // way farther down in the code
> for( i = 0; i < 256; i++ )
> <blah>

$ cat un.c
void bar(void);

void foo()
{ unsigned char i;
for( i = 0; i < 256; i++ )
bar();
} $ gcc -S -Wall -Wextra un.c
un.c: In function 'foo':
un.c:6:17: warning: comparison is always true due to limited range of data type [-Wtype-limits]
6 | for( i = 0; i < 256; i++ )
| ^
$ gcc -S -Wall -Wextra -Werror un.c
un.c: In function 'foo':
un.c:6:17: error: comparison is always true due to limited range of data type [-Werror=type-limits]
6 | for( i = 0; i < 256; i++ )
| ^
cc1: all warnings being treated as errors
$ clang -S -Wall un.c
un.c:6:17: warning: result of comparison of constant 256 with expression of type 'unsigned char' is always true [-Wtautological-constant-out-of-range-compare]
for( i = 0; i < 256; i++ )
~ ^ ~~~
1 warning generated.

> if the char part if 'i' is not on the same page as the for loop, it is easy for
> the code reviewers to see the for loop as "reasonable".

I'd expect a reasonable project to use appropriate warning flags.
"-Wall -Wextra -Werror" is a good start.

Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
> David Brown <david.brown@hesbynett.no> writes:
> ["optimize" bounded loop into an endless loop]
>>Do you have an example of sensible code where this happens, rather than
>>something that would be rejected by any code review as clearly wrong?
>
> The classical example is the SATD function, which was "optimized" into
> an endless loop by a prerelease of gcc-4.8; but the final version and
> later versions of gcc do not perform this "optimization", a fact that
> supposedly has nothing to do with SATD being in SPEC.
>
> int d[16];
>
> int SATD (void)
> {
>
> int satd = 0, dd, k;
> for (dd=d[k=0]; k<16; dd=d[++k]) {
>
> satd += (dd < 0 ? -dd : dd);
> }
> return satd;
> }

That's undefined behavior, anything can happen. Also, gcc
is nice enough to warn you (clang 10 doesn't catch this
particular one).

$ gcc -S -Wall -O satd.c
satd.c: In function 'SATD':
satd.c:7:28: warning: iteration 15 invokes undefined behavior [-Waggressive-loop-optimizations]
7 | for (dd=d[k=0]; k<16; dd=d[++k]) {
| ~~^~~~~~~
satd.c:7:21: note: within this loop
7 | for (dd=d[k=0]; k<16; dd=d[++k]) {

If somebody ignore compiler warnings like that, or if hat person does
not first run the code through "-Wall -Wextra -Werror" as a first
step, then the problem is not with the language definition or with
the compiler. The problem is then sitting before the keyboard.

On 2021-05-20 3:40, Stephen Fuld wrote:
> On 5/19/2021 8:47 AM, EricP wrote:
>> MitchAlsup wrote:
>>> On Wednesday, May 19, 2021 at 7:23:04 AM UTC-5, Anton Ertl wrote:
>>>> Thomas Koenig <tko...@netcologne.de> writes:
>>>>> Anton Ertl <an...@mips.complang.tuwien.ac.at> schrieb:
>>>>>> Thomas Koenig <tko...@netcologne.de> writes:
>>>>>>> Unsigned loops can cause a headache, because it is often not
>>>>>>> possible to prove they actually terminate...
>>>>>> And the difference to signed loops is? Note that you wrote
>>>>>> "actually", so pretending that signed overflow does not happen
>>>>>> does not count.
>>>>> According to many language definitions, it does indeed not count.
>>>> This sentence makes no sense.
>>> <
>>> How about this::
>>> <
>>> Languages, that want to be ported across multiple architectures, and
>>> have high performing implementations, cannot specify that signed
>>> integers overflow.
>>> <
>>
>> The language spec should:
>> - allow the programmer to choose between bounds-range checked,
>>    unchecked, modulo, or saturating data types
>
> Ada allows range checked, i.e. Range 20-100, unchecked, at least within
> the limits of the size, and Modulo variables.

Yes. But "unchecked" is not required; there are pragmas to _permit_ the
Ada compiler to omit the range checks and overflow checks locally or
globally, but the compiler does not have to obey them. The intent of
these pragmas is that the programmer knows that the checks would not
fail, and therefore they can be omitted. The intent is not to get some
specific behaviour on range violation or overflow.

> I suspect adding saturated wouldn't be a big stretch if it were
> popular enough.

I agree.

The next Ada standard, now in final editorial review in ISO WG9, will
also have standard libraries for "big numbers", that is, numbers with
unbounded range and precision, both integer and real. These libraries of
course provide the usual infix and prefix operators, so you can write
I+J even for big-integers I and J.

I suspect that saturating arithmetic would be added in the same way, as
standard libraries rather than as a new core feature of the Ada type system.

>> - specify that range and array bounds checks can be enabled or disabled
>>    at compile time by command line options or inline pragmas,
>>    for blocks of code, individual data types, or individual objects.
>
> Since Ada supports Range attributes, and you can use a range restricted
> variable as a subscript or loop limit, I think you can do all of that.

Yes, but see the note on check-disabling pragmas above.

> But Nick Holsti is the Ada expert around here, so perhaps he will chime in.

You got it right, Stephen.