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