[llvm-dev] Identifying contained loops

[Tobias Grosser via llvm-dev]

On 11/11/2015 03:28 PM, Russell Wallace via llvm-dev wrote:
> One of the things I'm trying to do is perform high-level optimizations
> on loops, which requires first identifying them. For a simple case,
> suppose you have something like
>
> for (size_t i = 0; i != n; ++i)
>    ++a[i];
>
> If a is a simple array, that will compile to a single basic block, which
> is easy enough to identify.
>
> But the body doesn't need to be a single basic block. It could contain
> complex conditions, nested loops, whatever, and for some purposes, it's
> still valid to think of it as a single loop that does something to every
> element of a.
>
> However, if there are branches into and out of the loop, that's no
> longer valid; it might do something to half the elements of the array
> and leave the other half untouched, for example.
>
> I don't know what the concept I'm looking for - a loop that is
> guaranteed to proceed from beginning to end, with no branches in or out
> - is usually called; for the title of this post, I've called it a
> 'contained' loop.
>
> I can figure out how to identify such, but I'd like to check whether
> this has already been done. Are there any existing passes or whatever
> that use this concept or identify such loops?

Hi Russel,

you might want to have a look at polly.llvm.org. We identify loop nests 
that can be transformed in lib/Analysis/ScopDetection.cpp. If you have 
specific questions I am glad to help.

Best,
Tobias