[LLVMdev] Make LoopBase inherit from "RegionBase"?

Jan Sjodin jan_sjodin at yahoo.com
Thu Jan 21 12:38:38 PST 2010

>>> No. The ideas are comparable, however I believe their implementation is
>>> a little complicated. ;-)
>> Do you have the same definition of a region and entry/exit blocks as they do?
> No. They define a region based on all the edges in the region. This is a
> very verbose definition, as all edges have to be saved. Also it is quite
> expensive to compare regions, ...
> However their description allows to talk about all possible regions.

I agree, their definition did not seem practical for our purposes.

>> Is the entry always contained and is the exit never contained, or is that specified
>> per region? Depending on the restrictions of entry and exit blocks a loop with a single
>> basic block cannot be an entry or exit by itself. Example:
> The entry is always contained and dominates all bbs in the region. The
> exit is never contained, but it postdominates all bbs in the region.

Okay, that makes sense. 

>> With the insertion of extra merge-blocks the code becomes more structured and the PST
>> can be refined further. A more fine-grained PST may allow more cases to be handled. 
> That is actually the difference between my algorithm and the PST bracket
> algorithm. Mine should get the same regions, that the PST one gets after
> inserting the best merge blocks possible. Just without requiring CFG
> changes.

With the definition of a SESE-region you mention above I can see how that would work. 
It was just not clear to me what the definition was to begin with. Back-edges is another
matter, but I am sure they are handled one way or another. I will have to look more into the

> I am in writing some documentation about this that we could discuss
> later on.


> Thanks for discussing this with me. It helped me to get a feeling where
> the differences are. Hoping we can have these discussions more often.

Yes, there are always interesting details to be discussed between different algorithms.

- Jan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100121/49d1910d/attachment.html>

More information about the llvm-dev mailing list