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