This is a story about the removal of a compiler optimization that had been in LLVM for a long time.

In C and C++, ‘e1 && e2’ conditionally evaluates e2 only if e1 evaluates to true. This is called a short-circuit evaluation, and programmers often rely on this to write an idiom like ‘idx < LEN && check(array[idx])’ that prevents the latter expression from raising an out of bounds access using the former condition^[1].

To correctly implement short-circuit evaluation, Clang inserts a branch that has the result of e1 as its condition when it translates ‘e1 && e2’ into the intermediate representation of LLVM. Then, it places e2 at a basic block which is executed only if the branch is taken. For example, the emitted intermediate representation of LLVM – or simply LLVM IR – translated from ‘idx < LEN && check(array[idx])’ roughly looks like this.

However, we know that conditional branches are, well, expensive. It is the SimplifyCFG pass that tries to remove the branch that looks like the one in the above example. It checks whether hoisting out the evaluation of e2 from the condition branch is (A) correct and (B) beneficial. A is met if e2 does not have any side effect, or the operations in e2 are possible to execute speculatively. B is met if e2 is very cheap, e.g., a simple integer comparison.

For the above example, neither A nor B holds because speculating a load is not safe or beneficial in general. For a simpler expression like ‘idx < LEN && idx != 1’ however, both A and B hold. Therefore, SimplifyCFG optimizes it to an IR program that does not have a branch. To represent the output, it uses the select instruction. Select is equivalent to the ternary operator ‘?:’ in C, except that the instruction can only take a constant or variable as its value operands. In the code generation, select can be efficiently lowered into an assembly like cmov in x86-64.

The journey does not stop here, and LLVM goes one step further. The InstCombine pass in LLVM rewrites ‘select’ to ‘and’. This is beneficial because it allows many optimizations for the bitwise ‘and’ operation (e.g., ‘x & (y & x)’ => ‘x & y’) to be reused.

The topic of this post is about the validity of the last canonicalization (select -> and). Unsurprisingly, the canonicalization has been in InstCombine for a long time; It was introduced in Apr 2004^[2], which was a month after ‘select’ was added to the list of IR instructions^[3].

However, the canonicalization is incorrect because the optimized program is more undefined if one of its operands is a poison value. Precisely speaking, the canonicalization had been correct in the past because the poison value was introduced six years after the canonicalization was written. After the introduction of the poison value, its correctness was in the gray area. Then, it explicitly became incorrect after a recent clarification of the semantics of the select instruction with respect to the poison value.

Then, what is a poison value? A poison value is a conceptual value that represents the result of an erroneous operation. For operations like shifting with an amount larger than integer bitwidth - 1, the evaluation does not immediately make the program undefined, but a poison value is stored into the virtual register^[4]. If the program does not access the register at all, everything is fine. An instruction that takes a poison value as input also returns poison (with a few exceptions). If the instruction has a side-effect, the program behavior finally becomes entirely undefined. According to the GitHub commit history, it was initially called a “trap value”^[5]. After a year, it was renamed to a “poison value”^[6].

Then, why does the existence of a poison value make the canonicalization incorrect? It is because the ‘select’ and ‘and’ operations have different rules about how a poison input is propagated to the output. According to the latest LangRef, they are like this:

According to this definition, canonicalizing ‘select A, B, 0’ into ‘and A, B’ is incorrect because the result is more poisonous if A is false and B is poison! To see the problem in practice, let’s consider a C expression ‘i < 32 && (16 >= 1 << i)’ where ‘i’ is a 32-bit integer. The expression is evaluated to false if i is 32. However, the canonicalization in LLVM converts it into an expression that uses the bitwise ‘and’, which is analogous to ‘i < 32 & (16 >= 1 << i)’. According to the poison propagation rule, the result is more undefined if i = 32.

Two tables below show the results of the two expressions ‘select x, y, false’ and ‘and x, y’ when various values are given to x and y:

Note that the poison propagation rules were fully specified in LangRef in 2020, which is quite recent. Before this change, LangRef stated that instructions other than phi nodes depend on their operands. This meant that ‘select false, poison, _’ was poison, invalidating lowering C’s “:?” / “&&” / “||” into the select instruction. Due to these problems, LangRef was updated to treat ‘select’ like a phi node in 2020, reaching to the current wordings^[7]. Instead, the canonicalization explicitly became an invalid transformation.

