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 #include "alloc-pool.h"
  89
  90 /* Estimate runtime of function can easilly run into huge numbers with many
  91    nested loops.  Be sure we can compute time * INLINE_SIZE_SCALE in integer.
  92    For anything larger we use gcov_type.  */
  93 #define MAX_TIME 1000000
  94
  95 /* Number of bits in integer, but we really want to be stable across different
  96    hosts.  */
  97 #define NUM_CONDITIONS 32
  98
  99 enum predicate_conditions
 100 {
 101   predicate_false_condition = 0,
 102   predicate_not_inlined_condition = 1,
 103   predicate_first_dynamic_condition = 2
 104 };
 105
 106 /* Special condition code we use to represent test that operand is compile time
 107    constant.  */
 108 #define IS_NOT_CONSTANT ERROR_MARK
 109
 110 /* Holders of ipa cgraph hooks: */
 111 static struct cgraph_node_hook_list *function_insertion_hook_holder;
 112 static struct cgraph_node_hook_list *node_removal_hook_holder;
 113 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
 114 static struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
 115 static struct cgraph_edge_hook_list *edge_removal_hook_holder;
 116 static void inline_node_removal_hook (struct cgraph_node *, void *);
 117 static void inline_node_duplication_hook (struct cgraph_node *,
 118                                           struct cgraph_node *, void *);
 119 static void inline_edge_removal_hook (struct cgraph_edge *, void *);
 120 static void inline_edge_duplication_hook (struct cgraph_edge *,
 121                                           struct cgraph_edge *,
 122                                           void *);
 123
 124 /* VECtor holding inline summaries.
 125    In GGC memory because conditions might point to constant trees.  */
 126 VEC(inline_summary_t,gc) *inline_summary_vec;
 127 VEC(inline_edge_summary_t,heap) *inline_edge_summary_vec;
 128
 129 /* Cached node/edge growths.  */
 130 VEC(int,heap) *node_growth_cache;
 131 VEC(edge_growth_cache_entry,heap) *edge_growth_cache;
 132
 133 /* Edge predicates goes here.  */
 134 static alloc_pool edge_predicate_pool;
 135
 136 /* Return true predicate (tautology).
 137    We represent it by empty list of clauses.  */
 138
 139 static inline struct predicate
 140 true_predicate (void)
 141 {
 142   struct predicate p;
 143   p.clause[0]=0;
 144   return p;
 145 }
 146
 147
 148 /* Return predicate testing single condition number COND.  */
 149
 150 static inline struct predicate
 151 single_cond_predicate (int cond)
 152 {
 153   struct predicate p;
 154   p.clause[0]=1 << cond;
 155   p.clause[1]=0;
 156   return p;
 157 }
 158
 159
 160 /* Return false predicate.  First clause require false condition.  */
 161
 162 static inline struct predicate
 163 false_predicate (void)
 164 {
 165   return single_cond_predicate (predicate_false_condition);
 166 }
 167
 168
 169 /* Return true if P is (false).  */
 170
 171 static inline bool
 172 true_predicate_p (struct predicate *p)
 173 {
 174   return !p->clause[0];
 175 }
 176
 177
 178 /* Return true if P is (false).  */
 179
 180 static inline bool
 181 false_predicate_p (struct predicate *p)
 182 {
 183   if (p->clause[0] == (1 << predicate_false_condition))
 184     {
 185       gcc_checking_assert (!p->clause[1]
 186                            && p->clause[0] == 1 << predicate_false_condition);
 187       return true;
 188     }
 189   return false;
 190 }
 191
 192
 193 /* Return predicate that is set true when function is not inlined.  */
 194 static inline struct predicate
 195 not_inlined_predicate (void)
 196 {
 197   return single_cond_predicate (predicate_not_inlined_condition);
 198 }
 199
 200
 201 /* Add condition to condition list CONDS.  */
 202
 203 static struct predicate
 204 add_condition (struct inline_summary *summary, int operand_num,
 205                enum tree_code code, tree val)
 206 {
 207   int i;
 208   struct condition *c;
 209   struct condition new_cond;
 210
 211   for (i = 0; VEC_iterate (condition, summary->conds, i, c); i++)
 212     {
 213       if (c->operand_num == operand_num
 214           && c->code == code
 215           && c->val == val)
 216         return single_cond_predicate (i + predicate_first_dynamic_condition);
 217     }
 218   /* Too many conditions.  Give up and return constant true.  */
 219   if (i == NUM_CONDITIONS - predicate_first_dynamic_condition)
 220     return true_predicate ();
 221
 222   new_cond.operand_num = operand_num;
 223   new_cond.code = code;
 224   new_cond.val = val;
 225   VEC_safe_push (condition, gc, summary->conds, &new_cond);
 226   return single_cond_predicate (i + predicate_first_dynamic_condition);
 227 }
 228
 229
 230 /* Add clause CLAUSE into the predicate P.  */
 231
 232 static inline void
 233 add_clause (struct predicate *p, clause_t clause)
 234 {
 235   int i;
 236   int i2;
 237   int insert_here = -1;
 238
 239   /* True clause.  */
 240   if (!clause)
 241     return;
 242
 243   /* False clause makes the whole predicate false.  Kill the other variants.  */
 244   if (clause == (1 << predicate_false_condition))
 245     {
 246       p->clause[0] = (1 << predicate_false_condition);
 247       p->clause[1] = 0;
 248       return;
 249     }
 250   if (false_predicate_p (p))
 251     return;
 252
 253   /* No one should be sily enough to add false into nontrivial clauses.  */
 254   gcc_checking_assert (!(clause & (1 << predicate_false_condition)));
 255
 256   /* Look where to insert the clause.  At the same time prune out
 257      clauses of P that are implied by the new clause and thus
 258      redundant.  */
 259   for (i = 0, i2 = 0; i <= MAX_CLAUSES; i++)
 260     {
 261       p->clause[i2] = p->clause[i];
 262
 263       if (!p->clause[i])
 264         break;
 265
 266       /* If p->clause[i] implies clause, there is nothing to add.  */
 267       if ((p->clause[i] & clause) == p->clause[i])
 268         {
 269           /* We had nothing to add, none of clauses should've become redundant.  */
 270           gcc_checking_assert (i == i2);
 271           return;
 272         }
 273
 274       if (p->clause[i] < clause && insert_here < 0)
 275         insert_here = i2;
 276
 277       /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
 278          Otherwise the p->clause[i] has to stay.  */
 279       if ((p->clause[i] & clause) != clause)
 280         i2++;
 281     }
 282   /* We run out of variants.  Be conservative in positive direction.  */
 283   if (i2 == MAX_CLAUSES)
 284     return;
 285   /* Keep clauses in decreasing order. This makes equivalence testing easy.  */
 286   p->clause[i2 + 1] = 0;
 287   if (insert_here >= 0)
 288     for (;i2 > insert_here; i2--)
 289       p->clause[i2] = p->clause[i2 - 1];
 290   else
 291     insert_here = i2;
 292   p->clause[insert_here] = clause;
 293 }
 294
 295
 296 /* Return P & P2.  */
 297
 298 static struct predicate
 299 and_predicates (struct predicate *p, struct predicate *p2)
 300 {
 301   struct predicate out = *p;
 302   int i;
 303
 304   /* Avoid busy work.  */
 305   if (false_predicate_p (p2) || true_predicate_p (p))
 306     return *p2;
 307   if (false_predicate_p (p) || true_predicate_p (p2))
 308     return *p;
 309
 310   /* See how far predicates match.  */
 311   for (i = 0; p->clause[i] && p->clause[i] == p2->clause[i]; i++)
 312     {
 313       gcc_checking_assert (i < MAX_CLAUSES);
 314     }
 315
 316   /* Combine the predicates rest.  */
 317   for (; p2->clause[i]; i++)
 318     {
 319       gcc_checking_assert (i < MAX_CLAUSES);
 320       add_clause (&out, p2->clause[i]);
 321     }
 322   return out;
 323 }
 324
 325
 326 /* Return true if predicates are obviously equal.  */
 327
 328 static inline bool
 329 predicates_equal_p (struct predicate *p, struct predicate *p2)
 330 {
 331   int i;
 332   for (i = 0; p->clause[i]; i++)
 333     {
 334       gcc_checking_assert (i < MAX_CLAUSES);
 335       gcc_checking_assert (p->clause [i] > p->clause[i + 1]);
 336       gcc_checking_assert (!p2->clause[i] || p2->clause [i] > p2->clause[i + 1]);
 337       if (p->clause[i] != p2->clause[i])
 338         return false;
 339     }
 340   return !p2->clause[i];
 341 }
 342
 343
 344 /* Return P | P2.  */
 345
 346 static struct predicate
 347 or_predicates (struct predicate *p, struct predicate *p2)
 348 {
 349   struct predicate out = true_predicate ();
 350   int i,j;
 351
 352   /* Avoid busy work.  */
 353   if (false_predicate_p (p2) || true_predicate_p (p))
 354     return *p;
 355   if (false_predicate_p (p) || true_predicate_p (p2))
 356     return *p2;
 357   if (predicates_equal_p (p, p2))
 358     return *p;
 359
 360   /* OK, combine the predicates.  */
 361   for (i = 0; p->clause[i]; i++)
 362     for (j = 0; p2->clause[j]; j++)
 363       {
 364         gcc_checking_assert (i < MAX_CLAUSES && j < MAX_CLAUSES);
 365         add_clause (&out, p->clause[i] | p2->clause[j]);
 366       }
 367   return out;
 368 }
 369
 370
 371 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false if predicate P
 372    to be false.  */
 373
 374 static bool
 375 evaluate_predicate (struct predicate *p, clause_t possible_truths)
 376 {
 377   int i;
 378
 379   /* True remains true.  */
 380   if (true_predicate_p (p))
 381     return true;
 382
 383   gcc_assert (!(possible_truths & (1 << predicate_false_condition)));
 384
 385   /* See if we can find clause we can disprove.  */
 386   for (i = 0; p->clause[i]; i++)
 387     {
 388       gcc_checking_assert (i < MAX_CLAUSES);
 389       if (!(p->clause[i] & possible_truths))
 390         return false;
 391     }
 392   return true;
 393 }
 394
 395
 396 /* Dump conditional COND.  */
 397
 398 static void
 399 dump_condition (FILE *f, conditions conditions, int cond)
 400 {
 401   condition *c;
 402   if (cond == predicate_false_condition)
 403     fprintf (f, "false");
 404   else if (cond == predicate_not_inlined_condition)
 405     fprintf (f, "not inlined");
 406   else
 407     {
 408       c = VEC_index (condition, conditions, cond - predicate_first_dynamic_condition);
 409       fprintf (f, "op%i", c->operand_num);
 410       if (c->code == IS_NOT_CONSTANT)
 411         {
 412           fprintf (f, " not constant");
 413           return;
 414         }
 415       fprintf (f, " %s ", op_symbol_code (c->code));
 416       print_generic_expr (f, c->val, 1);
 417     }
 418 }
 419
 420
 421 /* Dump clause CLAUSE.  */
 422
 423 static void
 424 dump_clause (FILE *f, conditions conds, clause_t clause)
 425 {
 426   int i;
 427   bool found = false;
 428   fprintf (f, "(");
 429   if (!clause)
 430     fprintf (f, "true");
 431   for (i = 0; i < NUM_CONDITIONS; i++)
 432     if (clause & (1 << i))
 433       {
 434         if (found)
 435           fprintf (f, " || ");
 436         found = true;
 437         dump_condition (f, conds, i);
 438       }
 439   fprintf (f, ")");
 440 }
 441
 442
 443 /* Dump predicate PREDICATE.  */
 444
 445 static void
 446 dump_predicate (FILE *f, conditions conds, struct predicate *pred)
 447 {
 448   int i;
 449   if (true_predicate_p (pred))
 450     dump_clause (f, conds, 0);
 451   else
 452     for (i = 0; pred->clause[i]; i++)
 453       {
 454         if (i)
 455           fprintf (f, " && ");
 456         dump_clause (f, conds, pred->clause[i]);
 457       }
 458   fprintf (f, "\n");
 459 }
 460
 461
 462 /* Record SIZE and TIME under condition PRED into the inline summary.  */
 463
 464 static void
 465 account_size_time (struct inline_summary *summary, int size, int time, struct predicate *pred)
 466 {
 467   size_time_entry *e;
 468   bool found = false;
 469   int i;
 470
 471   if (false_predicate_p (pred))
 472     return;
 473
 474   /* We need to create initial empty unconitional clause, but otherwie
 475      we don't need to account empty times and sizes.  */
 476   if (!size && !time && summary->entry)
 477     return;
 478
 479   /* Watch overflow that might result from insane profiles.  */
 480   if (time > MAX_TIME * INLINE_TIME_SCALE)
 481     time = MAX_TIME * INLINE_TIME_SCALE;
 482   gcc_assert (time >= 0);
 483
 484   for (i = 0; VEC_iterate (size_time_entry, summary->entry, i, e); i++)
 485     if (predicates_equal_p (&e->predicate, pred))
 486       {
 487         found = true;
 488         break;
 489       }
 490   if (i == 32)
 491     {
 492       i = 0;
 493       found = true;
 494       e = VEC_index (size_time_entry, summary->entry, 0);
 495       gcc_assert (!e->predicate.clause[0]);
 496     }
 497   if (dump_file && (dump_flags & TDF_DETAILS) && (time || size))
 498     {
 499       fprintf (dump_file, "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
 500                ((double)size) / INLINE_SIZE_SCALE, ((double)time) / INLINE_TIME_SCALE,
 501                found ? "" : "new ");
 502       dump_predicate (dump_file, summary->conds, pred);
 503     }
 504   if (!found)
 505     {
 506       struct size_time_entry new_entry;
 507       new_entry.size = size;
 508       new_entry.time = time;
 509       new_entry.predicate = *pred;
 510       VEC_safe_push (size_time_entry, gc, summary->entry, &new_entry);
 511     }
 512   else
 513     {
 514       e->size += size;
 515       e->time += time;
 516       if (e->time > MAX_TIME * INLINE_TIME_SCALE)
 517         e->time = MAX_TIME * INLINE_TIME_SCALE;
 518     }
 519 }
 520
 521 /* Set predicate for edge E.  */
 522
 523 static void
 524 edge_set_predicate (struct cgraph_edge *e, struct predicate *predicate)
 525 {
 526   struct inline_edge_summary *es = inline_edge_summary (e);
 527   if (predicate && !true_predicate_p (predicate))
 528     {
 529       if (!es->predicate)
 530         es->predicate = (struct predicate *)pool_alloc (edge_predicate_pool);
 531       *es->predicate = *predicate;
 532     }
 533   else
 534     {
 535       if (es->predicate)
 536         pool_free (edge_predicate_pool, es->predicate);
 537       es->predicate = NULL;
 538     }
 539 }
 540
 541
 542 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
 543    Return clause of possible truths. When INLINE_P is true, assume that
 544    we are inlining.  */
 545
 546 static clause_t
 547 evaluate_conditions_for_known_args (struct cgraph_node *node,
 548                                     bool inline_p,
 549                                     VEC (tree, heap) *known_vals)
 550 {
 551   clause_t clause = inline_p ? 0 : 1 << predicate_not_inlined_condition;
 552   struct inline_summary *info = inline_summary (node);
 553   int i;
 554   struct condition *c;
 555
 556   for (i = 0; VEC_iterate (condition, info->conds, i, c); i++)
 557     {
 558       tree val;
 559       tree res;
 560
 561       /* We allow call stmt to have fewer arguments than the callee
 562          function (especially for K&R style programs).  So bound
 563          check here.  */
 564       if (c->operand_num < (int)VEC_length (tree, known_vals))
 565         val = VEC_index (tree, known_vals, c->operand_num);
 566       else
 567         val = NULL;
 568
 569       if (!val)
 570         {
 571           clause |= 1 << (i + predicate_first_dynamic_condition);
 572           continue;
 573         }
 574       if (c->code == IS_NOT_CONSTANT)
 575         continue;
 576       res = fold_binary_to_constant (c->code, boolean_type_node, val, c->val);
 577       if (res
 578           && integer_zerop (res))
 579         continue;
 580       clause |= 1 << (i + predicate_first_dynamic_condition);
 581     }
 582   return clause;
 583 }
 584
 585
 586 /* Work out what conditions might be true at invocation of E.  */
 587
 588 static clause_t
 589 evaluate_conditions_for_edge (struct cgraph_edge *e, bool inline_p)
 590 {
 591   clause_t clause = inline_p ? 0 : 1 << predicate_not_inlined_condition;
 592   struct inline_summary *info = inline_summary (e->callee);
 593   int i;
 594
 595   if (ipa_node_params_vector && info->conds
 596       /* FIXME: it seems that we forget to get argument count in some cases,
 597          probaby for previously indirect edges or so.  */
 598       && ipa_get_cs_argument_count (IPA_EDGE_REF (e)))
 599     {
 600       struct ipa_node_params *parms_info;
 601       struct ipa_edge_args *args = IPA_EDGE_REF (e);
 602       int i, count = ipa_get_cs_argument_count (args);
 603       VEC (tree, heap) *known_vals = NULL;
 604
 605       if (e->caller->global.inlined_to)
 606         parms_info = IPA_NODE_REF (e->caller->global.inlined_to);
 607       else
 608         parms_info = IPA_NODE_REF (e->caller);
 609
 610       VEC_safe_grow_cleared (tree, heap, known_vals, count);
 611       for (i = 0; i < count; i++)
 612         {
 613           tree cst = ipa_cst_from_jfunc (parms_info,
 614                                          ipa_get_ith_jump_func (args, i));
 615           if (cst)
 616             VEC_replace (tree, known_vals, i, cst);
 617         }
 618       clause = evaluate_conditions_for_known_args (e->callee,
 619                                                    inline_p, known_vals);
 620       VEC_free (tree, heap, known_vals);
 621     }
 622   else
 623     for (i = 0; i < (int)VEC_length (condition, info->conds); i++)
 624       clause |= 1 << (i + predicate_first_dynamic_condition);
 625
 626   return clause;
 627 }
 628
 629
 630 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
 631
 632 static void
 633 inline_summary_alloc (void)
 634 {
 635   if (!node_removal_hook_holder)
 636     node_removal_hook_holder =
 637       cgraph_add_node_removal_hook (&inline_node_removal_hook, NULL);
 638   if (!edge_removal_hook_holder)
 639     edge_removal_hook_holder =
 640       cgraph_add_edge_removal_hook (&inline_edge_removal_hook, NULL);
 641   if (!node_duplication_hook_holder)
 642     node_duplication_hook_holder =
 643       cgraph_add_node_duplication_hook (&inline_node_duplication_hook, NULL);
 644   if (!edge_duplication_hook_holder)
 645     edge_duplication_hook_holder =
 646       cgraph_add_edge_duplication_hook (&inline_edge_duplication_hook, NULL);
 647
 648   if (VEC_length (inline_summary_t, inline_summary_vec)
 649       <= (unsigned) cgraph_max_uid)
 650     VEC_safe_grow_cleared (inline_summary_t, gc,
 651                            inline_summary_vec, cgraph_max_uid + 1);
 652   if (VEC_length (inline_edge_summary_t, inline_edge_summary_vec)
 653       <= (unsigned) cgraph_edge_max_uid)
 654     VEC_safe_grow_cleared (inline_edge_summary_t, heap,
 655                            inline_edge_summary_vec, cgraph_edge_max_uid + 1);
 656   if (!edge_predicate_pool)
 657     edge_predicate_pool = create_alloc_pool ("edge predicates", sizeof (struct predicate),
 658                                              10);
 659 }
 660
 661 /* Hook that is called by cgraph.c when a node is removed.  */
 662
 663 static void
 664 inline_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 665 {
 666   struct inline_summary *info;
 667   if (VEC_length (inline_summary_t, inline_summary_vec)
 668       <= (unsigned)node->uid)
 669     return;
 670   info = inline_summary (node);
 671   reset_node_growth_cache (node);
 672   VEC_free (condition, gc, info->conds);
 673   VEC_free (size_time_entry, gc, info->entry);
 674   info->conds = NULL;
 675   info->entry = NULL;
 676   memset (info, 0, sizeof (inline_summary_t));
 677 }
 678
 679
 680 /* Hook that is called by cgraph.c when a node is duplicated.  */
 681
 682 static void
 683 inline_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
 684                               ATTRIBUTE_UNUSED void *data)
 685 {
 686   struct inline_summary *info;
 687   inline_summary_alloc ();
 688   info = inline_summary (dst);
 689   memcpy (info, inline_summary (src),
 690           sizeof (struct inline_summary));
 691   /* TODO: as an optimization, we may avoid copying conditions
 692      that are known to be false or true.  */
 693   info->conds = VEC_copy (condition, gc, info->conds);
 694
 695   /* When there are any replacements in the function body, see if we can figure
 696      out that something was optimized out.  */
 697   if (ipa_node_params_vector && dst->clone.tree_map)
 698     {
 699       VEC(size_time_entry,gc) *entry = info->entry;
 700       /* Use SRC parm info since it may not be copied yet.  */
 701       struct ipa_node_params *parms_info = IPA_NODE_REF (src);
 702       VEC (tree, heap) *known_vals = NULL;
 703       int count = ipa_get_param_count (parms_info);
 704       int i,j;
 705       clause_t possible_truths;
 706       struct predicate true_pred = true_predicate ();
 707       size_time_entry *e;
 708       int optimized_out_size = 0;
 709       gcov_type optimized_out_time = 0;
 710       bool inlined_to_p = false;
 711       struct cgraph_edge *edge;
 712
 713       info->entry = 0;
 714       VEC_safe_grow_cleared (tree, heap, known_vals, count);
 715       for (i = 0; i < count; i++)
 716         {
 717           tree t = ipa_get_param (parms_info, i);
 718           struct ipa_replace_map *r;
 719
 720           for (j = 0;
 721                VEC_iterate (ipa_replace_map_p, dst->clone.tree_map, j, r);
 722                j++)
 723             {
 724               if (r->old_tree == t
 725                   && r->replace_p
 726                   && !r->ref_p)
 727                 {
 728                   VEC_replace (tree, known_vals, i, r->new_tree);
 729                   break;
 730                 }
 731             }
 732         }
 733       possible_truths = evaluate_conditions_for_known_args (dst,
 734                                                             false, known_vals);
 735       VEC_free (tree, heap, known_vals);
 736
 737       account_size_time (info, 0, 0, &true_pred);
 738
 739       /* Remap size_time vectors.
 740          Simplify the predicate by prunning out alternatives that are known
 741          to be false.
 742          TODO: as on optimization, we can also eliminate conditions known to be true.  */
 743       for (i = 0; VEC_iterate (size_time_entry, entry, i, e); i++)
 744         {
 745           struct predicate new_predicate = true_predicate ();
 746           for (j = 0; e->predicate.clause[j]; j++)
 747             if (!(possible_truths & e->predicate.clause[j]))
 748               {
 749                 new_predicate = false_predicate ();
 750                 break;
 751               }
 752             else
 753               add_clause (&new_predicate,
 754                           possible_truths & e->predicate.clause[j]);
 755           if (false_predicate_p (&new_predicate))
 756             {
 757               optimized_out_size += e->size;
 758               optimized_out_time += e->time;
 759             }
 760           else
 761             account_size_time (info, e->size, e->time, &new_predicate);
 762         }
 763
 764       /* Remap edge predicates with the same simplificaiton as above.  */
 765       for (edge = dst->callees; edge; edge = edge->next_callee)
 766         {
 767           struct predicate new_predicate = true_predicate ();
 768           struct inline_edge_summary *es = inline_edge_summary (edge);
 769
 770           if (!edge->inline_failed)
 771             inlined_to_p = true;
 772           if (!es->predicate)
 773             continue;
 774           for (j = 0; es->predicate->clause[j]; j++)
 775             if (!(possible_truths & es->predicate->clause[j]))
 776               {
 777                 new_predicate = false_predicate ();
 778                 break;
 779               }
 780             else
 781               add_clause (&new_predicate,
 782                           possible_truths & es->predicate->clause[j]);
 783           if (false_predicate_p (&new_predicate)
 784               && !false_predicate_p (es->predicate))
 785             {
 786               optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE;
 787               optimized_out_time += (es->call_stmt_time
 788                                      * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE)
 789                                      * edge->frequency);
 790               edge->frequency = 0;
 791             }
 792           *es->predicate = new_predicate;
 793         }
 794
 795       /* Remap indirect edge predicates with the same simplificaiton as above.  */
 796       for (edge = dst->indirect_calls; edge; edge = edge->next_callee)
 797         {
 798           struct predicate new_predicate = true_predicate ();
 799           struct inline_edge_summary *es = inline_edge_summary (edge);
 800
 801           if (!edge->inline_failed)
 802             inlined_to_p = true;
 803           if (!es->predicate)
 804             continue;
 805           for (j = 0; es->predicate->clause[j]; j++)
 806             if (!(possible_truths & es->predicate->clause[j]))
 807               {
 808                 new_predicate = false_predicate ();
 809                 break;
 810               }
 811             else
 812               add_clause (&new_predicate,
 813                           possible_truths & es->predicate->clause[j]);
 814           if (false_predicate_p (&new_predicate)
 815               && !false_predicate_p (es->predicate))
 816             {
 817               optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE;
 818               optimized_out_time += (es->call_stmt_time
 819                                      * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE)
 820                                      * edge->frequency);
 821               edge->frequency = 0;
 822             }
 823           *es->predicate = new_predicate;
 824         }
 825
 826       /* If inliner or someone after inliner will ever start producing
 827          non-trivial clones, we will get trouble with lack of information
 828          about updating self sizes, because size vectors already contains
 829          sizes of the calees.  */
 830       gcc_assert (!inlined_to_p
 831                   || (!optimized_out_size && !optimized_out_time));
 832
 833       info->size -= optimized_out_size / INLINE_SIZE_SCALE;
 834       info->self_size -= optimized_out_size / INLINE_SIZE_SCALE;
 835       gcc_assert (info->size > 0);
 836       gcc_assert (info->self_size > 0);
 837
 838       optimized_out_time /= INLINE_TIME_SCALE;
 839       if (optimized_out_time > MAX_TIME)
 840         optimized_out_time = MAX_TIME;
 841       info->time -= optimized_out_time;
 842       info->self_time -= optimized_out_time;
 843       if (info->time < 0)
 844         info->time = 0;
 845       if (info->self_time < 0)
 846         info->self_time = 0;
 847     }
 848   else
 849     info->entry = VEC_copy (size_time_entry, gc, info->entry);
 850 }
 851
 852
 853 /* Hook that is called by cgraph.c when a node is duplicated.  */
 854
 855 static void
 856 inline_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
 857                               ATTRIBUTE_UNUSED void *data)
 858 {
 859   struct inline_edge_summary *info;
 860   struct inline_edge_summary *srcinfo;
 861   inline_summary_alloc ();
 862   info = inline_edge_summary (dst);
 863   srcinfo = inline_edge_summary (src);
 864   memcpy (info, srcinfo,
 865           sizeof (struct inline_edge_summary));
 866   info->predicate = NULL;
 867   edge_set_predicate (dst, srcinfo->predicate);
 868 }
 869
 870
 871 /* Keep edge cache consistent across edge removal.  */
 872
 873 static void
 874 inline_edge_removal_hook (struct cgraph_edge *edge, void *data ATTRIBUTE_UNUSED)
 875 {
 876   if (edge_growth_cache)
 877     reset_edge_growth_cache (edge);
 878   if (edge->uid < (int)VEC_length (inline_edge_summary_t, inline_edge_summary_vec))
 879     {
 880       edge_set_predicate (edge, NULL);
 881       memset (inline_edge_summary (edge), 0, sizeof (struct inline_edge_summary));
 882     }
 883 }
 884
 885
 886 /* Initialize growth caches.  */
 887
 888 void
 889 initialize_growth_caches (void)
 890 {
 891   if (cgraph_edge_max_uid)
 892     VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache,
 893                            cgraph_edge_max_uid);
 894   if (cgraph_max_uid)
 895     VEC_safe_grow_cleared (int, heap, node_growth_cache, cgraph_max_uid);
 896 }
 897
 898
 899 /* Free growth caches.  */
 900
 901 void
 902 free_growth_caches (void)
 903 {
 904   VEC_free (edge_growth_cache_entry, heap, edge_growth_cache);
 905   edge_growth_cache = 0;
 906   VEC_free (int, heap, node_growth_cache);
 907   node_growth_cache = 0;
 908 }
 909
 910
 911 /* Dump edge summaries associated to NODE and recursively to all clones.
 912    Indent by INDENT.  */
 913
 914 static void
 915 dump_inline_edge_summary (FILE * f, int indent, struct cgraph_node *node,
 916                           struct inline_summary *info)
 917 {
 918   struct cgraph_edge *edge;
 919   for (edge = node->callees; edge; edge = edge->next_callee)
 920     {
 921       struct inline_edge_summary *es = inline_edge_summary (edge);
 922       fprintf (f, "%*s%s/%i %s\n%*s  loop depth:%2i freq:%4i size:%2i time: %2i callee size:%2i stack:%2i",
 923                indent, "", cgraph_node_name (edge->callee),
 924                edge->callee->uid,
 925                !edge->inline_failed ? "inlined"
 926                : cgraph_inline_failed_string (edge->inline_failed),
 927                indent, "",
 928                es->loop_depth,
 929                edge->frequency,
 930                es->call_stmt_size,
 931                es->call_stmt_time,
 932                (int)inline_summary (edge->callee)->size,
 933                (int)inline_summary (edge->callee)->estimated_stack_size);
 934       if (es->predicate)
 935         {
 936           fprintf (f, " predicate: ");
 937           dump_predicate (f, info->conds, es->predicate);
 938         }
 939       else
 940           fprintf (f, "\n");
 941       if (!edge->inline_failed)
 942         {
 943           fprintf (f, "%*sStack frame offset %i, callee self size %i, callee size %i\n",
 944                    indent+2, "",
 945                    (int)inline_summary (edge->callee)->stack_frame_offset,
 946                    (int)inline_summary (edge->callee)->estimated_self_stack_size,
 947                    (int)inline_summary (edge->callee)->estimated_stack_size);
 948           dump_inline_edge_summary (f, indent+2, edge->callee, info);
 949         }
 950     }
 951   for (edge = node->indirect_calls; edge; edge = edge->next_callee)
 952     {
 953       struct inline_edge_summary *es = inline_edge_summary (edge);
 954       fprintf (f, "%*sindirect call loop depth:%2i freq:%4i size:%2i time: %2i\n",
 955                indent, "",
 956                es->loop_depth,
 957                edge->frequency,
 958                es->call_stmt_size,
 959                es->call_stmt_time);
 960       if (es->predicate)
 961         {
 962           fprintf (f, "predicate: ");
 963           dump_predicate (f, info->conds, es->predicate);
 964         }
 965       else
 966           fprintf (f, "\n");
 967     }
 968 }
 969
 970
 971 void
 972 dump_inline_summary (FILE * f, struct cgraph_node *node)
 973 {
 974   if (node->analyzed)
 975     {
 976       struct inline_summary *s = inline_summary (node);
 977       size_time_entry *e;
 978       int i;
 979       fprintf (f, "Inline summary for %s/%i", cgraph_node_name (node),
 980                node->uid);
 981       if (DECL_DISREGARD_INLINE_LIMITS (node->decl))
 982         fprintf (f, " always_inline");
 983       if (s->inlinable)
 984         fprintf (f, " inlinable");
 985       if (s->versionable)
 986         fprintf (f, " versionable");
 987       fprintf (f, "\n  self time:       %i\n",
 988                s->self_time);
 989       fprintf (f, "  global time:     %i\n", s->time);
 990       fprintf (f, "  self size:       %i\n",
 991                s->self_size);
 992       fprintf (f, "  global size:     %i\n", s->size);
 993       fprintf (f, "  self stack:      %i\n",
 994                (int) s->estimated_self_stack_size);
 995       fprintf (f, "  global stack:    %i\n",
 996                (int) s->estimated_stack_size);
 997       for (i = 0;
 998            VEC_iterate (size_time_entry, s->entry, i, e);
 999            i++)
1000         {
1001           fprintf (f, "    size:%f, time:%f, predicate:",
1002                    (double) e->size / INLINE_SIZE_SCALE,
1003                    (double) e->time / INLINE_TIME_SCALE);
1004           dump_predicate (f, s->conds, &e->predicate);
1005         }
1006       fprintf (f, "  calls:\n");
1007       dump_inline_edge_summary (f, 4, node, s);
1008       fprintf (f, "\n");
1009     }
1010 }
1011
1012 DEBUG_FUNCTION void
1013 debug_inline_summary (struct cgraph_node *node)
1014 {
1015   dump_inline_summary (stderr, node);
1016 }
1017
1018 void
1019 dump_inline_summaries (FILE *f)
1020 {
1021   struct cgraph_node *node;
1022
1023   for (node = cgraph_nodes; node; node = node->next)
1024     if (node->analyzed && !node->global.inlined_to)
1025       dump_inline_summary (f, node);
1026 }
1027
1028 /* Give initial reasons why inlining would fail on EDGE.  This gets either
1029    nullified or usually overwritten by more precise reasons later.  */
1030
1031 void
1032 initialize_inline_failed (struct cgraph_edge *e)
1033 {
1034   struct cgraph_node *callee = e->callee;
1035
1036   if (e->indirect_unknown_callee)
1037     e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
1038   else if (!callee->analyzed)
1039     e->inline_failed = CIF_BODY_NOT_AVAILABLE;
1040   else if (callee->local.redefined_extern_inline)
1041     e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
1042   else if (e->call_stmt && gimple_call_cannot_inline_p (e->call_stmt))
1043     e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
1044   else
1045     e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
1046 }
1047
1048 /* See if statement might disappear after inlining.
1049    0 - means not eliminated
1050    1 - half of statements goes away
1051    2 - for sure it is eliminated.
1052    We are not terribly sophisticated, basically looking for simple abstraction
1053    penalty wrappers.  */
1054
1055 static int
1056 eliminated_by_inlining_prob (gimple stmt)
1057 {
1058   enum gimple_code code = gimple_code (stmt);
1059   switch (code)
1060     {
1061       case GIMPLE_RETURN:
1062         return 2;
1063       case GIMPLE_ASSIGN:
1064         if (gimple_num_ops (stmt) != 2)
1065           return 0;
1066
1067         /* Casts of parameters, loads from parameters passed by reference
1068            and stores to return value or parameters are often free after
1069            inlining dua to SRA and further combining.
1070            Assume that half of statements goes away.  */
1071         if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR
1072             || gimple_assign_rhs_code (stmt) == NOP_EXPR
1073             || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
1074             || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
1075           {
1076             tree rhs = gimple_assign_rhs1 (stmt);
1077             tree lhs = gimple_assign_lhs (stmt);
1078             tree inner_rhs = rhs;
1079             tree inner_lhs = lhs;
1080             bool rhs_free = false;
1081             bool lhs_free = false;
1082
1083             while (handled_component_p (inner_lhs)
1084                    || TREE_CODE (inner_lhs) == MEM_REF)
1085               inner_lhs = TREE_OPERAND (inner_lhs, 0);
1086             while (handled_component_p (inner_rhs)
1087                    || TREE_CODE (inner_rhs) == ADDR_EXPR
1088                    || TREE_CODE (inner_rhs) == MEM_REF)
1089               inner_rhs = TREE_OPERAND (inner_rhs, 0);
1090
1091
1092             if (TREE_CODE (inner_rhs) == PARM_DECL
1093                 || (TREE_CODE (inner_rhs) == SSA_NAME
1094                     && SSA_NAME_IS_DEFAULT_DEF (inner_rhs)
1095                     && TREE_CODE (SSA_NAME_VAR (inner_rhs)) == PARM_DECL))
1096               rhs_free = true;
1097             if (rhs_free && is_gimple_reg (lhs))
1098               lhs_free = true;
1099             if (((TREE_CODE (inner_lhs) == PARM_DECL
1100                   || (TREE_CODE (inner_lhs) == SSA_NAME
1101                       && SSA_NAME_IS_DEFAULT_DEF (inner_lhs)
1102                       && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == PARM_DECL))
1103                  && inner_lhs != lhs)
1104                 || TREE_CODE (inner_lhs) == RESULT_DECL
1105                 || (TREE_CODE (inner_lhs) == SSA_NAME
1106                     && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == RESULT_DECL))
1107               lhs_free = true;
1108             if (lhs_free
1109                 && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
1110               rhs_free = true;
1111             if (lhs_free && rhs_free)
1112               return 1;
1113           }
1114         return 0;
1115       default:
1116         return 0;
1117     }
1118 }
1119
1120
1121 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1122    predicates to the CFG edges.   */
1123
1124 static void
1125 set_cond_stmt_execution_predicate (struct ipa_node_params *info,
1126                                    struct inline_summary *summary,
1127                                    basic_block bb)
1128 {
1129   gimple last;
1130   tree op;
1131   int index;
1132   enum tree_code code, inverted_code;
1133   edge e;
1134   edge_iterator ei;
1135   gimple set_stmt;
1136   tree op2;
1137
1138   last = last_stmt (bb);
1139   if (!last
1140       || gimple_code (last) != GIMPLE_COND)
1141     return;
1142   if (!is_gimple_ip_invariant (gimple_cond_rhs (last)))
1143     return;
1144   op = gimple_cond_lhs (last);
1145   /* TODO: handle conditionals like
1146      var = op0 < 4;
1147      if (var != 0).  */
1148   if (TREE_CODE (op) != SSA_NAME)
1149     return;
1150   if (SSA_NAME_IS_DEFAULT_DEF (op))
1151     {
1152       index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op));
1153       if (index == -1)
1154         return;
1155       code = gimple_cond_code (last);
1156       inverted_code = invert_tree_comparison (code,
1157                                               HONOR_NANS (TYPE_MODE (TREE_TYPE (op))));
1158
1159       FOR_EACH_EDGE (e, ei, bb->succs)
1160         {
1161           struct predicate p = add_condition (summary,
1162                                               index,
1163                                               e->flags & EDGE_TRUE_VALUE
1164                                               ? code : inverted_code,
1165                                               gimple_cond_rhs (last));
1166           e->aux = pool_alloc (edge_predicate_pool);
1167           *(struct predicate *)e->aux = p;
1168         }
1169     }
1170
1171   /* Special case
1172      if (builtin_constant_p (op))
1173        constant_code
1174      else
1175        nonconstant_code.
1176      Here we can predicate nonconstant_code.  We can't
1177      really handle constant_code since we have no predicate
1178      for this and also the constant code is not known to be
1179      optimized away when inliner doen't see operand is constant.
1180      Other optimizers might think otherwise.  */
1181   set_stmt = SSA_NAME_DEF_STMT (op);
1182   if (!gimple_call_builtin_p (set_stmt, BUILT_IN_CONSTANT_P)
1183       || gimple_call_num_args (set_stmt) != 1)
1184     return;
1185   op2 = gimple_call_arg (set_stmt, 0);
1186   if (!SSA_NAME_IS_DEFAULT_DEF (op2))
1187     return;
1188   index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op2));
1189   if (index == -1)
1190     return;
1191   if (gimple_cond_code (last) != NE_EXPR
1192       || !integer_zerop (gimple_cond_rhs (last)))
1193     return;
1194   FOR_EACH_EDGE (e, ei, bb->succs)
1195     if (e->flags & EDGE_FALSE_VALUE)
1196       {
1197         struct predicate p = add_condition (summary,
1198                                             index,
1199                                             IS_NOT_CONSTANT,
1200                                             NULL);
1201         e->aux = pool_alloc (edge_predicate_pool);
1202         *(struct predicate *)e->aux = p;
1203       }
1204 }
1205
1206
1207 /* If BB ends by a switch we can turn into predicates, attach corresponding
1208    predicates to the CFG edges.   */
1209
1210 static void
1211 set_switch_stmt_execution_predicate (struct ipa_node_params *info,
1212                                    struct inline_summary *summary,
1213                                    basic_block bb)
1214 {
1215   gimple last;
1216   tree op;
1217   int index;
1218   edge e;
1219   edge_iterator ei;
1220   size_t n;
1221   size_t case_idx;
1222
1223   last = last_stmt (bb);
1224   if (!last
1225       || gimple_code (last) != GIMPLE_SWITCH)
1226     return;
1227   op = gimple_switch_index (last);
1228   if (TREE_CODE (op) != SSA_NAME
1229       || !SSA_NAME_IS_DEFAULT_DEF (op))
1230     return;
1231   index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op));
1232   if (index == -1)
1233     return;
1234
1235   FOR_EACH_EDGE (e, ei, bb->succs)
1236     {
1237       e->aux = pool_alloc (edge_predicate_pool);
1238       *(struct predicate *)e->aux = false_predicate ();
1239     }
1240   n = gimple_switch_num_labels(last);
1241   for (case_idx = 0; case_idx < n; ++case_idx)
1242     {
1243       tree cl = gimple_switch_label (last, case_idx);
1244       tree min, max;
1245       struct predicate p;
1246
1247       e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
1248       min = CASE_LOW (cl);
1249       max = CASE_HIGH (cl);
1250
1251       /* For default we might want to construct predicate that none
1252          of cases is met, but it is bit hard to do not having negations
1253          of conditionals handy.  */
1254       if (!min && !max)
1255         p = true_predicate ();
1256       else if (!max)
1257         p = add_condition (summary, index,
1258                            EQ_EXPR,
1259                            min);
1260       else
1261         {
1262           struct predicate p1, p2;
1263           p1 = add_condition (summary, index,
1264                               GE_EXPR,
1265                               min);
1266           p2 = add_condition (summary, index,
1267                               LE_EXPR,
1268                               max);
1269           p = and_predicates (&p1, &p2);
1270         }
1271       *(struct predicate *)e->aux
1272         = or_predicates (&p, (struct predicate *)e->aux);
1273     }
1274 }
1275
1276
1277 /* For each BB in NODE attach to its AUX pointer predicate under
1278    which it is executable.  */
1279
1280 static void
1281 compute_bb_predicates (struct cgraph_node *node,
1282                        struct ipa_node_params *parms_info,
1283                        struct inline_summary *summary)
1284 {
1285   struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1286   bool done = false;
1287   basic_block bb;
1288
1289   FOR_EACH_BB_FN (bb, my_function)
1290     {
1291       set_cond_stmt_execution_predicate (parms_info, summary, bb);
1292       set_switch_stmt_execution_predicate (parms_info, summary, bb);
1293     }
1294
1295   /* Entry block is always executable.  */
1296   ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux = pool_alloc (edge_predicate_pool);
1297   *(struct predicate *)ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux
1298     = true_predicate ();
1299
1300   /* A simple dataflow propagation of predicates forward in the CFG.
1301      TODO: work in reverse postorder.  */
1302   while (!done)
1303     {
1304       done = true;
1305       FOR_EACH_BB_FN (bb, my_function)
1306         {
1307           struct predicate p = false_predicate ();
1308           edge e;
1309           edge_iterator ei;
1310           FOR_EACH_EDGE (e, ei, bb->preds)
1311             {
1312               if (e->src->aux)
1313                 {
1314                   struct predicate this_bb_predicate = *(struct predicate *)e->src->aux;
1315                   if (e->aux)
1316                     this_bb_predicate = and_predicates (&this_bb_predicate,
1317                                                         (struct predicate *)e->aux);
1318                   p = or_predicates (&p, &this_bb_predicate);
1319                   if (true_predicate_p (&p))
1320                     break;
1321                 }
1322             }
1323           if (false_predicate_p (&p))
1324             gcc_assert (!bb->aux);
1325           else
1326             {
1327               if (!bb->aux)
1328                 {
1329                   done = false;
1330                   bb->aux = pool_alloc (edge_predicate_pool);
1331                   *((struct predicate *)bb->aux) = p;
1332                 }
1333               else if (!predicates_equal_p (&p, (struct predicate *)bb->aux))
1334                 {
1335                   done = false;
1336                   *((struct predicate *)bb->aux) = p;
1337                 }
1338             }
1339         }
1340     }
1341 }
1342
1343
1344 /* We keep info about constantness of SSA names.  */
1345
1346 typedef struct predicate predicate_t;
1347 DEF_VEC_O (predicate_t);
1348 DEF_VEC_ALLOC_O (predicate_t, heap);
1349
1350
1351 /* Return predicate specifying when the STMT might have result that is not a compile
1352    time constant.  */
1353
1354 static struct predicate
1355 will_be_nonconstant_predicate (struct ipa_node_params *info,
1356                                struct inline_summary *summary,
1357                                gimple stmt,
1358                                VEC (predicate_t, heap) *nonconstant_names)
1359
1360 {
1361   struct predicate p = true_predicate ();
1362   ssa_op_iter iter;
1363   tree use;
1364   struct predicate op_non_const;
1365
1366   /* What statments might be optimized away
1367      when their arguments are constant
1368      TODO: also trivial builtins.
1369      builtin_constant_p is already handled later.  */
1370   if (gimple_code (stmt) != GIMPLE_ASSIGN
1371       && gimple_code (stmt) != GIMPLE_COND
1372       && gimple_code (stmt) != GIMPLE_SWITCH)
1373     return p;
1374
1375   /* Stores and loads will stay anyway.
1376      TODO: Constant memory accesses could be handled here, too.  */
1377   if (gimple_vuse (stmt))
1378     return p;
1379
1380   /* See if we understand all operands before we start
1381      adding conditionals.  */
1382   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1383     {
1384       if (TREE_CODE (use) != SSA_NAME)
1385         return p;
1386       /* For arguments we can build a condition.  */
1387       if (SSA_NAME_IS_DEFAULT_DEF (use)
1388           && ipa_get_param_decl_index (info, SSA_NAME_VAR (use)) >= 0)
1389         continue;
1390       /* If we know when operand is constant,
1391          we still can say something useful.  */
1392       if (!true_predicate_p (VEC_index (predicate_t, nonconstant_names,
1393                                         SSA_NAME_VERSION (use))))
1394         continue;
1395       return p;
1396     }
1397   op_non_const = false_predicate ();
1398   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1399     {
1400       if (SSA_NAME_IS_DEFAULT_DEF (use)
1401           && ipa_get_param_decl_index (info, SSA_NAME_VAR (use)) >= 0)
1402         p = add_condition (summary,
1403                            ipa_get_param_decl_index (info, SSA_NAME_VAR (use)),
1404                            IS_NOT_CONSTANT, NULL);
1405       else
1406         p = *VEC_index (predicate_t, nonconstant_names,
1407                         SSA_NAME_VERSION (use));
1408       op_non_const = or_predicates (&p, &op_non_const);
1409     }
1410   if (gimple_code (stmt) == GIMPLE_ASSIGN
1411       && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
1412     VEC_replace (predicate_t, nonconstant_names,
1413                  SSA_NAME_VERSION (gimple_assign_lhs (stmt)), &op_non_const);
1414   return op_non_const;
1415 }
1416
1417
1418 /* Compute function body size parameters for NODE.
1419    When EARLY is true, we compute only simple summaries without
1420    non-trivial predicates to drive the early inliner.  */
1421
1422 static void
1423 estimate_function_body_sizes (struct cgraph_node *node, bool early)
1424 {
1425   gcov_type time = 0;
1426   /* Estimate static overhead for function prologue/epilogue and alignment. */
1427   int size = 2;
1428   /* Benefits are scaled by probability of elimination that is in range
1429      <0,2>.  */
1430   basic_block bb;
1431   gimple_stmt_iterator bsi;
1432   struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1433   int freq;
1434   struct inline_summary *info = inline_summary (node);
1435   struct predicate bb_predicate;
1436   struct ipa_node_params *parms_info = NULL;
1437   VEC (predicate_t, heap) *nonconstant_names = NULL;
1438
1439   if (ipa_node_params_vector && !early && optimize)
1440     {
1441       parms_info = IPA_NODE_REF (node);
1442       VEC_safe_grow_cleared (predicate_t, heap, nonconstant_names,
1443                              VEC_length (tree, SSANAMES (my_function)));
1444     }
1445
1446   info->conds = 0;
1447   info->entry = 0;
1448
1449
1450   if (dump_file)
1451     fprintf (dump_file, "\nAnalyzing function body size: %s\n",
1452              cgraph_node_name (node));
1453
1454   /* When we run into maximal number of entries, we assign everything to the
1455      constant truth case.  Be sure to have it in list. */
1456   bb_predicate = true_predicate ();
1457   account_size_time (info, 0, 0, &bb_predicate);
1458
1459   bb_predicate = not_inlined_predicate ();
1460   account_size_time (info, 2 * INLINE_SIZE_SCALE, 0, &bb_predicate);
1461
1462   gcc_assert (my_function && my_function->cfg);
1463   if (parms_info)
1464     compute_bb_predicates (node, parms_info, info);
1465   FOR_EACH_BB_FN (bb, my_function)
1466     {
1467       freq = compute_call_stmt_bb_frequency (node->decl, bb);
1468
1469       /* TODO: Obviously predicates can be propagated down across CFG.  */
1470       if (parms_info)
1471         {
1472           if (bb->aux)
1473             bb_predicate = *(struct predicate *)bb->aux;
1474           else
1475             bb_predicate = false_predicate ();
1476         }
1477       else
1478         bb_predicate = true_predicate ();
1479
1480       if (dump_file && (dump_flags & TDF_DETAILS))
1481         {
1482           fprintf (dump_file, "\n BB %i predicate:", bb->index);
1483           dump_predicate (dump_file, info->conds, &bb_predicate);
1484         }
1485
1486       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1487         {
1488           gimple stmt = gsi_stmt (bsi);
1489           int this_size = estimate_num_insns (stmt, &eni_size_weights);
1490           int this_time = estimate_num_insns (stmt, &eni_time_weights);
1491           int prob;
1492           struct predicate will_be_nonconstant;
1493
1494           if (dump_file && (dump_flags & TDF_DETAILS))
1495             {
1496               fprintf (dump_file, "  ");
1497               print_gimple_stmt (dump_file, stmt, 0, 0);
1498               fprintf (dump_file, "\t\tfreq:%3.2f size:%3i time:%3i\n",
1499                        ((double)freq)/CGRAPH_FREQ_BASE, this_size, this_time);
1500             }
1501
1502           if (is_gimple_call (stmt))
1503             {
1504               struct cgraph_edge *edge = cgraph_edge (node, stmt);
1505               struct inline_edge_summary *es = inline_edge_summary (edge);
1506
1507               /* Special case: results of BUILT_IN_CONSTANT_P will be always
1508                  resolved as constant.  We however don't want to optimize
1509                  out the cgraph edges.  */
1510               if (nonconstant_names
1511                   && gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P)
1512                   && gimple_call_lhs (stmt)
1513                   && TREE_CODE (gimple_call_lhs (stmt)) == SSA_NAME)
1514                 {
1515                   struct predicate false_p = false_predicate ();
1516                   VEC_replace (predicate_t, nonconstant_names,
1517                                SSA_NAME_VERSION (gimple_call_lhs (stmt)), &false_p);
1518                 }
1519
1520               es->call_stmt_size = this_size;
1521               es->call_stmt_time = this_time;
1522               es->loop_depth = bb->loop_depth;
1523               edge_set_predicate (edge, &bb_predicate);
1524
1525               /* Do not inline calls where we cannot triviall work around
1526                  mismatches in argument or return types.  */
1527               if (edge->callee
1528                   && !gimple_check_call_matching_types (stmt, edge->callee->decl))
1529                 {
1530                   edge->call_stmt_cannot_inline_p = true;
1531                   gimple_call_set_cannot_inline (stmt, true);
1532                 }
1533               else
1534                 gcc_assert (!gimple_call_cannot_inline_p (stmt));
1535             }
1536
1537           /* TODO: When conditional jump or swithc is known to be constant, but
1538              we did not translate it into the predicates, we really can account
1539              just maximum of the possible paths.  */
1540           if (parms_info)
1541             will_be_nonconstant
1542                = will_be_nonconstant_predicate (parms_info, info,
1543                                                 stmt, nonconstant_names);
1544           if (this_time || this_size)
1545             {
1546               struct predicate p;
1547
1548               this_time *= freq;
1549               time += this_time;
1550               size += this_size;
1551
1552               prob = eliminated_by_inlining_prob (stmt);
1553               if (prob == 1 && dump_file && (dump_flags & TDF_DETAILS))
1554                 fprintf (dump_file, "\t\t50%% will be eliminated by inlining\n");
1555               if (prob == 2 && dump_file && (dump_flags & TDF_DETAILS))
1556                 fprintf (dump_file, "\t\twill eliminated by inlining\n");
1557
1558               if (parms_info)
1559                 p = and_predicates (&bb_predicate, &will_be_nonconstant);
1560               else
1561                 p = true_predicate ();
1562
1563               /* We account everything but the calls.  Calls have their own
1564                  size/time info attached to cgraph edges.  This is neccesary
1565                  in order to make the cost disappear after inlining.  */
1566               if (!is_gimple_call (stmt))
1567                 {
1568                   if (prob)
1569                     {
1570                       struct predicate ip = not_inlined_predicate ();
1571                       ip = and_predicates (&ip, &p);
1572                       account_size_time (info, this_size * prob,
1573                                          this_time * prob, &ip);
1574                     }
1575                   if (prob != 2)
1576                     account_size_time (info, this_size * (2 - prob),
1577                                        this_time * (2 - prob), &p);
1578                 }
1579
1580               gcc_assert (time >= 0);
1581               gcc_assert (size >= 0);
1582             }
1583         }
1584     }
1585   FOR_ALL_BB_FN (bb, my_function)
1586     {
1587       edge e;
1588       edge_iterator ei;
1589
1590       if (bb->aux)
1591         pool_free (edge_predicate_pool, bb->aux);
1592       bb->aux = NULL;
1593       FOR_EACH_EDGE (e, ei, bb->succs)
1594         {
1595           if (e->aux)
1596             pool_free (edge_predicate_pool, e->aux);
1597           e->aux = NULL;
1598         }
1599     }
1600   time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
1601   if (time > MAX_TIME)
1602     time = MAX_TIME;
1603   inline_summary (node)->self_time = time;
1604   inline_summary (node)->self_size = size;
1605   VEC_free (predicate_t, heap, nonconstant_names);
1606   if (dump_file)
1607     {
1608       fprintf (dump_file, "\n");
1609       dump_inline_summary (dump_file, node);
1610     }
1611 }
1612
1613
1614 /* Compute parameters of functions used by inliner.
1615    EARLY is true when we compute parameters for the early inliner  */
1616
1617 void
1618 compute_inline_parameters (struct cgraph_node *node, bool early)
1619 {
1620   HOST_WIDE_INT self_stack_size;
1621   struct cgraph_edge *e;
1622   struct inline_summary *info;
1623
1624   gcc_assert (!node->global.inlined_to);
1625
1626   inline_summary_alloc ();
1627
1628   info = inline_summary (node);
1629
1630   /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
1631      Once this happen, we will need to more curefully predict call
1632      statement size.  */
1633   if (node->thunk.thunk_p)
1634     {
1635       struct inline_edge_summary *es = inline_edge_summary (node->callees);
1636       struct predicate t = true_predicate ();
1637
1638       info->inlinable = info->versionable = 0;
1639       node->callees->call_stmt_cannot_inline_p = true;
1640       node->local.can_change_signature = false;
1641       es->call_stmt_time = 1;
1642       es->call_stmt_size = 1;
1643       account_size_time (info, 0, 0, &t);
1644       return;
1645     }
1646
1647   /* Estimate the stack size for the function if we're optimizing.  */
1648   self_stack_size = optimize ? estimated_stack_frame_size (node) : 0;
1649   info->estimated_self_stack_size = self_stack_size;
1650   info->estimated_stack_size = self_stack_size;
1651   info->stack_frame_offset = 0;
1652
1653   /* Can this function be inlined at all?  */
1654   info->inlinable = tree_inlinable_function_p (node->decl);
1655
1656   /* Inlinable functions always can change signature.  */
1657   if (info->inlinable)
1658     node->local.can_change_signature = true;
1659   else
1660     {
1661       /* Functions calling builtin_apply can not change signature.  */
1662       for (e = node->callees; e; e = e->next_callee)
1663         if (DECL_BUILT_IN (e->callee->decl)
1664             && DECL_BUILT_IN_CLASS (e->callee->decl) == BUILT_IN_NORMAL
1665             && DECL_FUNCTION_CODE (e->callee->decl) == BUILT_IN_APPLY_ARGS)
1666           break;
1667       node->local.can_change_signature = !e;
1668     }
1669   estimate_function_body_sizes (node, early);
1670
1671   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
1672   info->time = info->self_time;
1673   info->size = info->self_size;
1674   info->stack_frame_offset = 0;
1675   info->estimated_stack_size = info->estimated_self_stack_size;
1676 }
1677
1678
1679 /* Compute parameters of functions used by inliner using
1680    current_function_decl.  */
1681
1682 static unsigned int
1683 compute_inline_parameters_for_current (void)
1684 {
1685   compute_inline_parameters (cgraph_get_node (current_function_decl), true);
1686   return 0;
1687 }
1688
1689 struct gimple_opt_pass pass_inline_parameters =
1690 {
1691  {
1692   GIMPLE_PASS,
1693   "inline_param",                       /* name */
1694   NULL,                                 /* gate */
1695   compute_inline_parameters_for_current,/* execute */
1696   NULL,                                 /* sub */
1697   NULL,                                 /* next */
1698   0,                                    /* static_pass_number */
1699   TV_INLINE_HEURISTICS,                 /* tv_id */
1700   0,                                    /* properties_required */
1701   0,                                    /* properties_provided */
1702   0,                                    /* properties_destroyed */
1703   0,                                    /* todo_flags_start */
1704   0                                     /* todo_flags_finish */
1705  }
1706 };
1707
1708
1709 /* Increase SIZE and TIME for size and time needed to handle edge E.  */
1710
1711 static void
1712 estimate_edge_size_and_time (struct cgraph_edge *e, int *size, int *time)
1713 {
1714   struct inline_edge_summary *es = inline_edge_summary (e);
1715   *size += es->call_stmt_size * INLINE_SIZE_SCALE;
1716   *time += (es->call_stmt_time
1717             * e->frequency * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE));
1718   if (*time > MAX_TIME * INLINE_TIME_SCALE)
1719     *time = MAX_TIME * INLINE_TIME_SCALE;
1720 }
1721
1722
1723 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE.  */
1724
1725 static void
1726 estimate_calls_size_and_time (struct cgraph_node *node, int *size, int *time,
1727                               clause_t possible_truths)
1728 {
1729   struct cgraph_edge *e;
1730   for (e = node->callees; e; e = e->next_callee)
1731     {
1732       struct inline_edge_summary *es = inline_edge_summary (e);
1733       if (!es->predicate || evaluate_predicate (es->predicate, possible_truths))
1734         {
1735           if (e->inline_failed)
1736             estimate_edge_size_and_time (e, size, time);
1737           else
1738             estimate_calls_size_and_time (e->callee, size, time,
1739                                           possible_truths);
1740         }
1741     }
1742   /* TODO: look for devirtualizing oppurtunities.  */
1743   for (e = node->indirect_calls; e; e = e->next_callee)
1744     {
1745       struct inline_edge_summary *es = inline_edge_summary (e);
1746       if (!es->predicate || evaluate_predicate (es->predicate, possible_truths))
1747         estimate_edge_size_and_time (e, size, time);
1748     }
1749 }
1750
1751
1752 /* Estimate size and time needed to execute NODE assuming
1753    POSSIBLE_TRUTHS clause. */
1754
1755 static void
1756 estimate_node_size_and_time (struct cgraph_node *node,
1757                              clause_t possible_truths,
1758                              int *ret_size, int *ret_time)
1759 {
1760   struct inline_summary *info = inline_summary (node);
1761   size_time_entry *e;
1762   int size = 0, time = 0;
1763   int i;
1764
1765   if (dump_file
1766       && (dump_flags & TDF_DETAILS))
1767     {
1768       bool found = false;
1769       fprintf (dump_file, "   Estimating body: %s/%i\n"
1770                           "   Known to be false: ",
1771                cgraph_node_name (node),
1772                node->uid);
1773
1774       for (i = predicate_not_inlined_condition;
1775            i < (predicate_first_dynamic_condition
1776                 + (int)VEC_length (condition, info->conds)); i++)
1777         if (!(possible_truths & (1 << i)))
1778           {
1779             if (found)
1780               fprintf (dump_file, ", ");
1781             found = true;
1782             dump_condition (dump_file, info->conds, i);
1783           }
1784     }
1785
1786   for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
1787     if (evaluate_predicate (&e->predicate, possible_truths))
1788       time += e->time, size += e->size;
1789
1790   if (time > MAX_TIME * INLINE_TIME_SCALE)
1791     time = MAX_TIME * INLINE_TIME_SCALE;
1792
1793   estimate_calls_size_and_time (node, &size, &time, possible_truths);
1794   time = (time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
1795   size = (size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
1796
1797
1798   if (dump_file
1799       && (dump_flags & TDF_DETAILS))
1800     fprintf (dump_file, "\n   size:%i time:%i\n", size, time);
1801   if (ret_time)
1802     *ret_time = time;
1803   if (ret_size)
1804     *ret_size = size;
1805   return;
1806 }
1807
1808
1809 /* Estimate size and time needed to execute callee of EDGE assuming that
1810    parameters known to be constant at caller of EDGE are propagated.
1811    KNOWN_VALs is a vector of assumed known constant values for parameters.  */
1812
1813 void
1814 estimate_ipcp_clone_size_and_time (struct cgraph_node *node,
1815                                    VEC (tree, heap) *known_vals,
1816                                    int *ret_size, int *ret_time)
1817 {
1818   clause_t clause;
1819
1820   clause = evaluate_conditions_for_known_args (node, false, known_vals);
1821   estimate_node_size_and_time (node, clause, ret_size, ret_time);
1822 }
1823
1824
1825 /* Translate all conditions from callee representation into caller representation and
1826    symbolically evaluate predicate P into new predicate.
1827
1828    INFO is inline_summary of function we are adding predicate into, CALLEE_INFO is summary
1829    of function predicate P is from. OPERAND_MAP is array giving callee formal IDs the
1830    caller formal IDs. POSSSIBLE_TRUTHS is clausule of all callee conditions that
1831    may be true in caller context. TOPLEV_PREDICATE is predicate under which callee
1832    is executed.  */
1833
1834 static struct predicate
1835 remap_predicate (struct inline_summary *info, struct inline_summary *callee_info,
1836                  struct predicate *p,
1837                  VEC (int, heap) *operand_map,
1838                  clause_t possible_truths,
1839                  struct predicate *toplev_predicate)
1840 {
1841   int i;
1842   struct predicate out = true_predicate ();
1843
1844   /* True predicate is easy.  */
1845   if (true_predicate_p (p))
1846     return *toplev_predicate;
1847   for (i = 0; p->clause[i]; i++)
1848     {
1849       clause_t clause = p->clause[i];
1850       int cond;
1851       struct predicate clause_predicate = false_predicate ();
1852
1853       gcc_assert (i < MAX_CLAUSES);
1854
1855       for (cond = 0; cond < NUM_CONDITIONS; cond ++)
1856         /* Do we have condition we can't disprove?   */
1857         if (clause & possible_truths & (1 << cond))
1858           {
1859             struct predicate cond_predicate;
1860             /* Work out if the condition can translate to predicate in the
1861                inlined function.  */
1862             if (cond >= predicate_first_dynamic_condition)
1863               {
1864                  struct condition *c;
1865
1866                  c = VEC_index (condition, callee_info->conds,
1867                                 cond - predicate_first_dynamic_condition);
1868                  /* See if we can remap condition operand to caller's operand.
1869                     Otherwise give up.  */
1870                  if (!operand_map
1871                      || VEC_index (int, operand_map, c->operand_num) == -1)
1872                    cond_predicate = true_predicate ();
1873                  else
1874                    cond_predicate = add_condition (info,
1875                                                    VEC_index (int, operand_map,
1876                                                               c->operand_num),
1877                                                    c->code, c->val);
1878               }
1879             /* Fixed conditions remains same, construct single
1880                condition predicate.  */
1881             else
1882               {
1883                 cond_predicate.clause[0] = 1 << cond;
1884                 cond_predicate.clause[1] = 0;
1885               }
1886             clause_predicate = or_predicates (&clause_predicate, &cond_predicate);
1887           }
1888       out = and_predicates (&out, &clause_predicate);
1889     }
1890   return and_predicates (&out, toplev_predicate);
1891 }
1892
1893
1894 /* Update summary information of inline clones after inlining.
1895    Compute peak stack usage.  */
1896
1897 static void
1898 inline_update_callee_summaries (struct cgraph_node *node,
1899                                 int depth)
1900 {
1901   struct cgraph_edge *e;
1902   struct inline_summary *callee_info = inline_summary (node);
1903   struct inline_summary *caller_info = inline_summary (node->callers->caller);
1904   HOST_WIDE_INT peak;
1905
1906   callee_info->stack_frame_offset
1907     = caller_info->stack_frame_offset
1908       + caller_info->estimated_self_stack_size;
1909   peak = callee_info->stack_frame_offset
1910       + callee_info->estimated_self_stack_size;
1911   if (inline_summary (node->global.inlined_to)->estimated_stack_size
1912       < peak)
1913     inline_summary (node->global.inlined_to)->estimated_stack_size = peak;
1914   cgraph_propagate_frequency (node);
1915   for (e = node->callees; e; e = e->next_callee)
1916     {
1917       if (!e->inline_failed)
1918         inline_update_callee_summaries (e->callee, depth);
1919       inline_edge_summary (e)->loop_depth += depth;
1920     }
1921   for (e = node->indirect_calls; e; e = e->next_callee)
1922     inline_edge_summary (e)->loop_depth += depth;
1923 }
1924
1925
1926 /* Remap predicates of callees of NODE.  Rest of arguments match
1927    remap_predicate.  */
1928
1929 static void
1930 remap_edge_predicates (struct cgraph_node *node,
1931                        struct inline_summary *info,
1932                        struct inline_summary *callee_info,
1933                        VEC (int, heap) *operand_map,
1934                        clause_t possible_truths,
1935                        struct predicate *toplev_predicate)
1936 {
1937   struct cgraph_edge *e;
1938   for (e = node->callees; e; e = e->next_callee)
1939     {
1940       struct inline_edge_summary *es = inline_edge_summary (e);
1941       struct predicate p;
1942       if (es->predicate)
1943         {
1944           p = remap_predicate (info, callee_info,
1945                                es->predicate, operand_map, possible_truths,
1946                                toplev_predicate);
1947           edge_set_predicate (e, &p);
1948           /* TODO: We should remove the edge for code that will be optimized out,
1949              but we need to keep verifiers and tree-inline happy.
1950              Make it cold for now.  */
1951           if (false_predicate_p (&p))
1952             {
1953               e->count = 0;
1954               e->frequency = 0;
1955             }
1956         }
1957       if (!e->inline_failed)
1958         remap_edge_predicates (e->callee, info, callee_info, operand_map,
1959                                possible_truths, toplev_predicate);
1960       else
1961         edge_set_predicate (e, toplev_predicate);
1962     }
1963   for (e = node->indirect_calls; e; e = e->next_callee)
1964     {
1965       struct inline_edge_summary *es = inline_edge_summary (e);
1966       struct predicate p;
1967       if (es->predicate)
1968         {
1969           p = remap_predicate (info, callee_info,
1970                                es->predicate, operand_map, possible_truths,
1971                                toplev_predicate);
1972           edge_set_predicate (e, &p);
1973           /* TODO: We should remove the edge for code that will be optimized out,
1974              but we need to keep verifiers and tree-inline happy.
1975              Make it cold for now.  */
1976           if (false_predicate_p (&p))
1977             {
1978               e->count = 0;
1979               e->frequency = 0;
1980             }
1981         }
1982       else
1983         edge_set_predicate (e, toplev_predicate);
1984     }
1985 }
1986
1987
1988 /* We inlined EDGE.  Update summary of the function we inlined into.  */
1989
1990 void
1991 inline_merge_summary (struct cgraph_edge *edge)
1992 {
1993   struct inline_summary *callee_info = inline_summary (edge->callee);
1994   struct cgraph_node *to = (edge->caller->global.inlined_to
1995                             ? edge->caller->global.inlined_to : edge->caller);
1996   struct inline_summary *info = inline_summary (to);
1997   clause_t clause = 0;          /* not_inline is known to be false.  */
1998   size_time_entry *e;
1999   VEC (int, heap) *operand_map = NULL;
2000   int i;
2001   struct predicate toplev_predicate;
2002   struct inline_edge_summary *es = inline_edge_summary (edge);
2003
2004   if (es->predicate)
2005     toplev_predicate = *es->predicate;
2006   else
2007     toplev_predicate = true_predicate ();
2008
2009   if (ipa_node_params_vector && callee_info->conds
2010       /* FIXME: it seems that we forget to get argument count in some cases,
2011          probaby for previously indirect edges or so.
2012          Removing the test leads to ICE on tramp3d.  */
2013       && ipa_get_cs_argument_count (IPA_EDGE_REF (edge)))
2014     {
2015       struct ipa_edge_args *args = IPA_EDGE_REF (edge);
2016       int count = ipa_get_cs_argument_count (args);
2017       int i;
2018
2019       clause = evaluate_conditions_for_edge (edge, true);
2020       VEC_safe_grow_cleared (int, heap, operand_map, count);
2021       for (i = 0; i < count; i++)
2022         {
2023           struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i);
2024           int map = -1;
2025           /* TODO: handle non-NOPs when merging.  */
2026           if (jfunc->type == IPA_JF_PASS_THROUGH
2027               && jfunc->value.pass_through.operation == NOP_EXPR)
2028             map = jfunc->value.pass_through.formal_id;
2029           VEC_replace (int, operand_map, i, map);
2030           gcc_assert (map < ipa_get_param_count (IPA_NODE_REF (to)));
2031         }
2032     }
2033   for (i = 0; VEC_iterate (size_time_entry, callee_info->entry, i, e); i++)
2034     {
2035       struct predicate p = remap_predicate (info, callee_info,
2036                                             &e->predicate, operand_map, clause,
2037                                             &toplev_predicate);
2038       gcov_type add_time = ((gcov_type)e->time * edge->frequency
2039                             + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
2040       if (add_time > MAX_TIME)
2041         add_time = MAX_TIME;
2042       account_size_time (info, e->size, add_time, &p);
2043     }
2044   remap_edge_predicates (edge->callee, info, callee_info, operand_map,
2045                          clause, &toplev_predicate);
2046   info->size = 0;
2047   info->time = 0;
2048   for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
2049     info->size += e->size, info->time += e->time;
2050   estimate_calls_size_and_time (to, &info->size, &info->time,
2051                                 ~(clause_t)(1 << predicate_false_condition));
2052
2053   inline_update_callee_summaries (edge->callee,
2054                                   inline_edge_summary (edge)->loop_depth);
2055
2056   info->time = (info->time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
2057   info->size = (info->size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
2058 }
2059
2060
2061 /* Estimate the time cost for the caller when inlining EDGE.
2062    Only to be called via estimate_edge_time, that handles the
2063    caching mechanism.
2064
2065    When caching, also update the cache entry.  Compute both time and
2066    size, since we always need both metrics eventually.  */
2067
2068 int
2069 do_estimate_edge_time (struct cgraph_edge *edge)
2070 {
2071   int time;
2072   int size;
2073   gcov_type ret;
2074   struct inline_edge_summary *es = inline_edge_summary (edge);
2075
2076   gcc_checking_assert (edge->inline_failed);
2077   estimate_node_size_and_time (edge->callee,
2078                                evaluate_conditions_for_edge (edge, true),
2079                                &size, &time);
2080
2081   ret = (((gcov_type)time - es->call_stmt_time) * edge->frequency
2082          + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
2083   if (ret > MAX_TIME)
2084     ret = MAX_TIME;
2085
2086   /* When caching, update the cache entry.  */
2087   if (edge_growth_cache)
2088     {
2089       int ret_size;
2090       if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache)
2091           <= edge->uid)
2092         VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache,
2093                                cgraph_edge_max_uid);
2094       VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->time
2095         = ret + (ret >= 0);
2096
2097       ret_size = size - es->call_stmt_size;
2098       gcc_checking_assert (es->call_stmt_size);
2099       VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->size
2100         = ret_size + (ret_size >= 0);
2101     }
2102   return ret;
2103 }
2104
2105
2106 /* Estimate the growth of the caller when inlining EDGE.
2107    Only to be called via estimate_edge_size.  */
2108
2109 int
2110 do_estimate_edge_growth (struct cgraph_edge *edge)
2111 {
2112   int size;
2113
2114   /* When we do caching, use do_estimate_edge_time to populate the entry.  */
2115
2116   if (edge_growth_cache)
2117     {
2118       do_estimate_edge_time (edge);
2119       size = VEC_index (edge_growth_cache_entry,
2120                         edge_growth_cache,
2121                         edge->uid)->size;
2122       gcc_checking_assert (size);
2123       return size - (size > 0);
2124     }
2125
2126   /* Early inliner runs without caching, go ahead and do the dirty work.  */
2127   gcc_checking_assert (edge->inline_failed);
2128   estimate_node_size_and_time (edge->callee,
2129                                evaluate_conditions_for_edge (edge, true),
2130                                &size, NULL);
2131   gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size);
2132   return size - inline_edge_summary (edge)->call_stmt_size;
2133 }
2134
2135
2136 /* Estimate self time of the function NODE after inlining EDGE.  */
2137
2138 int
2139 estimate_time_after_inlining (struct cgraph_node *node,
2140                               struct cgraph_edge *edge)
2141 {
2142   struct inline_edge_summary *es = inline_edge_summary (edge);
2143   if (!es->predicate || !false_predicate_p (es->predicate))
2144     {
2145       gcov_type time = inline_summary (node)->time + estimate_edge_time (edge);
2146       if (time < 0)
2147         time = 0;
2148       if (time > MAX_TIME)
2149         time = MAX_TIME;
2150       return time;
2151     }
2152   return inline_summary (node)->time;
2153 }
2154
2155
2156 /* Estimate the size of NODE after inlining EDGE which should be an
2157    edge to either NODE or a call inlined into NODE.  */
2158
2159 int
2160 estimate_size_after_inlining (struct cgraph_node *node,
2161                               struct cgraph_edge *edge)
2162 {
2163   struct inline_edge_summary *es = inline_edge_summary (edge);
2164   if (!es->predicate || !false_predicate_p (es->predicate))
2165     {
2166       int size = inline_summary (node)->size + estimate_edge_growth (edge);
2167       gcc_assert (size >= 0);
2168       return size;
2169     }
2170   return inline_summary (node)->size;
2171 }
2172
2173
2174 /* Estimate the growth caused by inlining NODE into all callees.  */
2175
2176 int
2177 do_estimate_growth (struct cgraph_node *node)
2178 {
2179   int growth = 0;
2180   struct cgraph_edge *e;
2181   bool self_recursive = false;
2182   struct inline_summary *info = inline_summary (node);
2183
2184   for (e = node->callers; e; e = e->next_caller)
2185     {
2186       gcc_checking_assert (e->inline_failed);
2187
2188       if (e->caller == node
2189           || (e->caller->global.inlined_to
2190               && e->caller->global.inlined_to == node))
2191         self_recursive = true;
2192       growth += estimate_edge_growth (e);
2193     }
2194
2195
2196   /* For self recursive functions the growth estimation really should be
2197      infinity.  We don't want to return very large values because the growth
2198      plays various roles in badness computation fractions.  Be sure to not
2199      return zero or negative growths. */
2200   if (self_recursive)
2201     growth = growth < info->size ? info->size : growth;
2202   else
2203     {
2204       if (cgraph_will_be_removed_from_program_if_no_direct_calls (node)
2205           && !DECL_EXTERNAL (node->decl))
2206         growth -= info->size;
2207       /* COMDAT functions are very often not shared across multiple units since they
2208          come from various template instantiations.  Take this into account.  */
2209       else  if (DECL_COMDAT (node->decl)
2210                 && cgraph_can_remove_if_no_direct_calls_p (node))
2211         growth -= (info->size
2212                    * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY)) + 50) / 100;
2213     }
2214
2215   if (node_growth_cache)
2216     {
2217       if ((int)VEC_length (int, node_growth_cache) <= node->uid)
2218         VEC_safe_grow_cleared (int, heap, node_growth_cache, cgraph_max_uid);
2219       VEC_replace (int, node_growth_cache, node->uid, growth + (growth >= 0));
2220     }
2221   return growth;
2222 }
2223
2224
2225 /* This function performs intraprocedural analysis in NODE that is required to
2226    inline indirect calls.  */
2227
2228 static void
2229 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
2230 {
2231   ipa_analyze_node (node);
2232   if (dump_file && (dump_flags & TDF_DETAILS))
2233     {
2234       ipa_print_node_params (dump_file, node);
2235       ipa_print_node_jump_functions (dump_file, node);
2236     }
2237 }
2238
2239
2240 /* Note function body size.  */
2241
2242 static void
2243 inline_analyze_function (struct cgraph_node *node)
2244 {
2245   push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2246   current_function_decl = node->decl;
2247
2248   if (dump_file)
2249     fprintf (dump_file, "\nAnalyzing function: %s/%u\n",
2250              cgraph_node_name (node), node->uid);
2251   /* FIXME: We should remove the optimize check after we ensure we never run
2252      IPA passes when not optimizing.  */
2253   if (flag_indirect_inlining && optimize && !node->thunk.thunk_p)
2254     inline_indirect_intraprocedural_analysis (node);
2255   compute_inline_parameters (node, false);
2256
2257   current_function_decl = NULL;
2258   pop_cfun ();
2259 }
2260
2261
2262 /* Called when new function is inserted to callgraph late.  */
2263
2264 static void
2265 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2266 {
2267   inline_analyze_function (node);
2268 }
2269
2270
2271 /* Note function body size.  */
2272
2273 void
2274 inline_generate_summary (void)
2275 {
2276   struct cgraph_node *node;
2277
2278   function_insertion_hook_holder =
2279       cgraph_add_function_insertion_hook (&add_new_function, NULL);
2280
2281   if (flag_indirect_inlining)
2282     ipa_register_cgraph_hooks ();
2283
2284   FOR_EACH_DEFINED_FUNCTION (node)
2285       inline_analyze_function (node);
2286 }
2287
2288
2289 /* Read predicate from IB.  */
2290
2291 static struct predicate
2292 read_predicate (struct lto_input_block *ib)
2293 {
2294   struct predicate out;
2295   clause_t clause;
2296   int k = 0;
2297
2298   do
2299     {
2300       gcc_assert (k <= MAX_CLAUSES);
2301       clause = out.clause[k++] = lto_input_uleb128 (ib);
2302     }
2303   while (clause);
2304   return out;
2305 }
2306
2307
2308 /* Write inline summary for edge E to OB.  */
2309
2310 static void
2311 read_inline_edge_summary (struct lto_input_block *ib, struct cgraph_edge *e)
2312 {
2313   struct inline_edge_summary *es = inline_edge_summary (e);
2314   struct predicate p;
2315
2316   es->call_stmt_size = lto_input_uleb128 (ib);
2317   es->call_stmt_time = lto_input_uleb128 (ib);
2318   es->loop_depth = lto_input_uleb128 (ib);
2319   p = read_predicate (ib);
2320   edge_set_predicate (e, &p);
2321 }
2322
2323
2324 /* Stream in inline summaries from the section.  */
2325
2326 static void
2327 inline_read_section (struct lto_file_decl_data *file_data, const char *data,
2328                      size_t len)
2329 {
2330   const struct lto_function_header *header =
2331     (const struct lto_function_header *) data;
2332   const int32_t cfg_offset = sizeof (struct lto_function_header);
2333   const int32_t main_offset = cfg_offset + header->cfg_size;
2334   const int32_t string_offset = main_offset + header->main_size;
2335   struct data_in *data_in;
2336   struct lto_input_block ib;
2337   unsigned int i, count2, j;
2338   unsigned int f_count;
2339
2340   LTO_INIT_INPUT_BLOCK (ib, (const char *) data + main_offset, 0,
2341                         header->main_size);
2342
2343   data_in =
2344     lto_data_in_create (file_data, (const char *) data + string_offset,
2345                         header->string_size, NULL);
2346   f_count = lto_input_uleb128 (&ib);
2347   for (i = 0; i < f_count; i++)
2348     {
2349       unsigned int index;
2350       struct cgraph_node *node;
2351       struct inline_summary *info;
2352       lto_cgraph_encoder_t encoder;
2353       struct bitpack_d bp;
2354       struct cgraph_edge *e;
2355
2356       index = lto_input_uleb128 (&ib);
2357       encoder = file_data->cgraph_node_encoder;
2358       node = lto_cgraph_encoder_deref (encoder, index);
2359       info = inline_summary (node);
2360
2361       info->estimated_stack_size
2362         = info->estimated_self_stack_size = lto_input_uleb128 (&ib);
2363       info->size = info->self_size = lto_input_uleb128 (&ib);
2364       info->time = info->self_time = lto_input_uleb128 (&ib);
2365
2366       bp = lto_input_bitpack (&ib);
2367       info->inlinable = bp_unpack_value (&bp, 1);
2368       info->versionable = bp_unpack_value (&bp, 1);
2369
2370       count2 = lto_input_uleb128 (&ib);
2371       gcc_assert (!info->conds);
2372       for (j = 0; j < count2; j++)
2373         {
2374           struct condition c;
2375           c.operand_num = lto_input_uleb128 (&ib);
2376           c.code = (enum tree_code) lto_input_uleb128 (&ib);
2377           c.val = lto_input_tree (&ib, data_in);
2378           VEC_safe_push (condition, gc, info->conds, &c);
2379         }
2380       count2 = lto_input_uleb128 (&ib);
2381       gcc_assert (!info->entry);
2382       for (j = 0; j < count2; j++)
2383         {
2384           struct size_time_entry e;
2385
2386           e.size = lto_input_uleb128 (&ib);
2387           e.time = lto_input_uleb128 (&ib);
2388           e.predicate = read_predicate (&ib);
2389
2390           VEC_safe_push (size_time_entry, gc, info->entry, &e);
2391         }
2392       for (e = node->callees; e; e = e->next_callee)
2393         read_inline_edge_summary (&ib, e);
2394       for (e = node->indirect_calls; e; e = e->next_callee)
2395         read_inline_edge_summary (&ib, e);
2396     }
2397
2398   lto_free_section_data (file_data, LTO_section_inline_summary, NULL, data,
2399                          len);
2400   lto_data_in_delete (data_in);
2401 }
2402
2403
2404 /* Read inline summary.  Jump functions are shared among ipa-cp
2405    and inliner, so when ipa-cp is active, we don't need to write them
2406    twice.  */
2407
2408 void
2409 inline_read_summary (void)
2410 {
2411   struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2412   struct lto_file_decl_data *file_data;
2413   unsigned int j = 0;
2414
2415   inline_summary_alloc ();
2416
2417   while ((file_data = file_data_vec[j++]))
2418     {
2419       size_t len;
2420       const char *data = lto_get_section_data (file_data, LTO_section_inline_summary, NULL, &len);
2421       if (data)
2422         inline_read_section (file_data, data, len);
2423       else
2424         /* Fatal error here.  We do not want to support compiling ltrans units with
2425            different version of compiler or different flags than the WPA unit, so
2426            this should never happen.  */
2427         fatal_error ("ipa inline summary is missing in input file");
2428     }
2429   if (flag_indirect_inlining)
2430     {
2431       ipa_register_cgraph_hooks ();
2432       if (!flag_ipa_cp)
2433         ipa_prop_read_jump_functions ();
2434     }
2435   function_insertion_hook_holder =
2436       cgraph_add_function_insertion_hook (&add_new_function, NULL);
2437 }
2438
2439
2440 /* Write predicate P to OB.  */
2441
2442 static void
2443 write_predicate (struct output_block *ob, struct predicate *p)
2444 {
2445   int j;
2446   if (p)
2447     for (j = 0; p->clause[j]; j++)
2448       {
2449          gcc_assert (j < MAX_CLAUSES);
2450          lto_output_uleb128_stream (ob->main_stream,
2451                                     p->clause[j]);
2452       }
2453   lto_output_uleb128_stream (ob->main_stream, 0);
2454 }
2455
2456
2457 /* Write inline summary for edge E to OB.  */
2458
2459 static void
2460 write_inline_edge_summary (struct output_block *ob, struct cgraph_edge *e)
2461 {
2462   struct inline_edge_summary *es = inline_edge_summary (e);
2463   lto_output_uleb128_stream (ob->main_stream, es->call_stmt_size);
2464   lto_output_uleb128_stream (ob->main_stream, es->call_stmt_time);
2465   lto_output_uleb128_stream (ob->main_stream, es->loop_depth);
2466   write_predicate (ob, es->predicate);
2467 }
2468
2469
2470 /* Write inline summary for node in SET.
2471    Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
2472    active, we don't need to write them twice.  */
2473
2474 void
2475 inline_write_summary (cgraph_node_set set,
2476                       varpool_node_set vset ATTRIBUTE_UNUSED)
2477 {
2478   struct cgraph_node *node;
2479   struct output_block *ob = create_output_block (LTO_section_inline_summary);
2480   lto_cgraph_encoder_t encoder = ob->decl_state->cgraph_node_encoder;
2481   unsigned int count = 0;
2482   int i;
2483
2484   for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
2485     if (lto_cgraph_encoder_deref (encoder, i)->analyzed)
2486       count++;
2487   lto_output_uleb128_stream (ob->main_stream, count);
2488
2489   for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
2490     {
2491       node = lto_cgraph_encoder_deref (encoder, i);
2492       if (node->analyzed)
2493         {
2494           struct inline_summary *info = inline_summary (node);
2495           struct bitpack_d bp;
2496           struct cgraph_edge *edge;
2497           int i;
2498           size_time_entry *e;
2499           struct condition *c;
2500
2501
2502           lto_output_uleb128_stream (ob->main_stream,
2503                                      lto_cgraph_encoder_encode (encoder, node));
2504           lto_output_sleb128_stream (ob->main_stream,
2505                                      info->estimated_self_stack_size);
2506           lto_output_sleb128_stream (ob->main_stream,
2507                                      info->self_size);
2508           lto_output_sleb128_stream (ob->main_stream,
2509                                      info->self_time);
2510           bp = bitpack_create (ob->main_stream);
2511           bp_pack_value (&bp, info->inlinable, 1);
2512           bp_pack_value (&bp, info->versionable, 1);
2513           lto_output_bitpack (&bp);
2514           lto_output_uleb128_stream (ob->main_stream,
2515                                      VEC_length (condition, info->conds));
2516           for (i = 0; VEC_iterate (condition, info->conds, i, c); i++)
2517             {
2518               lto_output_uleb128_stream (ob->main_stream,
2519                                          c->operand_num);
2520               lto_output_uleb128_stream (ob->main_stream,
2521                                          c->code);
2522               lto_output_tree (ob, c->val, true);
2523             }
2524           lto_output_uleb128_stream (ob->main_stream,
2525                                      VEC_length (size_time_entry, info->entry));
2526           for (i = 0;
2527                VEC_iterate (size_time_entry, info->entry, i, e);
2528                i++)
2529             {
2530               lto_output_uleb128_stream (ob->main_stream,
2531                                          e->size);
2532               lto_output_uleb128_stream (ob->main_stream,
2533                                          e->time);
2534               write_predicate (ob, &e->predicate);
2535             }
2536           for (edge = node->callees; edge; edge = edge->next_callee)
2537             write_inline_edge_summary (ob, edge);
2538           for (edge = node->indirect_calls; edge; edge = edge->next_callee)
2539             write_inline_edge_summary (ob, edge);
2540         }
2541     }
2542   lto_output_1_stream (ob->main_stream, 0);
2543   produce_asm (ob, NULL);
2544   destroy_output_block (ob);
2545
2546   if (flag_indirect_inlining && !flag_ipa_cp)
2547     ipa_prop_write_jump_functions (set);
2548 }
2549
2550
2551 /* Release inline summary.  */
2552
2553 void
2554 inline_free_summary (void)
2555 {
2556   if (function_insertion_hook_holder)
2557     cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
2558   function_insertion_hook_holder = NULL;
2559   if (node_removal_hook_holder)
2560     cgraph_remove_node_removal_hook (node_removal_hook_holder);
2561   if (edge_removal_hook_holder)
2562     cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
2563   node_removal_hook_holder = NULL;
2564   if (node_duplication_hook_holder)
2565     cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
2566   if (edge_duplication_hook_holder)
2567     cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
2568   node_duplication_hook_holder = NULL;
2569   VEC_free (inline_summary_t, gc, inline_summary_vec);
2570   inline_summary_vec = NULL;
2571   VEC_free (inline_edge_summary_t, heap, inline_edge_summary_vec);
2572   inline_edge_summary_vec = NULL;
2573   if (edge_predicate_pool)
2574     free_alloc_pool (edge_predicate_pool);
2575   edge_predicate_pool = 0;
2576 }