5 ms·

These optimizations are on LLVM IR into LLVM IR. So basically every backend benefits. I don't think most backend engineers would even understand them. I don't.

dragontamer 5y ago
None of these steps are too hard to think about in SSA form (a specific transformation of code that LLVM does near the beginning of its analysis). So the key is to first understand SSA form. After that, a lot of optimization passes become obvious to think about. --------- SSA has two bits to understand: 1. Single static assignment -- variables can be assigned, but once assigned they can never change. (This part is easy). 2. Graph-based, and therefore requires the 'Phi' function to understand -- variables may take on two different values. EX: "r0" may come from Node#1, while "r0" comes from Node#2. r0 may have been renamed %1 in #1, and %2 in #2. "Phi" is a "fake function" that resolves the ambiguity and kinda makes SSA code "real" again. Hmm, maybe that's a bad explanation. But whatever, my point is that understanding "Phi" is the concept you want to focus on in SSA. Phi is the harder part, but its still not that hard to understand. Once you get it, the whole form "clicks" in your brain and you suddenly understand how optimizations can become possible.
- jcranmer 5y ago
  Another explanation of SSA: SSA is static single assignment. Every variable has a single point of declaration. If you want to change the value of a variable (say, i = i + 1), you instead have to create a new variable. The advantage of this form is that tracking the definition of a variable is trivial; in LLVM IR, to use a variable, you literally pass in a pointer to the instruction that defined it. The inverse, finding all uses of a value, is done by building a use-list: whenever you create an instruction, it adds itself to the use-list of all the values it's using, which allows easy iteration of the users of a value. In short, SSA gives you a trivially correct-by-construction to understand the dataflow of a program (at least, that data which lives in registers; memory is more complicated). There's no separate analysis that has to be maintained throughout optimizations, and hence a possible source of programs (as there is for failure to maintain the dominator tree through CFG transformations, a historically bug-prone step in LLVM). Now, as you may notice, there are cases where it would seem hard to pin down a single definition of a variable: conditional assignment. SSA solves this by creating Phi values. Phi values can be better thought of as basic block arguments: when you enter a basic block, you must provide a value for each of the phi values in that basic block. The actual value of the phi is dependent on which edge you used to enter a basic block, or in other words, the control dependencies of the code. In short, phis are the intersection of control flow in the code with the dataflow--and they are the only things in that intersection.
- mhh__ 5y ago
  LLVMs IR has linear basic blocks inside a function graph, there are IRs which are graph all the way down as well.
woodruffw 5y ago
> I don't think most backend engineers would even understand them. I don't. Most engineers are intimidated by compilers, but they really shouldn't be! LLVM's source code is very approachable and well-isolated by concern, and most of the fundamental concepts in an optimizing compiler are understandable with a beginner's understanding of data structures, assembly, and resource allocation. One slightly funny thing, though: LLVM's optimizations are on IR, so every frontend can theoretically benefit from them. However, many assume patterns originating from the C/C++ frontend or heavy canonicalization, so you need to be a little careful as a language frontend developer to take full advantage of all optimizations!
- mhh__ 5y ago
  LLVM is approachable but some things are no better than GCC, I find. In particular I have noticed there seems to be very little high level documentation for the instruction scheduler. I find GCC machine def files actually slightly easier to read than LLVM's
