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

Groups > comp.compilers > #2205 > unrolled thread

Re: Optimization techniques

Back to article view | Back to comp.compilers

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: Optimization techniques David Brown <david.brown@hesbynett.no> - 2019-04-25 21:58 +0200
    Re: Optimization techniques Kaz Kylheku <847-115-0292@kylheku.com> - 2019-04-26 00:18 +0000
      Re: Optimization techniques David Brown <david.brown@hesbynett.no> - 2019-04-28 23:49 +0200
        Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-04-29 00:31 +0100
          Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-04-29 17:08 +0200
            Re: Optimization techniques and undefined behavior Christian Gollwitzer <auriocus@gmx.de> - 2019-04-29 18:10 +0200
              Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-04-30 14:46 +0200
                Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-01 13:53 +0100
                  Re: Optimization techniques and undefined behavior Andy Walker <anw@cuboid.co.uk> - 2019-05-02 11:29 +0100
                    Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-03 00:48 +0100
                      Re: Optimization techniques and undefined behavior Martin Ward <martin@gkc.org.uk> - 2019-05-03 10:52 +0100
                        Re: Optimization techniques and undefined behavior George Neuner <gneuner2@comcast.net> - 2019-05-04 17:44 -0400
                          Re: Bounds checking, Optimization techniques and undefined behavior George Neuner <gneuner2@comcast.net> - 2019-05-05 17:10 -0400
                        Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-06 08:14 +0200
                        Re: Optimization techniques and undefined behavior Gene Wirchenko <genew@telus.net> - 2019-05-11 22:25 -0700
                      Re: not a lot of memory, was Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-03 12:45 +0100
                      Re: Optimization techniques and undefined behavior Andy Walker <anw@cuboid.co.uk> - 2019-05-03 13:29 +0100
                        Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-03 23:10 +0100
                          Re: Optimization techniques and undefined behavior Andy Walker <anw@cuboid.co.uk> - 2019-05-04 10:45 +0100
                            Re: Bounds checking, Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-05 11:14 +0100
                              Re: Bounds checking, Optimization techniques and undefined behavior Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-05-05 20:44 +0200
                                Re: Bounds checking, Optimization techniques and undefined behavior Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-05-06 10:15 +0200
                                  Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 11:04 +0200
                                    Re: Bounds checking, Optimization techniques and undefined behavior "Nuno Lopes" <nuno.lopes@ist.utl.pt> - 2019-05-07 22:38 +0100
                                    Re: Bounds checking, Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-08 01:14 +0100
                                      Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-08 09:55 +0200
                                        Re: Bounds checking, Optimization techniques and undefined behavior "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2019-05-08 19:08 +0100
                                    Re: Bounds checking, Optimization techniques and undefined behavior Andy Walker <anw@cuboid.co.uk> - 2019-05-08 01:42 +0100
                                      Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-08 10:16 +0200
                                        Re: Bounds checking, Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-09 01:15 +0100
                                          Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-09 21:56 +0200
                                    Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-08 10:03 +0200
                                      Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-09 09:19 +0200
                                      Re: Bounds checking, Optimization techniques and undefined behavior Kaz Kylheku <847-115-0292@kylheku.com> - 2019-05-10 03:38 +0000
                                    Re: Bounds checking, Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-08 14:37 +0100
                                Re: Bounds checking, Optimization techniques and undefined behavior Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2019-05-06 05:05 -0400
                              Re: Bounds checking, Optimization techniques and undefined behavior George Neuner <gneuner2@comcast.net> - 2019-05-05 17:38 -0400
                                Re: Bounds checking, Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-06 13:07 +0100
                                  Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 14:01 +0200
                              Re: Bounds checking, Optimization techniques and undefined behavior Andy Walker <anw@cuboid.co.uk> - 2019-05-06 01:15 +0100
                                Re: Bounds checking, Optimization techniques and undefined behavior Andy Walker <anw@cuboid.co.uk> - 2019-05-06 14:40 +0100
                                  Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 15:05 +0200
                                    Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-08 10:18 +0200
                              Re: Bounds checking, Optimization techniques and undefined behavior Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2019-05-06 05:39 -0700
                                Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 15:42 +0200
                              Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-06 16:32 +0200
                          Re: Optimization techniques and undefined behavior George Neuner <gneuner2@comcast.net> - 2019-05-04 17:59 -0400
                  Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-02 16:51 +0200
                    Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-02 20:04 +0100
                      Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-03 17:23 +0200
                        Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-03 21:10 +0100
                        Re: Optimization techniques and undefined behavior Martin Ward <martin@gkc.org.uk> - 2019-05-06 13:25 +0100
                          Re: Optimization techniques and undefined behavior "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2019-05-06 16:32 +0100
                          Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 16:03 +0200
                            Re: Optimization techniques and undefined behavior Martin Ward <martin@gkc.org.uk> - 2019-05-08 13:16 +0100
                            Re: Optimization techniques and undefined behavior George Neuner <gneuner2@comcast.net> - 2019-05-08 15:13 -0400
                        Re: Optimization techniques and undefined behavior "Robin Vowels" <robin51@dodo.com.au> - 2019-05-07 01:22 +1000
                          Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 16:05 +0200
                    Re: Optimization techniques and undefined behavior Christian Gollwitzer <auriocus@gmx.de> - 2019-05-02 22:22 +0200
            Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-04-29 18:15 +0100
              Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-04-30 15:48 +0200
                Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-01 12:40 +0100
                  Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-02 17:27 +0200
                    Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-02 18:59 +0100
                      Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 16:16 +0200
                Re: Optimization techniques and undefined behavior Martin Ward <martin@gkc.org.uk> - 2019-05-02 14:54 +0100
        Re: Optimization techniques and runtime checks Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-04-29 22:36 +0200
          Re: Optimization techniques and runtime checks David Brown <david.brown@hesbynett.no> - 2019-05-07 16:29 +0200
            Re: Optimization techniques and runtime checks Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-05-08 02:27 +0200
              Re: Optimization techniques and runtime checks David Brown <david.brown@hesbynett.no> - 2019-05-08 10:31 +0200
                Re: Optimization techniques and runtime checks Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-05-08 22:50 +0200
                Re: Optimization techniques and runtime checks "Robin Vowels" <robin51@dodo.com.au> - 2019-05-11 19:26 +1000
                Re: Optimization techniques and runtime checks Gene Wirchenko <genew@telus.net> - 2019-05-11 22:43 -0700
                  Re: Optimization techniques and runtime checks David Brown <david.brown@hesbynett.no> - 2019-05-12 20:17 +0200
            Re: Optimization techniques and runtime checks Bart <bc@freeuk.com> - 2019-05-08 14:58 +0100
              Re: Optimization techniques and runtime checks David Brown <david.brown@hesbynett.no> - 2019-05-08 23:02 +0200
                Re: Optimization techniques and runtime checks Bart <bc@freeuk.com> - 2019-05-09 18:28 +0100
                  Re: Optimization techniques and runtime checks David Brown <david.brown@hesbynett.no> - 2019-05-09 22:07 +0200
        Re: Optimization techniques Gene Wirchenko <genew@telus.net> - 2019-04-30 18:24 -0700
          Re: Optimization techniques David Brown <david.brown@hesbynett.no> - 2019-05-01 09:20 +0200
            Re: Optimization techniques Kaz Kylheku <847-115-0292@kylheku.com> - 2019-05-02 17:40 +0000
            Re: Optimization techniques and error detection Gene Wirchenko <genew@telus.net> - 2019-05-03 10:16 -0700
            Re: Optimization techniques "Robin Vowels" <robin51@dodo.com.au> - 2019-05-07 01:42 +1000
    Re: Optimization techniques Kaz Kylheku <847-115-0292@kylheku.com> - 2019-04-26 02:26 +0000
      Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-04-29 00:12 +0200
        Re: Optimization techniques and undefined behavior Kaz Kylheku <847-115-0292@kylheku.com> - 2019-05-02 17:18 +0000
          Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 16:38 +0200

