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