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

[Bruce Hoult]

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>