gcc/ipa-cp.c

   1 /* Interprocedural constant propagation
   2    Copyright (C) 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
   3    Contributed by Razya Ladelsky <RAZYA@il.ibm.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* Interprocedural constant propagation.  The aim of interprocedural constant
  22    propagation (IPCP) is to find which function's argument has the same
  23    constant value in each invocation throughout the whole program. For example,
  24    consider the following program:
  25
  26    int g (int y)
  27    {
  28      printf ("value is %d",y);
  29    }
  30
  31    int f (int x)
  32    {
  33      g (x);
  34    }
  35
  36    int h (int y)
  37    {
  38      g (y);
  39    }
  40
  41    void main (void)
  42    {
  43      f (3);
  44      h (3);
  45    }
  46
  47
  48    The IPCP algorithm will find that g's formal argument y is always called
  49    with the value 3.
  50
  51    The algorithm used is based on "Interprocedural Constant Propagation", by
  52    Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86, pg
  53    152-161
  54
  55    The optimization is divided into three stages:
  56
  57    First stage - intraprocedural analysis
  58    =======================================
  59    This phase computes jump_function and modification flags.
  60
  61    A jump function for a callsite represents the values passed as an actual
  62    arguments of a given callsite. There are three types of values:
  63    Pass through - the caller's formal parameter is passed as an actual argument.
  64    Constant - a constant is passed as an actual argument.
  65    Unknown - neither of the above.
  66
  67    The jump function info, ipa_jump_func, is stored in ipa_edge_args
  68    structure (defined in ipa_prop.h and pointed to by cgraph_node->aux)
  69    modified_flags are defined in ipa_node_params structure
  70    (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
  71
  72    -ipcp_init_stage() is the first stage driver.
  73
  74    Second stage - interprocedural analysis
  75    ========================================
  76    This phase does the interprocedural constant propagation.
  77    It computes lattices for all formal parameters in the program
  78    and their value that may be:
  79    TOP - unknown.
  80    BOTTOM - non constant.
  81    CONSTANT - constant value.
  82
  83    Lattice describing a formal parameter p will have a constant value if all
  84    callsites invoking this function have the same constant value passed to p.
  85
  86    The lattices are stored in ipcp_lattice which is itself in ipa_node_params
  87    structure (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
  88
  89    -ipcp_iterate_stage() is the second stage driver.
  90
  91    Third phase - transformation of function code
  92    ============================================
  93    Propagates the constant-valued formals into the function.
  94    For each function whose parameters are constants, we create its clone.
  95
  96    Then we process the clone in two ways:
  97    1. We insert an assignment statement 'parameter = const' at the beginning
  98       of the cloned function.
  99    2. For read-only parameters that do not live in memory, we replace all their
 100       uses with the constant.
 101
 102    We also need to modify some callsites to call the cloned functions instead
 103    of the original ones.  For a callsite passing an argument found to be a
 104    constant by IPCP, there are two different cases to handle:
 105    1. A constant is passed as an argument.  In this case the callsite in the
 106       should be redirected to call the cloned callee.
 107    2. A parameter (of the caller) passed as an argument (pass through
 108       argument).  In such cases both the caller and the callee have clones and
 109       only the callsite in the cloned caller is redirected to call to the
 110       cloned callee.
 111
 112    This update is done in two steps: First all cloned functions are created
 113    during a traversal of the call graph, during which all callsites are
 114    redirected to call the cloned function.  Then the callsites are traversed
 115    and many calls redirected back to fit the description above.
 116
 117    -ipcp_insert_stage() is the third phase driver.
 118
 119 */
 120
 121 #include "config.h"
 122 #include "system.h"
 123 #include "coretypes.h"
 124 #include "tree.h"
 125 #include "target.h"
 126 #include "cgraph.h"
 127 #include "ipa-prop.h"
 128 #include "tree-flow.h"
 129 #include "tree-pass.h"
 130 #include "flags.h"
 131 #include "timevar.h"
 132 #include "diagnostic.h"
 133 #include "tree-dump.h"
 134 #include "tree-inline.h"
 135 #include "fibheap.h"
 136 #include "params.h"
 137
 138 /* Number of functions identified as candidates for cloning. When not cloning
 139    we can simplify iterate stage not forcing it to go through the decision
 140    on what is profitable and what not.  */
 141 static int n_cloning_candidates;
 142
 143 /* Maximal count found in program.  */
 144 static gcov_type max_count;
 145
 146 /* Cgraph nodes that has been completely replaced by cloning during iterate
 147  * stage and will be removed after ipcp is finished.  */
 148 static bitmap dead_nodes;
 149
 150 static void ipcp_print_profile_data (FILE *);
 151 static void ipcp_function_scale_print (FILE *);
 152
 153 /* Get the original node field of ipa_node_params associated with node NODE.  */
 154 static inline struct cgraph_node *
 155 ipcp_get_orig_node (struct cgraph_node *node)
 156 {
 157   return IPA_NODE_REF (node)->ipcp_orig_node;
 158 }
 159
 160 /* Return true if NODE describes a cloned/versioned function.  */
 161 static inline bool
 162 ipcp_node_is_clone (struct cgraph_node *node)
 163 {
 164   return (ipcp_get_orig_node (node) != NULL);
 165 }
 166
 167 /* Create ipa_node_params and its data structures for NEW_NODE.  Set ORIG_NODE
 168    as the ipcp_orig_node field in ipa_node_params.  */
 169 static void
 170 ipcp_init_cloned_node (struct cgraph_node *orig_node,
 171                        struct cgraph_node *new_node)
 172 {
 173   ipa_check_create_node_params ();
 174   IPA_NODE_REF (new_node)->ipcp_orig_node = orig_node;
 175   ipa_count_formal_params (new_node);
 176   ipa_create_param_decls_array (new_node);
 177 }
 178
 179 /* Perform intraprocedrual analysis needed for ipcp.  */
 180 static void
 181 ipcp_analyze_node (struct cgraph_node *node)
 182 {
 183   /* Unreachable nodes should have been eliminated before ipcp.  */
 184   gcc_assert (node->needed || node->reachable);
 185
 186   ipa_count_formal_params (node);
 187   ipa_create_param_decls_array (node);
 188   ipa_detect_param_modifications (node);
 189 }
 190
 191 /* Recompute all local information since node might've got new
 192    direct calls after cloning.  */
 193 static void
 194 ipcp_update_cloned_node (struct cgraph_node *new_node)
 195 {
 196   /* We might've introduced new direct calls.  */
 197   push_cfun (DECL_STRUCT_FUNCTION (new_node->decl));
 198   current_function_decl = new_node->decl;
 199   rebuild_cgraph_edges ();
 200
 201   /* Indirect inlinng rely on fact that we've already analyzed
 202      the body..  */
 203   if (flag_indirect_inlining)
 204     {
 205       struct cgraph_edge *cs;
 206
 207       ipcp_analyze_node (new_node);
 208
 209       for (cs = new_node->callees; cs; cs = cs->next_callee)
 210         {
 211           ipa_count_arguments (cs);
 212           ipa_compute_jump_functions (cs);
 213         }
 214     }
 215   pop_cfun ();
 216   current_function_decl = NULL;
 217 }
 218
 219 /* Return scale for NODE.  */
 220 static inline gcov_type
 221 ipcp_get_node_scale (struct cgraph_node *node)
 222 {
 223   return IPA_NODE_REF (node)->count_scale;
 224 }
 225
 226 /* Set COUNT as scale for NODE.  */
 227 static inline void
 228 ipcp_set_node_scale (struct cgraph_node *node, gcov_type count)
 229 {
 230   IPA_NODE_REF (node)->count_scale = count;
 231 }
 232
 233 /* Return whether LAT is a constant lattice.  */
 234 static inline bool
 235 ipcp_lat_is_const (struct ipcp_lattice *lat)
 236 {
 237   if (lat->type == IPA_CONST_VALUE)
 238     return true;
 239   else
 240     return false;
 241 }
 242
 243 /* Return whether LAT is a constant lattice that ipa-cp can actually insert
 244    into the code (i.e. constants excluding member pointers and pointers).  */
 245 static inline bool
 246 ipcp_lat_is_insertable (struct ipcp_lattice *lat)
 247 {
 248   return lat->type == IPA_CONST_VALUE;
 249 }
 250
 251 /* Return true if LAT1 and LAT2 are equal.  */
 252 static inline bool
 253 ipcp_lats_are_equal (struct ipcp_lattice *lat1, struct ipcp_lattice *lat2)
 254 {
 255   gcc_assert (ipcp_lat_is_const (lat1) && ipcp_lat_is_const (lat2));
 256   if (lat1->type != lat2->type)
 257     return false;
 258
 259   if (operand_equal_p (lat1->constant, lat2->constant, 0))
 260     return true;
 261
 262   return false;
 263 }
 264
 265 /* Compute Meet arithmetics:
 266    Meet (IPA_BOTTOM, x) = IPA_BOTTOM
 267    Meet (IPA_TOP,x) = x
 268    Meet (const_a,const_b) = IPA_BOTTOM,  if const_a != const_b.
 269    MEET (const_a,const_b) = const_a, if const_a == const_b.*/
 270 static void
 271 ipa_lattice_meet (struct ipcp_lattice *res, struct ipcp_lattice *lat1,
 272                   struct ipcp_lattice *lat2)
 273 {
 274   if (lat1->type == IPA_BOTTOM || lat2->type == IPA_BOTTOM)
 275     {
 276       res->type = IPA_BOTTOM;
 277       return;
 278     }
 279   if (lat1->type == IPA_TOP)
 280     {
 281       res->type = lat2->type;
 282       res->constant = lat2->constant;
 283       return;
 284     }
 285   if (lat2->type == IPA_TOP)
 286     {
 287       res->type = lat1->type;
 288       res->constant = lat1->constant;
 289       return;
 290     }
 291   if (!ipcp_lats_are_equal (lat1, lat2))
 292     {
 293       res->type = IPA_BOTTOM;
 294       return;
 295     }
 296   res->type = lat1->type;
 297   res->constant = lat1->constant;
 298 }
 299
 300 /* Return the lattice corresponding to the Ith formal parameter of the function
 301    described by INFO.  */
 302 static inline struct ipcp_lattice *
 303 ipcp_get_ith_lattice (struct ipa_node_params *info, int i)
 304 {
 305   return &(info->ipcp_lattices[i]);
 306 }
 307
 308 /* Given the jump function JFUNC, compute the lattice LAT that describes the
 309    value coming down the callsite. INFO describes the caller node so that
 310    pass-through jump functions can be evaluated.  */
 311 static void
 312 ipcp_lattice_from_jfunc (struct ipa_node_params *info, struct ipcp_lattice *lat,
 313                          struct ipa_jump_func *jfunc)
 314 {
 315   if (jfunc->type == IPA_CONST)
 316     {
 317       lat->type = IPA_CONST_VALUE;
 318       lat->constant = jfunc->value.constant;
 319     }
 320   else if (jfunc->type == IPA_PASS_THROUGH)
 321     {
 322       struct ipcp_lattice *caller_lat;
 323
 324       caller_lat = ipcp_get_ith_lattice (info, jfunc->value.formal_id);
 325       lat->type = caller_lat->type;
 326       lat->constant = caller_lat->constant;
 327     }
 328   else
 329     lat->type = IPA_BOTTOM;
 330 }
 331
 332 /* True when OLD_LAT and NEW_LAT values are not the same.  */
 333
 334 static bool
 335 ipcp_lattice_changed (struct ipcp_lattice *old_lat,
 336                       struct ipcp_lattice *new_lat)
 337 {
 338   if (old_lat->type == new_lat->type)
 339     {
 340       if (!ipcp_lat_is_const (old_lat))
 341         return false;
 342       if (ipcp_lats_are_equal (old_lat, new_lat))
 343         return false;
 344     }
 345   return true;
 346 }
 347
 348 /* Print all ipcp_lattices of all functions to F.  */
 349 static void
 350 ipcp_print_all_lattices (FILE * f)
 351 {
 352   struct cgraph_node *node;
 353   int i, count;
 354
 355   fprintf (f, "\nLattice:\n");
 356   for (node = cgraph_nodes; node; node = node->next)
 357     {
 358       struct ipa_node_params *info;
 359
 360       if (!node->analyzed)
 361         continue;
 362       info = IPA_NODE_REF (node);
 363       fprintf (f, "  Node: %s:\n", cgraph_node_name (node));
 364       count = ipa_get_param_count (info);
 365       for (i = 0; i < count; i++)
 366         {
 367           struct ipcp_lattice *lat = ipcp_get_ith_lattice (info, i);
 368
 369           fprintf (f, "    param [%d]: ", i);
 370           if (lat->type == IPA_CONST_VALUE)
 371             {
 372               fprintf (f, "type is CONST ");
 373               print_generic_expr (f, lat->constant, 0);
 374               fprintf (f, "\n");
 375             }
 376           else if (lat->type == IPA_TOP)
 377             fprintf (f, "type is TOP\n");
 378           else
 379             fprintf (f, "type is BOTTOM\n");
 380         }
 381     }
 382 }
 383
 384 /* Return true if this NODE is viable candidate for cloning.  */
 385 static bool
 386 ipcp_cloning_candidate_p (struct cgraph_node *node)
 387 {
 388   int n_calls = 0;
 389   int n_hot_calls = 0;
 390   gcov_type direct_call_sum = 0;
 391   struct cgraph_edge *e;
 392
 393   /* We never clone functions that are not visible from outside.
 394      FIXME: in future we should clone such functions when they are called with
 395      different constants, but current ipcp implementation is not good on this.
 396      */
 397   if (!node->needed || !node->analyzed)
 398     return false;
 399
 400   if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
 401     {
 402       if (dump_file)
 403         fprintf (dump_file, "Not considering %s for cloning; body is overwrittable.\n",
 404                  cgraph_node_name (node));
 405       return false;
 406     }
 407   if (!tree_versionable_function_p (node->decl))
 408     {
 409       if (dump_file)
 410         fprintf (dump_file, "Not considering %s for cloning; body is not versionable.\n",
 411                  cgraph_node_name (node));
 412       return false;
 413     }
 414   for (e = node->callers; e; e = e->next_caller)
 415     {
 416       direct_call_sum += e->count;
 417       n_calls ++;
 418       if (cgraph_maybe_hot_edge_p (e))
 419         n_hot_calls ++;
 420     }
 421
 422   if (!n_calls)
 423     {
 424       if (dump_file)
 425         fprintf (dump_file, "Not considering %s for cloning; no direct calls.\n",
 426                  cgraph_node_name (node));
 427       return false;
 428     }
 429   if (node->local.inline_summary.self_insns < n_calls)
 430     {
 431       if (dump_file)
 432         fprintf (dump_file, "Considering %s for cloning; code would shrink.\n",
 433                  cgraph_node_name (node));
 434       return true;
 435     }
 436
 437   if (!flag_ipa_cp_clone)
 438     {
 439       if (dump_file)
 440         fprintf (dump_file, "Not considering %s for cloning; -fipa-cp-clone disabled.\n",
 441                  cgraph_node_name (node));
 442       return false;
 443     }
 444
 445   if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
 446     {
 447       if (dump_file)
 448         fprintf (dump_file, "Not considering %s for cloning; optimizing it for size.\n",
 449                  cgraph_node_name (node));
 450       return false;
 451     }
 452
 453   /* When profile is available and function is hot, propagate into it even if
 454      calls seems cold; constant propagation can improve function's speed
 455      significandly.  */
 456   if (max_count)
 457     {
 458       if (direct_call_sum > node->count * 90 / 100)
 459         {
 460           if (dump_file)
 461             fprintf (dump_file, "Considering %s for cloning; usually called directly.\n",
 462                      cgraph_node_name (node));
 463           return true;
 464         }
 465     }
 466   if (!n_hot_calls)
 467     {
 468       if (dump_file)
 469         fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
 470                  cgraph_node_name (node));
 471     }
 472   if (dump_file)
 473     fprintf (dump_file, "Considering %s for cloning.\n",
 474              cgraph_node_name (node));
 475   return true;
 476 }
 477
 478 /* Initialize ipcp_lattices array.  The lattices corresponding to supported
 479    types (integers, real types and Fortran constants defined as const_decls)
 480    are initialized to IPA_TOP, the rest of them to IPA_BOTTOM.  */
 481 static void
 482 ipcp_initialize_node_lattices (struct cgraph_node *node)
 483 {
 484   int i;
 485   struct ipa_node_params *info = IPA_NODE_REF (node);
 486   enum ipa_lattice_type type;
 487
 488   info->ipcp_lattices = XCNEWVEC (struct ipcp_lattice,
 489                                   ipa_get_param_count (info));
 490
 491   if (ipa_is_called_with_var_arguments (info))
 492     type = IPA_BOTTOM;
 493   else if (!node->needed)
 494     type = IPA_TOP;
 495   /* When cloning is allowed, we can assume that externally visible functions
 496      are not called.  We will compensate this by cloning later.  */
 497   else if (ipcp_cloning_candidate_p (node))
 498     type = IPA_TOP, n_cloning_candidates ++;
 499   else
 500     type = IPA_BOTTOM;
 501
 502   for (i = 0; i < ipa_get_param_count (info) ; i++)
 503     ipcp_get_ith_lattice (info, i)->type = type;
 504 }
 505
 506 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
 507    Return the tree.  */
 508 static tree
 509 build_const_val (struct ipcp_lattice *lat, tree tree_type)
 510 {
 511   tree val;
 512
 513   gcc_assert (ipcp_lat_is_const (lat));
 514   val = lat->constant;
 515
 516   if (!useless_type_conversion_p (tree_type, TREE_TYPE (val)))
 517     {
 518       if (fold_convertible_p (tree_type, val))
 519         return fold_build1 (NOP_EXPR, tree_type, val);
 520       else
 521         return fold_build1 (VIEW_CONVERT_EXPR, tree_type, val);
 522     }
 523   return val;
 524 }
 525
 526 /* Compute the proper scale for NODE.  It is the ratio between the number of
 527    direct calls (represented on the incoming cgraph_edges) and sum of all
 528    invocations of NODE (represented as count in cgraph_node).  */
 529 static void
 530 ipcp_compute_node_scale (struct cgraph_node *node)
 531 {
 532   gcov_type sum;
 533   struct cgraph_edge *cs;
 534
 535   sum = 0;
 536   /* Compute sum of all counts of callers. */
 537   for (cs = node->callers; cs != NULL; cs = cs->next_caller)
 538     sum += cs->count;
 539   if (node->count == 0)
 540     ipcp_set_node_scale (node, 0);
 541   else
 542     ipcp_set_node_scale (node, sum * REG_BR_PROB_BASE / node->count);
 543 }
 544
 545 /* Initialization and computation of IPCP data structures.  This is the initial
 546    intraprocedural analysis of functions, which gathers information to be
 547    propagated later on.  */
 548 static void
 549 ipcp_init_stage (void)
 550 {
 551   struct cgraph_node *node;
 552   struct cgraph_edge *cs;
 553
 554   for (node = cgraph_nodes; node; node = node->next)
 555     if (node->analyzed)
 556       ipcp_analyze_node (node);
 557   for (node = cgraph_nodes; node; node = node->next)
 558     {
 559       if (!node->analyzed)
 560         continue;
 561       /* building jump functions  */
 562       for (cs = node->callees; cs; cs = cs->next_callee)
 563         {
 564           if (!cs->callee->analyzed)
 565             continue;
 566           ipa_count_arguments (cs);
 567           if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
 568               != ipa_get_param_count (IPA_NODE_REF (cs->callee)))
 569             {
 570               /* Handle cases of functions with
 571                  a variable number of parameters.  */
 572               ipa_set_called_with_variable_arg (IPA_NODE_REF (cs->callee));
 573               if (flag_indirect_inlining)
 574                 ipa_compute_jump_functions (cs);
 575             }
 576           else
 577             ipa_compute_jump_functions (cs);
 578         }
 579     }
 580 }
 581
 582 /* Return true if there are some formal parameters whose value is IPA_TOP (in
 583    the whole compilation unit).  Change their values to IPA_BOTTOM, since they
 584    most probably get their values from outside of this compilation unit.  */
 585 static bool
 586 ipcp_change_tops_to_bottom (void)
 587 {
 588   int i, count;
 589   struct cgraph_node *node;
 590   bool prop_again;
 591
 592   prop_again = false;
 593   for (node = cgraph_nodes; node; node = node->next)
 594     {
 595       struct ipa_node_params *info = IPA_NODE_REF (node);
 596       count = ipa_get_param_count (info);
 597       for (i = 0; i < count; i++)
 598         {
 599           struct ipcp_lattice *lat = ipcp_get_ith_lattice (info, i);
 600           if (lat->type == IPA_TOP)
 601             {
 602               prop_again = true;
 603               if (dump_file)
 604                 {
 605                   fprintf (dump_file, "Forcing param ");
 606                   print_generic_expr (dump_file, ipa_get_ith_param (info, i), 0);
 607                   fprintf (dump_file, " of node %s to bottom.\n",
 608                            cgraph_node_name (node));
 609                 }
 610               lat->type = IPA_BOTTOM;
 611             }
 612         }
 613     }
 614   return prop_again;
 615 }
 616
 617 /* Interprocedural analysis. The algorithm propagates constants from the
 618    caller's parameters to the callee's arguments.  */
 619 static void
 620 ipcp_propagate_stage (void)
 621 {
 622   int i;
 623   struct ipcp_lattice inc_lat = { IPA_BOTTOM, NULL };
 624   struct ipcp_lattice new_lat = { IPA_BOTTOM, NULL };
 625   struct ipcp_lattice *dest_lat;
 626   struct cgraph_edge *cs;
 627   struct ipa_jump_func *jump_func;
 628   struct ipa_func_list *wl;
 629   int count;
 630
 631   ipa_check_create_node_params ();
 632   ipa_check_create_edge_args ();
 633
 634   /* Initialize worklist to contain all functions.  */
 635   wl = ipa_init_func_list ();
 636   while (wl)
 637     {
 638       struct cgraph_node *node = ipa_pop_func_from_list (&wl);
 639       struct ipa_node_params *info = IPA_NODE_REF (node);
 640
 641       for (cs = node->callees; cs; cs = cs->next_callee)
 642         {
 643           struct ipa_node_params *callee_info = IPA_NODE_REF (cs->callee);
 644           struct ipa_edge_args *args = IPA_EDGE_REF (cs);
 645
 646           if (ipa_is_called_with_var_arguments (callee_info))
 647             continue;
 648
 649           count = ipa_get_cs_argument_count (args);
 650           for (i = 0; i < count; i++)
 651             {
 652               jump_func = ipa_get_ith_jump_func (args, i);
 653               ipcp_lattice_from_jfunc (info, &inc_lat, jump_func);
 654               dest_lat = ipcp_get_ith_lattice (callee_info, i);
 655               ipa_lattice_meet (&new_lat, &inc_lat, dest_lat);
 656               if (ipcp_lattice_changed (&new_lat, dest_lat))
 657                 {
 658                   dest_lat->type = new_lat.type;
 659                   dest_lat->constant = new_lat.constant;
 660                   ipa_push_func_to_list (&wl, cs->callee);
 661                 }
 662             }
 663         }
 664     }
 665 }
 666
 667 /* Call the constant propagation algorithm and re-call it if necessary
 668    (if there are undetermined values left).  */
 669 static void
 670 ipcp_iterate_stage (void)
 671 {
 672   struct cgraph_node *node;
 673   n_cloning_candidates = 0;
 674
 675   if (dump_file)
 676     fprintf (dump_file, "\nIPA iterate stage:\n\n");
 677   for (node = cgraph_nodes; node; node = node->next)
 678     {
 679       ipcp_initialize_node_lattices (node);
 680       ipcp_compute_node_scale (node);
 681     }
 682   if (dump_file && (dump_flags & TDF_DETAILS))
 683     {
 684       ipcp_print_all_lattices (dump_file);
 685       ipcp_function_scale_print (dump_file);
 686     }
 687
 688   ipcp_propagate_stage ();
 689   if (ipcp_change_tops_to_bottom ())
 690     /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
 691        This change should be propagated.  */
 692     {
 693       gcc_assert (n_cloning_candidates);
 694       ipcp_propagate_stage ();
 695     }
 696   if (dump_file)
 697     {
 698       fprintf (dump_file, "\nIPA lattices after propagation:\n");
 699       ipcp_print_all_lattices (dump_file);
 700       if (dump_flags & TDF_DETAILS)
 701         ipcp_print_profile_data (dump_file);
 702     }
 703 }
 704
 705 /* Check conditions to forbid constant insertion to function described by
 706    NODE.  */
 707 static inline bool
 708 ipcp_node_modifiable_p (struct cgraph_node *node)
 709 {
 710   /* Once we will be able to do in-place replacement, we can be more
 711      lax here.  */
 712   return tree_versionable_function_p (node->decl);
 713 }
 714
 715 /* Print count scale data structures.  */
 716 static void
 717 ipcp_function_scale_print (FILE * f)
 718 {
 719   struct cgraph_node *node;
 720
 721   for (node = cgraph_nodes; node; node = node->next)
 722     {
 723       if (!node->analyzed)
 724         continue;
 725       fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
 726       fprintf (f, "value is  " HOST_WIDE_INT_PRINT_DEC
 727                "  \n", (HOST_WIDE_INT) ipcp_get_node_scale (node));
 728     }
 729 }
 730
 731 /* Print counts of all cgraph nodes.  */
 732 static void
 733 ipcp_print_func_profile_counts (FILE * f)
 734 {
 735   struct cgraph_node *node;
 736
 737   for (node = cgraph_nodes; node; node = node->next)
 738     {
 739       fprintf (f, "function %s: ", cgraph_node_name (node));
 740       fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC
 741                "  \n", (HOST_WIDE_INT) node->count);
 742     }
 743 }
 744
 745 /* Print counts of all cgraph edges.  */
 746 static void
 747 ipcp_print_call_profile_counts (FILE * f)
 748 {
 749   struct cgraph_node *node;
 750   struct cgraph_edge *cs;
 751
 752   for (node = cgraph_nodes; node; node = node->next)
 753     {
 754       for (cs = node->callees; cs; cs = cs->next_callee)
 755         {
 756           fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
 757                    cgraph_node_name (cs->callee));
 758           fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC "  \n",
 759                    (HOST_WIDE_INT) cs->count);
 760         }
 761     }
 762 }
 763
 764 /* Print all counts and probabilities of cfg edges of all functions.  */
 765 static void
 766 ipcp_print_edge_profiles (FILE * f)
 767 {
 768   struct cgraph_node *node;
 769   basic_block bb;
 770   edge_iterator ei;
 771   edge e;
 772
 773   for (node = cgraph_nodes; node; node = node->next)
 774     {
 775       fprintf (f, "function %s: \n", cgraph_node_name (node));
 776       if (node->analyzed)
 777         {
 778           bb =
 779             ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 780           fprintf (f, "ENTRY: ");
 781           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 782                    " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
 783
 784           if (bb->succs)
 785             FOR_EACH_EDGE (e, ei, bb->succs)
 786             {
 787               if (e->dest ==
 788                   EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
 789                                                (node->decl)))
 790                 fprintf (f, "edge ENTRY -> EXIT,  Count");
 791               else
 792                 fprintf (f, "edge ENTRY -> %d,  Count", e->dest->index);
 793               fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 794                        " Prob %d\n", (HOST_WIDE_INT) e->count,
 795                        e->probability);
 796             }
 797           FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 798           {
 799             fprintf (f, "bb[%d]: ", bb->index);
 800             fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 801                      " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
 802             FOR_EACH_EDGE (e, ei, bb->succs)
 803             {
 804               if (e->dest ==
 805                   EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
 806                                                (node->decl)))
 807                 fprintf (f, "edge %d -> EXIT,  Count", e->src->index);
 808               else
 809                 fprintf (f, "edge %d -> %d,  Count", e->src->index,
 810                          e->dest->index);
 811               fprintf (f, " " HOST_WIDE_INT_PRINT_DEC " Prob %d\n",
 812                        (HOST_WIDE_INT) e->count, e->probability);
 813             }
 814           }
 815         }
 816     }
 817 }
 818
 819 /* Print counts and frequencies for all basic blocks of all functions.  */
 820 static void
 821 ipcp_print_bb_profiles (FILE * f)
 822 {
 823   basic_block bb;
 824   struct cgraph_node *node;
 825
 826   for (node = cgraph_nodes; node; node = node->next)
 827     {
 828       fprintf (f, "function %s: \n", cgraph_node_name (node));
 829       if (node->analyzed)
 830         {
 831           bb =
 832             ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 833           fprintf (f, "ENTRY: Count");
 834           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 835                    " Frequency  %d\n", (HOST_WIDE_INT) bb->count,
 836                    bb->frequency);
 837
 838           FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 839           {
 840             fprintf (f, "bb[%d]: Count", bb->index);
 841             fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 842                      " Frequency %d\n", (HOST_WIDE_INT) bb->count,
 843                      bb->frequency);
 844           }
 845           bb =
 846             EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 847           fprintf (f, "EXIT: Count");
 848           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 849                    " Frequency %d\n", (HOST_WIDE_INT) bb->count,
 850                    bb->frequency);
 851
 852         }
 853     }
 854 }
 855
 856 /* Print profile info for all functions.  */
 857 static void
 858 ipcp_print_profile_data (FILE * f)
 859 {
 860   fprintf (f, "\nNODE COUNTS :\n");
 861   ipcp_print_func_profile_counts (f);
 862   fprintf (f, "\nCS COUNTS stage:\n");
 863   ipcp_print_call_profile_counts (f);
 864   fprintf (f, "\nBB COUNTS and FREQUENCIES :\n");
 865   ipcp_print_bb_profiles (f);
 866   fprintf (f, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
 867   ipcp_print_edge_profiles (f);
 868 }
 869
 870 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
 871    processed by versioning, which operates according to the flags set.
 872    PARM_TREE is the formal parameter found to be constant.  LAT represents the
 873    constant.  */
 874 static struct ipa_replace_map *
 875 ipcp_create_replace_map (tree parm_tree, struct ipcp_lattice *lat)
 876 {
 877   struct ipa_replace_map *replace_map;
 878   tree const_val;
 879
 880   replace_map = XCNEW (struct ipa_replace_map);
 881   const_val = build_const_val (lat, TREE_TYPE (parm_tree));
 882   if (dump_file)
 883     {
 884       fprintf (dump_file, "  replacing param ");
 885       print_generic_expr (dump_file, parm_tree, 0);
 886       fprintf (dump_file, " with const ");
 887       print_generic_expr (dump_file, const_val, 0);
 888       fprintf (dump_file, "\n");
 889     }
 890   replace_map->old_tree = parm_tree;
 891   replace_map->new_tree = const_val;
 892   replace_map->replace_p = true;
 893   replace_map->ref_p = false;
 894
 895   return replace_map;
 896 }
 897
 898 /* Return true if this callsite should be redirected to the original callee
 899    (instead of the cloned one).  */
 900 static bool
 901 ipcp_need_redirect_p (struct cgraph_edge *cs)
 902 {
 903   struct ipa_node_params *orig_callee_info;
 904   int i, count;
 905   struct ipa_jump_func *jump_func;
 906   struct cgraph_node *node = cs->callee, *orig;
 907
 908   if (!n_cloning_candidates)
 909     return false;
 910
 911   if ((orig = ipcp_get_orig_node (node)) != NULL)
 912     node = orig;
 913   if (ipcp_get_orig_node (cs->caller))
 914     return false;
 915
 916   orig_callee_info = IPA_NODE_REF (node);
 917   count = ipa_get_param_count (orig_callee_info);
 918   for (i = 0; i < count; i++)
 919     {
 920       struct ipcp_lattice *lat = ipcp_get_ith_lattice (orig_callee_info, i);
 921       if (ipcp_lat_is_const (lat))
 922         {
 923           jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
 924           if (jump_func->type != IPA_CONST)
 925             return true;
 926         }
 927     }
 928
 929   return false;
 930 }
 931
 932 /* Fix the callsites and the call graph after function cloning was done.  */
 933 static void
 934 ipcp_update_callgraph (void)
 935 {
 936   struct cgraph_node *node;
 937
 938   for (node = cgraph_nodes; node; node = node->next)
 939     if (node->analyzed && ipcp_node_is_clone (node))
 940       {
 941         bitmap args_to_skip = BITMAP_ALLOC (NULL);
 942         struct cgraph_node *orig_node = ipcp_get_orig_node (node);
 943         struct ipa_node_params *info = IPA_NODE_REF (orig_node);
 944         int i, count = ipa_get_param_count (info);
 945         struct cgraph_edge *cs, *next;
 946
 947         for (i = 0; i < count; i++)
 948           {
 949             struct ipcp_lattice *lat = ipcp_get_ith_lattice (info, i);
 950             tree parm_tree = ipa_get_ith_param (info, i);
 951
 952             /* We can proactively remove obviously unused arguments.  */
 953             if (is_gimple_reg (parm_tree)
 954                 && !gimple_default_def (DECL_STRUCT_FUNCTION (orig_node->decl),
 955                                         parm_tree))
 956               {
 957                 bitmap_set_bit (args_to_skip, i);
 958                 continue;
 959               }
 960
 961             if (lat->type == IPA_CONST_VALUE)
 962               bitmap_set_bit (args_to_skip, i);
 963           }
 964         for (cs = node->callers; cs; cs = next)
 965           {
 966             next = cs->next_caller;
 967             if (ipcp_node_is_clone (cs->caller) || !ipcp_need_redirect_p (cs))
 968               {
 969                 gimple new_stmt;
 970                 gimple_stmt_iterator gsi;
 971
 972                 current_function_decl = cs->caller->decl;
 973                 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
 974
 975                 new_stmt = giple_copy_call_skip_args (cs->call_stmt, args_to_skip);
 976                 gsi = gsi_for_stmt (cs->call_stmt);
 977                 gsi_replace (&gsi, new_stmt, true);
 978                 cgraph_set_call_stmt (cs, new_stmt);
 979                 pop_cfun ();
 980                 current_function_decl = NULL;
 981               }
 982             else
 983               {
 984                 cgraph_redirect_edge_callee (cs, orig_node);
 985                 gimple_call_set_fndecl (cs->call_stmt, orig_node->decl);
 986               }
 987           }
 988       }
 989 }
 990
 991 /* Update all cfg basic blocks in NODE according to SCALE.  */
 992 static void
 993 ipcp_update_bb_counts (struct cgraph_node *node, gcov_type scale)
 994 {
 995   basic_block bb;
 996
 997   FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 998     bb->count = bb->count * scale / REG_BR_PROB_BASE;
 999 }
1000
1001 /* Update all cfg edges in NODE according to SCALE.  */
1002 static void
1003 ipcp_update_edges_counts (struct cgraph_node *node, gcov_type scale)
1004 {
1005   basic_block bb;
1006   edge_iterator ei;
1007   edge e;
1008
1009   FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
1010     FOR_EACH_EDGE (e, ei, bb->succs)
1011     e->count = e->count * scale / REG_BR_PROB_BASE;
1012 }
1013
1014 /* Update profiling info for versioned functions and the functions they were
1015    versioned from.  */
1016 static void
1017 ipcp_update_profiling (void)
1018 {
1019   struct cgraph_node *node, *orig_node;
1020   gcov_type scale, scale_complement;
1021   struct cgraph_edge *cs;
1022
1023   for (node = cgraph_nodes; node; node = node->next)
1024     {
1025       if (ipcp_node_is_clone (node))
1026         {
1027           orig_node = ipcp_get_orig_node (node);
1028           scale = ipcp_get_node_scale (orig_node);
1029           node->count = orig_node->count * scale / REG_BR_PROB_BASE;
1030           scale_complement = REG_BR_PROB_BASE - scale;
1031           orig_node->count =
1032             orig_node->count * scale_complement / REG_BR_PROB_BASE;
1033           for (cs = node->callees; cs; cs = cs->next_callee)
1034             cs->count = cs->count * scale / REG_BR_PROB_BASE;
1035           for (cs = orig_node->callees; cs; cs = cs->next_callee)
1036             cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
1037           ipcp_update_bb_counts (node, scale);
1038           ipcp_update_bb_counts (orig_node, scale_complement);
1039           ipcp_update_edges_counts (node, scale);
1040           ipcp_update_edges_counts (orig_node, scale_complement);
1041         }
1042     }
1043 }
1044
1045 /* If NODE was cloned, how much would program grow? */
1046 static long
1047 ipcp_estimate_growth (struct cgraph_node *node)
1048 {
1049   struct cgraph_edge *cs;
1050   int redirectable_node_callers = 0;
1051   int removable_args = 0;
1052   bool need_original = node->needed;
1053   struct ipa_node_params *info;
1054   int i, count;
1055   int growth;
1056
1057   for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1058     if (!ipcp_need_redirect_p (cs))
1059       redirectable_node_callers++;
1060     else
1061       need_original = true;
1062
1063   /* If we will be able to fully replace orignal node, we never increase
1064      program size.  */
1065   if (!need_original)
1066     return false;
1067
1068   info = IPA_NODE_REF (node);
1069   count = ipa_get_param_count (info);
1070   for (i = 0; i < count; i++)
1071     {
1072       struct ipcp_lattice *lat = ipcp_get_ith_lattice (info, i);
1073       tree parm_tree = ipa_get_ith_param (info, i);
1074
1075       /* We can proactively remove obviously unused arguments.  */
1076       if (is_gimple_reg (parm_tree)
1077           && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1078                                   parm_tree))
1079         removable_args++;
1080
1081       if (lat->type == IPA_CONST_VALUE)
1082         removable_args++;
1083     }
1084
1085   /* We make just very simple estimate of savings for removal of operand from
1086      call site.  Precise cost is dificult to get, as our size metric counts
1087      constants and moves as free.  Generally we are looking for cases that
1088      small function is called very many times.  */
1089   growth = node->local.inline_summary.self_insns
1090            - removable_args * redirectable_node_callers;
1091   if (growth < 0)
1092     return 0;
1093   return growth;
1094 }
1095
1096
1097 /* Estimate cost of cloning NODE.  */
1098 static long
1099 ipcp_estimate_cloning_cost (struct cgraph_node *node)
1100 {
1101   int freq_sum = 1;
1102   gcov_type count_sum = 1;
1103   struct cgraph_edge *e;
1104   int cost;
1105
1106   cost = ipcp_estimate_growth (node) * 1000;
1107   if (!cost)
1108     {
1109       if (dump_file)
1110         fprintf (dump_file, "Versioning of %s will save code size\n",
1111                  cgraph_node_name (node));
1112       return 0;
1113     }
1114
1115   for (e = node->callers; e; e = e->next_caller)
1116     if (!bitmap_bit_p (dead_nodes, e->caller->uid)
1117         && !ipcp_need_redirect_p (e))
1118       {
1119         count_sum += e->count;
1120         freq_sum += e->frequency + 1;
1121       }
1122
1123   if (max_count)
1124     cost /= count_sum * 1000 / max_count + 1;
1125   else
1126     cost /= freq_sum * 1000 / REG_BR_PROB_BASE + 1;
1127   if (dump_file)
1128     fprintf (dump_file, "Cost of versioning %s is %i, (size: %i, freq: %i)\n",
1129              cgraph_node_name (node), cost, node->local.inline_summary.self_insns,
1130              freq_sum);
1131   return cost + 1;
1132 }
1133
1134 /* Return number of live constant parameters.  */
1135 static int
1136 ipcp_const_param_count (struct cgraph_node *node)
1137 {
1138   int const_param = 0;
1139   struct ipa_node_params *info = IPA_NODE_REF (node);
1140   int count = ipa_get_param_count (info);
1141   int i;
1142
1143   for (i = 0; i < count; i++)
1144     {
1145       struct ipcp_lattice *lat = ipcp_get_ith_lattice (info, i);
1146       tree parm_tree = ipa_get_ith_param (info, i);
1147       if (ipcp_lat_is_insertable (lat)
1148           /* Do not count obviously unused arguments.  */
1149           && (!is_gimple_reg (parm_tree)
1150               || gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1151                                      parm_tree)))
1152         const_param++;
1153     }
1154   return const_param;
1155 }
1156
1157 /* Propagate the constant parameters found by ipcp_iterate_stage()
1158    to the function's code.  */
1159 static void
1160 ipcp_insert_stage (void)
1161 {
1162   struct cgraph_node *node, *node1 = NULL;
1163   int i;
1164   VEC (cgraph_edge_p, heap) * redirect_callers;
1165   varray_type replace_trees;
1166   struct cgraph_edge *cs;
1167   int node_callers, count;
1168   tree parm_tree;
1169   struct ipa_replace_map *replace_param;
1170   fibheap_t heap;
1171   long overall_insns = 0, new_insns = 0;
1172   long max_new_insns;
1173
1174   ipa_check_create_node_params ();
1175   ipa_check_create_edge_args ();
1176   if (dump_file)
1177     fprintf (dump_file, "\nIPA insert stage:\n\n");
1178
1179   dead_nodes = BITMAP_ALLOC (NULL);
1180
1181   for (node = cgraph_nodes; node; node = node->next)
1182     if (node->analyzed)
1183       {
1184         if (node->count > max_count)
1185           max_count = node->count;
1186         overall_insns += node->local.inline_summary.self_insns;
1187       }
1188
1189   max_new_insns = overall_insns;
1190   if (max_new_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1191     max_new_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1192   max_new_insns = max_new_insns * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
1193
1194   /* First collect all functions we proved to have constant arguments to heap.  */
1195   heap = fibheap_new ();
1196   for (node = cgraph_nodes; node; node = node->next)
1197     {
1198       struct ipa_node_params *info;
1199       /* Propagation of the constant is forbidden in certain conditions.  */
1200       if (!node->analyzed || !ipcp_node_modifiable_p (node))
1201           continue;
1202       info = IPA_NODE_REF (node);
1203       if (ipa_is_called_with_var_arguments (info))
1204         continue;
1205       if (ipcp_const_param_count (node))
1206         node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node), node);
1207      }
1208
1209   /* Now clone in priority order until code size growth limits are met or
1210      heap is emptied.  */
1211   while (!fibheap_empty (heap))
1212     {
1213       struct ipa_node_params *info;
1214       int growth = 0;
1215       bitmap args_to_skip;
1216
1217       node = (struct cgraph_node *)fibheap_extract_min (heap);
1218       node->aux = NULL;
1219       if (dump_file)
1220         fprintf (dump_file, "considering function %s\n",
1221                  cgraph_node_name (node));
1222
1223       growth = ipcp_estimate_growth (node);
1224
1225       if (new_insns + growth > max_new_insns)
1226         break;
1227       if (growth
1228           && optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl)))
1229         {
1230           if (dump_file)
1231             fprintf (dump_file, "Not versioning, cold code would grow");
1232           continue;
1233         }
1234
1235       new_insns += growth;
1236
1237       info = IPA_NODE_REF (node);
1238       count = ipa_get_param_count (info);
1239
1240       VARRAY_GENERIC_PTR_INIT (replace_trees, ipcp_const_param_count (node),
1241                                 "replace_trees");
1242       args_to_skip = BITMAP_ALLOC (NULL);
1243       for (i = 0; i < count; i++)
1244         {
1245           struct ipcp_lattice *lat = ipcp_get_ith_lattice (info, i);
1246           parm_tree = ipa_get_ith_param (info, i);
1247
1248           /* We can proactively remove obviously unused arguments.  */
1249           if (is_gimple_reg (parm_tree)
1250               && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1251                                       parm_tree))
1252             {
1253               bitmap_set_bit (args_to_skip, i);
1254               continue;
1255             }
1256
1257           if (lat->type == IPA_CONST_VALUE)
1258             {
1259               replace_param =
1260                 ipcp_create_replace_map (parm_tree, lat);
1261               VARRAY_PUSH_GENERIC_PTR (replace_trees, replace_param);
1262               bitmap_set_bit (args_to_skip, i);
1263             }
1264         }
1265
1266       /* Compute how many callers node has.  */
1267       node_callers = 0;
1268       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1269         node_callers++;
1270       redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers);
1271       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1272         VEC_quick_push (cgraph_edge_p, redirect_callers, cs);
1273
1274       /* Redirecting all the callers of the node to the
1275          new versioned node.  */
1276       node1 =
1277         cgraph_function_versioning (node, redirect_callers, replace_trees,
1278                                     args_to_skip);
1279       BITMAP_FREE (args_to_skip);
1280       VEC_free (cgraph_edge_p, heap, redirect_callers);
1281       VARRAY_CLEAR (replace_trees);
1282       if (node1 == NULL)
1283         continue;
1284       if (dump_file)
1285         fprintf (dump_file, "versioned function %s with growth %i, overall %i\n",
1286                  cgraph_node_name (node), (int)growth, (int)new_insns);
1287       ipcp_init_cloned_node (node, node1);
1288
1289       /* We've possibly introduced direct calls.  */
1290       ipcp_update_cloned_node (node1);
1291
1292       if (dump_file)
1293         dump_function_to_file (node1->decl, dump_file, dump_flags);
1294
1295       for (cs = node->callees; cs; cs = cs->next_callee)
1296         if (cs->callee->aux)
1297           {
1298             fibheap_delete_node (heap, (fibnode_t) cs->callee->aux);
1299             cs->callee->aux = fibheap_insert (heap,
1300                                               ipcp_estimate_cloning_cost (cs->callee),
1301                                               cs->callee);
1302           }
1303     }
1304
1305   while (!fibheap_empty (heap))
1306     {
1307       if (dump_file)
1308         fprintf (dump_file, "skipping function %s\n",
1309                  cgraph_node_name (node));
1310       node = (struct cgraph_node *) fibheap_extract_min (heap);
1311       node->aux = NULL;
1312     }
1313   fibheap_delete (heap);
1314   BITMAP_FREE (dead_nodes);
1315   ipcp_update_callgraph ();
1316   ipcp_update_profiling ();
1317 }
1318
1319 /* The IPCP driver.  */
1320 static unsigned int
1321 ipcp_driver (void)
1322 {
1323   cgraph_remove_unreachable_nodes (true,dump_file);
1324   if (dump_file)
1325     {
1326       fprintf (dump_file, "\nIPA structures before propagation:\n");
1327       if (dump_flags & TDF_DETAILS)
1328         ipa_print_all_params (dump_file);
1329       ipa_print_all_jump_functions (dump_file);
1330     }
1331   /* 2. Do the interprocedural propagation.  */
1332   ipcp_iterate_stage ();
1333   /* 3. Insert the constants found to the functions.  */
1334   ipcp_insert_stage ();
1335   if (dump_file && (dump_flags & TDF_DETAILS))
1336     {
1337       fprintf (dump_file, "\nProfiling info after insert stage:\n");
1338       ipcp_print_profile_data (dump_file);
1339     }
1340   /* Free all IPCP structures.  */
1341   free_all_ipa_structures_after_ipa_cp ();
1342   if (dump_file)
1343     fprintf (dump_file, "\nIPA constant propagation end\n");
1344   return 0;
1345 }
1346
1347 /* Note function body size.  */
1348 static void
1349 ipcp_generate_summary (void)
1350 {
1351   if (dump_file)
1352     fprintf (dump_file, "\nIPA constant propagation start:\n");
1353   ipa_check_create_node_params ();
1354   ipa_check_create_edge_args ();
1355   ipa_register_cgraph_hooks ();
1356   /* 1. Call the init stage to initialize
1357      the ipa_node_params and ipa_edge_args structures.  */
1358   ipcp_init_stage ();
1359 }
1360
1361 /* Gate for IPCP optimization.  */
1362 static bool
1363 cgraph_gate_cp (void)
1364 {
1365   return flag_ipa_cp;
1366 }
1367
1368 struct ipa_opt_pass pass_ipa_cp =
1369 {
1370  {
1371   IPA_PASS,
1372   "cp",                         /* name */
1373   cgraph_gate_cp,               /* gate */
1374   ipcp_driver,                  /* execute */
1375   NULL,                         /* sub */
1376   NULL,                         /* next */
1377   0,                            /* static_pass_number */
1378   TV_IPA_CONSTANT_PROP,         /* tv_id */
1379   0,                            /* properties_required */
1380   PROP_trees,                   /* properties_provided */
1381   0,                            /* properties_destroyed */
1382   0,                            /* todo_flags_start */
1383   TODO_dump_cgraph | TODO_dump_func |
1384   TODO_remove_functions /* todo_flags_finish */
1385  },
1386  ipcp_generate_summary,                 /* generate_summary */
1387  NULL,                                  /* write_summary */
1388  NULL,                                  /* read_summary */
1389  NULL,                                  /* function_read_summary */
1390  0,                                     /* TODOs */
1391  NULL,                                  /* function_transform */
1392  NULL,                                  /* variable_transform */
1393 };