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:tob...@grosser.es] Sent: Monday, September 28, 2015 3:19 AM To: Aditya Kumar; gcc-patches@gcc.gnu.org Cc: richard.guent...@gmail.com; aditya...@samsung.com; s....@samsung.com; seb...@gmail.com Subject: Re: [Graphite] Redesign Graphite scop detection On 09/28/2015 03:30 AM, Aditya Kumar wrote: > From: hiraditya <hiradi...@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
