5 ms·

Wrong optimization with aliasing

58 points by luu 11y ago

nmc 11y ago
TL;DR: the bug is due to GCC's optimization feature called full redundancy elimination (FRE). It treats "int a=* pi; * pi=a" as a redundant store and removes it, as explained in the 5th comment: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69776#c5 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69776#c5
amelius 11y ago
I wonder why this wasn't caught by the extensive set of regression tests of GCC.
- anon4 11y ago
  Because they don't think it's a regression, it's working as intended.
  - tetromino_ 11y ago
    No, apparently a gcc developer agreed that there was a regression and it wasn't working as intended. They've just fixed a reduced test case [1], although according to the original reporter, there remains an additional problem to be fixed. [1] https://gcc.gnu.org/viewcvs/gcc?view=revision&revision=233418 https://gcc.gnu.org/viewcvs/gcc?view=revision&revision=23341...
- kazinator 11y ago
  Part of the answer is observer bias. If the possibility of this flaw were covered by a regression test, then the flaw wouldn't exist. As long as bugs exist and are found in the field, we can continue to ask the question why these bugs were not covered by testing. The other part is that bugs are found because "extensive" isn't anywhere near "exhaustive". For this given bug, there exists some requirements in the ISO C standard. We could ask, why don't we have coverage of all ISO C requirements in the test suite. But even if we had that coverage of all requirements, it won't catch all bugs like this. There are ways of validating these requirements such that the bug won't show up. The requirements end up violated here through an obscure cascade of unintended consequences, not through a lack of implementation. The repro test case is quite contrived. It treats a piece of memory with no declared type as int. It loads the value from that memory into a temporary variable, then temporarily re-purposes them emory as type double, and then re-purposes it again as int---by storing the original, stashed temp value back into it. This happens all in the same scope. Because the re-purposing of memory is valid, the store back of the temporary variable isn't in fact redundant in this case, as the optimizer is programmed to think. Catching the problem requires the specific combination of testing the redundancy elimination together with code which re-purposes memory twice in the same scope. Suppose that you have 12 different optimizations which take advantage of strict aliasing, and 11 of them respect the concept of "effective type" for an object of no declared type. To catch the problem, you need to write the code which exercises requirements related to "effective type", and which elicits that one buggy optimization out of the compiler. Such combinations of interacting features this explode the testing space. It's not enough to test them in isolation. That optimization, tested in isolation, looks fine. "Effective type" is honored just fine---in absence of that optimization.
sharpneli 11y ago
I is not wrong optimization. The guy is explicitly breaking the C specification by doing that. The correct way of accessing a variable like that is trough an union. Here is an example http://pastebin.com/8V3whcL3 http://pastebin.com/8V3whcL3 Alternatively one can make both of them as volatile. That will basically force the compiler do all the loads and stores. I really hate it when people write code that breaks the spec and then complains to the compiler maker. And now they actually changed the compiler to work with the code that is simply wrong. Just as what happened with glibc memcpy (works like memmove due to people not knowing what they are doing and then crying for the libraries to change their behaviour to match their own incompetence).
- maximilianburke 11y ago
  There is a lot of code written and released that doesn't follow the standard to the letter. New compilers with new optimizations that require strict language adherence otherwise they generate broken programs cause issues for the developers but, most importantly, the users. The memcpy/memmove debacle could have been avoided entirely if memcpy performed a simple check about what was being copied where and changed the direction of the copy based on that. Simple, cheap, and an entire class of bugs can be avoided. People should still be aware of the behavior of their development system but the system shouldn't punish when a slightly wrong choice is made. Optimizations are great but software that continues to function is even better.
  - sharpneli 11y ago
    It's a strain on portability. Instead of just having a C or C++ program you actually have MSVC++ program (this is actually really common) or GCC program or clang program. Sure one can argue that the C standard is too lax. But these kind of errors come simply from the fact that people learn C by trial and error, which doesn't work with that language. Personally as long as the compilers still allow one to enable the optimizations it's not that bad in the end. Portability issues for badly written programs remain however.
- nkurz 11y ago
  The guy is explicitly breaking the C specification by doing that. You assert this, but clearly there are people in the bug thread who believe otherwise. In the thread, the submitter references a portion of the C11 spec that he feels defends his usage: C11, 6.5p6: If a value is stored into an object having no declared type through an lvalue having a type that is not a character type, then the type of the lvalue becomes the effective type of the object for that access and for subsequent accesses that do not modify the stored value. I'm not familiar enough with the spec to know the context, nor would I defend this code as good practice, but superficially this seems to be evidence that this is a bug. Is there another specification that can you point to that this "explicitly" breaks?
greglindahl 11y ago
-fstrict-aliasing is on by default in gcc at -O2 and above. I'm surprised that the bug discussion doesn't mention that. The PathScale compiler had a fair number of customers who complained about "bugs" that went away with -fnostrict-aliasing. We told them to use -fnostrict-aliasing.
- Too 11y ago
  I think it's quite obvious strict aliasing is implied in this case. The bug is than even with strict aliasing he should get the result he wants, because the last time he wrote to the pointer before reading it as an int he wrote it as an int and hence it should keep the int-value 1. Having that said, balancing aliasing like this is just asking for trouble, don't try this at home. EDIT: The more i look at it the more i think he is wrong. Since pi and pd shouldn't be able to alias, the last assignment to both of them is allowed to reorder. This is just UB.