Page 2 of 5 — ← Prev page 1 [2] 3 4 5  Next page →

#2264 — Re: Bounds checking, Optimization techniques and undefined behavior

Am 05.05.2019 um 12:14 schrieb Bart:

> But how do they get there? Take this:
>
>     int A[10], *p;
>     p = &A[3];
>
> You intend p to refer to the 4-element slice A[3..6], but how does the
> language know that? How can it stop code from writing to p[5]?

Not pointers are bad, but pointer arithmetic is. It should be allowed
only with objects of known bounds.

DoDi
[In this case the bounds look known to me. -John]

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

#2269 — Re: Bounds checking, Optimization techniques and undefined behavior

Am 05.05.2019 um 20:44 schrieb Hans-Peter Diettrich:
> Am 05.05.2019 um 12:14 schrieb Bart:
>
>> But how do they get there? Take this:
>>
>>     int A[10], *p;
>>     p = &A[3];
>>
>> You intend p to refer to the 4-element slice A[3..6], but how does the
>> language know that? How can it stop code from writing to p[5]?
>
> Not pointers are bad, but pointer arithmetic is. It should be allowed
> only with objects of known bounds.
>
> DoDi
> [In this case the bounds look known to me. -John]

The bounds are known for the array, so that the pointer is guaranteed
valid by compile time check. But p[x] or p+x can not be guaranteed valid
without considerable runtime and bounds storage overhead. Also simple
p++ operation or the like requires an update of the bounds information.
That's what I consider pointer arithmetic, not above &A[3].

I learned to love the Pascal indexing instead of pointers, because a
loop like
   for i := 1 to 10 do sum := sum + A[i];
can be optimized safely by the Pascal/Delphi compiler into pointer and
auto increment, so that no speed penalty exists vs. explicit pointer
usage. But in a C for loop the index variable can be changed in code, so
that even above code would execute slower with bounds checks.

DoDi

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

#2280 — Re: Bounds checking, Optimization techniques and undefined behavior

On 06/05/2019 10:15, Hans-Peter Diettrich wrote:
> Am 05.05.2019 um 20:44 schrieb Hans-Peter Diettrich:
>> Am 05.05.2019 um 12:14 schrieb Bart:
>>
>>> But how do they get there? Take this:
>>>
>>>     int A[10], *p;
>>>     p = &A[3];
>>>
>>> You intend p to refer to the 4-element slice A[3..6], but how does the
>>> language know that? How can it stop code from writing to p[5]?
>>
>> Not pointers are bad, but pointer arithmetic is. It should be allowed
>> only with objects of known bounds.
>>
>> DoDi
>> [In this case the bounds look known to me. -John]
>
> The bounds are known for the array, so that the pointer is guaranteed
> valid by compile time check. But p[x] or p+x can not be guaranteed valid
> without considerable runtime and bounds storage overhead. Also simple
> p++ operation or the like requires an update of the bounds information.

That depends on x, and what other operations are done on the pointers.

For example, given this:

	for (int x = 0; x < 7; x++) {
		p[x] = 10;
	}

the compiler can see that the access is valid.  Change the limit to 8,
and the compiler can tell that it is invalid.  (gcc can spot this one.)

But of course if x comes from elsewhere, it is going to take very
advanced analysis to figure out anything about its validity.


> That's what I consider pointer arithmetic, not above &A[3].
>

&A[3] is pointer arithmetic too.  A more useful distinction might be for
pointer calculations where the compiler knows the addresses or ranges at
compile time, however they might be expressed.


> I learned to love the Pascal indexing instead of pointers, because a
> loop like
>   for i := 1 to 10 do sum := sum + A[i];
> can be optimized safely by the Pascal/Delphi compiler into pointer and
> auto increment, so that no speed penalty exists vs. explicit pointer
> usage. But in a C for loop the index variable can be changed in code, so
> that even above code would execute slower with bounds checks.
>

