# Advanced Topics in Redundant Load Elimination with a Focus on PHI Translation

DevFeed: [Advanced Topics in Redundant Load Elimination with a Focus on PHI Translation](<https://devfeed.tech/articles/advanced-topics-in-redundant-load-elimination-with-a-focus-on-phi-translation-42835.md>)

Original publisher: [Read original article](<https://blog.llvm.org/2009/12/advanced-topics-in-redundant-load.html>)

Author: Chris Lattner

Published: 2009-12-19T14:45:00Z

Content type: article

Language: en

Sources: [LLVM Project](<https://devfeed.tech/sources/the-llvm-project-blog.md>)

Topics: [LLVM](<https://devfeed.tech/topics/llvm.md>), [Optimization](<https://devfeed.tech/topics/optimization.md>), [C](<https://devfeed.tech/topics/c.md>), [Code](<https://devfeed.tech/topics/code.md>), [implementation](<https://devfeed.tech/topics/implementation.md>)

Tags: [c](<https://devfeed.tech/tags/c.md>), [code](<https://devfeed.tech/tags/code.md>), [implementation](<https://devfeed.tech/tags/implementation.md>), [llvm](<https://devfeed.tech/tags/llvm.md>), [new-in-llvm-2-7](<https://devfeed.tech/tags/new-in-llvm-2-7.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [optimize](<https://devfeed.tech/tags/optimize.md>)

## AI overview

This article explains PHI translation in LLVM's global value numbering and redundant load elimination. It describes why PHI translation is required for correctness and how LLVM 2.7 uses it to analyze predecessor blocks and eliminate redundant loads.

## Source excerpt

In our previous post on GVN we introduced some basics of load elimination. This post describes some advanced topics and focuses on PHI translation: what it is, why it is important, shows some nice things it can do, and describes the implementation in LLVM. What is PHI Translation All About? When performing redundancy elimination on SSA form, PHI translation is required when we are walking through the CFG and the value being analyzed has an operand defined in the block we're walking through. In the case of load elimination, the operand of the value being analyzed is the pointer we're loading from. This means that PHI translation happens when the pointer we're loading is defined in a block. For example, consider this C code: if (...) { *A = 5; P = A; } else { *B = 9; P = B; } use(*P); This compiles into LLVM IR that looks like this: BB1: store i32 5, i32* %A br label %Merge BB2: store i32 9, i32* %B br label %Merge Merge: %P = phi i32* [%A, %BB1], [%B, %BB2] %Y = load i32 *%P ... ... use %Y ... In this example, GVN starts looking at the %Y load to see if it can eliminate it. It scans backwards up the block, looking for other things that provide the value of the memory address at %P. Unlike in the example in the previous post, here we actually find a definition of %P: what do we do? In LLVM 2.6 and before, memory dependence analysis would just give up and act as though the memory had been clobbered, preventing the load from being analyzed further (and eventually being eliminated in this case). New in LLVM 2.7, GVN is able to translate %P into each predecessor. In this case, it sees that %P has the value of %A in %BB1 (and then sees that %A is available there) and that %P has the value of %B in %BB2 (where it is also available). This allows GVN to optimize this example into: BB1: store i32 5, i32* %A br label %Merge BB2: store i32 9, i32* %B br label %Merge Merge: %Y = phi i32 [5, %BB1], [9, %BB2] %P = phi i32* [%A, %BB1], [%B, %BB2] ... ... use %Y ... which eliminates