X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-phinodes.c;h=e77f4884d727d6a81ceb58f30ce3590f092999ff;hb=f38e9908a187124e506ee74ec2e4dc9dd7669d65;hp=e4fc904fd4a5e802a7405d755cf3d9e8619ffb7b;hpb=4ee9c6840ad3fc92a9034343278a1e476ad6872a;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-phinodes.c b/gcc/tree-phinodes.c index e4fc904fd4a..e77f4884d72 100644 --- a/gcc/tree-phinodes.c +++ b/gcc/tree-phinodes.c @@ -1,23 +1,23 @@ /* Generic routines for manipulating PHIs - Copyright (C) 2003 Free Software Foundation, Inc. - + Copyright (C) 2003, 2005 Free Software Foundation, Inc. + This file is part of GCC. - + GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. - + GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. - + You should have received a copy of the GNU General Public License along with GCC; see the file COPYING. If not, write to -the Free Software Foundation, 59 Temple Place - Suite 330, -Boston, MA 02111-1307, USA. */ - +the Free Software Foundation, 51 Franklin Street, Fifth Floor, +Boston, MA 02110-1301, USA. */ + #include "config.h" #include "system.h" #include "coretypes.h" @@ -32,7 +32,7 @@ Boston, MA 02111-1307, USA. */ /* Rewriting a function into SSA form can create a huge number of PHIs many of which may be thrown away shortly after their creation if jumps - were threaded through PHI nodes. + were threaded through PHI nodes. While our garbage collection mechanisms will handle this situation, it is extremely wasteful to create nodes and throw them away, especially @@ -46,12 +46,12 @@ Boston, MA 02111-1307, USA. */ Right now we maintain our free list on a per-function basis. It may or may not make sense to maintain the free list for the duration of - a compilation unit. + a compilation unit. We could also use a zone allocator for these objects since they have a very well defined lifetime. If someone wants to experiment with that this is the place to try it. - + PHI nodes have different sizes, so we can't have a single list of all the PHI nodes as it would be too expensive to walk down that list to find a PHI of a suitable size. @@ -71,7 +71,7 @@ Boston, MA 02111-1307, USA. */ be very expensive if the program has released a bunch of large PHI nodes, but keeps asking for even larger PHI nodes. Experiments have shown that walking the elements of the last array entry would result in finding less - than .1% additional reusable PHI nodes. + than .1% additional reusable PHI nodes. Note that we can never have less than two PHI argument slots. Thus, the -2 on all the calculations below. */ @@ -123,6 +123,47 @@ phinodes_print_statistics (void) } #endif +/* Allocate a PHI node with at least LEN arguments. If the free list + happens to contain a PHI node with LEN arguments or more, return + that one. */ + +static inline tree +allocate_phi_node (int len) +{ + tree phi; + int bucket = NUM_BUCKETS - 2; + int size = (sizeof (struct tree_phi_node) + + (len - 1) * sizeof (struct phi_arg_d)); + + if (free_phinode_count) + for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++) + if (free_phinodes[bucket]) + break; + + /* If our free list has an element, then use it. */ + if (bucket < NUM_BUCKETS - 2 + && PHI_ARG_CAPACITY (free_phinodes[bucket]) >= len) + { + free_phinode_count--; + phi = free_phinodes[bucket]; + free_phinodes[bucket] = PHI_CHAIN (free_phinodes[bucket]); +#ifdef GATHER_STATISTICS + phi_nodes_reused++; +#endif + } + else + { + phi = ggc_alloc (size); +#ifdef GATHER_STATISTICS + phi_nodes_created++; + tree_node_counts[(int) phi_kind]++; + tree_node_sizes[(int) phi_kind] += size; +#endif + } + + return phi; +} + /* Given LEN, the original number of requested PHI arguments, return a new, "ideal" length for the PHI node. The "ideal" length rounds the total size of the PHI node up to the next power of two bytes. @@ -149,63 +190,48 @@ ideal_phi_node_len (int len) /* Round it up to the next power of two. */ log2 = ceil_log2 (size); new_size = 1 << log2; - - /* Now compute and return the number of PHI argument slots given an + + /* Now compute and return the number of PHI argument slots given an ideal size allocation. */ new_len = len + (new_size - size) / sizeof (struct phi_arg_d); return new_len; } -/* Return a PHI node for variable VAR defined in statement STMT. - STMT may be an empty statement for artificial references (e.g., default - definitions created when a variable is used without a preceding - definition). */ -tree +/* Return a PHI node with LEN argument slots for variable VAR. */ + +static tree make_phi_node (tree var, int len) { tree phi; - int size; - int bucket = NUM_BUCKETS - 2; - - len = ideal_phi_node_len (len); + int capacity, i; - size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d); - - if (free_phinode_count) - for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++) - if (free_phinodes[bucket]) - break; - - /* If our free list has an element, then use it. */ - if (bucket < NUM_BUCKETS - 2 - && PHI_ARG_CAPACITY (free_phinodes[bucket]) >= len) - { - free_phinode_count--; - phi = free_phinodes[bucket]; - free_phinodes[bucket] = TREE_CHAIN (free_phinodes[bucket]); -#ifdef GATHER_STATISTICS - phi_nodes_reused++; -#endif - } - else - { - phi = ggc_alloc (size); -#ifdef GATHER_STATISTICS - phi_nodes_created++; - tree_node_counts[(int) phi_kind]++; - tree_node_sizes[(int) phi_kind] += size; -#endif + capacity = ideal_phi_node_len (len); - } + phi = allocate_phi_node (capacity); - memset (phi, 0, size); + /* We need to clear the entire PHI node, including the argument + portion, because we represent a "missing PHI argument" by placing + NULL_TREE in PHI_ARG_DEF. */ + memset (phi, 0, (sizeof (struct tree_phi_node) - sizeof (struct phi_arg_d) + + sizeof (struct phi_arg_d) * len)); TREE_SET_CODE (phi, PHI_NODE); - PHI_ARG_CAPACITY (phi) = len; + PHI_NUM_ARGS (phi) = len; + PHI_ARG_CAPACITY (phi) = capacity; if (TREE_CODE (var) == SSA_NAME) - PHI_RESULT (phi) = var; + SET_PHI_RESULT (phi, var); else - PHI_RESULT (phi) = make_ssa_name (var, phi); + SET_PHI_RESULT (phi, make_ssa_name (var, phi)); + + for (i = 0; i < capacity; i++) + { + use_operand_p imm; + imm = &(PHI_ARG_IMM_USE_NODE (phi, i)); + imm->use = &(PHI_ARG_DEF_TREE (phi, i)); + imm->prev = NULL; + imm->next = NULL; + imm->stmt = phi; + } return phi; } @@ -217,74 +243,106 @@ release_phi_node (tree phi) { int bucket; int len = PHI_ARG_CAPACITY (phi); + int x; + + for (x = 0; x < PHI_NUM_ARGS (phi); x++) + { + use_operand_p imm; + imm = &(PHI_ARG_IMM_USE_NODE (phi, x)); + delink_imm_use (imm); + } bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len; bucket -= 2; - TREE_CHAIN (phi) = free_phinodes[bucket]; + PHI_CHAIN (phi) = free_phinodes[bucket]; free_phinodes[bucket] = phi; free_phinode_count++; } /* Resize an existing PHI node. The only way is up. Return the possibly relocated phi. */ - + static void resize_phi_node (tree *phi, int len) { - int size, old_size; + int old_size, i; tree new_phi; - int i, old_len, bucket = NUM_BUCKETS - 2; - -#ifdef ENABLE_CHECKING - if (len < PHI_ARG_CAPACITY (*phi)) - abort (); -#endif - - /* Note that OLD_SIZE is guaranteed to be smaller than SIZE. */ + + gcc_assert (len > PHI_ARG_CAPACITY (*phi)); + + /* The garbage collector will not look at the PHI node beyond the + first PHI_NUM_ARGS elements. Therefore, all we have to copy is a + portion of the PHI node currently in use. */ old_size = (sizeof (struct tree_phi_node) - + (PHI_ARG_CAPACITY (*phi) - 1) * sizeof (struct phi_arg_d)); - size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d); + + (PHI_NUM_ARGS (*phi) - 1) * sizeof (struct phi_arg_d)); - if (free_phinode_count) - for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++) - if (free_phinodes[bucket]) - break; + new_phi = allocate_phi_node (len); - /* If our free list has an element, then use it. */ - if (bucket < NUM_BUCKETS - 2 - && PHI_ARG_CAPACITY (free_phinodes[bucket]) >= len) - { - free_phinode_count--; - new_phi = free_phinodes[bucket]; - free_phinodes[bucket] = TREE_CHAIN (free_phinodes[bucket]); -#ifdef GATHER_STATISTICS - phi_nodes_reused++; -#endif - } - else + memcpy (new_phi, *phi, old_size); + + for (i = 0; i < PHI_NUM_ARGS (new_phi); i++) { - new_phi = ggc_alloc (size); -#ifdef GATHER_STATISTICS - phi_nodes_created++; - tree_node_counts[(int) phi_kind]++; - tree_node_sizes[(int) phi_kind] += size; -#endif + use_operand_p imm, old_imm; + imm = &(PHI_ARG_IMM_USE_NODE (new_phi, i)); + old_imm = &(PHI_ARG_IMM_USE_NODE (*phi, i)); + imm->use = &(PHI_ARG_DEF_TREE (new_phi, i)); + relink_imm_use_stmt (imm, old_imm, new_phi); } - memcpy (new_phi, *phi, old_size); - - old_len = PHI_ARG_CAPACITY (new_phi); PHI_ARG_CAPACITY (new_phi) = len; - - for (i = old_len; i < len; i++) + + for (i = PHI_NUM_ARGS (new_phi); i < len; i++) { - PHI_ARG_DEF (new_phi, i) = NULL_TREE; - PHI_ARG_EDGE (new_phi, i) = NULL; + use_operand_p imm; + imm = &(PHI_ARG_IMM_USE_NODE (new_phi, i)); + imm->use = &(PHI_ARG_DEF_TREE (new_phi, i)); + imm->prev = NULL; + imm->next = NULL; + imm->stmt = new_phi; } *phi = new_phi; } +/* Reserve PHI arguments for a new edge to basic block BB. */ + +void +reserve_phi_args_for_new_edge (basic_block bb) +{ + tree *loc; + int len = EDGE_COUNT (bb->preds); + int cap = ideal_phi_node_len (len + 4); + + for (loc = phi_nodes_ptr (bb); + *loc; + loc = &PHI_CHAIN (*loc)) + { + if (len > PHI_ARG_CAPACITY (*loc)) + { + tree old_phi = *loc; + + resize_phi_node (loc, cap); + + /* The result of the phi is defined by this phi node. */ + SSA_NAME_DEF_STMT (PHI_RESULT (*loc)) = *loc; + + release_phi_node (old_phi); + } + + /* We represent a "missing PHI argument" by placing NULL_TREE in + the corresponding slot. If PHI arguments were added + immediately after an edge is created, this zeroing would not + be necessary, but unfortunately this is not the case. For + example, the loop optimizer duplicates several basic blocks, + redirects edges, and then fixes up PHI arguments later in + batch. */ + SET_PHI_ARG_DEF (*loc, len - 1, NULL_TREE); + + PHI_NUM_ARGS (*loc)++; + } +} + + /* Create a new PHI node for variable VAR at basic block BB. */ tree @@ -292,15 +350,11 @@ create_phi_node (tree var, basic_block bb) { tree phi; - phi = make_phi_node (var, bb_ann (bb)->num_preds); - - /* This is a new phi node, so note that is has not yet been - rewritten. */ - PHI_REWRITTEN (phi) = 0; + phi = make_phi_node (var, EDGE_COUNT (bb->preds)); /* Add the new PHI node to the list of PHI nodes for block BB. */ - TREE_CHAIN (phi) = phi_nodes (bb); - bb_ann (bb)->phi_nodes = phi; + PHI_CHAIN (phi) = phi_nodes (bb); + set_phi_nodes (bb, phi); /* Associate BB to the PHI node. */ set_bb_for_stmt (phi, bb); @@ -308,6 +362,7 @@ create_phi_node (tree var, basic_block bb) return phi; } + /* Add a new argument to PHI node PHI. DEF is the incoming reaching definition and E is the edge through which DEF reaches PHI. The new argument is added at the end of the argument list. @@ -315,210 +370,125 @@ create_phi_node (tree var, basic_block bb) PHI points to the reallocated phi node when we return. */ void -add_phi_arg (tree *phi, tree def, edge e) +add_phi_arg (tree phi, tree def, edge e) { - int i = PHI_NUM_ARGS (*phi); - - if (i >= PHI_ARG_CAPACITY (*phi)) - { - tree old_phi = *phi; - - /* Resize the phi. Unfortunately, this may also relocate it. */ - resize_phi_node (phi, ideal_phi_node_len (i + 4)); - - /* The result of the phi is defined by this phi node. */ - SSA_NAME_DEF_STMT (PHI_RESULT (*phi)) = *phi; - - /* If the PHI was relocated, update the PHI chains appropriately and - release the old PHI node. */ - if (*phi != old_phi) - { - release_phi_node (old_phi); - - /* Update the list head if replacing the first listed phi. */ - if (phi_nodes (e->dest) == old_phi) - bb_ann (e->dest)->phi_nodes = *phi; - else - { - /* Traverse the list looking for the phi node to chain to. */ - tree p; + basic_block bb = e->dest; - for (p = phi_nodes (e->dest); - p && TREE_CHAIN (p) != old_phi; - p = TREE_CHAIN (p)) - ; + gcc_assert (bb == bb_for_stmt (phi)); - if (!p) - abort (); + /* We resize PHI nodes upon edge creation. We should always have + enough room at this point. */ + gcc_assert (PHI_NUM_ARGS (phi) <= PHI_ARG_CAPACITY (phi)); - TREE_CHAIN (p) = *phi; - } - } - } + /* We resize PHI nodes upon edge creation. We should always have + enough room at this point. */ + gcc_assert (e->dest_idx < (unsigned int) PHI_NUM_ARGS (phi)); /* Copy propagation needs to know what object occur in abnormal PHI nodes. This is a convenient place to record such information. */ if (e->flags & EDGE_ABNORMAL) { SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1; - SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (*phi)) = 1; + SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1; } - PHI_ARG_DEF (*phi, i) = def; - PHI_ARG_EDGE (*phi, i) = e; - PHI_NUM_ARGS (*phi)++; + SET_PHI_ARG_DEF (phi, e->dest_idx, def); } -/* Remove a PHI argument from PHI. BLOCK is the predecessor block where - the PHI argument is coming from. */ -void -remove_phi_arg (tree phi, basic_block block) +/* Remove the Ith argument from PHI's argument list. This routine + implements removal by swapping the last alternative with the + alternative we want to delete and then shrinking the vector, which + is consistent with how we remove an edge from the edge vector. */ + +static void +remove_phi_arg_num (tree phi, int i) { - int i, num_elem = PHI_NUM_ARGS (phi); + int num_elem = PHI_NUM_ARGS (phi); - for (i = 0; i < num_elem; i++) - { - basic_block src_bb; + gcc_assert (i < num_elem); - src_bb = PHI_ARG_EDGE (phi, i)->src; + /* Delink the item which is being removed. */ + delink_imm_use (&(PHI_ARG_IMM_USE_NODE (phi, i))); - if (src_bb == block) - { - remove_phi_arg_num (phi, i); - return; - } + /* If it is not the last element, move the last element + to the element we want to delete, resetting all the links. */ + if (i != num_elem - 1) + { + use_operand_p old_p, new_p; + old_p = &PHI_ARG_IMM_USE_NODE (phi, num_elem - 1); + new_p = &PHI_ARG_IMM_USE_NODE (phi, i); + /* Set use on new node, and link into last element's place. */ + *(new_p->use) = *(old_p->use); + relink_imm_use (new_p, old_p); } + + /* Shrink the vector and return. Note that we do not have to clear + PHI_ARG_DEF because the garbage collector will not look at those + elements beyond the first PHI_NUM_ARGS elements of the array. */ + PHI_NUM_ARGS (phi)--; } -/* Remove the Ith argument from PHI's argument list. This routine assumes - ordering of alternatives in the vector is not important and implements - removal by swapping the last alternative with the alternative we want to - delete, then shrinking the vector. */ +/* Remove all PHI arguments associated with edge E. */ void -remove_phi_arg_num (tree phi, int i) +remove_phi_args (edge e) { - int num_elem = PHI_NUM_ARGS (phi); - - /* If we are not at the last element, switch the last element - with the element we want to delete. */ - if (i != num_elem - 1) - { - PHI_ARG_DEF (phi, i) = PHI_ARG_DEF (phi, num_elem - 1); - PHI_ARG_EDGE (phi, i) = PHI_ARG_EDGE (phi, num_elem - 1); - } - - /* Shrink the vector and return. */ - PHI_ARG_DEF (phi, num_elem - 1) = NULL_TREE; - PHI_ARG_EDGE (phi, num_elem - 1) = NULL; - PHI_NUM_ARGS (phi)--; + tree phi; - /* If we removed the last PHI argument, then go ahead and - remove the PHI node. */ - if (PHI_NUM_ARGS (phi) == 0) - remove_phi_node (phi, NULL, bb_for_stmt (phi)); + for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) + remove_phi_arg_num (phi, e->dest_idx); } + /* Remove PHI node PHI from basic block BB. If PREV is non-NULL, it is - used as the node immediately before PHI in the linked list. */ + used as the node immediately before PHI in the linked list. If + RELEASE_LHS_P is true, the LHS of this PHI node is released into + the free pool of SSA names. */ void -remove_phi_node (tree phi, tree prev, basic_block bb) +remove_phi_node (tree phi, tree prev, bool release_lhs_p) { + tree *loc; + if (prev) { - /* Rewire the list if we are given a PREV pointer. */ - TREE_CHAIN (prev) = TREE_CHAIN (phi); - - /* If we are deleting the PHI node, then we should release the - SSA_NAME node so that it can be reused. */ - release_ssa_name (PHI_RESULT (phi)); - release_phi_node (phi); - } - else if (phi == phi_nodes (bb)) - { - /* Update the list head if removing the first element. */ - bb_ann (bb)->phi_nodes = TREE_CHAIN (phi); - - /* If we are deleting the PHI node, then we should release the - SSA_NAME node so that it can be reused. */ - release_ssa_name (PHI_RESULT (phi)); - release_phi_node (phi); + loc = &PHI_CHAIN (prev); } else { - /* Traverse the list looking for the node to remove. */ - tree prev, t; - prev = NULL_TREE; - for (t = phi_nodes (bb); t && t != phi; t = TREE_CHAIN (t)) - prev = t; - if (t) - remove_phi_node (t, prev, bb); + for (loc = phi_nodes_ptr (bb_for_stmt (phi)); + *loc != phi; + loc = &PHI_CHAIN (*loc)) + ; } + + /* Remove PHI from the chain. */ + *loc = PHI_CHAIN (phi); + + /* If we are deleting the PHI node, then we should release the + SSA_NAME node so that it can be reused. */ + release_phi_node (phi); + if (release_lhs_p) + release_ssa_name (PHI_RESULT (phi)); } -/* Remove all the PHI nodes for variables in the VARS bitmap. */ +/* Reverse the order of PHI nodes in the chain PHI. + Return the new head of the chain (old last PHI node). */ -void -remove_all_phi_nodes_for (bitmap vars) +tree +phi_reverse (tree phi) { - basic_block bb; - - FOR_EACH_BB (bb) + tree prev = NULL_TREE, next; + for (; phi; phi = next) { - /* Build a new PHI list for BB without variables in VARS. */ - tree phi, new_phi_list, last_phi, next; - - last_phi = new_phi_list = NULL_TREE; - for (phi = phi_nodes (bb), next = NULL; phi; phi = next) - { - tree var = SSA_NAME_VAR (PHI_RESULT (phi)); - - next = TREE_CHAIN (phi); - /* Only add PHI nodes for variables not in VARS. */ - if (!bitmap_bit_p (vars, var_ann (var)->uid)) - { - /* If we're not removing this PHI node, then it must have - been rewritten by a previous call into the SSA rewriter. - Note that fact in PHI_REWRITTEN. */ - PHI_REWRITTEN (phi) = 1; - - if (new_phi_list == NULL_TREE) - new_phi_list = last_phi = phi; - else - { - TREE_CHAIN (last_phi) = phi; - last_phi = phi; - } - } - else - { - /* If we are deleting the PHI node, then we should release the - SSA_NAME node so that it can be reused. */ - release_ssa_name (PHI_RESULT (phi)); - release_phi_node (phi); - } - } - - /* Make sure the last node in the new list has no successors. */ - if (last_phi) - TREE_CHAIN (last_phi) = NULL_TREE; - bb_ann (bb)->phi_nodes = new_phi_list; - -#if defined ENABLE_CHECKING - for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) - { - tree var = SSA_NAME_VAR (PHI_RESULT (phi)); - if (bitmap_bit_p (vars, var_ann (var)->uid)) - abort (); - } -#endif + next = PHI_CHAIN (phi); + PHI_CHAIN (phi) = prev; + prev = phi; } + return prev; } - #include "gt-tree-phinodes.h" -