Live values in LLVM

Question

Suppose I have in my CFG (among others) two basic blocks A and B, with an edge from A to B. I need to do the following:

• get the set S of live values across that edge (it can be an overapproximation, i.e. it might contain values that are not live anymore)
• map each of them to another value (S->S')
• replace - in B and its successors - all the uses of values in S with the mapped values (S')

Does LLVM provide an easy way to do the first and third points (because I can't seem to be able to find it)? If not, do you have any suggestions about how to do it?

note: crossposted on the LLVM mailing list

Answer 1

I do not have clear answer to your question, but director to follow, that came to my mind. I hope it will help you in some way.

First, I would check out "Iterating over the Instructions in a BasicBlock" and "Iterating over def-use & use-def chains" from LLVM Programmers Manual. It gives an idea how to iterate over instructions in basic block and users of this value.

As you need to know living values across the edge, I would check out "Iterating over the BasicBlocks in a Function", and try to determine where users (over ech you iterate) are placed, for example with const BasicBlock* llvm::Instruction::getParent()const.

If information, where users are placed is not enough, you might like to take advantage of [dominators and postdominators analysis], check out :

• LLVM analysis passes like "-domtree""postdom" etc ;
• bool llvm::DominatorTree::dominates (const BasicBlock *A, const BasicBlock *B) const
• bool DominatorTree::dominates (const Instruction *A, const Instruction *B) const

This might help you determine dominance relation between blocks or instructions, what might help you with creation of your sets.