Quadibloc <jsavard@ecn.ab.ca> writes:
>On Wednesday, November 3, 2021 at 10:45:53 AM UTC-6, David Brown wrote:
>> Given your past history, you
>> might find it useful to use a pseudonym.
>
>Um, that wouldn't help.
>
>The issue about which Anton Ertl is concerned is... one that a *lot* of
>people are concerned about.
....
>Basically, the question of whether C should embrace the future, or stay
>compatible with K&R C,

But that's not at all the issue I am concerned with.

The issue is: If a program has been tested and works on one or several
versions of a C compiler, and it does not work on a new version of the
same compiler on the same architecture(s), is it a regression in the
compiler (my position), or has the program been broken all the time,
and the earlier compiler releases were just not advanced enough to
expose this brokenness earlier.

>Since the other side has already won, C99 being an official standard
>and all that, I think that forking gcc is the only reasonable measure
>available at this late date.

Providing a saner alternative to gcc and clang may indeed be the
answer. However, gcc (and clang) are complex and by now nasal demons
have grown deep and intricate roots in the vast source code of these
projects, so basing the alternative of gcc or clang is probably not
the most effective approach.

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

> My position is basically that a responsible maintainer for a
> widely-used compiler does not break existing source code

Question: You mentioned tail call optimization in one of
your posts.

Should compilers be mandated to copy arguments for

int bar (int a, int b, int c);

int foo(int a, int b, int c)
{ if (a > 0)
return bar(a,b,c);
else
return -1;
}

?

On 04/11/2021 18:27, Anton Ertl wrote:
> Quadibloc <jsavard@ecn.ab.ca> writes:
>> On Wednesday, November 3, 2021 at 10:45:53 AM UTC-6, David Brown wrote:
>>> Given your past history, you
>>> might find it useful to use a pseudonym.
>>
>> Um, that wouldn't help.
>>
>> The issue about which Anton Ertl is concerned is... one that a *lot* of
>> people are concerned about.
> ...
>> Basically, the question of whether C should embrace the future, or stay
>> compatible with K&R C,
>
> But that's not at all the issue I am concerned with.
>
> The issue is: If a program has been tested and works on one or several
> versions of a C compiler, and it does not work on a new version of the
> same compiler on the same architecture(s), is it a regression in the
> compiler (my position), or has the program been broken all the time,
> and the earlier compiler releases were just not advanced enough to
> expose this brokenness earlier.
>

You cannot possibly justify that position as a generality. Should
compilers enforce bug-for-bug compatibility in the event that an error
is found in the previous version of the compiler? Should a new compiler
be unable to add new features or extensions within the reserved
namespace, just because someone has previously written code that defined
their own macro named _Static_assert or their own function named
__builtin__memset ?

I know that's not what you were thinking of - but that is what you said.
This is why I am so strongly against your ideas about consistency and
undefined behaviour - your statements are so sweeping that they cover
things that are clearly ridiculous. If you want to pick /specific/
classes of UB and give /specific/ definitions to how you want those to
behave, then we can get somewhere. I might not agree that the new
semantics you pick are an improvement (or not an improvement for my own
use), but I will happily appreciate that people might want to add new
semantics to the language.

On Thursday, November 4, 2021 at 1:22:50 PM UTC-5, Thomas Koenig wrote:
> Anton Ertl <an...@mips.complang.tuwien.ac.at> schrieb:
> > My position is basically that a responsible maintainer for a
> > widely-used compiler does not break existing source code
> Question: You mentioned tail call optimization in one of
> your posts.
>
> Should compilers be mandated to copy arguments for
>
> int bar (int a, int b, int c);
>
> int foo(int a, int b, int c)
> {
> if (a > 0)
> return bar(a,b,c);
> else
> return -1;
> }
>
My 66000
<
GLOBAL foo
ENTRY foo
foo:
PEQ0 R1,{3,{TEE}} // {1,{T}} and {2,{TE} also work.
JMP bar
MOV R1,#-1
RET
<
Since arguments are passed in registers, the simple JMP "copies" the
arguments forward. no stack frame is built, and the control transfer to
bar takes with it the return address from foo.
> ?

On Thursday, November 4, 2021 at 4:19:08 PM UTC-5, David Brown wrote:
> On 04/11/2021 18:27, Anton Ertl wrote:
> > Quadibloc <jsa...@ecn.ab.ca> writes:
> >> On Wednesday, November 3, 2021 at 10:45:53 AM UTC-6, David Brown wrote:
> >>> Given your past history, you
> >>> might find it useful to use a pseudonym.
> >>
> >> Um, that wouldn't help.
> >>
> >> The issue about which Anton Ertl is concerned is... one that a *lot* of
> >> people are concerned about.
> > ...
> >> Basically, the question of whether C should embrace the future, or stay
> >> compatible with K&R C,
> >
> > But that's not at all the issue I am concerned with.
> >
> > The issue is: If a program has been tested and works on one or several
> > versions of a C compiler, and it does not work on a new version of the
> > same compiler on the same architecture(s), is it a regression in the
> > compiler (my position), or has the program been broken all the time,
> > and the earlier compiler releases were just not advanced enough to
> > expose this brokenness earlier.
> >
> You cannot possibly justify that position as a generality. Should
> compilers enforce bug-for-bug compatibility in the event that an error
> is found in the previous version of the compiler? Should a new compiler
> be unable to add new features or extensions within the reserved
> namespace, just because someone has previously written code that defined
> their own macro named _Static_assert or their own function named
> __builtin__memset ?
<
I actually lived though such an example, but with a CAD tool.
<
After using a particular CAD tool for several years, we knew where most
of the nasal deamons lived, and wrote code so as to avoid those. The tool
supplied wanted to migrate the whole team forward, but when tested on
our working {makes reliable tapeouts for mask manufacturing} the new
crashed and burned. In effect, tool vendor wanted us to pay big-$$$ for
a tool that would cost us big $$$ to update the current (and working)
data bases of our parts.
<
We said no.
<
In addition, the new tool only ran on SOLARIS while the old tool ran on
SUN-O/S and had "a much more user friendly licensing system".
<
{Circa 1994}
>
> I know that's not what you were thinking of - but that is what you said.
> This is why I am so strongly against your ideas about consistency and
> undefined behaviour - your statements are so sweeping that they cover
> things that are clearly ridiculous. If you want to pick /specific/
> classes of UB and give /specific/ definitions to how you want those to
> behave, then we can get somewhere. I might not agree that the new
> semantics you pick are an improvement (or not an improvement for my own
> use), but I will happily appreciate that people might want to add new
> semantics to the language.
<
From the comp.arch layer of understanding::
<
What is it that ISAs can do to minimize the space of UB ?

