Potential Violation of 6.5p2
Shao Miller
Some discussion in another thread prompts me to ask: Does the included
source code yield undefined behaviour? I believe it does, since it's a
violation of a "shall" in 6.5p2 (of 'n1256.pdf'), where each element
object of 'ia' is read for a purpose unrelated to determining the new
value that will be stored therein. :(
Code also available at: http://codepad.org/s5U6MU9C
Thank you,
- Shao Miller
#include <stdio.h>
/**
* There's no causal possibility for misbehaviour,
* but is it undefined behaviour, nonetheless?
*/
int main(void) {
/* Non-volatile */
int ia[] = {0, 1, 2, 3, 4, 5};
int cur = 6;
do {
cur--;
/**
* The RHS of the assignment determines the new
* value, but the object is read on the LHS.
*/
ia[ia[cur]] = cur + 1;
printf("{ %d, %d, %d, %d, %d, %d }\n",
ia[0], ia[1], ia[2], ia[3], ia[4], ia[5]);
} while (cur);
return cur;
}
Sample output:
{ 0, 1, 2, 3, 4, 6 }
{ 0, 1, 2, 3, 5, 6 }
{ 0, 1, 2, 4, 5, 6 }
{ 0, 1, 3, 4, 5, 6 }
{ 0, 2, 3, 4, 5, 6 }
{ 1, 2, 3, 4, 5, 6 }
Ersek, Laszlo
> /**
> * The RHS of the assignment determines the new
> * value, but the object is read on the LHS.
> */
> ia[ia[cur]] = cur + 1;
*(ia + *(ia + cur)) = cur + 1;
All "ia" and "cur" instances are evaluated in an unspecified order. (All
"ia"'s decay to pointers to the first element.)
The outer dereference (indirection operator) on the left side cannot be
evaluated before the outer addition is evaluated on the left side. (The
operand of the indirection operator is simply not available until then.)
The outer addition on the left side cannot be evaluated before the inner
dereference (indirection operator) is evaluated -- the right operand of
the outer addition is simply not available until then.
And so on. Even if the same "slot" of "ia" is accessed twice (once read,
once written to), the data dependencies dictated by how the operators are
bound together serialize those accesses correctly.
lacos
--
All content in this message, posted from <la...@caesar.elte.hu>, is my
personal opinion, representing noone else than myself.
Shao Miller
> On Mon, 9 Aug 2010, Shao Miller wrote:
> > /**
> > * The RHS of the assignment determines the new
> > * value, but the object is read on the LHS.
> > */
> > ia[ia[cur]] = cur + 1;
>
> *(ia + *(ia + cur)) = cur + 1;
>
> All "ia" and "cur" instances are evaluated in an unspecified order. (All
> "ia"'s decay to pointers to the first element.)
>
> The outer dereference (indirection operator) on the left side cannot be
> evaluated before the outer addition is evaluated on the left side. (The
> operand of the indirection operator is simply not available until then.)
>
> The outer addition on the left side cannot be evaluated before the inner
> dereference (indirection operator) is evaluated -- the right operand of
> the outer addition is simply not available until then.
>
> And so on. Even if the same "slot" of "ia" is accessed twice (once read,
> once written to), the data dependencies dictated by how the operators are
> bound together serialize those accesses correctly.
lacos. :)
Unfortunately, despite the flow of causality you point out, an object
is read for purposes unrelated to a computation of the value which
will be stored in it, which I perceive to be a violation of a "shall"
in 6.5p2. What I'm wondering is if anyone sees a way out of this
violation, or doesn't see it at all.
Ben Bacarisse
> Some discussion in another thread prompts me to ask: Does the included
> source code yield undefined behaviour? I believe it does, since it's
> a violation of a "shall" in 6.5p2 (of 'n1256.pdf'), where each element
> object of 'ia' is read for a purpose unrelated to determining the new
> value that will be stored therein. :(
Yes. Agreement, however, is not the main purpose this post.
<snip>
> #include <stdio.h>
>
> /**
> * There's no causal possibility for misbehaviour,
> * but is it undefined behaviour, nonetheless?
> */
>
> int main(void) {
> /* Non-volatile */
> int ia[] = {0, 1, 2, 3, 4, 5};
> int cur = 6;
>
> do {
> cur--;
> /**
> * The RHS of the assignment determines the new
> * value, but the object is read on the LHS.
> */
> ia[ia[cur]] = cur + 1;
I think you could have come up with a simpler example. 'cur' is
irrelevant to your point and there is no need for a loop:
int ia[] = {0};
ia[ia[0]] = 1;
is undefined for the same reason and there is less chance that people
will be distracted by the extras.
> printf("{ %d, %d, %d, %d, %d, %d }\n",
> ia[0], ia[1], ia[2], ia[3], ia[4], ia[5]);
> } while (cur);
> return cur;
> }
<snip>
--
Ben.
Ersek, Laszlo
> int ia[] = {0};
> ia[ia[0]] = 1;
>
> is undefined for the same reason and there is less chance that people
> will be distracted by the extras.
Well, I stand corrected again.
Taking your word for it, I acknowledge that the code above violates the
words of the standard. I doubt it violates its intent.
Evaluating the inner ia[0] is indeed not necessary for computing the next
value of ia[0]. It is however necessary to *select* ia[0] for assignment.
A store takes two things, a "what" and a "where to". The current wording
of the standard appears to consider the "what", but not the "where to".
... I suspect somebody will be able to disprove this, so please, do.
Thanks,
Shao Miller
int i = 0;
int *ip = &i;
*(ip + i) = 0;
was far too confusing, because it was perhaps too abstract and useless
on its own. This code does something visible, at least.
Thanks for confirming though, Ben. :)
Shao Miller
> On Mon, 9 Aug 2010, Ben Bacarisse wrote:
> > int ia[] = {0};
> > ia[ia[0]] = 1;
>
> > is undefined for the same reason and there is less chance that people
> > will be distracted by the extras.
>
> Well, I stand corrected again.
>
> Taking your word for it, I acknowledge that the code above violates the
> words of the standard. I doubt it violates its intent.
>
> Evaluating the inner ia[0] is indeed not necessary for computing the next
> value of ia[0]. It is however necessary to *select* ia[0] for assignment.
> A store takes two things, a "what" and a "where to". The current wording
> of the standard appears to consider the "what", but not the "where to".
>
> ... I suspect somebody will be able to disprove this, so please, do.
lawrenc...@siemens.com
> On Aug 9, 7:40?am, "Ersek, Laszlo" <la...@caesar.elte.hu> wrote:
> >
> > And so on. Even if the same "slot" of "ia" is accessed twice (once read,
> > once written to), the data dependencies dictated by how the operators are
> > bound together serialize those accesses correctly.
>
> is read for purposes unrelated to a computation of the value which
> will be stored in it, which I perceive to be a violation of a "shall"
> in 6.5p2. What I'm wondering is if anyone sees a way out of this
> violation, or doesn't see it at all.
The way out is C1X, the latest draft of which can be found at the
committee's web site <http://wg14.open-std.org/jtc1/sc22/wg14/> as
document N1494. The statement in 6.5p2 did not fully reflect the
committee's intent, but there was never any agreement on a formal model
that did correctly reflect the intent before the new memory and
sequencing model reflected in the draft.
--
Larry Jones
Honey, are we out of aspirin again? -- Calvin's Dad
Ben Bacarisse
> On Mon, 9 Aug 2010, Ben Bacarisse wrote:
>
>> int ia[] = {0};
>> ia[ia[0]] = 1;
>>
>> is undefined for the same reason and there is less chance that
>> people will be distracted by the extras.
>
> Well, I stand corrected again.
>
> Taking your word for it, I acknowledge that the code above violates
> the words of the standard. I doubt it violates its intent.
Hmm... on that point I will be silent. I simply don't know (but see
below for a way forward).
> Evaluating the inner ia[0] is indeed not necessary for computing the
> next value of ia[0]. It is however necessary to *select* ia[0] for
> assignment. A store takes two things, a "what" and a "where to". The
> current wording of the standard appears to consider the "what", but
> not the "where to".
Yes, that's the way I see it.
Most of the "is a[i++] = a[--i] + i++; defined" questions are just there
to test the meaning of the words. Using an element of the array as an
index to the array, however, occurs in real-world code to do with
permutations and cryptography and care has to be taken to ensure that
the result is defined by the language. I've come across this in actual
code in the wild. I have the vaguest memory (but I can't verify this
with a citation) of unexpected result from an compiler's optimiser that
used the undefined nature of this sort of code to its advantage (and to
the determent of the code's author!)
> ... I suspect somebody will be able to disprove this, so please, do.
I wonder if the new wording in the C draft has any effect on this
expression. The intent of the wording is just to clarify the intent of
the old wording, so any differences would be revealing.
--
Ben.
Shao Miller
is defined as part of value computation. The way out is C1X,
indeed. :)
Tim Rentsch
Statements like
ia[0] = 0;
ia[ia[0]] = 1;
are certainly well-defined under the wording in C1X.