gcc/ipa-prop.c

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