llvm dev - May 2014 - [LLVMdev] How to decide whether a function is executed or not

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

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>

On 20 May 2014 16:08, RICHARD STUCKEY <richard.stuckey at virgin.net>
wrote:
> 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.
A more conservative approach, bailing out on any loops or
complication, would scan the BB flow graph in between any two nodes
(between fully dominating / fully dominated) would return { no, maybe,
yes }. I'd guess that it'd return maybe much more often that yes/no
for the interesting cases, limiting the possibilities of this
approach.

Do you have a concrete use in mind? DCE for the "no" cases? Hoisting
for the "yes" cases? Wouldn't you have to track the arguments as
well?
That can quickly get out of hand...

cheers,
--renato

(sorry for the long post; hopefully you will find it informative)

On Tue, May 20, 2014 at 8:19 AM, 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.
>
There is not. Almost any question that depends on the result of evaluating
"arbitrary code" is undecidable. "undecidable" is a
technical term which
basically means that there is no algorithm that answers the question.
"algorithm" also has a technical meaning in this context which is
basically
a computer program *that is guaranteed to return an answer in all cases*
(the alternative is to keep running forever). If you want to learn more
about this, the keyword is "theory of computation".

Intuitively, this means that there is no general "shortcut" for
understanding the behavior of an arbitrary computer program when it runs:
the only way to know is to actually run it. This issue is the crux of the
so-called "Full Employment Theorem for Compiler Writers"; i.e. you
cannot
generate optimal code in all cases (not just that it is hard to do so, but
actually provably impossible). The connection with compilers is that if you
could short-cut the execution, then you could constant-fold the entire
program into a single return expression, basically.

As another intuition for why this might be a difficult problem, if you had
an algorithm for deciding whether a function is called, you would put all
mathematicians out of business by running your algorithm on the following
program:

void foo() {}

int main() {
for K = 1, 2, ... (forever):
  for every string S of length K:
    if S is a valid proof of <<insert theorem of your choice>>:
      foo();
}

The same intuition can be applied to almost any question about the behavior
of a program at runtime (for example, with a trivial modification of the
above program, you could just as easily put mathematicians out of business
by being able to tell whether a function returns true or false; same goes
for the Halting Problem (deciding whether the program ever stops running)).



There is a small hitch with everything I just said. The Halting Problem
(and all these related problems) can be easily solved if you can compute an
upper bound on the maximum number of steps taken to produce an answer: run
the program for longer than that upper bound, and if it the program hasn't
given you an answer by then, it must be stuck in an infinite loop.

This upper bound can be established for real computers, or any model of
computation where there is a (computable) limit on the amount of storage
space. A real computer has a finite amount of state (say N bits) in RAM,
registers, etc.; furthermore, each "clock cycle" it deterministically
transitions from one particular configuration of those N bits to another
configuration (ignoring I/O, "random seed" instructions, etc.); there
are
only 2^N such configurations. So if it runs for 2^N + 1 cycles, at least
one configuration must have been entered twice. Because the computer is
deterministic, the same path that took it from the repeating configuration
back to itself will now take it back to that configuration again, and
again, and again, so the program is stuck in an infinite loop.

Of course, 2^N is a completely useless running time for such an algorithm.
Also, the arbitrary restriction to the N bits of a particular computer is
more likely to give you an answer to "does this program happen to go into
an infinite loop when it runs out of memory" (or similar) than about the
actual "ideal" behavior of the program.

Generally speaking, the more closely you can bound the amount of state used
in a computation, the more you can know about its runtime behavior without
actually running it.

-- Sean Silva


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

On Wed, May 21, 2014 at 7:28 AM, Sean Silva <chisophugis at gmail.com>
wrote:
> This upper bound can be established for real computers, or any model of
> computation where there is a (computable) limit on the amount of storage
> space. A real computer has a finite amount of state (say N bits) in RAM,
> registers, etc.; furthermore, each "clock cycle" it
deterministically
> transitions from one particular configuration of those N bits to another
> configuration (ignoring I/O, "random seed" instructions, etc.);
there are
> only 2^N such configurations. So if it runs for 2^N + 1 cycles, at least
> one configuration must have been entered twice. Because the computer is
> deterministic, the same path that took it from the repeating configuration
> back to itself will now take it back to that configuration again, and
> again, and again, so the program is stuck in an infinite loop.
>
There exist microcontrollers with 16 or 32 bytes of registers, and no RAM.
It's enough to run your washing machine, or microwave oven.

This method would be completely impractical even for such a
microcontroller. Let alone anything with RAM. Or I/O.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140521/9b762ed8/attachment.html>