/* Control flow graph analysis code for GNU compiler.
- Copyright (C) 1987-2013 Free Software Foundation, Inc.
+ Copyright (C) 1987-2016 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "basic-block.h"
-#include "vec.h"
-#include "bitmap.h"
-#include "sbitmap.h"
+#include "backend.h"
+#include "cfghooks.h"
#include "timevar.h"
+#include "cfganal.h"
/* Store the data structures necessary for depth-first search. */
-struct depth_first_search_dsS {
+struct depth_first_search_ds {
/* stack for backtracking during the algorithm */
basic_block *stack;
/* record of basic blocks already seen by depth-first search */
sbitmap visited_blocks;
};
-typedef struct depth_first_search_dsS *depth_first_search_ds;
-static void flow_dfs_compute_reverse_init (depth_first_search_ds);
-static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds,
+static void flow_dfs_compute_reverse_init (depth_first_search_ds *);
+static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds *,
basic_block);
-static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds,
+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 void flow_dfs_compute_reverse_finish (depth_first_search_ds *);
\f
/* Mark the back edges in DFS traversal.
Return nonzero if a loop (natural or otherwise) is present.
bool found = false;
/* Allocate the preorder and postorder number arrays. */
- pre = XCNEWVEC (int, last_basic_block);
- post = XCNEWVEC (int, last_basic_block);
+ pre = XCNEWVEC (int, last_basic_block_for_fn (cfun));
+ post = XCNEWVEC (int, last_basic_block_for_fn (cfun));
/* Allocate stack for back-tracking up CFG. */
- stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
+ stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
- visited = sbitmap_alloc (last_basic_block);
+ visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
/* None of the nodes in the CFG have been visited yet. */
bitmap_clear (visited);
/* Push the first edge on to the stack. */
- stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
+ stack[sp++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
while (sp)
{
ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
/* Check if the edge destination has been visited yet. */
- if (dest != EXIT_BLOCK_PTR && ! bitmap_bit_p (visited, dest->index))
+ if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && ! bitmap_bit_p (visited,
+ dest->index))
{
/* Mark that we have visited the destination. */
bitmap_set_bit (visited, dest->index);
}
else
{
- if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
+ if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
+ && src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
&& pre[src->index] >= pre[dest->index]
&& post[dest->index] == 0)
ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true;
- if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
+ if (ei_one_before_end_p (ei)
+ && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
post[src->index] = postnum++;
if (!ei_one_before_end_p (ei))
edge_iterator ei;
basic_block *tos, *worklist, bb;
- tos = worklist = XNEWVEC (basic_block, n_basic_blocks);
+ tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
/* Clear all the reachability flags. */
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
bb->flags &= ~BB_REACHABLE;
/* Add our starting points to the worklist. Almost always there will
be only one. It isn't inconceivable that we might one day directly
support Fortran alternate entry points. */
- FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
+ FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
{
*tos++ = e->dest;
free (worklist);
}
+
+/* Verify that there are no unreachable blocks in the current function. */
+
+void
+verify_no_unreachable_blocks (void)
+{
+ find_unreachable_blocks ();
+
+ basic_block bb;
+ FOR_EACH_BB_FN (bb, cfun)
+ gcc_assert ((bb->flags & BB_REACHABLE) != 0);
+}
+
\f
/* Functions to access an edge list with a vector representation.
Enough data is kept such that given an index number, the
/* Determine the number of edges in the flow graph by counting successor
edges on each basic block. */
num_edges = 0;
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
+ EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
{
num_edges += EDGE_COUNT (bb->succs);
}
num_edges = 0;
/* Follow successors of blocks, and register these edges. */
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
+ EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
FOR_EACH_EDGE (e, ei, bb->succs)
elist->index_to_edge[num_edges++] = e;
int x;
fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
- n_basic_blocks, elist->num_edges);
+ n_basic_blocks_for_fn (cfun), elist->num_edges);
for (x = 0; x < elist->num_edges; x++)
{
fprintf (f, " %-4d - edge(", x);
- if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
+ if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
fprintf (f, "entry,");
else
fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
- if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
+ if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR_FOR_FN (cfun))
fprintf (f, "exit)\n");
else
fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
basic_block bb, p, s;
edge_iterator ei;
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
+ EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
{
FOR_EACH_EDGE (e, ei, bb->succs)
{
/* We've verified that all the edges are in the list, now lets make sure
there are no spurious edges in the list. This is an expensive check! */
- FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
- FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
+ FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR_FOR_FN (cfun),
+ EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
+ FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb)
{
int found_edge = 0;
control_dependences::set_control_dependence_map_bit (basic_block bb,
int edge_index)
{
- if (bb == ENTRY_BLOCK_PTR)
+ if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
return;
- gcc_assert (bb != EXIT_BLOCK_PTR);
+ gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
bitmap_set_bit (control_dependence_map[bb->index], edge_index);
}
static inline basic_block
find_pdom (basic_block block)
{
- gcc_assert (block != ENTRY_BLOCK_PTR);
+ gcc_assert (block != ENTRY_BLOCK_PTR_FOR_FN (cfun));
- if (block == EXIT_BLOCK_PTR)
- return EXIT_BLOCK_PTR;
+ if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
+ return EXIT_BLOCK_PTR_FOR_FN (cfun);
else
{
basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
if (! bb)
- return EXIT_BLOCK_PTR;
+ return EXIT_BLOCK_PTR_FOR_FN (cfun);
return bb;
}
}
basic_block current_block;
basic_block ending_block;
- gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
+ gcc_assert (INDEX_EDGE_PRED_BB (m_el, edge_index)
+ != EXIT_BLOCK_PTR_FOR_FN (cfun));
- if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
- ending_block = single_succ (ENTRY_BLOCK_PTR);
+ if (INDEX_EDGE_PRED_BB (m_el, edge_index) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
+ ending_block = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
else
- ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
+ ending_block = find_pdom (INDEX_EDGE_PRED_BB (m_el, edge_index));
- for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
- current_block != ending_block && current_block != EXIT_BLOCK_PTR;
+ for (current_block = INDEX_EDGE_SUCC_BB (m_el, edge_index);
+ current_block != ending_block
+ && current_block != EXIT_BLOCK_PTR_FOR_FN (cfun);
current_block = find_pdom (current_block))
{
- edge e = INDEX_EDGE (el, edge_index);
+ edge e = INDEX_EDGE (m_el, edge_index);
/* For abnormal edges, we don't make current_block control
dependent because instructions that throw are always necessary
list EL, ala Morgan, Section 3.6. */
control_dependences::control_dependences (struct edge_list *edges)
- : el (edges)
+ : m_el (edges)
{
timevar_push (TV_CONTROL_DEPENDENCES);
- control_dependence_map.create (last_basic_block);
- for (int i = 0; i < last_basic_block; ++i)
+ control_dependence_map.create (last_basic_block_for_fn (cfun));
+ for (int i = 0; i < last_basic_block_for_fn (cfun); ++i)
control_dependence_map.quick_push (BITMAP_ALLOC (NULL));
- for (int i = 0; i < NUM_EDGES (el); ++i)
+ for (int i = 0; i < NUM_EDGES (m_el); ++i)
find_control_dependence (i);
timevar_pop (TV_CONTROL_DEPENDENCES);
}
for (unsigned i = 0; i < control_dependence_map.length (); ++i)
BITMAP_FREE (control_dependence_map[i]);
control_dependence_map.release ();
- free_edge_list (el);
+ free_edge_list (m_el);
}
/* Returns the bitmap of edges the basic-block I is dependent on. */
edge
control_dependences::get_edge (int i)
{
- return INDEX_EDGE (el, i);
+ return INDEX_EDGE (m_el, i);
}
{
basic_block bb;
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb)
remove_fake_predecessors (bb);
}
void
remove_fake_exit_edges (void)
{
- remove_fake_predecessors (EXIT_BLOCK_PTR);
+ remove_fake_predecessors (EXIT_BLOCK_PTR_FOR_FN (cfun));
}
{
basic_block bb;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
if (EDGE_COUNT (bb->succs) == 0)
- make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
+ make_single_succ_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
}
/* This function adds a fake edge between any infinite loops to the
void
connect_infinite_loops_to_exit (void)
{
- basic_block unvisited_block = EXIT_BLOCK_PTR;
+ basic_block unvisited_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
basic_block deadend_block;
- struct depth_first_search_dsS dfs_ds;
+ depth_first_search_ds dfs_ds;
/* Perform depth-first search in the reverse graph to find nodes
reachable from the exit block. */
flow_dfs_compute_reverse_init (&dfs_ds);
- flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
+ flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR_FOR_FN (cfun));
/* Repeatedly add fake edges, updating the unreachable nodes. */
while (1)
break;
deadend_block = dfs_find_deadend (unvisited_block);
- make_edge (deadend_block, EXIT_BLOCK_PTR, EDGE_FAKE);
+ make_edge (deadend_block, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
flow_dfs_compute_reverse_add_bb (&dfs_ds, deadend_block);
}
post_order[post_order_num++] = EXIT_BLOCK;
/* Allocate stack for back-tracking up CFG. */
- stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
+ stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
- visited = sbitmap_alloc (last_basic_block);
+ visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
/* None of the nodes in the CFG have been visited yet. */
bitmap_clear (visited);
/* Push the first edge on to the stack. */
- stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
+ stack[sp++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
while (sp)
{
dest = ei_edge (ei)->dest;
/* Check if the edge destination has been visited yet. */
- if (dest != EXIT_BLOCK_PTR && ! bitmap_bit_p (visited, dest->index))
+ if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
+ && ! bitmap_bit_p (visited, dest->index))
{
/* Mark that we have visited the destination. */
bitmap_set_bit (visited, dest->index);
}
else
{
- if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
+ if (ei_one_before_end_p (ei)
+ && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
post_order[post_order_num++] = src->index;
if (!ei_one_before_end_p (ei))
/* Delete the unreachable blocks if some were found and we are
supposed to do it. */
- if (delete_unreachable && (count != n_basic_blocks))
+ if (delete_unreachable && (count != n_basic_blocks_for_fn (cfun)))
{
basic_block b;
basic_block next_bb;
- for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
+ for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b
+ != EXIT_BLOCK_PTR_FOR_FN (cfun); b = next_bb)
{
next_bb = b->next_bb;
(from successors to predecessors).
This ordering can be used for forward dataflow problems among others.
+ Optionally if START_POINTS is specified, start from exit block and all
+ basic blocks in START_POINTS. This is used by CD-DCE.
+
This function assumes that all blocks in the CFG are reachable
from the ENTRY (but not necessarily from EXIT).
and do another inverted traversal from that block. */
int
-inverted_post_order_compute (int *post_order)
+inverted_post_order_compute (int *post_order,
+ sbitmap *start_points)
{
basic_block bb;
edge_iterator *stack;
int post_order_num = 0;
sbitmap visited;
+ if (flag_checking)
+ verify_no_unreachable_blocks ();
+
/* Allocate stack for back-tracking up CFG. */
- stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
+ stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
- visited = sbitmap_alloc (last_basic_block);
+ visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
/* None of the nodes in the CFG have been visited yet. */
bitmap_clear (visited);
+ if (start_points)
+ {
+ FOR_ALL_BB_FN (bb, cfun)
+ if (bitmap_bit_p (*start_points, bb->index)
+ && EDGE_COUNT (bb->preds) > 0)
+ {
+ stack[sp++] = ei_start (bb->preds);
+ bitmap_set_bit (visited, bb->index);
+ }
+ if (EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds))
+ {
+ stack[sp++] = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
+ bitmap_set_bit (visited, EXIT_BLOCK_PTR_FOR_FN (cfun)->index);
+ }
+ }
+ else
/* Put all blocks that have no successor into the initial work list. */
- FOR_ALL_BB (bb)
+ FOR_ALL_BB_FN (bb, cfun)
if (EDGE_COUNT (bb->succs) == 0)
{
/* Push the initial edge on to the stack. */
}
else
{
- if (bb != EXIT_BLOCK_PTR && ei_one_before_end_p (ei))
+ if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
+ && ei_one_before_end_p (ei))
post_order[post_order_num++] = bb->index;
if (!ei_one_before_end_p (ei))
/* Detect any infinite loop and activate the kludge.
Note that this doesn't check EXIT_BLOCK itself
since EXIT_BLOCK is always added after the outer do-while loop. */
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
+ EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
if (!bitmap_bit_p (visited, bb->index))
{
has_unvisited_bb = true;
{
/* No blocks are reachable from EXIT at all.
Find a dead-end from the ENTRY, and restart the iteration. */
- basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR);
+ basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun));
gcc_assert (be != NULL);
bitmap_set_bit (visited, be->index);
stack[sp++] = ei_start (be->preds);
return post_order_num;
}
-/* Compute the depth first search order and store in the array
- PRE_ORDER if nonzero, marking the nodes visited in VISITED. If
- REV_POST_ORDER is nonzero, return the reverse completion number for each
- node. Returns the number of nodes visited. A depth first search
- tries to get as far away from the starting point as quickly as
- possible.
+/* Compute the depth first search order of FN and store in the array
+ PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the
+ reverse completion number for each node. Returns the number of nodes
+ visited. A depth first search tries to get as far away from the starting
+ point as quickly as possible.
- pre_order is a really a preorder numbering of the graph.
- rev_post_order is really a reverse postorder numbering of the graph.
- */
+ In case the function has unreachable blocks the number of nodes
+ visited does not include them.
+
+ pre_order is a really a preorder numbering of the graph.
+ rev_post_order is really a reverse postorder numbering of the graph. */
int
-pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
- bool include_entry_exit)
+pre_and_rev_post_order_compute_fn (struct function *fn,
+ int *pre_order, int *rev_post_order,
+ bool include_entry_exit)
{
edge_iterator *stack;
int sp;
int pre_order_num = 0;
- int rev_post_order_num = n_basic_blocks - 1;
+ int rev_post_order_num = n_basic_blocks_for_fn (cfun) - 1;
sbitmap visited;
/* Allocate stack for back-tracking up CFG. */
- stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
+ stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
sp = 0;
if (include_entry_exit)
pre_order[pre_order_num] = ENTRY_BLOCK;
pre_order_num++;
if (rev_post_order)
- rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
+ rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
}
else
rev_post_order_num -= NUM_FIXED_BLOCKS;
/* Allocate bitmap to track nodes that have been visited. */
- visited = sbitmap_alloc (last_basic_block);
+ visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
/* None of the nodes in the CFG have been visited yet. */
bitmap_clear (visited);
/* Push the first edge on to the stack. */
- stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
+ stack[sp++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn)->succs);
while (sp)
{
dest = ei_edge (ei)->dest;
/* Check if the edge destination has been visited yet. */
- if (dest != EXIT_BLOCK_PTR && ! bitmap_bit_p (visited, dest->index))
+ if (dest != EXIT_BLOCK_PTR_FOR_FN (fn)
+ && ! bitmap_bit_p (visited, dest->index))
{
/* Mark that we have visited the destination. */
bitmap_set_bit (visited, dest->index);
}
else
{
- if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
+ if (ei_one_before_end_p (ei)
+ && src != ENTRY_BLOCK_PTR_FOR_FN (fn)
&& rev_post_order)
/* There are no more successors for the SRC node
so assign its reverse completion number. */
pre_order[pre_order_num] = EXIT_BLOCK;
pre_order_num++;
if (rev_post_order)
- rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
- /* The number of nodes visited should be the number of blocks. */
- gcc_assert (pre_order_num == n_basic_blocks);
+ rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
}
+
+ return pre_order_num;
+}
+
+/* Like pre_and_rev_post_order_compute_fn but operating on the
+ current function and asserting that all nodes were visited. */
+
+int
+pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
+ bool include_entry_exit)
+{
+ int pre_order_num
+ = pre_and_rev_post_order_compute_fn (cfun, pre_order, rev_post_order,
+ include_entry_exit);
+ if (include_entry_exit)
+ /* The number of nodes visited should be the number of blocks. */
+ gcc_assert (pre_order_num == n_basic_blocks_for_fn (cfun));
else
/* The number of nodes visited should be the number of blocks minus
the entry and exit blocks which are not visited here. */
- gcc_assert (pre_order_num == n_basic_blocks - NUM_FIXED_BLOCKS);
+ gcc_assert (pre_order_num
+ == (n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS));
return pre_order_num;
}
element on the stack. */
static void
-flow_dfs_compute_reverse_init (depth_first_search_ds data)
+flow_dfs_compute_reverse_init (depth_first_search_ds *data)
{
/* Allocate stack for back-tracking up CFG. */
- data->stack = XNEWVEC (basic_block, n_basic_blocks);
+ data->stack = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
data->sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
- data->visited_blocks = sbitmap_alloc (last_basic_block);
+ data->visited_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
/* None of the nodes in the CFG have been visited yet. */
bitmap_clear (data->visited_blocks);
block. */
static void
-flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
+flow_dfs_compute_reverse_add_bb (depth_first_search_ds *data, basic_block bb)
{
data->stack[data->sp++] = bb;
bitmap_set_bit (data->visited_blocks, bb->index);
available. */
static basic_block
-flow_dfs_compute_reverse_execute (depth_first_search_ds data,
+flow_dfs_compute_reverse_execute (depth_first_search_ds *data,
basic_block last_unvisited)
{
basic_block bb;
reverse graph. */
static void
-flow_dfs_compute_reverse_finish (depth_first_search_ds data)
+flow_dfs_compute_reverse_finish (depth_first_search_ds *data)
{
free (data->stack);
sbitmap_free (data->visited_blocks);
#define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
/* Resize the VISITED sbitmap if necessary. */
- size = last_basic_block;
+ size = last_basic_block_for_fn (cfun);
if (size < 10)
size = 10;
edge p;
edge_iterator ei;
basic_block b;
- FOR_EACH_BB (b)
+ FOR_EACH_BB_FN (b, cfun)
{
if (EDGE_COUNT (b->preds) >= 2)
{
{
basic_block runner = p->src;
basic_block domsb;
- if (runner == ENTRY_BLOCK_PTR)
+ if (runner == ENTRY_BLOCK_PTR_FOR_FN (cfun))
continue;
domsb = get_immediate_dominator (CDI_DOMINATORS, b);
{
bitmap_iterator bi;
unsigned bb_index, i;
- vec<int> work_stack;
bitmap phi_insertion_points;
/* Each block can appear at most twice on the work-stack. */
- work_stack.create (2 * n_basic_blocks);
+ auto_vec<int> work_stack (2 * n_basic_blocks_for_fn (cfun));
phi_insertion_points = BITMAP_ALLOC (NULL);
/* Seed the work list with all the blocks in DEF_BLOCKS. We use
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_checking_assert (bb_index < (unsigned) last_basic_block);
+ gcc_checking_assert (bb_index
+ < (unsigned) last_basic_block_for_fn (cfun));
EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs[bb_index], phi_insertion_points,
0, i, bi)
}
}
- work_stack.release ();
-
return phi_insertion_points;
}
for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
{
e = EDGE_SUCC (b, ix);
- if (e->dest == EXIT_BLOCK_PTR)
+ if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
continue;
bitmap_copy (dst, src[e->dest->index]);
SBITMAP_ELT_TYPE *p, *r;
e = EDGE_SUCC (b, ix);
- if (e->dest == EXIT_BLOCK_PTR)
+ if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
continue;
p = src[e->dest->index]->elms;
for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
{
e = EDGE_PRED (b, ix);
- if (e->src == ENTRY_BLOCK_PTR)
+ if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
continue;
bitmap_copy (dst, src[e->src->index]);
SBITMAP_ELT_TYPE *p, *r;
e = EDGE_PRED (b, ix);
- if (e->src == ENTRY_BLOCK_PTR)
+ if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
continue;
p = src[e->src->index]->elms;
for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
{
e = EDGE_SUCC (b, ix);
- if (e->dest == EXIT_BLOCK_PTR)
+ if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
continue;
bitmap_copy (dst, src[e->dest->index]);
SBITMAP_ELT_TYPE *p, *r;
e = EDGE_SUCC (b, ix);
- if (e->dest == EXIT_BLOCK_PTR)
+ if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
continue;
p = src[e->dest->index]->elms;
for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
{
e = EDGE_PRED (b, ix);
- if (e->src== ENTRY_BLOCK_PTR)
+ if (e->src== ENTRY_BLOCK_PTR_FOR_FN (cfun))
continue;
bitmap_copy (dst, src[e->src->index]);
SBITMAP_ELT_TYPE *p, *r;
e = EDGE_PRED (b, ix);
- if (e->src == ENTRY_BLOCK_PTR)
+ if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
continue;
p = src[e->src->index]->elms;
*r++ |= *p++;
}
}
+
+/* Returns the list of basic blocks in the function in an order that guarantees
+ that if a block X has just a single predecessor Y, then Y is after X in the
+ ordering. */
+
+basic_block *
+single_pred_before_succ_order (void)
+{
+ basic_block x, y;
+ basic_block *order = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
+ unsigned n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
+ unsigned np, i;
+ sbitmap visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
+
+#define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
+#define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
+
+ bitmap_clear (visited);
+
+ MARK_VISITED (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+ FOR_EACH_BB_FN (x, cfun)
+ {
+ if (VISITED_P (x))
+ continue;
+
+ /* Walk the predecessors of x as long as they have precisely one
+ predecessor and add them to the list, so that they get stored
+ after x. */
+ for (y = x, np = 1;
+ single_pred_p (y) && !VISITED_P (single_pred (y));
+ y = single_pred (y))
+ np++;
+ for (y = x, i = n - np;
+ single_pred_p (y) && !VISITED_P (single_pred (y));
+ y = single_pred (y), i++)
+ {
+ order[i] = y;
+ MARK_VISITED (y);
+ }
+ order[i] = y;
+ MARK_VISITED (y);
+
+ gcc_assert (i == n - 1);
+ n -= np;
+ }
+
+ sbitmap_free (visited);
+ gcc_assert (n == 0);
+ return order;
+
+#undef MARK_VISITED
+#undef VISITED_P
+}