LLVM: Constraint Elimination Pass

2025-04-14

Introduction

Constraint Elimination is a transformation pass that extracts facts from LLVM IR and tries to replace certain uses with known facts. One common replacement is to replace conditional comparisons with constants (true or false) when known. The following is a simple example of how Constraint Elimination works.

 1int foo(int x, int y) {
 2  if (x > y) {    // x > y is a known fact in this block
 3    if (x <= y) { // replace x <= y with false
 4      return 2;
 5    } 
 6    return 1;
 7  } 
 8  
 9  return 0;
10}
11
12// after constraint elimination
13int foo(int x, int y) {
14  if (x > y) {
15    if (false) { // block can be removed
16      return 2;
17    }
18    return 1;
19  } 
20  
21  return 0;
22}

The logic behind Constraint Elimination relies on an analysis pass called the Constraint System. Constraint Elimination stores known facts inside two constraint systems (signed and unsigned) and asks the constraint system if it’s okay to replace uses.

Constraint System

The Constraint System stores known facts in the following form (c0 is constant, c1 to cn are coefficients, v1 to vn are variables):

c0 <= c1 * v1 + c2 * v2 … + cn * vn

For instance, constraint x >= 0 will be decomposed into 0 <= 1 * x and constraint y >= 0 will be decomposed into 0 <= 0 * x + 1 * y. These two constraints are true in the constraint system, which implies a logical AND between them, resulting in x >= 0 && y >= 0.

Constraint Elimination will ask the constraint system whether a constraint (A) is implied by adding a negation of the constraint (!A) into the system. Since constraints are combined with logical AND, the system becomes C1 && C2 && ... && Cn && !A. If this is satisfiable (sat), there’s a solution where A is false, so A isn’t implied by the existing constraints. If unsatisfiable (unsat), no solution exists where A is false, meaning A must be true whenever the existing constraints hold. For example, with constraints A && B, checking A by adding !A gives A && B && !A, which is unsat (a contradiction). Thus, A is implied and can be safely replaced with true in the ConstraintElimination pass.

Now that we understand how constraints are handled, let’s dive into the core of the Constraint Elimination pass.

Constraint Elimination

The Constraint Elimination pass works roughly as follows:

Perform a Depth-First search the dominator tree and add entries to a worklist for every basic block. An entry can be a Fact to be added or a Check that needs to check if it can be replaced.
Sort the worklist by dominance information from the dominator tree.
Process sorted worklist and replace implied conditions.
Remove instructions with no uses inside the function.

Constraint Elimination begins by traversing the entry block and iterates over every instruction. If there’s a comparison instruction icmp, it adds an entry UseCheck into the worklist to check if it can be replaced later. If the terminator is a conditional branch, it adds corresponding facts to the successor blocks.

1define i1 @src(i4 %x, i4 %y) {
2entry:
3  %c.1 = icmp slt i4 %x, 0
4  br i1 %c.1, label %t, label %f
5t:
6  ...x < 0
7f:
8  ...x >= 0
9}

Branching to block t means that %c.1 is true, where it can safely add x < 0 constraint to block t. On the other hand, it will invert the predicate to x >= 0 and add this constraint to block f. It will traverse to the next basic block and do the same until it traverses every basic block in the dominator tree.

Consider another example: block t is reached if x < 0 || y < 0. However, as mentioned earlier that the current constraint system has an implicit logical AND for every fact, constraint elimination cannot add this fact x < 0 || y < 0 into the constraint system. As for block f, it can add the inverse of predicate x >= 0 && y >= 0 into the constraint system.

 1define i1 @src(i4 %x, i4 %y) {
 2entry:
 3  %c.1 = icmp slt i4 %x, 0
 4  %c.2 = icmp slt i4 %y, 0
 5  %or = or i1 %c.1, %c.2
 6  br i1 %or, label %t, label %f
 7t:
 8  ret i1 false
 9f:
10  %cmp = icmp sge i4 %x, 0
11  ret i1 %cmp
12}