The canonicalization had been in the InstCombine pass of LLVM for more than 14 years. Then, it was discovered by a formal verification tool in 2014 that the canonicalization was problematic^[8]. However, the canonicalization was not fixed because it did not cause any real-world miscompilation^[9]. The first real-world miscompilation bug was reported in early 2020. It caused a patch that implements a valid optimization^[10] to be reverted because it interacted badly with the canonicalization, causing an end-to-end miscompilation. Then, after a poison constant was added to LLVM in 2020^[11] and used more and more, many miscompilation bugs began to appear. This necessitated the removal of the old and incorrect canonicalization.

To fix the incorrect canonicalization, we came up with two solutions. The first one was to simply remove it. However, this could lead to performance regressions in optimized programs. In LLVM, simplification patterns for the bitwise ‘and’ operation (e.g., ‘x && (y && x)’ -> ‘x & (y & x)’ -> ‘y & x’) were responsible for optimizing conjunctions (similarly for bitwise ‘or’ and disjunctions). Without this canonicalization, conjunctions could not be optimized.

The second solution was to use the freeze instruction. Canonicalizing ‘select i1 x, y, false’ to ‘and x, (freeze y)’ is correct because the freeze instruction blocks the propagation of the poison value. The two expressions are not equivalent as the latter has a more defined result. This transformation is correct because a compiler can remove undefinedness from the source program.

Table 3. The outputs of ‘and i1 x, (freeze y)’. If x is true and y is poison, the result is well-defined.

This solution salvages a portion of, but not all, optimizations. For example, ‘x && (y && x)’ is canonicalized to ‘and x, (freeze (and (freeze y), x))’, which can be optimized into ‘and x, (freeze y)’ thanks to the existing optimizations on the (1) ‘and’ operation and (2) ‘freeze’ operation.

However, the second solution had one serious drawback: the insertion of freeze permanently removes undefinedness from the source program (look at the table above). Since undefined behavior in the program gives more freedom to compiler to do optimizations, its removal induces suboptimal code generation. I will leave a realistic optimization example that can be blocked at the bottom of this blog post.

Of course, it is reasonable to add a transformation that inserts freeze if the transformation brings a performance improvement. However, the canonicalization does not make the program fast or small by itself; it is the later pipeline that recognizes the bitwise operations and makes things better. Well, in theory, we could update all bitwise optimizations to accept selects as well and still achieve the goal.

After discussions, we chose to pursue the first solution. That was a tough decision because, as mentioned before, it meant we needed to start investigating all optimizations (as well as analyses) in LLVM and fix them.

A question that was naturally raised was whether we could revive the canonicalization in certain cases to minimize the impact. For example, if ‘y’ in ‘x && y’ is known to never be a poison value, then the canonicalization is valid. The never-poison analysis already existed in LLVM^[12] and we could simply use it. However, this is not the only case where the canonicalization is valid.

Then, what is the precise analysis that allows this canonicalization? The only problematic case was when x was false and y was poison. What about implementing a value analysis that takes two values (x, y) and returns true if ‘x != false or y != poison’? According to the definition of implication, this is equivalent to ‘y = poison implies x != false?’. But, the analysis was too specific to this problem. There was also a canonicalization that rewrites a disjunction ‘x || y’ to ‘x | y’ as well, and the analysis certainly needed to be reused to this case. By slightly sacrificing the precision, we generalized it to ‘does y = poison imply (x != false /\ x != true)’, which is equivalent to

The new value analysis function was called ‘impliesPoison(y, x)’. It is currently located at Analysis/ValueTracking.{h,cpp}.

Let’s visualize the cases where impliesPoison works. In table 4, a cell has a check (v) if it is theoretically correct to canonicalize ‘select i1 x, y, false’ to ‘and i1 x, y’ when (x, y) have the corresponding values. Also, a cell is colored blue if impliesPoison(y, x) is true in that case. Note that impliesPoison(y, x) is true if y is not poison. This is because false implies anything in logic.

You can see that using impliesPoison reallows the canonicalization in most cases.

