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