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 "flags.h"
  32 #include "timevar.h"
  33
  34 /* This file contains interfaces that can be used for various IPA
  35    optimizations:
  36
  37    - ipa_methodlist interface - It is used to create and handle a temporary
  38    worklist used in  the propagation stage of IPCP. (can be used for more
  39    IPA optimizations).
  40
  41    - ipa_callsite interface - for each callsite this interface creates and
  42    handles ipa_edge structure associated with it.
  43
  44    - ipa_method interface - for each method this interface creates and
  45    handles ipa_node structure associated with it.  */
  46
  47 /* ipa_methodlist interface.  */
  48
  49 /* Create a new worklist node.  */
  50 static inline ipa_methodlist_p
  51 ipa_create_methodlist_node (void)
  52 {
  53   return (ipa_methodlist_p) xcalloc (1, sizeof (struct ipa_methodlist));
  54 }
  55
  56 /* Return true if worklist WL is empty.  */
  57 bool
  58 ipa_methodlist_not_empty (ipa_methodlist_p wl)
  59 {
  60   return (wl != NULL);
  61 }
  62
  63 /* Return the method in worklist element WL.  */
  64 static inline struct cgraph_node *
  65 ipa_methodlist_method (ipa_methodlist_p wl)
  66 {
  67   return wl->method_p;
  68 }
  69
  70 /* Make worklist element WL point to method MT in the callgraph.  */
  71 static inline void
  72 ipa_methodlist_method_set (ipa_methodlist_p wl, struct cgraph_node *mt)
  73 {
  74   wl->method_p = mt;
  75 }
  76
  77 /* Return the next element in the worklist following worklist
  78    element WL.  */
  79 static inline ipa_methodlist_p
  80 ipa_methodlist_next_method (ipa_methodlist_p wl)
  81 {
  82   return wl->next_method;
  83 }
  84
  85 /* Set worklist element WL1 to point to worklist element WL2.  */
  86 static inline void
  87 ipa_methodlist_next_method_set (ipa_methodlist_p wl1, ipa_methodlist_p wl2)
  88 {
  89   wl1->next_method = wl2;
  90 }
  91
  92 /* Initialize worklist to contain all methods.  */
  93 ipa_methodlist_p
  94 ipa_methodlist_init (void)
  95 {
  96   struct cgraph_node *node;
  97   ipa_methodlist_p wl;
  98
  99   wl = NULL;
 100   for (node = cgraph_nodes; node; node = node->next)
 101     ipa_add_method (&wl, node);
 102
 103   return wl;
 104 }
 105
 106 /* Add method MT to the worklist. Set worklist element WL
 107    to point to MT.  */
 108 void
 109 ipa_add_method (ipa_methodlist_p * wl, struct cgraph_node *mt)
 110 {
 111   ipa_methodlist_p temp;
 112
 113   temp = ipa_create_methodlist_node ();
 114   ipa_methodlist_method_set (temp, mt);
 115   ipa_methodlist_next_method_set (temp, *wl);
 116   *wl = temp;
 117 }
 118
 119 /* Remove a method from the worklist. WL points to the first
 120    element in the list, which is removed.  */
 121 struct cgraph_node *
 122 ipa_remove_method (ipa_methodlist_p * wl)
 123 {
 124   ipa_methodlist_p first;
 125   struct cgraph_node *return_method;
 126
 127   first = *wl;
 128   *wl = ipa_methodlist_next_method (*wl);
 129   return_method = ipa_methodlist_method (first);
 130   free (first);
 131   return return_method;
 132 }
 133
 134 /* ipa_method interface.  */
 135
 136 /* Return number of formals of method MT.  */
 137 int
 138 ipa_method_formal_count (struct cgraph_node *mt)
 139 {
 140   return IPA_NODE_REF (mt)->ipa_arg_num;
 141 }
 142
 143 /* Set number of formals of method MT to I.  */
 144 void
 145 ipa_method_formal_count_set (struct cgraph_node *mt, int i)
 146 {
 147   IPA_NODE_REF (mt)->ipa_arg_num = i;
 148 }
 149
 150 /* Return whether I-th formal of MT is modified in MT.  */
 151 static inline bool
 152 ipa_method_is_modified (struct cgraph_node *mt, int i)
 153 {
 154   return IPA_NODE_REF (mt)->ipa_mod[i];
 155 }
 156
 157 /* Return the tree of I-th formal of MT.  */
 158 tree
 159 ipa_method_get_tree (struct cgraph_node *mt, int i)
 160 {
 161   return IPA_NODE_REF (mt)->ipa_param_tree[i];
 162 }
 163
 164 /* Create tree map structure for MT.  */
 165 static inline void
 166 ipa_method_tree_map_create (struct cgraph_node *mt)
 167 {
 168   IPA_NODE_REF (mt)->ipa_param_tree =
 169     XCNEWVEC (tree, ipa_method_formal_count (mt));
 170 }
 171
 172 /* Create modify structure for MT.  */
 173 static inline void
 174 ipa_method_modify_create (struct cgraph_node *mt)
 175 {
 176   ((struct ipa_node *) mt->aux)->ipa_mod =
 177     XCNEWVEC (bool, ipa_method_formal_count (mt));
 178 }
 179
 180 /* Set modify of I-th formal of MT to VAL.  */
 181 static inline void
 182 ipa_method_modify_set (struct cgraph_node *mt, int i, bool val)
 183 {
 184   IPA_NODE_REF (mt)->ipa_mod[i] = val;
 185 }
 186
 187 /* Return index of the formal whose tree is PTREE in method MT.  */
 188 static int
 189 ipa_method_tree_map (struct cgraph_node *mt, tree ptree)
 190 {
 191   int i, count;
 192
 193   count = ipa_method_formal_count (mt);
 194   for (i = 0; i < count; i++)
 195     if (IPA_NODE_REF (mt)->ipa_param_tree[i] == ptree)
 196       return i;
 197
 198   return -1;
 199 }
 200
 201 /* Insert the formal trees to the ipa_param_tree array in method MT.  */
 202 void
 203 ipa_method_compute_tree_map (struct cgraph_node *mt)
 204 {
 205   tree fndecl;
 206   tree fnargs;
 207   tree parm;
 208   int param_num;
 209
 210   ipa_method_tree_map_create (mt);
 211   fndecl = mt->decl;
 212   fnargs = DECL_ARGUMENTS (fndecl);
 213   param_num = 0;
 214   for (parm = fnargs; parm; parm = TREE_CHAIN (parm))
 215     {
 216       IPA_NODE_REF (mt)->ipa_param_tree[param_num] = parm;
 217       param_num++;
 218     }
 219 }
 220
 221 /* Count number of formals in MT. Insert the result to the
 222    ipa_node.  */
 223 void
 224 ipa_method_formal_compute_count (struct cgraph_node *mt)
 225 {
 226   tree fndecl;
 227   tree fnargs;
 228   tree parm;
 229   int param_num;
 230
 231   fndecl = mt->decl;
 232   fnargs = DECL_ARGUMENTS (fndecl);
 233   param_num = 0;
 234   for (parm = fnargs; parm; parm = TREE_CHAIN (parm))
 235     param_num++;
 236   ipa_method_formal_count_set (mt, param_num);
 237 }
 238
 239 /* Check STMT to detect whether a formal is modified within MT,
 240    the appropriate entry is updated in the ipa_mod array of ipa_node
 241    (associated with MT).  */
 242 static void
 243 ipa_method_modify_stmt (struct cgraph_node *mt, tree stmt)
 244 {
 245   int i, j;
 246   tree parm_decl;
 247
 248   switch (TREE_CODE (stmt))
 249     {
 250     case GIMPLE_MODIFY_STMT:
 251           if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == PARM_DECL)
 252         {
 253           parm_decl = GIMPLE_STMT_OPERAND (stmt, 0);
 254           i = ipa_method_tree_map (mt, parm_decl);
 255           if (i >= 0)
 256             ipa_method_modify_set (mt, i, true);
 257         }
 258       break;
 259     case ASM_EXPR:
 260       /* Asm code could modify any of the parameters.  */
 261       for (j = 0; j < ipa_method_formal_count (mt); j++)
 262         ipa_method_modify_set (mt, j, true);
 263       break;
 264     default:
 265       break;
 266     }
 267 }
 268
 269 /* Initialize ipa_mod array of MT.  */
 270 static void
 271 ipa_method_modify_init (struct cgraph_node *mt)
 272 {
 273   int i, count;
 274
 275   ipa_method_modify_create (mt);
 276   count = ipa_method_formal_count (mt);
 277   for (i = 0; i < count; i++)
 278     ipa_method_modify_set (mt, i, false);
 279 }
 280
 281 /* The modify computation driver for MT. Compute which formal arguments
 282    of method MT are locally modified.  Formals may be modified in MT
 283    if their address is taken, or if
 284    they appear on the left hand side of an assignment.  */
 285 void
 286 ipa_method_compute_modify (struct cgraph_node *mt)
 287 {
 288   tree decl;
 289   tree body;
 290   int j, count;
 291   basic_block bb;
 292   struct function *func;
 293   block_stmt_iterator bsi;
 294   tree stmt, parm_tree;
 295
 296   if (ipa_method_formal_count (mt) == 0)
 297     return;
 298
 299   ipa_method_modify_init (mt);
 300   decl = mt->decl;
 301   count = ipa_method_formal_count (mt);
 302   /* ??? Handle pending sizes case. Set all parameters
 303      of the method to be modified.  */
 304
 305   if (DECL_UNINLINABLE (decl))
 306     {
 307       for (j = 0; j < count; j++)
 308         ipa_method_modify_set (mt, j, true);
 309       return;
 310     }
 311   /* Formals whose address is taken are considered modified.  */
 312   for (j = 0; j < count; j++)
 313     {
 314       parm_tree = ipa_method_get_tree (mt, j);
 315       if (!is_gimple_reg (parm_tree)
 316           && TREE_ADDRESSABLE (parm_tree))
 317         ipa_method_modify_set (mt, j, true);
 318     }
 319   body = DECL_SAVED_TREE (decl);
 320   if (body != NULL)
 321     {
 322       func = DECL_STRUCT_FUNCTION (decl);
 323       FOR_EACH_BB_FN (bb, func)
 324       {
 325         for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 326           {
 327             stmt = bsi_stmt (bsi);
 328             ipa_method_modify_stmt (mt, stmt);
 329           }
 330       }
 331     }
 332 }
 333
 334
 335 /* ipa_callsite interface.  */
 336
 337 /* Return number of arguments in callsite CS.  */
 338 int
 339 ipa_callsite_param_count (struct cgraph_edge *cs)
 340 {
 341   return IPA_EDGE_REF (cs)->ipa_param_num;
 342 }
 343
 344 /* Set number of arguments in callsite CS to I.  */
 345 void
 346 ipa_callsite_param_count_set (struct cgraph_edge *cs, int i)
 347 {
 348   IPA_EDGE_REF (cs)->ipa_param_num = i;
 349 }
 350
 351 /* Return the jump function (ipa_jump_func struct) for argument I of
 352    callsite CS.  */
 353 struct ipa_jump_func *
 354 ipa_callsite_param (struct cgraph_edge *cs, int i)
 355 {
 356   return &(IPA_EDGE_REF (cs)->ipa_param_map[i]);
 357 }
 358
 359 /* return the callee (cgraph_node) of callsite CS.  */
 360 struct cgraph_node *
 361 ipa_callsite_callee (struct cgraph_edge *cs)
 362 {
 363   return cs->callee;
 364 }
 365
 366 /* Set field 'type' of jump function (ipa_jump_func struct) of argument I
 367    in callsite CS.  */
 368 static inline void
 369 ipa_callsite_param_set_type (struct cgraph_edge *cs, int i,
 370                              enum jump_func_type type1)
 371 {
 372   IPA_EDGE_REF (cs)->ipa_param_map[i].type = type1;
 373 }
 374
 375 /* Set FORMAL as 'info_type' field of jump function (ipa_jump_func struct)
 376    of argument I of callsite CS.  */
 377 static inline void
 378 ipa_callsite_param_set_info_type_formal (struct cgraph_edge *cs, int i,
 379                                          unsigned int formal)
 380 {
 381   ipa_callsite_param (cs, i)->info_type.formal_id = formal;
 382 }
 383
 384 /* Set int-valued INFO_TYPE1 as 'info_type' field of
 385    jump function (ipa_jump_func struct) of argument I of callsite CS.  */
 386 static inline void
 387 ipa_callsite_param_set_info_type (struct cgraph_edge *cs, int i,
 388                                   tree info_type1)
 389 {
 390   ipa_callsite_param (cs, i)->info_type.value = info_type1;
 391 }
 392
 393 /* Allocate space for callsite CS.  */
 394 static inline void
 395 ipa_callsite_param_map_create (struct cgraph_edge *cs)
 396 {
 397   IPA_EDGE_REF (cs)->ipa_param_map =
 398     XCNEWVEC (struct ipa_jump_func, ipa_callsite_param_count (cs));
 399 }
 400
 401 /* Return the call expr tree related to callsite CS.  */
 402 static inline tree
 403 ipa_callsite_tree (struct cgraph_edge *cs)
 404 {
 405   return cs->call_stmt;
 406 }
 407
 408 /* Return the caller (cgraph_node) of CS.  */
 409 static inline struct cgraph_node *
 410 ipa_callsite_caller (struct cgraph_edge *cs)
 411 {
 412   return cs->caller;
 413 }
 414
 415 /* Count number of arguments callsite CS has and store it in
 416    ipa_edge structure corresponding to this callsite.  */
 417 void
 418 ipa_callsite_compute_count (struct cgraph_edge *cs)
 419 {
 420   tree call_tree;
 421   int arg_num;
 422
 423   call_tree = get_call_expr_in (ipa_callsite_tree (cs));
 424   gcc_assert (TREE_CODE (call_tree) == CALL_EXPR);
 425   arg_num = call_expr_nargs (call_tree);
 426   ipa_callsite_param_count_set (cs, arg_num);
 427 }
 428
 429 /* Compute jump function for all arguments of callsite CS
 430    and insert the information in the ipa_param_map array
 431    in the ipa_edge corresponding to this callsite. (Explanation
 432    on jump functions is in ipa-prop.h).  */
 433 void
 434 ipa_callsite_compute_param (struct cgraph_edge *cs)
 435 {
 436   tree call_tree;
 437   tree arg, cst_decl;
 438   int arg_num;
 439   int i;
 440   struct cgraph_node *mt;
 441   tree parm_decl;
 442   struct function *curr_cfun;
 443   call_expr_arg_iterator iter;
 444
 445   if (ipa_callsite_param_count (cs) == 0)
 446     return;
 447   ipa_callsite_param_map_create (cs);
 448   call_tree = get_call_expr_in (ipa_callsite_tree (cs));
 449   gcc_assert (TREE_CODE (call_tree) == CALL_EXPR);
 450   arg_num = 0;
 451
 452   FOR_EACH_CALL_EXPR_ARG (arg, iter, call_tree)
 453     {
 454       /* If the formal parameter was passed as argument, we store
 455          FORMAL_IPATYPE and its index in the caller as the jump function
 456          of this argument.  */
 457       if ((TREE_CODE (arg) == SSA_NAME
 458            && TREE_CODE (SSA_NAME_VAR (arg)) == PARM_DECL)
 459           || TREE_CODE (arg) == PARM_DECL)
 460         {
 461           mt = ipa_callsite_caller (cs);
 462           parm_decl = TREE_CODE (arg) == PARM_DECL ? arg : SSA_NAME_VAR (arg);
 463
 464           i = ipa_method_tree_map (mt, parm_decl);
 465           if (TREE_CODE (arg) == SSA_NAME && IS_VALID_TREE_MAP_INDEX (i))
 466             {
 467               curr_cfun = DECL_STRUCT_FUNCTION (mt->decl);
 468               if (!gimple_default_def (curr_cfun, parm_decl)
 469                   || gimple_default_def (curr_cfun, parm_decl) != arg)
 470                     ipa_method_modify_set (mt, i, true);
 471             }
 472           if (!IS_VALID_TREE_MAP_INDEX (i) || ipa_method_is_modified (mt, i))
 473             ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
 474           else
 475             {
 476               ipa_callsite_param_set_type (cs, arg_num, FORMAL_IPATYPE);
 477               ipa_callsite_param_set_info_type_formal (cs, arg_num, i);
 478             }
 479         }
 480       /* If a constant value was passed as argument,
 481          we store CONST_IPATYPE and its value as the jump function
 482          of this argument.  */
 483       else if (TREE_CODE (arg) == INTEGER_CST
 484                || TREE_CODE (arg) == REAL_CST
 485                || TREE_CODE (arg) == FIXED_CST)
 486         {
 487           ipa_callsite_param_set_type (cs, arg_num, CONST_IPATYPE);
 488           ipa_callsite_param_set_info_type (cs, arg_num, arg);
 489         }
 490       /* This is for the case of Fortran. If the address of a const_decl
 491          was passed as argument then we store
 492          CONST_IPATYPE_REF/CONST_IPATYPE_REF and the constant
 493          value as the jump function corresponding to this argument.  */
 494       else if (TREE_CODE (arg) == ADDR_EXPR
 495                && TREE_CODE (TREE_OPERAND (arg, 0)) == CONST_DECL)
 496         {
 497           cst_decl = TREE_OPERAND (arg, 0);
 498           if (TREE_CODE (DECL_INITIAL (cst_decl)) == INTEGER_CST
 499               || TREE_CODE (DECL_INITIAL (cst_decl)) == REAL_CST
 500               || TREE_CODE (DECL_INITIAL (cst_decl)) == FIXED_CST)
 501             {
 502               ipa_callsite_param_set_type (cs, arg_num,
 503                                            CONST_IPATYPE_REF);
 504               ipa_callsite_param_set_info_type (cs, arg_num,
 505                                                 DECL_INITIAL (cst_decl));
 506             }
 507         }
 508       else
 509         ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
 510       arg_num++;
 511     }
 512 }
 513
 514 /* Return type of jump function JF.  */
 515 enum jump_func_type
 516 get_type (struct ipa_jump_func *jf)
 517 {
 518   return jf->type;
 519 }
 520
 521 /* Return info type of jump function JF.  */
 522 union parameter_info *
 523 ipa_jf_get_info_type (struct ipa_jump_func *jf)
 524 {
 525   return &(jf->info_type);
 526 }
 527
 528 /* Allocate and initialize ipa_node structure.
 529    cgraph_node NODE points to the new allocated ipa_node.  */
 530 void
 531 ipa_node_create (struct cgraph_node *node)
 532 {
 533   node->aux = xcalloc (1, sizeof (struct ipa_node));
 534 }
 535
 536 /* Allocate and initialize ipa_node structure for all
 537    nodes in callgraph.  */
 538 void
 539 ipa_nodes_create (void)
 540 {
 541   struct cgraph_node *node;
 542
 543   for (node = cgraph_nodes; node; node = node->next)
 544     ipa_node_create (node);
 545 }
 546
 547 /* Allocate and initialize ipa_edge structure.  */
 548 void
 549 ipa_edges_create (void)
 550 {
 551   struct cgraph_node *node;
 552   struct cgraph_edge *cs;
 553
 554   for (node = cgraph_nodes; node; node = node->next)
 555     for (cs = node->callees; cs; cs = cs->next_callee)
 556       cs->aux = xcalloc (1, sizeof (struct ipa_edge));
 557 }
 558
 559 /* Free ipa_node structure.  */
 560 void
 561 ipa_nodes_free (void)
 562 {
 563   struct cgraph_node *node;
 564
 565   for (node = cgraph_nodes; node; node = node->next)
 566     {
 567       free (node->aux);
 568       node->aux = NULL;
 569     }
 570 }
 571
 572 /* Free ipa_edge structure.  */
 573 void
 574 ipa_edges_free (void)
 575 {
 576   struct cgraph_node *node;
 577   struct cgraph_edge *cs;
 578
 579   for (node = cgraph_nodes; node; node = node->next)
 580     for (cs = node->callees; cs; cs = cs->next_callee)
 581       {
 582         free (cs->aux);
 583         cs->aux = NULL;
 584       }
 585 }
 586
 587 /* Free ipa data structures of ipa_node and ipa_edge.  */
 588 void
 589 ipa_free (void)
 590 {
 591   struct cgraph_node *node;
 592   struct cgraph_edge *cs;
 593
 594   for (node = cgraph_nodes; node; node = node->next)
 595     {
 596       if (node->aux == NULL)
 597         continue;
 598       if (IPA_NODE_REF (node)->ipcp_cval)
 599         free (IPA_NODE_REF (node)->ipcp_cval);
 600       if (IPA_NODE_REF (node)->ipa_param_tree)
 601         free (IPA_NODE_REF (node)->ipa_param_tree);
 602       if (IPA_NODE_REF (node)->ipa_mod)
 603         free (IPA_NODE_REF (node)->ipa_mod);
 604       for (cs = node->callees; cs; cs = cs->next_callee)
 605         {
 606           if (cs->aux)
 607             if (IPA_EDGE_REF (cs)->ipa_param_map)
 608               free (IPA_EDGE_REF (cs)->ipa_param_map);
 609         }
 610     }
 611 }
 612
 613 /* Print ipa_tree_map data structures of all methods in the
 614    callgraph to F.  */
 615 void
 616 ipa_method_tree_print (FILE * f)
 617 {
 618   int i, count;
 619   tree temp;
 620   struct cgraph_node *node;
 621
 622   fprintf (f, "\nPARAM TREE MAP PRINT\n");
 623   for (node = cgraph_nodes; node; node = node->next)
 624     {
 625       fprintf (f, "method  %s Trees :: \n", cgraph_node_name (node));
 626       count = ipa_method_formal_count (node);
 627       for (i = 0; i < count; i++)
 628         {
 629           temp = ipa_method_get_tree (node, i);
 630           if (TREE_CODE (temp) == PARM_DECL)
 631             fprintf (f, "  param [%d] : %s\n", i,
 632                      (*lang_hooks.decl_printable_name) (temp, 2));
 633         }
 634
 635     }
 636 }
 637
 638 /* Print ipa_modify data structures of all methods in the
 639    callgraph to F.  */
 640 void
 641 ipa_method_modify_print (FILE * f)
 642 {
 643   int i, count;
 644   bool temp;
 645   struct cgraph_node *node;
 646
 647   fprintf (f, "\nMODIFY PRINT\n");
 648   for (node = cgraph_nodes; node; node = node->next)
 649     {
 650       fprintf (f, "method  %s :: \n", cgraph_node_name (node));
 651       count = ipa_method_formal_count (node);
 652       for (i = 0; i < count; i++)
 653         {
 654           temp = ipa_method_is_modified (node, i);
 655           if (temp)
 656             fprintf (f, " param [%d] true \n", i);
 657           else
 658             fprintf (f, " param [%d] false \n", i);
 659         }
 660     }
 661 }