Then, how is the impliesPoison(y, x) implemented? We inductively defined impliesPoison as follows:

Interestingly, this analysis turned out to work well in practice. It was because many optimizations on conjunctions were dealing with formulae whose two subexpressions use the same set of variable, e.g., ‘idx < 10 && idx < 20’ or ‘(a | b) && (~a | b)’. Note that we can easily prove that impliesPoison(idx < 20, idx < 10) is true.

Therefore, the formula can be canonicalized into ‘and (idx < 10), (idx < 20)’. Similarly, impliesPoison(~a | b, a | b) is true.

Resurrecting the canonicalization using impliesPoison could partially recover the performance. However, the performance recovery was still not very satisfactory. We needed to update existing optimizations on the ‘and’ operator to deal with the select form (similarly for ‘or’ and its select form as well).

In order to facilitate updating existing optimizations, two pattern matchers were added into LLVM: m_LogicalAnd and m_LogicalOr. m_LogicalAnd(e, A, B) checks whether expression e is either ‘and i1 e1, e2’ or ‘select i1 e1, e2, false’ (allowing a vector type of i1s as well) such that ‘e1’ satisfies pattern A and ‘e2’ satisfies pattern B; similarly, m_LogicalOr checks whether the expression is a disjunction. Also, to track missing optimizations on the select form, unit tests on ‘and’ optimizations in LLVM were duplicated and edited in order to track whether ‘select’ instructions are also optimized. To make the comparison of the assembly outputs easy, a command-line flag that disables the select canonicalization was added as well.

These preparations made the updates easier than before, but we still needed to visit each optimization and carefully check whether generalizing it to accepting the ‘select’ form. The impliesPoison-based canonicalization could significantly reduce the number of optimizations to visit, but there were still many. Fortunately, we find that many of the remaining optimizations were recognizing conjunctions at conditional branches, and they fell into one of these two cases:

This optimization is still valid even if ‘cond1 && cond2’ is not canonicalized into the ‘and’ form.

This optimization isn’t valid because replacing use(i) with use(min(0, poison)) = use(poison) is incorrect.

To fully recover the performance, we added peephole optimizations that simplify expressions containing selects. The simplest and new one was an optimization folding ‘a && (a && b)’ (in C) into ‘a && b’ (in C)^[13]. General patterns were added by calling isImpliedCondition(lhs, rhs) in LLVM’s value analysis^[14]. isImpliedCondition is an LLVM function that returns true if lhs = true implies rhs = true (e.g., isImpliedCondition(“x < 10”, “x < 20”) returns true). For example, ‘(a || b) && c’ is now simplified into ‘a && c’ if isImpliedCondition(c, !b) holds. Optimizations for expressions containing both ‘select’ and bin ops - such as folding ‘a & (b ? A : B)’ into ‘a ? A : false’ if a = true implies b = true – were added as well^[15].

Checking the correctness of these optimizations was not trivial due to the existence of poison and undef values. For each patch, we left link(s) to Alive2 to show the validity of transformation.

Fixing some optimizations on the and/or operations required additional tricks. For example, LLVM simplifies ‘((t1 & k) == 0) | ((t4 & k) == 0)’ into ‘((t1 | t4) & k) == 0’ because the latter has fewer operations. However, the select version of the input pattern - ‘((t1 & k) == 0) || ((t4 & k) == 0)’ - cannot be optimized to the latter because the result may be more undefined if t4 is poison. To correctly fix it, t4 must be replaced with ‘freeze t4’. This tweak was necessary to resolve 6% performance regression after the removal of canonicalization^[16].

We updated LLVM to recognize the select form of conjunction as having the cost of an ‘and’ operation^[17]. The backend was updated to generate optimized assembly for the selects^[18].

First, we left InstCombine as the only place where the canonicalization happened. Previously, there were several optimizations that used the ‘and’ operation to create a conjunction expression in an IR program (‘or’ for a disjunction as well). For example, SimplifyCFG was inserting ‘and’ to represent the merged condition after merging two consecutive branches into one^[19]. Also, a loop vectorizer and peephole optimization were incorrectly introducing ‘and’ as well^[20].

