llvm dev - Mar 2020 - RFC: Making a common successor/predecessor interface

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?

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.
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/359aee92/attachment.html>

Hi Alina,

On Tue, Mar 10, 2020 at 4:31 PM Alina Sbirlea via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> 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.
> 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.
So the specific reason I was asking is that for GPU applications, we
are interested in potentially having two CFGs overlaying the same set
of basic blocks. Due to the SIMT nature of execution there are two
types of control flow.

On second thought, however, it probably doesn't make much of a
difference for that particular problem whether succ_begin/end are
global or member functions.

And from other perspectives, having them as member functions seems
slightly better because it makes it easier to find them. So in
summary, I suppose either way is fine, as long as we're making things
consistent :)

Cheers,
Nicolai
>
>
> 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: Introducing class specific iterators
>>> (2) 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
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


-- 
Lerne, wie die Welt wirklich ist,
aber vergiss niemals, wie sie sein sollte.

On Tue, Mar 10, 2020 at 9:46 AM Nicolai Hähnle <nhaehnle at gmail.com>
wrote:
> Hi Alina,
>
> On Tue, Mar 10, 2020 at 4:31 PM Alina Sbirlea via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> > 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.
> > 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.
>
> So the specific reason I was asking is that for GPU applications, we
> are interested in potentially having two CFGs overlaying the same set
> of basic blocks. Due to the SIMT nature of execution there are two
> types of control flow.
>
> On second thought, however, it probably doesn't make much of a
> difference for that particular problem whether succ_begin/end are
> global or member functions.
>
> And from other perspectives, having them as member functions seems
> slightly better because it makes it easier to find them. So in
> summary, I suppose either way is fine, as long as we're making things
> consistent :)
>
Sounds good :). Thank you for your input!

Best,
Alina

Alina
>
> Cheers,
> Nicolai
>
> >
> >
> > 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: Introducing class specific iterators
> >>> (2) 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
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
> --
> Lerne, wie die Welt wirklich ist,
> aber vergiss niemals, wie sie sein sollte.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200310/98c1d0f0/attachment-0001.html>

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/ )

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?

> 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/dec29362/attachment.html>

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>