[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle abandoned this revision.
nhaehnle added a comment.
Herald added a subscriber: teijeong.

Superseded by D92924 , D92925 
, D92926 


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle added a comment.
Herald added a subscriber: dexonsmith.

I'm going to follow up with another RFC about this on llvm-dev.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Renato Golin via Phabricator via cfe-commits]

rengolin added a comment.

I have read all of the comments in this review and have looked at all the other 
pending reviews because of this and I still see strong disagreement on the 
design and implementation.

Unfortunately, I can't contribute with the technical discussion because there's 
a lot more context and content here than I can absorb in the time I have 
available, but overall I think David's critics are very pertinent. They don't 
mean the code is wrong or bad, just that they are important questions that need 
answers. Some of the questions were answered, others weren't. This patch should 
not have been committed before those things were sorted out, as is clearly 
stated in the (existing) review policy 
(https://llvm.org/docs/CodeReview.html#acknowledge-all-reviewer-feedback).

I do appreciate that the other patches are "waiting" for this one and that it 
has been months, but this patch fundamentally changes the algorithm with a 
motivation that still isn't clear for two reasons:

1. It was initially stated that the motivation is to reduce the number of 
templates because the author doesn't like them, which is not a good reason.
2. Despite recurrent requests to show concrete code examples comparing current 
and new design, showing why it would be "easier to use", none have materialised 
(other than David's own attempts).

All of the other patches were approved by the same set of people. This is 
definitely not uncommon, but is highly susceptible to unconscious bias. Once 
David questioned the approach with concrete questions, concrete answers should 
address all of the points.

This patch should have never been committed in the first place, even with one 
approval.

In D83088#2342760 , @dblaikie wrote:

> Sorry about the delays in review - but please revert this patch until we can 
> hash out a few more details. I really don't think this is the best direction 
> forward for a core abstraction & I'll do my best to explain why & try to 
> understand where you're coming from.

The (current) review policy 
(https://llvm.org/docs/CodeReview.html#can-code-be-reviewed-after-it-is-committed)
 is already clear enough:

"There is a strong expectation that authors respond promptly to post-commit 
feedback and address it. Failure to do so is cause for the patch to be 
reverted."

It's pretty clear that the paragraph applies to David's post-commit review.

> I'd really like to see examples like this ^ using the different abstractions 
> under consideration here (classic GraphTraits, CfgTraits dynamic and static 
> typed, perhaps what a static API would look like if it wasn't trying to be 
> dynamic API compatible).

This is the main request that was left unaddressed and the one that has the 
highest impact on the design of the API as well as all the following patches. 
The fact that they have all been approved doesn't mean this one must, too.

Their own approval just means those changes look good with the current 
interpretation, not that they must land. It's entirely possible that they 
continue to be good after the API has changed (if it has), in which case the 
approvals can just be restated. But they may well disappear or change 
completely due to the change in API, and will need new reviews to avoid having 
an already approved review change substantially in content.

> Indeed template code can get a bit weird - but I'm not sure it's quite enough 
> to justify the change in/complications of mulitple (static and dynamic) 
> abstractions here just yet. It might be that taking a more structured C++ 
> idiomatic approach to template design (like C++ standard container concept 
> abstractions) might lead to more usable code without /some/ complexities 
> (though may trade others).

And this is the main critic to the overall design choice, which I also agree 
completely. I'm not a big fan of complex template code myself, but the idioms 
are well known and they do simplify usage in many cases.

LLVM has had its fair share of discussions on the topics and we have developed 
multiple APIs and containers tho overcome deficiencies in the standard library, 
some of those concepts made into the standard. Some of those I have learned to 
like when I tried to implement otherwise and failed.

Only with concrete comparison of usage and patterns that we can make an 
informed decision and this is required to change a core concept of the compiler 
more than any other place. A single example where your pattern fits isn't 
enough to demonstrate that it will be generic and usable for all the other 
patterns that it may be used.

I'm sorry this delays more your work, but this is what working on an open 
source very large project entails. In comparison, LLVM is very fast compared to 
other OSS projects out there.

Also, echoing other people in this thread, this is more a case for an RFC 
thread on the list than code review. If the original thread didn't catch the 
attention of a public 

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle added a comment.

I replied on llvm-dev.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Mehdi AMINI via Phabricator via cfe-commits]

mehdi_amini added a comment.

In D83088#2350287 , @nhaehnle wrote:

> Hi Mehdi, this is not an appropriate place for this discussion. Yes, we have 
> a general rule that patches can be reverted if they're obviously broken (e.g. 
> build bot problems) or clearly violate some other standard. This is a good 
> rule, but it doesn't apply here. If you think it does, please state your case 
> in the email thread that I've started on llvm-dev for this very purpose. Just 
> one thing:

I strongly disagree: the bar for post-review commit is not lower than 
pre-commit review.

Again: please revert when someone has a concern, including a *design* concern 
with you patch.

> P.S.: It's easy to miss on Phabricator, but there is already a long stack of 
> patches which build on this

(this is part of my previous point).


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Matt Arsenault via Phabricator via cfe-commits]

arsenm added a comment.

In D83088#2348641 , @mehdi_amini wrote:

> In D83088#2347111 , @arsenm wrote:
>
>> In D83088#2346322 , @mehdi_amini 
>> wrote:
>>
>>> In D83088#2345540 , @nhaehnle 
>>> wrote:
>>>
 David, I don't think this is appropriate here. Let's take the discussion 
 to llvm-dev.
>>>
>>> Seems like David asked to revert in the meantime?
>>
>> -1 to reverting, which will just make the history messier with no tangible 
>> benefit
>
> This is the usual LLVM policy I believe: someone expressed a concern and ask 
> to revert. We revert and discuss first.
> So again: please revert.
>
> The messier history is not an argument: we revert so many times for any 
> random bot failures already, and our contribution guidelines still tell 
> people to push a "fake commit" with a whitespace change to test their access.

Unrelated, but I think the test commit process should be dropped

> I also see tangile benefits:
>
> - we don't start building dependencies on newly introduced API making a 
> revert more difficult later.
> - the burden of convincing of the approach is on the patch author, reverting 
> is forcing the discussion here.

This patch has been up for review for almost 4 months, with a corresponding RFC 
on llvm-dev. The last review comments were over 2 months ago. Coming back to 
this so long after to ask for a revert is an unworkable level of review 
paralysis


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle added a comment.

Hi Mehdi, this is not an appropriate place for this discussion. Yes, we have a 
general rule that patches can be reverted if they're obviously broken (e.g. 
build bot problems) or clearly violate some other standard. This is a good 
rule, but it doesn't apply here. If you think it does, please state your case 
in the email thread that I've started on llvm-dev for this very purpose. Just 
one thing:

> - the burden of convincing of the approach is on the patch author, reverting 
> is forcing the discussion here.

I was trying to have this conversation. I am more than happy to have it, and I 
would be happy for me people to participate! But what can I do if the only(!) 
person who voices concerns just goes into radio silence, and the total number 
of people who participate is small in any case, despite raising it on llvm-dev 
as well?

It is in fact the decision to **not** revert the change which is apparently 
required to force the discussion!

P.S.: It's easy to miss on Phabricator, but there is already a long stack of 
patches which build on this. In a way this is a good thing because it can 
inform the discussion, but I will hold off from pushing more for now even 
though many of them have already been accepted.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Mehdi AMINI via Phabricator via cfe-commits]

mehdi_amini added a comment.

In D83088#2347111 , @arsenm wrote:

> In D83088#2346322 , @mehdi_amini 
> wrote:
>
>> In D83088#2345540 , @nhaehnle wrote:
>>
>>> David, I don't think this is appropriate here. Let's take the discussion to 
>>> llvm-dev.
>>
>> Seems like David asked to revert in the meantime?
>
> -1 to reverting, which will just make the history messier with no tangible 
> benefit

This is the usual LLVM policy I believe: someone expressed a concern and ask to 
revert. We revert and discuss first.
So again: please revert.

The messier history is not an argument: we revert so many times for any random 
bot failures already, and our contribution guidelines still tell people to push 
a "fake commit" with a whitespace change to test their access.

I also see tangile benefits:

- we don't start building dependencies on newly introduced API making a revert 
more difficult later.
- the burden of convincing of the approach is on the patch author, reverting is 
forcing the discussion here.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Matt Arsenault via Phabricator via cfe-commits]

arsenm added a comment.

In D83088#2346322 , @mehdi_amini wrote:

> In D83088#2345540 , @nhaehnle wrote:
>
>> David, I don't think this is appropriate here. Let's take the discussion to 
>> llvm-dev.
>
> Seems like David asked to revert in the meantime?

-1 to reverting, which will just make the history messier with no tangible 
benefit


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Mehdi AMINI via Phabricator via cfe-commits]

mehdi_amini added a comment.

In D83088#2345540 , @nhaehnle wrote:

> David, I don't think this is appropriate here. Let's take the discussion to 
> llvm-dev.

Seems like David asked to revert in the meantime?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle added a comment.

David, I don't think this is appropriate here. Let's take the discussion to 
llvm-dev.




