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

Thu Mar 12 11:50:55 PDT 2020

On Thu, Mar 12, 2020 at 11:36 AM Alina Sbirlea <alina.sbirlea at gmail.com>
wrote:

> Yup, that solves my problem :-). Thanks a lot for the taking the time to
> understand and address the underlying issue!
>

Sure thing - thanks for walking me through it!

> I have a couple of NFC patches sent out that I think are still worth
> checking-in (D75952 <https://reviews.llvm.org/D75952>, D75962
> <https://reviews.llvm.org/D75962>), but the others I'll abandon.
>

Cool - took a look/approved those two.

- Dave

>
> Best,
> Alina
>
>
> On Thu, Mar 12, 2020 at 10:52 AM David Blaikie <dblaikie at gmail.com> wrote:
>
>> Think we got this all figured out with: https://reviews.llvm.org/D76034 -
>> but if there's more issues here (or just general C++-y design questions,
>> etc) more than happy to discuss them here/other threads/whenever :)
>>
>> On Tue, Mar 10, 2020 at 4:42 PM Alina Sbirlea <alina.sbirlea at gmail.com>
>> wrote:
>>
>>> 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/20200312/993fe379/attachment.html>