UD and DU chains for LLVM IR before running mem2reg


Just had a simple question ,

The use-def and def-use chains provided by llvm::Value class ,

would they work for IR that has not been optimized by the “mem2reg” pass ?

( ie, IR code that contains memory interactions and is not in SSA form yet )



It depends on what you mean by ‘work’. They will exist and will link instructions, but all loads and stores to an alloca will appear as uses of that alloca.


This is nontrivial (if it were easy, we wouldn’t bother with SSA form), because it depends on the CFG. There may not even be a single most recent store. For example, consider the following code:

int x;
if (y == 0)
  x = 1;
  x = 2;

At the call to foo(x), what is the most recent store to x? It depends on which path through the CFG was taken: it’s either x=1 or x=2. If you perform SSA construction, then you will end up with a phi node[1] and an SSA register rather than stores to an alloca for x.

The real question is why do you want to avoid using the mechanisms that are explicitly designed to solve these problems? Do they not work for something in your language?


[1] Actually, in this example, you’ll end up with a select instruction, but ignore that for now.

Hi David,

Thanks for your reply , I am aware of those issues.
( my issue is quite complex - monomorphization for iN types at runtime )

This shouldn’t preclude performing SSA construction.

However, I have a simpler question -

Do the "alloca" instructions need to be at the top always ?
and do they need to be in reverse order ( reverse order of parameters and then reverse order of variable declarations ?)

No, with two caveats:

- mem2reg / SROA will only work reliably with allocas in the entry block

- Alloca instructions will allocate stack space whenever they are reached: if you accidentally put one in a loop then you can end up increasing your stack size considerably (if you actually dynamic allocations dependent on control flow, you are advised to look at the stack save and restore intrinsics).