58
$\begingroup$

I am interested in the time complexity of a compiler. Clearly this is a very complicated question as there are many compilers, compiler options and variables to consider. Specifically, I am interested in LLVM but would be interested in any thoughts people had or places to start research. A quite google seems to bring little to light.

My guess would be that there are some optimisation steps which are exponential, but which have little impact on the actual time. Eg, exponential based on the number are arguments of a function.

From the top of my head, I would say that generating the AST tree would be linear. IR generation would require stepping through the tree while looking up values in ever growing tables, so $O(n^2)$ or $O(n\log n)$. Code generation and linking would be a similar type of operation. Therefore, my guess would be $O(n^2)$, if we removed exponentials of variables which do not realistically grow.

I could be completely wrong though. Does anyone have any thoughts on it?

Improve this question
$\endgroup$
9
  • 8
    $\begingroup$ You have to be careful when you claim anything is "exponential", "linear", $O(n^2)$, or $O(n \log n)$. At least to me, it is not at all obvious how you measure your input (Exponential in what? What does $n$ stand for?) $\endgroup$
    – Juho
    Mar 9, 2014 at 17:32
  • 2
    $\begingroup$ When you say LLVM, do you mean Clang? LLVM is a big project with several different compiler subprojects so it's a bit ambiguous. $\endgroup$
    – Nate C-K
    Mar 9, 2014 at 21:10
  • 5
    $\begingroup$ For C# it's at least exponential for worst case problems (you can encode the NP complete SAT problem in C#). This isn't just optimization, it's required for choosing the correct overload of a function. For language like C++ it'll be undecidable, since templates are turing complete. $\endgroup$
    – CodesInChaos
    Mar 10, 2014 at 16:43
  • 3
    $\begingroup$ @Zane I don't understand your point. Template instantiation happens during compilation. You can encode hard problems into templates in a way that forces the compiler to solve that problem in order to produce a correct output. You could consider the compiler an interpreter of the turing complete template programming language. $\endgroup$
    – CodesInChaos
    Mar 11, 2014 at 15:18
  • 3
    $\begingroup$ C# overload resolution is pretty tricky when you combine multiple overloads with lambda expressions. You can use that to encode a boolean formula in such a way, that determining if there is an applicable overload requires the NP-complete 3SAT problem. To actually compile the problem, the compiler has to actually find the solution for that formula, which might even be harder. Eric Lippert talks about that in detail in his blog post Lambda Expressions vs. Anonymous Methods, Part Five $\endgroup$
    – CodesInChaos
    Mar 12, 2014 at 16:27

4 Answers 4

Reset to default
53
$\begingroup$

The best book to answer your question would probably be: Cooper and Torczon, "Engineering a Compiler," 2003. If you have access to a university library you should be able to borrow a copy.

In a production compiler like llvm or gcc the designers make every effort to keep all the algorithms below $O(n^2)$ where $n$ is the size of the input. For some of the analysis for the "optimization" phases this means that you need to use heuristics rather than producing truly optimal code.

The lexer is a finite state machine, so $O(n)$ in the size of the input (in characters) and produces a stream of $O(n)$ tokens that is passed to the parser.

For many compilers for many languages the parser is LALR(1) and thus processes the token stream in time $O(n)$ in the number of input tokens. During parsing you typically have to keep track of a symbol table, but, for many languages, that can be handled with a stack of hash tables ("dictionaries"). Each dictionary access is $O(1)$, but you may occasionally have to walk the stack to look up a symbol. The depth of the stack is $O(s)$ where $s$ is the nesting depth of the scopes. (So in C-like languages, how many layers of curly braces you are inside.)

Then the parse tree is typically "flattened" into a control flow graph. The nodes of the control flow graph might be 3-address instructions (similar to a RISC assembly language), and the size of the control flow graph will typically be linear in the size of the parse tree.

