[llvm-dev] RFC: Making a common successor/predecessor interface

Tue Mar 10 16:42:33 PDT 2020

On Tue, Mar 10, 2020 at 2:30 PM David Blaikie <dblaikie at gmail.com> wrote:

>
>
> On Tue, Mar 10, 2020 at 8:31 AM Alina Sbirlea <alina.sbirlea at gmail.com>
> wrote:
>
>> Hi Dave,
>>
>> It may be possible to do this with the current API, but what I was
>> looking for is a common API for existing block types. For example there is
>> no succ_begin for Machine BasicBlock.
>>
>
>> I'm looking to make the CFGSuccessors and CFGPredecessors classes in
>> CFGDiff.h templated, and this needs a common API for all types
>> instantiations.
>>
>> Does this clarify your question or did I misunderstand your suggestion?
>>
>
> Possibly some misunderstanding - sounds like Nicolai had the same
> suggestion phrased more clearly.
>
>
>> Nicolai,
>>
>> Yes, I considered declaring the "global" succ_begin for the other block
>> types, but it seems like a more complex change (probably to declare the
>> type as Dave described, and these need adding for 3 more types vs 2 now)
>> and these wouldn't be used anywhere else.
>>
>
> What do you mean by "adding 3 more types vs 2 now" - where the iterator
> types are written is pretty separate from this API change (even if the
> iterator types remain non-members - the succ_begin non-member -> member
> functions with a member type could be achieved by using a member typedef
> rather than a member /type/ )
>

I meant adding the global APIs for
MachineBasicBlock, VPBlockBase, clang::CFGBlock (3), vs adding member APIs
in BasicBlock and VPBlockBase (2).
This is only because the use case I am looking at involves the
DominatorTree and there are no instantiations around other types (like you
mentioned: Interval).
Looking closer at the comments for Interval, I see that the global APIs
were added to mirror the BasicBlock ones, and they're essentially wrappers
over iterators expressed as class members.

> So currently we have:
>
> class Instruction;
> class BasicBlock;
> class Interval;
>
> succ_begin(Instruction*)
> succ_begin(BasicBlock*)
> succ_begin(Interval*)
> (& some kind of Region thing in RegionIterator.h)
>
> and you'd like to generalize this over more types, MachineBasicBlocks,
> VPBlockBase and clang::CFGBlock?
>
> So the suggestion would be to add:
>
> succ_begin(MachineBasicBlock*)
> succ_begin(VPBlockBase*)
> succ_begin(CFGBlock*)
>
> what would be the negative side of adding that, rather than porting the
> extra 3 to member functions?
>

I don't think there is any negative, tbh. I simply found it clearer to
reason about these as class member methods, and, looking at the existing
cases, the "global" API approach looked to me to be the outlier.
I also found somewhat confusing that, for Instructions, there are defined
successor iterators via the global APIs but not predecessors, and these are
in a separate file (CFG.h) so it's not as obvious this is the case. If
these were class iterators, this would stand out.

Thinking more, I think your suggestion to add the global ones is easier to
implement as as quick solution:
succ_begin(MachineBasicBlock*)
succ_begin(VPBlockBase*)
succ_begin(CFGBlock*)
just like you suggested, as these are just wrappers over the class member
methods (like those defined for Interval).
If folks feel this is a cleaner/better approach, I'm happy to work towards
that.

The member methods still seem cleaner to me, but I realize I'll have to
sign up for changing the whole code-base to use that if going that route
:-).
Again, as long as the end result is consistent, I'm flexible to go either
way.

Best,
Alina

>
>> AFAICT, there is no issue with replacing the current "global" iterators
>> with class specific ones, they are already used as such. But perhaps I
>> don't have the full picture.
>>  In the first patch I put up, the iterators added inside BasicBlock can
>> co-exist with the global ones, so the switch can be done incrementally.
>>
>>
>> Thanks,
>> Alina
>>
>> On Mon, Mar 9, 2020, 4:16 PM David Blaikie <dblaikie at gmail.com> wrote:
>>
>>>
>>>
>>> On Mon, Mar 9, 2020 at 3:57 PM Alina Sbirlea via llvm-dev <
>>> llvm-dev at lists.llvm.org> wrote:
>>>
>>>> Hi,
>>>>
>>>> As part of an ongoing work to extend the GraphDiff (this models a CFG
>>>> view), I came across the need to have a common interface for accessing
>>>> successors/predecessors in various IR units, such that a type such as
>>>> `typename NodeT::succ_iterator` could be used in templated code.
>>>>
>>>
>>> I /think/ this can be achieved with the existing API by using
>>> "decltype(succ_begin(std::declval<NodeT>()))" instead of the typename
>>> you've got as an example (it looks like succ_begin is the extension point -
>>> but the problem you're having is naming its return type? decltype would be
>>> one option) - you could make a trait wrapper around that or the like if you
>>> need this type name in a bunch of disparate places (where they can't share
>>> a typedef).
>>>
>>> Would that suffice? are there other aspects of your use case that don't
>>> line up well with the existing non-member/overload API?
>>>
>>> - Dave
>>>
>>>
>>>> In particular, the need arose for BasicBlocks, MachineBasicBlocks,
>>>> VPBlockBase and clang::CFGBlock.
>>>>
>>>> The least invasive change seemed to be to use the interface already
>>>> being used in MachineBasicBlock and clang::CFGBlock, and:
>>>> (1) update BasicBlock to use this instead of the "global"
>>>> `succ_iterator` in IR/CFG.h
>>>> (2) add the same interfaces in VPBlockBase as simple wrappers over
>>>> existing Successors/Predecessors vectors.
>>>>
>>>> I've been working on a few patches to make this happen, but I'd like
>>>> the community's thoughts on this before deep-diving into code reviews.
>>>>
>>>> For some concrete view of what the changes look like, I uploaded two
>>>> preliminary patches:
>>>> (1) part 1: D75881 <https://reviews.llvm.org/D75881>: Introducing
>>>> class specific iterators
>>>> (2) D75882 <https://reviews.llvm.org/D75882>
>>>> (1) part 2: pending: Cleaning up existing usages; example replacement:
>>>> `succ_begin(BB)` with `BB->succ_begin()`.
>>>> (1) part3/4: pending: Add class specific iterators to `Instruction` and
>>>> clean up existing usages just as for `BasicBlock`.
>>>>
>>>> I split the above (1) just to clarify what interfaces are added versus
>>>> the NFC cleanups that follow. But it could be done just as well in a single
>>>> patch.
>>>>
>>>> I welcome comments on this, and if there's something I missed
>>>> explaining please let me know.
>>>>
>>>> Thank you,
>>>> Alina
>>>>
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org
>>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200310/1b4a16f0/attachment.html>