Hi,

I have compiled Leda on a Digital Alpha, but one of the test program
(sort_test) failed. After searching deep into source code and generated
assembler, I have been able to found that the problem is equivalent to bad
(?) generated code for the folowing snippet :

1  void bug (void * * l)
2  {
3      if ( * (long *) l > 2 )
4        *l = (void *) 1;
5
6      if ( * (long *) l < 2 )
7        *l = (void *) 2;
8  }

If you call this function with something like :
  void * val = (void *) 3;
  bug (&val);
the resulting value of val is 1 (compiled with standard optimisation).

When looking to generated assembler, I found that the value of *l is not
fetched again at line 6, so line 7 is not executed.

cxx men say that this program has undefined behaviour, because the store
(line 4) is done through a different type than the fetch (line 6).

In CD2, I have found the following paragraph wich seems relevant :
>  5.17  Assignment operators                                  [expr.ass]
>8 If the value being stored in an object is accessed from another object
>  that  overlaps  in  any  way the storage of the first object, then the
>  overlap shall be exact and the two objects shall have the  same  type,
>  otherwise the behavior is undefined.

My understanding is that cxx is right (and Leda wrong), but I would like
opinions from C++ lawyers.

Thanks,

--
Dominique Marcadet - Supelec - <http://www.supelec.fr>
Remove _nospam to get my right email
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Dominique.Marcadet_nospam@supelec.fr (Dominique Marcadet) writes:

>My understanding is that cxx is right (and Leda wrong), but I would like
>opinions [...]

My opinion is that your understanding is correct.

As well as the reason that you mentioned, there are several
additional reasons why the code fragment you presented may have
undefined behaviour.

>If you call this function with something like :
>  void * val = (void *) 3;
>  bug (&val);

The semantics of the cast `(void *) 3' are implementation-defined.

>1  void bug (void * * l)
>2  {
>3      if ( * (long *) l > 2 )

Here you access a value `val' whose type is `void *' via `* (long*)
&val', as if it were of type `long'.  The cast `long *' already has
undefined behaviour.  Dereferencing it is ever worse -- it can
definitely cause problems on systems where `long' and `void *' have
different sizes -- and expecting any meaningful result from the
comparison is certainly going a long way beyond what the standard
guarantees.

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

On 02 Oct 97 16:32:29 GMT, Dominique.Marcadet_nospam@supelec.fr
(Dominique Marcadet) wrote:
 >
 >I have compiled Leda on a Digital Alpha, but one of the test program
 >(sort_test) failed. After searching deep into source code and generated
 >assembler, I have been able to found that the problem is equivalent to bad
 >(?) generated code for the folowing snippet :
 >
 >1  void bug (void * * l)
 >2  {
 >3      if ( * (long *) l > 2 )
 >4        *l = (void *) 1;
 >5
 >6      if ( * (long *) l < 2 )
 >7        *l = (void *) 2;
 >8  }
 >
 >If you call this function with something like :
 >  void * val = (void *) 3;
 >  bug (&val);
 >the resulting value of val is 1 (compiled with standard optimisation).
 >
 >When looking to generated assembler, I found that the value of *l is not
 >fetched again at line 6, so line 7 is not executed.
 >
 >cxx men say that this program has undefined behaviour, because the store
 >(line 4) is done through a different type than the fetch (line 6).
 >
 >In CD2, I have found the following paragraph wich seems relevant :
 >>  5.17  Assignment operators                                  [expr.ass]
 >>8 If the value being stored in an object is accessed from another object
 >>  that  overlaps  in  any  way the storage of the first object, then the
 >>  overlap shall be exact and the two objects shall have the  same  type,
 >>  otherwise the behavior is undefined.
 >
 >My understanding is that cxx is right (and Leda wrong), but I would like
 >opinions from C++ lawyers.

I would say your analysis is correct. The code has undefined behaviour
for the reasons you give. But I do wonder about an optimizer that
seems to think that line 4 doesn't have any effect on line 6. What
happens if you change all instances of "void" to "long"?

---
Steve Clamage, stephen.clamage_nospam@eng.sun.com
( Note: remove "_nospam" when replying )
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Fergus Henderson wrote:
> The semantics of the cast `(void *) 3' are implementation-defined.
>
> >1  void bug (void * * l)
> >2  {
> >3      if ( * (long *) l > 2 )
>
> Here you access a value `val' whose type is `void *' via `* (long*)
> &val', as if it were of type `long'.  The cast `long *' already has
> undefined behaviour.  Dereferencing it is ever worse -- it can
> definitely cause problems on systems where `long' and `void *' have
> different sizes -- and expecting any meaningful result from the
> comparison is certainly going a long way beyond what the standard
> guarantees.

In addition, many systems have different alignment requirements on
different types of variables and will cause a segment violation or bus
fault when attempting to dereeference the misaligned cast object.

--
Gary Mussar <mussar@nortel.ca>   Phone: (613) 763-4937
Nortel                           FAX:   (613) 763-9406
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Steve Clamage wrote:
> I would say your analysis is correct. The code has undefined behaviour
> for the reasons you give. But I do wonder about an optimizer that
> seems to think that line 4 doesn't have any effect on line 6. What
> happens if you change all instances of "void" to "long"?

I had a similar problem with g++. The explanation I received was that
this is a memory aliasing problem and the optimizer was only tracking
changes to structs if these aliased items were part of this same union.

It appears to be a difficult problem to generically tell when a
write through a pointer invalidates data previously fetched into
a register. The volatile keyword can be used to tell the compiler
that it should always refetch values from memory because so
external event (eg. interrupt handler) or aliased memory access
may have changed the memory location. Some compilers also have
flags to indicate that data should always be refetched because
of aliasing concerns.

--
Gary Mussar <mussar@nortel.ca>   Phone: (613) 763-4937
Nortel                           FAX:   (613) 763-9406
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

In article (Dans l'article) <3436326c.29480517@engnews1.eng>,
stephen.clamage_nospam@eng.sun.com (Steve Clamage) wrote (icrivait) :

>I would say your analysis is correct. The code has undefined behaviour
>for the reasons you give. But I do wonder about an optimizer that
>seems to think that line 4 doesn't have any effect on line 6. What
>happens if you change all instances of "void" to "long"?

The bug is the same. But if the cast is done on the left side of the
assignment :
4   * (long *) l = 1;
the behaviour is right, which is coherent with the CD2 paragraph I have
mentioned.


In article (Dans l'article) <343532F5.91747EFB@nortel.ca>, "Gary Mussar"
<mussar@nortel.ca> wrote (icrivait) :

>I had a similar problem with g++. The explanation I received was that
>this is a memory aliasing problem and the optimizer was only tracking
>changes to structs if these aliased items were part of this same union.

In the answers I have received from DEC, they also mentionned that it was
an aliasing problem. Their C compiler has a -noansi_alias flag to disallow
this aggresive optimisation, and they are going to add it to their C++
compiler.

To explain a little more where does this come from, Leda has a generic
array of void * to implement any typed array whose elements can be stored
in a void *.
In their quick-sort algorithm, all comparisons are done after casting to
the right type, but the swap of elements are done on the raw void * bits.
If casts were also used in these swap, correct behaviour should be
obtained.

I have to first check this, and then ask Leda people to correct their library.

--
Dominique Marcadet - Supelec - <http://www.supelec.fr>
Remove nospam to get my right email
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]