Below is the worklist after traversing all blocks in the function and sorting the worklist. NumIn and NumOut represent the sequence for the Depth-first search. The sorted entries follow these rules NumIn < ConditionFact < Check < InstrBefore, where blocks with lower NumIn values dominate those with higher ones. In the same basic block, condition facts are processed before UseCheck.

1// entry NumIn=0, NumOut=5
2// t     NumIn=1, Numout=2
3// f     NumIn=3, Numout=4
4UseCheck(%c.1, ICMP_SLT, %x, 0, NumIn=0, NumOut=5)
5UseCheck(%c.2, ICMP_SLT, %y, 0, NumIn=0, NumOut=5)
6ConditionFact(DT.getNode(f), ICMP_SGE, %x, 0, NumIn=3, NumOut=4)
7ConditionFact(DT.getNode(f), ICMP_SGE, %y, 0, NumIn=3, NumOut=4)
8UseCheck(%cmp, ICMP_SGE, %x, 0, NumIn=3, NumOut=4)

By processing the above worklist, constraint elimination learns that it can replace %cmp with true in block f (see Alive2 proof — a tool to verify LLVM IR optimizations), and safely remove %cmp = icmp sge i4 %x, 0 instruction.

Missing Cases

As of writing, I have submitted a PR to add optimization opportunities for Constraint Elimination. The pass adds additional facts if the condition being analyzed matches one of the following four patterns.

1# bitwise OR
2(LHS | RHS >= 0) => LHS >= 0 && RHS >= 0
3(LHS | RHS > -1) => LHS >= 0 && RHS >= 0
4# bitwise AND
5(LHS & RHS < 0)   =>  LHS < 0 && RHS < 0
6(LHS & RHS <= -1) =>  LHS < 0 && RHS < 0

This example demonstrates how my PR works. Before my PR, constraint elimination would only add one fact %and.1 < 0 to block then. With the added facts x < 0 && y < 0 in the then block, the pass can replace %t.1 and %t.2 with true.

 1// before
 2define void @src(i4 %x, i4 %y) {
 3entry:
 4  %and.1 = and i4 %y, %x
 5  %c.1= icmp slt i4 %and.1, 0
 6  br i1 %c.1, label %then, label %end
 7
 8then:
 9  ; fact: %and.1 < 0
10  %t.1 = icmp slt i4 %x, 0
11  %t.2 = icmp slt i4 %y, 0
12  call void @use(i1 %t.1)
13  call void @use(i1 %t.2)
14  ret void
15
16end:
17  ret void
18}
19
20// after
21define void @tgt(i4 %x, i4 %y) {
22entry:
23  %and.1 = and i4 %y, %x
24  %c.1= icmp slt i4 %and.1, 0
25  br i1 %c.1, label %then, label %end
26
27then:
28  call void @use(i1 true)
29  call void @use(i1 true)
30  ret void
31
32end:
33  ret void
34}

Measure Replacement Counts

To evaluate the impact of my patch, I measured the number of replacements triggered by the Constraint Elimination pass. My approach is to print log whenever additional facts are added and replacement uses are triggered. This experiment was conducted on two projects, LLVM and Rust.

Building LLVM with UBSan enabled

With UBSan enabled, building LLVM will go through a series of bound checks, firing more Constraint Elimination. The first build has my constraint elimination patch, and I commented out my patch in the second build.

 1# $CC_HOME points to my locally built LLVM
 2cmake -GNinja -DCMAKE_CXX_COMPILER=$CC_HOME/bin/clang++ \
 3  -DCMAKE_C_COMPILER=$CC_HOME/bin/clang \
 4  -DCMAKE_BUILD_TYPE=Release \
 5  -DLLVM_ENABLE_PROJECTS="llvm;clang" \
 6  -DLLVM_CCACHE_BUILD=OFF -DLLVM_BUILD_EXAMPLES=ON \
 7  ../llvm -DLLVM_TARGETS_TO_BUILD=X86 \
 8  -DLLVM_USE_SANITIZER=Undefined
 9
10# without my patch
11ninja -j 12 > without.txt 2>&1
12# with my constraint elimination patch
13ninja -j 12 > with.txt 2>&1

We observed that Constraint Elimination added several new facts while building LLVM.

