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

Groups > comp.lang.c > #67773 > unrolled thread

Re: the language (and the role of Undefined Behavior therein)

Back to article view | Back to comp.lang.c

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-18 16:19 -0700
    Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-18 21:15 -0400
      Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-19 10:11 -0700
        Re: the language (and the role of Undefined Behavior therein) Ike Naar <ike@iceland.freeshell.org> - 2015-08-19 19:58 +0000
          Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-19 14:09 -0700
        Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-19 16:10 -0400
          Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-19 16:01 -0700
            Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-19 20:23 -0400
              Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 10:35 -0700
                Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-20 12:32 -0700
                  Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 13:31 -0700
                    Re: the language (and the role of Undefined Behavior therein) donalhambra@gmail.com - 2015-08-20 14:23 -0700
                      Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 16:13 -0700
                    Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-20 17:48 -0700
                      Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-21 01:32 -0700
                        Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-21 18:34 -0700
                          Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-21 22:11 -0700
                            Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-22 09:41 -0400
                              Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-22 16:59 +0000
                                Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-22 23:30 -0400
                                  Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-24 03:36 +0000
                                    Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-24 00:25 -0400
                                      Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 22:57 -0700
                                        Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-24 19:49 +0000
                                  Re: the language (and the role of Undefined Behavior therein) Tim Rentsch <txr@alumni.caltech.edu> - 2015-09-06 14:43 -0700
                              Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 16:27 -0700
                                Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-23 21:15 -0400
                                  Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 20:18 -0700
                            Re: the language (and the role of Undefined Behavior therein) raltbos@xs4all.nl (Richard Bos) - 2015-08-22 14:37 +0000
                          Re: the language (and the role of Undefined Behavior therein) David Kleinecke <dkleinecke@gmail.com> - 2015-08-22 19:12 -0700
                            Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-22 23:38 -0400
                              Re: the language (and the role of Undefined Behavior therein) David Kleinecke <dkleinecke@gmail.com> - 2015-08-23 20:01 -0700
                                Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-23 21:56 -0700
                                  Re: the language (and the role of Undefined Behavior therein) David Kleinecke <dkleinecke@gmail.com> - 2015-08-24 17:25 -0700
                                    Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-24 18:21 -0700
                                    Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-24 22:22 -0400
                                      Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-25 14:31 +0000
                                        Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-25 09:22 -0700
                                          Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-25 18:55 +0000
                                          Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-25 12:33 -0700
                                            Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-25 16:23 -0700
                                Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-24 00:31 -0400
                                  Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-24 10:32 -0700
                            Re: the language (and the role of Undefined Behavior therein) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-08-22 23:54 -0700
                            Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-24 03:45 +0000
                          Re: the language (and the role of Undefined Behavior therein) Tim Rentsch <txr@alumni.caltech.edu> - 2015-09-07 08:11 -0700
        Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-23 18:46 -0400
          Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 19:04 -0700
            Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-23 23:40 -0400
              Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 22:48 -0700
                Re: the language (and the role of Undefined Behavior therein) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-08-24 00:38 -0700
    Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-18 21:22 -0400
    Re: the language (and the role of Undefined Behavior therein) Ike Naar <ike@iceland.freeshell.org> - 2015-08-20 21:44 +0000
      Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 16:48 -0700
      Re: the language (and the role of Undefined Behavior therein) Philip Lantz <prl@canterey.us> - 2015-08-20 23:41 -0700

Page 1 of 3  [1] 2 3  Next page →

#67773 — Re: the language (and the role of Undefined Behavior therein)

On Saturday, December 20, 2014 at 12:36:33 PM UTC-6, James Kuyper wrote:
> It might seem perverse to produce any other result - until you consider
> optimizations. A shift expression could be optimized completely out of
> the generated code, or it could be combined with another expression, and
> the combination might be replaced by a different set of instructions
> that is better for some reason. As long as the alternative instructions
> have behavior that matches the standard's requirements, when it imposes
> some, it doesn't matter what the alternative code does when the behavior
> is undefined.

A problem with that thinking is that it precludes the possibility of optimizing code based on a programmer's willingness to accept range of behaviors.  Consider the following requirement and a method written in C to meet it:

    /* Requirement 1: If n is 0 to 31, return the value of dat
                      shifted left by n bits. */
    uint32_t shl(uint32_t dat, uint32_t n)
    {
      return dat << n;
    }

Nice and simple, and compilers for many processors will be able to optimize it.  Now add one more requirement:

    /* Requirement 2: If n is greater than 31, arbitrarily return either 0 or
                      dat << (n & 31) */

Feeding the simple code to vast majority of compilers written before 2009 would yield code meeting that requirement by default, though some compilers have "pedantic" or "diagnostic" modes where it would trap.  Newer compilers, however, would require use something like one of the following, each of which can only yield optimal code with certain processors.

    uint32_t shl_v1(uint32_t dat, uint32_t n) // Optimal for PC
    {
      return dat << (n & 31);
    }
    uint32_t shl_v2(uint32_t dat, uint32_t n) // Optimal for ARM
    {
      return (n & 255) < 32 ? dat << (n & 31) : 0;
    }

Any strictly-complaint means of writing the code will require that the programmer select one of the above behaviors when n>=32, even if the programmer would be equally happy with either.  Consequently, the effect of making a shift by 32 Undefined Behavior is that it will no longer be possible for both ARM and x86 compilers to generate the most efficient code meeting programmer requirements.

A major key to facilitating behavior-based optimization in usable programs is that it should be possible to write code whose behavior is sufficiently constrained to meet programmer requirements, but loosely-enough constrained to allow a compiler some flexibility.  Consider the following requirements/function:

    /* Requirement 1: If the arithmetical values of a*b and c*d are
                      both representable as int, return 1 if a*b > c*d
                      and 0 otherwise. */
    int mulcomp(int a, int b, int c, int d)
    {
      return a*b > c*d;
    }

Nice and simple, easy to read, and easy to optimize on a wide range of platforms.  Now add one more requirement:

    /* Requirement 2: Do not negate the laws of time and causality, even if
                      a*b or c*d is outside the range of int */

Requirement 2 is just about the loosest requirement imaginable, and should be a "gimme".  Unfortunately, since Undefined Behavior is allowed to negate the laws of time and causality (and on hyper-modern compilers it is prone to do so), it's not possible to meet requirement 1 with a function which is easily readable and will yield optimal code on all compilers.  If one assumes that a long can hold the product of any two int values, the code could be written as:

    int mulcomp(int a, int b, int c, int d)
    {
      return (long)a*b > (long)c*d;
    }

but that would likely be slow on many platforms--sometimes severely so.  Writing the code as 

    int mulcomp(int a, int b, int c, int d)
    {
      return (int)((unsigned)a*b) > (int)((unsigned)c*d);
    }

would work on most two's-complement platforms, but would yield sub-optimal performance on many DSPs.  Further, the function is a lot less readable than the original, and ends up spending more code meeting what should be a "gimme" requirement than performing its primary purpose.

[toc] | [next] | [standalone]

#67778

