1169689Skan/* Generic routines for manipulating PHIs 2169689Skan Copyright (C) 2003, 2005 Free Software Foundation, Inc. 3169689Skan 4169689SkanThis file is part of GCC. 5169689Skan 6169689SkanGCC is free software; you can redistribute it and/or modify 7169689Skanit under the terms of the GNU General Public License as published by 8169689Skanthe Free Software Foundation; either version 2, or (at your option) 9169689Skanany later version. 10169689Skan 11169689SkanGCC is distributed in the hope that it will be useful, 12169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 13169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14169689SkanGNU General Public License for more details. 15169689Skan 16169689SkanYou should have received a copy of the GNU General Public License 17169689Skanalong with GCC; see the file COPYING. If not, write to 18169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 19169689SkanBoston, MA 02110-1301, USA. */ 20169689Skan 21169689Skan#include "config.h" 22169689Skan#include "system.h" 23169689Skan#include "coretypes.h" 24169689Skan#include "tm.h" 25169689Skan#include "tree.h" 26169689Skan#include "rtl.h" 27169689Skan#include "varray.h" 28169689Skan#include "ggc.h" 29169689Skan#include "basic-block.h" 30169689Skan#include "tree-flow.h" 31169689Skan#include "toplev.h" 32169689Skan 33169689Skan/* Rewriting a function into SSA form can create a huge number of PHIs 34169689Skan many of which may be thrown away shortly after their creation if jumps 35169689Skan were threaded through PHI nodes. 36169689Skan 37169689Skan While our garbage collection mechanisms will handle this situation, it 38169689Skan is extremely wasteful to create nodes and throw them away, especially 39169689Skan when the nodes can be reused. 40169689Skan 41169689Skan For PR 8361, we can significantly reduce the number of nodes allocated 42169689Skan and thus the total amount of memory allocated by managing PHIs a 43169689Skan little. This additionally helps reduce the amount of work done by the 44169689Skan garbage collector. Similar results have been seen on a wider variety 45169689Skan of tests (such as the compiler itself). 46169689Skan 47169689Skan Right now we maintain our free list on a per-function basis. It may 48169689Skan or may not make sense to maintain the free list for the duration of 49169689Skan a compilation unit. 50169689Skan 51169689Skan We could also use a zone allocator for these objects since they have 52169689Skan a very well defined lifetime. If someone wants to experiment with that 53169689Skan this is the place to try it. 54169689Skan 55169689Skan PHI nodes have different sizes, so we can't have a single list of all 56169689Skan the PHI nodes as it would be too expensive to walk down that list to 57169689Skan find a PHI of a suitable size. 58169689Skan 59169689Skan Instead we have an array of lists of free PHI nodes. The array is 60169689Skan indexed by the number of PHI alternatives that PHI node can hold. 61169689Skan Except for the last array member, which holds all remaining PHI 62169689Skan nodes. 63169689Skan 64169689Skan So to find a free PHI node, we compute its index into the free PHI 65169689Skan node array and see if there are any elements with an exact match. 66169689Skan If so, then we are done. Otherwise, we test the next larger size 67169689Skan up and continue until we are in the last array element. 68169689Skan 69169689Skan We do not actually walk members of the last array element. While it 70169689Skan might allow us to pick up a few reusable PHI nodes, it could potentially 71169689Skan be very expensive if the program has released a bunch of large PHI nodes, 72169689Skan but keeps asking for even larger PHI nodes. Experiments have shown that 73169689Skan walking the elements of the last array entry would result in finding less 74169689Skan than .1% additional reusable PHI nodes. 75169689Skan 76169689Skan Note that we can never have less than two PHI argument slots. Thus, 77169689Skan the -2 on all the calculations below. */ 78169689Skan 79169689Skan#define NUM_BUCKETS 10 80169689Skanstatic GTY ((deletable (""))) tree free_phinodes[NUM_BUCKETS - 2]; 81169689Skanstatic unsigned long free_phinode_count; 82169689Skan 83169689Skanstatic int ideal_phi_node_len (int); 84169689Skanstatic void resize_phi_node (tree *, int); 85169689Skan 86169689Skan#ifdef GATHER_STATISTICS 87169689Skanunsigned int phi_nodes_reused; 88169689Skanunsigned int phi_nodes_created; 89169689Skan#endif 90169689Skan 91169689Skan/* Initialize management of PHIs. */ 92169689Skan 93169689Skanvoid 94169689Skaninit_phinodes (void) 95169689Skan{ 96169689Skan int i; 97169689Skan 98169689Skan for (i = 0; i < NUM_BUCKETS - 2; i++) 99169689Skan free_phinodes[i] = NULL; 100169689Skan free_phinode_count = 0; 101169689Skan} 102169689Skan 103169689Skan/* Finalize management of PHIs. */ 104169689Skan 105169689Skanvoid 106169689Skanfini_phinodes (void) 107169689Skan{ 108169689Skan int i; 109169689Skan 110169689Skan for (i = 0; i < NUM_BUCKETS - 2; i++) 111169689Skan free_phinodes[i] = NULL; 112169689Skan free_phinode_count = 0; 113169689Skan} 114169689Skan 115169689Skan/* Dump some simple statistics regarding the re-use of PHI nodes. */ 116169689Skan 117169689Skan#ifdef GATHER_STATISTICS 118169689Skanvoid 119169689Skanphinodes_print_statistics (void) 120169689Skan{ 121169689Skan fprintf (stderr, "PHI nodes allocated: %u\n", phi_nodes_created); 122169689Skan fprintf (stderr, "PHI nodes reused: %u\n", phi_nodes_reused); 123169689Skan} 124169689Skan#endif 125169689Skan 126169689Skan/* Allocate a PHI node with at least LEN arguments. If the free list 127169689Skan happens to contain a PHI node with LEN arguments or more, return 128169689Skan that one. */ 129169689Skan 130169689Skanstatic inline tree 131169689Skanallocate_phi_node (int len) 132169689Skan{ 133169689Skan tree phi; 134169689Skan int bucket = NUM_BUCKETS - 2; 135169689Skan int size = (sizeof (struct tree_phi_node) 136169689Skan + (len - 1) * sizeof (struct phi_arg_d)); 137169689Skan 138169689Skan if (free_phinode_count) 139169689Skan for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++) 140169689Skan if (free_phinodes[bucket]) 141169689Skan break; 142169689Skan 143169689Skan /* If our free list has an element, then use it. */ 144169689Skan if (bucket < NUM_BUCKETS - 2 145169689Skan && PHI_ARG_CAPACITY (free_phinodes[bucket]) >= len) 146169689Skan { 147169689Skan free_phinode_count--; 148169689Skan phi = free_phinodes[bucket]; 149169689Skan free_phinodes[bucket] = PHI_CHAIN (free_phinodes[bucket]); 150169689Skan#ifdef GATHER_STATISTICS 151169689Skan phi_nodes_reused++; 152169689Skan#endif 153169689Skan } 154169689Skan else 155169689Skan { 156169689Skan phi = ggc_alloc (size); 157169689Skan#ifdef GATHER_STATISTICS 158169689Skan phi_nodes_created++; 159169689Skan tree_node_counts[(int) phi_kind]++; 160169689Skan tree_node_sizes[(int) phi_kind] += size; 161169689Skan#endif 162169689Skan } 163169689Skan 164169689Skan return phi; 165169689Skan} 166169689Skan 167169689Skan/* Given LEN, the original number of requested PHI arguments, return 168169689Skan a new, "ideal" length for the PHI node. The "ideal" length rounds 169169689Skan the total size of the PHI node up to the next power of two bytes. 170169689Skan 171169689Skan Rounding up will not result in wasting any memory since the size request 172169689Skan will be rounded up by the GC system anyway. [ Note this is not entirely 173169689Skan true since the original length might have fit on one of the special 174169689Skan GC pages. ] By rounding up, we may avoid the need to reallocate the 175169689Skan PHI node later if we increase the number of arguments for the PHI. */ 176169689Skan 177169689Skanstatic int 178169689Skanideal_phi_node_len (int len) 179169689Skan{ 180169689Skan size_t size, new_size; 181169689Skan int log2, new_len; 182169689Skan 183169689Skan /* We do not support allocations of less than two PHI argument slots. */ 184169689Skan if (len < 2) 185169689Skan len = 2; 186169689Skan 187169689Skan /* Compute the number of bytes of the original request. */ 188169689Skan size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d); 189169689Skan 190169689Skan /* Round it up to the next power of two. */ 191169689Skan log2 = ceil_log2 (size); 192169689Skan new_size = 1 << log2; 193169689Skan 194169689Skan /* Now compute and return the number of PHI argument slots given an 195169689Skan ideal size allocation. */ 196169689Skan new_len = len + (new_size - size) / sizeof (struct phi_arg_d); 197169689Skan return new_len; 198169689Skan} 199169689Skan 200169689Skan 201169689Skan/* Return a PHI node with LEN argument slots for variable VAR. */ 202169689Skan 203169689Skanstatic tree 204169689Skanmake_phi_node (tree var, int len) 205169689Skan{ 206169689Skan tree phi; 207169689Skan int capacity, i; 208169689Skan 209169689Skan capacity = ideal_phi_node_len (len); 210169689Skan 211169689Skan phi = allocate_phi_node (capacity); 212169689Skan 213169689Skan /* We need to clear the entire PHI node, including the argument 214169689Skan portion, because we represent a "missing PHI argument" by placing 215169689Skan NULL_TREE in PHI_ARG_DEF. */ 216169689Skan memset (phi, 0, (sizeof (struct tree_phi_node) - sizeof (struct phi_arg_d) 217169689Skan + sizeof (struct phi_arg_d) * len)); 218169689Skan TREE_SET_CODE (phi, PHI_NODE); 219169689Skan PHI_NUM_ARGS (phi) = len; 220169689Skan PHI_ARG_CAPACITY (phi) = capacity; 221169689Skan TREE_TYPE (phi) = TREE_TYPE (var); 222169689Skan if (TREE_CODE (var) == SSA_NAME) 223169689Skan SET_PHI_RESULT (phi, var); 224169689Skan else 225169689Skan SET_PHI_RESULT (phi, make_ssa_name (var, phi)); 226169689Skan 227169689Skan for (i = 0; i < capacity; i++) 228169689Skan { 229169689Skan use_operand_p imm; 230169689Skan imm = &(PHI_ARG_IMM_USE_NODE (phi, i)); 231169689Skan imm->use = &(PHI_ARG_DEF_TREE (phi, i)); 232169689Skan imm->prev = NULL; 233169689Skan imm->next = NULL; 234169689Skan imm->stmt = phi; 235169689Skan } 236169689Skan return phi; 237169689Skan} 238169689Skan 239169689Skan/* We no longer need PHI, release it so that it may be reused. */ 240169689Skan 241169689Skanvoid 242169689Skanrelease_phi_node (tree phi) 243169689Skan{ 244169689Skan int bucket; 245169689Skan int len = PHI_ARG_CAPACITY (phi); 246169689Skan int x; 247169689Skan 248169689Skan for (x = 0; x < PHI_NUM_ARGS (phi); x++) 249169689Skan { 250169689Skan use_operand_p imm; 251169689Skan imm = &(PHI_ARG_IMM_USE_NODE (phi, x)); 252169689Skan delink_imm_use (imm); 253169689Skan } 254169689Skan 255169689Skan bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len; 256169689Skan bucket -= 2; 257169689Skan PHI_CHAIN (phi) = free_phinodes[bucket]; 258169689Skan free_phinodes[bucket] = phi; 259169689Skan free_phinode_count++; 260169689Skan} 261169689Skan 262169689Skan/* Resize an existing PHI node. The only way is up. Return the 263169689Skan possibly relocated phi. */ 264169689Skan 265169689Skanstatic void 266169689Skanresize_phi_node (tree *phi, int len) 267169689Skan{ 268169689Skan int old_size, i; 269169689Skan tree new_phi; 270169689Skan 271169689Skan gcc_assert (len > PHI_ARG_CAPACITY (*phi)); 272169689Skan 273169689Skan /* The garbage collector will not look at the PHI node beyond the 274169689Skan first PHI_NUM_ARGS elements. Therefore, all we have to copy is a 275169689Skan portion of the PHI node currently in use. */ 276169689Skan old_size = (sizeof (struct tree_phi_node) 277169689Skan + (PHI_NUM_ARGS (*phi) - 1) * sizeof (struct phi_arg_d)); 278169689Skan 279169689Skan new_phi = allocate_phi_node (len); 280169689Skan 281169689Skan memcpy (new_phi, *phi, old_size); 282169689Skan 283169689Skan for (i = 0; i < PHI_NUM_ARGS (new_phi); i++) 284169689Skan { 285169689Skan use_operand_p imm, old_imm; 286169689Skan imm = &(PHI_ARG_IMM_USE_NODE (new_phi, i)); 287169689Skan old_imm = &(PHI_ARG_IMM_USE_NODE (*phi, i)); 288169689Skan imm->use = &(PHI_ARG_DEF_TREE (new_phi, i)); 289169689Skan relink_imm_use_stmt (imm, old_imm, new_phi); 290169689Skan } 291169689Skan 292169689Skan PHI_ARG_CAPACITY (new_phi) = len; 293169689Skan 294169689Skan for (i = PHI_NUM_ARGS (new_phi); i < len; i++) 295169689Skan { 296169689Skan use_operand_p imm; 297169689Skan imm = &(PHI_ARG_IMM_USE_NODE (new_phi, i)); 298169689Skan imm->use = &(PHI_ARG_DEF_TREE (new_phi, i)); 299169689Skan imm->prev = NULL; 300169689Skan imm->next = NULL; 301169689Skan imm->stmt = new_phi; 302169689Skan } 303169689Skan 304169689Skan 305169689Skan *phi = new_phi; 306169689Skan} 307169689Skan 308169689Skan/* Reserve PHI arguments for a new edge to basic block BB. */ 309169689Skan 310169689Skanvoid 311169689Skanreserve_phi_args_for_new_edge (basic_block bb) 312169689Skan{ 313169689Skan tree *loc; 314169689Skan int len = EDGE_COUNT (bb->preds); 315169689Skan int cap = ideal_phi_node_len (len + 4); 316169689Skan 317169689Skan for (loc = &(bb->phi_nodes); 318169689Skan *loc; 319169689Skan loc = &PHI_CHAIN (*loc)) 320169689Skan { 321169689Skan if (len > PHI_ARG_CAPACITY (*loc)) 322169689Skan { 323169689Skan tree old_phi = *loc; 324169689Skan 325169689Skan resize_phi_node (loc, cap); 326169689Skan 327169689Skan /* The result of the phi is defined by this phi node. */ 328169689Skan SSA_NAME_DEF_STMT (PHI_RESULT (*loc)) = *loc; 329169689Skan 330169689Skan release_phi_node (old_phi); 331169689Skan } 332169689Skan 333169689Skan /* We represent a "missing PHI argument" by placing NULL_TREE in 334169689Skan the corresponding slot. If PHI arguments were added 335169689Skan immediately after an edge is created, this zeroing would not 336169689Skan be necessary, but unfortunately this is not the case. For 337169689Skan example, the loop optimizer duplicates several basic blocks, 338169689Skan redirects edges, and then fixes up PHI arguments later in 339169689Skan batch. */ 340169689Skan SET_PHI_ARG_DEF (*loc, len - 1, NULL_TREE); 341169689Skan 342169689Skan PHI_NUM_ARGS (*loc)++; 343169689Skan } 344169689Skan} 345169689Skan 346169689Skan/* Create a new PHI node for variable VAR at basic block BB. */ 347169689Skan 348169689Skantree 349169689Skancreate_phi_node (tree var, basic_block bb) 350169689Skan{ 351169689Skan tree phi; 352169689Skan 353169689Skan phi = make_phi_node (var, EDGE_COUNT (bb->preds)); 354169689Skan 355169689Skan /* Add the new PHI node to the list of PHI nodes for block BB. */ 356169689Skan PHI_CHAIN (phi) = phi_nodes (bb); 357169689Skan bb->phi_nodes = phi; 358169689Skan 359169689Skan /* Associate BB to the PHI node. */ 360169689Skan set_bb_for_stmt (phi, bb); 361169689Skan 362169689Skan return phi; 363169689Skan} 364169689Skan 365169689Skan/* Add a new argument to PHI node PHI. DEF is the incoming reaching 366169689Skan definition and E is the edge through which DEF reaches PHI. The new 367169689Skan argument is added at the end of the argument list. 368169689Skan If PHI has reached its maximum capacity, add a few slots. In this case, 369169689Skan PHI points to the reallocated phi node when we return. */ 370169689Skan 371169689Skanvoid 372169689Skanadd_phi_arg (tree phi, tree def, edge e) 373169689Skan{ 374169689Skan basic_block bb = e->dest; 375169689Skan 376169689Skan gcc_assert (bb == bb_for_stmt (phi)); 377169689Skan 378169689Skan /* We resize PHI nodes upon edge creation. We should always have 379169689Skan enough room at this point. */ 380169689Skan gcc_assert (PHI_NUM_ARGS (phi) <= PHI_ARG_CAPACITY (phi)); 381169689Skan 382169689Skan /* We resize PHI nodes upon edge creation. We should always have 383169689Skan enough room at this point. */ 384169689Skan gcc_assert (e->dest_idx < (unsigned int) PHI_NUM_ARGS (phi)); 385169689Skan 386169689Skan /* Copy propagation needs to know what object occur in abnormal 387169689Skan PHI nodes. This is a convenient place to record such information. */ 388169689Skan if (e->flags & EDGE_ABNORMAL) 389169689Skan { 390169689Skan SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1; 391169689Skan SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1; 392169689Skan } 393169689Skan 394169689Skan SET_PHI_ARG_DEF (phi, e->dest_idx, def); 395169689Skan} 396169689Skan 397169689Skan/* Remove the Ith argument from PHI's argument list. This routine 398169689Skan implements removal by swapping the last alternative with the 399169689Skan alternative we want to delete and then shrinking the vector, which 400169689Skan is consistent with how we remove an edge from the edge vector. */ 401169689Skan 402169689Skanstatic void 403169689Skanremove_phi_arg_num (tree phi, int i) 404169689Skan{ 405169689Skan int num_elem = PHI_NUM_ARGS (phi); 406169689Skan 407169689Skan gcc_assert (i < num_elem); 408169689Skan 409169689Skan 410169689Skan /* Delink the item which is being removed. */ 411169689Skan delink_imm_use (&(PHI_ARG_IMM_USE_NODE (phi, i))); 412169689Skan 413169689Skan /* If it is not the last element, move the last element 414169689Skan to the element we want to delete, resetting all the links. */ 415169689Skan if (i != num_elem - 1) 416169689Skan { 417169689Skan use_operand_p old_p, new_p; 418169689Skan old_p = &PHI_ARG_IMM_USE_NODE (phi, num_elem - 1); 419169689Skan new_p = &PHI_ARG_IMM_USE_NODE (phi, i); 420169689Skan /* Set use on new node, and link into last element's place. */ 421169689Skan *(new_p->use) = *(old_p->use); 422169689Skan relink_imm_use (new_p, old_p); 423169689Skan } 424169689Skan 425169689Skan /* Shrink the vector and return. Note that we do not have to clear 426169689Skan PHI_ARG_DEF because the garbage collector will not look at those 427169689Skan elements beyond the first PHI_NUM_ARGS elements of the array. */ 428169689Skan PHI_NUM_ARGS (phi)--; 429169689Skan} 430169689Skan 431169689Skan/* Remove all PHI arguments associated with edge E. */ 432169689Skan 433169689Skanvoid 434169689Skanremove_phi_args (edge e) 435169689Skan{ 436169689Skan tree phi; 437169689Skan 438169689Skan for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) 439169689Skan remove_phi_arg_num (phi, e->dest_idx); 440169689Skan} 441169689Skan 442169689Skan/* Remove PHI node PHI from basic block BB. If PREV is non-NULL, it is 443169689Skan used as the node immediately before PHI in the linked list. */ 444169689Skan 445169689Skanvoid 446169689Skanremove_phi_node (tree phi, tree prev) 447169689Skan{ 448169689Skan tree *loc; 449169689Skan 450169689Skan if (prev) 451169689Skan { 452169689Skan loc = &PHI_CHAIN (prev); 453169689Skan } 454169689Skan else 455169689Skan { 456169689Skan for (loc = &(bb_for_stmt (phi)->phi_nodes); 457169689Skan *loc != phi; 458169689Skan loc = &PHI_CHAIN (*loc)) 459169689Skan ; 460169689Skan } 461169689Skan 462169689Skan /* Remove PHI from the chain. */ 463169689Skan *loc = PHI_CHAIN (phi); 464169689Skan 465169689Skan /* If we are deleting the PHI node, then we should release the 466169689Skan SSA_NAME node so that it can be reused. */ 467169689Skan release_phi_node (phi); 468169689Skan release_ssa_name (PHI_RESULT (phi)); 469169689Skan} 470169689Skan 471169689Skan 472169689Skan/* Reverse the order of PHI nodes in the chain PHI. 473169689Skan Return the new head of the chain (old last PHI node). */ 474169689Skan 475169689Skantree 476169689Skanphi_reverse (tree phi) 477169689Skan{ 478169689Skan tree prev = NULL_TREE, next; 479169689Skan for (; phi; phi = next) 480169689Skan { 481169689Skan next = PHI_CHAIN (phi); 482169689Skan PHI_CHAIN (phi) = prev; 483169689Skan prev = phi; 484169689Skan } 485169689Skan return prev; 486169689Skan} 487169689Skan 488169689Skan#include "gt-tree-phinodes.h" 489