OSDN Git Service

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