Is this compiler specific or a C rule?

[aleksa]

Suppose I'm given a ptr to RECT and am modifying the RECT in a loop:

V1:

void ModifyRect (RECT* prect);
{
while (cond) {
if (newleft < prect->left) prect->left = newleft;
.
.
.
}
}


V2:

void ModifyRect (RECT* prect);
{
RECT rect;

while (cond) {
if (newleft < rect.left) rect.left = newleft;
.
.
.
}

*prect = rect;
}

(newleft is read sequentially from somewhere)

Compiler generated code for V1 accesses memory all the time,
while V2 holds everything in registers and only updates
the prect when finished.

I don't see a reason why both versions aren't coded the same.
(there is no VOLATILE anywhere...)

Just wondering, is this compiler specific or a C rule?

 

[Willem]

aleksa wrote:
) Suppose I'm given a ptr to RECT and am modifying the RECT in a loop:
)
) V1:
)
) void ModifyRect (RECT* prect);
) {
) while (cond) {
) if (newleft < prect->left) prect->left = newleft;
) .
) .
) .
) }
) }
)
)
) V2:
)
) void ModifyRect (RECT* prect);
) {
) RECT rect;
)
) while (cond) {
) if (newleft < rect.left) rect.left = newleft;
) .
) .
) .
) }
)
) *prect = rect;
) }
)
) (newleft is read sequentially from somewhere)
)
) Compiler generated code for V1 accesses memory all the time,
) while V2 holds everything in registers and only updates
) the prect when finished.
)
) I don't see a reason why both versions aren't coded the same.
) (there is no VOLATILE anywhere...)
)
) Just wondering, is this compiler specific or a C rule?

I think this is compiler specific, although C comes into it.

Does the other code in the while-loop call any other functions ?

If so, then it's a lot more difficult for the compiler to prove
that the pointed-to data isn't used or changed in the meantime
(which is kind-of a C rule) while in the V2 code, the compiler
knows that nothing outside the function can influence the struct.
(which is also kind-of a C rule).


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[aleksa]

Does the other code in the while-loop call any other functions ?

No.

 

[bart.c]

Suppose I'm given a ptr to RECT and am modifying the RECT in a loop:

V1:

