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, modified_flags, is defined in ipa_node_params 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_lattice, is defined in ipa_node_params 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_params 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_create_node_params (new_node);
 177   ipcp_method_set_orig_node (new_node, orig_node);
 178   ipa_count_formal_params (new_node);
 179   ipa_create_param_decls_array (new_node);
 180 }
 181
 182 /* Return cval_type field of CVAL.  */
 183 static inline enum ipa_lattice_type
 184 ipcp_cval_get_cvalue_type (struct ipcp_lattice *cval)
 185 {
 186   return 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_lattice *cval, enum jump_func_type type)
 206 {
 207   cval->type = type;
 208 }
 209
 210 /* Return cvalue field of CVAL.  */
 211 static inline tree
 212 ipcp_cval_get_cvalue (struct ipcp_lattice *cval)
 213 {
 214   return cval->constant;
 215 }
 216
 217 /* Set VALUE as cvalue field  CVAL.  */
 218 static inline void
 219 ipcp_cval_set_cvalue (struct ipcp_lattice *cval, tree value,
 220                       enum ipa_lattice_type type)
 221 {
 222   if (type == IPA_CONST_VALUE || type == IPA_CONST_VALUE_REF)
 223     cval->constant = value;
 224 }
 225
 226 /* Return whether TYPE is a constant type.  */
 227 static bool
 228 ipcp_type_is_const (enum ipa_lattice_type type)
 229 {
 230   if (type == IPA_CONST_VALUE || type == IPA_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 (tree const_val1, tree const_val2,
 239                          enum ipa_lattice_type type1,
 240                          enum ipa_lattice_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, const_val2, 0))
 247     return true;
 248
 249   return false;
 250 }
 251
 252 /* Compute Meet arithmetics:
 253    Meet (IPA_BOTTOM, x) = IPA_BOTTOM
 254    Meet (IPA_TOP,x) = x
 255    Meet (const_a,const_b) = IPA_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_lattice *cval, struct ipcp_lattice *cval1,
 259                 struct ipcp_lattice *cval2)
 260 {
 261   if (ipcp_cval_get_cvalue_type (cval1) == IPA_BOTTOM
 262       || ipcp_cval_get_cvalue_type (cval2) == IPA_BOTTOM)
 263     {
 264       ipcp_cval_set_cvalue_type (cval, IPA_BOTTOM);
 265       return;
 266     }
 267   if (ipcp_cval_get_cvalue_type (cval1) == IPA_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) == IPA_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, IPA_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_lattice *
 296 ipcp_method_cval (struct cgraph_node *mt, int info_type)
 297 {
 298   return &(IPA_NODE_REF (mt)->ipcp_lattices[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_lattice *cval, struct cgraph_node *mt,
 306                    enum jump_func_type type,
 307                    union jump_func_value *info_type)
 308 {
 309   if (type == IPA_UNKNOWN)
 310     ipcp_cval_set_cvalue_type (cval, IPA_BOTTOM);
 311   else if (type == IPA_CONST)
 312     {
 313       ipcp_cval_set_cvalue_type (cval, IPA_CONST_VALUE);
 314       ipcp_cval_set_cvalue (cval, info_type->constant, IPA_CONST_VALUE);
 315     }
 316   else if (type == IPA_CONST_REF)
 317     {
 318       ipcp_cval_set_cvalue_type (cval, IPA_CONST_VALUE_REF);
 319       ipcp_cval_set_cvalue (cval, info_type->constant, IPA_CONST_VALUE_REF);
 320     }
 321   else if (type == IPA_PASS_THROUGH)
 322     {
 323       enum ipa_lattice_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_lattice *cval1, struct ipcp_lattice *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) != IPA_CONST_VALUE
 341           && ipcp_cval_get_cvalue_type (cval1) != IPA_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_lattices =
 357     XCNEWVEC (struct ipcp_lattice, ipa_get_param_count (IPA_NODE_REF (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_lattice *cval)
 363 {
 364   IPA_NODE_REF (mt)->ipcp_lattices[i].type = cval->type;
 365   ipcp_cval_set_cvalue (ipcp_method_cval (mt, i),
 366                         ipcp_cval_get_cvalue (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 ipa_lattice_type type)
 373 {
 374   IPA_NODE_REF (mt)->ipcp_lattices[i].type = type;
 375 }
 376
 377 /* Set type of cval structure of formal I of MT to CVAL_TYPE1.  */
 378 static inline void
 379 ipcp_method_cval_set_lattice_type (struct cgraph_node *mt, int i,
 380                                    enum ipa_lattice_type type)
 381 {
 382   IPA_NODE_REF (mt)->ipcp_lattices[i].type = type;
 383 }
 384
 385 /* Print ipcp_cval data structures to F.  */
 386 static void
 387 ipcp_method_cval_print (FILE * f)
 388 {
 389   struct cgraph_node *node;
 390   int i, count;
 391   tree cvalue;
 392
 393   fprintf (f, "\nCVAL PRINT\n");
 394   for (node = cgraph_nodes; node; node = node->next)
 395     {
 396       fprintf (f, "Printing cvals %s:\n", cgraph_node_name (node));
 397       count = ipa_get_param_count (IPA_NODE_REF (node));
 398       for (i = 0; i < count; i++)
 399         {
 400           if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i))
 401               == IPA_CONST_VALUE
 402               || ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) ==
 403               IPA_CONST_VALUE_REF)
 404             {
 405               fprintf (f, " param [%d]: ", i);
 406               fprintf (f, "type is CONST ");
 407               cvalue =
 408                 ipcp_cval_get_cvalue (ipcp_method_cval (node, i));
 409               print_generic_expr (f, cvalue, 0);
 410               fprintf (f, "\n");
 411             }
 412           else if (ipcp_method_cval (node, i)->type == IPA_TOP)
 413             fprintf (f, "param [%d]: type is TOP  \n", i);
 414           else
 415             fprintf (f, "param [%d]: type is BOTTOM  \n", i);
 416         }
 417     }
 418 }
 419
 420 /* Initialize ipcp_cval array of MT with IPA_TOP values.
 421    All cvals for a method's formal parameters are initialized to IPA_BOTTOM
 422    The currently supported types are integer types, real types and
 423    Fortran constants (i.e. references to constants defined as
 424    const_decls). All other types are not analyzed and therefore are
 425    assigned with IPA_BOTTOM.  */
 426 static void
 427 ipcp_method_cval_init (struct cgraph_node *mt)
 428 {
 429   int i;
 430   tree parm_tree;
 431
 432   ipcp_formal_create (mt);
 433   for (i = 0; i < ipa_get_param_count (IPA_NODE_REF (mt)) ; i++)
 434     {
 435       parm_tree = ipa_get_ith_param (IPA_NODE_REF (mt), i);
 436       if (INTEGRAL_TYPE_P (TREE_TYPE (parm_tree))
 437           || SCALAR_FLOAT_TYPE_P (TREE_TYPE (parm_tree))
 438           || POINTER_TYPE_P (TREE_TYPE (parm_tree)))
 439         ipcp_method_cval_set_cvalue_type (mt, i, IPA_TOP);
 440       else
 441         ipcp_method_cval_set_cvalue_type (mt, i, IPA_BOTTOM);
 442     }
 443 }
 444
 445 /* Create a new assignment statment and make
 446    it the first statement in the function FN
 447    tree.
 448    PARM1 is the lhs of the assignment and
 449    VAL is the rhs. */
 450 static void
 451 constant_val_insert (tree parm1, tree val)
 452 {
 453   tree init_stmt = NULL;
 454   edge e_step;
 455
 456   init_stmt = build_gimple_modify_stmt (parm1, val);
 457
 458   if (init_stmt)
 459     {
 460       e_step = single_succ_edge (ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun));
 461       bsi_insert_on_edge_immediate (e_step, init_stmt);
 462     }
 463 }
 464
 465 /* build INTEGER_CST tree with type TREE_TYPE and
 466    value according to CVALUE. Return the tree.   */
 467 static tree
 468 build_const_val (tree cvalue, enum ipa_lattice_type type, tree tree_type)
 469 {
 470   tree const_val = NULL;
 471
 472   gcc_assert (ipcp_type_is_const (type));
 473   const_val = fold_convert (tree_type, cvalue);
 474   return const_val;
 475 }
 476
 477 /* Build the tree representing the constant and call
 478    constant_val_insert().  */
 479 static void
 480 ipcp_propagate_const (struct cgraph_node *mt, int param,
 481                       tree cvalue, enum ipa_lattice_type type)
 482 {
 483   tree const_val;
 484   tree parm_tree;
 485
 486   if (dump_file)
 487     fprintf (dump_file, "propagating const to %s\n", cgraph_node_name (mt));
 488   parm_tree = ipa_get_ith_param (IPA_NODE_REF (mt), param);
 489   const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree));
 490   constant_val_insert (parm_tree, const_val);
 491 }
 492
 493 /* Compute the proper scale for NODE.  It is the ratio between
 494    the number of direct calls (represented on the incoming
 495    cgraph_edges) and sum of all invocations of NODE (represented
 496    as count in cgraph_node). */
 497 static void
 498 ipcp_method_compute_scale (struct cgraph_node *node)
 499 {
 500   gcov_type sum;
 501   struct cgraph_edge *cs;
 502
 503   sum = 0;
 504   /* Compute sum of all counts of callers. */
 505   for (cs = node->callers; cs != NULL; cs = cs->next_caller)
 506     sum += cs->count;
 507   if (node->count == 0)
 508     ipcp_method_set_scale (node, 0);
 509   else
 510     ipcp_method_set_scale (node, sum * REG_BR_PROB_BASE / node->count);
 511 }
 512
 513 /* Initialization and computation of IPCP data structures.
 514    It is an intraprocedural
 515    analysis of methods, which gathers information to be propagated
 516    later on.  */
 517 static void
 518 ipcp_init_stage (void)
 519 {
 520   struct cgraph_node *node;
 521   struct cgraph_edge *cs;
 522
 523   for (node = cgraph_nodes; node; node = node->next)
 524     {
 525       ipa_count_formal_params (node);
 526       ipa_create_param_decls_array (node);
 527       ipcp_method_cval_init (node);
 528       ipa_detect_param_modifications (node);
 529       ipcp_method_compute_scale (node);
 530     }
 531   for (node = cgraph_nodes; node; node = node->next)
 532     {
 533       /* building jump functions  */
 534       for (cs = node->callees; cs; cs = cs->next_callee)
 535         {
 536           ipa_count_arguments (cs);
 537           if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
 538               != ipa_get_param_count (IPA_NODE_REF (cs->callee)))
 539             {
 540               /* Handle cases of functions with
 541                  a variable number of parameters.  */
 542               ipa_set_called_with_variable_arg (IPA_NODE_REF (cs->callee));
 543             }
 544           else
 545             ipa_compute_jump_functions (cs);
 546         }
 547     }
 548 }
 549
 550 /* Return true if there are some formal parameters whose value is IPA_TOP.
 551    Change their values to IPA_BOTTOM, since they weren't determined.  */
 552 static bool
 553 ipcp_after_propagate (void)
 554 {
 555   int i, count;
 556   struct cgraph_node *node;
 557   bool prop_again;
 558
 559   prop_again = false;
 560   for (node = cgraph_nodes; node; node = node->next)
 561     {
 562       count = ipa_get_param_count (IPA_NODE_REF (node));
 563       for (i = 0; i < count; i++)
 564         if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) == IPA_TOP)
 565           {
 566             prop_again = true;
 567             ipcp_method_cval_set_cvalue_type (node, i, IPA_BOTTOM);
 568           }
 569     }
 570   return prop_again;
 571 }
 572
 573 /* Interprocedural analysis. The algorithm propagates constants from
 574    the caller's parameters to the callee's arguments.  */
 575 static void
 576 ipcp_propagate_stage (void)
 577 {
 578   int i;
 579   struct ipcp_lattice cval1 = { IPA_BOTTOM, NULL }, cval = { IPA_BOTTOM, NULL };
 580   struct ipcp_lattice *cval2;
 581   struct cgraph_node *mt, *callee;
 582   struct cgraph_edge *cs;
 583   struct ipa_jump_func *jump_func;
 584   enum jump_func_type type;
 585   union jump_func_value *jf_value;
 586   struct ipa_func_list *wl;
 587   int count;
 588
 589   /* Initialize worklist to contain all functions.  */
 590   wl = ipa_init_func_list ();
 591   while (wl)
 592     {
 593       mt = ipa_pop_func_from_list (&wl);
 594       for (cs = mt->callees; cs; cs = cs->next_callee)
 595         {
 596           callee = cs->callee;
 597           if (ipa_is_called_with_var_arguments (IPA_NODE_REF (callee)))
 598             continue;
 599           count = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
 600           for (i = 0; i < count; i++)
 601             {
 602               jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
 603               type = jump_func->type;
 604               jf_value = &jump_func->value;
 605               ipcp_cval_compute (&cval1, mt, type, jf_value);
 606               cval2 = ipcp_method_cval (callee, i);
 607               ipcp_cval_meet (&cval, &cval1, cval2);
 608               if (ipcp_cval_changed (&cval, cval2))
 609                 {
 610                   ipcp_method_cval_set (callee, i, &cval);
 611                   ipa_push_func_to_list (&wl, callee);
 612                 }
 613             }
 614         }
 615     }
 616 }
 617
 618 /* Call the constant propagation algorithm and re-call it if necessary
 619    (if there are undetermined values left).  */
 620 static void
 621 ipcp_iterate_stage (void)
 622 {
 623   ipcp_propagate_stage ();
 624   if (ipcp_after_propagate ())
 625     /* Some cvals have changed from IPA_TOP to IPA_BOTTOM.
 626        This change should be propagated.  */
 627     ipcp_propagate_stage ();
 628 }
 629
 630 /* Check conditions to forbid constant insertion to MT.  */
 631 static bool
 632 ipcp_method_dont_insert_const (struct cgraph_node *mt)
 633 {
 634   /* ??? Handle pending sizes case.  */
 635   if (DECL_UNINLINABLE (mt->decl))
 636     return true;
 637   return false;
 638 }
 639
 640 /* Print ipa_jump_func data structures to F.  */
 641 static void
 642 ipcp_callsite_param_print (FILE * f)
 643 {
 644   struct cgraph_node *node;
 645   int i, count;
 646   struct cgraph_edge *cs;
 647   struct ipa_jump_func *jump_func;
 648   enum jump_func_type type;
 649   tree info_type;
 650
 651   fprintf (f, "\nCALLSITE PARAM PRINT\n");
 652   for (node = cgraph_nodes; node; node = node->next)
 653     {
 654       for (cs = node->callees; cs; cs = cs->next_callee)
 655         {
 656           fprintf (f, "callsite  %s ", cgraph_node_name (node));
 657           fprintf (f, "-> %s :: \n", cgraph_node_name (cs->callee));
 658
 659           if (ipa_is_called_with_var_arguments (IPA_NODE_REF (cs->callee)))
 660             continue;
 661
 662           count = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
 663           for (i = 0; i < count; i++)
 664             {
 665               jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
 666               type = jump_func->type;
 667
 668               fprintf (f, " param %d: ", i);
 669               if (type == IPA_UNKNOWN)
 670                 fprintf (f, "UNKNOWN\n");
 671               else if (type == IPA_CONST || type == IPA_CONST_REF)
 672                 {
 673                   info_type = jump_func->value.constant;
 674                   fprintf (f, "CONST : ");
 675                   print_generic_expr (f, info_type, 0);
 676                   fprintf (f, "\n");
 677                 }
 678               else if (type == IPA_PASS_THROUGH)
 679                 {
 680                   fprintf (f, "PASS THROUGH : ");
 681                   fprintf (f, "%d\n", jump_func->value.formal_id);
 682                 }
 683             }
 684         }
 685     }
 686 }
 687
 688 /* Print count scale data structures.  */
 689 static void
 690 ipcp_method_scale_print (FILE * f)
 691 {
 692   struct cgraph_node *node;
 693
 694   for (node = cgraph_nodes; node; node = node->next)
 695     {
 696       fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
 697       fprintf (f, "value is  " HOST_WIDE_INT_PRINT_DEC
 698                "  \n", (HOST_WIDE_INT) ipcp_method_get_scale (node));
 699     }
 700 }
 701
 702 /* Print counts of all cgraph nodes.  */
 703 static void
 704 ipcp_profile_mt_count_print (FILE * f)
 705 {
 706   struct cgraph_node *node;
 707
 708   for (node = cgraph_nodes; node; node = node->next)
 709     {
 710       fprintf (f, "method %s: ", cgraph_node_name (node));
 711       fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC
 712                "  \n", (HOST_WIDE_INT) node->count);
 713     }
 714 }
 715
 716 /* Print counts of all cgraph edges.  */
 717 static void
 718 ipcp_profile_cs_count_print (FILE * f)
 719 {
 720   struct cgraph_node *node;
 721   struct cgraph_edge *cs;
 722
 723   for (node = cgraph_nodes; node; node = node->next)
 724     {
 725       for (cs = node->callees; cs; cs = cs->next_callee)
 726         {
 727           fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
 728                    cgraph_node_name (cs->callee));
 729           fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC "  \n",
 730                    (HOST_WIDE_INT) cs->count);
 731         }
 732     }
 733 }
 734
 735 /* Print all counts and probabilities of cfg edges of all methods.  */
 736 static void
 737 ipcp_profile_edge_print (FILE * f)
 738 {
 739   struct cgraph_node *node;
 740   basic_block bb;
 741   edge_iterator ei;
 742   edge e;
 743
 744   for (node = cgraph_nodes; node; node = node->next)
 745     {
 746       fprintf (f, "method %s: \n", cgraph_node_name (node));
 747       if (DECL_SAVED_TREE (node->decl))
 748         {
 749           bb =
 750             ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 751           fprintf (f, "ENTRY: ");
 752           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 753                    " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
 754
 755           if (bb->succs)
 756             FOR_EACH_EDGE (e, ei, bb->succs)
 757             {
 758               if (e->dest ==
 759                   EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
 760                                                (node->decl)))
 761                 fprintf (f, "edge ENTRY -> EXIT,  Count");
 762               else
 763                 fprintf (f, "edge ENTRY -> %d,  Count", e->dest->index);
 764               fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 765                        " Prob %d\n", (HOST_WIDE_INT) e->count,
 766                        e->probability);
 767             }
 768           FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 769           {
 770             fprintf (f, "bb[%d]: ", bb->index);
 771             fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 772                      " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
 773             FOR_EACH_EDGE (e, ei, bb->succs)
 774             {
 775               if (e->dest ==
 776                   EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
 777                                                (node->decl)))
 778                 fprintf (f, "edge %d -> EXIT,  Count", e->src->index);
 779               else
 780                 fprintf (f, "edge %d -> %d,  Count", e->src->index,
 781                          e->dest->index);
 782               fprintf (f, " " HOST_WIDE_INT_PRINT_DEC " Prob %d\n",
 783                        (HOST_WIDE_INT) e->count, e->probability);
 784             }
 785           }
 786         }
 787     }
 788 }
 789
 790 /* Print counts and frequencies for all basic blocks of all methods.  */
 791 static void
 792 ipcp_profile_bb_print (FILE * f)
 793 {
 794   basic_block bb;
 795   struct cgraph_node *node;
 796
 797   for (node = cgraph_nodes; node; node = node->next)
 798     {
 799       fprintf (f, "method %s: \n", cgraph_node_name (node));
 800       if (node->analyzed)
 801         {
 802           bb =
 803             ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 804           fprintf (f, "ENTRY: Count");
 805           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 806                    " Frequency  %d\n", (HOST_WIDE_INT) bb->count,
 807                    bb->frequency);
 808
 809           FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 810           {
 811             fprintf (f, "bb[%d]: Count", bb->index);
 812             fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 813                      " Frequency %d\n", (HOST_WIDE_INT) bb->count,
 814                      bb->frequency);
 815           }
 816           bb =
 817             EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
 818           fprintf (f, "EXIT: Count");
 819           fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
 820                    " Frequency %d\n", (HOST_WIDE_INT) bb->count,
 821                    bb->frequency);
 822
 823         }
 824     }
 825 }
 826
 827 /* Print all IPCP data structures to F.  */
 828 static void
 829 ipcp_structures_print (FILE * f)
 830 {
 831   ipcp_method_cval_print (f);
 832   ipcp_method_scale_print (f);
 833   ipa_print_all_tree_maps (f);
 834   ipa_print_all_params_modified (f);
 835   ipcp_callsite_param_print (f);
 836 }
 837
 838 /* Print profile info for all methods.  */
 839 static void
 840 ipcp_profile_print (FILE * f)
 841 {
 842   fprintf (f, "\nNODE COUNTS :\n");
 843   ipcp_profile_mt_count_print (f);
 844   fprintf (f, "\nCS COUNTS stage:\n");
 845   ipcp_profile_cs_count_print (f);
 846   fprintf (f, "\nBB COUNTS and FREQUENCIES :\n");
 847   ipcp_profile_bb_print (f);
 848   fprintf (f, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
 849   ipcp_profile_edge_print (f);
 850 }
 851
 852 /* Build and initialize ipa_replace_map struct
 853    according to TYPE. This struct is read by versioning, which
 854    operates according to the flags sent.  PARM_TREE is the
 855    formal's tree found to be constant.  CVALUE represents the constant.  */
 856 static struct ipa_replace_map *
 857 ipcp_replace_map_create (struct function *func, enum ipa_lattice_type type,
 858                          tree parm_tree, tree cvalue)
 859 {
 860   struct ipa_replace_map *replace_map;
 861   tree const_val;
 862
 863   replace_map = XCNEW (struct ipa_replace_map);
 864   gcc_assert (ipcp_type_is_const (type));
 865   if (type != IPA_CONST_VALUE_REF
 866       && is_gimple_reg (parm_tree) && gimple_default_def (func, parm_tree)
 867         && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_default_def (func, parm_tree)))
 868     {
 869       if (dump_file)
 870         fprintf (dump_file, "replacing param with const\n");
 871       const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree));
 872       replace_map->old_tree =gimple_default_def (func, 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 ipa_lattice_type lattice_type;
 898
 899   caller = cs->caller;
 900   callee = cs->callee;
 901   orig_callee = ipcp_method_orig_node (callee);
 902   count = ipa_get_param_count (IPA_NODE_REF (orig_callee));
 903   for (i = 0; i < count; i++)
 904     {
 905       lattice_type =
 906         ipcp_cval_get_cvalue_type (ipcp_method_cval (orig_callee, i));
 907       if (ipcp_type_is_const (lattice_type))
 908         {
 909           jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
 910           type = jump_func->type;
 911           if (type != IPA_CONST && type != IPA_CONST_REF)
 912             return true;
 913         }
 914     }
 915
 916   return false;
 917 }
 918
 919 /* Fix the callsites and the callgraph after function cloning was done.  */
 920 static void
 921 ipcp_update_callgraph (void)
 922 {
 923   struct cgraph_node *node, *orig_callee;
 924   struct cgraph_edge *cs;
 925
 926   for (node = cgraph_nodes; node; node = node->next)
 927     {
 928       /* want to fix only original nodes  */
 929       if (ipcp_method_is_cloned (node))
 930         continue;
 931       for (cs = node->callees; cs; cs = cs->next_callee)
 932         if (ipcp_method_is_cloned (cs->callee))
 933           {
 934             /* Callee is a cloned node  */
 935             orig_callee = ipcp_method_orig_node (cs->callee);
 936             if (ipcp_redirect (cs))
 937               {
 938                 cgraph_redirect_edge_callee (cs, orig_callee);
 939                 TREE_OPERAND (CALL_EXPR_FN (get_call_expr_in (cs->call_stmt)),
 940                               0) =
 941                   orig_callee->decl;
 942               }
 943           }
 944     }
 945 }
 946
 947 /* Update all cfg basic blocks in NODE according to SCALE.  */
 948 static void
 949 ipcp_update_bb_counts (struct cgraph_node *node, gcov_type scale)
 950 {
 951   basic_block bb;
 952
 953   FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 954     bb->count = bb->count * scale / REG_BR_PROB_BASE;
 955 }
 956
 957 /* Update all cfg edges in NODE according to SCALE.  */
 958 static void
 959 ipcp_update_edges_counts (struct cgraph_node *node, gcov_type scale)
 960 {
 961   basic_block bb;
 962   edge_iterator ei;
 963   edge e;
 964
 965   FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 966     FOR_EACH_EDGE (e, ei, bb->succs)
 967     e->count = e->count * scale / REG_BR_PROB_BASE;
 968 }
 969
 970 /* Update profiling info for versioned methods and the
 971    methods they were versioned from.  */
 972 static void
 973 ipcp_update_profiling (void)
 974 {
 975   struct cgraph_node *node, *orig_node;
 976   gcov_type scale, scale_complement;
 977   struct cgraph_edge *cs;
 978
 979   for (node = cgraph_nodes; node; node = node->next)
 980     {
 981       if (ipcp_method_is_cloned (node))
 982         {
 983           orig_node = ipcp_method_orig_node (node);
 984           scale = ipcp_method_get_scale (orig_node);
 985           node->count = orig_node->count * scale / REG_BR_PROB_BASE;
 986           scale_complement = REG_BR_PROB_BASE - scale;
 987           orig_node->count =
 988             orig_node->count * scale_complement / REG_BR_PROB_BASE;
 989           for (cs = node->callees; cs; cs = cs->next_callee)
 990             cs->count = cs->count * scale / REG_BR_PROB_BASE;
 991           for (cs = orig_node->callees; cs; cs = cs->next_callee)
 992             cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
 993           ipcp_update_bb_counts (node, scale);
 994           ipcp_update_bb_counts (orig_node, scale_complement);
 995           ipcp_update_edges_counts (node, scale);
 996           ipcp_update_edges_counts (orig_node, scale_complement);
 997         }
 998     }
 999 }
