Brian G. Lucas <bagel99@gmail.com> schrieb:
> On 5/17/21 10:45 AM, Thomas Koenig wrote:

[...]

>> unsigned int foo(unsigned int *a, int n)
>> {
>> int i;
>> unsigned int res = 0;
>> for (i=0; i<n; i++)
>> res += a[i];
>>
>> return res;
>> }

> The compiler is currently based on LLVM 9. There is no mask in the loop.

So, at least there's that.

> (I do wish that the loop counter and limit were "unsigned", but that also
> seems to be a problem with legacy code.)

Unsigned loops can cause a headache, because it is often
not possible to prove they actually terminate...

>However, there is some other
> stupidness in the compiled code (compiled without VVM enabled:
> foo: ; @foo
> sra r3,r2,<32:0>
> cmp r3,r3,#1
> blt r3,.LBB0_1
> srl r3,r2,<32:0>
> mov r2,#0
> .LBB0_3: ; =>This Inner Loop Header: Depth=1
> lduw r4,[r1]
> add r2,r4,r2
> add r3,r3,#-1
> add r1,r1,#4
> bne0 r3,.LBB0_3
> mov r1,r2
> ret
> .LBB0_1:
> mov r2,#0
> mov r1,r2
> ret

A few points that I notice here.

There does not seem to be a mask added to the result at all.
Is this correct code for this platform to return the extra
bits in case of overflow? This seems to contradict what
Mitch wrote earlier.

A minor thing - why not use r1 from the start for the sum? The two
"mov r1,r2" instructions should be eliminated. Possibly, the
function epilogue is added too late for register allocation.

The other point I am not sure about. On x86_64 with gcc
with "-O2 -funroll-loops", the inner loop is compiled to

..L3:
addl (%rdi), %eax
addq $4, %rdi
cmpq %rdx, %rdi
jne .L3

where %rdx has been set up previously as the upper limit.

On a load-store architecture, the first addl would of course
be a load to a register, followed by the add.

IIRC, My 66000 has no condition registers. Unless it
has a "branch if two registers are equal" instruction,
then precomputing the upper limit probably does not
offer any advantages, is that correct?

On Tuesday, May 18, 2021 at 1:36:43 AM UTC-5, Thomas Koenig wrote:
> Brian G. Lucas <bag...@gmail.com> schrieb:
> > On 5/17/21 10:45 AM, Thomas Koenig wrote:
> [...]
> >> unsigned int foo(unsigned int *a, int n)
> >> {
> >> int i;
> >> unsigned int res = 0;
> >> for (i=0; i<n; i++)
> >> res += a[i];
> >>
> >> return res;
> >> }
> > The compiler is currently based on LLVM 9. There is no mask in the loop.
> So, at least there's that.
> > (I do wish that the loop counter and limit were "unsigned", but that also
> > seems to be a problem with legacy code.)
> Unsigned loops can cause a headache, because it is often
> not possible to prove they actually terminate...
> >However, there is some other
> > stupidness in the compiled code (compiled without VVM enabled:
> > foo: ; @foo
> > sra r3,r2,<32:0>
> > cmp r3,r3,#1
> > blt r3,.LBB0_1
> > srl r3,r2,<32:0>
> > mov r2,#0
> > .LBB0_3: ; =>This Inner Loop Header: Depth=1
> > lduw r4,[r1]
> > add r2,r4,r2
> > add r3,r3,#-1
> > add r1,r1,#4
> > bne0 r3,.LBB0_3
> > mov r1,r2
> > ret
> > .LBB0_1:
> > mov r2,#0
> > mov r1,r2
> > ret
> A few points that I notice here.
>
> There does not seem to be a mask added to the result at all.
> Is this correct code for this platform to return the extra
> bits in case of overflow? This seems to contradict what
> Mitch wrote earlier.
<
Yes, now I don't understand when LLVM does its smashes !?!
and when it "lets them slide".
>
> A minor thing - why not use r1 from the start for the sum? The two
> "mov r1,r2" instructions should be eliminated. Possibly, the
> function epilogue is added too late for register allocation.
<
Notice that R1 arrives pointing at the array and that R1 leaves
with the return value. So you only end up trading the MOV at the
end for a different MOV at the beginning.
>
> The other point I am not sure about. On x86_64 with gcc
> with "-O2 -funroll-loops", the inner loop is compiled to
>
> .L3:
> addl (%rdi), %eax
> addq $4, %rdi
> cmpq %rdx, %rdi
> jne .L3
>
> where %rdx has been set up previously as the upper limit.
>
> On a load-store architecture, the first addl would of course
> be a load to a register, followed by the add.
>
> IIRC, My 66000 has no condition registers. Unless it
> has a "branch if two registers are equal" instruction,
> then precomputing the upper limit probably does not
> offer any advantages, is that correct?
<
By converting the loop from up counting to down counting
one can end up with a compare-to-zero and a branch in one
instruction. This takes a CMP out of the loop.
<
But the think I don't see is why the compiler did not use the
LDUW R4,[R1+R3<<2] form available and eliminate one of
the ADDs.

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.

- 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:
> 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.

I could quote you chapter and verse from the Fortran standard, but
I hope you'll take my word for it. But then again, the Fortran
standard was probably written by evil benchmarkers :-)

On 5/18/21 1:36 AM, Thomas Koenig wrote:
> Brian G. Lucas <bagel99@gmail.com> schrieb:
>> On 5/17/21 10:45 AM, Thomas Koenig wrote:
>
> [...]
>
>>> unsigned int foo(unsigned int *a, int n)
>>> {
>>> int i;
>>> unsigned int res = 0;
>>> for (i=0; i<n; i++)
>>> res += a[i];
>>>
>>> return res;
>>> }
>
>> The compiler is currently based on LLVM 9. There is no mask in the loop.
>
> So, at least there's that.
>
>> (I do wish that the loop counter and limit were "unsigned", but that also
>> seems to be a problem with legacy code.)
>
> Unsigned loops can cause a headache, because it is often
> not possible to prove they actually terminate...
>
>> However, there is some other
>> stupidness in the compiled code (compiled without VVM enabled:
>> foo: ; @foo
>> sra r3,r2,<32:0>
>> cmp r3,r3,#1
>> blt r3,.LBB0_1
>> srl r3,r2,<32:0>
>> mov r2,#0
>> .LBB0_3: ; =>This Inner Loop Header: Depth=1
>> lduw r4,[r1]
>> add r2,r4,r2
>> add r3,r3,#-1
>> add r1,r1,#4
>> bne0 r3,.LBB0_3
>> mov r1,r2
>> ret
>> .LBB0_1:
>> mov r2,#0
>> mov r1,r2
>> ret
>
> A few points that I notice here.
>
> There does not seem to be a mask added to the result at all.
> Is this correct code for this platform to return the extra
> bits in case of overflow? This seems to contradict what
> Mitch wrote earlier.
>

This must be a bug. I'll look into it.

brian

On 5/17/21 7:43 AM, Anton Ertl wrote:
> Thomas Koenig <tkoenig@netcologne.de> writes:
> [Extension woes:]
>> There is an implicit assumption that people who use the default
>> types in languages like C or Fortran get code that is not
>> sub-optimal. This violates that assumption.
>
> Choosing a 32-bit default type on a 64-bit machine is unwise.
>
> But it's interesting how stuff was adapted to this decision (of using
> I32LP64 for C on 64-bit machines):
>
So, on a machine such as My66000, in which all ALU operations are 64-bit, we
should choose ILP64 as a model? Do you know of any other architectures that
have made that choice? Are their any downsides?

brian
> C defines modulo arithmetic for unsigned overflow, but not for signed
> overflow, so instead of sign-extending the result, some people got the
> idea to pretend that overflows don't happen, and "optimize" the
> sign-extension away.
>
> For unsigned numbers, C is defined, and apparently important enough to
> merit architectural workarounds for this problem: AMD64 and Aarch64
> include 32-bit instructions that zero-extend their results (and on
> AMD64 the 32-bit versions can sometimes be encoded with fewer bytes),
> but no sign-extending variant of the 32-bit instructions; at first I
> wondered about that, but now I think that this is because the
> sign-extending variants would not provide a benefit in benchmarketing
> given C compilers that "optimize" as described above.
>
> By contrast, Alpha has only sign-extending versions of 32-bit ALU
> instructions instructions, AFAIK mainly to make porting VAX software
> easier.
>
> - anton
>

Brian G. Lucas <bagel99@gmail.com> schrieb:
> On 5/17/21 7:43 AM, Anton Ertl wrote:
>> Thomas Koenig <tkoenig@netcologne.de> writes:
>> [Extension woes:]
>>> There is an implicit assumption that people who use the default
>>> types in languages like C or Fortran get code that is not
>>> sub-optimal. This violates that assumption.
>>
>> Choosing a 32-bit default type on a 64-bit machine is unwise.
>>
>> But it's interesting how stuff was adapted to this decision (of using
>> I32LP64 for C on 64-bit machines):
>>
> So, on a machine such as My66000, in which all ALU operations are 64-bit, we
> should choose ILP64 as a model? Do you know of any other architectures that
> have made that choice? Are their any downsides?

