tree-phinodes.c revision 256281
1193240Ssam/* Generic routines for manipulating PHIs 2193240Ssam Copyright (C) 2003, 2005 Free Software Foundation, Inc. 3193240Ssam 4193240SsamThis file is part of GCC. 5193240Ssam 6193240SsamGCC is free software; you can redistribute it and/or modify 7193240Ssamit under the terms of the GNU General Public License as published by 8193240Ssamthe Free Software Foundation; either version 2, or (at your option) 9193240Ssamany later version. 10193240Ssam 11193240SsamGCC is distributed in the hope that it will be useful, 12193240Ssambut WITHOUT ANY WARRANTY; without even the implied warranty of 13193240SsamMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14193240SsamGNU General Public License for more details. 15193240Ssam 16193240SsamYou should have received a copy of the GNU General Public License 17193240Ssamalong with GCC; see the file COPYING. If not, write to 18193240Ssamthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 19193240SsamBoston, MA 02110-1301, USA. */ 20193240Ssam 21193240Ssam#include "config.h" 22193240Ssam#include "system.h" 23193240Ssam#include "coretypes.h" 24193240Ssam#include "tm.h" 25193240Ssam#include "tree.h" 26193240Ssam#include "rtl.h" 27193240Ssam#include "varray.h" 28193240Ssam#include "ggc.h" 29193240Ssam#include "basic-block.h" 30193240Ssam#include "tree-flow.h" 31193240Ssam#include "toplev.h" 32193240Ssam 33193240Ssam/* Rewriting a function into SSA form can create a huge number of PHIs 34193240Ssam many of which may be thrown away shortly after their creation if jumps 35193240Ssam were threaded through PHI nodes. 36193240Ssam 37193240Ssam While our garbage collection mechanisms will handle this situation, it 38193240Ssam is extremely wasteful to create nodes and throw them away, especially 39193240Ssam when the nodes can be reused. 40193240Ssam 41193240Ssam For PR 8361, we can significantly reduce the number of nodes allocated 42193240Ssam and thus the total amount of memory allocated by managing PHIs a 43193240Ssam little. This additionally helps reduce the amount of work done by the 44193240Ssam garbage collector. Similar results have been seen on a wider variety 45193240Ssam of tests (such as the compiler itself). 46193240Ssam 47193240Ssam Right now we maintain our free list on a per-function basis. It may 48193240Ssam or may not make sense to maintain the free list for the duration of 49193240Ssam a compilation unit. 50193240Ssam 51193240Ssam We could also use a zone allocator for these objects since they have 52193240Ssam a very well defined lifetime. If someone wants to experiment with that 53193240Ssam this is the place to try it. 54193240Ssam 55193240Ssam PHI nodes have different sizes, so we can't have a single list of all 56193240Ssam the PHI nodes as it would be too expensive to walk down that list to 57193240Ssam find a PHI of a suitable size. 58193240Ssam 59193240Ssam Instead we have an array of lists of free PHI nodes. The array is 60193240Ssam indexed by the number of PHI alternatives that PHI node can hold. 61193240Ssam Except for the last array member, which holds all remaining PHI 62193240Ssam nodes. 63193240Ssam 64193240Ssam So to find a free PHI node, we compute its index into the free PHI 65193240Ssam node array and see if there are any elements with an exact match. 66193240Ssam If so, then we are done. Otherwise, we test the next larger size 67193240Ssam up and continue until we are in the last array element. 68193240Ssam 69193240Ssam We do not actually walk members of the last array element. While it 70193240Ssam might allow us to pick up a few reusable PHI nodes, it could potentially 71193240Ssam be very expensive if the program has released a bunch of large PHI nodes, 72193240Ssam but keeps asking for even larger PHI nodes. Experiments have shown that 73193240Ssam walking the elements of the last array entry would result in finding less 74193240Ssam than .1% additional reusable PHI nodes. 75193240Ssam 76193240Ssam Note that we can never have less than two PHI argument slots. Thus, 77193240Ssam the -2 on all the calculations below. */ 78193240Ssam 79193240Ssam#define NUM_BUCKETS 10 80193240Ssamstatic GTY ((deletable (""))) tree free_phinodes[NUM_BUCKETS - 2]; 81193240Ssamstatic unsigned long free_phinode_count; 82193240Ssam 83193240Ssamstatic int ideal_phi_node_len (int); 84193240Ssamstatic void resize_phi_node (tree *, int); 85193240Ssam 86193240Ssam#ifdef GATHER_STATISTICS 87193240Ssamunsigned int phi_nodes_reused; 88193240Ssamunsigned int phi_nodes_created; 89193240Ssam#endif 90193240Ssam 91193240Ssam/* Initialize management of PHIs. */ 92193240Ssam 93193240Ssamvoid 94193240Ssaminit_phinodes (void) 95193240Ssam{ 96193240Ssam int i; 97193240Ssam 98193240Ssam for (i = 0; i < NUM_BUCKETS - 2; i++) 99193240Ssam free_phinodes[i] = NULL; 100193240Ssam free_phinode_count = 0; 101193240Ssam} 102193240Ssam 103193240Ssam/* Finalize management of PHIs. */ 104193240Ssam 105193240Ssamvoid 106193240Ssamfini_phinodes (void) 107193240Ssam{ 108193240Ssam int i; 109193240Ssam 110193240Ssam for (i = 0; i < NUM_BUCKETS - 2; i++) 111193240Ssam free_phinodes[i] = NULL; 112193240Ssam free_phinode_count = 0; 113193240Ssam} 114193240Ssam 115193240Ssam/* Dump some simple statistics regarding the re-use of PHI nodes. */ 116193240Ssam 117193240Ssam#ifdef GATHER_STATISTICS 118193240Ssamvoid 119193240Ssamphinodes_print_statistics (void) 120193240Ssam{ 121193240Ssam fprintf (stderr, "PHI nodes allocated: %u\n", phi_nodes_created); 122193240Ssam fprintf (stderr, "PHI nodes reused: %u\n", phi_nodes_reused); 123193240Ssam} 124193240Ssam#endif 125193240Ssam 126193240Ssam/* Allocate a PHI node with at least LEN arguments. If the free list 127193240Ssam happens to contain a PHI node with LEN arguments or more, return 128193240Ssam that one. */ 129193240Ssam 130193240Ssamstatic inline tree 131193240Ssamallocate_phi_node (int len) 132193240Ssam{ 133193240Ssam tree phi; 134193240Ssam int bucket = NUM_BUCKETS - 2; 135193240Ssam int size = (sizeof (struct tree_phi_node) 136193240Ssam + (len - 1) * sizeof (struct phi_arg_d)); 137 138 if (free_phinode_count) 139 for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++) 140 if (free_phinodes[bucket]) 141 break; 142 143 /* If our free list has an element, then use it. */ 144 if (bucket < NUM_BUCKETS - 2 145 && PHI_ARG_CAPACITY (free_phinodes[bucket]) >= len) 146 { 147 free_phinode_count--; 148 phi = free_phinodes[bucket]; 149 free_phinodes[bucket] = PHI_CHAIN (free_phinodes[bucket]); 150#ifdef GATHER_STATISTICS 151 phi_nodes_reused++; 152#endif 153 } 154 else 155 { 156 phi = ggc_alloc (size); 157#ifdef GATHER_STATISTICS 158 phi_nodes_created++; 159 tree_node_counts[(int) phi_kind]++; 160 tree_node_sizes[(int) phi_kind] += size; 161#endif 162 } 163 164 return phi; 165} 166 167/* Given LEN, the original number of requested PHI arguments, return 168 a new, "ideal" length for the PHI node. The "ideal" length rounds 169 the total size of the PHI node up to the next power of two bytes. 170 171 Rounding up will not result in wasting any memory since the size request 172 will be rounded up by the GC system anyway. [ Note this is not entirely 173 true since the original length might have fit on one of the special 174 GC pages. ] By rounding up, we may avoid the need to reallocate the 175 PHI node later if we increase the number of arguments for the PHI. */ 176 177static int 178ideal_phi_node_len (int len) 179{ 180 size_t size, new_size; 181 int log2, new_len; 182 183 /* We do not support allocations of less than two PHI argument slots. */ 184 if (len < 2) 185 len = 2; 186 187 /* Compute the number of bytes of the original request. */ 188 size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d); 189 190 /* Round it up to the next power of two. */ 191 log2 = ceil_log2 (size); 192 new_size = 1 << log2; 193 194 /* Now compute and return the number of PHI argument slots given an 195 ideal size allocation. */ 196 new_len = len + (new_size - size) / sizeof (struct phi_arg_d); 197 return new_len; 198} 199 200 201/* Return a PHI node with LEN argument slots for variable VAR. */ 202 203static tree 204make_phi_node (tree var, int len) 205{ 206 tree phi; 207 int capacity, i; 208 209 capacity = ideal_phi_node_len (len); 210 211 phi = allocate_phi_node (capacity); 212 213 /* We need to clear the entire PHI node, including the argument 214 portion, because we represent a "missing PHI argument" by placing 215 NULL_TREE in PHI_ARG_DEF. */ 216 memset (phi, 0, (sizeof (struct tree_phi_node) - sizeof (struct phi_arg_d) 217 + sizeof (struct phi_arg_d) * len)); 218 TREE_SET_CODE (phi, PHI_NODE); 219 PHI_NUM_ARGS (phi) = len; 220 PHI_ARG_CAPACITY (phi) = capacity; 221 TREE_TYPE (phi) = TREE_TYPE (var); 222 if (TREE_CODE (var) == SSA_NAME) 223 SET_PHI_RESULT (phi, var); 224 else 225 SET_PHI_RESULT (phi, make_ssa_name (var, phi)); 226 227 for (i = 0; i < capacity; i++) 228 { 229 use_operand_p imm; 230 imm = &(PHI_ARG_IMM_USE_NODE (phi, i)); 231 imm->use = &(PHI_ARG_DEF_TREE (phi, i)); 232 imm->prev = NULL; 233 imm->next = NULL; 234 imm->stmt = phi; 235 } 236 return phi; 237} 238 239/* We no longer need PHI, release it so that it may be reused. */ 240 241void 242release_phi_node (tree phi) 243{ 244 int bucket; 245 int len = PHI_ARG_CAPACITY (phi); 246 int x; 247 248 for (x = 0; x < PHI_NUM_ARGS (phi); x++) 249 { 250 use_operand_p imm; 251 imm = &(PHI_ARG_IMM_USE_NODE (phi, x)); 252 delink_imm_use (imm); 253 } 254 255 bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len; 256 bucket -= 2; 257 PHI_CHAIN (phi) = free_phinodes[bucket]; 258 free_phinodes[bucket] = phi; 259 free_phinode_count++; 260} 261 262/* Resize an existing PHI node. The only way is up. Return the 263 possibly relocated phi. */ 264 265static void 266resize_phi_node (tree *phi, int len) 267{ 268 int old_size, i; 269 tree new_phi; 270 271 gcc_assert (len > PHI_ARG_CAPACITY (*phi)); 272 273 /* The garbage collector will not look at the PHI node beyond the 274 first PHI_NUM_ARGS elements. Therefore, all we have to copy is a 275 portion of the PHI node currently in use. */ 276 old_size = (sizeof (struct tree_phi_node) 277 + (PHI_NUM_ARGS (*phi) - 1) * sizeof (struct phi_arg_d)); 278 279 new_phi = allocate_phi_node (len); 280 281 memcpy (new_phi, *phi, old_size); 282 283 for (i = 0; i < PHI_NUM_ARGS (new_phi); i++) 284 { 285 use_operand_p imm, old_imm; 286 imm = &(PHI_ARG_IMM_USE_NODE (new_phi, i)); 287 old_imm = &(PHI_ARG_IMM_USE_NODE (*phi, i)); 288 imm->use = &(PHI_ARG_DEF_TREE (new_phi, i)); 289 relink_imm_use_stmt (imm, old_imm, new_phi); 290 } 291 292 PHI_ARG_CAPACITY (new_phi) = len; 293 294 for (i = PHI_NUM_ARGS (new_phi); i < len; i++) 295 { 296 use_operand_p imm; 297 imm = &(PHI_ARG_IMM_USE_NODE (new_phi, i)); 298 imm->use = &(PHI_ARG_DEF_TREE (new_phi, i)); 299 imm->prev = NULL; 300 imm->next = NULL; 301 imm->stmt = new_phi; 302 } 303 304 305 *phi = new_phi; 306} 307 308/* Reserve PHI arguments for a new edge to basic block BB. */ 309 310void 311reserve_phi_args_for_new_edge (basic_block bb) 312{ 313 tree *loc; 314 int len = EDGE_COUNT (bb->preds); 315 int cap = ideal_phi_node_len (len + 4); 316 317 for (loc = &(bb->phi_nodes); 318 *loc; 319 loc = &PHI_CHAIN (*loc)) 320 { 321 if (len > PHI_ARG_CAPACITY (*loc)) 322 { 323 tree old_phi = *loc; 324 325 resize_phi_node (loc, cap); 326 327 /* The result of the phi is defined by this phi node. */ 328 SSA_NAME_DEF_STMT (PHI_RESULT (*loc)) = *loc; 329 330 release_phi_node (old_phi); 331 } 332 333 /* We represent a "missing PHI argument" by placing NULL_TREE in 334 the corresponding slot. If PHI arguments were added 335 immediately after an edge is created, this zeroing would not 336 be necessary, but unfortunately this is not the case. For 337 example, the loop optimizer duplicates several basic blocks, 338 redirects edges, and then fixes up PHI arguments later in 339 batch. */ 340 SET_PHI_ARG_DEF (*loc, len - 1, NULL_TREE); 341 342 PHI_NUM_ARGS (*loc)++; 343 } 344} 345 346/* Create a new PHI node for variable VAR at basic block BB. */ 347 348tree 349create_phi_node (tree var, basic_block bb) 350{ 351 tree phi; 352 353 phi = make_phi_node (var, EDGE_COUNT (bb->preds)); 354 355 /* Add the new PHI node to the list of PHI nodes for block BB. */ 356 PHI_CHAIN (phi) = phi_nodes (bb); 357 bb->phi_nodes = phi; 358 359 /* Associate BB to the PHI node. */ 360 set_bb_for_stmt (phi, bb); 361 362 return phi; 363} 364 365/* Add a new argument to PHI node PHI. DEF is the incoming reaching 366 definition and E is the edge through which DEF reaches PHI. The new 367 argument is added at the end of the argument list. 368 If PHI has reached its maximum capacity, add a few slots. In this case, 369 PHI points to the reallocated phi node when we return. */ 370 371void 372add_phi_arg (tree phi, tree def, edge e) 373{ 374 basic_block bb = e->dest; 375 376 gcc_assert (bb == bb_for_stmt (phi)); 377 378 /* We resize PHI nodes upon edge creation. We should always have 379 enough room at this point. */ 380 gcc_assert (PHI_NUM_ARGS (phi) <= PHI_ARG_CAPACITY (phi)); 381 382 /* We resize PHI nodes upon edge creation. We should always have 383 enough room at this point. */ 384 gcc_assert (e->dest_idx < (unsigned int) PHI_NUM_ARGS (phi)); 385 386 /* Copy propagation needs to know what object occur in abnormal 387 PHI nodes. This is a convenient place to record such information. */ 388 if (e->flags & EDGE_ABNORMAL) 389 { 390 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1; 391 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1; 392 } 393 394 SET_PHI_ARG_DEF (phi, e->dest_idx, def); 395} 396 397/* Remove the Ith argument from PHI's argument list. This routine 398 implements removal by swapping the last alternative with the 399 alternative we want to delete and then shrinking the vector, which 400 is consistent with how we remove an edge from the edge vector. */ 401 402static void 403remove_phi_arg_num (tree phi, int i) 404{ 405 int num_elem = PHI_NUM_ARGS (phi); 406 407 gcc_assert (i < num_elem); 408 409 410 /* Delink the item which is being removed. */ 411 delink_imm_use (&(PHI_ARG_IMM_USE_NODE (phi, i))); 412 413 /* If it is not the last element, move the last element 414 to the element we want to delete, resetting all the links. */ 415 if (i != num_elem - 1) 416 { 417 use_operand_p old_p, new_p; 418 old_p = &PHI_ARG_IMM_USE_NODE (phi, num_elem - 1); 419 new_p = &PHI_ARG_IMM_USE_NODE (phi, i); 420 /* Set use on new node, and link into last element's place. */ 421 *(new_p->use) = *(old_p->use); 422 relink_imm_use (new_p, old_p); 423 } 424 425 /* Shrink the vector and return. Note that we do not have to clear 426 PHI_ARG_DEF because the garbage collector will not look at those 427 elements beyond the first PHI_NUM_ARGS elements of the array. */ 428 PHI_NUM_ARGS (phi)--; 429} 430 431/* Remove all PHI arguments associated with edge E. */ 432 433void 434remove_phi_args (edge e) 435{ 436 tree phi; 437 438 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) 439 remove_phi_arg_num (phi, e->dest_idx); 440} 441 442/* Remove PHI node PHI from basic block BB. If PREV is non-NULL, it is 443 used as the node immediately before PHI in the linked list. */ 444 445void 446remove_phi_node (tree phi, tree prev) 447{ 448 tree *loc; 449 450 if (prev) 451 { 452 loc = &PHI_CHAIN (prev); 453 } 454 else 455 { 456 for (loc = &(bb_for_stmt (phi)->phi_nodes); 457 *loc != phi; 458 loc = &PHI_CHAIN (*loc)) 459 ; 460 } 461 462 /* Remove PHI from the chain. */ 463 *loc = PHI_CHAIN (phi); 464 465 /* If we are deleting the PHI node, then we should release the 466 SSA_NAME node so that it can be reused. */ 467 release_phi_node (phi); 468 release_ssa_name (PHI_RESULT (phi)); 469} 470 471 472/* Reverse the order of PHI nodes in the chain PHI. 473 Return the new head of the chain (old last PHI node). */ 474 475tree 476phi_reverse (tree phi) 477{ 478 tree prev = NULL_TREE, next; 479 for (; phi; phi = next) 480 { 481 next = PHI_CHAIN (phi); 482 PHI_CHAIN (phi) = prev; 483 prev = phi; 484 } 485 return prev; 486} 487 488#include "gt-tree-phinodes.h" 489