On 8/18/15 7:19 PM, supercat@casperkitty.com wrote:
> On Saturday, December 20, 2014 at 12:36:33 PM UTC-6, James Kuyper wrote:
>> It might seem perverse to produce any other result - until you consider
>> optimizations. A shift expression could be optimized completely out of
>> the generated code, or it could be combined with another expression, and
>> the combination might be replaced by a different set of instructions
>> that is better for some reason. As long as the alternative instructions
>> have behavior that matches the standard's requirements, when it imposes
>> some, it doesn't matter what the alternative code does when the behavior
>> is undefined.
>
> A problem with that thinking is that it precludes the possibility of
>optimizing code based on a programmer's willingness to accept range of
>behaviors. Consider the following requirement and a method written in C
>to meet it:
>
>      /* Requirement 1: If n is 0 to 31, return the value of dat
>                        shifted left by n bits. */
>      uint32_t shl(uint32_t dat, uint32_t n)
>      {
>        return dat << n;
>      }
>
> Nice and simple, and compilers for many processors will be able to optimize it.  Now add one more requirement:
>
>      /* Requirement 2: If n is greater than 31, arbitrarily return either 0 or
>                        dat << (n & 31) */
>

If you are going to write your requirements to match 'common' machines 
in an attempt to optimize, you should be willing to expect that you are 
going to rely on machine dependent behavior. This is NOT the case that 
it will work naively on all machines. I seem to remember machines that 
would trap on excessive value on over sized values on register based 
shifts (I do admit it is very uncommon). If you want to be strictly 
conforming, you need to be strictly conforming.


> Feeding the simple code to vast majority of compilers written before
> 2009 would yield code meeting that requirement by default, though some
> compilers have "pedantic" or "diagnostic" modes where it would trap.
> Newer compilers, however, would require use something like one of the
> following, each of which can only yield optimal code with certain
> processors.
>
>      uint32_t shl_v1(uint32_t dat, uint32_t n) // Optimal for PC
>      {
>        return dat << (n & 31);
>      }
>      uint32_t shl_v2(uint32_t dat, uint32_t n) // Optimal for ARM
>      {
>        return (n & 255) < 32 ? dat << (n & 31) : 0;
>      }
>

My guess is that even today, as an independent function most compilers 
will do the simple thing in the original shift function. That IS the 
simplest code. You may need to separately compile the function on an 
aggressive compiler to keep it from propagating the permissions of 
undefined behavior against the callers.


> Any strictly-complaint means of writing the code will require that
> the  programmer select one of the above behaviors when n>=32, even if the
> programmer would be equally happy with either. Consequently, the effect
> of making a shift by 32 Undefined Behavior is that it will no longer be
> possible for both ARM and x86 compilers to generate the most efficient
> code meeting programmer requirements.
>
> A major key to facilitating behavior-based optimization in usable
> programs is that it should be possible to write code whose behavior is
> sufficiently constrained to meet programmer requirements, but
> loosely-enough constrained to allow a compiler some flexibility.
> Consider the following requirements/function:
>
>      /* Requirement 1: If the arithmetical values of a*b and c*d are
>                        both representable as int, return 1 if a*b > c*d
>                        and 0 otherwise. */
>      int mulcomp(int a, int b, int c, int d)
>      {
>        return a*b > c*d;
>      }
>
> Nice and simple, easy to read, and easy to optimize on a wide range of platforms.  Now add one more requirement:
>
>      /* Requirement 2: Do not negate the laws of time and causality, even if
>                        a*b or c*d is outside the range of int */
>
> Requirement 2 is just about the loosest requirement imaginable, and
> should be a "gimme". Unfortunately, since Undefined Behavior is allowed
> to negate the laws of time and causality (and on hyper-modern compilers
> it is prone to do so), it's not possible to meet requirement 1 with a
> function which is easily readable and will yield optimal code on all
> compilers. If one assumes that a long can hold the product of any two
> int values, the code could be written as:
>
>      int mulcomp(int a, int b, int c, int d)
>      {
>        return (long)a*b > (long)c*d;
>      }
>
> but that would likely be slow on many platforms--sometimes severely so.  Writing the code as

Any decent compiler will use the int*int->long multiply instruction in 
this case. It KNOWS the values are only int sized. Only a very dumb 
compiler would slow down on this, and that one would likely do the 
'right' thing on the first case.

Also, Undefined Behavior grants the implementation permission to break 
the laws of time and causality, it doesn't grant it the ability. If the 
implementers actually could break this, they are in the wrong business!

>
>      int mulcomp(int a, int b, int c, int d)
>      {
>        return (int)((unsigned)a*b) > (int)((unsigned)c*d);
>      }
>
> would work on most two's-complement platforms, but would yield
> sub-optimal performance on many DSPs. Further, the function is a lot
>less readable than the original, and ends up spending more code meeting
> what should be a "gimme" requirement than performing its primary purpose.
>

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

#67825

On Tuesday, August 18, 2015 at 8:15:50 PM UTC-5, Richard Damon wrote:
> >      /* Requirement 2: If n is greater than 31, arbitrarily return either 0 or
> >                        dat << (n & 31) */
> >
> 
> If you are going to write your requirements to match 'common' machines 
> in an attempt to optimize, you should be willing to expect that you are 
> going to rely on machine dependent behavior. This is NOT the case that 
> it will work naively on all machines. I seem to remember machines that 
> would trap on excessive value on over sized values on register based 
> shifts (I do admit it is very uncommon). If you want to be strictly 
> conforming, you need to be strictly conforming.

My point is that since there are a substantial number of real-world applications where code returning either of the indicated values would be fine, and real-world processors are split as to which value they will naturally return, the goal of producing optimal machine code will be best realized if there is a way to indicate that either result will be acceptable; my preferred way of doing that would be to have a set of standardized macros that a program could use compile-time assertions with its requirements, such that every compiler would be required to either yield the behavior indicated by the macros or regard the program as ill-formed, and define a standard of compliance for programs which will yield correct behavior on any platform meeting the documented requirements.

> My guess is that even today, as an independent function most compilers 
> will do the simple thing in the original shift function. That IS the 
> simplest code. You may need to separately compile the function on an 
> aggressive compiler to keep it from propagating the permissions of 
> undefined behavior against the callers.

Of course compilers would do the simple thing in a standalone function.  The problem is that the only Standard-defined way to force them not to propagate UB against the caller is to explicitly specify a behavior which may be the simplest on some platforms, but needlessly complex on others.

> Any decent compiler will use the int*int->long multiply instruction in 
> this case. It KNOWS the values are only int sized. Only a very dumb 
> compiler would slow down on this, and that one would likely do the 
> 'right' thing on the first case.

Even if a compiler for a 16-bit machine recognizes that a 16x16->32 multiply will suffice, casting to long would still require it to do work with the high-order word of the result which would be necessary to meet the C Standard, but useless from the perspective of meeting requirements.

Conversely, some 16-bit DSPs have a 16x16+32->32 multiply-accumulate instruction which would work very nicely to compute (long)a*b-(long)c*d, but could only compute the expression which truncated to unsigned and then to int by storing the first product to memory, computing the second, sign-extending that, and then subtracting the first.

> Also, Undefined Behavior grants the implementation permission to break 
> the laws of time and causality, it doesn't grant it the ability. If the 
> implementers actually could break this, they are in the wrong business!

