[gomp4] SESE region neutering

[Nathan Sidwell]

One optimization one can apply to the worker & vector neutering that the PTX 
backend does, is to neuter Single-Entry, Single-Exit regions, rather than 
individual BBs.  An  SESE region in a region  bounded by a single entry BB and a 
single exit BB.  (A single BB is a trivial  SESE region).  Finding these regions 
is important as it means we can skip straight from the entry block to the exit 
block.

This patch implements that optimization.  As the comment at the head of the code 
says, we first find 'cycle-equivalent' BBs.  These are ones that we determine 
are in the same (set of) loops, in the closed graph.  Such equivalent BBs form 
the entry and exit BBs of an SESE region.  Once we've found these, we need to 
find the ones that cover the most of the graph -- and delete the ones that are 
consumed by the larger areas.  This is done by a coloring algorithm executed as 
a DFS walk.  One of the properties of SESE regions is that they are always 
strictly nested -- they never partially overlap.  That property is used by the 
coloring algorithm.

Once we've obtained the set of SESE regions, it's a simple matter of applying 
the neutering algorithm, which already accepted an entry and an exit node.

nathan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: gomp4-sese.patch
Type: text/x-patch
Size: 20398 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20150911/e0a2d603/attachment.bin>