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

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

[grosser at gcc dot gnu dot org]

During SCoP detection we split bbs (e.g. in "scopdet_edge_info"), but the SCoP
detection should only detect SCoPs and not modify anything.
Also it splits bbs in inner loops, that do not need to be splitted.

Bb splitting was introduced to make SCoPs entry/exit defined by a single edge.
That is a great idea to simplify code generation, but we should ensure this in
a later cleanup pass. (May be just before code generation)


-- 
           Summary: [graphite] SCoP detection splits bbs / Define SCoPs with
                    single entry and exit edge
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: grosser at gcc dot gnu dot org
        ReportedBy: grosser at gcc dot gnu dot org


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

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

[grosser at gcc dot gnu dot org]

-- 

grosser at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |grosser at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
           Priority|P3                          |P5
   Last reconfirmed|0000-00-00 00:00:00         |2008-09-04 16:05:31
               date|                            |


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

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

[spop at gcc dot gnu dot org]

------- Comment #1 from spop at gcc dot gnu dot org  2008-09-05 16:19 -------
(In reply to comment #0)
> During SCoP detection we split bbs (e.g. in "scopdet_edge_info"), but the SCoP
> detection should only detect SCoPs and not modify anything.

No, we want to split BBs to increase the scop boundaries by moving
code in different BBs.

> Also it splits bbs in inner loops, that do not need to be splitted.
> 

More precisely: we split the basic block that is the destination of a
single exit loop, and that has multiple successors.

I think this is not a big problem right now, but indeed this bb_split
is not needed.  We can remove the bb_split by slightly modifying the
scop detection algorithm: putting the code that splits the bbs after
we determine whether the loop exit should be the place for a new scop,
i.e. computing result.next after we determine result.difficult.


-- 


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

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

[spop at gcc dot gnu dot org]

------- Comment #2 from spop at gcc dot gnu dot org  2008-09-11 16:47 -------
Jan proposed to switch to a different algorithm for detecting scops
based on the fact that scops are single entry, single exit regions.

Instead of detecting scops from the innermost to the outermost, we
should instead build a tree of SESE regions, then from the outermost
SESE ask whether the region contains side effects, in which case we
can walk down to an inner SESE region that does not contain side
effects.  When a SESE does not contain side effects, and does contain
interesting code for graphite, i.e. loops, we do build a scop for it.

We are working on an implementation of this algorithm.


-- 


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

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

[spop at gcc dot gnu dot org]

------- Comment #3 from spop at gcc dot gnu dot org  2008-09-11 16:51 -------
See also 
"The program structure tree: Computing control regions in linear time",
1994, by Richard Johnson, David Pearson, Keshav Pingali.


-- 


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

[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

[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 #5 from grosser at gcc dot gnu dot org  2008-09-18 16:34 -------
I need to read the paper now. It seems I was not informed about any updates by
the bugtracker so I just got the information. Sorry.


-- 


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

[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 #6 from grosser at gcc dot gnu dot org  2008-09-26 06:59 -------
Created an attachment (id=16410)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16410&action=view)
The next version, no bugs in polyhedron

I would like to commit this patch, can you test if it works with SCoP
generation.


-- 


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

[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 #7 from grosser at gcc dot gnu dot org  2008-09-29 13:14 -------
Committed SVN 140746.


-- 

grosser at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


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

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

[Sebastian Pop]

> ------- Comment #7 from grosser at gcc dot gnu dot org  2008-09-29 13:14 -------
> Committed SVN 140746.

I see that in http://gcc.gnu.org/viewcvs?view=rev&revision=140746
you forgot to include in the changelog a line like this:

PR tree-optimization/37372

that would have automatically included the commit message in the bugzilla bug.

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

[sebpop at gmail dot com]

------- Comment #8 from sebpop at gmail dot com  2008-09-29 14:46 -------
Subject: Re:  [graphite] SCoP detection splits bbs / Define SCoPs with single
entry and exit edge

> ------- Comment #7 from grosser at gcc dot gnu dot org  2008-09-29 13:14 -------
> Committed SVN 140746.

I see that in http://gcc.gnu.org/viewcvs?view=rev&revision=140746
you forgot to include in the changelog a line like this:

PR tree-optimization/37372

that would have automatically included the commit message in the bugzilla bug.


-- 


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