Not really.

    #include <stdio.h>

    int blah(int mode, int a, int b)
    {
      printf("[%d %d]\n",a,b); flush(stdout);
      if (mode == 33)
        launch_nuclear_missiles(); // Terminates program execution
      return mulcomp(a, 2, b, 3);
    }

    int main(void)
    {
      int ch = getch();
      int sum;
      sum += blah(9,ch,ch+2);
      sum += blah(ch,INT_MAX,ch);
      printf("%d",sum);
      return 0;
    }

Program execution will be defined if ch equals 33.  It might be defined on some platforms if ch is not 33 but a printf or flush(stdout) raises a SIGPIPE before the "if" gets invoked the second time.  It the "if" gets reached the second time with any mode value other than 33, however, the Standard will allow the compiler is allowed to travel backward in time from the overflow in mulcomp() and decide that mode holds the value 33 even if nothing ever assigns it that value.

BTW, suppose one wanted to make the indicated requirement for mulcomp() even on a platform where all signed types larger than char had the same positive range (legal if unsigned types have one more padding bit than signed types), would there be any strictly-compliant way one could write it that would be efficient and make its purpose obvious?

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

#67836

On 2015-08-19, supercat@casperkitty.com <supercat@casperkitty.com> wrote:
>> Also, Undefined Behavior grants the implementation permission to break 
>> the laws of time and causality, it doesn't grant it the ability. If the 
>> implementers actually could break this, they are in the wrong business!
>
> Not really.
>
>     #include <stdio.h>
>
>     int blah(int mode, int a, int b)
>     {
>       printf("[%d %d]\n",a,b); flush(stdout);
>       if (mode == 33)
>         launch_nuclear_missiles(); // Terminates program execution
>       return mulcomp(a, 2, b, 3);
>     }
>
>     int main(void)
>     {
>       int ch = getch();
>       int sum;
>       sum += blah(9,ch,ch+2);
>       sum += blah(ch,INT_MAX,ch);
>       printf("%d",sum);
>       return 0;
>     }
>
> Program execution will be defined if ch equals 33.

After

  int sum;

the value of sum is indeterminate, and the behaviour of

  sum += blah(9,ch,ch+2);

is undefined, even if ch equals 33.

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

#67845

On Wednesday, August 19, 2015 at 3:00:44 PM UTC-5, Ike Naar wrote:
>   int sum;
> 
> the value of sum is indeterminate, and the behaviour of
> 
>   sum += blah(9,ch,ch+2);

Mea culpa; I forgot to initialize it.  My intent was to try to make every line of "blah" relevant in at least some circumstances, though to really achieve that I would have to make the second call to blah() conditional on something [e.g. (ch & 1)].  Some compilers will warn if dead-code elimination removes a piece of code from all execution paths, but not it eliminates code from some inline expansions of a function but not all of them.

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

#67838

On 08/19/2015 01:11 PM, supercat@casperkitty.com wrote:
> On Tuesday, August 18, 2015 at 8:15:50 PM UTC-5, Richard Damon wrote:
...
>> Also, Undefined Behavior grants the implementation permission to break 
>> the laws of time and causality, it doesn't grant it the ability. If the 
>> implementers actually could break this, they are in the wrong business!
> 
> Not really.
> 
>     #include <stdio.h>
> 
>     int blah(int mode, int a, int b)
>     {
>       printf("[%d %d]\n",a,b); flush(stdout);
>       if (mode == 33)
>         launch_nuclear_missiles(); // Terminates program execution
>       return mulcomp(a, 2, b, 3);
>     }
> 
>     int main(void)
>     {
>       int ch = getch();
>       int sum;
>       sum += blah(9,ch,ch+2);
>       sum += blah(ch,INT_MAX,ch);
>       printf("%d",sum);
>       return 0;
>     }
> 
> Program execution will be defined if ch equals 33. It might be
> defined on some platforms if ch is not 33 but a printf or
> flush(stdout) raises a SIGPIPE before the "if" gets invoked the second time.
> It the "if" gets reached the second time with any mode value other than 33,
> however, the Standard will allow the compiler is allowed to travel backward
> in time from the overflow in mulcomp() and decide that mode holds the value
> 33 even if nothing ever assigns it that value.

The standard may allow time travel, but that doesn't make it actually
possible. And if an implementation does know how to generate code that
has the effect of traveling backwards in time, then there are much more
profitable uses of that technology than using it to confuse those who
choose to write code with undefined behavior.
What is both permitted by the standard, and unambiguously possible in
the real world, is that as soon as the code reaches a point where a
value of 33 is the only way to avoid undefined behavior, the program can
start executing code that does pretty much anything, if the value isn't
33. This is because the standard says that it's the entire program that
has undefined behavior, not just the particular line of code whose
execution renders the behavior undefined. As a result, unexpected
behavior could start occurring long before execution of that line. In
fact, it could even have the result of preventing that line of code from
ever actually being executed. But this isn't time travel, it's just a
permitted optimization.

...
> BTW, suppose one wanted to make the indicated requirement for
> mulcomp() even on a platform where all signed types larger than char
> had the same positive range (legal if unsigned types have one more
> padding bit than signed types), ...

As far as I can tell, every signed type (including signed char) can have
the same positive range, whether or not unsigned types have any padding
bits. Could you explain why you think unsigned padding bits would be
needed in order for such an implementation to be conforming?

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

#67856

On Wednesday, August 19, 2015 at 3:10:58 PM UTC-5, James Kuyper wrote:
> What is both permitted by the standard, and unambiguously possible in
> the real world, is that as soon as the code reaches a point where a
> value of 33 is the only way to avoid undefined behavior, the program can
> start executing code that does pretty much anything, if the value isn't
> 33.

I'd say such behavior effectively frees the abstract machine from the laws of time and causality.  Normal rules of time and causality would imply that "if (foo==23) bar();" may only execute "bar()" if the program receives input which could, for some combination of specified and unspecified behaviors that could have occurred up to that point, cause "foo" to equal 23.  On some compilers, Undefined Behavior negates those rules.

I agree that the present standard as written allows such an optimization; I would posit, however, that the inability for code to demand more constrained behaviors is a defect in the Standard.  The freedoms which hyper-modern compiler writers are claiming with respect to UB won't improve optimizations, but quite the opposite, as they will force programmers to write huge amounts of ugly and inefficient code for the purpose of ensuring that compilers never get to use the freedoms they've claimed for themselves.

I have a strong suspicion that the apparent mania for this style of optimization stems from some experiments which took pieces of code which relied upon behavior which many C compilers supported but which was not required by the standard, and perceived that huge efficiency gains should be possible.  I am highly skeptical that it offers any benefits which could not be obtained more cheaply and easily, and with far less collateral damage, via other means.

> As far as I can tell, every signed type (including signed char) can have
> the same positive range, whether or not unsigned types have any padding
> bits. Could you explain why you think unsigned padding bits would be
> needed in order for such an implementation to be conforming?

While it's often possible to work around C's lack of UB-safe integer math by converting values to unsigned types, using unsigned arithmetic, and then converting the results back to signed types, that will only work if unsigned types have more value bits than signed types--something which is not required by the Standard, and thus cannot be relied upon in a strictly-conforming program.

Thus my challenge to you: can you offer a strictly-compliant version of "mulcomp" which yields the correct result in all cases defined by the current Standard, and has no side-effect other than yielding a value or terminating the program, and have such a function (1) be clear and understandable to a human, and (2) compile to code which is no more than twice as big and slow the original when given to the best available x86 compiler [without cheating by omitting the code necessary to handle irksome integer sizes when using a platform with nicer ones].

Originally, the C Standard left many behaviors undefined because different platforms had mutually-exclusive behaviors which would be useful in different situations, and mandating any particular behavior would prevent programmers from exploiting behaviors of their platforms which would have been useful to them but were contrary to the Standard.  C thrived as a family of languages because differing dialects could offer different tradeoffs among various goals so as to best suit the users of those implementations.

I would posit that most programs are required to produce correct output when given valid input, and to refrain from launching nukes when given invalid input.  A good language or dialect should strive to allow code with those requirements to focus on the first one.  The dialects of C which were supported by pre-2009 compilers generally did that.  Hyper-modern C does the opposite.  I would consider dialects which allow a concisely-written "mulcomp" to meet both of its requirements to be superior to those where meeting the second requirement adds an absurd amount of complexity and would block what would otherwise be simple and useful optimizations.

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

#67863

On 08/19/2015 07:01 PM, supercat@casperkitty.com wrote:
> On Wednesday, August 19, 2015 at 3:10:58 PM UTC-5, James Kuyper wrote:
>> What is both permitted by the standard, and unambiguously possible in
>> the real world, is that as soon as the code reaches a point where a
>> value of 33 is the only way to avoid undefined behavior, the program can
>> start executing code that does pretty much anything, if the value isn't
>> 33.
> 
> I'd say such behavior effectively frees the abstract machine from
> the laws of time and causality. Normal rules of time and causality would
> imply that "if (foo==23) bar();" may only execute "bar()" if the program
> receives input which could, for some combination of specified and
> unspecified behaviors that could have occurred up to that point, cause
> "foo" to equal 23. On some compilers, Undefined Behavior negates those
> rules.

Well, the actual laws of time and causality are not written in such a
way as to allow you to justify that conclusion. They require only that a
cause of an effect be separated from the effect it causes by an amount
of time greater than the time required for light to travel from the
location of the cause to the location of the effect. In particular, the
way I worded that implies that the time must be positive. The ultimate
cause of the execution of bar() is the fact that the compiler performed
the optimization, which occurs long before the effect; light has plenty
of time to travel from the location where the optimization was performed
to the location where the optimized code was executed.

The laws of time and causality don't say that foo==32 has to cause bar()
to be executed - it's the C standard which says that; and it only says
it in contexts where the behavior is defined. When the behavior is
undefined, the standard revokes that requirement, so a compiler can
generate code (which behaves strictly according to the laws of time and
causality) to produce a result quite different from that one.

> I agree that the present standard as written allows such an
> optimization; I would posit, however, that the inability for code to
> demand more constrained behaviors is a defect in the Standard. The
> freedoms which hyper-modern compiler writers are claiming with respect
> to UB won't improve optimizations, but quite the opposite, as they will
> force programmers to write huge amounts of ugly and inefficient code for
> the purpose of ensuring that compilers never get to use the freedoms
> they've claimed for themselves.

That would be odd, because currently, the amount of ugly and inefficient
code required to avoid undefined behavior is relatively minor.

>> As far as I can tell, every signed type (including signed char) can have
>> the same positive range, whether or not unsigned types have any padding
>> bits. Could you explain why you think unsigned padding bits would be
>> needed in order for such an implementation to be conforming?
> 
> While it's often possible to work around C's lack of UB-safe integer
> math by converting values to unsigned types, using unsigned arithmetic,
> and then converting the results back to signed types, that will only
> work if unsigned types have more value bits than signed types--something
> which is not required by the Standard, and thus cannot be relied upon in
> a strictly-conforming program.

OK - I think you worded your comment poorly. You seemed to be saying
that an implementation in which all signed types had the same positive
type would not be legal unless the corresponding unsigned types had
padding bits.

Instead, it seems that you're saying that the signed types are the ones
that have to have padding bits, and the reason they need those bits is
not to legally conform to the standard, but only in order to make your
work-around work.

> Thus my challenge to you: can you offer a strictly-compliant version
> of "mulcomp" which yields the correct result in all cases defined by the
> current Standard, and has no side-effect other than yielding a value or
> terminating the program, and have such a function (1) be clear and
> understandable to a human, and (2) compile to code which is no more than
> twice as big and slow the original when given to the best available x86
> compiler [without cheating by omitting the code necessary to handle
> irksome integer sizes when using a platform with nicer ones].

No, I cannot. Avoiding unexpected side-effects on all platforms would
require detecting the possibility of overflow without actually creating
that possibility, and there's no simple and quick way of doing that.

The right way to do this is to ensure that overflow isn't a possibility
in the first place, by understanding your problem domain to set limits
on the possible range of the value of each expression (and possibly
validating your inputs to make sure that those ranges are satisfied),
and then making sure that each expression is evaluated using a data type
capable of representing that entire range. This may require rearranging
your calculations, and special handling of nasty cases. Sometimes
there's no such data type, which would require massive rearrangement of
your calculations. However, it isn't the horrible burden you imply that
it is.

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

#67894

On Wednesday, August 19, 2015 at 7:23:08 PM UTC-5, James Kuyper wrote:

> The laws of time and causality don't say that foo==32 has to cause bar()
> to be executed - it's the C standard which says that; and it only says
> it in contexts where the behavior is defined. When the behavior is
> undefined, the standard revokes that requirement, so a compiler can
> generate code (which behaves strictly according to the laws of time and
> causality) to produce a result quite different from that one.

I am well aware that C11 says that the fact that a program is "going to"
perform Undefined Behavior makes execution undefined even before it is
invoked.  I don't think debating the terminology is helpful, though there is
a point I'm not clear on: given

    #include <stdio.h>
    int main(void)
    {
      int ch;
      printf("DO NOT press any key!\n");
      ch = getchar();
      if (ch >= 32) return 1 << ch; else return 1 >> (ch - 32);
    }

would execution be well-defined if the user doesn't hits a key before execution
is halted by some means (SIGINT, "kill -9", removal of power, etc.)?  If
getchar() returns, there will be no defined execution path (and a compiler
could probably recognize that pretty easily), and the language of C11 suggests
that UB can time-travel before I/O, but there's no way the abstract machine
could perform an invalid left-shift if getch() doesn't return a value greater
than 31, nor an invalid right-shift if getch() doesn't return a value less
than 32.  Could a compiler move the UB before the getch() despite the data
dependency?

> That would be odd, because currently, the amount of ugly and inefficient
> code required to avoid undefined behavior is relatively minor.

The amount of ugly and inefficient code employed to avoid UB seems minor
because a lot of code *doesn't* avoid it.  Instead, a lot of code was written
on the assumption that if every compiler released in the last 10+ years for a
mainstream platform would behave acceptably, future compilers would continue
to do so.

> > Thus my challenge to you: can you offer a strictly-compliant version
> > of "mulcomp" which yields the correct result in all cases defined by the
> > current Standard, and has no side-effect other than yielding a value or
> > terminating the program, and have such a function (1) be clear and
> > understandable to a human, and (2) compile to code which is no more than
> > twice as big and slow the original when given to the best available x86
> > compiler [without cheating by omitting the code necessary to handle
> > irksome integer sizes when using a platform with nicer ones].
> 
> No, I cannot. Avoiding unexpected side-effects on all platforms would
> require detecting the possibility of overflow without actually creating
> that possibility, and there's no simple and quick way of doing that.

Handling overflow in such fashion as to meet requirements cannot be done quickly
nor easily on *all* platforms, but any non-obscure hardware platform built in
the last 20 years would have no problem whatsoever performing some calculation
that would meet requirements.  Until recently, one could expect that any
non-obscure platform, given the original source code, would perform such a calculation (likely the most efficient one) unless "trap on overflow"
was explicitly requested.

Even today, programmers can and do avoid the burden by using -wrapv, but doing
so often imposes constraints on the compiler which are much tighter than what
the programmer actually needs, and also creates the danger that the code which
relies upon the -wrapv option might accidentally get compiled without it.

> The right way to do this is to ensure that overflow isn't a possibility
> in the first place, by understanding your problem domain to set limits
> on the possible range of the value of each expression (and possibly
> validating your inputs to make sure that those ranges are satisfied),
> and then making sure that each expression is evaluated using a data type
> capable of representing that entire range. This may require rearranging
> your calculations, and special handling of nasty cases. Sometimes
> there's no such data type, which would require massive rearrangement of
> your calculations. However, it isn't the horrible burden you imply that
> it is.

C was designed in an era where computers would only receive input from 
trustworthy sources.  The design of gets() is testament to that.  Today, that
is no longer true.  Programs need to be able to guarantee that their behavior
will remain within certain limits even given maliciously-crafted inputs.  A
good language should facilitate that, for example by including a family of integer types which request that a compiler detect overflows on values of those
types and indicate them in some fashion [if the Standard were to define such
types, but also a macro which would indicate whether they actually did detect
overflows, any compiler could be made compliant with the standard by defining
such types as aliases to existing ones].

Compilers are often far better equipped to handle overflow detection than user
code, especially if compilers are only required to detect overflow that yield
arithmetically-incorrect results (but are allowed to detect others).  C
programs often have sloppy overflow checking because the language makes it
impossible to write overflow-checked code without a huge performance burden
(often 30% or more), even in cases where compilers subject to loose overflow
semantics would be able to provide overflow checking almost free of charge [I
don't mean ignoring overflows--I mean reporting that overflow occurred].  In
applications which need to detect overflows, compiler support could offer a
massive speed boost.

Fundamentally, programmers know their program's requirements.  Compilers don't.
Unless a language has a means by which programmers that need to meet loose
requirements can specify what those requirements are, there is no way that
even the most brilliant compilers in the world can be expected to yield the
optimal code to meet those requirements on a variety of hardware platforms
where different edge-case behaviors are "easiest" to implement.

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

#67900

supercat@casperkitty.com writes:
> On Wednesday, August 19, 2015 at 7:23:08 PM UTC-5, James Kuyper wrote:
>> The laws of time and causality don't say that foo==32 has to cause bar()
>> to be executed - it's the C standard which says that; and it only says
>> it in contexts where the behavior is defined. When the behavior is
>> undefined, the standard revokes that requirement, so a compiler can
>> generate code (which behaves strictly according to the laws of time and
>> causality) to produce a result quite different from that one.
>
> I am well aware that C11 says that the fact that a program is "going to"
> perform Undefined Behavior makes execution undefined even before it is
> invoked.

C99 and C89/C90 say the same thing; there's been no substantial change
in the meaning of "undefined behavior".  Or am I missing something?

>           I don't think debating the terminology is helpful, though there is
> a point I'm not clear on: given
>
>     #include <stdio.h>
>     int main(void)
>     {
>       int ch;
>       printf("DO NOT press any key!\n");
>       ch = getchar();
>       if (ch >= 32) return 1 << ch; else return 1 >> (ch - 32);
>     }
>
> would execution be well-defined if the user doesn't hits a key before
> execution is halted by some means (SIGINT, "kill -9", removal of
> power, etc.)?  If getchar() returns, there will be no defined
> execution path (and a compiler could probably recognize that pretty
> easily), and the language of C11 suggests that UB can time-travel
> before I/O, but there's no way the abstract machine could perform an
> invalid left-shift if getch() doesn't return a value greater than 31,
> nor an invalid right-shift if getch() doesn't return a value less than
> 32.  Could a compiler move the UB before the getch() despite the data
> dependency?

The compiler does not "move the UB".  It generates code consistent
with the possible range of *defined* behaviors.  If the program
has undefined behavior, that range is unbounded, and the generated
code can do literally anything (any bounds are imposed by things
other than the C standard, like the capabilities of the underlying
hardware or the laws of physics).

The behavior of the above code is undefined in all circumstances.
The use of an input function muddies the waters a little bit, but
IMHO not significantly.  Any program can be terminated by external
means at any time; doing so during an input operation is not special.
A compiler can re-order operations as long as the resulting behavior
is still conforming.  If that re-ordering causes some seemingly later
operations to occur while earlier operations do not because someone
pulled the power plug, that's not a violation of the standard.

A compiler could, for example, recognize that the program's behavior is
always undefined, and reject the program with an error message to that
effect.  Or it could generate code that attempts to make demons fly out
of hour nose before the "DO NOT press any key!" message is printed.

>> That would be odd, because currently, the amount of ugly and
>> inefficient code required to avoid undefined behavior is relatively
>> minor.
>
> The amount of ugly and inefficient code employed to avoid UB seems
> minor because a lot of code *doesn't* avoid it.  Instead, a lot of
> code was written on the assumption that if every compiler released in
> the last 10+ years for a mainstream platform would behave acceptably,
> future compilers would continue to do so.

What exactly happened 10 years ago?

[...]

> Handling overflow in such fashion as to meet requirements cannot be
> done quickly nor easily on *all* platforms, but any non-obscure
> hardware platform built in the last 20 years would have no problem
> whatsoever performing some calculation that would meet requirements.
> Until recently, one could expect that any non-obscure platform, given
> the original source code, would perform such a calculation (likely the
> most efficient one) unless "trap on overflow" was explicitly
> requested.
>
> Even today, programmers can and do avoid the burden by using -wrapv,
> but doing so often imposes constraints on the compiler which are much
> tighter than what the programmer actually needs, and also creates the
> danger that the code which relies upon the -wrapv option might
> accidentally get compiled without it.

C states that arithmetic overflow has undefined behavior, but
provides no coherent mechanisms to reliably detect or avoid it.
C programmers tend to deal with that problem by ignoring it.
We tend to be lucky; most arithmetic operations *don't* overflow,
but we rarely attempt to guarantee that.  This is IMHO a flaw in
the language.

[...]

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

#67906

On Thursday, August 20, 2015 at 1:35:04 PM UTC-5, Keith Thompson wrote:
> C99 and C89/C90 say the same thing; there's been no substantial change
> in the meaning of "undefined behavior".  Or am I missing something?

I believe C11 added language to the effect that an action which invokes UB
at any point during execution renders the entire execution Undefined, even
the portion before UB was invoked.  I don't think any earlier versions of the
Standard included anything like that.

I suspect most of the people who approved the addition of such language did so
with the intention of enabling compilers to move forward pointer-dereferencing
operations (which is a generally-useful optimization); I doubt many were aware
of the kinds of UB-based "optimizations" compiler writers would implement.

> The behavior of the above code is undefined in all circumstances.
> The use of an input function muddies the waters a little bit, but
> IMHO not significantly.  Any program can be terminated by external
> means at any time; doing so during an input operation is not special.

If a program does not perform any I/O nor access any volatile variables,
there would be no mechanism by which any external means of interrupting its
execution could be guaranteed to occur prior to the actual execution of a
statement which invokes UB.  The behavior of

    extern volatile int foo;
    int bar;
    do { bar = foo; } while(bar != 0);
    return 1/bar;

would be well-defined according to the standard if foo never reads as zero,
since a compiler is not allowed to assume that a loop which accesses at least
one externally-visible volatile variable will ever exit.  I would regard
getch() as being semantically similar, but know of nothing in the standard that
requires compilers to treat it thus.

> > The amount of ugly and inefficient code employed to avoid UB seems
> > minor because a lot of code *doesn't* avoid it.  Instead, a lot of
> > code was written on the assumption that if every compiler released in
> > the last 10+ years for a mainstream platform would behave acceptably,
> > future compilers would continue to do so.
> 
> What exactly happened 10 years ago?

By the mid 1980s, mainstream compilers for mainstream platforms had pretty well
established some de facto boundaries for the behaviors of some actions where the
standard imposed no requirements.  Thus, by the mid 1990s, programmers faced
with the choice of writing nasty code to avoid overflow, or less-nasty code to
limit the effects, would generally perceive no reason to favor the former unless
their code would need to run on some really obscure hardware.

I don't know the exact historical events, but I suspect a catalyst for change
was the fact that C++ started imposing requirements on Undefined Behavior: if
a template expansion would invoke certain actions where the C++ Standard had
previously imposed no requirements, compilers were required to silently reject
it and try another **even if the platform's documentation would have otherwise
guaranteed a useful behavior**.

Prior to that, compiler writers tended to make their compilers behave in predictable fashion even when not required by the Standard, even in cases where doing so would require adding an extra instruction or two [e.g. with processors which has rotate-left-through-carry but not shift-left, many compilers would
clear carry between the two statements "int1<<=1; int2<<=1;" since setting the
LSB of int2 would be very unexpected behavior].

> C states that arithmetic overflow has undefined behavior, but
> provides no coherent mechanisms to reliably detect or avoid it.
> C programmers tend to deal with that problem by ignoring it.
> We tend to be lucky; most arithmetic operations *don't* overflow,
> but we rarely attempt to guarantee that.  This is IMHO a flaw in
> the language.

Many compilers offered one of two guarantees:

1. Overflows trap.
2. Overflows simply yield a number (maybe or maybe not representable as int)

Each guarantee will be useful to some programs, and for the Standard to mandate
any behavior would invalidate code which relied upon a contrary guarantee.

If no code could ever rely upon anything when overflow occurred, that would have
been a major defect in the language, but instead there emerged a simple rule
which 99% of compilers tried to follow: implementation documentation should
specify whether overflows never trap, always trap, or sometimes trap, and
should indicate what can or cannot be guaranteed about the computed values if
overflows don't trap.  Further, if hardware design offers a clear bias toward
a particular overflow behavior, compilers should use that one unless requested
otherwise.

Until that rule got threw out the window around 2009, the fact that 99% of
compilers followed it even when not compelled to by the Standard meant that
it didn't really matter whether the Standard included such a rule or not.

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

#67911

On Thursday, August 20, 2015 at 4:32:11 PM UTC-4, supe...@casperkitty.com wrote:
> [...]
> By the mid 1980s, mainstream compilers for mainstream platforms had pretty well
> established some de facto boundaries for the behaviors of some actions where the
> standard imposed no requirements. [...]

By the mid 1980's, the Standard imposed no requirements whatsoever.

-Don

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

#67914

On Thursday, August 20, 2015 at 4:23:54 PM UTC-5, donal...@gmail.com wrote:
> On Thursday, August 20, 2015 at 4:32:11 PM UTC-4, supe...@casperkitty.com wrote:
> > [...]
> > By the mid 1980s, mainstream compilers for mainstream platforms had pretty well
> > established some de facto boundaries for the behaviors of some actions where the
> > standard imposed no requirements. [...]
> 
> By the mid 1980's, the Standard imposed no requirements whatsoever.

Common behaviors of C compilers were established before ANSI ratified C89.
While it could be argued that a non-ratified standard couldn't impose any
requirements, it would seem an amazing coincidence that compilers for both
the PC and Macintosh happened to conform pretty well with the things that
C89 would eventually require.

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

#67917

supercat@casperkitty.com writes:
> On Thursday, August 20, 2015 at 1:35:04 PM UTC-5, Keith Thompson wrote:
>> C99 and C89/C90 say the same thing; there's been no substantial change
>> in the meaning of "undefined behavior".  Or am I missing something?
>
> I believe C11 added language to the effect that an action which invokes UB
> at any point during execution renders the entire execution Undefined, even
> the portion before UB was invoked.  I don't think any earlier versions of the
> Standard included anything like that.

I'm skeptical that such a change was made, but I'm more than willing to
be convinced.  Can you cite the added wording in C11 that says this?

If this is new in C11, you should be able to inhibit such optimizations
with "-std=c99" or equivalent.

[...]

>> What exactly happened 10 years ago?
>
> By the mid 1980s, mainstream compilers for mainstream platforms had
> pretty well established some de facto boundaries for the behaviors of
> some actions where the standard imposed no requirements.  Thus, by the
> mid 1990s, programmers faced with the choice of writing nasty code to
> avoid overflow, or less-nasty code to limit the effects, would
> generally perceive no reason to favor the former unless their code
> would need to run on some really obscure hardware.

In the mind 1980s, there was no C standard.

> I don't know the exact historical events, but I suspect a catalyst for
> change was the fact that C++ started imposing requirements on
> Undefined Behavior: if a template expansion would invoke certain
> actions where the C++ Standard had previously imposed no requirements,
> compilers were required to silently reject it and try another **even
> if the platform's documentation would have otherwise guaranteed a
> useful behavior**.

That sounds similar to SFINAE
    https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error
but that applies only when a template expansion would cause a
compile-time error; undefined behavior is not relevant.

[...]

> Many compilers offered one of two guarantees:
>
> 1. Overflows trap.
> 2. Overflows simply yield a number (maybe or maybe not representable as int)
>
> Each guarantee will be useful to some programs, and for the Standard
> to mandate any behavior would invalidate code which relied upon a
> contrary guarantee.
>
> If no code could ever rely upon anything when overflow occurred, that
> would have been a major defect in the language, but instead there
> emerged a simple rule which 99% of compilers tried to follow:
> implementation documentation should specify whether overflows never
> trap, always trap, or sometimes trap, and should indicate what can or
> cannot be guaranteed about the computed values if overflows don't
> trap.  Further, if hardware design offers a clear bias toward a
> particular overflow behavior, compilers should use that one unless
> requested otherwise.
>
> Until that rule got threw out the window around 2009, the fact that
> 99% of compilers followed it even when not compelled to by the
> Standard meant that it didn't really matter whether the Standard
> included such a rule or not.

I'm still skeptical that anything in particular happened in 2009, but
I'll gladly believe you if you can offer some citation.

Certainly optimizers have simply gotten more clever over the years.
I'm not aware of any sudden change of the kind you describe.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

#67926

On Thursday, August 20, 2015 at 6:48:24 PM UTC-5, Keith Thompson wrote:
> I'm skeptical that such a change was made, but I'm more than willing to
> be convinced.  Can you cite the added wording in C11 that says this?

Hmm... upon doing some further research, it seems I may have been mistaken.

> > By the mid 1980s, mainstream compilers for mainstream platforms had
> > pretty well established some de facto boundaries for the behaviors of
> > some actions where the standard imposed no requirements.  Thus, by the
> > mid 1990s, programmers faced with the choice of writing nasty code to
> > avoid overflow, or less-nasty code to limit the effects, would
> > generally perceive no reason to favor the former unless their code
> > would need to run on some really obscure hardware.
> 
> In the mind 1980s, there was no C standard.

I would say that the 1978 publication of The C Programming Language, by Brian
W. Kernighan and Dennis M. Ritchie, established a C Standard.  I don't know
exactly when the new parameter specification form entered mainstream use, but
it was certainly before the 1989 publication of the ANSI C Standard.  I first
started programming with Turbo C in early 1988, and nearly all the code I
ever saw used the new form.

> That sounds similar to SFINAE
>     https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error
> but that applies only when a template expansion would cause a
> compile-time error; undefined behavior is not relevant.

If evaluation of a compile-time constant in the course of a template expansion
would invoke Undefined Behavior (e.g. -1<<3), the Standard mandates that the
expansion be regarded as ill-formed, even if the compiler's documentation would
specify a behavior consistent with yielding a constant (e.g. -8).

> I'm still skeptical that anything in particular happened in 2009, but
> I'll gladly believe you if you can offer some citation.

There wasn't an abrupt change in 2009, and indeed I didn't notice a real change
until this year, but articles from around 2009 suggest that's when people
started to take seriously the idea that if a particular inputs would cause
Undefined Behavior, a compiler should infer that such inputs will never occur.
I really don't know the history of what happened very well, since I only became
aware this year that popular compilers are starting to incorporate such logic.

> Certainly optimizers have simply gotten more clever over the years.
> I'm not aware of any sudden change of the kind you describe.

Historically, most optimizers would perform transformations which would be
valid under some sort of execution model.  For example, a compiler may behave
under an execution model where each variable of type "int" (including compiler
temporaries) may hold any mathematical integer, but would only be guaranteed to
read the exact number written if it's between -2147483648 and 2147483647.  If
a variable is written with a number outside that range, each read may yield an
independent arbitrary value which is congruent to the value written mod
4294967296.  Under such a model, given

    int a=2147483647; a++; long long b=a; long c=a;

Variables b and c could both hold 2147483648 or both hold -2147483648, or could
independently hold any two values which were congruent to 2147483648 mod
4294967296.  Such an execution model would allow the forms of loop optimization
which are cited as the reason overflow "needs" to be UB, but would have effects
that were constrained enough that dealing with them could often be much easier
than preventing overflow.  The behavior of most compilers has historically been
consistent with such a model unless they expressly trapped overflow.  Some
loop optimizations performed transforms which could have been valid if
variables happened to always read the number that was written (regardless of
whether it was within the range of the type), but didn't actually make
the variables always hold values within range of their type, but even in those
cases the consequence would be "Overflow may cause a loop to exit early--even
before the overflow actually occurs".  Not wonderful behavior, but something
that can be dealt with.

The hyper-modern philosophy is different, in that it makes it impossible to
define or constrain the effects of any sort of UB.  I don't have a firm grasp
as to when and how the philosophy took hold, but it seems to have been
sometime around 2009.

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

#67971

supercat@casperkitty.com writes:
> On Thursday, August 20, 2015 at 6:48:24 PM UTC-5, Keith Thompson wrote:
>> I'm skeptical that such a change was made, but I'm more than willing to
>> be convinced.  Can you cite the added wording in C11 that says this?
>
> Hmm... upon doing some further research, it seems I may have been mistaken.
>
>> > By the mid 1980s, mainstream compilers for mainstream platforms had
>> > pretty well established some de facto boundaries for the behaviors of
>> > some actions where the standard imposed no requirements.  Thus, by the
>> > mid 1990s, programmers faced with the choice of writing nasty code to
>> > avoid overflow, or less-nasty code to limit the effects, would
>> > generally perceive no reason to favor the former unless their code
>> > would need to run on some really obscure hardware.
>> 
>> In the mind 1980s, there was no C standard.
>
> I would say that the 1978 publication of The C Programming Language, by Brian
> W. Kernighan and Dennis M. Ritchie, established a C Standard.  I don't know
> exactly when the new parameter specification form entered mainstream use, but
> it was certainly before the 1989 publication of the ANSI C Standard.  I first
> started programming with Turbo C in early 1988, and nearly all the code I
> ever saw used the new form.

Prototypes were invented in C++ and later added to C.  They were first
*officially* introduced by the 1989 ANSI standard, but they were
undoubtedly implemented and used before that (just because they were *so
much better* than old-style function declarations).  There was also a
tool called "ansi2knr" that would translate C code with prototypes to C
code without prototypes, so you could use prototypes even if your
compiler didn't yet support them.

>> That sounds similar to SFINAE
>>     https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error
>> but that applies only when a template expansion would cause a
>> compile-time error; undefined behavior is not relevant.
>
> If evaluation of a compile-time constant in the course of a template
> expansion would invoke Undefined Behavior (e.g. -1<<3), the Standard
> mandates that the expansion be regarded as ill-formed, even if the
> compiler's documentation would specify a behavior consistent with
> yielding a constant (e.g. -8).

[...]

>> Certainly optimizers have simply gotten more clever over the years.
>> I'm not aware of any sudden change of the kind you describe.
>
> Historically, most optimizers would perform transformations which would be
> valid under some sort of execution model.
[SNIP]
> The hyper-modern philosophy is different, in that it makes it impossible to
> define or constrain the effects of any sort of UB.  I don't have a firm grasp
> as to when and how the philosophy took hold, but it seems to have been
> sometime around 2009.

The "hyper-modern philosophy" is the one that's been implicit in the C
standard since 1989.  I haven't kept track of developments in optimization
well enough to know how things have changed or when they've changed.
But if your program has potential undefined behavior, I suggest that you
need to fix the program.  If you think that
    int n = INT_MAX;
    n ++;
"should" set n to any particular value, that's not a conclusion that you
can draw from the C standard.

I do agree that compilers should do a better job of diagnosing such
programs, especially when they take advantage of the presence of
undefine behavior to perform "surprising" transformations.  I don't see
the point of catering to such code beyond that.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

#67980

On Friday, August 21, 2015 at 7:25:40 PM UTC-5, Keith Thompson wrote:
> The "hyper-modern philosophy" is the one that's been implicit in the C
> standard since 1989.  I haven't kept track of developments in optimization
> well enough to know how things have changed or when they've changed.
> But if your program has potential undefined behavior, I suggest that you
> need to fix the program.  If you think that
>     int n = INT_MAX;
>     n ++;
> "should" set n to any particular value, that's not a conclusion that you
> can draw from the C standard.

On the vast majority of platforms I've used, "n" would behave as something
that, each time it is read, will behave as some mathematical integer which
is congruent to a value one greater than MAX_INT, mod 2*MAX_INT+2.  I believe
the language would be enhanced enormously if such behavior were defined as
normative, such that compilers could opt to conform to it or not as they see
fit, but would require to indicate via macro or other such means whether or
not they do so.

Such a model would in no way interfere with most forms of loop optimization
which rely upon invariants like "i+1 > i", since even if "i" is the largest
value of the largest integer type, "i+1" would be allowed to behave as a
mathematical integer which was even larger.  On the other hand, code which
confirmed the existence of compiler support for the indicated execution model
could then safely omit overflow-handling logic in cases where that execution
model was sufficient to meet its requirements.

If C really wants to compete with Java and C#, it should offer some new data
types as well, with support for overflow detection, but with looser semantics
than C#.  Given the requirement for a method that performs the same as the
following when there is no overflow:

    int sum(int *dat, int *error)
    {
      int total;
      for (int i=0; i<65536; i++)
        total+=dat[i];
    }

but with the additional requirements that: (1) it must return INT_MIN if the
arithmetic total is not representable as "int", and (2) it may, but need not,
return INT_MIN if overflows occur during the calculation but the arithmetical
total is representable as "int", it would be possible for to meet those
requirements in hand-written x64 or ARM Cortex-M3 code with less than 1% time
overhead compared with the optimal peformance that could be achieved without
such checking, but there's presently no way to express such semantics in C.

I would posit that the primary reason so much software is so lax with overflow
checking is that languages don't offer the semantics necessary to make it
efficient.  If C wants to take on other languages, it needs to change that.


> I do agree that compilers should do a better job of diagnosing such
> programs, especially when they take advantage of the presence of
> undefine behavior to perform "surprising" transformations.  I don't see
> the point of catering to such code beyond that.

You've acknowledged that C lacks the facilities to write overflow-safe code
efficiently in cases where the validity of data would depend on whether or not
it causes overflow.  The easiest way to offer some guarantees which are
consistent with the behavior of compilers which were written by people who were
more interested in meeting the requirements of programmers than in avoiding
doing anything beyond what the anemic Standard requires.

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

#68007

On 8/22/15 1:11 AM, supercat@casperkitty.com wrote:
> On Friday, August 21, 2015 at 7:25:40 PM UTC-5, Keith Thompson wrote:
>> The "hyper-modern philosophy" is the one that's been implicit in the C
>> standard since 1989.  I haven't kept track of developments in optimization
>> well enough to know how things have changed or when they've changed.
>> But if your program has potential undefined behavior, I suggest that you
>> need to fix the program.  If you think that
>>      int n = INT_MAX;
>>      n ++;
>> "should" set n to any particular value, that's not a conclusion that you
>> can draw from the C standard.
>
> On the vast majority of platforms I've used, "n" would behave as something
> that, each time it is read, will behave as some mathematical integer which
> is congruent to a value one greater than MAX_INT, mod 2*MAX_INT+2.  I believe
> the language would be enhanced enormously if such behavior were defined as
> normative, such that compilers could opt to conform to it or not as they see
> fit, but would require to indicate via macro or other such means whether or
> not they do so.

Vast Majority != All.

A prime guiding principle in the design of C was that it wanted to make 
operators efficient, in other words, work at real hardware speeds, so 
much undefined behavior results from real (or imagined like possible) 
machine behavior. "Mod" behavior like you describe is common for a two's 
complement machine with no trapping on overflow, which may be the 
'standard' now, but even now is not universal.

1's complement machines (which were fairly common in the era that the 
standard was first being developed) would typically mod with a different 
value.