1000
1001 /* Propagate the constant parameters found by ipcp_iterate_stage()
1002    to the function's code.  */
1003 static void
1004 ipcp_insert_stage (void)
1005 {
1006   struct cgraph_node *node, *node1 = NULL;
1007   int i, const_param;
1008   tree cvalue;
1009   VEC (cgraph_edge_p, heap) * redirect_callers;
1010   varray_type replace_trees;
1011   struct cgraph_edge *cs;
1012   int node_callers, count;
1013   tree parm_tree;
1014   enum ipa_lattice_type type;
1015   struct ipa_replace_map *replace_param;
1016
1017   for (node = cgraph_nodes; node; node = node->next)
1018     {
1019       /* Propagation of the constant is forbidden in
1020          certain conditions.  */
1021       if (!node->analyzed || ipcp_method_dont_insert_const (node)
1022           || ipa_is_called_with_var_arguments (IPA_NODE_REF (node)))
1023         continue;
1024       const_param = 0;
1025       count = ipa_get_param_count (IPA_NODE_REF (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_get_ith_param (IPA_NODE_REF (node), i);
1042               replace_param =
1043                 ipcp_replace_map_create (DECL_STRUCT_FUNCTION (node->decl),
1044                                          type, parm_tree, cvalue);
1045               VARRAY_PUSH_GENERIC_PTR (replace_trees, replace_param);
1046             }
1047         }
1048       /* Compute how many callers node has.  */
1049       node_callers = 0;
1050       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1051         node_callers++;
1052       redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers);
1053       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1054         VEC_quick_push (cgraph_edge_p, redirect_callers, cs);
1055       /* Redirecting all the callers of the node to the
1056          new versioned node.  */
1057       node1 =
1058         cgraph_function_versioning (node, redirect_callers, replace_trees);
1059       VEC_free (cgraph_edge_p, heap, redirect_callers);
1060       VARRAY_CLEAR (replace_trees);
1061       if (node1 == NULL)
1062         continue;
1063       if (dump_file)
1064         fprintf (dump_file, "versioned function %s\n",
1065                  cgraph_node_name (node));
1066       ipcp_cloned_create (node, node1);
1067       if (const_param > 0)
1068         {
1069           push_cfun (DECL_STRUCT_FUNCTION (node1->decl));
1070           tree_register_cfg_hooks ();
1071           current_function_decl = node1->decl;
1072
1073           for (i = 0; i < count; i++)
1074             {
1075               type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
1076               if (ipcp_type_is_const (type))
1077                 {
1078                   cvalue = ipcp_cval_get_cvalue (ipcp_method_cval (node, i));
1079                   parm_tree = ipa_get_ith_param (IPA_NODE_REF (node), i);
1080                   if (type != IPA_CONST_VALUE_REF && !is_gimple_reg (parm_tree))
1081                     ipcp_propagate_const (node1, i, cvalue, type);
1082                 }
1083             }
1084           if (gimple_in_ssa_p (cfun))
1085             {
1086               update_ssa (TODO_update_ssa);
1087 #ifdef   ENABLE_CHECKING
1088               verify_ssa (true);
1089 #endif
1090             }
1091           free_dominance_info (CDI_DOMINATORS);
1092           free_dominance_info (CDI_POST_DOMINATORS);
1093           pop_cfun ();
1094           current_function_decl = NULL;
1095         }
1096       if (dump_file)
1097         dump_function_to_file (node1->decl, dump_file, dump_flags);
1098     }
1099   ipcp_update_callgraph ();
1100   ipcp_update_profiling ();
1101 }
1102
1103 /* The IPCP driver.  */
1104 static unsigned int
1105 ipcp_driver (void)
1106 {
1107   if (dump_file)
1108     fprintf (dump_file, "\nIPA constant propagation start:\n");
1109   ipa_create_all_node_params ();
1110   ipa_create_all_edge_args ();
1111   /* 1. Call the init stage to initialize
1112      the ipa_node_params and ipa_edge_args structures.  */
1113   ipcp_init_stage ();
1114   if (dump_file)
1115     {
1116       fprintf (dump_file, "\nIPA structures before propagation:\n");
1117       ipcp_structures_print (dump_file);
1118     }
1119   /* 2. Do the interprocedural propagation.  */
1120   ipcp_iterate_stage ();
1121   if (dump_file)
1122     {
1123       fprintf (dump_file, "\nIPA structures after propagation:\n");
1124       ipcp_structures_print (dump_file);
1125       fprintf (dump_file, "\nProfiling info before insert stage:\n");
1126       ipcp_profile_print (dump_file);
1127     }
1128   /* 3. Insert the constants found to the functions.  */
1129   ipcp_insert_stage ();
1130   if (dump_file)
1131     {
1132       fprintf (dump_file, "\nProfiling info after insert stage:\n");
1133       ipcp_profile_print (dump_file);
1134     }
1135   /* Free all IPCP structures.  */
1136   ipa_free_all_node_params ();
1137   ipa_free_all_edge_args ();
1138   if (dump_file)
1139     fprintf (dump_file, "\nIPA constant propagation end\n");
1140   cgraph_remove_unreachable_nodes (true, NULL);
1141   return 0;
1142 }
1143
1144 /* Gate for IPCP optimization.  */
1145 static bool
1146 cgraph_gate_cp (void)
1147 {
1148   return flag_ipa_cp;
1149 }
1150
1151 struct simple_ipa_opt_pass pass_ipa_cp =
1152 {
1153  {
1154   SIMPLE_IPA_PASS,
1155   "cp",                         /* name */
1156   cgraph_gate_cp,               /* gate */
1157   ipcp_driver,                  /* execute */
1158   NULL,                         /* sub */
1159   NULL,                         /* next */
1160   0,                            /* static_pass_number */
1161   TV_IPA_CONSTANT_PROP,         /* tv_id */
1162   0,                            /* properties_required */
1163   PROP_trees,                   /* properties_provided */
1164   0,                            /* properties_destroyed */
1165   0,                            /* todo_flags_start */
1166   TODO_dump_cgraph | TODO_dump_func     /* todo_flags_finish */
1167  }
1168 };