Memory footprint/compile time explosion caused by the tree inliner

[Geert Bosch]

On Friday, Apr 18, 2003, at 07:20 America/New_York, Eric Botcazou wrote:
>> It would be nice if the scheduler works with very large functions.  It
>> is ok to miss some of the edges, as long as the creamy center is nice.
>
> According to Vlad, there is no hope, the scheduler is at least O(n^2).

Why can't we just insert arbitrary scheduling barriers in very large
functions and schedule the pieces independently? We could relate the
maximum size of a piece to expected execution frequency, so that we
work harder to optimize loops than other code.

It would seem that scheduling is only quadratic if at any cycle you
consider all ready instructions as candidates. If you would limit
candidate instructions to a (preferably sliding) fixed-size window,
scheduling becomes linear as it should be.

Think about it, wouldn't it be quite unacceptable if the scheduling
performed by out-of-order processors would be anything else than
linear in the number of instructions of the executed code? :-)
We definitely need to make GCC's scheduling algorithm execute
in linear time, with the constant related to optimization level.

   -Geert