8 ms·

Introducing a new, advanced Visual C++ code optimizer

223 points by nikbackm 10y ago

polskibus 10y ago
I wonder what is the level of .NET's CLR optimization in comparison to this new optimizer for C++. I hope they will reuse some of those ideas to make .NET better.
- micahbright 10y ago
  Hopefully, they will just recompile the binaries, and the CLR will just get faster...
  - daeken 10y ago
    That's not really the way it works. The CLR compiles .NET code to native machine code (either at runtime or ahead of time), which means you need to implement these optimizations at the code generation layer of the CLR. You can make the CLR implementation itself faster, but that's negligible compared to the run time of the generated code.
    - micahbright 10y ago
      Are you saying the "code generation layer" of the CLR isn't itself written in c++? All of this stuff trickles down without a doubt. I realize it isn't going to magically optimize the bytecode, however, the thing that runs the bytecode will be faster.
      - ynik 10y ago
        The CLR doesn't have any bytecode interpreter that could get faster with this change. It's a JIT compiler that compiles the bytecode to native code.
        micahbright 10y ago
        Interpreter or not, the JIT compiler will certainly get faster with the c++ optimizations. The libraries that are linked against will get faster. The underlying OS components will get faster. Since .NET assemblies are mostly just glue code between framework code, which is mostly c++, everything should get a speedup out of this.
- gratilup 10y ago
  The optimizer will be ported to .NET Native soon, it should help code quality quite a lot. The JIT is a completely different matter though: it's a different project, done by a different team - copy-paste of the source code is definitely not going to work. JIT compilers also have different priorities, unlikely they would port all parts of a large optimizer.
mrich 10y ago
Thumbs up to Microsoft for investing that much into their C/C++ toolchain.
- jjawssd 10y ago
  I believe it is just a C++ toolchain and the C part is neglected. Has something changed?
  - cremno 10y ago
    Since VS2013 some useful and popular C99 language features are supported. And then there's Clang/C2 but it can't be used via command-line yet. Their standard library (besides being intentionally not fully compliant) is missing some C11 features though. I guess we have to wait at least for C++17: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0063r2.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p006...
    - xvilka 10y ago
      Not all of them, and today is 2016, important C11 feature, like _Generic still not supported. And it would be awesome, if MSVC will support GNU extensions, like Clang does. For now I recommend to use clang-cl wrapper: http://clang.llvm.org/docs/MSVCCompatibility.html http://clang.llvm.org/docs/MSVCCompatibility.html
    - pjmlp 10y ago
      For Visual C++ only to the extent as required by the C++ standard. Clang/C2 is exactly the path for those that still care about C on Windows.
  - terrymah 10y ago
    This is both C and C++ - they share a common backend (c2.dll) where this work was done. They have different front ends (c1.dll / c1xx.dll).
cokernel_hacker 10y ago
So they finally got SSA? Neat, right up there with LLVM and GCC. It also sounds like they have something like LLVM's InstCombine pass, it'll be interesting to compare which cases they handle. Despite it being a peephole pass, InstCombine is actually one of the most important scalar optimizations in LLVM's arsenal. I also wonder if they form SSA in the face of C++ and/or SEH exceptions. Like if you have something like: bool f() { int x = 2; try { throw 0; } catch (...) { x = 4; } return x & 1; } Will they insert a PHI of 2 and 4? The MSVC of today cannot optimize the return to a constant.
- cokernel_hacker 10y ago
  For reference, clang targeting MSVC mode can do this: $ clang t.cpp -target x86_64-pc-win32 -S -emit-llvm -o - | opt -S -sroa -instcombine | grep 'ret i1' ret i1 false
- deleted 10y ago
  [deleted]
