gcc/ipa-prop.c

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