OSDN Git Service

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