gcc/ipa-cp.c

   1 /* Interprocedural constant propagation
   2    Copyright (C) 2005, 2006, 2007, 2008, 2009 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_initialize_node_params (new_node);
 175   IPA_NODE_REF (new_node)->ipcp_orig_node = orig_node;
 176 }
 177
 178 /* Perform intraprocedrual analysis needed for ipcp.  */
 179 static void
 180 ipcp_analyze_node (struct cgraph_node *node)
 181 {
 182   /* Unreachable nodes should have been eliminated before ipcp.  */
 183   gcc_assert (node->needed || node->reachable);
 184
 185   ipa_initialize_node_params (node);
 186   ipa_detect_param_modifications (node);
 187 }
 188
 189 /* Return scale for NODE.  */
 190 static inline gcov_type
 191 ipcp_get_node_scale (struct cgraph_node *node)
 192 {
 193   return IPA_NODE_REF (node)->count_scale;
 194 }
 195
 196 /* Set COUNT as scale for NODE.  */
 197 static inline void
 198 ipcp_set_node_scale (struct cgraph_node *node, gcov_type count)
 199 {
 200   IPA_NODE_REF (node)->count_scale = count;
 201 }
 202
 203 /* Return whether LAT is a constant lattice.  */
 204 static inline bool
 205 ipcp_lat_is_const (struct ipcp_lattice *lat)
 206 {
 207   if (lat->type == IPA_CONST_VALUE)
 208     return true;
 209   else
 210     return false;
 211 }
 212
 213 /* Return whether LAT is a constant lattice that ipa-cp can actually insert
 214    into the code (i.e. constants excluding member pointers and pointers).  */
 215 static inline bool
 216 ipcp_lat_is_insertable (struct ipcp_lattice *lat)
 217 {
 218   return lat->type == IPA_CONST_VALUE;
 219 }
 220
 221 /* Return true if LAT1 and LAT2 are equal.  */
 222 static inline bool
 223 ipcp_lats_are_equal (struct ipcp_lattice *lat1, struct ipcp_lattice *lat2)
 224 {
 225   gcc_assert (ipcp_lat_is_const (lat1) && ipcp_lat_is_const (lat2));
 226   if (lat1->type != lat2->type)
 227     return false;
 228
 229   if (operand_equal_p (lat1->constant, lat2->constant, 0))
 230     return true;
 231
 232   return false;
 233 }
 234
 235 /* Compute Meet arithmetics:
 236    Meet (IPA_BOTTOM, x) = IPA_BOTTOM
 237    Meet (IPA_TOP,x) = x
 238    Meet (const_a,const_b) = IPA_BOTTOM,  if const_a != const_b.
 239    MEET (const_a,const_b) = const_a, if const_a == const_b.*/
 240 static void
 241 ipa_lattice_meet (struct ipcp_lattice *res, struct ipcp_lattice *lat1,
 242                   struct ipcp_lattice *lat2)
 243 {
 244   if (lat1->type == IPA_BOTTOM || lat2->type == IPA_BOTTOM)
 245     {
 246       res->type = IPA_BOTTOM;
 247       return;
 248     }
 249   if (lat1->type == IPA_TOP)
 250     {
 251       res->type = lat2->type;
 252       res->constant = lat2->constant;
 253       return;
 254     }
 255   if (lat2->type == IPA_TOP)
 256     {
 257       res->type = lat1->type;
 258       res->constant = lat1->constant;
 259       return;
 260     }
 261   if (!ipcp_lats_are_equal (lat1, lat2))
 262     {
 263       res->type = IPA_BOTTOM;
 264       return;
 265     }
 266   res->type = lat1->type;
 267   res->constant = lat1->constant;
 268 }
 269
 270 /* Return the lattice corresponding to the Ith formal parameter of the function
 271    described by INFO.  */
 272 static inline struct ipcp_lattice *
 273 ipcp_get_lattice (struct ipa_node_params *info, int i)
 274 {
 275   return &(info->params[i].ipcp_lattice);
 276 }
 277
 278 /* Given the jump function JFUNC, compute the lattice LAT that describes the
 279    value coming down the callsite. INFO describes the caller node so that
 280    pass-through jump functions can be evaluated.  */
 281 static void
 282 ipcp_lattice_from_jfunc (struct ipa_node_params *info, struct ipcp_lattice *lat,
 283                          struct ipa_jump_func *jfunc)
 284 {
 285   if (jfunc->type == IPA_JF_CONST)
 286     {
 287       lat->type = IPA_CONST_VALUE;
 288       lat->constant = jfunc->value.constant;
 289     }
 290   else if (jfunc->type == IPA_JF_PASS_THROUGH)
 291     {
 292       struct ipcp_lattice *caller_lat;
 293
 294       caller_lat = ipcp_get_lattice (info, jfunc->value.formal_id);
 295       lat->type = caller_lat->type;
 296       lat->constant = caller_lat->constant;
 297     }
 298   else
 299     lat->type = IPA_BOTTOM;
 300 }
 301
 302 /* True when OLD_LAT and NEW_LAT values are not the same.  */
 303
 304 static bool
 305 ipcp_lattice_changed (struct ipcp_lattice *old_lat,
 306                       struct ipcp_lattice *new_lat)
 307 {
 308   if (old_lat->type == new_lat->type)
 309     {
 310       if (!ipcp_lat_is_const (old_lat))
 311         return false;
 312       if (ipcp_lats_are_equal (old_lat, new_lat))
 313         return false;
 314     }
 315   return true;
 316 }
 317
 318 /* Print all ipcp_lattices of all functions to F.  */
 319 static void
 320 ipcp_print_all_lattices (FILE * f)
 321 {
 322   struct cgraph_node *node;
 323   int i, count;
 324
 325   fprintf (f, "\nLattice:\n");
 326   for (node = cgraph_nodes; node; node = node->next)
 327     {
 328       struct ipa_node_params *info;
 329
 330       if (!node->analyzed)
 331         continue;
 332       info = IPA_NODE_REF (node);
 333       fprintf (f, "  Node: %s:\n", cgraph_node_name (node));
 334       count = ipa_get_param_count (info);
 335       for (i = 0; i < count; i++)
 336         {
 337           struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
 338
 339           fprintf (f, "    param [%d]: ", i);
 340           if (lat->type == IPA_CONST_VALUE)
 341             {
 342               fprintf (f, "type is CONST ");
 343               print_generic_expr (f, lat->constant, 0);
 344               fprintf (f, "\n");
 345             }
 346           else if (lat->type == IPA_TOP)
 347             fprintf (f, "type is TOP\n");
 348           else
 349             fprintf (f, "type is BOTTOM\n");
 350         }
 351     }
 352 }
 353
 354 /* Return true if ipcp algorithms would allow cloning NODE.  */
 355
 356 static bool
 357 ipcp_versionable_function_p (struct cgraph_node *node)
 358 {
 359   tree decl = node->decl;
 360   basic_block bb;
 361
 362   /* There are a number of generic reasons functions cannot be versioned.  */
 363   if (!tree_versionable_function_p (decl))
 364     return false;
 365
 366   /* Removing arguments doesn't work if the function takes varargs.  */
 367   if (DECL_STRUCT_FUNCTION (decl)->stdarg)
 368     return false;
 369
 370   /* Removing arguments doesn't work if we use __builtin_apply_args.  */
 371   FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (decl))
 372     {
 373       gimple_stmt_iterator gsi;
 374       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 375         {
 376           const_gimple stmt = gsi_stmt (gsi);
 377           tree t;
 378
 379           if (!is_gimple_call (stmt))
 380             continue;
 381           t = gimple_call_fndecl (stmt);
 382           if (t == NULL_TREE)
 383             continue;
 384           if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL
 385               && DECL_FUNCTION_CODE (t) == BUILT_IN_APPLY_ARGS)
 386             return false;
 387         }
 388     }
 389
 390   return true;
 391 }
 392
 393 /* Return true if this NODE is viable candidate for cloning.  */
 394 static bool
 395 ipcp_cloning_candidate_p (struct cgraph_node *node)
 396 {
 397   int n_calls = 0;
 398   int n_hot_calls = 0;
 399   gcov_type direct_call_sum = 0;
 400   struct cgraph_edge *e;
 401
 402   /* We never clone functions that are not visible from outside.
 403      FIXME: in future we should clone such functions when they are called with
 404      different constants, but current ipcp implementation is not good on this.
 405      */
 406   if (!node->needed || !node->analyzed)
 407     return false;
 408
 409   if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
 410     {
 411       if (dump_file)
 412         fprintf (dump_file, "Not considering %s for cloning; body is overwrittable.\n",
 413                  cgraph_node_name (node));
 414       return false;
 415     }
 416   if (!ipcp_versionable_function_p (node))
 417     {
 418       if (dump_file)
 419         fprintf (dump_file, "Not considering %s for cloning; body is not versionable.\n",
 420                  cgraph_node_name (node));
 421       return false;
 422     }
 423   for (e = node->callers; e; e = e->next_caller)
 424     {
 425       direct_call_sum += e->count;
 426       n_calls ++;
 427       if (cgraph_maybe_hot_edge_p (e))
 428         n_hot_calls ++;
 429     }
 430
 431   if (!n_calls)
 432     {
 433       if (dump_file)
 434         fprintf (dump_file, "Not considering %s for cloning; no direct calls.\n",
 435                  cgraph_node_name (node));
 436       return false;
 437     }
 438   if (node->local.inline_summary.self_size < n_calls)
 439     {
 440       if (dump_file)
 441         fprintf (dump_file, "Considering %s for cloning; code would shrink.\n",
 442                  cgraph_node_name (node));
 443       return true;
 444     }
 445
 446   if (!flag_ipa_cp_clone)
 447     {
 448       if (dump_file)
 449         fprintf (dump_file, "Not considering %s for cloning; -fipa-cp-clone disabled.\n",
 450                  cgraph_node_name (node));
 451       return false;
 452     }
 453
 454   if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
 455     {
 456       if (dump_file)
 457         fprintf (dump_file, "Not considering %s for cloning; optimizing it for size.\n",
 458                  cgraph_node_name (node));
 459       return false;
 460     }
 461
 462   /* When profile is available and function is hot, propagate into it even if
 463      calls seems cold; constant propagation can improve function's speed
 464      significandly.  */
 465   if (max_count)
 466     {
 467       if (direct_call_sum > node->count * 90 / 100)
 468         {
 469           if (dump_file)
 470             fprintf (dump_file, "Considering %s for cloning; usually called directly.\n",
 471                      cgraph_node_name (node));
 472           return true;
 473         }
 474     }
 475   if (!n_hot_calls)
 476     {
 477       if (dump_file)
 478         fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
 479                  cgraph_node_name (node));
 480       return false;
 481     }
 482   if (dump_file)
 483     fprintf (dump_file, "Considering %s for cloning.\n",
 484              cgraph_node_name (node));
 485   return true;
 486 }
 487
 488 /* Initialize ipcp_lattices array.  The lattices corresponding to supported
 489    types (integers, real types and Fortran constants defined as const_decls)
 490    are initialized to IPA_TOP, the rest of them to IPA_BOTTOM.  */
 491 static void
 492 ipcp_initialize_node_lattices (struct cgraph_node *node)
 493 {
 494   int i;
 495   struct ipa_node_params *info = IPA_NODE_REF (node);
 496   enum ipa_lattice_type type;
 497
 498   if (ipa_is_called_with_var_arguments (info))
 499     type = IPA_BOTTOM;
 500   else if (!node->needed)
 501     type = IPA_TOP;
 502   /* When cloning is allowed, we can assume that externally visible functions
 503      are not called.  We will compensate this by cloning later.  */
 504   else if (ipcp_cloning_candidate_p (node))
 505     type = IPA_TOP, n_cloning_candidates ++;
 506   else
 507     type = IPA_BOTTOM;
 508
 509   for (i = 0; i < ipa_get_param_count (info) ; i++)
 510     ipcp_get_lattice (info, i)->type = type;
 511 }
 512
 513 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
 514    Return the tree.  */
 515 static tree
 516 build_const_val (struct ipcp_lattice *lat, tree tree_type)
 517 {
 518   tree val;
 519
 520   gcc_assert (ipcp_lat_is_const (lat));
 521   val = lat->constant;
 522
 523   if (!useless_type_conversion_p (tree_type, TREE_TYPE (val)))
 524     {
 525       if (fold_convertible_p (tree_type, val))
 526         return fold_build1 (NOP_EXPR, tree_type, val);
 527       else
 528         return fold_build1 (VIEW_CONVERT_EXPR, tree_type, val);
 529     }
 530   return val;
 531 }
 532
 533 /* Compute the proper scale for NODE.  It is the ratio between the number of
 534    direct calls (represented on the incoming cgraph_edges) and sum of all
 535    invocations of NODE (represented as count in cgraph_node).  */
 536 static void
 537 ipcp_compute_node_scale (struct cgraph_node *node)
 538 {
 539   gcov_type sum;
 540   struct cgraph_edge *cs;
 541
 542   sum = 0;
 543   /* Compute sum of all counts of callers. */
 544   for (cs = node->callers; cs != NULL; cs = cs->next_caller)
 545     sum += cs->count;
 546   if (node->count == 0)
 547     ipcp_set_node_scale (node, 0);
 548   else
 549     ipcp_set_node_scale (node, sum * REG_BR_PROB_BASE / node->count);
 550 }
 551
 552 /* Initialization and computation of IPCP data structures.  This is the initial
 553    intraprocedural analysis of functions, which gathers information to be
 554    propagated later on.  */
 555 static void
 556 ipcp_init_stage (void)
 557 {
 558   struct cgraph_node *node;
 559   struct cgraph_edge *cs;
 560
 561   for (node = cgraph_nodes; node; node = node->next)
 562     if (node->analyzed)
 563       ipcp_analyze_node (node);
 564   for (node = cgraph_nodes; node; node = node->next)
 565     {
 566       if (!node->analyzed)
 567         continue;
 568       /* building jump functions  */
 569       for (cs = node->callees; cs; cs = cs->next_callee)
 570         {
 571           if (!cs->callee->analyzed)
 572             continue;
 573           ipa_count_arguments (cs);
 574           if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
 575               != ipa_get_param_count (IPA_NODE_REF (cs->callee)))
 576             {
 577               /* Handle cases of functions with
 578                  a variable number of parameters.  */
 579               ipa_set_called_with_variable_arg (IPA_NODE_REF (cs->callee));
 580               if (flag_indirect_inlining)
 581                 ipa_compute_jump_functions (cs);
 582             }
 583           else
 584             ipa_compute_jump_functions (cs);
 585         }
 586     }
 587 }
 588
 589 /* Return true if there are some formal parameters whose value is IPA_TOP (in
 590    the whole compilation unit).  Change their values to IPA_BOTTOM, since they
 591    most probably get their values from outside of this compilation unit.  */
 592 static bool
 593 ipcp_change_tops_to_bottom (void)
 594 {
 595   int i, count;
 596   struct cgraph_node *node;
 597   bool prop_again;
 598
 599   prop_again = false;
 600   for (node = cgraph_nodes; node; node = node->next)
 601     {
 602       struct ipa_node_params *info = IPA_NODE_REF (node);
 603       count = ipa_get_param_count (info);
 604       for (i = 0; i < count; i++)
 605         {
 606           struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
 607           if (lat->type == IPA_TOP)
 608             {
 609               prop_again = true;
 610               if (dump_file)
 611                 {
 612                   fprintf (dump_file, "Forcing param ");
 613                   print_generic_expr (dump_file, ipa_get_param (info, i), 0);
 614                   fprintf (dump_file, " of node %s to bottom.\n",
 615                            cgraph_node_name (node));
 616                 }
 617               lat->type = IPA_BOTTOM;
 618             }
 619         }
 620     }
 621   return prop_again;
 622 }
 623
 624 /* Interprocedural analysis. The algorithm propagates constants from the
 625    caller's parameters to the callee's arguments.  */
 626 static void
 627 ipcp_propagate_stage (void)
 628 {
 629   int i;
 630   struct ipcp_lattice inc_lat = { IPA_BOTTOM, NULL };
 631   struct ipcp_lattice new_lat = { IPA_BOTTOM, NULL };
 632   struct ipcp_lattice *dest_lat;
 633   struct cgraph_edge *cs;
 634   struct ipa_jump_func *jump_func;
 635   struct ipa_func_list *wl;
 636   int count;
 637
 638   ipa_check_create_node_params ();
 639   ipa_check_create_edge_args ();
 640
 641   /* Initialize worklist to contain all functions.  */
 642   wl = ipa_init_func_list ();
 643   while (wl)
 644     {
 645       struct cgraph_node *node = ipa_pop_func_from_list (&wl);
 646       struct ipa_node_params *info = IPA_NODE_REF (node);
 647
 648       for (cs = node->callees; cs; cs = cs->next_callee)
 649         {
 650           struct ipa_node_params *callee_info = IPA_NODE_REF (cs->callee);
 651           struct ipa_edge_args *args = IPA_EDGE_REF (cs);
 652
 653           if (ipa_is_called_with_var_arguments (callee_info))
 654             continue;
 655
 656           count = ipa_get_cs_argument_count (args);
 657           for (i = 0; i < count; i++)
 658             {
 659               jump_func = ipa_get_ith_jump_func (args, i);
 660               ipcp_lattice_from_jfunc (info, &inc_lat, jump_func);
 661               dest_lat = ipcp_get_lattice (callee_info, i);
 662               ipa_lattice_meet (&new_lat, &inc_lat, dest_lat);
 663               if (ipcp_lattice_changed (&new_lat, dest_lat))
 664                 {
 665                   dest_lat->type = new_lat.type;
 666                   dest_lat->constant = new_lat.constant;
 667                   ipa_push_func_to_list (&wl, cs->callee);
 668                 }
 669             }
 670         }
 671     }
 672 }
 673
 674 /* Call the constant propagation algorithm and re-call it if necessary
 675    (if there are undetermined values left).  */
 676 static void
 677 ipcp_iterate_stage (void)
 678 {
 679   struct cgraph_node *node;
 680   n_cloning_candidates = 0;
 681
 682   if (dump_file)
 683     fprintf (dump_file, "\nIPA iterate stage:\n\n");
 684   for (node = cgraph_nodes; node; node = node->next)
 685     {
 686       ipcp_initialize_node_lattices (node);
 687       ipcp_compute_node_scale (node);
 688     }
 689   if (dump_file && (dump_flags & TDF_DETAILS))
 690     {
 691       ipcp_print_all_lattices (dump_file);
 692       ipcp_function_scale_print (dump_file);
 693     }
 694
 695   ipcp_propagate_stage ();
 696   if (ipcp_change_tops_to_bottom ())
 697     /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
 698        This change should be propagated.  */
 699     {
 700       gcc_assert (n_cloning_candidates);
 701       ipcp_propagate_stage ();
 702     }
 703   if (dump_file)
 704     {
 705       fprintf (dump_file, "\nIPA lattices after propagation:\n");
 706       ipcp_print_all_lattices (dump_file);
 707       if (dump_flags & TDF_DETAILS)
 708         ipcp_print_profile_data (dump_file);
 709     }
 710 }
 711
 712 /* Check conditions to forbid constant insertion to function described by
 713    NODE.  */
 714 static inline bool
 715 ipcp_node_modifiable_p (struct cgraph_node *node)
 716 {
 717   /* Once we will be able to do in-place replacement, we can be more
 718      lax here.  */
 719   return ipcp_versionable_function_p (node);
 720 }
 721
 722 /* Print count scale data structures.  */
 723 static void
 724 ipcp_function_scale_print (FILE * f)
 725 {
 726   struct cgraph_node *node;
 727
 728   for (node = cgraph_nodes; node; node = node->next)
 729     {
 730       if (!node->analyzed)
 731         continue;
 732       fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
 733       fprintf (f, "value is  " HOST_WIDE_INT_PRINT_DEC
 734                "  \n", (HOST_WIDE_INT) ipcp_get_node_scale (node));
 735     }
 736 }
 737
 738 /* Print counts of all cgraph nodes.  */
 739 static void
 740 ipcp_print_func_profile_counts (FILE * f)
 741 {
 742   struct cgraph_node *node;
 743
 744   for (node = cgraph_nodes; node; node = node->next)
 745     {
 746       fprintf (f, "function %s: ", cgraph_node_name (node));
 747       fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC
 748                "  \n", (HOST_WIDE_INT) node->count);
 749     }
 750 }
 751
 752 /* Print counts of all cgraph edges.  */
 753 static void
 754 ipcp_print_call_profile_counts (FILE * f)
 755 {
 756   struct cgraph_node *node;
 757   struct cgraph_edge *cs;
 758
 759   for (node = cgraph_nodes; node; node = node->next)
 760     {
 761       for (cs = node->callees; cs; cs = cs->next_callee)
 762         {
 763           fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
 764                    cgraph_node_name (cs->callee));
 765           fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC "  \n",
 766                    (HOST_WIDE_INT) cs->count);
 767         }
 768     }
 769 }
 770
 771 /* Print profile info for all functions.  */
 772 static void
 773 ipcp_print_profile_data (FILE * f)
 774 {
 775   fprintf (f, "\nNODE COUNTS :\n");
 776   ipcp_print_func_profile_counts (f);
 777   fprintf (f, "\nCS COUNTS stage:\n");
 778   ipcp_print_call_profile_counts (f);
 779 }
 780
 781 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
 782    processed by versioning, which operates according to the flags set.
 783    PARM_TREE is the formal parameter found to be constant.  LAT represents the
 784    constant.  */
 785 static struct ipa_replace_map *
 786 ipcp_create_replace_map (tree parm_tree, struct ipcp_lattice *lat)
 787 {
 788   struct ipa_replace_map *replace_map;
 789   tree const_val;
 790
 791   replace_map = GGC_NEW (struct ipa_replace_map);
 792   const_val = build_const_val (lat, TREE_TYPE (parm_tree));
 793   if (dump_file)
 794     {
 795       fprintf (dump_file, "  replacing param ");
 796       print_generic_expr (dump_file, parm_tree, 0);
 797       fprintf (dump_file, " with const ");
 798       print_generic_expr (dump_file, const_val, 0);
 799       fprintf (dump_file, "\n");
 800     }
 801   replace_map->old_tree = parm_tree;
 802   replace_map->new_tree = const_val;
 803   replace_map->replace_p = true;
 804   replace_map->ref_p = false;
 805
 806   return replace_map;
 807 }
 808
 809 /* Return true if this callsite should be redirected to the original callee
 810    (instead of the cloned one).  */
 811 static bool
 812 ipcp_need_redirect_p (struct cgraph_edge *cs)
 813 {
 814   struct ipa_node_params *orig_callee_info;
 815   int i, count;
 816   struct ipa_jump_func *jump_func;
 817   struct cgraph_node *node = cs->callee, *orig;
 818
 819   if (!n_cloning_candidates)
 820     return false;
 821
 822   if ((orig = ipcp_get_orig_node (node)) != NULL)
 823     node = orig;
 824   if (ipcp_get_orig_node (cs->caller))
 825     return false;
 826
 827   orig_callee_info = IPA_NODE_REF (node);
 828   count = ipa_get_param_count (orig_callee_info);
 829   for (i = 0; i < count; i++)
 830     {
 831       struct ipcp_lattice *lat = ipcp_get_lattice (orig_callee_info, i);
 832       if (ipcp_lat_is_const (lat))
 833         {
 834           jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
 835           if (jump_func->type != IPA_JF_CONST)
 836             return true;
 837         }
 838     }
 839
 840   return false;
 841 }
 842
 843 /* Fix the callsites and the call graph after function cloning was done.  */
 844 static void
 845 ipcp_update_callgraph (void)
 846 {
 847   struct cgraph_node *node;
 848
 849   for (node = cgraph_nodes; node; node = node->next)
 850     if (node->analyzed && ipcp_node_is_clone (node))
 851       {
 852         bitmap args_to_skip = BITMAP_ALLOC (NULL);
 853         struct cgraph_node *orig_node = ipcp_get_orig_node (node);
 854         struct ipa_node_params *info = IPA_NODE_REF (orig_node);
 855         int i, count = ipa_get_param_count (info);
 856         struct cgraph_edge *cs, *next;
 857
 858         for (i = 0; i < count; i++)
 859           {
 860             struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
 861             tree parm_tree = ipa_get_param (info, i);
 862
 863             /* We can proactively remove obviously unused arguments.  */
 864             if (is_gimple_reg (parm_tree)
 865                 && !gimple_default_def (DECL_STRUCT_FUNCTION (orig_node->decl),
 866                                         parm_tree))
 867               {
 868                 bitmap_set_bit (args_to_skip, i);
 869                 continue;
 870               }
 871
 872             if (lat->type == IPA_CONST_VALUE)
 873               bitmap_set_bit (args_to_skip, i);
 874           }
 875         for (cs = node->callers; cs; cs = next)
 876           {
 877             next = cs->next_caller;
 878             if (!ipcp_node_is_clone (cs->caller) && ipcp_need_redirect_p (cs))
 879               cgraph_redirect_edge_callee (cs, orig_node);
 880           }
 881       }
 882 }
 883
 884 /* Update profiling info for versioned functions and the functions they were
 885    versioned from.  */
 886 static void
 887 ipcp_update_profiling (void)
 888 {
 889   struct cgraph_node *node, *orig_node;
 890   gcov_type scale, scale_complement;
 891   struct cgraph_edge *cs;
 892
 893   for (node = cgraph_nodes; node; node = node->next)
 894     {
 895       if (ipcp_node_is_clone (node))
 896         {
 897           orig_node = ipcp_get_orig_node (node);
 898           scale = ipcp_get_node_scale (orig_node);
 899           node->count = orig_node->count * scale / REG_BR_PROB_BASE;
 900           scale_complement = REG_BR_PROB_BASE - scale;
 901           orig_node->count =
 902             orig_node->count * scale_complement / REG_BR_PROB_BASE;
 903           for (cs = node->callees; cs; cs = cs->next_callee)
 904             cs->count = cs->count * scale / REG_BR_PROB_BASE;
 905           for (cs = orig_node->callees; cs; cs = cs->next_callee)
 906             cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
 907         }
 908     }
 909 }
 910
 911 /* If NODE was cloned, how much would program grow? */
 912 static long
 913 ipcp_estimate_growth (struct cgraph_node *node)
 914 {
 915   struct cgraph_edge *cs;
 916   int redirectable_node_callers = 0;
 917   int removable_args = 0;
 918   bool need_original = node->needed;
 919   struct ipa_node_params *info;
 920   int i, count;
 921   int growth;
 922
 923   for (cs = node->callers; cs != NULL; cs = cs->next_caller)
 924     if (cs->caller == node || !ipcp_need_redirect_p (cs))
 925       redirectable_node_callers++;
 926     else
 927       need_original = true;
 928
 929   /* If we will be able to fully replace orignal node, we never increase
 930      program size.  */
 931   if (!need_original)
 932     return 0;
 933
 934   info = IPA_NODE_REF (node);
 935   count = ipa_get_param_count (info);
 936   for (i = 0; i < count; i++)
 937     {
 938       struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
 939       tree parm_tree = ipa_get_param (info, i);
 940
 941       /* We can proactively remove obviously unused arguments.  */
 942       if (is_gimple_reg (parm_tree)
 943           && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
 944                                   parm_tree))
 945         removable_args++;
 946
 947       if (lat->type == IPA_CONST_VALUE)
 948         removable_args++;
 949     }
 950
 951   /* We make just very simple estimate of savings for removal of operand from
 952      call site.  Precise cost is dificult to get, as our size metric counts
 953      constants and moves as free.  Generally we are looking for cases that
 954      small function is called very many times.  */
 955   growth = node->local.inline_summary.self_size
 956            - removable_args * redirectable_node_callers;
 957   if (growth < 0)
 958     return 0;
 959   return growth;
 960 }
 961
 962
 963 /* Estimate cost of cloning NODE.  */
 964 static long
 965 ipcp_estimate_cloning_cost (struct cgraph_node *node)
 966 {
 967   int freq_sum = 1;
 968   gcov_type count_sum = 1;
 969   struct cgraph_edge *e;
 970   int cost;
 971
 972   cost = ipcp_estimate_growth (node) * 1000;
 973   if (!cost)
 974     {
 975       if (dump_file)
 976         fprintf (dump_file, "Versioning of %s will save code size\n",
 977                  cgraph_node_name (node));
 978       return 0;
 979     }
 980
 981   for (e = node->callers; e; e = e->next_caller)
 982     if (!bitmap_bit_p (dead_nodes, e->caller->uid)
 983         && !ipcp_need_redirect_p (e))
 984       {
 985         count_sum += e->count;
 986         freq_sum += e->frequency + 1;
 987       }
 988
 989   if (max_count)
 990     cost /= count_sum * 1000 / max_count + 1;
 991   else
 992     cost /= freq_sum * 1000 / REG_BR_PROB_BASE + 1;
 993   if (dump_file)
 994     fprintf (dump_file, "Cost of versioning %s is %i, (size: %i, freq: %i)\n",
 995              cgraph_node_name (node), cost, node->local.inline_summary.self_size,
 996              freq_sum);
 997   return cost + 1;
 998 }
 999
