[LLVMdev] Inter-procedural program flow analysis

[Stephen Schiffli]

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
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121002/0ab14c4a/attachment.html>