/* Control flow graph analysis code for GNU compiler.
Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
+ 1999, 2000, 2001, 2003, 2004, 2005, 2006, 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) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
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, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
/* This file contains various simple utilities to analyze the CFG. */
#include "config.h"
#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. */
static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds,
basic_block);
static void flow_dfs_compute_reverse_finish (depth_first_search_ds);
-static bool flow_active_insn_p (rtx);
+static bool flow_active_insn_p (const_rtx);
\f
/* Like active_insn_p, except keep the return value clobber around
even after reload. */
static bool
-flow_active_insn_p (rtx insn)
+flow_active_insn_p (const_rtx insn)
{
if (active_insn_p (insn))
return true;
its single destination. */
bool
-forwarder_block_p (basic_block bb)
+forwarder_block_p (const_basic_block bb)
{
rtx insn;
/* Dump the list of basic blocks in the bitmap NODES. */
void
-flow_nodes_print (const char *str, const sbitmap nodes, FILE *file)
+flow_nodes_print (const char *str, const_sbitmap nodes, FILE *file)
{
unsigned int node = 0;
sbitmap_iterator sbi;
found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
int
dfs_enumerate_from (basic_block bb, int reverse,
- bool (*predicate) (basic_block, void *),
- basic_block *rslt, int rslt_max, void *data)
+ bool (*predicate) (const_basic_block, const void *),
+ basic_block *rslt, int rslt_max, const void *data)
{
basic_block *st, lbb;
int sp = 0, tv = 0;
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;
+}
+
+
OSDN Git Service
