RE: [graphite-branch] Improve SCoPs SESE

["Sjodin, Jan" <Jan dot Sjodin at amd dot com>]

> I would just like to discuss the idea. A little explanation 
> that was not
> possible during our phone call today (Since about two minutes my
> internet is working again)
> 
> During SCoP detection we can not represent the SCoPs as a single exit
> single entry region as it is described in the graphite.h 
> SCOP_REGION, as
> this data structure uses a single edge to describe e.g. the entry.
> 
> But code like
> 
>   |  1  2
>   |  | /
>   |  |/
>   |  3  <- entry
>   |  |\
>   |  | |
>   |  4 ^
>   |  | |
>   |  |/
>   |  5
> 
> 
> is also single entry, even if we do not have a single entry edge. But
> the edges (1->3, 2->3) can easily be combined using a forwarder bb.
> 
>   |  1  2
>   |  | /
>   |  |/
>   |3.0
>   |  |      (3.0 -> 3.1) = entry edge
>   |3.1          <- entry
>   |  |\
>   |  | |
>   |  4 ^
>   |  | |
>   |  |/
>   |  5  */
> 
> Here we get a single entry edge.
> 
> If we do not want to modify the CFG during SCoP detection, we have to
> use a representation (sd_region), that is able to represent SCoPs
> like the above.
> After SCoP detection we can introduce forwarder blocks, to be able to
> use a single edges to describe the entry and exit points.
> 
> Tobi
> 
> P.S.: I would like to test this patch a little bit more (polyhedron),
> but it would be great to hear some comments about the idea, as we are
> always fighting a little bit about the right representation 
> of the SCoP
> borders. ;-)


Imo using forwarding blocks makes sense. In the example you have block 3

has multiple in edges and out edges, which will prevent a SESE-region to
be formed for blocks 3, 4 and 5. 

The dvantage of defining SESE regions  on edges is that they are not 
ambiguous when it comes to rewriting the  CFG. For example: 
   
     1  _
     | / |
     vv  |
     2   |
    /|   |
   / v   |
  /  3   |
 v   |   |
 4    \_/
     
     
If scopes use blocks as borders a scope can be created for blocks 2 and
3.
During code generation 2 and 3 may be replaced by something a lot more 
complicated, or it could even be eliminated. To rewrite the CFG all four

edges around block 2 need to be considered. Which edges should be 
removed/replaced, and which ones should be preserved (or tied together 
if the SCoP was eliminated) cannot be locally determined by only 
looking at block 2. 

In the other case if the SCoP is defined by two edges: 1->2 and 2->4 it 
becomes much easier. All other edges must be part of the scope and can
be safely removed since only 2 external edges exist.

There are other cases that could be problematic (but perhaps do not
occur 
in GCC). If node 2 had multiple entries to the loop node 2 could contain
phi-nodes that would need to remain even if the SCoP was eliminated.

- Jan