<html><head><style type="text/css"><!-- DIV {margin:0px;} --></style></head><body><div style="font-family:arial,helvetica,sans-serif;font-size:10pt"><div>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.<br><br><br></div><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt;"><br><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt;"><font face="Tahoma" size="2"><hr size="1"><b><span style="font-weight: bold;">From:</span></b> Kenneth Uildriks <kennethuil@gmail.com><br><b><span style="font-weight: bold;">To:</span></b> Eli Friedman <eli.friedman@gmail.com><br><b><span style="font-weight: bold;">Cc:</span></b> Jimborean Alexandra <xinfinity_a@yahoo.com>; llvmdev@cs.uiuc.edu<br><b><span style="font-weight:
bold;">Sent:</span></b> Thu, March 31, 2011 3:12:59 PM<br><b><span style="font-weight: bold;">Subject:</span></b> Re: [LLVMdev] how to detect if block N is reachable from block M ?<br></font><br>
On Wed, Mar 30, 2011 at 11:35 PM, Eli Friedman <<a ymailto="mailto:eli.friedman@gmail.com" href="mailto:eli.friedman@gmail.com">eli.friedman@gmail.com</a>> wrote:<br>> On Wed, Mar 30, 2011 at 10:14 AM, Jimborean Alexandra<br>> <<a ymailto="mailto:xinfinity_a@yahoo.com" href="mailto:xinfinity_a@yahoo.com">xinfinity_a@yahoo.com</a>> wrote:<br>>> Hi,<br>>><br>>> Is there any method to check if there is a path in the CFG from block M to<br>>> block N, but M does not necessarily dominate block N?<br>>> In other words, if N is reachable from M.<br>><br>> I don't think there's any method built in to LLVM. It's pretty easy<br>> to write, though.<br>><br>> -Eli<br>A simple depth-first or breadth-first search is good unless you end up<br>querying all pairs - each query is O(blocks + edges), and the number<br>of pairs is O(blocks ^ 2). If you need to answer queries such as "all<br>blocks
reachable from X", especially using several X's in the course<br>of an analysis, you'll want more sophisticated algorithms. I found a<br>quick comparison of several algorithms at<br><span><a target="_blank" href="http://www.seas.upenn.edu/%7Emengmeng/presentations/reachability.pdf">http://www.seas.upenn.edu/~mengmeng/presentations/reachability.pdf</a></span><br></div></div>
</div></body></html>