OSDN Git Service

2010-04-12 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / ipa-inline.c
1 /* Inlining decision heuristics.
2    Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010
3    Free Software Foundation, Inc.
4    Contributed by Jan Hubicka
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
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 by early inliner.
65
66    The inliner itself is split into several passes:
67
68    pass_inline_parameters
69
70      This pass computes local properties of functions that are used by inliner:
71      estimated function body size, whether function is inlinable at all and
72      stack frame consumption.
73
74      Before executing any of inliner passes, this local pass has to be applied
75      to each function in the callgraph (ie run as subpass of some earlier
76      IPA pass).  The results are made out of date by any optimization applied
77      on the function body.
78
79    pass_early_inlining
80
81      Simple local inlining pass inlining callees into current function.  This
82      pass makes no global whole compilation unit analysis and this when allowed
83      to do inlining expanding code size it might result in unbounded growth of
84      whole unit.
85
86      The pass is run during conversion into SSA form.  Only functions already
87      converted into SSA form are inlined, so the conversion must happen in
88      topological order on the callgraph (that is maintained by pass manager).
89      The functions after inlining are early optimized so the early inliner sees
90      unoptimized function itself, but all considered callees are already
91      optimized allowing it to unfold abstraction penalty on C++ effectively and
92      cheaply.
93
94    pass_ipa_early_inlining
95
96      With profiling, the early inlining is also necessary to reduce
97      instrumentation costs on program with high abstraction penalty (doing
98      many redundant calls).  This can't happen in parallel with early
99      optimization and profile instrumentation, because we would end up
100      re-instrumenting already instrumented function bodies we brought in via
101      inlining.
102
103      To avoid this, this pass is executed as IPA pass before profiling.  It is
104      simple wrapper to pass_early_inlining and ensures first inlining.
105
106    pass_ipa_inline
107
108      This is the main pass implementing simple greedy algorithm to do inlining
109      of small functions that results in overall growth of compilation unit and
110      inlining of functions called once.  The pass compute just so called inline
111      plan (representation of inlining to be done in callgraph) and unlike early
112      inlining it is not performing the inlining itself.
113
114    pass_apply_inline
115
116      This pass performs actual inlining according to pass_ipa_inline on given
117      function.  Possible the function body before inlining is saved when it is
118      needed for further inlining later.
119  */
120
121 #include "config.h"
122 #include "system.h"
123 #include "coretypes.h"
124 #include "tm.h"
125 #include "tree.h"
126 #include "tree-inline.h"
127 #include "langhooks.h"
128 #include "flags.h"
129 #include "cgraph.h"
130 #include "diagnostic.h"
131 #include "timevar.h"
132 #include "params.h"
133 #include "fibheap.h"
134 #include "intl.h"
135 #include "tree-pass.h"
136 #include "hashtab.h"
137 #include "coverage.h"
138 #include "ggc.h"
139 #include "tree-flow.h"
140 #include "rtl.h"
141 #include "ipa-prop.h"
142 #include "except.h"
143
144 #define MAX_TIME 1000000000
145
146 /* Mode incremental inliner operate on:
147
148    In ALWAYS_INLINE only functions marked
149    always_inline are inlined.  This mode is used after detecting cycle during
150    flattening.
151
152    In SIZE mode, only functions that reduce function body size after inlining
153    are inlined, this is used during early inlining.
154
155    in ALL mode, everything is inlined.  This is used during flattening.  */
156 enum inlining_mode {
157   INLINE_NONE = 0,
158   INLINE_ALWAYS_INLINE,
159   INLINE_SIZE_NORECURSIVE,
160   INLINE_SIZE,
161   INLINE_ALL
162 };
163
164 static bool
165 cgraph_decide_inlining_incrementally (struct cgraph_node *, enum inlining_mode);
166 static void cgraph_flatten (struct cgraph_node *node);
167
168
169 /* Statistics we collect about inlining algorithm.  */
170 static int ncalls_inlined;
171 static int nfunctions_inlined;
172 static int overall_size;
173 static gcov_type max_count, max_benefit;
174
175 /* Holders of ipa cgraph hooks: */
176 static struct cgraph_node_hook_list *function_insertion_hook_holder;
177
178 static inline struct inline_summary *
179 inline_summary (struct cgraph_node *node)
180 {
181   return &node->local.inline_summary;
182 }
183
184 /* Estimate self time of the function after inlining WHAT into TO.  */
185
186 static int
187 cgraph_estimate_time_after_inlining (int frequency, struct cgraph_node *to,
188                                      struct cgraph_node *what)
189 {
190   gcov_type time = (((gcov_type)what->global.time
191                      - inline_summary (what)->time_inlining_benefit)
192                     * frequency + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE
193                     + to->global.time;
194   if (time < 0)
195     time = 0;
196   if (time > MAX_TIME)
197     time = MAX_TIME;
198   return time;
199 }
200
201 /* Estimate self time of the function after inlining WHAT into TO.  */
202
203 static int
204 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
205                                      struct cgraph_node *what)
206 {
207   int size = (what->global.size - inline_summary (what)->size_inlining_benefit) * times + to->global.size;
208   gcc_assert (size >= 0);
209   return size;
210 }
211
212 /* Scale frequency of NODE edges by FREQ_SCALE and increase loop nest
213    by NEST.  */
214
215 static void
216 update_noncloned_frequencies (struct cgraph_node *node,
217                               int freq_scale, int nest)
218 {
219   struct cgraph_edge *e;
220
221   /* We do not want to ignore high loop nest after freq drops to 0.  */
222   if (!freq_scale)
223     freq_scale = 1;
224   for (e = node->callees; e; e = e->next_callee)
225     {
226       e->loop_nest += nest;
227       e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
228       if (e->frequency > CGRAPH_FREQ_MAX)
229         e->frequency = CGRAPH_FREQ_MAX;
230       if (!e->inline_failed)
231         update_noncloned_frequencies (e->callee, freq_scale, nest);
232     }
233 }
234
235 /* E is expected to be an edge being inlined.  Clone destination node of
236    the edge and redirect it to the new clone.
237    DUPLICATE is used for bookkeeping on whether we are actually creating new
238    clones or re-using node originally representing out-of-line function call.
239    */
240 void
241 cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate,
242                             bool update_original)
243 {
244   HOST_WIDE_INT peak;
245
246   if (duplicate)
247     {
248       /* We may eliminate the need for out-of-line copy to be output.
249          In that case just go ahead and re-use it.  */
250       if (!e->callee->callers->next_caller
251           && cgraph_can_remove_if_no_direct_calls_p (e->callee)
252           /* Don't reuse if more than one function shares a comdat group.
253              If the other function(s) are needed, we need to emit even
254              this function out of line.  */
255           && !e->callee->same_comdat_group
256           && !cgraph_new_nodes)
257         {
258           gcc_assert (!e->callee->global.inlined_to);
259           if (e->callee->analyzed)
260             {
261               overall_size -= e->callee->global.size;
262               nfunctions_inlined++;
263             }
264           duplicate = false;
265           e->callee->local.externally_visible = false;
266           update_noncloned_frequencies (e->callee, e->frequency, e->loop_nest);
267         }
268       else
269         {
270           struct cgraph_node *n;
271           n = cgraph_clone_node (e->callee, e->callee->decl,
272                                  e->count, e->frequency, e->loop_nest,
273                                  update_original, NULL);
274           cgraph_redirect_edge_callee (e, n);
275         }
276     }
277
278   if (e->caller->global.inlined_to)
279     e->callee->global.inlined_to = e->caller->global.inlined_to;
280   else
281     e->callee->global.inlined_to = e->caller;
282   e->callee->global.stack_frame_offset
283     = e->caller->global.stack_frame_offset
284       + inline_summary (e->caller)->estimated_self_stack_size;
285   peak = e->callee->global.stack_frame_offset
286       + inline_summary (e->callee)->estimated_self_stack_size;
287   if (e->callee->global.inlined_to->global.estimated_stack_size < peak)
288     e->callee->global.inlined_to->global.estimated_stack_size = peak;
289   cgraph_propagate_frequency (e->callee);
290
291   /* Recursively clone all bodies.  */
292   for (e = e->callee->callees; e; e = e->next_callee)
293     if (!e->inline_failed)
294       cgraph_clone_inlined_nodes (e, duplicate, update_original);
295 }
296
297 /* Mark edge E as inlined and update callgraph accordingly.  UPDATE_ORIGINAL
298    specify whether profile of original function should be updated.  If any new
299    indirect edges are discovered in the process, add them to NEW_EDGES, unless
300    it is NULL.  Return true iff any new callgraph edges were discovered as a
301    result of inlining.  */
302
303 static bool
304 cgraph_mark_inline_edge (struct cgraph_edge *e, bool update_original,
305                          VEC (cgraph_edge_p, heap) **new_edges)
306 {
307   int old_size = 0, new_size = 0;
308   struct cgraph_node *to = NULL, *what;
309   struct cgraph_edge *curr = e;
310   int freq;
311
312   gcc_assert (e->inline_failed);
313   e->inline_failed = CIF_OK;
314   DECL_POSSIBLY_INLINED (e->callee->decl) = true;
315
316   cgraph_clone_inlined_nodes (e, true, update_original);
317
318   what = e->callee;
319
320   freq = e->frequency;
321   /* Now update size of caller and all functions caller is inlined into.  */
322   for (;e && !e->inline_failed; e = e->caller->callers)
323     {
324       to = e->caller;
325       old_size = e->caller->global.size;
326       new_size = cgraph_estimate_size_after_inlining (1, to, what);
327       to->global.size = new_size;
328       to->global.time = cgraph_estimate_time_after_inlining (freq, to, what);
329     }
330   gcc_assert (what->global.inlined_to == to);
331   if (new_size > old_size)
332     overall_size += new_size - old_size;
333   ncalls_inlined++;
334
335   if (flag_indirect_inlining)
336     return ipa_propagate_indirect_call_infos (curr, new_edges);
337   else
338     return false;
339 }
340
341 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.  */
342
343 static void
344 cgraph_mark_inline (struct cgraph_edge *edge)
345 {
346   struct cgraph_node *to = edge->caller;
347   struct cgraph_node *what = edge->callee;
348   struct cgraph_edge *e, *next;
349
350   gcc_assert (!edge->call_stmt_cannot_inline_p);
351   /* Look for all calls, mark them inline and clone recursively
352      all inlined functions.  */
353   for (e = what->callers; e; e = next)
354     {
355       next = e->next_caller;
356       if (e->caller == to && e->inline_failed)
357         {
358           cgraph_mark_inline_edge (e, true, NULL);
359           if (e == edge)
360             edge = next;
361         }
362     }
363 }
364
365 /* Estimate the growth caused by inlining NODE into all callees.  */
366
367 static int
368 cgraph_estimate_growth (struct cgraph_node *node)
369 {
370   int growth = 0;
371   struct cgraph_edge *e;
372   bool self_recursive = false;
373
374   if (node->global.estimated_growth != INT_MIN)
375     return node->global.estimated_growth;
376
377   for (e = node->callers; e; e = e->next_caller)
378     {
379       if (e->caller == node)
380         self_recursive = true;
381       if (e->inline_failed)
382         growth += (cgraph_estimate_size_after_inlining (1, e->caller, node)
383                    - e->caller->global.size);
384     }
385
386   /* ??? Wrong for non-trivially self recursive functions or cases where
387      we decide to not inline for different reasons, but it is not big deal
388      as in that case we will keep the body around, but we will also avoid
389      some inlining.  */
390   if (cgraph_only_called_directly_p (node)
391       && !DECL_EXTERNAL (node->decl) && !self_recursive)
392     growth -= node->global.size;
393
394   node->global.estimated_growth = growth;
395   return growth;
396 }
397
398 /* Return false when inlining WHAT into TO is not good idea
399    as it would cause too large growth of function bodies.
400    When ONE_ONLY is true, assume that only one call site is going
401    to be inlined, otherwise figure out how many call sites in
402    TO calls WHAT and verify that all can be inlined.
403    */
404
405 static bool
406 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
407                             cgraph_inline_failed_t *reason, bool one_only)
408 {
409   int times = 0;
410   struct cgraph_edge *e;
411   int newsize;
412   int limit;
413   HOST_WIDE_INT stack_size_limit, inlined_stack;
414
415   if (one_only)
416     times = 1;
417   else
418     for (e = to->callees; e; e = e->next_callee)
419       if (e->callee == what)
420         times++;
421
422   if (to->global.inlined_to)
423     to = to->global.inlined_to;
424
425   /* When inlining large function body called once into small function,
426      take the inlined function as base for limiting the growth.  */
427   if (inline_summary (to)->self_size > inline_summary(what)->self_size)
428     limit = inline_summary (to)->self_size;
429   else
430     limit = inline_summary (what)->self_size;
431
432   limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
433
434   /* Check the size after inlining against the function limits.  But allow
435      the function to shrink if it went over the limits by forced inlining.  */
436   newsize = cgraph_estimate_size_after_inlining (times, to, what);
437   if (newsize >= to->global.size
438       && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
439       && newsize > limit)
440     {
441       if (reason)
442         *reason = CIF_LARGE_FUNCTION_GROWTH_LIMIT;
443       return false;
444     }
445
446   stack_size_limit = inline_summary (to)->estimated_self_stack_size;
447
448   stack_size_limit += stack_size_limit * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH) / 100;
449
450   inlined_stack = (to->global.stack_frame_offset
451                    + inline_summary (to)->estimated_self_stack_size
452                    + what->global.estimated_stack_size);
453   if (inlined_stack  > stack_size_limit
454       && inlined_stack > PARAM_VALUE (PARAM_LARGE_STACK_FRAME))
455     {
456       if (reason)
457         *reason = CIF_LARGE_STACK_FRAME_GROWTH_LIMIT;
458       return false;
459     }
460   return true;
461 }
462
463 /* Return true when function N is small enough to be inlined.  */
464
465 static bool
466 cgraph_default_inline_p (struct cgraph_node *n, cgraph_inline_failed_t *reason)
467 {
468   tree decl = n->decl;
469
470   if (n->local.disregard_inline_limits)
471     return true;
472
473   if (!flag_inline_small_functions && !DECL_DECLARED_INLINE_P (decl))
474     {
475       if (reason)
476         *reason = CIF_FUNCTION_NOT_INLINE_CANDIDATE;
477       return false;
478     }
479
480   if (!n->analyzed)
481     {
482       if (reason)
483         *reason = CIF_BODY_NOT_AVAILABLE;
484       return false;
485     }
486
487   if (DECL_DECLARED_INLINE_P (decl))
488     {
489       if (n->global.size >= MAX_INLINE_INSNS_SINGLE)
490         {
491           if (reason)
492             *reason = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
493           return false;
494         }
495     }
496   else
497     {
498       if (n->global.size >= MAX_INLINE_INSNS_AUTO)
499         {
500           if (reason)
501             *reason = CIF_MAX_INLINE_INSNS_AUTO_LIMIT;
502           return false;
503         }
504     }
505
506   return true;
507 }
508
509 /* Return true when inlining WHAT would create recursive inlining.
510    We call recursive inlining all cases where same function appears more than
511    once in the single recursion nest path in the inline graph.  */
512
513 static bool
514 cgraph_recursive_inlining_p (struct cgraph_node *to,
515                              struct cgraph_node *what,
516                              cgraph_inline_failed_t *reason)
517 {
518   bool recursive;
519   if (to->global.inlined_to)
520     recursive = what->decl == to->global.inlined_to->decl;
521   else
522     recursive = what->decl == to->decl;
523   /* Marking recursive function inline has sane semantic and thus we should
524      not warn on it.  */
525   if (recursive && reason)
526     *reason = (what->local.disregard_inline_limits
527                ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
528   return recursive;
529 }
530
531 /* A cost model driving the inlining heuristics in a way so the edges with
532    smallest badness are inlined first.  After each inlining is performed
533    the costs of all caller edges of nodes affected are recomputed so the
534    metrics may accurately depend on values such as number of inlinable callers
535    of the function or function body size.  */
536
537 static int
538 cgraph_edge_badness (struct cgraph_edge *edge, bool dump)
539 {
540   gcov_type badness;
541   int growth =
542     (cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee)
543      - edge->caller->global.size);
544
545   if (edge->callee->local.disregard_inline_limits)
546     return INT_MIN;
547
548   if (dump)
549     {
550       fprintf (dump_file, "    Badness calculcation for %s -> %s\n",
551                cgraph_node_name (edge->caller),
552                cgraph_node_name (edge->callee));
553       fprintf (dump_file, "      growth %i, time %i-%i, size %i-%i\n",
554                growth,
555                edge->callee->global.time,
556                inline_summary (edge->callee)->time_inlining_benefit,
557                edge->callee->global.size,
558                inline_summary (edge->callee)->size_inlining_benefit);
559     }
560
561   /* Always prefer inlining saving code size.  */
562   if (growth <= 0)
563     {
564       badness = INT_MIN - growth;
565       if (dump)
566         fprintf (dump_file, "      %i: Growth %i < 0\n", (int) badness,
567                  growth);
568     }
569
570   /* When profiling is available, base priorities -(#calls / growth).
571      So we optimize for overall number of "executed" inlined calls.  */
572   else if (max_count)
573     {
574       badness =
575         ((int)
576          ((double) edge->count * INT_MIN / max_count / (max_benefit + 1)) *
577          (inline_summary (edge->callee)->time_inlining_benefit + 1)) / growth;
578       if (dump)
579         {
580           fprintf (dump_file,
581                    "      %i (relative %f): profile info. Relative count %f"
582                    " * Relative benefit %f\n",
583                    (int) badness, (double) badness / INT_MIN,
584                    (double) edge->count / max_count,
585                    (double) (inline_summary (edge->callee)->
586                              time_inlining_benefit + 1) / (max_benefit + 1));
587         }
588     }
589
590   /* When function local profile is available, base priorities on
591      growth / frequency, so we optimize for overall frequency of inlined
592      calls.  This is not too accurate since while the call might be frequent
593      within function, the function itself is infrequent.
594
595      Other objective to optimize for is number of different calls inlined.
596      We add the estimated growth after inlining all functions to bias the
597      priorities slightly in this direction (so fewer times called functions
598      of the same size gets priority).  */
599   else if (flag_guess_branch_prob)
600     {
601       int div = edge->frequency * 100 / CGRAPH_FREQ_BASE + 1;
602       int benefitperc;
603       int growth_for_all;
604       badness = growth * 10000;
605       benefitperc =
606         MIN (100 * inline_summary (edge->callee)->time_inlining_benefit /
607              (edge->callee->global.time + 1) +1, 100);
608       div *= benefitperc;
609
610
611       /* Decrease badness if call is nested.  */
612       /* Compress the range so we don't overflow.  */
613       if (div > 10000)
614         div = 10000 + ceil_log2 (div) - 8;
615       if (div < 1)
616         div = 1;
617       if (badness > 0)
618         badness /= div;
619       growth_for_all = cgraph_estimate_growth (edge->callee);
620       badness += growth_for_all;
621       if (badness > INT_MAX)
622         badness = INT_MAX;
623       if (dump)
624         {
625           fprintf (dump_file,
626                    "      %i: guessed profile. frequency %i, overall growth %i,"
627                    " benefit %i%%, divisor %i\n",
628                    (int) badness, edge->frequency, growth_for_all, benefitperc, div);
629         }
630     }
631   /* When function local profile is not available or it does not give
632      useful information (ie frequency is zero), base the cost on
633      loop nest and overall size growth, so we optimize for overall number
634      of functions fully inlined in program.  */
635   else
636     {
637       int nest = MIN (edge->loop_nest, 8);
638       badness = cgraph_estimate_growth (edge->callee) * 256;
639
640       /* Decrease badness if call is nested.  */
641       if (badness > 0)
642         badness >>= nest;
643       else
644         {
645           badness <<= nest;
646         }
647       if (dump)
648         fprintf (dump_file, "      %i: no profile. nest %i\n", (int) badness,
649                  nest);
650     }
651
652   /* Ensure that we did not overflow in all the fixed point math above.  */
653   gcc_assert (badness >= INT_MIN);
654   gcc_assert (badness <= INT_MAX - 1);
655   /* Make recursive inlining happen always after other inlining is done.  */
656   if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL))
657     return badness + 1;
658   else
659     return badness;
660 }
661
662 /* Recompute heap nodes for each of caller edge.  */
663
664 static void
665 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
666                     bitmap updated_nodes)
667 {
668   struct cgraph_edge *edge;
669   cgraph_inline_failed_t failed_reason;
670
671   if (!node->local.inlinable
672       || node->global.inlined_to)
673     return;
674   if (bitmap_bit_p (updated_nodes, node->uid))
675     return;
676   bitmap_set_bit (updated_nodes, node->uid);
677   node->global.estimated_growth = INT_MIN;
678
679   if (!node->local.inlinable)
680     return;
681   /* Prune out edges we won't inline into anymore.  */
682   if (!cgraph_default_inline_p (node, &failed_reason))
683     {
684       for (edge = node->callers; edge; edge = edge->next_caller)
685         if (edge->aux)
686           {
687             fibheap_delete_node (heap, (fibnode_t) edge->aux);
688             edge->aux = NULL;
689             if (edge->inline_failed)
690               edge->inline_failed = failed_reason;
691           }
692       return;
693     }
694
695   for (edge = node->callers; edge; edge = edge->next_caller)
696     if (edge->inline_failed)
697       {
698         int badness = cgraph_edge_badness (edge, false);
699         if (edge->aux)
700           {
701             fibnode_t n = (fibnode_t) edge->aux;
702             gcc_assert (n->data == edge);
703             if (n->key == badness)
704               continue;
705
706             /* fibheap_replace_key only increase the keys.  */
707             if (badness < n->key)
708               {
709                 fibheap_replace_key (heap, n, badness);
710                 gcc_assert (n->key == badness);
711                 continue;
712               }
713             fibheap_delete_node (heap, (fibnode_t) edge->aux);
714           }
715         edge->aux = fibheap_insert (heap, badness, edge);
716       }
717 }
718
719 /* Recompute heap nodes for each of caller edges of each of callees.  */
720
721 static void
722 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
723                     bitmap updated_nodes)
724 {
725   struct cgraph_edge *e;
726   node->global.estimated_growth = INT_MIN;
727
728   for (e = node->callees; e; e = e->next_callee)
729     if (e->inline_failed)
730       update_caller_keys (heap, e->callee, updated_nodes);
731     else if (!e->inline_failed)
732       update_callee_keys (heap, e->callee, updated_nodes);
733 }
734
735 /* Enqueue all recursive calls from NODE into priority queue depending on
736    how likely we want to recursively inline the call.  */
737
738 static void
739 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
740                         fibheap_t heap)
741 {
742   static int priority;
743   struct cgraph_edge *e;
744   for (e = where->callees; e; e = e->next_callee)
745     if (e->callee == node)
746       {
747         /* When profile feedback is available, prioritize by expected number
748            of calls.  Without profile feedback we maintain simple queue
749            to order candidates via recursive depths.  */
750         fibheap_insert (heap,
751                         !max_count ? priority++
752                         : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
753                         e);
754       }
755   for (e = where->callees; e; e = e->next_callee)
756     if (!e->inline_failed)
757       lookup_recursive_calls (node, e->callee, heap);
758 }
759
760 /* Decide on recursive inlining: in the case function has recursive calls,
761    inline until body size reaches given argument.  If any new indirect edges
762    are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
763    is NULL.  */
764
765 static bool
766 cgraph_decide_recursive_inlining (struct cgraph_node *node,
767                                   VEC (cgraph_edge_p, heap) **new_edges)
768 {
769   int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
770   int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
771   int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY);
772   fibheap_t heap;
773   struct cgraph_edge *e;
774   struct cgraph_node *master_clone, *next;
775   int depth = 0;
776   int n = 0;
777
778   /* It does not make sense to recursively inline always-inline functions
779      as we are going to sorry() on the remaining calls anyway.  */
780   if (node->local.disregard_inline_limits
781       && lookup_attribute ("always_inline", DECL_ATTRIBUTES (node->decl)))
782     return false;
783
784   if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl))
785       || (!flag_inline_functions && !DECL_DECLARED_INLINE_P (node->decl)))
786     return false;
787
788   if (DECL_DECLARED_INLINE_P (node->decl))
789     {
790       limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
791       max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
792     }
793
794   /* Make sure that function is small enough to be considered for inlining.  */
795   if (!max_depth
796       || cgraph_estimate_size_after_inlining (1, node, node)  >= limit)
797     return false;
798   heap = fibheap_new ();
799   lookup_recursive_calls (node, node, heap);
800   if (fibheap_empty (heap))
801     {
802       fibheap_delete (heap);
803       return false;
804     }
805
806   if (dump_file)
807     fprintf (dump_file,
808              "  Performing recursive inlining on %s\n",
809              cgraph_node_name (node));
810
811   /* We need original clone to copy around.  */
812   master_clone = cgraph_clone_node (node, node->decl,
813                                     node->count, CGRAPH_FREQ_BASE, 1,
814                                     false, NULL);
815   master_clone->needed = true;
816   for (e = master_clone->callees; e; e = e->next_callee)
817     if (!e->inline_failed)
818       cgraph_clone_inlined_nodes (e, true, false);
819
820   /* Do the inlining and update list of recursive call during process.  */
821   while (!fibheap_empty (heap)
822          && (cgraph_estimate_size_after_inlining (1, node, master_clone)
823              <= limit))
824     {
825       struct cgraph_edge *curr
826         = (struct cgraph_edge *) fibheap_extract_min (heap);
827       struct cgraph_node *cnode;
828
829       depth = 1;
830       for (cnode = curr->caller;
831            cnode->global.inlined_to; cnode = cnode->callers->caller)
832         if (node->decl == curr->callee->decl)
833           depth++;
834       if (depth > max_depth)
835         {
836           if (dump_file)
837             fprintf (dump_file,
838                      "   maximal depth reached\n");
839           continue;
840         }
841
842       if (max_count)
843         {
844           if (!cgraph_maybe_hot_edge_p (curr))
845             {
846               if (dump_file)
847                 fprintf (dump_file, "   Not inlining cold call\n");
848               continue;
849             }
850           if (curr->count * 100 / node->count < probability)
851             {
852               if (dump_file)
853                 fprintf (dump_file,
854                          "   Probability of edge is too small\n");
855               continue;
856             }
857         }
858
859       if (dump_file)
860         {
861           fprintf (dump_file,
862                    "   Inlining call of depth %i", depth);
863           if (node->count)
864             {
865               fprintf (dump_file, " called approx. %.2f times per call",
866                        (double)curr->count / node->count);
867             }
868           fprintf (dump_file, "\n");
869         }
870       cgraph_redirect_edge_callee (curr, master_clone);
871       cgraph_mark_inline_edge (curr, false, new_edges);
872       lookup_recursive_calls (node, curr->callee, heap);
873       n++;
874     }
875   if (!fibheap_empty (heap) && dump_file)
876     fprintf (dump_file, "    Recursive inlining growth limit met.\n");
877
878   fibheap_delete (heap);
879   if (dump_file)
880     fprintf (dump_file,
881              "\n   Inlined %i times, body grown from size %i to %i, time %i to %i\n", n,
882              master_clone->global.size, node->global.size,
883              master_clone->global.time, node->global.time);
884
885   /* Remove master clone we used for inlining.  We rely that clones inlined
886      into master clone gets queued just before master clone so we don't
887      need recursion.  */
888   for (node = cgraph_nodes; node != master_clone;
889        node = next)
890     {
891       next = node->next;
892       if (node->global.inlined_to == master_clone)
893         cgraph_remove_node (node);
894     }
895   cgraph_remove_node (master_clone);
896   /* FIXME: Recursive inlining actually reduces number of calls of the
897      function.  At this place we should probably walk the function and
898      inline clones and compensate the counts accordingly.  This probably
899      doesn't matter much in practice.  */
900   return n > 0;
901 }
902
903 /* Set inline_failed for all callers of given function to REASON.  */
904
905 static void
906 cgraph_set_inline_failed (struct cgraph_node *node,
907                           cgraph_inline_failed_t reason)
908 {
909   struct cgraph_edge *e;
910
911   if (dump_file)
912     fprintf (dump_file, "Inlining failed: %s\n",
913              cgraph_inline_failed_string (reason));
914   for (e = node->callers; e; e = e->next_caller)
915     if (e->inline_failed)
916       e->inline_failed = reason;
917 }
918
919 /* Given whole compilation unit estimate of INSNS, compute how large we can
920    allow the unit to grow.  */
921 static int
922 compute_max_insns (int insns)
923 {
924   int max_insns = insns;
925   if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
926     max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
927
928   return ((HOST_WIDEST_INT) max_insns
929           * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
930 }
931
932 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP.  */
933 static void
934 add_new_edges_to_heap (fibheap_t heap, VEC (cgraph_edge_p, heap) *new_edges)
935 {
936   while (VEC_length (cgraph_edge_p, new_edges) > 0)
937     {
938       struct cgraph_edge *edge = VEC_pop (cgraph_edge_p, new_edges);
939
940       gcc_assert (!edge->aux);
941       edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge);
942     }
943 }
944
945
946 /* We use greedy algorithm for inlining of small functions:
947    All inline candidates are put into prioritized heap based on estimated
948    growth of the overall number of instructions and then update the estimates.
949
950    INLINED and INLINED_CALEES are just pointers to arrays large enough
951    to be passed to cgraph_inlined_into and cgraph_inlined_callees.  */
952
953 static void
954 cgraph_decide_inlining_of_small_functions (void)
955 {
956   struct cgraph_node *node;
957   struct cgraph_edge *edge;
958   cgraph_inline_failed_t failed_reason;
959   fibheap_t heap = fibheap_new ();
960   bitmap updated_nodes = BITMAP_ALLOC (NULL);
961   int min_size, max_size;
962   VEC (cgraph_edge_p, heap) *new_indirect_edges = NULL;
963
964   if (flag_indirect_inlining)
965     new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8);
966
967   if (dump_file)
968     fprintf (dump_file, "\nDeciding on smaller functions:\n");
969
970   /* Put all inline candidates into the heap.  */
971
972   for (node = cgraph_nodes; node; node = node->next)
973     {
974       if (!node->local.inlinable || !node->callers)
975         continue;
976       if (dump_file)
977         fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
978
979       node->global.estimated_growth = INT_MIN;
980       if (!cgraph_default_inline_p (node, &failed_reason))
981         {
982           cgraph_set_inline_failed (node, failed_reason);
983           continue;
984         }
985
986       for (edge = node->callers; edge; edge = edge->next_caller)
987         if (edge->inline_failed)
988           {
989             gcc_assert (!edge->aux);
990             edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge);
991           }
992     }
993
994   max_size = compute_max_insns (overall_size);
995   min_size = overall_size;
996
997   while (overall_size <= max_size
998          && !fibheap_empty (heap))
999     {
1000       int old_size = overall_size;
1001       struct cgraph_node *where, *callee;
1002       int badness = fibheap_min_key (heap);
1003       int growth;
1004       cgraph_inline_failed_t not_good = CIF_OK;
1005
1006       edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1007       gcc_assert (edge->aux);
1008       edge->aux = NULL;
1009       if (!edge->inline_failed)
1010         continue;
1011 #ifdef ENABLE_CHECKING
1012       gcc_assert (cgraph_edge_badness (edge, false) == badness);
1013 #endif
1014       callee = edge->callee;
1015
1016       growth = (cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee)
1017                 - edge->caller->global.size);
1018
1019       if (dump_file)
1020         {
1021           fprintf (dump_file,
1022                    "\nConsidering %s with %i size\n",
1023                    cgraph_node_name (edge->callee),
1024                    edge->callee->global.size);
1025           fprintf (dump_file,
1026                    " to be inlined into %s in %s:%i\n"
1027                    " Estimated growth after inlined into all callees is %+i insns.\n"
1028                    " Estimated badness is %i, frequency %.2f.\n",
1029                    cgraph_node_name (edge->caller),
1030                    flag_wpa ? "unknown"
1031                    : gimple_filename ((const_gimple) edge->call_stmt),
1032                    flag_wpa ? -1 : gimple_lineno ((const_gimple) edge->call_stmt),
1033                    cgraph_estimate_growth (edge->callee),
1034                    badness,
1035                    edge->frequency / (double)CGRAPH_FREQ_BASE);
1036           if (edge->count)
1037             fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
1038           if (dump_flags & TDF_DETAILS)
1039             cgraph_edge_badness (edge, true);
1040         }
1041
1042       /* When not having profile info ready we don't weight by any way the
1043          position of call in procedure itself.  This means if call of
1044          function A from function B seems profitable to inline, the recursive
1045          call of function A in inline copy of A in B will look profitable too
1046          and we end up inlining until reaching maximal function growth.  This
1047          is not good idea so prohibit the recursive inlining.
1048
1049          ??? When the frequencies are taken into account we might not need this
1050          restriction.
1051
1052          We need to be cureful here, in some testcases, e.g. directivec.c in
1053          libcpp, we can estimate self recursive function to have negative growth
1054          for inlining completely.
1055          */
1056       if (!edge->count)
1057         {
1058           where = edge->caller;
1059           while (where->global.inlined_to)
1060             {
1061               if (where->decl == edge->callee->decl)
1062                 break;
1063               where = where->callers->caller;
1064             }
1065           if (where->global.inlined_to)
1066             {
1067               edge->inline_failed
1068                 = (edge->callee->local.disregard_inline_limits
1069                    ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
1070               if (dump_file)
1071                 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
1072               continue;
1073             }
1074         }
1075
1076       if (edge->callee->local.disregard_inline_limits)
1077         ;
1078       else if (!cgraph_maybe_hot_edge_p (edge))
1079         not_good = CIF_UNLIKELY_CALL;
1080       else if (!flag_inline_functions
1081           && !DECL_DECLARED_INLINE_P (edge->callee->decl))
1082         not_good = CIF_NOT_DECLARED_INLINED;
1083       else if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION(edge->caller->decl)))
1084         not_good = CIF_OPTIMIZING_FOR_SIZE;
1085       if (not_good && growth > 0 && cgraph_estimate_growth (edge->callee) > 0)
1086         {
1087           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1088                                             &edge->inline_failed))
1089             {
1090               edge->inline_failed = not_good;
1091               if (dump_file)
1092                 fprintf (dump_file, " inline_failed:%s.\n",
1093                          cgraph_inline_failed_string (edge->inline_failed));
1094             }
1095           continue;
1096         }
1097       if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
1098         {
1099           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1100                                             &edge->inline_failed))
1101             {
1102               if (dump_file)
1103                 fprintf (dump_file, " inline_failed:%s.\n",
1104                          cgraph_inline_failed_string (edge->inline_failed));
1105             }
1106           continue;
1107         }
1108       if (!tree_can_inline_p (edge))
1109         {
1110           if (dump_file)
1111             fprintf (dump_file, " inline_failed:%s.\n",
1112                      cgraph_inline_failed_string (edge->inline_failed));
1113           continue;
1114         }
1115       if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
1116                                        &edge->inline_failed))
1117         {
1118           where = edge->caller;
1119           if (where->global.inlined_to)
1120             where = where->global.inlined_to;
1121           if (!cgraph_decide_recursive_inlining (where,
1122                                                  flag_indirect_inlining
1123                                                  ? &new_indirect_edges : NULL))
1124             continue;
1125           if (flag_indirect_inlining)
1126             add_new_edges_to_heap (heap, new_indirect_edges);
1127           update_callee_keys (heap, where, updated_nodes);
1128         }
1129       else
1130         {
1131           struct cgraph_node *callee;
1132           if (edge->call_stmt_cannot_inline_p
1133               || !cgraph_check_inline_limits (edge->caller, edge->callee,
1134                                               &edge->inline_failed, true))
1135             {
1136               if (dump_file)
1137                 fprintf (dump_file, " Not inlining into %s:%s.\n",
1138                          cgraph_node_name (edge->caller),
1139                          cgraph_inline_failed_string (edge->inline_failed));
1140               continue;
1141             }
1142           callee = edge->callee;
1143           cgraph_mark_inline_edge (edge, true, &new_indirect_edges);
1144           if (flag_indirect_inlining)
1145             add_new_edges_to_heap (heap, new_indirect_edges);
1146
1147           update_callee_keys (heap, callee, updated_nodes);
1148         }
1149       where = edge->caller;
1150       if (where->global.inlined_to)
1151         where = where->global.inlined_to;
1152
1153       /* Our profitability metric can depend on local properties
1154          such as number of inlinable calls and size of the function body.
1155          After inlining these properties might change for the function we
1156          inlined into (since it's body size changed) and for the functions
1157          called by function we inlined (since number of it inlinable callers
1158          might change).  */
1159       update_caller_keys (heap, where, updated_nodes);
1160
1161       /* We removed one call of the function we just inlined.  If offline
1162          copy is still needed, be sure to update the keys.  */
1163       if (callee != where && !callee->global.inlined_to)
1164         update_caller_keys (heap, callee, updated_nodes);
1165       bitmap_clear (updated_nodes);
1166
1167       if (dump_file)
1168         {
1169           fprintf (dump_file,
1170                    " Inlined into %s which now has size %i and self time %i,"
1171                    "net change of %+i.\n",
1172                    cgraph_node_name (edge->caller),
1173                    edge->caller->global.time,
1174                    edge->caller->global.size,
1175                    overall_size - old_size);
1176         }
1177       if (min_size > overall_size)
1178         {
1179           min_size = overall_size;
1180           max_size = compute_max_insns (min_size);
1181
1182           if (dump_file)
1183             fprintf (dump_file, "New minimal size reached: %i\n", min_size);
1184         }
1185     }
1186   while (!fibheap_empty (heap))
1187     {
1188       int badness = fibheap_min_key (heap);
1189
1190       edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1191       gcc_assert (edge->aux);
1192       edge->aux = NULL;
1193       if (!edge->inline_failed)
1194         continue;
1195 #ifdef ENABLE_CHECKING
1196       gcc_assert (cgraph_edge_badness (edge, false) == badness);
1197 #endif
1198       if (dump_file)
1199         {
1200           fprintf (dump_file,
1201                    "\nSkipping %s with %i size\n",
1202                    cgraph_node_name (edge->callee),
1203                    edge->callee->global.size);
1204           fprintf (dump_file,
1205                    " called by %s in %s:%i\n"
1206                    " Estimated growth after inlined into all callees is %+i insns.\n"
1207                    " Estimated badness is %i, frequency %.2f.\n",
1208                    cgraph_node_name (edge->caller),
1209                    flag_wpa ? "unknown"
1210                    : gimple_filename ((const_gimple) edge->call_stmt),
1211                    flag_wpa ? -1 : gimple_lineno ((const_gimple) edge->call_stmt),
1212                    cgraph_estimate_growth (edge->callee),
1213                    badness,
1214                    edge->frequency / (double)CGRAPH_FREQ_BASE);
1215           if (edge->count)
1216             fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
1217           if (dump_flags & TDF_DETAILS)
1218             cgraph_edge_badness (edge, true);
1219         }
1220       if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
1221           && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
1222                                            &edge->inline_failed))
1223         edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT;
1224     }
1225
1226   if (new_indirect_edges)
1227     VEC_free (cgraph_edge_p, heap, new_indirect_edges);
1228   fibheap_delete (heap);
1229   BITMAP_FREE (updated_nodes);
1230 }
1231
1232 /* Flatten NODE from the IPA inliner.  */
1233
1234 static void
1235 cgraph_flatten (struct cgraph_node *node)
1236 {
1237   struct cgraph_edge *e;
1238
1239   /* We shouldn't be called recursively when we are being processed.  */
1240   gcc_assert (node->aux == NULL);
1241
1242   node->aux = (void *)(size_t) INLINE_ALL;
1243
1244   for (e = node->callees; e; e = e->next_callee)
1245     {
1246       struct cgraph_node *orig_callee;
1247
1248       if (e->call_stmt_cannot_inline_p)
1249         continue;
1250
1251       if (!e->callee->analyzed)
1252         {
1253           if (dump_file)
1254             fprintf (dump_file,
1255                      "Not inlining: Function body not available.\n");
1256           continue;
1257         }
1258
1259       /* We've hit cycle?  It is time to give up.  */
1260       if (e->callee->aux)
1261         {
1262           if (dump_file)
1263             fprintf (dump_file,
1264                      "Not inlining %s into %s to avoid cycle.\n",
1265                      cgraph_node_name (e->callee),
1266                      cgraph_node_name (e->caller));
1267           e->inline_failed = CIF_RECURSIVE_INLINING;
1268           continue;
1269         }
1270
1271       /* When the edge is already inlined, we just need to recurse into
1272          it in order to fully flatten the leaves.  */
1273       if (!e->inline_failed)
1274         {
1275           cgraph_flatten (e->callee);
1276           continue;
1277         }
1278
1279       if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1280         {
1281           if (dump_file)
1282             fprintf (dump_file, "Not inlining: recursive call.\n");
1283           continue;
1284         }
1285
1286       if (!tree_can_inline_p (e))
1287         {
1288           if (dump_file)
1289             fprintf (dump_file, "Not inlining: %s",
1290                      cgraph_inline_failed_string (e->inline_failed));
1291           continue;
1292         }
1293
1294       /* Inline the edge and flatten the inline clone.  Avoid
1295          recursing through the original node if the node was cloned.  */
1296       if (dump_file)
1297         fprintf (dump_file, " Inlining %s into %s.\n",
1298                  cgraph_node_name (e->callee),
1299                  cgraph_node_name (e->caller));
1300       orig_callee = e->callee;
1301       cgraph_mark_inline_edge (e, true, NULL);
1302       if (e->callee != orig_callee)
1303         orig_callee->aux = (void *)(size_t) INLINE_ALL;
1304       cgraph_flatten (e->callee);
1305       if (e->callee != orig_callee)
1306         orig_callee->aux = NULL;
1307     }
1308
1309   node->aux = NULL;
1310 }
1311
1312 /* Decide on the inlining.  We do so in the topological order to avoid
1313    expenses on updating data structures.  */
1314
1315 static unsigned int
1316 cgraph_decide_inlining (void)
1317 {
1318   struct cgraph_node *node;
1319   int nnodes;
1320   struct cgraph_node **order =
1321     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1322   int old_size = 0;
1323   int i;
1324   int initial_size = 0;
1325
1326   cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
1327   if (in_lto_p && flag_indirect_inlining)
1328     ipa_update_after_lto_read ();
1329   if (flag_indirect_inlining)
1330     ipa_create_all_structures_for_iinln ();
1331
1332   max_count = 0;
1333   max_benefit = 0;
1334   for (node = cgraph_nodes; node; node = node->next)
1335     if (node->analyzed)
1336       {
1337         struct cgraph_edge *e;
1338
1339         gcc_assert (inline_summary (node)->self_size == node->global.size);
1340         initial_size += node->global.size;
1341         for (e = node->callees; e; e = e->next_callee)
1342           if (max_count < e->count)
1343             max_count = e->count;
1344         if (max_benefit < inline_summary (node)->time_inlining_benefit)
1345           max_benefit = inline_summary (node)->time_inlining_benefit;
1346       }
1347   gcc_assert (in_lto_p
1348               || !max_count
1349               || (profile_info && flag_branch_probabilities));
1350   overall_size = initial_size;
1351
1352   nnodes = cgraph_postorder (order);
1353
1354   if (dump_file)
1355     fprintf (dump_file,
1356              "\nDeciding on inlining.  Starting with size %i.\n",
1357              initial_size);
1358
1359   for (node = cgraph_nodes; node; node = node->next)
1360     node->aux = 0;
1361
1362   if (dump_file)
1363     fprintf (dump_file, "\nFlattening functions:\n");
1364
1365   /* In the first pass handle functions to be flattened.  Do this with
1366      a priority so none of our later choices will make this impossible.  */
1367   for (i = nnodes - 1; i >= 0; i--)
1368     {
1369       node = order[i];
1370
1371       /* Handle nodes to be flattened, but don't update overall unit
1372          size.  Calling the incremental inliner here is lame,
1373          a simple worklist should be enough.  What should be left
1374          here from the early inliner (if it runs) is cyclic cases.
1375          Ideally when processing callees we stop inlining at the
1376          entry of cycles, possibly cloning that entry point and
1377          try to flatten itself turning it into a self-recursive
1378          function.  */
1379       if (lookup_attribute ("flatten",
1380                             DECL_ATTRIBUTES (node->decl)) != NULL)
1381         {
1382           if (dump_file)
1383             fprintf (dump_file,
1384                      "Flattening %s\n", cgraph_node_name (node));
1385           cgraph_flatten (node);
1386         }
1387     }
1388
1389   cgraph_decide_inlining_of_small_functions ();
1390
1391   if (flag_inline_functions_called_once)
1392     {
1393       if (dump_file)
1394         fprintf (dump_file, "\nDeciding on functions called once:\n");
1395
1396       /* And finally decide what functions are called once.  */
1397       for (i = nnodes - 1; i >= 0; i--)
1398         {
1399           node = order[i];
1400
1401           if (node->callers
1402               && !node->callers->next_caller
1403               && cgraph_only_called_directly_p (node)
1404               && node->local.inlinable
1405               && node->callers->inline_failed
1406               && node->callers->caller != node
1407               && node->callers->caller->global.inlined_to != node
1408               && !node->callers->call_stmt_cannot_inline_p
1409               && !DECL_EXTERNAL (node->decl)
1410               && !DECL_COMDAT (node->decl))
1411             {
1412               cgraph_inline_failed_t reason;
1413               old_size = overall_size;
1414               if (dump_file)
1415                 {
1416                   fprintf (dump_file,
1417                            "\nConsidering %s size %i.\n",
1418                            cgraph_node_name (node), node->global.size);
1419                   fprintf (dump_file,
1420                            " Called once from %s %i insns.\n",
1421                            cgraph_node_name (node->callers->caller),
1422                            node->callers->caller->global.size);
1423                 }
1424
1425               if (cgraph_check_inline_limits (node->callers->caller, node,
1426                                               &reason, false))
1427                 {
1428                   struct cgraph_node *caller = node->callers->caller;
1429                   cgraph_mark_inline (node->callers);
1430                   if (dump_file)
1431                     fprintf (dump_file,
1432                              " Inlined into %s which now has %i size"
1433                              " for a net change of %+i size.\n",
1434                              cgraph_node_name (caller),
1435                              caller->global.size,
1436                              overall_size - old_size);
1437                 }
1438               else
1439                 {
1440                   if (dump_file)
1441                     fprintf (dump_file,
1442                              " Not inlining: %s.\n",
1443                              cgraph_inline_failed_string (reason));
1444                 }
1445             }
1446         }
1447     }
1448
1449   /* Free ipa-prop structures if they are no longer needed.  */
1450   if (flag_indirect_inlining)
1451     ipa_free_all_structures_after_iinln ();
1452
1453   if (dump_file)
1454     fprintf (dump_file,
1455              "\nInlined %i calls, eliminated %i functions, "
1456              "size %i turned to %i size.\n\n",
1457              ncalls_inlined, nfunctions_inlined, initial_size,
1458              overall_size);
1459   free (order);
1460   return 0;
1461 }
1462
1463 /* Return true when N is leaf function.  Accept cheap (pure&const) builtins
1464    in leaf functions.  */
1465 static bool
1466 leaf_node_p (struct cgraph_node *n)
1467 {
1468   struct cgraph_edge *e;
1469   for (e = n->callees; e; e = e->next_callee)
1470     if (!DECL_BUILT_IN (e->callee->decl)
1471         || (!TREE_READONLY (e->callee->decl)
1472             || DECL_PURE_P (e->callee->decl)))
1473       return false;
1474   return true;
1475 }
1476
1477 /* Decide on the inlining.  We do so in the topological order to avoid
1478    expenses on updating data structures.  */
1479
1480 static bool
1481 cgraph_decide_inlining_incrementally (struct cgraph_node *node,
1482                                       enum inlining_mode mode)
1483 {
1484   struct cgraph_edge *e;
1485   bool inlined = false;
1486   cgraph_inline_failed_t failed_reason;
1487
1488 #ifdef ENABLE_CHECKING
1489   verify_cgraph_node (node);
1490 #endif
1491
1492   if (mode != INLINE_ALWAYS_INLINE && mode != INLINE_SIZE_NORECURSIVE
1493       && lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
1494     {
1495       if (dump_file)
1496         fprintf (dump_file, "Incrementally flattening %s\n",
1497                  cgraph_node_name (node));
1498       mode = INLINE_ALL;
1499     }
1500
1501   /* First of all look for always inline functions.  */
1502   if (mode != INLINE_SIZE_NORECURSIVE)
1503     for (e = node->callees; e; e = e->next_callee)
1504       {
1505         if (!e->callee->local.disregard_inline_limits
1506             && (mode != INLINE_ALL || !e->callee->local.inlinable))
1507           continue;
1508         if (e->call_stmt_cannot_inline_p)
1509           continue;
1510         if (dump_file)
1511           fprintf (dump_file,
1512                    "Considering to always inline inline candidate %s.\n",
1513                    cgraph_node_name (e->callee));
1514         if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1515           {
1516             if (dump_file)
1517               fprintf (dump_file, "Not inlining: recursive call.\n");
1518             continue;
1519           }
1520         if (!tree_can_inline_p (e))
1521           {
1522             if (dump_file)
1523               fprintf (dump_file,
1524                        "Not inlining: %s",
1525                        cgraph_inline_failed_string (e->inline_failed));
1526             continue;
1527           }
1528         if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1529             != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1530           {
1531             if (dump_file)
1532               fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1533             continue;
1534           }
1535         if (!e->callee->analyzed)
1536           {
1537             if (dump_file)
1538               fprintf (dump_file,
1539                        "Not inlining: Function body no longer available.\n");
1540             continue;
1541           }
1542
1543         if (dump_file)
1544           fprintf (dump_file, " Inlining %s into %s.\n",
1545                    cgraph_node_name (e->callee),
1546                    cgraph_node_name (e->caller));
1547         cgraph_mark_inline (e);
1548         inlined = true;
1549       }
1550
1551   /* Now do the automatic inlining.  */
1552   if (mode != INLINE_ALL && mode != INLINE_ALWAYS_INLINE
1553       /* Never inline regular functions into always-inline functions
1554          during incremental inlining.  */
1555       && !node->local.disregard_inline_limits)
1556     {
1557       bitmap visited = BITMAP_ALLOC (NULL);
1558       for (e = node->callees; e; e = e->next_callee)
1559         {
1560           int allowed_growth = 0;
1561           if (!e->callee->local.inlinable
1562               || !e->inline_failed
1563               || e->callee->local.disregard_inline_limits)
1564             continue;
1565           /* We are inlining a function to all call-sites in node
1566              or to none.  So visit each candidate only once.  */
1567           if (!bitmap_set_bit (visited, e->callee->uid))
1568             continue;
1569           if (dump_file)
1570             fprintf (dump_file, "Considering inline candidate %s.\n",
1571                      cgraph_node_name (e->callee));
1572           if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1573             {
1574               if (dump_file)
1575                 fprintf (dump_file, "Not inlining: recursive call.\n");
1576               continue;
1577             }
1578           if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1579               != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1580             {
1581               if (dump_file)
1582                 fprintf (dump_file,
1583                          "Not inlining: SSA form does not match.\n");
1584               continue;
1585             }
1586
1587           if (cgraph_maybe_hot_edge_p (e) && leaf_node_p (e->callee)
1588               && optimize_function_for_speed_p (cfun))
1589             allowed_growth = PARAM_VALUE (PARAM_EARLY_INLINING_INSNS);
1590
1591           /* When the function body would grow and inlining the function
1592              won't eliminate the need for offline copy of the function,
1593              don't inline.  */
1594           if (((mode == INLINE_SIZE || mode == INLINE_SIZE_NORECURSIVE)
1595                || (!flag_inline_functions
1596                    && !DECL_DECLARED_INLINE_P (e->callee->decl)))
1597               && (cgraph_estimate_size_after_inlining (1, e->caller, e->callee)
1598                   > e->caller->global.size + allowed_growth)
1599               && cgraph_estimate_growth (e->callee) > allowed_growth)
1600             {
1601               if (dump_file)
1602                 fprintf (dump_file,
1603                          "Not inlining: code size would grow by %i.\n",
1604                          cgraph_estimate_size_after_inlining (1, e->caller,
1605                                                               e->callee)
1606                          - e->caller->global.size);
1607               continue;
1608             }
1609           if (!cgraph_check_inline_limits (node, e->callee, &e->inline_failed,
1610                                            false)
1611               || e->call_stmt_cannot_inline_p)
1612             {
1613               if (dump_file)
1614                 fprintf (dump_file, "Not inlining: %s.\n",
1615                          cgraph_inline_failed_string (e->inline_failed));
1616               continue;
1617             }
1618           if (!e->callee->analyzed)
1619             {
1620               if (dump_file)
1621                 fprintf (dump_file,
1622                          "Not inlining: Function body no longer available.\n");
1623               continue;
1624             }
1625           if (!tree_can_inline_p (e))
1626             {
1627               if (dump_file)
1628                 fprintf (dump_file,
1629                          "Not inlining: %s.",
1630                          cgraph_inline_failed_string (e->inline_failed));
1631               continue;
1632             }
1633           if (cgraph_default_inline_p (e->callee, &failed_reason))
1634             {
1635               if (dump_file)
1636                 fprintf (dump_file, " Inlining %s into %s.\n",
1637                          cgraph_node_name (e->callee),
1638                          cgraph_node_name (e->caller));
1639               cgraph_mark_inline (e);
1640               inlined = true;
1641             }
1642         }
1643       BITMAP_FREE (visited);
1644     }
1645   return inlined;
1646 }
1647
1648 /* Because inlining might remove no-longer reachable nodes, we need to
1649    keep the array visible to garbage collector to avoid reading collected
1650    out nodes.  */
1651 static int nnodes;
1652 static GTY ((length ("nnodes"))) struct cgraph_node **order;
1653
1654 /* Do inlining of small functions.  Doing so early helps profiling and other
1655    passes to be somewhat more effective and avoids some code duplication in
1656    later real inlining pass for testcases with very many function calls.  */
1657 static unsigned int
1658 cgraph_early_inlining (void)
1659 {
1660   struct cgraph_node *node = cgraph_node (current_function_decl);
1661   unsigned int todo = 0;
1662   int iterations = 0;
1663
1664   if (sorrycount || errorcount)
1665     return 0;
1666
1667   if (!optimize
1668       || flag_no_inline
1669       || !flag_early_inlining)
1670     {
1671       /* When not optimizing or not inlining inline only always-inline
1672          functions.  */
1673       cgraph_decide_inlining_incrementally (node, INLINE_ALWAYS_INLINE);
1674       timevar_push (TV_INTEGRATION);
1675       todo |= optimize_inline_calls (current_function_decl);
1676       timevar_pop (TV_INTEGRATION);
1677     }
1678   else
1679     {
1680       /* We iterate incremental inlining to get trivial cases of indirect
1681          inlining.  */
1682       while (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS)
1683              && cgraph_decide_inlining_incrementally (node,
1684                                                       iterations
1685                                                       ? INLINE_SIZE_NORECURSIVE
1686                                                       : INLINE_SIZE))
1687         {
1688           timevar_push (TV_INTEGRATION);
1689           todo |= optimize_inline_calls (current_function_decl);
1690           iterations++;
1691           timevar_pop (TV_INTEGRATION);
1692         }
1693       if (dump_file)
1694         fprintf (dump_file, "Iterations: %i\n", iterations);
1695     }
1696
1697   cfun->always_inline_functions_inlined = true;
1698
1699   return todo;
1700 }
1701
1702 struct gimple_opt_pass pass_early_inline =
1703 {
1704  {
1705   GIMPLE_PASS,
1706   "einline",                            /* name */
1707   NULL,                                 /* gate */
1708   cgraph_early_inlining,                /* execute */
1709   NULL,                                 /* sub */
1710   NULL,                                 /* next */
1711   0,                                    /* static_pass_number */
1712   TV_INLINE_HEURISTICS,                 /* tv_id */
1713   0,                                    /* properties_required */
1714   0,                                    /* properties_provided */
1715   0,                                    /* properties_destroyed */
1716   0,                                    /* todo_flags_start */
1717   TODO_dump_func                        /* todo_flags_finish */
1718  }
1719 };
1720
1721 /* When inlining shall be performed.  */
1722 static bool
1723 cgraph_gate_ipa_early_inlining (void)
1724 {
1725   return (flag_early_inlining
1726           && !in_lto_p
1727           && (flag_branch_probabilities || flag_test_coverage
1728               || profile_arc_flag));
1729 }
1730
1731 /* IPA pass wrapper for early inlining pass.  We need to run early inlining
1732    before tree profiling so we have stand alone IPA pass for doing so.  */
1733 struct simple_ipa_opt_pass pass_ipa_early_inline =
1734 {
1735  {
1736   SIMPLE_IPA_PASS,
1737   "einline_ipa",                        /* name */
1738   cgraph_gate_ipa_early_inlining,       /* gate */
1739   NULL,                                 /* execute */
1740   NULL,                                 /* sub */
1741   NULL,                                 /* next */
1742   0,                                    /* static_pass_number */
1743   TV_INLINE_HEURISTICS,                 /* tv_id */
1744   0,                                    /* properties_required */
1745   0,                                    /* properties_provided */
1746   0,                                    /* properties_destroyed */
1747   0,                                    /* todo_flags_start */
1748   TODO_dump_cgraph                      /* todo_flags_finish */
1749  }
1750 };
1751
1752 /* See if statement might disappear after inlining.  We are not terribly
1753    sophisficated, basically looking for simple abstraction penalty wrappers.  */
1754
1755 static bool
1756 likely_eliminated_by_inlining_p (gimple stmt)
1757 {
1758   enum gimple_code code = gimple_code (stmt);
1759   switch (code)
1760     {
1761       case GIMPLE_RETURN:
1762         return true;
1763       case GIMPLE_ASSIGN:
1764         if (gimple_num_ops (stmt) != 2)
1765           return false;
1766
1767         /* Casts of parameters, loads from parameters passed by reference
1768            and stores to return value or parameters are probably free after
1769            inlining.  */
1770         if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR
1771             || gimple_assign_rhs_code (stmt) == NOP_EXPR
1772             || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
1773             || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
1774           {
1775             tree rhs = gimple_assign_rhs1 (stmt);
1776             tree lhs = gimple_assign_lhs (stmt);
1777             tree inner_rhs = rhs;
1778             tree inner_lhs = lhs;
1779             bool rhs_free = false;
1780             bool lhs_free = false;
1781
1782             while (handled_component_p (inner_lhs) || TREE_CODE (inner_lhs) == INDIRECT_REF)
1783               inner_lhs = TREE_OPERAND (inner_lhs, 0);
1784             while (handled_component_p (inner_rhs)
1785                    || TREE_CODE (inner_rhs) == ADDR_EXPR || TREE_CODE (inner_rhs) == INDIRECT_REF)
1786               inner_rhs = TREE_OPERAND (inner_rhs, 0);
1787
1788
1789             if (TREE_CODE (inner_rhs) == PARM_DECL
1790                 || (TREE_CODE (inner_rhs) == SSA_NAME
1791                     && SSA_NAME_IS_DEFAULT_DEF (inner_rhs)
1792                     && TREE_CODE (SSA_NAME_VAR (inner_rhs)) == PARM_DECL))
1793               rhs_free = true;
1794             if (rhs_free && is_gimple_reg (lhs))
1795               lhs_free = true;
1796             if (((TREE_CODE (inner_lhs) == PARM_DECL
1797                   || (TREE_CODE (inner_lhs) == SSA_NAME
1798                       && SSA_NAME_IS_DEFAULT_DEF (inner_lhs)
1799                       && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == PARM_DECL))
1800                  && inner_lhs != lhs)
1801                 || TREE_CODE (inner_lhs) == RESULT_DECL
1802                 || (TREE_CODE (inner_lhs) == SSA_NAME
1803                     && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == RESULT_DECL))
1804               lhs_free = true;
1805             if (lhs_free && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
1806               rhs_free = true;
1807             if (lhs_free && rhs_free)
1808               return true;
1809           }
1810         return false;
1811       default:
1812         return false;
1813     }
1814 }
1815
1816 /* Compute function body size parameters for NODE.  */
1817
1818 static void
1819 estimate_function_body_sizes (struct cgraph_node *node)
1820 {
1821   gcov_type time = 0;
1822   gcov_type time_inlining_benefit = 0;
1823   int size = 0;
1824   int size_inlining_benefit = 0;
1825   basic_block bb;
1826   gimple_stmt_iterator bsi;
1827   struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1828   tree arg;
1829   int freq;
1830   tree funtype = TREE_TYPE (node->decl);
1831
1832   if (node->local.disregard_inline_limits)
1833     {
1834       inline_summary (node)->self_time = 0;
1835       inline_summary (node)->self_size = 0;
1836       inline_summary (node)->time_inlining_benefit = 0;
1837       inline_summary (node)->size_inlining_benefit = 0;
1838     }
1839
1840   if (dump_file)
1841     fprintf (dump_file, "Analyzing function body size: %s\n",
1842              cgraph_node_name (node));
1843
1844   gcc_assert (my_function && my_function->cfg);
1845   FOR_EACH_BB_FN (bb, my_function)
1846     {
1847       freq = compute_call_stmt_bb_frequency (node->decl, bb);
1848       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1849         {
1850           gimple stmt = gsi_stmt (bsi);
1851           int this_size = estimate_num_insns (stmt, &eni_size_weights);
1852           int this_time = estimate_num_insns (stmt, &eni_time_weights);
1853
1854           if (dump_file && (dump_flags & TDF_DETAILS))
1855             {
1856               fprintf (dump_file, "  freq:%6i size:%3i time:%3i ",
1857                        freq, this_size, this_time);
1858               print_gimple_stmt (dump_file, stmt, 0, 0);
1859             }
1860           this_time *= freq;
1861           time += this_time;
1862           size += this_size;
1863           if (likely_eliminated_by_inlining_p (stmt))
1864             {
1865               size_inlining_benefit += this_size;
1866               time_inlining_benefit += this_time;
1867               if (dump_file && (dump_flags & TDF_DETAILS))
1868                 fprintf (dump_file, "    Likely eliminated\n");
1869             }
1870           gcc_assert (time >= 0);
1871           gcc_assert (size >= 0);
1872         }
1873     }
1874   time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
1875   time_inlining_benefit = ((time_inlining_benefit + CGRAPH_FREQ_BASE / 2)
1876                            / CGRAPH_FREQ_BASE);
1877   if (dump_file)
1878     fprintf (dump_file, "Overall function body time: %i-%i size: %i-%i\n",
1879              (int)time, (int)time_inlining_benefit,
1880              size, size_inlining_benefit);
1881   time_inlining_benefit += eni_time_weights.call_cost;
1882   size_inlining_benefit += eni_size_weights.call_cost;
1883   if (!VOID_TYPE_P (TREE_TYPE (funtype)))
1884     {
1885       int cost = estimate_move_cost (TREE_TYPE (funtype));
1886       time_inlining_benefit += cost;
1887       size_inlining_benefit += cost;
1888     }
1889   for (arg = DECL_ARGUMENTS (node->decl); arg; arg = TREE_CHAIN (arg))
1890     if (!VOID_TYPE_P (TREE_TYPE (arg)))
1891       {
1892         int cost = estimate_move_cost (TREE_TYPE (arg));
1893         time_inlining_benefit += cost;
1894         size_inlining_benefit += cost;
1895       }
1896   if (time_inlining_benefit > MAX_TIME)
1897     time_inlining_benefit = MAX_TIME;
1898   if (time > MAX_TIME)
1899     time = MAX_TIME;
1900   inline_summary (node)->self_time = time;
1901   inline_summary (node)->self_size = size;
1902   if (dump_file)
1903     fprintf (dump_file, "With function call overhead time: %i-%i size: %i-%i\n",
1904              (int)time, (int)time_inlining_benefit,
1905              size, size_inlining_benefit);
1906   inline_summary (node)->time_inlining_benefit = time_inlining_benefit;
1907   inline_summary (node)->size_inlining_benefit = size_inlining_benefit;
1908 }
1909
1910 /* Compute parameters of functions used by inliner.  */
1911 unsigned int
1912 compute_inline_parameters (struct cgraph_node *node)
1913 {
1914   HOST_WIDE_INT self_stack_size;
1915
1916   gcc_assert (!node->global.inlined_to);
1917
1918   /* Estimate the stack size for the function.  But not at -O0
1919      because estimated_stack_frame_size is a quadratic problem.  */
1920   self_stack_size = optimize ? estimated_stack_frame_size () : 0;
1921   inline_summary (node)->estimated_self_stack_size = self_stack_size;
1922   node->global.estimated_stack_size = self_stack_size;
1923   node->global.stack_frame_offset = 0;
1924
1925   /* Can this function be inlined at all?  */
1926   node->local.inlinable = tree_inlinable_function_p (node->decl);
1927   if (node->local.inlinable && !node->local.disregard_inline_limits)
1928     node->local.disregard_inline_limits
1929       = DECL_DISREGARD_INLINE_LIMITS (node->decl);
1930   estimate_function_body_sizes (node);
1931   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
1932   node->global.time = inline_summary (node)->self_time;
1933   node->global.size = inline_summary (node)->self_size;
1934   return 0;
1935 }
1936
1937
1938 /* Compute parameters of functions used by inliner using
1939    current_function_decl.  */
1940 static unsigned int
1941 compute_inline_parameters_for_current (void)
1942 {
1943   compute_inline_parameters (cgraph_node (current_function_decl));
1944   return 0;
1945 }
1946
1947 struct gimple_opt_pass pass_inline_parameters =
1948 {
1949  {
1950   GIMPLE_PASS,
1951   "inline_param",                       /* name */
1952   NULL,                                 /* gate */
1953   compute_inline_parameters_for_current,/* execute */
1954   NULL,                                 /* sub */
1955   NULL,                                 /* next */
1956   0,                                    /* static_pass_number */
1957   TV_INLINE_HEURISTICS,                 /* tv_id */
1958   0,                                    /* properties_required */
1959   0,                                    /* properties_provided */
1960   0,                                    /* properties_destroyed */
1961   0,                                    /* todo_flags_start */
1962   0                                     /* todo_flags_finish */
1963  }
1964 };
1965
1966 /* This function performs intraprocedural analyzis in NODE that is required to
1967    inline indirect calls.  */
1968 static void
1969 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
1970 {
1971   struct cgraph_edge *cs;
1972
1973   if (!flag_ipa_cp)
1974     {
1975       ipa_initialize_node_params (node);
1976       ipa_detect_param_modifications (node);
1977     }
1978   ipa_analyze_params_uses (node);
1979
1980   if (!flag_ipa_cp)
1981     for (cs = node->callees; cs; cs = cs->next_callee)
1982       {
1983         ipa_count_arguments (cs);
1984         ipa_compute_jump_functions (cs);
1985       }
1986
1987   if (dump_file)
1988     {
1989       ipa_print_node_params (dump_file, node);
1990       ipa_print_node_jump_functions (dump_file, node);
1991     }
1992 }
1993
1994 /* Note function body size.  */
1995 static void
1996 analyze_function (struct cgraph_node *node)
1997 {
1998   push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1999   current_function_decl = node->decl;
2000
2001   compute_inline_parameters (node);
2002   if (flag_indirect_inlining)
2003     inline_indirect_intraprocedural_analysis (node);
2004
2005   current_function_decl = NULL;
2006   pop_cfun ();
2007 }
2008
2009 /* Called when new function is inserted to callgraph late.  */
2010 static void
2011 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2012 {
2013   analyze_function (node);
2014 }
2015
2016 /* Note function body size.  */
2017 static void
2018 inline_generate_summary (void)
2019 {
2020   struct cgraph_node *node;
2021
2022   function_insertion_hook_holder =
2023       cgraph_add_function_insertion_hook (&add_new_function, NULL);
2024
2025   if (flag_indirect_inlining)
2026     {
2027       ipa_register_cgraph_hooks ();
2028       ipa_check_create_node_params ();
2029       ipa_check_create_edge_args ();
2030     }
2031
2032   for (node = cgraph_nodes; node; node = node->next)
2033     if (node->analyzed)
2034       analyze_function (node);
2035
2036   return;
2037 }
2038
2039 /* Apply inline plan to function.  */
2040 static unsigned int
2041 inline_transform (struct cgraph_node *node)
2042 {
2043   unsigned int todo = 0;
2044   struct cgraph_edge *e;
2045
2046   /* FIXME: Currently the passmanager is adding inline transform more than once to some
2047      clones.  This needs revisiting after WPA cleanups.  */
2048   if (cfun->after_inlining)
2049     return 0;
2050
2051   /* We might need the body of this function so that we can expand
2052      it inline somewhere else.  */
2053   if (cgraph_preserve_function_body_p (node->decl))
2054     save_inline_function_body (node);
2055
2056   for (e = node->callees; e; e = e->next_callee)
2057     if (!e->inline_failed || warn_inline)
2058       break;
2059
2060   if (e)
2061     {
2062       timevar_push (TV_INTEGRATION);
2063       todo = optimize_inline_calls (current_function_decl);
2064       timevar_pop (TV_INTEGRATION);
2065     }
2066   cfun->always_inline_functions_inlined = true;
2067   cfun->after_inlining = true;
2068   return todo | execute_fixup_cfg ();
2069 }
2070
2071 /* Read inline summary.  Jump functions are shared among ipa-cp
2072    and inliner, so when ipa-cp is active, we don't need to write them
2073    twice.  */
2074
2075 static void
2076 inline_read_summary (void)
2077 {
2078   if (flag_indirect_inlining)
2079     {
2080       ipa_register_cgraph_hooks ();
2081       if (!flag_ipa_cp)
2082         ipa_prop_read_jump_functions ();
2083     }
2084   function_insertion_hook_holder =
2085       cgraph_add_function_insertion_hook (&add_new_function, NULL);
2086 }
2087
2088 /* Write inline summary for node in SET.
2089    Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
2090    active, we don't need to write them twice.  */
2091
2092 static void
2093 inline_write_summary (cgraph_node_set set,
2094                       varpool_node_set vset ATTRIBUTE_UNUSED)
2095 {
2096   if (flag_indirect_inlining && !flag_ipa_cp)
2097     ipa_prop_write_jump_functions (set);
2098 }
2099
2100 /* When to run IPA inlining.  Inlining of always-inline functions
2101    happens during early inlining.  */
2102
2103 static bool
2104 gate_cgraph_decide_inlining (void)
2105 {
2106   /* ???  We'd like to skip this if not optimizing or not inlining as
2107      all always-inline functions have been processed by early
2108      inlining already.  But this at least breaks EH with C++ as
2109      we need to unconditionally run fixup_cfg even at -O0.
2110      So leave it on unconditionally for now.  */
2111   return 1;
2112 }
2113
2114 struct ipa_opt_pass_d pass_ipa_inline =
2115 {
2116  {
2117   IPA_PASS,
2118   "inline",                             /* name */
2119   gate_cgraph_decide_inlining,          /* gate */
2120   cgraph_decide_inlining,               /* execute */
2121   NULL,                                 /* sub */
2122   NULL,                                 /* next */
2123   0,                                    /* static_pass_number */
2124   TV_INLINE_HEURISTICS,                 /* tv_id */
2125   0,                                    /* properties_required */
2126   0,                                    /* properties_provided */
2127   0,                                    /* properties_destroyed */
2128   TODO_remove_functions,                /* todo_flags_finish */
2129   TODO_dump_cgraph | TODO_dump_func
2130   | TODO_remove_functions | TODO_ggc_collect    /* todo_flags_finish */
2131  },
2132  inline_generate_summary,               /* generate_summary */
2133  inline_write_summary,                  /* write_summary */
2134  inline_read_summary,                   /* read_summary */
2135  NULL,                                  /* write_optimization_summary */
2136  NULL,                                  /* read_optimization_summary */
2137  NULL,                                  /* stmt_fixup */
2138  0,                                     /* TODOs */
2139  inline_transform,                      /* function_transform */
2140  NULL,                                  /* variable_transform */
2141 };
2142
2143
2144 #include "gt-ipa-inline.h"