Building a Loop Invariant Code Motion (LICM) Pass in LLVM

A walkthrough of writing a custom LICM pass using the new pass manager - what it does, how it works, and how to verify it.

Before we go into what Loop Invariant Code Motion (LICM) is and what it solves, we first need to understand the problem that we are facing. Lets understand this with an example program.

Here we can clearly see that the value of “x” never changes inside the loop. So x*4 produces the same value for every single iteration. 1,2,3…..all the way to 1,000,000. We are multiplying the same two numbers a million times and then not using 999,999 of the answers.

The CPU doesn’t know this, it just executes the instructions that we give. It has no notion of “I already computed this”.

The fix is obvious once you see it :

Moving the computation of “t” outside of the loop. Same result just 999,999 fewer multiplications. For a million iterations of a tight loop this is a meaningful speedup. That’s what the entire project is about, teaching the compiler to do this transformation automatically.

What does a compiler actually do ? (the IR Layer)

Whenever we write C code, the CPU executes machine code (raw binary instruction). Between these two things, compilers have an intermediate layer called IR short for Intermediate Representation. LLVM’s IR is a textual format that is present in .ll files.

Now the reason IR exist is because transformations like LICM are much easier to do on IR that on C source code (too high-level, too many syntactic complications) or on machine code (too low-level, architecture specific). IR sits at the perfect space which is abstract enough to reason about, concrete enough to optimize.

If you wanna see the IR yourself for the above code run the below command :

Static Single Assignment (SSA)

Before we dive into the complexities its important to understand SSA and what it does.

The rule is simple : every variable is defined exactly once, in exactly one place in the code. New values are represented as new variables.

In normal C code, this is constantly violated :

In SSA form (which is what LLVM IR is), this become :

Every new value gets a new name, and its value are permanently bonded i.e “%x1” will always mean 5 not something else. This concept is gonna be useful in our LICM pass.

Def-Use chain

This is also one of the important concepts that will help us in the future. Lets us understand this with a proper example.

Consider this C code below :

In LLVM IR, this becomes :

Now forget about loops for a second. Just focus on these two instructions and how LLVM remembers them internally.

In LLVM every instruction is a Value object. That means %t is a Value, %res is a Value and %x is a Value. Even the constant 4 is a value.

Now Every single Value object in LLVM holds two things :

This isn’t something that we have to do, LLVM maintains this automatically for us at all times, for every Value in our IR.

The first is its definition, the one instruction that produced it. For “%t” that’s the mul instruction. For “%x” that’s whatever instruction outside the loop created it.

The second is its users list, every instruction that consumes this value as an input. For “%t” that’s the add instruction that uses it. For “%x” that’s the mul instruction.

These two pieces of information together form what’s called the def-use chain. You can traverse it in either direction.

The two directions of traversal

Backward direction : From an instruction, to its inputs, to where those inputs were defined. You call I.operands() to walk this direction. You’re basically asking “where did my inputs come from?”

Forward direction : From a definition, to everything that consumes it. You call I.users() to walk this direction. You’re asking “who depends on my result?”

Our invariance check uses the use-def direction backwards.

Basic Block in IR

IR is not organised as a flat list of instructions. It’s organised into basic blocks. A basic block is actually a sequence of instructions with one strict rule: execution enters at the top and exits at the bottom. There are no branches in the middle.

Every basic block ends with exactly one terminator instruction it could either be a branch (br), a return (ret), or a switch. The terminator says “after this block, go to block X, or go to block Y depending on a condition.”

All the basic blocks are connected through terminators. Basically one block’s terminator points to other blocks as successors. These connections for a graph called Control Flow Graph (CFG).

How do loops look like in CFG ?

A loop in IR is just a cycle in the CFG, a path from some block back to a block you’ve already visited. The specific structure that LLVM recognises is called a natural loop and it has 3 parts (Entry block, Header block, and Body block) :

The header block :

The single entry point of the loop. Every time the loop starts (or restarts after an iteration), execution enters through this one block. This is where the loop condition is typically checked (i < n).

The back edge :

An edge in the CFG that goes from a block inside the loop back to the header. This is what makes it a loop a cycle. At the end of each iteration, execution follows the back edge back to the header to check the condition again.

The body blocks :

These are all the blocks that are “inside” the loop, reachable from the header via the back edge. For a simple loop this might be just one block. For a complex loop with if-statements inside, there could be many.

Visually a simple loop looks like :

Now in LLVM, LoopInfo analysis automatically finds all of these structures. If you want to ask “what loops exist in this function?” It will hand you Loop* objects with methods like L->getHeader(), L->getBlocks(), L->getExitBlocks(), L->contains(BB).

