+
+/* Helper routine for inverted_post_order_compute.
+ BB has to belong to a region of CFG
+ unreachable by inverted traversal from the exit.
+ i.e. there's no control flow path from ENTRY to EXIT
+ that contains this BB.
+ This can happen in two cases - if there's an infinite loop
+ or if there's a block that has no successor
+ (call to a function with no return).
+ Some RTL passes deal with this condition by
+ calling connect_infinite_loops_to_exit () and/or
+ add_noreturn_fake_exit_edges ().
+ However, those methods involve modifying the CFG itself
+ which may not be desirable.
+ Hence, we deal with the infinite loop/no return cases
+ by identifying a unique basic block that can reach all blocks
+ in such a region by inverted traversal.
+ This function returns a basic block that guarantees
+ that all blocks in the region are reachable
+ by starting an inverted traversal from the returned block. */
+
+static basic_block
+dfs_find_deadend (basic_block bb)
+{
+ sbitmap visited = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (visited);
+
+ for (;;)
+ {
+ SET_BIT (visited, bb->index);
+ if (EDGE_COUNT (bb->succs) == 0
+ || TEST_BIT (visited, EDGE_SUCC (bb, 0)->dest->index))
+ {
+ sbitmap_free (visited);
+ return bb;
+ }
+
+ bb = EDGE_SUCC (bb, 0)->dest;
+ }
+
+ gcc_unreachable ();
+}
+
+
+/* Compute the reverse top sort order of the inverted CFG
+ i.e. starting from the exit block and following the edges backward
+ (from successors to predecessors).
+ This ordering can be used for forward dataflow problems among others.
+
+ This function assumes that all blocks in the CFG are reachable
+ from the ENTRY (but not necessarily from EXIT).
+
+ If there's an infinite loop,
+ a simple inverted traversal starting from the blocks
+ with no successors can't visit all blocks.
+ To solve this problem, we first do inverted traversal
+ starting from the blocks with no successor.
+ And if there's any block left that's not visited by the regular
+ inverted traversal from EXIT,
+ those blocks are in such problematic region.
+ Among those, we find one block that has
+ any visited predecessor (which is an entry into such a region),
+ and start looking for a "dead end" from that block
+ and do another inverted traversal from that block. */