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
 589    pointer formal parameter, return the parameter, otherwise return
 590    NULL.  If USE_DELTA, then we look for a use of the delta field
 591    rather than the pfn.  */
 592
 593 static tree
 594 ipa_get_member_ptr_load_param (tree rhs, bool use_delta)
 595 {
 596   tree rec, fld;
 597   tree ptr_field;
 598   tree delta_field;
 599
 600   if (TREE_CODE (rhs) != COMPONENT_REF)
 601     return NULL_TREE;
 602
 603   rec = TREE_OPERAND (rhs, 0);
 604   if (TREE_CODE (rec) != PARM_DECL
 605       || !type_like_member_ptr_p (TREE_TYPE (rec), &ptr_field, &delta_field))
 606     return NULL_TREE;
 607
 608   fld = TREE_OPERAND (rhs, 1);
 609   if (use_delta ? (fld == delta_field) : (fld == ptr_field))
 610     return rec;
 611   else
 612     return NULL_TREE;
 613 }
 614
 615 /* If STMT looks like a statement loading a value from a member pointer formal
 616    parameter, this function returns that parameter.  */
 617
 618 static tree
 619 ipa_get_stmt_member_ptr_load_param (gimple stmt, bool use_delta)
 620 {
 621   tree rhs;
 622
 623   if (!gimple_assign_single_p (stmt))
 624     return NULL_TREE;
 625
 626   rhs = gimple_assign_rhs1 (stmt);
 627   return ipa_get_member_ptr_load_param (rhs, use_delta);
 628 }
 629
 630 /* Returns true iff T is an SSA_NAME defined by a statement.  */
 631
 632 static bool
 633 ipa_is_ssa_with_stmt_def (tree t)
 634 {
 635   if (TREE_CODE (t) == SSA_NAME
 636       && !SSA_NAME_IS_DEFAULT_DEF (t))
 637     return true;
 638   else
 639     return false;
 640 }
 641
 642 /* Creates a new note describing a call to a parameter number FORMAL_ID and
 643    attaches it to the linked list of INFO.  It also sets the called flag of the
 644    parameter.  STMT is the corresponding call statement.  */
 645
 646 static void
 647 ipa_note_param_call (struct ipa_node_params *info, int formal_id,
 648                      gimple stmt)
 649 {
 650   struct ipa_param_call_note *note;
 651   basic_block bb = gimple_bb (stmt);
 652
 653   info->params[formal_id].called = 1;
 654
 655   note = XCNEW (struct ipa_param_call_note);
 656   note->formal_id = formal_id;
 657   note->stmt = stmt;
 658   note->count = bb->count;
 659   note->frequency = compute_call_stmt_bb_frequency (current_function_decl, bb);
 660
 661   note->next = info->param_calls;
 662   info->param_calls = note;
 663
 664   return;
 665 }
 666
 667 /* Analyze the CALL and examine uses of formal parameters of the caller
 668    (described by INFO).  Currently it checks whether the call calls a pointer
 669    that is a formal parameter and if so, the parameter is marked with the
 670    called flag and a note describing the call is created.  This is very simple
 671    for ordinary pointers represented in SSA but not-so-nice when it comes to
 672    member pointers.  The ugly part of this function does nothing more than
 673    tries to match the pattern of such a call.  An example of such a pattern is
 674    the gimple dump below, the call is on the last line:
 675
 676      <bb 2>:
 677        f$__delta_5 = f.__delta;
 678        f$__pfn_24 = f.__pfn;
 679        D.2496_3 = (int) f$__pfn_24;
 680        D.2497_4 = D.2496_3 & 1;
 681        if (D.2497_4 != 0)
 682          goto <bb 3>;
 683        else
 684          goto <bb 4>;
 685
 686      <bb 3>:
 687        D.2500_7 = (unsigned int) f$__delta_5;
 688        D.2501_8 = &S + D.2500_7;
 689        D.2502_9 = (int (*__vtbl_ptr_type) (void) * *) D.2501_8;
 690        D.2503_10 = *D.2502_9;
 691        D.2504_12 = f$__pfn_24 + -1;
 692        D.2505_13 = (unsigned int) D.2504_12;
 693        D.2506_14 = D.2503_10 + D.2505_13;
 694        D.2507_15 = *D.2506_14;
 695        iftmp.11_16 = (String:: *) D.2507_15;
 696
 697      <bb 4>:
 698        # iftmp.11_1 = PHI <iftmp.11_16(3), f$__pfn_24(2)>
 699        D.2500_19 = (unsigned int) f$__delta_5;
 700        D.2508_20 = &S + D.2500_19;
 701        D.2493_21 = iftmp.11_1 (D.2508_20, 4);
 702
 703    Such patterns are results of simple calls to a member pointer:
 704
 705      int doprinting (int (MyString::* f)(int) const)
 706      {
 707        MyString S ("somestring");
 708
 709        return (S.*f)(4);
 710      }
 711 */
 712
 713 static void
 714 ipa_analyze_call_uses (struct ipa_node_params *info, gimple call)
 715 {
 716   tree target = gimple_call_fn (call);
 717   gimple def;
 718   tree var;
 719   tree n1, n2;
 720   gimple d1, d2;
 721   tree rec, rec2, cond;
 722   gimple branch;
 723   int index;
 724   basic_block bb, virt_bb, join;
 725
 726   if (TREE_CODE (target) != SSA_NAME)
 727     return;
 728
 729   var = SSA_NAME_VAR (target);
 730   if (SSA_NAME_IS_DEFAULT_DEF (target))
 731     {
 732       /* assuming TREE_CODE (var) == PARM_DECL */
 733       index = ipa_get_param_decl_index (info, var);
 734       if (index >= 0)
 735         ipa_note_param_call (info, index, call);
 736       return;
 737     }
 738
 739   /* Now we need to try to match the complex pattern of calling a member
 740      pointer. */
 741
 742   if (!POINTER_TYPE_P (TREE_TYPE (target))
 743       || TREE_CODE (TREE_TYPE (TREE_TYPE (target))) != METHOD_TYPE)
 744     return;
 745
 746   def = SSA_NAME_DEF_STMT (target);
 747   if (gimple_code (def) != GIMPLE_PHI)
 748     return;
 749
 750   if (gimple_phi_num_args (def) != 2)
 751     return;
 752
 753   /* First, we need to check whether one of these is a load from a member
 754      pointer that is a parameter to this function. */
 755   n1 = PHI_ARG_DEF (def, 0);
 756   n2 = PHI_ARG_DEF (def, 1);
 757   if (!ipa_is_ssa_with_stmt_def (n1) || !ipa_is_ssa_with_stmt_def (n2))
 758     return;
 759   d1 = SSA_NAME_DEF_STMT (n1);
 760   d2 = SSA_NAME_DEF_STMT (n2);
 761
 762   if ((rec = ipa_get_stmt_member_ptr_load_param (d1, false)))
 763     {
 764       if (ipa_get_stmt_member_ptr_load_param (d2, false))
 765         return;
 766
 767       bb = gimple_bb (d1);
 768       virt_bb = gimple_bb (d2);
 769     }
 770   else if ((rec = ipa_get_stmt_member_ptr_load_param (d2, false)))
 771     {
 772       bb = gimple_bb (d2);
 773       virt_bb = gimple_bb (d1);
 774     }
 775   else
 776     return;
 777
 778   /* Second, we need to check that the basic blocks are laid out in the way
 779      corresponding to the pattern. */
 780
 781   join = gimple_bb (def);
 782   if (!single_pred_p (virt_bb) || !single_succ_p (virt_bb)
 783       || single_pred (virt_bb) != bb
 784       || single_succ (virt_bb) != join)
 785     return;
 786
 787   /* Third, let's see that the branching is done depending on the least
 788      significant bit of the pfn. */
 789
 790   branch = last_stmt (bb);
 791   if (gimple_code (branch) != GIMPLE_COND)
 792     return;
 793
 794   if (gimple_cond_code (branch) != NE_EXPR
 795       || !integer_zerop (gimple_cond_rhs (branch)))
 796     return;
 797
 798   cond = gimple_cond_lhs (branch);
 799   if (!ipa_is_ssa_with_stmt_def (cond))
 800     return;
 801
 802   def = SSA_NAME_DEF_STMT (cond);
 803   if (!is_gimple_assign (def)
 804       || gimple_assign_rhs_code (def) != BIT_AND_EXPR
 805       || !integer_onep (gimple_assign_rhs2 (def)))
 806     return;
 807
 808   cond = gimple_assign_rhs1 (def);
 809   if (!ipa_is_ssa_with_stmt_def (cond))
 810     return;
 811
 812   def = SSA_NAME_DEF_STMT (cond);
 813
 814   if (is_gimple_assign (def)
 815       && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
 816     {
 817       cond = gimple_assign_rhs1 (def);
 818       if (!ipa_is_ssa_with_stmt_def (cond))
 819         return;
 820       def = SSA_NAME_DEF_STMT (cond);
 821     }
 822
 823   rec2 = ipa_get_stmt_member_ptr_load_param (def,
 824                                              (TARGET_PTRMEMFUNC_VBIT_LOCATION
 825                                               == ptrmemfunc_vbit_in_delta));
 826
 827   if (rec != rec2)
 828     return;
 829
 830   index = ipa_get_param_decl_index (info, rec);
 831   if (index >= 0 && !ipa_is_param_modified (info, index))
 832     ipa_note_param_call (info, index, call);
 833
 834   return;
 835 }
 836
 837 /* Analyze the statement STMT with respect to formal parameters (described in
 838    INFO) and their uses.  Currently it only checks whether formal parameters
 839    are called.  */
 840
 841 static void
 842 ipa_analyze_stmt_uses (struct ipa_node_params *info, gimple stmt)
 843 {
 844   if (is_gimple_call (stmt))
 845     ipa_analyze_call_uses (info, stmt);
 846 }
 847
 848 /* Scan the function body of NODE and inspect the uses of formal parameters.
 849    Store the findings in various structures of the associated ipa_node_params
 850    structure, such as parameter flags, notes etc.  */
 851
 852 void
 853 ipa_analyze_params_uses (struct cgraph_node *node)
 854 {
 855   tree decl = node->decl;
 856   basic_block bb;
 857   struct function *func;
 858   gimple_stmt_iterator gsi;
 859   struct ipa_node_params *info = IPA_NODE_REF (node);
 860
 861   if (ipa_get_param_count (info) == 0 || info->uses_analysis_done)
 862     return;
 863
 864   func = DECL_STRUCT_FUNCTION (decl);
 865   FOR_EACH_BB_FN (bb, func)
 866     {
 867       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 868         {
 869           gimple stmt = gsi_stmt (gsi);
 870           ipa_analyze_stmt_uses (info, stmt);
 871         }
 872     }
 873
 874   info->uses_analysis_done = 1;
 875 }
 876
 877 /* Update the jump functions associated with call graph edge E when the call
 878    graph edge CS is being inlined, assuming that E->caller is already (possibly
 879    indirectly) inlined into CS->callee and that E has not been inlined.  */
 880
 881 static void
 882 update_jump_functions_after_inlining (struct cgraph_edge *cs,
 883                                       struct cgraph_edge *e)
 884 {
 885   struct ipa_edge_args *top = IPA_EDGE_REF (cs);
 886   struct ipa_edge_args *args = IPA_EDGE_REF (e);
 887   int count = ipa_get_cs_argument_count (args);
 888   int i;
 889
 890   for (i = 0; i < count; i++)
 891     {
 892       struct ipa_jump_func *src, *dst = ipa_get_ith_jump_func (args, i);
 893
 894       if (dst->type != IPA_JF_PASS_THROUGH)
 895         continue;
 896
 897       /* We must check range due to calls with variable number of arguments:  */
 898       if (dst->value.formal_id >= (unsigned) ipa_get_cs_argument_count (top))
 899         {
 900           dst->type = IPA_JF_UNKNOWN;
 901           continue;
 902         }
 903
 904       src = ipa_get_ith_jump_func (top, dst->value.formal_id);
 905       *dst = *src;
 906     }
 907 }
 908
 909 /* Print out a debug message to file F that we have discovered that an indirect
 910    call described by NT is in fact a call of a known constant function described
 911    by JFUNC.  NODE is the node where the call is.  */
 912
 913 static void
 914 print_edge_addition_message (FILE *f, struct ipa_param_call_note *nt,
 915                              struct ipa_jump_func *jfunc,
 916                              struct cgraph_node *node)
 917 {
 918   fprintf (f, "ipa-prop: Discovered an indirect call to a known target (");
 919   if (jfunc->type == IPA_JF_CONST_MEMBER_PTR)
 920     {
 921       print_node_brief (f, "", jfunc->value.member_cst.pfn, 0);
 922       print_node_brief (f, ", ", jfunc->value.member_cst.delta, 0);
 923     }
 924   else
 925     print_node_brief(f, "", jfunc->value.constant, 0);
 926
 927   fprintf (f, ") in %s: ", cgraph_node_name (node));
 928   print_gimple_stmt (f, nt->stmt, 2, TDF_SLIM);
 929 }
 930
 931 /* Update the param called notes associated with NODE when CS is being inlined,
 932    assuming NODE is (potentially indirectly) inlined into CS->callee.
 933    Moreover, if the callee is discovered to be constant, create a new cgraph
 934    edge for it.  Newly discovered indirect edges will be added to *NEW_EDGES,
 935    unless NEW_EDGES is NULL.  Return true iff a new edge(s) were created.  */
 936
 937 static bool
 938 update_call_notes_after_inlining (struct cgraph_edge *cs,
 939                                   struct cgraph_node *node,
 940                                   VEC (cgraph_edge_p, heap) **new_edges)
 941 {
 942   struct ipa_node_params *info = IPA_NODE_REF (node);
 943   struct ipa_edge_args *top = IPA_EDGE_REF (cs);
 944   struct ipa_param_call_note *nt;
 945   bool res = false;
 946
 947   for (nt = info->param_calls; nt; nt = nt->next)
 948     {
 949       struct ipa_jump_func *jfunc;
 950
 951       if (nt->processed)
 952         continue;
 953
 954       /* We must check range due to calls with variable number of arguments:  */
 955       if (nt->formal_id >= (unsigned) ipa_get_cs_argument_count (top))
 956         {
 957           nt->processed = true;
 958           continue;
 959         }
 960
 961       jfunc = ipa_get_ith_jump_func (top, nt->formal_id);
 962       if (jfunc->type == IPA_JF_PASS_THROUGH)
 963         nt->formal_id = jfunc->value.formal_id;
 964       else if (jfunc->type == IPA_JF_CONST
 965                || jfunc->type == IPA_JF_CONST_MEMBER_PTR)
 966         {
 967           struct cgraph_node *callee;
 968           struct cgraph_edge *new_indirect_edge;
 969           tree decl;
 970
 971           nt->processed = true;
 972           if (jfunc->type == IPA_JF_CONST_MEMBER_PTR)
 973             decl = jfunc->value.member_cst.pfn;
 974           else
 975             decl = jfunc->value.constant;
 976
 977           if (TREE_CODE (decl) != ADDR_EXPR)
 978             continue;
 979           decl = TREE_OPERAND (decl, 0);
 980
 981           if (TREE_CODE (decl) != FUNCTION_DECL)
 982             continue;
 983           callee = cgraph_node (decl);
 984           if (!callee || !callee->local.inlinable)
 985             continue;
 986
 987           res = true;
 988           if (dump_file)
 989             print_edge_addition_message (dump_file, nt, jfunc, node);
 990
 991           new_indirect_edge = cgraph_create_edge (node, callee, nt->stmt,
 992                                                   nt->count, nt->frequency,
 993                                                   nt->loop_nest);
 994           new_indirect_edge->indirect_call = 1;
 995           ipa_check_create_edge_args ();
 996           if (new_edges)
 997             VEC_safe_push (cgraph_edge_p, heap, *new_edges, new_indirect_edge);
 998           top = IPA_EDGE_REF (cs);
 999         }
1000     }
1001   return res;
1002 }
1003
1004 /* Recursively traverse subtree of NODE (including node) made of inlined
1005    cgraph_edges when CS has been inlined and invoke
1006    update_call_notes_after_inlining on all nodes and
1007    update_jump_functions_after_inlining on all non-inlined edges that lead out
1008    of this subtree.  Newly discovered indirect edges will be added to
1009    *NEW_EDGES, unless NEW_EDGES is NULL.  Return true iff a new edge(s) were
1010    created.  */
1011
1012 static bool
1013 propagate_info_to_inlined_callees (struct cgraph_edge *cs,
1014                                    struct cgraph_node *node,
1015                                    VEC (cgraph_edge_p, heap) **new_edges)
1016 {
1017   struct cgraph_edge *e;
1018   bool res;
1019
1020   res = update_call_notes_after_inlining (cs, node, new_edges);
1021
1022   for (e = node->callees; e; e = e->next_callee)
1023     if (!e->inline_failed)
1024       res |= propagate_info_to_inlined_callees (cs, e->callee, new_edges);
1025     else
1026       update_jump_functions_after_inlining (cs, e);
1027
1028   return res;
1029 }
1030
1031 /* Update jump functions and call note functions on inlining the call site CS.
1032    CS is expected to lead to a node already cloned by
1033    cgraph_clone_inline_nodes.  Newly discovered indirect edges will be added to
1034    *NEW_EDGES, unless NEW_EDGES is NULL.  Return true iff a new edge(s) were +
1035    created.  */
1036
1037 bool
1038 ipa_propagate_indirect_call_infos (struct cgraph_edge *cs,
1039                                    VEC (cgraph_edge_p, heap) **new_edges)
1040 {
1041   /* Do nothing if the preparation phase has not been carried out yet
1042      (i.e. during early inlining).  */
1043   if (!ipa_node_params_vector)
1044     return false;
1045   gcc_assert (ipa_edge_args_vector);
1046
1047   return propagate_info_to_inlined_callees (cs, cs->callee, new_edges);
1048 }
1049
1050 /* Frees all dynamically allocated structures that the argument info points
1051    to.  */
1052
1053 void
1054 ipa_free_edge_args_substructures (struct ipa_edge_args *args)
1055 {
1056   if (args->jump_functions)
1057     free (args->jump_functions);
1058
1059   memset (args, 0, sizeof (*args));
1060 }
1061
1062 /* Free all ipa_edge structures.  */
1063
1064 void
1065 ipa_free_all_edge_args (void)
1066 {
1067   int i;
1068   struct ipa_edge_args *args;
1069
1070   for (i = 0;
1071        VEC_iterate (ipa_edge_args_t, ipa_edge_args_vector, i, args);
1072        i++)
1073     ipa_free_edge_args_substructures (args);
1074
1075   VEC_free (ipa_edge_args_t, heap, ipa_edge_args_vector);
1076   ipa_edge_args_vector = NULL;
1077 }
1078
1079 /* Frees all dynamically allocated structures that the param info points
1080    to.  */
1081
1082 void
1083 ipa_free_node_params_substructures (struct ipa_node_params *info)
1084 {
1085   if (info->params)
1086     free (info->params);
1087
1088   while (info->param_calls)
1089     {
1090       struct ipa_param_call_note *note = info->param_calls;
1091       info->param_calls = note->next;
1092       free (note);
1093     }
1094
1095   memset (info, 0, sizeof (*info));
1096 }
1097
1098 /* Free all ipa_node_params structures.  */
1099
1100 void
1101 ipa_free_all_node_params (void)
1102 {
1103   int i;
1104   struct ipa_node_params *info;
1105
1106   for (i = 0;
1107        VEC_iterate (ipa_node_params_t, ipa_node_params_vector, i, info);
1108        i++)
1109     ipa_free_node_params_substructures (info);
1110
1111   VEC_free (ipa_node_params_t, heap, ipa_node_params_vector);
1112   ipa_node_params_vector = NULL;
1113 }
1114
1115 /* Hook that is called by cgraph.c when an edge is removed.  */
1116
1117 static void
1118 ipa_edge_removal_hook (struct cgraph_edge *cs, void *data ATTRIBUTE_UNUSED)
1119 {
1120   /* During IPA-CP updating we can be called on not-yet analyze clones.  */
1121   if (VEC_length (ipa_edge_args_t, ipa_edge_args_vector)
1122       <= (unsigned)cs->uid)
1123     return;
1124   ipa_free_edge_args_substructures (IPA_EDGE_REF (cs));
1125 }
1126
1127 /* Hook that is called by cgraph.c when a node is removed.  */
1128
1129 static void
1130 ipa_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
1131 {
1132   ipa_free_node_params_substructures (IPA_NODE_REF (node));
1133 }
1134
1135 /* Helper function to duplicate an array of size N that is at SRC and store a
1136    pointer to it to DST.  Nothing is done if SRC is NULL.  */
1137
1138 static void *
1139 duplicate_array (void *src, size_t n)
1140 {
1141   void *p;
1142
1143   if (!src)
1144     return NULL;
1145
1146   p = xcalloc (1, n);
1147   memcpy (p, src, n);
1148   return p;
1149 }
1150
1151 /* Hook that is called by cgraph.c when a node is duplicated.  */
1152
1153 static void
1154 ipa_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
1155                            __attribute__((unused)) void *data)
1156 {
1157   struct ipa_edge_args *old_args, *new_args;
1158   int arg_count;
1159
1160   ipa_check_create_edge_args ();
1161
1162   old_args = IPA_EDGE_REF (src);
1163   new_args = IPA_EDGE_REF (dst);
1164
1165   arg_count = ipa_get_cs_argument_count (old_args);
1166   ipa_set_cs_argument_count (new_args, arg_count);
1167   new_args->jump_functions = (struct ipa_jump_func *)
1168     duplicate_array (old_args->jump_functions,
1169                      sizeof (struct ipa_jump_func) * arg_count);
1170 }
1171
1172 /* Hook that is called by cgraph.c when a node is duplicated.  */
1173
1174 static void
1175 ipa_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
1176                            __attribute__((unused)) void *data)
1177 {
1178   struct ipa_node_params *old_info, *new_info;
1179   struct ipa_param_call_note *note;
1180   int param_count;
1181
1182   ipa_check_create_node_params ();
1183   old_info = IPA_NODE_REF (src);
1184   new_info = IPA_NODE_REF (dst);
1185   param_count = ipa_get_param_count (old_info);
1186
1187   ipa_set_param_count (new_info, param_count);
1188   new_info->params = (struct ipa_param_descriptor *)
1189     duplicate_array (old_info->params,
1190                      sizeof (struct ipa_param_descriptor) * param_count);
1191   new_info->ipcp_orig_node = old_info->ipcp_orig_node;
1192   new_info->count_scale = old_info->count_scale;
1193
1194   for (note = old_info->param_calls; note; note = note->next)
1195     {
1196       struct ipa_param_call_note *nn;
1197
1198       nn = (struct ipa_param_call_note *)
1199         xcalloc (1, sizeof (struct ipa_param_call_note));
1200       memcpy (nn, note, sizeof (struct ipa_param_call_note));
1201       nn->next = new_info->param_calls;
1202       new_info->param_calls = nn;
1203     }
1204 }
1205
1206 /* Register our cgraph hooks if they are not already there.  */
1207
1208 void
1209 ipa_register_cgraph_hooks (void)
1210 {
1211   if (!edge_removal_hook_holder)
1212     edge_removal_hook_holder =
1213       cgraph_add_edge_removal_hook (&ipa_edge_removal_hook, NULL);
1214   if (!node_removal_hook_holder)
1215     node_removal_hook_holder =
1216       cgraph_add_node_removal_hook (&ipa_node_removal_hook, NULL);
1217   if (!edge_duplication_hook_holder)
1218     edge_duplication_hook_holder =
1219       cgraph_add_edge_duplication_hook (&ipa_edge_duplication_hook, NULL);
1220   if (!node_duplication_hook_holder)
1221     node_duplication_hook_holder =
1222       cgraph_add_node_duplication_hook (&ipa_node_duplication_hook, NULL);
1223 }
1224
1225 /* Unregister our cgraph hooks if they are not already there.  */
1226
1227 static void
1228 ipa_unregister_cgraph_hooks (void)
1229 {
1230   cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
1231   edge_removal_hook_holder = NULL;
1232   cgraph_remove_node_removal_hook (node_removal_hook_holder);
1233   node_removal_hook_holder = NULL;
1234   cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
1235   edge_duplication_hook_holder = NULL;
1236   cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
1237   node_duplication_hook_holder = NULL;
1238 }
1239
1240 /* Free all ipa_node_params and all ipa_edge_args structures if they are no
1241    longer needed after ipa-cp.  */
1242
1243 void
1244 free_all_ipa_structures_after_ipa_cp (void)
1245 {
1246   if (!flag_indirect_inlining)
1247     {
1248       ipa_free_all_edge_args ();
1249       ipa_free_all_node_params ();
1250       ipa_unregister_cgraph_hooks ();
1251     }
1252 }
1253
1254 /* Free all ipa_node_params and all ipa_edge_args structures if they are no
1255    longer needed after indirect inlining.  */
1256
1257 void
1258 free_all_ipa_structures_after_iinln (void)
1259 {
1260   ipa_free_all_edge_args ();
1261   ipa_free_all_node_params ();
1262   ipa_unregister_cgraph_hooks ();
1263 }
1264
1265 /* Print ipa_tree_map data structures of all functions in the
1266    callgraph to F.  */
1267
1268 void
1269 ipa_print_node_params (FILE * f, struct cgraph_node *node)
1270 {
1271   int i, count;
1272   tree temp;
1273   struct ipa_node_params *info;
1274
1275   if (!node->analyzed)
1276     return;
1277   info = IPA_NODE_REF (node);
1278   fprintf (f, "  function  %s Trees :: \n", cgraph_node_name (node));
1279   count = ipa_get_param_count (info);
1280   for (i = 0; i < count; i++)
1281     {
1282       temp = ipa_get_param (info, i);
1283       if (TREE_CODE (temp) == PARM_DECL)
1284         fprintf (f, "    param %d : %s", i,
1285                  (*lang_hooks.decl_printable_name) (temp, 2));
1286       if (ipa_is_param_modified (info, i))
1287         fprintf (f, " modified");
1288       if (ipa_is_param_called (info, i))
1289         fprintf (f, " called");
1290       fprintf (f, "\n");
1291     }
1292 }
1293
1294 /* Print ipa_tree_map data structures of all functions in the
1295    callgraph to F.  */
1296
1297 void
1298 ipa_print_all_params (FILE * f)
1299 {
1300   struct cgraph_node *node;
1301
1302   fprintf (f, "\nFunction parameters:\n");
1303   for (node = cgraph_nodes; node; node = node->next)
1304     ipa_print_node_params (f, node);
1305 }