Re: Complexity of gcc compiler

[Ian Lance Taylor <iant@xxxxxxxxxx>]

vikram_sp <vikramforum@xxxxxxxxx> writes:

> I am wondering what may be the COMPLEXITY of GCC compiler in big Oh 
> notation or other notation. 
> I have some intuition that lexical analyzer's complexity is O(n) and that of
> parser is O(n^3). Optimization is NPC. Code generator might have some 
> log(n) factor. 
> Taking these things in accounts what is the time complexity of compilers
> in general and GCC in particular.
> Likewise space complexity may also be given thought?

Most of the compiler is linear in the size of the input.  Some specific
optimization passes have a larger complexity.  Some optimization passes
are linear in the number of basic blocks or in the number of
pseudo-registers.  Register allocation is O(n^2) in the number of
pseudo-registers.

Ian