[LLVMdev] The implementation algorithm behind LLVM's RegionInfo class

[Tobias Grosser]

On 01/07/2014 07:47, Matt Arsenault wrote:
>
> On Jun 27, 2014, at 1:55 PM, Tobias Grosser <tobias at grosser.es> wrote:
>
>> On 27/06/2014 22:43, Paul Vario wrote:
>>> Thanks very much for the quick response. I have read the text many times,
>>> but it was not very clear to me why checking the two conditions involving
>>> dominance frontiers is equivalent to proving the pair {entry, exit} defines
>>> a refined region. I was asking for an mathematical proof really. It sounds
>>> to me like there should be a theorem or two in the graph theory endorsing
>>> it. Or do you mean, the implementation is solely based on empirical
>>> observation instead of theory. The reason I am interested in the
>>> formalization is that I find the current RegionInfo implementation very
>>> helpful in defining regions in between barriers in the OpenCL
>>> implementation on CPU. I haven't found a test case that breaks it. I got
>>> the right intuition, just could not figure out a way to formally prove it,
>>> neither did I find one in your regioninfo draft.
>>
>> The code was written as a student project during my masters and I never got around to write a paper or a formal mathematical proof. I believe the description should give an intuition for the prove, but I am currently a little too loaded to do it myself. Obviously, I would be interested in any kind of further formalisation. Is there a specific part of the description that is unclear to you and that would allow you to possibly develop a proof?
>>
>> Also, please keep me updated with your OpenCL barrier work. This sounds very interesting.
>
> I was looking at this recently since I want to create a MachineRegionPass, which doesn’t currently exist. Can the existing RegionInfo be refactored to support MachineBasicBlocks? I went to try doing it it, but then the DominanceFrontier it depends on has a warning that it’s deprecated. Should I be looking somewhere else or do I need to create something new (which I really don’t want to do)?

Hi Matt,

to give my point on this.

The use of DominanceFrontier has previously caused concerns raising the 
following two issues: 1) Worst case N^2 complexity of the 
DominanceFrontier computation 2) Not available by default, which means 
using just the dominance information is preferable as it is most of the 
time already available and costs O(0). The last is an argument against 
the use of any analysis pass, if dominance info is sufficient.

I personally have not seen any compile-time issues due to 1) in the last 
four years of using it in Polly, but this does obviously not change the 
theoretical complexity. It would be great to remove the need for the 
dominance frontier in the RegionInfo pass, but at the time of writing it 
I did not see a way to do so, without reducing its precision (not 
handling so-called refined regions any more).

Assuming the concept of control flow regions is what you want/need there
seem to be the following steps you could take forward:

1) I think porting the interface/analysis to MachineBasicBlocks might
    makes sense in general to evaluate/experiment it in your work and
    also to gather data on its speed and possible compile-time overhead.
    Also, I would run experiments to verify how much benefit the use
    of refined regions gives you by running your pass once only on
    simple regions and once on simple and refined regions

2) If simple regions have shown sufficient for you, you might check if
    a dominance-tree-only check is possible that is sufficient
    to find simple regions.

3) Obviously, work on the algorithmic side is always possible and in
    the best case this should not affect the interface.

Cheers,
Tobias