CODEWITHSUNDEEP
algorithmcompiler-constructionllvm
Thomas U.
Thomas U.

Reputation: 31

Algorithms to backtrack the usage and dependencies of a variable

I'm extending LLVM for experiments. Therefore, I want to track a variable usage and its dependencies.

For example after finding a conditional branch which is caused by a comparison of two operands, I want to backtrack all usages of that variable and determine all its dependencies (which variables are used to compute the operand of the condition). For me, this seems some kind of recursive backtrack operation.

Are there any special algorithms specialized for that problem?

Upvotes: 2

Views: 107

Answers (1)

Ira Baxter
Ira Baxter

Reputation: 95410

What you want are called "reaching definitions". These are assignments (or side effects) to variables whose value "reaches" the statement or expression of interest.

See https://en.wikipedia.org/wiki/Reaching_definition for more discussion and algorithms on how to compute them (as well as any classic compiler textbook).

I'd expect LLVM to have some built-in machinery to help compute this. I'm not an LLVM expert so I could be wrong.

Upvotes: 2

Related Questions