The obvious downside is memory requirements, especially regarding
caches - they will fill up twice as fast if most of your variables
are twice as big.

Brian G. Lucas <bagel99@gmail.com> schrieb:
> On 5/18/21 1:36 AM, Thomas Koenig wrote:

>> There does not seem to be a mask added to the result at all.
>> Is this correct code for this platform to return the extra
>> bits in case of overflow? This seems to contradict what
>> Mitch wrote earlier.
>>
>
> This must be a bug. I'll look into it.

That's one thing I love about discussions such as this. So far,
we have gotten one gcc bug report and one bug for your special
architecture out of it. Keep it going, folks :-)

On 5/18/21 12:48 PM, Thomas Koenig wrote:
> Brian G. Lucas <bagel99@gmail.com> schrieb:
>> On 5/17/21 7:43 AM, Anton Ertl wrote:
>>> Thomas Koenig <tkoenig@netcologne.de> writes:
>>> [Extension woes:]
>>>> There is an implicit assumption that people who use the default
>>>> types in languages like C or Fortran get code that is not
>>>> sub-optimal. This violates that assumption.
>>>
>>> Choosing a 32-bit default type on a 64-bit machine is unwise.
>>>
>>> But it's interesting how stuff was adapted to this decision (of using
>>> I32LP64 for C on 64-bit machines):
>>>
>> So, on a machine such as My66000, in which all ALU operations are 64-bit, we
>> should choose ILP64 as a model? Do you know of any other architectures that
>> have made that choice? Are their any downsides?
>
> The obvious downside is memory requirements, especially regarding
> caches - they will fill up twice as fast if most of your variables
> are twice as big.
>
Yep, that's true. Perhaps C programmers will start to use stdint.h more so
variables in memory can be int32_t instead of just int. Sigh.