1# without my patch
2$ cat ce2/without.txt | grep "additional" | wc -l
30
4# with my constraint elimination patch
5$ cat ce2/with.txt | grep "additional" | wc -l
678

We expected that the extra facts could trigger more replacements. However, the total number of replace count is the same.

 1# without my patch
 2$ ./perform.sh ce/without.txt
 31: replace count
 430428
 52: replace count
 6517
 73: replace count
 80
 94: replace count
100
115: replace count
120
136: replace count
147
157: replace count
167
17total replace count
1830959
19
20# with my constraint elimination patch
21$ ./perform.sh ce/with.txt
221: replace count
2330428
242: replace count
25517
263: replace count
270
284: replace count
290
305: replace count
310
326: replace count
337
347: replace count
357
36total replace count
3730959

Building Rust nightly

The result of the first experiment didn’t meet what we expected, so we decided to see the result when compiling Rust.

As of writing, Rust nightly supports LLVM 20.x, so I had to rebuild my patch on top of LLVM 20. Luckily, there were no conflicts when I applied my updates to LLVM 20.x branch.

 1# bootstrap.toml for building rustc
 2change-id = "ignore"
 3
 4[target.x86_64-unknown-linux-gnu]
 5# set external llvm-config to get our locally built LLVM binaries
 6llvm-config = "/home/lee/dev/llvm-project/build/bin/llvm-config"
 7
 8[llvm]
 9download-ci-llvm = false
10link-shared = false
11
12[build]
13extended = true
14# this needs to set to false, or rustc will try to build from in-tree LLVM
15optimized-compiler-builtins = false
16
17[rust]
18channel = "nightly"

Build stage2 rustc and libstd.

1# without my patch
2./x.py build --stage 2 2>&1 | tee without.txt
3# with my constraint elimination patch
4./x.py build --stage 2 2>&1 | tee with.txt

Like we expected, there were additional facts added when compiling rustc.

1$ cat rust-ce/without.txt | grep "additional" | wc -l
20
3$ cat rust-ce/with.txt | grep "additional" | wc -l
4304

Finally, the result is similar to building LLVM. There was no difference in replacement count.

 1# without my patch
 2$ ./perform.sh rust-ce/without.txt
 31: replace count
 4594755
 52: replace count
 657
 73: replace count
 80
 94: replace count
100
115: replace count
120
136: replace count
140
157: replace count
160
17total replace count
18594812
19
20# with my constraint elimination patch
21$ ./perform.sh rust-ce/with.txt
221: replace count
23594755
242: replace count
2557
263: replace count
270
284: replace count
290
305: replace count
310
326: replace count
330
347: replace count
350
36total replace count
37594812

Given that Rust performs many bounds checks, we can observe that it benefits significantly from the Constraint Elimination pass overall.

Despite successfully adding additional facts, the total number of replacements remained unchanged in both LLVM and Rust builds. It’s unclear why this happened. One possible explanation is that these new facts did not intersect with any existing icmp checks eligible for replacement. Further investigation is needed to understand this behavior.

Future Work

Constraint Elimination is a fun and powerful transformation pass. There are still many missing optimizations that we can contribute. As we mentioned earlier, the current constraint system supports only logical AND for its constraints. This limitation prevents the system from learning facts expressed as Fact1 || Fact2. Supporting logical OR opens many optimization opportunities, such as (LHS | RHS) < 0 => LHS < 0 || RHS < 0.

Currently, ne constraints are not supported in the constraint system. The reason is that a != b cannot be directly encoded as a single linear constraint — it represents a disjunction: a < b || a > b. However, the constraint system models all facts as conjunctions (logical ANDs) of linear inequalities. Without support for logical OR, it is not possible to store ne facts within the system. In contrast, eq facts like a == b can be represented as two inequalities: a <= b && a >= b, both of which are individually expressible.

Conclusion

I only worked on a certain part of the Constraint Elimination pass. There is still more to discover inside this pass, such as, adding facts for loop induction variables. Lastly, I want to express my gratitude to Dr. John Regehr for his valuable advice on this project. Thanks, John!