Okay Now we know that the compiler turns this into IR and breaks it into three separate blocks :

Notice that the loop header has two different kind of predecessors arriving to it.

Now the actual problem that our pass needs to solve

We have identified that the computation %t = mul i32 %x, 4 as loop-invariant. So we wanna move it someplace else where it is executed only once. Where ?

Option A : Put it in the entry block. That might work for this simple case, but the entry block could be doing a hundred other things. More importantly, there could be multiple loops in the function, each needing their own hoisted instructions. Dumping everything into entry will definitely create problems in the long run.

Option B : Put it at the top of loop.header. This seems natural. The header is the first thing that runs before the body. But if we look at the diagram again, the header runs on every iteration, not just once. The back edge from loop.body goes back to the header. So if you put the instruction in the header, it still executes a million times.

Option C : Create a new dedicated block that sits between entry and the header. The pre-header is a basically a brand new block that you insert between entry and the header. The thing is the back edge still goes to the header and not to this new block. So the new block only gets executed once, when entry jumps to it at the very beginning.

Now look at this in actual IR

Before our pass :

After our pass :

Couple to things to notice in the updated IR :

• %t = mul i32 %x, 4 is moved from loop.body to loop.preheader. It now runs only once.

• The back edge br label %loop.header at the bottom of loop.body is still unchanged. It still goes to the header and back edge completely skips the preheader which is good since it will not recompute the values.

• %t is still used in loop.body with %res = add i32 %val, %t. This works because the preheader runs before the loop starts, so %t is already defined by the time any iteration uses it. SSA def-use chains remain valid, uses still reference %t, and %t is now defined in the preheader which runs before everything.

Why the two-predecessors problem matters

Here’s the specific thing that makes the pre-header necessary. Look at loop.header in the before case. It has two predecessors. The PHI node at the top of the header exists because of this:

%i = phi i32 [ 0, %entry ], [ %i.next, %loop.body ]

This PHI node says: if I arrived from %entry, then %i = 0. If I arrived from %loop.body, then %i = %i.next. The header has two predecessors, so values that flow into it need a PHI node to merge them.

Now imagine you put your hoisted instruction %t = mul %x, 4 directly in the header, above the PHI nodes. It would again execute every time the header runs: once from entry, and once again every time the back edge fires. Million iterations = million multiplications. Nothing gained.

The preheader solves this by being a block that only entry can reach. No back edge. No PHI node is needed. It executes once, produces %t, and the loop body uses it forever.

Writing the LICM pass

Now that we have an understanding of all the things that are happening conceptually, lets dive to into actually writing the pass.

Implementation-wise, LLVM LICM boils down to 3 phases:

1. Detect loops → using LoopAnalysis

2. Find invariant instructions → isInvariant()

3. Check safety + hoist → move to preheader

Let us start with the “run” function :

This run() function is essentially your control center of the LICM pass. This is the entry point of our pass, and LLVM calls it once for every function and expect it to transform if needed.

The run() function takes in two arguments :

1. Function &F : This is the function our pass is working on.

2. FunctionAnalysisManager &AM : This is how we can access the precomputed analyses. Instead of recomputing things like loops or dominance, you just ask:

• auto &LI = AM.getResult<LoopAnalysis>(F);

• auto &DT = AM.getResult<DominatorTreeAnalysis>(F);

• auto &AA = AM.getResult<AAManager>(F);

LoopAnalysis → LI

• All loops in the function

• Structure of loops

• Blocks inside loops

Without this → you can’t even detect loops

---

DominatorTreeAnalysis → DT

• Which blocks dominate others

Used for:

• Safety check (does instruction always execute?)

---

AAManager → AA

• Alias analysis

Used for:

• Memory safety (do two pointers refer to same memory?)

Then we are using a variable called “changed” to know if we have modified the IR or not.

Using LI.getLoopsInPreorder() function we get all the list of loops ordered as [Outer, Inner]. But we need to process the inner loops first so we just reverse the order of iteration using “loops.rbegin()” and “loops.rend()”.

At the end you might see “PreservedAnalyses::none()” and “PreservedAnalyses::all()”. See whenever LLVM computes this like Loop structure, Dominance and Alias info which are expensive computations, so LLVM caches them and resuses them across passes.

So the problme is, when our pass changes the IR, it can break previously computed analyses. So LLVM asks us “Did we change anything that might invalidate analyses?”

Case 1 : We changed the IR so return PreservedAnalyses::none() which means we have modified the program, don’t trust any old analysis.

Case 2 : No changes so return PreservedAnalyses::all() which means we didn’t touch anything, everything is still valid.