MitchAlsup <MitchAlsup@aol.com> schrieb:

> From the comp.arch layer of understanding::
><
> What is it that ISAs can do to minimize the space of UB ?

We have discussed part of this before, but here is a bit
of an expansion (and some repetition).

There are tools to find undefined behavior (or erroneous programs),
ranging from sanitizers (which add a low factor to execution time,
maybe two or so) to really heavy-handed tools like valgrind which
find a _lot_ of errors while making the code run abysmally slow.

Think of ways that an ISA could be designed to speed up those tests.
Zero overhead is almost certainly unreachable, but even reducing
the speed overhead of checked code would help a lot.

Going through the CERT coding standards, look for what can
be implemented either efficiently or at zero cost. An example:

5.1 INT30-C. Ensure that unsigned integer operations do not wrap.

Integer values must not be allowed to wrap, especially if they
are used in any of the following ways:

* Integer operands of any pointer arithmetic, including array
indexing

* The assignment expression for the declaration of a variable
length array

* The postfix expression preceding square brackets [] or the
expression in square brackets [] of a subscripted designation of
an element of an array object

* Function arguments of type size_t or rsize_t (for example,
an argument to a memory allocation function)

* In security-critical code

and they give the following example as a compliant solution:

void func(unsigned int ui_a, unsigned int ui_b) {
unsigned int usum;
if (UINT_MAX - ui_a < ui_b) {
/* Handle error */
} else {
usum = ui_a + ui_b;
}
/* ... */
}

Also of interest are the chapters regarding arrays, characters
and strings and memory management.

In an ideal world, all checks would be zero overhead, so everybody
would run every check all the time. Not likely to happen, though :-)

MitchAlsup <MitchAlsup@aol.com> writes:
>From the comp.arch layer of understanding::
><
>What is it that ISAs can do to minimize the space of UB ?

Not sure what you mean by that, but let me answer "What can in ISA do
to make UB attractive (or less so)."

The major reason why some people find undefined behaviour on integer
overflow so attractive is the fact that the decision to go with
I32LP64 requires sign-extending here and there with -fwrapv, e.g., with
loops like

for (int i=0; i<n; i++)
r+=a[i];

