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

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.
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200309/6db992a7/attachment.html>

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/20200309/1b2a9cfa/attachment.html>

On Mon, Mar 9, 2020 at 11:57 PM Alina Sbirlea via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> 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.
> 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.
Have you considered going the other way and implementing
succ_begin/end for MachineBasicBlock and others?

Cheers,
Nicolai

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


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

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>