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