I just wonder if there is anyone counting on the current ordering of uses.
Although, I think they shouldn't...

I like it! Great job!

I admit, I don't like this change. This is a work around a design flaw in the old PM. However, it seems like the right decision to handle it, right now.
I think we should post a RFC for a new - *cough* - PM... ;)

In D81236#2101924, @jdoerfert wrote:

Do you have someone in mind? Or would you just want to wait?

Not sure if waiting would help much, if we don't add new reviewers. Perhaps add @chandlerc , @rnk , @lattner , @mehdi_amini, @asbirlea, and maybe others who worked on these files (if needed).

This change should be split into 2.
One for the PM changes and the other for the LoopExtractor (that depend on the previous change).
Regardless, the changes in the PM should be reviewed by more people...

In D81236#2082487, @serge-sans-paille wrote:

I investigated, and BreakCriticalEdges is a dependency of LoopExtractor, and it's the pass that triggers the change.

This makes more sense. Every pass (in our case - BreakCriticalEdges) is responsible for reporting to the PM about the preserved (and non preserved) analyses.
I am not sure, what bug are you trying to tackle?
In case the LoopExtractor does nothing, it will report that all analyses are preserved, but the preceding call to BreakCriticalEdges will (and if it doesn't - it should) already report the non preserved analyses.
I guess, what you didn't expect is the fact that running the LoopExtractor will trigger BreakCriticalEdges, but although it may be a strange/ugly behavior, it is still valid.

There seems to be a more profound bug underneath.
Is this how every pass that use LoopInfo handle it?
It seems like the real issue is with LoopInfo - an analysis shouldn't do a transformation.

Update algorithm to use a custom GraphTraits and a NodeRef that holds the set of nodes for the subgraph.
This simplifies the algorithm quite a bit.

Added a test case.

In D80399#2056708, @foad wrote:

It looks like all those test diffs are caused by naming values. Can you add (perhaps even precommit) a test where your change makes a real improvement?

Updated tests to fit the change.

This is a second take of the solution, using SCCs instead of LoopInfo.
This algorithm can also handle irreducible loops, and, generally, any kind of cycle in the graph.

Of course, this requires also fixing the tests affected by this change; but I wanted to present the change first, and if approved, I'll work on fixing the tests.

In D79037#2040926, @sameerds wrote:

TBH, I spent a small amount of time visualizing the new testcase, but couldn't figure out the problem, nor the solution. I see that the check for currentLoopSize is moved up the control flow a bit, but I didn't see why.

We need to move up the check for *CurrentLoopSize, as in the case it is zero, then we no longer need to skip nodes, and just continue to the next node/loop.
The simplified, new test case, demonstrate a case where it is needed.

Simplified the new test case.

Ping

Fixed the bug causing an infinite loop in the new testcase.

Thanks both of you.
I'll revert and update the patch for it.

In D79037#2035980, @piotr wrote:

Hi, This commit makes some compilations go into an infinite loop. I will try to prepare a reproducer.

Thanks.
Waiting for a test case...

Rename Invert2 variable to InvertCond2.
Hope it makes more sense.

Ping

In D79037#2028811, @sameerds wrote:

LGTM. It would be nice if you can move the following tests to the new file and demonstrate that that they are fixed. But that need not hold up this review any longer.

• test/Transforms/StructurizeCFG/AMDGPU/backedge-id-bug.ll
• test/Transforms/StructurizeCFG/AMDGPU/backedge-id-bug-xfail.ll

[EDIT] Actually added the test names.

Added test for interleaved sibling loops, and change the test file name to "interleaved-loop-order.ll".

In D79037#2024574, @sameerds wrote:

Actually, I take that back. Consider the following CFG:

A -> H1, H2
H1->B, C
B->H1
C->B, H2
H2->E
E->H2, F

A is the entry and F is the exit. The loops (H1, B, C) and (H2, E) are siblings with backedges B->H1 and E->H2 respectively. C is an exiting block in the first loop that branches to H2. One POT would be "B, F, E, H2, C, H1, A". When iterating in reverse, the loop with H1 is started first, but H2 from the second loop is encountered before the first loop is completed.

In D79037#2022768, @sameerds wrote:

I see. It sure does look like PR25378. Then the only thing left is one new test with two sibling loops. The intention is to cover the case where CurrentLoop is not the parent of L.

I don't think it is possible, although I might be wrong.
Because the way I see it, for loop A be interfered with another loop B, while POT, there must be at least one block that belongs to loop A that is dependent on at least one block in loop B. But then loop B must be finished before loop A, and actually inside it. Otherwise, it won't be recognized as a separate loop.

The problem with those tests is something else, and not produced by the wrong ordering. You may refer to PR25378 for an example.
Still, this fix the ordering issue and fixes PR41509 (and its duplicates).
I think we should insert this patch, and attend to the other bug as a separate issue.

Ping

Removed pushPathToAncestor.

Done requested changes.

In D79037#2016160, @sameerds wrote:

It seems the new commit is an incremental update on the previous commit. Can you please submit a single squashed commit, so that the change can be compared against the original state of the trunk?

I am not sure what do you mean. In this page in the Phabricator, under [Revision Contents]->[History] you can choose which of the patch revisions to diff. The default is "Base" against the latest "Diff no.".

Thanks for the references.
I'm abandoning this change, due to lack of interest.

Done requested changes.

In D78746#2007393, @Wallbraker wrote:

This is a fairly substantial ABI break not sure how to deal with this best.

Update test to include debug info, and add some comments.

Changed the name of the test file to pr45476.cpp.

Simplify function using IgnoreParenNoopCasts.

Use the old structure of the algorithm, with the fix, as requested.

Added test.

The variables naming convention is inconsistent.
LLVM is using CamelCase while MLIR is using camelBack.
I know there have been some discussions regarding changing LLVM to use camelBack for variables as well, but I am not sure if there was any conclusion...

Note that MLIR_MAIN_INCLUDE_DIR is used in almost all (if not all) the CMakeLists.txt in the project.

"llvm/docs/ProgrammersManual.rst" needs to be updated as well.

Let me shed a little light on the Waymarking algorithm: