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

Groups > comp.lang.c > #71454 > 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-09-29 15:48 -0700
    Re: the language (and the role of Undefined Behavior therein) Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-04 16:57 -0700
      Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-10-04 19:48 -0700
        Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-05 04:50 +0000
          Re: the language (and the role of Undefined Behavior therein) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-05 13:43 +0100
            Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-05 15:26 +0000
              Re: the language (and the role of Undefined Behavior therein) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-05 19:39 +0100
                Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-10-05 13:32 -0700
                Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-05 22:06 +0000
                  Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-10-05 16:08 -0700
                  Re: the language (and the role of Undefined Behavior therein) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-06 11:04 +0100
                    Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-10-06 08:06 -0700
                      Re: the language (and the role of Undefined Behavior therein) Rosario19 <Ros@invalid.invalid> - 2015-10-06 18:14 +0200
                        Re: the language (and the role of Undefined Behavior therein) Rosario19 <Ros@invalid.invalid> - 2015-10-06 18:54 +0200
                          Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-10-06 11:20 -0700
                        Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-10-06 10:00 -0700
                      Re: the language (and the role of Undefined Behavior therein) David Thompson <dave.thompson2@verizon.net> - 2015-10-31 06:44 -0400
                        Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-10-31 11:08 -0700
                          Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-10-31 13:53 -0700
                            Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-10-31 14:06 -0700
            Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-10-05 09:28 -0700
            Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-10-05 11:20 -0700
              Re: the language (and the role of Undefined Behavior therein) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-10-05 20:13 +0100
                Re: the language (and the role of Undefined Behavior therein) Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-12 09:29 -0700
        Re: the language (and the role of Undefined Behavior therein) Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-12 10:32 -0700
          Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-10-12 12:23 -0700
          Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-10-12 14:42 -0700
          Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-10-14 09:10 -0700
            Re: the language (and the role of Undefined Behavior therein) Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-19 16:11 -0700

Page 1 of 2  [1] 2  Next page →

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

On Monday, September 7, 2015 at 10:11:46 AM UTC-5, Tim Rentsch wrote:
> Reading through the posting in this thread has been disappointing
> for me, because I think supercat is raising some important issues
> but mostly people aren't seeing that because his concerns are
> expressed in a funny way.

I had thought I was being fairly straight-forward, though perhaps overly
snarky; if I'm unclear about some things I'd like to know.

> For example, regarding "hyper-modern philosophy".  It's true that
> the C standard has always allowed aggressive optimization that
> takes advantage of undefined behavior, but AFAIK it is only
> relatively recently that compilers have started to exploit that,
> with results that are decidely counter-intuitive.  

Many compiler vendors have at times explicitly refrained from optimizations
which would have been straightforward and would have been compliant with
the Standard, because they would violate the Principle of Least
Astonishment.  For example, given:

    signed char x,y;
    ...
    x<<=1;
    y<<=1;

many compilers for 8-bit machines that have rotate-through-carry but lack
shift instructions will clear carry, rotate x left, clear carry, and
rotate y left.  I recall at least one compiler vendor expressly noting on
its discussion board that even though the Standard did not impose any
requirements in cases where "x<<=1" would set the carry flag, and even
though code could be an instruction shorter if it didn't care about behavior
in such cases, it would be better to make left-shifts of negative numbers
simply shift bits left, than to have them occasionally cause other side-
effects as well.

>                 I understand the desire of compiler writers to
> optimize aggressively, but I think this tendency is getting out
> of control to the point where the current rules no longer serve
> the interests of developers.

Hear hear.  If the purpose of a compiler isn't to help developers produce
programs meeting client requirements, what is it?

> A related point is that we would like to be able to write code in
> certain cases that, even though it may produce a nonsensical
> result under some circumstances, is not allowed arbitrary
> transgressions as would be allowed under undefined behavior.
> Unfortunately there is no middle ground....
> ...                       I don't know how common it is for such
> situations to arise, but certainly they /can/ arise, and when
> they do the current Standard offers no help.  IMO this matter
> also bears further investigation.

It is common--much more so today than in 1989--for programs to be fed
non-validated input from untrustworthy sources.  I would think that most
people who run such programs would include, among the requirements, that
such programs should refrain from letting the creators of malicious inputs
take over their machine.  Given a choice between a program which meets that
requirement, and another which would be 20% faster when given clean inputs
but which would allow the creator of malicious input to take over the
machine, I suspect most users would, in most cases, prefer the former.

While it may be useful for compilers to allow programmers to forego such
protections in favor of receiving maximum performance, such a trade-off
should nowadays be considered the exception rather than the norm.

> Note that there is some precedent for these kinds of concerns in
> official discussion.  C11 now has the notion of runtime
> constraint violations, which is one method for addressing cases
> that before would have been undefined behavior.  Also there have
> been proposals for some form of limited undefined behavior, where
> the consequences are not spelled out but not allowed to be as
> disastrous as full undefined behavior.  Both of these are related
> to the concerns that have been brought up in this thread.

The "ANALYZABLE" concept (Annex L) has the right idea, but fails to
adequately specify what is or is not guaranteed in case of things like
integer overflow.  For example, given

    int i=f(); // Happens to return MAX_INT
    if (i >= 0)
    {
      i++;
      if (i >= 0 && i < 128) foo[i]++;
    }

would code which incremented foo[-MAX_INT-1u] be considered ANALYZABLE?
I could see sound arguments to be made either way, but I don't think that
Annex L makes that clear.  The increment itself wouldn't cause any out-
of-bounds memory access, but if the compiler optimizes out the "i>=0"
check while performing the "i<128" check on a value that has wrapped
around, that could result in the code erroneously deciding that "i" is
within range.

> I don't expect any great philosphical shifts in response to my
> comments here, but I would like to ask those who have been
> following the thread to read through the postings again keeping
> the above remarks in mind.  I think some may find there is more
> substance of interest than it appeared on first reading.

I'm glad you are understanding what I'm trying to say.  Sorry it took me
awhile to notice your reply.  Thanks for writing.

[toc] | [next] | [standalone]

#71901

supercat@casperkitty.com writes:

> On Monday, September 7, 2015 at 10:11:46 AM UTC-5, Tim Rentsch wrote:
>> Reading through the posting in this thread has been disappointing
>> for me, because I think supercat is raising some important issues
>> but mostly people aren't seeing that because his concerns are
>> expressed in a funny way.
>
> I had thought I was being fairly straight-forward, though perhaps
> overly snarky;  if I'm unclear about some things I'd like to know.
> [snip]

I don't have any specific comments but let me make two
general suggestions.

One, if you really want to talk about changing C, even if
unofficially, a better place to do that is comp.std.c.

Two, if you want people to take you seriously, it's important to
become more conversant with the Standard and use its terminology
in the same way the Standard does.  Perhaps that shouldn't be
true but IME there is a significant effect.

I encourage you to proceed with these if you are interested
in pursuing the topic.  I do think you have some things to
say that it would be good for people to hear, but as things
are now it's hard for that to happen.

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

#71919

On Sunday, October 4, 2015 at 6:57:39 PM UTC-5, Tim Rentsch wrote:
> Two, if you want people to take you seriously, it's important to
> become more conversant with the Standard and use its terminology
> in the same way the Standard does.  Perhaps that shouldn't be
> true but IME there is a significant effect.

Fair point; I think one of my difficulties is that I was programming in C
before there even *was* an ANSI Standard, and so my perspective of the language
is in significant measure influenced by behaviors which were common to almost
every compiler for common platforms, but for various reasons the Standards
Committee has never acknowledged in any fashion.

For example, while the Standards Committee has never said that compilers
should support pointer-based type punning, it emerged as a common technique
because it was useful, compilers consistently supported it in practice, and
because code written to exploit it could in many cases be more efficient than
any readable alternative.  Whether or not the Standards Committee acknowledged
type punning as a technique which compilers should support by default in the
absence of a compelling reason to do otherwise, programmers and compiler
vendors both recognized it as such, and knew that it should be supported as
a technique whether or not the C Standard mandated it.

A lot of people seem to claim that pointer-based type punning was never
legitimate, but given that compilers consistently recognized it before C89
was published, I'd say the difference between the language defined by the
Standard and the language everyone was actually using was *not* due to poor
programming practices, but rather due to defects in the Standard which were
regarded as quaint oddities which would only be relevant if one was targeting
unusual platforms.

I have a very strong suspicion that things like the restrictions on pointer-
based type punning were never intended to be used for optimization purposes,
but were rather intended to allow compilers to enforce more rigid type
checking should they choose to do so.  The rules would actually be fairly
sensible if that was the intended purpose, if coupled with the notion that
implementations might offer a choice of whether or not to enforce the rules,
in much the same fashion as many compilers for other languages allow code
to enable or disable array-subscript checking.

In any case, I suspect what's happened is that people who were not programming
C in the 1980s and 1990s never got a sense for the de-facto standard behaviors
which went beyond those described by the "official" Standard.

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

#71933

supercat@casperkitty.com wrote:
> On Sunday, October 4, 2015 at 6:57:39 PM UTC-5, Tim Rentsch wrote:
>> Two, if you want people to take you seriously, it's important to
>> become more conversant with the Standard and use its terminology
>> in the same way the Standard does.  Perhaps that shouldn't be
>> true but IME there is a significant effect.
 
> Fair point; I think one of my difficulties is that I was 
> programming in C before there even *was* an ANSI Standard, 
> and so my perspective of the language is in significant measure 
> influenced by behaviors which were common to almost every compiler 
> for common platforms, but for various reasons the Standards 
> Committee has never acknowledged in any fashion.

Yes, I was also using C before ANSI, though not so long before.
 
> For example, while the Standards Committee has never said that 
> compilers should support pointer-based type punning, it emerged 
> as a common technique because it was useful, compilers consistently 
> supported it in practice, and because code written to exploit it 
> could in many cases be more efficient than any readable alternative.  

Without going back and looking, I believe it is system dependent.
You can't guarantee it, but if you know it works on yours,
you are allowed to use it.

> Whether or not the Standards Committee acknowledged type punning 
> as a technique which compilers should support by default in the 
> absence of a compelling reason to do otherwise, programmers and 
> compiler vendors both recognized it as such, and knew that it 
> should be supported as a technique whether or not the 
> C Standard mandated it.
 
> A lot of people seem to claim that pointer-based type punning 
> was never legitimate, but given that compilers consistently 
> recognized it before C89 was published, I'd say the difference 
> between the language defined by the Standard and the language 
> everyone was actually using was *not* due to poor programming 
> practices, but rather due to defects in the Standard which 
> were regarded as quaint oddities which would only be relevant if 
> one was targeting unusual platforms.

There has been hardware that disallows it. For more modern
system, JVM disallows it.  Also, some hardware has alignment
restrictions which can cause it to fail.
 
> I have a very strong suspicion that things like the restrictions 
> on pointer- based type punning were never intended to be used for 
> optimization purposes, but were rather intended to allow compilers 
> to enforce more rigid type checking should they choose to do so.  
> The rules would actually be fairly sensible if that was the 
> intended purpose, if coupled with the notion that implementations 
> might offer a choice of whether or not to enforce the rules, 
> in much the same fashion as many compilers for other languages 
> allow code to enable or disable array-subscript checking.

As noted, hardware might disallow it. There was a fairly strong
incentive to allow things that hardware allows, and disallow things
that hardware doesn't, even if the latter is relatively rare.
 
> In any case, I suspect what's happened is that people who were 
> not programming C in the 1980s and 1990s never got a sense for 
> the de-facto standard behaviors which went beyond those described 
> by the "official" Standard.

This goes back at least to the use of EQUIVALENCE in Fortran.

It is supposed to be used to save memory, but again has been
used to type pun. Early Fortran machines were word addressed.
Endianness wasn't a problem. 

But even in cases where type punning works, its use depends
on knowing the bit patterns, endianness, and padding, of the
values in use. For those reasons, the standard (I believe)
makes it system dependent. (Including that one might hit a
trap representation or alignment exception.)

-- glen

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

#71968

glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:

> supercat@casperkitty.com wrote:
<snip>
>> I have a very strong suspicion that things like the restrictions 
>> on pointer- based type punning were never intended to be used for 
>> optimization purposes, but were rather intended to allow compilers 
>> to enforce more rigid type checking should they choose to do so.  
>> The rules would actually be fairly sensible if that was the 
>> intended purpose, if coupled with the notion that implementations 
>> might offer a choice of whether or not to enforce the rules, 
>> in much the same fashion as many compilers for other languages 
>> allow code to enable or disable array-subscript checking.
>
> As noted, hardware might disallow it. There was a fairly strong
> incentive to allow things that hardware allows, and disallow things
> that hardware doesn't, even if the latter is relatively rare.

I don't think that's not really addressing supercat's point.  The
effective type rule renders some accesses undefined, and that is used by
some implementations to do what is, to some, surprising things -- like
not doing the access at all.  K&R 1st ed. had a notable phrase about
pointer conversions which was something like "the result is not
specified but should be unsurprising to anyone familiar with the
underlying address structure".  I think he or she would like to go back
to the days when the result of doing undefined things were largely
unsurprising to people in the know.

In his or her uint32_t w = *(uint32_t *)p; example I suspect that
supercat would be fine with a trap if p is misaligned, or if the result
was some odd data that comes from reading the nearest whole word.  The
objection (which I don't share) is that the result can be to cue the
optimiser to do something unexpected.

I don't share it because it's a rare situation with many solutions.  The
obvious one being to copy the target's representation using a char * or
memcpy.

<snip>
-- 
Ben.

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

#71974

Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
 
>> supercat@casperkitty.com wrote:
<snip>
>>> I have a very strong suspicion that things like the restrictions 
>>> on pointer- based type punning were never intended to be used for 
>>> optimization purposes, but were rather intended to allow compilers 
>>> to enforce more rigid type checking should they choose to do so.  

(snip, I wrote)
>> As noted, hardware might disallow it. There was a fairly strong
>> incentive to allow things that hardware allows, and disallow things
>> that hardware doesn't, even if the latter is relatively rare.
 
> I don't think that's not really addressing supercat's point.  The
> effective type rule renders some accesses undefined, and that is used by
> some implementations to do what is, to some, surprising things -- like
> not doing the access at all.  K&R 1st ed. had a notable phrase about
> pointer conversions which was something like "the result is not
> specified but should be unsurprising to anyone familiar with the
> underlying address structure".  I think he or she would like to go back
> to the days when the result of doing undefined things were largely
> unsurprising to people in the know.

The standard does separate implementation defined and undefined,
and I believe optimizers shouldn't do such tricks for the former.

As for what the hardware might do, consider:

https://en.wikipedia.org/wiki/Tagged_architecture

where the hardware remembers what type of data is stored in
each memory location.  If that seems too old fashioned, note
that is pretty much what JVM does. Java has
ClassCastException if you try to use an object reference
in the wrong way. 

> In his or her uint32_t w = *(uint32_t *)p; example I suspect that
> supercat would be fine with a trap if p is misaligned, or if the result
> was some odd data that comes from reading the nearest whole word.  The
> objection (which I don't share) is that the result can be to cue the
> optimiser to do something unexpected.

On many systems, the hardware trap for unaligned access if fatal,
so software can assume that it didn't happen. 

But yes, I mostly disagree with optimizers assuming some things
can't happen and optimize on that assumption.
 
> I don't share it because it's a rare situation with many solutions.  The
> obvious one being to copy the target's representation using a char * or
> memcpy.

OK, but the compiler knows when you are doing that.

-- glen

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

#71996

glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>  
>>> supercat@casperkitty.com wrote:
> <snip>
>>>> I have a very strong suspicion that things like the restrictions 
>>>> on pointer- based type punning were never intended to be used for 
>>>> optimization purposes, but were rather intended to allow compilers 
>>>> to enforce more rigid type checking should they choose to do so.  
>
> (snip, I wrote)
>>> As noted, hardware might disallow it. There was a fairly strong
>>> incentive to allow things that hardware allows, and disallow things
>>> that hardware doesn't, even if the latter is relatively rare.
>  
>> I don't think that's not really addressing supercat's point.  The
>> effective type rule renders some accesses undefined, and that is used by
>> some implementations to do what is, to some, surprising things -- like
>> not doing the access at all.  K&R 1st ed. had a notable phrase about
>> pointer conversions which was something like "the result is not
>> specified but should be unsurprising to anyone familiar with the
>> underlying address structure".  I think he or she would like to go back
>> to the days when the result of doing undefined things were largely
>> unsurprising to people in the know.
>
> The standard does separate implementation defined and undefined,
> and I believe optimizers shouldn't do such tricks for the former.

Yes.  It is that latter case -- undefined behaviour being exploited for
optimisation -- that is at issue.

> As for what the hardware might do, consider:
>
> https://en.wikipedia.org/wiki/Tagged_architecture
>
> where the hardware remembers what type of data is stored in
> each memory location.  If that seems too old fashioned, note
> that is pretty much what JVM does. Java has
> ClassCastException if you try to use an object reference
> in the wrong way.

I'm not sure how this information (not new to me BTW!) fits in.  Are you
agreeing, disagreeing, what?  I think supercat would be fine with an
exception in cases where that is what the hardware does.

>> In his or her uint32_t w = *(uint32_t *)p; example I suspect that
>> supercat would be fine with a trap if p is misaligned, or if the result
>> was some odd data that comes from reading the nearest whole word.  The
>> objection (which I don't share) is that the result can be to cue the
>> optimiser to do something unexpected.
>
> On many systems, the hardware trap for unaligned access if fatal,
> so software can assume that it didn't happen.

It can't know (in general) that the access is unaligned.  But I don't
think this is a hardware issue -- it's about a C language rule.

> But yes, I mostly disagree with optimizers assuming some things
> can't happen and optimize on that assumption.

The C rule says it can't happen, even on machines where the hardware is
happy.  That's the point at issue.

<snip>
-- 
Ben.

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

#71999

On Monday, October 5, 2015 at 1:39:50 PM UTC-5, Ben Bacarisse wrote:
> I'm not sure how this information (not new to me BTW!) fits in.  Are you
> agreeing, disagreeing, what?  I think supercat would be fine with an
> exception in cases where that is what the hardware does.

Not only that, but I would suggest that in cases where hardware traps
various things, having such traps occur in cases where the operations in
question would semantically be required to occur in the general non-trap
case, code upholding the Principle of Least Astonishment should cause the
traps to be triggered in the hardware-trapping case.

For example, given "int recip(int x) { return 32767/x;}" I would consider it
appropriate for a compiler to omit the division operation when the function
is passed a non-zero constant (simply replace the function call with a load
of the result) but calling the function with a constant zero should trigger
a divide exception if the platform has one.

A somewhat trickier scenario is (x<<y) when writing 16-bit code for the 8086,
since there are some processors in the family which would process ASL AX,CL
as CL single-bit left shifts, but there are others that would process it as
a shift by (CL & 15).  If a compiler documents that its behavior for x<<y
will match the underlying behavior of "ASL AX,CL" in cases where y is 16 or
higher (the fact that the behavior was documented would make it no longer be
UB) the compiler should use that expression if y is a constant 16 or higher,
even if x is also a constant.  If instead the compiler documents that "x<<y"
will select in arbitrary fashion between the two indicated values, with no
promise of consistency (the semantics I'd recommend as the best compromise
between performance and POLA) then having the behavior depend upon whether
something was a constant would not be astonishing at all.

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

#72006

Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:

(snip, I wrote)
>> The standard does separate implementation defined and undefined,
>> and I believe optimizers shouldn't do such tricks for the former.
 
> Yes.  It is that latter case -- undefined behaviour being exploited for
> optimisation -- that is at issue.
 
>> As for what the hardware might do, consider:

(snip on tagged hardware)

> I'm not sure how this information (not new to me BTW!) fits in.  Are you
> agreeing, disagreeing, what?  I think supercat would be fine with an
> exception in cases where that is what the hardware does.

The hardware can refuse to let you look at the bits in a different way.
Storing a (float) into a union and fetching an (int) would be a
hardware exception.  (As it is in Java.)
 
(snip)

>> On many systems, the hardware trap for unaligned access if fatal,
>> so software can assume that it didn't happen.
 
> It can't know (in general) that the access is unaligned.  But I don't
> think this is a hardware issue -- it's about a C language rule.
 
>> But yes, I mostly disagree with optimizers assuming some things
>> can't happen and optimize on that assumption.
 
> The C rule says it can't happen, even on machines where the 
> hardware is happy.  That's the point at issue.

Yes, I also agree that optimizers shouldn't do that.

As a more obvious example, there are systems were reading past the
and of an array doesn't cause problems, and programs might assume
that they could do that.  I have seen that more in Fortran,
which doesn't have short circuit logical operators:

      if(i.ge.1 .and. i.lt.n .and. x(i).ne.999) goto 123

will usually evaluate x(i) even when i is out of range.

-- glen

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

#72012

On Monday, October 5, 2015 at 5:06:21 PM UTC-5, glen herrmannsfeldt wrote:
> The hardware can refuse to let you look at the bits in a different way.
> Storing a (float) into a union and fetching an (int) would be a
> hardware exception.  (As it is in Java.)

If "p" and "q" are valid pointers to objects of the same type, a legitimate
C implementation must allow

    size_t i;
    unsigned char temp[sizeof *p];
    for (i=0; i<sizeof *p; i++)
       temp[i] = ((unsigned char*)q[i];  // Turn *q into a sequence of bytes
    for (i=0; i<sizeof *p; i++)
       ((unsigned char*)p[i] = temp[i];  // Make *p from a sequence of bytes

as a legitimate way of copying the contents of q to p.  Further, between the
loops, any sequence of operations on the contents of temp[] which ends with
that array holding the same sequence of bytes as when it started, will have
no effect on the value that gets assigned to p.

I don't think there are any platforms which would be rendered unable to
handle C if the language were to eliminate the prohibitions against writing
to a pointer of one type and reading the same locations with a pointer of
another.  There may be some platforms where performance would suffer if a
compiler had to work around hardware limitations by decomposing things to
"unsigned char[]" before storing them, and reconstituting them from "unsigned
char[]" when reading them back, but on the flip side there are a fair number
of applications whose performance on much more commonplace hardware will be
degraded by requiring user code to process things as "unsigned char"-sided
chunks rather than something bigger.

While there may be some platforms where C's restrictions allow things to be
more efficient than they otherwise would be, I do not think anything good
comes from trying to apply that restriction to platforms where it would
otherwise not apply.  The few optimizations that are enabled by such
restrictions could be achieved more easily and safely by e.g. adding a rule
which would make

    register int foo;
    foo = 23;
    somefunction(&foo);
    foo+=func2();
    foo+=func2();
    printf("%d",foo);

equivalent to--at the compiler's leisure--either the same code with the
"register" keyword omitted or:

    register int foo;
    foo = 23;
    {int __temp = foo; somefunction(&temp); foo = __temp;}
    foo+=func2();
    foo+=func2();
    printf("%d",foo+2);

That would maintain the meaning of the presently-useless "register" keyword
but allow it to direct useful optimizations [since the compiler would know
that nothing within func2() would be able to modify "foo", it could keep
that value in a register across the function calls and could also consolidate
updates to it].

> > The C rule says it can't happen, even on machines where the 
> > hardware is happy.  That's the point at issue.
> 
> Yes, I also agree that optimizers shouldn't do that.

Unfortunately, some people think optimizers should do that if it allows
the compilers to produce smaller executables whose behavior is consistent
with the C Language Specification [the notion that programmers use
compilers for the purpose of making executables which *meet application
requirements*, and that an exeuctable which fails to meet application
requirements is inferior to one that does, no matter how more "efficient"
the former might be, doesn't seem to factor into that objective].

> As a more obvious example, there are systems were reading past the
> and of an array doesn't cause problems, and programs might assume
> that they could do that.  I have seen that more in Fortran,
> which doesn't have short circuit logical operators:
> 
>       if(i.ge.1 .and. i.lt.n .and. x(i).ne.999) goto 123
> 
> will usually evaluate x(i) even when i is out of range.

It may be helpful for compilers to have options to try to catch such
out-of-bounds accesses even when hardware would tolerate it; I remember
seeing such a thing advertised in the late 1980s or thereabouts.  On
the other hand, I would suggest that compilers should generally at
minimum provide an option to leave any squawking up to the hardware.

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

#72034

glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>
> (snip, I wrote)
>>> The standard does separate implementation defined and undefined,
>>> and I believe optimizers shouldn't do such tricks for the former.
>  
>> Yes.  It is that latter case -- undefined behaviour being exploited for
>> optimisation -- that is at issue.
>  
>>> As for what the hardware might do, consider:
>
> (snip on tagged hardware)
>
>> I'm not sure how this information (not new to me BTW!) fits in.  Are you
>> agreeing, disagreeing, what?  I think supercat would be fine with an
>> exception in cases where that is what the hardware does.
>
> The hardware can refuse to let you look at the bits in a different way.
> Storing a (float) into a union and fetching an (int) would be a
> hardware exception.  (As it is in Java.)

Yes, I know, but that's not the point.  Exposing the hardware's
behaviour (provided it can be made conforming) is fine.  supercat's
issue is with the language rules.

> (snip)
>
>>> On many systems, the hardware trap for unaligned access if fatal,
>>> so software can assume that it didn't happen.
>  
>> It can't know (in general) that the access is unaligned.  But I don't
>> think this is a hardware issue -- it's about a C language rule.
>  
>>> But yes, I mostly disagree with optimizers assuming some things
>>> can't happen and optimize on that assumption.
>  
>> The C rule says it can't happen, even on machines where the 
>> hardware is happy.  That's the point at issue.
>
> Yes, I also agree that optimizers shouldn't do that.

But I don't!  I was simply trying to point out what supercat was
saying.  C has had it's effective type rules for a long time and it's
not that hard to program round them.  You can also rely on the fact that
some of these accesses are undefined if your implementation promises a
certain behaviour.  I don't know of any that do, but there might well be
small-system compilers that promise to interpret *(T *)p in a literal
way.

<snip>
-- 
Ben.

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

#72047

On Tuesday, October 6, 2015 at 5:04:49 AM UTC-5, Ben Bacarisse wrote:
> But I don't!  I was simply trying to point out what supercat was
> saying.  C has had it's effective type rules for a long time and it's
> not that hard to program round them.  You can also rely on the fact that
> some of these accesses are undefined if your implementation promises a
> certain behaviour.  I don't know of any that do, but there might well be
> small-system compilers that promise to interpret *(T *)p in a literal
> way.

The minimalist language specified by the Standards Committee has always had
the type rules, but the language that became popular in the 1980s and 1990s,
and in which things like Linux were written, never did.

The effective type rules existed to avoid the requirement that a compiler
for hardware which used type-tagged memory would have to process a code
like "void inc_l(long *l) { l++; }" as 

    void inc_l(long *l) {
      long temp;
      memcpy(&temp, l, sizeof l);
      temp++; memcpy(l,
      &temp, sizeof l);
    }

even for the 99% of cases where the value would have last been written as
type "long".  Requiring that programmers manually do the "memcpy" step on
the rare occasions when it is necessary would allow code to be much more
performant than it would be if the compiler had to do it always.

On the other hand, when compiling for hardware whose design guarantees that
writing something to memory one way and reading it another will simply
reinterpret the bits as the new type, allowing code to simply use that
feature directly makes more sense than requiring programmers to jump through
hoops.

Suppose one wants to write a method which will receive a "uint16_t*" which
identifies an array whose contents are guaranteed to consist of values in
the range 0 to 65534 and one wishes to write a method to increment all the
values in the array.  I would suggest that:

    void inc_many(uint16_t *arr, uint32_t n)
    {
      if (n < 16) // Handle small arrays in simple way so that the only
                  // overhead of extra logic is one comparison.
      {
        while(n--)
          (*arr++)++;        
      }
      else
      {
        uint32_t nn;
        uint32_t *larr;
        // If array is unaligned, handle first element and then do remainder
        // as aligned.
        if ((intptr_t)arr & (sizeof uint16_t))
        {
          (*arr++)++;
          n--;          
        }
        // If the array is now an odd size, handle oddball element at end
        // pre-emptively so we won't need to worry about it later
        if (n & 1)
          arr[n-1]++;
        // We now have an even-sized aligned array to process.
        n>>=1;
        *larr = (uint32_t*)arr;
        do
          (*larr++)+=0x00010001;
        while(--n);
      }
    }

could on many systems be a lot faster than a loop which does all the
operations on type "short".  The code as above (unless I oopsed somewhere)
would run without modifications to almost any compiler for almost any
microcomputer platform, but doubt there would be any way to write the code
that would:

    1. Abide by the rules that prohibit type punning.
    2. Allow modern compilers to yield output essentially as good as what
       would be possible using type punning.
    3. Not result in older compilers producing code which was worse than
       what would result under the short-based approach.
    4. Be no less readable than the code above.

How would you suggest the above code should be written?

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

#72054

On Tue, 6 Oct 2015 08:06:38 -0700 (PDT), supercat wrote:
>On Tuesday, October 6, 2015 at 5:04:49 AM UTC-5, Ben Bacarisse wrote:
>> But I don't!  I was simply trying to point out what supercat was
>> saying.  C has had it's effective type rules for a long time and it's
>> not that hard to program round them.  You can also rely on the fact that
>> some of these accesses are undefined if your implementation promises a
>> certain behaviour.  I don't know of any that do, but there might well be
>> small-system compilers that promise to interpret *(T *)p in a literal
>> way.
>
>The minimalist language specified by the Standards Committee has always had
>the type rules, but the language that became popular in the 1980s and 1990s,
>and in which things like Linux were written, never did.
>
>The effective type rules existed to avoid the requirement that a compiler
>for hardware which used type-tagged memory would have to process a code
>like "void inc_l(long *l) { l++; }" as 
>
>    void inc_l(long *l) {
>      long temp;
>      memcpy(&temp, l, sizeof l);
>      temp++; memcpy(l,
>      &temp, sizeof l);
>    }
>
>even for the 99% of cases where the value would have last been written as
>type "long".  Requiring that programmers manually do the "memcpy" step on
>the rare occasions when it is necessary would allow code to be much more
>performant than it would be if the compiler had to do it always.
>
>On the other hand, when compiling for hardware whose design guarantees that
>writing something to memory one way and reading it another will simply
>reinterpret the bits as the new type, allowing code to simply use that
>feature directly makes more sense than requiring programmers to jump through
>hoops.
>
>Suppose one wants to write a method which will receive a "uint16_t*" which
>identifies an array whose contents are guaranteed to consist of values in
>the range 0 to 65534 and one wishes to write a method to increment all the
>values in the array.  I would suggest that:
>
>    void inc_many(uint16_t *arr, uint32_t n)
>    {
>      if (n < 16) // Handle small arrays in simple way so that the only
>                  // overhead of extra logic is one comparison.
>      {
>        while(n--)
>          (*arr++)++;        
>      }
>      else
>      {
>        uint32_t nn;
>        uint32_t *larr;

larr is one pointer to uint32_t

>        // If array is unaligned, handle first element and then do remainder
>        // as aligned.
>        if ((intptr_t)arr & (sizeof uint16_t))
>        {
>          (*arr++)++;
>          n--;          
>        }
>        // If the array is now an odd size, handle oddball element at end
>        // pre-emptively so we won't need to worry about it later
>        if (n & 1)
>          arr[n-1]++;
>        // We now have an even-sized aligned array to process.
>        n>>=1;
>        *larr = (uint32_t*)arr;

so *larr is one uint32_t

>        do
>          (*larr++)+=0x00010001;

i not parse well *larr++

>        while(--n);
>      }
>    }

but that code is ok
seems to me i see many error in that

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

#72063

On Tue, 06 Oct 2015 18:14:16 +0200, Rosario19 wrote:

>On Tue, 6 Oct 2015 08:06:38 -0700 (PDT), supercat wrote:
>>    void inc_many(uint16_t *arr, uint32_t n)
>>    {
>>      if (n < 16) // Handle small arrays in simple way so that the only
>>                  // overhead of extra logic is one comparison.
>>      {
>>        while(n--)
>>          (*arr++)++;        
>>      }
>>      else
>>      {
>>        uint32_t nn;
>>        uint32_t *larr;
>
>larr is one pointer to uint32_t
>
>>        // If array is unaligned, handle first element and then do remainder
>>        // as aligned.
>>        if ((intptr_t)arr & (sizeof uint16_t))
>>        {
>>          (*arr++)++;
>>          n--;          
>>        }
>>        // If the array is now an odd size, handle oddball element at end
>>        // pre-emptively so we won't need to worry about it later
>>        if (n & 1)
>>          arr[n-1]++;
>>        // We now have an even-sized aligned array to process.
>>        n>>=1;
>>        *larr = (uint32_t*)arr;

larr is a pointer that has one not initializated value

>so *larr is one uint32_t

so in my vew *larr has to seg fault
if instead of above "lar=arr;"

i32 n=len;

l0: *larr+=0x00010001; ++larr; --n; if(n>0) goto l0;


>>        do
>>          (*larr++)+=0x00010001;
>
>i not parse well *larr++
>
>>        while(--n);
>>      }

>>    }
>
>but that code is ok
>seems to me i see many error in that
>

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

#72073

On Tuesday, October 6, 2015 at 11:54:33 AM UTC-5, Rosario19 wrote:
> >>        *larr = (uint32_t*)arr;
> 
> larr is a pointer that has one not initializated value

Typo.  It should have been: larr = (int32_t*)arr;

Does that help?

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

#72064

On Tuesday, October 6, 2015 at 11:14:27 AM UTC-5, Rosario19 wrote:
> larr is one pointer to uint32_t

It points to a four-byte chunk of memory, which was written as two 16-bit
values, but expects to interpret that chunk of memory as one 32-bit value.
For systems which define pointer-to-intptr conversion in anything resembling
usual fashion, previous code will have ensured that the pointer satisfies the
alignment requirements for a uint32_t [unless, for some bizarre reason, a
system requires word alignment for 32-bit values but does not require
half-word alignment for 16-bit values--a situation which would be legal but
not representative of any hardware I've ever encountered].

> supercat wrote: 
> >        *larr = (uint32_t*)arr;
> 
> so *larr is one uint32_t

Correct.

> >          (*larr++)+=0x00010001;
> 
> i not parse well *larr++

This code adds 0x00010001 to the 32-bit value identified by "*larr" and
then updates "larr" so it will identify the next value.

For systems which are either big-endian or little-endian, interpreting
the memory occupied by two 16-bit values as a 32-bit value will interpret
one of the 16-bit values as representing the top half of the 32-bit value
and the other as representing the bottom half.  Provided that both halves
are below 65534, adding 0x00010001 will increment both halves.  If the
value which was interpreted as the lower half were equal to 65535, that
addition would corrupt the value in the upper half, but the stated
requirements for the function indicated that it only had to work in the
case where all values were 65534 or less.

> but that code is ok
> seems to me i see many error in that

What errors do you see?  The code is a bit tricky, but on many platforms it
will run twice as fast as would code that increments each 16-bit value
individually rather than two at a time.  It might be possible for a hyper-
modern compiler to achieve the same performance if the code were written as:

    for (int i=0; i<size; i++)
      if (arr[i] < 65535)
        arr[i]++;
      else
        1/0;  // Let the compiler know this path is Undefined Behavior

but the first "if" would slow down execution on most compilers, and it
would be hard to predict in what cases a compiler would be able to figure
out that it could handle the items two at a time.

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

#74418

On Tue, 6 Oct 2015 08:06:38 -0700 (PDT), supercat@casperkitty.com
wrote:
<snip>
> The effective type rules existed to avoid the requirement that a compiler
> for hardware which used type-tagged memory would have to process a code
> like "void inc_l(long *l) { l++; }" as 
> 
I presume you mean the body to be (*l)++ or more conveniently ++*l .
Else the result is "dead" (never used) and the statement can be
eliminated -- and IME usually was even by 1980's compilers.

>     void inc_l(long *l) {
>       long temp;
>       memcpy(&temp, l, sizeof l);
>       temp++; memcpy(l,
>       &temp, sizeof l);
>     }
> 
And those need to be sizeof(long), or sizeof(temp) or sizeof(*l) 
(with the parens optional in the latter 2). It's quite possible for a
pointer-to-long to be a different size than long. 

> even for the 99% of cases where the value would have last been written as
> type "long".  Requiring that programmers manually do the "memcpy" step on
> the rare occasions when it is necessary would allow code to be much more
> performant than it would be if the compiler had to do it always.
> 
In the similar but distinct case of strict alignment, the compilers
I've used had a convenient and unobtrusive extension something like
__notaligned or __onlyaligned<N> that caused the compiler to implement
a load or store through the pointer as bytes rather than a word, or
halfwords rather than a fullword or doubleword, or whatever. 
On architectures (or sometimes variants) where not needed you could
#define it away. GCC does (several) similar things with "attributes".

<snip example>

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

#74464

On Saturday, October 31, 2015 at 5:44:43 AM UTC-5, David Thompson wrote:
> On Tue, 6 Oct 2015 08:06:38 -0700 (PDT), supercat wrote:
> <snip>
> > The effective type rules existed to avoid the requirement that a compiler
> > for hardware which used type-tagged memory would have to process a code
> > like "void inc_l(long *l) { l++; }" as 
> > 
> I presume you mean the body to be (*l)++ or more conveniently ++*l .
> Else the result is "dead" (never used) and the statement can be
> eliminated -- and IME usually was even by 1980's compilers.

You infer correctly.

> >     void inc_l(long *l) {
> >       long temp;
> >       memcpy(&temp, l, sizeof l);
> >       temp++; memcpy(l,
> >       &temp, sizeof l);
> >     }
> > 
> And those need to be sizeof(long), or sizeof(temp) or sizeof(*l) 
> (with the parens optional in the latter 2). It's quite possible for a
> pointer-to-long to be a different size than long. 

Again, my mistake.

> > even for the 99% of cases where the value would have last been written as
> > type "long".  Requiring that programmers manually do the "memcpy" step on
> > the rare occasions when it is necessary would allow code to be much more
> > performant than it would be if the compiler had to do it always.
> > 
> In the similar but distinct case of strict alignment, the compilers
> I've used had a convenient and unobtrusive extension something like
> __notaligned or __onlyaligned<N> that caused the compiler to implement
> a load or store through the pointer as bytes rather than a word, or
> halfwords rather than a fullword or doubleword, or whatever. 
> On architectures (or sometimes variants) where not needed you could
> #define it away. GCC does (several) similar things with "attributes".

I have no objection to compilers regarding any pointers which are not aligned
for their types as trap values, and thus assuming that given:

    void copyLong(long *dest, long *src)
    {
      memmove(dest, src, sizeof *dest);
    }

it may replace the memmove with a "long" load followed by a "long" store
even though memmove would not normally require pointers to be aligned.

I do dislike the prohibition on memcpy being passed the same argument for
src and dest along with a non-zero size, however, since a lot of compilers
do a better job of optimizing memcpy than memmove, and given code like:

    void copyLong2(long *dest, long *src)
    {
      if (dest != src)
        memcpy(dest, src, sizeof *dest);
    }

a compiler could only optimize away the comparison if it could prove that
it was impossible for dest and src to both be null (since calling copyLong2
with two null pointers would be a defined safe no-op, but reading and
writing a null pointer would not be.)  I don't think there are many realistic
cases where prohibiting passing the same pointer to src and dest would allow
*useful* optimizations, but there are many situations where making that
undefined behavior could break code that omits the otherwise-useless
comparison (which, as noted, the compiler may not be able to optimize away).

Of course, for some situations like those were memcpy/memmove are only
being used to avoid being bitten by aliasing rules, a nicer approach would
simply be to have directives which would syntactically be equivalent to

  #define __ALIASING_BOUNDARY_FUNCTION
  #define __ALIASING_BOUNDARY_BLOCK if(0) {} else

except that storage written outside the directive could be read as any type
inside, and storage written inside it would be readable as any type outside.
Any compiler which could guarantee that aliasing rules would not be invoked
across function boundaries could define the first as shown above; a compiler
that ignored the aliasing rules altogether could define the second as above
[it would be nicer to have a directive which could be used both within and
around functions, but I can't think of any way to support that with existing
compilers the way the above definitions can].

Given that the value of type-based aliasing generally diminishes with the
size of the scope over which it is applied, while the semantic cost of
infinite reach is much greater than that of limited reach, being able to
limit the reach of type-based aliasing rules would offer huge semantic
benefit in relation to the runtime cost.

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

#74495

supercat@casperkitty.com writes:
[...]
> I do dislike the prohibition on memcpy being passed the same argument for
> src and dest along with a non-zero size, however, since a lot of compilers
> do a better job of optimizing memcpy than memmove, and given code like:
>
>     void copyLong2(long *dest, long *src)
>     {
>       if (dest != src)
>         memcpy(dest, src, sizeof *dest);
>     }
>
> a compiler could only optimize away the comparison if it could prove that
> it was impossible for dest and src to both be null (since calling copyLong2
> with two null pointers would be a defined safe no-op, but reading and
> writing a null pointer would not be.)
[...]

A compiler could optimize away the comparison if it knows that
    memcpy(foo, foo, non_zero)
is safe *for that implementation*.  Since memcpy is part of the
standard library and therefore part of the implementation, a compiler
may take advantage of any knowledge it has about its behavior.

A compiler designed to work with different runtime libraries could
not in general assume anything beyond what the standard guarantees
-- but a particular implementation of <string.h> might include
gcc-specific code that could provide extra information to gcc and
be ignored by other compilers.

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

#74498

On Saturday, October 31, 2015 at 3:53:23 PM UTC-5, Keith Thompson wrote:
> supercat writes:
> [...]
> > I do dislike the prohibition on memcpy being passed the same argument for
> > src and dest along with a non-zero size, however, since a lot of compilers
> > do a better job of optimizing memcpy than memmove, and given code like:
> >
> >     void copyLong2(long *dest, long *src)
> >     {
> >       if (dest != src)
> >         memcpy(dest, src, sizeof *dest);
> >     }
> >
> > a compiler could only optimize away the comparison if it could prove that
> > it was impossible for dest and src to both be null (since calling copyLong2
> > with two null pointers would be a defined safe no-op, but reading and
> > writing a null pointer would not be.)
> [...]
> 
> A compiler could optimize away the comparison if it knows that
>     memcpy(foo, foo, non_zero)
> is safe *for that implementation*.  Since memcpy is part of the
> standard library and therefore part of the implementation, a compiler
> may take advantage of any knowledge it has about its behavior.
> 
> A compiler designed to work with different runtime libraries could
> not in general assume anything beyond what the standard guarantees
> -- but a particular implementation of <string.h> might include
> gcc-specific code that could provide extra information to gcc and
> be ignored by other compilers.

I think you neglected that the compiler would also have to be able to
guarantee that either memcpy(NULL, NULL, non_zero) was safe (very rarely can
that be guaranteed, since even if address zero is known to be RAM there's
generally no way a compiler can be sure there isn't an interrupt it knows
nothing about that might modify that memory in a way that would be broken
by code that reads data from address zero and then writes it back) or else
that it was not possible for both src and dest to be null (in which case
the function, as written, would have defined behavior, but would invoke
memcpy(0,0, non_zero) if the test were eliminated.

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web