Optimizing C++ Code: Dead Code Elimination(blogs.msdn.com)
blogs.msdn.com
Optimizing C++ Code: Dead Code Elimination
http://blogs.msdn.com/b/vcblog/archive/2013/08/09/optimizing-c-code-dead-code-elimination.aspx
4 comments
If you read all the way into the comments, you'll see that this does happen -- but only for values of n that are quite small. And this is a side effect of other optimizations -- not because of anything specific to this closed form.
Yes, which is kinda sad.
both GCC and LLVM do it as a result of computing scalar evolutions for the variables, and then instantiating the final values after the loop.
There are certain calculations both will bail on due to solving cost (rather than inability to solve), but otherwise ...
There are certain calculations both will bail on due to solving cost (rather than inability to solve), but otherwise ...
Yeah, I was just now skimming through the comments as well and I saw that. It looks like their constant propagation logic doesn't work on loops at all, and it's just that their loop unroller stage (which runs before it) will unroll loops of less than 10 iterations.
Dead Code Elimination can even optimise out blocking loops, a loop like for(;;) can be optimised out.
Somewhat related: http://blog.regehr.org/archives/140
So the compiler writers are bringing lazy evaluation to the unsuspecting masses?
Thats not lazy evaluation so much as "this loop literally doesn't do anything"
It does do something. It loops forever. The optimized version does nothing. This is a major difference in performance. No sarcasm; this sort of thing can manifest in real code, and when it does it will generally be a great deal more complicated. "Bugs that only appear at certain optimization levels" are not the absolute worst types of bugs to debug, but they're certainly up there on the great Hierarchy of Sucky Bugs.
Yup, when I was young and naive, I would not initialize structs to zero explicitly when they were allocated on the stack. One day I had a bug that only appeared in production code, which is bad, as I was working on an embedded system, so production code = no debugger. Took me a while to figure that one out! The compiler writer that thought that it would be a good idea to zero out stack variables, but only if the code was -O0 deserves to be taken out back and shot!
If an empty loop does no computation (i.e. has no observable side-effects), then arguably there should be no difference in observable behavior from the program. Of course, sometimes we "know" something that the compiler can't "see", and so must indicate as such in our code (e.g. using something stored inside the loop, adding volatile, ...).
Probably the most common (or at least my favorite) example of DCE leading to a surprise, is when embedded programmers use so-called "delay loops" which can be eliminated by the compiler because it too is "empty" (the loop produces nothing that is used outside of the loop).
Probably the most common (or at least my favorite) example of DCE leading to a surprise, is when embedded programmers use so-called "delay loops" which can be eliminated by the compiler because it too is "empty" (the loop produces nothing that is used outside of the loop).
An empty loop that has no computation but loops forever has an observable side-effect.
Go read page 14 of this: http://isocpp.org/files/papers/N3690.pdf ;-)
Essentially, C++ does not consider looping forever to be a side effect. You have to do something like writing to a volatile variable to ensure that the compiler does what you want.
Essentially, C++ does not consider looping forever to be a side effect. You have to do something like writing to a volatile variable to ensure that the compiler does what you want.
The relevent part of page 14:
"The implementation may assume that any thread will eventually do one of the following: — terminate, — make a call to a library I/O function, — access or modify a volatile object, or — perform a synchronization operation or an atomic operation. [ Note: This is intended to allow compiler transformations such as removal of empty loops, even when termination cannot be proven. — end note ]"
"The implementation may assume that any thread will eventually do one of the following: — terminate, — make a call to a library I/O function, — access or modify a volatile object, or — perform a synchronization operation or an atomic operation. [ Note: This is intended to allow compiler transformations such as removal of empty loops, even when termination cannot be proven. — end note ]"
I don't believe that's right (see below why). Point me to one compiler which does this intentionally (ie not a bug) and I would stand corrected, but in most cases most compiler experts I know (myself included) would frown and disapprove. There was a bug in GCC a while ago to that effect, but it's been corrected since.
Why: Computationally, there is no difference between "no code" and "a loop that iterates 100 times and does nothing". It is thus correct to eliminate the latter to preserve the observable behaviour. However, a loop that never terminates is a very different thing entirely: it says "execution will never progress past this point" and everything afterwards will never be reached. This property is so enshrined in theoretical computer science that any half-decent verification tool will consider what comes after the loop as dead code and not check it. In the newer GCC and Clang the code after a never-ending loop will be marked "unreachable" and be killed as dead code.
So removing a never-ending loop would be quite the big deal indeed.
Technical note: specifically in C and C++ and every language implemented using them, a loop with a counter but no check on the upper bound (eg. "for(i = 0; ; ++i)" ) is very different from the empty loop discussed above. Such a loop would be called "undefined behavior": the program may or may not stop, the world may explode, etc. This is because C and C++ say that overflow has undefined behavior. So this kind of loop does not mean "the programmer intends the control flow to terminate here", but rather "the programmer is playing with fire and it can burn".
Why: Computationally, there is no difference between "no code" and "a loop that iterates 100 times and does nothing". It is thus correct to eliminate the latter to preserve the observable behaviour. However, a loop that never terminates is a very different thing entirely: it says "execution will never progress past this point" and everything afterwards will never be reached. This property is so enshrined in theoretical computer science that any half-decent verification tool will consider what comes after the loop as dead code and not check it. In the newer GCC and Clang the code after a never-ending loop will be marked "unreachable" and be killed as dead code.
So removing a never-ending loop would be quite the big deal indeed.
Technical note: specifically in C and C++ and every language implemented using them, a loop with a counter but no check on the upper bound (eg. "for(i = 0; ; ++i)" ) is very different from the empty loop discussed above. Such a loop would be called "undefined behavior": the program may or may not stop, the world may explode, etc. This is because C and C++ say that overflow has undefined behavior. So this kind of loop does not mean "the programmer intends the control flow to terminate here", but rather "the programmer is playing with fire and it can burn".
What you write is perfectly plausible, and yet you're wrong. Such is the magic of the C++ standard ;)
There is a part of the C++ standard that says something along the lines of: the compiler may assume that every program will eventually exhibit some side-effect. That part of the standard also explicitly states that this is intended to allow compilers to remove loops with empty bodies (or bodies with only dead code) even if they cannot prove termination of the loop. See e.g. page 14 of http://isocpp.org/files/papers/N3690.pdf
This is certainly useful when you think of code that is created indirectly via macros and/or template instantiation. Whether compilers actually perform this "optimization" on explicit endless loops like for(;;); is another question, but at least C++ can claim to be able to run certain endless loops in under a second ;)
There is a part of the C++ standard that says something along the lines of: the compiler may assume that every program will eventually exhibit some side-effect. That part of the standard also explicitly states that this is intended to allow compilers to remove loops with empty bodies (or bodies with only dead code) even if they cannot prove termination of the loop. See e.g. page 14 of http://isocpp.org/files/papers/N3690.pdf
This is certainly useful when you think of code that is created indirectly via macros and/or template instantiation. Whether compilers actually perform this "optimization" on explicit endless loops like for(;;); is another question, but at least C++ can claim to be able to run certain endless loops in under a second ;)
Wait a second. The document you link to is a working draft for the next ISO C++ standard, which is by no means yet finalized (planned for 2014 or 2017?). The 2011 standard does not contain any wording to the same effect. Again I would be surprised if this specific paragraph makes it to the final version.
Then the initial discussion above was about C, and the ISO C standard does not contains words to that effect at all.
Then the initial discussion above was about C, and the ISO C standard does not contains words to that effect at all.
Your technical note is only true for signed integers and unsigned integers are usually the correct types for such counting loops.
Got stung by this testing out of idle curiousity whether strncmp or memcmp was faster the other day.
So memcmp was faster, right?
Didn't finish the job, realised code was optimised out by O3 and left it at that.
Unoptimised strncmp was beating unoptimised memcmp, it was taking 1.900s to finish where memcmp was taking 2.178s over many iterations.
MSVC, barely supports C99 but has time to have devs make posts about the obvious nature of optimization. Sigh.
This gets repeated a lot, but I'll say it again anyway:
MSVC is a C++ compiler. It happens to support some C99 (and will support more in VS2013, actually), but that's not its focus. While I, and many other Windows developers, feel that its standard compliance has fallen a bit behind in the last five years or so, Microsoft has made tremendous strides towards fixing that problem lately, and the roadmap (http://blogs.msdn.com/b/somasegar/archive/2013/06/28/1042993...) for full C++11/14 compliance looks good, and seems reasonable. Further, while C++11/14 compliance in MSVC isn't amazing, its compilation speed, and the optimizations it can deliver to its compiled executables, are both top-notch. VC++ generally seems to land between GCC and ICC for most code I write.
Is it perfect? No. Should it support more of C++11 and 14? Yes, and they're working on it. But as much as I wish there were a great C99 compiler on Windows, Microsoft has been open for a very, very long time that that's simply not their focus. Just as I don't assail Apple for Xcode's lousy Python support, I don't see a point in attacking MSVC for not doing C support.
MSVC is a C++ compiler. It happens to support some C99 (and will support more in VS2013, actually), but that's not its focus. While I, and many other Windows developers, feel that its standard compliance has fallen a bit behind in the last five years or so, Microsoft has made tremendous strides towards fixing that problem lately, and the roadmap (http://blogs.msdn.com/b/somasegar/archive/2013/06/28/1042993...) for full C++11/14 compliance looks good, and seems reasonable. Further, while C++11/14 compliance in MSVC isn't amazing, its compilation speed, and the optimizations it can deliver to its compiled executables, are both top-notch. VC++ generally seems to land between GCC and ICC for most code I write.
Is it perfect? No. Should it support more of C++11 and 14? Yes, and they're working on it. But as much as I wish there were a great C99 compiler on Windows, Microsoft has been open for a very, very long time that that's simply not their focus. Just as I don't assail Apple for Xcode's lousy Python support, I don't see a point in attacking MSVC for not doing C support.
The XCode Python support comment is specious at best.
We're talking about C -- the lingua franca of systems programming and important on every major computing platform.
I'd be more sympathetic to Microsoft's insistence that it "wasn't their focus" if they didn't have a long history of ignoring industry standards in favour of their own.
However, Microsoft recently said they were going to implement more of c99:
http://arstechnica.com/information-technology/2013/06/c99-ac...
...and to their credit, they've almost fully implemented the standard library from the C99 standard:
http://blogs.msdn.com/b/vcblog/archive/2013/07/19/c99-librar...
Of course, the C11/C++11 committees know how to solve this silliness -- they've intentionally worked on bringing the most recent C11 and C++11 standards closer so that if you implement C++11 you have to implement more C support :-)
The world no longer revolves around Windows or Microsoft platforms; every major platform except Microsoft's has an included or defacto compiler that supports C99. Developers wanting to write code that can be used on multiple platforms are understandably upset that Microsoft has made their lives more difficult for no good reason.
I view their lack of C99 support the same as their continued refusal to natively support OpenGL on Windows Phone, et al.
Although, given they recently implemented WebGL -- I remain hopeful.
Finally, I'd note that I'm pragmatic about this; I don't expect full C99 support. I'd accept full C11 support instead -- the controversial parts of C99 were made optional in C11. And they now finally seem committed to at least making a useful attempt at C99/C11 support thanks to the C++11/C++1y standards.
We're talking about C -- the lingua franca of systems programming and important on every major computing platform.
I'd be more sympathetic to Microsoft's insistence that it "wasn't their focus" if they didn't have a long history of ignoring industry standards in favour of their own.
However, Microsoft recently said they were going to implement more of c99:
http://arstechnica.com/information-technology/2013/06/c99-ac...
...and to their credit, they've almost fully implemented the standard library from the C99 standard:
http://blogs.msdn.com/b/vcblog/archive/2013/07/19/c99-librar...
Of course, the C11/C++11 committees know how to solve this silliness -- they've intentionally worked on bringing the most recent C11 and C++11 standards closer so that if you implement C++11 you have to implement more C support :-)
The world no longer revolves around Windows or Microsoft platforms; every major platform except Microsoft's has an included or defacto compiler that supports C99. Developers wanting to write code that can be used on multiple platforms are understandably upset that Microsoft has made their lives more difficult for no good reason.
I view their lack of C99 support the same as their continued refusal to natively support OpenGL on Windows Phone, et al.
Although, given they recently implemented WebGL -- I remain hopeful.
Finally, I'd note that I'm pragmatic about this; I don't expect full C99 support. I'd accept full C11 support instead -- the controversial parts of C99 were made optional in C11. And they now finally seem committed to at least making a useful attempt at C99/C11 support thanks to the C++11/C++1y standards.
It would help if they would just declare it unmaintained. Maybe projects would give up on sticking to a 20 year old C standard just to maintain compatibility with MSVC.
I wish these projects would just switch to MinGW. VLC and FFmpeg already use MinGW to target Windows. It's fast, stable and it lets them use nice C99 features like designated initalizers.
Designated initializers are (thankfully) among the subset of C99 that is actually getting added in the next MSVC release.
Yeah, VS2013 looks like a step in the right direction. I probably won't use it myself since I prefer FOSS development tools, but it will be a huge win for interoperability. I hope they implement enough C99 for big projects like FFmpeg to work.
Microsoft won't support a 14 year old C Standard because it's "really a C++ compiler"? When, exactly, did it from being a "C compiler" too?
At what point should a C++ Programmer worry that Visual Studio is becoming "really a C# coding environment"? Over the last few years, we've seen C# get features first with C++ receiving the same features only if MS gets around to it.
I miss the days when Microsoft cared about development tools because they had a lot of competition.
At what point should a C++ Programmer worry that Visual Studio is becoming "really a C# coding environment"? Over the last few years, we've seen C# get features first with C++ receiving the same features only if MS gets around to it.
I miss the days when Microsoft cared about development tools because they had a lot of competition.
Microsoft won't support a 14 year old C Standard
because it's "really a C++ compiler"? When, exactly, did
it from being a "C compiler" too?
Over the last few years, we've seen C# get features
first with C++ receiving the same features only if MS
gets around to it.
I further think it's clear that Microsoft does care about development tools. What they don't care about is having Visual Studio be the be-all, end-all environment for Windows development. You want C99? MinGW is actually good these days. You want Pascal? Free Pascal is at your disposal. JavaScript? NodeJS runs fine, embedded right in IIS. C++? Visual Studio actually makes one of the best C++ IDEs around, and its compiler is actually pluggable. (That's how you use ICC with it.)
So you agree that one day at a PDC, MS could just drop C++?
Seems to me our only disagreement is that I think, due to MS's lack of support for C for the 12 years before last PDC, that MS cannot be trusted to support C++.
Seems to me our only disagreement is that I think, due to MS's lack of support for C for the 12 years before last PDC, that MS cannot be trusted to support C++.
btw, do you [heavely] use c++ at fogcreek?
I used to use it heavily. In the last few months, I've also been using C++ heavily, because I'm working on some heavy performance boosts for Kiln Harmony. But I believe I am the only person in the entire company writing C++ at the moment.
Holy shit. I always find it fascinating that moment when you realize that person you vaguely know "from the internet" is exposed on a particular forum.
Thanks to the parent for getting me to click your username. We're barely acquainted in a relatively distant past when I used Kiln but your name came up a lot. If anyone is the "only person in the entire company" doing X, it's likely to be you.
Thanks to the parent for getting me to click your username. We're barely acquainted in a relatively distant past when I used Kiln but your name came up a lot. If anyone is the "only person in the entire company" doing X, it's likely to be you.
For example, clang or gcc (under -O1) will precompute all of the math in that for-loop, and the entire function just becomes the printf with a known value.