Comment at: mlir/include/mlir/IR/Dominance.h:49
+template <>
+struct llvm::CfgTraitsFor {
+  using CfgTraits = mlir::CfgTraits;

antiagainst wrote:
> rriddle wrote:
> > This seems to have broken the GCC5 build:
> > https://buildkite.com/mlir/mlir-core/builds/8739#7a957564-9850-487c-a814-c6818890bd14
> > 
> > ```
> > /mlir/include/mlir/IR/Dominance.h:49:14: error: specialization of 
> > 'template struct llvm::CfgTraitsFor' in different 
> > namespace [-fpermissive]
> >  struct llvm::CfgTraitsFor {
> >   ^
> > In file included from mlir/include/mlir/IR/Dominance.h:13:0,
> >  from mlir/lib/IR/Verifier.cpp:30:
> > llvm/include/llvm/Support/CfgTraits.h:294:44: error:   from definition of 
> > 'template struct llvm::CfgTraitsFor' [-fpermissive]
> >  template  struct CfgTraitsFor;
> > ```
> Pushed 
> https://github.com/llvm/llvm-project/commit/f2a06875b604c00cbe96e54363f4f5d28935d610
Apologies for the inconvenience, and thank you for taking care of it!


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[David Blaikie via Phabricator via cfe-commits]

dblaikie reopened this revision.
dblaikie added a comment.
This revision is now accepted and ready to land.

Sorry about the delays in review - but please revert this patch until we can 
hash out a few more details. I really don't think this is the best direction 
forward for a core abstraction & I'll do my best to explain why & try to 
understand where you're coming from.

In D83088#2232893 , @nhaehnle wrote:

> The most immediate problem is divergence analysis, which is extremely 
> complex and difficult to get right. If I had tried to fight the 
> accidental complexity that comes with attempting to write such an 
> algorithm as C++ templates in addition to the inherent complexity of the 
> algorithm at the same time, I'm not sure I would have been able to 
> produce anything workable at all.
>
> Frankly, I suspect that our dominator tree implementation also suffer 
> because of this, though at least dominator trees are much more well 
> studied in the academic literature, so that helps keep the inherent 
> complexity under control.

 I'm totally open to discussing making APIs more usable, for sure - though 
 I'm thinking it's likely a concept (like containers in the C++ standard 
 library) might be the better direction.

 Perhaps some code samples showing how one would interact (probably not 
 whole algorithms - maybe something simple like generating a dot diagram 
 for a graph) with these things given different APIs (traits, concepts, and 
 runtime polymorphism) - and implementations of each kind too.
>>>
>>> Take a look here for example: 
>>> https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/lib/Analysis/GenericConvergenceUtils.cpp#L499
>>>  -- this is obviously still fairly simple, but it's an example of printing 
>>> out the results of an analysis in a way that's generic over the underlying 
>>> CFG and SSA form.
>>
>> I'm having trouble following this example - I'm not sure what the CfgPrinter 
>> abstraction is/why it's first-class, and why this "print" function is 
>> calling what look like mutation operations like "appendBlocks". I guess 
>> perhaps the question is - what's it printing from and what's it printing to?
>>
>> Ah, I see, the "append" functions are accessors, of a sort. Returning a 
>> container might be more clear than using an out parameter - alternatively, a 
>> functor parameter (ala std::for_each) that is called for each element, that 
>> can then be used to populate an existing container if desired, or to do 
>> immediate processing without the need for an intermediate container.
>
> The code is trying to strike a balance here in terms of performance. Since 
> dynamic polymorphism is used, a functor-based traversal can't be inlined and 
> so the number of indirect function calls increases quite a bit. There are a 
> number of use cases where you really do want to just append successors or 
> predecessors to a vectors, like during a graph traversal. An example graph 
> traversal is here: 
> https://github.com/nhaehnle/llvm-project/blob/controlflow-wip-v7/llvm/lib/Analysis/GenericConvergenceUtils.cpp#L329

One way to simplify the dynamic polymorphism overhead of iteration would be to 
invert/limit the API - such as having a "node.forEachEdge([](const Edge& E) { 
... });" or the like.

