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 /* Add cgraph NODE described by INFO to the worklist WL regardless of whether
  49    it is in one or not.  It should almost never be used directly, as opposed to
  50    ipa_push_func_to_list.  */
  51
  52 void
  53 ipa_push_func_to_list_1 (struct ipa_func_list **wl,
  54                          struct cgraph_node *node,
  55                          struct ipa_node_params *info)
  56 {
  57   struct ipa_func_list *temp;
  58
  59   info->node_enqueued = 1;
  60   temp = XCNEW (struct ipa_func_list);
  61   temp->node = node;
  62   temp->next = *wl;
  63   *wl = temp;
  64 }
  65
  66 /* Initialize worklist to contain all functions.  */
  67
  68 struct ipa_func_list *
  69 ipa_init_func_list (void)
  70 {
  71   struct cgraph_node *node;
  72   struct ipa_func_list * wl;
  73
  74   wl = NULL;
  75   for (node = cgraph_nodes; node; node = node->next)
  76     if (node->analyzed)
  77       {
  78         struct ipa_node_params *info = IPA_NODE_REF (node);
  79         /* Unreachable nodes should have been eliminated before ipcp and
  80            inlining.  */
  81         gcc_assert (node->needed || node->reachable);
  82         ipa_push_func_to_list_1 (&wl, node, info);
  83       }
  84
  85   return wl;
  86 }
  87
  88 /* Remove a function from the worklist WL and return it.  */
  89
  90 struct cgraph_node *
  91 ipa_pop_func_from_list (struct ipa_func_list **wl)
  92 {
  93   struct ipa_node_params *info;
  94   struct ipa_func_list *first;
  95   struct cgraph_node *node;
  96
  97   first = *wl;
  98   *wl = (*wl)->next;
  99   node = first->node;
 100   free (first);
 101
 102   info = IPA_NODE_REF (node);
 103   info->node_enqueued = 0;
 104   return node;
 105 }
 106
 107 /* Return index of the formal whose tree is PTREE in function which corresponds
 108    to INFO.  */
 109
 110 static int
 111 ipa_get_param_decl_index (struct ipa_node_params *info, tree ptree)
 112 {
 113   int i, count;
 114
 115   count = ipa_get_param_count (info);
 116   for (i = 0; i < count; i++)
 117     if (ipa_get_param(info, i) == ptree)
 118       return i;
 119
 120   return -1;
 121 }
 122
 123 /* Populate the param_decl field in parameter descriptors of INFO that
 124    corresponds to NODE.  */
 125
 126 static void
 127 ipa_populate_param_decls (struct cgraph_node *node,
 128                           struct ipa_node_params *info)
 129 {
 130   tree fndecl;
 131   tree fnargs;
 132   tree parm;
 133   int param_num;
 134
 135   fndecl = node->decl;
 136   fnargs = DECL_ARGUMENTS (fndecl);
 137   param_num = 0;
 138   for (parm = fnargs; parm; parm = TREE_CHAIN (parm))
 139     {
 140       info->params[param_num].decl = parm;
 141       param_num++;
 142     }
 143 }
 144
 145 /* Count number of formal parameters in NOTE. Store the result to the
 146    appropriate field of INFO.  */
 147
 148 static void
 149 ipa_count_formal_params (struct cgraph_node *node,
 150                          struct ipa_node_params *info)
 151 {
 152   tree fndecl;
 153   tree fnargs;
 154   tree parm;
 155   int param_num;
 156
 157   fndecl = node->decl;
 158   fnargs = DECL_ARGUMENTS (fndecl);
 159   param_num = 0;
 160   for (parm = fnargs; parm; parm = TREE_CHAIN (parm))
 161     param_num++;
 162   ipa_set_param_count (info, param_num);
 163 }
 164
 165 /* Initialize the ipa_node_params structure associated with NODE by counting
 166    the function parameters, creating the descriptors and populating their
 167    param_decls.  */
 168
 169 void
 170 ipa_initialize_node_params (struct cgraph_node *node)
 171 {
 172   struct ipa_node_params *info = IPA_NODE_REF (node);
 173
 174   if (!info->params)
 175     {
 176       ipa_count_formal_params (node, info);
 177       info->params = XCNEWVEC (struct ipa_param_descriptor,
 178                                     ipa_get_param_count (info));
 179       ipa_populate_param_decls (node, info);
 180     }
 181 }
 182
 183 /* Callback of walk_stmt_load_store_addr_ops for the visit_store and visit_addr
 184    parameters.  If OP is a parameter declaration, mark it as modified in the
 185    info structure passed in DATA.  */
 186
 187 static bool
 188 visit_store_addr_for_mod_analysis (gimple stmt ATTRIBUTE_UNUSED,
 189                                    tree op, void *data)
 190 {
 191   struct ipa_node_params *info = (struct ipa_node_params *) data;
 192
 193   if (TREE_CODE (op) == PARM_DECL)
 194     {
 195       int index = ipa_get_param_decl_index (info, op);
 196       gcc_assert (index >= 0);
 197       info->params[index].modified = true;
 198     }
 199
 200   return false;
 201 }
 202
 203 /* Compute which formal parameters of function associated with NODE are locally
 204    modified or their address is taken.  Note that this does not apply on
 205    parameters with SSA names but those can and should be analyzed
 206    differently.  */
 207
 208 void
 209 ipa_detect_param_modifications (struct cgraph_node *node)
 210 {
 211   tree decl = node->decl;
 212   basic_block bb;
 213   struct function *func;
 214   gimple_stmt_iterator gsi;
 215   struct ipa_node_params *info = IPA_NODE_REF (node);
 216
 217   if (ipa_get_param_count (info) == 0 || info->modification_analysis_done)
 218     return;
 219
 220   func = DECL_STRUCT_FUNCTION (decl);
 221   FOR_EACH_BB_FN (bb, func)
 222     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 223       walk_stmt_load_store_addr_ops (gsi_stmt (gsi), info, NULL,
 224                                      visit_store_addr_for_mod_analysis,
 225                                      visit_store_addr_for_mod_analysis);
 226
 227   info->modification_analysis_done = 1;
 228 }
 229
 230 /* Count number of arguments callsite CS has and store it in
 231    ipa_edge_args structure corresponding to this callsite.  */
 232
 233 void
 234 ipa_count_arguments (struct cgraph_edge *cs)
 235 {
 236   gimple stmt;
 237   int arg_num;
 238
 239   stmt = cs->call_stmt;
 240   gcc_assert (is_gimple_call (stmt));
 241   arg_num = gimple_call_num_args (stmt);
 242   if (VEC_length (ipa_edge_args_t, ipa_edge_args_vector)
 243       <= (unsigned) cgraph_edge_max_uid)
 244     VEC_safe_grow_cleared (ipa_edge_args_t, heap,
 245                            ipa_edge_args_vector, cgraph_edge_max_uid + 1);
 246   ipa_set_cs_argument_count (IPA_EDGE_REF (cs), arg_num);
 247 }
 248
 249 /* Print the jump functions of all arguments on all call graph edges going from
 250    NODE to file F.  */
 251
 252 void
 253 ipa_print_node_jump_functions (FILE *f, struct cgraph_node *node)
 254 {
 255   int i, count;
 256   struct cgraph_edge *cs;
 257   struct ipa_jump_func *jump_func;
 258   enum jump_func_type type;
 259
 260   fprintf (f, "  Jump functions of caller  %s:\n", cgraph_node_name (node));
 261   for (cs = node->callees; cs; cs = cs->next_callee)
 262     {
 263       if (!ipa_edge_args_info_available_for_edge_p (cs))
 264         continue;
 265
 266       fprintf (f, "    callsite  %s ", cgraph_node_name (node));
 267       fprintf (f, "-> %s :: \n", cgraph_node_name (cs->callee));
 268
 269       count = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
 270       for (i = 0; i < count; i++)
 271         {
 272           jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
 273           type = jump_func->type;
 274
 275           fprintf (f, "       param %d: ", i);
 276           if (type == IPA_JF_UNKNOWN)
 277             fprintf (f, "UNKNOWN\n");
 278           else if (type == IPA_JF_CONST)
 279             {
 280               tree val = jump_func->value.constant;
 281               fprintf (f, "CONST: ");
 282               print_generic_expr (f, val, 0);
 283               fprintf (f, "\n");
 284             }
 285           else if (type == IPA_JF_CONST_MEMBER_PTR)
 286             {
 287               fprintf (f, "CONST MEMBER PTR: ");
 288               print_generic_expr (f, jump_func->value.member_cst.pfn, 0);
 289               fprintf (f, ", ");
 290               print_generic_expr (f, jump_func->value.member_cst.delta, 0);
 291               fprintf (f, "\n");
 292             }
 293           else if (type == IPA_JF_PASS_THROUGH)
 294             {
 295               fprintf (f, "PASS THROUGH: ");
 296               fprintf (f, "%d\n", jump_func->value.formal_id);
 297             }
 298         }
 299     }
 300 }
 301
 302 /* Print ipa_jump_func data structures of all nodes in the call graph to F.  */
 303
 304 void
 305 ipa_print_all_jump_functions (FILE *f)
 306 {
 307   struct cgraph_node *node;
 308
 309   fprintf (f, "\nJump functions:\n");
 310   for (node = cgraph_nodes; node; node = node->next)
 311     {
 312       ipa_print_node_jump_functions (f, node);
 313     }
 314 }
 315
 316 /* Determine the jump functions of scalar arguments.  Scalar means SSA names
 317    and constants of a number of selected types.  INFO is the ipa_node_params
 318    structure associated with the caller, FUNCTIONS is a pointer to an array of
 319    jump function structures associated with CALL which is the call statement
 320    being examined.*/
 321
 322 static void
 323 compute_scalar_jump_functions (struct ipa_node_params *info,
 324                                struct ipa_jump_func *functions,
 325                                gimple call)
 326 {
 327   tree arg;
 328   unsigned num = 0;
 329
 330   for (num = 0; num < gimple_call_num_args (call); num++)
 331     {
 332       arg = gimple_call_arg (call, num);
 333
 334       if (is_gimple_ip_invariant (arg))
 335         {
 336           functions[num].type = IPA_JF_CONST;
 337           functions[num].value.constant = arg;
 338         }
 339       else if ((TREE_CODE (arg) == SSA_NAME) && SSA_NAME_IS_DEFAULT_DEF (arg))
 340         {
 341           int index = ipa_get_param_decl_index (info, SSA_NAME_VAR (arg));
 342
 343           if (index >= 0)
 344             {
 345               functions[num].type = IPA_JF_PASS_THROUGH;
 346               functions[num].value.formal_id = index;
 347             }
 348         }
 349     }
 350 }
 351
 352 /* Inspect the given TYPE and return true iff it has the same structure (the
 353    same number of fields of the same types) as a C++ member pointer.  If
 354    METHOD_PTR and DELTA are non-NULL, store the trees representing the
 355    corresponding fields there.  */
 356
 357 static bool
 358 type_like_member_ptr_p (tree type, tree *method_ptr, tree *delta)
 359 {
 360   tree fld;
 361
 362   if (TREE_CODE (type) != RECORD_TYPE)
 363     return false;
 364
 365   fld = TYPE_FIELDS (type);
 366   if (!fld || !POINTER_TYPE_P (TREE_TYPE (fld))
 367       || TREE_CODE (TREE_TYPE (TREE_TYPE (fld))) != METHOD_TYPE)
 368     return false;
 369
 370   if (method_ptr)
 371     *method_ptr = fld;
 372
 373   fld = TREE_CHAIN (fld);
 374   if (!fld || INTEGRAL_TYPE_P (fld))
 375     return false;
 376   if (delta)
 377     *delta = fld;
 378
 379   if (TREE_CHAIN (fld))
 380     return false;
 381
 382   return true;
 383 }
 384
 385 /* Go through arguments of the CALL and for every one that looks like a member
 386    pointer, check whether it can be safely declared pass-through and if so,
 387    mark that to the corresponding item of jump FUNCTIONS.  Return true iff
 388    there are non-pass-through member pointers within the arguments.  INFO
 389    describes formal parameters of the caller.  */
 390
 391 static bool
 392 compute_pass_through_member_ptrs (struct ipa_node_params *info,
 393                                   struct ipa_jump_func *functions,
 394                                   gimple call)
 395 {
 396   bool undecided_members = false;
 397   unsigned num;
 398   tree arg;
 399
 400   for (num = 0; num < gimple_call_num_args (call); num++)
 401     {
 402       arg = gimple_call_arg (call, num);
 403
 404       if (type_like_member_ptr_p (TREE_TYPE (arg), NULL, NULL))
 405         {
 406           if (TREE_CODE (arg) == PARM_DECL)
 407             {
 408               int index = ipa_get_param_decl_index (info, arg);
 409
 410               gcc_assert (index >=0);
 411               if (!ipa_is_param_modified (info, index))
 412                 {
 413                   functions[num].type = IPA_JF_PASS_THROUGH;
 414                   functions[num].value.formal_id = index;
 415                 }
 416               else
 417                 undecided_members = true;
 418             }
 419           else
 420             undecided_members = true;
 421         }
 422     }
 423
 424   return undecided_members;
 425 }
 426
 427 /* Simple function filling in a member pointer constant jump function (with PFN
 428    and DELTA as the constant value) into JFUNC.  */
 429
 430 static void
 431 fill_member_ptr_cst_jump_function (struct ipa_jump_func *jfunc,
 432                                    tree pfn, tree delta)
 433 {
 434   jfunc->type = IPA_JF_CONST_MEMBER_PTR;
 435   jfunc->value.member_cst.pfn = pfn;
 436   jfunc->value.member_cst.delta = delta;
 437 }
 438
 439 /* If RHS is an SSA_NAMe and it is defined by a simple copy assign statement,
 440    return the rhs of its defining statement.  */
 441
 442 static inline tree
 443 get_ssa_def_if_simple_copy (tree rhs)
 444 {
 445   while (TREE_CODE (rhs) == SSA_NAME && !SSA_NAME_IS_DEFAULT_DEF (rhs))
 446     {
 447       gimple def_stmt = SSA_NAME_DEF_STMT (rhs);
 448
 449       if (gimple_assign_single_p (def_stmt))
 450         rhs = gimple_assign_rhs1 (def_stmt);
 451       else
 452         break;
 453     }
 454   return rhs;
 455 }
 456
 457 /* Traverse statements from CALL backwards, scanning whether the argument ARG
 458    which is a member pointer is filled in with constant values.  If it is, fill
 459    the jump function JFUNC in appropriately.  METHOD_FIELD and DELTA_FIELD are
 460    fields of the record type of the member pointer.  To give an example, we
 461    look for a pattern looking like the following:
 462
 463      D.2515.__pfn ={v} printStuff;
 464      D.2515.__delta ={v} 0;
 465      i_1 = doprinting (D.2515);  */
 466
 467 static void
 468 determine_cst_member_ptr (gimple call, tree arg, tree method_field,
 469                           tree delta_field, struct ipa_jump_func *jfunc)
 470 {
 471   gimple_stmt_iterator gsi;
 472   tree method = NULL_TREE;
 473   tree delta = NULL_TREE;
 474
 475   gsi = gsi_for_stmt (call);
 476
 477   gsi_prev (&gsi);
 478   for (; !gsi_end_p (gsi); gsi_prev (&gsi))
 479     {
 480       gimple stmt = gsi_stmt (gsi);
 481       tree lhs, rhs, fld;
 482
 483       if (!gimple_assign_single_p (stmt))
 484         return;
 485
 486       lhs = gimple_assign_lhs (stmt);
 487       rhs = gimple_assign_rhs1 (stmt);
 488
 489       if (TREE_CODE (lhs) != COMPONENT_REF
 490           || TREE_OPERAND (lhs, 0) != arg)
 491         continue;
 492
 493       fld = TREE_OPERAND (lhs, 1);
 494       if (!method && fld == method_field)
 495         {
 496           rhs = get_ssa_def_if_simple_copy (rhs);
 497           if (TREE_CODE (rhs) == ADDR_EXPR
 498               && TREE_CODE (TREE_OPERAND (rhs, 0)) == FUNCTION_DECL
 499               && TREE_CODE (TREE_TYPE (TREE_OPERAND (rhs, 0))) == METHOD_TYPE)
 500             {
 501               method = TREE_OPERAND (rhs, 0);
 502               if (delta)
 503                 {
 504                   fill_member_ptr_cst_jump_function (jfunc, rhs, delta);
 505                   return;
 506                 }
 507             }
 508           else
 509             return;
 510         }
 511
 512       if (!delta && fld == delta_field)
 513         {
 514           rhs = get_ssa_def_if_simple_copy (rhs);
 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 (!gimple_assign_single_p (stmt))
 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)
 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)
 812       && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
 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 }