It will not be slower in C - because the compiler knows that "i" is
never changed in the loop.  (I'd like some way to have that enforced in
C, but I don't know of any good method.)

Just for a laugh, try this code:
#include <stdio.h>

int main(void) {
        int i;
        int j;
        int *pi = &i;
        int *pj = &j;
        int sum = 0;

        printf("pi = %p, pj[-1] = %p\n", (void*) pi, (void*) &pj[-1]);

        for (i = 0; i < 11; i++) {
                if (i == 3) {
                        pj[-1] = 5;
                }
                sum += i;
        }
        printf("Sum is %i\n", sum);
}

Depending on the compiler, you might need to swap "int i;" and "int j;".
 The first printf shows that "pi" and "pj[-1]" point to the same
address, that of "i".  With no optimisation and a literal translation of
the code, the result will be 48.  With optimisation, the compiler knows
that access through "pj" cannot possibly affect "i" without invoking
undefined behaviour - so it can simplify the loop to "sum = 55;" and
shows that result.

[For the loop with the unchangable index, you can declare the index
const and cast the places you change it, but ugh.

        const int i;

        for(*(int*)&i = 0; i < 10; (*(int*)&i)++) {
                a[i] = i;
                i++; /* will be diagnosed as an error */
        }
-John]

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

#2291 — Re: Bounds checking, Optimization techniques and undefined behavior

Hi,

[shameless plug:]
Here's a link to the slides of a talk I have last January on undefined
behavior (UB) for compiler IRs:

http://web.ist.utl.pt/nuno.lopes/pres/ub-vmcai19.pptx

The slides have a bunch of examples showing why UB is sometimes useful for
compilers, when it is detrimental, or why it's basically impossible to make
certain languages fully specified.

Nuno

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

#2292 — Re: Bounds checking, Optimization techniques and undefined behavior

On 07/05/2019 10:04, David Brown wrote:

> Just for a laugh, try this code:
> #include <stdio.h>
>
> int main(void) {
>          int i;
>          int j;
>          int *pi = &i;
>          int *pj = &j;
>          int sum = 0;
>
>          printf("pi = %p, pj[-1] = %p\n", (void*) pi, (void*) &pj[-1]);
>
>          for (i = 0; i < 11; i++) {
>                  if (i == 3) {
>                          pj[-1] = 5;
>                  }
>                  sum += i;
>          }
>          printf("Sum is %i\n", sum);
> }

This is the sort of code that /I/ would say has undefined behaviour. In
this case because pj points to a 1-element block, and you writing
outside that block.

With my C compiler, it shows '55', whatever order i and j are defined
in. That's because these int32 types are 64-bit aligned so have a 4-byte
gap between. I could get '48' if I changed the ints to 64 bits.

Translating to my language, and in the knowledge that the (64-bit) ints
there are assigned consecutively, and knowing that j follows i, then I
would expect a result of 48.

I expect it because that's what I coded, and my compilers tend to do
what I tell them in the language. If I wanted to do something underhand
like this for some genuine reason, and which would be well-defined
according to the provisos above, then I don't want to have to fight the
compiler to achieve it.

In that case, a compiler generating '55' would be undesirable.

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

#2295 — Re: Bounds checking, Optimization techniques and undefined behavior

On 08/05/2019 02:14, Bart wrote:
> On 07/05/2019 10:04, David Brown wrote:
>
>> Just for a laugh, try this code:
>> #include <stdio.h>
>>
>> int main(void) {
>>          int i;
>>          int j;
>>          int *pi = &i;
>>          int *pj = &j;
>>          int sum = 0;
>>
>>          printf("pi = %p, pj[-1] = %p\n", (void*) pi, (void*) &pj[-1]);
>>
>>          for (i = 0; i < 11; i++) {
>>                  if (i == 3) {
>>                          pj[-1] = 5;
>>                  }
>>                  sum += i;
>>          }
>>          printf("Sum is %i\n", sum);
>> }
>
> This is the sort of code that /I/ would say has undefined behaviour. In
> this case because pj points to a 1-element block, and you writing
> outside that block.
>

Yes, exactly.  But it is undefined behaviour because using a pointer
outside the object it points to, is undefined behaviour in C (and many
languages).  This is the case even though "pj[-1]" is the same numeric
value as "pi" - at the assembly level, they are the same address.

> With my C compiler, it shows '55', whatever order i and j are defined
> in. That's because these int32 types are 64-bit aligned so have a 4-byte
> gap between. I could get '48' if I changed the ints to 64 bits.

OK, the compiler is of course free to align these variables as it sees fit.

>
> Translating to my language, and in the knowledge that the (64-bit) ints
> there are assigned consecutively, and knowing that j follows i, then I
> would expect a result of 48.
>
> I expect it because that's what I coded, and my compilers tend to do
> what I tell them in the language. If I wanted to do something underhand
> like this for some genuine reason, and which would be well-defined
> according to the provisos above, then I don't want to have to fight the
> compiler to achieve it.

In C, what I coded was buggy - it has no defined behaviour.  What /I/
want the compiler to do, is warn me about it.  (gcc doesn't, at least
not with the flags I tried.  Maybe next version will - I always hope for
better warnings.)  And I want the compiler to assume that I am not
intentionally doing something bad like this, so that it can better
optimise correct code.  If this were real code, I would /not/ expect an
answer of 48, because the code was in error.

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

#2304 — Re: Bounds checking, Optimization techniques and undefined behavior

David,

> In C, what I coded was buggy - it has no defined behaviour.  What /I/
> want the compiler to do, is warn me about it.  (gcc doesn't, at least
> not with the flags I tried.  Maybe next version will - I always hope for
> better warnings.)  And I want the compiler to assume that I am not

You might like to give Cerberus a go:
http://cerberus.cl.cam.ac.uk/cerberus

To cover all cases, click Options and untick
Sequentialise operations (soon to be the default, I'm told).


--
Derek M. Jones
blog:shape-of-code.coding-guidelines.com

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

#2293 — Re: Bounds checking, Optimization techniques and undefined behavior

On 07/05/2019 10:04, David Brown wrote:
> It will not be slower in C - because the compiler knows that "i" is
> never changed in the loop.  (I'd like some way to have that enforced in
> C, but I don't know of any good method.)

	There's rather little you can "enforce" in C unless the compiler
is on your side!  See below.

> Just for a laugh, try this code: [largely snipped for brevity -- ANW]
> #include <stdio.h>
>          int *pi = &i;
>          int *pj = &j;
>          printf("pi = %p, pj[-1] = %p\n", [...]

	There is sanction in the Standard for adding one to a pointer to
a scalar, but not for subtracting one;  so this is UB [N1570, section
6.5.6, paras 7, 8].

> [...] With no optimisation and a literal translation of
> the code, the result will be 48.

	Yes, provided that the compiler doesn't enforce the Standard!

>				    With optimisation, the compiler knows
> that access through "pj" cannot possibly affect "i" without invoking
> undefined behaviour - so it can simplify the loop to "sum = 55;" and
> shows that result.

	Quite.  That's the sort of way that UB comes back to bite you.
You optimise some code, and the answer changes.  There are worse
possibilities, even without going beyond reasonableness;  take, for
example Bart's "struct" with four integer members that he wants to
treat as an array.  Suppose further that he tries to write to the i'th
member of that array, even after checking that 0 <= i <= 3.  A non-
checking compiler will allow that, even though it's UB if i > 0.  An
optimising compiler may quite well, however, deduce that "therefore"
i = 0, and carry that value of "i" forward in the analysis.  If the
decision whether or not to "rm -rf /" depends on the value of "i",
you can be well and truly up the creek without a paddle.

[Moderator:]
> [For the loop with the unchangable index, you can declare the index
> const and cast the places you change it, [...].

	As so often, you may well get away with it, but it's UB.  See
in particular footnote 132 --

   " The implementation may place a const object that is not volatile
   " in a read-only region of storage. "

Further, if you can change the index that way, so can a malicious or
careless writer of the loop body, which rather negates the point of
making it "const".  To do it properly, it needs to be a defined and
checkable property in the language, as in, for example, Algol 68.

--
Andy Walker,
Nottingham.
[Hey, I said "but ugh".  I would think that an auto const without a
constant initializer wouldn't be eligible for read-only storage since
it might have a different value each time the block is entered. -John]

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

#2297 — Re: Bounds checking, Optimization techniques and undefined behavior

On 08/05/2019 02:42, Andy Walker wrote:
> On 07/05/2019 10:04, David Brown wrote:
>> It will not be slower in C - because the compiler knows that "i" is
>> never changed in the loop.  (I'd like some way to have that enforced in
>> C, but I don't know of any good method.)
>
>     There's rather little you can "enforce" in C unless the compiler
> is on your side!  See below.
>
>> Just for a laugh, try this code: [largely snipped for brevity -- ANW]
>> #include <stdio.h>
>>          int *pi = &i;
>>          int *pj = &j;
>>          printf("pi = %p, pj[-1] = %p\n", [...]
>
>     There is sanction in the Standard for adding one to a pointer to
> a scalar, but not for subtracting one;  so this is UB [N1570, section
> 6.5.6, paras 7, 8].
>

Yes, it is UB.  Even if "i" and "j" are swapped (or the compiler
allocation different) so that you would be using pj[1], you are not
allowed to dereference pj[1], merely to calculate it and use it for
certain comparisons.

>> [...] With no optimisation and a literal translation of
>> the code, the result will be 48.
>
>     Yes, provided that the compiler doesn't enforce the Standard!
>
>>                     With optimisation, the compiler knows
>> that access through "pj" cannot possibly affect "i" without invoking
>> undefined behaviour - so it can simplify the loop to "sum = 55;" and
>> shows that result.
>
>     Quite.  That's the sort of way that UB comes back to bite you.

It is not the UB that is biting you, as such - it is the bug in the
code.  When your code is wrong (as mine is), according to the language
rules, then you can never expect a "correct" answer.  This sample
demonstrates how the compiler can assume that UB does not occur and give
faster and more efficient code, though it makes the result of the wrong
code unstable.

> You optimise some code, and the answer changes. 

Yes - that happens when your code has a bug.

I have many times seen questions from programmers along the lines of "my
code works with optimisation disabled, but fails when optimisation is
enabled" - it means they have a bug in their code.

> There are worse
> possibilities, even without going beyond reasonableness;  take, for
> example Bart's "struct" with four integer members that he wants to
> treat as an array.  Suppose further that he tries to write to the i'th
> member of that array, even after checking that 0 <= i <= 3.  A non-
> checking compiler will allow that, even though it's UB if i > 0.  An
> optimising compiler may quite well, however, deduce that "therefore"
> i = 0, and carry that value of "i" forward in the analysis.  If the
> decision whether or not to "rm -rf /" depends on the value of "i",
> you can be well and truly up the creek without a paddle.

I note that in Bart's compiler, if he had four local "int" variables,
they would be aligned at 64-bit spacing.  He could quite reasonably have
the same thing in his struct.  Then trying to access the struct elements
as an array is bound to fail.

There are good reasons why this sort of thing is UB.

And yes, if your decision to "rm -rf /" depends on UB, you are in
trouble.  You are equally in trouble if you have /any/ bug in your code,
even if the code has fully defined behaviour according to the language.
 There is /nothing/ special about UB in that respect - it is just a bug.

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

#2308 — Re: Bounds checking, Optimization techniques and undefined behavior

On 08/05/2019 09:16, David Brown wrote:
> On 08/05/2019 02:42, Andy Walker wrote:

>>
>>      Quite.  That's the sort of way that UB comes back to bite you.
>
> It is not the UB that is biting you, as such - it is the bug in the
> code.  When your code is wrong (as mine is), according to the language
> rules, then you can never expect a "correct" answer.  This sample
> demonstrates how the compiler can assume that UB does not occur and give
> faster and more efficient code, though it makes the result of the wrong
> code unstable.

This is actually a little worrying. The code includes these lines:

                 if (i == 3) {
                         pj[-1] = 5;
                 }

The programmer didn't just add them for no reason. Why then should a
compiler just blithely ignore them?

Either it should do what the code says, or explain why it's ignoring
your instructions and doing something else instead. (I couldn't get gcc,
clang or msvc to say anything about it. BTW msvc gives either 55 or 57,
rather than 55 or 48.)


>> You optimise some code, and the answer changes.
>
> Yes - that happens when your code has a bug.
>
> I have many times seen questions from programmers along the lines of "my
> code works with optimisation disabled, but fails when optimisation is
> enabled" - it means they have a bug in their code.

And a few times I've found it to be a bug in a compiler.

>> There are worse
>> possibilities, even without going beyond reasonableness;  take, for
>> example Bart's "struct" with four integer members that he wants to
>> treat as an array.  Suppose further that he tries to write to the i'th
>> member of that array, even after checking that 0 <= i <= 3.  A non-
>> checking compiler will allow that, even though it's UB if i > 0.  An
>> optimising compiler may quite well, however, deduce that "therefore"
>> i = 0, and carry that value of "i" forward in the analysis.  If the
>> decision whether or not to "rm -rf /" depends on the value of "i",
>> you can be well and truly up the creek without a paddle.

> I note that in Bart's compiler, if he had four local "int" variables,
> they would be aligned at 64-bit spacing.  He could quite reasonably have
> the same thing in his struct.  Then trying to access the struct elements
> as an array is bound to fail.

No, struct layouts have to match C's rules for those, or at least be
compatible with other compilers on the same platform.

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

#2311 — Re: Bounds checking, Optimization techniques and undefined behavior

On 09/05/2019 02:15, Bart wrote:
> On 08/05/2019 09:16, David Brown wrote:
>> On 08/05/2019 02:42, Andy Walker wrote:
>
>>>
>>>      Quite.  That's the sort of way that UB comes back to bite you.
>>
>> It is not the UB that is biting you, as such - it is the bug in the
>> code.  When your code is wrong (as mine is), according to the language
>> rules, then you can never expect a "correct" answer.  This sample
>> demonstrates how the compiler can assume that UB does not occur and give
>> faster and more efficient code, though it makes the result of the wrong
>> code unstable.
>
> This is actually a little worrying. The code includes these lines:
>
>                  if (i == 3) {
>                          pj[-1] = 5;
>                  }
>
> The programmer didn't just add them for no reason. Why then should a
> compiler just blithely ignore them?

It is a bug in the code, since it does not follow the rules of the
language.  So either the programmer put them in for no reason (i.e., by
mistake), or they he/she put them in for wrong reasons - there being no
possibility of valid reasons for incorrect code.

The compiler may do the best it can with bad code.  That can include
ignoring it, but can also include attempting the write while still
assuming it has no influence on "i".  When trying this code, I first had
"pj[1]" rather than "pj[-1]".  The compiler generated the write, which
led to a OS error message telling me the program had a "stack smashing"
fault.  Arguably, that is the second best thing the compiler could do.
(The best thing would be a compile-time error message, which gcc did not
give.)

>
> Either it should do what the code says, or explain why it's ignoring
> your instructions and doing something else instead. (I couldn't get gcc,
> clang or msvc to say anything about it. BTW msvc gives either 55 or 57,
> rather than 55 or 48.)
>

Often it is very difficult to give error messages for this kind of
thing, without also giving lots of false positive in other situations.
It can be difficult to understand how it can be that the compiler can
see there is something odd that it can use for optimisation, but not be
able to warn about the situation.

>
>>> You optimise some code, and the answer changes.
>>
>> Yes - that happens when your code has a bug.
>>
>> I have many times seen questions from programmers along the lines of "my
>> code works with optimisation disabled, but fails when optimisation is
>> enabled" - it means they have a bug in their code.
>
> And a few times I've found it to be a bug in a compiler.
>

I have occasionally found bugs in compilers - the possibility cannot be
excluded.  (I have reported a couple in gcc.)  But in most cases, the
great majority of cases, it is the user code that is at fault.

>>> There are worse
>>> possibilities, even without going beyond reasonableness;  take, for
>>> example Bart's "struct" with four integer members that he wants to
>>> treat as an array.  Suppose further that he tries to write to the i'th
>>> member of that array, even after checking that 0 <= i <= 3.  A non-
>>> checking compiler will allow that, even though it's UB if i > 0.  An
>>> optimising compiler may quite well, however, deduce that "therefore"
>>> i = 0, and carry that value of "i" forward in the analysis.  If the
>>> decision whether or not to "rm -rf /" depends on the value of "i",
>>> you can be well and truly up the creek without a paddle.
>
>> I note that in Bart's compiler, if he had four local "int" variables,
>> they would be aligned at 64-bit spacing.  He could quite reasonably have
>> the same thing in his struct.  Then trying to access the struct elements
>> as an array is bound to fail.
>
> No, struct layouts have to match C's rules for those, or at least be
> compatible with other compilers on the same platform.

C allows you to have whatever padding you want, but if you want
compatibility with other compilers or ABI's, then of course you need to
follow their layout.

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

#2296 — Re: Bounds checking, Optimization techniques and undefined behavior

On 07/05/2019 11:04, David Brown wrote:
> [For the loop with the unchangable index, you can declare the index
> const and cast the places you change it, but ugh.
>
>         const int i;
>
>         for(*(int*)&i = 0; i < 10; (*(int*)&i)++) {
>                 a[i] = i;
>                 i++; /* will be diagnosed as an error */
>         }
> -John]
>

Looking more closely at your code here, it is wrong.

You can cast away "const" from something that was originally declared
without "const" and had "const" added via a cast.  You cannot cast away
"const" from something declared "const".  The compiler is free to assume
that "i" never changes, and ignore (or complain about) your attempts to
change it via the casts.

There is a much better way, but it is still ugly:

	for (int i = 0; i < 10; i++) {
		const int ii = i; const int i = ii;

		a[i] = 1;
		i++;		// Error
	}

You can, of course, just use a new local const variable, but then you
lose the matching names.


In C++, this won't work because the first "int i" scope is /inside/ the
compound statement, while in C it is /before/ that statement.  In C++,
you need:

	for (int i = 0; i < 10; i++) {{
		const int ii = i; const int i = ii;

		a[i] = 1;
		i++;		// Error
	}}


So it can be done, but it would be nicer if it were better integrated in
the language.  For a new language, I would make such immutability part
of the definition of the "for" loop.

[I'm looking at C11 and don't see where it says you can't cast away
const.  What am I missing?  I agree any approach here is ugly and we're
near the limits of what you can say in C. -John]

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

#2309 — Re: Bounds checking, Optimization techniques and undefined behavior

On 08/05/2019 10:03, David Brown wrote:

>
> [I'm looking at C11 and don't see where it says you can't cast away
> const.  What am I missing?  I agree any approach here is ugly and we're
> near the limits of what you can say in C. -John]
>

6.7.3p6 :

"""
If an attempt is made to modify an object defined with a const-qualified
type through use of an lvalue with non-const-qualified type, the
behavior is undefined.
"""


Consider this code:

int v = 10;
const int c = 20;

void change(const int * p, int n) {
	*(int*) p = n;
}

int foo(int a) {
	change(&v, a);		// OK
	change(&c, a);		// Usually compiles, but NOT OK

	return c;
}



You can cast away const (via pointers), but if the original declaration
of the object was const, it is undefined behaviour.

Compiling this with gcc x86 and optimisation (with
<https://godbolt.org>), you get this:

change:
        mov     DWORD PTR [rdi], esi
        ret
foo:
        mov     DWORD PTR v[rip], edi
        mov     eax, 20
        mov     DWORD PTR c[rip], edi
        ret
c:
        .long   20
v:
        .long   10


Although the call "change(&c, a)" attempts to modify "c" (which will
likely cause a fault on many systems), the compiler assumes the value of
"c" is still 20 for the return.
[Oh, look at that.  Tried it with clang, did the same thing returning a constant 20. -John]

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

#2313 — Re: Bounds checking, Optimization techniques and undefined behavior

On 2019-05-08, David Brown <david.brown@hesbynett.no> wrote:
> [I'm looking at C11 and don't see where it says you can't cast away
> const.  What am I missing?  I agree any approach here is ugly and we're
> near the limits of what you can say in C. -John]

By the way, on a tangent related to this topic, I use the following
definitions in code that compiles both as C and C++:

#ifdef __cplusplus
#define strip_qual(TYPE, EXPR) (const_cast<TYPE>(EXPR))
#define convert(TYPE, EXPR) (static_cast<TYPE>(EXPR))
#define coerce(TYPE, EXPR) (reinterpret_cast<TYPE>(EXPR))
#else
#define strip_qual(TYPE, EXPR) ((TYPE) (EXPR))
#define convert(TYPE, EXPR) ((TYPE) (EXPR))
#define coerce(TYPE, EXPR) ((TYPE) (EXPR))
#endif

When compiling as C++, I get diagnostics from the more nuanced cast
operators, which reduce to just regular C casts when compiling as C.

For instance, casting away const requires strip_qual(type, val).

That's just one way we can get the benefits of some C++ safety
without leaving C. Another example is the stronger type safety
of enumerations, and the rules around void * conversions.

--
TXR Programming Lanuage: http://nongnu.org/txr
Music DIY Mailing List:  http://www.kylheku.com/diy
ADA MP-1 Mailing List:   http://www.kylheku.com/mp1
[Wow, that's ugly.  -John]

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

#2302 — Re: Bounds checking, Optimization techniques and undefined behavior

On 07/05/2019 10:04, David Brown wrote:
> On 06/05/2019 10:15, Hans-Peter Diettrich wrote:

>> I learned to love the Pascal indexing instead of pointers, because a
>> loop like
>>    for i := 1 to 10 do sum := sum + A[i];
>> can be optimized safely by the Pascal/Delphi compiler into pointer and
>> auto increment, so that no speed penalty exists vs. explicit pointer
>> usage. But in a C for loop the index variable can be changed in code, so
>> that even above code would execute slower with bounds checks.
>>
>
> It will not be slower in C - because the compiler knows that "i" is
> never changed in the loop.  (I'd like some way to have that enforced in
> C, but I don't know of any good method.)

Making loop variables declared in a for-header be implicitly 'const'
could be done:

    for (int i=0; i<N; ++i)

This can be the same as 'const i=0'.

The problem is that in such a loop (of the kind I frequently malign in
c.l.c and you always disagree), the code to increment this loop variable
is in user-code. So it is subject to the same rules as all other code,
and i cannot be changed.

In a more typical for-loop, such increments are done behind the scenes,
while still keeping the loop index read-only in user-code.

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

#2270 — Re: Bounds checking, Optimization techniques and undefined behavior

While I join this conversation with trepidation as it is generating
more heat than light, I need to make a few points.

    1) “Built in” Array bounds checking can be done in C.  It actually
can be done in assembly language.  And, by built in, I mean when the
system enforces it even when the user doesn’t explicitly write it.
(More on this below.)

    2) C++ with vectors supports exactly the kind of for-loops
suggested.  In fact, it seems to be the preferred idiom these days.

I know item 1 for a fact, because while I was at DEC circa 1995, one
of my tasks was working on “Third degree”.  Third degree was a tool
written by DEC Labs for the Alpha computers to replace “Purify” (aka
“Saber C”) which Rational Software wanted $10 million to port and
$100k/per instance.  A similar tool was (is?) available for Intel PCs
called “Bounds Checker”.  Valgrind does roughly the same stuff if I
understand it right.   And those aren’t the only tools to do so.
Malloc like libraries that do some of the checking are also quite
common.  So, don’t blame C/C++ or the relevant compilers that you
aren’t getting your array bounds checked, or that you have dangling
pointers or garbage that isn’t deallocated.  It can be done.

That includes if you want slices.  I don’t know any tool that does
that explicitly, but it wouldn’t be hard to write.

Anyway, the point I wanted to make is that Third degree didn’t even
need the original source code.  Third degree worked from the object
files (or from an executable file).  It decompiled them, instrumented
them, and checked for all the common errors.  The basic ideas that it
was based upon were all developed in the 1960s (or perhaps before).

It isn’t necessarily the declaration in source code that gives an
object its bounds.  An object naturally has bounds.  You just have to
understand the underlying semantic model.  Again, this was realized in
the 1960s if not before.

If your model says that something handed back by the allocator is an
object and that you cannot reference beyond it.  You can create the
requisite fat pointer.  You can find all the places in the code, where
the fat pointer is used.  You can instrument them with whatever checks
you need.  You can even apply optimization checks (and Third degree
did) that eliminate the need for checks that are redundant and cannot
fail (or vice versa, that will always fail).

You can do that for arithmetic too.  You don’t need support from the
compiler.  You just need to understand the semantics you want.

Now, that doesn’t mean you can solve the Halting problem.  Code that
generates code and jumps to it is significantly harder to make work.
But, even that can be solved if you know what semantics you want to
support.  Debuggers have long inserted “trap instructions” into code
that replace bits of code to be checked, so that if the code is
executed, it goes and does some other code sequence that has the same
semantics but with additional checks. Think aspect oriented
programming at the machine code level.

You can even get that if your model of generated code is C.  You can
generate C that applies the checks you want (and only those you want).
There is nothing in the language that prevents you from doing that.
In fact, the nature of C is to make that possible.  That’s why C is
the modern portable assembly language.

Undefined behavior is just there because not every underlying machine
supports exactly the same semantics and if you want a universal
assembler, you have to deal with the fact that the minimal coding
sequence may have different results given the different underlying
semantics.  Even if you stay in the x86 family.  The best code for an
8086 is not the best code for an amd64 machine and the semantic models
are different despite there being a portable subset that would work on
both.

So, the hard part is defining a balance that one presents to the
users.  The balance C struck is that the code will be simple “assembly
like” and you will get something as close to what you would have hand
written in assembler (without checks) as the compiler can give you.
That includes assuming that the rules of arithmetic apply and that
x*4/4 (so macros where the two constant 4s may come from different
places, but you still want them to cancel work) is still x despite
overflows, but if the compiler cannot detect the overflow and it
happens you get whatever the machine gives you.

That’s exactly the code I want.  Because, I know that there will be
places in my code where something goes wrong no matter how carefully I
(and my team mates) craft it, we are human and make mistakes.  Thus,
we know how to practice defensive programming.  Programming that
checks for a pointer that in theory should never be null is actually
not null and those checks still catch things, things like the ECC code
on the chip missing a double-bit error caused by stray radiation or a
transistor that switched too slowly.

The code was correct, but quantum mechanics got in the way.  And
that’s reality.  Mathematically correct doesn’t catch the fact that
the under carefully controlled conditions of heat and pressure the
system does what it pleases.  And, yes, I have fixed bugs like that,
where the source code was correct, but the resulting system didn’t
work for reasons outside the programmers control.  But, of course,
many more bugs where the source code simply wasn’t correct or bugs
because the spec changed and the code hadn’t been updated yet.

Now, most people can’t deal with that.  They want to imagine that
their world is safe and that they can write simple code that will
“just work”.  My stint at Google showed me that point of view in
spades.  So, you can turn on -Wall, which many people do, and many
teams require.  Then you find, you cannot write the code (at least not
and have it pass by *all* compilers with no warnings/errors).

int32_t sum, increment, max;

sum = 0; max = something_far_less_than_maxint6;

for something {
   increment = some_small_value; // such that sum + increment will not
overflow, not even an int16
   if (max <= increment + sum) break;
   sum += increment;  // with -Wall, you get a warning about possible
overflow
   }

The compile time checks are simply not clever enough to realize that
this cannot overflow. You cannot even fix it with:

Int64_t added;

      added = sum + increment;
      if (max <= added) break;
      sum = added; // -Wall still warns here about potential overflow
(loss of data)

There are no casts you can do.  No coding tricks, short of applying a
compiler specific pragma to suppress the warning.

Until we have much smarter compilers, this is our fate.  Kvetching
about C is not going to fix that.   Of fast, easy to write, and always
correct you can pick 2.  It’s not the fault of C, that you cannot get
all 3.

--
*****************************************************************************
Chris Clark                  email:
christopher.f.clark@compiler-resources.com
Compiler Resources, Inc.  Web Site: http://world.std.com/~compres
23 Bailey Rd                 voice: (508) 435-5016
Berlin, MA  01503 USA      twitter: @intel_chris
-----------------------------------------------------------------------------

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

#2266 — Re: Bounds checking, Optimization techniques and undefined behavior

On Sun, 5 May 2019 11:14:51 +0100, Bart <bc@freeuk.com> wrote:

>On 04/05/2019 10:45, Andy Walker wrote:
>> On 03/05/2019 23:10, Bart wrote:
>
>>> C is just a mess; it has arrays of sorts, but people generally use raw
>>> pointers without associated bounds. Maybe that's one reason why your C
>>> didn't have it. Or did it somehow manage it if enabled?
>>
>>      This isn't really a problem with C, the language.  It's clear in
>> the reference manual right back to K&R C and in the various standards
>> that pointers always have associated bounds.
>
>But how do they get there? Take this:
>
>     int A[10], *p;
>     p = &A[3];
>
>You intend p to refer to the 4-element slice A[3..6], but how does the
>language know that? How can it stop code from writing to p[5]?

You declare 'p' as  int (*p)[4]  and then the compiler could check the
use.  Theoretically at least, I'm not sure it actually is done in many
situations.

But few programmers even take the trouble to declare the pointers
appropriately.


>Or you intend to index p[-2] to get at the preceding elements. Actually
>using negative indexing is quite common, but surely all array bounds in
>C are presumed to start from 0?
>
>Or this:
>
>   struct {int a,b,c,d;} S;
>
>   p = &S.a;
>
>You intend p to be used to access a,b,c,d as an int[4] array, but p's
>bounds will say it's only one element long.

The larger problem is that C even permits that.  If you want the
struct elements also to be available as an array, you should have used
a union.


>Or this:
>
>    int *p = malloc(sizeof(int)*1000);
>
>    int *q = p+400;
>
>You are allocating one pool of memory than sub-allocating that into
>smaller objects, here into a 20-element array headed by q. But how does
>the language know that?

Again 'q' is not declared appropriately such that the compiler *could*
check it.


>With language support, it need have no cost. For example, suppose that
>array A did carry its bounds with it (or are statically known), then in
>code like this:
>
>     for i in A do       # (iterate over bounds not values)
>         A[i] := 0
>     end
>
>the compiler knows it doesn't need to bounds-check each access. Or here:
>
>     forall x in A do    # (iterate over values)
>         print x
>     end

C has a lot of warts, no question ... but its biggest problem is that
the routine (ab)use of pointers in, so-called, "idiomatic" C in a real
sense is working against the compiler - making it's job much harder.


George

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

#2271 — Re: Bounds checking, Optimization techniques and undefined behavior

On 05/05/2019 22:38, George Neuner wrote:
> On Sun, 5 May 2019 11:14:51 +0100, Bart <bc@freeuk.com> wrote:

>> You intend p to refer to the 4-element slice A[3..6], but how does the
>> language know that? How can it stop code from writing to p[5]?
>
> You declare 'p' as  int (*p)[4]  and then the compiler could check the
> use.  Theoretically at least, I'm not sure it actually is done in many
> situations.

I declare pointers to arrays as T(*)[] when generating C code. But
you're right in that no one else does that when writing C.

Note that this is an open bound; usually the bound will be dynamic, and
held in a separate variable, which the language does not know is the bound.

C has something called VLAs, which is really a type where any bounds are
defined as a runtime expression. If you had a loop which extracted
different slices on each iteration, you would obliged to declare 'p'
within the loop, so it has a slightly different type (with different
bounds) each time around.

But this is very restrictive (for example I don't like using local block
scopes). It is also a rather heavyweight feature just to allow the
possibility of bounds checking.

(Also something I haven't implemented in my own C compiler; I just don't
know how to approach it. And I don't like the feature.)

Proper slicing (since we are not restricted to C or other existing
languages) is simpler and better.

>>    struct {int a,b,c,d;} S;
>>
>>    p = &S.a;
>>
>> You intend p to be used to access a,b,c,d as an int[4] array, but p's
>> bounds will say it's only one element long.
>
> The larger problem is that C even permits that.

I was half-expecting someone to say it was undefined behaviour. I
suppose you will say the way to declare that pointer is as:

    int (*p)[4] = (int(*)[4])&S.a;

The problem is that if you want to make C a safer, checked language,
none of this stops people writing it the wrong way.

> If you want the
> struct elements also to be available as an array, you should have used
> a union.

Maybe the struct is defined elsewhere and is not your code to change. Or
maybe the struct is {int a,b,c[20];}, and you want to treat a, b, c[0],
c[1] as an array.

The fact is that this is a low level language. You need to be able to do
stuff like this.

> C has a lot of warts, no question ... but its biggest problem is that
> the routine (ab)use of pointers in, so-called, "idiomatic" C in a real
> sense is working against the compiler - making it's job much harder.

So hard that I wouldn't even attempt it. Creating a more restrictive,
safer (or easier to check) language would be easier (IMO).

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

#2281 — Re: Bounds checking, Optimization techniques and undefined behavior

On 06/05/2019 14:07, Bart wrote:
> On 05/05/2019 22:38, George Neuner wrote:
>> On Sun, 5 May 2019 11:14:51 +0100, Bart <bc@freeuk.com> wrote:
>
>>> You intend p to refer to the 4-element slice A[3..6], but how does the
>>> language know that? How can it stop code from writing to p[5]?
>>
>> You declare 'p' as  int (*p)[4]  and then the compiler could check the
>> use.  Theoretically at least, I'm not sure it actually is done in many
>> situations.
>
> I declare pointers to arrays as T(*)[] when generating C code. But
> you're right in that no one else does that when writing C.
>

I'd declare a pointer to an array in that way too, as would anyone else
programming C - because that is what the type means.  But I would not
use it for a pointer /into/ an array, since that is a different thing.
And George had been talking about slices of an array, which is different
again.


If you have an array A of 10 ints ("int A[10];"), and you take a pointer
to, say, element 3 ("int * p = &A[3];"), then that pointer is /not/
compatible with a type "int (*)[4]" or any other pointer-to-array type.
 So using such types for "slices" into a C array is not valid - it would
be undefined behaviour.  (To be fair, I think it is likely that most
compilers will implement it in the way you would expect - but C
certainly does not say it should work.)

Remember that even though arrays used as lvalues in expressions decay to
pointers, arrays are independent types in C.  An array of 10 ints
contains ints, it does not contain sub-arrays of different sizes any
more than an "int" contains two "short int" items.


> Note that this is an open bound; usually the bound will be dynamic, and
> held in a separate variable, which the language does not know is the bound.
>

True.  C has no standard way to associate an array size with a pointer.
 In a new language, such an association is likely to be a good idea.

> C has something called VLAs, which is really a type where any bounds are
> defined as a runtime expression.

Yes, except that they are types, not "a type" - VLAs are types that are
not fixed until run-time, and the type of a given VLA may vary each time
you call the function or enter the block in which it is defined.

> If you had a loop which extracted
> different slices on each iteration, you would obliged to declare 'p'
> within the loop, so it has a slightly different type (with different
> bounds) each time around.
>

As noted above, using a pointer to an array as a slice of a bigger array
is not valid.  If you want "slice" types in C, you have to make them
with a struct (that is the only way of defining new types in C, along
with unions) and make your own access functions or macros.  It would be
possible, and can be done in a type-safe way, but it would undeniably be
ugly and awkward.

> But this is very restrictive (for example I don't like using local block
> scopes).

This is /you/ being restrictive.  You can't blame a language for your
own personal prejudices about features you don't want to use!

> It is also a rather heavyweight feature just to allow the
> possibility of bounds checking.
>
> (Also something I haven't implemented in my own C compiler; I just don't
> know how to approach it. And I don't like the feature.)
>
> Proper slicing (since we are not restricted to C or other existing
> languages) is simpler and better.
>

Agreed.  C does not have such a feature as part of the language.  (In
C++, you can make it - and it will be standardised in the up-coming
"ranges" library.  But in C it would be a mess.)

>>>    struct {int a,b,c,d;} S;
>>>
>>>    p = &S.a;
>>>
>>> You intend p to be used to access a,b,c,d as an int[4] array, but p's
>>> bounds will say it's only one element long.
>>
>> The larger problem is that C even permits that.
>
> I was half-expecting someone to say it was undefined behaviour. I
> suppose you will say the way to declare that pointer is as:
>
>    int (*p)[4] = (int(*)[4])&S.a;

That would be undefined behaviour.  (If I were being pedantic, I'd say
that /using/ the pointer p here would be undefined behaviour.  But I am
not going to do that.)

>
> The problem is that if you want to make C a safer, checked language,
> none of this stops people writing it the wrong way.

Correct.  C is not a strongly typed language.  It is rather cumbersome
to use it in a strongly type-checked manor (you need to keep wrapping
things in structs, which then become more awkward to use), and there are
always ways to get round any restrictions.

>
>> If you want the
>> struct elements also to be available as an array, you should have used
>> a union.
>
> Maybe the struct is defined elsewhere and is not your code to change. Or
> maybe the struct is {int a,b,c[20];}, and you want to treat a, b, c[0],
> c[1] as an array.
>
> The fact is that this is a low level language. You need to be able to do
> stuff like this.
>

Actually it is extremely rare that you need to do stuff like that.
Define your types the way you need to use them, and use them.  Very
occasionally, you need to do something like that with externally defined
types - a few lines of accessor code is simple enough.

>> C has a lot of warts, no question ... but its biggest problem is that
>> the routine (ab)use of pointers in, so-called, "idiomatic" C in a real
>> sense is working against the compiler - making it's job much harder.
>
> So hard that I wouldn't even attempt it. Creating a more restrictive,
> safer (or easier to check) language would be easier (IMO).

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

#2267 — Re: Bounds checking, Optimization techniques and undefined behavior

On 05/05/2019 11:14, Bart wrote:
>>> C is just a mess; it has arrays of sorts, but people generally use raw
>>> pointers without associated bounds. Maybe that's one reason why your C
>>> didn't have it. Or did it somehow manage it if enabled?
>>      This isn't really a problem with C, the language.  It's clear in
>> the reference manual right back to K&R C and in the various standards
>> that pointers always have associated bounds.
> But how do they get there? Take this:
>      int A[10], *p;
>      p = &A[3];
> You intend p to refer to the 4-element slice A[3..6], but how does the
> language know that? How can it stop code from writing to p[5]?

	You may intend that, but C doesn't.  C knows, after that code,
that "p" points within "A" and so can be bounds-checked that "p+i" is
valid for, and only for, A <= p+i <= A+10 [and for dereferencing only
if p+i < A+10.  So for bounds checking you need "fat pointers" and the
fat pointer that is "p" must contain the bounds information required to
check that;  IOW, A, p-A and 10, or near equivalent.

> Or you intend to index p[-2] to get at the preceding elements. Actually
> using negative indexing is quite common, but surely all array bounds in
> C are presumed to start from 0?

	Arrays may start there, but pointers are not arrays.

> Or this:
>    struct {int a,b,c,d;} S;
>    p = &S.a;
> You intend p to be used to access a,b,c,d as an int[4] array, but p's
> bounds will say it's only one element long.

	Again, you may intend that, but C doesn't.  AFAICT, nothing in
the C standard [any version] encourages the belief that your "S" is an
array.

> Or this:
>     int *p = malloc(sizeof(int)*1000);
>     int *q = p+400;
> You are allocating one pool of memory than sub-allocating that into
> smaller objects, here into a 20-element array headed by q. But how does
> the language know that?

	It doesn't.  You seem to be building much more into your C code
that C actually allows.  You have allocated a pool of 1000 integers, and
then made "q" point into that pool.  That's all.  If you now write [say]
"q--;", or "q[100] = 0;" then the bounds checking will reveal that "q"
is still within the pool, but "q[-500] = q[603] = 0;" [eg] is UB, which,
with a compiler that aborts on illegal accesses will cause your program
to fail.

> Or maybe p allocates memory for a 2D array, and q refers to one row of
> that; you can't detect accesses beyond that row.

	Of course you can, at least when they go beyond the bounds of
the allocated memory.

> I can see how the language can figure out the overall bounds of the
> block of memory a pointer refers to. But that can be a long way from
> knowing the precise bounds of any array or sub-array, when represented
> via a pointer to the first element.

	The bounds of the object that "q" [in your example] refers to
are all that is needed for an "array-bound check".

> So the problems are either that bounds transgressions can't be detected
> properly as 'fat pointers' only have broad info about allocations, or
> they will give false alarms when you want to do some pointer-offset
> manipulations that C normally allows.

	"C normally allows".  What you mean seems to be that compilers
that don't check such things [the usual case] don't detect the UB, and
so either do what you intended or ignore the bug.  Compilers are free to
ignore UB, but it's still incorrect code, and you would have no right to
complain if your program emitted the traditional nasal demons.

>> [...] It very likely means that arrays too need to
>> be implemented differently, with proper descriptors.
> Which C is not going to have without breaking just about every existing
> program. Besides, most array work in C doesn't actually use arrays, but
> explicit pointers.

	It would break programs with [perhaps undetected] bugs.  [I say
"perhaps" because you may have decided that a technical bug in fact works
with a particular program and compiler, and so that the bug does not need
to be corrected.  But you have, again, no right to complain if that view
comes back to bite you a few years down the line.]

[...]
> With language support, it need have no cost. For example, suppose that
> array A did carry its bounds with it (or are statically known), then in
> code like this:
>      for i in A do       # (iterate over bounds not values)
>          A[i] := 0
>      end
> the compiler knows it doesn't need to bounds-check each access. Or here:
>      forall x in A do    # (iterate over values)
>          print x
>      end

	Well, of course [though you would need guarantees that "i" and "x"
couldn't change inside the loop].  But that would be a much bigger change
to C than merely checking that pointers stay within bounds, already a part
[though commonly ignored] of the language.  Note too that the checking can
equally be zapped, under optimisation, for many of the common idioms for
looping around arrays.

[Moderator:]
> [Every pointer in C points either to a static object or to one that
> comes from a handful of routines like malloc() or mmap() so it
> shouldn't be too hard to do bounds checking within the allocated
> object, give or take unsafe typecasts which I don't think are common
> in application code.

	"Unsafe typecasts" are already UB!

>			But you are certainly correct that C isn't
> expressive enough to do slices or the like. -John]

	Um.  There should be no difficulty in defining library procedures
for the purpose [not strictly in C, of course, but lots of library stuff
has to be written for a specific compiler/OS/computer].  You would need
procedures that did clever things to fat pointers;  they could default to
doing unclever things when invoked on systems without fat pointers.  So
we could say that C doesn't currently have slices, but that's not *quite*
the same as saying it's not expressive enough.

--
Andy Walker,
Nottingham.
[In the struct { int a,b,c,d; } S example it is my understanding that &S and &S.a
have to be the same, the four ints have to be in the order declared, and they
all have the same alignment so it is valid abeit poor form to treat them as
an array. -John]

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

Page 2 of 5 — ← Prev page 1 [2] 3 4 5  Next page →

Back to top | Article view | comp.compilers

csiph-web