<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hi Stephen,<div><br></div><div>I investigated interprocedural dominators some years ago. One important thing to consider if you want to implement this is that interprocedural (post)dominators do not form a (post)dominator tree. </div><div><br></div><div>Consider</div><div><br></div><div>main(){</div><div> X;</div><div> if (...) {</div><div> f();</div><div> g();</div><div> } else {</div><div> g();</div><div> f();</div><div> }</div><div> Y;</div><div>}</div><div><br></div><div>In this program, Y postdominates the entry and exit blocks of procedures g and f, which in turn postdominate X. But the blocks in f and g do not postdominate each other. So the postdominance relation is a graph, not a tree. </div><div><br></div><div>We have published an efficient algorithm to compute interprocedural dominators in ACM TOPLAS some years ago. You can find it in the ACM Digital Library or on my homepage: <a href="http://users.elis.ugent.be/~brdsutte/research/publications/selected.html#whole-program">http://users.elis.ugent.be/~brdsutte/research/publications/selected.html#whole-program</a></div><div><br></div><div>An implementation of this algorithm can be obtained from the Diablo link-time rewriter, which is available through <a href="http://diablo.elis.ugent.be">diablo.elis.ugent.be</a></div><div><br></div><div>I wish you a lot of success if you want to re-implement it in LLVM. That would be great!</div><div><br></div><div>Best,</div><div><br></div><div><div>
<span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>Bjorn De Sutter</div><div>Computer Systems Lab</div><div>Ghent University</div><div><br></div></div></span></div></span></div></span></div></span><br class="Apple-interchange-newline"></span><br class="Apple-interchange-newline">
</div>
<br><div><div>On 03 Oct 2012, at 02:18, Stephen Schiffli wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">Okay thanks for the info. The term program termination was probably a poor choice of words. I'm really just trying to build an inter-procedural BasicBlock graph, and then look for postdominance as Scott suggested. I'll go about making my own since it doesn't sound like there is one out there already.<div>
<br></div><div>Thanks,</div><div>-Stephen<div><div><br><div class="gmail_quote">On Tue, Oct 2, 2012 at 5:06 PM, Scott Moore <span dir="ltr"><<a href="mailto:sdmoore@fas.harvard.edu" target="_blank">sdmoore@fas.harvard.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>I think you're looking for an inter-procedural post dominator analysis. I don't think there is one in LLVM already, but it should be relatively straightforward.</div>
<div><br></div><div>This gives a sound approximation (i.e. no false positives) of something sort-of equivalent to the halting problem: if the program terminates, then block Y was executed.</div>
<div><br></div>Cheers,<br>Scott<div><div><br>
<br><br><div class="gmail_quote">On Tue, Oct 2, 2012 at 7:43 PM, Jim Grosbach <span dir="ltr"><<a href="mailto:grosbach@apple.com" target="_blank">grosbach@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word">Isn't this effectively the halting problem? Consider the case where block Y is the exit block of main() and block X is the entry block of main().<div><br></div><div>Jim<br><div><br></div>
<div><br><div><div><div>On Oct 2, 2012, at 4:29 PM, Stephen Schiffli <<a href="mailto:sschiffli@gmail.com" target="_blank">sschiffli@gmail.com</a>> wrote:</div></div><div><br><blockquote type="cite"><div>
<div><p class="MsoNormal">Is there any inter-procedural analysis that could tell me if
some BasicBlock Y is guaranteed to execute based on my knowledge that
BasicBlock X will execute? For example:</p><p class="MsoNormal"><br></p><p class="MsoNormal">extern int x;</p><p class="MsoNormal">void foo() { }</p><p class="MsoNormal">int main() {</p><p class="MsoNormal"> if (x) {</p><p class="MsoNormal"> foo();</p><p class="MsoNormal"> } else {</p><p class="MsoNormal"> foo();</p><p class="MsoNormal" style="text-indent:.5in">}</p><p class="MsoNormal">
}</p><div> <br></div><p class="MsoNormal">I want to be told that the entry block of foo is guaranteed
to be executed since I know the entry block of main is guaranteed to be
executed. Basically that all paths from X to program termination go through Y at some point. Please ignore the folding of identical branches and function in-lining, I want to use this type of analysis in the general case.</p><p class="MsoNormal"><br></p><p class="MsoNormal">Thanks,</p><p class="MsoNormal">-Stephen</p></div></div>
_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu/" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></blockquote></div><br></div></div></div></div>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu/" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br>
</div></div></blockquote></div><br>
</div></div></div>
_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></blockquote></div><br></div></body></html>