Then a series of redundancy elimination steps are typically applied (common subexpression elimination, loop invariant code motion, constant propagation, ...). (This is often called "optimization" although there is rarely anything optimal about the result, the real goal is to improve the code as much as is possible within the time and space constraints we have placed on the compiler.) Each redundancy elimination step will typically require proofs of some facts about the control flow graph. These proofs are typically done using data flow analysis. Most data-flow analyses are designed so that they will converge in $O(d)$ passes over the flow graph where $d$ is (roughly speaking) the loop nesting depth and a pass over the flow graph takes time $O(n)$ where $n$ is the number of 3-address instructions.

For more sophisticated optimizations you might want to do more sophisticated analyses. At this point you start running into tradeoffs. You want your analysis algorithms to take much less than $O(n^2)$ time in the size of the whole-program's flow graph, but this means you need to do without information (and program improving transformations) that might be expensive to prove. A classic example of this is alias analysis, where for some pair of memory writes you would like to prove that the two writes can never target the same memory location. (You might want to do an alias analysis to see if you could move one instruction above the other.) But to get accurate information about aliases you might need to analyze every possible control path through the program, which is exponential in the number of branches in the program (and thus exponential in the number of nodes in the control flow graph.)

Next you get into register allocation. Register allocation can be phrased as a graph-coloring problem, and coloring a graph with a minimal number of colors is known to be NP-Hard. So most compilers use some kind of greedy heuristic combined with register spilling with the goal of reducing the number of register spills as best as possible within reasonable time bounds.

Finally you get into code generation. Code generation is typically done a maximal basic-block at a time where a basic block is a set of linearly connected control flow graph nodes with a single entry and single exit. This can be reformulated as a graph covering problem where the graph you are trying to cover is the dependence graph of the set of 3-address instructions in the basic block, and you are trying to cover with a set of graphs that represent the available machine instructions. This problem is exponential in the size of the largest basic block (which could, in principle, be the same order as the size of the entire program), so this is again typically done with heuristics where only a small subset of the possible coverings are examined.

Improve this answer
$\endgroup$
5
  • 4
    $\begingroup$ Thirded! Incidentally, many of the problems that compilers try to solve (e.g. register allocation) are NP-hard, but others are formally undecidable. Suppose, for example, you have a call p() followed by a call q(). If p is a pure function, then you can safely reorder the calls as long as p() does not infinitely loop. Proving this requires solving the halting problem. As with the NP-hard problems, a compiler writer could put in as much or as little effort in approximating a solution as is feasible. $\endgroup$
    – Pseudonym ♦
    Mar 10, 2014 at 1:23
  • 4
    $\begingroup$ Oh, one more thing: There are some type systems in use today which are very complex in theory. Hindley-Milner type inference is known to the DEXPTIME-complete, and ML-like languages must implement it correctly. However, the run time is linear in practice because a) pathological cases never come up in real-world programs, and b) real-world programmers tend to put in type annotations, if only to get better error messages. $\endgroup$
    – Pseudonym ♦
    Mar 10, 2014 at 1:30
  • 3
    $\begingroup$ Great answer, the only thing that seems missing is the simple part of the explanation, spelled out in simple terms: Compiling a program can be done in O(n). Optimizing a program before compiling, as any modern compiler would do, is a task that is practically unlimited. The time it actually takes is not governed by any inherent limit of the task, but rather by the practical need for the compiler to finish at some point before people get tired of waiting. It is always a compromise. $\endgroup$
    – aaaaaaaaaaaa
    Mar 10, 2014 at 16:08
  • $\begingroup$ @Pseudonym, the fact that many times the compiler would have to solve the halting problem (or very nasty NP hard problems) is one of the reasons standards give the compiler writer leeway in assuming undefined behaviour doesn't happen (like infinite loops and such). $\endgroup$
    – vonbrand
    Mar 11, 2014 at 0:43
  • $\begingroup$ Nice post. I wish compilers had an option to run optimizations for some amount of time rather than applying each algorithm either fully or not at all (like the flags enabled in g++ with -O1, -O2, and -O3). It would be interesting to see the output from relatively small programs optimized for 2 hours versus for 2 seconds. $\endgroup$
    – user904963
    Dec 27, 2021 at 5:25