The address of a is 64 bits, but i is a signed 32-bit value, and needs
to be sign-extended with -fwrapv when forming a+i on every iteration
of the loop. If the instruction generated for i++ sign-extends (like
Alpha's addl, but then Alpha have a similar problem if i was defined
as unsigned; so we would need both sign-extending and zero-extending
variants), you don't need to sign-extend with an extra intruction.
Alternatively, if the address computation supports sign-extended
32-bit arguments (IIRC Aarch64 has such addressing modes), this is
another way of avoiding the extra instruction. Finally,
sign-extension instructions could be made zero-cost in implementations
(like zero-extending is in some implementations), this might also
reduce the attraction (but I guess that the effect would be smaller,
because an instruction always has a psychological cost.

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

On Thursday, November 4, 2021 at 6:21:39 PM UTC-5, Anton Ertl wrote:
> MitchAlsup <Mitch...@aol.com> writes:
> >From the comp.arch layer of understanding::
> ><
> >What is it that ISAs can do to minimize the space of UB ?
> Not sure what you mean by that, but let me answer "What can in ISA do
> to make UB attractive (or less so)."
>
> The major reason why some people find undefined behaviour on integer
> overflow so attractive is the fact that the decision to go with
> I32LP64 requires sign-extending here and there with -fwrapv, e.g., with
> loops like
>
> for (int i=0; i<n; i++)
> r+=a[i];
>
> The address of a is 64 bits, but i is a signed 32-bit value, and needs
> to be sign-extended with -fwrapv when forming a+i on every iteration
> of the loop.
<
For a new ISA, why would anyone go with I32LP64 why not ILP64 ?
<
But why can 'n' not be checked for being "too big" before running the loop
and avoid all of the a+i checking "in the loop". Here, the check seems easy
enough (n>=0):: but it seems the real problem is that there is nothing close
to the loop supplying the bounds for a[] !!?!
<
> If the instruction generated for i++ sign-extends (like
> Alpha's addl, but then Alpha have a similar problem if i was defined
> as unsigned; so we would need both sign-extending and zero-extending
> variants), you don't need to sign-extend with an extra intruction.
<
In I32LP64 codes, Brian's My 66000 C compiler spits out copious
quantities of EXT Rx,Rx,<31:0> // extract the lower 32 bits and sign
extend.
<
> Alternatively, if the address computation supports sign-extended
> 32-bit arguments (IIRC Aarch64 has such addressing modes), this is
> another way of avoiding the extra instruction. Finally,
> sign-extension instructions could be made zero-cost in implementations
> (like zero-extending is in some implementations), this might also
> reduce the attraction (but I guess that the effect would be smaller,
> because an instruction always has a psychological cost.
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>
<
But I was wondering more about doing things like::
<
int a >> int b; // where b is allowed to be negative
int a << int b; // where b is allowed to be negative
<
And when a shift count is negative, the shift is performed in the "other" direction.

On Thursday, November 4, 2021 at 5:23:25 PM UTC-5, Thomas Koenig wrote:
> MitchAlsup <Mitch...@aol.com> schrieb:
> > From the comp.arch layer of understanding::
> ><
> > What is it that ISAs can do to minimize the space of UB ?
> We have discussed part of this before, but here is a bit
> of an expansion (and some repetition).
>
> There are tools to find undefined behavior (or erroneous programs),
> ranging from sanitizers (which add a low factor to execution time,
> maybe two or so) to really heavy-handed tools like valgrind which
> find a _lot_ of errors while making the code run abysmally slow.
>
> Think of ways that an ISA could be designed to speed up those tests.
> Zero overhead is almost certainly unreachable, but even reducing
> the speed overhead of checked code would help a lot.
>
> Going through the CERT coding standards, look for what can
> be implemented either efficiently or at zero cost. An example:
>
> 5.1 INT30-C. Ensure that unsigned integer operations do not wrap.
<
unsigned integers are the only integral format that has well defined
overflow characteristics == wrap. Why eliminate all wraps on the
only format that actually wraps correctly ?
<
For example: how does one check that
<
unsigned i = unsigned j -1
<
is different from:
<
unsigned i = unsigned j + 0xFFFFFFFFFFFFFFFFu
<
One is subtracting a very tiny negative number from j, the other is adding
a huge number to j that happens to have the same bit pattern as the tiny
subtrahend.
<
And why would one care ?
<
>
> Integer values must not be allowed to wrap, especially if they
> are used in any of the following ways:
<
signed integers are OVERFLOW checked.
conversions to signed integers are significance checked.
Should STs check significance in the parts that are not stored ?
>
> * Integer operands of any pointer arithmetic, including array
> indexing
<
AGEN exception or OVERFLOW exception depending on the instruction
at hand.
>
> * The assignment expression for the declaration of a variable
> length array
>
> * The postfix expression preceding square brackets [] or the
> expression in square brackets [] of a subscripted designation of
> an element of an array object
<
a+i is not allowed to OVERFLOW | AGEN:: check
>
> * Function arguments of type size_t or rsize_t (for example,
> an argument to a memory allocation function)
>
> * In security-critical code
>
> and they give the following example as a compliant solution:
>
> void func(unsigned int ui_a, unsigned int ui_b) {
> unsigned int usum;
> if (UINT_MAX - ui_a < ui_b) {
> /* Handle error */
> } else {
> usum = ui_a + ui_b;
> }
> /* ... */
> }
<
This seems to be a language expression limitation
<
void func(unsigned int ui_a, unsigned int ui_b) {
unsigned int usum, hsum;
{ hsum, usum } = ui_a+ui_b;
if( hsum )
{ it overflowed }
else
{ golden }
} >
> Also of interest are the chapters regarding arrays, characters
> and strings and memory management.
>
> In an ideal world, all checks would be zero overhead, so everybody
> would run every check all the time. Not likely to happen, though :-)
<
Checks are only zero overhead if you have the checks built into the ISA
ala:: descriptor machines. These machines have proven so slow as to
select themselves out of the high performance marketplace.

On 11/4/2021 4:56 PM, MitchAlsup wrote:
> On Thursday, November 4, 2021 at 6:21:39 PM UTC-5, Anton Ertl wrote:
>> MitchAlsup <Mitch...@aol.com> writes:
>> >From the comp.arch layer of understanding::
>>> <
>>> What is it that ISAs can do to minimize the space of UB ?
>> Not sure what you mean by that, but let me answer "What can in ISA do
>> to make UB attractive (or less so)."
>>
>> The major reason why some people find undefined behaviour on integer
>> overflow so attractive is the fact that the decision to go with
>> I32LP64 requires sign-extending here and there with -fwrapv, e.g., with
>> loops like
>>
>> for (int i=0; i<n; i++)
>> r+=a[i];
>>
>> The address of a is 64 bits, but i is a signed 32-bit value, and needs
>> to be sign-extended with -fwrapv when forming a+i on every iteration
>> of the loop.
> <
> For a new ISA, why would anyone go with I32LP64 why not ILP64 ?

The Mill compiler is currently i32lp64 (though that may change). The
reason was data compatibility, primarily for arrays. There's a lot of
"int arr[n]" out there; "long arr[n]" not so much, and all the "foo *
[n]" have already been cleaned up in prior generations.

Sign and zero extending ops have almost been eliminated by Mill's
widening instructions (32 OP 32 -> 64 etc.) and mixed width address
arithmetic - remember Mill data has self-identifying width, so there's
no instruction explosion.

We decided a decade ago to set the clock at the 32-bit ALU boundary, and
rely on scheduling to hide the latency of 64 bit (and 128 bit)
instructions. They do hide quite well, but the HW state of the art has
progressed since that decision and probably it should be revisited; it's
a cheap change if warranted, as everything in there is spec driven anyway.

> <
> But why can 'n' not be checked for being "too big" before running the loop
> and avoid all of the a+i checking "in the loop". Here, the check seems easy
> enough (n>=0):: but it seems the real problem is that there is nothing close
> to the loop supplying the bounds for a[] !!?!
> <
>> If the instruction generated for i++ sign-extends (like
>> Alpha's addl, but then Alpha have a similar problem if i was defined
>> as unsigned; so we would need both sign-extending and zero-extending
>> variants), you don't need to sign-extend with an extra intruction.
> <
> In I32LP64 codes, Brian's My 66000 C compiler spits out copious
> quantities of EXT Rx,Rx,<31:0> // extract the lower 32 bits and sign
> extend.

About the only extend-type instructions we see are for code like
"int32_t a; int16_t b; a = b;" where people have used explicit irregular
sizes for API or memory reasons; they get "widen(...)" instructions. But
there phasing removes any cycle penalty:

load(@a); -> %load
....
widen(%load) -> %widen, store(@b, %widen);

So I assert that the business reasons for i32lp64 may be wrong, but
there's no technical reason not to use it in a new ISA.

Thomas Koenig wrote:
> MitchAlsup <MitchAlsup@aol.com> schrieb:
>
>> From the comp.arch layer of understanding::
>> <
>> What is it that ISAs can do to minimize the space of UB ?
>
> We have discussed part of this before, but here is a bit
> of an expansion (and some repetition).
>
> There are tools to find undefined behavior (or erroneous programs),
> ranging from sanitizers (which add a low factor to execution time,
> maybe two or so) to really heavy-handed tools like valgrind which
> find a _lot_ of errors while making the code run abysmally slow.
>
> Think of ways that an ISA could be designed to speed up those tests.
> Zero overhead is almost certainly unreachable, but even reducing
> the speed overhead of checked code would help a lot.
>
> Going through the CERT coding standards, look for what can
> be implemented either efficiently or at zero cost. An example:
>
> 5.1 INT30-C. Ensure that unsigned integer operations do not wrap.
>
> Integer values must not be allowed to wrap, especially if they
> are used in any of the following ways:
>
> * Integer operands of any pointer arithmetic, including array
> indexing
>
> * The assignment expression for the declaration of a variable
> length array
>
> * The postfix expression preceding square brackets [] or the
> expression in square brackets [] of a subscripted designation of
> an element of an array object
>
> * Function arguments of type size_t or rsize_t (for example,
> an argument to a memory allocation function)
>
> * In security-critical code

Those are all very reasonable.

>
> and they give the following example as a compliant solution:
>
> void func(unsigned int ui_a, unsigned int ui_b) {
> unsigned int usum;
> if (UINT_MAX - ui_a < ui_b) {
> /* Handle error */
> } else {
> usum = ui_a + ui_b;
> }
> /* ... */
> }

When you have already taken the trouble to make both arguments unsigned,
then I'd prefer to use a simpler form:

void func(unsigned int ui_a, unsigned int ui_b) {
unsigned int usum = ui_a + ui_b; // Can wrap but not fault
if (usum < ui_b) { // check for wrapping
/* Handle error */
}
/* do whatever with usum */
/* ... */
}

>
> Also of interest are the chapters regarding arrays, characters
> and strings and memory management.
>
> In an ideal world, all checks would be zero overhead, so everybody
> would run every check all the time. Not likely to happen, though :-)
>
Running checks everywhere except inside innermost loops, by first
verifying that the loop itself cannot fault, has very close to zero
actual overhead, as proven by modern Java/Kotlin/etc compilers.

