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