brian

On Tuesday, May 18, 2021 at 11:39:49 AM UTC-5, Anton Ertl wrote:
> 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.
<
Signed calculations that overflow raise exceptions in My 66000.
<
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

On Tuesday, May 18, 2021 at 11:56:25 AM UTC-5, Thomas Koenig wrote:
> 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.
>
> I could quote you chapter and verse from the Fortran standard, but
> I hope you'll take my word for it. But then again, the Fortran
> standard was probably written by evil benchmarkers :-)
<
FORTRAN loops can have the trip count determined before the loop
begins and count to that number of iterations.

C loops do not have that property.

MitchAlsup <MitchAlsup@aol.com> schrieb:
> On Tuesday, May 18, 2021 at 1:36:43 AM UTC-5, Thomas Koenig wrote:

[assembler code a few level of quotations up]

>> > foo: ; @foo
>> > sra r3,r2,<32:0>
>> > cmp r3,r3,#1
>> > blt r3,.LBB0_1
>> > srl r3,r2,<32:0>
>> > mov r2,#0
>> > .LBB0_3: ; =>This Inner Loop Header: Depth=1
>> > lduw r4,[r1]
>> > add r2,r4,r2
>> > add r3,r3,#-1
>> > add r1,r1,#4
>> > bne0 r3,.LBB0_3
>> > mov r1,r2
>> > ret
>> > .LBB0_1:
>> > mov r2,#0
>> > mov r1,r2
>> > ret

