Memory footprint/compile time explosion caused by the tree inliner

[Eric Botcazou]

Hi,

PR optimization/10160 reports a huge compile time regression (4h30min vs a 
few minutes) on the 3.3 branch wrt the 3.2 branch for LyX/QT on Sparc. The 
time is mostly (85%) spent in the scheduler but the regression is caused by 
the tree inliner.

Here are some numbers at -O2:

                               peak    time
GCC 3.2.3pre                   63MB   1min38s
GCC 3.3pre
 max-inline-insns-single=150   89MB   1min18s
 max-inline-insns-single=175   89MB   1min36s
 max-inline-insns-single=200   89MB   2min10s
 max-inline-insns-single=205   90MB   2min38s
 max-inline-insns-single=210   90MB   3min37s
 max-inline-insns-single=215  157MB   5min35s
 max-inline-insns-single=225  185MB   8min19s
 max-inline-insns-single=235 >256MB   ??

The default is max-inline-insns-single=300.


Interestingly, max-inline-insns doesn't play any role:

 max-inline-insns=300 >256MB   ??
 max-inline-insns=200 >256MB   ??
 max-inline-insns=100 >256MB   ??

The default is max-inline-single-insns=600.


So, once we have reached a threshold on the number of insns for a single 
functions, a bunch of little functions (constructors in this case) gets 
inlined, totally out of control.

For example, one constructor grows from 128 stmts to 15437 stmts (154370 
insns according to the fixed conversion factor), that is more than 100 
times. Given that the scheduler is at least O(n^2), the game is over.


The problem is the new heuristics of the tree inliner:

      int sum_insns = (id ? id->inlined_stmts : 0) * INSNS_PER_STMT
		     + currfn_insns;
      /* In the extreme case that we have exceeded the recursive inlining
         limit by a huge factor (128), we just say no. Should not happen
         in real life.  */
      if (sum_insns > MAX_INLINE_INSNS * 128)
	 inlinable = 0;
      /* If we did not hit the extreme limit, we use a linear function
         with slope -1/MAX_INLINE_SLOPE to exceedingly decrease the
         allowable size. We always allow a size of MIN_INLINE_INSNS
         though.  */
      else if ((sum_insns > MAX_INLINE_INSNS)
	       && (currfn_insns > MIN_INLINE_INSNS))
	{
	  int max_curr = MAX_INLINE_INSNS_SINGLE
			- (sum_insns - MAX_INLINE_INSNS) / MAX_INLINE_SLOPE;
	  if (currfn_insns > max_curr)
	    inlinable = 0;
	}

The constructors are small, so we always have

	currfn_insns <= MIN_INLINE_INSNS.

So the limit is not max-inline-insns but max-inline-insns * 128, that is 
76800 insns (7680 stmts) per inlining group!

I did some testing on this arbitrary factor 128:

       peak    time
 16   >256 MB  ??
  8   >256 MB  ??
  4   >256 MB  ??
  3   >256 MB  ??
  2    110 MB  5min20s
  1.5  82  MB  2min37s


It clearly appears that the tree inliner lacks some global control on a per 
function basis. I think we should implement a cut, absolute or relative, so 
as to avoid this kind of explosion in compile time and memory footprint.

-- 
Eric Botcazou