(I'm not sure if Rust gives similar guarantees, but I believe you can
get the same effect there?)

Terje

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

MitchAlsup wrote:
> But I was wondering more about doing things like::
> <
> int a >> int b; // where b is allowed to be negative
> int a << int b; // where b is allowed to be negative
> <
> And when a shift count is negative, the shift is performed in the "other" direction.
>

I have been in that situation a few times, i.e. wanting/needing
potentially reverse shift direction, but it has always been possible to
bias my variables so as to make it unnecessary, with zero or
single-cycle overhead cost.

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

MitchAlsup <MitchAlsup@aol.com> writes:
>On Thursday, November 4, 2021 at 6:21:39 PM UTC-5, Anton Ertl wrote:
>> MitchAlsup <Mitch...@aol.com> writes:
>> >From the comp.arch layer of understanding::
>> ><
>> >What is it that ISAs can do to minimize the space of UB ?
>> Not sure what you mean by that, but let me answer "What can in ISA do
>> to make UB attractive (or less so)."
>>
>> The major reason why some people find undefined behaviour on integer
>> overflow so attractive is the fact that the decision to go with
>> I32LP64 requires sign-extending here and there with -fwrapv, e.g., with
>> loops like
>>
>> for (int i=0; i<n; i++)
>> r+=a[i];
>>
>> The address of a is 64 bits, but i is a signed 32-bit value, and needs
>> to be sign-extended with -fwrapv when forming a+i on every iteration
>> of the loop.
><
>For a new ISA, why would anyone go with I32LP64 why not ILP64 ?

Yes, indeed, although you should have asked (and maybe have asked) the
question 30 years ago when MIPS was extended to 64 bits and Alpha was
introduced. By now, I32LP64 is established, and everybody else (e.g.,
AMD in 2003, ARM and RISC-V in the 2010s) sticks to it to make it easy
to port existing software to the architecture. The cost is the large
number of sign and zero extends that is necessary in some form or
other (and some of the sign extends are "optimized" away by assuming
that signed overflow does not happen).

>But why can 'n' not be checked for being "too big" before running the loop
>and avoid all of the a+i checking "in the loop". Here, the check seems easy
>enough (n>=0):: but it seems the real problem is that there is nothing close
>to the loop supplying the bounds for a[] !!?!

Yes, it should be possible to make do with zero-extending here (which
AMD64 does for free). I looked up the example that [wang+12] gave:

int k;
int *ic, *is;
....
for(k = 1; k <= M; k++) {
...
ic[k] += is[k];
...
}

This is a loop from 456.hmmer, and both gcc and clang sign-extended k
after the k++ here if -fwrapv was used (and left away the sign
extension by default). Here, too, sign extension can be eliminated
without assuming that k++ does not overflow, by transforming the loop into:

for(k = 0; k < M; k++) {
...
(ic+1)[k] += (is+1)[k];
...
}

But back to your question: You can avoid burdening the compiler with
such optimizations or with assuming that overflow does not happen by
making the sign extension free.

>But I was wondering more about doing things like::
><
> int a >> int b; // where b is allowed to be negative
> int a << int b; // where b is allowed to be negative
><
>And when a shift count is negative, the shift is performed in the "other" direction.

I think divergent behaviour between architectures for instructions
that would be used for implementing a specific programming language
construct is one of the reasons for not defining behaviour (in
particular if one of the behaviours is to trap).