58 points by luu 11y ago

nmc 11y ago

TL;DR: the bug is due to GCC's optimization feature called full redundancy elimination (FRE). It treats "int a=* pi; * pi=a" as a redundant store and removes it, as explained in the 5th comment: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69776#c5 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69776#c5

amelius 11y ago

I wonder why this wasn't caught by the extensive set of regression tests of GCC.

anon4 11y ago
Because they don't think it's a regression, it's working as intended.
- tetromino_ 11y ago
  No, apparently a gcc developer agreed that there was a regression and it wasn't working as intended. They've just fixed a reduced test case [1], although according to the original reporter, there remains an additional problem to be fixed. [1] https://gcc.gnu.org/viewcvs/gcc?view=revision&revision=233418 https://gcc.gnu.org/viewcvs/gcc?view=revision&revision=23341...
kazinator 11y ago
Part of the answer is observer bias. If the possibility of this flaw were covered by a regression test, then the flaw wouldn't exist. As long as bugs exist and are found in the field, we can continue to ask the question why these bugs were not covered by testing. The other part is that bugs are found because "extensive" isn't anywhere near "exhaustive". For this given bug, there exists some requirements in the ISO C standard. We could ask, why don't we have coverage of all ISO C requirements in the test suite. But even if we had that coverage of all requirements, it won't catch all bugs like this. There are ways of validating these requirements such that the bug won't show up. The requirements end up violated here through an obscure cascade of unintended consequences, not through a lack of implementation. The repro test case is quite contrived. It treats a piece of memory with no declared type as int. It loads the value from that memory into a temporary variable, then temporarily re-purposes them emory as type double, and then re-purposes it again as int---by storing the original, stashed temp value back into it. This happens all in the same scope. Because the re-purposing of memory is valid, the store back of the temporary variable isn't in fact redundant in this case, as the optimizer is programmed to think. Catching the problem requires the specific combination of testing the redundancy elimination together with code which re-purposes memory twice in the same scope. Suppose that you have 12 different optimizations which take advantage of strict aliasing, and 11 of them respect the concept of "effective type" for an object of no declared type. To catch the problem, you need to write the code which exercises requirements related to "effective type", and which elicits that one buggy optimization out of the compiler. Such combinations of interacting features this explode the testing space. It's not enough to test them in isolation. That optimization, tested in isolation, looks fine. "Effective type" is honored just fine---in absence of that optimization.

sharpneli 11y ago

I is not wrong optimization. The guy is explicitly breaking the C specification by doing that. The correct way of accessing a variable like that is trough an union. Here is an example http://pastebin.com/8V3whcL3 http://pastebin.com/8V3whcL3 Alternatively one can make both of them as volatile. That will basically force the compiler do all the loads and stores. I really hate it when people write code that breaks the spec and then complains to the compiler maker. And now they actually changed the compiler to work with the code that is simply wrong. Just as what happened with glibc memcpy (works like memmove due to people not knowing what they are doing and then crying for the libraries to change their behaviour to match their own incompetence).

maximilianburke 11y ago
There is a lot of code written and released that doesn't follow the standard to the letter. New compilers with new optimizations that require strict language adherence otherwise they generate broken programs cause issues for the developers but, most importantly, the users. The memcpy/memmove debacle could have been avoided entirely if memcpy performed a simple check about what was being copied where and changed the direction of the copy based on that. Simple, cheap, and an entire class of bugs can be avoided. People should still be aware of the behavior of their development system but the system shouldn't punish when a slightly wrong choice is made. Optimizations are great but software that continues to function is even better.
- sharpneli 11y ago
  It's a strain on portability. Instead of just having a C or C++ program you actually have MSVC++ program (this is actually really common) or GCC program or clang program. Sure one can argue that the C standard is too lax. But these kind of errors come simply from the fact that people learn C by trial and error, which doesn't work with that language. Personally as long as the compilers still allow one to enable the optimizations it's not that bad in the end. Portability issues for badly written programs remain however.
nkurz 11y ago
The guy is explicitly breaking the C specification by doing that. You assert this, but clearly there are people in the bug thread who believe otherwise. In the thread, the submitter references a portion of the C11 spec that he feels defends his usage: C11, 6.5p6: If a value is stored into an object having no declared type through an lvalue having a type that is not a character type, then the type of the lvalue becomes the effective type of the object for that access and for subsequent accesses that do not modify the stored value. I'm not familiar enough with the spec to know the context, nor would I defend this code as good practice, but superficially this seems to be evidence that this is a bug. Is there another specification that can you point to that this "explicitly" breaks?

greglindahl 11y ago

-fstrict-aliasing is on by default in gcc at -O2 and above. I'm surprised that the bug discussion doesn't mention that. The PathScale compiler had a fair number of customers who complained about "bugs" that went away with -fnostrict-aliasing. We told them to use -fnostrict-aliasing.

Too 11y ago
I think it's quite obvious strict aliasing is implied in this case. The bug is than even with strict aliasing he should get the result he wants, because the last time he wrote to the pointer before reading it as an int he wrote it as an int and hence it should keep the int-value 1. Having that said, balancing aliasing like this is just asking for trouble, don't try this at home. EDIT: The more i look at it the more i think he is wrong. Since pi and pd shouldn't be able to alias, the last assignment to both of them is allowed to reorder. This is just UB.