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   /* Type attributes can use parameter indices to describe them.  */
1664   if (TYPE_ATTRIBUTES (TREE_TYPE (node->decl)))
1665     node->local.can_change_signature = false;
1666   else
1667     {
1668       /* Otherwise, inlinable functions always can change signature.  */
1669       if (info->inlinable)
1670         node->local.can_change_signature = true;
1671       else
1672         {
1673           /* Functions calling builtin_apply can not change signature.  */
1674           for (e = node->callees; e; e = e->next_callee)
1675             {
1676               tree cdecl = e->callee->decl;
1677               if (DECL_BUILT_IN (cdecl)
1678                   && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
1679                   && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
1680                       || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START))
1681                 break;
1682             }
1683           node->local.can_change_signature = !e;
1684         }
1685     }
1686   estimate_function_body_sizes (node, early);
1687
1688   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
1689   info->time = info->self_time;
1690   info->size = info->self_size;
1691   info->stack_frame_offset = 0;
1692   info->estimated_stack_size = info->estimated_self_stack_size;
1693 }
1694
1695
1696 /* Compute parameters of functions used by inliner using
1697    current_function_decl.  */
1698
1699 static unsigned int
1700 compute_inline_parameters_for_current (void)
1701 {
1702   compute_inline_parameters (cgraph_get_node (current_function_decl), true);
1703   return 0;
1704 }
1705
1706 struct gimple_opt_pass pass_inline_parameters =
1707 {
1708  {
1709   GIMPLE_PASS,
1710   "inline_param",                       /* name */
1711   NULL,                                 /* gate */
1712   compute_inline_parameters_for_current,/* execute */
1713   NULL,                                 /* sub */
1714   NULL,                                 /* next */
1715   0,                                    /* static_pass_number */
1716   TV_INLINE_HEURISTICS,                 /* tv_id */
1717   0,                                    /* properties_required */
1718   0,                                    /* properties_provided */
1719   0,                                    /* properties_destroyed */
1720   0,                                    /* todo_flags_start */
1721   0                                     /* todo_flags_finish */
1722  }
1723 };
1724
1725
1726 /* Increase SIZE and TIME for size and time needed to handle edge E.  */
1727
1728 static void
1729 estimate_edge_size_and_time (struct cgraph_edge *e, int *size, int *time)
1730 {
1731   struct inline_edge_summary *es = inline_edge_summary (e);
1732   *size += es->call_stmt_size * INLINE_SIZE_SCALE;
1733   *time += (es->call_stmt_time
1734             * e->frequency * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE));
1735   if (*time > MAX_TIME * INLINE_TIME_SCALE)
1736     *time = MAX_TIME * INLINE_TIME_SCALE;
1737 }
1738
1739
1740 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE.  */
1741
1742 static void
1743 estimate_calls_size_and_time (struct cgraph_node *node, int *size, int *time,
1744                               clause_t possible_truths)
1745 {
1746   struct cgraph_edge *e;
1747   for (e = node->callees; e; e = e->next_callee)
1748     {
1749       struct inline_edge_summary *es = inline_edge_summary (e);
1750       if (!es->predicate || evaluate_predicate (es->predicate, possible_truths))
1751         {
1752           if (e->inline_failed)
1753             estimate_edge_size_and_time (e, size, time);
1754           else
1755             estimate_calls_size_and_time (e->callee, size, time,
1756                                           possible_truths);
1757         }
1758     }
1759   /* TODO: look for devirtualizing oppurtunities.  */
1760   for (e = node->indirect_calls; e; e = e->next_callee)
1761     {
1762       struct inline_edge_summary *es = inline_edge_summary (e);
1763       if (!es->predicate || evaluate_predicate (es->predicate, possible_truths))
1764         estimate_edge_size_and_time (e, size, time);
1765     }
1766 }
1767
1768
1769 /* Estimate size and time needed to execute NODE assuming
1770    POSSIBLE_TRUTHS clause. */
1771
1772 static void
1773 estimate_node_size_and_time (struct cgraph_node *node,
1774                              clause_t possible_truths,
1775                              int *ret_size, int *ret_time)
1776 {
1777   struct inline_summary *info = inline_summary (node);
1778   size_time_entry *e;
1779   int size = 0, time = 0;
1780   int i;
1781
1782   if (dump_file
1783       && (dump_flags & TDF_DETAILS))
1784     {
1785       bool found = false;
1786       fprintf (dump_file, "   Estimating body: %s/%i\n"
1787                           "   Known to be false: ",
1788                cgraph_node_name (node),
1789                node->uid);
1790
1791       for (i = predicate_not_inlined_condition;
1792            i < (predicate_first_dynamic_condition
1793                 + (int)VEC_length (condition, info->conds)); i++)
1794         if (!(possible_truths & (1 << i)))
1795           {
1796             if (found)
1797               fprintf (dump_file, ", ");
1798             found = true;
1799             dump_condition (dump_file, info->conds, i);
1800           }
1801     }
1802
1803   for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
1804     if (evaluate_predicate (&e->predicate, possible_truths))
1805       time += e->time, size += e->size;
1806
1807   if (time > MAX_TIME * INLINE_TIME_SCALE)
1808     time = MAX_TIME * INLINE_TIME_SCALE;
1809
1810   estimate_calls_size_and_time (node, &size, &time, possible_truths);
1811   time = (time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
1812   size = (size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
1813
1814
1815   if (dump_file
1816       && (dump_flags & TDF_DETAILS))
1817     fprintf (dump_file, "\n   size:%i time:%i\n", size, time);
1818   if (ret_time)
1819     *ret_time = time;
1820   if (ret_size)
1821     *ret_size = size;
1822   return;
1823 }
1824
1825
1826 /* Estimate size and time needed to execute callee of EDGE assuming that
1827    parameters known to be constant at caller of EDGE are propagated.
1828    KNOWN_VALs is a vector of assumed known constant values for parameters.  */
1829
1830 void
1831 estimate_ipcp_clone_size_and_time (struct cgraph_node *node,
1832                                    VEC (tree, heap) *known_vals,
1833                                    int *ret_size, int *ret_time)
1834 {
1835   clause_t clause;
1836
1837   clause = evaluate_conditions_for_known_args (node, false, known_vals);
1838   estimate_node_size_and_time (node, clause, ret_size, ret_time);
1839 }
1840
1841
1842 /* Translate all conditions from callee representation into caller representation and
1843    symbolically evaluate predicate P into new predicate.
1844
1845    INFO is inline_summary of function we are adding predicate into, CALLEE_INFO is summary
1846    of function predicate P is from. OPERAND_MAP is array giving callee formal IDs the
1847    caller formal IDs. POSSSIBLE_TRUTHS is clausule of all callee conditions that
1848    may be true in caller context. TOPLEV_PREDICATE is predicate under which callee
1849    is executed.  */
1850
1851 static struct predicate
1852 remap_predicate (struct inline_summary *info, struct inline_summary *callee_info,
1853                  struct predicate *p,
1854                  VEC (int, heap) *operand_map,
1855                  clause_t possible_truths,
1856                  struct predicate *toplev_predicate)
1857 {
1858   int i;
1859   struct predicate out = true_predicate ();
1860
1861   /* True predicate is easy.  */
1862   if (true_predicate_p (p))
1863     return *toplev_predicate;
1864   for (i = 0; p->clause[i]; i++)
1865     {
1866       clause_t clause = p->clause[i];
1867       int cond;
1868       struct predicate clause_predicate = false_predicate ();
1869
1870       gcc_assert (i < MAX_CLAUSES);
1871
1872       for (cond = 0; cond < NUM_CONDITIONS; cond ++)
1873         /* Do we have condition we can't disprove?   */
1874         if (clause & possible_truths & (1 << cond))
1875           {
1876             struct predicate cond_predicate;
1877             /* Work out if the condition can translate to predicate in the
1878                inlined function.  */
1879             if (cond >= predicate_first_dynamic_condition)
1880               {
1881                  struct condition *c;
1882
1883                  c = VEC_index (condition, callee_info->conds,
1884                                 cond - predicate_first_dynamic_condition);
1885                  /* See if we can remap condition operand to caller's operand.
1886                     Otherwise give up.  */
1887                  if (!operand_map
1888                      || (int)VEC_length (int, operand_map) <= c->operand_num
1889                      || VEC_index (int, operand_map, c->operand_num) == -1)
1890                    cond_predicate = true_predicate ();
1891                  else
1892                    cond_predicate = add_condition (info,
1893                                                    VEC_index (int, operand_map,
1894                                                               c->operand_num),
1895                                                    c->code, c->val);
1896               }
1897             /* Fixed conditions remains same, construct single
1898                condition predicate.  */
1899             else
1900               {
1901                 cond_predicate.clause[0] = 1 << cond;
1902                 cond_predicate.clause[1] = 0;
1903               }
1904             clause_predicate = or_predicates (&clause_predicate, &cond_predicate);
1905           }
1906       out = and_predicates (&out, &clause_predicate);
1907     }
1908   return and_predicates (&out, toplev_predicate);
1909 }
1910
1911
1912 /* Update summary information of inline clones after inlining.
1913    Compute peak stack usage.  */
1914
1915 static void
1916 inline_update_callee_summaries (struct cgraph_node *node,
1917                                 int depth)
1918 {
1919   struct cgraph_edge *e;
1920   struct inline_summary *callee_info = inline_summary (node);
1921   struct inline_summary *caller_info = inline_summary (node->callers->caller);
1922   HOST_WIDE_INT peak;
1923
1924   callee_info->stack_frame_offset
1925     = caller_info->stack_frame_offset
1926       + caller_info->estimated_self_stack_size;
1927   peak = callee_info->stack_frame_offset
1928       + callee_info->estimated_self_stack_size;
1929   if (inline_summary (node->global.inlined_to)->estimated_stack_size
1930       < peak)
1931     inline_summary (node->global.inlined_to)->estimated_stack_size = peak;
1932   cgraph_propagate_frequency (node);
1933   for (e = node->callees; e; e = e->next_callee)
1934     {
1935       if (!e->inline_failed)
1936         inline_update_callee_summaries (e->callee, depth);
1937       inline_edge_summary (e)->loop_depth += depth;
1938     }
1939   for (e = node->indirect_calls; e; e = e->next_callee)
1940     inline_edge_summary (e)->loop_depth += depth;
1941 }
1942
1943
1944 /* Remap predicates of callees of NODE.  Rest of arguments match
1945    remap_predicate.  */
1946
1947 static void
1948 remap_edge_predicates (struct cgraph_node *node,
1949                        struct inline_summary *info,
1950                        struct inline_summary *callee_info,
1951                        VEC (int, heap) *operand_map,
1952                        clause_t possible_truths,
1953                        struct predicate *toplev_predicate)
1954 {
1955   struct cgraph_edge *e;
1956   for (e = node->callees; e; e = e->next_callee)
1957     {
1958       struct inline_edge_summary *es = inline_edge_summary (e);
1959       struct predicate p;
1960       if (es->predicate)
1961         {
1962           p = remap_predicate (info, callee_info,
1963                                es->predicate, operand_map, possible_truths,
1964                                toplev_predicate);
1965           edge_set_predicate (e, &p);
1966           /* TODO: We should remove the edge for code that will be optimized out,
1967              but we need to keep verifiers and tree-inline happy.
1968              Make it cold for now.  */
1969           if (false_predicate_p (&p))
1970             {
1971               e->count = 0;
1972               e->frequency = 0;
1973             }
1974         }
1975       if (!e->inline_failed)
1976         remap_edge_predicates (e->callee, info, callee_info, operand_map,
1977                                possible_truths, toplev_predicate);
1978       else
1979         edge_set_predicate (e, toplev_predicate);
1980     }
1981   for (e = node->indirect_calls; e; e = e->next_callee)
1982     {
1983       struct inline_edge_summary *es = inline_edge_summary (e);
1984       struct predicate p;
1985       if (es->predicate)
1986         {
1987           p = remap_predicate (info, callee_info,
1988                                es->predicate, operand_map, possible_truths,
1989                                toplev_predicate);
1990           edge_set_predicate (e, &p);
1991           /* TODO: We should remove the edge for code that will be optimized out,
1992              but we need to keep verifiers and tree-inline happy.
1993              Make it cold for now.  */
1994           if (false_predicate_p (&p))
1995             {
1996               e->count = 0;
1997               e->frequency = 0;
1998             }
1999         }
2000       else
2001         edge_set_predicate (e, toplev_predicate);
2002     }
2003 }
2004
2005
2006 /* We inlined EDGE.  Update summary of the function we inlined into.  */
2007
2008 void
2009 inline_merge_summary (struct cgraph_edge *edge)
2010 {
2011   struct inline_summary *callee_info = inline_summary (edge->callee);
2012   struct cgraph_node *to = (edge->caller->global.inlined_to
2013                             ? edge->caller->global.inlined_to : edge->caller);
2014   struct inline_summary *info = inline_summary (to);
2015   clause_t clause = 0;          /* not_inline is known to be false.  */
2016   size_time_entry *e;
2017   VEC (int, heap) *operand_map = NULL;
2018   int i;
2019   struct predicate toplev_predicate;
2020   struct inline_edge_summary *es = inline_edge_summary (edge);
2021
2022   if (es->predicate)
2023     toplev_predicate = *es->predicate;
2024   else
2025     toplev_predicate = true_predicate ();
2026
2027   if (ipa_node_params_vector && callee_info->conds
2028       /* FIXME: it seems that we forget to get argument count in some cases,
2029          probaby for previously indirect edges or so.
2030          Removing the test leads to ICE on tramp3d.  */
2031       && ipa_get_cs_argument_count (IPA_EDGE_REF (edge)))
2032     {
2033       struct ipa_edge_args *args = IPA_EDGE_REF (edge);
2034       int count = ipa_get_cs_argument_count (args);
2035       int i;
2036
2037       clause = evaluate_conditions_for_edge (edge, true);
2038       VEC_safe_grow_cleared (int, heap, operand_map, count);
2039       for (i = 0; i < count; i++)
2040         {
2041           struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i);
2042           int map = -1;
2043           /* TODO: handle non-NOPs when merging.  */
2044           if (jfunc->type == IPA_JF_PASS_THROUGH
2045               && jfunc->value.pass_through.operation == NOP_EXPR)
2046             map = jfunc->value.pass_through.formal_id;
2047           VEC_replace (int, operand_map, i, map);
2048           gcc_assert (map < ipa_get_param_count (IPA_NODE_REF (to)));
2049         }
2050     }
2051   for (i = 0; VEC_iterate (size_time_entry, callee_info->entry, i, e); i++)
2052     {
2053       struct predicate p = remap_predicate (info, callee_info,
2054                                             &e->predicate, operand_map, clause,
2055                                             &toplev_predicate);
2056       gcov_type add_time = ((gcov_type)e->time * edge->frequency
2057                             + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
2058       if (add_time > MAX_TIME)
2059         add_time = MAX_TIME;
2060       account_size_time (info, e->size, add_time, &p);
2061     }
2062   remap_edge_predicates (edge->callee, info, callee_info, operand_map,
2063                          clause, &toplev_predicate);
2064   info->size = 0;
2065   info->time = 0;
2066   for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
2067     info->size += e->size, info->time += e->time;
2068   estimate_calls_size_and_time (to, &info->size, &info->time,
2069                                 ~(clause_t)(1 << predicate_false_condition));
2070
2071   inline_update_callee_summaries (edge->callee,
2072                                   inline_edge_summary (edge)->loop_depth);
2073
2074   info->time = (info->time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
2075   info->size = (info->size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
2076 }
2077
2078
2079 /* Estimate the time cost for the caller when inlining EDGE.
2080    Only to be called via estimate_edge_time, that handles the
2081    caching mechanism.
2082
2083    When caching, also update the cache entry.  Compute both time and
2084    size, since we always need both metrics eventually.  */
2085
2086 int
2087 do_estimate_edge_time (struct cgraph_edge *edge)
2088 {
2089   int time;
2090   int size;
2091   gcov_type ret;
2092   struct inline_edge_summary *es = inline_edge_summary (edge);
2093
2094   gcc_checking_assert (edge->inline_failed);
2095   estimate_node_size_and_time (cgraph_function_or_thunk_node (edge->callee, NULL),
2096                                evaluate_conditions_for_edge (edge, true),
2097                                &size, &time);
2098
2099   ret = (((gcov_type)time - es->call_stmt_time) * edge->frequency
2100          + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
2101   if (ret > MAX_TIME)
2102     ret = MAX_TIME;
2103
2104   /* When caching, update the cache entry.  */
2105   if (edge_growth_cache)
2106     {
2107       int ret_size;
2108       if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache)
2109           <= edge->uid)
2110         VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache,
2111                                cgraph_edge_max_uid);
2112       VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->time
2113         = ret + (ret >= 0);
2114
2115       ret_size = size - es->call_stmt_size;
2116       gcc_checking_assert (es->call_stmt_size);
2117       VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->size
2118         = ret_size + (ret_size >= 0);
2119     }
2120   return ret;
2121 }
2122
2123
2124 /* Estimate the growth of the caller when inlining EDGE.
2125    Only to be called via estimate_edge_size.  */
2126
2127 int
2128 do_estimate_edge_growth (struct cgraph_edge *edge)
2129 {
2130   int size;
2131   struct cgraph_node *callee;
2132
2133   /* When we do caching, use do_estimate_edge_time to populate the entry.  */
2134
2135   if (edge_growth_cache)
2136     {
2137       do_estimate_edge_time (edge);
2138       size = VEC_index (edge_growth_cache_entry,
2139                         edge_growth_cache,
2140                         edge->uid)->size;
2141       gcc_checking_assert (size);
2142       return size - (size > 0);
2143     }
2144   callee = cgraph_function_or_thunk_node (edge->callee, NULL);
2145
2146   /* Early inliner runs without caching, go ahead and do the dirty work.  */
2147   gcc_checking_assert (edge->inline_failed);
2148   estimate_node_size_and_time (callee,
2149                                evaluate_conditions_for_edge (edge, true),
2150                                &size, NULL);
2151   gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size);
2152   return size - inline_edge_summary (edge)->call_stmt_size;
2153 }
2154
2155
2156 /* Estimate self time of the function NODE after inlining EDGE.  */
2157
2158 int
2159 estimate_time_after_inlining (struct cgraph_node *node,
2160                               struct cgraph_edge *edge)
2161 {
2162   struct inline_edge_summary *es = inline_edge_summary (edge);
2163   if (!es->predicate || !false_predicate_p (es->predicate))
2164     {
2165       gcov_type time = inline_summary (node)->time + estimate_edge_time (edge);
2166       if (time < 0)
2167         time = 0;
2168       if (time > MAX_TIME)
2169         time = MAX_TIME;
2170       return time;
2171     }
2172   return inline_summary (node)->time;
2173 }
2174
2175
2176 /* Estimate the size of NODE after inlining EDGE which should be an
2177    edge to either NODE or a call inlined into NODE.  */
2178
2179 int
2180 estimate_size_after_inlining (struct cgraph_node *node,
2181                               struct cgraph_edge *edge)
2182 {
2183   struct inline_edge_summary *es = inline_edge_summary (edge);
2184   if (!es->predicate || !false_predicate_p (es->predicate))
2185     {
2186       int size = inline_summary (node)->size + estimate_edge_growth (edge);
2187       gcc_assert (size >= 0);
2188       return size;
2189     }
2190   return inline_summary (node)->size;
2191 }
2192
2193
2194 struct growth_data
2195 {
2196   bool self_recursive;
2197   int growth;
2198 };
2199
2200
2201 /* Worker for do_estimate_growth.  Collect growth for all callers.  */
2202
2203 static bool
2204 do_estimate_growth_1 (struct cgraph_node *node, void *data)
2205 {
2206   struct cgraph_edge *e;
2207   struct growth_data *d = (struct growth_data *) data;
2208
2209   for (e = node->callers; e; e = e->next_caller)
2210     {
2211       gcc_checking_assert (e->inline_failed);
2212
2213       if (e->caller == node
2214           || (e->caller->global.inlined_to
2215               && e->caller->global.inlined_to == node))
2216         d->self_recursive = true;
2217       d->growth += estimate_edge_growth (e);
2218     }
2219   return false;
2220 }
2221
2222
2223 /* Estimate the growth caused by inlining NODE into all callees.  */
2224
2225 int
2226 do_estimate_growth (struct cgraph_node *node)
2227 {
2228   struct growth_data d = {0, false};
2229   struct inline_summary *info = inline_summary (node);
2230
2231   cgraph_for_node_and_aliases (node, do_estimate_growth_1, &d, true);
2232
2233   /* For self recursive functions the growth estimation really should be
2234      infinity.  We don't want to return very large values because the growth
2235      plays various roles in badness computation fractions.  Be sure to not
2236      return zero or negative growths. */
2237   if (d.self_recursive)
2238     d.growth = d.growth < info->size ? info->size : d.growth;
2239   else
2240     {
2241       if (!DECL_EXTERNAL (node->decl)
2242           && cgraph_will_be_removed_from_program_if_no_direct_calls (node))
2243         d.growth -= info->size;
2244       /* COMDAT functions are very often not shared across multiple units since they
2245          come from various template instantiations.  Take this into account.  */
2246       else  if (DECL_COMDAT (node->decl)
2247                 && cgraph_can_remove_if_no_direct_calls_p (node))
2248         d.growth -= (info->size
2249                      * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY)) + 50) / 100;
2250     }
2251
2252   if (node_growth_cache)
2253     {
2254       if ((int)VEC_length (int, node_growth_cache) <= node->uid)
2255         VEC_safe_grow_cleared (int, heap, node_growth_cache, cgraph_max_uid);
2256       VEC_replace (int, node_growth_cache, node->uid, d.growth + (d.growth >= 0));
2257     }
2258   return d.growth;
2259 }
2260
2261
2262 /* This function performs intraprocedural analysis in NODE that is required to
2263    inline indirect calls.  */
2264
2265 static void
2266 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
2267 {
2268   ipa_analyze_node (node);
2269   if (dump_file && (dump_flags & TDF_DETAILS))
2270     {
2271       ipa_print_node_params (dump_file, node);
2272       ipa_print_node_jump_functions (dump_file, node);
2273     }
2274 }
2275
2276
2277 /* Note function body size.  */
2278
2279 static void
2280 inline_analyze_function (struct cgraph_node *node)
2281 {
2282   push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2283   current_function_decl = node->decl;
2284
2285   if (dump_file)
2286     fprintf (dump_file, "\nAnalyzing function: %s/%u\n",
2287              cgraph_node_name (node), node->uid);
2288   /* FIXME: We should remove the optimize check after we ensure we never run
2289      IPA passes when not optimizing.  */
2290   if (flag_indirect_inlining && optimize && !node->thunk.thunk_p)
2291     inline_indirect_intraprocedural_analysis (node);
2292   compute_inline_parameters (node, false);
2293
2294   current_function_decl = NULL;
2295   pop_cfun ();
2296 }
2297
2298
2299 /* Called when new function is inserted to callgraph late.  */
2300
2301 static void
2302 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2303 {
2304   inline_analyze_function (node);
2305 }
2306
2307
2308 /* Note function body size.  */
2309
2310 void
2311 inline_generate_summary (void)
2312 {
2313   struct cgraph_node *node;
2314
2315   function_insertion_hook_holder =
2316       cgraph_add_function_insertion_hook (&add_new_function, NULL);
2317
2318   if (flag_indirect_inlining)
2319     ipa_register_cgraph_hooks ();
2320
2321   FOR_EACH_DEFINED_FUNCTION (node)
2322     if (!node->alias)
2323       inline_analyze_function (node);
2324 }
2325
2326
2327 /* Read predicate from IB.  */
2328
2329 static struct predicate
2330 read_predicate (struct lto_input_block *ib)
2331 {
2332   struct predicate out;
2333   clause_t clause;
2334   int k = 0;
2335
2336   do
2337     {
2338       gcc_assert (k <= MAX_CLAUSES);
2339       clause = out.clause[k++] = streamer_read_uhwi (ib);
2340     }
2341   while (clause);
2342
2343   /* Zero-initialize the remaining clauses in OUT.  */
2344   while (k <= MAX_CLAUSES)
2345     out.clause[k++] = 0;
2346
2347   return out;
2348 }
2349
2350
2351 /* Write inline summary for edge E to OB.  */
2352
2353 static void
2354 read_inline_edge_summary (struct lto_input_block *ib, struct cgraph_edge *e)
2355 {
2356   struct inline_edge_summary *es = inline_edge_summary (e);
2357   struct predicate p;
2358
2359   es->call_stmt_size = streamer_read_uhwi (ib);
2360   es->call_stmt_time = streamer_read_uhwi (ib);
2361   es->loop_depth = streamer_read_uhwi (ib);
2362   p = read_predicate (ib);
2363   edge_set_predicate (e, &p);
2364 }
2365
2366
2367 /* Stream in inline summaries from the section.  */
2368
2369 static void
2370 inline_read_section (struct lto_file_decl_data *file_data, const char *data,
2371                      size_t len)
2372 {
2373   const struct lto_function_header *header =
2374     (const struct lto_function_header *) data;
2375   const int32_t cfg_offset = sizeof (struct lto_function_header);
2376   const int32_t main_offset = cfg_offset + header->cfg_size;
2377   const int32_t string_offset = main_offset + header->main_size;
2378   struct data_in *data_in;
2379   struct lto_input_block ib;
2380   unsigned int i, count2, j;
2381   unsigned int f_count;
2382
2383   LTO_INIT_INPUT_BLOCK (ib, (const char *) data + main_offset, 0,
2384                         header->main_size);
2385
2386   data_in =
2387     lto_data_in_create (file_data, (const char *) data + string_offset,
2388                         header->string_size, NULL);
2389   f_count = streamer_read_uhwi (&ib);
2390   for (i = 0; i < f_count; i++)
2391     {
2392       unsigned int index;
2393       struct cgraph_node *node;
2394       struct inline_summary *info;
2395       lto_cgraph_encoder_t encoder;
2396       struct bitpack_d bp;
2397       struct cgraph_edge *e;
2398
2399       index = streamer_read_uhwi (&ib);
2400       encoder = file_data->cgraph_node_encoder;
2401       node = lto_cgraph_encoder_deref (encoder, index);
2402       info = inline_summary (node);
2403
2404       info->estimated_stack_size
2405         = info->estimated_self_stack_size = streamer_read_uhwi (&ib);
2406       info->size = info->self_size = streamer_read_uhwi (&ib);
2407       info->time = info->self_time = streamer_read_uhwi (&ib);
2408
2409       bp = streamer_read_bitpack (&ib);
2410       info->inlinable = bp_unpack_value (&bp, 1);
2411       info->versionable = bp_unpack_value (&bp, 1);
2412
2413       count2 = streamer_read_uhwi (&ib);
2414       gcc_assert (!info->conds);
2415       for (j = 0; j < count2; j++)
2416         {
2417           struct condition c;
2418           c.operand_num = streamer_read_uhwi (&ib);
2419           c.code = (enum tree_code) streamer_read_uhwi (&ib);
2420           c.val = stream_read_tree (&ib, data_in);
2421           VEC_safe_push (condition, gc, info->conds, &c);
2422         }
2423       count2 = streamer_read_uhwi (&ib);
2424       gcc_assert (!info->entry);
2425       for (j = 0; j < count2; j++)
2426         {
2427           struct size_time_entry e;
2428
2429           e.size = streamer_read_uhwi (&ib);
2430           e.time = streamer_read_uhwi (&ib);
2431           e.predicate = read_predicate (&ib);
2432
2433           VEC_safe_push (size_time_entry, gc, info->entry, &e);
2434         }
2435       for (e = node->callees; e; e = e->next_callee)
2436         read_inline_edge_summary (&ib, e);
2437       for (e = node->indirect_calls; e; e = e->next_callee)
2438         read_inline_edge_summary (&ib, e);
2439     }
2440
2441   lto_free_section_data (file_data, LTO_section_inline_summary, NULL, data,
2442                          len);
2443   lto_data_in_delete (data_in);
2444 }
2445
2446
2447 /* Read inline summary.  Jump functions are shared among ipa-cp
2448    and inliner, so when ipa-cp is active, we don't need to write them
2449    twice.  */
2450
2451 void
2452 inline_read_summary (void)
2453 {
2454   struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2455   struct lto_file_decl_data *file_data;
2456   unsigned int j = 0;
2457
2458   inline_summary_alloc ();
2459
2460   while ((file_data = file_data_vec[j++]))
2461     {
2462       size_t len;
2463       const char *data = lto_get_section_data (file_data, LTO_section_inline_summary, NULL, &len);
2464       if (data)
2465         inline_read_section (file_data, data, len);
2466       else
2467         /* Fatal error here.  We do not want to support compiling ltrans units with
2468            different version of compiler or different flags than the WPA unit, so
2469            this should never happen.  */
2470         fatal_error ("ipa inline summary is missing in input file");
2471     }
2472   if (flag_indirect_inlining)
2473     {
2474       ipa_register_cgraph_hooks ();
2475       if (!flag_ipa_cp)
2476         ipa_prop_read_jump_functions ();
2477     }
2478   function_insertion_hook_holder =
2479       cgraph_add_function_insertion_hook (&add_new_function, NULL);
2480 }
2481
2482
2483 /* Write predicate P to OB.  */
2484
2485 static void
2486 write_predicate (struct output_block *ob, struct predicate *p)
2487 {
2488   int j;
2489   if (p)
2490     for (j = 0; p->clause[j]; j++)
2491       {
2492          gcc_assert (j < MAX_CLAUSES);
2493          streamer_write_uhwi (ob, p->clause[j]);
2494       }
2495   streamer_write_uhwi (ob, 0);
2496 }
2497
2498
2499 /* Write inline summary for edge E to OB.  */
2500
2501 static void
2502 write_inline_edge_summary (struct output_block *ob, struct cgraph_edge *e)
2503 {
2504   struct inline_edge_summary *es = inline_edge_summary (e);
2505   streamer_write_uhwi (ob, es->call_stmt_size);
2506   streamer_write_uhwi (ob, es->call_stmt_time);
2507   streamer_write_uhwi (ob, es->loop_depth);
2508   write_predicate (ob, es->predicate);
2509 }
2510
2511
2512 /* Write inline summary for node in SET.
2513    Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
2514    active, we don't need to write them twice.  */
2515
2516 void
2517 inline_write_summary (cgraph_node_set set,
2518                       varpool_node_set vset ATTRIBUTE_UNUSED)
2519 {
2520   struct cgraph_node *node;
2521   struct output_block *ob = create_output_block (LTO_section_inline_summary);
2522   lto_cgraph_encoder_t encoder = ob->decl_state->cgraph_node_encoder;
2523   unsigned int count = 0;
2524   int i;
2525
2526   for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
2527     if (lto_cgraph_encoder_deref (encoder, i)->analyzed)
2528       count++;
2529   streamer_write_uhwi (ob, count);
2530
2531   for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
2532     {
2533       node = lto_cgraph_encoder_deref (encoder, i);
2534       if (node->analyzed)
2535         {
2536           struct inline_summary *info = inline_summary (node);
2537           struct bitpack_d bp;
2538           struct cgraph_edge *edge;
2539           int i;
2540           size_time_entry *e;
2541           struct condition *c;
2542
2543
2544           streamer_write_uhwi (ob, lto_cgraph_encoder_encode (encoder, node));
2545           streamer_write_hwi (ob, info->estimated_self_stack_size);
2546           streamer_write_hwi (ob, info->self_size);
2547           streamer_write_hwi (ob, info->self_time);
2548           bp = bitpack_create (ob->main_stream);
2549           bp_pack_value (&bp, info->inlinable, 1);
2550           bp_pack_value (&bp, info->versionable, 1);
2551           streamer_write_bitpack (&bp);
2552           streamer_write_uhwi (ob, VEC_length (condition, info->conds));
2553           for (i = 0; VEC_iterate (condition, info->conds, i, c); i++)
2554             {
2555               streamer_write_uhwi (ob, c->operand_num);
2556               streamer_write_uhwi (ob, c->code);
2557               stream_write_tree (ob, c->val, true);
2558             }
2559           streamer_write_uhwi (ob, VEC_length (size_time_entry, info->entry));
2560           for (i = 0;
2561                VEC_iterate (size_time_entry, info->entry, i, e);
2562                i++)
2563             {
2564               streamer_write_uhwi (ob, e->size);
2565               streamer_write_uhwi (ob, e->time);
2566               write_predicate (ob, &e->predicate);
2567             }
2568           for (edge = node->callees; edge; edge = edge->next_callee)
2569             write_inline_edge_summary (ob, edge);
2570           for (edge = node->indirect_calls; edge; edge = edge->next_callee)
2571             write_inline_edge_summary (ob, edge);
2572         }
2573     }
2574   streamer_write_char_stream (ob->main_stream, 0);
2575   produce_asm (ob, NULL);
2576   destroy_output_block (ob);
2577
2578   if (flag_indirect_inlining && !flag_ipa_cp)
2579     ipa_prop_write_jump_functions (set);
2580 }
2581
2582
2583 /* Release inline summary.  */
2584
2585 void
2586 inline_free_summary (void)
2587 {
2588   if (function_insertion_hook_holder)
2589     cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
2590   function_insertion_hook_holder = NULL;
2591   if (node_removal_hook_holder)
2592     cgraph_remove_node_removal_hook (node_removal_hook_holder);
2593   if (edge_removal_hook_holder)
2594     cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
2595   node_removal_hook_holder = NULL;
2596   if (node_duplication_hook_holder)
2597     cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
2598   if (edge_duplication_hook_holder)
2599     cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
2600   node_duplication_hook_holder = NULL;
2601   VEC_free (inline_summary_t, gc, inline_summary_vec);
2602   inline_summary_vec = NULL;
2603   VEC_free (inline_edge_summary_t, heap, inline_edge_summary_vec);
2604   inline_edge_summary_vec = NULL;
2605   if (edge_predicate_pool)
2606     free_alloc_pool (edge_predicate_pool);
2607   edge_predicate_pool = 0;
2608 }