Asymptotic complexity of a compiler

Question

What is the maximal acceptable asymptotic runtime of a general-purpose compiler?

For clarification: The complexity of compilation process itself, not of the compiled program. Depending on the program size, for instance, the number of source code characters, statements, variables, procedures, basic blocks, intermediate language instructions, assembler instructions, or whatever.

This is highly depending on your point of view, so this is a community wiki.

See this from the view of someone who writes a compiler. Will the optimisation level -O4 ever be used for larger programs when one of its optimisations takes O(n^6)?

Related questions:

• When is superoptimisation (exponential complexity or even incomputable) acceptable?

• What is acceptable for JITs? Does it have to be linear?

• What is the complexity of established compilers? GCC? VC? Intel? Java? C#? Turbo Pascal? LCC? LLVM? (Reference?)

If you do not know what asymptotic complexity is: How long are you willing to wait until the compiler compiled your project? (scripting languages excluded)

Answer 1

I don't think you will find any large project that requires the highest level of optimization for every source file. I would expect that level of optimization to only on those files/classes/modules that really need it. So it is important to provide ways for the developer to limit the scope and cost of such optimizations to the code that needs it.