gcc/ipa-inline-analysis.c

   1 /* Inlining decision heuristics.
   2    Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010, 2011
   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 /* Analysis used by the inliner and other passes limiting code size growth.
  23
  24    We estimate for each function
  25      - function body size
  26      - average function execution time
  27      - inlining size benefit (that is how much of function body size
  28        and its call sequence is expected to disappear by inlining)
  29      - inlining time benefit
  30      - function frame size
  31    For each call
  32      - call statement size and time
  33
  34    inlinie_summary datastructures store above information locally (i.e.
  35    parameters of the function itself) and globally (i.e. parameters of
  36    the function created by applying all the inline decisions already
  37    present in the callgraph).
  38
  39    We provide accestor to the inline_summary datastructure and
  40    basic logic updating the parameters when inlining is performed.
  41
  42    The summaries are context sensitive.  Context means
  43      1) partial assignment of known constant values of operands
  44      2) whether function is inlined into the call or not.
  45    It is easy to add more variants.  To represent function size and time
  46    that depends on context (i.e. it is known to be optimized away when
  47    context is known either by inlining or from IP-CP and clonning),
  48    we use predicates. Predicates are logical formulas in
  49    conjunctive-disjunctive form consisting of clauses. Clauses are bitmaps
  50    specifying what conditions must be true. Conditions are simple test
  51    of the form described above.
  52
  53    In order to make predicate (possibly) true, all of its clauses must
  54    be (possibly) true. To make clause (possibly) true, one of conditions
  55    it mentions must be (possibly) true.  There are fixed bounds on
  56    number of clauses and conditions and all the manipulation functions
  57    are conservative in positive direction. I.e. we may lose precision
  58    by thinking that predicate may be true even when it is not.
  59
  60    estimate_edge_size and estimate_edge_growth can be used to query
  61    function size/time in the given context.  inline_merge_summary merges
  62    properties of caller and callee after inlining.
  63
  64    Finally pass_inline_parameters is exported.  This is used to drive
  65    computation of function parameters used by the early inliner. IPA
  66    inlined performs analysis via its analyze_function method. */
  67
  68 #include "config.h"
  69 #include "system.h"
  70 #include "coretypes.h"
  71 #include "tm.h"
  72 #include "tree.h"
  73 #include "tree-inline.h"
  74 #include "langhooks.h"
  75 #include "flags.h"
  76 #include "cgraph.h"
  77 #include "diagnostic.h"
  78 #include "gimple-pretty-print.h"
  79 #include "timevar.h"
  80 #include "params.h"
  81 #include "tree-pass.h"
  82 #include "coverage.h"
  83 #include "ggc.h"
  84 #include "tree-flow.h"
  85 #include "ipa-prop.h"
  86 #include "lto-streamer.h"
  87 #include "ipa-inline.h"
  88
  89 /* Estimate runtime of function can easilly run into huge numbers with many
  90    nested loops.  Be sure we can compute time * INLINE_SIZE_SCALE in integer.
  91    For anything larger we use gcov_type.  */
  92 #define MAX_TIME 1000000
  93
  94 /* Number of bits in integer, but we really want to be stable across different
  95    hosts.  */
  96 #define NUM_CONDITIONS 32
  97
  98 enum predicate_conditions
  99 {
 100   predicate_false_condition = 0,
 101   predicate_not_inlined_condition = 1,
 102   predicate_first_dynamic_condition = 2
 103 };
 104
 105 /* Special condition code we use to represent test that operand is compile time
 106    constant.  */
 107 #define IS_NOT_CONSTANT ERROR_MARK
 108
 109 /* Holders of ipa cgraph hooks: */
 110 static struct cgraph_node_hook_list *function_insertion_hook_holder;
 111 static struct cgraph_node_hook_list *node_removal_hook_holder;
 112 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
 113 static struct cgraph_edge_hook_list *edge_removal_hook_holder;
 114 static void inline_node_removal_hook (struct cgraph_node *, void *);
 115 static void inline_node_duplication_hook (struct cgraph_node *,
 116                                           struct cgraph_node *, void *);
 117
 118 /* VECtor holding inline summaries.
 119    In GGC memory because conditions might point to constant trees.  */
 120 VEC(inline_summary_t,gc) *inline_summary_vec;
 121
 122 /* Cached node/edge growths.  */
 123 VEC(int,heap) *node_growth_cache;
 124 VEC(edge_growth_cache_entry,heap) *edge_growth_cache;
 125
 126
 127 /* Return true predicate (tautology).
 128    We represent it by empty list of clauses.  */
 129
 130 static inline struct predicate
 131 true_predicate (void)
 132 {
 133   struct predicate p;
 134   p.clause[0]=0;
 135   return p;
 136 }
 137
 138
 139 /* Return predicate testing single condition number COND.  */
 140
 141 static inline struct predicate
 142 single_cond_predicate (int cond)
 143 {
 144   struct predicate p;
 145   p.clause[0]=1 << cond;
 146   p.clause[1]=0;
 147   return p;
 148 }
 149
 150
 151 /* Return false predicate.  First clause require false condition.  */
 152
 153 static inline struct predicate
 154 false_predicate (void)
 155 {
 156   return single_cond_predicate (predicate_false_condition);
 157 }
 158
 159
 160 /* Return predicate that is set true when function is not inlined.  */
 161 static inline struct predicate
 162 not_inlined_predicate (void)
 163 {
 164   return single_cond_predicate (predicate_not_inlined_condition);
 165 }
 166
 167
 168 /* Add condition to condition list CONDS.  */
 169
 170 static struct predicate
 171 add_condition (struct inline_summary *summary, int operand_num,
 172                enum tree_code code, tree val)
 173 {
 174   int i;
 175   struct condition *c;
 176   struct condition new_cond;
 177
 178   for (i = 0; VEC_iterate (condition, summary->conds, i, c); i++)
 179     {
 180       if (c->operand_num == operand_num
 181           && c->code == code
 182           && c->val == val)
 183         return single_cond_predicate (i + predicate_first_dynamic_condition);
 184     }
 185   /* Too many conditions.  Give up and return constant true.  */
 186   if (i == NUM_CONDITIONS - predicate_first_dynamic_condition)
 187     return true_predicate ();
 188
 189   new_cond.operand_num = operand_num;
 190   new_cond.code = code;
 191   new_cond.val = val;
 192   VEC_safe_push (condition, gc, summary->conds, &new_cond);
 193   return single_cond_predicate (i + predicate_first_dynamic_condition);
 194 }
 195
 196
 197 /* Add clause CLAUSE into the predicate.  */
 198
 199 static inline void
 200 add_clause (struct predicate *p, clause_t clause)
 201 {
 202   int i;
 203   int insert_here = 0;
 204   /* True clause.  */
 205   if (!clause)
 206     return;
 207
 208   /* Flase clause makes the whole predicate false.  Kill the other variants.  */
 209   if (clause & (1 << predicate_false_condition))
 210     {
 211       p->clause[0] = (1 << predicate_false_condition);
 212       p->clause[1] = 0;
 213     }
 214   for (i = 0; i < MAX_CLAUSES; i++)
 215     {
 216       if (p->clause[i] == clause)
 217         return;
 218       if (!p->clause[i])
 219         break;
 220       if (p->clause[i] < clause && !insert_here)
 221         insert_here = i;
 222     }
 223   /* We run out of variants.  Be conservative in positive direciton.  */
 224   if (i == MAX_CLAUSES)
 225     return;
 226   /* Keep clauses ordered by index, so equivalence testing is easy.  */
 227   p->clause[i + 1] = 0;
 228   for (;i > insert_here; i--)
 229     p->clause[i] = p->clause[i - 1];
 230   p->clause[insert_here] = clause;
 231 }
 232
 233
 234 /* Return P & P2.  */
 235
 236 static struct predicate
 237 and_predicates (struct predicate *p, struct predicate *p2)
 238 {
 239   struct predicate out = *p;
 240   int i;
 241   for (i = 0; p2->clause[i]; i++)
 242     add_clause (&out, p2->clause[i]);
 243   return out;
 244 }
 245
 246
 247 /* Return P | P2.  */
 248
 249 static struct predicate
 250 or_predicates (struct predicate *p, struct predicate *p2)
 251 {
 252   struct predicate out = true_predicate ();
 253   int i,j;
 254   /* If one of conditions is false, return the other.  */
 255   if (p2->clause[0] == 1 << predicate_false_condition)
 256     {
 257       gcc_checking_assert (!p2->clause[1]);
 258       return *p;
 259     }
 260   if (p->clause[0] == 1 << predicate_false_condition)
 261     {
 262       gcc_checking_assert (!p->clause[1]);
 263       return *p2;
 264     }
 265   for (i = 0; p->clause[i]; i++)
 266     for (j = 0; p2->clause[j]; j++)
 267       add_clause (&out, p->clause[i] | p2->clause[j]);
 268   return out;
 269 }
 270
 271
 272 /* Return true if predicates are obviously equal.  */
 273
 274 static inline bool
 275 predicates_equal_p (struct predicate *p, struct predicate *p2)
 276 {
 277   int i;
 278   for (i = 0; p->clause[i]; i++)
 279     if (p->clause[i] != p2->clause[i])
 280       return false;
 281   return !p2->clause[i];
 282 }
 283
 284
 285 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false if predicate P
 286    to be false.  */
 287
 288 static bool
 289 evaulate_predicate (struct predicate *p, clause_t possible_truths)
 290 {
 291   int i;
 292
 293   /* True remains true.  */
 294   if (!p->clause[0])
 295     return true;
 296
 297   /* See if we can find clause we can disprove.  */
 298   for (i = 0; p->clause[i]; i++)
 299     if (!(p->clause[i] & possible_truths))
 300       return false;
 301   return true;
 302 }
 303
 304
 305 /* Dump conditional COND.  */
 306
 307 static void
 308 dump_condition (FILE *f, conditions conditions, int cond)
 309 {
 310   condition *c;
 311   if (cond == predicate_false_condition)
 312     fprintf (f, "false");
 313   else if (cond == predicate_not_inlined_condition)
 314     fprintf (f, "not inlined");
 315   else
 316     {
 317       c = VEC_index (condition, conditions, cond - predicate_first_dynamic_condition);
 318       fprintf (f, "op%i", c->operand_num);
 319       if (c->code == IS_NOT_CONSTANT)
 320         {
 321           fprintf (f, " not constant");
 322           return;
 323         }
 324       fprintf (f, " %s ", op_symbol_code (c->code));
 325       print_generic_expr (f, c->val, 1);
 326     }
 327 }
 328
 329
 330 /* Dump clause CLAUSE.  */
 331
 332 static void
 333 dump_clause (FILE *f, conditions conds, clause_t clause)
 334 {
 335   int i;
 336   bool found = false;
 337   fprintf (f, "(");
 338   if (!clause)
 339     fprintf (f, "true");
 340   for (i = 0; i < NUM_CONDITIONS; i++)
 341     if (clause & (1 << i))
 342       {
 343         if (found)
 344           fprintf (f, " || ");
 345         found = true;
 346         dump_condition (f, conds, i);
 347       }
 348   fprintf (f, ")");
 349 }
 350
 351
 352 /* Dump predicate PREDICATE.  */
 353
 354 static void
 355 dump_predicate (FILE *f, conditions conds, struct predicate *pred)
 356 {
 357   int i;
 358   if (!pred->clause[0])
 359     dump_clause (f, conds, 0);
 360   else
 361     for (i = 0; pred->clause[i]; i++)
 362       {
 363         if (i)
 364           fprintf (f, " && ");
 365         dump_clause (f, conds, pred->clause[i]);
 366       }
 367   fprintf (f, "\n");
 368 }
 369
 370
 371 /* Record SIZE and TIME under condition PRED into the inline summary.  */
 372
 373 static void
 374 account_size_time (struct inline_summary *summary, int size, int time, struct predicate *pred)
 375 {
 376   size_time_entry *e;
 377   bool found = false;
 378   int i;
 379
 380   if (pred->clause[0] == (1 << predicate_false_condition))
 381     return;
 382
 383   /* We need to create initial empty unconitional clause, but otherwie
 384      we don't need to account empty times and sizes.  */
 385   if (!size && !time && summary->conds)
 386     return;
 387
 388   /* Watch overflow that might result from insane profiles.  */
 389   if (time > MAX_TIME * INLINE_TIME_SCALE)
 390     time = MAX_TIME * INLINE_TIME_SCALE;
 391   gcc_assert (time >= 0);
 392
 393   for (i = 0; VEC_iterate (size_time_entry, summary->entry, i, e); i++)
 394     if (predicates_equal_p (&e->predicate, pred))
 395       {
 396         found = true;
 397         break;
 398       }
 399   if (i == 32)
 400     {
 401       i = 0;
 402       found = true;
 403       e = VEC_index (size_time_entry, summary->entry, 0);
 404       gcc_assert (!e->predicate.clause[0]);
 405     }
 406   if (dump_file && (dump_flags & TDF_DETAILS) && (time || size))
 407     {
 408       fprintf (dump_file, "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
 409                ((double)size) / INLINE_SIZE_SCALE, ((double)time) / INLINE_TIME_SCALE,
 410                found ? "" : "new ");
 411       dump_predicate (dump_file, summary->conds, pred);
 412     }
 413   if (!found)
 414     {
 415       struct size_time_entry new_entry;
 416       new_entry.size = size;
 417       new_entry.time = time;
 418       new_entry.predicate = *pred;
 419       VEC_safe_push (size_time_entry, gc, summary->entry, &new_entry);
 420     }
 421   else
 422     {
 423       e->size += size;
 424       e->time += time;
 425       if (e->time > MAX_TIME * INLINE_TIME_SCALE)
 426         e->time = MAX_TIME * INLINE_TIME_SCALE;
 427     }
 428 }
 429
 430
 431 /* Work out what conditions might be true at invocation of E.  */
 432
 433 static clause_t
 434 evaulate_conditions_for_edge (struct cgraph_edge *e, bool inline_p)
 435 {
 436   clause_t clause = inline_p ? 0 : 1 << predicate_not_inlined_condition;
 437   struct inline_summary *info = inline_summary (e->callee);
 438   int i;
 439
 440   if (ipa_node_params_vector && info->conds
 441       /* FIXME: it seems that we forget to get argument count in some cases,
 442          probaby for previously indirect edges or so.  */
 443       && ipa_get_cs_argument_count (IPA_EDGE_REF (e)))
 444     {
 445       struct ipa_node_params *parms_info;
 446       struct ipa_edge_args *args = IPA_EDGE_REF (e);
 447       int i, count = ipa_get_cs_argument_count (args);
 448       struct ipcp_lattice lat;
 449       struct condition *c;
 450       VEC (tree, heap) *known_vals = NULL;
 451
 452       if (e->caller->global.inlined_to)
 453         parms_info = IPA_NODE_REF (e->caller->global.inlined_to);
 454       else
 455         parms_info = IPA_NODE_REF (e->caller);
 456
 457       VEC_safe_grow_cleared (tree, heap, known_vals, count);
 458       for (i = 0; i < count; i++)
 459         {
 460           ipa_lattice_from_jfunc (parms_info, &lat, ipa_get_ith_jump_func (args, i));
 461           if (lat.type == IPA_CONST_VALUE)
 462             VEC_replace (tree, known_vals, i, lat.constant);
 463         }
 464       for (i = 0; VEC_iterate (condition, info->conds, i, c); i++)
 465         {
 466           tree val = VEC_index (tree, known_vals, c->operand_num);
 467           tree res;
 468
 469           if (!val)
 470             {
 471               clause |= 1 << (i + predicate_first_dynamic_condition);
 472               continue;
 473             }
 474           if (c->code == IS_NOT_CONSTANT)
 475             continue;
 476           res = fold_binary_to_constant (c->code, boolean_type_node, val, c->val);
 477           if (res
 478               && integer_zerop (res))
 479             continue;
 480           clause |= 1 << (i + predicate_first_dynamic_condition);
 481         }
 482       VEC_free (tree, heap, known_vals);
 483     }
 484   else
 485     for (i = 0; i < (int)VEC_length (condition, info->conds); i++)
 486       clause |= 1 << (i + predicate_first_dynamic_condition);
 487
 488   return clause;
 489 }
 490
 491
 492 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
 493
 494 static void
 495 inline_summary_alloc (void)
 496 {
 497   if (!node_removal_hook_holder)
 498     node_removal_hook_holder =
 499       cgraph_add_node_removal_hook (&inline_node_removal_hook, NULL);
 500   if (!node_duplication_hook_holder)
 501     node_duplication_hook_holder =
 502       cgraph_add_node_duplication_hook (&inline_node_duplication_hook, NULL);
 503
 504   if (VEC_length (inline_summary_t, inline_summary_vec)
 505       <= (unsigned) cgraph_max_uid)
 506     VEC_safe_grow_cleared (inline_summary_t, gc,
 507                            inline_summary_vec, cgraph_max_uid + 1);
 508 }
 509
 510 /* Hook that is called by cgraph.c when a node is removed.  */
 511
 512 static void
 513 inline_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 514 {
 515   struct inline_summary *info;
 516   if (VEC_length (inline_summary_t, inline_summary_vec)
 517       <= (unsigned)node->uid)
 518     return;
 519   info = inline_summary (node);
 520   reset_node_growth_cache (node);
 521   VEC_free (condition, gc, info->conds);
 522   VEC_free (size_time_entry, gc, info->entry);
 523   info->conds = NULL;
 524   info->entry = NULL;
 525   memset (info, 0, sizeof (inline_summary_t));
 526 }
 527
 528 /* Hook that is called by cgraph.c when a node is duplicated.  */
 529
 530 static void
 531 inline_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
 532                               ATTRIBUTE_UNUSED void *data)
 533 {
 534   struct inline_summary *info;
 535   inline_summary_alloc ();
 536   info = inline_summary (dst);
 537   memcpy (info, inline_summary (src),
 538           sizeof (struct inline_summary));
 539   info->conds = VEC_copy (condition, gc, info->conds);
 540   info->entry = VEC_copy (size_time_entry, gc, info->entry);
 541 }
 542
 543
 544 /* Keep edge cache consistent across edge removal.  */
 545
 546 static void
 547 inline_edge_removal_hook (struct cgraph_edge *edge, void *data ATTRIBUTE_UNUSED)
 548 {
 549   reset_edge_growth_cache (edge);
 550 }
 551
 552
 553 /* Initialize growth caches.  */
 554
 555 void
 556 initialize_growth_caches (void)
 557 {
 558   if (!edge_removal_hook_holder)
 559     edge_removal_hook_holder =
 560       cgraph_add_edge_removal_hook (&inline_edge_removal_hook, NULL);
 561   if (cgraph_edge_max_uid)
 562     VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache,
 563                            cgraph_edge_max_uid);
 564   if (cgraph_max_uid)
 565     VEC_safe_grow_cleared (int, heap, node_growth_cache, cgraph_max_uid);
 566 }
 567
 568
 569 /* Free growth caches.  */
 570
 571 void
 572 free_growth_caches (void)
 573 {
 574   if (edge_removal_hook_holder)
 575     cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
 576   VEC_free (edge_growth_cache_entry, heap, edge_growth_cache);
 577   edge_growth_cache = 0;
 578   VEC_free (int, heap, node_growth_cache);
 579   node_growth_cache = 0;
 580 }
 581
 582
 583 static void
 584 dump_inline_summary (FILE * f, struct cgraph_node *node)
 585 {
 586   if (node->analyzed)
 587     {
 588       struct inline_summary *s = inline_summary (node);
 589       size_time_entry *e;
 590       int i;
 591       fprintf (f, "Inline summary for %s/%i", cgraph_node_name (node),
 592                node->uid);
 593       if (DECL_DISREGARD_INLINE_LIMITS (node->decl))
 594         fprintf (f, " always_inline");
 595       if (s->inlinable)
 596         fprintf (f, " inlinable");
 597       if (s->versionable)
 598         fprintf (f, " versionable");
 599       fprintf (f, "\n  self time:       %i\n",
 600                s->self_time);
 601       fprintf (f, "  global time:     %i\n", s->time);
 602       fprintf (f, "  self size:       %i\n",
 603                s->self_size);
 604       fprintf (f, "  global size:     %i\n", s->size);
 605       fprintf (f, "  self stack:      %i\n",
 606                (int) s->estimated_self_stack_size);
 607       fprintf (f, "  global stack:    %i\n",
 608                (int) s->estimated_stack_size);
 609       for (i = 0;
 610            VEC_iterate (size_time_entry, s->entry, i, e);
 611            i++)
 612         {
 613           fprintf (f, "    size:%f, time:%f, predicate:",
 614                    (double) e->size / INLINE_SIZE_SCALE,
 615                    (double) e->time / INLINE_TIME_SCALE);
 616           dump_predicate (f, s->conds, &e->predicate);
 617         }
 618       fprintf (f, "\n");
 619     }
 620 }
 621
 622 void
 623 debug_inline_summary (struct cgraph_node *node)
 624 {
 625   dump_inline_summary (stderr, node);
 626 }
 627
 628 void
 629 dump_inline_summaries (FILE *f)
 630 {
 631   struct cgraph_node *node;
 632
 633   for (node = cgraph_nodes; node; node = node->next)
 634     if (node->analyzed)
 635       dump_inline_summary (f, node);
 636 }
 637
 638 /* Give initial reasons why inlining would fail on EDGE.  This gets either
 639    nullified or usually overwritten by more precise reasons later.  */
 640
 641 void
 642 initialize_inline_failed (struct cgraph_edge *e)
 643 {
 644   struct cgraph_node *callee = e->callee;
 645
 646   if (e->indirect_unknown_callee)
 647     e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
 648   else if (!callee->analyzed)
 649     e->inline_failed = CIF_BODY_NOT_AVAILABLE;
 650   else if (callee->local.redefined_extern_inline)
 651     e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
 652   else if (e->call_stmt && gimple_call_cannot_inline_p (e->call_stmt))
 653     e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
 654   else
 655     e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
 656 }
 657
 658 /* See if statement might disappear after inlining.
 659    0 - means not eliminated
 660    1 - half of statements goes away
 661    2 - for sure it is eliminated.
 662    We are not terribly sophisticated, basically looking for simple abstraction
 663    penalty wrappers.  */
 664
 665 static int
 666 eliminated_by_inlining_prob (gimple stmt)
 667 {
 668   enum gimple_code code = gimple_code (stmt);
 669   switch (code)
 670     {
 671       case GIMPLE_RETURN:
 672         return 2;
 673       case GIMPLE_ASSIGN:
 674         if (gimple_num_ops (stmt) != 2)
 675           return 0;
 676
 677         /* Casts of parameters, loads from parameters passed by reference
 678            and stores to return value or parameters are often free after
 679            inlining dua to SRA and further combining.
 680            Assume that half of statements goes away.  */
 681         if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR
 682             || gimple_assign_rhs_code (stmt) == NOP_EXPR
 683             || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
 684             || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
 685           {
 686             tree rhs = gimple_assign_rhs1 (stmt);
 687             tree lhs = gimple_assign_lhs (stmt);
 688             tree inner_rhs = rhs;
 689             tree inner_lhs = lhs;
 690             bool rhs_free = false;
 691             bool lhs_free = false;
 692
 693             while (handled_component_p (inner_lhs)
 694                    || TREE_CODE (inner_lhs) == MEM_REF)
 695               inner_lhs = TREE_OPERAND (inner_lhs, 0);
 696             while (handled_component_p (inner_rhs)
 697                    || TREE_CODE (inner_rhs) == ADDR_EXPR
 698                    || TREE_CODE (inner_rhs) == MEM_REF)
 699               inner_rhs = TREE_OPERAND (inner_rhs, 0);
 700
 701
 702             if (TREE_CODE (inner_rhs) == PARM_DECL
 703                 || (TREE_CODE (inner_rhs) == SSA_NAME
 704                     && SSA_NAME_IS_DEFAULT_DEF (inner_rhs)
 705                     && TREE_CODE (SSA_NAME_VAR (inner_rhs)) == PARM_DECL))
 706               rhs_free = true;
 707             if (rhs_free && is_gimple_reg (lhs))
 708               lhs_free = true;
 709             if (((TREE_CODE (inner_lhs) == PARM_DECL
 710                   || (TREE_CODE (inner_lhs) == SSA_NAME
 711                       && SSA_NAME_IS_DEFAULT_DEF (inner_lhs)
 712                       && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == PARM_DECL))
 713                  && inner_lhs != lhs)
 714                 || TREE_CODE (inner_lhs) == RESULT_DECL
 715                 || (TREE_CODE (inner_lhs) == SSA_NAME
 716                     && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == RESULT_DECL))
 717               lhs_free = true;
 718             if (lhs_free
 719                 && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
 720               rhs_free = true;
 721             if (lhs_free && rhs_free)
 722               return 1;
 723           }
 724         return 0;
 725       default:
 726         return 0;
 727     }
 728 }
 729
 730
 731 /* Return predicate that must be true when is E executable.  */
 732
 733 static struct predicate
 734 edge_execution_predicate (struct ipa_node_params *info,
 735                           struct inline_summary *summary,
 736                           edge e)
 737 {
 738   struct predicate p = true_predicate ();
 739   gimple last;
 740   tree op;
 741   int index;
 742   enum tree_code code;
 743
 744   if (e->src == ENTRY_BLOCK_PTR)
 745     return p;
 746
 747   last = last_stmt (e->src);
 748   /* TODO: handle switch.  */
 749   if (!last
 750       || gimple_code (last) != GIMPLE_COND)
 751     return p;
 752   if (!is_gimple_ip_invariant (gimple_cond_rhs (last)))
 753     return p;
 754   op = gimple_cond_lhs (last);
 755   /* TODO: handle conditionals like
 756      var = op0 < 4;
 757      if (var != 0)
 758      and __bulitin_constant_p.  */
 759   if (TREE_CODE (op) != SSA_NAME
 760       || !SSA_NAME_IS_DEFAULT_DEF (op))
 761     return p;
 762   index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op));
 763   if (index == -1)
 764     return p;
 765   code = gimple_cond_code (last);
 766
 767   if (EDGE_TRUE_VALUE)
 768     code = invert_tree_comparison (code,
 769                                    HONOR_NANS (TYPE_MODE (TREE_TYPE (op))));
 770
 771   return add_condition (summary,
 772                         index,
 773                         gimple_cond_code (last),
 774                         gimple_cond_rhs (last));
 775 }
 776
 777 static struct predicate
 778 will_be_nonconstant_predicate (struct ipa_node_params *info,
 779                                struct inline_summary *summary,
 780                                gimple stmt)
 781 {
 782   struct predicate p = true_predicate ();
 783   ssa_op_iter iter;
 784   tree use;
 785   struct predicate op_non_const;
 786
 787   /* What statments might be optimized away
 788      when their arguments are constant
 789      TODO: also trivial builtins, especially builtin_constant_p.  */
 790   if (gimple_code (stmt) != GIMPLE_ASSIGN
 791       && gimple_code (stmt) != GIMPLE_COND
 792       && gimple_code (stmt) != GIMPLE_SWITCH)
 793     return p;
 794
 795   /* Stores and loads will stay anyway.  */
 796   if (gimple_vuse (stmt))
 797     return p;
 798
 799   /* See if we understand all operands before we start
 800      adding conditionals.  */
 801   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 802     {
 803       /* TODO: handle nested expressions and constant
 804          array accesses.  */
 805       if (TREE_CODE (use) != SSA_NAME
 806           || !SSA_NAME_IS_DEFAULT_DEF (use)
 807           || ipa_get_param_decl_index (info, SSA_NAME_VAR (use)) < 0)
 808         return p;
 809     }
 810   op_non_const = false_predicate ();
 811   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 812     {
 813       p = add_condition (summary,
 814                          ipa_get_param_decl_index (info, SSA_NAME_VAR (use)),
 815                          IS_NOT_CONSTANT, NULL);
 816       op_non_const = or_predicates (&p, &op_non_const);
 817     }
 818   return op_non_const;
 819 }
 820
 821
 822 /* Compute function body size parameters for NODE.
 823    When EARLY is true, we compute only simple summaries without
 824    non-trivial predicates to drive the early inliner.  */
 825
 826 static void
 827 estimate_function_body_sizes (struct cgraph_node *node, bool early)
 828 {
 829   gcov_type time = 0;
 830   /* Estimate static overhead for function prologue/epilogue and alignment. */
 831   int size = 2;
 832   /* Benefits are scaled by probability of elimination that is in range
 833      <0,2>.  */
 834   basic_block bb;
 835   gimple_stmt_iterator bsi;
 836   struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
 837   int freq;
 838   struct inline_summary *info = inline_summary (node);
 839   struct predicate bb_predicate;
 840   struct ipa_node_params *parms_info;
 841
 842   parms_info = ipa_node_params_vector && !early ? IPA_NODE_REF (node) : NULL;
 843
 844   info->conds = 0;
 845   info->entry = 0;
 846
 847
 848   if (dump_file)
 849     fprintf (dump_file, "\nAnalyzing function body size: %s\n",
 850              cgraph_node_name (node));
 851
 852   /* When we run into maximal number of entries, we assign everything to the
 853      constant truth case.  Be sure to have it in list. */
 854   bb_predicate = true_predicate ();
 855   account_size_time (info, 0, 0, &bb_predicate);
 856
 857   bb_predicate = not_inlined_predicate ();
 858   account_size_time (info, 2 * INLINE_SIZE_SCALE, 0, &bb_predicate);
 859
 860
 861   gcc_assert (my_function && my_function->cfg);
 862   FOR_EACH_BB_FN (bb, my_function)
 863     {
 864       edge e;
 865       edge_iterator ei;
 866
 867       freq = compute_call_stmt_bb_frequency (node->decl, bb);
 868
 869       /* TODO: Obviously predicates can be propagated down across CFG.  */
 870       if (parms_info)
 871         {
 872           bb_predicate = false_predicate ();
 873           FOR_EACH_EDGE (e, ei, bb->preds)
 874             {
 875               struct predicate ep;
 876               ep = edge_execution_predicate (parms_info, info, e);
 877               bb_predicate = or_predicates (&ep, &bb_predicate);
 878             }
 879         }
 880       else
 881         bb_predicate = true_predicate ();
 882
 883       if (dump_file && (dump_flags & TDF_DETAILS))
 884         {
 885           fprintf (dump_file, "\n BB %i predicate:", bb->index);
 886           dump_predicate (dump_file, info->conds, &bb_predicate);
 887         }
 888
 889       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 890         {
 891           gimple stmt = gsi_stmt (bsi);
 892           int this_size = estimate_num_insns (stmt, &eni_size_weights);
 893           int this_time = estimate_num_insns (stmt, &eni_time_weights);
 894           int prob;
 895
 896           if (dump_file && (dump_flags & TDF_DETAILS))
 897             {
 898               fprintf (dump_file, "  ");
 899               print_gimple_stmt (dump_file, stmt, 0, 0);
 900               fprintf (dump_file, "\t\tfreq:%3.2f size:%3i time:%3i\n",
 901                        ((double)freq)/CGRAPH_FREQ_BASE, this_size, this_time);
 902             }
 903
 904           if (is_gimple_call (stmt))
 905             {
 906               struct cgraph_edge *edge = cgraph_edge (node, stmt);
 907               edge->call_stmt_size = this_size;
 908               edge->call_stmt_time = this_time;
 909
 910               /* Do not inline calls where we cannot triviall work around
 911                  mismatches in argument or return types.  */
 912               if (edge->callee
 913                   && !gimple_check_call_matching_types (stmt, edge->callee->decl))
 914                 {
 915                   edge->call_stmt_cannot_inline_p = true;
 916                   gimple_call_set_cannot_inline (stmt, true);
 917                 }
 918               else
 919                 gcc_assert (!gimple_call_cannot_inline_p (stmt));
 920             }
 921
 922           if (this_time || this_size)
 923             {
 924               struct predicate will_be_nonconstant;
 925               struct predicate p;
 926
 927               this_time *= freq;
 928               time += this_time;
 929               size += this_size;
 930
 931               prob = eliminated_by_inlining_prob (stmt);
 932               if (prob == 1 && dump_file && (dump_flags & TDF_DETAILS))
 933                 fprintf (dump_file, "\t\t50%% will be eliminated by inlining\n");
 934               if (prob == 2 && dump_file && (dump_flags & TDF_DETAILS))
 935                 fprintf (dump_file, "\t\twill eliminated by inlining\n");
 936
 937               if (parms_info)
 938                 {
 939                   will_be_nonconstant
 940                      = will_be_nonconstant_predicate (parms_info, info, stmt);
 941                   p = and_predicates (&bb_predicate, &will_be_nonconstant);
 942                 }
 943               else
 944                 p = true_predicate ();
 945
 946               /* We account everything but the calls.  Calls have their own
 947                  size/time info attached to cgraph edges.  This is neccesary
 948                  in order to make the cost disappear after inlining.  */
 949               if (!is_gimple_call (stmt))
 950                 {
 951                   if (prob)
 952                     {
 953                       struct predicate ip = not_inlined_predicate ();
 954                       ip = and_predicates (&ip, &p);
 955                       account_size_time (info, this_size * prob,
 956                                          this_time * prob, &ip);
 957                     }
 958                   if (prob != 2)
 959                     account_size_time (info, this_size * (2 - prob),
 960                                        this_time * (2 - prob), &p);
 961                 }
 962
 963               gcc_assert (time >= 0);
 964               gcc_assert (size >= 0);
 965             }
 966         }
 967     }
 968   time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
 969   if (time > MAX_TIME)
 970     time = MAX_TIME;
 971   inline_summary (node)->self_time = time;
 972   inline_summary (node)->self_size = size;
 973   if (dump_file)
 974     {
 975       fprintf (dump_file, "\n");
 976       dump_inline_summary (dump_file, node);
 977     }
 978 }
 979
 980
 981 /* Compute parameters of functions used by inliner.
 982    EARLY is true when we compute parameters for the early inliner  */
 983
 984 void
 985 compute_inline_parameters (struct cgraph_node *node, bool early)
 986 {
 987   HOST_WIDE_INT self_stack_size;
 988   struct cgraph_edge *e;
 989   struct inline_summary *info;
 990
 991   gcc_assert (!node->global.inlined_to);
 992
 993   inline_summary_alloc ();
 994
 995   info = inline_summary (node);
 996
 997   /* Estimate the stack size for the function if we're optimizing.  */
 998   self_stack_size = optimize ? estimated_stack_frame_size (node) : 0;
 999   info->estimated_self_stack_size = self_stack_size;
1000   info->estimated_stack_size = self_stack_size;
1001   info->stack_frame_offset = 0;
1002
1003   /* Can this function be inlined at all?  */
1004   info->inlinable = tree_inlinable_function_p (node->decl);
1005
1006   /* Inlinable functions always can change signature.  */
1007   if (info->inlinable)
1008     node->local.can_change_signature = true;
1009   else
1010     {
1011       /* Functions calling builtin_apply can not change signature.  */
1012       for (e = node->callees; e; e = e->next_callee)
1013         if (DECL_BUILT_IN (e->callee->decl)
1014             && DECL_BUILT_IN_CLASS (e->callee->decl) == BUILT_IN_NORMAL
1015             && DECL_FUNCTION_CODE (e->callee->decl) == BUILT_IN_APPLY_ARGS)
1016           break;
1017       node->local.can_change_signature = !e;
1018     }
1019   estimate_function_body_sizes (node, early);
1020
1021   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
1022   info->time = info->self_time;
1023   info->size = info->self_size;
1024   info->stack_frame_offset = 0;
1025   info->estimated_stack_size = info->estimated_self_stack_size;
1026 }
1027
1028
1029 /* Compute parameters of functions used by inliner using
1030    current_function_decl.  */
1031
1032 static unsigned int
1033 compute_inline_parameters_for_current (void)
1034 {
1035   compute_inline_parameters (cgraph_get_node (current_function_decl), true);
1036   return 0;
1037 }
1038
1039 struct gimple_opt_pass pass_inline_parameters =
1040 {
1041  {
1042   GIMPLE_PASS,
1043   "inline_param",                       /* name */
1044   NULL,                                 /* gate */
1045   compute_inline_parameters_for_current,/* execute */
1046   NULL,                                 /* sub */
1047   NULL,                                 /* next */
1048   0,                                    /* static_pass_number */
1049   TV_INLINE_HEURISTICS,                 /* tv_id */
1050   0,                                    /* properties_required */
1051   0,                                    /* properties_provided */
1052   0,                                    /* properties_destroyed */
1053   0,                                    /* todo_flags_start */
1054   0                                     /* todo_flags_finish */
1055  }
1056 };
1057
1058
1059 /* Increase SIZE and TIME for size and time needed to handle edge E.  */
1060
1061 static void
1062 estimate_edge_size_and_time (struct cgraph_edge *e, int *size, int *time)
1063 {
1064   *size += e->call_stmt_size * INLINE_SIZE_SCALE;
1065   *time += (e->call_stmt_time
1066             * e->frequency * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE));
1067   if (*time > MAX_TIME * INLINE_TIME_SCALE)
1068     *time = MAX_TIME * INLINE_TIME_SCALE;
1069 }
1070
1071
1072 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE.  */
1073
1074 static void
1075 estimate_calls_size_and_time (struct cgraph_node *node, int *size, int *time)
1076 {
1077   struct cgraph_edge *e;
1078   for (e = node->callees; e; e = e->next_callee)
1079     if (e->inline_failed)
1080       estimate_edge_size_and_time (e, size, time);
1081     else
1082       estimate_calls_size_and_time (e->callee, size, time);
1083   /* TODO: look for devirtualizing oppurtunities.  */
1084   for (e = node->indirect_calls; e; e = e->next_callee)
1085     estimate_edge_size_and_time (e, size, time);
1086 }
1087
1088
1089 /* Estimate size and time needed to execute callee of EDGE assuming
1090    that parameters known to be constant at caller of EDGE are
1091    propagated.  If INLINE_P is true, it is assumed that call will
1092    be inlined.  */
1093
1094 static void
1095 estimate_callee_size_and_time (struct cgraph_edge *edge, bool inline_p,
1096                                int *ret_size, int *ret_time)
1097 {
1098   struct inline_summary *info = inline_summary (edge->callee);
1099   clause_t clause = evaulate_conditions_for_edge (edge, inline_p);
1100   size_time_entry *e;
1101   int size = 0, time = 0;
1102   int i;
1103
1104   if (dump_file
1105       && (dump_flags & TDF_DETAILS))
1106     {
1107       bool found = false;
1108       fprintf (dump_file, "   Estimating callee body: %s/%i\n"
1109                           "   Known to be false: ",
1110                cgraph_node_name (edge->callee),
1111                edge->callee->uid);
1112
1113       for (i = predicate_not_inlined_condition;
1114            i < (predicate_first_dynamic_condition
1115                 + (int)VEC_length (condition, info->conds)); i++)
1116         if (!(clause & (1 << i)))
1117           {
1118             if (found)
1119               fprintf (dump_file, ", ");
1120             found = true;
1121             dump_condition (dump_file, info->conds, i);
1122           }
1123     }
1124
1125   for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
1126     if (evaulate_predicate (&e->predicate, clause))
1127       time += e->time, size += e->size;
1128
1129   if (time > MAX_TIME * INLINE_TIME_SCALE)
1130     time = MAX_TIME * INLINE_TIME_SCALE;
1131
1132   estimate_calls_size_and_time (edge->callee, &size, &time);
1133   time = (time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
1134   size = (size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
1135
1136
1137   if (dump_file
1138       && (dump_flags & TDF_DETAILS))
1139     fprintf (dump_file, "\n   size:%i time:%i\n", size, time);
1140   if (ret_time)
1141     *ret_time = time;
1142   if (ret_size)
1143     *ret_size = size;
1144   return;
1145 }
1146
1147
1148 /* Translate all conditions from callee representation into caller representaiton and
1149    symbolically evaulate predicate P into new predicate.  */
1150
1151 static struct predicate
1152 remap_predicate (struct inline_summary *info, struct inline_summary *callee_info,
1153                  struct predicate *p,
1154                  VEC (int, heap) *operand_map,
1155                  clause_t possible_truths)
1156 {
1157   int i;
1158   struct predicate out = true_predicate ();
1159
1160   /* True predicate is easy.  */
1161   if (p->clause[0] == 0)
1162     return *p;
1163   for (i = 0; p->clause[i]; i++)
1164     {
1165       clause_t clause = p->clause[i];
1166       int cond;
1167       struct predicate clause_predicate = false_predicate ();
1168
1169       for (cond = 0; cond < NUM_CONDITIONS; cond ++)
1170         /* Do we have condition we can't disprove?   */
1171         if (clause & possible_truths & (1 << cond))
1172           {
1173             struct predicate cond_predicate;
1174             /* Work out if the condition can translate to predicate in the
1175                inlined function.  */
1176             if (cond >= predicate_first_dynamic_condition)
1177               {
1178                  struct condition *c;
1179
1180                  c = VEC_index (condition, callee_info->conds,
1181                                 cond - predicate_first_dynamic_condition);
1182                  /* See if we can remap condition operand to caller's operand.
1183                     Otherwise give up.  */
1184                  if (!operand_map
1185                      || VEC_index (int, operand_map, c->operand_num) == -1)
1186                    cond_predicate = true_predicate ();
1187                  else
1188                    cond_predicate = add_condition (info,
1189                                                    VEC_index (int, operand_map,
1190                                                               c->operand_num),
1191                                                    c->code, c->val);
1192               }
1193             /* Fixed conditions remains same, construct single
1194                condition predicate.  */
1195             else
1196               {
1197                 cond_predicate.clause[0] = 1 << cond;
1198                 cond_predicate.clause[1] = 0;
1199               }
1200             clause_predicate = or_predicates (&clause_predicate, &cond_predicate);
1201           }
1202       out = and_predicates (&out, &clause_predicate);
1203     }
1204   return out;
1205 }
1206
1207
1208 /* We inlined EDGE.  Update summary of the function we inlined into.  */
1209
1210 void
1211 inline_merge_summary (struct cgraph_edge *edge)
1212 {
1213   struct inline_summary *callee_info = inline_summary (edge->callee);
1214   struct cgraph_node *to = (edge->caller->global.inlined_to
1215                             ? edge->caller->global.inlined_to : edge->caller);
1216   struct inline_summary *info = inline_summary (to);
1217   clause_t clause = 0;          /* not_inline is known to be false.  */
1218   size_time_entry *e;
1219   VEC (int, heap) *operand_map = NULL;
1220   int i;
1221
1222   if (ipa_node_params_vector && callee_info->conds
1223       /* FIXME: it seems that we forget to get argument count in some cases,
1224          probaby for previously indirect edges or so.
1225          Removing the test leads to ICE on tramp3d.  */
1226       && ipa_get_cs_argument_count (IPA_EDGE_REF (edge)))
1227     {
1228       struct ipa_edge_args *args = IPA_EDGE_REF (edge);
1229       int count = ipa_get_cs_argument_count (args);
1230       int i;
1231
1232       clause = evaulate_conditions_for_edge (edge, true);
1233       VEC_safe_grow_cleared (int, heap, operand_map, count);
1234       for (i = 0; i < count; i++)
1235         {
1236           struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i);
1237           int map = -1;
1238           /* TODO: handle non-NOPs when merging.  */
1239           if (jfunc->type == IPA_JF_PASS_THROUGH
1240               && jfunc->value.pass_through.operation == NOP_EXPR)
1241             map = jfunc->value.pass_through.formal_id;
1242           VEC_replace (int, operand_map, i, map);
1243         }
1244     }
1245   for (i = 0; VEC_iterate (size_time_entry, callee_info->entry, i, e); i++)
1246     {
1247       struct predicate p = remap_predicate (info, callee_info,
1248                                             &e->predicate, operand_map, clause);
1249       gcov_type add_time = ((gcov_type)e->time * edge->frequency
1250                             + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
1251       if (add_time > MAX_TIME)
1252         add_time = MAX_TIME;
1253       account_size_time (info, e->size, add_time, &p);
1254     }
1255   info->size = 0;
1256   info->time = 0;
1257   for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
1258     info->size += e->size, info->time += e->time;
1259   estimate_calls_size_and_time (to, &info->size, &info->time);
1260   info->time = (info->time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
1261   info->size = (info->size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
1262 }
1263
1264
1265 /* Estimate the time cost for the caller when inlining EDGE.
1266    Only to be called via estimate_edge_time, that handles the
1267    caching mechanism.
1268
1269    When caching, also update the cache entry.  Compute both time and
1270    size, since we always need both metrics eventually.  */
1271
1272 int
1273 do_estimate_edge_time (struct cgraph_edge *edge)
1274 {
1275   int time;
1276   int size;
1277   gcov_type ret;
1278
1279   gcc_checking_assert (edge->inline_failed);
1280   estimate_callee_size_and_time (edge, true, &size, &time);
1281
1282   ret = (((gcov_type)time - edge->call_stmt_time) * edge->frequency
1283          + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
1284   if (ret > MAX_TIME)
1285     ret = MAX_TIME;
1286
1287   /* When caching, update the cache entry.  */
1288   if (edge_growth_cache)
1289     {
1290       int ret_size;
1291       if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache)
1292           <= edge->uid)
1293         VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache,
1294                                cgraph_edge_max_uid);
1295       VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->time
1296         = ret + (ret >= 0);
1297
1298       ret_size = size - edge->call_stmt_size;
1299       gcc_checking_assert (edge->call_stmt_size);
1300       VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->size
1301         = ret_size + (ret_size >= 0);
1302     }
1303   return ret;
1304 }
1305
1306
1307 /* Estimate the growth of the caller when inlining EDGE.
1308    Only to be called via estimate_edge_size.  */
1309
1310 int
1311 do_estimate_edge_growth (struct cgraph_edge *edge)
1312 {
1313   int size;
1314
1315   /* When we do caching, use do_estimate_edge_time to populate the entry.  */
1316
1317   if (edge_growth_cache)
1318     {
1319       do_estimate_edge_time (edge);
1320       size = VEC_index (edge_growth_cache_entry,
1321                         edge_growth_cache,
1322                         edge->uid)->size;
1323       gcc_checking_assert (size);
1324       return size - (size > 0);
1325     }
1326
1327   /* Early inliner runs without caching, go ahead and do the dirty work.  */
1328   gcc_checking_assert (edge->inline_failed);
1329   estimate_callee_size_and_time (edge, true, &size, NULL);
1330   gcc_checking_assert (edge->call_stmt_size);
1331   return size - edge->call_stmt_size;
1332 }
1333
1334
1335 /* Estimate self time of the function NODE after inlining EDGE.  */
1336
1337 int
1338 estimate_time_after_inlining (struct cgraph_node *node,
1339                               struct cgraph_edge *edge)
1340 {
1341   gcov_type time = inline_summary (node)->time + estimate_edge_time (edge);
1342   if (time < 0)
1343     time = 0;
1344   if (time > MAX_TIME)
1345     time = MAX_TIME;
1346   return time;
1347 }
1348
1349
1350 /* Estimate the size of NODE after inlining EDGE which should be an
1351    edge to either NODE or a call inlined into NODE.  */
1352
1353 int
1354 estimate_size_after_inlining (struct cgraph_node *node,
1355                               struct cgraph_edge *edge)
1356 {
1357   int size = inline_summary (node)->size + estimate_edge_growth (edge);
1358   gcc_assert (size >= 0);
1359   return size;
1360 }
1361
1362
1363 /* Estimate the growth caused by inlining NODE into all callees.  */
1364
1365 int
1366 do_estimate_growth (struct cgraph_node *node)
1367 {
1368   int growth = 0;
1369   struct cgraph_edge *e;
1370   bool self_recursive = false;
1371   struct inline_summary *info = inline_summary (node);
1372
1373   for (e = node->callers; e; e = e->next_caller)
1374     {
1375       gcc_checking_assert (e->inline_failed);
1376
1377       if (e->caller == node
1378           || (e->caller->global.inlined_to
1379               && e->caller->global.inlined_to == node))
1380         self_recursive = true;
1381       growth += estimate_edge_growth (e);
1382     }
1383
1384
1385   /* For self recursive functions the growth estimation really should be
1386      infinity.  We don't want to return very large values because the growth
1387      plays various roles in badness computation fractions.  Be sure to not
1388      return zero or negative growths. */
1389   if (self_recursive)
1390     growth = growth < info->size ? info->size : growth;
1391   else
1392     {
1393       if (cgraph_will_be_removed_from_program_if_no_direct_calls (node)
1394           && !DECL_EXTERNAL (node->decl))
1395         growth -= info->size;
1396       /* COMDAT functions are very often not shared across multiple units since they
1397          come from various template instantiations.  Take this into account.  */
1398       else  if (DECL_COMDAT (node->decl)
1399                 && cgraph_can_remove_if_no_direct_calls_p (node))
1400         growth -= (info->size
1401                    * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY)) + 50) / 100;
1402     }
1403
1404   if (node_growth_cache)
1405     {
1406       if ((int)VEC_length (int, node_growth_cache) <= node->uid)
1407         VEC_safe_grow_cleared (int, heap, node_growth_cache, cgraph_max_uid);
1408       VEC_replace (int, node_growth_cache, node->uid, growth + (growth >= 0));
1409     }
1410   return growth;
1411 }
1412
1413
1414 /* This function performs intraprocedural analysis in NODE that is required to
1415    inline indirect calls.  */
1416
1417 static void
1418 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
1419 {
1420   ipa_analyze_node (node);
1421   if (dump_file && (dump_flags & TDF_DETAILS))
1422     {
1423       ipa_print_node_params (dump_file, node);
1424       ipa_print_node_jump_functions (dump_file, node);
1425     }
1426 }
1427
1428
1429 /* Note function body size.  */
1430
1431 static void
1432 inline_analyze_function (struct cgraph_node *node)
1433 {
1434   push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1435   current_function_decl = node->decl;
1436
1437   if (dump_file)
1438     fprintf (dump_file, "\nAnalyzing function: %s/%u\n",
1439              cgraph_node_name (node), node->uid);
1440   /* FIXME: We should remove the optimize check after we ensure we never run
1441      IPA passes when not optimizing.  */
1442   if (flag_indirect_inlining && optimize)
1443     inline_indirect_intraprocedural_analysis (node);
1444   compute_inline_parameters (node, false);
1445
1446   current_function_decl = NULL;
1447   pop_cfun ();
1448 }
1449
1450
1451 /* Called when new function is inserted to callgraph late.  */
1452
1453 static void
1454 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
1455 {
1456   inline_analyze_function (node);
1457 }
1458
1459
1460 /* Note function body size.  */
1461
1462 void
1463 inline_generate_summary (void)
1464 {
1465   struct cgraph_node *node;
1466
1467   function_insertion_hook_holder =
1468       cgraph_add_function_insertion_hook (&add_new_function, NULL);
1469
1470   if (flag_indirect_inlining)
1471     ipa_register_cgraph_hooks ();
1472
1473   for (node = cgraph_nodes; node; node = node->next)
1474     if (node->analyzed)
1475       inline_analyze_function (node);
1476 }
1477
1478
1479 /* Stream in inline summaries from the section.  */
1480
1481 static void
1482 inline_read_section (struct lto_file_decl_data *file_data, const char *data,
1483                      size_t len)
1484 {
1485   const struct lto_function_header *header =
1486     (const struct lto_function_header *) data;
1487   const int32_t cfg_offset = sizeof (struct lto_function_header);
1488   const int32_t main_offset = cfg_offset + header->cfg_size;
1489   const int32_t string_offset = main_offset + header->main_size;
1490   struct data_in *data_in;
1491   struct lto_input_block ib;
1492   unsigned int i, count2, j;
1493   unsigned int f_count;
1494
1495   LTO_INIT_INPUT_BLOCK (ib, (const char *) data + main_offset, 0,
1496                         header->main_size);
1497
1498   data_in =
1499     lto_data_in_create (file_data, (const char *) data + string_offset,
1500                         header->string_size, NULL);
1501   f_count = lto_input_uleb128 (&ib);
1502   for (i = 0; i < f_count; i++)
1503     {
1504       unsigned int index;
1505       struct cgraph_node *node;
1506       struct inline_summary *info;
1507       lto_cgraph_encoder_t encoder;
1508       struct bitpack_d bp;
1509
1510       index = lto_input_uleb128 (&ib);
1511       encoder = file_data->cgraph_node_encoder;
1512       node = lto_cgraph_encoder_deref (encoder, index);
1513       info = inline_summary (node);
1514
1515       info->estimated_stack_size
1516         = info->estimated_self_stack_size = lto_input_uleb128 (&ib);
1517       info->size = info->self_size = lto_input_uleb128 (&ib);
1518       info->time = info->self_time = lto_input_uleb128 (&ib);
1519
1520       bp = lto_input_bitpack (&ib);
1521       info->inlinable = bp_unpack_value (&bp, 1);
1522       info->versionable = bp_unpack_value (&bp, 1);
1523
1524       count2 = lto_input_uleb128 (&ib);
1525       gcc_assert (!info->conds);
1526       for (j = 0; j < count2; j++)
1527         {
1528           struct condition c;
1529           c.operand_num = lto_input_uleb128 (&ib);
1530           c.code = (enum tree_code) lto_input_uleb128 (&ib);
1531           c.val = lto_input_tree (&ib, data_in);
1532           VEC_safe_push (condition, gc, info->conds, &c);
1533         }
1534       count2 = lto_input_uleb128 (&ib);
1535       gcc_assert (!info->entry);
1536       for (j = 0; j < count2; j++)
1537         {
1538           struct size_time_entry e;
1539           clause_t clause;
1540           int k = 0;
1541
1542           e.size = lto_input_uleb128 (&ib);
1543           e.time = lto_input_uleb128 (&ib);
1544           do
1545             {
1546               clause = e.predicate.clause[k++] = lto_input_uleb128 (&ib);
1547             }
1548           while (clause);
1549
1550           VEC_safe_push (size_time_entry, gc, info->entry, &e);
1551         }
1552     }
1553
1554   lto_free_section_data (file_data, LTO_section_inline_summary, NULL, data,
1555                          len);
1556   lto_data_in_delete (data_in);
1557 }
1558
1559
1560 /* Read inline summary.  Jump functions are shared among ipa-cp
1561    and inliner, so when ipa-cp is active, we don't need to write them
1562    twice.  */
1563
1564 void
1565 inline_read_summary (void)
1566 {
1567   struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
1568   struct lto_file_decl_data *file_data;
1569   unsigned int j = 0;
1570
1571   inline_summary_alloc ();
1572
1573   while ((file_data = file_data_vec[j++]))
1574     {
1575       size_t len;
1576       const char *data = lto_get_section_data (file_data, LTO_section_inline_summary, NULL, &len);
1577       if (data)
1578         inline_read_section (file_data, data, len);
1579       else
1580         /* Fatal error here.  We do not want to support compiling ltrans units with
1581            different version of compiler or different flags than the WPA unit, so
1582            this should never happen.  */
1583         fatal_error ("ipa inline summary is missing in input file");
1584     }
1585   if (flag_indirect_inlining)
1586     {
1587       ipa_register_cgraph_hooks ();
1588       if (!flag_ipa_cp)
1589         ipa_prop_read_jump_functions ();
1590     }
1591   function_insertion_hook_holder =
1592       cgraph_add_function_insertion_hook (&add_new_function, NULL);
1593 }
1594
1595
1596 /* Write inline summary for node in SET.
1597    Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
1598    active, we don't need to write them twice.  */
1599
1600 void
1601 inline_write_summary (cgraph_node_set set,
1602                       varpool_node_set vset ATTRIBUTE_UNUSED)
1603 {
1604   struct cgraph_node *node;
1605   struct output_block *ob = create_output_block (LTO_section_inline_summary);
1606   lto_cgraph_encoder_t encoder = ob->decl_state->cgraph_node_encoder;
1607   unsigned int count = 0;
1608   int i;
1609
1610   for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
1611     if (lto_cgraph_encoder_deref (encoder, i)->analyzed)
1612       count++;
1613   lto_output_uleb128_stream (ob->main_stream, count);
1614
1615   for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
1616     {
1617       node = lto_cgraph_encoder_deref (encoder, i);
1618       if (node->analyzed)
1619         {
1620           struct inline_summary *info = inline_summary (node);
1621           struct bitpack_d bp;
1622           int i;
1623           size_time_entry *e;
1624           struct condition *c;
1625
1626
1627           lto_output_uleb128_stream (ob->main_stream,
1628                                      lto_cgraph_encoder_encode (encoder, node));
1629           lto_output_sleb128_stream (ob->main_stream,
1630                                      info->estimated_self_stack_size);
1631           lto_output_sleb128_stream (ob->main_stream,
1632                                      info->self_size);
1633           lto_output_sleb128_stream (ob->main_stream,
1634                                      info->self_time);
1635           bp = bitpack_create (ob->main_stream);
1636           bp_pack_value (&bp, info->inlinable, 1);
1637           bp_pack_value (&bp, info->versionable, 1);
1638           lto_output_bitpack (&bp);
1639           lto_output_uleb128_stream (ob->main_stream,
1640                                      VEC_length (condition, info->conds));
1641           for (i = 0; VEC_iterate (condition, info->conds, i, c); i++)
1642             {
1643               lto_output_uleb128_stream (ob->main_stream,
1644                                          c->operand_num);
1645               lto_output_uleb128_stream (ob->main_stream,
1646                                          c->code);
1647               lto_output_tree (ob, c->val, true);
1648             }
1649           lto_output_uleb128_stream (ob->main_stream,
1650                                      VEC_length (size_time_entry, info->entry));
1651           for (i = 0;
1652                VEC_iterate (size_time_entry, info->entry, i, e);
1653                i++)
1654             {
1655               int j;
1656               lto_output_uleb128_stream (ob->main_stream,
1657                                          e->time);
1658               lto_output_uleb128_stream (ob->main_stream,
1659                                          e->size);
1660               for (j = 0; e->predicate.clause[j]; j++)
1661                 lto_output_uleb128_stream (ob->main_stream,
1662                                            e->predicate.clause[j]);
1663               lto_output_uleb128_stream (ob->main_stream, 0);
1664             }
1665         }
1666     }
1667   lto_output_1_stream (ob->main_stream, 0);
1668   produce_asm (ob, NULL);
1669   destroy_output_block (ob);
1670
1671   if (flag_indirect_inlining && !flag_ipa_cp)
1672     ipa_prop_write_jump_functions (set);
1673 }
1674
1675
1676 /* Release inline summary.  */
1677
1678 void
1679 inline_free_summary (void)
1680 {
1681   if (function_insertion_hook_holder)
1682     cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
1683   function_insertion_hook_holder = NULL;
1684   if (node_removal_hook_holder)
1685     cgraph_remove_node_removal_hook (node_removal_hook_holder);
1686   node_removal_hook_holder = NULL;
1687   if (node_duplication_hook_holder)
1688     cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
1689   node_duplication_hook_holder = NULL;
1690   VEC_free (inline_summary_t, gc, inline_summary_vec);
1691   inline_summary_vec = NULL;
1692 }