<div dir="ltr">(sorry for the long post; hopefully you will find it informative)<br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, May 20, 2014 at 8:19 AM, lyh.kernel <span dir="ltr"><<a href="mailto:lyh.kernel@gmail.com" target="_blank">lyh.kernel@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">Hello everyone, <div><br></div><div>I want to decide whether a function is executed or not. For example (the value of</div>
<div>cond is not determined at compile time):</div><div><br></div><div>br i1 %cond, label %if, label %else</div>
<div><br></div><div>if:</div><div> ...</div><div> call void f()</div><div> ...</div><div> br label %exit</div><div><br></div><div>else:</div><div> ...</div><div> br label %exit<br></div><div><br></div><div>We could say that function f is control dependent on cond and may not be </div>
<div>executed.</div><div><br></div><div>On the other hand:</div><div><br></div><div><div>br i1 %cond, label %if, label %else</div><div><br></div><div>if:</div><div> ...</div><div> call void f()</div><div> ...</div><div>
br label %exit</div><div><br></div><div>else:</div><div> ...</div><div> call void f()</div><div> ...</div><div> br label %exit</div></div><div><br></div><div>No matter the value of cond is, function f would be executed.<br>
</div><div><br></div><div>I am wondering whether there exist any algorithm to decide whether function f is </div><div>executed or not. Any suggestion or key word are appreciated.</div></div></blockquote><div><br></div><div>
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".</div>
<div><br></div><div>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.</div>
<div><br></div><div>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:</div>
<div><br></div><div>void foo() {}</div><div><br></div><div>int main() {</div><div>for K = 1, 2, ... (forever):</div><div> for every string S of length K:</div><div> if S is a valid proof of <<insert theorem of your choice>>:</div>
<div> foo();</div><div>}</div><div><br></div><div>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)).</div>
<div><br></div><div><br></div><div><br></div><div>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.</div>
<div><br></div><div>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.</div>
<div><br></div><div>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.</div>
<div><br></div><div>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.</div><div><br></div><div>-- Sean Silva</div>
<div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><br></div><div>
Many thanks</div>
</div>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br></div></div>