/* Generic dominator tree walker
- Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
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,
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
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
which reduces code duplication since the rewriting phase is inherently
a walk of the dominator tree.
- And (of course), we use the dominator walker to drive a our dominator
+ And (of course), we use the dominator walker to drive our dominator
optimizer, which is a semi-global optimizer.
TODO:
basic_block dest;
block_stmt_iterator bsi;
bool is_interesting;
+ basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2);
+ int sp = 0;
- /* If block BB is not interesting to the caller, then none of the
- callbacks that walk the statements in BB are going to be
- executed. */
- is_interesting = bb->index < 0
- || walk_data->interesting_blocks == NULL
- || TEST_BIT (walk_data->interesting_blocks, bb->index);
-
- /* Callback to initialize the local data structure. */
- if (walk_data->initialize_block_local_data)
+ while (true)
{
- bool recycled;
-
- /* First get some local data, reusing any local data pointer we may
- have saved. */
- if (VARRAY_ACTIVE_SIZE (walk_data->free_block_data) > 0)
+ /* Don't worry about unreachable blocks. */
+ if (EDGE_COUNT (bb->preds) > 0
+ || bb == ENTRY_BLOCK_PTR
+ || bb == EXIT_BLOCK_PTR)
{
- bd = VARRAY_TOP_GENERIC_PTR (walk_data->free_block_data);
- VARRAY_POP (walk_data->free_block_data);
- recycled = 1;
+ /* If block BB is not interesting to the caller, then none of the
+ callbacks that walk the statements in BB are going to be
+ executed. */
+ is_interesting = walk_data->interesting_blocks == NULL
+ || TEST_BIT (walk_data->interesting_blocks,
+ bb->index);
+
+ /* Callback to initialize the local data structure. */
+ if (walk_data->initialize_block_local_data)
+ {
+ bool recycled;
+
+ /* First get some local data, reusing any local data pointer we may
+ have saved. */
+ if (VEC_length (void_p, walk_data->free_block_data) > 0)
+ {
+ bd = VEC_pop (void_p, walk_data->free_block_data);
+ recycled = 1;
+ }
+ else
+ {
+ bd = xcalloc (1, walk_data->block_local_data_size);
+ recycled = 0;
+ }
+
+ /* Push the local data into the local data stack. */
+ VEC_safe_push (void_p, heap, walk_data->block_data_stack, bd);
+
+ /* Call the initializer. */
+ walk_data->initialize_block_local_data (walk_data, bb,
+ recycled);
+
+ }
+
+ /* Callback for operations to execute before we have walked the
+ dominator children, but before we walk statements. */
+ if (walk_data->before_dom_children_before_stmts)
+ (*walk_data->before_dom_children_before_stmts) (walk_data, bb);
+
+ /* Statement walk before walking dominator children. */
+ if (is_interesting && walk_data->before_dom_children_walk_stmts)
+ {
+ if (walk_data->walk_stmts_backward)
+ for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
+ (*walk_data->before_dom_children_walk_stmts) (walk_data, bb,
+ bsi);
+ else
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ (*walk_data->before_dom_children_walk_stmts) (walk_data, bb,
+ bsi);
+ }
+
+ /* Callback for operations to execute before we have walked the
+ dominator children, and after we walk statements. */
+ if (walk_data->before_dom_children_after_stmts)
+ (*walk_data->before_dom_children_after_stmts) (walk_data, bb);
+
+ /* Mark the current BB to be popped out of the recursion stack
+ once childs are processed. */
+ worklist[sp++] = bb;
+ worklist[sp++] = NULL;
+
+ for (dest = first_dom_son (walk_data->dom_direction, bb);
+ dest; dest = next_dom_son (walk_data->dom_direction, dest))
+ worklist[sp++] = dest;
}
- else
+ /* NULL is used to signalize pop operation in recursion stack. */
+ while (sp > 0 && !worklist[sp - 1])
{
- bd = xcalloc (1, walk_data->block_local_data_size);
- recycled = 0;
+ --sp;
+ bb = worklist[--sp];
+ is_interesting = walk_data->interesting_blocks == NULL
+ || TEST_BIT (walk_data->interesting_blocks,
+ bb->index);
+ /* Callback for operations to execute after we have walked the
+ dominator children, but before we walk statements. */
+ if (walk_data->after_dom_children_before_stmts)
+ (*walk_data->after_dom_children_before_stmts) (walk_data, bb);
+
+ /* Statement walk after walking dominator children. */
+ if (is_interesting && walk_data->after_dom_children_walk_stmts)
+ {
+ if (walk_data->walk_stmts_backward)
+ for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
+ (*walk_data->after_dom_children_walk_stmts) (walk_data, bb,
+ bsi);
+ else
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ (*walk_data->after_dom_children_walk_stmts) (walk_data, bb,
+ bsi);
+ }
+
+ /* Callback for operations to execute after we have walked the
+ dominator children and after we have walked statements. */
+ if (walk_data->after_dom_children_after_stmts)
+ (*walk_data->after_dom_children_after_stmts) (walk_data, bb);
+
+ if (walk_data->initialize_block_local_data)
+ {
+ /* And finally pop the record off the block local data stack. */
+ bd = VEC_pop (void_p, walk_data->block_data_stack);
+ /* And save the block data so that we can re-use it. */
+ VEC_safe_push (void_p, heap, walk_data->free_block_data, bd);
+ }
}
-
- /* Push the local data into the local data stack. */
- VARRAY_PUSH_GENERIC_PTR (walk_data->block_data_stack, bd);
-
- /* Call the initializer. */
- walk_data->initialize_block_local_data (walk_data, bb, recycled);
-
- }
-
- /* Callback for operations to execute before we have walked the
- dominator children, but before we walk statements. */
- if (walk_data->before_dom_children_before_stmts)
- (*walk_data->before_dom_children_before_stmts) (walk_data, bb);
-
- /* Statement walk before walking dominator children. */
- if (is_interesting && walk_data->before_dom_children_walk_stmts)
- {
- if (walk_data->walk_stmts_backward)
- for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
- (*walk_data->before_dom_children_walk_stmts) (walk_data, bb, bsi);
- else
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- (*walk_data->before_dom_children_walk_stmts) (walk_data, bb, bsi);
- }
-
- /* Callback for operations to execute before we have walked the
- dominator children, and after we walk statements. */
- if (walk_data->before_dom_children_after_stmts)
- (*walk_data->before_dom_children_after_stmts) (walk_data, bb);
-
- /* Recursively call ourselves on the dominator children of BB. */
- for (dest = first_dom_son (walk_data->dom_direction, bb);
- dest;
- dest = next_dom_son (walk_data->dom_direction, dest))
- {
- /* The destination block may have become unreachable, in
- which case there's no point in optimizing it. */
- if (EDGE_COUNT (dest->preds) > 0)
- walk_dominator_tree (walk_data, dest);
- }
-
- /* Callback for operations to execute after we have walked the
- dominator children, but before we walk statements. */
- if (walk_data->after_dom_children_before_stmts)
- (*walk_data->after_dom_children_before_stmts) (walk_data, bb);
-
- /* Statement walk after walking dominator children. */
- if (is_interesting && walk_data->after_dom_children_walk_stmts)
- {
- if (walk_data->walk_stmts_backward)
- for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
- (*walk_data->after_dom_children_walk_stmts) (walk_data, bb, bsi);
+ if (sp)
+ bb = worklist[--sp];
else
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- (*walk_data->after_dom_children_walk_stmts) (walk_data, bb, bsi);
- }
-
- /* Callback for operations to execute after we have walked the
- dominator children and after we have walked statements. */
- if (walk_data->after_dom_children_after_stmts)
- (*walk_data->after_dom_children_after_stmts) (walk_data, bb);
-
- if (walk_data->initialize_block_local_data)
- {
- /* And save the block data so that we can re-use it. */
- VARRAY_PUSH_GENERIC_PTR (walk_data->free_block_data, bd);
-
- /* And finally pop the record off the block local data stack. */
- VARRAY_POP (walk_data->block_data_stack);
+ break;
}
+ free (worklist);
}
void
init_walk_dominator_tree (struct dom_walk_data *walk_data)
{
- if (walk_data->initialize_block_local_data)
- {
- VARRAY_GENERIC_PTR_INIT (walk_data->free_block_data, 2, "freelist ");
- VARRAY_GENERIC_PTR_INIT (walk_data->block_data_stack, 2, "block_data");
- }
- else
- {
- walk_data->free_block_data = NULL;
- walk_data->block_data_stack = NULL;
- }
+ walk_data->free_block_data = NULL;
+ walk_data->block_data_stack = NULL;
}
void
{
if (walk_data->initialize_block_local_data)
{
- while (VARRAY_ACTIVE_SIZE (walk_data->free_block_data) > 0)
- {
- free (VARRAY_TOP_GENERIC_PTR (walk_data->free_block_data));
- VARRAY_POP (walk_data->free_block_data);
- }
+ while (VEC_length (void_p, walk_data->free_block_data) > 0)
+ free (VEC_pop (void_p, walk_data->free_block_data));
}
+
+ VEC_free (void_p, heap, walk_data->free_block_data);
+ VEC_free (void_p, heap, walk_data->block_data_stack);
}
OSDN Git Service
