[Graphite] Redesign Graphite scop detection

[Sebastian Paul Pop]

Hi Tobi,

we do not cache SCEV information as it depends on the region boundaries,
so I think we are safe when we extend scops.

On handling non-affine regions/loops, you are right, we would need to
first teach scop detection about how to handle them, and then teach it
to the SESE-to-poly pass as well.

Thanks for your review.

Sebastian

-----Original Message-----
From: Tobias Grosser [mailto:tobias@grosser.es] 
Sent: Monday, September 28, 2015 3:19 AM
To: Aditya Kumar; gcc-patches@gcc.gnu.org
Cc: richard.guenther@gmail.com; aditya.k7@samsung.com; s.pop@samsung.com;
sebpop@gmail.com
Subject: Re: [Graphite] Redesign Graphite scop detection

On 09/28/2015 03:30 AM, Aditya Kumar wrote:
> From: hiraditya <hiraditya@msn.com>
>
> Redesign Graphite scop detection for faster compiler time and detecting
more SCoPs.
>
> Existing algorithm for SCoP detection in graphite was based on dominator
tree
> where a tree (CFG) traversal was required for analyzing an SESE. The tree
> traversal is linear in the number of basic blocks and SCoP detection is
> (probably) linear in number of instructions. That algorithm utilized a
generic
> infrastructure of SESE which does not directly represent loops.  With
regards to
> graphite framework, we are only interested in subtrees with loops. The new
> algorithm is geared towards tree traversal on loop structure. The
algorithm is
> linear in number of loops which is faster than the previous algorithm.
>
> Briefly, we start the traversal at a loop-nest and analyze it recursively
for
> validity. Once a valid loop is found we find a valid adjacent loop. If an
> adjacent loop is found and is valid, we merge both loop nests otherwise we
form
> a SCoP from the previous loop nest, and resume the algorithm from the
adjacent
> loop nest. The data structure to represent an SESE is an ordered pair of
edges
> (entry, exit). The new algoritm can extend a SCoP in both the directions.
With
> this approach, the number of instructions to be analyzed for validity
reduces to
> a minimal set.  We start by analyzing those statements which are inside a
loop,
> because validity of those statements is necessary for the validity of
loop. The
> statements outside the loop nest can be just excluded from the SESE if
they are
> not valid.

I am generally fine with this, but please consider that when growing a SCoP
certain
previous analysis may become invalid (an affine expression may suddenly
become
non-affine as parameters that were previously scop-invariant may now be part
of
the scop. Also, how are you planning to handle non-affine regions/loops. In
polly
we can encapsulate non-affine loops and regions in bigger scops. To handle
this,
I assume you would need to teach your patch to start growing regions even
though
the innermost loops cannot be modeled precisely.

Best,
Tobias