gcc/ipa-prop.c

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