Moving on to the “processLoop()” function :

Now this is our core optimization engine which takes a single loop, finds invariant + safe instructions, and moves them to the loop preheader.

The arguments that we are providing to the processLoop() function are :

• Loop *L → the loop to optimize

• DominatorTree &DT → for safety (execution guarantee)

• LoopInfo &LI → needed for CFG updates (preheader creation)

• AAResults &AA → for memory safety

The high level workflow is gonna be something like this :

1. Get/Create preheader

2. Scan loop → find candidates

3. Store candidates

4. Move them outside loop

Firstly we get the preheader for the given loop and if it doesn’t exist then we will create it using :

**preheader = InsertPreheaderForLoop(L, &DT, &LI, nullptr, false);

This transforms our CFG :

Before: entry → loop.header

After: entry → preheader → loop.header

This makes LICM possible, because without this preheader, hoisting has no safe destination.

Then create storage for candidates :

std::vector<Instruction *> toHoist;

We are storing first because never modify the IR while iterating it.

Then Itearate over every block in loop and then over each Instruction. Inside those loops we have to check two things :

1. isInvariant() - Does it depend on loop ?

2. isSafeToHoist() - meaning it has no side effects, no aliasing

If these checks satisfy then push the instruction into the toHoist vector that we created for storage.

Hoisting Phase :

for (Instruction *I : toHoist){
	I->moveBefore(preheader->getTerminator());
}

This basically moves the instructions from the loop body to the preheader.

Lets move on to the isInvariant() and isSafeToHoist() functions

LICM has two filters :

1. Invariant? → Does value change across iterations?

2. Safe? → Will moving it break the program?

If both are true then we hoist.

1. isInvariant() :

Checks whether the instruction produces the same value every iteration or not. An instruction is invariant if all its inputs are defined outside the loop

1. Firstly skip the instruction if it is PHINode since PHI nodes represent changing values.

2. Then Iterate over the operands and check where each operand is defined.

if (auto *defInst = dyn_cast<Instruction>(op))

3. Check if those are inside the loop, and if they are inside the loop return false. Since operands computed inside the loop may change each iteration.

4. If all operands pass then return true.

2. isSafeToHoist() :

This basically makes sure that the instruction does not change program behaviour.

Now this function is just asking us “If I move this instruction out the loop, will the program still behave the same?”

To check this we have 3 conditions that it has to follow :

1. No side effects

2. Memory should be safe

3. It always executes anyway

Side Effect check :

This check basically tells to reject anything that writes to memory, calls functions or changes state.

Memory Safety (alias analysis) :

Lets understand with a simple example first.

Loads read memory:

t = *ptr;

But what if inside loop:

*ptr = i;

Then value of *ptr changes each iteration.

So our code basically iterates over the load and store instruction and checks if they have the same memory location or not.

if (auto *loadInst =dyn_cast<LoadInst>(&I))

Only check loads

---

Scan entire loop

for (BasicBlock *BB :L->getBlocks()) {
for (Instruction &other : *BB) {

Look at ALL instructions in loop

---

Find stores

if (auto *storeInst =dyn_cast<StoreInst>(&other))

---

Check alias

Basically means do these two pointers refer to the same memory?

AliasResultresult =AA.alias(
	loadInst->getPointerOperand(),
	storeInst->getPointerOperand()
);

---

Dominance Check :

The reason we are checking this is because of one problem, lets understand it using an example :

for (...) {
    if (i % 2 == 0) {
        t = x * 4;
    }
}

Here we can see “t” only runs sometimes and If hoisted :

t = x * 4;
for (...) {
    if (...) { }
}

Now it runs every time which is not good.

So what we are doing is getting all the exit points of an instruction :

SmallVector<BasicBlock *, 4> exitBlocks;
L->getExitBlocks(exitBlocks);

and then checking that instruction must dominate ALL exit blocks, or in other words the instruction must execute on every path through the loop. If not that means its conditional and it cannot be hoisted.

This implementation is intentionally conservative. It avoids unsafe transformations, but it also misses some opportunities that a production compiler like LLVM would handle. Real-world LICM includes more advanced techniques such as:

• Handling chains of dependent invariant instructions

• Speculative execution checks

• More precise memory analysis (like MemorySSA)

That said, the goal here was not to replicate LLVM’s full complexity, but to understand the core idea deeply enough to build it ourselves.

The full implementation is on GitHub - feel free to explore or build on top of it.

I’m still learning LLVM myself, so if you spot anything off or have suggestions, I’d love to hear them. This is as much a learning log as it is a tutorial.