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