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