void ModifyRect (RECT* prect);
{
while (cond) {
if (newleft < prect->left) prect->left = newleft;

V2:

void ModifyRect (RECT* prect);
{
RECT rect;

while (cond) {
if (newleft < rect.left) rect.left = newleft;

*prect = rect;
}

(newleft is read sequentially from somewhere)

Compiler generated code for V1 accesses memory all the time,
while V2 holds everything in registers and only updates
the prect when finished.

I don't see a reason why both versions aren't coded the same.
(there is no VOLATILE anywhere...)

Just wondering, is this compiler specific or a C rule?

V1 is more difficult to optimise (for a start, you have a pointer *and* rect
to deal with, instead of just rect). And while you say no other functions
are called.. is 'newleft' updated during the loop?

What about a V3 where you pass and return the rect by value?

 

[Eric Sosman]

Suppose I'm given a ptr to RECT and am modifying the RECT in a loop:

V1:

void ModifyRect (RECT* prect);

Assuming RECT is suitably declared, this is a valid declaration
for a function. It is not, however, a valid beginning for a function
definition. Two thoughts: Lose the semicolon, and make a habit of
posting real code rather than messed-up paraphrases.

{
while (cond) {
if (newleft< prect->left) prect->left = newleft;
.
.
.
}
}


V2:

void ModifyRect (RECT* prect);

Well, at least you're consistent.

{
RECT rect;

while (cond) {
if (newleft< rect.left) rect.left = newleft;
.
.
.
}

*prect = rect;
}

(newleft is read sequentially from somewhere)

Compiler generated code for V1 accesses memory all the time,
while V2 holds everything in registers and only updates
the prect when finished.

I don't see a reason why both versions aren't coded the same.
(there is no VOLATILE anywhere...)

Just wondering, is this compiler specific or a C rule?

Most likely, the difference is that in V2 the compiler knows
that `rect' is distinct from all other variables in the program.
In V1, `prect' might be pointing pretty much anywhere, including
at something that overlaps `newleft' or some other variable. The
"C rule" would be that if you store a new value in something via
a pointer and then access that something by name, the access by
name and the access by pointer must agree on what's there.

You're on a game show, with three other people hidden behind
three doors. You know that Alice has ten dollars, Betty has twelve,
and Carol has eight, but you don't know who's behind which door.
The game show host pushes a dollar bill through the slot of Door
Number Two (access via pointer). How much money does Carol have?
To find out, you must ask her (access via name).

 

[William Hughes]

Suppose I'm given a ptr to RECT and am modifying the RECT in a loop:

V1:

void ModifyRect (RECT* prect);
{
    while (cond) {
        if (newleft < prect->left) prect->left = newleft;
        .
        .
        .
    }

}

V2:

void ModifyRect (RECT* prect);
{
    RECT rect;

    while (cond) {
        if (newleft < rect.left) rect.left = newleft;
        .
        .
        .
    }

    *prect = rect;

}

(newleft is read sequentially from somewhere)

Compiler generated code for V1 accesses memory all the time,
while V2 holds everything in registers and only updates
the prect when finished.

I don't see a reason why both versions aren't coded the same.
(there is no VOLATILE anywhere...)

Well, for one thing, the two functions do something very
different. In V2 you never actually initialize rect
and you ignore the initial values of prect!
I think you left out a

rect = *prect;

Just wondering, is this compiler specific or a C rule?

This is compiler specific. That said it is easier
for the compiler to put a local into registers, than to
put stuff pointed to by a parameter into registers.

- William Hughes

 

[aleksa]

Well, at least you're consistent.

I got the will-power from copy & paste

Most likely, the difference is that in V2 the compiler knows
that `rect' is distinct from all other variables in the program.
In V1, `prect' might be pointing pretty much anywhere, including
at something that overlaps `newleft' or some other variable.

Yes, I can understand the compilers POW here.

 

[aleksa]

My first post was supposed to show the problem,
without going too much into details.

For the sake of completeness, here are the sources:

void V1 (POINT* src, RECT* prect)
{
POINT pt;

prect->left = INT_MAX;
prect->bottom = INT_MAX;
prect->right = INT_MIN;
prect->top = INT_MIN;

while (1) {
pt.x = src->x;
pt.y = src->y;
src++;

if (pt.x == 0) break;

if (pt.x < prect->left) prect->left = pt.x;
if (pt.x > prect->right) prect->right = pt.x;

if (pt.y < prect->bottom) prect->bottom = pt.y;
if (pt.y > prect->top) prect->top = pt.y;
}
}

void V2 (POINT* src, RECT* prect)
{
POINT pt;
RECT rect;

rect.left = INT_MAX;
rect.bottom = INT_MAX;
rect.right = INT_MIN;
rect.top = INT_MIN;

while (1) {
pt.x = src->x;
pt.y = src->y;
src++;

if (pt.x == 0) break;

if (pt.x < rect.left) rect.left = pt.x;
if (pt.x > rect.right) rect.right = pt.x;

if (pt.y < rect.bottom) rect.bottom = pt.y;
if (pt.y > rect.top) rect.top = pt.y;
}

*prect = rect;
}

 

[Francis Moreau]

In V1, `prect' might be pointing pretty much anywhere, including
at something that overlaps `newleft' or some other variable.

Do you mean that 'prect' whose type is pointer on 'RECT' can overlap
'newleft' whose type is obviously different from 'RECT' one ?

Does the C rules allow this ?

 

[Nobody]

My first post was supposed to show the problem,
without going too much into details.

For the sake of completeness, here are the sources:

void V1 (POINT* src, RECT* prect)

The compiler must assume that the data referenced via src can overlap
the data referenced via prect. So modifying e.g. prect->left could modify
elements of src which will be used later.

If you copy *prect to a local variable and modify that, the compiler
is free to assume that the data referenced via src doesn't overlap the
local variable (in practice, it's possible to cause this to happen, but
only by using mechanisms which the standard specifies as invoking
undefined behaviour).

 

[Thad Smith]

My first post was supposed to show the problem,
without going too much into details.

For the sake of completeness, here are the sources:

void V1 (POINT* src, RECT* prect)
{
POINT pt;

prect->left = INT_MAX;
prect->bottom = INT_MAX;
prect->right = INT_MIN;
prect->top = INT_MIN;

while (1) {
pt.x = src->x;
pt.y = src->y;
src++;

if (pt.x == 0) break;

if (pt.x < prect->left) prect->left = pt.x;
if (pt.x > prect->right) prect->right = pt.x;

if (pt.y < prect->bottom) prect->bottom = pt.y;
if (pt.y > prect->top) prect->top = pt.y;
}
}

Assume

union {
POINT p;
RECT r;
} u;
....
V1 (&u.p, &u.r);

is in a different module.

With suitable definitions of POINT and RECT, setting prect->left can affect
access to src->x on the next iteration of the loop. The compiler therefore must
store each assignment to members of *prect.

 

[Tim Rentsch]

The compiler must assume that the data referenced via src can overlap
the data referenced via prect. So modifying e.g. prect->left could modify
elements of src which will be used later.

Unless a RECT has a POINT inside it, implementations are
not obliged to make such an assumption.

(There are more complicated situations, involving unions,
where implementations must allow for such possible overlap,
but those don't hold in the example since no union type
definitions are visible at the point V1 is defined.)

 

[Eric Sosman]

]

Tim, is there anyone named "van Winkle" in your family tree?

 

[Tim Rentsch]

Assume

union {
POINT p;
RECT r;
} u;
...
V1 (&u.p, &u.r);

is in a different module.

With suitable definitions of POINT and RECT, setting prect->left can
affect access to src->x on the next iteration of the loop. The
compiler therefore must store each assignment to members of *prect.

Not if the union definition isn't visible at the definition
of V1. Just because such a union type might be (or is)
defined in another translation unit does not affect what
happens at the point the function V1 is compiled.
See 6.5.2.3p5, more specifically:

One special guarantee is made in order to simplify the
use of unions: if a union contains several structures
that share a common initial sequence (see below), and if
the union object currently contains one of these
structures, it is permitted to inspect the common
initial part of any of them anywhere that a declaration
of the complete type of the union is visible.

Notice the final qualifying clause: "anywhere that a declaration
of the complete type of the union is visible." If the union type
definition isn't visible, the provision doesn't come into play.

 

[Thad Smith]

Not if the union definition isn't visible at the definition
of V1. Just because such a union type might be (or is)
defined in another translation unit does not affect what
happens at the point the function V1 is compiled.

I think you misunderstand. If the compiler, before generating code for V1, can
see all instances of calls to V1 and deduce, from the parameters, and sources of
those parameters, that there is no overlap of pointed-to objects, then it can
optimize accordingly. Without that visibility it is required to assume an
overlap may occur such that a storage through one pointer may affect the value
accessible through another. The restrict qualifier allows you to promise to the
compiler that no such multiple pointer reference paths exist.

I think that the compiler could deduce that, say, a storage of a pointer won't
affect the value a double, since the result of setting a object area with
pointer and reading as a double is undefined.

See 6.5.2.3p5, more specifically:

One special guarantee is made in order to simplify the
use of unions: if a union contains several structures
that share a common initial sequence (see below), and if
the union object currently contains one of these
structures, it is permitted to inspect the common
initial part of any of them anywhere that a declaration
of the complete type of the union is visible.

Notice the final qualifying clause: "anywhere that a declaration
of the complete type of the union is visible." If the union type
definition isn't visible, the provision doesn't come into play.

What you say is true, but it provides guarantees of object coincidence for
common initial sequences of structs within a union. Union of common initial
sequences is not the issue and no such guarantee is being sought by the example
code. The paragraph has no impact on the issue at hand.

 

[Tim Rentsch]

]

Tim, is there anyone named "van Winkle" in your family tree?

Alas, I don't always have the luxury of reading newsgroups (especially
comp.lang.c) regularly or responding in a timely fashion.

 

