[Bug middle-end/37372] [graphite] SCoP detection splits bbs / Define SCoPs with single entry and exit edge

[grosser at gcc dot gnu dot org]

------- Comment #4 from grosser at gcc dot gnu dot org  2008-09-18 16:25 -------
Created an attachment (id=16355)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16355&action=view)
Create single entry single exit edges for the SCoPs of the SCoP detection

Here is a idea how to handle the single exit single entry edges. Have also a
look at this mail:
http://gcc.gnu.org/ml/gcc-patches/2008-09/msg01324.html

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.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37372