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)
(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.
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.
See also "The program structure tree: Computing control regions in linear time", 1994, by Richard Johnson, David Pearson, Keshav Pingali.
Created attachment 16355 [details] 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.
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.
Created attachment 16410 [details] The next version, no bugs in polyhedron I would like to commit this patch, can you test if it works with SCoP generation.
Committed SVN 140746.
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.