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     XCNEWVEC (struct ipcp_formal, ipa_method_formal_count (mt));
 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 (GIMPLE_MODIFY_STMT, 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   current_function_decl = NULL;
 457   cfun = NULL;
 458 }
 459
 460 /* build INTEGER_CST tree with type TREE_TYPE and
 461    value according to CVALUE. Return the tree.   */
 462 static tree
 463 build_const_val (union parameter_info *cvalue, enum cvalue_type type,
 464                  tree tree_type)
 465 {
 466   tree const_val = NULL;
 467
 468   gcc_assert (ipcp_type_is_const (type));
 469   const_val = fold_convert (tree_type, cvalue->value);
 470   return const_val;
 471 }
 472
 473 /* Build the tree representing the constant and call
 474    constant_val_insert().  */
 475 static void
 476 ipcp_propagate_const (struct cgraph_node *mt, int param,
 477                       union parameter_info *cvalue ,enum cvalue_type type)
 478 {
 479   tree fndecl;
 480   tree const_val;
 481   tree parm_tree;
 482
 483   if (dump_file)
 484     fprintf (dump_file, "propagating const to %s\n", cgraph_node_name (mt));
 485   fndecl = mt->decl;
 486   parm_tree = ipa_method_get_tree (mt, param);
 487   const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree));
 488   constant_val_insert (fndecl, parm_tree, const_val);
 489 }
 490
 491 /* Compute the proper scale for NODE.  It is the ratio between
 492    the number of direct calls (represented on the incoming
 493    cgraph_edges) and sum of all invocations of NODE (represented
 494    as count in cgraph_node). */
 495 static void
 496 ipcp_method_compute_scale (struct cgraph_node *node)
 497 {
 498   gcov_type sum;
 499   struct cgraph_edge *cs;
 500
 501   sum = 0;
 502   /* Compute sum of all counts of callers. */
 503   for (cs = node->callers; cs != NULL; cs = cs->next_caller)
 504     sum += cs->count;
 505   if (node->count == 0)
 506     ipcp_method_set_scale (node, 0);
 507   else
 508     ipcp_method_set_scale (node, sum * REG_BR_PROB_BASE / node->count);
 509 }
 510
 511 /* Initialization and computation of IPCP data structures.
 512    It is an intraprocedural
 513    analysis of methods, which gathers information to be propagated
 514    later on.  */
 515 static void
 516 ipcp_init_stage (void)
 517 {
 518   struct cgraph_node *node;
 519   struct cgraph_edge *cs;
 520
 521   for (node = cgraph_nodes; node; node = node->next)
 522     {
 523       ipa_method_formal_compute_count (node);
 524       ipa_method_compute_tree_map (node);
 525       ipcp_method_cval_init (node);
 526       ipa_method_compute_modify (node);
 527       ipcp_method_compute_scale (node);
 528     }
 529   for (node = cgraph_nodes; node; node = node->next)
 530     {
 531       /* building jump functions  */
 532       for (cs = node->callees; cs; cs = cs->next_callee)
 533         {
 534           ipa_callsite_compute_count (cs);
 535           if (ipa_callsite_param_count (cs)
 536               != ipa_method_formal_count (cs->callee))
 537             {
 538               /* Handle cases of functions with
 539                  a variable number of parameters.  */
 540               ipa_callsite_param_count_set (cs, 0);
 541               ipa_method_formal_count_set (cs->callee, 0);
 542             }
 543           else
 544             ipa_callsite_compute_param (cs);
 545         }
 546     }
 547 }
 548
 549 /* Return true if there are some formal parameters whose value is TOP.
 550    Change their values to BOTTOM, since they weren't determined.  */
 551 static bool
 552 ipcp_after_propagate (void)
 553 {
 554   int i, count;
 555   struct cgraph_node *node;
 556   bool prop_again;
 557
 558   prop_again = false;
 559   for (node = cgraph_nodes; node; node = node->next)
 560     {
 561       count = ipa_method_formal_count (node);
 562       for (i = 0; i < count; i++)
 563         if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) == TOP)
 564           {
 565             prop_again = true;
 566             ipcp_method_cval_set_cvalue_type (node, i, BOTTOM);
 567           }
 568     }
 569   return prop_again;
 570 }
 571
 572 /* Interprocedural analysis. The algorithm propagates constants from
 573    the caller's parameters to the callee's arguments.  */
 574 static void
 575 ipcp_propagate_stage (void)
 576 {
 577   int i;
 578   struct ipcp_formal cval1 = { 0, {0} }, cval = { 0,{0} };
 579   struct ipcp_formal *cval2;
 580   struct cgraph_node *mt, *callee;
 581   struct cgraph_edge *cs;
 582   struct ipa_jump_func *jump_func;
 583   enum jump_func_type type;
 584   union parameter_info *info_type;
 585   ipa_methodlist_p wl;
 586   int count;
 587
 588   /* Initialize worklist to contain all methods.  */
 589   wl = ipa_methodlist_init ();
 590   while (ipa_methodlist_not_empty (wl))
 591     {
 592       mt = ipa_remove_method (&wl);
 593       for (cs = mt->callees; cs; cs = cs->next_callee)
 594         {
 595           callee = ipa_callsite_callee (cs);
 596           count = ipa_callsite_param_count (cs);
 597           for (i = 0; i < count; i++)
 598             {
 599               jump_func = ipa_callsite_param (cs, i);
 600               type = get_type (jump_func);
 601               info_type = ipa_jf_get_info_type (jump_func);
 602               ipcp_cval_compute (&cval1, mt, type, info_type);
 603               cval2 = ipcp_method_cval (callee, i);
 604               ipcp_cval_meet (&cval, &cval1, cval2);
 605               if (ipcp_cval_changed (&cval, cval2))
 606                 {
 607                   ipcp_method_cval_set (callee, i, &cval);
 608                   ipa_add_method (&wl, callee);
 609                 }
 610             }
 611         }
 612     }
 613 }
 614
 615 /* Call the constant propagation algorithm and re-call it if necessary
 616    (if there are undetermined values left).  */
 617 static void
 618 ipcp_iterate_stage (void)
 619 {
 620   ipcp_propagate_stage ();
 621   if (ipcp_after_propagate ())
 622     /* Some cvals have changed from TOP to BOTTOM.
 623        This change should be propagated.  */
 624     ipcp_propagate_stage ();
 625 }
 626
 627 /* Check conditions to forbid constant insertion to MT.  */
 628 static bool
 629 ipcp_method_dont_insert_const (struct cgraph_node *mt)
 630 {
 631   /* ??? Handle pending sizes case.  */
 632   if (DECL_UNINLINABLE (mt->decl))
 633     return true;
 634   return false;
 635 }
 636
 637 /* Print ipa_jump_func data structures to F.  */
 638 static void
 639 ipcp_callsite_param_print (FILE * f)
 640 {
 641   struct cgraph_node *node;
 642   int i, count;
 643   struct cgraph_edge *cs;
 644   struct ipa_jump_func *jump_func;
 645   enum jump_func_type type;
 646   tree info_type;
 647
 648   fprintf (f, "\nCALLSITE PARAM PRINT\n");
 649   for (node = cgraph_nodes; node; node = node->next)
 650     {
 651       for (cs = node->callees; cs; cs = cs->next_callee)
 652         {
 653           fprintf (f, "callsite  %s ", cgraph_node_name (node));
 654           fprintf (f, "-> %s :: \n", cgraph_node_name (cs->callee));
 655           count = ipa_callsite_param_count (cs);
 656           for (i = 0; i < count; i++)
 657             {
 658               jump_func = ipa_callsite_param (cs, i);
 659               type = get_type (jump_func);
 660
 661               fprintf (f, " param %d: ", i);
 662               if (type == UNKNOWN_IPATYPE)
 663                 fprintf (f, "UNKNOWN\n");
 664               else if (type == CONST_IPATYPE || type == CONST_IPATYPE_REF)
 665                 {
 666                   info_type =
 667                     ipa_jf_get_info_type (jump_func)->value;
 668                   fprintf (f, "CONST : ");
 669                   print_generic_expr (f, info_type, 0);
 670                   fprintf (f, "\n");
 671                 }
 672               else if (type == FORMAL_IPATYPE)
 673                 {
 674                   fprintf (f, "FORMAL : ");
 675                   fprintf (f, "%d\n",
 676                            ipa_jf_get_info_type (jump_func)->formal_id);
 677                 }
 678             }
 679         }
 680     }
 681 }
 682
 683 /* Print count scale data structures.  */
 684 static void
 685 ipcp_method_scale_print (FILE * f)
 686 {
 687   struct cgraph_node *node;
 688
 689   for (node = cgraph_nodes; node; node = node->next)
 690     {
 691       fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
 692       fprintf (f, "value is  " HOST_WIDE_INT_PRINT_DEC
 693                "  \n", (HOST_WIDE_INT) ipcp_method_get_scale (node));
 694     }
 695 }
 696
 697 /* Print counts of all cgraph nodes.  */
 698 static void
 699 ipcp_profile_mt_count_print (FILE * f)
 700 {
 701   struct cgraph_node *node;
 702
 703   for (node = cgraph_nodes; node; node = node->next)
 704     {
 705       fprintf (f, "method %s: ", cgraph_node_name (node));
 706       fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC
 707                "  \n", (HOST_WIDE_INT) node->count);
 708     }
 709 }
 710
 711 /* Print counts of all cgraph edges.  */
 712 static void
 713 ipcp_profile_cs_count_print (FILE * f)
 714 {
 715   struct cgraph_node *node;
 716   struct cgraph_edge *cs;
 717
 718   for (node = cgraph_nodes; node; node = node->next)
 719     {
 720       for (cs = node->callees; cs; cs = cs->next_callee)
 721         {
 722           fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
 723                    cgraph_node_name (cs->callee));
 724           fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC "  \n",
 725                    (HOST_WIDE_INT) cs->count);
 726         }
 727     }
 728 }
 729
 730 /* Print all counts and probabilities of cfg edges of all methods.  */
 731 static void
 732 ipcp_profile_edge_print (FILE * f)
 733 {
 734   struct cgraph_node *node;
 735   basic_block bb;
 736   edge_iterator ei;
 737   edge e;
 738
 739   for (node = cgraph_nodes; node; node = node->next)
 740     {
 741       fprintf (f, "method %s: \n", cgraph_node_name (node));
 742       if (DECL_SAVED_TREE (node->decl))
 743         {
 744           bb =
 745             ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 746           fprintf (f, "ENTRY: ");
 747           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 748                    " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
 749
 750           if (bb->succs)
 751             FOR_EACH_EDGE (e, ei, bb->succs)
 752             {
 753               if (e->dest ==
 754                   EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
 755                                                (node->decl)))
 756                 fprintf (f, "edge ENTRY -> EXIT,  Count");
 757               else
 758                 fprintf (f, "edge ENTRY -> %d,  Count", e->dest->index);
 759               fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 760                        " Prob %d\n", (HOST_WIDE_INT) e->count,
 761                        e->probability);
 762             }
 763           FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 764           {
 765             fprintf (f, "bb[%d]: ", bb->index);
 766             fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 767                      " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
 768             FOR_EACH_EDGE (e, ei, bb->succs)
 769             {
 770               if (e->dest ==
 771                   EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
 772                                                (node->decl)))
 773                 fprintf (f, "edge %d -> EXIT,  Count", e->src->index);
 774               else
 775                 fprintf (f, "edge %d -> %d,  Count", e->src->index,
 776                          e->dest->index);
 777               fprintf (f, " " HOST_WIDE_INT_PRINT_DEC " Prob %d\n",
 778                        (HOST_WIDE_INT) e->count, e->probability);
 779             }
 780           }
 781         }
 782     }
 783 }
 784
 785 /* Print counts and frequencies for all basic blocks of all methods.  */
 786 static void
 787 ipcp_profile_bb_print (FILE * f)
 788 {
 789   basic_block bb;
 790   struct cgraph_node *node;
 791
 792   for (node = cgraph_nodes; node; node = node->next)
 793     {
 794       fprintf (f, "method %s: \n", cgraph_node_name (node));
 795       if (DECL_SAVED_TREE (node->decl))
 796         {
 797           bb =
 798             ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 799           fprintf (f, "ENTRY: Count");
 800           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 801                    " Frquency  %d\n", (HOST_WIDE_INT) bb->count,
 802                    bb->frequency);
 803
 804           FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 805           {
 806             fprintf (f, "bb[%d]: Count", bb->index);
 807             fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 808                      " Frequency %d\n", (HOST_WIDE_INT) bb->count,
 809                      bb->frequency);
 810           }
 811           bb =
 812             EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 813           fprintf (f, "EXIT: Count");
 814           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 815                    " Frequency %d\n", (HOST_WIDE_INT) bb->count,
 816                    bb->frequency);
 817
 818         }
 819     }
 820 }
 821
 822 /* Print all IPCP data structures to F.  */
 823 static void
 824 ipcp_structures_print (FILE * f)
 825 {
 826   ipcp_method_cval_print (f);
 827   ipcp_method_scale_print (f);
 828   ipa_method_tree_print (f);
 829   ipa_method_modify_print (f);
 830   ipcp_callsite_param_print (f);
 831 }
 832
 833 /* Print profile info for all methods.  */
 834 static void
 835 ipcp_profile_print (FILE * f)
 836 {
 837   fprintf (f, "\nNODE COUNTS :\n");
 838   ipcp_profile_mt_count_print (f);
 839   fprintf (f, "\nCS COUNTS stage:\n");
 840   ipcp_profile_cs_count_print (f);
 841   fprintf (f, "\nBB COUNTS and FREQUENCIES :\n");
 842   ipcp_profile_bb_print (f);
 843   fprintf (f, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
 844   ipcp_profile_edge_print (f);
 845 }
 846
 847 /* Build and initialize ipa_replace_map struct
 848    according to TYPE. This struct is read by versioning, which
 849    operates according to the flags sent.  PARM_TREE is the
 850    formal's tree found to be constant.  CVALUE represents the constant.  */
 851 static struct ipa_replace_map *
 852 ipcp_replace_map_create (enum cvalue_type type, tree parm_tree,
 853                          union parameter_info *cvalue)
 854 {
 855   struct ipa_replace_map *replace_map;
 856   tree const_val;
 857
 858   replace_map = XCNEW (struct ipa_replace_map);
 859   gcc_assert (ipcp_type_is_const (type));
 860   if (type == CONST_VALUE_REF )
 861     {
 862       const_val =
 863         build_const_val (cvalue, type, TREE_TYPE (TREE_TYPE (parm_tree)));
 864       replace_map->old_tree = parm_tree;
 865       replace_map->new_tree = const_val;
 866       replace_map->replace_p = true;
 867       replace_map->ref_p = true;
 868     }
 869   else if (TREE_READONLY (parm_tree) && !TREE_ADDRESSABLE (parm_tree))
 870     {
 871       const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree));
 872       replace_map->old_tree = parm_tree;
 873       replace_map->new_tree = const_val;
 874       replace_map->replace_p = true;
 875       replace_map->ref_p = false;
 876     }
 877   else
 878     {
 879       replace_map->old_tree = NULL;
 880       replace_map->new_tree = NULL;
 881       replace_map->replace_p = false;
 882       replace_map->ref_p = false;
 883     }
 884
 885   return replace_map;
 886 }
 887
 888 /* Return true if this callsite should be redirected to
 889    the orig callee (instead of the cloned one).  */
 890 static bool
 891 ipcp_redirect (struct cgraph_edge *cs)
 892 {
 893   struct cgraph_node *caller, *callee, *orig_callee;
 894   int i, count;
 895   struct ipa_jump_func *jump_func;
 896   enum jump_func_type type;
 897   enum cvalue_type cval_type;
 898
 899   caller = cs->caller;
 900   callee = cs->callee;
 901   orig_callee = ipcp_method_orig_node (callee);
 902   count = ipa_method_formal_count (orig_callee);
 903   for (i = 0; i < count; i++)
 904     {
 905       cval_type =
 906         ipcp_cval_get_cvalue_type (ipcp_method_cval (orig_callee, i));
 907       if (ipcp_type_is_const (cval_type))
 908         {
 909           jump_func = ipa_callsite_param (cs, i);
 910           type = get_type (jump_func);
 911           if (type != CONST_IPATYPE
 912               && type != CONST_IPATYPE_REF)
 913             return true;
 914         }
 915     }
 916
 917   return false;
 918 }
 919
 920 /* Fix the callsites and the callgraph after function cloning was done.  */
 921 static void
 922 ipcp_update_callgraph (void)
 923 {
 924   struct cgraph_node *node, *orig_callee;
 925   struct cgraph_edge *cs;
 926
 927   for (node = cgraph_nodes; node; node = node->next)
 928     {
 929       /* want to fix only original nodes  */
 930       if (ipcp_method_is_cloned (node))
 931         continue;
 932       for (cs = node->callees; cs; cs = cs->next_callee)
 933         if (ipcp_method_is_cloned (cs->callee))
 934           {
 935             /* Callee is a cloned node  */
 936             orig_callee = ipcp_method_orig_node (cs->callee);
 937             if (ipcp_redirect (cs))
 938               {
 939                 cgraph_redirect_edge_callee (cs, orig_callee);
 940                 TREE_OPERAND (TREE_OPERAND
 941                               (get_call_expr_in (cs->call_stmt), 0), 0) =
 942                   orig_callee->decl;
 943               }
 944           }
 945     }
 946 }
 947
 948 /* Update all cfg basic blocks in NODE according to SCALE.  */
 949 static void
 950 ipcp_update_bb_counts (struct cgraph_node *node, gcov_type scale)
 951 {
 952   basic_block bb;
 953
 954   FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 955     bb->count = bb->count * scale / REG_BR_PROB_BASE;
 956 }
 957
 958 /* Update all cfg edges in NODE according to SCALE.  */
 959 static void
 960 ipcp_update_edges_counts (struct cgraph_node *node, gcov_type scale)
 961 {
 962   basic_block bb;
 963   edge_iterator ei;
 964   edge e;
 965
 966   FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 967     FOR_EACH_EDGE (e, ei, bb->succs)
 968     e->count = e->count * scale / REG_BR_PROB_BASE;
 969 }
 970
 971 /* Update profiling info for versioned methods and the
 972    methods they were versioned from.  */
 973 static void
 974 ipcp_update_profiling (void)
 975 {
 976   struct cgraph_node *node, *orig_node;
 977   gcov_type scale, scale_complement;
 978   struct cgraph_edge *cs;
 979
 980   for (node = cgraph_nodes; node; node = node->next)
 981     {
 982       if (ipcp_method_is_cloned (node))
 983         {
 984           orig_node = ipcp_method_orig_node (node);
 985           scale = ipcp_method_get_scale (orig_node);
 986           node->count = orig_node->count * scale / REG_BR_PROB_BASE;
 987           scale_complement = REG_BR_PROB_BASE - scale;
 988           orig_node->count =
 989             orig_node->count * scale_complement / REG_BR_PROB_BASE;
 990           for (cs = node->callees; cs; cs = cs->next_callee)
 991             cs->count = cs->count * scale / REG_BR_PROB_BASE;
 992           for (cs = orig_node->callees; cs; cs = cs->next_callee)
 993             cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
 994           ipcp_update_bb_counts (node, scale);
 995           ipcp_update_bb_counts (orig_node, scale_complement);
 996           ipcp_update_edges_counts (node, scale);
 997           ipcp_update_edges_counts (orig_node, scale_complement);
 998         }
 999     }
1000 }
1001
1002 /* Propagate the constant parameters found by ipcp_iterate_stage()
1003    to the function's code.  */
1004 static void
1005 ipcp_insert_stage (void)
1006 {
1007   struct cgraph_node *node, *node1 = NULL;
1008   int i, const_param;
1009   union parameter_info *cvalue;
1010   VEC(cgraph_edge_p,heap) *redirect_callers;
1011   varray_type replace_trees;
1012   struct cgraph_edge *cs;
1013   int node_callers, count;
1014   tree parm_tree;
1015   enum cvalue_type type;
1016   struct ipa_replace_map *replace_param;
1017
1018   for (node = cgraph_nodes; node; node = node->next)
1019     {
1020       /* Propagation of the constant is forbidden in
1021          certain conditions.  */
1022       if (ipcp_method_dont_insert_const (node))
1023         continue;
1024       const_param = 0;
1025       count = ipa_method_formal_count (node);
1026       for (i = 0; i < count; i++)
1027         {
1028           type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
1029           if (ipcp_type_is_const (type))
1030             const_param++;
1031         }
1032       if (const_param == 0)
1033         continue;
1034       VARRAY_GENERIC_PTR_INIT (replace_trees, const_param, "replace_trees");
1035       for (i = 0; i < count; i++)
1036         {
1037           type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
1038           if (ipcp_type_is_const (type))
1039             {
1040               cvalue = ipcp_cval_get_cvalue (ipcp_method_cval (node, i));
1041               parm_tree = ipa_method_get_tree (node, i);
1042               replace_param =
1043                 ipcp_replace_map_create (type, parm_tree, cvalue);
1044               VARRAY_PUSH_GENERIC_PTR (replace_trees, replace_param);
1045             }
1046         }
1047       /* Compute how many callers node has.  */
1048       node_callers = 0;
1049       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1050         node_callers++;
1051       redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers);
1052       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1053         VEC_quick_push (cgraph_edge_p, redirect_callers, cs);
1054       /* Redirecting all the callers of the node to the
1055          new versioned node.  */
1056       node1 =
1057         cgraph_function_versioning (node, redirect_callers, replace_trees);
1058       VEC_free (cgraph_edge_p, heap, redirect_callers);
1059       VARRAY_CLEAR (replace_trees);
1060       if (node1 == NULL)
1061         continue;
1062       if (dump_file)
1063         fprintf (dump_file, "versioned function %s\n",
1064                  cgraph_node_name (node));
1065       ipcp_cloned_create (node, node1);
1066       for (i = 0; i < count; i++)
1067         {
1068           type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
1069           if (ipcp_type_is_const (type))
1070             {
1071               cvalue = ipcp_cval_get_cvalue (ipcp_method_cval (node, i));
1072               parm_tree = ipa_method_get_tree (node, i);
1073               if (type != CONST_VALUE_REF
1074                   && !TREE_READONLY (parm_tree))
1075                 ipcp_propagate_const (node1, i, cvalue, type);
1076             }
1077         }
1078     }
1079   ipcp_update_callgraph ();
1080   ipcp_update_profiling ();
1081 }
1082
1083 /* The IPCP driver.  */
1084 unsigned int
1085 ipcp_driver (void)
1086 {
1087   if (dump_file)
1088     fprintf (dump_file, "\nIPA constant propagation start:\n");
1089   ipa_nodes_create ();
1090   ipa_edges_create ();
1091   /* 1. Call the init stage to initialize
1092      the ipa_node and ipa_edge structures.  */
1093   ipcp_init_stage ();
1094   if (dump_file)
1095     {
1096       fprintf (dump_file, "\nIPA structures before propagation:\n");
1097       ipcp_structures_print (dump_file);
1098     }
1099   /* 2. Do the interprocedural propagation.  */
1100   ipcp_iterate_stage ();
1101   if (dump_file)
1102     {
1103       fprintf (dump_file, "\nIPA structures after propagation:\n");
1104       ipcp_structures_print (dump_file);
1105       fprintf (dump_file, "\nProfiling info before insert stage:\n");
1106       ipcp_profile_print (dump_file);
1107     }
1108   /* 3. Insert the constants found to the functions.  */
1109   ipcp_insert_stage ();
1110   if (dump_file)
1111     {
1112       fprintf (dump_file, "\nProfiling info after insert stage:\n");
1113       ipcp_profile_print (dump_file);
1114     }
1115   /* Free all IPCP structures.  */
1116   ipa_free ();
1117   ipa_nodes_free ();
1118   ipa_edges_free ();
1119   if (dump_file)
1120     fprintf (dump_file, "\nIPA constant propagation end\n");
1121   cgraph_remove_unreachable_nodes (true, NULL);
1122   return 0;
1123 }
1124
1125 /* Gate for IPCP optimization.  */
1126 static bool
1127 cgraph_gate_cp (void)
1128 {
1129   return flag_ipa_cp;
1130 }
1131
1132 struct tree_opt_pass pass_ipa_cp = {
1133   "cp",                         /* name */
1134   cgraph_gate_cp,               /* gate */
1135   ipcp_driver,                  /* execute */
1136   NULL,                         /* sub */
1137   NULL,                         /* next */
1138   0,                            /* static_pass_number */
1139   TV_IPA_CONSTANT_PROP,         /* tv_id */
1140   0,                            /* properties_required */
1141   PROP_trees,                   /* properties_provided */
1142   0,                            /* properties_destroyed */
1143   0,                            /* todo_flags_start */
1144   TODO_dump_cgraph | TODO_dump_func,    /* todo_flags_finish */
1145   0                             /* letter */
1146 };