gcc/ipa-cp.c

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