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   int arg_num;
 423
 424   call_tree = get_call_expr_in (ipa_callsite_tree (cs));
 425   gcc_assert (TREE_CODE (call_tree) == CALL_EXPR);
 426   arg_num = call_expr_nargs (call_tree);
 427   ipa_callsite_param_count_set (cs, arg_num);
 428 }
 429
 430 /* Compute jump function for all arguments of callsite CS
 431    and insert the information in the ipa_param_map array
 432    in the ipa_edge corresponding to this callsite. (Explanation
 433    on jump functions is in ipa-prop.h).  */
 434 void
 435 ipa_callsite_compute_param (struct cgraph_edge *cs)
 436 {
 437   tree call_tree;
 438   tree arg, cst_decl;
 439   int arg_num;
 440   int i;
 441   struct cgraph_node *mt;
 442   tree parm_decl;
 443   struct function *curr_cfun;
 444   call_expr_arg_iterator iter;
 445
 446   if (ipa_callsite_param_count (cs) == 0)
 447     return;
 448   ipa_callsite_param_map_create (cs);
 449   call_tree = get_call_expr_in (ipa_callsite_tree (cs));
 450   gcc_assert (TREE_CODE (call_tree) == CALL_EXPR);
 451   arg_num = 0;
 452
 453   FOR_EACH_CALL_EXPR_ARG (arg, iter, call_tree)
 454     {
 455       /* If the formal parameter was passed as argument, we store
 456          FORMAL_IPATYPE and its index in the caller as the jump function
 457          of this argument.  */
 458       if ((TREE_CODE (arg) == SSA_NAME
 459            && TREE_CODE (SSA_NAME_VAR (arg)) == PARM_DECL)
 460           || TREE_CODE (arg) == PARM_DECL)
 461         {
 462           mt = ipa_callsite_caller (cs);
 463           parm_decl = TREE_CODE (arg) == PARM_DECL ? arg : SSA_NAME_VAR (arg);
 464
 465           i = ipa_method_tree_map (mt, parm_decl);
 466           if (TREE_CODE (arg) == SSA_NAME && IS_VALID_TREE_MAP_INDEX (i))
 467             {
 468               curr_cfun = DECL_STRUCT_FUNCTION (mt->decl);
 469               if (!gimple_default_def (curr_cfun, parm_decl)
 470                   || gimple_default_def (curr_cfun, parm_decl) != arg)
 471                     ipa_method_modify_set (mt, i, true);
 472             }
 473           if (!IS_VALID_TREE_MAP_INDEX (i) || ipa_method_is_modified (mt, i))
 474             ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
 475           else
 476             {
 477               ipa_callsite_param_set_type (cs, arg_num, FORMAL_IPATYPE);
 478               ipa_callsite_param_set_info_type_formal (cs, arg_num, i);
 479             }
 480         }
 481       /* If a constant value was passed as argument,
 482          we store CONST_IPATYPE and its value as the jump function
 483          of this argument.  */
 484       else if (TREE_CODE (arg) == INTEGER_CST
 485                || TREE_CODE (arg) == REAL_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             {
 501               ipa_callsite_param_set_type (cs, arg_num,
 502                                            CONST_IPATYPE_REF);
 503               ipa_callsite_param_set_info_type (cs, arg_num,
 504                                                 DECL_INITIAL (cst_decl));
 505             }
 506         }
 507       else
 508         ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
 509       arg_num++;
 510     }
 511 }
 512
 513 /* Return type of jump function JF.  */
 514 enum jump_func_type
 515 get_type (struct ipa_jump_func *jf)
 516 {
 517   return jf->type;
 518 }
 519
 520 /* Return info type of jump function JF.  */
 521 union parameter_info *
 522 ipa_jf_get_info_type (struct ipa_jump_func *jf)
 523 {
 524   return &(jf->info_type);
 525 }
 526
 527 /* Allocate and initialize ipa_node structure.
 528    cgraph_node NODE points to the new allocated ipa_node.  */
 529 void
 530 ipa_node_create (struct cgraph_node *node)
 531 {
 532   node->aux = xcalloc (1, sizeof (struct ipa_node));
 533 }
 534
 535 /* Allocate and initialize ipa_node structure for all
 536    nodes in callgraph.  */
 537 void
 538 ipa_nodes_create (void)
 539 {
 540   struct cgraph_node *node;
 541
 542   for (node = cgraph_nodes; node; node = node->next)
 543     ipa_node_create (node);
 544 }
 545
 546 /* Allocate and initialize ipa_edge structure.  */
 547 void
 548 ipa_edges_create (void)
 549 {
 550   struct cgraph_node *node;
 551   struct cgraph_edge *cs;
 552
 553   for (node = cgraph_nodes; node; node = node->next)
 554     for (cs = node->callees; cs; cs = cs->next_callee)
 555       cs->aux = xcalloc (1, sizeof (struct ipa_edge));
 556 }
 557
 558 /* Free ipa_node structure.  */
 559 void
 560 ipa_nodes_free (void)
 561 {
 562   struct cgraph_node *node;
 563
 564   for (node = cgraph_nodes; node; node = node->next)
 565     {
 566       free (node->aux);
 567       node->aux = NULL;
 568     }
 569 }
 570
 571 /* Free ipa_edge structure.  */
 572 void
 573 ipa_edges_free (void)
 574 {
 575   struct cgraph_node *node;
 576   struct cgraph_edge *cs;
 577
 578   for (node = cgraph_nodes; node; node = node->next)
 579     for (cs = node->callees; cs; cs = cs->next_callee)
 580       {
 581         free (cs->aux);
 582         cs->aux = NULL;
 583       }
 584 }
 585
 586 /* Free ipa data structures of ipa_node and ipa_edge.  */
 587 void
 588 ipa_free (void)
 589 {
 590   struct cgraph_node *node;
 591   struct cgraph_edge *cs;
 592
 593   for (node = cgraph_nodes; node; node = node->next)
 594     {
 595       if (node->aux == NULL)
 596         continue;
 597       if (IPA_NODE_REF (node)->ipcp_cval)
 598         free (IPA_NODE_REF (node)->ipcp_cval);
 599       if (IPA_NODE_REF (node)->ipa_param_tree)
 600         free (IPA_NODE_REF (node)->ipa_param_tree);
 601       if (IPA_NODE_REF (node)->ipa_mod)
 602         free (IPA_NODE_REF (node)->ipa_mod);
 603       for (cs = node->callees; cs; cs = cs->next_callee)
 604         {
 605           if (cs->aux)
 606             if (IPA_EDGE_REF (cs)->ipa_param_map)
 607               free (IPA_EDGE_REF (cs)->ipa_param_map);
 608         }
 609     }
 610 }
 611
 612 /* Print ipa_tree_map data structures of all methods in the
 613    callgraph to F.  */
 614 void
 615 ipa_method_tree_print (FILE * f)
 616 {
 617   int i, count;
 618   tree temp;
 619   struct cgraph_node *node;
 620
 621   fprintf (f, "\nPARAM TREE MAP PRINT\n");
 622   for (node = cgraph_nodes; node; node = node->next)
 623     {
 624       fprintf (f, "method  %s Trees :: \n", cgraph_node_name (node));
 625       count = ipa_method_formal_count (node);
 626       for (i = 0; i < count; i++)
 627         {
 628           temp = ipa_method_get_tree (node, i);
 629           if (TREE_CODE (temp) == PARM_DECL)
 630             fprintf (f, "  param [%d] : %s\n", i,
 631                      (*lang_hooks.decl_printable_name) (temp, 2));
 632         }
 633
 634     }
 635 }
 636
 637 /* Print ipa_modify data structures of all methods in the
 638    callgraph to F.  */
 639 void
 640 ipa_method_modify_print (FILE * f)
 641 {
 642   int i, count;
 643   bool temp;
 644   struct cgraph_node *node;
 645
 646   fprintf (f, "\nMODIFY PRINT\n");
 647   for (node = cgraph_nodes; node; node = node->next)
 648     {
 649       fprintf (f, "method  %s :: \n", cgraph_node_name (node));
 650       count = ipa_method_formal_count (node);
 651       for (i = 0; i < count; i++)
 652         {
 653           temp = ipa_method_is_modified (node, i);
 654           if (temp)
 655             fprintf (f, " param [%d] true \n", i);
 656           else
 657             fprintf (f, " param [%d] false \n", i);
 658         }
 659     }
 660 }