Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #3278 > unrolled thread

Undefined Behavior Optimizations in C

Back to article view | Back to comp.compilers

Contents

  Undefined Behavior Optimizations in C "Lucian Popescu" <lucic71@ctrl-c.club> - 2023-01-05 10:05 +0000
    RE: Undefined Behavior Optimizations in C "Nuno Lopes" <nuno.lopes@tecnico.ulisboa.pt> - 2023-01-05 10:24 +0000
    Re: Undefined Behavior Optimizations in C Spiros Bousbouras <spibou@gmail.com> - 2023-01-05 18:06 +0000
      Re: Undefined Behavior Optimizations in C gah4 <gah4@u.washington.edu> - 2023-01-05 16:22 -0800
        Re: Undefined Behavior Optimizations in C anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2023-01-06 08:41 +0000
        Re: Undefined Behavior Optimizations in C David Brown <david.brown@hesbynett.no> - 2023-01-06 16:12 +0100
          Re: Undefined Behavior Optimizations in C gah4 <gah4@u.washington.edu> - 2023-01-06 10:33 -0800
            Re: Undefined Behavior Optimizations in C gah4 <gah4@u.washington.edu> - 2023-01-06 11:39 -0800
            Re: Undefined Behavior Optimizations in C Spiros Bousbouras <spibou@gmail.com> - 2023-01-07 12:10 +0000
              Re: Undefined Behavior Optimizations in C antispam@math.uni.wroc.pl - 2023-01-13 20:46 +0000
          Re: Undefined Behavior Optimizations in C Kaz Kylheku <864-117-4973@kylheku.com> - 2023-01-09 10:14 +0000
            Re: Re: Undefined Behavior Optimizations in C Jon Chesterfield <jonathanchesterfield@gmail.com> - 2023-01-10 10:46 +0000
              Re: Undefined Behavior Optimizations in C Thomas Koenig <tkoenig@netcologne.de> - 2023-01-11 09:34 +0000
                Re: Undefined Behavior Optimizations in C Kaz Kylheku <864-117-4973@kylheku.com> - 2023-01-12 05:21 +0000
                  Re: Undefined Behavior Optimizations in C Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2023-01-12 12:21 -0800
                  Re: Undefined Behavior Optimizations in C Thomas Koenig <tkoenig@netcologne.de> - 2023-01-12 21:50 +0000
                  Re: Undefined Behavior Optimizations in C Kaz Kylheku <864-117-4973@kylheku.com> - 2023-01-15 04:17 +0000
              Re: Undefined Behavior Optimizations in C David Brown <david.brown@hesbynett.no> - 2023-01-11 14:20 +0100
                Re: Undefined Behavior Optimizations in C Spiros Bousbouras <spibou@gmail.com> - 2023-01-18 13:14 +0000
                  Re: Undefined Behavior Optimizations in C David Brown <david.brown@hesbynett.no> - 2023-01-18 21:14 +0100
                    Re: Undefined Behavior Optimizations in C gah4 <gah4@u.washington.edu> - 2023-01-18 21:10 -0800
                    Re: Undefined Behavior Optimizations in C gah4 <gah4@u.washington.edu> - 2023-01-20 10:45 -0800
                      Re: Undefined Behavior Optimizations in C Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2023-01-20 13:54 -0800
                    Re: Undefined Behavior Optimizations in C gah4 <gah4@u.washington.edu> - 2023-01-23 18:50 -0800
                      Re: Undefined Behavior Optimizations in Fortran "Steven G. Kargl" <sgk@REMOVEtroutmask.apl.washington.edu> - 2023-01-26 21:12 +0000
                      Re: Undefined Behavior Optimizations in Fortran gah4 <gah4@u.washington.edu> - 2023-01-26 17:50 -0800
                  Re: Undefined Behavior Optimizations in C "Alexei A. Frounze" <alexfrunews@gmail.com> - 2023-01-19 21:18 -0800
                    Re: Undefined Behavior Optimizations in C Thomas Koenig <tkoenig@netcologne.de> - 2023-01-20 20:42 +0000
                      Re: Undefined Behavior Optimizations in C anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2023-01-21 11:54 +0000
                        Re: Undefined Behavior Optimizations in C anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2023-01-22 09:56 +0000
                      Re: Undefined Behavior Optimizations in C Kaz Kylheku <864-117-4973@kylheku.com> - 2023-01-22 07:04 +0000
                  Re: Undefined Behavior Optimizations in C Martin Ward <martin@gkc.org.uk> - 2023-01-23 17:12 +0000
            Re: Undefined Behavior Optimizations in C David Brown <david.brown@hesbynett.no> - 2023-01-10 17:32 +0100
              Re: Undefined Behavior Optimizations in C gah4 <gah4@u.washington.edu> - 2023-01-10 15:57 -0800
                Re: Undefined Behavior Optimizations in C David Brown <david.brown@hesbynett.no> - 2023-01-11 14:40 +0100
                  Re: Undefined Behavior Optimizations in C gah4 <gah4@u.washington.edu> - 2023-01-11 16:09 -0800
              Re: Undefined Behavior Optimizations in C dave_thompson_2@comcast.net - 2023-01-28 10:35 -0500
    Re: Undefined Behavior Optimizations in C anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2023-01-06 07:47 +0000
    Re: Undefined Behavior Optimizations in C Kaz Kylheku <864-117-4973@kylheku.com> - 2023-01-09 09:10 +0000

Page 2 of 2 — ← Prev page 1 [2]

#3332

On Wednesday, January 18, 2023 at 3:55:49 PM UTC-8, David Brown wrote:

(snip)

> From your example above, we can see that the compiler can transform (a)
> into "y++;" - there is no need for the conditional. But the compiler
> can /also/ transform (b) into ";" - it is allowed to reason that if x
> /were/ equal to INT_MAX, statement (a) would be undefined behaviour
> (even though it was transformed away) and there is no value for x which
> would result in "y = 10" being executed without also executing UB.

This is reminding me of some quantum mechanics rules described here:

https://www.sciencenews.org/wp-content/uploads/2010/11/baseball.pdf

It is interesting reading for those interested in the physics, but also
for those who aren't.   It doesn't take much physics thought.

It has to do with what quantum mechanics allows when you don't
actually measure something.

And, similarly, compilers shouldn't try to make too many assumptions
about things not measured.

