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