OTOH, convergent behaviour that programming language designers don't
want to specify (like "a << b" is equivalent to "a << (b&63)") is
another reason.

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

On 2021-11-04 19:58, Tim Rentsch wrote:
> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>>
>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>>
>>>>> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>>>>
>>>>>> Standard C is such a programming language; it only specifies
>>>>>> how "strictly conforming programs" should behave, [...]
>>>>>
>>>>> That statement is patently false.
>>>>
>>>> Please tell us where the C standard specifies how, e.g., the
>>>> following program should behave:
>>>>
>>>> int main() {
>>>> return 0;
>>>> }
>>>
>>> First let me ask a question. Do you think there's a difference
>>> between that program and this one:
>>>
>>> int main(void) {
>>> return 0;
>>> }
>>
>> I would not expect a difference, but in any case, the arguments of
>> main() are not the point of this example. Choose whatever arguments
>> you want to provide an answer for. The result is not a "strictly
>> conforming program" in any case, because it terminates.
>
> What makes you think strictly conforming programs cannot
> terminate?

Anton has not yet answered that, but I suspect that the reason is that a
strictly conforming program "shall not produce output dependent on any
unspecified, undefined, or _implementation-defined_ behavior", but when
the main() function returns 0, this is the same as calling exit(0),
which means that "control is returned to the host environment [with] an
_implementation-defined_ form of the status /successful termination/".
(Quotes from the C11 draft N1570, with my addition of emphasis.)

However, IMO, returning to the host environment is not "producing
output", so IMO it cannot violate the strict conformance rules. I think
the words "an implementation-defined form of" could be omitted from the
second quotation above; it would be enough for the C standard to specify
that a "successful termination" status is returned to the environment,
without saying anything about how that status is represented.

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>I looked up the example that [wang+12] gave:
>
>int k;
>int *ic, *is;
>...
>for(k = 1; k <= M; k++) {
> ...
> ic[k] += is[k];
> ...
>}
>
>This is a loop from 456.hmmer, and both gcc and clang sign-extended k
>after the k++ here if -fwrapv was used (and left away the sign
>extension by default).

BTW, this is the only place in SPECint 2006 where -fwrapv makes a
noticable differene [wang+12].

And here's the reference I forgot to include:

@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 = {}
}

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

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>>
>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>>
>>>>> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>>>>
>>>>>> Standard C is such a programming language; it only specifies
>>>>>> how "strictly conforming programs" should behave, [...]
>>>>>
>>>>> That statement is patently false.
>>>>
>>>> Please tell us where the C standard specifies how, e.g., the
>>>> following program should behave:
>>>>
>>>> int main() {
>>>> return 0;
>>>> }
>>>
>>> First let me ask a question. Do you think there's a difference
>>> between that program and this one:
>>>
>>> int main(void) {
>>> return 0;
>>> }
>>
>> I would not expect a difference, but in any case, the arguments of
>> main() are not the point of this example. Choose whatever arguments
>> you want to provide an answer for. The result is not a "strictly
>> conforming program" in any case, because it terminates.
>
>What makes you think strictly conforming programs cannot
>terminate?

7.22.4.4 in n1570 says:

|Finally, control is returned to the host environment. If the value of
|status is zero or EXIT_SUCCESS, an implementation-defined form of the
|status successful termination is returned. If the value of status is
|EXIT_FAILURE, an implementation-defined form of the status
|unsuccessful termination is returned. Otherwise the status returned
|is implementation-defined.

All other ways to terminate C programs eventually do this.

WRT my original statement, this means that the C standard does not
specify how the program behaves.

You claimed that my statement is "patently false". Please support
your position.

It seems to me that my statement is a trivial consequence of the
definition of a "strictly conforming program", and is therefore
patently true, but if you have a good argument to the contrary, please
elucidate us.

- 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:
>
>> My position is basically that a responsible maintainer for a
>> widely-used compiler does not break existing source code
>
>Question: You mentioned tail call optimization in one of
>your posts.
>
>Should compilers be mandated to copy arguments for
>
>int bar (int a, int b, int c);
>
>int foo(int a, int b, int c)
>{
> if (a > 0)
> return bar(a,b,c);
> else
> return -1;
>}

I don't see why. I also don't see the connection to tail-call
optimization. On AMD64 gcc -O does not copy arguments, whether you
enable tail-call optimization in this case (and in this case it
happens to work) with -foptimize-sibling-calls or not.

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

On Friday, November 5, 2021 at 9:39:02 AM UTC+2, Anton Ertl wrote:
> MitchAlsup <Mitch...@aol.com> writes:
> >On Thursday, November 4, 2021 at 6:21:39 PM UTC-5, Anton Ertl wrote:
> >> MitchAlsup <Mitch...@aol.com> writes:
> >> >From the comp.arch layer of understanding::
> >> ><
> >> >What is it that ISAs can do to minimize the space of UB ?
> >> Not sure what you mean by that, but let me answer "What can in ISA do
> >> to make UB attractive (or less so)."
> >>
> >> The major reason why some people find undefined behaviour on integer
> >> overflow so attractive is the fact that the decision to go with
> >> I32LP64 requires sign-extending here and there with -fwrapv, e.g., with
> >> loops like
> >>
> >> for (int i=0; i<n; i++)
> >> r+=a[i];
> >>
> >> The address of a is 64 bits, but i is a signed 32-bit value, and needs
> >> to be sign-extended with -fwrapv when forming a+i on every iteration
> >> of the loop.
> ><
> >For a new ISA, why would anyone go with I32LP64 why not ILP64 ?
> Yes, indeed, although you should have asked (and maybe have asked) the
> question 30 years ago when MIPS was extended to 64 bits and Alpha was
> introduced. By now, I32LP64 is established, and everybody else (e.g.,
> AMD in 2003, ARM and RISC-V in the 2010s) sticks to it to make it easy
> to port existing software to the architecture. The cost is the large
> number of sign and zero extends that is necessary in some form or
> other (and some of the sign extends are "optimized" away by assuming
> that signed overflow does not happen).
> >But why can 'n' not be checked for being "too big" before running the loop
> >and avoid all of the a+i checking "in the loop". Here, the check seems easy
> >enough (n>=0):: but it seems the real problem is that there is nothing close
> >to the loop supplying the bounds for a[] !!?!
> Yes, it should be possible to make do with zero-extending here (which
> AMD64 does for free). I looked up the example that [wang+12] gave:
>
> int k;
> int *ic, *is;
> ...
> for(k = 1; k <= M; k++) {
> ...
> ic[k] += is[k];
> ...
> }
>
> This is a loop from 456.hmmer, and both gcc and clang sign-extended k
> after the k++ here if -fwrapv was used (and left away the sign
> extension by default). Here, too, sign extension can be eliminated
> without assuming that k++ does not overflow, by transforming the loop into:
>
> for(k = 0; k < M; k++) {
> ...
> (ic+1)[k] += (is+1)[k];
> ...
> }
>
> But back to your question: You can avoid burdening the compiler with
> such optimizations or with assuming that overflow does not happen by
> making the sign extension free.

