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