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
 136 /* Get the original node field of ipa_node_params associated with node NODE.  */
 137 static inline struct cgraph_node *
 138 ipcp_get_orig_node (struct cgraph_node *node)
 139 {
 140   return IPA_NODE_REF (node)->ipcp_orig_node;
 141 }
 142
 143 /* Return true if NODE describes a cloned/versioned function.  */
 144 static inline bool
 145 ipcp_node_is_clone (struct cgraph_node *node)
 146 {
 147   return (ipcp_get_orig_node (node) != NULL);
 148 }
 149
 150 /* Create ipa_node_params and its data structures for NEW_NODE.  Set ORIG_NODE
 151    as the ipcp_orig_node field in ipa_node_params.  */
 152 static void
 153 ipcp_init_cloned_node (struct cgraph_node *orig_node,
 154                        struct cgraph_node *new_node)
 155 {
 156   ipa_check_create_node_params ();
 157   IPA_NODE_REF (new_node)->ipcp_orig_node = orig_node;
 158   ipa_count_formal_params (new_node);
 159   ipa_create_param_decls_array (new_node);
 160 }
 161
 162 /* Perform intraprocedrual analysis needed for ipcp.  */
 163 static void
 164 ipcp_analyze_node (struct cgraph_node *node)
 165 {
 166   /* Unreachable nodes should have been eliminated before ipcp.  */
 167   gcc_assert (node->needed || node->reachable);
 168
 169   ipa_count_formal_params (node);
 170   ipa_create_param_decls_array (node);
 171   ipa_detect_param_modifications (node);
 172 }
 173
 174 /* Recompute all local information since node might've got new
 175    direct calls after clonning.  */
 176 static void
 177 ipcp_update_cloned_node (struct cgraph_node *new_node)
 178 {
 179   /* We might've introduced new direct calls.  */
 180   push_cfun (DECL_STRUCT_FUNCTION (new_node->decl));
 181   current_function_decl = new_node->decl;
 182   rebuild_cgraph_edges ();
 183
 184   /* Indirect inlinng rely on fact that we've already analyzed
 185      the body..  */
 186   if (flag_indirect_inlining)
 187     {
 188       struct cgraph_edge *cs;
 189
 190       ipcp_analyze_node (new_node);
 191
 192       for (cs = new_node->callees; cs; cs = cs->next_callee)
 193         {
 194           ipa_count_arguments (cs);
 195           ipa_compute_jump_functions (cs);
 196         }
 197     }
 198   pop_cfun ();
 199   current_function_decl = NULL;
 200 }
 201
 202 /* Return scale for NODE.  */
 203 static inline gcov_type
 204 ipcp_get_node_scale (struct cgraph_node *node)
 205 {
 206   return IPA_NODE_REF (node)->count_scale;
 207 }
 208
 209 /* Set COUNT as scale for NODE.  */
 210 static inline void
 211 ipcp_set_node_scale (struct cgraph_node *node, gcov_type count)
 212 {
 213   IPA_NODE_REF (node)->count_scale = count;
 214 }
 215
 216 /* Return whether LAT is a constant lattice.  */
 217 static inline bool
 218 ipcp_lat_is_const (struct ipcp_lattice *lat)
 219 {
 220   if (lat->type == IPA_CONST_VALUE)
 221     return true;
 222   else
 223     return false;
 224 }
 225
 226 /* Return whether LAT is a constant lattice that ipa-cp can actually insert
 227    into the code (i.e. constants excluding member pointers and pointers).  */
 228 static inline bool
 229 ipcp_lat_is_insertable (struct ipcp_lattice *lat)
 230 {
 231   return lat->type == IPA_CONST_VALUE;
 232 }
 233
 234 /* Return true if LAT1 and LAT2 are equal.  */
 235 static inline bool
 236 ipcp_lats_are_equal (struct ipcp_lattice *lat1, struct ipcp_lattice *lat2)
 237 {
 238   gcc_assert (ipcp_lat_is_const (lat1) && ipcp_lat_is_const (lat2));
 239   if (lat1->type != lat2->type)
 240     return false;
 241
 242   if (operand_equal_p (lat1->constant, lat2->constant, 0))
 243     return true;
 244
 245   return false;
 246 }
 247
 248 /* Compute Meet arithmetics:
 249    Meet (IPA_BOTTOM, x) = IPA_BOTTOM
 250    Meet (IPA_TOP,x) = x
 251    Meet (const_a,const_b) = IPA_BOTTOM,  if const_a != const_b.
 252    MEET (const_a,const_b) = const_a, if const_a == const_b.*/
 253 static void
 254 ipa_lattice_meet (struct ipcp_lattice *res, struct ipcp_lattice *lat1,
 255                   struct ipcp_lattice *lat2)
 256 {
 257   if (lat1->type == IPA_BOTTOM || lat2->type == IPA_BOTTOM)
 258     {
 259       res->type = IPA_BOTTOM;
 260       return;
 261     }
 262   if (lat1->type == IPA_TOP)
 263     {
 264       res->type = lat2->type;
 265       res->constant = lat2->constant;
 266       return;
 267     }
 268   if (lat2->type == IPA_TOP)
 269     {
 270       res->type = lat1->type;
 271       res->constant = lat1->constant;
 272       return;
 273     }
 274   if (!ipcp_lats_are_equal (lat1, lat2))
 275     {
 276       res->type = IPA_BOTTOM;
 277       return;
 278     }
 279   res->type = lat1->type;
 280   res->constant = lat1->constant;
 281 }
 282
 283 /* Return the lattice corresponding to the Ith formal parameter of the function
 284    described by INFO.  */
 285 static inline struct ipcp_lattice *
 286 ipcp_get_ith_lattice (struct ipa_node_params *info, int i)
 287 {
 288   return &(info->ipcp_lattices[i]);
 289 }
 290
 291 /* Given the jump function JFUNC, compute the lattice LAT that describes the
 292    value coming down the callsite. INFO describes the caller node so that
 293    pass-through jump functions can be evaluated.  */
 294 static void
 295 ipcp_lattice_from_jfunc (struct ipa_node_params *info, struct ipcp_lattice *lat,
 296                          struct ipa_jump_func *jfunc)
 297 {
 298   if (jfunc->type == IPA_CONST)
 299     {
 300       lat->type = IPA_CONST_VALUE;
 301       lat->constant = jfunc->value.constant;
 302     }
 303   else if (jfunc->type == IPA_PASS_THROUGH)
 304     {
 305       struct ipcp_lattice *caller_lat;
 306
 307       caller_lat = ipcp_get_ith_lattice (info, jfunc->value.formal_id);
 308       lat->type = caller_lat->type;
 309       lat->constant = caller_lat->constant;
 310     }
 311   else
 312     lat->type = IPA_BOTTOM;
 313 }
 314
 315 /* True when OLD_LAT and NEW_LAT values are not the same.  */
 316
 317 static bool
 318 ipcp_lattice_changed (struct ipcp_lattice *old_lat,
 319                       struct ipcp_lattice *new_lat)
 320 {
 321   if (old_lat->type == new_lat->type)
 322     {
 323       if (!ipcp_lat_is_const (old_lat))
 324         return false;
 325       if (ipcp_lats_are_equal (old_lat, new_lat))
 326         return false;
 327     }
 328   return true;
 329 }
 330
 331 /* Print all ipcp_lattices of all functions to F.  */
 332 static void
 333 ipcp_print_all_lattices (FILE * f)
 334 {
 335   struct cgraph_node *node;
 336   int i, count;
 337
 338   fprintf (f, "\nLATTICE PRINT\n");
 339   for (node = cgraph_nodes; node; node = node->next)
 340     {
 341       struct ipa_node_params *info;
 342
 343       if (!node->analyzed)
 344         continue;
 345       info = IPA_NODE_REF (node);
 346       fprintf (f, "Printing lattices %s:\n", cgraph_node_name (node));
 347       count = ipa_get_param_count (info);
 348       for (i = 0; i < count; i++)
 349         {
 350           struct ipcp_lattice *lat = ipcp_get_ith_lattice (info, i);
 351
 352           fprintf (f, " param [%d]: ", i);
 353           if (lat->type == IPA_CONST_VALUE)
 354             {
 355               fprintf (f, "type is CONST ");
 356               print_generic_expr (f, lat->constant, 0);
 357               fprintf (f, "\n");
 358             }
 359           else if (lat->type == IPA_TOP)
 360             fprintf (f, "type is TOP\n");
 361           else
 362             fprintf (f, "type is BOTTOM\n");
 363         }
 364     }
 365 }
 366
 367 /* Initialize ipcp_lattices array.  The lattices corresponding to supported
 368    types (integers, real types and Fortran constants defined as const_decls)
 369    are initialized to IPA_TOP, the rest of them to IPA_BOTTOM.  */
 370 static void
 371 ipcp_initialize_node_lattices (struct cgraph_node *node)
 372 {
 373   int i;
 374   struct ipa_node_params *info = IPA_NODE_REF (node);
 375
 376   info->ipcp_lattices = XCNEWVEC (struct ipcp_lattice,
 377                                   ipa_get_param_count (info));
 378   for (i = 0; i < ipa_get_param_count (info) ; i++)
 379     ipcp_get_ith_lattice (info, i)->type = IPA_TOP;
 380 }
 381
 382 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
 383    Return the tree.  */
 384 static tree
 385 build_const_val (struct ipcp_lattice *lat, tree tree_type)
 386 {
 387   tree val;
 388
 389   gcc_assert (ipcp_lat_is_const (lat));
 390   val = lat->constant;
 391
 392   if (!useless_type_conversion_p (tree_type, TREE_TYPE (val)))
 393     {
 394       if (fold_convertible_p (tree_type, val))
 395         return fold_build1 (NOP_EXPR, tree_type, val);
 396       else
 397         return fold_build1 (VIEW_CONVERT_EXPR, tree_type, val);
 398     }
 399   return val;
 400 }
 401
 402 /* Compute the proper scale for NODE.  It is the ratio between the number of
 403    direct calls (represented on the incoming cgraph_edges) and sum of all
 404    invocations of NODE (represented as count in cgraph_node).  */
 405 static void
 406 ipcp_compute_node_scale (struct cgraph_node *node)
 407 {
 408   gcov_type sum;
 409   struct cgraph_edge *cs;
 410
 411   sum = 0;
 412   /* Compute sum of all counts of callers. */
 413   for (cs = node->callers; cs != NULL; cs = cs->next_caller)
 414     sum += cs->count;
 415   if (node->count == 0)
 416     ipcp_set_node_scale (node, 0);
 417   else
 418     ipcp_set_node_scale (node, sum * REG_BR_PROB_BASE / node->count);
 419 }
 420
 421 /* Initialization and computation of IPCP data structures.  This is the initial
 422    intraprocedural analysis of functions, which gathers information to be
 423    propagated later on.  */
 424 static void
 425 ipcp_init_stage (void)
 426 {
 427   struct cgraph_node *node;
 428   struct cgraph_edge *cs;
 429
 430   for (node = cgraph_nodes; node; node = node->next)
 431     if (node->analyzed)
 432       {
 433         ipcp_analyze_node (node);
 434         ipcp_initialize_node_lattices (node);
 435         ipcp_compute_node_scale (node);
 436       }
 437   for (node = cgraph_nodes; node; node = node->next)
 438     {
 439       if (!node->analyzed)
 440         continue;
 441       /* building jump functions  */
 442       for (cs = node->callees; cs; cs = cs->next_callee)
 443         {
 444           if (!cs->callee->analyzed)
 445             continue;
 446           ipa_count_arguments (cs);
 447           if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
 448               != ipa_get_param_count (IPA_NODE_REF (cs->callee)))
 449             {
 450               /* Handle cases of functions with
 451                  a variable number of parameters.  */
 452               ipa_set_called_with_variable_arg (IPA_NODE_REF (cs->callee));
 453               if (flag_indirect_inlining)
 454                 ipa_compute_jump_functions (cs);
 455             }
 456           else
 457             ipa_compute_jump_functions (cs);
 458         }
 459     }
 460 }
 461
 462 /* Return true if there are some formal parameters whose value is IPA_TOP (in
 463    the whole compilation unit).  Change their values to IPA_BOTTOM, since they
 464    most probably get their values from outside of this compilation unit.  */
 465 static bool
 466 ipcp_change_tops_to_bottom (void)
 467 {
 468   int i, count;
 469   struct cgraph_node *node;
 470   bool prop_again;
 471
 472   prop_again = false;
 473   for (node = cgraph_nodes; node; node = node->next)
 474     {
 475       struct ipa_node_params *info = IPA_NODE_REF (node);
 476       count = ipa_get_param_count (info);
 477       for (i = 0; i < count; i++)
 478         {
 479           struct ipcp_lattice *lat = ipcp_get_ith_lattice (info, i);
 480           if (lat->type == IPA_TOP)
 481             {
 482               prop_again = true;
 483               lat->type = IPA_BOTTOM;
 484             }
 485         }
 486     }
 487   return prop_again;
 488 }
 489
 490 /* Interprocedural analysis. The algorithm propagates constants from the
 491    caller's parameters to the callee's arguments.  */
 492 static void
 493 ipcp_propagate_stage (void)
 494 {
 495   int i;
 496   struct ipcp_lattice inc_lat = { IPA_BOTTOM, NULL };
 497   struct ipcp_lattice new_lat = { IPA_BOTTOM, NULL };
 498   struct ipcp_lattice *dest_lat;
 499   struct cgraph_edge *cs;
 500   struct ipa_jump_func *jump_func;
 501   struct ipa_func_list *wl;
 502   int count;
 503
 504   ipa_check_create_node_params ();
 505   ipa_check_create_edge_args ();
 506   /* Initialize worklist to contain all functions.  */
 507   wl = ipa_init_func_list ();
 508   while (wl)
 509     {
 510       struct cgraph_node *node = ipa_pop_func_from_list (&wl);
 511       struct ipa_node_params *info = IPA_NODE_REF (node);
 512
 513       for (cs = node->callees; cs; cs = cs->next_callee)
 514         {
 515           struct ipa_node_params *callee_info = IPA_NODE_REF (cs->callee);
 516           struct ipa_edge_args *args = IPA_EDGE_REF (cs);
 517
 518           if (ipa_is_called_with_var_arguments (callee_info))
 519             continue;
 520
 521           count = ipa_get_cs_argument_count (args);
 522           for (i = 0; i < count; i++)
 523             {
 524               jump_func = ipa_get_ith_jump_func (args, i);
 525               ipcp_lattice_from_jfunc (info, &inc_lat, jump_func);
 526               dest_lat = ipcp_get_ith_lattice (callee_info, i);
 527               ipa_lattice_meet (&new_lat, &inc_lat, dest_lat);
 528               if (ipcp_lattice_changed (&new_lat, dest_lat))
 529                 {
 530                   dest_lat->type = new_lat.type;
 531                   dest_lat->constant = new_lat.constant;
 532                   ipa_push_func_to_list (&wl, cs->callee);
 533                 }
 534             }
 535         }
 536     }
 537 }
 538
 539 /* Call the constant propagation algorithm and re-call it if necessary
 540    (if there are undetermined values left).  */
 541 static void
 542 ipcp_iterate_stage (void)
 543 {
 544   ipcp_propagate_stage ();
 545   if (ipcp_change_tops_to_bottom ())
 546     /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
 547        This change should be propagated.  */
 548     ipcp_propagate_stage ();
 549 }
 550
 551 /* Check conditions to forbid constant insertion to function described by
 552    NODE.  */
 553 static inline bool
 554 ipcp_node_not_modifiable_p (struct cgraph_node *node)
 555 {
 556   /* ??? Handle pending sizes case.  */
 557   if (DECL_UNINLINABLE (node->decl))
 558     return true;
 559   return false;
 560 }
 561
 562 /* Print count scale data structures.  */
 563 static void
 564 ipcp_function_scale_print (FILE * f)
 565 {
 566   struct cgraph_node *node;
 567
 568   for (node = cgraph_nodes; node; node = node->next)
 569     {
 570       if (!node->analyzed)
 571         continue;
 572       fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
 573       fprintf (f, "value is  " HOST_WIDE_INT_PRINT_DEC
 574                "  \n", (HOST_WIDE_INT) ipcp_get_node_scale (node));
 575     }
 576 }
 577
 578 /* Print counts of all cgraph nodes.  */
 579 static void
 580 ipcp_print_func_profile_counts (FILE * f)
 581 {
 582   struct cgraph_node *node;
 583
 584   for (node = cgraph_nodes; node; node = node->next)
 585     {
 586       fprintf (f, "function %s: ", cgraph_node_name (node));
 587       fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC
 588                "  \n", (HOST_WIDE_INT) node->count);
 589     }
 590 }
 591
 592 /* Print counts of all cgraph edges.  */
 593 static void
 594 ipcp_print_call_profile_counts (FILE * f)
 595 {
 596   struct cgraph_node *node;
 597   struct cgraph_edge *cs;
 598
 599   for (node = cgraph_nodes; node; node = node->next)
 600     {
 601       for (cs = node->callees; cs; cs = cs->next_callee)
 602         {
 603           fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
 604                    cgraph_node_name (cs->callee));
 605           fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC "  \n",
 606                    (HOST_WIDE_INT) cs->count);
 607         }
 608     }
 609 }
 610
 611 /* Print all counts and probabilities of cfg edges of all functions.  */
 612 static void
 613 ipcp_print_edge_profiles (FILE * f)
 614 {
 615   struct cgraph_node *node;
 616   basic_block bb;
 617   edge_iterator ei;
 618   edge e;
 619
 620   for (node = cgraph_nodes; node; node = node->next)
 621     {
 622       fprintf (f, "function %s: \n", cgraph_node_name (node));
 623       if (node->analyzed)
 624         {
 625           bb =
 626             ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 627           fprintf (f, "ENTRY: ");
 628           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 629                    " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
 630
 631           if (bb->succs)
 632             FOR_EACH_EDGE (e, ei, bb->succs)
 633             {
 634               if (e->dest ==
 635                   EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
 636                                                (node->decl)))
 637                 fprintf (f, "edge ENTRY -> EXIT,  Count");
 638               else
 639                 fprintf (f, "edge ENTRY -> %d,  Count", e->dest->index);
 640               fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 641                        " Prob %d\n", (HOST_WIDE_INT) e->count,
 642                        e->probability);
 643             }
 644           FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 645           {
 646             fprintf (f, "bb[%d]: ", bb->index);
 647             fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 648                      " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
 649             FOR_EACH_EDGE (e, ei, bb->succs)
 650             {
 651               if (e->dest ==
 652                   EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
 653                                                (node->decl)))
 654                 fprintf (f, "edge %d -> EXIT,  Count", e->src->index);
 655               else
 656                 fprintf (f, "edge %d -> %d,  Count", e->src->index,
 657                          e->dest->index);
 658               fprintf (f, " " HOST_WIDE_INT_PRINT_DEC " Prob %d\n",
 659                        (HOST_WIDE_INT) e->count, e->probability);
 660             }
 661           }
 662         }
 663     }
 664 }
 665
 666 /* Print counts and frequencies for all basic blocks of all functions.  */
 667 static void
 668 ipcp_print_bb_profiles (FILE * f)
 669 {
 670   basic_block bb;
 671   struct cgraph_node *node;
 672
 673   for (node = cgraph_nodes; node; node = node->next)
 674     {
 675       fprintf (f, "function %s: \n", cgraph_node_name (node));
 676       if (node->analyzed)
 677         {
 678           bb =
 679             ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 680           fprintf (f, "ENTRY: Count");
 681           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 682                    " Frequency  %d\n", (HOST_WIDE_INT) bb->count,
 683                    bb->frequency);
 684
 685           FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 686           {
 687             fprintf (f, "bb[%d]: Count", bb->index);
 688             fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 689                      " Frequency %d\n", (HOST_WIDE_INT) bb->count,
 690                      bb->frequency);
 691           }
 692           bb =
 693             EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 694           fprintf (f, "EXIT: Count");
 695           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 696                    " Frequency %d\n", (HOST_WIDE_INT) bb->count,
 697                    bb->frequency);
 698
 699         }
 700     }
 701 }
 702
 703 /* Print all IPCP data structures to F.  */
 704 static void
 705 ipcp_print_all_structures (FILE * f)
 706 {
 707   ipcp_print_all_lattices (f);
 708   ipcp_function_scale_print (f);
 709   ipa_print_all_tree_maps (f);
 710   ipa_print_all_param_flags (f);
 711   ipa_print_all_jump_functions (f);
 712 }
 713
 714 /* Print profile info for all functions.  */
 715 static void
 716 ipcp_print_profile_data (FILE * f)
 717 {
 718   fprintf (f, "\nNODE COUNTS :\n");
 719   ipcp_print_func_profile_counts (f);
 720   fprintf (f, "\nCS COUNTS stage:\n");
 721   ipcp_print_call_profile_counts (f);
 722   fprintf (f, "\nBB COUNTS and FREQUENCIES :\n");
 723   ipcp_print_bb_profiles (f);
 724   fprintf (f, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
 725   ipcp_print_edge_profiles (f);
 726 }
 727
 728 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
 729    processed by versioning, which operates according to the flags set.
 730    PARM_TREE is the formal parameter found to be constant.  LAT represents the
 731    constant.  */
 732 static struct ipa_replace_map *
 733 ipcp_create_replace_map (tree parm_tree, struct ipcp_lattice *lat)
 734 {
 735   struct ipa_replace_map *replace_map;
 736   tree const_val;
 737
 738   replace_map = XCNEW (struct ipa_replace_map);
 739   if (dump_file)
 740     fprintf (dump_file, "replacing param with const\n");
 741   const_val = build_const_val (lat, TREE_TYPE (parm_tree));
 742   replace_map->old_tree = parm_tree;
 743   replace_map->new_tree = const_val;
 744   replace_map->replace_p = true;
 745   replace_map->ref_p = false;
 746
 747   return replace_map;
 748 }
 749
 750 /* Return true if this callsite should be redirected to the original callee
 751    (instead of the cloned one).  */
 752 static bool
 753 ipcp_need_redirect_p (struct cgraph_edge *cs)
 754 {
 755   struct ipa_node_params *orig_callee_info;
 756   int i, count;
 757   struct ipa_jump_func *jump_func;
 758
 759   orig_callee_info = IPA_NODE_REF (ipcp_get_orig_node (cs->callee));
 760   count = ipa_get_param_count (orig_callee_info);
 761   for (i = 0; i < count; i++)
 762     {
 763       struct ipcp_lattice *lat = ipcp_get_ith_lattice (orig_callee_info, i);
 764       if (ipcp_lat_is_const (lat))
 765         {
 766           jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
 767           if (jump_func->type != IPA_CONST)
 768             return true;
 769         }
 770     }
 771
 772   return false;
 773 }
 774
 775 /* Fix the callsites and the call graph after function cloning was done.  */
 776 static void
 777 ipcp_update_callgraph (void)
 778 {
 779   struct cgraph_node *node, *orig_callee;
 780   struct cgraph_edge *cs;
 781
 782   for (node = cgraph_nodes; node; node = node->next)
 783     {
 784       /* want to fix only original nodes  */
 785       if (!node->analyzed || ipcp_node_is_clone (node))
 786         continue;
 787       for (cs = node->callees; cs; cs = cs->next_callee)
 788         if (ipcp_node_is_clone (cs->callee))
 789           {
 790             /* Callee is a cloned node  */
 791             orig_callee = ipcp_get_orig_node (cs->callee);
 792             if (ipcp_need_redirect_p (cs))
 793               {
 794                 cgraph_redirect_edge_callee (cs, orig_callee);
 795                 gimple_call_set_fndecl (cs->call_stmt, orig_callee->decl);
 796               }
 797           }
 798     }
 799 }
 800
 801 /* Update all cfg basic blocks in NODE according to SCALE.  */
 802 static void
 803 ipcp_update_bb_counts (struct cgraph_node *node, gcov_type scale)
 804 {
 805   basic_block bb;
 806
 807   FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 808     bb->count = bb->count * scale / REG_BR_PROB_BASE;
 809 }
 810
 811 /* Update all cfg edges in NODE according to SCALE.  */
 812 static void
 813 ipcp_update_edges_counts (struct cgraph_node *node, gcov_type scale)
 814 {
 815   basic_block bb;
 816   edge_iterator ei;
 817   edge e;
 818
 819   FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 820     FOR_EACH_EDGE (e, ei, bb->succs)
 821     e->count = e->count * scale / REG_BR_PROB_BASE;
 822 }
 823
 824 /* Update profiling info for versioned functions and the functions they were
 825    versioned from.  */
 826 static void
 827 ipcp_update_profiling (void)
 828 {
 829   struct cgraph_node *node, *orig_node;
 830   gcov_type scale, scale_complement;
 831   struct cgraph_edge *cs;
 832
 833   for (node = cgraph_nodes; node; node = node->next)
 834     {
 835       if (ipcp_node_is_clone (node))
 836         {
 837           orig_node = ipcp_get_orig_node (node);
 838           scale = ipcp_get_node_scale (orig_node);
 839           node->count = orig_node->count * scale / REG_BR_PROB_BASE;
 840           scale_complement = REG_BR_PROB_BASE - scale;
 841           orig_node->count =
 842             orig_node->count * scale_complement / REG_BR_PROB_BASE;
 843           for (cs = node->callees; cs; cs = cs->next_callee)
 844             cs->count = cs->count * scale / REG_BR_PROB_BASE;
 845           for (cs = orig_node->callees; cs; cs = cs->next_callee)
 846             cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
 847           ipcp_update_bb_counts (node, scale);
 848           ipcp_update_bb_counts (orig_node, scale_complement);
 849           ipcp_update_edges_counts (node, scale);
 850           ipcp_update_edges_counts (orig_node, scale_complement);
 851         }
 852     }
 853 }
 854
 855 /* Propagate the constant parameters found by ipcp_iterate_stage()
 856    to the function's code.  */
 857 static void
 858 ipcp_insert_stage (void)
 859 {
 860   struct cgraph_node *node, *node1 = NULL;
 861   int i, const_param;
 862   VEC (cgraph_edge_p, heap) * redirect_callers;
 863   varray_type replace_trees;
 864   struct cgraph_edge *cs;
 865   int node_callers, count;
 866   tree parm_tree;
 867   struct ipa_replace_map *replace_param;
 868
 869   ipa_check_create_node_params ();
 870   ipa_check_create_edge_args ();
 871
 872   for (node = cgraph_nodes; node; node = node->next)
 873     {
 874       struct ipa_node_params *info;
 875       /* Propagation of the constant is forbidden in certain conditions.  */
 876       if (!node->analyzed || ipcp_node_not_modifiable_p (node))
 877           continue;
 878       info = IPA_NODE_REF (node);
 879       if (ipa_is_called_with_var_arguments (info))
 880         continue;
 881       const_param = 0;
 882       count = ipa_get_param_count (info);
 883       for (i = 0; i < count; i++)
 884         {
 885           struct ipcp_lattice *lat = ipcp_get_ith_lattice (info, i);
 886           tree parm_tree = ipa_get_ith_param (info, i);
 887           if (ipcp_lat_is_insertable (lat)
 888               /* Do not count obviously unused arguments.  */
 889               && (!is_gimple_reg (parm_tree)
 890                   || gimple_default_def (DECL_STRUCT_FUNCTION (node->decl), parm_tree)))
 891             const_param++;
 892         }
 893       if (const_param == 0)
 894         continue;
 895       VARRAY_GENERIC_PTR_INIT (replace_trees, const_param, "replace_trees");
 896       for (i = 0; i < count; i++)
 897         {
 898           struct ipcp_lattice *lat = ipcp_get_ith_lattice (info, i);
 899           if (lat->type == IPA_CONST_VALUE)
 900             {
 901               parm_tree = ipa_get_ith_param (info, i);
 902               replace_param =
 903                 ipcp_create_replace_map (parm_tree, lat);
 904               VARRAY_PUSH_GENERIC_PTR (replace_trees, replace_param);
 905             }
 906         }
 907       /* Compute how many callers node has.  */
 908       node_callers = 0;
 909       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
 910         node_callers++;
 911       redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers);
 912       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
 913         VEC_quick_push (cgraph_edge_p, redirect_callers, cs);
 914       /* Redirecting all the callers of the node to the
 915          new versioned node.  */
 916       node1 =
 917         cgraph_function_versioning (node, redirect_callers, replace_trees);
 918       VEC_free (cgraph_edge_p, heap, redirect_callers);
 919       VARRAY_CLEAR (replace_trees);
 920       if (node1 == NULL)
 921         continue;
 922       if (dump_file)
 923         fprintf (dump_file, "versioned function %s\n",
 924                  cgraph_node_name (node));
 925       ipcp_init_cloned_node (node, node1);
 926       /* We've possibly introduced direct calls.  */
 927       ipcp_update_cloned_node (node1);
 928
 929       if (dump_file)
 930         dump_function_to_file (node1->decl, dump_file, dump_flags);
 931     }
 932   ipcp_update_callgraph ();
 933   ipcp_update_profiling ();
 934 }
 935
 936 /* The IPCP driver.  */
 937 static unsigned int
 938 ipcp_driver (void)
 939 {
 940   /* 2. Do the interprocedural propagation.  */
 941   ipcp_iterate_stage ();
 942   if (dump_file)
 943     {
 944       fprintf (dump_file, "\nIPA structures after propagation:\n");
 945       ipcp_print_all_structures (dump_file);
 946       fprintf (dump_file, "\nProfiling info before insert stage:\n");
 947       ipcp_print_profile_data (dump_file);
 948     }
 949   /* 3. Insert the constants found to the functions.  */
 950   ipcp_insert_stage ();
 951   if (dump_file)
 952     {
 953       fprintf (dump_file, "\nProfiling info after insert stage:\n");
 954       ipcp_print_profile_data (dump_file);
 955     }
 956   /* Free all IPCP structures.  */
 957   free_all_ipa_structures_after_ipa_cp ();
 958   if (dump_file)
 959     fprintf (dump_file, "\nIPA constant propagation end\n");
 960   cgraph_remove_unreachable_nodes (true, NULL);
 961   return 0;
 962 }
 963
 964 /* Note function body size.  */
 965 static void
 966 ipcp_generate_summary (void)
 967 {
 968   if (dump_file)
 969     fprintf (dump_file, "\nIPA constant propagation start:\n");
 970   ipa_check_create_node_params ();
 971   ipa_check_create_edge_args ();
 972   ipa_register_cgraph_hooks ();
 973   /* 1. Call the init stage to initialize
 974      the ipa_node_params and ipa_edge_args structures.  */
 975   ipcp_init_stage ();
 976   if (dump_file)
 977     {
 978       fprintf (dump_file, "\nIPA structures before propagation:\n");
 979       ipcp_print_all_structures (dump_file);
 980     }
 981 }
 982
 983 /* Gate for IPCP optimization.  */
 984 static bool
 985 cgraph_gate_cp (void)
 986 {
 987   return flag_ipa_cp;
 988 }
 989
 990 struct ipa_opt_pass pass_ipa_cp =
 991 {
 992  {
 993   IPA_PASS,
 994   "cp",                         /* name */
 995   cgraph_gate_cp,               /* gate */
 996   ipcp_driver,                  /* execute */
 997   NULL,                         /* sub */
 998   NULL,                         /* next */
 999   0,                            /* static_pass_number */
1000   TV_IPA_CONSTANT_PROP,         /* tv_id */
1001   0,                            /* properties_required */
1002   PROP_trees,                   /* properties_provided */
1003   0,                            /* properties_destroyed */
1004   0,                            /* todo_flags_start */
1005   TODO_dump_cgraph | TODO_dump_func     /* todo_flags_finish */
1006  },
1007  ipcp_generate_summary,                 /* generate_summary */
1008  NULL,                                  /* write_summary */
1009  NULL,                                  /* read_summary */
1010  NULL,                                  /* function_read_summary */
1011  0,                                     /* TODOs */
1012  NULL,                                  /* function_transform */
1013  NULL,                                  /* variable_transform */
1014 };