4 ms·
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 i
by 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 agoAnother 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 agoLLVMs IR has linear basic blocks inside a function graph, there are IRs which are graph all the way down as well.