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
 247   switch (TREE_CODE (stmt))
 248     {
 249     case MODIFY_EXPR:
 250       if (TREE_CODE (TREE_OPERAND (stmt, 0)) == PARM_DECL)
 251         {
 252           i = ipa_method_tree_map (mt, TREE_OPERAND (stmt, 0));
 253           if (i >= 0)
 254             ipa_method_modify_set (mt, i, true);
 255         }
 256       break;
 257     case ASM_EXPR:
 258       /* Asm code could modify any of the parameters.  */
 259       for (j = 0; j < ipa_method_formal_count (mt); j++)
 260         ipa_method_modify_set (mt, j, true);
 261       break;
 262     default:
 263       break;
 264     }
 265 }
 266
 267 /* Initialize ipa_mod array of MT.  */
 268 static void
 269 ipa_method_modify_init (struct cgraph_node *mt)
 270 {
 271   int i, count;
 272
 273   ipa_method_modify_create (mt);
 274   count = ipa_method_formal_count (mt);
 275   for (i = 0; i < count; i++)
 276     ipa_method_modify_set (mt, i, false);
 277 }
 278
 279 /* The modify computation driver for MT. Compute which formal arguments
 280    of method MT are locally modified.  Formals may be modified in MT
 281    if their address is taken, or if
 282    they appear on the left hand side of an assignment.  */
 283 void
 284 ipa_method_compute_modify (struct cgraph_node *mt)
 285 {
 286   tree decl;
 287   tree body;
 288   int j, count;
 289   basic_block bb;
 290   struct function *func;
 291   block_stmt_iterator bsi;
 292   tree stmt, parm_tree;
 293
 294   ipa_method_modify_init (mt);
 295   decl = mt->decl;
 296   count = ipa_method_formal_count (mt);
 297   /* ??? Handle pending sizes case. Set all parameters
 298      of the method to be modified.  */
 299   if (DECL_UNINLINABLE (decl))
 300     {
 301       for (j = 0; j < count; j++)
 302         ipa_method_modify_set (mt, j, true);
 303       return;
 304     }
 305   /* Formals whose address is taken are considered modified.  */
 306   for (j = 0; j < count; j++)
 307     {
 308       parm_tree = ipa_method_get_tree (mt, j);
 309       if (TREE_ADDRESSABLE (parm_tree))
 310         ipa_method_modify_set (mt, j, true);
 311     }
 312   body = DECL_SAVED_TREE (decl);
 313   if (body != NULL)
 314     {
 315       func = DECL_STRUCT_FUNCTION (decl);
 316       FOR_EACH_BB_FN (bb, func)
 317       {
 318         for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 319           {
 320             stmt = bsi_stmt (bsi);
 321             ipa_method_modify_stmt (mt, stmt);
 322           }
 323       }
 324     }
 325 }
 326
 327
 328 /* ipa_callsite interface.  */
 329
 330 /* Return number of arguments in callsite CS.  */
 331 int
 332 ipa_callsite_param_count (struct cgraph_edge *cs)
 333 {
 334   return IPA_EDGE_REF (cs)->ipa_param_num;
 335 }
 336
 337 /* Set number of arguments in callsite CS to I.  */
 338 void
 339 ipa_callsite_param_count_set (struct cgraph_edge *cs, int i)
 340 {
 341   IPA_EDGE_REF (cs)->ipa_param_num = i;
 342 }
 343
 344 /* Return the jump function (ipa_jump_func struct) for argument I of
 345    callsite CS.  */
 346 struct ipa_jump_func *
 347 ipa_callsite_param (struct cgraph_edge *cs, int i)
 348 {
 349   return &(IPA_EDGE_REF (cs)->ipa_param_map[i]);
 350 }
 351
 352 /* return the callee (cgraph_node) of callsite CS.  */
 353 struct cgraph_node *
 354 ipa_callsite_callee (struct cgraph_edge *cs)
 355 {
 356   return cs->callee;
 357 }
 358
 359 /* Set field 'type' of jump function (ipa_jump_func struct) of argument I
 360    in callsite CS.  */
 361 static inline void
 362 ipa_callsite_param_set_type (struct cgraph_edge *cs, int i,
 363                              enum jump_func_type type1)
 364 {
 365   IPA_EDGE_REF (cs)->ipa_param_map[i].type = type1;
 366 }
 367
 368 /* Set FORMAL as 'info_type' field of jump function (ipa_jump_func struct)
 369    of argument I of callsite CS.  */
 370 static inline void
 371 ipa_callsite_param_set_info_type_formal (struct cgraph_edge *cs, int i,
 372                                          unsigned int formal)
 373 {
 374   ipa_callsite_param (cs, i)->info_type.formal_id = formal;
 375 }
 376
 377 /* Set int-valued INFO_TYPE1 as 'info_type' field of
 378    jump function (ipa_jump_func struct) of argument I of callsite CS.  */
 379 static inline void
 380 ipa_callsite_param_set_info_type (struct cgraph_edge *cs, int i, tree info_type1)
 381 {
 382   ipa_callsite_param (cs, i)->info_type.value = info_type1;
 383 }
 384
 385 /* Allocate space for callsite CS.  */
 386 static inline void
 387 ipa_callsite_param_map_create (struct cgraph_edge *cs)
 388 {
 389   IPA_EDGE_REF (cs)->ipa_param_map =
 390     XCNEWVEC (struct ipa_jump_func, ipa_callsite_param_count (cs));
 391 }
 392
 393 /* Return the call expr tree related to callsite CS.  */
 394 static inline tree
 395 ipa_callsite_tree (struct cgraph_edge *cs)
 396 {
 397   return cs->call_stmt;
 398 }
 399
 400 /* Return the caller (cgraph_node) of CS.  */
 401 static inline struct cgraph_node *
 402 ipa_callsite_caller (struct cgraph_edge *cs)
 403 {
 404   return cs->caller;
 405 }
 406
 407 /* Count number of arguments callsite CS has and store it in
 408    ipa_edge structure corresponding to this callsite.  */
 409 void
 410 ipa_callsite_compute_count (struct cgraph_edge *cs)
 411 {
 412   tree call_tree;
 413   tree arg;
 414   int arg_num;
 415
 416   call_tree = get_call_expr_in (ipa_callsite_tree (cs));
 417   gcc_assert (TREE_CODE (call_tree) == CALL_EXPR);
 418   arg = TREE_OPERAND (call_tree, 1);
 419   arg_num = 0;
 420   for (; arg != NULL_TREE; arg = TREE_CHAIN (arg))
 421     arg_num++;
 422   ipa_callsite_param_count_set (cs, arg_num);
 423 }
 424
 425 /* Compute jump function for all arguments of callsite CS
 426    and insert the information in the ipa_param_map array
 427    in the ipa_edge corresponding to this callsite. (Explanation
 428    on jump functions is in ipa-prop.h).  */
 429 void
 430 ipa_callsite_compute_param (struct cgraph_edge *cs)
 431 {
 432   tree call_tree;
 433   tree arg, cst_decl;
 434   int arg_num;
 435   int i;
 436   struct cgraph_node *mt;
 437
 438   if (ipa_callsite_param_count (cs) == 0)
 439     return;
 440   ipa_callsite_param_map_create (cs);
 441   call_tree = get_call_expr_in (ipa_callsite_tree (cs));
 442   gcc_assert (TREE_CODE (call_tree) == CALL_EXPR);
 443   arg = TREE_OPERAND (call_tree, 1);
 444   arg_num = 0;
 445
 446   for (; arg != NULL_TREE; arg = TREE_CHAIN (arg))
 447     {
 448       /* If the formal parameter was passed as argument, we store
 449          FORMAL_IPATYPE and its index in the caller as the jump function
 450          of this argument.  */
 451       if (TREE_CODE (TREE_VALUE (arg)) == PARM_DECL)
 452         {
 453           mt = ipa_callsite_caller (cs);
 454           i = ipa_method_tree_map (mt, TREE_VALUE (arg));
 455           if (i < 0 || ipa_method_is_modified (mt, i))
 456             ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
 457           else
 458             {
 459               ipa_callsite_param_set_type (cs, arg_num, FORMAL_IPATYPE);
 460               ipa_callsite_param_set_info_type_formal (cs, arg_num, i);
 461             }
 462         }
 463       /* If a constant value was passed as argument,
 464          we store CONST_IPATYPE and its value as the jump function
 465          of this argument.  */
 466       else if (TREE_CODE (TREE_VALUE (arg)) == INTEGER_CST
 467                || TREE_CODE (TREE_VALUE (arg)) == REAL_CST)
 468         {
 469           ipa_callsite_param_set_type (cs, arg_num, CONST_IPATYPE);
 470           ipa_callsite_param_set_info_type (cs, arg_num,
 471                                             TREE_VALUE (arg));
 472         }
 473       /* This is for the case of Fortran. If the address of a const_decl
 474          was passed as argument then we store
 475          CONST_IPATYPE_REF/CONST_IPATYPE_REF and the constant
 476          value as the jump function corresponding to this argument.  */
 477       else if (TREE_CODE (TREE_VALUE (arg)) == ADDR_EXPR
 478                && TREE_CODE (TREE_OPERAND (TREE_VALUE (arg), 0)) ==
 479                CONST_DECL)
 480         {
 481           cst_decl = TREE_OPERAND (TREE_VALUE (arg), 0);
 482           if (TREE_CODE (DECL_INITIAL (cst_decl)) == INTEGER_CST
 483               || TREE_CODE (DECL_INITIAL (cst_decl)) == REAL_CST)
 484             {
 485               ipa_callsite_param_set_type (cs, arg_num,
 486                                            CONST_IPATYPE_REF);
 487               ipa_callsite_param_set_info_type (cs, arg_num,
 488                                                 DECL_INITIAL (cst_decl));
 489             }
 490         }
 491       else
 492         ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
 493       arg_num++;
 494     }
 495 }
 496
 497 /* Return type of jump function JF.  */
 498 enum jump_func_type
 499 get_type (struct ipa_jump_func *jf)
 500 {
 501   return jf->type;
 502 }
 503
 504 /* Return info type of jump function JF.  */
 505 union parameter_info *
 506 ipa_jf_get_info_type (struct ipa_jump_func *jf)
 507 {
 508   return &(jf->info_type);
 509 }
 510
 511 /* Allocate and initialize ipa_node structure.
 512    cgraph_node NODE points to the new allocated ipa_node.  */
 513 void
 514 ipa_node_create (struct cgraph_node *node)
 515 {
 516   node->aux = xcalloc (1, sizeof (struct ipa_node));
 517 }
 518
 519 /* Allocate and initialize ipa_node structure for all
 520    nodes in callgraph.  */
 521 void
 522 ipa_nodes_create (void)
 523 {
 524   struct cgraph_node *node;
 525
 526   for (node = cgraph_nodes; node; node = node->next)
 527     ipa_node_create (node);
 528 }
 529
 530 /* Allocate and initialize ipa_edge structure.  */
 531 void
 532 ipa_edges_create (void)
 533 {
 534   struct cgraph_node *node;
 535   struct cgraph_edge *cs;
 536
 537   for (node = cgraph_nodes; node; node = node->next)
 538     for (cs = node->callees; cs; cs = cs->next_callee)
 539       cs->aux = xcalloc (1, sizeof (struct ipa_edge));
 540 }
 541
 542 /* Free ipa_node structure.  */
 543 void
 544 ipa_nodes_free (void)
 545 {
 546   struct cgraph_node *node;
 547
 548   for (node = cgraph_nodes; node; node = node->next)
 549     {
 550       free (node->aux);
 551       node->aux = NULL;
 552     }
 553 }
 554
 555 /* Free ipa_edge structure.  */
 556 void
 557 ipa_edges_free (void)
 558 {
 559   struct cgraph_node *node;
 560   struct cgraph_edge *cs;
 561
 562   for (node = cgraph_nodes; node; node = node->next)
 563     for (cs = node->callees; cs; cs = cs->next_callee)
 564       {
 565         free (cs->aux);
 566         cs->aux = NULL;
 567       }
 568 }
 569
 570 /* Free ipa data structures of ipa_node and ipa_edge.  */
 571 void
 572 ipa_free (void)
 573 {
 574   struct cgraph_node *node;
 575   struct cgraph_edge *cs;
 576
 577   for (node = cgraph_nodes; node; node = node->next)
 578     {
 579       if (node->aux == NULL)
 580         continue;
 581       if (IPA_NODE_REF (node)->ipcp_cval)
 582         free (IPA_NODE_REF (node)->ipcp_cval);
 583       if (IPA_NODE_REF (node)->ipa_param_tree)
 584         free (IPA_NODE_REF (node)->ipa_param_tree);
 585       if (IPA_NODE_REF (node)->ipa_mod)
 586         free (IPA_NODE_REF (node)->ipa_mod);
 587       for (cs = node->callees; cs; cs = cs->next_callee)
 588         {
 589           if (cs->aux)
 590             if (IPA_EDGE_REF (cs)->ipa_param_map)
 591               free (IPA_EDGE_REF (cs)->ipa_param_map);
 592         }
 593     }
 594 }
 595
 596 /* Print ipa_tree_map data structures of all methods in the
 597    callgraph to F.  */
 598 void
 599 ipa_method_tree_print (FILE * f)
 600 {
 601   int i, count;
 602   tree temp;
 603   struct cgraph_node *node;
 604
 605   fprintf (f, "\nPARAM TREE MAP PRINT\n");
 606   for (node = cgraph_nodes; node; node = node->next)
 607     {
 608       fprintf (f, "method  %s Trees :: \n", cgraph_node_name (node));
 609       count = ipa_method_formal_count (node);
 610       for (i = 0; i < count; i++)
 611         {
 612           temp = ipa_method_get_tree (node, i);
 613           if (TREE_CODE (temp) == PARM_DECL)
 614             fprintf (f, "  param [%d] : %s\n", i,
 615                      (*lang_hooks.decl_printable_name) (temp, 2));
 616         }
 617
 618     }
 619 }
 620
 621 /* Print ipa_modify data structures of all methods in the
 622    callgraph to F.  */
 623 void
 624 ipa_method_modify_print (FILE * f)
 625 {
 626   int i, count;
 627   bool temp;
 628   struct cgraph_node *node;
 629
 630   fprintf (f, "\nMODIFY PRINT\n");
 631   for (node = cgraph_nodes; node; node = node->next)
 632     {
 633       fprintf (f, "method  %s :: \n", cgraph_node_name (node));
 634       count = ipa_method_formal_count (node);
 635       for (i = 0; i < count; i++)
 636         {
 637           temp = ipa_method_is_modified (node, i);
 638           if (temp)
 639             fprintf (f, " param [%d] true \n", i);
 640           else
 641             fprintf (f, " param [%d] false \n", i);
 642         }
 643     }
 644 }