gcc/ipa-prop.c

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