[LLVMdev] How to decide whether a function is executed or not

[RICHARD STUCKEY]

Hello,

I should think that it is undecidable: it looks like a variant of the
Halting Problem.

Consider a function which contains an infinite loop: any algorithm which
could determine whether that function is called or not would effectively be
an algorithm that could determine whether the program containing that
function halts or not.  Equally, deciding whether the function contains an
infinite loop or not is itself an instance of the Halting Problem.

    Richard


On 20 May 2014 15:19, lyh.kernel <lyh.kernel at gmail.com> wrote:

> Hello everyone,
>
> I want to decide whether a function is executed or not. For example (the
> value of
> cond is not determined at compile time):
>
> br i1 %cond, label %if, label %else
>
> if:
>   ...
>   call void f()
>   ...
>   br label %exit
>
> else:
>   ...
>   br label %exit
>
> We could say that function f is control dependent on cond and may not be
> executed.
>
> On the other hand:
>
> br i1 %cond, label %if, label %else
>
> if:
>   ...
>   call void f()
>   ...
>   br label %exit
>
> else:
>   ...
>   call void f()
>   ...
>   br label %exit
>
> No matter the value of cond is, function f would be executed.
>
> I am wondering whether there exist any algorithm to decide whether
> function f is
> executed or not. Any suggestion or key word are appreciated.
>
> Many thanks
>
> _______________________________________________
> 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/20140520/b74fd90b/attachment.html>