Alina Sbirlea via llvm-dev
2020-Mar-10 23:42 UTC
[llvm-dev] RFC: Making a common successor/predecessor interface
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>
David Blaikie via llvm-dev
2020-Mar-12 17:52 UTC
[llvm-dev] RFC: Making a common successor/predecessor interface
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/25fd80bd/attachment.html>
Alina Sbirlea via llvm-dev
2020-Mar-12 18:35 UTC
[llvm-dev] RFC: Making a common successor/predecessor interface
Yup, that solves my problem :-). Thanks a lot for the taking the time to understand and address the underlying issue! 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. 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/f83f75f2/attachment-0001.html>