gcc/ipa-cp.c

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