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 /* 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_JF_UNKNOWN)
 297             fprintf (f, "UNKNOWN\n");
 298           else if (type == IPA_JF_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_JF_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_JF_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_JF_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_JF_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_JF_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_JF_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_JF_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 (current_function_decl, 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_JF_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_JF_UNKNOWN;
 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_JF_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_JF_PASS_THROUGH)
 957         nt->formal_id = jfunc->value.formal_id;
 958       else if (jfunc->type == IPA_JF_CONST
 959                || jfunc->type == IPA_JF_CONST_MEMBER_PTR)
 960         {
 961           struct cgraph_node *callee;
 962           struct cgraph_edge *new_indirect_edge;
 963           tree decl;
 964
 965           nt->processed = true;
 966           if (jfunc->type == IPA_JF_CONST_MEMBER_PTR)
 967             decl = jfunc->value.member_cst.pfn;
 968           else
 969             decl = jfunc->value.constant;
 970
 971           if (TREE_CODE (decl) != ADDR_EXPR)
 972             continue;
 973           decl = TREE_OPERAND (decl, 0);
 974
 975           if (TREE_CODE (decl) != FUNCTION_DECL)
 976             continue;
 977           callee = cgraph_node (decl);
 978           if (!callee || !callee->local.inlinable)
 979             continue;
 980
 981           res = true;
 982           if (dump_file)
 983             print_edge_addition_message (dump_file, nt, jfunc, node);
 984
 985           new_indirect_edge = cgraph_create_edge (node, callee, nt->stmt,
 986                                                   nt->count, nt->frequency,
 987                                                   nt->loop_nest);
 988           new_indirect_edge->indirect_call = 1;
 989           ipa_check_create_edge_args ();
 990           if (new_edges)
 991             VEC_safe_push (cgraph_edge_p, heap, *new_edges, new_indirect_edge);
 992           top = IPA_EDGE_REF (cs);
 993         }
 994     }
 995   return res;
 996 }
 997
 998 /* Recursively traverse subtree of NODE (including node) made of inlined
 999    cgraph_edges when CS has been inlined and invoke
1000    update_call_notes_after_inlining on all nodes and
1001    update_jump_functions_after_inlining on all non-inlined edges that lead out
1002    of this subtree.  Newly discovered indirect edges will be added to
1003    *NEW_EDGES, unless NEW_EDGES is NULL.  Return true iff a new edge(s) were
1004    created.  */
1005
1006 static bool
1007 propagate_info_to_inlined_callees (struct cgraph_edge *cs,
1008                                    struct cgraph_node *node,
1009                                    VEC (cgraph_edge_p, heap) **new_edges)
1010 {
1011   struct cgraph_edge *e;
1012   bool res;
1013
1014   res = update_call_notes_after_inlining (cs, node, new_edges);
1015
1016   for (e = node->callees; e; e = e->next_callee)
1017     if (!e->inline_failed)
1018       res |= propagate_info_to_inlined_callees (cs, e->callee, new_edges);
1019     else
1020       update_jump_functions_after_inlining (cs, e);
1021
1022   return res;
1023 }
1024
1025 /* Update jump functions and call note functions on inlining the call site CS.
1026    CS is expected to lead to a node already cloned by
1027    cgraph_clone_inline_nodes.  Newly discovered indirect edges will be added to
1028    *NEW_EDGES, unless NEW_EDGES is NULL.  Return true iff a new edge(s) were +
1029    created.  */
1030
1031 bool
1032 ipa_propagate_indirect_call_infos (struct cgraph_edge *cs,
1033                                    VEC (cgraph_edge_p, heap) **new_edges)
1034 {
1035   /* Do nothing if the preparation phase has not been carried out yet
1036      (i.e. during early inlining).  */
1037   if (!ipa_node_params_vector)
1038     return false;
1039   gcc_assert (ipa_edge_args_vector);
1040
1041   return propagate_info_to_inlined_callees (cs, cs->callee, new_edges);
1042 }
1043
1044 /* Frees all dynamically allocated structures that the argument info points
1045    to.  */
1046
1047 void
1048 ipa_free_edge_args_substructures (struct ipa_edge_args *args)
1049 {
1050   if (args->jump_functions)
1051     free (args->jump_functions);
1052
1053   memset (args, 0, sizeof (*args));
1054 }
1055
1056 /* Free all ipa_edge structures.  */
1057
1058 void
1059 ipa_free_all_edge_args (void)
1060 {
1061   int i;
1062   struct ipa_edge_args *args;
1063
1064   for (i = 0;
1065        VEC_iterate (ipa_edge_args_t, ipa_edge_args_vector, i, args);
1066        i++)
1067     ipa_free_edge_args_substructures (args);
1068
1069   VEC_free (ipa_edge_args_t, heap, ipa_edge_args_vector);
1070   ipa_edge_args_vector = NULL;
1071 }
1072
1073 /* Frees all dynamically allocated structures that the param info points
1074    to.  */
1075
1076 void
1077 ipa_free_node_params_substructures (struct ipa_node_params *info)
1078 {
1079   if (info->params)
1080     free (info->params);
1081
1082   while (info->param_calls)
1083     {
1084       struct ipa_param_call_note *note = info->param_calls;
1085       info->param_calls = note->next;
1086       free (note);
1087     }
1088
1089   memset (info, 0, sizeof (*info));
1090 }
1091
1092 /* Free all ipa_node_params structures.  */
1093
1094 void
1095 ipa_free_all_node_params (void)
1096 {
1097   int i;
1098   struct ipa_node_params *info;
1099
1100   for (i = 0;
1101        VEC_iterate (ipa_node_params_t, ipa_node_params_vector, i, info);
1102        i++)
1103     ipa_free_node_params_substructures (info);
1104
1105   VEC_free (ipa_node_params_t, heap, ipa_node_params_vector);
1106   ipa_node_params_vector = NULL;
1107 }
1108
1109 /* Hook that is called by cgraph.c when an edge is removed.  */
1110
1111 static void
1112 ipa_edge_removal_hook (struct cgraph_edge *cs, void *data ATTRIBUTE_UNUSED)
1113 {
1114   /* During IPA-CP updating we can be called on not-yet analyze clones.  */
1115   if (VEC_length (ipa_edge_args_t, ipa_edge_args_vector)
1116       <= (unsigned)cs->uid)
1117     return;
1118   ipa_free_edge_args_substructures (IPA_EDGE_REF (cs));
1119 }
1120
1121 /* Hook that is called by cgraph.c when a node is removed.  */
1122
1123 static void
1124 ipa_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
1125 {
1126   ipa_free_node_params_substructures (IPA_NODE_REF (node));
1127 }
1128
1129 /* Helper function to duplicate an array of size N that is at SRC and store a
1130    pointer to it to DST.  Nothing is done if SRC is NULL.  */
1131
1132 static void *
1133 duplicate_array (void *src, size_t n)
1134 {
1135   void *p;
1136
1137   if (!src)
1138     return NULL;
1139
1140   p = xcalloc (1, n);
1141   memcpy (p, src, n);
1142   return p;
1143 }
1144
1145 /* Hook that is called by cgraph.c when a node is duplicated.  */
1146
1147 static void
1148 ipa_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
1149                            __attribute__((unused)) void *data)
1150 {
1151   struct ipa_edge_args *old_args, *new_args;
1152   int arg_count;
1153
1154   ipa_check_create_edge_args ();
1155
1156   old_args = IPA_EDGE_REF (src);
1157   new_args = IPA_EDGE_REF (dst);
1158
1159   arg_count = ipa_get_cs_argument_count (old_args);
1160   ipa_set_cs_argument_count (new_args, arg_count);
1161   new_args->jump_functions = (struct ipa_jump_func *)
1162     duplicate_array (old_args->jump_functions,
1163                      sizeof (struct ipa_jump_func) * arg_count);
1164 }
1165
1166 /* Hook that is called by cgraph.c when a node is duplicated.  */
1167
1168 static void
1169 ipa_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
1170                            __attribute__((unused)) void *data)
1171 {
1172   struct ipa_node_params *old_info, *new_info;
1173   struct ipa_param_call_note *note;
1174   int param_count;
1175
1176   ipa_check_create_node_params ();
1177   old_info = IPA_NODE_REF (src);
1178   new_info = IPA_NODE_REF (dst);
1179   param_count = ipa_get_param_count (old_info);
1180
1181   ipa_set_param_count (new_info, param_count);
1182   new_info->params = (struct ipa_param_descriptor *)
1183     duplicate_array (old_info->params,
1184                      sizeof (struct ipa_param_descriptor) * param_count);
1185   new_info->ipcp_orig_node = old_info->ipcp_orig_node;
1186   new_info->count_scale = old_info->count_scale;
1187
1188   for (note = old_info->param_calls; note; note = note->next)
1189     {
1190       struct ipa_param_call_note *nn;
1191
1192       nn = (struct ipa_param_call_note *)
1193         xcalloc (1, sizeof (struct ipa_param_call_note));
1194       memcpy (nn, note, sizeof (struct ipa_param_call_note));
1195       nn->next = new_info->param_calls;
1196       new_info->param_calls = nn;
1197     }
1198 }
1199
1200 /* Register our cgraph hooks if they are not already there.  */
1201
1202 void
1203 ipa_register_cgraph_hooks (void)
1204 {
1205   if (!edge_removal_hook_holder)
1206     edge_removal_hook_holder =
1207       cgraph_add_edge_removal_hook (&ipa_edge_removal_hook, NULL);
1208   if (!node_removal_hook_holder)
1209     node_removal_hook_holder =
1210       cgraph_add_node_removal_hook (&ipa_node_removal_hook, NULL);
1211   if (!edge_duplication_hook_holder)
1212     edge_duplication_hook_holder =
1213       cgraph_add_edge_duplication_hook (&ipa_edge_duplication_hook, NULL);
1214   if (!node_duplication_hook_holder)
1215     node_duplication_hook_holder =
1216       cgraph_add_node_duplication_hook (&ipa_node_duplication_hook, NULL);
1217 }
1218
1219 /* Unregister our cgraph hooks if they are not already there.  */
1220
1221 static void
1222 ipa_unregister_cgraph_hooks (void)
1223 {
1224   cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
1225   edge_removal_hook_holder = NULL;
1226   cgraph_remove_node_removal_hook (node_removal_hook_holder);
1227   node_removal_hook_holder = NULL;
1228   cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
1229   edge_duplication_hook_holder = NULL;
1230   cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
1231   node_duplication_hook_holder = NULL;
1232 }
1233
1234 /* Free all ipa_node_params and all ipa_edge_args structures if they are no
1235    longer needed after ipa-cp.  */
1236
1237 void
1238 free_all_ipa_structures_after_ipa_cp (void)
1239 {
1240   if (!flag_indirect_inlining)
1241     {
1242       ipa_free_all_edge_args ();
1243       ipa_free_all_node_params ();
1244       ipa_unregister_cgraph_hooks ();
1245     }
1246 }
1247
1248 /* Free all ipa_node_params and all ipa_edge_args structures if they are no
1249    longer needed after indirect inlining.  */
1250
1251 void
1252 free_all_ipa_structures_after_iinln (void)
1253 {
1254   ipa_free_all_edge_args ();
1255   ipa_free_all_node_params ();
1256   ipa_unregister_cgraph_hooks ();
1257 }
1258
1259 /* Print ipa_tree_map data structures of all functions in the
1260    callgraph to F.  */
1261
1262 void
1263 ipa_print_node_params (FILE * f, struct cgraph_node *node)
1264 {
1265   int i, count;
1266   tree temp;
1267   struct ipa_node_params *info;
1268
1269   if (!node->analyzed)
1270     return;
1271   info = IPA_NODE_REF (node);
1272   fprintf (f, "  function  %s Trees :: \n", cgraph_node_name (node));
1273   count = ipa_get_param_count (info);
1274   for (i = 0; i < count; i++)
1275     {
1276       temp = ipa_get_param (info, i);
1277       if (TREE_CODE (temp) == PARM_DECL)
1278         fprintf (f, "    param %d : %s", i,
1279                  (*lang_hooks.decl_printable_name) (temp, 2));
1280       if (ipa_is_param_modified (info, i))
1281         fprintf (f, " modified");
1282       if (ipa_is_param_called (info, i))
1283         fprintf (f, " called");
1284       fprintf (f, "\n");
1285     }
1286 }
1287
1288 /* Print ipa_tree_map data structures of all functions in the
1289    callgraph to F.  */
1290
1291 void
1292 ipa_print_all_params (FILE * f)
1293 {
1294   struct cgraph_node *node;
1295
1296   fprintf (f, "\nFunction parameters:\n");
1297   for (node = cgraph_nodes; node; node = node->next)
1298     ipa_print_node_params (f, node);
1299 }