Looking for a Reaching Definition Analysis


I am a newbie to LLVM as well as compilers and I am hoping for some direction in finding an instance of where a Reaching Definition Analysis is being implemented within LLVM. I have referenced the sources files, initially hoping to find an explicit ReachingDefinitionAnalysis.cpp file :wink: but with no such luck. Other than that I have found the files SimpleRegisterCoalescing.cpp and the PreAllocSplitting.cpp which are referencing Reaching Definitions (as VNInfo objects), which leads me to believe that Reaching Definitions are created as part of the LiveIntervalAnalysis, which is a MachineFunctionPass. However, I was expecting to find a implementation of RD Analysis earlier on. I will continue walking though LiveIntervalAnalysis and the rest of the code, but was looking for some direction here if possible.

Thanks in advance!

Shone Sadler

The immediate uses info provides reaching definitions already, at
least while the code is in SSA form.
So uh, what more are you looking for?

Thanks for the response. I was more specifically looking through the source code for a place where Reaching Definitions was implemented to derive those uses and/or to generate the SSA. To provide some context, as a student I have a project to implement a path infeasibility algorithm to “Sharpen” the results of the Reaching Definitions results in LLVM. Being new to LLVM I wasn’t looking for the answer for the latter, but was looking for some pointers on how the current “Reaching Definitions” was implemented and where (or where the “uses” were otherwise built up).


mem2reg (llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp)
transforms to SSA form, but that's the conventional SSA construction
algorithm, which doesn't really use reaching definitions. The closest
thing to what you're looking for is probably memdep


Great! Both are good reference points. Thanks for the help!