/* Control flow graph analysis code for GNU compiler.
- Copyright (C) 1987-2013 Free Software Foundation, Inc.
+ Copyright (C) 1987-2019 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"
+#include "cfgloop.h"
+namespace {
/* Store the data structures necessary for depth-first search. */
-struct depth_first_search_dsS {
- /* 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;
};
-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,
- 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.
bool
mark_dfs_back_edges (void)
{
- edge_iterator *stack;
int *pre;
int *post;
- int sp;
int prenum = 1;
int postnum = 1;
- sbitmap visited;
bool found = false;
/* Allocate the preorder and postorder number arrays. */
post = XCNEWVEC (int, last_basic_block_for_fn (cfun));
/* Allocate stack for back-tracking up CFG. */
- stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
- sp = 0;
+ auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
/* Allocate bitmap to track nodes that have been visited. */
- visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
+ auto_sbitmap visited (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_FOR_FN (cfun)->succs);
+ stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
- while (sp)
+ while (!stack.is_empty ())
{
- edge_iterator ei;
basic_block src;
basic_block dest;
/* Look at the edge on the top of the stack. */
- ei = stack[sp - 1];
+ edge_iterator ei = stack.last ();
src = ei_edge (ei)->src;
dest = ei_edge (ei)->dest;
ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
{
/* Since the DEST node has been visited for the first
time, check its successors. */
- stack[sp++] = ei_start (dest->succs);
+ stack.quick_push (ei_start (dest->succs));
}
else
post[dest->index] = postnum++;
post[src->index] = postnum++;
if (!ei_one_before_end_p (ei))
- ei_next (&stack[sp - 1]);
+ ei_next (&stack.last ());
else
- sp--;
+ stack.pop ();
}
}
free (pre);
free (post);
- free (stack);
- sbitmap_free (visited);
return found;
}
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
basic_block current_block;
basic_block ending_block;
- gcc_assert (INDEX_EDGE_PRED_BB (m_el, edge_index)
- != EXIT_BLOCK_PTR_FOR_FN (cfun));
+ gcc_assert (get_edge_src (edge_index) != EXIT_BLOCK_PTR_FOR_FN (cfun));
+
+ /* For abnormal edges, we don't make current_block control
+ dependent because instructions that throw are always necessary
+ anyway. */
+ edge e = find_edge (get_edge_src (edge_index), get_edge_dest (edge_index));
+ if (e->flags & EDGE_ABNORMAL)
+ return;
- if (INDEX_EDGE_PRED_BB (m_el, edge_index) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
+ if (get_edge_src (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 (m_el, edge_index));
+ ending_block = find_pdom (get_edge_src (edge_index));
- for (current_block = INDEX_EDGE_SUCC_BB (m_el, edge_index);
+ for (current_block = get_edge_dest (edge_index);
current_block != ending_block
&& current_block != EXIT_BLOCK_PTR_FOR_FN (cfun);
current_block = find_pdom (current_block))
- {
- 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
- anyway. */
- if (e->flags & EDGE_ABNORMAL)
- continue;
-
- set_control_dependence_map_bit (current_block, edge_index);
- }
+ set_control_dependence_map_bit (current_block, edge_index);
}
/* Record all blocks' control dependences on all edges in the edge
list EL, ala Morgan, Section 3.6. */
-control_dependences::control_dependences (struct edge_list *edges)
- : m_el (edges)
+control_dependences::control_dependences ()
{
timevar_push (TV_CONTROL_DEPENDENCES);
+
+ /* Initialize the edge list. */
+ int num_edges = 0;
+ basic_block 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);
+ m_el.create (num_edges);
+ edge e;
+ edge_iterator ei;
+ 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)
+ m_el.quick_push (std::make_pair (e->src->index, e->dest->index));
+
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 (m_el); ++i)
+ for (int i = 0; i < num_edges; ++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 (m_el);
+ m_el.release ();
}
/* Returns the bitmap of edges the basic-block I is dependent on. */
return control_dependence_map[i];
}
-/* Returns the edge with index I from the edge list. */
+/* Returns the edge source with index I from the edge list. */
-edge
-control_dependences::get_edge (int i)
+basic_block
+control_dependences::get_edge_src (int i)
+{
+ return BASIC_BLOCK_FOR_FN (cfun, m_el[i].first);
+}
+
+/* Returns the edge destination with index I from the edge list. */
+
+basic_block
+control_dependences::get_edge_dest (int i)
{
- return INDEX_EDGE (m_el, i);
+ return BASIC_BLOCK_FOR_FN (cfun, m_el[i].second);
}
void
connect_infinite_loops_to_exit (void)
{
- basic_block unvisited_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
- basic_block deadend_block;
- struct depth_first_search_dsS 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
post_order_compute (int *post_order, bool include_entry_exit,
bool delete_unreachable)
{
- edge_iterator *stack;
- int sp;
int post_order_num = 0;
- sbitmap visited;
int count;
if (include_entry_exit)
post_order[post_order_num++] = EXIT_BLOCK;
/* Allocate stack for back-tracking up CFG. */
- stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
- sp = 0;
+ auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
/* Allocate bitmap to track nodes that have been visited. */
- visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
+ auto_sbitmap visited (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_FOR_FN (cfun)->succs);
+ stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
- while (sp)
+ while (!stack.is_empty ())
{
- edge_iterator ei;
basic_block src;
basic_block dest;
/* Look at the edge on the top of the stack. */
- ei = stack[sp - 1];
+ edge_iterator ei = stack.last ();
src = ei_edge (ei)->src;
dest = ei_edge (ei)->dest;
if (EDGE_COUNT (dest->succs) > 0)
/* Since the DEST node has been visited for the first
time, check its successors. */
- stack[sp++] = ei_start (dest->succs);
+ stack.quick_push (ei_start (dest->succs));
else
post_order[post_order_num++] = dest->index;
}
post_order[post_order_num++] = src->index;
if (!ei_one_before_end_p (ei))
- ei_next (&stack[sp - 1]);
+ ei_next (&stack.last ());
else
- sp--;
+ stack.pop ();
}
}
tidy_fallthru_edges ();
}
- free (stack);
- sbitmap_free (visited);
return post_order_num;
}
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;
- }
-
- bb = EDGE_SUCC (bb, 0)->dest;
+ 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))
+ next = EDGE_SUCC (bb, 0)->dest;
+ else
+ {
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (loop_exit_edge_p (bb->loop_father, e))
+ break;
+ next = e ? e->dest : EDGE_SUCC (bb, 0)->dest;
+ }
}
gcc_unreachable ();
(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 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;
- edge_iterator *stack;
- int sp;
- int post_order_num = 0;
- sbitmap visited;
+ post_order->reserve_exact (n_basic_blocks_for_fn (cfun));
+
+ if (flag_checking)
+ verify_no_unreachable_blocks ();
/* Allocate stack for back-tracking up CFG. */
- stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
- sp = 0;
+ auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
/* Allocate bitmap to track nodes that have been visited. */
- visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
+ auto_sbitmap visited (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.quick_push (ei_start (bb->preds));
+ bitmap_set_bit (visited, bb->index);
+ }
+ if (EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds))
+ {
+ stack.quick_push (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_FN (bb, cfun)
if (EDGE_COUNT (bb->succs) == 0)
/* Push the initial edge on to the stack. */
if (EDGE_COUNT (bb->preds) > 0)
{
- stack[sp++] = ei_start (bb->preds);
+ stack.quick_push (ei_start (bb->preds));
bitmap_set_bit (visited, bb->index);
}
}
bool has_unvisited_bb = false;
/* The inverted traversal loop. */
- while (sp)
+ while (!stack.is_empty ())
{
edge_iterator ei;
basic_block pred;
/* Look at the edge on the top of the stack. */
- ei = stack[sp - 1];
+ ei = stack.last ();
bb = ei_edge (ei)->dest;
pred = ei_edge (ei)->src;
if (EDGE_COUNT (pred->preds) > 0)
/* Since the predecessor node has been visited for the first
time, check its predecessors. */
- stack[sp++] = ei_start (pred->preds);
+ 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[sp - 1]);
+ ei_next (&stack.last ());
else
- sp--;
+ stack.pop ();
}
}
/* 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. */
+ since EXIT_BLOCK is always added after the outer do-while loop. */
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))
basic_block be = dfs_find_deadend (bb);
gcc_assert (be != NULL);
bitmap_set_bit (visited, be->index);
- stack[sp++] = ei_start (be->preds);
+ stack.quick_push (ei_start (be->preds));
break;
}
}
}
- if (has_unvisited_bb && sp == 0)
+ if (has_unvisited_bb && stack.is_empty ())
{
- /* No blocks are reachable from EXIT at all.
+ /* 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_FOR_FN (cfun));
gcc_assert (be != NULL);
bitmap_set_bit (visited, be->index);
- stack[sp++] = ei_start (be->preds);
+ stack.quick_push (ei_start (be->preds));
}
/* The only case the below while fires is
when there's an infinite loop. */
}
- while (sp);
+ while (!stack.is_empty ());
/* EXIT_BLOCK is always included. */
- post_order[post_order_num++] = EXIT_BLOCK;
-
- free (stack);
- sbitmap_free (visited);
- return post_order_num;
+ post_order->quick_push (EXIT_BLOCK);
}
/* Compute the depth first search order of FN and store in the array
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_for_fn (cfun) - 1;
- sbitmap visited;
+ int rev_post_order_num = n_basic_blocks_for_fn (fn) - 1;
/* Allocate stack for back-tracking up CFG. */
- stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
- sp = 0;
+ auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (fn) + 1);
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_for_fn (cfun));
+ auto_sbitmap visited (last_basic_block_for_fn (fn));
/* 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_FOR_FN (fn)->succs);
+ stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn)->succs));
- while (sp)
+ while (!stack.is_empty ())
{
- edge_iterator ei;
basic_block src;
basic_block dest;
/* Look at the edge on the top of the stack. */
- ei = stack[sp - 1];
+ edge_iterator ei = stack.last ();
src = ei_edge (ei)->src;
dest = ei_edge (ei)->dest;
if (EDGE_COUNT (dest->succs) > 0)
/* Since the DEST node has been visited for the first
time, check its successors. */
- stack[sp++] = ei_start (dest->succs);
+ stack.quick_push (ei_start (dest->succs));
else if (rev_post_order)
/* There are no successors for the DEST node so assign
its reverse completion number. */
rev_post_order[rev_post_order_num--] = src->index;
if (!ei_one_before_end_p (ei))
- ei_next (&stack[sp - 1]);
+ ei_next (&stack.last ());
else
- sp--;
+ stack.pop ();
}
}
- free (stack);
- sbitmap_free (visited);
-
if (include_entry_exit)
{
if (pre_order)
pre_order[pre_order_num] = EXIT_BLOCK;
pre_order_num++;
if (rev_post_order)
- rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
+ rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
}
return pre_order_num;
return pre_order_num;
}
+/* Unlike pre_and_rev_post_order_compute we fill rev_post_order backwards
+ so iterating in RPO order needs to start with rev_post_order[n - 1]
+ going to rev_post_order[0]. If FOR_ITERATION is true then try to
+ make CFG cycles fit into small contiguous regions of the RPO order.
+ When FOR_ITERATION is true this requires up-to-date loop structures. */
+
+int
+rev_post_order_and_mark_dfs_back_seme (struct function *fn, edge entry,
+ bitmap exit_bbs, bool for_iteration,
+ int *rev_post_order)
+{
+ int pre_order_num = 0;
+ int rev_post_order_num = 0;
+
+ /* Allocate stack for back-tracking up CFG. Worst case we need
+ O(n^2) edges but the following should suffice in practice without
+ a need to re-allocate. */
+ auto_vec<edge, 20> stack (2 * n_basic_blocks_for_fn (fn));
+
+ int *pre = XNEWVEC (int, 2 * last_basic_block_for_fn (fn));
+ int *post = pre + last_basic_block_for_fn (fn);
+
+ /* BB flag to track nodes that have been visited. */
+ auto_bb_flag visited (fn);
+ /* BB flag to track which nodes have post[] assigned to avoid
+ zeroing post. */
+ auto_bb_flag post_assigned (fn);
+
+ /* Push the first edge on to the stack. */
+ stack.quick_push (entry);
+
+ while (!stack.is_empty ())
+ {
+ basic_block src;
+ basic_block dest;
+
+ /* Look at the edge on the top of the stack. */
+ int idx = stack.length () - 1;
+ edge e = stack[idx];
+ src = e->src;
+ dest = e->dest;
+ e->flags &= ~EDGE_DFS_BACK;
+
+ /* Check if the edge destination has been visited yet. */
+ if (! bitmap_bit_p (exit_bbs, dest->index)
+ && ! (dest->flags & visited))
+ {
+ /* Mark that we have visited the destination. */
+ dest->flags |= visited;
+
+ pre[dest->index] = pre_order_num++;
+
+ if (EDGE_COUNT (dest->succs) > 0)
+ {
+ /* Since the DEST node has been visited for the first
+ time, check its successors. */
+ /* Push the edge vector in reverse to match previous behavior. */
+ stack.reserve (EDGE_COUNT (dest->succs));
+ for (int i = EDGE_COUNT (dest->succs) - 1; i >= 0; --i)
+ stack.quick_push (EDGE_SUCC (dest, i));
+ /* Generalize to handle more successors? */
+ if (for_iteration
+ && EDGE_COUNT (dest->succs) == 2)
+ {
+ edge &e1 = stack[stack.length () - 2];
+ if (loop_exit_edge_p (e1->src->loop_father, e1))
+ std::swap (e1, stack.last ());
+ }
+ }
+ else
+ {
+ /* There are no successors for the DEST node so assign
+ its reverse completion number. */
+ post[dest->index] = rev_post_order_num;
+ dest->flags |= post_assigned;
+ rev_post_order[rev_post_order_num] = dest->index;
+ rev_post_order_num++;
+ }
+ }
+ else
+ {
+ if (dest->flags & visited
+ && src != entry->src
+ && pre[src->index] >= pre[dest->index]
+ && !(dest->flags & post_assigned))
+ e->flags |= EDGE_DFS_BACK;
+
+ if (idx != 0 && stack[idx - 1]->src != src)
+ {
+ /* There are no more successors for the SRC node
+ so assign its reverse completion number. */
+ post[src->index] = rev_post_order_num;
+ src->flags |= post_assigned;
+ rev_post_order[rev_post_order_num] = src->index;
+ rev_post_order_num++;
+ }
+
+ stack.pop ();
+ }
+ }
+
+ XDELETEVEC (pre);
+
+ /* Clear the temporarily allocated flags. */
+ for (int i = 0; i < rev_post_order_num; ++i)
+ BASIC_BLOCK_FOR_FN (fn, rev_post_order[i])->flags
+ &= ~(post_assigned|visited);
+
+ return rev_post_order_num;
+}
+
+
+
/* Compute the depth first search order on the _reverse_ graph and
- store in the array DFS_ORDER, marking the nodes visited in VISITED.
+ store it in the array DFS_ORDER, marking the nodes visited in VISITED.
Returns the number of nodes visited.
The computation is split into three pieces:
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. */
{
basic_block *st, lbb;
int sp = 0, tv = 0;
- unsigned size;
- /* A bitmap to keep track of visited blocks. Allocating it each time
- this function is called is not possible, since dfs_enumerate_from
- is often used on small (almost) disjoint parts of cfg (bodies of
- loops), and allocating a large sbitmap would lead to quadratic
- behavior. */
- static sbitmap visited;
- static unsigned v_size;
+ auto_bb_flag visited (cfun);
-#define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
-#define UNMARK_VISITED(BB) (bitmap_clear_bit (visited, (BB)->index))
-#define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
-
- /* Resize the VISITED sbitmap if necessary. */
- size = last_basic_block_for_fn (cfun);
- if (size < 10)
- size = 10;
-
- if (!visited)
- {
-
- visited = sbitmap_alloc (size);
- bitmap_clear (visited);
- v_size = size;
- }
- else if (v_size < size)
- {
- /* Ensure that we increase the size of the sbitmap exponentially. */
- if (2 * v_size > size)
- size = 2 * v_size;
-
- visited = sbitmap_resize (visited, size, 0);
- v_size = size;
- }
+#define MARK_VISITED(BB) ((BB)->flags |= visited)
+#define UNMARK_VISITED(BB) ((BB)->flags &= ~visited)
+#define VISITED_P(BB) (((BB)->flags & visited) != 0)
st = XNEWVEC (basic_block, rslt_max);
rslt[tv++] = st[sp++] = bb;
edge e;
unsigned ix;
- gcc_assert (!dst->popcount);
-
for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
{
e = EDGE_SUCC (b, ix);
edge e;
unsigned ix;
- gcc_assert (!dst->popcount);
-
for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
{
e = EDGE_PRED (b, ix);
edge e;
unsigned ix;
- gcc_assert (!dst->popcount);
-
for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
{
e = EDGE_SUCC (b, ix);
edge e;
unsigned ix;
- gcc_assert (!dst->popcount);
-
for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
{
e = EDGE_PRED (b, ix);
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));
+ auto_sbitmap visited (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))
n -= np;
}
- sbitmap_free (visited);
gcc_assert (n == 0);
return order;
#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 / thirdparty / gcc.git / blobdiff