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_modifiable_p (struct cgraph_node *node)
 564 {
 565   /* Once we will be able to do in-place replacement, we can be more
 566      lax here.  */
 567   return tree_versionable_function_p (node->decl);
 568 }
 569
 570 /* Print count scale data structures.  */
 571 static void
 572 ipcp_function_scale_print (FILE * f)
 573 {
 574   struct cgraph_node *node;
 575
 576   for (node = cgraph_nodes; node; node = node->next)
 577     {
 578       if (!node->analyzed)
 579         continue;
 580       fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
 581       fprintf (f, "value is  " HOST_WIDE_INT_PRINT_DEC
 582                "  \n", (HOST_WIDE_INT) ipcp_get_node_scale (node));
 583     }
 584 }
 585
 586 /* Print counts of all cgraph nodes.  */
 587 static void
 588 ipcp_print_func_profile_counts (FILE * f)
 589 {
 590   struct cgraph_node *node;
 591
 592   for (node = cgraph_nodes; node; node = node->next)
 593     {
 594       fprintf (f, "function %s: ", cgraph_node_name (node));
 595       fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC
 596                "  \n", (HOST_WIDE_INT) node->count);
 597     }
 598 }
 599
 600 /* Print counts of all cgraph edges.  */
 601 static void
 602 ipcp_print_call_profile_counts (FILE * f)
 603 {
 604   struct cgraph_node *node;
 605   struct cgraph_edge *cs;
 606
 607   for (node = cgraph_nodes; node; node = node->next)
 608     {
 609       for (cs = node->callees; cs; cs = cs->next_callee)
 610         {
 611           fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
 612                    cgraph_node_name (cs->callee));
 613           fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC "  \n",
 614                    (HOST_WIDE_INT) cs->count);
 615         }
 616     }
 617 }
 618
 619 /* Print all counts and probabilities of cfg edges of all functions.  */
 620 static void
 621 ipcp_print_edge_profiles (FILE * f)
 622 {
 623   struct cgraph_node *node;
 624   basic_block bb;
 625   edge_iterator ei;
 626   edge e;
 627
 628   for (node = cgraph_nodes; node; node = node->next)
 629     {
 630       fprintf (f, "function %s: \n", cgraph_node_name (node));
 631       if (node->analyzed)
 632         {
 633           bb =
 634             ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 635           fprintf (f, "ENTRY: ");
 636           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 637                    " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
 638
 639           if (bb->succs)
 640             FOR_EACH_EDGE (e, ei, bb->succs)
 641             {
 642               if (e->dest ==
 643                   EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
 644                                                (node->decl)))
 645                 fprintf (f, "edge ENTRY -> EXIT,  Count");
 646               else
 647                 fprintf (f, "edge ENTRY -> %d,  Count", e->dest->index);
 648               fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 649                        " Prob %d\n", (HOST_WIDE_INT) e->count,
 650                        e->probability);
 651             }
 652           FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 653           {
 654             fprintf (f, "bb[%d]: ", bb->index);
 655             fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 656                      " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
 657             FOR_EACH_EDGE (e, ei, bb->succs)
 658             {
 659               if (e->dest ==
 660                   EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
 661                                                (node->decl)))
 662                 fprintf (f, "edge %d -> EXIT,  Count", e->src->index);
 663               else
 664                 fprintf (f, "edge %d -> %d,  Count", e->src->index,
 665                          e->dest->index);
 666               fprintf (f, " " HOST_WIDE_INT_PRINT_DEC " Prob %d\n",
 667                        (HOST_WIDE_INT) e->count, e->probability);
 668             }
 669           }
 670         }
 671     }
 672 }
 673
 674 /* Print counts and frequencies for all basic blocks of all functions.  */
 675 static void
 676 ipcp_print_bb_profiles (FILE * f)
 677 {
 678   basic_block bb;
 679   struct cgraph_node *node;
 680
 681   for (node = cgraph_nodes; node; node = node->next)
 682     {
 683       fprintf (f, "function %s: \n", cgraph_node_name (node));
 684       if (node->analyzed)
 685         {
 686           bb =
 687             ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 688           fprintf (f, "ENTRY: Count");
 689           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 690                    " Frequency  %d\n", (HOST_WIDE_INT) bb->count,
 691                    bb->frequency);
 692
 693           FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 694           {
 695             fprintf (f, "bb[%d]: Count", bb->index);
 696             fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 697                      " Frequency %d\n", (HOST_WIDE_INT) bb->count,
 698                      bb->frequency);
 699           }
 700           bb =
 701             EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 702           fprintf (f, "EXIT: Count");
 703           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 704                    " Frequency %d\n", (HOST_WIDE_INT) bb->count,
 705                    bb->frequency);
 706
 707         }
 708     }
 709 }
 710
 711 /* Print all IPCP data structures to F.  */
 712 static void
 713 ipcp_print_all_structures (FILE * f)
 714 {
 715   ipcp_print_all_lattices (f);
 716   ipcp_function_scale_print (f);
 717   ipa_print_all_tree_maps (f);
 718   ipa_print_all_param_flags (f);
 719   ipa_print_all_jump_functions (f);
 720 }
 721
 722 /* Print profile info for all functions.  */
 723 static void
 724 ipcp_print_profile_data (FILE * f)
 725 {
 726   fprintf (f, "\nNODE COUNTS :\n");
 727   ipcp_print_func_profile_counts (f);
 728   fprintf (f, "\nCS COUNTS stage:\n");
 729   ipcp_print_call_profile_counts (f);
 730   fprintf (f, "\nBB COUNTS and FREQUENCIES :\n");
 731   ipcp_print_bb_profiles (f);
 732   fprintf (f, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
 733   ipcp_print_edge_profiles (f);
 734 }
 735
 736 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
 737    processed by versioning, which operates according to the flags set.
 738    PARM_TREE is the formal parameter found to be constant.  LAT represents the
 739    constant.  */
 740 static struct ipa_replace_map *
 741 ipcp_create_replace_map (tree parm_tree, struct ipcp_lattice *lat)
 742 {
 743   struct ipa_replace_map *replace_map;
 744   tree const_val;
 745
 746   replace_map = XCNEW (struct ipa_replace_map);
 747   const_val = build_const_val (lat, TREE_TYPE (parm_tree));
 748   if (dump_file)
 749     {
 750       fprintf (dump_file, "  replacing param ");
 751       print_generic_expr (dump_file, parm_tree, 0);
 752       fprintf (dump_file, " with const ");
 753       print_generic_expr (dump_file, const_val, 0);
 754       fprintf (dump_file, "\n");
 755     }
 756   replace_map->old_tree = parm_tree;
 757   replace_map->new_tree = const_val;
 758   replace_map->replace_p = true;
 759   replace_map->ref_p = false;
 760
 761   return replace_map;
 762 }
 763
 764 /* Return true if this callsite should be redirected to the original callee
 765    (instead of the cloned one).  */
 766 static bool
 767 ipcp_need_redirect_p (struct cgraph_edge *cs)
 768 {
 769   struct ipa_node_params *orig_callee_info;
 770   int i, count;
 771   struct ipa_jump_func *jump_func;
 772   struct cgraph_node *node = cs->callee, *orig;
 773
 774   if (!flag_ipa_cp_clone)
 775     return false;
 776
 777   if ((orig = ipcp_get_orig_node (node)) != NULL)
 778     node = orig;
 779   if (ipcp_get_orig_node (cs->caller))
 780     return false;
 781
 782   orig_callee_info = IPA_NODE_REF (node);
 783   count = ipa_get_param_count (orig_callee_info);
 784   for (i = 0; i < count; i++)
 785     {
 786       struct ipcp_lattice *lat = ipcp_get_ith_lattice (orig_callee_info, i);
 787       if (ipcp_lat_is_const (lat))
 788         {
 789           jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
 790           if (jump_func->type != IPA_CONST)
 791             return true;
 792         }
 793     }
 794
 795   return false;
 796 }
 797
 798 /* Fix the callsites and the call graph after function cloning was done.  */
 799 static void
 800 ipcp_update_callgraph (void)
 801 {
 802   struct cgraph_node *node;
 803
 804   for (node = cgraph_nodes; node; node = node->next)
 805     if (node->analyzed && ipcp_node_is_clone (node))
 806       {
 807         bitmap args_to_skip = BITMAP_ALLOC (NULL);
 808         struct cgraph_node *orig_node = ipcp_get_orig_node (node);
 809         struct ipa_node_params *info = IPA_NODE_REF (orig_node);
 810         int i, count = ipa_get_param_count (info);
 811         struct cgraph_edge *cs, *next;
 812
 813         for (i = 0; i < count; i++)
 814           {
 815             struct ipcp_lattice *lat = ipcp_get_ith_lattice (info, i);
 816             tree parm_tree = ipa_get_ith_param (info, i);
 817
 818             /* We can proactively remove obviously unused arguments.  */
 819             if (is_gimple_reg (parm_tree)
 820                 && !gimple_default_def (DECL_STRUCT_FUNCTION (orig_node->decl),
 821                                         parm_tree))
 822               {
 823                 bitmap_set_bit (args_to_skip, i);
 824                 continue;
 825               }
 826
 827             if (lat->type == IPA_CONST_VALUE)
 828               bitmap_set_bit (args_to_skip, i);
 829           }
 830         for (cs = node->callers; cs; cs = next)
 831           {
 832             next = cs->next_caller;
 833             if (ipcp_node_is_clone (cs->caller) || !ipcp_need_redirect_p (cs))
 834               {
 835                 gimple new_stmt;
 836                 gimple_stmt_iterator gsi;
 837
 838                 current_function_decl = cs->caller->decl;
 839                 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
 840
 841                 new_stmt = giple_copy_call_skip_args (cs->call_stmt, args_to_skip);
 842                 gsi = gsi_for_stmt (cs->call_stmt);
 843                 gsi_replace (&gsi, new_stmt, true);
 844                 cgraph_set_call_stmt (cs, new_stmt);
 845                 pop_cfun ();
 846                 current_function_decl = NULL;
 847               }
 848             else
 849               {
 850                 cgraph_redirect_edge_callee (cs, orig_node);
 851                 gimple_call_set_fndecl (cs->call_stmt, orig_node->decl);
 852               }
 853           }
 854       }
 855 }
 856
 857 /* Update all cfg basic blocks in NODE according to SCALE.  */
 858 static void
 859 ipcp_update_bb_counts (struct cgraph_node *node, gcov_type scale)
 860 {
 861   basic_block bb;
 862
 863   FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 864     bb->count = bb->count * scale / REG_BR_PROB_BASE;
 865 }
 866
 867 /* Update all cfg edges in NODE according to SCALE.  */
 868 static void
 869 ipcp_update_edges_counts (struct cgraph_node *node, gcov_type scale)
 870 {
 871   basic_block bb;
 872   edge_iterator ei;
 873   edge e;
 874
 875   FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 876     FOR_EACH_EDGE (e, ei, bb->succs)
 877     e->count = e->count * scale / REG_BR_PROB_BASE;
 878 }
 879
 880 /* Update profiling info for versioned functions and the functions they were
 881    versioned from.  */
 882 static void
 883 ipcp_update_profiling (void)
 884 {
 885   struct cgraph_node *node, *orig_node;
 886   gcov_type scale, scale_complement;
 887   struct cgraph_edge *cs;
 888
 889   for (node = cgraph_nodes; node; node = node->next)
 890     {
 891       if (ipcp_node_is_clone (node))
 892         {
 893           orig_node = ipcp_get_orig_node (node);
 894           scale = ipcp_get_node_scale (orig_node);
 895           node->count = orig_node->count * scale / REG_BR_PROB_BASE;
 896           scale_complement = REG_BR_PROB_BASE - scale;
 897           orig_node->count =
 898             orig_node->count * scale_complement / REG_BR_PROB_BASE;
 899           for (cs = node->callees; cs; cs = cs->next_callee)
 900             cs->count = cs->count * scale / REG_BR_PROB_BASE;
 901           for (cs = orig_node->callees; cs; cs = cs->next_callee)
 902             cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
 903           ipcp_update_bb_counts (node, scale);
 904           ipcp_update_bb_counts (orig_node, scale_complement);
 905           ipcp_update_edges_counts (node, scale);
 906           ipcp_update_edges_counts (orig_node, scale_complement);
 907         }
 908     }
 909 }
 910
 911 /* Maximal count found in program.  */
 912 static gcov_type max_count;
 913 bitmap dead_nodes;
 914
 915 /* Return true if original clone needs to be preserved.  */
 916 static bool
 917 ipcp_need_original_clone_p (struct cgraph_node *node)
 918 {
 919   struct cgraph_edge *e;
 920
 921   if (node->needed)
 922     return true;
 923   for (e = node->callers; e; e = e->next_caller)
 924     if (!bitmap_bit_p (dead_nodes, e->caller->uid)
 925         && ipcp_need_redirect_p (e))
 926       return true;
 927
 928   return false;
 929 }
 930
 931 /* Estimate cost of cloning NODE.  */
 932 static long
 933 ipcp_estimate_cloning_cost (struct cgraph_node *node)
 934 {
 935   int freq_sum = 1;
 936   gcov_type count_sum = 1;
 937   struct cgraph_edge *e;
 938   int cost;
 939
 940   /* When we don't need original clone; we should always propagate.  */
 941   if (!ipcp_need_original_clone_p (node))
 942     {
 943       if (dump_file)
 944         fprintf (dump_file, "Function %s can be fully propagated\n",
 945                  cgraph_node_name (node));
 946       return 0;
 947     }
 948
 949   for (e = node->callers; e; e = e->next_caller)
 950     if (!bitmap_bit_p (dead_nodes, e->caller->uid)
 951         && !ipcp_need_redirect_p (e))
 952       {
 953         count_sum += e->count;
 954         freq_sum += e->frequency + 1;
 955       }
 956
 957   cost = node->local.inline_summary.self_insns * 1000;
 958   if (max_count)
 959     cost /= count_sum * 1000 / max_count + 1;
 960   else
 961     cost /= freq_sum * 1000 / REG_BR_PROB_BASE + 1;
 962   if (dump_file)
 963     fprintf (dump_file, "Cost of versioning %s is %i, (size: %i, freq: %i)\n",
 964              cgraph_node_name (node), cost, node->local.inline_summary.self_insns,
 965              freq_sum);
 966   return cost + 1;
 967 }
 968
 969 /* Return number of live constant parameters.  */
 970 static int
 971 ipcp_const_param_count (struct cgraph_node *node)
 972 {
 973   int const_param = 0;
 974   struct ipa_node_params *info = IPA_NODE_REF (node);
 975   int count = ipa_get_param_count (info);
 976   int i;
 977
 978   for (i = 0; i < count; i++)
 979     {
 980       struct ipcp_lattice *lat = ipcp_get_ith_lattice (info, i);
 981       tree parm_tree = ipa_get_ith_param (info, i);
 982       if (ipcp_lat_is_insertable (lat)
 983           /* Do not count obviously unused arguments.  */
 984           && (!is_gimple_reg (parm_tree)
 985               || gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
 986                                      parm_tree)))
 987         const_param++;
 988     }
 989   return const_param;
 990 }
 991
 992 /* Propagate the constant parameters found by ipcp_iterate_stage()
 993    to the function's code.  */
 994 static void
 995 ipcp_insert_stage (void)
 996 {
 997   struct cgraph_node *node, *node1 = NULL;
 998   int i;
 999   VEC (cgraph_edge_p, heap) * redirect_callers;
1000   varray_type replace_trees;
1001   struct cgraph_edge *cs;
1002   int node_callers, count;
1003   tree parm_tree;
1004   struct ipa_replace_map *replace_param;
1005   fibheap_t heap;
1006   long overall_insns = 0, new_insns = 0;
1007   long max_new_insns;
1008
1009   ipa_check_create_node_params ();
1010   ipa_check_create_edge_args ();
1011
1012   dead_nodes = BITMAP_ALLOC (NULL);
1013
1014   for (node = cgraph_nodes; node; node = node->next)
1015     if (node->analyzed)
1016       {
1017         if (node->count > max_count)
1018           max_count = node->count;
1019         overall_insns += node->local.inline_summary.self_insns;
1020       }
1021
1022   max_new_insns = overall_insns;
1023   if (max_new_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1024     max_new_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1025   max_new_insns = max_new_insns * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
1026
1027   /* First collect all functions we proved to have constant arguments to heap.  */
1028   heap = fibheap_new ();
1029   for (node = cgraph_nodes; node; node = node->next)
1030     {
1031       struct ipa_node_params *info;
1032       /* Propagation of the constant is forbidden in certain conditions.  */
1033       if (!node->analyzed || !ipcp_node_modifiable_p (node))
1034           continue;
1035       info = IPA_NODE_REF (node);
1036       if (ipa_is_called_with_var_arguments (info))
1037         continue;
1038       if (ipcp_const_param_count (node))
1039         node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node), node);
1040      }
1041
1042   /* Now clone in priority order until code size growth limits are met or
1043      heap is emptied.  */
1044   while (!fibheap_empty (heap))
1045     {
1046       struct ipa_node_params *info;
1047       int growth = 0;
1048       bitmap args_to_skip;
1049
1050       node = (struct cgraph_node *)fibheap_extract_min (heap);
1051       node->aux = NULL;
1052       if (dump_file)
1053         fprintf (dump_file, "considering function %s\n",
1054                  cgraph_node_name (node));
1055
1056       if (ipcp_need_original_clone_p (node))
1057         growth = node->local.inline_summary.self_insns;
1058       else
1059         bitmap_set_bit (dead_nodes, node->uid);
1060
1061       if (new_insns + growth > max_new_insns)
1062         break;
1063       if (growth
1064           && optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl)))
1065         {
1066           if (dump_file)
1067             fprintf (dump_file, "Not versioning, cold code would grow");
1068           continue;
1069         }
1070
1071       new_insns += growth;
1072
1073       info = IPA_NODE_REF (node);
1074       count = ipa_get_param_count (info);
1075
1076       VARRAY_GENERIC_PTR_INIT (replace_trees, ipcp_const_param_count (node),
1077                                 "replace_trees");
1078       args_to_skip = BITMAP_ALLOC (NULL);
1079       for (i = 0; i < count; i++)
1080         {
1081           struct ipcp_lattice *lat = ipcp_get_ith_lattice (info, i);
1082           parm_tree = ipa_get_ith_param (info, i);
1083
1084           /* We can proactively remove obviously unused arguments.  */
1085           if (is_gimple_reg (parm_tree)
1086               && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
1087                                       parm_tree))
1088             {
1089               bitmap_set_bit (args_to_skip, i);
1090               continue;
1091             }
1092
1093           if (lat->type == IPA_CONST_VALUE)
1094             {
1095               replace_param =
1096                 ipcp_create_replace_map (parm_tree, lat);
1097               VARRAY_PUSH_GENERIC_PTR (replace_trees, replace_param);
1098               bitmap_set_bit (args_to_skip, i);
1099             }
1100         }
1101
1102       /* Compute how many callers node has.  */
1103       node_callers = 0;
1104       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1105         node_callers++;
1106       redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers);
1107       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1108         VEC_quick_push (cgraph_edge_p, redirect_callers, cs);
1109
1110       /* Redirecting all the callers of the node to the
1111          new versioned node.  */
1112       node1 =
1113         cgraph_function_versioning (node, redirect_callers, replace_trees,
1114                                     args_to_skip);
1115       BITMAP_FREE (args_to_skip);
1116       VEC_free (cgraph_edge_p, heap, redirect_callers);
1117       VARRAY_CLEAR (replace_trees);
1118       if (node1 == NULL)
1119         continue;
1120       if (dump_file)
1121         fprintf (dump_file, "versioned function %s with growth %i, overall %i\n",
1122                  cgraph_node_name (node), (int)growth, (int)new_insns);
1123       ipcp_init_cloned_node (node, node1);
1124
1125       /* We've possibly introduced direct calls.  */
1126       ipcp_update_cloned_node (node1);
1127
1128       if (dump_file)
1129         dump_function_to_file (node1->decl, dump_file, dump_flags);
1130
1131       for (cs = node->callees; cs; cs = cs->next_callee)
1132         if (cs->callee->aux)
1133           {
1134             fibheap_delete_node (heap, (fibnode_t) cs->callee->aux);
1135             cs->callee->aux = fibheap_insert (heap,
1136                                               ipcp_estimate_cloning_cost (cs->callee),
1137                                               cs->callee);
1138           }
1139     }
1140
1141   while (!fibheap_empty (heap))
1142     {
1143       if (dump_file)
1144         fprintf (dump_file, "skipping function %s\n",
1145                  cgraph_node_name (node));
1146       node = (struct cgraph_node *) fibheap_extract_min (heap);
1147       node->aux = NULL;
1148     }
1149   fibheap_delete (heap);
1150   BITMAP_FREE (dead_nodes);
1151   ipcp_update_callgraph ();
1152   ipcp_update_profiling ();
1153 }
1154
1155 /* The IPCP driver.  */
1156 static unsigned int
1157 ipcp_driver (void)
1158 {
1159   /* 2. Do the interprocedural propagation.  */
1160   ipcp_iterate_stage ();
1161   if (dump_file)
1162     {
1163       fprintf (dump_file, "\nIPA structures after propagation:\n");
1164       ipcp_print_all_structures (dump_file);
1165       fprintf (dump_file, "\nProfiling info before insert stage:\n");
1166       ipcp_print_profile_data (dump_file);
1167     }
1168   /* 3. Insert the constants found to the functions.  */
1169   ipcp_insert_stage ();
1170   if (dump_file)
1171     {
1172       fprintf (dump_file, "\nProfiling info after insert stage:\n");
1173       ipcp_print_profile_data (dump_file);
1174     }
1175   /* Free all IPCP structures.  */
1176   free_all_ipa_structures_after_ipa_cp ();
1177   if (dump_file)
1178     fprintf (dump_file, "\nIPA constant propagation end\n");
1179   cgraph_remove_unreachable_nodes (true, NULL);
1180   return 0;
1181 }
1182
1183 /* Note function body size.  */
1184 static void
1185 ipcp_generate_summary (void)
1186 {
1187   if (dump_file)
1188     fprintf (dump_file, "\nIPA constant propagation start:\n");
1189   ipa_check_create_node_params ();
1190   ipa_check_create_edge_args ();
1191   ipa_register_cgraph_hooks ();
1192   /* 1. Call the init stage to initialize
1193      the ipa_node_params and ipa_edge_args structures.  */
1194   ipcp_init_stage ();
1195   if (dump_file)
1196     {
1197       fprintf (dump_file, "\nIPA structures before propagation:\n");
1198       ipcp_print_all_structures (dump_file);
1199     }
1200 }
1201
1202 /* Gate for IPCP optimization.  */
1203 static bool
1204 cgraph_gate_cp (void)
1205 {
1206   return flag_ipa_cp;
1207 }
1208
1209 struct ipa_opt_pass pass_ipa_cp =
1210 {
1211  {
1212   IPA_PASS,
1213   "cp",                         /* name */
1214   cgraph_gate_cp,               /* gate */
1215   ipcp_driver,                  /* execute */
1216   NULL,                         /* sub */
1217   NULL,                         /* next */
1218   0,                            /* static_pass_number */
1219   TV_IPA_CONSTANT_PROP,         /* tv_id */
1220   0,                            /* properties_required */
1221   PROP_trees,                   /* properties_provided */
1222   0,                            /* properties_destroyed */
1223   0,                            /* todo_flags_start */
1224   TODO_dump_cgraph | TODO_dump_func     /* todo_flags_finish */
1225  },
1226  ipcp_generate_summary,                 /* generate_summary */
1227  NULL,                                  /* write_summary */
1228  NULL,                                  /* read_summary */
1229  NULL,                                  /* function_read_summary */
1230  0,                                     /* TODOs */
1231  NULL,                                  /* function_transform */
1232  NULL,                                  /* variable_transform */
1233 };