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

[Sean Silva]

On Tue, May 20, 2014 at 6:19 PM, Bruce Hoult <bruce at hoult.org> wrote:

> 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.
>

Yup. Tiny ones like that are usually mask-programmed or one-time
programmable, so unfortunately there's no use desoldering them from broken
items and keeping them around to reuse in projects. Just have to throw them
away :(


>
> This method would be completely impractical even for such a
> microcontroller. Let alone anything with RAM. Or I/O.
>
>
Yes, that's what I said in the next paragraph. The importance of this
observation is not the practicality: it's that the nature of the difficulty
changes radically, from "provably impossible to do, AT ALL" to "we know at
least that there is an obvious extremely slow and naive algorithm for the
general case, but the door is open for improvements".

Just to play devil's advocate against your claim "would be completely
impractical even for such a microcontroller", I'll give you another
situation where you theoretically have to deal with 2^N configurations
(states), but on many kinds of typical practical inputs the result is quite
manageable: the power set construction, where an NFA with N states is
turned into a DFA with (worst case) 2^N states.

-- Sean Silva
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140521/4e60031f/attachment.html>