Optimizing away a “while(1);” in C++0x

by

To me, the relevant justification is:

This is intended to allow compiler transfor- mations, such as removal of empty loops, even when termination cannot be proven.

Presumably, this is because proving termination mechanically is difficult, and the inability to prove termination hampers compilers which could otherwise make useful transformations, such as moving nondependent operations from before the loop to after or vice versa, performing post-loop operations in one thread while the loop executes in another, and so on. Without these transformations, a loop might block all other threads while they wait for the one thread to finish said loop. (I use “thread” loosely to mean any form of parallel processing, including separate VLIW instruction streams.)

EDIT: Dumb example:

while (complicated_condition()) {
    x = complicated_but_externally_invisible_operation(x);
}
complex_io_operation();
cout << "Results:" << endl;
cout << x << endl;

Here, it would be faster for one thread to do the complex_io_operation while the other is doing all the complex calculations in the loop. But without the clause you have quoted, the compiler has to prove two things before it can make the optimisation: 1) that complex_io_operation() doesn’t depend on the results of the loop, and 2) that the loop will terminate. Proving 1) is pretty easy, proving 2) is the halting problem. With the clause, it may assume the loop terminates and get a parallelisation win.

I also imagine that the designers considered that the cases where infinite loops occur in production code are very rare and are usually things like event-driven loops which access I/O in some manner. As a result, they have pessimised the rare case (infinite loops) in favour of optimising the more common case (noninfinite, but difficult to mechanically prove noninfinite, loops).

It does, however, mean that infinite loops used in learning examples will suffer as a result, and will raise gotchas in beginner code. I can’t say this is entirely a good thing.

EDIT: with respect to the insightful article you now link, I would say that “the compiler may assume X about the program” is logically equivalent to “if the program doesn’t satisfy X, the behaviour is undefined”. We can show this as follows: suppose there exists a program which does not satisfy property X. Where would the behaviour of this program be defined? The Standard only defines behaviour assuming property X is true. Although the Standard does not explicitly declare the behaviour undefined, it has declared it undefined by omission.

Consider a similar argument: “the compiler may assume a variable x is only assigned to at most once between sequence points” is equivalent to “assigning to x more than once between sequence points is undefined”.

More Related Contents:

  1. Has C++ standard changed with respect to the use of indeterminate values and undefined behavior in C++14?
  2. In C++11, does `i += ++i + 1` exhibit undefined behavior?
  3. So why is i = ++i + 1 well-defined in C++11?
  4. In which versions of the C++ standard does “(i+=10)+=10” have undefined behaviour?
  5. Accessing inactive union member and undefined behavior?
  6. When does invoking a member function on a null instance result in undefined behavior?
  7. Is `reinterpret_cast`ing between hardware SIMD vector pointer and the corresponding type an undefined behavior?
  8. Will std::string always be null-terminated in C++11?
  9. Does “Undefined Behavior” really permit *anything* to happen? [duplicate]
  10. Is a moved-from vector always empty?
  11. c++ access static members using null pointer
  12. Is passing a C++ object into its own constructor legal?
  13. Are multiple mutations within initializer lists undefined behavior?
  14. Why is modifying a string through a retrieved pointer to its data not allowed?
  15. Get pointer to object from pointer to some member
  16. Is it legal to declare a constexpr initializer_list object?
  17. Are notes and examples in the core language specification of the C++ Standard non-normative?
  18. Why is f(i = -1, i = -1) undefined behavior?
  19. Why is the std::initializer_list constructor preferred when using a braced initializer list?
  20. Why is locking a std::mutex twice ‘Undefined Behaviour’?
  21. Does this code from “The C++ Programming Language” 4th edition section 36.3.6 have well-defined behavior?
  22. Are int8_t and uint8_t intended to be char types?
  23. What is the difference between C++03 `throw()` specifier and C++11 `noexcept`?
  24. What is the purpose of a declaration like int (x); or int (x) = 10;
  25. Can branches with undefined behavior be assumed unreachable and optimized as dead code?
  26. Does C++11 allow dollar signs in identifiers?
  27. reinterpret_cast from object to first member
  28. reinterpret_cast between char* and std::uint8_t* – safe?
  29. Does C++11 change the behavior of explicitly calling std::swap to ensure ADL-located swap’s are found, like boost::swap?
  30. C++11 cross compiler/standard library random distribution reproducibility

Leave a Comment