OSDN Git Service

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