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