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