OSDN Git Service

cb71047d0aa775fb800160471854a13c4625f2ea
[pf3gnuchains/gcc-fork.git] / gcc / ipa-inline.c
1 /* Inlining decision heuristics.
2    Copyright (C) 2003, 2004 Free Software Foundation, Inc.
3    Contributed by Jan Hubicka
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
21
22 /*  Inlining decision heuristics
23
24     We separate inlining decisions from the inliner itself and store it
25     inside callgraph as so called inline plan.  Refer to cgraph.c
26     documentation about particular representation of inline plans in the
27     callgraph.
28
29     There are three major parts of this file:
30
31     cgraph_mark_inline implementation
32
33       This function allows to mark given call inline and performs necessary
34       modifications of cgraph (production of the clones and updating overall
35       statistics)
36
37     inlining heuristics limits
38
39       These functions allow to check that particular inlining is allowed
40       by the limits specified by user (allowed function growth, overall unit
41       growth and so on).
42
43     inlining heuristics
44
45       This is implementation of IPA pass aiming to get as much of benefit
46       from inlining obeying the limits checked above.
47
48       The implementation of particular heuristics is separated from
49       the rest of code to make it easier to replace it with more complicated
50       implementation in the future.  The rest of inlining code acts as a
51       library aimed to modify the callgraph and verify that the parameters
52       on code size growth fits.
53
54       To mark given call inline, use cgraph_mark_inline function, the
55       verification is performed by cgraph_default_inline_p and
56       cgraph_check_inline_limits.
57
58       The heuristics implements simple knapsack style algorithm ordering
59       all functions by their "profitability" (estimated by code size growth)
60       and inlining them in priority order.
61
62       cgraph_decide_inlining implements heuristics taking whole callgraph
63       into account, while cgraph_decide_inlining_incrementally considers
64       only one function at a time and is used in non-unit-at-a-time mode.  */
65
66 #include "config.h"
67 #include "system.h"
68 #include "coretypes.h"
69 #include "tm.h"
70 #include "tree.h"
71 #include "tree-inline.h"
72 #include "langhooks.h"
73 #include "flags.h"
74 #include "cgraph.h"
75 #include "diagnostic.h"
76 #include "timevar.h"
77 #include "params.h"
78 #include "fibheap.h"
79 #include "intl.h"
80 #include "tree-pass.h"
81 #include "coverage.h"
82 #include "ggc.h"
83
84 /* Statistics we collect about inlining algorithm.  */
85 static int ncalls_inlined;
86 static int nfunctions_inlined;
87 static int initial_insns;
88 static int overall_insns;
89 static int max_insns;
90 static gcov_type max_count;
91
92 /* Estimate size of the function after inlining WHAT into TO.  */
93
94 static int
95 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
96                                      struct cgraph_node *what)
97 {
98   int size;
99   tree fndecl = what->decl, arg;
100   int call_insns = PARAM_VALUE (PARAM_INLINE_CALL_COST);
101
102   for (arg = DECL_ARGUMENTS (fndecl); arg; arg = TREE_CHAIN (arg))
103     call_insns += estimate_move_cost (TREE_TYPE (arg));
104   size = (what->global.insns - call_insns) * times + to->global.insns;
105   gcc_assert (size >= 0);
106   return size;
107 }
108
109 /* E is expected to be an edge being inlined.  Clone destination node of
110    the edge and redirect it to the new clone.
111    DUPLICATE is used for bookkeeping on whether we are actually creating new
112    clones or re-using node originally representing out-of-line function call.
113    */
114 void
115 cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate)
116 {
117   struct cgraph_node *n;
118
119   /* We may eliminate the need for out-of-line copy to be output.  In that
120      case just go ahead and re-use it.  */
121   if (!e->callee->callers->next_caller
122       && (!e->callee->needed || DECL_EXTERNAL (e->callee->decl))
123       && duplicate
124       && flag_unit_at_a_time)
125     {
126       gcc_assert (!e->callee->global.inlined_to);
127       if (!DECL_EXTERNAL (e->callee->decl))
128         overall_insns -= e->callee->global.insns, nfunctions_inlined++;
129       duplicate = 0;
130     }
131    else if (duplicate)
132     {
133       n = cgraph_clone_node (e->callee, e->count, e->loop_nest);
134       cgraph_redirect_edge_callee (e, n);
135     }
136
137   if (e->caller->global.inlined_to)
138     e->callee->global.inlined_to = e->caller->global.inlined_to;
139   else
140     e->callee->global.inlined_to = e->caller;
141
142   /* Recursively clone all bodies.  */
143   for (e = e->callee->callees; e; e = e->next_callee)
144     if (!e->inline_failed)
145       cgraph_clone_inlined_nodes (e, duplicate);
146 }
147
148 /* Mark edge E as inlined and update callgraph accordingly.  */
149
150 void
151 cgraph_mark_inline_edge (struct cgraph_edge *e)
152 {
153   int old_insns = 0, new_insns = 0;
154   struct cgraph_node *to = NULL, *what;
155
156   gcc_assert (e->inline_failed);
157   e->inline_failed = NULL;
158
159   if (!e->callee->global.inlined && flag_unit_at_a_time)
160     DECL_POSSIBLY_INLINED (e->callee->decl) = true;
161   e->callee->global.inlined = true;
162
163   cgraph_clone_inlined_nodes (e, true);
164
165   what = e->callee;
166
167   /* Now update size of caller and all functions caller is inlined into.  */
168   for (;e && !e->inline_failed; e = e->caller->callers)
169     {
170       old_insns = e->caller->global.insns;
171       new_insns = cgraph_estimate_size_after_inlining (1, e->caller,
172                                                        what);
173       gcc_assert (new_insns >= 0);
174       to = e->caller;
175       to->global.insns = new_insns;
176     }
177   gcc_assert (what->global.inlined_to == to);
178   if (new_insns > old_insns)
179     overall_insns += new_insns - old_insns;
180   ncalls_inlined++;
181 }
182
183 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
184    Return following unredirected edge in the list of callers
185    of EDGE->CALLEE  */
186
187 static struct cgraph_edge *
188 cgraph_mark_inline (struct cgraph_edge *edge)
189 {
190   struct cgraph_node *to = edge->caller;
191   struct cgraph_node *what = edge->callee;
192   struct cgraph_edge *e, *next;
193   int times = 0;
194
195   /* Look for all calls, mark them inline and clone recursively
196      all inlined functions.  */
197   for (e = what->callers; e; e = next)
198     {
199       next = e->next_caller;
200       if (e->caller == to && e->inline_failed)
201         {
202           cgraph_mark_inline_edge (e);
203           if (e == edge)
204             edge = next;
205           times++;
206         }
207     }
208   gcc_assert (times);
209   return edge;
210 }
211
212 /* Estimate the growth caused by inlining NODE into all callees.  */
213
214 static int
215 cgraph_estimate_growth (struct cgraph_node *node)
216 {
217   int growth = 0;
218   struct cgraph_edge *e;
219   if (node->global.estimated_growth != INT_MIN)
220     return node->global.estimated_growth;
221
222   for (e = node->callers; e; e = e->next_caller)
223     if (e->inline_failed)
224       growth += (cgraph_estimate_size_after_inlining (1, e->caller, node)
225                  - e->caller->global.insns);
226
227   /* ??? Wrong for self recursive functions or cases where we decide to not
228      inline for different reasons, but it is not big deal as in that case
229      we will keep the body around, but we will also avoid some inlining.  */
230   if (!node->needed && !DECL_EXTERNAL (node->decl))
231     growth -= node->global.insns;
232
233   node->global.estimated_growth = growth;
234   return growth;
235 }
236
237 /* Return false when inlining WHAT into TO is not good idea
238    as it would cause too large growth of function bodies.  */
239
240 static bool
241 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
242                             const char **reason)
243 {
244   int times = 0;
245   struct cgraph_edge *e;
246   int newsize;
247   int limit;
248
249   if (to->global.inlined_to)
250     to = to->global.inlined_to;
251
252   for (e = to->callees; e; e = e->next_callee)
253     if (e->callee == what)
254       times++;
255
256   /* When inlining large function body called once into small function,
257      take the inlined function as base for limiting the growth.  */
258   if (to->local.self_insns > what->local.self_insns)
259     limit = to->local.self_insns;
260   else
261     limit = what->local.self_insns;
262
263   limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
264
265   newsize = cgraph_estimate_size_after_inlining (times, to, what);
266   if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
267       && newsize > limit)
268     {
269       if (reason)
270         *reason = N_("--param large-function-growth limit reached");
271       return false;
272     }
273   return true;
274 }
275
276 /* Return true when function N is small enough to be inlined.  */
277
278 bool
279 cgraph_default_inline_p (struct cgraph_node *n)
280 {
281   if (!DECL_INLINE (n->decl) || !DECL_SAVED_TREE (n->decl))
282     return false;
283   if (DECL_DECLARED_INLINE_P (n->decl))
284     return n->global.insns < MAX_INLINE_INSNS_SINGLE;
285   else
286     return n->global.insns < MAX_INLINE_INSNS_AUTO;
287 }
288
289 /* Return true when inlining WHAT would create recursive inlining.
290    We call recursive inlining all cases where same function appears more than
291    once in the single recursion nest path in the inline graph.  */
292
293 static bool
294 cgraph_recursive_inlining_p (struct cgraph_node *to,
295                              struct cgraph_node *what,
296                              const char **reason)
297 {
298   bool recursive;
299   if (to->global.inlined_to)
300     recursive = what->decl == to->global.inlined_to->decl;
301   else
302     recursive = what->decl == to->decl;
303   /* Marking recursive function inline has sane semantic and thus we should
304      not warn on it.  */
305   if (recursive && reason)
306     *reason = (what->local.disregard_inline_limits
307                ? N_("recursive inlining") : "");
308   return recursive;
309 }
310
311 /* Return true if the call can be hot.  */
312 static bool
313 cgraph_maybe_hot_edge_p (struct cgraph_edge *edge)
314 {
315   if (profile_info && flag_branch_probabilities
316       && (edge->count
317           <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
318     return false;
319   return true;
320 }
321
322 /* A cost model driving the inlining heuristics in a way so the edges with
323    smallest badness are inlined first.  After each inlining is performed
324    the costs of all caller edges of nodes affected are recomputed so the
325    metrics may accurately depend on values such as number of inlinable callers
326    of the function or function body size.
327
328    For the moment we use estimated growth caused by inlining callee into all
329    it's callers for driving the inlining but once we have loop depth or
330    frequency information readily available we should do better.
331
332    With profiling we use number of executions of each edge to drive the cost.
333    We also should distinguish hot and cold calls where the cold calls are
334    inlined into only when code size is overall improved.  
335    
336    Value INT_MAX can be returned to prevent function from being inlined.
337    */
338
339 static int
340 cgraph_edge_badness (struct cgraph_edge *edge)
341 {
342   if (max_count)
343     {
344       int growth =
345         cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
346       growth -= edge->caller->global.insns;
347
348       /* Always prefer inlining saving code size.  */
349       if (growth <= 0)
350         return INT_MIN - growth;
351       return ((int)((double)edge->count * INT_MIN / max_count)) / growth;
352     }
353   else
354   {
355     int nest = MIN (edge->loop_nest, 8);
356     int badness = cgraph_estimate_growth (edge->callee) * 256;
357                     
358     badness >>= nest;
359
360     /* Make recursive inlining happen always after other inlining is done.  */
361     if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL))
362       return badness + 1;
363     else
364       return badness;
365   }
366 }
367
368 /* Recompute heap nodes for each of caller edge.  */
369
370 static void
371 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
372                     bitmap updated_nodes)
373 {
374   struct cgraph_edge *edge;
375
376   if (!node->local.inlinable || node->local.disregard_inline_limits
377       || node->global.inlined_to)
378     return;
379   if (bitmap_bit_p (updated_nodes, node->uid))
380     return;
381   bitmap_set_bit (updated_nodes, node->uid);
382
383   for (edge = node->callers; edge; edge = edge->next_caller)
384     if (edge->inline_failed)
385       {
386         int badness = cgraph_edge_badness (edge);
387         if (edge->aux)
388           {
389             fibnode_t n = edge->aux;
390             gcc_assert (n->data == edge);
391             if (n->key == badness)
392               continue;
393
394             /* fibheap_replace_key only increase the keys.  */
395             if (fibheap_replace_key (heap, n, badness))
396               continue;
397             fibheap_delete_node (heap, edge->aux);
398           }
399         edge->aux = fibheap_insert (heap, badness, edge);
400       }
401 }
402
403 /* Recompute heap nodes for each of caller edges of each of callees.  */
404
405 static void
406 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
407                     bitmap updated_nodes)
408 {
409   struct cgraph_edge *e;
410   node->global.estimated_growth = INT_MIN;
411
412   for (e = node->callees; e; e = e->next_callee)
413     if (e->inline_failed)
414       update_caller_keys (heap, e->callee, updated_nodes);
415     else if (!e->inline_failed)
416       update_callee_keys (heap, e->callee, updated_nodes);
417 }
418
419 /* Enqueue all recursive calls from NODE into priority queue depending on
420    how likely we want to recursively inline the call.  */
421
422 static void
423 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
424                         fibheap_t heap)
425 {
426   static int priority;
427   struct cgraph_edge *e;
428   for (e = where->callees; e; e = e->next_callee)
429     if (e->callee == node)
430       {
431         /* FIXME: Once counts and frequencies are available we should drive the
432            order by these.  For now force the order to be simple queue since
433            we get order dependent on recursion depth for free by this.  */
434         fibheap_insert (heap, priority++, e);
435       }
436   for (e = where->callees; e; e = e->next_callee)
437     if (!e->inline_failed)
438       lookup_recursive_calls (node, e->callee, heap);
439 }
440
441 /* Decide on recursive inlining: in the case function has recursive calls,
442    inline until body size reaches given argument.  */
443
444 static bool
445 cgraph_decide_recursive_inlining (struct cgraph_node *node)
446 {
447   int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
448   int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
449   fibheap_t heap;
450   struct cgraph_edge *e;
451   struct cgraph_node *master_clone;
452   int depth = 0;
453   int n = 0;
454
455   if (DECL_DECLARED_INLINE_P (node->decl))
456     {
457       limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
458       max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
459     }
460
461   /* Make sure that function is small enough to be considered for inlining.  */
462   if (!max_depth
463       || cgraph_estimate_size_after_inlining (1, node, node)  >= limit)
464     return false;
465   heap = fibheap_new ();
466   lookup_recursive_calls (node, node, heap);
467   if (fibheap_empty (heap))
468     {
469       fibheap_delete (heap);
470       return false;
471     }
472
473   if (dump_file)
474     fprintf (dump_file, 
475              "  Performing recursive inlining on %s\n",
476              cgraph_node_name (node));
477
478   /* We need original clone to copy around.  */
479   master_clone = cgraph_clone_node (node, 0, 1);
480   master_clone->needed = true;
481   for (e = master_clone->callees; e; e = e->next_callee)
482     if (!e->inline_failed)
483       cgraph_clone_inlined_nodes (e, true);
484
485   /* Do the inlining and update list of recursive call during process.  */
486   while (!fibheap_empty (heap)
487          && cgraph_estimate_size_after_inlining (1, node, master_clone) <= limit)
488     {
489       struct cgraph_edge *curr = fibheap_extract_min (heap);
490       struct cgraph_node *node;
491
492       depth = 0;
493       for (node = curr->caller;
494            node; node = node->global.inlined_to)
495         if (node->decl == curr->callee->decl)
496           depth++;
497       if (depth > max_depth)
498         continue;
499
500       if (dump_file)
501         fprintf (dump_file, 
502                  "   Inlining call of depth %i\n", depth);
503       cgraph_redirect_edge_callee (curr, master_clone);
504       cgraph_mark_inline_edge (curr);
505       lookup_recursive_calls (node, curr->callee, heap);
506       n++;
507     }
508
509   fibheap_delete (heap);
510   if (dump_file)
511     fprintf (dump_file, 
512              "\n   Inlined %i times, body grown from %i to %i insns\n", n,
513              master_clone->global.insns, node->global.insns);
514
515   /* Remove master clone we used for inlining.  We rely that clones inlined
516      into master clone gets queued just before master clone so we don't
517      need recursion.  */
518   for (node = cgraph_nodes; node != master_clone;
519        node = node->next)
520     if (node->global.inlined_to == master_clone)
521       cgraph_remove_node (node);
522   cgraph_remove_node (master_clone);
523   return true;
524 }
525
526 /* Set inline_failed for all callers of given function to REASON.  */
527
528 static void
529 cgraph_set_inline_failed (struct cgraph_node *node, const char *reason)
530 {
531   struct cgraph_edge *e;
532
533   if (dump_file)
534     fprintf (dump_file, "Inlining failed: %s\n", reason);
535   for (e = node->callers; e; e = e->next_caller)
536     if (e->inline_failed)
537       e->inline_failed = reason;
538 }
539
540 /* We use greedy algorithm for inlining of small functions:
541    All inline candidates are put into prioritized heap based on estimated
542    growth of the overall number of instructions and then update the estimates.
543
544    INLINED and INLINED_CALEES are just pointers to arrays large enough
545    to be passed to cgraph_inlined_into and cgraph_inlined_callees.  */
546
547 static void
548 cgraph_decide_inlining_of_small_functions (void)
549 {
550   struct cgraph_node *node;
551   struct cgraph_edge *edge;
552   fibheap_t heap = fibheap_new ();
553   bitmap updated_nodes = BITMAP_ALLOC (NULL);
554
555   if (dump_file)
556     fprintf (dump_file, "\nDeciding on smaller functions:\n");
557
558   /* Put all inline candidates into the heap.  */
559
560   for (node = cgraph_nodes; node; node = node->next)
561     {
562       if (!node->local.inlinable || !node->callers
563           || node->local.disregard_inline_limits)
564         continue;
565       if (dump_file)
566         fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
567
568       node->global.estimated_growth = INT_MIN;
569       if (!cgraph_default_inline_p (node))
570         {
571           cgraph_set_inline_failed (node,
572             N_("--param max-inline-insns-single limit reached"));
573           continue;
574         }
575
576       for (edge = node->callers; edge; edge = edge->next_caller)
577         if (edge->inline_failed)
578           {
579             gcc_assert (!edge->aux);
580             edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge);
581           }
582     }
583   while (overall_insns <= max_insns && (edge = fibheap_extract_min (heap)))
584     {
585       int old_insns = overall_insns;
586       struct cgraph_node *where;
587       int growth =
588         cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
589
590       growth -= edge->caller->global.insns;
591
592       if (dump_file)
593         {
594           fprintf (dump_file, 
595                    "\nConsidering %s with %i insns to be inlined into %s\n"
596                    " Estimated growth after inlined into all callees is %+i insns.\n"
597                    " Estimated badness is %i.\n",
598                    cgraph_node_name (edge->callee),
599                    edge->callee->global.insns,
600                    cgraph_node_name (edge->caller),
601                    cgraph_estimate_growth (edge->callee),
602                    cgraph_edge_badness (edge));
603           if (edge->count)
604             fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
605         }
606       gcc_assert (edge->aux);
607       edge->aux = NULL;
608       if (!edge->inline_failed)
609         continue;
610
611       /* When not having profile info ready we don't weight by any way the
612          position of call in procedure itself.  This means if call of
613          function A from function B seems profitable to inline, the recursive
614          call of function A in inline copy of A in B will look profitable too
615          and we end up inlining until reaching maximal function growth.  This
616          is not good idea so prohibit the recursive inlining.
617
618          ??? When the frequencies are taken into account we might not need this
619          restriction.   */
620       if (!max_count)
621         {
622           where = edge->caller;
623           while (where->global.inlined_to)
624             {
625               if (where->decl == edge->callee->decl)
626                 break;
627               where = where->callers->caller;
628             }
629           if (where->global.inlined_to)
630             {
631               edge->inline_failed
632                 = (edge->callee->local.disregard_inline_limits ? N_("recursive inlining") : "");
633               if (dump_file)
634                 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
635               continue;
636             }
637         }
638
639       if (!cgraph_maybe_hot_edge_p (edge) && growth > 0)
640         {
641           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
642                                             &edge->inline_failed))
643             {
644               edge->inline_failed = 
645                 N_("call is unlikely");
646               if (dump_file)
647                 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
648             }
649           continue;
650         }
651       if (!cgraph_default_inline_p (edge->callee))
652         {
653           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
654                                             &edge->inline_failed))
655             {
656               edge->inline_failed = 
657                 N_("--param max-inline-insns-single limit reached after inlining into the callee");
658               if (dump_file)
659                 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
660             }
661           continue;
662         }
663       if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
664                                        &edge->inline_failed))
665         {
666           where = edge->caller;
667           if (where->global.inlined_to)
668             where = where->global.inlined_to;
669           if (!cgraph_decide_recursive_inlining (where))
670             continue;
671           update_callee_keys (heap, where, updated_nodes);
672         }
673       else
674         {
675           if (!cgraph_check_inline_limits (edge->caller, edge->callee,
676                                            &edge->inline_failed))
677             {
678               if (dump_file)
679                 fprintf (dump_file, " Not inlining into %s:%s.\n",
680                          cgraph_node_name (edge->caller), edge->inline_failed);
681               continue;
682             }
683           cgraph_mark_inline_edge (edge);
684          update_callee_keys (heap, edge->callee, updated_nodes);
685         }
686       where = edge->caller;
687       if (where->global.inlined_to)
688         where = where->global.inlined_to;
689
690       /* Our profitability metric can depend on local properties
691          such as number of inlinable calls and size of the function body.
692          After inlining these properties might change for the function we
693          inlined into (since it's body size changed) and for the functions
694          called by function we inlined (since number of it inlinable callers
695          might change).  */
696       update_caller_keys (heap, where, updated_nodes);
697       bitmap_clear (updated_nodes);
698
699       if (dump_file)
700         fprintf (dump_file, 
701                  " Inlined into %s which now has %i insns.\n",
702                  cgraph_node_name (edge->caller),
703                  edge->caller->global.insns);
704       if (dump_file)
705         fprintf (dump_file, 
706                  " Inlined for a net change of %+i insns.\n",
707                  overall_insns - old_insns);
708     }
709   while ((edge = fibheap_extract_min (heap)) != NULL)
710     {
711       gcc_assert (edge->aux);
712       edge->aux = NULL;
713       if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
714           && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
715                                            &edge->inline_failed))
716         edge->inline_failed = N_("--param inline-unit-growth limit reached");
717     }
718   fibheap_delete (heap);
719   BITMAP_FREE (updated_nodes);
720 }
721
722 /* Decide on the inlining.  We do so in the topological order to avoid
723    expenses on updating data structures.  */
724
725 static void
726 cgraph_decide_inlining (void)
727 {
728   struct cgraph_node *node;
729   int nnodes;
730   struct cgraph_node **order =
731     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
732   int old_insns = 0;
733   int i;
734
735   timevar_push (TV_INLINE_HEURISTICS);
736   max_count = 0;
737   for (node = cgraph_nodes; node; node = node->next)
738     {
739       struct cgraph_edge *e;
740       initial_insns += node->local.self_insns;
741       for (e = node->callees; e; e = e->next_callee)
742         if (max_count < e->count)
743           max_count = e->count;
744     }
745   overall_insns = initial_insns;
746   gcc_assert (!max_count || (profile_info && flag_branch_probabilities));
747
748   max_insns = ((HOST_WIDEST_INT) overall_insns
749                * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
750
751   nnodes = cgraph_postorder (order);
752
753   if (dump_file)
754     fprintf (dump_file,
755              "\nDeciding on inlining.  Starting with %i insns.\n",
756              initial_insns);
757
758   for (node = cgraph_nodes; node; node = node->next)
759     node->aux = 0;
760
761   if (dump_file)
762     fprintf (dump_file, "\nInlining always_inline functions:\n");
763
764   /* In the first pass mark all always_inline edges.  Do this with a priority
765      so none of our later choices will make this impossible.  */
766   for (i = nnodes - 1; i >= 0; i--)
767     {
768       struct cgraph_edge *e, *next;
769
770       node = order[i];
771
772       if (!node->local.disregard_inline_limits)
773         continue;
774       if (dump_file)
775         fprintf (dump_file,
776                  "\nConsidering %s %i insns (always inline)\n",
777                  cgraph_node_name (node), node->global.insns);
778       old_insns = overall_insns;
779       for (e = node->callers; e; e = next)
780         {
781           next = e->next_caller;
782           if (!e->inline_failed)
783             continue;
784           if (cgraph_recursive_inlining_p (e->caller, e->callee,
785                                            &e->inline_failed))
786             continue;
787           cgraph_mark_inline_edge (e);
788           if (dump_file)
789             fprintf (dump_file, 
790                      " Inlined into %s which now has %i insns.\n",
791                      cgraph_node_name (e->caller),
792                      e->caller->global.insns);
793         }
794       if (dump_file)
795         fprintf (dump_file, 
796                  " Inlined for a net change of %+i insns.\n",
797                  overall_insns - old_insns);
798     }
799
800   if (!flag_really_no_inline)
801     {
802       cgraph_decide_inlining_of_small_functions ();
803
804       if (dump_file)
805         fprintf (dump_file, "\nDeciding on functions called once:\n");
806
807       /* And finally decide what functions are called once.  */
808
809       for (i = nnodes - 1; i >= 0; i--)
810         {
811           node = order[i];
812
813           if (node->callers && !node->callers->next_caller && !node->needed
814               && node->local.inlinable && node->callers->inline_failed
815               && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
816             {
817               bool ok = true;
818               struct cgraph_node *node1;
819
820               /* Verify that we won't duplicate the caller.  */
821               for (node1 = node->callers->caller;
822                    node1->callers && !node1->callers->inline_failed
823                    && ok; node1 = node1->callers->caller)
824                 if (node1->callers->next_caller || node1->needed)
825                   ok = false;
826               if (ok)
827                 {
828                   if (dump_file)
829                     fprintf (dump_file,
830                              "\nConsidering %s %i insns.\n"
831                              " Called once from %s %i insns.\n",
832                              cgraph_node_name (node), node->global.insns,
833                              cgraph_node_name (node->callers->caller),
834                              node->callers->caller->global.insns);
835
836                   old_insns = overall_insns;
837
838                   if (cgraph_check_inline_limits (node->callers->caller, node,
839                                                   NULL))
840                     {
841                       cgraph_mark_inline (node->callers);
842                       if (dump_file)
843                         fprintf (dump_file,
844                                  " Inlined into %s which now has %i insns"
845                                  " for a net change of %+i insns.\n",
846                                  cgraph_node_name (node->callers->caller),
847                                  node->callers->caller->global.insns,
848                                  overall_insns - old_insns);
849                     }
850                   else
851                     {
852                       if (dump_file)
853                         fprintf (dump_file,
854                                  " Inline limit reached, not inlined.\n");
855                     }
856                 }
857             }
858         }
859     }
860
861   if (dump_file)
862     fprintf (dump_file,
863              "\nInlined %i calls, eliminated %i functions, "
864              "%i insns turned to %i insns.\n\n",
865              ncalls_inlined, nfunctions_inlined, initial_insns,
866              overall_insns);
867   free (order);
868   timevar_pop (TV_INLINE_HEURISTICS);
869 }
870
871 /* Decide on the inlining.  We do so in the topological order to avoid
872    expenses on updating data structures.  */
873
874 bool
875 cgraph_decide_inlining_incrementally (struct cgraph_node *node, bool early)
876 {
877   struct cgraph_edge *e;
878   bool inlined = false;
879
880   /* First of all look for always inline functions.  */
881   for (e = node->callees; e; e = e->next_callee)
882     if (e->callee->local.disregard_inline_limits
883         && e->inline_failed
884         && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
885         /* ??? It is possible that renaming variable removed the function body
886            in duplicate_decls. See gcc.c-torture/compile/20011119-2.c  */
887         && DECL_SAVED_TREE (e->callee->decl))
888       {
889         if (dump_file && early)
890           fprintf (dump_file, "  Early inlining %s into %s\n",
891                    cgraph_node_name (e->callee), cgraph_node_name (node));
892         cgraph_mark_inline (e);
893         inlined = true;
894       }
895
896   /* Now do the automatic inlining.  */
897   if (!flag_really_no_inline)
898     for (e = node->callees; e; e = e->next_callee)
899       if (e->callee->local.inlinable
900           && e->inline_failed
901           && !e->callee->local.disregard_inline_limits
902           && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
903           && (!early
904               || (cgraph_estimate_size_after_inlining (1, e->caller, node)
905                   <= e->caller->global.insns))
906           && cgraph_check_inline_limits (node, e->callee, &e->inline_failed)
907           && DECL_SAVED_TREE (e->callee->decl))
908         {
909           if (cgraph_default_inline_p (e->callee))
910             {
911               if (dump_file && early)
912                 fprintf (dump_file, "  Early inlining %s into %s\n",
913                          cgraph_node_name (e->callee), cgraph_node_name (node));
914               cgraph_mark_inline (e);
915               inlined = true;
916             }
917           else if (!early)
918             e->inline_failed
919               = N_("--param max-inline-insns-single limit reached");
920         }
921   if (early && inlined)
922     {
923       push_cfun (DECL_STRUCT_FUNCTION (node->decl));
924       tree_register_cfg_hooks ();
925       current_function_decl = node->decl;
926       optimize_inline_calls (current_function_decl);
927       node->local.self_insns = node->global.insns;
928       current_function_decl = NULL;
929       pop_cfun ();
930       ggc_collect ();
931     }
932   return inlined;
933 }
934
935 /* When inlining shall be performed.  */
936 static bool
937 cgraph_gate_inlining (void)
938 {
939   return flag_inline_trees;
940 }
941
942 struct tree_opt_pass pass_ipa_inline = 
943 {
944   "inline",                             /* name */
945   cgraph_gate_inlining,                 /* gate */
946   cgraph_decide_inlining,               /* execute */
947   NULL,                                 /* sub */
948   NULL,                                 /* next */
949   0,                                    /* static_pass_number */
950   TV_INTEGRATION,                       /* tv_id */
951   0,                                    /* properties_required */
952   PROP_cfg,                             /* properties_provided */
953   0,                                    /* properties_destroyed */
954   0,                                    /* todo_flags_start */
955   TODO_dump_cgraph | TODO_dump_func,    /* todo_flags_finish */
956   0                                     /* letter */
957 };
958
959 /* Do inlining of small functions.  Doing so early helps profiling and other
960    passes to be somewhat more effective and avoids some code duplication in
961    later real inlining pass for testcases with very many function calls.  */
962 static void
963 cgraph_early_inlining (void)
964 {
965   struct cgraph_node *node;
966   int nnodes;
967   struct cgraph_node **order =
968     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
969   int i;
970
971   if (sorrycount || errorcount)
972     return;
973 #ifdef ENABLE_CHECKING
974   for (node = cgraph_nodes; node; node = node->next)
975     gcc_assert (!node->aux);
976 #endif
977
978   nnodes = cgraph_postorder (order);
979   for (i = nnodes - 1; i >= 0; i--)
980     {
981       node = order[i];
982       if (node->analyzed && node->local.inlinable
983           && (node->needed || node->reachable)
984           && node->callers)
985         cgraph_decide_inlining_incrementally (node, true);
986     }
987   cgraph_remove_unreachable_nodes (true, dump_file);
988 #ifdef ENABLE_CHECKING
989   for (node = cgraph_nodes; node; node = node->next)
990     gcc_assert (!node->global.inlined_to);
991 #endif
992   free (order);
993 }
994
995 /* When inlining shall be performed.  */
996 static bool
997 cgraph_gate_early_inlining (void)
998 {
999   return flag_inline_trees && flag_early_inlining;
1000 }
1001
1002 struct tree_opt_pass pass_early_ipa_inline = 
1003 {
1004   "einline",                            /* name */
1005   cgraph_gate_early_inlining,           /* gate */
1006   cgraph_early_inlining,                /* execute */
1007   NULL,                                 /* sub */
1008   NULL,                                 /* next */
1009   0,                                    /* static_pass_number */
1010   TV_INTEGRATION,                       /* tv_id */
1011   0,                                    /* properties_required */
1012   PROP_cfg,                             /* properties_provided */
1013   0,                                    /* properties_destroyed */
1014   0,                                    /* todo_flags_start */
1015   TODO_dump_cgraph | TODO_dump_func,    /* todo_flags_finish */
1016   0                                     /* letter */
1017 };