Inlining heuristics fun (Re: [GCC 3.0] Bad regression, binary size)

[Daniel Berlin <dan at cgsoftware dot com>]

Gerald Pfeifer <pfeifer@dbai.tuwien.ac.at> writes:

> On Mon, 9 Jul 2001, Neil Booth wrote:
>>> Indeed, GCC 3.0 takes an order of magnitude longer to compile my sources,
>> That's not fair - it's not compiling the same sources if you're
>> talking about C++ with the standard library, which I presume you are.
> 
> Well, yes. As I wrote "Plus, a lot of that slowdown probably is due to
> libstdc++-v3 and its much more standards compliant implementation of
> iterators etc."
> 
> But, frankly, as I user I'm mainly seeing the following: It's exactly
> the same source that compiles without warning under both compilers, and
> one compiler takes significantly more time and more memory to generate a
> binary that is both larger and slower.

On a related note, I was thinking about region based compiling to
start to solve these problems, and to do this, you really need to
defer output till we have the whole AST. This part isn't too difficult for
C++, we just defer_fn instead of expand_body in the parser (well, for
one of the expand_body's, if you do both, it sits in the reconsidering
loop in finish_file forever).
Imagine my surprise when I did this, and it just caused it to inline
even more, take a ton more time in the backend, but not much more time
in the frontend (memory usage was up about 30%).  This is because we
too aggressively inline already, and I just took it to it's extreme
(by giving it the ability to inline any function in the translation
unit that it wanted to).

the simple program:

#include <string>
#include <iostream>
#include <map>
using namespace std;
int main(void)
{
	map<string, string> dan;
	dan["test"]="test2";

	dan["test"]="test2";
	dan["test"]="test2";
	dan["test"]="test2";
	dan["test"]="test2";
	dan["test"]="test2";
	cout <<dan["test"]<<endl;
	}


Before i did that, generates a main function with 15242 insns (after
they were numbered right after jump. Before this, the max insn number
was 69k or something.)
By the time we hit GCSE, we still have 1288 basic blocks, 1926 edges.
Then  GCSE and scheduling take forever.

*After* i deferred output of all functions, we get a main with, by the
time we hit GCSE, 1516 basic blocks, 2280 edges.
We start with around 17k insns.

In other words, giving the inliner more function bodies, it inlined
more.
I would think that growing a function another ~2500 insns, 200 basic blcoks,
and 360 edges would have hit some clamp, especially after main had
originally started at *get this* 300 insns.

300->15242.

Seems a bit, i dunno, excessive.

Setting the max-inline-insns to 0 to get it to stop inlining (which is
where i came up with the number of insns it started with), it takes 5
seconds to compile at -O3, vs 35 seconds.


If this isn't a cry for help by our poor compiler, i don't know what is.
The solutions are probably, in order of implementation:

1. Better inlining heuristics (Isn't nathan working on this?)

2. Region based compilation or a much faster backend, or something (i only mentioned region
   based compilation because it's easier in gcc to implement than
   straight interprocedural analysis, and allows us to control the
   problem size).


Given the choice, i'd go with something more like region based
compilation, but i'm sure others have other ideas, and have probably
done tons of research on this.

> 
> Gerald
> -- 
> Gerald "Jerry" pfeifer@dbai.tuwien.ac.at http://www.dbai.tuwien.ac.at/~pfeifer/

-- 
"Doing a little work around the house.  I put fake brick
wallpaper over a real brick wall, just so I'd be the only one
who knew.  People come over and I'm gonna say, "Go ahead, touch
it...  It feels real."
"-Steven Wright