gcc/ipa-cp.c

   1 /* Interprocedural constant propagation
   2    Copyright (C) 2005 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 2, 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 COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22 /* Interprocedural constant propagation.
  23    The aim of interprocedural constant propagation (IPCP) is to find which
  24    function's argument has the same constant value in each invocation throughout
  25    the whole program. For example, for an application consisting of two files,
  26    foo1.c, foo2.c:
  27
  28    foo1.c contains :
  29
  30    int f (int x)
  31    {
  32      g (x);
  33    }
  34    void main (void)
  35    {
  36      f (3);
  37      h (3);
  38    }
  39
  40    foo2.c contains :
  41
  42    int h (int y)
  43    {
  44      g (y);
  45    }
  46    int g (int y)
  47    {
  48      printf ("value is %d",y);
  49    }
  50
  51    The IPCP algorithm will find that g's formal argument y
  52    is always called with the value 3.
  53
  54    The algorithm used is based on "Interprocedural Constant Propagation",
  55    by Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86,
  56    pg 152-161
  57
  58    The optimization is divided into three stages:
  59
  60    First stage - intraprocedural analysis
  61    =======================================
  62    This phase computes jump_function and modify information.
  63
  64    A jump function for a callsite represents the values passed as actual
  65    arguments
  66    of the callsite. There are three types of values :
  67    Formal - the caller's formal parameter is passed as an actual argument.
  68    Constant - a constant is passed as a an actual argument.
  69    Unknown - neither of the above.
  70
  71    In order to compute the jump functions, we need the modify information for
  72    the formal parameters of methods.
  73
  74    The jump function info, ipa_jump_func, is defined in ipa_edge
  75    structure (defined in ipa_prop.h and pointed to by cgraph_node->aux)
  76    The modify info, ipa_modify, is defined in ipa_node structure
  77    (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
  78
  79    -ipcp_init_stage() is the first stage driver.
  80
  81    Second stage - interprocedural analysis
  82    ========================================
  83    This phase does the interprocedural constant propagation.
  84    It computes for all formal parameters in the program
  85    their cval value that may be:
  86    TOP - unknown.
  87    BOTTOM - non constant.
  88    CONSTANT_TYPE - constant value.
  89
  90    Cval of formal f will have a constant value if all callsites to this
  91    function have the same constant value passed to f.
  92
  93    The cval info, ipcp_formal, is defined in ipa_node structure
  94    (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
  95
  96    -ipcp_iterate_stage() is the second stage driver.
  97
  98    Third phase - transformation of methods code
  99    ============================================
 100    Propagates the constant-valued formals into the function.
 101    For each method mt, whose parameters are consts, we create a clone/version.
 102
 103    We use two ways to annotate the versioned function with the constant
 104    formal information:
 105    1. We insert an assignment statement 'parameter = const' at the beginning
 106    of the cloned method.
 107    2. For read-only formals whose address is not taken, we replace all uses
 108    of the formal with the constant (we provide versioning with an
 109    ipa_replace_map struct representing the trees we want to replace).
 110
 111    We also need to modify some callsites to call to the cloned methods instead
 112    of the original ones. For a callsite passing an argument found to be a
 113    constant by IPCP, there are two different cases to handle:
 114    1. A constant is passed as an argument.
 115    2. A parameter (of the caller) passed as an argument (pass through argument).
 116
 117    In the first case, the callsite in the original caller should be redirected
 118    to call the cloned callee.
 119    In the second case, both the caller and the callee have clones
 120    and the callsite of the cloned caller would be redirected to call to
 121    the cloned callee.
 122
 123    The callgraph is updated accordingly.
 124
 125    This update is done in two stages:
 126    First all cloned methods are created during a traversal of the callgraph,
 127    during which all callsites are redirected to call the cloned method.
 128    Then the callsites are traversed and updated as described above.
 129
 130    -ipcp_insert_stage() is the third phase driver.
 131
 132 */
 133
 134 #include "config.h"
 135 #include "system.h"
 136 #include "coretypes.h"
 137 #include "tree.h"
 138 #include "target.h"
 139 #include "cgraph.h"
 140 #include "ipa-prop.h"
 141 #include "tree-flow.h"
 142 #include "tree-pass.h"
 143 #include "flags.h"
 144 #include "timevar.h"
 145 #include "diagnostic.h"
 146
 147 /* Get orig node field of ipa_node associated with method MT.  */
 148 static inline struct cgraph_node *
 149 ipcp_method_orig_node (struct cgraph_node *mt)
 150 {
 151   return IPA_NODE_REF (mt)->ipcp_orig_node;
 152 }
 153
 154 /* Return true if NODE is a cloned/versioned method.  */
 155 static inline bool
 156 ipcp_method_is_cloned (struct cgraph_node *node)
 157 {
 158   return (ipcp_method_orig_node (node) != NULL);
 159 }
 160
 161 /* Set ORIG_NODE in ipa_node associated with method NODE.  */
 162 static inline void
 163 ipcp_method_set_orig_node (struct cgraph_node *node,
 164                            struct cgraph_node *orig_node)
 165 {
 166   IPA_NODE_REF (node)->ipcp_orig_node = orig_node;
 167 }
 168
 169 /* Create ipa_node and its data structures for NEW_NODE.
 170    Set ORIG_NODE as the orig_node field in ipa_node.  */
 171 static void
 172 ipcp_cloned_create (struct cgraph_node *orig_node,
 173                     struct cgraph_node *new_node)
 174 {
 175   ipa_node_create (new_node);
 176   ipcp_method_set_orig_node (new_node, orig_node);
 177   ipa_method_formal_compute_count (new_node);
 178   ipa_method_compute_tree_map (new_node);
 179 }
 180
 181 /* Return cval_type field of CVAL.  */
 182 static inline enum cvalue_type
 183 ipcp_cval_get_cvalue_type (struct ipcp_formal *cval)
 184 {
 185   return cval->cval_type;
 186 }
 187
 188 /* Return scale for MT.  */
 189 static inline gcov_type
 190 ipcp_method_get_scale (struct cgraph_node *mt)
 191 {
 192   return IPA_NODE_REF (mt)->count_scale;
 193 }
 194
 195 /* Set COUNT as scale for MT.  */
 196 static inline void
 197 ipcp_method_set_scale (struct cgraph_node *node, gcov_type count)
 198 {
 199   IPA_NODE_REF (node)->count_scale = count;
 200 }
 201
 202 /* Set TYPE as cval_type field of CVAL.  */
 203 static inline void
 204 ipcp_cval_set_cvalue_type (struct ipcp_formal *cval, enum cvalue_type type)
 205 {
 206   cval->cval_type = type;
 207 }
 208
 209 /* Return cvalue field of CVAL.  */
 210 static inline union parameter_info *
 211 ipcp_cval_get_cvalue (struct ipcp_formal *cval)
 212 {
 213   return &(cval->cvalue);
 214 }
 215
 216 /* Set VALUE as cvalue field  CVAL.  */
 217 static inline void
 218 ipcp_cval_set_cvalue (struct ipcp_formal *cval, union parameter_info *value,
 219                       enum cvalue_type type)
 220 {
 221   if (type == CONST_VALUE || type == CONST_VALUE_REF)
 222     cval->cvalue.value =  value->value;
 223 }
 224
 225 /* Return whether TYPE is a constant type.  */
 226 static bool
 227 ipcp_type_is_const (enum cvalue_type type)
 228 {
 229   if (type == CONST_VALUE || type == CONST_VALUE_REF)
 230     return true;
 231   else
 232     return false;
 233 }
 234
 235 /* Return true if CONST_VAL1 and CONST_VAL2 are equal.  */
 236 static inline bool
 237 ipcp_cval_equal_cvalues (union parameter_info *const_val1,
 238                          union parameter_info *const_val2,
 239                          enum cvalue_type type1, enum cvalue_type type2)
 240 {
 241   gcc_assert (ipcp_type_is_const (type1) && ipcp_type_is_const (type2));
 242   if (type1 != type2)
 243     return false;
 244
 245   if (operand_equal_p (const_val1->value, const_val2->value, 0))
 246     return true;
 247
 248   return false;
 249 }
 250
 251 /* Compute Meet arithmetics:
 252    Meet (BOTTOM, x) = BOTTOM
 253    Meet (TOP,x) = x
 254    Meet (const_a,const_b) = BOTTOM,  if const_a != const_b.
 255    MEET (const_a,const_b) = const_a, if const_a == const_b.*/
 256 static void
 257 ipcp_cval_meet (struct ipcp_formal *cval, struct ipcp_formal *cval1,
 258                 struct ipcp_formal *cval2)
 259 {
 260   if (ipcp_cval_get_cvalue_type (cval1) == BOTTOM
 261       || ipcp_cval_get_cvalue_type (cval2) == BOTTOM)
 262     {
 263       ipcp_cval_set_cvalue_type (cval, BOTTOM);
 264       return;
 265     }
 266   if (ipcp_cval_get_cvalue_type (cval1) == TOP)
 267     {
 268       ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval2));
 269       ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval2),
 270                             ipcp_cval_get_cvalue_type (cval2));
 271       return;
 272     }
 273   if (ipcp_cval_get_cvalue_type (cval2) == TOP)
 274     {
 275       ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval1));
 276       ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval1),
 277                             ipcp_cval_get_cvalue_type (cval1));
 278       return;
 279     }
 280   if (!ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1),
 281                                 ipcp_cval_get_cvalue (cval2),
 282                                 ipcp_cval_get_cvalue_type (cval1),
 283                                 ipcp_cval_get_cvalue_type (cval2)))
 284     {
 285       ipcp_cval_set_cvalue_type (cval, BOTTOM);
 286       return;
 287     }
 288   ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval1));
 289   ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval1),
 290                         ipcp_cval_get_cvalue_type (cval1));
 291 }
 292
 293 /* Return cval structure for the formal at index INFO_TYPE in MT.  */
 294 static inline struct ipcp_formal *
 295 ipcp_method_cval (struct cgraph_node *mt, int info_type)
 296 {
 297   return &(IPA_NODE_REF (mt)->ipcp_cval[info_type]);
 298 }
 299
 300 /* Given the jump function (TYPE, INFO_TYPE), compute a new value of CVAL.
 301    If TYPE is FORMAL_IPA_TYPE, the cval of the corresponding formal is
 302    drawn from MT.  */
 303 static void
 304 ipcp_cval_compute (struct ipcp_formal *cval, struct cgraph_node *mt,
 305                    enum jump_func_type type, union parameter_info *info_type)
 306 {
 307   if (type == UNKNOWN_IPATYPE)
 308     ipcp_cval_set_cvalue_type (cval, BOTTOM);
 309   else if (type == CONST_IPATYPE)
 310     {
 311       ipcp_cval_set_cvalue_type (cval, CONST_VALUE);
 312       ipcp_cval_set_cvalue (cval, info_type, CONST_VALUE);
 313     }
 314   else if (type == CONST_IPATYPE_REF)
 315     {
 316       ipcp_cval_set_cvalue_type (cval, CONST_VALUE_REF);
 317       ipcp_cval_set_cvalue (cval, info_type, CONST_VALUE_REF);
 318     }
 319   else if (type == FORMAL_IPATYPE)
 320     {
 321       enum cvalue_type type =
 322         ipcp_cval_get_cvalue_type (ipcp_method_cval
 323                                    (mt, info_type->formal_id));
 324       ipcp_cval_set_cvalue_type (cval, type);
 325       ipcp_cval_set_cvalue (cval,
 326                             ipcp_cval_get_cvalue (ipcp_method_cval
 327                                                   (mt, info_type->formal_id)),
 328                             type);
 329     }
 330 }
 331
 332 /* True when CVAL1 and CVAL2 values are not the same.  */
 333 static bool
 334 ipcp_cval_changed (struct ipcp_formal *cval1, struct ipcp_formal *cval2)
 335 {
 336   if (ipcp_cval_get_cvalue_type (cval1) == ipcp_cval_get_cvalue_type (cval2))
 337     {
 338       if (ipcp_cval_get_cvalue_type (cval1) != CONST_VALUE &&
 339           ipcp_cval_get_cvalue_type (cval1) != CONST_VALUE_REF)
 340         return false;
 341       if (ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1),
 342                                    ipcp_cval_get_cvalue (cval2),
 343                                    ipcp_cval_get_cvalue_type (cval1),
 344                                    ipcp_cval_get_cvalue_type (cval2)))
 345         return false;
 346     }
 347   return true;
 348 }
 349
 350 /* Create cval structure for method MT.  */
 351 static inline void
 352 ipcp_formal_create (struct cgraph_node *mt)
 353 {
 354   IPA_NODE_REF (mt)->ipcp_cval =
 355     xcalloc (ipa_method_formal_count (mt), sizeof (struct ipcp_formal));
 356 }
 357
 358 /* Set cval structure of I-th formal of MT to CVAL.  */
 359 static inline void
 360 ipcp_method_cval_set (struct cgraph_node *mt, int i, struct ipcp_formal *cval)
 361 {
 362   IPA_NODE_REF (mt)->ipcp_cval[i].cval_type = cval->cval_type;
 363   ipcp_cval_set_cvalue (ipcp_method_cval (mt, i),
 364                         ipcp_cval_get_cvalue (cval), cval->cval_type);
 365 }
 366
 367 /* Set type of cval structure of formal I of MT to CVAL_TYPE1.  */
 368 static inline void
 369 ipcp_method_cval_set_cvalue_type (struct cgraph_node *mt, int i,
 370                                   enum cvalue_type cval_type1)
 371 {
 372   IPA_NODE_REF (mt)->ipcp_cval[i].cval_type = cval_type1;
 373 }
 374
 375 /* Print ipcp_cval data structures to F.  */
 376 static void
 377 ipcp_method_cval_print (FILE * f)
 378 {
 379   struct cgraph_node *node;
 380   int i, count;
 381   tree cvalue;
 382
 383   fprintf (f, "\nCVAL PRINT\n");
 384   for (node = cgraph_nodes; node; node = node->next)
 385     {
 386       fprintf (f, "Printing cvals %s:\n", cgraph_node_name (node));
 387       count = ipa_method_formal_count (node);
 388       for (i = 0; i < count; i++)
 389         {
 390           if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i))
 391               == CONST_VALUE
 392               || ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) ==
 393               CONST_VALUE_REF)
 394             {
 395               fprintf (f, " param [%d]: ", i);
 396               fprintf (f, "type is CONST ");
 397               cvalue =
 398                 ipcp_cval_get_cvalue (ipcp_method_cval (node, i))->
 399                   value;
 400               print_generic_expr (f, cvalue, 0);
 401               fprintf (f, "\n");
 402             }
 403           else if (ipcp_method_cval (node, i)->cval_type == TOP)
 404             fprintf (f, "param [%d]: type is TOP  \n", i);
 405           else
 406             fprintf (f, "param [%d]: type is BOTTOM  \n", i);
 407         }
 408     }
 409 }
 410
 411 /* Initialize ipcp_cval array of MT with TOP values.
 412    All cvals for a method's formal parameters are initialized to BOTTOM
 413    The currently supported types are integer types, real types and
 414    Fortran constants (i.e. references to constants defined as
 415    const_decls). All other types are not analyzed and therefore are
 416    assigned with BOTTOM.  */
 417 static void
 418 ipcp_method_cval_init (struct cgraph_node *mt)
 419 {
 420   int i;
 421   tree parm_tree;
 422
 423   ipcp_formal_create (mt);
 424   for (i = 0; i < ipa_method_formal_count (mt); i++)
 425     {
 426       parm_tree = ipa_method_get_tree (mt, i);
 427       if (INTEGRAL_TYPE_P (TREE_TYPE (parm_tree))
 428           || SCALAR_FLOAT_TYPE_P (TREE_TYPE (parm_tree))
 429           || POINTER_TYPE_P (TREE_TYPE (parm_tree)))
 430         ipcp_method_cval_set_cvalue_type (mt, i, TOP);
 431       else
 432         ipcp_method_cval_set_cvalue_type (mt, i, BOTTOM);
 433     }
 434 }
 435
 436 /* Create a new assignment statment and make
 437    it the first statement in the function FN
 438    tree.
 439    PARM1 is the lhs of the assignment and
 440    VAL is the rhs. */
 441 static void
 442 constant_val_insert (tree fn, tree parm1, tree val)
 443 {
 444   struct function *func;
 445   tree init_stmt;
 446   edge e_step;
 447   edge_iterator ei;
 448
 449   init_stmt = build2 (MODIFY_EXPR, void_type_node, parm1, val);
 450   func = DECL_STRUCT_FUNCTION (fn);
 451   cfun = func;
 452   current_function_decl = fn;
 453   if (ENTRY_BLOCK_PTR_FOR_FUNCTION (func)->succs)
 454     FOR_EACH_EDGE (e_step, ei, ENTRY_BLOCK_PTR_FOR_FUNCTION (func)->succs)
 455       bsi_insert_on_edge_immediate (e_step, init_stmt);
 456 }
 457
 458 /* build INTEGER_CST tree with type TREE_TYPE and
 459    value according to CVALUE. Return the tree.   */
 460 static tree
 461 build_const_val (union parameter_info *cvalue, enum cvalue_type type,
 462                  tree tree_type)
 463 {
 464   tree const_val = NULL;
 465
 466   gcc_assert (ipcp_type_is_const (type));
 467   const_val = fold_convert (tree_type, cvalue->value);
 468   return const_val;
 469 }
 470
 471 /* Build the tree representing the constant and call
 472    constant_val_insert().  */
 473 static void
 474 ipcp_propagate_const (struct cgraph_node *mt, int param,
 475                       union parameter_info *cvalue ,enum cvalue_type type)
 476 {
 477   tree fndecl;
 478   tree const_val;
 479   tree parm_tree;
 480
 481   if (dump_file)
 482     fprintf (dump_file, "propagating const to %s\n", cgraph_node_name (mt));
 483   fndecl = mt->decl;
 484   parm_tree = ipa_method_get_tree (mt, param);
 485   const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree));
 486   constant_val_insert (fndecl, parm_tree, const_val);
 487 }
 488
 489 /* Compute the proper scale for NODE.  It is the ratio between
 490    the number of direct calls (represented on the incoming
 491    cgraph_edges) and sum of all invocations of NODE (represented
 492    as count in cgraph_node). */
 493 static void
 494 ipcp_method_compute_scale (struct cgraph_node *node)
 495 {
 496   gcov_type sum;
 497   struct cgraph_edge *cs;
 498
 499   sum = 0;
 500   /* Compute sum of all counts of callers. */
 501   for (cs = node->callers; cs != NULL; cs = cs->next_caller)
 502     sum += cs->count;
 503   if (node->count == 0)
 504     ipcp_method_set_scale (node, 0);
 505   else
 506     ipcp_method_set_scale (node, sum * REG_BR_PROB_BASE / node->count);
 507 }
 508
 509 /* Initialization and computation of IPCP data structures.
 510    It is an intraprocedural
 511    analysis of methods, which gathers information to be propagated
 512    later on.  */
 513 static void
 514 ipcp_init_stage (void)
 515 {
 516   struct cgraph_node *node;
 517   struct cgraph_edge *cs;
 518
 519   for (node = cgraph_nodes; node; node = node->next)
 520     {
 521       ipa_method_formal_compute_count (node);
 522       ipa_method_compute_tree_map (node);
 523       ipcp_method_cval_init (node);
 524       ipa_method_compute_modify (node);
 525       ipcp_method_compute_scale (node);
 526     }
 527   for (node = cgraph_nodes; node; node = node->next)
 528     {
 529       /* building jump functions  */
 530       for (cs = node->callees; cs; cs = cs->next_callee)
 531         {
 532           ipa_callsite_compute_count (cs);
 533           if (ipa_callsite_param_count (cs)
 534               != ipa_method_formal_count (cs->callee))
 535             {
 536               /* Handle cases of functions with
 537                  a variable number of parameters.  */
 538               ipa_callsite_param_count_set (cs, 0);
 539               ipa_method_formal_count_set (cs->callee, 0);
 540             }
 541           else
 542             ipa_callsite_compute_param (cs);
 543         }
 544     }
 545 }
 546
 547 /* Return true if there are some formal parameters whose value is TOP.
 548    Change their values to BOTTOM, since they weren't determined.  */
 549 static bool
 550 ipcp_after_propagate (void)
 551 {
 552   int i, count;
 553   struct cgraph_node *node;
 554   bool prop_again;
 555
 556   prop_again = false;
 557   for (node = cgraph_nodes; node; node = node->next)
 558     {
 559       count = ipa_method_formal_count (node);
 560       for (i = 0; i < count; i++)
 561         if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) == TOP)
 562           {
 563             prop_again = true;
 564             ipcp_method_cval_set_cvalue_type (node, i, BOTTOM);
 565           }
 566     }
 567   return prop_again;
 568 }
 569
 570 /* Interprocedural analysis. The algorithm propagates constants from
 571    the caller's parameters to the callee's arguments.  */
 572 static void
 573 ipcp_propagate_stage (void)
 574 {
 575   int i;
 576   struct ipcp_formal cval1 = { 0, {0} }, cval = { 0,{0} };
 577   struct ipcp_formal *cval2;
 578   struct cgraph_node *mt, *callee;
 579   struct cgraph_edge *cs;
 580   struct ipa_jump_func *jump_func;
 581   enum jump_func_type type;
 582   union parameter_info *info_type;
 583   ipa_methodlist_p wl;
 584   int count;
 585
 586   /* Initialize worklist to contain all methods.  */
 587   wl = ipa_methodlist_init ();
 588   while (ipa_methodlist_not_empty (wl))
 589     {
 590       mt = ipa_remove_method (&wl);
 591       for (cs = mt->callees; cs; cs = cs->next_callee)
 592         {
 593           callee = ipa_callsite_callee (cs);
 594           count = ipa_callsite_param_count (cs);
 595           for (i = 0; i < count; i++)
 596             {
 597               jump_func = ipa_callsite_param (cs, i);
 598               type = get_type (jump_func);
 599               info_type = ipa_jf_get_info_type (jump_func);
 600               ipcp_cval_compute (&cval1, mt, type, info_type);
 601               cval2 = ipcp_method_cval (callee, i);
 602               ipcp_cval_meet (&cval, &cval1, cval2);
 603               if (ipcp_cval_changed (&cval, cval2))
 604                 {
 605                   ipcp_method_cval_set (callee, i, &cval);
 606                   ipa_add_method (&wl, callee);
 607                 }
 608             }
 609         }
 610     }
 611 }
 612
 613 /* Call the constant propagation algorithm and re-call it if necessary
 614    (if there are undetermined values left).  */
 615 static void
 616 ipcp_iterate_stage (void)
 617 {
 618   ipcp_propagate_stage ();
 619   if (ipcp_after_propagate ())
 620     /* Some cvals have changed from TOP to BOTTOM.
 621        This change should be propagated.  */
 622     ipcp_propagate_stage ();
 623 }
 624
 625 /* Check conditions to forbid constant insertion to MT.  */
 626 static bool
 627 ipcp_method_dont_insert_const (struct cgraph_node *mt)
 628 {
 629   /* ??? Handle pending sizes case.  */
 630   if (DECL_UNINLINABLE (mt->decl))
 631     return true;
 632   return false;
 633 }
 634
 635 /* Print ipa_jump_func data structures to F.  */
 636 static void
 637 ipcp_callsite_param_print (FILE * f)
 638 {
 639   struct cgraph_node *node;
 640   int i, count;
 641   struct cgraph_edge *cs;
 642   struct ipa_jump_func *jump_func;
 643   enum jump_func_type type;
 644   tree info_type;
 645
 646   fprintf (f, "\nCALLSITE PARAM PRINT\n");
 647   for (node = cgraph_nodes; node; node = node->next)
 648     {
 649       for (cs = node->callees; cs; cs = cs->next_callee)
 650         {
 651           fprintf (f, "callsite  %s ", cgraph_node_name (node));
 652           fprintf (f, "-> %s :: \n", cgraph_node_name (cs->callee));
 653           count = ipa_callsite_param_count (cs);
 654           for (i = 0; i < count; i++)
 655             {
 656               jump_func = ipa_callsite_param (cs, i);
 657               type = get_type (jump_func);
 658
 659               fprintf (f, " param %d: ", i);
 660               if (type == UNKNOWN_IPATYPE)
 661                 fprintf (f, "UNKNOWN\n");
 662               else if (type == CONST_IPATYPE || type == CONST_IPATYPE_REF)
 663                 {
 664                   info_type =
 665                     ipa_jf_get_info_type (jump_func)->value;
 666                   fprintf (f, "CONST : ");
 667                   print_generic_expr (f, info_type, 0);
 668                   fprintf (f, "\n");
 669                 }
 670               else if (type == FORMAL_IPATYPE)
 671                 {
 672                   fprintf (f, "FORMAL : ");
 673                   fprintf (f, "%d\n",
 674                            ipa_jf_get_info_type (jump_func)->formal_id);
 675                 }
 676             }
 677         }
 678     }
 679 }
 680
 681 /* Print count scale data structures.  */
 682 static void
 683 ipcp_method_scale_print (FILE * f)
 684 {
 685   struct cgraph_node *node;
 686
 687   for (node = cgraph_nodes; node; node = node->next)
 688     {
 689       fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
 690       fprintf (f, "value is  " HOST_WIDE_INT_PRINT_DEC
 691                "  \n", (HOST_WIDE_INT) ipcp_method_get_scale (node));
 692     }
 693 }
 694
 695 /* Print counts of all cgraph nodes.  */
 696 static void
 697 ipcp_profile_mt_count_print (FILE * f)
 698 {
 699   struct cgraph_node *node;
 700
 701   for (node = cgraph_nodes; node; node = node->next)
 702     {
 703       fprintf (f, "method %s: ", cgraph_node_name (node));
 704       fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC
 705                "  \n", (HOST_WIDE_INT) node->count);
 706     }
 707 }
 708
 709 /* Print counts of all cgraph edges.  */
 710 static void
 711 ipcp_profile_cs_count_print (FILE * f)
 712 {
 713   struct cgraph_node *node;
 714   struct cgraph_edge *cs;
 715
 716   for (node = cgraph_nodes; node; node = node->next)
 717     {
 718       for (cs = node->callees; cs; cs = cs->next_callee)
 719         {
 720           fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
 721                    cgraph_node_name (cs->callee));
 722           fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC "  \n",
 723                    (HOST_WIDE_INT) cs->count);
 724         }
 725     }
 726 }
 727
 728 /* Print all counts and probabilities of cfg edges of all methods.  */
 729 static void
 730 ipcp_profile_edge_print (FILE * f)
 731 {
 732   struct cgraph_node *node;
 733   basic_block bb;
 734   edge_iterator ei;
 735   edge e;
 736
 737   for (node = cgraph_nodes; node; node = node->next)
 738     {
 739       fprintf (f, "method %s: \n", cgraph_node_name (node));
 740       if (DECL_SAVED_TREE (node->decl))
 741         {
 742           bb =
 743             ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 744           fprintf (f, "ENTRY: ");
 745           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 746                    " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
 747
 748           if (bb->succs)
 749             FOR_EACH_EDGE (e, ei, bb->succs)
 750             {
 751               if (e->dest ==
 752                   EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
 753                                                (node->decl)))
 754                 fprintf (f, "edge ENTRY -> EXIT,  Count");
 755               else
 756                 fprintf (f, "edge ENTRY -> %d,  Count", e->dest->index);
 757               fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 758                        " Prob %d\n", (HOST_WIDE_INT) e->count,
 759                        e->probability);
 760             }
 761           FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 762           {
 763             fprintf (f, "bb[%d]: ", bb->index);
 764             fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 765                      " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
 766             FOR_EACH_EDGE (e, ei, bb->succs)
 767             {
 768               if (e->dest ==
 769                   EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
 770                                                (node->decl)))
 771                 fprintf (f, "edge %d -> EXIT,  Count", e->src->index);
 772               else
 773                 fprintf (f, "edge %d -> %d,  Count", e->src->index,
 774                          e->dest->index);
 775               fprintf (f, " " HOST_WIDE_INT_PRINT_DEC " Prob %d\n",
 776                        (HOST_WIDE_INT) e->count, e->probability);
 777             }
 778           }
 779         }
 780     }
 781 }
 782
 783 /* Print counts and frequencies for all basic blocks of all methods.  */
 784 static void
 785 ipcp_profile_bb_print (FILE * f)
 786 {
 787   basic_block bb;
 788   struct cgraph_node *node;
 789
 790   for (node = cgraph_nodes; node; node = node->next)
 791     {
 792       fprintf (f, "method %s: \n", cgraph_node_name (node));
 793       if (DECL_SAVED_TREE (node->decl))
 794         {
 795           bb =
 796             ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 797           fprintf (f, "ENTRY: Count");
 798           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 799                    " Frquency  %d\n", (HOST_WIDE_INT) bb->count,
 800                    bb->frequency);
 801
 802           FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 803           {
 804             fprintf (f, "bb[%d]: Count", bb->index);
 805             fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 806                      " Frequency %d\n", (HOST_WIDE_INT) bb->count,
 807                      bb->frequency);
 808           }
 809           bb =
 810             EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 811           fprintf (f, "EXIT: Count");
 812           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 813                    " Frequency %d\n", (HOST_WIDE_INT) bb->count,
 814                    bb->frequency);
 815
 816         }
 817     }
 818 }
 819
 820 /* Print all IPCP data structures to F.  */
 821 static void
 822 ipcp_structures_print (FILE * f)
 823 {
 824   ipcp_method_cval_print (f);
 825   ipcp_method_scale_print (f);
 826   ipa_method_tree_print (f);
 827   ipa_method_modify_print (f);
 828   ipcp_callsite_param_print (f);
 829 }
 830
 831 /* Print profile info for all methods.  */
 832 static void
 833 ipcp_profile_print (FILE * f)
 834 {
 835   fprintf (f, "\nNODE COUNTS :\n");
 836   ipcp_profile_mt_count_print (f);
 837   fprintf (f, "\nCS COUNTS stage:\n");
 838   ipcp_profile_cs_count_print (f);
 839   fprintf (f, "\nBB COUNTS and FREQUENCIES :\n");
 840   ipcp_profile_bb_print (f);
 841   fprintf (f, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
 842   ipcp_profile_edge_print (f);
 843 }
 844
 845 /* Build and initialize ipa_replace_map struct
 846    according to TYPE. This struct is read by versioning, which
 847    operates according to the flags sent.  PARM_TREE is the
 848    formal's tree found to be constant.  CVALUE represents the constant.  */
 849 static struct ipa_replace_map *
 850 ipcp_replace_map_create (enum cvalue_type type, tree parm_tree,
 851                          union parameter_info *cvalue)
 852 {
 853   struct ipa_replace_map *replace_map;
 854   tree const_val;
 855
 856   replace_map = xcalloc (1, sizeof (struct ipa_replace_map));
 857   gcc_assert (ipcp_type_is_const (type));
 858   if (type == CONST_VALUE_REF )
 859     {
 860       const_val =
 861         build_const_val (cvalue, type, TREE_TYPE (TREE_TYPE (parm_tree)));
 862       replace_map->old_tree = parm_tree;
 863       replace_map->new_tree = const_val;
 864       replace_map->replace_p = true;
 865       replace_map->ref_p = true;
 866     }
 867   else if (TREE_READONLY (parm_tree) && !TREE_ADDRESSABLE (parm_tree))
 868     {
 869       const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree));
 870       replace_map->old_tree = parm_tree;
 871       replace_map->new_tree = const_val;
 872       replace_map->replace_p = true;
 873       replace_map->ref_p = false;
 874     }
 875   else
 876     {
 877       replace_map->old_tree = NULL;
 878       replace_map->new_tree = NULL;
 879       replace_map->replace_p = false;
 880       replace_map->ref_p = false;
 881     }
 882
 883   return replace_map;
 884 }
 885
 886 /* Return true if this callsite should be redirected to
 887    the orig callee (instead of the cloned one).  */
 888 static bool
 889 ipcp_redirect (struct cgraph_edge *cs)
 890 {
 891   struct cgraph_node *caller, *callee, *orig_callee;
 892   int i, count;
 893   struct ipa_jump_func *jump_func;
 894   enum jump_func_type type;
 895   enum cvalue_type cval_type;
 896
 897   caller = cs->caller;
 898   callee = cs->callee;
 899   orig_callee = ipcp_method_orig_node (callee);
 900   count = ipa_method_formal_count (orig_callee);
 901   for (i = 0; i < count; i++)
 902     {
 903       cval_type =
 904         ipcp_cval_get_cvalue_type (ipcp_method_cval (orig_callee, i));
 905       if (ipcp_type_is_const (cval_type))
 906         {
 907           jump_func = ipa_callsite_param (cs, i);
 908           type = get_type (jump_func);
 909           if (type != CONST_IPATYPE
 910               && type != CONST_IPATYPE_REF)
 911             return true;
 912         }
 913     }
 914
 915   return false;
 916 }
 917
 918 /* Fix the callsites and the callgraph after function cloning was done.  */
 919 static void
 920 ipcp_update_callgraph (void)
 921 {
 922   struct cgraph_node *node, *orig_callee;
 923   struct cgraph_edge *cs;
 924
 925   for (node = cgraph_nodes; node; node = node->next)
 926     {
 927       /* want to fix only original nodes  */
 928       if (ipcp_method_is_cloned (node))
 929         continue;
 930       for (cs = node->callees; cs; cs = cs->next_callee)
 931         if (ipcp_method_is_cloned (cs->callee))
 932           {
 933             /* Callee is a cloned node  */
 934             orig_callee = ipcp_method_orig_node (cs->callee);
 935             if (ipcp_redirect (cs))
 936               {
 937                 cgraph_redirect_edge_callee (cs, orig_callee);
 938                 TREE_OPERAND (TREE_OPERAND
 939                               (get_call_expr_in (cs->call_stmt), 0), 0) =
 940                   orig_callee->decl;
 941               }
 942           }
 943     }
 944 }
 945
 946 /* Update all cfg basic blocks in NODE according to SCALE.  */
 947 static void
 948 ipcp_update_bb_counts (struct cgraph_node *node, gcov_type scale)
 949 {
 950   basic_block bb;
 951
 952   FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 953     bb->count = bb->count * scale / REG_BR_PROB_BASE;
 954 }
 955
 956 /* Update all cfg edges in NODE according to SCALE.  */
 957 static void
 958 ipcp_update_edges_counts (struct cgraph_node *node, gcov_type scale)
 959 {
 960   basic_block bb;
 961   edge_iterator ei;
 962   edge e;
 963
 964   FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 965     FOR_EACH_EDGE (e, ei, bb->succs)
 966     e->count = e->count * scale / REG_BR_PROB_BASE;
 967 }
 968
 969 /* Update profiling info for versioned methods and the
 970    methods they were versioned from.  */
 971 static void
 972 ipcp_update_profiling (void)
 973 {
 974   struct cgraph_node *node, *orig_node;
 975   gcov_type scale, scale_complement;
 976   struct cgraph_edge *cs;
 977
 978   for (node = cgraph_nodes; node; node = node->next)
 979     {
 980       if (ipcp_method_is_cloned (node))
 981         {
 982           orig_node = ipcp_method_orig_node (node);
 983           scale = ipcp_method_get_scale (orig_node);
 984           node->count = orig_node->count * scale / REG_BR_PROB_BASE;
 985           scale_complement = REG_BR_PROB_BASE - scale;
 986           orig_node->count =
 987             orig_node->count * scale_complement / REG_BR_PROB_BASE;
 988           for (cs = node->callees; cs; cs = cs->next_callee)
 989             cs->count = cs->count * scale / REG_BR_PROB_BASE;
 990           for (cs = orig_node->callees; cs; cs = cs->next_callee)
 991             cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
 992           ipcp_update_bb_counts (node, scale);
 993           ipcp_update_bb_counts (orig_node, scale_complement);
 994           ipcp_update_edges_counts (node, scale);
 995           ipcp_update_edges_counts (orig_node, scale_complement);
 996         }
 997     }
 998 }
 999
