1/* Generic routines for manipulating PHIs 2 Copyright (C) 2003-2015 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify 7it under the terms of the GNU General Public License as published by 8the Free Software Foundation; either version 3, or (at your option) 9any later version. 10 11GCC is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14GNU General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along 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 "tm.h" 24#include "hash-set.h" 25#include "machmode.h" 26#include "vec.h" 27#include "double-int.h" 28#include "input.h" 29#include "alias.h" 30#include "symtab.h" 31#include "wide-int.h" 32#include "inchash.h" 33#include "tree.h" 34#include "fold-const.h" 35#include "predict.h" 36#include "hard-reg-set.h" 37#include "input.h" 38#include "function.h" 39#include "basic-block.h" 40#include "tree-ssa-alias.h" 41#include "internal-fn.h" 42#include "gimple-expr.h" 43#include "is-a.h" 44#include "gimple.h" 45#include "gimple-iterator.h" 46#include "gimple-ssa.h" 47#include "tree-phinodes.h" 48#include "ssa-iterators.h" 49#include "stringpool.h" 50#include "tree-ssanames.h" 51#include "tree-ssa.h" 52#include "diagnostic-core.h" 53 54/* Rewriting a function into SSA form can create a huge number of PHIs 55 many of which may be thrown away shortly after their creation if jumps 56 were threaded through PHI nodes. 57 58 While our garbage collection mechanisms will handle this situation, it 59 is extremely wasteful to create nodes and throw them away, especially 60 when the nodes can be reused. 61 62 For PR 8361, we can significantly reduce the number of nodes allocated 63 and thus the total amount of memory allocated by managing PHIs a 64 little. This additionally helps reduce the amount of work done by the 65 garbage collector. Similar results have been seen on a wider variety 66 of tests (such as the compiler itself). 67 68 PHI nodes have different sizes, so we can't have a single list of all 69 the PHI nodes as it would be too expensive to walk down that list to 70 find a PHI of a suitable size. 71 72 Instead we have an array of lists of free PHI nodes. The array is 73 indexed by the number of PHI alternatives that PHI node can hold. 74 Except for the last array member, which holds all remaining PHI 75 nodes. 76 77 So to find a free PHI node, we compute its index into the free PHI 78 node array and see if there are any elements with an exact match. 79 If so, then we are done. Otherwise, we test the next larger size 80 up and continue until we are in the last array element. 81 82 We do not actually walk members of the last array element. While it 83 might allow us to pick up a few reusable PHI nodes, it could potentially 84 be very expensive if the program has released a bunch of large PHI nodes, 85 but keeps asking for even larger PHI nodes. Experiments have shown that 86 walking the elements of the last array entry would result in finding less 87 than .1% additional reusable PHI nodes. 88 89 Note that we can never have less than two PHI argument slots. Thus, 90 the -2 on all the calculations below. */ 91 92#define NUM_BUCKETS 10 93static GTY ((deletable (""))) vec<gimple, va_gc> *free_phinodes[NUM_BUCKETS - 2]; 94static unsigned long free_phinode_count; 95 96static int ideal_phi_node_len (int); 97 98unsigned int phi_nodes_reused; 99unsigned int phi_nodes_created; 100 101/* Dump some simple statistics regarding the re-use of PHI nodes. */ 102 103void 104phinodes_print_statistics (void) 105{ 106 fprintf (stderr, "PHI nodes allocated: %u\n", phi_nodes_created); 107 fprintf (stderr, "PHI nodes reused: %u\n", phi_nodes_reused); 108} 109 110/* Allocate a PHI node with at least LEN arguments. If the free list 111 happens to contain a PHI node with LEN arguments or more, return 112 that one. */ 113 114static inline gphi * 115allocate_phi_node (size_t len) 116{ 117 gphi *phi; 118 size_t bucket = NUM_BUCKETS - 2; 119 size_t size = sizeof (struct gphi) 120 + (len - 1) * sizeof (struct phi_arg_d); 121 122 if (free_phinode_count) 123 for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++) 124 if (free_phinodes[bucket]) 125 break; 126 127 /* If our free list has an element, then use it. */ 128 if (bucket < NUM_BUCKETS - 2 129 && gimple_phi_capacity ((*free_phinodes[bucket])[0]) >= len) 130 { 131 free_phinode_count--; 132 phi = as_a <gphi *> (free_phinodes[bucket]->pop ()); 133 if (free_phinodes[bucket]->is_empty ()) 134 vec_free (free_phinodes[bucket]); 135 if (GATHER_STATISTICS) 136 phi_nodes_reused++; 137 } 138 else 139 { 140 phi = static_cast <gphi *> (ggc_internal_alloc (size)); 141 if (GATHER_STATISTICS) 142 { 143 enum gimple_alloc_kind kind = gimple_alloc_kind (GIMPLE_PHI); 144 phi_nodes_created++; 145 gimple_alloc_counts[(int) kind]++; 146 gimple_alloc_sizes[(int) kind] += size; 147 } 148 } 149 150 return phi; 151} 152 153/* Given LEN, the original number of requested PHI arguments, return 154 a new, "ideal" length for the PHI node. The "ideal" length rounds 155 the total size of the PHI node up to the next power of two bytes. 156 157 Rounding up will not result in wasting any memory since the size request 158 will be rounded up by the GC system anyway. [ Note this is not entirely 159 true since the original length might have fit on one of the special 160 GC pages. ] By rounding up, we may avoid the need to reallocate the 161 PHI node later if we increase the number of arguments for the PHI. */ 162 163static int 164ideal_phi_node_len (int len) 165{ 166 size_t size, new_size; 167 int log2, new_len; 168 169 /* We do not support allocations of less than two PHI argument slots. */ 170 if (len < 2) 171 len = 2; 172 173 /* Compute the number of bytes of the original request. */ 174 size = sizeof (struct gphi) 175 + (len - 1) * sizeof (struct phi_arg_d); 176 177 /* Round it up to the next power of two. */ 178 log2 = ceil_log2 (size); 179 new_size = 1 << log2; 180 181 /* Now compute and return the number of PHI argument slots given an 182 ideal size allocation. */ 183 new_len = len + (new_size - size) / sizeof (struct phi_arg_d); 184 return new_len; 185} 186 187/* Return a PHI node with LEN argument slots for variable VAR. */ 188 189static gphi * 190make_phi_node (tree var, int len) 191{ 192 gphi *phi; 193 int capacity, i; 194 195 capacity = ideal_phi_node_len (len); 196 197 phi = allocate_phi_node (capacity); 198 199 /* We need to clear the entire PHI node, including the argument 200 portion, because we represent a "missing PHI argument" by placing 201 NULL_TREE in PHI_ARG_DEF. */ 202 memset (phi, 0, (sizeof (struct gphi) 203 - sizeof (struct phi_arg_d) 204 + sizeof (struct phi_arg_d) * len)); 205 phi->code = GIMPLE_PHI; 206 gimple_init_singleton (phi); 207 phi->nargs = len; 208 phi->capacity = capacity; 209 if (!var) 210 ; 211 else if (TREE_CODE (var) == SSA_NAME) 212 gimple_phi_set_result (phi, var); 213 else 214 gimple_phi_set_result (phi, make_ssa_name (var, phi)); 215 216 for (i = 0; i < capacity; i++) 217 { 218 use_operand_p imm; 219 220 gimple_phi_arg_set_location (phi, i, UNKNOWN_LOCATION); 221 imm = gimple_phi_arg_imm_use_ptr (phi, i); 222 imm->use = gimple_phi_arg_def_ptr (phi, i); 223 imm->prev = NULL; 224 imm->next = NULL; 225 imm->loc.stmt = phi; 226 } 227 228 return phi; 229} 230 231/* We no longer need PHI, release it so that it may be reused. */ 232 233void 234release_phi_node (gimple phi) 235{ 236 size_t bucket; 237 size_t len = gimple_phi_capacity (phi); 238 size_t x; 239 240 for (x = 0; x < gimple_phi_num_args (phi); x++) 241 { 242 use_operand_p imm; 243 imm = gimple_phi_arg_imm_use_ptr (phi, x); 244 delink_imm_use (imm); 245 } 246 247 bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len; 248 bucket -= 2; 249 vec_safe_push (free_phinodes[bucket], phi); 250 free_phinode_count++; 251} 252 253 254/* Resize an existing PHI node. The only way is up. Return the 255 possibly relocated phi. */ 256 257static gphi * 258resize_phi_node (gphi *phi, size_t len) 259{ 260 size_t old_size, i; 261 gphi *new_phi; 262 263 gcc_assert (len > gimple_phi_capacity (phi)); 264 265 /* The garbage collector will not look at the PHI node beyond the 266 first PHI_NUM_ARGS elements. Therefore, all we have to copy is a 267 portion of the PHI node currently in use. */ 268 old_size = sizeof (struct gphi) 269 + (gimple_phi_num_args (phi) - 1) * sizeof (struct phi_arg_d); 270 271 new_phi = allocate_phi_node (len); 272 273 memcpy (new_phi, phi, old_size); 274 275 for (i = 0; i < gimple_phi_num_args (new_phi); i++) 276 { 277 use_operand_p imm, old_imm; 278 imm = gimple_phi_arg_imm_use_ptr (new_phi, i); 279 old_imm = gimple_phi_arg_imm_use_ptr (phi, i); 280 imm->use = gimple_phi_arg_def_ptr (new_phi, i); 281 relink_imm_use_stmt (imm, old_imm, new_phi); 282 } 283 284 new_phi->capacity = len; 285 286 for (i = gimple_phi_num_args (new_phi); i < len; i++) 287 { 288 use_operand_p imm; 289 290 gimple_phi_arg_set_location (new_phi, i, UNKNOWN_LOCATION); 291 imm = gimple_phi_arg_imm_use_ptr (new_phi, i); 292 imm->use = gimple_phi_arg_def_ptr (new_phi, i); 293 imm->prev = NULL; 294 imm->next = NULL; 295 imm->loc.stmt = new_phi; 296 } 297 298 return new_phi; 299} 300 301/* Reserve PHI arguments for a new edge to basic block BB. */ 302 303void 304reserve_phi_args_for_new_edge (basic_block bb) 305{ 306 size_t len = EDGE_COUNT (bb->preds); 307 size_t cap = ideal_phi_node_len (len + 4); 308 gphi_iterator gsi; 309 310 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 311 { 312 gphi *stmt = gsi.phi (); 313 314 if (len > gimple_phi_capacity (stmt)) 315 { 316 gphi *new_phi = resize_phi_node (stmt, cap); 317 318 /* The result of the PHI is defined by this PHI node. */ 319 SSA_NAME_DEF_STMT (gimple_phi_result (new_phi)) = new_phi; 320 gsi_set_stmt (&gsi, new_phi); 321 322 release_phi_node (stmt); 323 stmt = new_phi; 324 } 325 326 /* We represent a "missing PHI argument" by placing NULL_TREE in 327 the corresponding slot. If PHI arguments were added 328 immediately after an edge is created, this zeroing would not 329 be necessary, but unfortunately this is not the case. For 330 example, the loop optimizer duplicates several basic blocks, 331 redirects edges, and then fixes up PHI arguments later in 332 batch. */ 333 SET_PHI_ARG_DEF (stmt, len - 1, NULL_TREE); 334 gimple_phi_arg_set_location (stmt, len - 1, UNKNOWN_LOCATION); 335 336 stmt->nargs++; 337 } 338} 339 340/* Adds PHI to BB. */ 341 342void 343add_phi_node_to_bb (gphi *phi, basic_block bb) 344{ 345 gimple_seq seq = phi_nodes (bb); 346 /* Add the new PHI node to the list of PHI nodes for block BB. */ 347 if (seq == NULL) 348 set_phi_nodes (bb, gimple_seq_alloc_with_stmt (phi)); 349 else 350 { 351 gimple_seq_add_stmt (&seq, phi); 352 gcc_assert (seq == phi_nodes (bb)); 353 } 354 355 /* Associate BB to the PHI node. */ 356 gimple_set_bb (phi, bb); 357 358} 359 360/* Create a new PHI node for variable VAR at basic block BB. */ 361 362gphi * 363create_phi_node (tree var, basic_block bb) 364{ 365 gphi *phi = make_phi_node (var, EDGE_COUNT (bb->preds)); 366 367 add_phi_node_to_bb (phi, bb); 368 return phi; 369} 370 371 372/* Add a new argument to PHI node PHI. DEF is the incoming reaching 373 definition and E is the edge through which DEF reaches PHI. The new 374 argument is added at the end of the argument list. 375 If PHI has reached its maximum capacity, add a few slots. In this case, 376 PHI points to the reallocated phi node when we return. */ 377 378void 379add_phi_arg (gphi *phi, tree def, edge e, source_location locus) 380{ 381 basic_block bb = e->dest; 382 383 gcc_assert (bb == gimple_bb (phi)); 384 385 /* We resize PHI nodes upon edge creation. We should always have 386 enough room at this point. */ 387 gcc_assert (gimple_phi_num_args (phi) <= gimple_phi_capacity (phi)); 388 389 /* We resize PHI nodes upon edge creation. We should always have 390 enough room at this point. */ 391 gcc_assert (e->dest_idx < gimple_phi_num_args (phi)); 392 393 /* Copy propagation needs to know what object occur in abnormal 394 PHI nodes. This is a convenient place to record such information. */ 395 if (e->flags & EDGE_ABNORMAL) 396 { 397 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1; 398 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1; 399 } 400 401 SET_PHI_ARG_DEF (phi, e->dest_idx, def); 402 gimple_phi_arg_set_location (phi, e->dest_idx, locus); 403} 404 405 406/* Remove the Ith argument from PHI's argument list. This routine 407 implements removal by swapping the last alternative with the 408 alternative we want to delete and then shrinking the vector, which 409 is consistent with how we remove an edge from the edge vector. */ 410 411static void 412remove_phi_arg_num (gphi *phi, int i) 413{ 414 int num_elem = gimple_phi_num_args (phi); 415 416 gcc_assert (i < num_elem); 417 418 /* Delink the item which is being removed. */ 419 delink_imm_use (gimple_phi_arg_imm_use_ptr (phi, i)); 420 421 /* If it is not the last element, move the last element 422 to the element we want to delete, resetting all the links. */ 423 if (i != num_elem - 1) 424 { 425 use_operand_p old_p, new_p; 426 old_p = gimple_phi_arg_imm_use_ptr (phi, num_elem - 1); 427 new_p = gimple_phi_arg_imm_use_ptr (phi, i); 428 /* Set use on new node, and link into last element's place. */ 429 *(new_p->use) = *(old_p->use); 430 relink_imm_use (new_p, old_p); 431 /* Move the location as well. */ 432 gimple_phi_arg_set_location (phi, i, 433 gimple_phi_arg_location (phi, num_elem - 1)); 434 } 435 436 /* Shrink the vector and return. Note that we do not have to clear 437 PHI_ARG_DEF because the garbage collector will not look at those 438 elements beyond the first PHI_NUM_ARGS elements of the array. */ 439 phi->nargs--; 440} 441 442 443/* Remove all PHI arguments associated with edge E. */ 444 445void 446remove_phi_args (edge e) 447{ 448 gphi_iterator gsi; 449 450 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) 451 remove_phi_arg_num (gsi.phi (), 452 e->dest_idx); 453} 454 455 456/* Remove the PHI node pointed-to by iterator GSI from basic block BB. After 457 removal, iterator GSI is updated to point to the next PHI node in the 458 sequence. If RELEASE_LHS_P is true, the LHS of this PHI node is released 459 into the free pool of SSA names. */ 460 461void 462remove_phi_node (gimple_stmt_iterator *gsi, bool release_lhs_p) 463{ 464 gimple phi = gsi_stmt (*gsi); 465 466 if (release_lhs_p) 467 insert_debug_temps_for_defs (gsi); 468 469 gsi_remove (gsi, false); 470 471 /* If we are deleting the PHI node, then we should release the 472 SSA_NAME node so that it can be reused. */ 473 release_phi_node (phi); 474 if (release_lhs_p) 475 release_ssa_name (gimple_phi_result (phi)); 476} 477 478/* Remove all the phi nodes from BB. */ 479 480void 481remove_phi_nodes (basic_block bb) 482{ 483 gphi_iterator gsi; 484 485 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); ) 486 remove_phi_node (&gsi, true); 487 488 set_phi_nodes (bb, NULL); 489} 490 491/* Given PHI, return its RHS if the PHI is a degenerate, otherwise return 492 NULL. */ 493 494tree 495degenerate_phi_result (gphi *phi) 496{ 497 tree lhs = gimple_phi_result (phi); 498 tree val = NULL; 499 size_t i; 500 501 /* Ignoring arguments which are the same as LHS, if all the remaining 502 arguments are the same, then the PHI is a degenerate and has the 503 value of that common argument. */ 504 for (i = 0; i < gimple_phi_num_args (phi); i++) 505 { 506 tree arg = gimple_phi_arg_def (phi, i); 507 508 if (arg == lhs) 509 continue; 510 else if (!arg) 511 break; 512 else if (!val) 513 val = arg; 514 else if (arg == val) 515 continue; 516 /* We bring in some of operand_equal_p not only to speed things 517 up, but also to avoid crashing when dereferencing the type of 518 a released SSA name. */ 519 else if (TREE_CODE (val) != TREE_CODE (arg) 520 || TREE_CODE (val) == SSA_NAME 521 || !operand_equal_p (arg, val, 0)) 522 break; 523 } 524 return (i == gimple_phi_num_args (phi) ? val : NULL); 525} 526 527/* Set PHI nodes of a basic block BB to SEQ. */ 528 529void 530set_phi_nodes (basic_block bb, gimple_seq seq) 531{ 532 gimple_stmt_iterator i; 533 534 gcc_checking_assert (!(bb->flags & BB_RTL)); 535 bb->il.gimple.phi_nodes = seq; 536 if (seq) 537 for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i)) 538 gimple_set_bb (gsi_stmt (i), bb); 539} 540 541#include "gt-tree-phinodes.h" 542