Search code examples
c++graphllvm

Finding the dominating definition location from a use location using llvm

I am trying to find the defining locations that can reach a use location in llvm. For example, I have a CFG that looks like

  a (def)
 / \
b   c (def)
 \ / 
  d (use)

So, both instructions a and c define a value, and at d, we want to use that value. How can I find the locations a and c from d in general using llvm? Can I solve this problem using the dominance tree?

Solution

  • If you are using a good compiler, then the answer is yes. If the answer is no, then run the mem2reg pass first and understand that the result won't be perfect.

    The use at point (d) is a Value. If that value is a PHINode, then get its incoming values and look at them too until you have a set of Values that aren't PHINodes. Those are your definitions.

    This sounds suspiciously simple, doesn't it? It is simple because SSA languages (such as IR) make precisely this kind of job simple. SSA languages can be a pain in several ways, the pain is worth is because the're so great at this kind of thing.