ping

I'm not trying to fully solve the live range splitting problem greedy regalloc hits. I'm trying to eliminate the isBasicBlockPrologue concept that fastregalloc trips over when inserting spills at the beginning of the block

It's unclear to me what this is trying to achieve. If it is to prevent

bb:
  <-- reload inserted here during live range splitting
  $exec = S_OR_B64 $exec, %other
  ... rest of code ...

... then this change only replaces it by:

bb:
  <-- reload inserted here during live range splitting
  $exec = S_OR_B64_term $exec, %other
  // fallthrough

Hi Carl, what's the status of this?

In D87674#2290548, @madhur13490 wrote:

The revert also highlights the problem that we don't have representative test in llvm/test :(

In D87674#2290434, @madhur13490 wrote:

In D87674#2290419, @arsenm wrote:

In D87674#2290418, @madhur13490 wrote:

In D87674#2290396, @mareko wrote:

Yes, this commit is incorrect. It completely breaks code linking in Mesa OpenGL. s_waitcnt is required at the end of all global functions that return values.

Please revert. @nhaehnle

I don't understand why would it fail. This patch just moves s_waitcnt to the caller so they would be executed anyway. I think I am missing something. It would be helpful to root cause if we can isolate to a small test case.

Shader returns aren't real returns and the "caller" doesn't wait

I see. So how should this be implemented? May be we conditionalize this patch just for compute?

ReplaceNodeResults expects the result type to be changed in semi-magical ways during vector type legalization, which is non-obvious since the method can be called from different places. I think it *could* be made to work with a lot of patience, but it's really a bad interface -- and besides, by doing it in IR we reduce code duplication between SelectionDAG and GlobalISel, which is an added benefit IMO.

Well the globalisel handling should be much simpler. We have a lot of stuff that's randomly handled in the IR to work around the DAG which long term should be moved where it belongs in codegen

• cleanup operators on CfgOpaqueType
• address other review comments

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.

Hmm, forgot to adjust the author field to you for that commit. Sorry about that, I'm doing it for the other ones.

In D86154#2224272, @arsenm wrote:

In D86154#2224270, @nhaehnle wrote:

Note that part of my motivation here over D84639 is to support more general types on the lane intrinsics, since they also express some semantic content which would be interesting to be able to express e.g. on descriptors. I wasn't able to bend the SelectionDAG type legalization to my will, so that's why I instead "legalize" the intrinsics in the AMDGPUCodeGenPrepare pass.

Don't you just need to handle this in ReplaceNodeResults the same way?

Don't duplicate the intrinsics. Rely on D86317 to reduce the pain of this
change caused to downstream users.

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.

clang-format fixes

• tighten the static rules about cycles: there was a gap in the exact phrasing if two loop heart intrinsics in a cycle use _different_ convergence tokens
• add verifier checks and corresponding tests for the static rules

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?

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.

Note that part of my motivation here over D84639 is to support more general types on the lane intrinsics, since they also express some semantic content which would be interesting to be able to express e.g. on descriptors. I wasn't able to bend the SelectionDAG type legalization to my will, so that's why I instead "legalize" the intrinsics in the AMDGPUCodeGenPrepare pass.

D86154 is an attempt to do essentially this, on all lane intrinsics simultaneously, giving them a new name to avoid a flag day change.

In D85838#2222073, @Paul-C-Anagnostopoulos wrote:

In D85838#2222000, @nhaehnle wrote:

First of all, thank you for doing this. I haven't gone through it fully yet. The main thing that is missing in my opinion is to remove stuff from the existing files. You include here a listing of TableGen syntax -- that's fine, but it's now redundant with what's in TableGen/LangRef.rst, and this redundancy is a very bad place for us to be in.

You are most welcome. My plan was to get this committed first. Note that this includes an update to the TableGen Overview to refer to this document rather than the two old ones. A search turns up no other references to the two old documents in the Clang or LLVM documentation. Then once this is committed, we can delete the two old files. (Is that what we do, delete them?)

Do I need to reformat the code as Lint suggests? Most of the if (!xxx) return ... tests in the code are on one line.

I like this. I agree with David that the goal should be to remove existing uses of the old syntax, but I think it's fine to do that in a separate patch. One small nit, apart from that LGTM.

LGTM

First of all, thank you for doing this. I haven't gone through it fully yet. The main thing that is missing in my opinion is to remove stuff from the existing files. You include here a listing of TableGen syntax -- that's fine, but it's now redundant with what's in TableGen/LangRef.rst, and this redundancy is a very bad place for us to be in.

• add an inline assembly test
• simplification suggest by a review comment

• use llvm_unreachable

• add another test case

• sink use getCalledFunction() below convergence check in ValueTracking

Add more language about loops

On second thought, can we make this not be a flag-day change?

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

LGTM minus something rather obvious.

Typos and yet slightly more detail.

Actually submit all the changes that I thought I had submitted
two days ago.

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?

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)

With this change, I've edited the documents in a way where I hope all
comments have been addressed.

Address a first batch of review comments. I got almost as far as the final examples section.

I am abandoning this change in favor of D85603, which is the next and hopefully final iteration on this.

LGTM

LGTM

Do you have a pointer to how this is planned to be used in the frontend? Why is the per-function attribute not enough?

I think this makes sense, but it is a flag-day change for both Mesa and LLPC. Intrinsics created with incorrect mangling don't fall over completely (as evidenced by the fact that your change *doesn't* change the test files), but certain things like attributes tend to not work quite correctly anymore.

Now that I'm actually editing this text, I realize that this is an older version than I thought. I've given up on "join" and "point" as being too noisy in the IR in favor of something that more explicitly tracks loop structure, which is the real point of concern at least for what we care about.

This is a nice cleanup, thanks. LGTM.

LGTM

It's interesting that you end up using a modified post-order where loops are kept contiguous, I found the same thing helpful in my work on control flow lowering in AMDGPU.

Can you expand on the issues that are present here?

It's hard to say whether this is really correct given how underdefined the control flow pseudos are, but it seems like a pretty reasonable change to me. Assuming you've properly tested this change, LGTM

Update the comment above removeTerminatorBit. LGTM otherwise.

LGTM and thanks, I think this kind of change may help with the codegen in my new control flow lowering.

LGTM with the option name fixed, and please adjust the variable name also (amdgcn-skip-cache-invalidations --> AmdgcnSkipCacheInvalidations).