Wider behavior comes from machines that would 'Trap' on overflow, which 
is a behavior so extreme that standard needed to define it as undefined 
behavior. (without trapping, I think the standard could easily have 
defined the results as an unspecified result.

Note also, Standards don't define normative behavior that 
implementations can choose to 'opt out'. You can have features 
officially described as optional, normally with a standard specified 
macro to detect that this optional feature is available.

Note again, it is quite allowable for someone to define a language 
extension to C, that when present, defines a number of things that C 
leaves undefined, and using floating point as an example, the C 
standards committee has shown a willingness to make such a standard as 
an optional part of C. The key would be finding a large enough set of 
behaviors to be useful and at the same point naturally supportable by a 
large set of common machines.

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

#68026

Richard Damon <Richard@damon-family.org> wrote:
> On 8/22/15 1:11 AM, supercat@casperkitty.com wrote:
(snip)
>> On the vast majority of platforms I've used, "n" would behave as something
>> that, each time it is read, will behave as some mathematical integer which
>> is congruent to a value one greater than MAX_INT, mod 2*MAX_INT+2.  I believe
>> the language would be enhanced enormously if such behavior were defined as
>> normative, such that compilers could opt to conform to it or not as they see
>> fit, but would require to indicate via macro or other such means whether or
>> not they do so.
 
> Vast Majority != All.
 
> A prime guiding principle in the design of C was that it wanted to make 
> operators efficient, in other words, work at real hardware speeds, so 
> much undefined behavior results from real (or imagined like possible) 
> machine behavior. "Mod" behavior like you describe is common for a two's 
> complement machine with no trapping on overflow, which may be the 
> 'standard' now, but even now is not universal.

Yes, C still allows for ones complement and sign magnitude machines.

I am still waiting for a C compiler for the 7094.
 
> 1's complement machines (which were fairly common in the era that the 
> standard was first being developed) would typically mod with a different 
> value.

