Dead Code Elimination Pass

A beginner's guide to compiler optimization with LLVM

What exactly is Dead Code Elimination (DCE) ?

Its a compiler optimization that removes code that does not affect the final output of a program. Any line of code in a codebase that isn’t being used is removed using DCE pass.

For Example :

int main() {

  int x = 10; //dead code

  return 5;
}

Here we can clearly see that the variable “x” doesn’t affect the final output of the program, hence that piece of code will be removed by the compiler.

Note: Not all unused-looking code can be removed. Instructions that have side effects (such as memory writes or function calls) must be preserved.

---

Why is there a need for this ?

Now we know that CPU executes instructions one by one. Therefore having fewer instructions helps the CPU complete the tasks faster and in less time. Generally, fewer instructions means less work for the CPU. Let’s understand this in more detail :

Example

int main() {
	int x = 10; // unused
	int y = 20; // unused
	return 5;
}

As you can see here we are not using the variables “x” and “y” and since we didn’t remove those lines of code, the compiler will generate instructions for them.

load 10 into register
store into x
load 20 into register
store into y
return 5

While individual load/store operations may seem small in isolation, redundant instructions still increase total execution time and memory traffic.

More instructions = more cycles

---

Now since we know what and why of DCE let us understand where does DCE actually happen.

High-Level View : What is actually happening and where ?

When we usually write any C++ program, the computer doesn’t understand the C++ code directly. This is where the compiler comes into play.

The compiler works in stages :

Your C++ code
      ↓
Convert to an intermediate form (IR)
      ↓
Optimize the IR (DCE happens here)
      ↓
Convert to machine code

The compiler simplifies your code into a standard internal form called the Intermediate Representation (IR) so it can analyze and optimize it easily.

Now you might get a doubt that why aren’t we directly optimizing the C++ code that we have.

The reason for that it is :

• complex

• ambiguous

• high-level

This could involve operator precedence, function calls, and overloads which would become very hard to optimize reliably.

---

So now let us try to understand what is LLVM IR and how is it actually helps us optimize.

LLVM IR is like a low-level, simplified version of your program.

Example :

C++:

int main() {
   int x = 5 + 10;
   return 0;
}

---

LLVM IR:

%1 = add i32 5, 10
ret i32 0

• Here %1 represents a temporary variable

• add i32 5, 10 computes 5 + 10

• ret i32 0 return 0

Here “i32” basically denotes that it is a 32 bit integer.

IR is the perfect place for DCE because of the following reasons:

In IR:

%1 = add i32 5, 10

1. Everything is explicit:

   • Everything is clearly defined

   • no hidden behaviour

2. Data flow is clear :

   You can easily track:

   • where a value is used

   • where it is not

3. Language-Independent

   Same DCE works for:

   • C++

   • Rust

   • Swift

   Because all become LLVM IR

4. Easier than machine code :

   Machine code is:

   • too low-level

   • tied to hardware

   IR is:

perfect balance between abstraction and control

Write your own DCE Pass

Now we have enough back story and we can move on to actually write a proper DCE pass.

Our project setup will look like this :

We start by creating a simple project structure :

DCEPass/
├── test.cpp       ← Input C++ program
├── test.ll        ← LLVM IR (generated)
├── DCEPass.cpp    ← Our custom optimization pass
├── CMakeLists.txt ← Build configuration
└── build/         ← Compiled plugin

---

1. Writing the Input Program (test.cpp)

Here

• x is never used

• So everything related to x is dead code

2. Converting C++ → LLVM IR

Now we know Computers don’t optimize C++ directly. They optimize an intermediate form called LLVM IR.

We generate IR using:

clang -S -emit-llvm -O0 test.cpp -o test.ll

Type this in the terminal and a “test.ll” file will be generated.

3. Understanding the IR (test.ll)

• alloca → allocate memory (like variables)

• store → assign values

• ret → return

Problem that we are trying to solve:

• %1, %2, and their stores are never used

• This is exactly what DCE should remove

---

4. Writing the DCE Pass (DCEPass.cpp)

Before we dive into the Pass, we have to understand what a basic block is. A Basic block is a straight-line sequence of instructions with one entry and exit point and no jumps in between.

Now we have to write our core logic which basically removes instructions that :

• have no users

• are not control flow

• have no side effects

Here the function traverses over all the Basic Blocks present in the IR. Inside each basic block it iterates on the instructions. We have to check these instructions and see if they affect our final output or not. If they don’t we simply delete them.

One important thing to note is that we are incrementing the iterator before we delete the instruction to safely perform the check and to not get a segmentation fault.

Some Important functions used here are :

I.use_empty()

No instruction is using this value → safe to delete

This means the result produced by this instruction is never used anywhere else in the program.

---

I.isTerminator()

Do NOT delete return/branch instructions.

These instructions control the flow of the program, so removing them would break execution.

---

I.mayHaveSideEffects()

Do NOT delete:
- stores
- function calls

Even if their result is unused, they still affect program state (like modifying memory or printing something.

5. Building the Pass

We use CMake to compile our pass into a plugin:

cmake -S .-B build
cmake --build build

Output:

build/libDCEPass.dylib

6. Running the Pass

We run our pass using LLVM’s opt tool:

opt -S -load-pass-plugin ./build/libDCEPass.dylib \\
-passes="dce-pass" test.ll -o out.ll

This makes an out.ll file which removes the unwanted stores that we saw earlier in the test.ll file

In practice, DCE is often applied repeatedly, because removing one instruction can make other instructions dead.

A quick note : modern compilers like Clang/GCC already do this automatically when you compile with -O1 or higher. You don’t need to write this pass to get DCE in production. The goal here was to understand what’s happening under the hood, stripping away the magic and seeing exactly how the compiler identifies and removes dead instructions at the IR level. Think of it as reading the compiler’s source code, but from scratch.

If you’d like to dive deeper and experiment with the implementation yourself, I’ve uploaded the complete code for this DCE pass on GitHub.

GitHub Repo : https://github.com/Sajid-Zubair/DCEPass