>> The other point I am not sure about. On x86_64 with gcc
>> with "-O2 -funroll-loops", the inner loop is compiled to
>>
>> .L3:
>> addl (%rdi), %eax
>> addq $4, %rdi
>> cmpq %rdx, %rdi
>> jne .L3
>>
>> where %rdx has been set up previously as the upper limit.
>>
>> On a load-store architecture, the first addl would of course
>> be a load to a register, followed by the add.
>>
>> IIRC, My 66000 has no condition registers. Unless it
>> has a "branch if two registers are equal" instruction,
>> then precomputing the upper limit probably does not
>> offer any advantages, is that correct?
><
> By converting the loop from up counting to down counting
> one can end up with a compare-to-zero and a branch in one
> instruction. This takes a CMP out of the loop.

That makes sense. As a matter of fact, that is something I've
wanted for gcc since 2005, as evidenced by PR 22041 :-)

> But the think I don't see is why the compiler did not use the
> LDUW R4,[R1+R3<<2] form available and eliminate one of
> the ADDs.

That would have required reversal of the loop access, which is not
something that compilers do lightly in a basically serial language
like C.

Hmm.. come to think of it, this could be a reason for an addressing
mode for something like

LDUW R4,[R1-R3<<2]

so set up one register to pointing one past the end of the array
and then (if I get your assembler correct)

label:
LDUW R4,[R1-R3<<2]
ADD R2,R4,R2
ADD R3,-1
BNE0 R3,label

which would save an instruction without reversing the loop.

MitchAlsup <MitchAlsup@aol.com> schrieb:
> On Tuesday, May 18, 2021 at 11:56:25 AM UTC-5, Thomas Koenig wrote:
>> 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.
>>
>> I could quote you chapter and verse from the Fortran standard, but
>> I hope you'll take my word for it. But then again, the Fortran
>> standard was probably written by evil benchmarkers :-)
><
> FORTRAN loops can have the trip count determined before the loop
> begins and count to that number of iterations.
>
> C loops do not have that property.

Your statement is correct for a simple DO loop in Fortran.

C loops do not have that property in general. By inspecting the
loop, a compiler can sometimes determine the number of loops.

And you can also write Fortran DO loops where this is not
possible - it is legal to branch out (plus, since F90,
Fortran has the equivalent of C's while loops).

Brian G. Lucas [2021-05-18 12:11:27] wrote:
> On 5/17/21 7:43 AM, Anton Ertl wrote:
>> Thomas Koenig <tkoenig@netcologne.de> writes:
>> [Extension woes:]
>>> There is an implicit assumption that people who use the default
>>> types in languages like C or Fortran get code that is not
>>> sub-optimal. This violates that assumption.
>> Choosing a 32-bit default type on a 64-bit machine is unwise.
>> But it's interesting how stuff was adapted to this decision (of using
>> I32LP64 for C on 64-bit machines):
> So, on a machine such as My66000, in which all ALU operations are 64-bit, we
> should choose ILP64 as a model? Do you know of any other architectures that
> have made that choice?

According to https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models,
HAL's port of Solaris to SPARC64 used ILP64.
Of course, the Crays pushed this yet further and used
64bit for the char type as well.

LP64 and LLP64 seem a lot more popular.

Stefan

