1/* Generic routines for manipulating PHIs 2 Copyright (C) 2003, 2005 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 2, 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 COPYING. If not, write to 18the Free Software Foundation, 51 Franklin Street, Fifth Floor, 19Boston, MA 02110-1301, USA. */ 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" 27#include "varray.h" 28#include "ggc.h" 29#include "basic-block.h" 30#include "tree-flow.h" 31#include "toplev.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 80static GTY ((deletable (""))) tree free_phinodes[NUM_BUCKETS - 2]; 81static unsigned long free_phinode_count; 82 83static int ideal_phi_node_len (int); 84static void resize_phi_node (tree *, int); 85 86#ifdef GATHER_STATISTICS 87unsigned int phi_nodes_reused; 88unsigned int phi_nodes_created; 89#endif 90 91/* Initialize management of PHIs. */ 92 93void 94init_phinodes (void) 95{ 96 int i; 97 98 for (i = 0; i < NUM_BUCKETS - 2; i++) 99 free_phinodes[i] = NULL; 100 free_phinode_count = 0; 101} 102 103/* Finalize management of PHIs. */ 104 105void 106fini_phinodes (void) 107{ 108 int i; 109 110 for (i = 0; i < NUM_BUCKETS - 2; i++) 111 free_phinodes[i] = NULL; 112 free_phinode_count = 0; 113} 114 115/* Dump some simple statistics regarding the re-use of PHI nodes. */ 116 117#ifdef GATHER_STATISTICS 118void 119phinodes_print_statistics (void) 120{ 121 fprintf (stderr, "PHI nodes allocated: %u\n", phi_nodes_created); 122 fprintf (stderr, "PHI nodes reused: %u\n", phi_nodes_reused); 123} 124#endif 125 126/* Allocate a PHI node with at least LEN arguments. If the free list 127 happens to contain a PHI node with LEN arguments or more, return 128 that one. */ 129 130static inline tree 131allocate_phi_node (int len) 132{ 133 tree phi; 134 int bucket = NUM_BUCKETS - 2; 135 int size = (sizeof (struct tree_phi_node) 136 + (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