[toc] | [prev] | [next] | [standalone]

#3334

On Wednesday, January 18, 2023 at 3:55:49 PM UTC-8, David Brown wrote:

(snip)

> So if you have :
>
> int x, y;
>
> if (x + 1 > x) y++; // (a)
> if (x == INT_MAX) y = 10; // (b)

> From your example above, we can see that the compiler can transform (a)
> into "y++;" - there is no need for the conditional. But the compiler
> can /also/ transform (b) into ";" - it is allowed to reason that if x
> /were/ equal to INT_MAX, statement (a) would be undefined behaviour
> (even though it was transformed away) and there is no value for x which
> would result in "y = 10" being executed without also executing UB.

I am now wondering both how well compilers do this, and how well
people do this.

Note that the only case where, on all machines I use, the y++ is
not executed, is when x==INT_MAX.   Now, it would be completely
different for:

if(x + 2 > x) y++; (a)

or

if(x == INT_MAX) y--;

For many years, C allowed for sign-magnitude and ones' complement
representation.  Fixed point overflow was, then, at least machine
dependent as they overflow differently.  Some machines have the
ability to enable an interrupt on fixed point overflow, but at least
for Fortran and C, it is normally disabled.

Now, C has unsigned int which you can use when you need specific
overflow behavior (except on some Unisys machines). Fortran does not,
and so people expect, and depend, on two's complement overflow. (The
Fortran standard allows for any integer radix greater than one, and
also for different sign representations. But often enough, people know
it is two's complement binary.)

As C allows for both UB and system-dependent behavior, and it is
hard for people to remember every case of each one, it is unreasonable
to me, to assume fixed point overflow is UB.

Dereference of pointers that might point to the wrong place, maybe.

The reason for the Fortran example above, mentioning short circuit
IF statements, was that Fortran programs, at least with IBM compilers,
could reliably fetch from element 0 of an array. With static allocation,
and data stored after code, there was no chance of element 0 being
outside the address space.  Yes people shouldn't rely on it,
but sometimes they did.

Storing outside an array often enough leads to problems, but fetch
much less often.

[toc] | [prev] | [next] | [standalone]

#3336

gah4 <gah4@u.washington.edu> writes:
[snip]
> For many years, C allowed for sign-magnitude and ones' complement
> representation.

It still does.  The upcoming 2023 ISO C standard mandates 2's-complement
for signed integer types, but it hasn't been published yet.

[...]

> Now, C has unsigned int which you can use when you need specific
> overflow behavior (except on some Unisys machines).

If a Unisys C implementation doesn't behave as the standard requires
with respect to unsigned overflow, then it's a non-conforming
implementation.  (Non-conforming implementations can still be useful.)

[...]

> As C allows for both UB and system-dependent behavior, and it is
> hard for people to remember every case of each one, it is unreasonable
> to me, to assume fixed point overflow is UB.

C has:
- Undefined behavior (the standard imposes no requirements);
- Unspecified behavior (the standard provides 2 or more possibilities
  and implementations can choose arbitrarily; an example is the order of
  evaluation of function arguments); and
- Implementation-defined behavior (unspecified behavior where the
  implementation must document its choice).

Signed integer overflow has undefined behavior -- not because it is or
isn't reasonable, but because the standard says so.

Even in C23, the mandate for 2's-complement representation doesn't
imply a requirement for 2's-complement behavior on overflow.

[...]

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for XCOM Labs
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#3341

On Wednesday, January 18, 2023 at 3:55:49 PM UTC-8, David Brown wrote:

(snip)

> int x, y;
>
> if (x + 1 > x) y++;

OK, for now just considering this one.

And the only Fortran program I still remember from almost 50 years ago.
(It was summer 1972 when I first started learning Fortran, so not long after.)

|      SUBROUTINE RANDU (IX, IY, YFL)
|      IY = IX * 65539
|      IF (IY) 5,6,6
|5     IY = IY + 2147483647 + 1
|6     YFL = IY
|      YFL = YFL * .4656613E-9
|      RETURN
|      END

To avoid loss of indenting, I put in the |.

Since Fortran doesn't have unsigned integers, programs use signed integers.

And a lot of Fortran programs get translated to C.

But first, I suspect that many C programmers don't know, or don't remember
if they did, that two's complement overflow is UB.

And of those that know it is UB, I suspect many don't expect compilers to remove
statements that depend on it. Most C programmers don't carry around the
standard, and don't look up every operation.

Now, C programmers should know about unsigned int, and its properties.

But those translating Fortran programs to C won't always know when they
depend on it.  RANDU is probably the most infamous random number generator,
that was popular for many years.  It comes from the IBM Scientific Subroutine
Package that traces back to the early 1960's.

It conveniently depends on the fixed point overflow properties of the multiply,
and then the IF to correct for negative results.

As far as I can tell, Fortran makes no claims regarding fixed point overflow,
being undefined or system dependent.

Fortran does allow for fixed point values in any radix greater than one.
There are requirements for the number of decimal digits that types can
represent.

There are also, as part of the C interoperability feature, fixed point types
(KINDs in Fortran terms) with specific bit widths.

Now, the original subject of this thread, is the cost vs. benefit of such
optimizations.  Not so obvious the benefit, but there is a cost when people
try to debug programs where things are optimized away.
[Gee, it's been a while since I thought about SSP.  I believe that IBM wrote
it largely to give people code that would get reasonable numeric answers
with the 360's funky floating point.  Then there were a few odds and ends
like RANDU.  They never promised the code would work on anything other
than IBM 360 Fortran. -John]

[toc] | [prev] | [next] | [standalone]

#3342 — Re: Undefined Behavior Optimizations in Fortran

On Mon, 23 Jan 2023 18:50:31 -0800, gah4 wrote:
>
> As far as I can tell, Fortran makes no claims regarding
> fixed point overflow, being undefined or system dependent.
>

It makes claims.  F2018 (18-007r1.pdf), p. 148.

   The execution of any numeric operation whose result is
   not defined by the arithmetic used by the processor is
   prohibited.

If you want to go back to F66, one finds in Sec. 6.4,
"Evaluation of Experssions."

   No element may be evaluated whose values is not
   mathematically defined.

