OSDN Git Service

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