18
$\begingroup$

Actually, some languages (like C++, Lisp, and D) are Turing-complete at compile time, so compiling them is undecidable in general. For C++, this is because of recursive template instantiation. For Lisp and D, you can execute almost any code at compile time, so you can throw the compiler into an infinite loop if you want.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Haskell's (with extensions) and Scala's type systems are also Turing-complete, meaning that type-checking may take an infinite amount of time. Scala now also has Turing-complete macros on top. $\endgroup$
    – Jörg W Mittag
    Mar 10, 2014 at 12:19
6
$\begingroup$

From my actual experience with C# compiler, I can say that for certain programs the size of the output binary grows exponentially with respect to the size of the input source (this is actually required by the C# spec and cannot be reduced), so time complexity must be at least exponential as well.

The general overload resolution task in C# is known to be NP-hard (and the actual implementation complexity is at least exponential).

A processing of XML documentation comments in C# sources also requires evaluating arbitrary XPath 1.0 expressions at compile-time, that is also exponential, AFAIK.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What makes C# binaries blow up that way? Sounds like a language bug to me... $\endgroup$
    – vonbrand
    Mar 10, 2014 at 19:49
  • 1
    $\begingroup$ It's the way how generic types are encoded in metadata. class X<A,B,C,D,E> { class Y : X<Y,Y,Y,Y,Y> { Y.Y.Y.Y.Y.Y.Y.Y.Y y; } } $\endgroup$
    – Vladimir Reshetnikov
    Mar 10, 2014 at 20:22
-1
$\begingroup$

Measure it with realistic code bases, such as a set of open source projects. If you plot the results as (codeSize,finishTime), then you can plot those graphs. If your data f(x)=y is O(n), then plotting g = f(x)/x should give you a straight line after the data starts to get large.

Plot f(x)/x, f(x)/lg(x), f(x)/(x*lg(x)), f(x)/(x*x), etc. The graph will either dive off to zero, increase without bound, or flatten out. This idea comes in handy for situations like measuring insert times starting from an empty database (ie: to look for a 'performance leak' over a long period.).

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Empirical measurement of running times does not establish computational complexity. First, computational complexity is most commonly expressed in terms of worst-case running time. Second, even if you wanted to measure some sort of average case, you'd need to establish that your inputs are "average" in that sense. $\endgroup$
    – David Richerby
    Mar 11, 2014 at 19:22
  • $\begingroup$ Well sure it's only an estimate. But simple empirical tests with lots of real data (every commit for a bunch of git repos) may well beat a careful model. In any case, if a function really is O(n^3) and you plot f(n)/(nnn), you should get a noisy line with a slope of roughly zero. If you plotted O(n^3)/(n*n) only, you would see it rise linearly. It's really obvious if you overestimate and watch the line quickly dive to zero. $\endgroup$
    – Rob
    Mar 11, 2014 at 21:25
  • 1
    $\begingroup$ No. For example, quicksort runs in time $\Theta(n\log n)$ on most input data but some implementations have $\Theta(n^2)$ running time in the worst case (typically, on input that's already sorted). However, if you just plot the running time, you're much more likely to run into the $\Theta(n\log n)$ cases than the $\Theta(n^2)$ ones. $\endgroup$
    – David Richerby
    Mar 11, 2014 at 21:39
  • $\begingroup$ I agree that it's what you need to know if you are worried about getting a denial of service from an attacker giving you bad input, doing some real-time critical input parsing. The real function that measures compile times is going to be very noisy, and the case that we care about is going to be in real code repositories. $\endgroup$
    – Rob
    Mar 11, 2014 at 21:50
  • 1
    $\begingroup$ No. The question asks about the time complexity of the problem. That is typically interpreted as being the worst-case running time, which is emphatically not the running time on code in repositories. The tests you propose give a reasonable handle on how long you might expect the compiler to take on a given piece of code, which is a good and useful thing to know. But they tell you almost nothing about the computational complexity of the problem. $\endgroup$
    – David Richerby
    Mar 11, 2014 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.