<div dir="ltr">I see, this is interesting, thanks! Yeah, it seems you're doing something similar with a specific focus on optimizing array operations; this comment seems to be the explanation of the core of it:<br><br>// Detect the maximal Scops of a function.<br>//<br>// A static control part (Scop) is a subgraph of the control flow graph (CFG)<br>// that only has statically known control flow and can therefore be described<br>// within the polyhedral model.<br>//<br>// Every Scop fullfills these restrictions:<br>//<br>// * It is a single entry single exit region<br>//<br>// * Only affine linear bounds in the loops<br>//<br>// Every natural loop in a Scop must have a number of loop iterations that can<br>// be described as an affine linear function in surrounding loop iterators or<br>// parameters. (A parameter is a scalar that does not change its value during<br>// execution of the Scop).<br>//<br>// * Only comparisons of affine linear expressions in conditions<br>//<br>// * All loops and conditions perfectly nested<br>//<br>// The control flow needs to be structured such that it could be written using<br>// just 'for' and 'if' statements, without the need for any 'goto', 'break' or<br>// 'continue'.<br>//<br>// * Side effect free functions call<br>//<br>// Only function calls and intrinsics that do not have side effects are allowed<br>// (readnone).<br>//<br>// The Scop detection finds the largest Scops by checking if the largest<br>// region is a Scop. If this is not the case, its canonical subregions are<br>// checked until a region is a Scop. It is now tried to extend this Scop by<br>// creating a larger non canonical region.<br><br>And it seems to make use of llvm's notion of SESE regions as described in <a href="http://llvm.org/docs/doxygen/html/RegionInfo_8h_source.html">http://llvm.org/docs/doxygen/html/RegionInfo_8h_source.html</a><br><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Nov 11, 2015 at 4:24 PM, Tobias Grosser <span dir="ltr"><<a href="mailto:tobias@grosser.es" target="_blank">tobias@grosser.es</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">On 11/11/2015 03:28 PM, Russell Wallace via llvm-dev wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
One of the things I'm trying to do is perform high-level optimizations<br>
on loops, which requires first identifying them. For a simple case,<br>
suppose you have something like<br>
<br>
for (size_t i = 0; i != n; ++i)<br>
   ++a[i];<br>
<br>
If a is a simple array, that will compile to a single basic block, which<br>
is easy enough to identify.<br>
<br>
But the body doesn't need to be a single basic block. It could contain<br>
complex conditions, nested loops, whatever, and for some purposes, it's<br>
still valid to think of it as a single loop that does something to every<br>
element of a.<br>
<br>
However, if there are branches into and out of the loop, that's no<br>
longer valid; it might do something to half the elements of the array<br>
and leave the other half untouched, for example.<br>
<br>
I don't know what the concept I'm looking for - a loop that is<br>
guaranteed to proceed from beginning to end, with no branches in or out<br>
- is usually called; for the title of this post, I've called it a<br>
'contained' loop.<br>
<br>
I can figure out how to identify such, but I'd like to check whether<br>
this has already been done. Are there any existing passes or whatever<br>
that use this concept or identify such loops?<br>
</blockquote>
<br></div></div>
Hi Russel,<br>
<br>
you might want to have a look at <a href="http://polly.llvm.org" rel="noreferrer" target="_blank">polly.llvm.org</a>. We identify loop nests that can be transformed in lib/Analysis/ScopDetection.cpp. If you have specific questions I am glad to help.<br>
<br>
Best,<br>
Tobias<br>
<br>
</blockquote></div><br></div>