[Tim Rentsch]

I think you misunderstand. If the compiler, before generating code
for V1, can see all instances of calls to V1 and deduce, from the
parameters, and sources of those parameters, that there is no overlap
of pointed-to objects, then it can optimize accordingly. Without that
visibility it is required to assume an overlap may occur such that a
storage through one pointer may affect the value accessible through
another.

I believe you are mistaken. The rules for effective type
mean the compiler may ignore possible overlap, even if it
can't see all the calls to V1.

The restrict qualifier allows you to promise to the compiler
that no such multiple pointer reference paths exist.

I think that the compiler could deduce that, say, a storage of a
pointer won't affect the value a double, since the result of setting a
object area with pointer and reading as a double is undefined.

What you may be missing is that the pointers in question are
pointers to structs, and the effective type access rules
apply to the struct objects as well as the individual members
in them.

What you say is true, but it provides guarantees of object coincidence
for common initial sequences of structs within a union. Union of
common initial sequences is not the issue and no such guarantee is
being sought by the example code. The paragraph has no impact on the
issue at hand.

It's relevant because it's the only situation for accessing
structs that the compiler /does/ have to consider the possibility
of overlap. In all other cases (assuming one struct is not
a subobject of the other), pointers to distinct struct types
may be assumed not to overlap. The paragraph quoted above
is the only exception; since it doesn't apply, the compiler
is free to treat accesses to members in the different structs
as independent.