You mean, making the sign extension free in part of the code that generates effective address?
So, on architectures similar to x86/Arm/PPC/SPARC you advocate addressing mode
that calculates EA=signExt64(RegI32)*SzImm+RegB64 ?
And on architectures similar to MIPS64/RV64/Alpha you advocate ALU instruction that does the same?
Supposedly, with SzImm that can be 1,2,4,8 and hopefully 16, 32, 64 ?

But that would not help more general case of iterating array of items that have size not equal to small power-of-two.
Even if your ISA provided implied sign-extension option for Integer multiply,
the resulting code would at best match UB-based code generator by number of instructions and
even that is not given.
It's unlikely to match its speed, because integer multiplication tends to be slower than addition.

Personally, to bypass the problem, I am starting to acquire the habit of defining (in performance-critical loops)
such variables as 'i' in your example as ptrdiff_t.

> >But I was wondering more about doing things like::
> ><
> > int a >> int b; // where b is allowed to be negative
> > int a << int b; // where b is allowed to be negative
> ><
> >And when a shift count is negative, the shift is performed in the "other" direction.
> I think divergent behaviour between architectures for instructions
> that would be used for implementing a specific programming language
> construct is one of the reasons for not defining behaviour (in
> particular if one of the behaviours is to trap).
>
> OTOH, convergent behaviour that programming language designers don't
> want to specify (like "a << b" is equivalent to "a << (b&63)") is
> another reason.
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

On 04/11/2021 07:55, Terje Mathisen wrote:
> David Brown wrote:
>> On 03/11/2021 09:25, Anton Ertl wrote:
>>> David Brown <david.brown@hesbynett.no> writes:
>>>> On 02/11/2021 17:35, Anton Ertl wrote:
>>>>> Which leads us back
>>>>> to the #1 advantage that manual optimization has over compilers:
>>>>> requirements instead of source code equivalence.
>>>>>
>>>>
>>>> I think we all know that is something programmers can do that compilers
>>>> cannot.  I'm not sure why you feel the need to emphasise it so often -
>>>> are you under the impression that some people think compilers read
>>>> programmers' minds to learn information not expressed in the source
>>>> code?
>>>
>>> There is a widespread myth that compilers are so good at optimization
>>> that there is no point for programmers to think about optimization
>>> (with some variations; e.g., selecting a good algorithm is admitted as
>>> being outside of the realm of compilers, if algorithms are discussed
>>> at all).
>>
>> Compiler optimisation does a lot of things well, and understanding this
>> can let you write code in a clearer, safer and more maintainable fashion
>> with less programmer effort and more efficient results.  Compilers also
>> know a lot more details about the target architecture and its timings
>> than the great majority of programmers.  Failing to understand this, or
>> failing to use good tools in a good way, means more manual work and
>> sometimes manual "micro-optimisations" that are actually
>> counter-productive in practice.
>
> This is both correct, and misleading:
>
> Yes, compilers do know a lot more about the nooks & crannies of cpu
> performance than the vast majority of programmers, but OTOH, the type of
> optimizations you have to employ to handle micro-architectural balance
> shifts can very often be far larger than anything a compiler would be
> allowed to do.
>

There are some a compiler can do, some that they can't, and some that
modern compilers can help with if you work with them. Compilers can,
for example, intersperse different kinds of instructions or use
different registers to reduce pipeline stalls or bottlenecks. They can
/sometimes/ make use of SIMD and vector instructions, but often they do
this best if you use extension features such as vector types. They can
rarely make use of the more complicated processor instructions for SIMD,
hash acceleration, etc.

> A case in point: I have done several conference presentations and a
> university guest lecture on a single program/algorithm (unix wc - word
> count) which I've optimized for most generations of x86 cpus from 8088
> to Pentium and PentiumPro.
>
> The type of optimizations needed consisted of total rewrites, using new
> algorithms, but still achieving the same end result.
>

Compilers only know "tricks" that their developers have programmed.

> None of those rewrites will ever become possible for any compiler I can
> imagine, besides the fact that most of them was written in pure asm to
> be able to control everything. I did have C or Pascal equivalents though.
>

The aim of C and good compilers here is not to replace the programmer
who figures out the most efficient algorithms, but to reduce the need to
use assembly to implement them efficiently. (And that's "reduce", not
"replace" - it's always an ongoing process.)

> The main steps were (8088) unrolled in-word and white space scanners,
> with absolute minimum code and data byte counts, via runtime-generated
> state machines carefully located at all 128-byte boundaries of a 64K
> segment) (similar to direct threaded forth) that would load the next
> input byte and use that as the high part of a direct branch address,
> with the lower 8 bits containing either 0 or 128 to indicate the current
> in-word status, then around the Pentium time frame I switched to a pure
> data state machine where the code had no branches at all when processing
> a block of 256 input bytes.
>
> For the Out-of-Order class machines (PentiumPro etc) most of the code
> has both C and asm versions, I have a bunch (6-8?) different
> implementations and pick the best at runtime by benchmarking all of them
> against the first 4K block of input.
>
> Somewhat coincidentally, those final versions tend to produce very near
> asm-speed results for the C implementations since there is no need to
> trick the compiler into generating the code I need.
>

