/* Control flow graph analysis code for GNU compiler.
- Copyright (C) 1987-2017 Free Software Foundation, Inc.
+ Copyright (C) 1987-2018 Free Software Foundation, Inc.
This file is part of GCC.
#include "cfganal.h"
#include "cfgloop.h"
+namespace {
/* Store the data structures necessary for depth-first search. */
-struct depth_first_search_ds {
- /* stack for backtracking during the algorithm */
- basic_block *stack;
+class depth_first_search
+ {
+public:
+ depth_first_search ();
+
+ basic_block execute (basic_block);
+ void add_bb (basic_block);
- /* number of edges in the stack. That is, positions 0, ..., sp-1
- have edges. */
- unsigned int sp;
+private:
+ /* stack for backtracking during the algorithm */
+ auto_vec<basic_block, 20> m_stack;
/* record of basic blocks already seen by depth-first search */
- sbitmap visited_blocks;
+ auto_sbitmap m_visited_blocks;
};
-
-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 *,
- basic_block);
-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.
void
connect_infinite_loops_to_exit (void)
{
- basic_block unvisited_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
- basic_block deadend_block;
- 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_FOR_FN (cfun));
+ depth_first_search dfs;
+ dfs.add_bb (EXIT_BLOCK_PTR_FOR_FN (cfun));
/* Repeatedly add fake edges, updating the unreachable nodes. */
+ basic_block unvisited_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
while (1)
{
- unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds,
- unvisited_block);
+ unvisited_block = dfs.execute (unvisited_block);
if (!unvisited_block)
break;
- deadend_block = dfs_find_deadend (unvisited_block);
- make_edge (deadend_block, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
- flow_dfs_compute_reverse_add_bb (&dfs_ds, deadend_block);
+ basic_block deadend_block = dfs_find_deadend (unvisited_block);
+ edge e = make_edge (deadend_block, EXIT_BLOCK_PTR_FOR_FN (cfun),
+ EDGE_FAKE);
+ e->probability = profile_probability::never ();
+ dfs.add_bb (deadend_block);
}
-
- flow_dfs_compute_reverse_finish (&dfs_ds);
- return;
}
\f
/* Compute reverse top sort order. This is computing a post order
basic_block
dfs_find_deadend (basic_block bb)
{
- bitmap visited = BITMAP_ALLOC (NULL);
+ auto_bitmap visited;
+ basic_block next = bb;
for (;;)
{
- if (EDGE_COUNT (bb->succs) == 0
- || ! bitmap_set_bit (visited, bb->index))
- {
- BITMAP_FREE (visited);
- return bb;
- }
+ if (EDGE_COUNT (next->succs) == 0)
+ return next;
+
+ if (! bitmap_set_bit (visited, next->index))
+ return bb;
+ bb = next;
/* If we are in an analyzed cycle make sure to try exiting it.
Note this is a heuristic only and expected to work when loop
fixup is needed as well. */
if (! bb->loop_father
|| ! loop_outer (bb->loop_father))
- bb = EDGE_SUCC (bb, 0)->dest;
+ next = EDGE_SUCC (bb, 0)->dest;
else
{
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
if (loop_exit_edge_p (bb->loop_father, e))
break;
- bb = e ? e->dest : EDGE_SUCC (bb, 0)->dest;
+ next = e ? e->dest : EDGE_SUCC (bb, 0)->dest;
}
}
and start looking for a "dead end" from that block
and do another inverted traversal from that block. */
-int
-inverted_post_order_compute (int *post_order,
+void
+inverted_post_order_compute (vec<int> *post_order,
sbitmap *start_points)
{
basic_block bb;
- int post_order_num = 0;
+ post_order->reserve_exact (n_basic_blocks_for_fn (cfun));
if (flag_checking)
verify_no_unreachable_blocks ();
time, check its predecessors. */
stack.quick_push (ei_start (pred->preds));
else
- post_order[post_order_num++] = pred->index;
+ post_order->quick_push (pred->index);
}
else
{
if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
&& ei_one_before_end_p (ei))
- post_order[post_order_num++] = bb->index;
+ post_order->quick_push (bb->index);
if (!ei_one_before_end_p (ei))
ei_next (&stack.last ());
while (!stack.is_empty ());
/* EXIT_BLOCK is always included. */
- post_order[post_order_num++] = EXIT_BLOCK;
-
- return post_order_num;
+ post_order->quick_push (EXIT_BLOCK);
}
/* Compute the depth first search order of FN and store in the array
search context. If INITIALIZE_STACK is nonzero, there is an
element on the stack. */
-static void
-flow_dfs_compute_reverse_init (depth_first_search_ds *data)
+depth_first_search::depth_first_search () :
+ m_stack (n_basic_blocks_for_fn (cfun)),
+ m_visited_blocks (last_basic_block_for_fn (cfun))
{
- /* Allocate stack for back-tracking up CFG. */
- 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_for_fn (cfun));
-
- /* None of the nodes in the CFG have been visited yet. */
- bitmap_clear (data->visited_blocks);
-
- return;
+ bitmap_clear (m_visited_blocks);
}
/* Add the specified basic block to the top of the dfs data
structures. When the search continues, it will start at the
block. */
-static void
-flow_dfs_compute_reverse_add_bb (depth_first_search_ds *data, basic_block bb)
+void
+depth_first_search::add_bb (basic_block bb)
{
- data->stack[data->sp++] = bb;
- bitmap_set_bit (data->visited_blocks, bb->index);
+ m_stack.quick_push (bb);
+ bitmap_set_bit (m_visited_blocks, bb->index);
}
/* Continue the depth-first search through the reverse graph starting with the
are marked. Returns an unvisited basic block, or NULL if there is none
available. */
-static basic_block
-flow_dfs_compute_reverse_execute (depth_first_search_ds *data,
- basic_block last_unvisited)
+basic_block
+depth_first_search::execute (basic_block last_unvisited)
{
basic_block bb;
edge e;
edge_iterator ei;
- while (data->sp > 0)
+ while (!m_stack.is_empty ())
{
- bb = data->stack[--data->sp];
+ bb = m_stack.pop ();
/* Perform depth-first search on adjacent vertices. */
FOR_EACH_EDGE (e, ei, bb->preds)
- if (!bitmap_bit_p (data->visited_blocks, e->src->index))
- flow_dfs_compute_reverse_add_bb (data, e->src);
+ if (!bitmap_bit_p (m_visited_blocks, e->src->index))
+ add_bb (e->src);
}
/* Determine if there are unvisited basic blocks. */
FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
- if (!bitmap_bit_p (data->visited_blocks, bb->index))
+ if (!bitmap_bit_p (m_visited_blocks, bb->index))
return bb;
return NULL;
}
-/* Destroy the data structures needed for depth-first search on the
- reverse graph. */
-
-static void
-flow_dfs_compute_reverse_finish (depth_first_search_ds *data)
-{
- free (data->stack);
- sbitmap_free (data->visited_blocks);
-}
-
/* Performs dfs search from BB over vertices satisfying PREDICATE;
if REVERSE, go against direction of edges. Returns number of blocks
found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
#undef MARK_VISITED
#undef VISITED_P
}
+
+/* Ignoring loop backedges, if BB has precisely one incoming edge then
+ return that edge. Otherwise return NULL.
+
+ When IGNORE_NOT_EXECUTABLE is true, also ignore edges that are not marked
+ as executable. */
+
+edge
+single_pred_edge_ignoring_loop_edges (basic_block bb,
+ bool ignore_not_executable)
+{
+ edge retval = NULL;
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ /* A loop back edge can be identified by the destination of
+ the edge dominating the source of the edge. */
+ if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
+ continue;
+
+ /* We can safely ignore edges that are not executable. */
+ if (ignore_not_executable
+ && (e->flags & EDGE_EXECUTABLE) == 0)
+ continue;
+
+ /* If we have already seen a non-loop edge, then we must have
+ multiple incoming non-loop edges and thus we return NULL. */
+ if (retval)
+ return NULL;
+
+ /* This is the first non-loop incoming edge we have found. Record
+ it. */
+ retval = e;
+ }
+
+ return retval;
+}
projects / gcc.git / blobdiff