X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Ftree-phinodes.c;h=05b63fbea88708948b965175abfa1e16621416c2;hp=c4240e7cb69a157c0e60e65a22d9f47101c1f4f5;hb=2f1ce05cf95e354ae01c6801d32fb518f97fa593;hpb=1af6dc83bcc7707a772adb1d76d9484294e388c3 diff --git a/gcc/tree-phinodes.c b/gcc/tree-phinodes.c index c4240e7cb69..05b63fbea88 100644 --- a/gcc/tree-phinodes.c +++ b/gcc/tree-phinodes.c @@ -1,11 +1,11 @@ /* Generic routines for manipulating PHIs - Copyright (C) 2003 Free Software Foundation, Inc. + Copyright (C) 2003, 2005, 2007, 2008 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) +the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, @@ -14,21 +14,20 @@ 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. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" #include "coretypes.h" #include "tm.h" #include "tree.h" -#include "rtl.h" -#include "varray.h" +#include "rtl.h" /* FIXME: Only for ceil_log2, of all things... */ #include "ggc.h" #include "basic-block.h" #include "tree-flow.h" #include "toplev.h" +#include "gimple.h" /* 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 @@ -77,11 +76,10 @@ Boston, MA 02111-1307, USA. */ the -2 on all the calculations below. */ #define NUM_BUCKETS 10 -static GTY ((deletable (""))) tree free_phinodes[NUM_BUCKETS - 2]; +static GTY ((deletable (""))) VEC(gimple,gc) *free_phinodes[NUM_BUCKETS - 2]; static unsigned long free_phinode_count; static int ideal_phi_node_len (int); -static void resize_phi_node (tree *, int); #ifdef GATHER_STATISTICS unsigned int phi_nodes_reused; @@ -127,13 +125,13 @@ phinodes_print_statistics (void) happens to contain a PHI node with LEN arguments or more, return that one. */ -static inline tree -allocate_phi_node (int len) +static inline gimple +allocate_phi_node (size_t len) { - tree phi; - int bucket = NUM_BUCKETS - 2; - int size = (sizeof (struct tree_phi_node) - + (len - 1) * sizeof (struct phi_arg_d)); + gimple phi; + size_t bucket = NUM_BUCKETS - 2; + size_t size = sizeof (struct gimple_statement_phi) + + (len - 1) * sizeof (struct phi_arg_d); if (free_phinode_count) for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++) @@ -142,22 +140,27 @@ allocate_phi_node (int len) /* If our free list has an element, then use it. */ if (bucket < NUM_BUCKETS - 2 - && PHI_ARG_CAPACITY (free_phinodes[bucket]) >= len) + && gimple_phi_capacity (VEC_index (gimple, free_phinodes[bucket], 0)) + >= len) { free_phinode_count--; - phi = free_phinodes[bucket]; - free_phinodes[bucket] = PHI_CHAIN (free_phinodes[bucket]); + phi = VEC_pop (gimple, free_phinodes[bucket]); + if (VEC_empty (gimple, free_phinodes[bucket])) + VEC_free (gimple, gc, free_phinodes[bucket]); #ifdef GATHER_STATISTICS phi_nodes_reused++; #endif } else { - phi = ggc_alloc (size); + phi = ggc_alloc_gimple_statement_d (size); #ifdef GATHER_STATISTICS phi_nodes_created++; - tree_node_counts[(int) phi_kind]++; - tree_node_sizes[(int) phi_kind] += size; + { + enum gimple_alloc_kind kind = gimple_alloc_kind (GIMPLE_PHI); + gimple_alloc_counts[(int) kind]++; + gimple_alloc_sizes[(int) kind] += size; + } #endif } @@ -185,7 +188,8 @@ ideal_phi_node_len (int len) len = 2; /* Compute the number of bytes of the original request. */ - size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d); + size = sizeof (struct gimple_statement_phi) + + (len - 1) * sizeof (struct phi_arg_d); /* Round it up to the next power of two. */ log2 = ceil_log2 (size); @@ -197,33 +201,43 @@ ideal_phi_node_len (int len) 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). */ +/* Return a PHI node with LEN argument slots for variable VAR. */ -static tree +gimple make_phi_node (tree var, int len) { - tree phi; - - len = ideal_phi_node_len (len); - - phi = allocate_phi_node (len); - - /* We do not have to clear a part of the PHI node that stores PHI - arguments, which is safe because we tell the garbage collector to - scan up to num_args elements in the array of PHI arguments. In - other words, the garbage collector will not follow garbage - pointers in the unused portion of the array. */ - memset (phi, 0, sizeof (struct tree_phi_node) - sizeof (struct phi_arg_d)); - TREE_SET_CODE (phi, PHI_NODE); - PHI_ARG_CAPACITY (phi) = len; - TREE_TYPE (phi) = TREE_TYPE (var); + gimple phi; + int capacity, i; + + capacity = ideal_phi_node_len (len); + + phi = allocate_phi_node (capacity); + + /* 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 gimple_statement_phi) + - sizeof (struct phi_arg_d) + + sizeof (struct phi_arg_d) * len)); + phi->gsbase.code = GIMPLE_PHI; + phi->gimple_phi.nargs = len; + phi->gimple_phi.capacity = capacity; if (TREE_CODE (var) == SSA_NAME) - SET_PHI_RESULT (phi, var); + gimple_phi_set_result (phi, var); else - SET_PHI_RESULT (phi, make_ssa_name (var, phi)); + gimple_phi_set_result (phi, make_ssa_name (var, phi)); + + for (i = 0; i < capacity; i++) + { + use_operand_p imm; + + gimple_phi_arg_set_location (phi, i, UNKNOWN_LOCATION); + imm = gimple_phi_arg_imm_use_ptr (phi, i); + imm->use = gimple_phi_arg_def_ptr (phi, i); + imm->prev = NULL; + imm->next = NULL; + imm->loc.stmt = phi; + } return phi; } @@ -231,63 +245,141 @@ make_phi_node (tree var, int len) /* We no longer need PHI, release it so that it may be reused. */ void -release_phi_node (tree phi) +release_phi_node (gimple phi) { - int bucket; - int len = PHI_ARG_CAPACITY (phi); + size_t bucket; + size_t len = gimple_phi_capacity (phi); + size_t x; + + for (x = 0; x < gimple_phi_num_args (phi); x++) + { + use_operand_p imm; + imm = gimple_phi_arg_imm_use_ptr (phi, x); + delink_imm_use (imm); + } bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len; bucket -= 2; - PHI_CHAIN (phi) = free_phinodes[bucket]; - free_phinodes[bucket] = phi; + VEC_safe_push (gimple, gc, 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) +resize_phi_node (gimple *phi, size_t len) { - int old_size; - tree new_phi; + size_t old_size, i; + gimple new_phi; - gcc_assert (len >= PHI_ARG_CAPACITY (*phi)); + gcc_assert (len > gimple_phi_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_NUM_ARGS (*phi) - 1) * sizeof (struct phi_arg_d)); + old_size = sizeof (struct gimple_statement_phi) + + (gimple_phi_num_args (*phi) - 1) * sizeof (struct phi_arg_d); new_phi = allocate_phi_node (len); memcpy (new_phi, *phi, old_size); - PHI_ARG_CAPACITY (new_phi) = len; + for (i = 0; i < gimple_phi_num_args (new_phi); i++) + { + use_operand_p imm, old_imm; + imm = gimple_phi_arg_imm_use_ptr (new_phi, i); + old_imm = gimple_phi_arg_imm_use_ptr (*phi, i); + imm->use = gimple_phi_arg_def_ptr (new_phi, i); + relink_imm_use_stmt (imm, old_imm, new_phi); + } + + new_phi->gimple_phi.capacity = len; + + for (i = gimple_phi_num_args (new_phi); i < len; i++) + { + use_operand_p imm; + + gimple_phi_arg_set_location (new_phi, i, UNKNOWN_LOCATION); + imm = gimple_phi_arg_imm_use_ptr (new_phi, i); + imm->use = gimple_phi_arg_def_ptr (new_phi, i); + imm->prev = NULL; + imm->next = NULL; + imm->loc.stmt = new_phi; + } *phi = new_phi; } -/* Create a new PHI node for variable VAR at basic block BB. */ +/* Reserve PHI arguments for a new edge to basic block BB. */ -tree -create_phi_node (tree var, basic_block bb) +void +reserve_phi_args_for_new_edge (basic_block bb) { - tree phi; + size_t len = EDGE_COUNT (bb->preds); + size_t cap = ideal_phi_node_len (len + 4); + gimple_stmt_iterator gsi; + + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple *loc = gsi_stmt_ptr (&gsi); + + if (len > gimple_phi_capacity (*loc)) + { + gimple old_phi = *loc; + + resize_phi_node (loc, cap); + + /* The result of the PHI is defined by this PHI node. */ + SSA_NAME_DEF_STMT (gimple_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); + + (*loc)->gimple_phi.nargs++; + } +} - phi = make_phi_node (var, EDGE_COUNT (bb->preds)); +/* Adds PHI to BB. */ +void +add_phi_node_to_bb (gimple phi, basic_block bb) +{ + gimple_stmt_iterator gsi; /* Add the new PHI node to the list of PHI nodes for block BB. */ - PHI_CHAIN (phi) = phi_nodes (bb); - bb_ann (bb)->phi_nodes = phi; + if (phi_nodes (bb) == NULL) + set_phi_nodes (bb, gimple_seq_alloc ()); + + gsi = gsi_last (phi_nodes (bb)); + gsi_insert_after (&gsi, phi, GSI_NEW_STMT); /* Associate BB to the PHI node. */ - set_bb_for_stmt (phi, bb); + gimple_set_bb (phi, bb); +} + +/* Create a new PHI node for variable VAR at basic block BB. */ + +gimple +create_phi_node (tree var, basic_block bb) +{ + gimple phi = make_phi_node (var, EDGE_COUNT (bb->preds)); + + add_phi_node_to_bb (phi, 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. @@ -295,209 +387,115 @@ 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 (gimple phi, tree def, edge e, source_location locus) { basic_block bb = e->dest; - int i = PHI_NUM_ARGS (*phi); - gcc_assert (bb == bb_for_stmt (*phi)); + gcc_assert (bb == gimple_bb (phi)); - if (i >= PHI_ARG_CAPACITY (*phi)) - { - tree old_phi = *phi; - - /* Resize the phi. Unfortunately, this will relocate it. */ - resize_phi_node (phi, ideal_phi_node_len (i + 4)); - - /* resize_phi_node will necessarily relocate the phi. */ - gcc_assert (*phi != old_phi); + /* We resize PHI nodes upon edge creation. We should always have + enough room at this point. */ + gcc_assert (gimple_phi_num_args (phi) <= gimple_phi_capacity (phi)); - /* The result of the phi is defined by this phi node. */ - SSA_NAME_DEF_STMT (PHI_RESULT (*phi)) = *phi; - - release_phi_node (old_phi); - - /* Update the list head if replacing the first listed phi. */ - if (phi_nodes (bb) == old_phi) - bb_ann (bb)->phi_nodes = *phi; - else - { - /* Traverse the list looking for the phi node to chain to. */ - tree p; - - for (p = phi_nodes (bb); - p && PHI_CHAIN (p) != old_phi; - p = PHI_CHAIN (p)) - ; - - gcc_assert (p); - PHI_CHAIN (p) = *phi; - } - } + /* We resize PHI nodes upon edge creation. We should always have + enough room at this point. */ + gcc_assert (e->dest_idx < gimple_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; } - SET_PHI_ARG_DEF (*phi, i, def); - PHI_ARG_EDGE (*phi, i) = e; - PHI_ARG_NONZERO (*phi, i) = false; - PHI_NUM_ARGS (*phi)++; + SET_PHI_ARG_DEF (phi, e->dest_idx, def); + gimple_phi_arg_set_location (phi, e->dest_idx, locus); } -/* 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. */ -void -remove_phi_arg_num (tree phi, int i) +/* 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 (gimple phi, int i) { - int num_elem = PHI_NUM_ARGS (phi); + int num_elem = gimple_phi_num_args (phi); gcc_assert (i < num_elem); - /* If we are not at the last element, switch the last element - with the element we want to delete. */ + /* Delink the item which is being removed. */ + delink_imm_use (gimple_phi_arg_imm_use_ptr (phi, i)); + + /* 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) { - SET_PHI_ARG_DEF (phi, i, PHI_ARG_DEF (phi, num_elem - 1)); - PHI_ARG_EDGE (phi, i) = PHI_ARG_EDGE (phi, num_elem - 1); - PHI_ARG_NONZERO (phi, i) = PHI_ARG_NONZERO (phi, num_elem - 1); + use_operand_p old_p, new_p; + old_p = gimple_phi_arg_imm_use_ptr (phi, num_elem - 1); + new_p = gimple_phi_arg_imm_use_ptr (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); + /* Move the location as well. */ + gimple_phi_arg_set_location (phi, i, + gimple_phi_arg_location (phi, num_elem - 1)); } /* Shrink the vector and return. Note that we do not have to clear - PHI_ARG_DEF, PHI_ARG_EDGE, or PHI_ARG_NONZERO because the garbage - collector will not look at those elements beyond the first - PHI_NUM_ARGS elements of the array. */ - PHI_NUM_ARGS (phi)--; + PHI_ARG_DEF because the garbage collector will not look at those + elements beyond the first PHI_NUM_ARGS elements of the array. */ + phi->gimple_phi.nargs--; } + /* Remove all PHI arguments associated with edge E. */ void remove_phi_args (edge e) { - tree phi; + gimple_stmt_iterator gsi; - for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) - { - int index = phi_arg_from_edge (phi, e); - if (index >= 0) - remove_phi_arg_num (phi, index); - } + for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) + remove_phi_arg_num (gsi_stmt (gsi), 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. */ + +/* Remove the PHI node pointed-to by iterator GSI from basic block BB. After + removal, iterator GSI is updated to point to the next PHI node in the + sequence. 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 (gimple_stmt_iterator *gsi, bool release_lhs_p) { - if (prev) - { - /* Rewire the list if we are given a PREV pointer. */ - PHI_CHAIN (prev) = PHI_CHAIN (phi); + gimple phi = gsi_stmt (*gsi); - /* 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 = PHI_CHAIN (phi); + if (release_lhs_p) + insert_debug_temps_for_defs (gsi); - /* 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 - { - /* Traverse the list looking for the node to remove. */ - tree prev, t; - prev = NULL_TREE; - for (t = phi_nodes (bb); t && t != phi; t = PHI_CHAIN (t)) - prev = t; - if (t) - remove_phi_node (t, prev, bb); - } -} + gsi_remove (gsi, false); + /* 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 (gimple_phi_result (phi)); +} -/* Remove all the PHI nodes for variables in the VARS bitmap. */ +/* Remove all the phi nodes from BB. */ void -remove_all_phi_nodes_for (bitmap vars) +remove_phi_nodes (basic_block bb) { - basic_block bb; + gimple_stmt_iterator gsi; - FOR_EACH_BB (bb) - { - /* Build a new PHI list for BB without variables in VARS. */ - tree phi, new_phi_list, next; - tree *lastp = &new_phi_list; + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); ) + remove_phi_node (&gsi, true); - for (phi = phi_nodes (bb); phi; phi = next) - { - tree var = SSA_NAME_VAR (PHI_RESULT (phi)); - - next = PHI_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; - - *lastp = phi; - lastp = &PHI_CHAIN (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. */ - *lastp = NULL; - bb_ann (bb)->phi_nodes = new_phi_list; - -#if defined ENABLE_CHECKING - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - { - tree var = SSA_NAME_VAR (PHI_RESULT (phi)); - gcc_assert (!bitmap_bit_p (vars, var_ann (var)->uid)); - } -#endif - } -} - -/* Reverse the order of PHI nodes in the chain PHI. - Return the new head of the chain (old last PHI node). */ - -tree -phi_reverse (tree phi) -{ - tree prev = NULL_TREE, next; - for (; phi; phi = next) - { - next = PHI_CHAIN (phi); - PHI_CHAIN (phi) = prev; - prev = phi; - } - return prev; + set_phi_nodes (bb, NULL); } #include "gt-tree-phinodes.h" -