gcc/ipa-prop.c

   1 /* Interprocedural analyses.
   2    Copyright (C) 2005, 2007 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tree.h"
  24 #include "langhooks.h"
  25 #include "ggc.h"
  26 #include "target.h"
  27 #include "cgraph.h"
  28 #include "ipa-prop.h"
  29 #include "tree-flow.h"
  30 #include "tree-pass.h"
  31 #include "tree-inline.h"
  32 #include "flags.h"
  33 #include "timevar.h"
  34 #include "flags.h"
  35 #include "diagnostic.h"
  36
  37 /* Vector where the parameter infos are actually stored. */
  38 VEC (ipa_node_params_t, heap) *ipa_node_params_vector;
  39 /* Vector where the parameter infos are actually stored. */
  40 VEC (ipa_edge_args_t, heap) *ipa_edge_args_vector;
  41
  42 /* Holders of ipa cgraph hooks: */
  43 static struct cgraph_edge_hook_list *edge_removal_hook_holder;
  44 static struct cgraph_node_hook_list *node_removal_hook_holder;
  45 static struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
  46 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
  47
  48 /* Initialize worklist to contain all functions.  */
  49
  50 struct ipa_func_list *
  51 ipa_init_func_list (void)
  52 {
  53   struct cgraph_node *node;
  54   struct ipa_func_list * wl;
  55
  56   wl = NULL;
  57   for (node = cgraph_nodes; node; node = node->next)
  58     if (node->analyzed)
  59       {
  60         /* Unreachable nodes should have been eliminated before ipcp and
  61            inlining.  */
  62         gcc_assert (node->needed || node->reachable);
  63         ipa_push_func_to_list (&wl, node);
  64       }
  65
  66   return wl;
  67 }
  68
  69 /* Add cgraph node MT to the worklist. Set worklist element WL
  70    to point to MT.  */
  71
  72 void
  73 ipa_push_func_to_list (struct ipa_func_list **wl, struct cgraph_node *mt)
  74 {
  75   struct ipa_func_list *temp;
  76
  77   temp = XCNEW (struct ipa_func_list);
  78   temp->node = mt;
  79   temp->next = *wl;
  80   *wl = temp;
  81 }
  82
  83 /* Remove a function from the worklist. WL points to the first
  84    element in the list, which is removed.  */
  85
  86 struct cgraph_node *
  87 ipa_pop_func_from_list (struct ipa_func_list ** wl)
  88 {
  89   struct ipa_func_list *first;
  90   struct cgraph_node *return_func;
  91
  92   first = *wl;
  93   *wl = (*wl)->next;
  94   return_func = first->node;
  95   free (first);
  96   return return_func;
  97 }
  98
  99 /* Return index of the formal whose tree is PTREE in function which corresponds
 100    to INFO.  */
 101
 102 static int
 103 ipa_get_param_decl_index (struct ipa_node_params *info, tree ptree)
 104 {
 105   int i, count;
 106
 107   count = ipa_get_param_count (info);
 108   for (i = 0; i < count; i++)
 109     if (ipa_get_param(info, i) == ptree)
 110       return i;
 111
 112   return -1;
 113 }
 114
 115 /* Populate the param_decl field in parameter descriptors of INFO that
 116    corresponds to NODE.  */
 117
 118 static void
 119 ipa_populate_param_decls (struct cgraph_node *node,
 120                           struct ipa_node_params *info)
 121 {
 122   tree fndecl;
 123   tree fnargs;
 124   tree parm;
 125   int param_num;
 126
 127   fndecl = node->decl;
 128   fnargs = DECL_ARGUMENTS (fndecl);
 129   param_num = 0;
 130   for (parm = fnargs; parm; parm = TREE_CHAIN (parm))
 131     {
 132       info->params[param_num].decl = parm;
 133       param_num++;
 134     }
 135 }
 136
 137 /* Count number of formal parameters in NOTE. Store the result to the
 138    appropriate field of INFO.  */
 139
 140 static void
 141 ipa_count_formal_params (struct cgraph_node *node,
 142                          struct ipa_node_params *info)
 143 {
 144   tree fndecl;
 145   tree fnargs;
 146   tree parm;
 147   int param_num;
 148
 149   fndecl = node->decl;
 150   fnargs = DECL_ARGUMENTS (fndecl);
 151   param_num = 0;
 152   for (parm = fnargs; parm; parm = TREE_CHAIN (parm))
 153     param_num++;
 154   ipa_set_param_count (info, param_num);
 155 }
 156
 157 /* Initialize the ipa_node_params structure associated with NODE by counting
 158    the function parameters, creating the descriptors and populating their
 159    param_decls.  */
 160
 161 void
 162 ipa_initialize_node_params (struct cgraph_node *node)
 163 {
 164   struct ipa_node_params *info = IPA_NODE_REF (node);
 165
 166   if (!info->params)
 167     {
 168       ipa_count_formal_params (node, info);
 169       info->params = XCNEWVEC (struct ipa_param_descriptor,
 170                                     ipa_get_param_count (info));
 171       ipa_populate_param_decls (node, info);
 172     }
 173 }
 174
 175 /* Check STMT to detect whether a formal parameter is directly modified within
 176    STMT, the appropriate entry is updated in the modified flags of INFO.
 177    Directly means that this function does not check for modifications through
 178    pointers or escaping addresses because all TREE_ADDRESSABLE parameters are
 179    considered modified anyway.  */
 180
 181 static void
 182 ipa_check_stmt_modifications (struct ipa_node_params *info, gimple stmt)
 183 {
 184   int j;
 185   int index;
 186   tree lhs;
 187
 188   switch (gimple_code (stmt))
 189     {
 190     case GIMPLE_ASSIGN:
 191       lhs = gimple_assign_lhs (stmt);
 192
 193       while (handled_component_p (lhs))
 194         lhs = TREE_OPERAND (lhs, 0);
 195       if (TREE_CODE (lhs) == SSA_NAME)
 196         lhs = SSA_NAME_VAR (lhs);
 197       index = ipa_get_param_decl_index (info, lhs);
 198       if (index >= 0)
 199         info->params[index].modified = true;
 200       break;
 201
 202     case GIMPLE_ASM:
 203       /* Asm code could modify any of the parameters.  */
 204       for (j = 0; j < ipa_get_param_count (info); j++)
 205         info->params[j].modified = true;
 206       break;
 207
 208     default:
 209       break;
 210     }
 211 }
 212
 213 /* Compute which formal parameters of function associated with NODE are locally
 214    modified.  Parameters may be modified in NODE if they are TREE_ADDRESSABLE,
 215    if they appear on the left hand side of an assignment or if there is an
 216    ASM_EXPR in the function.  */
 217
 218 void
 219 ipa_detect_param_modifications (struct cgraph_node *node)
 220 {
 221   tree decl = node->decl;
 222   basic_block bb;
 223   struct function *func;
 224   gimple_stmt_iterator gsi;
 225   gimple stmt;
 226   struct ipa_node_params *info = IPA_NODE_REF (node);
 227   int i, count;
 228
 229   if (ipa_get_param_count (info) == 0 || info->modification_analysis_done)
 230     return;
 231
 232   func = DECL_STRUCT_FUNCTION (decl);
 233   FOR_EACH_BB_FN (bb, func)
 234     {
 235       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 236         {
 237           stmt = gsi_stmt (gsi);
 238           ipa_check_stmt_modifications (info, stmt);
 239         }
 240     }
 241
 242   count = ipa_get_param_count (info);
 243   for (i = 0; i < count; i++)
 244     if (TREE_ADDRESSABLE (ipa_get_param (info, i)))
 245       info->params[i].modified = true;
 246
 247   info->modification_analysis_done = 1;
 248 }
 249
 250 /* Count number of arguments callsite CS has and store it in
 251    ipa_edge_args structure corresponding to this callsite.  */
 252
 253 void
 254 ipa_count_arguments (struct cgraph_edge *cs)
 255 {
 256   gimple stmt;
 257   int arg_num;
 258
 259   stmt = cs->call_stmt;
 260   gcc_assert (is_gimple_call (stmt));
 261   arg_num = gimple_call_num_args (stmt);
 262   if (VEC_length (ipa_edge_args_t, ipa_edge_args_vector)
 263       <= (unsigned) cgraph_edge_max_uid)
 264     VEC_safe_grow_cleared (ipa_edge_args_t, heap,
 265                            ipa_edge_args_vector, cgraph_edge_max_uid + 1);
 266   ipa_set_cs_argument_count (IPA_EDGE_REF (cs), arg_num);
 267 }
 268
 269 /* Print the jump functions of all arguments on all call graph edges going from
 270    NODE to file F.  */
 271
 272 void
 273 ipa_print_node_jump_functions (FILE *f, struct cgraph_node *node)
 274 {
 275   int i, count;
 276   struct cgraph_edge *cs;
 277   struct ipa_jump_func *jump_func;
 278   enum jump_func_type type;
 279
 280   fprintf (f, "  Jump functions of caller  %s:\n", cgraph_node_name (node));
 281   for (cs = node->callees; cs; cs = cs->next_callee)
 282     {
 283       if (!ipa_edge_args_info_available_for_edge_p (cs))
 284         continue;
 285
 286       fprintf (f, "    callsite  %s ", cgraph_node_name (node));
 287       fprintf (f, "-> %s :: \n", cgraph_node_name (cs->callee));
 288
 289       count = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
 290       for (i = 0; i < count; i++)
 291         {
 292           jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
 293           type = jump_func->type;
 294
 295           fprintf (f, "       param %d: ", i);
 296           if (type == IPA_UNKNOWN)
 297             fprintf (f, "UNKNOWN\n");
 298           else if (type == IPA_CONST)
 299             {
 300               tree val = jump_func->value.constant;
 301               fprintf (f, "CONST: ");
 302               print_generic_expr (f, val, 0);
 303               fprintf (f, "\n");
 304             }
 305           else if (type == IPA_CONST_MEMBER_PTR)
 306             {
 307               fprintf (f, "CONST MEMBER PTR: ");
 308               print_generic_expr (f, jump_func->value.member_cst.pfn, 0);
 309               fprintf (f, ", ");
 310               print_generic_expr (f, jump_func->value.member_cst.delta, 0);
 311               fprintf (f, "\n");
 312             }
 313           else if (type == IPA_PASS_THROUGH)
 314             {
 315               fprintf (f, "PASS THROUGH: ");
 316               fprintf (f, "%d\n", jump_func->value.formal_id);
 317             }
 318         }
 319     }
 320 }
 321
 322 /* Print ipa_jump_func data structures of all nodes in the call graph to F.  */
 323
 324 void
 325 ipa_print_all_jump_functions (FILE *f)
 326 {
 327   struct cgraph_node *node;
 328
 329   fprintf (f, "\nJump functions:\n");
 330   for (node = cgraph_nodes; node; node = node->next)
 331     {
 332       ipa_print_node_jump_functions (f, node);
 333     }
 334 }
 335
 336 /* Determine the jump functions of scalar arguments.  Scalar means SSA names
 337    and constants of a number of selected types.  INFO is the ipa_node_params
 338    structure associated with the caller, FUNCTIONS is a pointer to an array of
 339    jump function structures associated with CALL which is the call statement
 340    being examined.*/
 341
 342 static void
 343 compute_scalar_jump_functions (struct ipa_node_params *info,
 344                                struct ipa_jump_func *functions,
 345                                gimple call)
 346 {
 347   tree arg;
 348   unsigned num = 0;
 349
 350   for (num = 0; num < gimple_call_num_args (call); num++)
 351     {
 352       arg = gimple_call_arg (call, num);
 353
 354       if (is_gimple_ip_invariant (arg))
 355         {
 356           functions[num].type = IPA_CONST;
 357           functions[num].value.constant = arg;
 358         }
 359       else if ((TREE_CODE (arg) == SSA_NAME) && SSA_NAME_IS_DEFAULT_DEF (arg))
 360         {
 361           int index = ipa_get_param_decl_index (info, SSA_NAME_VAR (arg));
 362
 363           if (index >= 0)
 364             {
 365               functions[num].type = IPA_PASS_THROUGH;
 366               functions[num].value.formal_id = index;
 367             }
 368         }
 369     }
 370 }
 371
 372 /* Inspect the given TYPE and return true iff it has the same structure (the
 373    same number of fields of the same types) as a C++ member pointer.  If
 374    METHOD_PTR and DELTA are non-NULL, store the trees representing the
 375    corresponding fields there.  */
 376
 377 static bool
 378 type_like_member_ptr_p (tree type, tree *method_ptr, tree *delta)
 379 {
 380   tree fld;
 381
 382   if (TREE_CODE (type) != RECORD_TYPE)
 383     return false;
 384
 385   fld = TYPE_FIELDS (type);
 386   if (!fld || !POINTER_TYPE_P (TREE_TYPE (fld))
 387       || TREE_CODE (TREE_TYPE (TREE_TYPE (fld))) != METHOD_TYPE)
 388     return false;
 389
 390   if (method_ptr)
 391     *method_ptr = fld;
 392
 393   fld = TREE_CHAIN (fld);
 394   if (!fld || INTEGRAL_TYPE_P (fld))
 395     return false;
 396   if (delta)
 397     *delta = fld;
 398
 399   if (TREE_CHAIN (fld))
 400     return false;
 401
 402   return true;
 403 }
 404
 405 /* Go through arguments of the CALL and for every one that looks like a member
 406    pointer, check whether it can be safely declared pass-through and if so,
 407    mark that to the corresponding item of jump FUNCTIONS.  Return true iff
 408    there are non-pass-through member pointers within the arguments.  INFO
 409    describes formal parameters of the caller.  */
 410
 411 static bool
 412 compute_pass_through_member_ptrs (struct ipa_node_params *info,
 413                                   struct ipa_jump_func *functions,
 414                                   gimple call)
 415 {
 416   bool undecided_members = false;
 417   unsigned num;
 418   tree arg;
 419
 420   for (num = 0; num < gimple_call_num_args (call); num++)
 421     {
 422       arg = gimple_call_arg (call, num);
 423
 424       if (type_like_member_ptr_p (TREE_TYPE (arg), NULL, NULL))
 425         {
 426           if (TREE_CODE (arg) == PARM_DECL)
 427             {
 428               int index = ipa_get_param_decl_index (info, arg);
 429
 430               gcc_assert (index >=0);
 431               if (!ipa_is_param_modified (info, index))
 432                 {
 433                   functions[num].type = IPA_PASS_THROUGH;
 434                   functions[num].value.formal_id = index;
 435                 }
 436               else
 437                 undecided_members = true;
 438             }
 439           else
 440             undecided_members = true;
 441         }
 442     }
 443
 444   return undecided_members;
 445 }
 446
 447 /* Simple function filling in a member pointer constant jump function (with PFN
 448    and DELTA as the constant value) into JFUNC.  */
 449
 450 static void
 451 fill_member_ptr_cst_jump_function (struct ipa_jump_func *jfunc,
 452                                    tree pfn, tree delta)
 453 {
 454   jfunc->type = IPA_CONST_MEMBER_PTR;
 455   jfunc->value.member_cst.pfn = pfn;
 456   jfunc->value.member_cst.delta = delta;
 457 }
 458
 459 /* Traverse statements from CALL backwards, scanning whether the argument ARG
 460    which is a member pointer is filled in with constant values.  If it is, fill
 461    the jump function JFUNC in appropriately.  METHOD_FIELD and DELTA_FIELD are
 462    fields of the record type of the member pointer.  To give an example, we
 463    look for a pattern looking like the following:
 464
 465      D.2515.__pfn ={v} printStuff;
 466      D.2515.__delta ={v} 0;
 467      i_1 = doprinting (D.2515);  */
 468
 469 static void
 470 determine_cst_member_ptr (gimple call, tree arg, tree method_field,
 471                           tree delta_field, struct ipa_jump_func *jfunc)
 472 {
 473   gimple_stmt_iterator gsi;
 474   tree method = NULL_TREE;
 475   tree delta = NULL_TREE;
 476
 477   gsi = gsi_for_stmt (call);
 478
 479   gsi_prev (&gsi);
 480   for (; !gsi_end_p (gsi); gsi_prev (&gsi))
 481     {
 482       gimple stmt = gsi_stmt (gsi);
 483       tree lhs, rhs, fld;
 484
 485       if (!is_gimple_assign (stmt) || gimple_num_ops (stmt) != 2)
 486         return;
 487
 488       lhs = gimple_assign_lhs (stmt);
 489       rhs = gimple_assign_rhs1 (stmt);
 490
 491       if (TREE_CODE (lhs) != COMPONENT_REF
 492           || TREE_OPERAND (lhs, 0) != arg)
 493         continue;
 494
 495       fld = TREE_OPERAND (lhs, 1);
 496       if (!method && fld == method_field)
 497         {
 498           if (TREE_CODE (rhs) == ADDR_EXPR
 499               && TREE_CODE (TREE_OPERAND (rhs, 0)) == FUNCTION_DECL
 500               && TREE_CODE (TREE_TYPE (TREE_OPERAND (rhs, 0))) == METHOD_TYPE)
 501             {
 502               method = TREE_OPERAND (rhs, 0);
 503               if (delta)
 504                 {
 505                   fill_member_ptr_cst_jump_function (jfunc, rhs, delta);
 506                   return;
 507                 }
 508             }
 509           else
 510             return;
 511         }
 512
 513       if (!delta && fld == delta_field)
 514         {
 515           if (TREE_CODE (rhs) == INTEGER_CST)
 516             {
 517               delta = rhs;
 518               if (method)
 519                 {
 520                   fill_member_ptr_cst_jump_function (jfunc, rhs, delta);
 521                   return;
 522                 }
 523             }
 524           else
 525             return;
 526         }
 527     }
 528
 529   return;
 530 }
 531
 532 /* Go through the arguments of the CALL and for every member pointer within
 533    tries determine whether it is a constant.  If it is, create a corresponding
 534    constant jump function in FUNCTIONS which is an array of jump functions
 535    associated with the call.  */
 536
 537 static void
 538 compute_cst_member_ptr_arguments (struct ipa_jump_func *functions,
 539                                   gimple call)
 540 {
 541   unsigned num;
 542   tree arg, method_field, delta_field;
 543
 544   for (num = 0; num < gimple_call_num_args (call); num++)
 545     {
 546       arg = gimple_call_arg (call, num);
 547
 548       if (functions[num].type == IPA_UNKNOWN
 549           && type_like_member_ptr_p (TREE_TYPE (arg), &method_field,
 550                                      &delta_field))
 551         determine_cst_member_ptr (call, arg, method_field, delta_field,
 552                                   &functions[num]);
 553     }
 554 }
 555
 556 /* Compute jump function for all arguments of callsite CS and insert the
 557    information in the jump_functions array in the ipa_edge_args corresponding
 558    to this callsite.  */
 559
 560 void
 561 ipa_compute_jump_functions (struct cgraph_edge *cs)
 562 {
 563   struct ipa_node_params *info = IPA_NODE_REF (cs->caller);
 564   struct ipa_edge_args *arguments = IPA_EDGE_REF (cs);
 565   gimple call;
 566
 567   if (ipa_get_cs_argument_count (arguments) == 0 || arguments->jump_functions)
 568     return;
 569   arguments->jump_functions = XCNEWVEC (struct ipa_jump_func,
 570                                         ipa_get_cs_argument_count (arguments));
 571
 572   call = cs->call_stmt;
 573   gcc_assert (is_gimple_call (call));
 574
 575   /* We will deal with constants and SSA scalars first:  */
 576   compute_scalar_jump_functions (info, arguments->jump_functions, call);
 577
 578   /* Let's check whether there are any potential member pointers and if so,
 579      whether we can determine their functions as pass_through.  */
 580   if (!compute_pass_through_member_ptrs (info, arguments->jump_functions, call))
 581     return;
 582
 583   /* Finally, let's check whether we actually pass a new constant member
 584      pointer here...  */
 585   compute_cst_member_ptr_arguments (arguments->jump_functions, call);
 586 }
 587
 588 /* If RHS looks like a rhs of a statement loading pfn from a member pointer
 589    formal parameter, return the parameter, otherwise return NULL.  */
 590
 591 static tree
 592 ipa_get_member_ptr_load_param (tree rhs)
 593 {
 594   tree rec, fld;
 595   tree ptr_field;
 596
 597   if (TREE_CODE (rhs) != COMPONENT_REF)
 598     return NULL_TREE;
 599
 600   rec = TREE_OPERAND (rhs, 0);
 601   if (TREE_CODE (rec) != PARM_DECL
 602       || !type_like_member_ptr_p (TREE_TYPE (rec), &ptr_field, NULL))
 603     return NULL_TREE;
 604
 605   fld = TREE_OPERAND (rhs, 1);
 606   if (fld == ptr_field)
 607     return rec;
 608   else
 609     return NULL_TREE;
 610 }
 611
 612 /* If STMT looks like a statement loading a value from a member pointer formal
 613    parameter, this function returns that parameter.  */
 614
 615 static tree
 616 ipa_get_stmt_member_ptr_load_param (gimple stmt)
 617 {
 618   tree rhs;
 619
 620   if (!is_gimple_assign (stmt) || gimple_num_ops (stmt) != 2)
 621     return NULL_TREE;
 622
 623   rhs = gimple_assign_rhs1 (stmt);
 624   return ipa_get_member_ptr_load_param (rhs);
 625 }
 626
 627 /* Returns true iff T is an SSA_NAME defined by a statement.  */
 628
 629 static bool
 630 ipa_is_ssa_with_stmt_def (tree t)
 631 {
 632   if (TREE_CODE (t) == SSA_NAME
 633       && !SSA_NAME_IS_DEFAULT_DEF (t))
 634     return true;
 635   else
 636     return false;
 637 }
 638
 639 /* Creates a new note describing a call to a parameter number FORMAL_ID and
 640    attaches it to the linked list of INFO.  It also sets the called flag of the
 641    parameter.  STMT is the corresponding call statement.  */
 642
 643 static void
 644 ipa_note_param_call (struct ipa_node_params *info, int formal_id,
 645                      gimple stmt)
 646 {
 647   struct ipa_param_call_note *note;
 648   basic_block bb = gimple_bb (stmt);
 649
 650   info->params[formal_id].called = 1;
 651
 652   note = XCNEW (struct ipa_param_call_note);
 653   note->formal_id = formal_id;
 654   note->stmt = stmt;
 655   note->count = bb->count;
 656   note->frequency = compute_call_stmt_bb_frequency (bb);
 657
 658   note->next = info->param_calls;
 659   info->param_calls = note;
 660
 661   return;
 662 }
 663
 664 /* Analyze the CALL and examine uses of formal parameters of the caller
 665    (described by INFO).  Currently it checks whether the call calls a pointer
 666    that is a formal parameter and if so, the parameter is marked with the
 667    called flag and a note describing the call is created.  This is very simple
 668    for ordinary pointers represented in SSA but not-so-nice when it comes to
 669    member pointers.  The ugly part of this function does nothing more than
 670    tries to match the pattern of such a call.  An example of such a pattern is
 671    the gimple dump below, the call is on the last line:
 672
 673      <bb 2>:
 674        f$__delta_5 = f.__delta;
 675        f$__pfn_24 = f.__pfn;
 676        D.2496_3 = (int) f$__pfn_24;
 677        D.2497_4 = D.2496_3 & 1;
 678        if (D.2497_4 != 0)
 679          goto <bb 3>;
 680        else
 681          goto <bb 4>;
 682
 683      <bb 3>:
 684        D.2500_7 = (unsigned int) f$__delta_5;
 685        D.2501_8 = &S + D.2500_7;
 686        D.2502_9 = (int (*__vtbl_ptr_type) (void) * *) D.2501_8;
 687        D.2503_10 = *D.2502_9;
 688        D.2504_12 = f$__pfn_24 + -1;
 689        D.2505_13 = (unsigned int) D.2504_12;
 690        D.2506_14 = D.2503_10 + D.2505_13;
 691        D.2507_15 = *D.2506_14;
 692        iftmp.11_16 = (String:: *) D.2507_15;
 693
 694      <bb 4>:
 695        # iftmp.11_1 = PHI <iftmp.11_16(3), f$__pfn_24(2)>
 696        D.2500_19 = (unsigned int) f$__delta_5;
 697        D.2508_20 = &S + D.2500_19;
 698        D.2493_21 = iftmp.11_1 (D.2508_20, 4);
 699
 700    Such patterns are results of simple calls to a member pointer:
 701
 702      int doprinting (int (MyString::* f)(int) const)
 703      {
 704        MyString S ("somestring");
 705
 706        return (S.*f)(4);
 707      }
 708 */
 709
 710 static void
 711 ipa_analyze_call_uses (struct ipa_node_params *info, gimple call)
 712 {
 713   tree target = gimple_call_fn (call);
 714   gimple def;
 715   tree var;
 716   tree n1, n2;
 717   gimple d1, d2;
 718   tree rec, rec2, cond;
 719   gimple branch;
 720   int index;
 721   basic_block bb, virt_bb, join;
 722
 723   if (TREE_CODE (target) != SSA_NAME)
 724     return;
 725
 726   var = SSA_NAME_VAR (target);
 727   if (SSA_NAME_IS_DEFAULT_DEF (target))
 728     {
 729       /* assuming TREE_CODE (var) == PARM_DECL */
 730       index = ipa_get_param_decl_index (info, var);
 731       if (index >= 0)
 732         ipa_note_param_call (info, index, call);
 733       return;
 734     }
 735
 736   /* Now we need to try to match the complex pattern of calling a member
 737      pointer. */
 738
 739   if (!POINTER_TYPE_P (TREE_TYPE (target))
 740       || TREE_CODE (TREE_TYPE (TREE_TYPE (target))) != METHOD_TYPE)
 741     return;
 742
 743   def = SSA_NAME_DEF_STMT (target);
 744   if (gimple_code (def) != GIMPLE_PHI)
 745     return;
 746
 747   if (gimple_phi_num_args (def) != 2)
 748     return;
 749
 750   /* First, we need to check whether one of these is a load from a member
 751      pointer that is a parameter to this function. */
 752   n1 = PHI_ARG_DEF (def, 0);
 753   n2 = PHI_ARG_DEF (def, 1);
 754   if (!ipa_is_ssa_with_stmt_def (n1) || !ipa_is_ssa_with_stmt_def (n2))
 755     return;
 756   d1 = SSA_NAME_DEF_STMT (n1);
 757   d2 = SSA_NAME_DEF_STMT (n2);
 758
 759   if ((rec = ipa_get_stmt_member_ptr_load_param (d1)))
 760     {
 761       if (ipa_get_stmt_member_ptr_load_param (d2))
 762         return;
 763
 764       bb = gimple_bb (d1);
 765       virt_bb = gimple_bb (d2);
 766     }
 767   else if ((rec = ipa_get_stmt_member_ptr_load_param (d2)))
 768     {
 769       bb = gimple_bb (d2);
 770       virt_bb = gimple_bb (d1);
 771     }
 772   else
 773     return;
 774
 775   /* Second, we need to check that the basic blocks are laid out in the way
 776      corresponding to the pattern. */
 777
 778   join = gimple_bb (def);
 779   if (!single_pred_p (virt_bb) || !single_succ_p (virt_bb)
 780       || single_pred (virt_bb) != bb
 781       || single_succ (virt_bb) != join)
 782     return;
 783
 784   /* Third, let's see that the branching is done depending on the least
 785      significant bit of the pfn. */
 786
 787   branch = last_stmt (bb);
 788   if (gimple_code (branch) != GIMPLE_COND)
 789     return;
 790
 791   if (gimple_cond_code (branch) != NE_EXPR
 792       || !integer_zerop (gimple_cond_rhs (branch)))
 793     return;
 794
 795   cond = gimple_cond_lhs (branch);
 796   if (!ipa_is_ssa_with_stmt_def (cond))
 797     return;
 798
 799   def = SSA_NAME_DEF_STMT (cond);
 800   if (!is_gimple_assign (def) || gimple_num_ops (def) != 3
 801       || gimple_assign_rhs_code (def) != BIT_AND_EXPR
 802       || !integer_onep (gimple_assign_rhs2 (def)))
 803     return;
 804
 805   cond = gimple_assign_rhs1 (def);
 806   if (!ipa_is_ssa_with_stmt_def (cond))
 807     return;
 808
 809   def = SSA_NAME_DEF_STMT (cond);
 810
 811   if (is_gimple_assign (def) && gimple_num_ops (def) == 2
 812       && gimple_assign_rhs_code (def) == NOP_EXPR)
 813     {
 814       cond = gimple_assign_rhs1 (def);
 815       if (!ipa_is_ssa_with_stmt_def (cond))
 816         return;
 817       def = SSA_NAME_DEF_STMT (cond);
 818     }
 819
 820   rec2 = ipa_get_stmt_member_ptr_load_param (def);
 821   if (rec != rec2)
 822     return;
 823
 824   index = ipa_get_param_decl_index (info, rec);
 825   if (index >= 0 && !ipa_is_param_modified (info, index))
 826     ipa_note_param_call (info, index, call);
 827
 828   return;
 829 }
 830
 831 /* Analyze the statement STMT with respect to formal parameters (described in
 832    INFO) and their uses.  Currently it only checks whether formal parameters
 833    are called.  */
 834
 835 static void
 836 ipa_analyze_stmt_uses (struct ipa_node_params *info, gimple stmt)
 837 {
 838   if (is_gimple_call (stmt))
 839     ipa_analyze_call_uses (info, stmt);
 840 }
 841
 842 /* Scan the function body of NODE and inspect the uses of formal parameters.
 843    Store the findings in various structures of the associated ipa_node_params
 844    structure, such as parameter flags, notes etc.  */
 845
 846 void
 847 ipa_analyze_params_uses (struct cgraph_node *node)
 848 {
 849   tree decl = node->decl;
 850   basic_block bb;
 851   struct function *func;
 852   gimple_stmt_iterator gsi;
 853   struct ipa_node_params *info = IPA_NODE_REF (node);
 854
 855   if (ipa_get_param_count (info) == 0 || info->uses_analysis_done)
 856     return;
 857
 858   func = DECL_STRUCT_FUNCTION (decl);
 859   FOR_EACH_BB_FN (bb, func)
 860     {
 861       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 862         {
 863           gimple stmt = gsi_stmt (gsi);
 864           ipa_analyze_stmt_uses (info, stmt);
 865         }
 866     }
 867
 868   info->uses_analysis_done = 1;
 869 }
 870
 871 /* Update the jump functions associated with call graph edge E when the call
 872    graph edge CS is being inlined, assuming that E->caller is already (possibly
 873    indirectly) inlined into CS->callee and that E has not been inlined.  */
 874
 875 static void
 876 update_jump_functions_after_inlining (struct cgraph_edge *cs,
 877                                       struct cgraph_edge *e)
 878 {
 879   struct ipa_edge_args *top = IPA_EDGE_REF (cs);
 880   struct ipa_edge_args *args = IPA_EDGE_REF (e);
 881   int count = ipa_get_cs_argument_count (args);
 882   int i;
 883
 884   for (i = 0; i < count; i++)
 885     {
 886       struct ipa_jump_func *src, *dst = ipa_get_ith_jump_func (args, i);
 887
 888       if (dst->type != IPA_PASS_THROUGH)
 889         continue;
 890
 891       /* We must check range due to calls with variable number of arguments:  */
 892       if (dst->value.formal_id >= (unsigned) ipa_get_cs_argument_count (top))
 893         {
 894           dst->type = IPA_BOTTOM;
 895           continue;
 896         }
 897
 898       src = ipa_get_ith_jump_func (top, dst->value.formal_id);
 899       *dst = *src;
 900     }
 901 }
 902
 903 /* Print out a debug message to file F that we have discovered that an indirect
 904    call described by NT is in fact a call of a known constant function described
 905    by JFUNC.  NODE is the node where the call is.  */
 906
 907 static void
 908 print_edge_addition_message (FILE *f, struct ipa_param_call_note *nt,
 909                              struct ipa_jump_func *jfunc,
 910                              struct cgraph_node *node)
 911 {
 912   fprintf (f, "ipa-prop: Discovered an indirect call to a known target (");
 913   if (jfunc->type == IPA_CONST_MEMBER_PTR)
 914     {
 915       print_node_brief (f, "", jfunc->value.member_cst.pfn, 0);
 916       print_node_brief (f, ", ", jfunc->value.member_cst.delta, 0);
 917     }
 918   else
 919     print_node_brief(f, "", jfunc->value.constant, 0);
 920
 921   fprintf (f, ") in %s: ", cgraph_node_name (node));
 922   print_gimple_stmt (f, nt->stmt, 2, TDF_SLIM);
 923 }
 924
 925 /* Update the param called notes associated with NODE when CS is being inlined,
 926    assuming NODE is (potentially indirectly) inlined into CS->callee.
 927    Moreover, if the callee is discovered to be constant, create a new cgraph
 928    edge for it.  Newly discovered indirect edges will be added to *NEW_EDGES,
 929    unless NEW_EDGES is NULL.  Return true iff a new edge(s) were created.  */
 930
 931 static bool
 932 update_call_notes_after_inlining (struct cgraph_edge *cs,
 933                                   struct cgraph_node *node,
 934                                   VEC (cgraph_edge_p, heap) **new_edges)
 935 {
 936   struct ipa_node_params *info = IPA_NODE_REF (node);
 937   struct ipa_edge_args *top = IPA_EDGE_REF (cs);
 938   struct ipa_param_call_note *nt;
 939   bool res = false;
 940
 941   for (nt = info->param_calls; nt; nt = nt->next)
 942     {
 943       struct ipa_jump_func *jfunc;
 944
 945       if (nt->processed)
 946         continue;
 947
 948       /* We must check range due to calls with variable number of arguments:  */
 949       if (nt->formal_id >= (unsigned) ipa_get_cs_argument_count (top))
 950         {
 951           nt->processed = true;
 952           continue;
 953         }
 954
 955       jfunc = ipa_get_ith_jump_func (top, nt->formal_id);
 956       if (jfunc->type == IPA_PASS_THROUGH)
 957         nt->formal_id = jfunc->value.formal_id;
 958       else if (jfunc->type == IPA_CONST || jfunc->type == IPA_CONST_MEMBER_PTR)
 959         {
 960           struct cgraph_node *callee;
 961           struct cgraph_edge *new_indirect_edge;
 962           tree decl;
 963
 964           nt->processed = true;
 965           if (jfunc->type == IPA_CONST_MEMBER_PTR)
 966             decl = jfunc->value.member_cst.pfn;
 967           else
 968             decl = jfunc->value.constant;
 969
 970           if (TREE_CODE (decl) != ADDR_EXPR)
 971             continue;
 972           decl = TREE_OPERAND (decl, 0);
 973
 974           if (TREE_CODE (decl) != FUNCTION_DECL)
 975             continue;
 976           callee = cgraph_node (decl);
 977           if (!callee || !callee->local.inlinable)
 978             continue;
 979
 980           res = true;
 981           if (dump_file)
 982             print_edge_addition_message (dump_file, nt, jfunc, node);
 983
 984           new_indirect_edge = cgraph_create_edge (node, callee, nt->stmt,
 985                                                   nt->count, nt->frequency,
 986                                                   nt->loop_nest);
 987           new_indirect_edge->indirect_call = 1;
 988           ipa_check_create_edge_args ();
 989           if (new_edges)
 990             VEC_safe_push (cgraph_edge_p, heap, *new_edges, new_indirect_edge);
 991           top = IPA_EDGE_REF (cs);
 992         }
 993     }
 994   return res;
 995 }
 996
 997 /* Recursively traverse subtree of NODE (including node) made of inlined
 998    cgraph_edges when CS has been inlined and invoke
 999    update_call_notes_after_inlining on all nodes and
1000    update_jump_functions_after_inlining on all non-inlined edges that lead out
1001    of this subtree.  Newly discovered indirect edges will be added to
1002    *NEW_EDGES, unless NEW_EDGES is NULL.  Return true iff a new edge(s) were
1003    created.  */
1004
1005 static bool
1006 propagate_info_to_inlined_callees (struct cgraph_edge *cs,
1007                                    struct cgraph_node *node,
1008                                    VEC (cgraph_edge_p, heap) **new_edges)
1009 {
1010   struct cgraph_edge *e;
1011   bool res;
1012
1013   res = update_call_notes_after_inlining (cs, node, new_edges);
1014
1015   for (e = node->callees; e; e = e->next_callee)
1016     if (!e->inline_failed)
1017       res |= propagate_info_to_inlined_callees (cs, e->callee, new_edges);
1018     else
1019       update_jump_functions_after_inlining (cs, e);
1020
1021   return res;
1022 }
1023
1024 /* Update jump functions and call note functions on inlining the call site CS.
1025    CS is expected to lead to a node already cloned by
1026    cgraph_clone_inline_nodes.  Newly discovered indirect edges will be added to
1027    *NEW_EDGES, unless NEW_EDGES is NULL.  Return true iff a new edge(s) were +
1028    created.  */
1029
1030 bool
1031 ipa_propagate_indirect_call_infos (struct cgraph_edge *cs,
1032                                    VEC (cgraph_edge_p, heap) **new_edges)
1033 {
1034   /* Do nothing if the preparation phase has not been carried out yet
1035      (i.e. during early inlining).  */
1036   if (!ipa_node_params_vector)
1037     return false;
1038   gcc_assert (ipa_edge_args_vector);
1039
1040   return propagate_info_to_inlined_callees (cs, cs->callee, new_edges);
1041 }
1042
1043 /* Frees all dynamically allocated structures that the argument info points
1044    to.  */
1045
1046 void
1047 ipa_free_edge_args_substructures (struct ipa_edge_args *args)
1048 {
1049   if (args->jump_functions)
1050     free (args->jump_functions);
1051
1052   memset (args, 0, sizeof (*args));
1053 }
1054
1055 /* Free all ipa_edge structures.  */
1056
1057 void
1058 ipa_free_all_edge_args (void)
1059 {
1060   int i;
1061   struct ipa_edge_args *args;
1062
1063   for (i = 0;
1064        VEC_iterate (ipa_edge_args_t, ipa_edge_args_vector, i, args);
1065        i++)
1066     ipa_free_edge_args_substructures (args);
1067
1068   VEC_free (ipa_edge_args_t, heap, ipa_edge_args_vector);
1069   ipa_edge_args_vector = NULL;
1070 }
1071
1072 /* Frees all dynamically allocated structures that the param info points
1073    to.  */
1074
1075 void
1076 ipa_free_node_params_substructures (struct ipa_node_params *info)
1077 {
1078   if (info->params)
1079     free (info->params);
1080
1081   while (info->param_calls)
1082     {
1083       struct ipa_param_call_note *note = info->param_calls;
1084       info->param_calls = note->next;
1085       free (note);
1086     }
1087
1088   memset (info, 0, sizeof (*info));
1089 }
1090
1091 /* Free all ipa_node_params structures.  */
1092
1093 void
1094 ipa_free_all_node_params (void)
1095 {
1096   int i;
1097   struct ipa_node_params *info;
1098
1099   for (i = 0;
1100        VEC_iterate (ipa_node_params_t, ipa_node_params_vector, i, info);
1101        i++)
1102     ipa_free_node_params_substructures (info);
1103
1104   VEC_free (ipa_node_params_t, heap, ipa_node_params_vector);
1105   ipa_node_params_vector = NULL;
1106 }
1107
1108 /* Hook that is called by cgraph.c when an edge is removed.  */
1109
1110 static void
1111 ipa_edge_removal_hook (struct cgraph_edge *cs, void *data ATTRIBUTE_UNUSED)
1112 {
1113   /* During IPA-CP updating we can be called on not-yet analyze clones.  */
1114   if (VEC_length (ipa_edge_args_t, ipa_edge_args_vector)
1115       <= (unsigned)cs->uid)
1116     return;
1117   ipa_free_edge_args_substructures (IPA_EDGE_REF (cs));
1118 }
1119
1120 /* Hook that is called by cgraph.c when a node is removed.  */
1121
1122 static void
1123 ipa_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
1124 {
1125   ipa_free_node_params_substructures (IPA_NODE_REF (node));
1126 }
1127
1128 /* Helper function to duplicate an array of size N that is at SRC and store a
1129    pointer to it to DST.  Nothing is done if SRC is NULL.  */
1130
1131 static void *
1132 duplicate_array (void *src, size_t n)
1133 {
1134   void *p;
1135
1136   if (!src)
1137     return NULL;
1138
1139   p = xcalloc (1, n);
1140   memcpy (p, src, n);
1141   return p;
1142 }
1143
1144 /* Hook that is called by cgraph.c when a node is duplicated.  */
1145
1146 static void
1147 ipa_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
1148                            __attribute__((unused)) void *data)
1149 {
1150   struct ipa_edge_args *old_args, *new_args;
1151   int arg_count;
1152
1153   ipa_check_create_edge_args ();
1154
1155   old_args = IPA_EDGE_REF (src);
1156   new_args = IPA_EDGE_REF (dst);
1157
1158   arg_count = ipa_get_cs_argument_count (old_args);
1159   ipa_set_cs_argument_count (new_args, arg_count);
1160   new_args->jump_functions = (struct ipa_jump_func *)
1161     duplicate_array (old_args->jump_functions,
1162                      sizeof (struct ipa_jump_func) * arg_count);
1163 }
1164
1165 /* Hook that is called by cgraph.c when a node is duplicated.  */
1166
1167 static void
1168 ipa_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
1169                            __attribute__((unused)) void *data)
1170 {
1171   struct ipa_node_params *old_info, *new_info;
1172   struct ipa_param_call_note *note;
1173   int param_count;
1174
1175   ipa_check_create_node_params ();
1176   old_info = IPA_NODE_REF (src);
1177   new_info = IPA_NODE_REF (dst);
1178   param_count = ipa_get_param_count (old_info);
1179
1180   ipa_set_param_count (new_info, param_count);
1181   new_info->params = (struct ipa_param_descriptor *)
1182     duplicate_array (old_info->params,
1183                      sizeof (struct ipa_param_descriptor) * param_count);
1184   new_info->ipcp_orig_node = old_info->ipcp_orig_node;
1185   new_info->count_scale = old_info->count_scale;
1186
1187   for (note = old_info->param_calls; note; note = note->next)
1188     {
1189       struct ipa_param_call_note *nn;
1190
1191       nn = (struct ipa_param_call_note *)
1192         xcalloc (1, sizeof (struct ipa_param_call_note));
1193       memcpy (nn, note, sizeof (struct ipa_param_call_note));
1194       nn->next = new_info->param_calls;
1195       new_info->param_calls = nn;
1196     }
1197 }
1198
1199 /* Register our cgraph hooks if they are not already there.  */
1200
1201 void
1202 ipa_register_cgraph_hooks (void)
1203 {
1204   if (!edge_removal_hook_holder)
1205     edge_removal_hook_holder =
1206       cgraph_add_edge_removal_hook (&ipa_edge_removal_hook, NULL);
1207   if (!node_removal_hook_holder)
1208     node_removal_hook_holder =
1209       cgraph_add_node_removal_hook (&ipa_node_removal_hook, NULL);
1210   if (!edge_duplication_hook_holder)
1211     edge_duplication_hook_holder =
1212       cgraph_add_edge_duplication_hook (&ipa_edge_duplication_hook, NULL);
1213   if (!node_duplication_hook_holder)
1214     node_duplication_hook_holder =
1215       cgraph_add_node_duplication_hook (&ipa_node_duplication_hook, NULL);
1216 }
1217
1218 /* Unregister our cgraph hooks if they are not already there.  */
1219
1220 static void
1221 ipa_unregister_cgraph_hooks (void)
1222 {
1223   cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
1224   edge_removal_hook_holder = NULL;
1225   cgraph_remove_node_removal_hook (node_removal_hook_holder);
1226   node_removal_hook_holder = NULL;
1227   cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
1228   edge_duplication_hook_holder = NULL;
1229   cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
1230   node_duplication_hook_holder = NULL;
1231 }
1232
1233 /* Free all ipa_node_params and all ipa_edge_args structures if they are no
1234    longer needed after ipa-cp.  */
1235
1236 void
1237 free_all_ipa_structures_after_ipa_cp (void)
1238 {
1239   if (!flag_indirect_inlining)
1240     {
1241       ipa_free_all_edge_args ();
1242       ipa_free_all_node_params ();
1243       ipa_unregister_cgraph_hooks ();
1244     }
1245 }
1246
1247 /* Free all ipa_node_params and all ipa_edge_args structures if they are no
1248    longer needed after indirect inlining.  */
1249
1250 void
1251 free_all_ipa_structures_after_iinln (void)
1252 {
1253   ipa_free_all_edge_args ();
1254   ipa_free_all_node_params ();
1255   ipa_unregister_cgraph_hooks ();
1256 }
1257
1258 /* Print ipa_tree_map data structures of all functions in the
1259    callgraph to F.  */
1260
1261 void
1262 ipa_print_node_params (FILE * f, struct cgraph_node *node)
1263 {
1264   int i, count;
1265   tree temp;
1266   struct ipa_node_params *info;
1267
1268   if (!node->analyzed)
1269     return;
1270   info = IPA_NODE_REF (node);
1271   fprintf (f, "  function  %s Trees :: \n", cgraph_node_name (node));
1272   count = ipa_get_param_count (info);
1273   for (i = 0; i < count; i++)
1274     {
1275       temp = ipa_get_param (info, i);
1276       if (TREE_CODE (temp) == PARM_DECL)
1277         fprintf (f, "    param %d : %s", i,
1278                  (*lang_hooks.decl_printable_name) (temp, 2));
1279       if (ipa_is_param_modified (info, i))
1280         fprintf (f, " modified");
1281       if (ipa_is_param_called (info, i))
1282         fprintf (f, " called");
1283       fprintf (f, "\n");
1284     }
1285 }
1286
1287 /* Print ipa_tree_map data structures of all functions in the
1288    callgraph to F.  */
1289
1290 void
1291 ipa_print_all_params (FILE * f)
1292 {
1293   struct cgraph_node *node;
1294
1295   fprintf (f, "\nFunction parameters:\n");
1296   for (node = cgraph_nodes; node; node = node->next)
1297     ipa_print_node_params (f, node);
1298 }