{"id":1273,"date":"2013-08-09T13:00:00","date_gmt":"2013-08-09T13:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/vcblog\/2013\/08\/09\/optimizing-c-code-dead-code-elimination\/"},"modified":"2019-02-18T18:40:57","modified_gmt":"2019-02-18T18:40:57","slug":"optimizing-c-code-dead-code-elimination","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/cppblog\/optimizing-c-code-dead-code-elimination\/","title":{"rendered":"Optimizing C++ Code : Dead Code Elimination"},"content":{"rendered":"

 <\/p>\n

If you have arrived in the middle of this blog series, you might want instead to begin at the <\/span>beginning<\/span><\/a>.<\/span><\/span><\/p>\n

This post examines the optimization called Dead-Code-Elimination, which I’ll abbreviate to DCE.  It does what it says: discards any calculations whose results are not actually used<\/em> by the program.<\/span><\/span><\/p>\n

Now, you will probably assert that your code calculates only<\/em> results that are used, and never any results that are not <\/em>used: only an idiot, after all, would gratuitously add useless code – calculating the first 1000 digits of pi<\/em>, for example, whilst also doing something useful.  So when would the DCE optimization ever have an effect?<\/span><\/span><\/p>\n

The reason for describing DCE so early in this series is that it could otherwise wreak havoc and confusion throughout our  exploration of other, more interesting optimizations: consider this tiny example program, held in a file called <\/span>Sum.cpp<\/span>:<\/span><\/span><\/span><\/p>\n

int main() {
    long long s = 0;
    for (long long i = 1; i <= 1000000000; ++i) s += i;
}<\/span><\/p>\n

We are interested in how fast the loop executes, calculating the sum of the first billion integers.  (Yes, this is a spectacularly silly example, since the result has a closed formula, taught in High school.  But that’s not the point)<\/span><\/span><\/p>\n

Build this program with the command:  <\/span><\/span>CL \/Od \/FA Sum.cpp<\/span><\/span>  and run with the command <\/span>Sum<\/span>.  Note that this build disables<\/em> optimizations, via the <\/span>\/Od<\/span> switch.  On my PC, it takes about 4 seconds to run.  Now try compiling optimized-for-speed, using <\/span>CL \/O2 \/FA Sum.cpp<\/span>.  On my PC, this version runs so fast there’s no perceptible delay.  Has the compiler really done such a fantastic job at optimizing our code?  The answer is no (but in a surprising way, also yes):<\/span><\/span><\/p>\n

Let’s look first at the code it generates for the \/Od<\/span> case, stored into Sum.asm<\/span>.  I have trimmed and annotated the text to show only the loop body:<\/span><\/span><\/p>\n

       mov    QWORD PTR s$[rsp], 0                     ;; long long s = 0
<\/span>       mov    QWORD PTR i$1[rsp], 1                    ;; long long i = 1
<\/span>       jmp    SHORT $LN3@main <\/span> 
$LN2@main<\/span><\/a>:<\/span>
<\/span>       mov    rax, QWORD PTR i$1[rsp]                  ;; rax = i
<\/span>       inc    rax                                      ;; rax += 1
<\/span>       mov    QWORD PTR i$1[rsp], rax                  ;; i = rax<\/span> 
<\/span>$LN3@main<\/span><\/a>:
<\/span>       cmp    QWORD PTR i$1[rsp], 1000000000           ;; i <= 1000000000 ?
<\/span>       jg     SHORT $LN1@main                          ;; no – we’re done
<\/span>       mov    rax, QWORD PTR i$1[rsp]                  ;; rax = i
<\/span>       mov    rcx, QWORD PTR s$[rsp]                   ;; rcx = s
<\/span>       add    rcx, rax                                 ;; rcx += rax
<\/span>       mov    rax, rcx                                 ;; rax = rcx
<\/span>       mov    QWORD PTR s$[rsp], rax                   ;; s = rax
<\/span>       jmp    SHORT $LN2@main                        &\nnbsp; ;; loop
<\/span>$LN1@main:<\/span><\/span><\/p>\n

The instructions look pretty much like you would expect.  The variable <\/span>i<\/span> is held on the stack at offset <\/span>i$1<\/span> from the location pointed-to by the RSP register; elsewhere in the asm file, we find that <\/span>i$1<\/span> = 0.  We use the <\/span>RAX<\/span> register to increment <\/span>i<\/span>.  Similarly, variable <\/span>s<\/span> is held on the stack (at offset <\/span>s$<\/span> from the location pointed-to by the <\/span>RSP<\/span> register; elsewhere in the asm file, we find that <\/span>s$<\/span> = 8).  The code uses <\/span>RCX<\/span> to calculate the running sum each time around the loop.<\/span><\/span><\/p>\n

Notice how we load the value for <\/span>i<\/span> from its “home” location on the stack, every time around the loop; and write the new value back to its “home” location.  The same for the variable <\/span>s<\/span>.  We could describe this code as “naïve” – it’s been generated by a dumb compiler (i.e., one with optimizations disabled).  For example, it’s wasteful to keep accessing memory for every iteration of the loop, when we could have kept the values for <\/span>i<\/span> and <\/span>s<\/span> in registers throughout.<\/span><\/span><\/p>\n

So much for the non-optimized code.  What about the code generated for the optimized case?  Let’s look at the corresponding <\/span>Sum.asm <\/span>for the optimized, \/O2<\/span>, build.  Again, I have trimmed the file down to just the part that implements the loop body, and the answer is:<\/span><\/span><\/p>\n

                                                       ;; there’s nothing here!<\/span><\/span><\/p>\n

Yes – it’s empty!  There are no<\/em> instructions that calculate the value of <\/span>s<\/span>.   <\/span><\/span><\/p>\n

Well, that answer is clearly wrong, you might say.  But how do we know <\/em>the answer is wrong?  The optimizer has reasoned that the program does not actually<\/em> make use of the answer for <\/span>s<\/span> at any point; and so it has not bothered to include any code to calculate it.  You can’t say the answer is wrong, unless you check that answer, right?<\/span><\/span><\/p>\n

We have just fallen victim to, been mugged in the street by, and lost our shirt to, the DCE optimization.  If you don’t observe an answer, the program (often) won’t calculate that answer.  <\/span><\/span><\/p>\n

You might view this effect in the optimizer as analogous, in a profoundly shallow way, to a fundamental result in Quantum Physics, often paraphrased in articles on popular science as “<\/span>If a tree falls<\/span><\/a> in the forest, and there’s nobody around to hear, does it make a sound?”<\/span><\/span><\/p>\n

Well, let’s “observe” the answer in our program, by adding a <\/span>printf<\/span> of variable <\/span>s<\/span>, into our code, as follows:<\/span><\/span><\/p>\n

#include <stdio.h>
<\/span>int main() {
<\/span>    long long s = 0;
<\/span>    for (long long i = 1; i <= 1000000000; ++i) s += i;
<\/span>    printf(“%lld “, s);
<\/span>}  <\/span><\/span><\/p>\n

The \/Od<\/span> version of this program prints the correct answer, still taking about 4 seconds to run.  The \/O2<\/span> version prints the same, correct answer, but runs much faster.   (See the optional section below for the value of “much faster” – in fact, the speedup is around 7X)<\/span><\/span><\/p>\n

At this point, we have explained the main point of this blog post: always be very careful in analyzing compiler optimizations, and in measuring their benefit, that we are not being misled by DCE.  Here are four steps to help notice, and ward off, the unasked-for attention of DCE:<\/span><\/span><\/p>\n