On Tuesday, May 18, 2021 at 1:50:17 PM UTC-5, Thomas Koenig wrote:
> MitchAlsup <Mitch...@aol.com> schrieb:
> > On Tuesday, May 18, 2021 at 11:56:25 AM UTC-5, Thomas Koenig wrote:
> >> 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.
> >>
> >> I could quote you chapter and verse from the Fortran standard, but
> >> I hope you'll take my word for it. But then again, the Fortran
> >> standard was probably written by evil benchmarkers :-)
> ><
> > FORTRAN loops can have the trip count determined before the loop
> > begins and count to that number of iterations.
> >
> > C loops do not have that property.
> Your statement is correct for a simple DO loop in Fortran.
>
> C loops do not have that property in general. By inspecting the
> loop, a compiler can sometimes determine the number of loops.
>
> And you can also write Fortran DO loops where this is not
> possible - it is legal to branch out (plus, since F90,
> Fortran has the equivalent of C's while loops).
<
One could always goto or return out of FORTRAN DO loops from
at least FORTRAN II time period.

"Brian G. Lucas" <bagel99@gmail.com> writes:
>On 5/17/21 7:43 AM, Anton Ertl wrote:
>> Thomas Koenig <tkoenig@netcologne.de> writes:
>> [Extension woes:]
>>> There is an implicit assumption that people who use the default
>>> types in languages like C or Fortran get code that is not
>>> sub-optimal. This violates that assumption.
>>
>> Choosing a 32-bit default type on a 64-bit machine is unwise.
>>
>> But it's interesting how stuff was adapted to this decision (of using
>> I32LP64 for C on 64-bit machines):
>>
>So, on a machine such as My66000, in which all ALU operations are 64-bit, we
>should choose ILP64 as a model?

Yes, and on all others.

>Do you know of any other architectures that
>have made that choice?

Cray

>Are their any downsides?

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.

In C you would need something like "long short" to cover both 16-bit
and 32-bit sizes (int16_t and int32_t are typically defined in terms
of keyword-based types).

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

On 5/18/2021 11:43 AM, MitchAlsup wrote:
> On Tuesday, May 18, 2021 at 11:39:49 AM UTC-5, Anton Ertl wrote:
>> 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.
> <
> Signed calculations that overflow raise exceptions in My 66000.
> <

Or saturate, or wrap, or produce double-width result, your choice, in Mill.

MitchAlsup <MitchAlsup@aol.com> schrieb:
> On Tuesday, May 18, 2021 at 11:39:49 AM UTC-5, Anton Ertl wrote:
>> 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.
><
> Signed calculations that overflow raise exceptions in My 66000.

Does that also happen for signed calculations smaller than the
register width (specifically, with a 32-bit int?)

If so, count me in for the first model of your architecture
that is delivered to customers, unless the price is way
above my league.

On 5/18/2021 10:49 PM, Thomas Koenig wrote:
> MitchAlsup <MitchAlsup@aol.com> schrieb:
>> On Tuesday, May 18, 2021 at 11:39:49 AM UTC-5, Anton Ertl wrote:
>>> 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.
>> <
>> Signed calculations that overflow raise exceptions in My 66000.
>
> Does that also happen for signed calculations smaller than the
> register width (specifically, with a 32-bit int?)
>
> If so, count me in for the first model of your architecture
> that is delivered to customers, unless the price is way
> above my league.
>

Yes for Mill. Mill scalar arithmetic is just lane zero of Mill SIMD
arithmetic, and the standard overflow detection and behavior (exception,
wrap, saturate, double-width result) apply to each lane and hence
automatically to scalars. Lanes of 8/16/32/64/128 bits are supported.
Each full-width ALU is able to break the carry chain at each 8-bit
portion, selected by the desired width; the logic required beyond that
of a monolithic full-width ALU is minor.

This seems like such an obvious thing to do that I have long wondered
why it hasn't been done many times before; instead designs duplicate the
SIMD and scalar engines. It's been suggested to me that it was an
encoding issue: not enough instruction bits available to also express
the desired width in the instruction. But I really don't know.

