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