[LLVMdev] region pass - new pass for llvm

[Tobias Grosser]

On 03/08/2010 11:23 AM, Renato Golin wrote:
> On 6 March 2010 02:05, Tobias Grosser<grosser at fim.uni-passau.de>  wrote:
>> This is useful if you want to restrict an analysis&transformation
>> e.g. to side effect free code, code without loops, code without
>> irregular control flow, ...
>
> I'm confused...
>
> I thought that loop optimization was one of the benefits of separating
> a region from the rest of the code... Also, you can only guarantee
> side effect free code if there is no function calls or the whole
> program is running single threaded. SSA would guarantee all the other
> cases.

Hi Renato,

these are just examples for what regions could be used for. The idea is 
in a first step to create a region tree that contains all regions in the 
CFG, where a region is a subgraph of the CFG that has just one entry and 
on exit edge (or can be transformed to such a region). These regions can 
easily be extracted or separately analyzed/optimized.

However the actual analysis of the content of the region is done in a 
later pass.

E.g. if your optimization only works on side effect free code it could 
be checked, that in a specific region only pure/const function calls 
appear. As you said you would also need restrictions on the load/stores 
and probably several more. However this is not the problem of the region 
framework. The region framework only gives you the units of the CFG that 
you can work on (or decide it is too difficult to work on these).

Using the region framework gives you can easily describe a part of the 
CFG, by just saying "this region will be optimized", "this region does 
not change any memory".

> I guess that the CFG would not be closed if there was a function call
> (or a jump for that matter), but multi-threaded load/stores can't be
> guaranteed. Even if you have locks, LLVM wouldn't be able to tell it's
> a lock and for that particular variable. Or maybe we should just
> ignore the case and let the programmer hang himself... ;)

What do you mean with a closed CFG? In terms of the CFG of a function a 
region is closed as there is just one entry and one exit edge. So there 
are no other ways to get into or out of the region except these two 
edges. A function call does not leave the region, as it either will 
return and finally leave the region using the exit edge or it will never 
return and therefore also never leave the region using a wrong edge. :-)

>> We will use it to extract regions with regular control flow that contain
>> only loops and branches with affine linear expressions in the loop
>> bounds or branch conditions. These are the regions that Polly
>> (polyhedral optimizations for LLVM) should work on.
>
> Ok, so this means you meant "code without non-affine loops", right?
Where did I say this? A region can have any content you want.

In Polly we want code without non-affine loops. Also there is a lot of 
other stuff we do not want. Either as it can technically not be handled 
or we just did not write code to support it.

> Still, non-affine loops can be converted to affine loops in many ways
How would you do this? As we use the scalar evolution analysis to 
analyze the loops, we do not depend on any syntactic form. Therefore to 
change non-affine loops to affine loops, I believe it takes some heavier 
transformations.

> and would be easier to do so in a closed region rather than looking
> again the same code poly has just seen, and converting loops to affine
> could be easier if the region was closed (simpler dependency
> analysis).
Again, what do you mean by closed region? And why would something look 
again at code polly hast just seen?

> So, I wouldn't rule out any kind of loop in the poly pass, and keep a
> flag to assert the region is "clean". The passes that need a clean
> region should only pass after all "cleaning" passes (such as
> 'affine-zising' loops) had run and skip if the region is not clean.

Yes. This is more or less how it should work.

At first I would start with a pass that detects if regions are clean and 
a polly pass that skips non clean regions. Later on I would like to 
schedule several cleanup passes before polly to make more regions 
"clean", so that the can be optimized by polly.

Cheers,

Tobias