1000 /* Return number of live constant parameters.  */
1001 static int
1002 ipcp_const_param_count (struct cgraph_node *node)
1003 {
1004   int const_param = 0;
1005   struct ipa_node_params *info = IPA_NODE_REF (node);
1006   int count = ipa_get_param_count (info);
1007   int i;
1008
1009   for (i = 0; i < count; i++)
1010     {
1011       struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1012       tree parm_tree = ipa_get_param (info, i);
1013       if (ipcp_lat_is_insertable (lat)
1014           /* Do not count obviously unused arguments.  */
1015           && (!is_gimple_reg (parm_tree)
1016               || gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1017                                      parm_tree)))
1018         const_param++;
1019     }
1020   return const_param;
1021 }
1022
1023 /* Propagate the constant parameters found by ipcp_iterate_stage()
1024    to the function's code.  */
1025 static void
1026 ipcp_insert_stage (void)
1027 {
1028   struct cgraph_node *node, *node1 = NULL;
1029   int i;
1030   VEC (cgraph_edge_p, heap) * redirect_callers;
1031   VEC (ipa_replace_map_p,gc)* replace_trees;
1032   int node_callers, count;
1033   tree parm_tree;
1034   struct ipa_replace_map *replace_param;
1035   fibheap_t heap;
1036   long overall_size = 0, new_size = 0;
1037   long max_new_size;
1038
1039   ipa_check_create_node_params ();
1040   ipa_check_create_edge_args ();
1041   if (dump_file)
1042     fprintf (dump_file, "\nIPA insert stage:\n\n");
1043
1044   dead_nodes = BITMAP_ALLOC (NULL);
1045
1046   for (node = cgraph_nodes; node; node = node->next)
1047     if (node->analyzed)
1048       {
1049         if (node->count > max_count)
1050           max_count = node->count;
1051         overall_size += node->local.inline_summary.self_size;
1052       }
1053
1054   max_new_size = overall_size;
1055   if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1056     max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1057   max_new_size = max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
1058
1059   /* First collect all functions we proved to have constant arguments to heap.  */
1060   heap = fibheap_new ();
1061   for (node = cgraph_nodes; node; node = node->next)
1062     {
1063       struct ipa_node_params *info;
1064       /* Propagation of the constant is forbidden in certain conditions.  */
1065       if (!node->analyzed || !ipcp_node_modifiable_p (node))
1066           continue;
1067       info = IPA_NODE_REF (node);
1068       if (ipa_is_called_with_var_arguments (info))
1069         continue;
1070       if (ipcp_const_param_count (node))
1071         node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node), node);
1072      }
1073
1074   /* Now clone in priority order until code size growth limits are met or
1075      heap is emptied.  */
1076   while (!fibheap_empty (heap))
1077     {
1078       struct ipa_node_params *info;
1079       int growth = 0;
1080       bitmap args_to_skip;
1081       struct cgraph_edge *cs;
1082
1083       node = (struct cgraph_node *)fibheap_extract_min (heap);
1084       node->aux = NULL;
1085       if (dump_file)
1086         fprintf (dump_file, "considering function %s\n",
1087                  cgraph_node_name (node));
1088
1089       growth = ipcp_estimate_growth (node);
1090
1091       if (new_size + growth > max_new_size)
1092         break;
1093       if (growth
1094           && optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl)))
1095         {
1096           if (dump_file)
1097             fprintf (dump_file, "Not versioning, cold code would grow");
1098           continue;
1099         }
1100
1101       new_size += growth;
1102
1103       /* Look if original function becomes dead after clonning.  */
1104       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1105         if (cs->caller == node || ipcp_need_redirect_p (cs))
1106           break;
1107       if (!cs && !node->needed)
1108         bitmap_set_bit (dead_nodes, node->uid);
1109
1110       info = IPA_NODE_REF (node);
1111       count = ipa_get_param_count (info);
1112
1113       replace_trees = VEC_alloc (ipa_replace_map_p, gc, 1);
1114       args_to_skip = BITMAP_GGC_ALLOC ();
1115       for (i = 0; i < count; i++)
1116         {
1117           struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
1118           parm_tree = ipa_get_param (info, i);
1119
1120           /* We can proactively remove obviously unused arguments.  */
1121           if (is_gimple_reg (parm_tree)
1122               && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1123                                       parm_tree))
1124             {
1125               bitmap_set_bit (args_to_skip, i);
1126               continue;
1127             }
1128
1129           if (lat->type == IPA_CONST_VALUE)
1130             {
1131               replace_param =
1132                 ipcp_create_replace_map (parm_tree, lat);
1133               VEC_safe_push (ipa_replace_map_p, gc, replace_trees, replace_param);
1134               bitmap_set_bit (args_to_skip, i);
1135             }
1136         }
1137
1138       /* Compute how many callers node has.  */
1139       node_callers = 0;
1140       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1141         node_callers++;
1142       redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers);
1143       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1144         VEC_quick_push (cgraph_edge_p, redirect_callers, cs);
1145
1146       /* Redirecting all the callers of the node to the
1147          new versioned node.  */
1148       node1 =
1149         cgraph_create_virtual_clone (node, redirect_callers, replace_trees,
1150                                      args_to_skip);
1151       args_to_skip = NULL;
1152       VEC_free (cgraph_edge_p, heap, redirect_callers);
1153       replace_trees = NULL;
1154
1155       if (node1 == NULL)
1156         continue;
1157       if (dump_file)
1158         fprintf (dump_file, "versioned function %s with growth %i, overall %i\n",
1159                  cgraph_node_name (node), (int)growth, (int)new_size);
1160       ipcp_init_cloned_node (node, node1);
1161
1162       /* TODO: We can use indirect inlning info to produce new calls.  */
1163
1164       if (dump_file)
1165         dump_function_to_file (node1->decl, dump_file, dump_flags);
1166
1167       for (cs = node->callees; cs; cs = cs->next_callee)
1168         if (cs->callee->aux)
1169           {
1170             fibheap_delete_node (heap, (fibnode_t) cs->callee->aux);
1171             cs->callee->aux = fibheap_insert (heap,
1172                                               ipcp_estimate_cloning_cost (cs->callee),
1173                                               cs->callee);
1174           }
1175     }
1176
1177   while (!fibheap_empty (heap))
1178     {
1179       if (dump_file)
1180         fprintf (dump_file, "skipping function %s\n",
1181                  cgraph_node_name (node));
1182       node = (struct cgraph_node *) fibheap_extract_min (heap);
1183       node->aux = NULL;
1184     }
1185   fibheap_delete (heap);
1186   BITMAP_FREE (dead_nodes);
1187   ipcp_update_callgraph ();
1188   ipcp_update_profiling ();
1189 }
1190
1191 /* The IPCP driver.  */
1192 static unsigned int
1193 ipcp_driver (void)
1194 {
1195   cgraph_remove_unreachable_nodes (true,dump_file);
1196   if (dump_file)
1197     {
1198       fprintf (dump_file, "\nIPA structures before propagation:\n");
1199       if (dump_flags & TDF_DETAILS)
1200         ipa_print_all_params (dump_file);
1201       ipa_print_all_jump_functions (dump_file);
1202     }
1203   /* 2. Do the interprocedural propagation.  */
1204   ipcp_iterate_stage ();
1205   /* 3. Insert the constants found to the functions.  */
1206   ipcp_insert_stage ();
1207   if (dump_file && (dump_flags & TDF_DETAILS))
1208     {
1209       fprintf (dump_file, "\nProfiling info after insert stage:\n");
1210       ipcp_print_profile_data (dump_file);
1211     }
1212   /* Free all IPCP structures.  */
1213   free_all_ipa_structures_after_ipa_cp ();
1214   if (dump_file)
1215     fprintf (dump_file, "\nIPA constant propagation end\n");
1216   return 0;
1217 }
1218
1219 /* Note function body size.  */
1220 static void
1221 ipcp_generate_summary (void)
1222 {
1223   if (dump_file)
1224     fprintf (dump_file, "\nIPA constant propagation start:\n");
1225   ipa_check_create_node_params ();
1226   ipa_check_create_edge_args ();
1227   ipa_register_cgraph_hooks ();
1228   /* 1. Call the init stage to initialize
1229      the ipa_node_params and ipa_edge_args structures.  */
1230   ipcp_init_stage ();
1231 }
1232
1233 /* Gate for IPCP optimization.  */
1234 static bool
1235 cgraph_gate_cp (void)
1236 {
1237   return flag_ipa_cp;
1238 }
1239
1240 struct ipa_opt_pass_d pass_ipa_cp =
1241 {
1242  {
1243   IPA_PASS,
1244   "cp",                         /* name */
1245   cgraph_gate_cp,               /* gate */
1246   ipcp_driver,                  /* execute */
1247   NULL,                         /* sub */
1248   NULL,                         /* next */
1249   0,                            /* static_pass_number */
1250   TV_IPA_CONSTANT_PROP,         /* tv_id */
1251   0,                            /* properties_required */
1252   0,                            /* properties_provided */
1253   0,                            /* properties_destroyed */
1254   0,                            /* todo_flags_start */
1255   TODO_dump_cgraph | TODO_dump_func |
1256   TODO_remove_functions /* todo_flags_finish */
1257  },
1258  ipcp_generate_summary,                 /* generate_summary */
1259  NULL,                                  /* write_summary */
1260  NULL,                                  /* read_summary */
1261  NULL,                                  /* function_read_summary */
1262  0,                                     /* TODOs */
1263  NULL,                                  /* function_transform */
1264  NULL,                                  /* variable_transform */
1265 };