[LLVMdev] how to detect if block N is reachable from block M ?

[Jimborean Alexandra]

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.






________________________________
From: Kenneth Uildriks <kennethuil at gmail.com>
To: Eli Friedman <eli.friedman at gmail.com>
Cc: Jimborean Alexandra <xinfinity_a at yahoo.com>; llvmdev at cs.uiuc.edu
Sent: Thu, March 31, 2011 3:12:59 PM
Subject: Re: [LLVMdev] how to detect if block N is reachable from block M ?

On Wed, Mar 30, 2011 at 11:35 PM, Eli Friedman <eli.friedman at gmail.com> wrote:
> On Wed, Mar 30, 2011 at 10:14 AM, Jimborean Alexandra
> <xinfinity_a at yahoo.com> wrote:
>> 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.
>
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110331/f8367c46/attachment.html>