- jagger27 5y ago
  > so you need to be a little careful as a language frontend developer to take full advantage of all optimizations! So does this mean that it’s possible to express exotic patterns in LLVM-IR that aren’t typically produced when compiling C or C++? Are Rust’s optimizer passes significantly different than clang's? I would guess borrow checking has a special pass that wouldn’t be applicable to C. This topic is really fascinating to me!
  - jamincan 5y ago
    Notably, the Rust borrow checker has exposed a tonne of bugs in the LLVM noalias optimizations. I believe the latest versions of rustc now have noalias enabled since the LLVM 12 release, but it's been a long cycle of enabling it, discovering a bug, and disabling it to this point.
  - sillycross 5y ago
    My experience is that LLVM can generally optimize the IR produced from clang frontend a bit better than the IR produced by myself. The advantage is small, but still exists. I think the major reason is that TBAA optimization is only possible if you manually emit those metadata (clang does, but I didn't, due to time limitation and fear of aliasing-related bugs). But that LLVM is designed to work best on the pattern emitted by Clang is definitely another reason. In fact, even the official documentation recommends users to emit IR in a way that looks similar to what is emitted by Clang, so you have a better chance to keep the LLVM optimizer happy.
srcreigh 5y ago
EDIT - nvm, the CS241 UWaterloo course doesn't cover SSA. In case anybody's interested in learning the basics, here's some course notes to a compilers class which I love! http://anthony-zhang.me/University-Notes/CS241/CS241.html http://anthony-zhang.me/University-Notes/CS241/CS241.html
- CalChris 5y ago
  Your notes, while honestly very good, don't cover data flow analysis or Single Static Assignment (SSA) which is what LLVM IR [1] uses and which are the tools that the article's optimizations are based on. Hell, LLVM backend engineers rarely even look at IR. We mostly look at Generic Machine IR [2]. [1] https://llvm.org/docs/LangRef.html https://llvm.org/docs/LangRef.html [2] https://llvm.org/docs/GlobalISel/GMIR.html https://llvm.org/docs/GlobalISel/GMIR.html
  - srcreigh 5y ago
    Ah, my bad. When you said "backend" I thought you mean "HTTP backend" hence my over-simplification. You're right -- SSA isn't covered in that course. Cheers.
- dleslie 5y ago
  Interesting, in my day SFU kept this til 3rd year, as CMPT379 IIRC, and only as an option for Theoretical or Systems paths. Looks like it's still 379; not sure about the optional component. http://anoopsarkar.github.io/compilers-class/ http://anoopsarkar.github.io/compilers-class/
- macintux 5y ago
  Decades ago I participated in some group programming contest for universities (in person, not online). We did terribly, but mainly I remember being in awe of how quickly Waterloo was solving the challenges.

dragontamer 5y ago

None of these steps are too hard to think about in SSA form (a specific transformation of code that LLVM does near the beginning of its analysis). So the key is to first understand SSA form. After that, a lot of optimization passes become obvious to think about. --------- SSA has two bits to understand: 1. Single static assignment -- variables can be assigned, but once assigned they can never change. (This part is easy). 2. Graph-based, and therefore requires the 'Phi' function to understand -- variables may take on two different values. EX: "r0" may come from Node#1, while "r0" comes from Node#2. r0 may have been renamed %1 in #1, and %2 in #2. "Phi" is a "fake function" that resolves the ambiguity and kinda makes SSA code "real" again. Hmm, maybe that's a bad explanation. But whatever, my point is that understanding "Phi" is the concept you want to focus on in SSA. Phi is the harder part, but its still not that hard to understand. Once you get it, the whole form "clicks" in your brain and you suddenly understand how optimizations can become possible.

jcranmer 5y ago
Another explanation of SSA: SSA is static single assignment. Every variable has a single point of declaration. If you want to change the value of a variable (say, i = i + 1), you instead have to create a new variable. The advantage of this form is that tracking the definition of a variable is trivial; in LLVM IR, to use a variable, you literally pass in a pointer to the instruction that defined it. The inverse, finding all uses of a value, is done by building a use-list: whenever you create an instruction, it adds itself to the use-list of all the values it's using, which allows easy iteration of the users of a value. In short, SSA gives you a trivially correct-by-construction to understand the dataflow of a program (at least, that data which lives in registers; memory is more complicated). There's no separate analysis that has to be maintained throughout optimizations, and hence a possible source of programs (as there is for failure to maintain the dominator tree through CFG transformations, a historically bug-prone step in LLVM). Now, as you may notice, there are cases where it would seem hard to pin down a single definition of a variable: conditional assignment. SSA solves this by creating Phi values. Phi values can be better thought of as basic block arguments: when you enter a basic block, you must provide a value for each of the phi values in that basic block. The actual value of the phi is dependent on which edge you used to enter a basic block, or in other words, the control dependencies of the code. In short, phis are the intersection of control flow in the code with the dataflow--and they are the only things in that intersection.
mhh__ 5y ago
LLVMs IR has linear basic blocks inside a function graph, there are IRs which are graph all the way down as well.

woodruffw 5y ago

> I don't think most backend engineers would even understand them. I don't. Most engineers are intimidated by compilers, but they really shouldn't be! LLVM's source code is very approachable and well-isolated by concern, and most of the fundamental concepts in an optimizing compiler are understandable with a beginner's understanding of data structures, assembly, and resource allocation. One slightly funny thing, though: LLVM's optimizations are on IR, so every frontend can theoretically benefit from them. However, many assume patterns originating from the C/C++ frontend or heavy canonicalization, so you need to be a little careful as a language frontend developer to take full advantage of all optimizations!

mhh__ 5y ago
LLVM is approachable but some things are no better than GCC, I find. In particular I have noticed there seems to be very little high level documentation for the instruction scheduler. I find GCC machine def files actually slightly easier to read than LLVM's
jagger27 5y ago
> so you need to be a little careful as a language frontend developer to take full advantage of all optimizations! So does this mean that it’s possible to express exotic patterns in LLVM-IR that aren’t typically produced when compiling C or C++? Are Rust’s optimizer passes significantly different than clang's? I would guess borrow checking has a special pass that wouldn’t be applicable to C. This topic is really fascinating to me!
- jamincan 5y ago
  Notably, the Rust borrow checker has exposed a tonne of bugs in the LLVM noalias optimizations. I believe the latest versions of rustc now have noalias enabled since the LLVM 12 release, but it's been a long cycle of enabling it, discovering a bug, and disabling it to this point.
- sillycross 5y ago
  My experience is that LLVM can generally optimize the IR produced from clang frontend a bit better than the IR produced by myself. The advantage is small, but still exists. I think the major reason is that TBAA optimization is only possible if you manually emit those metadata (clang does, but I didn't, due to time limitation and fear of aliasing-related bugs). But that LLVM is designed to work best on the pattern emitted by Clang is definitely another reason. In fact, even the official documentation recommends users to emit IR in a way that looks similar to what is emitted by Clang, so you have a better chance to keep the LLVM optimizer happy.

srcreigh 5y ago

EDIT - nvm, the CS241 UWaterloo course doesn't cover SSA. In case anybody's interested in learning the basics, here's some course notes to a compilers class which I love! http://anthony-zhang.me/University-Notes/CS241/CS241.html http://anthony-zhang.me/University-Notes/CS241/CS241.html

CalChris 5y ago
Your notes, while honestly very good, don't cover data flow analysis or Single Static Assignment (SSA) which is what LLVM IR [1] uses and which are the tools that the article's optimizations are based on. Hell, LLVM backend engineers rarely even look at IR. We mostly look at Generic Machine IR [2]. [1] https://llvm.org/docs/LangRef.html https://llvm.org/docs/LangRef.html [2] https://llvm.org/docs/GlobalISel/GMIR.html https://llvm.org/docs/GlobalISel/GMIR.html
- srcreigh 5y ago
  Ah, my bad. When you said "backend" I thought you mean "HTTP backend" hence my over-simplification. You're right -- SSA isn't covered in that course. Cheers.
dleslie 5y ago
Interesting, in my day SFU kept this til 3rd year, as CMPT379 IIRC, and only as an option for Theoretical or Systems paths. Looks like it's still 379; not sure about the optional component. http://anoopsarkar.github.io/compilers-class/ http://anoopsarkar.github.io/compilers-class/
macintux 5y ago
Decades ago I participated in some group programming contest for universities (in person, not online). We did terribly, but mainly I remember being in awe of how quickly Waterloo was solving the challenges.