On 07/23/2010 03:54 PM, Don wrote:
Walter Bright wrote:
Andrei Alexandrescu wrote:
Walter Bright wrote:
Don wrote:
While running the semantic on each function body, the compiler
could fairly easily check to see if the function is CTFEable. (The
main complication is that it has to guess about how many iterations
are performed in loops). Then, when a CTFEable function is called
with compile-time constants as arguments, it could run CTFE on it,
even if it is not mandatory.
I think this is the halting problem, and is insoluble.
On what basis?
Trying to determine by static analysis if a function would evaluate
within a "reasonable" amount of time, or even if it would finish at all.
So let's suppose the compiler just attempts CTFE on those functions
anyway, with a timeout if they take too long. Suddenly we've just
thrown all the compiler performance out the window.
But it doesn't need to perfectly solve the complete halting problem. It
can be of benefit if it just identifies some functions which can be
trivially shown to halt, and ignores any which it is unsure about.
For example, a function which contains no loops and no recursive calls
is always CTFEable.
Admittedly, that probably doesn't include many functions which wouldn't
be inlined anyway. But still, while checking for which functions are
inlinable, the compiler could check for 'trivially CTFEable' at the same
time.
If a CTFEable call is made to an inlinable function, it's probably
quicker to CTFE it rather than inline + optimize. Assuming of course
that we have a fast implementation of CTFE.
I completely agree that there will always be opportunities for CTFE
which will be missed unless you allow the compile time to become
arbitrarily long.
By the way, remember you asked at some point what removeAny in
std.container is good for? CTFEability analysis could use such a
primitive...
Andrei
