Is this compiler specific or a C rule?

Discussion in 'C Programming' started by aleksa, May 5, 2010.

  1. aleksa

    aleksa Guest

    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?
     
    aleksa, May 5, 2010
    #1
    1. Advertising

  2. aleksa

    Willem Guest

    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
     
    Willem, May 5, 2010
    #2
    1. Advertising

  3. aleksa

    aleksa Guest

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

    No.
     
    aleksa, May 5, 2010
    #3
  4. aleksa

    bart.c Guest

    "aleksa" <> wrote in message
    news:...
    > 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?

    --
    Bartc
     
    bart.c, May 5, 2010
    #4
  5. aleksa

    Eric Sosman Guest

    On 5/5/2010 6:05 AM, aleksa wrote:
    > 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).

    --
    Eric Sosman
    lid
     
    Eric Sosman, May 5, 2010
    #5
  6. On May 5, 7:05 am, 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...)
    >



    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
     
    William Hughes, May 5, 2010
    #6
  7. aleksa

    aleksa Guest

    > 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, May 5, 2010
    #7
  8. aleksa

    aleksa Guest

    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;
    }
     
    aleksa, May 5, 2010
    #8
  9. On 5 mai, 15:16, Eric Sosman <> wrote:
    [snip]
    > 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 ?
     
    Francis Moreau, May 5, 2010
    #9
  10. aleksa

    Nobody Guest

    On Wed, 05 May 2010 16:23:19 +0200, aleksa wrote:

    > 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).
     
    Nobody, May 6, 2010
    #10
  11. aleksa

    Thad Smith Guest

    aleksa wrote:
    > 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.

    --
    Thad
     
    Thad Smith, May 7, 2010
    #11
  12. aleksa

    Tim Rentsch Guest

    Nobody <> writes:

    > On Wed, 05 May 2010 16:23:19 +0200, aleksa wrote:
    >
    >> 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.


    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.)
     
    Tim Rentsch, Jun 17, 2010
    #12
  13. aleksa

    Eric Sosman Guest

    [OT] Re: Is this compiler specific or a C rule?

    On 6/17/2010 1:11 PM, Tim Rentsch wrote:
    > Nobody<> writes:
    > [... on 05 May 2010 ...]
    >> On Wed, 05 May 2010 16:23:19 +0200, aleksa wrote:
    >> [...]


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

    --
    Eric Sosman
    lid
     
    Eric Sosman, Jun 17, 2010
    #13
  14. aleksa

    Tim Rentsch Guest

    Thad Smith <> writes:

    > aleksa wrote:
    >> 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.


    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.
     
    Tim Rentsch, Jun 17, 2010
    #14
  15. aleksa

    Thad Smith Guest

    Tim Rentsch wrote:
    > Thad Smith <> writes:
    >
    >> aleksa wrote:
    >>> 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.

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

    --
    Thad
     
    Thad Smith, Jun 18, 2010
    #15
  16. aleksa

    Tim Rentsch Guest

    Re: [OT] Re: Is this compiler specific or a C rule?

    Eric Sosman <> writes:

    > On 6/17/2010 1:11 PM, Tim Rentsch wrote:
    >> Nobody<> writes:
    >> [... on 05 May 2010 ...]
    >>> On Wed, 05 May 2010 16:23:19 +0200, aleksa wrote:
    >>> [...]

    >
    > 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, Jun 20, 2010
    #16
  17. aleksa

    Tim Rentsch Guest

    Thad Smith <> writes:

    > Tim Rentsch wrote:
    >> Thad Smith <> writes:
    >>
    >>> aleksa wrote:
    >>>> 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.

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


    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.


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


    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.
     
    Tim Rentsch, Jun 20, 2010
    #17
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Roxanne
    Replies:
    0
    Views:
    1,259
    Roxanne
    Jul 4, 2003
  2. =?Utf-8?B?SmF2?=

    Is ViwState Page-Specific or UserControl-Specific

    =?Utf-8?B?SmF2?=, Aug 16, 2006, in forum: ASP .Net
    Replies:
    2
    Views:
    575
    =?Utf-8?B?SmF2?=
    Aug 16, 2006
  3. Replies:
    0
    Views:
    1,416
  4. mazdotnet
    Replies:
    2
    Views:
    425
    Alexey Smirnov
    Oct 2, 2009
  5. William FERRERES
    Replies:
    7
    Views:
    240
    William FERRERES
    Jul 9, 2007
Loading...

Share This Page