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         {
 486           ipa_callsite_param_set_type (cs, arg_num, CONST_IPATYPE);
 487           ipa_callsite_param_set_info_type (cs, arg_num, arg);
 488         }
 489       /* This is for the case of Fortran. If the address of a const_decl
 490          was passed as argument then we store
 491          CONST_IPATYPE_REF/CONST_IPATYPE_REF and the constant
 492          value as the jump function corresponding to this argument.  */
 493       else if (TREE_CODE (arg) == ADDR_EXPR
 494                && TREE_CODE (TREE_OPERAND (arg, 0)) == CONST_DECL)
 495         {
 496           cst_decl = TREE_OPERAND (arg, 0);
 497           if (TREE_CODE (DECL_INITIAL (cst_decl)) == INTEGER_CST
 498               || TREE_CODE (DECL_INITIAL (cst_decl)) == REAL_CST)
 499             {
 500               ipa_callsite_param_set_type (cs, arg_num,
 501                                            CONST_IPATYPE_REF);
 502               ipa_callsite_param_set_info_type (cs, arg_num,
 503                                                 DECL_INITIAL (cst_decl));
 504             }
 505         }
 506       else
 507         ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
 508       arg_num++;
 509     }
 510 }
 511
 512 /* Return type of jump function JF.  */
 513 enum jump_func_type
 514 get_type (struct ipa_jump_func *jf)
 515 {
 516   return jf->type;
 517 }
 518
 519 /* Return info type of jump function JF.  */
 520 union parameter_info *
 521 ipa_jf_get_info_type (struct ipa_jump_func *jf)
 522 {
 523   return &(jf->info_type);
 524 }
 525
 526 /* Allocate and initialize ipa_node structure.
 527    cgraph_node NODE points to the new allocated ipa_node.  */
 528 void
 529 ipa_node_create (struct cgraph_node *node)
 530 {
 531   node->aux = xcalloc (1, sizeof (struct ipa_node));
 532 }
 533
 534 /* Allocate and initialize ipa_node structure for all
 535    nodes in callgraph.  */
 536 void
 537 ipa_nodes_create (void)
 538 {
 539   struct cgraph_node *node;
 540
 541   for (node = cgraph_nodes; node; node = node->next)
 542     ipa_node_create (node);
 543 }
 544
 545 /* Allocate and initialize ipa_edge structure.  */
 546 void
 547 ipa_edges_create (void)
 548 {
 549   struct cgraph_node *node;
 550   struct cgraph_edge *cs;
 551
 552   for (node = cgraph_nodes; node; node = node->next)
 553     for (cs = node->callees; cs; cs = cs->next_callee)
 554       cs->aux = xcalloc (1, sizeof (struct ipa_edge));
 555 }
 556
 557 /* Free ipa_node structure.  */
 558 void
 559 ipa_nodes_free (void)
 560 {
 561   struct cgraph_node *node;
 562
 563   for (node = cgraph_nodes; node; node = node->next)
 564     {
 565       free (node->aux);
 566       node->aux = NULL;
 567     }
 568 }
 569
 570 /* Free ipa_edge structure.  */
 571 void
 572 ipa_edges_free (void)
 573 {
 574   struct cgraph_node *node;
 575   struct cgraph_edge *cs;
 576
 577   for (node = cgraph_nodes; node; node = node->next)
 578     for (cs = node->callees; cs; cs = cs->next_callee)
 579       {
 580         free (cs->aux);
 581         cs->aux = NULL;
 582       }
 583 }
 584
 585 /* Free ipa data structures of ipa_node and ipa_edge.  */
 586 void
 587 ipa_free (void)
 588 {
 589   struct cgraph_node *node;
 590   struct cgraph_edge *cs;
 591
 592   for (node = cgraph_nodes; node; node = node->next)
 593     {
 594       if (node->aux == NULL)
 595         continue;
 596       if (IPA_NODE_REF (node)->ipcp_cval)
 597         free (IPA_NODE_REF (node)->ipcp_cval);
 598       if (IPA_NODE_REF (node)->ipa_param_tree)
 599         free (IPA_NODE_REF (node)->ipa_param_tree);
 600       if (IPA_NODE_REF (node)->ipa_mod)
 601         free (IPA_NODE_REF (node)->ipa_mod);
 602       for (cs = node->callees; cs; cs = cs->next_callee)
 603         {
 604           if (cs->aux)
 605             if (IPA_EDGE_REF (cs)->ipa_param_map)
 606               free (IPA_EDGE_REF (cs)->ipa_param_map);
 607         }
 608     }
 609 }
 610
 611 /* Print ipa_tree_map data structures of all methods in the
 612    callgraph to F.  */
 613 void
 614 ipa_method_tree_print (FILE * f)
 615 {
 616   int i, count;
 617   tree temp;
 618   struct cgraph_node *node;
 619
 620   fprintf (f, "\nPARAM TREE MAP PRINT\n");
 621   for (node = cgraph_nodes; node; node = node->next)
 622     {
 623       fprintf (f, "method  %s Trees :: \n", cgraph_node_name (node));
 624       count = ipa_method_formal_count (node);
 625       for (i = 0; i < count; i++)
 626         {
 627           temp = ipa_method_get_tree (node, i);
 628           if (TREE_CODE (temp) == PARM_DECL)
 629             fprintf (f, "  param [%d] : %s\n", i,
 630                      (*lang_hooks.decl_printable_name) (temp, 2));
 631         }
 632
 633     }
 634 }
 635
 636 /* Print ipa_modify data structures of all methods in the
 637    callgraph to F.  */
 638 void
 639 ipa_method_modify_print (FILE * f)
 640 {
 641   int i, count;
 642   bool temp;
 643   struct cgraph_node *node;
 644
 645   fprintf (f, "\nMODIFY PRINT\n");
 646   for (node = cgraph_nodes; node; node = node->next)
 647     {
 648       fprintf (f, "method  %s :: \n", cgraph_node_name (node));
 649       count = ipa_method_formal_count (node);
 650       for (i = 0; i < count; i++)
 651         {
 652           temp = ipa_method_is_modified (node, i);
 653           if (temp)
 654             fprintf (f, " param [%d] true \n", i);
 655           else
 656             fprintf (f, " param [%d] false \n", i);
 657         }
 658     }
 659 }