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/fb708f90/attachment.html>
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>
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>