<div dir="ltr">Kristóf,<div><br></div><div>This is really useful for ClangSA developers. I am wondering if this should be placed somewhere in the official documentation?</div><div><br></div><div><div><div>> ---=== 3. How the static analyzer uses it ===---</div></div><div>> I'll detail this in a followup mail when and if I get to it.<br></div></div><div><br></div><div>Can't wait to read that! Perhaps that should be part of the above mentioned docs too :)</div><div><br></div><div>Gábor</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Jul 28, 2020 at 3:17 AM Kristóf Umann <<a href="mailto:dkszelethus@gmail.com">dkszelethus@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hi!<div><br></div><div>This mail will take a look at LiveVariables, which in reality is a live values analysis implemented by clang. Written about 2 months after the clang/ directory itself was created, it plays a crucial rule in the Clang Static Analyzer to this day. Despite that, I managed to find only 2 functional changes to it in the last 8 years, so we generally consider it to be stable.</div><div><br></div><div>As I wanted to merge the implementations of Liveness and UninitializedVariables, I ended up struggling a lot to comprehend the former, so this serves as a documentation for myself but written for anyone, and I welcome anyone to find errors in my understanding.</div><div><br></div><div>---=== 1. What is liveness analysis? ===---</div><div><br></div><div>Suppose statement i assigns a value to x . If statement j has x as an operand, and control can flow from statement i to j along a path that has no intervening assignments to x , then we say statement j uses the value of x computed at statement i. We further say that x is live at statement i. [5]<br></div><div><br></div><div>This can be used to spot, for example, to spot dead stores (storing a value into a variable, but not using it anywhere).</div><div><br></div><div>In practice, similarly to other data flow algorithms, we calculate an in-state and out-state for each basic block in a control flow graph. The in-state of a block is the set of variables that are live at the start of the block. Its out-state is the set of variables that are live at the end of it. The out-state is the union of the in-states of the block's successors. [8]</div><div><br></div><div>We can extend the above described live variable analysis to include values, this is the so called live expressions analysis [2]. Expressions live only within the containing statement -- for instance, argument expressions in a call expressions are live until the end of the call expression itself. If the expression isn't immediately read, it does not live in any context.</div><div><div><br></div><div><div>---=== 2. Examples ===---</div><div><br></div><div>a.) The following example shows the LIVEin and LIVEout sets (after, not during calculation): [6]</div><div><br></div><div><font face="monospace">// in: {}<br>b1: a = 3; <br> b = 5;<br> d = 4;<br> x = 100; //x is never being used later thus not in the out set {a,b,d}<br> if a > b then<br>// out: {a,b,d} //union of all (in) successors of b1 => b2: {a,b}, and b3:{b,d} <br><br>// in: {a,b}<br>b2: c = a + b;<br> d = 2;<br>// out: {b,d}<br><br>// in: {b,d}<br>b3: endif<br> c = 4;<br> return b * d + c;<br>// out:{}</font></div><div><br></div><div><div>b.) Multiple kills of a variable in a single block:</div><div><br></div><div><font face="monospace">int a = 5; // 'a' is written, can liveness tell whether 'a' is live?</font></div><div><font face="monospace">a = 6; // 'a' is written</font></div><div><font face="monospace">use(6); // 'a' is used</font></div><div><br></div><div>c.) Statement that spans multiple blocks:</div><div><font face="monospace"><br></font></div><div><font face="monospace">x ? y : z</font></div><div><br></div><div>d.) Expression liveness example:</div><div><br></div><div><font face="monospace">int getInt();<br>int getInt2();<br>void foo(int, int);<br>void test() {<br> foo(getInt(), getInt2());<br>}<br></font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">Contents of test()'s main CFGBlock:</font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="monospace">1: foo<br>2: [B1.1] (ImplicitCastExpr, FunctionToPointerDecay, void (*)(int, int))<br>3: getInt<br>4: [B1.3] (ImplicitCastExpr, FunctionToPointerDecay, int (*)(void))<br>5: [B1.4]()<br>6: getInt2<br>7: [B1.6] (ImplicitCastExpr, FunctionToPointerDecay, int (*)(void))<br>8: [B1.7]()<br>9: [B1.2]([B1.5], [B1.8])</font></div></div><div><br></div><div><div><font face="arial, sans-serif">Note how, as one would expect, the order of evaluation can be clearly seen in the elements of the block on a rather fine level.</font></div></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">The relevant (and somewhat simplified) AST:</font><br><br></div><div><font face="monospace">`-CallExpr 'void'<br> |-ImplicitCastExpr 'void (*)(int, int)'<br> | `-DeclRefExpr 'foo' 'void (int, int)'<br> |-CallExpr 'int'<br> | `-ImplicitCastExpr 'int (*)()'<br> | `-DeclRefExpr 'getInt' 'int ()'<br> `-CallExpr 'int'<br> `-ImplicitCastExpr 'int (*)()'<br> `-DeclRefExpr 'getInt2' 'int ()'</font></div><div><br></div><div><div>---=== 3. How it works in Clang ===---</div></div></div></div><div><div><br></div><div>a.) General</div><div><br></div><div>Since liveness analysis is a backwards may analysis [8], each CFGBlock in the CFG is visited with a worklist that always enqueues predecessors. It runs a fix-point algorithm, calculating the set of in- and outgoing live expressions/variables until those sets change no more.</div><div><br></div><div>Calculating liveness sets for only blocks isn't granular enough, as a single block may contain multiple kills (example b.). This demands that these LIVEin and LIVEout sets are calculated for each statement. However, since a statement can span across multiple blocks, block-level liveness needs to be calculated as well (example c.).</div><div><br></div><div>Contrary to the Wikipedia algorithm [8] describes, there are no established GEN and KILL sets, nor similar constructs like a symbol table as described in the dragon book [5]. Instead, determining which statements constitutes as variable/expression kill (write), or GENeration (use/read) is done in the same step as the calculation of the LIVEin and LIVEout sets.</div><div><br></div><div>For each block in the worklist, we traverse its CFGElements backwards and create a TransferFunctions object, which is a statement visitor under the hood. For each element in this block that is a statement (CFGStmt), we visit the statement with said TranserFunctions. We always copy the liveness set from the previous statement to the next. Wiki reads,</div><div><br></div><div>"The transfer function of a statement is applied by making the variables that are written dead, then making the variables that are read live."[8]</div><div><br></div><div>b.) Calculating expression liveness for a single CFGBlock</div><div><br></div><div>Since we also calculate live expressions however, we have to also account for them in addition. If the statement is an Expr, it must also be the kill of that Expr (it is the only write of that expression, after all), so we remove it from the live expressions set. Moving on, we branch out -- depending on the type of the statement, we mark things like the condition of for/if/while/do statements live. </div><div><br></div><div>We also employ a heuristic to generalize this task -- we mark all child expressions live as well. Demonstrating that on the Example d.):</div><div><br></div><div>* [B1.9] (Block 1, Element 9): Remove [B1.9] (as it is the CallExpr to foo) from [B1.9]'s liveness set, add its children, the arguments, [B1.5] and [B1.8], and the function to be called, [B1.2] (mind that this could be a function pointer as well!).</div><div>* [B1.8]: Remove [B1.8] (as it is the CallExpr to getInt2) from [B1.8]'s liveness set, add its child, [B1.7].</div><div>* [B1.7]: Remove [B1.7] (as it is also an Expr, an ImplicitCastExpr) from [B1.7]'s liveness set, add its child, [B1.6].</div><div>* [B1.6]: Remove [B1.6] (as it is a DeclRefExpr to getInt2) from [B1.6]'s liveness set, and since it has no more children, we're done here.</div><div>* [B1.5] -- [B1.3] same as [B1.8] --[B1.6].</div><div>* [B1.2]: Remove [B1.2] (as it is also an ImplicitCastExpr of function foo) from [B1.7]'s liveness set, add its child, [B1.1].</div><div>* [B1.1]: Remove [B1.1] (as it is the DeclRefExpr to function foo) from [B1.1]'s liveness set, and we're done.</div><div><br></div><div>This leaves the following live expression sets (mind that due to the linearity of the CFG, this is the final result):</div><div><div>* [B1.9]: [B1.8], [B1.5], [B1.2]</div><div></div></div><div><div>* [B1.8]: [B1.5], [B1.2], [B1.7]</div><div></div></div><div></div><div>* [B1.7]: [B1.5], [B1.2], [B1.6]</div><div></div><div>* [B1.6]: [B1.5], [B1.2]</div><div></div><div>* [B1.5]: [B1.2], [B1.4]</div><div></div><div>* [B1.4]: [B1.2], [B1.3],</div><div></div><div>* [B1.3]: [B1.2]</div><div></div><div></div><div>* [B1.2]: [B1.1]</div><div></div><div>* [B1.1]: {}</div><div><br></div><div>Indeed, this accurately represents the liveness of these expressions -- the function to be called, and both arguments must live until the end of the call expression.</div><div><br></div><div>c.) Calculating variable liveness for a single CFGBlock</div><div><br></div><div>Reads or usages of variables can be found in many contexts, namely when the statement visitor encounters a DeclRefExpr, DeclStmt, BlockExpr, CFGAutomaticObjDtor, or ObjCMessageExpr. What is different compared to expression live set calculation, are kills, or in other words, the removal of variables from liveness sets -- writes happen on either assignments or their definitions. Mind that not all assignments are kills -- operators such as += also read the variable.</div><div><br></div><div>In general, understanding live variables calculation follows the literature more closely, and in my experience, demands far less time to understand.</div><div><br></div><div>d.) Transfer in between blocks</div><div><br></div><div>The LIVEin set of a CFGBlock will always be the liveness set (both for variables and expressions) of the corresponding CFGElement no1. Next, as the algorithm states, we enqueue all predecessor nodes to the worklist. Processing the next block in the worklist starts with calculating its LIVEout set with the union of all liveness sets of successor blocks.</div><div><br></div><div>e.) Relaxed liveness analysis</div><div><br></div><div>LiveVariables presents the option to conduct a relaxed analysis, no longer regarding assignments as kills. This is desirable when we're not interested in a liveness of a value held by a variable, but rather the lifetime of a variable. As such, the analyzer uses relaxed liveness analysis when inquiring about variables for the most part with the exception of DeadStoresChecker. Even debug.DumpLiveStms dumps relaxed sets, but debug.DumpLiveVars uses the non-relaxed version.</div><div><br></div><div>d.) Miscellaneous notes</div><div><br></div><div>Live bindings[9] work very similarly to variables, but have their own distinct liveness set.</div><div><br></div><div>There is currently a hack in the analyzer where we assign value to a statement, and thus Liveness calculates live statements, not expressions [2], <a href="https://reviews.llvm.org/D82598#2171312" target="_blank">https://reviews.llvm.org/D82598#2171312</a>.</div><div><br></div><div>There is a corner case for CFGAutomaticObjDtor, which isn't a CFGStmt, but is still handled, as it marks its associated variable live.</div><div><br></div><div>A notable bug when we heuristic of adding all child expressions (or, as of writing this mail, still statements) didn't work is described in [3].</div><div><br></div><div>---=== 3. How the static analyzer uses it ===---</div></div><div><br></div><div>I'll detail this in a followup mail when and if I get to it. I guess the most interesting and non-trivial usage of liveness is found in DeadStoresChecker, which is definitely a good learning example of dataflow analysis being incorporated into symbolic execution.</div><div><br></div><div>If that mail doesn't happen soon enough, [1], [4], [7] provide great further reading on a related problem, zombie symbols, which is strongly related to liveness.</div><div><br></div><div>Have a great one!</div><div>Husi</div><div><br></div><div>[1] [cfe-dev] [analyzer] Zombie symbols. <a href="http://lists.llvm.org/pipermail/cfe-dev/2016-March/048142.html" target="_blank">http://lists.llvm.org/pipermail/cfe-dev/2016-March/048142.html</a><br></div><div>[2] [analyzer][Liveness][NFC] Get rid of statement liveness, because such a thing doesn't exist <a href="https://reviews.llvm.org/D82598" target="_blank">https://reviews.llvm.org/D82598</a><br></div><div>[3] [analyzer] LiveVariables: Fix a zombie expression problem, add testing infrastructure. <a href="https://reviews.llvm.org/D55566" target="_blank">https://reviews.llvm.org/D55566</a><br></div><div>[4] [analyzer] Fix the "Zombie symbols" issue. <a href="https://reviews.llvm.org/D18860" target="_blank">https://reviews.llvm.org/D18860</a></div><div>[5] <span style="font-family:Arial,sans-serif;font-size:13px">Aho, A., Lam, M., Sethi, R., & Ullman, J. (2007). Compilers: Principles, Techniques and Tools, 2nd Edition.</span></div><div><span style="font-family:Arial,sans-serif;font-size:13px">[6] Live variable analysis, Wikipedia, second example </span><a href="https://en.wikipedia.org/wiki/Live_variable_analysis#Second_example" target="_blank">https://en.wikipedia.org/wiki/Live_variable_analysis#Second_example</a></div><div>[7] <span style="font-family:Arial,sans-serif;font-size:13px">Dergachev, A. (2016). Clang Static Analyzer: A Checker Developer’s Guide.(2016).</span></div><div><span style="font-size:13px;font-family:Arial,sans-serif">[8] Live variable analysis, Wikipedia, second example </span><a href="https://en.wikipedia.org/wiki/Live_variable_analysis#Second_example" target="_blank">https://en.wikipedia.org/wiki/Live_variable_analysis</a></div><div>[9] <a href="https://clang.llvm.org/doxygen/classclang_1_1BindingDecl.html" target="_blank">https://clang.llvm.org/doxygen/classclang_1_1BindingDecl.html</a></div><div><span style="font-family:Arial,sans-serif;font-size:13px"></span></div></div>
</blockquote></div>