Second, we conditionally disabled the InstCombine canonicalization^[21] to fix a miscompilation bug reported in March 2021^[22]. The canonicalization was disabled if the second operand of the select (‘b’ in ‘select a, b, false’) was a poison-creating operation like ‘add nsw’. Since many arithmetic operations translated from C have poison-generating flags, it made the canonicalization seldomly happen. Fortunately, no performance regression that was hard to fix was reported after this patch had landed. This meant that the complete removal of the canonicalization was prospective.

The last step was to fully disable the canonicalization unless impliesPoison hold^[23]. It was spurred by another miscompilation bug report due to this canonicalization^[24]. After a lot of optimizations were added in advance to avoid a performance regression, the canonicalization was fully removed in May 2021.

Interestingly, after each step, hidden bugs and issues in LLVM were revealed^[25]. We found miscompilation bugs after the first step and the third step. Also, an unexpected performance regression and infinite loop were found after the second step. If the removal of the canonicalization had been done at once, downstream projects of LLVM must have fallen into a chaotic state. Gradually removing the canonicalization helped us avoid the hassle.

However, the story isn’t over yet. A report^[26] demonstrates suboptimal code generations due to uncovered simplification patterns on select. This implies that there still exists a set of transformations that are uncovered by our updates. Furthermore, we don’t know which transformations are uncovered unless users report performance regressions. Exhaustively adding all possible optimizations on select is infeasible and will cause the compiler to run infinitely.

Then, how can we solve this problem? The problem exists because LLVM has poison value, but we cannot change the IR because its existence allows another set of important optimizations. Instead, we can update the frontends (e.g., C/C++, Swift, Rust) to leave never-poison marks at SSA variables. Then, the canonicalization will fire again because impliesPoison(y,x) returns true if y is never poison (it’s because false implies everything).

This is somewhat analogous to how the alignment information of a pointer is encoded in LLVM IR. Many architectures support fast and wide memory instructions that are tailored for specific alignment(s). Therefore, to use the instructions, it is important to check whether a dereferencing pointer has the alignment. However, in LLVM IR, a pointer type ‘ty*’ has nothing to do with its underlying type ‘ty’. This means that one cannot infer the alignment of a pointer from ‘ty’. Instead, it is the frontend that leaves the alignment information. For example, the C language standard states that types have alignment requirements, and the addresses of objects of that type must satisfy the restriction. The clang frontend attaches the ‘align’ attribute (with the corresponding alignment number) to pointers and instructions using them.

Actually, LLVM IR already has an attribute for presenting the never-poison information - it is the ‘noundef’ attribute. If the ‘noundef’ attribute is attached to a function argument, its value is neither undef nor poison because passing such values to the argument is undefined behavior. What is cool is that clang already has a command-line flag that enables attaching the ‘noundef’ attribute to arguments if C/C++ standards allow doing so^[27]. Turning on the flag effectively resolved a performance regression after another miscompilation bug was fixed using the freeze instruction. I believe that the flag will also help address unseen performance regressions after the removal of select canonicalization as well. To enable the flag by default, a student who participated in Google Summer of Code this year created a patch^[28]. We welcome any support for reviewing our patch! ☺

Appendix I. An example showing that folding ‘select x, y, false’ to ‘add x, (freeze y)’ can block further optimizations.

The inserted freeze can block induction variable widening. “The nsw story”^[29] has a nice background about the transformation. Imagine this loop:

If the branch condition is canonicalized into ‘and’ with its second operand frozen, it becomes:

This is bad because the loop condition is frozen. This blocks loop optimizations such as induction variable widening on y. If there was no freeze at all, like this:

[1] One can also use a similar technique for `e1 || e2`. I will mainly use ‘e1 && e2’ as an example in this post for brevity.

[4] I will not explain what undefined behavior is in this post because there are a lot of other great posts that describe it.

[9] Fortunately, the situation is much better now. If you report that a transformation is buggy with anAlive2 proof (https://alive2.llvm.org/), it is likely to be fixed. ☺

[12] It is the isGuaranteedNotToBePoison function in ValueTracking.{h,cpp}.'

[27] https://godbolt.org/z/Tq6bdWsT1 - the flag does not attach noundef to load instructions yet.

x \ y	false	true	poison
false	false	false	false
true	false	true	poison
poison	poison	poison	poison