/* 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.
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"
}
#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.
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;
+ int capacity, i;
- len = ideal_phi_node_len (len);
+ capacity = ideal_phi_node_len (len);
- size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d);
+ phi = allocate_phi_node (capacity);
- 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
-
- }
-
- 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;
TREE_TYPE (phi) = TREE_TYPE (var);
if (TREE_CODE (var) == SSA_NAME)
SET_PHI_RESULT (phi, var);
else
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;
}
{
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;
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;
- gcc_assert (len >= PHI_ARG_CAPACITY (*phi));
+ gcc_assert (len > PHI_ARG_CAPACITY (*phi));
- /* Note that OLD_SIZE is guaranteed to be smaller than SIZE. */
+ /* 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] = PHI_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++)
{
- SET_PHI_ARG_DEF (new_phi, i, NULL_TREE);
- PHI_ARG_EDGE (new_phi, i) = NULL;
- PHI_ARG_NONZERO (new_phi, i) = false;
+ 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 = &(bb->phi_nodes);
+ *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
phi = make_phi_node (var, EDGE_COUNT (bb->preds));
- /* This is a new phi node, so note that is has not yet been
- rewritten. */
- PHI_REWRITTEN (phi) = 0;
-
/* 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;
+ bb->phi_nodes = phi;
/* Associate BB to the PHI node. */
set_bb_for_stmt (phi, 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;
- basic_block bb;
+ basic_block bb = e->dest;
- /* Resize the phi. Unfortunately, this will relocate it. */
- resize_phi_node (phi, ideal_phi_node_len (i + 4));
+ gcc_assert (bb == bb_for_stmt (phi));
- /* 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 (PHI_NUM_ARGS (phi) <= PHI_ARG_CAPACITY (phi));
- /* The result of the phi is defined by this phi node. */
- SSA_NAME_DEF_STMT (PHI_RESULT (*phi)) = *phi;
-
- /* Extract the basic block for the PHI from the PHI's annotation
- rather than the edge. This works better as the edge's
- destination may not currently be the block with the PHI node
- if we are in the process of threading the edge to a new
- destination. */
- bb = bb_for_stmt (*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 < (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;
}
- SET_PHI_ARG_DEF (*phi, i, def);
- PHI_ARG_EDGE (*phi, i) = e;
- PHI_ARG_NONZERO (*phi, i) = false;
- PHI_NUM_ARGS (*phi)++;
-}
-
-/* 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)
-{
- int i, num_elem = PHI_NUM_ARGS (phi);
-
- for (i = 0; i < num_elem; i++)
- {
- basic_block src_bb;
-
- src_bb = PHI_ARG_EDGE (phi, i)->src;
-
- if (src_bb == block)
- {
- remove_phi_arg_num (phi, i);
- return;
- }
- }
+ SET_PHI_ARG_DEF (phi, e->dest_idx, def);
}
+/* 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. */
-/* 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
+static void
remove_phi_arg_num (tree phi, int i)
{
int num_elem = PHI_NUM_ARGS (phi);
gcc_assert (i < num_elem);
+ /* Delink the last item, which is being removed. */
+ delink_imm_use (&(PHI_ARG_IMM_USE_NODE (phi, num_elem - 1)));
+
/* If we are not at the last element, switch the last element
with the element we want to delete. */
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);
}
- /* Shrink the vector and return. */
- SET_PHI_ARG_DEF (phi, num_elem - 1, NULL_TREE);
- PHI_ARG_EDGE (phi, num_elem - 1) = NULL;
- PHI_ARG_NONZERO (phi, num_elem - 1) = false;
+ /* 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 all PHI arguments associated with edge E. */
+
+void
+remove_phi_args (edge e)
+{
+ tree 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. */
void
-remove_phi_node (tree phi, tree prev, basic_block bb)
+remove_phi_node (tree phi, tree prev)
{
- if (prev)
- {
- /* Rewire the list if we are given a PREV pointer. */
- PHI_CHAIN (prev) = PHI_CHAIN (phi);
+ tree *loc;
- /* 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))
+ if (prev)
{
- /* Update the list head if removing the first element. */
- bb_ann (bb)->phi_nodes = 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_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 = PHI_CHAIN (t))
- prev = t;
- if (t)
- remove_phi_node (t, prev, bb);
+ for (loc = &(bb_for_stmt (phi)->phi_nodes);
+ *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);
+ 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 = 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;
-
- if (new_phi_list == NULL_TREE)
- new_phi_list = last_phi = phi;
- else
- {
- PHI_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)
- PHI_CHAIN (last_phi) = NULL_TREE;
- 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
+ next = PHI_CHAIN (phi);
+ PHI_CHAIN (phi) = prev;
+ prev = phi;
}
+ return prev;
}
-
#include "gt-tree-phinodes.h"
-
OSDN Git Service
