From 25e87727418263bb68dae17a2ec4e6b9e933e46a Mon Sep 17 00:00:00 2001 From: Steven Bosscher Date: Thu, 26 Jun 2008 20:06:49 +0000 Subject: [PATCH] cfganal.c: Include vec.h and vecprim.h. * cfganal.c: Include vec.h and vecprim.h. (compute_idf): Import from... * tree-into-ssa (compute_idf): ...here. * basic-block.h (compute_idf): Export. From-SVN: r137158 --- gcc/ChangeLog | 7 +++++ gcc/basic-block.h | 1 + gcc/cfganal.c | 63 +++++++++++++++++++++++++++++++++++++++++++++ gcc/tree-into-ssa.c | 60 ------------------------------------------ 4 files changed, 71 insertions(+), 60 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 52589586672..e175dddb7ef 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +2008-06-26 Steven Bosscher + + * cfganal.c: Include vec.h and vecprim.h. + (compute_idf): Import from... + * tree-into-ssa (compute_idf): ...here. + * basic-block.h (compute_idf): Export. + 2008-06-26 Joseph Myers * c-decl.c (merge_decls): Use !current_function_decl to check for diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 17ec338a7a4..4aa864d66cf 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -529,6 +529,7 @@ extern int dfs_enumerate_from (basic_block, int, bool (*)(const_basic_block, const void *), basic_block *, int, const void *); extern void compute_dominance_frontiers (bitmap *); +extern bitmap compute_idf (bitmap, bitmap *); extern void dump_bb_info (basic_block, bool, bool, int, const char *, FILE *); extern void dump_edge_info (FILE *, edge, int); extern void brief_dump_cfg (FILE *); diff --git a/gcc/cfganal.c b/gcc/cfganal.c index 66214d7fec6..663fbdcb6e4 100644 --- a/gcc/cfganal.c +++ b/gcc/cfganal.c @@ -31,6 +31,8 @@ along with GCC; see the file COPYING3. If not see #include "recog.h" #include "toplev.h" #include "tm_p.h" +#include "vec.h" +#include "vecprim.h" #include "timevar.h" /* Store the data structures necessary for depth-first search. */ @@ -1292,3 +1294,64 @@ compute_dominance_frontiers (bitmap *frontiers) timevar_pop (TV_DOM_FRONTIERS); } + +/* Given a set of blocks with variable definitions (DEF_BLOCKS), + return a bitmap with all the blocks in the iterated dominance + frontier of the blocks in DEF_BLOCKS. DFS contains dominance + frontier information as returned by compute_dominance_frontiers. + + The resulting set of blocks are the potential sites where PHI nodes + are needed. The caller is responsible for freeing the memory + allocated for the return value. */ + +bitmap +compute_idf (bitmap def_blocks, bitmap *dfs) +{ + bitmap_iterator bi; + unsigned bb_index, i; + VEC(int,heap) *work_stack; + bitmap phi_insertion_points; + + work_stack = VEC_alloc (int, heap, n_basic_blocks); + phi_insertion_points = BITMAP_ALLOC (NULL); + + /* Seed the work list with all the blocks in DEF_BLOCKS. We use + VEC_quick_push here for speed. This is safe because we know that + the number of definition blocks is no greater than the number of + basic blocks, which is the initial capacity of WORK_STACK. */ + EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi) + VEC_quick_push (int, work_stack, bb_index); + + /* Pop a block off the worklist, add every block that appears in + the original block's DF that we have not already processed to + the worklist. Iterate until the worklist is empty. Blocks + which are added to the worklist are potential sites for + PHI nodes. */ + while (VEC_length (int, work_stack) > 0) + { + bb_index = VEC_pop (int, work_stack); + + /* Since the registration of NEW -> OLD name mappings is done + separately from the call to update_ssa, when updating the SSA + form, the basic blocks where new and/or old names are defined + may have disappeared by CFG cleanup calls. In this case, + we may pull a non-existing block from the work stack. */ + gcc_assert (bb_index < (unsigned) last_basic_block); + + EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points, + 0, i, bi) + { + /* Use a safe push because if there is a definition of VAR + in every basic block, then WORK_STACK may eventually have + more than N_BASIC_BLOCK entries. */ + VEC_safe_push (int, heap, work_stack, i); + bitmap_set_bit (phi_insertion_points, i); + } + } + + VEC_free (int, heap, work_stack); + + return phi_insertion_points; +} + + diff --git a/gcc/tree-into-ssa.c b/gcc/tree-into-ssa.c index c0bebf73bf0..0eb2ded11b9 100644 --- a/gcc/tree-into-ssa.c +++ b/gcc/tree-into-ssa.c @@ -985,66 +985,6 @@ prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses) free (defs); } -/* Given a set of blocks with variable definitions (DEF_BLOCKS), - return a bitmap with all the blocks in the iterated dominance - frontier of the blocks in DEF_BLOCKS. DFS contains dominance - frontier information as returned by compute_dominance_frontiers. - - The resulting set of blocks are the potential sites where PHI nodes - are needed. The caller is responsible for freeing the memory - allocated for the return value. */ - -static bitmap -compute_idf (bitmap def_blocks, bitmap *dfs) -{ - bitmap_iterator bi; - unsigned bb_index, i; - VEC(int,heap) *work_stack; - bitmap phi_insertion_points; - - work_stack = VEC_alloc (int, heap, n_basic_blocks); - phi_insertion_points = BITMAP_ALLOC (NULL); - - /* Seed the work list with all the blocks in DEF_BLOCKS. We use - VEC_quick_push here for speed. This is safe because we know that - the number of definition blocks is no greater than the number of - basic blocks, which is the initial capacity of WORK_STACK. */ - EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi) - VEC_quick_push (int, work_stack, bb_index); - - /* Pop a block off the worklist, add every block that appears in - the original block's DF that we have not already processed to - the worklist. Iterate until the worklist is empty. Blocks - which are added to the worklist are potential sites for - PHI nodes. */ - while (VEC_length (int, work_stack) > 0) - { - bb_index = VEC_pop (int, work_stack); - - /* Since the registration of NEW -> OLD name mappings is done - separately from the call to update_ssa, when updating the SSA - form, the basic blocks where new and/or old names are defined - may have disappeared by CFG cleanup calls. In this case, - we may pull a non-existing block from the work stack. */ - gcc_assert (bb_index < (unsigned) last_basic_block); - - EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points, - 0, i, bi) - { - /* Use a safe push because if there is a definition of VAR - in every basic block, then WORK_STACK may eventually have - more than N_BASIC_BLOCK entries. */ - VEC_safe_push (int, heap, work_stack, i); - bitmap_set_bit (phi_insertion_points, i); - } - } - - VEC_free (int, heap, work_stack); - - return phi_insertion_points; -} - - /* Return the set of blocks where variable VAR is defined and the blocks where VAR is live on entry (livein). Return NULL, if no entry is found in DEF_BLOCKS. */ -- 2.30.2