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