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
  36 /* Vector where the parameter infos are actually stored. */
  37 VEC (ipa_node_params_t, heap) *ipa_node_params_vector;
  38 /* Vector where the parameter infos are actually stored. */
  39 VEC (ipa_edge_args_t, heap) *ipa_edge_args_vector;
  40
  41 /* Holders of ipa cgraph hooks: */
  42 struct cgraph_edge_hook_list *edge_removal_hook_holder;
  43 struct cgraph_node_hook_list *node_removal_hook_holder;
  44 struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
  45 struct cgraph_2node_hook_list *node_duplication_hook_holder;
  46
  47 /* Initialize worklist to contain all functions.  */
  48 struct ipa_func_list *
  49 ipa_init_func_list (void)
  50 {
  51   struct cgraph_node *node;
  52   struct ipa_func_list * wl;
  53
  54   wl = NULL;
  55   for (node = cgraph_nodes; node; node = node->next)
  56     ipa_push_func_to_list (&wl, node);
  57
  58   return wl;
  59 }
  60
  61 /* Add cgraph node MT to the worklist. Set worklist element WL
  62    to point to MT.  */
  63 void
  64 ipa_push_func_to_list (struct ipa_func_list **wl, struct cgraph_node *mt)
  65 {
  66   struct ipa_func_list *temp;
  67
  68   temp = XCNEW (struct ipa_func_list);
  69   temp->node = mt;
  70   temp->next = *wl;
  71   *wl = temp;
  72 }
  73
  74 /* Remove a function from the worklist. WL points to the first
  75    element in the list, which is removed.  */
  76 struct cgraph_node *
  77 ipa_pop_func_from_list (struct ipa_func_list ** wl)
  78 {
  79   struct ipa_func_list *first;
  80   struct cgraph_node *return_func;
  81
  82   first = *wl;
  83   *wl = (*wl)->next;
  84   return_func = first->node;
  85   free (first);
  86   return return_func;
  87 }
  88
  89 /* Return index of the formal whose tree is ptree in function which corresponds
  90    to info.  */
  91 static int
  92 ipa_get_param_decl_index (struct ipa_node_params *info, tree ptree)
  93 {
  94   int i, count;
  95
  96   count = ipa_get_param_count (info);
  97   for (i = 0; i < count; i++)
  98     if (ipa_get_ith_param(info, i) == ptree)
  99       return i;
 100
 101   return -1;
 102 }
 103
 104 /* Insert the formal trees to the param_decls array in function MT.  */
 105 void
 106 ipa_create_param_decls_array (struct cgraph_node *mt)
 107 {
 108   tree fndecl;
 109   tree fnargs;
 110   tree parm;
 111   int param_num;
 112   struct ipa_node_params *info = IPA_NODE_REF (mt);
 113
 114   info->param_decls = XCNEWVEC (tree, ipa_get_param_count (info));
 115   fndecl = mt->decl;
 116   fnargs = DECL_ARGUMENTS (fndecl);
 117   param_num = 0;
 118   for (parm = fnargs; parm; parm = TREE_CHAIN (parm))
 119     {
 120       info->param_decls[param_num] = parm;
 121       param_num++;
 122     }
 123 }
 124
 125 /* Count number of formals in MT. Insert the result to the
 126    ipa_node_params.  */
 127 void
 128 ipa_count_formal_params (struct cgraph_node *mt)
 129 {
 130   tree fndecl;
 131   tree fnargs;
 132   tree parm;
 133   int param_num;
 134
 135   fndecl = mt->decl;
 136   fnargs = DECL_ARGUMENTS (fndecl);
 137   param_num = 0;
 138   for (parm = fnargs; parm; parm = TREE_CHAIN (parm))
 139     param_num++;
 140   ipa_set_param_count (IPA_NODE_REF (mt), param_num);
 141 }
 142
 143 /* Check STMT to detect whether a formal is modified within MT, the appropriate
 144    entry is updated in the modified_flags array of ipa_node_params (associated
 145    with MT).  */
 146 static void
 147 ipa_check_stmt_modifications (struct cgraph_node *mt, tree stmt)
 148 {
 149   int index, j;
 150   tree parm_decl;
 151   struct ipa_node_params *info;
 152
 153   switch (TREE_CODE (stmt))
 154     {
 155     case GIMPLE_MODIFY_STMT:
 156           if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == PARM_DECL)
 157         {
 158           info = IPA_NODE_REF (mt);
 159           parm_decl = GIMPLE_STMT_OPERAND (stmt, 0);
 160           index = ipa_get_param_decl_index (info, parm_decl);
 161           if (index >= 0)
 162             info->modified_flags[index] = true;
 163         }
 164       break;
 165     case ASM_EXPR:
 166       /* Asm code could modify any of the parameters.  */
 167       info = IPA_NODE_REF (mt);
 168       for (j = 0; j < ipa_get_param_count (IPA_NODE_REF (mt)); j++)
 169         info->modified_flags[j] = true;
 170       break;
 171     default:
 172       break;
 173     }
 174 }
 175
 176 /* The modify computation driver for MT. Compute which formal arguments
 177    of function MT are locally modified.  Formals may be modified in MT
 178    if their address is taken, or if
 179    they appear on the left hand side of an assignment.  */
 180 void
 181 ipa_detect_param_modifications (struct cgraph_node *mt)
 182 {
 183   tree decl;
 184   tree body;
 185   int j, count;
 186   basic_block bb;
 187   struct function *func;
 188   block_stmt_iterator bsi;
 189   tree stmt, parm_tree;
 190   struct ipa_node_params *info = IPA_NODE_REF (mt);
 191
 192   if (ipa_get_param_count (info) == 0 || info->modified_flags)
 193     return;
 194
 195   count = ipa_get_param_count (info);
 196   info->modified_flags = XCNEWVEC (bool, count);
 197   decl = mt->decl;
 198   /* ??? Handle pending sizes case. Set all parameters
 199      of the function to be modified.  */
 200
 201   if (DECL_UNINLINABLE (decl))
 202     {
 203       for (j = 0; j < count; j++)
 204         info->modified_flags[j] = true;
 205
 206       return;
 207     }
 208   /* Formals whose address is taken are considered modified.  */
 209   for (j = 0; j < count; j++)
 210     {
 211       parm_tree = ipa_get_ith_param (info, j);
 212       if (!is_gimple_reg (parm_tree)
 213           && TREE_ADDRESSABLE (parm_tree))
 214         info->modified_flags[j] = true;
 215     }
 216   body = DECL_SAVED_TREE (decl);
 217   if (body != NULL)
 218     {
 219       func = DECL_STRUCT_FUNCTION (decl);
 220       FOR_EACH_BB_FN (bb, func)
 221       {
 222         for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 223           {
 224             stmt = bsi_stmt (bsi);
 225             ipa_check_stmt_modifications (mt, stmt);
 226           }
 227       }
 228     }
 229 }
 230
 231 /* Count number of arguments callsite CS has and store it in
 232    ipa_edge_args structure corresponding to this callsite.  */
 233 void
 234 ipa_count_arguments (struct cgraph_edge *cs)
 235 {
 236   tree call_tree;
 237   int arg_num;
 238
 239   call_tree = get_call_expr_in (cs->call_stmt);
 240   gcc_assert (TREE_CODE (call_tree) == CALL_EXPR);
 241   arg_num = call_expr_nargs (call_tree);
 242   ipa_set_cs_argument_count (IPA_EDGE_REF (cs), arg_num);
 243 }
 244
 245 /* Compute jump function for all arguments of callsite CS
 246    and insert the information in the jump_functions array
 247    in the ipa_edge_args corresponding to this callsite.  */
 248 void
 249 ipa_compute_jump_functions (struct cgraph_edge *cs)
 250 {
 251   tree call_tree;
 252   tree arg, cst_decl;
 253   int arg_num;
 254   struct cgraph_node *mt;
 255   tree parm_decl;
 256   struct function *curr_cfun;
 257   call_expr_arg_iterator iter;
 258   struct ipa_edge_args *args = IPA_EDGE_REF (cs);
 259
 260   if (ipa_get_cs_argument_count (args) == 0 || args->jump_functions)
 261     return;
 262   args->jump_functions = XCNEWVEC (struct ipa_jump_func,
 263                                    ipa_get_cs_argument_count (args));
 264   call_tree = get_call_expr_in (cs->call_stmt);
 265   gcc_assert (TREE_CODE (call_tree) == CALL_EXPR);
 266   arg_num = 0;
 267
 268   FOR_EACH_CALL_EXPR_ARG (arg, iter, call_tree)
 269     {
 270       /* If the formal parameter was passed as argument, we store
 271          IPA_PASS_THROUGH and its index in the caller as the jump function
 272          of this argument.  */
 273       if ((TREE_CODE (arg) == SSA_NAME
 274            && TREE_CODE (SSA_NAME_VAR (arg)) == PARM_DECL)
 275           || TREE_CODE (arg) == PARM_DECL)
 276         {
 277           struct ipa_node_params *info;
 278           int index;
 279
 280           mt = cs->caller;
 281           info = IPA_NODE_REF (mt);
 282           parm_decl = TREE_CODE (arg) == PARM_DECL ? arg : SSA_NAME_VAR (arg);
 283
 284           index = ipa_get_param_decl_index (info, parm_decl);
 285           if (TREE_CODE (arg) == SSA_NAME && IS_VALID_JUMP_FUNC_INDEX (index))
 286             {
 287               curr_cfun = DECL_STRUCT_FUNCTION (mt->decl);
 288               if (!gimple_default_def (curr_cfun, parm_decl)
 289                   || gimple_default_def (curr_cfun, parm_decl) != arg)
 290                 info->modified_flags[index] = true;
 291             }
 292           if (!IS_VALID_JUMP_FUNC_INDEX (index) || info->modified_flags[index])
 293             args->jump_functions[arg_num].type = IPA_UNKNOWN;
 294           else
 295             {
 296               args->jump_functions[arg_num].type = IPA_PASS_THROUGH;
 297               args->jump_functions[arg_num].value.formal_id = index;
 298             }
 299         }
 300       /* If a constant value was passed as argument,
 301          we store IPA_CONST and its value as the jump function
 302          of this argument.  */
 303       else if (TREE_CODE (arg) == INTEGER_CST
 304                || TREE_CODE (arg) == REAL_CST
 305                || TREE_CODE (arg) == FIXED_CST)
 306         {
 307           args->jump_functions[arg_num].type = IPA_CONST;
 308           args->jump_functions[arg_num].value.constant = arg;
 309         }
 310       /* This is for the case of Fortran. If the address of a const_decl
 311          was passed as argument then we store
 312          IPA_CONST_REF/IPA_CONST_REF and the constant
 313          value as the jump function corresponding to this argument.  */
 314       else if (TREE_CODE (arg) == ADDR_EXPR
 315                && TREE_CODE (TREE_OPERAND (arg, 0)) == CONST_DECL)
 316         {
 317           cst_decl = TREE_OPERAND (arg, 0);
 318           if (TREE_CODE (DECL_INITIAL (cst_decl)) == INTEGER_CST
 319               || TREE_CODE (DECL_INITIAL (cst_decl)) == REAL_CST
 320               || TREE_CODE (DECL_INITIAL (cst_decl)) == FIXED_CST)
 321             {
 322               args->jump_functions[arg_num].type = IPA_CONST_REF;
 323               args->jump_functions[arg_num].value.constant = cst_decl;
 324             }
 325         }
 326       else
 327         args->jump_functions[arg_num].type = IPA_UNKNOWN;
 328       arg_num++;
 329     }
 330 }
 331
 332 /* Frees all dynamically allocated structures that the argument info points
 333    to.  */
 334 void
 335 ipa_free_edge_args_substructures (struct ipa_edge_args *args)
 336 {
 337   if (args->jump_functions)
 338     free (args->jump_functions);
 339
 340   memset (args, 0, sizeof (*args));
 341 }
 342
 343 /* Free all ipa_edge structures.  */
 344 void
 345 ipa_free_all_edge_args (void)
 346 {
 347   int i;
 348   struct ipa_edge_args *args;
 349
 350   for (i = 0;
 351        VEC_iterate (ipa_edge_args_t, ipa_edge_args_vector, i, args);
 352        i++)
 353     ipa_free_edge_args_substructures (args);
 354
 355   VEC_free (ipa_edge_args_t, heap, ipa_edge_args_vector);
 356   ipa_edge_args_vector = NULL;
 357 }
 358
 359 /* Frees all dynamically allocated structures that the param info points
 360    to.  */
 361 void
 362 ipa_free_node_params_substructures (struct ipa_node_params *info)
 363 {
 364   if (info->ipcp_lattices)
 365     free (info->ipcp_lattices);
 366   if (info->param_decls)
 367     free (info->param_decls);
 368   if (info->modified_flags)
 369     free (info->modified_flags);
 370
 371   memset (info, 0, sizeof (*info));
 372 }
 373
 374 /* Free all ipa_node_params structures.  */
 375 void
 376 ipa_free_all_node_params (void)
 377 {
 378   int i;
 379   struct ipa_node_params *info;
 380
 381   for (i = 0;
 382        VEC_iterate (ipa_node_params_t, ipa_node_params_vector, i, info);
 383        i++)
 384     ipa_free_node_params_substructures (info);
 385
 386   VEC_free (ipa_node_params_t, heap, ipa_node_params_vector);
 387   ipa_node_params_vector = NULL;
 388 }
 389
 390 /* Hook that is called by cgraph.c when an edge is removed.  */
 391 static void
 392 ipa_edge_removal_hook (struct cgraph_edge *cs,
 393                        void *data __attribute__ ((unused)))
 394 {
 395   ipa_free_edge_args_substructures (IPA_EDGE_REF (cs));
 396 }
 397
 398 /* Hook that is called by cgraph.c when a node is removed.  */
 399 static void
 400 ipa_node_removal_hook (struct cgraph_node *node,
 401                        void *data __attribute__ ((unused)))
 402 {
 403   ipa_free_node_params_substructures (IPA_NODE_REF (node));
 404 }
 405
 406 /* Helper function to duplicate an array of size N that is at SRC and store a
 407    pointer to it to DST.  Nothing is done if SRC is NULL.  */
 408 static void *
 409 duplicate_array (void *src, size_t n)
 410 {
 411   void *p;
 412
 413   if (!src)
 414     return NULL;
 415
 416   p = xcalloc (1, n);
 417   memcpy (p, src, n);
 418   return p;
 419 }
 420
 421 /* Hook that is called by cgraph.c when a node is duplicated.  */
 422 static void
 423 ipa_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
 424                            void *data)
 425 {
 426   struct ipa_edge_args *old_args, *new_args;
 427   int arg_count;
 428
 429   ipa_check_create_edge_args ();
 430
 431   old_args = IPA_EDGE_REF (src);
 432   new_args = IPA_EDGE_REF (dst);
 433
 434   arg_count = ipa_get_cs_argument_count (old_args);
 435   ipa_set_cs_argument_count (new_args, arg_count);
 436   new_args->jump_functions = (struct ipa_jump_func *)
 437     duplicate_array (old_args->jump_functions,
 438                      sizeof (struct ipa_jump_func) * arg_count);
 439   data = data;                  /* Suppressing compiler warning.  */
 440 }
 441
 442 /* Hook that is called by cgraph.c when a node is duplicated.  */
 443 static void
 444 ipa_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
 445                            void *data)
 446 {
 447   struct ipa_node_params *old_info, *new_info;
 448   int param_count;
 449
 450   ipa_check_create_node_params ();
 451   old_info = IPA_NODE_REF (src);
 452   new_info = IPA_NODE_REF (dst);
 453   param_count = ipa_get_param_count (old_info);
 454
 455   ipa_set_param_count (new_info, param_count);
 456   new_info->ipcp_lattices = (struct ipcp_lattice *)
 457     duplicate_array (old_info->ipcp_lattices,
 458                      sizeof (struct ipcp_lattice) * param_count);
 459   new_info->param_decls = (tree *)
 460     duplicate_array (old_info->param_decls, sizeof (tree) * param_count);
 461   new_info->modified_flags = (bool *)
 462     duplicate_array (old_info->modified_flags, sizeof (bool) * param_count);
 463
 464   new_info->ipcp_orig_node = old_info->ipcp_orig_node;
 465   new_info->count_scale = old_info->count_scale;
 466
 467   data = data;                  /* Suppressing compiler warning.  */
 468 }
 469
 470 /* Register our cgraph hooks if they are not already there.  */
 471 void
 472 ipa_register_cgraph_hooks (void)
 473 {
 474   if (!edge_removal_hook_holder)
 475     edge_removal_hook_holder =
 476       cgraph_add_edge_removal_hook (&ipa_edge_removal_hook, NULL);
 477   if (!node_removal_hook_holder)
 478     node_removal_hook_holder =
 479       cgraph_add_node_removal_hook (&ipa_node_removal_hook, NULL);
 480   if (!edge_duplication_hook_holder)
 481     edge_duplication_hook_holder =
 482       cgraph_add_edge_duplication_hook (&ipa_edge_duplication_hook, NULL);
 483   if (!node_duplication_hook_holder)
 484     node_duplication_hook_holder =
 485       cgraph_add_node_duplication_hook (&ipa_node_duplication_hook, NULL);
 486 }
 487
 488 /* Unregister our cgraph hooks if they are not already there.  */
 489 static void
 490 ipa_unregister_cgraph_hooks (void)
 491 {
 492   cgraph_remove_edge_removal_hook (edge_removal_hook_holder);
 493   edge_removal_hook_holder = NULL;
 494   cgraph_remove_node_removal_hook (node_removal_hook_holder);
 495   node_removal_hook_holder = NULL;
 496   cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
 497   edge_duplication_hook_holder = NULL;
 498   cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
 499   node_duplication_hook_holder = NULL;
 500 }
 501
 502 /* Free all ipa_node_params and all ipa_edge_args structures if they are no
 503    longer needed after ipa-cp.  */
 504 void
 505 free_all_ipa_structures_after_ipa_cp (void)
 506 {
 507   ipa_free_all_edge_args ();
 508   ipa_free_all_node_params ();
 509   ipa_unregister_cgraph_hooks ();
 510 }
 511
 512 /* Print ipa_tree_map data structures of all functions in the
 513    callgraph to F.  */
 514 void
 515 ipa_print_all_tree_maps (FILE * f)
 516 {
 517   int i, count;
 518   tree temp;
 519   struct cgraph_node *node;
 520
 521   fprintf (f, "\nPARAM TREE MAP PRINT\n");
 522   for (node = cgraph_nodes; node; node = node->next)
 523     {
 524       struct ipa_node_params *info = IPA_NODE_REF (node);
 525       fprintf (f, "function  %s Trees :: \n", cgraph_node_name (node));
 526       count = ipa_get_param_count (info);
 527       for (i = 0; i < count; i++)
 528         {
 529           temp = ipa_get_ith_param (info, i);
 530           if (TREE_CODE (temp) == PARM_DECL)
 531             fprintf (f, "  param [%d] : %s\n", i,
 532                      (*lang_hooks.decl_printable_name) (temp, 2));
 533         }
 534
 535     }
 536 }
 537
 538 /* Print modified_flags data structures of all functions in the
 539    callgraph to F.  */
 540 void
 541 ipa_print_all_params_modified (FILE * f)
 542 {
 543   int i, count;
 544   bool temp;
 545   struct cgraph_node *node;
 546
 547   fprintf (f, "\nMODIFY PRINT\n");
 548   for (node = cgraph_nodes; node; node = node->next)
 549     {
 550       struct ipa_node_params *info = IPA_NODE_REF (node);
 551       fprintf (f, "function  %s :: \n", cgraph_node_name (node));
 552       count = ipa_get_param_count (info);
 553       for (i = 0; i < count; i++)
 554         {
 555           temp = info->modified_flags[i];
 556           if (temp)
 557             fprintf (f, " param [%d] true \n", i);
 558           else
 559             fprintf (f, " param [%d] false \n", i);
 560         }
 561     }
 562 }
 563