If you feel you need to "trick" the compiler, the results will be
fragile - you will not be able to rely on the same details in the object
code for different versions of the compiler, different flags, different
compilers, different targets. Of course, not all code needs to be
widely portable - indeed, most code written has very little need of
portability. But if you are able to get code expressed in correct and
fairly portable C, and you get close to optimal results when you compile
it, then you have something a lot more useful than hand-written
assembly. You no longer have to start again for each new generation of
chip, or each new architecture.

On 04/11/2021 22:45, MitchAlsup wrote:
> On Thursday, November 4, 2021 at 4:19:08 PM UTC-5, David Brown wrote:

>>
>> I know that's not what you were thinking of - but that is what you said.
>> This is why I am so strongly against your ideas about consistency and
>> undefined behaviour - your statements are so sweeping that they cover
>> things that are clearly ridiculous. If you want to pick /specific/
>> classes of UB and give /specific/ definitions to how you want those to
>> behave, then we can get somewhere. I might not agree that the new
>> semantics you pick are an improvement (or not an improvement for my own
>> use), but I will happily appreciate that people might want to add new
>> semantics to the language.
> <
> From the comp.arch layer of understanding::
> <
> What is it that ISAs can do to minimize the space of UB ?
>

That's a different kind of question, and more in line with what I think
is a feasible direction for discussion. Again, I might not agree that
it is desirable to reduce a particular type of UB - but I can see that
some people might want to define semantics for specific classes of UB.

For example, it would be a simple matter to define the semantics for
signed integer overflow - and some people, but by no means all people,
would see that as useful.

It is highly impractical to define the semantics for what happens when
you try to write to an object defined as "const". (I gather some old
FORTRAN compilers let you accidentally redefine the values of integer
constants.) It is impossible to define the semantics for what happens
if a function is defined in one unit with one set of parameters, and
called from a different unit with a different set of parameters.

And several things that are left as UB in the C standards could clearly
be detected by the toolchain. Often they /are/ detected and diagnosed
by the toolchain, but it could be nice to make this a requirement in the
standards rather than UB.

Compilers and their targets are always free to give additional semantics
to things that are UB in the C standards. An ISA could have a hardware
exception any time address 0 is accessed - and the compiler could
support that feature.

On 05/11/2021 01:11, MitchAlsup wrote:
> On Thursday, November 4, 2021 at 5:23:25 PM UTC-5, Thomas Koenig wrote:
>> MitchAlsup <Mitch...@aol.com> schrieb:
>>> From the comp.arch layer of understanding::
>>> <
>>> What is it that ISAs can do to minimize the space of UB ?
>> We have discussed part of this before, but here is a bit
>> of an expansion (and some repetition).
>>
>> There are tools to find undefined behavior (or erroneous programs),
>> ranging from sanitizers (which add a low factor to execution time,
>> maybe two or so) to really heavy-handed tools like valgrind which
>> find a _lot_ of errors while making the code run abysmally slow.
>>
>> Think of ways that an ISA could be designed to speed up those tests.
>> Zero overhead is almost certainly unreachable, but even reducing
>> the speed overhead of checked code would help a lot.
>>
>> Going through the CERT coding standards, look for what can
>> be implemented either efficiently or at zero cost. An example:
>>
>> 5.1 INT30-C. Ensure that unsigned integer operations do not wrap.
> <
> unsigned integers are the only integral format that has well defined
> overflow characteristics == wrap. Why eliminate all wraps on the
> only format that actually wraps correctly ?

In the majority of cases of unsigned integer overflow, the answer is
wrong. It is well-defined, but wrong in the context where you are using
it. Adding an apple to a pile of 65535 apples and ending up with no
apples is only marginally less silly than adding an apple to a pile of
32767 apples and getting -32768 apples.

It is useful that C has a way of getting wrapping behaviour - as such
semantics are occasionally what you need. But defining semantics for
something that makes no logical sense in your code does not suddenly
give you the right answer - it just means you get the wrong answer
consistently.

On 05/11/2021 00:00, Anton Ertl wrote:
> MitchAlsup <MitchAlsup@aol.com> writes:
>>From the comp.arch layer of understanding::
>> <
>> What is it that ISAs can do to minimize the space of UB ?
>
> Not sure what you mean by that, but let me answer "What can in ISA do
> to make UB attractive (or less so)."
>
> The major reason why some people find undefined behaviour on integer
> overflow so attractive is the fact that the decision to go with
> I32LP64 requires sign-extending here and there with -fwrapv, e.g., with
> loops like
>
> for (int i=0; i<n; i++)
> r+=a[i];

I suppose it is possible that this is /a/ reason why some people like
signed integer overflow to be UB. But I would hardly call it "the
/major/ reason".

It is, however, one example of the kind of optimisation that compilers
can make when integer overflow is UB. And you can be quite confident
that in a case like this, the programmer had no intention of wanting "i"
to wrap.

On 05/11/2021 00:56, MitchAlsup wrote:
> On Thursday, November 4, 2021 at 6:21:39 PM UTC-5, Anton Ertl wrote:
>> MitchAlsup <Mitch...@aol.com> writes:
>> >From the comp.arch layer of understanding::
>>> <
>>> What is it that ISAs can do to minimize the space of UB ?
>> Not sure what you mean by that, but let me answer "What can in ISA do
>> to make UB attractive (or less so)."
>>
>> The major reason why some people find undefined behaviour on integer
>> overflow so attractive is the fact that the decision to go with
>> I32LP64 requires sign-extending here and there with -fwrapv, e.g., with
>> loops like
>>
>> for (int i=0; i<n; i++)
>> r+=a[i];
>>
>> The address of a is 64 bits, but i is a signed 32-bit value, and needs
>> to be sign-extended with -fwrapv when forming a+i on every iteration
>> of the loop.
> <
> For a new ISA, why would anyone go with I32LP64 why not ILP64 ?

