[LLVMdev] Inter-procedural program flow analysis

[Bjorn De Sutter]

Hi Stephen,

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. 

Consider

main(){
   X;
   if (...) {
       f();
       g();
    } else {
      g();
      f();
   }
   Y;
}

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. 

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: http://users.elis.ugent.be/~brdsutte/research/publications/selected.html#whole-program

An implementation of this algorithm can be obtained from the Diablo link-time rewriter, which is available through diablo.elis.ugent.be

I wish you a lot of success if you want to re-implement it in LLVM. That would be great!

Best,

Bjorn De Sutter
Computer Systems Lab
Ghent University




On 03 Oct 2012, at 02:18, Stephen Schiffli wrote:

> 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.
> 
> Thanks,
> -Stephen
> 
> On Tue, Oct 2, 2012 at 5:06 PM, Scott Moore <sdmoore at fas.harvard.edu> wrote:
> 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.
> 
> 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.
> 
> Cheers,
> Scott
> 
> 
> 
> On Tue, Oct 2, 2012 at 7:43 PM, Jim Grosbach <grosbach at apple.com> wrote:
> 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().
> 
> Jim
> 
> 
> On Oct 2, 2012, at 4:29 PM, Stephen Schiffli <sschiffli at gmail.com> wrote:
> 
>> 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:
>> 
>> 
>> 
>> extern int x;
>> 
>> void foo() { }
>> 
>> int main() {
>> 
>>             if (x) {
>> 
>>                         foo();
>> 
>>             } else {
>> 
>>                         foo();
>> 
>> }
>> 
>> }
>> 
>>  
>> 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.
>> 
>> 
>> 
>> Thanks,
>> 
>> -Stephen
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121003/0f96f5c4/attachment.html>