OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [ipa-inline.c] - Blame information for rev 280

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.