With 64-bit integers, the great majority of the issues with integer
overflow just disappear.

But it would surprise some people in their coding, and might cause
trouble for those that made assumptions about the size of "int". You
would also have to add an extended integer type in order to get int16_t
and int32_t, which are useful types to have.

Despite that, I think it would be a good idea.

> <
> But why can 'n' not be checked for being "too big" before running the loop
> and avoid all of the a+i checking "in the loop". Here, the check seems easy
> enough (n>=0):: but it seems the real problem is that there is nothing close
> to the loop supplying the bounds for a[] !!?!
> <

If the compiler knows about the size of the array, or the size of n,
then it could avoid any additional work regardless of -fwrapv semantics.
And yes, I think if these were unknown, then the check could be hoisted
to the start of the loop rather than doing any kind of sign-extension in
the loop.

>> If the instruction generated for i++ sign-extends (like
>> Alpha's addl, but then Alpha have a similar problem if i was defined
>> as unsigned; so we would need both sign-extending and zero-extending
>> variants), you don't need to sign-extend with an extra intruction.
> <
> In I32LP64 codes, Brian's My 66000 C compiler spits out copious
> quantities of EXT Rx,Rx,<31:0> // extract the lower 32 bits and sign
> extend.
> <
>> Alternatively, if the address computation supports sign-extended
>> 32-bit arguments (IIRC Aarch64 has such addressing modes), this is
>> another way of avoiding the extra instruction. Finally,
>> sign-extension instructions could be made zero-cost in implementations
>> (like zero-extending is in some implementations), this might also
>> reduce the attraction (but I guess that the effect would be smaller,
>> because an instruction always has a psychological cost.
>> - anton
>> --
>> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
>> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>
> <
> But I was wondering more about doing things like::
> <
> int a >> int b; // where b is allowed to be negative
> int a << int b; // where b is allowed to be negative
> <
> And when a shift count is negative, the shift is performed in the "other" direction.
>

I am not sure these occur very often in code. More common, I would
expect, are cases where "a" is negative, or where "b" is greater than or
equal to the width of the type. If the ISA has a particular fixed way
to handle these, then those semantics could be added to the compiler.

On 04/11/2021 22:42, John Dallman wrote:
> In article <2021Nov4.182748@mips.complang.tuwien.ac.at>,
> anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:
>
>> The issue is: If a program has been tested and works on one or
>> several versions of a C compiler, and it does not work on a new
>> version of the same compiler on the same architecture(s), is
>> it a regression in the compiler (my position), or has the program
>> been broken all the time, and the earlier compiler releases were
>> just not advanced enough to expose this brokenness earlier.
>
> The question does not have a general answer IME. I've encountered this
> situation many times. The results have included:
>
> "Yes, the compiler really has a regression." Sometimes that is easy to
> decide, sometimes you have to dig a fair bit to be sure.
>
> "No, I can't blame the compiler for misunderstanding this code." Because
> it's complex or twisted in some strange way that previous compilers
> didn't notice.
>
> And occasionally, "What the hell was the developer thinking? Why did any
> compiler ever do anything sensible with this?"
>

I've been there. I once had to fix a program I inherited where the
programmer tended to declare external functions randomly throughout the
C files that used them, rather than in a nicely structure header. The
result was that the function definitions might be changed later to have
different numbers or types of parameters, while the declarations and
uses kept the old parameter sets. The program "worked", for the most
part, except for a few odd bugs. But it worked due to coincidences of
what happened to be in particular registers before and after these
broken function calls. No compiler could be expected to replicate such
behaviour when changing to a new version!

MitchAlsup <MitchAlsup@aol.com> schrieb:
> On Thursday, November 4, 2021 at 5:23:25 PM UTC-5, Thomas Koenig wrote:
>> MitchAlsup <Mitch...@aol.com> schrieb:
>> > From the comp.arch layer of understanding::
>> ><
>> > What is it that ISAs can do to minimize the space of UB ?
>> We have discussed part of this before, but here is a bit
>> of an expansion (and some repetition).
>>
>> There are tools to find undefined behavior (or erroneous programs),
>> ranging from sanitizers (which add a low factor to execution time,
>> maybe two or so) to really heavy-handed tools like valgrind which
>> find a _lot_ of errors while making the code run abysmally slow.
>>
>> Think of ways that an ISA could be designed to speed up those tests.
>> Zero overhead is almost certainly unreachable, but even reducing
>> the speed overhead of checked code would help a lot.
>>
>> Going through the CERT coding standards, look for what can
>> be implemented either efficiently or at zero cost. An example:
>>
>> 5.1 INT30-C. Ensure that unsigned integer operations do not wrap.
><
> unsigned integers are the only integral format that has well defined
> overflow characteristics == wrap. Why eliminate all wraps on the
> only format that actually wraps correctly ?

If it is wrapping "correctly" or not depends on what is done with
it, and what the programmer intended.

The CERT C coding standards cites four vulnerabilities because
due to this kind of thing, among them CVE-2009-1385 (a Linux
kernel vulnerability), a vmsplice exploit in Linux, an integer
wrap vulnerability in LZO and an iOS 7.1 vulnerability due to
a multiplication resuling in a too-small memory amount.

The full text (which is longish, but can be browsed for a general
overview rather quickly) can be found at

https://resources.sei.cmu.edu/downloads/secure-coding/assets/sei-cert-c-coding-standard-2016-v01.pdf