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 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
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
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.