>> Though the printer abstraction still strikes me as a bit strange - 
>> especially since it doesn't seem to be printing itself. This function was 
>> passed a printer and a stream - the printer prints to the stream (perhaps 
>> it'd make more sense for the printer to take the stream on construction) and 
>> the function isn't passed the thing to print at all - that thing is accessed 
>> from the printer. That seems fairly awkward to me - I'd expect a printing 
>> operation to take a thing to be printed and a thing to print to.
>
> Keep in mind that where those `printBlockName` / `printValue` methods are 
> used, they will always be mixed in with printing of other things. So the 
> alternative you're describing would result in code like:
>
>   dbgs() << " currently at: ";  // explicit stream
>   printer.printBlockName(block); // implicit stream
>   dbgs() << '\n'; // explicit stream
>
> I would argue that that ends up being more awkward because it mixes implicit 
> streams with explicitly given streams.
>
> We could perhaps add versions of the methods that return a `Printable` 
> object, so that we can write:
>
>   dbgs() << "currently at: " << printer.printableBlockName(block) << '\n';
>
> By the way, the main motivation for making the CfgPrinter a separate object 
> is that printing LLVM IR efficiently requires keeping a ModuleSlotTracker 
> around. Splitting the CfgPrinter off from the CfgInterface allows the 
> fast-path of code that doesn't want debug prints to not have to carry a 
> reference to a ModuleSlotTracker around, even if 

[PATCH] D83088: Introduce CfgTraits abstraction

[Lei Zhang via Phabricator via cfe-commits]

antiagainst added inline comments.



Comment at: mlir/include/mlir/IR/Dominance.h:49
+template <>
+struct llvm::CfgTraitsFor {
+  using CfgTraits = mlir::CfgTraits;

rriddle wrote:
> This seems to have broken the GCC5 build:
> https://buildkite.com/mlir/mlir-core/builds/8739#7a957564-9850-487c-a814-c6818890bd14
> 
> ```
> /mlir/include/mlir/IR/Dominance.h:49:14: error: specialization of 
> 'template struct llvm::CfgTraitsFor' in different 
> namespace [-fpermissive]
>  struct llvm::CfgTraitsFor {
>   ^
> In file included from mlir/include/mlir/IR/Dominance.h:13:0,
>  from mlir/lib/IR/Verifier.cpp:30:
> llvm/include/llvm/Support/CfgTraits.h:294:44: error:   from definition of 
> 'template struct llvm::CfgTraitsFor' [-fpermissive]
>  template  struct CfgTraitsFor;
> ```
Pushed 
https://github.com/llvm/llvm-project/commit/f2a06875b604c00cbe96e54363f4f5d28935d610


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[River Riddle via Phabricator via cfe-commits]

rriddle added inline comments.



Comment at: mlir/include/mlir/IR/Dominance.h:49
+template <>
+struct llvm::CfgTraitsFor {
+  using CfgTraits = mlir::CfgTraits;

This seems to have broken the GCC5 build:
https://buildkite.com/mlir/mlir-core/builds/8739#7a957564-9850-487c-a814-c6818890bd14

```
/mlir/include/mlir/IR/Dominance.h:49:14: error: specialization of 
'template struct llvm::CfgTraitsFor' in different 
namespace [-fpermissive]
 struct llvm::CfgTraitsFor {
  ^
In file included from mlir/include/mlir/IR/Dominance.h:13:0,
 from mlir/lib/IR/Verifier.cpp:30:
llvm/include/llvm/Support/CfgTraits.h:294:44: error:   from definition of 
'template struct llvm::CfgTraitsFor' [-fpermissive]
 template  struct CfgTraitsFor;
```


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.
Closed by commit rGc0cdd22c72fa: Introduce CfgTraits abstraction (authored by 
nhaehnle).

Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

Files:
  clang/include/clang/Analysis/Analyses/Dominators.h
  llvm/include/llvm/CodeGen/MachineCfgTraits.h
  llvm/include/llvm/IR/CFG.h
  llvm/include/llvm/Support/CfgTraits.h
  llvm/lib/CodeGen/CMakeLists.txt
  llvm/lib/CodeGen/MachineCfgTraits.cpp
  llvm/lib/IR/CFG.cpp
  llvm/lib/IR/CMakeLists.txt
  llvm/lib/Support/CMakeLists.txt
  llvm/lib/Support/CfgTraits.cpp
  llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
  mlir/include/mlir/IR/Dominance.h

Index: mlir/include/mlir/IR/Dominance.h
===
--- mlir/include/mlir/IR/Dominance.h
+++ mlir/include/mlir/IR/Dominance.h
@@ -10,8 +10,46 @@
 #define MLIR_IR_DOMINANCE_H
 
 #include "mlir/IR/RegionGraphTraits.h"
+#include "llvm/Support/CfgTraits.h"
 #include "llvm/Support/GenericDomTree.h"
 
+namespace mlir {
+
+/// Partial CFG traits for MLIR's CFG, without a value type.
+class CfgTraitsBase : public llvm::CfgTraitsBase {
+public:
+  using ParentType = Region;
+  using BlockRef = Block *;
+  using ValueRef = void;
+
+  static llvm::CfgBlockRef wrapRef(BlockRef block) {
+return makeOpaque(block);
+  }
+  static BlockRef unwrapRef(llvm::CfgBlockRef block) {
+return static_cast(getOpaque(block));
+  }
+};
+
+class CfgTraits : public llvm::CfgTraits {
+public:
+  static Region *getBlockParent(Block *block) { return block->getParent(); }
+
+  static auto predecessors(Block *block) {
+return llvm::inverse_children(block);
+  }
+
+  static auto successors(Block *block) {
+return llvm::children(block);
+  }
+};
+
+} // namespace mlir
+
+template <>
+struct llvm::CfgTraitsFor {
+  using CfgTraits = mlir::CfgTraits;
+};
+
 extern template class llvm::DominatorTreeBase;
 extern template class llvm::DominatorTreeBase;
 
Index: llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
===
--- llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
+++ llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
@@ -18,9 +18,42 @@
 #include "VPlan.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/Support/CfgTraits.h"
 
 namespace llvm {
 
+/// Partial CFG traits for VPlan's CFG, without a value type.
+class VPCfgTraitsBase : public CfgTraitsBase {
+public:
+  using ParentType = VPRegionBlock;
+  using BlockRef = VPBlockBase *;
+  using ValueRef = void;
+
+  static CfgBlockRef wrapRef(BlockRef block) {
+return makeOpaque(block);
+  }
+  static BlockRef unwrapRef(CfgBlockRef block) {
+return static_cast(getOpaque(block));
+  }
+};
+
+class VPCfgTraits : public CfgTraits {
+public:
+  static VPRegionBlock *getBlockParent(VPBlockBase *block) {
+return block->getParent();
+  }
+
+  static auto predecessors(VPBlockBase *block) {
+return llvm::inverse_children(block);
+  }
+
+  static auto successors(VPBlockBase *block) {
+return llvm::children(block);
+  }
+};
+
+template <> struct CfgTraitsFor { using CfgTraits = VPCfgTraits; };
+
 /// Template specialization of the standard LLVM dominator tree utility for
 /// VPBlockBases.
 using VPDominatorTree = DomTreeBase;
Index: llvm/lib/Support/CfgTraits.cpp
===
--- /dev/null
+++ llvm/lib/Support/CfgTraits.cpp
@@ -0,0 +1,14 @@
+//===- CfgTraits.cpp - Traits for generically working on CFGs ---*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===--===//
+
+#include "llvm/Support/CfgTraits.h"
+
+using namespace llvm;
+
+void CfgInterface::anchor() {}
+void CfgPrinter::anchor() {}
Index: llvm/lib/Support/CMakeLists.txt
===
--- llvm/lib/Support/CMakeLists.txt
+++ llvm/lib/Support/CMakeLists.txt
@@ -97,6 +97,7 @@
   BranchProbability.cpp
   BuryPointer.cpp
   CachePruning.cpp
+  CfgTraits.cpp
   circular_raw_ostream.cpp
   Chrono.cpp
   COM.cpp
Index: llvm/lib/IR/CMakeLists.txt
===
--- llvm/lib/IR/CMakeLists.txt
+++ llvm/lib/IR/CMakeLists.txt
@@ -4,6 +4,7 @@
   Attributes.cpp
   AutoUpgrade.cpp
   BasicBlock.cpp
+  CFG.cpp
   Comdat.cpp
   ConstantFold.cpp
   ConstantRange.cpp
Index: llvm/lib/IR/CFG.cpp
===
--- /dev/null
+++ llvm/lib/IR/CFG.cpp
@@ -0,0 +1,56 @@
+//===- CFG.cpp 

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle added a comment.
Herald added a subscriber: rdzhabarov.

ping^2


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle added a comment.
Herald added a subscriber: tatianashp.

ping


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle added inline comments.



Comment at: llvm/include/llvm/Support/CfgTraits.h:51
+
+  operator bool() const { return ptr != nullptr; }
+

dblaikie wrote:
> `operator bool` should be `explicit`
Done.



Comment at: llvm/include/llvm/Support/CfgTraits.h:53-54
+
+  bool operator==(CfgOpaqueType other) const { return ptr == other.ptr; }
+  bool operator!=(CfgOpaqueType other) const { return ptr != other.ptr; }
+};

dblaikie wrote:
> Preferably make any operator overload that can be a non-member, a non-member 
> - this ensures equal conversion handling on both the left and right hand side 
> of symmetric operators like these. (they can be friends if needed, but 
> doesn't look like it in this case - non-friend, non-members that call get() 
> should be fine here)
Done.



Comment at: llvm/include/llvm/Support/CfgTraits.h:90
+/// operations such as traversal of the CFG.
+class CfgTraitsBase {
+protected:

dblaikie wrote:
> Not sure if this benefits from being inherited from, versus being freely 
> accessible?
The idea here is to enforce via the type system that people use 
CfgTraits::{wrap,unwrap}Ref instead of having makeOpaque calls freely in random 
code.



Comment at: llvm/include/llvm/Support/CfgTraits.h:271-273
+template  struct CfgTraitsFor {
+  // using CfgTraits = ...;
+};

dblaikie wrote:
> This probably shouldn't be defined if it's only needed for specialization,  
> instead it can be declared:
> ```
> template struct CfgTraitsFor;
> ```
Interesting. So GraphTraits should arguably be changed similarly.



Comment at: llvm/include/llvm/Support/CfgTraits.h:287
+public:
+  virtual ~CfgInterface() {}
+

dblaikie wrote:
> prefer `= default` where possible
Done.



Comment at: llvm/include/llvm/Support/CfgTraits.h:337
+return Printable(
+[this, block](raw_ostream ) { printBlockName(out, block); });
+  }

dblaikie wrote:
> generally capture everything by ref `[&]` if the lambda is only used 
> locally/within the same expression or block
The lambda is returned via `Printable`.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle updated this revision to Diff 287441.
nhaehnle added a comment.

- cleanup operators on CfgOpaqueType
- address other review comments


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

Files:
  clang/include/clang/Analysis/Analyses/Dominators.h
  llvm/include/llvm/CodeGen/MachineCfgTraits.h
  llvm/include/llvm/IR/CFG.h
  llvm/include/llvm/Support/CfgTraits.h
  llvm/lib/CodeGen/CMakeLists.txt
  llvm/lib/CodeGen/MachineCfgTraits.cpp
  llvm/lib/IR/CFG.cpp
  llvm/lib/IR/CMakeLists.txt
  llvm/lib/Support/CMakeLists.txt
  llvm/lib/Support/CfgTraits.cpp
  llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
  mlir/include/mlir/IR/Dominance.h

Index: mlir/include/mlir/IR/Dominance.h
===
--- mlir/include/mlir/IR/Dominance.h
+++ mlir/include/mlir/IR/Dominance.h
@@ -10,8 +10,46 @@
 #define MLIR_IR_DOMINANCE_H
 
 #include "mlir/IR/RegionGraphTraits.h"
+#include "llvm/Support/CfgTraits.h"
 #include "llvm/Support/GenericDomTree.h"
 
+namespace mlir {
+
+/// Partial CFG traits for MLIR's CFG, without a value type.
+class CfgTraitsBase : public llvm::CfgTraitsBase {
+public:
+  using ParentType = Region;
+  using BlockRef = Block *;
+  using ValueRef = void;
+
+  static llvm::CfgBlockRef wrapRef(BlockRef block) {
+return makeOpaque(block);
+  }
+  static BlockRef unwrapRef(llvm::CfgBlockRef block) {
+return static_cast(getOpaque(block));
+  }
+};
+
+class CfgTraits : public llvm::CfgTraits {
+public:
+  static Region *getBlockParent(Block *block) { return block->getParent(); }
+
+  static auto predecessors(Block *block) {
+return llvm::inverse_children(block);
+  }
+
+  static auto successors(Block *block) {
+return llvm::children(block);
+  }
+};
+
+} // namespace mlir
+
+template <>
+struct llvm::CfgTraitsFor {
+  using CfgTraits = mlir::CfgTraits;
+};
+
 extern template class llvm::DominatorTreeBase;
 extern template class llvm::DominatorTreeBase;
 
Index: llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
===
--- llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
+++ llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
@@ -18,9 +18,42 @@
 #include "VPlan.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/Support/CfgTraits.h"
 
 namespace llvm {
 
+/// Partial CFG traits for VPlan's CFG, without a value type.
+class VPCfgTraitsBase : public CfgTraitsBase {
+public:
+  using ParentType = VPRegionBlock;
+  using BlockRef = VPBlockBase *;
+  using ValueRef = void;
+
+  static CfgBlockRef wrapRef(BlockRef block) {
+return makeOpaque(block);
+  }
+  static BlockRef unwrapRef(CfgBlockRef block) {
+return static_cast(getOpaque(block));
+  }
+};
+
+class VPCfgTraits : public CfgTraits {
+public:
+  static VPRegionBlock *getBlockParent(VPBlockBase *block) {
+return block->getParent();
+  }
+
+  static auto predecessors(VPBlockBase *block) {
+return llvm::inverse_children(block);
+  }
+
+  static auto successors(VPBlockBase *block) {
+return llvm::children(block);
+  }
+};
+
+template <> struct CfgTraitsFor { using CfgTraits = VPCfgTraits; };
+
 /// Template specialization of the standard LLVM dominator tree utility for
 /// VPBlockBases.
 using VPDominatorTree = DomTreeBase;
Index: llvm/lib/Support/CfgTraits.cpp
===
--- /dev/null
+++ llvm/lib/Support/CfgTraits.cpp
@@ -0,0 +1,14 @@
+//===- CfgTraits.cpp - Traits for generically working on CFGs ---*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===--===//
+
+#include "llvm/Support/CfgTraits.h"
+
+using namespace llvm;
+
+void CfgInterface::anchor() {}
+void CfgPrinter::anchor() {}
Index: llvm/lib/Support/CMakeLists.txt
===
--- llvm/lib/Support/CMakeLists.txt
+++ llvm/lib/Support/CMakeLists.txt
@@ -83,6 +83,7 @@
   BranchProbability.cpp
   BuryPointer.cpp
   CachePruning.cpp
+  CfgTraits.cpp
   circular_raw_ostream.cpp
   Chrono.cpp
   COM.cpp
Index: llvm/lib/IR/CMakeLists.txt
===
--- llvm/lib/IR/CMakeLists.txt
+++ llvm/lib/IR/CMakeLists.txt
@@ -4,6 +4,7 @@
   Attributes.cpp
   AutoUpgrade.cpp
   BasicBlock.cpp
+  CFG.cpp
   Comdat.cpp
   ConstantFold.cpp
   ConstantRange.cpp
Index: llvm/lib/IR/CFG.cpp
===
--- /dev/null
+++ llvm/lib/IR/CFG.cpp
@@ -0,0 +1,56 @@
+//===- CFG.cpp --*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache 

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle added a comment.

 The most immediate problem is divergence analysis, which is extremely 
 complex and difficult to get right. If I had tried to fight the accidental 
 complexity that comes with attempting to write such an algorithm as C++ 
 templates in addition to the inherent complexity of the algorithm at the 
 same time, I'm not sure I would have been able to produce anything 
 workable at all.

 Frankly, I suspect that our dominator tree implementation also suffer 
 because of this, though at least dominator trees are much more well 
 studied in the academic literature, so that helps keep the inherent 
 complexity under control.
>>>
>>> I'm totally open to discussing making APIs more usable, for sure - though 
>>> I'm thinking it's likely a concept (like containers in the C++ standard 
>>> library) might be the better direction.
>>>
>>> Perhaps some code samples showing how one would interact (probably not 
>>> whole algorithms - maybe something simple like generating a dot diagram for 
>>> a graph) with these things given different APIs (traits, concepts, and 
>>> runtime polymorphism) - and implementations of each kind too.
>>
>> Take a look here for example: 
>> https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/lib/Analysis/GenericConvergenceUtils.cpp#L499
>>  -- this is obviously still fairly simple, but it's an example of printing 
>> out the results of an analysis in a way that's generic over the underlying 
>> CFG and SSA form.
>
> I'm having trouble following this example - I'm not sure what the CfgPrinter 
> abstraction is/why it's first-class, and why this "print" function is calling 
> what look like mutation operations like "appendBlocks". I guess perhaps the 
> question is - what's it printing from and what's it printing to?
>
> Ah, I see, the "append" functions are accessors, of a sort. Returning a 
> container might be more clear than using an out parameter - alternatively, a 
> functor parameter (ala std::for_each) that is called for each element, that 
> can then be used to populate an existing container if desired, or to do 
> immediate processing without the need for an intermediate container.

The code is trying to strike a balance here in terms of performance. Since 
dynamic polymorphism is used, a functor-based traversal can't be inlined and so 
the number of indirect function calls increases quite a bit. There are a number 
of use cases where you really do want to just append successors or predecessors 
to a vectors, like during a graph traversal. An example graph traversal is 
here: 
https://github.com/nhaehnle/llvm-project/blob/controlflow-wip-v7/llvm/lib/Analysis/GenericConvergenceUtils.cpp#L329

> Though the printer abstraction still strikes me as a bit strange - especially 
> since it doesn't seem to be printing itself. This function was passed a 
> printer and a stream - the printer prints to the stream (perhaps it'd make 
> more sense for the printer to take the stream on construction) and the 
> function isn't passed the thing to print at all - that thing is accessed from 
> the printer. That seems fairly awkward to me - I'd expect a printing 
> operation to take a thing to be printed and a thing to print to.

Keep in mind that where those `printBlockName` / `printValue` methods are used, 
they will always be mixed in with printing of other things. So the alternative 
you're describing would result in code like:

  dbgs() << " currently at: ";  // explicit stream
  printer.printBlockName(block); // implicit stream
  dbgs() << '\n'; // explicit stream

I would argue that that ends up being more awkward because it mixes implicit 
streams with explicitly given streams.

We could perhaps add versions of the methods that return a `Printable` object, 
so that we can write:

  dbgs() << "currently at: " << printer.printableBlockName(block) << '\n';

By the way, the main motivation for making the CfgPrinter a separate object is 
that printing LLVM IR efficiently requires keeping a ModuleSlotTracker around. 
Splitting the CfgPrinter off from the CfgInterface allows the fast-path of code 
that doesn't want debug prints to not have to carry a reference to a 
ModuleSlotTracker around, even if it's just an empty std::unique_ptr. That's a 
comparatively small burden though, so I'd be fine with merging the CfgPrinter 
back into the CfgInterface.

> Perhaps setting aside the complexities of printing things - could you provide 
> an example of code, given a CfgGraph, that walks the graph - perhaps just 
> numbering the nodes/edges/etc to produce a dot graph? Showing what the code 
> would look like if it were passed a GraphTraits-implementing graph, a static 
> polymorphic CfgGraph, and a dynamically polymorphic GfgGraph - and also 
> showing what would be fandemantally possible with the CfgGraph that wouldn't 
> be possible with GraphTraits, if any such things exist (it's still unclear to 
> 

[PATCH] D83088: Introduce CfgTraits abstraction

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

(side note: this code review is a bit hard to follow with all the linting 
messages about naming - might be a bit more readable if it conformed to the 
naming conventions?)

In D83088#2227151 , @nhaehnle wrote:

> In D83088#2225415 , @dblaikie wrote:
>
 But I guess coming back to the original/broader design: What problems is 
 this intended to solve? The inability to write non-template algorithms 
 over graphs? What cost does that come with? Are there algorithms that are 
 a bit too complicated/unwieldy when done as templates? 
 If it's specifically the static/dynamic dispatch issue - I'm not sure the 
 type erasure and runtime overhead may be worth the tradeoff here, though 
 if it is - it'd be good to keep the non-dynamic version common, rather 
 than now having GraphTraits and CfgTraits done a bit differently, etc.
>>>
>>> It's not just over graphs, but taking SSA values into account as well -- 
>>> that is the key distinction between GraphTraits and CfgTraits.
>>
>> Not sure I follow - could you give an example of a graph where the 
>> GraphTraits concept of the Graph and the CfgTraits concept of the graph (or, 
>> perhaps more importantly - features of the graph/API surface area/properties 
>> you can expose through the CFG API/concept/thing but not through GraphTraits?
>
> See below.
>
>>> The most immediate problem is divergence analysis, which is extremely 
>>> complex and difficult to get right. If I had tried to fight the accidental 
>>> complexity that comes with attempting to write such an algorithm as C++ 
>>> templates in addition to the inherent complexity of the algorithm at the 
>>> same time, I'm not sure I would have been able to produce anything workable 
>>> at all.
>>>
>>> Frankly, I suspect that our dominator tree implementation also suffer 
>>> because of this, though at least dominator trees are much more well studied 
>>> in the academic literature, so that helps keep the inherent complexity 
>>> under control.
>>
>> I'm totally open to discussing making APIs more usable, for sure - though 
>> I'm thinking it's likely a concept (like containers in the C++ standard 
>> library) might be the better direction.
>>
>> Perhaps some code samples showing how one would interact (probably not whole 
>> algorithms - maybe something simple like generating a dot diagram for a 
>> graph) with these things given different APIs (traits, concepts, and runtime 
>> polymorphism) - and implementations of each kind too.
>
> Take a look here for example: 
> https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/lib/Analysis/GenericConvergenceUtils.cpp#L499
>  -- this is obviously still fairly simple, but it's an example of printing 
> out the results of an analysis in a way that's generic over the underlying 
> CFG and SSA form.

I'm having trouble following this example - I'm not sure what the CfgPrinter 
abstraction is/why it's first-class, and why this "print" function is calling 
what look like mutation operations like "appendBlocks". I guess perhaps the 
question is - what's it printing from and what's it printing to?

Ah, I see, the "append" functions are accessors, of a sort. Returning a 
container might be more clear than using an out parameter - alternatively, a 
functor parameter (ala std::for_each) that is called for each element, that can 
then be used to populate an existing container if desired, or to do immediate 
processing without the need for an intermediate container.

Though the printer abstraction still strikes me as a bit strange - especially 
since it doesn't seem to be printing itself. This function was passed a printer 
and a stream - the printer prints to the stream (perhaps it'd make more sense 
for the printer to take the stream on construction) and the function isn't 
passed the thing to print at all - that thing is accessed from the printer. 
That seems fairly awkward to me - I'd expect a printing operation to take a 
thing to be printed and a thing to print to.

Perhaps setting aside the complexities of printing things - could you provide 
an example of code, given a CfgGraph, that walks the graph - perhaps just 
numbering the nodes/edges/etc to produce a dot graph? Showing what the code 
would look like if it were passed a GraphTraits-implementing graph, a static 
polymorphic CfgGraph, and a dynamically polymorphic GfgGraph - and also showing 
what would be fandemantally possible with the CfgGraph that wouldn't be 
possible with GraphTraits, if any such things exist (it's still unclear to me 
whether CfgGraph has abstractions that don't exist in GraphTraits (eg: could 
you write a CfgGraph over GraphTraits? or would that be impossible because 
GraphTraits is missing concepts/CfgGraph doesn't apply to all 
GraphTraits-grahs? what subset of GraphTraits graphs does CfgGraph cover?).

> A statically 

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle added a comment.

> Based on your description and the DomTree patches, if I understand correctly, 
> the primary motivation is to facilitate writing CFG-representation-agnostic 
> algorithms/analyses (e.g., dominators, divergence, convergence analyses), 
> such that you can later lift the results back to the representation-aware 
> types? If that's correct, I support the overall goal. Having spent probably 
> ~weeks wrangling with domtree templates, this sounds like something that 
> could simplify life a lot and potentially cut down on compilation times & 
> sizes of llvm binaries.

Yes, that is the motivation.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Jakub Kuderski via Phabricator via cfe-commits]

kuhar added a comment.

Hi Nicoali,

In D83088#2227151 , @nhaehnle wrote:

> ...
> Take a look here for example: 
> https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/lib/Analysis/GenericConvergenceUtils.cpp#L499
>  -- this is obviously still fairly simple, but it's an example of printing 
> out the results of an analysis in a way that's generic over the underlying 
> CFG and SSA form. A statically polymorphic wrapper is here: 
> https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/include/llvm/Analysis/GenericConvergenceUtils.h#L569
>
> The simple example might be bearable writing as a template, precisely because 
> it's simple -- so only looking at simple examples is unlikely to really 
> capture the motivation. Really what the motivation boils down to is stuff 
> like this: 
> https://github.com/nhaehnle/llvm-project/blob/controlflow-wip-v7/llvm/lib/Analysis/GenericUniformAnalysis.cpp
>  -- I don't fancy writing all this as a template.
>
> Thid motivation would essentially go away if C++ could type-check against 
> traits in the way that Rust and other languages like it can -- but it can't, 
> so here we are.

Based on your description and the DomTree patches, if I understand correctly, 
the primary motivation is to facilitate writing CFG-representation-agnostic 
algorithms/analyses (e.g., dominators, divergence, convergence analyses), such 
that you can later lift the results back to the representation-aware types? If 
that's correct, I support the overall goal. Having spent probably ~weeks 
wrangling with domtree templates, this sounds like something that could 
simplify life a lot and potentially cut down on compilation times & sizes of 
llvm binaries.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle added a comment.

In D83088#2225415 , @dblaikie wrote:

>>> But I guess coming back to the original/broader design: What problems is 
>>> this intended to solve? The inability to write non-template algorithms over 
>>> graphs? What cost does that come with? Are there algorithms that are a bit 
>>> too complicated/unwieldy when done as templates? 
>>> If it's specifically the static/dynamic dispatch issue - I'm not sure the 
>>> type erasure and runtime overhead may be worth the tradeoff here, though if 
>>> it is - it'd be good to keep the non-dynamic version common, rather than 
>>> now having GraphTraits and CfgTraits done a bit differently, etc.
>>
>> It's not just over graphs, but taking SSA values into account as well -- 
>> that is the key distinction between GraphTraits and CfgTraits.
>
> Not sure I follow - could you give an example of a graph where the 
> GraphTraits concept of the Graph and the CfgTraits concept of the graph (or, 
> perhaps more importantly - features of the graph/API surface area/properties 
> you can expose through the CFG API/concept/thing but not through GraphTraits?

See below.

>> The most immediate problem is divergence analysis, which is extremely 
>> complex and difficult to get right. If I had tried to fight the accidental 
>> complexity that comes with attempting to write such an algorithm as C++ 
>> templates in addition to the inherent complexity of the algorithm at the 
>> same time, I'm not sure I would have been able to produce anything workable 
>> at all.
>>
>> Frankly, I suspect that our dominator tree implementation also suffer 
>> because of this, though at least dominator trees are much more well studied 
>> in the academic literature, so that helps keep the inherent complexity under 
>> control.
>
> I'm totally open to discussing making APIs more usable, for sure - though I'm 
> thinking it's likely a concept (like containers in the C++ standard library) 
> might be the better direction.
>
> Perhaps some code samples showing how one would interact (probably not whole 
> algorithms - maybe something simple like generating a dot diagram for a 
> graph) with these things given different APIs (traits, concepts, and runtime 
> polymorphism) - and implementations of each kind too.

Take a look here for example: 
https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/lib/Analysis/GenericConvergenceUtils.cpp#L499
 -- this is obviously still fairly simple, but it's an example of printing out 
the results of an analysis in a way that's generic over the underlying CFG and 
SSA form. A statically polymorphic wrapper is here: 
https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/include/llvm/Analysis/GenericConvergenceUtils.h#L569

The simple example might be bearable writing as a template, precisely because 
it's simple -- so only looking at simple examples is unlikely to really capture 
the motivation. Really what the motivation boils down to is stuff like this: 
https://github.com/nhaehnle/llvm-project/blob/controlflow-wip-v7/llvm/lib/Analysis/GenericUniformAnalysis.cpp
 -- I don't fancy writing all this as a template.

Thid motivation would essentially go away if C++ could type-check against 
traits in the way that Rust and other languages like it can -- but it can't, so 
here we are.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

In D83088#2224297 , @nhaehnle wrote:

>> Not sure that's the best place to be designing this fairly integral and 
>> complicated piece of infrastructure from, but hoping we can find some good 
>> places/solutions/etc.
>
> I sent an email to llvm-dev several weeks ago, but things seem to have moved 
> here. Either way is fine with me.

Yeah, sorry, I did see it - but didn't follow it in sufficient detail to 
understand the motivation/tradeoffs so well. (I do usually prefer to keep the 
design discussion on the design discussion threads, before worrying about the 
code specifics - but sometimes hard to understand it without code)

>> But I guess coming back to the original/broader design: What problems is 
>> this intended to solve? The inability to write non-template algorithms over 
>> graphs? What cost does that come with? Are there algorithms that are a bit 
>> too complicated/unwieldy when done as templates? 
>> If it's specifically the static/dynamic dispatch issue - I'm not sure the 
>> type erasure and runtime overhead may be worth the tradeoff here, though if 
>> it is - it'd be good to keep the non-dynamic version common, rather than now 
>> having GraphTraits and CfgTraits done a bit differently, etc.
>
> It's not just over graphs, but taking SSA values into account as well -- that 
> is the key distinction between GraphTraits and CfgTraits.

Not sure I follow - could you give an example of a graph where the GraphTraits 
concept of the Graph and the CfgTraits concept of the graph (or, perhaps more 
importantly - features of the graph/API surface area/properties you can expose 
through the CFG API/concept/thing but not through GraphTraits?

> The most immediate problem is divergence analysis, which is extremely complex 
> and difficult to get right. If I had tried to fight the accidental complexity 
> that comes with attempting to write such an algorithm as C++ templates in 
> addition to the inherent complexity of the algorithm at the same time, I'm 
> not sure I would have been able to produce anything workable at all.
>
> Frankly, I suspect that our dominator tree implementation also suffer because 
> of this, though at least dominator trees are much more well studied in the 
> academic literature, so that helps keep the inherent complexity under control.

I'm totally open to discussing making APIs more usable, for sure - though I'm 
thinking it's likely a concept (like containers in the C++ standard library) 
might be the better direction.

Perhaps some code samples showing how one would interact (probably not whole 
algorithms - maybe something simple like generating a dot diagram for a graph) 
with these things given different APIs (traits, concepts, and runtime 
polymorphism) - and implementations of each kind too.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle added a comment.

> Not sure that's the best place to be designing this fairly integral and 
> complicated piece of infrastructure from, but hoping we can find some good 
> places/solutions/etc.

I sent an email to llvm-dev several weeks ago, but things seem to have moved 
here. Either way is fine with me.

> But I guess coming back to the original/broader design: What problems is this 
> intended to solve? The inability to write non-template algorithms over 
> graphs? What cost does that come with? Are there algorithms that are a bit 
> too complicated/unwieldy when done as templates? 
> If it's specifically the static/dynamic dispatch issue - I'm not sure the 
> type erasure and runtime overhead may be worth the tradeoff here, though if 
> it is - it'd be good to keep the non-dynamic version common, rather than now 
> having GraphTraits and CfgTraits done a bit differently, etc.

It's not just over graphs, but taking SSA values into account as well -- that 
is the key distinction between GraphTraits and CfgTraits. The most immediate 
problem is divergence analysis, which is extremely complex and difficult to get 
right. If I had tried to fight the accidental complexity that comes with 
attempting to write such an algorithm as C++ templates in addition to the 
inherent complexity of the algorithm at the same time, I'm not sure I would 
have been able to produce anything workable at all.

Frankly, I suspect that our dominator tree implementation also suffer because 
of this, though at least dominator trees are much more well studied in the 
academic literature, so that helps keep the inherent complexity under control.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

In D83088#2218559 , @nhaehnle wrote:

> In D83088#2213886 , @dblaikie wrote:
>
>> In D83088#2213864 , @nhaehnle wrote:
>>
>>> In D83088#2213802 , @dblaikie 
>>> wrote:
>>>
 In D83088#2213797 , @nhaehnle 
 wrote:

> In D83088#2208611 , @dblaikie 
> wrote:
>
>> This seems like a strange hybrid between a static-polymorphism (with 
>> traits) and dynamic polymorphism (with base classes/virtual functions). 
>> Could this more readily be just one or the other? (sounds like you're 
>> leaning towards dynamic polymorphism)
>
> No, it's very much this way on purpose. The idea is to support the same 
> set of functionality as much as possible in both static **and** dynamic 
> polymorphism.

 Could it be implemented statically as a primary interface, with a dynamic 
 wrapper? (eg: a base class, then a derived class template that takes the 
 static CFG type to wrap into the dynamic type) keeping the two concepts 
 more clearly separated?
>>>
>>> That is how it is implemented. CfgTraits is the primary static interface, 
>>> and then CfgInterface / CfgInterfaceImpl is the dynamic wrapper.
>>
>> Ah, fair enough. The inheritance details in the traits class confused me a 
>> bit/I had a hard time following, with all the features being in the one 
>> patch. Might be easier separately, but not sure.
>>
>> Would it be possible for this not to use traits - I know @asbirlea and I had 
>> trouble with some things using GraphTraits owing to the traits API. An 
>> alternative would be to describe a CFGGraph concept (same as a standard 
>> container concept, for instance) - where there is a concrete graph object 
>> and that object is queried for things like nodes, edges, etc. (actually one 
>> of the significant things we tripped over was the API choice to navigate 
>> edges from a node itself without any extra state - which meant nodes/edge 
>> iteration had to carry state (potentially pointers back to the graph, etc) 
>> to be able to manifest their edges - trait or concept could both address 
>> this by, for traits, passing the graph as well as the node when querying the 
>> trait for edges, or for a concept passing the node back to the graph to 
>> query for edges).
>
> So there is a bit of a part here where I may admittedly be a bit confused 
> with the C++ lingo, since I don't actually like template programming that 
> much :)

Not sure that's the best place to be designing this fairly integral and 
complicated piece of infrastructure from, but hoping we can find some good 
places/solutions/etc.

> (Which is part of the motivation for this to begin with... so that I can do 
> the later changes in the stack here without *everything* being in templates.)

That concerns me a bit as a motivation - Perhaps the existing GraphTraits 
template approach could be improved, rather than adding another/separate set of 
complexity with both dynamic and static dispatch. (eg: containers in the C++ 
standard library don't support runtime polymorphism (you can't dynamically 
dispatch over a std::vector versus a std::list, for instance)).

What does/will this Cfg abstraction provide that's separate from the current 
Graph (provided by GraphTraits) abstraction? Does it provide things other than 
the ability to write these algorithms as non-templates? (in which case is the 
non-dynamic portion of this functionally equivalent to GraphTraits (but more as 
a concept than a trait, by the sounds of it))

> The way the `CfgTraits` is used is that you never use the `CfgTraits` class 
> directly except to inherit from it using CRTP (curiously recurring template 
> pattern).

side note: Using the same name in multiple namespaces makes this a bit harder 
to read than it might otherwise be (clang::CfgTraits deriving from 
llvm::CfgTraits, etc)
So currently you write a MyCfgTraitsBase, deriving from llvm::CfgTraitsBase

  class MyCfgTraitsBase : public llvm::CfgTraitsBase { ...

then you write CfgTraits that derieves from that with both CRTP and the 
MyCfgTraitsBase

  class MyCfgTraits : public llvm::CfgTraits

Could this be simplified by moving the MyCfgTraitsBase stuff into MyCfgTraits, 
and having llvm::CfgTraits with just one template parameter, the derived class?

> When writing algorithms that want to be generic over the type of CFG, those 
> algorithms then have a derived class of CfgTraits as a template parameter. 
> For example, D83094  adds a 
> `GenericCycleInfo` template class, where the template parameter 
> should be set to e.g. `IrCfgTraits`, if you want cycle info on LLVM IR, or to 
> `MachineCfgTraits`, if you want cycle info on MachineIR. Both of these 
> classes 

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle added a comment.

In D83088#2213886 , @dblaikie wrote:

> In D83088#2213864 , @nhaehnle wrote:
>
>> In D83088#2213802 , @dblaikie wrote:
>>
>>> In D83088#2213797 , @nhaehnle 
>>> wrote:
>>>
 In D83088#2208611 , @dblaikie 
 wrote:

> This seems like a strange hybrid between a static-polymorphism (with 
> traits) and dynamic polymorphism (with base classes/virtual functions). 
> Could this more readily be just one or the other? (sounds like you're 
> leaning towards dynamic polymorphism)

 No, it's very much this way on purpose. The idea is to support the same 
 set of functionality as much as possible in both static **and** dynamic 
 polymorphism.
>>>
>>> Could it be implemented statically as a primary interface, with a dynamic 
>>> wrapper? (eg: a base class, then a derived class template that takes the 
>>> static CFG type to wrap into the dynamic type) keeping the two concepts 
>>> more clearly separated?
>>
>> That is how it is implemented. CfgTraits is the primary static interface, 
>> and then CfgInterface / CfgInterfaceImpl is the dynamic wrapper.
>
> Ah, fair enough. The inheritance details in the traits class confused me a 
> bit/I had a hard time following, with all the features being in the one 
> patch. Might be easier separately, but not sure.
>
> Would it be possible for this not to use traits - I know @asbirlea and I had 
> trouble with some things using GraphTraits owing to the traits API. An 
> alternative would be to describe a CFGGraph concept (same as a standard 
> container concept, for instance) - where there is a concrete graph object and 
> that object is queried for things like nodes, edges, etc. (actually one of 
> the significant things we tripped over was the API choice to navigate edges 
> from a node itself without any extra state - which meant nodes/edge iteration 
> had to carry state (potentially pointers back to the graph, etc) to be able 
> to manifest their edges - trait or concept could both address this by, for 
> traits, passing the graph as well as the node when querying the trait for 
> edges, or for a concept passing the node back to the graph to query for 
> edges).

So there is a bit of a part here where I may admittedly be a bit confused with 
the C++ lingo, since I don't actually like template programming that much :)  
(Which is part of the motivation for this to begin with... so that I can do the 
later changes in the stack here without *everything* being in templates.)

The way the `CfgTraits` is used is that you never use the `CfgTraits` class 
directly except to inherit from it using CRTP (curiously recurring template 
pattern). When writing algorithms that want to be generic over the type of CFG, 
those algorithms then have a derived class of CfgTraits as a template 
parameter. For example, D83094  adds a 
`GenericCycleInfo` template class, where the template parameter 
should be set to e.g. `IrCfgTraits`, if you want cycle info on LLVM IR, or to 
`MachineCfgTraits`, if you want cycle info on MachineIR. Both of these classes 
are derived from `CfgTraits`.

It is definitely different from how `GraphTraits` works, which you use it as 
`GraphTraits`, and then `GraphTraits` etc. are 
specialized implementations. If `GraphTraits` worked the way that `CfgTraits` 
works, then we'd instead have classes like `BasicBlockGraphTraits`.

So to sum it up, all this sounds a bit to me like maybe calling `CfgTraits` 
"traits" is wrong? Is that what you're saying here? You can't just call it 
`Cfg` though, because it's *not* a CFG -- it's a kind of interface to a CFG 
which is designed for static polymorphism, unlike `CfgInterface` which is 
designed for dynamic polymorphism. Getting the names right is important, 
unfortunately I admit that I'm a bit lost there. "Traits" seemed like the 
closest thing to what I want, but I'm definitely open to suggestions.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

In D83088#2213864 , @nhaehnle wrote:

> In D83088#2213802 , @dblaikie wrote:
>
>> In D83088#2213797 , @nhaehnle wrote:
>>
>>> In D83088#2208611 , @dblaikie 
>>> wrote:
>>>
 This seems like a strange hybrid between a static-polymorphism (with 
 traits) and dynamic polymorphism (with base classes/virtual functions). 
 Could this more readily be just one or the other? (sounds like you're 
 leaning towards dynamic polymorphism)
>>>
>>> No, it's very much this way on purpose. The idea is to support the same set 
>>> of functionality as much as possible in both static **and** dynamic 
>>> polymorphism.
>>
>> Could it be implemented statically as a primary interface, with a dynamic 
>> wrapper? (eg: a base class, then a derived class template that takes the 
>> static CFG type to wrap into the dynamic type) keeping the two concepts more 
>> clearly separated?
>
> That is how it is implemented. CfgTraits is the primary static interface, and 
> then CfgInterface / CfgInterfaceImpl is the dynamic wrapper.

Ah, fair enough. The inheritance details in the traits class confused me a 
bit/I had a hard time following, with all the features being in the one patch. 
Might be easier separately, but not sure.

Would it be possible for this not to use traits - I know @asbirlea and I had 
trouble with some things using GraphTraits owing to the traits API. An 
alternative would be to describe a CFGGraph concept (same as a standard 
container concept, for instance) - where there is a concrete graph object and 
that object is queried for things like nodes, edges, etc. (actually one of the 
significant things we tripped over was the API choice to navigate edges from a 
node itself without any extra state - which meant nodes/edge iteration had to 
carry state (potentially pointers back to the graph, etc) to be able to 
manifest their edges - trait or concept could both address this by, for traits, 
passing the graph as well as the node when querying the trait for edges, or for 
a concept passing the node back to the graph to query for edges).


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle added a comment.

In D83088#2213802 , @dblaikie wrote:

> In D83088#2213797 , @nhaehnle wrote:
>
>> In D83088#2208611 , @dblaikie wrote:
>>
>>> This seems like a strange hybrid between a static-polymorphism (with 
>>> traits) and dynamic polymorphism (with base classes/virtual functions). 
>>> Could this more readily be just one or the other? (sounds like you're 
>>> leaning towards dynamic polymorphism)
>>
>> No, it's very much this way on purpose. The idea is to support the same set 
>> of functionality as much as possible in both static **and** dynamic 
>> polymorphism.
>
> Could it be implemented statically as a primary interface, with a dynamic 
> wrapper? (eg: a base class, then a derived class template that takes the 
> static CFG type to wrap into the dynamic type) keeping the two concepts more 
> clearly separated?

That is how it is implemented. CfgTraits is the primary static interface, and 
then CfgInterface / CfgInterfaceImpl is the dynamic wrapper.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

In D83088#2213797 , @nhaehnle wrote:

> In D83088#2208611 , @dblaikie wrote:
>
>> This seems like a strange hybrid between a static-polymorphism (with traits) 
>> and dynamic polymorphism (with base classes/virtual functions). Could this 
>> more readily be just one or the other? (sounds like you're leaning towards 
>> dynamic polymorphism)
>
> No, it's very much this way on purpose. The idea is to support the same set 
> of functionality as much as possible in both static **and** dynamic 
> polymorphism.

Could it be implemented statically as a primary interface, with a dynamic 
wrapper? (eg: a base class, then a derived class template that takes the static 
CFG type to wrap into the dynamic type) keeping the two concepts more clearly 
separated?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle added a comment.

In D83088#2208611 , @dblaikie wrote:

> This seems like a strange hybrid between a static-polymorphism (with traits) 
> and dynamic polymorphism (with base classes/virtual functions). Could this 
> more readily be just one or the other? (sounds like you're leaning towards 
> dynamic polymorphism)

No, it's very much this way on purpose. The idea is to support the same set of 
functionality as much as possible in both static **and** dynamic polymorphism.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[David Blaikie via Phabricator via cfe-commits]

dblaikie added a comment.

This seems like a strange hybrid between a static-polymorphism (with traits) 
and dynamic polymorphism (with base classes/virtual functions). Could this more 
readily be just one or the other? (sounds like you're leaning towards dynamic 
polymorphism)


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle updated this revision to Diff 284195.
nhaehnle marked 2 inline comments as done.
nhaehnle added a comment.

  v7:
  - std::forward fix in wrapping_iterator
  - fix typos


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

Files:
  clang/include/clang/Analysis/Analyses/Dominators.h
  llvm/include/llvm/CodeGen/MachineCfgTraits.h
  llvm/include/llvm/IR/CFG.h
  llvm/include/llvm/Support/CfgTraits.h
  llvm/lib/CodeGen/CMakeLists.txt
  llvm/lib/CodeGen/MachineCfgTraits.cpp
  llvm/lib/IR/CFG.cpp
  llvm/lib/IR/CMakeLists.txt
  llvm/lib/Support/CMakeLists.txt
  llvm/lib/Support/CfgTraits.cpp
  llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
  mlir/include/mlir/IR/Dominance.h

Index: mlir/include/mlir/IR/Dominance.h
===
--- mlir/include/mlir/IR/Dominance.h
+++ mlir/include/mlir/IR/Dominance.h
@@ -10,8 +10,46 @@
 #define MLIR_IR_DOMINANCE_H
 
 #include "mlir/IR/RegionGraphTraits.h"
+#include "llvm/Support/CfgTraits.h"
 #include "llvm/Support/GenericDomTree.h"
 
+namespace mlir {
+
+/// Partial CFG traits for MLIR's CFG, without a value type.
+class CfgTraitsBase : public llvm::CfgTraitsBase {
+public:
+  using ParentType = Region;
+  using BlockRef = Block *;
+  using ValueRef = void;
+
+  static llvm::CfgBlockRef wrapRef(BlockRef block) {
+return makeOpaque(block);
+  }
+  static BlockRef unwrapRef(llvm::CfgBlockRef block) {
+return static_cast(getOpaque(block));
+  }
+};
+
+class CfgTraits : public llvm::CfgTraits {
+public:
+  static Region *getBlockParent(Block *block) { return block->getParent(); }
+
+  static auto predecessors(Block *block) {
+return llvm::inverse_children(block);
+  }
+
+  static auto successors(Block *block) {
+return llvm::children(block);
+  }
+};
+
+} // namespace mlir
+
+template <>
+struct llvm::CfgTraitsFor {
+  using CfgTraits = mlir::CfgTraits;
+};
+
 extern template class llvm::DominatorTreeBase;
 extern template class llvm::DominatorTreeBase;
 
Index: llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
===
--- llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
+++ llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
@@ -18,9 +18,42 @@
 #include "VPlan.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/Support/CfgTraits.h"
 
 namespace llvm {
 
+/// Partial CFG traits for VPlan's CFG, without a value type.
+class VPCfgTraitsBase : public CfgTraitsBase {
+public:
+  using ParentType = VPRegionBlock;
+  using BlockRef = VPBlockBase *;
+  using ValueRef = void;
+
+  static CfgBlockRef wrapRef(BlockRef block) {
+return makeOpaque(block);
+  }
+  static BlockRef unwrapRef(CfgBlockRef block) {
+return static_cast(getOpaque(block));
+  }
+};
+
+class VPCfgTraits : public CfgTraits {
+public:
+  static VPRegionBlock *getBlockParent(VPBlockBase *block) {
+return block->getParent();
+  }
+
+  static auto predecessors(VPBlockBase *block) {
+return llvm::inverse_children(block);
+  }
+
+  static auto successors(VPBlockBase *block) {
+return llvm::children(block);
+  }
+};
+
+template <> struct CfgTraitsFor { using CfgTraits = VPCfgTraits; };
+
 /// Template specialization of the standard LLVM dominator tree utility for
 /// VPBlockBases.
 using VPDominatorTree = DomTreeBase;
Index: llvm/lib/Support/CfgTraits.cpp
===
--- /dev/null
+++ llvm/lib/Support/CfgTraits.cpp
@@ -0,0 +1,14 @@
+//===- CfgTraits.cpp - Traits for generically working on CFGs ---*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===--===//
+
+#include "llvm/Support/CfgTraits.h"
+
+using namespace llvm;
+
+void CfgInterface::anchor() {}
+void CfgPrinter::anchor() {}
Index: llvm/lib/Support/CMakeLists.txt
===
--- llvm/lib/Support/CMakeLists.txt
+++ llvm/lib/Support/CMakeLists.txt
@@ -71,6 +71,7 @@
   BranchProbability.cpp
   BuryPointer.cpp
   CachePruning.cpp
+  CfgTraits.cpp
   circular_raw_ostream.cpp
   Chrono.cpp
   COM.cpp
Index: llvm/lib/IR/CMakeLists.txt
===
--- llvm/lib/IR/CMakeLists.txt
+++ llvm/lib/IR/CMakeLists.txt
@@ -4,6 +4,7 @@
   Attributes.cpp
   AutoUpgrade.cpp
   BasicBlock.cpp
+  CFG.cpp
   Comdat.cpp
   ConstantFold.cpp
   ConstantRange.cpp
Index: llvm/lib/IR/CFG.cpp
===
--- /dev/null
+++ llvm/lib/IR/CFG.cpp
@@ -0,0 +1,56 @@
+//===- CFG.cpp --*- C++ -*-===//
+//
+// Part of 

[PATCH] D83088: Introduce CfgTraits abstraction

[Matt Arsenault via Phabricator via cfe-commits]

arsenm added inline comments.



Comment at: clang/include/clang/Analysis/Analyses/Dominators.h:50
+
+  // Clang's CFG contains nullpointers for unreachable succesors, e.g. when an
+  // if statement's condition is always false, it's 'then' branch is 
represented

Missing space nullpointers, missing s succesors



Comment at: clang/include/clang/Analysis/Analyses/Dominators.h:51
+  // Clang's CFG contains nullpointers for unreachable succesors, e.g. when an
+  // if statement's condition is always false, it's 'then' branch is 
represented
+  // with a nullptr. Account for this in the predecessors / successors

s/it's/its/


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle updated this revision to Diff 280481.
nhaehnle marked an inline comment as done.
nhaehnle added a comment.

  v6:
  - implement predecessors/successors for all CfgTraits implementations
  - fix error in unwrapRange
  - rename toGeneric/fromGeneric into wrapRef/unwrapRef to have naming
that is consistent with {wrap,unwrap}{Iterator,Range}
  - use getVRegDef instead of getUniqueVRegDef


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

Files:
  clang/include/clang/Analysis/Analyses/Dominators.h
  llvm/include/llvm/CodeGen/MachineCfgTraits.h
  llvm/include/llvm/IR/CFG.h
  llvm/include/llvm/Support/CfgTraits.h
  llvm/lib/CodeGen/CMakeLists.txt
  llvm/lib/CodeGen/MachineCfgTraits.cpp
  llvm/lib/IR/CFG.cpp
  llvm/lib/IR/CMakeLists.txt
  llvm/lib/Support/CMakeLists.txt
  llvm/lib/Support/CfgTraits.cpp
  llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
  mlir/include/mlir/IR/Dominance.h

Index: mlir/include/mlir/IR/Dominance.h
===
--- mlir/include/mlir/IR/Dominance.h
+++ mlir/include/mlir/IR/Dominance.h
@@ -10,8 +10,46 @@
 #define MLIR_IR_DOMINANCE_H
 
 #include "mlir/IR/RegionGraphTraits.h"
+#include "llvm/Support/CfgTraits.h"
 #include "llvm/Support/GenericDomTree.h"
 
+namespace mlir {
+
+/// Partial CFG traits for MLIR's CFG, without a value type.
+class CfgTraitsBase : public llvm::CfgTraitsBase {
+public:
+  using ParentType = Region;
+  using BlockRef = Block *;
+  using ValueRef = void;
+
+  static llvm::CfgBlockRef wrapRef(BlockRef block) {
+return makeOpaque(block);
+  }
+  static BlockRef unwrapRef(llvm::CfgBlockRef block) {
+return static_cast(getOpaque(block));
+  }
+};
+
+class CfgTraits : public llvm::CfgTraits {
+public:
+  static Region *getBlockParent(Block *block) { return block->getParent(); }
+
+  static auto predecessors(Block *block) {
+return llvm::inverse_children(block);
+  }
+
+  static auto successors(Block *block) {
+return llvm::children(block);
+  }
+};
+
+} // namespace mlir
+
+template <>
+struct llvm::CfgTraitsFor {
+  using CfgTraits = mlir::CfgTraits;
+};
+
 extern template class llvm::DominatorTreeBase;
 extern template class llvm::DominatorTreeBase;
 
Index: llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
===
--- llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
+++ llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
@@ -18,9 +18,42 @@
 #include "VPlan.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/Support/CfgTraits.h"
 
 namespace llvm {
 
+/// Partial CFG traits for VPlan's CFG, without a value type.
+class VPCfgTraitsBase : public CfgTraitsBase {
+public:
+  using ParentType = VPRegionBlock;
+  using BlockRef = VPBlockBase *;
+  using ValueRef = void;
+
+  static CfgBlockRef wrapRef(BlockRef block) {
+return makeOpaque(block);
+  }
+  static BlockRef unwrapRef(CfgBlockRef block) {
+return static_cast(getOpaque(block));
+  }
+};
+
+class VPCfgTraits : public CfgTraits {
+public:
+  static VPRegionBlock *getBlockParent(VPBlockBase *block) {
+return block->getParent();
+  }
+
+  static auto predecessors(VPBlockBase *block) {
+return llvm::inverse_children(block);
+  }
+
+  static auto successors(VPBlockBase *block) {
+return llvm::children(block);
+  }
+};
+
+template <> struct CfgTraitsFor { using CfgTraits = VPCfgTraits; };
+
 /// Template specialization of the standard LLVM dominator tree utility for
 /// VPBlockBases.
 using VPDominatorTree = DomTreeBase;
Index: llvm/lib/Support/CfgTraits.cpp
===
--- /dev/null
+++ llvm/lib/Support/CfgTraits.cpp
@@ -0,0 +1,14 @@
+//===- CfgTraits.cpp - Traits for generically working on CFGs ---*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===--===//
+
+#include "llvm/Support/CfgTraits.h"
+
+using namespace llvm;
+
+void CfgInterface::anchor() {}
+void CfgPrinter::anchor() {}
Index: llvm/lib/Support/CMakeLists.txt
===
--- llvm/lib/Support/CMakeLists.txt
+++ llvm/lib/Support/CMakeLists.txt
@@ -71,6 +71,7 @@
   BranchProbability.cpp
   BuryPointer.cpp
   CachePruning.cpp
+  CfgTraits.cpp
   circular_raw_ostream.cpp
   Chrono.cpp
   COM.cpp
Index: llvm/lib/IR/CMakeLists.txt
===
--- llvm/lib/IR/CMakeLists.txt
+++ llvm/lib/IR/CMakeLists.txt
@@ -4,6 +4,7 @@
   Attributes.cpp
   AutoUpgrade.cpp
   BasicBlock.cpp
+  CFG.cpp
   Comdat.cpp
   ConstantFold.cpp
   ConstantRange.cpp
Index: llvm/lib/IR/CFG.cpp

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle marked 3 inline comments as done.
nhaehnle added inline comments.



Comment at: llvm/include/llvm/CodeGen/MachineCfgTraits.h:44
+// use on a 32-bit architecture.
+assert(wrapped != (uintptr_t)-1 && wrapped != (uintptr_t)-2);
+

arsenm wrote:
> I feel like there should be a better way to do this; we should probably have 
> an assert where virtual registers are created
The reason for doing it here is that this is the place where the reinterpret 
happens. If the check is elsewhere, it's easy to miss by a user of this.



Comment at: llvm/include/llvm/CodeGen/MachineCfgTraits.h:101
+  return nullptr;
+return m_regInfo->getUniqueVRegDef(value)->getParent();
+  }

arsenm wrote:
> I think regular getVRegDef is preferable for SSA MIR
Fixed locally.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Matt Arsenault via Phabricator via cfe-commits]

arsenm added inline comments.



Comment at: llvm/include/llvm/CodeGen/MachineCfgTraits.h:44
+// use on a 32-bit architecture.
+assert(wrapped != (uintptr_t)-1 && wrapped != (uintptr_t)-2);
+

I feel like there should be a better way to do this; we should probably have an 
assert where virtual registers are created



Comment at: llvm/include/llvm/CodeGen/MachineCfgTraits.h:101
+  return nullptr;
+return m_regInfo->getUniqueVRegDef(value)->getParent();
+  }

I think regular getVRegDef is preferable for SSA MIR


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle marked an inline comment as done.
nhaehnle added inline comments.



Comment at: llvm/include/llvm/CodeGen/MachineCfgTraits.h:136-138
+  // Prefer to avoid support for bundled instructions as long as we
+  // don't really need it.
+  assert(!m_instr->isBundle());

arsenm wrote:
> nhaehnle wrote:
> > arsenm wrote:
> > > I've been thinking about more aggressively using bundles around call 
> > > sites to handle waterfall looping around divergent calls with SGPR 
> > > arguments
> > Hmm, so what's the correct iteration behavior in the presence of bundles? 
> > Iterate over all instructions in the bundle (which is that 
> > MachineBasicBlock::instr_iterator does) and only iterate over explicit 
> > defs? I think that's what makes the most sense, and what I'm going with for 
> > now...
> I don't think this actually needs to specially consider bundles. The BUNDLE 
> itself is supposed to have the uses/defs that cover all the uses/defs inside 
> the bundle. You shouldn't need to worry about the individual instructions
This is what should be there with the last change :)


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Matt Arsenault via Phabricator via cfe-commits]

arsenm added inline comments.



Comment at: llvm/include/llvm/CodeGen/MachineCfgTraits.h:136-138
+  // Prefer to avoid support for bundled instructions as long as we
+  // don't really need it.
+  assert(!m_instr->isBundle());

nhaehnle wrote:
> arsenm wrote:
> > I've been thinking about more aggressively using bundles around call sites 
> > to handle waterfall looping around divergent calls with SGPR arguments
> Hmm, so what's the correct iteration behavior in the presence of bundles? 
> Iterate over all instructions in the bundle (which is that 
> MachineBasicBlock::instr_iterator does) and only iterate over explicit defs? 
> I think that's what makes the most sense, and what I'm going with for now...
I don't think this actually needs to specially consider bundles. The BUNDLE 
itself is supposed to have the uses/defs that cover all the uses/defs inside 
the bundle. You shouldn't need to worry about the individual instructions


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle updated this revision to Diff 275811.
nhaehnle marked 4 inline comments as done.
nhaehnle added a comment.

- fix MachineCfgTraits::blockdef_iterator and allow it to iterate over the 
instructions in a bundle
- use MachineBasicBlock::printName


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088

Files:
  clang/include/clang/Analysis/Analyses/Dominators.h
  llvm/include/llvm/CodeGen/MachineCfgTraits.h
  llvm/include/llvm/IR/CFG.h
  llvm/include/llvm/Support/CfgTraits.h
  llvm/lib/CodeGen/CMakeLists.txt
  llvm/lib/CodeGen/MachineCfgTraits.cpp
  llvm/lib/IR/CFG.cpp
  llvm/lib/IR/CMakeLists.txt
  llvm/lib/Support/CMakeLists.txt
  llvm/lib/Support/CfgTraits.cpp
  llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
  mlir/include/mlir/IR/Dominance.h

Index: mlir/include/mlir/IR/Dominance.h
===
--- mlir/include/mlir/IR/Dominance.h
+++ mlir/include/mlir/IR/Dominance.h
@@ -10,8 +10,37 @@
 #define MLIR_IR_DOMINANCE_H
 
 #include "mlir/IR/RegionGraphTraits.h"
+#include "llvm/Support/CfgTraits.h"
 #include "llvm/Support/GenericDomTree.h"
 
+namespace mlir {
+
+/// Partial CFG traits for MLIR's CFG, without a value type.
+class CfgTraitsBase : public llvm::CfgTraitsBase {
+public:
+  using ParentType = Region;
+  using BlockRef = Block *;
+  using ValueRef = void;
+
+  static llvm::CfgBlockRef toGeneric(BlockRef block) {
+return makeOpaque(block);
+  }
+  static BlockRef fromGeneric(llvm::CfgBlockRef block) {
+return static_cast(getOpaque(block));
+  }
+};
+
+class CfgTraits : public llvm::CfgTraits {
+  static Region *getBlockParent(Block *block) { return block->getParent(); }
+};
+
+} // namespace mlir
+
+template <>
+struct llvm::CfgTraitsFor {
+  using CfgTraits = mlir::CfgTraits;
+};
+
 extern template class llvm::DominatorTreeBase;
 extern template class llvm::DominatorTreeBase;
 
Index: llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
===
--- llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
+++ llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
@@ -18,9 +18,33 @@
 #include "VPlan.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/Support/CfgTraits.h"
 
 namespace llvm {
 
+/// Partial CFG traits for VPlan's CFG, without a value type.
+class VPCfgTraitsBase : public CfgTraitsBase {
+public:
+  using ParentType = VPRegionBlock;
+  using BlockRef = VPBlockBase *;
+  using ValueRef = void;
+
+  static CfgBlockRef toGeneric(BlockRef block) {
+return makeOpaque(block);
+  }
+  static BlockRef fromGeneric(CfgBlockRef block) {
+return static_cast(getOpaque(block));
+  }
+};
+
+class VPCfgTraits : public CfgTraits {
+  static VPRegionBlock *getBlockParent(VPBlockBase *block) {
+return block->getParent();
+  }
+};
+
+template <> struct CfgTraitsFor { using CfgTraits = VPCfgTraits; };
+
 /// Template specialization of the standard LLVM dominator tree utility for
 /// VPBlockBases.
 using VPDominatorTree = DomTreeBase;
Index: llvm/lib/Support/CfgTraits.cpp
===
--- /dev/null
+++ llvm/lib/Support/CfgTraits.cpp
@@ -0,0 +1,14 @@
+//===- CfgTraits.cpp - Traits for generically working on CFGs ---*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===--===//
+
+#include "llvm/Support/CfgTraits.h"
+
+using namespace llvm;
+
+void CfgInterface::anchor() {}
+void CfgPrinter::anchor() {}
Index: llvm/lib/Support/CMakeLists.txt
===
--- llvm/lib/Support/CMakeLists.txt
+++ llvm/lib/Support/CMakeLists.txt
@@ -71,6 +71,7 @@
   BranchProbability.cpp
   BuryPointer.cpp
   CachePruning.cpp
+  CfgTraits.cpp
   circular_raw_ostream.cpp
   Chrono.cpp
   COM.cpp
Index: llvm/lib/IR/CMakeLists.txt
===
--- llvm/lib/IR/CMakeLists.txt
+++ llvm/lib/IR/CMakeLists.txt
@@ -4,6 +4,7 @@
   Attributes.cpp
   AutoUpgrade.cpp
   BasicBlock.cpp
+  CFG.cpp
   Comdat.cpp
   ConstantFold.cpp
   ConstantRange.cpp
Index: llvm/lib/IR/CFG.cpp
===
--- /dev/null
+++ llvm/lib/IR/CFG.cpp
@@ -0,0 +1,56 @@
+//===- CFG.cpp --*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===--===//
+
+#include "llvm/IR/CFG.h"

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle added inline comments.



Comment at: llvm/include/llvm/CodeGen/MachineCfgTraits.h:133
+  ++m_def;
+  if (m_def == m_instr->defs().end()) {
+++m_instr;

arsenm wrote:
> != return early?
The logic is actually subtly broken in the presence of instructions without 
defs, I just didn't notice it because it currently affects only debug printing 
logic. Going to fix it.



Comment at: llvm/include/llvm/CodeGen/MachineCfgTraits.h:136-138
+  // Prefer to avoid support for bundled instructions as long as we
+  // don't really need it.
+  assert(!m_instr->isBundle());

arsenm wrote:
> I've been thinking about more aggressively using bundles around call sites to 
> handle waterfall looping around divergent calls with SGPR arguments
Hmm, so what's the correct iteration behavior in the presence of bundles? 
Iterate over all instructions in the bundle (which is that 
MachineBasicBlock::instr_iterator does) and only iterate over explicit defs? I 
think that's what makes the most sense, and what I'm going with for now...



Comment at: llvm/lib/CodeGen/MachineCfgTraits.cpp:27-29
+void MachineCfgTraits::Printer::printBlockName(raw_ostream ,
+   MachineBasicBlock *block) const 
{
+  out << "bb." << block->getNumber();

arsenm wrote:
> I think this should be added to MachineBasicBlock. The same logic is already 
> repeated in MIRPrinter (and the MBB dump function uses a different prefix)
D83253


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Matt Arsenault via Phabricator via cfe-commits]

arsenm added inline comments.



Comment at: llvm/include/llvm/CodeGen/MachineCfgTraits.h:133
+  ++m_def;
+  if (m_def == m_instr->defs().end()) {
+++m_instr;

!= return early?



Comment at: llvm/include/llvm/CodeGen/MachineCfgTraits.h:136-138
+  // Prefer to avoid support for bundled instructions as long as we
+  // don't really need it.
+  assert(!m_instr->isBundle());

I've been thinking about more aggressively using bundles around call sites to 
handle waterfall looping around divergent calls with SGPR arguments



Comment at: llvm/lib/CodeGen/MachineCfgTraits.cpp:27-29
+void MachineCfgTraits::Printer::printBlockName(raw_ostream ,
+   MachineBasicBlock *block) const 
{
+  out << "bb." << block->getNumber();

I think this should be added to MachineBasicBlock. The same logic is already 
repeated in MIRPrinter (and the MBB dump function uses a different prefix)



Comment at: llvm/lib/CodeGen/MachineCfgTraits.cpp:32
+if (irBlock->hasName())
+  out << "." << irBlock->getName();
+  }

Single quotes around .



Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D83088/new/

https://reviews.llvm.org/D83088



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D83088: Introduce CfgTraits abstraction

[Nicolai Hähnle via Phabricator via cfe-commits]

nhaehnle created this revision.
nhaehnle added reviewers: arsenm, RKSimon, mehdi_amini, courbet.
Herald added subscribers: cfe-commits, msifontes, jurahul, Kayjukh, vkmr, 
grosul1, Joonsoo, stephenneuendorffer, liufengdb, aartbik, lucyrfox, mgester, 
arpith-jacob, nicolasvasilache, antiagainst, shauheen, jpienaar, rriddle, 
rogfer01, kuhar, hiraditya, mgorny, wdng.
Herald added a reviewer: rriddle.
Herald added a reviewer: aartbik.
Herald added projects: clang, MLIR, LLVM.
nhaehnle added a parent revision: D83087: DomTree: remove explicit use of 
DomTreeNodeBase::iterator.
nhaehnle added a child revision: D83089: DomTree: Extract (mostly) read-only 
logic into type-erased base classes.

The CfgTraits abstraction simplfies writing algorithms that are
generic over the type of CFG, and enables writing such algorithms
as regular non-template code that operates on opaque references
to CFG blocks and values.

Implementations of CfgTraits provide operations on the concrete
CFG types, e.g. `IrCfgTraits::BlockRef` is `BasicBlock *`.

CfgInterface is an abstract base class which provides operations
on opaque types CfgBlockRef and CfgValueRef. Those opaque types
encapsulate a `void *`, but the meaning depends on the concrete
CFG type. For example, MachineCfgTraits -- for use with MachineIR
in SSA form -- encodes a Register inside CfgValueRef. Converting
between concrete references and opaque/generic ones is done by
CfgTraits::{fromGeneric,toGeneric}. Convenience methods
CfgTraits::{un}wrap{Iterator,Range} are available as well.

Writing algorithms in terms of CfgInterface adds some overhead
(virtual method calls, plus in same cases it removes the
opportunity to inline iterators), but can be much more convenient
since generic algorithms can be written as non-templates.

This patch adds implementations of CfgTraits for all CFGs on
which dominator trees are calculated, so that the dominator
tree can be ported to this machinery. Only IrCfgTraits (LLVM IR)
and MachineCfgTraits (Machine IR in SSA form) are complete, the
other implementations are limited to the absolute minimum
required to make the upcoming dominator tree changes work.

Change-Id: Ia75f4f268fded33fca11218a7d578c9aec1f3f4d


Repository:
  rG LLVM Github Monorepo

https://reviews.llvm.org/D83088

Files:
  clang/include/clang/Analysis/Analyses/Dominators.h
  llvm/include/llvm/CodeGen/MachineCfgTraits.h
  llvm/include/llvm/IR/CFG.h
  llvm/include/llvm/Support/CfgTraits.h
  llvm/lib/CodeGen/CMakeLists.txt
  llvm/lib/CodeGen/MachineCfgTraits.cpp
  llvm/lib/IR/CFG.cpp
  llvm/lib/IR/CMakeLists.txt
  llvm/lib/Support/CMakeLists.txt
  llvm/lib/Support/CfgTraits.cpp
  llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
  mlir/include/mlir/IR/Dominance.h

Index: mlir/include/mlir/IR/Dominance.h
===
--- mlir/include/mlir/IR/Dominance.h
+++ mlir/include/mlir/IR/Dominance.h
@@ -10,8 +10,37 @@
 #define MLIR_IR_DOMINANCE_H
 
 #include "mlir/IR/RegionGraphTraits.h"
+#include "llvm/Support/CfgTraits.h"
 #include "llvm/Support/GenericDomTree.h"
 
+namespace mlir {
+
+/// Partial CFG traits for MLIR's CFG, without a value type.
+class CfgTraitsBase : public llvm::CfgTraitsBase {
+public:
+  using ParentType = Region;
+  using BlockRef = Block *;
+  using ValueRef = void;
+
+  static llvm::CfgBlockRef toGeneric(BlockRef block) {
+return makeOpaque(block);
+  }
+  static BlockRef fromGeneric(llvm::CfgBlockRef block) {
+return static_cast(getOpaque(block));
+  }
+};
+
+class CfgTraits : public llvm::CfgTraits {
+  static Region *getBlockParent(Block *block) { return block->getParent(); }
+};
+
+} // namespace mlir
+
+template <>
+struct llvm::CfgTraitsFor {
+  using CfgTraits = mlir::CfgTraits;
+};
+
 extern template class llvm::DominatorTreeBase;
 extern template class llvm::DominatorTreeBase;
 
Index: llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
===
--- llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
+++ llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
@@ -18,9 +18,33 @@
 #include "VPlan.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/Support/CfgTraits.h"
 
 namespace llvm {
 
+/// Partial CFG traits for VPlan's CFG, without a value type.
+class VPCfgTraitsBase : public CfgTraitsBase {
+public:
+  using ParentType = VPRegionBlock;
+  using BlockRef = VPBlockBase *;
+  using ValueRef = void;
+
+  static CfgBlockRef toGeneric(BlockRef block) {
+return makeOpaque(block);
+  }
+  static BlockRef fromGeneric(CfgBlockRef block) {
+return static_cast(getOpaque(block));
+  }
+};
+
+class VPCfgTraits : public CfgTraits {
+  static VPRegionBlock *getBlockParent(VPBlockBase *block) {
+return block->getParent();
+  }
+};
+
+template <> struct CfgTraitsFor { using CfgTraits = VPCfgTraits; };
+
 /// Template specialization of the standard LLVM dominator tree utility for
 /// VPBlockBases.
 using