1000 /* Propagate the constant parameters found by ipcp_iterate_stage()
1001    to the function's code.  */
1002 static void
1003 ipcp_insert_stage (void)
1004 {
1005   struct cgraph_node *node, *node1 = NULL;
1006   int i, const_param;
1007   union parameter_info *cvalue;
1008   varray_type redirect_callers, replace_trees;
1009   struct cgraph_edge *cs;
1010   int node_callers, count;
1011   tree parm_tree;
1012   enum cvalue_type type;
1013   struct ipa_replace_map *replace_param;
1014
1015   for (node = cgraph_nodes; node; node = node->next)
1016     {
1017       /* Propagation of the constant is forbidden in
1018          certain conditions.  */
1019       if (ipcp_method_dont_insert_const (node))
1020         continue;
1021       const_param = 0;
1022       count = ipa_method_formal_count (node);
1023       for (i = 0; i < count; i++)
1024         {
1025           type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
1026           if (ipcp_type_is_const (type))
1027             const_param++;
1028         }
1029       if (const_param == 0)
1030         continue;
1031       VARRAY_GENERIC_PTR_INIT (replace_trees, const_param, "replace_trees");
1032       for (i = 0; i < count; i++)
1033         {
1034           type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
1035           if (ipcp_type_is_const (type))
1036             {
1037               cvalue = ipcp_cval_get_cvalue (ipcp_method_cval (node, i));
1038               parm_tree = ipa_method_get_tree (node, i);
1039               replace_param =
1040                 ipcp_replace_map_create (type, parm_tree, cvalue);
1041               VARRAY_PUSH_GENERIC_PTR (replace_trees, replace_param);
1042             }
1043         }
1044       /* Compute how many callers node has.  */
1045       node_callers = 0;
1046       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1047         node_callers++;
1048       VARRAY_GENERIC_PTR_INIT (redirect_callers, node_callers,
1049                                "redirect_callers");
1050       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1051         VARRAY_PUSH_GENERIC_PTR (redirect_callers, cs);
1052       /* Redirecting all the callers of the node to the
1053          new versioned node.  */
1054       node1 =
1055         cgraph_function_versioning (node, redirect_callers, replace_trees);
1056       VARRAY_CLEAR (redirect_callers);
1057       VARRAY_CLEAR (replace_trees);
1058       if (node1 == NULL)
1059         continue;
1060       if (dump_file)
1061         fprintf (dump_file, "versioned function %s\n",
1062                  cgraph_node_name (node));
1063       ipcp_cloned_create (node, node1);
1064       for (i = 0; i < count; i++)
1065         {
1066           type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
1067           if (ipcp_type_is_const (type))
1068             {
1069               cvalue = ipcp_cval_get_cvalue (ipcp_method_cval (node, i));
1070               parm_tree = ipa_method_get_tree (node, i);
1071               if (type != CONST_VALUE_REF
1072                   && !TREE_READONLY (parm_tree))
1073                 ipcp_propagate_const (node1, i, cvalue, type);
1074             }
1075         }
1076     }
1077   ipcp_update_callgraph ();
1078   ipcp_update_profiling ();
1079 }
1080
1081 /* The IPCP driver.  */
1082 void
1083 ipcp_driver (void)
1084 {
1085   if (dump_file)
1086     fprintf (dump_file, "\nIPA constant propagation start:\n");
1087   ipa_nodes_create ();
1088   ipa_edges_create ();
1089   /* 1. Call the init stage to initialize
1090      the ipa_node and ipa_edge structures.  */
1091   ipcp_init_stage ();
1092   if (dump_file)
1093     {
1094       fprintf (dump_file, "\nIPA structures before propagation:\n");
1095       ipcp_structures_print (dump_file);
1096     }
1097   /* 2. Do the interprocedural propagation.  */
1098   ipcp_iterate_stage ();
1099   if (dump_file)
1100     {
1101       fprintf (dump_file, "\nIPA structures after propagation:\n");
1102       ipcp_structures_print (dump_file);
1103       fprintf (dump_file, "\nProfiling info before insert stage:\n");
1104       ipcp_profile_print (dump_file);
1105     }
1106   /* 3. Insert the constants found to the functions.  */
1107   ipcp_insert_stage ();
1108   if (dump_file)
1109     {
1110       fprintf (dump_file, "\nProfiling info after insert stage:\n");
1111       ipcp_profile_print (dump_file);
1112     }
1113   /* Free all IPCP structures.  */
1114   ipa_free ();
1115   ipa_nodes_free ();
1116   ipa_edges_free ();
1117   if (dump_file)
1118     fprintf (dump_file, "\nIPA constant propagation end\n");
1119   cgraph_remove_unreachable_nodes (true, NULL);
1120 }
1121
1122 /* Gate for IPCP optimization.  */
1123 static bool
1124 cgraph_gate_cp (void)
1125 {
1126   return flag_ipa_cp;
1127 }
1128
1129 struct tree_opt_pass pass_ipa_cp = {
1130   "cp",                         /* name */
1131   cgraph_gate_cp,               /* gate */
1132   ipcp_driver,                  /* execute */
1133   NULL,                         /* sub */
1134   NULL,                         /* next */
1135   0,                            /* static_pass_number */
1136   TV_IPA_CONSTANT_PROP,         /* tv_id */
1137   0,                            /* properties_required */
1138   PROP_trees,                   /* properties_provided */
1139   0,                            /* properties_destroyed */
1140   0,                            /* todo_flags_start */
1141   TODO_dump_cgraph | TODO_dump_func,    /* todo_flags_finish */
1142   0                             /* letter */
1143 };