--
steve
[Like I said, IBM didn't promise that SSP would work anywhere else. -John]

[toc] | [prev] | [next] | [standalone]

#3343 — Re: Undefined Behavior Optimizations in Fortran

On Thursday, January 26, 2023 at 11:00:02 AM UTC-8, gah4 wrote:

(snip)

> Now, the original subject of this thread, is the cost vs. benefit of such
> optimizations. Not so obvious the benefit, but there is a cost when people
> try to debug programs where things are optimized away.

> [Gee, it's been a while since I thought about SSP. I believe that IBM wrote
> it largely to give people code that would get reasonable numeric answers
> with the 360's funky floating point. Then there were a few odds and ends
> like RANDU. They never promised the code would work on anything other
> than IBM 360 Fortran. -John]

It seems that there is also SSP for the IBM 1130, which is 16 bit binary,
so probably also a 32 bit two's complement integer.

There is a PL/I SSP, but seems not to have RANDU.

When I was in high school, we had CALL/OS, with PL/I, and
I used the RANDU algorithm, as I didn't have any other one.

As you say, it wasn't promised to work with any other Fortran,
but others did try to stay compatible with IBM.
(But often with non-IBM extensions.)

Fortran systems that I know, are good at ignoring fixed point
overflow, though often trap or count floating point overflow.
[I took a look, RANDU on the 1130 repeated after 2^13 items.
Yow. -John]

[toc] | [prev] | [next] | [standalone]

#3333

On Wednesday, January 18, 2023 at 8:35:40 AM UTC-8, Spiros Bousbouras wrote:
...
> I have encountered several times the claim that compilers assume that UB does
> not happen and I don't understand it. Lets consider 2 examples :
>
> x + 1 > x
>
> in C where x is a signed integer. Compilers will often treat this as
> always true with the following reasoning :
>
> - if x does not have the maximum value which fits in its type then the
> meaning of the C expressions is the same as their mathematical meaning
> so the expression evaluates to true.
>
> - if x has the maximum value which fits in its type then x + 1 is not
> defined so any translation (including treating the whole expression as
> true) is valid.
>
> There's no assumption that UB (undefined behaviour) will not happen, both
> possibilities are accounted for.

I believe in a case like this a modern C/C++ compiler reasons that x must be
less than the maximum representable value and it generates code according
to this, possibly removing dead code that depends on x being the maximum
representable value. If the compiler's assumption that x is less than the
maximum is wrong, it's perfectly fine, it's UB, any "broken" code generated
is allowed.

Alex

[toc] | [prev] | [next] | [standalone]

#3335

Alexei A. Frounze <alexfrunews@gmail.com> schrieb:

> I believe in a case like this a modern C/C++ compiler reasons that x must be
> less than the maximum representable value and it generates code according
> to this, possibly removing dead code that depends on x being the maximum
> representable value. If the compiler's assumption that x is less than the
> maximum is wrong, it's perfectly fine, it's UB, any "broken" code generated
> is allowed.

There are cases when compilers don't even use this knowledge.

Take the function

int add (int a, int b)
{
    return a+b;
}

on an instruction set architecture which has only 64-bit
arithmetic, such as POWER.  This is translated by gcc,
with optimization, to

        add 3,3,4
        extsw 3,3
        blr

(which is an addition followed by a sign extension).  The POWER ABi
specifies that all values passed in registers are sign-extended,
so the content of a register has the same value independent of
the width of the signed integer it is being considered as.

So, the compiler would be within its right to _not_ extend the sign
of the result, because it could assume that no overflow occurs.
This, however, would result in a violation of the ABI, so the
compiler puts in the extra instruction just in case.  If you
replace int by long in the example above, the sign extension
instruction is not generated.

By comparision, MIPS gcc translates this to

        jr      $31
        addu    $2,$4,$5

(note use of the delay slot), so no explicit sign extension is done,
and the value returned in the register might have a different value
if interpreted as a 64-bit value.

[toc] | [prev] | [next] | [standalone]

#3337

Thomas Koenig <tkoenig@netcologne.de> writes:
>Take the function
>
>int add (int a, int b)
>{
>    return a+b;
>}
>
>on an instruction set architecture which has only 64-bit
>arithmetic, such as POWER.  This is translated by gcc,
>with optimization, to
>
>        add 3,3,4
>        extsw 3,3
>        blr
>
>(which is an addition followed by a sign extension).  The POWER ABi
>specifies that all values passed in registers are sign-extended,
>so the content of a register has the same value independent of
>the width of the signed integer it is being considered as.
>
>So, the compiler would be within its right to _not_ extend the sign
>of the result, because it could assume that no overflow occurs.
>This, however, would result in a violation of the ABI, so the
>compiler puts in the extra instruction just in case.  If you
>replace int by long in the example above, the sign extension
>instruction is not generated.
>
>By comparision, MIPS gcc translates this to
>
>        jr      $31
>        addu    $2,$4,$5
>
>(note use of the delay slot), so no explicit sign extension is done,

What makes you think so?  The definition of ADDU in MIPS IV Rev. 3.2
is pretty perverse, specifying an undefined result if one of the
operands is not a sign-extended 32-bit value; but if both operands are
to the instruction's liking, it produces a sign-extended 32-bit
result.

A programming note says:

|[ADDU] is appropriate for arithmetic which is not signed, such as
|address arithmetic, or integer arithmetic environments that ignore
|overflow, such as “C” language arithmetic.

One interesting aspect is that the Power ABI specifies sign-extension
rather than garbage-extension for passing around ints.  Many other
ABIs are similar (e.g., the RISC-V ABI specifies sign extension, even
for unsigned ints), and AMD64 specifies zero-extension for both signed
and unsigned ints (and has instructions that generate zero-extended
results).

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

[toc] | [prev] | [next] | [standalone]

#3339

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>AMD64 specifies zero-extension for both signed
>and unsigned ints (and has instructions that generate zero-extended
>results).

Looking at <https://refspecs.linuxbase.org/elf/x86_64-abi-0.99.pdf>, I
find no such specification.  However, compilers certainly behave in
that way.  E.g., for

int add (int a, int b)
{
    return a+b;
}

gcc generates:

   0:   8d 04 37                lea    (%rdi,%rsi,1),%eax
   3:   c3                      retq

which zero-extends the result.  This certainly rules out an ABI that
requires sign-extension for signed integers.

One interesting case is:

long add (unsigned a, long b)
{
    return a+b;
}

which gcc compiles into

   0:   89 ff                   mov    %edi,%edi
   2:   48 8d 04 37             lea    (%rdi,%rsi,1),%rax
   6:   c3                      retq

What's the point of the MOV instruction here?  It performs a
32->64-bit zero extension of %rdi.  So gcc apparently assumes that
passed operands are garbage-extended on AMD64.  Or maybe gcc is just
cautious here.  Another test:

unsigned bar(int x);

unsigned long foo(long x)
{
  return bar(x);
}

gcc -O compiles this to:

   0:   48 83 ec 08             sub    $0x8,%rsp
   4:   e8 00 00 00 00          callq  9 <foo+0x9>
   9:   89 c0                   mov    %eax,%eax
   b:   48 83 c4 08             add    $0x8,%rsp
   f:   c3                      retq

There is no zero or sign-extension on passing x to bar(), so the value
is passed garbage-extended.  There is a zero extension for converting
the return value unsigned long, so gcc assumes that the return value
of bar is not necessarily zero-extended.

Conclusion: In the System V ABI for AMD64, values are passed around
garbage-extended (in the general case).

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

[toc] | [prev] | [next] | [standalone]

#3338

On 2023-01-20, Thomas Koenig <tkoenig@netcologne.de> wrote:
> Alexei A. Frounze <alexfrunews@gmail.com> schrieb:
>
>> I believe in a case like this a modern C/C++ compiler reasons that x must be
>> less than the maximum representable value and it generates code according
>> to this, possibly removing dead code that depends on x being the maximum
>> representable value. If the compiler's assumption that x is less than the
>> maximum is wrong, it's perfectly fine, it's UB, any "broken" code generated
>> is allowed.
>
> There are cases when compilers don't even use this knowledge.
>
> Take the function
>
> int add (int a, int b)
> {
>     return a+b;
> }
>
> on an instruction set architecture which has only 64-bit
> arithmetic, such as POWER.  This is translated by gcc,
> with optimization, to
>
>         add 3,3,4
>         extsw 3,3
>         blr
>
> (which is an addition followed by a sign extension).  The POWER ABi
> specifies that all values passed in registers are sign-extended,
> so the content of a register has the same value independent of
> the width of the signed integer it is being considered as.
>
> So, the compiler would be within its right to _not_ extend the sign
> of the result, because it could assume that no overflow occurs.

Indeed. If overflow occurs, then there could be an unexpected results if
the, say, result of the addition is converted to a 64 bit type.

Suppose that a 32 to 64 conversion is actually a no-op, because the
register values are assumed to be sign-extended, like the ABI says.

Then, say a and b are positives values that fit into the 32 bit
range, such that the a + b sum does not; it wraps negative
in 32 bits.

The programmer might thus expect expect (long) (a + b) to be
that wrapped negative value.

But since the addition is done in 64 bits, it doesn't overflow;
there is a positive 64 bit result. If conversion to long is a noop,
a positive value of long will result, as if the expression were
(long) a + (long) b.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

[toc] | [prev] | [next] | [standalone]

#3340

On 18/01/2023 13:14, Spiros Bousbouras wrote:

There's no assumption that UB (undefined behaviour) will not happen, both
possibilities are accounted for.


The "assumption that UB will not happen" is shorthand for the idea
that any optimisation is valid if the optimised code is a refinement
of the unoptimised code for all initial states such that UB does not
occur. Equivalently, a proposed optimiation is valid if we represent
UB as "abort" (a statement which can be refined to anything) and the
optimised code is a refinement of the unoptimised code for all initial
states.

--
            Martin

Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk
G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4

[toc] | [prev] | [next] | [standalone]

#3300

On 09/01/2023 11:14, Kaz Kylheku wrote:
> On 2023-01-06, David Brown <david.brown@hesbynett.no> wrote:
>> On 06/01/2023 01:22, gah4 wrote:

>>> Most important when debugging, is that you can trust the compiler to
>>> do what you said. That they don't, has always been part of
>>> optimization, but these UB make it worse.
>>
>> The trouble with undefined behaviour is that, in general, you cannot
>> trust the compiler to "do what you say" because it cannot know what you
>> have said.
>
> That's correcst; however, what we should be able to trust is for the
> compiler not to make it worse.
>

Let's be clear here.  At the theoretical level, when your code executes
undefined behaviour at run time, you have said "I don't care what
happens now".  The compiler is allowed to do /anything/.  There is no
such thing as "making it worse" - you have said you will accept
absolutely /anything/ from the compiler.  No restrictions, no
limitations - /anything/.

That is what "undefined behaviour" means.  There are /no/ definitions of
the behaviour, and no limits, expectations, "worse" choices, "better"
choices.

At a /practical/ level, compilers can try to be more helpful.  They can
define behaviour for things that are not defined in the language
specifications.  They can give you warnings or error messages (at
compile time or run time, such as when using sanitizers).  They can
offer optional extra semantics (like gcc's "-fwrapv" flag).  They can
certainly avoid going out of their way to avoid being specially awkward
- normally they are simply trying to make the code more efficient when
it is running correctly.

But you cannot be sure things won't go unexpectedly bad.  You can never
have guarantees about that.  Guarantees require definitions, and you
don't have that with undefined behaviour.

Consider this example source code:

void print_message(bool x) {
	if (x) {
		printf("Great!\n");
	} else {
		printf("Boo!\n");
	}
}

void format_harddisk(int disk_number) {
	...
}


This is fine code, with no UB in sight.

The compiler could this to the pseudo-code :

print_message:
	if ($GPR1 == 0) :
		$GPR1 = "Boo!"
		jump puts

	if ($GPR1 == 1) :
		$GPR1 = "Great!"
		jump puts

format_harddisk:
	...


It knows that on entry, the parameter in GPR1 is either 0 or 1, because
it is type "bool".

What happens if you call the function from a different translation unit
like this :

	extern void print_message(int x);
	print_message(2);

?

This is clearly wrong - clearly undefined behaviour.  And the result
would be a formatted disk.  But there is nothing wrong with the
compiler's generated code.  I have seen other occasions when compiler's
have made code with booleans that appear to be both true and false, or
neither true nor false, as a result of undefined behaviour setting the
underlying memory to something other than 0 or 1, simply because that
was the result of the most efficient code.

There are all sorts of other ways a compiler can take advantage of
knowing a boolean is either 0 or 1, and all sorts of things that can go
wrong if you've messed up your code and the boolean is /not/ 0 or 1.  It
can use it as an index into an array, or to multiply a value
(translating "x = f ? a : b;" into "x = f * (a - b) + b;" ), or using it
as a bit mask, or subtracting 1 and using /that/ as a mask.  And once
you have started getting the wrong values, there is no theoretical limit
to how bad things can get - it is not the compiler "making things
worse", it is bugs in the code being outside the specifications for what
is intended for the program.


Of course the compiler should not be messing around checking that the
value you pass is actually 0 or 1.  That would be inefficient.  And what
would it do if it was a bad value?  Treat it as "false" ?  What about
calling "missile_control(bool cancel_launch)" with a bad value?  Should
it treat it as "true" ?  What about calling "missile_control(bool
confirm_launch)" with a bad value?  Jump to an error handler and stop
the program with a message?  How does that work for your flight controller?

If you want a hand-holding check everything language, there are plenty
of them to go around.  They're great, and far more appropriate than C
for many purposes.  C, on the other hand, trusts the programmer and
gives you the most efficient object code it can from the source you give
it, based on the rules of the language (plus any extra features defined
by the compiler).

> The compiler makes it worse when it assumes that the programmer is
> infallible, and thus makes logical inferences predicated on some
> construct never having undefined behavior, using those to guide the
> translation of other constructs.

It is the programmers' /job/ to write correct code.  It is up to them to
use any and all tools available to do that - static error checking,
run-time sanitizers, code reviews, unit tests, system tests, etc.  That
also includes using the write language for the task in hand.  If the
code is critical, but too complex to be written bug-free in C, then
maybe a different language would be better - or maybe a different
programmer.

I am not suggesting that I always write bug-free code.  But the bugs I
put in my code are /my/ bugs - /my/ responsibility.  And I don't blame
the compiler for the effects of these bugs.

>
> This is particularly harmful when the undefined behavior is *de facto*
> defined: like that if the undefinedness aspect is ignored, and the
> obvious code is emitted, that code will do something characteristic
> of the machine.

It is particularly harmful when programmers think there is such a thing
as "de facto defined".  That's an oxymoron.  If the behaviour is
defined, it is defined.  If it is not defined, it is not defined.  If it
is not defined and a programmer makes unwarranted and incorrect
assumptions about what they think it means, then the programmer needs to
update his or her understanding of the language.  They don't get to
blame the compiler or the compiler writer for not making the same
unfounded assumptions that they did.


>
> In C99, the original definition of undefined behavior is this:
>
>    behavior, upon use of a nonportable or erroneous program construct or
>    of erroneous data, for which this International Standard imposes no
>    requirements.
>
>    NOTE: Possible undefined behavior ranges from ignoring the situation
>    completely with unpredictable results, to behaving during translation
>    or program execution in a documented manner characteristic of the
>    environment (with or without the issuance of a diagnostic message), to
>    terminating a translation or execution (with the issuance of a
>    diagnostic message).
>
> There is an obvious intepretation of this text which rules out
> the too-clever optimizations.
>

I presume you mean "a documented manner characteristic of the
environment".  That would be something like gcc's "-fwrapv" flag.  It
takes something that is undefined in the C standards - signed integer
overflow - and gives it a /documented/ behaviour.  The key here is
"documented".  Now the behaviour is /defined/ - it is UB as far as the C
standards are concerned, but /defined/ behaviour as far as the
implementation is concerned.  And you can rely on it, as long as you use
a compiler with such a flag and documented behaviour.

The more general and obvious interpretation of the definition is
"imposes no requirements" - you have no right to have any expectations
about the results of the undefined behaviour.  In particular, while you
might have some guesses as to what will happen just at the time, you
have no idea about knock-on effects.

> If the compiler optimizes construct Y based on some other construct
> X being free of undefined behavior, and that assumption turns
> out to be false, that compiler has not conformed to the "NOTE"
> part of the treatment of undefined behavior.
>
> Firstly, it has not "ignor[ed] the situation completely". You cannot
> assume that X is well-defined, in order to treat Y in some way, and yet
> say that you're completely ignoring the situaton of X.  If the UB
> problem in X causes a secondary problem with the way Y was translated,
> that is a problem with the assumption that was made about X. That
> assumption was made because it's possible for X to be undefined, and
> that possiblity was expliclty disregarded, which is not the same as
> completely ignored.
>
> The situation also isn't a documented manner characteristic of
> the environment.
>
> It also isn't a termination of translation or execution with or without
> a diagnostic message.
>
> The situation doesn't conform to the NOTE.
>
> C compiler writers should take the NOTE more seriously.

The "note" is just a note, not part of the language definitions, and it
gives some example treatments of undefined behaviour, not an exclusive
list of options.  No, compiler writers do /not/ have to take it
seriously.  If the C standards committee had wanted to impose
restrictions on what can happen during undefined behaviour, they would
have given them instead of saying "no requirements".  (And the committee
are smart enough to know that imposing restrictions to UB in general is
not possible.)

Of course it would be possible to impose restrictions in particular
cases.  It would be fine to say, for example, that signed integer
overflow gives an unspecified integer value as a result, rather than
undefined behaviour.  Or that attempting to dereference an invalid
pointer will result in the memory being written or read regardless.  But
that would be giving definitions to behaviour that is currently
undefined - you cannot impose meaning on undefined behaviour itself.

[toc] | [prev] | [next] | [standalone]

#3303

On Tuesday, January 10, 2023 at 2:00:57 PM UTC-8, David Brown wrote:

(big snip)

> It is particularly harmful when programmers think there is such a thing
> as "de facto defined". That's an oxymoron. If the behaviour is
> defined, it is defined. If it is not defined, it is not defined. If it
> is not defined and a programmer makes unwarranted and incorrect
> assumptions about what they think it means, then the programmer needs to
> update his or her understanding of the language. They don't get to
> blame the compiler or the compiler writer for not making the same
> unfounded assumptions that they did.

A lot of C code assumes two's complement.  I believe Unisys still sells
ones' complement hardware, and so that code might have UB, but often
people know that it will only run on two's complement machines.

Much also assumes ASCII code.  Don't tell IBM about that.

I remember comments in some routines in the IBM PL/I (F)
library, such as:

THE OPERATION OF THIS MODULE DEPENDS UPON AN INTERNAL
REPRESENTATION OF THE EXTERNAL CHARACTER SET WHICH IS
EQUIVALENT TO THE ONE USED AT ASSEMBLY TIME. THE CODING
HAS BEEN ARRANGED SO THAT REDEFINITION OF ''CHARACTER''
CONSTANTS, BY REASSEMBLY, WILL RESULT IN A CORRECT
MODULE FOR THE NEW DEFINITIONS.

I have never seen that in C programs.

As I noted in another thread, Java has a rule that the compiler be
able to determine that a variable is given a value before it is used.
It is a fatal compilation error if it can't.

If C compilers had a fatal compilation error when they found
suspicious UB, I could live with that.  Maybe it means doing
something to convince the compiler, even if it really is still UB.

Remember, much of the data breaches we hear about
(and also the ones we don't) are due to buffer overflow
in C programs.  Make it easier, instead of harder, for programmers
to avoid buffer problems.

(snip)

[toc] | [prev] | [next] | [standalone]

#3310

On 11/01/2023 00:57, gah4 wrote:
> On Tuesday, January 10, 2023 at 2:00:57 PM UTC-8, David Brown wrote:
>
> (big snip)
>
>> It is particularly harmful when programmers think there is such a thing
>> as "de facto defined". That's an oxymoron. If the behaviour is
>> defined, it is defined. If it is not defined, it is not defined. If it
>> is not defined and a programmer makes unwarranted and incorrect
>> assumptions about what they think it means, then the programmer needs to
>> update his or her understanding of the language. They don't get to
>> blame the compiler or the compiler writer for not making the same
>> unfounded assumptions that they did.
>
> A lot of C code assumes two's complement.  I believe Unisys still sells
> ones' complement hardware, and so that code might have UB, but often
> people know that it will only run on two's complement machines.
>
> Much also assumes ASCII code.  Don't tell IBM about that.

There is usually no requirement for a given piece of C code to be fully
portable to all conforming compilers.  Most C code is quite limited in
the scope of its use, and it is quite reasonable to assume two's
complement representation (though /not/ two's complement wrapping on
overflow), 8-bit char, ASCII characters, etc.  It may be fine to assume
32-bit int, and perhaps little-endian ordering.  These are /warranted/
assumptions, not unwarranted ones - they are typically reasonable to
make, and if you want to you can sometimes put compile-time checks so
that if someone does try to use it out of context, they get an error
message.

And these are all points that the C standards call
implementation-dependent behaviour.  These may vary between compilers or
targets, but for a given toolchain and target the behaviour is clear and
defined.  That is quite different from undefined behaviour.

>
> If C compilers had a fatal compilation error when they found
> suspicious UB, I could live with that.  Maybe it means doing
> something to convince the compiler, even if it really is still UB.
>

C compilers often do their best here, as long as you enable warnings and
optimisation (needed for the code analysis).  I'd prefer it if tools
like gcc had a lot more warnings by default.  However, it is rarely
possible to find run-time UB at compile time.  If a function takes a
pointer parameter and dereferences it, it is only UB if the function is
called with an invalid pointer.  The compiler will assume that UB does
not occur, and compile the function optimised with that assumption.  If
the compiler were to warn you about the potential UB in the function,
your builds would be swamped by false positives.

You can come a long way be using sanitizers when testing code - then
your code is augmented by extra checks, and the run-time will stop with
a fatal error when there are problems.  I think such tools are often
under-used by developers (as are static warnings).  Of course no testing
can prove code is correct, but it is certainly a help.

> Remember, much of the data breaches we hear about
> (and also the ones we don't) are due to buffer overflow
> in C programs.  Make it easier, instead of harder, for programmers
> to avoid buffer problems.
>

Sure.  The prime solution here is to stop using C - use a language that
gives you more help in such cases.  That could be a high level language
such as Python, a managed language like C# or Java, or a smarter
language like Rust or C++.

If you have to use C, then write /better/ C and do better testing.  Stop
passing raw pointers around independently of the size of the data.  Stop
using fixed size "magic numbers" for the size of buffers when the size
needed might change later.  Refactor your data accesses into small
inline functions, where you can easily add tests and limits during
debugging.

Yes, C makes it easy to write incorrect code - but it is quite possible
to use it for writing correct code.  There are other languages that make
it easier to write correct code and harder to write incorrect code -
it's too late for C to change.

[toc] | [prev] | [next] | [standalone]

#3311

On Wednesday, January 11, 2023 at 3:13:08 PM UTC-8, David Brown wrote:

(snip)

> > Much also assumes ASCII code. Don't tell IBM about that.

> There is usually no requirement for a given piece of C code to be fully
> portable to all conforming compilers. Most C code is quite limited in
> the scope of its use, and it is quite reasonable to assume two's
> complement representation (though /not/ two's complement wrapping on
> overflow), 8-bit char, ASCII characters, etc. It may be fine to assume
> 32-bit int, and perhaps little-endian ordering. These are /warranted/
> assumptions, not unwarranted ones - they are typically reasonable to
> make, and if you want to you can sometimes put compile-time checks so
> that if someone does try to use it out of context, they get an error
> message.

As I noted with the Fortran optimization example from 50 years ago,
this is not a new problem.  But IBM documented it (so, as you note, it
is an extension and not UB), and programmers learn to expect it.

And yes I ignored the distinction between implementation defined
and undefined.  But that is exactly what happens when actual
people (as opposed to other programs) write programs.

People learn what works and what doesn't. When they need to worry
about endianness or ASCII or two's complement.

Much of the implementation, or undefined, behavior of early Fortran
compilers, later got implemented into the standard. And much didn't,
but enough people believe it did.

If compiler writers remember that they are writing for use by actual
people, who are sometimes imperfect, then it should be fine. Try to
make the changes not too surprising to users.

I don't remember the exact example of surprising UB, but they are out
there.

In any case, I am all for the original project, of studying compilers,
UB, and optimization. If it doesn't really help speed up problems, but
does slow down debugging, maybe it isn't worth doing.

[toc] | [prev] | [next] | [standalone]

#3344

On Tue, 10 Jan 2023 17:32:28 +0100, David Brown
<david.brown@hesbynett.no> wrote:

[ UB example: generated code assumes bool parameter is only 0 or 1 and
mishandles anything else, but misdeclared call passes 2 ]

> This is clearly wrong - clearly undefined behaviour.  And the result
> would be a formatted disk.  But there is nothing wrong with the
> compiler's generated code.  I have seen other occasions when compiler's
> have made code with booleans that appear to be both true and false, or
> neither true nor false, as a result of undefined behaviour setting the
> underlying memory to something other than 0 or 1, simply because that
> was the result of the most efficient code.
>
FWIW -- back in the 80s the VAX FORTRAN compiler checked only the _low
bit_ of a LOGICAL variable (stored as a byte or a 4-byte word, I
forget which) because this was faster. People often reused (scarce and
expensive) memory then and such a variable might accidentally get set
to a value other than 0 or 1, producing surprising/confusing results.

In those days DEC was vigorously opposing C (they had BLISS instead)
and Unix, so there was no DEC C compiler, though I'm pretty sure there
was a DECUS (user group) one, and of course there was not yet a C
standard at all much less one including bool.

[toc] | [prev] | [next] | [standalone]

#3283

"Lucian Popescu" <lucic71@ctrl-c.club> writes:
>I'm currently working on an academic project that analyzes the speedup gain of
>Undefined Behavior Optimizations in C.

Some earlier work:

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

The most interesting part wrt. topic is section 3.3: They compiled
SPECint 2006 with gcc and clang, with either the default options, or
with defining the behaviour with the options -fno-strict-overflow (or
-fwrapv) -fno-delete-null-pointer-checks -fno-strict-aliasing, which
disables most of what you call "UB Optimizations" in the compiler
versions they used (and probably still disables most "UB
Optimizations"; there have been new -fno-* flags added, corresponding
to some of the new "UB Optimizations", but I expect that the early "UB
Optimizations" have the most impact (you would not start with
low-impact "optimizations").

The results were that in 10 of 12 programs, there was no significant
performance difference.  In 2 of the 12 programs, there were speed
differences by factors 1.072, 1.09, 1.063 and 1.118 (depending on
program and compiler used).

However, they also found that these speed differences are due to a
single place in the source code of each of the two programs, and that
a small change to the source code of each program could eliminate the
speed difference.

@InProceedings{ertl15kps,
  author =       {M. Anton Ertl},
  title =        {What every compiler writer should know about programmers},
  crossref =	 {kps15},
  pages =	 {112--133},
  url =          {http://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_2015_submission_29.pdf},
  abstract =     {In recent years C compiler writers have taken the
                  attitude that tested and working production (i.e.,
                  \emph{conforming} according to the C standard) C
                  programs are buggy if they contain undefined
                  behavior, and they feel free to compile these
                  programs (except benchmarks) in a way that they no
                  longer work.  The justification for this attitude is
                  that it allows C compilers to optimize better.  But
                  while these ``optimizations'' provide a factor 1.017
                  speedup with Clang-3.1 on SPECint 2006, for
                  non-benchmarks it also has a cost: if we go by the
                  wishes of the compiler maintainers, we have to
                  ``fix'' our working, conforming C programs; this
                  requires a substantial effort, and can result in
                  bigger and slower code.  The effort could otherwise
                  be invested in source-level optimizations by
                  programmers, which can have a much bigger effect
                  (e.g., a factor $>2.7$ for Jon Bentley's traveling
                  salesman program).  Therefore, optimizations that
                  assume that undefined behavior does not exist are a
                  bad idea not just for security, but also for the
                  performance of non-benchmark programs.}
}

@Proceedings{kps15,
  title =        {18. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'15)},
  booktitle =    {18. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'15)},
  year =         {2015},
  key =          {KPS '15},
  editor =       {Jens Knoop and M. Anton Ertl},
  url = 	 {http://www.complang.tuwien.ac.at/kps2015/proceedings/},
  url-pdf = 	 {http://www.complang.tuwien.ac.at/kps2015/proceedings/kps15.pdf}
}

In section 4.2 I use the same way to determine the effectiveness of
"UB Optimizations" (called "optimizations" (with quotes) in the
paper), but with a longer list of flags for gcc-5.2.0:

-fno-aggressive-loop-optimizations -fno-unsafe-loop-optimizations
-fno-delete-null-pointer-checks -fno-strict-aliasing
-fno-strict-overflow -fno-isolate-erroneous-paths-dereference
-fwrapv

I used 8 different versions of Jon Bentley's Traveling Salesman
program translated to C (from Pascal).  I found that for clang-3.5 the
flags made no difference (same binary) for any of the programs, while
for gcc-5.2.0 they made no difference in the binary for three of the
programs and no significant speed difference for two more programs.
For the remaining programs, the "speedups" from "UB Optimizations"
were by a factor of 1.04, 0.95, and 1.02.

It contrasts this with the speedup seen from source-level (manual)
optimizations: The 8 programs were successive steps in manual
optimization.  The speedup seen here was a factor 2.7 when using
gcc-5.2.0 -O3 and more for other compilers.

>I argue that UB Optimizations introduce
>more risks than actual speedup gains.

It's hard to quantify the risks.

My argument has been that it is cheaper and much more effective to
perform manual optimization than to ensure that a C program contains
no undefined behaviour.

>Don't get me wrong, I'm not saying that the compiler should magically
>understand situations where the programmer makes UB mistakes and then
>repair them. What I'm saying is that the compiler should compile the code
>"as is" without making smart optimization transformations that break the
>intention of the programmer.

To which the advocates of "UB Optimizations" react by claiming that
they don't know the intention.  So I have written a followup paper
that discusses this aspect in more depth:

@InProceedings{ertl17kps,
  author =       {M. Anton Ertl},
  title =        {The Intended Meaning of \emph{Undefined Behaviour}
                  in {C} Programs},
  crossref =     {kps17},
  pages =        {20--28},
  url =          {http://www.complang.tuwien.ac.at/papers/ertl17kps.pdf},
  url2 =         {http://www.kps2017.uni-jena.de/proceedings/kps2017_submission_5.pdf},
  abstract =     {All significant C programs contain undefined
                  behaviour. There are conflicting positions about how
                  to deal with that: One position is that all these
                  programs are broken and may be compiled to arbitrary
                  code.  Another position is that tested and working
                  programs should continue to work as intended by the
                  programmer with future versions of the same C
                  compiler. In that context the advocates of the first
                  position often claim that they do not know the
                  intended meaning of a program with undefined
                  behaviour. This paper explores this topic in greater
                  depth. The goal is to preserve the behaviour of
                  existing, tested programs. It is achieved by letting
                  the compiler define a consistent mapping of C
                  operations to machine code; and the compiler then
                  has to stick to this behaviour during optimizations
                  and in future releases.}
}

@Proceedings{kps17,
  title =        {19. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'17)},
  booktitle =    {19. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'17)},
  year =         {2017},
  key =          {KPS '17},
  editor =       {Wolfram Amme and Thomas Heinze},
  url = 	 {http://www.kps2017.uni-jena.de/kps2017_proceedings.html},
  url-pdf = 	 {http://www.kps2017.uni-jena.de/proceedings/kps2017.pdf}
}

>My current progress is here [2]. I did not start the technical work, ATM I only
>have the research proposal. I reached you to see if you have any feedback
>on this proposal.
[[2] https://tildegit.org/lucic71/dissertation/src/branch/master/TSW/tsw.pdf]

I have read Section III and IV of this paper.

Section III: You cite my 2015 paper above.  About SPECInt 2006, I
cited only Wang et al.'s paper (and compute the overall SPECInt
difference based on their numbers).  For the traveling salesman
program, the speedup factor of 2.7 (or more, depending on compiler and
optimization level) is for source-level (i.e., manual) optimization,
not "UB Optimization".  The numbers for "UB Optimization" are, as
mentioned above, usually a factor of 1, and in the three cases where
there is a difference, it's a factor 1.04, 0.95, and 1.02, as
mentioned above.

Section IV: You have the beginnings of a plan to evaluate the
performance; you leave the question of benchmarks open until you know
what changes in the resulting code are due to "UB Optimization".  It's
not clear what the point of such a benchmark selection would be.  It
certainly would not make the selection more representative, and would
have the smell of cherry-picking.  Also, "UB Optimization" may cause
changes in thousands of places in the code of OpenBSD, but only few of
those places will be in hot code and be relevant for performance.

What I miss is a plan to quantify the risks.  Wang et al. made a
pretty good case (as far as I am concerned, but the "UB Optimization"
faithful remain unconvinced) in one of their papers when they analysed
all the Debian packages.

One question is: Given Wang et al.'s earlier work, what is the
original contribution of your intended research?

I discuss some alternative research topics in Section 5.4 of my 2015
paper.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

[toc] | [prev] | [next] | [standalone]

#3294

On 2023-01-05, Lucian Popescu <lucic71@ctrl-c.club> wrote:
> Hi,
>
> I'm currently working on an academic project that analyzes the speedup gain of
> Undefined Behavior Optimizations in C. I argue that UB Optimizations introduce
> more risks than actual speedup gains. This happens because most of the time
> the compiler does not have the context to understand the intention of the
> programmer in code that contains UB. For example this fast inverse square root
> function [1] triggers UB at this line: i  = * ( long * ) &y;. A "smart"
> compiler could delete this line as an optimization because it contains UB.

"(Lack of) UB optimizations" are based on these ideas:

1. The programmer is infallible, and therefore
2. Any interpretation of the code's meaning which entails undefined
   behavior must be incorrect and unintended; and also
3. If some construct has no interpretation that is not UB, the
   programmer must be saying that that code is unreachable.

They are pretty terrible engineering.

Assuming a lack of undefined behavior in C is simply foolish; it's
extremely unlikely to be correct for any nontrivial program. A
compiler processing just tens of thousands of lines of C is likely to
be incorrect a few times in making a no-UB assumption.

In regard to 3, there are actually some extensions being proposed to C
whereby the programer can insert an expression which means "this code
is not reached", and the only semantics of that expression is that it
has undefined behavior. Since the programmer would never intend
undefined behavior, by (3) above it implies that the construct is not
reached. The compiler can replace it by an infinite loop, abortive
exit, reformatting of the disk, or whatever. Or just generate no
instructions at all.

I simply cannot get behind the idea of a deliberately introduced
language construct that has nothing but undefined behavior. I
understand that it's efficient: the compiler can reason about that not
being reachable, and not expend any instructions for it that would add
to the code size. I would rather have spend the code size to have it
stop. Just stick a breakpoint trap instruction in there or whatever.

> Don't get me wrong, I'm not saying that the compiler should magically
> understand situations where the programmer makes UB mistakes and then
> repair them. What I'm saying is that the compiler should compile the code
> "as is" without making smart optimization transformations that break the
> intention of the programmer.

I echo that serntiment. I don't require optimizations of the form
"assuming expression X is always well-defined, thus can translate some
other expression Y as follows".

In C, the programmer is supposed to do a lot of the optimizing.

In spite of these UB-related shennanigans, new developments in compilers
like GCC are not improving this basic fact.

You still have to know the tight coding techniques from 1990 in order
to get good code out of the latest GCC.

In the 1990's, I compared code for deleting from a linked list:

   node->next->prev = node->prev;
   node->prev->next = node->next;

versus:

   node_t *next = node->next;
   node_t *prev = node->prev;

   next->prev = prev;
   prev->next = next;

I get the same results today as I did in 1990-something: a shorter
instruction sequence for the code in which I cached the pointers in
local variables! This is because the compiler suspects that
the first assignment "node->next->prev = node->prev"
might or might not have affected the value of "node->prev";
so that has to be loaded again; it cannot be subject to CSE. Strict
aliasing reasoning doesn't help because everything has the same node_t *
type.

(But, note! If the assignment node->next->prev = node->prev
affects node->prev, that could only be becauase node->next == node.
And in that case, the assignment is a no-op: the cached node->prev
value could be used to avoid accesing that location again! GCC is not
yet smart enough to figure this out: and nobody needs it to be.)

A C compiler just needs to obey the memory accesses the programmer
expressed, figure out which local variables to keep in registers,
and do some basic things with loops, inlining and whatnot; and
have good basic optimizations like control flow stuff (jump thraeding
and whatnot), peephole optimizations, CSE, ...

Approaches like "oh this loop must be infinite because it nothing but
increments the dummy variable and tests for it going negative" just have
no place in engineering; that's just someone dicking around to get their
name in the git history of the compiler, and stuff their resume.

If you want an optimal instruction sequence for something, there is
always assembly language.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.compilers

csiph-web