- gratilup 10y ago
  Hi, I'm the author of the blog post and optimizer. We had SSA since around 1999-2000, just that some important components like the expression optimizer were written before that and not updated with support for SSA. The difference is a lot more than just SSA, the blog has just a few examples. The new framework started as being somewhat similar to InstCombine, since then it got much larger and it will be the place where more optimizations will be integrated, hopefully replacing some older ones. To answer your question: SSA is built with both types of exceptions and the new optimizer works as expected, except a few cases where it would be unsafe. It seems that the rejection rules are a bit too aggressive in your example, it's obviously safe to optimize in this case - thanks for the example!
  - cokernel_hacker 10y ago
    Cool, good to know! Another interesting example is: bool f(bool b) { int x; try { if (b) { x = 2; throw 0; } x = 4; throw 0.0; } catch (...) { } return x & 1; } Here, a phi is needed on the catch. Out of curiosity, can you give details regarding how your EH representation looks like in SSA?
dkopi 10y ago
Love the a % 2 != 0 ? 4 : 2; optimization. This used to be one of my favorite interview questions for low-level positions - conditional assignment without branches.
- deleted 10y ago
  [deleted]
- wmu 10y ago
  Nice question, I had to think for a while. :)
m4dc4pXXX 10y ago
It bothers me that they say implementing SSA eliminates the need for "complicated" data-flow analysis. Data-flow has a really nice theory behind it and enables a lot of optimizations. For example, dead-code elimination. But otherwise, kudos to MS!
- pbiggar 10y ago
  Except they are exactly right!
  - pbiggar 10y ago
    I should add more context here. A data-flow analysis framework has significant overlap with an SSA-based analysis framework, except that the SSA-based one leads to simpler analyses which are more powerful. A good comparison is CCP (conditional copy propagation) vs SCCP (sparse CCP) - the SCCP version is naturally flow-sensitive (that's a property of SSA form), so it can eliminate entire branches, leading to more dead code being eliminated.
    - rayiner 10y ago
      Aren't SSA analyses generally only "kinda flow-sensitive" since values are only renamed where control flow merges, not where it splits? E.g. int x = ... if(x > 0) { use(x) else { use(x) } In a DFA where you track information about each variable at each program point, you could push the constraint implied by the condition into each branch. If you do a sparse analysis on SSA form, that doesn't come naturally, right?
      - pcwalton 10y ago
        That's correct; it doesn't come for free.
      - nikic 10y ago
        To handle this case some SSA implementations add a concept of "pi" nodes, which are used to artificially split variables on branches that establish some useful data flow property. x1 = ... if (x1 > 0) { x2 = pi(x1 & RANGE[1..]) use(x2) } else { x3 = pi(x1 & RANGE[..0]) use(x3) } x4 = phi(x2, x3) // if used I have placed the pi nodes in the blocks, but semantically they are placed along the control edge. Ref e.g. e-SSA in the ABCD value range inference algorithm.
kibwen 10y ago
Undefined behavior notice: > Historically, Visual C++ did not take advantage of the > fact that the C and C++ standards consider the result > of overflowing signed operations undefined. Other > compilers are very aggressive in this regard, which > motivated the decision to implement some patterns which > take advantage of undefined integer overflow behavior. > We implemented the ones we thought were safe and didn’t > impose any unnecessary security risks in generated code. > A new undocumented compiler flag has been added to > disable these optimizations, in case an application > that is not standard-conformant fails: > -d2SSAOptimizerUndefinedIntOverflow-. Due to security > concerns, we have seen cases where these patterns > should not be optimized, even though following the C > and C++ standards allows us to [...] It sounds like they're not doing anything that GCC/Clang aren't already, but if you've only ever compiled with MSVC then be careful not to overlook this.
- loeg 10y ago
  Makes me wonder why they called it "d2SSAOptimizerUndefinedIntOverflow" and not the existing `-fwrapv`.
  - gratilup 10y ago
    Visual C++ does not use the GCC naming for flags. The flag will likely be renamed to something shorter in the final release in Update 3.
- protomikron 10y ago
  Interesting. Can anybody explain in a few sentences (if this is possible), why we have undefined behaviour in the first place? I know there are optimization reasons, but do we have data that confirms that turning on stricter flags (I think all major compilers let you avoid undefined behaviour) breaks lots of software?
  - Ono-Sendai 10y ago
    Undefined behaviour allows faster code. It also allows handling of situations that would otherwise have to be defined in some 'awkward' way, such as throwing an exception on out-of-bounds array reads. Edit: To add to my reply - for example, Java has almost no undefined behaviour. (The single exception AFAIK is some kind of multithreaded data race situation). The cost paid is that e.g. bounds checks must be done (in general) on array accesses, as the behaviour is defined to be an exception thrown in that case. Similarly for null reference dereferences.
zoren 10y ago
I believe the Bit Estimator example could be better: int test(unsigned char a) { short b = a; // b: 00000000________, a: ________ b <<= 4; // b: 0000________0000 b |= 3; // b: 0000________0011 return b != 0; // -> return true } The analyzer doesn't need any information about the two low bits of b to know b != 0. Had it been b ^= 3 instead of b |= 3, it would be a different matter.
- gratilup 10y ago
  I tried to have a simple example, maybe it was too simple. You are right, an OR with a constant is enough to know it is not zero. For this case the Bit Estimator also knows b = [3, 4083], writing something that takes advantage of this info would have been more interesting.
AaronFriel 10y ago
The tl;dr of this seems to be: * Visual C++ now has very aggressive SSA-based optimization rules. * One of these optimizations is the bit estimator, which tracks the state of each bit of local variables. I'm not aware of LLVM/GCC or other compilers using a bit estimator. I found some hits in the CS literature but I'm not aware of any other compilers using it, and it seems like a pretty potent optimization!
- theresistor 10y ago
  LLVM has had the same thing for a very long time, under the name SimplifyDemandedBits
- flamedoge 10y ago
  tl;dr +generated a lot more CMOV's. While conditional moves are a cheap way to get performance on poorly branch predicted programs, speculatively inserting them is _NOT_ a good idea for general performance as it may hurt performance (because of serializing conditional path) and should only be considered with Profiling information.
_RPM 10y ago
Why do they call it "Visual C++", What does the term "Visual" mean to them? Also, is their compiler standard compliant? (c++11, c++98)
- Strom 10y ago
  Visual C++ is just the product name, it's branding. It has no functional meaning beyond that. As for the standards, there's pretty good partial support for C++11/14/17. One fairly recent blog post by them has some tables. [1] [1] https://blogs.msdn.microsoft.com/vcblog/2016/01/22/vs-2015-update-2s-stl-is-c17-so-far-feature-complete/ https://blogs.msdn.microsoft.com/vcblog/2016/01/22/vs-2015-u...
  - StephanTLavavej 10y ago
    Fun fact: the compiler's version (19) is larger than the IDE's version (14) because the compiler predated the addition of "Visual" to the branding. (And the IDE skipped 13, while the compiler didn't.)
- TwoBit 10y ago
  Years ago Microsoft introduced Visual Basic, which had some drag and drop programmability. It was popular and so Microsoft management decided to put "Visual" in front of everything. And now it means nothing. Kinda like how IMax used to mean large movie screens, and it was popular so now that company calls everything the do "IMax" and it now meanscnothing.
- pjmlp 10y ago
  To add a bit more of context to TwoBit's answer, since the mid-90's, the only C++ compiler that was really visual is C++ Builder[1]. It is great for GUI applications, you get to develop C++ applications as if they were Delphi, VB ones, with all the power of C++. For Microsoft, the lame MFC was already visual enough. To be faire to Microsoft the original MFC was much more powerful, .NET style, but many didn't like it that way, hence the thin layer over Win32 APIs[2]. However since Windows 8 and the introduction of Windows App Model, Visual C++ has actually become Visual. When developing Windows apps based on the new APIs introduced to replace Win32, you can develop pure native applicatins in C++ using XAML and the exactly the same RAD tooling as .NET WPF applications. [1] https://www.embarcadero.com/products/cbuilder https://www.embarcadero.com/products/cbuilder [2] https://groups.google.com/forum/#!topic/microsoft.public.vc.mfc/IkDkvFn71uQ https://groups.google.com/forum/#!topic/microsoft.public.vc....

223 points by nikbackm 10y ago

I wonder what is the level of .NET's CLR optimization in comparison to this new optimizer for C++. I hope they will reuse some of those ideas to make .NET better.

micahbright 10y ago
Hopefully, they will just recompile the binaries, and the CLR will just get faster...
- daeken 10y ago
  That's not really the way it works. The CLR compiles .NET code to native machine code (either at runtime or ahead of time), which means you need to implement these optimizations at the code generation layer of the CLR. You can make the CLR implementation itself faster, but that's negligible compared to the run time of the generated code.
  - micahbright 10y ago
    Are you saying the "code generation layer" of the CLR isn't itself written in c++? All of this stuff trickles down without a doubt. I realize it isn't going to magically optimize the bytecode, however, the thing that runs the bytecode will be faster.
    - ynik 10y ago
      The CLR doesn't have any bytecode interpreter that could get faster with this change. It's a JIT compiler that compiles the bytecode to native code.
      - micahbright 10y ago
        Interpreter or not, the JIT compiler will certainly get faster with the c++ optimizations. The libraries that are linked against will get faster. The underlying OS components will get faster. Since .NET assemblies are mostly just glue code between framework code, which is mostly c++, everything should get a speedup out of this.
gratilup 10y ago
The optimizer will be ported to .NET Native soon, it should help code quality quite a lot. The JIT is a completely different matter though: it's a different project, done by a different team - copy-paste of the source code is definitely not going to work. JIT compilers also have different priorities, unlikely they would port all parts of a large optimizer.

mrich 10y ago

Thumbs up to Microsoft for investing that much into their C/C++ toolchain.

jjawssd 10y ago
I believe it is just a C++ toolchain and the C part is neglected. Has something changed?
- cremno 10y ago
  Since VS2013 some useful and popular C99 language features are supported. And then there's Clang/C2 but it can't be used via command-line yet. Their standard library (besides being intentionally not fully compliant) is missing some C11 features though. I guess we have to wait at least for C++17: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0063r2.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p006...
  - xvilka 10y ago
    Not all of them, and today is 2016, important C11 feature, like _Generic still not supported. And it would be awesome, if MSVC will support GNU extensions, like Clang does. For now I recommend to use clang-cl wrapper: http://clang.llvm.org/docs/MSVCCompatibility.html http://clang.llvm.org/docs/MSVCCompatibility.html
  - pjmlp 10y ago
    For Visual C++ only to the extent as required by the C++ standard. Clang/C2 is exactly the path for those that still care about C on Windows.
- terrymah 10y ago
  This is both C and C++ - they share a common backend (c2.dll) where this work was done. They have different front ends (c1.dll / c1xx.dll).

cokernel_hacker 10y ago

So they finally got SSA? Neat, right up there with LLVM and GCC. It also sounds like they have something like LLVM's InstCombine pass, it'll be interesting to compare which cases they handle. Despite it being a peephole pass, InstCombine is actually one of the most important scalar optimizations in LLVM's arsenal. I also wonder if they form SSA in the face of C++ and/or SEH exceptions. Like if you have something like: bool f() { int x = 2; try { throw 0; } catch (...) { x = 4; } return x & 1; } Will they insert a PHI of 2 and 4? The MSVC of today cannot optimize the return to a constant.

cokernel_hacker 10y ago
For reference, clang targeting MSVC mode can do this: $ clang t.cpp -target x86_64-pc-win32 -S -emit-llvm -o - | opt -S -sroa -instcombine | grep 'ret i1' ret i1 false
deleted 10y ago
[deleted]
gratilup 10y ago
Hi, I'm the author of the blog post and optimizer. We had SSA since around 1999-2000, just that some important components like the expression optimizer were written before that and not updated with support for SSA. The difference is a lot more than just SSA, the blog has just a few examples. The new framework started as being somewhat similar to InstCombine, since then it got much larger and it will be the place where more optimizations will be integrated, hopefully replacing some older ones. To answer your question: SSA is built with both types of exceptions and the new optimizer works as expected, except a few cases where it would be unsafe. It seems that the rejection rules are a bit too aggressive in your example, it's obviously safe to optimize in this case - thanks for the example!
- cokernel_hacker 10y ago
  Cool, good to know! Another interesting example is: bool f(bool b) { int x; try { if (b) { x = 2; throw 0; } x = 4; throw 0.0; } catch (...) { } return x & 1; } Here, a phi is needed on the catch. Out of curiosity, can you give details regarding how your EH representation looks like in SSA?

dkopi 10y ago

Love the a % 2 != 0 ? 4 : 2; optimization. This used to be one of my favorite interview questions for low-level positions - conditional assignment without branches.

deleted 10y ago
[deleted]
wmu 10y ago
Nice question, I had to think for a while. :)

m4dc4pXXX 10y ago

It bothers me that they say implementing SSA eliminates the need for "complicated" data-flow analysis. Data-flow has a really nice theory behind it and enables a lot of optimizations. For example, dead-code elimination. But otherwise, kudos to MS!

pbiggar 10y ago
Except they are exactly right!
- pbiggar 10y ago
  I should add more context here. A data-flow analysis framework has significant overlap with an SSA-based analysis framework, except that the SSA-based one leads to simpler analyses which are more powerful. A good comparison is CCP (conditional copy propagation) vs SCCP (sparse CCP) - the SCCP version is naturally flow-sensitive (that's a property of SSA form), so it can eliminate entire branches, leading to more dead code being eliminated.
  - rayiner 10y ago
    Aren't SSA analyses generally only "kinda flow-sensitive" since values are only renamed where control flow merges, not where it splits? E.g. int x = ... if(x > 0) { use(x) else { use(x) } In a DFA where you track information about each variable at each program point, you could push the constraint implied by the condition into each branch. If you do a sparse analysis on SSA form, that doesn't come naturally, right?
    - pcwalton 10y ago
      That's correct; it doesn't come for free.
    - nikic 10y ago
      To handle this case some SSA implementations add a concept of "pi" nodes, which are used to artificially split variables on branches that establish some useful data flow property. x1 = ... if (x1 > 0) { x2 = pi(x1 & RANGE[1..]) use(x2) } else { x3 = pi(x1 & RANGE[..0]) use(x3) } x4 = phi(x2, x3) // if used I have placed the pi nodes in the blocks, but semantically they are placed along the control edge. Ref e.g. e-SSA in the ABCD value range inference algorithm.

kibwen 10y ago

Undefined behavior notice: > Historically, Visual C++ did not take advantage of the > fact that the C and C++ standards consider the result > of overflowing signed operations undefined. Other > compilers are very aggressive in this regard, which > motivated the decision to implement some patterns which > take advantage of undefined integer overflow behavior. > We implemented the ones we thought were safe and didn’t > impose any unnecessary security risks in generated code. > A new undocumented compiler flag has been added to > disable these optimizations, in case an application > that is not standard-conformant fails: > -d2SSAOptimizerUndefinedIntOverflow-. Due to security > concerns, we have seen cases where these patterns > should not be optimized, even though following the C > and C++ standards allows us to [...] It sounds like they're not doing anything that GCC/Clang aren't already, but if you've only ever compiled with MSVC then be careful not to overlook this.

loeg 10y ago
Makes me wonder why they called it "d2SSAOptimizerUndefinedIntOverflow" and not the existing `-fwrapv`.
- gratilup 10y ago
  Visual C++ does not use the GCC naming for flags. The flag will likely be renamed to something shorter in the final release in Update 3.
protomikron 10y ago
Interesting. Can anybody explain in a few sentences (if this is possible), why we have undefined behaviour in the first place? I know there are optimization reasons, but do we have data that confirms that turning on stricter flags (I think all major compilers let you avoid undefined behaviour) breaks lots of software?
- Ono-Sendai 10y ago
  Undefined behaviour allows faster code. It also allows handling of situations that would otherwise have to be defined in some 'awkward' way, such as throwing an exception on out-of-bounds array reads. Edit: To add to my reply - for example, Java has almost no undefined behaviour. (The single exception AFAIK is some kind of multithreaded data race situation). The cost paid is that e.g. bounds checks must be done (in general) on array accesses, as the behaviour is defined to be an exception thrown in that case. Similarly for null reference dereferences.

zoren 10y ago

I believe the Bit Estimator example could be better: int test(unsigned char a) { short b = a; // b: 00000000________, a: ________ b <<= 4; // b: 0000________0000 b |= 3; // b: 0000________0011 return b != 0; // -> return true } The analyzer doesn't need any information about the two low bits of b to know b != 0. Had it been b ^= 3 instead of b |= 3, it would be a different matter.

gratilup 10y ago
I tried to have a simple example, maybe it was too simple. You are right, an OR with a constant is enough to know it is not zero. For this case the Bit Estimator also knows b = [3, 4083], writing something that takes advantage of this info would have been more interesting.

AaronFriel 10y ago

The tl;dr of this seems to be: * Visual C++ now has very aggressive SSA-based optimization rules. * One of these optimizations is the bit estimator, which tracks the state of each bit of local variables. I'm not aware of LLVM/GCC or other compilers using a bit estimator. I found some hits in the CS literature but I'm not aware of any other compilers using it, and it seems like a pretty potent optimization!

theresistor 10y ago
LLVM has had the same thing for a very long time, under the name SimplifyDemandedBits
flamedoge 10y ago
tl;dr +generated a lot more CMOV's. While conditional moves are a cheap way to get performance on poorly branch predicted programs, speculatively inserting them is _NOT_ a good idea for general performance as it may hurt performance (because of serializing conditional path) and should only be considered with Profiling information.

_RPM 10y ago

Why do they call it "Visual C++", What does the term "Visual" mean to them? Also, is their compiler standard compliant? (c++11, c++98)

Strom 10y ago
Visual C++ is just the product name, it's branding. It has no functional meaning beyond that. As for the standards, there's pretty good partial support for C++11/14/17. One fairly recent blog post by them has some tables. [1] [1] https://blogs.msdn.microsoft.com/vcblog/2016/01/22/vs-2015-update-2s-stl-is-c17-so-far-feature-complete/ https://blogs.msdn.microsoft.com/vcblog/2016/01/22/vs-2015-u...
- StephanTLavavej 10y ago
  Fun fact: the compiler's version (19) is larger than the IDE's version (14) because the compiler predated the addition of "Visual" to the branding. (And the IDE skipped 13, while the compiler didn't.)
TwoBit 10y ago
Years ago Microsoft introduced Visual Basic, which had some drag and drop programmability. It was popular and so Microsoft management decided to put "Visual" in front of everything. And now it means nothing. Kinda like how IMax used to mean large movie screens, and it was popular so now that company calls everything the do "IMax" and it now meanscnothing.
pjmlp 10y ago
To add a bit more of context to TwoBit's answer, since the mid-90's, the only C++ compiler that was really visual is C++ Builder[1]. It is great for GUI applications, you get to develop C++ applications as if they were Delphi, VB ones, with all the power of C++. For Microsoft, the lame MFC was already visual enough. To be faire to Microsoft the original MFC was much more powerful, .NET style, but many didn't like it that way, hence the thin layer over Win32 APIs[2]. However since Windows 8 and the introduction of Windows App Model, Visual C++ has actually become Visual. When developing Windows apps based on the new APIs introduced to replace Win32, you can develop pure native applicatins in C++ using XAML and the exactly the same RAD tooling as .NET WPF applications. [1] https://www.embarcadero.com/products/cbuilder https://www.embarcadero.com/products/cbuilder [2] https://groups.google.com/forum/#!topic/microsoft.public.vc.mfc/IkDkvFn71uQ https://groups.google.com/forum/#!topic/microsoft.public.vc....