Hi,

Is there any method to check if there is a path in the CFG from block M to block N, but M does not necessarily dominate block N?

In other words, if N is reachable from M.

Thanks,

Alexandra

Hi,

Is there any method to check if there is a path in the CFG from block M to block N, but M does not necessarily dominate block N?

In other words, if N is reachable from M.

Thanks,

Alexandra

I don't think there's any method built in to LLVM. It's pretty easy

to write, though.

-Eli

A simple depth-first or breadth-first search is good unless you end up

querying all pairs - each query is O(blocks + edges), and the number

of pairs is O(blocks ^ 2). If you need to answer queries such as "all

blocks reachable from X", especially using several X's in the course

of an analysis, you'll want more sophisticated algorithms. I found a

quick comparison of several algorithms at

http://www.seas.upenn.edu/~mengmeng/presentations/reachability.pdf

Thank you, I have already implemented the simple depth first search and I will check if there are any significant performance related problems. In which case I will go for a more complex algorithm, like the ones presented in the paper you suggest.