X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fdomwalk.c;h=b70a807e7a454a99f9538d7ad451edd4fd9a1484;hb=d0aaf3990d011abe5d7c65905f240a60d2fdccb6;hp=15b1dff82dbfc2c755d921a9cd212e4c05e09dc9;hpb=cd665a06e2398f370313e6ec3df029d06e9dfffe;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/domwalk.c b/gcc/domwalk.c index 15b1dff82db..b70a807e7a4 100644 --- a/gcc/domwalk.c +++ b/gcc/domwalk.c @@ -1,12 +1,13 @@ /* Generic dominator tree walker - Copyright (C) 2003, 2004 Free Software Foundation, Inc. + Copyright (C) 2003, 2004, 2005, 2007, 2008 Free Software Foundation, + Inc. Contributed by Diego Novillo 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, @@ -15,17 +16,14 @@ 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 "basic-block.h" -#include "tree-flow.h" #include "domwalk.h" #include "ggc.h" @@ -122,7 +120,7 @@ Boston, MA 02111-1307, USA. */ 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: @@ -144,111 +142,89 @@ walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) { void *bd = NULL; basic_block dest; - block_stmt_iterator bsi; + basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2); + int sp = 0; - /* 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; + /* 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) + (*walk_data->before_dom_children) (walk_data, bb); + + /* Mark the current BB to be popped out of the recursion stack + once children 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 mark pop operations in the recursion stack. */ + while (sp > 0 && !worklist[sp - 1]) { - bd = xcalloc (1, walk_data->block_local_data_size); - recycled = 0; + --sp; + bb = worklist[--sp]; + + /* Callback for operations to execute after we have walked the + dominator children, but before we walk statements. */ + if (walk_data->after_dom_children) + (*walk_data->after_dom_children) (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 (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); + if (sp) + bb = worklist[--sp]; 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 (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 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 @@ -256,10 +232,10 @@ fini_walk_dominator_tree (struct dom_walk_data *walk_data) { 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); }