RFC: Making a common successor/predecessor interface

Project Infrastructure LLVM Dev List Archives
1

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

2

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()))” 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
3

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

4

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

5

Hi Alina,

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

Cheers,
Nicolai

6

Hi Alina,

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

Sounds good :). Thank you for your input!

Best,
Alina

Alina

7

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?

8

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

9

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

10

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, D75962), but the others I’ll abandon.

Best,
Alina

11

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, D75962), but the others I’ll abandon.

Cool - took a look/approved those two.

  • Dave