Ivan Godard <ivan@millcomputing.com> schrieb:
> On 5/18/2021 10:49 PM, Thomas Koenig wrote:
>> MitchAlsup <MitchAlsup@aol.com> schrieb:
>>> On Tuesday, May 18, 2021 at 11:39:49 AM UTC-5, Anton Ertl wrote:
>>>> 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.
>>> <
>>> Signed calculations that overflow raise exceptions in My 66000.
>>
>> Does that also happen for signed calculations smaller than the
>> register width (specifically, with a 32-bit int?)
>>
>> If so, count me in for the first model of your architecture
>> that is delivered to customers, unless the price is way
>> above my league.
>>
>
> Yes for Mill. Mill scalar arithmetic is just lane zero of Mill SIMD
> arithmetic, and the standard overflow detection and behavior (exception,
> wrap, saturate, double-width result) apply to each lane and hence
> automatically to scalars. Lanes of 8/16/32/64/128 bits are supported.
> Each full-width ALU is able to break the carry chain at each 8-bit
> portion, selected by the desired width; the logic required beyond that
> of a monolithic full-width ALU is minor.

That sounds excellent. As soon as you have an affordable system on
the market, count me in. (As a reference: My son runs a Talos II
POWER machine, for which he ordered mainbord, CPU and memory from
the US).

> This seems like such an obvious thing to do that I have long wondered
> why it hasn't been done many times before; instead designs duplicate the
> SIMD and scalar engines. It's been suggested to me that it was an
> encoding issue: not enough instruction bits available to also express
> the desired width in the instruction. But I really don't know.

POWER has a 32-bit carry and overflow bits, IIRC. If you wanted
separate bits for everything from unsigned (no overflow) up to 64
or 128 bits, you would have five or six possibilities, so three
instruction bits. That can be a lot.

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?

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; well, a C compiler might "optimize" the int loop into
anything, but my experience is that gcc tends towards "optimizing"
intended-to-be-bounded loops into endless loops, not the reverse.

You can extend this example into one where the loop terminates, but
the compiler cannot prove it for the unsigned case, while it uses the
same nonsense "proof" for the signed case.

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

MitchAlsup <MitchAlsup@aol.com> writes:
>Signed calculations that overflow raise exceptions in My 66000.

So does add and sub on MIPS, and addv, subv, and mulv on Alpha. No C
compiler has dared to use these instructions for signed addition in C
by default (and I read that gcc -trapv does not work properly, not
that I have tried).

There is no market for such instructions. Witness the fact that Alpha
has been killed, and MIPS is struggling. These ISAs have trapping
instructions, but nobody chooses them for these instructions and
nobody uses these instructions. RISC-V, the spiritual descendent of
MIPS, turned add and sub into non-trapping instructions (i.e., MIPS
addu became RISC-V add, with no replacement for MIPS add).

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

On Wednesday, May 19, 2021 at 12:49:34 AM UTC-5, Thomas Koenig wrote:
> MitchAlsup <Mitch...@aol.com> schrieb:
> > On Tuesday, May 18, 2021 at 11:39:49 AM UTC-5, Anton Ertl wrote:
> >> 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.
> ><
> > Signed calculations that overflow raise exceptions in My 66000.
<
> Does that also happen for signed calculations smaller than the
> register width (specifically, with a 32-bit int?)
<
All calculations are 64-bit.
>
> If so, count me in for the first model of your architecture
> that is delivered to customers, unless the price is way
> above my league.
<
Price is not for me to decide. For my part the IP is essentially free.

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.
<
> >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.
>
> 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.
<
It may theoretically terminate, but it may not terminate in the lifetime
the earth has left.
>
> 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
and the unsigned version does not. It seems to me that the container for
both cases contains the same number of states.
<
> well, a C compiler might "optimize" the int loop into
> anything, but my experience is that gcc tends towards "optimizing"
> intended-to-be-bounded loops into endless loops, not the reverse.
>
> You can extend this example into one where the loop terminates, but
> the compiler cannot prove it for the unsigned case, while it uses the
> same nonsense "proof" for the signed case.
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

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
- 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.

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