CDC machines are ones complement, and were fairly popular for
high-end machines through the 1980's. 

Last I knew, Unisys still sells ones complement machines.

The last of the sign magnitude machines I know about is the
IBM 7094, descendant of the 704 where Fortran started.
 
> Wider behavior comes from machines that would 'Trap' on overflow, which 
> is a behavior so extreme that standard needed to define it as undefined 
> behavior. (without trapping, I think the standard could easily have 
> defined the results as an unspecified result.

Most commonly discussed is the results from divide and mod with
one or two negative arguments. C might have changed this now, but
it used to be that two choices were allowed. 

Fortran, partly from originating on sign magnitude machines, doesn't
have this freedom. Since hardware designers wanted Fortran to run on
their machines, it was usual to design hardware to follow the
Fortran requirement.

(snip)

-- glen

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

#68085

On 08/22/2015 12:59 PM, glen herrmannsfeldt wrote:
...
> Most commonly discussed is the results from divide and mod with
> one or two negative arguments. C might have changed this now, but
> it used to be that two choices were allowed.

Two choices were never allowed when both arguments are negative, only
when one was negative and the other was positive, and only in C90

In C99. integer division is described as truncating the fractional part,
and a footnote clarifies that this means rounding toward 0. The
mathematical value of -4/3 is -(1 1/3), truncating the fractional part
gives -1. From the identity (a/b)*b + a%b == a, i follows that -4%-3 == -1.
-- 
James Kuyper

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

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web